Appearance
| 1 | namespace Syntax.Process is | |
| 2 | use Collections | |
| 3 | ||
| 4 | use Semantic | |
| 5 | ||
| 6 | // One stage of a recognised pipe chain. Three kinds: | |
| 7 | // | |
| 8 | // - map (is_filter false, is_index false): `argument` is the mapper. | |
| 9 | // - filter (is_filter true): `argument` is the predicate. | |
| 10 | // - index (is_index true): `argument` is the start, or null to start | |
| 11 | // at zero; the loop keeps a running counter and emits | |
| 12 | // `INDEXED_VALUE[element](counter, current)` per element. | |
| 13 | // compile-expressions fills `indexed_value_type` (the constructed | |
| 14 | // `INDEXED_VALUE[element]` struct) and `indexed_value_constructor`. | |
| 15 | // | |
| 16 | // A fourth kind is transparent: a `memo` stage (is_noop true) is | |
| 17 | // recognised but never added to a chain's stage list. A memo pipe | |
| 18 | // consumed inline by the one `for` loop or terminal consumer that | |
| 19 | // fuses a chain is unobservable - its cache is never read a second | |
| 20 | // time and its source runs exactly once with or without it - so the | |
| 21 | // chain fuses as though the memo were absent. The MEMO_PIPE itself is | |
| 22 | // then never constructed; wherever the chain does not fuse, the memo | |
| 23 | // is built and behaves exactly as written. | |
| 24 | // | |
| 25 | // For a map/filter stage whose `argument` is an inlinable literal | |
| 26 | // lambda, compile-expressions fills `param_local` (a synthetic | |
| 27 | // enclosing-method local the loop assigns the incoming element to) and | |
| 28 | // `inline_body` (the lambda body re-walked in the enclosing scope, so | |
| 29 | // its parameter loads that local and its captures load ordinary | |
| 30 | // enclosing locals - no delegate, no closure frame). When both are set | |
| 31 | // the loop emits the body inline; otherwise it invokes the argument's | |
| 32 | // compiled delegate value. | |
| 33 | class PIPE_FUSION_STAGE is | |
| 34 | is_filter: bool public | |
| 35 | is_index: bool public | |
| 36 | is_noop: bool public | |
| 37 | ||
| 38 | // A `take`/`skip` stage: `argument` is the int count expression, | |
| 39 | // evaluated once into a running counter that the loop decrements per | |
| 40 | // pulled element (take stops the loop when it runs out; skip drops | |
| 41 | // the element while it remains). | |
| 42 | is_take: bool public | |
| 43 | is_skip: bool public | |
| 44 | ||
| 45 | // The stage's argument: a map/filter lambda or delegate, the int | |
| 46 | // count of a take/skip stage, or an index stage's start. Null for | |
| 47 | // an index stage that starts at zero. | |
| 48 | argument: Trees.Expressions.Expression? public | |
| 49 | ||
| 50 | // Index stage only. `chain_type` is the `index` call's own type, | |
| 51 | // `Pipe[INDEXED_VALUE[E]]`, from which compile-expressions reads | |
| 52 | // the INDEXED_VALUE the loop builds per element and resolves its | |
| 53 | // constructor. `argument`, when present, is the start the caller | |
| 54 | // supplied, evaluated once into the running counter exactly as a | |
| 55 | // take/skip count is; absent, the counter starts at zero. | |
| 56 | chain_type: Semantic.Types.Type? public | |
| 57 | indexed_value_type: Semantic.Types.Type? public | |
| 58 | indexed_value_constructor: Semantic.Symbols.Function? public | |
| 59 | ||
| 60 | param_local: Semantic.Symbols.Variable? public | |
| 61 | inline_body: IR.Values.Value? public | |
| 62 | ||
| 63 | // A take/skip stage keeps a running counter but transforms nothing, | |
| 64 | // so the element passes through unchanged. | |
| 65 | is_countdown: bool => is_take \/ is_skip | |
| 66 | ||
| 67 | is_inlined: bool => param_local? /\ inline_body? | |
| 68 | ||
| 69 | // A fusible index stage needs both its type and constructor | |
| 70 | // resolved; otherwise the recogniser rejects the chain. | |
| 71 | is_index_ready: bool => indexed_value_type? /\ indexed_value_constructor? | |
| 72 | ||
| 73 | init(is_filter: bool, argument: Trees.Expressions.Expression) is | |
| 74 | self.is_filter = is_filter | |
| 75 | self.argument = argument | |
| 76 | si | |
| 77 | ||
| 78 | init(chain_type: Semantic.Types.Type, start: Trees.Expressions.Expression?) is | |
| 79 | self.is_index = true | |
| 80 | self.chain_type = chain_type | |
| 81 | self.argument = start | |
| 82 | si | |
| 83 | ||
| 84 | init(is_take: bool, is_skip: bool, count: Trees.Expressions.Expression) is | |
| 85 | self.is_take = is_take | |
| 86 | self.is_skip = is_skip | |
| 87 | self.argument = count | |
| 88 | si | |
| 89 | ||
| 90 | init() is | |
| 91 | is_noop = true | |
| 92 | si | |
| 93 | si | |
| 94 | ||
| 95 | // Stage-B inlining (`_try_inline_stage` in compile-expressions) | |
| 96 | // harvests IR straight from a speculative compile-expressions walk of | |
| 97 | // the stage lambda's body, then splices it directly into the fused | |
| 98 | // loop - it is never walked again during generate-il. A `cast` | |
| 99 | // expression compiles in two stages: compile-expressions leaves a | |
| 100 | // `WRAPPER` placeholder around a poisoning `DUMMY` value, and only | |
| 101 | // generate-il's own walk (`visit(CAST)`) fills it in with the real | |
| 102 | // conversion. An inlined stage skips that second walk entirely, so a | |
| 103 | // `cast` anywhere in its body reaches `gen()` still holding the | |
| 104 | // placeholder and the compiler dies with "generated dummy value". | |
| 105 | // Scanning for one disqualifies the stage from inlining; the delegate | |
| 106 | // fallback compiles the same body as an ordinary function, which does | |
| 107 | // get generate-il's normal walk. | |
| 108 | class INLINE_DISQUALIFYING_SCANNER: Visitor is | |
| 109 | _found: bool | |
| 110 | ||
| 111 | init() is | |
| 112 | super.init() | |
| 113 | si | |
| 114 | ||
| 115 | contains_cast(body: Trees.Bodies.Body?) -> bool is | |
| 116 | _found = false | |
| 117 | ||
| 118 | if body? then | |
| 119 | body.walk(self) | |
| 120 | fi | |
| 121 | ||
| 122 | return _found | |
| 123 | si | |
| 124 | ||
| 125 | pre(`cast: Trees.Expressions.CAST) -> bool is | |
| 126 | _found = true | |
| 127 | ||
| 128 | return true | |
| 129 | si | |
| 130 | ||
| 131 | pre(function: Trees.Definitions.FUNCTION) -> bool => true | |
| 132 | pre(function: Trees.Expressions.FUNCTION) -> bool => true | |
| 133 | si | |
| 134 | ||
| 135 | // A recognised fusible pipe chain rooted at a `for` loop. `source` is | |
| 136 | // the iterable the chain starts from; the fused loop iterates it | |
| 137 | // directly - so no pipe object is built for it - and applies `stages` | |
| 138 | // inline per element. `stages` | |
| 139 | // are outermost-first (the order they wrap the source), so inline | |
| 140 | // application walks them in reverse. | |
| 141 | class PIPE_FUSION(source: Trees.Expressions.Expression, stages_outermost_first: LIST[PIPE_FUSION_STAGE]) is | |
| 142 | source: Trees.Expressions.Expression public | |
| 143 | stages_outermost_first: LIST[PIPE_FUSION_STAGE] public | |
| 144 | ||
| 145 | // The source's own iterator members, resolved against its type | |
| 146 | // exactly as a plain `for x in source` would. read_iterator is | |
| 147 | // null when the source is directly an iterator (e.g. a range); | |
| 148 | // otherwise it yields the iterator that move_next / read_current | |
| 149 | // drive. Filled by compile-expressions after recognition. | |
| 150 | source_read_iterator: Semantic.Symbols.Function? public | |
| 151 | source_move_next: Semantic.Symbols.Function? public | |
| 152 | source_read_current: Semantic.Symbols.Function? public | |
| 153 | ||
| 154 | // `Pipe[E].reset` and the `Pipe[E]` it is declared on, for the | |
| 155 | // guarded rewind a spent `take` owes the cursor. A stage pipe | |
| 156 | // ends its pass by rewinding whatever it drew from, and rewinding | |
| 157 | // asks at run time whether that cursor is a `Pipe[T]`: one is | |
| 158 | // reset in place, and anything else is left where it stopped for | |
| 159 | // whoever reads it next. The static type does not settle the | |
| 160 | // question - a `Pipe` reaches the loop through an `Iterable` | |
| 161 | // variable, and a type that is its own iterator need not be a | |
| 162 | // pipe at all - so the loop asks the same question the same way. | |
| 163 | // Null when the cursor is a value type, which the loop holds a | |
| 164 | // copy of and owes nothing. Filled by compile-expressions after | |
| 165 | // recognition. | |
| 166 | pipe_type: Semantic.Types.Type? public | |
| 167 | pipe_reset: Semantic.Symbols.Function? public | |
| 168 | si | |
| 169 | ||
| 170 | // Decides whether a `for x in <chain>` loop's expression is a | |
| 171 | // fusible pipe chain, and if so returns the plan the IL pass | |
| 172 | // consumes. Pure recognition — no compilation side effects. | |
| 173 | // | |
| 174 | // A chain is a run of `Ghul.Pipes` free-function calls, which have no | |
| 175 | // receiver, so no call in one can reach a `Pipe[T]` implementation | |
| 176 | // that overrides a combinator: what a stage does is settled by the | |
| 177 | // function the call resolved to. Nothing about the source's dynamic | |
| 178 | // type can change that, so a chain fuses whatever it starts from - | |
| 179 | // see `recognize_free_function_chain`. | |
| 180 | class PIPE_FUSION_RECOGNIZER(fusion_functions: Collections.MAP[Semantic.Symbols.Symbol, string]) is | |
| 181 | ||
| 182 | recognize(`for: Trees.Statements.FOR) -> PIPE_FUSION? => | |
| 183 | recognize_any(`for.expression) | |
| 184 | ||
| 185 | // Peel a chain of `Ghul.Pipes` free functions off `expression`. | |
| 186 | // Used both by the `for`-loop path and by consumer fusion. | |
| 187 | recognize_any(expression: Trees.Expressions.Expression?) -> PIPE_FUSION? => | |
| 188 | recognize_free_function_chain(expression) | |
| 189 | ||
| 190 | // Peel a `... |> map(f) |> filter(p)` chain of `Ghul.Pipes` free | |
| 191 | // functions off an arbitrary expression. `|>` is desugared entirely | |
| 192 | // at parse time into an ordinary CALL with the threaded value | |
| 193 | // inserted as argument 0, so by the time this pass runs `xs |> | |
| 194 | // map(f)` is indistinguishable from `map(xs, f)` - a plain | |
| 195 | // global-function call resolved once via ordinary overload | |
| 196 | // resolution. | |
| 197 | // | |
| 198 | // Soundness, dispatch: `Ghul.Pipes.map`/`filter`/`take`/`skip` are | |
| 199 | // global functions with no receiver, so a call to one is never a | |
| 200 | // member access and never reaches an overridden `Pipe[T].map`/ | |
| 201 | // `filter` - fused or not, whatever the source's static or | |
| 202 | // dynamic type. | |
| 203 | // | |
| 204 | // A source that is itself a Pipe also fuses, because a | |
| 205 | // thread-first chain is routinely | |
| 206 | // written straight off a generator or a `stream`. Driving such a | |
| 207 | // source's own cursor carries an obligation the fused loop has to | |
| 208 | // honour by hand - see `source_reset` on PIPE_FUSION. | |
| 209 | recognize_free_function_chain(expression: Trees.Expressions.Expression?) -> PIPE_FUSION? is | |
| 210 | if !expression? then | |
| 211 | return null | |
| 212 | fi | |
| 213 | ||
| 214 | let stages = LIST[PIPE_FUSION_STAGE]() | |
| 215 | ||
| 216 | let current mut = expression | |
| 217 | let calls mut = 0 | |
| 218 | ||
| 219 | while isa Trees.Expressions.CALL(current) do | |
| 220 | let call = cast Trees.Expressions.CALL(current) | |
| 221 | ||
| 222 | let stage = _classify_free_function_stage(call) | |
| 223 | ||
| 224 | if !stage? then | |
| 225 | break | |
| 226 | fi | |
| 227 | ||
| 228 | calls = calls + 1 | |
| 229 | ||
| 230 | // A memo stage is elided rather than fused: the chain | |
| 231 | // fuses as though it were absent (see PIPE_FUSION_STAGE). | |
| 232 | if !stage.is_noop then | |
| 233 | stages.add(stage) | |
| 234 | fi | |
| 235 | ||
| 236 | current = call.arguments.expressions[0] | |
| 237 | od | |
| 238 | ||
| 239 | // A chain whose only call was a memo still fuses - it iterates | |
| 240 | // the memo's source directly - but an expression that peeled | |
| 241 | // nothing at all is not a chain. | |
| 242 | if calls == 0 then | |
| 243 | return null | |
| 244 | fi | |
| 245 | ||
| 246 | let source = current | |
| 247 | let source_value = source.value | |
| 248 | ||
| 249 | if !source_value? \/ !source_value.type? then | |
| 250 | return null | |
| 251 | fi | |
| 252 | ||
| 253 | return PIPE_FUSION(source, stages) | |
| 254 | si | |
| 255 | ||
| 256 | // Classify `call` as a fusible `Ghul.Pipes` free-function stage - | |
| 257 | // map, filter, take, skip or index, or a `memo` stage that is | |
| 258 | // recognised only to be elided - by comparing the resolved call | |
| 259 | // target against the fusible-combinator symbols, so what fuses | |
| 260 | // follows the function the call bound rather than how it spells | |
| 261 | // itself. Returns null for any other function, which stops the | |
| 262 | // peel loop and leaves the call as an ordinary, unfused | |
| 263 | // expression - still correct, since an unrecognised stage drives | |
| 264 | // its own result through its own iterator exactly as the unfused | |
| 265 | // lowering would. | |
| 266 | _classify_free_function_stage(call: Trees.Expressions.CALL) -> PIPE_FUSION_STAGE? is | |
| 267 | let value = call.value | |
| 268 | ||
| 269 | if !isa IR.Values.Call.GLOBAL(value) then | |
| 270 | return null | |
| 271 | fi | |
| 272 | ||
| 273 | let global_call = cast IR.Values.Call.GLOBAL(value) | |
| 274 | let role: string mut | |
| 275 | ||
| 276 | if !fusion_functions.try_get_value(global_call.function.root_specialized_from, role ref) then | |
| 277 | return null | |
| 278 | fi | |
| 279 | ||
| 280 | let arguments = call.arguments.expressions | |
| 281 | ||
| 282 | if role =~ "memo" then | |
| 283 | if arguments.count != 1 then | |
| 284 | return null | |
| 285 | fi | |
| 286 | ||
| 287 | return PIPE_FUSION_STAGE() | |
| 288 | fi | |
| 289 | ||
| 290 | // `index` comes in both arities: from zero, or from a start | |
| 291 | // the caller supplies. The stage carries the call's own type, | |
| 292 | // which is where the INDEXED_VALUE it builds per element is | |
| 293 | // read from rather than reconstructed. | |
| 294 | if role =~ "index" then | |
| 295 | let chain_type = value.type | |
| 296 | ||
| 297 | if arguments.count == 1 then | |
| 298 | return PIPE_FUSION_STAGE(chain_type, null) | |
| 299 | elif arguments.count == 2 then | |
| 300 | return PIPE_FUSION_STAGE(chain_type, arguments[1]) | |
| 301 | fi | |
| 302 | ||
| 303 | return null | |
| 304 | fi | |
| 305 | ||
| 306 | if arguments.count != 2 then | |
| 307 | return null | |
| 308 | fi | |
| 309 | ||
| 310 | if role =~ "map" \/ role =~ "filter" then | |
| 311 | return PIPE_FUSION_STAGE(role =~ "filter", arguments[1]) | |
| 312 | fi | |
| 313 | ||
| 314 | if role =~ "take" \/ role =~ "skip" then | |
| 315 | return PIPE_FUSION_STAGE(role =~ "take", role =~ "skip", arguments[1]) | |
| 316 | fi | |
| 317 | ||
| 318 | return null | |
| 319 | si | |
| 320 | si | |
| 321 | si |