Runtime: Immutable hash-based collections do not accept `null` values

[bradphelan]

I have spent two days chasing down an evil bug. I narrowed down the problem with this test case demonstrating different behavior for different collection classes that implement the same interface. Specifically Contains(null) throws a ArgumentNullException for ImmutableSortedSet but not for Array or the mutable SortedSet.

```c#
using System.Collections.Generic;
using System.Collections.Immutable;
using Xunit;

public class SortedSetSpec
{
    [Fact]
    public void WTFNullCheck()
    {
        var data = new[] {"a", "b", "c", "d"};

        SortedSet<string> ss = new SortedSet<string>(data);
        ImmutableSortedSet<string> iss = ss.ToImmutableSortedSet();

        // This passes
        data.Contains(null).Should().BeFalse();

        // This passes
        ss.Contains(null).Should().BeFalse();

        // This throws an exception
        iss.Contains(null).Should().BeFalse();
    }
}

Given that all classes Array / SortedSet and ImmutableSortedSet implement ``ICollection<T>`` shouldn't they have the same behavior on the ``Contains(null)`` call?

The bug manifested itself when I data bound an ``ImmutableSortedSet`` to the ``ItemsSource`` property of a listbox. 

```xml
     <ListBox x:Name="ListBox" Margin="2" 
              ItemsSource="{Binding WorkflowTags}" 
              SelectedItem="{Binding SelectedTag}" >
     </ListBox>

The problem is that at some point deep in the databinding code ListBox (aka Selector ) asks the collection Contains(null)?? and then it crashes if I've databound an ImmutableSortedSet.

So is this a bug with ImmutableCollections or with WPF or is it expected behavior and I should know better than to use ImmutableSortedSet?

[EDIT] Add syntax highlighting by @karelz

[ianhays]

How do the other ImmutableCollections act in this case? Do they also throw on Contains(null) or do they return false like their mutable counterparts?

cc @AArnott

[AArnott]

I see ImmutableHashSet<T>.Contains(T) also throws ArgumentNullException when its argument is null.
As does the Add method, and IndexOf, and probably any other method that accepts T.
These are hash-based collections and no hash can be taken of a null value.

It does look like the mutable collections special case null in order to avoid throwing this exception. They assume a hash code of 0. Amazingly enough, even null is evidently a valid value in a HashSet<T> to be added.

I don't see any reason why the immutable collections couldn't also support null values. I don't think backward compatibility would be an issue here because we're allowing something we didn't allow before and folks were hopefully not catching ArgumentNullException to do something interesting before.

[JonHanna]

Strictly if going through an IComparer<T> or IEqualityComparer<T> there should be no need to special-case null at all, but it's worth doing to guard against buggy implementations.

HashSet<T> accepting null is a feature shared with SortedSet<T>. Meanwhile Dictionary, SortedDictionary and Hashtable all throw, which may have some philosophical points in its favour, but can be a nuisance at times.

[jamesqo]

@JonHanna

but it's worth doing to guard against buggy implementations.

Is it really considered buggy to throw for null in comparers? I noticed a while ago that all of the StringComparers throw for null, e.g. https://github.com/dotnet/coreclr/blob/master/src/mscorlib/src/System/StringComparer.cs#L336 I always thought that EqualityComparer<T>'s behavior of accepting null values was something specific to that class.

[AArnott]

I consider IEqualityComparer<T>.Equals(T,T) should definitely accept nulls. And that GetHashCode(T) should throw ArgumentNullException for them. I'm pretty sure on Equals -- and I'm going from vague memory and guy on GetHashCode.

[JonHanna]

I just checked the docs, and yes, I was misremembering. Throwing is the documented behaviour.

[bradphelan]

As @JonHanna mentions the doc for IEqualityComparer.GetHashCode says that

but against that advice, EqualityComparer<T>.Default for reference types returns an ObjectEqualityComparer and has a GetHashCode implementation

  [Serializable]
  internal class ObjectEqualityComparer<T> : EqualityComparer<T>
  {

    public override int GetHashCode(T obj)
    {
      if ((object) obj == null)
        return 0;
      return obj.GetHashCode();
    }

 }

which explicitly returns 0 for GetHashCode.

[bradphelan]

But maybe this is a bug with the WPF code. The offending code that alerted me to this problem is in System.Windows.Controls.Primitives.Selector.cs . The SelectedValuePath is empty and the argument to FindItemWithValue is null because SelectedIndex=-1 and thus SelectedValue=null. It crashes at the line

index = this.Items.IndexOf(value);

within

    private object FindItemWithValue(object value, out int index)
    {
      index = -1;
      if (!this.HasItems)
        return DependencyProperty.UnsetValue;
      BindingExpression bindingExpression = this.PrepareItemValueBinding(this.Items.GetRepresentativeItem());
      if (bindingExpression == null)
        return DependencyProperty.UnsetValue;
      if (string.IsNullOrEmpty(this.SelectedValuePath))
      {
        if (!string.IsNullOrEmpty(bindingExpression.ParentBinding.Path.Path))
          return SystemXmlHelper.FindXmlNodeWithInnerText((IEnumerable) this.Items, value, out index);
        index = this.Items.IndexOf(value);
        if (index >= 0)
          return value;
        return DependencyProperty.UnsetValue;
      }
      Type knownType = value != null ? value.GetType() : (Type) null;
      DynamicValueConverter converter = new DynamicValueConverter(false);
      index = 0;
      foreach (object obj in (IEnumerable) this.Items)
      {
        bindingExpression.Activate(obj);
        object itemValue = bindingExpression.Value;
        if (this.VerifyEqual(value, knownType, itemValue, converter))
        {
          bindingExpression.Deactivate();
          return obj;
        }
        ++index;
      }
      bindingExpression.Deactivate();
      index = -1;
      return DependencyProperty.UnsetValue;
    }

because that eventually gets down to ImmutableSortedSet<string>.IndexOf and the problem we are talking about.

Stack dump for anybody who is interested https://gist.github.com/bradphelan/131890e7c57c54cc01666a2b85384383

[safern]

@bradphelan did you find the source of the error? it seems that it is a little bit unclear yet.

[bradphelan]

No. I just stopped using Immutable collections with WPF as it seems they
are incompatible.

On Wed, 8 Feb 2017, 20:38 Santiago Fernandez Madero <
[email protected]> wrote:

@bradphelan https://github.com/bradphelan did you find the source of
the error? it seems that it is a little bit unclear yet.

—
You are receiving this because you were mentioned.

Reply to this email directly, view it on GitHub
https://github.com/dotnet/corefx/issues/15403#issuecomment-278437848,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AABE8jpAj3k-nSXJa_YYY8RREPlvzOZWks5rahmtgaJpZM4LrOft
.

[safern]

Thanks for the update @bradphelan. So then we are going to close it until further notice.

[bradphelan]

Why close it? It's obviously a bug in the immutable collections API.
Liskov substition principle and all that. I should be able to swap any
collection and it will have the same behaviour. What else can I do except
report it. That I have a work around is not acknowledgment that there is no
problem.

On Wed, 8 Feb 2017, 20:54 Santiago Fernandez Madero <
[email protected]> wrote:

Closed dotnet/corefx#15403 https://github.com/dotnet/corefx/issues/15403.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/dotnet/corefx/issues/15403#event-954458563, or mute
the thread
https://github.com/notifications/unsubscribe-auth/AABE8ryOGV4Nq4g7k6DT1_E8VbYxhRQuks5rah1igaJpZM4LrOft
.

[madelson]

This problem goes beyond just accepting or rejecting nulls: the current behavior allows nulls in some situations and not in others for the same collection type:

(Copied from https://github.com/dotnet/corefx/issues/16948)

It is possible to create an ImmutableHashSet<T> containing a null value using ImmutableHashSet.CreateRange<T> and Union. However, other methods of doing so (Add, Create<T>(T)) result in ArgumentNullException:

var set = ImmutableHashSet<string>.Empty;
set = set.Add(null); // throws
set = set.Union(ImmutableHashSet.CreateRange(new string[] { null })); // adds null

Similarly, trying to remove a null with Remove throws but the null can be removed using Except.

In my opinion, allowing or rejecting nulls should be left entirely to the IEqualityComparer<T>. Since the default equality comparers support null, blocking null just forces special-casing of null in a number of scenarios where adding null to a collection would be useful. The current inconsistency is surprising as a user and clearly sub-optimal. Removing the ability to work with nulls from all methods would clearly be a breaking change, while as others have mentioned simply allowing null in Add, Remove, and Contains would not be breaking.

[karelz]

Thanks for your contribution @madelson! I sent you collaborator invite, once you accept, please ping me here and I will be able to assign the issue to you (GitHub limitation).

Note that we have new contributor docs (under construction): https://github.com/dotnet/corefx/wiki/New-contributor-Docs#contributing-guide ... feel free to improve them, the wiki is RW for everyone. There is also gitter chat room for new contributor docs if you have any questions.
If you hit roadblocks, or have questions, please don't hesitate to ask - @safern @ianhays will be happy to help. Thanks and welcome on board!

[madelson]

@karelz Thanks! I have accepted the invite.