1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2008 Jean Privat <jean@pryen.org>
5 # Licensed under the Apache License, Version 2.0 (the "License");
6 # you may not use this file except in compliance with the License.
7 # You may obtain a copy of the License at
9 # http://www.apache.org/licenses/LICENSE-2.0
11 # Unless required by applicable law or agreed to in writing, software
12 # distributed under the License is distributed on an "AS IS" BASIS,
13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 # See the License for the specific language governing permissions and
15 # limitations under the License.
17 # Compute and generate tables for classes and modules.
18 package compiling_global
20 #import compiling_base
21 private import compiling_methods
24 # Something that store color of table elements
26 attr _colors
: HashMap[TableElt, Int] = null
28 # The color of a table element.
29 meth color
(e
: TableElt): Int
34 # Is a table element already colored?
35 meth has_color
(e
: TableElt): Bool
37 return _colors
!= null and _colors
.has_key
(e
)
40 # Assign a color to a table element.
41 meth color
=(e
: TableElt, c
: Int)
43 if _colors
== null then _colors
= new HashMap[TableElt, Int]
46 for i
in [0..e
.length
[ do
47 _colors
[e
.item
(i
)] = idx
53 # All information and results of the global analysis.
56 # Associate global classes to compiled classes
57 readable attr _compiled_classes
: HashMap[MMGlobalClass, CompiledClass]
59 # The main module of the program globally analysed
60 readable attr _module
: MMModule
62 # FIXME: do something better.
63 readable writable attr _max_class_table_length
: Int
65 init(module: MMSrcModule)
67 _compiled_classes
= new HashMap[MMGlobalClass, CompiledClass]
72 redef class CompilerVisitor
73 # The global analysis result, if any
74 readable writable attr _global_analysis
: GlobalAnalysis
77 # A compiled class is a class in a program
80 # The corresponding local class in the main module of the prgram
81 readable attr _local_class
: MMLocalClass
83 # The identifier of the class
84 readable writable attr _id
: Int
86 # The full class table of the class
87 readable writable attr _class_table
: Array[TableElt]
89 # The full instance table of the class
90 readable writable attr _instance_table
: Array[TableElt]
92 # The proper class table part (no superclasses but all refinements)
93 readable writable attr _class_layout
: TableEltComposite
95 # The proper instance table part (no superclasses but all refinements)
96 readable writable attr _instance_layout
: TableEltComposite
98 init(c
: MMLocalClass) do _local_class
= c
101 redef class MMGlobalProperty
102 # The position of the property in the local class table part
103 # FIXME: It's ugly. store this somewhere else please
104 readable writable attr _pos_of
: Int
107 redef class MMSrcLocalClass
108 # The table element of the attribute position (for accessor simulation)
109 readable attr _base_attr_pos
: TableEltBaseAttrPos
111 # The table element of the subtype check
112 readable attr _class_color_pos
: TableEltClassColorPos
114 # The proper local class table part (nor superclasses nor refinments)
115 readable attr _class_layout
: Array[LocalTableElt]
117 # The proper local instance table part (nor superclasses nor refinments)
118 readable attr _instance_layout
: Array[LocalTableElt]
120 # Build the local layout of the class and feed the module table
121 meth build_layout_in
(tc
: ToolContext, module_table
: Array[LocalTableElt])
123 var intro_methods
= new Array[MMGlobalProperty] # FIXME: Remove this
124 var intro_attributes
= new Array[MMGlobalProperty] # FIXME: Remove this
125 var clt
= new Array[LocalTableElt]
127 var ilt
= new Array[LocalTableElt]
128 _instance_layout
= ilt
130 if global
.intro
== self then
131 module_table
.add
(new TableEltClassIdPos(self))
132 _class_color_pos
= new TableEltClassColorPos(self)
133 module_table
.add
(_class_color_pos
)
134 #clt.add(_class_color_pos)
135 clt
.add
(new TableEltClassInitTablePos(self))
137 for p
in src_local_properties
do
139 if pg
.intro
== p
then
140 if p
isa MMSrcAttribute then
141 pg
.pos_of
= intro_attributes
.length
142 intro_attributes
.add
(pg
)
143 ilt
.add
(new TableEltAttrPos(p
))
144 else if p
isa MMSrcMethod then
145 pg
.pos_of
= intro_methods
.length
146 intro_methods
.add
(pg
)
147 clt
.add
(new TableEltMethPos(p
))
150 if p
isa MMSrcMethod and p
.need_super
then
151 clt
.add
(new TableEltSuperPos(p
))
154 if tc
.attr_sim
and not intro_attributes
.is_empty
then
155 _base_attr_pos
= new TableEltBaseAttrPos(self)
156 clt
.add
(_base_attr_pos
)
158 module_table
.append
(ilt
)
160 module_table
.append
(clt
)
164 redef class MMSrcModule
165 # The local table of the module (refers things introduced in the module)
166 attr _local_table
: Array[LocalTableElt]
168 # Builds the local tables and local classes layouts
169 meth local_analysis
(tc
: ToolContext)
171 var lt
= new Array[LocalTableElt]
173 for c
in src_local_classes
do
174 c
.build_layout_in
(tc
, lt
)
178 # Do the complete global analysis
179 meth global_analysis
(cctx
: ToolContext): GlobalAnalysis
181 #print "Do the complete global analysis"
182 var ga
= new GlobalAnalysis(self)
183 var smallest_classes
= new Array[MMLocalClass]
184 var global_properties
= new HashSet[MMGlobalProperty]
185 var ctab
= new Array[TableElt]
186 var itab
= new Array[TableElt]
188 ctab
.add
(new TableEltClassSelfId)
189 itab
.add
(new TableEltVftPointer)
194 # We have to work on ALL the classes of the module
195 var classes
= new Array[MMLocalClass]
196 for c
in local_classes
do
197 c
.compute_super_classes
200 (new ClassSorter).sort
(classes
)
203 # Finish processing the class (if invisible)
205 c
.inherit_global_properties
207 # Associate a CompiledClass to the class
208 var cc
= new CompiledClass(c
)
209 ga
.compiled_classes
[c
.global
] = cc
211 # Assign a unique class identifier
212 # (negative are for primitive classes)
215 if c
.primitive_info
!= null then
217 pclassid
= pclassid
- 4
220 classid
= classid
+ 4
223 # Register is the class is a leaf
224 if c
.cshe
.direct_smallers
.is_empty
then
225 smallest_classes
.add
(c
)
228 # Store the colortableelt in the class table pool
229 var bc
= c
.global
.intro
230 assert bc
isa MMSrcLocalClass
231 ctab
.add
(bc
.class_color_pos
)
234 # Compute core and crown classes for colorization
235 var crown_classes
= new HashSet[MMLocalClass]
236 var core_classes
= new HashSet[MMLocalClass]
237 for c
in smallest_classes
do
238 while c
.cshe
.direct_greaters
.length
== 1 do
239 c
= c
.cshe
.direct_greaters
.first
242 core_classes
.add_all
(c
.cshe
.greaters_and_self
)
244 #print("nbclasses: {classes.length} leaves: {smallest_classes.length} crown: {crown_classes.length} core: {core_classes.length}")
246 # Colorize core color for typechecks
247 colorize
(ga
, ctab
, crown_classes
, 0)
249 # Compute tables for typechecks
252 var cc
= ga
.compiled_classes
[c
.global
]
253 if core_classes
.has
(c
) then
254 # For core classes, just build the table
255 cc
.class_table
= build_tables
(ga
, c
, ctab
)
256 if maxcolor
< cc
.class_table
.length
then maxcolor
= cc
.class_table
.length
258 # For other classes, it's easier: just append to the parent tables
259 var sc
= c
.cshe
.direct_greaters
.first
260 var scc
= ga
.compiled_classes
[sc
.global
]
261 cc
.class_table
= scc
.class_table
.to_a
262 var bc
= c
.global
.intro
263 assert bc
isa MMSrcLocalClass
264 var colpos
= bc
.class_color_pos
265 var colposcolor
= cc
.class_table
.length
266 ga
.color
(colpos
) = colposcolor
267 cc
.class_table
.add
(colpos
)
268 if maxcolor
< colposcolor
then maxcolor
= colposcolor
271 ga
.max_class_table_length
= maxcolor
+ 1
273 # Fill class table and instance tables pools
275 var cc
= ga
.compiled_classes
[c
.global
]
276 var cte
= new TableEltComposite(cc
)
277 var ite
= new TableEltComposite(cc
)
278 for sc
in c
.crhe
.greaters_and_self
do
279 if sc
isa MMSrcLocalClass then
280 cte
.add
(sc
, sc
.class_layout
)
281 ite
.add
(sc
, sc
.instance_layout
)
283 cc
.class_layout
= cte
284 cc
.instance_layout
= ite
287 if core_classes
.has
(c
) then
288 if cte
.length
> 0 then
291 if not cctx
.attr_sim
and ite
.length
> 0 then
297 # Colorize all elements in pools tables
298 colorize
(ga
, ctab
, crown_classes
, maxcolor
+1)
299 colorize
(ga
, itab
, crown_classes
, 0)
301 # Build class and instance tables now things are colored
302 ga
.max_class_table_length
= 0
304 var cc
= ga
.compiled_classes
[c
.global
]
305 if core_classes
.has
(c
) then
306 # For core classes, just build the table
307 cc
.class_table
= build_tables
(ga
, c
, ctab
)
308 cc
.instance_table
= build_tables
(ga
, c
, itab
)
310 # For other classes, it's easier: just append to the parent tables
311 var sc
= c
.cshe
.direct_greaters
.first
312 var scc
= ga
.compiled_classes
[sc
.global
]
313 cc
.class_table
= scc
.class_table
.to_a
314 var bc
= c
.global
.intro
315 assert bc
isa MMSrcLocalClass
316 var colpos
= bc
.class_color_pos
317 cc
.class_table
[ga
.color
(colpos
)] = colpos
318 while cc
.class_table
.length
<= maxcolor
do
319 cc
.class_table
.add
(null)
321 append_to_table
(ga
, cc
.class_table
, cc
.class_layout
)
322 cc
.instance_table
= scc
.instance_table
.to_a
323 append_to_table
(ga
, cc
.instance_table
, cc
.instance_layout
)
326 if cctx
.attr_sim
then
327 cc
.instance_table
= build_tables
(ga
, c
, itab
)
328 for sc
in c
.cshe
.greaters_and_self
do
329 var scc
= ga
.compiled_classes
[sc
.global
]
330 append_to_table
(cc
, cc
.instance_table
, scc
.instance_layout
)
338 private meth append_to_table
(cc
: ColorContext, table
: Array[TableElt], cmp
: TableEltComposite)
340 for j
in [0..cmp
.length
[ do
342 cc
.color
(e
) = table
.length
347 private meth build_tables
(ga
: GlobalAnalysis, c
: MMLocalClass, elts
: Array[TableElt]): Array[TableElt]
349 var tab
= new HashMap[Int, TableElt]
352 if e
.is_related_to
(c
) then
353 var col
= ga
.color
(e
)
354 var l
= col
+ e
.length
361 var res
= new Array[TableElt]
364 if tab
.has_key
(i
) then
366 for j
in [0..e
.length
[ do
379 meth colorize
(ga
: GlobalAnalysis, elts
: Array[TableElt], classes
: Collection[MMLocalClass], startcolor
: Int)
381 var colors
= new HashMap[Int, Array[TableElt]]
382 var rel_classes
= new Array[MMLocalClass]
386 if ga
.has_color
(e
) then
391 if e
.is_related_to
(c
) then
395 var trycolor
= startcolor
396 while trycolor
!= color
do
398 for c
in rel_classes
do
401 if colors
.has_key
(trycolor
+ idx
) and not free_color
(colors
[trycolor
+ idx
], c
) then
402 trycolor
= trycolor
+ idx
+ 1
412 for idx
in [0..len
[ do
413 if colors
.has_key
(color
+ idx
) then
414 colors
[color
+ idx
].add
(e
)
416 colors
[color
+ idx
] = [e
]
422 private meth free_color
(es
: Array[TableElt], c
: MMLocalClass): Bool
425 if e2
.is_related_to
(c
) then
432 # Compile module and class tables
433 meth compile_tables_to_c
(v
: CompilerVisitor)
435 for m
in mhe
.greaters_and_self
do
436 assert m
isa MMSrcModule
437 m
.compile_local_table_to_c
(v
)
440 for c
in local_classes
do
441 c
.compile_tables_to_c
(v
)
443 var s
= "classtable_t TAG2VFT[4] = \{NULL"
444 for t
in ["Int","Char","Bool"] do
445 if has_global_class_named
(t
.to_symbol
) then
446 s
.append
(", (const classtable_t)VFT_{t}")
455 # Declare class table (for _sep.h)
456 meth declare_class_tables_to_c
(v
: CompilerVisitor)
458 for c
in local_classes
do
459 if c
.global
.module == self then
460 c
.declare_tables_to_c
(v
)
465 # Compile main part (for _table.c)
466 meth compile_main_part
(v
: CompilerVisitor)
468 v
.add_instr
("int main(int argc, char **argv) \{")
470 v
.add_instr
("prepare_signals();")
471 v
.add_instr
("glob_argc = argc; glob_argv = argv;")
472 var sysname
= once
"Sys".to_symbol
473 if not has_global_class_named
(sysname
) then
476 var sys
= class_by_name
(sysname
)
477 # var initm = sys.select_method(once "init".to_symbol)
478 var mainm
= sys
.select_method
(once
"main".to_symbol
)
479 if mainm
== null then
482 #v.add_instr("G_sys = NEW_{initm.cname}();")
483 v
.add_instr
("G_sys = NEW_Sys();")
484 v
.add_instr
("{mainm.cname}(G_sys);")
487 v
.add_instr
("return 0;")
493 meth compile_mod_to_c
(v
: CompilerVisitor)
495 v
.add_decl
("extern const char *LOCATE_{name};")
496 if not v
.tc
.global
then
497 v
.add_decl
("extern const int SFT_{name}[];")
500 for e
in _local_table
do
502 v
.add_decl
("#define {e.symbol} {e.value(v.global_analysis)}")
504 v
.add_decl
("#define {e.symbol} SFT_{name}[{i}]")
508 for c
in src_local_classes
do
509 for p
in c
.src_local_properties
do
511 if pg
.intro
== p
and p
isa MMAttribute then
512 if v
.tc
.attr_sim
then
513 var bc
= pg
.local_class
514 assert bc
isa MMSrcLocalClass
515 var s
= bc
.base_attr_pos
.symbol
516 v
.add_decl
("#define {pg.attr_access}(recv) ATTRS(recv, {s}, {pg.pos_of})")
518 v
.add_decl
("#define {pg.attr_access}(recv) ATTR(recv, {pg.color_id})")
521 p
.compile_property_to_c
(v
)
526 # Compile module file for the current module
527 meth compile_local_table_to_c
(v
: CompilerVisitor)
529 v
.add_instr
("const char *LOCATE_{name} = \"{filename}\
";")
531 if v
.tc
.global
or _local_table
.is_empty
then
535 v
.add_instr
("const int SFT_{name}[{_local_table.length}] = \{")
537 for e
in _local_table
do
538 v
.add_instr
(e
.value
(v
.global_analysis
) + ",")
546 meth is_related_to
(c
: MMLocalClass): Bool is abstract
547 meth length
: Int do return 1
548 meth item
(i
: Int): TableElt do return self
549 meth compile_to_c
(v
: CompilerVisitor, c
: MMLocalClass): String is abstract
554 meth symbol
: String is abstract
555 meth value
(ga
: GlobalAnalysis): String is abstract
558 class TableEltPropPos
559 special LocalTableElt
560 attr _property
: MMLocalProperty
561 redef meth symbol
do return _property
.global
.color_id
562 redef meth value
(ga
) do return "{ga.color(self)} /* Property {_property} */"
564 init(p
: MMLocalProperty)
570 class TableEltMethPos
571 special TableEltPropPos
572 redef meth compile_to_c
(v
, c
)
574 var p
= c
[_property
.global
]
580 class TableEltSuperPos
581 special TableEltPropPos
582 redef meth symbol
do return _property
.color_id_for_super
583 redef meth compile_to_c
(v
, c
)
585 var pc
= _property
.local_class
586 var g
= _property
.global
587 var lin
= c
.che
.linear_extension
590 #print "{c.module}::{c} for {pc.module}::{pc}::{_property} try {s.module}:{s}"
593 else if found
and c
.che
< s
then
596 #print "found {s.module}::{s}::{p}"
608 class TableEltAttrPos
609 special TableEltPropPos
610 redef meth compile_to_c
(v
, c
)
612 var ga
= v
.global_analysis
613 var p
= c
[_property
.global
]
614 return "/* {ga.color(self)}: Attribute {c}::{p} */"
620 class TableEltClassPos
621 special LocalTableElt
622 attr _local_class
: MMLocalClass
623 redef meth is_related_to
(c
)
625 var bc
= c
.module[_local_class
.global
]
629 init(c
: MMLocalClass)
635 class TableEltClassIdPos
636 special TableEltClassPos
637 redef meth symbol
do return _local_class
.global
.id_id
640 return "{ga.compiled_classes[_local_class.global].id} /* Id of {_local_class} */"
646 class TableEltClassInitTablePos
647 special TableEltClassPos
648 redef meth symbol
do return _local_class
.global
.init_table_pos_id
651 return "{ga.color(self)} /* Color of {_local_class} */"
653 redef meth compile_to_c
(v
, c
)
655 var ga
= v
.global_analysis
656 var cc
= ga
.compiled_classes
[_local_class
.global
]
657 var linext
= c
.cshe
.reverse_linear_extension
659 while linext
[i
].global
!= _local_class
.global
do
662 return "{i} /* {ga.color(self)}: {c} < {cc.local_class}: superclass init_table position */"
668 class TableEltClassColorPos
669 special TableEltClassPos
670 redef meth symbol
do return _local_class
.global
.color_id
673 return "{ga.color(self)} /* Color of {_local_class} */"
675 redef meth compile_to_c
(v
, c
)
677 var ga
= v
.global_analysis
678 var cc
= ga
.compiled_classes
[_local_class
.global
]
679 return "{cc.id} /* {ga.color(self)}: {c} < {cc.local_class}: superclass typecheck marker */"
685 class TableEltBaseAttrPos
686 special LocalTableElt
687 attr _local_class
: MMSrcLocalClass
688 redef meth symbol
do return "COLOR_{_local_class.module}_{_local_class.name}_BASEATTR"
691 return "{ga.color(self)} /* BaseAttrPos of {_local_class} */"
694 redef meth compile_to_c
(v
, c
)
696 var ga
= v
.global_analysis
697 var cc
= ga
.compiled_classes
[c
.global
]
698 return "{cc.color(_local_class.instance_layout.first)} /* {ga.color(self)}: Base attribut offset of {_local_class.module}::{_local_class} in {c} */"
701 init(c
: MMSrcLocalClass)
707 class TableEltComposite
709 attr _table
: Array[LocalTableElt]
710 attr _cc
: CompiledClass
711 attr _offsets
: HashMap[MMLocalClass, Int]
712 redef meth length
do return _table
.length
713 redef meth is_related_to
(c
) do return c
.cshe
<= _cc
.local_class
715 meth add
(c
: MMLocalClass, tab
: Array[LocalTableElt])
717 _offsets
[c
] = _table
.length
721 redef meth item
(i
) do return _table
[i
]
723 redef meth compile_to_c
(v
, c
) do abort
725 init(cc
: CompiledClass)
728 _table
= new Array[LocalTableElt]
729 _offsets
= new HashMap[MMLocalClass, Int]
733 class TableEltClassSelfId
735 redef meth is_related_to
(c
) do return true
736 redef meth compile_to_c
(v
, c
)
738 var ga
= v
.global_analysis
739 return "{v.global_analysis.compiled_classes[c.global].id} /* {ga.color(self)}: Identity */"
745 class TableEltVftPointer
747 redef meth is_related_to
(c
) do return true
748 redef meth compile_to_c
(v
, c
)
750 var ga
= v
.global_analysis
751 return "/* {ga.color(self)}: Pointer to the classtable */"
757 # Used to sort local class in a deterministic total order
758 # The total order superset the class refinement and the class specialisation relations
760 special AbstractSorter[MMLocalClass]
761 redef meth compare
(a
, b
) do return a
.compare
(b
)
765 redef class MMLocalClass
766 # Comparaison in a total order that superset the class refinement and the class specialisation relations
767 meth compare
(b
: MMLocalClass): Int
772 else if a
.module.mhe
< b
.module then
774 else if b
.module.mhe
< a
.module then
784 return b
.name
.to_s
<=> a
.name
.to_s
788 # Declaration and macros related to the class table
789 meth declare_tables_to_c
(v
: CompilerVisitor)
792 var pi
= primitive_info
793 v
.add_decl
("extern const classtable_elt_t VFT_{name}[];")
795 # v.add_decl("val_t NEW_{name}(void);")
796 else if not pi
.tagged
then
798 var tbox
= "struct TBOX_{name}"
799 v
.add_decl
("{tbox} \{ const classtable_elt_t * vft; {t} val;};")
800 v
.add_decl
("val_t BOX_{name}({t} val);")
801 v
.add_decl
("#define UNBOX_{name}(x) ((({tbox} *)(VAL2OBJ(x)))->val)")
805 # Compilation of table and new (or box)
806 meth compile_tables_to_c
(v
: CompilerVisitor)
808 var cc
= v
.global_analysis
.compiled_classes
[self.global
]
809 var ctab
= cc
.class_table
810 var clen
= ctab
.length
811 if v
.global_analysis
.max_class_table_length
> ctab
.length
then
812 clen
= v
.global_analysis
.max_class_table_length
815 v
.add_instr
("const classtable_elt_t VFT_{name}[{clen}] = \{")
819 v
.add_instr
("\{0} /* Class Hole :( */,")
821 v
.add_instr
("\{(bigint) {e.compile_to_c(v, self)}},")
824 if clen
> ctab
.length
then
825 v
.add_instr
("\{0},"*(clen-ctab
.length
))
829 var itab
= cc
.instance_table
832 v
.add_instr
("/* Instance Hole :( */")
834 v
.add_instr
(e
.compile_to_c
(v
, self))
838 var pi
= primitive_info
841 var s
= "val_t NEW_{name}(void)"
842 v
.add_instr
(s
+ " \{")
847 v
.method_params
= ["OBJ2VAL(obj)"]
849 v
.add_instr
("obj_t obj;")
850 v
.add_instr
("obj = alloc(sizeof(val_t) * {itab.length});")
851 v
.add_instr
("obj->vft = (classtable_elt_t*)VFT_{name};")
852 for g
in global_properties
do
854 var t
= p
.signature
.return_type
855 if p
isa MMAttribute and t
!= null then
856 # FIXME: Not compatible with sep compilation
857 assert p
isa MMSrcAttribute
859 assert np
isa AAttrPropdef
862 var e
= ne
.compile_expr
(v
)
863 v
.add_instr
("{p.global.attr_access}(obj) = {e};")
865 var pi
= t
.local_class
.primitive_info
866 if pi
!= null and pi
.tagged
then
867 var default
= t
.default_cvalue
868 v
.add_instr
("{p.global.attr_access}(obj) = {default};")
873 v
.add_instr
("return OBJ2VAL(obj);")
874 ctx_old
.append
(v
.ctx
)
879 var init_table_size
= cshe
.greaters
.length
+ 1
880 var init_table_decl
= "int init_table[{init_table_size}] = \{0{", 0" * (init_table_size-1)}};"
882 for g
in global_properties
do
884 # FIXME skip invisible constructors
885 if not p
.global
.is_init
then continue
887 var params
= new Array[String]
889 for i
in [0..p
.signature
.arity
[ do
890 params
.add
("val_t p{i}")
893 args
.add
("init_table")
894 var s
= "val_t NEW_{self}_{p.global.intro.cname}({params.join(", ")})"
896 v
.add_instr
(s
+ " \{")
898 v
.add_instr
(init_table_decl
)
899 v
.add_instr
("val_t self = NEW_{name}();")
900 v
.add_instr
("{p.cname}({args.join(", ")});")
901 v
.add_instr
("return self;")
905 else if not pi
.tagged
then
907 var tbox
= "struct TBOX_{name}"
908 v
.add_instr
("val_t BOX_{name}({t} val) \{")
910 v
.add_instr
("{tbox} *box = ({tbox}*)alloc(sizeof({tbox}));")
911 v
.add_instr
("box->vft = VFT_{name};")
912 v
.add_instr
("box->val = val;")
913 v
.add_instr
("return OBJ2VAL(box);")