Simplified ConcatenatedSequence iteration logic. Non-recursive ConcatenatedSequence.size() to limit stack usage.
diff --git a/src/main/java/freemarker/core/AddConcatExpression.java b/src/main/java/freemarker/core/AddConcatExpression.java
index 077af8d..54e4d71 100644
--- a/src/main/java/freemarker/core/AddConcatExpression.java
+++ b/src/main/java/freemarker/core/AddConcatExpression.java
@@ -19,7 +19,10 @@
package freemarker.core;
+import java.util.ArrayList;
+import java.util.Arrays;
import java.util.HashSet;
+import java.util.List;
import java.util.Set;
import freemarker.template.SimpleNumber;
@@ -204,9 +207,40 @@
}
@Override
- public int size()
- throws TemplateModelException {
- return left.size() + right.size();
+ public int size() throws TemplateModelException {
+ int totalSize = 0;
+
+ ConcatenatedSequence[] concSeqsWithRightPending = new ConcatenatedSequence[2];
+ int concSeqsWithRightPendingLength = 0;
+ ConcatenatedSequence concSeqInFocus = this;
+
+ while (true) {
+ TemplateSequenceModel left;
+ while ((left = concSeqInFocus.left) instanceof ConcatenatedSequence) {
+ if (concSeqsWithRightPendingLength == concSeqsWithRightPending.length) {
+ concSeqsWithRightPending = Arrays.copyOf(concSeqsWithRightPending, concSeqsWithRightPendingLength * 2);
+ }
+ concSeqsWithRightPending[concSeqsWithRightPendingLength++] = concSeqInFocus;
+ concSeqInFocus = (ConcatenatedSequence) left;
+ }
+ totalSize += left.size();
+
+ while (true) {
+ TemplateSequenceModel right = concSeqInFocus.right;
+ if (right instanceof ConcatenatedSequence) {
+ concSeqInFocus = (ConcatenatedSequence) right;
+ break; // To jump at the left-descending loop
+ }
+ totalSize += right.size();
+
+ if (concSeqsWithRightPendingLength == 0) {
+ return totalSize;
+ }
+
+ concSeqsWithRightPendingLength--;
+ concSeqInFocus = concSeqsWithRightPending[concSeqsWithRightPendingLength];
+ }
+ }
}
@Override
@@ -225,7 +259,8 @@
private static class ConcatenatedSequenceIterator implements TemplateModelIterator {
/** The path from the root down to the parent of {@link #currentSegment} */
- private ParentStep parentStep = null;
+ private final List<ConcatenatedSequence> concSeqsWithRightPending = new ArrayList<>();
+ private ConcatenatedSequence concSeqWithLeftDescentPending;
private TemplateSequenceModel currentSegment;
private int currentSegmentNextIndex;
@@ -237,18 +272,7 @@
public ConcatenatedSequenceIterator(ConcatenatedSequence concatSeq) throws TemplateModelException {
// Descent down to the first nested sequence, and memorize the path down there
- descendToLeftmostSubsequence(concatSeq);
- }
-
- private void setCurrentSegment(TemplateSequenceModel currentSegment) throws TemplateModelException {
- if (currentSegment instanceof TemplateCollectionModel) {
- this.currentSegmentIterator = ((TemplateCollectionModel) currentSegment).iterator();
- this.currentSegment = null;
- } else {
- this.currentSegment = currentSegment;
- this.currentSegmentNextIndex = 0;
- this.currentSegmentIterator = null;
- }
+ concSeqWithLeftDescentPending = concatSeq;
}
@Override
@@ -285,6 +309,9 @@
prefetchedHasNext = true;
hasPrefetchedResult = true;
return;
+ } else {
+ currentSegmentIterator = null;
+ // Falls through
}
} else if (currentSegment != null) {
int size = currentSegment.size();
@@ -293,69 +320,50 @@
prefetchedHasNext = true;
hasPrefetchedResult = true;
return;
+ } else {
+ currentSegment = null;
+ // Falls through
}
- } else {
- // No current segment => We have already reached the end of the last segment in the past
+ } else if (concSeqWithLeftDescentPending != null) { // Nothing to fetch from, has to descend left first
+ ConcatenatedSequence leftDescentCurrentConcSeq = concSeqWithLeftDescentPending;
+ concSeqWithLeftDescentPending = null;
+ concSeqsWithRightPending.add(leftDescentCurrentConcSeq);
+
+ TemplateSequenceModel leftSeq;
+ while ((leftSeq = leftDescentCurrentConcSeq.left) instanceof ConcatenatedSequence) {
+ leftDescentCurrentConcSeq = (ConcatenatedSequence) leftSeq;
+ concSeqsWithRightPending.add(leftDescentCurrentConcSeq);
+ }
+ setCurrentSegment(leftSeq);
+ continue; // Jump to fetching from current segment
+ }
+
+ // If we reach this, then the current segment was fully consumed, so we have to switch to the next segment.
+
+ if (concSeqsWithRightPending.isEmpty()) {
+ prefetchedNext = null;
prefetchedHasNext = false;
hasPrefetchedResult = true;
return;
}
- // If we reach this, then the current segment was fully consumed, so we switch to the next segment.
-
- if (parentStep == null) {
- setIteratorEndWasReached();
- return;
- }
-
- if (!parentStep.rightVisited) {
- parentStep.rightVisited = true;
- descendToLeftmostSubsequence(parentStep.concSeq.right);
+ TemplateSequenceModel right = concSeqsWithRightPending.remove(concSeqsWithRightPending.size() - 1).right;
+ if (right instanceof ConcatenatedSequence) {
+ concSeqWithLeftDescentPending = (ConcatenatedSequence) right;
} else {
- while (true) {
- // Ascend one level
- parentStep = parentStep.parentStep;
-
- if (parentStep == null) {
- setIteratorEndWasReached();
- return;
- }
-
- if (!parentStep.rightVisited) {
- parentStep.rightVisited = true;
- descendToLeftmostSubsequence(parentStep.concSeq.right);
- break;
- }
- }
+ setCurrentSegment(right);
}
}
}
- private void descendToLeftmostSubsequence(TemplateSequenceModel maybeConcSeq) throws TemplateModelException {
- while (maybeConcSeq instanceof ConcatenatedSequence) {
- ConcatenatedSequence concSeq = (ConcatenatedSequence) maybeConcSeq;
- parentStep = new ParentStep(concSeq, parentStep);
- maybeConcSeq = concSeq.left;
- }
- setCurrentSegment(maybeConcSeq);
- }
-
- private void setIteratorEndWasReached() {
- currentSegment = null;
- currentSegmentIterator = null;
- prefetchedNext = null;
- prefetchedHasNext = false;
- hasPrefetchedResult = true;
- }
-
- private static class ParentStep {
- private final ConcatenatedSequence concSeq;
- private final ParentStep parentStep;
- private boolean rightVisited;
-
- public ParentStep(ConcatenatedSequence concSeq, ParentStep parentStep) {
- this.concSeq = concSeq;
- this.parentStep = parentStep;
+ private void setCurrentSegment(TemplateSequenceModel currentSegment) throws TemplateModelException {
+ if (currentSegment instanceof TemplateCollectionModel) {
+ this.currentSegmentIterator = ((TemplateCollectionModel) currentSegment).iterator();
+ this.currentSegment = null;
+ } else {
+ this.currentSegment = currentSegment;
+ this.currentSegmentNextIndex = 0;
+ this.currentSegmentIterator = null;
}
}
}
diff --git a/src/manual/en_US/book.xml b/src/manual/en_US/book.xml
index 1e7a410..f307d9e 100644
--- a/src/manual/en_US/book.xml
+++ b/src/manual/en_US/book.xml
@@ -30094,19 +30094,35 @@
<listitem>
<para>When concatenating many sequences (like Java
<literal>List</literal>-s) with the <literal>+</literal>
- operator, iterating through the resulting sequence has become
- very slow as the number of sequences added increased. Now
- iteration is reasonably fast, regardless of the number of
- sequences added. But this still only applies to mere iteration
- (like using <literal><#list seq as
- <replaceable>...</replaceable>></literal>, or
- <literal>seq?join(', ')</literal>). Accessing items by index
- (like <literal>seq[n]</literal>) is still as slow as it always
- was. (Note that <literal>+</literal> is still only meant to be
- used to quickly create a concatenated view from a few sequences,
- and not for constructing sequences from hundreds of small
- sequences. So it's still not recommended to concatenate more
- then a few tens of sequences.)</para>
+ operator:</para>
+
+ <itemizedlist>
+ <listitem>
+ <para>In previous versions iIterating through the resulting
+ sequence has become very slow as the number of sequences
+ added increased. Now iteration is reasonably fast,
+ regardless of the number of sequences added. But this still
+ only applies to mere iteration (like using
+ <literal><#list <replaceable>seq</replaceable> as
+ <replaceable>...</replaceable>></literal>, or
+ <literal><replaceable>seq</replaceable>?join(',
+ ')</literal>). Accessing items by index (like
+ <literal><replaceable>seq</replaceable>[n]</literal>) is
+ still as slow as it always was. (Note that
+ <literal>+</literal> is still only meant to be used to
+ quickly create a concatenated view from a few sequences, and
+ not for constructing sequences from hundreds of small
+ sequences. So it's still not recommended to concatenate more
+ then a few tens of sequences.)</para>
+ </listitem>
+
+ <listitem>
+ <para>In previous versions
+ <literal><replaceable>seq</replaceable>?size</literal> could
+ cause stack overflow (if you have concatenated thousands of
+ sequences). Now the impementation is not recursive.</para>
+ </listitem>
+ </itemizedlist>
</listitem>
</itemizedlist>
</section>
diff --git a/src/test/java/freemarker/core/ConcatenatedSequenceTest.java b/src/test/java/freemarker/core/ConcatenatedSequenceTest.java
index 8cedd9c..1280cae 100644
--- a/src/test/java/freemarker/core/ConcatenatedSequenceTest.java
+++ b/src/test/java/freemarker/core/ConcatenatedSequenceTest.java
@@ -211,6 +211,12 @@
}
assertEquals(Arrays.asList(expectedItems), actualItems);
}
+
+ if (repeatable) {
+ seq = seqSupplier.get();
+ }
+
+ assertEquals(expectedItems.length, seq.size());
}
}
\ No newline at end of file
