mfogliatto / mfogliatto/ReferenceCop
[Performance] PatternMatchComparer.GetHashCode breaks Dictionary invariant — O(1) lookups degrade to O(n)
- 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
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