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.

https://github.com/eiiches/jackson-jq/blob/c957014363743d46cee7a6143897c21197bca4cb/jackson-jq/src/main/resources/net/thisptr/jackson/jq/jq.json#L92-L93

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.