You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by us...@apache.org on 2026/07/27 17:14:26 UTC
(lucene) branch main updated: Add (configurable) guards for complexity of expressions (#16423)
This is an automated email from the ASF dual-hosted git repository.
uschindler pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/main by this push:
new b6c2c31e225 Add (configurable) guards for complexity of expressions (#16423)
b6c2c31e225 is described below
commit b6c2c31e22518503a8da0cd26b196217b30f4186
Author: Uwe Schindler <us...@apache.org>
AuthorDate: Mon Jul 27 19:14:20 2026 +0200
Add (configurable) guards for complexity of expressions (#16423)
* Add (configurable) guards for complexity of expressions to fail with ParseException instead of StackOverflowError or LinkageErrors
* Raise nesting limit to 1024, add documentation that implicit precedence also counts
* Avoid 2nd recursive tree walking by doing it while building classfile
* add changes entry
* add extra test (on boundary)
---
lucene/CHANGES.txt | 6 ++
.../lucene/expressions/js/JavascriptCompiler.java | 82 ++++++++++++++++++++--
.../js/JavascriptNestingDepthListener.java | 60 ++++++++++++++++
.../lucene/expressions/js/CompilerTestCase.java | 3 +-
.../expressions/js/TestJavascriptCompiler.java | 51 ++++++++++++++
5 files changed, 194 insertions(+), 8 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 338918dac62..2cf190740d8 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -341,6 +341,12 @@ Improvements
* GITHUB#16271: Add detail to KNN no-match explanations. (Jakub Slowinski)
+* GITHUB#16423: Add (configurable) guards for complexity of expressions. Previously
+ the expressions parser could throw StackOverflowError on deeply nested expressions
+ or also cause VerifyError and other LinkageErrors when the expression was to complex.
+ The new code allows to add a hard limit for nesting (default is 1024) and no longer
+ throws virtual machine errors. (Uwe Schindler, Seth Kraft)
+
Optimizations
---------------------
* GITHUG#16280: Single-pass writeString fast path for short strings in ByteBuffersDataOutput (neoremind)
diff --git a/lucene/expressions/src/java/org/apache/lucene/expressions/js/JavascriptCompiler.java b/lucene/expressions/src/java/org/apache/lucene/expressions/js/JavascriptCompiler.java
index a35f8c7072f..ae2ccc67031 100644
--- a/lucene/expressions/src/java/org/apache/lucene/expressions/js/JavascriptCompiler.java
+++ b/lucene/expressions/src/java/org/apache/lucene/expressions/js/JavascriptCompiler.java
@@ -58,6 +58,7 @@ import org.antlr.v4.runtime.BaseErrorListener;
import org.antlr.v4.runtime.CharStreams;
import org.antlr.v4.runtime.CommonTokenStream;
import org.antlr.v4.runtime.DiagnosticErrorListener;
+import org.antlr.v4.runtime.ParserRuleContext;
import org.antlr.v4.runtime.RecognitionException;
import org.antlr.v4.runtime.Recognizer;
import org.antlr.v4.runtime.atn.PredictionMode;
@@ -100,6 +101,13 @@ import org.apache.lucene.util.SuppressForbidden;
* be resolved correctly using a private {@link Lookup} instance. Ideally the methods should be
* {@code static}, but you can use {@link MethodHandle#bindTo(Object)} to bind it to a receiver.
*
+ * <p>The parser has a default maximum nesting limit of 1024 (see {@link
+ * #DEFAULT_MAX_NESTING_DEPTH}) which is enforced during parsing. Violating it will cause a {@link
+ * ParseException}. Please keep in mind that also code like <code class="language-java">
+ * a + b + c + d + ... + z</code> is treated as if it would look like this:
+ * <code class="language-java">(((((a + b) + c) + d) + ...) + z)</code> (because of the nature of
+ * the JVM as a stack-based machine).
+ *
* @lucene.experimental
*/
public final class JavascriptCompiler {
@@ -126,8 +134,12 @@ public final class JavascriptCompiler {
private static final ExceptionsAttribute ATTR_THROWS_IOEXCEPTION =
ExceptionsAttribute.ofSymbols(IOException.class.describeConstable().orElseThrow());
+ /** The default maximum depth of nesting (function calls, precedence - also implicit) */
+ public static final int DEFAULT_MAX_NESTING_DEPTH = 1024;
+
final String sourceText;
final Map<String, MethodHandle> functions;
+ final int maxNestingDepth;
final boolean picky;
/**
@@ -136,6 +148,8 @@ public final class JavascriptCompiler {
* @param sourceText The expression to compile
* @return A new compiled expression
* @throws ParseException on failure to compile
+ * @throws IllegalStateException if the resulting expression class fails to link (e.g.,
+ * complexity)
*/
public static Expression compile(String sourceText) throws ParseException {
return compile(sourceText, DEFAULT_FUNCTIONS);
@@ -152,10 +166,36 @@ public final class JavascriptCompiler {
* @param functions map of String names to {@link MethodHandle}s
* @return A new compiled expression
* @throws ParseException on failure to compile
+ * @throws IllegalArgumentException if any of the functions does not have correct signature
+ * @throws IllegalStateException if the resulting expression class fails to link (e.g.,
+ * complexity)
*/
public static Expression compile(String sourceText, Map<String, MethodHandle> functions)
throws ParseException {
- return compile(sourceText, functions, false);
+ return compile(sourceText, functions, DEFAULT_MAX_NESTING_DEPTH);
+ }
+
+ /**
+ * Compiles the given expression with the supplied custom functions using a custom maximum nesting
+ * depth.
+ *
+ * <p>Functions must be {@code public static}, return {@code double} and can take from zero to 256
+ * {@code double} parameters.
+ *
+ * @param sourceText The expression to compile
+ * @param functions map of String names to {@link MethodHandle}s
+ * @param maxNestingDepth the maximum depth of nesting (function calls, precedence - also
+ * implicit)
+ * @return A new compiled expression
+ * @throws ParseException on failure to compile
+ * @throws IllegalArgumentException if any of the functions does not have correct signature
+ * @throws IllegalStateException if the resulting expression class fails to link (e.g.,
+ * complexity)
+ */
+ public static Expression compile(
+ String sourceText, Map<String, MethodHandle> functions, int maxNestingDepth)
+ throws ParseException {
+ return compile(sourceText, functions, maxNestingDepth, false);
}
/**
@@ -166,17 +206,24 @@ public final class JavascriptCompiler {
*
* @param sourceText The expression to compile
* @param functions map of String names to {@link MethodHandle}s
+ * @param maxNestingDepth the maximum depth of nesting (function calls, precedence - also
+ * implicit)
* @param picky whether to throw exception on ambiguity or other internal parsing issues (this
* option makes things slower too, it is only for debugging).
* @return A new compiled expression
* @throws ParseException on failure to compile
+ * @throws IllegalArgumentException if any of the functions does not have correct signature
+ * @throws IllegalStateException if the resulting expression class fails to link (e.g.,
+ * complexity)
*/
- static Expression compile(String sourceText, Map<String, MethodHandle> functions, boolean picky)
+ static Expression compile(
+ String sourceText, Map<String, MethodHandle> functions, int maxNestingDepth, boolean picky)
throws ParseException {
for (MethodHandle m : functions.values()) {
checkFunction(m);
}
- return new JavascriptCompiler(sourceText, functions, picky).compileExpression();
+ return new JavascriptCompiler(sourceText, functions, maxNestingDepth, picky)
+ .compileExpression();
}
/**
@@ -185,9 +232,10 @@ public final class JavascriptCompiler {
* @param sourceText The expression to compile
*/
private JavascriptCompiler(
- String sourceText, Map<String, MethodHandle> functions, boolean picky) {
+ String sourceText, Map<String, MethodHandle> functions, int maxNestingDepth, boolean picky) {
this.sourceText = Objects.requireNonNull(sourceText, "sourceText");
this.functions = Map.copyOf(functions);
+ this.maxNestingDepth = maxNestingDepth;
this.picky = picky;
}
@@ -215,6 +263,12 @@ public final class JavascriptCompiler {
throw cause;
}
throw re;
+ } catch (StackOverflowError soe) {
+ // we should catch this before in the visitor, but too high limits may cause this.
+ final var e =
+ new ParseException("Invalid expression '" + sourceText + "': Nesting level too deep", -1);
+ e.initCause(soe);
+ throw e;
}
try {
@@ -222,10 +276,12 @@ public final class JavascriptCompiler {
LOOKUP.defineHiddenClassWithClassData(
classFile, constantsMap.keySet().stream().map(functions::get).toList(), true);
return invokeConstructor(lookup, lookup.lookupClass(), externalsMap);
- } catch (ReflectiveOperationException exception) {
+ } catch (ReflectiveOperationException | LinkageError e) {
throw new IllegalStateException(
- "An internal error occurred attempting to compile the expression (" + sourceText + ").",
- exception);
+ "An internal error occurred attempting to compile the expression ('"
+ + sourceText
+ + "'). This may be caused by too complex code triggering limits inside the Java VM.",
+ e);
}
}
@@ -258,6 +314,10 @@ public final class JavascriptCompiler {
setupPicky(javascriptParser);
}
javascriptParser.setErrorHandler(new JavascriptParserErrorStrategy());
+ // add listener to detect too deep nesting early, this may not catch all occurrences... (this
+ // will count root node, so add one recursion extra).
+ javascriptParser.addParseListener(
+ new JavascriptNestingDepthListener(sourceText, maxNestingDepth + 1));
return javascriptParser.compile();
}
@@ -340,10 +400,18 @@ public final class JavascriptCompiler {
CodeBuilder gen,
final Map<String, Integer> externalsMap,
final Map<String, Integer> constantsMap) {
+ // we do an extra check on the tree to make sure the final structure is not too deeply nested:
+ final var nestingChecker = new JavascriptNestingDepthListener(sourceText, maxNestingDepth);
// to completely hide the ANTLR visitor we use an anonymous impl:
return new JavascriptBaseVisitor<>() {
private final Deque<TypeKind> typeStack = new ArrayDeque<>();
+ private void visit(ParserRuleContext ctx) {
+ nestingChecker.enterEveryRule(ctx);
+ ctx.accept(this);
+ nestingChecker.exitEveryRule(ctx);
+ }
+
@Override
public Void visitCompile(JavascriptParser.CompileContext ctx) {
typeStack.push(TypeKind.DOUBLE);
diff --git a/lucene/expressions/src/java/org/apache/lucene/expressions/js/JavascriptNestingDepthListener.java b/lucene/expressions/src/java/org/apache/lucene/expressions/js/JavascriptNestingDepthListener.java
new file mode 100644
index 00000000000..cc74a32f660
--- /dev/null
+++ b/lucene/expressions/src/java/org/apache/lucene/expressions/js/JavascriptNestingDepthListener.java
@@ -0,0 +1,60 @@
+/*
+ * 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.lucene.expressions.js;
+
+import org.antlr.v4.runtime.ParserRuleContext;
+import org.antlr.v4.runtime.tree.ErrorNode;
+import org.antlr.v4.runtime.tree.ParseTreeListener;
+import org.antlr.v4.runtime.tree.TerminalNode;
+
+final class JavascriptNestingDepthListener implements ParseTreeListener {
+ private final String sourceText;
+ private final int maxNestingDepth;
+
+ private int depth = 0;
+
+ public JavascriptNestingDepthListener(String sourceText, int maxNestingDepth) {
+ super();
+ this.sourceText = sourceText;
+ this.maxNestingDepth = maxNestingDepth;
+ }
+
+ @Override
+ public void visitTerminal(TerminalNode node) {}
+
+ @Override
+ public void visitErrorNode(ErrorNode node) {}
+
+ @Override
+ public void enterEveryRule(ParserRuleContext ctx) {
+ depth++;
+ if (depth > maxNestingDepth) {
+ throw JavascriptCompiler.newWrappedParseException(
+ "Invalid expression '"
+ + sourceText
+ + "': Nesting level too deep (>"
+ + maxNestingDepth
+ + ")",
+ ctx.start != null ? ctx.start.getStartIndex() : -1);
+ }
+ }
+
+ @Override
+ public void exitEveryRule(ParserRuleContext ctx) {
+ depth--;
+ }
+}
diff --git a/lucene/expressions/src/test/org/apache/lucene/expressions/js/CompilerTestCase.java b/lucene/expressions/src/test/org/apache/lucene/expressions/js/CompilerTestCase.java
index d7cc843efda..b28eb480b19 100644
--- a/lucene/expressions/src/test/org/apache/lucene/expressions/js/CompilerTestCase.java
+++ b/lucene/expressions/src/test/org/apache/lucene/expressions/js/CompilerTestCase.java
@@ -34,6 +34,7 @@ public abstract class CompilerTestCase extends LuceneTestCaseJupiter {
/** compiles expression for sourceText with custom functions list */
protected Expression compile(String sourceText, Map<String, MethodHandle> functions)
throws ParseException {
- return JavascriptCompiler.compile(sourceText, functions, true);
+ return JavascriptCompiler.compile(
+ sourceText, functions, JavascriptCompiler.DEFAULT_MAX_NESTING_DEPTH, true);
}
}
diff --git a/lucene/expressions/src/test/org/apache/lucene/expressions/js/TestJavascriptCompiler.java b/lucene/expressions/src/test/org/apache/lucene/expressions/js/TestJavascriptCompiler.java
index 94d180df5f9..e9e9a3d093f 100644
--- a/lucene/expressions/src/test/org/apache/lucene/expressions/js/TestJavascriptCompiler.java
+++ b/lucene/expressions/src/test/org/apache/lucene/expressions/js/TestJavascriptCompiler.java
@@ -17,6 +17,8 @@
package org.apache.lucene.expressions.js;
import java.text.ParseException;
+import java.util.stream.Collectors;
+import java.util.stream.IntStream;
import org.apache.lucene.expressions.Expression;
import org.junit.jupiter.api.Test;
@@ -269,4 +271,53 @@ public class TestJavascriptCompiler extends CompilerTestCase {
x = compile("foo['\\\\'][\"\\\\\"]");
assertEquals("foo['\\\\']['\\\\']", x.variables[0]);
}
+
+ @Test
+ public void testRecursionDepth1() throws Exception {
+ int depth = 20000;
+ String src = "(".repeat(depth) + "1" + ")".repeat(depth);
+ assertEquals(JavascriptCompiler.DEFAULT_MAX_NESTING_DEPTH, assertRecursionLimit(src));
+ }
+
+ @Test
+ public void testRecursionDepth1a() throws Exception {
+ int depth = JavascriptCompiler.DEFAULT_MAX_NESTING_DEPTH;
+ String src = "(".repeat(depth) + "1" + ")".repeat(depth);
+ assertEquals(JavascriptCompiler.DEFAULT_MAX_NESTING_DEPTH, assertRecursionLimit(src));
+ }
+
+ @Test
+ public void testRecursionDepth2() throws Exception {
+ String src = "-".repeat(20000) + "1";
+ assertEquals(JavascriptCompiler.DEFAULT_MAX_NESTING_DEPTH, assertRecursionLimit(src));
+ }
+
+ @Test
+ public void testRecursionDepth3() throws Exception {
+ String src =
+ IntStream.range(0, JavascriptCompiler.DEFAULT_MAX_NESTING_DEPTH + 1)
+ .mapToObj(Integer::toString)
+ .collect(Collectors.joining("+"));
+ assertEquals(
+ "error offset needs to be 0 due to recursion with depth first",
+ 0,
+ assertRecursionLimit(src));
+ }
+
+ @Test
+ public void testRecursionDepth3a() throws Exception {
+ String src =
+ IntStream.range(0, 20000).mapToObj(Integer::toString).collect(Collectors.joining("+"));
+ assertEquals(
+ "error offset needs to be 0 due to recursion with depth first",
+ 0,
+ assertRecursionLimit(src));
+ }
+
+ /** returns the error offset for further checks */
+ private int assertRecursionLimit(String src) {
+ ParseException expected = expectThrows(ParseException.class, () -> compile(src));
+ assertTrue(expected.getMessage(), expected.getMessage().contains("Nesting level too deep"));
+ return expected.getErrorOffset();
+ }
}