srdatalog.ir.core.strategy

Strategy combinators for IR rewrite walks.

Lifted from Stratego (Visser, Program Transformation with Stratego/XT). The idea: a strategy is a partial function Op -> Op | None where None means “the strategy didn’t apply at this op.” Strategies compose via combinators — seq, choice, try_, repeat, top_down, bottom_up, all_, one. The composition is total, deterministic, and pure.

Why strategies and not ad-hoc walkers:

• Composable: rewrite logic is built from named combinators rather than re-implementing tree traversal in every pass.

• Pure: each strategy is a function. No mutable rewriter objects. Unlike MLIR’s PatternRewriter, strategies don’t carry hidden state.

• Confluence-friendly: applying top_down(repeat(rule)) is a standard idiom; correctness arguments lift directly from the term-rewriting literature.

Children of an Op are discovered generically: any field whose value is an Op or a list/tuple of Ops is considered a child. This is the “scrap your boilerplate” lesson — generic traversal beats per-op visitor methods.

References: Visser, “Strategic pattern matching”, RTA 1999. Visser & Benaissa, “A core language for rewriting”, FroCoS 1998. Lämmel & Peyton Jones, “Scrap your boilerplate”, TLDI 2003.

Module Contents

Functions

all_	Apply s to every immediate child of the op. Fails if s fails on any child (Stratego semantics: all is “all-or-nothing”).
bottom_up	Apply s at every descendant, then at the root (postorder). Equivalent to seq(all_(bottom_up(s)), try_(s)).
choice	Apply s1. If it fails, apply s2 to the original op.
fail	The failing strategy. Always returns None.
id_	The identity strategy. Always succeeds, returning the op unchanged.
one	Apply s to exactly one immediate child of the op (the first that succeeds). Fails if s fails on every child.
repeat	Apply s to fixpoint (until it fails or returns the same op).
seq	Apply s1, then s2 to the result. Fails if either fails.
some	Apply s to as many immediate children as it succeeds on. Fails if s fails on every child.
top_down	Apply s at the root, then recursively at every descendant (preorder). Equivalent to try_(seq(s, all_(top_down(s)))).
try_	Apply s. If it fails, return the op unchanged. Always succeeds.

Data

Strategy
T

API

srdatalog.ir.core.strategy.Strategy

None

srdatalog.ir.core.strategy.T

‘TypeVar(…)’

srdatalog.ir.core.strategy.all_(s: srdatalog.ir.core.strategy.Strategy) → srdatalog.ir.core.strategy.Strategy

Apply s to every immediate child of the op. Fails if s fails on any child (Stratego semantics: all is “all-or-nothing”).

Returns a new op with transformed children, or None if any child transformation failed.

srdatalog.ir.core.strategy.bottom_up(s: srdatalog.ir.core.strategy.Strategy) → srdatalog.ir.core.strategy.Strategy

Apply s at every descendant, then at the root (postorder). Equivalent to seq(all_(bottom_up(s)), try_(s)).

srdatalog.ir.core.strategy.choice(s1: srdatalog.ir.core.strategy.Strategy, s2: srdatalog.ir.core.strategy.Strategy) → srdatalog.ir.core.strategy.Strategy

Apply s1. If it fails, apply s2 to the original op.

srdatalog.ir.core.strategy.fail(_op: srdatalog.ir.core.ops.Op) → srdatalog.ir.core.ops.Op | None

The failing strategy. Always returns None.

srdatalog.ir.core.strategy.id_(op: srdatalog.ir.core.ops.Op) → srdatalog.ir.core.ops.Op

The identity strategy. Always succeeds, returning the op unchanged.

srdatalog.ir.core.strategy.one(s: srdatalog.ir.core.strategy.Strategy) → srdatalog.ir.core.strategy.Strategy

Apply s to exactly one immediate child of the op (the first that succeeds). Fails if s fails on every child.

srdatalog.ir.core.strategy.repeat(s: srdatalog.ir.core.strategy.Strategy, max_iters: int = 1024) → srdatalog.ir.core.strategy.Strategy

Apply s to fixpoint (until it fails or returns the same op).

max_iters guards against non-terminating rewrites; when reached, raises RuntimeError. In the standard term-rewriting literature this bound is implicit; we make it explicit since Python doesn’t have a natural confluence proof.

srdatalog.ir.core.strategy.seq(s1: srdatalog.ir.core.strategy.Strategy, s2: srdatalog.ir.core.strategy.Strategy) → srdatalog.ir.core.strategy.Strategy

Apply s1, then s2 to the result. Fails if either fails.

srdatalog.ir.core.strategy.some(s: srdatalog.ir.core.strategy.Strategy) → srdatalog.ir.core.strategy.Strategy

Apply s to as many immediate children as it succeeds on. Fails if s fails on every child.

srdatalog.ir.core.strategy.top_down(s: srdatalog.ir.core.strategy.Strategy) → srdatalog.ir.core.strategy.Strategy

Apply s at the root, then recursively at every descendant (preorder). Equivalent to try_(seq(s, all_(top_down(s)))).

srdatalog.ir.core.strategy.try_(s: srdatalog.ir.core.strategy.Strategy) → srdatalog.ir.core.strategy.Strategy

Apply s. If it fails, return the op unchanged. Always succeeds.