angr.analyses.decompiler.known_patterns.dsl¶
Declarative pattern-AST for describing known AIL code idioms (KnownPatterns).
Pattern nodes are frozen dataclasses that structurally match AIL expressions and
statements. Every node accepts an optional name: a named capture. When the
same capture name occurs more than once in a pattern, all occurrences must bind
.likes()-equal expressions (unification).
Matching is performed by calling PatternNode.match() with a
MatchState (the bindings environment) and a MatchCtx
(matcher-wide flags and callbacks). Match methods are functional: they return a
new MatchState on success and None on failure, so alternatives
(commutative operand orders, PChoice) can backtrack by reusing the
pre-branch state.
- class angr.analyses.decompiler.known_patterns.dsl.MatchState¶
Bases:
objectThe bindings environment threaded through a match attempt.
- bindings: dict[str, Expression]
- remote_defs: tuple[tuple[int, Expression], ...] = ()¶
- skipped_converts: tuple[Convert | Reinterpret, ...] = ()¶
- bind(name, expr)¶
Bind
nametoexpr; on rebind, require.likes()equality.- Return type:
- Parameters:
name (str)
expr (Expression)
- __init__(bindings=<factory>, consumed_stmt_idxs=frozenset({}), chased_defs=(), remote_defs=(), skipped_converts=(), base_aliases=())¶
- class angr.analyses.decompiler.known_patterns.dsl.MatchCtx¶
Bases:
objectMatcher-wide flags and callbacks.
- skip_conversions_at_leaves: bool = False¶
also step over Convert wrappers right above a variable or constant leaf. The exact library keeps this off: its patterns spell out the conversions they expect. A pattern lifted from a selection has had them dropped, since the generator mirrors the structural nodes’ skipping, so it needs the leaves to skip as well or it cannot match the statements it came from.
- __init__(ptr_bits=None, skip_conversions=True, skip_conversions_at_leaves=False, chase_fn=None, peek_fn=None, remote_chase_fn=None, stack_slot_fn=None, call_target_fn=None, next_idx=<function _standalone_idx>, def_fn=None, symbol_addr_fn=None)¶
- Parameters:
ptr_bits (int | None)
skip_conversions (bool)
skip_conversions_at_leaves (bool)
chase_fn (Callable[[int], tuple[int, Expression] | None] | None)
peek_fn (Callable[[int], Expression | None] | None)
remote_chase_fn (Callable[[int], Expression | None] | None)
stack_slot_fn (Callable[[int], VirtualVariable | None] | None)
def_fn (Callable[[int], Expression | None] | None)
- Return type:
None
- class angr.analyses.decompiler.known_patterns.dsl.PatternNode¶
Bases:
objectBase class of all pattern nodes.
- class angr.analyses.decompiler.known_patterns.dsl.PatternExpr¶
Bases:
PatternNodeBase class of expression patterns.
- match(expr, state, ctx)¶
- Return type:
- Parameters:
expr (Expression)
state (MatchState)
ctx (MatchCtx)
- class angr.analyses.decompiler.known_patterns.dsl.PAny¶
Bases:
PatternExprMatches any expression.
- match(expr, state, ctx)¶
- Return type:
- Parameters:
expr (Expression)
state (MatchState)
ctx (MatchCtx)
- class angr.analyses.decompiler.known_patterns.dsl.PVVar¶
Bases:
PatternExprMatches a VirtualVariable.
- match(expr, state, ctx)¶
- Return type:
- Parameters:
expr (Expression)
state (MatchState)
ctx (MatchCtx)
- class angr.analyses.decompiler.known_patterns.dsl.PConst¶
Bases:
PatternExprMatches a Const, by exact value or by predicate. Width is ignored unless
bitsis given (e.g. shift amounts are often 8-bit).- values: frozenset[int] | None = None¶
an enumerable set of acceptable values. Prefer this over
predwhen the set is known: the finder indexes patterns by the constants they accept, so a pattern is only tried where one of its constants occurs.
- symbol: str | None = None¶
the address of this symbol in the binary being matched, resolved through
MatchCtx.symbol_addr_fn; the portable spelling of a global’s address
- match(expr, state, ctx)¶
- Return type:
- Parameters:
expr (Expression)
state (MatchState)
ctx (MatchCtx)
- class angr.analyses.decompiler.known_patterns.dsl.PBinOp¶
Bases:
PatternExprMatches a BinaryOp.
opmay be a single op string or a set of acceptable ops. Commutative ops try both operand orders unlesscommutativeis explicitly False.- operands: tuple[PatternExpr, PatternExpr]
- match(expr, state, ctx)¶
- Return type:
- Parameters:
expr (Expression)
state (MatchState)
ctx (MatchCtx)
- __init__(op, operands, commutative=None, name=None)¶
- Parameters:
operands (tuple[PatternExpr, PatternExpr])
commutative (bool | None)
name (str | None)
- Return type:
None
- class angr.analyses.decompiler.known_patterns.dsl.PUnaryOp¶
Bases:
PatternExprMatches a UnaryOp.
- operand: PatternExpr
- match(expr, state, ctx)¶
- Return type:
- Parameters:
expr (Expression)
state (MatchState)
ctx (MatchCtx)
- class angr.analyses.decompiler.known_patterns.dsl.PConv¶
Bases:
PatternExprMatches a Convert explicitly (never skipped).
- operand: PatternExpr
- match(expr, state, ctx)¶
- Return type:
- Parameters:
expr (Expression)
state (MatchState)
ctx (MatchCtx)
- __init__(operand, from_bits=None, to_bits=None, name=None)¶
- Parameters:
operand (PatternExpr)
from_bits (int | None)
to_bits (int | None)
name (str | None)
- Return type:
None
- class angr.analyses.decompiler.known_patterns.dsl.PReinterpret¶
Bases:
PatternExprMatches a Reinterpret explicitly (never skipped): the bit pattern of a floating-point value read as an integer (
from_type="F"), or an integer’s bits viewed as a floating-point value (from_type="I").- operand: PatternExpr
- match(expr, state, ctx)¶
- Return type:
- Parameters:
expr (Expression)
state (MatchState)
ctx (MatchCtx)
- __init__(operand, from_type=None, name=None)¶
- Parameters:
operand (PatternExpr)
from_type (str | None)
name (str | None)
- Return type:
None
- class angr.analyses.decompiler.known_patterns.dsl.PExtract¶
Bases:
PatternExprMatches an
Extract, a bit-slice of a wider value.This is how a scalar reaches integer code out of a vector register when the 128-bit op did not get narrowed away:
movq %xmm2,%raxon a value that came frommaxsd/mulsdlifts toExtract(vvar_128, 64bits@0)rather than to a Convert. Without a node for it, every libm bit-twiddle whose operand is a computed double rather than an incoming argument is unmatchable.bits/offsetdefault to unconstrained;offsetis in bits.- operand: PatternExpr
- match(expr, state, ctx)¶
- Return type:
- Parameters:
expr (Expression)
state (MatchState)
ctx (MatchCtx)
- __init__(operand, bits=None, offset=None, name=None)¶
- Parameters:
operand (PatternExpr)
bits (int | None)
offset (int | None)
name (str | None)
- Return type:
None
- class angr.analyses.decompiler.known_patterns.dsl.PLoad¶
Bases:
PatternExprMatches a memory Load.
sizeis in bytes.- addr: PatternExpr
- match(expr, state, ctx)¶
- Return type:
- Parameters:
expr (Expression)
state (MatchState)
ctx (MatchCtx)
- __init__(addr, size=None, name=None)¶
- Parameters:
addr (PatternExpr)
size (int | None)
name (str | None)
- Return type:
None
- class angr.analyses.decompiler.known_patterns.dsl.PCall¶
Bases:
PatternExprMatches a
Callwhose callee is one ofnames.The callee is what makes a pattern containing this node self-guarding: an idiom spelled around a named runtime function (
operator deletein the std::string destructor,__ctype_b_locinisspace) cannot be confused with arithmetic that happens to look alike, because no other code calls that function to do something else.namesis matched against every spelling the callee is known by (the raw symbol and its demangled form), so a pattern may name either. Prefer the mangled spelling: it is exact, while a demangled one carries the argument list and varies with the demangler.args=Noneleaves the arguments unconstrained; a tuple constrains them positionally, withNonein a slot meaning “any expression”.- args: tuple[PatternExpr | None, ...] | None = None¶
- match(expr, state, ctx)¶
- Return type:
- Parameters:
expr (Expression)
state (MatchState)
ctx (MatchCtx)
- class angr.analyses.decompiler.known_patterns.dsl.PCallResult¶
Bases:
PatternExprThe value a call to one of
namesreturned.A call’s result is rarely used where it is produced: the compiler assigns it to a register and reads that register, often in another block.
__ctype_b_loc()is called once per function and its table indexed at every predicate. So this node matches the virtual variable and looks up its definition read-only. Nothing is consumed, moved or recomputed; the call stays where the compiler put it.An inline
Callexpression is matched too, for the case where the value is used at its definition.- match(expr, state, ctx)¶
- Return type:
- Parameters:
expr (Expression)
state (MatchState)
ctx (MatchCtx)
- class angr.analyses.decompiler.known_patterns.dsl.PDefOf¶
Bases:
PatternExprinner, or a virtual variable whose reaching definition isinner.The compiler is free to compute a value once and use it twice, and it does so exactly where an idiom uses one value twice.
if (_M_p != &_M_local_buf) operator delete(_M_p, ...)reads _M_p in the compare and in the call, so gcc loads it into a register and the pattern seesLoad(s)in neither place; it sees the same virtual variable in both.Reading that variable’s definition is read-only. Nothing is consumed, moved or recomputed, and the identification stays accurate even if memory changes afterwards: the variable holds what the load produced at the definition, which is what the idiom meant. That is why this is not
peek_fn, whose contract (“can be recomputed at the use”) a load cannot satisfy.The unconsumed definition is left where it was, so a region that matches through this node keeps it as residue. That is harmless, and dead-code elimination removes it once the idiom’s other uses are gone.
- inner: PatternExpr
- match(expr, state, ctx)¶
- Return type:
- Parameters:
expr (Expression)
state (MatchState)
ctx (MatchCtx)
- __init__(inner, name=None)¶
- Parameters:
inner (PatternExpr)
name (str | None)
- Return type:
None
- class angr.analyses.decompiler.known_patterns.dsl.PField¶
Bases:
PatternExprThe address of the field at
offsetinside the object bound tobase.Spelling a container’s fields as
PLoad(PVVar("v"))/PLoad(PVVar("v") + 8)requires the object to sit at the very address held in a virtual variable. That is the minority case: measured over the benchmark corpus, only 10-25% of the DWARF sites for astd::vectoraccessor read the container through a bare pointer; the rest reach it as a field of something else (this->tokens.size()), which lifts toLoad(this + 56)/Load(this + 64)and cannot bindvat all.PFieldmatches such an address and bindsbaseto the object’s own address:rootwhen the object is at offset 0, elseroot + K. Two fields of one object therefore unify onK, which is what keeps the node honest: it replaces the constraint “this displacement is exactly 8” with “these two displacements differ by exactly 8”.Only use it in patterns that reference at least two fields. With a single field there is no second displacement to constrain, so
PLoad(PField("s", 8))degenerates into “any load through a pointer plus a non-negative constant” and matches essentially everything.rootmust be a virtual variable: the outliner materializestmp = root + Kahead of the region so the synthesized call still takes a variable.- base: str
- offset: int
- match(expr, state, ctx)¶
- Return type:
- Parameters:
expr (Expression)
state (MatchState)
ctx (MatchCtx)
- class angr.analyses.decompiler.known_patterns.dsl.PStackField¶
Bases:
PatternExprA field of a container that lives on the stack.
A stack object never reaches the matcher as an object at all: variable recovery has already split it into one virtual variable per slot, so
std::string s;is a handful of independentvvar{s-112},vvar{s-96}and there is noLoad(s)to match and nos + 16to compare against. Measured over the benchmark corpus (kp-eval/stack_share.py), stack objects are 40-54% of the DWARF sites forstd::string::lengthand 15-35% forstd::vector<T>::size.This node matches the slot of the field at
offsetand bindsbaseto the object’s own stack offset, so two fields of one object unify on it exactly asPField’s two displacements do.as_addressmatches the address form (&slot, which lifts toUnaryOp("Reference", vvar)) rather than the value form;std::string::capacityneeds both, since it compares the data pointer against the address of the local buffer.The binding is a
StackBaseOffset, the object’s own address. That is both the thing two fields must agree on and, directly, the argument the synthesized call takes, so nothing has to be materialized for it.Matching is only half the problem, and the other half is why a pattern using this node is never outlined: the region for a stack container reads N independent slots, so its live-ins are N values rather than one pointer and there is nothing for a synthesized callee to take. Such a match is instead rewritten in place: the matched expression, or the whole region, is replaced by
call(&s), whose argument the binding already is. SeeKnownPatternFinder._rewrite_in_placeand_rewrite_graph_in_place.- base: str
- offset: int
- match(expr, state, ctx)¶
- Return type:
- Parameters:
expr (Expression)
state (MatchState)
ctx (MatchCtx)
- class angr.analyses.decompiler.known_patterns.dsl.PPhi¶
Bases:
PatternExprMatches a Phi expression, capturing it whole (its individual sources are not matched). Useful for loop-header blocks, whose statements are phi assignments.
- match(expr, state, ctx)¶
- Return type:
- Parameters:
expr (Expression)
state (MatchState)
ctx (MatchCtx)
- class angr.analyses.decompiler.known_patterns.dsl.PITE¶
Bases:
PatternExprMatches an ITE (ternary) expression
cond ? iftrue : iffalse.Needed because ITERegionConverter (AFTER_GLOBAL_SIMPLIFICATION) collapses
if (c) x = a; else x = b;diamonds into a single ITE assignment before the KnownPatternOutliner runs, so a two-armed value-select idiom reaches the outliner as an expression, not as a PGraphPat region. (A triangle, with one arm empty as in the MSVC std::string::c_str SSO select, is not converted, which is why that idiom is still a PGraphPat.)- cond: PatternExpr
- iftrue: PatternExpr
- iffalse: PatternExpr
- match(expr, state, ctx)¶
- Return type:
- Parameters:
expr (Expression)
state (MatchState)
ctx (MatchCtx)
- __init__(cond, iftrue, iffalse, name=None)¶
- Parameters:
cond (PatternExpr)
iftrue (PatternExpr)
iffalse (PatternExpr)
name (str | None)
- Return type:
None
- class angr.analyses.decompiler.known_patterns.dsl.PChoice¶
Bases:
PatternExprOrdered alternation: matches the first alternative that succeeds.
- alternatives: tuple[PatternExpr, ...]
- __init__(*alternatives)¶
- Parameters:
alternatives (PatternExpr)
- match(expr, state, ctx)¶
- Return type:
- Parameters:
expr (Expression)
state (MatchState)
ctx (MatchCtx)
- class angr.analyses.decompiler.known_patterns.dsl.PatternStmt¶
Bases:
PatternNodeBase class of statement patterns.
- match(stmt, state, ctx)¶
- Return type:
- Parameters:
stmt (Statement)
state (MatchState)
ctx (MatchCtx)
- class angr.analyses.decompiler.known_patterns.dsl.PAssign¶
Bases:
PatternStmtMatches an Assignment statement.
- dst: PatternExpr
- src: PatternExpr
- match(stmt, state, ctx)¶
- Return type:
- Parameters:
stmt (Statement)
state (MatchState)
ctx (MatchCtx)
- __init__(dst, src, *, optional=False, weight=1.0)¶
- Parameters:
dst (PatternExpr)
src (PatternExpr)
optional (bool)
weight (float)
- Return type:
None
- class angr.analyses.decompiler.known_patterns.dsl.PStore¶
Bases:
PatternStmtMatches a Store statement.
sizeis in bytes.- addr: PatternExpr
- value: PatternExpr
- match(stmt, state, ctx)¶
- Return type:
- Parameters:
stmt (Statement)
state (MatchState)
ctx (MatchCtx)
- __init__(addr, value, size=None, *, optional=False, weight=1.0)¶
- Parameters:
addr (PatternExpr)
value (PatternExpr)
size (int | None)
optional (bool)
weight (float)
- Return type:
None
- class angr.analyses.decompiler.known_patterns.dsl.PCallStmt¶
Bases:
PatternStmtMatches a statement whose effect is a call.
Ailment has no Call statement: a call whose result is discarded is a
SideEffectStatementwrapping the Call expression, and one whose result is kept is an ordinaryAssignment. Both spellings are the same idiom, so both match;dst, when given, also constrains the assigned destination, which requires the assignment form.- call: PCall
- dst: PatternExpr | None = None¶
- match(stmt, state, ctx)¶
- Return type:
- Parameters:
stmt (Statement)
state (MatchState)
ctx (MatchCtx)
- __init__(call, dst=None, *, optional=False, weight=1.0)¶
- Parameters:
call (PCall)
dst (PatternExpr | None)
optional (bool)
weight (float)
- Return type:
None
- class angr.analyses.decompiler.known_patterns.dsl.PCondJump¶
Bases:
PatternStmtMatches a ConditionalJump, matching its condition expression.
- condition: PatternExpr
- match(stmt, state, ctx)¶
- Return type:
- Parameters:
stmt (Statement)
state (MatchState)
ctx (MatchCtx)
- __init__(condition, *, optional=False, weight=1.0)¶
- Parameters:
condition (PatternExpr)
optional (bool)
weight (float)
- Return type:
None
- class angr.analyses.decompiler.known_patterns.dsl.PAnyStmt¶
Bases:
PatternStmtMatches any single statement. The statement-level counterpart of
PAny: a placeholder for “something happens here” whose exact form the pattern does not care about.- match(stmt, state, ctx)¶
- Return type:
- Parameters:
stmt (Statement)
state (MatchState)
ctx (MatchCtx)
- class angr.analyses.decompiler.known_patterns.dsl.PReturn¶
Bases:
PatternStmtMatches a Return.
valuesconstrains the returned expressions, one pattern each; None matches a return of any arity.- values: tuple[PatternExpr, ...] | None = None¶
- match(stmt, state, ctx)¶
- Return type:
- Parameters:
stmt (Statement)
state (MatchState)
ctx (MatchCtx)
- __init__(values=None, *, optional=False, weight=1.0)¶
- Parameters:
values (tuple[PatternExpr, ...] | None)
optional (bool)
weight (float)
- Return type:
None
- class angr.analyses.decompiler.known_patterns.dsl.PStmtSeq¶
Bases:
PatternStmtMatches a group of statements within one block. When
ordered(the default), the statement patterns must match in order; withallow_gaps, unrelated statements may sit between the matched ones. Whenorderedis False, the statement patterns match statements of the block in any order (each pattern to a distinct statement), which suits idioms whose statement order the compiler chooses freely (e.g. list-link stores).- stmts: tuple[PatternStmt, ...]
- max_gap: int = 8¶
How many unmatched statements may sit between two matched ones. Without a bound the scan runs to the end of the block from every statement it could start at, quadratic per block per template, and finds nothing: an idiom’s statements are adjacent apart from what the scheduler interleaved, which is a handful of instructions rather than a basic block.
- class angr.analyses.decompiler.known_patterns.dsl.PBlockPat¶
Bases:
PatternNodeA labeled block of statements in a multi-block pattern graph. An empty
stmtssequence matches any block (structure alone identifies it).- label: str
- stmts: PStmtSeq
- class angr.analyses.decompiler.known_patterns.dsl.PGraphPat¶
Bases:
PatternNodeA multi-block pattern: labeled blocks connected by edges.
blocksmaps a label to itsPBlockPat.edgesare(src_label, dst_label)pairs; a destination label that does not appear inblocksdenotes an external successor, a region exit that becomes the Outliner frontier.entryis the label of the single entry block. Captures unify across all blocks (one bindings environment).- entry: str
- angr.analyses.decompiler.known_patterns.dsl.LeafStmt = angr.analyses.decompiler.known_patterns.dsl.PAssign | angr.analyses.decompiler.known_patterns.dsl.PStore | angr.analyses.decompiler.known_patterns.dsl.PCallStmt | angr.analyses.decompiler.known_patterns.dsl.PCondJump | angr.analyses.decompiler.known_patterns.dsl.PReturn | angr.analyses.decompiler.known_patterns.dsl.PAnyStmt¶
The statement patterns that stand for one concrete statement, and so are the ones a fuzzy occurrence can score, skip or weight.
- angr.analyses.decompiler.known_patterns.dsl.iter_stmt_patterns(node)¶
Every leaf statement pattern under
node, in pattern order.
- angr.analyses.decompiler.known_patterns.dsl.has_fuzzy_nodes(node)¶
Whether
nodecan only be matched by the fuzzy matcher.An optional statement has no meaning to the exact matcher, which either finds every statement pattern or fails; a pattern carrying one has to be kept away from it rather than silently matched as if the statement were required.
- Return type:
- Parameters:
node (PatternNode)
- angr.analyses.decompiler.known_patterns.dsl.pattern_anchor_key(node)¶
A cheap discriminator of the pattern root, used to prune candidate patterns at each expression position:
(ail kind, op or None).Returns None when the root is not discriminating (PAny/PChoice/…), in which case the pattern must be attempted everywhere.
- angr.analyses.decompiler.known_patterns.dsl.pattern_index_keys(node)¶
Every
(ail kind, op or None, constant operand or None)an occurrence ofnodecan start with; None when the root is not discriminating.Finer than
pattern_anchor_key()in three ways. A set-valued op is expanded into one key per op rather than dropped to “any op”. A PChoice is the union of its alternatives’ keys, not “anywhere” unless one alternative truly is. And a binary op with a PConst operand whose values are enumerable (valueorvalues) carries each such value as a third component: a PConst only matches a literal Const, so aMul(x, magic)pattern need not be tried at a multiply by any other constant. The generatedstd::vector<T>::sizefamily is a thousand such patterns keyed onMul, and without this every multiply in a function tried all of them.
- angr.analyses.decompiler.known_patterns.dsl.expr_const_operands(expr)¶
The literal constants among a binary op’s operands (through Converts), for the index lookup.
- Return type:
- Parameters:
expr (Expression)
- angr.analyses.decompiler.known_patterns.dsl.stmt_pattern_anchor_key(node)¶
The discriminator of a statement pattern’s first statement.
Statement patterns are anchored at every statement of every block and then scan forward, so trying one that cannot possibly match is the expensive kind of waste. The key is the statement kind plus the anchor key of the expression that carries the pattern’s shape (an assignment’s source, a store’s value), which is what separates
t = *a(a swap) from the assignments that make up most of a block.
- angr.analyses.decompiler.known_patterns.dsl.stmt_anchor_key(stmt)¶
The anchor key of a concrete AIL statement, for pruning.