# UNDF: UNDF-2026-000000671
# UNDF: (pending)
# typescript-0005: hasBaseType — O(2^D) diamond interface/class hierarchy re-traversal

## CWE-407 — Algorithmic Complexity: O(2^D) recursive diamond re-traversal

| Field | Value |
|-------|-------|
| ID | typescript-0005 |
| Severity | HIGH |
| Ecosystem | typescript |
| Package | `typescript` (compiler internals) |
| File | `src/compiler/checker.ts` |
| Lines | 13029–13041 |
| Complexity | O(2^D) on diamond interface/class hierarchies |
| Hot path | Type assignability checking (`isTypeDerivedFrom` → `hasBaseType`) |

## Background

`hasBaseType(type, checkBase)` tests whether `checkBase` appears anywhere in the
transitive base-type hierarchy of `type`.  It recurses through `getBaseTypes(target)`
with an inner `check` closure that carries **no visited set**.

TypeScript interfaces support multiple inheritance:

```typescript
interface A {}
interface B extends A {}
interface C extends A {}
interface D extends B, C {}  // diamond: A reachable via B and via C
```

For such a diamond at depth D, `check` re-visits every shared ancestor exponentially.

## Defect

```typescript
// src/compiler/checker.ts  lines 13029-13041
function hasBaseType(type: Type, checkBase: Type | undefined) {
    return check(type);
    function check(type: Type): boolean {
        if (getObjectFlags(type) & (ObjectFlags.ClassOrInterface | ObjectFlags.Reference)) {
            const target = getTargetType(type) as InterfaceType;
            return target === checkBase || some(getBaseTypes(target), check);
            //                             ^^^ DEFECT: no visited guard — re-enters
            //                             shared ancestors exponentially on diamond hierarchies
        }
        else if (type.flags & TypeFlags.Intersection) {
            return some((type as IntersectionType).types, check);
            //          ^^^ same issue for intersection types
        }
        return false;
    }
}
```

`some(getBaseTypes(target), check)` calls `check` on every direct base type.
If two branches both reach a shared ancestor, that ancestor's entire subtree is
traversed again.  No memoisation prevents this.

### Call sites (hot paths)

```
isTypeDerivedFrom()      → hasBaseType()   (type assignability; called in isRelatedTo)
resolveBaseTypesOfInterface() → hasBaseType()
getBaseTypeNodeOfClass()      → hasBaseType()
checkAccessOfProtectedMember  → hasBaseType()
```

`isTypeDerivedFrom` is called from the core type-relation machinery for every
assignability check involving class/interface types.

## Complexity table

| Diamond depth D | `check` calls (before fix) | `check` calls (after fix) | Speedup |
|-----------------|---------------------------|--------------------------|---------|
| 1 | 2 | 2 | 1× |
| 5 | 31 | 5 | 6× |
| 10 | 1,023 | 10 | 102× |
| 15 | 32,767 | 15 | 2,185× |
| 20 | 1,048,575 | 20 | 52,429× |

## Fix

Add a `visited` Set to the outer function and guard with `has()` before recursing:

```typescript
function hasBaseType(type: Type, checkBase: Type | undefined) {
    const visited = new Set<Type>();   // FIX: per-call visited set
    return check(type);
    function check(type: Type): boolean {
        if (getObjectFlags(type) & (ObjectFlags.ClassOrInterface | ObjectFlags.Reference)) {
            const target = getTargetType(type) as InterfaceType;
            if (target === checkBase) return true;
            if (visited.has(target)) return false;   // FIX: guard
            visited.add(target);
            return some(getBaseTypes(target), check);
        }
        else if (type.flags & TypeFlags.Intersection) {
            return some((type as IntersectionType).types, check);
        }
        return false;
    }
}
```

The `visited` set is allocated once per `hasBaseType` call and shared across the
entire recursive descent.  `Set.has()` / `Set.add()` are O(1) amortised.

## Notes

- `getBaseTypes(target)` is already memoised via `target.resolvedBaseTypes`; the
  defect is purely in the recursive descent of `check`, not in type-set resolution.
- Intersection branches do not themselves recurse into `getBaseTypes` and so are
  bounded by the width of the intersection, not exponential; however they benefit
  from the same visited guard when the intersection members are shared.
- TypeScript's structural type system does permit arbitrarily deep diamond interface
  hierarchies in user code; library authors composing mixins can easily reach D≥10.
