Bug 10808 - SplitOrderedList appears to call its EqualityComparer on uninitialized values
Summary: SplitOrderedList appears to call its EqualityComparer on uninitialized values
Alias: None
Product: Class Libraries
Classification: Mono
Component: mscorlib ()
Version: unspecified
Hardware: All All
: --- normal
Target Milestone: Untriaged
Assignee: Bugzilla
Depends on:
Reported: 2013-03-01 08:04 UTC by Kevin Gadd
Modified: 2014-11-25 05:01 UTC (History)
2 users (show)

Is this bug a regression?: ---
Last known good build:

Log file from user showing special null check being triggered (15.54 KB, text/plain)
2013-03-01 08:05 UTC, Kevin Gadd

Notice (2018-05-24): bugzilla.xamarin.com is now in read-only mode.

Please join us on Visual Studio Developer Community and in the Xamarin and Mono organizations on GitHub to continue tracking issues. Bugzilla will remain available for reference in read-only mode. We will continue to work on open Bugzilla bugs, copy them to the new locations as needed for follow-up, and add the new items under Related Links.

Our sincere thanks to everyone who has contributed on this bug tracker over the years. Thanks also for your understanding as we make these adjustments and improvements for the future.

Please create a new report on GitHub or Developer Community with your current version information, steps to reproduce, and relevant error messages or log files if you are hitting an issue that looks similar to this resolved bug and you do not yet see a matching new report.

Related Links:

Description Kevin Gadd 2013-03-01 08:04:11 UTC
While theoretically this should be harmless for thoroughly robust IEqualityComparer implementations, SplitOrderedList appears to be able to invoke IEqualityComparer.Equals on one (or two) uninitialized values during normal use.

If you look at the current source code on trunk:
There are two constructors for Node that do not actually initialize the Node.Data or Node.SubKey members. Despite this, the IEqualityComparer is invoked on Node.SubKey in various scenarios (insert, search, etc) without anything that seems like it would detect that a node lacks a valid SubKey.

One of my users has observed behavior caused by this in my compiler when running in a multi-threaded environment on Mono 3.0.6 (built from source). I did some troubleshooting with him and ended up adding a special check to the key-type I was using to detect that an uninitialized Key had been passed to the IEqualityComparer implementation (Key's only constructor asserts that it is given non-null arguments and my code never uses the argumentless constructor or default() ). Adding the check caused the check to be triggered by SplitOrderedList, as you can see in the attachment text file.

Sadly I have not been able to easily come up with a reproducible test case for this problem due to the fact that it seems to only appear in multithreaded scenarios (and in fact the user was not able to reproduce it on all of his machines) - my only accessible Linux machine is single-core.

I'm not sure what the exact fix would be here. You could argue that all IEqualityComparer implementations should handle either argument (or both arguments) being default(T), but this is definitely something that I've never seen any of the MS BCL types ever do, so it's at least a big divergence from expected behavior - kind of troublesome since it's in a concurrent container, but I know these things happen sometimes. :) A simple fix might be to have a 'valid' flag stored in the Node type that is only set if the Node actually has a Key and a Value, and then to ensure that the EqualityComparer is only invoked if both nodes are valid. (If the nodes' validity doesn't match, they can't be equal because an invalid node doesn't have a key or a value).
Comment 1 Kevin Gadd 2013-03-01 08:05:40 UTC
Created attachment 3519 [details]
Log file from user showing special null check being triggered

Not sure why the log didn't attach the first time.

This is the key type implementation and comparer that contain the special null check:
Comment 2 Marek Safar 2014-11-25 05:01:26 UTC
Resolved in master