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 for this class
 171                         var count = 0
 172                         var min_visibility = public_visibility
 173                         for p in parent.intro_mproperties(min_visibility) do
 174                                 if p isa MMethod then
 175                                         count += 1
 176                                 end
 177                         end
 178
 179                         ids.push(parent.vtable.id)
 180                         nb_methods.push(count)
 181                 end
 182
 183                 # When all super-classes have their identifiers and vtables, allocate current one
 184                 allocate_vtable(v, ids, nb_methods)
 185                 loaded = true
 186                 # The virtual table now needs to be filled with pointer to methods
 187         end
 188
 189         # Allocate a single vtable
 190         #       ids : Array of superclasses identifiers
 191         #       nb_methods : Array which contain the number of methods for each class in ids
 192         private fun allocate_vtable(v: VirtualMachine, ids: Array[Int], nb_methods: Array[Int])
 193         do
 194                 vtable = new VTable
 195                 var idc = new Array[Int]
 196
 197                 vtable.mask = v.ph.pnand(ids, 1, idc) - 1
 198                 vtable.id = idc[0]
 199                 vtable.classname = name
 200
 201                 # Add current id to Array of super-ids
 202                 var ids_total = new Array[Int]
 203                 ids_total.add_all(ids)
 204                 ids_total.push(vtable.id)
 205
 206                 var nb_methods_total = new Array[Int]
 207                 var count = 0
 208                 var min_visibility = public_visibility
 209                 for p in intro_mproperties(min_visibility) do
 210                         if p isa MMethod then
 211                                 count += 1
 212                         end
 213                 end
 214                 nb_methods_total.add_all(nb_methods)
 215                 nb_methods_total.push(count)
 216
 217                 vtable.internal_vtable = v.memory_manager.init_vtable(ids_total, nb_methods_total, vtable.mask)
 218         end
 219 end
 220
 221 # A VTable contains the virtual method table for the dispatch
 222 # and informations to perform subtyping tests
 223 class VTable
 224         # The mask to perform perfect hashing
 225         var mask: Int
 226
 227         # Unique identifier given by perfect hashing
 228         var id: Int
 229
 230         # Pointer to the c-allocated area, represents the virtual table
 231         var internal_vtable: Pointer
 232
 233         # The short classname of this class
 234         var classname: String
 235
 236         init do end
 237 end
 238
 239 redef class Instance
 240
 241         var vtable: nullable VTable
 242
 243         init(mt: MType)
 244         do
 245                 mtype = mt
 246
 247                 # An instance is associated to its class virtual table
 248                 if mt isa MClassType then
 249                         vtable = mt.mclass.vtable
 250                 end
 251         end
 252 end
 253
 254 # Handle memory, used for allocate virtual table and associated structures
 255 class MemoryManager
 256
 257         # Allocate and fill a virtual table
 258         fun init_vtable(ids: Array[Int], nb_methods: Array[Int], mask: Int): Pointer
 259         do
 260                 # Allocate in C current virtual table
 261                 var res = intern_init_vtable(ids, nb_methods, mask)
 262
 263                 return res
 264         end
 265
 266         # Construct virtual tables with a bi-dimensional layout
 267         private fun intern_init_vtable(ids: Array[Int], nb_methods: Array[Int], mask: Int): Pointer
 268                 import Array[Int].length, Array[Int].[] `{
 269
 270                 // Allocate and fill current virtual table
 271                 int i;
 272                 int total_size = 0; // total size of this virtual table
 273                 int nb_classes = Array_of_Int_length(nb_methods);
 274                 for(i = 0; i<nb_classes; i++) {
 275                         /* - One for each method of this class
 276                         *  - One for the delta (pointer to attributes)
 277                         *  - One for the id
 278                         */
 279                         total_size += Array_of_Int__index(nb_methods, i);
 280                         total_size += 2;
 281                 }
 282
 283                 // And the size of the perfect hashtable
 284                 total_size += mask+1;
 285                 long unsigned int* vtable = malloc(sizeof(long unsigned int)*total_size);
 286
 287                 // Initialisation to the first position of the virtual table (ie : Object)
 288                 long unsigned int *init = vtable + mask + 2;
 289                 for(i=0; i<total_size; i++)
 290                         vtable[i] = (long unsigned int)init;
 291
 292                 // Set the virtual table to its position 0
 293                 // ie: after the hashtable
 294                 vtable = vtable + mask + 1;
 295
 296                 int current_size = 1;
 297                 for(i = 0; i < nb_classes; i++) {
 298                         /*
 299                                 vtable[hv] contains a pointer to the group of introducted methods
 300                                 For each superclasse we have in virtual table :
 301                                         (id | delta (attributes) | introduced methods)
 302                         */
 303                         int hv = mask & Array_of_Int__index(ids, i);
 304
 305                         vtable[current_size] = Array_of_Int__index(ids, i);
 306                         vtable[-hv] = (long unsigned int)&(vtable[current_size]);
 307
 308                         current_size += 2;
 309                         current_size += Array_of_Int__index(nb_methods, i);
 310                 }
 311
 312                 return vtable;
 313         `}
 314 end