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
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 MParameterType or sub
isa MVirtualType then
65 sub
= sub
.resolve_for
(anchor
.mclass
.mclass_type
, anchor
, mainmodule
, false)
67 if sup
isa MParameterType or sup
isa MVirtualType 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 MParameterType or sub
isa MVirtualType 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 # `sub` and `sup` can be discovered inside a Generic type during the subtyping test
109 if not sup
.mclass
.loaded
then create_class
(sup
.mclass
)
110 if not sub
.mclass
.loaded
then create_class
(sub
.mclass
)
112 # For now, always use perfect hashing for subtyping test
113 var super_id
= sup
.mclass
.vtable
.id
114 var mask
= sub
.mclass
.vtable
.mask
116 var res
= inter_is_subtype_ph
(super_id
, mask
, sub
.mclass
.vtable
.internal_vtable
)
117 if res
== false then return false
118 # sub and sup can be generic types, each argument of generics has to be tested
120 if not sup
isa MGenericType then return true
121 var sub2
= sub
.supertype_to
(mainmodule
, anchor
, sup
.mclass
)
123 # Test each argument of a generic by recursive calls
124 for i
in [0..sup
.mclass
.arity
[ do
125 var sub_arg
= sub2
.arguments
[i
]
126 var sup_arg
= sup
.arguments
[i
]
127 var res2
= is_subtype
(sub_arg
, sup_arg
)
128 if res2
== false then return false
133 # Subtyping test with perfect hashing
134 # * `id` is the identifier of the target class
135 # * `mask` is the perfect hashing mask of the receiver class
136 # * `vtable` is the pointer to the virtual table of the receiver class
137 fun inter_is_subtype_ph
(id
: Int, mask
:Int, vtable
: Pointer): Bool `{
138 // hv is the position in hashtable
141 // Follow the pointer to somewhere in the vtable
142 long unsigned int *offset = (long unsigned int*)(((long int *)vtable)[-hv]);
144 // If the pointed value is corresponding to the identifier, the test is true, otherwise false
145 return *offset == id;
148 # Subtyping test with Cohen test (direct access)
149 # * `id` is the identifier of the target class
150 # * `mask` is the absolute position of the target identifier in the virtual table
151 # * `vtable` is the pointer to the virtual table of the receiver class
152 fun inter_is_subtype_sst
(id
: Int, position
: Int, vtable
: Pointer): Bool `{
153 // Direct access to the position given in parameter
154 int tableid = (long unsigned int)((long int *)vtable)[position];
156 return id == tableid;
159 # Redef init_instance to simulate the loading of a class
160 redef fun init_instance
(recv
: Instance)
162 if not recv
.mtype
.as(MClassType).mclass
.loaded
then create_class
(recv
.mtype
.as(MClassType).mclass
)
164 recv
.vtable
= recv
.mtype
.as(MClassType).mclass
.vtable
166 assert recv
isa MutableInstance
168 recv
.internal_attributes
= init_internal_attributes
(initialization_value
, recv
.mtype
.as(MClassType).mclass
.mattributes
.length
)
172 # Associate a `PrimitiveInstance` to its `VTable`
173 redef fun init_instance_primitive
(recv
: Instance)
175 if not recv
.mtype
.as(MClassType).mclass
.loaded
then create_class
(recv
.mtype
.as(MClassType).mclass
)
177 recv
.vtable
= recv
.mtype
.as(MClassType).mclass
.vtable
180 # Create a virtual table for this `MClass` if not already done
181 redef fun get_primitive_class
(name
: String): MClass
185 if not mclass
.loaded
then create_class
(mclass
)
190 # Initialize the internal representation of an object (its attribute values)
191 # `init_instance` is the initial value of attributes
192 private fun init_internal_attributes
(init_instance
: Instance, size
: Int): Pointer
193 import Array[Instance].length
, Array[Instance].[] `{
195 Instance* attributes = malloc(sizeof(Instance) * size);
198 for(i=0; i<size; i++)
199 attributes[i] = init_instance;
201 Instance_incr_ref(init_instance);
205 # Creates the runtime structures for this class
206 fun create_class
(mclass
: MClass) do mclass
.make_vt
(self)
208 # Execute `mproperty` for a `args` (where `args[0]` is the receiver).
209 redef fun send
(mproperty
: MMethod, args
: Array[Instance]): nullable Instance
211 var recv
= args
.first
212 var mtype
= recv
.mtype
213 var ret
= send_commons
(mproperty
, args
, mtype
)
214 if ret
!= null then return ret
216 var propdef
= method_dispatch
(mproperty
, recv
.vtable
.as(not null), recv
)
218 return self.call
(propdef
, args
)
221 # Method dispatch, for a given global method `mproperty`
222 # returns the most specific local method in the class corresponding to `vtable`
223 private fun method_dispatch
(mproperty
: MMethod, vtable
: VTable, recv
: Instance): MMethodDef
225 if mproperty
.intro_mclassdef
.mclass
.positions_methods
[recv
.mtype
.as(MClassType).mclass
] != -1 then
226 return method_dispatch_sst
(vtable
.internal_vtable
, mproperty
.absolute_offset
)
228 return method_dispatch_ph
(vtable
.internal_vtable
, vtable
.mask
,
229 mproperty
.intro_mclassdef
.mclass
.vtable
.id
, mproperty
.offset
)
233 # Execute a method dispatch with perfect hashing and return the appropriate `MMethodDef`
234 # * `vtable` Pointer to the internal virtual table of the class
235 # * `mask` Perfect hashing mask of the receiver class
236 # * `id` Identifier of the class which introduce the method
237 # * `offset` Relative offset of the method from the beginning of the block
238 fun method_dispatch_ph
(vtable
: Pointer, mask
: Int, id
: Int, offset
: Int): MMethodDef `{
239 // Perfect hashing position
241 long unsigned int *pointer = (long unsigned int*)(((long int *)vtable)[-hv]);
243 // pointer+2 is the position where methods are
244 // Add the offset of property and get the method implementation
245 MMethodDef propdef = (MMethodDef)*(pointer + 2 + offset);
250 # Execute a method dispatch with direct access and return the appropriate `MMethodDef`
251 # * `vtable` Pointer to the internal virtual table of the class
252 # * `absolute_offset` Absolute offset from the beginning of the virtual table
253 fun method_dispatch_sst
(vtable
: Pointer, absolute_offset
: Int): MMethodDef `{
254 // pointer+2 is the position where methods are
255 // Add the offset of property and get the method implementation
256 MMethodDef propdef = (MMethodDef)((long int *)vtable)[absolute_offset];
261 # Return the value of the attribute `mproperty` for the object `recv`
262 redef fun read_attribute
(mproperty
: MAttribute, recv
: Instance): Instance
264 assert recv
isa MutableInstance
268 if mproperty
.intro_mclassdef
.mclass
.positions_attributes
[recv
.mtype
.as(MClassType).mclass
] != -1 then
269 # if this attribute class has an unique position for this receiver, then use direct access
270 i
= read_attribute_sst
(recv
.internal_attributes
, mproperty
.absolute_offset
)
272 # Otherwise, read the attribute value with perfect hashing
273 var id
= mproperty
.intro_mclassdef
.mclass
.vtable
.id
275 i
= read_attribute_ph
(recv
.internal_attributes
, recv
.vtable
.internal_vtable
,
276 recv
.vtable
.mask
, id
, mproperty
.offset
)
279 # If we get a `MInit` value, throw an error
280 if i
== initialization_value
then
281 fatal
("Uninitialized attribute {mproperty.name}")
288 # Return the attribute value in `instance` with a sequence of perfect_hashing
289 # * `instance` is the attributes array of the receiver
290 # * `vtable` is the pointer to the virtual table of the class (of the receiver)
291 # * `mask` is the perfect hashing mask of the class
292 # * `id` is the identifier of the class
293 # * `offset` is the relative offset of this attribute
294 fun read_attribute_ph
(instance
: Pointer, vtable
: Pointer, mask
: Int, id
: Int, offset
: Int): Instance `{
295 // Perfect hashing position
297 long unsigned int *pointer = (long unsigned int*)(((long int *)vtable)[-hv]);
299 // pointer+1 is the position where the delta of the class is
300 int absolute_offset = *(pointer + 1);
302 Instance res = ((Instance *)instance)[absolute_offset + offset];
307 # Return the attribute value in `instance` with a direct access (SST)
308 # * `instance` is the attributes array of the receiver
309 # * `offset` is the absolute offset of this attribute
310 fun read_attribute_sst
(instance
: Pointer, offset
: Int): Instance `{
311 /* We can make a direct access to the attribute value
312 because this attribute is always at the same position
313 for the class of this receiver */
314 Instance res = ((Instance *)instance)[offset];
319 # Replace in `recv` the value of the attribute `mproperty` by `value`
320 redef fun write_attribute
(mproperty
: MAttribute, recv
: Instance, value
: Instance)
322 assert recv
isa MutableInstance
324 # Replace the old value of mproperty in recv
325 if mproperty
.intro_mclassdef
.mclass
.positions_attributes
[recv
.mtype
.as(MClassType).mclass
] != -1 then
326 # if this attribute class has an unique position for this receiver, then use direct access
327 write_attribute_sst
(recv
.internal_attributes
, mproperty
.absolute_offset
, value
)
329 # Otherwise, use perfect hashing to replace the old value
330 var id
= mproperty
.intro_mclassdef
.mclass
.vtable
.id
332 write_attribute_ph
(recv
.internal_attributes
, recv
.vtable
.internal_vtable
,
333 recv
.vtable
.mask
, id
, mproperty
.offset
, value
)
337 # Replace the value of an attribute in an instance
338 # * `instance` is the attributes array of the receiver
339 # * `vtable` is the pointer to the virtual table of the class (of the receiver)
340 # * `mask` is the perfect hashing mask of the class
341 # * `id` is the identifier of the class
342 # * `offset` is the relative offset of this attribute
343 # * `value` is the new value for this attribute
344 fun write_attribute_ph
(instance
: Pointer, vtable
: Pointer, mask
: Int, id
: Int, offset
: Int, value
: Instance) `{
345 // Perfect hashing position
347 long unsigned int *pointer = (long unsigned int*)(((long int *)vtable)[-hv]);
349 // pointer+1 is the position where the delta of the class is
350 int absolute_offset = *(pointer + 1);
352 ((Instance *)instance)[absolute_offset + offset] = value;
353 Instance_incr_ref(value);
356 # Replace the value of an attribute in an instance with direct access
357 # * `instance` is the attributes array of the receiver
358 # * `offset` is the absolute offset of this attribute
359 # * `value` is the new value for this attribute
360 fun write_attribute_sst
(instance
: Pointer, offset
: Int, value
: Instance) `{
361 // Direct access to the position with the absolute offset
362 ((Instance *)instance)[offset] = value;
363 Instance_incr_ref(value);
366 # Is the attribute `mproperty` initialized in the instance `recv`?
367 redef fun isset_attribute
(mproperty
: MAttribute, recv
: Instance): Bool
369 assert recv
isa MutableInstance
371 # Read the attribute value with internal perfect hashing read
372 # because we do not want to throw an error if the value is `initialization_value`
373 var id
= mproperty
.intro_mclassdef
.mclass
.vtable
.id
375 var i
= read_attribute_ph
(recv
.internal_attributes
, recv
.vtable
.internal_vtable
,
376 recv
.vtable
.mask
, id
, mproperty
.offset
)
378 return i
!= initialization_value
383 # A reference to the virtual table of this class
384 var vtable
: nullable VTable
386 # True when the class is effectively loaded by the vm, false otherwise
387 var loaded
: Bool = false
389 # Color for Cohen subtyping test : the absolute position of the id
390 # of this class in virtual tables
393 # For each loaded subclass, keep the position of the group of attributes
394 # introduced by self class in the object
395 var positions_attributes
: HashMap[MClass, Int] = new HashMap[MClass, Int]
397 # For each loaded subclass, keep the position of the group of methods
398 # introduced by self class in the vtable
399 var positions_methods
: HashMap[MClass, Int] = new HashMap[MClass, Int]
401 # The `MAttribute` this class introduced
402 var intro_mattributes
= new Array[MAttribute]
404 # The `MMethod` this class introduced
405 var intro_mmethods
= new Array[MMethod]
407 # All `MAttribute` this class contains
408 var mattributes
= new Array[MAttribute]
410 # All `MMethod` this class contains
411 var mmethods
= new Array[MMethod]
413 # Allocates a VTable for this class and gives it an id
414 private fun make_vt
(v
: VirtualMachine)
416 if loaded
then return
418 # `superclasses` contains the order of superclasses for virtual tables
419 var superclasses
= superclasses_ordering
(v
)
420 superclasses
.remove
(self)
422 # Make_vt for super-classes
423 var ids
= new Array[Int]
424 var nb_methods
= new Array[Int]
425 var nb_attributes
= new Array[Int]
427 # Absolute offset of attribute from the beginning of the attributes table
428 var offset_attributes
= 0
430 # Absolute offset of method from the beginning of the methods table,
431 # is initialize to 3 because the first position is empty in the virtual table
432 # and the second and third are respectively class id and delta
433 var offset_methods
= 3
435 # The previous element in `superclasses`
436 var previous_parent
: nullable MClass = null
437 if superclasses
.length
> 0 then previous_parent
= superclasses
[0]
438 for parent
in superclasses
do
439 if not parent
.loaded
then parent
.make_vt
(v
)
441 # Get the number of introduced methods and attributes for this class
442 var methods
= parent
.intro_mmethods
.length
443 var attributes
= parent
.intro_mattributes
.length
445 # Updates `mmethods` and `mattributes`
446 mmethods
.add_all
(parent
.intro_mmethods
)
447 mattributes
.add_all
(parent
.intro_mattributes
)
449 ids
.push
(parent
.vtable
.id
)
450 nb_methods
.push
(methods
)
451 nb_attributes
.push
(attributes
)
453 # Update `positions_attributes` and `positions_methods` in `parent`.
454 # If the position is invariant for this parent, store this position
455 # else store a special value (-1)
459 if previous_parent
.as(not null).positions_attributes
[parent
] == offset_attributes
then pos_attr
= offset_attributes
460 if previous_parent
.as(not null).positions_methods
[parent
] == offset_methods
then pos_meth
= offset_methods
462 parent
.update_positions
(pos_attr
, pos_meth
, self)
464 offset_attributes
+= attributes
465 offset_methods
+= methods
466 offset_methods
+= 2 # Because each block starts with an id and the delta
469 # When all super-classes have their identifiers and vtables, allocate current one
470 allocate_vtable
(v
, ids
, nb_methods
, nb_attributes
, offset_attributes
, offset_methods
)
473 # Set the absolute position of the identifier of this class in the virtual table
474 color
= offset_methods
- 2
476 # The virtual table now needs to be filled with pointer to methods
477 superclasses
.add
(self)
478 for cl
in superclasses
do
479 fill_vtable
(v
, vtable
.as(not null), cl
)
483 # Allocate a single vtable
484 # * `ids : Array of superclasses identifiers
485 # * `nb_methods : Array which contain the number of introduced methods for each class in ids
486 # * `nb_attributes : Array which contain the number of introduced attributes for each class in ids
487 # * `offset_attributes : Offset from the beginning of the table of the group of attributes
488 # * `offset_methods : Offset from the beginning of the table of the group of methods
489 private fun allocate_vtable
(v
: VirtualMachine, ids
: Array[Int], nb_methods
: Array[Int], nb_attributes
: Array[Int],
490 offset_attributes
: Int, offset_methods
: Int)
493 var idc
= new Array[Int]
495 vtable
.mask
= v
.ph
.pnand
(ids
, 1, idc
) - 1
497 vtable
.classname
= name
499 # Add current id to Array of super-ids
500 var ids_total
= new Array[Int]
501 ids_total
.add_all
(ids
)
502 ids_total
.push
(vtable
.id
)
504 var nb_methods_total
= new Array[Int]
505 var nb_attributes_total
= new Array[Int]
508 var nb_introduced_attributes
= 0
510 # Fixing offsets for self attributes and methods
511 var relative_offset_attr
= 0
512 var relative_offset_meth
= 0
514 # Update `intro_mmethods` and `intro_mattributes`
515 # For each MClassdef this MClass has
516 for classdef
in mclassdefs
do
517 # For each property this MClassdef introduce
518 for p
in classdef
.intro_mproperties
do
519 # Collect properties and fixing offsets
520 if p
isa MMethod then
522 p
.offset
= relative_offset_meth
523 p
.absolute_offset
= offset_methods
+ relative_offset_meth
524 relative_offset_meth
+= 1
526 intro_mmethods
.add
(p
)
528 if p
isa MAttribute then
529 nb_introduced_attributes
+= 1
530 p
.offset
= relative_offset_attr
531 p
.absolute_offset
= offset_attributes
+ relative_offset_attr
532 relative_offset_attr
+= 1
534 intro_mattributes
.add
(p
)
539 # Updates caches with introduced attributes of `self` class
540 mattributes
.add_all
(intro_mattributes
)
541 mmethods
.add_all
(intro_mmethods
)
543 nb_methods_total
.add_all
(nb_methods
)
544 nb_methods_total
.push
(self_methods
)
546 nb_attributes_total
.add_all
(nb_attributes
)
547 nb_attributes_total
.push
(nb_introduced_attributes
)
549 # Save the offsets of self class
550 update_positions
(offset_attributes
, offset_methods
, self)
552 # Since we have the number of attributes for each class, calculate the delta
553 var deltas
= calculate_delta
(nb_attributes_total
)
554 vtable
.internal_vtable
= v
.memory_manager
.init_vtable
(ids_total
, nb_methods_total
, deltas
, vtable
.mask
)
557 # Fill the vtable with methods of `self` class
558 # * `v` : Current instance of the VirtualMachine
559 # * `table` : the table of self class, will be filled with its methods
560 private fun fill_vtable
(v
:VirtualMachine, table
: VTable, cl
: MClass)
562 var methods
= new Array[MMethodDef]
563 for m
in cl
.intro_mmethods
do
564 # `propdef` is the most specific implementation for this MMethod
565 var propdef
= m
.lookup_first_definition
(v
.mainmodule
, self.intro
.bound_mtype
)
566 methods
.push
(propdef
)
569 # Call a method in C to put propdefs of self methods in the vtables
570 v
.memory_manager
.put_methods
(vtable
.internal_vtable
, vtable
.mask
, cl
.vtable
.id
, methods
)
573 # Computes delta for each class
574 # A delta represents the offset for this group of attributes in the object
575 # *`nb_attributes` : number of attributes for each class (classes are linearized from Object to current)
576 # * return deltas for each class
577 private fun calculate_delta
(nb_attributes
: Array[Int]): Array[Int]
579 var deltas
= new Array[Int]
582 for nb
in nb_attributes
do
590 # Order superclasses of self
591 # Return the order of superclasses in runtime structures of this class
592 private fun superclasses_ordering
(v
: VirtualMachine): Array[MClass]
594 var superclasses
= new Array[MClass]
596 # Add all superclasses of `self`
597 superclasses
.add_all
(self.in_hierarchy
(v
.mainmodule
).greaters
)
599 var res
= new Array[MClass]
600 if superclasses
.length
> 1 then
602 var ordering
= self.dfs
(v
, res
)
606 # There is no super-class, self is Object
611 # A kind of Depth-First-Search for superclasses ordering
612 # *`v` : the current executed instance of VirtualMachine
613 # * `res` : Result Array, ie current superclasses ordering
614 private fun dfs
(v
: VirtualMachine, res
: Array[MClass]): Array[MClass]
616 # Add this class at the beginning
619 var direct_parents
= self.in_hierarchy
(v
.mainmodule
).direct_greaters
.to_a
621 if direct_parents
.length
> 1 then
622 # Prefix represents the class which has the most properties
623 # we try to choose it in first to reduce the number of potential recompilations
626 for cl
in direct_parents
do
627 # If we never have visited this class
628 if not res
.has
(cl
) then
629 var properties_length
= cl
.mmethods
.length
+ cl
.mattributes
.length
630 if properties_length
> max
then
631 max
= properties_length
637 if prefix
!= null then
638 # Add the prefix class ordering at the beginning of our sequence
639 var prefix_res
= new Array[MClass]
640 prefix_res
= prefix
.dfs
(v
, prefix_res
)
642 # Then we recurse on other classes
643 for cl
in direct_parents
do
645 res
= new Array[MClass]
649 if not prefix_res
.has
(cl_res
) then prefix_res
.push
(cl_res
)
658 if direct_parents
.length
> 0 then
659 res
= direct_parents
.first
.dfs
(v
, res
)
663 if not res
.has
(self) then res
.push
(self)
668 # Update positions of the class `cl`
669 # * `attributes_offset`: absolute offset of introduced attributes
670 # * `methods_offset`: absolute offset of introduced methods
671 private fun update_positions
(attributes_offsets
: Int, methods_offset
:Int, cl
: MClass)
673 positions_attributes
[cl
] = attributes_offsets
674 positions_methods
[cl
] = methods_offset
678 redef class MAttribute
679 # Relative offset of this attribute in the runtime instance
680 # (beginning of the block of its introducing class)
683 # Absolute offset of this attribute in the runtime instance (beginning of the attribute table)
684 var absolute_offset
: Int
688 # Relative offset of this method in the virtual table (from the beginning of the block)
691 # Absolute offset of this method in the virtual table (from the beginning of the vtable)
692 var absolute_offset
: Int
695 # Redef MutableInstance to improve implementation of attributes in objects
696 redef class MutableInstance
698 # C-array to store pointers to attributes of this Object
699 var internal_attributes
: Pointer
702 # Redef to associate an `Instance` to its `VTable`
705 # Associate a runtime instance to its virtual table which contains methods, types etc.
706 var vtable
: nullable VTable
709 # Is the type of the initial value inside attributes
713 redef var model
: Model
715 redef fun to_s
do return "InitType"
716 redef fun as_nullable
do return self
717 redef fun need_anchor
do return false
718 redef fun resolve_for
(mtype
, anchor
, mmodule
, cleanup_virtual
) do return self
719 redef fun can_resolve_for
(mtype
, anchor
, mmodule
) do return true
721 redef fun collect_mclassdefs
(mmodule
) do return new HashSet[MClassDef]
723 redef fun collect_mclasses
(mmodule
) do return new HashSet[MClass]
725 redef fun collect_mtypes
(mmodule
) do return new HashSet[MClassType]
728 # A VTable contains the virtual method table for the dispatch
729 # and informations to perform subtyping tests
731 # The mask to perform perfect hashing
732 var mask
: Int is noinit
734 # Unique identifier given by perfect hashing
735 var id
: Int is noinit
737 # Pointer to the c-allocated area, represents the virtual table
738 var internal_vtable
: Pointer is noinit
740 # The short classname of this class
741 var classname
: String is noinit
744 # Handle memory, used for allocate virtual table and associated structures
747 # Allocate and fill a virtual table
748 fun init_vtable
(ids
: Array[Int], nb_methods
: Array[Int], nb_attributes
: Array[Int], mask
: Int): Pointer
750 # Allocate in C current virtual table
751 var res
= intern_init_vtable
(ids
, nb_methods
, nb_attributes
, mask
)
756 # Construct virtual tables with a bi-dimensional layout
757 private fun intern_init_vtable
(ids
: Array[Int], nb_methods
: Array[Int], deltas
: Array[Int], mask
: Int): Pointer
758 import Array[Int].length
, Array[Int].[] `{
760 // Allocate and fill current virtual table
762 int total_size = 0; // total size of this virtual table
763 int nb_classes = Array_of_Int_length(nb_methods);
764 for(i = 0; i<nb_classes; i++) {
765 /* - One for each method of this class
766 * - One for the delta (offset of this group of attributes in objects)
769 total_size += Array_of_Int__index(nb_methods, i);
773 // Add the size of the perfect hashtable (mask +1)
774 // Add one because we start to fill the vtable at position 1 (0 is the init position)
775 total_size += mask+2;
776 long unsigned int* vtable = malloc(sizeof(long unsigned int)*total_size);
778 // Initialisation to the first position of the virtual table (ie : Object)
779 long unsigned int *init = vtable + mask + 2;
780 for(i=0; i<total_size; i++)
781 vtable[i] = (long unsigned int)init;
783 // Set the virtual table to its position 0
784 // ie: after the hashtable
785 vtable = vtable + mask + 1;
787 int current_size = 1;
788 for(i = 0; i < nb_classes; i++) {
790 vtable[hv] contains a pointer to the group of introduced methods
791 For each superclasse we have in virtual table :
792 (id | delta | introduced methods)
794 int hv = mask & Array_of_Int__index(ids, i);
796 vtable[current_size] = Array_of_Int__index(ids, i);
797 vtable[current_size + 1] = Array_of_Int__index(deltas, i);
798 vtable[-hv] = (long unsigned int)&(vtable[current_size]);
801 current_size += Array_of_Int__index(nb_methods, i);
807 # Put implementation of methods of a class in `vtable`
808 # * `vtable` : Pointer to the C-virtual table
809 # * `mask` : perfect-hashing mask of the class corresponding to the vtable
810 # * `id` : id of the target class
811 # * `methods` : array of MMethodDef of the target class
812 fun put_methods
(vtable
: Pointer, mask
: Int, id
: Int, methods
: Array[MMethodDef])
813 import Array[MMethodDef].length
, Array[MMethodDef].[] `{
815 // Get the area to fill with methods by a sequence of perfect hashing
817 long unsigned int *pointer = (long unsigned int*)(((long unsigned int *)vtable)[-hv]);
819 // pointer+2 is the beginning of the area for methods implementation
820 int length = Array_of_MMethodDef_length(methods);
821 long unsigned int *area = (pointer + 2);
824 for(i=0; i<length; i++)
826 MMethodDef method = Array_of_MMethodDef__index(methods, i);
827 area[i] = (long unsigned int)method;
828 MMethodDef_incr_ref(method);