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 impl: MMLocalProperty
 320
 321                 var ghier = glob.concrete_property_hierarchy
 322                 var supers = che.direct_greaters
 323                 if ghier.length == 1 then
 324                         # Unredefined property
 325                         impl = glob.intro
 326                 else if supers.length == 1 then
 327                         # Single inheritance
 328                         impl = supers.first[glob]
 329                 else
 330                         # Hard multiple inheritance
 331                         # First compute the set of bottom properties
 332                         var impls = new ArraySet[MMConcreteProperty]
 333                         for sc in supers do
 334                                 var p = sc[glob]
 335                                 assert p isa MMConcreteProperty
 336                                 if p != null then impls.add(p)
 337                         end
 338                         # Second, extract most specific
 339                         var impls2 = ghier.select_smallests(impls)
 340                         # Conflict case (FIXME)
 341                         if impls2.length != 1 then
 342                                 stderr.write("Fatal error: inherit_local_property error\n")
 343                                 print("------- {module}::{self} {glob.intro.full_name}")
 344                                 for i in impls2 do
 345                                         print("   {i.full_name}")
 346                                 end
 347                                 print("------- {glob.concrete_property_hierarchy.first}")
 348                                 print("------- {glob.concrete_property_hierarchy.to_dot}")
 349                                 exit(1)
 350                         end
 351                         impl = impls2.first
 352                 end
 353
 354                 # FIXME: Why these 3 lines ?
 355                 #var ac = ancestor_for(impl.local_class)
 356                 #ac.local_class.inherit_global_properties
 357                 #var a = ac.stype
 358                 #assert a.local_class != self
 359
 360                 # Register the local property
 361                 _local_property_by_global[glob] = impl
 362
 363                 return impl
 364         end
 365 end
 366
 367 redef class MMConcreteProperty
 368         # FIXME: use this
 369         meth is_deferred: Bool do return false
 370 end
 371
 372 redef class MMLocalProperty
 373         # Attach self to a global property
 374         meth inherit_global(g: MMGlobalProperty)
 375         do
 376                 set_global(g)
 377                 var impls = new Array[MMConcreteProperty]
 378                 for sc in local_class.che.direct_greaters do
 379                         var p = sc[g]
 380                         if p == null then continue
 381                         assert p isa MMConcreteProperty
 382                         impls.add(p)
 383                 end
 384                 g.add_concrete_property(concrete_property, impls)
 385         end
 386 end
 387
 388 redef class MMAncestor
 389         # Add this ancestor and it's super one in tab
 390         private meth add_in(tab: Array[MMAncestor])
 391         do
 392                 assert ancestor: stype != null
 393                 assert local_class: stype.local_class != null
 394                 tab.add(self)
 395                 stype.local_class.compute_ancestors
 396                 for anc in stype.local_class.ancestors do
 397                         var aaa = anc.stype.for_module(stype.module)
 398                         var a = aaa.adapt_to(stype).for_module(inheriter.module)
 399                         if a.local_class != inheriter.local_class then
 400                                 var it = tab.iterator
 401                                 var b = true
 402                                 while it.is_ok and b do
 403                                         b = not ( it.item.inheriter == inheriter and it.item.stype == a)
 404                                         it.next
 405                                 end
 406                                 if b then
 407                                         tab.add(new MMSpecAncestor(inheriter,a))
 408                                 end
 409                         end
 410                 end
 411         end
 412 end
 413
 414 ##########################################
 415
 416 # A local class that is a pure importation of an other local class
 417 class MMImplicitLocalClass
 418 special MMLocalClass
 419         init(mod: MMModule, g: MMGlobalClass)
 420         do
 421                 var cla = g.intro
 422                 super(cla.name, cla.arity)
 423                 mod.add_local_class(self)
 424                 set_global(g)
 425         end
 426 end
 427
 428 class MMRefineAncestor
 429 special MMAncestor
 430         redef readable attr _local_class: MMLocalClass
 431
 432         init(b: MMLocalClass, a: MMLocalClass)
 433         do
 434                 _local_class = a
 435                 inheriter = b.get_type
 436                 stype = _local_class.get_type
 437         end
 438 end
 439
 440
 441 class MMSpecAncestor
 442 special MMAncestor
 443         redef meth local_class do return stype.local_class
 444
 445         init(inheriter: MMType, stype: MMType)
 446         do
 447                 _inheriter = inheriter
 448                 _stype = stype
 449         end
 450 end
 451
 452 class MMDefaultAncestor
 453 special MMAncestor
 454         redef meth local_class do return stype.local_class
 455
 456         init(b: MMLocalClass, anc: MMType)
 457         do
 458                 assert b != null
 459                 assert b.module != null
 460                 assert anc != null
 461                 inheriter = b.get_type
 462                 stype = anc
 463         end
 464 end