This is an automated email from the ASF dual-hosted git repository.
daim pushed a commit to branch trunk
in repository https://gitbox.apache.org/repos/asf/jackrabbit-oak.git
The following commit(s) were added to refs/heads/trunk by this push:
new 2c702adfcb OAK-11833 : replaced Guava's Traverser with OAK commons
(#2447)
2c702adfcb is described below
commit 2c702adfcba8cc66c56b14a999ac13f6b05d7dc0
Author: Rishabh Kumar <[email protected]>
AuthorDate: Mon Aug 18 19:12:55 2025 +0530
OAK-11833 : replaced Guava's Traverser with OAK commons (#2447)
* OAK-11833 : replaced Guava's Traverser with OAK commons
* OAK-11833 : throw NPE is root node is null
* OAK-11833 : added NPE test for Guava to verify new behaviour with old one
---
.../apache/jackrabbit/oak/commons/Traverser.java | 114 ++++++++++-
.../oak/commons/io/FileTreeTraverser.java | 16 +-
.../jackrabbit/oak/commons/TraverserTest.java | 217 ++++++++++++++++++++-
3 files changed, 324 insertions(+), 23 deletions(-)
diff --git
a/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/Traverser.java
b/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/Traverser.java
index 7ee6fc5cc2..ae240e0b60 100644
--- a/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/Traverser.java
+++ b/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/Traverser.java
@@ -23,11 +23,9 @@ import
org.apache.commons.collections4.iterators.UnmodifiableIterator;
import org.jetbrains.annotations.NotNull;
import java.util.ArrayDeque;
-import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.Iterator;
-import java.util.List;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.function.Function;
@@ -53,12 +51,9 @@ public class Traverser {
@NotNull
public static <T> FluentIterable<T> preOrderTraversal(final T root, final
@NotNull Function<T, Iterable<? extends T>> childExtractor) {
+ Objects.requireNonNull(root, "root must not be null");
Objects.requireNonNull(childExtractor, "Children extractor function
must not be null");
- if (root == null) {
- return FluentIterable.empty();
- }
-
return FluentIterable.of(new Iterable<>() {
@Override
public @NotNull Iterator<T> iterator() {
@@ -123,11 +118,9 @@ public class Traverser {
*/
@NotNull
public static <T> FluentIterable<T> breadthFirstTraversal(final T root,
final @NotNull Function<T, Iterable<? extends T>> childExtractor) {
- Objects.requireNonNull(childExtractor, "Children extractor function
must not be null");
- if (root == null) {
- return FluentIterable.empty();
- }
+ Objects.requireNonNull(root, "root must not be null");
+ Objects.requireNonNull(childExtractor, "Children extractor function
must not be null");
return FluentIterable.of(new Iterable<>() {
@Override
@@ -169,5 +162,106 @@ public class Traverser {
return current;
}
}
+
+ /**
+ * Returns an iterator that traverses a tree structure in post-order. Null
nodes are strictly forbidden.
+ * <p>
+ * In post-order traversal, all children of a node are visited from left
to right, followed by
+ * the node itself. This creates a bottom-up traversal pattern where leaf
nodes are visited first,
+ * then their parents, and finally the root.
+ *
+ * @param <T> the type of value in the tree nodes
+ * @param root the root node of the tree, may be null
+ * @param childExtractor function to extract children from a node, must
not be null
+ * @return an iterator that traverses the tree in post-order
+ * @throws NullPointerException if childExtractor or any child is null
+ */
+ public static <T> FluentIterable<T> postOrderTraversal(final T root, final
Function<T, Iterable<? extends T>> childExtractor) {
+ Objects.requireNonNull(root, "root must not be null");
+ Objects.requireNonNull(childExtractor, "Children extractor function
must not be null");
+
+ return FluentIterable.of(new Iterable<>() {
+ @Override
+ public @NotNull Iterator<T> iterator() {
+ return UnmodifiableIterator.unmodifiableIterator(new
PostOrderIterator<>(root, childExtractor));
+ }
+ });
+ }
+
+ private static final class PostOrderIterator<T> implements Iterator<T> {
+
+ private final Deque<PostOrderNode<T>> stack;
+ private final Function<T, Iterable<? extends T>> childExtractor;
+
+ PostOrderIterator(final T root, final Function<T, Iterable<? extends
T>> childExtractor) {
+ this.childExtractor = childExtractor;
+ this.stack = new ArrayDeque<>();
+ // Start by pushing the leftmost path to initialize
+ pushChildren(root, childExtractor);
+ }
+
+ @Override
+ public boolean hasNext() {
+ return !stack.isEmpty();
+ }
+
+ @Override
+ public T next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException("No more nodes in the tree");
+ }
+
+ while (!stack.isEmpty()) {
+ final PostOrderNode<T> frame = stack.getLast();
+
+ // If there are more children, process the next one first
+ if (frame.childIterator.hasNext()) {
+ // throw NPE if any child is null
+ T nextChild = frame.childIterator.next();
+ Objects.requireNonNull(nextChild, "Child nodes must not be
null");
+
+ pushChildren(nextChild, childExtractor);
+ continue; // Continue the loop to get the next leaf
+ }
+
+ // No more children, remove this node (post-order behavior)
+ stack.removeLast();
+ return frame.node;
+ }
+
+ throw new AssertionError("Should not reach here");
+ }
+
+ private void pushChildren(final T node, final Function<T, Iterable<?
extends T>> childExtractor) {
+
+ // Iteratively go down the leftmost path
+ T current = node;
+ Objects.requireNonNull(node, "node must not be null");
+ while (current != null) {
+ Iterator<? extends T> childItr =
childExtractor.apply(current).iterator();
+ stack.addLast(new PostOrderNode<>(current, childItr));
+
+ // Move to the leftmost child if available
+ // Check for null child IMMEDIATELY when retrieving it
+ if (childItr.hasNext()) {
+ T child = childItr.next();
+ // This validation needs to happen here, before any other
processing
+ current = Objects.requireNonNull(child, "Child nodes must
not be null");
+ } else {
+ current = null;
+ }
+ }
+ }
+ }
+
+ private static class PostOrderNode<T> {
+ final T node;
+ final Iterator<? extends T> childIterator;
+
+ PostOrderNode(final T node, final Iterator<? extends T> childItr) {
+ this.node = node;
+ this.childIterator = childItr;
+ }
+ }
}
diff --git
a/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/io/FileTreeTraverser.java
b/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/io/FileTreeTraverser.java
index 8f2468bc70..ffa98f3e67 100644
---
a/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/io/FileTreeTraverser.java
+++
b/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/io/FileTreeTraverser.java
@@ -18,37 +18,37 @@
*/
package org.apache.jackrabbit.oak.commons.io;
-import org.apache.jackrabbit.guava.common.graph.SuccessorsFunction;
-import org.apache.jackrabbit.guava.common.graph.Traverser;
+import org.apache.jackrabbit.oak.commons.Traverser;
import org.jetbrains.annotations.NotNull;
import java.io.File;
import java.util.Arrays;
import java.util.Set;
+import java.util.function.Function;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;
public class FileTreeTraverser {
- private static final FileSystemTree FILE_SYSTEM_TREE = new
FileSystemTree();
+ private static final @NotNull Function<File, Iterable<? extends File>>
FILE_SYSTEM_TREE = new FileSystemTree();
public static Stream<File> depthFirstPostOrder(File startNode) {
- Iterable<File> iterable =
Traverser.forTree(FILE_SYSTEM_TREE).depthFirstPostOrder(startNode);
+ Iterable<File> iterable = Traverser.postOrderTraversal(startNode,
FILE_SYSTEM_TREE);
return StreamSupport.stream(iterable.spliterator(), false);
}
public static Stream<File> breadthFirst(File startNode) {
- Iterable<File> iterable =
Traverser.forTree(FILE_SYSTEM_TREE).breadthFirst(startNode);
+ Iterable<File> iterable = Traverser.breadthFirstTraversal(startNode,
FILE_SYSTEM_TREE);
return StreamSupport.stream(iterable.spliterator(), false);
}
public static Stream<File> depthFirstPreOrder(File startNode) {
- Iterable<File> iterable =
Traverser.forTree(FILE_SYSTEM_TREE).depthFirstPreOrder(startNode);
+ Iterable<File> iterable = Traverser.preOrderTraversal(startNode,
FILE_SYSTEM_TREE);
return StreamSupport.stream(iterable.spliterator(), false);
}
- private static class FileSystemTree implements SuccessorsFunction<File> {
+ private static class FileSystemTree implements Function<File, Iterable<?
extends File>> {
@Override
- public @NotNull Iterable<? extends File> successors(File file) {
+ public @NotNull Iterable<? extends File> apply(File file) {
if (!file.isDirectory()) {
return Set.of();
}
diff --git
a/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/TraverserTest.java
b/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/TraverserTest.java
index fed2ccad45..64f8087310 100644
---
a/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/TraverserTest.java
+++
b/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/TraverserTest.java
@@ -20,7 +20,6 @@
package org.apache.jackrabbit.oak.commons;
import org.apache.jackrabbit.guava.common.collect.TreeTraverser;
-import org.apache.commons.collections4.FluentIterable;
import org.jetbrains.annotations.NotNull;
import org.junit.Assert;
import org.junit.Test;
@@ -61,8 +60,7 @@ public class TraverserTest {
@Test
public void testPreOrderTraversalWithNullRoot() {
- FluentIterable<Node> result = Traverser.preOrderTraversal(null,
Node::getChildren);
- Assert.assertTrue(result.isEmpty());
+ Assert.assertThrows(NullPointerException.class, () ->
Traverser.preOrderTraversal(null, Node::getChildren));
}
@Test
@@ -164,6 +162,19 @@ public class TraverserTest {
Assert.fail("Shouldn't reach here");
}
+ // TODO remove this test when we remove guava dependency
+ @Test(expected = NullPointerException.class)
+ public void testPreOrderTraversalWithNullChildrenWithGuava() {
+ // A tree with some null children
+ Node root = new Node(1,
+ null,
+ new Node(3));
+
+
traverser.preOrderTraversal(root).transform(Node::getValue).forEach(System.out::println);
+
+ Assert.fail("Shouldn't reach here");
+ }
+
@Test
public void testBreadthFirstTraversalWithNormalTree() {
// Create a simple tree structure:
@@ -230,8 +241,7 @@ public class TraverserTest {
@Test
public void testBreadthFirstTraversalWithNullRoot() {
- FluentIterable<Node> result = Traverser.breadthFirstTraversal(null,
Node::getChildren);
- Assert.assertTrue(result.isEmpty());
+ Assert.assertThrows(NullPointerException.class, () ->
Traverser.breadthFirstTraversal(null, Node::getChildren));
}
@Test
@@ -280,6 +290,19 @@ public class TraverserTest {
Assert.fail("Shouldn't reach here");
}
+ // TODO remove this test when we remove guava dependency
+ @Test(expected = NullPointerException.class)
+ public void testBreadthFirstTraversalWithNullChildrenWithGuava() {
+ // A tree with some null children
+ Node root = new Node(1,
+ null,
+ new Node(3));
+
+
traverser.breadthFirstTraversal(root).transform(Node::getValue).forEach(System.out::println);
+
+ Assert.fail("Shouldn't reach here");
+ }
+
@Test
public void testBreadthFirstTraversalWithNullChildExtractor() {
Node root = new Node(1);
@@ -348,10 +371,193 @@ public class TraverserTest {
Assert.assertEquals(result,
traverser.breadthFirstTraversal(root).transform(Node::getValue).toList());
}
+ @Test
+ public void testPostOrderTraversalWithNormalTree() {
+ // Create a simple tree structure:
+ // 1
+ // / \
+ // 2 3
+ // / \ / \
+ // 4 5 6 7
+ Node root = new Node(1,
+ new Node(2,
+ new Node(4),
+ new Node(5)),
+ new Node(3,
+ new Node(6),
+ new Node(7)));
+
+ List<Integer> result = Traverser.postOrderTraversal(root,
Node::getChildren)
+ .transform(Node::getValue)
+ .toList();
+
+ // In post-order: visit left subtree, right subtree, then root
+ Assert.assertEquals(Arrays.asList(4, 5, 2, 6, 7, 3, 1), result);
+ }
+
+ @Test
+ public void testPostOrderTraversalWithNullRoot() {
+ Assert.assertThrows(NullPointerException.class, () ->
Traverser.postOrderTraversal(null, Node::getChildren));
+ Assert.assertThrows(NullPointerException.class, () ->
traverser.postOrderTraversal(null));
+ }
+
+ @Test
+ public void testPostOrderTraversalWithSingleNode() {
+ Node root = new Node(1);
+ List<Integer> result = Traverser.postOrderTraversal(root,
Node::getChildren)
+ .transform(Node::getValue)
+ .toList();
+
+ Assert.assertEquals(Collections.singletonList(1), result);
+ }
+
+ @Test
+ public void testPostOrderTraversalWithAsymmetricTree() {
+ // Create an asymmetric tree:
+ // 1
+ // / \
+ // 2 3
+ // / \
+ // 4 7
+ // \
+ // 5
+ Node root = new Node(1,
+ new Node(2,
+ new Node(4,
+ new Node(5))),
+ new Node(3,
+ new Node(7)));
+
+ List<Integer> result = Traverser.postOrderTraversal(root,
Node::getChildren)
+ .transform(Node::getValue)
+ .toList();
+
+ // In post-order: visit children before parent
+ Assert.assertEquals(Arrays.asList(5, 4, 2, 7, 3, 1), result);
+ }
+
+ @Test
+ public void testPostOrderTraversalWithNullChildExtractor() {
+ Node root = new Node(1);
+ Assert.assertThrows(NullPointerException.class, () ->
Traverser.postOrderTraversal(root, null));
+ }
+
+ @Test(expected = NullPointerException.class)
+ public void testPostOrderTraversalWithNullChildren() {
+ // A tree with some null children
+ Node root = new Node(1,
+ null,
+ new Node(3));
+
+ Traverser.postOrderTraversal(root,
Node::getChildren).transform(Node::getValue).forEach(System.out::println);
+
+ Assert.fail("Shouldn't reach here");
+ }
+
+ // TODO remove this test when we remove guava dependency
+ @Test(expected = NullPointerException.class)
+ public void testPostOrderTraversalWithNullChildrenWithGuava() {
+ // A tree with some null children
+ Node root = new Node(1,
+ null,
+ new Node(3));
+
+
traverser.postOrderTraversal(root).transform(Node::getValue).forEach(System.out::println);
+
+ Assert.fail("Shouldn't reach here");
+ }
+
+ @Test
+ public void testPostOrderTraversalWithDeepTree() {
+ // Create a deep tree with many levels (linked-list-like)
+ Node n1 = new Node(1);
+ Node n2 = new Node(2);
+ Node n3 = new Node(3);
+ Node n4 = new Node(4);
+ Node n5 = new Node(5);
+
+ n1.addChild(n2);
+ n2.addChild(n3);
+ n3.addChild(n4);
+ n4.addChild(n5);
+
+ List<Integer> result = Traverser.postOrderTraversal(n1,
Node::getChildren)
+ .transform(Node::getValue)
+ .toList();
+
+ // In post-order: deepest nodes first
+ Assert.assertEquals(Arrays.asList(5, 4, 3, 2, 1), result);
+ }
+
+ @Test
+ public void testPostOrderTraversalWithBinarySearchTree() {
+ // Create a binary search tree structure
+ // 4
+ // / \
+ // 2 6
+ // / \ / \
+ // 1 3 5 7
+ Node root = new Node(4,
+ new Node(2,
+ new Node(1),
+ new Node(3)),
+ new Node(6,
+ new Node(5),
+ new Node(7)));
+
+ List<Integer> result = Traverser.postOrderTraversal(root,
Node::getChildren).transform(Node::getValue).toList();
+ Assert.assertEquals(Arrays.asList(1, 3, 2, 5, 7, 6, 4), result);
+ }
+
+ @Test
+ public void testPostOrderTraversalWithTree() {
+ // Create a tree structure
+ // 4
+ // / \
+ // 0,2 6
+ // / \
+ // 1,3,5 7,8,9
+ Node root = new Node(4,
+ new Node(0),
+ new Node(2,
+ new Node(1),
+ new Node(3),
+ new Node(5)),
+ new Node(6,
+ new Node(7),
+ new Node(8),
+ new Node(9)));
+
+ List<Integer> result = Traverser.postOrderTraversal(root,
Node::getChildren)
+ .transform(Node::getValue)
+ .toList();
+
+ // In post-order: left subtree, right subtree, root
+ Assert.assertEquals(Arrays.asList(0, 1, 3, 5, 2, 7, 8, 9, 6, 4),
result);
+ }
+
+ // TODO remove this test when we remove guava dependency
+ @Test
+ public void testPostOrderTraversalWithRandomTree() {
+
+ final Node root = getRoot(10000);
+
+ List<Integer> result = Traverser.postOrderTraversal(root,
Node::getChildren)
+ .transform(Node::getValue)
+ .toList();
+
+ // In post-order: left subtree, right subtree, root
+ final List<Integer> guavaTraversal = new ArrayList<>(10000);
+
org.apache.jackrabbit.guava.common.graph.Traverser.forTree(Node::getChildren).depthFirstPostOrder(root).forEach(n
-> guavaTraversal.add(n.value));
+ Assert.assertEquals(result, guavaTraversal);
+ }
+
// Helper class for testing tree traversal
+
private static class Node {
private final int value;
private final List<Node> children = new ArrayList<>();
+
public Node(int value, Node... children) {
this.value = value;
this.children.addAll(Arrays.asList(children));
@@ -375,6 +581,7 @@ public class TraverserTest {
}
}
+
private @NotNull Node getRoot(final int count) {
final Node root = new Node(4);
