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
204 if mclass
.abstract_loaded
then
205 mclass
.allocate_vtable
(self)
207 mclass
.make_vt
(self, true)
211 # Recursively load superclasses.
212 private fun load_supers
(mclass
: MClass)
214 for parent
in mclass
.in_hierarchy
(mainmodule
).direct_greaters
do
215 load_class_indirect
(parent
)
219 # This method is called to handle an implicitly loaded class,
220 # i.e. a superclass of an explicitly loaded class
221 # A class loaded implicitly will not be fully allocated
222 fun load_class_indirect
(mclass
: MClass)
224 # It the class was already implicitly loaded
225 if mclass
.abstract_loaded
then return
229 mclass
.make_vt
(self, false)
232 # Execute `mproperty` for a `args` (where `args[0]` is the receiver).
233 redef fun send
(mproperty
: MMethod, args
: Array[Instance]): nullable Instance
235 var recv
= args
.first
236 var mtype
= recv
.mtype
237 var ret
= send_commons
(mproperty
, args
, mtype
)
238 if ret
!= null then return ret
240 var propdef
= method_dispatch
(mproperty
, recv
.vtable
.as(not null), recv
)
242 return self.call
(propdef
, args
)
245 # Method dispatch, for a given global method `mproperty`
246 # returns the most specific local method in the class corresponding to `vtable`
247 private fun method_dispatch
(mproperty
: MMethod, vtable
: VTable, recv
: Instance): MMethodDef
249 var position
= recv
.mtype
.as(MClassType).mclass
.get_position_methods
(mproperty
.intro_mclassdef
.mclass
)
251 return method_dispatch_sst
(vtable
.internal_vtable
, mproperty
.offset
+ position
)
253 return method_dispatch_ph
(vtable
.internal_vtable
, vtable
.mask
,
254 mproperty
.intro_mclassdef
.mclass
.vtable
.id
, mproperty
.offset
)
258 # Execute a method dispatch with perfect hashing and return the appropriate `MMethodDef`
259 # * `vtable` Pointer to the internal virtual table of the class
260 # * `mask` Perfect hashing mask of the receiver class
261 # * `id` Identifier of the class which introduce the method
262 # * `offset` Relative offset of the method from the beginning of the block
263 fun method_dispatch_ph
(vtable
: Pointer, mask
: Int, id
: Int, offset
: Int): MMethodDef `{
264 // Perfect hashing position
266 long unsigned int *pointer = (long unsigned int*)(((long int *)vtable)[-hv]);
268 // pointer+2 is the position where methods are
269 // Add the offset of property and get the method implementation
270 MMethodDef propdef = (MMethodDef)*(pointer + 2 + offset);
275 # Execute a method dispatch with direct access and return the appropriate `MMethodDef`
276 # * `vtable` Pointer to the internal virtual table of the class
277 # * `absolute_offset` Absolute offset from the beginning of the virtual table
278 fun method_dispatch_sst
(vtable
: Pointer, absolute_offset
: Int): MMethodDef `{
279 // pointer+2 is the position where methods are
280 // Add the offset of property and get the method implementation
281 MMethodDef propdef = (MMethodDef)((long int *)vtable)[absolute_offset];
286 # Return the value of the attribute `mproperty` for the object `recv`
287 redef fun read_attribute
(mproperty
: MAttribute, recv
: Instance): Instance
289 assert recv
isa MutableInstance
292 var position
= recv
.mtype
.as(MClassType).mclass
.get_position_attributes
(mproperty
.intro_mclassdef
.mclass
)
294 # if this attribute class has an unique position for this receiver, then use direct access
295 i
= read_attribute_sst
(recv
.internal_attributes
, position
+ mproperty
.offset
)
297 # Otherwise, read the attribute value with perfect hashing
298 var id
= mproperty
.intro_mclassdef
.mclass
.vtable
.id
300 i
= read_attribute_ph
(recv
.internal_attributes
, recv
.vtable
.internal_vtable
,
301 recv
.vtable
.mask
, id
, mproperty
.offset
)
304 # If we get a `MInit` value, throw an error
305 if i
== initialization_value
then
306 fatal
("Uninitialized attribute {mproperty.name}")
313 # Return the attribute value in `instance` with a sequence of perfect_hashing
314 # * `instance` is the attributes array of the receiver
315 # * `vtable` is the pointer to the virtual table of the class (of the receiver)
316 # * `mask` is the perfect hashing mask of the class
317 # * `id` is the identifier of the class
318 # * `offset` is the relative offset of this attribute
319 fun read_attribute_ph
(instance
: Pointer, vtable
: Pointer, mask
: Int, id
: Int, offset
: Int): Instance `{
320 // Perfect hashing position
322 long unsigned int *pointer = (long unsigned int*)(((long int *)vtable)[-hv]);
324 // pointer+1 is the position where the delta of the class is
325 int absolute_offset = *(pointer + 1);
327 Instance res = ((Instance *)instance)[absolute_offset + offset];
332 # Return the attribute value in `instance` with a direct access (SST)
333 # * `instance` is the attributes array of the receiver
334 # * `offset` is the absolute offset of this attribute
335 fun read_attribute_sst
(instance
: Pointer, offset
: Int): Instance `{
336 /* We can make a direct access to the attribute value
337 because this attribute is always at the same position
338 for the class of this receiver */
339 Instance res = ((Instance *)instance)[offset];
344 # Replace in `recv` the value of the attribute `mproperty` by `value`
345 redef fun write_attribute
(mproperty
: MAttribute, recv
: Instance, value
: Instance)
347 assert recv
isa MutableInstance
349 # Replace the old value of mproperty in recv
350 var position
= recv
.mtype
.as(MClassType).mclass
.get_position_attributes
(mproperty
.intro_mclassdef
.mclass
)
351 if position
> -1 then
352 # if this attribute class has an unique position for this receiver, then use direct access
353 write_attribute_sst
(recv
.internal_attributes
, position
+ mproperty
.offset
, value
)
355 # Otherwise, use perfect hashing to replace the old value
356 var id
= mproperty
.intro_mclassdef
.mclass
.vtable
.id
358 write_attribute_ph
(recv
.internal_attributes
, recv
.vtable
.internal_vtable
,
359 recv
.vtable
.mask
, id
, mproperty
.offset
, value
)
363 # Replace the value of an attribute in an instance
364 # * `instance` is the attributes array of the receiver
365 # * `vtable` is the pointer to the virtual table of the class (of the receiver)
366 # * `mask` is the perfect hashing mask of the class
367 # * `id` is the identifier of the class
368 # * `offset` is the relative offset of this attribute
369 # * `value` is the new value for this attribute
370 fun write_attribute_ph
(instance
: Pointer, vtable
: Pointer, mask
: Int, id
: Int, offset
: Int, value
: Instance) `{
371 // Perfect hashing position
373 long unsigned int *pointer = (long unsigned int*)(((long int *)vtable)[-hv]);
375 // pointer+1 is the position where the delta of the class is
376 int absolute_offset = *(pointer + 1);
378 ((Instance *)instance)[absolute_offset + offset] = value;
379 Instance_incr_ref(value);
382 # Replace the value of an attribute in an instance with direct access
383 # * `instance` is the attributes array of the receiver
384 # * `offset` is the absolute offset of this attribute
385 # * `value` is the new value for this attribute
386 fun write_attribute_sst
(instance
: Pointer, offset
: Int, value
: Instance) `{
387 // Direct access to the position with the absolute offset
388 ((Instance *)instance)[offset] = value;
389 Instance_incr_ref(value);
392 # Is the attribute `mproperty` initialized in the instance `recv`?
393 redef fun isset_attribute
(mproperty
: MAttribute, recv
: Instance): Bool
395 assert recv
isa MutableInstance
397 # Read the attribute value with internal perfect hashing read
398 # because we do not want to throw an error if the value is `initialization_value`
399 var id
= mproperty
.intro_mclassdef
.mclass
.vtable
.id
401 var i
= read_attribute_ph
(recv
.internal_attributes
, recv
.vtable
.internal_vtable
,
402 recv
.vtable
.mask
, id
, mproperty
.offset
)
404 return i
!= initialization_value
409 # A reference to the virtual table of this class
410 var vtable
: nullable VTable
412 # True when the class is effectively loaded by the vm, false otherwise
413 var loaded
: Bool = false
415 # Indicate this class was partially loaded (it only has its identifier allocated)
416 var abstract_loaded
: Bool = false
418 # Color for Cohen subtyping test : the absolute position of the id
419 # of this class in virtual tables
422 # For superclasses which have a non-invariant position, keep their position in attribute table
423 var positions_attributes
: HashMap[MClass, Int] = new HashMap[MClass, Int]
425 # For superclasses which have a non-invariant position, keep their position in virtual table
426 var positions_methods
: HashMap[MClass, Int] = new HashMap[MClass, Int]
428 # The position of the class' block in virtual table,
429 # the position is set to -1 when the invariant position is no longer satisfied
430 var position_attributes
: Int
432 # The position of the class' block in attribute table
433 # the position is set to -1 when the invariant position is no longer satisfied
434 var position_methods
: Int
436 # The chosen prefix for this class.
437 # The prefix is the direct superclass which has the most properties,
438 # this class will stay at its usual position in virtual table and attribute table
439 var prefix
: nullable MClass
441 # The linear extension of all superclasses with the prefix rule
442 var ordering
: Array[MClass]
444 # The `MAttribute` this class introduced
445 var intro_mattributes
= new Array[MAttribute]
447 # The `MMethod` this class introduced
448 var intro_mmethods
= new Array[MMethod]
450 # All `MAttribute` this class contains
451 var mattributes
= new Array[MAttribute]
453 # All `MMethod` this class contains
454 var mmethods
= new Array[MMethod]
456 # Allocates a VTable for this class and gives it an id
457 # * `vm` The currently executed VirtualMachine
458 # * `explicit` Indicate if this class was directly instantiated (i.e. not indirectly loaded)
459 private fun make_vt
(vm
: VirtualMachine, explicit
: Bool)
461 # `ordering` contains the order of superclasses for virtual tables
462 ordering
= superclasses_ordering
(vm
)
463 ordering
.remove
(self)
465 var ids
= new Array[Int]
466 var nb_methods
= new Array[Int]
467 var nb_attributes
= new Array[Int]
469 # Absolute offset of attribute from the beginning of the attributes table
470 var offset_attributes
= 0
472 # Absolute offset of method from the beginning of the methods table,
473 # is initialize to 3 because the first position is empty in the virtual table
474 # and the second and third are respectively class id and delta
475 var offset_methods
= 3
478 var prefix_index
= ordering
.index_of
(prefix
.as(not null))
479 for i
in [0..ordering
.length
[ do
482 # Get the number of introduced methods and attributes for this class
483 var methods
= parent
.intro_mmethods
.length
484 var attributes
= parent
.intro_mattributes
.length
486 # Updates `mmethods` and `mattributes`
487 mmethods
.add_all
(parent
.intro_mmethods
)
488 mattributes
.add_all
(parent
.intro_mattributes
)
490 ids
.push
(parent
.vtable
.id
)
491 nb_methods
.push
(methods
)
492 nb_attributes
.push
(attributes
)
494 # If the class is in the suffix part of the order
495 if i
> prefix_index
then
496 moved_class_attributes
(vm
, ordering
[i
], offset_attributes
)
497 moved_class_methods
(vm
, ordering
[i
], offset_methods
)
500 offset_attributes
+= attributes
501 offset_methods
+= methods
502 offset_methods
+= 2 # Because each block starts with an id and the delta
505 # Update the positions of the class
506 update_positions
(offset_attributes
, offset_methods
)
510 # Compute the identifier with Perfect Hashing
511 compute_identifier
(vm
, ids
, offset_methods
)
513 # Update caches and offsets of methods and attributes for this class
514 # If the loading was explicit, the virtual table will be allocated and filled
515 set_offsets
(vm
, explicit
)
518 # Just init the C-pointer to NULL to avoid errors
519 vtable
.internal_vtable
= vm
.memory_manager
.null_ptr
523 # Allocate a unique identifier to the class with perfect hashing
524 # * `vm` The currently executed VirtualMachine
525 # * `ids` Array of superclasses identifiers
526 # * `offset_methods : Offset from the beginning of the table of the group of methods
527 private fun compute_identifier
(vm
: VirtualMachine, ids
: Array[Int], offset_methods
: Int)
530 var idc
= new Array[Int]
532 # Give an identifier to the class and put it inside the virtual table
533 vtable
.mask
= vm
.ph
.pnand
(ids
, 1, idc
) - 1
535 vtable
.classname
= name
537 # Set the color for subtyping tests in SST of this class
538 color
= offset_methods
- 2
540 # Indicate the class has its identifier computed
541 abstract_loaded
= true
544 # Update the positions of this class
545 # * `offset_attributes` The offset of the block of attributes of this class
546 # * `offset_methods` The offset of the block of methods of this class
547 private fun update_positions
(offset_attributes
: Int, offset_methods
: Int)
549 # Recopy the position tables of the prefix in `self`
550 for key
, value
in prefix
.positions_methods
do
551 positions_methods
[key
] = value
554 for key
, value
in prefix
.positions_attributes
do
555 positions_attributes
[key
] = value
558 # Save the offsets of self class
559 position_attributes
= offset_attributes
560 position_methods
= offset_methods
563 # Set the offsets for the properties introduced by `self` class
564 # * `vm` The currently executed VirtualMachine
565 # * `explicit` Indicate if this class was explicitly loaded
566 private fun set_offsets
(vm
: VirtualMachine, explicit
: Bool)
568 # Fixing offsets for self attributes and methods
569 var relative_offset_attr
= 0
570 var relative_offset_meth
= 0
572 # Update `intro_mmethods` and `intro_mattributes`
573 # For each MClassdef this MClass has
574 for classdef
in mclassdefs
do
575 # For each property this MClassdef introduce
576 for p
in classdef
.intro_mproperties
do
577 # Collect properties and fixing offsets
578 if p
isa MMethod then
579 p
.offset
= relative_offset_meth
580 relative_offset_meth
+= 1
582 intro_mmethods
.add
(p
)
584 if p
isa MAttribute then
585 p
.offset
= relative_offset_attr
586 relative_offset_attr
+= 1
588 intro_mattributes
.add
(p
)
593 # Updates caches with introduced attributes of `self` class
594 mattributes
.add_all
(intro_mattributes
)
595 mmethods
.add_all
(intro_mmethods
)
597 if explicit
then allocate_vtable
(vm
)
600 # Allocate a single vtable
601 # * `vm` The currently executed VirtualMachine
602 private fun allocate_vtable
(vm
: VirtualMachine)
604 var ids
= new Array[Int]
605 var nb_methods_total
= new Array[Int]
606 var nb_attributes_total
= new Array[Int]
608 for cl
in ordering
do
609 ids
.add
(cl
.vtable
.id
)
610 nb_methods_total
.add
(cl
.intro_mmethods
.length
)
611 nb_attributes_total
.add
(cl
.intro_mattributes
.length
)
614 # Calculate the delta to prepare object structure
615 var deltas
= calculate_delta
(nb_attributes_total
)
616 vtable
.internal_vtable
= vm
.memory_manager
.init_vtable
(ids
, nb_methods_total
, deltas
, vtable
.mask
)
618 # The virtual table now needs to be filled with pointer to methods
619 for cl
in ordering
do
620 fill_vtable
(vm
, vtable
.as(not null), cl
)
626 # Fill the vtable with local methods for `self` class
627 # * `vm` Current instance of the VirtualMachine
628 # * `table` the table of self class, will be filled with its methods
629 # * `cl` The class which introduced the methods
630 private fun fill_vtable
(vm
: VirtualMachine, table
: VTable, cl
: MClass)
632 var methods
= new Array[MMethodDef]
633 for m
in cl
.intro_mmethods
do
634 # `propdef` is the most specific implementation for this MMethod
635 var propdef
= m
.lookup_first_definition
(vm
.mainmodule
, self.intro
.bound_mtype
)
636 methods
.push
(propdef
)
639 # Call a method in C to put propdefs of self methods in the vtables
640 vm
.memory_manager
.put_methods
(vtable
.internal_vtable
, vtable
.mask
, cl
.vtable
.id
, methods
)
643 # Computes delta for each class
644 # A delta represents the offset for this group of attributes in the object
645 # *`nb_attributes` : number of attributes for each class (classes are linearized from Object to current)
646 # * return deltas for each class
647 private fun calculate_delta
(nb_attributes
: Array[Int]): Array[Int]
649 var deltas
= new Array[Int]
652 for nb
in nb_attributes
do
660 # Order superclasses of self
661 # Return the order of superclasses in runtime structures of this class
662 private fun superclasses_ordering
(v
: VirtualMachine): Array[MClass]
664 var superclasses
= new Array[MClass]
666 # Add all superclasses of `self`
667 superclasses
.add_all
(self.in_hierarchy
(v
.mainmodule
).greaters
)
669 var res
= new Array[MClass]
670 if superclasses
.length
> 1 then
672 var ordering
= self.dfs
(v
, res
)
676 # There is no super-class, self is Object
682 # A kind of Depth-First-Search for superclasses ordering
683 # *`v` : the current executed instance of VirtualMachine
684 # * `res` : Result Array, ie current superclasses ordering
685 private fun dfs
(v
: VirtualMachine, res
: Array[MClass]): Array[MClass]
687 # Add this class at the beginning
690 var direct_parents
= self.in_hierarchy
(v
.mainmodule
).direct_greaters
.to_a
692 if direct_parents
.length
> 1 then
693 # Prefix represents the class which has the most properties
694 # we try to choose it in first to reduce the number of potential recompilations
697 for cl
in direct_parents
do
698 # If we never have visited this class
699 if not res
.has
(cl
) then
700 var properties_length
= cl
.mmethods
.length
+ cl
.mattributes
.length
701 if properties_length
> max
then
702 max
= properties_length
708 if prefix
!= null then
709 if self.prefix
== null then self.prefix
= prefix
711 # Add the prefix class ordering at the beginning of our sequence
712 var prefix_res
= new Array[MClass]
713 prefix_res
= prefix
.dfs
(v
, prefix_res
)
715 # Then we recurse on other classes
716 for cl
in direct_parents
do
718 res
= new Array[MClass]
722 if not prefix_res
.has
(cl_res
) then prefix_res
.push
(cl_res
)
731 if direct_parents
.length
> 0 then
732 if prefix
== null then prefix
= direct_parents
.first
734 res
= direct_parents
.first
.dfs
(v
, res
)
738 if not res
.has
(self) then res
.push
(self)
743 # This method is called when `current_class` class is moved in virtual table of `self`
744 # *`vm` Running instance of the virtual machine
745 # *`current_class` The class which was moved in `self` structures
746 # *`offset` The offset of block of methods of `current_class` in `self`
747 fun moved_class_methods
(vm
: VirtualMachine, current_class
: MClass, offset
: Int)
749 # `current_class` was moved in `self` method table
750 if current_class
.position_methods
> 0 then
751 # The invariant position is no longer satisfied
752 current_class
.positions_methods
[current_class
] = current_class
.position_methods
753 current_class
.position_methods
= - current_class
.position_methods
755 # The class has already several positions and an update is needed
756 current_class
.positions_methods
[current_class
] = -current_class
.positions_methods
[current_class
]
758 for sub
in ordering
do
759 if sub
== current_class
then continue
761 var super_id
= current_class
.vtable
.id
762 var mask
= sub
.vtable
.mask
765 if vm
.inter_is_subtype_ph
(super_id
, mask
, sub
.vtable
.internal_vtable
) then
766 if not sub
.positions_methods
.has_key
(current_class
) then
767 sub
.positions_methods
[current_class
] = current_class
.position_methods
769 var old_position
= sub
.positions_methods
[current_class
]
770 if old_position
> 0 then
771 # Indicate this class can not used anymore single inheritance implementation
772 sub
.positions_methods
[current_class
] = - old_position
779 # Save the position of `current_class` in `self`
780 positions_methods
[current_class
] = offset
783 # This method is called when `current_class` class is moved in attribute table of `self`
784 # *`vm` Running instance of the virtual machine
785 # *`current_class` The class which was moved in `self` structures
786 # *`offset` The offset of block of attributes of `current_class` in `self`
787 fun moved_class_attributes
(vm
: VirtualMachine, current_class
: MClass, offset
: Int)
789 # `current_class` was moved in `self` attribute table
790 if not current_class
.positions_attributes
.has_key
(current_class
) then
791 # The invariant position is no longer satisfied
792 current_class
.positions_attributes
[current_class
] = current_class
.position_attributes
793 current_class
.position_attributes
= - current_class
.position_attributes
795 # The class has already several positions and an update is needed
796 current_class
.positions_attributes
[current_class
] = - current_class
.positions_attributes
[current_class
]
798 for sub
in ordering
do
799 if sub
== current_class
then continue
801 var super_id
= current_class
.vtable
.id
802 var mask
= sub
.vtable
.mask
805 if vm
.inter_is_subtype_ph
(super_id
, mask
, sub
.vtable
.internal_vtable
) then
806 if not sub
.positions_methods
.has_key
(current_class
) then
807 sub
.positions_attributes
[current_class
] = current_class
.position_attributes
809 var old_position
= sub
.positions_attributes
[current_class
]
810 if old_position
> 0 then
811 # Indicate this class can not used anymore single inheritance implementation
812 sub
.positions_attributes
[current_class
] = - old_position
819 # Save the position of `current_class` in `self`
820 positions_attributes
[current_class
] = offset
823 # Return the position of the method's block of class `cl` in `self` if `cl` has an invariant position in self,
824 # Otherwise return a negative position
825 fun get_position_methods
(cl
: MClass): Int
827 # The class has an invariant position in all subclasses
828 if cl
.position_methods
> 0 then return cl
.position_methods
830 # The position has an invariant position for this class and its subclasses only
831 if positions_methods
.has_key
(cl
) then
832 var pos
= positions_methods
[cl
]
833 if pos
> 0 then return pos
837 # No invariant position at all, the caller must use a multiple inheritance implementation
841 # Return the position of the attribute's block of class `cl` in `self` if `cl` has an invariant position in self,
842 # Otherwise return a negative position
843 fun get_position_attributes
(cl
: MClass): Int
845 # The class has an invariant position in all subclasses
846 if cl
.position_attributes
> 0 then return cl
.position_attributes
848 # The position has an invariant position for this class and its subclasses only
849 if positions_attributes
.has_key
(cl
) then
850 var pos
= positions_attributes
[cl
]
851 if pos
> 0 then return pos
855 # No invariant position at all, the caller must use a multiple inheritance implementation
860 redef class MProperty
861 # Relative offset of this in the runtime instance
862 # (beginning of the block of its introducing class for attributes or methods)
866 redef class MAttribute
867 # Relative offset of this attribute in the runtime instance
868 # (beginning of the block of its introducing class)
869 redef var offset
: Int
873 # Relative offset of this method in the virtual table (from the beginning of the block)
874 redef var offset
: Int
877 # Redef MutableInstance to improve implementation of attributes in objects
878 redef class MutableInstance
880 # C-array to store pointers to attributes of this Object
881 var internal_attributes
: Pointer
884 # Redef to associate an `Instance` to its `VTable`
887 # Associate a runtime instance to its virtual table which contains methods, types etc.
888 var vtable
: nullable VTable
891 # Is the type of the initial value inside attributes
895 redef var model
: Model
897 redef fun to_s
do return "InitType"
898 redef fun as_nullable
do return self
899 redef fun need_anchor
do return false
900 redef fun resolve_for
(mtype
, anchor
, mmodule
, cleanup_virtual
) do return self
901 redef fun can_resolve_for
(mtype
, anchor
, mmodule
) do return true
903 redef fun collect_mclassdefs
(mmodule
) do return new HashSet[MClassDef]
905 redef fun collect_mclasses
(mmodule
) do return new HashSet[MClass]
907 redef fun collect_mtypes
(mmodule
) do return new HashSet[MClassType]
910 # A VTable contains the virtual method table for the dispatch
911 # and informations to perform subtyping tests
913 # The mask to perform perfect hashing
914 var mask
: Int is noinit
916 # Unique identifier given by perfect hashing
917 var id
: Int is noinit
919 # Pointer to the c-allocated area, represents the virtual table
920 var internal_vtable
: Pointer is noinit
922 # The short classname of this class
923 var classname
: String is noinit
926 # Handle memory, used for allocate virtual table and associated structures
929 # Allocate and fill a virtual table
930 fun init_vtable
(ids
: Array[Int], nb_methods
: Array[Int], nb_attributes
: Array[Int], mask
: Int): Pointer
932 # Allocate in C current virtual table
933 var res
= intern_init_vtable
(ids
, nb_methods
, nb_attributes
, mask
)
938 # Construct virtual tables with a bi-dimensional layout
939 private fun intern_init_vtable
(ids
: Array[Int], nb_methods
: Array[Int], deltas
: Array[Int], mask
: Int): Pointer
940 import Array[Int].length
, Array[Int].[] `{
942 // Allocate and fill current virtual table
944 int total_size = 0; // total size of this virtual table
945 int nb_classes = Array_of_Int_length(nb_methods);
946 for(i = 0; i<nb_classes; i++) {
947 /* - One for each method of this class
948 * - One for the delta (offset of this group of attributes in objects)
951 total_size += Array_of_Int__index(nb_methods, i);
955 // Add the size of the perfect hashtable (mask +1)
956 // Add one because we start to fill the vtable at position 1 (0 is the init position)
957 total_size += mask+2;
958 long unsigned int* vtable = malloc(sizeof(long unsigned int)*total_size);
960 // Initialisation to the first position of the virtual table (ie : Object)
961 long unsigned int *init = vtable + mask + 2;
962 for(i=0; i<total_size; i++)
963 vtable[i] = (long unsigned int)init;
965 // Set the virtual table to its position 0
966 // ie: after the hashtable
967 vtable = vtable + mask + 1;
969 int current_size = 1;
970 for(i = 0; i < nb_classes; i++) {
972 vtable[hv] contains a pointer to the group of introduced methods
973 For each superclasse we have in virtual table :
974 (id | delta | introduced methods)
976 int hv = mask & Array_of_Int__index(ids, i);
978 vtable[current_size] = Array_of_Int__index(ids, i);
979 vtable[current_size + 1] = Array_of_Int__index(deltas, i);
980 vtable[-hv] = (long unsigned int)&(vtable[current_size]);
983 current_size += Array_of_Int__index(nb_methods, i);
989 # Put implementation of methods of a class in `vtable`
990 # * `vtable` : Pointer to the C-virtual table
991 # * `mask` : perfect-hashing mask of the class corresponding to the vtable
992 # * `id` : id of the target class
993 # * `methods` : array of MMethodDef of the target class
994 fun put_methods
(vtable
: Pointer, mask
: Int, id
: Int, methods
: Array[MMethodDef])
995 import Array[MMethodDef].length
, Array[MMethodDef].[] `{
997 // Get the area to fill with methods by a sequence of perfect hashing
999 long unsigned int *pointer = (long unsigned int*)(((long unsigned int *)vtable)[-hv]);
1001 // pointer+2 is the beginning of the area for methods implementation
1002 int length = Array_of_MMethodDef_length(methods);
1003 long unsigned int *area = (pointer + 2);
1006 for(i=0; i<length; i++)
1008 MMethodDef method = Array_of_MMethodDef__index(methods, i);
1009 area[i] = (long unsigned int)method;
1010 MMethodDef_incr_ref(method);
1014 # Return a NULL pointer, used to initialize virtual tables
1015 private fun null_ptr
: Pointer `{