# UNDF: UNDF-2026-000000370
# crystal-0002: type_merge add_type — O(N) includes? inside O(N) compact_types loop

## Severity: HIGH

## Location
- `src/compiler/crystal/semantic/type_merge.cr:87,100`
- Called from: `compact_types` at line 73, `type_merge` at lines 16,33,60

## Description
`add_type` deduplicates types into a growing array using `Array#includes?` — an O(N)
linear scan on every insertion. `compact_types` calls `add_type` for every type in the
input collection, making `compact_types` O(N²). `type_merge` is called for every union
type computation during type inference — one of the hottest paths in the Crystal compiler.

**Complexity:** O(N²) where N = number of distinct types in the union being built.
For programs with large union types (error hierarchies, protocol implementations), this
is a significant compilation bottleneck.

## Root Cause
```crystal
# type_merge.cr:99-101
def add_type(types, type : Type)
  types << type unless types.includes? type   # O(N) scan every time
end

# type_merge.cr:71-75
def compact_types(objects, &) : Array(Type)
  all_types = Array(Type).new(objects.size)
  objects.each { |obj| add_type all_types, yield(obj) }   # O(N) add_type for each
  all_types.reject! &.no_return? if all_types.size > 1
  all_types
end
```

## Fix
Use a `Set(Type)` for dedup tracking alongside the ordered array:

```crystal
def compact_types(objects, &) : Array(Type)
  seen = Set(Type).new
  all_types = [] of Type
  objects.each do |obj|
    type = yield obj
    add_type(all_types, seen, type) if type
  end
  all_types.reject! &.no_return? if all_types.size > 1
  all_types
end

def add_type(types, seen, type : Type)
  unless seen.includes?(type)
    seen.add(type)
    types << type
  end
end
```

## Impact
Large union types in Crystal (e.g., deeply nested error hierarchies, union of many
struct types) cause O(N²) type inference time. Hits every branch of type inference that
produces union types — essentially the entire compilation of non-trivial programs.
