# UNDF: UNDF-2026-000000564
# v8-0002 — objects/intl: CanonicalizeLocaleList seen-list O(N²) → O(N)

## Metadata
- Project: V8
- Component: src/objects/intl-objects.cc
- CWE: CWE-407
- Severity: HIGH
- Complexity: O(N²) → O(N)
- Function: `Intl::CanonicalizeLocaleList`
- Line: 940 (chromium.googlesource.com/v8/v8, HEAD 2026-03)

## Problem

`CanonicalizeLocaleList` is the first operation performed by every `Intl.*`
constructor (`Intl.Collator`, `Intl.DateTimeFormat`, `Intl.NumberFormat`, etc.)
when a locale list is passed.

It maintains a deduplication list `seen` as a `std::vector<std::string>`.
For each of the N input locales the function does:

```cpp
// src/objects/intl-objects.cc  line 940
if (std::find(seen.begin(), seen.end(), canonicalized_tag) == seen.end()) {
    seen.push_back(canonicalized_tag);
}
```

`std::find` on a `std::vector` is O(seen.size()). Since `seen` grows to at
most N entries, the total cost across the loop is:

  0 + 1 + 2 + … + (N-1) = N·(N-1)/2  →  **O(N²)**

For an application that constructs an `Intl` object with a large deduplicated
locale priority list (e.g., a language negotiation library, a locale-aware
formatter factory, server-side i18n that loops over all BCP-47 subtags) this
compounds per object construction.

## Defective code

```cpp
// src/objects/intl-objects.cc:862-948
Maybe<std::vector<std::string>> Intl::CanonicalizeLocaleList(
    Isolate* isolate, DirectHandle<Object> locales,
    bool only_return_one_result) {
  ...
  std::vector<std::string> seen;           // <-- deduplication list
  ...
  for (uint32_t k = 0; k < len; k++) {
    ...
    // line 940
    if (std::find(seen.begin(), seen.end(), canonicalized_tag) == seen.end()) {
      seen.push_back(canonicalized_tag);
    }
  }
  return Just(seen);
}
```

## Fix

Introduce a parallel `std::unordered_set<std::string>` for O(1) membership
test; keep the `seen` vector to preserve insertion order required by the
ECMA-402 spec (§9.2.1 step 7c.vi says "append as last element").

```cpp
Maybe<std::vector<std::string>> Intl::CanonicalizeLocaleList(
    Isolate* isolate, DirectHandle<Object> locales,
    bool only_return_one_result) {
  ...
  std::vector<std::string> seen;
  std::unordered_set<std::string> seen_set;  // CWE-407 fix: O(1) membership
  ...
  for (uint32_t k = 0; k < len; k++) {
    ...
    // CWE-407 fix: O(1) hash lookup replaces O(seen.size()) linear scan
    if (seen_set.find(canonicalized_tag) == seen_set.end()) {
      seen.push_back(canonicalized_tag);
      seen_set.insert(canonicalized_tag);
    }
  }
  return Just(seen);
}
```

## Complexity analysis

| Scenario | Before (defect) | After (fix) |
|---|---|---|
| N distinct locales | O(N²) string comparisons | O(N) hash lookups |
| N identical locales | O(N) comparisons (list stays size 1) | O(N) hash lookups |
| N=10 | 45 comparisons | 10 hash lookups |
| N=100 | 4950 comparisons | 100 hash lookups |
| N=500 | 124750 comparisons | 500 hash lookups |
| Speedup at N=500 | baseline | ~249x fewer string ops |

## Call sites (ECMA-402 API surface)

- `Intl.Collator()` — language-sensitive string comparison
- `Intl.DateTimeFormat()` — date/time formatting
- `Intl.NumberFormat()` — number formatting
- `Intl.PluralRules()` — plural-form selection
- `Intl.RelativeTimeFormat()` — relative time formatting
- `Intl.ListFormat()` — list formatting
- `Intl.Segmenter()` — text segmentation
- `Intl.supportedLocalesOf()` — locale support query

Any JS application that calls these APIs with an array of N locale tags pays
O(N²) in V8 before this fix.
