Exist: [BUG] Side effects when calling map functions

[PieterLamers]

Describe the bug

In some cases it is possible that the value of a variable bound to a map is mutated.

Expected behavior

In XQuery, variables are immutable. Once a variable is bound, its value cannot change within the scope of its FLWOR expression and binding sequence. See https://www.w3.org/TR/xquery-31/#id-binding-rules.

In the example below, the variable $three-entry-map is bound to a map containing three entries:

map {
    "a": 1,
    "b": 2,
    "c": 3
}

The query returns this variable—this 3-entry map—and it does so in BaseX and Saxon.

However, in eXist, the presence of a map-altering function like map:remove(), map:put(), or map:merge() in a subsequent let clause somehow mutates the $three-entry-map variable. As a result, in eXist, the example queries all returns the following map, with only 2 entries instead of the expected 3:

map {
    "a": 1,
    "c": 3
}

This violates immutability.

To Reproduce

The problem has been reduced to the following:

xquery version "3.1";

let $three-entry-map := 
    map:merge((
        map {
            "a" : 1,
            "b" : 2,
            "c" : 3
        }
    ))
let $some-other-map := map:remove($three-entry-map, "b")
return 
    $three-entry-map

In BaseX and Saxon, this returns the expected 3-entry map. In eXist, it returns a 2-entry map.

Similarly, the presence of map:put() will trigger the problem in eXist:

xquery version "3.1";

let $three-entry-map := 
    map:merge((
        map {
            "a" : 1,
            "b" : 2,
            "c" : 3
        }
    ))
let $some-other-map := map:put($three-entry-map, "b", "foo")
return 
    $three-entry-map

Lastly, map:merge() will trigger it too:

xquery version "3.1";

let $three-entry-map := 
    map:merge((
        map {
            "a" : 1,
            "b" : 2,
            "c" : 3
        }
    ))
let $some-other-map := 
    map:merge((
        $three-entry-map, 
        map { "b": "foo" }
    ))
return 
    $three-entry-map

In all 3 cases, in BaseX and Saxon, this returns the expected 3-entry map. In eXist, it returns a 2-entry map.

Even this case without a let clause reveals the problem - returning an empty map instead of a 1-entry map:

xquery version "3.1";

map:merge( map { "a" : 1 } ) ! (., map:put(., "a", 2))[1]

• OS: linux, windows, macOS
• eXist-db version: 5.3.0-SNAPSHOT 303ca0db511ee93bac1b50ccede357fde9658e7b
• Java Version 1.8.0_271

[joewiz]

As discussed in Slack: https://exist-db.slack.com/archives/CG2MRUZ35/p1612362478152200. From my assessment there:

Great find, Pieter. I know of many apps that make heavy use of map:merge(), such as eXist’s templating module and TEI Publisher, and this bug could really screw them up.

Even more concerning, this bug is new to 5.3.0-SNAPSHOT. It is not present in 4.7.1, 5.1.1, or 5.2.0.

[joewiz]

Update: I've edited the original post to add variants that show the problem affects all map-altering functions: map:remove, map:put, and map:merge. I also added a 1-liner demonstrating the problem.

[line-o]

I only see map:merge as the function returning mutable maps.

[line-o]

Here is proof:

xquery version "3.1";

let $original := map { 1 : true() }
let $merged := map:merge($original)

return 
    map {
        "original:put": [
            $original?1,
            map:put($original, 1, 2)?1,
            $original?1
        ],
        "merged:put": [
            $merged?1,
            map:put($merged, 1, 2)?1,
            $merged?1
        ]
    }
,
let $original := map { 1 : true() }
let $merged := map:merge($original)

return 
    map {
        "original:remove": [
            $original?1,
            map:remove($original, 1)?1,
            $original?1
        ],
        "merged:remove": [
            $merged?1,
            map:remove($merged, 1)?1,
            $merged?1
        ]
    }

[line-o]

on 5.3.0 the above will yield

(
map {
    "original:put": [true(),2,true()],
    "merged:put": [true(),2,()]
},
map {
    "original:remove": [true(),(),true()],
    "merged:remove": [true(),(),()]
}
)

[line-o]

I stand corrected map:remove also returns a mutable reference to the original map!

[line-o]

test code

xquery version "3.1";

let $original := map { 1 : true(), 2: true() }
let $merged := map:merge($original)
let $putted := map:put($original, 2, false())
let $removed := map:remove($original, 2)

return 
    map {
        "original:put": [$original?1, map:put($original, 1, 2)?1, $original?1],
        "merged:put": [$merged?1, map:put($merged, 1, 2)?1, $merged?1],
        "putted:put": [$putted?1, map:put($putted, 1, 2)?1, $putted?1],
        "removed:put": [$removed?1, map:put($removed, 1, 2)?1, $removed?1]
    }
,
let $original := map { 1 : true(), 2: true() }
let $merged := map:merge($original)
let $putted := map:put($original, 2, false())
let $removed := map:remove($original, 2)

return 
    map {
        "original:remove": [$original?1, map:remove($original, 1)?1, $original?1],
        "merged:remove": [$merged?1, map:remove($merged, 1)?1, $merged?1],
        "putted:remove": [$putted?1, map:remove($putted, 1)?1, $putted?1],
        "removed:remove": [$removed?1, map:remove($removed, 1)?1, $removed?1]
    }

Yields

(
map {
    "original:put": [true(),2,true()],
    "merged:put": [true(),2,()],
    "putted:put": [true(),2,true()],
    "removed:put": [true(),2,()]
}
,
map {
    "original:remove": [true(),(),true()],
    "merged:remove": [true(),(),()],
    "putted:remove": [true(),(),true()],
    "removed:remove": [true(),(),()]
}
)

[joewiz]

Using the current develop branch, I repeated the tests in the original post, and they now all return the expected results.

Since all of the problems described in the original post by @PieterLamers and me are now fixed and the steps to reproduce now can no longer be reproduced, this issue can now be closed. (Credit goes to https://github.com/eXist-db/exist/pull/3886.)

That's not to assert that "all issues with maps are fixed"—just that this issue as submitted is fixed.

Indeed, work on maps continues in https://github.com/eXist-db/exist/pull/3725 (not tagged with a milestone, but intended for 5.3.0 as I recall from a Community Call) and https://github.com/eXist-db/exist/pull/3738 (tagged for the 6.0.0 milestone). Let's continue discussion of those issues in their respective PRs, in follow-on issues, in Slack, Community Calls, etc.

[line-o]

Interesting! I wonder how both @adamretter and me came to a different conclusion?

[joewiz]

@line-o Let me expand on my statement:

Using the current develop branch, I repeated the tests in the original post, and they now all return the expected results.

Test 1

xquery version "3.1";

let $three-entry-map := 
    map:merge((
        map {
            "a" : 1,
            "b" : 2,
            "c" : 3
        }
    ))
let $some-other-map := map:remove($three-entry-map, "b")
return 
    $three-entry-map

Previously, eXist returned a 2-entry map as its result. Now it joins BaseX and Saxon in returning the expected 3-entry map:

map {
    "a": 1,
    "b": 2,
    "c": 3
}

Test 2

xquery version "3.1";

let $three-entry-map := 
    map:merge((
        map {
            "a" : 1,
            "b" : 2,
            "c" : 3
        }
    ))
let $some-other-map := map:put($three-entry-map, "b", "foo")
return 
    $three-entry-map

Previously, eXist returned a 2-entry map as its result. Now it joins BaseX and Saxon in returning the same 3-entry map as Test 1.

Test 3

xquery version "3.1";

let $three-entry-map := 
    map:merge((
        map {
            "a" : 1,
            "b" : 2,
            "c" : 3
        }
    ))
let $some-other-map := 
    map:merge((
        $three-entry-map, 
        map { "b": "foo" }
    ))
return 
    $three-entry-map

Previously, eXist returned a 2-entry map as its result. Now it joins BaseX and Saxon in returning the same 3-entry map as Test 1.

Test 4

xquery version "3.1";

map:merge( map { "a" : 1 } ) ! (., map:put(., "a", 2))[1]

Previously, eXist returned an empty map. Now it joins BaseX and Saxon in returning a 1-entry map.

This explains my statement that all of the tests in the description of this issue now pass. Again, that's not to assert that "all issues with maps are fixed"—just that this issue as explained and described via the supplied tests is fixed.

[line-o]

Still great news!

[adamretter]

I just want to check this through one last time before we close it...

[joewiz]

@adamretter As promised during the Community Call just now, I just repeated the steps as described in the original post and elaborated in https://github.com/eXist-db/exist/issues/3724#issuecomment-849843191 using the 5.3.0 release, and the tests all still return the expected results.

[adamretter]

@joewiz If all of the original tests from here pass, then that is good :-)

I had previously seen some failing tests still in https://github.com/eXist-db/exist/pull/3738 so I just revisited them. I found only 4 remaining failing tests, and after a close examination, the problems were in the tests themselves. I am now happy that the side-effects are indeed resolved by the bug-fix and upgrade to the latest Bifurcan version.

We can now close this, and decide what to do with https://github.com/eXist-db/exist/pull/3738 separately...

[joewiz]

@adamretter Excellent news! Thank you for checking this!