// Copyright 2020 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "content/browser/preloading/prerender/prerender_host_registry.h"

#include <algorithm>

#include "base/auto_reset.h"
#include "base/byte_size.h"
#include "base/check.h"
#include "base/check_op.h"
#include "base/feature_list.h"
#include "base/functional/bind.h"
#include "base/memory_coordinator/memory_coordinator_features.h"
#include "base/memory_coordinator/utils.h"
#include "base/metrics/field_trial_params.h"
#include "base/metrics/histogram_functions.h"
#include "base/notreached.h"
#include "base/numerics/safe_conversions.h"
#include "base/observer_list.h"
#include "base/system/sys_info.h"
#include "base/task/sequenced_task_runner.h"
#include "base/task/single_thread_task_runner.h"
#include "base/time/time.h"
#include "build/build_config.h"
#include "content/browser/devtools/devtools_instrumentation.h"
#include "content/browser/devtools/render_frame_devtools_agent_host.h"
#include "content/browser/preloading/preloading_data_impl.h"
#include "content/browser/preloading/preloading_trigger_type_impl.h"
#include "content/browser/preloading/prerender/devtools_prerender_attempt.h"
#include "content/browser/preloading/prerender/prerender_features.h"
#include "content/browser/preloading/prerender/prerender_final_status.h"
#include "content/browser/preloading/prerender/prerender_metrics.h"
#include "content/browser/preloading/prerender/prerender_navigation_utils.h"
#include "content/browser/preloading/prerender/prerender_new_tab_handle.h"
#include "content/browser/preloading/speculation_rules/speculation_rules_util.h"
#include "content/browser/renderer_host/frame_tree_node.h"
#include "content/browser/renderer_host/navigation_request.h"
#include "content/browser/renderer_host/render_frame_host_impl.h"
#include "content/browser/web_contents/web_contents_impl.h"
#include "content/common/frame.mojom.h"
#include "content/public/browser/preloading.h"
#include "content/public/browser/preloading_data.h"
#include "content/public/browser/render_frame_host.h"
#include "content/public/browser/visibility.h"
#include "content/public/browser/web_contents.h"
#include "content/public/browser/web_contents_delegate.h"
#include "net/base/load_flags.h"
#include "services/network/public/cpp/simple_url_loader.h"
#include "third_party/abseil-cpp/absl/cleanup/cleanup.h"
#include "third_party/blink/public/common/features.h"
#include "url/gurl.h"

namespace content {

namespace {

// If enabled, cancels the prerender when a navigation in the prerendered page
// is restarted as cross-document. This feature is enabled by default as
// a crash fix. The feature flag is kept as a kill switch.
BASE_FEATURE(kPrerenderCancelOnCrossDocumentRestart,
             base::FEATURE_ENABLED_BY_DEFAULT);

constexpr base::MemoryConsumerTraits kPrerenderHostRegistryTraits(
    base::MemoryConsumerTraits::EstimatedMemoryUsage::kLarge,
    base::MemoryConsumerTraits::ReleaseMemoryCost::kRequiresTraversal,
    base::MemoryConsumerTraits::InformationRetention::kLossy,
    base::MemoryConsumerTraits::ExecutionType::kAsynchronous,
    base::MemoryConsumerTraits::IsStateful::kNo);

bool IsBackground(Visibility visibility) {
  // PrerenderHostRegistry treats HIDDEN and OCCLUDED as background.
  switch (visibility) {
    case Visibility::HIDDEN:
    case Visibility::OCCLUDED:
      return true;
    case Visibility::VISIBLE:
      return false;
  }
}

bool DeviceHasEnoughMemoryForPrerender() {
  // This method disallows prerendering on low-end devices if the
  // kPrerender2MemoryControls feature is enabled.
  if (!base::FeatureList::IsEnabled(
          blink::features::kPrerender2MemoryControls)) {
    return true;
  }

  // On Android, Prerender2 is only enabled for 2GB+ high memory devices.  The
  // default threshold value is set to 1700 MB to account for all 2GB devices
  // which report lower RAM due to carveouts.
  // Previously used the same default threshold as the back/forward cache. See
  // comments in DeviceHasEnoughMemoryForBackForwardCache().
  // TODO(crbug.com/40277975): experiment with 1200 MB threshold like
  // back/forward cache.
  static constexpr int kDefaultMemoryThresholdMb =
#if BUILDFLAG(IS_ANDROID)
      1700;
#else
      0;
#endif

  // The default is overridable by field trial param.
  int memory_threshold_mb = base::GetFieldTrialParamByFeatureAsInt(
      blink::features::kPrerender2MemoryControls,
      blink::features::kPrerender2MemoryThresholdParamName,
      kDefaultMemoryThresholdMb);

  return base::SysInfo::AmountOfTotalPhysicalMemory() >
         base::MiB(base::saturated_cast<uint64_t>(memory_threshold_mb));
}

// Create a resource request for `back_url` that only checks whether the
// resource is in the HTTP cache.
std::unique_ptr<network::SimpleURLLoader> CreateHttpCacheQueryingResourceLoad(
    const GURL& back_url) {
  std::unique_ptr<network::ResourceRequest> request =
      std::make_unique<network::ResourceRequest>();
  request->url = back_url;
  request->load_flags =
      net::LOAD_ONLY_FROM_CACHE | net::LOAD_SKIP_CACHE_VALIDATION;
  if (base::FeatureList::IsEnabled(
          blink::features::kAvoidTrustedParamsCopies)) {
    request->trusted_params = network::ResourceRequest::TrustedParams();
    url::Origin origin = url::Origin::Create(back_url);
    request->trusted_params->isolation_info = net::IsolationInfo::Create(
        net::IsolationInfo::RequestType::kMainFrame, origin, origin,
        net::SiteForCookies::FromOrigin(origin));
    request->site_for_cookies =
        request->trusted_params->isolation_info.site_for_cookies();
  } else {
    url::Origin origin = url::Origin::Create(back_url);
    net::IsolationInfo isolation_info = net::IsolationInfo::Create(
        net::IsolationInfo::RequestType::kMainFrame, origin, origin,
        net::SiteForCookies::FromOrigin(origin));
    network::ResourceRequest::TrustedParams trusted_params;
    trusted_params.isolation_info = isolation_info;

    request->trusted_params = trusted_params;
    request->site_for_cookies =
        trusted_params.isolation_info.site_for_cookies();
  }
  request->credentials_mode = network::mojom::CredentialsMode::kOmit;
  request->skip_service_worker = true;
  request->do_not_prompt_for_login = true;

  CHECK(!request->SendsCookies());
  CHECK(!request->SavesCookies());
  constexpr net::NetworkTrafficAnnotationTag traffic_annotation =
      net::DefineNetworkTrafficAnnotation("back_navigation_cache_query",
                                          R"(
          semantics {
            sender: "Prerender"
            description:
              "This is not actually a network request. It is used internally by the browser to determine if the HTTP cache would be used if the user were to navigate back in session history. It only checks the cache and does not hit the network."
            trigger:
              "When the user performs an action that would suggest that they intend to navigate back soon. Examples include hovering the mouse over the back button and the start of a gestural back navigation."
            user_data {
              type: NONE
            }
            data: "None. The request doesn't hit the network."
            destination: LOCAL
            internal {
              contacts {
                email: "chrome-brapp-loading@chromium.org"
              }
            }
            last_reviewed: "2023-03-24"
          }
          policy {
            cookies_allowed: NO
            setting:
              "This is not controlled by a setting."
            policy_exception_justification: "This is not a network request."
        })");

  return network::SimpleURLLoader::Create(std::move(request),
                                          traffic_annotation);
}

// Returns true if the given navigation is meant to be predicted by a predictor
// related to session history (e.g. hovering over the back button could have
// predicted the navigation).
bool IsNavigationInSessionHistoryPredictorDomain(NavigationHandle* handle) {
  CHECK(handle->IsInPrimaryMainFrame());
  CHECK(!handle->IsSameDocument());

  if (handle->IsRendererInitiated()) {
    return false;
  }

  // Note that currently the only predictors are for back navigations of a
  // single step, however we still include all session history navigations in
  // the domain. The preloading of back navigations could generalize to session
  // history navigations of other offsets, but we haven't explored this due to
  // the higher usage of the back button compared to the forward button or
  // history menu.
  if (!(handle->GetPageTransition() & ui::PAGE_TRANSITION_FORWARD_BACK)) {
    return false;
  }

  if (handle->IsPost()) {
    return false;
  }

  if (handle->IsServedFromBackForwardCache()) {
    return false;
  }

  if (!handle->GetURL().SchemeIsHTTPOrHTTPS()) {
    return false;
  }

  // Note that even though the current predictors do not handle session history
  // navigations that are same-site or which don't use the HTTP cache, they are
  // still included in the domain.
  return true;
}

PreloadingEligibility ToEligibility(PrerenderFinalStatus status) {
  switch (status) {
    case PrerenderFinalStatus::kActivated:
    case PrerenderFinalStatus::kDestroyed:
      NOTREACHED();
    case PrerenderFinalStatus::kLowEndDevice:
      return PreloadingEligibility::kLowMemory;
    case PrerenderFinalStatus::kInvalidSchemeRedirect:
      NOTREACHED();
    case PrerenderFinalStatus::kInvalidSchemeNavigation:
      return PreloadingEligibility::kHttpOrHttpsOnly;
    case PrerenderFinalStatus::kNavigationRequestBlockedByCsp:
    case PrerenderFinalStatus::kMojoBinderPolicy:
    case PrerenderFinalStatus::kRendererProcessCrashed:
    case PrerenderFinalStatus::kRendererProcessKilled:
    case PrerenderFinalStatus::kDownload:
    case PrerenderFinalStatus::kTriggerDestroyed:
    case PrerenderFinalStatus::kNavigationNotCommitted:
    case PrerenderFinalStatus::kNavigationBadHttpStatus:
    case PrerenderFinalStatus::kClientCertRequested:
    case PrerenderFinalStatus::kNavigationRequestNetworkError:
    case PrerenderFinalStatus::kCancelAllHostsForTesting:
    case PrerenderFinalStatus::kDidFailLoad:
    case PrerenderFinalStatus::kStop:
    case PrerenderFinalStatus::kSslCertificateError:
    case PrerenderFinalStatus::kLoginAuthRequested:
    case PrerenderFinalStatus::kUaChangeRequiresReload:
    case PrerenderFinalStatus::kBlockedByClient:
    case PrerenderFinalStatus::kMixedContent:
    case PrerenderFinalStatus::kCrossDocumentRestart:
      NOTREACHED();
    case PrerenderFinalStatus::kTriggerBackgrounded:
      return PreloadingEligibility::kHidden;
    case PrerenderFinalStatus::kMemoryLimitExceeded:
      NOTREACHED();
    case PrerenderFinalStatus::kDataSaverEnabled:
      return PreloadingEligibility::kDataSaverEnabled;
    case PrerenderFinalStatus::kTriggerUrlHasEffectiveUrl:
      return PreloadingEligibility::kHasEffectiveUrl;
    case PrerenderFinalStatus::kActivatedBeforeStarted:
    case PrerenderFinalStatus::kInactivePageRestriction:
    case PrerenderFinalStatus::kStartFailed:
    case PrerenderFinalStatus::kTimeoutBackgrounded:
    case PrerenderFinalStatus::kCrossSiteRedirectInInitialNavigation:
      NOTREACHED();
    case PrerenderFinalStatus::kCrossSiteNavigationInInitialNavigation:
      return PreloadingEligibility::kCrossOrigin;
    case PrerenderFinalStatus::
        kSameSiteCrossOriginRedirectNotOptInInInitialNavigation:
    case PrerenderFinalStatus::
        kSameSiteCrossOriginNavigationNotOptInInInitialNavigation:
    case PrerenderFinalStatus::kActivationNavigationParameterMismatch:
    case PrerenderFinalStatus::kActivatedInBackground:
    case PrerenderFinalStatus::kActivationNavigationDestroyedBeforeSuccess:
    case PrerenderFinalStatus::kTabClosedByUserGesture:
    case PrerenderFinalStatus::kTabClosedWithoutUserGesture:
    case PrerenderFinalStatus::kPrimaryMainFrameRendererProcessCrashed:
    case PrerenderFinalStatus::kPrimaryMainFrameRendererProcessKilled:
    case PrerenderFinalStatus::kActivationFramePolicyNotCompatible:
      NOTREACHED();
    case PrerenderFinalStatus::kPreloadingDisabled:
      return PreloadingEligibility::kPreloadingDisabled;
    case PrerenderFinalStatus::kBatterySaverEnabled:
      return PreloadingEligibility::kBatterySaverEnabled;
    case PrerenderFinalStatus::kActivatedDuringMainFrameNavigation:
      NOTREACHED();
    case PrerenderFinalStatus::kPreloadingUnsupportedByWebContents:
      return PreloadingEligibility::kPreloadingUnsupportedByWebContents;
    case PrerenderFinalStatus::kCrossSiteRedirectInMainFrameNavigation:
    case PrerenderFinalStatus::kCrossSiteNavigationInMainFrameNavigation:
    case PrerenderFinalStatus::
        kSameSiteCrossOriginRedirectNotOptInInMainFrameNavigation:
    case PrerenderFinalStatus::
        kSameSiteCrossOriginNavigationNotOptInInMainFrameNavigation:
      NOTREACHED();
    case PrerenderFinalStatus::kMemoryPressureOnTrigger:
      return PreloadingEligibility::kMemoryPressure;
    case PrerenderFinalStatus::kMemoryPressureAfterTriggered:
      NOTREACHED();
    case PrerenderFinalStatus::kPrerenderingDisabledByDevTools:
      return PreloadingEligibility::kPreloadingDisabledByDevTools;
    case PrerenderFinalStatus::kSpeculationRuleRemoved:
    case PrerenderFinalStatus::kActivatedWithAuxiliaryBrowsingContexts:
    case PrerenderFinalStatus::kMaxNumOfRunningImmediatePrerendersExceeded:
    case PrerenderFinalStatus::kMaxNumOfRunningNonImmediatePrerendersExceeded:
    case PrerenderFinalStatus::kMaxNumOfRunningEmbedderPrerendersExceeded:
      NOTREACHED();
    case PrerenderFinalStatus::kPrerenderingUrlHasEffectiveUrl:
    case PrerenderFinalStatus::kRedirectedPrerenderingUrlHasEffectiveUrl:
    case PrerenderFinalStatus::kActivationUrlHasEffectiveUrl:
      return PreloadingEligibility::kHasEffectiveUrl;
    case PrerenderFinalStatus::kJavaScriptInterfaceAdded:
    case PrerenderFinalStatus::kJavaScriptInterfaceRemoved:
    case PrerenderFinalStatus::kAllPrerenderingCanceled:
    case PrerenderFinalStatus::kWindowClosed:
    case PrerenderFinalStatus::kOtherPrerenderedPageActivated:
      NOTREACHED();
    case PrerenderFinalStatus::kPrerenderFailedDuringPrefetch:
    case PrerenderFinalStatus::kBrowsingDataRemoved:
      NOTREACHED();
    case PrerenderFinalStatus::kPrerenderHostReused:
    case PrerenderFinalStatus::kFormSubmitWhenPrerendering:
      NOTREACHED();
  }

  NOTREACHED();
}

template <class ContainerType>
void DestructPrerenderHosts(ContainerType& hosts) {
  // Swap the container and let it scope out instead of directly destructing the
  // hosts in the container, for example, by `hosts.clear()`. This avoids
  // potential cases where a host being deleted indirectly modifies the
  // container while the container is being cleared up.
  // See https://crbug.com/40263658 for contexts.
  ContainerType temp;
  hosts.swap(temp);
}

// Represents a contract and ensures that the given prerender attempt is started
// as a PrerenderHost or rejected with a reason. It is allowed to use it only in
// PrerenderHostRegistry::CreateAndStartHost.
//
// TODO(kenoss): Add emits of Preload.prerenderStatusUpdated.
class PrerenderHostBuilder {
 public:
  explicit PrerenderHostBuilder(PreloadingAttempt* attempt);
  ~PrerenderHostBuilder();

  PrerenderHostBuilder(const PrerenderHostBuilder&) = delete;
  PrerenderHostBuilder& operator=(const PrerenderHostBuilder&) = delete;
  PrerenderHostBuilder(PrerenderHostBuilder&&) = delete;
  PrerenderHostBuilder& operator=(PrerenderHostBuilder&&) = delete;

  // The following methods consumes this class.
  std::unique_ptr<PrerenderHost> Build(
      std::unique_ptr<PrerenderHost> reuse_host,
      const PrerenderAttributes& attributes,
      WebContentsImpl& prerender_web_contents);
  void RejectAsNotEligible(const PrerenderAttributes& attributes,
                           PrerenderFinalStatus status);
  void RejectAsDuplicate();
  void RejectAsFailure(const PrerenderAttributes& attributes,
                       PrerenderFinalStatus status);
  void RejectDueToHoldback();

  void SetHoldbackOverride(PreloadingHoldbackStatus status);
  bool CheckIfShouldHoldback();

  // Public only for exceptional case.
  // TODO(crbug.com/40904828): Make this private again.
  void Drop();

 private:
  bool IsDropped() const;

  // Use raw pointer as PrerenderHostBuilder is alive only during
  // PrerenderHostRegistry::CreateAndStartHost(), and PreloadingAttempt should
  // outlive the function.
  raw_ptr<PreloadingAttempt> attempt_;
  std::unique_ptr<DevToolsPrerenderAttempt> devtools_attempt_;
};

PrerenderHostBuilder::PrerenderHostBuilder(PreloadingAttempt* attempt)
    : attempt_(attempt),
      devtools_attempt_(std::make_unique<DevToolsPrerenderAttempt>()) {}

PrerenderHostBuilder::~PrerenderHostBuilder() {
  CHECK(IsDropped());
}

void PrerenderHostBuilder::Drop() {
  attempt_ = nullptr;
  devtools_attempt_.reset();
}

bool PrerenderHostBuilder::IsDropped() const {
  return devtools_attempt_ == nullptr;
}

std::unique_ptr<PrerenderHost> PrerenderHostBuilder::Build(
    std::unique_ptr<PrerenderHost> reuse_host,
    const PrerenderAttributes& attributes,
    WebContentsImpl& prerender_web_contents) {
  CHECK(!IsDropped());
  std::unique_ptr<PrerenderHost> prerender_host;

  prerender_host = std::make_unique<PrerenderHost>(
      std::move(reuse_host), attributes, prerender_web_contents,
      attempt_ ? attempt_->GetWeakPtr() : nullptr,
      std::move(devtools_attempt_));
  Drop();

  return prerender_host;
}

void PrerenderHostBuilder::RejectAsNotEligible(
    const PrerenderAttributes& attributes,
    PrerenderFinalStatus status) {
  CHECK(!IsDropped());

  if (attempt_) {
    attempt_->SetEligibility(ToEligibility(status));
  }

  devtools_attempt_->SetFailureReason(attributes, status);

  RecordFailedPrerenderFinalStatus(PrerenderCancellationReason(status),
                                   attributes);

  Drop();
}

bool PrerenderHostBuilder::CheckIfShouldHoldback() {
  CHECK(!IsDropped());

  // Assigns the holdback status in the attempt it was not overridden earlier.
  return attempt_ && attempt_->ShouldHoldback();
}

void PrerenderHostBuilder::RejectDueToHoldback() {
  CHECK(!IsDropped());

  // If DevTools is opened, holdbacks are force-disabled. So, we don't need to
  // report this case to DevTools.

  Drop();
}

void PrerenderHostBuilder::RejectAsDuplicate() {
  CHECK(!IsDropped());

  if (attempt_) {
    attempt_->SetTriggeringOutcome(PreloadingTriggeringOutcome::kDuplicate);
  }

  // No need to report DevTools nor UMA; just removing duplicates.

  Drop();
}

void PrerenderHostBuilder::SetHoldbackOverride(
    PreloadingHoldbackStatus status) {
  if (!attempt_) {
    return;
  }
  attempt_->SetHoldbackStatus(status);
}

void PrerenderHostBuilder::RejectAsFailure(
    const PrerenderAttributes& attributes,
    PrerenderFinalStatus status) {
  CHECK(!IsDropped());

  if (attempt_) {
    attempt_->SetFailureReason(ToPreloadingFailureReason(status));
  }

  devtools_attempt_->SetFailureReason(attributes, status);

  RecordFailedPrerenderFinalStatus(PrerenderCancellationReason(status),
                                   attributes);

  Drop();
}

const base::FeatureParam<bool> kPrerenderScaleImmediate{
    &base::kStatefulMemoryPressure, "PrerenderScaleImmediate", true};

const base::FeatureParam<bool> kPrerenderScaleNonImmediate{
    &base::kStatefulMemoryPressure, "PrerenderScaleNonImmediate", true};

const base::FeatureParam<bool> kPrerenderScaleEmbedder{
    &base::kStatefulMemoryPressure, "PrerenderScaleEmbedder", false};

}  // namespace

PrerenderHostRegistry::PrerenderHostRegistry(WebContents& web_contents) {
  if (base::FeatureList::IsEnabled(
          blink::features::kPrerender2MemoryControls)) {
    memory_consumer_registration_.emplace(
        "PrerenderHostRegistry", kPrerenderHostRegistryTraits, this,
        base::MemoryConsumerRegistration::CheckUnregister::kDisabled);
  }
  Observe(&web_contents);
}

PrerenderHostRegistry::~PrerenderHostRegistry() {
  // This function is called by WebContentsImpl's dtor, so web_contents() should
  // not be a null ptr at this moment.
  CHECK(web_contents());

  PrerenderFinalStatus final_status =
      web_contents()->GetClosedByUserGesture()
          ? PrerenderFinalStatus::kTabClosedByUserGesture
          : PrerenderFinalStatus::kTabClosedWithoutUserGesture;

  // Here we have to delete the prerender hosts synchronously, to ensure the
  // FrameTrees would not access the WebContents.
  CancelAllHosts(final_status);
  DestructPrerenderHosts(to_be_deleted_hosts_);
  DestructPrerenderHosts(pending_deletion_hosts_);

  Observe(nullptr);
  for (Observer& obs : observers_) {
    obs.OnRegistryDestroyed();
  }
}

void PrerenderHostRegistry::AddObserver(Observer* observer) {
  observers_.AddObserver(observer);
}

void PrerenderHostRegistry::RemoveObserver(Observer* observer) {
  observers_.RemoveObserver(observer);
}

PrerenderHostId PrerenderHostRegistry::CreateAndStartHost(
    const PrerenderAttributes& attributes,
    PreloadingAttempt* attempt) {
  std::string recorded_url =
      attributes.initiator_origin.has_value()
          ? attributes.initiator_origin.value().GetURL().spec()
          : "(empty_url)";

  TRACE_EVENT("navigation", "PrerenderHostRegistry::CreateAndStartHost",
              "attributes", attributes, "initiator_origin", recorded_url);

  // The initiator WebContents can be different from the WebContents that will
  // host a prerendered page only when the prerender-in-new-tab runs.
  CHECK(attributes.initiator_web_contents);
  auto& initiator_web_contents =
      static_cast<WebContentsImpl&>(*attributes.initiator_web_contents);
  auto& prerender_web_contents = static_cast<WebContentsImpl&>(*web_contents());

  PrerenderHostId prerender_host_id;

  std::optional<blink::mojom::SpeculationEagerness> eagerness =
      attributes.GetEagerness();

  {
    RenderFrameHostImpl* initiator_rfh =
        attributes.IsBrowserInitiated()
            ? nullptr
            : RenderFrameHostImpl::FromFrameToken(
                  attributes.initiator_process_id,
                  attributes.initiator_frame_token.value());

    // Ensure observers are notified that a trigger occurred.
    absl::Cleanup notify_trigger = [this, &attributes] {
      NotifyTrigger(attributes.prerendering_url);
    };

    auto builder = PrerenderHostBuilder(attempt);

    // We don't know the root cause, but there is a case this is null.
    //
    // TODO(crbug.com/40904828): Continue investigation and fix the root
    // cause.
    if (initiator_web_contents.GetDelegate() == nullptr) {
      // Note that return without consuming `builder` is exceptional.
      builder.Drop();
      return PrerenderHostId();
    }

    // Check the about://flags toggle.
    if (!base::FeatureList::IsEnabled(blink::features::kPrerender2)) {
      builder.RejectAsNotEligible(attributes,
                                  PrerenderFinalStatus::kPreloadingDisabled);
      return PrerenderHostId();
    }

    // Check whether preloading is enabled. If it is not enabled, report the
    // reason.
    switch (initiator_web_contents.GetDelegate()->IsPrerender2Supported(
        initiator_web_contents, attributes.trigger_type)) {
      case PreloadingEligibility::kEligible:
        // nop
        break;
      case PreloadingEligibility::kPreloadingDisabled:
        builder.RejectAsNotEligible(attributes,
                                    PrerenderFinalStatus::kPreloadingDisabled);
        return PrerenderHostId();
      case PreloadingEligibility::kDataSaverEnabled:
        builder.RejectAsNotEligible(attributes,
                                    PrerenderFinalStatus::kDataSaverEnabled);
        return PrerenderHostId();
      case PreloadingEligibility::kBatterySaverEnabled:
        builder.RejectAsNotEligible(attributes,
                                    PrerenderFinalStatus::kBatterySaverEnabled);
        return PrerenderHostId();
      case PreloadingEligibility::kPreloadingUnsupportedByWebContents:
        builder.RejectAsNotEligible(
            attributes,
            PrerenderFinalStatus::kPreloadingUnsupportedByWebContents);
        return PrerenderHostId();
      default:
        NOTREACHED();
    }

    // Don't prerender when the initiator is in the background and its type is
    // `kEmbedder`, as current implementation doesn't use `pending_prerenders_`
    // when kEmbedder.
    // If the trigger type is speculation rules, nothing should be done here and
    // then prerender host will be created and its id will be enqueued to
    // `pending_prerenders_`. The visibility of the initiator will be considered
    // when trying to pop from `pending_prerenders_` on `StartPrerendering()`.
    if (attributes.trigger_type == PreloadingTriggerType::kEmbedder &&
        initiator_web_contents.GetVisibility() == Visibility::HIDDEN) {
      builder.RejectAsNotEligible(attributes,
                                  PrerenderFinalStatus::kTriggerBackgrounded);
      return PrerenderHostId();
    }

    // Don't prerender on low-end devices.
    if (!DeviceHasEnoughMemoryForPrerender()) {
      builder.RejectAsNotEligible(attributes,
                                  PrerenderFinalStatus::kLowEndDevice);
      return PrerenderHostId();
    }

    // Don't prerender under critical memory pressure.
    if (GetCurrentMemoryLimit() <= base::kCriticalMemoryPressureThreshold) {
      builder.RejectAsNotEligible(
          attributes, PrerenderFinalStatus::kMemoryPressureOnTrigger);
      return PrerenderHostId();
    }

    // Allow prerendering only for same-site. The initiator origin is nullopt
    // when prerendering is initiated by the browser (not by a renderer using
    // Speculation Rules API). In that case, skip this same-site check.
    // TODO(crbug.com/40168192): Support cross-site prerendering.
    if (!attributes.IsBrowserInitiated() &&
        !prerender_navigation_utils::IsSameSite(
            attributes.prerendering_url, attributes.initiator_origin.value())) {
      builder.RejectAsNotEligible(
          attributes,
          PrerenderFinalStatus::kCrossSiteNavigationInInitialNavigation);
      return PrerenderHostId();
    }

    // Allow prerendering only HTTP(S) scheme URLs. For redirection, this will
    // be checked in PrerenderNavigationThrottle::WillStartOrRedirectRequest().
    if (!attributes.prerendering_url.SchemeIsHTTPOrHTTPS()) {
      builder.RejectAsNotEligible(
          attributes, PrerenderFinalStatus::kInvalidSchemeNavigation);
      return PrerenderHostId();
    }

    // Disallow all pages that have an effective URL like hosted apps and NTP.
    auto* browser_context = prerender_web_contents.GetBrowserContext();
    if (SiteInstanceImpl::HasEffectiveURL(browser_context,
                                          initiator_web_contents.GetURL())) {
      builder.RejectAsNotEligible(
          attributes, PrerenderFinalStatus::kTriggerUrlHasEffectiveUrl);
      return PrerenderHostId();
    }
    if (SiteInstanceImpl::HasEffectiveURL(browser_context,
                                          attributes.prerendering_url)) {
      builder.RejectAsNotEligible(
          attributes, PrerenderFinalStatus::kPrerenderingUrlHasEffectiveUrl);
      return PrerenderHostId();
    }

    if (initiator_rfh && initiator_rfh->frame_tree() &&
        !devtools_instrumentation::IsPrerenderAllowed(
            *initiator_rfh->frame_tree())) {
      builder.RejectAsNotEligible(
          attributes, PrerenderFinalStatus::kPrerenderingDisabledByDevTools);
      return PrerenderHostId();
    }

    // Once all eligibility checks are completed, set the status to kEligible.
    if (attempt) {
      attempt->SetEligibility(PreloadingEligibility::kEligible);
    }

    // Normally CheckIfShouldHoldback() computes the holdback status based on
    // PreloadingConfig. In special cases, we call SetHoldbackOverride() to
    // override that processing.
    bool has_devtools_open =
        initiator_rfh &&
        RenderFrameDevToolsAgentHost::GetFor(initiator_rfh) != nullptr;

    if (has_devtools_open) {
      // Never holdback when DevTools is opened, to avoid web developer
      // frustration.
      builder.SetHoldbackOverride(PreloadingHoldbackStatus::kAllowed);
    } else if (attributes.holdback_status_override !=
               PreloadingHoldbackStatus::kUnspecified) {
      // The caller (e.g. from chrome/) is allowed to specify a holdback that
      // overrides the default logic.
      builder.SetHoldbackOverride(attributes.holdback_status_override);
    }

    // Check if the attempt is held back either due to the check above or via
    // PreloadingConfig.
    if (builder.CheckIfShouldHoldback()) {
      builder.RejectDueToHoldback();
      return PrerenderHostId();
    }

    // Ignore prerendering requests that duplicate an existing host. Two
    // requests are considered duplicates when they target the same URL, or
    // when they share the same No-Vary-Search hint and their URLs are
    // equivalent under that hint (e.g. /p?a=1 and /p?a=2 with hint
    // `params=("a")`).
    for (auto& iter : prerender_host_by_id_) {
      const PrerenderHost& existing_host = *iter.second;
      const GURL& existing_url = existing_host.GetInitialUrl();
      if (existing_url == attributes.prerendering_url) {
        builder.RejectAsDuplicate();
        return PrerenderHostId();
      }
      if (attributes.no_vary_search_hint.has_value() &&
          existing_host.no_vary_search_hint() ==
              attributes.no_vary_search_hint &&
          attributes.no_vary_search_hint->AreEquivalent(
              existing_url, attributes.prerendering_url)) {
        builder.RejectAsDuplicate();
        return PrerenderHostId();
      }
    }

    // Since IsAllowedToStartPrerenderingForTrigger will check
    // the number of the active PrerenderHosts triggered by the embedder, we
    // need to tentatively move the reuse host out of the map first
    // so that the count can be correctly calculated.
    // The reuse_host is not yet deleted at this point and can be added back
    // if the check failes.
    std::unique_ptr<PrerenderHost> reuse_host;
    if (base::FeatureList::IsEnabled(features::kPrerender2ReuseHost)) {
      reuse_host = FindAndTakePrerenderHostToReuse(attributes);
    }

    // CreateAndStartHost can be called in the newly created WebContents's
    // PrerenderHostRegistry for new tab triggers, rather than in initiator
    // WebContents's registry, while it is called in initiator ones for normal
    // triggers. In either case, we want to control the limit based on the
    // initiator WebContents.
    //
    // TODO(crbug.com/40235847): Enqueue the request exceeding the number limit
    // until the forerunners are cancelled, and suspend starting a new prerender
    // when the number reaches the limit.
    if (!initiator_web_contents.GetPrerenderHostRegistry()
             ->IsAllowedToStartPrerenderingForTrigger(attributes.trigger_type,
                                                      eagerness)) {
      // The reason we don't consider limit exceeded as an ineligibility
      // reason is because we can't replicate the behavior in our other
      // experiment groups for analysis. To prevent this we set
      // TriggeringOutcome to kFailure and look into the failure reason to
      // learn more.
      PrerenderFinalStatus final_status;
      switch (GetPrerenderLimitGroup(attributes.trigger_type, eagerness)) {
        case PrerenderLimitGroup::kSpeculationRulesImmediate:
          final_status =
              PrerenderFinalStatus::kMaxNumOfRunningImmediatePrerendersExceeded;
          break;
        case PrerenderLimitGroup::kSpeculationRulesNonImmediate:
          final_status = PrerenderFinalStatus::
              kMaxNumOfRunningNonImmediatePrerendersExceeded;
          break;
        case PrerenderLimitGroup::kEmbedder:
          final_status =
              PrerenderFinalStatus::kMaxNumOfRunningEmbedderPrerendersExceeded;
          break;
      }
      builder.RejectAsFailure(attributes, final_status);
      // If we cannot start a new prerender, we should release the reuse host
      // back to the pool.
      if (reuse_host) {
        PrerenderHostId reuse_id = reuse_host->prerender_host_id();
        const PrerenderLimitGroup reuse_group = GetPrerenderLimitGroup(
            reuse_host->trigger_type(), reuse_host->eagerness());
        prerender_host_by_id_[reuse_id] = std::move(reuse_host);
        arrival_order_queue_by_limit_group_[std::to_underlying(reuse_group)]
            .push_front(reuse_id);
      }
      return PrerenderHostId();
    }

    // If we find a reusable prerender host under the same site. We will
    // take over its frame tree and initiate a new navigation to the new
    // prerender URL.
    if (!reuse_host) {
      base::UmaHistogramCounts100(
          "Prerender.Experimental.ReusePrerenderHost.PrerenderHostCount.Failed",
          prerender_host_by_id_.size());
    }
    base::UmaHistogramBoolean("Prerender.Experimental.FoundReusePrerenderHost",
                              reuse_host != nullptr);
    std::unique_ptr<PrerenderHost> prerender_host = builder.Build(
        std::move(reuse_host), attributes, prerender_web_contents);
    prerender_host_id = prerender_host->prerender_host_id();

    CHECK(!prerender_host_by_id_.contains(prerender_host_id));
    prerender_host_by_id_[prerender_host_id] = std::move(prerender_host);

    const PrerenderLimitGroup limit_group =
        GetPrerenderLimitGroup(attributes.trigger_type, eagerness);
    arrival_order_queue_by_limit_group_[std::to_underlying(limit_group)]
        .push_back(prerender_host_id);
  }

  // Now start prerender the new page. If the PrerenderHost is reusing a frame
  // tree, the previous page will be unloaded after initiating a new navigation.
  switch (attributes.trigger_type) {
    case PreloadingTriggerType::kSpeculationRule:
    case PreloadingTriggerType::kSpeculationRuleFromIsolatedWorld:
    case PreloadingTriggerType::kSpeculationRuleFromAutoSpeculationRules:
      pending_prerenders_.push_back(prerender_host_id);
      if (running_prerender_host_id_.is_null()) {
        // Start the initial prerendering navigation of the pending request in
        // the head of the queue if there's no running prerender and the
        // initiator is in the foreground. If the initiator page is in the
        // background, `StartPrerendering` will return a corresponding
        // PrerenderHostId if allowed by
        // `PrerenderCanBeStartedWhenInitiatorIsInBackground`.
        if (IsBackground(initiator_web_contents.GetVisibility()) &&
            !initiator_web_contents.GetPrerenderHostRegistry()
                 ->PrerenderCanBeStartedWhenInitiatorIsInBackground()) {
          // Cancel if it is prerender-into-new-tab.
          // TODO(crbug.com/350785853): Add queue
          // mechanism and update test expectation.
          if (web_contents() != &initiator_web_contents) {
            return PrerenderHostId();
          }
          break;
        }
        const PrerenderHostId started_prerender_host_id =
            StartPrerendering(PrerenderHostId());
        CHECK(started_prerender_host_id == prerender_host_id ||
              started_prerender_host_id.is_null());
        prerender_host_id = started_prerender_host_id;
      }
      break;
    case PreloadingTriggerType::kEmbedder:
      // The prerendering request from embedder should have high-priority
      // because embedder prediction is more likely for the user to visit. Hold
      // the return value of `StartPrerendering` because the requested prerender
      // might be cancelled due to some restrictions and a null FrameTreeNodeId
      // should be returned in that case.
      const PrerenderHostId started_prerender_host_id =
          StartPrerendering(prerender_host_id);
      prerender_host_id = started_prerender_host_id;
      break;
  }

  auto it = prerender_host_by_id_.find(prerender_host_id);
  if (it == prerender_host_by_id_.end()) {
    return PrerenderHostId();
  }
  return it->second->prerender_host_id();
}

PrerenderHostId PrerenderHostRegistry::CreateAndStartHostForNewTab(
    const PrerenderAttributes& attributes,
    const PreloadingPredictor& creating_predictor,
    const PreloadingPredictor& enacting_predictor,
    PreloadingConfidence confidence) {
  CHECK(IsSpeculationRuleType(attributes.trigger_type));
  std::string recorded_url =
      attributes.initiator_origin.has_value()
          ? attributes.initiator_origin.value().GetURL().spec()
          : "(empty_url)";
  TRACE_EVENT("navigation",
              "PrerenderHostRegistry::CreateAndStartHostForNewTab",
              "attributes", attributes, "initiator_origin", recorded_url);

  auto handle = std::make_unique<PrerenderNewTabHandle>(
      attributes, *web_contents()->GetBrowserContext());
  PrerenderHostId prerender_host_id = handle->StartPrerendering(
      creating_predictor, enacting_predictor, confidence);
  if (!prerender_host_id) {
    return PrerenderHostId();
  }
  prerender_new_tab_handle_by_id_[prerender_host_id] = std::move(handle);

  const PrerenderLimitGroup limit_group = GetPrerenderLimitGroup(
      attributes.trigger_type, attributes.GetEagerness());
  arrival_order_queue_by_limit_group_[std::to_underlying(limit_group)]
      .push_back(prerender_host_id);
  return prerender_host_id;
}

PrerenderHostId PrerenderHostRegistry::StartPrerendering(
    PrerenderHostId prerender_host_id) {
  if (is_starting_prerendering_) {
    return PrerenderHostId();
  }
  base::AutoReset<bool> auto_reset(&is_starting_prerendering_, true);

  // TODO(crbug.com/40260412): Don't start prerendering if the current
  // memory pressure level is critical, and then retry prerendering when the
  // memory pressure level goes down.
  if (prerender_host_id.is_null()) {
    CHECK(running_prerender_host_id_.is_null());

    while (!pending_prerenders_.empty()) {
      PrerenderHostId host_id = pending_prerenders_.front();

      // Skip a cancelled request.
      auto found = prerender_host_by_id_.find(host_id);
      if (found == prerender_host_by_id_.end()) {
        // Remove the cancelled request from the pending queue.
        pending_prerenders_.pop_front();
        continue;
      }
      PrerenderHost* prerender_host = found->second.get();

      // The initiator WebContents should be alive as it cancels all the
      // prerendering requests during destruction.
      CHECK(prerender_host->initiator_web_contents());

      WebContentsImpl* initiator_web_contents = static_cast<WebContentsImpl*>(
          prerender_host->initiator_web_contents().get());
      if (IsBackground(initiator_web_contents->GetVisibility())) {
        // The pending prerender triggered by the background tab will be started
        // according to the conditions in
        // `PrerenderCanBeStartedWhenInitiatorIsInBackground`.
        if (!initiator_web_contents->GetPrerenderHostRegistry()
                 ->PrerenderCanBeStartedWhenInitiatorIsInBackground()) {
          return PrerenderHostId();
        }
      }

      // Found the request to run.
      pending_prerenders_.pop_front();
      prerender_host_id = host_id;
      break;
    }

    if (prerender_host_id.is_null()) {
      return PrerenderHostId();
    }
  }

  auto prerender_host_it = prerender_host_by_id_.find(prerender_host_id);
  CHECK(prerender_host_it != prerender_host_by_id_.end());
  PrerenderHost& prerender_host = *prerender_host_it->second;
  devtools_instrumentation::WillInitiatePrerender(
      prerender_host.GetPrerenderFrameTree());
  if (!prerender_host.StartPrerendering()) {
    CancelHost(prerender_host.prerender_host_id(),
               PrerenderFinalStatus::kStartFailed);
    return PrerenderHostId();
  }

  switch (prerender_host.trigger_type()) {
    case PreloadingTriggerType::kSpeculationRule:
    case PreloadingTriggerType::kSpeculationRuleFromIsolatedWorld:
    case PreloadingTriggerType::kSpeculationRuleFromAutoSpeculationRules:
      // Update the `running_prerender_host_id` to the starting prerender's id.
      running_prerender_host_id_ = prerender_host_id;
      break;
    case PreloadingTriggerType::kEmbedder:
      // `running_prerender_host_id` only tracks the id for speculation rules
      // trigger, so we also don't update it in the case of embedder.
      break;
  }

  RecordPrerenderTriggered(prerender_host.initiator_ukm_id());
  return prerender_host.prerender_host_id();
}

std::set<PrerenderHostId> PrerenderHostRegistry::CancelHosts(
    const std::vector<PrerenderHostId>& prerender_host_ids,
    const PrerenderCancellationReason& reason) {
  TRACE_EVENT("navigation", "PrerenderHostRegistry::CancelHosts",
              "prerender_host_ids", prerender_host_ids);

  // Cancel must not be requested during activation.
  CHECK(!reserved_prerender_host_);

  std::set<PrerenderHostId> cancelled_ids;

  for (PrerenderHostId host_id : prerender_host_ids) {
    if (CancelHostInternal(host_id, reason) ||
        CancelNewTabHostInternal(host_id, reason)) {
      cancelled_ids.insert(host_id);
    }
  }

  // Start another prerender if the running prerender is cancelled.
  if (running_prerender_host_id_.is_null()) {
    StartPrerendering(PrerenderHostId());
  }

  return cancelled_ids;
}

bool PrerenderHostRegistry::CancelHost(PrerenderHostId prerender_host_id,
                                       PrerenderFinalStatus final_status) {
  return CancelHost(prerender_host_id,
                    PrerenderCancellationReason(final_status));
}

bool PrerenderHostRegistry::CancelHost(
    PrerenderHostId prerender_host_id,
    const PrerenderCancellationReason& reason) {
  TRACE_EVENT("navigation", "PrerenderHostRegistry::CancelHost",
              "prerender_host_id", prerender_host_id);
  std::set<PrerenderHostId> cancelled_ids =
      CancelHosts({prerender_host_id}, reason);
  return !cancelled_ids.empty();
}

void PrerenderHostRegistry::CancelHostsForTriggers(
    std::vector<PreloadingTriggerType> trigger_types,
    const PrerenderCancellationReason& reason) {
  TRACE_EVENT("navigation", "PrerenderHostRegistry::CancelHostsForTrigger",
              "trigger_type", trigger_types[0]);

  std::vector<PrerenderHostId> ids_to_be_deleted;

  for (auto& iter : prerender_host_by_id_) {
    if (std::ranges::contains(trigger_types, iter.second->trigger_type())) {
      ids_to_be_deleted.push_back(iter.first);
    }
  }
  for (auto& iter : prerender_new_tab_handle_by_id_) {
    if (std::ranges::contains(trigger_types, iter.second->trigger_type())) {
      // Prerendering into a new tab can be triggered by speculation rules only.
      CHECK(IsSpeculationRuleType(iter.second->trigger_type()));
      ids_to_be_deleted.push_back(iter.first);
    }
  }

  CancelHosts(ids_to_be_deleted, reason);
}

void PrerenderHostRegistry::CancelAllHosts(PrerenderFinalStatus final_status) {
  // Cancel must not be requested during activation.
  CHECK(!reserved_prerender_host_);

  PrerenderCancellationReason reason(final_status);

  while (!prerender_host_by_id_.empty()) {
    CancelHostInternal(prerender_host_by_id_.begin()->first, reason);
  }

  while (!prerender_new_tab_handle_by_id_.empty()) {
    CancelNewTabHostInternal(prerender_new_tab_handle_by_id_.begin()->first,
                             reason);
  }

  pending_prerenders_.clear();
}

bool PrerenderHostRegistry::CancelHostInternal(
    PrerenderHostId prerender_host_id,
    const PrerenderCancellationReason& reason) {
  // Look up the id in the non-reserved host map.
  auto iter = prerender_host_by_id_.find(prerender_host_id);
  if (iter == prerender_host_by_id_.end()) {
    return false;
  }

  if (running_prerender_host_id_ == prerender_host_id) {
    running_prerender_host_id_ = PrerenderHostId();
  }

  // Remove the prerender host from the host map so that it's not used for
  // activation during asynchronous deletion.
  std::unique_ptr<PrerenderHost> prerender_host = std::move(iter->second);
  prerender_host_by_id_.erase(iter);
  RemoveFromArrivalOrderQueues(prerender_host_id);

  prerender_host->OnWillBeCancelled(reason);
  reason.ReportMetrics(prerender_host->GetHistogramSuffix());

  NotifyRetriggerable(prerender_host->prerender_host_id(), reason);

  // If the host we are attempting to cancel is the new-tab host and initiator
  // WebContents's PrerenderHostRegistry for this host is still alive, invoke
  // the initiator WebContents's CancelNewTabHostInternal to destroy
  // PrerenderNewTabHandle and WebContents that this new-tab host belongs to.
  // This will eventually destroy `this`, so it should be performed
  // asynchronously.
  WebContentsImpl* initiator_web_contents = static_cast<WebContentsImpl*>(
      prerender_host->initiator_web_contents().get());
  // The initiator WebContents may not be alive.
  // See crrev.com/c/6286546/comment/1adfe28c_4f769aa7 for more details.
  if (initiator_web_contents && web_contents() != initiator_web_contents &&
      !initiator_web_contents->IsBeingDestroyed()) {
    base::SequencedTaskRunner::GetCurrentDefault()->PostTask(
        FROM_HERE,
        base::BindOnce(
            base::IgnoreResult(
                &PrerenderHostRegistry::CancelNewTabHostInternal),
            initiator_web_contents->GetPrerenderHostRegistry()->GetWeakPtr(),
            prerender_host->prerender_host_id(),
            PrerenderCancellationReason(reason.final_status())));
  }

  // Asynchronously delete the prerender host.
  ScheduleToDeleteAbandonedHost(std::move(prerender_host), reason);
  return true;
}

bool PrerenderHostRegistry::CancelNewTabHostInternal(
    PrerenderHostId prerender_host_id,
    const PrerenderCancellationReason& reason) {
  // Look up the id in the prerender-in-new-tab handle map.
  auto iter = prerender_new_tab_handle_by_id_.find(prerender_host_id);
  if (iter == prerender_new_tab_handle_by_id_.end()) {
    return false;
  }

  // The host should be driven by PrerenderHostRegistry associated with
  // the new tab.
  CHECK_NE(running_prerender_host_id_, prerender_host_id);

  std::unique_ptr<PrerenderNewTabHandle> handle = std::move(iter->second);
  prerender_new_tab_handle_by_id_.erase(iter);
  RemoveFromArrivalOrderQueues(prerender_host_id);
  NotifyRetriggerable(handle->prerender_host_id(), reason);

  PrerenderNewTabHandle::CancelPrerenderingAndDestroy(std::move(handle),
                                                      reason);

  return true;
}

PrerenderHostId PrerenderHostRegistry::FindPotentialHostToActivate(
    NavigationRequest& navigation_request) {
  TRACE_EVENT(
      "navigation", "PrerenderHostRegistry::FindPotentialHostToActivate",
      "navigation_url", navigation_request.GetURL().spec(), "render_frame_host",
      navigation_request.frame_tree_node()->current_frame_host());

  // Disallow activation when the navigation is for a nested browsing context
  // (e.g., iframes, fenced frames). This is because nested browsing contexts
  // such as iframes are supposed to be created in the parent's browsing context
  // group and can script with the parent, but prerendered pages are created in
  // new browsing context groups.
  //
  // Also, disallow activation when the navigation happens in the prerendering
  // frame tree.
  if (!navigation_request.IsInPrimaryMainFrame()) {
    return PrerenderHostId();
  }

  // Collect hosts that can match the navigation request.
  std::vector<PrerenderHost*> matchable_hosts;
  // First, collect hosts that can exactly match or match with the
  // No-Vary-Search header.
  for (const auto& [host_id, host] : prerender_host_by_id_) {
    if (host->IsUrlMatch(navigation_request.GetURL())) {
      matchable_hosts.push_back(host.get());
    }
  }
  // Then, collect hosts that can match with the No-Vary-Search hint.
  for (const auto& [host_id, host] : prerender_host_by_id_) {
    if (host->IsNoVarySearchHintUrlMatch(navigation_request.GetURL())) {
      matchable_hosts.push_back(host.get());
    }
  }
  RecordPotentialPrerenderProcessReuse(!matchable_hosts.empty(),
                                       navigation_request.GetURL());
  if (matchable_hosts.empty()) {
    return PrerenderHostId();
  }
  // Use the first match. This prioritizes the exact match or No-Vary-Search
  // header match than No-Vary-Search hint match.
  PrerenderHost* host = *matchable_hosts.begin();

  base::UmaHistogramCounts100(
      "Prerender.Experimental.MatchableHostCountOnActivation",
      matchable_hosts.size());
  // Cannot activate if prerendering navigation has not started yet.
  if (!host->GetInitialNavigationId().has_value()) {
    CancelHost(host->prerender_host_id(),
               PrerenderFinalStatus::kActivatedBeforeStarted);
    return PrerenderHostId();
  }

  return CanNavigationActivateHost(navigation_request, *host)
             ? host->prerender_host_id()
             : PrerenderHostId();
}

std::optional<ReservedPrerenderHostInfo>
PrerenderHostRegistry::ReserveHostToActivate(
    NavigationRequest& navigation_request,
    PrerenderHostId expected_host_id) {
  RenderFrameHostImpl* render_frame_host =
      navigation_request.frame_tree_node()->current_frame_host();
  TRACE_EVENT("navigation", "PrerenderHostRegistry::ReserveHostToActivate",
              "navigation_url", navigation_request.GetURL().spec(),
              "render_frame_host", render_frame_host);

  CHECK(navigation_request.IsInPrimaryMainFrame());

  // Choose the host that NavigationRequest expects.
  //
  // Note that other prerendered pages may match this NavigationRequest but
  // we shouldn't activate them. NavigationRequest makes sure that the
  // expected prerendered page is ready for activation by waiting for
  // PrerenderCommitDeferringCondition before this point, while the new
  // matched pages may not be ready for activation yet.
  auto it = prerender_host_by_id_.find(expected_host_id);
  if (it == prerender_host_by_id_.end()) {
    return std::nullopt;
  }

  PrerenderHost& host_ref = *it->second;

  // The expected host does not match. This can happen when the host matches
  // based on the No-Vary-Search hint but actually it does not match based on
  // the No-Vary-Search header.
  std::optional<UrlMatchType> match_type =
      host_ref.IsUrlMatch(navigation_request.GetURL());
  if (!match_type.has_value()) {
    return std::nullopt;
  }

  if (!CanNavigationActivateHost(navigation_request, host_ref)) {
    return std::nullopt;
  }

  // Disallow activation when ongoing navigations exist. It can happen when the
  // main frame navigation starts after PrerenderCommitDeferringCondition posts
  // a task to resume activation and before the activation is completed.
  auto& prerender_frame_tree = host_ref.GetPrerenderFrameTree();
  if (prerender_frame_tree.root()->HasNavigation()) {
    CancelHost(expected_host_id,
               PrerenderFinalStatus::kActivatedDuringMainFrameNavigation);
    return std::nullopt;
  }

  // Remove the host from the map of non-reserved hosts.
  std::unique_ptr<PrerenderHost> host =
      std::move(prerender_host_by_id_[expected_host_id]);
  prerender_host_by_id_.erase(expected_host_id);
  RemoveFromArrivalOrderQueues(expected_host_id);
  CHECK(host->IsUrlMatch(navigation_request.GetURL()));

  if (match_type.value() == UrlMatchType::kNoVarySearch) {
    // Count use of No-Vary-Search header in prerender.
    GetContentClient()->browser()->LogWebFeatureForCurrentPage(
        web_contents()->GetPrimaryMainFrame(),
        blink::mojom::WebFeature::kNoVarySearchPrerender);
  }
  // Reserve the host for activation.
  CHECK(!reserved_prerender_host_);
  reserved_prerender_host_ = std::move(host);

  return ReservedPrerenderHostInfo(expected_host_id,
                                   reserved_prerender_host_->trigger_type(),
                                   reserved_prerender_host_->histogram_suffix(),
                                   reserved_prerender_host_->host_reused());
}

RenderFrameHostImpl* PrerenderHostRegistry::GetRenderFrameHostForReservedHost(
    PrerenderHostId prerender_host_id) {
  if (!reserved_prerender_host_) {
    return nullptr;
  }

  CHECK_EQ(prerender_host_id, reserved_prerender_host_->prerender_host_id());

  return reserved_prerender_host_->GetPrerenderedMainFrameHost();
}

std::unique_ptr<StoredPage> PrerenderHostRegistry::ActivateReservedHost(
    PrerenderHostId prerender_host_id,
    NavigationRequest& navigation_request) {
  CHECK(reserved_prerender_host_);
  CHECK_EQ(prerender_host_id, reserved_prerender_host_->prerender_host_id());

  std::unique_ptr<PrerenderHost> prerender_host =
      std::move(reserved_prerender_host_);
  return prerender_host->Activate(navigation_request);
}

void PrerenderHostRegistry::OnActivationFinished(
    PrerenderHostId prerender_host_id) {
  // OnActivationFinished() should not be called for non-reserved hosts.
  CHECK(!FindNonReservedHostById(prerender_host_id));

  if (!reserved_prerender_host_) {
    // The activation finished successfully and has already activated the
    // reserved host.
    return;
  }

  // The activation navigation is cancelled before activating the prerendered
  // page, which means the activation failed.
  CHECK_EQ(prerender_host_id, reserved_prerender_host_->prerender_host_id());

  // TODO(crbug.com/40243805): Monitor the final status metric and see
  // whether it could be possible.
  ScheduleToDeleteAbandonedHost(
      std::move(reserved_prerender_host_),
      PrerenderCancellationReason(
          PrerenderFinalStatus::kActivationNavigationDestroyedBeforeSuccess));
}

PrerenderHost* PrerenderHostRegistry::FindNonReservedHostById(
    PrerenderHostId prerender_host_id) {
  auto id_iter = prerender_host_by_id_.find(prerender_host_id);
  if (id_iter == prerender_host_by_id_.end()) {
    return nullptr;
  }
  return id_iter->second.get();
}

bool PrerenderHostRegistry::HasReservedHost() const {
  return !!reserved_prerender_host_;
}

std::unique_ptr<WebContentsImpl>
PrerenderHostRegistry::TakePreCreatedWebContentsForNewTabIfExists(
    const mojom::CreateNewWindowParams& create_new_window_params,
    const WebContents::CreateParams& web_contents_create_params) {
  // Don't serve a prerendered page if the window needs the opener or is created
  // for non-regular navigations.
  if (!create_new_window_params.opener_suppressed ||
      create_new_window_params.pip_options) {
    return nullptr;
  }

  for (auto& iter : prerender_new_tab_handle_by_id_) {
    // Skip those PrerenderHosts that are not for form submission if the window
    // is created by form submission.
    if (create_new_window_params.is_form_submission &&
        !iter.second->form_submission()) {
      continue;
    }
    std::unique_ptr<WebContentsImpl> web_contents =
        iter.second->TakeWebContentsIfAvailable(create_new_window_params,
                                                web_contents_create_params);
    if (web_contents) {
      // Notify observers that this prerender was consumed by activation so that
      // it can be re-triggered if needed.
      // See crbug.com/513412121 for more details.
      NotifyRetriggerable(
          iter.second->prerender_host_id(),
          PrerenderCancellationReason(PrerenderFinalStatus::kActivated));
      PrerenderHostId host_id = iter.first;
      prerender_new_tab_handle_by_id_.erase(iter);
      RemoveFromArrivalOrderQueues(host_id);
      return web_contents;
    }
  }
  return nullptr;
}

std::vector<FrameTree*> PrerenderHostRegistry::GetPrerenderFrameTrees() {
  std::vector<FrameTree*> result;
  for (auto& i : prerender_host_by_id_) {
    result.push_back(&i.second->GetPrerenderFrameTree());
  }
  if (reserved_prerender_host_) {
    result.push_back(&reserved_prerender_host_->GetPrerenderFrameTree());
  }

  return result;
}

std::vector<FrameTreeNode*>
PrerenderHostRegistry::GetNewTabPrerenderFrameTreeNodes() {
  std::vector<FrameTreeNode*> result;
  for (auto& [id, handle] : prerender_new_tab_handle_by_id_) {
    PrerenderHost* host =
        handle->GetPrerenderHostRegistry().FindNonReservedHostById(
            handle->prerender_host_id());
    if (host) {
      result.push_back(host->GetPrerenderFrameTree().root());
    }
  }
  return result;
}

PrerenderHost* PrerenderHostRegistry::FindHostByUrlForTesting(
    const GURL& prerendering_url) {
  for (auto& iter : prerender_host_by_id_) {
    if (iter.second->IsUrlMatch(prerendering_url)) {
      return iter.second.get();
    }
  }
  return nullptr;
}

PrerenderHost* PrerenderHostRegistry::FindPrewarmSearchResultHostForTesting(
    const GURL& search_prewarm_url) {
  for (auto& iter : prerender_host_by_id_) {
    if (iter.second->GetInitialUrl() == search_prewarm_url) {
      return iter.second.get();
    }
  }
  return nullptr;
}

bool PrerenderHostRegistry::HasNewTabHandleByIdForTesting(
    PrerenderHostId prerender_host_id) {
  return prerender_new_tab_handle_by_id_.contains(prerender_host_id);
}

void PrerenderHostRegistry::CancelAllHostsForTesting() {
  CancelAllHosts(PrerenderFinalStatus::kCancelAllHostsForTesting);
}

void PrerenderHostRegistry::BackNavigationLikely(
    PreloadingPredictor predictor) {
  if (http_cache_query_loader_) {
    return;
  }

  PreloadingDataImpl* preloading_data =
      PreloadingDataImpl::GetOrCreateForWebContents(web_contents());
  preloading_data->SetIsNavigationInDomainCallback(
      predictor,
      base::BindRepeating(IsNavigationInSessionHistoryPredictorDomain));

  WebContentsImpl* contents = static_cast<WebContentsImpl*>(web_contents());
  NavigationControllerImpl& controller = contents->GetController();
  const std::optional<int> target_index = controller.GetIndexForGoBack();

  if (!target_index.has_value()) {
    RecordPrerenderBackNavigationEligibility(
        predictor, PrerenderBackNavigationEligibility::kNoBackEntry, nullptr);
    return;
  }

  NavigationEntryImpl* back_entry = controller.GetEntryAtIndex(*target_index);
  CHECK(back_entry);
  const GURL& back_url = back_entry->GetURL();

  if (controller.GetBackForwardCache()
          .GetOrEvictEntry(back_entry->GetUniqueID())
          .has_value()) {
    RecordPrerenderBackNavigationEligibility(
        predictor, PrerenderBackNavigationEligibility::kBfcacheEntryExists,
        nullptr);
    return;
  }

  PreloadingURLMatchCallback same_url_matcher =
      PreloadingData::GetSameURLMatcher(back_url);
  ukm::SourceId triggered_primary_page_source_id =
      web_contents()->GetPrimaryMainFrame()->GetPageUkmSourceId();
  preloading_data->AddPreloadingPrediction(predictor, PreloadingConfidence{100},
                                           same_url_matcher,
                                           triggered_primary_page_source_id);
  PreloadingAttempt* attempt = preloading_data->AddPreloadingAttempt(
      predictor, PreloadingType::kPrerender, same_url_matcher,
      triggered_primary_page_source_id);

  if (back_entry->GetMainFrameDocumentSequenceNumber() ==
      controller.GetLastCommittedEntry()
          ->GetMainFrameDocumentSequenceNumber()) {
    RecordPrerenderBackNavigationEligibility(
        predictor, PrerenderBackNavigationEligibility::kTargetIsSameDocument,
        attempt);
    return;
  }

  if (back_entry->root_node()->frame_entry->method() != "GET") {
    RecordPrerenderBackNavigationEligibility(
        predictor, PrerenderBackNavigationEligibility::kMethodNotGet, attempt);
    return;
  }

  if (prerender_navigation_utils::IsDisallowedHttpResponseCode(
          back_entry->GetHttpStatusCode())) {
    RecordPrerenderBackNavigationEligibility(
        predictor,
        PrerenderBackNavigationEligibility::kTargetIsFailedNavigation, attempt);
    return;
  }

  if (!back_url.SchemeIsHTTPOrHTTPS()) {
    RecordPrerenderBackNavigationEligibility(
        predictor, PrerenderBackNavigationEligibility::kTargetIsNonHttp,
        attempt);
    return;
  }

  // While same site back navigations could potentially be prerendered, doing so
  // would involve more significant compat risk. For now, we consider them
  // ineligible. See https://crbug.com/1422266 .
  if (prerender_navigation_utils::IsSameSite(
          back_url,
          contents->GetPrimaryMainFrame()->GetLastCommittedOrigin())) {
    RecordPrerenderBackNavigationEligibility(
        predictor, PrerenderBackNavigationEligibility::kTargetIsSameSite,
        attempt);
    return;
  }

  // Session history prerendering will reuse the back navigation entry's
  // existing SiteInstance. We can't have a prerendered document share a
  // SiteInstance with related active content (i.e. an active document with the
  // same BrowsingInstance) as that would risk having scripting connections to
  // prerendered documents. So this case is not eligible for prerendering.
  SiteInstanceImpl* entry_site_instance = back_entry->site_instance();
  // `entry_site_instance` could be null in cases such as session restore.
  if (entry_site_instance) {
    const bool current_and_target_related =
        contents->GetSiteInstance()->IsRelatedSiteInstance(entry_site_instance);
    const size_t allowable_related_count = current_and_target_related ? 1u : 0u;
    if (entry_site_instance->GetRelatedActiveContentsCount() >
        allowable_related_count) {
      RecordPrerenderBackNavigationEligibility(
          predictor, PrerenderBackNavigationEligibility::kRelatedActiveContents,
          attempt);
      return;
    }
  }

  // To determine whether the resource for the target entry is in the HTTP
  // cache, we send a "fake" ResourceRequest which only loads from the cache.
  scoped_refptr<network::SharedURLLoaderFactory> url_loader_factory =
      contents->GetPrimaryMainFrame()
          ->GetStoragePartition()
          ->GetURLLoaderFactoryForBrowserProcess();
  http_cache_query_loader_ = CreateHttpCacheQueryingResourceLoad(back_url);
  http_cache_query_loader_->DownloadHeadersOnly(
      url_loader_factory.get(),
      base::BindOnce(&PrerenderHostRegistry::OnBackResourceCacheResult,
                     base::Unretained(this), predictor, attempt->GetWeakPtr(),
                     back_url));
}

void PrerenderHostRegistry::OnBackResourceCacheResult(
    PreloadingPredictor predictor,
    base::WeakPtr<PreloadingAttempt> attempt,
    GURL back_url,
    scoped_refptr<net::HttpResponseHeaders> headers) {
  // It's safe to delete the SimpleURLLoader while running the callback that was
  // passed to it. We do so once we're done with it in this method.
  std::unique_ptr<network::SimpleURLLoader> http_cache_query_loader =
      std::move(http_cache_query_loader_);

  // A LOAD_ONLY_FROM_CACHE request is considered successful only if it is
  // served from the cache. Note that net::OK may be returned even when
  // LoadedFromCache() is false (e.g., when a test interceptor satisfies the
  // request).
  if (http_cache_query_loader->NetError() != net::OK ||
      !http_cache_query_loader->LoadedFromCache()) {
    RecordPrerenderBackNavigationEligibility(
        predictor, PrerenderBackNavigationEligibility::kNoHttpCacheEntry,
        attempt.get());
    return;
  }

  RecordPrerenderBackNavigationEligibility(
      predictor, PrerenderBackNavigationEligibility::kEligible, attempt.get());

  if (attempt) {
    attempt->SetHoldbackStatus(PreloadingHoldbackStatus::kAllowed);
    // At this point, we are only collecting metrics and not actually
    // prerendering anything.
    attempt->SetTriggeringOutcome(PreloadingTriggeringOutcome::kNoOp);
  }
}

base::WeakPtr<PrerenderHostRegistry> PrerenderHostRegistry::GetWeakPtr() {
  return weak_factory_.GetWeakPtr();
}

PrerenderHostId PrerenderHostRegistry::GetPrerenderHostIdForNavigation(
    NavigationRequest* navigation_request) {
  PrerenderHost* prerender_host = nullptr;
  if (navigation_request->IsInPrerenderedMainFrame()) {
    // This navigation is running on the main frame in the prerendered page, so
    // its FrameTree::Delegate should be PrerenderHost.
    prerender_host = &PrerenderHost::GetFromFrameTreeNode(
        *navigation_request->frame_tree_node());
  } else {
    // Since the navigation in the fenced frames are deferred until the
    // activation, we do not need to check the outermost main frame for
    // navigation requests in prerendered pages.
    PrerenderHostId main_frame_host_id = navigation_request->frame_tree_node()
                                             ->frame_tree()
                                             .delegate()
                                             ->GetPrerenderHostId();
    prerender_host = FindNonReservedHostById(main_frame_host_id);
  }
  if (prerender_host) {
    return prerender_host->prerender_host_id();
  }
  return PrerenderHostId();
}

void PrerenderHostRegistry::DidStartNavigation(
    NavigationHandle* navigation_handle) {
  // DidStartNavigation is used for monitoring the main frame navigation in a
  // prerendered page so do nothing for other navigations.
  auto* navigation_request = NavigationRequest::From(navigation_handle);
  if (!navigation_request->IsInPrerenderedMainFrame() ||
      navigation_request->IsSameDocument()) {
    return;
  }

  // This navigation is running on the main frame in the prerendered page, so
  // its FrameTree::Delegate should be PrerenderHost.
  auto& prerender_host = PrerenderHost::GetFromFrameTreeNode(
      *navigation_request->frame_tree_node());
  prerender_host.DidStartNavigation(navigation_handle);
}

void PrerenderHostRegistry::ReadyToCommitNavigation(
    NavigationHandle* navigation_handle) {
  // ReadyToCommitNavigation is used for monitoring the main frame navigation in
  // a prerendered page so do nothing for other navigations.
  auto* navigation_request = NavigationRequest::From(navigation_handle);
  if (!navigation_request->IsInPrerenderedMainFrame() ||
      navigation_request->IsSameDocument()) {
    return;
  }

  // This navigation is running on the main frame in the prerendered page, so
  // its FrameTree::Delegate should be PrerenderHost.
  auto& prerender_host = PrerenderHost::GetFromFrameTreeNode(
      *navigation_request->frame_tree_node());

  prerender_host.ReadyToCommitNavigation(navigation_handle);
}

void PrerenderHostRegistry::DidFinishNavigation(
    NavigationHandle* navigation_handle) {
  auto* navigation_request = NavigationRequest::From(navigation_handle);

  if (navigation_request->IsSameDocument()) {
    // If a navigation in the prerendered page starts as same-document but is
    // restarted as cross-document, it can cause duplicate DidFinishNavigation
    // calls and CHECK failures because the initial start was ignored.
    // Since prerendering is an optimization, we cancel the prerender in this
    // corner case to avoid complex state management.
    // This is guarded by a kill switch feature flag.
    if (navigation_request->was_reset_for_cross_document_restart() &&
        base::FeatureList::IsEnabled(kPrerenderCancelOnCrossDocumentRestart)) {
      PrerenderHostId prerender_host_id =
          navigation_handle->GetPrerenderHostId();
      CancelHost(prerender_host_id,
                 PrerenderFinalStatus::kCrossDocumentRestart);
    }
    return;
  }

  PrerenderHostId main_frame_host_id = navigation_request->frame_tree_node()
                                           ->frame_tree()
                                           .delegate()
                                           ->GetPrerenderHostId();
  PrerenderHost* prerender_host = FindNonReservedHostById(main_frame_host_id);
  if (!prerender_host) {
    return;
  }

  prerender_host->DidFinishNavigation(navigation_handle);

  if (running_prerender_host_id_ == main_frame_host_id) {
    running_prerender_host_id_ = PrerenderHostId();
    StartPrerendering(PrerenderHostId());
  }
}

void PrerenderHostRegistry::OnVisibilityChanged(Visibility visibility) {
  // Update the timer for prerendering timeout in the background.
  if (IsBackground(visibility)) {
    if (timeout_timer_for_embedder_.IsRunning() ||
        timeout_timer_for_speculation_rules_.IsRunning()) {
      // Keep the timers which started on a previous visibility change.
      return;
    }
    // Keep a prerendered page alive in the background when its visibility
    // state changes to HIDDEN or OCCLUDED.
    timeout_timer_for_embedder_.SetTaskRunner(GetTimerTaskRunner());
    timeout_timer_for_speculation_rules_.SetTaskRunner(GetTimerTaskRunner());

    // Cancel PrerenderHost in the background when it exceeds a certain
    // amount of time. The timeout differs depending on the trigger type.
    timeout_timer_for_embedder_.Start(
        FROM_HERE, kTimeToLiveInBackgroundForEmbedder,
        base::BindOnce(&PrerenderHostRegistry::CancelHostsForTriggers,
                       base::Unretained(this),
                       std::vector({PreloadingTriggerType::kEmbedder}),
                       PrerenderCancellationReason(
                           PrerenderFinalStatus::kTimeoutBackgrounded)));
    timeout_timer_for_speculation_rules_.Start(
        FROM_HERE, kTimeToLiveInBackgroundForSpeculationRules,
        base::BindOnce(
            &PrerenderHostRegistry::CancelHostsForTriggers,
            base::Unretained(this),
            std::vector(
                {PreloadingTriggerType::kSpeculationRule,
                 PreloadingTriggerType::kSpeculationRuleFromIsolatedWorld}),
            PrerenderCancellationReason(
                PrerenderFinalStatus::kTimeoutBackgrounded)));
  } else {
    // Stop the timer when a prerendered page gets visible to users.
    timeout_timer_for_embedder_.Stop();
    timeout_timer_for_speculation_rules_.Stop();

    // Start the next prerender if needed.
    if (running_prerender_host_id_.is_null()) {
      StartPrerendering(PrerenderHostId());
    }
  }
}

void PrerenderHostRegistry::PrimaryMainFrameRenderProcessGone(
    base::TerminationStatus status) {
  CancelAllHosts(
      status == base::TERMINATION_STATUS_PROCESS_CRASHED
          ? PrerenderFinalStatus::kPrimaryMainFrameRendererProcessCrashed
          : PrerenderFinalStatus::kPrimaryMainFrameRendererProcessKilled);
}

bool PrerenderHostRegistry::CanNavigationActivateHost(
    NavigationRequest& navigation_request,
    PrerenderHost& host) {
  RenderFrameHostImpl* render_frame_host =
      navigation_request.frame_tree_node()->current_frame_host();
  TRACE_EVENT("navigation", "PrerenderHostRegistry::CanNavigationActivateHost",
              "navigation_url", navigation_request.GetURL().spec(),
              "render_frame_host", render_frame_host);

  // Disallow activation when the navigation URL has an effective URL like
  // hosted apps and NTP.
  if (SiteInstanceImpl::HasEffectiveURL(web_contents()->GetBrowserContext(),
                                        navigation_request.GetURL())) {
    CancelHost(host.prerender_host_id(),
               PrerenderFinalStatus::kActivationUrlHasEffectiveUrl);
    return false;
  }

  // Disallow activation when other auxiliary browsing contexts (e.g., pop-up
  // windows) exist in the same browsing context group. This is because these
  // browsing contexts should be able to script each other, but prerendered
  // pages are created in new browsing context groups.
  SiteInstance* site_instance = render_frame_host->GetSiteInstance();
  if (site_instance->GetRelatedActiveContentsCount() != 1u) {
    CancelHost(host.prerender_host_id(),
               PrerenderFinalStatus::kActivatedWithAuxiliaryBrowsingContexts);
    return false;
  }

  // Disallow activation when the navigation happens in the hidden tab.
  //
  // This visibility check is a bit tricky:
  //
  // - If this host is for prerendering in the same tab, `web_contents()` is the
  //   same as `host.initiator_web_contents()`. Thus, both web_contents should
  //   return the same visibility. In this case, we don't need to check both
  //   web_contents here but it's still necessary for the next case.
  //
  // - If this host is for prerendering in a new tab (i.e., `target_hint` is
  //   `_blank` in speculation rules), `web_contents()` is different from
  //   `host.initiator_web_contents()`. Depending on platforms (e.g., WPT on
  //   macOS), `web_contents()`'s visibiltiy can still be hidden and instead
  //   `host.initiator_web_contents()` is visible at this point. Thus,
  //   activation is allowed when either of them is visible.
  //
  // TODO(crbug.com/40249964): Remove the restriction after further
  // investigation and discussion.
  CHECK(host.initiator_web_contents());
  if (web_contents()->GetVisibility() == Visibility::HIDDEN &&
      host.initiator_web_contents()->GetVisibility() == Visibility::HIDDEN) {
    CancelHost(host.prerender_host_id(),
               PrerenderFinalStatus::kActivatedInBackground);
    return false;
  }

  {
    PrerenderCancellationReason reason = PrerenderCancellationReason::
        CreateCandidateReasonForActivationParameterMismatch();
    // Compare navigation params from activation with the navigation params
    // from the initial prerender navigation. If they don't match, the
    // navigation should not activate the prerendered page.
    if (!host.AreInitialPrerenderNavigationParamsCompatibleWithNavigation(
            navigation_request, reason)) {
      // TODO(lingqi): We'd better cancel all hosts.

      CancelHost(host.prerender_host_id(), reason);
      return false;
    }
  }

  if (!host.IsFramePolicyCompatibleWithPrimaryFrameTree()) {
    CancelHost(host.prerender_host_id(),
               PrerenderFinalStatus::kActivationFramePolicyNotCompatible);
    return false;
  }

  // Cancel all the other prerender hosts because we no longer need the other
  // hosts after we determine the host to be activated.
  std::vector<PrerenderHostId> cancelled_prerenders;
  for (const auto& [host_id, prerender_host] : prerender_host_by_id_) {
    if (host_id != host.prerender_host_id()) {
      cancelled_prerenders.push_back(prerender_host->prerender_host_id());
    }
  }
  for (const auto& [host_id, handle] : prerender_new_tab_handle_by_id_) {
    cancelled_prerenders.push_back(handle->prerender_host_id());
  }
  CancelHosts(cancelled_prerenders,
              PrerenderCancellationReason(
                  PrerenderFinalStatus::kOtherPrerenderedPageActivated));
  pending_prerenders_.clear();

  return true;
}

void PrerenderHostRegistry::DeletePendingDeletionHosts(
    PrerenderHostId prerender_host_id) {
  // Avoid directly destructing the host in the map. See the comments in
  // `DestructPrerenderHosts()` for details.
  std::unique_ptr<PrerenderHost> prerender_host =
      std::move(pending_deletion_hosts_[prerender_host_id]);
  pending_deletion_hosts_.erase(prerender_host_id);
  DestructPrerenderHosts(prerender_host);

  if (pending_deletion_new_tab_prerender_handle_) {
    // Delete the handle asynchronously to avoid delete `this`, as the handle
    // owns the prerender WebContents, which indirectly owns this
    // PrerenderHostRegistry.
    base::SingleThreadTaskRunner::GetCurrentDefault()->DeleteSoon(
        FROM_HERE, std::move(pending_deletion_new_tab_prerender_handle_));
  }
}

void PrerenderHostRegistry::SchedulePendingDeletionPrerenderNewTabHandle(
    base::PassKey<PrerenderNewTabHandle>,
    std::unique_ptr<PrerenderNewTabHandle> handle) {
  CHECK(!pending_deletion_new_tab_prerender_handle_);
  pending_deletion_new_tab_prerender_handle_ = std::move(handle);
}

void PrerenderHostRegistry::ScheduleToDeleteAbandonedHost(
    std::unique_ptr<PrerenderHost> prerender_host,
    const PrerenderCancellationReason& cancellation_reason) {
  prerender_host->RecordFailedFinalStatus(PassKey(), cancellation_reason);

  // TODO(crbug.com/353628449): Support pagehide event dispatch for
  // PrerenderFinalStatus::kWindowClosed.
  if (cancellation_reason.final_status() ==
      PrerenderFinalStatus::kSpeculationRuleRemoved) {
    // Fire unload related events upon intended prerender cancellation.
    RenderFrameHostImpl* rfhi = prerender_host->GetPrerenderedMainFrameHost();
    PrerenderHostId prerender_host_id = prerender_host->prerender_host_id();
    pending_deletion_hosts_[prerender_host_id] = std::move(prerender_host);
    rfhi->ClosePage(
        RenderFrameHostImpl::ClosePageSource::kPrerenderDiscard,
        base::BindRepeating(&PrerenderHostRegistry::DeletePendingDeletionHosts,
                            weak_factory_.GetWeakPtr(), prerender_host_id));
    return;
  }

  // Asynchronously delete the prerender host.
  to_be_deleted_hosts_.push_back(std::move(prerender_host));

  // A task has already been scheduled to delete the abandoned hosts.
  if (to_be_deleted_hosts_.size() > 1) {
    return;
  }
  base::SequencedTaskRunner::GetCurrentDefault()->PostTask(
      FROM_HERE, base::BindOnce(&PrerenderHostRegistry::DeleteAbandonedHosts,
                                weak_factory_.GetWeakPtr()));
}

void PrerenderHostRegistry::DeleteAbandonedHosts() {
  DestructPrerenderHosts(to_be_deleted_hosts_);
}

void PrerenderHostRegistry::NotifyTrigger(const GURL& url) {
  for (Observer& obs : observers_) {
    obs.OnTrigger(url);
  }
}

void PrerenderHostRegistry::NotifyRetriggerable(
    PrerenderHostId prerender_host_id,
    const PrerenderCancellationReason& reason) {
  for (Observer& obs : observers_) {
    obs.OnRetriggerable(prerender_host_id, reason);
  }
}

void PrerenderHostRegistry::RemoveFromArrivalOrderQueues(
    PrerenderHostId host_id) {
  for (auto& queue : arrival_order_queue_by_limit_group_) {
    base::Erase(queue, host_id);
  }
}

PrerenderHostRegistry::PrerenderLimitGroup
PrerenderHostRegistry::GetPrerenderLimitGroup(
    PreloadingTriggerType trigger_type,
    std::optional<blink::mojom::SpeculationEagerness> eagerness) {
  switch (trigger_type) {
    case PreloadingTriggerType::kSpeculationRule:
    case PreloadingTriggerType::kSpeculationRuleFromIsolatedWorld:
    case PreloadingTriggerType::kSpeculationRuleFromAutoSpeculationRules:
      CHECK(eagerness.has_value());
      return IsImmediateSpeculationEagerness(eagerness.value())
                 ? PrerenderLimitGroup::kSpeculationRulesImmediate
                 : PrerenderLimitGroup::kSpeculationRulesNonImmediate;
    case PreloadingTriggerType::kEmbedder:
      return PrerenderLimitGroup::kEmbedder;
  }
}

int PrerenderHostRegistry::GetHostCountByLimitGroup(
    PrerenderLimitGroup limit_group) {
  return arrival_order_queue_by_limit_group_[std::to_underlying(limit_group)]
      .size();
}

// Prerender eviction and replacement policy per limit group:
//
// These replacement and eviction rules enforce capacity limits both under
// standard max capacity and under memory pressure scaling:
//
// 1. kSpeculationRulesImmediate (LIFO - evict/refuse newest first):
//    Newly started immediate prerenders actively churn CPU and allocate memory
//    buffers while parsing DOM and executing JS. Canceling the newest host
//    first under memory pressure instantly halts active allocation, preserving
//    older, fully-loaded hosts ready for activation. Under standard capacity
//    limits, new immediate triggers are refused or queued while a host is
//    running.
//
// 2. kSpeculationRulesNonImmediate (FIFO - evict oldest first):
//    Non-immediate triggers (e.g., pointer hovers) reflect evolving user
//    intent. Fresher triggers represent higher probability of activation than
//    older, stale user interactions, so reaching the capacity limit evicts the
//    oldest non-immediate trigger to start the newest one.
//
// 3. kEmbedder (FIFO - evict oldest first):
//    Browser-initiated predictions (e.g., Omnibox typing) update as user input
//    progresses. Newer predictions supersede older predictions.
bool ShouldEvictNewestForLimitGroup(
    PrerenderHostRegistry::PrerenderLimitGroup limit_group) {
  switch (limit_group) {
    case PrerenderHostRegistry::PrerenderLimitGroup::kSpeculationRulesImmediate:
      return true;
    case PrerenderHostRegistry::PrerenderLimitGroup::
        kSpeculationRulesNonImmediate:
    case PrerenderHostRegistry::PrerenderLimitGroup::kEmbedder:
      return false;
  }
}

bool PrerenderHostRegistry::IsAllowedToStartPrerenderingForTrigger(
    PreloadingTriggerType trigger_type,
    std::optional<blink::mojom::SpeculationEagerness> eagerness) {
  const PrerenderLimitGroup limit_group =
      GetPrerenderLimitGroup(trigger_type, eagerness);

  const int host_count = GetHostCountByLimitGroup(limit_group);

  switch (limit_group) {
    case PrerenderLimitGroup::kSpeculationRulesImmediate:
      return host_count < GetScaledLimit(limit_group);
    case PrerenderLimitGroup::kSpeculationRulesNonImmediate: {
      const int host_limit = GetScaledLimit(limit_group);

      if (host_limit == 0) {
        return false;
      }

      // When the limit on non-immediate speculation rules is reached, cancel
      // the oldest host to allow a newly incoming trigger to start.
      if (GetHostCountByLimitGroup(limit_group) >= host_limit) {
        auto& queue = arrival_order_queue_by_limit_group_[std::to_underlying(
            PrerenderLimitGroup::kSpeculationRulesNonImmediate)];
        CHECK(!queue.empty());
        PrerenderHostId oldest_prerender_host_id = queue.front();
        CHECK(
            prerender_host_by_id_.contains(oldest_prerender_host_id) ||
            prerender_new_tab_handle_by_id_.contains(oldest_prerender_host_id));

        CHECK(CancelHost(oldest_prerender_host_id,
                         PrerenderFinalStatus::
                             kMaxNumOfRunningNonImmediatePrerendersExceeded));
      }

      return true;
    }
    case PrerenderLimitGroup::kEmbedder:
      return IsAllowedToStartPrerenderingForEmbedder();
  }
}

void PrerenderHostRegistry::OnUpdateMemoryLimit() {}

void PrerenderHostRegistry::OnReleaseMemory() {
  if (memory_limit() <= base::kCriticalMemoryPressureThreshold) {
    CancelAllHosts(PrerenderFinalStatus::kMemoryPressureAfterTriggered);
    return;
  }

  if (base::FeatureList::IsEnabled(base::kStatefulMemoryPressure)) {
    for (auto limit_group : {PrerenderLimitGroup::kSpeculationRulesImmediate,
                             PrerenderLimitGroup::kSpeculationRulesNonImmediate,
                             PrerenderLimitGroup::kEmbedder}) {
      EvictExcessHostsForLimitGroup(limit_group);
    }
  }
}

void PrerenderHostRegistry::EvictExcessHostsForLimitGroup(
    PrerenderLimitGroup limit_group) {
  const int target_limit = GetScaledLimit(limit_group);
  const PrerenderCancellationReason reason(
      PrerenderFinalStatus::kMemoryPressureAfterTriggered);
  const bool evict_newest = ShouldEvictNewestForLimitGroup(limit_group);

  while (GetHostCountByLimitGroup(limit_group) > target_limit) {
    auto& queue =
        arrival_order_queue_by_limit_group_[std::to_underlying(limit_group)];
    if (queue.empty()) {
      break;
    }
    PrerenderHostId host_id = evict_newest ? queue.back() : queue.front();
    if (!CancelHost(host_id, reason)) {
      break;
    }
  }
}

scoped_refptr<base::SingleThreadTaskRunner>
PrerenderHostRegistry::GetTimerTaskRunner() {
  return timer_task_runner_for_testing_
             ? timer_task_runner_for_testing_
             : base::SingleThreadTaskRunner::GetCurrentDefault();
}

int PrerenderHostRegistry::GetMaxLimit(PrerenderLimitGroup limit_group) const {
  switch (limit_group) {
    case PrerenderLimitGroup::kSpeculationRulesImmediate:
      return kMaxRunningSpeculationRulesImmediatePrerenders;
    case PrerenderLimitGroup::kSpeculationRulesNonImmediate:
      return kMaxRunningSpeculationRulesNonImmediatePrerenders;
    case PrerenderLimitGroup::kEmbedder: {
      auto* delegate = web_contents()->GetDelegate();
      return delegate ? delegate->AllowedPrerenderingCount(*web_contents()) : 0;
    }
  }
}

int PrerenderHostRegistry::GetScaledLimit(
    PrerenderLimitGroup limit_group) const {
  const int max_limit = GetMaxLimit(limit_group);

  // Check feature parameters to determine if memory limit scaling is enabled
  // for the specified limit group.
  bool should_scale = false;
  switch (limit_group) {
    case PrerenderLimitGroup::kSpeculationRulesImmediate:
      should_scale = kPrerenderScaleImmediate.Get();
      break;
    case PrerenderLimitGroup::kSpeculationRulesNonImmediate:
      should_scale = kPrerenderScaleNonImmediate.Get();
      break;
    case PrerenderLimitGroup::kEmbedder:
      should_scale = kPrerenderScaleEmbedder.Get();
      break;
  }
  return should_scale
             ? base::ScaleByMemoryLimit(max_limit, GetCurrentMemoryLimit())
             : max_limit;
}

int PrerenderHostRegistry::GetCurrentMemoryLimit() const {
  if (!base::FeatureList::IsEnabled(base::kStatefulMemoryPressure)) {
    return base::MemoryConsumer::kDefaultMemoryLimit;
  }

  return memory_limit();
}

void PrerenderHostRegistry::SetTaskRunnerForTesting(
    scoped_refptr<base::SingleThreadTaskRunner> task_runner) {
  timer_task_runner_for_testing_ = std::move(task_runner);
}

bool PrerenderHostRegistry::PrerenderCanBeStartedWhenInitiatorIsInBackground() {
  // Allow at most 1 prerendering to be started if the initiator page is
  // still in the background.

  // There is a running prerender, so no extra prerender is allowed before
  // this one is finished.
  if (running_prerender_host_id_) {
    return false;
  }

  // There are non-pending prerenders, which have finished the initial
  // navigation and been waiting for activation. Don't start a new prerender.
  if (prerender_host_by_id_.size() - pending_prerenders_.size() >= 1) {
    return false;
  }

  // One or more than prerenders for new tab finished or are running. Don't
  // start a new prerender.
  if (prerender_new_tab_handle_by_id_.size() >= 1) {
    return false;
  }

  return true;
}

bool PrerenderHostRegistry::IsAllowedToStartPrerenderingForEmbedder() {
  int host_count = GetHostCountByLimitGroup(PrerenderLimitGroup::kEmbedder);
  const int scaled_limit = GetScaledLimit(PrerenderLimitGroup::kEmbedder);
  return host_count < scaled_limit;
}

void PrerenderHostRegistry::CancelHostsByOriginFilter(
    const StoragePartition::StorageKeyMatcherFunction& storage_key_filter,
    PrerenderFinalStatus final_status) {
  std::vector<PrerenderHostId> ids_to_be_deleted;

  for (const auto& [host_id, host] : prerender_host_by_id_) {
    if (host->initiator_origin().has_value()) {
      if (storage_key_filter.Run(blink::StorageKey::CreateFirstParty(
              host->initiator_origin().value()))) {
        ids_to_be_deleted.push_back(host->prerender_host_id());
      }
    }
  }

  for (const auto& [host_id, handle] : prerender_new_tab_handle_by_id_) {
    if (handle->initiator_origin().has_value()) {
      if (storage_key_filter.Run(blink::StorageKey::CreateFirstParty(
              handle->initiator_origin().value()))) {
        ids_to_be_deleted.push_back(handle->prerender_host_id());
      }
    } else {
      CHECK(prerender_new_tab_handle_by_id_.empty());
    }
  }

  if (!ids_to_be_deleted.empty()) {
    CancelHosts(ids_to_be_deleted, PrerenderCancellationReason(final_status));
  }
}

void PrerenderHostRegistry::RecordPotentialPrerenderProcessReuse(
    bool has_matchable_hosts,
    const GURL& navigation_url) {
  static constexpr char kPrerenderProcessReuseUMAName[] =
      "Prerender.Experimental.PrerenderProcessReuseAvailability";
  if (has_matchable_hosts) {
    base::UmaHistogramEnumeration(
        kPrerenderProcessReuseUMAName,
        PrerenderProcessReuseAvailability::kHasMatchableHosts);
    return;
  }
  bool has_same_origin_host =
      std::find_if(prerender_host_by_id_.begin(), prerender_host_by_id_.end(),
                   [&navigation_url](const auto& pair) {
                     return pair.second->IsUrlSameOrigin(navigation_url);
                   }) != prerender_host_by_id_.end();
  bool has_same_site_host =
      std::find_if(prerender_host_by_id_.begin(), prerender_host_by_id_.end(),
                   [&navigation_url](const auto& pair) {
                     return pair.second->IsUrlSameSite(navigation_url);
                   }) != prerender_host_by_id_.end();
  PrerenderProcessReuseAvailability availability =
      PrerenderProcessReuseAvailability::kNoSameOriginOrSiteHosts;
  if (has_same_origin_host) {
    availability = PrerenderProcessReuseAvailability::kHasSameOriginHosts;
  } else if (has_same_site_host) {
    availability = PrerenderProcessReuseAvailability::kHasSameSiteHosts;
  }

  base::UmaHistogramEnumeration(kPrerenderProcessReuseUMAName, availability);
}

std::unique_ptr<PrerenderHost>
PrerenderHostRegistry::FindAndTakePrerenderHostToReuse(
    const PrerenderAttributes& attributes) {
  const GURL prerender_url = attributes.prerendering_url;
  auto iter =
      std::find_if(prerender_host_by_id_.begin(), prerender_host_by_id_.end(),
                   [&prerender_url](const auto& pair) {
                     return pair.second->IsUrlSameSite(prerender_url) &&
                            pair.second->IsReusable();
                   });
  if (iter != prerender_host_by_id_.end()) {
    PrerenderHostId reuse_host_id = iter->first;
    std::unique_ptr<PrerenderHost> reuse_host = std::move(iter->second);
    prerender_host_by_id_.erase(iter);
    RemoveFromArrivalOrderQueues(reuse_host_id);
    return reuse_host;
  }
  return nullptr;
}

int PrerenderHostRegistry::GetProcessReuseCount() const {
  return process_reuse_count_;
}

base::ScopedClosureRunner PrerenderHostRegistry::IncrementProcessReuseCount() {
  process_reuse_count_++;
  return base::ScopedClosureRunner(
      base::BindOnce(&PrerenderHostRegistry::DecrementProcessReuseCount,
                     weak_factory_.GetWeakPtr()));
}

void PrerenderHostRegistry::DecrementProcessReuseCount() {
  process_reuse_count_--;
}

}  // namespace content