diff --git a/azkaban-exec-server/src/main/java/azkaban/dag/DagBuilder.java b/azkaban-exec-server/src/main/java/azkaban/dag/DagBuilder.java
index fed5a75..d920594 100644
--- a/azkaban-exec-server/src/main/java/azkaban/dag/DagBuilder.java
+++ b/azkaban-exec-server/src/main/java/azkaban/dag/DagBuilder.java
@@ -21,6 +21,7 @@ import static java.util.Objects.requireNonNull;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
+import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
@@ -69,14 +70,100 @@ public class DagBuilder {
* @return the Dag reflecting the current state of the DagBuilder
*/
public Dag build() {
+ checkCircularDependencies();
final Dag dag = new Dag(this.name, this.dagProcessor);
final Map<NodeBuilder, Node> builderNodeMap = createBuilderToNodeMap(dag);
updateNodesRelationships(builderNodeMap);
- // todo HappyRay: circular dependency detection.
return dag;
}
/**
+ * Checks if the builder contains nodes that form a circular dependency ring.
+ *
+ * <p>The depth first algorithm is described in this article
+ * <a href="https://en.wikipedia.org/wiki/Topological_sorting">https://en.wikipedia.org/wiki/Topological_sorting</a>
+ * </p>
+ *
+ * @throws DagException if true
+ */
+ private void checkCircularDependencies() {
+ class CircularDependencyChecker {
+
+ // The nodes that need to be visited
+ private final Set<NodeBuilder> toVisit = new HashSet<>(DagBuilder.this.builders);
+
+ // The nodes that have finished traversing all their parent nodes
+ private final Set<NodeBuilder> finished = new HashSet<>();
+
+ // The nodes that are waiting for their parent nodes to finish visit.
+ private final Set<NodeBuilder> ongoing = new HashSet<>();
+
+ // One sample of nodes that form a circular dependency
+ private final List<NodeBuilder> 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 NodeBuilder 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 NodeBuilder removeOneNodeFromToVisitSet() {
+ final Iterator<NodeBuilder> iterator = this.toVisit.iterator();
+ final NodeBuilder 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 NodeBuilder 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 NodeBuilder 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();
+ }
+
+ /**
* Creates nodes using information stored in the current list of builders.
*
* <p>New nodes are created here to ensure they don't change even if their corresponding
diff --git a/azkaban-exec-server/src/test/java/azkaban/dag/DagBuilderTest.java b/azkaban-exec-server/src/test/java/azkaban/dag/DagBuilderTest.java
index 132aa83..2bc1b29 100644
--- a/azkaban-exec-server/src/test/java/azkaban/dag/DagBuilderTest.java
+++ b/azkaban-exec-server/src/test/java/azkaban/dag/DagBuilderTest.java
@@ -80,6 +80,27 @@ public class DagBuilderTest {
}
@Test
+ public void build_should_throw_exception_when_circular_dependency_is_detected() {
+ // given
+ final NodeBuilder nodeBuilder1 = createNodeBuilder("nb1");
+ final NodeBuilder nodeBuilder2 = createNodeBuilder("nb2");
+ final NodeBuilder nodeBuilder3 = createNodeBuilder("nb3");
+ nodeBuilder2.addParents(nodeBuilder1);
+ nodeBuilder3.addParents(nodeBuilder2);
+ nodeBuilder1.addParents(nodeBuilder3);
+
+ // when
+ final Throwable thrown = catchThrowable(() -> {
+ this.dagBuilder.build();
+ });
+
+ // then
+ // Expect the exception message to show the loop: nb1 -> nb2 -> nb3 -> nb1.
+ System.out.println("Expect exception: " + thrown);
+ assertThat(thrown).isInstanceOf(DagException.class);
+ }
+
+ @Test
public void add_dependency_should_not_affect_dag_already_built() {
// given
final Dag dag = this.dagBuilder.build();
