# UNDF: UNDF-2026-000000499
# php-0004: zend_do_inherit_interfaces — O(IF × CE) interface inheritance dedup linear scan

## Summary

| Field       | Value |
|-------------|-------|
| ID          | php-0004 |
| Severity    | MEDIUM |
| CWE         | CWE-407 (Algorithmic Complexity) |
| File        | `Zend/zend_inheritance.c` |
| Function    | `zend_do_inherit_interfaces` |
| Lines       | 1592–1623 |
| Speedup     | ~150x op-count at IF=CE=500 |

## Defect

When a class inherits from a parent or implements an interface, PHP calls
`zend_do_inherit_interfaces` to copy the interface's interface list into the
class's own interface list (without duplicates). For each of IF parent interfaces,
it does an O(CE) linear scan over the class's current `ce_num` interfaces:

```c
// zend_inheritance.c:1606
while (if_num--) {
    zend_class_entry *entry = iface->interfaces[if_num];
    for (i = 0; i < ce_num; i++) {      // O(ce_num) scan
        if (ce->interfaces[i] == entry) { // pointer equality
            break;
        }
    }
    if (i == ce_num) {
        ce->interfaces[ce->num_interfaces++] = entry;
    }
}
```

The outer loop is `if_num` = number of interfaces in the implemented interface.
The inner loop scans `ce_num` = current class interface count.
Total: O(IF × CE).

This function is called once per implemented interface during class linking
(`do_interface_implementation` → `zend_do_inherit_interfaces`). A class
implementing K interfaces, each with M sub-interfaces, results in K calls
each costing O(M × K×M) = O(K × M²) overall.

In Symfony/Laravel, deeply nested interface hierarchies (Countable, Traversable,
Iterator, IteratorAggregate, etc.) can produce dozens of inherited interfaces
per class.

## Root Cause

`ce->interfaces` is a flat pointer array. Duplicate detection uses a linear
scan rather than a pointer set.

## Fix

Maintain a pointer hash set that grows as interfaces are added:

```diff
--- a/Zend/zend_inheritance.c
+++ b/Zend/zend_inheritance.c
@@ -1592,6 +1592,9 @@ static void zend_do_inherit_interfaces(...)
 {
 	uint32_t i, ce_num, if_num = iface->num_interfaces;
 	ce_num = ce->num_interfaces;
+	HashTable iface_set;
+	zend_hash_init(&iface_set, ce_num + if_num, NULL, NULL, 0);
+	for (i = 0; i < ce_num; i++) {
+		zend_hash_index_add_empty_element(&iface_set, (zend_ulong)(uintptr_t)ce->interfaces[i]);
+	}

 	while (if_num--) {
 		zend_class_entry *entry = iface->interfaces[if_num];
-		for (i = 0; i < ce_num; i++) {
-			if (ce->interfaces[i] == entry) {
-				break;
-			}
-		}
-		if (i == ce_num) {
+		if (!zend_hash_index_find(&iface_set, (zend_ulong)(uintptr_t)entry)) {
 			ce->interfaces[ce->num_interfaces++] = entry;
+			zend_hash_index_add_empty_element(&iface_set, (zend_ulong)(uintptr_t)entry);
 		}
 	}
+	zend_hash_destroy(&iface_set);
```

## Measurement

Simulated with `PhpInterfaceDedupAlgorithm.java`:

| IF   | CE   | slow ops | fast ops | ratio |
|------|------|----------|----------|-------|
| 50   | 50   | 2,500    | 100      | 25×   |
| 200  | 200  | 40,000   | 400      | 100×  |
| 500  | 500  | 250,000  | 1,000    | 250×  |

## References

- `Zend/zend_inheritance.c` lines 1592–1623 (`zend_do_inherit_interfaces`)
- `Zend/zend_inheritance.c` lines 1606–1616 (inner dedup loop)
- Related: php-0003 (`zend_do_implement_interfaces` same pattern)