src/coloring.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 # Graph coloring tools
  16 module coloring
  17
  18 import rapid_type_analysis # for type coloration
  19
  20 abstract class AbstractColoring[E: Object]
  21
  22         private var sorter: AbstractSorter[E]
  23         private var reverse_sorter: AbstractSorter[E]
  24
  25         private var core: OrderedSet[E] = new OrderedSet[E]
  26         private var crown: OrderedSet[E] = new OrderedSet[E]
  27         private var border: OrderedSet[E] = new OrderedSet[E]
  28
  29         private var coloration_result: Map[E, Int] = new HashMap[E, Int]
  30         private var conflicts_graph_cache: nullable HashMap[E, Set[E]]
  31
  32         init(sorter: AbstractSorter[E], reverse_sorter: AbstractSorter[E]) do
  33                 self.sorter = sorter
  34                 self.reverse_sorter = reverse_sorter
  35         end
  36
  37         fun colorize(elements: Collection[E]): Map[E, Int] do
  38                 # tag each element as part of group core, crown or border
  39                 for e in elements do
  40                         tag_element(e)
  41                 end
  42
  43                 #print "core: {core.join(", ")}"
  44                 #print "border: {border.join(", ")}"
  45                 #print "crown: {crown.join(", ")}"
  46
  47                 # sort by reverse linearization order
  48                 reverse_sorter.sort(core)
  49                 reverse_sorter.sort(border)
  50                 reverse_sorter.sort(crown)
  51
  52                 #print "conflicts"
  53                 #for k, v in conflicts_graph do
  54                 #       if k isa MType then
  55                 #               print "{k}: {v.join(", ")}"
  56                 #       end
  57                 #end
  58
  59                 # colorize graph
  60                 colorize_elements(core)
  61                 colorize_elements(border)
  62                 colorize_elements(crown)
  63
  64                 return coloration_result
  65         end
  66
  67         # Colorize a collection of elements
  68         private fun colorize_elements(elements: Collection[E]) do
  69                 var min_color = 0
  70
  71                 for element in elements do
  72                         var color = min_color
  73                         while not self.is_color_free(element, color) do
  74                                 color += 1
  75                         end
  76                         coloration_result[element] = color
  77                         color = min_color
  78                 end
  79         end
  80
  81         # Check if a related element to the element already use the color
  82         private fun is_color_free(element: E, color: Int): Bool do
  83                 if conflicts_graph.has_key(element) then
  84                         for st in conflicts_graph[element] do
  85                                 if coloration_result.has_key(st) and coloration_result[st] == color then return false
  86                         end
  87                 end
  88                 for st in self.super_elements(element) do
  89                         if coloration_result.has_key(st) and coloration_result[st] == color then return false
  90                 end
  91                 return true
  92         end
  93
  94         # Tag element as core, crown or border
  95         private fun tag_element(element: E) do
  96                 # Check if sub elements are all in single inheritance
  97                 var all_subelements_si = true
  98                 for subelem in self.sub_elements(element) do
  99                         if self.is_element_mi(subelem) then
 100                                 all_subelements_si = false
 101                                 break
 102                         end
 103                 end
 104
 105                 # Tag as core, crown or border
 106                 if self.is_element_mi(element) then
 107                         core.add_all(self.super_elements(element))
 108                         core.add(element)
 109                         if all_subelements_si then
 110                                 border.add(element)
 111                         end
 112                 else if not all_subelements_si then
 113                         core.add_all(self.super_elements(element))
 114                         core.add(element)
 115                 else
 116                         crown.add(element)
 117                 end
 118         end
 119
 120         # Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
 121         private fun conflicts_graph: Map[E, Set[E]] do
 122                 if self.conflicts_graph_cache == null then
 123                         self.conflicts_graph_cache = new HashMap[E, HashSet[E]]
 124                         for t in self.core do
 125                                 for i in self.linear_extension(t) do
 126                                         if t == i then continue
 127
 128                                         var lin_i = self.linear_extension(i)
 129
 130                                         for j in self.linear_extension(t) do
 131                                                 if i == j or j == t then continue
 132                                                 var lin_j = self.linear_extension(j)
 133
 134                                                 var d_ij = lin_i - lin_j
 135                                                 var d_ji = lin_j - lin_i
 136
 137                                                 for ed1 in d_ij do
 138                                                         if not conflicts_graph_cache.has_key(ed1) then conflicts_graph_cache[ed1] = new HashSet[E]
 139                                                         # add ed1 x ed2 to conflicts graph
 140                                                         for ed2 in d_ji do conflicts_graph_cache[ed1].add(ed2)
 141                                                 end
 142                                                 for ed1 in d_ij do
 143                                                         if not conflicts_graph_cache.has_key(ed1) then conflicts_graph_cache[ed1] = new HashSet[E]
 144                                                         # add ed1 x ed2 to conflicts graph
 145                                                         for ed2 in d_ji do conflicts_graph_cache[ed1].add(ed2)
 146                                                 end
 147                                         end
 148                                 end
 149                         end
 150                 end
 151                 return conflicts_graph_cache.as(not null)
 152         end
 153
 154         # cache for linear_extensions
 155         private var linear_extensions_cache: Map[E, OrderedSet[E]] = new HashMap[E, OrderedSet[E]]
 156
 157         # Return a linear_extension of super_elements of the element
 158         private fun linear_extension(element: E): OrderedSet[E] do
 159                 if not self.linear_extensions_cache.has_key(element) then
 160                         var lin = new OrderedSet[E]
 161                         lin.add(element)
 162                         lin.add_all(self.super_elements(element))
 163                         self.sorter.sort(lin)
 164                         self.linear_extensions_cache[element] = lin
 165                 end
 166                 return self.linear_extensions_cache[element]
 167         end
 168
 169         # Return all super elements (directs and indirects) of an element
 170         private fun super_elements(element: E): Collection[E] is abstract
 171
 172         # Return all sub elements (directs and indirects) of an element
 173         private fun sub_elements(element: E): Collection[E] is abstract
 174
 175         # Is the element in multiple inheritance ?
 176         private fun is_element_mi(element: E): Bool is abstract
 177 end
 178
 179 # MClassType coloring
 180 class TypeColoring
 181         super AbstractColoring[MType]
 182
 183         type T: MType
 184
 185         private var mmodule: MModule
 186         private var mtypes: Set[T]
 187
 188         # caches
 189         private var super_elements_cache: Map[T, Set[T]] = new HashMap[T, Set[T]]
 190         private var sub_elements_cache: Map[T, Set[T]] = new HashMap[T, Set[T]]
 191
 192         init(mainmodule: MModule, mtypes: Set[T]) do
 193                 super(new TypeSorter(mainmodule), new ReverseTypeSorter(mainmodule))
 194                 self.mmodule = mainmodule
 195                 self.mtypes = mtypes
 196         end
 197
 198         # Build type tables
 199         fun build_type_tables(mtypes: Set[T], colors: Map[T, Int]): Map[T, Array[nullable T]] do
 200                 var tables = new HashMap[T, Array[nullable T]]
 201
 202                 for mtype in mtypes do
 203                         var table = new Array[nullable T]
 204                         var supers = new HashSet[T]
 205                         supers.add_all(self.super_elements(mtype))
 206                         supers.add(mtype)
 207                         for sup in supers do
 208                                 var color = colors[sup]
 209                                 if table.length <= color then
 210                                         for i in [table.length .. color[ do
 211                                                 table[i] = null
 212                                         end
 213                                 end
 214                                 table[color] = sup
 215                         end
 216                         tables[mtype] = table
 217                 end
 218                 return tables
 219         end
 220
 221         redef fun super_elements(element) do
 222                 if not self.super_elements_cache.has_key(element) then
 223                         var supers = new HashSet[T]
 224                         for mtype in self.mtypes do
 225                                 if element == mtype then continue
 226                                 if element.is_subtype(self.mmodule, null, mtype) then
 227                                         supers.add(mtype)
 228                                 end
 229                         end
 230                         self.super_elements_cache[element] = supers
 231                 end
 232                 return self.super_elements_cache[element]
 233         end
 234
 235         # Return all direct super elements of an element
 236         redef fun is_element_mi(element) do
 237                 return self.super_elements(element).length > 1
 238         end
 239
 240         # Return all sub elements (directs and indirects) of an element
 241         redef fun sub_elements(element) do
 242                 if not self.sub_elements_cache.has_key(element) then
 243                         var subs = new HashSet[T]
 244                         for mtype in self.mtypes do
 245                                 if element == mtype then continue
 246                                 if mtype.is_subtype(self.mmodule, null, element) then
 247                                         subs.add(mtype)
 248                                 end
 249                         end
 250                         self.sub_elements_cache[element] = subs
 251                 end
 252                 return self.sub_elements_cache[element]
 253         end
 254 end
 255
 256 class NaiveTypeColoring
 257         super TypeColoring
 258
 259         init(mainmodule: MModule, mtypes: Set[T]) do
 260                 super(mainmodule, mtypes)
 261         end
 262
 263         # naive coloring that use incremental coloring
 264         redef fun colorize_elements(elements) do
 265                 for e in elements do
 266                         self.coloration_result[e] = self.coloration_result.length
 267                 end
 268         end
 269 end
 270
 271 abstract class TypePerfectHashing
 272         super TypeColoring
 273
 274         init(mainmodule: MModule, mtypes: Set[T]) do
 275                 super(mainmodule, mtypes)
 276         end
 277
 278         fun compute_masks(elements: Set[T], ids: Map[T, Int]): Map[T, Int] do
 279                 for e in elements do
 280                         # Create super type list
 281                         var supers = new HashSet[T]
 282                         supers.add_all(self.super_elements(e))
 283                         supers.add(e)
 284                         # Compute the hashing 'mask'
 285                         self.coloration_result[e] = compute_mask(supers, ids)
 286                 end
 287                 return self.coloration_result
 288         end
 289
 290         # Build type tables
 291         fun hash_type_tables(mtypes: Set[T], ids: Map[T, Int], masks: Map[T, Int]): Map[T, Array[nullable T]] do
 292                 var tables = new HashMap[T, Array[nullable T]]
 293
 294                 for mtype in mtypes do
 295                         var table = new Array[nullable T]
 296                         var supers = new HashSet[T]
 297                         supers.add_all(self.super_elements(mtype))
 298                         supers.add(mtype)
 299
 300                         for sup in supers do
 301                                 var color = phash(ids[sup], masks[mtype])
 302                                 if table.length <= color then
 303                                         for i in [table.length .. color[ do
 304                                                 table[i] = null
 305                                         end
 306                                 end
 307                                 table[color] = sup
 308                         end
 309                         tables[mtype] = table
 310                 end
 311                 return tables
 312         end
 313
 314         private fun compute_mask(mtypes: Set[T], ids: Map[T, Int]): Int do
 315                 var mask = 0
 316                 loop
 317                         var used = new List[Int]
 318                         for sup in mtypes do
 319                                 var res = op(mask, ids[sup])
 320                                 if used.has(res) then
 321                                         break
 322                                 else
 323                                         used.add(res)
 324                                 end
 325                         end
 326                         if used.length == mtypes.length then break
 327                         mask += 1
 328                 end
 329                 return mask
 330         end
 331
 332         private fun op(mask: Int, id:Int): Int is abstract
 333         private fun phash(id: Int, mask: Int): Int do return op(mask, id)
 334 end
 335
 336 class TypeModPerfectHashing
 337         super TypePerfectHashing
 338         init(mainmodule: MModule, mtypes: Set[T]) do
 339                 super(mainmodule, mtypes)
 340         end
 341         redef fun op(mask, id) do return mask % id
 342 end
 343
 344 class TypeAndPerfectHashing
 345         super TypePerfectHashing
 346         init(mainmodule: MModule, mtypes: Set[T]) do
 347                 super(mainmodule, mtypes)
 348         end
 349         redef fun op(mask, id) do return mask.bin_and(id)
 350 end
 351
 352 # A sorter for linearize list of types
 353 class TypeSorter
 354         super AbstractSorter[MType]
 355
 356         private var mmodule: MModule
 357
 358         init(mmodule: MModule) do self.mmodule = mmodule
 359
 360         redef fun compare(a, b) do
 361                 if a == b then
 362                         return 0
 363                 else if a.is_subtype(self.mmodule, null, b) then
 364                         return -1
 365                 end
 366                 return 1
 367         end
 368 end
 369
 370 # A sorter for reverse linearization
 371 class ReverseTypeSorter
 372         super TypeSorter
 373
 374         init(mmodule: MModule) do end
 375
 376         redef fun compare(a, b) do
 377                 if a == b then
 378                         return 0
 379                 else if a.is_subtype(self.mmodule, null, b) then
 380                         return 1
 381                 end
 382                 return -1
 383         end
 384 end
 385
 386 # MClass coloring
 387 class ClassColoring
 388         super AbstractColoring[MClass]
 389
 390         type T: MClass
 391
 392         private var mmodule: MModule
 393
 394         # caches
 395         private var super_elements_cache: Map[T, Set[T]] = new HashMap[T, Set[T]]
 396         private var parent_elements_cache: Map[T, Set[T]] = new HashMap[T, Set[T]]
 397         private var sub_elements_cache: Map[T, Set[T]] = new HashMap[T, Set[T]]
 398
 399         init(mainmodule: MModule) do
 400                 super(new ClassSorter(mainmodule), new ReverseClassSorter(mainmodule))
 401                 self.mmodule = mainmodule
 402         end
 403
 404         # Build type tables
 405         fun build_type_tables(mclasses: Array[T], colors: Map[T, Int]): Map[T, Array[nullable T]] do
 406                 var tables = new HashMap[T, Array[nullable T]]
 407
 408                 for mclasse in mclasses do
 409                         var table = new Array[nullable T]
 410                         var supers = new HashSet[T]
 411                         supers.add_all(self.super_elements(mclasse))
 412                         supers.add(mclasse)
 413                         for sup in supers do
 414                                 var color = colors[sup]
 415                                 if table.length <= color then
 416                                         for i in [table.length .. color[ do
 417                                                 table[i] = null
 418                                         end
 419                                 end
 420                                 table[color] = sup
 421                         end
 422                         tables[mclasse] = table
 423                 end
 424                 return tables
 425         end
 426
 427         redef fun super_elements(element) do
 428                 if not self.super_elements_cache.has_key(element) then
 429                         var supers = new HashSet[T]
 430                         if self.mmodule.flatten_mclass_hierarchy.has(element) then
 431                                 for sup in self.mmodule.flatten_mclass_hierarchy[element].greaters do
 432                                         if element == sup then continue
 433                                         supers.add(sup)
 434                                 end
 435                         end
 436                         self.super_elements_cache[element] = supers
 437                 end
 438                 return self.super_elements_cache[element]
 439         end
 440
 441         private fun parent_elements(element: T): Set[T] do
 442                 if not self.parent_elements_cache.has_key(element) then
 443                         var parents = new HashSet[T]
 444                         if self.mmodule.flatten_mclass_hierarchy.has(element) then
 445                                 for parent in self.mmodule.flatten_mclass_hierarchy[element].direct_greaters do
 446                                         if element == parent then continue
 447                                         parents.add(parent)
 448                                 end
 449                         end
 450                         self.parent_elements_cache[element] = parents
 451                 end
 452                 return self.parent_elements_cache[element]
 453         end
 454
 455         # Return all sub elements (directs and indirects) of an element
 456         redef fun sub_elements(element) do
 457                 if not self.sub_elements_cache.has_key(element) then
 458                         var subs = new HashSet[T]
 459                         if self.mmodule.flatten_mclass_hierarchy.has(element) then
 460                                 for sub in self.mmodule.flatten_mclass_hierarchy[element].smallers do
 461                                         subs.add(sub)
 462                                 end
 463                         end
 464                         self.sub_elements_cache[element] = subs
 465                 end
 466                 return self.sub_elements_cache[element]
 467         end
 468
 469         # Return all direct super elements of an element
 470         redef fun is_element_mi(element) do
 471                 if not self.mmodule.flatten_mclass_hierarchy.has(element) then return false
 472                 return self.mmodule.flatten_mclass_hierarchy[element].direct_greaters.length > 1
 473         end
 474 end
 475
 476 # incremental coloring (very naive)
 477 class NaiveClassColoring
 478         super ClassColoring
 479
 480         init(mainmodule: MModule) do
 481                 super(mainmodule)
 482         end
 483
 484         # naive coloring that use incremental coloring
 485         redef fun colorize_elements(elements: Collection[MClass]) do
 486                 for e in elements do
 487                         self.coloration_result[e] = self.coloration_result.length
 488                 end
 489         end
 490 end
 491
 492 abstract class ClassPerfectHashing
 493         super ClassColoring
 494
 495         init(mainmodule: MModule) do
 496                 super(mainmodule)
 497         end
 498
 499         fun compute_masks(elements: Set[T], ids: Map[T, Int]): Map[T, Int] do
 500                 for e in elements do
 501                         # Create super type list
 502                         var supers = new HashSet[T]
 503                         supers.add_all(self.super_elements(e))
 504                         supers.add(e)
 505                         # Compute the hashing 'mask'
 506                         self.coloration_result[e] = compute_mask(supers, ids)
 507                 end
 508                 return self.coloration_result
 509         end
 510
 511         # Build type tables
 512         fun hash_type_tables(mtypes: Set[T], ids: Map[T, Int], masks: Map[T, Int]): Map[T, Array[nullable T]] do
 513                 var tables = new HashMap[T, Array[nullable T]]
 514
 515                 for mtype in mtypes do
 516                         var table = new Array[nullable T]
 517                         var supers = new HashSet[T]
 518                         supers.add_all(self.super_elements(mtype))
 519                         supers.add(mtype)
 520
 521                         for sup in supers do
 522                                 var color = phash(ids[sup], masks[mtype])
 523                                 if table.length <= color then
 524                                         for i in [table.length .. color[ do
 525                                                 table[i] = null
 526                                         end
 527                                 end
 528                                 table[color] = sup
 529                         end
 530                         tables[mtype] = table
 531                 end
 532                 return tables
 533         end
 534
 535         private fun compute_mask(mtypes: Set[T], ids: Map[T, Int]): Int do
 536                 var mask = 0
 537                 loop
 538                         var used = new List[Int]
 539                         for sup in mtypes do
 540                                 var res = op(mask, ids[sup])
 541                                 if used.has(res) then
 542                                         break
 543                                 else
 544                                         used.add(res)
 545                                 end
 546                         end
 547                         if used.length == mtypes.length then break
 548                         mask += 1
 549                 end
 550                 return mask
 551         end
 552
 553         private fun op(mask: Int, id:Int): Int is abstract
 554         private fun phash(id: Int, mask: Int): Int do return op(mask, id)
 555 end
 556
 557 class ClassModPerfectHashing
 558         super ClassPerfectHashing
 559         init(mainmodule: MModule) do
 560                 super(mainmodule)
 561         end
 562         redef fun op(mask, id) do return mask % id
 563 end
 564
 565 class ClassAndPerfectHashing
 566         super ClassPerfectHashing
 567         init(mainmodule: MModule) do
 568                 super(mainmodule)
 569         end
 570         redef fun op(mask, id) do return mask.bin_and(id)
 571 end
 572
 573 # A sorter for linearize list of classes
 574 private class ClassSorter
 575         super AbstractSorter[MClass]
 576
 577         var mmodule: MModule
 578
 579         redef fun compare(a, b) do
 580                 if a == b then
 581                         return 0
 582                 else if self.mmodule.flatten_mclass_hierarchy.has(a) and self.mmodule.flatten_mclass_hierarchy[a].greaters.has(b) then
 583                         return -1
 584                 end
 585                 return 1
 586         end
 587 end
 588
 589 # A sorter for reverse linearization
 590 private class ReverseClassSorter
 591         super AbstractSorter[MClass]
 592
 593         var mmodule: MModule
 594
 595         redef fun compare(a, b) do
 596                 if a == b then
 597                         return 0
 598                 else if self.mmodule.flatten_mclass_hierarchy.has(a) and self.mmodule.flatten_mclass_hierarchy[a].greaters.has(b) then
 599                         return 1
 600                 end
 601                 return -1
 602         end
 603 end
 604
 605 # MProperty coloring
 606 class PropertyColoring
 607
 608         type MPROP: MProperty
 609         type MPROPDEF: MPropDef
 610
 611         private var class_coloring: ClassColoring
 612         private var coloration_result: Map[MPROP, Int] = new HashMap[MPROP, Int]
 613
 614         init(class_coloring: ClassColoring) do
 615                 self.class_coloring = class_coloring
 616         end
 617
 618         fun colorize: Map[MPROP, Int] do
 619                 colorize_core_properties
 620                 colorize_crown_properties
 621                 return self.coloration_result
 622         end
 623
 624         fun build_property_tables: Map[MClass, Array[nullable MPROPDEF]] do
 625                 var tables = new HashMap[MClass, Array[nullable MPROPDEF]]
 626
 627                 for mclass in self.class_coloring.coloration_result.keys do
 628                         var table = new Array[nullable MPROPDEF]
 629                         # first, fill table from parents by reverse linearization order
 630                         var parents = new OrderedSet[MClass]
 631                         parents.add_all(self.class_coloring.super_elements(mclass))
 632                         self.class_coloring.reverse_sorter.sort(parents)
 633                         for parent in parents do
 634                                 for mproperty in self.properties(parent) do
 635                                         var color = self.coloration_result[mproperty]
 636                                         if table.length <= color then
 637                                                 for i in [table.length .. color[ do
 638                                                         table[i] = null
 639                                                 end
 640                                         end
 641                                         for mpropdef in mproperty.mpropdefs do
 642                                                 if mpropdef.mclassdef.mclass == parent then
 643                                                         table[color] = mpropdef
 644                                                 end
 645                                         end
 646                                 end
 647                         end
 648
 649                         # then override with local properties
 650                         for mproperty in self.properties(mclass) do
 651                                 var color = self.coloration_result[mproperty]
 652                                 if table.length <= color then
 653                                         for i in [table.length .. color[ do
 654                                                 table[i] = null
 655                                         end
 656                                 end
 657                                 for mpropdef in mproperty.mpropdefs do
 658                                         if mpropdef.mclassdef.mclass == mclass then
 659                                                 table[color] = mpropdef
 660                                         end
 661                                 end
 662                         end
 663                         tables[mclass] = table
 664                 end
 665                 return tables
 666         end
 667
 668         # Colorize properties of the core hierarchy
 669         private fun colorize_core_properties do
 670                 var mclasses = self.class_coloring.core
 671                 var min_color = 0
 672
 673                 for mclass in mclasses do
 674                         var color = min_color
 675
 676                         # if the class is root, get the minimal color
 677                         if self.class_coloring.parent_elements(mclass).length == 0 then
 678                                 colorize_elements(self.properties(mclass), color)
 679                         else
 680                                 # check last color used by parents
 681                                 color = max_color(color, self.class_coloring.parent_elements(mclass))
 682                                 # check max color used in conflicts
 683                                 if self.class_coloring.conflicts_graph.has_key(mclass) then
 684                                         color = max_color(color, self.class_coloring.conflicts_graph[mclass])
 685                                 end
 686
 687                                 # colorize
 688                                 colorize_elements(self.properties(mclass), color)
 689                         end
 690                 end
 691         end
 692
 693         # Colorize properties of the crown hierarchy
 694         private fun colorize_crown_properties do
 695                 for mclass in self.class_coloring.crown do
 696                         colorize_elements(self.properties(mclass), max_color(0, self.class_coloring.parent_elements(mclass)))
 697                 end
 698         end
 699
 700         # Colorize a collection of properties given a starting color
 701         private fun colorize_elements(elements: Collection[MPROP], start_color: Int) do
 702                 for element in elements do
 703                         if self.coloration_result.has_key(element) then continue
 704                         self.coloration_result[element] = start_color
 705                         start_color += 1
 706                 end
 707         end
 708
 709         private fun max_color(min_color: Int, mclasses: Collection[MClass]): Int do
 710                 var max_color = min_color
 711
 712                 for mclass in mclasses do
 713                         for mproperty in self.properties(mclass) do
 714                                 var color = min_color
 715                                 if self.coloration_result.has_key(mproperty) then
 716                                         color = self.coloration_result[mproperty]
 717                                         if color >= max_color then max_color = color + 1
 718                                 end
 719                         end
 720                 end
 721                 return max_color
 722         end
 723
 724         # properties cache
 725         private var properties_cache: Map[MClass, Set[MPROP]] = new HashMap[MClass, Set[MPROP]]
 726
 727         # All 'mproperties' associated to all 'mclassdefs' of the class
 728         private fun properties(mclass: MClass): Set[MPROP] do
 729                 if not self.properties_cache.has_key(mclass) then
 730                         var properties = new HashSet[MPROP]
 731                         var parents = self.class_coloring.super_elements(mclass)
 732                         for parent in parents do
 733                                 properties.add_all(self.properties(parent))
 734                         end
 735
 736                         for mclassdef in mclass.mclassdefs do
 737                                 for mpropdef in mclassdef.mpropdefs do
 738                                         var mproperty = mpropdef.mproperty
 739                                         if mproperty isa MPROP then
 740                                                 properties.add(mproperty)
 741                                         end
 742                                 end
 743                         end
 744                         self.properties_cache[mclass] = properties
 745                 end
 746                 return properties_cache[mclass]
 747         end
 748 end
 749
 750 # MMethod coloring
 751 class MethodColoring
 752         super PropertyColoring
 753
 754         redef type MPROP: MMethod
 755         redef type MPROPDEF: MMethodDef
 756         init(class_coloring: ClassColoring) do end
 757 end
 758
 759 # MAttribute coloring
 760 class AttributeColoring
 761         super PropertyColoring
 762
 763         redef type MPROP: MAttribute
 764         redef type MPROPDEF: MAttributeDef
 765         init(class_coloring: ClassColoring) do end
 766 end
 767
 768 # MVirtualTypeProp coloring
 769 class VTColoring
 770         super PropertyColoring
 771
 772         redef type MPROP: MVirtualTypeProp
 773         redef type MPROPDEF: MVirtualTypeDef
 774         init(class_coloring: ClassColoring) do end
 775 end
 776
 777 class NaiveVTColoring
 778         super VTColoring
 779
 780         init(class_coloring: ClassColoring) do end
 781
 782         redef fun colorize: Map[MPROP, Int] do
 783                 var mclasses = new HashSet[MClass]
 784                 mclasses.add_all(self.class_coloring.core)
 785                 mclasses.add_all(self.class_coloring.crown)
 786                 var min_color = 0
 787
 788                 for mclass in mclasses do
 789                         min_color = max_color(min_color, mclasses)
 790                         colorize_elements(self.properties(mclass), min_color)
 791                 end
 792                 return self.coloration_result
 793         end
 794 end
 795
 796 # MParameterType coloring
 797 class FTColoring
 798         private var class_coloring: ClassColoring
 799         private var coloration_result: Map[MParameterType, Int] = new HashMap[MParameterType, Int]
 800
 801         init(class_coloring: ClassColoring) do
 802                 self.class_coloring = class_coloring
 803         end
 804
 805         fun colorize: Map[MParameterType, Int] do
 806                 colorize_core_properties
 807                 colorize_crown_properties
 808                 return self.coloration_result
 809         end
 810
 811         # Colorize properties of the core hierarchy
 812         private fun colorize_core_properties do
 813                 var mclasses = self.class_coloring.core
 814                 var min_color = 0
 815
 816                 for mclass in mclasses do
 817                         var color = min_color
 818
 819                         # if the class is root, get the minimal color
 820                         if self.class_coloring.parent_elements(mclass).length == 0 then
 821                                 colorize_elements(self.fts(mclass), color)
 822                         else
 823                                 # check last color used by parents
 824                                 color = max_color(color, self.class_coloring.parent_elements(mclass))
 825                                 # check max color used in conflicts
 826                                 if self.class_coloring.conflicts_graph.has_key(mclass) then
 827                                         color = max_color(color, self.class_coloring.conflicts_graph[mclass])
 828                                 end
 829                                 # colorize
 830                                 colorize_elements(self.fts(mclass), color)
 831                         end
 832                 end
 833         end
 834
 835         # Colorize properties of the crown hierarchy
 836         private fun colorize_crown_properties do
 837                 for mclass in self.class_coloring.crown do
 838                         colorize_elements(self.fts(mclass), max_color(0, self.class_coloring.parent_elements(mclass)))
 839                 end
 840         end
 841
 842         # Colorize a collection of properties given a starting color
 843         private fun colorize_elements(elements: Collection[MParameterType], start_color: Int) do
 844                 for element in elements do
 845                         if self.coloration_result.has_key(element) then continue
 846                         self.coloration_result[element] = start_color
 847                         start_color += 1
 848                 end
 849         end
 850
 851         private fun max_color(min_color: Int, mclasses: Collection[MClass]): Int do
 852                 var max_color = min_color
 853
 854                 for mclass in mclasses do
 855                         for ft in self.fts(mclass) do
 856                                 var color = min_color
 857                                 if self.coloration_result.has_key(ft) then
 858                                         color = self.coloration_result[ft]
 859                                         if color >= max_color then max_color = color + 1
 860                                 end
 861                         end
 862                 end
 863                 return max_color
 864         end
 865
 866         # fts cache
 867         private var fts_cache: Map[MClass, Set[MParameterType]] = new HashMap[MClass, Set[MParameterType]]
 868
 869         private fun fts(mclass: MClass): Set[MParameterType] do
 870                 if not self.fts_cache.has_key(mclass) then
 871                         var fts = new HashSet[MParameterType]
 872                         var mclass_type = mclass.mclass_type
 873                         if mclass_type isa MGenericType then
 874                                 for ft in mclass_type.arguments do
 875                                         fts.add(ft.as(MParameterType))
 876                                 end
 877                         end
 878                         self.fts_cache[mclass] = fts
 879                 end
 880                 return fts_cache[mclass]
 881         end
 882
 883         fun build_ft_tables: Map[MClass, Array[nullable MParameterType]] do
 884                 var tables = new HashMap[MClass, Array[nullable MParameterType]]
 885
 886                 for mclass in self.class_coloring.coloration_result.keys do
 887                         var table = new Array[nullable MParameterType]
 888
 889                         # first, fill table from parents
 890                         for parent in self.class_coloring.super_elements(mclass) do
 891                                 for ft in self.fts(parent) do
 892                                         var color = self.coloration_result[ft]
 893                                         if table.length <= color then
 894                                                 for i in [table.length .. color[ do
 895                                                         table[i] = null
 896                                                 end
 897                                         end
 898                                         table[color] = ft
 899                                 end
 900                         end
 901
 902                         # then override with local properties
 903                         for ft in self.fts(mclass) do
 904                                 var color = self.coloration_result[ft]
 905                                 if table.length <= color then
 906                                         for i in [table.length .. color[ do
 907                                                 table[i] = null
 908                                         end
 909                                 end
 910                                 table[color] = ft
 911                         end
 912                         tables[mclass] = table
 913                 end
 914                 return tables
 915         end
 916 end
 917
 918 class NaiveFTColoring
 919         super FTColoring
 920
 921         init(class_coloring: ClassColoring) do end
 922
 923         redef fun colorize: Map[MParameterType, Int] do
 924                 var mclasses = new HashSet[MClass]
 925                 mclasses.add_all(self.class_coloring.core)
 926                 mclasses.add_all(self.class_coloring.crown)
 927                 var min_color = 0
 928
 929                 for mclass in mclasses do
 930                         min_color = max_color(min_color, mclasses)
 931                         colorize_elements(self.fts(mclass), min_color)
 932                 end
 933                 return self.coloration_result
 934         end
 935 end
 936
 937 # Live Entries coloring
 938 class LiveEntryColoring
 939
 940         private var coloration_result: Map[MType, Int] = new HashMap[MType, Int]
 941         private var conflicts_graph_cache: nullable HashMap[MType, Set[MType]]
 942         var livetypes_tables_sizes: nullable Map[MClass, Array[Int]]
 943
 944         init do end
 945
 946         fun colorize(elements: Collection[MType]): Map[MType, Int] do
 947                 # compute conflicts
 948                 build_conflicts_graph(elements)
 949
 950                 # colorize graph
 951                 colorize_elements(elements)
 952
 953                 return coloration_result
 954         end
 955
 956         # Build type tables
 957         fun build_livetype_tables(mtypes: Set[MType]): Map[MClass, Array[nullable Object]] do
 958                 var livetypes_tables = new HashMap[MClass, Array[nullable Object]]
 959                 self.livetypes_tables_sizes = new HashMap[MClass, Array[Int]]
 960
 961                 for mtype in mtypes do
 962                         if mtype isa MGenericType then
 963                                 var table: Array[nullable Object]
 964                                 var sizes: Array[Int]
 965                                 if livetypes_tables.has_key(mtype.mclass) then
 966                                         table = livetypes_tables[mtype.mclass]
 967                                 else
 968                                         table = new Array[nullable Object]
 969                                         livetypes_tables[mtype.mclass] = table
 970                                 end
 971                                 if livetypes_tables_sizes.has_key(mtype.mclass) then
 972                                         sizes = livetypes_tables_sizes[mtype.mclass]
 973                                 else
 974                                         sizes = new Array[Int]
 975                                         livetypes_tables_sizes[mtype.mclass] = sizes
 976                                 end
 977                                 build_livetype_table(mtype, 0, table, sizes)
 978                         end
 979                 end
 980
 981                 return livetypes_tables
 982         end
 983
 984         # Build live gentype table recursively
 985         private fun build_livetype_table(mtype: MGenericType, current_rank: Int, table: Array[nullable Object], sizes: Array[Int]) do
 986                 var ft = mtype.arguments[current_rank]
 987                 if not self.coloration_result.has_key(ft) then return
 988                 var color = self.coloration_result[ft]
 989
 990                 if current_rank >= sizes.length then
 991                         sizes[current_rank] = color + 1
 992                 else if color >= sizes[current_rank] then
 993                         sizes[current_rank] = color + 1
 994                 end
 995
 996                 if color > table.length then
 997                         for i in [table.length .. color[ do table[i] = null
 998                 end
 999
1000                 if current_rank == mtype.arguments.length - 1 then
1001                         table[color] = mtype
1002                 else
1003                         var ft_table: Array[nullable Object]
1004                         if color < table.length and table[color] != null then
1005                                 ft_table = table[color].as(Array[nullable Object])
1006                         else
1007                                 ft_table = new Array[nullable Object]
1008                         end
1009                         table[color] = ft_table
1010                         build_livetype_table(mtype, current_rank + 1, ft_table, sizes)
1011                 end
1012         end
1013
1014         # Colorize a collection of elements
1015         fun colorize_elements(elements: Collection[MType]) do
1016                 var min_color = 0
1017
1018                 for element in elements do
1019                         var color = min_color
1020                         while not self.is_color_free(element, color) do
1021                                 color += 1
1022                         end
1023                         coloration_result[element] = color
1024                         color = min_color
1025                 end
1026         end
1027
1028         # Check if a related element to the element already use the color
1029         private fun is_color_free(element: MType, color: Int): Bool do
1030                 if conflicts_graph.has_key(element) then
1031                         for st in conflicts_graph[element] do
1032                                 if coloration_result.has_key(st) and coloration_result[st] == color then return false
1033                         end
1034                 end
1035                 return true
1036         end
1037
1038         # look for types in the same generic signatures
1039         private fun build_conflicts_graph(elements: Collection[MType]) do
1040                 # regroup types by classes
1041                 var genclasses = new HashMap[MClass, Set[MType]]
1042                 for e in elements do
1043                         if e isa MGenericType then
1044                                 if not genclasses.has_key(e.mclass) then
1045                                         genclasses[e.mclass] = new HashSet[MType]
1046                                 end
1047                                 genclasses[e.mclass].add(e)
1048                         end
1049                 end
1050
1051                 # for each class
1052                 self.conflicts_graph_cache = new HashMap[MType, Set[MType]]
1053                 for mclass, mtypes in genclasses do
1054                         # for each rank
1055                         for rank in [0..mclass.arity[ do
1056                                 # for each live type
1057                                 for mtype in mtypes do
1058                                         var mclasstype: MClassType
1059                                         if mtype isa MNullableType then
1060                                                 mclasstype = mtype.mtype.as(MClassType)
1061                                         else
1062                                                 mclasstype = mtype.as(MClassType)
1063                                         end
1064                                         var ft = mclasstype.arguments[rank]
1065                                         for otype in mtypes do
1066                                                 if mtype == otype then continue
1067                                                 var oclasstype: MClassType
1068                                                 if otype isa MNullableType then
1069                                                         oclasstype = otype.mtype.as(MClassType)
1070                                                 else
1071                                                         oclasstype = otype.as(MClassType)
1072                                                 end
1073                                                 var oft = oclasstype.arguments[rank]
1074                                                 self.add_conflict(ft, oft)
1075                                         end
1076                                 end
1077                         end
1078                 end
1079         end
1080
1081         private fun add_conflict(mtype: MType, otype: MType) do
1082                 if mtype == otype then return
1083                 if not self.conflicts_graph_cache.has_key(mtype) then  self.conflicts_graph_cache[mtype] = new HashSet[MClassType]
1084                 self.conflicts_graph_cache[mtype].add(otype)
1085                 if not self.conflicts_graph_cache.has_key(otype) then  self.conflicts_graph_cache[otype] = new HashSet[MClassType]
1086                 self.conflicts_graph_cache[otype].add(mtype)
1087         end
1088         private fun conflicts_graph: Map[MType, Set[MType]] do return conflicts_graph_cache.as(not null)
1089 end
1090
1091 class NaiveLiveEntryColoring
1092         super LiveEntryColoring
1093
1094         init do end
1095
1096         redef fun colorize_elements(elements: Collection[MType]) do
1097                 var color = 0
1098                 for element in elements do
1099                         coloration_result[element] = color
1100                         color += 1
1101                 end
1102         end
1103 end
1104
1105
1106 # Utils
1107
1108 # An ordered set
1109 class OrderedSet[E]
1110         super Array[E]
1111
1112         init do end
1113
1114         init from(elements: Set[E]) do
1115                 self.add_all(elements)
1116         end
1117
1118         redef fun add(e) do
1119                 if not self.has(e) then
1120                         super(e)
1121                 end
1122         end
1123
1124         # Return a new OrderedSet with the elements only contened in 'self' and not in 'o'
1125         fun -(o: OrderedSet[E]): OrderedSet[E] do
1126                 var res = new OrderedSet[E]
1127                 for e in self do if not o.has(e) then res.add(e)
1128                 return res
1129         end
1130
1131         # Linearize a set of elements
1132         fun linearize(sorter: AbstractSorter[E]) do
1133                 sorter.sort(self)
1134         end
1135 end