NaturalStringComparer returns 0 for different strings like "file5" and "file005", so SortedSet silently drops them and SortedDictionary throws on Add

[matt-edmondson]

What's wrong

NaturalStringComparer.Compare returns 0 whenever every chunk compares equal. Numeric chunks are compared by value after leading zeros are stripped. Different strings therefore compare as equal when they differ only in leading zeros or in digit script:

x	y	Compare(x, y)
"file5"	"file005"	0
"v1"	"v01"	0
"file٥" (Arabic-Indic 5)	"file5"	0

The only ordinal check is the x == y short-circuit at the top of Compare. Nothing breaks the tie after the chunk loop.

Reproduction (ktsu.Sorting from NuGet, net10.0)

var c = new NaturalStringComparer();

var set = new SortedSet<string>(c) { "file5.txt", "file005.txt", "file05.txt" };
// set.Count == 1  → "file005.txt" and "file05.txt" were silently dropped

var d = new SortedDictionary<string, int>(c);
d["v1"] = 1;
d.Add("v01", 2);
// ArgumentException: An item with the same key has already been added. Key: [v01, 2]

var a = new[] { "b05", "a", "b5" }; Array.Sort(a, c);  // a, b05, b5
var b = new[] { "b5", "a", "b05" }; Array.Sort(b, c);  // a, b5, b05
// Same set of inputs, different output depending on input order

Why it matters

The main use for a natural comparer is sorting file names, versions, and similar user-visible keys, where img1.png and img01.png can both exist. Returning 0 for distinct strings causes three problems:

• Silent data loss. SortedSet<string>, SortedList, SortedDictionary, and ImmutableSortedSet treat the two names as the same key. Files disappear from a listing, and nothing reports an error.
• Crashes. SortedDictionary.Add / SortedList.Add throw on keys that are actually distinct.
• Nondeterministic order. Array.Sort / List.Sort are unstable, so the relative order of b5 and b05 depends on the input order. UI lists can reshuffle between refreshes.

IComparer<T> consumers expect Compare(x, y) == 0 only for strings they should treat as identical. Windows' StrCmpLogicalW (Explorer's natural sort) orders 5 and 05 differently for the same reason.

Suggested fix

Keep the natural ordering as the primary key, and add a deterministic tie-break when it reports equality:

// after the chunk loop, instead of returning the length comparison directly:
int chunkCountComparison = xMatches.Length.CompareTo(yMatches.Length);
if (chunkCountComparison != 0)
{
	return chunkCountComparison;
}

// Numerically equal but textually different (leading zeros, digit script): break the tie
// ordinally so distinct strings never compare equal.
return string.CompareOrdinal(x, y);

"file5" and "file005" stay adjacent, and neither can now sort between file4 and file6 on the wrong side. A slightly nicer secondary key is "fewer leading zeros first, then ordinal", which puts file5 before file05 before file005. The ordinal fallback is the minimum needed.

Acceptance criteria

• Compare(x, y) == 0 if and only if string.Equals(x, y, StringComparison.Ordinal) (nulls aside).
• A SortedSet<string> built with the comparer from {"file5", "file05", "file005"} has Count == 3.
• Sorting any permutation of {"a", "b5", "b05"} gives the same output.
• The existing tests that assert 0 for numerically equal chunks (Compare_StringsWithLeadingZeros_HandledCorrectly, Compare_NonAsciiDigits_EqualValuesAreEqual, Compare_NonAsciiLeadingZeros_NormalizedLikeAsciiZeros) are updated to assert a nonzero, antisymmetric result. Only the tie-break changes; numeric ordering against other values stays the same.

[matt-edmondson]

Triage

• Category: Bug
• Priority: High. Compare returns 0 for distinct strings (file5 / file005), which violates the IComparer<T> contract. As a result, SortedSet silently drops entries, SortedDictionary.Add throws on distinct keys, and Array.Sort output depends on input order. File-name sorting is the main use case, so this causes silent data loss.
• Area / suggested assignee: NaturalStringComparer.Compare (the tie-break after the chunk loop), plus the three existing tests that assert 0 for numerically equal chunks. Owner: @matt-edmondson
• Duplicates / in progress: not a duplicate. Open PR Keep NaturalStringComparer transitive across digit scripts #57 ("Keep NaturalStringComparer transitive across digit scripts", for NaturalStringComparer is intransitive for non-ASCII digits (٥ < 10 < z < ٥), so sort output depends on input order #55) changes the same method and the same non-ASCII-digit tests. Land this on top of Keep NaturalStringComparer transitive across digit scripts #57, or fold it in, to avoid conflicts. It is also related to NaturalStringComparer builds a new Regex on every Compare call, so sorting large lists is slow and allocation-heavy #56 (per-call Regex) and NaturalStringComparer sorts file10 before file9 when the digits are outside the BMP (surrogate-pair Nd digits compared as text) #58 (surrogate-pair digits), which touch the same chunking code.
• Next step: after the chunk-count comparison, fall back to string.CompareOrdinal(x, y) (optionally ordering by fewest leading zeros first). Update the equal-chunk tests to assert a nonzero, antisymmetric result, and add the SortedSet Count == 3 and permutation-stability tests.

---

Generated by Claude Code