history_fuzzy_provider_unittest.cc | Explore in Territory

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

#ifdef UNSAFE_BUFFERS_BUILD
// TODO(crbug.com/40285824): Remove this and convert code to safer constructs.
#pragma allow_unsafe_buffers
#endif

#include "components/omnibox/browser/history_fuzzy_provider.h"

#include <vector>

#include "base/logging.h"
#include "base/ranges/algorithm.h"
#include "testing/gtest/include/gtest/gtest.h"

namespace {

struct TestCase { … };

template <typename Container, typename Item>
void SwapRemoveElement(Container& container, const Item& item) { … }

// These operator implementations are for debugging.
std::ostream& operator<<(std::ostream& os, const fuzzy::Edit& edit) { … }

std::ostream& operator<<(std::ostream& os,
                         const fuzzy::Correction& correction) { … }

// Note: The `test_case` is destroyed in place as it is checked.
void VerifyTestCase(fuzzy::Node* node,
                    TestCase& test_case,
                    fuzzy::ToleranceSchedule tolerance_schedule) { … }

// Verifies a vector of `cases`, destroying them in the process.
void VerifyCases(fuzzy::Node* node, std::vector<TestCase>& cases) { … }

// This is just like `VerifyCases` but uses a specified `tolerance_schedule`
// for all cases instead of each TestCase `tolerance` value.
void VerifyCasesWithSchedule(fuzzy::Node* node,
                             std::vector<TestCase>& cases,
                             fuzzy::ToleranceSchedule tolerance_schedule) { … }

}  // namespace

class HistoryFuzzyProviderTest : public testing::Test { … };

TEST_F(HistoryFuzzyProviderTest, AlgorithmIsNotGreedy) { … }

TEST_F(HistoryFuzzyProviderTest, ReplacementWorksAnywhere) { … }

TEST_F(HistoryFuzzyProviderTest, InsertionWorksAnywhereExceptEnd) { … }

TEST_F(HistoryFuzzyProviderTest, DeletionWorksAnywhere) { … }

// This test ensures a preference for longer results when edit distances are
// equal. This isn't an absolute requirement, and some relevance or probability
// guidance might be better, but this simple heuristic avoids creating shorter
// substring corrections, for example both "was" and "wash".
TEST_F(HistoryFuzzyProviderTest, LongerResultsArePreferred) { … }

TEST_F(HistoryFuzzyProviderTest, EmptyTrieRespectsToleranceSchedule) { … }

TEST_F(HistoryFuzzyProviderTest, ToleranceScheduleIsEnforced) { … }

// This test ensures that transposition swaps two adjacent characters with
// a single operation at edit distance one. Only directly adjacent characters
// can be transposed and nonadjacent character swaps still require two edits.
TEST_F(HistoryFuzzyProviderTest, TransposeIsEditDistanceOne) { … }

// This test covers a subtlety in the algorithm. It ensures we don't take
// replacements at the same position of a previous insertion because we
// only want one of {I,1,e}~{R,0,t} (ler ter) | {R,0,e}~{I,0,t} (er ter).
TEST_F(HistoryFuzzyProviderTest, DoesNotProduceDuplicate) { … }

TEST_F(HistoryFuzzyProviderTest, NodesDeleteAndPreserveStructure) { … }

TEST_F(HistoryFuzzyProviderTest, NodesMaintainRelevanceTotalTerminalCount) { … }
chromium/components/omnibox/browser/history_fuzzy_provider_unittest.cc
