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