ContiguousSet<T>.Remove and InsertionOrderSet<T>.Remove leave the item in storage when the set has a custom comparer, corrupting the set

[matt-edmondson]

What's wrong

Both sets keep a HashSet<T> (uniquenessSet) built with the caller's IEqualityComparer<T>, next to an ordered backing store. Remove uses the comparer for the hash set but searches the backing store with default equality:

• Containers/ContiguousSet.cs, Remove: int index = Array.IndexOf(items, item, 0, Count);
• Containers/InsertionOrderSet.cs, Remove: items.Remove(item); (List<T>.Remove, default equality)

When the argument is equal under the comparer but not under Equals, the hash-set entry is removed and the backing-store entry is not. The two structures then disagree.

Reproduction (confirmed with a temporary MSTest against current main)

ContiguousSet<string> set = new(StringComparer.OrdinalIgnoreCase) { "Apple" };
bool removed = set.Remove("APPLE");
// removed == true, Count == 1, Contains("apple") == false, enumeration yields ["Apple"]
set.Add("apple");
// Count == 2, enumeration yields ["Apple", "apple"]: a duplicate in a set

InsertionOrderSet<string> gives exactly the same output.

Why it matters

A case-insensitive set of names, paths or tags is the main reason to pass a comparer. On such a set, one Remove with different casing breaks the set:

• Remove reports success, but the item still enumerates.
• Count stays the same.
• Contains says the item is absent.
• A later Add stores a second copy, which breaks the set's uniqueness invariant.

Suggested fix

Find the index with the set's own comparer rather than default equality:

// ContiguousSet
IEqualityComparer<T> cmp = uniquenessSet.Comparer;
int index = -1;
for (int i = 0; i < Count; i++) { if (cmp.Equals(items[i], item)) { index = i; break; } }

// InsertionOrderSet
int index = items.FindIndex(x => uniquenessSet.Comparer.Equals(x, item));
items.RemoveAt(index);

(#51 fixed the same kind of comparer bypass in OrderedSet<T>.)

Acceptance criteria

• With StringComparer.OrdinalIgnoreCase, Remove("APPLE") on a set holding "Apple" leaves Count == 0 and nothing to enumerate, for both types.
• A following Add("apple") gives exactly one element.
• Regression tests cover both types.