src/metamodel/inheritance.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2004-2008 Jean Privat <jean@pryen.org>
   4 # Copyright 2006-2008 Floréal Morandat <morandat@lirmm.fr>
   5 #
   6 # Licensed under the Apache License, Version 2.0 (the "License");
   7 # you may not use this file except in compliance with the License.
   8 # You may obtain a copy of the License at
   9 #
  10 #     http://www.apache.org/licenses/LICENSE-2.0
  11 #
  12 # Unless required by applicable law or agreed to in writing, software
  13 # distributed under the License is distributed on an "AS IS" BASIS,
  14 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15 # See the License for the specific language governing permissions and
  16 # limitations under the License.
  17
  18 # Compute importation of classes and inheritance of properties
  19 package inheritance
  20
  21 intrude import static_type
  22
  23 redef class MMModule
  24         # The root of the class hierarchy
  25         meth type_any: MMType
  26         do
  27                 var c_name = class_by_name(once ("Object".to_symbol))
  28                 return c_name.get_type
  29         end
  30
  31         # Import global classes from supermodules
  32         meth import_global_classes
  33         do
  34                 var globals = new HashMap[MMGlobalClass,HashSet[MMLocalClass]]
  35                 assert mhe != null
  36                 for mod in mhe.direct_greaters do
  37                         for glob in mod.global_classes do
  38                                 if global_classes.has(glob) then continue
  39                                 _global_classes.add(glob)
  40                                 _global_class_by_name[glob.name] = glob
  41                         end
  42                 end
  43
  44         end
  45
  46         # Create implicit local classes for global classes that are not refined
  47         meth import_local_classes
  48         do
  49                 for g in _global_classes do
  50                         if self[g] != null then continue
  51                         var impl = new MMImplicitLocalClass(self, g)
  52                 end
  53         end
  54 end
  55
  56 redef class MMLocalClass
  57         # List of all parents
  58         attr _direct_parents: Array[MMAncestor] = new Array[MMAncestor]
  59
  60         # Is the class computing super.
  61         # Used to detect specialization loops.
  62         attr _computing_super: Bool
  63
  64         # Compute super classes of a class
  65         meth compute_super_classes
  66         do
  67                 if computed_super_classes then
  68                         # do no recompute if allready done
  69                         return
  70                 else if _computing_super then
  71                         stderr.write("Fatal error: Inheritance loop for class {self}\n")
  72                         exit(1)
  73                 end
  74                 _computing_super = true
  75
  76                 var supers = new Array[MMLocalClass]
  77                 add_explicit_classes(supers)
  78                 add_super_classes(supers)
  79                 add_default_any_class(supers)
  80                 compute_super_parents(supers)
  81                 var set = new HashSet[MMLocalClass]
  82                 set.add_all(supers)
  83                 var u = set.to_a
  84                 module.set_supers_class(self,u)
  85                 assert _crhe != null
  86                 assert _cshe != null
  87                 _computing_super = false
  88         end
  89
  90         # Compute ancestors for a class
  91         meth compute_ancestors
  92         do
  93                 assert computed_super_classes
  94                 if computed_ancestors then return
  95
  96                 var ancestors = group_ancestors(build_ancestors)
  97                 _ancestors = new HashMap[MMLocalClass, MMAncestor]
  98
  99                 for set in ancestors do
 100                         if set.length == 1 then
 101                                 add_ancestor(set.first)
 102                         else
 103                                 var ma = merge_ancestors(set)
 104                                 add_ancestor(merge_ancestors(set))
 105                         end
 106                 end
 107         end
 108
 109         # Inherit global properties for a class
 110         meth inherit_global_properties
 111         do
 112                 if _global_properties != null then return
 113
 114                 _global_properties = new HashSet[MMGlobalProperty]
 115                 _properties_by_name = new HashMap[Symbol, Array[MMGlobalProperty]]
 116                 _local_property_by_global = new HashMap[MMGlobalProperty, MMLocalProperty]
 117
 118                 var names = _properties_by_name
 119                 var set = _global_properties
 120                 for c in che.direct_greaters do
 121                         for glob in c.global_properties do
 122                                 if set.has(glob) then continue
 123
 124                                 set.add(glob) # Add the global property
 125
 126                                 # Do not inherit constructors trough specialization
 127                                 #print "{c.module}::{c} -> {module}::{self} for {glob.local_property.local_class.module}::{glob.local_property.local_class}::{glob.local_property} : {glob.is_init}"
 128                                 if glob.is_init and glob.intro.local_class.global != global then
 129                                         #print "pass"
 130                                         continue
 131                                 end
 132
 133                                 var gname = glob.intro.name
 134                                 var conf_set: Array[MMGlobalProperty]
 135                                 if names.has_key(gname) then
 136                                         conf_set = names[gname]
 137                                 else
 138                                         conf_set = new Array[MMGlobalProperty]
 139                                         names[gname] = conf_set
 140                                 end
 141                                 conf_set.add(glob)
 142                         end
 143                 end
 144         end
 145
 146         # Add super stype of this current local class
 147         meth add_direct_parent(p: MMAncestor)
 148         do
 149                 _direct_parents.add(p)
 150         end
 151
 152         # Are super-class already computed?
 153         meth computed_super_classes: Bool
 154         do
 155                 return _crhe != null and _cshe != null
 156         end
 157
 158         # Are ancestors already computed
 159         meth computed_ancestors: Bool
 160         do
 161                 return _ancestors != null
 162         end
 163
 164         # Get the ancestor for a given class
 165         # TODO: is this useful?
 166         private meth ancestor_for(c: MMLocalClass): MMAncestor
 167         do
 168                 assert ancestors != null
 169
 170                 if _ancestors.has_key(c) then
 171                         return _ancestors[c]
 172                 end
 173                 var a = c.for_module(module)
 174                 assert cshe <= a
 175                 var ra: MMAncestor
 176                 if _ancestors.has_key(a) then
 177                         ra = _ancestors[a]
 178                 else if c.global == _global then
 179                         ra = new MMRefineAncestor(self,c)
 180                 else
 181                         ra = new MMSpecAncestor(get_type,c.get_type)
 182                 end
 183                 _ancestors[c] = ra
 184                 return ra
 185         end
 186
 187         redef meth [](glob)
 188         do
 189                 var prop = super(glob)
 190                 if prop == null and _global_properties.has(glob) then
 191                         prop = inherit_local_property(glob)
 192                 end
 193                 return prop
 194         end
 195
 196         # Add default super class in direct parent and in super classes if this is not the Object class
 197         private meth add_default_any_class(supers: Array[MMLocalClass])
 198         do
 199                 if supers.is_empty and name != once ("Object".to_symbol) then
 200                         var t_any = module.type_any
 201                         supers.add(t_any.local_class)
 202                         var default = new MMDefaultAncestor(self, t_any)
 203                         add_direct_parent(default)
 204                 end
 205         end
 206
 207         # Adding inherited class from previous refinement of self
 208         private meth add_super_classes(supers: Array[MMLocalClass])
 209         do
 210                 assert _crhe != null
 211                 for ref in _crhe.direct_greaters do
 212                         assert ref.cshe != null
 213                         for sup in ref.cshe.direct_greaters do
 214                                 var cla = sup.for_module(_module)
 215                                 assert cla != null
 216                                 supers.add(cla)
 217                         end
 218                 end
 219         end
 220
 221         # Add self parents of this local class
 222         private meth add_explicit_classes(supers: Array[MMLocalClass])
 223         do
 224                 for p in _direct_parents do
 225                         supers.add(p.local_class)
 226                 end
 227         end
 228
 229         # Ensure all super parents are computed
 230         private meth compute_super_parents(supers: Array[MMLocalClass])
 231         do
 232                 for p in supers do
 233                         assert p != null
 234                         p.compute_super_classes
 235                 end
 236         end
 237
 238         # compute all ancestors for a class (multiple)
 239         private meth build_ancestors: Array[MMAncestor]
 240         do
 241                 var all_ancestors = new Array[MMAncestor]
 242                 # Refined classes are ancestors
 243                 assert _crhe != null
 244                 for p in _crhe.direct_greaters do
 245                         assert p != self
 246                         var anc = new MMRefineAncestor(self, p)
 247                         anc.add_in(all_ancestors)
 248                 end
 249                 for anc in _direct_parents do
 250                         assert anc.local_class != self
 251                         anc.add_in(all_ancestors)
 252                 end
 253                 return all_ancestors
 254         end
 255
 256         # Build an ancestor map indexed by LocalClass
 257         private meth group_ancestors(all: Array[MMAncestor]): Map[MMLocalClass, Set[MMAncestor]]
 258         do
 259                 #print "process {self}"
 260                 var map = new HashMap[MMLocalClass, Set[MMAncestor]]
 261                 for a in all do
 262                         var c = a.local_class
 263                         #print "ancestor is"
 264                         #print "  {c}"
 265                         var set: Set[MMAncestor]
 266                         c.compute_ancestors
 267                         if map.has_key(c) then
 268                                 set = map[c]
 269                         else
 270                                 set = new HashSet[MMAncestor]
 271                                 map[c] = set
 272                         end
 273                         set.add(a)
 274                 end
 275                 return map
 276         end
 277
 278         # Remove duplicate ancestors and merge if compatible, in the other case do an error
 279         private meth merge_ancestors(set: Set[MMAncestor]): MMAncestor
 280         do
 281                 var marks = new HashSet[MMAncestor]
 282                 var res = new Array[MMAncestor]
 283                 for t in set do
 284                         var it = set.iterator
 285                         var search = true
 286                         while it.is_ok and search do
 287
 288                                 var a = t == it.item
 289                                 a = marks.has(it.item)
 290                                 a = it.item.stype < t.stype
 291
 292                                 if not(t == it.item or marks.has(it.item)) and
 293                                         (it.item.stype < t.stype) then
 294                                                 marks.add(t)
 295                                                 search = false
 296                                 end
 297                                 it.next
 298                         end
 299                         if not marks.has(t) then
 300                                 res.add(t)
 301                         end
 302                 end
 303
 304                 if res.length > 1 then
 305                         stderr.write("Fatal error: Incompatibles ancestors for {self.name}: {res.join(", ")}\n")
 306                         exit(1)
 307                 end
 308                 return res.first
 309         end
 310
 311         # Inherit a local property
 312         # Is lazily called
 313         # FIXME: dont crash lazily
 314         private meth inherit_local_property(glob: MMGlobalProperty): MMLocalProperty
 315         do
 316                 assert not _local_property_by_global.has_key(glob)
 317                 assert glob != null
 318
 319                 var impls = glob.get_compatible_concrete_properties_for(self)
 320                 if impls.length != 1 then
 321                         stderr.write("Fatal error: inherit_local_property error\n")
 322                         print("------- {module}::{self} {glob.intro.full_name}")
 323                         for i in impls do
 324                                 print("   {i.full_name}")
 325                         end
 326                         print("------- {glob.concrete_property_hierarchy.first}")
 327                         print("------- {glob.concrete_property_hierarchy.to_dot}")
 328                         exit(1)
 329                 end
 330                 var impl = impls.first
 331                 var ac = ancestor_for(impl.local_class)
 332                 ac.local_class.inherit_global_properties
 333                 var a = ac.stype
 334
 335                 assert a.local_class != self
 336                 var sup = a.select_property(glob) # Select super prop
 337                 assert sup != null
 338                 return sup
 339         end
 340 end
 341
 342 redef class MMConcreteProperty
 343         # FIXME: use this
 344         meth is_deferred: Bool do return false
 345 end
 346
 347 redef class MMGlobalProperty
 348         # Get the most specific local properties defined in superclasses of c
 349         private meth get_compatible_concrete_properties_for(cla: MMLocalClass): Array[MMConcreteProperty]
 350         do
 351                 var impl_hier = _concrete_property_hierarchy
 352                 if impl_hier.length == 1 then return [intro]
 353                 var impls = new ArraySet[MMConcreteProperty]
 354                 var clache = cla.che
 355                 if true then
 356                         #print "{cla.module}::{cla} get glob {intro.local_class}::{intro.name}"
 357                 for sc in cla.che.direct_greaters do
 358                         #print "   try {sc.module}::{sc} {sc.che != null} {sc.crhe != null} {sc.che != null}"
 359                         var p = sc[self]
 360                         if p == null then continue
 361                         var impl = p.concrete_property
 362                         impls.add(impl)
 363                 end
 364                 else
 365                 for impl in impl_hier do
 366                         var bc = impl.local_class
 367                         if clache < bc then
 368                                 impls.add(impl)
 369                         end
 370                 end
 371                 end
 372                 return impl_hier.select_smallests(impls)
 373         end
 374 end
 375
 376 redef class MMLocalProperty
 377         # Attach self to a global property
 378         meth inherit_global(g: MMGlobalProperty)
 379         do
 380                 set_global(g)
 381                 # What the next line used for?
 382                 g.add_concrete_property(concrete_property, g.get_compatible_concrete_properties_for(local_class))
 383         end
 384 end
 385
 386 redef class MMAncestor
 387         # Add this ancestor and it's super one in tab
 388         private meth add_in(tab: Array[MMAncestor])
 389         do
 390                 assert ancestor: stype != null
 391                 assert local_class: stype.local_class != null
 392                 tab.add(self)
 393                 stype.local_class.compute_ancestors
 394                 for anc in stype.local_class.ancestors do
 395                         var aaa = anc.stype.for_module(stype.module)
 396                         var a = aaa.adapt_to(stype).for_module(inheriter.module)
 397                         if a.local_class != inheriter.local_class then
 398                                 var it = tab.iterator
 399                                 var b = true
 400                                 while it.is_ok and b do
 401                                         b = not ( it.item.inheriter == inheriter and it.item.stype == a)
 402                                         it.next
 403                                 end
 404                                 if b then
 405                                         tab.add(new MMSpecAncestor(inheriter,a))
 406                                 end
 407                         end
 408                 end
 409         end
 410 end
 411
 412 ##########################################
 413
 414 # A local class that is a pure importation of an other local class
 415 class MMImplicitLocalClass
 416 special MMLocalClass
 417         init(mod: MMModule, g: MMGlobalClass)
 418         do
 419                 var cla = g.intro
 420                 super(cla.name, cla.arity)
 421                 mod.add_local_class(self)
 422                 set_global(g)
 423         end
 424 end
 425
 426 class MMRefineAncestor
 427 special MMAncestor
 428         redef readable attr _local_class: MMLocalClass
 429
 430         init(b: MMLocalClass, a: MMLocalClass)
 431         do
 432                 _local_class = a
 433                 inheriter = b.get_type
 434                 stype = _local_class.get_type
 435         end
 436 end
 437
 438
 439 class MMSpecAncestor
 440 special MMAncestor
 441         redef meth local_class do return stype.local_class
 442
 443         init(inheriter: MMType, stype: MMType)
 444         do
 445                 _inheriter = inheriter
 446                 _stype = stype
 447         end
 448 end
 449
 450 class MMDefaultAncestor
 451 special MMAncestor
 452         redef meth local_class do return stype.local_class
 453
 454         init(b: MMLocalClass, anc: MMType)
 455         do
 456                 assert b != null
 457                 assert b.module != null
 458                 assert anc != null
 459                 inheriter = b.get_type
 460                 stype = anc
 461         end
 462 end