TMap.remove and removeAll incorrectly clear entire bucket on hash collision

[loveqoo]

Hi — I think I found a bug in TMap.remove and TMap.removeAll.
Filing per the contributing guide; happy to open a PR if helpful.

Summary

When two or more keys hash to the same bucket, calling TMap.remove(key) clears the entire bucket while only decrementing tSize by 1.

The remaining keys become unreachable via TMap.get even though TMap.size reports them as present.

Reproducer

Effect 3.21.2 (current latest on npm).

Forces a hash collision via a custom Hash so the bug is deterministic regardless of environment.

import { Effect, Equal, Hash, Option, STM, TMap } from "effect"

class Key implements Equal.Equal {
  constructor(readonly id: string) {}
  [Hash.symbol](): number {
    return 1 // all keys collide into the same bucket
  }
  [Equal.symbol](that: unknown): boolean {
    return that instanceof Key && that.id === this.id
  }
}

const program = Effect.gen(function* () {
  const m = yield* STM.commit(TMap.empty<Key, number>())
  yield* STM.commit(TMap.set(m, new Key("a"), 1))
  yield* STM.commit(TMap.set(m, new Key("b"), 2))
  yield* STM.commit(TMap.set(m, new Key("c"), 3))

  yield* STM.commit(TMap.remove(m, new Key("b")))

  const size = yield* STM.commit(TMap.size(m))
  const a = yield* STM.commit(TMap.get(m, new Key("a")))
  const b = yield* STM.commit(TMap.get(m, new Key("b")))
  const c = yield* STM.commit(TMap.get(m, new Key("c")))

  console.log({
    size,
    a: Option.isSome(a),
    b: Option.isSome(b),
    c: Option.isSome(c)
  })
})

Effect.runPromise(program)

Expected: { size: 2, a: true,  b: false, c: true  }
Observed: { size: 2, a: false, b: false, c: false }

With keys whose hashes happen to land in different buckets the bug does not surface, which is why it is easy to miss.

Current code

packages/effect/src/internal/stm/tMap.ts (current main):

// remove
const [toRemove, toRetain] = Chunk.partition(bucket, 
  (entry) => Equal.equals(entry[1], key))
if (Chunk.isNonEmpty(toRemove)) {
  const currentSize = tRef.unsafeGet(self.tSize, journal)
  tRef.unsafeSet(buckets.chunk[index], toRetain, journal)
  tRef.unsafeSet(self.tSize, currentSize - 1, journal)
}

// removeAll
const [toRemove, toRetain] = Chunk.partition(bucket, 
  (entry) => Equal.equals(next.value)(entry[0]))
if (Chunk.isNonEmpty(toRemove)) {
  const currentSize = tRef.unsafeGet(self.tSize, journal)
  tRef.unsafeSet(buckets.chunk[index], toRetain, journal)
  tRef.unsafeSet(self.tSize, currentSize - 1, journal)
}

Chunk.partition returns [excluded, satisfying] (predicate=false first, predicate=true second). The destructuring [toRemove, toRetain] is reversed relative to that contract, so toRetain actually holds the entries that should be deleted, and the bucket gets replaced with that subset. In remove the predicate also compares entry[1] (the value) instead of entry[0] (the key), which makes it nearly always false and therefore clears the bucket entirely.

For comparison, set uses the expected shape:

const shouldUpdate = Chunk.some(bucket, (entry) => Equal.equals(key)(entry[0]))

Suggested fix

// remove
const [toRetain, toRemove] = Chunk.partition(bucket, 
  (entry) => Equal.equals(entry[0], key))
if (Chunk.isNonEmpty(toRemove)) {
  const currentSize = tRef.unsafeGet(self.tSize, journal)
  tRef.unsafeSet(buckets.chunk[index], toRetain, journal)
  tRef.unsafeSet(self.tSize, currentSize - 1, journal)
}

// removeAll
const [toRetain, toRemove] = Chunk.partition(bucket, 
  (entry) => Equal.equals(next.value)(entry[0]))
if (Chunk.isNonEmpty(toRemove)) {
  const currentSize = tRef.unsafeGet(self.tSize, journal)
  tRef.unsafeSet(buckets.chunk[index], toRetain, journal)
  tRef.unsafeSet(self.tSize, currentSize - 1, journal)
}

A regression test that intentionally collides two keys in the same bucket would also be useful.

Thanks for Effect.

[mvanhorn]

Implemented in #6233 - the destructuring of Chunk.partition was reversed and the predicate compared the value field instead of the key field, so removing one key with a hash collision dropped every other entry in the same bucket. Fix is 2 lines + regression tests.