This is an automated email from the ASF dual-hosted git repository.
garydgregory pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-collections.git
The following commit(s) were added to refs/heads/master by this push:
new ba6ea29fb [COLLECTIONS-900] Preserve IteratorChain state and child
behavior (#755)
ba6ea29fb is described below
commit ba6ea29fb48ee8dfb61e66ee209189a9c787486f
Author: Gary Gregory <[email protected]>
AuthorDate: Thu Nov 12 11:01:59 2026 -0500
[COLLECTIONS-900] Preserve IteratorChain state and child behavior (#755)
* [COLLECTIONS-900] Preserve IteratorChain state and child behavior
Fix regressions introduced by the chain-flattening optimization in #628,
released in 4.6.0. Copying a child chain's iterator queue discarded its
active iterator after hasNext() or next(), bypassed subclass overrides,
and omitted iterators subsequently added to the child.
Retain child iterators instead of copying their contents. Traverse exact
IteratorChain instances iteratively, including chains wrapped by
UnmodifiableIterator, to avoid stack overflow with deep nesting.
Delegate
normally to subclasses so their iterator methods and protected
updateCurrentIterator() hook remain effective.
Preserve locking, cached availability, and removal state throughout
nested
chains. Keep unmodifiable boundaries intact and clear removal state only
after the underlying remove() succeeds. Later additions remain visible
until the child chain is visited and locked.
Correct the addIterator() exception documentation, document live child
behavior and queue-based size() semantics, and update the release notes.
Extend regression coverage for partial consumption, repeated lookahead,
empty children, exhaustion, null elements, constructor and factory
paths,
shared sources, subclass overrides, exception recovery, and removal.
Verify ordinary and unmodifiable chains nested 20,000 levels deep.
This restores live delegation semantics at the cost of traversal work
proportional to nesting depth, rather than flattening away child
identity.
Assisted-By: OpenAI Codex
* [COLLECTIONS-900] Detect cyclic IteratorChain traversal and removal
Detect cycles by identity during nested traversal and removal,
preventing
unbounded deque growth and OutOfMemoryError. Cover cyclic removal state
left by a failed next() call as well as direct, mutual, and wrapped
cycles.
Check active ancestors before using cached availability, and discard
intermediate cached results when a cycle is detected so retries cannot
silently report exhaustion. Remove completed children from the active
path to allow shared acyclic children.
Allocate traversal state only when descending into nested chains. Add a
flat-removal fast path that preserves subclass dispatch, unmodifiable
boundaries, and clearing removal state only after successful delegation.
Document cycle handling and its subclass boundary, update release notes,
and add 41 regression cases covering cycles, retries, removal state,
shared children, and identity-based tracking. Use JUnit fail() instead
of explicit AssertionError throws in the added tests.
Validation:
- Full Maven build: 22,545 tests, no failures or errors, 82 skipped.
- All 310 focused tests passed on Java 8 and Java 21.
- Zero Checkstyle violations.
- 800,000 randomized acyclic operations retained the pre-flattening
behavior.
Assisted-By: OpenAI Codex
* [COLLECTIONS-900] Detect cyclic IteratorChain traversal and removal
Use JUnit fail()
---
src/changes/changes.xml | 1 +
.../collections4/iterators/IteratorChain.java | 189 +++++++---
.../iterators/IteratorChainCompatibilityTest.java | 406 +++++++++++++++++++++
.../iterators/IteratorChainCycleTest.java | 198 ++++++++++
.../iterators/IteratorChainRechainingTest.java | 292 +++++++++++++++
.../collections4/iterators/IteratorChainTest.java | 19 +
6 files changed, 1058 insertions(+), 47 deletions(-)
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index e87d07d02..d0c23b478 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -35,6 +35,7 @@
<action type="fix" dev="ggregory" due-to="Naveed Khan, Gary Gregory">Reset
last element in EnumerationIterator.remove() (#729).</action>
<action type="fix" dev="ggregory" due-to="Naveed Khan, Gary Gregory">Fix
TransformedMultiValuedMap.putAll(K, Iterable) NPE for null value transformer
(#731).</action>
<action type="fix" dev="ggregory" due-to="Gary Gregory">Fix
AbstractReferenceMap.ReferenceEntry.setValue(V) to throw NullPointerException
on null input (contract).</action>
+ <action type="fix" dev="ggregory" due-to="Manfred Baedke, Gary Gregory"
issue="COLLECTIONS-900">Preserve iteration state, subclass behavior, and later
child additions when chaining IteratorChain instances. Reject detected cycles
during traversal and removal (#730, #755).</action>
<!-- ADD -->
<!-- UPDATE -->
<action type="update" dev="ggregory" due-to="Gary Gregory">Bump
org.apache.commons:commons-parent from 104 to 107.</action>
diff --git
a/src/main/java/org/apache/commons/collections4/iterators/IteratorChain.java
b/src/main/java/org/apache/commons/collections4/iterators/IteratorChain.java
index 08ee8fe05..b5138489a 100644
--- a/src/main/java/org/apache/commons/collections4/iterators/IteratorChain.java
+++ b/src/main/java/org/apache/commons/collections4/iterators/IteratorChain.java
@@ -16,11 +16,16 @@
*/
package org.apache.commons.collections4.iterators;
+import java.util.ArrayDeque;
import java.util.Collection;
+import java.util.Collections;
+import java.util.Deque;
+import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
+import java.util.Set;
/**
* An IteratorChain is an Iterator that wraps a number of Iterators.
@@ -40,6 +45,11 @@ import java.util.Queue;
* interface has been called</i> will result in an
UnsupportedOperationException.
* </p>
* <p>
+ * Nested chains must not form cycles. If a cycle is detected during traversal
or removal,
+ * an {@link IllegalStateException} is thrown. Subclasses and other iterator
implementations
+ * are invoked normally and are responsible for their own cycle handling.
+ * </p>
+ * <p>
* NOTE: As from version 3.0, the IteratorChain may contain no iterators. In
* this case the class will function as an empty iterator.
* </p>
@@ -56,6 +66,19 @@ import java.util.Queue;
*/
public class IteratorChain<E> implements Iterator<E> {
+ /**
+ * Gets a nested chain that can be traversed without invoking overridden
methods.
+ * Unmodifiable decorators forward hasNext() and next(), but must still be
retained for remove().
+ */
+ private static <E> IteratorChain<? extends E> asIteratorChain(final
Iterator<? extends E> iterator) {
+ Iterator<? extends E> unwrapped = iterator;
+ while (unwrapped instanceof UnmodifiableIterator) {
+ unwrapped = ((UnmodifiableIterator<? extends E, ?>)
unwrapped).unwrap();
+ }
+ // Subclasses may override any iterator method or
updateCurrentIterator().
+ return unwrapped.getClass() == IteratorChain.class ? (IteratorChain<?
extends E>) unwrapped : null;
+ }
+
/** The chain of iterators */
private final Queue<Iterator<? extends E>> iteratorQueue = new
LinkedList<>();
@@ -69,8 +92,7 @@ public class IteratorChain<E> implements Iterator<E> {
private Iterator<? extends E> lastUsedIterator;
/**
- * ComparatorChain is "locked" after the first time compare(Object, Object)
- * is called
+ * The chain is locked after the first call to an Iterator interface
method.
*/
private boolean isLocked;
@@ -160,37 +182,20 @@ public class IteratorChain<E> implements Iterator<E> {
}
/**
- * Add an Iterator to the end of the chain
+ * Adds an Iterator to the end of the chain.
+ * <p>
+ * The iterator is retained, not copied. If it is another {@code
IteratorChain}, iterators added to that child before it is locked are also
visited.
+ * Subclasses retain their iterator behavior when used as children.
+ * </p>
*
* @param iterator Iterator to add
- * @throws IllegalStateException if I've already started iterating
+ * @throws UnsupportedOperationException if this chain is already locked
* @throws NullPointerException if the iterator is null
*/
public void addIterator(final Iterator<? extends E> iterator) {
checkLocked();
- Objects.requireNonNull(iterator, "iterator");
- if (iterator instanceof UnmodifiableIterator) {
- final Iterator<? extends E> underlyingIterator =
((UnmodifiableIterator) iterator).unwrap();
- if (underlyingIterator instanceof IteratorChain) {
- // in case it is an IteratorChain, wrap every underlying
iterators as unmodifiable
- // multiple rechainings would otherwise lead to exponential
growing number of function calls
- // when the iteratorChain gets used.
- for (final Iterator<? extends E> nestedIterator :
((IteratorChain<? extends E>) underlyingIterator).iteratorQueue) {
-
iteratorQueue.add(UnmodifiableIterator.unmodifiableIterator(nestedIterator));
- }
- } else {
- // we don't know anything about the underlying iterator,
simply add it here
- iteratorQueue.add(iterator);
- }
- } else if (iterator instanceof IteratorChain) {
- // add the wrapped iterators directly instead of reusing the given
instance
- // multiple rechainings would otherwise lead to exponential
growing number of function calls
- // when the iteratorChain gets used.
- iteratorQueue.addAll(((IteratorChain) iterator).iteratorQueue);
- } else {
- // arbitrary other iterator
- iteratorQueue.add(iterator);
- }
+ // Retain the iterator itself so subclass behavior and later additions
to a child chain are preserved.
+ iteratorQueue.add(Objects.requireNonNull(iterator, "iterator"));
}
/**
@@ -206,6 +211,7 @@ public class IteratorChain<E> implements Iterator<E> {
* Return true if any Iterator in the IteratorChain has a remaining
element.
*
* @return true if elements remain
+ * @throws IllegalStateException if a cycle is detected in the nested
chains
*/
@Override
public boolean hasNext() {
@@ -216,6 +222,15 @@ public class IteratorChain<E> implements Iterator<E> {
return cachedHasNextValue;
}
+ /**
+ * Initializes the current iterator without inspecting its contents.
+ */
+ private void initializeCurrentIterator() {
+ if (currentIterator == null) {
+ pollCurrentIterator();
+ }
+ }
+
/**
* Determine if modifications can still be made to the IteratorChain.
* IteratorChains cannot be modified once they have executed a method from
@@ -243,16 +258,36 @@ public class IteratorChain<E> implements Iterator<E> {
* @return Object from the current Iterator
* @throws java.util.NoSuchElementException if all the Iterators are
* exhausted
+ * @throws IllegalStateException if a cycle is detected in the nested
chains
*/
@Override
public E next() {
+ Iterator<? extends E> iterator = nextIterator();
+ IteratorChain<? extends E> chain;
+ while ((chain = asIteratorChain(iterator)) != null) {
+ iterator = chain.nextIterator();
+ }
+ return iterator.next();
+ }
+
+ /**
+ * Prepares this chain for next() while retaining the actual child for
remove().
+ */
+ private Iterator<? extends E> nextIterator() {
lockChain();
if (cachedHasNextValue == null) {
updateCurrentIterator();
}
lastUsedIterator = currentIterator;
cachedHasNextValue = null;
- return currentIterator.next();
+ return currentIterator;
+ }
+
+ /**
+ * Advances to the next queued iterator, or an empty iterator if the queue
is empty.
+ */
+ private void pollCurrentIterator() {
+ currentIterator = iteratorQueue.isEmpty() ?
EmptyIterator.<E>emptyIterator() : iteratorQueue.remove();
}
/**
@@ -266,20 +301,51 @@ public class IteratorChain<E> implements Iterator<E> {
* supported by the underlying Iterator
* @throws IllegalStateException if the next method has not yet been
called,
* or the remove method has already been called after the last call to the
- * next method.
+ * next method, or a cycle is detected in the nested chains.
*/
@Override
public void remove() {
lockChain();
- if (lastUsedIterator == null) {
+ if (lastUsedIterator == null) {
throw new IllegalStateException("remove() has been invoked without
next()");
}
- lastUsedIterator.remove();
- lastUsedIterator = null; // must never be used twice without next()
being invoked
+ // Flat removal needs no traversal state, and must still delegate to
subclasses and decorators.
+ if (lastUsedIterator.getClass() != IteratorChain.class) {
+ lastUsedIterator.remove();
+ lastUsedIterator = null;
+ return;
+ }
+ final Deque<IteratorChain<?>> chains = new ArrayDeque<>();
+ final Set<IteratorChain<?>> active = Collections.newSetFromMap(new
IdentityHashMap<>());
+ IteratorChain<?> chain = this;
+ while (true) {
+ if (!active.add(chain)) {
+ throw new IllegalStateException("Cyclic IteratorChain");
+ }
+ chain.lockChain();
+ if (chain.lastUsedIterator == null) {
+ throw new IllegalStateException("remove() has been invoked
without next()");
+ }
+ chains.push(chain);
+ final Iterator<?> iterator = chain.lastUsedIterator;
+ // Do not unwrap unmodifiable decorators or bypass a subclass's
remove() method.
+ if (iterator.getClass() != IteratorChain.class) {
+ iterator.remove();
+ break;
+ }
+ chain = (IteratorChain<?>) iterator;
+ }
+ // Only clear removal state after the underlying remove() succeeds.
+ for (final IteratorChain<?> usedChain : chains) {
+ usedChain.lastUsedIterator = null;
+ }
}
/**
- * Returns the remaining number of Iterators in the current IteratorChain.
+ * Gets the number of iterators remaining in this chain's queue.
+ * <p>
+ * The current iterator is excluded. A nested chain counts as one
iterator, regardless of its contents.
+ * </p>
*
* @return Iterator count
*/
@@ -288,26 +354,55 @@ public class IteratorChain<E> implements Iterator<E> {
}
/**
- * Updates the current iterator field to ensure that the current Iterator
is
- * not exhausted
+ * Updates the current iterator field to ensure that the current Iterator
is not exhausted.
+ * Nested instances of this class are traversed iteratively; subclasses
are invoked normally to preserve their overrides.
+ *
+ * @throws IllegalStateException if a cycle is detected in the nested
chains
*/
protected void updateCurrentIterator() {
- if (currentIterator == null) {
- if (iteratorQueue.isEmpty()) {
- currentIterator = EmptyIterator.<E>emptyIterator();
+ Deque<IteratorChain<? extends E>> parents = null;
+ Set<IteratorChain<? extends E>> active = null;
+ IteratorChain<? extends E> chain = this;
+ while (true) {
+ chain.initializeCurrentIterator();
+ final IteratorChain<? extends E> child =
asIteratorChain(chain.currentIterator);
+ if (child == null) {
+ chain.cachedHasNextValue = chain.currentIterator.hasNext();
} else {
- currentIterator = iteratorQueue.remove();
+ child.lockChain();
+ // A cached result must not conceal a link back to an active
ancestor.
+ if (child == chain || active != null &&
active.contains(child)) {
+ // Discard intermediate results so a retry also detects
the cycle.
+ chain.cachedHasNextValue = null;
+ if (parents != null) {
+ for (final IteratorChain<?> parent : parents) {
+ parent.cachedHasNextValue = null;
+ }
+ }
+ throw new IllegalStateException("Cyclic IteratorChain");
+ }
+ if (child.cachedHasNextValue == null) {
+ if (parents == null) {
+ parents = new ArrayDeque<>();
+ active = Collections.newSetFromMap(new
IdentityHashMap<>());
+ active.add(chain);
+ }
+ active.add(child);
+ parents.push(chain);
+ chain = child;
+ continue;
+ }
+ chain.cachedHasNextValue = child.cachedHasNextValue;
}
- }
- while (true) {
- cachedHasNextValue = currentIterator.hasNext();
- if (cachedHasNextValue) {
- break;
+ if (!chain.cachedHasNextValue && !chain.iteratorQueue.isEmpty()) {
+ chain.pollCurrentIterator();
+ continue;
}
- if (iteratorQueue.isEmpty()) {
- break;
+ if (parents == null || parents.isEmpty()) {
+ return;
}
- currentIterator = iteratorQueue.remove();
+ active.remove(chain);
+ chain = parents.pop();
}
}
}
diff --git
a/src/test/java/org/apache/commons/collections4/iterators/IteratorChainCompatibilityTest.java
b/src/test/java/org/apache/commons/collections4/iterators/IteratorChainCompatibilityTest.java
new file mode 100644
index 000000000..0ecc5eae1
--- /dev/null
+++
b/src/test/java/org/apache/commons/collections4/iterators/IteratorChainCompatibilityTest.java
@@ -0,0 +1,406 @@
+/*
+ * 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
+ *
+ * https://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.commons.collections4.iterators;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertFalse;
+import static org.junit.jupiter.api.Assertions.assertSame;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertTimeoutPreemptively;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+import static org.junit.jupiter.api.Assertions.fail;
+
+import java.time.Duration;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.stream.Stream;
+
+import org.apache.commons.collections4.IteratorUtils;
+import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.CsvSource;
+import org.junit.jupiter.params.provider.MethodSource;
+import org.junit.jupiter.params.provider.ValueSource;
+
+/**
+ * Tests the live child-chain and subclass contracts that eager flattening
broke in COLLECTIONS-722.
+ */
+class IteratorChainCompatibilityTest {
+
+ private enum Construction {
+ ADD, SINGLE, PAIR, ARRAY, COLLECTION, UTILS_PAIR, UTILS_ARRAY,
UTILS_COLLECTION
+ }
+
+ private static Stream<Arguments> additionCases() {
+ final List<Arguments> arguments = new ArrayList<>();
+ for (final Construction construction : Construction.values()) {
+ for (final boolean unmodifiable : new boolean[] { false, true }) {
+ for (final boolean initiallyEmpty : new boolean[] { false,
true }) {
+ arguments.add(Arguments.of(construction, unmodifiable,
initiallyEmpty));
+ }
+ }
+ }
+ return arguments.stream();
+ }
+
+ private static Iterator<Integer> construct(final Construction
construction, final Iterator<Integer> child) {
+ final Iterator<Integer> tail = Collections.singletonList(9).iterator();
+ switch (construction) {
+ case ADD:
+ final IteratorChain<Integer> added = new IteratorChain<>();
+ added.addIterator(child);
+ added.addIterator(tail);
+ return added;
+ case SINGLE:
+ final IteratorChain<Integer> single = new IteratorChain<>(child);
+ single.addIterator(tail);
+ return single;
+ case PAIR:
+ return new IteratorChain<>(child, tail);
+ case ARRAY:
+ return new IteratorChain<>(Collections.emptyIterator(), child,
tail);
+ case COLLECTION:
+ return new IteratorChain<>(Arrays.asList(child, tail));
+ case UTILS_PAIR:
+ return IteratorUtils.chainedIterator(child, tail);
+ case UTILS_ARRAY:
+ return IteratorUtils.chainedIterator(Collections.emptyIterator(),
child, tail);
+ case UTILS_COLLECTION:
+ return IteratorUtils.chainedIterator(Arrays.asList(child, tail));
+ default:
+ return fail("Unexpected construction: " + construction);
+ }
+ }
+
+ private static <E> Iterator<E> wrap(final Iterator<E> iterator, final
boolean unmodifiable) {
+ return unmodifiable ?
UnmodifiableIterator.unmodifiableIterator(iterator) : iterator;
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testAdditionsAfterParentStartsBeforeChildIsReached(final boolean
unmodifiable) {
+ final IteratorChain<Integer> source = new IteratorChain<>();
+ final IteratorChain<Integer> destination = new
IteratorChain<>(Arrays.asList(0, 1).iterator(), wrap(source, unmodifiable));
+ assertTrue(destination.hasNext());
+ assertFalse(source.isLocked());
+ source.addIterator(Collections.singletonList(2).iterator());
+ assertEquals(0, destination.next());
+ source.addIterator(Collections.singletonList(3).iterator());
+ assertEquals(1, destination.next());
+ assertFalse(source.isLocked());
+ assertTrue(destination.hasNext());
+ assertTrue(source.isLocked());
+ assertThrows(UnsupportedOperationException.class, () ->
source.addIterator(Collections.singletonList(4).iterator()));
+ assertEquals(Arrays.asList(2, 3), IteratorUtils.toList(destination));
+ }
+
+ @ParameterizedTest
+ @MethodSource("additionCases")
+ void testAdditionsAfterWrapping(final Construction construction, final
boolean unmodifiable, final boolean initiallyEmpty) {
+ final IteratorChain<Integer> source = new IteratorChain<>();
+ if (!initiallyEmpty) {
+ source.addIterator(Collections.singletonList(1).iterator());
+ }
+ final Iterator<Integer> destination = construct(construction,
wrap(source, unmodifiable));
+ assertFalse(source.isLocked());
+ source.addIterator(Collections.emptyIterator());
+ source.addIterator(Collections.singletonList(2).iterator());
+ assertEquals(initiallyEmpty ? Arrays.asList(2, 9) : Arrays.asList(1,
2, 9), IteratorUtils.toList(destination));
+ assertTrue(source.isLocked());
+ assertFalse(source.hasNext());
+ assertThrows(UnsupportedOperationException.class, () ->
source.addIterator(Collections.emptyIterator()));
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testDeepLiveChains(final boolean unmodifiable) {
+ assertTimeoutPreemptively(Duration.ofSeconds(10), () -> {
+ final List<Integer> values = new ArrayList<>(Arrays.asList(1, 2));
+ final AtomicInteger hasNextCalls = new AtomicInteger();
+ final Iterator<Integer> delegate = values.iterator();
+ final Iterator<Integer> leaf = new Iterator<Integer>() {
+
+ @Override
+ public boolean hasNext() {
+ hasNextCalls.incrementAndGet();
+ return delegate.hasNext();
+ }
+
+ @Override
+ public Integer next() {
+ return delegate.next();
+ }
+
+ @Override
+ public void remove() {
+ delegate.remove();
+ }
+ };
+ final IteratorChain<Integer> source = new IteratorChain<>(leaf);
+ final List<IteratorChain<Integer>> chains = new ArrayList<>();
+ IteratorChain<Integer> destination = source;
+ for (int i = 0; i < 20000; i++) {
+ destination = new IteratorChain<>(wrap(destination,
unmodifiable));
+ chains.add(destination);
+ }
+ source.addIterator(Collections.singletonList(3).iterator());
+ for (final IteratorChain<Integer> chain : chains) {
+ assertFalse(chain.isLocked());
+ }
+ assertTrue(destination.hasNext());
+ assertTrue(destination.hasNext());
+ assertEquals(1, hasNextCalls.get());
+ assertEquals(1, destination.next());
+ if (unmodifiable) {
+ assertThrows(UnsupportedOperationException.class,
destination::remove);
+ } else {
+ destination.remove();
+ assertThrows(IllegalStateException.class, destination::remove);
+ assertThrows(IllegalStateException.class, source::remove);
+ }
+ assertEquals(Arrays.asList(2, 3),
IteratorUtils.toList(destination));
+ assertEquals(3, hasNextCalls.get());
+ assertEquals(unmodifiable ? Arrays.asList(1, 2) :
Collections.singletonList(2), values);
+ assertFalse(source.hasNext());
+ assertThrows(NoSuchElementException.class, destination::next);
+ for (final IteratorChain<Integer> chain : chains) {
+ assertTrue(chain.isLocked());
+ assertFalse(chain.hasNext());
+ }
+ });
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testEmptyChildLocksWhenVisited(final boolean unmodifiable) {
+ final IteratorChain<Integer> source = new IteratorChain<>();
+ final IteratorChain<Integer> destination = new
IteratorChain<>(wrap(source, unmodifiable));
+ assertFalse(source.isLocked());
+ assertFalse(destination.hasNext());
+ assertTrue(source.isLocked());
+ assertThrows(UnsupportedOperationException.class, () ->
source.addIterator(Collections.singletonList(1).iterator()));
+ }
+
+ @Test
+ void testNestedRemovalCanBeRetriedAfterFailure() {
+ final List<Integer> values = new
ArrayList<>(Collections.singletonList(1));
+ final AtomicInteger attempts = new AtomicInteger();
+ final IllegalStateException failure = new IllegalStateException("First
removal fails");
+ final IteratorChain<Integer> source = new
IteratorChain<Integer>(values.iterator()) {
+
+ @Override
+ public void remove() {
+ if (attempts.incrementAndGet() == 1) {
+ throw failure;
+ }
+ super.remove();
+ }
+ };
+ final IteratorChain<Integer> destination = new IteratorChain<>(new
IteratorChain<>(source));
+ assertEquals(1, destination.next());
+ assertSame(failure, assertThrows(IllegalStateException.class,
destination::remove));
+ destination.remove();
+ assertTrue(values.isEmpty());
+ assertEquals(2, attempts.get());
+ assertThrows(IllegalStateException.class, destination::remove);
+ assertEquals(2, attempts.get());
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testNestedSourcesAddedAfterWrapping(final boolean unmodifiable) {
+ final IteratorChain<Integer> source = new IteratorChain<>();
+ final IteratorChain<Integer> destination = new
IteratorChain<>(wrap(source, unmodifiable));
+ final IteratorChain<Integer> grandchild = new IteratorChain<>();
+ source.addIterator(wrap(grandchild, unmodifiable));
+ source.addIterator(Collections.singletonList(3).iterator());
+ grandchild.addIterator(Arrays.asList(1, 2).iterator());
+ assertEquals(Arrays.asList(1, 2, 3),
IteratorUtils.toList(destination));
+ assertTrue(grandchild.isLocked());
+ assertFalse(grandchild.hasNext());
+ }
+
+ @Test
+ void testQueueSizeCountsLiveChildren() {
+ final IteratorChain<Integer> source = new
IteratorChain<>(Collections.singletonList(1).iterator(),
Collections.singletonList(2).iterator());
+ final IteratorChain<Integer> destination = new IteratorChain<>(source);
+ assertEquals(1, destination.size());
+ assertEquals(2, source.size());
+ assertTrue(destination.hasNext());
+ assertEquals(0, destination.size());
+ assertEquals(1, source.size());
+ assertEquals(Arrays.asList(1, 2), IteratorUtils.toList(destination));
+ assertEquals(0, source.size());
+ }
+
+ @Test
+ void testSharedSourceConsumptionAndRemovalState() {
+ final List<Integer> values = new ArrayList<>(Arrays.asList(1, 2, 3));
+ final IteratorChain<Integer> source = new
IteratorChain<>(values.iterator());
+ final IteratorChain<Integer> first = new IteratorChain<>(source);
+ final IteratorChain<Integer> second = new IteratorChain<>(source);
+ assertEquals(1, source.next());
+ assertEquals(2, first.next());
+ source.remove();
+ assertThrows(IllegalStateException.class, first::remove);
+ assertEquals(3, second.next());
+ second.remove();
+ assertThrows(IllegalStateException.class, source::remove);
+ assertEquals(Collections.singletonList(1), values);
+ assertFalse(first.hasNext());
+ assertFalse(second.hasNext());
+ assertFalse(source.hasNext());
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testSourceAdvancesAfterWrapping(final boolean unmodifiable) {
+ final IteratorChain<Integer> source = new
IteratorChain<>(Arrays.asList(1, 2).iterator(),
Collections.singletonList(3).iterator());
+ final IteratorChain<Integer> destination = new
IteratorChain<>(wrap(source, unmodifiable));
+ assertEquals(1, source.next());
+ assertEquals(2, source.next());
+ assertTrue(source.hasNext());
+ assertEquals(Collections.singletonList(3),
IteratorUtils.toList(destination));
+ assertFalse(source.hasNext());
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testSubclassHasNextOverride(final boolean unmodifiable) {
+ final AtomicInteger calls = new AtomicInteger();
+ final IteratorChain<Integer> source = new
IteratorChain<Integer>(Collections.singletonList(1).iterator()) {
+
+ @Override
+ public boolean hasNext() {
+ calls.incrementAndGet();
+ return false;
+ }
+ };
+ final IteratorChain<Integer> destination = new
IteratorChain<>(wrap(source, unmodifiable),
Collections.singletonList(2).iterator());
+ assertEquals(Collections.singletonList(2),
IteratorUtils.toList(destination));
+ assertEquals(1, calls.get());
+ }
+
+ @ParameterizedTest
+ @CsvSource({ "false, false", "false, true", "true, false", "true, true" })
+ void testSubclassNextOverride(final boolean unmodifiable, final boolean
initialized) {
+ final AtomicInteger calls = new AtomicInteger();
+ final IteratorChain<Integer> source = new
IteratorChain<Integer>(Arrays.asList(1, 2).iterator()) {
+
+ @Override
+ public Integer next() {
+ calls.incrementAndGet();
+ return super.next() * 10;
+ }
+ };
+ if (initialized) {
+ assertTrue(source.hasNext());
+ }
+ final IteratorChain<Integer> destination = new
IteratorChain<>(wrap(source, unmodifiable));
+ final List<Integer> values = new ArrayList<>();
+ destination.forEachRemaining(values::add);
+ assertEquals(Arrays.asList(10, 20), values);
+ assertEquals(2, calls.get());
+ }
+
+ @Test
+ void testSubclassRemoveOverrideAfterLookAhead() {
+ final List<Integer> values = new
ArrayList<>(Collections.singletonList(1));
+ final AtomicInteger calls = new AtomicInteger();
+ final IteratorChain<Integer> source = new
IteratorChain<Integer>(values.iterator()) {
+
+ @Override
+ public void remove() {
+ calls.incrementAndGet();
+ throw new UnsupportedOperationException("Subclass is read
only");
+ }
+ };
+ final IteratorChain<Integer> destination = new IteratorChain<>(source,
Collections.singletonList(2).iterator());
+ assertEquals(1, destination.next());
+ assertTrue(destination.hasNext());
+ assertThrows(UnsupportedOperationException.class, destination::remove);
+ assertEquals(1, calls.get());
+ assertEquals(Collections.singletonList(1), values);
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testSubclassUpdateCurrentIteratorOverride(final boolean unmodifiable)
{
+ final AtomicInteger calls = new AtomicInteger();
+ final IllegalStateException failure = new IllegalStateException("Retry
traversal");
+ final IteratorChain<Integer> source = new
IteratorChain<Integer>(Collections.singletonList(1).iterator()) {
+
+ @Override
+ protected void updateCurrentIterator() {
+ if (calls.incrementAndGet() == 1) {
+ throw failure;
+ }
+ super.updateCurrentIterator();
+ }
+ };
+ final IteratorChain<Integer> destination = new IteratorChain<>(new
IteratorChain<>(wrap(source, unmodifiable)));
+ assertSame(failure, assertThrows(IllegalStateException.class,
destination::hasNext));
+ assertEquals(1, destination.next());
+ assertEquals(2, calls.get());
+ assertFalse(destination.hasNext());
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testSubclassWithoutQueuedIterators(final boolean unmodifiable) {
+ final AtomicInteger remaining = new AtomicInteger(2);
+ final IteratorChain<Integer> source = new IteratorChain<Integer>() {
+
+ @Override
+ public boolean hasNext() {
+ return remaining.get() > 0;
+ }
+
+ @Override
+ public Integer next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+ return remaining.getAndDecrement();
+ }
+ };
+ final IteratorChain<Number> destination = new
IteratorChain<>(wrap(source, unmodifiable));
+ assertEquals(Arrays.asList(2, 1), IteratorUtils.toList(destination));
+ assertThrows(NoSuchElementException.class, destination::next);
+ }
+
+ @Test
+ void testUnmodifiableBoundaryInsideModifiableChains() {
+ final List<Integer> values = new
ArrayList<>(Collections.singletonList(1));
+ final IteratorChain<Integer> source = new
IteratorChain<>(values.iterator());
+ final IteratorChain<Integer> middle = new
IteratorChain<>(UnmodifiableIterator.unmodifiableIterator(source));
+ final IteratorChain<Integer> destination = new IteratorChain<>(middle);
+ assertEquals(1, destination.next());
+ assertThrows(UnsupportedOperationException.class, destination::remove);
+ assertEquals(Collections.singletonList(1), values);
+ // Direct access to the source retains the same removal state as
normal delegation.
+ source.remove();
+ assertTrue(values.isEmpty());
+ }
+}
diff --git
a/src/test/java/org/apache/commons/collections4/iterators/IteratorChainCycleTest.java
b/src/test/java/org/apache/commons/collections4/iterators/IteratorChainCycleTest.java
new file mode 100644
index 000000000..e52b96a4f
--- /dev/null
+++
b/src/test/java/org/apache/commons/collections4/iterators/IteratorChainCycleTest.java
@@ -0,0 +1,198 @@
+/*
+ * 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
+ *
+ * https://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.commons.collections4.iterators;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertFalse;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+import static org.junit.jupiter.api.Assertions.fail;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+import java.util.stream.Stream;
+
+import org.apache.commons.collections4.IteratorUtils;
+import org.junit.jupiter.api.Test;
+import org.junit.jupiter.api.function.Executable;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.EnumSource;
+import org.junit.jupiter.params.provider.MethodSource;
+import org.junit.jupiter.params.provider.ValueSource;
+
+/**
+ * Tests cycle detection without rejecting shared acyclic children.
+ */
+class IteratorChainCycleTest {
+
+ private enum CycleShape {
+ DIRECT, MUTUAL, WRAPPED_DIRECT, WRAPPED_MUTUAL, INDIRECT
+ }
+
+ private enum Prefix {
+ NONE, EMPTY, VALUE
+ }
+
+ private static void assertCycle(final Executable operation) {
+ assertEquals("Cyclic IteratorChain",
assertThrows(IllegalStateException.class, operation).getMessage());
+ }
+
+ private static IteratorChain<Integer> createCycle(final CycleShape shape,
final List<Integer> prefix) {
+ final IteratorChain<Integer> root = new IteratorChain<>();
+ if (prefix != null) {
+ root.addIterator(prefix.iterator());
+ }
+ final IteratorChain<Integer> child = new IteratorChain<>();
+ switch (shape) {
+ case DIRECT:
+ root.addIterator(root);
+ break;
+ case MUTUAL:
+ root.addIterator(child);
+ child.addIterator(root);
+ break;
+ case WRAPPED_DIRECT:
+ root.addIterator(UnmodifiableIterator.unmodifiableIterator(root));
+ break;
+ case WRAPPED_MUTUAL:
+ root.addIterator(UnmodifiableIterator.unmodifiableIterator(child));
+ child.addIterator(UnmodifiableIterator.unmodifiableIterator(root));
+ break;
+ case INDIRECT:
+ final IteratorChain<Integer> grandchild = new IteratorChain<>();
+ root.addIterator(child);
+ child.addIterator(grandchild);
+ grandchild.addIterator(root);
+ break;
+ default:
+ return fail("Unexpected cycle shape: " + shape);
+ }
+ return root;
+ }
+
+ private static Stream<Arguments> cycleCases() {
+ final List<Arguments> arguments = new ArrayList<>();
+ for (final CycleShape shape : CycleShape.values()) {
+ for (final Prefix prefix : Prefix.values()) {
+ for (final boolean hasNextFirst : new boolean[] { false, true
}) {
+ arguments.add(Arguments.of(shape, prefix, hasNextFirst));
+ }
+ }
+ }
+ return arguments.stream();
+ }
+
+ @ParameterizedTest
+ @MethodSource("cycleCases")
+ void testCycleDuringTraversal(final CycleShape shape, final Prefix prefix,
final boolean hasNextFirst) {
+ final List<Integer> values = prefix == Prefix.NONE ? null : prefix ==
Prefix.EMPTY ? Collections.emptyList() : Collections.singletonList(1);
+ final IteratorChain<Integer> root = createCycle(shape, values);
+ if (prefix == Prefix.VALUE) {
+ assertEquals(1, root.next());
+ }
+ if (hasNextFirst) {
+ assertCycle(root::hasNext);
+ } else {
+ assertCycle(root::next);
+ }
+ // A failed traversal must not leave a cached false result that hides
the cycle on retry.
+ assertCycle(root::hasNext);
+ assertCycle(root::next);
+ assertTrue(root.isLocked());
+ assertThrows(UnsupportedOperationException.class, () ->
root.addIterator(Collections.emptyIterator()));
+ }
+
+ @ParameterizedTest
+ @EnumSource(CycleShape.class)
+ void testCycleFailurePreservesLastSuccessfulRemoval(final CycleShape
shape) {
+ final List<Integer> values = new
ArrayList<>(Collections.singletonList(1));
+ final IteratorChain<Integer> root = createCycle(shape, values);
+ assertEquals(1, root.next());
+ assertCycle(root::hasNext);
+ root.remove();
+ assertTrue(values.isEmpty());
+ assertThrows(IllegalStateException.class, root::remove);
+ assertCycle(root::hasNext);
+ }
+
+ @ParameterizedTest
+ @ValueSource(ints = { 2, 3, 20 })
+ void testRemovalCycleAfterFailedNext(final int length) {
+ final List<IteratorChain<Integer>> chains = new ArrayList<>();
+ for (int i = 0; i < length; i++) {
+ chains.add(new IteratorChain<>());
+ }
+ final List<Integer> values = new
ArrayList<>(Collections.singletonList(1));
+ final IteratorChain<Integer> root = chains.get(0);
+ root.addIterator(values.iterator());
+ for (int i = 0; i < length; i++) {
+ chains.get(i).addIterator(chains.get((i + 1) % length));
+ }
+ assertTrue(root.hasNext());
+ // Populate cached results around the cycle before consuming the
finite prefix.
+ assertTrue(chains.get(1).hasNext());
+ assertEquals(1, root.next());
+ assertTrue(root.hasNext());
+ assertCycle(root::next);
+ // next() has prepared removal state along the path before detecting
the cycle.
+ assertCycle(root::remove);
+ assertCycle(root::remove);
+ assertEquals(Collections.singletonList(1), values);
+ assertCycle(root::hasNext);
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testSharedChildrenAreNotCycles(final boolean unmodifiable) {
+ final IteratorChain<Integer> shared = new
IteratorChain<>(Collections.emptyIterator());
+ final Iterator<Integer> child = unmodifiable ?
UnmodifiableIterator.unmodifiableIterator(shared) : shared;
+ final IteratorChain<Integer> first = new IteratorChain<>(child);
+ final IteratorChain<Integer> second = new IteratorChain<>(child,
Collections.singletonList(1).iterator());
+ final IteratorChain<Integer> root = new IteratorChain<>(first, second,
child);
+ // The same child is visited through three paths during one traversal.
+ assertEquals(Collections.singletonList(1), IteratorUtils.toList(root));
+ assertFalse(root.hasNext());
+ assertTrue(shared.isLocked());
+ }
+
+ @Test
+ void testTraversalStateUsesIdentity() {
+ final List<Integer> values = new ArrayList<>(Arrays.asList(1, 2));
+ final IteratorChain<Integer> root = new IteratorChain<Integer>() {
+
+ @Override
+ public boolean equals(final Object other) {
+ return fail("Traversal must not call equals()");
+ }
+
+ @Override
+ public int hashCode() {
+ return fail("Traversal must not call hashCode()");
+ }
+ };
+ root.addIterator(new IteratorChain<>(values.iterator()));
+ assertEquals(1, root.next());
+ root.remove();
+ assertEquals(Collections.singletonList(2), IteratorUtils.toList(root));
+ assertEquals(Collections.singletonList(2), values);
+ }
+}
diff --git
a/src/test/java/org/apache/commons/collections4/iterators/IteratorChainRechainingTest.java
b/src/test/java/org/apache/commons/collections4/iterators/IteratorChainRechainingTest.java
new file mode 100644
index 000000000..b3dba1047
--- /dev/null
+++
b/src/test/java/org/apache/commons/collections4/iterators/IteratorChainRechainingTest.java
@@ -0,0 +1,292 @@
+/*
+ * 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
+ *
+ * https://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.commons.collections4.iterators;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertFalse;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertTimeoutPreemptively;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.verifyNoInteractions;
+import static org.mockito.Mockito.when;
+
+import java.time.Duration;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.stream.Stream;
+
+import org.apache.commons.collections4.IteratorUtils;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
+import org.junit.jupiter.params.provider.ValueSource;
+
+/**
+ * Tests rechaining initialized iterators, including the regression in
COLLECTIONS-900.
+ */
+class IteratorChainRechainingTest {
+
+ private static Stream<Arguments> chainingStates() {
+ final List<Arguments> arguments = new ArrayList<>();
+ for (final boolean unmodifiable : new boolean[] { false, true }) {
+ for (int consumed = 0; consumed <= 6; consumed++) {
+ for (final boolean lookAhead : new boolean[] { false, true }) {
+ for (final boolean emptyChildren : new boolean[] { false,
true }) {
+ arguments.add(Arguments.of(unmodifiable, consumed,
lookAhead, emptyChildren));
+ }
+ }
+ }
+ }
+ return arguments.stream();
+ }
+
+ private static IteratorChain<Integer> createChain(final List<Integer>
first, final List<Integer> second, final List<Integer> third,
+ final boolean emptyChildren) {
+ final IteratorChain<Integer> chain = new IteratorChain<>();
+ for (final List<Integer> list : Arrays.asList(first, second, third)) {
+ if (emptyChildren) {
+ chain.addIterator(Collections.emptyIterator());
+ }
+ chain.addIterator(list.iterator());
+ }
+ if (emptyChildren) {
+ chain.addIterator(Collections.emptyIterator());
+ }
+ return chain;
+ }
+
+ private static void exhaust(final Iterator<?> iterator) {
+ assertFalse(iterator.hasNext());
+ assertFalse(iterator.hasNext());
+ assertThrows(NoSuchElementException.class, iterator::next);
+ assertFalse(iterator.hasNext());
+ }
+
+ private static void position(final Iterator<Integer> iterator, final int
consumed, final boolean lookAhead) {
+ for (int i = 1; i <= consumed; i++) {
+ assertEquals(i, iterator.next());
+ }
+ if (lookAhead) {
+ assertEquals(consumed < 6, iterator.hasNext());
+ assertEquals(consumed < 6, iterator.hasNext());
+ }
+ }
+
+ private static <E> Iterator<E> wrap(final Iterator<E> iterator, final
boolean unmodifiable) {
+ return unmodifiable ?
UnmodifiableIterator.unmodifiableIterator(iterator) : iterator;
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testAddingDoesNotInvokeChild(final boolean unmodifiable) {
+ @SuppressWarnings("unchecked")
+ final Iterator<Integer> child = mock(Iterator.class);
+ final IteratorChain<Integer> source = new IteratorChain<>(child);
+ final IteratorChain<Integer> destination = new
IteratorChain<>(wrap(source, unmodifiable));
+ verifyNoInteractions(child);
+ when(child.hasNext()).thenReturn(true);
+ when(child.next()).thenReturn(1);
+ assertEquals(1, destination.next());
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testAddingInitializedChainDoesNotAdvanceChild(final boolean
unmodifiable) {
+ final Iterator<Integer> child = Arrays.asList(1, 2).iterator();
+ final IteratorChain<Integer> source = new IteratorChain<>(child);
+ assertTrue(source.hasNext());
+ final IteratorChain<Integer> destination = new
IteratorChain<>(wrap(source, unmodifiable));
+ assertEquals(Arrays.asList(1, 2), IteratorUtils.toList(destination));
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testConstructorAndFactoryVariants(final boolean unmodifiable) {
+ // Each construction path receives a fresh initialized source chain.
+ for (int variant = 0; variant < 6; variant++) {
+ final IteratorChain<Integer> source = new
IteratorChain<>(Arrays.asList(1, 2).iterator());
+ assertTrue(source.hasNext());
+ final Iterator<Integer> child = wrap(source, unmodifiable);
+ final Iterator<Integer> tail =
Collections.singletonList(3).iterator();
+ final Iterator<Integer> destination;
+ switch (variant) {
+ case 0:
+ final IteratorChain<Integer> added = new IteratorChain<>();
+ added.addIterator(child);
+ added.addIterator(tail);
+ destination = added;
+ break;
+ case 1:
+ final IteratorChain<Integer> single = new
IteratorChain<>(child);
+ single.addIterator(tail);
+ destination = single;
+ break;
+ case 2:
+ destination = new IteratorChain<>(child, tail);
+ break;
+ case 3:
+ destination = new IteratorChain<>(Collections.emptyIterator(),
child, tail);
+ break;
+ case 4:
+ destination = new IteratorChain<>(Arrays.asList(child, tail));
+ break;
+ default:
+ destination = IteratorUtils.chainedIterator(child, tail);
+ break;
+ }
+ assertEquals(Arrays.asList(1, 2, 3),
IteratorUtils.toList(destination), "Construction variant " + variant);
+ exhaust(destination);
+ }
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testEmptySource(final boolean unmodifiable) {
+ final IteratorChain<Integer> source = new IteratorChain<>();
+ exhaust(source);
+ final IteratorChain<Integer> destination = new
IteratorChain<>(wrap(source, unmodifiable));
+ assertThrows(IllegalStateException.class, destination::remove);
+ exhaust(destination);
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testLockedDestinationRejectsAdd(final boolean unmodifiable) {
+ final IteratorChain<Integer> destination = new
IteratorChain<>(Collections.singletonList(1).iterator());
+ final IteratorChain<Integer> source = new
IteratorChain<>(Collections.singletonList(2).iterator());
+ assertTrue(source.hasNext());
+ assertTrue(destination.hasNext());
+ assertThrows(UnsupportedOperationException.class, () ->
destination.addIterator(wrap(source, unmodifiable)));
+ assertEquals(1, destination.next());
+ exhaust(destination);
+ assertEquals(2, source.next());
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testNullElements(final boolean unmodifiable) {
+ final IteratorChain<Integer> source = new
IteratorChain<>(Arrays.asList(null, 1, null).iterator());
+ assertTrue(source.hasNext());
+ final IteratorChain<Integer> destination = new
IteratorChain<>(wrap(source, unmodifiable));
+ assertEquals(Arrays.asList(null, 1, null),
IteratorUtils.toList(destination));
+ exhaust(destination);
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testRechainAfterRemove(final boolean unmodifiable) {
+ final List<Integer> values = new ArrayList<>(Arrays.asList(1, 2, 3));
+ final IteratorChain<Integer> source = new
IteratorChain<>(values.iterator());
+ assertEquals(1, source.next());
+ source.remove();
+ final IteratorChain<Integer> destination = new
IteratorChain<>(wrap(source, unmodifiable));
+ assertThrows(IllegalStateException.class, destination::remove);
+ assertEquals(Arrays.asList(2, 3), IteratorUtils.toList(destination));
+ assertEquals(Arrays.asList(2, 3), values);
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testRechainAfterUnsuccessfulRemove(final boolean unmodifiable) {
+ final IteratorChain<Integer> source = new
IteratorChain<>(Arrays.asList(1, 2).iterator());
+ assertThrows(IllegalStateException.class, source::remove);
+ assertTrue(source.isLocked());
+ final IteratorChain<Integer> destination = new
IteratorChain<>(wrap(source, unmodifiable));
+ assertEquals(Arrays.asList(1, 2), IteratorUtils.toList(destination));
+ }
+
+ @ParameterizedTest
+ @MethodSource("chainingStates")
+ void testRemainingSequence(final boolean unmodifiable, final int consumed,
final boolean lookAhead, final boolean emptyChildren) {
+ final IteratorChain<Integer> source = createChain(Arrays.asList(1, 2,
3), Collections.singletonList(4), Arrays.asList(5, 6), emptyChildren);
+ position(source, consumed, lookAhead);
+ final IteratorChain<Integer> destination = new
IteratorChain<>(wrap(source, unmodifiable));
+ destination.addIterator(Arrays.asList(7, 8).iterator());
+ assertFalse(destination.isLocked());
+ for (int expected = consumed + 1; expected <= 8; expected++) {
+ assertTrue(destination.hasNext());
+ assertTrue(destination.hasNext());
+ assertEquals(expected, destination.next());
+ }
+ exhaust(destination);
+ assertTrue(destination.isLocked());
+ }
+
+ @ParameterizedTest
+ @MethodSource("chainingStates")
+ void testRemainingSequenceWithoutHasNext(final boolean unmodifiable, final
int consumed, final boolean lookAhead, final boolean emptyChildren) {
+ final IteratorChain<Integer> source = createChain(Arrays.asList(1, 2,
3), Collections.singletonList(4), Arrays.asList(5, 6), emptyChildren);
+ position(source, consumed, lookAhead);
+ final IteratorChain<Integer> destination = new
IteratorChain<>(wrap(source, unmodifiable));
+ for (int expected = consumed + 1; expected <= 6; expected++) {
+ assertEquals(expected, destination.next());
+ }
+ assertThrows(NoSuchElementException.class, destination::next);
+ exhaust(destination);
+ }
+
+ @ParameterizedTest
+ @MethodSource("chainingStates")
+ void testRemoveAfterRechaining(final boolean unmodifiable, final int
consumed, final boolean lookAhead, final boolean emptyChildren) {
+ final List<Integer> first = new ArrayList<>(Arrays.asList(1, 2, 3));
+ final List<Integer> second = new
ArrayList<>(Collections.singletonList(4));
+ final List<Integer> third = new ArrayList<>(Arrays.asList(5, 6));
+ final List<Integer> tail = new
ArrayList<>(Collections.singletonList(7));
+ final IteratorChain<Integer> source = createChain(first, second,
third, emptyChildren);
+ position(source, consumed, lookAhead);
+ final IteratorChain<Integer> destination = new
IteratorChain<>(wrap(source, unmodifiable));
+ destination.addIterator(tail.iterator());
+ assertThrows(IllegalStateException.class, destination::remove);
+ for (int expected = consumed + 1; expected <= 7; expected++) {
+ assertEquals(expected, destination.next());
+ // Look ahead across child boundaries and, for the final element,
exhaustion before removing.
+ assertEquals(expected < 7, destination.hasNext());
+ if (unmodifiable && expected <= 6) {
+ assertThrows(UnsupportedOperationException.class,
destination::remove);
+ } else {
+ destination.remove();
+ assertThrows(IllegalStateException.class, destination::remove);
+ }
+ }
+ final List<Integer> remaining = new ArrayList<>(first);
+ remaining.addAll(second);
+ remaining.addAll(third);
+ assertEquals(Arrays.asList(1, 2, 3, 4, 5, 6).subList(0, unmodifiable ?
6 : consumed), remaining);
+ assertTrue(tail.isEmpty());
+ exhaust(destination);
+ }
+
+ @ParameterizedTest
+ @ValueSource(booleans = { false, true })
+ void testRepeatedInitializedRechaining(final boolean unmodifiable) {
+ assertTimeoutPreemptively(Duration.ofSeconds(5), () -> {
+ IteratorChain<Integer> chain = new
IteratorChain<>(Arrays.asList(1, 2).iterator(),
Collections.singletonList(3).iterator());
+ for (int i = 0; i < 5000; i++) {
+ assertTrue(chain.hasNext());
+ chain = new IteratorChain<>(wrap(chain, unmodifiable));
+ }
+ assertEquals(Arrays.asList(1, 2, 3), IteratorUtils.toList(chain));
+ exhaust(chain);
+ });
+ }
+}
diff --git
a/src/test/java/org/apache/commons/collections4/iterators/IteratorChainTest.java
b/src/test/java/org/apache/commons/collections4/iterators/IteratorChainTest.java
index 4ada92c66..c9da3cafc 100644
---
a/src/test/java/org/apache/commons/collections4/iterators/IteratorChainTest.java
+++
b/src/test/java/org/apache/commons/collections4/iterators/IteratorChainTest.java
@@ -126,6 +126,25 @@ public class IteratorChainTest extends
AbstractIteratorTest<String> {
assertTrue(list3.isEmpty(), "List is empty");
}
+ /** COLLECTIONS-900. */
+ @Test
+ public void testChainingAfterHasNextCall() {
+ IteratorChain<String> chain = new IteratorChain<>();
+ chain.addIterator(list1.iterator());
+ chain.hasNext();
+ chain = new IteratorChain<>(chain);
+ chain.addIterator(list2.iterator());
+ // test that the first element is still returned correctly after a
hasNext() call
+ assertEquals(list1.get(0), chain.next());
+ // Same test with an unmodifiable IteratorChain.
+ chain = new IteratorChain<>();
+ chain.addIterator(list1.iterator());
+ chain.hasNext();
+ chain = new
IteratorChain<>(UnmodifiableIterator.unmodifiableIterator(chain));
+ chain.addIterator(list2.iterator());
+ assertEquals(list1.get(0), chain.next());
+ }
+
@Test
public void testChainingPerformsWell() {
Iterator<String> iter = makeObject();
