# UNDF: UNDF-2026-000000369
# crystal-0001: collect_ancestors / lookup_defs O(2^D) diamond module traversal

## Metadata

| Field | Value |
|-------|-------|
| ID | crystal-0001 |
| Ecosystem | Crystal |
| Repo | https://github.com/crystal-lang/crystal |
| File | `src/compiler/crystal/types.cr` |
| Function | `collect_ancestors`, `lookup_defs`, `include` (cycle-check path) |
| CWE | CWE-407 (Inefficient Algorithmic Complexity) |
| Severity | MEDIUM |
| Complexity | O(2^D) where D = diamond nesting depth |
| Speedup | ~32x at D=5 nested diamonds (32 vs 1 unique module traversals) |

## Summary

The Crystal compiler's `Type#collect_ancestors` method (and `lookup_defs` which
recursively walks `parents`) contains no visited-type guard. When modules form a
diamond-shaped inclusion hierarchy, shared ancestors are traversed once per path
that leads to them, producing O(2^D) work for D levels of nested diamonds.

## Vulnerable Code

**`src/compiler/crystal/types.cr`, lines 384–394:**

```crystal
def ancestors
  ancestors = [] of Type
  collect_ancestors(ancestors)
  ancestors
end

protected def collect_ancestors(ancestors)
  parents.try &.each do |parent|
    ancestors << parent
    parent.collect_ancestors(ancestors)  # no visited set — recurses into shared modules multiple times
  end
end
```

**`src/compiler/crystal/types.cr`, lines 408–433 (`lookup_defs`):**

```crystal
def lookup_defs(name : String, all_defs : Array(Def), lookup_ancestors_for_new : Bool? = false)
  self.defs.try &.[name]?.try &.each do |item|
    all_defs << item.def unless all_defs.find(&.same?(item.def))  # O(N) linear dedup
  end
  # ...
  my_parents.try &.each do |parent|
    parent.lookup_defs(name, all_defs, lookup_ancestors_for_new)  # no visited set
  end
end
```

## Diamond Scenario

```crystal
module M; def foo; end; end
module A; include M; end   # A.parents = [M]
module B; include M; end   # B.parents = [M]
class C; include A; include B; end  # C.parents = [A, B] — M not directly in C.parents
```

- `C.parents = [A, B]`
- `C.collect_ancestors` → visits A → visits M (1st), visits B → visits M (2nd)
- `C.lookup_defs("foo")` → recurses A → recurses M (1st), recurses B → recurses M (2nd)

With D nested diamond levels:

```
module M0; def foo; end; end
module M1a; include M0; end; module M1b; include M0; end
module M2a; include M1a; include M1b; end
module M2b; include M1a; include M1b; end
class C; include M2a; include M2b; end
```

This causes 2^D traversals of M0's `lookup_defs` and `collect_ancestors`.

## Hot Paths Affected

`ancestors` (via `collect_ancestors`) is called in:
- `Type#include` (cycle detection) — called for every `include` at compile time
- `AbstractDefChecker#implements_with_ancestors?` — called for every abstract method
- `TypeDeclarationProcessor` — called 4× per type per compilation pass
- `call.cr`, `new.cr`, doc generator — all rebuild the list from scratch each call

`lookup_defs` is called for every method lookup that needs to collect all overloads.

## Fix

Add a `Set(UInt64)` (keyed on `object_id`) to `collect_ancestors` and a visited
set passed through `lookup_defs` to skip already-visited types:

```crystal
def ancestors
  ancestors = [] of Type
  visited = Set(UInt64).new
  collect_ancestors(ancestors, visited)
  ancestors
end

protected def collect_ancestors(ancestors, visited : Set(UInt64))
  parents.try &.each do |parent|
    next unless visited.add?(parent.object_id)
    ancestors << parent
    parent.collect_ancestors(ancestors, visited)
  end
end
```

For `lookup_defs`, pass a `visited : Set(UInt64)` parameter and skip types already
in the set before recursing into parents.

## Patch

```diff
--- a/src/compiler/crystal/types.cr
+++ b/src/compiler/crystal/types.cr
@@ -384,11 +384,14 @@ module Crystal
     def ancestors
       ancestors = [] of Type
-      collect_ancestors(ancestors)
+      visited = Set(UInt64).new
+      collect_ancestors(ancestors, visited)
       ancestors
     end

-    protected def collect_ancestors(ancestors)
+    protected def collect_ancestors(ancestors, visited : Set(UInt64))
       parents.try &.each do |parent|
-        ancestors << parent
-        parent.collect_ancestors(ancestors)
+        next unless visited.add?(parent.object_id)
+        ancestors << parent
+        parent.collect_ancestors(ancestors, visited)
       end
     end
@@ -408,15 +411,17 @@ module Crystal
-    def lookup_defs(name : String, all_defs : Array(Def), lookup_ancestors_for_new : Bool? = false)
+    def lookup_defs(name : String, all_defs : Array(Def), lookup_ancestors_for_new : Bool? = false,
+                    visited : Set(UInt64)? = nil)
       self.defs.try &.[name]?.try &.each do |item|
         all_defs << item.def unless all_defs.find(&.same?(item.def))
       end
       # ...
+      visited ||= Set(UInt64).new
       my_parents.try &.each do |parent|
-        parent.lookup_defs(name, all_defs, lookup_ancestors_for_new)
+        next unless visited.not_nil!.add?(parent.object_id)
+        parent.lookup_defs(name, all_defs, lookup_ancestors_for_new, visited)
       end
     end
```

## Benchmark

| Scenario | D=0 | D=1 | D=3 | D=5 |
|----------|-----|-----|-----|-----|
| collect_ancestors calls to M (unpatched) | 1 | 2 | 8 | 32 |
| collect_ancestors calls to M (patched) | 1 | 1 | 1 | 1 |
| Ratio | 1x | 2x | 8x | 32x |

At D=5 nested diamonds (a deep framework with shared mixins), compilation throughput
for type checking is degraded ~32× for ancestor-related operations.

## References

- CWE-407: Inefficient Algorithmic Complexity
- `src/compiler/crystal/types.cr` lines 384–434
- `src/compiler/crystal/semantic/type_declaration_processor.cr` lines 508, 582, 591, 614, 733
- `src/compiler/crystal/semantic/abstract_def_checker.cr` lines 94, 390
