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
  Modifier and Type
  Field
  Description
  `protected final Address`
  `at`
  `protected final AssemblyPatternBlock`
  `context`
  `protected final AssemblyContextGraph`
  `ctxGraph`
  `protected static final DbgTimer`
  `DBG`
  `protected final AssemblyGrammar`
  `grammar`
  `static final String`
  `INST_NEXT`
  `static final String`
  `INST_NEXT2`
  `static final String`
  `INST_START`
  `protected final SleighLanguage`
  `lang`
  `protected static final RecursiveDescentSolver`
  `SOLVER`
  `protected final AssemblyParseBranch`
  `tree`
  `protected final Map<String,Long>`
  `vals`

- ## Constructor Summary

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

- ## Method Summary

  Modifier and Type
  Method
  Description
  `protected AssemblyResolutionResults`
  `applyMutations(AssemblyConstructorSemantic sem, AssemblyResolutionResults temp)`
  TODO: This is currently used only for resolving recursion.
  `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
  `static int`
  `computeOffset(OperandSymbol opsym, Constructor cons)`
  Compute the offset of an operand encoded in the instruction block
  `protected AssemblyResolutionResults`
  `filterByDisassembly(AssemblyResolutionResults temp)`
  Filter out results that get disassembled differently than assembled
  `protected AssemblyResolutionResults`
  `filterForbidden(AssemblyResolutionResults temp)`
  Filter out results that would certainly be disassembled differently than assembled
  `protected AbstractAssemblyStateGenerator<?>`
  `getHiddenStateGenerator(OperandSymbol opSym, AssemblyResolvedPatterns fromLeft)`
  Get the state generator for a hidden operand
  `protected AssemblyProduction`
  `getRootRecursion()`
  If applicable, get the `I => I` production of the grammar
  `protected AbstractAssemblyStateGenerator<?>`
  `getStateGenerator(OperandSymbol opSym, AssemblyParseTreeNode node, AssemblyResolvedPatterns fromLeft)`
  Get the state generator for a given operand and parse tree node
  `protected AssemblyResolutionResults`
  `parent(String description, AssemblyResolutionResults temp, int opCount)`
  TODO: Can this be factored?
  `AssemblyResolutionResults`
  `resolve()`
  Resolve the tree for the given parameters
  `protected AssemblyResolutionResults`
  `resolvePatterns(AssemblyConstructorSemantic sem, int shift, AssemblyResolutionResults fromChildren)`
  Apply a constructor pattern
  `protected AssemblyResolutionResults`
  `resolvePendingBackfills(AssemblyResolutionResults temp)`
  Attempt a second time to solve operands and context changes
  `AssemblyResolutionResults`
  `resolveRootRecursion(AssemblyResolutionResults temp)`
  If necessary, resolve recursive constructors at the root, usually for prefixes
  `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.

  ### Methods inherited from class java.lang.Object

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

- ## Field Details

  - ### SOLVER

    protected static final RecursiveDescentSolver SOLVER

  - ### DBG

    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

    public static final String INST_NEXT2
    See Also:
      - Constant Field Values

  - ### lang

    protected final SleighLanguage lang

  - ### at

    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

    protected AssemblyProduction getRootRecursion()
    If applicable, get the `I => I` production of the grammar
    Returns:
      the production

  - ### resolveRootRecursion

    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

    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

    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

    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

    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

    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

    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

    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

    protected AssemblyResolutionResults parent(String description, AssemblyResolutionResults temp, int opCount)
    TODO: Can this be factored?

  - ### applyMutations

    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

    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

    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)`