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 | if let call: IR.Values.Call.INSTANCE = value then | |
| 138 | _note_overload_site(call.function, call.from, call.arguments) | |
| 139 | _add_callee(call.function) | |
| 140 | _study_note_call_arguments(call.function, call.arguments) | |
| 141 | return true | |
| 142 | fi | |
| 143 | ||
| 144 | if let call: IR.Values.Call.STATIC = value then | |
| 145 | _note_overload_site(call.function, null, call.arguments) | |
| 146 | _add_callee(call.function) | |
| 147 | _study_note_call_arguments(call.function, call.arguments) | |
| 148 | return true | |
| 149 | fi | |
| 150 | ||
| 151 | if let call: IR.Values.Call.GLOBAL = value then | |
| 152 | _note_overload_site(call.function, null, call.arguments) | |
| 153 | _add_callee(call.function) | |
| 154 | _study_note_call_arguments(call.function, call.arguments) | |
| 155 | return true | |
| 156 | fi | |
| 157 | ||
| 158 | if let call: IR.Values.Call.STRUCT = value then | |
| 159 | _note_overload_site(call.function, call.from, call.arguments) | |
| 160 | _add_callee(call.function) | |
| 161 | _study_note_call_arguments(call.function, call.arguments) | |
| 162 | return true | |
| 163 | fi | |
| 164 | ||
| 165 | if let construction: IR.Values.NEW = value then | |
| 166 | // constructing a reflected exception writes only the | |
| 167 | // fresh object — the same trust the declared-types | |
| 168 | // classification extends, restated here so the edge | |
| 169 | // to the unwalked BCL constructor does not poison | |
| 170 | if !_is_store_free_construction(cast Symbol?(construction.constructor.owner)) then | |
| 171 | _add_construction_callee(construction.constructor) | |
| 172 | fi | |
| 173 | ||
| 174 | _study_note_call_arguments(construction.constructor, construction.arguments) | |
| 175 | return true | |
| 176 | fi | |
| 177 | ||
| 178 | // Invoking a function value: bounded when the value names | |
| 179 | // its function, effect-polymorphic when it is one of the | |
| 180 | // enclosing function's own parameters, unboundable | |
| 181 | // otherwise. | |
| 182 | if let call: IR.Values.Call.CLOSURE = value then | |
| 183 | if !call.is_state_changing_call then | |
| 184 | return true | |
| 185 | fi | |
| 186 | ||
| 187 | let fn = function_value_of(call.from) | |
| 188 | ||
| 189 | if fn? then | |
| 190 | _add_callee(fn) | |
| 191 | _study_note_call_arguments(fn, call.arguments) | |
| 192 | return true | |
| 193 | fi | |
| 194 | ||
| 195 | if isa IR.Values.Load.LOCAL_ARGUMENT(call.from) then | |
| 196 | if _current_record? then | |
| 197 | _current_record.invokes_function_param = true | |
| 198 | fi | |
| 199 | ||
| 200 | return true | |
| 201 | fi | |
| 202 | ||
| 203 | return false | |
| 204 | fi | |
| 205 | ||
| 206 | // not a call at all: reading a value writes nothing, and any | |
| 207 | // sub-expression is classified as the walk reaches it | |
| 208 | return !value.is_state_changing_call | |
| 209 | si | |
| 210 | ||
| 211 | function_values: FUNCTION_VALUES public | |
| 212 | ||
| 213 | // The resolver from compiled values to the functions they | |
| 214 | // denote, including the immutable-local record this walk | |
| 215 | // populates. Shared with the pure-slot judge. | |
| 216 | ||
| 217 | function_value_of(value: IR.Values.Value?) -> Function? => | |
| 218 | function_values.function_value_of(value) | |
| 219 | ||
| 220 | // Record which function values flow into a callee's | |
| 221 | // function-typed parameters. A named value joins the callee's | |
| 222 | // passed set; the caller's own parameter forwarded onward is | |
| 223 | // accounted at the caller's own call sites instead; anything | |
| 224 | // else function-typed makes the callee's parameter values | |
| 225 | // unknowable - unless its type is pure, which admits only | |
| 226 | // store-free values whoever invokes it. | |
| 227 | _study_note_call_arguments(callee: Function?, arguments: Collections.List[IR.Values.Value]) is | |
| 228 | if !callee? then | |
| 229 | return | |
| 230 | fi | |
| 231 | ||
| 232 | let from_file = if let current = _current_function then current.location.file_name else "" fi | |
| 233 | ||
| 234 | for argument in arguments do | |
| 235 | let fn = function_value_of(argument) | |
| 236 | ||
| 237 | if fn? then | |
| 238 | EFFECT_FACTS.note_passed_function(callee, fn, from_file) | |
| 239 | continue | |
| 240 | fi | |
| 241 | ||
| 242 | if isa IR.Values.Load.LOCAL_ARGUMENT(argument) then | |
| 243 | let argument_type = argument.type | |
| 244 | ||
| 245 | if argument_type? /\ argument_type.is_function /\ !argument_type.is_pure_function then | |
| 246 | if _current_record? then | |
| 247 | let root = cast Function?(callee.root_specialized_from) | |
| 248 | ||
| 249 | if root? then | |
| 250 | _current_record.forwards_param_to.add(root) | |
| 251 | fi | |
| 252 | fi | |
| 253 | fi | |
| 254 | ||
| 255 | continue | |
| 256 | fi | |
| 257 | ||
| 258 | let argument_type = argument.type | |
| 259 | ||
| 260 | if argument_type? /\ argument_type.is_function /\ !argument_type.is_pure_function then | |
| 261 | EFFECT_FACTS.note_passed_opaque(callee, from_file) | |
| 262 | NARROWING_STUDY.note_opaque_shape("{argument.get_type().name} -> {callee.name}") | |
| 263 | fi | |
| 264 | od | |
| 265 | si | |
| 266 | ||
| 267 | // `_disqualify` with the reason recorded for the study, so the | |
| 268 | // report can say what the walk actually gives up on. First | |
| 269 | // reason wins: it is the one that made the function unbounded. | |
| 270 | _disqualify_because(reason: string) is | |
| 271 | ||
| 272 | if _current? /\ _current_record? /\ _current_record.unbounded_reason =~ "" then | |
| 273 | _current_record.unbounded_reason = reason | |
| 274 | fi | |
| 275 | ||
| 276 | _disqualify() | |
| 277 | si | |
| 278 | ||
| 279 | _disqualify() is | |
| 280 | if !_current? then | |
| 281 | return | |
| 282 | fi | |
| 283 | ||
| 284 | _current.is_disqualified = true | |
| 285 | _current.is_construction_disqualified = true | |
| 286 | ||
| 287 | if _current_record? then | |
| 288 | _current_record.own_unbounded = true | |
| 289 | ||
| 290 | // whatever the walk could not bound could write | |
| 291 | // anything, so the write set stops being a bound too | |
| 292 | _current_record.writes_unbounded = true | |
| 293 | fi | |
| 294 | si | |
| 295 | ||
| 296 | // A captured-local store: not store-free - the declaring | |
| 297 | // scope sees the write - but the write set stays bounded, | |
| 298 | // because the store targets exactly the one local symbol the | |
| 299 | // study path records. | |
| 300 | _disqualify_captured_store() is | |
| 301 | if !_current? then | |
| 302 | return | |
| 303 | fi | |
| 304 | ||
| 305 | _current.is_disqualified = true | |
| 306 | _current.is_construction_disqualified = true | |
| 307 | si | |
| 308 | ||
| 309 | // The subset of `_disqualify` where the walk saw a write to a | |
| 310 | // pre-existing heap slot rather than merely failing to bound | |
| 311 | // something. Behaves identically; only the study distinguishes | |
| 312 | // them. | |
| 313 | _disqualify_store() is | |
| 314 | if !_current? then | |
| 315 | return | |
| 316 | fi | |
| 317 | ||
| 318 | _current.is_disqualified = true | |
| 319 | _current.is_construction_disqualified = true | |
| 320 | ||
| 321 | if _current_record? then | |
| 322 | _current_record.own_stores = true | |
| 323 | fi | |
| 324 | si | |
| 325 | ||
| 326 | // A store the strict analysis rejects but a construction does | |
| 327 | // not: writing the receiver's own instance state touches only | |
| 328 | // the fresh object a `NEW` is building. | |
| 329 | _disqualify_strict_only() is | |
| 330 | if !_current? then | |
| 331 | return | |
| 332 | fi | |
| 333 | ||
| 334 | _current.is_disqualified = true | |
| 335 | ||
| 336 | if _current_record? then | |
| 337 | _current_record.own_stores = true | |
| 338 | fi | |
| 339 | si | |
| 340 | ||
| 341 | ||
| 342 | _in_constructor: bool => | |
| 343 | _current_function? /\ _current_function.is_constructor | |
| 344 | ||
| 345 | // A `self.field` target naming an instance field of the | |
| 346 | // receiver. `self` is the only receiver the construction bit | |
| 347 | // says anything about; a member on any other receiver stays a | |
| 348 | // heap store. | |
| 349 | _writes_own_instance_field_member(target: Trees.Expressions.Expression?) -> bool is | |
| 350 | if !target? \/ !isa Trees.Expressions.MEMBER(target) then | |
| 351 | return false | |
| 352 | fi | |
| 353 | ||
| 354 | let member = cast Trees.Expressions.MEMBER(target) | |
| 355 | ||
| 356 | if !isa Trees.Expressions.SELF(member.left) then | |
| 357 | return false | |
| 358 | fi | |
| 359 | ||
| 360 | let context = current_instance_context | |
| 361 | ||
| 362 | if !context? then | |
| 363 | return false | |
| 364 | fi | |
| 365 | ||
| 366 | let field_symbol = context.find_member(member.identifier.name) | |
| 367 | ||
| 368 | return field_symbol? /\ field_symbol.is_field /\ field_symbol.is_instance | |
| 369 | si | |
| 370 | ||
| 371 | // The assign accessor behind a `self.property` target on the | |
| 372 | // type under construction. Writing a property runs its | |
| 373 | // accessor rather than storing directly, so the write is only | |
| 374 | // as safe as that accessor is — an auto-property's accessor | |
| 375 | // writes nothing but its own backing field and qualifies, a | |
| 376 | // hand-written one that stores elsewhere does not. Null for any | |
| 377 | // target that is not an instance property on `self`. | |
| 378 | _writes_own_instance_property_member(target: Trees.Expressions.Expression?) -> Function? is | |
| 379 | if !target? \/ !isa Trees.Expressions.MEMBER(target) then | |
| 380 | return null | |
| 381 | fi | |
| 382 | ||
| 383 | let member = cast Trees.Expressions.MEMBER(target) | |
| 384 | ||
| 385 | if !isa Trees.Expressions.SELF(member.left) then | |
| 386 | return null | |
| 387 | fi | |
| 388 | ||
| 389 | let context = current_instance_context | |
| 390 | ||
| 391 | if !context? then | |
| 392 | return null | |
| 393 | fi | |
| 394 | ||
| 395 | return _instance_property_assign(context.find_member(member.identifier.name)) | |
| 396 | si | |
| 397 | ||
| 398 | // A constructor delegating to another constructor on the same | |
| 399 | // object — `super.init(…)` from a subclass, `self.init(…)` from | |
| 400 | // a secondary constructor. | |
| 401 | _is_constructor_chain(member: Trees.Expressions.MEMBER) -> bool => | |
| 402 | _in_constructor /\ | |
| 403 | member.identifier.name =~ "init" /\ | |
| 404 | (isa Trees.Expressions.SELF(member.left) \/ isa Trees.Expressions.SUPER(member.left)) | |
| 405 | ||
| 406 | _instance_property_assign(symbol: Symbol?) -> Function? is | |
| 407 | if !symbol? \/ !symbol.is_instance \/ !isa Semantic.Symbols.Property(symbol) then | |
| 408 | return null | |
| 409 | fi | |
| 410 | ||
| 411 | return (cast Semantic.Symbols.Property(symbol)).assign_function | |
| 412 | si | |
| 413 | ||
| 414 | si | |
| 415 | si | |
| 416 | ||
| 417 | namespace Syntax.Process is | |
| 418 | use Function = Semantic.Symbols.Function | |
| 419 | ||
| 420 | // Measurement only: the call sites where the overload compile- | |
| 421 | // expressions chose was picked with a narrowed operand in play and | |
| 422 | // the callee has siblings. These are the only places the solve is | |
| 423 | // not monotone in the facts - a killed narrowing can move the call | |
| 424 | // to a sibling with a different write set - so their count, and | |
| 425 | // how many siblings actually differ, says whether the descent's | |
| 426 | // answer can depend on where it started. | |
| 427 | partial INFER_STORE_FREE is | |
| 428 | _overload_sites: Collections.LIST[(callee: Function, siblings: Collections.List[Function])]? static | |
| 429 | ||
| 430 | _note_overload_site(function: Function, from: IR.Values.Value?, arguments: Collections.List[IR.Values.Value]) is | |
| 431 | if !_measure_overload_sites \/ !_resolved_mode then | |
| 432 | return | |
| 433 | fi | |
| 434 | ||
| 435 | let narrowed mut = from? /\ isa IR.Values.NARROW_VIEW(from) | |
| 436 | ||
| 437 | for argument in arguments do | |
| 438 | if isa IR.Values.NARROW_VIEW(argument) then | |
| 439 | narrowed = true | |
| 440 | fi | |
| 441 | od | |
| 442 | ||
| 443 | if !narrowed then | |
| 444 | return | |
| 445 | fi | |
| 446 | ||
| 447 | let root = cast Function?(function.root_specialized_from) | |
| 448 | ||
| 449 | if !root? then | |
| 450 | return | |
| 451 | fi | |
| 452 | ||
| 453 | if let owner = root.owner, group: Semantic.Symbols.FUNCTION_GROUP = owner.find_member(root.name) then | |
| 454 | if group.count > 1 then | |
| 455 | if !_overload_sites? then | |
| 456 | _overload_sites = Collections.LIST[(callee: Function, siblings: Collections.List[Function])]() | |
| 457 | fi | |
| 458 | ||
| 459 | _overload_sites.add((callee = root, siblings = group.functions)) | |
| 460 | fi | |
| 461 | fi | |
| 462 | si | |
| 463 | ||
| 464 | // After a solve: how many noted sites have a sibling whose | |
| 465 | // solved write set differs from the chosen overload's. | |
| 466 | _report_overload_sites() static is | |
| 467 | let sites = _overload_sites | |
| 468 | ||
| 469 | if !sites? then | |
| 470 | IO.Std.error.write_line("overload sites with a narrowed operand: 0") | |
| 471 | ||
| 472 | return | |
| 473 | fi | |
| 474 | ||
| 475 | let differing mut = 0 | |
| 476 | ||
| 477 | for site in sites do | |
| 478 | let chosen = EFFECTS.write_set_of(site.callee) | |
| 479 | ||
| 480 | for sibling in site.siblings do | |
| 481 | if sibling == site.callee then | |
| 482 | continue | |
| 483 | fi | |
| 484 | ||
| 485 | if !_same_write_set(chosen, EFFECTS.write_set_of(sibling)) then | |
| 486 | differing = differing + 1 | |
| 487 | ||
| 488 | IO.Std.error.write_line(" overload site: {site.callee.qualified_name} vs {sibling.qualified_name}") | |
| 489 | ||
| 490 | break | |
| 491 | fi | |
| 492 | od | |
| 493 | od | |
| 494 | ||
| 495 | IO.Std.error.write_line("overload sites with a narrowed operand: {sites.count}, with a sibling whose write set differs: {differing}") | |
| 496 | ||
| 497 | _overload_sites = null | |
| 498 | si | |
| 499 | ||
| 500 | _same_write_set(a: Collections.SET[int]?, b: Collections.SET[int]?) -> bool static is | |
| 501 | if !a? \/ !b? then | |
| 502 | return !a? /\ !b? | |
| 503 | fi | |
| 504 | ||
| 505 | if a.count != b.count then | |
| 506 | return false | |
| 507 | fi | |
| 508 | ||
| 509 | for id in a do | |
| 510 | if !b.contains(id) then | |
| 511 | return false | |
| 512 | fi | |
| 513 | od | |
| 514 | ||
| 515 | return true | |
| 516 | si | |
| 517 | si | |
| 518 | si |