Merge: Loose Tokens

[nit.git] / src / vm / virtual_machine.nit

# This file is part of NIT ( http://www.nitlanguage.org ).
#
# Copyright 2014 Julien Pagès <julien.pages@lirmm.fr>
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

# Implementation of the Nit virtual machine
module virtual_machine

import interpreter::naive_interpreter
import perfect_hashing

redef class ModelBuilder
        fun run_virtual_machine(mainmodule: MModule, arguments: Array[String])
        do
                var time0 = get_time
                self.toolcontext.info("*** NITVM STARTING ***", 1)

                var interpreter = new VirtualMachine(self, mainmodule, arguments)
                interpreter.start(mainmodule)

                var time1 = get_time
                self.toolcontext.info("*** NITVM STOPPING : {time1-time0} ***", 2)
        end
end

# 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 res == false 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 res2 == false 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

                # Recursively load superclasses
                for parent in mclass.in_hierarchy(mainmodule).direct_greaters do load_class_indirect(parent)

                if mclass.abstract_loaded then
                        mclass.allocate_vtable(self)
                else
                        mclass.make_vt(self, true)
                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

                for parent in mclass.in_hierarchy(mainmodule).direct_greaters do load_class_indirect(parent)

                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

redef class MClass
        # A reference to the virtual table of this class
        var vtable: nullable VTable

        # True when the class is effectively loaded by the vm, false otherwise
        var loaded: Bool = false

        # Indicate this class was partially loaded (it only has its identifier allocated)
        var abstract_loaded: Bool = false

        # Color for Cohen subtyping test : the absolute position of the id
        # of this class in virtual tables
        var color: Int

        # For superclasses which have a non-invariant position, keep their position in attribute table
        var positions_attributes: HashMap[MClass, Int] = new HashMap[MClass, Int]

        # For superclasses which have a non-invariant position, keep their position in virtual table
        var positions_methods: HashMap[MClass, Int] = new HashMap[MClass, Int]

        # The position of the class' block in virtual table,
        # the position is set to -1 when the invariant position is no longer satisfied
        var position_attributes: Int

        # The position of the class' block in attribute table
        # the position is set to -1 when the invariant position is no longer satisfied
        var position_methods: Int

        # The chosen prefix for this class.
        # The prefix is the direct superclass which has the most properties,
        # this class will stay at its usual position in virtual table and attribute table
        var prefix: nullable MClass

        # The linear extension of all superclasses with the prefix rule
        var ordering: Array[MClass]

        # The `MAttribute` this class introduced
        var intro_mattributes = new Array[MAttribute]

        # The `MMethod` this class introduced
        var intro_mmethods = new Array[MMethod]

        # All `MAttribute` this class contains
        var mattributes = new Array[MAttribute]

        # All `MMethod` this class contains
        var mmethods = new Array[MMethod]

        # Allocates a VTable for this class and gives it an id
        # * `vm` The currently executed VirtualMachine
        # * `explicit` Indicate if this class was directly instantiated (i.e. not indirectly loaded)
        private fun make_vt(vm: VirtualMachine, explicit: Bool)
        do
                # `ordering` contains the order of superclasses for virtual tables
                ordering = superclasses_ordering(vm)
                ordering.remove(self)

                var ids = new Array[Int]
                var nb_methods = new Array[Int]
                var nb_attributes = new Array[Int]

                # Absolute offset of attribute from the beginning of the attributes table
                var offset_attributes = 0

                # Absolute offset of method from the beginning of the methods table,
                # is initialize to 3 because the first position is empty in the virtual table
                # and the second and third are respectively class id and delta
                var offset_methods = 3

                var parent
                var prefix_index = ordering.index_of(prefix.as(not null))
                for i in [0..ordering.length[ do
                        parent = ordering[i]

                        # Get the number of introduced methods and attributes for this class
                        var methods = parent.intro_mmethods.length
                        var attributes = parent.intro_mattributes.length

                        # Updates `mmethods` and `mattributes`
                        mmethods.add_all(parent.intro_mmethods)
                        mattributes.add_all(parent.intro_mattributes)

                        ids.push(parent.vtable.id)
                        nb_methods.push(methods)
                        nb_attributes.push(attributes)

                        # If the class is in the suffix part of the order
                        if i > prefix_index then
                                moved_class_attributes(vm, ordering[i], offset_attributes)
                                moved_class_methods(vm, ordering[i], offset_methods)
                        end

                        offset_attributes += attributes
                        offset_methods += methods
                        offset_methods += 2 # Because each block starts with an id and the delta
                end

                # Update the positions of the class
                update_positions(offset_attributes, offset_methods)

                ordering.add(self)

                # Compute the identifier with Perfect Hashing
                compute_identifier(vm, ids, offset_methods)

                # Update caches and offsets of methods and attributes for this class
                # If the loading was explicit, the virtual table will be allocated and filled
                set_offsets(vm, explicit)

                if not explicit then
                        # Just init the C-pointer to NULL to avoid errors
                        vtable.internal_vtable = vm.memory_manager.null_ptr
                end
        end

        # Allocate a unique identifier to the class with perfect hashing
        # * `vm` The currently executed VirtualMachine
        # * `ids` Array of superclasses identifiers
        # * `offset_methods : Offset from the beginning of the table of the group of methods
        private fun compute_identifier(vm: VirtualMachine, ids: Array[Int], offset_methods: Int)
        do
                vtable = new VTable
                var idc = new Array[Int]

                # Give an identifier to the class and put it inside the virtual table
                vtable.mask = vm.ph.pnand(ids, 1, idc) - 1
                vtable.id = idc[0]
                vtable.classname = name

                # Set the color for subtyping tests in SST of this class
                color = offset_methods - 2

                # Indicate the class has its identifier computed
                abstract_loaded = true
        end

        # Update the positions of this class
        # * `offset_attributes` The offset of the block of attributes of this class
        # * `offset_methods` The offset of the block of methods of this class
        private fun update_positions(offset_attributes: Int, offset_methods: Int)
        do
                # Recopy the position tables of the prefix in `self`
                for key, value in prefix.positions_methods do
                        positions_methods[key] = value
                end

                for key, value in prefix.positions_attributes do
                        positions_attributes[key] = value
                end

                # Save the offsets of self class
                position_attributes = offset_attributes
                position_methods = offset_methods
        end

        # Set the offsets for the properties introduced by `self` class
        # * `vm` The currently executed VirtualMachine
        # * `explicit` Indicate if this class was explicitly loaded
        private fun set_offsets(vm: VirtualMachine, explicit: Bool)
        do
                # Fixing offsets for self attributes and methods
                var relative_offset_attr = 0
                var relative_offset_meth = 0

                # Update `intro_mmethods` and `intro_mattributes`
                # For each MClassdef this MClass has
                for classdef in mclassdefs do
                        # For each property this MClassdef introduce
                        for p in classdef.intro_mproperties do
                                # Collect properties and fixing offsets
                                if p isa MMethod then
                                        p.offset = relative_offset_meth
                                        relative_offset_meth += 1

                                        intro_mmethods.add(p)
                                end
                                if p isa MAttribute then
                                        p.offset = relative_offset_attr
                                        relative_offset_attr += 1

                                        intro_mattributes.add(p)
                                end
                        end
                end

                # Updates caches with introduced attributes of `self` class
                mattributes.add_all(intro_mattributes)
                mmethods.add_all(intro_mmethods)

                if explicit then allocate_vtable(vm)
        end

        # Allocate a single vtable
        # * `vm` The currently executed VirtualMachine
        private fun allocate_vtable(vm: VirtualMachine)
        do
                var ids = new Array[Int]
                var nb_methods_total = new Array[Int]
                var nb_attributes_total = new Array[Int]

                for cl in ordering do
                        ids.add(cl.vtable.id)
                        nb_methods_total.add(cl.intro_mmethods.length)
                        nb_attributes_total.add(cl.intro_mattributes.length)
                end

                # Calculate the delta to prepare object structure
                var deltas = calculate_delta(nb_attributes_total)
                vtable.internal_vtable = vm.memory_manager.init_vtable(ids, nb_methods_total, deltas, vtable.mask)

                # The virtual table now needs to be filled with pointer to methods
                for cl in ordering do
                        fill_vtable(vm, vtable.as(not null), cl)
                end

                loaded = true
        end

        # Fill the vtable with local methods for `self` class
        # * `vm` Current instance of the VirtualMachine
        # * `table` the table of self class, will be filled with its methods
        # * `cl` The class which introduced the methods
        private fun fill_vtable(vm: VirtualMachine, table: VTable, cl: MClass)
        do
                var methods = new Array[MMethodDef]
                for m in cl.intro_mmethods do
                        # `propdef` is the most specific implementation for this MMethod
                        var propdef = m.lookup_first_definition(vm.mainmodule, self.intro.bound_mtype)
                        methods.push(propdef)
                end

                # Call a method in C to put propdefs of self methods in the vtables
                vm.memory_manager.put_methods(vtable.internal_vtable, vtable.mask, cl.vtable.id, methods)
        end

        # Computes delta for each class
        # A delta represents the offset for this group of attributes in the object
        # *`nb_attributes` : number of attributes for each class (classes are linearized from Object to current)
        # * return deltas for each class
        private fun calculate_delta(nb_attributes: Array[Int]): Array[Int]
        do
                var deltas = new Array[Int]

                var total = 0
                for nb in nb_attributes do
                        deltas.push(total)
                        total += nb
                end

                return deltas
        end

        # Order superclasses of self
        # Return the order of superclasses in runtime structures of this class
        private fun superclasses_ordering(v: VirtualMachine): Array[MClass]
        do
                var superclasses = new Array[MClass]

                # Add all superclasses of `self`
                superclasses.add_all(self.in_hierarchy(v.mainmodule).greaters)

                var res = new Array[MClass]
                if superclasses.length > 1 then
                        # Starting at self
                        var ordering = self.dfs(v, res)

                        return ordering
                else
                        # There is no super-class, self is Object
                        prefix = self
                        return superclasses
                end
        end

        # A kind of Depth-First-Search for superclasses ordering
        # *`v` : the current executed instance of VirtualMachine
        # * `res` : Result Array, ie current superclasses ordering
        private fun dfs(v: VirtualMachine, res: Array[MClass]): Array[MClass]
        do
                # Add this class at the beginning
                res.insert(self, 0)

                var direct_parents = self.in_hierarchy(v.mainmodule).direct_greaters.to_a

                if direct_parents.length > 1 then
                        # Prefix represents the class which has the most properties
                        # we try to choose it in first to reduce the number of potential recompilations
                        var prefix = null
                        var max = -1
                        for cl in direct_parents do
                                # If we never have visited this class
                                if not res.has(cl) then
                                        var properties_length = cl.mmethods.length + cl.mattributes.length
                                        if properties_length > max then
                                                max = properties_length
                                                prefix = cl
                                        end
                                end
                        end

                        if prefix != null then
                                if self.prefix == null then self.prefix = prefix

                                # Add the prefix class ordering at the beginning of our sequence
                                var prefix_res = new Array[MClass]
                                prefix_res = prefix.dfs(v, prefix_res)

                                # Then we recurse on other classes
                                for cl in direct_parents do
                                        if cl != prefix then
                                                res = new Array[MClass]
                                                res = cl.dfs(v, res)

                                                for cl_res in res do
                                                        if not prefix_res.has(cl_res) then prefix_res.push(cl_res)
                                                end
                                        end
                                end
                                res = prefix_res
                        end

                        res.push(self)
                else
                        if direct_parents.length > 0 then
                                if prefix == null then prefix = direct_parents.first

                                res = direct_parents.first.dfs(v, res)
                        end
                end

                if not res.has(self) then res.push(self)

                return res
        end

        # This method is called when `current_class` class is moved in virtual table of `self`
        # *`vm` Running instance of the virtual machine
        # *`current_class` The class which was moved in `self` structures
        # *`offset` The offset of block of methods of `current_class` in `self`
        fun moved_class_methods(vm: VirtualMachine, current_class: MClass, offset: Int)
        do
                # `current_class` was moved in `self` method table
                if current_class.position_methods > 0 then
                        # The invariant position is no longer satisfied
                        current_class.positions_methods[current_class] = current_class.position_methods
                        current_class.position_methods = - current_class.position_methods
                else
                        # The class has already several positions and an update is needed
                        current_class.positions_methods[current_class] = -current_class.positions_methods[current_class]

                        for sub in ordering do
                                if sub == current_class then continue

                                var super_id = current_class.vtable.id
                                var mask = sub.vtable.mask
                                vm.load_class(sub)

                                if vm.inter_is_subtype_ph(super_id, mask, sub.vtable.internal_vtable) then
                                        if not sub.positions_methods.has_key(current_class) then
                                                sub.positions_methods[current_class] = current_class.position_methods
                                        else
                                                var old_position = sub.positions_methods[current_class]
                                                if old_position > 0 then
                                                        # Indicate this class can not used anymore single inheritance implementation
                                                        sub.positions_methods[current_class] = - old_position
                                                end
                                        end
                                end
                        end
                end

                # Save the position of `current_class` in `self`
                positions_methods[current_class] = offset
        end

        # This method is called when `current_class` class is moved in attribute table of `self`
        # *`vm` Running instance of the virtual machine
        # *`current_class` The class which was moved in `self` structures
        # *`offset` The offset of block of attributes of `current_class` in `self`
        fun moved_class_attributes(vm: VirtualMachine, current_class: MClass, offset: Int)
        do
                # `current_class` was moved in `self` attribute table
                if not current_class.positions_attributes.has_key(current_class) then
                        # The invariant position is no longer satisfied
                        current_class.positions_attributes[current_class] = current_class.position_attributes
                        current_class.position_attributes = - current_class.position_attributes
                else
                        # The class has already several positions and an update is needed
                        current_class.positions_attributes[current_class] = - current_class.positions_attributes[current_class]

                        for sub in ordering do
                                if sub == current_class then continue

                                var super_id = current_class.vtable.id
                                var mask = sub.vtable.mask
                                vm.load_class(sub)

                                if vm.inter_is_subtype_ph(super_id, mask, sub.vtable.internal_vtable) then
                                        if not sub.positions_methods.has_key(current_class) then
                                                sub.positions_attributes[current_class] = current_class.position_attributes
                                        else
                                                var old_position = sub.positions_attributes[current_class]
                                                if old_position > 0 then
                                                        # Indicate this class can not used anymore single inheritance implementation
                                                        sub.positions_attributes[current_class] = - old_position
                                                end
                                        end
                                end
                        end
                end

                # Save the position of `current_class` in `self`
                positions_attributes[current_class] = offset
        end

        # Return the position of the method's block of class `cl` in `self` if `cl` has an invariant position in self,
        # Otherwise return a negative position
        fun get_position_methods(cl: MClass): Int
        do
                # The class has an invariant position in all subclasses
                if cl.position_methods > 0 then return cl.position_methods

                # The position has an invariant position for this class and its subclasses only
                if positions_methods.has_key(cl) then
                        var pos = positions_methods[cl]
                        if pos > 0 then return pos
                        return -1
                end

                # No invariant position at all, the caller must use a multiple inheritance implementation
                return -1
        end

        # Return the position of the attribute's block of class `cl` in `self` if `cl` has an invariant position in self,
        # Otherwise return a negative position
        fun get_position_attributes(cl: MClass): Int
        do
                # The class has an invariant position in all subclasses
                if cl.position_attributes > 0 then return cl.position_attributes

                # The position has an invariant position for this class and its subclasses only
                if positions_attributes.has_key(cl) then
                        var pos = positions_attributes[cl]
                        if pos > 0 then return pos
                        return -1
                end

                # No invariant position at all, the caller must use a multiple inheritance implementation
                return -1
        end
end

redef class MProperty
        # Relative offset of this in the runtime instance
        # (beginning of the block of its introducing class for attributes or methods)
        var offset: Int
end

redef class MAttribute
        # Relative offset of this attribute in the runtime instance
        # (beginning of the block of its introducing class)
        redef var offset: Int
end

redef class MMethod
        # Relative offset of this method in the virtual table (from the beginning of the block)
        redef var offset: Int
end

# Redef MutableInstance to improve implementation of attributes in objects
redef class MutableInstance

        # C-array to store pointers to attributes of this Object
        var internal_attributes: Pointer
end

# Redef to associate an `Instance` to its `VTable`
redef class Instance

        # Associate a runtime instance to its virtual table which contains methods, types etc.
        var vtable: nullable VTable
end

# Is the type of the initial value inside attributes
class MInitType
        super MType

        redef var model: Model

        redef fun to_s do return "InitType"
        redef fun as_nullable do return self
        redef fun need_anchor do return false
        redef fun resolve_for(mtype, anchor, mmodule, cleanup_virtual) do return self
        redef fun can_resolve_for(mtype, anchor, mmodule) do return true

        redef fun collect_mclassdefs(mmodule) do return new HashSet[MClassDef]

        redef fun collect_mclasses(mmodule) do return new HashSet[MClass]

        redef fun collect_mtypes(mmodule) do return new HashSet[MClassType]
end

# A VTable contains the virtual method table for the dispatch
# and informations to perform subtyping tests
class VTable
        # The mask to perform perfect hashing
        var mask: Int is noinit

        # Unique identifier given by perfect hashing
        var id: Int is noinit

        # Pointer to the c-allocated area, represents the virtual table
        var internal_vtable: Pointer is noinit

        # The short classname of this class
        var classname: String is noinit
end

# Handle memory, used for allocate virtual table and associated structures
class MemoryManager

        # Allocate and fill a virtual table
        fun init_vtable(ids: Array[Int], nb_methods: Array[Int], nb_attributes: Array[Int], mask: Int): Pointer
        do
                # Allocate in C current virtual table
                var res = intern_init_vtable(ids, nb_methods, nb_attributes, mask)

                return res
        end

        # Construct virtual tables with a bi-dimensional layout
        private fun intern_init_vtable(ids: Array[Int], nb_methods: Array[Int], deltas: Array[Int], mask: Int): Pointer
                import Array[Int].length, Array[Int].[] `{

                // Allocate and fill current virtual table
                int i;
                int total_size = 0; // total size of this virtual table
                int nb_classes = Array_of_Int_length(nb_methods);
                for(i = 0; i<nb_classes; i++) {
                        /* - One for each method of this class
                        *  - One for the delta (offset of this group of attributes in objects)
                        *  - One for the id
                        */
                        total_size += Array_of_Int__index(nb_methods, i);
                        total_size += 2;
                }

                // Add the size of the perfect hashtable (mask +1)
                // Add one because we start to fill the vtable at position 1 (0 is the init position)
                total_size += mask+2;
                long unsigned int* vtable = malloc(sizeof(long unsigned int)*total_size);

                // Initialisation to the first position of the virtual table (ie : Object)
                long unsigned int *init = vtable + mask + 2;
                for(i=0; i<total_size; i++)
                        vtable[i] = (long unsigned int)init;

                // Set the virtual table to its position 0
                // ie: after the hashtable
                vtable = vtable + mask + 1;

                int current_size = 1;
                for(i = 0; i < nb_classes; i++) {
                        /*
                                vtable[hv] contains a pointer to the group of introduced methods
                                For each superclasse we have in virtual table :
                                        (id | delta | introduced methods)
                        */
                        int hv = mask & Array_of_Int__index(ids, i);

                        vtable[current_size] = Array_of_Int__index(ids, i);
                        vtable[current_size + 1] = Array_of_Int__index(deltas, i);
                        vtable[-hv] = (long unsigned int)&(vtable[current_size]);

                        current_size += 2;
                        current_size += Array_of_Int__index(nb_methods, i);
                }

                return vtable;
        `}

        # Put implementation of methods of a class in `vtable`
        # * `vtable` : Pointer to the C-virtual table
        # * `mask` : perfect-hashing mask of the class corresponding to the vtable
        # * `id` : id of the target class
        # * `methods` : array of MMethodDef of the target class
        fun put_methods(vtable: Pointer, mask: Int, id: Int, methods: Array[MMethodDef])
                import Array[MMethodDef].length, Array[MMethodDef].[] `{

                // Get the area to fill with methods by a sequence of perfect hashing
                int hv = mask & id;
                long unsigned int *pointer = (long unsigned int*)(((long unsigned int *)vtable)[-hv]);

                // pointer+2 is the beginning of the area for methods implementation
                int length = Array_of_MMethodDef_length(methods);
                long unsigned int *area = (pointer + 2);
                int i;

                for(i=0; i<length; i++)
                {
                        MMethodDef method = Array_of_MMethodDef__index(methods, i);
                        area[i] = (long unsigned int)method;
                        MMethodDef_incr_ref(method);
                }
        `}

        # Return a NULL pointer, used to initialize virtual tables
        private fun null_ptr: Pointer `{
                return NULL;
        `}
end