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 MMSrcLocalClass
102 # The table element of the subtype check
103 readable attr _class_color_pos
: TableEltClassColor
105 # The proper local class table part (nor superclasses nor refinments)
106 readable attr _class_layout
: Array[LocalTableElt]
108 # The proper local instance table part (nor superclasses nor refinments)
109 readable attr _instance_layout
: Array[LocalTableElt]
111 # Build the local layout of the class and feed the module table
112 meth build_layout_in
(tc
: ToolContext, module_table
: Array[LocalTableElt])
114 var clt
= new Array[LocalTableElt]
116 var ilt
= new Array[LocalTableElt]
117 _instance_layout
= ilt
119 if global
.intro
== self then
120 module_table
.add
(new TableEltClassId(self))
121 _class_color_pos
= new TableEltClassColor(self)
122 module_table
.add
(_class_color_pos
)
123 clt
.add
(new TableEltClassInitTable(self))
125 for p
in src_local_properties
do
127 if pg
.intro
== p
then
128 if p
isa MMSrcAttribute then
129 ilt
.add
(new TableEltAttr(p
))
130 else if p
isa MMSrcMethod then
131 clt
.add
(new TableEltMeth(p
))
134 if p
isa MMSrcMethod and p
.need_super
then
135 clt
.add
(new TableEltSuper(p
))
138 module_table
.append
(ilt
)
139 module_table
.append
(clt
)
143 redef class MMSrcModule
144 # The local table of the module (refers things introduced in the module)
145 attr _local_table
: Array[LocalTableElt]
147 # Builds the local tables and local classes layouts
148 meth local_analysis
(tc
: ToolContext)
150 var lt
= new Array[LocalTableElt]
152 for c
in src_local_classes
do
153 c
.build_layout_in
(tc
, lt
)
157 # Do the complete global analysis
158 meth global_analysis
(cctx
: ToolContext): GlobalAnalysis
160 #print "Do the complete global analysis"
161 var ga
= new GlobalAnalysis(self)
162 var smallest_classes
= new Array[MMLocalClass]
163 var global_properties
= new HashSet[MMGlobalProperty]
164 var ctab
= new Array[TableElt]
165 var itab
= new Array[TableElt]
167 ctab
.add
(new TableEltClassSelfId)
168 itab
.add
(new TableEltVftPointer)
173 # We have to work on ALL the classes of the module
174 var classes
= new Array[MMLocalClass]
175 for c
in local_classes
do
176 c
.compute_super_classes
179 (new ClassSorter).sort
(classes
)
182 # Finish processing the class (if invisible)
184 c
.inherit_global_properties
186 # Associate a CompiledClass to the class
187 var cc
= new CompiledClass(c
)
188 ga
.compiled_classes
[c
.global
] = cc
190 # Assign a unique class identifier
191 # (negative are for primitive classes)
194 if c
.primitive_info
!= null then
196 pclassid
= pclassid
- 4
199 classid
= classid
+ 4
202 # Register is the class is a leaf
203 if c
.cshe
.direct_smallers
.is_empty
then
204 smallest_classes
.add
(c
)
207 # Store the colortableelt in the class table pool
208 var bc
= c
.global
.intro
209 assert bc
isa MMSrcLocalClass
210 ctab
.add
(bc
.class_color_pos
)
213 # Compute core and crown classes for colorization
214 var crown_classes
= new HashSet[MMLocalClass]
215 var core_classes
= new HashSet[MMLocalClass]
216 for c
in smallest_classes
do
217 while c
.cshe
.direct_greaters
.length
== 1 do
218 c
= c
.cshe
.direct_greaters
.first
221 core_classes
.add_all
(c
.cshe
.greaters_and_self
)
223 #print("nbclasses: {classes.length} leaves: {smallest_classes.length} crown: {crown_classes.length} core: {core_classes.length}")
225 # Colorize core color for typechecks
226 colorize
(ga
, ctab
, crown_classes
, 0)
228 # Compute tables for typechecks
231 var cc
= ga
.compiled_classes
[c
.global
]
232 if core_classes
.has
(c
) then
233 # For core classes, just build the table
234 cc
.class_table
= build_tables
(ga
, c
, ctab
)
235 if maxcolor
< cc
.class_table
.length
then maxcolor
= cc
.class_table
.length
237 # For other classes, it's easier: just append to the parent tables
238 var sc
= c
.cshe
.direct_greaters
.first
239 var scc
= ga
.compiled_classes
[sc
.global
]
240 cc
.class_table
= scc
.class_table
.to_a
241 var bc
= c
.global
.intro
242 assert bc
isa MMSrcLocalClass
243 var colpos
= bc
.class_color_pos
244 var colposcolor
= cc
.class_table
.length
245 ga
.color
(colpos
) = colposcolor
246 cc
.class_table
.add
(colpos
)
247 if maxcolor
< colposcolor
then maxcolor
= colposcolor
250 ga
.max_class_table_length
= maxcolor
+ 1
252 # Fill class table and instance tables pools
254 var cc
= ga
.compiled_classes
[c
.global
]
255 var cte
= new TableEltComposite(cc
)
256 var ite
= new TableEltComposite(cc
)
257 for sc
in c
.crhe
.greaters_and_self
do
258 if sc
isa MMSrcLocalClass then
259 cte
.add
(sc
, sc
.class_layout
)
260 ite
.add
(sc
, sc
.instance_layout
)
262 cc
.class_layout
= cte
263 cc
.instance_layout
= ite
266 if core_classes
.has
(c
) then
267 if cte
.length
> 0 then
270 if ite
.length
> 0 then
276 # Colorize all elements in pools tables
277 colorize
(ga
, ctab
, crown_classes
, maxcolor
+1)
278 colorize
(ga
, itab
, crown_classes
, 0)
280 # Build class and instance tables now things are colored
281 ga
.max_class_table_length
= 0
283 var cc
= ga
.compiled_classes
[c
.global
]
284 if core_classes
.has
(c
) then
285 # For core classes, just build the table
286 cc
.class_table
= build_tables
(ga
, c
, ctab
)
287 cc
.instance_table
= build_tables
(ga
, c
, itab
)
289 # For other classes, it's easier: just append to the parent tables
290 var sc
= c
.cshe
.direct_greaters
.first
291 var scc
= ga
.compiled_classes
[sc
.global
]
292 cc
.class_table
= scc
.class_table
.to_a
293 var bc
= c
.global
.intro
294 assert bc
isa MMSrcLocalClass
295 var colpos
= bc
.class_color_pos
296 cc
.class_table
[ga
.color
(colpos
)] = colpos
297 while cc
.class_table
.length
<= maxcolor
do
298 cc
.class_table
.add
(null)
300 append_to_table
(ga
, cc
.class_table
, cc
.class_layout
)
301 cc
.instance_table
= scc
.instance_table
.to_a
302 append_to_table
(ga
, cc
.instance_table
, cc
.instance_layout
)
309 private meth append_to_table
(cc
: ColorContext, table
: Array[TableElt], cmp
: TableEltComposite)
311 for j
in [0..cmp
.length
[ do
313 cc
.color
(e
) = table
.length
318 private meth build_tables
(ga
: GlobalAnalysis, c
: MMLocalClass, elts
: Array[TableElt]): Array[TableElt]
320 var tab
= new HashMap[Int, TableElt]
323 if e
.is_related_to
(c
) then
324 var col
= ga
.color
(e
)
325 var l
= col
+ e
.length
332 var res
= new Array[TableElt]
335 if tab
.has_key
(i
) then
337 for j
in [0..e
.length
[ do
350 meth colorize
(ga
: GlobalAnalysis, elts
: Array[TableElt], classes
: Collection[MMLocalClass], startcolor
: Int)
352 var colors
= new HashMap[Int, Array[TableElt]]
353 var rel_classes
= new Array[MMLocalClass]
357 if ga
.has_color
(e
) then
362 if e
.is_related_to
(c
) then
366 var trycolor
= startcolor
367 while trycolor
!= color
do
369 for c
in rel_classes
do
372 if colors
.has_key
(trycolor
+ idx
) and not free_color
(colors
[trycolor
+ idx
], c
) then
373 trycolor
= trycolor
+ idx
+ 1
383 for idx
in [0..len
[ do
384 if colors
.has_key
(color
+ idx
) then
385 colors
[color
+ idx
].add
(e
)
387 colors
[color
+ idx
] = [e
]
393 private meth free_color
(es
: Array[TableElt], c
: MMLocalClass): Bool
396 if e2
.is_related_to
(c
) then
403 # Compile module and class tables
404 meth compile_tables_to_c
(v
: CompilerVisitor)
406 for m
in mhe
.greaters_and_self
do
407 assert m
isa MMSrcModule
408 m
.compile_local_table_to_c
(v
)
411 for c
in local_classes
do
412 c
.compile_tables_to_c
(v
)
414 var s
= "classtable_t TAG2VFT[4] = \{NULL"
415 for t
in ["Int","Char","Bool"] do
416 if has_global_class_named
(t
.to_symbol
) then
417 s
.append
(", (const classtable_t)VFT_{t}")
426 # Declare class table (for _sep.h)
427 meth declare_class_tables_to_c
(v
: CompilerVisitor)
429 for c
in local_classes
do
430 if c
.global
.module == self then
431 c
.declare_tables_to_c
(v
)
436 # Compile main part (for _table.c)
437 meth compile_main_part
(v
: CompilerVisitor)
439 v
.add_instr
("int main(int argc, char **argv) \{")
441 v
.add_instr
("prepare_signals();")
442 v
.add_instr
("glob_argc = argc; glob_argv = argv;")
443 var sysname
= once
"Sys".to_symbol
444 if not has_global_class_named
(sysname
) then
447 var sys
= class_by_name
(sysname
)
448 # var initm = sys.select_method(once "init".to_symbol)
449 var mainm
= sys
.select_method
(once
"main".to_symbol
)
450 if mainm
== null then
453 #v.add_instr("G_sys = NEW_{initm.cname}();")
454 v
.add_instr
("G_sys = NEW_Sys();")
455 v
.add_instr
("{mainm.cname}(G_sys);")
458 v
.add_instr
("return 0;")
464 meth compile_mod_to_c
(v
: CompilerVisitor)
466 v
.add_decl
("extern const char *LOCATE_{name};")
467 if not v
.tc
.global
then
468 v
.add_decl
("extern const int SFT_{name}[];")
471 for e
in _local_table
do
474 value
= "{e.value(v.global_analysis)}"
476 value
= "SFT_{name}[{i}]"
479 e
.compile_macros
(v
, value
)
481 for c
in src_local_classes
do
482 for pg
in c
.global_properties
do
484 if p
.local_class
== c
then
485 p
.compile_property_to_c
(v
)
487 if pg
.is_init_for
(c
) then
488 # Declare constructors
489 var params
= new Array[String]
490 for i
in [0..p
.signature
.arity
[ do
491 params
.add
("val_t p{i}")
493 v
.add_decl
("val_t NEW_{c}_{p.global.intro.cname}({params.join(", ")});")
499 # Compile module file for the current module
500 meth compile_local_table_to_c
(v
: CompilerVisitor)
502 v
.add_instr
("const char *LOCATE_{name} = \"{filename}\
";")
504 if v
.tc
.global
or _local_table
.is_empty
then
508 v
.add_instr
("const int SFT_{name}[{_local_table.length}] = \{")
510 for e
in _local_table
do
511 v
.add_instr
(e
.value
(v
.global_analysis
) + ",")
518 abstract class TableElt
519 meth is_related_to
(c
: MMLocalClass): Bool is abstract
520 meth length
: Int do return 1
521 meth item
(i
: Int): TableElt do return self
522 meth compile_macros
(v
: CompilerVisitor, value
: String) is abstract
523 meth compile_to_c
(v
: CompilerVisitor, c
: MMLocalClass): String is abstract
526 abstract class LocalTableElt
528 meth value
(ga
: GlobalAnalysis): String is abstract
531 abstract class TableEltProp
532 special LocalTableElt
533 attr _property
: MMLocalProperty
535 redef meth value
(ga
) do return "{ga.color(self)} /* Property {_property} */"
537 init(p
: MMLocalProperty)
545 redef meth compile_macros
(v
, value
)
547 var pg
= _property
.global
548 v
.add_decl
("#define {pg.meth_call}(recv) (({pg.intro.cname}_t)CALL((recv), ({value})))")
551 redef meth compile_to_c
(v
, c
)
553 var p
= c
[_property
.global
]
561 redef meth compile_macros
(v
, value
)
564 v
.add_decl
("#define {p.super_meth_call}(recv) (({p.cname}_t)CALL((recv), ({value})))")
567 redef meth compile_to_c
(v
, c
)
569 var pc
= _property
.local_class
570 var g
= _property
.global
571 var lin
= c
.che
.linear_extension
574 #print "{c.module}::{c} for {pc.module}::{pc}::{_property} try {s.module}:{s}"
577 else if found
and c
.che
< s
then
580 #print "found {s.module}::{s}::{p}"
594 redef meth compile_macros
(v
, value
)
596 var pg
= _property
.global
597 v
.add_decl
("#define {pg.attr_access}(recv) ATTR(recv, ({value}))")
600 redef meth compile_to_c
(v
, c
)
602 var ga
= v
.global_analysis
603 var p
= c
[_property
.global
]
604 return "/* {ga.color(self)}: Attribute {c}::{p} */"
611 special LocalTableElt
612 attr _local_class
: MMLocalClass
613 redef meth is_related_to
(c
)
615 var bc
= c
.module[_local_class
.global
]
619 init(c
: MMLocalClass)
624 meth symbol
: String is abstract
626 redef meth compile_macros
(v
, value
)
628 v
.add_decl
("#define {symbol} ({value})")
632 class TableEltClassId
633 special TableEltClass
634 redef meth symbol
do return _local_class
.global
.id_id
638 return "{ga.compiled_classes[_local_class.global].id} /* Id of {_local_class} */"
644 class TableEltClassInitTable
645 special TableEltClass
646 redef meth symbol
do return _local_class
.global
.init_table_pos_id
650 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 TableEltClassColor
669 special TableEltClass
670 redef meth symbol
do return _local_class
.global
.color_id
674 return "{ga.color(self)} /* Color of {_local_class} */"
676 redef meth compile_to_c
(v
, c
)
678 var ga
= v
.global_analysis
679 var cc
= ga
.compiled_classes
[_local_class
.global
]
680 return "{cc.id} /* {ga.color(self)}: {c} < {cc.local_class}: superclass typecheck marker */"
686 class TableEltComposite
688 attr _table
: Array[LocalTableElt]
689 attr _cc
: CompiledClass
690 attr _offsets
: HashMap[MMLocalClass, Int]
691 redef meth length
do return _table
.length
692 redef meth is_related_to
(c
) do return c
.cshe
<= _cc
.local_class
694 meth add
(c
: MMLocalClass, tab
: Array[LocalTableElt])
696 _offsets
[c
] = _table
.length
700 redef meth item
(i
) do return _table
[i
]
702 redef meth compile_to_c
(v
, c
) do abort
704 init(cc
: CompiledClass)
707 _table
= new Array[LocalTableElt]
708 _offsets
= new HashMap[MMLocalClass, Int]
712 class TableEltClassSelfId
714 redef meth is_related_to
(c
) do return true
715 redef meth compile_to_c
(v
, c
)
717 var ga
= v
.global_analysis
718 return "{v.global_analysis.compiled_classes[c.global].id} /* {ga.color(self)}: Identity */"
724 class TableEltVftPointer
726 redef meth is_related_to
(c
) do return true
727 redef meth compile_to_c
(v
, c
)
729 var ga
= v
.global_analysis
730 return "/* {ga.color(self)}: Pointer to the classtable */"
736 # Used to sort local class in a deterministic total order
737 # The total order superset the class refinement and the class specialisation relations
739 special AbstractSorter[MMLocalClass]
740 redef meth compare
(a
, b
) do return a
.compare
(b
)
744 redef class MMLocalClass
745 # Comparaison in a total order that superset the class refinement and the class specialisation relations
746 meth compare
(b
: MMLocalClass): Int
751 else if a
.module.mhe
< b
.module then
753 else if b
.module.mhe
< a
.module then
763 return b
.name
.to_s
<=> a
.name
.to_s
767 # Declaration and macros related to the class table
768 meth declare_tables_to_c
(v
: CompilerVisitor)
771 var pi
= primitive_info
772 v
.add_decl
("extern const classtable_elt_t VFT_{name}[];")
774 # v.add_decl("val_t NEW_{name}(void);")
775 else if not pi
.tagged
then
777 var tbox
= "struct TBOX_{name}"
778 v
.add_decl
("{tbox} \{ const classtable_elt_t * vft; {t} val;};")
779 v
.add_decl
("val_t BOX_{name}({t} val);")
780 v
.add_decl
("#define UNBOX_{name}(x) ((({tbox} *)(VAL2OBJ(x)))->val)")
784 # Compilation of table and new (or box)
785 meth compile_tables_to_c
(v
: CompilerVisitor)
787 var cc
= v
.global_analysis
.compiled_classes
[self.global
]
788 var ctab
= cc
.class_table
789 var clen
= ctab
.length
790 if v
.global_analysis
.max_class_table_length
> ctab
.length
then
791 clen
= v
.global_analysis
.max_class_table_length
794 v
.add_instr
("const classtable_elt_t VFT_{name}[{clen}] = \{")
798 v
.add_instr
("\{0} /* Class Hole :( */,")
800 v
.add_instr
("\{(bigint) {e.compile_to_c(v, self)}},")
803 if clen
> ctab
.length
then
804 v
.add_instr
("\{0},"*(clen-ctab
.length
))
808 var itab
= cc
.instance_table
811 v
.add_instr
("/* Instance Hole :( */")
813 v
.add_instr
(e
.compile_to_c
(v
, self))
817 var pi
= primitive_info
819 v
.cfc
= new CFunctionContext(v
)
820 v
.nmc
= new NitMethodContext(null)
821 var s
= "val_t NEW_{name}(void)"
822 v
.add_instr
(s
+ " \{")
827 var self_var
= new ParamVariable(null, null)
828 var self_var_cname
= v
.cfc
.register_variable
(self_var
)
829 v
.nmc
.method_params
= [self_var
]
831 v
.add_instr
("obj_t obj;")
832 v
.add_instr
("obj = alloc(sizeof(val_t) * {itab.length});")
833 v
.add_instr
("obj->vft = (classtable_elt_t*)VFT_{name};")
834 v
.add_assignment
(self_var_cname
, "OBJ2VAL(obj)")
836 for g
in global_properties
do
838 var t
= p
.signature
.return_type
839 if p
isa MMAttribute and t
!= null then
840 # FIXME: Not compatible with sep compilation
841 assert p
isa MMSrcAttribute
843 assert np
isa AAttrPropdef
846 var e
= ne
.compile_expr
(v
)
847 v
.add_instr
("{p.global.attr_access}(obj) = {e};")
849 var pi
= t
.local_class
.primitive_info
850 if pi
!= null and pi
.tagged
then
851 var default
= t
.default_cvalue
852 v
.add_instr
("{p.global.attr_access}(obj) = {default};")
857 v
.add_instr
("return OBJ2VAL(obj);")
858 v
.cfc
.generate_var_decls
859 ctx_old
.append
(v
.ctx
)
864 var init_table_size
= cshe
.greaters
.length
+ 1
865 var init_table_decl
= "int init_table[{init_table_size}] = \{0{", 0" * (init_table_size-1)}};"
867 for g
in global_properties
do
869 # FIXME skip invisible constructors
870 if not p
.global
.is_init_for
(self) then continue
871 var params
= new Array[String]
873 for i
in [0..p
.signature
.arity
[ do
874 params
.add
("val_t p{i}")
877 args
.add
("init_table")
878 var s
= "val_t NEW_{self}_{p.global.intro.cname}({params.join(", ")}) \{"
881 v
.add_instr
(init_table_decl
)
882 v
.add_instr
("val_t self = NEW_{name}();")
883 v
.add_instr
("{p.cname}({args.join(", ")});")
884 v
.add_instr
("return self;")
888 else if not pi
.tagged
then
890 var tbox
= "struct TBOX_{name}"
891 v
.add_instr
("val_t BOX_{name}({t} val) \{")
893 v
.add_instr
("{tbox} *box = ({tbox}*)alloc(sizeof({tbox}));")
894 v
.add_instr
("box->vft = VFT_{name};")
895 v
.add_instr
("box->val = val;")
896 v
.add_instr
("return OBJ2VAL(box);")