module vm
import interpreter::naive_interpreter
-import model_utils
import perfect_hashing
redef class ModelBuilder
- redef fun run_naive_interpreter(mainmodule: MModule, arguments: Array[String])
+ fun run_virtual_machine(mainmodule: MModule, arguments: Array[String])
do
var time0 = get_time
self.toolcontext.info("*** NITVM STARTING ***", 1)
var memory_manager: MemoryManager = new MemoryManager
# The unique instance of the `MInit` value
- var initialization_value: Instance
+ var initialization_value: Instance is noinit
- init(modelbuilder: ModelBuilder, mainmodule: MModule, arguments: Array[String])
+ init
do
var init_type = new MInitType(mainmodule.model)
initialization_value = new MutableInstance(init_type)
super
end
- # Subtyping test for the virtual machine
+ # 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 MParameterType or sub isa MVirtualType then
+ sub = sub.resolve_for(anchor.mclass.mclass_type, anchor, mainmodule, false)
+ end
+ if sup isa MParameterType or sup isa MVirtualType 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
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
assert sup isa MClassType
- # Create the sup vtable if not create
+ # `sub` and `sup` can be discovered inside a Generic type during the subtyping test
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 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
-
+ # For now, always use perfect hashing for subtyping test
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)
+ 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
- private fun inter_is_subtype(id: Int, mask:Int, vtable: Pointer): Bool `{
+ private fun inter_is_subtype_ph(id: Int, mask:Int, vtable: Pointer): Bool `{
// hv is the position in hashtable
int hv = id & mask;
return *offset == id;
`}
+ # Subtyping test with Cohen test (direct access)
+ private 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
assert recv isa MutableInstance
- recv.internal_attributes = init_internal_attributes(initialization_value, recv.mtype.as(MClassType).mclass.all_mattributes(mainmodule, none_visibility).length)
+ recv.internal_attributes = init_internal_attributes(initialization_value, recv.mtype.as(MClassType).mclass.mattributes.length)
super
end
var ret = send_commons(mproperty, args, mtype)
if ret != null then return ret
- var propdef = method_dispatch(mproperty, recv.vtable.as(not null))
+ 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): MMethodDef
+ private fun method_dispatch(mproperty: MMethod, vtable: VTable, recv: Instance): MMethodDef
do
- return method_dispatch_ph(vtable.internal_vtable, vtable.mask,
+ if mproperty.intro_mclassdef.mclass.positions_methods[recv.mtype.as(MClassType).mclass] != -1 then
+ return method_dispatch_sst(vtable.internal_vtable, mproperty.absolute_offset)
+ 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
return propdef;
`}
+ # Execute a method dispatch with direct access and return the appropriate `MMethodDef`
+ # `vtable` : Pointer to the internal pointer of the class
+ # `absolute_offset` : Absolute offset from the beginning of the virtual table
+ private 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
# True when the class is effectively loaded by the vm, false otherwise
var loaded: Bool = false
+ # Color for Cohen subtyping test : the absolute position of the id
+ # of this class in virtual tables
+ var color: Int
+
# For each loaded subclass, keep the position of the group of attributes
# introduced by self class in the object
var positions_attributes: HashMap[MClass, Int] = new HashMap[MClass, Int]
# introduced by self class in the vtable
var positions_methods: HashMap[MClass, Int] = new HashMap[MClass, Int]
+ # 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
private fun make_vt(v: VirtualMachine)
do
# 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
- var offset_methods = 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
# The previous element in `superclasses`
var previous_parent: nullable MClass = null
if not parent.loaded then parent.make_vt(v)
# Get the number of introduced methods and attributes for this class
- var methods = 0
- var attributes = 0
+ var methods = parent.intro_mmethods.length
+ var attributes = parent.intro_mattributes.length
- for p in parent.intro_mproperties(none_visibility) do
- if p isa MMethod then methods += 1
- if p isa MAttribute then attributes += 1
- end
+ # 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)
offset_attributes += attributes
offset_methods += methods
+ offset_methods += 2 # Because each block starts with an id and the delta
end
# When all super-classes have their identifiers and vtables, allocate current one
allocate_vtable(v, ids, nb_methods, nb_attributes, offset_attributes, offset_methods)
loaded = true
+ # Set the absolute position of the identifier of this class in the virtual table
+ color = offset_methods - 2
+
# The virtual table now needs to be filled with pointer to methods
superclasses.add(self)
for cl in superclasses do
# Fixing offsets for self attributes and methods
var relative_offset_attr = 0
var relative_offset_meth = 0
- for p in intro_mproperties(none_visibility) do
- if p isa MMethod then
- self_methods += 1
- p.offset = relative_offset_meth
- p.absolute_offset = offset_methods + relative_offset_meth
- relative_offset_meth += 1
- end
- if p isa MAttribute then
- nb_introduced_attributes += 1
- p.offset = relative_offset_attr
- p.absolute_offset = offset_attributes + relative_offset_attr
- relative_offset_attr += 1
+
+ # 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
+ self_methods += 1
+ p.offset = relative_offset_meth
+ p.absolute_offset = offset_methods + relative_offset_meth
+ relative_offset_meth += 1
+
+ intro_mmethods.add(p)
+ end
+ if p isa MAttribute then
+ nb_introduced_attributes += 1
+ p.offset = relative_offset_attr
+ p.absolute_offset = offset_attributes + 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)
+
nb_methods_total.add_all(nb_methods)
nb_methods_total.push(self_methods)
private fun fill_vtable(v:VirtualMachine, table: VTable, cl: MClass)
do
var methods = new Array[MMethodDef]
- for m in cl.intro_mproperties(none_visibility) do
- if m isa MMethod then
- # `propdef` is the most specific implementation for this MMethod
- var propdef = m.lookup_first_definition(v.mainmodule, self.intro.bound_mtype)
- methods.push(propdef)
- end
+ for m in cl.intro_mmethods do
+ # `propdef` is the most specific implementation for this MMethod
+ var propdef = m.lookup_first_definition(v.mainmodule, self.intro.bound_mtype)
+ methods.push(propdef)
end
# Call a method in C to put propdefs of self methods in the vtables
private fun superclasses_ordering(v: VirtualMachine): Array[MClass]
do
var superclasses = new Array[MClass]
- superclasses.add_all(ancestors)
+
+ # Add all superclasses of `self`
+ superclasses.add_all(self.in_hierarchy(v.mainmodule).greaters)
var res = new Array[MClass]
if superclasses.length > 1 then
for cl in direct_parents do
# If we never have visited this class
if not res.has(cl) then
- var properties_length = cl.all_mproperties(v.mainmodule, none_visibility).length
+ var properties_length = cl.mmethods.length + cl.mattributes.length
if properties_length > max then
max = properties_length
prefix = cl
# 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
super MType
redef var model: Model
- protected init(model: Model)
- do
- self.model = model
- end
redef fun to_s do return "InitType"
redef fun as_nullable do return self