Expand description
Matching a set of rules against a term.
Design: spec/10-backend.md section 10.2 and spec/optimizer/13-rewrite-rules.md. The rules
themselves are rule files, one per rule set, and the automaton they compile into is generated
by rucc-rules when the crate that owns the file is built. What is here is the walk over
that automaton, which is the same walk for every rule set and is written once.
§Why this is at the bottom of the stack
Two crates match with a generated table and neither can see the other. rucc-codegen lowers
IR to machine terms and rucc-opt rewrites IR to IR, and a lowering and a rewrite are the
same claim about two terms, so they are the same trie and the same walk. Putting the walk
here rather than in either of them is what keeps that true rather than merely intended, and
it costs nothing: none of this knows what an instruction is, what a value is, or what C is.
§What a subject is
A rule matches a term, and the compiler does not have terms: it has a function full of
instructions, and what a pattern is about is one of them and whatever it was computed from.
So the walk is written against Subject, which is the three questions the automaton asks
of whatever it is matching, and a caller answers them out of the IR without building a term
to be thrown away. A test can answer them out of anything at all, which is what the tests at
the bottom of this file do.
§What a match gives back
The rule that fired and what its pattern bound, in the order the pattern binds it. The
bindings are positions rather than names because that is what the walk has, and the rule
carries the names for anything that has to say what it did. Building the replacement out of
Piece belongs to the caller rather than to this file, because what a replacement becomes
is a machine instruction in one crate and an IR instruction in the other, and this module is
about matching.
§A name written twice
A pattern may write one name in two places, which is how x & x is said. The second place
becomes Test::Same rather than a hole, and it asks the subject whether the two are the
same thing rather than comparing nodes, because a node is a place and two places can hold one
value. It is a concrete test, so it is tried before the wildcard for the same reason every
other test is: a rule about one value in both operands is more specific than a rule about any
two.
§Order
At every node the concrete tests are tried before the branch that takes anything, so a rule
naming an operand is tried before a rule taking whatever is there. That is the maximal munch
spec/10-backend.md asks for, and it falls out of the shape of the trie rather than being
sorted for. Among rules that are equally specific the first one written wins.
A guard is part of deciding whether a rule fires, so a rule whose guard is false is a rule that did not match, and the walk carries on looking rather than giving up. What that costs is the search from where the guard failed, which is the price of a guard being allowed to be about the values rather than only about the shape.
Structs§
- Match
- What a successful match found.
- Node
- One node of the trie over the patterns.
- Rule
- One rule, as much of it as matching needs.
- Table
- A set of rules, as an automaton over their patterns.
Enums§
Traits§
- Subject
- The bits of a term the automaton asks about.
Type Aliases§
- Guard
- A condition on the constants a pattern matched.