Appearance
| 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 |