[BREAKING]: `ParsedThemeRule.GetHashCode()` violates hash code contract causing incorrect behavior of equality and in hash-based collections

[udlose]

ParsedThemeRuleTests.cs.txt

Description

The ParsedThemeRule class has a problematic implementation of GetHashCode() and Equals() methods are inconsistent, violating the fundamental hash code contract. This causes incorrect behavior when ParsedThemeRule instances are used testing equality or as keys in Dictionary<T> or stored in HashSet<T>.

I've noticed 3 distinct manifestations of this bug:

1. Two ParsedThemeRule instances which only differ by name are considered equal
2. Two ParsedThemeRule instances which are "equivalent" by definition do not produce the same hash code and thus break the GetHashCode API contract.
3. The ParsedThemeRule type cannot effectively be used as a key in a Dictionary

Important

Most of the GetHashCode implementations I have seen in TextMateSharp have a fundamental design issue: the fields are not immutable. Fields/properties that are used in GetHashCode should be immutable. This ensures that objects aren't lost in hash-based collectins.
The bug fix I propose here DOES NOT address the field immutability issue. That would be a breaking change since the fields are currently writable.

Root Causes

1. GetHashCode() method: does not use name property as part of the hash code calculation
2. Equals() method: Uses Enumerable.SequenceEqual() for parentScopes comparison (content-based)
3. GetHashCode() method: Uses List<T>.GetHashCode() for parentScopes (identity-based/reference-based)
   This means two ParsedThemeRule objects that are considered equal by Equals() can produce different hash codes, violating the contract:

If obj1.Equals(obj2) returns true, then obj1.GetHashCode() MUST equal obj2.GetHashCode()

Impact

This bug affects any code using ParsedThemeRule for Equality or in hash-based collections:

• ❌ Two ParsedThemeRule instances which only differ by name are considered equal
• ❌ Objects which have the same content but different references are not considered equal
• ❌ Dictionary lookups may fail to find equal keys
• ❌ HashSet may store duplicate "equal" objects
• ❌ LINQ operations like Distinct() may not work correctly
• ❌ Caching strategies using these objects as keys will be unreliable

Steps to Reproduce

Several of the unit tests in the attached unit test class demonstrate the problem:

• Equals_DifferentName_ReturnsFalse
• GetHashCode_CanBeUsedAsDictionaryKey
• GetHashCode_EqualObjects_ProduceSameHashCode
• ToString_NullParentScopes_DoesNotThrow

Proposed Solution

The GetHashCode() method needs to:

1. Include the name field in the hash computation
2. Compute a hash based on the contents of parentScopes, not its reference

Here's the fix:

public override int GetHashCode()
{
    int prime = 31;
    int result = 1;
    result = (prime * result) + ((background == null) ? 0 : background.GetHashCode());
    result = (prime * result) + (int)fontStyle;
    result = (prime * result) + ((foreground == null) ? 0 : foreground.GetHashCode());
    result = (prime * result) + index;
    result = (prime * result) + ((name == null) ? 0 : name.GetHashCode());
    if (parentScopes != null)
    {
        foreach (string parentScope in parentScopes)
        {
            result = (prime * result) + ((parentScope == null) ? 0 : parentScope.GetHashCode());
        }
    }
    result = (prime * result) + ((scope == null) ? 0 : scope.GetHashCode());
    return result;
}

public override bool Equals(object obj)
{
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (GetType() != obj.GetType())
        return false;
    ParsedThemeRule other = (ParsedThemeRule)obj;
    if (background == null)
    {
        if (other.background != null)
            return false;
    }
    else if (!background.Equals(other.background))
        return false;
    if (fontStyle != other.fontStyle)
        return false;
    if (foreground == null)
    {
        if (other.foreground != null)
            return false;
    }
    else if (!foreground.Equals(other.foreground))
        return false;
    if (index != other.index)
        return false;
    if (parentScopes == null)
    {
        if (other.parentScopes != null)
            return false;
    }
    else if (!Enumerable.SequenceEqual(parentScopes, other.parentScopes))
        return false;
    if (scope == null)
    {
        if (other.scope != null)
            return false;
    }
    else if (!scope.Equals(other.scope))
        return false;
    if (name == null)
    {
        if (other.name != null)
            return false;
    }
    else if (!name.Equals(other.name))
        return false;
    return true;
}

[danipen]

Thanks for the insights. Are you providing a PR for this? If so, please pass the benchmark to ensure we don't regress (benchmarks are not passed in the CI).

[udlose]

Thanks for the insights. Are you providing a PR for this? If so, please pass the benchmark to ensure we don't regress (benchmarks are not passed in the CI).

Sure I can do that.

[udlose]

@danipen do you mean to run the benchmark app and provide the results or something else? I was going to do the former.

[danipen]

Yes just compare perf after changes against branch base to ensure we don't add perf regressions

[udlose]

I'm a .NET Performance Architect so I always make sure to do so :). Thanks for clarifying.

[danipen]

Hhaha sorry for the asumption!

[udlose]

Hhaha sorry for the asumption!

no worries! As a repo owner, you are taking the quality of your code seriously which I appreciate. And, I wouldn't expect you to know what my full time consulting role is lol

[danipen]

Absolutely. This project is used by Unity Version Controls (formerly Plastic SCM) so we treat it as our production code.

[udlose]

@danipen I forgot to ask...is there a reason that ParsedThemeRule does not include name in any operation? ToString, Equals, GetHashCode? Just making sure before I make a change that was intentionally done the way it is currently coded.

[danipen]

is there a reason that ParsedThemeRule does not include name in any operation? ToString, Equals, GetHashCode?

Nope. Probably the upstream port (tm4e) does it that way. I cannot chek it now (I'm not in a laptop) but double check if you want. Anyway event if the upstream is not fine I'm open to do it well here.

[udlose]

Ah, I see why. The upstream implementation doesn't have a field/property of name. Thus, there is no code that would use that field: https://github.com/eclipse-tm4e/tm4e/blob/main/org.eclipse.tm4e.core/src/main/java/org/eclipse/tm4e/core/internal/theme/ParsedThemeRule.java#L47

It looks like this commit added name to TextMateSharp on 5/3/23 by @Andrew1Medvedev

What would you like me to do?

[danipen]

I think it makes sense adapting the GetHashCode then

[udlose]

ok, I'll have a couple of PR's coming soon then with benchmarks. After that, I'll try to pull myself out of this repo and get back to the AvaloniaEdit memory leak that started me down this rabbit hole 😂

I'll fix the leak there first and I noticed some allocation optimization opportunities in DocumentSnapshot I can create a PR for too if you're open to that (of course with benchmarks lol).

[udlose]

@danipen Visibility of fields/properties/classes does not match upstream tm4e implementation #123 should be fixed and merged separately IMO.