Skip to content
← Back

src/semantic/obligations.ghul

1
namespace Semantic is
2
use Source.LOCATION
3
4
use Collections.LIST
5
6
// A rule that could not fire on this walk because one of its inputs
7
// was still an inference placeholder: which rule, the placeholder it
8
// waits on, and where. Recorded instead of committing to a result
9
// computed from the settled inputs alone, or reporting the placeholder
10
// as an error the whole-body loop may yet erase.
11
class OBLIGATION(rule: string, awaiting: Types.Type, location: LOCATION?)
12
13
// The obligations recorded during the current walk of the body being
14
// compiled. The whole-body loop in COMPILE_LAMBDAS re-walks a body
15
// while its walks make progress, and every re-walk records the
16
// obligations still standing afresh, so the queue is cleared at each
17
// walk and read once the loop has stopped: an obligation still
18
// standing then, on a placeholder nothing settled, is reported at the
19
// placeholder's origin, naming the variable whose type the body could
20
// not infer.
21
//
22
// Recording an obligation marks the walk as having consumed an
23
// unresolved type, which is what keeps the loop walking; the sites
24
// that record one need not also signal that themselves.
25
class OBLIGATIONS is
26
_bodies: LIST[LIST[OBLIGATION]] static
27
28
init() static is
29
_bodies = LIST[LIST[OBLIGATION]]()
30
_previous = LIST[LIST[Symbols.Variable]]()
31
_defaulted = LIST[LIST[Symbols.Variable]]()
32
_learned = LIST[int]()
33
si
34
35
begin_body() static is
36
_bodies.add(LIST[OBLIGATION]())
37
_previous.add(LIST[Symbols.Variable]())
38
_defaulted.add(LIST[Symbols.Variable]())
39
_learned.add(0)
40
si
41
42
// Per body, the origins its previous walk left waiting, for
43
// `is_stuck` to compare against; a stack beside `_bodies`, since a
44
// body compiled during another's walk has walks of its own.
45
_previous: LIST[LIST[Symbols.Variable]] static
46
47
// Per body, how many bounds and constraints its current walk has
48
// recorded that were not recorded before. A walk that leaves the
49
// same obligations standing as the walk before it has still moved
50
// when this is not zero: what it learned is what the next walk
51
// settles the waiting origin from.
52
_learned: LIST[int] static
53
54
// Counts a bound or constraint that carried information, for every
55
// body currently being walked - a body compiled during another's
56
// walk is something that walk learned too.
57
note_learned() static is
58
for i in 0.._learned.count do
59
_learned[i] = _learned[i] + 1
60
od
61
si
62
63
// Per body, the origins the fixing step has taken a default for.
64
// Unlike the queue itself this survives `begin_walk`: the walk
65
// that follows the default is the walk that has to see it.
66
_defaulted: LIST[LIST[Symbols.Variable]] static
67
68
// The rule an untyped local initialized with an empty array
69
// literal waits under. The one rule with a default, so the one
70
// `take_defaults` answers.
71
EMPTY_LITERAL: string static => "empty_literal"
72
73
// The return of a function literal whose body produced only null
74
// with no slot to say what it is optional of. Reported by the
75
// fixing step if nothing settles it.
76
LITERAL_RETURN: string static => "literal_return"
77
78
// The return of a function literal whose tail failed to compile.
79
// The tail's own diagnostic is the report, so the fixing step
80
// adds none.
81
LITERAL_RETURN_AFTER_ERROR: string static => "literal_return_after_error"
82
83
// The return of a recursive literal, read by its own self-call
84
// before the body settled it. What the literal went wrong on is
85
// its own report, so the fixing step adds none.
86
RECURSIVE_RETURN: string static => "recursive_return"
87
88
begin_walk() static is
89
if _bodies.count == 0 then
90
return
91
fi
92
93
let previous = LIST[Symbols.Variable]()
94
95
for obligation in standing do
96
if let placeholder: Types.INFERRED_VARIABLE_TYPE = obligation.awaiting then
97
if !previous.contains(placeholder.origin) then
98
previous.add(placeholder.origin)
99
fi
100
fi
101
od
102
103
_previous[_previous.count - 1] = previous
104
_bodies[_bodies.count - 1].clear()
105
_learned[_learned.count - 1] = 0
106
si
107
108
// Whether this walk learned nothing and left no origin waiting that
109
// the previous walk did not, so a further walk can only repeat this
110
// one. Fewer origins waiting is not progress in itself: the ones
111
// that stopped waiting were settled by what the previous walk
112
// learned, and this walk added nothing for the next to use.
113
is_stuck: bool static is
114
if _learned.count > 0 /\ _learned[_learned.count - 1] > 0 then
115
return false
116
fi
117
118
let current = LIST[Symbols.Variable]()
119
120
for obligation in standing do
121
if let placeholder: Types.INFERRED_VARIABLE_TYPE = obligation.awaiting then
122
if !current.contains(placeholder.origin) then
123
current.add(placeholder.origin)
124
fi
125
fi
126
od
127
128
if current.count == 0 then
129
return false
130
fi
131
132
let previous = if _previous.count > 0 then _previous[_previous.count - 1] else LIST[Symbols.Variable]() fi
133
134
for origin in current do
135
if !previous.contains(origin) then
136
return false
137
fi
138
od
139
140
return true
141
si
142
143
// Whether this walk recorded no bound or constraint that was not
144
// recorded before. With nothing standing either, a further walk
145
// starts from exactly what this one had, and can only repeat it.
146
learned_nothing: bool static =>
147
_learned.count > 0 /\ _learned[_learned.count - 1] == 0
148
149
end_body() static is
150
if _bodies.count > 0 then
151
_bodies.remove_at(_bodies.count - 1)
152
_previous.remove_at(_previous.count - 1)
153
_defaulted.remove_at(_defaulted.count - 1)
154
_learned.remove_at(_learned.count - 1)
155
fi
156
si
157
158
// The obligations the last walk of the current body recorded.
159
standing: LIST[OBLIGATION] static =>
160
if _bodies.count > 0 then _bodies[_bodies.count - 1] else LIST[OBLIGATION]() fi
161
162
defer(rule: string, awaiting: Types.Type, location: LOCATION?) static is
163
INFERENCE_TRACE.obligation(rule, awaiting, location)
164
165
if _bodies.count > 0 then
166
_bodies[_bodies.count - 1].add(OBLIGATION(rule, awaiting, location))
167
fi
168
169
IoC.CONTAINER.instance.logger.mark_consumed_any()
170
si
171
172
// Takes the language default for every standing obligation that
173
// has one, and says whether it took any. Called once the body's
174
// loop has stopped: a default is an answer to the walks having
175
// run out rather than information a walk found, so taking one
176
// earlier pre-empts the walk that would have settled the origin
177
// properly. The caller answers true with one more walk, which is
178
// where the default reaches the literal and everything typed
179
// from it.
180
take_defaults() -> bool static is
181
let taken mut = false
182
183
for obligation in standing do
184
if obligation.rule !~ EMPTY_LITERAL then
185
continue
186
fi
187
188
if let placeholder: Types.INFERRED_VARIABLE_TYPE = obligation.awaiting then
189
let origin = placeholder.origin
190
191
if let type = origin.type /\ type.is_settled then
192
continue
193
fi
194
195
let resolved = origin.try_get_inferred_type()
196
197
if resolved? /\ resolved.is_settled then
198
continue
199
fi
200
201
if has_default_for(origin) then
202
continue
203
fi
204
205
_defaulted[_defaulted.count - 1].add(origin)
206
207
taken = true
208
fi
209
od
210
211
return taken
212
si
213
214
// Whether the fixing step has taken a default for this origin, so
215
// the site that waited on it takes the default rather than waiting
216
// again.
217
has_default_for(origin: Symbols.Variable) -> bool static =>
218
_defaulted.count > 0 /\ _defaulted[_defaulted.count - 1].contains(origin)
219
220
// Called once the loop has stopped without converging. Each
221
// variable whose placeholder an obligation still waits on, and
222
// whose type nothing in the body settled, is reported once, at
223
// its declaration, pointing at the first site that waited on it.
224
// A constructor's type-argument phantom is reported by
225
// TYPE_ARG_PLACEHOLDER_REGISTRY instead, which knows the
226
// construction it belongs to.
227
fix(logger: Logging.Logger) static is
228
let reported = LIST[Symbols.Variable]()
229
230
for obligation in LIST[OBLIGATION](standing) do
231
if let placeholder: Types.INFERRED_VARIABLE_TYPE = obligation.awaiting then
232
let origin = placeholder.origin
233
234
if obligation.rule =~ LITERAL_RETURN_AFTER_ERROR \/ obligation.rule =~ RECURSIVE_RETURN then
235
continue
236
fi
237
238
if let result_origin: Symbols.INFERRED_RESULT_ORIGIN = origin then
239
if reported.contains(origin) \/ has_default_for(origin) then
240
continue
241
fi
242
243
if let resolved = origin.try_get_inferred_type() /\ resolved.is_settled then
244
continue
245
fi
246
247
if let type = origin.type /\ type.is_settled then
248
continue
249
fi
250
251
reported.add(origin)
252
253
logger.error(origin.location, "cannot infer {result_origin.description}")
254
255
continue
256
fi
257
258
if isa Symbols.INFERRED_TYPE_ARG_ORIGIN(origin) \/ origin.name.starts_with("$") then
259
continue
260
fi
261
262
if reported.contains(origin) \/ has_default_for(origin) then
263
continue
264
fi
265
266
let resolved = origin.try_get_inferred_type()
267
268
if resolved? /\ resolved.is_settled then
269
continue
270
fi
271
272
if let type = origin.type /\ type.is_settled then
273
continue
274
fi
275
276
reported.add(origin)
277
278
if let location = _first_site_for(origin) then
279
logger.error(origin.location, "cannot infer the type of {origin.name}", location, "{origin.name} is needed here")
280
else
281
logger.error(origin.location, "cannot infer the type of {origin.name}")
282
fi
283
fi
284
od
285
si
286
287
// Where the first standing obligation on `origin` with a location
288
// was recorded.
289
_first_site_for(origin: Symbols.Variable) -> LOCATION? static is
290
for obligation in standing do
291
if let placeholder: Types.INFERRED_VARIABLE_TYPE = obligation.awaiting, location = obligation.location then
292
if placeholder.origin == origin then
293
return location
294
fi
295
fi
296
od
297
298
return null
299
si
300
si
301
si