transform.alc 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410
  1. include "primitives.alh"
  2. include "object_operations.alh"
  3. include "modelling.alh"
  4. include "random.alh"
  5. include "conformance_scd.alh"
  6. include "model_management.alh"
  7. Element function make_matching_schedule(schedule_model : Element, LHS : Element):
  8. Element schedule
  9. Element workset
  10. Element all_elements
  11. Element full_all_elements
  12. Integer required_size
  13. String new_element
  14. Integer counter
  15. String next
  16. Element tmp
  17. // Initialize
  18. schedule = create_node()
  19. workset = create_node()
  20. all_elements = allAssociationDestinations(schedule_model, LHS, "LHS_contains")
  21. full_all_elements = set_copy(all_elements)
  22. required_size = read_nr_out(all_elements)
  23. // Need to keep adding to the schedule
  24. while (read_nr_out(schedule) < required_size):
  25. // workset is empty, but we still need to add to the list
  26. // Therefore, we pick a random, unbound node, and add it to the workset
  27. new_element = set_pop(all_elements)
  28. while (bool_or(set_in(schedule, new_element), is_edge(schedule_model["model"][new_element]))):
  29. // Element is not usable, so pick another one
  30. new_element = set_pop(all_elements)
  31. set_add(workset, new_element)
  32. // Handle the workset
  33. while (read_nr_out(workset) > 0):
  34. // Still elements in the workset, so pop from these first
  35. next = set_pop(workset)
  36. // Check if element might not be already used somewhere
  37. if (bool_not(set_in(schedule, next))):
  38. if (set_in(full_all_elements, next)):
  39. list_append(schedule, next)
  40. // If it is an edge, we should also add the target and source
  41. if (is_edge(schedule_model["model"][next])):
  42. // Add the target/source to the schedule
  43. set_add(workset, reverseKeyLookup(schedule_model["model"], read_edge_src(schedule_model["model"][next])))
  44. set_add(workset, reverseKeyLookup(schedule_model["model"], read_edge_dst(schedule_model["model"][next])))
  45. // Also add all outgoing links
  46. counter = read_nr_out(schedule_model["model"][next])
  47. while (counter > 0):
  48. counter = counter - 1
  49. if (set_in_node(schedule_model["model"], read_out(schedule_model["model"][next], counter))):
  50. set_add(workset, reverseKeyLookup(schedule_model["model"], read_out(schedule_model["model"][next], counter)))
  51. return schedule!
  52. Element function get_possible_bindings(host_model : Element, schedule_model : Element, current_element : String, map : Element):
  53. Element options
  54. String src_label
  55. String dst_label
  56. String typename
  57. String original_typename
  58. options = create_node()
  59. typename = reverseKeyLookup(schedule_model["metamodel"]["model"], dict_read_node(schedule_model["type_mapping"], schedule_model["model"][current_element]))
  60. original_typename = string_substr(typename, 4, string_len(typename))
  61. if (is_edge(schedule_model["model"][current_element])):
  62. // Is an edge, so check for already bound source/target
  63. src_label = read_attribute(schedule_model, reverseKeyLookup(schedule_model["model"], read_edge_src(schedule_model["model"][current_element])), "label")
  64. dst_label = read_attribute(schedule_model, reverseKeyLookup(schedule_model["model"], read_edge_dst(schedule_model["model"][current_element])), "label")
  65. if (bool_and(set_in(dict_keys(map), src_label), set_in(dict_keys(map), dst_label))):
  66. // Source and destination are bound
  67. options = allOutgoingAssociationInstances(host_model, map[src_label], original_typename)
  68. options = set_overlap(options, allIncomingAssociationInstances(host_model, map[dst_label], original_typename))
  69. elif (set_in(dict_keys(map), src_label)):
  70. // Source is bound
  71. options = allOutgoingAssociationInstances(host_model, map[src_label], original_typename)
  72. elif (set_in(dict_keys(map), dst_label)):
  73. // Destination is bound
  74. options = allIncomingAssociationInstances(host_model, map[dst_label], original_typename)
  75. else:
  76. // Neither is bound, so just get all of them
  77. log("ERROR: unbound source/target for association!")
  78. return create_node()!
  79. else:
  80. // Is a node, so find whether or not there are some connections that are already resolved
  81. // TODO check implementation
  82. Element ic
  83. Element oc
  84. String poll
  85. ic = allIncomingAssociationInstances(schedule_model, current_element, "Pre_Element")
  86. oc = allOutgoingAssociationInstances(schedule_model, current_element, "Pre_Element")
  87. while (bool_and(read_nr_out(ic) > 0, read_nr_out(options) == 0)):
  88. poll = set_pop(ic)
  89. if (dict_in(map, read_attribute(schedule_model, poll, "label"))):
  90. // This incoming link is already defined, so we just have one option: the destination of the link we matched
  91. set_add(options, readAssociationDestination(host_model, map[read_attribute(schedule_model, poll, "label")]))
  92. while (bool_and(read_nr_out(oc) > 0, read_nr_out(options) == 0)):
  93. poll = set_pop(oc)
  94. if (dict_in(map, read_attribute(schedule_model, poll, "label"))):
  95. // This incoming link is already defined, so we just have one option: the destination of the link we matched
  96. set_add(options, readAssociationSource(host_model, map[read_attribute(schedule_model, poll, "label")]))
  97. if (read_nr_out(options) == 0):
  98. // Is a node and no connections, so we just pick all options
  99. options = allInstances(host_model, original_typename)
  100. // Filter options further
  101. Element filtered_options
  102. String option
  103. filtered_options = create_node()
  104. while (read_nr_out(options) > 0):
  105. option = set_pop(options)
  106. // Check for detecting same element twice
  107. if (bool_not(set_in(map, option))):
  108. // Option is already present with another label, so skip this!
  109. // Check for local constraints of element
  110. if (element_eq(read_attribute(schedule_model, current_element, "constraint"), read_root())):
  111. // No local constraints, so all is well
  112. set_add(filtered_options, option)
  113. else:
  114. // Check local constraints and add only if positive
  115. Element constraint_function
  116. constraint_function = read_attribute(schedule_model, current_element, "constraint")
  117. Boolean result
  118. result = constraint_function(host_model, option)
  119. if (result):
  120. set_add(filtered_options, option)
  121. return filtered_options!
  122. Element function match(host_model : Element, schedule_model : Element, LHS : Element):
  123. // Match the schedule_model to the host_model, returning all possible mappings from schedule_model elements to host_model elements
  124. // Make the schedule first
  125. Element schedule
  126. schedule = make_matching_schedule(schedule_model, LHS)
  127. // Now follow the schedule, incrementally building all mappings
  128. Element mappings
  129. Element new_mappings
  130. Element new_map
  131. String current_element
  132. Element map
  133. String option
  134. Element options
  135. mappings = create_node()
  136. set_add(mappings, create_node())
  137. while (bool_and(read_nr_out(schedule) > 0, read_nr_out(mappings) > 0)):
  138. current_element = list_pop(schedule, 0)
  139. new_mappings = create_node()
  140. while (read_nr_out(mappings) > 0):
  141. map = set_pop(mappings)
  142. options = get_possible_bindings(host_model, schedule_model, current_element, map)
  143. while (read_nr_out(options) > 0):
  144. option = set_pop(options)
  145. new_map = dict_copy(map)
  146. dict_add(new_map, read_attribute(schedule_model, current_element, "label"), option)
  147. set_add(new_mappings, new_map)
  148. mappings = new_mappings
  149. // Finished, so try the global constraint
  150. Element constraint
  151. new_mappings = create_node()
  152. constraint = read_attribute(schedule_model, LHS, "constraint")
  153. if (element_neq(constraint, read_root())):
  154. while (read_nr_out(mappings) > 0):
  155. map = set_pop(mappings)
  156. if (constraint(host_model, map)):
  157. set_add(new_mappings, map)
  158. mappings = new_mappings
  159. return mappings!
  160. Void function rewrite(host_model : Element, schedule_model : Element, RHS : String, mapping : Element):
  161. // Rewrite the host model based on the mapping combined with the RHS
  162. Element LHS_labels
  163. Element RHS_labels
  164. Element RHS_elements
  165. Element remaining
  166. String elem
  167. String label
  168. Element labels_to_remove
  169. Element labels_to_add
  170. String typename
  171. String original_typename
  172. String src
  173. String dst
  174. Element new_mapping
  175. String new_name
  176. Element RHS_map
  177. String tmp
  178. Element value
  179. Element value_function
  180. Element action
  181. Element original_RHS_labels
  182. LHS_labels = dict_keys(mapping)
  183. RHS_labels = create_node()
  184. RHS_map = create_node()
  185. RHS_elements = allAssociationDestinations(schedule_model, RHS, "RHS_contains")
  186. while (read_nr_out(RHS_elements) > 0):
  187. tmp = set_pop(RHS_elements)
  188. label = read_attribute(schedule_model, tmp, "label")
  189. set_add(RHS_labels, label)
  190. dict_add(RHS_map, label, tmp)
  191. remaining = set_overlap(LHS_labels, RHS_labels)
  192. original_RHS_labels = set_copy(RHS_labels)
  193. while (read_nr_out(remaining) > 0):
  194. elem = set_pop(remaining)
  195. set_remove(LHS_labels, elem)
  196. set_remove(RHS_labels, elem)
  197. labels_to_remove = LHS_labels
  198. labels_to_add = set_to_list(RHS_labels)
  199. new_mapping = dict_copy(mapping)
  200. while (read_nr_out(labels_to_add) > 0):
  201. // Add the elements linked to these labels
  202. label = list_pop(labels_to_add, 0)
  203. if (element_neq(read_attribute(schedule_model, RHS_map[label], "value"), read_root())):
  204. // There is a value associated with this node
  205. value_function = read_attribute(schedule_model, RHS_map[label], "value")
  206. value = value_function(host_model, mapping)
  207. typename = reverseKeyLookup(schedule_model["metamodel"]["model"], dict_read_node(schedule_model["type_mapping"], schedule_model["model"][RHS_map[label]]))
  208. original_typename = string_substr(typename, 5, string_len(typename))
  209. new_name = instantiate_value(host_model, original_typename, "", value)
  210. dict_add(new_mapping, label, new_name)
  211. elif (is_edge(schedule_model["model"][RHS_map[label]])):
  212. // Edge
  213. src = read_attribute(schedule_model, reverseKeyLookup(schedule_model["model"], read_edge_src(schedule_model["model"][RHS_map[label]])), "label")
  214. dst = read_attribute(schedule_model, reverseKeyLookup(schedule_model["model"], read_edge_dst(schedule_model["model"][RHS_map[label]])), "label")
  215. // First check whether both source and destination are already created
  216. if (bool_and(dict_in(new_mapping, src), dict_in(new_mapping, dst))):
  217. // Both are present, so we can make the link
  218. typename = reverseKeyLookup(schedule_model["metamodel"]["model"], dict_read_node(schedule_model["type_mapping"], schedule_model["model"][RHS_map[label]]))
  219. original_typename = string_substr(typename, 5, string_len(typename))
  220. new_name = instantiate_link(host_model, original_typename, "", new_mapping[src], new_mapping[dst])
  221. dict_add(new_mapping, label, new_name)
  222. else:
  223. // Delay this a bit, until all are bound
  224. list_append(labels_to_add, label)
  225. else:
  226. // Node
  227. // Create the node and add it
  228. typename = reverseKeyLookup(schedule_model["metamodel"]["model"], dict_read_node(schedule_model["type_mapping"], schedule_model["model"][RHS_map[label]]))
  229. original_typename = string_substr(typename, 5, string_len(typename))
  230. new_name = instantiate_node(host_model, original_typename, "")
  231. dict_add(new_mapping, label, new_name)
  232. while (read_nr_out(original_RHS_labels) > 0):
  233. label = set_pop(original_RHS_labels)
  234. action = read_attribute(schedule_model, RHS_map[label], "action")
  235. if (element_neq(action, read_root())):
  236. action(host_model, new_mapping[label], mapping)
  237. while (read_nr_out(labels_to_remove) > 0):
  238. // Remove the elements linked to these labels
  239. label = set_pop(labels_to_remove)
  240. model_delete_element(host_model, mapping[label])
  241. dict_delete(new_mapping, label)
  242. // Execute global action (whatever it may be)
  243. action = read_attribute(schedule_model, RHS, "action")
  244. if (element_neq(action, read_root())):
  245. action(host_model, new_mapping)
  246. return!
  247. Element function transform(host_model : Element, schedule_model : Element):
  248. // Find initial model
  249. Element all_composites
  250. String composite
  251. String current
  252. Element merged
  253. Element original_mm
  254. // Now start transforming for real
  255. all_composites = allInstances(schedule_model, "Composite")
  256. if (read_nr_out(all_composites) == 1):
  257. // Only one, so it is easy
  258. current = set_pop(all_composites)
  259. else:
  260. // Filter out those that are themselves contained
  261. while (read_nr_out(all_composites) > 0):
  262. composite = set_pop(all_composites)
  263. if (read_nr_out(allIncomingAssociationInstances(schedule_model, composite, "Contains")) == 0):
  264. // Isn't contained in any, so this is the root model!
  265. current = composite
  266. if (transform_composite(host_model, schedule_model, current)):
  267. // Success, so return True if it is in-place, or the new model if it is out-place
  268. log("Transform success!")
  269. return True!
  270. else:
  271. log("Transform failed!")
  272. return False!
  273. Boolean function transform_composite(host_model : Element, schedule_model : Element, composite : String):
  274. String current
  275. String typename
  276. Boolean result
  277. current = set_pop(allAssociationDestinations(schedule_model, composite, "Initial"))
  278. while (is_nominal_instance(schedule_model, current, "Rule")):
  279. // Still a rule that we must execute
  280. typename = reverseKeyLookup(schedule_model["metamodel"]["model"], dict_read_node(schedule_model["type_mapping"], schedule_model["model"][current]))
  281. if (typename == "Atomic"):
  282. result = transform_atomic(host_model, schedule_model, current)
  283. elif (typename == "Query"):
  284. result = transform_query(host_model, schedule_model, current)
  285. elif (typename == "Composite"):
  286. result = transform_composite(host_model, schedule_model, current)
  287. elif (typename == "ForAll"):
  288. result = transform_forall(host_model, schedule_model, current)
  289. if (result):
  290. current = set_pop(allAssociationDestinations(schedule_model, current, "OnSuccess"))
  291. else:
  292. current = set_pop(allAssociationDestinations(schedule_model, current, "OnFailure"))
  293. // No longer a rule, so it is either success or failure
  294. if (is_nominal_instance(schedule_model, current, "Success")):
  295. return True!
  296. else:
  297. return False!
  298. Boolean function transform_atomic(host_model : Element, schedule_model : Element, current : String):
  299. // Execute the atomic transformation
  300. Element mappings
  301. String LHS
  302. Element mapping
  303. LHS = set_pop(allAssociationDestinations(schedule_model, current, "AtomicLHS"))
  304. mappings = match(host_model, schedule_model, LHS)
  305. if (read_nr_out(mappings) > 0):
  306. // Pick one!
  307. mapping = random_choice(set_to_list(mappings))
  308. String RHS
  309. RHS = set_pop(allAssociationDestinations(schedule_model, current, "AtomicRHS"))
  310. rewrite(host_model, schedule_model, RHS, mapping)
  311. return True!
  312. else:
  313. return False!
  314. Boolean function transform_forall(host_model : Element, schedule_model : Element, current : String):
  315. // Execute the atomic transformation
  316. Element mappings
  317. String LHS
  318. String RHS
  319. Element mapping
  320. Boolean result
  321. LHS = set_pop(allAssociationDestinations(schedule_model, current, "AtomicLHS"))
  322. mappings = match(host_model, schedule_model, LHS)
  323. if (read_nr_out(mappings) > 0):
  324. result = True
  325. else:
  326. result = False
  327. while (read_nr_out(mappings) > 0):
  328. mapping = set_pop(mappings)
  329. // TODO check if there are actually no deletions happening in the meantime of other matched elements...
  330. RHS = set_pop(allAssociationDestinations(schedule_model, current, "AtomicRHS"))
  331. rewrite(host_model, schedule_model, RHS, mapping)
  332. return result!
  333. Boolean function transform_query(host_model : Element, schedule_model : Element, current : String):
  334. // Execute the transformation
  335. String LHS
  336. Element mappings
  337. Element mapping
  338. LHS = set_pop(allAssociationDestinations(schedule_model, current, "QueryLHS"))
  339. mappings = match(host_model, schedule_model, LHS)
  340. if (read_nr_out(mappings) > 0):
  341. return True!
  342. else:
  343. return False!