transform.alc 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427
  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. log("Finding in/out for " + current_element)
  86. log("Current mapping: " + set_to_string(map))
  87. ic = allIncomingAssociationInstances(schedule_model, current_element, "Pre_Element")
  88. oc = allOutgoingAssociationInstances(schedule_model, current_element, "Pre_Element")
  89. log("Incoming: " + set_to_string(ic))
  90. log("Outgoing: " + set_to_string(oc))
  91. log("Check incoming")
  92. while (bool_and(read_nr_out(ic) > 0, read_nr_out(options) == 0)):
  93. poll = set_pop(ic)
  94. log("Checking if already bound " + poll)
  95. if (dict_in(map, read_attribute(schedule_model, poll, "label"))):
  96. // This incoming link is already defined, so we just have one option: the destination of the link we matched
  97. log("Got match!")
  98. set_add(options, readAssociationDestination(host_model, map[read_attribute(schedule_model, poll, "label")]))
  99. log("Check outgoing")
  100. while (bool_and(read_nr_out(oc) > 0, read_nr_out(options) == 0)):
  101. poll = set_pop(oc)
  102. log("Checking if already bound " + poll)
  103. if (dict_in(map, read_attribute(schedule_model, poll, "label"))):
  104. // This incoming link is already defined, so we just have one option: the destination of the link we matched
  105. log("Got match!")
  106. set_add(options, readAssociationSource(host_model, map[read_attribute(schedule_model, poll, "label")]))
  107. if (read_nr_out(options) == 0):
  108. // Is a node and no connections, so we just pick all options
  109. log("NO, so find new instances anyway")
  110. options = allInstances(host_model, original_typename)
  111. else:
  112. log("YES, so got instance already")
  113. log("Returned options: " + set_to_string(options))
  114. // Filter options further
  115. Element filtered_options
  116. String option
  117. filtered_options = create_node()
  118. while (read_nr_out(options) > 0):
  119. option = set_pop(options)
  120. // Check for detecting same element twice
  121. if (bool_not(set_in(map, option))):
  122. // Option is already present with another label, so skip this!
  123. // Check for local constraints of element
  124. if (element_eq(read_attribute(schedule_model, current_element, "constraint"), read_root())):
  125. // No local constraints, so all is well
  126. set_add(filtered_options, option)
  127. else:
  128. // Check local constraints and add only if positive
  129. Element constraint_function
  130. constraint_function = read_attribute(schedule_model, current_element, "constraint")
  131. Boolean result
  132. result = constraint_function(host_model, option)
  133. if (result):
  134. set_add(filtered_options, option)
  135. return filtered_options!
  136. Element function match(host_model : Element, schedule_model : Element, LHS : Element):
  137. // Match the schedule_model to the host_model, returning all possible mappings from schedule_model elements to host_model elements
  138. // Make the schedule first
  139. Element schedule
  140. schedule = make_matching_schedule(schedule_model, LHS)
  141. // Now follow the schedule, incrementally building all mappings
  142. Element mappings
  143. Element new_mappings
  144. Element new_map
  145. String current_element
  146. Element map
  147. String option
  148. Element options
  149. mappings = create_node()
  150. set_add(mappings, create_node())
  151. while (bool_and(read_nr_out(schedule) > 0, read_nr_out(mappings) > 0)):
  152. current_element = list_pop(schedule, 0)
  153. new_mappings = create_node()
  154. while (read_nr_out(mappings) > 0):
  155. map = set_pop(mappings)
  156. options = get_possible_bindings(host_model, schedule_model, current_element, map)
  157. while (read_nr_out(options) > 0):
  158. option = set_pop(options)
  159. new_map = dict_copy(map)
  160. dict_add(new_map, read_attribute(schedule_model, current_element, "label"), option)
  161. set_add(new_mappings, new_map)
  162. mappings = new_mappings
  163. // Finished, so try the global constraint
  164. Element constraint
  165. new_mappings = create_node()
  166. constraint = read_attribute(schedule_model, LHS, "constraint")
  167. if (element_neq(constraint, read_root())):
  168. while (read_nr_out(mappings) > 0):
  169. map = set_pop(mappings)
  170. if (constraint(host_model, map)):
  171. set_add(new_mappings, map)
  172. mappings = new_mappings
  173. return mappings!
  174. Void function rewrite(host_model : Element, schedule_model : Element, RHS : String, mapping : Element):
  175. // Rewrite the host model based on the mapping combined with the RHS
  176. Element LHS_labels
  177. Element RHS_labels
  178. Element RHS_elements
  179. Element remaining
  180. String elem
  181. String label
  182. Element labels_to_remove
  183. Element labels_to_add
  184. String typename
  185. String original_typename
  186. String src
  187. String dst
  188. Element new_mapping
  189. String new_name
  190. Element RHS_map
  191. String tmp
  192. Element value
  193. Element value_function
  194. Element action
  195. Element original_RHS_labels
  196. LHS_labels = dict_keys(mapping)
  197. RHS_labels = create_node()
  198. RHS_map = create_node()
  199. RHS_elements = allAssociationDestinations(schedule_model, RHS, "RHS_contains")
  200. while (read_nr_out(RHS_elements) > 0):
  201. tmp = set_pop(RHS_elements)
  202. label = read_attribute(schedule_model, tmp, "label")
  203. set_add(RHS_labels, label)
  204. dict_add(RHS_map, label, tmp)
  205. remaining = set_overlap(LHS_labels, RHS_labels)
  206. original_RHS_labels = set_copy(RHS_labels)
  207. while (read_nr_out(remaining) > 0):
  208. elem = set_pop(remaining)
  209. set_remove(LHS_labels, elem)
  210. set_remove(RHS_labels, elem)
  211. labels_to_remove = LHS_labels
  212. labels_to_add = set_to_list(RHS_labels)
  213. new_mapping = dict_copy(mapping)
  214. while (read_nr_out(labels_to_add) > 0):
  215. // Add the elements linked to these labels
  216. label = list_pop(labels_to_add, 0)
  217. if (element_neq(read_attribute(schedule_model, RHS_map[label], "value"), read_root())):
  218. // There is a value associated with this node
  219. value_function = read_attribute(schedule_model, RHS_map[label], "value")
  220. value = value_function(host_model, mapping)
  221. typename = reverseKeyLookup(schedule_model["metamodel"]["model"], dict_read_node(schedule_model["type_mapping"], schedule_model["model"][RHS_map[label]]))
  222. original_typename = string_substr(typename, 5, string_len(typename))
  223. new_name = instantiate_value(host_model, original_typename, "", value)
  224. dict_add(new_mapping, label, new_name)
  225. elif (is_edge(schedule_model["model"][RHS_map[label]])):
  226. // Edge
  227. src = read_attribute(schedule_model, reverseKeyLookup(schedule_model["model"], read_edge_src(schedule_model["model"][RHS_map[label]])), "label")
  228. dst = read_attribute(schedule_model, reverseKeyLookup(schedule_model["model"], read_edge_dst(schedule_model["model"][RHS_map[label]])), "label")
  229. // First check whether both source and destination are already created
  230. if (bool_and(dict_in(new_mapping, src), dict_in(new_mapping, dst))):
  231. // Both are present, so we can make the link
  232. typename = reverseKeyLookup(schedule_model["metamodel"]["model"], dict_read_node(schedule_model["type_mapping"], schedule_model["model"][RHS_map[label]]))
  233. original_typename = string_substr(typename, 5, string_len(typename))
  234. new_name = instantiate_link(host_model, original_typename, "", new_mapping[src], new_mapping[dst])
  235. dict_add(new_mapping, label, new_name)
  236. else:
  237. // Delay this a bit, until all are bound
  238. list_append(labels_to_add, label)
  239. else:
  240. // Node
  241. // Create the node and add it
  242. typename = reverseKeyLookup(schedule_model["metamodel"]["model"], dict_read_node(schedule_model["type_mapping"], schedule_model["model"][RHS_map[label]]))
  243. original_typename = string_substr(typename, 5, string_len(typename))
  244. new_name = instantiate_node(host_model, original_typename, "")
  245. dict_add(new_mapping, label, new_name)
  246. while (read_nr_out(original_RHS_labels) > 0):
  247. label = set_pop(original_RHS_labels)
  248. action = read_attribute(schedule_model, RHS_map[label], "action")
  249. if (element_neq(action, read_root())):
  250. action(host_model, new_mapping[label], mapping)
  251. while (read_nr_out(labels_to_remove) > 0):
  252. // Remove the elements linked to these labels
  253. label = set_pop(labels_to_remove)
  254. model_delete_element(host_model, mapping[label])
  255. dict_delete(new_mapping, label)
  256. // Execute global action (whatever it may be)
  257. action = read_attribute(schedule_model, RHS, "action")
  258. if (element_neq(action, read_root())):
  259. action(host_model, new_mapping)
  260. return!
  261. Element function transform(host_model : Element, schedule_model : Element):
  262. // Find initial model
  263. Element all_composites
  264. String composite
  265. String current
  266. Element merged
  267. Element original_mm
  268. // Now start transforming for real
  269. all_composites = allInstances(schedule_model, "Composite")
  270. if (read_nr_out(all_composites) == 1):
  271. // Only one, so it is easy
  272. current = set_pop(all_composites)
  273. else:
  274. // Filter out those that are themselves contained
  275. while (read_nr_out(all_composites) > 0):
  276. composite = set_pop(all_composites)
  277. if (read_nr_out(allIncomingAssociationInstances(schedule_model, composite, "Contains")) == 0):
  278. // Isn't contained in any, so this is the root model!
  279. current = composite
  280. if (transform_composite(host_model, schedule_model, current)):
  281. // Success, so return True if it is in-place, or the new model if it is out-place
  282. log("Transform success!")
  283. return True!
  284. else:
  285. log("Transform failed!")
  286. return False!
  287. Boolean function transform_composite(host_model : Element, schedule_model : Element, composite : String):
  288. String current
  289. String typename
  290. Boolean result
  291. current = set_pop(allAssociationDestinations(schedule_model, composite, "Initial"))
  292. while (is_nominal_instance(schedule_model, current, "Rule")):
  293. // Still a rule that we must execute
  294. typename = reverseKeyLookup(schedule_model["metamodel"]["model"], dict_read_node(schedule_model["type_mapping"], schedule_model["model"][current]))
  295. if (typename == "Atomic"):
  296. result = transform_atomic(host_model, schedule_model, current)
  297. elif (typename == "Query"):
  298. result = transform_query(host_model, schedule_model, current)
  299. elif (typename == "Composite"):
  300. result = transform_composite(host_model, schedule_model, current)
  301. elif (typename == "ForAll"):
  302. result = transform_forall(host_model, schedule_model, current)
  303. if (result):
  304. current = set_pop(allAssociationDestinations(schedule_model, current, "OnSuccess"))
  305. else:
  306. current = set_pop(allAssociationDestinations(schedule_model, current, "OnFailure"))
  307. // No longer a rule, so it is either success or failure
  308. if (is_nominal_instance(schedule_model, current, "Success")):
  309. return True!
  310. else:
  311. return False!
  312. Boolean function transform_atomic(host_model : Element, schedule_model : Element, current : String):
  313. // Execute the atomic transformation
  314. Element mappings
  315. String LHS
  316. Element mapping
  317. LHS = set_pop(allAssociationDestinations(schedule_model, current, "AtomicLHS"))
  318. mappings = match(host_model, schedule_model, LHS)
  319. if (read_nr_out(mappings) > 0):
  320. // Pick one!
  321. mapping = random_choice(set_to_list(mappings))
  322. String RHS
  323. RHS = set_pop(allAssociationDestinations(schedule_model, current, "AtomicRHS"))
  324. rewrite(host_model, schedule_model, RHS, mapping)
  325. return True!
  326. else:
  327. return False!
  328. Boolean function transform_forall(host_model : Element, schedule_model : Element, current : String):
  329. // Execute the atomic transformation
  330. Element mappings
  331. String LHS
  332. String RHS
  333. Element mapping
  334. Boolean result
  335. LHS = set_pop(allAssociationDestinations(schedule_model, current, "AtomicLHS"))
  336. mappings = match(host_model, schedule_model, LHS)
  337. if (read_nr_out(mappings) > 0):
  338. result = True
  339. else:
  340. result = False
  341. while (read_nr_out(mappings) > 0):
  342. mapping = set_pop(mappings)
  343. log("Apply for mapping: " + dict_to_string(mapping))
  344. // TODO check if there are actually no deletions happening in the meantime of other matched elements...
  345. RHS = set_pop(allAssociationDestinations(schedule_model, current, "AtomicRHS"))
  346. rewrite(host_model, schedule_model, RHS, mapping)
  347. return result!
  348. Boolean function transform_query(host_model : Element, schedule_model : Element, current : String):
  349. // Execute the transformation
  350. String LHS
  351. Element mappings
  352. Element mapping
  353. LHS = set_pop(allAssociationDestinations(schedule_model, current, "QueryLHS"))
  354. mappings = match(host_model, schedule_model, LHS)
  355. if (read_nr_out(mappings) > 0):
  356. return True!
  357. else:
  358. return False!