nitc :: virtual_machine $ Instance
Redef to associate anInstance
to its VTable
nitc :: virtual_machine $ MProperty
A service (global property) that generalize method, attribute, etc.nitc :: virtual_machine $ ModelBuilder
A model builder knows how to load nit source files and build the associated modelnitc :: virtual_machine $ MutableInstance
Redef MutableInstance to improve implementation of attributes in objectsnitc :: virtual_machine $ Instance
Redef to associate anInstance
to its VTable
nitc :: virtual_machine $ MProperty
A service (global property) that generalize method, attribute, etc.nitc :: virtual_machine $ ModelBuilder
A model builder knows how to load nit source files and build the associated modelnitc :: virtual_machine $ MutableInstance
Redef MutableInstance to improve implementation of attributes in objectsSerializable::inspect
to show more useful information
nitc :: modelbuilder
more_collections :: more_collections
Highly specific, but useful, collections-related classes.serialization :: serialization_core
Abstract services to serialize Nit objects to different formatsserialize_to_json
and JsonSerializer
nitc :: toolcontext
Common command-line tool infrastructure than handle options and error messagescore :: union_find
union–find algorithm using an efficient disjoint-set data structureclone
method of the astbuilder tool
# 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 not res then return false
# sub and sup can be generic types, each argument of generics has to be tested
if not sup isa MGenericType then return true
var sub2 = sub.supertype_to(mainmodule, anchor, sup.mclass)
# Test each argument of a generic by recursive calls
for i in [0..sup.mclass.arity[ do
var sub_arg = sub2.arguments[i]
var sup_arg = sup.arguments[i]
var res2 = is_subtype(sub_arg, sup_arg)
if not res2 then return false
end
return true
end
# Subtyping test with perfect hashing
# * `id` is the identifier of the target class
# * `mask` is the perfect hashing mask of the receiver class
# * `vtable` is the pointer to the virtual table of the receiver class
fun inter_is_subtype_ph(id: Int, mask:Int, vtable: Pointer): Bool `{
// hv is the position in hashtable
int hv = id & mask;
// Follow the pointer to somewhere in the vtable
long unsigned int *offset = (long unsigned int*)(((long int *)vtable)[-hv]);
// If the pointed value is corresponding to the identifier, the test is true, otherwise false
return *offset == id;
`}
# Subtyping test with Cohen test (direct access)
# * `id` is the identifier of the target class
# * `mask` is the absolute position of the target identifier in the virtual table
# * `vtable` is the pointer to the virtual table of the receiver class
fun inter_is_subtype_sst(id: Int, position: Int, vtable: Pointer): Bool `{
// Direct access to the position given in parameter
int tableid = (long unsigned int)((long int *)vtable)[position];
return id == tableid;
`}
# Redef init_instance to simulate the loading of a class
redef fun init_instance(recv: Instance)
do
if not recv.mtype.as(MClassType).mclass.loaded then load_class(recv.mtype.as(MClassType).mclass)
recv.vtable = recv.mtype.as(MClassType).mclass.vtable
assert recv isa MutableInstance
recv.internal_attributes = init_internal_attributes(initialization_value, recv.mtype.as(MClassType).mclass.mattributes.length)
super
end
# Associate a `PrimitiveInstance` to its `VTable`
redef fun init_instance_primitive(recv: Instance)
do
if not recv.mtype.as(MClassType).mclass.loaded then load_class(recv.mtype.as(MClassType).mclass)
recv.vtable = recv.mtype.as(MClassType).mclass.vtable
end
# Initialize the internal representation of an object (its attribute values)
# `init_instance` is the initial value of attributes
private fun init_internal_attributes(init_instance: Instance, size: Int): Pointer
import Array[Instance].length, Array[Instance].[] `{
Instance* attributes = malloc(sizeof(Instance) * size);
int i;
for(i=0; i<size; i++)
attributes[i] = init_instance;
Instance_incr_ref(init_instance);
return attributes;
`}
# Load the class and create its runtime structures, this loading is explicit
fun load_class(mclass: MClass)
do
if mclass.loaded then return
load_supers(mclass)
if mclass.abstract_loaded then
mclass.allocate_vtable(self)
else
mclass.make_vt(self, true)
end
end
# Recursively load superclasses.
private fun load_supers(mclass: MClass)
do
for parent in mclass.in_hierarchy(mainmodule).direct_greaters do
load_class_indirect(parent)
end
end
# This method is called to handle an implicitly loaded class,
# i.e. a superclass of an explicitly loaded class
# A class loaded implicitly will not be fully allocated
fun load_class_indirect(mclass: MClass)
do
# It the class was already implicitly loaded
if mclass.abstract_loaded then return
load_supers(mclass)
mclass.make_vt(self, false)
end
# Execute `mproperty` for a `args` (where `args[0]` is the receiver).
redef fun send(mproperty: MMethod, args: Array[Instance]): nullable Instance
do
var recv = args.first
var mtype = recv.mtype
var ret = send_commons(mproperty, args, mtype)
if ret != null then return ret
var propdef = method_dispatch(mproperty, recv.vtable.as(not null), recv)
return self.call(propdef, args)
end
# Method dispatch, for a given global method `mproperty`
# returns the most specific local method in the class corresponding to `vtable`
private fun method_dispatch(mproperty: MMethod, vtable: VTable, recv: Instance): MMethodDef
do
var position = recv.mtype.as(MClassType).mclass.get_position_methods(mproperty.intro_mclassdef.mclass)
if position > 0 then
return method_dispatch_sst(vtable.internal_vtable, mproperty.offset + position)
else
return method_dispatch_ph(vtable.internal_vtable, vtable.mask,
mproperty.intro_mclassdef.mclass.vtable.id, mproperty.offset)
end
end
# Execute a method dispatch with perfect hashing and return the appropriate `MMethodDef`
# * `vtable` Pointer to the internal virtual table of the class
# * `mask` Perfect hashing mask of the receiver class
# * `id` Identifier of the class which introduce the method
# * `offset` Relative offset of the method from the beginning of the block
fun method_dispatch_ph(vtable: Pointer, mask: Int, id: Int, offset: Int): MMethodDef `{
// Perfect hashing position
int hv = mask & id;
long unsigned int *pointer = (long unsigned int*)(((long int *)vtable)[-hv]);
// pointer+2 is the position where methods are
// Add the offset of property and get the method implementation
MMethodDef propdef = (MMethodDef)*(pointer + 2 + offset);
return propdef;
`}
# Execute a method dispatch with direct access and return the appropriate `MMethodDef`
# * `vtable` Pointer to the internal virtual table of the class
# * `absolute_offset` Absolute offset from the beginning of the virtual table
fun method_dispatch_sst(vtable: Pointer, absolute_offset: Int): MMethodDef `{
// pointer+2 is the position where methods are
// Add the offset of property and get the method implementation
MMethodDef propdef = (MMethodDef)((long int *)vtable)[absolute_offset];
return propdef;
`}
# Return the value of the attribute `mproperty` for the object `recv`
redef fun read_attribute(mproperty: MAttribute, recv: Instance): Instance
do
assert recv isa MutableInstance
var i: Instance
var position = recv.mtype.as(MClassType).mclass.get_position_attributes(mproperty.intro_mclassdef.mclass)
if position > 0 then
# if this attribute class has an unique position for this receiver, then use direct access
i = read_attribute_sst(recv.internal_attributes, position + mproperty.offset)
else
# Otherwise, read the attribute value with perfect hashing
var id = mproperty.intro_mclassdef.mclass.vtable.id
i = read_attribute_ph(recv.internal_attributes, recv.vtable.internal_vtable,
recv.vtable.mask, id, mproperty.offset)
end
# If we get a `MInit` value, throw an error
if i == initialization_value then
fatal("Uninitialized attribute {mproperty.name}")
abort
end
return i
end
# Return the attribute value in `instance` with a sequence of perfect_hashing
# * `instance` is the attributes array of the receiver
# * `vtable` is the pointer to the virtual table of the class (of the receiver)
# * `mask` is the perfect hashing mask of the class
# * `id` is the identifier of the class
# * `offset` is the relative offset of this attribute
fun read_attribute_ph(instance: Pointer, vtable: Pointer, mask: Int, id: Int, offset: Int): Instance `{
// Perfect hashing position
int hv = mask & id;
long unsigned int *pointer = (long unsigned int*)(((long int *)vtable)[-hv]);
// pointer+1 is the position where the delta of the class is
int absolute_offset = *(pointer + 1);
Instance res = ((Instance *)instance)[absolute_offset + offset];
return res;
`}
# Return the attribute value in `instance` with a direct access (SST)
# * `instance` is the attributes array of the receiver
# * `offset` is the absolute offset of this attribute
fun read_attribute_sst(instance: Pointer, offset: Int): Instance `{
/* We can make a direct access to the attribute value
because this attribute is always at the same position
for the class of this receiver */
Instance res = ((Instance *)instance)[offset];
return res;
`}
# Replace in `recv` the value of the attribute `mproperty` by `value`
redef fun write_attribute(mproperty: MAttribute, recv: Instance, value: Instance)
do
assert recv isa MutableInstance
# Replace the old value of mproperty in recv
var position = recv.mtype.as(MClassType).mclass.get_position_attributes(mproperty.intro_mclassdef.mclass)
if position > -1 then
# if this attribute class has an unique position for this receiver, then use direct access
write_attribute_sst(recv.internal_attributes, position + mproperty.offset, value)
else
# Otherwise, use perfect hashing to replace the old value
var id = mproperty.intro_mclassdef.mclass.vtable.id
write_attribute_ph(recv.internal_attributes, recv.vtable.internal_vtable,
recv.vtable.mask, id, mproperty.offset, value)
end
end
# Replace the value of an attribute in an instance
# * `instance` is the attributes array of the receiver
# * `vtable` is the pointer to the virtual table of the class (of the receiver)
# * `mask` is the perfect hashing mask of the class
# * `id` is the identifier of the class
# * `offset` is the relative offset of this attribute
# * `value` is the new value for this attribute
fun write_attribute_ph(instance: Pointer, vtable: Pointer, mask: Int, id: Int, offset: Int, value: Instance) `{
// Perfect hashing position
int hv = mask & id;
long unsigned int *pointer = (long unsigned int*)(((long int *)vtable)[-hv]);
// pointer+1 is the position where the delta of the class is
int absolute_offset = *(pointer + 1);
((Instance *)instance)[absolute_offset + offset] = value;
Instance_incr_ref(value);
`}
# Replace the value of an attribute in an instance with direct access
# * `instance` is the attributes array of the receiver
# * `offset` is the absolute offset of this attribute
# * `value` is the new value for this attribute
fun write_attribute_sst(instance: Pointer, offset: Int, value: Instance) `{
// Direct access to the position with the absolute offset
((Instance *)instance)[offset] = value;
Instance_incr_ref(value);
`}
# Is the attribute `mproperty` initialized in the instance `recv`?
redef fun isset_attribute(mproperty: MAttribute, recv: Instance): Bool
do
assert recv isa MutableInstance
# Read the attribute value with internal perfect hashing read
# because we do not want to throw an error if the value is `initialization_value`
var id = mproperty.intro_mclassdef.mclass.vtable.id
var i = read_attribute_ph(recv.internal_attributes, recv.vtable.internal_vtable,
recv.vtable.mask, id, mproperty.offset)
return i != initialization_value
end
end
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
src/vm/virtual_machine.nit:17,1--1018,3