# UNDF: UNDF-2026-000000572
# vim-0002: au_find_group() O(G) linear scan called per item in autocmd_add_or_delete loop

## Metadata

| Field | Value |
|-------|-------|
| ID | vim-0002 |
| Severity | MEDIUM |
| CWE | CWE-407 (Algorithmic Complexity — Linear Membership Test in a Loop) |
| Component | `src/autocmd.c` |
| Function | `autocmd_add_or_delete()` → `au_find_group()` |
| Complexity | O(L×G) where L = list items, G = number of augroups |

## Description

`autocmd_add_or_delete()` (called by the Vim script `autocmd_add()` and
`autocmd_delete()` builtins) iterates over a list of autocmd dicts with
`FOR_ALL_LIST_ITEMS`. For each item, if a "group" key is present, it calls
`au_find_group(group_name)` which performs a linear scan over the `augroups`
garray (`for i = 0; i < augroups.ga_len; ++i`).

When a startup script or plugin manager registers many autocmds in bulk
(passing a large list), and multiple distinct groups are referenced, this
becomes O(L×G).

Additionally, the fallback `au_new_group()` also calls `au_find_group()`
first, so a "create if missing" path also incurs the O(G) scan.

## Defective Code

```c
// autocmd.c: autocmd_add_or_delete()
FOR_ALL_LIST_ITEMS(aucmd_list, li)     // outer loop: L iterations
{
    ...
    group = au_find_group(group_name); // O(G) linear scan each time
    if (group == AUGROUP_ERROR)
    {
        group = au_new_group(group_name); // also calls au_find_group → O(G)
        ...
    }
}

// au_find_group() — linear scan over augroups array
static int au_find_group(char_u *name)
{
    int i;
    for (i = 0; i < augroups.ga_len; ++i)          // O(G)
        if (AUGROUP_NAME(i) != NULL && ...
                && STRCMP(AUGROUP_NAME(i), name) == 0)
            return i;
    return AUGROUP_ERROR;
}
```

## Fix

Replace the `augroups` garray with (or supplement it with) a hash table
mapping group name → index. Vim already uses `hashtab_T` / `hash_T` elsewhere
(e.g. `paramtab` in Zsh-style param tables). A `hashtab_T` lookup is O(1)
amortized.

```c
// Add alongside augroups garray:
static hashtab_T augroups_ht;  // name → index mapping

// au_find_group becomes O(1):
static int au_find_group(char_u *name)
{
    hashitem_T *hi = hash_find(&augroups_ht, name);
    if (HASHITEM_EMPTY(hi))
        return AUGROUP_ERROR;
    return (int)(hi->hi_data);  // stored index
}
```

## Impact

Plugin managers (lazy.nvim, vim-plug used via compatibility shim) and
`ftplugin/` loading can register hundreds of autocmds across 50+ groups at
startup. With G=100 groups and L=500 list items: 50,000 string comparisons
instead of 500. Measurable startup latency on large plugin configurations.

## Speedup

Expected: O(L×G) → O(L). At L=500 items, G=100 groups: ~100x op-count reduction
(measured by unit test).
