# UNDF: UNDF-2026-000000549
# tcl-0001: DoImport O(C×P) export pattern scan per namespace import

## Classification
- **Severity:** MEDIUM
- **CWE:** CWE-407 (Inefficient Algorithmic Complexity)
- **Component:** `generic/tclNamesp.c`
- **Function:** `DoImport()`, `Tcl_Import()`

## Description

`Tcl_Import()` with a wildcard pattern (the common case: `namespace import ::ns::*`)
iterates over every command C in the source namespace's `cmdTable`:

```c
for (hPtr = Tcl_FirstHashEntry(&importNsPtr->cmdTable, &search);
        (hPtr != NULL); hPtr = Tcl_NextHashEntry(&search)) {
    char *cmdName = (char *) Tcl_GetHashKey(&importNsPtr->cmdTable, hPtr);
    if (Tcl_StringMatch(cmdName, simplePattern) &&
            DoImport(...) == TCL_ERROR) {
        return TCL_ERROR;
    }
}
```

For each matching command, `DoImport()` linearly scans P export patterns:

```c
static int DoImport(...) {
    Tcl_Size i = 0, exported = 0;
    while (!exported && (i < importNsPtr->numExportPatterns)) {
        exported |= Tcl_StringMatch(cmdName, importNsPtr->exportArrayPtr[i++]);
    }
    ...
}
```

**Total cost per `Tcl_Import` call: O(C × P)** where:
- C = number of commands in the source namespace
- P = number of export patterns (`namespace export` entries)

A namespace with C=1000 commands and P=50 export patterns costs 50,000
`Tcl_StringMatch` calls per import. In large Tcl applications (Tk itself,
Itcl, TclOO) with many namespaces and wildcard imports at startup, this
compounds significantly.

## Root Cause

The export pattern list `exportArrayPtr` is a plain C array (char**) with no
hash-indexed "exported command" cache. Every import re-checks every pattern for
every command.

## Fix

Cache the set of currently exported command names in a `Tcl_HashTable` on the
namespace struct, keyed by command name. Invalidate the cache whenever
`namespace export` changes. `DoImport` then does a single O(1) `Tcl_FindHashEntry`
instead of a P-deep linear scan.

```c
/* In Namespace struct, add: */
Tcl_HashTable *exportedCmds;  /* cache: exported cmd name → 1; NULL = stale */

/* In DoImport, replace the while loop with: */
if (importNsPtr->exportedCmds != NULL) {
    exported = (Tcl_FindHashEntry(importNsPtr->exportedCmds, cmdName) != NULL);
} else {
    /* rebuild cache then check */
    ...
}
```

## Overhead Measured

See unit test `TclDoImportAlgorithm.java`. At C=1000 commands, P=50 patterns:
- SLOW (linear pattern scan per command): ~50,000 operations
- FAST (hash lookup): ~1,000 operations
- Ratio: ~50x (grows linearly with P)

## Files

- `generic/tclNamesp.c` — `DoImport()`, `Tcl_Import()`, `Tcl_Export()`
  (export modification must invalidate cache)
