src/vm.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2014 Julien Pagès <julien.pages@lirmm.fr>
   4 #
   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
   8 #
   9 #     http://www.apache.org/licenses/LICENSE-2.0
  10 #
  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.
  16
  17 # Implementation of the Nit virtual machine
  18 module vm
  19
  20 intrude import naive_interpreter
  21 import model_utils
  22 import perfect_hashing
  23
  24 redef class ModelBuilder
  25         redef fun run_naive_interpreter(mainmodule: MModule, arguments: Array[String])
  26         do
  27                 var time0 = get_time
  28                 self.toolcontext.info("*** NITVM STARTING ***", 1)
  29
  30                 var interpreter = new VirtualMachine(self, mainmodule, arguments)
  31                 init_naive_interpreter(interpreter, mainmodule)
  32
  33                 var time1 = get_time
  34                 self.toolcontext.info("*** NITVM STOPPING : {time1-time0} ***", 2)
  35         end
  36 end
  37
  38 # A virtual machine based on the naive_interpreter
  39 class VirtualMachine super NaiveInterpreter
  40
  41         # Perfect hashing and perfect numbering
  42         var ph: Perfecthashing = new Perfecthashing
  43
  44         # Handles memory and garbage collection
  45         var memory_manager: MemoryManager = new MemoryManager
  46
  47         # Subtyping test for the virtual machine
  48         redef fun is_subtype(sub, sup: MType): Bool
  49         do
  50                 var anchor = self.frame.arguments.first.mtype.as(MClassType)
  51                 var sup_accept_null = false
  52                 if sup isa MNullableType then
  53                         sup_accept_null = true
  54                         sup = sup.mtype
  55                 else if sup isa MNullType then
  56                         sup_accept_null = true
  57                 end
  58
  59                 # Can `sub` provides null or not?
  60                 # Thus we can match with `sup_accept_null`
  61                 # Also discard the nullable marker if it exists
  62                 if sub isa MNullableType then
  63                         if not sup_accept_null then return false
  64                         sub = sub.mtype
  65                 else if sub isa MNullType then
  66                         return sup_accept_null
  67                 end
  68                 # Now the case of direct null and nullable is over
  69
  70                 # An unfixed formal type can only accept itself
  71                 if sup isa MParameterType or sup isa MVirtualType then
  72                         return sub == sup
  73                 end
  74
  75                 if sub isa MParameterType or sub isa MVirtualType then
  76                         sub = sub.anchor_to(mainmodule, anchor)
  77                         # Manage the second layer of null/nullable
  78                         if sub isa MNullableType then
  79                                 if not sup_accept_null then return false
  80                                 sub = sub.mtype
  81                         else if sub isa MNullType then
  82                                 return sup_accept_null
  83                         end
  84                 end
  85
  86                 assert sub isa MClassType
  87
  88                 # `sup` accepts only null
  89                 if sup isa MNullType then return false
  90
  91                 assert sup isa MClassType
  92
  93                 # Create the sup vtable if not create
  94                 if not sup.mclass.loaded then create_class(sup.mclass)
  95
  96                 # Sub can be discovered inside a Generic type during the subtyping test
  97                 if not sub.mclass.loaded then create_class(sub.mclass)
  98
  99                 if anchor == null then anchor = sub
 100                 if sup isa MGenericType then
 101                         var sub2 = sub.supertype_to(mainmodule, anchor, sup.mclass)
 102                         assert sub2.mclass == sup.mclass
 103
 104                         for i in [0..sup.mclass.arity[ do
 105                                 var sub_arg = sub2.arguments[i]
 106                                 var sup_arg = sup.arguments[i]
 107                                 var res = is_subtype(sub_arg, sup_arg)
 108
 109                                 if res == false then return false
 110                         end
 111                         return true
 112                 end
 113
 114                 var super_id = sup.mclass.vtable.id
 115                 var mask = sub.mclass.vtable.mask
 116
 117                 return inter_is_subtype(super_id, mask, sub.mclass.vtable.internal_vtable)
 118         end
 119
 120         # Subtyping test with perfect hashing
 121         private fun inter_is_subtype(id: Int, mask:Int, vtable: Pointer): Bool `{
 122                 // hv is the position in hashtable
 123                 int hv = id & mask;
 124
 125                 // Follow the pointer to somewhere in the vtable
 126                 long unsigned int *offset = (long unsigned int*)(((long int *)vtable)[-hv]);
 127
 128                 // If the pointed value is corresponding to the identifier, the test is true, otherwise false
 129                 return *offset == id;
 130         `}
 131
 132         # Redef init_instance to simulate the loading of a class
 133         redef fun init_instance(recv: Instance)
 134         do
 135                 if not recv.mtype.as(MClassType).mclass.loaded then create_class(recv.mtype.as(MClassType).mclass)
 136                 super
 137
 138                 recv.vtable = recv.mtype.as(MClassType).mclass.vtable
 139         end
 140
 141         # Creates the runtime structures for this class
 142         fun create_class(mclass: MClass) do     mclass.make_vt(self)
 143 end
 144
 145 redef class MClass
 146         # A reference to the virtual table of this class
 147         var vtable: nullable VTable
 148
 149         # True when the class is effectively loaded by the vm, false otherwise
 150         var loaded: Bool = false
 151
 152         # Allocates a VTable for this class and gives it an id
 153         private fun make_vt(v: VirtualMachine)
 154         do
 155                 if loaded then return
 156
 157                 # Superclasses contains all superclasses except self
 158                 var superclasses = new Array[MClass]
 159                 superclasses.add_all(ancestors)
 160                 superclasses.remove(self)
 161                 v.mainmodule.linearize_mclasses(superclasses)
 162
 163                 # Make_vt for super-classes
 164                 var ids = new Array[Int]
 165                 var nb_methods = new Array[Int]
 166
 167                 for parent in superclasses do
 168                         if parent.vtable == null then parent.make_vt(v)
 169
 170                         # Get the number of introduced methods and attributes for this class
 171                         var methods = 0
 172
 173                         for p in parent.intro_mproperties(none_visibility) do
 174                                 if p isa MMethod then methods += 1
 175                         end
 176
 177                         ids.push(parent.vtable.id)
 178                         nb_methods.push(methods)
 179                 end
 180
 181                 # When all super-classes have their identifiers and vtables, allocate current one
 182                 allocate_vtable(v, ids, nb_methods)
 183                 loaded = true
 184                 # The virtual table now needs to be filled with pointer to methods
 185         end
 186
 187         # Allocate a single vtable
 188         #       ids : Array of superclasses identifiers
 189         #       nb_methods : Array which contain the number of introducted methods for each class in ids
 190         private fun allocate_vtable(v: VirtualMachine, ids: Array[Int], nb_methods: Array[Int])
 191         do
 192                 vtable = new VTable
 193                 var idc = new Array[Int]
 194
 195                 vtable.mask = v.ph.pnand(ids, 1, idc) - 1
 196                 vtable.id = idc[0]
 197                 vtable.classname = name
 198
 199                 # Add current id to Array of super-ids
 200                 var ids_total = new Array[Int]
 201                 ids_total.add_all(ids)
 202                 ids_total.push(vtable.id)
 203
 204                 var nb_methods_total = new Array[Int]
 205                 var methods = 0
 206                 for p in intro_mproperties(none_visibility) do
 207                         if p isa MMethod then methods += 1
 208                 end
 209                 nb_methods_total.add_all(nb_methods)
 210                 nb_methods_total.push(methods)
 211
 212                 vtable.internal_vtable = v.memory_manager.init_vtable(ids_total, nb_methods_total, vtable.mask)
 213         end
 214 end
 215
 216 # A VTable contains the virtual method table for the dispatch
 217 # and informations to perform subtyping tests
 218 class VTable
 219         # The mask to perform perfect hashing
 220         var mask: Int
 221
 222         # Unique identifier given by perfect hashing
 223         var id: Int
 224
 225         # Pointer to the c-allocated area, represents the virtual table
 226         var internal_vtable: Pointer
 227
 228         # The short classname of this class
 229         var classname: String
 230
 231         init do end
 232 end
 233
 234 redef class Instance
 235         var vtable: nullable VTable
 236 end
 237
 238 # Handle memory, used for allocate virtual table and associated structures
 239 class MemoryManager
 240
 241         # Allocate and fill a virtual table
 242         fun init_vtable(ids: Array[Int], nb_methods: Array[Int], mask: Int): Pointer
 243         do
 244                 # Allocate in C current virtual table
 245                 var res = intern_init_vtable(ids, nb_methods, mask)
 246
 247                 return res
 248         end
 249
 250         # Construct virtual tables with a bi-dimensional layout
 251         private fun intern_init_vtable(ids: Array[Int], nb_methods: Array[Int], mask: Int): Pointer
 252                 import Array[Int].length, Array[Int].[] `{
 253
 254                 // Allocate and fill current virtual table
 255                 int i;
 256                 int total_size = 0; // total size of this virtual table
 257                 int nb_classes = Array_of_Int_length(nb_methods);
 258                 for(i = 0; i<nb_classes; i++) {
 259                         /* - One for each method of this class
 260                         *  - One for the delta (offset of this group of attributes in objects)
 261                         *  - One for the id
 262                         */
 263                         total_size += Array_of_Int__index(nb_methods, i);
 264                         total_size += 2;
 265                 }
 266
 267                 // Add the size of the perfect hashtable
 268                 total_size += mask+1;
 269                 long unsigned int* vtable = malloc(sizeof(long unsigned int)*total_size);
 270
 271                 // Initialisation to the first position of the virtual table (ie : Object)
 272                 long unsigned int *init = vtable + mask + 2;
 273                 for(i=0; i<total_size; i++)
 274                         vtable[i] = (long unsigned int)init;
 275
 276                 // Set the virtual table to its position 0
 277                 // ie: after the hashtable
 278                 vtable = vtable + mask + 1;
 279
 280                 int current_size = 1;
 281                 for(i = 0; i < nb_classes; i++) {
 282                         /*
 283                                 vtable[hv] contains a pointer to the group of introducted methods
 284                                 For each superclasse we have in virtual table :
 285                                         (id | delta | introduced methods)
 286                         */
 287                         int hv = mask & Array_of_Int__index(ids, i);
 288
 289                         vtable[current_size] = Array_of_Int__index(ids, i);
 290                         vtable[-hv] = (long unsigned int)&(vtable[current_size]);
 291
 292                         current_size += 2;
 293                         current_size += Array_of_Int__index(nb_methods, i);
 294                 }
 295
 296                 return vtable;
 297         `}
 298 end