Appearance
| 1 | namespace Syntax.Process is | |
| 2 | use System.Exception; | |
| 3 | ||
| 4 | use Logging; | |
| 5 | use Trees; | |
| 6 | ||
| 7 | use Semantic.Types.Type; | |
| 8 | ||
| 9 | use Function = Semantic.Symbols.Function; | |
| 10 | use Symbol = Semantic.Symbols.Symbol; | |
| 11 | ||
| 12 | // Facts the body walk gathers for one function, consumed by the | |
| 13 | // finish-time fixpoint. | |
| 14 | class STORE_FREE_FACTS is | |
| 15 | // The body performs a store or an effect the walk cannot | |
| 16 | // bound: an assignment to anything but a local, a call with | |
| 17 | // an unresolvable callee set, disposal, iteration, an | |
| 18 | // untyped interpolation fragment, an await or yield, ... | |
| 19 | is_disqualified: bool public; | |
| 20 | ||
| 21 | // The same, except a store to the receiver's own instance | |
| 22 | // field does not set it — that write hits only a fresh object | |
| 23 | // when the function is a constructor reached through a `NEW`. | |
| 24 | // The fixpoint reads it to classify a constructor | |
| 25 | // construction-store-free even when its own-field writes leave | |
| 26 | // it not strictly store-free. | |
| 27 | is_construction_disqualified: bool public; | |
| 28 | ||
| 29 | // Statically-bounded callees. The function is store-free | |
| 30 | // only if every one of them proves store-free too. | |
| 31 | callees: Collections.MutableList[Function]; | |
| 32 | ||
| 33 | init() is | |
| 34 | callees = Collections.LIST[Function](); | |
| 35 | si | |
| 36 | ||
| 37 | add_callee(callee: Function) is | |
| 38 | callees.add(callee); | |
| 39 | si | |
| 40 | si | |
| 41 | ||
| 42 | // Runs after resolve-overrides, before compile-expressions. | |
| 43 | // Computes for every function declared in the compilation whether | |
| 44 | // it provably performs no store to any pre-existing heap location | |
| 45 | // — no field, property, global, indexer or array-element | |
| 46 | // assignment — directly or through anything a call from its body | |
| 47 | // could dispatch to. Reads are always harmless; only writes and | |
| 48 | // unboundable calls disqualify. A call to a store-free function | |
| 49 | // can never invalidate a field narrowing, which is what | |
| 50 | // IR.Values.Call.*.is_state_changing_call consumes the bit for. | |
| 51 | // | |
| 52 | // The classification runs before types are inferred, so it only | |
| 53 | // trusts declared types: fields, properties, parameters, | |
| 54 | // annotated locals, and locals whose initializer type is trivial. | |
| 55 | // Any call whose callee set it cannot bound — a delegate | |
| 56 | // invocation, a member of an untyped receiver, an imported | |
| 57 | // function — disqualifies the caller. Dispatch is bounded using | |
| 58 | // resolve-overrides' overrider links; a method reachable through | |
| 59 | // an open class or a trait is never store-free, because an | |
| 60 | // override in another assembly could store. | |
| 61 | // | |
| 62 | // Every node kind not explicitly classified below is unsafe via | |
| 63 | // visit_default. When a new node kind is added, it must be | |
| 64 | // explicitly audited here before functions containing it can | |
| 65 | // classify as store-free. | |
| 66 | // | |
| 67 | // This pass never reports diagnostics. It runs on incomplete and | |
| 68 | // incorrect code in analysis mode, where the other passes own | |
| 69 | // finding and reporting every problem; anything suspect here just | |
| 70 | // classifies conservatively. Incremental analysis-mode edit paths | |
| 71 | // do not re-run it, so their per-edit results can hold stale bits; | |
| 72 | // COMPILER.refresh_store_free re-runs it at the debounced compile, | |
| 73 | // and on any flip the compile trues up the files referencing a | |
| 74 | // flipped function - or rebuilds outright when the flip set can't | |
| 75 | // be bounded - so callers' narrowings never stay wrong. | |
| 76 | class INFER_STORE_FREE: DefaultVisitor is | |
| 77 | _facts: Collections.MutableMap[Function, STORE_FREE_FACTS]; | |
| 78 | _current: STORE_FREE_FACTS?; | |
| 79 | _current_function: Function?; | |
| 80 | ||
| 81 | // Whether the most recent finish_run moved any function's | |
| 82 | // store-free bit. Only meaningful between finish_run and the | |
| 83 | // next start_run. | |
| 84 | _last_run_changed: bool; | |
| 85 | last_run_changed: bool => _last_run_changed; | |
| 86 | ||
| 87 | // The functions the most recent finish_run's fixpoint moved, or | |
| 88 | // null when a broken run made the flip set unboundable. Same | |
| 89 | // lifetime as last_run_changed. | |
| 90 | _last_flipped: Collections.List[Function]?; | |
| 91 | last_flipped: Collections.List[Function]? => _last_flipped; | |
| 92 | ||
| 93 | // Mirror of _facts scoped to the file currently being walked, | |
| 94 | // handed back to the caller as the file's reusable fact bucket. | |
| 95 | // Null outside begin_file_bucket / end_file_bucket. | |
| 96 | _bucket: Collections.MutableMap[Function, STORE_FREE_FACTS]?; | |
| 97 | ||
| 98 | // Files whose bodies were actually re-walked during the most | |
| 99 | // recent finished run, versus absorbed from a retained bucket. | |
| 100 | // Snapshotted by finish_run; the accumulator resets with each | |
| 101 | // start_run. Refresh telemetry. | |
| 102 | _walked_files: int; | |
| 103 | _last_run_walked_files: int; | |
| 104 | last_run_walked_files: int => _last_run_walked_files; | |
| 105 | ||
| 106 | // Start mirroring walked facts into a fresh per-file bucket. | |
| 107 | begin_file_bucket() is | |
| 108 | _bucket = Collections.MAP[Function, STORE_FREE_FACTS](); | |
| 109 | _walked_files = _walked_files + 1; | |
| 110 | si | |
| 111 | ||
| 112 | end_file_bucket() -> Collections.MutableMap[Function, STORE_FREE_FACTS] is | |
| 113 | let result = _bucket!; | |
| 114 | _bucket = null; | |
| 115 | return result; | |
| 116 | si | |
| 117 | ||
| 118 | // Feed a retained file bucket into this run's facts without | |
| 119 | // re-walking the file. Callee edges in retained facts can hold | |
| 120 | // symbol objects an incremental edit has since replaced; the | |
| 121 | // fixpoint treats such an edge as an unknown target and | |
| 122 | // classifies the caller conservatively, and the file's bucket is | |
| 123 | // dropped whenever its expressions recompile, so the pessimism | |
| 124 | // heals at the next walk. | |
| 125 | absorb(bucket: Collections.MutableMap[Function, STORE_FREE_FACTS]) is | |
| 126 | for pair in bucket do | |
| 127 | _facts[pair.key] = pair.value; | |
| 128 | od | |
| 129 | si | |
| 130 | ||
| 131 | // Trivially-derivable static types, including the per-function | |
| 132 | // record of locals whose initializer type was derivable. | |
| 133 | _typer: TRIVIAL_EXPRESSION_TYPER; | |
| 134 | ||
| 135 | _innate_symbol_lookup: Semantic.Lookups.InnateSymbolLookup; | |
| 136 | ||
| 137 | init( | |
| 138 | logger: Logger, | |
| 139 | symbol_table: Semantic.SYMBOL_TABLE, | |
| 140 | namespaces: Semantic.NAMESPACES, | |
| 141 | innate_symbol_lookup: Semantic.Lookups.InnateSymbolLookup | |
| 142 | ) | |
| 143 | is | |
| 144 | super.init(logger, symbol_table, namespaces); | |
| 145 | ||
| 146 | _typer = TRIVIAL_EXPRESSION_TYPER(symbol_table, innate_symbol_lookup); | |
| 147 | _innate_symbol_lookup = innate_symbol_lookup; | |
| 148 | ||
| 149 | start_run(); | |
| 150 | si | |
| 151 | ||
| 152 | start_run() is | |
| 153 | _facts = Collections.MAP[Function, STORE_FREE_FACTS](); | |
| 154 | _typer.reset(); | |
| 155 | _current = null; | |
| 156 | _current_function = null; | |
| 157 | _bucket = null; | |
| 158 | _walked_files = 0; | |
| 159 | si | |
| 160 | ||
| 161 | // The walk must survive incomplete and incorrect code — it | |
| 162 | // runs in analysis mode on whatever the user has half-typed. | |
| 163 | // It reports nothing, ever: broken code is found and | |
| 164 | // diagnosed by the other passes, and an analysis here that | |
| 165 | // cannot complete only means some functions conservatively | |
| 166 | // stay not-store-free. On an exception the symbol-table scope | |
| 167 | // stack is restored to its entry depth so a long-lived | |
| 168 | // analysis process is not poisoned for later passes, and | |
| 169 | // whatever function was mid-walk keeps its disqualification. | |
| 170 | apply(root: Trees.Node) is | |
| 171 | let mark = mark_scope_stack(); | |
| 172 | ||
| 173 | _last_walk_failed = false; | |
| 174 | ||
| 175 | try | |
| 176 | root.walk(self); | |
| 177 | catch ex: Exception | |
| 178 | _disqualify(); | |
| 179 | release_scope_stack(mark); | |
| 180 | ||
| 181 | _last_walk_failed = true; | |
| 182 | yrt | |
| 183 | ||
| 184 | _current = null; | |
| 185 | _current_function = null; | |
| 186 | si | |
| 187 | ||
| 188 | // Whether the most recent apply abandoned its walk on an | |
| 189 | // exception. A partial walk's facts must not be retained as a | |
| 190 | // file bucket: the functions it never reached would stay absent | |
| 191 | // from every later run's union instead of getting a fresh walk. | |
| 192 | _last_walk_failed: bool; | |
| 193 | last_walk_failed: bool => _last_walk_failed; | |
| 194 | ||
| 195 | // Facts in, bits out — the graph solving lives in | |
| 196 | // STORE_FREE_FIXPOINT. | |
| 197 | finish_run() is | |
| 198 | _last_run_walked_files = _walked_files; | |
| 199 | ||
| 200 | try | |
| 201 | let fixpoint = STORE_FREE_FIXPOINT(); | |
| 202 | ||
| 203 | _last_run_changed = fixpoint.mark(_facts); | |
| 204 | _last_flipped = fixpoint.flipped; | |
| 205 | ||
| 206 | _trust_value_optional_accessors(); | |
| 207 | catch ex: Exception | |
| 208 | // a broken fixpoint must not leave optimistic bits | |
| 209 | // from a partial write-back behind; treat the run as | |
| 210 | // having changed, with the flip set unboundable, so any | |
| 211 | // incremental shortcut escalates | |
| 212 | _last_run_changed = true; | |
| 213 | _last_flipped = null; | |
| 214 | ||
| 215 | for function in _facts.keys do | |
| 216 | function.set_store_free(false); | |
| 217 | od | |
| 218 | yrt | |
| 219 | ||
| 220 | start_run(); | |
| 221 | si | |
| 222 | ||
| 223 | // The value-type optional carriers' accessors get the bit | |
| 224 | // directly: `x?` / `x!` on an `int?`-style slot lower to | |
| 225 | // these at compile-expressions time without appearing as | |
| 226 | // call edges here, and both read a field of a sealed struct | |
| 227 | // — no overrider can exist, so unconditional trust is sound. | |
| 228 | // Without the bit every value-type presence test would count | |
| 229 | // as a possibly-storing call and kill the very facts it | |
| 230 | // establishes. | |
| 231 | _trust_value_optional_accessors() is | |
| 232 | let bool_type = _innate_symbol_lookup.get_bool_type(); | |
| 233 | ||
| 234 | _mark_read_accessors_store_free(_innate_symbol_lookup.get_optional_type(bool_type)); | |
| 235 | _mark_read_accessors_store_free(_innate_symbol_lookup.get_maybe_type(bool_type)); | |
| 236 | si | |
| 237 | ||
| 238 | _mark_read_accessors_store_free(type: Semantic.Types.Type?) is | |
| 239 | if !type? then | |
| 240 | return; | |
| 241 | fi | |
| 242 | ||
| 243 | for name in ["has_value", "value"] do | |
| 244 | let member = type.find_member(name); | |
| 245 | ||
| 246 | if member? /\ isa Semantic.Symbols.Property(member) then | |
| 247 | let read_function = (cast Semantic.Symbols.Property(member)).read_function; | |
| 248 | ||
| 249 | if read_function? then | |
| 250 | read_function.set_store_free(true); | |
| 251 | fi | |
| 252 | fi | |
| 253 | od | |
| 254 | si | |
| 255 | ||
| 256 | // ==== default: any node kind without an explicit override ==== | |
| 257 | ||
| 258 | visit_default(node: Trees.Node) is | |
| 259 | _disqualify(); | |
| 260 | si | |
| 261 | ||
| 262 | _disqualify() is | |
| 263 | if _current? then | |
| 264 | _current.is_disqualified = true; | |
| 265 | _current.is_construction_disqualified = true; | |
| 266 | fi | |
| 267 | si | |
| 268 | ||
| 269 | // A store the strict analysis rejects but a construction does | |
| 270 | // not: writing the receiver's own instance field touches only | |
| 271 | // the fresh object a `NEW` is building. | |
| 272 | _disqualify_strict_only() is | |
| 273 | if _current? then | |
| 274 | _current.is_disqualified = true; | |
| 275 | fi | |
| 276 | si | |
| 277 | ||
| 278 | _in_constructor: bool => | |
| 279 | _current_function? /\ _current_function.is_constructor; | |
| 280 | ||
| 281 | // A `self.field` target naming an instance field of the type | |
| 282 | // under construction. `self` is the only receiver that resolves | |
| 283 | // to the fresh object; a member on any other receiver stays a | |
| 284 | // heap store. | |
| 285 | _writes_own_instance_field_member(target: Trees.Expressions.Expression?) -> bool is | |
| 286 | if !target? \/ !isa Trees.Expressions.MEMBER(target) then | |
| 287 | return false; | |
| 288 | fi | |
| 289 | ||
| 290 | let member = cast Trees.Expressions.MEMBER(target); | |
| 291 | ||
| 292 | if !isa Trees.Expressions.SELF(member.left) then | |
| 293 | return false; | |
| 294 | fi | |
| 295 | ||
| 296 | let context = current_instance_context; | |
| 297 | ||
| 298 | if !context? then | |
| 299 | return false; | |
| 300 | fi | |
| 301 | ||
| 302 | let field_symbol = context.find_member(member.identifier.name); | |
| 303 | ||
| 304 | return field_symbol? /\ field_symbol.is_field /\ field_symbol.is_instance; | |
| 305 | si | |
| 306 | ||
| 307 | _add_callee(callee: Function?) is | |
| 308 | if !_current? then | |
| 309 | return; | |
| 310 | fi | |
| 311 | ||
| 312 | if !callee? then | |
| 313 | _disqualify(); | |
| 314 | return; | |
| 315 | fi | |
| 316 | ||
| 317 | let root = cast Function?(callee.root_specialized_from); | |
| 318 | ||
| 319 | if !root? then | |
| 320 | _disqualify(); | |
| 321 | return; | |
| 322 | fi | |
| 323 | ||
| 324 | _current.add_callee(root); | |
| 325 | si | |
| 326 | ||
| 327 | _add_callee_edges(symbol: Symbol?) is | |
| 328 | if !_current? then | |
| 329 | return; | |
| 330 | fi | |
| 331 | ||
| 332 | if !symbol? then | |
| 333 | _disqualify(); | |
| 334 | return; | |
| 335 | fi | |
| 336 | ||
| 337 | if isa Semantic.Symbols.FUNCTION_GROUP(symbol) then | |
| 338 | for function in (cast Semantic.Symbols.FUNCTION_GROUP(symbol)).functions do | |
| 339 | _add_callee(function); | |
| 340 | od | |
| 341 | elif isa Function(symbol) then | |
| 342 | _add_callee(cast Function(symbol)); | |
| 343 | elif _is_store_free_construction(symbol) then | |
| 344 | // constructing a fresh exception writes only that new | |
| 345 | // object, never a pre-existing heap slot, so it cannot | |
| 346 | // invalidate a narrowing | |
| 347 | else | |
| 348 | // a constructor, a delegate-typed value, or something | |
| 349 | // stranger: the call's effect cannot be bounded | |
| 350 | _disqualify(); | |
| 351 | fi | |
| 352 | si | |
| 353 | ||
| 354 | // Constructing an imported exception type is store-free for | |
| 355 | // narrowing: an exception constructor by .NET convention only | |
| 356 | // records its arguments into the new exception's own state and | |
| 357 | // invokes no behaviour on them, so no user code runs and no | |
| 358 | // pre-existing heap slot is written. The constructor arguments | |
| 359 | // are classified as the walk reaches them, so a storing | |
| 360 | // argument still disqualifies. Restricted to reflected types so | |
| 361 | // a user-declared exception - whose constructor could store - | |
| 362 | // stays unbounded. | |
| 363 | _is_store_free_construction(symbol: Symbol?) -> bool is | |
| 364 | if !symbol? \/ !symbol.is_reflected \/ !isa Semantic.Symbols.Classy(symbol) then | |
| 365 | return false; | |
| 366 | fi | |
| 367 | ||
| 368 | let exception_type = _innate_symbol_lookup.get_exception_type(); | |
| 369 | let classy_type = (cast Semantic.Symbols.Classy(symbol)).type; | |
| 370 | ||
| 371 | return classy_type? /\ exception_type.is_assignable_from(classy_type); | |
| 372 | si | |
| 373 | ||
| 374 | // A property read runs its getter, and a call that reaches | |
| 375 | // the getter may dispatch to any overriding property's getter. | |
| 376 | // Property override links live on the Property symbols, not | |
| 377 | // on the accessor functions, so the override closure is | |
| 378 | // expanded here rather than through Function.overriders. | |
| 379 | _add_property_read_edges(property: Semantic.Symbols.Property) is | |
| 380 | if !_current? then | |
| 381 | return; | |
| 382 | fi | |
| 383 | ||
| 384 | if !property.read_function? then | |
| 385 | _disqualify(); | |
| 386 | return; | |
| 387 | fi | |
| 388 | ||
| 389 | _add_callee(property.read_function); | |
| 390 | ||
| 391 | let overriders = property.overriders; | |
| 392 | ||
| 393 | if !overriders? then | |
| 394 | return; | |
| 395 | fi | |
| 396 | ||
| 397 | for overrider in overriders do | |
| 398 | if isa Semantic.Symbols.Property(overrider) then | |
| 399 | _add_property_read_edges(cast Semantic.Symbols.Property(overrider)); | |
| 400 | else | |
| 401 | _disqualify(); | |
| 402 | fi | |
| 403 | od | |
| 404 | si | |
| 405 | ||
| 406 | _classify_member_read(symbol: Symbol?) is | |
| 407 | if !symbol? then | |
| 408 | return; | |
| 409 | fi | |
| 410 | ||
| 411 | if isa Semantic.Symbols.Property(symbol) then | |
| 412 | _add_property_read_edges(cast Semantic.Symbols.Property(symbol)); | |
| 413 | fi | |
| 414 | ||
| 415 | // fields, locals, parameters, function groups (a bare | |
| 416 | // function reference only creates a delegate), types and | |
| 417 | // namespaces are harmless reads | |
| 418 | si | |
| 419 | ||
| 420 | // ==== function context ==== | |
| 421 | ||
| 422 | pre(function: Definitions.FUNCTION) -> bool is | |
| 423 | enter_scope(function); | |
| 424 | ||
| 425 | if _current? then | |
| 426 | // function definitions do not nest; if the tree ever | |
| 427 | // produces one, poison the enclosing classification | |
| 428 | // rather than mis-attribute the nested body's facts | |
| 429 | _current.is_disqualified = true; | |
| 430 | fi | |
| 431 | ||
| 432 | _typer.reset(); | |
| 433 | ||
| 434 | let symbol = function_for(function); | |
| 435 | ||
| 436 | if symbol? then | |
| 437 | let facts = STORE_FREE_FACTS(); | |
| 438 | ||
| 439 | _facts[symbol] = facts; | |
| 440 | ||
| 441 | if _bucket? then | |
| 442 | _bucket![symbol] = facts; | |
| 443 | fi | |
| 444 | ||
| 445 | _current = facts; | |
| 446 | _current_function = symbol; | |
| 447 | else | |
| 448 | _current = null; | |
| 449 | _current_function = null; | |
| 450 | fi | |
| 451 | ||
| 452 | return false; | |
| 453 | si | |
| 454 | ||
| 455 | visit(function: Definitions.FUNCTION) is | |
| 456 | leave_scope(function); | |
| 457 | ||
| 458 | _current = null; | |
| 459 | _current_function = null; | |
| 460 | si | |
| 461 | ||
| 462 | // Property and indexer accessor bodies arrive as synthesised | |
| 463 | // sibling FUNCTION definitions; the original nodes carry the | |
| 464 | // same body and would double-classify it. | |
| 465 | pre(property: Definitions.PROPERTY) -> bool => true; | |
| 466 | visit(property: Definitions.PROPERTY) is si | |
| 467 | ||
| 468 | pre(indexer: Definitions.INDEXER) -> bool => true; | |
| 469 | visit(indexer: Definitions.INDEXER) is si | |
| 470 | ||
| 471 | // A lambda body does not run when the enclosing function | |
| 472 | // merely creates the closure; any invocation happens through | |
| 473 | // a delegate-typed value, which is never a bounded callee. | |
| 474 | // Closure symbols are never marked store-free. | |
| 475 | pre(function: Expressions.FUNCTION) -> bool => true; | |
| 476 | visit(function: Expressions.FUNCTION) is si | |
| 477 | ||
| 478 | // ==== stores ==== | |
| 479 | ||
| 480 | visit(assign: Statements.ASSIGNMENT) is | |
| 481 | if !_current? then | |
| 482 | return; | |
| 483 | fi | |
| 484 | ||
| 485 | _classify_assignment_target(assign.left); | |
| 486 | si | |
| 487 | ||
| 488 | _classify_assignment_target(left: Trees.Expressions.AssignmentLeftExpression?) is | |
| 489 | if !left? then | |
| 490 | _disqualify(); | |
| 491 | return; | |
| 492 | fi | |
| 493 | ||
| 494 | if isa Trees.Expressions.SIMPLE_LEFT_EXPRESSION(left) then | |
| 495 | _classify_simple_store((cast Trees.Expressions.SIMPLE_LEFT_EXPRESSION(left)).expression); | |
| 496 | elif isa Trees.Expressions.DESTRUCTURING_LEFT_EXPRESSION(left) then | |
| 497 | for element in (cast Trees.Expressions.DESTRUCTURING_LEFT_EXPRESSION(left)).elements do | |
| 498 | _classify_assignment_target(element); | |
| 499 | od | |
| 500 | else | |
| 501 | _disqualify(); | |
| 502 | fi | |
| 503 | si | |
| 504 | ||
| 505 | _classify_simple_store(target: Trees.Expressions.Expression?) is | |
| 506 | if _in_constructor /\ _writes_own_instance_field_member(target) then | |
| 507 | // `self.field = …` on the fresh receiver a constructor | |
| 508 | // is building: disqualifies the strict bit but not | |
| 509 | // construction, exactly like the bare-field form below | |
| 510 | _disqualify_strict_only(); | |
| 511 | return; | |
| 512 | fi | |
| 513 | ||
| 514 | if !target? \/ !isa Trees.Expressions.IDENTIFIER(target) then | |
| 515 | // a member, index or other compound target is a heap | |
| 516 | // store | |
| 517 | _disqualify(); | |
| 518 | return; | |
| 519 | fi | |
| 520 | ||
| 521 | let identifier = (cast Trees.Expressions.IDENTIFIER(target)).identifier; | |
| 522 | ||
| 523 | if identifier.is_qualified then | |
| 524 | _disqualify(); | |
| 525 | return; | |
| 526 | fi | |
| 527 | ||
| 528 | let symbol = try_find(identifier); | |
| 529 | ||
| 530 | if | |
| 531 | symbol? /\ | |
| 532 | (isa Semantic.Symbols.LOCAL_VARIABLE(symbol) \/ isa Semantic.Symbols.LOCAL_ARGUMENT(symbol)) | |
| 533 | then | |
| 534 | // reassigning a local variable or parameter is | |
| 535 | // callee-private | |
| 536 | return; | |
| 537 | fi | |
| 538 | ||
| 539 | if _in_constructor /\ symbol? /\ symbol.is_field /\ symbol.is_instance then | |
| 540 | // a bare instance-field name resolves to the receiver's | |
| 541 | // own field; in a constructor the receiver is the fresh | |
| 542 | // object a `NEW` is building, so the write disqualifies | |
| 543 | // the strict bit but not construction | |
| 544 | _disqualify_strict_only(); | |
| 545 | return; | |
| 546 | fi | |
| 547 | ||
| 548 | _disqualify(); | |
| 549 | si | |
| 550 | ||
| 551 | // ==== calls ==== | |
| 552 | ||
| 553 | visit(call: Expressions.CALL) is | |
| 554 | if !_current? then | |
| 555 | return; | |
| 556 | fi | |
| 557 | ||
| 558 | _add_call_target_edges(call.function); | |
| 559 | si | |
| 560 | ||
| 561 | // A value slot whose declared type is a pure function type: | |
| 562 | // invoking the held value is trusted store-free, whatever it | |
| 563 | // turns out to be — the pure-typed slot only admits pure | |
| 564 | // values. Parameters and fields qualify; a property is excluded | |
| 565 | // because reading it runs its getter. A local variable is | |
| 566 | // excluded too: its `type` is filled by compile-expressions, | |
| 567 | // which runs after this pass, so reading it here would make the | |
| 568 | // classification depend on whether that later pass has run — it | |
| 569 | // has in an analysis-mode refresh, it has not in a batch build. | |
| 570 | _is_pure_function_valued(symbol: Semantic.Symbols.Symbol?) -> bool => | |
| 571 | symbol? /\ | |
| 572 | isa Semantic.Symbols.Variable(symbol) /\ | |
| 573 | !isa Semantic.Symbols.LOCAL_VARIABLE(symbol) /\ | |
| 574 | symbol.type? /\ symbol.type.is_pure_function; | |
| 575 | ||
| 576 | _add_call_target_edges(target: Trees.Expressions.Expression?) is | |
| 577 | if !target? then | |
| 578 | _disqualify(); | |
| 579 | return; | |
| 580 | fi | |
| 581 | ||
| 582 | if isa Trees.Expressions.IDENTIFIER(target) then | |
| 583 | let identifier = (cast Trees.Expressions.IDENTIFIER(target)).identifier; | |
| 584 | ||
| 585 | let symbol = try_find(identifier); | |
| 586 | ||
| 587 | if _is_pure_function_valued(symbol) then | |
| 588 | return; | |
| 589 | fi | |
| 590 | ||
| 591 | _add_callee_edges(symbol); | |
| 592 | return; | |
| 593 | fi | |
| 594 | ||
| 595 | if isa Trees.Expressions.MEMBER(target) then | |
| 596 | let member = cast Trees.Expressions.MEMBER(target); | |
| 597 | ||
| 598 | let as_identifier = member.try_copy_as_identifer(); | |
| 599 | ||
| 600 | if as_identifier? then | |
| 601 | let symbol = try_find(as_identifier); | |
| 602 | ||
| 603 | if symbol? then | |
| 604 | if _is_pure_function_valued(symbol) then | |
| 605 | return; | |
| 606 | fi | |
| 607 | ||
| 608 | _add_callee_edges(symbol); | |
| 609 | return; | |
| 610 | fi | |
| 611 | fi | |
| 612 | ||
| 613 | let left_type = _typer.try_type(member.left); | |
| 614 | ||
| 615 | if !left_type? then | |
| 616 | _disqualify(); | |
| 617 | return; | |
| 618 | fi | |
| 619 | ||
| 620 | let member_symbol = left_type.find_member(member.identifier.name); | |
| 621 | ||
| 622 | if member_symbol? /\ _is_pure_function_valued(member_symbol) /\ member_symbol.is_field then | |
| 623 | return; | |
| 624 | fi | |
| 625 | ||
| 626 | _add_callee_edges(member_symbol); | |
| 627 | return; | |
| 628 | fi | |
| 629 | ||
| 630 | if isa Trees.Expressions.RECURSE(target) then | |
| 631 | _add_callee(_current_function); | |
| 632 | return; | |
| 633 | fi | |
| 634 | ||
| 635 | if isa Trees.Expressions.EXPLICIT_SPECIALIZATION(target) then | |
| 636 | _add_call_target_edges((cast Trees.Expressions.EXPLICIT_SPECIALIZATION(target)).left); | |
| 637 | return; | |
| 638 | fi | |
| 639 | ||
| 640 | _disqualify(); | |
| 641 | si | |
| 642 | ||
| 643 | // ==== operators ==== | |
| 644 | ||
| 645 | visit(binary: Expressions.BINARY) is | |
| 646 | if !_current? then | |
| 647 | return; | |
| 648 | fi | |
| 649 | ||
| 650 | _add_operator_edges(binary.operation, binary.left, binary.right); | |
| 651 | si | |
| 652 | ||
| 653 | visit(unary: Expressions.UNARY) is | |
| 654 | if !_current? then | |
| 655 | return; | |
| 656 | fi | |
| 657 | ||
| 658 | _add_operator_edges(unary.operation, unary.right, null); | |
| 659 | si | |
| 660 | ||
| 661 | _add_operator_edges( | |
| 662 | operation: Identifiers.Identifier?, | |
| 663 | left: Trees.Expressions.Expression?, | |
| 664 | right: Trees.Expressions.Expression? | |
| 665 | ) is | |
| 666 | if !operation? then | |
| 667 | _disqualify(); | |
| 668 | return; | |
| 669 | fi | |
| 670 | ||
| 671 | // free operator functions visible in scope: the innate | |
| 672 | // operators and user-defined operators share one group | |
| 673 | let group = find(operation.name); | |
| 674 | ||
| 675 | if group? then | |
| 676 | _add_callee_edges(group); | |
| 677 | fi | |
| 678 | ||
| 679 | // Equality is the one operator with a single | |
| 680 | // compiler-generated implementation: `==` and `!=` both | |
| 681 | // carry the operation name `==` (the parser rewrites `!=`), | |
| 682 | // and neither can be overloaded or overridden as a member. | |
| 683 | // There is never a member operator to bound, so the member | |
| 684 | // lookup — which otherwise disqualifies the function | |
| 685 | // whenever an operand's type is not trivially derivable — is | |
| 686 | // skipped. Other operators, comparisons included, can carry | |
| 687 | // a member implementation and still need it. | |
| 688 | if operation.name =~ "==" then | |
| 689 | return; | |
| 690 | fi | |
| 691 | ||
| 692 | // operator members can only be bounded when the operand | |
| 693 | // types are known | |
| 694 | _add_member_operator_edges(operation.name, left); | |
| 695 | ||
| 696 | if right? then | |
| 697 | _add_member_operator_edges(operation.name, right); | |
| 698 | fi | |
| 699 | si | |
| 700 | ||
| 701 | _add_member_operator_edges(name: string, operand: Trees.Expressions.Expression?) is | |
| 702 | let operand_type = _typer.try_type(operand); | |
| 703 | ||
| 704 | if !operand_type? then | |
| 705 | // The operand's type is not trivially derivable, so a | |
| 706 | // member operator on it cannot be bounded here. It is | |
| 707 | // safe only if no source type declares a member operator | |
| 708 | // of this name: a reflected type never exposes one under | |
| 709 | // a ghūl operator name, and the free and innate operators | |
| 710 | // are already bounded through the operator group above. | |
| 711 | if Semantic.Symbols.MEMBER_OPERATOR_NAMES.contains(name) then | |
| 712 | _disqualify(); | |
| 713 | fi | |
| 714 | ||
| 715 | return; | |
| 716 | fi | |
| 717 | ||
| 718 | let member_symbol = operand_type.find_member(name); | |
| 719 | ||
| 720 | if member_symbol? then | |
| 721 | _add_callee_edges(member_symbol); | |
| 722 | fi | |
| 723 | si | |
| 724 | ||
| 725 | // ==== reads ==== | |
| 726 | ||
| 727 | visit(identifier: Expressions.IDENTIFIER) is | |
| 728 | if !_current? then | |
| 729 | return; | |
| 730 | fi | |
| 731 | ||
| 732 | // an unresolvable bare name is either an error compile- | |
| 733 | // expressions will report or a contextual load (a unit | |
| 734 | // variant); neither can store | |
| 735 | _classify_member_read(try_find(identifier.identifier)); | |
| 736 | si | |
| 737 | ||
| 738 | visit(member: Expressions.MEMBER) is | |
| 739 | if !_current? then | |
| 740 | return; | |
| 741 | fi | |
| 742 | ||
| 743 | let as_identifier = member.try_copy_as_identifer(); | |
| 744 | ||
| 745 | if as_identifier? then | |
| 746 | let symbol = try_find(as_identifier); | |
| 747 | ||
| 748 | if symbol? then | |
| 749 | _classify_member_read(symbol); | |
| 750 | return; | |
| 751 | fi | |
| 752 | fi | |
| 753 | ||
| 754 | let left_type = _typer.try_type(member.left); | |
| 755 | ||
| 756 | if left_type? then | |
| 757 | let member_symbol = left_type.find_member(member.identifier.name); | |
| 758 | ||
| 759 | if member_symbol? then | |
| 760 | _classify_member_read(member_symbol); | |
| 761 | return; | |
| 762 | fi | |
| 763 | fi | |
| 764 | ||
| 765 | // untyped receiver: if this member turns out to be a | |
| 766 | // property, its getter could run arbitrary code | |
| 767 | _disqualify(); | |
| 768 | si | |
| 769 | ||
| 770 | visit(index: Expressions.INDEX) is | |
| 771 | if !_current? then | |
| 772 | return; | |
| 773 | fi | |
| 774 | ||
| 775 | let left_type = _typer.try_type(index.left); | |
| 776 | ||
| 777 | if !left_type? then | |
| 778 | _disqualify(); | |
| 779 | return; | |
| 780 | fi | |
| 781 | ||
| 782 | if isa Semantic.Types.ARRAY(left_type) then | |
| 783 | // array element read; element stores only occur as | |
| 784 | // assignment targets, which are classified separately | |
| 785 | return; | |
| 786 | fi | |
| 787 | ||
| 788 | // an indexer read runs the receiver type's get_Item — | |
| 789 | // bound it like any other member call | |
| 790 | _add_callee_edges(left_type.find_member("get_Item")); | |
| 791 | si | |
| 792 | ||
| 793 | visit(recurse: Expressions.RECURSE) is | |
| 794 | if !_current? then | |
| 795 | return; | |
| 796 | fi | |
| 797 | ||
| 798 | _add_callee(_current_function); | |
| 799 | si | |
| 800 | ||
| 801 | // ==== local variable declarations ==== | |
| 802 | ||
| 803 | visit(variable: Variables.VARIABLE) is | |
| 804 | if !_current? then | |
| 805 | return; | |
| 806 | fi | |
| 807 | ||
| 808 | if variable.want_dispose then | |
| 809 | // `let use` runs dispose() at scope exit | |
| 810 | _disqualify(); | |
| 811 | return; | |
| 812 | fi | |
| 813 | ||
| 814 | if variable.is_argument then | |
| 815 | // parameter types come from the symbol; a default | |
| 816 | // value expression is walked as part of this body and | |
| 817 | // classified like any other code | |
| 818 | return; | |
| 819 | fi | |
| 820 | ||
| 821 | let name = variable.name; | |
| 822 | ||
| 823 | if !name? then | |
| 824 | return; | |
| 825 | fi | |
| 826 | ||
| 827 | let symbol = find(name.name); | |
| 828 | ||
| 829 | if !symbol? \/ !isa Semantic.Symbols.LOCAL_VARIABLE(symbol) then | |
| 830 | return; | |
| 831 | fi | |
| 832 | ||
| 833 | // An explicitly-declared local carries its type on the | |
| 834 | // declaration node, resolved before this pass. Read it there, | |
| 835 | // not from the symbol: the symbol's `type` field is also | |
| 836 | // written later by compile-expressions inference, so reading | |
| 837 | // it would make the store-free classification depend on | |
| 838 | // whether that later pass has run — it has in an analysis-mode | |
| 839 | // refresh, it has not in a batch build. | |
| 840 | if !isa TypeExpressions.INFER(variable.type_expression) then | |
| 841 | if let declared = _typer.usable(variable.type_expression.type) then | |
| 842 | _typer.set_local_type(symbol, declared); | |
| 843 | fi | |
| 844 | ||
| 845 | return; | |
| 846 | fi | |
| 847 | ||
| 848 | let initializer_type = _typer.try_type(variable.initializer); | |
| 849 | ||
| 850 | if initializer_type? then | |
| 851 | _typer.set_local_type(symbol, initializer_type); | |
| 852 | fi | |
| 853 | si | |
| 854 | ||
| 855 | // An assert's condition and message classify like any other | |
| 856 | // code as the walk reaches them; the construct-and-throw | |
| 857 | // machinery a failing assert runs is compiler-synthesised — | |
| 858 | // it allocates a fresh exception and stores nothing that | |
| 859 | // existed before it, so even a caller that catches the | |
| 860 | // failure observes an unchanged heap. | |
| 861 | visit(`assert: Statements.ASSERT) is si | |
| 862 | visit(assert_in: Expressions.ASSERT_IN) is si | |
| 863 | ||
| 864 | // Interpolation formats each fragment by calling to_string | |
| 865 | // on it. When a fragment's static type is known, that | |
| 866 | // dispatch is bounded like any other member call — the | |
| 867 | // fixpoint checks the type's to_string and every override a | |
| 868 | // call could reach; primitive and object to_string bodies | |
| 869 | // are trusted imports. An untyped fragment, or one with a | |
| 870 | // format specifier (which selects a different, culture-aware | |
| 871 | // formatting path), cannot be bounded. | |
| 872 | visit(interpolation: Expressions.STRING_INTERPOLATION) is | |
| 873 | if !_current? then | |
| 874 | return; | |
| 875 | fi | |
| 876 | ||
| 877 | for fragment in interpolation.values do | |
| 878 | if fragment.is_expression then | |
| 879 | if fragment.format? then | |
| 880 | _disqualify(); | |
| 881 | return; | |
| 882 | fi | |
| 883 | ||
| 884 | let fragment_type = _typer.try_type(fragment.expression); | |
| 885 | ||
| 886 | if !fragment_type? then | |
| 887 | _disqualify(); | |
| 888 | return; | |
| 889 | fi | |
| 890 | ||
| 891 | _add_callee_edges(fragment_type.find_member("to_string")); | |
| 892 | fi | |
| 893 | od | |
| 894 | si | |
| 895 | ||
| 896 | // ==== innate bodies ==== | |
| 897 | ||
| 898 | visit(block: Bodies.INNATE) is | |
| 899 | if !_current? then | |
| 900 | return; | |
| 901 | fi | |
| 902 | ||
| 903 | if !STORE_FREE_INNATES.is_store_free(block.name) then | |
| 904 | _disqualify(); | |
| 905 | fi | |
| 906 | si | |
| 907 | ||
| 908 | // ==== audited-harmless node kinds ==== | |
| 909 | // | |
| 910 | // Everything below either has no effect of its own (its | |
| 911 | // children are classified independently as the walk reaches | |
| 912 | // them) or cannot occur in an executable position. | |
| 913 | ||
| 914 | visit(identifier: Identifiers.Identifier) is si | |
| 915 | visit(identifier: Identifiers.QUALIFIED) is si | |
| 916 | visit(modifier: Modifiers.Modifier) is si | |
| 917 | visit(modifiers: Modifiers.LIST) is si | |
| 918 | visit(pragma: Pragmas.PRAGMA) is si | |
| 919 | visit(pragma: Statements.PRAGMA) is si | |
| 920 | ||
| 921 | visit(type_expression: TypeExpressions.TypeExpression) is si | |
| 922 | visit(type_expression: TypeExpressions.INFER) is si | |
| 923 | visit(structured: TypeExpressions.Structured) is si | |
| 924 | visit(array: TypeExpressions.ARRAY_) is si | |
| 925 | visit(pointer: TypeExpressions.POINTER) is si | |
| 926 | visit(optional: TypeExpressions.OPTIONAL) is si | |
| 927 | visit(reference: TypeExpressions.REFERENCE) is si | |
| 928 | visit(member: TypeExpressions.MEMBER) is si | |
| 929 | visit(named: TypeExpressions.NAMED) is si | |
| 930 | visit(types: TypeExpressions.LIST) is si | |
| 931 | visit(generic: TypeExpressions.GENERIC) is si | |
| 932 | visit(function: TypeExpressions.FUNCTION) is si | |
| 933 | visit(functions: TypeExpressions.FUNCTION_GROUP) is si | |
| 934 | visit(tuple: TypeExpressions.TUPLE) is si | |
| 935 | visit(element: TypeExpressions.NAMED_TUPLE_ELEMENT) is si | |
| 936 | visit(element: TypeExpressions.UNDEFINED) is si | |
| 937 | visit(constraint: TypeExpressions.TYPE_PARAMETER_CONSTRAINT) is si | |
| 938 | ||
| 939 | visit(literal: Expressions.Literals.Literal) is si | |
| 940 | visit(`string: Expressions.Literals.STRING) is si | |
| 941 | visit(integer: Expressions.Literals.INTEGER) is si | |
| 942 | visit(float: Expressions.Literals.FLOAT) is si | |
| 943 | visit(character: Expressions.Literals.CHARACTER) is si | |
| 944 | visit(boolean: Expressions.Literals.BOOLEAN) is si | |
| 945 | visit(none: Expressions.Literals.NONE) is si | |
| 946 | ||
| 947 | visit(`null: Expressions.NULL) is si | |
| 948 | visit(`self: Expressions.SELF) is si | |
| 949 | visit(`super: Expressions.SUPER) is si | |
| 950 | visit(`cast: Expressions.CAST) is si | |
| 951 | visit(`isa: Expressions.ISA) is si | |
| 952 | visit(`isa: Expressions.TYPEOF) is si | |
| 953 | visit(`default: Expressions.DEFAULT) is si | |
| 954 | visit(has_value: Expressions.HAS_VALUE) is si | |
| 955 | visit(unwrap: Expressions.UNWRAP) is si | |
| 956 | visit(tuple: Expressions.TUPLE) is si | |
| 957 | visit(variable: Expressions.TUPLE_ELEMENT) is si | |
| 958 | visit(sequence: Expressions.SEQUENCE) is si | |
| 959 | visit(list: Expressions.LIST) is si | |
| 960 | visit(variable: Expressions.VARIABLE) is si | |
| 961 | visit(statement: Expressions.STATEMENT) is si | |
| 962 | visit(block: Expressions.VAL_BLOCK) is si | |
| 963 | visit(member: Expressions.EXPLICIT_SPECIALIZATION) is si | |
| 964 | ||
| 965 | visit(statement: Expressions.LET_IN) is | |
| 966 | if statement.want_dispose then | |
| 967 | _disqualify(); | |
| 968 | fi | |
| 969 | ||
| 970 | leave_scope(statement); | |
| 971 | si | |
| 972 | ||
| 973 | visit(left: Trees.Expressions.SIMPLE_LEFT_EXPRESSION) is si | |
| 974 | visit(destructure_left: Trees.Expressions.DESTRUCTURING_LEFT_EXPRESSION) is si | |
| 975 | ||
| 976 | visit(left: Trees.Variables.SIMPLE_VARIABLE_LEFT) is si | |
| 977 | visit(destructure_left: Trees.Variables.DESTRUCTURING_VARIABLE_LEFT) is si | |
| 978 | visit(left: Trees.Variables.LITERAL_VARIABLE_LEFT) is si | |
| 979 | visit(variables: Variables.LIST) is si | |
| 980 | ||
| 981 | visit(statements: Statements.LIST) is si | |
| 982 | visit(expression: Statements.EXPRESSION) is si | |
| 983 | visit(`return: Statements.RETURN) is si | |
| 984 | visit(`throw: Statements.THROW) is si | |
| 985 | visit(`if: Statements.IF) is si | |
| 986 | visit(`break: Statements.BREAK) is si | |
| 987 | visit(`continue: Statements.CONTINUE) is si | |
| 988 | visit(rb: Statements.REFUTABLE_BINDING) is si | |
| 989 | ||
| 990 | visit(l: Statements.LET) is | |
| 991 | if l.want_dispose then | |
| 992 | _disqualify(); | |
| 993 | fi | |
| 994 | si | |
| 995 | ||
| 996 | visit(if_branch: Statements.IF_BRANCH) is | |
| 997 | leave_scope(if_branch); | |
| 998 | si | |
| 999 | ||
| 1000 | visit(`case: Statements.CASE) is | |
| 1001 | leave_scope(`case); | |
| 1002 | si | |
| 1003 | ||
| 1004 | visit(case_match: Statements.CASE_MATCH) is | |
| 1005 | leave_scope(case_match); | |
| 1006 | si | |
| 1007 | ||
| 1008 | visit(`try: Statements.TRY) is | |
| 1009 | leave_scope(`try); | |
| 1010 | si | |
| 1011 | ||
| 1012 | visit(`catch: Statements.CATCH) is | |
| 1013 | leave_scope(`catch); | |
| 1014 | si | |
| 1015 | ||
| 1016 | visit(`do: Statements.DO) is | |
| 1017 | leave_scope(`do); | |
| 1018 | si | |
| 1019 | ||
| 1020 | visit(labelled: Statements.LABELLED) is | |
| 1021 | si | |
| 1022 | ||
| 1023 | visit(expression: Bodies.EXPRESSION) is | |
| 1024 | leave_scope(expression); | |
| 1025 | si | |
| 1026 | ||
| 1027 | visit(block: Bodies.BLOCK) is | |
| 1028 | leave_scope(block); | |
| 1029 | si | |
| 1030 | ||
| 1031 | // a bodiless declaration stores nothing; whether calls to it | |
| 1032 | // are safe is decided by its overriders through the fixpoint | |
| 1033 | visit(block: Bodies.NULL) is si | |
| 1034 | si | |
| 1035 | si |