include "primitives.alh"
include "object_operations.alh"
include "modelling.alh"

Element function make_matching_schedule(LHS_model : Element):
	Element schedule
	Element workset
	Element all_elements
	Element full_all_elements
	Integer required_size
	String new_element
	Integer counter
	String next

	// Initialize
	schedule = create_node()
	workset = create_node()
	all_elements = allInstances(LHS_model, "Pre_Element")
	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(LHS_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)):
					list_append(schedule, next)

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

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

	return schedule!

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

	options = create_node()

	typename = reverseKeyLookup(LHS_model["metamodel"]["model"], dict_read_node(LHS_model["type_mapping"], LHS_model["model"][current_element]))
	original_typename = string_substr(typename, 4, string_len(typename))

	if (is_edge(LHS_model["model"][current_element])):
		// Is an edge, so check for already bound source/target
		src_label = read_attribute(LHS_model, reverseKeyLookup(LHS_model["model"], read_edge_src(LHS_model["model"][current_element])), "label")
		dst_label = read_attribute(LHS_model, reverseKeyLookup(LHS_model["model"], read_edge_dst(LHS_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
			log("ERROR: unbound source/target for association!")
			return create_node()!
	else:
		// Is a node, so check for already bound incoming/outgoing
		options = allInstances(host_model, original_typename)

	// 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 for local constraints of element
			if (element_eq(read_attribute(LHS_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
				log("Finding constraint")
				constraint_function = read_attribute(LHS_model, current_element, "constraint")
				Boolean result
				log("Executing constraint")
				result = constraint_function(host_model, option)
				log("Executed constraint")
				if (result):
					set_add(filtered_options, option)

	return filtered_options!

Element function match(host_model : Element, LHS_model : Element):
	// Match the LHS_model to the host_model, returning all possible mappings from LHS_model elements to host_model elements

	// Make the schedule first
	Element schedule
	schedule = make_matching_schedule(LHS_model)

	// 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, create_node())
	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, LHS_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(LHS_model, current_element, "label"), option)
				set_add(new_mappings, new_map)

		mappings = new_mappings

	return mappings!

Void function rewrite(host_model : Element, RHS_model : Element, 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

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

	RHS_elements = allInstances(RHS_model, "Post_Element")
	while (read_nr_out(RHS_elements) > 0):
		tmp = set_pop(RHS_elements)
		label = read_attribute(RHS_model, tmp, "label")
		set_add(RHS_labels, label)
		dict_add(RHS_map, label, tmp)

	remaining = set_overlap(LHS_labels, 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_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)

	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(RHS_model, RHS_map[label], "value"), read_root())):
			// There is an action associated with this node
			value_function = read_attribute(RHS_model, RHS_map[label], "value")
			value = value_function(host_model, RHS_model)

			typename = reverseKeyLookup(RHS_model["metamodel"]["model"], dict_read_node(RHS_model["type_mapping"], RHS_model["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(RHS_model["model"][RHS_map[label]])):
			// Edge
			src = read_attribute(RHS_model, reverseKeyLookup(RHS_model["model"], read_edge_src(RHS_model["model"][RHS_map[label]])), "label")
			dst = read_attribute(RHS_model, reverseKeyLookup(RHS_model["model"], read_edge_dst(RHS_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 = reverseKeyLookup(RHS_model["metamodel"]["model"], dict_read_node(RHS_model["type_mapping"], RHS_model["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 = reverseKeyLookup(RHS_model["metamodel"]["model"], dict_read_node(RHS_model["type_mapping"], RHS_model["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)

	return!

Void function transform(host_model : Element, LHS_model : Element, RHS_model : Element):
	Element mapping
	Element mappings

	// Get all possible mappings
	mappings = match(host_model, LHS_model)
	log("Found total mappings: " + cast_v2s(read_nr_out(mappings)))

	// Select one such mapping and rewrite it
	if (read_nr_out(mappings) > 0):
		// Mapping found, so can rewrite it
		mapping = set_pop(mappings)
		log("Found example mapping " + dict_to_string(mapping))
		rewrite(host_model, RHS_model, mapping)
	else:
		output("No mapping found!")

	return!