Repository: james-project Updated Branches: refs/heads/master af4934b63 -> 8437d54e1
JAMES-1713 Graph should throw when loop detected Project: http://git-wip-us.apache.org/repos/asf/james-project/repo Commit: http://git-wip-us.apache.org/repos/asf/james-project/commit/8437d54e Tree: http://git-wip-us.apache.org/repos/asf/james-project/tree/8437d54e Diff: http://git-wip-us.apache.org/repos/asf/james-project/diff/8437d54e Branch: refs/heads/master Commit: 8437d54e1458a716be6016cf2aaf54a57084b63f Parents: af4934b Author: Raphael Ouazana <[email protected]> Authored: Tue Mar 29 15:32:03 2016 +0200 Committer: Raphael Ouazana <[email protected]> Committed: Thu Mar 31 09:43:00 2016 +0200 ---------------------------------------------------------------------- .../james/jmap/utils/DependencyGraph.java | 15 +++++- .../jmap/utils/MailboxHierarchySorter.java | 5 +- .../james/jmap/utils/DependencyGraphTest.java | 55 +++++++++++++++++--- .../jmap/utils/MailboxHierarchySorterTest.java | 23 ++++++++ 4 files changed, 88 insertions(+), 10 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/james-project/blob/8437d54e/server/protocols/jmap/src/main/java/org/apache/james/jmap/utils/DependencyGraph.java ---------------------------------------------------------------------- diff --git a/server/protocols/jmap/src/main/java/org/apache/james/jmap/utils/DependencyGraph.java b/server/protocols/jmap/src/main/java/org/apache/james/jmap/utils/DependencyGraph.java index 96c5ff6..c9b2d2d 100644 --- a/server/protocols/jmap/src/main/java/org/apache/james/jmap/utils/DependencyGraph.java +++ b/server/protocols/jmap/src/main/java/org/apache/james/jmap/utils/DependencyGraph.java @@ -24,6 +24,7 @@ import java.util.function.Function; import java.util.stream.Stream; import org.apache.james.util.streams.Iterators; +import org.jgrapht.alg.CycleDetector; import org.jgrapht.graph.DefaultDirectedGraph; import org.jgrapht.graph.DefaultEdge; import org.jgrapht.graph.builder.DirectedGraphBuilder; @@ -45,12 +46,24 @@ public class DependencyGraph<T> { .map(parentNode -> builder.addEdge(parentNode, item)); } - public Stream<T> getBuildChain() { + public Stream<T> getBuildChain() throws CycleDetectedException { DefaultDirectedGraph<T, DefaultEdge> graph = builder.build(); + ensureNoCycle(graph); return Iterators.toStream(new TopologicalOrderIterator<>(graph)); } + private void ensureNoCycle(DefaultDirectedGraph<T, DefaultEdge> graph) throws CycleDetectedException { + CycleDetector<T, DefaultEdge> cycleDetector = new CycleDetector<>(graph); + if (cycleDetector.detectCycles()) { + throw new CycleDetectedException(); + } + } + public String toString() { return builder.build().toString(); } + + public static class CycleDetectedException extends RuntimeException { + + } } http://git-wip-us.apache.org/repos/asf/james-project/blob/8437d54e/server/protocols/jmap/src/main/java/org/apache/james/jmap/utils/MailboxHierarchySorter.java ---------------------------------------------------------------------- diff --git a/server/protocols/jmap/src/main/java/org/apache/james/jmap/utils/MailboxHierarchySorter.java b/server/protocols/jmap/src/main/java/org/apache/james/jmap/utils/MailboxHierarchySorter.java index 67efd2e..ea12215 100644 --- a/server/protocols/jmap/src/main/java/org/apache/james/jmap/utils/MailboxHierarchySorter.java +++ b/server/protocols/jmap/src/main/java/org/apache/james/jmap/utils/MailboxHierarchySorter.java @@ -25,12 +25,13 @@ import java.util.function.Function; import java.util.stream.Collectors; import org.apache.james.jmap.model.mailbox.Mailbox; +import org.apache.james.jmap.utils.DependencyGraph.CycleDetectedException; import com.google.common.collect.Lists; public class MailboxHierarchySorter { - public List<Mailbox> sortFromRootToLeaf(List<Mailbox> mailboxes) { + public List<Mailbox> sortFromRootToLeaf(List<Mailbox> mailboxes) throws CycleDetectedException { Map<String, Mailbox> mapOfMailboxesById = indexMailboxesById(mailboxes); @@ -47,7 +48,7 @@ public class MailboxHierarchySorter { .collect(Collectors.toMap(Mailbox::getId, Function.identity())); } - public List<Mailbox> sortFromLeafToRoot(List<Mailbox> mailboxes) { + public List<Mailbox> sortFromLeafToRoot(List<Mailbox> mailboxes) throws CycleDetectedException { return Lists.reverse(sortFromRootToLeaf(mailboxes)); } } http://git-wip-us.apache.org/repos/asf/james-project/blob/8437d54e/server/protocols/jmap/src/test/java/org/apache/james/jmap/utils/DependencyGraphTest.java ---------------------------------------------------------------------- diff --git a/server/protocols/jmap/src/test/java/org/apache/james/jmap/utils/DependencyGraphTest.java b/server/protocols/jmap/src/test/java/org/apache/james/jmap/utils/DependencyGraphTest.java index 96c2658..1a66a2e 100644 --- a/server/protocols/jmap/src/test/java/org/apache/james/jmap/utils/DependencyGraphTest.java +++ b/server/protocols/jmap/src/test/java/org/apache/james/jmap/utils/DependencyGraphTest.java @@ -27,6 +27,7 @@ import java.util.Set; import java.util.stream.Collectors; import java.util.stream.Stream; +import org.apache.james.jmap.utils.DependencyGraph.CycleDetectedException; import org.junit.Test; import com.google.common.annotations.VisibleForTesting; @@ -44,8 +45,8 @@ public class DependencyGraphTest { Commit c = new Commit("C", b); DependencyGraph<Commit> graph = new DependencyGraph<>(Commit::getParent); - Set<Commit> mailboxes = ImmutableSet.of(b, a, c); - mailboxes.stream().forEach(graph::registerItem); + Stream.of(b, a, c) + .forEach(graph::registerItem); // When Stream<Commit> orderedMailboxes = graph.getBuildChain(); @@ -83,9 +84,9 @@ public class DependencyGraphTest { Commit d = new Commit("D"); Commit e = new Commit("E", d); Commit f = new Commit("F", d); - List<Commit> input = ImmutableList.of(b, a, e, d, f, c); DependencyGraph<Commit> testee = new DependencyGraph<>(Commit::getParent); - input.stream().forEach(testee::registerItem); + Stream.of(b, a, e, d, f, c) + .forEach(testee::registerItem); //When Stream<Commit> actual = testee.getBuildChain(); @@ -104,9 +105,9 @@ public class DependencyGraphTest { Commit e = new Commit("E", b); Commit f = new Commit("F", c); Commit g = new Commit("G", e); - List<Commit> input = ImmutableList.of(b, a, e, g, d, f, c); DependencyGraph<Commit> testee = new DependencyGraph<>(Commit::getParent); - input.stream().forEach(testee::registerItem); + Stream.of(b, a, e, g, d, f, c) + .forEach(testee::registerItem); //When Stream<Commit> actual = testee.getBuildChain(); @@ -114,11 +115,47 @@ public class DependencyGraphTest { //Then assertThat(actual).extracting(Commit::getMessage).containsExactly("A", "B", "C", "E", "D", "F", "G"); } + + @Test(expected=CycleDetectedException.class) + public void getBuildChainOnTreeWithLoopShouldFail() { + //Given + Commit a = new Commit("A"); + Commit b = new Commit("B", a); + a.setParent(b); + DependencyGraph<Commit> testee = new DependencyGraph<>(Commit::getParent); + Stream.of(a, b) + .forEach(testee::registerItem); + + //When + testee.getBuildChain(); + } + + @Test(expected=CycleDetectedException.class) + public void getBuildChainOnTreeWithComplexLoopShouldFail() { + // a - b + // c - d - e - f + // |___________| + //Given + Commit a = new Commit("A"); + Commit b = new Commit("B", a); + + Commit c = new Commit("C"); + Commit d = new Commit("D", c); + Commit e = new Commit("E", d); + Commit f = new Commit("F", e); + c.setParent(f); + DependencyGraph<Commit> testee = new DependencyGraph<>(Commit::getParent); + Stream.of(a, b, c, d, e, f) + .forEach(testee::registerItem); + + //When + testee.getBuildChain(); + } private static class Commit { private final String message; - private final Optional<Commit> parent; + private Optional<Commit> parent; @VisibleForTesting Commit(String message) { @@ -135,6 +172,10 @@ public class DependencyGraphTest { public Optional<Commit> getParent() { return parent; } + + public void setParent(Commit parent) { + this.parent = Optional.of(parent); + } public String getMessage() { return message; http://git-wip-us.apache.org/repos/asf/james-project/blob/8437d54e/server/protocols/jmap/src/test/java/org/apache/james/jmap/utils/MailboxHierarchySorterTest.java ---------------------------------------------------------------------- diff --git a/server/protocols/jmap/src/test/java/org/apache/james/jmap/utils/MailboxHierarchySorterTest.java b/server/protocols/jmap/src/test/java/org/apache/james/jmap/utils/MailboxHierarchySorterTest.java index 692f038..32f4829 100644 --- a/server/protocols/jmap/src/test/java/org/apache/james/jmap/utils/MailboxHierarchySorterTest.java +++ b/server/protocols/jmap/src/test/java/org/apache/james/jmap/utils/MailboxHierarchySorterTest.java @@ -25,6 +25,7 @@ import java.util.List; import java.util.stream.Collectors; import org.apache.james.jmap.model.mailbox.Mailbox; +import org.apache.james.jmap.utils.DependencyGraph.CycleDetectedException; import org.junit.Test; import com.google.common.collect.ImmutableList; @@ -73,6 +74,17 @@ public class MailboxHierarchySorterTest { assertThat(result).containsExactly("A", "B", "C"); } + @Test(expected=CycleDetectedException.class) + public void sortFromRootToLeafWithLoopShouldThrow() { + Mailbox a = Mailbox.builder().name("A").id("A").parentId("B").build(); + Mailbox b = Mailbox.builder().name("B").id("B").parentId("A").build(); + + MailboxHierarchySorter sut = new MailboxHierarchySorter(); + ImmutableList<Mailbox> input = ImmutableList.of(a, b); + + sut.sortFromRootToLeaf(input); + } + @Test public void sortFromLeafToRootShouldReturnOrderedMailbox() { //Given @@ -113,4 +125,15 @@ public class MailboxHierarchySorterTest { assertThat(result).containsExactly("C", "B", "A"); } + + @Test(expected=CycleDetectedException.class) + public void sortFromLeafToRootWithLoopShouldThrow() { + Mailbox a = Mailbox.builder().name("A").id("A").parentId("B").build(); + Mailbox b = Mailbox.builder().name("B").id("B").parentId("A").build(); + + MailboxHierarchySorter sut = new MailboxHierarchySorter(); + ImmutableList<Mailbox> input = ImmutableList.of(a, b); + + sut.sortFromLeafToRoot(input); + } } \ No newline at end of file --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
