# UNDF: UNDF-2026-000000457
# make-0001: implicit.c pattern_search file->deps O(R×D×F) → O(R×D+F)

## Defect

- **File**: `src/implicit.c`
- **Function**: `pattern_search`
- **Lines**: ~796 (Savannah HEAD, 2025-03-27)
- **CWE**: 407 — Inefficient Algorithmic Complexity
- **Severity**: HIGH

## Pattern

```c
/* Outer: for (intermed_ok = 0; intermed_ok < 2; ++intermed_ok) */
/* Outer: for (ri = 0; ri < nrules; ri++)                        */
/*   Middle: while(1) / for (d = dl; d != 0; d = d->next)        */

                  if (df && df->is_target)
                    explicit = 1;
                  else
                    for (dp = file->deps; dp != 0; dp = dp->next)  /* O(F) */
                      if (streq (d->name, dep_name (dp)))           /* O(F) linear scan */
                        break;
```

## Complexity

- `R` = number of pattern rules (can be hundreds of built-in + user-defined rules)
- `D` = number of pattern prerequisites per rule (typically 1-5)
- `F` = number of explicit prerequisites of the current target file

For each target, `pattern_search` runs through R rules × D deps × F explicit deps.
The O(F) inner linear scan is performed for every `(rule, dep)` pair.

**Worst case**: target with F=100 deps and R=200 rules with D=5 deps each:
- Without fix: 200 × 5 × 100 = 100,000 string comparisons
- With fix: build hash set once from F deps (O(F)), then O(1) per lookup:
  200 × 5 × 1 = 1,000 lookups + 100 hash inserts = ~1,100 ops
- **Speedup**: ~91× at F=100, scales as O(F)

## Root Cause

The function `pattern_search` is the hot path called for every target that
needs an implicit rule.  In a project with many targets (e.g. a large
parallel make with hundreds of object files, each with many explicit
prerequisites), this inner loop fires F times per (rule, dep) combination.

`file->deps` is a linked list — no random access or hashing. The membership
test `streq(d->name, dep_name(dp))` scans the whole list every time.

## Fix

Build a `hash_set` (or a `struct hash_table` using GNU Make's `hashmap`
infrastructure) from `file->deps` **once** before the rule loop begins.
Replace the inner `for (dp = file->deps; ...)` linear scan with an O(1)
hash lookup.

```c
/* CWE-407 fix: build a set of explicit dep names once before the rule loop.
   The inner for(dp = file->deps; ...) scan was O(F) per (rule, dep) pair,
   giving O(R * D * F) total.  A hash set gives O(R * D + F). */
struct hash_table *dep_name_set = make_file_dep_name_set (file);

/* ... inside the rule/dep loops ... */

  if (df && df->is_target)
    explicit = 1;
  else
    dp = dep_name_set_contains (dep_name_set, d->name) ? (struct dep *)1 : 0;
```

GNU Make already uses `struct hash_table` (see `hash.h`) for file name
lookup (`hash_find_item`). The same infrastructure applies here.

## Evidence

Confirmed present in:
- `src/implicit.c` in GNU Make mirror (mirror/make on GitHub, ~2024)
- `src/implicit.c` in GNU Make Savannah HEAD (`cgit/make.git`, 2025-03-27)

Lines 796-797 (Savannah):
```c
                    for (dp = file->deps; dp != 0; dp = dp->next)
                      if (streq (d->name, dep_name (dp)))
```