# UNDF: UNDF-2026-000000712
# ruby-0003: RubyGems Gem::Specification#dependent_gems — O(N²×D) nested scan

## Severity: MEDIUM

## Location
- `lib/rubygems/specification.rb:1746` — `def dependent_gems(check_dev = true)`
- `lib/rubygems/specification.rb:1748` — `Gem::Specification.each do |spec|`
- `lib/rubygems/specification.rb:1752` — `find_all_satisfiers(dep) do |sat|`
- `lib/rubygems/specification.rb:1872` — `def find_all_satisfiers(dep)`
- `lib/rubygems/specification.rb:1873` — `Gem::Specification.each do |spec|`

## Description

`Gem::Specification#dependent_gems` computes which installed specs depend on
`self`. It does this with two nested `Gem::Specification.each` loops:

```ruby
# specification.rb:1746-1759
def dependent_gems(check_dev = true)
  out = []
  Gem::Specification.each do |spec|          # O(N) outer scan
    deps = check_dev ? spec.dependencies : spec.runtime_dependencies
    deps.each do |dep|
      next unless satisfies_requirement?(dep)
      sats = []
      find_all_satisfiers(dep) do |sat|      # O(N) inner scan per dep
        sats << sat
      end
      out << [spec, dep, sats]
    end
  end
  out
end

def find_all_satisfiers(dep)
  Gem::Specification.each do |spec|          # O(N) full scan
    yield spec if spec.satisfies_requirement? dep
  end
end
```

For N installed gems, each with D dependencies:
- Outer loop: O(N)
- For each spec's D deps: `find_all_satisfiers` runs a full O(N) scan
- **Total: O(N × D × N) = O(N² × D)**

`dependent_gems` is called from `Gem::Uninstaller#ask_if_ok` during
`gem uninstall` to warn about broken dependencies. For large gem environments
(Ruby on Rails applications, CI servers, rbenv setups with 300–800 installed
gems), this triggers hundreds of thousands of comparisons.

## Root Cause

`find_all_satisfiers` scans ALL specs linearly to find which ones satisfy a
given dependency requirement. There is no reverse index from gem name → specs,
so each `satisfies_requirement?` check performs a full scan.

## Fix

Build a reverse index once: map `gem_name → [spec, ...]`. Since
`satisfies_requirement?` checks the gem name first (version check is secondary),
the index reduces `find_all_satisfiers` from O(N) to O(matching_name_count).
`dependent_gems` itself avoids the inner `find_all_satisfiers` loop:

```diff
--- a/lib/rubygems/specification.rb
+++ b/lib/rubygems/specification.rb
@@ -1746,18 +1746,20 @@ class Gem::Specification
   def dependent_gems(check_dev = true)
     out = []
-    Gem::Specification.each do |spec|
-      deps = check_dev ? spec.dependencies : spec.runtime_dependencies
-      deps.each do |dep|
-        next unless satisfies_requirement?(dep)
-        sats = []
-        find_all_satisfiers(dep) do |sat|
-          sats << sat
-        end
-        out << [spec, dep, sats]
+    # Build a reverse index: gem_name -> [specs that provide it]
+    name_index = Hash.new { |h, k| h[k] = [] }
+    Gem::Specification.each { |s| name_index[s.name] << s }
+
+    Gem::Specification.each do |spec|
+      deps = check_dev ? spec.dependencies : spec.runtime_dependencies
+      deps.each do |dep|
+        next unless satisfies_requirement?(dep)
+        # Only check specs with the right name — O(matches) not O(N)
+        sats = name_index[dep.name].select { |s| s.satisfies_requirement?(dep) }
+        out << [spec, dep, sats]
       end
     end
     out
   end
```

## Complexity

N = installed gem count, D = avg dependencies per gem

| N    | Before (ops)  | After (ops)    | Ratio  |
|------|---------------|----------------|--------|
| 100  | ~5,000        | ~200           | 25×    |
| 300  | ~45,000       | ~600           | 75×    |
| 800  | ~320,000      | ~1,600         | 200×   |

Assumptions: D=5 deps/gem, avg 1 satisfier per dep (same gem name, single version).

## Impact

`gem uninstall <gem>` → `ask_if_ok` → `dependent_gems`:
- Development machines with rbenv/rvm typically have 200–500 gems installed
- CI servers running bundler-audit or bundle exec gem commands: 300–800 gems
- With 500 gems and D=5 deps, the fix reduces ~1.25M comparisons to ~2,500

The `find_all_satisfiers` private method should also be updated to use the index
for consistency, though it is primarily used through `dependent_gems`.