[BUG] NPE with tail-recursive function that calculates Fibonacci numbers

[joewiz]

Describe the bug

A tail-recursive function that calculates Fibonacci numbers produces an NPE.

Expected behavior

The function, which works fine in BaseX and Saxon, should also work in eXist and not raise an error.

To Reproduce

The following query assumes the Fibonacci sequence starts with 1 and asks for the 3rd number in the sequence. The query should return 2, but instead it triggers an NPE:

xquery version "3.1";

declare namespace map="http://www.w3.org/2005/xpath-functions/map";

declare function local:fibC($n as xs:integer, $memo as map(*), $con as function(*)) as xs:integer {
  if (map:contains($memo, $n)) 
  then $con(map:get($memo, $n), $memo)
  else
    local:fibC(
      $n - 1, 
      $memo,
      (: $n1 = fib($n - 1) :)
      function($n1 as xs:integer, $memo as map(*)) as xs:integer { 
        local:fibC(
          $n - 2, 
          $memo, 
          (: $n2 = fib($n - 2) :)
          function($n2 as xs:integer, $memo as map(*)) as xs:integer {
            $con($n1 + $n2, map:put($memo, $n, $n1 + $n2)) 
          }
        )
      } 
    )
};

declare function local:fib($n as xs:integer) {
  let $memo := map { 1: 1, 2: 1 }
  let $con := function($x as xs:integer, $memo as map(*)) { $x }
  return
    local:fibC($n, $memo, $con)
};

let $n := 3
return
  local:fib($n)

Excerpt from exist.log:

2022-06-29 17:08:51,732 [qtp1438589510-70] ERROR (XQueryServlet.java [process]:549) - null 
java.lang.NullPointerException: null
	at org.exist.xquery.AnalyzeContextInfo.<init>(AnalyzeContextInfo.java:69) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.DynamicFunctionCall.eval(DynamicFunctionCall.java:94) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.UserDefinedFunction.eval(UserDefinedFunction.java:161) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.DynamicCardinalityCheck.eval(DynamicCardinalityCheck.java:73) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.UntypedValueCheck.eval(UntypedValueCheck.java:81) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.FunctionCall$DeferredFunctionCallImpl.execute(FunctionCall.java:421) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.DeferredFunctionCall.realize(DeferredFunctionCall.java:57) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.DeferredFunctionCall.isEmpty(DeferredFunctionCall.java:200) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.DynamicCardinalityCheck.eval(DynamicCardinalityCheck.java:75) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.UntypedValueCheck.eval(UntypedValueCheck.java:81) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.FunctionCall$DeferredFunctionCallImpl.execute(FunctionCall.java:421) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.DeferredFunctionCall.realize(DeferredFunctionCall.java:57) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.DeferredFunctionCall.isEmpty(DeferredFunctionCall.java:200) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.DynamicCardinalityCheck.eval(DynamicCardinalityCheck.java:75) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.UntypedValueCheck.eval(UntypedValueCheck.java:81) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.FunctionCall.evalFunction(FunctionCall.java:289) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.FunctionCall.eval(FunctionCall.java:207) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.AbstractExpression.eval(AbstractExpression.java:71) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.value.FunctionReference.eval(FunctionReference.java:86) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.DynamicFunctionCall.eval(DynamicFunctionCall.java:97) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.ConditionalExpression.eval(ConditionalExpression.java:98) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.UserDefinedFunction.eval(UserDefinedFunction.java:161) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.DynamicCardinalityCheck.eval(DynamicCardinalityCheck.java:73) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.UntypedValueCheck.eval(UntypedValueCheck.java:81) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.FunctionCall$DeferredFunctionCallImpl.execute(FunctionCall.java:421) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.DeferredFunctionCall.realize(DeferredFunctionCall.java:57) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.DeferredFunctionCall.isEmpty(DeferredFunctionCall.java:200) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.DynamicCardinalityCheck.eval(DynamicCardinalityCheck.java:75) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.UntypedValueCheck.eval(UntypedValueCheck.java:81) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.FunctionCall.evalFunction(FunctionCall.java:289) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.FunctionCall.eval(FunctionCall.java:207) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.DebuggableExpression.eval(DebuggableExpression.java:58) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.LetExpr.eval(LetExpr.java:110) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.LetExpr.eval(LetExpr.java:110) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.UserDefinedFunction.eval(UserDefinedFunction.java:161) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.FunctionCall.evalFunction(FunctionCall.java:289) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.FunctionCall.eval(FunctionCall.java:207) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.DebuggableExpression.eval(DebuggableExpression.java:58) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.LetExpr.eval(LetExpr.java:110) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.AbstractExpression.eval(AbstractExpression.java:71) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.PathExpr.eval(PathExpr.java:279) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.AbstractExpression.eval(AbstractExpression.java:71) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]
	at org.exist.xquery.XQuery.execute(XQuery.java:441) ~[exist-core-6.1.0-SNAPSHOT.jar:6.1.0-SNAPSHOT]

Furthermore, after running the query 3 times, subsequent runs start to produce these truncated entries in exist.log:

2022-06-29 17:08:58,423 [qtp1438589510-74] ERROR (XQueryServlet.java [process]:549) - null 
java.lang.NullPointerException: null

When these truncated entries appear, that's all you see - there is no more associated stack trace info in the logs.

The test query was adapted from @CliffordAnderson's https://github.com/NashFP/fib/blob/main/andersoncliffb%2Bxquery/fib.xqy. See his original report at https://twitter.com/andersoncliffb/status/1542152581786615811:

Can someone help me to understand why this code runs on #BaseX but not #eXistDB?

Screenshots

n/a

Context (please always complete the following information):

• OS: macOS 12.4
• eXist-db version: eXist 6.1.0-SNAPSHOT 65d3d5e6968ae8e281cc9926604b055254022529 20220512042037
• Java Version:

  openjdk version "1.8.0_332" OpenJDK Runtime Environment (Temurin)(build 1.8.0_332-b09) OpenJDK 64-Bit Server VM (Temurin)(build 25.332-b09, mixed mode)

Additional context

• How is eXist-db installed? built from source
• Any custom changes in e.g. conf.xml? none

[joewiz]

This is similar to these other recent reports of NPEs that point to AnalyzeContextInfo:

• https://github.com/eXist-db/exist/issues/2385
• https://github.com/eXist-db/exist/issues/1881#issuecomment-392162211
• https://github.com/eXist-db/exist/pull/1520#issuecomment-604467000