Module cranelift_isle::serialize

Put “sea of nodes” representation of a RuleSet into a sequential order.

We’re trying to satisfy two key constraints on generated code:

First, we must produce the same result as if we tested the left-hand side of every rule in descending priority order and picked the first match. But that would mean a lot of duplicated work since many rules have similar patterns. We want to evaluate in an order that gets the same answer but does as little work as possible.

Second, some ISLE patterns can only be implemented in Rust using a match expression (or various choices of syntactic sugar). Others can only be implemented as expressions, which can’t be evaluated while matching patterns in Rust. So we need to alternate between pattern matching and expression evaluation.

To meet both requirements, we repeatedly partition the set of rules for a term and build a tree of Rust control-flow constructs corresponding to each partition. The root of such a tree is a Block, and serialize constructs it.

Structs

• Block
  A sequence of steps to evaluate in order. Any step may return early, so steps ordered later can assume the negation of the conditions evaluated in earlier steps.
• EvalStep
  A step to evaluate involves possibly let-binding some expressions, then executing some control flow construct.
• MatchArm
  One concrete pattern and the block to evaluate if the pattern matches.

Enums

• ControlFlow
  What kind of control-flow structure do we need to emit here?

Functions

• serialize
  Decomposes the rule-set into a tree of Blocks.