Package ghidra.app.plugin.assembler.sleigh.sem

Class AssemblyTreeResolver

java.lang.Object

ghidra.app.plugin.assembler.sleigh.sem.AssemblyTreeResolver

public class AssemblyTreeResolver
extends Object

The workhorse of semantic resolution for the assembler

This class takes a parse tree and some additional information (start address, context, etc.) and attempts to determine possible encodings using the semantics associated with each branch of the given parse tree. Details of this process are described in SleighAssemblerBuilder.

See Also:

• SleighAssemblerBuilder

Field Summary

Fields

Change	Modifier and Type	Field	Description
NEW	protected final Address	at
	protected final AssemblyPatternBlock	context
	protected final AssemblyContextGraph	ctxGraph
NEW	protected static final DbgTimer	DBG
	protected final AssemblyGrammar	grammar
	static final String	INST_NEXT
NEW	static final String	INST_NEXT2
	static final String	INST_START
	protected final SleighLanguage	lang
NEW	protected static final RecursiveDescentSolver	SOLVER
	protected final AssemblyParseBranch	tree
	protected final Map<String,Long>	vals
REMOVED		solver()	Removed
REMOVED		dbg()	Removed
REMOVED		instStart()	Removed

Constructor Summary

Constructors

Change	Constructor	Description
	AssemblyTreeResolver(SleighLanguage lang, Address at, AssemblyParseBranch tree, AssemblyPatternBlock context, AssemblyContextGraph ctxGraph)	Construct a resolver for the given parse tree

Method Summary

Change	Modifier and Type	Method	Description
NEW	protected AssemblyResolutionResults	applyMutations(AssemblyConstructorSemantic sem, AssemblyResolutionResults temp)	TODO: This is currently used only for resolving recursion.
NEW	protected AssemblyResolutionResults	applyPatterns(AssemblyConstructorSemantic sem, int shift, AssemblyResolutionResults temp)	TODO: This is currently used only for resolving recursion.
	protected AssemblyResolutionResults	applyRecursionPath(Deque<AssemblyConstructorSemantic> path, AssemblyParseBranch branch, AssemblyProduction rec, AssemblyResolvedPatterns child)	Apply constructors as indicated by a path returned by the context resolution graph
NEW	static int	computeOffset(OperandSymbol opsym, Constructor cons)	Compute the offset of an operand encoded in the instruction block
NEW	protected AssemblyResolutionResults	filterByDisassembly(AssemblyResolutionResults temp)	Filter out results that get disassembled differently than assembled
NEW	protected AssemblyResolutionResults	filterForbidden(AssemblyResolutionResults temp)	Filter out results that would certainly be disassembled differently than assembled
NEW	protected AbstractAssemblyStateGenerator<?>	getHiddenStateGenerator(OperandSymbol opSym, AssemblyResolvedPatterns fromLeft)	Get the state generator for a hidden operand
NEW	protected AssemblyProduction	getRootRecursion()	If applicable, get the I => I production of the grammar
NEW	protected AbstractAssemblyStateGenerator<?>	getStateGenerator(OperandSymbol opSym, AssemblyParseTreeNode node, AssemblyResolvedPatterns fromLeft)	Get the state generator for a given operand and parse tree node
NEW	protected AssemblyResolutionResults	parent(String description, AssemblyResolutionResults temp, int opCount)	TODO: Can this be factored?
	AssemblyResolutionResults	resolve()	Resolve the tree for the given parameters
NEW	protected AssemblyResolutionResults	resolvePatterns(AssemblyConstructorSemantic sem, int shift, AssemblyResolutionResults fromChildren)	Apply a constructor pattern
NEW	protected AssemblyResolutionResults	resolvePendingBackfills(AssemblyResolutionResults temp)	Attempt a second time to solve operands and context changes
NEW	AssemblyResolutionResults	resolveRootRecursion(AssemblyResolutionResults temp)	If necessary, resolve recursive constructors at the root, usually for prefixes
NEW	protected AssemblyResolutionResults	selectContext(AssemblyResolutionResults temp)	Filter out results whose context do not match that requested
	protected static AssemblyResolution	solveOrBackfill(PatternExpression exp, long goal, int bits, Map<String,Long> vals, AssemblyResolvedPatterns cur, String description)	Attempt to solve an expression
	protected static AssemblyResolution	solveOrBackfill(PatternExpression exp, long goal, Map<String,Long> vals, AssemblyResolvedPatterns cur, String description)	Attempt to solve an expression
	protected static AssemblyResolution	solveOrBackfill(PatternExpression exp, MaskedLong goal, Map<String,Long> vals, AssemblyResolvedPatterns cur, String description)	Attempt to solve an expression
	protected AssemblyResolutionResults	tryResolveBackfills(AssemblyResolutionResults results)	TODO: This is currently used only for resolving recursion.
REMOVED	AssemblyResolutionResults	resolveBranch(AssemblyParseBranch branch)	Removed
REMOVED	AssemblyResolutionResults	resolveBranchRecursive(AssemblyParseBranch branch, AssemblyProduction rec)	Removed
REMOVED	AssemblyResolutionResults	resolveBranchNonRecursive(AssemblyParseBranch branch)	Removed

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

SOLVER NEW

protected static final RecursiveDescentSolver SOLVER

DBG NEW

protected static final DbgTimer DBG

INST_START

public static final String INST_START

See Also:

• Constant Field Values

INST_NEXT

public static final String INST_NEXT

See Also:

• Constant Field Values

INST_NEXT2 NEW

public static final String INST_NEXT2

See Also:

• Constant Field Values

lang

protected final SleighLanguage lang

at NEW

protected final Address at

vals

protected final Map<String,Long> vals

tree

protected final AssemblyParseBranch tree

grammar

protected final AssemblyGrammar grammar

context

protected final AssemblyPatternBlock context

ctxGraph

protected final AssemblyContextGraph ctxGraph

Constructor Details

AssemblyTreeResolver

public AssemblyTreeResolver(SleighLanguage lang,
 Address at,
 AssemblyParseBranch tree,
 AssemblyPatternBlock context,
 AssemblyContextGraph ctxGraph)

Construct a resolver for the given parse tree

Parameters:

lang -

at - the address where the instruction will start

tree - the parse tree

context - the context expected at instStart

ctxGraph - the context transition graph used to resolve purely-recursive productions

Method Details

resolve

public AssemblyResolutionResults resolve()

Resolve the tree for the given parameters

Returns:

a set of resolutions (encodings and errors)

getRootRecursion NEW

protected AssemblyProduction getRootRecursion()

If applicable, get the I => I production of the grammar

Returns:

the production

resolveRootRecursion NEW

public AssemblyResolutionResults resolveRootRecursion(AssemblyResolutionResults temp)

If necessary, resolve recursive constructors at the root, usually for prefixes

If there are no pure recursive constructors at the root, then this simply returns temp unmodified.

Parameters:

temp - the resolved root results

Returns:

the results with pure recursive constructors applied to obtain a compatible context

resolvePendingBackfills NEW

protected AssemblyResolutionResults resolvePendingBackfills(AssemblyResolutionResults temp)

Attempt a second time to solve operands and context changes

Backfills that depended on inst_next should now easily be solved, since the instruction length is now known.

Parameters:

temp - the resolved results, with backfill pending

Returns:

the results without backfill, possible with new errors

selectContext NEW

protected AssemblyResolutionResults selectContext(AssemblyResolutionResults temp)

Filter out results whose context do not match that requested

Parameters:

temp - the results whose contexts have not yet been checked

Returns:

the results that pass. Those that do not are replaced with errors.

filterForbidden NEW

protected AssemblyResolutionResults filterForbidden(AssemblyResolutionResults temp)

Filter out results that would certainly be disassembled differently than assembled

Because of constructor precedence rules, it is possible to assemble a pattern from a prototype that would not result in equivalent disassembly. This can be detected in some cases via the "forbids" mechanism, where more specific constructors are recorded with the result. If the generated pattern matches on of those more-specific constructors, it is forbidden.

Parameters:

temp - the results whose forbids have not yet been checked

Returns:

the results that pass. Those that do not are replaced with errors.

filterByDisassembly NEW

protected AssemblyResolutionResults filterByDisassembly(AssemblyResolutionResults temp)

Filter out results that get disassembled differently than assembled

The forbids mechanism is not perfect, so as a final fail safe, we disassemble the result and compare the prototypes.

Parameters:

temp - the results whose disassemblies have not yet been checked

Returns:

the results that pass. Those that do not are replaced with errors.

getStateGenerator NEW

protected AbstractAssemblyStateGenerator<?> getStateGenerator(OperandSymbol opSym,
 AssemblyParseTreeNode node,
 AssemblyResolvedPatterns fromLeft)

Get the state generator for a given operand and parse tree node

Parameters:

opSym - the operand symbol

node - the corresponding parse tree node, possibly null indicating a hidden operand

fromLeft - the accumulated patterns from the left sibling or parent

Returns:

the generator

getHiddenStateGenerator NEW

protected AbstractAssemblyStateGenerator<?> getHiddenStateGenerator(OperandSymbol opSym,
 AssemblyResolvedPatterns fromLeft)

Get the state generator for a hidden operand

Parameters:

opSym - the operand symbol

fromLeft - the accumulated patterns from the left sibling or parent

Returns:

the generator

resolvePatterns NEW

protected AssemblyResolutionResults resolvePatterns(AssemblyConstructorSemantic sem,
 int shift,
 AssemblyResolutionResults fromChildren)

Apply a constructor pattern

TODO: This is currently used only for resolving recursion. Could this be factored with AssemblyConstructState.resolve(AssemblyResolvedPatterns, Collection)?

Parameters:

sem - the SLEIGH constructor

shift - the shift

fromChildren - the results from the single resolved child

Returns:

the results

parent NEW

protected AssemblyResolutionResults parent(String description,
 AssemblyResolutionResults temp,
 int opCount)

TODO: Can this be factored?

applyMutations NEW

protected AssemblyResolutionResults applyMutations(AssemblyConstructorSemantic sem,
 AssemblyResolutionResults temp)

TODO: This is currently used only for resolving recursion. Could this be factored with AssemblyConstructState.resolveMutations(AssemblyResolvedPatterns, Collection)?

applyPatterns NEW

protected AssemblyResolutionResults applyPatterns(AssemblyConstructorSemantic sem,
 int shift,
 AssemblyResolutionResults temp)

TODO: This is currently used only for resolving recursion. Could this be factored with AssemblyConstructState.resolvePatterns(AssemblyResolvedPatterns, Collection)?

applyRecursionPath

protected AssemblyResolutionResults applyRecursionPath(Deque<AssemblyConstructorSemantic> path,
 AssemblyParseBranch branch,
 AssemblyProduction rec,
 AssemblyResolvedPatterns child)

Apply constructors as indicated by a path returned by the context resolution graph

NOTE: The given path will be emptied during processing.

Parameters:

path - the path to apply

branch - the branch corresponding to the production whose LHS has a purely-recursive definition.

rec - the purely-recursive production

child - the intermediate result to apply the constructors to

Returns:

the results

tryResolveBackfills

protected AssemblyResolutionResults tryResolveBackfills(AssemblyResolutionResults results)

TODO: This is currently used only for resolving recursion. It seems its missing from the refactor?

computeOffset NEW

public static int computeOffset(OperandSymbol opsym,
 Constructor cons)

Compute the offset of an operand encoded in the instruction block

TODO: Currently, there are duplicate mechanisms for resolving a constructor: 1) The newer mechanism implemented in AssemblyConstructState, and 2) the older one implemented in applyPatterns(AssemblyConstructorSemantic, int, AssemblyResolutionResults). The latter seems to require this method, since it does not have pre-computed shifts as in the former. We should probably remove the latter in favor of the former....

Parameters:

opsym - the operand symbol

cons - the constructor containing the operand

Returns:

the offset (right shift) to apply to the encoded operand

solveOrBackfill

protected static AssemblyResolution solveOrBackfill(PatternExpression exp,
 MaskedLong goal,
 Map<String,Long> vals,
 AssemblyResolvedPatterns cur,
 String description)

Attempt to solve an expression

Parameters:

exp - the expression to solve

goal - the desired value of the expression

vals - any defined symbols

cur - the resolved constructor so far

description - a description of the result

Returns:

the encoded solution, or a backfill record

solveOrBackfill

protected static AssemblyResolution solveOrBackfill(PatternExpression exp,
 long goal,
 Map<String,Long> vals,
 AssemblyResolvedPatterns cur,
 String description)

Attempt to solve an expression

Converts the given goal to a fully-defined MaskedLong and then solves as before.

See Also:

• solveOrBackfill(PatternExpression, MaskedLong, Map, AssemblyResolvedPatterns, String)

solveOrBackfill

protected static AssemblyResolution solveOrBackfill(PatternExpression exp,
 long goal,
 int bits,
 Map<String,Long> vals,
 AssemblyResolvedPatterns cur,
 String description)

Attempt to solve an expression

Converts the given goal and bits count to a MaskedLong and then solves as before. As a special case, if bits == 0, the goal is considered fully-defined (as if bits == 64).

See Also:

• solveOrBackfill(PatternExpression, MaskedLong, Map, AssemblyResolvedPatterns, String)