Maps test immutable

[laher]

Addresses issues raised by @BarrensZeppelin here https://github.com/benbjohnson/immutable/issues/36 and also https://github.com/benbjohnson/immutable/issues/32#issuecomment-1375981222

@BarrensZeppelin provided a fix here too: https://github.com/benbjohnson/immutable/pull/39 (but that creates a new Map for each item being added)

The general fix is to use mutable = false on first item, and then mutable = true for the rest.

• I fixed Map.SetMany() / SortedMap.SetMany() as above, (and added test cases which failed previously).
• For Sets/SortedSets, I made a variant of Map.SetMany - Map.setManySameValue() for convenience. Tests added here too. I also fixed Set.Delete and some docs as in #39.

[BarrensZeppelin]

Unfortunately I don't think this is sound either.

As far as I understand, calling set with mutable=false will only copy tree nodes on the path from the root to the leaf node where the key should be stored (maybe @benbjohnson can clarify). So if the later calls to set with mutable=true use keys that fall into different map leaves than the first key, you will end up modifying tree nodes that haven't been copied, which will affect previous versions of the map.

[BarrensZeppelin]

The implementation fails the following test, showing that SetMany affects previous versions of the tree:

diff --git a/immutable_test.go b/immutable_test.go
index e0f1857..cea14f9 100644
--- a/immutable_test.go
+++ b/immutable_test.go
@@ -1087,6 +1087,26 @@ func TestMap_SetMany(t *testing.T) {
            t.Fatalf("unexpected value for m: <%v,%v>", v, ok)
        }
    })
+
+   RunRandom(t, "Random", func(t *testing.T, rand *rand.Rand) {
+       history := []*TMap{NewTestMap()}
+
+       for i := 0; i < 10; i++ {
+           nm := history[len(history)-1].Copy()
+           entries := map[int]int{}
+           for j := 0; j < 5; j++ {
+               entries[nm.NewKey(rand)] = i
+           }
+           nm.SetMany(entries)
+           history = append(history, nm)
+       }
+
+       for i, m := range history {
+           if err := m.Validate(); err != nil {
+               t.Fatalf("History item %d is wrong: %v", i, err)
+           }
+       }
+   })
 }

 // Ensure map can support overwrites as it expands.
@@ -1353,6 +1373,21 @@ func (m *TMap) Set(k, v int) {
    m.std[k] = v
 }

+func (m *TMap) SetMany(entries map[int]int) {
+   m.prev = m.im
+   m.im = m.im.SetMany(entries)
+
+   for k, v := range entries {
+       m.builder.Set(k, v)
+
+       _, exists := m.std[k]
+       if !exists {
+           m.keys = append(m.keys, k)
+       }
+       m.std[k] = v
+   }
+}
+
 func (m *TMap) Delete(k int) {
    m.prev = m.im
    m.im = m.im.Delete(k)
@@ -1367,6 +1402,20 @@ func (m *TMap) Delete(k int) {
    }
 }

+func (m *TMap) Copy() *TMap {
+   nm := make(map[int]int, len(m.std))
+   nb := NewMapBuilder[int, int](nil)
+   for k, v := range m.std {
+       nb.Set(k, v)
+       nm[k] = v
+   }
+
+   return &TMap{
+       m.im, m.prev,
+       nb, nm, m.keys,
+   }
+}
+
 func (m *TMap) Validate() error {
    for _, k := range m.keys {
        if v, ok := m.im.Get(k); !ok {
@@ -2525,6 +2574,7 @@ func RunRandom(t *testing.T, name string, fn func(t *testing.T, rand *rand.Rand)
    }
    t.Run(name, func(t *testing.T) {
        for i := 0; i < *randomN; i++ {
+           i := i
            t.Run(fmt.Sprintf("%08d", i), func(t *testing.T) {
                t.Parallel()
                fn(t, rand.New(rand.NewSource(int64(i))))

[laher]

The implementation fails the following test, showing that SetMany affects previous versions of the tree:

Fair enough, I'll close this and approve yours this evening.