{"version":3,"file":"route-trie.js","names":[],"sources":["../../src/routing/route-trie.ts"],"sourcesContent":["import { decodeMatchedParams } from \"./utils\";\n\n/**\n * Trie (prefix tree) for O(depth) route matching.\n *\n * Replaces the O(n) linear scan over pre-sorted routes with a trie-based\n * lookup. Priority is enforced by traversal order at each node:\n *   1. Static child (exact segment match) — highest priority\n *   2. Dynamic child (single-segment param) — medium\n *   3. Catch-all (1+ remaining segments) — low\n *   4. Optional catch-all (0+ remaining segments) — lowest\n *\n * Backtracking via recursive DFS ensures that dead-end static/dynamic\n * branches fall through to catch-all alternatives.\n */\n\nexport type TrieNode<R> = {\n  staticChildren: Map<string, TrieNode<R>>;\n  dynamicChild: { paramName: string; node: TrieNode<R> } | null;\n  catchAllChild: { paramName: string; route: R } | null;\n  optionalCatchAllChild: { paramName: string; route: R } | null;\n  route: R | null;\n};\n\nfunction createNode<R>(): TrieNode<R> {\n  return {\n    staticChildren: new Map(),\n    dynamicChild: null,\n    catchAllChild: null,\n    optionalCatchAllChild: null,\n    route: null,\n  };\n}\n\n/**\n * Build a trie from pre-sorted routes.\n *\n * Routes must have a `patternParts` property (string[] of URL segments).\n * Pattern segment conventions:\n *   - `:name`  — dynamic segment\n *   - `:name+` — catch-all (1+ segments)\n *   - `:name*` — optional catch-all (0+ segments)\n *   - anything else — static segment\n *\n * First route to claim a terminal position wins (routes are pre-sorted\n * by precedence, so insertion order preserves correct priority).\n */\nexport function buildRouteTrie<R extends { patternParts: string[] }>(routes: R[]): TrieNode<R> {\n  const root = createNode<R>();\n\n  for (const route of routes) {\n    const parts = route.patternParts;\n\n    // Root route (patternParts = [])\n    if (parts.length === 0) {\n      if (root.route === null) {\n        root.route = route;\n      }\n      continue;\n    }\n\n    let node = root;\n\n    for (let i = 0; i < parts.length; i++) {\n      const part = parts[i];\n\n      // Catch-all: :name+ (must be terminal — skip malformed non-terminal catch-alls)\n      if (part.endsWith(\"+\") && part.startsWith(\":\")) {\n        if (i !== parts.length - 1) break; // malformed: not terminal\n        const paramName = part.slice(1, -1);\n        if (node.catchAllChild === null) {\n          node.catchAllChild = { paramName, route };\n        }\n        break;\n      }\n\n      // Optional catch-all: :name* (must be terminal — skip malformed non-terminal)\n      if (part.endsWith(\"*\") && part.startsWith(\":\")) {\n        if (i !== parts.length - 1) break; // malformed: not terminal\n        const paramName = part.slice(1, -1);\n        if (node.optionalCatchAllChild === null) {\n          node.optionalCatchAllChild = { paramName, route };\n        }\n        break;\n      }\n\n      // Dynamic segment: :name\n      if (part.startsWith(\":\")) {\n        const paramName = part.slice(1);\n        if (node.dynamicChild === null) {\n          node.dynamicChild = { paramName, node: createNode<R>() };\n        }\n        node = node.dynamicChild.node;\n\n        // If this is the last segment, set the route\n        if (i === parts.length - 1) {\n          if (node.route === null) {\n            node.route = route;\n          }\n        }\n        continue;\n      }\n\n      // Static segment\n      let child = node.staticChildren.get(part);\n      if (!child) {\n        child = createNode<R>();\n        node.staticChildren.set(part, child);\n      }\n      node = child;\n\n      // If this is the last segment, set the route\n      if (i === parts.length - 1) {\n        if (node.route === null) {\n          node.route = route;\n        }\n      }\n    }\n  }\n\n  return root;\n}\n\n/**\n * Match a URL against the trie.\n *\n * Returns decoded param values — `decodeURIComponent` is applied to\n * individual param entries so that `%2F` → `/`, `%23` → `#`, etc.\n * Segment boundaries (the original `/` splits) are preserved by the\n * upstream normalization layer; this step only decodes the captured\n * param strings the caller sees.\n *\n * Mirrors Next.js route-matcher.ts:25-27.\n *\n * @param root - Trie root built by `buildRouteTrie`\n * @param urlParts - Pre-split URL segments (no empty strings)\n * @returns Match result with route and extracted params, or null\n */\nexport function trieMatch<R>(\n  root: TrieNode<R>,\n  urlParts: string[],\n): { route: R; params: Record<string, string | string[]> } | null {\n  const result = match(root, urlParts, 0);\n  if (result) {\n    decodeMatchedParams(result.params);\n  }\n  return result;\n}\n\nfunction createParams(): Record<string, string | string[]> {\n  return Object.create(null);\n}\n\nfunction match<R>(\n  node: TrieNode<R>,\n  urlParts: string[],\n  index: number,\n): { route: R; params: Record<string, string | string[]> } | null {\n  // All URL segments consumed\n  if (index === urlParts.length) {\n    // Exact match at this node\n    if (node.route !== null) {\n      return { route: node.route, params: createParams() };\n    }\n\n    // Optional catch-all with 0 segments\n    if (node.optionalCatchAllChild !== null) {\n      return {\n        route: node.optionalCatchAllChild.route,\n        params: createParams(),\n      };\n    }\n\n    return null;\n  }\n\n  const segment = urlParts[index];\n\n  // 1. Try static child (highest priority)\n  const staticChild = node.staticChildren.get(segment);\n  if (staticChild) {\n    const result = match(staticChild, urlParts, index + 1);\n    if (result !== null) {\n      return result;\n    }\n  }\n\n  // 2. Try dynamic child (single segment)\n  if (node.dynamicChild !== null) {\n    const result = match(node.dynamicChild.node, urlParts, index + 1);\n    if (result !== null) {\n      result.params[node.dynamicChild.paramName] = segment;\n      return result;\n    }\n  }\n\n  // 3. Try catch-all (1+ remaining segments)\n  if (node.catchAllChild !== null) {\n    const remaining = urlParts.slice(index);\n    const params = createParams();\n    params[node.catchAllChild.paramName] = remaining;\n    return { route: node.catchAllChild.route, params };\n  }\n\n  // 4. Try optional catch-all (0+ remaining segments)\n  if (node.optionalCatchAllChild !== null) {\n    const remaining = urlParts.slice(index);\n    const params = createParams();\n    params[node.optionalCatchAllChild.paramName] = remaining;\n    return { route: node.optionalCatchAllChild.route, params };\n  }\n\n  return null;\n}\n"],"mappings":";;AAwBA,SAAS,aAA6B;CACpC,OAAO;EACL,gCAAgB,IAAI,KAAK;EACzB,cAAc;EACd,eAAe;EACf,uBAAuB;EACvB,OAAO;EACR;;;;;;;;;;;;;;;AAgBH,SAAgB,eAAqD,QAA0B;CAC7F,MAAM,OAAO,YAAe;CAE5B,KAAK,MAAM,SAAS,QAAQ;EAC1B,MAAM,QAAQ,MAAM;EAGpB,IAAI,MAAM,WAAW,GAAG;GACtB,IAAI,KAAK,UAAU,MACjB,KAAK,QAAQ;GAEf;;EAGF,IAAI,OAAO;EAEX,KAAK,IAAI,IAAI,GAAG,IAAI,MAAM,QAAQ,KAAK;GACrC,MAAM,OAAO,MAAM;GAGnB,IAAI,KAAK,SAAS,IAAI,IAAI,KAAK,WAAW,IAAI,EAAE;IAC9C,IAAI,MAAM,MAAM,SAAS,GAAG;IAC5B,MAAM,YAAY,KAAK,MAAM,GAAG,GAAG;IACnC,IAAI,KAAK,kBAAkB,MACzB,KAAK,gBAAgB;KAAE;KAAW;KAAO;IAE3C;;GAIF,IAAI,KAAK,SAAS,IAAI,IAAI,KAAK,WAAW,IAAI,EAAE;IAC9C,IAAI,MAAM,MAAM,SAAS,GAAG;IAC5B,MAAM,YAAY,KAAK,MAAM,GAAG,GAAG;IACnC,IAAI,KAAK,0BAA0B,MACjC,KAAK,wBAAwB;KAAE;KAAW;KAAO;IAEnD;;GAIF,IAAI,KAAK,WAAW,IAAI,EAAE;IACxB,MAAM,YAAY,KAAK,MAAM,EAAE;IAC/B,IAAI,KAAK,iBAAiB,MACxB,KAAK,eAAe;KAAE;KAAW,MAAM,YAAe;KAAE;IAE1D,OAAO,KAAK,aAAa;IAGzB,IAAI,MAAM,MAAM,SAAS;SACnB,KAAK,UAAU,MACjB,KAAK,QAAQ;;IAGjB;;GAIF,IAAI,QAAQ,KAAK,eAAe,IAAI,KAAK;GACzC,IAAI,CAAC,OAAO;IACV,QAAQ,YAAe;IACvB,KAAK,eAAe,IAAI,MAAM,MAAM;;GAEtC,OAAO;GAGP,IAAI,MAAM,MAAM,SAAS;QACnB,KAAK,UAAU,MACjB,KAAK,QAAQ;;;;CAMrB,OAAO;;;;;;;;;;;;;;;;;AAkBT,SAAgB,UACd,MACA,UACgE;CAChE,MAAM,SAAS,MAAM,MAAM,UAAU,EAAE;CACvC,IAAI,QACF,oBAAoB,OAAO,OAAO;CAEpC,OAAO;;AAGT,SAAS,eAAkD;CACzD,OAAO,OAAO,OAAO,KAAK;;AAG5B,SAAS,MACP,MACA,UACA,OACgE;CAEhE,IAAI,UAAU,SAAS,QAAQ;EAE7B,IAAI,KAAK,UAAU,MACjB,OAAO;GAAE,OAAO,KAAK;GAAO,QAAQ,cAAc;GAAE;EAItD,IAAI,KAAK,0BAA0B,MACjC,OAAO;GACL,OAAO,KAAK,sBAAsB;GAClC,QAAQ,cAAc;GACvB;EAGH,OAAO;;CAGT,MAAM,UAAU,SAAS;CAGzB,MAAM,cAAc,KAAK,eAAe,IAAI,QAAQ;CACpD,IAAI,aAAa;EACf,MAAM,SAAS,MAAM,aAAa,UAAU,QAAQ,EAAE;EACtD,IAAI,WAAW,MACb,OAAO;;CAKX,IAAI,KAAK,iBAAiB,MAAM;EAC9B,MAAM,SAAS,MAAM,KAAK,aAAa,MAAM,UAAU,QAAQ,EAAE;EACjE,IAAI,WAAW,MAAM;GACnB,OAAO,OAAO,KAAK,aAAa,aAAa;GAC7C,OAAO;;;CAKX,IAAI,KAAK,kBAAkB,MAAM;EAC/B,MAAM,YAAY,SAAS,MAAM,MAAM;EACvC,MAAM,SAAS,cAAc;EAC7B,OAAO,KAAK,cAAc,aAAa;EACvC,OAAO;GAAE,OAAO,KAAK,cAAc;GAAO;GAAQ;;CAIpD,IAAI,KAAK,0BAA0B,MAAM;EACvC,MAAM,YAAY,SAAS,MAAM,MAAM;EACvC,MAAM,SAAS,cAAc;EAC7B,OAAO,KAAK,sBAAsB,aAAa;EAC/C,OAAO;GAAE,OAAO,KAAK,sBAAsB;GAAO;GAAQ;;CAG5D,OAAO"}