1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2014 Julien Pagès <julien.pages@lirmm.fr>
5 # Licensed under the Apache License, Version 2.0 (the "License");
6 # you may not use this file except in compliance with the License.
7 # You may obtain a copy of the License at
9 # http://www.apache.org/licenses/LICENSE-2.0
11 # Unless required by applicable law or agreed to in writing, software
12 # distributed under the License is distributed on an "AS IS" BASIS,
13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 # See the License for the specific language governing permissions and
15 # limitations under the License.
17 # Implementation of the Nit virtual machine
18 module virtual_machine
20 import interpreter
::naive_interpreter
21 import perfect_hashing
23 redef class ModelBuilder
24 fun run_virtual_machine
(mainmodule
: MModule, arguments
: Array[String])
27 self.toolcontext
.info
("*** NITVM STARTING ***", 1)
29 var interpreter
= new VirtualMachine(self, mainmodule
, arguments
)
30 interpreter
.start
(mainmodule
)
33 self.toolcontext
.info
("*** NITVM STOPPING : {time1-time0} ***", 2)
37 # A virtual machine based on the naive_interpreter
38 class VirtualMachine super NaiveInterpreter
40 # Perfect hashing and perfect numbering
41 var ph
: Perfecthashing = new Perfecthashing
43 # Handles memory allocated in C
44 var memory_manager
: MemoryManager = new MemoryManager
46 # The unique instance of the `MInit` value
47 var initialization_value
: Instance is noinit
51 var init_type
= new MInitType(mainmodule
.model
)
52 initialization_value
= new MutableInstance(init_type
)
56 # Runtime subtyping test
57 redef fun is_subtype
(sub
, sup
: MType): Bool
59 if sub
== sup
then return true
61 var anchor
= self.frame
.arguments
.first
.mtype
.as(MClassType)
63 # `sub` or `sup` are formal or virtual types, resolve them to concrete types
64 if sub
isa MFormalType then
65 sub
= sub
.resolve_for
(anchor
.mclass
.mclass_type
, anchor
, mainmodule
, false)
67 if sup
isa MFormalType then
68 sup
= sup
.resolve_for
(anchor
.mclass
.mclass_type
, anchor
, mainmodule
, false)
71 var sup_accept_null
= false
72 if sup
isa MNullableType then
73 sup_accept_null
= true
75 else if sup
isa MNullType then
76 sup_accept_null
= true
79 # Can `sub` provides null or not?
80 # Thus we can match with `sup_accept_null`
81 # Also discard the nullable marker if it exists
82 if sub
isa MNullableType then
83 if not sup_accept_null
then return false
85 else if sub
isa MNullType then
86 return sup_accept_null
88 # Now the case of direct null and nullable is over
90 if sub
isa MFormalType then
91 sub
= sub
.anchor_to
(mainmodule
, anchor
)
92 # Manage the second layer of null/nullable
93 if sub
isa MNullableType then
94 if not sup_accept_null
then return false
96 else if sub
isa MNullType then
97 return sup_accept_null
101 assert sub
isa MClassType
103 # `sup` accepts only null
104 if sup
isa MNullType then return false
106 assert sup
isa MClassType
108 # and `sup` can be discovered inside a Generic type during the subtyping test
109 if not sub
.mclass
.loaded
then load_class
(sub
.mclass
)
111 # If the target of the test is not-loaded yet, the subtyping-test will be false
112 if not sup
.mclass
.abstract_loaded
then return false
114 # For now, always use perfect hashing for subtyping test
115 var super_id
= sup
.mclass
.vtable
.id
116 var mask
= sub
.mclass
.vtable
.mask
118 var res
= inter_is_subtype_ph
(super_id
, mask
, sub
.mclass
.vtable
.internal_vtable
)
119 if res
== false then return false
120 # sub and sup can be generic types, each argument of generics has to be tested
122 if not sup
isa MGenericType then return true
123 var sub2
= sub
.supertype_to
(mainmodule
, anchor
, sup
.mclass
)
125 # Test each argument of a generic by recursive calls
126 for i
in [0..sup
.mclass
.arity
[ do
127 var sub_arg
= sub2
.arguments
[i
]
128 var sup_arg
= sup
.arguments
[i
]
129 var res2
= is_subtype
(sub_arg
, sup_arg
)
130 if res2
== false then return false
135 # Subtyping test with perfect hashing
136 # * `id` is the identifier of the target class
137 # * `mask` is the perfect hashing mask of the receiver class
138 # * `vtable` is the pointer to the virtual table of the receiver class
139 fun inter_is_subtype_ph
(id
: Int, mask
:Int, vtable
: Pointer): Bool `{
140 // hv is the position in hashtable
143 // Follow the pointer to somewhere in the vtable
144 long unsigned int *offset = (long unsigned int*)(((long int *)vtable)[-hv]);
146 // If the pointed value is corresponding to the identifier, the test is true, otherwise false
147 return *offset == id;
150 # Subtyping test with Cohen test (direct access)
151 # * `id` is the identifier of the target class
152 # * `mask` is the absolute position of the target identifier in the virtual table
153 # * `vtable` is the pointer to the virtual table of the receiver class
154 fun inter_is_subtype_sst
(id
: Int, position
: Int, vtable
: Pointer): Bool `{
155 // Direct access to the position given in parameter
156 int tableid = (long unsigned int)((long int *)vtable)[position];
158 return id == tableid;
161 # Redef init_instance to simulate the loading of a class
162 redef fun init_instance
(recv
: Instance)
164 if not recv
.mtype
.as(MClassType).mclass
.loaded
then load_class
(recv
.mtype
.as(MClassType).mclass
)
166 recv
.vtable
= recv
.mtype
.as(MClassType).mclass
.vtable
168 assert recv
isa MutableInstance
170 recv
.internal_attributes
= init_internal_attributes
(initialization_value
, recv
.mtype
.as(MClassType).mclass
.mattributes
.length
)
174 # Associate a `PrimitiveInstance` to its `VTable`
175 redef fun init_instance_primitive
(recv
: Instance)
177 if not recv
.mtype
.as(MClassType).mclass
.loaded
then load_class
(recv
.mtype
.as(MClassType).mclass
)
179 recv
.vtable
= recv
.mtype
.as(MClassType).mclass
.vtable
182 # Initialize the internal representation of an object (its attribute values)
183 # `init_instance` is the initial value of attributes
184 private fun init_internal_attributes
(init_instance
: Instance, size
: Int): Pointer
185 import Array[Instance].length
, Array[Instance].[] `{
187 Instance* attributes = malloc(sizeof(Instance) * size);
190 for(i=0; i<size; i++)
191 attributes[i] = init_instance;
193 Instance_incr_ref(init_instance);
197 # Load the class and create its runtime structures, this loading is explicit
198 fun load_class
(mclass
: MClass)
200 if mclass
.loaded
then return
202 # Recursively load superclasses
203 for parent
in mclass
.in_hierarchy
(mainmodule
).direct_greaters
do load_class_indirect
(parent
)
205 if mclass
.abstract_loaded
then
206 mclass
.allocate_vtable
(self)
208 mclass
.make_vt
(self, true)
212 # This method is called to handle an implicitly loaded class,
213 # i.e. a superclass of an explicitly loaded class
214 # A class loaded implicitly will not be fully allocated
215 fun load_class_indirect
(mclass
: MClass)
217 # It the class was already implicitly loaded
218 if mclass
.abstract_loaded
then return
220 for parent
in mclass
.in_hierarchy
(mainmodule
).direct_greaters
do load_class_indirect
(parent
)
222 mclass
.make_vt
(self, false)
225 # Execute `mproperty` for a `args` (where `args[0]` is the receiver).
226 redef fun send
(mproperty
: MMethod, args
: Array[Instance]): nullable Instance
228 var recv
= args
.first
229 var mtype
= recv
.mtype
230 var ret
= send_commons
(mproperty
, args
, mtype
)
231 if ret
!= null then return ret
233 var propdef
= method_dispatch
(mproperty
, recv
.vtable
.as(not null), recv
)
235 return self.call
(propdef
, args
)
238 # Method dispatch, for a given global method `mproperty`
239 # returns the most specific local method in the class corresponding to `vtable`
240 private fun method_dispatch
(mproperty
: MMethod, vtable
: VTable, recv
: Instance): MMethodDef
242 var position
= recv
.mtype
.as(MClassType).mclass
.get_position_methods
(mproperty
.intro_mclassdef
.mclass
)
244 return method_dispatch_sst
(vtable
.internal_vtable
, mproperty
.offset
+ position
)
246 return method_dispatch_ph
(vtable
.internal_vtable
, vtable
.mask
,
247 mproperty
.intro_mclassdef
.mclass
.vtable
.id
, mproperty
.offset
)
251 # Execute a method dispatch with perfect hashing and return the appropriate `MMethodDef`
252 # * `vtable` Pointer to the internal virtual table of the class
253 # * `mask` Perfect hashing mask of the receiver class
254 # * `id` Identifier of the class which introduce the method
255 # * `offset` Relative offset of the method from the beginning of the block
256 fun method_dispatch_ph
(vtable
: Pointer, mask
: Int, id
: Int, offset
: Int): MMethodDef `{
257 // Perfect hashing position
259 long unsigned int *pointer = (long unsigned int*)(((long int *)vtable)[-hv]);
261 // pointer+2 is the position where methods are
262 // Add the offset of property and get the method implementation
263 MMethodDef propdef = (MMethodDef)*(pointer + 2 + offset);
268 # Execute a method dispatch with direct access and return the appropriate `MMethodDef`
269 # * `vtable` Pointer to the internal virtual table of the class
270 # * `absolute_offset` Absolute offset from the beginning of the virtual table
271 fun method_dispatch_sst
(vtable
: Pointer, absolute_offset
: Int): MMethodDef `{
272 // pointer+2 is the position where methods are
273 // Add the offset of property and get the method implementation
274 MMethodDef propdef = (MMethodDef)((long int *)vtable)[absolute_offset];
279 # Return the value of the attribute `mproperty` for the object `recv`
280 redef fun read_attribute
(mproperty
: MAttribute, recv
: Instance): Instance
282 assert recv
isa MutableInstance
285 var position
= recv
.mtype
.as(MClassType).mclass
.get_position_attributes
(mproperty
.intro_mclassdef
.mclass
)
287 # if this attribute class has an unique position for this receiver, then use direct access
288 i
= read_attribute_sst
(recv
.internal_attributes
, position
+ mproperty
.offset
)
290 # Otherwise, read the attribute value with perfect hashing
291 var id
= mproperty
.intro_mclassdef
.mclass
.vtable
.id
293 i
= read_attribute_ph
(recv
.internal_attributes
, recv
.vtable
.internal_vtable
,
294 recv
.vtable
.mask
, id
, mproperty
.offset
)
297 # If we get a `MInit` value, throw an error
298 if i
== initialization_value
then
299 fatal
("Uninitialized attribute {mproperty.name}")
306 # Return the attribute value in `instance` with a sequence of perfect_hashing
307 # * `instance` is the attributes array of the receiver
308 # * `vtable` is the pointer to the virtual table of the class (of the receiver)
309 # * `mask` is the perfect hashing mask of the class
310 # * `id` is the identifier of the class
311 # * `offset` is the relative offset of this attribute
312 fun read_attribute_ph
(instance
: Pointer, vtable
: Pointer, mask
: Int, id
: Int, offset
: Int): Instance `{
313 // Perfect hashing position
315 long unsigned int *pointer = (long unsigned int*)(((long int *)vtable)[-hv]);
317 // pointer+1 is the position where the delta of the class is
318 int absolute_offset = *(pointer + 1);
320 Instance res = ((Instance *)instance)[absolute_offset + offset];
325 # Return the attribute value in `instance` with a direct access (SST)
326 # * `instance` is the attributes array of the receiver
327 # * `offset` is the absolute offset of this attribute
328 fun read_attribute_sst
(instance
: Pointer, offset
: Int): Instance `{
329 /* We can make a direct access to the attribute value
330 because this attribute is always at the same position
331 for the class of this receiver */
332 Instance res = ((Instance *)instance)[offset];
337 # Replace in `recv` the value of the attribute `mproperty` by `value`
338 redef fun write_attribute
(mproperty
: MAttribute, recv
: Instance, value
: Instance)
340 assert recv
isa MutableInstance
342 # Replace the old value of mproperty in recv
343 var position
= recv
.mtype
.as(MClassType).mclass
.get_position_attributes
(mproperty
.intro_mclassdef
.mclass
)
344 if position
> -1 then
345 # if this attribute class has an unique position for this receiver, then use direct access
346 write_attribute_sst
(recv
.internal_attributes
, position
+ mproperty
.offset
, value
)
348 # Otherwise, use perfect hashing to replace the old value
349 var id
= mproperty
.intro_mclassdef
.mclass
.vtable
.id
351 write_attribute_ph
(recv
.internal_attributes
, recv
.vtable
.internal_vtable
,
352 recv
.vtable
.mask
, id
, mproperty
.offset
, value
)
356 # Replace the value of an attribute in an instance
357 # * `instance` is the attributes array of the receiver
358 # * `vtable` is the pointer to the virtual table of the class (of the receiver)
359 # * `mask` is the perfect hashing mask of the class
360 # * `id` is the identifier of the class
361 # * `offset` is the relative offset of this attribute
362 # * `value` is the new value for this attribute
363 fun write_attribute_ph
(instance
: Pointer, vtable
: Pointer, mask
: Int, id
: Int, offset
: Int, value
: Instance) `{
364 // Perfect hashing position
366 long unsigned int *pointer = (long unsigned int*)(((long int *)vtable)[-hv]);
368 // pointer+1 is the position where the delta of the class is
369 int absolute_offset = *(pointer + 1);
371 ((Instance *)instance)[absolute_offset + offset] = value;
372 Instance_incr_ref(value);
375 # Replace the value of an attribute in an instance with direct access
376 # * `instance` is the attributes array of the receiver
377 # * `offset` is the absolute offset of this attribute
378 # * `value` is the new value for this attribute
379 fun write_attribute_sst
(instance
: Pointer, offset
: Int, value
: Instance) `{
380 // Direct access to the position with the absolute offset
381 ((Instance *)instance)[offset] = value;
382 Instance_incr_ref(value);
385 # Is the attribute `mproperty` initialized in the instance `recv`?
386 redef fun isset_attribute
(mproperty
: MAttribute, recv
: Instance): Bool
388 assert recv
isa MutableInstance
390 # Read the attribute value with internal perfect hashing read
391 # because we do not want to throw an error if the value is `initialization_value`
392 var id
= mproperty
.intro_mclassdef
.mclass
.vtable
.id
394 var i
= read_attribute_ph
(recv
.internal_attributes
, recv
.vtable
.internal_vtable
,
395 recv
.vtable
.mask
, id
, mproperty
.offset
)
397 return i
!= initialization_value
402 # A reference to the virtual table of this class
403 var vtable
: nullable VTable
405 # True when the class is effectively loaded by the vm, false otherwise
406 var loaded
: Bool = false
408 # Indicate this class was partially loaded (it only has its identifier allocated)
409 var abstract_loaded
: Bool = false
411 # Color for Cohen subtyping test : the absolute position of the id
412 # of this class in virtual tables
415 # For superclasses which have a non-invariant position, keep their position in attribute table
416 var positions_attributes
: HashMap[MClass, Int] = new HashMap[MClass, Int]
418 # For superclasses which have a non-invariant position, keep their position in virtual table
419 var positions_methods
: HashMap[MClass, Int] = new HashMap[MClass, Int]
421 # The position of the class' block in virtual table,
422 # the position is set to -1 when the invariant position is no longer satisfied
423 var position_attributes
: Int
425 # The position of the class' block in attribute table
426 # the position is set to -1 when the invariant position is no longer satisfied
427 var position_methods
: Int
429 # The chosen prefix for this class.
430 # The prefix is the direct superclass which has the most properties,
431 # this class will stay at its usual position in virtual table and attribute table
432 var prefix
: nullable MClass
434 # The linear extension of all superclasses with the prefix rule
435 var ordering
: Array[MClass]
437 # The `MAttribute` this class introduced
438 var intro_mattributes
= new Array[MAttribute]
440 # The `MMethod` this class introduced
441 var intro_mmethods
= new Array[MMethod]
443 # All `MAttribute` this class contains
444 var mattributes
= new Array[MAttribute]
446 # All `MMethod` this class contains
447 var mmethods
= new Array[MMethod]
449 # Allocates a VTable for this class and gives it an id
450 # * `vm` The currently executed VirtualMachine
451 # * `explicit` Indicate if this class was directly instantiated (i.e. not indirectly loaded)
452 private fun make_vt
(vm
: VirtualMachine, explicit
: Bool)
454 # `ordering` contains the order of superclasses for virtual tables
455 ordering
= superclasses_ordering
(vm
)
456 ordering
.remove
(self)
458 var ids
= new Array[Int]
459 var nb_methods
= new Array[Int]
460 var nb_attributes
= new Array[Int]
462 # Absolute offset of attribute from the beginning of the attributes table
463 var offset_attributes
= 0
465 # Absolute offset of method from the beginning of the methods table,
466 # is initialize to 3 because the first position is empty in the virtual table
467 # and the second and third are respectively class id and delta
468 var offset_methods
= 3
471 var prefix_index
= ordering
.index_of
(prefix
.as(not null))
472 for i
in [0..ordering
.length
[ do
475 # Get the number of introduced methods and attributes for this class
476 var methods
= parent
.intro_mmethods
.length
477 var attributes
= parent
.intro_mattributes
.length
479 # Updates `mmethods` and `mattributes`
480 mmethods
.add_all
(parent
.intro_mmethods
)
481 mattributes
.add_all
(parent
.intro_mattributes
)
483 ids
.push
(parent
.vtable
.id
)
484 nb_methods
.push
(methods
)
485 nb_attributes
.push
(attributes
)
487 # If the class is in the suffix part of the order
488 if i
> prefix_index
then
489 moved_class_attributes
(vm
, ordering
[i
], offset_attributes
)
490 moved_class_methods
(vm
, ordering
[i
], offset_methods
)
493 offset_attributes
+= attributes
494 offset_methods
+= methods
495 offset_methods
+= 2 # Because each block starts with an id and the delta
498 # Update the positions of the class
499 update_positions
(offset_attributes
, offset_methods
)
503 # Compute the identifier with Perfect Hashing
504 compute_identifier
(vm
, ids
, offset_methods
)
506 # Update caches and offsets of methods and attributes for this class
507 # If the loading was explicit, the virtual table will be allocated and filled
508 set_offsets
(vm
, explicit
)
511 # Just init the C-pointer to NULL to avoid errors
512 vtable
.internal_vtable
= vm
.memory_manager
.null_ptr
516 # Allocate a unique identifier to the class with perfect hashing
517 # * `vm` The currently executed VirtualMachine
518 # * `ids` Array of superclasses identifiers
519 # * `offset_methods : Offset from the beginning of the table of the group of methods
520 private fun compute_identifier
(vm
: VirtualMachine, ids
: Array[Int], offset_methods
: Int)
523 var idc
= new Array[Int]
525 # Give an identifier to the class and put it inside the virtual table
526 vtable
.mask
= vm
.ph
.pnand
(ids
, 1, idc
) - 1
528 vtable
.classname
= name
530 # Set the color for subtyping tests in SST of this class
531 color
= offset_methods
- 2
533 # Indicate the class has its identifier computed
534 abstract_loaded
= true
537 # Update the positions of this class
538 # * `offset_attributes` The offset of the block of attributes of this class
539 # * `offset_methods` The offset of the block of methods of this class
540 private fun update_positions
(offset_attributes
: Int, offset_methods
: Int)
542 # Recopy the position tables of the prefix in `self`
543 for key
, value
in prefix
.positions_methods
do
544 positions_methods
[key
] = value
547 for key
, value
in prefix
.positions_attributes
do
548 positions_attributes
[key
] = value
551 # Save the offsets of self class
552 position_attributes
= offset_attributes
553 position_methods
= offset_methods
556 # Set the offsets for the properties introduced by `self` class
557 # * `vm` The currently executed VirtualMachine
558 # * `explicit` Indicate if this class was explicitly loaded
559 private fun set_offsets
(vm
: VirtualMachine, explicit
: Bool)
561 # Fixing offsets for self attributes and methods
562 var relative_offset_attr
= 0
563 var relative_offset_meth
= 0
565 # Update `intro_mmethods` and `intro_mattributes`
566 # For each MClassdef this MClass has
567 for classdef
in mclassdefs
do
568 # For each property this MClassdef introduce
569 for p
in classdef
.intro_mproperties
do
570 # Collect properties and fixing offsets
571 if p
isa MMethod then
572 p
.offset
= relative_offset_meth
573 relative_offset_meth
+= 1
575 intro_mmethods
.add
(p
)
577 if p
isa MAttribute then
578 p
.offset
= relative_offset_attr
579 relative_offset_attr
+= 1
581 intro_mattributes
.add
(p
)
586 # Updates caches with introduced attributes of `self` class
587 mattributes
.add_all
(intro_mattributes
)
588 mmethods
.add_all
(intro_mmethods
)
590 if explicit
then allocate_vtable
(vm
)
593 # Allocate a single vtable
594 # * `vm` The currently executed VirtualMachine
595 private fun allocate_vtable
(vm
: VirtualMachine)
597 var ids
= new Array[Int]
598 var nb_methods_total
= new Array[Int]
599 var nb_attributes_total
= new Array[Int]
601 for cl
in ordering
do
602 ids
.add
(cl
.vtable
.id
)
603 nb_methods_total
.add
(cl
.intro_mmethods
.length
)
604 nb_attributes_total
.add
(cl
.intro_mattributes
.length
)
607 # Calculate the delta to prepare object structure
608 var deltas
= calculate_delta
(nb_attributes_total
)
609 vtable
.internal_vtable
= vm
.memory_manager
.init_vtable
(ids
, nb_methods_total
, deltas
, vtable
.mask
)
611 # The virtual table now needs to be filled with pointer to methods
612 for cl
in ordering
do
613 fill_vtable
(vm
, vtable
.as(not null), cl
)
619 # Fill the vtable with local methods for `self` class
620 # * `vm` Current instance of the VirtualMachine
621 # * `table` the table of self class, will be filled with its methods
622 # * `cl` The class which introduced the methods
623 private fun fill_vtable
(vm
: VirtualMachine, table
: VTable, cl
: MClass)
625 var methods
= new Array[MMethodDef]
626 for m
in cl
.intro_mmethods
do
627 # `propdef` is the most specific implementation for this MMethod
628 var propdef
= m
.lookup_first_definition
(vm
.mainmodule
, self.intro
.bound_mtype
)
629 methods
.push
(propdef
)
632 # Call a method in C to put propdefs of self methods in the vtables
633 vm
.memory_manager
.put_methods
(vtable
.internal_vtable
, vtable
.mask
, cl
.vtable
.id
, methods
)
636 # Computes delta for each class
637 # A delta represents the offset for this group of attributes in the object
638 # *`nb_attributes` : number of attributes for each class (classes are linearized from Object to current)
639 # * return deltas for each class
640 private fun calculate_delta
(nb_attributes
: Array[Int]): Array[Int]
642 var deltas
= new Array[Int]
645 for nb
in nb_attributes
do
653 # Order superclasses of self
654 # Return the order of superclasses in runtime structures of this class
655 private fun superclasses_ordering
(v
: VirtualMachine): Array[MClass]
657 var superclasses
= new Array[MClass]
659 # Add all superclasses of `self`
660 superclasses
.add_all
(self.in_hierarchy
(v
.mainmodule
).greaters
)
662 var res
= new Array[MClass]
663 if superclasses
.length
> 1 then
665 var ordering
= self.dfs
(v
, res
)
669 # There is no super-class, self is Object
675 # A kind of Depth-First-Search for superclasses ordering
676 # *`v` : the current executed instance of VirtualMachine
677 # * `res` : Result Array, ie current superclasses ordering
678 private fun dfs
(v
: VirtualMachine, res
: Array[MClass]): Array[MClass]
680 # Add this class at the beginning
683 var direct_parents
= self.in_hierarchy
(v
.mainmodule
).direct_greaters
.to_a
685 if direct_parents
.length
> 1 then
686 # Prefix represents the class which has the most properties
687 # we try to choose it in first to reduce the number of potential recompilations
690 for cl
in direct_parents
do
691 # If we never have visited this class
692 if not res
.has
(cl
) then
693 var properties_length
= cl
.mmethods
.length
+ cl
.mattributes
.length
694 if properties_length
> max
then
695 max
= properties_length
701 if prefix
!= null then
702 if self.prefix
== null then self.prefix
= prefix
704 # Add the prefix class ordering at the beginning of our sequence
705 var prefix_res
= new Array[MClass]
706 prefix_res
= prefix
.dfs
(v
, prefix_res
)
708 # Then we recurse on other classes
709 for cl
in direct_parents
do
711 res
= new Array[MClass]
715 if not prefix_res
.has
(cl_res
) then prefix_res
.push
(cl_res
)
724 if direct_parents
.length
> 0 then
725 if prefix
== null then prefix
= direct_parents
.first
727 res
= direct_parents
.first
.dfs
(v
, res
)
731 if not res
.has
(self) then res
.push
(self)
736 # This method is called when `current_class` class is moved in virtual table of `self`
737 # *`vm` Running instance of the virtual machine
738 # *`current_class` The class which was moved in `self` structures
739 # *`offset` The offset of block of methods of `current_class` in `self`
740 fun moved_class_methods
(vm
: VirtualMachine, current_class
: MClass, offset
: Int)
742 # `current_class` was moved in `self` method table
743 if current_class
.position_methods
> 0 then
744 # The invariant position is no longer satisfied
745 current_class
.positions_methods
[current_class
] = current_class
.position_methods
746 current_class
.position_methods
= - current_class
.position_methods
748 # The class has already several positions and an update is needed
749 current_class
.positions_methods
[current_class
] = -current_class
.positions_methods
[current_class
]
751 for sub
in ordering
do
752 if sub
== current_class
then continue
754 var super_id
= current_class
.vtable
.id
755 var mask
= sub
.vtable
.mask
758 if vm
.inter_is_subtype_ph
(super_id
, mask
, sub
.vtable
.internal_vtable
) then
759 if not sub
.positions_methods
.has_key
(current_class
) then
760 sub
.positions_methods
[current_class
] = current_class
.position_methods
762 var old_position
= sub
.positions_methods
[current_class
]
763 if old_position
> 0 then
764 # Indicate this class can not used anymore single inheritance implementation
765 sub
.positions_methods
[current_class
] = - old_position
772 # Save the position of `current_class` in `self`
773 positions_methods
[current_class
] = offset
776 # This method is called when `current_class` class is moved in attribute table of `self`
777 # *`vm` Running instance of the virtual machine
778 # *`current_class` The class which was moved in `self` structures
779 # *`offset` The offset of block of attributes of `current_class` in `self`
780 fun moved_class_attributes
(vm
: VirtualMachine, current_class
: MClass, offset
: Int)
782 # `current_class` was moved in `self` attribute table
783 if not current_class
.positions_attributes
.has_key
(current_class
) then
784 # The invariant position is no longer satisfied
785 current_class
.positions_attributes
[current_class
] = current_class
.position_attributes
786 current_class
.position_attributes
= - current_class
.position_attributes
788 # The class has already several positions and an update is needed
789 current_class
.positions_attributes
[current_class
] = - current_class
.positions_attributes
[current_class
]
791 for sub
in ordering
do
792 if sub
== current_class
then continue
794 var super_id
= current_class
.vtable
.id
795 var mask
= sub
.vtable
.mask
798 if vm
.inter_is_subtype_ph
(super_id
, mask
, sub
.vtable
.internal_vtable
) then
799 if not sub
.positions_methods
.has_key
(current_class
) then
800 sub
.positions_attributes
[current_class
] = current_class
.position_attributes
802 var old_position
= sub
.positions_attributes
[current_class
]
803 if old_position
> 0 then
804 # Indicate this class can not used anymore single inheritance implementation
805 sub
.positions_attributes
[current_class
] = - old_position
812 # Save the position of `current_class` in `self`
813 positions_attributes
[current_class
] = offset
816 # Return the position of the method's block of class `cl` in `self` if `cl` has an invariant position in self,
817 # Otherwise return a negative position
818 fun get_position_methods
(cl
: MClass): Int
820 # The class has an invariant position in all subclasses
821 if cl
.position_methods
> 0 then return cl
.position_methods
823 # The position has an invariant position for this class and its subclasses only
824 if positions_methods
.has_key
(cl
) then
825 var pos
= positions_methods
[cl
]
826 if pos
> 0 then return pos
830 # No invariant position at all, the caller must use a multiple inheritance implementation
834 # Return the position of the attribute's block of class `cl` in `self` if `cl` has an invariant position in self,
835 # Otherwise return a negative position
836 fun get_position_attributes
(cl
: MClass): Int
838 # The class has an invariant position in all subclasses
839 if cl
.position_attributes
> 0 then return cl
.position_attributes
841 # The position has an invariant position for this class and its subclasses only
842 if positions_attributes
.has_key
(cl
) then
843 var pos
= positions_attributes
[cl
]
844 if pos
> 0 then return pos
848 # No invariant position at all, the caller must use a multiple inheritance implementation
853 redef class MProperty
854 # Relative offset of this in the runtime instance
855 # (beginning of the block of its introducing class for attributes or methods)
859 redef class MAttribute
860 # Relative offset of this attribute in the runtime instance
861 # (beginning of the block of its introducing class)
862 redef var offset
: Int
866 # Relative offset of this method in the virtual table (from the beginning of the block)
867 redef var offset
: Int
870 # Redef MutableInstance to improve implementation of attributes in objects
871 redef class MutableInstance
873 # C-array to store pointers to attributes of this Object
874 var internal_attributes
: Pointer
877 # Redef to associate an `Instance` to its `VTable`
880 # Associate a runtime instance to its virtual table which contains methods, types etc.
881 var vtable
: nullable VTable
884 # Is the type of the initial value inside attributes
888 redef var model
: Model
890 redef fun to_s
do return "InitType"
891 redef fun as_nullable
do return self
892 redef fun need_anchor
do return false
893 redef fun resolve_for
(mtype
, anchor
, mmodule
, cleanup_virtual
) do return self
894 redef fun can_resolve_for
(mtype
, anchor
, mmodule
) do return true
896 redef fun collect_mclassdefs
(mmodule
) do return new HashSet[MClassDef]
898 redef fun collect_mclasses
(mmodule
) do return new HashSet[MClass]
900 redef fun collect_mtypes
(mmodule
) do return new HashSet[MClassType]
903 # A VTable contains the virtual method table for the dispatch
904 # and informations to perform subtyping tests
906 # The mask to perform perfect hashing
907 var mask
: Int is noinit
909 # Unique identifier given by perfect hashing
910 var id
: Int is noinit
912 # Pointer to the c-allocated area, represents the virtual table
913 var internal_vtable
: Pointer is noinit
915 # The short classname of this class
916 var classname
: String is noinit
919 # Handle memory, used for allocate virtual table and associated structures
922 # Allocate and fill a virtual table
923 fun init_vtable
(ids
: Array[Int], nb_methods
: Array[Int], nb_attributes
: Array[Int], mask
: Int): Pointer
925 # Allocate in C current virtual table
926 var res
= intern_init_vtable
(ids
, nb_methods
, nb_attributes
, mask
)
931 # Construct virtual tables with a bi-dimensional layout
932 private fun intern_init_vtable
(ids
: Array[Int], nb_methods
: Array[Int], deltas
: Array[Int], mask
: Int): Pointer
933 import Array[Int].length
, Array[Int].[] `{
935 // Allocate and fill current virtual table
937 int total_size = 0; // total size of this virtual table
938 int nb_classes = Array_of_Int_length(nb_methods);
939 for(i = 0; i<nb_classes; i++) {
940 /* - One for each method of this class
941 * - One for the delta (offset of this group of attributes in objects)
944 total_size += Array_of_Int__index(nb_methods, i);
948 // Add the size of the perfect hashtable (mask +1)
949 // Add one because we start to fill the vtable at position 1 (0 is the init position)
950 total_size += mask+2;
951 long unsigned int* vtable = malloc(sizeof(long unsigned int)*total_size);
953 // Initialisation to the first position of the virtual table (ie : Object)
954 long unsigned int *init = vtable + mask + 2;
955 for(i=0; i<total_size; i++)
956 vtable[i] = (long unsigned int)init;
958 // Set the virtual table to its position 0
959 // ie: after the hashtable
960 vtable = vtable + mask + 1;
962 int current_size = 1;
963 for(i = 0; i < nb_classes; i++) {
965 vtable[hv] contains a pointer to the group of introduced methods
966 For each superclasse we have in virtual table :
967 (id | delta | introduced methods)
969 int hv = mask & Array_of_Int__index(ids, i);
971 vtable[current_size] = Array_of_Int__index(ids, i);
972 vtable[current_size + 1] = Array_of_Int__index(deltas, i);
973 vtable[-hv] = (long unsigned int)&(vtable[current_size]);
976 current_size += Array_of_Int__index(nb_methods, i);
982 # Put implementation of methods of a class in `vtable`
983 # * `vtable` : Pointer to the C-virtual table
984 # * `mask` : perfect-hashing mask of the class corresponding to the vtable
985 # * `id` : id of the target class
986 # * `methods` : array of MMethodDef of the target class
987 fun put_methods
(vtable
: Pointer, mask
: Int, id
: Int, methods
: Array[MMethodDef])
988 import Array[MMethodDef].length
, Array[MMethodDef].[] `{
990 // Get the area to fill with methods by a sequence of perfect hashing
992 long unsigned int *pointer = (long unsigned int*)(((long unsigned int *)vtable)[-hv]);
994 // pointer+2 is the beginning of the area for methods implementation
995 int length = Array_of_MMethodDef_length(methods);
996 long unsigned int *area = (pointer + 2);
999 for(i=0; i<length; i++)
1001 MMethodDef method = Array_of_MMethodDef__index(methods, i);
1002 area[i] = (long unsigned int)method;
1003 MMethodDef_incr_ref(method);
1007 # Return a NULL pointer, used to initialize virtual tables
1008 private fun null_ptr
: Pointer `{