{"version":3,"sources":["../../../../src/client/components/segment-cache-impl/scheduler.ts"],"sourcesContent":["import type {\n  FlightRouterState,\n  Segment as FlightRouterStateSegment,\n  Segment,\n} from '../../../shared/lib/app-router-types'\nimport { HasLoadingBoundary } from '../../../shared/lib/app-router-types'\nimport { matchSegment } from '../match-segments'\nimport {\n  readOrCreateRouteCacheEntry,\n  readOrCreateSegmentCacheEntry,\n  fetchRouteOnCacheMiss,\n  fetchSegmentOnCacheMiss,\n  EntryStatus,\n  type FulfilledRouteCacheEntry,\n  type RouteCacheEntry,\n  type SegmentCacheEntry,\n  type RouteTree,\n  fetchSegmentPrefetchesUsingDynamicRequest,\n  type PendingSegmentCacheEntry,\n  convertRouteTreeToFlightRouterState,\n  readOrCreateRevalidatingSegmentEntry,\n  upsertSegmentEntry,\n  type FulfilledSegmentCacheEntry,\n  upgradeToPendingSegment,\n  waitForSegmentCacheEntry,\n  resetRevalidatingSegmentEntry,\n  getSegmentKeypath,\n  canNewFetchStrategyProvideMoreContent,\n} from './cache'\nimport type { RouteCacheKey } from './cache-key'\nimport { createCacheKey } from './cache-key'\nimport {\n  FetchStrategy,\n  type PrefetchTaskFetchStrategy,\n  getCurrentCacheVersion,\n  PrefetchPriority,\n} from '../segment-cache'\nimport {\n  addSearchParamsIfPageSegment,\n  PAGE_SEGMENT_KEY,\n} from '../../../shared/lib/segment'\nimport type { SegmentCacheKey } from '../../../shared/lib/segment-cache/segment-value-encoding'\n\nconst scheduleMicrotask =\n  typeof queueMicrotask === 'function'\n    ? queueMicrotask\n    : (fn: () => unknown) =>\n        Promise.resolve()\n          .then(fn)\n          .catch((error) =>\n            setTimeout(() => {\n              throw error\n            })\n          )\n\nexport type PrefetchTask = {\n  key: RouteCacheKey\n\n  /**\n   * The FlightRouterState at the time the task was initiated. This is needed\n   * when falling back to the non-PPR behavior, which only prefetches up to\n   * the first loading boundary.\n   */\n  treeAtTimeOfPrefetch: FlightRouterState\n\n  /**\n   * The cache version at the time the task was initiated. This is used to\n   * determine if the cache was invalidated since the task was initiated.\n   */\n  cacheVersion: number\n\n  /**\n   * Whether to prefetch dynamic data, in addition to static data. This is\n   * used by `<Link prefetch={true}>`.\n   *\n   * Note that a task with `FetchStrategy.PPR` might need to use\n   * `FetchStrategy.LoadingBoundary` instead if we find out that a route\n   * does not support PPR after doing the initial route prefetch.\n   */\n  fetchStrategy: PrefetchTaskFetchStrategy\n\n  /**\n   * sortId is an incrementing counter\n   *\n   * Newer prefetches are prioritized over older ones, so that as new links\n   * enter the viewport, they are not starved by older links that are no\n   * longer relevant. In the future, we can add additional prioritization\n   * heuristics, like removing prefetches once a link leaves the viewport.\n   *\n   * The sortId is assigned when the prefetch is initiated, and reassigned if\n   * the same task is prefetched again (effectively bumping it to the top of\n   * the queue).\n   *\n   * TODO: We can add additional fields here to indicate what kind of prefetch\n   * it is. For example, was it initiated by a link? Or was it an imperative\n   * call? If it was initiated by a link, we can remove it from the queue when\n   * the link leaves the viewport, but if it was an imperative call, then we\n   * should keep it in the queue until it's fulfilled.\n   *\n   * We can also add priority levels. For example, hovering over a link could\n   * increase the priority of its prefetch.\n   */\n  sortId: number\n\n  /**\n   * The priority of the task. Like sortId, this affects the task's position in\n   * the queue, so it must never be updated without resifting the heap.\n   */\n  priority: PrefetchPriority\n\n  /**\n   * The phase of the task. Tasks are split into multiple phases so that their\n   * priority can be adjusted based on what kind of work they're doing.\n   * Concretely, prefetching the route tree is higher priority than prefetching\n   * segment data.\n   */\n  phase: PrefetchPhase\n\n  /**\n   * These fields are temporary state for tracking the currently running task.\n   * They are reset after each iteration of the task queue.\n   */\n  hasBackgroundWork: boolean\n  spawnedRuntimePrefetches: Set<SegmentCacheKey> | null\n\n  /**\n   * True if the prefetch was cancelled.\n   */\n  isCanceled: boolean\n\n  /**\n   * The callback passed to `router.prefetch`, if given.\n   */\n  onInvalidate: null | (() => void)\n\n  /**\n   * The index of the task in the heap's backing array. Used to efficiently\n   * change the priority of a task by re-sifting it, which requires knowing\n   * where it is in the array. This is only used internally by the heap\n   * algorithm. The naive alternative is indexOf every time a task is queued,\n   * which has O(n) complexity.\n   *\n   * We also use this field to check whether a task is currently in the queue.\n   */\n  _heapIndex: number\n}\n\nconst enum PrefetchTaskExitStatus {\n  /**\n   * The task yielded because there are too many requests in progress.\n   */\n  InProgress,\n\n  /**\n   * The task is blocked. It needs more data before it can proceed.\n   *\n   * Currently the only reason this happens is we're still waiting to receive a\n   * route tree from the server, because we can't start prefetching the segments\n   * until we know what to prefetch.\n   */\n  Blocked,\n\n  /**\n   * There's nothing left to prefetch.\n   */\n  Done,\n}\n\n/**\n * Prefetch tasks are processed in two phases: first the route tree is fetched,\n * then the segments. We use this to priortize tasks that have not yet fetched\n * the route tree.\n */\nconst enum PrefetchPhase {\n  RouteTree = 1,\n  Segments = 0,\n}\n\nexport type PrefetchSubtaskResult<T> = {\n  /**\n   * A promise that resolves when the network connection is closed.\n   */\n  closed: Promise<void>\n  value: T\n}\n\nconst taskHeap: Array<PrefetchTask> = []\n\nlet inProgressRequests = 0\n\nlet sortIdCounter = 0\nlet didScheduleMicrotask = false\n\n// The most recently hovered (or touched, etc) link, i.e. the most recent task\n// scheduled at Intent priority. There's only ever a single task at Intent\n// priority at a time. We reserve special network bandwidth for this task only.\nlet mostRecentlyHoveredLink: PrefetchTask | null = null\n\n// CDN cache propagation delay after revalidation (in milliseconds)\nconst REVALIDATION_COOLDOWN_MS = 300\n\n// Timeout handle for the revalidation cooldown. When non-null, prefetch\n// requests are blocked to allow CDN cache propagation.\nlet revalidationCooldownTimeoutHandle: ReturnType<typeof setTimeout> | null =\n  null\n\n/**\n * Called by the cache when revalidation occurs. Starts a cooldown period\n * during which prefetch requests are blocked to allow CDN cache propagation.\n */\nexport function startRevalidationCooldown(): void {\n  // Clear any existing timeout in case multiple revalidations happen\n  // in quick succession.\n  if (revalidationCooldownTimeoutHandle !== null) {\n    clearTimeout(revalidationCooldownTimeoutHandle)\n  }\n\n  // Schedule the cooldown to expire after the delay.\n  revalidationCooldownTimeoutHandle = setTimeout(() => {\n    revalidationCooldownTimeoutHandle = null\n    // Retry the prefetch queue now that the cooldown has expired.\n    ensureWorkIsScheduled()\n  }, REVALIDATION_COOLDOWN_MS)\n}\n\nexport type IncludeDynamicData = null | 'full' | 'dynamic'\n\n/**\n * Initiates a prefetch task for the given URL. If a prefetch for the same URL\n * is already in progress, this will bump it to the top of the queue.\n *\n * This is not a user-facing function. By the time this is called, the href is\n * expected to be validated and normalized.\n *\n * @param key The RouteCacheKey to prefetch.\n * @param treeAtTimeOfPrefetch The app's current FlightRouterState\n * @param fetchStrategy Whether to prefetch dynamic data, in addition to\n * static data. This is used by `<Link prefetch={true}>`.\n */\nexport function schedulePrefetchTask(\n  key: RouteCacheKey,\n  treeAtTimeOfPrefetch: FlightRouterState,\n  fetchStrategy: PrefetchTaskFetchStrategy,\n  priority: PrefetchPriority,\n  onInvalidate: null | (() => void)\n): PrefetchTask {\n  // Spawn a new prefetch task\n  const task: PrefetchTask = {\n    key,\n    treeAtTimeOfPrefetch,\n    cacheVersion: getCurrentCacheVersion(),\n    priority,\n    phase: PrefetchPhase.RouteTree,\n    hasBackgroundWork: false,\n    spawnedRuntimePrefetches: null,\n    fetchStrategy,\n    sortId: sortIdCounter++,\n    isCanceled: false,\n    onInvalidate,\n    _heapIndex: -1,\n  }\n\n  trackMostRecentlyHoveredLink(task)\n\n  heapPush(taskHeap, task)\n\n  // Schedule an async task to process the queue.\n  //\n  // The main reason we process the queue in an async task is for batching.\n  // It's common for a single JS task/event to trigger multiple prefetches.\n  // By deferring to a microtask, we only process the queue once per JS task.\n  // If they have different priorities, it also ensures they are processed in\n  // the optimal order.\n  ensureWorkIsScheduled()\n\n  return task\n}\n\nexport function cancelPrefetchTask(task: PrefetchTask): void {\n  // Remove the prefetch task from the queue. If the task already completed,\n  // then this is a no-op.\n  //\n  // We must also explicitly mark the task as canceled so that a blocked task\n  // does not get added back to the queue when it's pinged by the network.\n  task.isCanceled = true\n  heapDelete(taskHeap, task)\n}\n\nexport function reschedulePrefetchTask(\n  task: PrefetchTask,\n  treeAtTimeOfPrefetch: FlightRouterState,\n  fetchStrategy: PrefetchTaskFetchStrategy,\n  priority: PrefetchPriority\n): void {\n  // Bump the prefetch task to the top of the queue, as if it were a fresh\n  // task. This is essentially the same as canceling the task and scheduling\n  // a new one, except it reuses the original object.\n  //\n  // The primary use case is to increase the priority of a Link-initated\n  // prefetch on hover.\n\n  // Un-cancel the task, in case it was previously canceled.\n  task.isCanceled = false\n  task.phase = PrefetchPhase.RouteTree\n\n  // Assign a new sort ID to move it ahead of all other tasks at the same\n  // priority level. (Higher sort IDs are processed first.)\n  task.sortId = sortIdCounter++\n  task.priority =\n    // If this task is the most recently hovered link, maintain its\n    // Intent priority, even if the rescheduled priority is lower.\n    task === mostRecentlyHoveredLink ? PrefetchPriority.Intent : priority\n\n  task.treeAtTimeOfPrefetch = treeAtTimeOfPrefetch\n  task.fetchStrategy = fetchStrategy\n\n  trackMostRecentlyHoveredLink(task)\n\n  if (task._heapIndex !== -1) {\n    // The task is already in the queue.\n    heapResift(taskHeap, task)\n  } else {\n    heapPush(taskHeap, task)\n  }\n  ensureWorkIsScheduled()\n}\n\nexport function isPrefetchTaskDirty(\n  task: PrefetchTask,\n  nextUrl: string | null,\n  tree: FlightRouterState\n): boolean {\n  // This is used to quickly bail out of a prefetch task if the result is\n  // guaranteed to not have changed since the task was initiated. This is\n  // strictly an optimization — theoretically, if it always returned true, no\n  // behavior should change because a full prefetch task will effectively\n  // perform the same checks.\n  const currentCacheVersion = getCurrentCacheVersion()\n  return (\n    task.cacheVersion !== currentCacheVersion ||\n    task.treeAtTimeOfPrefetch !== tree ||\n    task.key.nextUrl !== nextUrl\n  )\n}\n\nfunction trackMostRecentlyHoveredLink(task: PrefetchTask) {\n  // Track the mostly recently hovered link, i.e. the most recently scheduled\n  // task at Intent priority. There must only be one such task at a time.\n  if (\n    task.priority === PrefetchPriority.Intent &&\n    task !== mostRecentlyHoveredLink\n  ) {\n    if (mostRecentlyHoveredLink !== null) {\n      // Bump the previously hovered link's priority down to Default.\n      if (mostRecentlyHoveredLink.priority !== PrefetchPriority.Background) {\n        mostRecentlyHoveredLink.priority = PrefetchPriority.Default\n        heapResift(taskHeap, mostRecentlyHoveredLink)\n      }\n    }\n    mostRecentlyHoveredLink = task\n  }\n}\n\nfunction ensureWorkIsScheduled() {\n  if (didScheduleMicrotask) {\n    // Already scheduled a task to process the queue\n    return\n  }\n  didScheduleMicrotask = true\n  scheduleMicrotask(processQueueInMicrotask)\n}\n\n/**\n * Checks if we've exceeded the maximum number of concurrent prefetch requests,\n * to avoid saturating the browser's internal network queue. This is a\n * cooperative limit — prefetch tasks should check this before issuing\n * new requests.\n *\n * Also checks if we're within the revalidation cooldown window, during which\n * prefetch requests are delayed to allow CDN cache propagation.\n */\nfunction hasNetworkBandwidth(task: PrefetchTask): boolean {\n  // Check if we're within the revalidation cooldown window\n  if (revalidationCooldownTimeoutHandle !== null) {\n    // We're within the cooldown window. Return false to prevent prefetching.\n    // When the cooldown expires, the timeout will call ensureWorkIsScheduled()\n    // to retry the queue.\n    return false\n  }\n\n  // TODO: Also check if there's an in-progress navigation. We should never\n  // add prefetch requests to the network queue if an actual navigation is\n  // taking place, to ensure there's sufficient bandwidth for render-blocking\n  // data and resources.\n\n  // TODO: Consider reserving some amount of bandwidth for static prefetches.\n\n  if (task.priority === PrefetchPriority.Intent) {\n    // The most recently hovered link is allowed to exceed the default limit.\n    //\n    // The goal is to always have enough bandwidth to start a new prefetch\n    // request when hovering over a link.\n    //\n    // However, because we don't abort in-progress requests, it's still possible\n    // we'll run out of bandwidth. When links are hovered in quick succession,\n    // there could be multiple hover requests running simultaneously.\n    return inProgressRequests < 12\n  }\n\n  // The default limit is lower than the limit for a hovered link.\n  return inProgressRequests < 4\n}\n\nfunction spawnPrefetchSubtask<T>(\n  prefetchSubtask: Promise<PrefetchSubtaskResult<T> | null>\n): Promise<T | null> {\n  // When the scheduler spawns an async task, we don't await its result.\n  // Instead, the async task writes its result directly into the cache, then\n  // pings the scheduler to continue.\n  //\n  // We process server responses streamingly, so the prefetch subtask will\n  // likely resolve before we're finished receiving all the data. The subtask\n  // result includes a promise that resolves once the network connection is\n  // closed. The scheduler uses this to control network bandwidth by tracking\n  // and limiting the number of concurrent requests.\n  inProgressRequests++\n  return prefetchSubtask.then((result) => {\n    if (result === null) {\n      // The prefetch task errored before it could start processing the\n      // network stream. Assume the connection is closed.\n      onPrefetchConnectionClosed()\n      return null\n    }\n    // Wait for the connection to close before freeing up more bandwidth.\n    result.closed.then(onPrefetchConnectionClosed)\n    return result.value\n  })\n}\n\nfunction onPrefetchConnectionClosed(): void {\n  inProgressRequests--\n\n  // Notify the scheduler that we have more bandwidth, and can continue\n  // processing tasks.\n  ensureWorkIsScheduled()\n}\n\n/**\n * Notify the scheduler that we've received new data for an in-progress\n * prefetch. The corresponding task will be added back to the queue (unless the\n * task has been canceled in the meantime).\n */\nexport function pingPrefetchTask(task: PrefetchTask) {\n  // \"Ping\" a prefetch that's already in progress to notify it of new data.\n  if (\n    // Check if prefetch was canceled.\n    task.isCanceled ||\n    // Check if prefetch is already queued.\n    task._heapIndex !== -1\n  ) {\n    return\n  }\n  // Add the task back to the queue.\n  heapPush(taskHeap, task)\n  ensureWorkIsScheduled()\n}\n\nfunction processQueueInMicrotask() {\n  didScheduleMicrotask = false\n\n  // We aim to minimize how often we read the current time. Since nearly all\n  // functions in the prefetch scheduler are synchronous, we can read the time\n  // once and pass it as an argument wherever it's needed.\n  const now = Date.now()\n\n  // Process the task queue until we run out of network bandwidth.\n  let task = heapPeek(taskHeap)\n  while (task !== null && hasNetworkBandwidth(task)) {\n    task.cacheVersion = getCurrentCacheVersion()\n\n    const exitStatus = pingRoute(now, task)\n\n    // These fields are only valid for a single attempt. Reset them after each\n    // iteration of the task queue.\n    const hasBackgroundWork = task.hasBackgroundWork\n    task.hasBackgroundWork = false\n    task.spawnedRuntimePrefetches = null\n\n    switch (exitStatus) {\n      case PrefetchTaskExitStatus.InProgress:\n        // The task yielded because there are too many requests in progress.\n        // Stop processing tasks until we have more bandwidth.\n        return\n      case PrefetchTaskExitStatus.Blocked:\n        // The task is blocked. It needs more data before it can proceed.\n        // Keep the task out of the queue until the server responds.\n        heapPop(taskHeap)\n        // Continue to the next task\n        task = heapPeek(taskHeap)\n        continue\n      case PrefetchTaskExitStatus.Done:\n        if (task.phase === PrefetchPhase.RouteTree) {\n          // Finished prefetching the route tree. Proceed to prefetching\n          // the segments.\n          task.phase = PrefetchPhase.Segments\n          heapResift(taskHeap, task)\n        } else if (hasBackgroundWork) {\n          // The task spawned additional background work. Reschedule the task\n          // at background priority.\n          task.priority = PrefetchPriority.Background\n          heapResift(taskHeap, task)\n        } else {\n          // The prefetch is complete. Continue to the next task.\n          heapPop(taskHeap)\n        }\n        task = heapPeek(taskHeap)\n        continue\n      default:\n        exitStatus satisfies never\n    }\n  }\n}\n\n/**\n * Check this during a prefetch task to determine if background work can be\n * performed. If so, it evaluates to `true`. Otherwise, it returns `false`,\n * while also scheduling a background task to run later. Usage:\n *\n * @example\n * if (background(task)) {\n *   // Perform background-pri work\n * }\n */\nfunction background(task: PrefetchTask): boolean {\n  if (task.priority === PrefetchPriority.Background) {\n    return true\n  }\n  task.hasBackgroundWork = true\n  return false\n}\n\nfunction pingRoute(now: number, task: PrefetchTask): PrefetchTaskExitStatus {\n  const key = task.key\n  const route = readOrCreateRouteCacheEntry(now, task, key)\n  const exitStatus = pingRootRouteTree(now, task, route)\n\n  if (exitStatus !== PrefetchTaskExitStatus.InProgress && key.search !== '') {\n    // If the URL has a non-empty search string, also prefetch the pathname\n    // without the search string. We use the searchless route tree as a base for\n    // optimistic routing; see requestOptimisticRouteCacheEntry for details.\n    //\n    // Note that we don't need to prefetch any of the segment data. Just the\n    // route tree.\n    //\n    // TODO: This is a temporary solution; the plan is to replace this by adding\n    // a wildcard lookup method to the TupleMap implementation. This is\n    // non-trivial to implement because it needs to account for things like\n    // fallback route entries, hence this temporary workaround.\n    const url = new URL(key.href)\n    url.search = ''\n    const keyWithoutSearch = createCacheKey(url.href, key.nextUrl)\n    const routeWithoutSearch = readOrCreateRouteCacheEntry(\n      now,\n      task,\n      keyWithoutSearch\n    )\n    switch (routeWithoutSearch.status) {\n      case EntryStatus.Empty: {\n        if (background(task)) {\n          routeWithoutSearch.status = EntryStatus.Pending\n          spawnPrefetchSubtask(\n            fetchRouteOnCacheMiss(routeWithoutSearch, task, keyWithoutSearch)\n          )\n        }\n        break\n      }\n      case EntryStatus.Pending:\n      case EntryStatus.Fulfilled:\n      case EntryStatus.Rejected: {\n        // Either the route tree is already cached, or there's already a\n        // request in progress. Since we don't need to fetch any segment data\n        // for this route, there's nothing left to do.\n        break\n      }\n      default:\n        routeWithoutSearch satisfies never\n    }\n  }\n\n  return exitStatus\n}\n\nfunction pingRootRouteTree(\n  now: number,\n  task: PrefetchTask,\n  route: RouteCacheEntry\n): PrefetchTaskExitStatus {\n  switch (route.status) {\n    case EntryStatus.Empty: {\n      // Route is not yet cached, and there's no request already in progress.\n      // Spawn a task to request the route, load it into the cache, and ping\n      // the task to continue.\n\n      // TODO: There are multiple strategies in the <Link> API for prefetching\n      // a route. Currently we've only implemented the main one: per-segment,\n      // static-data only.\n      //\n      // There's also `<Link prefetch={true}>`\n      // which prefetch both static *and* dynamic data.\n      // Similarly, we need to fallback to the old, per-page\n      // behavior if PPR is disabled for a route (via the incremental opt-in).\n      //\n      // Those cases will be handled here.\n      spawnPrefetchSubtask(fetchRouteOnCacheMiss(route, task, task.key))\n\n      // If the request takes longer than a minute, a subsequent request should\n      // retry instead of waiting for this one. When the response is received,\n      // this value will be replaced by a new value based on the stale time sent\n      // from the server.\n      // TODO: We should probably also manually abort the fetch task, to reclaim\n      // server bandwidth.\n      route.staleAt = now + 60 * 1000\n\n      // Upgrade to Pending so we know there's already a request in progress\n      route.status = EntryStatus.Pending\n\n      // Intentional fallthrough to the Pending branch\n    }\n    case EntryStatus.Pending: {\n      // Still pending. We can't start prefetching the segments until the route\n      // tree has loaded. Add the task to the set of blocked tasks so that it\n      // is notified when the route tree is ready.\n      const blockedTasks = route.blockedTasks\n      if (blockedTasks === null) {\n        route.blockedTasks = new Set([task])\n      } else {\n        blockedTasks.add(task)\n      }\n      return PrefetchTaskExitStatus.Blocked\n    }\n    case EntryStatus.Rejected: {\n      // Route tree failed to load. Treat as a 404.\n      return PrefetchTaskExitStatus.Done\n    }\n    case EntryStatus.Fulfilled: {\n      if (task.phase !== PrefetchPhase.Segments) {\n        // Do not prefetch segment data until we've entered the segment phase.\n        return PrefetchTaskExitStatus.Done\n      }\n      // Recursively fill in the segment tree.\n      if (!hasNetworkBandwidth(task)) {\n        // Stop prefetching segments until there's more bandwidth.\n        return PrefetchTaskExitStatus.InProgress\n      }\n      const tree = route.tree\n\n      // A task's fetch strategy gets set to `PPR` for any \"auto\" prefetch.\n      // If it turned out that the route isn't PPR-enabled, we need to use `LoadingBoundary` instead.\n      // We don't need to do this for runtime prefetches, because those are only available in\n      // `cacheComponents`, where every route is PPR.\n      const fetchStrategy =\n        task.fetchStrategy === FetchStrategy.PPR\n          ? route.isPPREnabled\n            ? FetchStrategy.PPR\n            : FetchStrategy.LoadingBoundary\n          : task.fetchStrategy\n\n      switch (fetchStrategy) {\n        case FetchStrategy.PPR: {\n          // For Cache Components pages, each segment may be prefetched\n          // statically or using a runtime request, based on various\n          // configurations and heuristics. We'll do this in two passes: first\n          // traverse the tree and perform all the static prefetches.\n          //\n          // Then, if there are any segments that need a runtime request,\n          // do another pass to perform a runtime prefetch.\n          const exitStatus = pingSharedPartOfCacheComponentsTree(\n            now,\n            task,\n            route,\n            task.treeAtTimeOfPrefetch,\n            tree\n          )\n          if (exitStatus === PrefetchTaskExitStatus.InProgress) {\n            // Child yielded without finishing.\n            return PrefetchTaskExitStatus.InProgress\n          }\n          const spawnedRuntimePrefetches = task.spawnedRuntimePrefetches\n          if (spawnedRuntimePrefetches !== null) {\n            // During the first pass, we discovered segments that require a\n            // runtime prefetch. Do a second pass to construct a request tree.\n            const spawnedEntries = new Map<\n              SegmentCacheKey,\n              PendingSegmentCacheEntry\n            >()\n            const requestTree = pingRuntimePrefetches(\n              now,\n              task,\n              route,\n              tree,\n              spawnedRuntimePrefetches,\n              spawnedEntries\n            )\n            let needsDynamicRequest = spawnedEntries.size > 0\n            if (needsDynamicRequest) {\n              // Perform a dynamic prefetch request and populate the cache with\n              // the result.\n              spawnPrefetchSubtask(\n                fetchSegmentPrefetchesUsingDynamicRequest(\n                  task,\n                  route,\n                  FetchStrategy.PPRRuntime,\n                  requestTree,\n                  spawnedEntries\n                )\n              )\n            }\n          }\n          return PrefetchTaskExitStatus.Done\n        }\n        case FetchStrategy.Full:\n        case FetchStrategy.PPRRuntime:\n        case FetchStrategy.LoadingBoundary: {\n          // Prefetch multiple segments using a single dynamic request.\n          // TODO: We can consolidate this branch with previous one by modeling\n          // it as if the first segment in the new tree has runtime prefetching\n          // enabled. Will do this as a follow-up refactor. Might want to remove\n          // the special metatdata case below first. In the meantime, it's not\n          // really that much duplication, just would be nice to remove one of\n          // these codepaths.\n          const spawnedEntries = new Map<\n            SegmentCacheKey,\n            PendingSegmentCacheEntry\n          >()\n          const dynamicRequestTree = diffRouteTreeAgainstCurrent(\n            now,\n            task,\n            route,\n            task.treeAtTimeOfPrefetch,\n            tree,\n            spawnedEntries,\n            fetchStrategy\n          )\n\n          let needsDynamicRequest = spawnedEntries.size > 0\n\n          if (\n            !needsDynamicRequest &&\n            route.isHeadPartial &&\n            route.TODO_metadataStatus === EntryStatus.Empty\n          ) {\n            // All the segment data is already cached, however, we need to issue\n            // a request anyway so we can prefetch the head. Update the status\n            // field to prevent additional requests from being spawned while\n            // this one is in progress.\n            // TODO: This is a temporary, targeted solution to fix a regression\n            // we found. It exists to prevent the scheduler from sending a\n            // redundant request if there's already one in progress.\n            // Essentially, it will attempt once at most, then give up until the\n            // route entry expires or is evicted by other means. But because\n            // this doesn't have its own stale time separate from the route\n            // itself, there will be edge cases where the metadata fails to be\n            // fully prefetched. Consider caching metadata using a separate\n            // entry type so we can model this more cleanly. The circumstances\n            // that lead to this branch running in the first place are\n            // relatively rare, so it's not critical.\n            route.TODO_metadataStatus = EntryStatus.Fulfilled\n            needsDynamicRequest = true\n            // This instructs the server to only send the metadata.\n            dynamicRequestTree[3] = 'metadata-only'\n            // We can null out the children to reduce the request size, since\n            // they won't be needed.\n            dynamicRequestTree[1] = {}\n          }\n\n          if (needsDynamicRequest) {\n            // Perform a dynamic prefetch request and populate the cache with\n            // the result\n            spawnPrefetchSubtask(\n              fetchSegmentPrefetchesUsingDynamicRequest(\n                task,\n                route,\n                fetchStrategy,\n                dynamicRequestTree,\n                spawnedEntries\n              )\n            )\n          }\n          return PrefetchTaskExitStatus.Done\n        }\n        default:\n          fetchStrategy satisfies never\n      }\n      break\n    }\n    default: {\n      route satisfies never\n    }\n  }\n  return PrefetchTaskExitStatus.Done\n}\n\nfunction pingSharedPartOfCacheComponentsTree(\n  now: number,\n  task: PrefetchTask,\n  route: FulfilledRouteCacheEntry,\n  oldTree: FlightRouterState,\n  newTree: RouteTree\n): PrefetchTaskExitStatus {\n  // When Cache Components is enabled (or PPR, or a fully static route when PPR\n  // is disabled; those cases are treated equivalently to Cache Components), we\n  // start by prefetching each segment individually. Once we reach the \"new\"\n  // part of the tree — the part that doesn't exist on the current page — we\n  // may choose to switch to a runtime prefetch instead, based on the\n  // information sent by the server in the route tree.\n  //\n  // The traversal starts in the \"shared\" part of the tree. Once we reach the\n  // \"new\" part of the tree, we switch to a different traversal,\n  // pingNewPartOfCacheComponentsTree.\n\n  // Prefetch this segment's static data.\n  const segment = readOrCreateSegmentCacheEntry(\n    now,\n    task.fetchStrategy,\n    route,\n    newTree.cacheKey\n  )\n  pingStaticSegmentData(now, task, route, segment, task.key, newTree)\n\n  // Recursively ping the children.\n  const oldTreeChildren = oldTree[1]\n  const newTreeChildren = newTree.slots\n  if (newTreeChildren !== null) {\n    for (const parallelRouteKey in newTreeChildren) {\n      if (!hasNetworkBandwidth(task)) {\n        // Stop prefetching segments until there's more bandwidth.\n        return PrefetchTaskExitStatus.InProgress\n      }\n      const newTreeChild = newTreeChildren[parallelRouteKey]\n      const newTreeChildSegment = newTreeChild.segment\n      const oldTreeChild: FlightRouterState | void =\n        oldTreeChildren[parallelRouteKey]\n      const oldTreeChildSegment: FlightRouterStateSegment | void =\n        oldTreeChild?.[0]\n      let childExitStatus\n      if (\n        oldTreeChildSegment !== undefined &&\n        doesCurrentSegmentMatchCachedSegment(\n          route,\n          newTreeChildSegment,\n          oldTreeChildSegment\n        )\n      ) {\n        // We're still in the \"shared\" part of the tree.\n        childExitStatus = pingSharedPartOfCacheComponentsTree(\n          now,\n          task,\n          route,\n          oldTreeChild,\n          newTreeChild\n        )\n      } else {\n        // We've entered the \"new\" part of the tree. Switch\n        // traversal functions.\n        childExitStatus = pingNewPartOfCacheComponentsTree(\n          now,\n          task,\n          route,\n          newTreeChild\n        )\n      }\n      if (childExitStatus === PrefetchTaskExitStatus.InProgress) {\n        // Child yielded without finishing.\n        return PrefetchTaskExitStatus.InProgress\n      }\n    }\n  }\n\n  return PrefetchTaskExitStatus.Done\n}\n\nfunction pingNewPartOfCacheComponentsTree(\n  now: number,\n  task: PrefetchTask,\n  route: FulfilledRouteCacheEntry,\n  tree: RouteTree\n): PrefetchTaskExitStatus.InProgress | PrefetchTaskExitStatus.Done {\n  // We're now prefetching in the \"new\" part of the tree, the part that doesn't\n  // exist on the current page. (In other words, we're deeper than the\n  // shared layouts.) Segments in here default to being prefetched statically.\n  // However, if the server instructs us to, we may switch to a runtime\n  // prefetch instead. Traverse the tree and check at each segment.\n  if (tree.hasRuntimePrefetch) {\n    // This route has a runtime prefetch response. Since we're below the shared\n    // layout, everything from this point should be prefetched using a single,\n    // combined runtime request, rather than using per-segment static requests.\n    // This is true even if some of the child segments are known to be fully\n    // static — once we've decided to perform a runtime prefetch, we might as\n    // well respond with the static segments in the same roundtrip. (That's how\n    // regular navigations work, too.) We'll still skip over segments that are\n    // already cached, though.\n    //\n    // It's the server's responsibility to set a reasonable value of\n    // `hasRuntimePrefetch`. Currently it's user-defined, but eventually, the\n    // server may send a value of `false` even if the user opts in, if it\n    // determines during build that the route is always fully static. There are\n    // more optimizations we can do once we implement fallback param\n    // tracking, too.\n    //\n    // Use the task object to collect the segments that need a runtime prefetch.\n    // This will signal to the outer task queue that a second traversal is\n    // required to construct a request tree.\n    if (task.spawnedRuntimePrefetches === null) {\n      task.spawnedRuntimePrefetches = new Set([tree.cacheKey])\n    } else {\n      task.spawnedRuntimePrefetches.add(tree.cacheKey)\n    }\n    // Then exit the traversal without prefetching anything further.\n    return PrefetchTaskExitStatus.Done\n  }\n\n  // This segment should not be runtime prefetched. Prefetch its static data.\n  const segment = readOrCreateSegmentCacheEntry(\n    now,\n    task.fetchStrategy,\n    route,\n    tree.cacheKey\n  )\n  pingStaticSegmentData(now, task, route, segment, task.key, tree)\n  if (tree.slots !== null) {\n    if (!hasNetworkBandwidth(task)) {\n      // Stop prefetching segments until there's more bandwidth.\n      return PrefetchTaskExitStatus.InProgress\n    }\n    // Recursively ping the children.\n    for (const parallelRouteKey in tree.slots) {\n      const childTree = tree.slots[parallelRouteKey]\n      const childExitStatus = pingNewPartOfCacheComponentsTree(\n        now,\n        task,\n        route,\n        childTree\n      )\n      if (childExitStatus === PrefetchTaskExitStatus.InProgress) {\n        // Child yielded without finishing.\n        return PrefetchTaskExitStatus.InProgress\n      }\n    }\n  }\n  // This segment and all its children have finished prefetching.\n  return PrefetchTaskExitStatus.Done\n}\n\nfunction diffRouteTreeAgainstCurrent(\n  now: number,\n  task: PrefetchTask,\n  route: FulfilledRouteCacheEntry,\n  oldTree: FlightRouterState,\n  newTree: RouteTree,\n  spawnedEntries: Map<string, PendingSegmentCacheEntry>,\n  fetchStrategy:\n    | FetchStrategy.Full\n    | FetchStrategy.PPRRuntime\n    | FetchStrategy.LoadingBoundary\n): FlightRouterState {\n  // This is a single recursive traversal that does multiple things:\n  // - Finds the parts of the target route (newTree) that are not part of\n  //   of the current page (oldTree) by diffing them, using the same algorithm\n  //   as a real navigation.\n  // - Constructs a request tree (FlightRouterState) that describes which\n  //   segments need to be prefetched and which ones are already cached.\n  // - Creates a set of pending cache entries for the segments that need to\n  //   be prefetched, so that a subsequent prefetch task does not request the\n  //   same segments again.\n  const oldTreeChildren = oldTree[1]\n  const newTreeChildren = newTree.slots\n  let requestTreeChildren: Record<string, FlightRouterState> = {}\n  if (newTreeChildren !== null) {\n    for (const parallelRouteKey in newTreeChildren) {\n      const newTreeChild = newTreeChildren[parallelRouteKey]\n      const newTreeChildSegment = newTreeChild.segment\n      const oldTreeChild: FlightRouterState | void =\n        oldTreeChildren[parallelRouteKey]\n      const oldTreeChildSegment: FlightRouterStateSegment | void =\n        oldTreeChild?.[0]\n      if (\n        oldTreeChildSegment !== undefined &&\n        doesCurrentSegmentMatchCachedSegment(\n          route,\n          newTreeChildSegment,\n          oldTreeChildSegment\n        )\n      ) {\n        // This segment is already part of the current route. Keep traversing.\n        const requestTreeChild = diffRouteTreeAgainstCurrent(\n          now,\n          task,\n          route,\n          oldTreeChild,\n          newTreeChild,\n          spawnedEntries,\n          fetchStrategy\n        )\n        requestTreeChildren[parallelRouteKey] = requestTreeChild\n      } else {\n        // This segment is not part of the current route. We're entering a\n        // part of the tree that we need to prefetch (unless everything is\n        // already cached).\n        switch (fetchStrategy) {\n          case FetchStrategy.LoadingBoundary: {\n            // When PPR is disabled, we can't prefetch per segment. We must\n            // fallback to the old prefetch behavior and send a dynamic request.\n            // Only routes that include a loading boundary can be prefetched in\n            // this way.\n            //\n            // This is simlar to a \"full\" prefetch, but we're much more\n            // conservative about which segments to include in the request.\n            //\n            // The server will only render up to the first loading boundary\n            // inside new part of the tree. If there's no loading boundary\n            // anywhere in the tree, the server will never return any data, so\n            // we can skip the request.\n            const subtreeHasLoadingBoundary =\n              newTreeChild.hasLoadingBoundary !==\n              HasLoadingBoundary.SubtreeHasNoLoadingBoundary\n            const requestTreeChild = subtreeHasLoadingBoundary\n              ? pingPPRDisabledRouteTreeUpToLoadingBoundary(\n                  now,\n                  task,\n                  route,\n                  newTreeChild,\n                  null,\n                  spawnedEntries\n                )\n              : // There's no loading boundary within this tree. Bail out.\n                convertRouteTreeToFlightRouterState(newTreeChild)\n            requestTreeChildren[parallelRouteKey] = requestTreeChild\n            break\n          }\n          case FetchStrategy.PPRRuntime: {\n            // This is a runtime prefetch. Fetch all cacheable data in the tree,\n            // not just the static PPR shell.\n            const requestTreeChild = pingRouteTreeAndIncludeDynamicData(\n              now,\n              task,\n              route,\n              newTreeChild,\n              false,\n              spawnedEntries,\n              fetchStrategy\n            )\n            requestTreeChildren[parallelRouteKey] = requestTreeChild\n            break\n          }\n          case FetchStrategy.Full: {\n            // This is a \"full\" prefetch. Fetch all the data in the tree, both\n            // static and dynamic. We issue roughly the same request that we\n            // would during a real navigation. The goal is that once the\n            // navigation occurs, the router should not have to fetch any\n            // additional data.\n            //\n            // Although the response will include dynamic data, opting into a\n            // Full prefetch — via <Link prefetch={true}> — implicitly\n            // instructs the cache to treat the response as \"static\", or non-\n            // dynamic, since the whole point is to cache it for\n            // future navigations.\n            //\n            // Construct a tree (currently a FlightRouterState) that represents\n            // which segments need to be prefetched and which ones are already\n            // cached. If the tree is empty, then we can exit. Otherwise, we'll\n            // send the request tree to the server and use the response to\n            // populate the segment cache.\n            const requestTreeChild = pingRouteTreeAndIncludeDynamicData(\n              now,\n              task,\n              route,\n              newTreeChild,\n              false,\n              spawnedEntries,\n              fetchStrategy\n            )\n            requestTreeChildren[parallelRouteKey] = requestTreeChild\n            break\n          }\n          default:\n            fetchStrategy satisfies never\n        }\n      }\n    }\n  }\n  const requestTree: FlightRouterState = [\n    newTree.segment,\n    requestTreeChildren,\n    null,\n    null,\n    newTree.isRootLayout,\n  ]\n  return requestTree\n}\n\nfunction pingPPRDisabledRouteTreeUpToLoadingBoundary(\n  now: number,\n  task: PrefetchTask,\n  route: FulfilledRouteCacheEntry,\n  tree: RouteTree,\n  refetchMarkerContext: 'refetch' | 'inside-shared-layout' | null,\n  spawnedEntries: Map<string, PendingSegmentCacheEntry>\n): FlightRouterState {\n  // This function is similar to pingRouteTreeAndIncludeDynamicData, except the\n  // server is only going to return a minimal loading state — it will stop\n  // rendering at the first loading boundary. Whereas a Full prefetch is\n  // intentionally aggressive and tries to pretfetch all the data that will be\n  // needed for a navigation, a LoadingBoundary prefetch is much more\n  // conservative. For example, it will omit from the request tree any segment\n  // that is already cached, regardles of whether it's partial or full. By\n  // contrast, a Full prefetch will refetch partial segments.\n\n  // \"inside-shared-layout\" tells the server where to start looking for a\n  // loading boundary.\n  let refetchMarker: 'refetch' | 'inside-shared-layout' | null =\n    refetchMarkerContext === null ? 'inside-shared-layout' : null\n\n  const segment = readOrCreateSegmentCacheEntry(\n    now,\n    task.fetchStrategy,\n    route,\n    tree.cacheKey\n  )\n  switch (segment.status) {\n    case EntryStatus.Empty: {\n      // This segment is not cached. Add a refetch marker so the server knows\n      // to start rendering here.\n      // TODO: Instead of a \"refetch\" marker, we could just omit this subtree's\n      // FlightRouterState from the request tree. I think this would probably\n      // already work even without any updates to the server. For consistency,\n      // though, I'll send the full tree and we'll look into this later as part\n      // of a larger redesign of the request protocol.\n\n      // Add the pending cache entry to the result map.\n      spawnedEntries.set(\n        tree.cacheKey,\n        upgradeToPendingSegment(\n          segment,\n          // Set the fetch strategy to LoadingBoundary to indicate that the server\n          // might not include it in the pending response. If another route is able\n          // to issue a per-segment request, we'll do that in the background.\n          FetchStrategy.LoadingBoundary\n        )\n      )\n      if (refetchMarkerContext !== 'refetch') {\n        refetchMarker = refetchMarkerContext = 'refetch'\n      } else {\n        // There's already a parent with a refetch marker, so we don't need\n        // to add another one.\n      }\n      break\n    }\n    case EntryStatus.Fulfilled: {\n      // The segment is already cached.\n      const segmentHasLoadingBoundary =\n        tree.hasLoadingBoundary === HasLoadingBoundary.SegmentHasLoadingBoundary\n      if (segmentHasLoadingBoundary) {\n        // This segment has a loading boundary, which means the server won't\n        // render its children. So there's nothing left to prefetch along this\n        // path. We can bail out.\n        return convertRouteTreeToFlightRouterState(tree)\n      }\n      // NOTE: If the cached segment were fetched using PPR, then it might be\n      // partial. We could get a more complete version of the segment by\n      // including it in this non-PPR request.\n      //\n      // We're intentionally choosing not to, though, because it's generally\n      // better to avoid doing a full prefetch whenever possible.\n      break\n    }\n    case EntryStatus.Pending: {\n      // There's another prefetch currently in progress. Don't add the refetch\n      // marker yet, so the server knows it can skip rendering this segment.\n      break\n    }\n    case EntryStatus.Rejected: {\n      // The segment failed to load. We shouldn't issue another request until\n      // the stale time has elapsed.\n      break\n    }\n    default:\n      segment satisfies never\n  }\n  const requestTreeChildren: Record<string, FlightRouterState> = {}\n  if (tree.slots !== null) {\n    for (const parallelRouteKey in tree.slots) {\n      const childTree = tree.slots[parallelRouteKey]\n      requestTreeChildren[parallelRouteKey] =\n        pingPPRDisabledRouteTreeUpToLoadingBoundary(\n          now,\n          task,\n          route,\n          childTree,\n          refetchMarkerContext,\n          spawnedEntries\n        )\n    }\n  }\n  const requestTree: FlightRouterState = [\n    tree.segment,\n    requestTreeChildren,\n    null,\n    refetchMarker,\n    tree.isRootLayout,\n  ]\n  return requestTree\n}\n\nfunction pingRouteTreeAndIncludeDynamicData(\n  now: number,\n  task: PrefetchTask,\n  route: FulfilledRouteCacheEntry,\n  tree: RouteTree,\n  isInsideRefetchingParent: boolean,\n  spawnedEntries: Map<string, PendingSegmentCacheEntry>,\n  fetchStrategy: FetchStrategy.Full | FetchStrategy.PPRRuntime\n): FlightRouterState {\n  // The tree we're constructing is the same shape as the tree we're navigating\n  // to. But even though this is a \"new\" tree, some of the individual segments\n  // may be cached as a result of other route prefetches.\n  //\n  // So we need to find the first uncached segment along each path add an\n  // explicit \"refetch\" marker so the server knows where to start rendering.\n  // Once the server starts rendering along a path, it keeps rendering the\n  // entire subtree.\n  const segment = readOrCreateSegmentCacheEntry(\n    now,\n    // Note that `fetchStrategy` might be different from `task.fetchStrategy`,\n    // and we have to use the former here.\n    // We can have a task with `FetchStrategy.PPR` where some of its segments are configured to\n    // always use runtime prefetching (via `export const prefetch`), and those should check for\n    // entries that include search params.\n    fetchStrategy,\n    route,\n    tree.cacheKey\n  )\n\n  let spawnedSegment: PendingSegmentCacheEntry | null = null\n\n  switch (segment.status) {\n    case EntryStatus.Empty: {\n      // This segment is not cached. Include it in the request.\n      spawnedSegment = upgradeToPendingSegment(segment, fetchStrategy)\n      break\n    }\n    case EntryStatus.Fulfilled: {\n      // The segment is already cached.\n      if (\n        segment.isPartial &&\n        canNewFetchStrategyProvideMoreContent(\n          segment.fetchStrategy,\n          fetchStrategy\n        )\n      ) {\n        // The cached segment contains dynamic holes, and was prefetched using a less specific strategy than the current one.\n        // This means we're in one of these cases:\n        //   - we have a static prefetch, and we're doing a runtime prefetch\n        //   - we have a static or runtime prefetch, and we're doing a Full prefetch (or a navigation).\n        // In either case, we need to include it in the request to get a more specific (or full) version.\n        spawnedSegment = pingFullSegmentRevalidation(\n          now,\n          route,\n          segment,\n          tree,\n          fetchStrategy\n        )\n      }\n      break\n    }\n    case EntryStatus.Pending:\n    case EntryStatus.Rejected: {\n      // There's either another prefetch currently in progress, or the previous\n      // attempt failed. If the new strategy can provide more content, fetch it again.\n      if (\n        canNewFetchStrategyProvideMoreContent(\n          segment.fetchStrategy,\n          fetchStrategy\n        )\n      ) {\n        spawnedSegment = pingFullSegmentRevalidation(\n          now,\n          route,\n          segment,\n          tree,\n          fetchStrategy\n        )\n      }\n      break\n    }\n    default:\n      segment satisfies never\n  }\n  const requestTreeChildren: Record<string, FlightRouterState> = {}\n  if (tree.slots !== null) {\n    for (const parallelRouteKey in tree.slots) {\n      const childTree = tree.slots[parallelRouteKey]\n      requestTreeChildren[parallelRouteKey] =\n        pingRouteTreeAndIncludeDynamicData(\n          now,\n          task,\n          route,\n          childTree,\n          isInsideRefetchingParent || spawnedSegment !== null,\n          spawnedEntries,\n          fetchStrategy\n        )\n    }\n  }\n\n  if (spawnedSegment !== null) {\n    // Add the pending entry to the result map.\n    spawnedEntries.set(tree.cacheKey, spawnedSegment)\n  }\n\n  // Don't bother to add a refetch marker if one is already present in a parent.\n  const refetchMarker =\n    !isInsideRefetchingParent && spawnedSegment !== null ? 'refetch' : null\n\n  const requestTree: FlightRouterState = [\n    tree.segment,\n    requestTreeChildren,\n    null,\n    refetchMarker,\n    tree.isRootLayout,\n  ]\n  return requestTree\n}\n\nfunction pingRuntimePrefetches(\n  now: number,\n  task: PrefetchTask,\n  route: FulfilledRouteCacheEntry,\n  tree: RouteTree,\n  spawnedRuntimePrefetches: Set<SegmentCacheKey>,\n  spawnedEntries: Map<string, PendingSegmentCacheEntry>\n): FlightRouterState {\n  // Construct a request tree (FlightRouterState) for a runtime prefetch. If\n  // a segment is part of the runtime prefetch, the tree is constructed by\n  // diffing against what's already in the prefetch cache. Otherwise, we send\n  // a regular FlightRouterState with no special markers.\n  //\n  // See pingRouteTreeAndIncludeDynamicData for details.\n  if (spawnedRuntimePrefetches.has(tree.cacheKey)) {\n    // This segment needs a runtime prefetch.\n    return pingRouteTreeAndIncludeDynamicData(\n      now,\n      task,\n      route,\n      tree,\n      false,\n      spawnedEntries,\n      FetchStrategy.PPRRuntime\n    )\n  }\n  let requestTreeChildren: Record<string, FlightRouterState> = {}\n  const slots = tree.slots\n  if (slots !== null) {\n    for (const parallelRouteKey in slots) {\n      const childTree = slots[parallelRouteKey]\n      requestTreeChildren[parallelRouteKey] = pingRuntimePrefetches(\n        now,\n        task,\n        route,\n        childTree,\n        spawnedRuntimePrefetches,\n        spawnedEntries\n      )\n    }\n  }\n\n  // This segment is not part of the runtime prefetch. Clone the base tree.\n  const requestTree: FlightRouterState = [\n    tree.segment,\n    requestTreeChildren,\n    null,\n    null,\n  ]\n  return requestTree\n}\n\nfunction pingStaticSegmentData(\n  now: number,\n  task: PrefetchTask,\n  route: FulfilledRouteCacheEntry,\n  segment: SegmentCacheEntry,\n  routeKey: RouteCacheKey,\n  tree: RouteTree\n): void {\n  switch (segment.status) {\n    case EntryStatus.Empty:\n      // Upgrade to Pending so we know there's already a request in progress\n      spawnPrefetchSubtask(\n        fetchSegmentOnCacheMiss(\n          route,\n          upgradeToPendingSegment(segment, FetchStrategy.PPR),\n          routeKey,\n          tree\n        )\n      )\n      break\n    case EntryStatus.Pending: {\n      // There's already a request in progress. Depending on what kind of\n      // request it is, we may want to revalidate it.\n      switch (segment.fetchStrategy) {\n        case FetchStrategy.PPR:\n        case FetchStrategy.PPRRuntime:\n        case FetchStrategy.Full:\n          // There's already a request in progress. Don't do anything.\n          break\n        case FetchStrategy.LoadingBoundary:\n          // There's a pending request, but because it's using the old\n          // prefetching strategy, we can't be sure if it will be fulfilled by\n          // the response — it might be inside the loading boundary. Perform\n          // a revalidation, but because it's speculative, wait to do it at\n          // background priority.\n          if (background(task)) {\n            // TODO: Instead of speculatively revalidating, consider including\n            // `hasLoading` in the route tree prefetch response.\n            pingPPRSegmentRevalidation(\n              now,\n              task,\n              segment,\n              route,\n              routeKey,\n              tree\n            )\n          }\n          break\n        default:\n          segment.fetchStrategy satisfies never\n      }\n      break\n    }\n    case EntryStatus.Rejected: {\n      // The existing entry in the cache was rejected. Depending on how it\n      // was originally fetched, we may or may not want to revalidate it.\n      switch (segment.fetchStrategy) {\n        case FetchStrategy.PPR:\n        case FetchStrategy.PPRRuntime:\n        case FetchStrategy.Full:\n          // The previous attempt to fetch this entry failed. Don't attempt to\n          // fetch it again until the entry expires.\n          break\n        case FetchStrategy.LoadingBoundary:\n          // There's a rejected entry, but it was fetched using the loading\n          // boundary strategy. So the reason it wasn't returned by the server\n          // might just be because it was inside a loading boundary. Or because\n          // there was a dynamic rewrite. Revalidate it using the per-\n          // segment strategy.\n          //\n          // Because a rejected segment will definitely prevent the segment (and\n          // all of its children) from rendering, we perform this revalidation\n          // immediately instead of deferring it to a background task.\n          pingPPRSegmentRevalidation(now, task, segment, route, routeKey, tree)\n          break\n        default:\n          segment.fetchStrategy satisfies never\n      }\n      break\n    }\n    case EntryStatus.Fulfilled:\n      // Segment is already cached. There's nothing left to prefetch.\n      break\n    default:\n      segment satisfies never\n  }\n\n  // Segments do not have dependent tasks, so once the prefetch is initiated,\n  // there's nothing else for us to do (except write the server data into the\n  // entry, which is handled by `fetchSegmentOnCacheMiss`).\n}\n\nfunction pingPPRSegmentRevalidation(\n  now: number,\n  task: PrefetchTask,\n  currentSegment: SegmentCacheEntry,\n  route: FulfilledRouteCacheEntry,\n  routeKey: RouteCacheKey,\n  tree: RouteTree\n): void {\n  const revalidatingSegment = readOrCreateRevalidatingSegmentEntry(\n    now,\n    currentSegment\n  )\n  switch (revalidatingSegment.status) {\n    case EntryStatus.Empty:\n      // Spawn a prefetch request and upsert the segment into the cache\n      // upon completion.\n      upsertSegmentOnCompletion(\n        task.fetchStrategy,\n        route,\n        tree.cacheKey,\n        spawnPrefetchSubtask(\n          fetchSegmentOnCacheMiss(\n            route,\n            upgradeToPendingSegment(revalidatingSegment, FetchStrategy.PPR),\n            routeKey,\n            tree\n          )\n        )\n      )\n      break\n    case EntryStatus.Pending:\n      // There's already a revalidation in progress.\n      break\n    case EntryStatus.Fulfilled:\n    case EntryStatus.Rejected:\n      // A previous revalidation attempt finished, but we chose not to replace\n      // the existing entry in the cache. Don't try again until or unless the\n      // revalidation entry expires.\n      break\n    default:\n      revalidatingSegment satisfies never\n  }\n}\n\nfunction pingFullSegmentRevalidation(\n  now: number,\n  route: FulfilledRouteCacheEntry,\n  currentSegment: SegmentCacheEntry,\n  tree: RouteTree,\n  fetchStrategy: FetchStrategy.Full | FetchStrategy.PPRRuntime\n): PendingSegmentCacheEntry | null {\n  const revalidatingSegment = readOrCreateRevalidatingSegmentEntry(\n    now,\n    currentSegment\n  )\n  if (revalidatingSegment.status === EntryStatus.Empty) {\n    // During a Full/PPRRuntime prefetch, a single dynamic request is made for all the\n    // segments that we need. So we don't initiate a request here directly. By\n    // returning a pending entry from this function, it signals to the caller\n    // that this segment should be included in the request that's sent to\n    // the server.\n    const pendingSegment = upgradeToPendingSegment(\n      revalidatingSegment,\n      fetchStrategy\n    )\n    upsertSegmentOnCompletion(\n      fetchStrategy,\n      route,\n      tree.cacheKey,\n      waitForSegmentCacheEntry(pendingSegment)\n    )\n    return pendingSegment\n  } else {\n    // There's already a revalidation in progress.\n    const nonEmptyRevalidatingSegment = revalidatingSegment\n    if (\n      canNewFetchStrategyProvideMoreContent(\n        nonEmptyRevalidatingSegment.fetchStrategy,\n        fetchStrategy\n      )\n    ) {\n      // The existing revalidation was fetched using a less specific strategy.\n      // Reset it and start a new revalidation.\n      const emptySegment = resetRevalidatingSegmentEntry(\n        nonEmptyRevalidatingSegment\n      )\n      const pendingSegment = upgradeToPendingSegment(\n        emptySegment,\n        fetchStrategy\n      )\n      upsertSegmentOnCompletion(\n        fetchStrategy,\n        route,\n        tree.cacheKey,\n        waitForSegmentCacheEntry(pendingSegment)\n      )\n      return pendingSegment\n    }\n    switch (nonEmptyRevalidatingSegment.status) {\n      case EntryStatus.Pending:\n        // There's already an in-progress prefetch that includes this segment.\n        return null\n      case EntryStatus.Fulfilled:\n      case EntryStatus.Rejected:\n        // A previous revalidation attempt finished, but we chose not to replace\n        // the existing entry in the cache. Don't try again until or unless the\n        // revalidation entry expires.\n        return null\n      default:\n        nonEmptyRevalidatingSegment satisfies never\n        return null\n    }\n  }\n}\n\nconst noop = () => {}\n\nfunction upsertSegmentOnCompletion(\n  fetchStrategy: FetchStrategy,\n  route: FulfilledRouteCacheEntry,\n  cacheKey: SegmentCacheKey,\n  promise: Promise<FulfilledSegmentCacheEntry | null>\n) {\n  // Wait for a segment to finish loading, then upsert it into the cache\n  promise.then((fulfilled) => {\n    if (fulfilled !== null) {\n      // Received new data. Attempt to replace the existing entry in the cache.\n      const keypath = getSegmentKeypath(fetchStrategy, route, cacheKey)\n      upsertSegmentEntry(Date.now(), keypath, fulfilled)\n    }\n  }, noop)\n}\n\nfunction doesCurrentSegmentMatchCachedSegment(\n  route: FulfilledRouteCacheEntry,\n  currentSegment: Segment,\n  cachedSegment: Segment\n): boolean {\n  if (cachedSegment === PAGE_SEGMENT_KEY) {\n    // In the FlightRouterState stored by the router, the page segment has the\n    // rendered search params appended to the name of the segment. In the\n    // prefetch cache, however, this is stored separately. So, when comparing\n    // the router's current FlightRouterState to the cached FlightRouterState,\n    // we need to make sure we compare both parts of the segment.\n    // TODO: This is not modeled clearly. We use the same type,\n    // FlightRouterState, for both the CacheNode tree _and_ the prefetch cache\n    // _and_ the server response format, when conceptually those are three\n    // different things and treated in different ways. We should encode more of\n    // this information into the type design so mistakes are less likely.\n    return (\n      currentSegment ===\n      addSearchParamsIfPageSegment(\n        PAGE_SEGMENT_KEY,\n        Object.fromEntries(new URLSearchParams(route.renderedSearch))\n      )\n    )\n  }\n  // Non-page segments are compared using the same function as the server\n  return matchSegment(cachedSegment, currentSegment)\n}\n\n// -----------------------------------------------------------------------------\n// The remainder of the module is a MinHeap implementation. Try not to put any\n// logic below here unless it's related to the heap algorithm. We can extract\n// this to a separate module if/when we need multiple kinds of heaps.\n// -----------------------------------------------------------------------------\n\nfunction compareQueuePriority(a: PrefetchTask, b: PrefetchTask) {\n  // Since the queue is a MinHeap, this should return a positive number if b is\n  // higher priority than a, and a negative number if a is higher priority\n  // than b.\n\n  // `priority` is an integer, where higher numbers are higher priority.\n  const priorityDiff = b.priority - a.priority\n  if (priorityDiff !== 0) {\n    return priorityDiff\n  }\n\n  // If the priority is the same, check which phase the prefetch is in — is it\n  // prefetching the route tree, or the segments? Route trees are prioritized.\n  const phaseDiff = b.phase - a.phase\n  if (phaseDiff !== 0) {\n    return phaseDiff\n  }\n\n  // Finally, check the insertion order. `sortId` is an incrementing counter\n  // assigned to prefetches. We want to process the newest prefetches first.\n  return b.sortId - a.sortId\n}\n\nfunction heapPush(heap: Array<PrefetchTask>, node: PrefetchTask): void {\n  const index = heap.length\n  heap.push(node)\n  node._heapIndex = index\n  heapSiftUp(heap, node, index)\n}\n\nfunction heapPeek(heap: Array<PrefetchTask>): PrefetchTask | null {\n  return heap.length === 0 ? null : heap[0]\n}\n\nfunction heapPop(heap: Array<PrefetchTask>): PrefetchTask | null {\n  if (heap.length === 0) {\n    return null\n  }\n  const first = heap[0]\n  first._heapIndex = -1\n  const last = heap.pop() as PrefetchTask\n  if (last !== first) {\n    heap[0] = last\n    last._heapIndex = 0\n    heapSiftDown(heap, last, 0)\n  }\n  return first\n}\n\nfunction heapDelete(heap: Array<PrefetchTask>, node: PrefetchTask): void {\n  const index = node._heapIndex\n  if (index !== -1) {\n    node._heapIndex = -1\n    if (heap.length !== 0) {\n      const last = heap.pop() as PrefetchTask\n      if (last !== node) {\n        heap[index] = last\n        last._heapIndex = index\n        heapSiftDown(heap, last, index)\n      }\n    }\n  }\n}\n\nfunction heapResift(heap: Array<PrefetchTask>, node: PrefetchTask): void {\n  const index = node._heapIndex\n  if (index !== -1) {\n    if (index === 0) {\n      heapSiftDown(heap, node, 0)\n    } else {\n      const parentIndex = (index - 1) >>> 1\n      const parent = heap[parentIndex]\n      if (compareQueuePriority(parent, node) > 0) {\n        // The parent is larger. Sift up.\n        heapSiftUp(heap, node, index)\n      } else {\n        // The parent is smaller (or equal). Sift down.\n        heapSiftDown(heap, node, index)\n      }\n    }\n  }\n}\n\nfunction heapSiftUp(\n  heap: Array<PrefetchTask>,\n  node: PrefetchTask,\n  i: number\n): void {\n  let index = i\n  while (index > 0) {\n    const parentIndex = (index - 1) >>> 1\n    const parent = heap[parentIndex]\n    if (compareQueuePriority(parent, node) > 0) {\n      // The parent is larger. Swap positions.\n      heap[parentIndex] = node\n      node._heapIndex = parentIndex\n      heap[index] = parent\n      parent._heapIndex = index\n\n      index = parentIndex\n    } else {\n      // The parent is smaller. Exit.\n      return\n    }\n  }\n}\n\nfunction heapSiftDown(\n  heap: Array<PrefetchTask>,\n  node: PrefetchTask,\n  i: number\n): void {\n  let index = i\n  const length = heap.length\n  const halfLength = length >>> 1\n  while (index < halfLength) {\n    const leftIndex = (index + 1) * 2 - 1\n    const left = heap[leftIndex]\n    const rightIndex = leftIndex + 1\n    const right = heap[rightIndex]\n\n    // If the left or right node is smaller, swap with the smaller of those.\n    if (compareQueuePriority(left, node) < 0) {\n      if (rightIndex < length && compareQueuePriority(right, left) < 0) {\n        heap[index] = right\n        right._heapIndex = index\n        heap[rightIndex] = node\n        node._heapIndex = rightIndex\n\n        index = rightIndex\n      } else {\n        heap[index] = left\n        left._heapIndex = index\n        heap[leftIndex] = node\n        node._heapIndex = leftIndex\n\n        index = leftIndex\n      }\n    } else if (rightIndex < length && compareQueuePriority(right, node) < 0) {\n      heap[index] = right\n      right._heapIndex = index\n      heap[rightIndex] = node\n      node._heapIndex = rightIndex\n\n      index = rightIndex\n    } else {\n      // Neither child is smaller. Exit.\n      return\n    }\n  }\n}\n"],"names":["cancelPrefetchTask","isPrefetchTaskDirty","pingPrefetchTask","reschedulePrefetchTask","schedulePrefetchTask","startRevalidationCooldown","scheduleMicrotask","queueMicrotask","fn","Promise","resolve","then","catch","error","setTimeout","taskHeap","inProgressRequests","sortIdCounter","didScheduleMicrotask","mostRecentlyHoveredLink","REVALIDATION_COOLDOWN_MS","revalidationCooldownTimeoutHandle","clearTimeout","ensureWorkIsScheduled","key","treeAtTimeOfPrefetch","fetchStrategy","priority","onInvalidate","task","cacheVersion","getCurrentCacheVersion","phase","hasBackgroundWork","spawnedRuntimePrefetches","sortId","isCanceled","_heapIndex","trackMostRecentlyHoveredLink","heapPush","heapDelete","PrefetchPriority","Intent","heapResift","nextUrl","tree","currentCacheVersion","Background","Default","processQueueInMicrotask","hasNetworkBandwidth","spawnPrefetchSubtask","prefetchSubtask","result","onPrefetchConnectionClosed","closed","value","now","Date","heapPeek","exitStatus","pingRoute","heapPop","background","route","readOrCreateRouteCacheEntry","pingRootRouteTree","search","url","URL","href","keyWithoutSearch","createCacheKey","routeWithoutSearch","status","EntryStatus","Empty","Pending","fetchRouteOnCacheMiss","Fulfilled","Rejected","staleAt","blockedTasks","Set","add","FetchStrategy","PPR","isPPREnabled","LoadingBoundary","pingSharedPartOfCacheComponentsTree","spawnedEntries","Map","requestTree","pingRuntimePrefetches","needsDynamicRequest","size","fetchSegmentPrefetchesUsingDynamicRequest","PPRRuntime","Full","dynamicRequestTree","diffRouteTreeAgainstCurrent","isHeadPartial","TODO_metadataStatus","oldTree","newTree","segment","readOrCreateSegmentCacheEntry","cacheKey","pingStaticSegmentData","oldTreeChildren","newTreeChildren","slots","parallelRouteKey","newTreeChild","newTreeChildSegment","oldTreeChild","oldTreeChildSegment","childExitStatus","undefined","doesCurrentSegmentMatchCachedSegment","pingNewPartOfCacheComponentsTree","hasRuntimePrefetch","childTree","requestTreeChildren","requestTreeChild","subtreeHasLoadingBoundary","hasLoadingBoundary","HasLoadingBoundary","SubtreeHasNoLoadingBoundary","pingPPRDisabledRouteTreeUpToLoadingBoundary","convertRouteTreeToFlightRouterState","pingRouteTreeAndIncludeDynamicData","isRootLayout","refetchMarkerContext","refetchMarker","set","upgradeToPendingSegment","segmentHasLoadingBoundary","SegmentHasLoadingBoundary","isInsideRefetchingParent","spawnedSegment","isPartial","canNewFetchStrategyProvideMoreContent","pingFullSegmentRevalidation","has","routeKey","fetchSegmentOnCacheMiss","pingPPRSegmentRevalidation","currentSegment","revalidatingSegment","readOrCreateRevalidatingSegmentEntry","upsertSegmentOnCompletion","pendingSegment","waitForSegmentCacheEntry","nonEmptyRevalidatingSegment","emptySegment","resetRevalidatingSegmentEntry","noop","promise","fulfilled","keypath","getSegmentKeypath","upsertSegmentEntry","cachedSegment","PAGE_SEGMENT_KEY","addSearchParamsIfPageSegment","Object","fromEntries","URLSearchParams","renderedSearch","matchSegment","compareQueuePriority","a","b","priorityDiff","phaseDiff","heap","node","index","length","push","heapSiftUp","first","last","pop","heapSiftDown","parentIndex","parent","i","halfLength","leftIndex","left","rightIndex","right"],"mappings":";;;;;;;;;;;;;;;;;;;IAsRgBA,kBAAkB;eAAlBA;;IAiDAC,mBAAmB;eAAnBA;;IA6HAC,gBAAgB;eAAhBA;;IApKAC,sBAAsB;eAAtBA;;IAjDAC,oBAAoB;eAApBA;;IA7BAC,yBAAyB;eAAzBA;;;gCA7MmB;+BACN;uBAsBtB;0BAEwB;8BAMxB;yBAIA;AAGP,MAAMC,oBACJ,OAAOC,mBAAmB,aACtBA,iBACA,CAACC,KACCC,QAAQC,OAAO,GACZC,IAAI,CAACH,IACLI,KAAK,CAAC,CAACC,QACNC,WAAW;YACT,MAAMD;QACR;AAsIZ,MAAME,WAAgC,EAAE;AAExC,IAAIC,qBAAqB;AAEzB,IAAIC,gBAAgB;AACpB,IAAIC,uBAAuB;AAE3B,8EAA8E;AAC9E,0EAA0E;AAC1E,+EAA+E;AAC/E,IAAIC,0BAA+C;AAEnD,mEAAmE;AACnE,MAAMC,2BAA2B;AAEjC,wEAAwE;AACxE,uDAAuD;AACvD,IAAIC,oCACF;AAMK,SAAShB;IACd,mEAAmE;IACnE,uBAAuB;IACvB,IAAIgB,sCAAsC,MAAM;QAC9CC,aAAaD;IACf;IAEA,mDAAmD;IACnDA,oCAAoCP,WAAW;QAC7CO,oCAAoC;QACpC,8DAA8D;QAC9DE;IACF,GAAGH;AACL;AAgBO,SAAShB,qBACdoB,GAAkB,EAClBC,oBAAuC,EACvCC,aAAwC,EACxCC,QAA0B,EAC1BC,YAAiC;IAEjC,4BAA4B;IAC5B,MAAMC,OAAqB;QACzBL;QACAC;QACAK,cAAcC,IAAAA,oCAAsB;QACpCJ;QACAK,KAAK;QACLC,mBAAmB;QACnBC,0BAA0B;QAC1BR;QACAS,QAAQlB;QACRmB,YAAY;QACZR;QACAS,YAAY,CAAC;IACf;IAEAC,6BAA6BT;IAE7BU,SAASxB,UAAUc;IAEnB,+CAA+C;IAC/C,EAAE;IACF,yEAAyE;IACzE,yEAAyE;IACzE,2EAA2E;IAC3E,2EAA2E;IAC3E,qBAAqB;IACrBN;IAEA,OAAOM;AACT;AAEO,SAAS7B,mBAAmB6B,IAAkB;IACnD,0EAA0E;IAC1E,wBAAwB;IACxB,EAAE;IACF,2EAA2E;IAC3E,wEAAwE;IACxEA,KAAKO,UAAU,GAAG;IAClBI,WAAWzB,UAAUc;AACvB;AAEO,SAAS1B,uBACd0B,IAAkB,EAClBJ,oBAAuC,EACvCC,aAAwC,EACxCC,QAA0B;IAE1B,wEAAwE;IACxE,0EAA0E;IAC1E,mDAAmD;IACnD,EAAE;IACF,sEAAsE;IACtE,qBAAqB;IAErB,0DAA0D;IAC1DE,KAAKO,UAAU,GAAG;IAClBP,KAAKG,KAAK;IAEV,uEAAuE;IACvE,yDAAyD;IACzDH,KAAKM,MAAM,GAAGlB;IACdY,KAAKF,QAAQ,GACX,+DAA+D;IAC/D,8DAA8D;IAC9DE,SAASV,0BAA0BsB,8BAAgB,CAACC,MAAM,GAAGf;IAE/DE,KAAKJ,oBAAoB,GAAGA;IAC5BI,KAAKH,aAAa,GAAGA;IAErBY,6BAA6BT;IAE7B,IAAIA,KAAKQ,UAAU,KAAK,CAAC,GAAG;QAC1B,oCAAoC;QACpCM,WAAW5B,UAAUc;IACvB,OAAO;QACLU,SAASxB,UAAUc;IACrB;IACAN;AACF;AAEO,SAAStB,oBACd4B,IAAkB,EAClBe,OAAsB,EACtBC,IAAuB;IAEvB,uEAAuE;IACvE,uEAAuE;IACvE,2EAA2E;IAC3E,uEAAuE;IACvE,2BAA2B;IAC3B,MAAMC,sBAAsBf,IAAAA,oCAAsB;IAClD,OACEF,KAAKC,YAAY,KAAKgB,uBACtBjB,KAAKJ,oBAAoB,KAAKoB,QAC9BhB,KAAKL,GAAG,CAACoB,OAAO,KAAKA;AAEzB;AAEA,SAASN,6BAA6BT,IAAkB;IACtD,2EAA2E;IAC3E,uEAAuE;IACvE,IACEA,KAAKF,QAAQ,KAAKc,8BAAgB,CAACC,MAAM,IACzCb,SAASV,yBACT;QACA,IAAIA,4BAA4B,MAAM;YACpC,+DAA+D;YAC/D,IAAIA,wBAAwBQ,QAAQ,KAAKc,8BAAgB,CAACM,UAAU,EAAE;gBACpE5B,wBAAwBQ,QAAQ,GAAGc,8BAAgB,CAACO,OAAO;gBAC3DL,WAAW5B,UAAUI;YACvB;QACF;QACAA,0BAA0BU;IAC5B;AACF;AAEA,SAASN;IACP,IAAIL,sBAAsB;QACxB,gDAAgD;QAChD;IACF;IACAA,uBAAuB;IACvBZ,kBAAkB2C;AACpB;AAEA;;;;;;;;CAQC,GACD,SAASC,oBAAoBrB,IAAkB;IAC7C,yDAAyD;IACzD,IAAIR,sCAAsC,MAAM;QAC9C,yEAAyE;QACzE,2EAA2E;QAC3E,sBAAsB;QACtB,OAAO;IACT;IAEA,yEAAyE;IACzE,wEAAwE;IACxE,2EAA2E;IAC3E,sBAAsB;IAEtB,2EAA2E;IAE3E,IAAIQ,KAAKF,QAAQ,KAAKc,8BAAgB,CAACC,MAAM,EAAE;QAC7C,yEAAyE;QACzE,EAAE;QACF,sEAAsE;QACtE,qCAAqC;QACrC,EAAE;QACF,4EAA4E;QAC5E,0EAA0E;QAC1E,iEAAiE;QACjE,OAAO1B,qBAAqB;IAC9B;IAEA,gEAAgE;IAChE,OAAOA,qBAAqB;AAC9B;AAEA,SAASmC,qBACPC,eAAyD;IAEzD,sEAAsE;IACtE,0EAA0E;IAC1E,mCAAmC;IACnC,EAAE;IACF,wEAAwE;IACxE,2EAA2E;IAC3E,yEAAyE;IACzE,2EAA2E;IAC3E,kDAAkD;IAClDpC;IACA,OAAOoC,gBAAgBzC,IAAI,CAAC,CAAC0C;QAC3B,IAAIA,WAAW,MAAM;YACnB,iEAAiE;YACjE,mDAAmD;YACnDC;YACA,OAAO;QACT;QACA,qEAAqE;QACrED,OAAOE,MAAM,CAAC5C,IAAI,CAAC2C;QACnB,OAAOD,OAAOG,KAAK;IACrB;AACF;AAEA,SAASF;IACPtC;IAEA,qEAAqE;IACrE,oBAAoB;IACpBO;AACF;AAOO,SAASrB,iBAAiB2B,IAAkB;IACjD,yEAAyE;IACzE,IACE,kCAAkC;IAClCA,KAAKO,UAAU,IACf,uCAAuC;IACvCP,KAAKQ,UAAU,KAAK,CAAC,GACrB;QACA;IACF;IACA,kCAAkC;IAClCE,SAASxB,UAAUc;IACnBN;AACF;AAEA,SAAS0B;IACP/B,uBAAuB;IAEvB,0EAA0E;IAC1E,4EAA4E;IAC5E,wDAAwD;IACxD,MAAMuC,MAAMC,KAAKD,GAAG;IAEpB,gEAAgE;IAChE,IAAI5B,OAAO8B,SAAS5C;IACpB,MAAOc,SAAS,QAAQqB,oBAAoBrB,MAAO;QACjDA,KAAKC,YAAY,GAAGC,IAAAA,oCAAsB;QAE1C,MAAM6B,aAAaC,UAAUJ,KAAK5B;QAElC,0EAA0E;QAC1E,+BAA+B;QAC/B,MAAMI,oBAAoBJ,KAAKI,iBAAiB;QAChDJ,KAAKI,iBAAiB,GAAG;QACzBJ,KAAKK,wBAAwB,GAAG;QAEhC,OAAQ0B;YACN;gBACE,oEAAoE;gBACpE,sDAAsD;gBACtD;YACF;gBACE,iEAAiE;gBACjE,4DAA4D;gBAC5DE,QAAQ/C;gBACR,4BAA4B;gBAC5Bc,OAAO8B,SAAS5C;gBAChB;YACF;gBACE,IAAIc,KAAKG,KAAK,QAA8B;oBAC1C,8DAA8D;oBAC9D,gBAAgB;oBAChBH,KAAKG,KAAK;oBACVW,WAAW5B,UAAUc;gBACvB,OAAO,IAAII,mBAAmB;oBAC5B,mEAAmE;oBACnE,0BAA0B;oBAC1BJ,KAAKF,QAAQ,GAAGc,8BAAgB,CAACM,UAAU;oBAC3CJ,WAAW5B,UAAUc;gBACvB,OAAO;oBACL,uDAAuD;oBACvDiC,QAAQ/C;gBACV;gBACAc,OAAO8B,SAAS5C;gBAChB;YACF;gBACE6C;QACJ;IACF;AACF;AAEA;;;;;;;;;CASC,GACD,SAASG,WAAWlC,IAAkB;IACpC,IAAIA,KAAKF,QAAQ,KAAKc,8BAAgB,CAACM,UAAU,EAAE;QACjD,OAAO;IACT;IACAlB,KAAKI,iBAAiB,GAAG;IACzB,OAAO;AACT;AAEA,SAAS4B,UAAUJ,GAAW,EAAE5B,IAAkB;IAChD,MAAML,MAAMK,KAAKL,GAAG;IACpB,MAAMwC,QAAQC,IAAAA,kCAA2B,EAACR,KAAK5B,MAAML;IACrD,MAAMoC,aAAaM,kBAAkBT,KAAK5B,MAAMmC;IAEhD,IAAIJ,oBAAoDpC,IAAI2C,MAAM,KAAK,IAAI;QACzE,uEAAuE;QACvE,4EAA4E;QAC5E,wEAAwE;QACxE,EAAE;QACF,wEAAwE;QACxE,cAAc;QACd,EAAE;QACF,4EAA4E;QAC5E,mEAAmE;QACnE,uEAAuE;QACvE,2DAA2D;QAC3D,MAAMC,MAAM,IAAIC,IAAI7C,IAAI8C,IAAI;QAC5BF,IAAID,MAAM,GAAG;QACb,MAAMI,mBAAmBC,IAAAA,wBAAc,EAACJ,IAAIE,IAAI,EAAE9C,IAAIoB,OAAO;QAC7D,MAAM6B,qBAAqBR,IAAAA,kCAA2B,EACpDR,KACA5B,MACA0C;QAEF,OAAQE,mBAAmBC,MAAM;YAC/B,KAAKC,kBAAW,CAACC,KAAK;gBAAE;oBACtB,IAAIb,WAAWlC,OAAO;wBACpB4C,mBAAmBC,MAAM,GAAGC,kBAAW,CAACE,OAAO;wBAC/C1B,qBACE2B,IAAAA,4BAAqB,EAACL,oBAAoB5C,MAAM0C;oBAEpD;oBACA;gBACF;YACA,KAAKI,kBAAW,CAACE,OAAO;YACxB,KAAKF,kBAAW,CAACI,SAAS;YAC1B,KAAKJ,kBAAW,CAACK,QAAQ;gBAAE;oBAIzB;gBACF;YACA;gBACEP;QACJ;IACF;IAEA,OAAOb;AACT;AAEA,SAASM,kBACPT,GAAW,EACX5B,IAAkB,EAClBmC,KAAsB;IAEtB,OAAQA,MAAMU,MAAM;QAClB,KAAKC,kBAAW,CAACC,KAAK;YAAE;gBACtB,uEAAuE;gBACvE,sEAAsE;gBACtE,wBAAwB;gBAExB,wEAAwE;gBACxE,uEAAuE;gBACvE,oBAAoB;gBACpB,EAAE;gBACF,wCAAwC;gBACxC,iDAAiD;gBACjD,sDAAsD;gBACtD,wEAAwE;gBACxE,EAAE;gBACF,oCAAoC;gBACpCzB,qBAAqB2B,IAAAA,4BAAqB,EAACd,OAAOnC,MAAMA,KAAKL,GAAG;gBAEhE,yEAAyE;gBACzE,wEAAwE;gBACxE,0EAA0E;gBAC1E,mBAAmB;gBACnB,0EAA0E;gBAC1E,oBAAoB;gBACpBwC,MAAMiB,OAAO,GAAGxB,MAAM,KAAK;gBAE3B,sEAAsE;gBACtEO,MAAMU,MAAM,GAAGC,kBAAW,CAACE,OAAO;YAElC,gDAAgD;YAClD;QACA,KAAKF,kBAAW,CAACE,OAAO;YAAE;gBACxB,yEAAyE;gBACzE,uEAAuE;gBACvE,4CAA4C;gBAC5C,MAAMK,eAAelB,MAAMkB,YAAY;gBACvC,IAAIA,iBAAiB,MAAM;oBACzBlB,MAAMkB,YAAY,GAAG,IAAIC,IAAI;wBAACtD;qBAAK;gBACrC,OAAO;oBACLqD,aAAaE,GAAG,CAACvD;gBACnB;gBACA;YACF;QACA,KAAK8C,kBAAW,CAACK,QAAQ;YAAE;gBACzB,6CAA6C;gBAC7C;YACF;QACA,KAAKL,kBAAW,CAACI,SAAS;YAAE;gBAC1B,IAAIlD,KAAKG,KAAK,QAA6B;oBACzC,sEAAsE;oBACtE;gBACF;gBACA,wCAAwC;gBACxC,IAAI,CAACkB,oBAAoBrB,OAAO;oBAC9B,0DAA0D;oBAC1D;gBACF;gBACA,MAAMgB,OAAOmB,MAAMnB,IAAI;gBAEvB,qEAAqE;gBACrE,+FAA+F;gBAC/F,uFAAuF;gBACvF,+CAA+C;gBAC/C,MAAMnB,gBACJG,KAAKH,aAAa,KAAK2D,2BAAa,CAACC,GAAG,GACpCtB,MAAMuB,YAAY,GAChBF,2BAAa,CAACC,GAAG,GACjBD,2BAAa,CAACG,eAAe,GAC/B3D,KAAKH,aAAa;gBAExB,OAAQA;oBACN,KAAK2D,2BAAa,CAACC,GAAG;wBAAE;4BACtB,6DAA6D;4BAC7D,0DAA0D;4BAC1D,oEAAoE;4BACpE,2DAA2D;4BAC3D,EAAE;4BACF,+DAA+D;4BAC/D,iDAAiD;4BACjD,MAAM1B,aAAa6B,oCACjBhC,KACA5B,MACAmC,OACAnC,KAAKJ,oBAAoB,EACzBoB;4BAEF,IAAIe,kBAAkD;gCACpD,mCAAmC;gCACnC;4BACF;4BACA,MAAM1B,2BAA2BL,KAAKK,wBAAwB;4BAC9D,IAAIA,6BAA6B,MAAM;gCACrC,+DAA+D;gCAC/D,kEAAkE;gCAClE,MAAMwD,iBAAiB,IAAIC;gCAI3B,MAAMC,cAAcC,sBAClBpC,KACA5B,MACAmC,OACAnB,MACAX,0BACAwD;gCAEF,IAAII,sBAAsBJ,eAAeK,IAAI,GAAG;gCAChD,IAAID,qBAAqB;oCACvB,iEAAiE;oCACjE,cAAc;oCACd3C,qBACE6C,IAAAA,gDAAyC,EACvCnE,MACAmC,OACAqB,2BAAa,CAACY,UAAU,EACxBL,aACAF;gCAGN;4BACF;4BACA;wBACF;oBACA,KAAKL,2BAAa,CAACa,IAAI;oBACvB,KAAKb,2BAAa,CAACY,UAAU;oBAC7B,KAAKZ,2BAAa,CAACG,eAAe;wBAAE;4BAClC,6DAA6D;4BAC7D,qEAAqE;4BACrE,qEAAqE;4BACrE,sEAAsE;4BACtE,oEAAoE;4BACpE,oEAAoE;4BACpE,mBAAmB;4BACnB,MAAME,iBAAiB,IAAIC;4BAI3B,MAAMQ,qBAAqBC,4BACzB3C,KACA5B,MACAmC,OACAnC,KAAKJ,oBAAoB,EACzBoB,MACA6C,gBACAhE;4BAGF,IAAIoE,sBAAsBJ,eAAeK,IAAI,GAAG;4BAEhD,IACE,CAACD,uBACD9B,MAAMqC,aAAa,IACnBrC,MAAMsC,mBAAmB,KAAK3B,kBAAW,CAACC,KAAK,EAC/C;gCACA,oEAAoE;gCACpE,kEAAkE;gCAClE,gEAAgE;gCAChE,2BAA2B;gCAC3B,mEAAmE;gCACnE,8DAA8D;gCAC9D,wDAAwD;gCACxD,oEAAoE;gCACpE,gEAAgE;gCAChE,+DAA+D;gCAC/D,kEAAkE;gCAClE,+DAA+D;gCAC/D,kEAAkE;gCAClE,0DAA0D;gCAC1D,yCAAyC;gCACzCZ,MAAMsC,mBAAmB,GAAG3B,kBAAW,CAACI,SAAS;gCACjDe,sBAAsB;gCACtB,uDAAuD;gCACvDK,kBAAkB,CAAC,EAAE,GAAG;gCACxB,iEAAiE;gCACjE,wBAAwB;gCACxBA,kBAAkB,CAAC,EAAE,GAAG,CAAC;4BAC3B;4BAEA,IAAIL,qBAAqB;gCACvB,iEAAiE;gCACjE,aAAa;gCACb3C,qBACE6C,IAAAA,gDAAyC,EACvCnE,MACAmC,OACAtC,eACAyE,oBACAT;4BAGN;4BACA;wBACF;oBACA;wBACEhE;gBACJ;gBACA;YACF;QACA;YAAS;gBACPsC;YACF;IACF;IACA;AACF;AAEA,SAASyB,oCACPhC,GAAW,EACX5B,IAAkB,EAClBmC,KAA+B,EAC/BuC,OAA0B,EAC1BC,OAAkB;IAElB,6EAA6E;IAC7E,6EAA6E;IAC7E,0EAA0E;IAC1E,0EAA0E;IAC1E,mEAAmE;IACnE,oDAAoD;IACpD,EAAE;IACF,2EAA2E;IAC3E,8DAA8D;IAC9D,oCAAoC;IAEpC,uCAAuC;IACvC,MAAMC,UAAUC,IAAAA,oCAA6B,EAC3CjD,KACA5B,KAAKH,aAAa,EAClBsC,OACAwC,QAAQG,QAAQ;IAElBC,sBAAsBnD,KAAK5B,MAAMmC,OAAOyC,SAAS5E,KAAKL,GAAG,EAAEgF;IAE3D,iCAAiC;IACjC,MAAMK,kBAAkBN,OAAO,CAAC,EAAE;IAClC,MAAMO,kBAAkBN,QAAQO,KAAK;IACrC,IAAID,oBAAoB,MAAM;QAC5B,IAAK,MAAME,oBAAoBF,gBAAiB;YAC9C,IAAI,CAAC5D,oBAAoBrB,OAAO;gBAC9B,0DAA0D;gBAC1D;YACF;YACA,MAAMoF,eAAeH,eAAe,CAACE,iBAAiB;YACtD,MAAME,sBAAsBD,aAAaR,OAAO;YAChD,MAAMU,eACJN,eAAe,CAACG,iBAAiB;YACnC,MAAMI,sBACJD,cAAc,CAAC,EAAE;YACnB,IAAIE;YACJ,IACED,wBAAwBE,aACxBC,qCACEvD,OACAkD,qBACAE,sBAEF;gBACA,gDAAgD;gBAChDC,kBAAkB5B,oCAChBhC,KACA5B,MACAmC,OACAmD,cACAF;YAEJ,OAAO;gBACL,mDAAmD;gBACnD,uBAAuB;gBACvBI,kBAAkBG,iCAChB/D,KACA5B,MACAmC,OACAiD;YAEJ;YACA,IAAII,uBAAuD;gBACzD,mCAAmC;gBACnC;YACF;QACF;IACF;IAEA;AACF;AAEA,SAASG,iCACP/D,GAAW,EACX5B,IAAkB,EAClBmC,KAA+B,EAC/BnB,IAAe;IAEf,6EAA6E;IAC7E,oEAAoE;IACpE,4EAA4E;IAC5E,qEAAqE;IACrE,iEAAiE;IACjE,IAAIA,KAAK4E,kBAAkB,EAAE;QAC3B,2EAA2E;QAC3E,0EAA0E;QAC1E,2EAA2E;QAC3E,wEAAwE;QACxE,yEAAyE;QACzE,2EAA2E;QAC3E,0EAA0E;QAC1E,0BAA0B;QAC1B,EAAE;QACF,gEAAgE;QAChE,yEAAyE;QACzE,qEAAqE;QACrE,2EAA2E;QAC3E,gEAAgE;QAChE,iBAAiB;QACjB,EAAE;QACF,4EAA4E;QAC5E,sEAAsE;QACtE,wCAAwC;QACxC,IAAI5F,KAAKK,wBAAwB,KAAK,MAAM;YAC1CL,KAAKK,wBAAwB,GAAG,IAAIiD,IAAI;gBAACtC,KAAK8D,QAAQ;aAAC;QACzD,OAAO;YACL9E,KAAKK,wBAAwB,CAACkD,GAAG,CAACvC,KAAK8D,QAAQ;QACjD;QACA,gEAAgE;QAChE;IACF;IAEA,2EAA2E;IAC3E,MAAMF,UAAUC,IAAAA,oCAA6B,EAC3CjD,KACA5B,KAAKH,aAAa,EAClBsC,OACAnB,KAAK8D,QAAQ;IAEfC,sBAAsBnD,KAAK5B,MAAMmC,OAAOyC,SAAS5E,KAAKL,GAAG,EAAEqB;IAC3D,IAAIA,KAAKkE,KAAK,KAAK,MAAM;QACvB,IAAI,CAAC7D,oBAAoBrB,OAAO;YAC9B,0DAA0D;YAC1D;QACF;QACA,iCAAiC;QACjC,IAAK,MAAMmF,oBAAoBnE,KAAKkE,KAAK,CAAE;YACzC,MAAMW,YAAY7E,KAAKkE,KAAK,CAACC,iBAAiB;YAC9C,MAAMK,kBAAkBG,iCACtB/D,KACA5B,MACAmC,OACA0D;YAEF,IAAIL,uBAAuD;gBACzD,mCAAmC;gBACnC;YACF;QACF;IACF;IACA,+DAA+D;IAC/D;AACF;AAEA,SAASjB,4BACP3C,GAAW,EACX5B,IAAkB,EAClBmC,KAA+B,EAC/BuC,OAA0B,EAC1BC,OAAkB,EAClBd,cAAqD,EACrDhE,aAGiC;IAEjC,kEAAkE;IAClE,uEAAuE;IACvE,4EAA4E;IAC5E,0BAA0B;IAC1B,uEAAuE;IACvE,sEAAsE;IACtE,yEAAyE;IACzE,2EAA2E;IAC3E,yBAAyB;IACzB,MAAMmF,kBAAkBN,OAAO,CAAC,EAAE;IAClC,MAAMO,kBAAkBN,QAAQO,KAAK;IACrC,IAAIY,sBAAyD,CAAC;IAC9D,IAAIb,oBAAoB,MAAM;QAC5B,IAAK,MAAME,oBAAoBF,gBAAiB;YAC9C,MAAMG,eAAeH,eAAe,CAACE,iBAAiB;YACtD,MAAME,sBAAsBD,aAAaR,OAAO;YAChD,MAAMU,eACJN,eAAe,CAACG,iBAAiB;YACnC,MAAMI,sBACJD,cAAc,CAAC,EAAE;YACnB,IACEC,wBAAwBE,aACxBC,qCACEvD,OACAkD,qBACAE,sBAEF;gBACA,sEAAsE;gBACtE,MAAMQ,mBAAmBxB,4BACvB3C,KACA5B,MACAmC,OACAmD,cACAF,cACAvB,gBACAhE;gBAEFiG,mBAAmB,CAACX,iBAAiB,GAAGY;YAC1C,OAAO;gBACL,kEAAkE;gBAClE,kEAAkE;gBAClE,mBAAmB;gBACnB,OAAQlG;oBACN,KAAK2D,2BAAa,CAACG,eAAe;wBAAE;4BAClC,+DAA+D;4BAC/D,oEAAoE;4BACpE,mEAAmE;4BACnE,YAAY;4BACZ,EAAE;4BACF,2DAA2D;4BAC3D,+DAA+D;4BAC/D,EAAE;4BACF,+DAA+D;4BAC/D,8DAA8D;4BAC9D,kEAAkE;4BAClE,2BAA2B;4BAC3B,MAAMqC,4BACJZ,aAAaa,kBAAkB,KAC/BC,kCAAkB,CAACC,2BAA2B;4BAChD,MAAMJ,mBAAmBC,4BACrBI,4CACExE,KACA5B,MACAmC,OACAiD,cACA,MACAvB,kBAGFwC,IAAAA,0CAAmC,EAACjB;4BACxCU,mBAAmB,CAACX,iBAAiB,GAAGY;4BACxC;wBACF;oBACA,KAAKvC,2BAAa,CAACY,UAAU;wBAAE;4BAC7B,oEAAoE;4BACpE,iCAAiC;4BACjC,MAAM2B,mBAAmBO,mCACvB1E,KACA5B,MACAmC,OACAiD,cACA,OACAvB,gBACAhE;4BAEFiG,mBAAmB,CAACX,iBAAiB,GAAGY;4BACxC;wBACF;oBACA,KAAKvC,2BAAa,CAACa,IAAI;wBAAE;4BACvB,kEAAkE;4BAClE,gEAAgE;4BAChE,4DAA4D;4BAC5D,6DAA6D;4BAC7D,mBAAmB;4BACnB,EAAE;4BACF,iEAAiE;4BACjE,0DAA0D;4BAC1D,iEAAiE;4BACjE,oDAAoD;4BACpD,sBAAsB;4BACtB,EAAE;4BACF,mEAAmE;4BACnE,kEAAkE;4BAClE,mEAAmE;4BACnE,8DAA8D;4BAC9D,8BAA8B;4BAC9B,MAAM0B,mBAAmBO,mCACvB1E,KACA5B,MACAmC,OACAiD,cACA,OACAvB,gBACAhE;4BAEFiG,mBAAmB,CAACX,iBAAiB,GAAGY;4BACxC;wBACF;oBACA;wBACElG;gBACJ;YACF;QACF;IACF;IACA,MAAMkE,cAAiC;QACrCY,QAAQC,OAAO;QACfkB;QACA;QACA;QACAnB,QAAQ4B,YAAY;KACrB;IACD,OAAOxC;AACT;AAEA,SAASqC,4CACPxE,GAAW,EACX5B,IAAkB,EAClBmC,KAA+B,EAC/BnB,IAAe,EACfwF,oBAA+D,EAC/D3C,cAAqD;IAErD,6EAA6E;IAC7E,wEAAwE;IACxE,sEAAsE;IACtE,4EAA4E;IAC5E,mEAAmE;IACnE,4EAA4E;IAC5E,wEAAwE;IACxE,2DAA2D;IAE3D,uEAAuE;IACvE,oBAAoB;IACpB,IAAI4C,gBACFD,yBAAyB,OAAO,yBAAyB;IAE3D,MAAM5B,UAAUC,IAAAA,oCAA6B,EAC3CjD,KACA5B,KAAKH,aAAa,EAClBsC,OACAnB,KAAK8D,QAAQ;IAEf,OAAQF,QAAQ/B,MAAM;QACpB,KAAKC,kBAAW,CAACC,KAAK;YAAE;gBACtB,uEAAuE;gBACvE,2BAA2B;gBAC3B,yEAAyE;gBACzE,uEAAuE;gBACvE,wEAAwE;gBACxE,yEAAyE;gBACzE,gDAAgD;gBAEhD,iDAAiD;gBACjDc,eAAe6C,GAAG,CAChB1F,KAAK8D,QAAQ,EACb6B,IAAAA,8BAAuB,EACrB/B,SACA,wEAAwE;gBACxE,yEAAyE;gBACzE,mEAAmE;gBACnEpB,2BAAa,CAACG,eAAe;gBAGjC,IAAI6C,yBAAyB,WAAW;oBACtCC,gBAAgBD,uBAAuB;gBACzC,OAAO;gBACL,mEAAmE;gBACnE,sBAAsB;gBACxB;gBACA;YACF;QACA,KAAK1D,kBAAW,CAACI,SAAS;YAAE;gBAC1B,iCAAiC;gBACjC,MAAM0D,4BACJ5F,KAAKiF,kBAAkB,KAAKC,kCAAkB,CAACW,yBAAyB;gBAC1E,IAAID,2BAA2B;oBAC7B,oEAAoE;oBACpE,sEAAsE;oBACtE,yBAAyB;oBACzB,OAAOP,IAAAA,0CAAmC,EAACrF;gBAC7C;gBAOA;YACF;QACA,KAAK8B,kBAAW,CAACE,OAAO;YAAE;gBAGxB;YACF;QACA,KAAKF,kBAAW,CAACK,QAAQ;YAAE;gBAGzB;YACF;QACA;YACEyB;IACJ;IACA,MAAMkB,sBAAyD,CAAC;IAChE,IAAI9E,KAAKkE,KAAK,KAAK,MAAM;QACvB,IAAK,MAAMC,oBAAoBnE,KAAKkE,KAAK,CAAE;YACzC,MAAMW,YAAY7E,KAAKkE,KAAK,CAACC,iBAAiB;YAC9CW,mBAAmB,CAACX,iBAAiB,GACnCiB,4CACExE,KACA5B,MACAmC,OACA0D,WACAW,sBACA3C;QAEN;IACF;IACA,MAAME,cAAiC;QACrC/C,KAAK4D,OAAO;QACZkB;QACA;QACAW;QACAzF,KAAKuF,YAAY;KAClB;IACD,OAAOxC;AACT;AAEA,SAASuC,mCACP1E,GAAW,EACX5B,IAAkB,EAClBmC,KAA+B,EAC/BnB,IAAe,EACf8F,wBAAiC,EACjCjD,cAAqD,EACrDhE,aAA4D;IAE5D,6EAA6E;IAC7E,4EAA4E;IAC5E,uDAAuD;IACvD,EAAE;IACF,uEAAuE;IACvE,0EAA0E;IAC1E,wEAAwE;IACxE,kBAAkB;IAClB,MAAM+E,UAAUC,IAAAA,oCAA6B,EAC3CjD,KACA,0EAA0E;IAC1E,sCAAsC;IACtC,2FAA2F;IAC3F,2FAA2F;IAC3F,sCAAsC;IACtC/B,eACAsC,OACAnB,KAAK8D,QAAQ;IAGf,IAAIiC,iBAAkD;IAEtD,OAAQnC,QAAQ/B,MAAM;QACpB,KAAKC,kBAAW,CAACC,KAAK;YAAE;gBACtB,yDAAyD;gBACzDgE,iBAAiBJ,IAAAA,8BAAuB,EAAC/B,SAAS/E;gBAClD;YACF;QACA,KAAKiD,kBAAW,CAACI,SAAS;YAAE;gBAC1B,iCAAiC;gBACjC,IACE0B,QAAQoC,SAAS,IACjBC,IAAAA,4CAAqC,EACnCrC,QAAQ/E,aAAa,EACrBA,gBAEF;oBACA,qHAAqH;oBACrH,0CAA0C;oBAC1C,oEAAoE;oBACpE,+FAA+F;oBAC/F,iGAAiG;oBACjGkH,iBAAiBG,4BACftF,KACAO,OACAyC,SACA5D,MACAnB;gBAEJ;gBACA;YACF;QACA,KAAKiD,kBAAW,CAACE,OAAO;QACxB,KAAKF,kBAAW,CAACK,QAAQ;YAAE;gBACzB,yEAAyE;gBACzE,gFAAgF;gBAChF,IACE8D,IAAAA,4CAAqC,EACnCrC,QAAQ/E,aAAa,EACrBA,gBAEF;oBACAkH,iBAAiBG,4BACftF,KACAO,OACAyC,SACA5D,MACAnB;gBAEJ;gBACA;YACF;QACA;YACE+E;IACJ;IACA,MAAMkB,sBAAyD,CAAC;IAChE,IAAI9E,KAAKkE,KAAK,KAAK,MAAM;QACvB,IAAK,MAAMC,oBAAoBnE,KAAKkE,KAAK,CAAE;YACzC,MAAMW,YAAY7E,KAAKkE,KAAK,CAACC,iBAAiB;YAC9CW,mBAAmB,CAACX,iBAAiB,GACnCmB,mCACE1E,KACA5B,MACAmC,OACA0D,WACAiB,4BAA4BC,mBAAmB,MAC/ClD,gBACAhE;QAEN;IACF;IAEA,IAAIkH,mBAAmB,MAAM;QAC3B,2CAA2C;QAC3ClD,eAAe6C,GAAG,CAAC1F,KAAK8D,QAAQ,EAAEiC;IACpC;IAEA,8EAA8E;IAC9E,MAAMN,gBACJ,CAACK,4BAA4BC,mBAAmB,OAAO,YAAY;IAErE,MAAMhD,cAAiC;QACrC/C,KAAK4D,OAAO;QACZkB;QACA;QACAW;QACAzF,KAAKuF,YAAY;KAClB;IACD,OAAOxC;AACT;AAEA,SAASC,sBACPpC,GAAW,EACX5B,IAAkB,EAClBmC,KAA+B,EAC/BnB,IAAe,EACfX,wBAA8C,EAC9CwD,cAAqD;IAErD,0EAA0E;IAC1E,wEAAwE;IACxE,2EAA2E;IAC3E,uDAAuD;IACvD,EAAE;IACF,sDAAsD;IACtD,IAAIxD,yBAAyB8G,GAAG,CAACnG,KAAK8D,QAAQ,GAAG;QAC/C,yCAAyC;QACzC,OAAOwB,mCACL1E,KACA5B,MACAmC,OACAnB,MACA,OACA6C,gBACAL,2BAAa,CAACY,UAAU;IAE5B;IACA,IAAI0B,sBAAyD,CAAC;IAC9D,MAAMZ,QAAQlE,KAAKkE,KAAK;IACxB,IAAIA,UAAU,MAAM;QAClB,IAAK,MAAMC,oBAAoBD,MAAO;YACpC,MAAMW,YAAYX,KAAK,CAACC,iBAAiB;YACzCW,mBAAmB,CAACX,iBAAiB,GAAGnB,sBACtCpC,KACA5B,MACAmC,OACA0D,WACAxF,0BACAwD;QAEJ;IACF;IAEA,yEAAyE;IACzE,MAAME,cAAiC;QACrC/C,KAAK4D,OAAO;QACZkB;QACA;QACA;KACD;IACD,OAAO/B;AACT;AAEA,SAASgB,sBACPnD,GAAW,EACX5B,IAAkB,EAClBmC,KAA+B,EAC/ByC,OAA0B,EAC1BwC,QAAuB,EACvBpG,IAAe;IAEf,OAAQ4D,QAAQ/B,MAAM;QACpB,KAAKC,kBAAW,CAACC,KAAK;YACpB,sEAAsE;YACtEzB,qBACE+F,IAAAA,8BAAuB,EACrBlF,OACAwE,IAAAA,8BAAuB,EAAC/B,SAASpB,2BAAa,CAACC,GAAG,GAClD2D,UACApG;YAGJ;QACF,KAAK8B,kBAAW,CAACE,OAAO;YAAE;gBACxB,mEAAmE;gBACnE,+CAA+C;gBAC/C,OAAQ4B,QAAQ/E,aAAa;oBAC3B,KAAK2D,2BAAa,CAACC,GAAG;oBACtB,KAAKD,2BAAa,CAACY,UAAU;oBAC7B,KAAKZ,2BAAa,CAACa,IAAI;wBAErB;oBACF,KAAKb,2BAAa,CAACG,eAAe;wBAChC,4DAA4D;wBAC5D,oEAAoE;wBACpE,kEAAkE;wBAClE,iEAAiE;wBACjE,uBAAuB;wBACvB,IAAIzB,WAAWlC,OAAO;4BACpB,kEAAkE;4BAClE,oDAAoD;4BACpDsH,2BACE1F,KACA5B,MACA4E,SACAzC,OACAiF,UACApG;wBAEJ;wBACA;oBACF;wBACE4D,QAAQ/E,aAAa;gBACzB;gBACA;YACF;QACA,KAAKiD,kBAAW,CAACK,QAAQ;YAAE;gBACzB,oEAAoE;gBACpE,mEAAmE;gBACnE,OAAQyB,QAAQ/E,aAAa;oBAC3B,KAAK2D,2BAAa,CAACC,GAAG;oBACtB,KAAKD,2BAAa,CAACY,UAAU;oBAC7B,KAAKZ,2BAAa,CAACa,IAAI;wBAGrB;oBACF,KAAKb,2BAAa,CAACG,eAAe;wBAChC,iEAAiE;wBACjE,oEAAoE;wBACpE,qEAAqE;wBACrE,4DAA4D;wBAC5D,oBAAoB;wBACpB,EAAE;wBACF,sEAAsE;wBACtE,oEAAoE;wBACpE,4DAA4D;wBAC5D2D,2BAA2B1F,KAAK5B,MAAM4E,SAASzC,OAAOiF,UAAUpG;wBAChE;oBACF;wBACE4D,QAAQ/E,aAAa;gBACzB;gBACA;YACF;QACA,KAAKiD,kBAAW,CAACI,SAAS;YAExB;QACF;YACE0B;IACJ;AAEA,2EAA2E;AAC3E,2EAA2E;AAC3E,yDAAyD;AAC3D;AAEA,SAAS0C,2BACP1F,GAAW,EACX5B,IAAkB,EAClBuH,cAAiC,EACjCpF,KAA+B,EAC/BiF,QAAuB,EACvBpG,IAAe;IAEf,MAAMwG,sBAAsBC,IAAAA,2CAAoC,EAC9D7F,KACA2F;IAEF,OAAQC,oBAAoB3E,MAAM;QAChC,KAAKC,kBAAW,CAACC,KAAK;YACpB,iEAAiE;YACjE,mBAAmB;YACnB2E,0BACE1H,KAAKH,aAAa,EAClBsC,OACAnB,KAAK8D,QAAQ,EACbxD,qBACE+F,IAAAA,8BAAuB,EACrBlF,OACAwE,IAAAA,8BAAuB,EAACa,qBAAqBhE,2BAAa,CAACC,GAAG,GAC9D2D,UACApG;YAIN;QACF,KAAK8B,kBAAW,CAACE,OAAO;YAEtB;QACF,KAAKF,kBAAW,CAACI,SAAS;QAC1B,KAAKJ,kBAAW,CAACK,QAAQ;YAIvB;QACF;YACEqE;IACJ;AACF;AAEA,SAASN,4BACPtF,GAAW,EACXO,KAA+B,EAC/BoF,cAAiC,EACjCvG,IAAe,EACfnB,aAA4D;IAE5D,MAAM2H,sBAAsBC,IAAAA,2CAAoC,EAC9D7F,KACA2F;IAEF,IAAIC,oBAAoB3E,MAAM,KAAKC,kBAAW,CAACC,KAAK,EAAE;QACpD,kFAAkF;QAClF,0EAA0E;QAC1E,yEAAyE;QACzE,qEAAqE;QACrE,cAAc;QACd,MAAM4E,iBAAiBhB,IAAAA,8BAAuB,EAC5Ca,qBACA3H;QAEF6H,0BACE7H,eACAsC,OACAnB,KAAK8D,QAAQ,EACb8C,IAAAA,+BAAwB,EAACD;QAE3B,OAAOA;IACT,OAAO;QACL,8CAA8C;QAC9C,MAAME,8BAA8BL;QACpC,IACEP,IAAAA,4CAAqC,EACnCY,4BAA4BhI,aAAa,EACzCA,gBAEF;YACA,wEAAwE;YACxE,yCAAyC;YACzC,MAAMiI,eAAeC,IAAAA,oCAA6B,EAChDF;YAEF,MAAMF,iBAAiBhB,IAAAA,8BAAuB,EAC5CmB,cACAjI;YAEF6H,0BACE7H,eACAsC,OACAnB,KAAK8D,QAAQ,EACb8C,IAAAA,+BAAwB,EAACD;YAE3B,OAAOA;QACT;QACA,OAAQE,4BAA4BhF,MAAM;YACxC,KAAKC,kBAAW,CAACE,OAAO;gBACtB,sEAAsE;gBACtE,OAAO;YACT,KAAKF,kBAAW,CAACI,SAAS;YAC1B,KAAKJ,kBAAW,CAACK,QAAQ;gBACvB,wEAAwE;gBACxE,uEAAuE;gBACvE,8BAA8B;gBAC9B,OAAO;YACT;gBACE0E;gBACA,OAAO;QACX;IACF;AACF;AAEA,MAAMG,OAAO,KAAO;AAEpB,SAASN,0BACP7H,aAA4B,EAC5BsC,KAA+B,EAC/B2C,QAAyB,EACzBmD,OAAmD;IAEnD,sEAAsE;IACtEA,QAAQnJ,IAAI,CAAC,CAACoJ;QACZ,IAAIA,cAAc,MAAM;YACtB,yEAAyE;YACzE,MAAMC,UAAUC,IAAAA,wBAAiB,EAACvI,eAAesC,OAAO2C;YACxDuD,IAAAA,yBAAkB,EAACxG,KAAKD,GAAG,IAAIuG,SAASD;QAC1C;IACF,GAAGF;AACL;AAEA,SAAStC,qCACPvD,KAA+B,EAC/BoF,cAAuB,EACvBe,aAAsB;IAEtB,IAAIA,kBAAkBC,yBAAgB,EAAE;QACtC,0EAA0E;QAC1E,qEAAqE;QACrE,yEAAyE;QACzE,0EAA0E;QAC1E,6DAA6D;QAC7D,2DAA2D;QAC3D,0EAA0E;QAC1E,sEAAsE;QACtE,2EAA2E;QAC3E,qEAAqE;QACrE,OACEhB,mBACAiB,IAAAA,qCAA4B,EAC1BD,yBAAgB,EAChBE,OAAOC,WAAW,CAAC,IAAIC,gBAAgBxG,MAAMyG,cAAc;IAGjE;IACA,uEAAuE;IACvE,OAAOC,IAAAA,2BAAY,EAACP,eAAef;AACrC;AAEA,gFAAgF;AAChF,8EAA8E;AAC9E,6EAA6E;AAC7E,qEAAqE;AACrE,gFAAgF;AAEhF,SAASuB,qBAAqBC,CAAe,EAAEC,CAAe;IAC5D,6EAA6E;IAC7E,wEAAwE;IACxE,UAAU;IAEV,sEAAsE;IACtE,MAAMC,eAAeD,EAAElJ,QAAQ,GAAGiJ,EAAEjJ,QAAQ;IAC5C,IAAImJ,iBAAiB,GAAG;QACtB,OAAOA;IACT;IAEA,4EAA4E;IAC5E,4EAA4E;IAC5E,MAAMC,YAAYF,EAAE7I,KAAK,GAAG4I,EAAE5I,KAAK;IACnC,IAAI+I,cAAc,GAAG;QACnB,OAAOA;IACT;IAEA,0EAA0E;IAC1E,0EAA0E;IAC1E,OAAOF,EAAE1I,MAAM,GAAGyI,EAAEzI,MAAM;AAC5B;AAEA,SAASI,SAASyI,IAAyB,EAAEC,IAAkB;IAC7D,MAAMC,QAAQF,KAAKG,MAAM;IACzBH,KAAKI,IAAI,CAACH;IACVA,KAAK5I,UAAU,GAAG6I;IAClBG,WAAWL,MAAMC,MAAMC;AACzB;AAEA,SAASvH,SAASqH,IAAyB;IACzC,OAAOA,KAAKG,MAAM,KAAK,IAAI,OAAOH,IAAI,CAAC,EAAE;AAC3C;AAEA,SAASlH,QAAQkH,IAAyB;IACxC,IAAIA,KAAKG,MAAM,KAAK,GAAG;QACrB,OAAO;IACT;IACA,MAAMG,QAAQN,IAAI,CAAC,EAAE;IACrBM,MAAMjJ,UAAU,GAAG,CAAC;IACpB,MAAMkJ,OAAOP,KAAKQ,GAAG;IACrB,IAAID,SAASD,OAAO;QAClBN,IAAI,CAAC,EAAE,GAAGO;QACVA,KAAKlJ,UAAU,GAAG;QAClBoJ,aAAaT,MAAMO,MAAM;IAC3B;IACA,OAAOD;AACT;AAEA,SAAS9I,WAAWwI,IAAyB,EAAEC,IAAkB;IAC/D,MAAMC,QAAQD,KAAK5I,UAAU;IAC7B,IAAI6I,UAAU,CAAC,GAAG;QAChBD,KAAK5I,UAAU,GAAG,CAAC;QACnB,IAAI2I,KAAKG,MAAM,KAAK,GAAG;YACrB,MAAMI,OAAOP,KAAKQ,GAAG;YACrB,IAAID,SAASN,MAAM;gBACjBD,IAAI,CAACE,MAAM,GAAGK;gBACdA,KAAKlJ,UAAU,GAAG6I;gBAClBO,aAAaT,MAAMO,MAAML;YAC3B;QACF;IACF;AACF;AAEA,SAASvI,WAAWqI,IAAyB,EAAEC,IAAkB;IAC/D,MAAMC,QAAQD,KAAK5I,UAAU;IAC7B,IAAI6I,UAAU,CAAC,GAAG;QAChB,IAAIA,UAAU,GAAG;YACfO,aAAaT,MAAMC,MAAM;QAC3B,OAAO;YACL,MAAMS,cAAc,AAACR,QAAQ,MAAO;YACpC,MAAMS,SAASX,IAAI,CAACU,YAAY;YAChC,IAAIf,qBAAqBgB,QAAQV,QAAQ,GAAG;gBAC1C,iCAAiC;gBACjCI,WAAWL,MAAMC,MAAMC;YACzB,OAAO;gBACL,+CAA+C;gBAC/CO,aAAaT,MAAMC,MAAMC;YAC3B;QACF;IACF;AACF;AAEA,SAASG,WACPL,IAAyB,EACzBC,IAAkB,EAClBW,CAAS;IAET,IAAIV,QAAQU;IACZ,MAAOV,QAAQ,EAAG;QAChB,MAAMQ,cAAc,AAACR,QAAQ,MAAO;QACpC,MAAMS,SAASX,IAAI,CAACU,YAAY;QAChC,IAAIf,qBAAqBgB,QAAQV,QAAQ,GAAG;YAC1C,wCAAwC;YACxCD,IAAI,CAACU,YAAY,GAAGT;YACpBA,KAAK5I,UAAU,GAAGqJ;YAClBV,IAAI,CAACE,MAAM,GAAGS;YACdA,OAAOtJ,UAAU,GAAG6I;YAEpBA,QAAQQ;QACV,OAAO;YACL,+BAA+B;YAC/B;QACF;IACF;AACF;AAEA,SAASD,aACPT,IAAyB,EACzBC,IAAkB,EAClBW,CAAS;IAET,IAAIV,QAAQU;IACZ,MAAMT,SAASH,KAAKG,MAAM;IAC1B,MAAMU,aAAaV,WAAW;IAC9B,MAAOD,QAAQW,WAAY;QACzB,MAAMC,YAAY,AAACZ,CAAAA,QAAQ,CAAA,IAAK,IAAI;QACpC,MAAMa,OAAOf,IAAI,CAACc,UAAU;QAC5B,MAAME,aAAaF,YAAY;QAC/B,MAAMG,QAAQjB,IAAI,CAACgB,WAAW;QAE9B,wEAAwE;QACxE,IAAIrB,qBAAqBoB,MAAMd,QAAQ,GAAG;YACxC,IAAIe,aAAab,UAAUR,qBAAqBsB,OAAOF,QAAQ,GAAG;gBAChEf,IAAI,CAACE,MAAM,GAAGe;gBACdA,MAAM5J,UAAU,GAAG6I;gBACnBF,IAAI,CAACgB,WAAW,GAAGf;gBACnBA,KAAK5I,UAAU,GAAG2J;gBAElBd,QAAQc;YACV,OAAO;gBACLhB,IAAI,CAACE,MAAM,GAAGa;gBACdA,KAAK1J,UAAU,GAAG6I;gBAClBF,IAAI,CAACc,UAAU,GAAGb;gBAClBA,KAAK5I,UAAU,GAAGyJ;gBAElBZ,QAAQY;YACV;QACF,OAAO,IAAIE,aAAab,UAAUR,qBAAqBsB,OAAOhB,QAAQ,GAAG;YACvED,IAAI,CAACE,MAAM,GAAGe;YACdA,MAAM5J,UAAU,GAAG6I;YACnBF,IAAI,CAACgB,WAAW,GAAGf;YACnBA,KAAK5I,UAAU,GAAG2J;YAElBd,QAAQc;QACV,OAAO;YACL,kCAAkC;YAClC;QACF;IACF;AACF","ignoreList":[0]}