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 intrude import interpreter
::naive_interpreter
22 import perfect_hashing
24 redef class ModelBuilder
25 redef fun run_naive_interpreter
(mainmodule
: MModule, arguments
: Array[String])
28 self.toolcontext
.info
("*** NITVM STARTING ***", 1)
30 var interpreter
= new VirtualMachine(self, mainmodule
, arguments
)
31 init_naive_interpreter
(interpreter
, mainmodule
)
34 self.toolcontext
.info
("*** NITVM STOPPING : {time1-time0} ***", 2)
38 # A virtual machine based on the naive_interpreter
39 class VirtualMachine super NaiveInterpreter
41 # Perfect hashing and perfect numbering
42 var ph
: Perfecthashing = new Perfecthashing
44 # Handles memory and garbage collection
45 var memory_manager
: MemoryManager = new MemoryManager
47 # The unique instance of the `MInit` value
48 var initialization_value
: Instance
50 init(modelbuilder
: ModelBuilder, mainmodule
: MModule, arguments
: Array[String])
53 var init_type
= new MInitType(mainmodule
.model
)
54 initialization_value
= new MutableInstance(init_type
)
57 # Subtyping test for the virtual machine
58 redef fun is_subtype
(sub
, sup
: MType): Bool
60 var anchor
= self.frame
.arguments
.first
.mtype
.as(MClassType)
61 var sup_accept_null
= false
62 if sup
isa MNullableType then
63 sup_accept_null
= true
65 else if sup
isa MNullType then
66 sup_accept_null
= true
69 # Can `sub` provides null or not?
70 # Thus we can match with `sup_accept_null`
71 # Also discard the nullable marker if it exists
72 if sub
isa MNullableType then
73 if not sup_accept_null
then return false
75 else if sub
isa MNullType then
76 return sup_accept_null
78 # Now the case of direct null and nullable is over
80 # An unfixed formal type can only accept itself
81 if sup
isa MParameterType or sup
isa MVirtualType then
85 if sub
isa MParameterType or sub
isa MVirtualType then
86 sub
= sub
.anchor_to
(mainmodule
, anchor
)
87 # Manage the second layer of null/nullable
88 if sub
isa MNullableType then
89 if not sup_accept_null
then return false
91 else if sub
isa MNullType then
92 return sup_accept_null
96 assert sub
isa MClassType
98 # `sup` accepts only null
99 if sup
isa MNullType then return false
101 assert sup
isa MClassType
103 # Create the sup vtable if not create
104 if not sup
.mclass
.loaded
then create_class
(sup
.mclass
)
106 # Sub can be discovered inside a Generic type during the subtyping test
107 if not sub
.mclass
.loaded
then create_class
(sub
.mclass
)
109 if anchor
== null then anchor
= sub
110 if sup
isa MGenericType then
111 var sub2
= sub
.supertype_to
(mainmodule
, anchor
, sup
.mclass
)
112 assert sub2
.mclass
== sup
.mclass
114 for i
in [0..sup
.mclass
.arity
[ do
115 var sub_arg
= sub2
.arguments
[i
]
116 var sup_arg
= sup
.arguments
[i
]
117 var res
= is_subtype
(sub_arg
, sup_arg
)
119 if res
== false then return false
124 var super_id
= sup
.mclass
.vtable
.id
125 var mask
= sub
.mclass
.vtable
.mask
127 return inter_is_subtype
(super_id
, mask
, sub
.mclass
.vtable
.internal_vtable
)
130 # Subtyping test with perfect hashing
131 private fun inter_is_subtype
(id
: Int, mask
:Int, vtable
: Pointer): Bool `{
132 // hv is the position in hashtable
135 // Follow the pointer to somewhere in the vtable
136 long unsigned int *offset = (long unsigned int*)(((long int *)vtable)[-hv]);
138 // If the pointed value is corresponding to the identifier, the test is true, otherwise false
139 return *offset == id;
142 # Redef init_instance to simulate the loading of a class
143 redef fun init_instance
(recv
: Instance)
145 if not recv
.mtype
.as(MClassType).mclass
.loaded
then create_class
(recv
.mtype
.as(MClassType).mclass
)
147 recv
.vtable
= recv
.mtype
.as(MClassType).mclass
.vtable
149 assert(recv
isa MutableInstance)
151 recv
.internal_attributes
= init_internal_attributes
(initialization_value
, recv
.mtype
.as(MClassType).mclass
.all_mattributes
(mainmodule
, none_visibility
).length
)
155 # Initialize the internal representation of an object (its attribute values)
156 # `init_instance` is the initial value of attributes
157 private fun init_internal_attributes
(init_instance
: Instance, size
: Int): Pointer
158 import Array[Instance].length
, Array[Instance].[] `{
160 Instance* attributes = malloc(sizeof(Instance) * size);
163 for(i=0; i<size; i++)
164 attributes[i] = init_instance;
166 Instance_incr_ref(init_instance);
170 # Creates the runtime structures for this class
171 fun create_class
(mclass
: MClass) do mclass
.make_vt
(self)
173 # Return the value of the attribute `mproperty` for the object `recv`
174 redef fun read_attribute
(mproperty
: MAttribute, recv
: Instance): Instance
176 assert recv
isa MutableInstance
178 # Read the attribute value with perfect hashing
179 var id
= mproperty
.intro_mclassdef
.mclass
.vtable
.id
181 var i
= read_attribute_ph
(recv
.internal_attributes
, recv
.vtable
.internal_vtable
,
182 recv
.vtable
.mask
, id
, mproperty
.offset
)
184 # If we get a `MInit` value, throw an error
185 if i
== initialization_value
then
186 fatal
("Uninitialized attribute {mproperty.name}")
193 # Return the attribute value in `instance` with a sequence of perfect_hashing
194 # `instance` is the attributes array of the receiver
195 # `vtable` is the pointer to the virtual table of the class (of the receiver)
196 # `mask` is the perfect hashing mask of the class
197 # `id` is the identifier of the class
198 # `offset` is the relative offset of this attribute
199 private fun read_attribute_ph
(instance
: Pointer, vtable
: Pointer, mask
: Int, id
: Int, offset
: Int): Instance `{
200 // Perfect hashing position
202 long unsigned int *pointer = (long unsigned int*)(((long int *)vtable)[-hv]);
204 // pointer+1 is the position where the delta of the class is
205 int absolute_offset = *(pointer + 1);
207 Instance res = ((Instance *)instance)[absolute_offset + offset];
212 # Replace in `recv` the value of the attribute `mproperty` by `value`
213 redef fun write_attribute
(mproperty
: MAttribute, recv
: Instance, value
: Instance)
215 assert recv
isa MutableInstance
217 var id
= mproperty
.intro_mclassdef
.mclass
.vtable
.id
219 # Replace the old value of mproperty in recv
220 write_attribute_ph
(recv
.internal_attributes
, recv
.vtable
.internal_vtable
,
221 recv
.vtable
.mask
, id
, mproperty
.offset
, value
)
224 # Replace the value of an attribute in an instance
225 # `instance` is the attributes array of the receiver
226 # `vtable` is the pointer to the virtual table of the class (of the receiver)
227 # `mask` is the perfect hashing mask of the class
228 # `id` is the identifier of the class
229 # `offset` is the relative offset of this attribute
230 # `value` is the new value for this attribute
231 private fun write_attribute_ph
(instance
: Pointer, vtable
: Pointer, mask
: Int, id
: Int, offset
: Int, value
: Instance) `{
232 // Perfect hashing position
234 long unsigned int *pointer = (long unsigned int*)(((long int *)vtable)[-hv]);
236 // pointer+1 is the position where the delta of the class is
237 int absolute_offset = *(pointer + 1);
239 ((Instance *)instance)[absolute_offset + offset] = value;
240 Instance_incr_ref(value);
243 # Is the attribute `mproperty` initialized in the instance `recv`?
244 redef fun isset_attribute
(mproperty
: MAttribute, recv
: Instance): Bool
246 assert recv
isa MutableInstance
248 # Read the attribute value with internal perfect hashing read
249 # because we do not want to throw an error if the value is `initialization_value`
250 var id
= mproperty
.intro_mclassdef
.mclass
.vtable
.id
252 var i
= read_attribute_ph
(recv
.internal_attributes
, recv
.vtable
.internal_vtable
,
253 recv
.vtable
.mask
, id
, mproperty
.offset
)
255 return i
!= initialization_value
260 # A reference to the virtual table of this class
261 var vtable
: nullable VTable
263 # True when the class is effectively loaded by the vm, false otherwise
264 var loaded
: Bool = false
266 # For each loaded subclass, keep the position of the group of attributes
267 # introduced by self class in the object
268 var positions_attributes
: HashMap[MClass, Int] = new HashMap[MClass, Int]
270 # For each loaded subclass, keep the position of the group of methods
271 # introduced by self class in the vtable
272 var positions_methods
: HashMap[MClass, Int] = new HashMap[MClass, Int]
274 # Allocates a VTable for this class and gives it an id
275 private fun make_vt
(v
: VirtualMachine)
277 if loaded
then return
279 # `superclasses` contains the order of superclasses for virtual tables
280 var superclasses
= superclasses_ordering
(v
)
281 superclasses
.remove
(self)
283 # Make_vt for super-classes
284 var ids
= new Array[Int]
285 var nb_methods
= new Array[Int]
286 var nb_attributes
= new Array[Int]
288 # Absolute offset of the beginning of the attributes table
289 var offset_attributes
= 0
290 # Absolute offset of the beginning of the methods table
291 var offset_methods
= 0
293 for parent
in superclasses
do
294 if not parent
.loaded
then parent
.make_vt
(v
)
296 # Get the number of introduced methods and attributes for this class
300 for p
in parent
.intro_mproperties
(none_visibility
) do
301 if p
isa MMethod then methods
+= 1
302 if p
isa MAttribute then
307 ids
.push
(parent
.vtable
.id
)
308 nb_methods
.push
(methods
)
309 nb_attributes
.push
(attributes
)
311 # Update `positions_attributes` and `positions_methods` in `parent`
312 update_positions
(offset_attributes
, offset_methods
, parent
)
314 offset_attributes
+= attributes
315 offset_methods
+= methods
318 # When all super-classes have their identifiers and vtables, allocate current one
319 allocate_vtable
(v
, ids
, nb_methods
, nb_attributes
, offset_attributes
, offset_methods
)
321 # The virtual table now needs to be filled with pointer to methods
324 # Allocate a single vtable
325 # `ids : Array of superclasses identifiers
326 # `nb_methods : Array which contain the number of introduced methods for each class in ids
327 # `nb_attributes : Array which contain the number of introduced attributes for each class in ids
328 # `offset_attributes : Offset from the beginning of the table of the group of attributes
329 # `offset_methods : Offset from the beginning of the table of the group of methods
330 private fun allocate_vtable
(v
: VirtualMachine, ids
: Array[Int], nb_methods
: Array[Int], nb_attributes
: Array[Int],
331 offset_attributes
: Int, offset_methods
: Int)
334 var idc
= new Array[Int]
336 vtable
.mask
= v
.ph
.pnand
(ids
, 1, idc
) - 1
338 vtable
.classname
= name
340 # Add current id to Array of super-ids
341 var ids_total
= new Array[Int]
342 ids_total
.add_all
(ids
)
343 ids_total
.push
(vtable
.id
)
345 var nb_methods_total
= new Array[Int]
346 var nb_attributes_total
= new Array[Int]
349 var nb_introduced_attributes
= 0
351 # For self attributes, fixing offsets
352 var relative_offset
= 0
353 for p
in intro_mproperties
(none_visibility
) do
354 if p
isa MMethod then self_methods
+= 1
355 if p
isa MAttribute then
356 nb_introduced_attributes
+= 1
357 p
.offset
= relative_offset
362 nb_methods_total
.add_all
(nb_methods
)
363 nb_methods_total
.push
(self_methods
)
365 nb_attributes_total
.add_all
(nb_attributes
)
366 nb_attributes_total
.push
(nb_introduced_attributes
)
368 # Save the offsets of self class
369 offset_attributes
+= nb_introduced_attributes
370 offset_methods
+= self_methods
371 update_positions
(offset_attributes
, offset_methods
, self)
373 # Since we have the number of attributes for each class, calculate the delta
374 var d
= calculate_delta
(nb_attributes_total
)
375 vtable
.internal_vtable
= v
.memory_manager
.init_vtable
(ids_total
, nb_methods_total
, d
, vtable
.mask
)
378 # Computes delta for each class
379 # A delta represents the offset for this group of attributes in the object
380 # `nb_attributes` : number of attributes for each class (classes are linearized from Object to current)
381 # return deltas for each class
382 private fun calculate_delta
(nb_attributes
: Array[Int]): Array[Int]
384 var deltas
= new Array[Int]
387 for nb
in nb_attributes
do
395 # Order superclasses of self
396 # Return the order of superclasses in runtime structures of this class
397 private fun superclasses_ordering
(v
: VirtualMachine): Array[MClass]
399 var superclasses
= new Array[MClass]
400 superclasses
.add_all
(ancestors
)
402 var res
= new Array[MClass]
403 if superclasses
.length
> 1 then
405 var ordering
= self.dfs
(v
, res
)
409 # There is no super-class, self is Object
414 # A kind of Depth-First-Search for superclasses ordering
415 # `v` : the current executed instance of VirtualMachine
416 # `res` : Result Array, ie current superclasses ordering
417 private fun dfs
(v
: VirtualMachine, res
: Array[MClass]): Array[MClass]
419 # Add this class at the beginning
422 var direct_parents
= self.in_hierarchy
(v
.mainmodule
).direct_greaters
.to_a
424 if direct_parents
.length
> 1 then
425 # Prefix represents the class which has the most properties
426 # we try to choose it in first to reduce the number of potential recompilations
429 for cl
in direct_parents
do
430 # If we never have visited this class
431 if not res
.has
(cl
) then
432 var properties_length
= cl
.all_mproperties
(v
.mainmodule
, none_visibility
).length
433 if properties_length
> max
then
434 max
= properties_length
440 if prefix
!= null then
441 # Add the prefix class ordering at the beginning of our sequence
442 var prefix_res
= new Array[MClass]
443 prefix_res
= prefix
.dfs
(v
, prefix_res
)
445 # Then we recurse on other classes
446 for cl
in direct_parents
do
448 res
= new Array[MClass]
452 if not prefix_res
.has
(cl_res
) then prefix_res
.push
(cl_res
)
461 if direct_parents
.length
> 0 then
462 res
= direct_parents
.first
.dfs
(v
, res
)
466 if not res
.has
(self) then res
.push
(self)
471 # Update positions of self class in `parent`
472 # `attributes_offset`: absolute offset of introduced attributes
473 # `methods_offset`: absolute offset of introduced methods
474 private fun update_positions
(attributes_offsets
: Int, methods_offset
:Int, parent
: MClass)
476 parent
.positions_attributes
[self] = attributes_offsets
477 parent
.positions_methods
[self] = methods_offset
481 redef class MAttribute
482 # Represents the relative offset of this attribute in the runtime instance
486 # Redef MutableInstance to improve implementation of attributes in objects
487 redef class MutableInstance
489 # C-array to store pointers to attributes of this Object
490 var internal_attributes
: Pointer
493 # Is the type of the initial value inside attributes
497 redef var model
: Model
498 protected init(model
: Model)
503 redef fun to_s
do return "InitType"
504 redef fun as_nullable
do return self
505 redef fun need_anchor
do return false
506 redef fun resolve_for
(mtype
, anchor
, mmodule
, cleanup_virtual
) do return self
507 redef fun can_resolve_for
(mtype
, anchor
, mmodule
) do return true
509 redef fun collect_mclassdefs
(mmodule
) do return new HashSet[MClassDef]
511 redef fun collect_mclasses
(mmodule
) do return new HashSet[MClass]
513 redef fun collect_mtypes
(mmodule
) do return new HashSet[MClassType]
516 # A VTable contains the virtual method table for the dispatch
517 # and informations to perform subtyping tests
519 # The mask to perform perfect hashing
520 var mask
: Int is noinit
522 # Unique identifier given by perfect hashing
523 var id
: Int is noinit
525 # Pointer to the c-allocated area, represents the virtual table
526 var internal_vtable
: Pointer is noinit
528 # The short classname of this class
529 var classname
: String is noinit
533 var vtable
: nullable VTable
536 # Handle memory, used for allocate virtual table and associated structures
539 # Allocate and fill a virtual table
540 fun init_vtable
(ids
: Array[Int], nb_methods
: Array[Int], nb_attributes
: Array[Int], mask
: Int): Pointer
542 # Allocate in C current virtual table
543 var res
= intern_init_vtable
(ids
, nb_methods
, nb_attributes
, mask
)
548 # Construct virtual tables with a bi-dimensional layout
549 private fun intern_init_vtable
(ids
: Array[Int], nb_methods
: Array[Int], deltas
: Array[Int], mask
: Int): Pointer
550 import Array[Int].length
, Array[Int].[] `{
552 // Allocate and fill current virtual table
554 int total_size = 0; // total size of this virtual table
555 int nb_classes = Array_of_Int_length(nb_methods);
556 for(i = 0; i<nb_classes; i++) {
557 /* - One for each method of this class
558 * - One for the delta (offset of this group of attributes in objects)
561 total_size += Array_of_Int__index(nb_methods, i);
565 // Add the size of the perfect hashtable (mask +1)
566 // Add one because we start to fill the vtable at position 1 (0 is the init position)
567 total_size += mask+2;
568 long unsigned int* vtable = malloc(sizeof(long unsigned int)*total_size);
570 // Initialisation to the first position of the virtual table (ie : Object)
571 long unsigned int *init = vtable + mask + 2;
572 for(i=0; i<total_size; i++)
573 vtable[i] = (long unsigned int)init;
575 // Set the virtual table to its position 0
576 // ie: after the hashtable
577 vtable = vtable + mask + 1;
579 int current_size = 1;
580 for(i = 0; i < nb_classes; i++) {
582 vtable[hv] contains a pointer to the group of introduced methods
583 For each superclasse we have in virtual table :
584 (id | delta | introduced methods)
586 int hv = mask & Array_of_Int__index(ids, i);
588 vtable[current_size] = Array_of_Int__index(ids, i);
589 vtable[current_size + 1] = Array_of_Int__index(deltas, i);
590 vtable[-hv] = (long unsigned int)&(vtable[current_size]);
593 current_size += Array_of_Int__index(nb_methods, i);