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 subtype check
109 readable attr _class_color_pos
: TableEltClassColor
111 # The proper local class table part (nor superclasses nor refinments)
112 readable attr _class_layout
: Array[LocalTableElt]
114 # The proper local instance table part (nor superclasses nor refinments)
115 readable attr _instance_layout
: Array[LocalTableElt]
117 # Build the local layout of the class and feed the module table
118 meth build_layout_in
(tc
: ToolContext, module_table
: Array[LocalTableElt])
120 var intro_methods
= new Array[MMGlobalProperty] # FIXME: Remove this
121 var intro_attributes
= new Array[MMGlobalProperty] # FIXME: Remove this
122 var clt
= new Array[LocalTableElt]
124 var ilt
= new Array[LocalTableElt]
125 _instance_layout
= ilt
127 if global
.intro
== self then
128 module_table
.add
(new TableEltClassId(self))
129 _class_color_pos
= new TableEltClassColor(self)
130 module_table
.add
(_class_color_pos
)
131 #clt.add(_class_color_pos)
132 clt
.add
(new TableEltClassInitTable(self))
134 for p
in src_local_properties
do
136 if pg
.intro
== p
then
137 if p
isa MMSrcAttribute then
138 pg
.pos_of
= intro_attributes
.length
139 intro_attributes
.add
(pg
)
140 ilt
.add
(new TableEltAttr(p
))
141 else if p
isa MMSrcMethod then
142 pg
.pos_of
= intro_methods
.length
143 intro_methods
.add
(pg
)
144 clt
.add
(new TableEltMeth(p
))
147 if p
isa MMSrcMethod and p
.need_super
then
148 clt
.add
(new TableEltSuper(p
))
151 module_table
.append
(ilt
)
152 module_table
.append
(clt
)
156 redef class MMSrcModule
157 # The local table of the module (refers things introduced in the module)
158 attr _local_table
: Array[LocalTableElt]
160 # Builds the local tables and local classes layouts
161 meth local_analysis
(tc
: ToolContext)
163 var lt
= new Array[LocalTableElt]
165 for c
in src_local_classes
do
166 c
.build_layout_in
(tc
, lt
)
170 # Do the complete global analysis
171 meth global_analysis
(cctx
: ToolContext): GlobalAnalysis
173 #print "Do the complete global analysis"
174 var ga
= new GlobalAnalysis(self)
175 var smallest_classes
= new Array[MMLocalClass]
176 var global_properties
= new HashSet[MMGlobalProperty]
177 var ctab
= new Array[TableElt]
178 var itab
= new Array[TableElt]
180 ctab
.add
(new TableEltClassSelfId)
181 itab
.add
(new TableEltVftPointer)
186 # We have to work on ALL the classes of the module
187 var classes
= new Array[MMLocalClass]
188 for c
in local_classes
do
189 c
.compute_super_classes
192 (new ClassSorter).sort
(classes
)
195 # Finish processing the class (if invisible)
197 c
.inherit_global_properties
199 # Associate a CompiledClass to the class
200 var cc
= new CompiledClass(c
)
201 ga
.compiled_classes
[c
.global
] = cc
203 # Assign a unique class identifier
204 # (negative are for primitive classes)
207 if c
.primitive_info
!= null then
209 pclassid
= pclassid
- 4
212 classid
= classid
+ 4
215 # Register is the class is a leaf
216 if c
.cshe
.direct_smallers
.is_empty
then
217 smallest_classes
.add
(c
)
220 # Store the colortableelt in the class table pool
221 var bc
= c
.global
.intro
222 assert bc
isa MMSrcLocalClass
223 ctab
.add
(bc
.class_color_pos
)
226 # Compute core and crown classes for colorization
227 var crown_classes
= new HashSet[MMLocalClass]
228 var core_classes
= new HashSet[MMLocalClass]
229 for c
in smallest_classes
do
230 while c
.cshe
.direct_greaters
.length
== 1 do
231 c
= c
.cshe
.direct_greaters
.first
234 core_classes
.add_all
(c
.cshe
.greaters_and_self
)
236 #print("nbclasses: {classes.length} leaves: {smallest_classes.length} crown: {crown_classes.length} core: {core_classes.length}")
238 # Colorize core color for typechecks
239 colorize
(ga
, ctab
, crown_classes
, 0)
241 # Compute tables for typechecks
244 var cc
= ga
.compiled_classes
[c
.global
]
245 if core_classes
.has
(c
) then
246 # For core classes, just build the table
247 cc
.class_table
= build_tables
(ga
, c
, ctab
)
248 if maxcolor
< cc
.class_table
.length
then maxcolor
= cc
.class_table
.length
250 # For other classes, it's easier: just append to the parent tables
251 var sc
= c
.cshe
.direct_greaters
.first
252 var scc
= ga
.compiled_classes
[sc
.global
]
253 cc
.class_table
= scc
.class_table
.to_a
254 var bc
= c
.global
.intro
255 assert bc
isa MMSrcLocalClass
256 var colpos
= bc
.class_color_pos
257 var colposcolor
= cc
.class_table
.length
258 ga
.color
(colpos
) = colposcolor
259 cc
.class_table
.add
(colpos
)
260 if maxcolor
< colposcolor
then maxcolor
= colposcolor
263 ga
.max_class_table_length
= maxcolor
+ 1
265 # Fill class table and instance tables pools
267 var cc
= ga
.compiled_classes
[c
.global
]
268 var cte
= new TableEltComposite(cc
)
269 var ite
= new TableEltComposite(cc
)
270 for sc
in c
.crhe
.greaters_and_self
do
271 if sc
isa MMSrcLocalClass then
272 cte
.add
(sc
, sc
.class_layout
)
273 ite
.add
(sc
, sc
.instance_layout
)
275 cc
.class_layout
= cte
276 cc
.instance_layout
= ite
279 if core_classes
.has
(c
) then
280 if cte
.length
> 0 then
283 if ite
.length
> 0 then
289 # Colorize all elements in pools tables
290 colorize
(ga
, ctab
, crown_classes
, maxcolor
+1)
291 colorize
(ga
, itab
, crown_classes
, 0)
293 # Build class and instance tables now things are colored
294 ga
.max_class_table_length
= 0
296 var cc
= ga
.compiled_classes
[c
.global
]
297 if core_classes
.has
(c
) then
298 # For core classes, just build the table
299 cc
.class_table
= build_tables
(ga
, c
, ctab
)
300 cc
.instance_table
= build_tables
(ga
, c
, itab
)
302 # For other classes, it's easier: just append to the parent tables
303 var sc
= c
.cshe
.direct_greaters
.first
304 var scc
= ga
.compiled_classes
[sc
.global
]
305 cc
.class_table
= scc
.class_table
.to_a
306 var bc
= c
.global
.intro
307 assert bc
isa MMSrcLocalClass
308 var colpos
= bc
.class_color_pos
309 cc
.class_table
[ga
.color
(colpos
)] = colpos
310 while cc
.class_table
.length
<= maxcolor
do
311 cc
.class_table
.add
(null)
313 append_to_table
(ga
, cc
.class_table
, cc
.class_layout
)
314 cc
.instance_table
= scc
.instance_table
.to_a
315 append_to_table
(ga
, cc
.instance_table
, cc
.instance_layout
)
322 private meth append_to_table
(cc
: ColorContext, table
: Array[TableElt], cmp
: TableEltComposite)
324 for j
in [0..cmp
.length
[ do
326 cc
.color
(e
) = table
.length
331 private meth build_tables
(ga
: GlobalAnalysis, c
: MMLocalClass, elts
: Array[TableElt]): Array[TableElt]
333 var tab
= new HashMap[Int, TableElt]
336 if e
.is_related_to
(c
) then
337 var col
= ga
.color
(e
)
338 var l
= col
+ e
.length
345 var res
= new Array[TableElt]
348 if tab
.has_key
(i
) then
350 for j
in [0..e
.length
[ do
363 meth colorize
(ga
: GlobalAnalysis, elts
: Array[TableElt], classes
: Collection[MMLocalClass], startcolor
: Int)
365 var colors
= new HashMap[Int, Array[TableElt]]
366 var rel_classes
= new Array[MMLocalClass]
370 if ga
.has_color
(e
) then
375 if e
.is_related_to
(c
) then
379 var trycolor
= startcolor
380 while trycolor
!= color
do
382 for c
in rel_classes
do
385 if colors
.has_key
(trycolor
+ idx
) and not free_color
(colors
[trycolor
+ idx
], c
) then
386 trycolor
= trycolor
+ idx
+ 1
396 for idx
in [0..len
[ do
397 if colors
.has_key
(color
+ idx
) then
398 colors
[color
+ idx
].add
(e
)
400 colors
[color
+ idx
] = [e
]
406 private meth free_color
(es
: Array[TableElt], c
: MMLocalClass): Bool
409 if e2
.is_related_to
(c
) then
416 # Compile module and class tables
417 meth compile_tables_to_c
(v
: CompilerVisitor)
419 for m
in mhe
.greaters_and_self
do
420 assert m
isa MMSrcModule
421 m
.compile_local_table_to_c
(v
)
424 for c
in local_classes
do
425 c
.compile_tables_to_c
(v
)
427 var s
= "classtable_t TAG2VFT[4] = \{NULL"
428 for t
in ["Int","Char","Bool"] do
429 if has_global_class_named
(t
.to_symbol
) then
430 s
.append
(", (const classtable_t)VFT_{t}")
439 # Declare class table (for _sep.h)
440 meth declare_class_tables_to_c
(v
: CompilerVisitor)
442 for c
in local_classes
do
443 if c
.global
.module == self then
444 c
.declare_tables_to_c
(v
)
449 # Compile main part (for _table.c)
450 meth compile_main_part
(v
: CompilerVisitor)
452 v
.add_instr
("int main(int argc, char **argv) \{")
454 v
.add_instr
("prepare_signals();")
455 v
.add_instr
("glob_argc = argc; glob_argv = argv;")
456 var sysname
= once
"Sys".to_symbol
457 if not has_global_class_named
(sysname
) then
460 var sys
= class_by_name
(sysname
)
461 # var initm = sys.select_method(once "init".to_symbol)
462 var mainm
= sys
.select_method
(once
"main".to_symbol
)
463 if mainm
== null then
466 #v.add_instr("G_sys = NEW_{initm.cname}();")
467 v
.add_instr
("G_sys = NEW_Sys();")
468 v
.add_instr
("{mainm.cname}(G_sys);")
471 v
.add_instr
("return 0;")
477 meth compile_mod_to_c
(v
: CompilerVisitor)
479 v
.add_decl
("extern const char *LOCATE_{name};")
480 if not v
.tc
.global
then
481 v
.add_decl
("extern const int SFT_{name}[];")
484 for e
in _local_table
do
487 value
= "{e.value(v.global_analysis)}"
489 value
= "SFT_{name}[{i}]"
492 e
.compile_macros
(v
, value
)
494 for c
in src_local_classes
do
495 for pg
in c
.global_properties
do
497 if p
.local_class
== c
then
498 p
.compile_property_to_c
(v
)
500 if pg
.is_init_for
(c
) then
501 # Declare constructors
502 var params
= new Array[String]
503 for i
in [0..p
.signature
.arity
[ do
504 params
.add
("val_t p{i}")
506 v
.add_decl
("val_t NEW_{c}_{p.global.intro.cname}({params.join(", ")});")
512 # Compile module file for the current module
513 meth compile_local_table_to_c
(v
: CompilerVisitor)
515 v
.add_instr
("const char *LOCATE_{name} = \"{filename}\
";")
517 if v
.tc
.global
or _local_table
.is_empty
then
521 v
.add_instr
("const int SFT_{name}[{_local_table.length}] = \{")
523 for e
in _local_table
do
524 v
.add_instr
(e
.value
(v
.global_analysis
) + ",")
531 abstract class TableElt
532 meth is_related_to
(c
: MMLocalClass): Bool is abstract
533 meth length
: Int do return 1
534 meth item
(i
: Int): TableElt do return self
535 meth compile_macros
(v
: CompilerVisitor, value
: String) is abstract
536 meth compile_to_c
(v
: CompilerVisitor, c
: MMLocalClass): String is abstract
539 abstract class LocalTableElt
541 meth value
(ga
: GlobalAnalysis): String is abstract
544 abstract class TableEltProp
545 special LocalTableElt
546 attr _property
: MMLocalProperty
548 redef meth value
(ga
) do return "{ga.color(self)} /* Property {_property} */"
550 init(p
: MMLocalProperty)
558 redef meth compile_macros
(v
, value
)
560 var pg
= _property
.global
561 v
.add_decl
("#define {pg.meth_call}(recv) (({pg.intro.cname}_t)CALL((recv), ({value})))")
564 redef meth compile_to_c
(v
, c
)
566 var p
= c
[_property
.global
]
574 redef meth compile_macros
(v
, value
)
577 v
.add_decl
("#define {p.super_meth_call}(recv) (({p.cname}_t)CALL((recv), ({value})))")
580 redef meth compile_to_c
(v
, c
)
582 var pc
= _property
.local_class
583 var g
= _property
.global
584 var lin
= c
.che
.linear_extension
587 #print "{c.module}::{c} for {pc.module}::{pc}::{_property} try {s.module}:{s}"
590 else if found
and c
.che
< s
then
593 #print "found {s.module}::{s}::{p}"
607 redef meth compile_macros
(v
, value
)
609 var pg
= _property
.global
610 v
.add_decl
("#define {pg.attr_access}(recv) ATTR(recv, ({value}))")
613 redef meth compile_to_c
(v
, c
)
615 var ga
= v
.global_analysis
616 var p
= c
[_property
.global
]
617 return "/* {ga.color(self)}: Attribute {c}::{p} */"
624 special LocalTableElt
625 attr _local_class
: MMLocalClass
626 redef meth is_related_to
(c
)
628 var bc
= c
.module[_local_class
.global
]
632 init(c
: MMLocalClass)
637 meth symbol
: String is abstract
639 redef meth compile_macros
(v
, value
)
641 v
.add_decl
("#define {symbol} ({value})")
645 class TableEltClassId
646 special TableEltClass
647 redef meth symbol
do return _local_class
.global
.id_id
651 return "{ga.compiled_classes[_local_class.global].id} /* Id of {_local_class} */"
657 class TableEltClassInitTable
658 special TableEltClass
659 redef meth symbol
do return _local_class
.global
.init_table_pos_id
663 return "{ga.color(self)} /* Color of {_local_class} */"
666 redef meth compile_to_c
(v
, c
)
668 var ga
= v
.global_analysis
669 var cc
= ga
.compiled_classes
[_local_class
.global
]
670 var linext
= c
.cshe
.reverse_linear_extension
672 while linext
[i
].global
!= _local_class
.global
do
675 return "{i} /* {ga.color(self)}: {c} < {cc.local_class}: superclass init_table position */"
681 class TableEltClassColor
682 special TableEltClass
683 redef meth symbol
do return _local_class
.global
.color_id
687 return "{ga.color(self)} /* Color of {_local_class} */"
689 redef meth compile_to_c
(v
, c
)
691 var ga
= v
.global_analysis
692 var cc
= ga
.compiled_classes
[_local_class
.global
]
693 return "{cc.id} /* {ga.color(self)}: {c} < {cc.local_class}: superclass typecheck marker */"
699 class TableEltComposite
701 attr _table
: Array[LocalTableElt]
702 attr _cc
: CompiledClass
703 attr _offsets
: HashMap[MMLocalClass, Int]
704 redef meth length
do return _table
.length
705 redef meth is_related_to
(c
) do return c
.cshe
<= _cc
.local_class
707 meth add
(c
: MMLocalClass, tab
: Array[LocalTableElt])
709 _offsets
[c
] = _table
.length
713 redef meth item
(i
) do return _table
[i
]
715 redef meth compile_to_c
(v
, c
) do abort
717 init(cc
: CompiledClass)
720 _table
= new Array[LocalTableElt]
721 _offsets
= new HashMap[MMLocalClass, Int]
725 class TableEltClassSelfId
727 redef meth is_related_to
(c
) do return true
728 redef meth compile_to_c
(v
, c
)
730 var ga
= v
.global_analysis
731 return "{v.global_analysis.compiled_classes[c.global].id} /* {ga.color(self)}: Identity */"
737 class TableEltVftPointer
739 redef meth is_related_to
(c
) do return true
740 redef meth compile_to_c
(v
, c
)
742 var ga
= v
.global_analysis
743 return "/* {ga.color(self)}: Pointer to the classtable */"
749 # Used to sort local class in a deterministic total order
750 # The total order superset the class refinement and the class specialisation relations
752 special AbstractSorter[MMLocalClass]
753 redef meth compare
(a
, b
) do return a
.compare
(b
)
757 redef class MMLocalClass
758 # Comparaison in a total order that superset the class refinement and the class specialisation relations
759 meth compare
(b
: MMLocalClass): Int
764 else if a
.module.mhe
< b
.module then
766 else if b
.module.mhe
< a
.module then
776 return b
.name
.to_s
<=> a
.name
.to_s
780 # Declaration and macros related to the class table
781 meth declare_tables_to_c
(v
: CompilerVisitor)
784 var pi
= primitive_info
785 v
.add_decl
("extern const classtable_elt_t VFT_{name}[];")
787 # v.add_decl("val_t NEW_{name}(void);")
788 else if not pi
.tagged
then
790 var tbox
= "struct TBOX_{name}"
791 v
.add_decl
("{tbox} \{ const classtable_elt_t * vft; {t} val;};")
792 v
.add_decl
("val_t BOX_{name}({t} val);")
793 v
.add_decl
("#define UNBOX_{name}(x) ((({tbox} *)(VAL2OBJ(x)))->val)")
797 # Compilation of table and new (or box)
798 meth compile_tables_to_c
(v
: CompilerVisitor)
800 var cc
= v
.global_analysis
.compiled_classes
[self.global
]
801 var ctab
= cc
.class_table
802 var clen
= ctab
.length
803 if v
.global_analysis
.max_class_table_length
> ctab
.length
then
804 clen
= v
.global_analysis
.max_class_table_length
807 v
.add_instr
("const classtable_elt_t VFT_{name}[{clen}] = \{")
811 v
.add_instr
("\{0} /* Class Hole :( */,")
813 v
.add_instr
("\{(bigint) {e.compile_to_c(v, self)}},")
816 if clen
> ctab
.length
then
817 v
.add_instr
("\{0},"*(clen-ctab
.length
))
821 var itab
= cc
.instance_table
824 v
.add_instr
("/* Instance Hole :( */")
826 v
.add_instr
(e
.compile_to_c
(v
, self))
830 var pi
= primitive_info
832 v
.cfc
= new CFunctionContext(v
)
833 v
.nmc
= new NitMethodContext(null)
834 var s
= "val_t NEW_{name}(void)"
835 v
.add_instr
(s
+ " \{")
840 var self_var
= new ParamVariable(null, null)
841 var self_var_cname
= v
.cfc
.register_variable
(self_var
)
842 v
.nmc
.method_params
= [self_var
]
844 v
.add_instr
("obj_t obj;")
845 v
.add_instr
("obj = alloc(sizeof(val_t) * {itab.length});")
846 v
.add_instr
("obj->vft = (classtable_elt_t*)VFT_{name};")
847 v
.add_assignment
(self_var_cname
, "OBJ2VAL(obj)")
849 for g
in global_properties
do
851 var t
= p
.signature
.return_type
852 if p
isa MMAttribute and t
!= null then
853 # FIXME: Not compatible with sep compilation
854 assert p
isa MMSrcAttribute
856 assert np
isa AAttrPropdef
859 var e
= ne
.compile_expr
(v
)
860 v
.add_instr
("{p.global.attr_access}(obj) = {e};")
862 var pi
= t
.local_class
.primitive_info
863 if pi
!= null and pi
.tagged
then
864 var default
= t
.default_cvalue
865 v
.add_instr
("{p.global.attr_access}(obj) = {default};")
870 v
.add_instr
("return OBJ2VAL(obj);")
871 v
.cfc
.generate_var_decls
872 ctx_old
.append
(v
.ctx
)
877 var init_table_size
= cshe
.greaters
.length
+ 1
878 var init_table_decl
= "int init_table[{init_table_size}] = \{0{", 0" * (init_table_size-1)}};"
880 for g
in global_properties
do
882 # FIXME skip invisible constructors
883 if not p
.global
.is_init_for
(self) then continue
884 var params
= new Array[String]
886 for i
in [0..p
.signature
.arity
[ do
887 params
.add
("val_t p{i}")
890 args
.add
("init_table")
891 var s
= "val_t NEW_{self}_{p.global.intro.cname}({params.join(", ")}) \{"
894 v
.add_instr
(init_table_decl
)
895 v
.add_instr
("val_t self = NEW_{name}();")
896 v
.add_instr
("{p.cname}({args.join(", ")});")
897 v
.add_instr
("return self;")
901 else if not pi
.tagged
then
903 var tbox
= "struct TBOX_{name}"
904 v
.add_instr
("val_t BOX_{name}({t} val) \{")
906 v
.add_instr
("{tbox} *box = ({tbox}*)alloc(sizeof({tbox}));")
907 v
.add_instr
("box->vft = VFT_{name};")
908 v
.add_instr
("box->val = val;")
909 v
.add_instr
("return OBJ2VAL(box);")