This is an automated email from the ASF dual-hosted git repository.
joerghoh 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 840eb75257 OAK-11607 for ordered nodetypes read the child node names
lazily (#2182)
840eb75257 is described below
commit 840eb7525735918ab1f41500810601e35c8f7b74
Author: Jörg Hoh <[email protected]>
AuthorDate: Tue Apr 8 15:37:32 2025 +0200
OAK-11607 for ordered nodetypes read the child node names lazily (#2182)
Co-authored-by: Julian Reschke <[email protected]>
---
.../oak/plugins/tree/impl/AbstractTree.java | 18 +--
.../tree/impl/OrderedChildnameIterator.java | 125 ++++++++++++++++++
.../tree/impl/OrderedChildnameIterableTest.java | 147 +++++++++++++++++++++
.../evaluation/ChildOrderPropertyTest.java | 10 +-
4 files changed, 281 insertions(+), 19 deletions(-)
diff --git
a/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/tree/impl/AbstractTree.java
b/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/tree/impl/AbstractTree.java
index 852e84047a..0b77b63567 100644
---
a/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/tree/impl/AbstractTree.java
+++
b/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/tree/impl/AbstractTree.java
@@ -24,17 +24,13 @@ import static
org.apache.jackrabbit.oak.api.Tree.Status.UNCHANGED;
import static org.apache.jackrabbit.oak.api.Type.NAMES;
import static
org.apache.jackrabbit.oak.plugins.tree.TreeConstants.OAK_CHILD_ORDER;
-import java.util.ArrayList;
import java.util.Iterator;
-import java.util.List;
import java.util.Objects;
-import java.util.Set;
-
import org.apache.jackrabbit.oak.api.PropertyState;
import org.apache.jackrabbit.oak.api.Tree;
import org.apache.jackrabbit.oak.commons.PathUtils;
import org.apache.jackrabbit.oak.commons.collections.IterableUtils;
-import org.apache.jackrabbit.oak.commons.collections.SetUtils;
+import org.apache.jackrabbit.oak.commons.collections.IteratorUtils;
import org.apache.jackrabbit.oak.commons.conditions.Validate;
import org.apache.jackrabbit.oak.plugins.index.IndexConstants;
import
org.apache.jackrabbit.oak.plugins.index.reference.NodeReferenceConstants;
@@ -125,17 +121,7 @@ public abstract class AbstractTree implements Tree {
NodeBuilder nodeBuilder = getNodeBuilder();
PropertyState order = nodeBuilder.getProperty(OAK_CHILD_ORDER);
if (order != null && order.getType() == NAMES) {
- Set<String> names =
SetUtils.toLinkedSet(nodeBuilder.getChildNodeNames());
- List<String> ordered = new ArrayList<>(names.size());
- for (String name : order.getValue(NAMES)) {
- // only include names of child nodes that actually exist
- if (names.remove(name)) {
- ordered.add(name);
- }
- }
- // add names of child nodes that are not explicitly ordered
- ordered.addAll(names);
- return ordered;
+ return IteratorUtils.toIterable(new
OrderedChildnameIterator(order.getValue(NAMES),
nodeBuilder.getChildNodeNames()));
} else {
return nodeBuilder.getChildNodeNames();
}
diff --git
a/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/tree/impl/OrderedChildnameIterator.java
b/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/tree/impl/OrderedChildnameIterator.java
new file mode 100644
index 0000000000..a0bdc6a9a3
--- /dev/null
+++
b/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/tree/impl/OrderedChildnameIterator.java
@@ -0,0 +1,125 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.jackrabbit.oak.plugins.tree.impl;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+
+/**
+ * Return the childrenNames in the order defined by the orderedChildren
iterator, and merges it
+ * with the existing children defined by allChildren.
+ *
+ * This implementation focuses on being as lazy as possible; especially
consuming the
+ * allChildren iterator can be slow.
+ */
+
+public class OrderedChildnameIterator implements Iterator<String>{
+
+ final Iterator<String> orderedChildren;
+ final Iterator<String> allChildren;
+
+ private String nextResult;
+
+ private final List<String> nonOrderedChildren = new ArrayList<>();
+ private Iterator<String> nonOrderedChildrenIterator = null;
+
+ public OrderedChildnameIterator (Iterable<String> orderedChildren,
Iterable<String> allChildren) {
+ this.orderedChildren = orderedChildren == null ?
Collections.emptyIterator() : orderedChildren.iterator();
+ this.allChildren = allChildren.iterator();
+ nextResult = getNextElement();
+ }
+
+ private String getNextElement() {
+ if (orderedChildren.hasNext()) {
+ String elem = getNextOrderedChild();
+ if (elem != null) {
+ return elem;
+ }
+ }
+ // if the flow comes here, all orderedChildren have already been
consumed, and the
+ // nonOrderedChildren list is no longer changed, so it's safe to
create the iterator here
+ if (nonOrderedChildrenIterator == null) {
+ nonOrderedChildrenIterator = nonOrderedChildren.iterator();
+ }
+ // return all children which have already been read into the
nonOrderedChildren list
+ if (nonOrderedChildrenIterator.hasNext()) {
+ return nonOrderedChildrenIterator.next();
+ }
+ // return all children which have not been consumed from the
allChildren iterator
+ if (allChildren.hasNext()) {
+ return allChildren.next();
+ }
+ // all iterators consumed, no children anymore
+ return null;
+ }
+
+ /**
+ * Consume the next element from the orderedChild list and validates that
it's actually present
+ * @return the next ordered child or {code null} if all ordered children
have already been returned
+ */
+ private String getNextOrderedChild() {
+ // check that this element is actually present in the allChildren
iterable
+ while (orderedChildren.hasNext()) {
+ String current = orderedChildren.next();
+ if (isOrderedChildPresent(current)) {
+ return current;
+ }
+ }
+ return null;
+ }
+
+ /**
+ * Check if the provided childname is also provided by the allChildren
iterator.
+ *
+ * Note, that in the pth
+ *
+ *
+ * @param orderedChildName
+ * @return true if childname is a valid child, false otherwise
+ */
+ private boolean isOrderedChildPresent(String orderedChildName) {
+ // read from the allChildren iterator until it's a hit or exhausted
+ while (!nonOrderedChildren.contains(orderedChildName) &&
allChildren.hasNext()) {
+ nonOrderedChildren.add(allChildren.next());
+ }
+ if (nonOrderedChildren.contains(orderedChildName)) {
+ // remove it from the list, as it is returned early
+ nonOrderedChildren.remove(orderedChildName);
+ return true;
+ } else {
+ return false;
+ }
+ }
+
+ @Override
+ public boolean hasNext() {
+ return nextResult != null;
+ }
+
+ @Override
+ public String next() {
+ String n = nextResult;
+ nextResult = getNextElement();
+ return n;
+ }
+
+
+}
diff --git
a/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/tree/impl/OrderedChildnameIterableTest.java
b/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/tree/impl/OrderedChildnameIterableTest.java
new file mode 100644
index 0000000000..4fea79ef55
--- /dev/null
+++
b/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/tree/impl/OrderedChildnameIterableTest.java
@@ -0,0 +1,147 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.jackrabbit.oak.plugins.tree.impl;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+public class OrderedChildnameIterableTest {
+
+ static final List<String> ALL_CHILDREN = List.of("1","2","3","4","5");
+
+ // Track iterator access for testing lazy loading
+ private static class TrackingIterable implements Iterable<String> {
+ private final List<String> elements;
+ private int accessCount = 0;
+ private final List<String> accessedElements = new ArrayList<>();
+
+ TrackingIterable(List<String> elements) {
+ this.elements = elements;
+ }
+
+ @Override
+ public Iterator<String> iterator() {
+ return new Iterator<String>() {
+ private int index = 0;
+
+ @Override
+ public boolean hasNext() {
+ return index < elements.size();
+ }
+
+ @Override
+ public String next() {
+ String element = elements.get(index++);
+ accessCount++;
+ accessedElements.add(element);
+ return element;
+ }
+ };
+ }
+
+ public int getAccessCount() {
+ return accessCount;
+ }
+
+ public List<String> getAccessedElements() {
+ return accessedElements;
+ }
+ }
+
+ List<String> iteratorToList(Iterator<String> iter) {
+ List<String> result = new ArrayList<>();
+ iter.forEachRemaining(result::add);
+ return result;
+ }
+
+ @Test
+ public void noOrderedChildren() {
+ // all children are returned in their order
+ OrderedChildnameIterator iterable = new
OrderedChildnameIterator(List.of(),ALL_CHILDREN);
+ Assert.assertEquals(ALL_CHILDREN, iteratorToList(iterable));
+ }
+
+ @Test
+ public void orderedChildren() {
+ // only 2 child nodes ordered, return them up front
+ OrderedChildnameIterator iterable = new
OrderedChildnameIterator(List.of("4","5"),ALL_CHILDREN);
+ Assert.assertEquals(List.of("4","5","1","2","3"),
iteratorToList(iterable));
+ }
+
+ @Test
+ public void orderedChildrenWithNonExistingOrderedChild() {
+ // the ordered list contains non-existing childnames, which are not
part of children list
+ OrderedChildnameIterator iterable = new
OrderedChildnameIterator(List.of("4","nonexisting1","5","nonexisting2"),ALL_CHILDREN);
+ Assert.assertEquals(List.of("4","5","1","2","3"),
iteratorToList(iterable));
+ }
+
+ @Test
+ public void orderedChildrenWithOnlyNonExistingOrderedChild() {
+ // the ordered list contains non-existing childnames, which are not
part of children list
+ OrderedChildnameIterator iterable = new
OrderedChildnameIterator(List.of("nonexisting"),ALL_CHILDREN);
+ Assert.assertEquals(List.of("1","2","3","4","5"),
iteratorToList(iterable));
+ }
+
+ @Test
+ public void onlyOrderedChildrenAvailable() {
+ // the orderedChildren property is populated, but no children are
available
+ OrderedChildnameIterator iterable = new
OrderedChildnameIterator(List.of("1","2"),List.of());
+ Assert.assertEquals(List.of(), iteratorToList(iterable));
+ }
+
+ @Test
+ public void testLazyLoading() {
+ // Create tracking iterable for allChildren
+ TrackingIterable trackingAllChildren = new
TrackingIterable(ALL_CHILDREN);
+
+ OrderedChildnameIterator iterator = new OrderedChildnameIterator(
+ List.of("4", "1"),
+ trackingAllChildren);
+
+ // Get first element ("4")
+ Assert.assertTrue(iterator.hasNext());
+ Assert.assertEquals("4", iterator.next());
+ // iterated through 4 elements in allChildren
+ Assert.assertEquals(4, trackingAllChildren.getAccessCount());
+ Assert.assertEquals(List.of("1", "2", "3", "4"),
trackingAllChildren.getAccessedElements());
+
+ // Get second element ("1")
+ Assert.assertTrue(iterator.hasNext());
+ Assert.assertEquals("1", iterator.next());
+ // No additional access to allChildren
+ Assert.assertEquals(4, trackingAllChildren.getAccessCount());
+ Assert.assertEquals(List.of("1", "2", "3", "4"),
trackingAllChildren.getAccessedElements());
+
+ // Get remaining elements
+ Assert.assertTrue(iterator.hasNext());
+ Assert.assertEquals("2", iterator.next());
+ Assert.assertTrue(iterator.hasNext());
+ Assert.assertEquals("3", iterator.next());
+ Assert.assertTrue(iterator.hasNext());
+ Assert.assertEquals("5", iterator.next());
+
+ // No more elements should be accessed since we already had them all
+ Assert.assertEquals(5, trackingAllChildren.getAccessCount());
+ Assert.assertFalse(iterator.hasNext());
+ }
+}
diff --git
a/oak-core/src/test/java/org/apache/jackrabbit/oak/security/authorization/evaluation/ChildOrderPropertyTest.java
b/oak-core/src/test/java/org/apache/jackrabbit/oak/security/authorization/evaluation/ChildOrderPropertyTest.java
index 3d7ace8cc5..e31b5c8379 100644
---
a/oak-core/src/test/java/org/apache/jackrabbit/oak/security/authorization/evaluation/ChildOrderPropertyTest.java
+++
b/oak-core/src/test/java/org/apache/jackrabbit/oak/security/authorization/evaluation/ChildOrderPropertyTest.java
@@ -21,6 +21,7 @@ import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertTrue;
+import java.util.ArrayList;
import java.util.List;
import java.util.Set;
@@ -28,7 +29,6 @@ import org.apache.jackrabbit.JcrConstants;
import org.apache.jackrabbit.oak.api.PropertyState;
import org.apache.jackrabbit.oak.api.Root;
import org.apache.jackrabbit.oak.api.Tree;
-import org.apache.jackrabbit.oak.commons.collections.IterableUtils;
import org.apache.jackrabbit.oak.commons.collections.SetUtils;
import org.apache.jackrabbit.oak.plugins.tree.TreeConstants;
import org.apache.jackrabbit.oak.spi.security.privilege.PrivilegeConstants;
@@ -98,7 +98,11 @@ public class ChildOrderPropertyTest extends
AbstractOakCoreTest {
assertFalse(aTree.hasProperty(JcrConstants.JCR_PRIMARYTYPE));
List<String> expected = List.of("/a/bb", "/a/b");
- Iterable<String> childPaths =
IterableUtils.transform(aTree.getChildren(), input -> input.getPath());
- assertTrue(childPaths.toString(),
IterableUtils.elementsEqual(expected, childPaths));
+
+ // Collect actual paths into a list
+ List<String> actual = new ArrayList<>();
+ aTree.getChildren().forEach( c -> actual.add(c.getPath()));
+
+ assertEquals("Child order should be maintained", expected, actual);
}
}
