# sinatra-0002: CWE-407 — `provides` condition calls `Array#include?` inside route-match loop

| Field       | Value |
|-------------|-------|
| ID          | sinatra-0002 |
| Project     | sinatra/sinatra |
| Severity    | MEDIUM |
| Status      | OPEN |
| CWE         | CWE-407 (Algorithmic Complexity) |
| Found       | 2026-03-27 |

## Location

`lib/sinatra/base.rb:1765` (inside the `provides` method's condition block)

```ruby
def provides(*types)
  types.map! { |t| mime_types(t) }
  types.flatten!
  condition do                              # <-- this block runs on every route attempt
    response_content_type = response['content-type']
    preferred_type = request.preferred_type(types)

    if response_content_type
      types.include?(response_content_type) || types.include?(response_content_type[/^[^;]+/])
      # ^^^ two O(n) Array#include? scans on every route evaluation
```

## Root Cause

`provides` registers a `condition` block that runs during `process_route` for every route that
uses it (line 1120: `conditions.each { |c| throw :pass if c.bind(self).call == false }`).

Inside the condition, `types` is a plain Array. `Array#include?` is O(n). Two back-to-back
scans happen when `response_content_type` is already set (the common case after middleware sets
content-type early).

With R routes each using `provides` and T types, every request costs O(R×T) Array scans in the
worst case (all routes are attempted before match).

## Fix

Freeze `types` as a `Set` at route-registration time (once), not at request time:

```ruby
def provides(*types)
  types.map! { |t| mime_types(t) }
  types.flatten!
  types_set = types.to_set                  # built once at route definition time
  condition do
    response_content_type = response['content-type']
    preferred_type = request.preferred_type(types)   # keep Array for ordering

    if response_content_type
      types_set.include?(response_content_type) ||
        types_set.include?(response_content_type[/^[^;]+/])
      # O(1) hash lookup instead of O(n) scan
```

`request.preferred_type(types)` needs the Array for Accept-header ordering logic, so `types`
must remain an Array for that call. `types_set` is used only for the membership tests.

## Patch

`defects/sinatra/patch/sinatra-0002-provides-types-set.patch`

## Benchmark

`defects/sinatra/unit/SinatraTest.java`