mfogliatto / mfogliatto/ReferenceCop

[Performance] PatternMatchComparer.GetHashCode breaks Dictionary invariant — O(1) lookups degrade to O(n)

Open Beginner friendly
#70 0 comments 0 reactions 0 assignees View on GitHub
performance
Dominant language
C#
Stars
1
Forks
2
PR merge metrics
No merged PRs in 30d

Description

## Description

`PatternMatchComparer` implements `IEqualityComparer` but its `GetHashCode` method uses the default `string.GetHashCode()`. This violates the `IEqualityComparer` contract: when `Equals(x, y)` returns true, `GetHashCode(x)` must equal `GetHashCode(y)`.

Specifically, `PatternMatchComparer.Equals("*", "SomeAssembly")` returns `true`, but `"*".GetHashCode() != "SomeAssembly".GetHashCode()`. This means any dictionary using this comparer cannot perform correct O(1) lookups for wildcard patterns.

## Affected Files

- `src/ReferenceCop/Comparers/PatternMatchComparer.cs` — `GetHashCode()` (line 12)
- `src/ReferenceCop/Detectors/AssemblyNameViolationDetector.cs` — `rules` dictionary uses this comparer (line 8)

## Impact

- **Broken invariant**: The `Dictionary` in `AssemblyNameViolationDetector` uses `PatternMatchComparer` as its equality comparer. Dictionary lookups via `TryGetValue` or indexer for wildcard keys will silently fail to find matches because hash codes differ.
- **Hidden by current usage**: The current `GetViolationsFrom()` iterates `this.rules` via `foreach` (treating the dictionary as `IEnumerable`), which bypasses hash-based lookup entirely — masking the bug. But it also means the Dictionary provides zero performance benefit over a `List`.
- **The `experimental` path is affected**: `GetViolationsFromExperimental` uses `exactMatchRules.TryGetValue()` which works for exact matches (correct hash codes), but the original `rules` dictionary remains broken for any consumers that might try to look up by key.

## Suggested Fix

Since `PatternMatchComparer` supports wildcards, it cannot produce consistent hash codes for all equal pairs. Two options:

1. **Replace the Dictionary with a List** for rule storage (since it is only iterated, never looked up by key):

```csharp
private readonly List> rules;
```

This makes the actual data structure match how it is used and avoids the misleading `Dictionary` type.

2. **If dictionary lookup is needed**, use a constant hash code (trades O(1) for correctness):

```csharp
public int GetHashCode(string obj) => 0; // Forces bucket collision, but maintains contract
```

This is correct but makes the dictionary degenerate to O(n). Option 1 is preferred since the dictionary is never used as a dictionary.

Contributor guide

Open the contributing guide

Research direction

Start with src/ReferenceCop/Comparers/PatternMatchComparer.cs and inspect GetHashCode alongside Equals. Then read the rules field and its uses in src/ReferenceCop/Detectors/AssemblyNameViolationDetector.cs, including the foreach and TryGetValue paths. Done means wildcard equality and hashing no longer violate the comparer contract, and the chosen rule-storage approach matches how the collection is used.

Written by the indexing model from the issue text.

Assessment

Tech stack
csharp
Domain
build-system, devtools
Issue type
Bug
Difficulty
2/5
Estimated time
1-3 hours
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
76/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.