russell@unturf.com 3986d8dc50 diamond hunt: godot-0009/0010 + meson-0002 + typeorm-0004/0005 + ts-0003; count 629→635

New diamond recursion defects (O(2^D) → O(N)):
- godot-0009: Font::_is_cyclic no visited set — CJK fallback diamond, 2648x at F=4,D=8
- godot-0010: Font::_update_rids_fb no visited set — duplicate RIDs + O(N^2) hot path
- meson-0002: get_internal_static_libraries_recurse link_whole guard missing — 132x at D=10
- typescript-0003: hasBaseType inner check() no visited set — 1024x at D=10; hot on instanceof

New O(N²) defects:
- typeorm-0004: SubjectTopologicalSorter Array.indexOf dedup — 200x at N=400
- typeorm-0005: DepGraph.createDFS result.indexOf + addDependency edge dedup — 300x at N=600

CLEAN confirmed (diamond recursion sweep): bazel, cargo, cmake, composer, dgl, diesel,
doctrine-orm, efcore, helm, mybatis, networkx-deeper, ninja, npm-arborist, peewee, pip,
rubygems, seaorm, sqlalchemy, swift

UNDF: 571→578 assigned; MOAD count: 629→635

2026-03-29 16:52:04 -04:00

4.3 KiB

Raw Permalink Blame History

UNDF: UNDF-2026-000000405

godot-0010 — Font::_update_rids_fb O(N^2) diamond re-traversal → O(N) with visited set

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

The Defect

Font::_update_rids_fb collects RIDs (font renderer handles) from a font and all its fallbacks, recursively. It carries no visited set:

void Font::_update_rids_fb(const Font *p_f, int p_depth) const {
    ERR_FAIL_COND(p_depth > MAX_FALLBACK_DEPTH);
    if (p_f != nullptr) {
        RID rid = p_f->_get_rid();
        if (rid.is_valid()) {
            rids.push_back(rid);
        }
        const TypedArray<Font> &_fallbacks = p_f->get_fallbacks();
        for (int i = 0; i < _fallbacks.size(); i++) {
            Ref<Font> fb_font = _fallbacks[i];
            _update_rids_fb(fb_font.ptr(), p_depth + 1);  // ← no visited set
        }
    }
}

Called from Font::_update_rids() which is called lazily on every render operation: get_rids(), get_height(), get_ascent(), get_descent(), get_underline_position(), get_underline_thickness(), etc.

Diamond Topology — Duplicate RIDs and O(N^2) Traversal

In a diamond fallback graph:

         A (this)
        / \
       B   C       ← both have D as fallback (shared CJK font)
        \ /
         D

Traversal from A:

A → B → D (D.rid added once)
A → C → D (D.rid added AGAIN — duplicate!)

The rids array now contains D's RID twice. This causes:

Correctness defect: glyph lookup iterates rids in order; duplicate entries cause the same font to be queried twice per glyph, wasting rendering work.
Performance defect: O(N^2) traversal with F fallbacks sharing K common fonts. With P paths through a diamond of depth D: O(P × K) total work instead of O(N).

With a large internationalized font stack (Japanese + Chinese + Korean all falling back to NotoSansCJK), rids could contain tens of duplicate entries. Since _update_rids is called on every text measurement and render, this is a hot-path defect.

Call Frequency

_update_rids is marked dirty_rids = true in _invalidate_rids(), which is called:

set_fallbacks — on every font configuration change
emit_changed — propagated to all fonts that reference this one as a fallback

This means in a deeply connected font graph, a single fallback change triggers cascading _update_rids calls across all dependent fonts, each with O(N^2) traversal.

The Fix

Add a HashSet<const Font *> *r_visited parameter to _update_rids_fb and pass it from _update_rids:

void Font::_update_rids_fb(const Font *p_f, int p_depth,
                            HashSet<const Font *> *r_visited) const {
    ERR_FAIL_COND(p_depth > MAX_FALLBACK_DEPTH);
    if (p_f == nullptr) { return; }
    if (r_visited != nullptr && r_visited->has(p_f)) {
        return; // already collected; skip duplicates
    }
    if (r_visited != nullptr) { r_visited->insert(p_f); }
    RID rid = p_f->_get_rid();
    if (rid.is_valid()) { rids.push_back(rid); }
    const TypedArray<Font> &_fallbacks = p_f->get_fallbacks();
    for (int i = 0; i < _fallbacks.size(); i++) {
        Ref<Font> fb_font = _fallbacks[i];
        _update_rids_fb(fb_font.ptr(), p_depth + 1, r_visited);
    }
}

void Font::_update_rids() const {
    rids.clear();
    HashSet<const Font *> visited;
    _update_rids_fb(this, 0, &visited);
    dirty_rids = false;
}

After fix:

Each font visited at most once: O(N) total traversal
rids[] contains each font RID exactly once (correct behavior)
Subclasses FontVariation::_update_rids() and SystemFont::_update_rids() call _update_rids_fb directly — they need the same fix (see patch for full diff)

Complexity

Topology	Before	After
Linear (F=1, D=10)	O(10)	O(10)
Diamond (2 shared fonts, D=4)	O(2×4)=8, but D duplicates	O(N)=6
Full CJK stack (3 lang fonts, 1 shared CJK)	O(3×K) RID entries	O(K+3)

Speedup: 3-100x depending on diamond depth; correctness fix eliminates duplicate RIDs.

Unit Test

See defects/godot/unit/GodotFontUpdateRidsTest.java

4.3 KiB Raw Permalink Blame History Unescape Escape