The Compare Contract [Kim Hamilton]

The Compare Contract [Kim Hamilton] : EasyCoded

The Compare Contract [Kim Hamilton] : EasyCoded — Mon, 06 Oct 2008 18:44:45 GMT

PingBack from http://www.easycoded.com/the-compare-contract-kim-hamilton/

Does this apply to System.Comparison?

Kalle Olavi Niemitalo — Tue, 07 Oct 2008 14:14:09 GMT

This requirement treat nulls as the smallest values is documented as applying to:

- System.IComparable.CompareTo

- System.IComparable<T>.CompareTo

- System.Collections.IComparer.Compare

- System.Collections.Generic.IComparer<T>.Compare

But does it apply to the System.Comparison<T> delegate? The documentation does not say.

re: The Compare Contract [Kim Hamilton]

Simone Busoli — Wed, 08 Oct 2008 02:13:24 GMT

Of course it doesn't Kalle, since it accepts two arguments and you can perform any sorting you like there.

re: The Compare Contract [Kim Hamilton]

Kalle Olavi Niemitalo — Wed, 08 Oct 2008 09:47:23 GMT

IComparer.Compare and IComparer<T>.Compare accept two arguments too, yet they have the same requirement. I can understand that nulls must be treated specially in IComparable and IComparable<T>, because it is not possible to call ((IComparable)a).Compare(b) when a is null. In IComparer and IComparer<T> however, either parameter could easily be null. I don't see any reason to require IComparer and IComparer<T> to sort nulls first, but the documentation requires that anyway. And it seems quite odd to me if Comparison<T> and IComparer<T>.Compare have different requirements.

re: The Compare Contract [Kim Hamilton]

Simone Busoli — Wed, 08 Oct 2008 10:33:26 GMT

Yes, that's what I mean. Since the CompareTo is an instance method it won't be called on nulls.

IComparer<T> and Comparison<T>, be it odd or not, behave differently. Try it yourself:

using System;

using System.Collections.Generic;

public class StringWrapper : IComparable<StringWrapper>

{

public string Value { get; set; }

public StringWrapper(string value)

{

Value = value;

}

public int CompareTo(StringWrapper other)

{

if(other == null)

return -1;

return Value.CompareTo(other.Value);

}

public class MyComparer : IComparer<StringWrapper>

{

public int Compare(StringWrapper first, StringWrapper second)

{

if(first == null)

return 1;

if(second == null)

return -1;

return first.Value.CompareTo(second.Value);

}

public class MyClass

{

public static void Main()

{

StringWrapper a = new StringWrapper("a");

StringWrapper b = new StringWrapper("b");

StringWrapper c = new StringWrapper("c");

StringWrapper d = null;

StringWrapper e = new StringWrapper("e");

StringWrapper f = null;

var array1 = new[] {e, c, f, b, d, a};

var array2 = new[] {e, c, f, b, d, a};

var array3 = new[] {e, c, f, b, d, a};

Array.Sort(array1);

foreach(var el in array1)

WL(el != null ? el.Value : "null");

WL("");

Array.Sort(array2, new MyComparer());

foreach(var el in array2)

WL(el != null ? el.Value : "null");

WL("");

Array.Sort(array3, new MyComparer().Compare);

foreach(var el in array3)

WL(el != null ? el.Value : "null");

}

private static void WL(string text)

{

Console.WriteLine(text);

}

re: The Compare Contract [Kim Hamilton]

daniel_lidstrom — Wed, 08 Oct 2008 14:52:19 GMT

Hi Kim, it was enjoyable to get some insights into the BCL. I've been looking through some of the xml classes and I would love to know more about their internal design. I realize this is not the right place to ask, but do you know a better place?

For example, I'd like to know why XmlTextReader has an internal class called XmlTextReaderImpl.

Thanks in advance!

Regards,

Daniel Lidström,

Stockholm, Sweden

re: The Compare Contract [Kim Hamilton]

Kim Hamilton — Thu, 09 Oct 2008 22:32:25 GMT

Hi Kalle and Simone,

Sorry for the delay. It's correct that, with IComparables, nulls may be special cased to avoid calling CompareTo on null.

If you specify a comparer other than the default comparer, then that comparer will be used.

Simone - are you saying when you run that repro you get different results for IComparer<T> and Comparison<T>? I get the same output, i.e.:

a, b, c, e, null, null

Let me know if you're seeing different behavior.

To get back to the original question: I'm not sure why our docs say this requirement for IComparer and IComparer<T>, because no special cases are being made. My guess is it's either a doc error or based on an earlier assumption that IComparers should always do this. I'll look into this and reply.

Thanks,

Kim

re: The Compare Contract [Kim Hamilton]

Simone Busoli — Sat, 11 Oct 2008 01:11:46 GMT

@Kim

no I'm not saying that IComparer and Comparison have different behavior, quite the opposite. I mean that they have different behavior compared to IComparable, that is, they can sort nulls correctly.

The docs of IComparer<T>.Compare method say:

A null reference is considered to be less than any reference that is not null.

To me, this doesn't mean anything. I am doing the custom sorting, so who is considering null references less than non null references?

re: The Compare Contract [Kim Hamilton]

slorion — Mon, 13 Oct 2008 01:17:34 GMT

Let's say we want to sort a List<T> and put null values at the end, how can we achieve that goal then ? Seems to me that you impose a non obvious semantic contract for the sake of performance only.

IComparable, IEquatable and others similar interfaces are broken anyway as their behavior on null is undefined. IMO a functional approach would have been much better (ie Comparison<T> or even IComparer<T>).

Why have so many different ways (IEquatable<T>, IEqualityComparer<T>, static and virtual Objects.Equals, Comparison<T> ....) to do something as basic as comparing ? It just makes things complicated, inconsistent and cumbersome. It is particularly annoying when one library cannot "talk" to another because one did not do it the same way as the other.

re: The Compare Contract [Kim Hamilton]

kimhamil — Tue, 21 Oct 2008 09:27:05 GMT

I did some detective work and have a recommendation about the Comparison<T> delegate discrepancy. But to make sure we’re all on the same page, I’ll start with a more thorough description of the problem.

The docs for IComparable.Compare (generic and nongeneric; signatures below) say null should always compare least; i.e. null is less than any non-null reference. As discussed above, that’s reasonable in this case, since CompareTo is an instance method and one may be null.

IComparable.CompareTo(Object obj)

IComparable<T>.CompareTo(T other)

The docs for IComparer.Compare (generic and non-) also say null should compare least

IComparer.Compare(Object x, Object y)

IComparer<T>.Compare(T x, T y)

Interestingly, the Comparison<T> delegate takes 2 args (like IComparer<T>.Compare), but it doesn’t specify that null should always compare least.

delegate int Comparison<T>(T x, T y);

So why does IComparer<T>.Compare say null should compare least but Comparison<T> has no such requirement?

Unfortunately the history is missing, but the most likely explanation seems to be rooted in the Remarks section for IComparer.Compare (note, non-generic). This says the preferred implementation is to use CompareTo method (from the IComparable interface) of one of the parameters. If this is the case, it makes sense that it would expect parity with IComparable and null should compare least.

IComparer<T>.Compare (the generic version of above) get trickier. It doesn’t mention that the preferred implementation is to use CompareTo, but it does say null should always compare least.

As discussed in the comments above, special casing null is a reasonable restriction if the compare method is an instance method on the comparands, one of which may be null. However, this isn’t the case for IComparer, IComparer<T>, and Comparison<T> .

I think the “preferred implementation” guidance is the only reason IComparer.Compare requires that null compare least. Furthermore, the “preferred implementation” guidance is questionable because it overlooks a key selling point of IComparer – the ability to provide a custom comparison. It’s good that the preferred implementation guidance didn’t carry over to IComparer<T>.Compare. Unfortunately, the requirement to special-case null for IComparer<T>.Compare is inconsistent from this perspective. However, this guidance has been there for a while and possibly the best thing we can do for now is leave this as is.

Lastly, the IComparison<T> delegate currently has neither restriction. I think we should leave it as is instead of letting legacy restrictions creep around. Why not give the flexibility? Any comments?

re: The Compare Contract [Kim Hamilton]

Kalle Olavi Niemitalo — Tue, 21 Oct 2008 13:57:25 GMT

Certainly the documentation of IComparer.Compare and IComparer<T>.Compare should be clearer on whether nulls first is only a recommendation or a requirement. I think a reasonable compromise would be:

- At IComparer.Compare and IComparer<T>.Compare, say that these methods were originally intended to treat nulls as the smallest values, and that some callers may require this but the Sort methods included in the .NET Framework do not.

- At each Sort method that takes an IComparer or IComparer<T> parameter, say whether or not that Sort method expects the comparer to sort nulls first.

That would leave the interface specification vague but it's better to be vague explicitly than implicitly.

re: The Compare Contract [Kim Hamilton]

kimhamil — Tue, 21 Oct 2008 20:58:23 GMT

Definitely agree that doc clarification is needed -- I'll follow up on this.

In fact, I like the phrasing of your first bullet. That will reduce confusion for readers who've been through former iterations of guidance.

Also, perhaps I should rename this post to the CompareTo contract, to avoid further confusion. :)

re: The Compare Contract [Kim Hamilton]

kimhamil — Tue, 21 Oct 2008 21:06:50 GMT

Hi Daniel,

Sorry for the delay. Have you tried http://blogs.msdn.com/xmlteam/?

Thanks,

Kim