This is an automated email from the ASF dual-hosted git repository.
ddekany pushed a commit to branch 3
in repository https://gitbox.apache.org/repos/asf/freemarker.git
The following commit(s) were added to refs/heads/3 by this push:
new 3d3dcac6 Forward ported from 2.3-gae: ConcatenatedSequence performance
improvements
3d3dcac6 is described below
commit 3d3dcac6b355a5a4ef39726a03a229a4112c82a2
Author: ddekany <[email protected]>
AuthorDate: Fri Dec 15 23:15:11 2023 +0100
Forward ported from 2.3-gae: ConcatenatedSequence performance improvements
---
.../freemarker/core/ConcatenatedSequenceTest.java | 318 +++++++++++++++++++++
.../apache/freemarker/core/ASTExpAddOrConcat.java | 229 +++++++++++++--
2 files changed, 528 insertions(+), 19 deletions(-)
diff --git
a/freemarker-core-test/src/test/java/org/apache/freemarker/core/ConcatenatedSequenceTest.java
b/freemarker-core-test/src/test/java/org/apache/freemarker/core/ConcatenatedSequenceTest.java
new file mode 100644
index 00000000..0e71e4bc
--- /dev/null
+++
b/freemarker-core-test/src/test/java/org/apache/freemarker/core/ConcatenatedSequenceTest.java
@@ -0,0 +1,318 @@
+/*
+ * 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.freemarker.core;
+
+import org.apache.freemarker.core.ASTExpAddOrConcat.ConcatenatedSequence;
+import org.apache.freemarker.core.model.TemplateModel;
+import org.apache.freemarker.core.model.TemplateModelIterator;
+import org.apache.freemarker.core.model.TemplateSequenceModel;
+import org.apache.freemarker.core.model.TemplateStringModel;
+import org.apache.freemarker.core.model.impl.DefaultListAdapter;
+import org.apache.freemarker.core.model.impl.DefaultObjectWrapper;
+import org.apache.freemarker.core.model.impl.SimpleString;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.function.Supplier;
+
+import static org.junit.Assert.*;
+
+public class ConcatenatedSequenceTest {
+ interface SeqFactory {
+ TemplateSequenceModel create(String... items);
+ boolean isUnrepeatable();
+ }
+
+ @Test
+ public void testForNativeSequences() throws TemplateException {
+ testWithSegmentFactory(new SeqFactory() {
+ @Override
+ public TemplateSequenceModel create(String... items) {
+ return new NativeSequence(Arrays.stream(items).map(it -> it ==
null ? null : (TemplateModel) new SimpleString(it)).toList());
+ }
+
+ @Override
+ public boolean isUnrepeatable() {
+ return false;
+ }
+ });
+ }
+
+ @Test
+ public void testForListAdapter() throws TemplateException {
+ DefaultObjectWrapper objectWrapper = new
DefaultObjectWrapper.Builder(Configuration.VERSION_3_0_0).build();
+ testWithSegmentFactory(new SeqFactory() {
+ @Override
+ public TemplateSequenceModel create(String... items) {
+ return DefaultListAdapter.adapt(Arrays.asList(items),
objectWrapper);
+ }
+
+ @Override
+ public boolean isUnrepeatable() {
+ return false;
+ }
+ });
+ }
+
+ public void testWithSegmentFactory(SeqFactory segmentFactory) throws
TemplateException {
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(segmentFactory.create(),
segmentFactory.create()));
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(segmentFactory.create(),
segmentFactory.create("b")),
+ "b");
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(segmentFactory.create("a"),
segmentFactory.create()),
+ "a");
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(segmentFactory.create("a"),
segmentFactory.create("b")),
+ "a", "b");
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(
+ new ConcatenatedSequence(
+ segmentFactory.create(),
+ segmentFactory.create()),
+ new ConcatenatedSequence(
+ segmentFactory.create(),
+ segmentFactory.create())
+ )
+ );
+
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(
+ new ConcatenatedSequence(
+ segmentFactory.create("a", "b"),
+ segmentFactory.create()),
+ new ConcatenatedSequence(
+ segmentFactory.create(),
+ segmentFactory.create())
+ ),
+ "a", "b"
+ );
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(
+ new ConcatenatedSequence(
+ segmentFactory.create(),
+ segmentFactory.create("a", "b")),
+ new ConcatenatedSequence(
+ segmentFactory.create(),
+ segmentFactory.create())
+ ),
+ "a", "b"
+ );
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(
+ new ConcatenatedSequence(
+ segmentFactory.create(),
+ segmentFactory.create()),
+ new ConcatenatedSequence(
+ segmentFactory.create("a", "b"),
+ segmentFactory.create())
+ ),
+ "a", "b"
+ );
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(
+ new ConcatenatedSequence(
+ segmentFactory.create(),
+ segmentFactory.create()),
+ new ConcatenatedSequence(
+ segmentFactory.create(),
+ segmentFactory.create("a", "b"))
+ ),
+ "a", "b"
+ );
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(
+ new ConcatenatedSequence(
+ segmentFactory.create("a"),
+ segmentFactory.create("b")),
+ new ConcatenatedSequence(
+ segmentFactory.create(),
+ segmentFactory.create())
+ ),
+ "a", "b"
+ );
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(
+ new ConcatenatedSequence(
+ segmentFactory.create(),
+ segmentFactory.create("a")),
+ new ConcatenatedSequence(
+ segmentFactory.create("b"),
+ segmentFactory.create())
+ ),
+ "a", "b"
+ );
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(
+ new ConcatenatedSequence(
+ segmentFactory.create(),
+ segmentFactory.create()),
+ new ConcatenatedSequence(
+ segmentFactory.create("a"),
+ segmentFactory.create("b"))
+ ),
+ "a", "b"
+ );
+
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(
+ new ConcatenatedSequence(
+ new ConcatenatedSequence(
+ segmentFactory.create("a"),
+ segmentFactory.create("b")),
+ segmentFactory.create("c")),
+ segmentFactory.create("d")),
+ "a", "b", "c", "d");
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(
+ new ConcatenatedSequence(
+ segmentFactory.create("a"),
+ segmentFactory.create("b")),
+ new ConcatenatedSequence(
+ segmentFactory.create("c"),
+ segmentFactory.create("d"))
+ ),
+ "a", "b", "c", "d");
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(
+ segmentFactory.create("a"),
+ new ConcatenatedSequence(
+ segmentFactory.create("b"),
+ new ConcatenatedSequence(
+ segmentFactory.create("c"),
+ segmentFactory.create("d")
+ )
+ )
+ ),
+ "a", "b", "c", "d");
+
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(
+ new ConcatenatedSequence(
+ segmentFactory.create("a", "b"),
+ segmentFactory.create("c", "d")),
+ new ConcatenatedSequence(
+ segmentFactory.create("e", "f"),
+ segmentFactory.create("g", "h"))
+ ),
+ "a", "b", "c", "d", "e", "f", "g", "h");
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(
+ segmentFactory.create("a", "b", "c"),
+ new ConcatenatedSequence(
+ segmentFactory.create("d", "e"),
+ segmentFactory.create("f", "g", "h"))
+ ),
+ "a", "b", "c", "d", "e", "f", "g", "h");
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(
+ new ConcatenatedSequence(
+ segmentFactory.create("a", "b"),
+ segmentFactory.create("c", "d")),
+ segmentFactory.create("e", "f", "g", "h")
+ ),
+ "a", "b", "c", "d", "e", "f", "g", "h");
+
+ if (!segmentFactory.isUnrepeatable()) {
+ // Test when the same segment seq instance is for multiple times
in a concatenated seq.
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ {
+ TemplateSequenceModel ab = segmentFactory.create("a",
"b");
+ ConcatenatedSequence abab = new
ConcatenatedSequence(ab, ab);
+ return new ConcatenatedSequence(abab, abab);
+ },
+ "a", "b", "a", "b", "a", "b", "a", "b");
+ }
+
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(
+ new ConcatenatedSequence(
+ segmentFactory.create(null, "a"),
+ segmentFactory.create("b", null)),
+ segmentFactory.create((String) null)
+ ),
+ null, "a", "b", null, null);
+ }
+
+ private void assertConcatenationResult(
+ boolean repeatable,
+ Supplier<ConcatenatedSequence> seqSupplier,
+ String... expectedItems)
+ throws TemplateException {
+ ConcatenatedSequence seq = seqSupplier.get();
+
+ {
+ List<String> actualItems = new ArrayList<>();
+ for (TemplateModelIterator iter = seq.iterator(); iter.hasNext();
) {
+ actualItems.add(asNullableString((TemplateStringModel)
iter.next()));
+ }
+ assertEquals(Arrays.asList(expectedItems), actualItems);
+ }
+
+ if (repeatable) {
+ seq = seqSupplier.get();
+ }
+
+ {
+ List<String> actualItems = new ArrayList<>();
+ for (TemplateModelIterator iter = seq.iterator(); iter.hasNext();
) {
+ assertTrue(iter.hasNext());
+ actualItems.add(asNullableString((TemplateStringModel)
iter.next()));
+ }
+ assertEquals(Arrays.asList(expectedItems), actualItems);
+ }
+
+ if (repeatable) {
+ seq = seqSupplier.get();
+ }
+
+ {
+ List<String> actualItems = new ArrayList<>();
+ int size = seq.getCollectionSize();
+ for (int i = 0; i < size; i++) {
+ actualItems.add(asNullableString((TemplateStringModel)
seq.get(i)));
+ }
+ assertEquals(Arrays.asList(expectedItems), actualItems);
+ assertNull(seq.get(-1));
+ assertNull(seq.get(size));
+ assertNull(seq.get(size + 1));
+ }
+
+ if (repeatable) {
+ seq = seqSupplier.get();
+ }
+
+ assertEquals(expectedItems.length, seq.getCollectionSize());
+
+ if (repeatable) {
+ seq = seqSupplier.get();
+ }
+
+ assertEquals(expectedItems.length == 0, seq.isEmptyCollection());
+ }
+
+ private String asNullableString(TemplateStringModel model) throws
TemplateException {
+ return model != null ? model.getAsString() : null;
+ }
+
+}
diff --git
a/freemarker-core/src/main/java/org/apache/freemarker/core/ASTExpAddOrConcat.java
b/freemarker-core/src/main/java/org/apache/freemarker/core/ASTExpAddOrConcat.java
index d222aa57..bb345a3e 100644
---
a/freemarker-core/src/main/java/org/apache/freemarker/core/ASTExpAddOrConcat.java
+++
b/freemarker-core/src/main/java/org/apache/freemarker/core/ASTExpAddOrConcat.java
@@ -19,22 +19,13 @@
package org.apache.freemarker.core;
-import java.util.Collection;
-import java.util.LinkedHashMap;
-import java.util.Map;
-
import org.apache.freemarker.core.arithmetic.ArithmeticEngine;
-import org.apache.freemarker.core.model.TemplateCollectionModel;
-import org.apache.freemarker.core.model.TemplateHashModel;
-import org.apache.freemarker.core.model.TemplateHashModelEx;
-import org.apache.freemarker.core.model.TemplateMarkupOutputModel;
-import org.apache.freemarker.core.model.TemplateModel;
-import org.apache.freemarker.core.model.TemplateModelIterator;
-import org.apache.freemarker.core.model.TemplateNumberModel;
-import org.apache.freemarker.core.model.TemplateSequenceModel;
+import org.apache.freemarker.core.model.*;
import org.apache.freemarker.core.model.impl.SimpleNumber;
import org.apache.freemarker.core.model.impl.SimpleString;
+import java.util.*;
+
/**
* AST expression node: binary {@code +} operator. Note that this is treated
separately from the other 4 arithmetic
* operators, since it's overloaded to mean concatenation of string-s,
sequences and hash-es too.
@@ -178,7 +169,7 @@ final class ASTExpAddOrConcat extends ASTExpression {
return ParameterRole.forBinaryOperatorOperand(idx);
}
- private static final class ConcatenatedSequence implements
TemplateSequenceModel {
+ static final class ConcatenatedSequence implements TemplateSequenceModel {
private final TemplateSequenceModel left;
private final TemplateSequenceModel right;
@@ -190,23 +181,223 @@ final class ASTExpAddOrConcat extends ASTExpression {
@Override
public int getCollectionSize()
throws TemplateException {
- return left.getCollectionSize() + right.getCollectionSize();
+ 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.getCollectionSize();
+
+ while (true) {
+ TemplateSequenceModel right = concSeqInFocus.right;
+ if (right instanceof ConcatenatedSequence) {
+ concSeqInFocus = (ConcatenatedSequence) right;
+ break; // To jump at the left-descending loop
+ }
+ totalSize += right.getCollectionSize();
+
+ if (concSeqsWithRightPendingLength == 0) {
+ return totalSize;
+ }
+
+ concSeqsWithRightPendingLength--;
+ concSeqInFocus =
concSeqsWithRightPending[concSeqsWithRightPendingLength];
+ }
+ }
}
@Override
public boolean isEmptyCollection() throws TemplateException {
- return left.isEmptyCollection() && right.isEmptyCollection();
+ 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;
+ }
+ if (!left.isEmptyCollection()) {
+ return false;
+ }
+
+ while (true) {
+ TemplateSequenceModel right = concSeqInFocus.right;
+ if (right instanceof ConcatenatedSequence) {
+ concSeqInFocus = (ConcatenatedSequence) right;
+ break; // To jump at the left-descending loop
+ }
+ if (!right.isEmptyCollection()) {
+ return false;
+ }
+
+ if (concSeqsWithRightPendingLength == 0) {
+ return true;
+ }
+
+ concSeqsWithRightPendingLength--;
+ concSeqInFocus =
concSeqsWithRightPending[concSeqsWithRightPendingLength];
+ }
+ }
}
@Override
- public TemplateModel get(int i) throws TemplateException {
- int leftSize = left.getCollectionSize();
- return i < leftSize ? left.get(i) : right.get(i - leftSize);
+ public TemplateModel get(int index) throws TemplateException {
+ if (index < 0) {
+ return null;
+ }
+
+ 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;
+ }
+ {
+ int segmentSize = left.getCollectionSize();
+ totalSize += segmentSize;
+ if (totalSize > index) {
+ return left.get(index - (totalSize - segmentSize));
+ }
+ }
+
+ while (true) {
+ TemplateSequenceModel right = concSeqInFocus.right;
+ if (right instanceof ConcatenatedSequence) {
+ concSeqInFocus = (ConcatenatedSequence) right;
+ break; // To jump at the left-descending loop
+ }
+ {
+ int segmentSize = right.getCollectionSize();
+ totalSize += segmentSize;
+ if (totalSize > index) {
+ return right.get(index - (totalSize -
segmentSize));
+ }
+ }
+
+ if (concSeqsWithRightPendingLength == 0) {
+ return null;
+ }
+
+ concSeqsWithRightPendingLength--;
+ concSeqInFocus =
concSeqsWithRightPending[concSeqsWithRightPendingLength];
+ }
+ }
}
@Override
public TemplateModelIterator iterator() throws TemplateException {
- return new ConcatenatedTemplateModelIterator(left.iterator(),
right.iterator());
+ return new ConcatenatedSequenceIterator(this);
+ }
+ }
+
+ private static class ConcatenatedSequenceIterator implements
TemplateModelIterator {
+ /** The path from the root down to the parent of the current segment
({@link #currentSegmentIterator}) */
+ private final List<ConcatenatedSequence> concSeqsWithRightPending =
new ArrayList<>();
+ private ConcatenatedSequence concSeqWithLeftDescentPending;
+
+ private TemplateModelIterator currentSegmentIterator;
+
+ private boolean hasPrefetchedResult;
+ private TemplateModel prefetchedNext;
+ private boolean prefetchedHasNext;
+
+ public ConcatenatedSequenceIterator(ConcatenatedSequence concatSeq)
throws TemplateException {
+ // Descent down to the first nested sequence, and memorize the
path down there
+ concSeqWithLeftDescentPending = concatSeq;
+ }
+
+ @Override
+ public TemplateModel next() throws TemplateException {
+ ensureHasPrefetchedResult();
+
+ if (!prefetchedHasNext) {
+ throw new TemplateException("The collection has no more
elements.");
+ }
+
+ TemplateModel result = prefetchedNext;
+ hasPrefetchedResult = false; // To consume prefetched element
+ prefetchedNext = null; // To not prevent GC
+ return result;
+ }
+
+ @Override
+ public boolean hasNext() throws TemplateException {
+ ensureHasPrefetchedResult();
+ return prefetchedHasNext;
+ }
+
+ private void ensureHasPrefetchedResult() throws TemplateException {
+ if (hasPrefetchedResult) {
+ return;
+ }
+
+ while (true) {
+ // Try to fetch the next value from the current segment:
+ if (currentSegmentIterator != null) {
+ boolean hasNext = currentSegmentIterator.hasNext();
+ if (hasNext) {
+ prefetchedNext = currentSegmentIterator.next();
+ prefetchedHasNext = true;
+ hasPrefetchedResult = true;
+ return;
+ } else {
+ currentSegmentIterator = null;
+ // Falls through
+ }
+ } 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);
+ }
+ this.currentSegmentIterator = leftSeq.iterator();
+ 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;
+ }
+
+ TemplateSequenceModel right =
concSeqsWithRightPending.remove(concSeqsWithRightPending.size() - 1).right;
+ if (right instanceof ConcatenatedSequence) {
+ concSeqWithLeftDescentPending = (ConcatenatedSequence)
right;
+ } else {
+ this.currentSegmentIterator = right.iterator();
+ }
+ }
}
}
