# A virtual machine based on the naive_interpreter
class VirtualMachine super NaiveInterpreter

	# Perfect hashing and perfect numbering
	var ph: Perfecthashing = new Perfecthashing

	# Handles memory allocated in C
	var memory_manager: MemoryManager = new MemoryManager

	# The unique instance of the `MInit` value
	var initialization_value: Instance is noinit

	init
	do
		var init_type = new MInitType(mainmodule.model)
		initialization_value = new MutableInstance(init_type)
		super
	end

	# Runtime subtyping test
	redef fun is_subtype(sub, sup: MType): Bool
	do
		if sub == sup then return true

		var anchor = self.frame.arguments.first.mtype.as(MClassType)

		# `sub` or `sup` are formal or virtual types, resolve them to concrete types
		if sub isa MFormalType then
			sub = sub.resolve_for(anchor.mclass.mclass_type, anchor, mainmodule, false)
		end
		if sup isa MFormalType then
			sup = sup.resolve_for(anchor.mclass.mclass_type, anchor, mainmodule, false)
		end

		var sup_accept_null = false
		if sup isa MNullableType then
			sup_accept_null = true
			sup = sup.mtype
		else if sup isa MNullType then
			sup_accept_null = true
		end

		# Can `sub` provides null or not?
		# Thus we can match with `sup_accept_null`
		# Also discard the nullable marker if it exists
		if sub isa MNullableType then
			if not sup_accept_null then return false
			sub = sub.mtype
		else if sub isa MNullType then
			return sup_accept_null
		end
		# Now the case of direct null and nullable is over

		if sub isa MFormalType then
			sub = sub.anchor_to(mainmodule, anchor)
			# Manage the second layer of null/nullable
			if sub isa MNullableType then
				if not sup_accept_null then return false
				sub = sub.mtype
			else if sub isa MNullType then
				return sup_accept_null
			end
		end

		assert sub isa MClassType

		# `sup` accepts only null
		if sup isa MNullType then return false

		assert sup isa MClassType

		# and `sup` can be discovered inside a Generic type during the subtyping test
		if not sub.mclass.loaded then load_class(sub.mclass)

		# If the target of the test is not-loaded yet, the subtyping-test will be false
		if not sup.mclass.abstract_loaded then return false

		# For now, always use perfect hashing for subtyping test
		var super_id = sup.mclass.vtable.id
		var mask = sub.mclass.vtable.mask

		var res = inter_is_subtype_ph(super_id, mask, sub.mclass.vtable.internal_vtable)
		if not res then return false
		# sub and sup can be generic types, each argument of generics has to be tested

		if not sup isa MGenericType then return true
		var sub2 = sub.supertype_to(mainmodule, anchor, sup.mclass)

		# Test each argument of a generic by recursive calls
		for i in [0..sup.mclass.arity[ do
			var sub_arg = sub2.arguments[i]
			var sup_arg = sup.arguments[i]
			var res2 = is_subtype(sub_arg, sup_arg)
			if not res2 then return false
		end
		return true
	end

	# Subtyping test with perfect hashing
	# * `id` is the identifier of the target class
	# * `mask` is the perfect hashing mask of the receiver class
	# * `vtable` is the pointer to the virtual table of the receiver class
	fun inter_is_subtype_ph(id: Int, mask:Int, vtable: Pointer): Bool `{
		// hv is the position in hashtable
		int hv = id & mask;

		// Follow the pointer to somewhere in the vtable
		long unsigned int *offset = (long unsigned int*)(((long int *)vtable)[-hv]);

		// If the pointed value is corresponding to the identifier, the test is true, otherwise false
		return *offset == id;
	`}

	# Subtyping test with Cohen test (direct access)
	# * `id` is the identifier of the target class
	# * `mask` is the absolute position of the target identifier in the virtual table
	# * `vtable` is the pointer to the virtual table of the receiver class
	fun inter_is_subtype_sst(id: Int, position: Int, vtable: Pointer): Bool `{
		// Direct access to the position given in parameter
		int tableid = (long unsigned int)((long int *)vtable)[position];

		return id == tableid;
	`}

	# Redef init_instance to simulate the loading of a class
	redef fun init_instance(recv: Instance)
	do
		if not recv.mtype.as(MClassType).mclass.loaded then load_class(recv.mtype.as(MClassType).mclass)

		recv.vtable = recv.mtype.as(MClassType).mclass.vtable

		assert recv isa MutableInstance

		recv.internal_attributes = init_internal_attributes(initialization_value, recv.mtype.as(MClassType).mclass.mattributes.length)
		super
	end

	# Associate a `PrimitiveInstance` to its `VTable`
	redef fun init_instance_primitive(recv: Instance)
	do
		if not recv.mtype.as(MClassType).mclass.loaded then load_class(recv.mtype.as(MClassType).mclass)

		recv.vtable = recv.mtype.as(MClassType).mclass.vtable
	end

	# Initialize the internal representation of an object (its attribute values)
	# `init_instance` is the initial value of attributes
	private fun init_internal_attributes(init_instance: Instance, size: Int): Pointer
		import Array[Instance].length, Array[Instance].[] `{

		Instance* attributes = malloc(sizeof(Instance) * size);

		int i;
		for(i=0; i<size; i++)
			attributes[i] = init_instance;

		Instance_incr_ref(init_instance);
		return attributes;
	`}

	# Load the class and create its runtime structures, this loading is explicit
	fun load_class(mclass: MClass)
	do
		if mclass.loaded then return

		load_supers(mclass)

		if mclass.abstract_loaded then
			mclass.allocate_vtable(self)
		else
			mclass.make_vt(self, true)
		end
	end

	# Recursively load superclasses.
	private fun load_supers(mclass: MClass)
	do
		for parent in mclass.in_hierarchy(mainmodule).direct_greaters do
			load_class_indirect(parent)
		end
	end

	# This method is called to handle an implicitly loaded class,
	# i.e. a superclass of an explicitly loaded class
	# A class loaded implicitly will not be fully allocated
	fun load_class_indirect(mclass: MClass)
	do
		# It the class was already implicitly loaded
		if mclass.abstract_loaded then return

		load_supers(mclass)

		mclass.make_vt(self, false)
	end

	# Execute `mproperty` for a `args` (where `args[0]` is the receiver).
	redef fun send(mproperty: MMethod, args: Array[Instance]): nullable Instance
	do
		var recv = args.first
		var mtype = recv.mtype
		var ret = send_commons(mproperty, args, mtype)
		if ret != null then return ret

		var propdef = method_dispatch(mproperty, recv.vtable.as(not null), recv)

		return self.call(propdef, args)
	end

	# Method dispatch, for a given global method `mproperty`
	# returns the most specific local method in the class corresponding to `vtable`
	private fun method_dispatch(mproperty: MMethod, vtable: VTable, recv: Instance): MMethodDef
	do
		var position = recv.mtype.as(MClassType).mclass.get_position_methods(mproperty.intro_mclassdef.mclass)
		if position > 0 then
			return method_dispatch_sst(vtable.internal_vtable, mproperty.offset + position)
		else
			return method_dispatch_ph(vtable.internal_vtable, vtable.mask,
				mproperty.intro_mclassdef.mclass.vtable.id, mproperty.offset)
		end
	end

	# Execute a method dispatch with perfect hashing and return the appropriate `MMethodDef`
	# * `vtable` Pointer to the internal virtual table of the class
	# * `mask` Perfect hashing mask of the receiver class
	# * `id` Identifier of the class which introduce the method
	# * `offset` Relative offset of the method from the beginning of the block
	fun method_dispatch_ph(vtable: Pointer, mask: Int, id: Int, offset: Int): MMethodDef `{
		// Perfect hashing position
		int hv = mask & id;
		long unsigned int *pointer = (long unsigned int*)(((long int *)vtable)[-hv]);

		// pointer+2 is the position where methods are
		// Add the offset of property and get the method implementation
		MMethodDef propdef = (MMethodDef)*(pointer + 2 + offset);

		return propdef;
	`}

	# Execute a method dispatch with direct access and return the appropriate `MMethodDef`
	# * `vtable` Pointer to the internal virtual table of the class
	# * `absolute_offset` Absolute offset from the beginning of the virtual table
	fun method_dispatch_sst(vtable: Pointer, absolute_offset: Int): MMethodDef `{
		// pointer+2 is the position where methods are
		// Add the offset of property and get the method implementation
		MMethodDef propdef = (MMethodDef)((long int *)vtable)[absolute_offset];

		return propdef;
	`}

	# Return the value of the attribute `mproperty` for the object `recv`
	redef fun read_attribute(mproperty: MAttribute, recv: Instance): Instance
	do
		assert recv isa MutableInstance

		var i: Instance
		var position = recv.mtype.as(MClassType).mclass.get_position_attributes(mproperty.intro_mclassdef.mclass)
		if position > 0 then
			# if this attribute class has an unique position for this receiver, then use direct access
			i = read_attribute_sst(recv.internal_attributes, position + mproperty.offset)
		else
			# Otherwise, read the attribute value with perfect hashing
			var id = mproperty.intro_mclassdef.mclass.vtable.id

			i = read_attribute_ph(recv.internal_attributes, recv.vtable.internal_vtable,
					recv.vtable.mask, id, mproperty.offset)
		end

		# If we get a `MInit` value, throw an error
		if i == initialization_value then
			fatal("Uninitialized attribute {mproperty.name}")
			abort
		end

		return i
	end

	# Return the attribute value in `instance` with a sequence of perfect_hashing
	# * `instance` is the attributes array of the receiver
	# * `vtable` is the pointer to the virtual table of the class (of the receiver)
	# * `mask` is the perfect hashing mask of the class
	# * `id` is the identifier of the class
	# * `offset` is the relative offset of this attribute
	fun read_attribute_ph(instance: Pointer, vtable: Pointer, mask: Int, id: Int, offset: Int): Instance `{
		// Perfect hashing position
		int hv = mask & id;
		long unsigned int *pointer = (long unsigned int*)(((long int *)vtable)[-hv]);

		// pointer+1 is the position where the delta of the class is
		int absolute_offset = *(pointer + 1);

		Instance res = ((Instance *)instance)[absolute_offset + offset];

		return res;
	`}

	# Return the attribute value in `instance` with a direct access (SST)
	# * `instance` is the attributes array of the receiver
	# * `offset` is the absolute offset of this attribute
	fun read_attribute_sst(instance: Pointer, offset: Int): Instance `{
		/* We can make a direct access to the attribute value
		   because this attribute is always at the same position
		   for the class of this receiver */
		Instance res = ((Instance *)instance)[offset];

		return res;
	`}

	# Replace in `recv` the value of the attribute `mproperty` by `value`
	redef fun write_attribute(mproperty: MAttribute, recv: Instance, value: Instance)
	do
		assert recv isa MutableInstance

		# Replace the old value of mproperty in recv
		var position = recv.mtype.as(MClassType).mclass.get_position_attributes(mproperty.intro_mclassdef.mclass)
		if position > -1 then
			# if this attribute class has an unique position for this receiver, then use direct access
			write_attribute_sst(recv.internal_attributes, position + mproperty.offset, value)
		else
			# Otherwise, use perfect hashing to replace the old value
			var id = mproperty.intro_mclassdef.mclass.vtable.id

			write_attribute_ph(recv.internal_attributes, recv.vtable.internal_vtable,
					recv.vtable.mask, id, mproperty.offset, value)
		end
	end

	# Replace the value of an attribute in an instance
	# * `instance` is the attributes array of the receiver
	# * `vtable` is the pointer to the virtual table of the class (of the receiver)
	# * `mask` is the perfect hashing mask of the class
	# * `id` is the identifier of the class
	# * `offset` is the relative offset of this attribute
	# * `value` is the new value for this attribute
	fun write_attribute_ph(instance: Pointer, vtable: Pointer, mask: Int, id: Int, offset: Int, value: Instance) `{
		// Perfect hashing position
		int hv = mask & id;
		long unsigned int *pointer = (long unsigned int*)(((long int *)vtable)[-hv]);

		// pointer+1 is the position where the delta of the class is
		int absolute_offset = *(pointer + 1);

		((Instance *)instance)[absolute_offset + offset] = value;
		Instance_incr_ref(value);
	`}

	# Replace the value of an attribute in an instance with direct access
	# * `instance` is the attributes array of the receiver
	# * `offset` is the absolute offset of this attribute
	# * `value` is the new value for this attribute
	fun write_attribute_sst(instance: Pointer, offset: Int, value: Instance) `{
		// Direct access to the position with the absolute offset
		((Instance *)instance)[offset] = value;
		Instance_incr_ref(value);
	`}

	# Is the attribute `mproperty` initialized in the instance `recv`?
	redef fun isset_attribute(mproperty: MAttribute, recv: Instance): Bool
	do
		assert recv isa MutableInstance

		# Read the attribute value with internal perfect hashing read
		# because we do not want to throw an error if the value is `initialization_value`
		var id = mproperty.intro_mclassdef.mclass.vtable.id

		var i = read_attribute_ph(recv.internal_attributes, recv.vtable.internal_vtable,
					recv.vtable.mask, id, mproperty.offset)

		return i != initialization_value
	end
end