Skip to content
← Back

src/ir/program/program_plan.ghul

1
namespace IR.Program is
2
use Collections.LIST
3
use Collections.MAP
4
use Collections.SET
5
6
use Source.LOCATION
7
8
use Semantic.Symbols.Classy
9
use Semantic.Symbols.Function
10
11
/// What finding a program's reach needs from the target that lowers it.
12
trait DiscoveryTarget open is
13
/// Follows `instance`'s body far enough to find what it reaches: the
14
/// functions it calls, the classes it creates or tests for, and the
15
/// methods it dispatches on, each recorded on the plan's worklist,
16
/// class set and dispatched methods. Nothing it produces is kept.
17
reach(instance: FUNCTION_INSTANCE)
18
19
/// Whether a value of `type` can exist: a box only where something
20
/// boxes a value in it.
21
is_instantiated(type: CLASS_INSTANCE) -> bool
22
23
/// Called once for each class found to be instantiated, before its
24
/// dispatched methods are reached.
25
note_instantiated(type: CLASS_INSTANCE)
26
27
/// Reports a construct the target cannot compile, declared at
28
/// `location`.
29
report(location: LOCATION, construct: string)
30
si
31
32
/// What a whole program reaches: the function instances to compile, the
33
/// classes they use, and the methods they dispatch on, found to a fixed
34
/// point from the entry point or, for a library, from every function
35
/// that is not generic.
36
///
37
/// Following a body finds the functions it calls and the classes it
38
/// uses. A class found adds the types its fields hold, since the fields
39
/// are laid out wherever the class is, and every instantiated class adds
40
/// its implementations of the methods something dispatches on, since
41
/// dispatch can reach them. An array type adds every method, since the
42
/// trait table reaches them at the element type.
43
class PROGRAM_PLAN is
44
_classes: CLASS_SET
45
_functions: FUNCTION_WORKLIST
46
_dispatched: DISPATCHED_METHODS
47
_display: DISPLAY_PLAN?
48
_methods: MAP[Classy, LIST[Function]]
49
50
/// A plan over the bodies `bodies` the program compiles.
51
///
52
/// - classes: the classes found, which `reach` adds to
53
/// - functions: the worklist of instances to compile, which `reach`
54
/// adds to
55
/// - dispatched: the methods calls dispatch on, which `reach` adds to
56
/// - display: which types get a displayer, and what each calls, or null
57
/// where the target writes no displayers
58
/// - bodies: every function the program has a body for
59
init(
60
classes: CLASS_SET,
61
functions: FUNCTION_WORKLIST,
62
dispatched: DISPATCHED_METHODS,
63
display: DISPLAY_PLAN?,
64
bodies: Collections.Iterable[Function]
65
) is
66
_classes = classes
67
_functions = functions
68
_dispatched = dispatched
69
_display = display
70
71
_methods = MAP[Classy, LIST[Function]]()
72
73
for function in bodies do
74
if let owner = FUNCTION_BODIES.class_of_body(function) then
75
if !_methods.contains_key(owner) then
76
_methods[owner] = LIST[Function]()
77
fi
78
79
_methods[owner].add(function)
80
fi
81
od
82
si
83
84
/// The classes the program uses.
85
classes: CLASS_SET => _classes
86
87
/// The function instances the program compiles.
88
functions: FUNCTION_WORKLIST => _functions
89
90
/// The methods calls dispatch on.
91
dispatched: DISPATCHED_METHODS => _dispatched
92
93
/// Finds everything the program reaches from what is already on the
94
/// worklist, through `target`, until nothing new is found. A generic
95
/// class instantiated more often, or at deeper type arguments, than
96
/// `INSTANTIATION_LIMITS` allows is reported once, and the types of
97
/// its fields are left out.
98
discover(target: DiscoveryTarget) is
99
let too_deep = SET[Classy]()
100
let instantiations = MAP[Classy, int]()
101
let instantiated = SET[CLASS_INSTANCE]()
102
103
let is_done mut = false
104
105
while !is_done do
106
is_done = true
107
108
while let instance = _functions.next() do
109
is_done = false
110
111
target.reach(instance)
112
od
113
114
for type in _classes.take_new_classes() do
115
is_done = false
116
117
let found mut = 0
118
119
instantiations.try_get_value(type.definition, found ref)
120
instantiations[type.definition] = found + 1
121
122
if type.definition.is_generic /\ (found >= INSTANTIATION_LIMITS.MAXIMUM_INSTANTIATIONS \/ TYPE_MAPS.depth(type.arguments) > INSTANTIATION_LIMITS.MAXIMUM_TYPE_ARGUMENT_DEPTH) then
123
// A class whose methods or fields instantiate it at
124
// deeper and deeper type arguments would be compiled
125
// without end, so its fields add nothing further.
126
if too_deep.add(type.definition) then
127
if found >= INSTANTIATION_LIMITS.MAXIMUM_INSTANTIATIONS then
128
target.report(type.definition.location, "a generic class instantiated at more than {INSTANTIATION_LIMITS.MAXIMUM_INSTANTIATIONS} type arguments")
129
else
130
target.report(type.definition.location, "a generic class that instantiates itself at ever deeper type arguments")
131
fi
132
fi
133
134
_classes.leave_field_types(type)
135
else
136
_classes.add_field_types(type)
137
fi
138
od
139
140
let count = _functions.count
141
let instantiated_count = instantiated.count
142
143
for type in _classes.classes_and_arrays do
144
if !target.is_instantiated(type) then
145
continue
146
fi
147
148
if instantiated.add(type) then
149
target.note_instantiated(type)
150
fi
151
152
let class_methods: LIST[Function] mut
153
154
if _methods.try_get_value(type.definition, class_methods ref) then
155
for method in class_methods do
156
if (method.generic_arguments.count == 0 /\ _dispatched.is_dispatched_to(method)) \/ _classes.is_array(type) then
157
_functions.add(FUNCTION_INSTANCE(method, type.type_map))
158
fi
159
od
160
fi
161
od
162
163
// A trait's default method is reached through the table from
164
// any implementor that does not override it.
165
for (definition, class_methods) in _methods do
166
if definition.is_trait /\ !definition.is_generic then
167
for method in class_methods do
168
if _dispatched.is_dispatched_to(method) then
169
_functions.add(method)
170
fi
171
od
172
fi
173
od
174
175
if let display = _display, helpers = display.helpers then
176
for type in _classes.classes_and_arrays do
177
for function in display.calls(type, helpers) do
178
_functions.add(function)
179
od
180
od
181
fi
182
183
if _functions.count != count \/ instantiated.count != instantiated_count then
184
is_done = false
185
fi
186
od
187
si
188
si
189
si