net/http/no_vary_search_cache.h - chromium/src - Git at Google

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

 #ifndef NET_HTTP_NO_VARY_SEARCH_CACHE_H_
 #define NET_HTTP_NO_VARY_SEARCH_CACHE_H_

 #include <stddef.h>

 #include <compare>
 #include <map>
 #include <optional>
 #include <string>
 #include <string_view>
 #include <tuple>
 #include <utility>
 #include <vector>

 #include "base/containers/linked_list.h"
 #include "base/functional/function_ref.h"
 #include "base/memory/raw_ptr.h"
 #include "base/memory/stack_allocated.h"
 #include "base/memory/weak_ptr.h"
 #include "base/types/strong_alias.h"
 #include "net/base/does_url_match_filter.h"
 #include "net/base/net_export.h"
 #include "net/base/pickle_traits.h"
 #include "net/http/http_no_vary_search_data.h"
 #include "net/http/http_request_info.h"
 #include "url/gurl.h"

 namespace base {
 class Time;
 }

 namespace net {

 class HttpResponseHeaders;

 // An in-memory cache that permits looking up a URL and seeing if it matches a
 // previous response according to the rules of the No-Vary-Search header (see
 // https://httpwg.org/http-extensions/draft-ietf-httpbis-no-vary-search.html).
 // See also the design doc at
 // https://docs.google.com/document/d/1RS3q6qZ7-k9CvZsDYseGOXzcdQ9fGZ6YYnaW7fTPu7A/edit
 //
 // Owned by net::HttpCache.
 //
 // Ignoring eviction, the data structure is approximately equivalent to
 // std::map<std::pair<BaseURLCacheKey, HttpNoVarySearchData>,
 //          std::list<QueryString>>.
 //
 // BaseURLCacheKey is the output of the HttpCache key algorithm run on the base
 // URL (everything before the "?"). So it incorporates the NetworkIsolationKey
 // when split cache is enabled.
 class NET_EXPORT_PRIVATE NoVarySearchCache {
  private:
   // Declared here so that it can be mentioned in the definition of EraseHandle.
   class QueryString;

  public:
   // Opaque object that permits erasure of an item from the cache.
   // See comments on the Lookup() and Erase() methods for usage.
   class NET_EXPORT_PRIVATE EraseHandle {
    public:
     ~EraseHandle();

     // Not copyable.
     EraseHandle(const EraseHandle&) = delete;
     EraseHandle& operator=(const EraseHandle&) = delete;

     // Movable.
     EraseHandle(EraseHandle&& rhs);
     EraseHandle& operator=(EraseHandle&& rhs);

     // For unit tests it is useful to be able to inspect this.
     bool EqualsForTesting(const EraseHandle& rhs) const;
     bool IsGoneForTesting() const;

    private:
     friend class NoVarySearchCache;
     friend class QueryString;

     explicit EraseHandle(base::WeakPtr<QueryString> query_string);

     base::WeakPtr<QueryString> query_string_;
   };

   // An interface for receiving notifications about changes to the
   // NoVarySearchCache. Only insertions and refreshes via MaybeInsert() and
   // erasures via Erase() are reported to this interface. Evictions are
   // implicit, and modifications via ClearData() are expected to be followed by
   // persisting a fresh copy of the database.
   class NET_EXPORT_PRIVATE Journal {
    public:
     Journal() = default;

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

     // Called when an entry is inserted or refreshed by the MaybeInsert()
     // method. Not called when MaybeInsert() results in no changes to the
     // database. Also called by MergeFrom() for each merged entry.
     virtual void OnInsert(const std::string& base_url_cache_key,
                           const HttpNoVarySearchData& nvs_data,
                           const std::optional<std::string>& query,
                           base::Time update_time) = 0;

     // Called when an entry is erased by the Erase() method.
     virtual void OnErase(const std::string& base_url_cache_key,
                          const HttpNoVarySearchData& nvs_data,
                          const std::optional<std::string>& query) = 0;

    protected:
     // Journal objects are never deleted via a base class pointer.
     virtual ~Journal();
   };

   struct LookupResult {
     GURL original_url;
     EraseHandle erase_handle;
   };

   // The cache will hold at most `max_size` entries. Each entry stores the query
   // parameter from a previous response, which will typically be 100 to 200
   // bytes.
   explicit NoVarySearchCache(size_t max_size);

   // Move-constructible to permit deserialization and passing between threads.
   NoVarySearchCache(NoVarySearchCache&&);

   // Not copyable or assignable.
   NoVarySearchCache(const NoVarySearchCache&) = delete;
   NoVarySearchCache& operator=(const NoVarySearchCache&) = delete;
   NoVarySearchCache& operator=(NoVarySearchCache&&) = delete;

   ~NoVarySearchCache();

   // Finds an entry in the cache equivalent to `request.url` and in the same
   // cache partition. If a result is returned, then `original_url` can be used
   // to find a disk cache entry. `erase_handle` can be used to remove the entry
   // from this cache if it was not in the disk cache. Not const because it
   // updates the LRU linked list to mark the entry as recently used.
   std::optional<LookupResult> Lookup(const HttpRequestInfo& request);

   // Inserts `url` into the cache if a non-default "No-Vary-Search" header was
   // found in `headers`. On insertion, will remove any existing matching entry
   // with the same No-Vary-Search header, as the older entry would never be
   // returned by Lookup() anyway. May evict the oldest entry in the cache to
   // avoid the size exceeding `max_size_`.
   void MaybeInsert(const HttpRequestInfo& request,
                    const HttpResponseHeaders& headers);

   // Synchronously deletes entries that match `origins` or `domains` with update
   // times equal or greater than `delete_begin` and less than `delete_end`.
   // Setting `filter_type` to UrlFilterType::kFalseIfMatching inverts the
   // meaning of `origins` and `domains` as with DoesURlMatchFilter(), but
   // doesn't affect the interpretation of `delete_begin` and `delete_end`.
   // In particular, ClearData(URLFilterType::kFalseIfMatching, {}, {},
   // base::Time(), base::Time::Max()) will delete everything. Returns `true` if
   // anything was removed.
   bool ClearData(UrlFilterType filter_type,
                  const base::flat_set<url::Origin>& origins,
                  const base::flat_set<std::string>& domains,
                  base::Time delete_begin,
                  base::Time delete_end);

   // Erases the entry referenced by `erase_handle` from the cache. Does
   // nothing if the entry no longer exists.
   void Erase(EraseHandle handle);

   // Set a Journal to be notified about subsequent changes to the cache. This
   // object does not take ownership of the Journal. Calling the method again
   // will replace the journal. The method can be called with nullptr to stop
   // being notified.
   void SetJournal(Journal* journal);

   // Adds the specified entry to the cache as if by MaybeInsert(), evicting an
   // older entry if the cache is full. The entry is treated as if newly used for
   // the purposes of eviction. For use when replaying journalled entries. The
   // arguments are expected to match a previous call to Journal::OnInsert()
   // from a different instance of NoVarySearchCache, but with the same settings
   // for cache partitioning. It can also be called with other valid arguments
   // for testing. If a valid base URL cannot be extracted from
   // `base_url_cache_key`, or `query` contains an invalid character, the call is
   // ignored. This will never happen if the arguments are unchanged from a call
   // to Journal::OnInsert() with the same partitioning. A valid base URL does
   // not contain a query or a fragment. Journal methods are not called.
   void ReplayInsert(std::string base_url_cache_key,
                     HttpNoVarySearchData nvs_data,
                     std::optional<std::string> query,
                     base::Time update_time);

   // Removes the specified entry from the cache as if by Erase(). For use when
   // replaying journalled entries. The arguments are expected to match a
   // previous call to Journal::OnErase from a different instance of
   // NoVarySearchCache, with the same settings for cache partitioning
   // base::Features. If `query` is not found the call silently
   // does nothing. Journal methods are not called.
   void ReplayErase(const std::string& base_url_cache_key,
                    const HttpNoVarySearchData& nvs_data,
                    const std::optional<std::string>& query);

   // Merge entries from `newer` in order from the least-recently-used to the
   // most-recently-used, treating them as newly used. Less recently-used entries
   // will be evicted if necessary to avoid exceeding the maximum size.
   // Journal::OnInsert() is called as if the entries were newly inserted (but
   // with the original update_time).
   void MergeFrom(const NoVarySearchCache& newer);

   // Returns the size (number of stored original query strings) of the cache.
   size_t size() const { return size_; }

   // Return the maximum size for the cache. Attempting to add more than this
   // many entries will result in older entries being evicted.
   size_t max_size() const { return max_size_; }

   // Returns true if the top-level map is empty. This should be equivalent to
   // size() == 0 in the absence of bugs.
   bool IsTopLevelMapEmptyForTesting() const;

  private:
   friend struct PickleTraits<NoVarySearchCache>;

   struct QueryStringList;
   friend struct PickleTraits<NoVarySearchCache::QueryStringList>;

   using BaseURLCacheKey =
       base::StrongAlias<struct BaseURLCacheKeyTagType, std::string>;
   friend struct PickleTraits<NoVarySearchCache::BaseURLCacheKey>;

   class LruNode;
   class QueryStringListNode;

   struct QueryStringList {
     base::LinkedList<QueryStringListNode> list;
     // nvs_data_ref can't be raw_ref because it needs to be lazily initialized
     // after the QueryStringList has been added to the map.
     raw_ptr<const HttpNoVarySearchData> nvs_data_ref = nullptr;

     // key_ref can't be raw_ref because it needs to be added in a second pass
     // during deserialization.
     raw_ptr<const BaseURLCacheKey> key_ref = nullptr;

     // The referent of this reference has to be the actual key in the map. It is
     // not sufficient for the value to match, because the lifetime has to be the
     // same.
     explicit QueryStringList(const BaseURLCacheKey& key);

     // Needed during deserialization.
     QueryStringList();

     // Only used during deserialization. This is O(N) in the size of `list`.
     QueryStringList(QueryStringList&&);

     // base::LinkedList<> does not do memory management, so make sure the
     // contents of `list` are deleted on destruction.
     ~QueryStringList();
   };

   struct FindQueryStringResult {
     STACK_ALLOCATED();  // `match` doesn't need to be raw_ptr.

    public:
     QueryString* match;
     GURL original_url;
   };

   // TODO(crbug.com/382394774): Investigate performance of different map types.
   using DataMapType = std::map<HttpNoVarySearchData, QueryStringList>;
   using OuterMapType = std::map<BaseURLCacheKey, DataMapType, std::less<>>;

   // Erases an entry from the cache if `size_ > max_size_`.
   void EvictIfOverfull();

   // Erases `query_string` from the cache.
   void EraseQuery(QueryString* query_string);

   // Inserts `query` or marks it as used in the cache. evicting an older entry
   // if necessary to make space. `journal` is notified if set.
   void DoInsert(const GURL& url,
                 const GURL& base_url,
                 std::string base_url_cache_key,
                 HttpNoVarySearchData nvs_data,
                 std::optional<std::string_view> query,
                 base::Time update_time,
                 Journal* journal);

   // A convenience method for callers that do not have the original URL handy.
   // Reconstructs the original URL and then calls DoInsert().
   void ReconstructURLAndDoInsert(const GURL& base_url,
                                  std::string base_url_cache_key,
                                  HttpNoVarySearchData nvs_data,
                                  std::optional<std::string> query,
                                  base::Time update_time,
                                  Journal* journal);

   // Scans all the QueryStrings in `data_map` to find ones in the range
   // [delete_begin, delete_end) and appends them to `matches`. `data_map` is
   // mutable to reflect that it is returning mutable pointers to QueryString
   // objects that it owns. The returned QueryString objects are mutable so the
   // caller can erase them.
   static void FindQueryStringsInTimeRange(DataMapType& data_map,
                                           base::Time delete_begin,
                                           base::Time delete_end,
                                           std::vector<QueryString*>& matches);

   static std::optional<FindQueryStringResult> FindQueryStringInList(
       QueryStringList& query_strings,
       const GURL& base,
       const GURL& url,
       const HttpNoVarySearchData& nvs_data);

   // Calls f(query_string_ptr) for every QueryString in `list`.
   static void ForEachQueryString(base::LinkedList<QueryStringListNode>& list,
                                  base::FunctionRef<void(QueryString*)> f);

   // Calls f(const_query_string_ptr) for every QueryString in `list`.
   static void ForEachQueryString(
       const base::LinkedList<QueryStringListNode>& list,
       base::FunctionRef<void(const QueryString*)> f);

   // The main cache data structure.
   OuterMapType map_;

   // lru_.tail() is the least-recently-used QueryString.
   base::LinkedList<LruNode> lru_;

   // The number of QueryString objects in the cache.
   size_t size_ = 0u;

   // QueryString objects will be evicted to avoid exceeding `max_size_`.
   const size_t max_size_;

   // An object to be notified about changes to this cache.
   raw_ptr<Journal> journal_ = nullptr;
 };

 template <>
 struct NET_EXPORT_PRIVATE PickleTraits<NoVarySearchCache> {
   static void Serialize(base::Pickle& pickle, const NoVarySearchCache& cache);

   static std::optional<NoVarySearchCache> Deserialize(
       base::PickleIterator& iter);

   static size_t PickleSize(const NoVarySearchCache& cache);
 };

 }  // namespace net

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

	#ifndef NET_HTTP_NO_VARY_SEARCH_CACHE_H_
	#define NET_HTTP_NO_VARY_SEARCH_CACHE_H_

	#include <stddef.h>

	#include <compare>
	#include <map>
	#include <optional>
	#include <string>
	#include <string_view>
	#include <tuple>
	#include <utility>
	#include <vector>

	#include "base/containers/linked_list.h"
	#include "base/functional/function_ref.h"
	#include "base/memory/raw_ptr.h"
	#include "base/memory/stack_allocated.h"
	#include "base/memory/weak_ptr.h"
	#include "base/types/strong_alias.h"
	#include "net/base/does_url_match_filter.h"
	#include "net/base/net_export.h"
	#include "net/base/pickle_traits.h"
	#include "net/http/http_no_vary_search_data.h"
	#include "net/http/http_request_info.h"
	#include "url/gurl.h"

	namespace base {
	class Time;
	}

	namespace net {

	class HttpResponseHeaders;

	// An in-memory cache that permits looking up a URL and seeing if it matches a
	// previous response according to the rules of the No-Vary-Search header (see
	// https://httpwg.org/http-extensions/draft-ietf-httpbis-no-vary-search.html).
	// See also the design doc at
	// https://docs.google.com/document/d/1RS3q6qZ7-k9CvZsDYseGOXzcdQ9fGZ6YYnaW7fTPu7A/edit
	//
	// Owned by net::HttpCache.
	//
	// Ignoring eviction, the data structure is approximately equivalent to
	// std::map<std::pair<BaseURLCacheKey, HttpNoVarySearchData>,
	// std::list<QueryString>>.
	//
	// BaseURLCacheKey is the output of the HttpCache key algorithm run on the base
	// URL (everything before the "?"). So it incorporates the NetworkIsolationKey
	// when split cache is enabled.
	class NET_EXPORT_PRIVATE NoVarySearchCache {
	private:
	// Declared here so that it can be mentioned in the definition of EraseHandle.
	class QueryString;

	public:
	// Opaque object that permits erasure of an item from the cache.
	// See comments on the Lookup() and Erase() methods for usage.
	class NET_EXPORT_PRIVATE EraseHandle {
	public:
	~EraseHandle();

	// Not copyable.
	EraseHandle(const EraseHandle&) = delete;
	EraseHandle& operator=(const EraseHandle&) = delete;

	// Movable.
	EraseHandle(EraseHandle&& rhs);
	EraseHandle& operator=(EraseHandle&& rhs);

	// For unit tests it is useful to be able to inspect this.
	bool EqualsForTesting(const EraseHandle& rhs) const;
	bool IsGoneForTesting() const;

	private:
	friend class NoVarySearchCache;
	friend class QueryString;

	explicit EraseHandle(base::WeakPtr<QueryString> query_string);

	base::WeakPtr<QueryString> query_string_;
	};

	// An interface for receiving notifications about changes to the
	// NoVarySearchCache. Only insertions and refreshes via MaybeInsert() and
	// erasures via Erase() are reported to this interface. Evictions are
	// implicit, and modifications via ClearData() are expected to be followed by
	// persisting a fresh copy of the database.
	class NET_EXPORT_PRIVATE Journal {
	public:
	Journal() = default;

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

	// Called when an entry is inserted or refreshed by the MaybeInsert()
	// method. Not called when MaybeInsert() results in no changes to the
	// database. Also called by MergeFrom() for each merged entry.
	virtual void OnInsert(const std::string& base_url_cache_key,
	const HttpNoVarySearchData& nvs_data,
	const std::optional<std::string>& query,
	base::Time update_time) = 0;

	// Called when an entry is erased by the Erase() method.
	virtual void OnErase(const std::string& base_url_cache_key,
	const HttpNoVarySearchData& nvs_data,
	const std::optional<std::string>& query) = 0;

	protected:
	// Journal objects are never deleted via a base class pointer.
	virtual ~Journal();
	};

	struct LookupResult {
	GURL original_url;
	EraseHandle erase_handle;
	};

	// The cache will hold at most `max_size` entries. Each entry stores the query
	// parameter from a previous response, which will typically be 100 to 200
	// bytes.
	explicit NoVarySearchCache(size_t max_size);

	// Move-constructible to permit deserialization and passing between threads.
	NoVarySearchCache(NoVarySearchCache&&);

	// Not copyable or assignable.
	NoVarySearchCache(const NoVarySearchCache&) = delete;
	NoVarySearchCache& operator=(const NoVarySearchCache&) = delete;
	NoVarySearchCache& operator=(NoVarySearchCache&&) = delete;

	~NoVarySearchCache();

	// Finds an entry in the cache equivalent to `request.url` and in the same
	// cache partition. If a result is returned, then `original_url` can be used
	// to find a disk cache entry. `erase_handle` can be used to remove the entry
	// from this cache if it was not in the disk cache. Not const because it
	// updates the LRU linked list to mark the entry as recently used.
	std::optional<LookupResult> Lookup(const HttpRequestInfo& request);

	// Inserts `url` into the cache if a non-default "No-Vary-Search" header was
	// found in `headers`. On insertion, will remove any existing matching entry
	// with the same No-Vary-Search header, as the older entry would never be
	// returned by Lookup() anyway. May evict the oldest entry in the cache to
	// avoid the size exceeding `max_size_`.
	void MaybeInsert(const HttpRequestInfo& request,
	const HttpResponseHeaders& headers);

	// Synchronously deletes entries that match `origins` or `domains` with update
	// times equal or greater than `delete_begin` and less than `delete_end`.
	// Setting `filter_type` to UrlFilterType::kFalseIfMatching inverts the
	// meaning of `origins` and `domains` as with DoesURlMatchFilter(), but
	// doesn't affect the interpretation of `delete_begin` and `delete_end`.
	// In particular, ClearData(URLFilterType::kFalseIfMatching, {}, {},
	// base::Time(), base::Time::Max()) will delete everything. Returns `true` if
	// anything was removed.
	bool ClearData(UrlFilterType filter_type,
	const base::flat_set<url::Origin>& origins,
	const base::flat_set<std::string>& domains,
	base::Time delete_begin,
	base::Time delete_end);

	// Erases the entry referenced by `erase_handle` from the cache. Does
	// nothing if the entry no longer exists.
	void Erase(EraseHandle handle);

	// Set a Journal to be notified about subsequent changes to the cache. This
	// object does not take ownership of the Journal. Calling the method again
	// will replace the journal. The method can be called with nullptr to stop
	// being notified.
	void SetJournal(Journal* journal);

	// Adds the specified entry to the cache as if by MaybeInsert(), evicting an
	// older entry if the cache is full. The entry is treated as if newly used for
	// the purposes of eviction. For use when replaying journalled entries. The
	// arguments are expected to match a previous call to Journal::OnInsert()
	// from a different instance of NoVarySearchCache, but with the same settings
	// for cache partitioning. It can also be called with other valid arguments
	// for testing. If a valid base URL cannot be extracted from
	// `base_url_cache_key`, or `query` contains an invalid character, the call is
	// ignored. This will never happen if the arguments are unchanged from a call
	// to Journal::OnInsert() with the same partitioning. A valid base URL does
	// not contain a query or a fragment. Journal methods are not called.
	void ReplayInsert(std::string base_url_cache_key,
	HttpNoVarySearchData nvs_data,
	std::optional<std::string> query,
	base::Time update_time);

	// Removes the specified entry from the cache as if by Erase(). For use when
	// replaying journalled entries. The arguments are expected to match a
	// previous call to Journal::OnErase from a different instance of
	// NoVarySearchCache, with the same settings for cache partitioning
	// base::Features. If `query` is not found the call silently
	// does nothing. Journal methods are not called.
	void ReplayErase(const std::string& base_url_cache_key,
	const HttpNoVarySearchData& nvs_data,
	const std::optional<std::string>& query);

	// Merge entries from `newer` in order from the least-recently-used to the
	// most-recently-used, treating them as newly used. Less recently-used entries
	// will be evicted if necessary to avoid exceeding the maximum size.
	// Journal::OnInsert() is called as if the entries were newly inserted (but
	// with the original update_time).
	void MergeFrom(const NoVarySearchCache& newer);

	// Returns the size (number of stored original query strings) of the cache.
	size_t size() const { return size_; }

	// Return the maximum size for the cache. Attempting to add more than this
	// many entries will result in older entries being evicted.
	size_t max_size() const { return max_size_; }

	// Returns true if the top-level map is empty. This should be equivalent to
	// size() == 0 in the absence of bugs.
	bool IsTopLevelMapEmptyForTesting() const;

	private:
	friend struct PickleTraits<NoVarySearchCache>;

	struct QueryStringList;
	friend struct PickleTraits<NoVarySearchCache::QueryStringList>;

	using BaseURLCacheKey =
	base::StrongAlias<struct BaseURLCacheKeyTagType, std::string>;
	friend struct PickleTraits<NoVarySearchCache::BaseURLCacheKey>;

	class LruNode;
	class QueryStringListNode;

	struct QueryStringList {
	base::LinkedList<QueryStringListNode> list;
	// nvs_data_ref can't be raw_ref because it needs to be lazily initialized
	// after the QueryStringList has been added to the map.
	raw_ptr<const HttpNoVarySearchData> nvs_data_ref = nullptr;

	// key_ref can't be raw_ref because it needs to be added in a second pass
	// during deserialization.
	raw_ptr<const BaseURLCacheKey> key_ref = nullptr;

	// The referent of this reference has to be the actual key in the map. It is
	// not sufficient for the value to match, because the lifetime has to be the
	// same.
	explicit QueryStringList(const BaseURLCacheKey& key);

	// Needed during deserialization.
	QueryStringList();

	// Only used during deserialization. This is O(N) in the size of `list`.
	QueryStringList(QueryStringList&&);

	// base::LinkedList<> does not do memory management, so make sure the
	// contents of `list` are deleted on destruction.
	~QueryStringList();
	};

	struct FindQueryStringResult {
	STACK_ALLOCATED(); // `match` doesn't need to be raw_ptr.

	public:
	QueryString* match;
	GURL original_url;
	};

	// TODO(crbug.com/382394774): Investigate performance of different map types.
	using DataMapType = std::map<HttpNoVarySearchData, QueryStringList>;
	using OuterMapType = std::map<BaseURLCacheKey, DataMapType, std::less<>>;

	// Erases an entry from the cache if `size_ > max_size_`.
	void EvictIfOverfull();

	// Erases `query_string` from the cache.
	void EraseQuery(QueryString* query_string);

	// Inserts `query` or marks it as used in the cache. evicting an older entry
	// if necessary to make space. `journal` is notified if set.
	void DoInsert(const GURL& url,
	const GURL& base_url,
	std::string base_url_cache_key,
	HttpNoVarySearchData nvs_data,
	std::optional<std::string_view> query,
	base::Time update_time,
	Journal* journal);

	// A convenience method for callers that do not have the original URL handy.
	// Reconstructs the original URL and then calls DoInsert().
	void ReconstructURLAndDoInsert(const GURL& base_url,
	std::string base_url_cache_key,
	HttpNoVarySearchData nvs_data,
	std::optional<std::string> query,
	base::Time update_time,
	Journal* journal);

	// Scans all the QueryStrings in `data_map` to find ones in the range
	// [delete_begin, delete_end) and appends them to `matches`. `data_map` is
	// mutable to reflect that it is returning mutable pointers to QueryString
	// objects that it owns. The returned QueryString objects are mutable so the
	// caller can erase them.
	static void FindQueryStringsInTimeRange(DataMapType& data_map,
	base::Time delete_begin,
	base::Time delete_end,
	std::vector<QueryString*>& matches);

	static std::optional<FindQueryStringResult> FindQueryStringInList(
	QueryStringList& query_strings,
	const GURL& base,
	const GURL& url,
	const HttpNoVarySearchData& nvs_data);

	// Calls f(query_string_ptr) for every QueryString in `list`.
	static void ForEachQueryString(base::LinkedList<QueryStringListNode>& list,
	base::FunctionRef<void(QueryString*)> f);

	// Calls f(const_query_string_ptr) for every QueryString in `list`.
	static void ForEachQueryString(
	const base::LinkedList<QueryStringListNode>& list,
	base::FunctionRef<void(const QueryString*)> f);

	// The main cache data structure.
	OuterMapType map_;

	// lru_.tail() is the least-recently-used QueryString.
	base::LinkedList<LruNode> lru_;

	// The number of QueryString objects in the cache.
	size_t size_ = 0u;

	// QueryString objects will be evicted to avoid exceeding `max_size_`.
	const size_t max_size_;

	// An object to be notified about changes to this cache.
	raw_ptr<Journal> journal_ = nullptr;
	};

	template <>
	struct NET_EXPORT_PRIVATE PickleTraits<NoVarySearchCache> {
	static void Serialize(base::Pickle& pickle, const NoVarySearchCache& cache);

	static std::optional<NoVarySearchCache> Deserialize(
	base::PickleIterator& iter);

	static size_t PickleSize(const NoVarySearchCache& cache);
	};

	} // namespace net

	#endif // NET_HTTP_NO_VARY_SEARCH_CACHE_H_