# UNDF: UNDF-2026-000000372
# crystal-0004: add_to_including_types — O(N²) Array#includes? in module instantiation loop

## Severity: MEDIUM

## Location
- `src/compiler/crystal/types.cr:3568,3581` — `add_to_including_types` private helpers
- `src/compiler/crystal/types.cr:1164-1170` — `NonGenericModuleType#add_to_including_types`
- Called from: `including_types` method at lines 1154, 2220 during type union computation

## Description
`add_to_including_types` builds an `Array(Type)` representing the set of all concrete
types that include a given module. For each type to add, it calls `all_types.includes?(instance)`
— an O(N) linear scan — before appending. The outer loop iterates over all instantiated
types of a generic module, making the total cost O(N²) where N = number of instantiated
types for the module.

`including_types` is called during `program.type_merge_union_of(all_types)` which runs
during type inference for every expression whose type involves a module-based union. In
programs with heavily-instantiated generic modules (e.g. `Comparable`, `Enumerable`,
`Iterable`), this function is called many times with growing `all_types` arrays.

## Root Cause
```crystal
# types.cr:3560-3581
private def add_to_including_types(type : Crystal::GenericType, all_types)
  type.each_instantiated_type do |instance|
    next if instance.unbound?
    next if instance.abstract?
    all_types << instance unless all_types.includes?(instance)  # O(N) per insertion
  end
  type.subclasses.each do |subclass|
    add_to_including_types subclass, all_types
  end
end

private def add_to_including_types(type, all_types)
  virtual_type = type.virtual_type
  all_types << virtual_type unless all_types.includes?(virtual_type)  # O(N) per insertion
end
```

`all_types` is an `Array(Type)` (line 1156: `Array(Type).new`). `Array#includes?` scans
the array linearly. The function inserts up to M types, each requiring O(M) scan → O(M²).
For modules with many generic instantiations, M grows with program size.

## Fix
Track seen types in a `Set(Type)` alongside the array. Since `Type` instances are
identity-compared (pointer equality), `Set(Type)` provides O(1) membership:

```crystal
# NonGenericModuleType#including_types (types.cr:1154)
def including_types
  if including_types = @including_types
    all_types = Array(Type).new(including_types.size)
    seen = Set(Type).new
    add_to_including_types(all_types, seen)
    program.type_merge_union_of(all_types)
  else
    nil
  end
end
```

Pass `seen` through `add_to_including_types` and use `seen.includes?` (O(1)) instead
of `all_types.includes?` (O(N)).

## Complexity
| | Before | After |
|---|---|---|
| add_to_including_types (M types) | O(M²) | O(M) |
| including_types | O(M²) | O(M) |

## Impact
For a generic module like `Comparable` instantiated by 100 types, building `all_types`
costs 100 + 99 + ... + 1 = 5,050 comparisons today versus 100 set insertions with the fix.
At 500 instantiations: 125,000 comparisons vs 500 insertions.
