assert sup isa MClassType
- # `sub` and `sup` can be discovered inside a Generic type during the subtyping test
- if not sup.mclass.loaded then create_class(sup.mclass)
- if not sub.mclass.loaded then create_class(sub.mclass)
+ # 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
+ 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 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
+ if not res2 then return false
end
return true
end
# 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)
+ if not recv.mtype.as(MClassType).mclass.loaded then load_class(recv.mtype.as(MClassType).mclass)
recv.vtable = recv.mtype.as(MClassType).mclass.vtable
# Associate a `PrimitiveInstance` to its `VTable`
redef fun init_instance_primitive(recv: Instance)
do
- if not recv.mtype.as(MClassType).mclass.loaded then create_class(recv.mtype.as(MClassType).mclass)
+ 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
return attributes;
`}
- # Creates the runtime structures for this class
- fun create_class(mclass: MClass) do mclass.make_vt(self)
+ # 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
# returns the most specific local method in the class corresponding to `vtable`
private fun method_dispatch(mproperty: MMethod, vtable: VTable, recv: Instance): MMethodDef
do
- if mproperty.intro_mclassdef.mclass.positions_methods[recv.mtype.as(MClassType).mclass] != -1 then
- return method_dispatch_sst(vtable.internal_vtable, mproperty.absolute_offset)
+ 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)
assert recv isa MutableInstance
var i: Instance
-
- if mproperty.intro_mclassdef.mclass.positions_attributes[recv.mtype.as(MClassType).mclass] != -1 then
+ 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, mproperty.absolute_offset)
+ 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
assert recv isa MutableInstance
# Replace the old value of mproperty in recv
- if mproperty.intro_mclassdef.mclass.positions_attributes[recv.mtype.as(MClassType).mclass] != -1 then
+ 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, mproperty.absolute_offset, value)
+ 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
# 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 each loaded subclass, keep the position of the group of attributes
- # introduced by self class in the object
+ # 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 each loaded subclass, keep the position of the group of methods
- # introduced by self class in the vtable
+ # 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]
var mmethods = new Array[MMethod]
# Allocates a VTable for this class and gives it an id
- private fun make_vt(v: VirtualMachine)
+ # * `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
- if loaded then return
-
- # `superclasses` contains the order of superclasses for virtual tables
- var superclasses = superclasses_ordering(v)
- superclasses.remove(self)
+ # `ordering` contains the order of superclasses for virtual tables
+ ordering = superclasses_ordering(vm)
+ ordering.remove(self)
- # Make_vt for super-classes
var ids = new Array[Int]
var nb_methods = new Array[Int]
var nb_attributes = new Array[Int]
# 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 superclasses.length > 0 then previous_parent = superclasses[0]
- for parent in superclasses do
- if not parent.loaded then parent.make_vt(v)
+ 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
nb_methods.push(methods)
nb_attributes.push(attributes)
- # Update `positions_attributes` and `positions_methods` in `parent`.
- # If the position is invariant for this parent, store this position
- # else store a special value (-1)
- var pos_attr = -1
- var pos_meth = -1
-
- if previous_parent.as(not null).positions_attributes[parent] == offset_attributes then pos_attr = offset_attributes
- if previous_parent.as(not null).positions_methods[parent] == offset_methods then pos_meth = offset_methods
-
- parent.update_positions(pos_attr, pos_meth, self)
+ # 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
- # 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
+ # Update the positions of the class
+ update_positions(offset_attributes, offset_methods)
- # Set the absolute position of the identifier of this class in the virtual table
- color = offset_methods - 2
+ ordering.add(self)
- # The virtual table now needs to be filled with pointer to methods
- superclasses.add(self)
- for cl in superclasses do
- fill_vtable(v, vtable.as(not null), cl)
+ # 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 single vtable
- # * `ids : Array of superclasses identifiers
- # * `nb_methods : Array which contain the number of introduced methods for each class in ids
- # * `nb_attributes : Array which contain the number of introduced attributes for each class in ids
- # * `offset_attributes : Offset from the beginning of the table of the group of attributes
+ # 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 allocate_vtable(v: VirtualMachine, ids: Array[Int], nb_methods: Array[Int], nb_attributes: Array[Int],
- offset_attributes: Int, offset_methods: Int)
+ private fun compute_identifier(vm: VirtualMachine, ids: Array[Int], offset_methods: Int)
do
vtable = new VTable
var idc = new Array[Int]
- vtable.mask = v.ph.pnand(ids, 1, idc) - 1
+ # 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
- # Add current id to Array of super-ids
- var ids_total = new Array[Int]
- ids_total.add_all(ids)
- ids_total.push(vtable.id)
+ # Set the color for subtyping tests in SST of this class
+ color = offset_methods - 2
- var nb_methods_total = new Array[Int]
- var nb_attributes_total = new Array[Int]
+ # Indicate the class has its identifier computed
+ abstract_loaded = true
+ end
- var self_methods = 0
- var nb_introduced_attributes = 0
+ # 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
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)
mattributes.add_all(intro_mattributes)
mmethods.add_all(intro_mmethods)
- nb_methods_total.add_all(nb_methods)
- nb_methods_total.push(self_methods)
+ if explicit then allocate_vtable(vm)
+ end
- nb_attributes_total.add_all(nb_attributes)
- nb_attributes_total.push(nb_introduced_attributes)
+ # 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]
- # Save the offsets of self class
- update_positions(offset_attributes, offset_methods, self)
+ 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
- # Since we have the number of attributes for each class, calculate the delta
+ # Calculate the delta to prepare object structure
var deltas = calculate_delta(nb_attributes_total)
- vtable.internal_vtable = v.memory_manager.init_vtable(ids_total, nb_methods_total, deltas, vtable.mask)
+ 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 methods of `self` class
- # * `v` : Current instance of the VirtualMachine
- # * `table` : the table of self class, will be filled with its methods
- private fun fill_vtable(v:VirtualMachine, table: VTable, cl: MClass)
+ # 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(v.mainmodule, self.intro.bound_mtype)
+ 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
- v.memory_manager.put_methods(vtable.internal_vtable, vtable.mask, cl.vtable.id, methods)
+ vm.memory_manager.put_methods(vtable.internal_vtable, vtable.mask, cl.vtable.id, methods)
end
# Computes delta for each class
return ordering
else
# There is no super-class, self is Object
+ prefix = self
return superclasses
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)
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
return res
end
- # Update positions of the class `cl`
- # * `attributes_offset`: absolute offset of introduced attributes
- # * `methods_offset`: absolute offset of introduced methods
- private fun update_positions(attributes_offsets: Int, methods_offset:Int, cl: MClass)
+ # 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
- positions_attributes[cl] = attributes_offsets
- positions_methods[cl] = methods_offset
+ # `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)
- var offset: Int
-
- # Absolute offset of this attribute in the runtime instance (beginning of the attribute table)
- var absolute_offset: Int
+ redef var offset: Int
end
redef class MMethod
# Relative offset of this method in the virtual table (from the beginning of the block)
- var offset: Int
-
- # Absolute offset of this method in the virtual table (from the beginning of the vtable)
- var absolute_offset: Int
+ redef var offset: Int
end
# Redef MutableInstance to improve implementation of attributes in objects
MMethodDef_incr_ref(method);
}
`}
+
+ # Return a NULL pointer, used to initialize virtual tables
+ private fun null_ptr: Pointer `{
+ return NULL;
+ `}
end
nitlanguage / nit.git / blobdiff