Module relate 

Recognising the join a loop already contains.

docs/99-the-data-tier-means-of-combination.md §99.6:

for x in xs: whose body contains map_get(ys, k(x)) is an equi-join […] Recognising the shape and emitting a Join instead of a captured FlatMap would make 27-review.beck and examples/board.beck faster with no edit to either program.

The cost this removes is not a constant. A per-element function that captured the accumulator is a different function on every event, so crate::engine’s rebuild rule reapplies it to every element — a nested-loop join with no index, re-run from scratch per event. 27-review.beck is the corpus program that has one, and it did not know it did.

What is recognised, stated as the condition rather than as the shape

One map_get(m, k) inside the loop’s body, where

• m reads only what the function captured — so the collection being looked up in is a node the plan already has, or can build, rather than something derived per element; and
• k reads only the element — so the join key is a function of the left row alone, which is what makes it an equi-join rather than a predicate.

Both conditions are about which variables an expression reads, so both survive the lookup being written behind a call: 27-review’s is three definitions deep (verdict_for → map_get), and §99.6 forecast that as the case inference would fail on. It does not, because the body is inlined before it is searched — but the limit is real and moved rather than removed, and Refusal is where it is named.

The second shape: a filter that is a lookup into an index nobody built

One filter_list(xs, lambda y: g(y) == k(x)) inside the loop’s body, where

• xs reads only what the function captured, as above;
• g reads only the filtered element, so it is a key the collection can be arranged by; and
• k reads only the loop’s element, so the probe is a function of the left row alone.

That is the same equi-join with a different right side. map_get’s collection is a Map whose own key is the join key, so crate::plan::Op::MapValues’s arrangement already answers it and at most one row comes back. A filter’s collection is keyed by something else entirely, so the index has to be built — crate::plan::Op::ArrangeBy, §99.9 item 3 — and several rows share a key, so what comes back is the group.

The group is the rows the predicate would have kept, in the order the collection held them, because the index’s key is g(y) followed by the collection’s own key and the probe takes the range under g(y). That the two agree at all is a fact about Prim::Eq rather than a convention: == is crate::Value’s own total order compared for equality, which is the order the arrangement is a BTreeMap in.

What this does not do, stated here because the operator’s name promises more. The group is a list, because the expression it replaced was one and its consumer loops over it. So a row added to a group rebuilds that group’s list and no other — the scan over the whole collection is gone and the capture with it, but the group’s own size is still paid. Removing that is group by (§99.9 item 6), which is why item 6 follows this one rather than standing beside it.

The third shape, which is the second one asked a different question

list_len(filter_list(xs, lambda y: g(y) == k(x))) is the same equi-join again, and what differs is only what a probe returns: a number rather than the rows. Nothing about the index changes, so this is a field of the grouped shape (Answers) rather than a shape of its own — and it is the first of §99.9 item 6’s aggregates, the one the language already had a spelling for. A group that is only ever counted is never built, which is what crate::plan::Matching::Count is for.

The fourth shape: a number the group’s rows decide

list_min(filter_list(…)), list_max(…) and list_sum(…), bare or over a map_list of the same filter, are the same question once more — §99.9 item 6’s other three aggregates. What differs from the count is that the answer is a function of what the rows say rather than only of how many there are, so something has to hold what they contribute: crate::plan::Op::GroupBy, keyed by the group and holding per group whatever its aggregate needs — a multiset of the projection, whose two ends are min and max, or a running total, which is sum.

It is the one shape whose index is not an index. The other three probe an arrangement of the collection; this probes an arrangement of the groups, one entry each. For the extremes the join above it is a crate::plan::Matching::Unique — the same probe a map_get gets, Some for a group with rows and None for one without, which is what list_min returns of a list and of an empty one. For a total it is a crate::plan::Matching::Total, and the difference is what a missing entry means: list_sum of no rows is 0, so the probe answers with a value where the extremes answer with an absence.

The fifth shape, which is not a loop at all

filter_list(xs, lambda x: map_contains(m, k(x))) and its negation are the algebra’s intersection and difference by key — crate::plan::Op::Restrict, §99.9 item 7 — and restriction is where they are read. The conditions are the same two conditions again: m reads only what the function captured, k reads only the element.

What differs is where the shape is looked for, and the reason is what comes out of the operator. A join is recognised at a site inside a body, because a loop does other things besides look up and the body has to be rewritten around the row. A restriction has no body to rewrite: it keeps and drops the elements the filter was keeping and dropping, so the predicate is not rewritten, it is deleted. That is also why a filter_list can have this operator when it cannot have a join — a join’s element is a row, and a filter’s consumers read the element.

The cost it removes is the same one, arrived at from the other side. A predicate that reads a collection is a different predicate whenever that collection moves, so crate::engine’s rebuild rule reconsiders every element on every event — a nested-loop anti-join with no index.

Structs

Aggregate

What a group was asked for, and what its rows contribute to the question.

Lookup

One lookup, as the join that answers it.

Membership

One membership test, as the restriction that answers it.

Recognised

A loop whose body looked things up, taken apart.

Enums

Answers

What a body wanted from a group, which decides whether the group has to be built at all.

Index

The index a lookup is answered from — the one difference between the two shapes recognised.

Refusal

Why a body that contained a map_get was not recognised as a join.

Constants

LEFT

The two halves of a joined row, as the field names the rewritten body reads them by.

RIGHT

ROW

The type name the joined row carries. Nothing checks it — the plan runs after the checker — but a value that prints as Join(left=…, right=…) in a panic is worth the four bytes.

Functions

fingerprint

An expression’s shape as a string, so two that are the same expression share one index.

fingerprint_fun

The same, for an expression written over one bound parameter, whose number is written canonically.

recognise

Try to read a loop’s per-element function as a join.

restriction

Try to read a filter’s predicate as a membership test against another collection.