[nit.git] / src / vm.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 vm

intrude import naive_interpreter
import model_utils
import perfect_hashing

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

                var interpreter = new VirtualMachine(self, mainmodule, arguments)
                init_naive_interpreter(interpreter, 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 and garbage collection
        var memory_manager: MemoryManager = new MemoryManager

        # Subtyping test for the virtual machine
        redef fun is_subtype(sub, sup: MType): Bool
        do
                var anchor = self.frame.arguments.first.mtype.as(MClassType)
                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

                # An unfixed formal type can only accept itself
                if sup isa MParameterType or sup isa MVirtualType then
                        return sub == sup
                end
                
                if sub isa MParameterType or sub isa MVirtualType 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

                # Create the sup vtable if not create
                if not sup.mclass.loaded then create_class(sup.mclass)

                # Sub can be discovered inside a Generic type during the subtyping test
                if not sub.mclass.loaded then create_class(sub.mclass)

                if anchor == null then anchor = sub
                if sup isa MGenericType then
                        var sub2 = sub.supertype_to(mainmodule, anchor, sup.mclass)
                        assert sub2.mclass == sup.mclass

                        for i in [0..sup.mclass.arity[ do
                                var sub_arg = sub2.arguments[i]
                                var sup_arg = sup.arguments[i]
                                var res = is_subtype(sub_arg, sup_arg)

                                if res == false then return false
                        end
                        return true
                end

                var super_id = sup.mclass.vtable.id
                var mask = sub.mclass.vtable.mask

                return inter_is_subtype(super_id, mask, sub.mclass.vtable.internal_vtable)
        end

        # Subtyping test with perfect hashing
        private fun inter_is_subtype(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;
        `}
        
        # 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 create_class(recv.mtype.as(MClassType).mclass)

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

                assert(recv isa MutableInstance)

                recv.internal_attributes = init_internal_attributes(null_instance, recv.mtype.as(MClassType).mclass.all_mattributes(mainmodule, none_visibility).length)
                super
        end
                
        # Initialize the internal representation of an object (its attribute values)
        private fun init_internal_attributes(null_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] = null_instance;

                Instance_incr_ref(null_instance);
                return attributes;
        `}

        # Creates the runtime structures for this class
        fun create_class(mclass: MClass) do     mclass.make_vt(self)

        # 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

                # Read the attribute value with perfect hashing
                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
        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
        private 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;
        `}

        # 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

                var id = mproperty.intro_mclassdef.mclass.vtable.id
                
                # Replace the old value of mproperty in recv
                write_attribute_ph(recv.internal_attributes, recv.vtable.internal_vtable,
                                        recv.vtable.mask, id, mproperty.offset, value)
        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
        private 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);
        `}
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

        # Cached attributes for faster instanciations of this class
        var cached_attributes: Array[MAttribute] = new Array[MAttribute]

        # Allocates a VTable for this class and gives it an id
        private fun make_vt(v: VirtualMachine)
        do
                if loaded then return

                # Superclasses contains all superclasses except self
                var superclasses = new Array[MClass]
                superclasses.add_all(ancestors)
                superclasses.remove(self)
                v.mainmodule.linearize_mclasses(superclasses)

                # Make_vt for super-classes
                var ids = new Array[Int]
                var nb_methods = new Array[Int]
                var nb_attributes = new Array[Int]

                for parent in superclasses do
                        if parent.vtable == null then parent.make_vt(v)
                        
                        # Get the number of introduced methods and attributes for this class
                        var methods = 0
                        var attributes = 0

                        for p in parent.intro_mproperties(none_visibility) do
                                if p isa MMethod then methods += 1
                                if p isa MAttribute then
                                        attributes += 1
                                end
                        end
                        
                        ids.push(parent.vtable.id)
                        nb_methods.push(methods)
                        nb_attributes.push(attributes)
                end
                
                # When all super-classes have their identifiers and vtables, allocate current one
                allocate_vtable(v, ids, nb_methods, nb_attributes)
                loaded = true
                # The virtual table now needs to be filled with pointer to methods
        end

        # Allocate a single vtable
        #     `ids : Array of superclasses identifiers
        #     `nb_methods : Array which contain the number of introducted methods for each class in ids
        #     `nb_attributes : Array which contain the number of introducted attributes for each class in ids
        private fun allocate_vtable(v: VirtualMachine, ids: Array[Int], nb_methods: Array[Int], nb_attributes: Array[Int])
        do
                vtable = new VTable
                var idc = new Array[Int]

                vtable.mask = v.ph.pnand(ids, 1, idc) - 1
                vtable.id = idc[0]
                vtable.classname = name

                # Add current id to Array of super-ids
                var ids_total = new Array[Int]
                ids_total.add_all(ids)
                ids_total.push(vtable.id)

                var nb_methods_total = new Array[Int]
                var nb_attributes_total = new Array[Int]

                var self_methods = 0
                var self_attributes = 0
                
                # For self attributes, fixing offsets
                var relative_offset = 0
                for p in intro_mproperties(none_visibility) do
                        if p isa MMethod then self_methods += 1
                        if p isa MAttribute then
                                self_attributes += 1
                                p.offset = relative_offset
                                relative_offset += 1
                                cached_attributes.push(p)
                        end
                end

                nb_methods_total.add_all(nb_methods)
                nb_methods_total.push(self_methods)

                nb_attributes_total.add_all(nb_attributes)
                nb_attributes_total.push(self_attributes)

                # Since we have the number of attributes for each class, calculate the delta
                var d = calculate_delta(nb_attributes_total)
                vtable.internal_vtable = v.memory_manager.init_vtable(ids_total, nb_methods_total, d, vtable.mask)
        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
end

redef class MAttribute
        # Represents the relative offset of this attribute in the runtime instance
        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

# 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

redef class Instance
        var vtable: nullable VTable
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;
        `}
end