# UNDF: UNDF-2026-000000720
# zeek-0002 — Attributes::AddAttr O(A²) during script compilation

## Ecosystem
zeek (C++)

## Severity
LOW-MEDIUM — script compilation path; not per-packet, but scales with
size of Zeek scripts and record type definitions

## Location
`src/Attr.cc`
- `Attributes::Find(AttrTag t)` (~line 264): O(A) linear scan of `attrs` vector
- `Attributes::AddAttr` (~line 191): calls `Find` + `RemoveAttr` — each O(A)
- `Attributes::AddAttrs` (~line 259): calls `AddAttr` for each of A attributes — O(A²) total
- `Attributes::RemoveAttr` (~line 272): O(A) linear scan

## Description

`Attributes` stores a list of `AttrPtr` objects in `std::vector<AttrPtr> attrs`.
There are no O(1) accessors by tag.

`AddAttr` is the hot function: it checks for duplicates using `Find(tag)` (O(A)),
then removes the old copy via `RemoveAttr(tag)` (O(A)), then appends the new one.
It also calls `Find(ATTR_REDEF)` a third time:

```cpp
void Attributes::AddAttr(AttrPtr attr, bool is_redef) {
    if ( ! is_redef ) {
        auto existing = Find(attr->Tag());   // O(A) scan #1
        ...
    }
    RemoveAttr(attr->Tag());                 // O(A) scan #2
    attrs.emplace_back(attr);
    ...
    if ( ... && ! Find(ATTR_REDEF) )         // O(A) scan #3
        attrs.emplace_back(...);
}
```

`AddAttrs` calls `AddAttr` for every attribute in a source list:

```cpp
void Attributes::AddAttrs(const AttributesPtr& a, bool is_redef) {
    for ( const auto& attr : a->GetAttrs() )   // O(A) iterations
        AddAttr(attr, is_redef);               // O(A) per call
}
```

Total cost of `AddAttrs`: O(A²) where A is the number of attributes.

In practice, Zeek record types (common in enterprise scripts) can have many
attributes. During compilation of `redef record ...` statements that add
many `&log`, `&optional`, `&default`, etc. attributes, this becomes noticeable.
Large Zeek script deployments with many redefs on heavily-attributed record
types can see significant compilation slowdowns.

## Fix

Replace the linear `attrs` vector with a small fixed-size array indexed by
`AttrTag` (since `AttrTag` is a small enum), or use an
`std::unordered_map<AttrTag, AttrPtr>` for O(1) Find/Remove:

```cpp
--- a/src/Attr.h
+++ b/src/Attr.h
@@ class Attributes {
-    std::vector<AttrPtr> attrs;
+    std::unordered_map<AttrTag, AttrPtr> attr_map;   // O(1) find/remove by tag
+    std::vector<AttrPtr> attrs;                       // kept for ordered iteration

--- a/src/Attr.cc
+++ b/src/Attr.cc
 const AttrPtr& Attributes::Find(AttrTag t) const {
-    for ( const auto& a : attrs )
-        if ( a->Tag() == t ) return a;     // O(A) scan eliminated
-    return Attr::nil;
+    auto it = attr_map.find(t);
+    if ( it != attr_map.end() ) return it->second;
+    return Attr::nil;
 }

 void Attributes::RemoveAttr(AttrTag t) {
-    for ( auto it = attrs.begin(); it != attrs.end(); ) {
-        if ( (*it)->Tag() == t ) it = attrs.erase(it);
-        else ++it;
-    }
+    auto it = attr_map.find(t);
+    if ( it != attr_map.end() ) {
+        attrs.erase(std::remove_if(attrs.begin(), attrs.end(),
+                    [t](const AttrPtr& a){ return a->Tag() == t; }), attrs.end());
+        attr_map.erase(it);
+    }
 }
```

## Complexity

| Variant | AddAttr cost | AddAttrs(A attrs) total |
|---------|-------------|------------------------|
| Before  | O(A)        | O(A²)                  |
| After   | O(1)        | O(A)                   |
| Speedup | A× (number of attributes) |

## Notes
- `AttrTag` has ~40 enum values; a fixed array indexed by tag would work too
  and would avoid hash overhead
- The `attrs` vector is still needed for ordered iteration in `Describe()`
  and `CheckAttr()`; the map is an additional O(1) index, not a replacement
- Zeek compilation for large enterprises with hundreds of script files and
  many record redefs can involve thousands of `AddAttrs` calls
