modelverse/bootstrap/transform.alc

include "primitives.alh"
include "object_operations.alh"
include "modelling.alh"
include "random.alh"
include "conformance_scd.alh"
include "model_management.alh"
include "library.alh"

Element function make_matching_schedule(schedule_model : Element, LHS : String, ignore : Element):
	Element schedule
	Element workset
	Element all_elements
	Element full_all_elements
	Integer required_size
	String new_element
	Integer counter
	String next
	Element tmp

	// Initialize
	schedule = create_node()
	workset = create_node()
	all_elements = allAssociationDestinations(schedule_model, LHS, "LHS_contains")
	full_all_elements = set_copy(all_elements)
	required_size = read_nr_out(all_elements)

	// Need to keep adding to the schedule
	while (read_nr_out(schedule) < required_size):

		// workset is empty, but we still need to add to the list
		// Therefore, we pick a random, unbound node, and add it to the workset
		new_element = set_pop(all_elements)
		while (bool_or(set_in(schedule, new_element), is_edge(schedule_model["model"][new_element]))):
			// Element is not usable, so pick another one
			new_element = set_pop(all_elements)
		set_add(workset, new_element)

		// Handle the workset
		while (read_nr_out(workset) > 0):
			// Still elements in the workset, so pop from these first
			next = set_pop(workset)

			// Check if element might not be already used somewhere
			if (bool_not(set_in(schedule, next))):
				if (set_in(full_all_elements, next)):
					if (bool_not(set_in(ignore, read_attribute(schedule_model, next, "label")))):
						list_insert(schedule, next, 0)
					else:
						required_size = required_size - 1
						continue!

					// If it is an edge, we should also add the target and source
					if (is_edge(schedule_model["model"][next])):
						// Add the target/source to the schedule
						set_add(workset, reverseKeyLookup(schedule_model["model"], read_edge_src(schedule_model["model"][next])))
						set_add(workset, reverseKeyLookup(schedule_model["model"], read_edge_dst(schedule_model["model"][next])))

					// Also add all outgoing links
					counter = read_nr_out(schedule_model["model"][next])
					while (counter > 0):
						counter = counter - 1
						if (set_in_node(schedule_model["model"], read_out(schedule_model["model"][next], counter))):
							set_add(workset, reverseKeyLookup(schedule_model["model"], read_out(schedule_model["model"][next], counter)))

					// And incoming links
					counter = read_nr_in(schedule_model["model"][next])
					while (counter > 0):
						counter = counter - 1
						if (set_in_node(schedule_model["model"], read_in(schedule_model["model"][next], counter))):
							set_add(workset, reverseKeyLookup(schedule_model["model"], read_in(schedule_model["model"][next], counter)))

	return schedule!

Element function get_possible_bindings(host_model : Element, schedule_model : Element, current_element : String, map : Element):
	Element options
	String src_label
	String dst_label
	String typename
	String original_typename

	options = create_node()

	typename = read_type(schedule_model, current_element)
	original_typename = string_substr(typename, 4, string_len(typename))
	
	if (is_edge(schedule_model["model"][current_element])):
		// Is an edge, so check for already bound source/target
		src_label = read_attribute(schedule_model, reverseKeyLookup(schedule_model["model"], read_edge_src(schedule_model["model"][current_element])), "label")
		dst_label = read_attribute(schedule_model, reverseKeyLookup(schedule_model["model"], read_edge_dst(schedule_model["model"][current_element])), "label")

		if (bool_and(set_in(dict_keys(map), src_label), set_in(dict_keys(map), dst_label))):
			// Source and destination are bound
			options = allOutgoingAssociationInstances(host_model, map[src_label], original_typename)
			options = set_overlap(options, allIncomingAssociationInstances(host_model, map[dst_label], original_typename))

		elif (set_in(dict_keys(map), src_label)):
			// Source is bound
			options = allOutgoingAssociationInstances(host_model, map[src_label], original_typename)

		elif (set_in(dict_keys(map), dst_label)):
			// Destination is bound
			options = allIncomingAssociationInstances(host_model, map[dst_label], original_typename)

		else:
			// Neither is bound, so just get all of them
			return allInstances(host_model, original_typename)!
	else:
		// Is a node, so find whether or not there are some connections that are already resolved
		Element ic
		Element oc
		String poll

		// TODO optimize: do outgoing first, and only get incoming when not yet failed for incoming (incoming much slower!)

		ic = allIncomingAssociationInstances(schedule_model, current_element, "PreElement")
		oc = allOutgoingAssociationInstances(schedule_model, current_element, "PreElement")

		String value
		while (bool_and(read_nr_out(ic) > 0, read_nr_out(options) < 2)):
			poll = set_pop(ic)
			if (dict_in(map, read_attribute(schedule_model, poll, "label"))):
				// This incoming link is already defined, so we just have one option: the destination of the link we matched
				value = readAssociationDestination(host_model, map[read_attribute(schedule_model, poll, "label")])
				if (bool_not(set_in(options, value))):
					set_add(options, value)
			
		while (bool_and(read_nr_out(oc) > 0, read_nr_out(options) < 2)):
			poll = set_pop(oc)
			if (dict_in(map, read_attribute(schedule_model, poll, "label"))):
				// This incoming link is already defined, so we just have one option: the destination of the link we matched
				value = readAssociationSource(host_model, map[read_attribute(schedule_model, poll, "label")])
				if (bool_not(set_in(options, value))):
					set_add(options, value)

		if (read_nr_out(options) == 0):
			// Is a node and no connections, so we just pick all options
			options = allInstances(host_model, original_typename)
		elif (read_nr_out(options) > 1):
			// Multiple "only" options, which will not work out: no options!
			return create_node()!

	// Filter options further
	Element filtered_options
	String option

	filtered_options = create_node()
	while (read_nr_out(options) > 0):
		option = set_pop(options)

		// Check for detecting same element twice
		if (bool_not(set_in(map, option))):
			// Option is already present with another label, so skip this!

			// Check if it conforms to the desired type
			if (is_nominal_instance(host_model, option, original_typename)):
				// Check for local constraints of element
				if (element_eq(read_attribute(schedule_model, current_element, "constraint"), read_root())):
					// No local constraints, so all is well
					set_add(filtered_options, option)
				else:
					// Check local constraints and add only if positive
					Element constraint_function
					Boolean result
					Element func

					constraint_function = read_attribute(schedule_model, current_element, "constraint")
					func = get_func_AL_model(import_node(constraint_function))
					result = func(host_model, option)

					if (result):
						set_add(filtered_options, option)

	Element attributes
	String attribute
	Element value
	Element func
	Boolean result
	Element attributes_copy

	options = filtered_options
	filtered_options = create_node()

	// Check whether all attributes have a satisfied condition
	attributes_copy = dict_keys(getAttributeList(schedule_model, current_element))

	while (read_nr_out(options) > 0):
		option = set_pop(options)
		attributes = set_copy(attributes_copy)

		result = True
		while (read_nr_out(attributes) > 0):
			attribute = set_pop(attributes)
			if (bool_not(string_startswith(attribute, "constraint_"))):
				continue!

			value = read_attribute(schedule_model, current_element, attribute)
			// Attribute might be undefined, so skip if it is
			if (element_neq(value, read_root())):
				func = get_func_AL_model(import_node(value))
				result = func(read_attribute(host_model, option, string_substr(attribute, string_len("constraint_"), string_len(attribute) + 1)))
			else:
				result = True

			if (bool_not(result)):
				break!

		// Check value of last result, which will be True if all passed, or False otherwise
		if (result):
			set_add(filtered_options, option)

	options = filtered_options
	return options!

Element function full_match(host_model : Element, schedule_model : Element, current : String, single_ok : Boolean):
	Element NACs
	String LHS
	String NAC
	Element mappings
	Element mapping
	Integer i
	Element result
	Element final_mappings
	Boolean allowed

	final_mappings = create_node()

	// First match the LHS part itself to get initial mappings
	LHS = set_pop(allAssociationDestinations(schedule_model, current, "LHSLink"))
	mappings = match(host_model, schedule_model, LHS, create_node())

	// Got a list of all possible mappings, now filter based on NACs
	NACs = allAssociationDestinations(schedule_model, current, "NACLink")

	// For each possible mapping, we check all NACs!
	while (read_nr_out(mappings) > 0):
		mapping = set_pop(mappings)
		i = 0
		allowed = True
		while (i < read_nr_out(NACs)):
			NAC = read_edge_dst(read_out(NACs, i))
			result = match(host_model, schedule_model, NAC, mapping)
			if (read_nr_out(result) > 0):
				// NAC could be matched, and therefore is not allowed
				allowed = False
				break!
			i = i + 1
		
		if (allowed):
			set_add(final_mappings, mapping)

			if (single_ok):
				break!

	return final_mappings!

Element function match(host_model : Element, schedule_model : Element, LHS : String, initial_mapping : Element):
	// Match the schedule_model to the host_model, returning all possible mappings from schedule_model elements to host_model elements

	// Make the schedule first
	Element schedule
	schedule = make_matching_schedule(schedule_model, LHS, dict_keys(initial_mapping))

	// Now follow the schedule, incrementally building all mappings
	Element mappings
	Element new_mappings
	Element new_map
	String current_element
	Element map
	String option
	Element options

	mappings = create_node()
	set_add(mappings, initial_mapping)
	while (read_nr_out(schedule) > 0):
		current_element = list_pop(schedule, read_nr_out(schedule) - 1)
		log("Binding element with label " + cast_v2s(read_attribute(schedule_model, current_element, "label")))
		new_mappings = create_node()

		while (read_nr_out(mappings) > 0):
			map = set_pop(mappings)
			options = get_possible_bindings(host_model, schedule_model, current_element, map)

			while (read_nr_out(options) > 0):
				option = set_pop(options)
				new_map = dict_copy(map)
				dict_add_fast(new_map, read_attribute(schedule_model, current_element, "label"), option)
				set_add(new_mappings, new_map)

		mappings = new_mappings
		log("Remaining options: " + cast_v2s(read_nr_out(mappings)))

		if (read_nr_out(mappings) == 0):
			// Stop because we have no more options remaining!
			return create_node()!

	// Finished, so try the global constraint
	String constraint
	Element func
	Boolean result

	new_mappings = create_node()
	constraint = read_attribute(schedule_model, LHS, "constraint")
	if (element_neq(constraint, read_root())):
		while (read_nr_out(mappings) > 0):
			map = set_pop(mappings)
			func = get_func_AL_model(import_node(constraint))
			result = func(host_model, map)

			if (result):
				set_add(new_mappings, map)
		mappings = new_mappings

	return mappings!

Void function rewrite(host_model : Element, schedule_model : Element, RHS : String, mapping : Element):
	// Rewrite the host model based on the mapping combined with the RHS
	Element LHS_labels
	Element RHS_labels
	Element RHS_elements
	Element remaining
	String elem
	String label
	Element labels_to_remove
	Element labels_to_add
	String typename
	String original_typename
	String src
	String dst
	Element new_mapping
	String new_name
	Element RHS_map
	String tmp
	Element value
	Element action
	Element original_RHS_labels

	LHS_labels = dict_keys(mapping)
	RHS_labels = create_node()
	RHS_map = create_node()

	RHS_elements = allAssociationDestinations(schedule_model, RHS, "RHS_contains")
	while (read_nr_out(RHS_elements) > 0):
		tmp = set_pop(RHS_elements)
		label = read_attribute(schedule_model, tmp, "label")
		set_add(RHS_labels, label)
		dict_add_fast(RHS_map, label, tmp)

	remaining = set_overlap(LHS_labels, RHS_labels)
	original_RHS_labels = set_copy(RHS_labels)
	while (read_nr_out(remaining) > 0):
		elem = set_pop(remaining)
		set_remove(LHS_labels, elem)
		set_remove(RHS_labels, elem)

	labels_to_remove = LHS_labels
	labels_to_add = set_to_list(RHS_labels)

	new_mapping = dict_copy(mapping)

	while (read_nr_out(labels_to_add) > 0):
		// Add the elements linked to these labels
		label = list_pop(labels_to_add, read_nr_out(labels_to_add) - 1)
		if (is_edge(schedule_model["model"][RHS_map[label]])):
			// Edge
			src = read_attribute(schedule_model, reverseKeyLookup(schedule_model["model"], read_edge_src(schedule_model["model"][RHS_map[label]])), "label")
			dst = read_attribute(schedule_model, reverseKeyLookup(schedule_model["model"], read_edge_dst(schedule_model["model"][RHS_map[label]])), "label")
			// First check whether both source and destination are already created
			if (bool_and(dict_in(new_mapping, src), dict_in(new_mapping, dst))):
				// Both are present, so we can make the link
				typename = read_type(schedule_model, RHS_map[label])
				original_typename = string_substr(typename, 5, string_len(typename))
				new_name = instantiate_link(host_model, original_typename, "", new_mapping[src], new_mapping[dst])
				dict_add_fast(new_mapping, label, new_name)
			else:
				// Delay this a bit, until all are bound
				list_insert(labels_to_add, label, 0)
		else:
			// Node
			// Create the node and add it
			typename = read_type(schedule_model, RHS_map[label])
			original_typename = string_substr(typename, 5, string_len(typename))
			new_name = instantiate_node(host_model, original_typename, "")
			dict_add_fast(new_mapping, label, new_name)

	Element attributes
	String attribute
	Element result
	Element func

	while (read_nr_out(original_RHS_labels) > 0):
		// Perform actions
		label = set_pop(original_RHS_labels)

		// Do all attribute actions that are defined
		attributes = dict_keys(getAttributeList(schedule_model, RHS_map[label]))
		while (read_nr_out(attributes) > 0):
			attribute = set_pop(attributes)
			if (bool_not(string_startswith(attribute, "value_"))):
				continue!

			value = read_attribute(schedule_model, RHS_map[label], attribute)
			if (element_neq(value, read_root())):
				func = get_func_AL_model(import_node(value))
				result = func(host_model, new_mapping[label], mapping)

				if (has_value(result)):
					// New value defined, so assign!
					instantiate_attribute(host_model, new_mapping[label], string_substr(attribute, string_len("value_"), string_len(attribute) + 1), result)
				else:
					// Non-value return means to destroy the attribute!
					unset_attribute(host_model, new_mapping[label], string_substr(attribute, string_len("value_"), string_len(attribute) + 1))

		// Do the global action of each element
		action = read_attribute(schedule_model, RHS_map[label], "action")
		if (element_neq(action, read_root())):
			Element func
			func = get_func_AL_model(import_node(action))
			func(host_model, new_mapping[label], mapping)

	while (read_nr_out(labels_to_remove) > 0):
		// Remove the elements linked to these labels
		label = set_pop(labels_to_remove)
		model_delete_element(host_model, mapping[label])
		dict_delete(new_mapping, label)

	// Execute global action (whatever it may be)
	action = read_attribute(schedule_model, RHS, "action")
	if (element_neq(action, read_root())):
		Element func
		func = get_func_AL_model(import_node(action))
		func(host_model, new_mapping)

	return!

Element function transform(host_model : Element, schedule_model : Element):
	// Find initial model
	Element all_composites
	String composite
	String current
	Element merged
	Element original_mm

	// Now start transforming for real
	all_composites = allInstances(schedule_model, "Composite")
	if (read_nr_out(all_composites) == 1):
		// Only one, so it is easy
		current = set_pop(all_composites)
	else:
		// Filter out those that are themselves contained
		while (read_nr_out(all_composites) > 0):
			composite = set_pop(all_composites)
			if (read_nr_out(allIncomingAssociationInstances(schedule_model, composite, "Contains")) == 0):
				// Isn't contained in any, so this is the root model!
				current = composite

	if (transform_composite(host_model, schedule_model, current)):
		// Success, so return True if it is in-place, or the new model if it is out-place
		return True!
	else:
		return False!

Boolean function transform_composite(host_model : Element, schedule_model : Element, composite : String):
	String current
	String typename
	Boolean result

	current = set_pop(allAssociationDestinations(schedule_model, composite, "Initial"))
	while (is_nominal_instance(schedule_model, current, "Rule")):
		log("Executing " + current)
		// Still a rule that we must execute
		typename = read_type(schedule_model, current)
		if (typename == "Atomic"):
			result = transform_atomic(host_model, schedule_model, current)
		elif (typename == "Query"):
			result = transform_query(host_model, schedule_model, current)
		elif (typename == "Composite"):
			result = transform_composite(host_model, schedule_model, current)
		elif (typename == "ForAll"):
			result = transform_forall(host_model, schedule_model, current)

		if (result):
			current = set_pop(allAssociationDestinations(schedule_model, current, "OnSuccess"))
		else:
			current = set_pop(allAssociationDestinations(schedule_model, current, "OnFailure"))

	// No longer a rule, so it is either success or failure
	if (is_nominal_instance(schedule_model, current, "Success")):
		return True!
	else:
		return False!

Boolean function transform_atomic(host_model : Element, schedule_model : Element, current : String):
	// Execute the atomic transformation
	Element mappings
	Element mapping
	mappings = full_match(host_model, schedule_model, current, True)

	if (read_nr_out(mappings) > 0):
		// Pick one!
		mapping = random_choice(set_to_list(mappings))
		String RHS
		RHS = set_pop(allAssociationDestinations(schedule_model, current, "RHSLink"))
		rewrite(host_model, schedule_model, RHS, mapping)
		return True!
	else:
		return False!

Boolean function transform_forall(host_model : Element, schedule_model : Element, current : String):
	// Execute the atomic transformation
	Element mappings
	String RHS
	Element mapping
	Boolean result

	mappings = full_match(host_model, schedule_model, current, False)

	if (read_nr_out(mappings) > 0):
		result = True
	else:
		result = False

	log("Matches in forall: " + cast_v2s(read_nr_out(mappings)))
	while (read_nr_out(mappings) > 0):
		mapping = set_pop(mappings)
		// TODO check if there are actually no deletions happening in the meantime of other matched elements...
		RHS = set_pop(allAssociationDestinations(schedule_model, current, "RHSLink"))
		rewrite(host_model, schedule_model, RHS, mapping)

	return result!

Boolean function transform_query(host_model : Element, schedule_model : Element, current : String):
	// Execute the transformation
	Element mappings
	Element mapping
	mappings = full_match(host_model, schedule_model, current, True)

	if (read_nr_out(mappings) > 0):
		return True!
	else:
		return False!