java-topology/docs/tickets/sinatra-0002-provides-types-array-include-per-request.md

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)

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:

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