Incorrect behavior of SortedDictionary when used with OrdinalIgnoreCase comparer

[AndreyChechel]

Number of entries added to a SortedDictionary shouldn't be affected by the order of insertion.
The issue is reproducible in non-Windows environments (checked in .NET Core 2.1 / 2.2).
See playground.

There are 5 entries being inserted in the sample below. The dictionary is supposed to have 4 entries, since two records have the equal keys in terms of OrdinalIgnoreCase comparer,

• ["narınnarın"] = 3
• ["narinnarin"] = 4

Proving snippet:

var equal = string.Equals("narınnarın", "narinnarin", StringComparison.OrdinalIgnoreCase);
Console.WriteLine(equal); // "True" (on Linux/Mac)

Sample

using System;
using System.Collections.Generic;
using System.Reflection;
using System.Runtime.Versioning;

public class Program
{
  public static void Main()
  {
    Console.WriteLine(Environment.OSVersion);

    // ------------------------------------------------------------------------------
    // Test Case 1
    // Expected output: 4
    // Actual output: 4
    // ------------------------------------------------------------------------------

    var dict1 = new SortedDictionary<string, int>(StringComparer.OrdinalIgnoreCase);

    dict1["naryn"] = 1;
    dict1["нарын"] = 2;
    dict1["narınnarın"] = 3;
    dict1["narinnarin"] = 4;
    dict1["ナルインナルイン"] = 5;

    Console.WriteLine(dict1.Count); // Outputs 4 - OK

    // ------------------------------------------------------------------------------
    // Test Case 2 (changed order of insertion)
    // Expected output: 4
    // Actual output: 5
    // ------------------------------------------------------------------------------

    var dict2 = new SortedDictionary<string, int>(StringComparer.OrdinalIgnoreCase);

    dict2["naryn"] = 1;
    dict2["нарын"] = 2;
    dict2["ナルインナルイン"] = 3;
    dict2["narınnarın"] = 4;
    dict2["narinnarin"] = 5;

    Console.WriteLine(dict2.Count); // Outputs 5 (Expected 4)
  }
}

Actual Output

Unix 5.0.3.200
4
5

Expected Output

Unix 5.0.3.200
4
4

[pgovind]

I spent some time debugging this and here's what I found:

I don't think there is a bug in the implementation of SortedDictionary(or SortedSet which is what it leverages). The interesting bit is the following lines:

            var equal = string.Equals("narınnarın", "narinnarin", StringComparison.OrdinalIgnoreCase);
            Console.WriteLine(equal); // True on Mac
            var rightCompare = StringComparer.OrdinalIgnoreCase.Compare("naryn", "narınnarın"); // equals -1
            var leftCompare = StringComparer.OrdinalIgnoreCase.Compare("naryn", "narinnarin"); // equals 16

This is important because "narınnarın" is the right child of "naryn". When we go looking for "narinnarin", we check Compare("naryn", "narinnarin"). If "narınnarın" and "narinnarin" are indeed equal, we should have gone right at "naryn" and found "narınnarın". Instead, we go left and find null and insert into the SortedSet. Why are rightCompare and leftCompare different? This may be a string compare bug. Tagging @tarekgh to potentially take a look?

[tarekgh]

When you are comparing "naryn" and "narınnarın", the first different characters are 'y' and 'ı'. The 'y' ordinal value is 0x79 and the ordinal value of 'ı' is 0x131. This means 'y' < 'ı' which means "naryn" < "narınnarın" and that is why you got negative number.

When you are comparing "naryn" and "narinnarin", the first different characters are 'y' and 'i'. The 'y' ordinal value is 0x79 and the ordinal value of 'i' is 0x69. This means 'y' > 'i' which means "naryn" > "narinnarin" and that is why you got positive number.

Note, the casing is done only for checking the equality but not for deciding which string less than or greater the other string.

[GrabYourPitchforks]

Seems like it might be an ICU bug? Per @pgovind's comment, the collation engine is returning s1 < s2, s1 > s3, and s2 == s3. Those three relationships when taken together are nonsensical.

[dotnet-policy-service]

Due to lack of recent activity, this issue has been marked as a candidate for backlog cleanup. It will be closed if no further activity occurs within 14 more days. Any new comment (by anyone, not necessarily the author) will undo this process.

This process is part of our issue cleanup automation.