1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2008 Jean Privat <jean@pryen.org>
4 # Copyright 2009 Jean-Sebastien Gelinas <calestar@gmail.com>
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
10 # http://www.apache.org/licenses/LICENSE-2.0
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.
18 # Compute tables for classes and modules.
19 package table_computation
25 # Something that store color of table elements
27 var _colors
: HashMap[TableElt, Int] = new HashMap[TableElt, Int]
29 # The color of a table element.
30 fun color
(e
: TableElt): Int
35 # Is a table element already colored?
36 fun has_color
(e
: TableElt): Bool
38 return _colors
.has_key
(e
)
41 # Assign a color to a table element.
42 fun color
=(e
: TableElt, c
: Int)
46 for i
in [0..e
.length
[ do
47 _colors
[e
.item
(i
)] = idx
53 # All information and results of the global analysis.
54 class TableInformation
56 # FIXME: do something better.
57 readable writable var _max_class_table_length
: Int = 0
60 # A compiled class is a class in a program
63 # The corresponding local class in the main module of the prgram
64 readable var _local_class
: MMLocalClass
66 # The identifier of the class
67 readable writable var _id
: Int = 0
69 # The full class table of the class
70 readable var _class_table
: Array[nullable TableElt] = new Array[nullable TableElt]
72 # The full instance table of the class
73 readable var _instance_table
: Array[nullable TableElt] = new Array[nullable TableElt]
75 # The proper class table part (no superclasses but all refinements)
76 readable writable var _class_layout
: TableEltComposite = new TableEltComposite(self)
78 # The proper instance table part (no superclasses but all refinements)
79 readable writable var _instance_layout
: TableEltComposite = new TableEltComposite(self)
81 init(c
: MMLocalClass) do _local_class
= c
84 redef class MMConcreteClass
85 # The table element of the subtype check
86 fun class_color_pos
: TableEltClassColor do return _class_color_pos
.as(not null)
87 var _class_color_pos
: nullable TableEltClassColor
89 # The proper local class table part (nor superclasses nor refinments)
90 readable var _class_layout
: Array[TableElt] = new Array[TableElt]
92 # The proper local instance table part (nor superclasses nor refinments)
93 readable var _instance_layout
: Array[TableElt] = new Array[TableElt]
95 # Build the local layout of the class and feed the module table
96 private fun build_layout_in
(tc
: ToolContext, module_table
: Array[ModuleTableElt])
98 var clt
= _class_layout
99 var ilt
= _instance_layout
101 if global
.intro
== self then
102 module_table
.add
(new TableEltClassId(self))
103 var cpp
= new TableEltClassColor(self)
104 _class_color_pos
= cpp
105 module_table
.add
(cpp
)
106 clt
.add
(new TableEltClassInitTable(self))
108 for p
in local_local_properties
do
110 if pg
.intro
== p
then
111 if p
isa MMAttribute then
112 ilt
.add
(new TableEltAttr(p
))
113 else if p
isa MMMethod then
114 clt
.add
(new TableEltMeth(p
))
117 if p
isa MMMethod and p
.need_super
then
118 clt
.add
(new TableEltSuper(p
))
122 if not ilt
.is_empty
then
123 var teg
= new ModuleTableEltGroup
124 teg
.elements
.append
(ilt
)
125 module_table
.add
(teg
)
128 if not clt
.is_empty
then
129 var teg
= new ModuleTableEltGroup
130 teg
.elements
.append
(clt
)
131 module_table
.add
(teg
)
137 # Information about the class tables
138 readable var _table_information
: TableInformation = new TableInformation
140 # Associate global classes to compiled classes
141 readable var _compiled_classes
: HashMap[MMGlobalClass, CompiledClass] = new HashMap[MMGlobalClass, CompiledClass]
143 fun do_table_computation
(tc
: ToolContext)
145 tc
.info
("Building tables",1)
146 for m
in module.mhe
.greaters_and_self
do
147 tc
.info
("Building tables for module: {m.name}",2)
151 tc
.info
("Merging all tables",2)
152 do_global_analysis
(tc
)
155 # Do the complete global analysis
156 private fun do_global_analysis
(cctx
: ToolContext)
158 #print "Do the complete global analysis"
159 var smallest_classes
= new Array[MMLocalClass]
160 var global_properties
= new HashSet[MMGlobalProperty]
161 var ctab
= new Array[TableElt]
162 var itab
= new Array[TableElt]
164 ctab
.add
(new TableEltClassSelfId)
165 ctab
.add
(new TableEltClassObjectSize)
166 itab
.add
(new TableEltVftPointer)
167 itab
.add
(new TableEltObjectId)
172 # We have to work on ALL the classes of the module
173 var classes
= new Array[MMLocalClass]
174 for c
in module.local_classes
do
175 c
.compute_super_classes
178 (new ClassSorter).sort
(classes
)
181 # Finish processing the class (if invisible)
183 c
.inherit_global_properties
185 # Associate a CompiledClass to the class
186 var cc
= new CompiledClass(c
)
187 compiled_classes
[c
.global
] = cc
189 # Assign a unique class identifier
190 # (negative are for primitive classes)
193 if c
.primitive_info
!= null then
195 pclassid
= pclassid
- 4
198 classid
= classid
+ 4
201 # Register is the class is a leaf
202 if c
.cshe
.direct_smallers
.is_empty
then
203 smallest_classes
.add
(c
)
206 # Store the colortableelt in the class table pool
207 var bc
= c
.global
.intro
208 assert bc
isa MMConcreteClass
209 ctab
.add
(bc
.class_color_pos
)
212 # Compute core and crown classes for colorization
213 var crown_classes
= new HashSet[MMLocalClass]
214 var core_classes
= new HashSet[MMLocalClass]
215 for c
in smallest_classes
do
216 while c
.cshe
.direct_greaters
.length
== 1 do
217 c
= c
.cshe
.direct_greaters
.first
220 core_classes
.add_all
(c
.cshe
.greaters_and_self
)
222 #print("nbclasses: {classes.length} leaves: {smallest_classes.length} crown: {crown_classes.length} core: {core_classes.length}")
224 # Colorize core color for typechecks
225 colorize
(ctab
, crown_classes
, 0)
227 # Compute tables for typechecks
230 var cc
= compiled_classes
[c
.global
]
231 if core_classes
.has
(c
) then
232 # For core classes, just build the table
233 build_tables_in
(cc
.class_table
, c
, ctab
)
234 if maxcolor
< cc
.class_table
.length
then maxcolor
= cc
.class_table
.length
236 # For other classes, it's easier: just append to the parent tables
237 var sc
= c
.cshe
.direct_greaters
.first
238 var scc
= compiled_classes
[sc
.global
]
239 assert cc
.class_table
.is_empty
240 cc
.class_table
.add_all
(scc
.class_table
)
241 var bc
= c
.global
.intro
242 assert bc
isa MMConcreteClass
243 var colpos
= bc
.class_color_pos
244 var colposcolor
= cc
.class_table
.length
245 table_information
.color
(colpos
) = colposcolor
246 cc
.class_table
.add
(colpos
)
247 if maxcolor
< colposcolor
then maxcolor
= colposcolor
250 table_information
.max_class_table_length
= maxcolor
+ 1
252 # Fill class table and instance tables pools
254 var cc
= compiled_classes
[c
.global
]
255 var cte
= cc
.class_layout
256 var ite
= cc
.instance_layout
257 for sc
in c
.crhe
.greaters_and_self
do
258 if sc
isa MMConcreteClass then
259 cte
.add
(sc
, sc
.class_layout
)
260 ite
.add
(sc
, sc
.instance_layout
)
264 if core_classes
.has
(c
) then
265 if cte
.length
> 0 then
268 if ite
.length
> 0 then
274 # Colorize all elements in pools tables
275 colorize
(ctab
, crown_classes
, maxcolor
+1)
276 colorize
(itab
, crown_classes
, 0)
278 # Build class and instance tables now things are colored
279 table_information
.max_class_table_length
= 0
281 var cc
= compiled_classes
[c
.global
]
282 if core_classes
.has
(c
) then
283 # For core classes, just build the table
284 build_tables_in
(cc
.class_table
, c
, ctab
)
285 build_tables_in
(cc
.instance_table
, c
, itab
)
287 # For other classes, it's easier: just append to the parent tables
288 var sc
= c
.cshe
.direct_greaters
.first
289 var scc
= compiled_classes
[sc
.global
]
291 cc
.class_table
.add_all
(scc
.class_table
)
292 var bc
= c
.global
.intro
293 assert bc
isa MMConcreteClass
294 var colpos
= bc
.class_color_pos
295 cc
.class_table
[table_information
.color
(colpos
)] = colpos
296 while cc
.class_table
.length
<= maxcolor
do
297 cc
.class_table
.add
(null)
299 append_to_table
(cc
.class_table
, cc
.class_layout
)
300 assert cc
.instance_table
.is_empty
301 cc
.instance_table
.add_all
(scc
.instance_table
)
302 append_to_table
(cc
.instance_table
, cc
.instance_layout
)
308 fun colorize
(elts
: Array[TableElt], classes
: Collection[MMLocalClass], startcolor
: Int)
310 var colors
= new HashMap[Int, Array[TableElt]]
311 var rel_classes
= new Array[MMLocalClass]
315 if table_information
.has_color
(e
) then
316 color
= table_information
.color
(e
)
320 if e
.is_related_to
(c
) then
324 var trycolor
= startcolor
325 while trycolor
!= color
do
327 for c
in rel_classes
do
330 if colors
.has_key
(trycolor
+ idx
) and not free_color
(colors
[trycolor
+ idx
], c
) then
331 trycolor
= trycolor
+ idx
+ 1
339 table_information
.color
(e
) = color
341 for idx
in [0..len
[ do
342 if colors
.has_key
(color
+ idx
) then
343 colors
[color
+ idx
].add
(e
)
345 colors
[color
+ idx
] = [e
]
351 private fun free_color
(es
: Array[TableElt], c
: MMLocalClass): Bool
354 if e2
.is_related_to
(c
) then
361 private fun append_to_table
(table
: Array[nullable TableElt], cmp
: TableEltComposite)
363 for j
in [0..cmp
.length
[ do
365 table_information
.color
(e
) = table
.length
370 private fun build_tables_in
(table
: Array[nullable TableElt], c
: MMLocalClass, elts
: Array[TableElt])
372 var tab
= new HashMap[Int, TableElt]
375 if e
.is_related_to
(c
) then
376 var col
= table_information
.color
(e
)
377 var l
= col
+ e
.length
386 if tab
.has_key
(i
) then
388 for j
in [0..e
.length
[ do
401 # The local table of the module (refers things introduced in the module)
402 readable var _local_table
: Array[ModuleTableElt] = new Array[ModuleTableElt]
404 # Builds the local tables and local classes layouts
405 private fun local_analysis
(tc
: ToolContext)
407 for c
in local_classes
do
408 if c
isa MMConcreteClass then
409 c
.build_layout_in
(tc
, _local_table
)
415 ###############################################################################
417 # An element of a class, an instance or a module table
418 abstract class AbsTableElt
421 # An element of a class or an instance table
422 # Such an elements represent method function pointers, attribute values, etc.
423 abstract class TableElt
425 # Is the element conflict to class `c' (used for coloring)
426 fun is_related_to
(c
: MMLocalClass): Bool is abstract
428 # Number of sub-elements. 1 if none
429 fun length
: Int do return 1
431 # Access the ith subelement.
432 fun item
(i
: Int): TableElt do return self
435 # An element of a module table
436 # Such an elements represent colors or identifiers
437 abstract class ModuleTableElt
441 # An element of a module table that represents a group of TableElt defined in the same local class
442 class ModuleTableEltGroup
443 special ModuleTableElt
444 readable var _elements
: Array[TableElt] = new Array[TableElt]
447 # An element that represents a class property
448 abstract class TableEltProp
450 readable var _property
: MMLocalProperty
452 init(p
: MMLocalProperty)
458 # An element that represents a function pointer to a global method
463 # An element that represents a function pointer to the super method of a local method
468 # An element that represents the value stored for a global attribute
473 # An element representing a class information
474 class AbsTableEltClass
476 # The local class where the information comes from
477 readable var _local_class
: MMLocalClass
479 init(c
: MMLocalClass)
485 # An element of a class table representing a class information
488 special AbsTableEltClass
489 redef fun is_related_to
(c
)
491 var bc
= c
.module[_local_class
.global
]
496 # An element representing the id of a class in a module table
497 class TableEltClassId
498 special ModuleTableElt
499 special AbsTableEltClass
502 # An element representing the constructor marker position in a class table
503 class TableEltClassInitTable
504 special TableEltClass
507 # An element used for a cast
508 # Note: this element is both a TableElt and a ModuleTableElt.
509 # At the TableElt offset, there is the id of the super-class
510 # At the ModuleTableElt offset, there is the TableElt offset (ie. the color of the super-class).
511 class TableEltClassColor
512 special TableEltClass
513 special ModuleTableElt
516 # A Group of elements introduced in the same global-class that are colored together
517 class TableEltComposite
519 var _table
: Array[TableElt]
520 var _cc
: CompiledClass
521 var _offsets
: HashMap[MMLocalClass, Int]
522 redef fun length
do return _table
.length
523 redef fun is_related_to
(c
) do return c
.cshe
<= _cc
.local_class
525 fun add
(c
: MMLocalClass, tab
: Array[TableElt])
527 _offsets
[c
] = _table
.length
531 redef fun item
(i
) do return _table
[i
]
533 init(cc
: CompiledClass)
536 _table
= new Array[TableElt]
537 _offsets
= new HashMap[MMLocalClass, Int]
541 # The element that represent the class id
542 class TableEltClassSelfId
544 redef fun is_related_to
(c
) do return true
547 # The element that represent the Object Size
548 class TableEltClassObjectSize
550 redef fun is_related_to
(c
) do return true
553 # The element that represent the object id
554 class TableEltObjectId
556 redef fun is_related_to
(c
) do return true
560 class TableEltVftPointer
562 redef fun is_related_to
(c
) do return true
565 ###############################################################################
567 # Used to sort local class in a deterministic total order
568 # The total order superset the class refinement and the class specialisation relations
570 special AbstractSorter[MMLocalClass]
571 redef fun compare
(a
, b
) do return a
.compare
(b
)
575 redef class MMLocalClass
576 # Comparaison in a total order that superset the class refinement and the class specialisation relations
577 fun compare
(b
: MMLocalClass): Int
582 else if a
.module.mhe
< b
.module then
584 else if b
.module.mhe
< a
.module then
594 return b
.name
.to_s
<=> a
.name
.to_s