# UNDF: UNDF-2026-000000503
# prometheus-0002: dependencyMap.dependencies() O(R²×D) in AnalyseRules

**CWE:** CWE-407 (Algorithmic Complexity — Inefficient Algorithmic Complexity)
**Severity:** HIGH
**Component:** `rules/group.go` — `(dependencyMap).dependencies()`
**Commit:** cb33823

## Defect

`dependencyMap` is `map[Rule][]Rule` mapping each rule to its *dependents* (rules that
consume its output).  `dependencies(r)` inverts the map by iterating all entries and
calling `slices.Contains(dependents, r)` on each dependents slice.

```go
// rules/group.go:1090-1103
func (m dependencyMap) dependencies(r Rule) []Rule {
    if len(m) == 0 {
        return []Rule{}
    }
    var dependencies []Rule
    for rule, dependents := range m {           // O(R) map scan
        if slices.Contains(dependents, r) {     // O(D) slice scan each time
            dependencies = append(dependencies, rule)
        }
    }
    return dependencies
}
```

`AnalyseRules` (called once per group reload) calls this for every rule:

```go
// rules/manager.go:512-515
for _, r := range rules {                          // O(R) outer loop
    r.SetDependentRules(depMap.dependents(r))      // O(1) map lookup — fine
    r.SetDependencyRules(depMap.dependencies(r))   // O(R×D) per call — BAD
}
```

Total: **O(R² × D)** where R = rules in group, D = average dependents per rule.

## Impact

In a rule group with 500 rules and average fan-out D=10, `AnalyseRules` performs
500 × 500 × 10 = **2,500,000** comparisons on every group reload.  Rule groups of
this size are common in Prometheus deployments with auto-generated recording rules
from tools like `kube-prometheus`.

## Fix

Build the inverse map (rule → its dependencies) inside `buildDependencyMap` so that
`dependencies(r)` becomes an O(1) lookup.

```go
// Add a second map alongside dependencyMap:
type dependencyMap map[Rule][]Rule      // rule → rules that depend on it (dependents)
type dependenciesMap map[Rule][]Rule    // rule → rules it depends on (dependencies)

// OR: extend buildDependencyMap to maintain both directions simultaneously.
// The forward relationship is already stored; add the reverse at the same time:

// In buildDependencyMap, alongside:
//   dependencies[other] = append(dependencies[other], rule)
// also maintain:
//   inverseDeps[rule] = append(inverseDeps[rule], other)
//
// Then dependencies(r) is just:
//   return inverseDeps[r]   // O(1)
```

Minimal patch to `buildDependencyMap` and `dependencyMap`:

```go
// rules/group.go

// dependencyMap maps a rule to the rules which depend on its output (dependents).
// dependencyMap also carries the inverse: m.inverse maps a rule to its own dependencies.
type dependencyMap struct {
    forward map[Rule][]Rule // rule → dependents
    inverse map[Rule][]Rule // rule → dependencies
}

func (m dependencyMap) dependents(r Rule) []Rule {
    return m.forward[r]
}

func (m dependencyMap) dependencies(r Rule) []Rule {
    if m.inverse == nil {
        return []Rule{}
    }
    return m.inverse[r]
}

func buildDependencyMap(rules []Rule) dependencyMap {
    dm := dependencyMap{
        forward: make(map[Rule][]Rule),
        inverse: make(map[Rule][]Rule),
    }
    // ...existing loop unchanged, but after each:
    //   dm.forward[other] = append(dm.forward[other], rule)
    // also add:
    //   dm.inverse[rule] = append(dm.inverse[rule], other)
}
```

## Complexity

| Version  | AnalyseRules cost         | R=500, D=10 ops |
|----------|---------------------------|-----------------|
| Defective | O(R × R × D)              | 2,500,000        |
| Patched   | O(R) map lookups O(1) each | 500              |
| Speedup   |                           | **5000×**        |

At R=100, D=5: defective = 50,000 ops; patched = 100 ops → **500× speedup**.
