Skip to content
← Back

src/syntax/process/narrowing/kill_ledger.ghul

1
namespace Syntax.Process is
2
use Symbol = Semantic.Symbols.Symbol
3
use LOCATION = Source.LOCATION
4
5
// One heap fact crossed by one call during a body walk, and what
6
// the walk did about it: killed it, because the relations solved by
7
// the previous effects round could not show the callee left it
8
// alone, or kept it - because they could, or because no relations
9
// had been solved yet. `function` is the definition whose walk
10
// made the record, so that walk alone can be redone.
11
class KILL(
12
file_name: string,
13
crossing: CROSSING,
14
target: Symbol?,
15
path: ACCESS_PATH?,
16
is_presence: bool,
17
killed: bool
18
) is
19
function: Trees.Definitions.FUNCTION? public
20
21
// Whether this records a fact that was never formed, because a
22
// getter the value is read through cannot back one, rather than
23
// a call that ended a fact that was. The crossing then names the
24
// getter's own declaration, which is no call site, and a use
25
// short of the fact is short of it from the start.
26
declined: bool public
27
28
// What the dropped fact said the value was, for a type fact of a
29
// formed narrowing. Null for a presence fact, and for a record
30
// made where no fact was formed. A use that fails for want of
31
// this fact is reported with the call attached, and what the
32
// fact said is how that is judged.
33
narrowed_type: Semantic.Types.Type? public
34
si
35
36
// The combined type + effect solve, in-walk form. When a
37
// solved set of effect relations exists, the call transfer asks of
38
// every heap fact live across a call whether the callee provably
39
// left it alone, and drops the fact at the call when it cannot -
40
// the fact's validity region ends there, the widened view flows
41
// on, and a use only the fact satisfied is an ordinary type error.
42
//
43
// Every crossing a fact takes is recorded here with the walk's
44
// decision. After each solve the decisions are re-asked against the
45
// new relations: a fact kept across a call that cannot now be
46
// discharged - every crossing of a walk made before any solve, and
47
// some after an edit - or dropped at one that now can, makes its
48
// body inexact, and the driver re-walks inexact bodies until a
49
// solve finds none. The ledger keys nothing on rendered text: it
50
// holds the crossing, fact and definition objects the walk
51
// recorded.
52
class KILL_LEDGER is
53
_kills: Collections.LIST[KILL] static
54
55
// Each read of a function's store-free proof made by a walk
56
// before the solve that settles it: the pure shape of a named
57
// function's type is read that way, and a literal returning the
58
// function infers its own type from the answer.
59
_purity_reads: Collections.LIST[PURITY_READ] static
60
61
init() static is
62
_kills = Collections.LIST[KILL]()
63
_purity_reads = Collections.LIST[PURITY_READ]()
64
_restart_bodies = Collections.SET[Trees.Definitions.FUNCTION]()
65
si
66
67
// The file whose bodies are being walked, for records made
68
// where no location is at hand.
69
current_file: string? public static
70
71
// The definition whose body is being walked. Set for the
72
// duration of each definition's walk by compile-expressions;
73
// a record made outside one is keyed on its file alone.
74
current_function: Trees.Definitions.FUNCTION? public static
75
76
// Set while a walk must keep every fact whatever the relations
77
// say: the start of a descent from the top.
78
kills_suspended: bool public static
79
80
// Set while the driver re-walks inexact bodies against the
81
// relations, as opposed to an edit path walking a body against
82
// the last complete solve.
83
in_descent: bool public static
84
85
// Whether some body was walked with kills outside a descent since
86
// the last descent from the top - so the next COMPILE must restart
87
// from the top to be sure of reaching the same answer batch would.
88
needs_restart: bool public static
89
90
// The definitions whose walk killed outside a descent since the
91
// last descent from the top: the only bodies that started the
92
// descent below the top, so the only ones a restart re-walks.
93
_restart_bodies: Collections.SET[Trees.Definitions.FUNCTION] static
94
95
// Whether the walk can consult relations at all.
96
can_kill_in_walk: bool static => EFFECTS.is_complete /\ !kills_suspended
97
98
record(kill: KILL) static is
99
kill.function = current_function
100
101
if kill.killed /\ !in_descent then
102
needs_restart = true
103
104
if let function = current_function then
105
_restart_bodies.add(function)
106
fi
107
fi
108
109
_kills.add(kill)
110
si
111
112
// A definition's walk read whether `function` is proven store-free,
113
// and was told `answer`. Reads made anywhere else record nothing:
114
// no inferred type depends on them.
115
record_purity_read(function: Semantic.Symbols.Function, answer: bool) static is
116
if let walked = current_function then
117
_purity_reads.add(PURITY_READ(walked.location.file_name, walked, function, answer))
118
fi
119
si
120
121
// Hand over the bodies a restart has to re-walk and start
122
// afresh: those whose walk killed outside a descent.
123
take_restart_bodies() -> Collections.SET[Trees.Definitions.FUNCTION] static is
124
let result = _restart_bodies
125
126
_restart_bodies = Collections.SET[Trees.Definitions.FUNCTION]()
127
needs_restart = false
128
129
return result
130
si
131
132
// Every definition whose last walk killed something.
133
bodies_with_kills() -> Collections.SET[Trees.Definitions.FUNCTION] static is
134
let result = Collections.SET[Trees.Definitions.FUNCTION]()
135
136
for kill in _kills do
137
if kill.killed then
138
if let function = kill.function then
139
result.add(function)
140
fi
141
fi
142
od
143
144
return result
145
si
146
147
// The file's walk is being redone from its source: whatever it
148
// recorded is superseded by the walk to come.
149
clear_for(file_name: string) static is
150
_drop_where((file, _) => file =~ file_name)
151
si
152
153
// One definition's body walk is being redone.
154
clear_for(function: Trees.Definitions.FUNCTION) static is
155
_drop_where((_, walked: Trees.Definitions.FUNCTION?) => walked == function)
156
si
157
158
_drop_where(condition: (string, Trees.Definitions.FUNCTION?) -> bool) static is
159
let kept = Collections.LIST[KILL]()
160
161
for kill in _kills do
162
if !condition(kill.file_name, kill.function) then
163
kept.add(kill)
164
fi
165
od
166
167
_kills = kept
168
169
let kept_reads = Collections.LIST[PURITY_READ]()
170
171
for read in _purity_reads do
172
if !condition(read.file_name, read.walked) then
173
kept_reads.add(read)
174
fi
175
od
176
177
_purity_reads = kept_reads
178
si
179
180
// One line per record, for comparing what walks recorded.
181
dump(writer: IO.TextWriter) static is
182
for kill in _kills do
183
let what = if let target = kill.target then target.name elif let path = kill.path then path.to_string() else "?" fi
184
185
writer.write_line("{kill.file_name} {if let function = kill.function then function.location.start_line else 0 fi} {kill.crossing.location} {if kill.is_presence then "presence" else "type" fi} {what} {if kill.killed then "killed" else "kept" fi}")
186
od
187
si
188
189
clear_all() static is
190
_kills.clear()
191
_purity_reads.clear()
192
si
193
194
// The call that dropped a fact about this target nearest above
195
// `at`, if one did. Asked at a use that failed for want of the
196
// fact, so that the error can name the call that ended it;
197
// `is_presence` picks the domain. A value narrowed more than
198
// once in a body has a record per drop, each of a fact
199
// re-established since the last, so the one the use is short of
200
// is the last drop written before it - an earlier one belongs
201
// to a narrowing this use never had.
202
last_dropped_before(target: Symbol?, path: ACCESS_PATH?, is_presence: bool, at: LOCATION) -> KILL? static is
203
let result: KILL? mut = null
204
205
for kill in _kills do
206
if
207
kill.killed /\
208
!kill.declined /\
209
kill.is_presence == is_presence /\
210
kill.function == current_function /\
211
_describes(kill, target, path) /\
212
_precedes(kill.crossing.location, at)
213
then
214
if !result? \/ kill.crossing.location.start > result.crossing.location.start then
215
result = kill
216
fi
217
fi
218
od
219
220
return result
221
si
222
223
// Whether a call written here could have ended a fact a use at
224
// `use` needed: the same file, and not below it.
225
_precedes(call: LOCATION, at: LOCATION) -> bool static =>
226
call.file_name =~ at.file_name /\ call.start <= at.start
227
228
_describes(kill: KILL, target: Symbol?, path: ACCESS_PATH?) -> bool static is
229
if let killed_target = kill.target then
230
return target? /\ killed_target == target
231
fi
232
233
if let killed_path = kill.path then
234
return path? /\ killed_path.equals(path)
235
fi
236
237
return false
238
si
239
240
// After a solve: every body whose walk decided some crossing
241
// differently from the way the new relations would, and the
242
// files of the records made outside any definition's walk.
243
// Both empty means the last walk of every body agrees with the
244
// relations, which is the fixpoint.
245
take_inexact() -> INEXACT static is
246
let result = INEXACT()
247
248
let stopwatch = System.Diagnostics.Stopwatch.start_new()
249
let asked mut = 0
250
let killed mut = 0
251
252
for kill in _kills do
253
if kill.killed then
254
killed = killed + 1
255
fi
256
257
if let function = kill.function then
258
if result.bodies.contains(function) then
259
continue
260
fi
261
elif result.files.contains(kill.file_name) then
262
continue
263
fi
264
265
asked = asked + 1
266
267
let discharged = RELIANCES.crossing_discharged(kill.crossing, kill.target, kill.path, kill.is_presence)
268
269
if discharged == kill.killed then
270
if let function = kill.function then
271
result.bodies.add(function)
272
else
273
result.files.add(kill.file_name)
274
fi
275
fi
276
od
277
278
// A body that read a proof the solve has since settled the
279
// other way inferred its types from the wrong answer.
280
for read in _purity_reads do
281
if read.function.is_proven_store_free != read.answer then
282
result.bodies.add(read.walked)
283
fi
284
od
285
286
if Driver.COMPILER_ENVIRONMENT.effects_timing then
287
IO.Std.error.write_line("ledger: {_kills.count} records ({killed} killed), {asked} re-asked in {stopwatch.elapsed_milliseconds} ms, {result.bodies.count} body(ies) and {result.files.count} file(s) inexact")
288
fi
289
290
return result
291
si
292
si
293
294
// One read of a function's store-free proof by the walk of the
295
// definition `walked`, in the file `file_name`.
296
class PURITY_READ(
297
file_name: string,
298
walked: Trees.Definitions.FUNCTION,
299
function: Semantic.Symbols.Function,
300
answer: bool
301
)
302
303
// What a solve found inexact: the definitions whose body walks
304
// disagree with the relations, and the files of records that were
305
// made outside a definition's walk.
306
class INEXACT is
307
bodies: Collections.SET[Trees.Definitions.FUNCTION]
308
files: Collections.SET[string]
309
310
init() is
311
bodies = Collections.SET[Trees.Definitions.FUNCTION]()
312
files = Collections.SET[string]()
313
si
314
315
is_empty: bool => bodies.count == 0 /\ files.count == 0
316
si
317
si