transform.alc 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483
  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 : String, ignore : 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. if (bool_not(set_in(ignore, read_attribute(schedule_model, next, "label")))):
  40. list_append(schedule, next)
  41. required_size = required_size - 1
  42. // If it is an edge, we should also add the target and source
  43. if (is_edge(schedule_model["model"][next])):
  44. // Add the target/source to the schedule
  45. set_add(workset, reverseKeyLookup(schedule_model["model"], read_edge_src(schedule_model["model"][next])))
  46. set_add(workset, reverseKeyLookup(schedule_model["model"], read_edge_dst(schedule_model["model"][next])))
  47. // Also add all outgoing links
  48. counter = read_nr_out(schedule_model["model"][next])
  49. while (counter > 0):
  50. counter = counter - 1
  51. if (set_in_node(schedule_model["model"], read_out(schedule_model["model"][next], counter))):
  52. set_add(workset, reverseKeyLookup(schedule_model["model"], read_out(schedule_model["model"][next], counter)))
  53. return schedule!
  54. Element function get_possible_bindings(host_model : Element, schedule_model : Element, current_element : String, map : Element):
  55. Element options
  56. String src_label
  57. String dst_label
  58. String typename
  59. String original_typename
  60. options = create_node()
  61. typename = read_type(schedule_model, current_element)
  62. original_typename = string_substr(typename, 4, string_len(typename))
  63. log("Getting possible bindings for " + current_element)
  64. log(" type: " + typename)
  65. if (is_edge(schedule_model["model"][current_element])):
  66. log(" is_edge")
  67. // Is an edge, so check for already bound source/target
  68. src_label = read_attribute(schedule_model, reverseKeyLookup(schedule_model["model"], read_edge_src(schedule_model["model"][current_element])), "label")
  69. dst_label = read_attribute(schedule_model, reverseKeyLookup(schedule_model["model"], read_edge_dst(schedule_model["model"][current_element])), "label")
  70. if (bool_and(set_in(dict_keys(map), src_label), set_in(dict_keys(map), dst_label))):
  71. // Source and destination are bound
  72. log(" SD bound")
  73. options = allOutgoingAssociationInstances(host_model, map[src_label], original_typename)
  74. log(" Outgoing associations instances: " + set_to_string(options))
  75. log(" Incoming associations instances: " + set_to_string(allIncomingAssociationInstances(host_model, map[dst_label], original_typename)))
  76. options = set_overlap(options, allIncomingAssociationInstances(host_model, map[dst_label], original_typename))
  77. elif (set_in(dict_keys(map), src_label)):
  78. // Source is bound
  79. log(" S bound")
  80. options = allOutgoingAssociationInstances(host_model, map[src_label], original_typename)
  81. elif (set_in(dict_keys(map), dst_label)):
  82. // Destination is bound
  83. log(" D bound")
  84. options = allIncomingAssociationInstances(host_model, map[dst_label], original_typename)
  85. else:
  86. // Neither is bound, so just get all of them
  87. log("ERROR: unbound source/target for association!")
  88. //TODO should actually return all
  89. return create_node()!
  90. else:
  91. log(" is_node")
  92. // Is a node, so find whether or not there are some connections that are already resolved
  93. Element ic
  94. Element oc
  95. String poll
  96. ic = allIncomingAssociationInstances(schedule_model, current_element, "PreElement")
  97. oc = allOutgoingAssociationInstances(schedule_model, current_element, "PreElement")
  98. while (bool_and(read_nr_out(ic) > 0, read_nr_out(options) == 0)):
  99. poll = set_pop(ic)
  100. log(" poll I " + poll)
  101. if (dict_in(map, read_attribute(schedule_model, poll, "label"))):
  102. // This incoming link is already defined, so we just have one option: the destination of the link we matched
  103. set_add(options, readAssociationDestination(host_model, map[read_attribute(schedule_model, poll, "label")]))
  104. while (bool_and(read_nr_out(oc) > 0, read_nr_out(options) == 0)):
  105. poll = set_pop(oc)
  106. log(" poll O " + poll)
  107. if (dict_in(map, read_attribute(schedule_model, poll, "label"))):
  108. // This incoming link is already defined, so we just have one option: the destination of the link we matched
  109. set_add(options, readAssociationSource(host_model, map[read_attribute(schedule_model, poll, "label")]))
  110. if (read_nr_out(options) == 0):
  111. // Is a node and no connections, so we just pick all options
  112. log(" empty")
  113. options = allInstances(host_model, original_typename)
  114. elif (read_nr_out(options) > 1):
  115. // Multiple "only" options, which will not work out: no options!
  116. log(" multi!")
  117. return create_node()!
  118. // Filter options further
  119. Element filtered_options
  120. String option
  121. log(" Got options: " + set_to_string(options))
  122. filtered_options = create_node()
  123. while (read_nr_out(options) > 0):
  124. option = set_pop(options)
  125. // Check for detecting same element twice
  126. if (bool_not(set_in(map, option))):
  127. // Option is already present with another label, so skip this!
  128. // Check for local constraints of element
  129. if (element_eq(read_attribute(schedule_model, current_element, "constraint"), read_root())):
  130. // No local constraints, so all is well
  131. set_add(filtered_options, option)
  132. else:
  133. // Check local constraints and add only if positive
  134. Element constraint_function
  135. Boolean result
  136. Element func
  137. constraint_function = read_attribute(schedule_model, current_element, "constraint")
  138. func = get_func_AL_model(constraint_function)
  139. result = func(host_model, option)
  140. log("Execute constraint on " + dict_to_string(option))
  141. log("Result: " + cast_e2s(result))
  142. if (result):
  143. set_add(filtered_options, option)
  144. return filtered_options!
  145. Element function full_match(host_model : Element, schedule_model : Element, current : String):
  146. Element NACs
  147. String LHS
  148. String NAC
  149. Element mappings
  150. Element mapping
  151. Integer i
  152. Element result
  153. Element final_mappings
  154. Boolean allowed
  155. final_mappings = create_node()
  156. // First match the LHS part itself to get initial mappings
  157. LHS = set_pop(allAssociationDestinations(schedule_model, current, "LHSLink"))
  158. mappings = match(host_model, schedule_model, LHS, create_node())
  159. // Got a list of all possible mappings, now filter based on NACs
  160. NACs = allAssociationDestinations(schedule_model, current, "NACLink")
  161. // For each possible mapping, we check all NACs!
  162. while (read_nr_out(mappings) > 0):
  163. mapping = set_pop(mappings)
  164. i = 0
  165. allowed = True
  166. while (i < read_nr_out(NACs)):
  167. NAC = read_edge_dst(read_out(NACs, i))
  168. result = match(host_model, schedule_model, NAC, mapping)
  169. if (read_nr_out(result) > 0):
  170. // NAC could be matched, and therefore is not allowed
  171. allowed = False
  172. break!
  173. i = i + 1
  174. if (allowed):
  175. set_add(final_mappings, mapping)
  176. return final_mappings!
  177. Element function match(host_model : Element, schedule_model : Element, LHS : String, initial_mapping : Element):
  178. // Match the schedule_model to the host_model, returning all possible mappings from schedule_model elements to host_model elements
  179. // Make the schedule first
  180. Element schedule
  181. schedule = make_matching_schedule(schedule_model, LHS, dict_keys(initial_mapping))
  182. // Now follow the schedule, incrementally building all mappings
  183. Element mappings
  184. Element new_mappings
  185. Element new_map
  186. String current_element
  187. Element map
  188. String option
  189. Element options
  190. mappings = create_node()
  191. set_add(mappings, initial_mapping)
  192. while (bool_and(read_nr_out(schedule) > 0, read_nr_out(mappings) > 0)):
  193. current_element = list_pop(schedule, 0)
  194. new_mappings = create_node()
  195. while (read_nr_out(mappings) > 0):
  196. map = set_pop(mappings)
  197. options = get_possible_bindings(host_model, schedule_model, current_element, map)
  198. while (read_nr_out(options) > 0):
  199. option = set_pop(options)
  200. new_map = dict_copy(map)
  201. dict_add(new_map, read_attribute(schedule_model, current_element, "label"), option)
  202. set_add(new_mappings, new_map)
  203. mappings = new_mappings
  204. // Finished, so try the global constraint
  205. String constraint
  206. Element func
  207. Boolean result
  208. new_mappings = create_node()
  209. constraint = read_attribute(schedule_model, LHS, "constraint")
  210. if (element_neq(constraint, read_root())):
  211. while (read_nr_out(mappings) > 0):
  212. map = set_pop(mappings)
  213. func = get_func_AL_model(constraint)
  214. result = func(host_model, map)
  215. log("Execute global constraint on " + dict_to_string(map))
  216. log("Result: " + cast_e2s(result))
  217. if (result):
  218. set_add(new_mappings, map)
  219. mappings = new_mappings
  220. return mappings!
  221. Void function rewrite(host_model : Element, schedule_model : Element, RHS : String, mapping : Element):
  222. // Rewrite the host model based on the mapping combined with the RHS
  223. Element LHS_labels
  224. Element RHS_labels
  225. Element RHS_elements
  226. Element remaining
  227. String elem
  228. String label
  229. Element labels_to_remove
  230. Element labels_to_add
  231. String typename
  232. String original_typename
  233. String src
  234. String dst
  235. Element new_mapping
  236. String new_name
  237. Element RHS_map
  238. String tmp
  239. Element value
  240. Element value_function
  241. Element action
  242. Element original_RHS_labels
  243. LHS_labels = dict_keys(mapping)
  244. RHS_labels = create_node()
  245. RHS_map = create_node()
  246. RHS_elements = allAssociationDestinations(schedule_model, RHS, "RHS_contains")
  247. while (read_nr_out(RHS_elements) > 0):
  248. tmp = set_pop(RHS_elements)
  249. label = read_attribute(schedule_model, tmp, "label")
  250. set_add(RHS_labels, label)
  251. dict_add(RHS_map, label, tmp)
  252. remaining = set_overlap(LHS_labels, RHS_labels)
  253. original_RHS_labels = set_copy(RHS_labels)
  254. while (read_nr_out(remaining) > 0):
  255. elem = set_pop(remaining)
  256. set_remove(LHS_labels, elem)
  257. set_remove(RHS_labels, elem)
  258. labels_to_remove = LHS_labels
  259. labels_to_add = set_to_list(RHS_labels)
  260. new_mapping = dict_copy(mapping)
  261. while (read_nr_out(labels_to_add) > 0):
  262. // Add the elements linked to these labels
  263. label = list_pop(labels_to_add, 0)
  264. if (element_neq(read_attribute(schedule_model, RHS_map[label], "value"), read_root())):
  265. // There is a value associated with this node
  266. value_function = read_attribute(schedule_model, RHS_map[label], "value")
  267. value = value_function(host_model, mapping)
  268. typename = read_type(schedule_model, RHS_map[label])
  269. original_typename = string_substr(typename, 5, string_len(typename))
  270. new_name = instantiate_value(host_model, original_typename, "", value)
  271. dict_add(new_mapping, label, new_name)
  272. elif (is_edge(schedule_model["model"][RHS_map[label]])):
  273. // Edge
  274. src = read_attribute(schedule_model, reverseKeyLookup(schedule_model["model"], read_edge_src(schedule_model["model"][RHS_map[label]])), "label")
  275. dst = read_attribute(schedule_model, reverseKeyLookup(schedule_model["model"], read_edge_dst(schedule_model["model"][RHS_map[label]])), "label")
  276. // First check whether both source and destination are already created
  277. if (bool_and(dict_in(new_mapping, src), dict_in(new_mapping, dst))):
  278. // Both are present, so we can make the link
  279. typename = read_type(schedule_model, RHS_map[label])
  280. original_typename = string_substr(typename, 5, string_len(typename))
  281. new_name = instantiate_link(host_model, original_typename, "", new_mapping[src], new_mapping[dst])
  282. dict_add(new_mapping, label, new_name)
  283. else:
  284. // Delay this a bit, until all are bound
  285. list_append(labels_to_add, label)
  286. else:
  287. // Node
  288. // Create the node and add it
  289. typename = read_type(schedule_model, RHS_map[label])
  290. original_typename = string_substr(typename, 5, string_len(typename))
  291. new_name = instantiate_node(host_model, original_typename, "")
  292. dict_add(new_mapping, label, new_name)
  293. while (read_nr_out(original_RHS_labels) > 0):
  294. label = set_pop(original_RHS_labels)
  295. action = read_attribute(schedule_model, RHS_map[label], "action")
  296. if (element_neq(action, read_root())):
  297. Element func
  298. func = get_func_AL_model(action)
  299. func(host_model, new_mapping[label], mapping)
  300. while (read_nr_out(labels_to_remove) > 0):
  301. // Remove the elements linked to these labels
  302. label = set_pop(labels_to_remove)
  303. model_delete_element(host_model, mapping[label])
  304. dict_delete(new_mapping, label)
  305. // Execute global action (whatever it may be)
  306. action = read_attribute(schedule_model, RHS, "action")
  307. if (element_neq(action, read_root())):
  308. Element func
  309. func = get_func_AL_model(action)
  310. func(host_model, new_mapping)
  311. return!
  312. Element function transform(host_model : Element, schedule_model : Element):
  313. // Find initial model
  314. Element all_composites
  315. String composite
  316. String current
  317. Element merged
  318. Element original_mm
  319. // Now start transforming for real
  320. all_composites = allInstances(schedule_model, "Composite")
  321. if (read_nr_out(all_composites) == 1):
  322. // Only one, so it is easy
  323. current = set_pop(all_composites)
  324. else:
  325. // Filter out those that are themselves contained
  326. while (read_nr_out(all_composites) > 0):
  327. composite = set_pop(all_composites)
  328. if (read_nr_out(allIncomingAssociationInstances(schedule_model, composite, "Contains")) == 0):
  329. // Isn't contained in any, so this is the root model!
  330. current = composite
  331. if (transform_composite(host_model, schedule_model, current)):
  332. // Success, so return True if it is in-place, or the new model if it is out-place
  333. return True!
  334. else:
  335. return False!
  336. Boolean function transform_composite(host_model : Element, schedule_model : Element, composite : String):
  337. String current
  338. String typename
  339. Boolean result
  340. current = set_pop(allAssociationDestinations(schedule_model, composite, "Initial"))
  341. while (is_nominal_instance(schedule_model, current, "Rule")):
  342. // Still a rule that we must execute
  343. typename = read_type(schedule_model, current)
  344. log("RULE: " + current)
  345. if (typename == "Atomic"):
  346. result = transform_atomic(host_model, schedule_model, current)
  347. elif (typename == "Query"):
  348. result = transform_query(host_model, schedule_model, current)
  349. elif (typename == "Composite"):
  350. result = transform_composite(host_model, schedule_model, current)
  351. elif (typename == "ForAll"):
  352. result = transform_forall(host_model, schedule_model, current)
  353. if (result):
  354. current = set_pop(allAssociationDestinations(schedule_model, current, "OnSuccess"))
  355. else:
  356. current = set_pop(allAssociationDestinations(schedule_model, current, "OnFailure"))
  357. // No longer a rule, so it is either success or failure
  358. if (is_nominal_instance(schedule_model, current, "Success")):
  359. return True!
  360. else:
  361. return False!
  362. Boolean function transform_atomic(host_model : Element, schedule_model : Element, current : String):
  363. // Execute the atomic transformation
  364. Element mappings
  365. Element mapping
  366. mappings = full_match(host_model, schedule_model, current)
  367. if (read_nr_out(mappings) > 0):
  368. // Pick one!
  369. mapping = random_choice(set_to_list(mappings))
  370. String RHS
  371. RHS = set_pop(allAssociationDestinations(schedule_model, current, "RHSLink"))
  372. rewrite(host_model, schedule_model, RHS, mapping)
  373. return True!
  374. else:
  375. return False!
  376. Boolean function transform_forall(host_model : Element, schedule_model : Element, current : String):
  377. // Execute the atomic transformation
  378. Element mappings
  379. String RHS
  380. Element mapping
  381. Boolean result
  382. mappings = full_match(host_model, schedule_model, current)
  383. if (read_nr_out(mappings) > 0):
  384. result = True
  385. else:
  386. result = False
  387. while (read_nr_out(mappings) > 0):
  388. mapping = set_pop(mappings)
  389. // TODO check if there are actually no deletions happening in the meantime of other matched elements...
  390. log("Execute RHS for binding: " + dict_to_string(mapping))
  391. RHS = set_pop(allAssociationDestinations(schedule_model, current, "RHSLink"))
  392. rewrite(host_model, schedule_model, RHS, mapping)
  393. return result!
  394. Boolean function transform_query(host_model : Element, schedule_model : Element, current : String):
  395. // Execute the transformation
  396. Element mappings
  397. Element mapping
  398. mappings = full_match(host_model, schedule_model, current)
  399. if (read_nr_out(mappings) > 0):
  400. return True!
  401. else:
  402. return False!