Runtime: Add HashSet.CreateSetComparer(comparer)

[JonHanna]

2nd API review iteration [TODO]

TODO - Fill the new API proposal here please, with summary of the troubles we have found during code review of the 1st API review iteration.

1st API review iteration [approved] - for context

Originally approved in https://github.com/dotnet/corefx/issues/14416#issuecomment-279797190

1. Addition of new Method

```C#
namespace System.Collections.Generic
{
public class HashSet
{
public static IEqualityComparer> CreateSetComparer(
IEqualityComparer comparer);
}
}

This method will return an `IEqualityComparer<HashSet<T>>` that uses the `IEqualityComparer<T>` passed to it in comparing elements to determine equality of hash-sets.

The comparer returned will consider two sets equal iff for each element in either there is an element in the other that `comparer` considers equal to it.

Optimised paths may only be taken if they give the same result as this.

If `comparer` is null, the method will treat this as if `EqualityComparer<T>.Default` had been passed to it.

The comparer will produce a hash code for sets as follows:

1. If the set is `null` the hash code is `0`.
2. Otherwise start with a seed value. For each value that `comparer` considers distinct, exclusive-or `comparer.GetHashCode(element)` with it. (The use of exclusive-or allows this algorithm to be agnostic to element order).

## 2. Obsolescence of Current `CreateSetComparer` Method
<s>
```C#
namespace System.Collections.Generic
{
    public class HashSet<T>
    {
        [System.Obsolete("This method can produce inconsistent results. Use CreatSetComparer(IEqualityComparer<T>")]
        public static IEqualityComparer<HashSet<T>> CreateSetComparer();
    }
}

The existing CreateSetComparer method has a minor design and major implementation issue. The design issue is that it lacks the ability to select the IEqualityComparer<T> to use. If this was the only problem it could work as an overload equivalent to CreateSetComparer(null) but it also has implementation flaws resulting in a non-commutative Equals() and disagreement between Equals() and GetHashCode(). However fixing it would break some cases that it can (in disagreement with how it is specified) serve to usefully determine set-equality of two sets in respect of their own comparers, if those comparers are the same. See dotnet/runtime#18931

Since it can't be fixed without considerable breaks, and both the specified behaviour and the other type of comparison it sometimes makes are offered by the new method (with a clear way of indicating which is wanted), this method should be obsoleted. (Fixing it to behave as specified could be considered after it has been obsolete for some time, as an alternative to deleting it).

[karelz]

The Obsolete attribute text will need better explanation IMO - ideally with link to docs that explain the problem (incl. examples).
@JonHanna can you please provide an example where today's method is wrong as 'Motivation'?

Nit: Why do you use {} instead of <> in the Obsolete attribute text?

[JonHanna]

Oh, I was thinking of the XML doc syntax, though what is the best form to use there, considering that <> isn't universal across .NET languages?

As a motivating example, consider:

``` C#
var set1 = new HashSet{"a", "b", "c", "d", "d", "f", "g", "h", "A"};
var set2 = new HashSet(StringComparer.OrdinalIgnoreCase){"a"};
Console.WriteLine(HashSet.CreateSetComparer().Equals(set1, set2)); // True!
Console.WriteLine(HashSet.CreateSetComparer().Equals(set2, set1)); // False

When `(x == y) != (y == x)` bad things happen.

But at the same time:

```C#
var set1 = new HashSet<string>(StringComparer.OrdinalIgnoreCase){"a"};
var set2 = new HashSet<string>(StringComparer.OrdinalIgnoreCase){"A"};
Console.WriteLine(HashSet<string>.CreateSetComparer().Equals(set1, set2)); // True

If a user is comparing sets which all use the same comparer, then the current method works perfectly well as a means of doing so (for Equals() anyway, not so much for the hash codes), but it is against the spec to do so. Fixing the current behaviour to work as specified would break such users.

[safern]

For this one we would definitely would want the new API addition but since IEqualityComparer<HashSet<T>> CreateSetComparer() has been out so long we wouldn't like to mark it as obsolete. So we are going to mark it as ready for review. Thanks @JonHanna

[terrajobst]

We should close on our obsoletion policy; there is no consensus yet. So except for the obsolete attribute, the API proposal looks good as proposed.

[JonHanna]

Okay, I've redacted that bit but left it visible (can be referenced in a new issue perhaps), and will proceed with the addition.

[karelz]

Thanks @safern @JonHanna! Once you have ready proposal update, please flip the issue to api-ready-for-review again.
Please keep the originally approved proposal in top issue as well for context during API review.

[EamonNerbonne]

A little late here, but wouldn't the only possible reasonable fix be for hashsets with differing comparers to return false?

The problem with the proposed approach is that the concept of containment in a hashset depends on the comparer of that hashset, and no later comparer can ever reconstruct the elements that were actually placed in the hashset because duplicates according to the hashset's comparer were ignored at insertion time.

For example if you have a set {"A", "a" } with ordinal comparison, and { "A", "a" } with OrdinalIgnoreCase, and you then compare the two sets with ordinal comparison, you'd think they were equal: but they're not, because the IgnoreCase set omits "a" during insertion.

Sure; you can specify that; but I can't imagine any situation where that behavior isn't so tricky as to be an enormous bug magnet. Consuming code trying to depend on that detail is in for a world of pain.

I don't know about how worried you are about backwards compat here, but the only comprehensible behavior is going to be simply returning false if the two sets have differing internal comparers. That's easy to understand and document, and it never produces a surprising result - and if people really want to compare the current enumerable contents with a new comparer, it's not hard to do explicitly.