// 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.

#ifndef CONTENT_BROWSER_PRELOADING_PRERENDER_PRERENDER_HOST_REGISTRY_H_
#define CONTENT_BROWSER_PRELOADING_PRERENDER_PRERENDER_HOST_REGISTRY_H_

#include <array>
#include <memory>
#include <set>
#include <string>
#include <utility>
#include <vector>

#include "base/containers/circular_deque.h"
#include "base/containers/flat_map.h"
#include "base/functional/callback_helpers.h"
#include "base/memory/scoped_refptr.h"
#include "base/memory/weak_ptr.h"
#include "base/memory_coordinator/memory_consumer.h"
#include "base/observer_list.h"
#include "base/observer_list_types.h"
#include "base/timer/timer.h"
#include "base/types/pass_key.h"
#include "content/browser/preloading/preloading_confidence.h"
#include "content/browser/preloading/prerender/prerender_final_status.h"
#include "content/browser/preloading/prerender/reserved_prerender_host_info.h"
#include "content/browser/web_contents/web_contents_impl.h"
#include "content/common/content_export.h"
#include "content/common/frame.mojom-forward.h"
#include "content/public/browser/preloading.h"
#include "content/public/browser/visibility.h"
#include "content/public/browser/web_contents.h"
#include "content/public/browser/web_contents_observer.h"
#include "third_party/blink/public/mojom/speculation_rules/speculation_rules.mojom-shared.h"

class GURL;

namespace base {
class SingleThreadTaskRunner;
}

namespace net {
class HttpResponseHeaders;
}

namespace network {
class SimpleURLLoader;
}  // namespace network

namespace content {

class FrameTree;
class FrameTreeNode;
class NavigationRequest;
class PrerenderCancellationReason;
class PrerenderHost;
class PrerenderNewTabHandle;
class RenderFrameHostImpl;
class StoredPage;
struct PrerenderAttributes;

// PrerenderHostRegistry creates and retains a prerender host, and reserves it
// for NavigationRequest to activate the prerendered page. This is created per
// WebContentsImpl and owned by it.
//
// The APIs of this class are categorized into two: APIs for triggers and APIs
// for activators.
//
// - Triggers (e.g., SpeculationHostImpl) start prerendering by
//   CreateAndStartHost() and notify the registry of destruction of the trigger
//   by CancelHosts().
// - Activators (i.e., NavigationRequest) can reserve the prerender host on
//   activation start by ReserveHostToActivate(), activate it by
//   ActivateReservedHost(), and notify the registry of completion of the
//   activation by OnActivationFinished().
class CONTENT_EXPORT PrerenderHostRegistry : public WebContentsObserver,
                                             public base::MemoryConsumer {
 public:
  // The time to allow prerendering kept alive in the background. All the hosts
  // that this PrerenderHostRegistry holds will be terminated when the timer
  // exceeds this. The timeout value differs depending on the trigger type. The
  // value for an embedder was determined by
  // PageLoad.Clients.Prerender.NavigationToActivation.*.
  // The value for speculation rules was determined to align with the default
  // value of BFCache's eviction timer
  // (kDefaultTimeToLiveInBackForwardCacheInSeconds).
  static constexpr base::TimeDelta kTimeToLiveInBackgroundForEmbedder =
      base::Seconds(19);
  static constexpr base::TimeDelta kTimeToLiveInBackgroundForSpeculationRules =
      base::Seconds(600);
  static constexpr int kMaxRunningSpeculationRulesImmediatePrerenders = 10;
  static constexpr int kMaxRunningSpeculationRulesNonImmediatePrerenders = 2;

  using PassKey = base::PassKey<PrerenderHostRegistry>;

  // These values are persisted to logs. Entries should not be renumbered and
  // numeric values should never be reused.
  //
  // LINT.IfChange(PrerenderProcessReuseAvailability)
  enum class PrerenderProcessReuseAvailability {
    kHasMatchableHosts = 0,
    kHasSameOriginHosts = 1,
    kHasSameSiteHosts = 2,
    kNoSameOriginOrSiteHosts = 3,
    kMaxValue = kNoSameOriginOrSiteHosts,
  };
  // LINT.ThenChange(//tools/metrics/histograms/metadata/navigation/enums.xml:PrerenderProcessReuseAvailability)

  explicit PrerenderHostRegistry(WebContents&);
  ~PrerenderHostRegistry() override;

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

  class Observer : public base::CheckedObserver {
   public:
    // Called once per CreateAndStartHost() call. Indicates the registry
    // received a request to create a prerender but does not necessarily mean a
    // host was created. If a host was created, it is guaranteed to be in the
    // registry at the time this is called.
    virtual void OnTrigger(const GURL& url) {}

    // Called when CancelHosts() actually cancels each host and allows them to
    // be retriggered.
    virtual void OnRetriggerable(PrerenderHostId host_id,
                                 const PrerenderCancellationReason& reason) {}

    // Called from the registry's destructor. The observer
    // should drop any reference to the registry.
    virtual void OnRegistryDestroyed() {}
  };

  void AddObserver(Observer* observer);
  void RemoveObserver(Observer* observer);

  // For triggers.
  // Creates and starts a host. Returns the PrerenderHostId of the created host.
  // `preloading_attempt` is the attempt corresponding to this prerender, the
  // default value is set to nullptr as every case of prerendering trigger is
  // not yet integrated with PreloadingAttempt.
  // TODO(crbug.com/40234240): Remove the default value as nullptr for
  // preloading_attempt once new-tab-prerender is integrated with Preloading
  // APIs.
  PrerenderHostId CreateAndStartHost(
      const PrerenderAttributes& attributes,
      PreloadingAttempt* preloading_attempt = nullptr);

  // Creates and starts a host in a new WebContents so that a navigation in a
  // new tab will be able to activate it. PrerenderHostRegistry associated with
  // the new WebContents manages the started host, and `this`
  // PrerenderHostRegistry manages PrerenderNewTabHandle that owns the
  // WebContents (see `prerender_new_tab_handle_by_id_`).
  PrerenderHostId CreateAndStartHostForNewTab(
      const PrerenderAttributes& attributes,
      const PreloadingPredictor& creating_predictor,
      const PreloadingPredictor& enacting_predictor,
      PreloadingConfidence confidence);

  // Cancels the host registered for PrerenderHostId. The host is immediately
  // removed from the map of non-reserved hosts but asynchronously destroyed so
  // that prerendered pages can cancel themselves without concern for self
  // destruction.
  // Returns true if a cancelation has occurred.
  bool CancelHost(PrerenderHostId prerender_host_id,
                  PrerenderFinalStatus final_status);
  // Same as CancelHost, but can pass a detailed reason for recording if given.
  bool CancelHost(PrerenderHostId prerender_host_id,
                  const PrerenderCancellationReason& reason);

  // Cancels the existing hosts specified in the vector with the same reason.
  // Returns a subset of `prerender_host_ids` that were actually cancelled.
  std::set<PrerenderHostId> CancelHosts(
      const std::vector<PrerenderHostId>& prerender_host_ids,
      const PrerenderCancellationReason& reason);

  // Applies CancelHost for all existing PrerenderHost.
  void CancelAllHosts(PrerenderFinalStatus final_status);

  // For activators. Finds the host to activate for a navigation for the given
  // NavigationRequest. Returns the PrerenderHostId of the prerendered page.
  // This doesn't reserve the host so it can be destroyed or activated by
  // another navigation. This also cancels all the prerender hosts except the
  // one to be activated. See also comments on ReserveHostToActivate().
  PrerenderHostId FindPotentialHostToActivate(
      NavigationRequest& navigation_request);

  // For activators. Reserves the host to activate for a navigation for the
  // given NavigationRequest.
  // Returns a valid ReservedPrerenderHostInfo, which has the valid
  // PrerenderHostId of the prerendered page. Returns nullopt if it's not found
  // or not ready for activation yet.
  // The caller is responsible for calling OnActivationFinished() with the id to
  // release the reserved host. This also cancels all the prerender hosts except
  // the one to be activated.
  std::optional<ReservedPrerenderHostInfo> ReserveHostToActivate(
      NavigationRequest& navigation_request,
      PrerenderHostId expected_host_id);

  // For activators.
  // Activates the host reserved by ReserveHostToActivate() and returns the
  // StoredPage containing the page that was activated on success, or nullptr
  // on failure.
  std::unique_ptr<StoredPage> ActivateReservedHost(
      PrerenderHostId prerender_host_id,
      NavigationRequest& navigation_request);

  RenderFrameHostImpl* GetRenderFrameHostForReservedHost(
      PrerenderHostId prerender_host_id);

  // For activators.
  // Called from the destructor of NavigationRequest that reserved the host.
  // `frame_tree_node_id` should be the id returned by ReserveHostToActivate().
  void OnActivationFinished(PrerenderHostId prerender_host_id);

  // Returns how many times the initiator's process has been reused for
  // prerendering.
  int GetProcessReuseCount() const;

  // Increments the reuse count for the initiator's process.
  [[nodiscard]] base::ScopedClosureRunner IncrementProcessReuseCount();

  // Returns the non-reserved host with the given id. Returns nullptr if the id
  // does not match any non-reserved host.
  PrerenderHost* FindNonReservedHostById(PrerenderHostId prerender_host_id);

  // Returns true if this registry reserves a host for activation.
  bool HasReservedHost() const;

  // Returns the ownership of a pre-created WebContentsImpl that contains a
  // prerendered page that corresponds to the given params for a new tab
  // navigation, if it exists.
  std::unique_ptr<WebContentsImpl> TakePreCreatedWebContentsForNewTabIfExists(
      const mojom::CreateNewWindowParams& create_new_window_params,
      const WebContents::CreateParams& web_contents_create_params);

  // Returns the FrameTrees owned by this registry's prerender hosts.
  std::vector<FrameTree*> GetPrerenderFrameTrees();

  // Returns the non-reserved host for `prerendering_url`. Returns nullptr if
  // the URL doesn't match any non-reserved host.
  PrerenderHost* FindHostByUrlForTesting(const GURL& prerendering_url);

  // Returns the prewarmed default search engine page. The prewarm page is
  // filtered by exactly matching the search prewarm URL with the initial URL of
  // the prerender host.
  PrerenderHost* FindPrewarmSearchResultHostForTesting(
      const GURL& search_prewarm_url);

  // Returns the root FrameTreeNodes of prerender hosts managed by new tab
  // handles. These are prerenders triggered with target_hint="_blank" that live
  // in separate WebContents from the initiator.
  std::vector<FrameTreeNode*> GetNewTabPrerenderFrameTreeNodes();

  // Returns whether `prerender_new_tab_handle_by_id_` has the given id.
  bool HasNewTabHandleByIdForTesting(PrerenderHostId prerender_host_id);

  // Cancels all hosts.
  void CancelAllHostsForTesting();

  // Represents the group of prerender limit calculated by PreloadingTriggerType
  // and SpeculationEagerness on GetPrerenderLimitGroup.
  enum class PrerenderLimitGroup {
    kSpeculationRulesImmediate,
    kSpeculationRulesNonImmediate,
    kEmbedder,
  };

  // May be called when it is believed to be likely that the user will perform a
  // back navigation due to the trigger indicated by `predictor` (e.g. they're
  // hovering over a back button).
  void BackNavigationLikely(PreloadingPredictor predictor);

  base::WeakPtr<PrerenderHostRegistry> GetWeakPtr();

  // Only used for tests.
  base::OneShotTimer* GetEmbedderTimerForTesting() {
    return &timeout_timer_for_embedder_;
  }
  base::OneShotTimer* GetSpeculationRulesTimerForTesting() {
    return &timeout_timer_for_speculation_rules_;
  }
  void SetTaskRunnerForTesting(
      scoped_refptr<base::SingleThreadTaskRunner> task_runner);
  bool HasOngoingHttpCacheQueryForTesting() const {
    return !!http_cache_query_loader_;
  }
  int GetHostCountByLimitGroupForTesting(PrerenderLimitGroup limit_group) {
    return GetHostCountByLimitGroup(limit_group);
  }
  PrerenderHostId StartPrerenderingForTesting(
      PrerenderHostId prerender_host_id) {
    return StartPrerendering(prerender_host_id);
  }
  size_t GetPendingPrerendersCountForTesting() const {
    return pending_prerenders_.size();
  }
  PrerenderHostId GetPendingPrerenderFrontForTesting() const {
    return pending_prerenders_.empty() ? PrerenderHostId()
                                       : pending_prerenders_.front();
  }
  int GetScaledLimitForTesting(PrerenderLimitGroup limit_group) const {
    return GetScaledLimit(limit_group);
  }

  bool PrerenderCanBeStartedWhenInitiatorIsInBackground();

  // Returns true when prerendering can be triggered for embedders without
  // hitting the number limit of running prerenders.
  bool IsAllowedToStartPrerenderingForEmbedder();

  // Cancels the existing hosts for the given origin filter.
  // Currently used for browsing data removal and Clear-Site-Data header.
  void CancelHostsByOriginFilter(
      const StoragePartition::StorageKeyMatcherFunction& storage_key_filter,
      PrerenderFinalStatus final_status);

  PrerenderHostId GetPrerenderHostIdForNavigation(
      NavigationRequest* navigation_request);
  void SchedulePendingDeletionPrerenderNewTabHandle(
      base::PassKey<PrerenderNewTabHandle>,
      std::unique_ptr<PrerenderNewTabHandle> handle);

 private:
  // WebContentsObserver implementation:
  void DidStartNavigation(NavigationHandle* navigation_handle) override;
  void ReadyToCommitNavigation(NavigationHandle* navigation_handle) override;
  void DidFinishNavigation(NavigationHandle* navigation_handle) override;
  void OnVisibilityChanged(Visibility visibility) override;
  void PrimaryMainFrameRenderProcessGone(
      base::TerminationStatus status) override;

  bool CancelHostInternal(PrerenderHostId prerender_host_id,
                          const PrerenderCancellationReason& reason);
  bool CancelNewTabHostInternal(PrerenderHostId prerender_host_id,
                                const PrerenderCancellationReason& reason);

  // Returns true if `navigation_request` can activate `host`.
  bool CanNavigationActivateHost(NavigationRequest& navigation_request,
                                 PrerenderHost& host);
  void DeletePendingDeletionHosts(PrerenderHostId prerender_host_id);
  void ScheduleToDeleteAbandonedHost(
      std::unique_ptr<PrerenderHost> prerender_host,
      const PrerenderCancellationReason& cancellation_reason);

  void DeleteAbandonedHosts();

  void NotifyTrigger(const GURL& url);
  void NotifyRetriggerable(PrerenderHostId host_id,
                           const PrerenderCancellationReason& reason);
  void RemoveFromArrivalOrderQueues(PrerenderHostId host_id);

  // Pops one PrerenderHost from the queue and starts the prerendering if
  // there's no running prerender and an invalid PrerenderHostId is passed as
  // `prerender_host_id`. If the given `prerender_host_id` is valid, this
  // function starts prerendering for the id. Returns starting PrerenderHostId
  // when it succeeds, and returns an invalid PrerenderHostId if it's cancelled.
  PrerenderHostId StartPrerendering(PrerenderHostId prerender_host_id);

  // Cancels the existing hosts that were triggered by `trigger_types`.
  void CancelHostsForTriggers(std::vector<PreloadingTriggerType> trigger_types,
                              const PrerenderCancellationReason& reason);

  // Calculates PrerenderLimitGroup by PreloadingTriggerType and
  // SpeculationEagerness.
  PrerenderLimitGroup GetPrerenderLimitGroup(
      PreloadingTriggerType trigger_type,
      std::optional<blink::mojom::SpeculationEagerness> eagerness);

  // Returns the number of hosts that prerender_host_by_id_ holds by limit
  // group.
  int GetHostCountByLimitGroup(PrerenderLimitGroup limit_group);

  // Returns whether a certain type of PreloadingTriggerType is allowed to be
  // added to PrerenderHostRegistry according to the limit of the given
  // PreloadingTriggerType. SpeculationEagerness is additionally considered in
  // order to apply the limits and behaviors according to
  // PrerenderLimitGroup.
  bool IsAllowedToStartPrerenderingForTrigger(
      PreloadingTriggerType trigger_type,
      std::optional<blink::mojom::SpeculationEagerness> eagerness);

  // Called when we have the HTTP cache result of the main resource of the back
  // navigation queried by `BackNavigationLikely`.
  void OnBackResourceCacheResult(
      PreloadingPredictor predictor,
      base::WeakPtr<PreloadingAttempt> attempt,
      GURL back_url,
      scoped_refptr<net::HttpResponseHeaders> headers);

  // base::MemoryConsumer:
  void OnUpdateMemoryLimit() override;
  void OnReleaseMemory() override;

  // Evicts excess running prerender hosts in `limit_group` if current host
  // count exceeds the scaled capacity limit using the limit group's eviction
  // policy (LIFO vs. FIFO).
  void EvictExcessHostsForLimitGroup(PrerenderLimitGroup limit_group);

  void RecordPotentialPrerenderProcessReuse(bool has_matchable_hosts,
                                            const GURL& navigation_url);

  // Find a prerender host that is marked as reusable and under the
  // same site as attributes.prerendering_url.
  std::unique_ptr<PrerenderHost> FindAndTakePrerenderHostToReuse(
      const PrerenderAttributes& attributes);

  scoped_refptr<base::SingleThreadTaskRunner> GetTimerTaskRunner();

  // Returns the current memory pressure limit percentage (0 to 100). Returns
  // base::MemoryConsumer::kDefaultMemoryLimit (100) if stateful memory
  // pressure or Prerender2 memory controls are disabled.
  int GetCurrentMemoryLimit() const;

  // Returns the baseline unscaled maximum capacity limit for `limit_group`.
  int GetMaxLimit(PrerenderLimitGroup limit_group) const;

  // Scales the baseline capacity limit of `limit_group` by the current memory
  // limit percentage.
  int GetScaledLimit(PrerenderLimitGroup limit_group) const;

  // Holds the PrerenderHostId of running PrerenderHost. Reset to an invalid
  // value when there's no running PrerenderHost. Tracks only the host id of
  // speculation rules triggers and ignores requests from embedder because
  // embedder requests are more urgent and we'd like to handle embedder
  // prerender independently from speculation rules requests.
  PrerenderHostId running_prerender_host_id_;

  // Holds the ids of upcoming prerender requests. The requests from embedder
  // trigger are prioritized and pushed to the front of the queue, while the
  // requests from the speculation rules are appended to the back. This may
  // contain ids of cancelled requests. You can identify cancelled requests by
  // checking if an id is in `prerender_host_by_id_`.
  base::circular_deque<PrerenderHostId> pending_prerenders_;

  // Hosts that are not reserved for activation yet. This map also includes the
  // hosts still waiting for their start.
  base::flat_map<PrerenderHostId, std::unique_ptr<PrerenderHost>>
      prerender_host_by_id_;

  // Holds the host IDs by arrival order for each PrerenderLimitGroup.
  std::array<base::circular_deque<PrerenderHostId>, 3>
      arrival_order_queue_by_limit_group_;

  // The host that is reserved for activation.
  std::unique_ptr<PrerenderHost> reserved_prerender_host_;

  // Handles that manage WebContents for prerendering in new tabs.
  base::flat_map<PrerenderHostId, std::unique_ptr<PrerenderNewTabHandle>>
      prerender_new_tab_handle_by_id_;

  // Hosts that are scheduled to be deleted asynchronously.
  // Design note: PrerenderHostRegistry should explicitly manage the hosts to be
  // deleted instead of depending on the deletion helpers like DeleteSoon() to
  // asynchronously destruct them before this instance is deleted. The helpers
  // could let the hosts and their FrameTrees outlive WebContentsImpl (the owner
  // of the registry) and results in UAF.
  std::vector<std::unique_ptr<PrerenderHost>> to_be_deleted_hosts_;

  // The list of hosts which are scheduled to be deleted when
  // `DeletePendingDeletionHosts` is called. This list is for avoiding
  // the PrerenderHost being deleted prematurely before IPC calls are completed.
  base::flat_map<PrerenderHostId, std::unique_ptr<PrerenderHost>>
      pending_deletion_hosts_;

  // PrerenderNewTabHandle that is scheduled to be deleted asynchronously. When
  // unload related events are dispatched, PrerenderNewTabHandle deletion needs
  // to be delayed until the dispatch of the events.
  std::unique_ptr<PrerenderNewTabHandle>
      pending_deletion_new_tab_prerender_handle_;

  // Starts running the timers when prerendering gets hidden.
  base::OneShotTimer timeout_timer_for_embedder_;
  base::OneShotTimer timeout_timer_for_speculation_rules_;
  // Only used for tests. This task runner is used for precise injection in
  // tests and for timing control.
  scoped_refptr<base::SingleThreadTaskRunner> timer_task_runner_for_testing_;

  // A pending cache-only load of a URL, used to identify whether there is an
  // entry for it in the HTTP cache.
  std::unique_ptr<network::SimpleURLLoader> http_cache_query_loader_;

  std::optional<base::MemoryConsumerRegistration> memory_consumer_registration_;

  bool is_starting_prerendering_ = false;

  base::ObserverList<Observer> observers_;

  // Decrements the reuse count for the initiator's process.
  void DecrementProcessReuseCount();

  // The number of prerender hosts which attempted to reuse the initiator's
  // process.
  int32_t process_reuse_count_ = 0;

  base::WeakPtrFactory<PrerenderHostRegistry> weak_factory_{this};
};

}  // namespace content

#endif  // CONTENT_BROWSER_PRELOADING_PRERENDER_PRERENDER_HOST_REGISTRY_H_