Package org.jenkinsci.plugins.workflow.graphanalysis

Class DepthFirstScanner

java.lang.Object

org.jenkinsci.plugins.workflow.graphanalysis.AbstractFlowScanner

org.jenkinsci.plugins.workflow.graphanalysis.DepthFirstScanner

All Implemented Interfaces:

Iterable<FlowNode>, Iterator<FlowNode>, Filterator<FlowNode>

@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 with FlowGraphWalker - 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

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 needed
protected 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 searches
protected 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 in AbstractFlowScanner.myBlackList removed - none of the filteredHeads are null
protected 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

visited

protected HashSet<FlowNode> visited

Constructor Detail

DepthFirstScanner

public DepthFirstScanner()

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 class AbstractFlowScanner

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 in AbstractFlowScanner.myBlackList removed - none of the filteredHeads are null

Specified by:

setHeads in class AbstractFlowScanner

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 class AbstractFlowScanner

Parameters:

current - Current node to use in generating next value

blackList - Nodes that are not eligible for visiting

Returns:

Next node to visit, or null if we've exhausted the node list