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 java.lang.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 A transition consists of the constructor whose context changes were applied.
protected static class	AssemblyContextGraph.Vertex	A vertex in a context transition graph Each vertex consists of a context block and a (sub)table name

Field Summary

Fields

Modifier and Type	Field	Description
protected java.util.Set<AssemblyContextGraph.Edge>	cachedEdges
protected java.util.Map<AssemblyContextGraph.Vertex,java.util.Set<AssemblyContextGraph.Edge>>	cachedOutEdges
protected java.util.Set<AssemblyContextGraph.Vertex>	cachedVertices
protected DijkstraShortestPathsAlgorithm<AssemblyContextGraph.Vertex,AssemblyContextGraph.Edge>	dijkstra
protected AssemblyGrammar	grammar
protected SleighLanguage	lang
protected java.util.Map<java.lang.String,java.util.Set<AssemblyConstructorSemantic>>	semantics

Constructor Summary

Constructors

Constructor	Description
AssemblyContextGraph(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.

Method Summary

Modifier and Type	Method	Description
java.util.Collection<java.util.Deque<AssemblyConstructorSemantic>>	computeOptimalApplications(AssemblyPatternBlock src, java.lang.String srcTable, AssemblyPatternBlock dst, java.lang.String dstTable)	Compute the optimal, i.e., fewest, sequences of applications to resolve a given context to the language's default context.
protected java.util.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 Currently, only semantics from :^instruction constructors are taken.
java.util.Collection<AssemblyContextGraph.Edge>	getInEdges(AssemblyContextGraph.Vertex v)	This operation is not supported.
java.util.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 Detail

semantics

protected final java.util.Map<java.lang.String,java.util.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 java.util.Set<AssemblyContextGraph.Vertex> cachedVertices

cachedEdges

protected final java.util.Set<AssemblyContextGraph.Edge> cachedEdges

cachedOutEdges

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

Constructor Detail

AssemblyContextGraph

public AssemblyContextGraph(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 subconstructors.

Parameters:

lang - the language

grammar - the grammar derived from the given language

Method Detail

computeOptimalApplications

public java.util.Collection<java.util.Deque<AssemblyConstructorSemantic>> computeOptimalApplications(AssemblyPatternBlock src,
                                                                                                     java.lang.String srcTable,
                                                                                                     AssemblyPatternBlock dst,
                                                                                                     java.lang.String dstTable)

Compute the optimal, i.e., fewest, sequences of applications to resolve a given context to 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 java.util.Set<AssemblyContextGraph.Edge> computeOutEdges(AssemblyContextGraph.Vertex from)

getInEdges

public java.util.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 java.util.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