# UNDF: UNDF-2026-000000679
# UNDF: (pending)
# rails-0019: ActionView::Digestor#dependency_digest — O(N²) cycle-detection via Array#include?

## CWE-407 — Algorithmic Complexity: O(N²) template dependency stack scan

| Field | Value |
|-------|-------|
| ID | rails-0019 |
| Severity | MEDIUM |
| Ecosystem | ruby/rails |
| Package | actionview |
| File | `actionview/lib/action_view/digestor.rb` |
| Lines | 97–107 |
| Complexity | O(N²) for linear template dependency chains of depth N |
| Hot path | Called on every cache-miss template digest computation during asset compilation and development-mode rendering |

## Defect

```ruby
# actionview/lib/action_view/digestor.rb  lines 97-107
def dependency_digest(finder, stack)
  children.map do |node|
    if stack.include?(node)      # DEFECT: Array#include? is O(N) — scans entire stack
      false
    else
      finder.digest_cache[node.name] ||= begin
                                           stack.push node   # grows unboundedly
                                           node.digest(finder, stack).tap { stack.pop }
                                         end
    end
  end.join("-")
end
```

`stack` is a plain `Array`. For a chain of depth N (layout → partial_1 → partial_2 → … →
partial_N), each level scans the entire stack to detect cycles:

| Depth | stack.include? cost | Cumulative |
|-------|--------------------|-----------:|
| 1 | 0 | 0 |
| 2 | 1 | 1 |
| 3 | 2 | 3 |
| k | k−1 | k(k−1)/2 |
| N | N−1 | **O(N²)** |

Note: diamond template sharing (A→B→D and A→C→D) is *already handled* by
`finder.digest_cache` — D is cached after first traversal and returned immediately on the
second visit. The O(N²) cost arises purely from the cycle-detection guard on deep linear
chains, not from diamond re-traversal.

The caller `digest(finder, stack = [])` initialises `stack` as a fresh `[]` per top-level
call, so there is no cross-tree pollution, but the per-call cost is O(N²) in chain depth.

## Fix

Replace the `Array` stack with a `Set` (or use `compare_by_identity` on a `Set` already
used nearby in `to_dep_map`):

```ruby
# AFTER — O(N) total: Set#include? is O(1) amortised
def digest(finder, stack = Set.new.compare_by_identity)
  ActiveSupport::Digest.hexdigest("#{template.source}-#{dependency_digest(finder, stack)}")
end

def dependency_digest(finder, stack)
  children.map do |node|
    if stack.include?(node)          # O(1) identity check
      false
    else
      finder.digest_cache[node.name] ||= begin
                                           stack.add(node)
                                           node.digest(finder, stack).tap { stack.delete(node) }
                                         end
    end
  end.join("-")
end
```

`Set#compare_by_identity` matches the existing `to_dep_map(seen = Set.new.compare_by_identity)`
pattern in the same file (line 110), ensuring object identity is used for cycle detection
(consistent with the original `Array#include?` behaviour which also uses `==` identity for
`Node` objects with no custom `==`).

## Speedup

| Chain depth N | Before (ops) | After (ops) | Speedup |
|--------------|-------------|------------|---------|
| 10 | 45 | 10 | 4.5× |
| 50 | 1,225 | 50 | 24.5× |
| 100 | 4,950 | 100 | 49.5× |
| 500 | 124,750 | 500 | 249.5× |
| 1,000 | 499,500 | 1,000 | 499.5× |

Template dependency chains of depth 50–100 are realistic in large Rails applications with
nested layouts, shared partials, and component hierarchies. At depth 500 (possible in
generated or framework-heavy view hierarchies) this is a 249× regression.