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

# Class AssemblyContextGraph

java.lang.Object
ghidra.app.plugin.assembler.sleigh.sem.AssemblyContextGraph

All Implemented Interfaces:
  `GImplicitDirectedGraph<AssemblyContextGraph.Vertex,AssemblyContextGraph.Edge>`

public class AssemblyContextGraph extends Object implements GImplicitDirectedGraph<AssemblyContextGraph.Vertex,AssemblyContextGraph.Edge>
A graph of possible context changes via the application of various constructors

This is used primarily to find optimal paths for the application of recursive rules, i.e., those of the form I => I. These cannot be resolved without some form of semantic analysis. The most notable disadvantage to all of this is that you no longer get all of the possible assemblies, but only those with the fewest rule applications.

Conceivably, this may also be used to prune some possibilities during semantic resolution of a parse tree. Even better, it may be possible to derive a grammar which accounts for the context changes already; however, it's unclear how many rules this will generate, and consequently, how much larger its LALR(1) parser would become.

- ## Nested Class Summary

  Nested Classes
  Modifier and Type
  Class
  Description
  `protected static class`
  `AssemblyContextGraph.Edge`
  A transition in a context transition graph
  `protected static class`
  `AssemblyContextGraph.Vertex`
  A vertex in a context transition graph

- ## Field Summary

  Fields
  Modifier and Type
  Field
  Description
  `protected final Set<AssemblyContextGraph.Edge>`
  `cachedEdges`
  `protected final Map<AssemblyContextGraph.Vertex,Set<AssemblyContextGraph.Edge>>`
  `cachedOutEdges`
  `protected final Set<AssemblyContextGraph.Vertex>`
  `cachedVertices`
  `protected final DijkstraShortestPathsAlgorithm<AssemblyContextGraph.Vertex,AssemblyContextGraph.Edge>`
  `dijkstra`
  `protected final AbstractAssemblyResolutionFactory<?,?>`
  `factory`
  `protected final AssemblyGrammar`
  `grammar`
  `protected final SleighLanguage`
  `lang`
  `protected final Map<String,Set<AssemblyConstructorSemantic>>`
  `semantics`

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `AssemblyContextGraph(AbstractAssemblyResolutionFactory<?,?> factory, SleighLanguage lang, AssemblyGrammar grammar)`
  Build the context change graph for a given language and grammar

- ## Method Summary

  Modifier and Type
  Method
  Description
  `Collection<Deque<AssemblyConstructorSemantic>>`
  `computeOptimalApplications(AssemblyPatternBlock src, String srcTable, AssemblyPatternBlock dst, String dstTable)`
  Compute the optimal, i.e., shortest, sequences of applications to resolve a given context to another, often the language's default context.
  `protected Set<AssemblyContextGraph.Edge>`
  `computeOutEdges(AssemblyContextGraph.Vertex from)`
  `GDirectedGraph<AssemblyContextGraph.Vertex,AssemblyContextGraph.Edge>`
  `copy()`
  Returns a copy of the graph explored so far
  `protected void`
  `gatherSemantics()`
  Gather all the semantics that can be used as state transitions
  `Collection<AssemblyContextGraph.Edge>`
  `getInEdges(AssemblyContextGraph.Vertex v)`
  This operation is not supported.
  `Collection<AssemblyContextGraph.Edge>`
  `getOutEdges(AssemblyContextGraph.Vertex v)`
  Compute the incident edges that start at the given vertex NOTE: This method ought to return cached results if available NOTE: As part of computing out-edges, this method will also provide successors

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

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

  ### Methods inherited from interface ghidra.graph.GImplicitDirectedGraph

  `getPredecessors, getSuccessors`

- ## Field Details

  - ### factory

    protected final AbstractAssemblyResolutionFactory<?,?> factory

  - ### semantics

    protected final Map<String,Set<AssemblyConstructorSemantic>> semantics

  - ### grammar

    protected final AssemblyGrammar grammar

  - ### lang

    protected final SleighLanguage lang

  - ### dijkstra

    protected final DijkstraShortestPathsAlgorithm<AssemblyContextGraph.Vertex,AssemblyContextGraph.Edge> dijkstra

  - ### cachedVertices

    protected final Set<AssemblyContextGraph.Vertex> cachedVertices

  - ### cachedEdges

    protected final Set<AssemblyContextGraph.Edge> cachedEdges

  - ### cachedOutEdges

    protected final Map<AssemblyContextGraph.Vertex,Set<AssemblyContextGraph.Edge>> cachedOutEdges

- ## Constructor Details

  - ### AssemblyContextGraph

    public AssemblyContextGraph(AbstractAssemblyResolutionFactory<?,?> factory, SleighLanguage lang, AssemblyGrammar grammar)
    Build the context change graph for a given language and grammar

    The grammar must have been constructed from the given language. The language is used just to obtain the most common default context.

    At the moment, this graph only expands the recursive rules at the root constructor table, i.e., "instruction". Thus, the assembler will not be able to process any language that has purely-recursive rules at sub-constructors.

    Parameters:
      `lang` - the language
      `grammar` - the grammar derived from the given language

- ## Method Details

  - ### computeOptimalApplications

    public Collection<Deque<AssemblyConstructorSemantic>> computeOptimalApplications(AssemblyPatternBlock src, String srcTable, AssemblyPatternBlock dst, String dstTable)
    Compute the optimal, i.e., shortest, sequences of applications to resolve a given context to another, often the language's default context.
    Parameters:
      `src` - presumably, the language's default context
      `srcTable` - the name of the SLEIGH constructor table, presumably "instruction"
      `dst` - the context block being resolved
      `dstTable` - the name of the SLEIGH constructor table being resolved
    Returns:
      a collection of sequences of constructor applications from `src` to `dst` NOTE: For assembly, the sequences will need to be applied right-to-left.

  - ### gatherSemantics

    protected void gatherSemantics()
    Gather all the semantics that can be used as state transitions

    Currently, only semantics from `:^instruction` constructors are taken.

  - ### computeOutEdges

    protected Set<AssemblyContextGraph.Edge> computeOutEdges(AssemblyContextGraph.Vertex from)

  - ### getInEdges

    public Collection<AssemblyContextGraph.Edge> getInEdges(AssemblyContextGraph.Vertex v)
    This operation is not supported.

    I could implement this using the cached edges, but that may not be semantically, what a path computation algorithm actually requires. Instead, I will assume the algorithm only explores the graph in the same direction as its edges. If not, I will hear about it quickly.

    Specified by:
      `getInEdges` in interface `GImplicitDirectedGraph<AssemblyContextGraph.Vertex,AssemblyContextGraph.Edge>`
    Parameters:
      `v` - the destination vertex
    Returns:
      the in-edges to the given vertex

  - ### getOutEdges

    public Collection<AssemblyContextGraph.Edge> getOutEdges(AssemblyContextGraph.Vertex v)
    Description copied from interface: `GImplicitDirectedGraph`
    Compute the incident edges that start at the given vertex NOTE: This method ought to return cached results if available NOTE: As part of computing out-edges, this method will also provide successors
    Specified by:
      `getOutEdges` in interface `GImplicitDirectedGraph<AssemblyContextGraph.Vertex,AssemblyContextGraph.Edge>`
    Parameters:
      `v` - the source vertex
    Returns:
      the out-edges from the given vertex

  - ### copy

    public GDirectedGraph<AssemblyContextGraph.Vertex,AssemblyContextGraph.Edge> copy()
    Returns a copy of the graph explored so far
    Specified by:
      `copy` in interface `GImplicitDirectedGraph<AssemblyContextGraph.Vertex,AssemblyContextGraph.Edge>`
    Returns:
      a "copy" of this implicit graph