# UNDF: UNDF-2026-000000362
# chef-0001 — O(N²) run list dedup via Array#include?

**Severity:** MEDIUM
**Complexity:** O(N²) → O(N)
**CWE:** CWE-407 (Algorithmic Complexity)

## Affected Files

| File | Lines | Notes |
|------|-------|-------|
| `lib/chef/run_list.rb` | 65 | `RunList#<<`: dedup guard via Array#include? |
| `lib/chef/run_list/versioned_recipe_list.rb` | 39 | `VersionedRecipeList#add_recipe`: same pattern |

## Defective Code

### `lib/chef/run_list.rb` line 65

```ruby
def <<(run_list_item)
  run_list_item = coerce_to_run_list_item(run_list_item)
  @run_list_items << run_list_item unless @run_list_items.include?(run_list_item)  # O(N) scan
  self
end
```

### `lib/chef/run_list/versioned_recipe_list.rb` line 39

```ruby
def add_recipe(name, version = nil)
  # ...version conflict check...
  self << name unless include?(name)  # include? delegates to Array#include? — O(N)
end
```

`VersionedRecipeList` inherits from `Array`. Its `include?` method is `Array#include?`,
which is an O(N) linear scan. `add_recipe` is called once per recipe during run list
expansion; for a run list of R recipes, total cost is O(R²).

## Why It Is O(N²)

`RunList#<<` is the append operator used to build `@run_list_items`. It guards against
duplicates with `@run_list_items.include?(run_list_item)`. `@run_list_items` is a plain
`Array`; `Array#include?` scans from index 0 to N−1 — O(N) per call.

Building a run list of N items via N `<<` calls costs:
- 1st call: scan 0 elements — O(0)
- 2nd call: scan 1 element  — O(1)
- ...
- Nth call: scan N−1 elements — O(N−1)

Total: 0 + 1 + … + (N−1) = N(N−1)/2 = **O(N²)**.

`VersionedRecipeList#add_recipe` is the hot path during run list expansion: every role
expansion calls it for each recipe. A cookbook run involving R recipes across multiple
roles incurs R(R−1)/2 comparisons in total.

## Impact

A node with 500 recipes in its expanded run list (common in large Chef organizations
with many roles and nested roles) triggers ~125,000 string comparisons just for
deduplication. At 1000 recipes: ~500,000 comparisons. This adds measurable overhead to
every Chef client run during the compile phase.

## Fixed Code

### `lib/chef/run_list.rb` — add a shadow `Set` for O(1) membership tests

```ruby
def initialize(*run_list_items)
  @run_list_items = []
  @run_list_set   = Set.new  # shadow set for O(1) include? checks
  run_list_items.map { |i| self << coerce_to_run_list_item(i) }
end

def <<(run_list_item)
  run_list_item = coerce_to_run_list_item(run_list_item)
  unless @run_list_set.include?(run_list_item)
    @run_list_items << run_list_item
    @run_list_set   << run_list_item
  end
  self
end
```

### `lib/chef/run_list/versioned_recipe_list.rb` — replace Array with Set-backed dedup

```ruby
class VersionedRecipeList < Array
  def initialize
    super
    @versions  = {}
    @seen_names = Set.new  # O(1) membership instead of Array#include?
  end

  def add_recipe(name, version = nil)
    if version && @versions.key?(name)
      unless Chef::Version.new(@versions[name]) == Chef::Version.new(version)
        raise Chef::Exceptions::CookbookVersionConflict, "..."
      end
    end
    @versions[name] = version if version
    unless @seen_names.include?(name)
      @seen_names << name
      self << name
    end
  end
end
```

Both fixes reduce duplication-checking from O(N²) to O(N) while preserving insertion order
(required for deterministic run list execution).

## Speedup

At N=500 unique recipes: ~125,000 comparisons (slow) vs ~500 comparisons (fast) → **≥250×**.
At N=1000: ~500,000 vs ~1000 → **≥500×**.