Stackoverflow error

[devika5555]

Encountered stack overflow error for the below query and input combination.

query : ". | until(. >6; . - 1)"
input : "0"

Below is the code snippet where test is failing with stackoverflow error for the v 0.0.13.

@Test
public void longRunningQueryTest() throws IOException {
	final Scope rootScope = Scope.newEmptyScope();
	rootScope.loadFunctions(Thread.currentThread().getContextClassLoader());
	final Scope childScope = Scope.newChildScope(rootScope);
	final JsonQuery query = JsonQuery.compile(". | until(. >6; . - 1)");
	final JsonNode input = new ObjectMapper().readTree("0");
	final List<JsonNode> output = query.apply(childScope, input);
	assertFalse(output.isEmpty());
}

Below is the stack trace

Exception in thread "main" java.lang.StackOverflowError
at java.base/java.lang.Enum.hashCode(Enum.java:172)
at java.base/java.util.HashMap.hash(HashMap.java:340)
at java.base/java.util.HashMap.getNode(HashMap.java:570)
at java.base/java.util.HashMap.get(HashMap.java:558)
at net.thisptr.jackson.jq.internal.misc.JsonNodeComparator.orderValue(JsonNodeComparator.java:44)
at net.thisptr.jackson.jq.internal.misc.JsonNodeComparator.orderValue(JsonNodeComparator.java:40)
at net.thisptr.jackson.jq.internal.misc.JsonNodeComparator.compare(JsonNodeComparator.java:58)
at net.thisptr.jackson.jq.internal.operators.ComparisonOperator.apply(ComparisonOperator.java:22)
at net.thisptr.jackson.jq.internal.tree.binaryop.SimpleBinaryOperatorExpression.apply(SimpleBinaryOperatorExpression.java:26)
at net.thisptr.jackson.jq.internal.FixedScopeQuery.apply(FixedScopeQuery.java:22)
at net.thisptr.jackson.jq.internal.JsonQueryFunction.applyRecursive(JsonQueryFunction.java:42)
at net.thisptr.jackson.jq.internal.JsonQueryFunction.apply(JsonQueryFunction.java:36)
at net.thisptr.jackson.jq.internal.tree.FunctionCall.apply(FunctionCall.java:26)
at net.thisptr.jackson.jq.internal.tree.Conditional.applyRecursive(Conditional.java:25)
at net.thisptr.jackson.jq.internal.tree.Conditional.apply(Conditional.java:42)
at net.thisptr.jackson.jq.internal.JsonQueryFunction.applyRecursive(JsonQueryFunction.java:42)
at net.thisptr.jackson.jq.internal.JsonQueryFunction.apply(JsonQueryFunction.java:36)
at net.thisptr.jackson.jq.internal.tree.FunctionCall.apply(FunctionCall.java:26)
at net.thisptr.jackson.jq.internal.tree.PipedQuery.applyRecursive(PipedQuery.java:42)
at net.thisptr.jackson.jq.internal.tree.PipedQuery.applyRecursive(PipedQuery.java:55)
at net.thisptr.jackson.jq.internal.tree.PipedQuery.apply(PipedQuery.java:25)
at net.thisptr.jackson.jq.internal.tree.Conditional.applyRecursive(Conditional.java:33)
at net.thisptr.jackson.jq.internal.tree.Conditional.apply(Conditional.java:42)
at net.thisptr.jackson.jq.internal.JsonQueryFunction.applyRecursive(JsonQueryFunction.java:42)
at net.thisptr.jackson.jq.internal.JsonQueryFunction.apply(JsonQueryFunction.java:36)
at net.thisptr.jackson.jq.internal.tree.FunctionCall.apply(FunctionCall.java:26)
at net.thisptr.jackson.jq.internal.tree.PipedQuery.applyRecursive(PipedQuery.java:42)
at net.thisptr.jackson.jq.internal.tree.PipedQuery.applyRecursive(PipedQuery.java:55)
at net.thisptr.jackson.jq.internal.tree.PipedQuery.apply(PipedQuery.java:25)
at net.thisptr.jackson.jq.internal.tree.Conditional.applyRecursive(Conditional.java:33)
at net.thisptr.jackson.jq.internal.tree.Conditional.apply(Conditional.java:42)
at net.thisptr.jackson.jq.internal.JsonQueryFunction.applyRecursive(JsonQueryFunction.java:42)
at net.thisptr.jackson.jq.internal.JsonQueryFunction.apply(JsonQueryFunction.java:36)
at net.thisptr.jackson.jq.internal.tree.FunctionCall.apply(FunctionCall.java:26)
at net.thisptr.jackson.jq.internal.tree.PipedQuery.applyRecursive(PipedQuery.java:42)
at net.thisptr.jackson.jq.internal.tree.PipedQuery.applyRecursive(PipedQuery.java:55)
at net.thisptr.jackson.jq.internal.tree.PipedQuery.apply(PipedQuery.java:25)
at net.thisptr.jackson.jq.internal.tree.Conditional.applyRecursive(Conditional.java:33)
at net.thisptr.jackson.jq.internal.tree.Conditional.apply(Conditional.java:42)
at net.thisptr.jackson.jq.internal.JsonQueryFunction.applyRecursive(JsonQueryFunction.java:42)
at net.thisptr.jackson.jq.internal.JsonQueryFunction.apply(JsonQueryFunction.java:36)
at net.thisptr.jackson.jq.internal.tree.FunctionCall.apply(FunctionCall.java:26)
at net.thisptr.jackson.jq.internal.tree.PipedQuery.applyRecursive(PipedQuery.java:42)
at net.thisptr.jackson.jq.internal.tree.PipedQuery.applyRecursive(PipedQuery.java:55)
at net.thisptr.jackson.jq.internal.tree.PipedQuery.apply(PipedQuery.java:25)
at net.thisptr.jackson.jq.internal.tree.Conditional.applyRecursive(Conditional.java:33)
at net.thisptr.jackson.jq.internal.tree.Conditional.apply(Conditional.java:42)
at net.thisptr.jackson.jq.internal.JsonQueryFunction.applyRecursive(JsonQueryFunction.java:42)
at net.thisptr.jackson.jq.internal.JsonQueryFunction.apply(JsonQueryFunction.java:36)
at net.thisptr.jackson.jq.internal.tree.FunctionCall.apply(FunctionCall.java:26)
at net.thisptr.jackson.jq.internal.tree.PipedQuery.applyRecursive(PipedQuery.java:42)
at net.thisptr.jackson.jq.internal.tree.PipedQuery.applyRecursive(PipedQuery.java:55).......continued

[Jiehong]

Same result without the pipe: until(. >6; . - 1), or with a while: [while(.<100; .*2)].

[eiiches]

This is because until/2 and while/2 are both defined using recursion which never stops until/while the specified condition is met.

jackson-jq/jackson-jq/src/main/resources/net/thisptr/jackson/jq/jq.json

Lines 92 to 93 in c957014

	{"name": "until", "args": ["cond", "next"], "body": "def _until: if cond then . else (next|_until) end; _until"},
	{"name": "while", "args": ["cond", "update"], "body": "def _while: if cond then ., (update | _while) else empty end; _while"},

While the official jq implementation uses tail call optimization (TCO) to convert the recursion into a loop, jackson-jq does not and thus results in stack overflow instead of looping endlessly. I want to implement TCO in jackson-jq eventually, but even with TCO, your test case will never finish and eventually time out.

That said, I see bare StackOverflowError should not be thrown to users. Instead, it should be wrapped in JsonQueryException (or its subclass). I'll fix it later.