# UNDF: UNDF-2026-000000404
# godot-0009 — Font::_is_cyclic O(F^D) diamond re-traversal → O(N) with visited set

**Project:** Godot Engine
**File:** `scene/resources/font.cpp`, `scene/resources/font.h`
**Function:** `Font::_is_cyclic(const Ref<Font> &p_f, int p_depth)`
**Severity:** HIGH
**CWE:** CWE-407 (Algorithmic Complexity)
**Also affects:** Redot Engine (Godot fork, identical code)

## The Defect

`Font::_is_cyclic` recurses through the font fallback graph to check whether adding a
font would create a cycle. It takes no visited set:

```cpp
bool Font::_is_cyclic(const Ref<Font> &p_f, int p_depth) const {
    ERR_FAIL_COND_V(p_depth > MAX_FALLBACK_DEPTH, true);
    if (p_f.is_null())  { return false; }
    if (p_f == this)    { return true; }
    for (int i = 0; i < p_f->fallbacks.size(); i++) {
        const Ref<Font> &f = p_f->fallbacks[i];
        if (_is_cyclic(f, p_depth + 1)) { return true; }  // ← no visited set
    }
    return false;
}
```

Called from `Font::set_fallbacks`:

```cpp
void Font::set_fallbacks(const TypedArray<Font> &p_fallbacks) {
    for (int i = 0; i < p_fallbacks.size(); i++) {
        const Ref<Font> &f = p_fallbacks[i];
        ERR_FAIL_COND_MSG(_is_cyclic(f, 0), "Cyclic font fallback.");  // ← F calls, each O(F^D)
    }
    ...
}
```

### Diamond Topology — Exponential Re-traversal

Consider a diamond font fallback graph (common in internationalization setups):

```
          A (this font)
         / \
        B   C           ← B and C both reference D (shared CJK fallback)
         \ /
          D
```

When calling `_is_cyclic(B, 0)`:
- visits B → visits D (1 traversal of D)
When calling `_is_cyclic(C, 0)`:
- visits C → visits D (1 more traversal of D — redundant)

With F fallbacks at each level, depth D, and `MAX_FALLBACK_DEPTH = 64`:
- **Complexity: O(F^D)** — exponential in depth
- A diamond of depth 10 with 2 fallbacks per node: 2^10 = 1024 traversals instead of 10

### Real-World Impact

International font stacks routinely have shared CJK fallback fonts referenced by
multiple language-specific fonts (e.g., NotoSansCJK referenced by NotoSansJapanese,
NotoSansChinese, NotoSansKorean). `set_fallbacks` is called from the editor and from
`_update_exports` when font resources change. With a deep diamond topology, this
call becomes catastrophically slow.

## The Fix

Add an internal helper that passes a `HashSet<const Font *>` visited set:

```cpp
bool Font::_is_cyclic(const Ref<Font> &p_f, int p_depth) const {
    HashSet<const Font *> visited;
    return _is_cyclic_internal(p_f, p_depth, visited);
}

bool Font::_is_cyclic_internal(const Ref<Font> &p_f, int p_depth,
                                HashSet<const Font *> &r_visited) const {
    ERR_FAIL_COND_V(p_depth > MAX_FALLBACK_DEPTH, true);
    if (p_f.is_null()) { return false; }
    if (p_f == this)   { return true; }
    const Font *raw = p_f.ptr();
    if (r_visited.has(raw)) { return false; }  // already checked, skip
    r_visited.insert(raw);
    for (int i = 0; i < p_f->fallbacks.size(); i++) {
        const Ref<Font> &f = p_f->fallbacks[i];
        if (_is_cyclic_internal(f, p_depth + 1, r_visited)) { return true; }
    }
    return false;
}
```

**After fix:** O(N) where N = total unique fonts in the fallback graph.

## Complexity

| Topology | Before | After |
|----------|--------|-------|
| Linear (F=1, D=10) | O(10) | O(10) |
| Diamond (F=2, D=10, shared leaves) | O(2^10) = 1024 | O(10+shared) ≈ O(N) |
| Full diamond (F=4, D=8, shared subtrees) | O(4^8) = 65536 | O(N) |

**Speedup at D=10, F=2 diamond:** ~100x
**Speedup at D=8, F=4 diamond:** ~6500x

## Unit Test

See `defects/godot/unit/GodotFontCyclicTest.java`
