Package com.crawljax.core.state

Class InMemoryStateFlowGraph

java.lang.Object

com.crawljax.core.state.InMemoryStateFlowGraph

All Implemented Interfaces:

StateFlowGraph, Serializable

@Singleton
public class InMemoryStateFlowGraph
extends Object
implements Serializable, StateFlowGraph

The State-Flow Graph is a multi-edge directed graph with states (StateVertex) on the vertices and clickables (Eventable) on the edges.

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field	Description
private ExitNotifier	exitNotifier
private List<Eventable>	expiredEdges
private List<StateVertex>	expiredStates
private static org.slf4j.Logger	LOG
private AtomicInteger	nextStateNameCounter
private Lock	readLock
private org.jgrapht.graph.AbstractBaseGraph<StateVertex,Eventable>	sfg
private Map<Integer,StateVertex>	stateById
private AtomicInteger	stateCounter	Intermediate counter for the number of states, not relaying on getAllStates.size() because of Thread-safety.
private StateVertexFactory	vertexFactory
private Lock	writeLock

Constructor Summary

Constructors

Constructor	Description
InMemoryStateFlowGraph(ExitNotifier exitNotifier, StateVertexFactory vertexFactory)	The constructor.

Method Summary

Modifier and Type	Method	Description
boolean	addEdge(StateVertex sourceVertex, StateVertex targetVertex, Eventable clickable)	Adds the specified edge to this graph, going from the source vertex to the target vertex.
boolean	canGoTo(StateVertex source, StateVertex target)	Is it possible to go from s1 -> s2?
private boolean	cyclic(Set<String> visitedStates, Set<StateVertex> outgoingSet)
com.google.common.collect.ImmutableSet<Eventable>	getAllEdges()	Return all the edges in the StateFlowGraph.
List<List<org.jgrapht.GraphPath<StateVertex,Eventable>>>	getAllPossiblePaths(StateVertex index)	This method returns all possible paths from the index state using the k-shortest paths.
com.google.common.collect.ImmutableSet<StateVertex>	getAllStates()	Return all the states in the StateFlowGraph.
StateVertex	getById(int id)
private List<StateVertex>	getDeepStates(StateVertex state)
List<Eventable>	getExpiredEdges()
List<StateVertex>	getExpiredStates()
com.google.common.collect.ImmutableSet<Eventable>	getIncomingClickable(StateVertex stateVertex)	Returns a set of all edges incoming into the specified vertex.
StateVertex	getInitialState()
int	getMeanStateStringSize()
private String	getNewStateName(int id)
int	getNumberOfStates()
com.google.common.collect.ImmutableSet<Eventable>	getOutgoingClickables(StateVertex stateVertex)	Returns a set of all clickables outgoing from the specified vertex.
com.google.common.collect.ImmutableSet<StateVertex>	getOutgoingStates(StateVertex stateVertex)
com.google.common.collect.ImmutableList<Eventable>	getShortestPath(StateVertex start, StateVertex end)	Convenience method to find the Dijkstra shortest path between two states on the graph.
private StateVertex	getStateInGraph(StateVertex state)
boolean	hasClone(StateVertex vertex)	Adding assignment to dynamic fragments in case the vertex is hybridstate vertex
StateVertex	newStateFor(String url, String dom, String strippedDom, EmbeddedBrowser browser)
StateVertex	putIfAbsent(StateVertex stateVertex)	Adds a state (as a vertex) to the State-Flow Graph if not already present.
private StateVertex	putIfAbsent(StateVertex stateVertex, boolean correctName)	Adds a state (as a vertex) to the State-Flow Graph if not already present.
StateVertex	putIndex(StateVertex index)
boolean	removeEdge(Eventable event)
boolean	removeState(StateVertex state)
boolean	restoreEdge(Eventable event)
boolean	restoreState(StateVertex state)
private void	setNearDuplicate(StateVertex vertex)
String	toString()
private void	traverse(Set<String> visitedStates, List<StateVertex> deepStates, StateVertex state)

Methods inherited from class java.lang.Object

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

Field Detail

LOG

private static final org.slf4j.Logger LOG

sfg

private final org.jgrapht.graph.AbstractBaseGraph<StateVertex,Eventable> sfg

readLock

private final Lock readLock

writeLock

private final Lock writeLock

stateCounter

private final AtomicInteger stateCounter

Intermediate counter for the number of states, not relaying on getAllStates.size() because of Thread-safety.

nextStateNameCounter

private final AtomicInteger nextStateNameCounter

stateById

private final Map<Integer,StateVertex> stateById

exitNotifier

private final ExitNotifier exitNotifier

vertexFactory

private final StateVertexFactory vertexFactory

expiredEdges

private final List<Eventable> expiredEdges

expiredStates

private final List<StateVertex> expiredStates

Constructor Detail

InMemoryStateFlowGraph

@Inject
public InMemoryStateFlowGraph(ExitNotifier exitNotifier,
                              StateVertexFactory vertexFactory)

The constructor.

Parameters:

exitNotifier - used for triggering an exit.

Method Detail

getExpiredEdges

public List<Eventable> getExpiredEdges()

getExpiredStates

public List<StateVertex> getExpiredStates()

putIfAbsent

public StateVertex putIfAbsent(StateVertex stateVertex)

Adds a state (as a vertex) to the State-Flow Graph if not already present. More formally, adds the specified vertex, v, to this graph if this graph contains no vertex u such that u.equals(v). If this graph already contains such vertex, the call leaves this graph unchanged and returns false. In combination with the restriction on constructors, this ensures that graphs never contain duplicate vertices. Throws java.lang.NullPointerException - if the specified vertex is null. This method automatically updates the state name to reflect the internal state counter.

Parameters:

stateVertex - the state to be added.

Returns:

the clone if one is detected null otherwise.

See Also:

Graph.addVertex(Object)

putIndex

public StateVertex putIndex(StateVertex index)

putIfAbsent

private StateVertex putIfAbsent(StateVertex stateVertex,
                                boolean correctName)

Adds a state (as a vertex) to the State-Flow Graph if not already present. More formally, adds the specified vertex, v, to this graph if this graph contains no vertex u such that u.equals(v). If this graph already contains such vertex, the call leaves this graph unchanged and returns false. In combination with the restriction on constructors, this ensures that graphs never contain duplicate vertices. Throws java.lang.NullPointerException - if the specified vertex is null.

Parameters:

stateVertex - the state to be added.

correctName - if true the name of the state will be corrected according to the internal state counter.

Returns:

the clone if one is detected null otherwise.

See Also:

Graph.addVertex(Object)

setNearDuplicate

private void setNearDuplicate(StateVertex vertex)

hasClone

public boolean hasClone(StateVertex vertex)

Adding assignment to dynamic fragments in case the vertex is hybridstate vertex

Specified by:

hasClone in interface StateFlowGraph

getById

public StateVertex getById(int id)

Specified by:

getById in interface StateFlowGraph

Parameters:

id - The ID of the state

Returns:

The state if found or null.

getInitialState

public StateVertex getInitialState()

Specified by:

getInitialState in interface StateFlowGraph

Returns:

The index state.

addEdge

public boolean addEdge(StateVertex sourceVertex,
                       StateVertex targetVertex,
                       Eventable clickable)

Adds the specified edge to this graph, going from the source vertex to the target vertex. More formally, adds the specified edge, e, to this graph if this graph contains no edge e2 such that e2.equals(e). If this graph already contains such an edge, the call leaves this graph unchanged and returns false. Some graphs do not allow edge-multiplicity. In such cases, if the graph already contains an edge from the specified source to the specified target, than this method does not change the graph and returns false. If the edge was added to the graph, returns true. The source and target vertices must already be contained in this graph. If they are not found in graph IllegalArgumentException is thrown.

Parameters:

sourceVertex - source vertex of the edge.

targetVertex - target vertex of the edge.

clickable - the clickable edge to be added to this graph.

Returns:

true if this graph did not already contain the specified edge.

See Also:

Graph.addEdge(Object, Object, Object)

toString

public String toString()

Overrides:

toString in class Object

getOutgoingClickables

public com.google.common.collect.ImmutableSet<Eventable> getOutgoingClickables(StateVertex stateVertex)

Description copied from interface: StateFlowGraph

Returns a set of all clickables outgoing from the specified vertex.

Specified by:

getOutgoingClickables in interface StateFlowGraph

Parameters:

stateVertex - the state vertex.

Returns:

a set of the outgoing edges (clickables) of the stateVertex.

getIncomingClickable

public com.google.common.collect.ImmutableSet<Eventable> getIncomingClickable(StateVertex stateVertex)

Description copied from interface: StateFlowGraph

Returns a set of all edges incoming into the specified vertex.

Specified by:

getIncomingClickable in interface StateFlowGraph

Parameters:

stateVertex - the state vertex.

Returns:

a set of the incoming edges (clickables) of the stateVertex.

canGoTo

public boolean canGoTo(StateVertex source,
                       StateVertex target)

Description copied from interface: StateFlowGraph

Is it possible to go from s1 -> s2?

Specified by:

canGoTo in interface StateFlowGraph

Parameters:

source - the source state.

target - the target state.

Returns:

true if it is possible (edge exists in graph) to go from source to target.

getShortestPath

public com.google.common.collect.ImmutableList<Eventable> getShortestPath(StateVertex start,
                                                                          StateVertex end)

Description copied from interface: StateFlowGraph

Convenience method to find the Dijkstra shortest path between two states on the graph.

Specified by:

getShortestPath in interface StateFlowGraph

Parameters:

start - the start state.

end - the end state.

Returns:

a list of shortest path of clickables from the state to the end

getAllStates

public com.google.common.collect.ImmutableSet<StateVertex> getAllStates()

Description copied from interface: StateFlowGraph

Return all the states in the StateFlowGraph.

Specified by:

getAllStates in interface StateFlowGraph

Returns:

all the states on the graph.

getAllEdges

public com.google.common.collect.ImmutableSet<Eventable> getAllEdges()

Description copied from interface: StateFlowGraph

Return all the edges in the StateFlowGraph.

Specified by:

getAllEdges in interface StateFlowGraph

Returns:

a Set of all edges in the StateFlowGraph

getStateInGraph

private StateVertex getStateInGraph(StateVertex state)

getMeanStateStringSize

public int getMeanStateStringSize()

Specified by:

getMeanStateStringSize in interface StateFlowGraph

Returns:

Dom string average size (byte).

getNumberOfStates

public int getNumberOfStates()

Specified by:

getNumberOfStates in interface StateFlowGraph

Returns:

The number of states, currently in the graph.

newStateFor

public StateVertex newStateFor(String url,
                               String dom,
                               String strippedDom,
                               EmbeddedBrowser browser)

getNewStateName

private String getNewStateName(int id)

getAllPossiblePaths

public List<List<org.jgrapht.GraphPath<StateVertex,Eventable>>> getAllPossiblePaths(StateVertex index)

Description copied from interface: StateFlowGraph

This method returns all possible paths from the index state using the k-shortest paths.

Specified by:

getAllPossiblePaths in interface StateFlowGraph

Parameters:

index - the initial state.

Returns:

a list of GraphPath lists.

getDeepStates

private List<StateVertex> getDeepStates(StateVertex state)

Parameters:

state - The starting state.

Returns:

A list of the deepest states (states with no outgoing edges).

traverse

private void traverse(Set<String> visitedStates,
                      List<StateVertex> deepStates,
                      StateVertex state)

cyclic

private boolean cyclic(Set<String> visitedStates,
                       Set<StateVertex> outgoingSet)

getOutgoingStates

public com.google.common.collect.ImmutableSet<StateVertex> getOutgoingStates(StateVertex stateVertex)

Specified by:

getOutgoingStates in interface StateFlowGraph

Parameters:

stateVertex - The source StateVertex

Returns:

a Set of StateVertex that are connected to the source StateVertex via one of the sources outgoing edges.

removeEdge

public boolean removeEdge(Eventable event)

Specified by:

removeEdge in interface StateFlowGraph

restoreEdge

public boolean restoreEdge(Eventable event)

Specified by:

restoreEdge in interface StateFlowGraph

removeState

public boolean removeState(StateVertex state)

Specified by:

removeState in interface StateFlowGraph

restoreState

public boolean restoreState(StateVertex state)

Specified by:

restoreState in interface StateFlowGraph