`SortedSet<T>.SortedSetEquals` is not correct when the sets have different comparers

[skyoxZ]

Description

When set1 and set2 have different comparers, current SortedSetEquals basically returns set1.IsSubsetOf(set2). https://github.com/dotnet/runtime/blob/f61ca08d93fe06599f4566d6faf6f9da4cf05484/src/libraries/System.Collections/src/System/Collections/Generic/SortedSet.cs#L811-L828

Reproduction Steps

using System;
using System.Collections.Generic;

SortedSet<string> a = new();
SortedSet<string> b = new(StringComparer.OrdinalIgnoreCase) { "1" };
var setComparer = SortedSet<string>.CreateSetComparer();
Console.WriteLine(setComparer.Equals(a, b));

Expected behavior

False

Actual behavior

True

Regression?

No response

Known Workarounds

No response

Configuration

No response

Other information

No response

[dotnet-policy-service[bot]]

Tagging subscribers to this area: @dotnet/area-system-collections See info in area-owners.md if you want to be subscribed.

[skyoxZ]

I'm not sure what should happen if set1.comparer, set2.comparer and setComparer.memberEqualityComparer are not all same. Do we support such situation?

https://learn.microsoft.com/dotnet/api/system.collections.generic.sortedset-1.createsetcomparer

[lilinus]

I'm not sure what should happen if set1.comparer, set2.comparer and setComparer.memberEqualityComparer are not all same. Do we support such situation?

Tricky. setComparer.memberEqualityComparer is a IEqualityComparer will never be equal to set1.comparer (which is IComparer). Documentation says they should have the same definition of equal, but it's not checked in the code nor is any behaviour documented if it doesn't hold.

[skyoxZ]

Similar issue exists in HashSet<T>:

using System;
using System.Collections.Generic;

HashSet<string> a = new();
HashSet<string> b = new(StringComparer.OrdinalIgnoreCase) { "1" };
var setComparer = HashSet<string>.CreateSetComparer();
Console.WriteLine(setComparer.Equals(b, a));

https://github.com/dotnet/runtime/blob/086ee6680a28eb2384a42ed350a536c32e07ad6d/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/HashSetEqualityComparer.cs#L35-L53

[eiriktsarpalis]

Related to #19644 and #69218. Comparing sets that encapsulate different notions of equality is inherently problematic and this shows up in the implementations that attempt to reconcile the problem. A few possible solutions have been discussed, but so far we have been hesitant to make any changes for fear of breaking code that depends subtly on the current behaviour.