Appearance
| 1 | namespace Syntax.Process is | |
| 2 | use Function = Semantic.Symbols.Function | |
| 3 | use Symbol = Semantic.Symbols.Symbol | |
| 4 | use Semantic.Symbols.STORE_FREE_IMPORTS | |
| 5 | ||
| 6 | // Solves the whole-program effect relations the crossing discharge | |
| 7 | // reads, over the same per-function facts STORE_FREE_FIXPOINT | |
| 8 | // consumes: member-granular may-write and may-write-null sets, the | |
| 9 | // store-free set, and member read closures. Nothing here writes a | |
| 10 | // store-free bit; the solved sets are installed into EFFECTS. | |
| 11 | // One solve's rows, keyed on the functions, kept so the next solve | |
| 12 | // can start from them: a row whose inputs did not change, directly | |
| 13 | // or through anything it absorbs, is the same row. | |
| 14 | class EFFECT_SOLUTION( | |
| 15 | write_sets: Collections.MutableMap[Function, Collections.SET[Symbol]], | |
| 16 | write_unbounded: Collections.SET[Function], | |
| 17 | null_sets: Collections.MutableMap[Function, Collections.SET[Symbol]], | |
| 18 | null_unbounded: Collections.SET[Function], | |
| 19 | store_free: Collections.SET[Function], | |
| 20 | constructs_store_free: Collections.SET[Function], | |
| 21 | read_sets: Collections.MutableMap[Function, Collections.SET[Symbol]], | |
| 22 | read_unbounded: Collections.SET[Function], | |
| 23 | reads_elements: Collections.SET[Function], | |
| 24 | writes_elements: Collections.SET[Function] | |
| 25 | ) | |
| 26 | ||
| 27 | class EFFECT_SOLVERS is | |
| 28 | _facts: Collections.MutableMap[Function, STORE_FREE_FACTS] | |
| 29 | ||
| 30 | // Set to solve from a previous solution: only the rows in | |
| 31 | // `_affected` are re-derived, every other row is taken from | |
| 32 | // `_previous` as it stands. | |
| 33 | _previous: EFFECT_SOLUTION? | |
| 34 | _affected: Collections.SET[Function]? | |
| 35 | ||
| 36 | // Functions that invoke a function-typed parameter, directly | |
| 37 | // or by forwarding one to something that does. Their write | |
| 38 | // sets absorb the write sets of every function value passed | |
| 39 | // to them at any recorded call site. | |
| 40 | _param_invokers: Collections.SET[Function]? | |
| 41 | ||
| 42 | _dependants: EFFECT_DEPENDANTS? | |
| 43 | ||
| 44 | init(facts: Collections.MutableMap[Function, STORE_FREE_FACTS]) is | |
| 45 | _facts = facts | |
| 46 | si | |
| 47 | ||
| 48 | dependants: EFFECT_DEPENDANTS is | |
| 49 | if _dependants? then | |
| 50 | return _dependants | |
| 51 | fi | |
| 52 | ||
| 53 | let result = EFFECT_DEPENDANTS(_facts, param_invokers) | |
| 54 | ||
| 55 | _dependants = result | |
| 56 | ||
| 57 | return result | |
| 58 | si | |
| 59 | ||
| 60 | // Solve from `previous`, re-deriving only the rows of the | |
| 61 | // functions whose own inputs changed and of everything that | |
| 62 | // absorbs one of them, directly or through a chain. A row | |
| 63 | // outside that closure has exactly the inputs it had, so it | |
| 64 | // keeps its previous value. | |
| 65 | seed_from(previous: EFFECT_SOLUTION, changed: Collections.Iterable[Function]) is | |
| 66 | let affected = Collections.SET[Function]() | |
| 67 | let frontier = Collections.LIST[Function]() | |
| 68 | ||
| 69 | for function in changed do | |
| 70 | if affected.add(function) then | |
| 71 | frontier.add(function) | |
| 72 | fi | |
| 73 | od | |
| 74 | ||
| 75 | let i mut = 0 | |
| 76 | ||
| 77 | while i < frontier.count do | |
| 78 | let target = frontier[i] | |
| 79 | i = i + 1 | |
| 80 | ||
| 81 | for functions in [dependants.dependants_of(target), dependants.dependants_through_unwalked(target)] do | |
| 82 | if !functions? then | |
| 83 | continue | |
| 84 | fi | |
| 85 | ||
| 86 | for function in functions do | |
| 87 | if affected.add(function) then | |
| 88 | frontier.add(function) | |
| 89 | fi | |
| 90 | od | |
| 91 | od | |
| 92 | od | |
| 93 | ||
| 94 | _previous = previous | |
| 95 | _affected = affected | |
| 96 | si | |
| 97 | ||
| 98 | // The functions whose rows this solve derives: every walked | |
| 99 | // function, or the affected ones when seeded. | |
| 100 | affected_count: int => if let affected = _affected then affected.count else _facts.count fi | |
| 101 | ||
| 102 | // Whether `function`'s row is derived here rather than kept. | |
| 103 | _is_derived(function: Function) -> bool is | |
| 104 | if !_previous? \/ !_affected? then | |
| 105 | return true | |
| 106 | fi | |
| 107 | ||
| 108 | return _affected.contains(function) | |
| 109 | si | |
| 110 | ||
| 111 | // The rows derived by this solve, in a stable order. | |
| 112 | _derived: Collections.Iterable[Function] is | |
| 113 | if let affected = _affected then | |
| 114 | let result = Collections.LIST[Function]() | |
| 115 | ||
| 116 | for function in affected do | |
| 117 | if _facts.contains_key(function) then | |
| 118 | result.add(function) | |
| 119 | fi | |
| 120 | od | |
| 121 | ||
| 122 | return result | |
| 123 | fi | |
| 124 | ||
| 125 | return _facts.keys | |
| 126 | si | |
| 127 | ||
| 128 | param_invokers: Collections.SET[Function] is | |
| 129 | if _param_invokers? then | |
| 130 | return _param_invokers | |
| 131 | fi | |
| 132 | ||
| 133 | let invokers = Collections.SET[Function]() | |
| 134 | ||
| 135 | for function in _facts.keys do | |
| 136 | let record = EFFECT_FACTS.record_for(function) | |
| 137 | ||
| 138 | if record? /\ record.invokes_function_param then | |
| 139 | invokers.add(function) | |
| 140 | fi | |
| 141 | od | |
| 142 | ||
| 143 | let changed mut = true | |
| 144 | ||
| 145 | while changed do | |
| 146 | changed = false | |
| 147 | ||
| 148 | for function in _facts.keys do | |
| 149 | if invokers.contains(function) then | |
| 150 | continue | |
| 151 | fi | |
| 152 | ||
| 153 | let record = EFFECT_FACTS.record_for(function) | |
| 154 | ||
| 155 | if !record? then | |
| 156 | continue | |
| 157 | fi | |
| 158 | ||
| 159 | for target in record.forwards_param_to do | |
| 160 | if invokers.contains(target) then | |
| 161 | invokers.add(function) | |
| 162 | changed = true | |
| 163 | fi | |
| 164 | od | |
| 165 | od | |
| 166 | od | |
| 167 | ||
| 168 | _param_invokers = invokers | |
| 169 | ||
| 170 | return invokers | |
| 171 | si | |
| 172 | ||
| 173 | // The store-free relation, solved by STORE_FREE_FIXPOINT | |
| 174 | // itself so the two can never drift apart. The construction | |
| 175 | // relation rides along: a constructor in it writes nothing | |
| 176 | // beyond its own fresh receiver's state, which no | |
| 177 | // pre-existing fact can see. | |
| 178 | solve() -> ( | |
| 179 | store_free: Collections.SET[Function], | |
| 180 | constructs_store_free: Collections.SET[Function] | |
| 181 | ) is | |
| 182 | let solved = STORE_FREE_FIXPOINT().solve(_facts, dependants, _previous, _affected) | |
| 183 | ||
| 184 | let safe = Collections.SET[Function]() | |
| 185 | let construction_safe = Collections.SET[Function]() | |
| 186 | ||
| 187 | for function in _facts.keys do | |
| 188 | if !solved.unsafe.contains(function) then | |
| 189 | safe.add(function) | |
| 190 | fi | |
| 191 | ||
| 192 | if !solved.construction_unsafe.contains(function) then | |
| 193 | construction_safe.add(function) | |
| 194 | fi | |
| 195 | od | |
| 196 | ||
| 197 | return (store_free = safe, constructs_store_free = construction_safe) | |
| 198 | si | |
| 199 | ||
| 200 | // What each function may write, at member-symbol granularity: | |
| 201 | // its own writes, plus those of everything it can dispatch to. | |
| 202 | // `unbounded` names the functions for which no such set exists | |
| 203 | // - the walk lost track, a callee was not walked, or an | |
| 204 | // override outside the compilation could write anything. | |
| 205 | // | |
| 206 | // Receiver-blind, exactly as NARROWING_FLOW.on_member_store is: | |
| 207 | // a write to `other.f` and one to `self.f` are the same entry, | |
| 208 | // because the two receivers may alias. | |
| 209 | write_sets(close_open: bool, trust_imports: bool) -> ( | |
| 210 | sets: Collections.MutableMap[Function, Collections.SET[Symbol]], | |
| 211 | unbounded: Collections.SET[Function] | |
| 212 | ) is | |
| 213 | let sets = Collections.MAP[Function, Collections.SET[Symbol]]() | |
| 214 | let unbounded = Collections.SET[Function]() | |
| 215 | let shadow = STORE_FREE_FIXPOINT() | |
| 216 | ||
| 217 | let previous = _previous | |
| 218 | ||
| 219 | for function in _facts.keys do | |
| 220 | if !_is_derived(function) /\ previous? /\ previous.write_sets.contains_key(function) then | |
| 221 | sets[function] = previous.write_sets[function] | |
| 222 | ||
| 223 | if previous.write_unbounded.contains(function) then | |
| 224 | unbounded.add(function) | |
| 225 | fi | |
| 226 | ||
| 227 | continue | |
| 228 | fi | |
| 229 | ||
| 230 | let set = Collections.SET[Symbol]() | |
| 231 | let record = EFFECT_FACTS.record_for(function) | |
| 232 | ||
| 233 | if record? then | |
| 234 | for member in record.writes do | |
| 235 | set.add(member) | |
| 236 | od | |
| 237 | ||
| 238 | if record.writes_unbounded then | |
| 239 | unbounded.add(function) | |
| 240 | fi | |
| 241 | else | |
| 242 | unbounded.add(function) | |
| 243 | fi | |
| 244 | ||
| 245 | // An override in another assembly could write anything. | |
| 246 | // `close_open` drops that, which is the whole-program | |
| 247 | // assumption a self-contained program like the compiler | |
| 248 | // could legitimately make. | |
| 249 | if !close_open /\ shadow.is_openly_dispatchable(function) then | |
| 250 | unbounded.add(function) | |
| 251 | fi | |
| 252 | ||
| 253 | sets[function] = set | |
| 254 | od | |
| 255 | ||
| 256 | // Every row absorbs all its targets once; from then on a | |
| 257 | // target is re-absorbed only into the rows that depend on | |
| 258 | // it, and only when its own row changed. A row's set only | |
| 259 | // grows and its unbounded flag only sets, so a target that | |
| 260 | // has not changed since it was absorbed has nothing new to | |
| 261 | // contribute. | |
| 262 | let changed = Collections.SET[Function]() | |
| 263 | ||
| 264 | for function in _derived do | |
| 265 | let before = sets[function].count | |
| 266 | ||
| 267 | if _absorb(function, sets, unbounded, trust_imports) \/ sets[function].count != before then | |
| 268 | changed.add(function) | |
| 269 | fi | |
| 270 | od | |
| 271 | ||
| 272 | let dirty mut = changed | |
| 273 | ||
| 274 | while dirty.count > 0 do | |
| 275 | let next = Collections.SET[Function]() | |
| 276 | ||
| 277 | for target in dirty do | |
| 278 | let dependants = self.dependants.dependants_of(target) | |
| 279 | ||
| 280 | if !dependants? then | |
| 281 | continue | |
| 282 | fi | |
| 283 | ||
| 284 | for function in dependants do | |
| 285 | if unbounded.contains(function) then | |
| 286 | continue | |
| 287 | fi | |
| 288 | ||
| 289 | let before = sets[function].count | |
| 290 | ||
| 291 | if _absorb_target(function, target, sets, unbounded, trust_imports) \/ sets[function].count != before then | |
| 292 | next.add(function) | |
| 293 | fi | |
| 294 | od | |
| 295 | od | |
| 296 | ||
| 297 | dirty = next | |
| 298 | od | |
| 299 | ||
| 300 | return (sets = sets, unbounded = unbounded) | |
| 301 | si | |
| 302 | ||
| 303 | // Pull every dispatch target's writes into `function`'s set. | |
| 304 | // Returns whether the function became unbounded. | |
| 305 | _absorb( | |
| 306 | function: Function, | |
| 307 | sets: Collections.MutableMap[Function, Collections.SET[Symbol]], | |
| 308 | unbounded: Collections.SET[Function], | |
| 309 | trust_imports: bool | |
| 310 | ) -> bool is | |
| 311 | // Once unbounded, nothing more can change: queries answer | |
| 312 | // conservatively without reading the member set, and | |
| 313 | // callers read only the unbounded flag. | |
| 314 | if unbounded.contains(function) then | |
| 315 | return false | |
| 316 | fi | |
| 317 | ||
| 318 | let became mut = false | |
| 319 | ||
| 320 | for callee in _facts[function].callees do | |
| 321 | if _absorb_target(function, callee, sets, unbounded, trust_imports) then | |
| 322 | became = true | |
| 323 | fi | |
| 324 | od | |
| 325 | ||
| 326 | for callee in _facts[function].construction_callees do | |
| 327 | if _absorb_target(function, callee, sets, unbounded, trust_imports) then | |
| 328 | became = true | |
| 329 | fi | |
| 330 | od | |
| 331 | ||
| 332 | // Effect-polymorphic absorption: an invoked function-typed | |
| 333 | // parameter is bounded by the values recorded flowing in | |
| 334 | // at the function's call sites; a value nothing could name | |
| 335 | // makes the invocation unboundable after all. | |
| 336 | if param_invokers.contains(function) then | |
| 337 | if EFFECT_FACTS.passed_opaque.contains(function) then | |
| 338 | if !unbounded.contains(function) then | |
| 339 | unbounded.add(function) | |
| 340 | became = true | |
| 341 | fi | |
| 342 | else | |
| 343 | let passed = EFFECT_FACTS.passed_functions_for(function) | |
| 344 | ||
| 345 | if passed? then | |
| 346 | for value in passed do | |
| 347 | if _absorb_target(function, value, sets, unbounded, trust_imports) then | |
| 348 | became = true | |
| 349 | fi | |
| 350 | od | |
| 351 | fi | |
| 352 | fi | |
| 353 | fi | |
| 354 | ||
| 355 | let overriders = function.overriders | |
| 356 | ||
| 357 | if overriders? then | |
| 358 | for overrider in overriders do | |
| 359 | if !isa Function(overrider) then | |
| 360 | if !unbounded.contains(function) then | |
| 361 | unbounded.add(function) | |
| 362 | became = true | |
| 363 | fi | |
| 364 | ||
| 365 | continue | |
| 366 | fi | |
| 367 | ||
| 368 | if _absorb_target(function, cast Function(overrider), sets, unbounded, trust_imports) then | |
| 369 | became = true | |
| 370 | fi | |
| 371 | od | |
| 372 | fi | |
| 373 | ||
| 374 | return became | |
| 375 | si | |
| 376 | ||
| 377 | _absorb_target( | |
| 378 | function: Function, | |
| 379 | target: Function, | |
| 380 | sets: Collections.MutableMap[Function, Collections.SET[Symbol]], | |
| 381 | unbounded: Collections.SET[Function], | |
| 382 | trust_imports: bool | |
| 383 | ) -> bool is | |
| 384 | if target.is_declared_pure then | |
| 385 | return false | |
| 386 | fi | |
| 387 | ||
| 388 | if !sets.contains_key(target) then | |
| 389 | // not walked here: a trusted store-free import writes | |
| 390 | // nothing, a receiver-interior mutator writes only its | |
| 391 | // own receiver's internal state - never a ghul member - | |
| 392 | // and anything else could write anything | |
| 393 | if | |
| 394 | trust_imports \/ | |
| 395 | STORE_FREE_IMPORTS.is_store_free(target) \/ | |
| 396 | target.writes_only_receiver_interior | |
| 397 | then | |
| 398 | return false | |
| 399 | fi | |
| 400 | ||
| 401 | unbounded.add(function) | |
| 402 | return true | |
| 403 | fi | |
| 404 | ||
| 405 | if unbounded.contains(target) then | |
| 406 | // the caller's members no longer matter either, so | |
| 407 | // skip the union | |
| 408 | unbounded.add(function) | |
| 409 | return true | |
| 410 | fi | |
| 411 | ||
| 412 | let function_set = sets[function] | |
| 413 | ||
| 414 | for member in sets[target] do | |
| 415 | function_set.add(member) | |
| 416 | od | |
| 417 | ||
| 418 | return false | |
| 419 | si | |
| 420 | ||
| 421 | // The member-keyed may-null relation: which members each | |
| 422 | // function (or anything it dispatches to) may assign a | |
| 423 | // possibly-absent value. Open dispatch makes the set | |
| 424 | // unboundable. | |
| 425 | // | |
| 426 | // `trust_imports` selects the import model. Trusted, an | |
| 427 | // unwalked callee contributes nothing, on the argument that | |
| 428 | // imported code cannot assign a ghul member except by | |
| 429 | // re-entering ghul code - an argument with a known leak | |
| 430 | // (delegate re-entry), so it is a measurement configuration | |
| 431 | // only. Untrusted - the production setting - an unwalked | |
| 432 | // callee that is not declared pure and not on the curated | |
| 433 | // store-free whitelist makes the caller unboundable. | |
| 434 | may_null_sets(close_open: bool, trust_imports: bool) -> ( | |
| 435 | sets: Collections.MutableMap[Function, Collections.SET[Symbol]], | |
| 436 | unbounded: Collections.SET[Function] | |
| 437 | ) is | |
| 438 | let sets = Collections.MAP[Function, Collections.SET[Symbol]]() | |
| 439 | let unbounded = Collections.SET[Function]() | |
| 440 | let shadow = STORE_FREE_FIXPOINT() | |
| 441 | ||
| 442 | let previous = _previous | |
| 443 | ||
| 444 | for function in _facts.keys do | |
| 445 | if !_is_derived(function) /\ previous? /\ previous.null_sets.contains_key(function) then | |
| 446 | sets[function] = previous.null_sets[function] | |
| 447 | ||
| 448 | if previous.null_unbounded.contains(function) then | |
| 449 | unbounded.add(function) | |
| 450 | fi | |
| 451 | ||
| 452 | continue | |
| 453 | fi | |
| 454 | ||
| 455 | let set = Collections.SET[Symbol]() | |
| 456 | let record = EFFECT_FACTS.record_for(function) | |
| 457 | ||
| 458 | if record? then | |
| 459 | for m in record.nulling_writes do | |
| 460 | set.add(m) | |
| 461 | od | |
| 462 | ||
| 463 | // an unbounded write could write null just as well | |
| 464 | // as it could write anything else, so the nulling | |
| 465 | // set is only a bound where the write set is | |
| 466 | if record.nulling_unbounded \/ record.writes_unbounded then | |
| 467 | unbounded.add(function) | |
| 468 | fi | |
| 469 | else | |
| 470 | unbounded.add(function) | |
| 471 | fi | |
| 472 | ||
| 473 | if !close_open /\ shadow.is_openly_dispatchable(function) then | |
| 474 | unbounded.add(function) | |
| 475 | fi | |
| 476 | ||
| 477 | sets[function] = set | |
| 478 | od | |
| 479 | ||
| 480 | let changed = Collections.SET[Function]() | |
| 481 | ||
| 482 | for function in _derived do | |
| 483 | if _absorb_nulling(function, sets, unbounded, trust_imports) then | |
| 484 | changed.add(function) | |
| 485 | fi | |
| 486 | od | |
| 487 | ||
| 488 | let dirty mut = changed | |
| 489 | ||
| 490 | while dirty.count > 0 do | |
| 491 | let next = Collections.SET[Function]() | |
| 492 | ||
| 493 | for target in dirty do | |
| 494 | let dependants = self.dependants.dependants_of(target) | |
| 495 | ||
| 496 | if !dependants? then | |
| 497 | continue | |
| 498 | fi | |
| 499 | ||
| 500 | for function in dependants do | |
| 501 | if unbounded.contains(function) then | |
| 502 | continue | |
| 503 | fi | |
| 504 | ||
| 505 | if _absorb_nulling_target(function, target, sets, unbounded, trust_imports) then | |
| 506 | next.add(function) | |
| 507 | fi | |
| 508 | od | |
| 509 | od | |
| 510 | ||
| 511 | dirty = next | |
| 512 | od | |
| 513 | ||
| 514 | return (sets = sets, unbounded = unbounded) | |
| 515 | si | |
| 516 | ||
| 517 | _absorb_nulling( | |
| 518 | function: Function, | |
| 519 | sets: Collections.MutableMap[Function, Collections.SET[Symbol]], | |
| 520 | unbounded: Collections.SET[Function], | |
| 521 | trust_imports: bool | |
| 522 | ) -> bool is | |
| 523 | // Once unbounded, nothing more can change - see _absorb. | |
| 524 | if unbounded.contains(function) then | |
| 525 | return false | |
| 526 | fi | |
| 527 | ||
| 528 | let became mut = false | |
| 529 | ||
| 530 | for callee in _facts[function].callees do | |
| 531 | if _absorb_nulling_target(function, callee, sets, unbounded, trust_imports) then | |
| 532 | became = true | |
| 533 | fi | |
| 534 | od | |
| 535 | ||
| 536 | for callee in _facts[function].construction_callees do | |
| 537 | if _absorb_nulling_target(function, callee, sets, unbounded, trust_imports) then | |
| 538 | became = true | |
| 539 | fi | |
| 540 | od | |
| 541 | ||
| 542 | if param_invokers.contains(function) then | |
| 543 | if EFFECT_FACTS.passed_opaque.contains(function) then | |
| 544 | if !unbounded.contains(function) then | |
| 545 | unbounded.add(function) | |
| 546 | became = true | |
| 547 | fi | |
| 548 | else | |
| 549 | let passed = EFFECT_FACTS.passed_functions_for(function) | |
| 550 | ||
| 551 | if passed? then | |
| 552 | for value in passed do | |
| 553 | if _absorb_nulling_target(function, value, sets, unbounded, trust_imports) then | |
| 554 | became = true | |
| 555 | fi | |
| 556 | od | |
| 557 | fi | |
| 558 | fi | |
| 559 | fi | |
| 560 | ||
| 561 | let overriders = function.overriders | |
| 562 | ||
| 563 | if overriders? then | |
| 564 | for overrider in overriders do | |
| 565 | if !isa Function(overrider) then | |
| 566 | if !unbounded.contains(function) then | |
| 567 | unbounded.add(function) | |
| 568 | became = true | |
| 569 | fi | |
| 570 | ||
| 571 | continue | |
| 572 | fi | |
| 573 | ||
| 574 | if _absorb_nulling_target(function, cast Function(overrider), sets, unbounded, trust_imports) then | |
| 575 | became = true | |
| 576 | fi | |
| 577 | od | |
| 578 | fi | |
| 579 | ||
| 580 | return became | |
| 581 | si | |
| 582 | ||
| 583 | _absorb_nulling_target( | |
| 584 | function: Function, | |
| 585 | target: Function, | |
| 586 | sets: Collections.MutableMap[Function, Collections.SET[Symbol]], | |
| 587 | unbounded: Collections.SET[Function], | |
| 588 | trust_imports: bool | |
| 589 | ) -> bool is | |
| 590 | if target.is_declared_pure then | |
| 591 | return false | |
| 592 | fi | |
| 593 | ||
| 594 | if !sets.contains_key(target) then | |
| 595 | // Same tiers as _absorb_target; a receiver-interior | |
| 596 | // mutator cannot assign a ghul member at all, null or | |
| 597 | // otherwise. | |
| 598 | if | |
| 599 | trust_imports \/ | |
| 600 | STORE_FREE_IMPORTS.is_store_free(target) \/ | |
| 601 | target.writes_only_receiver_interior | |
| 602 | then | |
| 603 | return false | |
| 604 | fi | |
| 605 | ||
| 606 | unbounded.add(function) | |
| 607 | return true | |
| 608 | fi | |
| 609 | ||
| 610 | if unbounded.contains(target) then | |
| 611 | // the caller's members no longer matter either, so | |
| 612 | // skip the union | |
| 613 | unbounded.add(function) | |
| 614 | return true | |
| 615 | fi | |
| 616 | ||
| 617 | let became mut = false | |
| 618 | let function_set = sets[function] | |
| 619 | ||
| 620 | for m in sets[target] do | |
| 621 | if !function_set.contains(m) then | |
| 622 | function_set.add(m) | |
| 623 | became = true | |
| 624 | fi | |
| 625 | od | |
| 626 | ||
| 627 | return became | |
| 628 | si | |
| 629 | ||
| 630 | // The member read closure: which members each function - or | |
| 631 | // anything it can dispatch to or invoke - may read, plus | |
| 632 | // whether it may read or write collection/array elements. | |
| 633 | // Consumed by the crossing discharge for facts read through a | |
| 634 | // getter: a crossing callee whose write set is disjoint from | |
| 635 | // the getter's read closure provably leaves the getter's | |
| 636 | // answer alone. An unwalked callee makes the reads | |
| 637 | // unboundable, except the curated import tiers: a store-free | |
| 638 | // import reads only its receiver's interior, and a | |
| 639 | // receiver-interior mutator additionally writes it. | |
| 640 | read_sets() -> ( | |
| 641 | sets: Collections.MutableMap[Function, Collections.SET[Symbol]], | |
| 642 | unbounded: Collections.SET[Function], | |
| 643 | reads_elements: Collections.SET[Function], | |
| 644 | writes_elements: Collections.SET[Function] | |
| 645 | ) is | |
| 646 | let sets = Collections.MAP[Function, Collections.SET[Symbol]]() | |
| 647 | let unbounded = Collections.SET[Function]() | |
| 648 | let reads_elements = Collections.SET[Function]() | |
| 649 | let writes_elements = Collections.SET[Function]() | |
| 650 | let shadow = STORE_FREE_FIXPOINT() | |
| 651 | ||
| 652 | let previous = _previous | |
| 653 | ||
| 654 | for function in _facts.keys do | |
| 655 | if !_is_derived(function) /\ previous? /\ previous.read_sets.contains_key(function) then | |
| 656 | sets[function] = previous.read_sets[function] | |
| 657 | ||
| 658 | if previous.read_unbounded.contains(function) then | |
| 659 | unbounded.add(function) | |
| 660 | fi | |
| 661 | ||
| 662 | if previous.reads_elements.contains(function) then | |
| 663 | reads_elements.add(function) | |
| 664 | fi | |
| 665 | ||
| 666 | if previous.writes_elements.contains(function) then | |
| 667 | writes_elements.add(function) | |
| 668 | fi | |
| 669 | ||
| 670 | continue | |
| 671 | fi | |
| 672 | ||
| 673 | let set = Collections.SET[Symbol]() | |
| 674 | let record = EFFECT_FACTS.record_for(function) | |
| 675 | ||
| 676 | if record? then | |
| 677 | for m in record.reads do | |
| 678 | set.add(m) | |
| 679 | od | |
| 680 | ||
| 681 | if record.reads_elements then | |
| 682 | reads_elements.add(function) | |
| 683 | fi | |
| 684 | ||
| 685 | if record.writes_elements then | |
| 686 | writes_elements.add(function) | |
| 687 | fi | |
| 688 | ||
| 689 | if record.own_unbounded \/ record.writes_unbounded then | |
| 690 | unbounded.add(function) | |
| 691 | fi | |
| 692 | else | |
| 693 | unbounded.add(function) | |
| 694 | fi | |
| 695 | ||
| 696 | if shadow.is_openly_dispatchable(function) then | |
| 697 | unbounded.add(function) | |
| 698 | writes_elements.add(function) | |
| 699 | fi | |
| 700 | ||
| 701 | sets[function] = set | |
| 702 | od | |
| 703 | ||
| 704 | let changed = Collections.SET[Function]() | |
| 705 | ||
| 706 | for function in _derived do | |
| 707 | if _absorb_reads(function, sets, unbounded, reads_elements, writes_elements) then | |
| 708 | changed.add(function) | |
| 709 | fi | |
| 710 | od | |
| 711 | ||
| 712 | let dirty mut = changed | |
| 713 | ||
| 714 | // An unbounded row is not skipped here: the element flags | |
| 715 | // propagate through it regardless of its closure. | |
| 716 | while dirty.count > 0 do | |
| 717 | let next = Collections.SET[Function]() | |
| 718 | ||
| 719 | for target in dirty do | |
| 720 | let dependants = self.dependants.dependants_of(target) | |
| 721 | ||
| 722 | if !dependants? then | |
| 723 | continue | |
| 724 | fi | |
| 725 | ||
| 726 | for function in dependants do | |
| 727 | if _absorb_reads_target(function, target, sets, unbounded, reads_elements, writes_elements) then | |
| 728 | next.add(function) | |
| 729 | fi | |
| 730 | od | |
| 731 | od | |
| 732 | ||
| 733 | dirty = next | |
| 734 | od | |
| 735 | ||
| 736 | return (sets = sets, unbounded = unbounded, reads_elements = reads_elements, writes_elements = writes_elements) | |
| 737 | si | |
| 738 | ||
| 739 | _absorb_reads( | |
| 740 | function: Function, | |
| 741 | sets: Collections.MutableMap[Function, Collections.SET[Symbol]], | |
| 742 | unbounded: Collections.SET[Function], | |
| 743 | reads_elements: Collections.SET[Function], | |
| 744 | writes_elements: Collections.SET[Function] | |
| 745 | ) -> bool is | |
| 746 | let became mut = false | |
| 747 | ||
| 748 | for callee in _facts[function].callees do | |
| 749 | if _absorb_reads_target(function, callee, sets, unbounded, reads_elements, writes_elements) then | |
| 750 | became = true | |
| 751 | fi | |
| 752 | od | |
| 753 | ||
| 754 | for callee in _facts[function].construction_callees do | |
| 755 | if _absorb_reads_target(function, callee, sets, unbounded, reads_elements, writes_elements) then | |
| 756 | became = true | |
| 757 | fi | |
| 758 | od | |
| 759 | ||
| 760 | if param_invokers.contains(function) then | |
| 761 | if EFFECT_FACTS.passed_opaque.contains(function) then | |
| 762 | became = _add_once(unbounded, function) \/ became | |
| 763 | became = _add_once(writes_elements, function) \/ became | |
| 764 | else | |
| 765 | let passed = EFFECT_FACTS.passed_functions_for(function) | |
| 766 | ||
| 767 | if passed? then | |
| 768 | for value in passed do | |
| 769 | if _absorb_reads_target(function, value, sets, unbounded, reads_elements, writes_elements) then | |
| 770 | became = true | |
| 771 | fi | |
| 772 | od | |
| 773 | fi | |
| 774 | fi | |
| 775 | fi | |
| 776 | ||
| 777 | let overriders = function.overriders | |
| 778 | ||
| 779 | if overriders? then | |
| 780 | for overrider in overriders do | |
| 781 | if !isa Function(overrider) then | |
| 782 | became = _add_once(unbounded, function) \/ became | |
| 783 | became = _add_once(writes_elements, function) \/ became | |
| 784 | ||
| 785 | continue | |
| 786 | fi | |
| 787 | ||
| 788 | if _absorb_reads_target(function, cast Function(overrider), sets, unbounded, reads_elements, writes_elements) then | |
| 789 | became = true | |
| 790 | fi | |
| 791 | od | |
| 792 | fi | |
| 793 | ||
| 794 | return became | |
| 795 | si | |
| 796 | ||
| 797 | _absorb_reads_target( | |
| 798 | function: Function, | |
| 799 | target: Function, | |
| 800 | sets: Collections.MutableMap[Function, Collections.SET[Symbol]], | |
| 801 | unbounded: Collections.SET[Function], | |
| 802 | reads_elements: Collections.SET[Function], | |
| 803 | writes_elements: Collections.SET[Function] | |
| 804 | ) -> bool is | |
| 805 | let became mut = false | |
| 806 | ||
| 807 | if !sets.contains_key(target) then | |
| 808 | // not walked here. A curated store-free import reads | |
| 809 | // only its receiver's interior; a receiver-interior | |
| 810 | // mutator also writes it. A declared-pure import | |
| 811 | // stores nothing but can read anything; everything | |
| 812 | // else could do either. | |
| 813 | // Declared purity is checked before the | |
| 814 | // receiver-interior tier: `pure` implies the | |
| 815 | // store-free bit, which the receiver-interior test | |
| 816 | // accepts, but a pure function promises nothing | |
| 817 | // about what it reads. | |
| 818 | if STORE_FREE_IMPORTS.is_store_free(target) then | |
| 819 | became = _add_once(reads_elements, function) | |
| 820 | elif target.is_declared_pure then | |
| 821 | became = _add_once(unbounded, function) | |
| 822 | elif target.writes_only_receiver_interior then | |
| 823 | became = _add_once(reads_elements, function) \/ became | |
| 824 | became = _add_once(writes_elements, function) \/ became | |
| 825 | else | |
| 826 | became = _add_once(unbounded, function) \/ became | |
| 827 | became = _add_once(writes_elements, function) \/ became | |
| 828 | fi | |
| 829 | ||
| 830 | return became | |
| 831 | fi | |
| 832 | ||
| 833 | if unbounded.contains(target) then | |
| 834 | became = _add_once(unbounded, function) \/ became | |
| 835 | elif !unbounded.contains(function) then | |
| 836 | // the member union matters only while both closures | |
| 837 | // are still bounded - an unbounded closure answers | |
| 838 | // null whatever its set holds. The element flags | |
| 839 | // below still propagate regardless, because | |
| 840 | // may_write_elements consults them independently of | |
| 841 | // the read closure. | |
| 842 | let function_set = sets[function] | |
| 843 | ||
| 844 | for m in sets[target] do | |
| 845 | if !function_set.contains(m) then | |
| 846 | function_set.add(m) | |
| 847 | became = true | |
| 848 | fi | |
| 849 | od | |
| 850 | fi | |
| 851 | ||
| 852 | if reads_elements.contains(target) then | |
| 853 | became = _add_once(reads_elements, function) \/ became | |
| 854 | fi | |
| 855 | ||
| 856 | if writes_elements.contains(target) then | |
| 857 | became = _add_once(writes_elements, function) \/ became | |
| 858 | fi | |
| 859 | ||
| 860 | return became | |
| 861 | si | |
| 862 | ||
| 863 | _add_once(set: Collections.SET[Function], function: Function) -> bool static is | |
| 864 | if set.contains(function) then | |
| 865 | return false | |
| 866 | fi | |
| 867 | ||
| 868 | set.add(function) | |
| 869 | return true | |
| 870 | si | |
| 871 | si | |
| 872 | si |