Autocomplete / Typeahead Search

Keystrokes per day: 50M × 4 × 6 = 1.2B keystrokes/day
With debouncing (200ms): ~40% reduction → 720M API calls/day
With client caching (70% hit): 720M × 0.3 = 216M actual network requests/day
Peak RPS: 216M / 86400 × 3 (peak multiplier) ≈ 7,500 RPS to search service

<AutocompleteProvider>              ← Context for shared state
  <AutocompleteRoot>                ← Container, ARIA combobox owner
    <SearchInput />                 ← Controlled input, aria-autocomplete="list"
    <ClearButton />                 ← Visible when query.length > 0
    <SuggestionDropdown>            ← Portal or inline, role="listbox"
      <SuggestionGroup>             ← Grouped by category (recent/trending/results)
        <SuggestionItem />          ← role="option", aria-selected
        <SuggestionItem />
      </SuggestionGroup>
      <NoResults />                 ← Fallback state
      <SearchFooter />              ← "Press Enter to search for '{query}'"
    </SuggestionDropdown>
  </AutocompleteRoot>
</AutocompleteProvider>

// === Domain Types ===

interface Suggestion {
  id: string;
  text: string;
  category: SuggestionCategory;
  metadata: SuggestionMetadata;
}

type SuggestionCategory = "recent" | "trending" | "result" | "entity";

interface SuggestionMetadata {
  icon?: string;
  subtitle?: string;
  url?: string;
  entityType?: "product" | "user" | "page" | "category";
  score?: number;
}

interface SuggestionGroup {
  category: SuggestionCategory;
  label: string;
  items: Suggestion[];
}

// === API Response Shape ===

interface AutocompleteResponse {
  query: string;
  groups: SuggestionGroup[];
  meta: {
    requestId: string;
    latencyMs: number;
    fromCache: boolean;
  };
}

// === Cache Types ===

interface CacheEntry {
  query: string;
  response: AutocompleteResponse;
  timestamp: number;
  ttl: number;
  accessCount: number;
}

interface LRUCacheConfig {
  maxSize: number;
  defaultTTL: number;
  onEvict?: (key: string, entry: CacheEntry) => void;
}

// === Store State ===

interface AutocompleteState {
  // Query slice
  query: string;
  debouncedQuery: string;
  isComposing: boolean;

  // Results slice
  suggestions: SuggestionGroup[];
  status: RequestStatus;
  error: AutocompleteError | null;

  // Navigation slice
  activeIndex: number;
  isOpen: boolean;
  selectedItem: Suggestion | null;

  // Actions
  setQuery: (query: string) => void;
  setComposing: (isComposing: boolean) => void;
  selectItem: (item: Suggestion) => void;
  navigateUp: () => void;
  navigateDown: () => void;
  close: () => void;
  reset: () => void;
}

type RequestStatus = "idle" | "loading" | "success" | "error" | "stale";

interface AutocompleteError {
  code: "NETWORK" | "TIMEOUT" | "RATE_LIMITED" | "SERVER_ERROR";
  message: string;
  retryAfter?: number;
}

// === Recent Searches (localStorage) ===

interface RecentSearch {
  query: string;
  timestamp: number;
  resultUrl?: string;
}

interface RecentSearchStore {
  searches: RecentSearch[];
  maxItems: number;
  ttlMs: number;
}

// 200 OK
interface SuccessResponse {
  data: AutocompleteResponse;
  cache: {
    hit: boolean;
    ttl: number;
    key: string;
  };
}

// Error responses
interface ErrorResponse {
  error: {
    code: string;
    message: string;
    retryAfter?: number;
  };
  requestId: string;
}

Cache-Control: public, max-age=60, stale-while-revalidate=300
Vary: Accept-Encoding, Accept-Language
ETag: "abc123"
X-Request-Id: uuid-v4

X-RateLimit-Limit: 100
X-RateLimit-Remaining: 97
X-RateLimit-Reset: 1700000000

interface FetchSuggestionsOptions {
  query: string;
  signal: AbortSignal;
  limit?: number;
  categories?: SuggestionCategory[];
}

async function fetchSuggestions({
  query,
  signal,
  limit = 5,
  categories = ["recent", "trending", "result"],
}: FetchSuggestionsOptions): Promise<AutocompleteResponse> {
  const params = new URLSearchParams({
    q: query,
    limit: String(limit),
    categories: categories.join(","),
  });

  const response = await fetch(`/api/search/suggest?${params}`, {
    signal,
    headers: {
      Accept: "application/json",
      "X-Request-Id": crypto.randomUUID(),
    },
  });

  if (!response.ok) {
    const error = (await response.json()) as ErrorResponse;
    throw new AutocompleteFetchError(error.error.code, error.error.message);
  }

  return ((await response.json()) as SuccessResponse).data;
}

class LRUCache<T> {
  private cache: Map<string, CacheEntry>;
  private readonly maxSize: number;
  private readonly defaultTTL: number;

  constructor(config: LRUCacheConfig) {
    this.cache = new Map();
    this.maxSize = config.maxSize;
    this.defaultTTL = config.defaultTTL;
  }

  get(key: string): T | null {
    const entry = this.cache.get(key);
    if (!entry) return null;

    if (Date.now() - entry.timestamp > entry.ttl) {
      this.cache.delete(key);
      return null;
    }

    // Move to end (most recently used)
    this.cache.delete(key);
    entry.accessCount++;
    this.cache.set(key, entry);
    return entry.response as T;
  }

  set(key: string, value: T, ttl?: number): void {
    if (this.cache.size >= this.maxSize) {
      // Evict oldest (first entry in Map)
      const firstKey = this.cache.keys().next().value;
      if (firstKey) this.cache.delete(firstKey);
    }

    this.cache.set(key, {
      query: key,
      response: value,
      timestamp: Date.now(),
      ttl: ttl ?? this.defaultTTL,
      accessCount: 1,
    } as CacheEntry);
  }

  has(key: string): boolean {
    return this.get(key) !== null;
  }

  clear(): void {
    this.cache.clear();
  }

  get size(): number {
    return this.cache.size;
  }
}

const RECENT_SEARCHES_KEY = "autocomplete:recent";
const MAX_RECENT = 50;
const RECENT_TTL_MS = 30 * 24 * 60 * 60 * 1000; // 30 days

function getRecentSearches(): RecentSearch[] {
  const raw = localStorage.getItem(RECENT_SEARCHES_KEY);
  if (!raw) return [];

  const searches: RecentSearch[] = JSON.parse(raw);
  const now = Date.now();
  return searches.filter((s) => now - s.timestamp < RECENT_TTL_MS);
}

function addRecentSearch(query: string, resultUrl?: string): void {
  const searches = getRecentSearches().filter((s) => s.query !== query);
  searches.unshift({ query, timestamp: Date.now(), resultUrl });
  localStorage.setItem(
    RECENT_SEARCHES_KEY,
    JSON.stringify(searches.slice(0, MAX_RECENT)),
  );
}

function getPrefixCacheHit(
  query: string,
  cache: LRUCache<AutocompleteResponse>,
): AutocompleteResponse | null {
  // Try progressively shorter prefixes
  for (let i = query.length - 1; i >= 2; i--) {
    const prefix = query.slice(0, i);
    const cached = cache.get(prefix);
    if (!cached) continue;

    // Filter cached results that still match the longer query
    const filtered: SuggestionGroup[] = cached.groups
      .map((group) => ({
        ...group,
        items: group.items.filter((item) =>
          item.text.toLowerCase().includes(query.toLowerCase()),
        ),
      }))
      .filter((group) => group.items.length > 0);

    // Only use prefix cache if we have meaningful results
    if (filtered.reduce((sum, g) => sum + g.items.length, 0) >= 3) {
      return { ...cached, groups: filtered };
    }
  }
  return null;
}

Keystroke → Debounce (150ms) → Cache Check (< 1ms) → [Cache Hit? Return] →
  → Network Request → AbortController check → Parse JSON →
  → Update Store → React Re-render → Paint (< 16ms)

Total budget: 100ms (cached), 300ms (network)

interface DebounceConfig {
  minDelay: number; // 100ms — fast typists
  maxDelay: number; // 300ms — slow typists
  initialDelay: number; // 150ms — default
}

function createAdaptiveDebounce(config: DebounceConfig) {
  let lastKeystrokeTime = 0;
  let currentDelay = config.initialDelay;
  let timeoutId: ReturnType<typeof setTimeout> | null = null;

  return function debounce(fn: () => void): void {
    const now = Date.now();
    const timeSinceLastKeystroke = now - lastKeystrokeTime;
    lastKeystrokeTime = now;

    // Adapt delay based on typing speed
    if (timeSinceLastKeystroke < 100) {
      // Fast typing — increase debounce to avoid wasted requests
      currentDelay = Math.min(currentDelay + 20, config.maxDelay);
    } else if (timeSinceLastKeystroke > 500) {
      // Pause detected — reduce debounce for responsiveness
      currentDelay = config.minDelay;
    }

    if (timeoutId) clearTimeout(timeoutId);
    timeoutId = setTimeout(fn, currentDelay);
  };
}

class RequestManager {
  private currentController: AbortController | null = null;
  private requestId = 0;

  async fetch(query: string): Promise<AutocompleteResponse | null> {
    // Cancel any in-flight request
    this.currentController?.abort();
    this.currentController = new AbortController();

    const thisRequestId = ++this.requestId;

    try {
      const response = await fetchSuggestions({
        query,
        signal: this.currentController.signal,
      });

      // Guard against race conditions: if a newer request was made
      // while this one was in-flight, discard this response
      if (thisRequestId !== this.requestId) return null;

      return response;
    } catch (error) {
      if (error instanceof DOMException && error.name === "AbortError") {
        return null; // Expected — request was superseded
      }
      throw error;
    }
  }

  cancel(): void {
    this.currentController?.abort();
    this.currentController = null;
  }
}

Content-Security-Policy:
  default-src 'self';
  script-src 'self' 'nonce-{random}';
  style-src 'self' 'unsafe-inline';  /* Tailwind requires this */
  connect-src 'self' https://api.example.com;
  img-src 'self' https://cdn.example.com;

// Input sanitization — applied before sending to API
function sanitizeQuery(raw: string): string {
  return raw
    .trim()
    .slice(0, 200)                          // Length limit
    .replace(/[<>"'&]/g, '');               // Strip HTML-significant chars
}

// Output encoding — when rendering suggestion text with highlights
function renderHighlightedText(
  text: string,
  query: string
): React.ReactNode[] {
  // NEVER use dangerouslySetInnerHTML
  const escapedQuery = query.replace(/[.*+?^${}()|[\]\\]/g, '\\$&');
  const regex = new RegExp(`(${escapedQuery})`, 'gi');
  const parts = text.split(regex);

  return parts.map((part, index) =>
    regex.test(part)
      ? <mark key={index} className="bg-yellow-100 font-semibold">{part}</mark>
      : <span key={index}>{part}</span>
  );
}

class CircuitBreaker {
  private failures = 0;
  private lastFailureTime = 0;
  private state: "closed" | "open" | "half-open" = "closed";

  private readonly threshold = 5;
  private readonly resetTimeout = 30_000; // 30s

  async execute<T>(fn: () => Promise<T>): Promise<T> {
    if (this.state === "open") {
      if (Date.now() - this.lastFailureTime > this.resetTimeout) {
        this.state = "half-open";
      } else {
        throw new Error("Circuit breaker is open");
      }
    }

    try {
      const result = await fn();
      this.onSuccess();
      return result;
    } catch (error) {
      this.onFailure();
      throw error;
    }
  }

  private onSuccess(): void {
    this.failures = 0;
    this.state = "closed";
  }

  private onFailure(): void {
    this.failures++;
    this.lastFailureTime = Date.now();
    if (this.failures >= this.threshold) {
      this.state = "open";
    }
  }
}

// On the input element
const inputAttributes = {
  role: "combobox",
  "aria-autocomplete": "list",
  "aria-expanded": isOpen,
  "aria-controls": "suggestion-listbox",
  "aria-activedescendant": activeItemId ?? undefined,
  "aria-describedby": "autocomplete-help",
  autoComplete: "off", // Prevent browser autocomplete from conflicting
};

// On the dropdown container
const listboxAttributes = {
  role: "listbox",
  id: "suggestion-listbox",
  "aria-label": "Search suggestions",
};

// On each suggestion item
const optionAttributes = (item: Suggestion, index: number) => ({
  role: "option",
  id: `suggestion-${item.id}`,
  "aria-selected": index === activeIndex,
  "aria-label": `${item.text}, ${item.category}`,
});

function getAnnouncement(
  status: RequestStatus,
  resultCount: number,
  query: string,
): string {
  switch (status) {
    case "loading":
      return "Searching...";
    case "success":
      return resultCount > 0
        ? `${resultCount} suggestions available for "${query}". Use arrow keys to navigate.`
        : `No suggestions found for "${query}".`;
    case "error":
      return "Search suggestions unavailable. Recent searches are shown.";
    default:
      return "";
  }
}

<div
  role="status"
  aria-live="polite"
  aria-atomic="true"
  className="sr-only"
>
  {announcement}
</div>

function useKeyboardNavigation(
  suggestions: Suggestion[],
  isOpen: boolean,
  onSelect: (item: Suggestion) => void,
  onClose: () => void,
) {
  const [activeIndex, setActiveIndex] = useState(-1);
  const flatItems = suggestions;
  const itemCount = flatItems.length;

  const handleKeyDown = useCallback(
    (event: React.KeyboardEvent) => {
      if (!isOpen && event.key !== "ArrowDown" && event.key !== "ArrowUp")
        return;

      switch (event.key) {
        case "ArrowDown":
          event.preventDefault();
          setActiveIndex((prev) => (prev + 1) % itemCount);
          break;
        case "ArrowUp":
          event.preventDefault();
          setActiveIndex((prev) => (prev - 1 + itemCount) % itemCount);
          break;
        case "Enter":
          if (activeIndex >= 0) {
            event.preventDefault();
            onSelect(flatItems[activeIndex]);
          }
          break;
        case "Escape":
          event.preventDefault();
          onClose();
          setActiveIndex(-1);
          break;
        case "Home":
          event.preventDefault();
          setActiveIndex(0);
          break;
        case "End":
          event.preventDefault();
          setActiveIndex(itemCount - 1);
          break;
      }
    },
    [isOpen, activeIndex, itemCount, flatItems, onSelect, onClose],
  );

  // Reset active index when suggestions change
  useEffect(() => {
    setActiveIndex(-1);
  }, [suggestions]);

  return {
    activeIndex,
    handleKeyDown,
    activeItemId: flatItems[activeIndex]?.id,
  };
}

interface AutocompleteMetricEvent {
  name: string;
  value: number;
  tags: {
    query_length: number;
    cache_layer: "l1" | "l2" | "l3" | "miss";
    result_count: number;
    selected_position?: number;
    error_code?: string;
    degradation_tier: 1 | 2 | 3 | 4;
  };
  timestamp: number;
}

function trackMetric(event: AutocompleteMetricEvent): void {
  // Batch and send to analytics endpoint
  // Use sendBeacon for page-unload resilience
  if (navigator.sendBeacon) {
    navigator.sendBeacon("/api/metrics", JSON.stringify(event));
  }
}