private void checkCircularDependencies ( ) { class CircularDependencyChecker { // The nodes that need to be visited private final Set < Node > toVisit = new HashSet <> ( DagBuilder . this . nameToNodeMap . values ( ) ) ; // The nodes that have finished traversing all their parent nodes private final Set < Node > finished = new HashSet <> ( ) ; // The nodes that are waiting for their parent nodes to finish visit. private final Set < Node > ongoing = new HashSet <> ( ) ; // One sample of nodes that form a circular dependency private final List < Node > sampleCircularNodes = new ArrayList <> ( ) ; /** * Checks if the builder contains nodes that form a circular dependency ring. * * @throws DagException if true */ private void check ( ) { while ( ! this . toVisit . isEmpty ( ) ) { final Node node = removeOneNodeFromToVisitSet ( ) ; if ( checkNode ( node ) ) { final String msg = String . format ( "Circular dependency detected. Sample: %s" , this . sampleCircularNodes ) ; throw new DagException ( msg ) ; } } } /** * Removes one node from the toVisit set and returns that node. * * @return a node */ private Node removeOneNodeFromToVisitSet ( ) { final Iterator < Node > iterator = this . toVisit . iterator ( ) ; final Node node = iterator . next ( ) ; iterator . remove ( ) ; return node ; } /** * Checks if the node is part of a group of nodes that form a circular dependency ring. * * <p>If true, the node will be added to the sampleCircularNodes list</p> * * @param node node to check * @return true if it is */ private boolean checkNode ( final Node node ) { if ( this . finished . contains ( node ) ) { return false ; } if ( this . ongoing . contains ( node ) ) { this . sampleCircularNodes . add ( node ) ; return true ; } this . toVisit . remove ( node ) ; this . ongoing . add ( node ) ; for ( final Node parent : node . getParents ( ) ) { if ( checkNode ( parent ) ) { this . sampleCircularNodes . add ( node ) ; return true ; } } this . ongoing . remove ( node ) ; this . finished . add ( node ) ; return false ; } } final CircularDependencyChecker checker = new CircularDependencyChecker ( ) ; checker . check ( ) ; }
Checks if the builder contains nodes that form a circular dependency ring .