src/layout_builders.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Licensed under the Apache License, Version 2.0 (the "License");
   4 # you may not use this file except in compliance with the License.
   5 # You may obtain a copy of the License at
   6 #
   7 #     http://www.apache.org/licenses/LICENSE-2.0
   8 #
   9 # Unless required by applicable law or agreed to in writing, software
  10 # distributed under the License is distributed on an "AS IS" BASIS,
  11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 # See the License for the specific language governing permissions and
  13 # limitations under the License.
  14
  15 # Table layout builders
  16 module layout_builders
  17
  18 import abstract_compiler
  19
  20 # Layouts
  21
  22 class Layout[E: Object]
  23         # Ids or each element
  24         var ids: Map[E, Int] = new HashMap[E, Int]
  25         # Fixed positions of each element in all tables
  26         var pos: Map[E, Int] = new HashMap[E, Int]
  27 end
  28
  29 class PHLayout[HOLDER: Object, E: Object]
  30         super Layout[E]
  31         # Masks used by hash function
  32         var masks: Map[HOLDER, Int] = new HashMap[HOLDER, Int]
  33         # Positions of each element for each tables
  34         var hashes: Map[HOLDER, Map[E, Int]] = new HashMap[HOLDER, Map[E, Int]]
  35 end
  36
  37 class PropertyLayout[E: Object]
  38         # Fixed positions of each element in all tables
  39         var pos: Map[E, Int] = new HashMap[E, Int]
  40 end
  41
  42 # Builders
  43
  44 interface TypingLayoutBuilder[E: Object]
  45         # Build typing table layout
  46         fun build_layout(elements: Set[E]): Layout[E] is abstract
  47 end
  48
  49 interface PropertyLayoutBuilder[E: MProperty]
  50         # Build table layout for attributes, methods and virtual types
  51         fun build_layout(elements: Set[MClass]): Layout[E] is abstract
  52 end
  53
  54 interface ResolutionLayoutBuilder
  55         # Build resolution table layout
  56         fun build_layout(elements: Map[MClassType, Set[MType]]): Layout[MType] is abstract
  57 end
  58
  59 # Matrice computers
  60
  61 abstract class TypingBMizer[E: Object]
  62         super TypingLayoutBuilder[E]
  63
  64         var mmodule: MModule
  65
  66         init(mmodule: MModule) do
  67                 self.mmodule = mmodule
  68         end
  69
  70         # Compute mtypes ids and position using BM
  71         redef fun build_layout(elements: Set[E]): Layout[E] do
  72                 var result = new Layout[E]
  73                 var ids = new HashMap[E, Int]
  74                 var lin = self.reverse_linearize(elements)
  75                 for element in lin do
  76                         ids[element] = ids.length
  77                 end
  78                 result.ids = ids
  79                 result.pos = ids
  80                 return result
  81         end
  82
  83         private fun reverse_linearize(elements: Set[E]): Array[E] is abstract
  84 end
  85
  86 class MTypeBMizer
  87         super TypingBMizer[MType]
  88
  89         init(mmodule: MModule) do super(mmodule)
  90
  91         redef fun reverse_linearize(elements) do
  92                 return self.mmodule.reverse_linearize_mtypes(elements)
  93         end
  94 end
  95
  96 class MClassBMizer
  97         super TypingBMizer[MClass]
  98
  99         init(mmodule: MModule) do super(mmodule)
 100
 101         redef fun reverse_linearize(elements) do
 102                 return self.mmodule.reverse_linearize_mclasses(elements)
 103         end
 104 end
 105
 106 # Layout builder for resolution tables using Binary Matrix (BM)
 107 class ResolutionBMizer
 108         super ResolutionLayoutBuilder
 109
 110         init do end
 111
 112         redef fun build_layout(elements) do
 113                 var result = new Layout[MType]
 114                 var ids = new HashMap[MType, Int]
 115                 var color = 0
 116                 for mclasstype, mclasstypes in elements do
 117                         for element in mclasstypes do
 118                                 if ids.has_key(element) then continue
 119                                 ids[element] = color
 120                                 color += 1
 121                         end
 122                 end
 123                 result.ids = ids
 124                 result.pos = ids
 125                 return result
 126         end
 127 end
 128
 129 # Colorers
 130
 131 abstract class TypingColorer[E: Object]
 132         super TypingLayoutBuilder[E]
 133
 134         private var core: Set[E] = new HashSet[E]
 135         private var crown: Set[E] = new HashSet[E]
 136         private var border: Set[E] = new HashSet[E]
 137
 138         private var coloration_result: Map[E, Int] = new HashMap[E, Int]
 139
 140         init do end
 141
 142         # Compute the layout with coloring
 143         redef fun build_layout(elements: Set[E]): Layout[E] do
 144                 var result = new Layout[E]
 145                 result.ids = compute_ids(elements)
 146                 result.pos = colorize(elements)
 147                 return result
 148         end
 149
 150         private fun compute_ids(elements: Set[E]): Map[E, Int] do
 151                 var ids = new HashMap[E, Int]
 152                 var lin = reverse_linearize(elements)
 153                 for element in lin do
 154                         ids[element] = ids.length
 155                 end
 156                 return ids
 157         end
 158
 159         private fun colorize(elements: Set[E]): Map[E, Int] do
 160                 tag_elements(elements)
 161                 build_conflicts_graph(elements)
 162                 colorize_elements(core)
 163                 colorize_elements(border)
 164                 colorize_elements(crown)
 165                 return coloration_result
 166         end
 167
 168         # Colorize a collection of elements
 169         private fun colorize_elements(elements: Set[E]) do
 170                 var min_color = 0
 171
 172                 var lin = reverse_linearize(elements)
 173                 for element in lin do
 174                         var color = min_color
 175                         while not self.is_color_free(element, elements, color) do
 176                                 color += 1
 177                         end
 178                         coloration_result[element] = color
 179                         color = min_color
 180                 end
 181         end
 182
 183         # Check if a related element to the element already use the color
 184         private fun is_color_free(element: E, elements: Set[E], color: Int): Bool do
 185                 if conflicts_graph.has_key(element) then
 186                         for st in conflicts_graph[element] do
 187                                 if coloration_result.has_key(st) and coloration_result[st] == color then return false
 188                         end
 189                 end
 190                 for st in self.super_elements(element, elements) do
 191                         if coloration_result.has_key(st) and coloration_result[st] == color then return false
 192                 end
 193                 return true
 194         end
 195
 196         # Tag elements as core, crown or border
 197         private fun tag_elements(elements: Set[E]) do
 198                 for element in elements do
 199                         # Check if sub elements are all in single inheritance
 200                         var all_subelements_si = true
 201                         for subelem in self.sub_elements(element, elements) do
 202                                 if self.is_element_mi(subelem, elements) then
 203                                         all_subelements_si = false
 204                                         break
 205                                 end
 206                         end
 207
 208                         # Tag as core, crown or border
 209                         if self.is_element_mi(element, elements) then
 210                                 core.add_all(self.super_elements(element, elements))
 211                                 core.add(element)
 212                                 if all_subelements_si then
 213                                         border.add(element)
 214                                 end
 215                         else if not all_subelements_si then
 216                                 core.add_all(self.super_elements(element, elements))
 217                                 core.add(element)
 218                         else
 219                                 crown.add(element)
 220                         end
 221                 end
 222         end
 223
 224         # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
 225         private fun build_conflicts_graph(elements: Set[E]) do
 226                 self.conflicts_graph = new HashMap[E, HashSet[E]]
 227                 var core = reverse_linearize(self.core)
 228                 for t in core do
 229                         for i in self.linear_extension(t, elements) do
 230                                 if t == i then continue
 231
 232                                 var lin_i = self.linear_extension(i, elements)
 233
 234                                 for j in self.linear_extension(t, elements) do
 235                                         if i == j or j == t then continue
 236                                         var lin_j = self.linear_extension(j, elements)
 237
 238                                         var d_ij = lin_i - lin_j
 239                                         var d_ji = lin_j - lin_i
 240
 241                                         for ed1 in d_ij do
 242                                                 if not conflicts_graph.has_key(ed1) then conflicts_graph[ed1] = new HashSet[E]
 243                                                 # add ed1 x ed2 to conflicts graph
 244                                                 for ed2 in d_ji do conflicts_graph[ed1].add(ed2)
 245                                         end
 246                                         for ed1 in d_ij do
 247                                                 if not conflicts_graph.has_key(ed1) then conflicts_graph[ed1] = new HashSet[E]
 248                                                 # add ed1 x ed2 to conflicts graph
 249                                                 for ed2 in d_ji do conflicts_graph[ed1].add(ed2)
 250                                         end
 251                                 end
 252                         end
 253                 end
 254         end
 255
 256         private var conflicts_graph: nullable HashMap[E, Set[E]]
 257
 258         # cache for linear_extensions
 259         private var linear_extensions_cache: Map[E, Array[E]] = new HashMap[E, Array[E]]
 260
 261         # Return a linear_extension of super_elements of the element
 262         private fun linear_extension(element: E, elements: Set[E]): Array[E] do
 263                 if not self.linear_extensions_cache.has_key(element) then
 264                         var supers = new HashSet[E]
 265                         supers.add(element)
 266                         supers.add_all(self.super_elements(element, elements))
 267                         self.linear_extensions_cache[element] = self.linearize(supers)
 268                 end
 269                 return self.linear_extensions_cache[element]
 270         end
 271
 272         private fun super_elements(element: E, elements: Set[E]): Set[E] is abstract
 273         private fun sub_elements(element: E, elements: Set[E]): Set[E] is abstract
 274         private fun is_element_mi(element: E, elements: Set[E]): Bool is abstract
 275         private fun linearize(elements: Set[E]): Array[E] is abstract
 276         private fun reverse_linearize(elements: Set[E]): Array[E] is abstract
 277 end
 278
 279 # MType coloring
 280 class MTypeColorer
 281         super TypingColorer[MType]
 282
 283         var mmodule: MModule
 284
 285         init(mmodule: MModule) do self.mmodule = mmodule
 286
 287         redef fun super_elements(element, elements) do return self.mmodule.super_mtypes(element, elements)
 288         redef fun is_element_mi(element, elements) do return self.super_elements(element, elements).length > 1
 289         redef fun sub_elements(element, elements) do do return self.mmodule.sub_mtypes(element, elements)
 290         redef fun linearize(elements) do return self.mmodule.linearize_mtypes(elements)
 291         redef fun reverse_linearize(elements) do return self.mmodule.reverse_linearize_mtypes(elements)
 292 end
 293
 294 # MClass coloring
 295 class MClassColorer
 296         super TypingColorer[MClass]
 297
 298         private var mmodule: MModule
 299
 300         init(mmodule: MModule) do self.mmodule = mmodule
 301
 302         redef fun super_elements(element, elements) do return self.mmodule.super_mclasses(element)
 303         fun parent_elements(element: MClass): Set[MClass] do return self.mmodule.parent_mclasses(element)
 304         redef fun is_element_mi(element, elements) do return self.parent_elements(element).length > 1
 305         redef fun sub_elements(element, elements) do do return self.mmodule.sub_mclasses(element)
 306         redef fun linearize(elements) do return self.mmodule.linearize_mclasses(elements)
 307         redef fun reverse_linearize(elements) do return self.mmodule.reverse_linearize_mclasses(elements)
 308 end
 309
 310 # MProperty coloring
 311 abstract class MPropertyColorer[E: MProperty]
 312         super PropertyLayoutBuilder[E]
 313
 314         private var mmodule: MModule
 315         private var class_colorer: MClassColorer
 316         private var coloration_result: Map[E, Int] = new HashMap[E, Int]
 317
 318         init(mmodule: MModule) do
 319                 self.mmodule = mmodule
 320                 self.class_colorer = new MClassColorer(mmodule)
 321         end
 322
 323         # Compute mclasses ids and position using BM
 324         redef fun build_layout(mclasses: Set[MClass]): Layout[E] do
 325                 var result = new Layout[E]
 326                 result.pos = self.colorize(mclasses)
 327                 return result
 328         end
 329
 330         private fun colorize(mclasses: Set[MClass]): Map[E, Int] do
 331                 self.class_colorer.tag_elements(mclasses)
 332                 self.class_colorer.build_conflicts_graph(mclasses)
 333                 self.colorize_core(self.class_colorer.core)
 334                 self.colorize_crown(self.class_colorer.crown)
 335                 return self.coloration_result
 336         end
 337
 338         # Colorize properties of the core hierarchy
 339         private fun colorize_core(mclasses: Set[MClass]) do
 340                 var min_color = 0
 341                 for mclass in mclasses do
 342                         var color = min_color
 343
 344                         # if the class is root, get the minimal color
 345                         if self.mmodule.parent_mclasses(mclass).length == 0 then
 346                                 colorize_elements(self.properties(mclass), color)
 347                         else
 348                                 # check last color used by parents
 349                                 color = max_color(color, self.mmodule.parent_mclasses(mclass))
 350                                 # check max color used in conflicts
 351                                 if self.class_colorer.conflicts_graph.has_key(mclass) then
 352                                         color = max_color(color, self.class_colorer.conflicts_graph[mclass])
 353                                 end
 354                                 colorize_elements(self.properties(mclass), color)
 355                         end
 356                 end
 357         end
 358
 359         # Colorize properties of the crown hierarchy
 360         private fun colorize_crown(mclasses: Set[MClass]) do
 361                 for mclass in mclasses do
 362                         colorize_elements(self.properties(mclass), max_color(0, self.mmodule.parent_mclasses(mclass)))
 363                 end
 364         end
 365
 366         # Colorize a collection of mproperties given a starting color
 367         private fun colorize_elements(elements: Collection[E], start_color: Int) do
 368                 for element in elements do
 369                         if self.coloration_result.has_key(element) then continue
 370                         self.coloration_result[element] = start_color
 371                         start_color += 1
 372                 end
 373         end
 374
 375         private fun max_color(min_color: Int, mclasses: Collection[MClass]): Int do
 376                 var max_color = min_color
 377
 378                 for mclass in mclasses do
 379                         for mproperty in self.properties(mclass) do
 380                                 var color = min_color
 381                                 if self.coloration_result.has_key(mproperty) then
 382                                         color = self.coloration_result[mproperty]
 383                                         if color >= max_color then max_color = color + 1
 384                                 end
 385                         end
 386                 end
 387                 return max_color
 388         end
 389
 390         # Filter properties
 391         private fun properties(mclass: MClass): Set[E] is abstract
 392 end
 393
 394 # Coloring for MMethods
 395 class MMethodColorer
 396         super MPropertyColorer[MMethod]
 397
 398         init(mmodule: MModule) do super
 399
 400         redef fun properties(mclass) do
 401                 var properties = new HashSet[MMethod]
 402                 for mprop in self.mmodule.properties(mclass) do
 403                         if mprop isa MMethod then properties.add(mprop)
 404                 end
 405                 return properties
 406         end
 407 end
 408
 409 # Coloring for MMAttributes
 410 class MAttributeColorer
 411         super MPropertyColorer[MAttribute]
 412
 413         init(mmodule: MModule) do super
 414
 415         redef fun properties(mclass) do
 416                 var properties = new HashSet[MAttribute]
 417                 for mprop in self.mmodule.properties(mclass) do
 418                         if mprop isa MAttribute then properties.add(mprop)
 419                 end
 420                 return properties
 421         end
 422 end
 423
 424 # Coloring for MVirtualTypeProps
 425 class MVirtualTypePropColorer
 426         super MPropertyColorer[MVirtualTypeProp]
 427
 428         init(mmodule: MModule) do super
 429
 430         redef fun properties(mclass) do
 431                 var properties = new HashSet[MVirtualTypeProp]
 432                 for mprop in self.mmodule.properties(mclass) do
 433                         if mprop isa MVirtualTypeProp then properties.add(mprop)
 434                 end
 435                 return properties
 436         end
 437 end
 438
 439 # Colorer for type resolution table
 440 class ResolutionColorer
 441         super ResolutionLayoutBuilder
 442
 443         private var coloration_result: Map[MType, Int] = new HashMap[MType, Int]
 444
 445         init do end
 446
 447         # Compute resolved types colors
 448         redef fun build_layout(elements) do
 449                 self.build_conflicts_graph(elements)
 450                 var result = new Layout[MType]
 451                 result.ids = self.compute_ids(elements)
 452                 result.pos = self.colorize_elements(elements)
 453                 return result
 454         end
 455
 456         private fun compute_ids(elements: Map[MClassType, Set[MType]]): Map[MType, Int] do
 457                 var ids = new HashMap[MType, Int]
 458                 var color = 0
 459                 for mclasstype, mclasstypes in elements do
 460                         for element in mclasstypes do
 461                                 if ids.has_key(element) then continue
 462                                 ids[element] = color
 463                                 color += 1
 464                         end
 465                 end
 466                 return ids
 467         end
 468
 469         # Colorize a collection of elements
 470         private fun colorize_elements(elements: Map[MClassType, Set[MType]]): Map[MType, Int] do
 471                 var min_color = 0
 472                 for mclasstype, mclasstypes in elements do
 473                         for element in mclasstypes do
 474                                 if self.coloration_result.has_key(element) then continue
 475                                 var color = min_color
 476                                 while not self.is_color_free(element, color) do
 477                                         color += 1
 478                                 end
 479                                 coloration_result[element] = color
 480                                 color = min_color
 481                         end
 482                 end
 483                 return self.coloration_result
 484         end
 485
 486         # Check if a related element to the element already use the color
 487         private fun is_color_free(element: MType, color: Int): Bool do
 488                 if conflicts_graph.has_key(element) then
 489                         for st in conflicts_graph[element] do
 490                                 if coloration_result.has_key(st) and coloration_result[st] == color then return false
 491                         end
 492                 end
 493                 return true
 494         end
 495
 496         # look for unanchored types generated by the same type
 497         private fun build_conflicts_graph(elements: Map[MClassType, Set[MType]]) do
 498                 for mclasstype, mtypes in elements do
 499                         for mtype in mtypes do
 500                                 for otype in mtypes do
 501                                         if otype == mtype then continue
 502                                         self.add_conflict(mtype, otype)
 503                                 end
 504                         end
 505                 end
 506         end
 507
 508         private var conflicts_graph: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
 509
 510         private fun add_conflict(mtype: MType, otype: MType) do
 511                 if mtype == otype then return
 512                 if not self.conflicts_graph.has_key(mtype) then  self.conflicts_graph[mtype] = new HashSet[MType]
 513                 self.conflicts_graph[mtype].add(otype)
 514                 if not self.conflicts_graph.has_key(otype) then  self.conflicts_graph[otype] = new HashSet[MType]
 515                 self.conflicts_graph[otype].add(mtype)
 516         end
 517 end
 518
 519 # Perfect Hashing (PH)
 520 # T = type of holder
 521 # U = type of elements to hash
 522 private class PerfectHasher[T: Object, U: Object]
 523
 524         var operator: PHOperator
 525
 526         init(operator: PHOperator) do self.operator = operator
 527
 528         fun compute_masks(conflicts: Map[T, Set[U]], ids: Map[U, Int]): Map[T, Int] do
 529                 var masks = new HashMap[T, Int]
 530                 for mclasstype, mtypes in conflicts do
 531                         masks[mclasstype] = compute_mask(mtypes, ids)
 532                 end
 533                 return masks
 534         end
 535
 536         private fun compute_mask(mtypes: Set[U], ids: Map[U, Int]): Int do
 537                 var mask = 0
 538                 loop
 539                         var used = new List[Int]
 540                         for mtype in mtypes do
 541                                 var res = operator.op(mask, ids[mtype])
 542                                 if used.has(res) then
 543                                         break
 544                                 else
 545                                         used.add(res)
 546                                 end
 547                         end
 548                         if used.length == mtypes.length then break
 549                         mask += 1
 550                 end
 551                 return mask
 552         end
 553
 554         fun compute_hashes(elements: Map[T, Set[U]], ids: Map[U, Int], masks: Map[T, Int]): Map[T, Map[U, Int]] do
 555                 var hashes = new HashMap[T, Map[U, Int]]
 556                 for mclasstype, mtypes in elements do
 557                         var mask = masks[mclasstype]
 558                         var inhashes = new HashMap[U, Int]
 559                         for mtype in mtypes do
 560                                 inhashes[mtype] = operator.op(mask, ids[mtype])
 561                         end
 562                         hashes[mclasstype] = inhashes
 563                 end
 564                 return hashes
 565         end
 566 end
 567
 568 # Abstract operator used for perfect hashing
 569 abstract class PHOperator
 570         fun op(mask: Int, id:Int): Int is abstract
 571 end
 572
 573 # Hashing using modulo (MOD) operator
 574 # slower but compact
 575 class PHModOperator
 576         super PHOperator
 577         init do end
 578         redef fun op(mask, id) do return mask % id
 579 end
 580
 581 # Hashing using binary and (AND) operator
 582 # faster but sparse
 583 class PHAndOperator
 584         super PHOperator
 585         init do end
 586         redef fun op(mask, id) do return mask.bin_and(id)
 587 end
 588
 589 class TypingHasher[E: Object]
 590         super PerfectHasher[E, E]
 591         super TypingLayoutBuilder[E]
 592
 593         var mmodule: MModule
 594
 595         init(operator: PHOperator, mmodule: MModule) do
 596                 super(operator)
 597                 self.mmodule = mmodule
 598         end
 599
 600         redef fun build_layout(elements: Set[E]): PHLayout[E, E] do
 601                 var result = new PHLayout[E, E]
 602                 var conflicts = self.build_conflicts(elements)
 603                 result.ids = self.compute_ids(elements)
 604                 result.masks = self.compute_masks(conflicts, result.ids)
 605                 result.hashes = self.compute_hashes(conflicts, result.ids, result.masks)
 606                 return result
 607         end
 608
 609         # Ids start from 1 instead of 0
 610         private fun compute_ids(elements: Set[E]): Map[E, Int] do
 611                 var ids = new HashMap[E, Int]
 612                 var lin = self.reverse_linearize(elements)
 613                 for e in lin do
 614                         ids[e] = ids.length + 1
 615                 end
 616                 return ids
 617         end
 618
 619         private fun build_conflicts(elements: Set[E]): Map[E, Set[E]] do
 620                 var conflicts = new HashMap[E, Set[E]]
 621                 for e in elements do
 622                         var supers = self.super_elements(e, elements)
 623                         supers.add(e)
 624                         conflicts[e] = supers
 625                 end
 626                 return conflicts
 627         end
 628
 629         private fun super_elements(element: E, elements: Set[E]): Set[E] is abstract
 630         private fun reverse_linearize(elements: Set[E]): Array[E] is abstract
 631 end
 632
 633 class MTypeHasher
 634         super TypingHasher[MType]
 635
 636         init(operator: PHOperator, mmodule: MModule) do super(operator, mmodule)
 637
 638         redef fun super_elements(element, elements) do
 639                 return self.mmodule.super_mtypes(element, elements)
 640         end
 641
 642         redef fun reverse_linearize(elements) do
 643                 return self.mmodule.reverse_linearize_mtypes(elements)
 644         end
 645 end
 646
 647 class MClassHasher
 648         super TypingHasher[MClass]
 649
 650         init(operator: PHOperator, mmodule: MModule) do super(operator, mmodule)
 651
 652         redef fun super_elements(element, elements) do
 653                 return self.mmodule.super_mclasses(element)
 654         end
 655
 656         redef fun reverse_linearize(elements) do
 657                 return self.mmodule.reverse_linearize_mclasses(elements)
 658         end
 659 end
 660
 661 # Layout builder for MProperty using Perfect Hashing (PH)
 662 # TODO implement this class without sublcassing CL builder
 663 class MPropertyHasher[E: MProperty]
 664         super MPropertyColorer[E]
 665 end
 666
 667 class ResolutionHasher
 668         super PerfectHasher[MClassType, MType]
 669         super ResolutionLayoutBuilder
 670
 671         init(operator: PHOperator) do super(operator)
 672
 673         # Compute resolved types masks and hashes
 674         redef fun build_layout(elements) do
 675                 var result = new PHLayout[MClassType, MType]
 676                 var ids = new HashMap[MType, Int]
 677                 var color = 1
 678                 for mclasstype, mclasstypes in elements do
 679                         for element in mclasstypes do
 680                                 if ids.has_key(element) then continue
 681                                 ids[element] = color
 682                                 color += 1
 683                         end
 684                 end
 685                 result.ids = ids
 686                 result.pos = ids
 687                 result.masks = self.compute_masks(elements, ids)
 688                 result.hashes = self.compute_hashes(elements, ids, result.masks)
 689                 return result
 690         end
 691 end