accept.test.ts

// Type-level tests for accept.ts. Each alias fails to compile if the assertion fails.

import type { AcceptItem, Negotiate, NegotiateError, ParseAccept, ParseError } from "./accept";

type Eq<A, B> = (<T>() => T extends A ? 1 : 2) extends <T>() => T extends B ? 1 : 2 ? true : false;
type Assert<T extends true> = T;

// --- basics ---

type T01 = Assert<Eq<ParseAccept<"">, []>>;
type T02 = Assert<
  Eq<ParseAccept<"text/html">, [{ type: "text"; subtype: "html"; params: []; q: "1" }]>
>;
type T03 = Assert<Eq<ParseAccept<"*/*">, [{ type: "*"; subtype: "*"; params: []; q: "1" }]>>;
type T04 = Assert<
  Eq<ParseAccept<"image/*">, [{ type: "image"; subtype: "*"; params: []; q: "1" }]>
>;

// a typical browser Accept header
type T05 = Assert<
  Eq<
    ParseAccept<"text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8">,
    [
      { type: "text"; subtype: "html"; params: []; q: "1" },
      { type: "application"; subtype: "xhtml+xml"; params: []; q: "1" },
      { type: "application"; subtype: "xml"; params: []; q: "0.9" },
      { type: "*"; subtype: "*"; params: []; q: "0.8" },
    ]
  >
>;

// the example from RFC 9110 Section 12.5.1, with an HTAB thrown in as OWS
type T06 = Assert<
  Eq<
    ParseAccept<"text/plain; q=0.5, text/html,\t text/x-dvi; q=0.8, text/x-c">,
    [
      { type: "text"; subtype: "plain"; params: []; q: "0.5" },
      { type: "text"; subtype: "html"; params: []; q: "1" },
      { type: "text"; subtype: "x-dvi"; params: []; q: "0.8" },
      { type: "text"; subtype: "x-c"; params: []; q: "1" },
    ]
  >
>;

// --- parameters ---

type T07 = Assert<
  Eq<
    ParseAccept<"text/html;charset=utf-8">,
    [{ type: "text"; subtype: "html"; params: [["charset", "utf-8"]]; q: "1" }]
  >
>;
type T08 = Assert<
  Eq<
    ParseAccept<'text/html; charset="utf-8"'>,
    [{ type: "text"; subtype: "html"; params: [["charset", "utf-8"]]; q: "1" }]
  >
>;
// quoted-pairs are unescaped
type T09 = Assert<
  Eq<
    ParseAccept<'text/plain; title="a\\"b\\\\c"'>,
    [{ type: "text"; subtype: "plain"; params: [["title", 'a"b\\c']]; q: "1" }]
  >
>;
// type, subtype, and parameter names are lowercased; parameter values are not
type T10 = Assert<
  Eq<
    ParseAccept<"Text/HTML;Charset=UTF-8;Q=0.5">,
    [{ type: "text"; subtype: "html"; params: [["charset", "UTF-8"]]; q: "0.5" }]
  >
>;
// q is the weight regardless of position; parameters after it are kept
type T11 = Assert<
  Eq<
    ParseAccept<"text/html;level=1;q=0.5;foo=Bar">,
    [{ type: "text"; subtype: "html"; params: [["level", "1"], ["foo", "Bar"]]; q: "0.5" }]
  >
>;
// the last q wins
type T12 = Assert<
  Eq<
    ParseAccept<"text/html;q=0.5;q=0.3">,
    [{ type: "text"; subtype: "html"; params: []; q: "0.3" }]
  >
>;
// a repeated parameter name is preserved as-is (RFC 9110 does not define its semantics)
type T13 = Assert<
  Eq<
    ParseAccept<"text/html;a=1;a=2">,
    [{ type: "text"; subtype: "html"; params: [["a", "1"], ["a", "2"]]; q: "1" }]
  >
>;
// empty parameters (`[ parameter ]`) are allowed
type T14 = Assert<
  Eq<ParseAccept<"text/html; ;q=0.5;">, [{ type: "text"; subtype: "html"; params: []; q: "0.5" }]>
>;

// --- list rule (recipient) ---

type T15 = Assert<
  Eq<
    ParseAccept<"text/html , , text/plain">,
    [
      { type: "text"; subtype: "html"; params: []; q: "1" },
      { type: "text"; subtype: "plain"; params: []; q: "1" },
    ]
  >
>;
type T16 = Assert<Eq<ParseAccept<",,">, []>>;
type T17 = Assert<Eq<ParseAccept<" ">, []>>;
type T18 = Assert<
  Eq<ParseAccept<"text/html,">, [{ type: "text"; subtype: "html"; params: []; q: "1" }]>
>;

// --- qvalue forms ---

type T19 = Assert<Eq<ParseAccept<"a/b;q=0.">, [{ type: "a"; subtype: "b"; params: []; q: "0." }]>>;
type T20 = Assert<
  Eq<ParseAccept<"a/b;q=1.000">, [{ type: "a"; subtype: "b"; params: []; q: "1.000" }]>
>;
type T21 = Assert<
  Eq<ParseAccept<"a/b;q=0.75">, [{ type: "a"; subtype: "b"; params: []; q: "0.75" }]>
>;
type T22 = Assert<Eq<ParseAccept<"a/b;q=1.5">, ParseError<"invalid qvalue", "">>>;
type T23 = Assert<Eq<ParseAccept<"a/b;q=0.1234">, ParseError<"invalid qvalue", "">>>;
type T24 = Assert<Eq<ParseAccept<"a/b;q=1.01">, ParseError<"invalid qvalue", "">>>;

// --- parse errors ---

type T25 = Assert<
  Eq<ParseAccept<"text">, ParseError<"unexpected end of input in a media-range", "">>
>;
type T26 = Assert<Eq<ParseAccept<"text/">, ParseError<"expected a subtype after '/'", "">>>;
type T27 = Assert<Eq<ParseAccept<"text/@">, ParseError<"expected a subtype after '/'", "@">>>;
type T28 = Assert<
  Eq<ParseAccept<"text /html">, ParseError<"expected '/' after the media-range type", " /html">>
>;
type T29 = Assert<
  Eq<ParseAccept<"text/html; charset">, ParseError<"unexpected end of input in a parameter", "">>
>;
type T30 = Assert<
  Eq<
    ParseAccept<"text/html; charset;x=1">,
    ParseError<"expected '=' after a parameter name", ";x=1">
  >
>;
type T31 = Assert<
  Eq<ParseAccept<'text/html;q="0.5"'>, ParseError<"weight must be an unquoted qvalue", "">>
>;
type T32 = Assert<
  Eq<ParseAccept<'text/html; charset="utf-8'>, ParseError<"unterminated quoted-string", "">>
>;
type T33 = Assert<
  Eq<ParseAccept<"text/html; charset=@">, ParseError<"expected a parameter value after '='", "@">>
>;
type T34 = Assert<Eq<ParseAccept<"@">, ParseError<"expected a media-range", "@">>>;
type T35 = Assert<Eq<ParseAccept<"text/html?">, ParseError<"expected ';' or ','", "?">>>;

// --- misc ---

// distributes over unions
type T36 = Assert<
  Eq<
    ParseAccept<"a/b" | "c/d">,
    | [{ type: "a"; subtype: "b"; params: []; q: "1" }]
    | [{ type: "c"; subtype: "d"; params: []; q: "1" }]
  >
>;
// a non-literal input yields the broad result type
type T37 = Assert<Eq<ParseAccept<string>, AcceptItem[] | ParseError>>;

// ===========================================================================
// Negotiate

// --- basics ---

type N01 = Assert<Eq<Negotiate<"text/html", ["text/html", "text/plain"]>, "text/html">>;
type N02 = Assert<Eq<Negotiate<"text/html", ["application/json"]>, null>>;
// an empty Accept (present but empty) accepts nothing; an absent one accepts anything
type N03 = Assert<Eq<Negotiate<"", ["text/html"]>, null>>;
type N04 = Assert<Eq<Negotiate<undefined, ["text/html", "text/plain"]>, "text/html">>;
type N05 = Assert<Eq<Negotiate<undefined, []>, null>>;
type N06 = Assert<Eq<Negotiate<"text/html", []>, null>>;

// RFC 9110 Section 12.5.1: "I prefer audio/basic, but send me any audio type if it is
// the best available after an 80% markdown in quality"
type N07 = Assert<
  Eq<Negotiate<"audio/*; q=0.2, audio/basic", ["audio/mpeg", "audio/basic"]>, "audio/basic">
>;

// RFC 9110 Section 12.5.1: the "more elaborate example"
type ElaborateHeader = "text/plain; q=0.5, text/html, text/x-dvi; q=0.8, text/x-c";
type N08 = Assert<Eq<Negotiate<ElaborateHeader, ["text/plain", "text/x-dvi"]>, "text/x-dvi">>;
type N09 = Assert<
  Eq<Negotiate<ElaborateHeader, ["text/x-dvi", "text/html", "text/x-c"]>, "text/html">
>;

// RFC 9110 Section 12.5.1, Table 5. (Its last row, "text/html;level=3 -> 0.7", is a
// leftover from the RFC 7231 example this was adapted from; with the ranges given here,
// text/html matches text/* and gets 0.3.)
type Table5Header =
  "text/*;q=0.3, text/plain;q=0.7, text/plain;format=flowed, text/plain;format=fixed;q=0.4, */*;q=0.5";
// 1 vs 0.7
type N10 = Assert<
  Eq<
    Negotiate<Table5Header, ["text/plain;format=flowed", "text/plain"]>,
    "text/plain;format=flowed"
  >
>;
// 0.7 vs 0.5
type N11 = Assert<Eq<Negotiate<Table5Header, ["text/plain", "image/jpeg"]>, "text/plain">>;
// 0.3 vs 0.5
type N12 = Assert<Eq<Negotiate<Table5Header, ["text/html", "image/jpeg"]>, "image/jpeg">>;
// 0.4 vs 0.5
type N13 = Assert<
  Eq<Negotiate<Table5Header, ["text/plain;format=fixed", "image/jpeg"]>, "image/jpeg">
>;

// --- qvalue comparison ---

type N14 = Assert<Eq<Negotiate<"a/b;q=0.85, c/d;q=0.9", ["a/b", "c/d"]>, "c/d">>;
type N15 = Assert<Eq<Negotiate<"a/b;q=0.999, c/d;q=1", ["a/b", "c/d"]>, "c/d">>;
// 0.30 = 0.3, so the tie is broken by candidate order
type N16 = Assert<Eq<Negotiate<"a/b;q=0.30, c/d;q=0.3", ["a/b", "c/d"]>, "a/b">>;
type N17 = Assert<Eq<Negotiate<"*/*", ["c/d", "a/b"]>, "c/d">>;

// q=0 means "not acceptable"
type N18 = Assert<
  Eq<Negotiate<"text/html;q=0, */*;q=0.1", ["text/html", "text/plain"]>, "text/plain">
>;
type N19 = Assert<Eq<Negotiate<"*/*;q=0", ["text/html"]>, null>>;
type N20 = Assert<Eq<Negotiate<"a/b;q=0.000", ["a/b"]>, null>>;

// --- matching ---

// a range with parameters applies only to candidates having all of them
type N21 = Assert<Eq<Negotiate<"text/html;level=1", ["text/html"]>, null>>;
type N22 = Assert<
  Eq<
    Negotiate<"text/html;level=1", ["text/html;charset=utf-8;level=1"]>,
    "text/html;charset=utf-8;level=1"
  >
>;
// parameter values are compared case-sensitively (names are lowercased by the parser)
type N23 = Assert<Eq<Negotiate<"text/html;a=UTF", ["text/html;a=utf"]>, null>>;
type N24 = Assert<Eq<Negotiate<"TEXT/*", ["text/plain"]>, "text/plain">>;
// the chosen candidate is returned as written
type N25 = Assert<Eq<Negotiate<"text/html", ["Text/HTML"]>, "Text/HTML">>;

// specificity: rank (exact > type/* > */*) first, then the number of parameters;
// here the more specific range's weight loses to x/y's 0.5, proving it was the one used
type N26 = Assert<
  Eq<
    Negotiate<
      "text/html;a=1;q=0.9, text/html;a=1;b=2;q=0.2, x/y;q=0.5",
      ["text/html;a=1;b=2", "x/y"]
    >,
    "x/y"
  >
>;
type N27 = Assert<
  Eq<
    Negotiate<
      "text/*;charset=utf-8;q=0.9, text/html;q=0.2, x/y;q=0.5",
      ["text/html;charset=utf-8", "x/y"]
    >,
    "x/y"
  >
>;
// among equally specific ranges, the first one wins
type N28 = Assert<Eq<Negotiate<"a/b;q=0.2, a/b;q=0.9, c/d;q=0.5", ["a/b", "c/d"]>, "c/d">>;

// --- errors ---

type N29 = Assert<Eq<Negotiate<"@", ["a/b"]>, ParseError<"expected a media-range", "@">>>;
type N30 = Assert<
  Eq<
    Negotiate<"text/html", ["text/html", "bogus"]>,
    ParseError<"unexpected end of input in a media-range", "">
  >
>;
type N31 = Assert<
  Eq<
    Negotiate<"text/html", ["*/*"]>,
    NegotiateError<"a candidate must be a concrete media type", "*/*">
  >
>;
type N32 = Assert<
  Eq<
    Negotiate<"text/html", ["text/*"]>,
    NegotiateError<"a candidate must be a concrete media type", "text/*">
  >
>;
type N33 = Assert<
  Eq<
    Negotiate<"text/html", ["text/html;q=0.5"]>,
    NegotiateError<"a candidate must not have a weight", "text/html;q=0.5">
  >
>;
type N34 = Assert<
  Eq<
    Negotiate<"text/html", ["a/b, c/d"]>,
    NegotiateError<"a candidate must be exactly one media type", "a/b, c/d">
  >
>;
type N35 = Assert<
  Eq<Negotiate<"text/html", [""]>, NegotiateError<"a candidate must be exactly one media type", "">>
>;

// --- misc ---

// distributes over unions; a non-literal header yields the broad result type
type N36 = Assert<Eq<Negotiate<"a/b" | undefined, ["c/d", "a/b"]>, "a/b" | "c/d">>;
type N37 = Assert<Eq<Negotiate<string, ["a/b", "c/d"]>, "a/b" | "c/d" | null | ParseError>>;

export {};

accept.ts

// A type-level parser for the HTTP `Accept` header field value, implementing the full
// grammar of RFC 9110:
//
//     Accept      = #( media-range [ weight ] )
//     media-range = ( "*/*" / ( type "/" "*" ) / ( type "/" subtype ) ) parameters
//     weight      = OWS ";" OWS "q=" qvalue                        ; Section 12.4.2
//     parameters  = *( OWS ";" OWS [ parameter ] )                 ; Section 5.6.6
//     parameter   = parameter-name "=" parameter-value
//
// Parsing follows the recipient requirements rather than the sender ones:
//
// - Empty list elements are parsed and ignored (Section 5.6.1.2).
// - A parameter named "q" (case-insensitive) is processed as the weight regardless of
//   its position (Section 12.5.1); if it occurs multiple times, the last one wins.
//   Its value must still be a valid, unquoted qvalue.
// - A quoted-pair in a quoted-string is replaced by the octet following the backslash
//   (Section 5.6.4).
// - type, subtype, and parameter names are case-insensitive (Sections 8.3.1 and 5.6.6)
//   and are normalized to lowercase; parameter values are preserved as-is.
// - Parameters are collected as [name, value] pairs in order of appearance. RFC 9110
//   does not define the semantics of a repeated parameter name, so nothing is merged
//   or dropped.
//
// The parser is written as a state machine over one character per step, with a single
// flat recursion at the top level (`Run`).
//
// `Negotiate` then performs proactive content negotiation (Section 12) over the parsed
// elements: it selects, among the media types the server can produce, the one the
// client prefers most, following the precedence rules of Section 12.5.1.

// ---------------------------------------------------------------------------
// Character classes

// ALPHA / DIGIT (RFC 5234 Appendix B.1)
type Alpha =
  | "A"
  | "B"
  | "C"
  | "D"
  | "E"
  | "F"
  | "G"
  | "H"
  | "I"
  | "J"
  | "K"
  | "L"
  | "M"
  | "N"
  | "O"
  | "P"
  | "Q"
  | "R"
  | "S"
  | "T"
  | "U"
  | "V"
  | "W"
  | "X"
  | "Y"
  | "Z"
  | "a"
  | "b"
  | "c"
  | "d"
  | "e"
  | "f"
  | "g"
  | "h"
  | "i"
  | "j"
  | "k"
  | "l"
  | "m"
  | "n"
  | "o"
  | "p"
  | "q"
  | "r"
  | "s"
  | "t"
  | "u"
  | "v"
  | "w"
  | "x"
  | "y"
  | "z";
type Digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";

// tchar = "!" / "#" / "$" / "%" / "&" / "'" / "*" / "+" / "-" / "." / "^" / "_"
//       / "`" / "|" / "~" / DIGIT / ALPHA                          (Section 5.6.2)
type Tchar =
  | Alpha
  | Digit
  | "!"
  | "#"
  | "$"
  | "%"
  | "&"
  | "'"
  | "*"
  | "+"
  | "-"
  | "."
  | "^"
  | "_"
  | "`"
  | "|"
  | "~";

// OWS = *( SP / HTAB )                                             (Section 5.6.3)
type OwsChar = " " | "\t";

// Control characters other than HTAB, plus DEL. These are exactly the characters
// excluded from both qdtext and quoted-pair (Section 5.6.4), whose alternatives
// (HTAB / SP / VCHAR / obs-text) otherwise cover the whole 0x00-0xFF byte range.
type CtlChar =
  | "\u0000"
  | "\u0001"
  | "\u0002"
  | "\u0003"
  | "\u0004"
  | "\u0005"
  | "\u0006"
  | "\u0007"
  | "\u0008"
  | "\n"
  | "\u000b"
  | "\u000c"
  | "\r"
  | "\u000e"
  | "\u000f"
  | "\u0010"
  | "\u0011"
  | "\u0012"
  | "\u0013"
  | "\u0014"
  | "\u0015"
  | "\u0016"
  | "\u0017"
  | "\u0018"
  | "\u0019"
  | "\u001a"
  | "\u001b"
  | "\u001c"
  | "\u001d"
  | "\u001e"
  | "\u001f"
  | "\u007f";

// qvalue = ( "0" [ "." 0*3DIGIT ] ) / ( "1" [ "." 0*3("0") ] )     (Section 12.4.2)
type IsQvalue<S extends string> = S extends "0" | "1"
  ? true
  : S extends `0.${infer Frac}`
    ? IsRepeat0To3<Frac, Digit>
    : S extends `1.${infer Frac}`
      ? IsRepeat0To3<Frac, "0">
      : false;

type IsRepeat0To3<S extends string, C extends string> = S extends
  | ""
  | C
  | `${C}${C}`
  | `${C}${C}${C}`
  ? true
  : false;

// ---------------------------------------------------------------------------
// Results

/**
 * A single parsed element of an `Accept` header field value: a media-range with its
 * parameters and weight. `params` lists [name, value] pairs in order of appearance,
 * and `q` defaults to `"1"` when no weight is given.
 */
export type AcceptItem = {
  type: string;
  subtype: string;
  params: [string, string][];
  q: string;
};

/**
 * A parse failure. `rest` is the remaining input starting at the offending position
 * (empty if the input ended unexpectedly).
 */
export type ParseError<Message extends string = string, Rest extends string = string> = {
  error: Message;
  rest: Rest;
};

type Params = [string, string][];

// ---------------------------------------------------------------------------
// The state machine

/**
 * `State<I, M, Ty, Sub, Nm, Vl, Ps, Q, Acc>` is a state of the parser.
 *
 * `I` is the remaining input, `M` is the current mode, `Ty` / `Sub` / `Nm` / `Vl` are
 * accumulators for the type / subtype / parameter name / parameter value being read,
 * `Ps` collects the parameters and `Q` the weight (`null` = not seen) of the current
 * element, and `Acc` collects the elements parsed so far.
 */
type State<I, M, Ty, Sub, Nm, Vl, Ps, Q, Acc> = {
  input: I;
  mode: M;
  type: Ty;
  subtype: Sub;
  name: Nm;
  value: Vl;
  params: Ps;
  q: Q;
  accepts: Acc;
};

type Init<I> = State<I, "beforeElement", "", "", "", "", [], null, []>;

/**
 * Finishes the current element and appends it to the results.
 */
type Emit<Ty extends string, Sub extends string, Ps extends Params, Q, Acc extends AcceptItem[]> = [
  ...Acc,
  {
    type: Lowercase<Ty>;
    subtype: Lowercase<Sub>;
    params: Ps;
    q: Q extends string ? Q : "1";
  },
];

/**
 * `Next<S>` runs the parser one step: it consumes at most one character of the input
 * and returns either the next state or a terminal (the results tuple or a `ParseError`).
 */
type Next<S> =
  S extends State<
    infer I extends string,
    infer M,
    infer Ty extends string,
    infer Sub extends string,
    infer Nm extends string,
    infer Vl extends string,
    infer Ps extends Params,
    infer Q,
    infer Acc extends AcceptItem[]
  >
    ? M extends "beforeElement"
      ? NextBeforeElement<I, Acc>
      : M extends "type"
        ? NextType<I, Ty, Acc>
        : M extends "subtype"
          ? NextSubtype<I, Ty, Sub, Acc>
          : M extends "params"
            ? NextParams<I, Ty, Sub, Ps, Q, Acc>
            : M extends "paramStart"
              ? NextParamStart<I, Ty, Sub, Ps, Q, Acc>
              : M extends "paramName"
                ? NextParamName<I, Ty, Sub, Nm, Ps, Q, Acc>
                : M extends "paramValue"
                  ? NextParamValue<I, Ty, Sub, Nm, Ps, Q, Acc>
                  : M extends "paramValueToken"
                    ? NextParamValueToken<I, Ty, Sub, Nm, Vl, Ps, Q, Acc>
                    : M extends "paramValueQuoted"
                      ? NextParamValueQuoted<I, Ty, Sub, Nm, Vl, Ps, Q, Acc>
                      : M extends "paramValueQuotedPair"
                        ? NextParamValueQuotedPair<I, Ty, Sub, Nm, Vl, Ps, Q, Acc>
                        : never
    : never;

// Before an element: `#element => [ element ] *( OWS "," OWS [ element ] )` for
// recipients (Section 5.6.1.2), so OWS and empty list elements are skipped here.
type NextBeforeElement<
  I extends string,
  Acc extends AcceptItem[],
> = I extends `${infer C}${infer R}`
  ? C extends OwsChar | ","
    ? State<R, "beforeElement", "", "", "", "", [], null, Acc>
    : C extends Tchar
      ? State<R, "type", C, "", "", "", [], null, Acc>
      : ParseError<"expected a media-range", I>
  : Acc;

// Reading the type token. Note that "*" is a tchar, so all three media-range
// alternatives are uniformly `token "/" token`.
type NextType<
  I extends string,
  Ty extends string,
  Acc extends AcceptItem[],
> = I extends `${infer C}${infer R}`
  ? C extends Tchar
    ? State<R, "type", `${Ty}${C}`, "", "", "", [], null, Acc>
    : C extends "/"
      ? State<R, "subtype", Ty, "", "", "", [], null, Acc>
      : ParseError<"expected '/' after the media-range type", I>
  : ParseError<"unexpected end of input in a media-range", I>;

// Reading the subtype token. On the first non-tchar the character is left in the
// input and reprocessed in "params" mode.
type NextSubtype<
  I extends string,
  Ty extends string,
  Sub extends string,
  Acc extends AcceptItem[],
> = I extends `${infer C}${infer R}`
  ? C extends Tchar
    ? State<R, "subtype", Ty, `${Sub}${C}`, "", "", [], null, Acc>
    : Sub extends ""
      ? ParseError<"expected a subtype after '/'", I>
      : State<I, "params", Ty, Sub, "", "", [], null, Acc>
  : Sub extends ""
    ? ParseError<"expected a subtype after '/'", I>
    : State<I, "params", Ty, Sub, "", "", [], null, Acc>;

// Between parameters: `parameters = *( OWS ";" OWS [ parameter ] )`, or the end of
// the element (list delimiter or end of input).
type NextParams<
  I extends string,
  Ty extends string,
  Sub extends string,
  Ps extends Params,
  Q,
  Acc extends AcceptItem[],
> = I extends `${infer C}${infer R}`
  ? C extends OwsChar
    ? State<R, "params", Ty, Sub, "", "", Ps, Q, Acc>
    : C extends ";"
      ? State<R, "paramStart", Ty, Sub, "", "", Ps, Q, Acc>
      : C extends ","
        ? State<R, "beforeElement", "", "", "", "", [], null, Emit<Ty, Sub, Ps, Q, Acc>>
        : ParseError<"expected ';' or ','", I>
  : Emit<Ty, Sub, Ps, Q, Acc>;

// After a ";": OWS, then a parameter name — or nothing, since `[ parameter ]` is
// optional, in which case another ";", a ",", or the end of input may follow.
type NextParamStart<
  I extends string,
  Ty extends string,
  Sub extends string,
  Ps extends Params,
  Q,
  Acc extends AcceptItem[],
> = I extends `${infer C}${infer R}`
  ? C extends OwsChar | ";"
    ? State<R, "paramStart", Ty, Sub, "", "", Ps, Q, Acc>
    : C extends ","
      ? State<R, "beforeElement", "", "", "", "", [], null, Emit<Ty, Sub, Ps, Q, Acc>>
      : C extends Tchar
        ? State<R, "paramName", Ty, Sub, C, "", Ps, Q, Acc>
        : ParseError<"expected a parameter name", I>
  : Emit<Ty, Sub, Ps, Q, Acc>;

// Reading a parameter name; `parameter = parameter-name "=" parameter-value` allows
// no whitespace around "=" and no valueless parameters.
type NextParamName<
  I extends string,
  Ty extends string,
  Sub extends string,
  Nm extends string,
  Ps extends Params,
  Q,
  Acc extends AcceptItem[],
> = I extends `${infer C}${infer R}`
  ? C extends Tchar
    ? State<R, "paramName", Ty, Sub, `${Nm}${C}`, "", Ps, Q, Acc>
    : C extends "="
      ? State<R, "paramValue", Ty, Sub, Nm, "", Ps, Q, Acc>
      : ParseError<"expected '=' after a parameter name", I>
  : ParseError<"unexpected end of input in a parameter", I>;

// At the first character of a parameter value: `parameter-value = token / quoted-string`.
type NextParamValue<
  I extends string,
  Ty extends string,
  Sub extends string,
  Nm extends string,
  Ps extends Params,
  Q,
  Acc extends AcceptItem[],
> = I extends `${infer C}${infer R}`
  ? C extends Tchar
    ? State<R, "paramValueToken", Ty, Sub, Nm, C, Ps, Q, Acc>
    : C extends '"'
      ? State<R, "paramValueQuoted", Ty, Sub, Nm, "", Ps, Q, Acc>
      : ParseError<"expected a parameter value after '='", I>
  : ParseError<"unexpected end of input in a parameter", I>;

// Reading a token parameter value.
type NextParamValueToken<
  I extends string,
  Ty extends string,
  Sub extends string,
  Nm extends string,
  Vl extends string,
  Ps extends Params,
  Q,
  Acc extends AcceptItem[],
> = I extends `${infer C}${infer R}`
  ? C extends Tchar
    ? State<R, "paramValueToken", Ty, Sub, Nm, `${Vl}${C}`, Ps, Q, Acc>
    : FinishParam<I, Ty, Sub, Nm, Vl, false, Ps, Q, Acc>
  : FinishParam<I, Ty, Sub, Nm, Vl, false, Ps, Q, Acc>;

// Inside a quoted-string: `quoted-string = DQUOTE *( qdtext / quoted-pair ) DQUOTE`.
type NextParamValueQuoted<
  I extends string,
  Ty extends string,
  Sub extends string,
  Nm extends string,
  Vl extends string,
  Ps extends Params,
  Q,
  Acc extends AcceptItem[],
> = I extends `${infer C}${infer R}`
  ? C extends '"'
    ? FinishParam<R, Ty, Sub, Nm, Vl, true, Ps, Q, Acc>
    : C extends "\\"
      ? State<R, "paramValueQuotedPair", Ty, Sub, Nm, Vl, Ps, Q, Acc>
      : C extends CtlChar
        ? ParseError<"control character in a quoted-string", I>
        : State<R, "paramValueQuoted", Ty, Sub, Nm, `${Vl}${C}`, Ps, Q, Acc>
  : ParseError<"unterminated quoted-string", I>;

// After a "\" in a quoted-string: `quoted-pair = "\" ( HTAB / SP / VCHAR / obs-text )`,
// handled as if replaced by the character following the backslash.
type NextParamValueQuotedPair<
  I extends string,
  Ty extends string,
  Sub extends string,
  Nm extends string,
  Vl extends string,
  Ps extends Params,
  Q,
  Acc extends AcceptItem[],
> = I extends `${infer C}${infer R}`
  ? C extends CtlChar
    ? ParseError<"control character in a quoted-pair", I>
    : State<R, "paramValueQuoted", Ty, Sub, Nm, `${Vl}${C}`, Ps, Q, Acc>
  : ParseError<"unterminated quoted-string", I>;

// Stores a finished parameter. A parameter named "q" (case-insensitive) is the weight
// regardless of its position (Section 12.5.1); `weight = OWS ";" OWS "q=" qvalue`
// admits neither a quoted-string nor anything but a qvalue.
type FinishParam<
  I extends string,
  Ty extends string,
  Sub extends string,
  Nm extends string,
  Vl extends string,
  Quoted extends boolean,
  Ps extends Params,
  Q,
  Acc extends AcceptItem[],
> =
  Lowercase<Nm> extends "q"
    ? Quoted extends true
      ? ParseError<"weight must be an unquoted qvalue", I>
      : IsQvalue<Vl> extends true
        ? State<I, "params", Ty, Sub, "", "", Ps, Vl, Acc>
        : ParseError<"invalid qvalue", I>
    : State<I, "params", Ty, Sub, "", "", [...Ps, [Lowercase<Nm>, Vl]], Q, Acc>;

// ---------------------------------------------------------------------------
// The driver

/**
 * `Run<S>` steps the machine until it leaves the state space (i.e. `Next` returns the
 * results tuple or a `ParseError`).
 */
type Run<S> = S extends { mode: unknown } ? Run<Next<S>> : S;

/**
 * `ParseAccept<Input>` parses an `Accept` header field value into a tuple of
 * `AcceptItem`s, or a `ParseError` if the value does not match the RFC 9110 grammar.
 *
 * For example, `ParseAccept<"text/html;level=1, image/svg+xml;q=0.5">` is
 * `[{ type: "text"; subtype: "html"; params: [["level", "1"]]; q: "1" },
 *   { type: "image"; subtype: "svg+xml"; params: []; q: "0.5" }]`.
 */
export type ParseAccept<Input extends string> = string extends Input
  ? AcceptItem[] | ParseError
  : Input extends unknown
    ? Run<Init<Input>>
    : never;

// ---------------------------------------------------------------------------
// Content negotiation (Section 12)

/**
 * An invalid candidate given to `Negotiate`. Unlike `ParseError`, this indicates a bug
 * on the server side (the candidate list is authored by the server), not a bad request.
 */
export type NegotiateError<Message extends string = string, Candidate extends string = string> = {
  error: Message;
  candidate: Candidate;
};

// Normalizes a qvalue into four digits ("1" -> "1000", "0.8" -> "0800") so that
// qvalues can be compared digit by digit.
type NormalizeQvalue<Q extends string> = Q extends `${infer Int}.${infer Frac}`
  ? `${Int}${PadFraction<Frac>}`
  : `${Q}000`;

// Pads the fractional part of a qvalue (at most three digits) to exactly three.
type PadFraction<F extends string> = F extends `${infer _1}${infer R1}`
  ? R1 extends `${infer _2}${infer R2}`
    ? R2 extends `${infer _3}${infer _R3}`
      ? F
      : `${F}0`
    : `${F}00`
  : "000";

// A weight of 0 means "not acceptable" (Section 12.4.2).
type IsZeroQvalue<Q extends string> = NormalizeQvalue<Q> extends "0000" ? true : false;

type Ordering = "lt" | "eq" | "gt";

// DigitsAbove[D] is the set of digits greater than D.
type DigitsAbove = {
  "0": "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";
  "1": "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";
  "2": "3" | "4" | "5" | "6" | "7" | "8" | "9";
  "3": "4" | "5" | "6" | "7" | "8" | "9";
  "4": "5" | "6" | "7" | "8" | "9";
  "5": "6" | "7" | "8" | "9";
  "6": "7" | "8" | "9";
  "7": "8" | "9";
  "8": "9";
  "9": never;
};

type CompareDigit<A extends Digit, B extends Digit> = A extends B
  ? "eq"
  : B extends DigitsAbove[A]
    ? "lt"
    : "gt";

// Compares two equal-length digit strings lexicographically.
type CompareDigits<
  A extends string,
  B extends string,
> = A extends `${infer AH extends Digit}${infer AR}`
  ? B extends `${infer BH extends Digit}${infer BR}`
    ? CompareDigit<AH, BH> extends infer O extends Ordering
      ? O extends "eq"
        ? CompareDigits<AR, BR>
        : O
      : never
    : "eq"
  : "eq";

// Compares two qvalues numerically.
type CompareQvalue<A extends string, B extends string> = CompareDigits<
  NormalizeQvalue<A>,
  NormalizeQvalue<B>
>;

// A successful match of a media range against a candidate media type. `rank` encodes
// the shape of the range: "0" for */*, "1" for type/*, and "2" for type/subtype. A
// range is more specific than another if its rank is greater, or the ranks are equal
// and it has more parameters (Section 12.5.1: "the most specific reference has
// precedence").
type RangeMatch = {
  rank: "0" | "1" | "2";
  params: Params;
  q: string;
};

// Matches the media range `It` against the concrete candidate `C`: the range's type
// and subtype must equal or cover the candidate's, and every [name, value] parameter
// of the range must be present among the candidate's parameters (values are compared
// case-sensitively; names were already lowercased by the parser). The `[X] extends [Y]`
// test over the unions of pairs checks elementwise membership without recursion. A
// range like */x (grammatically token "/" subtype) is taken literally and thus matches
// no concrete candidate.
type MatchRange<It extends AcceptItem, C extends AcceptItem> = It extends {
  type: "*";
  subtype: "*";
}
  ? MatchedRange<It, "0", C>
  : It["subtype"] extends "*"
    ? It["type"] extends C["type"]
      ? MatchedRange<It, "1", C>
      : null
    : It["type"] extends C["type"]
      ? It["subtype"] extends C["subtype"]
        ? MatchedRange<It, "2", C>
        : null
      : null;

type MatchedRange<It extends AcceptItem, Rank extends RangeMatch["rank"], C extends AcceptItem> = [
  It["params"][number],
] extends [C["params"][number]]
  ? { rank: Rank; params: It["params"]; q: It["q"] }
  : null;

// Compares the specificity of two matched ranges: by rank, then by the number of
// parameters.
type CompareSpecificity<A extends RangeMatch, B extends RangeMatch> =
  CompareDigit<A["rank"], B["rank"]> extends infer O extends Ordering
    ? O extends "eq"
      ? CompareLength<A["params"], B["params"]>
      : O
    : never;

type CompareLength<A extends unknown[], B extends unknown[]> = A extends [unknown, ...infer AR]
  ? B extends [unknown, ...infer BR]
    ? CompareLength<AR, BR>
    : "gt"
  : B extends [unknown, ...unknown[]]
    ? "lt"
    : "eq";

// `SelectRange<Items, C>` finds the media range with the highest precedence that
// matches the candidate `C`; among equally specific ranges the first one wins.
type SelectRange<
  Items extends AcceptItem[],
  C extends AcceptItem,
  Best extends RangeMatch | null = null,
> = Items extends [infer It extends AcceptItem, ...infer Rest extends AcceptItem[]]
  ? SelectRange<Rest, C, BetterRange<Best, MatchRange<It, C>>>
  : Best;

type BetterRange<Best extends RangeMatch | null, M extends RangeMatch | null> = M extends RangeMatch
  ? Best extends RangeMatch
    ? CompareSpecificity<M, Best> extends "gt"
      ? M
      : Best
    : M
  : Best;

// Evaluates one candidate against the parsed elements: its weight (a qvalue string) if
// acceptable, null if not acceptable (no matching range, or the matched weight is 0),
// or an error for an invalid candidate. A candidate must be a single, concrete media
// type without a weight (an explicit "q=1" is indistinguishable from no weight and is
// tolerated).
type EvaluateCandidate<C extends string, Items extends AcceptItem[]> =
  ParseAccept<C> extends infer P
    ? P extends ParseError
      ? P
      : P extends [infer It extends AcceptItem]
        ? "*" extends It["type"] | It["subtype"]
          ? NegotiateError<"a candidate must be a concrete media type", C>
          : It["q"] extends "1"
            ? SelectRange<Items, It> extends infer M
              ? M extends RangeMatch
                ? IsZeroQvalue<M["q"]> extends true
                  ? null
                  : M["q"]
                : null
              : never
            : NegotiateError<"a candidate must not have a weight", C>
        : NegotiateError<"a candidate must be exactly one media type", C>
    : never;

// Folds over the candidates, keeping the first one with the greatest weight. The
// candidate list is server-authored and short, so plain recursion suffices here.
type NegotiateSub<
  Items extends AcceptItem[],
  Cs extends string[],
  Best extends { candidate: string; q: string } | null,
> = Cs extends [infer C extends string, ...infer Rest extends string[]]
  ? EvaluateCandidate<C, Items> extends infer R
    ? R extends { error: string }
      ? R
      : R extends string
        ? Best extends { q: infer BQ extends string }
          ? CompareQvalue<R, BQ> extends "gt"
            ? NegotiateSub<Items, Rest, { candidate: C; q: R }>
            : NegotiateSub<Items, Rest, Best>
          : NegotiateSub<Items, Rest, { candidate: C; q: R }>
        : NegotiateSub<Items, Rest, Best>
    : never
  : Best extends { candidate: infer BC extends string }
    ? BC
    : null;

/**
 * `Negotiate<Header, Candidates>` performs proactive content negotiation (Section 12):
 * given an `Accept` header field value and the media types the server can produce
 * (written as they would appear in `Content-Type`, e.g. `"text/html;charset=utf-8"`),
 * it returns the candidate the client prefers most.
 *
 * - The weight of a candidate is that of the most specific media range matching it
 *   (Section 12.5.1). A range with parameters applies only to candidates having all of
 *   those parameters.
 * - The candidate with the greatest weight is returned; ties are broken in favor of
 *   the one listed first, so `Candidates` should be ordered by the server's own
 *   preference.
 * - `Header` being `undefined` means the header field is absent, i.e. the client has
 *   no preference (Section 12.4.1), and the first candidate is returned.
 * - `null` means no candidate is acceptable; the caller decides between a 406 response
 *   and disregarding the header field (Section 12.4.1).
 * - A malformed header field value yields its `ParseError`, and an invalid candidate a
 *   `NegotiateError`.
 *
 * For example, `Negotiate<"text/html;q=0.8, application/json", ["text/html", "application/json"]>`
 * is `"application/json"`.
 */
export type Negotiate<
  Header extends string | undefined,
  Candidates extends string[],
> = Header extends undefined
  ? NegotiateSub<[{ type: "*"; subtype: "*"; params: []; q: "1" }], Candidates, null>
  : Header extends string
    ? string extends Header
      ? Candidates[number] | null | ParseError
      : ParseAccept<Header> extends infer P
        ? P extends ParseError
          ? P
          : P extends AcceptItem[]
            ? NegotiateSub<P, Candidates, null>
            : never
        : never
    : never;