# UNDF: UNDF-2026-000000232
# UNDF: (pending)
# helm-0001: ResourceList.Contains/Difference/Intersect — O(N²) linear scan

## CWE-407 — Algorithmic Complexity

| Field | Value |
|-------|-------|
| ID | helm-0001 |
| Severity | MEDIUM |
| Ecosystem | helm |
| Package | pkg/kube |
| File | `pkg/kube/resource.go` |
| Lines | 61–79 |
| Complexity | O(N²) — Difference/Intersect each call Contains O(N) per element |
| Hot path | `helm upgrade` resource reconciliation — deletes resources not in new manifest |

## Defect

`ResourceList.Contains()` is a linear scan over all resources:

```go
func (r ResourceList) Contains(info *resource.Info) bool {
    for _, i := range r {
        if isMatchingInfo(i, info) {
            return true
        }
    }
    return false
}
```

`Difference` and `Intersect` call `Contains` inside a `Filter` loop, which iterates
over the full list:

```go
func (r ResourceList) Difference(rs ResourceList) ResourceList {
    return r.Filter(func(info *resource.Info) bool {
        return !rs.Contains(info)   // O(|rs|) per element of r
    })
}

func (r ResourceList) Intersect(rs ResourceList) ResourceList {
    return r.Filter(rs.Contains)   // O(|rs|) per element of r
}
```

`Filter` iterates over `r`:

```go
func (r ResourceList) Filter(fn func(*resource.Info) bool) ResourceList {
    var result ResourceList
    for _, v := range r {
        if fn(v) {
            result = append(result, v)
        }
    }
    return result
}
```

At `helm upgrade` time, `client.go:648` calls `originals.Difference(targets)` to find
resources to delete. With N=200 resources, this costs 200×200 = 40,000 equality checks
instead of 200 map lookups.

`isMatchingInfo` compares Name+Namespace+Group+Kind — uniquely identifies a resource,
making it suitable as a map key.

## Fix

Build an index set from `rs` before filtering:

```go
// resourceKey returns a unique string key for a resource.Info.
func resourceKey(info *resource.Info) string {
    return fmt.Sprintf("%s/%s/%s/%s",
        info.Mapping.GroupVersionKind.Group,
        info.Mapping.GroupVersionKind.Kind,
        info.Namespace,
        info.Name,
    )
}

func (r ResourceList) Contains(info *resource.Info) bool {
    for _, i := range r {
        if isMatchingInfo(i, info) {
            return true
        }
    }
    return false
}

// Difference returns resources in r not in rs. O(|r| + |rs|) with index.
func (r ResourceList) Difference(rs ResourceList) ResourceList {
    index := make(map[string]struct{}, len(rs))
    for _, i := range rs {
        index[resourceKey(i)] = struct{}{}
    }
    return r.Filter(func(info *resource.Info) bool {
        _, found := index[resourceKey(info)]
        return !found
    })
}

// Intersect returns resources in both r and rs. O(|r| + |rs|) with index.
func (r ResourceList) Intersect(rs ResourceList) ResourceList {
    index := make(map[string]struct{}, len(rs))
    for _, i := range rs {
        index[resourceKey(i)] = struct{}{}
    }
    return r.Filter(func(info *resource.Info) bool {
        _, found := index[resourceKey(info)]
        return found
    })
}
```

## Speedup

| N (resources) | Before (ops) | After (ops) | Speedup |
|---|---|---|---|
| 50 | 2,500 | 100 | 25× |
| 200 | 40,000 | 400 | 100× |
| 500 | 250,000 | 1,000 | 250× |
