mfogliatto / mfogliatto/ReferenceCop

[Performance] O(rules × references) nested loop in GetViolationsFrom for ProjectPath/ProjectTag detectors

Open
#54 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

`ProjectPathViolationDetector.GetViolationsFrom()` and `ProjectTagViolationDetector.GetViolationsFrom()` both iterate over all rules in the outer loop and all references in the inner loop, resulting in O(rules × references) complexity.

Unlike `AssemblyNameViolationDetector` (which has an experimental O(n) path using dictionary lookups), these detectors have no optimized path — the `GetViolationsFromExperimental()` just delegates back to the same nested loop.

## Affected Files

- `src/ReferenceCop/Detectors/ProjectPathViolationDetector.cs` — `GetViolationsFrom()`
- `src/ReferenceCop/Detectors/ProjectTagViolationDetector.cs` — `GetViolationsFrom()`

## Impact

For projects with many references (e.g., 50+ project references) and many rules, the nested iteration becomes costly, especially during MSBuild where this runs per-project.

## Suggested Optimization

**For ProjectTagViolationDetector:** Pre-filter rules that match the current project's tag (only one `fromProjectTag` can match). Then use a HashSet or dictionary keyed by `ToProjectTag` for O(1) lookup per reference:

```csharp
var matchingRules = this.rules.Where(r => r.FromProjectTag == fromProjectTag).ToList();
var blockedTags = new HashSet(matchingRules.Select(r => r.ToProjectTag));

foreach (var referenceContext in references)
{
var toTag = this.projectTagProvider.GetProjectTag(referenceContext.Reference);
if (blockedTags.Contains(toTag) && !referenceContext.IsWarningSuppressed)
{
var rule = matchingRules.First(r => r.ToProjectTag == toTag);
yield return new Violation(rule, referenceContext.Reference);
}
}
```

**For ProjectPathViolationDetector:** Similar approach — pre-filter rules matching the current project's path prefix, then check references linearly against only the matching subset.

Contributor guide

Open the contributing guide

Research direction

Read GetViolationsFrom() and GetViolationsFromExperimental() in src/ReferenceCop/Detectors/ProjectPathViolationDetector.cs and ProjectTagViolationDetector.cs, then compare the experimental approach in AssemblyNameViolationDetector. Preserve rule matching and warning suppression while avoiding the nested rules-by-references iteration; done means both detectors retain the same violations with improved lookup complexity.

Written by the indexing model from the issue text.

Assessment

Tech stack
csharp
Domain
build-system, performance
Issue type
Refactor
Difficulty
3/5
Estimated time
1-2 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
68/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.