chromium/chrome/browser/predictors/lcp_critical_path_predictor/lcp_critical_path_predictor_util.cc

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

#include "chrome/browser/predictors/lcp_critical_path_predictor/lcp_critical_path_predictor_util.h"

#include "base/containers/contains.h"
#include "base/metrics/histogram_functions.h"
#include "base/no_destructor.h"
#include "base/strings/string_split.h"
#include "base/strings/stringprintf.h"
#include "chrome/browser/predictors/resource_prefetch_predictor_tables.h"
#include "net/base/network_change_notifier.h"
#include "net/base/url_util.h"
#include "third_party/blink/public/common/features.h"
#include "url/origin.h"

namespace predictors {

namespace {
constexpr std::string_view kLcppTableName = …;
constexpr std::string_view kLcppTableNameInitiatorOrigin = …;
const char kCreateProtoTableStatementTemplate[] = …;

// Convert `LcppStringFrequencyStatData` a vector of frequency and std::string.
// The result is sorted with frequency (from high to low).
std::vector<std::pair<double, std::string>> ConvertToFrequencyStringPair(
    const LcppStringFrequencyStatData& data) { … }

// Returns true if the given `url` is a valid URL to be used as a key
// of `LcppStringFrequencyStatData`.
bool IsValidUrlInLcppStringFrequencyStatData(const std::string& url) { … }

// Returns LCP element locators in the past loads for a given `stat`.  The
// returned LCP element locators are ordered by descending frequency (the
// most frequent one comes first). If there is no data, it returns an empty
// vector.
std::vector<std::string> PredictLcpElementLocators(const LcppStat& stat) { … }

// Returns LCP influencer scripts from past loads for a given `stat`.
// The returned script urls are ordered by descending frequency (the most
// frequent one comes first). If there is no data, it returns an empty
// vector.
std::vector<GURL> PredictLcpInfluencerScripts(const LcppStat& stat) { … }

double SumOfFrequency(const std::map<std::string, double>& histogram,
                      double other_bucket_frequency) { … }

// This class implements the algorithm to update the
// `LcppStringFrequencyStatData` with given entries.
//
// The class is used in three steps.
// 1. Instantiate.
// 2. Update (You can repeat this step if there is multiple inputs).
// 3. Extract.
// e.g.
// ```
// // Instantiate.
// LcppFrequencyStatDataUpdater updater =
// LcppFrequencyStatDataUpdater::FromLcppStringFrequencyStatData(
//    sliding_window_size, max_histogram_buckets,
//    *stat.mutable_lcp_script_url_stat());
// // Update.
// updater.Update(url);
// // Extract.
// *stat.mutable_lcp_script_url_stat() =
//     updater.ToLcppStringFrequencyStatData();
// ```
//
// The algorithm takes two parameters:
// - sliding_window_size
// - max_histogram_buckets
//
// `sliding_window_size` is a virtual sliding window size that builds
// histogram.
// `max_histogram_buckets` is a bucket count that actually can be saved
// in the database. If the histogram has more buckets than
// `max_histogram_buckets`, this algorithm sums up the less frequent
// buckets, and stores them in a single "other_bucket" called
// `other_bucket_frequency`.
//
// <Conceptual model of sliding window and histogram>
//
// <------ sliding window ------->
// +-----------------------------+                 <- data feed
// | /#a   /#a   /#a   /#b   /#b | /#b   /#c   /#d   /#c   /#d
// +-----------------------------+
//  => histogram: {/#a: 3, /#b: 2}
//
//       <------ sliding window ------->
//       +-----------------------------+
//   /#a | /#a   /#a   /#b   /#b   /#b | /#c   /#d   /#c   /#d
//       +-----------------------------+
//        => histogram: {/#a: 2, /#b: 3}
//
//             <------ sliding window ------->
//             +-----------------------------+
//   /#a   /#a | /#a   /#b   /#b   /#b   /#c | /#d   /#c   /#d
//             +-----------------------------+
//              => histogram: {/#a: 1, /#b: 3, /#c: 1}
//
// The above sliding window model has the following two problems for us.
//
// - [Problem_1] We need to keep the entire data inside the sliding
//               window to know which item is the first item inside
//               the sliding window. But we don't want to keep such
//               large data.
// - [Problem_2] The histogram can be large if the items don't have
//               overlap. We don't want to keep a large histogram.
//
// To address [Problem_1], we decided not to use the first item
// inside the sliding window. Instead, We decided to reduce the
// weight of the item.
//
// histogram: {/#a: 3, /#b: 2}
// => histogram: {/#a: {1, 1, 1}, /#b: {1, 1}}
//
// To add new item "/#c", Reduce the item weight, and add "/#c".
//
// histogram: {/#a: {4/5, 4/5, 4/5}, /#b: {4/5, 4/5}, /#c: {1}}
//
// To address [Problem_2], we decided to introduce an "others"
// bucket.
//
// histogram: {/#a: 5, /#b: 3, /#c: 2, /#d: 2}
//
// To reduce the bucket count under 3 buckets, we merge /#c and /#d
// buckets into an <other> bucket.
//
// histogram: {/#a: 5, /#b: 3, <other>: 4}
//
// For more information, please see:
// https://docs.google.com/document/d/1T80d4xW8xIEqfo792g1nC1deFqzMraunFJW_5ft4ziQ/edit
class LcppFrequencyStatDataUpdater { … };

bool RecordLcpElementLocatorHistogram(const LoadingPredictorConfig& config,
                                      const std::string& lcp_element_locator,
                                      LcppStat& stat) { … }

bool RecordLcpInfluencerScriptUrlsHistogram(
    const LoadingPredictorConfig& config,
    const std::vector<GURL>& lcp_influencer_scripts,
    LcppStat& stat) { … }

bool RecordPreconnectOriginsHistogram(const LoadingPredictorConfig& config,
                                      const std::vector<GURL>& origins,
                                      LcppStat& stat) { … }

bool RecordFetchedFontUrlsHistogram(const LoadingPredictorConfig& config,
                                    const std::vector<GURL>& fetched_font_urls,
                                    LcppStat& stat) { … }

bool RecordFetchedSubresourceUrlsHistogram(
    const LoadingPredictorConfig& config,
    const std::map<GURL, base::TimeDelta>& fetched_subresource_urls,
    LcppStat& stat) { … }

bool IsValidLcpElementLocatorHistogram(
    const LcpElementLocatorStat& lcp_element_locator_stat) { … }

bool RecordUnusedPreloadUrlsHistogram(const LoadingPredictorConfig& config,
                                      const std::vector<GURL>& unused_preloads,
                                      LcppStat& stat) { … }

bool IsValidLcpUrlsHistogram(
    const LcppStringFrequencyStatData& lcpp_stat_data) { … }

size_t GetLCPPMultipleKeyMaxPathLength() { … }

bool IsKeyLengthValidForMultipleKey(const std::string& host,
                                    const std::string& first_level_path) { … }

bool IsLcppMultipleKeyKeyStatEnabled() { … }

std::string GetLCPPDatabaseKey(const GURL& url) { … }

// Returns LcppStat from `data` for LcppMultipleKeyKeyStat.
// This function can modify `data` to emplace new LcppStat. `data_updated` is
// true on the case and the caller should update the stored data.
// This can return nullptr based on the FrequencyStatData of `data`.
LcppStat* TryToGetLcppStatForKeyStat(const LoadingPredictorConfig& config,
                                     const GURL& url,
                                     LcppData& data,
                                     bool& data_updated) { … }

bool IsLCPPFontPrefetchExcludedHost(const GURL& url) { … }

class FakeLoadingPredictorKeyValueTable
    : public sqlite_proto::KeyValueTable<LcppData> { … };

bool EnsureTable(sql::Database* db, const std::string_view& table_name) { … }

bool IsInitiatorOriginEnabled() { … }

void DeleteTables(std::unique_ptr<LcppDataMap::DataTable> data_table,
                  std::unique_ptr<LcppDataMap::OriginTable> origin_table) { … }

}  // namespace

std::optional<blink::mojom::LCPCriticalPathPredictorNavigationTimeHint>
ConvertLcppStatToLCPCriticalPathPredictorNavigationTimeHint(
    const LcppStat& lcpp_stat) { … }

std::vector<GURL> PredictFetchedFontUrls(const LcppStat& stat) { … }

std::vector<GURL> PredictPreconnectableOrigins(const LcppStat& stat) { … }

std::vector<GURL> PredictFetchedSubresourceUrls(const LcppStat& stat) { … }

std::vector<GURL> PredictUnusedPreloads(const LcppStat& stat) { … }

LcppDataInputs::LcppDataInputs() = default;
LcppDataInputs::~LcppDataInputs() = default;

bool UpdateLcppStatWithLcppDataInputs(const LoadingPredictorConfig& config,
                                      const LcppDataInputs& inputs,
                                      LcppStat& stat) { … }

void UpdateLcppStringFrequencyStatData(
    size_t sliding_window_size,
    size_t max_histogram_buckets,
    const std::string& new_entry,
    LcppStringFrequencyStatData& lcpp_stat_data,
    std::optional<std::string>& dropped_entry) { … }

bool IsValidLcppStat(const LcppStat& lcpp_stat) { … }

bool IsURLValidForLcpp(const GURL& url) { … }

std::string GetFirstLevelPath(const GURL& url) { … }

LcppDataMap::LcppDataMap(scoped_refptr<sqlite_proto::TableManager> manager,
                         const LoadingPredictorConfig& config)
    : … { … }

LcppDataMap::LcppDataMap(scoped_refptr<sqlite_proto::TableManager> manager,
                         const LoadingPredictorConfig& config,
                         std::unique_ptr<DataTable> data_table)
    : … { … }

std::unique_ptr<LcppDataMap> LcppDataMap::CreateWithMockTableForTesting(
    scoped_refptr<sqlite_proto::TableManager> manager,
    const LoadingPredictorConfig& config) { … }

LcppDataMap::~LcppDataMap() { … }

void LcppDataMap::InitializeOnDBSequence() { … }

void LcppDataMap::InitializeAfterDBInitialization() { … }

// Record LCP element locators after a page has finished loading and LCP has
// been determined.
bool LcppDataMap::LearnLcpp(const std::optional<url::Origin>& initiator_origin,
                            const GURL& url,
                            const LcppDataInputs& inputs) { … }

// Returns LcppStat for the `url`, or std::nullopt on failure.
std::optional<LcppStat> LcppDataMap::GetLcppStat(
    const std::optional<url::Origin>& initiator_origin,
    const GURL& url) const { … }

void LcppDataMap::DeleteUrls(const std::vector<GURL>& urls) { … }

void LcppDataMap::DeleteAllData() { … }

const std::map<std::string, LcppData>& LcppDataMap::GetAllCachedForTesting() { … }
const std::map<std::string, LcppOrigin>&
LcppDataMap::GetAllCachedOriginForTesting() { … }

bool LcppDataMap::CreateOrClearTablesIfNecessary(sql::Database* db) { … }

}  // namespace predictors