transform.alc 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598
  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. include "library.alh"
  8. Element function make_matching_schedule(schedule_model : Element, LHS : String, ignore : Element):
  9. Element schedule
  10. Element workset
  11. Element all_elements
  12. Element full_all_elements
  13. Integer required_size
  14. String new_element
  15. Integer counter
  16. String next
  17. Element tmp
  18. String elem_id
  19. Element scheduled
  20. Element reverse
  21. reverse = make_reverse_dictionary(schedule_model["model"])
  22. // Initialize
  23. schedule = list_create()
  24. scheduled = set_create()
  25. workset = set_create()
  26. all_elements = allAssociationDestinations(schedule_model, LHS, "LHS_contains")
  27. full_all_elements = set_copy(all_elements)
  28. required_size = set_len(all_elements)
  29. // Need to keep adding to the schedule
  30. while (list_len(schedule) < required_size):
  31. // workset is empty, but we still need to add to the list
  32. // Therefore, we pick a random, unbound node, and add it to the workset
  33. new_element = set_pop(all_elements)
  34. while (bool_or(set_in(scheduled, new_element), is_edge(schedule_model["model"][new_element]))):
  35. // Element is not usable, so pick another one
  36. new_element = set_pop(all_elements)
  37. set_add(workset, new_element)
  38. // Handle the workset
  39. while (set_len(workset) > 0):
  40. // Still elements in the workset, so pop from these first
  41. next = set_pop(workset)
  42. // Check if element might not be already used somewhere
  43. if (bool_not(set_in(scheduled, next))):
  44. if (set_in(full_all_elements, next)):
  45. if (bool_not(set_in(ignore, read_attribute(schedule_model, next, "label")))):
  46. list_insert(schedule, next, 0)
  47. set_add(scheduled, next)
  48. else:
  49. required_size = required_size - 1
  50. continue!
  51. // If it is an edge, we should also add the target and source
  52. if (is_edge(schedule_model["model"][next])):
  53. // Add the target/source to the schedule
  54. set_add(workset, reverse[cast_id(read_edge_src(schedule_model["model"][next]))])
  55. set_add(workset, reverse[cast_id(read_edge_dst(schedule_model["model"][next]))])
  56. // Also add all outgoing links
  57. counter = read_nr_out(schedule_model["model"][next])
  58. while (counter > 0):
  59. counter = counter - 1
  60. elem_id = cast_id(read_out(schedule_model["model"][next], counter))
  61. if (dict_in(reverse, elem_id)):
  62. set_add(workset, reverse[elem_id])
  63. // And incoming links
  64. counter = read_nr_in(schedule_model["model"][next])
  65. while (counter > 0):
  66. counter = counter - 1
  67. elem_id = cast_id(read_in(schedule_model["model"][next], counter))
  68. if (dict_in(reverse, elem_id)):
  69. set_add(workset, reverse[elem_id])
  70. return schedule!
  71. Element function get_possible_bindings(host_model : Element, schedule_model : Element, current_element : String, map : Element):
  72. Element options
  73. String src_label
  74. String dst_label
  75. String typename
  76. String original_typename
  77. Boolean guaranteed_instance
  78. options = set_create()
  79. typename = read_type(schedule_model, current_element)
  80. original_typename = string_substr(typename, 4, string_len(typename))
  81. guaranteed_instance = False
  82. // Is a node, so find whether or not there are some connections that are already resolved
  83. Element ic
  84. Element oc
  85. String poll
  86. String value
  87. oc = allOutgoingAssociationInstances(schedule_model, current_element, "PreElement")
  88. while (bool_and(set_len(oc) > 0, set_len(options) < 2)):
  89. poll = set_pop(oc)
  90. if (dict_in(map, read_attribute(schedule_model, poll, "label"))):
  91. // This incoming link is already defined, so we just have one option: the destination of the link we matched
  92. value = readAssociationSource(host_model, map[read_attribute(schedule_model, poll, "label")])
  93. if (bool_not(set_in(options, value))):
  94. set_add(options, value)
  95. if (set_len(options) < 2):
  96. ic = allIncomingAssociationInstances(schedule_model, current_element, "PreElement")
  97. while (bool_and(set_len(ic) > 0, set_len(options) < 2)):
  98. poll = set_pop(ic)
  99. if (dict_in(map, read_attribute(schedule_model, poll, "label"))):
  100. // This incoming link is already defined, so we just have one option: the destination of the link we matched
  101. value = readAssociationDestination(host_model, map[read_attribute(schedule_model, poll, "label")])
  102. if (bool_not(set_in(options, value))):
  103. set_add(options, value)
  104. if (set_len(options) == 0):
  105. // Is a node and no connections, so we just pick all options
  106. options = allInstances(host_model, original_typename)
  107. guaranteed_instance = True
  108. elif (set_len(options) > 1):
  109. // Multiple "only" options, which will not work out: no options!
  110. return set_create()!
  111. if (is_edge(schedule_model["model"][current_element])):
  112. Boolean src_in
  113. Boolean dst_in
  114. // Is an edge, so check for already bound source/target
  115. src_label = read_attribute(schedule_model, readAssociationSource(schedule_model, current_element), "label")
  116. dst_label = read_attribute(schedule_model, readAssociationDestination(schedule_model, current_element), "label")
  117. src_in = set_in(dict_keys(map), src_label)
  118. dst_in = set_in(dict_keys(map), dst_label)
  119. guaranteed_instance = True
  120. if (bool_and(src_in, dst_in)):
  121. // Source and destination are bound
  122. if (set_len(options) > 0):
  123. options = set_overlap(options, allOutgoingAssociationInstances(host_model, map[src_label], original_typename))
  124. if (set_len(options) > 0):
  125. options = set_overlap(options, allIncomingAssociationInstances(host_model, map[dst_label], original_typename))
  126. elif (src_in):
  127. // Source is bound
  128. options = set_overlap(options, allOutgoingAssociationInstances(host_model, map[src_label], original_typename))
  129. elif (dst_in):
  130. // Destination is bound
  131. options = set_overlap(options, allIncomingAssociationInstances(host_model, map[dst_label], original_typename))
  132. else:
  133. // Neither is bound, so just get all of them
  134. options = options
  135. // Filter options further
  136. Element filtered_options
  137. String option
  138. filtered_options = set_create()
  139. Element bound
  140. bound = dict_values(map)
  141. while (set_len(options) > 0):
  142. option = set_pop(options)
  143. // Check for detecting same element twice
  144. if (bool_not(set_in(bound, option))):
  145. // Option is already present with another label, so skip this!
  146. if (dict_in(host_model["model"], option)):
  147. // Check if it conforms to the desired type
  148. if (bool_not(guaranteed_instance)):
  149. if (bool_not(is_nominal_instance(host_model, option, original_typename))):
  150. // Not an actual instance, so skip!
  151. continue!
  152. // Check for local (matching) constraints of element
  153. if (element_eq(read_attribute(schedule_model, current_element, "constraint"), read_root())):
  154. // No local constraints, so all is well
  155. set_add(filtered_options, option)
  156. else:
  157. // Check local constraints and add only if positive
  158. Element constraint_function
  159. Boolean result
  160. Element func
  161. constraint_function = read_attribute(schedule_model, current_element, "constraint")
  162. func = get_func_AL_model(import_node(constraint_function))
  163. result = func(host_model, option)
  164. if (result):
  165. set_add(filtered_options, option)
  166. else:
  167. log("ERROR in found option: not in model")
  168. Element attributes
  169. String attribute
  170. Element func
  171. Boolean result
  172. Element attributes_copy
  173. options = filtered_options
  174. filtered_options = set_create()
  175. // Check whether all attributes have a satisfied condition
  176. attributes_copy = dict_keys(getAttributeList(schedule_model, current_element))
  177. while (set_len(options) > 0):
  178. option = set_pop(options)
  179. attributes = set_copy(attributes_copy)
  180. result = True
  181. while (set_len(attributes) > 0):
  182. attribute = set_pop(attributes)
  183. if (bool_not(string_startswith(attribute, "constraint_"))):
  184. continue!
  185. value = read_attribute(schedule_model, current_element, attribute)
  186. // Attribute might be undefined, so skip if it is
  187. if (element_neq(value, read_root())):
  188. func = get_func_AL_model(import_node(value))
  189. result = func(read_attribute(host_model, option, string_substr(attribute, string_len("constraint_"), string_len(attribute) + 1)))
  190. else:
  191. result = True
  192. if (bool_not(result)):
  193. break!
  194. // Check value of last result, which will be True if all passed, or False otherwise
  195. if (result):
  196. set_add(filtered_options, option)
  197. options = filtered_options
  198. return options!
  199. Element function full_match(host_model : Element, schedule_model : Element, current : String, single_ok : Boolean):
  200. Element NACs
  201. Element NACs_backup
  202. String LHS
  203. String NAC
  204. Element mappings
  205. Element mapping
  206. Element result
  207. Element final_mappings
  208. Boolean allowed
  209. final_mappings = set_create()
  210. // First match the LHS part itself to get initial mappings
  211. LHS = set_pop(allAssociationDestinations(schedule_model, current, "LHSLink"))
  212. mappings = match(host_model, schedule_model, LHS, dict_create())
  213. // Got a list of all possible mappings, now filter based on NACs
  214. NACs_backup = allAssociationDestinations(schedule_model, current, "NACLink")
  215. // For each possible mapping, we check all NACs!
  216. while (set_len(mappings) > 0):
  217. mapping = set_pop(mappings)
  218. allowed = True
  219. NACs = set_copy(NACs_backup)
  220. while (set_len(NACs) > 0):
  221. NAC = set_pop(NACs)
  222. result = match(host_model, schedule_model, NAC, mapping)
  223. if (set_len(result) > 0):
  224. // NAC could be matched, and therefore is not allowed
  225. allowed = False
  226. break!
  227. if (allowed):
  228. set_add_node(final_mappings, mapping)
  229. if (single_ok):
  230. break!
  231. return final_mappings!
  232. Element function match(host_model : Element, schedule_model : Element, LHS : String, initial_mapping : Element):
  233. // Match the schedule_model to the host_model, returning all possible mappings from schedule_model elements to host_model elements
  234. // Make the schedule first
  235. Element schedule
  236. schedule = make_matching_schedule(schedule_model, LHS, dict_keys(initial_mapping))
  237. // Now follow the schedule, incrementally building all mappings
  238. Element mappings
  239. Element new_mappings
  240. Element new_map
  241. String current_element
  242. Element map
  243. String option
  244. Element options
  245. mappings = set_create()
  246. set_add_node(mappings, initial_mapping)
  247. while (list_len(schedule) > 0):
  248. current_element = list_pop(schedule, list_len(schedule) - 1)
  249. //log("Binding element with label " + cast_value(read_attribute(schedule_model, current_element, "label")))
  250. new_mappings = dict_create()
  251. while (set_len(mappings) > 0):
  252. map = set_pop(mappings)
  253. options = get_possible_bindings(host_model, schedule_model, current_element, map)
  254. while (set_len(options) > 0):
  255. option = set_pop(options)
  256. new_map = dict_copy(map)
  257. dict_add_fast(new_map, read_attribute(schedule_model, current_element, "label"), option)
  258. set_add_node(new_mappings, new_map)
  259. mappings = new_mappings
  260. //log("Remaining options: " + cast_value(set_len(mappings)))
  261. if (set_len(mappings) == 0):
  262. // Stop because we have no more options remaining!
  263. return set_create()!
  264. // Finished, so try the global constraint
  265. String constraint
  266. Element func
  267. Boolean result
  268. new_mappings = dict_create()
  269. constraint = read_attribute(schedule_model, LHS, "constraint")
  270. if (element_neq(constraint, read_root())):
  271. while (set_len(mappings) > 0):
  272. map = set_pop(mappings)
  273. func = get_func_AL_model(import_node(constraint))
  274. result = func(host_model, map)
  275. if (result):
  276. set_add_node(new_mappings, map)
  277. mappings = new_mappings
  278. return mappings!
  279. Void function rewrite(host_model : Element, schedule_model : Element, RHS : String, mapping : Element):
  280. // Rewrite the host model based on the mapping combined with the RHS
  281. Element LHS_labels
  282. Element RHS_labels
  283. Element RHS_elements
  284. Element remaining
  285. String elem
  286. String label
  287. Element labels_to_remove
  288. Element labels_to_add
  289. String typename
  290. String original_typename
  291. String src
  292. String dst
  293. Element new_mapping
  294. String new_name
  295. Element RHS_map
  296. String tmp
  297. String value
  298. String action
  299. Element original_RHS_labels
  300. String new_identifier
  301. Element func
  302. Element reverse
  303. reverse = make_reverse_dictionary(schedule_model["model"])
  304. LHS_labels = dict_keys(mapping)
  305. RHS_labels = set_create()
  306. RHS_map = dict_create()
  307. RHS_elements = allAssociationDestinations(schedule_model, RHS, "RHS_contains")
  308. while (set_len(RHS_elements) > 0):
  309. tmp = set_pop(RHS_elements)
  310. label = read_attribute(schedule_model, tmp, "label")
  311. set_add(RHS_labels, label)
  312. dict_add_fast(RHS_map, label, tmp)
  313. remaining = set_overlap(LHS_labels, RHS_labels)
  314. original_RHS_labels = set_copy(RHS_labels)
  315. while (set_len(remaining) > 0):
  316. elem = set_pop(remaining)
  317. set_remove(LHS_labels, elem)
  318. set_remove(RHS_labels, elem)
  319. labels_to_remove = LHS_labels
  320. labels_to_add = set_to_list(RHS_labels)
  321. new_mapping = dict_copy(mapping)
  322. while (list_len(labels_to_add) > 0):
  323. // Add the elements linked to these labels
  324. label = list_pop(labels_to_add, list_len(labels_to_add) - 1)
  325. // Check if we have any requirement for the ID
  326. if (element_eq(read_attribute(schedule_model, RHS_map[label], "__id__"), read_root())):
  327. new_identifier = ""
  328. else:
  329. func = get_func_AL_model(import_node(read_attribute(schedule_model, RHS_map[label], "__id__")))
  330. new_identifier = func(host_model, mapping)
  331. if (is_edge(schedule_model["model"][RHS_map[label]])):
  332. // Edge
  333. src = read_attribute(schedule_model, reverse[cast_id(read_edge_src(schedule_model["model"][RHS_map[label]]))], "label")
  334. dst = read_attribute(schedule_model, reverse[cast_id(read_edge_dst(schedule_model["model"][RHS_map[label]]))], "label")
  335. // First check whether both source and destination are already created
  336. if (bool_and(dict_in(new_mapping, src), dict_in(new_mapping, dst))):
  337. // Both are present, so we can make the link
  338. typename = read_type(schedule_model, RHS_map[label])
  339. original_typename = string_substr(typename, 5, string_len(typename))
  340. new_name = instantiate_link(host_model, original_typename, new_identifier, new_mapping[src], new_mapping[dst])
  341. dict_add_fast(new_mapping, label, new_name)
  342. else:
  343. // Delay this a bit, until all are bound
  344. list_insert(labels_to_add, label, 0)
  345. else:
  346. // Node
  347. // Create the node and add it
  348. typename = read_type(schedule_model, RHS_map[label])
  349. original_typename = string_substr(typename, 5, string_len(typename))
  350. new_name = instantiate_node(host_model, original_typename, new_identifier)
  351. dict_add_fast(new_mapping, label, new_name)
  352. Element attributes
  353. String attribute
  354. Element result
  355. while (set_len(original_RHS_labels) > 0):
  356. // Perform actions
  357. label = set_pop(original_RHS_labels)
  358. // Do all attribute actions that are defined
  359. attributes = dict_keys(getAttributeList(schedule_model, RHS_map[label]))
  360. while (set_len(attributes) > 0):
  361. attribute = set_pop(attributes)
  362. if (bool_not(string_startswith(attribute, "value_"))):
  363. continue!
  364. value = read_attribute(schedule_model, RHS_map[label], attribute)
  365. if (element_neq(value, read_root())):
  366. func = get_func_AL_model(import_node(value))
  367. result = func(host_model, new_mapping[label], mapping)
  368. if (element_eq(result, read_root())):
  369. unset_attribute(host_model, new_mapping[label], string_substr(attribute, string_len("value_"), string_len(attribute) + 1))
  370. elif (has_value(result)):
  371. // New value defined, so assign!
  372. instantiate_attribute(host_model, new_mapping[label], string_substr(attribute, string_len("value_"), string_len(attribute) + 1), result)
  373. elif (is_error(result)):
  374. log("Error in evaluation of attribute " + attribute)
  375. log("On element with label " + label)
  376. else:
  377. // Try to interpret as code
  378. instantiate_attribute_code(host_model, new_mapping[label], string_substr(attribute, string_len("value_"), string_len(attribute) + 1), result)
  379. // Do the global action of each element
  380. action = read_attribute(schedule_model, RHS_map[label], "action")
  381. if (element_neq(action, read_root())):
  382. Element func
  383. func = get_func_AL_model(import_node(action))
  384. func(host_model, new_mapping[label], mapping)
  385. while (set_len(labels_to_remove) > 0):
  386. // Remove the elements linked to these labels
  387. label = set_pop(labels_to_remove)
  388. model_delete_element(host_model, mapping[label])
  389. dict_delete(new_mapping, label)
  390. // Execute global action (whatever it may be)
  391. action = read_attribute(schedule_model, RHS, "action")
  392. if (element_neq(action, read_root())):
  393. Element func
  394. func = get_func_AL_model(import_node(action))
  395. func(host_model, new_mapping)
  396. return!
  397. Element function transform(host_model : Element, schedule_model : Element):
  398. // Find initial model
  399. Element all_composites
  400. String composite
  401. String current
  402. Element merged
  403. Element original_mm
  404. // Now start transforming for real
  405. all_composites = allInstances(schedule_model, "Composite")
  406. if (set_len(all_composites) == 1):
  407. // Only one, so it is easy
  408. current = set_pop(all_composites)
  409. else:
  410. // Filter out those that are themselves contained
  411. while (set_len(all_composites) > 0):
  412. composite = set_pop(all_composites)
  413. if (set_len(allIncomingAssociationInstances(schedule_model, composite, "Contains")) == 0):
  414. // Isn't contained in any, so this is the root model!
  415. current = composite
  416. if (transform_composite(host_model, schedule_model, current)):
  417. // Success, so return True if it is in-place, or the new model if it is out-place
  418. return True!
  419. else:
  420. return False!
  421. Boolean function transform_composite(host_model : Element, schedule_model : Element, composite : String):
  422. String current
  423. String typename
  424. Boolean result
  425. current = set_pop(allAssociationDestinations(schedule_model, composite, "Initial"))
  426. while (is_nominal_instance(schedule_model, current, "Rule")):
  427. // Still a rule that we must execute
  428. typename = read_type(schedule_model, current)
  429. if (typename == "Atomic"):
  430. result = transform_atomic(host_model, schedule_model, current)
  431. elif (typename == "Query"):
  432. result = transform_query(host_model, schedule_model, current)
  433. elif (typename == "Composite"):
  434. result = transform_composite(host_model, schedule_model, current)
  435. elif (typename == "ForAll"):
  436. result = transform_forall(host_model, schedule_model, current)
  437. Element result_set
  438. if (result):
  439. result_set = allAssociationDestinations(schedule_model, current, "OnSuccess")
  440. else:
  441. result_set = allAssociationDestinations(schedule_model, current, "OnFailure")
  442. if (set_len(result_set) == 0):
  443. log("ERROR: no next rule found for execution result " + cast_string(result))
  444. elif (set_len(result_set) > 1):
  445. log("WARNING: multiple next rules found for execution result " + cast_string(result))
  446. log("Picking one at random...")
  447. current = set_pop(result_set)
  448. // No longer a rule, so it is either success or failure
  449. if (is_nominal_instance(schedule_model, current, "Success")):
  450. return True!
  451. else:
  452. return False!
  453. Boolean function transform_atomic(host_model : Element, schedule_model : Element, current : String):
  454. // Execute the atomic transformation
  455. Element mappings
  456. Element mapping
  457. mappings = full_match(host_model, schedule_model, current, True)
  458. //log("Executing rule: " + current)
  459. if (set_len(mappings) > 0):
  460. // Pick one!
  461. mapping = random_choice(set_to_list(mappings))
  462. String RHS
  463. RHS = set_pop(allAssociationDestinations(schedule_model, current, "RHSLink"))
  464. rewrite(host_model, schedule_model, RHS, mapping)
  465. //log("Rewrite OK")
  466. return True!
  467. else:
  468. return False!
  469. Boolean function transform_forall(host_model : Element, schedule_model : Element, current : String):
  470. // Execute the atomic transformation
  471. Element mappings
  472. String RHS
  473. Element mapping
  474. Boolean result
  475. //log("Executing rule: " + current)
  476. mappings = full_match(host_model, schedule_model, current, False)
  477. if (set_len(mappings) > 0):
  478. result = True
  479. else:
  480. result = False
  481. //log("Matches in forall: " + cast_string(set_len(mappings)))
  482. while (set_len(mappings) > 0):
  483. mapping = set_pop(mappings)
  484. RHS = set_pop(allAssociationDestinations(schedule_model, current, "RHSLink"))
  485. rewrite(host_model, schedule_model, RHS, mapping)
  486. //log("Rewrite OK")
  487. return result!
  488. Boolean function transform_query(host_model : Element, schedule_model : Element, current : String):
  489. // Execute the transformation
  490. Element mappings
  491. Element mapping
  492. mappings = full_match(host_model, schedule_model, current, True)
  493. if (set_len(mappings) > 0):
  494. return True!
  495. else:
  496. return False!