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 | ||
| 62 | inline_body: IR.Values.Value? public | |
| 63 | ||
| 64 | // The literal whose body this stage inlines, so the emission site | |
| 65 | // can have its body walked into the block it emits. | |
| 66 | inlined_closure: Semantic.Symbols.Closure? public | |
| 67 | ||
| 68 | // A take/skip stage keeps a running counter but transforms nothing, | |
| 69 | // so the element passes through unchanged. | |
| 70 | is_countdown: bool => is_take \/ is_skip | |
| 71 | ||
| 72 | is_inlined: bool => param_local? /\ inline_body? | |
| 73 | ||
| 74 | // A fusible index stage needs both its type and constructor | |
| 75 | // resolved; otherwise the recogniser rejects the chain. | |
| 76 | is_index_ready: bool => indexed_value_type? /\ indexed_value_constructor? | |
| 77 | ||
| 78 | init(is_filter: bool, argument: Trees.Expressions.Expression) is | |
| 79 | self.is_filter = is_filter | |
| 80 | self.argument = argument | |
| 81 | si | |
| 82 | ||
| 83 | init(chain_type: Semantic.Types.Type, start: Trees.Expressions.Expression?) is | |
| 84 | self.is_index = true | |
| 85 | self.chain_type = chain_type | |
| 86 | self.argument = start | |
| 87 | si | |
| 88 | ||
| 89 | init(is_take: bool, is_skip: bool, count: Trees.Expressions.Expression) is | |
| 90 | self.is_take = is_take | |
| 91 | self.is_skip = is_skip | |
| 92 | self.argument = count | |
| 93 | si | |
| 94 | ||
| 95 | init() is | |
| 96 | is_noop = true | |
| 97 | si | |
| 98 | si | |
| 99 | ||
| 100 | // The literals written inside a stage body, outermost first. Each | |
| 101 | // one's captures are recorded against the symbols its enclosing | |
| 102 | // literal owned, so they are dropped before the body is walked | |
| 103 | // inline and recorded afresh against the method's own locals. | |
| 104 | class NESTED_LITERAL_COLLECTOR: Visitor is | |
| 105 | _literals: LIST[Trees.Expressions.FUNCTION] | |
| 106 | ||
| 107 | init() is | |
| 108 | super.init() | |
| 109 | ||
| 110 | _literals = LIST[Trees.Expressions.FUNCTION]() | |
| 111 | si | |
| 112 | ||
| 113 | collect(body: Trees.Bodies.Body?) -> Collections.List[Trees.Expressions.FUNCTION] is | |
| 114 | _literals.clear() | |
| 115 | ||
| 116 | if body? then | |
| 117 | body.walk(self) | |
| 118 | fi | |
| 119 | ||
| 120 | return _literals | |
| 121 | si | |
| 122 | ||
| 123 | pre(function: Trees.Expressions.FUNCTION) -> bool is | |
| 124 | _literals.add(function) | |
| 125 | ||
| 126 | return false | |
| 127 | si | |
| 128 | si | |
| 129 | ||
| 130 | // A recognised fusible pipe chain rooted at a `for` loop. `source` is | |
| 131 | // the iterable the chain starts from; the fused loop iterates it | |
| 132 | // directly - so no pipe object is built for it - and applies `stages` | |
| 133 | // inline per element. `stages` | |
| 134 | // are outermost-first (the order they wrap the source), so inline | |
| 135 | // application walks them in reverse. | |
| 136 | class PIPE_FUSION(source: Trees.Expressions.Expression, stages_outermost_first: LIST[PIPE_FUSION_STAGE]) is | |
| 137 | source: Trees.Expressions.Expression public | |
| 138 | stages_outermost_first: LIST[PIPE_FUSION_STAGE] public | |
| 139 | ||
| 140 | // The source's own iterator members, resolved against its type | |
| 141 | // exactly as a plain `for x in source` would. read_iterator is | |
| 142 | // null when the source is directly an iterator (e.g. a range); | |
| 143 | // otherwise it yields the iterator that move_next / read_current | |
| 144 | // drive. Filled by compile-expressions after recognition. | |
| 145 | source_read_iterator: Semantic.Symbols.Function? public | |
| 146 | source_move_next: Semantic.Symbols.Function? public | |
| 147 | source_read_current: Semantic.Symbols.Function? public | |
| 148 | si | |
| 149 | ||
| 150 | // Decides whether a `for x in <chain>` loop's expression is a | |
| 151 | // fusible pipe chain, and if so returns the plan the IL pass | |
| 152 | // consumes. Pure recognition — no compilation side effects. | |
| 153 | // | |
| 154 | // A chain is a run of `Ghul.Pipes` free-function calls, which have no | |
| 155 | // receiver, so no call in one can reach a `Pipe[T]` implementation | |
| 156 | // that overrides a combinator: what a stage does is settled by the | |
| 157 | // function the call resolved to. Nothing about the source's dynamic | |
| 158 | // type can change that, so a chain fuses whatever it starts from - | |
| 159 | // see `recognize_free_function_chain`. | |
| 160 | class PIPE_FUSION_RECOGNIZER(fusion_functions: Collections.MAP[Semantic.Symbols.Symbol, string]) is | |
| 161 | ||
| 162 | // Why the last recognition declined, and the roles of whatever | |
| 163 | // chain it had peeled when it did, outermost first. Read by the | |
| 164 | // pipe-fusion study; nothing the compiler decides depends on | |
| 165 | // either. A recogniser is constructed per recognition, so they | |
| 166 | // describe that one. | |
| 167 | decline_reason: string? | |
| 168 | peeled_roles: string? | |
| 169 | ||
| 170 | // The role the last successful classification named. | |
| 171 | _last_role: string? | |
| 172 | ||
| 173 | // The function the peel loop stopped at, when it stopped at a | |
| 174 | // global call fusion has no stage for. Read by the pipe-fusion | |
| 175 | // study, which asks whether it is a Ghul.Pipes combinator and so | |
| 176 | // a stage worth teaching the fuser. | |
| 177 | boundary_function: Semantic.Symbols.Function? | |
| 178 | ||
| 179 | // A `for` needs a stage to fuse. Its expression is whatever the | |
| 180 | // loop iterates, so accepting a chain of no stages here would take | |
| 181 | // every `for` in every program through the fused loop rather than | |
| 182 | // the ordinary one - a change to how all iteration is emitted, | |
| 183 | // which is not this path's to make. | |
| 184 | recognize(`for: Trees.Statements.FOR) -> PIPE_FUSION? => | |
| 185 | recognize_free_function_chain(`for.expression, false) | |
| 186 | ||
| 187 | // Peel a chain of `Ghul.Pipes` free functions off `expression`, for | |
| 188 | // a consumer, which fuses over a chain of no stages as well: a bare | |
| 189 | // `xs |> sum()` has nothing between the consumer and its source. | |
| 190 | recognize_any(expression: Trees.Expressions.Expression?) -> PIPE_FUSION? => | |
| 191 | recognize_free_function_chain(expression, true) | |
| 192 | ||
| 193 | // Peel a `... |> map(f) |> filter(p)` chain of `Ghul.Pipes` free | |
| 194 | // functions off an arbitrary expression. `|>` is desugared entirely | |
| 195 | // at parse time into an ordinary CALL with the threaded value | |
| 196 | // inserted as argument 0, so by the time this pass runs `xs |> | |
| 197 | // map(f)` is indistinguishable from `map(xs, f)` - a plain | |
| 198 | // global-function call resolved once via ordinary overload | |
| 199 | // resolution. | |
| 200 | // | |
| 201 | // Soundness, dispatch: `Ghul.Pipes.map`/`filter`/`take`/`skip` are | |
| 202 | // global functions with no receiver, so a call to one is never a | |
| 203 | // member access and never reaches an overridden `Pipe[T].map`/ | |
| 204 | // `filter` - fused or not, whatever the source's static or | |
| 205 | // dynamic type. | |
| 206 | // | |
| 207 | // A source that is itself a Pipe also fuses, because a | |
| 208 | // thread-first chain is routinely written straight off a | |
| 209 | // generator or a `stream`. The loop reads it through a fresh | |
| 210 | // iterator, as a plain `for` does. | |
| 211 | recognize_free_function_chain(expression: Trees.Expressions.Expression?) -> PIPE_FUSION? => | |
| 212 | recognize_free_function_chain(expression, true) | |
| 213 | ||
| 214 | recognize_free_function_chain(expression: Trees.Expressions.Expression?, allow_no_stages: bool) -> PIPE_FUSION? is | |
| 215 | if !expression? then | |
| 216 | decline_reason = "no-expression" | |
| 217 | ||
| 218 | return null | |
| 219 | fi | |
| 220 | ||
| 221 | let stages = LIST[PIPE_FUSION_STAGE]() | |
| 222 | let roles = LIST[string]() | |
| 223 | ||
| 224 | let current mut = expression | |
| 225 | let calls mut = 0 | |
| 226 | ||
| 227 | while isa Trees.Expressions.CALL(current) do | |
| 228 | let call = cast Trees.Expressions.CALL(current) | |
| 229 | ||
| 230 | let stage = _classify_free_function_stage(call) | |
| 231 | ||
| 232 | if !stage? then | |
| 233 | break | |
| 234 | fi | |
| 235 | ||
| 236 | calls = calls + 1 | |
| 237 | roles.add(_last_role ?? "?") | |
| 238 | ||
| 239 | // A memo stage is elided rather than fused: the chain | |
| 240 | // fuses as though it were absent (see PIPE_FUSION_STAGE). | |
| 241 | if !stage.is_noop then | |
| 242 | stages.add(stage) | |
| 243 | fi | |
| 244 | ||
| 245 | current = call.arguments.expressions[0] | |
| 246 | od | |
| 247 | ||
| 248 | // An expression that peeled no stage is still a chain of no | |
| 249 | // stages, which a consumer fuses over directly: the loop reads | |
| 250 | // the source and applies the consumer, as the stage-free path | |
| 251 | // already did for a chain whose only stage was a memo. Whatever | |
| 252 | // the source turns out to be - a local, a call, a generator - | |
| 253 | // the loop reads it through one fresh iterator, exactly as the | |
| 254 | // unfused consumer would. A `for` declines it instead, keeping | |
| 255 | // ordinary iteration on the lowering it has always had. | |
| 256 | if !allow_no_stages /\ calls == 0 then | |
| 257 | decline_reason = "not-a-chain" | |
| 258 | ||
| 259 | return null | |
| 260 | fi | |
| 261 | ||
| 262 | let joined = System.Text.StringBuilder() | |
| 263 | ||
| 264 | for role in roles do | |
| 265 | if joined.length > 0 then | |
| 266 | joined.append(",") | |
| 267 | fi | |
| 268 | ||
| 269 | joined.append(role) | |
| 270 | od | |
| 271 | ||
| 272 | peeled_roles = joined.to_string() | |
| 273 | ||
| 274 | let source = current | |
| 275 | let source_value = source.value | |
| 276 | ||
| 277 | if !source_value? \/ !source_value.type? then | |
| 278 | decline_reason = "source-not-compiled" | |
| 279 | ||
| 280 | return null | |
| 281 | fi | |
| 282 | ||
| 283 | return PIPE_FUSION(source, stages) | |
| 284 | si | |
| 285 | ||
| 286 | // Classify `call` as a fusible `Ghul.Pipes` free-function stage - | |
| 287 | // map, filter, take, skip or index, or a `memo` stage that is | |
| 288 | // recognised only to be elided - by comparing the resolved call | |
| 289 | // target against the fusible-combinator symbols, so what fuses | |
| 290 | // follows the function the call bound rather than how it spells | |
| 291 | // itself. Returns null for any other function, which stops the | |
| 292 | // peel loop and leaves the call as an ordinary, unfused | |
| 293 | // expression - still correct, since an unrecognised stage drives | |
| 294 | // its own result through its own iterator exactly as the unfused | |
| 295 | // lowering would. | |
| 296 | _classify_free_function_stage(call: Trees.Expressions.CALL) -> PIPE_FUSION_STAGE? is | |
| 297 | let value = call.value | |
| 298 | ||
| 299 | if !isa IR.Values.Call.GLOBAL(value) then | |
| 300 | return null | |
| 301 | fi | |
| 302 | ||
| 303 | let global_call = cast IR.Values.Call.GLOBAL(value) | |
| 304 | let role: string mut | |
| 305 | ||
| 306 | if !fusion_functions.try_get_value(global_call.function.root_specialized_from, role ref) then | |
| 307 | boundary_function = global_call.function | |
| 308 | ||
| 309 | return null | |
| 310 | fi | |
| 311 | ||
| 312 | _last_role = role | |
| 313 | boundary_function = null | |
| 314 | ||
| 315 | let arguments = call.arguments.expressions | |
| 316 | ||
| 317 | if role =~ "memo" then | |
| 318 | if arguments.count != 1 then | |
| 319 | return null | |
| 320 | fi | |
| 321 | ||
| 322 | return PIPE_FUSION_STAGE() | |
| 323 | fi | |
| 324 | ||
| 325 | // `index` comes in both arities: from zero, or from a start | |
| 326 | // the caller supplies. The stage carries the call's own type, | |
| 327 | // which is where the INDEXED_VALUE it builds per element is | |
| 328 | // read from rather than reconstructed. | |
| 329 | if role =~ "index" then | |
| 330 | let chain_type = value.type | |
| 331 | ||
| 332 | if arguments.count == 1 then | |
| 333 | return PIPE_FUSION_STAGE(chain_type, null) | |
| 334 | elif arguments.count == 2 then | |
| 335 | return PIPE_FUSION_STAGE(chain_type, arguments[1]) | |
| 336 | fi | |
| 337 | ||
| 338 | ||
| 339 | return null | |
| 340 | fi | |
| 341 | ||
| 342 | if arguments.count != 2 then | |
| 343 | return null | |
| 344 | fi | |
| 345 | ||
| 346 | if role =~ "map" \/ role =~ "filter" then | |
| 347 | return PIPE_FUSION_STAGE(role =~ "filter", arguments[1]) | |
| 348 | fi | |
| 349 | ||
| 350 | if role =~ "take" \/ role =~ "skip" then | |
| 351 | return PIPE_FUSION_STAGE(role =~ "take", role =~ "skip", arguments[1]) | |
| 352 | fi | |
| 353 | ||
| 354 | // A consumer role - the peel loop's source boundary, which is | |
| 355 | // where a chain ends rather than where one fails. | |
| 356 | ||
| 357 | return null | |
| 358 | si | |
| 359 | si | |
| 360 | si |