Appearance
| 1 | namespace Syntax.Process is | |
| 2 | use Logging | |
| 3 | use Trees | |
| 4 | ||
| 5 | use Function = Semantic.Symbols.Function | |
| 6 | use Symbol = Semantic.Symbols.Symbol | |
| 7 | ||
| 8 | // Recognises the guarded-memoiser getter shape whose presence | |
| 9 | // answers are monotone: once the memoised member holds a value it | |
| 10 | // is never made absent again, so two adjacent reads through the | |
| 11 | // getter agree on presence. | |
| 12 | // | |
| 13 | // The shape: every member write in the body targets one instance | |
| 14 | // field of the receiver, every written value has a non-optional | |
| 15 | // static type, every absent-typed return sits inside an arm whose | |
| 16 | // condition proved that field absent, every other return returns | |
| 17 | // the field, and control cannot fall off the end of the body | |
| 18 | // (which would return an unguarded absent value). Local writes and | |
| 19 | // calls are unrestricted here - their effect on the member is | |
| 20 | // bounded by the solved relations, which the query consults. | |
| 21 | // | |
| 22 | // Why that is sound for presence: a read that answered present | |
| 23 | // returned the member, so the member was non-null when the call | |
| 24 | // ended; nothing runs between adjacent reads, so the next call | |
| 25 | // starts with the member still non-null; the solved relations | |
| 26 | // show nothing the getter can reach writes an absent value to it, | |
| 27 | // so it is still non-null at every guard; an absent-typed return | |
| 28 | // needs a guard that proved it absent; contradiction - the next | |
| 29 | // read returns the member, present. Type narrows are deliberately | |
| 30 | // not covered: a rewrite while absent can change the runtime type | |
| 31 | // a wider-typed member holds. | |
| 32 | class MONOTONE_MEMOISER_SHAPE: DefaultVisitor is | |
| 33 | _typer: TRIVIAL_EXPRESSION_TYPER | |
| 34 | ||
| 35 | _failed: bool | |
| 36 | _write_member: Symbol? | |
| 37 | _return_member: Symbol? | |
| 38 | _has_return_member: bool | |
| 39 | _absent_guards: Collections.LIST[Collections.LIST[Symbol]] | |
| 40 | ||
| 41 | // One entry per enclosing if-arm: the member whose absence | |
| 42 | // that arm's condition proved, or null when it proved nothing | |
| 43 | // usable. A return under an arm is dominated by every guard | |
| 44 | // on the stack, so absence established at any depth counts. | |
| 45 | _guard_stack: Collections.LIST[Symbol?] | |
| 46 | _if_stack: Collections.LIST[Statements.IF] | |
| 47 | ||
| 48 | init( | |
| 49 | logger: Logger, | |
| 50 | symbol_table: Semantic.SYMBOL_TABLE, | |
| 51 | namespaces: Semantic.NAMESPACES, | |
| 52 | typer: TRIVIAL_EXPRESSION_TYPER | |
| 53 | ) | |
| 54 | is | |
| 55 | super.init(logger, symbol_table, namespaces) | |
| 56 | ||
| 57 | _typer = typer | |
| 58 | _absent_guards = Collections.LIST[Collections.LIST[Symbol]]() | |
| 59 | _guard_stack = Collections.LIST[Symbol?]() | |
| 60 | _if_stack = Collections.LIST[Statements.IF]() | |
| 61 | si | |
| 62 | ||
| 63 | // Walk a property read accessor's body and return the | |
| 64 | // canonical memoised member, or null when the shape is not | |
| 65 | // the guarded-memoiser one. Never reports anything: a shape | |
| 66 | // mismatch is a conservative decline, not a diagnostic. | |
| 67 | classify_getter(body: Bodies.Body?) -> Symbol? is | |
| 68 | _failed = false | |
| 69 | _write_member = null | |
| 70 | _return_member = null | |
| 71 | _has_return_member = false | |
| 72 | _absent_guards.clear() | |
| 73 | ||
| 74 | if !body? then | |
| 75 | return null | |
| 76 | fi | |
| 77 | ||
| 78 | let mark = mark_scope_stack() | |
| 79 | ||
| 80 | try | |
| 81 | if isa Bodies.BLOCK(body) then | |
| 82 | let block = cast Bodies.BLOCK(body) | |
| 83 | ||
| 84 | block.walk(self) | |
| 85 | ||
| 86 | if _falls_through(block.statements) then | |
| 87 | _failed = true | |
| 88 | fi | |
| 89 | elif isa Bodies.EXPRESSION(body) then | |
| 90 | _note_return((cast Bodies.EXPRESSION(body)).expression) | |
| 91 | else | |
| 92 | _failed = true | |
| 93 | fi | |
| 94 | catch ex: System.Exception | |
| 95 | _failed = true | |
| 96 | yrt | |
| 97 | ||
| 98 | release_scope_stack(mark) | |
| 99 | ||
| 100 | if _failed then | |
| 101 | return null | |
| 102 | fi | |
| 103 | ||
| 104 | let member mut = _write_member | |
| 105 | ||
| 106 | if _has_return_member then | |
| 107 | if _return_member? /\ _write_member? /\ _return_member != _write_member then | |
| 108 | return null | |
| 109 | fi | |
| 110 | ||
| 111 | if !member? then | |
| 112 | member = _return_member | |
| 113 | fi | |
| 114 | fi | |
| 115 | ||
| 116 | if !member? then | |
| 117 | return null | |
| 118 | fi | |
| 119 | ||
| 120 | let memoised = member | |
| 121 | ||
| 122 | for guards in _absent_guards do | |
| 123 | if !_guarded_by(guards, memoised) then | |
| 124 | return null | |
| 125 | fi | |
| 126 | od | |
| 127 | ||
| 128 | return memoised | |
| 129 | si | |
| 130 | ||
| 131 | _guarded_by(guards: Collections.LIST[Symbol], member: Symbol) -> bool static is | |
| 132 | for guard in guards do | |
| 133 | if guard == member then | |
| 134 | return true | |
| 135 | fi | |
| 136 | od | |
| 137 | ||
| 138 | return false | |
| 139 | si | |
| 140 | ||
| 141 | // A lambda body runs on invocation, not during the getter's | |
| 142 | // own call, so its returns and writes are not this body's; | |
| 143 | // its effect on the member arrives through the solved | |
| 144 | // relations like any other callee. | |
| 145 | pre(function: Expressions.FUNCTION) -> bool => true | |
| 146 | visit(function: Expressions.FUNCTION) is si | |
| 147 | ||
| 148 | // Node kinds this walk does not handle carry no shape | |
| 149 | // information of their own - their effect on the member is | |
| 150 | // the solved relations' question, not this one. | |
| 151 | visit_default(node: Trees.Node) is si | |
| 152 | ||
| 153 | pre(assign: Statements.ASSIGNMENT) -> bool is | |
| 154 | _note_assignment(assign) | |
| 155 | ||
| 156 | return false | |
| 157 | si | |
| 158 | ||
| 159 | visit(`return: Statements.RETURN) is | |
| 160 | // a return inside a val block exits that block, not the | |
| 161 | // getter | |
| 162 | if `return.val_block_target? then | |
| 163 | return | |
| 164 | fi | |
| 165 | ||
| 166 | _note_return(`return.expression) | |
| 167 | si | |
| 168 | ||
| 169 | pre(`if: Statements.IF) -> bool is | |
| 170 | _if_stack.add(`if) | |
| 171 | ||
| 172 | return false | |
| 173 | si | |
| 174 | ||
| 175 | visit(`if: Statements.IF) is | |
| 176 | _if_stack.remove_at(_if_stack.count - 1) | |
| 177 | si | |
| 178 | ||
| 179 | pre(if_branch: Statements.IF_BRANCH) -> bool is | |
| 180 | let result = super.pre(if_branch) | |
| 181 | ||
| 182 | let current_if: Statements.IF? = | |
| 183 | if _if_stack.count > 0 then _if_stack[_if_stack.count - 1] else null fi | |
| 184 | ||
| 185 | _guard_stack.add(_arm_absent_member(if_branch, current_if)) | |
| 186 | ||
| 187 | return result | |
| 188 | si | |
| 189 | ||
| 190 | visit(if_branch: Statements.IF_BRANCH) is | |
| 191 | _guard_stack.remove_at(_guard_stack.count - 1) | |
| 192 | ||
| 193 | super.visit(if_branch) | |
| 194 | si | |
| 195 | ||
| 196 | // The member whose absence `branch`'s arm entry proves, or | |
| 197 | // null. A conditioned arm proves absence when its condition | |
| 198 | // is (or conjoins) a negated presence test on the receiver's | |
| 199 | // own field. An `if let` arm (a binding, no condition) proves | |
| 200 | // nothing here. The else arm (no condition, no binding) is | |
| 201 | // entered only when every sibling condition was false, so a | |
| 202 | // sibling's bare presence test proves absence there. | |
| 203 | _arm_absent_member(branch: Statements.IF_BRANCH, current_if: Statements.IF?) -> Symbol? is | |
| 204 | if branch.condition? then | |
| 205 | return _then_arm_absent_member(branch.condition) | |
| 206 | fi | |
| 207 | ||
| 208 | if branch.binding? \/ !current_if? then | |
| 209 | return null | |
| 210 | fi | |
| 211 | ||
| 212 | for sibling in current_if.branches do | |
| 213 | if sibling.condition? /\ isa Expressions.HAS_VALUE(sibling.condition) then | |
| 214 | let member = _self_member_of((cast Expressions.HAS_VALUE(sibling.condition)).left) | |
| 215 | ||
| 216 | if member? then | |
| 217 | return member | |
| 218 | fi | |
| 219 | fi | |
| 220 | od | |
| 221 | ||
| 222 | return null | |
| 223 | si | |
| 224 | ||
| 225 | _then_arm_absent_member(condition: Expressions.Expression) -> Symbol? is | |
| 226 | if isa Expressions.BINARY(condition) then | |
| 227 | let binary = cast Expressions.BINARY(condition) | |
| 228 | ||
| 229 | if binary.operation.name =~ "/\\" then | |
| 230 | let from_left = _then_arm_absent_member(binary.left) | |
| 231 | ||
| 232 | if from_left? then | |
| 233 | return from_left | |
| 234 | fi | |
| 235 | ||
| 236 | return _then_arm_absent_member(binary.right) | |
| 237 | fi | |
| 238 | ||
| 239 | return null | |
| 240 | fi | |
| 241 | ||
| 242 | if isa Expressions.UNARY(condition) then | |
| 243 | let unary = cast Expressions.UNARY(condition) | |
| 244 | ||
| 245 | if unary.operation.name =~ "!" /\ isa Expressions.HAS_VALUE(unary.right) then | |
| 246 | return _self_member_of((cast Expressions.HAS_VALUE(unary.right)).left) | |
| 247 | fi | |
| 248 | fi | |
| 249 | ||
| 250 | return null | |
| 251 | si | |
| 252 | ||
| 253 | _note_assignment(assign: Statements.ASSIGNMENT) is | |
| 254 | let left = assign.left | |
| 255 | ||
| 256 | if isa Expressions.SIMPLE_LEFT_EXPRESSION(left) then | |
| 257 | _note_store_target( | |
| 258 | (cast Expressions.SIMPLE_LEFT_EXPRESSION(left)).expression, | |
| 259 | assign.right) | |
| 260 | return | |
| 261 | fi | |
| 262 | ||
| 263 | if isa Expressions.DESTRUCTURING_LEFT_EXPRESSION(left) then | |
| 264 | // a destructuring store cannot give the per-element | |
| 265 | // written types this shape needs | |
| 266 | _failed = true | |
| 267 | return | |
| 268 | fi | |
| 269 | ||
| 270 | _failed = true | |
| 271 | si | |
| 272 | ||
| 273 | _note_store_target(target: Expressions.Expression?, value: Expressions.Expression?) is | |
| 274 | let member = _self_member_of(target) | |
| 275 | ||
| 276 | if member? then | |
| 277 | if _write_member? /\ _write_member != member then | |
| 278 | _failed = true | |
| 279 | return | |
| 280 | fi | |
| 281 | ||
| 282 | _write_member = member | |
| 283 | ||
| 284 | let type = _typer.try_type(value) | |
| 285 | ||
| 286 | if !type? \/ type.is_optional then | |
| 287 | _failed = true | |
| 288 | fi | |
| 289 | ||
| 290 | return | |
| 291 | fi | |
| 292 | ||
| 293 | if _is_local_target(target) then | |
| 294 | return | |
| 295 | fi | |
| 296 | ||
| 297 | // a store to anything but the receiver's own memoised | |
| 298 | // field - another object's member, a property, a global, | |
| 299 | // an element | |
| 300 | _failed = true | |
| 301 | si | |
| 302 | ||
| 303 | _is_local_target(target: Expressions.Expression?) -> bool is | |
| 304 | if !target? \/ !isa Expressions.IDENTIFIER(target) then | |
| 305 | return false | |
| 306 | fi | |
| 307 | ||
| 308 | let identifier = (cast Expressions.IDENTIFIER(target)).identifier | |
| 309 | ||
| 310 | if identifier.is_qualified then | |
| 311 | return false | |
| 312 | fi | |
| 313 | ||
| 314 | let symbol = try_find(identifier) | |
| 315 | ||
| 316 | return | |
| 317 | symbol? /\ | |
| 318 | (isa Semantic.Symbols.LOCAL_VARIABLE(symbol) \/ isa Semantic.Symbols.LOCAL_ARGUMENT(symbol)) | |
| 319 | si | |
| 320 | ||
| 321 | // The receiver's own instance field named by `target`, or | |
| 322 | // null for anything else - another object's member, a | |
| 323 | // property, a local, an unresolved name. | |
| 324 | _self_member_of(target: Expressions.Expression?) -> Symbol? is | |
| 325 | if !target? then | |
| 326 | return null | |
| 327 | fi | |
| 328 | ||
| 329 | if isa Expressions.IDENTIFIER(target) then | |
| 330 | let identifier = (cast Expressions.IDENTIFIER(target)).identifier | |
| 331 | ||
| 332 | if identifier.is_qualified then | |
| 333 | return null | |
| 334 | fi | |
| 335 | ||
| 336 | let symbol = try_find(identifier) | |
| 337 | ||
| 338 | if symbol? /\ symbol.is_field /\ symbol.is_instance then | |
| 339 | return symbol.root_specialized_from | |
| 340 | fi | |
| 341 | ||
| 342 | return null | |
| 343 | fi | |
| 344 | ||
| 345 | if isa Expressions.MEMBER(target) then | |
| 346 | let member = cast Expressions.MEMBER(target) | |
| 347 | ||
| 348 | if !isa Expressions.SELF(member.left) then | |
| 349 | return null | |
| 350 | fi | |
| 351 | ||
| 352 | let context = current_instance_context | |
| 353 | ||
| 354 | if !context? then | |
| 355 | return null | |
| 356 | fi | |
| 357 | ||
| 358 | let symbol = context.find_member(member.identifier.name) | |
| 359 | ||
| 360 | if symbol? /\ symbol.is_field /\ symbol.is_instance then | |
| 361 | return symbol.root_specialized_from | |
| 362 | fi | |
| 363 | fi | |
| 364 | ||
| 365 | return null | |
| 366 | si | |
| 367 | ||
| 368 | _note_return(expression: Expressions.Expression?) is | |
| 369 | if !expression? then | |
| 370 | _note_absent_return() | |
| 371 | return | |
| 372 | fi | |
| 373 | ||
| 374 | if isa Expressions.NULL(expression) then | |
| 375 | _note_absent_return() | |
| 376 | return | |
| 377 | fi | |
| 378 | ||
| 379 | let member = _self_member_of(expression) | |
| 380 | ||
| 381 | if member? then | |
| 382 | if _has_return_member /\ _return_member != member then | |
| 383 | _failed = true | |
| 384 | return | |
| 385 | fi | |
| 386 | ||
| 387 | _return_member = member | |
| 388 | _has_return_member = true | |
| 389 | return | |
| 390 | fi | |
| 391 | ||
| 392 | let type = _typer.try_type(expression) | |
| 393 | ||
| 394 | if type? /\ type.is_optional then | |
| 395 | _note_absent_return() | |
| 396 | else | |
| 397 | // a present value from somewhere other than the | |
| 398 | // member, or nothing the typer can type | |
| 399 | _failed = true | |
| 400 | fi | |
| 401 | si | |
| 402 | ||
| 403 | _note_absent_return() is | |
| 404 | let guards = Collections.LIST[Symbol]() | |
| 405 | ||
| 406 | for operand in _guard_stack do | |
| 407 | if operand? then | |
| 408 | guards.add(operand) | |
| 409 | fi | |
| 410 | od | |
| 411 | ||
| 412 | _absent_guards.add(guards) | |
| 413 | si | |
| 414 | ||
| 415 | // Whether control can reach the end of a block-bodied | |
| 416 | // getter, whose fall-off return value would be an absent | |
| 417 | // return no guard dominates. A statement that does not fall | |
| 418 | // through ends every path through the list, so the list | |
| 419 | // falls through only when every statement in it does. | |
| 420 | // Over-approximates - anything not explicitly a divergence | |
| 421 | // or a fully-covering branch structure falls through, which | |
| 422 | // only declines the shape. | |
| 423 | _falls_through(statements: Statements.LIST) -> bool is | |
| 424 | for statement in statements do | |
| 425 | if !_statement_falls_through(statement) then | |
| 426 | return false | |
| 427 | fi | |
| 428 | od | |
| 429 | ||
| 430 | return true | |
| 431 | si | |
| 432 | ||
| 433 | _statement_falls_through(statement: Statements.Statement) -> bool is | |
| 434 | if | |
| 435 | isa Statements.RETURN(statement) \/ | |
| 436 | isa Statements.THROW(statement) \/ | |
| 437 | isa Statements.BREAK(statement) \/ | |
| 438 | isa Statements.CONTINUE(statement) | |
| 439 | then | |
| 440 | return false | |
| 441 | fi | |
| 442 | ||
| 443 | if isa Statements.IF(statement) then | |
| 444 | let `if = cast Statements.IF(statement) | |
| 445 | let has_else mut = false | |
| 446 | ||
| 447 | for branch in `if.branches do | |
| 448 | if !branch.condition? /\ !branch.binding? then | |
| 449 | has_else = true | |
| 450 | fi | |
| 451 | od | |
| 452 | ||
| 453 | if !has_else then | |
| 454 | return true | |
| 455 | fi | |
| 456 | ||
| 457 | for branch in `if.branches do | |
| 458 | if _falls_through(branch.body) then | |
| 459 | return true | |
| 460 | fi | |
| 461 | od | |
| 462 | ||
| 463 | return false | |
| 464 | fi | |
| 465 | ||
| 466 | if isa Statements.CASE(statement) then | |
| 467 | let `case = cast Statements.CASE(statement) | |
| 468 | let has_else mut = false | |
| 469 | ||
| 470 | for match in `case.matches do | |
| 471 | if !match.expressions? /\ !match.pattern? then | |
| 472 | has_else = true | |
| 473 | fi | |
| 474 | od | |
| 475 | ||
| 476 | if !has_else /\ !`case.is_exhaustive then | |
| 477 | return true | |
| 478 | fi | |
| 479 | ||
| 480 | for match in `case.matches do | |
| 481 | if _falls_through(match.statements) then | |
| 482 | return true | |
| 483 | fi | |
| 484 | od | |
| 485 | ||
| 486 | return false | |
| 487 | fi | |
| 488 | ||
| 489 | if isa Statements.TRY(statement) then | |
| 490 | let `try = cast Statements.TRY(statement) | |
| 491 | ||
| 492 | if _falls_through(`try.body) then | |
| 493 | return true | |
| 494 | fi | |
| 495 | ||
| 496 | for `catch in `try.catches do | |
| 497 | if _falls_through(`catch.body) then | |
| 498 | return true | |
| 499 | fi | |
| 500 | od | |
| 501 | ||
| 502 | return false | |
| 503 | fi | |
| 504 | ||
| 505 | return true | |
| 506 | si | |
| 507 | si | |
| 508 | ||
| 509 | ||
| 510 | // The per-compilation record of which getters hold the guarded- | |
| 511 | // memoiser shape, filled by the infer-effects body walk and read | |
| 512 | // by the crossing discharge to discharge a presence fact against a | |
| 513 | // monotone memoiser's own call. | |
| 514 | // | |
| 515 | // Entries are noted per file and dropped when that file is | |
| 516 | // re-walked, so a getter whose body stopped matching the shape | |
| 517 | // on an edit cannot keep a stale classification. An entry with a | |
| 518 | // null member records the decline, so re-walking a demoted | |
| 519 | // getter overwrites its earlier classification. | |
| 520 | class MONOTONE_MEMOISER is | |
| 521 | _entries: Collections.MAP[Function, MONOTONE_MEMOISER_ENTRY] static | |
| 522 | _dispatch: STORE_FREE_FIXPOINT static | |
| 523 | ||
| 524 | init() static is | |
| 525 | _entries = Collections.MAP[Function, MONOTONE_MEMOISER_ENTRY]() | |
| 526 | _dispatch = STORE_FREE_FIXPOINT() | |
| 527 | si | |
| 528 | ||
| 529 | note_getter(getter: Function, member: Symbol?, file_name: string) static is | |
| 530 | let root = cast Function?(getter.root_specialized_from) | |
| 531 | ||
| 532 | if !root? then | |
| 533 | return | |
| 534 | fi | |
| 535 | ||
| 536 | _entries[root] = MONOTONE_MEMOISER_ENTRY(member, file_name) | |
| 537 | si | |
| 538 | ||
| 539 | clear_file(file_name: string) static is | |
| 540 | let stale = Collections.LIST[Function]() | |
| 541 | ||
| 542 | for entry in _entries do | |
| 543 | if entry.value.file_name =~ file_name then | |
| 544 | stale.add(entry.key) | |
| 545 | fi | |
| 546 | od | |
| 547 | ||
| 548 | for key in stale do | |
| 549 | _entries.remove(key) | |
| 550 | od | |
| 551 | si | |
| 552 | ||
| 553 | // Whether a presence fact read through `property` survives | |
| 554 | // the getter's own call: the body holds the guarded-memoiser | |
| 555 | // shape, nothing the getter can reach writes an absent value | |
| 556 | // to the memoised member, and dispatch cannot reach a getter | |
| 557 | // that fails either question. | |
| 558 | is_presence_monotone(property: Semantic.Symbols.Property) -> bool static is | |
| 559 | let getter = property.read_function | |
| 560 | ||
| 561 | if !getter? then | |
| 562 | return false | |
| 563 | fi | |
| 564 | ||
| 565 | let root = cast Function?(getter.root_specialized_from) | |
| 566 | ||
| 567 | if !root? then | |
| 568 | return false | |
| 569 | fi | |
| 570 | ||
| 571 | if !_entries.contains_key(root) then | |
| 572 | return false | |
| 573 | fi | |
| 574 | ||
| 575 | let entry = _entries[root] | |
| 576 | ||
| 577 | if !entry.member? then | |
| 578 | return false | |
| 579 | fi | |
| 580 | ||
| 581 | if !EFFECTS.is_solved then | |
| 582 | return false | |
| 583 | fi | |
| 584 | ||
| 585 | if EFFECTS.may_null(root, entry.member) then | |
| 586 | return false | |
| 587 | fi | |
| 588 | ||
| 589 | if _dispatch.is_openly_dispatchable(root) then | |
| 590 | return false | |
| 591 | fi | |
| 592 | ||
| 593 | let overriders = property.overriders | |
| 594 | ||
| 595 | if overriders? then | |
| 596 | for overrider in overriders do | |
| 597 | if !isa Semantic.Symbols.Property(overrider) then | |
| 598 | return false | |
| 599 | fi | |
| 600 | ||
| 601 | if !is_presence_monotone(cast Semantic.Symbols.Property(overrider)) then | |
| 602 | return false | |
| 603 | fi | |
| 604 | od | |
| 605 | fi | |
| 606 | ||
| 607 | return true | |
| 608 | si | |
| 609 | si | |
| 610 | ||
| 611 | ||
| 612 | class MONOTONE_MEMOISER_ENTRY( | |
| 613 | member: Symbol?, | |
| 614 | file_name: string | |
| 615 | ) | |
| 616 | si |