# UNDF: UNDF-2026-000000388
# emacs-0001: Ffontset_info Fmember dedup O(R×F×N) — MEDIUM

## Summary

`Ffontset_info` in `src/fontset.c` accumulates opened font names per font-spec slot using
`Fmember` for deduplication inside a triple-nested loop.  The name list (`XCDR(slot)`) grows
as names are appended, so each check scans a list that grows over the course of the outer loop.

## Location

`src/fontset.c` — function `Ffontset_info` (DEFUN `fontset-info`)

## Defect Pattern

```c
/* Outer loops: for k ∈ {0,1}; for c over char ranges; for i over realized fontsets R */
for (i = 0; ! NILP (realized[k][i]); i++) {
    …
    for (j = 0; j < ASIZE (val); j++) {      /* F font entries */
        …
        slot = Fassq (RFONT_DEF_SPEC (elt), alist);         /* O(A) */
        name = AREF (font_object, FONT_NAME_INDEX);
        if (NILP (Fmember (name, XCDR (slot))))             /* O(N) — N grows */
            nconc2 (slot, list1 (name));                     /* list grows here */
    }
}
```

- `R` = number of realized fontsets on the frame (one per face that has been realized)
- `F` = font entries per character range slot
- `A` = number of distinct font-specs in the base fontset (= length of `alist`)
- `N` = names accumulated in each alist slot so far (grows up to `R×F`)

Total work: **O(R × F × (A + N))** ≈ **O(R² × F²)** in worst case as N → R×F.

## Severity

**MEDIUM** — `fontset-info` is a diagnostic/interactive function, not a hot render path.
However, a frame with many realized faces (e.g. in a large mixed-script document) can trigger
this during `describe-fontset` or `fontset-info` calls, causing multi-second stalls with
200+ realized fontsets.

## Complexity

| Scenario | N realized fontsets | Op count |
|---|---|---|
| Typical desktop | 20 | ~400 |
| Large CJK document | 200 | ~40 000 |
| Stress (1000 fontsets) | 1000 | ~1 000 000 |

Ratio at N=1000: **~2500×** vs O(R) baseline.

## Fix

Replace the `Fmember` list with a hash table (`make-hash-table`) keyed on font name symbol.

```c
/* Before: O(N) per check, N grows */
if (NILP (Fmember (name, XCDR (slot))))
    nconc2 (slot, list1 (name));

/* After: O(1) amortized — use a side hash table for dedup */
/* Build Lisp hash table alongside alist, keyed on name */
if (NILP (Fgethash (name, name_seen_ht, Qnil))) {
    Fputhash (name, Qt, name_seen_ht);
    nconc2 (slot, list1 (name));
}
```

Or simply sort-and-deduplicate after the loop (acceptable for a diagnostic function).

## References

- `src/fontset.c` lines 1960–2005 (Ffontset_info inner loops)
- CWE-407: Inefficient Algorithmic Complexity
