Appearance
| 1 | namespace Syntax.Process is | |
| 2 | use System.Exception | |
| 3 | ||
| 4 | use Ghul.Pipes | |
| 5 | ||
| 6 | use Logging | |
| 7 | use Trees | |
| 8 | ||
| 9 | use Semantic.Types.Type | |
| 10 | ||
| 11 | use Function = Semantic.Symbols.Function | |
| 12 | use Symbol = Semantic.Symbols.Symbol | |
| 13 | ||
| 14 | // Per-node classification: visit_default, resolved-value and fused-for classification, | |
| 15 | // study notes and the disqualify family. | |
| 16 | partial INFER_STORE_FREE is | |
| 17 | // ==== default: any node kind without an explicit override ==== | |
| 18 | ||
| 19 | visit_default(node: Trees.Node) is | |
| 20 | if _resolved_mode /\ _classify_resolved(node) then | |
| 21 | return | |
| 22 | fi | |
| 23 | ||
| 24 | _disqualify_because("unaudited-node:{node.get_type().full_name}") | |
| 25 | si | |
| 26 | ||
| 27 | // Once compile-expressions has run, the node kinds | |
| 28 | // this walk never modelled carry enough resolved state to be | |
| 29 | // classified: a `for` names the three iterator members it calls, | |
| 30 | // and every other expression carries the value it compiled to, | |
| 31 | // whose callee is a bounded edge like any other. Returns whether | |
| 32 | // the node was classified; false falls through to disqualifying | |
| 33 | // it as before. | |
| 34 | _classify_resolved(node: Trees.Node) -> bool is | |
| 35 | // an element read cannot be pinned to a member symbol; | |
| 36 | // the read-closure records it as its own dimension | |
| 37 | if _current_record? then | |
| 38 | if isa Trees.Expressions.INDEX(node) then | |
| 39 | _current_record.reads_elements = true | |
| 40 | elif isa Trees.Expressions.AMBIGUOUS_EXPRESSION(node) then | |
| 41 | if (cast Trees.Expressions.AMBIGUOUS_EXPRESSION(node)).result == Trees.Expressions.AmbiguousExpressionResult.INDEX then | |
| 42 | _current_record.reads_elements = true | |
| 43 | fi | |
| 44 | fi | |
| 45 | fi | |
| 46 | ||
| 47 | if let carrier: Trees.IteratorCarrier = node then | |
| 48 | if let `for: Statements.FOR = node /\ `for.fusion? then | |
| 49 | return _classify_fused_for(`for.fusion) | |
| 50 | fi | |
| 51 | ||
| 52 | // read_iterator is legitimately null when the iterated | |
| 53 | // expression is already an iterator - the emitter | |
| 54 | // drives move_next/current on the value directly | |
| 55 | let move_next = carrier.move_next | |
| 56 | let read_current = carrier.read_current | |
| 57 | ||
| 58 | if !move_next? \/ !read_current? then | |
| 59 | let expression = carrier.iterated | |
| 60 | ||
| 61 | let detail = | |
| 62 | if !expression? then | |
| 63 | "no-expression" | |
| 64 | elif !expression.value? then | |
| 65 | "no-value" | |
| 66 | elif !expression.value.type? then | |
| 67 | "no-type" | |
| 68 | else | |
| 69 | "{expression.value.type}" | |
| 70 | fi | |
| 71 | ||
| 72 | _disqualify_because("iterator-unresolved:{detail}") | |
| 73 | return true | |
| 74 | fi | |
| 75 | ||
| 76 | if carrier.read_iterator? then | |
| 77 | _add_callee(carrier.read_iterator) | |
| 78 | fi | |
| 79 | ||
| 80 | _add_callee(move_next) | |
| 81 | _add_callee(read_current) | |
| 82 | ||
| 83 | return true | |
| 84 | fi | |
| 85 | ||
| 86 | if let expression: Trees.Expressions.Expression = node then | |
| 87 | let value = expression.value | |
| 88 | ||
| 89 | if !value? then | |
| 90 | return false | |
| 91 | fi | |
| 92 | ||
| 93 | return _classify_resolved_value(value) | |
| 94 | fi | |
| 95 | ||
| 96 | return false | |
| 97 | si | |
| 98 | ||
| 99 | // A fused loop never builds the pipe objects: it iterates the | |
| 100 | // pinned built-in source directly and runs each map/filter | |
| 101 | // stage's lambda body inline, so the loop's effects are the | |
| 102 | // stage bodies' effects. The lambda literals were skipped by | |
| 103 | // the ordinary walk (creating a closure is effect-free), so | |
| 104 | // they are walked here, attributed to the enclosing function | |
| 105 | // exactly as the fused lowering executes them. A stage fed an | |
| 106 | // arbitrary delegate value rather than a literal is invoked | |
| 107 | // per element with no bounded callee, so it stays unbounded | |
| 108 | // unless the value's type is a pure function type. | |
| 109 | _classify_fused_for(fusion: PIPE_FUSION) -> bool is | |
| 110 | for stage in fusion.stages_outermost_first do | |
| 111 | if stage.is_countdown \/ stage.is_index then | |
| 112 | continue | |
| 113 | fi | |
| 114 | ||
| 115 | let argument = stage.argument | |
| 116 | ||
| 117 | if !argument? then | |
| 118 | continue | |
| 119 | fi | |
| 120 | ||
| 121 | if let literal: Trees.Expressions.FUNCTION = argument then | |
| 122 | literal.body.walk(self) | |
| 123 | elif !(argument.value? /\ argument.value.type? /\ argument.value.type.is_pure_function) then | |
| 124 | _disqualify_because("fused-stage-delegate") | |
| 125 | return true | |
| 126 | fi | |
| 127 | od | |
| 128 | ||
| 129 | return true | |
| 130 | si | |
| 131 | ||
| 132 | _classify_resolved_value(value: IR.Values.Value) -> bool is | |
| 133 | if let view: IR.Values.NARROW_VIEW = value then | |
| 134 | return _classify_resolved_value(view.underlying) | |
| 135 | fi | |
| 136 | ||
| 137 | // A scalar constructor is a cast, and a cast is not a call. | |
| 138 | if isa IR.Values.SCALAR_CONVERSION(value) then | |
| 139 | return true | |
| 140 | fi | |
| 141 | ||
| 142 | if let call: IR.Values.Call.INSTANCE = value then | |
| 143 | _note_overload_site(call.function, call.from, call.arguments) | |
| 144 | _add_callee(call.function) | |
| 145 | _study_note_call_arguments(call.function, call.arguments) | |
| 146 | return true | |
| 147 | fi | |
| 148 | ||
| 149 | if let call: IR.Values.Call.STATIC = value then | |
| 150 | _note_overload_site(call.function, null, call.arguments) | |
| 151 | _add_callee(call.function) | |
| 152 | _study_note_call_arguments(call.function, call.arguments) | |
| 153 | return true | |
| 154 | fi | |
| 155 | ||
| 156 | if let call: IR.Values.Call.GLOBAL = value then | |
| 157 | _note_overload_site(call.function, null, call.arguments) | |
| 158 | _add_callee(call.function) | |
| 159 | _study_note_call_arguments(call.function, call.arguments) | |
| 160 | return true | |
| 161 | fi | |
| 162 | ||
| 163 | if let call: IR.Values.Call.STRUCT = value then | |
| 164 | _note_overload_site(call.function, call.from, call.arguments) | |
| 165 | _add_callee(call.function) | |
| 166 | _study_note_call_arguments(call.function, call.arguments) | |
| 167 | return true | |
| 168 | fi | |
| 169 | ||
| 170 | if let construction: IR.Values.NEW = value then | |
| 171 | // constructing a reflected exception writes only the | |
| 172 | // fresh object — the same trust the declared-types | |
| 173 | // classification extends, restated here so the edge | |
| 174 | // to the unwalked BCL constructor does not poison | |
| 175 | if !_is_store_free_construction(cast Symbol?(construction.constructor.owner)) then | |
| 176 | _add_construction_callee(construction.constructor) | |
| 177 | fi | |
| 178 | ||
| 179 | _study_note_call_arguments(construction.constructor, construction.arguments) | |
| 180 | return true | |
| 181 | fi | |
| 182 | ||
| 183 | // Invoking a function value: bounded when the value names | |
| 184 | // its function, effect-polymorphic when it is one of the | |
| 185 | // enclosing function's own parameters, unboundable | |
| 186 | // otherwise. | |
| 187 | if let call: IR.Values.Call.CLOSURE = value then | |
| 188 | if !call.is_state_changing_call then | |
| 189 | return true | |
| 190 | fi | |
| 191 | ||
| 192 | let fn = function_value_of(call.from) | |
| 193 | ||
| 194 | if fn? then | |
| 195 | _add_callee(fn) | |
| 196 | _study_note_call_arguments(fn, call.arguments) | |
| 197 | return true | |
| 198 | fi | |
| 199 | ||
| 200 | if isa IR.Values.Load.LOCAL_ARGUMENT(call.from) then | |
| 201 | if _current_record? then | |
| 202 | _current_record.invokes_function_param = true | |
| 203 | fi | |
| 204 | ||
| 205 | return true | |
| 206 | fi | |
| 207 | ||
| 208 | return false | |
| 209 | fi | |
| 210 | ||
| 211 | // not a call at all: reading a value writes nothing, and any | |
| 212 | // sub-expression is classified as the walk reaches it | |
| 213 | return !value.is_state_changing_call | |
| 214 | si | |
| 215 | ||
| 216 | function_values: FUNCTION_VALUES public | |
| 217 | ||
| 218 | // The resolver from compiled values to the functions they | |
| 219 | // denote, including the immutable-local record this walk | |
| 220 | // populates. Shared with the pure-slot judge. | |
| 221 | ||
| 222 | function_value_of(value: IR.Values.Value?) -> Function? => | |
| 223 | function_values.function_value_of(value) | |
| 224 | ||
| 225 | // Record which function values flow into a callee's | |
| 226 | // function-typed parameters. A named value joins the callee's | |
| 227 | // passed set; the caller's own parameter forwarded onward is | |
| 228 | // accounted at the caller's own call sites instead; anything | |
| 229 | // else function-typed makes the callee's parameter values | |
| 230 | // unknowable - unless its type is pure, which admits only | |
| 231 | // store-free values whoever invokes it. | |
| 232 | _study_note_call_arguments(callee: Function?, arguments: Collections.List[IR.Values.Value]) is | |
| 233 | if !callee? then | |
| 234 | return | |
| 235 | fi | |
| 236 | ||
| 237 | let from_file = if let current = _current_function then current.location.file_name else "" fi | |
| 238 | ||
| 239 | for argument in arguments do | |
| 240 | let fn = function_value_of(argument) | |
| 241 | ||
| 242 | if fn? then | |
| 243 | EFFECT_FACTS.note_passed_function(callee, fn, from_file) | |
| 244 | continue | |
| 245 | fi | |
| 246 | ||
| 247 | if isa IR.Values.Load.LOCAL_ARGUMENT(argument) then | |
| 248 | let argument_type = argument.type | |
| 249 | ||
| 250 | if argument_type? /\ argument_type.is_function /\ !argument_type.is_pure_function then | |
| 251 | if _current_record? then | |
| 252 | let root = cast Function?(callee.root_specialized_from) | |
| 253 | ||
| 254 | if root? then | |
| 255 | _current_record.forwards_param_to.add(root) | |
| 256 | fi | |
| 257 | fi | |
| 258 | fi | |
| 259 | ||
| 260 | continue | |
| 261 | fi | |
| 262 | ||
| 263 | let argument_type = argument.type | |
| 264 | ||
| 265 | if argument_type? /\ argument_type.is_function /\ !argument_type.is_pure_function then | |
| 266 | EFFECT_FACTS.note_passed_opaque(callee, from_file) | |
| 267 | NARROWING_STUDY.note_opaque_shape("{argument.get_type().name} -> {callee.name}") | |
| 268 | fi | |
| 269 | od | |
| 270 | si | |
| 271 | ||
| 272 | // `_disqualify` with the reason recorded for the study, so the | |
| 273 | // report can say what the walk actually gives up on. First | |
| 274 | // reason wins: it is the one that made the function unbounded. | |
| 275 | _disqualify_because(reason: string) is | |
| 276 | ||
| 277 | if _current? /\ _current_record? /\ _current_record.unbounded_reason =~ "" then | |
| 278 | _current_record.unbounded_reason = reason | |
| 279 | fi | |
| 280 | ||
| 281 | _disqualify() | |
| 282 | si | |
| 283 | ||
| 284 | _disqualify() is | |
| 285 | if !_current? then | |
| 286 | return | |
| 287 | fi | |
| 288 | ||
| 289 | _current.is_disqualified = true | |
| 290 | _current.is_construction_disqualified = true | |
| 291 | ||
| 292 | if _current_record? then | |
| 293 | _current_record.own_unbounded = true | |
| 294 | ||
| 295 | // whatever the walk could not bound could write | |
| 296 | // anything, so the write set stops being a bound too | |
| 297 | _current_record.writes_unbounded = true | |
| 298 | fi | |
| 299 | si | |
| 300 | ||
| 301 | // A captured-local store: not store-free - the declaring | |
| 302 | // scope sees the write - but the write set stays bounded, | |
| 303 | // because the store targets exactly the one local symbol the | |
| 304 | // study path records. | |
| 305 | _disqualify_captured_store() is | |
| 306 | if !_current? then | |
| 307 | return | |
| 308 | fi | |
| 309 | ||
| 310 | _current.is_disqualified = true | |
| 311 | _current.is_construction_disqualified = true | |
| 312 | si | |
| 313 | ||
| 314 | // The subset of `_disqualify` where the walk saw a write to a | |
| 315 | // pre-existing heap slot rather than merely failing to bound | |
| 316 | // something. Behaves identically; only the study distinguishes | |
| 317 | // them. | |
| 318 | _disqualify_store() is | |
| 319 | if !_current? then | |
| 320 | return | |
| 321 | fi | |
| 322 | ||
| 323 | _current.is_disqualified = true | |
| 324 | _current.is_construction_disqualified = true | |
| 325 | ||
| 326 | if _current_record? then | |
| 327 | _current_record.own_stores = true | |
| 328 | fi | |
| 329 | si | |
| 330 | ||
| 331 | // A store the strict analysis rejects but a construction does | |
| 332 | // not: writing the receiver's own instance state touches only | |
| 333 | // the fresh object a `NEW` is building. | |
| 334 | _disqualify_strict_only() is | |
| 335 | if !_current? then | |
| 336 | return | |
| 337 | fi | |
| 338 | ||
| 339 | _current.is_disqualified = true | |
| 340 | ||
| 341 | if _current_record? then | |
| 342 | _current_record.own_stores = true | |
| 343 | fi | |
| 344 | si | |
| 345 | ||
| 346 | ||
| 347 | _in_constructor: bool => | |
| 348 | _current_function? /\ _current_function.is_constructor | |
| 349 | ||
| 350 | // A `self.field` target naming an instance field of the | |
| 351 | // receiver. `self` is the only receiver the construction bit | |
| 352 | // says anything about; a member on any other receiver stays a | |
| 353 | // heap store. | |
| 354 | _writes_own_instance_field_member(target: Trees.Expressions.Expression?) -> bool is | |
| 355 | if !target? \/ !isa Trees.Expressions.MEMBER(target) then | |
| 356 | return false | |
| 357 | fi | |
| 358 | ||
| 359 | let member = cast Trees.Expressions.MEMBER(target) | |
| 360 | ||
| 361 | if !isa Trees.Expressions.SELF(member.left) then | |
| 362 | return false | |
| 363 | fi | |
| 364 | ||
| 365 | let context = current_instance_context | |
| 366 | ||
| 367 | if !context? then | |
| 368 | return false | |
| 369 | fi | |
| 370 | ||
| 371 | let field_symbol = context.find_member(member.identifier.name) | |
| 372 | ||
| 373 | return field_symbol? /\ field_symbol.is_field /\ field_symbol.is_instance | |
| 374 | si | |
| 375 | ||
| 376 | // The assign accessor behind a `self.property` target on the | |
| 377 | // type under construction. Writing a property runs its | |
| 378 | // accessor rather than storing directly, so the write is only | |
| 379 | // as safe as that accessor is — an auto-property's accessor | |
| 380 | // writes nothing but its own backing field and qualifies, a | |
| 381 | // hand-written one that stores elsewhere does not. Null for any | |
| 382 | // target that is not an instance property on `self`. | |
| 383 | _writes_own_instance_property_member(target: Trees.Expressions.Expression?) -> Function? is | |
| 384 | if !target? \/ !isa Trees.Expressions.MEMBER(target) then | |
| 385 | return null | |
| 386 | fi | |
| 387 | ||
| 388 | let member = cast Trees.Expressions.MEMBER(target) | |
| 389 | ||
| 390 | if !isa Trees.Expressions.SELF(member.left) then | |
| 391 | return null | |
| 392 | fi | |
| 393 | ||
| 394 | let context = current_instance_context | |
| 395 | ||
| 396 | if !context? then | |
| 397 | return null | |
| 398 | fi | |
| 399 | ||
| 400 | return _instance_property_assign(context.find_member(member.identifier.name)) | |
| 401 | si | |
| 402 | ||
| 403 | // A constructor delegating to another constructor on the same | |
| 404 | // object — `super.init(…)` from a subclass, `self.init(…)` from | |
| 405 | // a secondary constructor. | |
| 406 | _is_constructor_chain(member: Trees.Expressions.MEMBER) -> bool => | |
| 407 | _in_constructor /\ | |
| 408 | member.identifier.name =~ "init" /\ | |
| 409 | (isa Trees.Expressions.SELF(member.left) \/ isa Trees.Expressions.SUPER(member.left)) | |
| 410 | ||
| 411 | _instance_property_assign(symbol: Symbol?) -> Function? is | |
| 412 | if !symbol? \/ !symbol.is_instance \/ !isa Semantic.Symbols.Property(symbol) then | |
| 413 | return null | |
| 414 | fi | |
| 415 | ||
| 416 | return (cast Semantic.Symbols.Property(symbol)).assign_function | |
| 417 | si | |
| 418 | ||
| 419 | si | |
| 420 | si | |
| 421 | ||
| 422 | namespace Syntax.Process is | |
| 423 | use Function = Semantic.Symbols.Function | |
| 424 | ||
| 425 | // Measurement only: the call sites where the overload compile- | |
| 426 | // expressions chose was picked with a narrowed operand in play and | |
| 427 | // the callee has siblings. These are the only places the solve is | |
| 428 | // not monotone in the facts - a killed narrowing can move the call | |
| 429 | // to a sibling with a different write set - so their count, and | |
| 430 | // how many siblings actually differ, says whether the descent's | |
| 431 | // answer can depend on where it started. | |
| 432 | partial INFER_STORE_FREE is | |
| 433 | _overload_sites: Collections.LIST[(callee: Function, siblings: Collections.List[Function])]? static | |
| 434 | ||
| 435 | _note_overload_site(function: Function, from: IR.Values.Value?, arguments: Collections.List[IR.Values.Value]) is | |
| 436 | if !_measure_overload_sites \/ !_resolved_mode then | |
| 437 | return | |
| 438 | fi | |
| 439 | ||
| 440 | let narrowed mut = from? /\ isa IR.Values.NARROW_VIEW(from) | |
| 441 | ||
| 442 | for argument in arguments do | |
| 443 | if isa IR.Values.NARROW_VIEW(argument) then | |
| 444 | narrowed = true | |
| 445 | fi | |
| 446 | od | |
| 447 | ||
| 448 | if !narrowed then | |
| 449 | return | |
| 450 | fi | |
| 451 | ||
| 452 | let root = cast Function?(function.root_specialized_from) | |
| 453 | ||
| 454 | if !root? then | |
| 455 | return | |
| 456 | fi | |
| 457 | ||
| 458 | if let owner = root.owner, group: Semantic.Symbols.FUNCTION_GROUP = owner.find_member(root.name) then | |
| 459 | if group.count > 1 then | |
| 460 | if !_overload_sites? then | |
| 461 | _overload_sites = Collections.LIST[(callee: Function, siblings: Collections.List[Function])]() | |
| 462 | fi | |
| 463 | ||
| 464 | _overload_sites.add((callee = root, siblings = group.functions)) | |
| 465 | fi | |
| 466 | fi | |
| 467 | si | |
| 468 | ||
| 469 | // After a solve: how many noted sites have a sibling whose | |
| 470 | // solved write set differs from the chosen overload's. | |
| 471 | _report_overload_sites() static is | |
| 472 | let sites = _overload_sites | |
| 473 | ||
| 474 | if !sites? then | |
| 475 | IO.Std.error.write_line("overload sites with a narrowed operand: 0") | |
| 476 | ||
| 477 | return | |
| 478 | fi | |
| 479 | ||
| 480 | let differing mut = 0 | |
| 481 | ||
| 482 | for site in sites do | |
| 483 | let chosen = EFFECTS.write_set_of(site.callee) | |
| 484 | ||
| 485 | for sibling in site.siblings do | |
| 486 | if sibling == site.callee then | |
| 487 | continue | |
| 488 | fi | |
| 489 | ||
| 490 | if !_same_write_set(chosen, EFFECTS.write_set_of(sibling)) then | |
| 491 | differing = differing + 1 | |
| 492 | ||
| 493 | IO.Std.error.write_line(" overload site: {site.callee.qualified_name} vs {sibling.qualified_name}") | |
| 494 | ||
| 495 | break | |
| 496 | fi | |
| 497 | od | |
| 498 | od | |
| 499 | ||
| 500 | IO.Std.error.write_line("overload sites with a narrowed operand: {sites.count}, with a sibling whose write set differs: {differing}") | |
| 501 | ||
| 502 | _overload_sites = null | |
| 503 | si | |
| 504 | ||
| 505 | _same_write_set(a: Collections.SET[int]?, b: Collections.SET[int]?) -> bool static is | |
| 506 | if !a? \/ !b? then | |
| 507 | return !a? /\ !b? | |
| 508 | fi | |
| 509 | ||
| 510 | if a.count != b.count then | |
| 511 | return false | |
| 512 | fi | |
| 513 | ||
| 514 | for id in a do | |
| 515 | if !b.contains(id) then | |
| 516 | return false | |
| 517 | fi | |
| 518 | od | |
| 519 | ||
| 520 | return true | |
| 521 | si | |
| 522 | si | |
| 523 | si |