The case of the mysterious comparison by Mark Seemann
A ploeh mystery.
I was recently playing around with the example code from my book Code That Fits in Your Head, refactoring the Table class to use a predicative NaturalNumber wrapper to represent a table's seating capacity.
Originally, the Table constructor and corresponding read-only data looked like this:
private readonly bool isStandard; private readonly Reservation[] reservations; public int Capacity { get; } private Table(bool isStandard, int capacity, params Reservation[] reservations) { this.isStandard = isStandard; Capacity = capacity; this.reservations = reservations; }
Since I wanted to show an example of how wrapper types can help make preconditions explicit, I changed it to this:
private readonly bool isStandard; private readonly Reservation[] reservations; public NaturalNumber Capacity { get; } private Table(bool isStandard, NaturalNumber capacity, params Reservation[] reservations) { this.isStandard = isStandard; Capacity = capacity; this.reservations = reservations; }
The only thing I changed was the type of Capacity and capacity.
As I did that, two tests failed.
Evidence #
Both tests failed in the same way, so I only show one of the failures:
Ploeh.Samples.Restaurants.RestApi.Tests.MaitreDScheduleTests.Schedule Source: MaitreDScheduleTests.cs line 16 Duration: 340 ms Message: FsCheck.Xunit.PropertyFailedException : Falsifiable, after 2 tests (0 shrinks) (StdGen (48558275,297233133)): Original: <null> (Ploeh.Samples.Restaurants.RestApi.MaitreD, [|Ploeh.Samples.Restaurants.RestApi.Reservation|]) ---- System.InvalidOperationException : Failed to compare two elements in the array. -------- System.ArgumentException : At least one object must implement IComparable. Stack Trace: ----- Inner Stack Trace ----- GenericArraySortHelper`1.Sort(T[] keys, Int32 index, Int32 length, IComparer`1 comparer) Array.Sort[T](T[] array, Int32 index, Int32 length, IComparer`1 comparer) EnumerableSorter`2.QuickSort(Int32[] keys, Int32 lo, Int32 hi) EnumerableSorter`1.Sort(TElement[] elements, Int32 count) OrderedEnumerable`1.ToList() Enumerable.ToList[TSource](IEnumerable`1 source) MaitreD.Allocate(IEnumerable`1 reservations) line 91 <>c__DisplayClass21_0.<Schedule>b__4(<>f__AnonymousType7`2 <>h__TransparentIdentifier1) line 114 <>c__DisplayClass2_0`3.<CombineSelectors>b__0(TSource x) SelectIPartitionIterator`2.GetCount(Boolean onlyIfCheap) Enumerable.Count[TSource](IEnumerable`1 source) MaitreDScheduleTests.ScheduleImp(MaitreD sut, Reservation[] reservations) line 31 <>c.<Schedule>b__0_2(ValueTuple`2 t) line 22 ForAll@15.Invoke(Value arg00) Testable.evaluate[a,b](FSharpFunc`2 body, a a) ----- Inner Stack Trace ----- Comparer.Compare(Object a, Object b) ObjectComparer`1.Compare(T x, T y) EnumerableSorter`2.CompareAnyKeys(Int32 index1, Int32 index2) ComparisonComparer`1.Compare(T x, T y) ArraySortHelper`1.SwapIfGreater(T[] keys, Comparison`1 comparer, Int32 a, Int32 b) ArraySortHelper`1.IntroSort(T[] keys, Int32 lo, Int32 hi, Int32 depthLimit, Comparison`1 comparer) GenericArraySortHelper`1.Sort(T[] keys, Int32 index, Int32 length, IComparer`1 comparer)
The code highlighted with red is user code (i.e. my code). The rest comes from .NET or FsCheck.
While a stack trace like that can look intimidating, I usually navigate to the top stack frame of my own code. As I reproduce my investigation, see if you can spot the problem before I did.
Understand before resolving #
Before starting the investigation proper, we might as well acknowledge what seems evident. I had a fully passing test suite, then I edited two lines of code, which caused the above error. The two nested exception messages contain obvious clues: Failed to compare two elements in the array, and At least one object must implement IComparable.
The only edit I made was to change an int to a NaturalNumber, and NaturalNumber didn't implement IComparable. It seems straightforward to just make NaturalNumber implement that interface and move on, and as it turns out, that is the solution.
As I describe in Code That Fits in Your Head, when troubleshooting, first seek to understand the problem. I've seen too many people go immediately into 'action mode' when faced with a problem. It's often a suboptimal strategy.
First, if the immediate solution turns out not to work, you can waste much time trashing, trying various 'fixes' without understanding the problem.
Second, even if the resolution is easy, as is the case here, if you don't understand the underlying cause and effect, you can easily build a cargo cult-like 'understanding' of programming. This could become one such experience: All wrapper types must implement IComparable, or some nonsense like that.
Unless people are getting hurt or you are bleeding money because of the error, seek first to understand, and only then fix the problem.
First clue #
The top user stack frame is the Allocate method:
private IEnumerable<Table> Allocate( IEnumerable<Reservation> reservations) { List<Table> allocation = Tables.ToList(); foreach (var r in reservations) { var table = allocation.Find(t => t.Fits(r.Quantity)); if (table is { }) { allocation.Remove(table); allocation.Add(table.Reserve(r)); } } return allocation; }
The stack trace points to line 91, which is the first line of code; where it calls Tables.ToList(). This is also consistent with the stack trace, which indicates that the exception is thrown from ToList.
I am, however, not used to ToList throwing exceptions, so I admit that I was nonplussed. Why would ToList try to sort the input? It usually doesn't do that.
Now, I did notice the OrderedEnumerable`1 on the stack frame above Enumerable.ToList, but this early in the investigation, I failed to connect the dots.
What does the caller look like? It's that scary DisplayClass21...
Immediate caller #
The code that calls Allocate is the Schedule method, the System Under Test:
public IEnumerable<TimeSlot> Schedule( IEnumerable<Reservation> reservations) { return from r in reservations group r by r.At into g orderby g.Key let seating = new Seating(SeatingDuration, g.Key) let overlapping = reservations.Where(seating.Overlaps) select new TimeSlot(g.Key, Allocate(overlapping).ToList()); }
While it does orderby, it doesn't seem to be sorting the input to Allocate. While overlapping is a filtered subset of reservations, the code doesn't sort reservations.
Okay, moving on, what does the caller of that method look like?
Test implementation #
The caller of the Schedule method is this test implementation:
private static void ScheduleImp( MaitreD sut, Reservation[] reservations) { var actual = sut.Schedule(reservations); Assert.Equal( reservations.Select(r => r.At).Distinct().Count(), actual.Count()); Assert.Equal( actual.Select(ts => ts.At).OrderBy(d => d), actual.Select(ts => ts.At)); Assert.All(actual, ts => AssertTables(sut.Tables, ts.Tables)); Assert.All( actual, ts => AssertRelevance(reservations, sut.SeatingDuration, ts)); }
Notice how the first line of code calls Schedule, while the rest is 'just' assertions.
Because I had noticed that OrderedEnumerable`1 on the stack, I was on the lookout for an expression that would sort an IEnumerable<T>. The ScheduleImp method surprised me, though, because the reservations parameter is an array. If there was any problem sorting it, it should have blown up much earlier.
I really should be paying more attention, but despite my best resolution to proceed methodically, I was chasing the wrong clue.
Which line of code throws the exception? The stack trace says line 31. That's not the sut.Schedule(reservations) call. It's the first assertion following it. I failed to notice that.
Property #
I was stumped, and not knowing what to do, I looked at the fourth and final piece of user code in that stack trace:
[Property] public Property Schedule() { return Prop.ForAll( (from rs in Gens.Reservations from m in Gens.MaitreD(rs) select (m, rs)).ToArbitrary(), t => ScheduleImp(t.m, t.rs)); }
No sorting there. What's going on?
In retrospect, I'm struggling to understand what was going on in my mind. Perhaps you're about to lose patience with me. I was chasing the wrong 'clue', just as I said above that 'other' people do, but surely, it's understood, that I don't.
WYSIATI #
In Code That Fits in Your Head I spend some time discussing how code relates to human cognition. I'm no neuroscientist, but I try to read books on other topics than programming. I was partially inspired by Thinking, Fast and Slow in which Daniel Kahneman (among many other topics) presents how System 1 (the inaccurate fast thinking process) mostly works with what's right in front of it: What You See Is All There Is, or WYSIATI.
That OrderedEnumerable`1 in the stack trace had made me look for an IEnumerable<T> as the culprit, and in the source code of the Allocate method, one parameter is clearly what I was looking for. I'll repeat that code here for your benefit:
private IEnumerable<Table> Allocate( IEnumerable<Reservation> reservations) { List<Table> allocation = Tables.ToList(); foreach (var r in reservations) { var table = allocation.Find(t => t.Fits(r.Quantity)); if (table is { }) { allocation.Remove(table); allocation.Add(table.Reserve(r)); } } return allocation; }
Where's the IEnumerable<T> in that code?
reservations, right?
Revelation #
As WYSIATI 'predicts', the brain gloms on to what's prominent. I was looking for IEnumerable<T>, and it's right there in the method declaration as the parameter IEnumerable<Reservation> reservations.
As covered in multiple places (my book, The Programmer's Brain), the human brain has limited short-term memory. Apparently, while chasing the IEnumerable<T> clue, I'd already managed to forget another important datum.
Which line of code throws the exception? This one:
List<Table> allocation = Tables.ToList();
The IEnumerable<T> isn't reservations, but Tables.
While the code doesn't explicitly say IEnumerable<Table> Tables, that's just what it is.
Yes, it took me way too long to notice that I'd been barking up the wrong tree all along. Perhaps you immediately noticed that, but have pity with me. I don't think this kind of human error is uncommon.
The culprit #
Where do Tables come from? It's a read-only property originally injected via the constructor:
public MaitreD( TimeOfDay opensAt, TimeOfDay lastSeating, TimeSpan seatingDuration, IEnumerable<Table> tables) { OpensAt = opensAt; LastSeating = lastSeating; SeatingDuration = seatingDuration; Tables = tables; }
Okay, in the test then, where does it come from? That's the m in the above property, repeated here for your convenience:
[Property] public Property Schedule() { return Prop.ForAll( (from rs in Gens.Reservations from m in Gens.MaitreD(rs) select (m, rs)).ToArbitrary(), t => ScheduleImp(t.m, t.rs)); }
The m variable is generated by Gens.MaitreD, so let's follow that clue:
internal static Gen<MaitreD> MaitreD( IEnumerable<Reservation> reservations) { return from seatingDuration in Gen.Choose(1, 6) from tables in Tables(reservations) select new MaitreD( TimeSpan.FromHours(18), TimeSpan.FromHours(21), TimeSpan.FromHours(seatingDuration), tables); }
We're not there yet, but close. The tables variable is generated by this Tables helper function:
/// <summary> /// Generate a table configuration that can at minimum accomodate all /// reservations. /// </summary> /// <param name="reservations">The reservations to accommodate</param> /// <returns>A generator of valid table configurations.</returns> private static Gen<IEnumerable<Table>> Tables( IEnumerable<Reservation> reservations) { // Create a table for each reservation, to ensure that all // reservations can be allotted a table. var tables = reservations.Select(r => Table.Standard(r.Quantity)); return from moreTables in Gen.Choose(1, 12).Select( i => Table.Standard(new NaturalNumber(i))).ArrayOf() let allTables = tables.Concat(moreTables).OrderBy(t => t.Capacity) select allTables.AsEnumerable(); }
And there you have it: OrderBy(t => t.Capacity)!
The Capacity property was exactly the property I changed from int to NaturalNumber - the change that made the test fail.
As expected, the fix was to let NaturalNumber implement IComparable<NaturalNumber>.
Conclusion #
I thought this little troubleshooting session was interesting enough to write down. I spent perhaps twenty minutes on it before I understood what was going on. Not disastrously long, but enough time that I was relieved when I figured it out.
Apart from the obvious (look for the problem where it is), there is one other useful lesson to be learned, I think.
Deferred execution can confuse even the most experienced programmer. It took me some time before it dawned on me that even though the the MaitreD constructor had run and the object was 'safely' initialised, it actually wasn't.
The implication is that there's a 'disconnect' between the constructor and the Allocate method. The error actually happens during initialisation (i.e. in the caller of the constructor), but it only manifests when you run the method.
Ever since I discovered the IReadOnlyCollection<T> interface in 2013 I've resolved to favour it over IEnumerable<T>. This is one example of why that's a good idea.
Despite my best intentions, I, too, cut corners from time to time. I've done it here, by accepting IEnumerable<Table> instead of IReadOnlyCollection<Table> as a constructor parameter. I really should have known better, and now I've paid the price.
This is particularly ironic because I also love Haskell so much. Haskell is lazy by default, so you'd think that I run into such issues all the time. An expression like OrderBy(t => t.Capacity), however, wouldn't have compiled in Haskell unless the sort key implemented the Ord type class. Even C#'s type system can express that a generic type must implement an interface, but OrderBy doesn't do that.
This problem could have been caught at compile-time, but unfortunately it wasn't.
Comments
I made a pull request describing the issue.
As this is likely a breaking change I don't have high hopes for it to be fixed, though…