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:

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:

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.

/* 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)

2.6 KiB Raw Permalink Blame History Unescape Escape