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"

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_append(schedule, next)
						required_size = required_size - 1

					// 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)))

	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))
	
	log("Getting possible bindings for " + current_element)
	log("    type: " + typename)

	if (is_edge(schedule_model["model"][current_element])):
		log("    is_edge")
		// 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
			log("    SD bound")
			options = allOutgoingAssociationInstances(host_model, map[src_label], original_typename)
			log("    Outgoing associations instances: " + set_to_string(options))
			log("    Incoming associations instances: " + set_to_string(allIncomingAssociationInstances(host_model, map[dst_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
			log("    S bound")
			options = allOutgoingAssociationInstances(host_model, map[src_label], original_typename)

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

		else:
			// Neither is bound, so just get all of them
			log("ERROR: unbound source/target for association!")
			//TODO should actually return all
			return create_node()!
	else:
		log("    is_node")
		// Is a node, so find whether or not there are some connections that are already resolved
		Element ic
		Element oc
		String poll

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

		while (bool_and(read_nr_out(ic) > 0, read_nr_out(options) == 0)):
			poll = set_pop(ic)
			log("    poll I " + poll)
			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
				set_add(options, readAssociationDestination(host_model, map[read_attribute(schedule_model, poll, "label")]))
			
		while (bool_and(read_nr_out(oc) > 0, read_nr_out(options) == 0)):
			poll = set_pop(oc)
			log("    poll O " + poll)
			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
				set_add(options, readAssociationSource(host_model, map[read_attribute(schedule_model, poll, "label")]))

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

	// Filter options further
	Element filtered_options
	String option

	log("    Got options: " + set_to_string(options))

	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 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(constraint_function)
				result = func(host_model, option)

				log("Execute constraint on " + dict_to_string(option))
				log("Result: " + cast_e2s(result))

				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()
	log("Checking options: " + set_to_string(options))

	// Check whether all attributes have a satisfied condition
	attributes_copy = dict_keys(getAttributeList(schedule_model, current_element))
	log("Defined attributes: " + set_to_string(attributes_copy))

	while (read_nr_out(options) > 0):
		option = set_pop(options)
		attributes = set_copy(attributes_copy)
		log(" opt: " + option)

		while (read_nr_out(attributes) > 0):
			attribute = set_pop(attributes)
			log("Check attribute: " + attribute)

			value = read_attribute(schedule_model, current_element, attribute)
			func = get_func_AL_model(value)
			log("EXEC")
			result = func(host_model, option, attribute)
			log("Got result of constraint eval: " + cast_v2s(result))

			if (result):
				log("Adding")
				set_add(filtered_options, option)
			else:
				log("Dropping")

	options = filtered_options
	return options!

Element function full_match(host_model : Element, schedule_model : Element, current : String):
	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)

	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 (bool_and(read_nr_out(schedule) > 0, read_nr_out(mappings) > 0)):
		current_element = list_pop(schedule, 0)
		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(new_map, read_attribute(schedule_model, current_element, "label"), option)
				set_add(new_mappings, new_map)

		mappings = new_mappings

	// 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(constraint)
			result = func(host_model, map)

			log("Execute global constraint on " + dict_to_string(map))
			log("Result: " + cast_e2s(result))

			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 value_function
	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(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, 0)
		if (element_neq(read_attribute(schedule_model, RHS_map[label], "value"), read_root())):
			// There is a value associated with this node
			value_function = read_attribute(schedule_model, RHS_map[label], "value")
			value = value_function(host_model, mapping)

			typename = read_type(schedule_model, RHS_map[label])
			original_typename = string_substr(typename, 5, string_len(typename))
			new_name = instantiate_value(host_model, original_typename, "", value)
			dict_add(new_mapping, label, new_name)

		elif (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(new_mapping, label, new_name)
			else:
				// Delay this a bit, until all are bound
				list_append(labels_to_add, label)
		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(new_mapping, label, new_name)

	while (read_nr_out(original_RHS_labels) > 0):
		label = set_pop(original_RHS_labels)
		action = read_attribute(schedule_model, RHS_map[label], "action")
		if (element_neq(action, read_root())):
			Element func
			func = get_func_AL_model(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(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")):
		// Still a rule that we must execute
		typename = read_type(schedule_model, current)
		log("RULE: " + 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)

	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)

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

	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...
		log("Execute RHS for binding: " + dict_to_string(mapping))
		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)

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