# UNDF: UNDF-2026-000000609
# UNDF: (pending)
# mastodon-0001: OStatus::Activity::Creation#save_mentions — O(N²) processed_account_ids Array#include? dedup

## CWE-407 — Algorithmic Complexity

| Field | Value |
|-------|-------|
| ID | mastodon-0001 |
| Severity | MEDIUM |
| Ecosystem | mastodon |
| Package | mastodon (OStatus activity processing) |
| File | `app/lib/ostatus/activity/creation.rb` |
| Lines | 128–143 |
| Complexity | O(N²) Array#include? inside O(N) loop |
| Hot path | Federated OStatus post ingestion with multiple mentions |

## Defect

`save_mentions` iterates over all mention links in an OStatus XML payload and
uses `Array#include?` on a plain `Array` to skip duplicate account IDs. Each
`include?` call is O(N) over the array of already-processed IDs. For a post
with N mention links (group posts, reply-alls, or maliciously crafted
federation packets), the total cost is O(N²).

```ruby
# BEFORE — O(N²): Array#include? is O(N) inside O(N) loop
def save_mentions(parent)
  processed_account_ids = []       # Array, not Set

  @xml.xpath('./xmlns:link[@rel="mentioned"]', ...).each do |link|
    next if [...].include? link['ostatus:object-type']

    mentioned_account = account_from_href(link['href'])
    next if mentioned_account.nil? || processed_account_ids.include?(mentioned_account.id)  # O(N)

    mentioned_account.mentions.where(status: parent).first_or_create(status: parent)
    processed_account_ids << mentioned_account.id   # accumulates
  end
end
```

## Fix

Replace `Array` with `Set` for O(1) average membership testing.

```ruby
# AFTER — O(N): Set#include? is O(1)
require 'set'

def save_mentions(parent)
  processed_account_ids = Set.new   # Set, not Array

  @xml.xpath('./xmlns:link[@rel="mentioned"]', ...).each do |link|
    next if [...].include? link['ostatus:object-type']

    mentioned_account = account_from_href(link['href'])
    next if mentioned_account.nil? || processed_account_ids.include?(mentioned_account.id)  # O(1)

    mentioned_account.mentions.where(status: parent).first_or_create(status: parent)
    processed_account_ids.add(mentioned_account.id)
  end
end
```

## Speedup

| Mentions (N) | Before (comparisons) | After (comparisons) | Speedup |
|--------------|----------------------|---------------------|---------|
| 50 | 1,275 | 50 | 25× |
| 100 | 5,050 | 100 | 50× |
| 500 | 125,250 | 500 | 250× |

## Notes

- OStatus is the legacy federation protocol; ActivityPub (`app/lib/activitypub/`)
  does not have this pattern.
- Account IDs are integers — Set hashing is safe and stable.
- `Set` is in Ruby stdlib; `require 'set'` is already present in the Mastodon
  codebase via other files loaded in the same context.
