import type {
  CacheNodeSeedData,
  FlightRouterState,
  Segment,
} from '../../../shared/lib/app-router-types'
import type { CacheNode } from '../../../shared/lib/app-router-types'
import type { HeadData, ScrollRef } from '../../../shared/lib/app-router-types'
import { PrefetchHint } from '../../../shared/lib/app-router-types'
import {
  PAGE_SEGMENT_KEY,
  DEFAULT_SEGMENT_KEY,
  NOT_FOUND_SEGMENT_KEY,
} from '../../../shared/lib/segment'
import { matchSegment } from '../match-segments'
import { createHrefFromUrl } from './create-href-from-url'
import { fetchServerResponse } from './fetch-server-response'
import { dispatchAppRouterAction } from '../use-action-queue'
import {
  ACTION_SERVER_PATCH,
  type ServerPatchAction,
} from './router-reducer-types'
import { isNavigatingToNewRootLayout } from './is-navigating-to-new-root-layout'
import { getLastCommittedTree } from './reducers/committed-state'
import {
  convertServerPatchToFullTree,
  type NavigationSeed,
} from '../segment-cache/navigation'
import {
  type RouteTree,
  type RefreshState,
  type FulfilledRouteCacheEntry,
  convertReusedFlightRouterStateToRouteTree,
  readSegmentCacheEntry,
  waitForSegmentCacheEntry,
  markRouteEntryAsDynamicRewrite,
  invalidateRouteCacheEntries,
  getStaleAt,
  writeStaticStageResponseIntoCache,
  processRuntimePrefetchStream,
  writeDynamicRenderResponseIntoCache,
  EntryStatus,
} from '../segment-cache/cache'
import { FetchStrategy } from '../segment-cache/types'
import { discoverKnownRoute } from '../segment-cache/optimistic-routes'
import { NEXT_NAV_DEPLOYMENT_ID_HEADER } from '../../../lib/constants'
import type { NormalizedSearch } from '../segment-cache/cache-key'
import {
  getRenderedSearchFromVaryPath,
  type PageVaryPath,
} from '../segment-cache/vary-path'
import {
  readFromBFCache,
  readFromBFCacheDuringRegularNavigation,
  writeToBFCache,
  writeHeadToBFCache,
  updateBFCacheEntryStaleAt,
  computeDynamicStaleAt,
} from '../segment-cache/bfcache'

// This is yet another tree type that is used to track pending promises that
// need to be fulfilled once the dynamic data is received. The terminal nodes of
// this tree represent the new Cache Node trees that were created during this
// request. We can't use the Cache Node tree or Route State tree directly
// because those include reused nodes, too. This tree is discarded as soon as
// the navigation response is received.
export type NavigationTask = {
  status: NavigationTaskStatus
  // The router state that corresponds to the tree that this Task represents.
  route: FlightRouterState
  // The CacheNode that corresponds to the tree that this Task represents.
  node: CacheNode
  // The tree sent to the server during the dynamic request. If all the segments
  // are static, then this will be null, and no server request is required.
  // Otherwise, this is the same as `route`, except with the `refetch` marker
  // set on the top-most segment that needs to be fetched.
  dynamicRequestTree: FlightRouterState | null
  // The URL that should be used to fetch the dynamic data. This is only set
  // when the segment cannot be refetched from the current route, because it's
  // part of a "default" parallel slot that was reused during a navigation.
  refreshState: RefreshState | null
  children: Map<string, NavigationTask> | null
}

export const enum FreshnessPolicy {
  Default,
  Hydration,
  HistoryTraversal,
  RefreshAll,
  HMRRefresh,
  Gesture,
}

const enum NavigationTaskStatus {
  Pending,
  Fulfilled,
  Rejected,
}

/**
 * When a NavigationTask finishes, there may or may not be data still missing,
 * necessitating a retry.
 */
const enum NavigationTaskExitStatus {
  /**
   * No additional navigation is required.
   */
  Done = 0,
  /**
   * Some data failed to load, presumably due to a route tree mismatch. Perform
   * a soft retry to reload the entire tree.
   */
  SoftRetry = 1,
  /**
   * Some data failed to load in an unrecoverable way, e.g. in an inactive
   * parallel route. Fall back to a hard (MPA-style) retry.
   */
  HardRetry = 2,
}

export type NavigationRequestAccumulation = {
  separateRefreshUrls: Set<string> | null
  /**
   * Set when a navigation creates new leaf segments that should be
   * scrolled to. Stays null when no new segments are created (e.g.
   * during a refresh where the route structure didn't change).
   */
  scrollRef: ScrollRef | null
}

const noop = () => {}

export function createInitialCacheNodeForHydration(
  navigatedAt: number,
  initialTree: RouteTree,
  seedData: CacheNodeSeedData | null,
  seedHead: HeadData,
  seedDynamicStaleAt: number
): NavigationTask {
  // Create the initial cache node tree, using the data embedded into the
  // HTML document.
  const accumulation: NavigationRequestAccumulation = {
    separateRefreshUrls: null,
    scrollRef: null,
  }
  const task = createCacheNodeOnNavigation(
    navigatedAt,
    initialTree,
    null,
    FreshnessPolicy.Hydration,
    seedData,
    seedHead,
    seedDynamicStaleAt,
    false,
    accumulation
  )
  return task
}

// Creates a new Cache Node tree (i.e. copy-on-write) that represents the
// optimistic result of a navigation, using both the current Cache Node tree and
// data that was prefetched prior to navigation.
//
// At the moment we call this function, we haven't yet received the navigation
// response from the server. It could send back something completely different
// from the tree that was prefetched — due to rewrites, default routes, parallel
// routes, etc.
//
// But in most cases, it will return the same tree that we prefetched, just with
// the dynamic holes filled in. So we optimistically assume this will happen,
// and accept that the real result could be arbitrarily different.
//
// We'll reuse anything that was already in the previous tree, since that's what
// the server does.
//
// New segments (ones that don't appear in the old tree) are assigned an
// unresolved promise. The data for these promises will be fulfilled later, when
// the navigation response is received.
//
// The tree can be rendered immediately after it is created (that's why this is
// a synchronous function). Any new trees that do not have prefetch data will
// suspend during rendering, until the dynamic data streams in.
//
// Returns a Task object, which contains both the updated Cache Node and a path
// to the pending subtrees that need to be resolved by the navigation response.
//
// A return value of `null` means there were no changes, and the previous tree
// can be reused without initiating a server request.
export function startPPRNavigation(
  navigatedAt: number,
  oldUrl: URL,
  oldRenderedSearch: string,
  oldCacheNode: CacheNode | null,
  oldRouterState: FlightRouterState,
  newRouteTree: RouteTree,
  newMetadataVaryPath: PageVaryPath | null,
  freshness: FreshnessPolicy,
  seedData: CacheNodeSeedData | null,
  seedHead: HeadData | null,
  seedDynamicStaleAt: number,
  isSamePageNavigation: boolean,
  accumulation: NavigationRequestAccumulation
): NavigationTask | null {
  const didFindRootLayout = false
  const parentNeedsDynamicRequest = false
  const parentRefreshState = null
  const oldRootRefreshState: RefreshState = {
    canonicalUrl: createHrefFromUrl(oldUrl),
    renderedSearch: oldRenderedSearch as NormalizedSearch,
  }
  return updateCacheNodeOnNavigation(
    navigatedAt,
    oldUrl,
    oldCacheNode !== null ? oldCacheNode : undefined,
    oldRouterState,
    newRouteTree,
    newMetadataVaryPath,
    freshness,
    didFindRootLayout,
    seedData,
    seedHead,
    seedDynamicStaleAt,
    isSamePageNavigation,
    parentNeedsDynamicRequest,
    oldRootRefreshState,
    parentRefreshState,
    accumulation
  )
}

function updateCacheNodeOnNavigation(
  navigatedAt: number,
  oldUrl: URL,
  oldCacheNode: CacheNode | void,
  oldRouterState: FlightRouterState,
  newRouteTree: RouteTree,
  newMetadataVaryPath: PageVaryPath | null,
  freshness: FreshnessPolicy,
  didFindRootLayout: boolean,
  seedData: CacheNodeSeedData | null,
  seedHead: HeadData | null,
  seedDynamicStaleAt: number,
  isSamePageNavigation: boolean,
  parentNeedsDynamicRequest: boolean,
  oldRootRefreshState: RefreshState,
  parentRefreshState: RefreshState | null,
  accumulation: NavigationRequestAccumulation
): NavigationTask | null {
  // Check if this segment matches the one in the previous route.
  const oldSegment = oldRouterState[0]
  const newSegment = createSegmentFromRouteTree(newRouteTree)
  if (!matchSegment(newSegment, oldSegment)) {
    // This segment does not match the previous route. We're now entering the
    // new part of the target route. Switch to the "create" path.
    if (
      // Check if the route tree changed before we reached a layout. (The
      // highest-level layout in a route tree is referred to as the "root"
      // layout.) This could mean that we're navigating between two different
      // root layouts. When this happens, we perform a full-page (MPA-style)
      // navigation.
      //
      // However, the algorithm for deciding where to start rendering a route
      // (i.e. the one performed in order to reach this function) is stricter
      // than the one used to detect a change in the root layout. So just
      // because we're re-rendering a segment outside of the root layout does
      // not mean we should trigger a full-page navigation.
      //
      // Specifically, we handle dynamic parameters differently: two segments
      // are considered the same even if their parameter values are different.
      //
      // Refer to isNavigatingToNewRootLayout for details.
      //
      // Note that we only have to perform this extra traversal if we didn't
      // already discover a root layout in the part of the tree that is
      // unchanged. We also only need to compare the subtree that is not
      // shared. In the common case, this branch is skipped completely.
      (!didFindRootLayout &&
        isNavigatingToNewRootLayout(oldRouterState, newRouteTree)) ||
      // The global Not Found route (app/global-not-found.tsx) is a special
      // case, because it acts like a root layout, but in the router tree, it
      // is rendered in the same position as app/layout.tsx.
      //
      // Any navigation to the global Not Found route should trigger a
      // full-page navigation.
      //
      // TODO: We should probably model this by changing the key of the root
      // segment when this happens. Then the root layout check would work
      // as expected, without a special case.
      newSegment === NOT_FOUND_SEGMENT_KEY
    ) {
      return null
    }
    return createCacheNodeOnNavigation(
      navigatedAt,
      newRouteTree,
      newMetadataVaryPath,
      freshness,
      seedData,
      seedHead,
      seedDynamicStaleAt,
      parentNeedsDynamicRequest,
      accumulation
    )
  }

  const newSlots = newRouteTree.slots
  const oldRouterStateChildren = oldRouterState[1]
  const seedDataChildren = seedData !== null ? seedData[1] : null

  // We're currently traversing the part of the tree that was also part of
  // the previous route. If we discover a root layout, then we don't need to
  // trigger an MPA navigation.
  const childDidFindRootLayout =
    didFindRootLayout ||
    (newRouteTree.prefetchHints & PrefetchHint.IsRootLayout) !== 0

  let shouldRefreshDynamicData: boolean = false
  switch (freshness) {
    case FreshnessPolicy.Default:
    case FreshnessPolicy.HistoryTraversal:
    case FreshnessPolicy.Hydration:
    case FreshnessPolicy.Gesture:
      shouldRefreshDynamicData = false
      break
    case FreshnessPolicy.RefreshAll:
    case FreshnessPolicy.HMRRefresh:
      shouldRefreshDynamicData = true
      break
    default:
      freshness satisfies never
      break
  }

  // TODO: We're not consistent about how we do this check. Some places
  // check if the segment starts with PAGE_SEGMENT_KEY, but most seem to
  // check if there any any children, which is why I'm doing it here. We
  // should probably encode an empty children set as `null` though. Either
  // way, we should update all the checks to be consistent.
  const isLeafSegment = newSlots === null

  // Get the data for this segment. Since it was part of the previous route,
  // usually we just clone the data from the old CacheNode. However, during a
  // refresh or a revalidation, there won't be any existing CacheNode. So we
  // may need to consult the prefetch cache, like we would for a new segment.
  let newCacheNode: CacheNode
  let needsDynamicRequest: boolean
  if (
    oldCacheNode !== undefined &&
    !shouldRefreshDynamicData &&
    // During a same-page navigation, we always refetch the page segments
    !(isLeafSegment && isSamePageNavigation)
  ) {
    // Reuse the existing CacheNode
    const dropPrefetchRsc = false
    newCacheNode = reuseSharedCacheNode(dropPrefetchRsc, oldCacheNode)
    needsDynamicRequest = false
  } else {
    // If this is part of a refresh, ignore the existing CacheNode and create a
    // new one.
    const seedRsc = seedData !== null ? seedData[0] : null
    const result = createCacheNodeForSegment(
      navigatedAt,
      newRouteTree,
      seedRsc,
      newMetadataVaryPath,
      seedHead,
      freshness,
      seedDynamicStaleAt
    )
    newCacheNode = result.cacheNode
    needsDynamicRequest = result.needsDynamicRequest

    // Carry forward the old node's scrollRef. This preserves scroll
    // intent when a prior navigation's cache node is replaced by a
    // refresh before the scroll handler has had a chance to fire —
    // e.g. when router.push() and router.refresh() are called in the
    // same startTransition batch.
    if (oldCacheNode !== undefined) {
      newCacheNode.scrollRef = oldCacheNode.scrollRef
    }
  }

  // During a refresh navigation, there's a special case that happens when
  // entering a "default" slot. The default slot may not be part of the
  // current route; it may have been reused from an older route. If so,
  // we need to fetch its data from the old route's URL rather than current
  // route's URL. Keep track of this as we traverse the tree.
  const maybeRefreshState = newRouteTree.refreshState
  const refreshState =
    maybeRefreshState !== undefined && maybeRefreshState !== null
      ? // This segment is not present in the current route. Track its
        // refresh URL as we continue traversing the tree.
        maybeRefreshState
      : // Inherit the refresh URL from the parent.
        parentRefreshState

  // If this segment itself needs to fetch new data from the server, then by
  // definition it is being refreshed. Track its refresh URL so we know which
  // URL to request the data from.
  if (needsDynamicRequest && refreshState !== null) {
    accumulateRefreshUrl(accumulation, refreshState)
  }

  // As we diff the trees, we may sometimes modify (copy-on-write, not mutate)
  // the Route Tree that was returned by the server — for example, in the case
  // of default parallel routes, we preserve the currently active segment. To
  // avoid mutating the original tree, we clone the router state children along
  // the return path.
  let patchedRouterStateChildren: {
    [parallelRouteKey: string]: FlightRouterState
  } = {}
  let taskChildren = null

  // Most navigations require a request to fetch additional data from the
  // server, either because the data was not already prefetched, or because the
  // target route contains dynamic data that cannot be prefetched.
  //
  // However, if the target route is fully static, and it's already completely
  // loaded into the segment cache, then we can skip the server request.
  //
  // This starts off as `false`, and is set to `true` if any of the child
  // routes requires a dynamic request.
  let childNeedsDynamicRequest = false
  // As we traverse the children, we'll construct a FlightRouterState that can
  // be sent to the server to request the dynamic data. If it turns out that
  // nothing in the subtree is dynamic (i.e. childNeedsDynamicRequest is false
  // at the end), then this will be discarded.
  // TODO: We can probably optimize the format of this data structure to only
  // include paths that are dynamic. Instead of reusing the
  // FlightRouterState type.
  let dynamicRequestTreeChildren: {
    [parallelRouteKey: string]: FlightRouterState
  } = {}

  let newCacheNodeSlots: Record<string, CacheNode> | null = null
  if (newSlots !== null) {
    const oldCacheNodeSlots =
      oldCacheNode !== undefined ? oldCacheNode.slots : null

    newCacheNode.slots = newCacheNodeSlots = {}
    taskChildren = new Map()
    for (let parallelRouteKey in newSlots) {
      let newRouteTreeChild: RouteTree = newSlots[parallelRouteKey]
      const oldRouterStateChild: FlightRouterState | void =
        oldRouterStateChildren[parallelRouteKey]
      if (oldRouterStateChild === undefined) {
        // This should never happen, but if it does, it suggests a malformed
        // server response. Trigger a full-page navigation.
        return null
      }

      let seedDataChild: CacheNodeSeedData | void | null =
        seedDataChildren !== null ? seedDataChildren[parallelRouteKey] : null

      const oldSegmentChild = oldRouterStateChild[0]
      let newSegmentChild = createSegmentFromRouteTree(newRouteTreeChild)
      let seedHeadChild = seedHead
      if (
        // Skip this branch during a history traversal. We restore the tree that
        // was stashed in the history entry as-is.
        freshness !== FreshnessPolicy.HistoryTraversal &&
        newSegmentChild === DEFAULT_SEGMENT_KEY &&
        oldSegmentChild !== DEFAULT_SEGMENT_KEY
      ) {
        // This is a "default" segment. These are never sent by the server during
        // a soft navigation; instead, the client reuses whatever segment was
        // already active in that slot on the previous route.
        newRouteTreeChild = reuseActiveSegmentInDefaultSlot(
          newRouteTree,
          parallelRouteKey,
          oldRootRefreshState,
          oldRouterStateChild
        )
        newSegmentChild = createSegmentFromRouteTree(newRouteTreeChild)

        // Since we're switching to a different route tree, these are no
        // longer valid, because they correspond to the outer tree.
        seedDataChild = null
        seedHeadChild = null
      }

      const oldCacheNodeChild =
        oldCacheNodeSlots !== null
          ? oldCacheNodeSlots[parallelRouteKey]
          : undefined

      const taskChild = updateCacheNodeOnNavigation(
        navigatedAt,
        oldUrl,
        oldCacheNodeChild,
        oldRouterStateChild,
        newRouteTreeChild,
        newMetadataVaryPath,
        freshness,
        childDidFindRootLayout,
        seedDataChild ?? null,
        seedHeadChild,
        seedDynamicStaleAt,
        isSamePageNavigation,
        parentNeedsDynamicRequest || needsDynamicRequest,
        oldRootRefreshState,
        refreshState,
        accumulation
      )

      if (taskChild === null) {
        // One of the child tasks discovered a change to the root layout.
        // Immediately unwind from this recursive traversal. This will trigger a
        // full-page navigation.
        return null
      }

      // Recursively propagate up the child tasks.
      taskChildren.set(parallelRouteKey, taskChild)
      newCacheNodeSlots[parallelRouteKey] = taskChild.node

      // The child tree's route state may be different from the prefetched
      // route sent by the server. We need to clone it as we traverse back up
      // the tree.
      const taskChildRoute = taskChild.route
      patchedRouterStateChildren[parallelRouteKey] = taskChildRoute

      const dynamicRequestTreeChild = taskChild.dynamicRequestTree
      if (dynamicRequestTreeChild !== null) {
        // Something in the child tree is dynamic.
        childNeedsDynamicRequest = true
        dynamicRequestTreeChildren[parallelRouteKey] = dynamicRequestTreeChild
      } else {
        dynamicRequestTreeChildren[parallelRouteKey] = taskChildRoute
      }
    }
  }

  const newFlightRouterState: FlightRouterState = [
    createSegmentFromRouteTree(newRouteTree),
    patchedRouterStateChildren,
    refreshState !== null
      ? [refreshState.canonicalUrl, refreshState.renderedSearch]
      : null,
    null,
    newRouteTree.prefetchHints,
  ]

  return {
    status: needsDynamicRequest
      ? NavigationTaskStatus.Pending
      : NavigationTaskStatus.Fulfilled,
    route: newFlightRouterState,
    node: newCacheNode,
    dynamicRequestTree: createDynamicRequestTree(
      newFlightRouterState,
      dynamicRequestTreeChildren,
      needsDynamicRequest,
      childNeedsDynamicRequest,
      parentNeedsDynamicRequest
    ),
    refreshState,
    children: taskChildren,
  }
}

/**
 * Assigns a ScrollRef to a new leaf CacheNode so the scroll handler
 * knows to scroll to it after navigation. All leaves in the same
 * navigation share the same ScrollRef — the first segment to scroll
 * consumes it, preventing others from also scrolling.
 *
 * This is only called inside `createCacheNodeOnNavigation`, which only
 * runs when segments diverge from the previous route. So for a refresh
 * where the route structure stays the same, segments match, the update
 * path is taken, and this function is never called — no scroll ref is
 * assigned. A scroll ref is only assigned when the route actually
 * changed (e.g. a redirect, or a dynamic condition on the server that
 * produces a different route).
 *
 * Skipped during hydration (initial render should not scroll) and
 * history traversal (scroll restoration is handled separately).
 */
function accumulateScrollRef(
  freshness: FreshnessPolicy,
  cacheNode: CacheNode,
  accumulation: NavigationRequestAccumulation
): void {
  switch (freshness) {
    case FreshnessPolicy.Default:
    case FreshnessPolicy.Gesture:
    case FreshnessPolicy.RefreshAll:
    case FreshnessPolicy.HMRRefresh:
      if (accumulation.scrollRef === null) {
        accumulation.scrollRef = { current: true }
      }
      cacheNode.scrollRef = accumulation.scrollRef
      break
    case FreshnessPolicy.Hydration:
      // Initial render — no scroll.
      break
    case FreshnessPolicy.HistoryTraversal:
      // Back/forward — scroll restoration is handled separately.
      break
    default:
      freshness satisfies never
      break
  }
}

function createCacheNodeOnNavigation(
  navigatedAt: number,
  newRouteTree: RouteTree,
  newMetadataVaryPath: PageVaryPath | null,
  freshness: FreshnessPolicy,
  seedData: CacheNodeSeedData | null,
  seedHead: HeadData | null,
  seedDynamicStaleAt: number,
  parentNeedsDynamicRequest: boolean,
  accumulation: NavigationRequestAccumulation
): NavigationTask {
  // Same traversal as updateCacheNodeNavigation, but simpler. We switch to this
  // path once we reach the part of the tree that was not in the previous route.
  // We don't need to diff against the old tree, we just need to create a new
  // one. We also don't need to worry about any refresh-related logic.
  //
  // For the most part, this is a subset of updateCacheNodeOnNavigation, so any
  // change that happens in this function likely needs to be applied to that
  // one, too. However there are some places where the behavior intentionally
  // diverges, which is why we keep them separate.

  const newSegment = createSegmentFromRouteTree(newRouteTree)

  const newSlots = newRouteTree.slots
  const seedDataChildren = seedData !== null ? seedData[1] : null

  const seedRsc = seedData !== null ? seedData[0] : null
  const result = createCacheNodeForSegment(
    navigatedAt,
    newRouteTree,
    seedRsc,
    newMetadataVaryPath,
    seedHead,
    freshness,
    seedDynamicStaleAt
  )
  const newCacheNode = result.cacheNode
  const needsDynamicRequest = result.needsDynamicRequest

  const isLeafSegment = newSlots === null
  if (isLeafSegment) {
    accumulateScrollRef(freshness, newCacheNode, accumulation)
  }

  let patchedRouterStateChildren: {
    [parallelRouteKey: string]: FlightRouterState
  } = {}
  let taskChildren = null

  let childNeedsDynamicRequest = false
  let dynamicRequestTreeChildren: {
    [parallelRouteKey: string]: FlightRouterState
  } = {}

  let newCacheNodeSlots: Record<string, CacheNode> | null = null
  if (newSlots !== null) {
    newCacheNode.slots = newCacheNodeSlots = {}
    taskChildren = new Map()
    for (let parallelRouteKey in newSlots) {
      const newRouteTreeChild: RouteTree = newSlots[parallelRouteKey]
      const seedDataChild: CacheNodeSeedData | void | null =
        seedDataChildren !== null ? seedDataChildren[parallelRouteKey] : null

      const taskChild = createCacheNodeOnNavigation(
        navigatedAt,
        newRouteTreeChild,
        newMetadataVaryPath,
        freshness,
        seedDataChild ?? null,
        seedHead,
        seedDynamicStaleAt,
        parentNeedsDynamicRequest || needsDynamicRequest,
        accumulation
      )

      taskChildren.set(parallelRouteKey, taskChild)
      newCacheNodeSlots[parallelRouteKey] = taskChild.node

      const taskChildRoute = taskChild.route
      patchedRouterStateChildren[parallelRouteKey] = taskChildRoute

      const dynamicRequestTreeChild = taskChild.dynamicRequestTree
      if (dynamicRequestTreeChild !== null) {
        childNeedsDynamicRequest = true
        dynamicRequestTreeChildren[parallelRouteKey] = dynamicRequestTreeChild
      } else {
        dynamicRequestTreeChildren[parallelRouteKey] = taskChildRoute
      }
    }
  }

  const newFlightRouterState: FlightRouterState = [
    newSegment,
    patchedRouterStateChildren,
    null,
    null,
    newRouteTree.prefetchHints,
  ]

  return {
    status: needsDynamicRequest
      ? NavigationTaskStatus.Pending
      : NavigationTaskStatus.Fulfilled,
    route: newFlightRouterState,
    node: newCacheNode,
    dynamicRequestTree: createDynamicRequestTree(
      newFlightRouterState,
      dynamicRequestTreeChildren,
      needsDynamicRequest,
      childNeedsDynamicRequest,
      parentNeedsDynamicRequest
    ),
    // This route is not part of the current tree, so there's no reason to
    // track the refresh URL.
    refreshState: null,
    children: taskChildren,
  }
}

function createSegmentFromRouteTree(newRouteTree: RouteTree): Segment {
  if (newRouteTree.isPage) {
    // In a dynamic server response, the server embeds the search params into
    // the segment key, but in a static one it's omitted. The client handles
    // this inconsistency by adding the search params back right at the end.
    //
    // TODO: The only thing this is used for is to create a cache key for
    // ChildSegmentMap. But we already track the `renderedSearch` everywhere as
    // part of the varyPath. The plan is get rid of ChildSegmentMap and
    // store the page data in a CacheMap using the varyPath, like we do
    // for prefetches. Then we can remove it from the segment key.
    //
    // As an incremental step, we can grab the search params from the varyPath.
    const renderedSearch = getRenderedSearchFromVaryPath(newRouteTree.varyPath)
    if (renderedSearch === null) {
      return PAGE_SEGMENT_KEY
    }
    // This is based on equivalent logic in addSearchParamsIfPageSegment, used
    // on the server.
    const stringifiedQuery = JSON.stringify(
      Object.fromEntries(new URLSearchParams(renderedSearch))
    )
    return stringifiedQuery !== '{}'
      ? PAGE_SEGMENT_KEY + '?' + stringifiedQuery
      : PAGE_SEGMENT_KEY
  }
  return newRouteTree.segment
}

function patchRouterStateWithNewChildren(
  baseRouterState: FlightRouterState,
  newChildren: { [parallelRouteKey: string]: FlightRouterState }
): FlightRouterState {
  const clone: FlightRouterState = [baseRouterState[0], newChildren]
  // Based on equivalent logic in apply-router-state-patch-to-tree, but should
  // confirm whether we need to copy all of these fields. Not sure the server
  // ever sends, e.g. the refetch marker.
  if (2 in baseRouterState) {
    clone[2] = baseRouterState[2]
  }
  if (3 in baseRouterState) {
    clone[3] = baseRouterState[3]
  }
  if (4 in baseRouterState) {
    clone[4] = baseRouterState[4]
  }
  return clone
}

function createDynamicRequestTree(
  newRouterState: FlightRouterState,
  dynamicRequestTreeChildren: Record<string, FlightRouterState>,
  needsDynamicRequest: boolean,
  childNeedsDynamicRequest: boolean,
  parentNeedsDynamicRequest: boolean
): FlightRouterState | null {
  // Create a FlightRouterState that instructs the server how to render the
  // requested segment.
  //
  // Or, if neither this segment nor any of the children require a new data,
  // then we return `null` to skip the request.
  let dynamicRequestTree: FlightRouterState | null = null
  if (needsDynamicRequest) {
    dynamicRequestTree = patchRouterStateWithNewChildren(
      newRouterState,
      dynamicRequestTreeChildren
    )
    // The "refetch" marker is set on the top-most segment that requires new
    // data. We can omit it if a parent was already marked.
    if (!parentNeedsDynamicRequest) {
      dynamicRequestTree[3] = 'refetch'
    }
  } else if (childNeedsDynamicRequest) {
    // This segment does not request new data, but at least one of its
    // children does.
    dynamicRequestTree = patchRouterStateWithNewChildren(
      newRouterState,
      dynamicRequestTreeChildren
    )
  } else {
    dynamicRequestTree = null
  }
  return dynamicRequestTree
}

function accumulateRefreshUrl(
  accumulation: NavigationRequestAccumulation,
  refreshState: RefreshState
) {
  // This is a refresh navigation, and we're inside a "default" slot that's
  // not part of the current route; it was reused from an older route. In
  // order to get fresh data for this reused route, we need to issue a
  // separate request using the old route's URL.
  //
  // Track these extra URLs in the accumulated result. Later, we'll construct
  // an appropriate request for each unique URL in the final set. The reason
  // we don't do it immediately here is so we can deduplicate multiple
  // instances of the same URL into a single request. See
  // listenForDynamicRequest for more details.
  const refreshUrl = refreshState.canonicalUrl
  const separateRefreshUrls = accumulation.separateRefreshUrls
  if (separateRefreshUrls === null) {
    accumulation.separateRefreshUrls = new Set([refreshUrl])
  } else {
    separateRefreshUrls.add(refreshUrl)
  }
}

function reuseActiveSegmentInDefaultSlot(
  parentRouteTree: RouteTree,
  parallelRouteKey: string,
  oldRootRefreshState: RefreshState,
  oldRouterState: FlightRouterState
): RouteTree {
  // This is a "default" segment. These are never sent by the server during a
  // soft navigation; instead, the client reuses whatever segment was already
  // active in that slot on the previous route. This means if we later need to
  // refresh the segment, it will have to be refetched from the previous route's
  // URL. We store it in the Flight Router State.

  let reusedUrl: string
  let reusedRenderedSearch: NormalizedSearch
  const oldRefreshState = oldRouterState[2]
  if (oldRefreshState !== undefined && oldRefreshState !== null) {
    // This segment was already reused from an even older route. Keep its
    // existing URL and refresh state.
    reusedUrl = oldRefreshState[0]
    reusedRenderedSearch = oldRefreshState[1] as NormalizedSearch
  } else {
    // Since this route didn't already have a refresh state, it must have been
    // reachable from the root of the old route. So we use the refresh state
    // that represents the old route.
    reusedUrl = oldRootRefreshState.canonicalUrl
    reusedRenderedSearch = oldRootRefreshState.renderedSearch
  }

  const acc = { metadataVaryPath: null }
  const reusedRouteTree = convertReusedFlightRouterStateToRouteTree(
    parentRouteTree,
    parallelRouteKey,
    oldRouterState,
    reusedRenderedSearch,
    acc
  )
  reusedRouteTree.refreshState = {
    canonicalUrl: reusedUrl,
    renderedSearch: reusedRenderedSearch,
  }
  return reusedRouteTree
}

function reuseSharedCacheNode(
  dropPrefetchRsc: boolean,
  existingCacheNode: CacheNode
): CacheNode {
  // Clone the CacheNode that was already present in the previous tree.
  // Carry forward the scrollRef so scroll intent from a prior navigation
  // survives tree rebuilds (e.g. push + refresh in the same batch).
  return createCacheNode(
    existingCacheNode.rsc,
    dropPrefetchRsc ? null : existingCacheNode.prefetchRsc,
    existingCacheNode.head,
    dropPrefetchRsc ? null : existingCacheNode.prefetchHead,
    existingCacheNode.scrollRef
  )
}

function createCacheNodeForSegment(
  now: number,
  tree: RouteTree,
  seedRsc: React.ReactNode | null,
  metadataVaryPath: PageVaryPath | null,
  seedHead: HeadData | null,
  freshness: FreshnessPolicy,
  dynamicStaleAt: number
): { cacheNode: CacheNode; needsDynamicRequest: boolean } {
  // Construct a new CacheNode using data from the BFCache, the client's
  // Segment Cache, or seeded from a server response.
  //
  // If there's a cache miss, or if we only have a partial hit, we'll render
  // the partial state immediately, and spawn a request to the server to fill
  // in the missing data.
  //
  // If the segment is fully cached on the client already, we can omit this
  // segment from the server request.
  //
  // If we already have a dynamic data response associated with this navigation,
  // as in the case of a Server Action-initiated redirect or refresh, we may
  // also be able to use that data without spawning a new request. (This is
  // referred to as the "seed" data.)

  const isPage = tree.isPage

  // During certain kinds of navigations, we may be able to render from
  // the BFCache.
  switch (freshness) {
    case FreshnessPolicy.Default: {
      // Check BFCache during regular navigations. The entry's staleAt
      // determines whether it's still fresh. This is used when
      // staleTimes.dynamic is configured globally or when a page exports
      // unstable_dynamicStaleTime for per-page control.
      const bfcacheEntry = readFromBFCacheDuringRegularNavigation(
        now,
        tree.varyPath
      )
      if (bfcacheEntry !== null) {
        return {
          cacheNode: createCacheNode(
            bfcacheEntry.rsc,
            bfcacheEntry.prefetchRsc,
            bfcacheEntry.head,
            bfcacheEntry.prefetchHead
          ),
          needsDynamicRequest: false,
        }
      }
      break
    }
    case FreshnessPolicy.Hydration: {
      // This is not related to the BFCache but it is a special case.
      //
      // We should never spawn network requests during hydration. We must treat
      // the initial payload as authoritative, because the initial page load is
      // used as a last-ditch mechanism for recovering the app.
      //
      // This is also an important safety check because if this leaks into the
      // server rendering path (which theoretically it never should because the
      // server payload should be consistent), the server would hang because these
      // promises would never resolve.
      //
      // TODO: There is an existing case where the global "not found" boundary
      // triggers this path. But it does render correctly despite that. That's an
      // unusual render path so it's not surprising, but we should look into
      // modeling it in a more consistent way. See also the /_notFound special
      // case in updateCacheNodeOnNavigation.
      const rsc = seedRsc
      const prefetchRsc = null
      const head = isPage ? seedHead : null
      const prefetchHead = null
      writeToBFCache(
        now,
        tree.varyPath,
        rsc,
        prefetchRsc,
        head,
        prefetchHead,
        dynamicStaleAt
      )
      if (isPage && metadataVaryPath !== null) {
        writeHeadToBFCache(
          now,
          metadataVaryPath,
          head,
          prefetchHead,
          dynamicStaleAt
        )
      }
      return {
        cacheNode: createCacheNode(rsc, prefetchRsc, head, prefetchHead),
        needsDynamicRequest: false,
      }
    }
    case FreshnessPolicy.HistoryTraversal:
      const bfcacheEntry = readFromBFCache(tree.varyPath)
      if (bfcacheEntry !== null) {
        // Only show prefetched data if the dynamic data is still pending. This
        // avoids a flash back to the prefetch state in a case where it's highly
        // likely to have already streamed in.
        //
        // Tehnically, what we're actually checking is whether the dynamic
        // network response was received. But since it's a streaming response,
        // this does not mean that all the dynamic data has fully streamed in.
        // It just means that _some_ of the dynamic data was received. But as a
        // heuristic, we assume that the rest dynamic data will stream in
        // quickly, so it's still better to skip the prefetch state.
        const oldRsc = bfcacheEntry.rsc
        const oldRscDidResolve =
          !isDeferredRsc(oldRsc) || oldRsc.status !== 'pending'
        const dropPrefetchRsc = oldRscDidResolve
        return {
          cacheNode: createCacheNode(
            bfcacheEntry.rsc,
            dropPrefetchRsc ? null : bfcacheEntry.prefetchRsc,
            bfcacheEntry.head,
            dropPrefetchRsc ? null : bfcacheEntry.prefetchHead
          ),
          needsDynamicRequest: false,
        }
      }
      break
    case FreshnessPolicy.RefreshAll:
    case FreshnessPolicy.HMRRefresh:
    case FreshnessPolicy.Gesture:
      // Don't consult the BFCache.
      break
    default:
      freshness satisfies never
      break
  }

  let cachedRsc: React.ReactNode | null = null
  let isCachedRscPartial: boolean = true

  const segmentEntry = readSegmentCacheEntry(now, tree.varyPath)
  if (segmentEntry !== null) {
    switch (segmentEntry.status) {
      case EntryStatus.Fulfilled: {
        // Happy path: a cache hit
        cachedRsc = segmentEntry.rsc
        isCachedRscPartial = segmentEntry.isPartial
        break
      }
      case EntryStatus.Pending: {
        // We haven't received data for this segment yet, but there's already
        // an in-progress request. Since it's extremely likely to arrive
        // before the dynamic data response, we might as well use it.
        const promiseForFulfilledEntry = waitForSegmentCacheEntry(segmentEntry)
        cachedRsc = promiseForFulfilledEntry.then((entry) =>
          entry !== null ? entry.rsc : null
        )
        // Because the request is still pending, we typically don't know yet
        // whether the response will be partial. We shouldn't skip this segment
        // during the dynamic navigation request. Otherwise, we might need to
        // do yet another request to fill in the remaining data, creating
        // a waterfall.
        //
        // The one exception is if this segment is being fetched with via
        // prefetch={true} (i.e. the "force stale" or "full" strategy). If so,
        // we can assume the response will be full. This field is set to `false`
        // for such segments.
        isCachedRscPartial = segmentEntry.isPartial
        break
      }
      case EntryStatus.Empty:
      case EntryStatus.Rejected: {
        break
      }
      default: {
        segmentEntry satisfies never
        break
      }
    }
  }

  // Now combine the cached data with the seed data to determine what we can
  // render immediately, versus what needs to stream in later.

  // A partial state to show immediately while we wait for the final data to
  // arrive. If `rsc` is already a complete value (not partial), or if we
  // don't have any useful partial state, this will be `null`.
  let prefetchRsc: React.ReactNode | null
  // The final, resolved segment data. If the data is missing, this will be a
  // promise that resolves to the eventual data. A resolved value of `null`
  // means the data failed to load; the LayoutRouter will suspend indefinitely
  // until the router updates again (refer to finishNavigationTask).
  let rsc: React.ReactNode | null
  let doesSegmentNeedDynamicRequest: boolean

  if (seedRsc !== null) {
    // We already have a dynamic server response for this segment.
    if (isCachedRscPartial) {
      // The seed data may still be streaming in, so it's worth showing the
      // partial cached state in the meantime.
      prefetchRsc = cachedRsc
      rsc = seedRsc
    } else {
      // We already have a completely cached segment. Ignore the seed data,
      // which may still be streaming in. This shouldn't happen in the normal
      // case because the client will inform the server which segments are
      // already fully cached, and the server will skip rendering them.
      prefetchRsc = null
      rsc = cachedRsc
    }
    doesSegmentNeedDynamicRequest = false
  } else {
    if (isCachedRscPartial) {
      // The cached data contains dynamic holes, or it's missing entirely. We'll
      // show the partial state immediately (if available), and stream in the
      // final data.
      //
      // Create a pending promise that we can later write to when the
      // data arrives from the server.
      prefetchRsc = cachedRsc
      rsc = createDeferredRsc()
    } else {
      // The data is fully cached.
      prefetchRsc = null
      rsc = cachedRsc
    }
    doesSegmentNeedDynamicRequest = isCachedRscPartial
  }

  // If this is a page segment, we need to do the same for the head. This
  // follows analogous logic to the segment data above.
  // TODO: We don't need to store the head on the page segment's CacheNode; we
  // can lift it to the main state object. Then we can also delete
  // findHeadCache.

  let prefetchHead: HeadData | null = null
  let head: React.ReactNode | null = null
  let doesHeadNeedDynamicRequest: boolean = isPage

  if (isPage) {
    let cachedHead: HeadData | null = null
    let isCachedHeadPartial: boolean = true
    if (metadataVaryPath !== null) {
      const metadataEntry = readSegmentCacheEntry(now, metadataVaryPath)
      if (metadataEntry !== null) {
        switch (metadataEntry.status) {
          case EntryStatus.Fulfilled: {
            cachedHead = metadataEntry.rsc
            isCachedHeadPartial = metadataEntry.isPartial
            break
          }
          case EntryStatus.Pending: {
            cachedHead = waitForSegmentCacheEntry(metadataEntry).then(
              (entry) => (entry !== null ? entry.rsc : null)
            )
            isCachedHeadPartial = metadataEntry.isPartial
            break
          }
          case EntryStatus.Empty:
          case EntryStatus.Rejected: {
            break
          }
          default: {
            metadataEntry satisfies never
            break
          }
        }
      }
    }

    if (process.env.__NEXT_OPTIMISTIC_ROUTING && isCachedHeadPartial) {
      // TODO: When optimistic routing is enabled, don't block on waiting for
      // the viewport to resolve. This is a temporary workaround until Vary
      // Params are tracked when rendering the metadata. We'll fix it before
      // this feature is stable. However, it's not a critical issue because 1)
      // it will stream in eventually anyway 2) metadata is wrapped in an
      // internal Suspense boundary, so is always non-blocking; this only
      // affects the viewport node, which is meant to blocking, however... 3)
      // before Segment Cache landed this wasn't always the case, anyway, so
      // it's unlikely that many people are relying on this behavior. Still,
      // will be fixed before stable. It's the very next step in the sequence of
      // work on this project.
      //
      // This line of code works because the App Router treats `null` as
      // "no renderable head available", rather than an empty head. React treats
      // an empty string as empty.
      cachedHead = ''
    }

    if (seedHead !== null) {
      if (isCachedHeadPartial) {
        prefetchHead = cachedHead
        head = seedHead
      } else {
        prefetchHead = null
        head = cachedHead
      }
      doesHeadNeedDynamicRequest = false
    } else {
      if (isCachedHeadPartial) {
        prefetchHead = cachedHead
        head = createDeferredRsc()
      } else {
        prefetchHead = null
        head = cachedHead
      }
      doesHeadNeedDynamicRequest = isCachedHeadPartial
    }
  }

  // Now that we're creating a new segment, write its data to the BFCache. A
  // subsequent back/forward navigation will reuse this same data, until or
  // unless it's cleared by a refresh/revalidation.
  //
  // Skip BFCache writes for optimistic navigations since they are transient
  // and will be replaced by the canonical navigation.
  if (freshness !== FreshnessPolicy.Gesture) {
    writeToBFCache(
      now,
      tree.varyPath,
      rsc,
      prefetchRsc,
      head,
      prefetchHead,
      dynamicStaleAt
    )
    if (isPage && metadataVaryPath !== null) {
      writeHeadToBFCache(
        now,
        metadataVaryPath,
        head,
        prefetchHead,
        dynamicStaleAt
      )
    }
  }

  return {
    cacheNode: createCacheNode(rsc, prefetchRsc, head, prefetchHead),
    // TODO: We should store this field on the CacheNode itself. I think we can
    // probably unify NavigationTask, CacheNode, and DeferredRsc into a
    // single type. Or at least CacheNode and DeferredRsc.
    needsDynamicRequest:
      doesSegmentNeedDynamicRequest || doesHeadNeedDynamicRequest,
  }
}

function createCacheNode(
  rsc: React.ReactNode | null,
  prefetchRsc: React.ReactNode | null,
  head: React.ReactNode | null,
  prefetchHead: HeadData | null,
  scrollRef: ScrollRef | null = null
): CacheNode {
  return {
    rsc,
    prefetchRsc,
    head,
    prefetchHead,
    slots: null,
    scrollRef,
  }
}

// Represents whether the previuos navigation resulted in a route tree mismatch.
// A mismatch results in a refresh of the page. If there are two successive
// mismatches, we will fall back to an MPA navigation, to prevent a retry loop.
let previousNavigationDidMismatch = false

// Writes a dynamic server response into the tree created by
// updateCacheNodeOnNavigation. All pending promises that were spawned by the
// navigation will be resolved, either with dynamic data from the server, or
// `null` to indicate that the data is missing.
//
// A `null` value will trigger a lazy fetch during render, which will then patch
// up the tree using the same mechanism as the non-PPR implementation
// (serverPatchReducer).
//
// Usually, the server will respond with exactly the subset of data that we're
// waiting for — everything below the nearest shared layout. But technically,
// the server can return anything it wants.
//
// This does _not_ create a new tree; it modifies the existing one in place.
// Which means it must follow the Suspense rules of cache safety.
export function spawnDynamicRequests(
  task: NavigationTask,
  primaryUrl: URL,
  nextUrl: string | null,
  freshnessPolicy: FreshnessPolicy,
  accumulation: NavigationRequestAccumulation,
  // The route cache entry used for this navigation, if it came from route
  // prediction. Passed through so it can be marked as having a dynamic rewrite
  // if the server returns a different pathname than expected (indicating
  // dynamic rewrite behavior that varies by param value).
  routeCacheEntry: FulfilledRouteCacheEntry | null,
  // The original navigation's push/replace intent. Threaded through to the
  // server-patch retry logic so it can inherit the intent if the original
  // transition hasn't committed yet.
  navigateType: 'push' | 'replace'
): void {
  const dynamicRequestTree = task.dynamicRequestTree
  if (dynamicRequestTree === null) {
    // This navigation was fully cached. There are no dynamic requests to spawn.
    previousNavigationDidMismatch = false
    return
  }

  // This is intentionally not an async function to discourage the caller from
  // awaiting the result. Any subsequent async operations spawned by this
  // function should result in a separate navigation task, rather than
  // block the original one.
  //
  // In this function we spawn (but do not await) all the network requests that
  // block the navigation, and collect the promises. The next function,
  // `finishNavigationTask`, can await the promises in any order without
  // accidentally introducing a network waterfall.
  const primaryRequestPromise = fetchMissingDynamicData(
    task,
    dynamicRequestTree,
    primaryUrl,
    nextUrl,
    freshnessPolicy,
    routeCacheEntry
  )

  const separateRefreshUrls = accumulation.separateRefreshUrls
  let refreshRequestPromises: Array<
    ReturnType<typeof fetchMissingDynamicData>
  > | null = null
  if (separateRefreshUrls !== null) {
    // There are multiple URLs that we need to request the data from. This
    // happens when a "default" parallel route slot is present in the tree, and
    // its data cannot be fetched from the current route. We need to split the
    // combined dynamic request tree into separate requests per URL.

    // TODO: Create a scoped dynamic request tree that omits anything that
    // is not relevant to the given URL. Without doing this, the server may
    // sometimes render more data than necessary; this is not a regression
    // compared to the pre-Segment Cache implementation, though, just an
    // optimization we can make in the future.

    // Construct a request tree for each additional refresh URL. This will
    // prune away everything except the parts of the tree that match the
    // given refresh URL.
    refreshRequestPromises = []
    const canonicalUrl = createHrefFromUrl(primaryUrl)
    for (const refreshUrl of separateRefreshUrls) {
      if (refreshUrl === canonicalUrl) {
        // We already initiated a request for the this URL, above. Skip it.
        // TODO: This only happens because the main URL is not tracked as
        // part of the separateRefreshURLs set. There's probably a better way
        // to structure this so this case doesn't happen.
        continue
      }
      // TODO: Create a scoped dynamic request tree that omits anything that
      // is not relevant to the given URL. Without doing this, the server may
      // sometimes render more data than necessary; this is not a regression
      // compared to the pre-Segment Cache implementation, though, just an
      // optimization we can make in the future.
      // const scopedDynamicRequestTree = splitTaskByURL(task, refreshUrl)
      const scopedDynamicRequestTree = dynamicRequestTree
      if (scopedDynamicRequestTree !== null) {
        refreshRequestPromises.push(
          fetchMissingDynamicData(
            task,
            scopedDynamicRequestTree,
            new URL(refreshUrl, location.origin),
            // TODO: Just noticed that this should actually the Next-Url at the
            // time the refresh URL was set, not the current Next-Url. Need to
            // start tracking this alongside the refresh URL. In the meantime,
            // if a refresh fails due to a mismatch, it will trigger a
            // hard refresh.
            nextUrl,
            freshnessPolicy,
            routeCacheEntry
          )
        )
      }
    }
  }

  // Further async operations are moved into this separate function to
  // discourage sequential network requests.
  const voidPromise = finishNavigationTask(
    task,
    nextUrl,
    primaryRequestPromise,
    refreshRequestPromises,
    routeCacheEntry,
    navigateType
  )
  // `finishNavigationTask` is responsible for error handling, so we can attach
  // noop callbacks to this promise.
  voidPromise.then(noop, noop)
}

async function finishNavigationTask(
  task: NavigationTask,
  nextUrl: string | null,
  primaryRequestPromise: ReturnType<typeof fetchMissingDynamicData>,
  refreshRequestPromises: Array<
    ReturnType<typeof fetchMissingDynamicData>
  > | null,
  routeCacheEntry: FulfilledRouteCacheEntry | null,
  navigateType: 'push' | 'replace'
): Promise<void> {
  // Wait for all the requests to finish, or for the first one to fail.
  let exitStatus = await waitForRequestsToFinish(
    primaryRequestPromise,
    refreshRequestPromises
  )

  // Once the all the requests have finished, check the tree for any remaining
  // pending tasks. If anything is still pending, it means the server response
  // does not match the client, and we must refresh to get back to a consistent
  // state. We can skip this step if we already detected a mismatch during the
  // first phase; it doesn't matter in that case because we're going to refresh
  // the whole tree regardless.
  if (exitStatus === NavigationTaskExitStatus.Done) {
    exitStatus = abortRemainingPendingTasks(task, null, null)
  }

  switch (exitStatus) {
    case NavigationTaskExitStatus.Done: {
      // The task has completely finished. There's no missing data. Exit.
      previousNavigationDidMismatch = false
      return
    }
    case NavigationTaskExitStatus.SoftRetry: {
      // Some data failed to finish loading. Trigger a soft retry.
      // TODO: As an extra precaution against soft retry loops, consider
      // tracking whether a navigation was itself triggered by a retry. If two
      // happen in a row, fall back to a hard retry.
      const isHardRetry = false
      const primaryRequestResult = await primaryRequestPromise
      dispatchRetryDueToTreeMismatch(
        isHardRetry,
        primaryRequestResult.url,
        nextUrl,
        primaryRequestResult.seed,
        task.route,
        routeCacheEntry,
        navigateType
      )
      return
    }
    case NavigationTaskExitStatus.HardRetry: {
      // Some data failed to finish loading in a non-recoverable way, such as a
      // network error. Trigger an MPA navigation.
      //
      // Hard navigating/refreshing is how we prevent an infinite retry loop
      // caused by a network error — when the network fails, we fall back to the
      // browser behavior for offline navigations. In the future, Next.js may
      // introduce its own custom handling of offline navigations, but that
      // doesn't exist yet.
      const isHardRetry = true
      const primaryRequestResult = await primaryRequestPromise
      dispatchRetryDueToTreeMismatch(
        isHardRetry,
        primaryRequestResult.url,
        nextUrl,
        primaryRequestResult.seed,
        task.route,
        routeCacheEntry,
        navigateType
      )
      return
    }
    default: {
      return exitStatus satisfies never
    }
  }
}

function waitForRequestsToFinish(
  primaryRequestPromise: ReturnType<typeof fetchMissingDynamicData>,
  refreshRequestPromises: Array<
    ReturnType<typeof fetchMissingDynamicData>
  > | null
) {
  // Custom async combinator logic. This could be replaced by Promise.any but
  // we don't assume that's available.
  //
  // Each promise resolves once the server responsds and the data is written
  // into the CacheNode tree. Resolve the combined promise once all the
  // requests finish.
  //
  // Or, resolve as soon as one of the requests fails, without waiting for the
  // others to finish.
  return new Promise<NavigationTaskExitStatus>((resolve) => {
    const onFulfill = (result: { exitStatus: NavigationTaskExitStatus }) => {
      if (result.exitStatus === NavigationTaskExitStatus.Done) {
        remainingCount--
        if (remainingCount === 0) {
          // All the requests finished successfully.
          resolve(NavigationTaskExitStatus.Done)
        }
      } else {
        // One of the requests failed. Exit with a failing status.
        // NOTE: It's possible for one of the requests to fail with SoftRetry
        // and a later one to fail with HardRetry. In this case, we choose to
        // retry immediately, rather than delay the retry until all the requests
        // finish. If it fails again, we will hard retry on the next
        // attempt, anyway.
        resolve(result.exitStatus)
      }
    }
    // onReject shouldn't ever be called because fetchMissingDynamicData's
    // entire body is wrapped in a try/catch. This is just defensive.
    const onReject = () => resolve(NavigationTaskExitStatus.HardRetry)

    // Attach the listeners to the promises.
    let remainingCount = 1
    primaryRequestPromise.then(onFulfill, onReject)
    if (refreshRequestPromises !== null) {
      remainingCount += refreshRequestPromises.length
      refreshRequestPromises.forEach((refreshRequestPromise) =>
        refreshRequestPromise.then(onFulfill, onReject)
      )
    }
  })
}

function dispatchRetryDueToTreeMismatch(
  isHardRetry: boolean,
  retryUrl: URL,
  retryNextUrl: string | null,
  seed: NavigationSeed | null,
  baseTree: FlightRouterState,
  // The route cache entry used for this navigation, if it came from route
  // prediction. If the navigation results in a mismatch, we mark it as having
  // a dynamic rewrite so future predictions bail out.
  routeCacheEntry: FulfilledRouteCacheEntry | null,
  // The original navigation's push/replace intent.
  originalNavigateType: 'push' | 'replace'
) {
  // If the navigation used a route prediction, mark it as having a dynamic
  // rewrite since it resulted in a mismatch.
  if (routeCacheEntry !== null) {
    markRouteEntryAsDynamicRewrite(routeCacheEntry)
  } else if (seed !== null) {
    // Even without a direct reference to the route cache entry, we can still
    // mark the route as having a dynamic rewrite by traversing the known route
    // tree. This handles cases where the navigation didn't originate from a
    // route prediction, but still needs to mark the pattern.
    const metadataVaryPath = seed.metadataVaryPath
    if (metadataVaryPath !== null) {
      const now = Date.now()
      discoverKnownRoute(
        now,
        retryUrl.pathname,
        retryNextUrl,
        null,
        seed.routeTree,
        metadataVaryPath,
        false, // couldBeIntercepted - doesn't matter, we're just marking hasDynamicRewrite
        createHrefFromUrl(retryUrl),
        false, // supportsPerSegmentPrefetching - doesn't matter, we're just marking hasDynamicRewrite
        true // hasDynamicRewrite
      )
    }
  }

  // Invalidate all route cache entries. Other entries may have been derived
  // from the template before we knew it had a dynamic rewrite. This also
  // triggers re-prefetching of visible links.
  invalidateRouteCacheEntries(retryNextUrl, baseTree)

  // If this is the second time in a row that a navigation resulted in a
  // mismatch, fall back to a hard (MPA) refresh.
  isHardRetry = isHardRetry || previousNavigationDidMismatch
  previousNavigationDidMismatch = true

  // If the original navigation hasn't committed to the browser history yet
  // (the transition suspended before React committed), inherit its push/replace
  // intent. Otherwise, the pushState already ran, so use 'replace' to avoid
  // creating a duplicate history entry.
  //
  // This works because React entangles the retry's state update with the
  // original pending transition — they commit together as a single batch,
  // so the navigate type from the retry is what HistoryUpdater ultimately sees.
  //
  // TODO: Ideally this check would happen right before we schedule the React
  // update (i.e., closer to where the action is dispatched into the queue),
  // not here where the action is constructed. But the current action queue
  // doesn't provide a natural place for that. Revisit when we refactor the
  // action queue into a more reactive navigation model.
  const lastCommitted = getLastCommittedTree()
  const retryNavigateType: 'push' | 'replace' =
    lastCommitted !== null && baseTree !== lastCommitted
      ? originalNavigateType
      : 'replace'

  const retryAction: ServerPatchAction = {
    type: ACTION_SERVER_PATCH,
    previousTree: baseTree,
    url: retryUrl,
    nextUrl: retryNextUrl,
    seed,
    mpa: isHardRetry,
    navigateType: retryNavigateType,
  }
  dispatchAppRouterAction(retryAction)
}

async function fetchMissingDynamicData(
  task: NavigationTask,
  dynamicRequestTree: FlightRouterState,
  url: URL,
  nextUrl: string | null,
  freshnessPolicy: FreshnessPolicy,
  routeCacheEntry: FulfilledRouteCacheEntry | null
): Promise<{
  exitStatus: NavigationTaskExitStatus
  url: URL
  seed: NavigationSeed | null
}> {
  try {
    const result = await fetchServerResponse(url, {
      flightRouterState: dynamicRequestTree,
      nextUrl,
      isHmrRefresh: freshnessPolicy === FreshnessPolicy.HMRRefresh,
    })
    if (typeof result === 'string') {
      // fetchServerResponse will return an href to indicate that the SPA
      // navigation failed. For example, if the server triggered a hard
      // redirect, or the fetch request errored. Initiate an MPA navigation
      // to the given href.
      return {
        exitStatus: NavigationTaskExitStatus.HardRetry,
        url: new URL(result, location.origin),
        seed: null,
      }
    }
    const now = Date.now()

    const seed = convertServerPatchToFullTree(
      now,
      task.route,
      result.flightData,
      result.renderedSearch,
      result.dynamicStaleTime
    )

    // If the navigation lock is active, wait for it to be released before
    // writing the dynamic data. This allows tests to assert on the prefetched
    // UI state.
    if (process.env.__NEXT_EXPOSE_TESTING_API) {
      await waitForNavigationLock()
    }

    if (routeCacheEntry !== null && result.staticStageData !== null) {
      const { response: staticStageResponse, isResponsePartial } =
        result.staticStageData

      getStaleAt(now, staticStageResponse.s)
        .then((staleAt) => {
          const buildId =
            result.responseHeaders.get(NEXT_NAV_DEPLOYMENT_ID_HEADER) ??
            staticStageResponse.b

          writeStaticStageResponseIntoCache(
            now,
            staticStageResponse.f,
            buildId,
            staticStageResponse.h,
            staleAt,
            dynamicRequestTree,
            result.renderedSearch,
            isResponsePartial
          )
        })
        .catch(() => {
          // The static stage processing failed. Not fatal — the navigation
          // completed normally, we just won't write into the cache.
        })
    }

    if (routeCacheEntry !== null && result.runtimePrefetchStream !== null) {
      processRuntimePrefetchStream(
        now,
        result.runtimePrefetchStream,
        dynamicRequestTree,
        result.renderedSearch
      )
        .then((processed) => {
          if (processed !== null) {
            writeDynamicRenderResponseIntoCache(
              now,
              FetchStrategy.PPRRuntime,
              processed.flightDatas,
              processed.buildId,
              processed.isResponsePartial,
              processed.headVaryParams,
              processed.staleAt,
              processed.navigationSeed,
              null
            )
          }
        })
        .catch(() => {
          // The runtime prefetch cache write failed. Not fatal — the
          // navigation completed normally, we just won't cache runtime data.
        })
    }

    // result.dynamicStaleTime is in seconds (from the server's `d` field).
    // Convert to an absolute timestamp using the centralized helper.
    const dynamicStaleAt = computeDynamicStaleAt(now, result.dynamicStaleTime)

    const didReceiveUnknownParallelRoute = writeDynamicDataIntoNavigationTask(
      task,
      seed.routeTree,
      seed.data,
      seed.head,
      dynamicStaleAt,
      result.debugInfo
    )

    return {
      exitStatus: didReceiveUnknownParallelRoute
        ? NavigationTaskExitStatus.SoftRetry
        : NavigationTaskExitStatus.Done,
      url: new URL(result.canonicalUrl, location.origin),
      seed,
    }
  } catch {
    // This shouldn't happen because fetchServerResponse's entire body is
    // wrapped in a try/catch. If it does, though, it implies the server failed
    // to respond with any tree at all. So we must fall back to a hard retry.
    return {
      exitStatus: NavigationTaskExitStatus.HardRetry,
      url: url,
      seed: null,
    }
  }
}

function writeDynamicDataIntoNavigationTask(
  task: NavigationTask,
  serverRouteTree: RouteTree,
  dynamicData: CacheNodeSeedData | null,
  dynamicHead: HeadData,
  dynamicStaleAt: number,
  debugInfo: Array<any> | null
): boolean {
  if (task.status === NavigationTaskStatus.Pending && dynamicData !== null) {
    task.status = NavigationTaskStatus.Fulfilled
    finishPendingCacheNode(task.node, dynamicData, dynamicHead, debugInfo)

    // Update the BFCache entry's staleAt for this segment with the value
    // from the dynamic response. This applies the per-page
    // unstable_dynamicStaleTime if set, or the default DYNAMIC_STALETIME_MS.
    // We only update segments that received dynamic data — static segments
    // are unaffected.
    updateBFCacheEntryStaleAt(serverRouteTree.varyPath, dynamicStaleAt)
  }

  const taskChildren = task.children
  const serverChildren = serverRouteTree.slots
  const dynamicDataChildren = dynamicData !== null ? dynamicData[1] : null

  // Detect whether the server sends a parallel route slot that the client
  // doesn't know about.
  let didReceiveUnknownParallelRoute = false

  if (taskChildren !== null) {
    if (serverChildren !== null) {
      for (const parallelRouteKey in serverChildren) {
        const serverRouteTreeChild: RouteTree = serverChildren[parallelRouteKey]
        const dynamicDataChild: CacheNodeSeedData | null | void =
          dynamicDataChildren !== null
            ? dynamicDataChildren[parallelRouteKey]
            : null

        const taskChild = taskChildren.get(parallelRouteKey)
        if (taskChild === undefined) {
          // The server sent a child segment that the client doesn't know about.
          //
          // When we receive an unknown parallel route, we must consider it a
          // mismatch. This is unlike the case where the segment itself
          // mismatches, because multiple routes can be active simultaneously.
          // But a given layout should never have a mismatching set of
          // child slots.
          //
          // Theoretically, this should only happen in development during an HMR
          // refresh, because the set of parallel routes for a layout does not
          // change over the lifetime of a build/deployment. In production, we
          // should have already mismatched on either the build id or the segment
          // path. But as an extra precaution, we validate in prod, too.
          didReceiveUnknownParallelRoute = true
        } else {
          const taskSegment = taskChild.route[0]
          const serverSegment = createSegmentFromRouteTree(serverRouteTreeChild)
          if (
            matchSegment(serverSegment, taskSegment) &&
            dynamicDataChild !== null &&
            dynamicDataChild !== undefined
          ) {
            // Found a match for this task. Keep traversing down the task tree.
            const childDidReceiveUnknownParallelRoute =
              writeDynamicDataIntoNavigationTask(
                taskChild,
                serverRouteTreeChild,
                dynamicDataChild,
                dynamicHead,
                dynamicStaleAt,
                debugInfo
              )
            if (childDidReceiveUnknownParallelRoute) {
              didReceiveUnknownParallelRoute = true
            }
          }
        }
      }
    } else {
      if (serverChildren !== null) {
        // The server sent a child segment that the client doesn't know about.
        didReceiveUnknownParallelRoute = true
      }
    }
  }

  return didReceiveUnknownParallelRoute
}

function finishPendingCacheNode(
  cacheNode: CacheNode,
  dynamicData: CacheNodeSeedData,
  dynamicHead: HeadData,
  debugInfo: Array<any> | null
): void {
  // Writes a dynamic response into an existing Cache Node tree. This does _not_
  // create a new tree, it updates the existing tree in-place. So it must follow
  // the Suspense rules of cache safety — it can resolve pending promises, but
  // it cannot overwrite existing data. It can add segments to the tree (because
  // a missing segment will cause the layout router to suspend).
  // but it cannot delete them.
  //
  // We must resolve every promise in the tree, or else it will suspend
  // indefinitely. If we did not receive data for a segment, we will resolve its
  // data promise to `null` to trigger a lazy fetch during render.

  // Use the dynamic data from the server to fulfill the deferred RSC promise
  // on the Cache Node.
  const rsc = cacheNode.rsc
  const dynamicSegmentData = dynamicData[0]

  if (dynamicSegmentData === null) {
    // This is an empty CacheNode; this particular server request did not
    // render this segment. There may be a separate pending request that will,
    // though, so we won't abort the task until all pending requests finish.
    return
  }

  if (rsc === null) {
    // This is a lazy cache node. We can overwrite it. This is only safe
    // because we know that the LayoutRouter suspends if `rsc` is `null`.
    cacheNode.rsc = dynamicSegmentData
  } else if (isDeferredRsc(rsc)) {
    // This is a deferred RSC promise. We can fulfill it with the data we just
    // received from the server. If it was already resolved by a different
    // navigation, then this does nothing because we can't overwrite data.
    rsc.resolve(dynamicSegmentData, debugInfo)
  } else {
    // This is not a deferred RSC promise, nor is it empty, so it must have
    // been populated by a different navigation. We must not overwrite it.
  }

  // Check if this is a leaf segment. If so, it will have a `head` property with
  // a pending promise that needs to be resolved with the dynamic head from
  // the server.
  const head = cacheNode.head
  if (isDeferredRsc(head)) {
    head.resolve(dynamicHead, debugInfo)
  }
}

function abortRemainingPendingTasks(
  task: NavigationTask,
  error: any,
  debugInfo: Array<any> | null
): NavigationTaskExitStatus {
  let exitStatus
  if (task.status === NavigationTaskStatus.Pending) {
    // The data for this segment is still missing.
    task.status = NavigationTaskStatus.Rejected
    abortPendingCacheNode(task.node, error, debugInfo)

    // If the server failed to fulfill the data for this segment, it implies
    // that the route tree received from the server mismatched the tree that
    // was previously prefetched.
    //
    // In an app with fully static routes and no proxy-driven redirects or
    // rewrites, this should never happen, because the route for a URL would
    // always be the same across multiple requests. So, this implies that some
    // runtime routing condition changed, likely in a proxy, without being
    // pushed to the client.
    //
    // When this happens, we treat this the same as a refresh(). The entire
    // tree will be re-rendered from the root.
    if (task.refreshState === null) {
      // Trigger a "soft" refresh. Essentially the same as calling `refresh()`
      // in a Server Action.
      exitStatus = NavigationTaskExitStatus.SoftRetry
    } else {
      // The mismatch was discovered inside an inactive parallel route. This
      // implies the inactive parallel route is no longer reachable at the URL
      // that originally rendered it. Fall back to an MPA refresh.
      // TODO: An alternative could be to trigger a soft refresh but to _not_
      // re-use the inactive parallel routes this time. Similar to what would
      // happen if were to do a hard refrehs, but without the HTML page.
      exitStatus = NavigationTaskExitStatus.HardRetry
    }
  } else {
    // This segment finished. (An error here is treated as Done because they are
    // surfaced to the application during render.)
    exitStatus = NavigationTaskExitStatus.Done
  }

  const taskChildren = task.children
  if (taskChildren !== null) {
    for (const [, taskChild] of taskChildren) {
      const childExitStatus = abortRemainingPendingTasks(
        taskChild,
        error,
        debugInfo
      )
      // Propagate the exit status up the tree. The statuses are ordered by
      // their precedence.
      if (childExitStatus > exitStatus) {
        exitStatus = childExitStatus
      }
    }
  }

  return exitStatus
}

function abortPendingCacheNode(
  cacheNode: CacheNode,
  error: any,
  debugInfo: Array<any> | null
): void {
  const rsc = cacheNode.rsc
  if (isDeferredRsc(rsc)) {
    if (error === null) {
      // This will trigger a lazy fetch during render.
      rsc.resolve(null, debugInfo)
    } else {
      // This will trigger an error during rendering.
      rsc.reject(error, debugInfo)
    }
  }

  // Check if this is a leaf segment. If so, it will have a `head` property with
  // a pending promise that needs to be resolved. If an error was provided, we
  // will not resolve it with an error, since this is rendered at the root of
  // the app. We want the segment to error, not the entire app.
  const head = cacheNode.head
  if (isDeferredRsc(head)) {
    head.resolve(null, debugInfo)
  }
}

const DEFERRED = Symbol()

type PendingDeferredRsc<T> = Promise<T> & {
  status: 'pending'
  resolve: (value: T, debugInfo: Array<any> | null) => void
  reject: (error: any, debugInfo: Array<any> | null) => void
  tag: Symbol
  _debugInfo: Array<any>
}

type FulfilledDeferredRsc<T> = Promise<T> & {
  status: 'fulfilled'
  value: T
  resolve: (value: T, debugInfo: Array<any> | null) => void
  reject: (error: any, debugInfo: Array<any> | null) => void
  tag: Symbol
  _debugInfo: Array<any>
}

type RejectedDeferredRsc<T> = Promise<T> & {
  status: 'rejected'
  reason: any
  resolve: (value: T, debugInfo: Array<any> | null) => void
  reject: (error: any, debugInfo: Array<any> | null) => void
  tag: Symbol
  _debugInfo: Array<any>
}

type DeferredRsc<T extends React.ReactNode = React.ReactNode> =
  | PendingDeferredRsc<T>
  | FulfilledDeferredRsc<T>
  | RejectedDeferredRsc<T>

// This type exists to distinguish a DeferredRsc from a Flight promise. It's a
// compromise to avoid adding an extra field on every Cache Node, which would be
// awkward because the pre-PPR parts of codebase would need to account for it,
// too. We can remove it once type Cache Node type is more settled.
export function isDeferredRsc(value: any): value is DeferredRsc {
  return value && typeof value === 'object' && value.tag === DEFERRED
}

function createDeferredRsc<
  T extends React.ReactNode = React.ReactNode,
>(): PendingDeferredRsc<T> {
  // Create an unresolved promise that represents data derived from a Flight
  // response. The promise will be resolved later as soon as we start receiving
  // data from the server, i.e. as soon as the Flight client decodes and returns
  // the top-level response object.

  // The `_debugInfo` field contains profiling information. Promises that are
  // created by Flight already have this info added by React; for any derived
  // promise created by the router, we need to transfer the Flight debug info
  // onto the derived promise.
  //
  // The debug info represents the latency between the start of the navigation
  // and the start of rendering. (It does not represent the time it takes for
  // whole stream to finish.)
  const debugInfo: Array<any> = []

  let resolve: any
  let reject: any
  const pendingRsc = new Promise<T>((res, rej) => {
    resolve = res
    reject = rej
  }) as PendingDeferredRsc<T>
  pendingRsc.status = 'pending'
  pendingRsc.resolve = (value: T, responseDebugInfo: Array<any> | null) => {
    if (pendingRsc.status === 'pending') {
      const fulfilledRsc: FulfilledDeferredRsc<T> = pendingRsc as any
      fulfilledRsc.status = 'fulfilled'
      fulfilledRsc.value = value
      if (responseDebugInfo !== null) {
        // Transfer the debug info to the derived promise.
        debugInfo.push.apply(debugInfo, responseDebugInfo)
      }
      resolve(value)
    }
  }
  pendingRsc.reject = (error: any, responseDebugInfo: Array<any> | null) => {
    if (pendingRsc.status === 'pending') {
      const rejectedRsc: RejectedDeferredRsc<T> = pendingRsc as any
      rejectedRsc.status = 'rejected'
      rejectedRsc.reason = error
      if (responseDebugInfo !== null) {
        // Transfer the debug info to the derived promise.
        debugInfo.push.apply(debugInfo, responseDebugInfo)
      }
      reject(error)
    }
  }
  pendingRsc.tag = DEFERRED
  pendingRsc._debugInfo = debugInfo

  return pendingRsc
}

/**
 * Helper for the Instant Navigation Testing API. Waits for the navigation lock
 * to be released before returning. The network request has already completed by
 * the time this is called, so this only delays writing the dynamic data.
 *
 * Not exposed in production builds by default.
 */
async function waitForNavigationLock(): Promise<void> {
  if (process.env.__NEXT_EXPOSE_TESTING_API) {
    const { waitForNavigationLockIfActive } =
      require('../segment-cache/navigation-testing-lock') as typeof import('../segment-cache/navigation-testing-lock')
    await waitForNavigationLockIfActive()
  }
}