Class DepthFirstScanner
- java.lang.Object
-
- org.jenkinsci.plugins.workflow.graphanalysis.AbstractFlowScanner
-
- org.jenkinsci.plugins.workflow.graphanalysis.DepthFirstScanner
-
@NotThreadSafe public class DepthFirstScanner extends AbstractFlowScanner
Does a simple and somewhat efficient depth-first search of all FlowNodes in the DAG.Iteration order: depth-first search, revisiting parallel branches once done.
The behavior is analogous to
FlowGraphWalker
but faster. With parallel branches, the first branch is explored, then remaining branches are explored in order. This keeps ordering compatibility withFlowGraphWalker
- it can be a drop-in replacement.- Author:
- Sam Van Oort
-
-
Field Summary
Fields Modifier and Type Field Description protected ArrayDeque<FlowNode>
queue
protected HashSet<FlowNode>
visited
-
Fields inherited from class org.jenkinsci.plugins.workflow.graphanalysis.AbstractFlowScanner
MAX_LIST_CHECK_SIZE, myBlackList, myCurrent, myNext
-
-
Constructor Summary
Constructors Constructor Description DepthFirstScanner()
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected FlowNode
next(FlowNode current, Collection<FlowNode> blackList)
Actual meat of the iteration, get the next node to visit, using and updating state as neededprotected boolean
possibleParallelStart(FlowNode f)
protected void
reset()
Reset internal state so that we can begin walking a new flow graph Public APIs need to invoke this before searchesprotected void
setHeads(Collection<FlowNode> heads)
Set up to begin flow scanning using the filteredHeads as starting points This method makes several assumptions: -AbstractFlowScanner.reset()
has already been invoked to reset state - filteredHeads has already had any points inAbstractFlowScanner.myBlackList
removed - none of the filteredHeads are nullprotected boolean
testCandidate(FlowNode f, Collection<FlowNode> blackList)
-
Methods inherited from class org.jenkinsci.plugins.workflow.graphanalysis.AbstractFlowScanner
allNodes, allNodes, convertToFastCheckable, filter, filteredNodes, filteredNodes, filteredNodes, filteredNodes, findFirstMatch, findFirstMatch, findFirstMatch, findFirstMatch, hasNext, iterator, next, remove, setup, setup, setup, setup, visitAll, visitAll
-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Methods inherited from interface java.lang.Iterable
forEach, spliterator
-
Methods inherited from interface java.util.Iterator
forEachRemaining
-
-
-
-
Field Detail
-
queue
protected ArrayDeque<FlowNode> queue
-
-
Method Detail
-
reset
protected void reset()
Description copied from class:AbstractFlowScanner
Reset internal state so that we can begin walking a new flow graph Public APIs need to invoke this before searches- Specified by:
reset
in classAbstractFlowScanner
-
setHeads
protected void setHeads(@NonNull Collection<FlowNode> heads)
Description copied from class:AbstractFlowScanner
Set up to begin flow scanning using the filteredHeads as starting points This method makes several assumptions: -AbstractFlowScanner.reset()
has already been invoked to reset state - filteredHeads has already had any points inAbstractFlowScanner.myBlackList
removed - none of the filteredHeads are null- Specified by:
setHeads
in classAbstractFlowScanner
- Parameters:
heads
- Head nodes that have been filtered against denyList
-
possibleParallelStart
protected boolean possibleParallelStart(FlowNode f)
-
testCandidate
protected boolean testCandidate(FlowNode f, Collection<FlowNode> blackList)
-
next
protected FlowNode next(@NonNull FlowNode current, @NonNull Collection<FlowNode> blackList)
Description copied from class:AbstractFlowScanner
Actual meat of the iteration, get the next node to visit, using and updating state as needed- Specified by:
next
in classAbstractFlowScanner
- Parameters:
current
- Current node to use in generating next valueblackList
- Nodes that are not eligible for visiting- Returns:
- Next node to visit, or null if we've exhausted the node list
-
-