fuzzy_pattern_matching_unittest.cc 3.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108
  1. // Copyright 2016 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #include "components/url_pattern_index/fuzzy_pattern_matching.h"
  5. #include <vector>
  6. #include "testing/gtest/include/gtest/gtest.h"
  7. namespace url_pattern_index {
  8. TEST(SubresourceFilterFuzzyPatternMatchingTest, StartsWithFuzzy) {
  9. const struct {
  10. const char* text;
  11. const char* subpattern;
  12. bool expected_starts_with;
  13. } kTestCases[] = {
  14. {"abc", "", true}, {"abc", "a", true}, {"abc", "ab", true},
  15. {"abc", "abc", true}, {"abc", "abcd", false}, {"abc", "abc^^", false},
  16. {"abc", "abcd^", false}, {"abc", "ab^", false}, {"abc", "bc", false},
  17. {"abc", "bc^", false}, {"abc", "^abc", false},
  18. };
  19. // TODO(pkalinnikov): Make end-of-string match '^' again.
  20. for (const auto& test_case : kTestCases) {
  21. SCOPED_TRACE(testing::Message()
  22. << "Test: " << test_case.text
  23. << "; Subpattern: " << test_case.subpattern);
  24. const bool starts_with =
  25. StartsWithFuzzy(test_case.text, test_case.subpattern);
  26. EXPECT_EQ(test_case.expected_starts_with, starts_with);
  27. }
  28. }
  29. TEST(SubresourceFilterFuzzyPatternMatchingTest, EndsWithFuzzy) {
  30. const struct {
  31. const char* text;
  32. const char* subpattern;
  33. bool expected_ends_with;
  34. } kTestCases[] = {
  35. {"abc", "", true}, {"abc", "c", true}, {"abc", "bc", true},
  36. {"abc", "abc", true}, {"abc", "0abc", false}, {"abc", "abc^^", false},
  37. {"abc", "abcd^", false}, {"abc", "ab^", false}, {"abc", "ab", false},
  38. {"abc", "^abc", false},
  39. };
  40. // TODO(pkalinnikov): Make end-of-string match '^' again.
  41. for (const auto& test_case : kTestCases) {
  42. SCOPED_TRACE(testing::Message()
  43. << "Test: " << test_case.text
  44. << "; Subpattern: " << test_case.subpattern);
  45. const bool ends_with = EndsWithFuzzy(test_case.text, test_case.subpattern);
  46. EXPECT_EQ(test_case.expected_ends_with, ends_with);
  47. }
  48. }
  49. TEST(SubresourceFilterFuzzyPatternMatchingTest, FindFuzzy) {
  50. const struct {
  51. base::StringPiece text;
  52. base::StringPiece subpattern;
  53. std::vector<size_t> expected_occurrences;
  54. } kTestCases[] = {
  55. {"abcd", "", {0, 1, 2, 3, 4}},
  56. {"abcd", "de", std::vector<size_t>()},
  57. {"abcd", "ab", {0}},
  58. {"abcd", "bc", {1}},
  59. {"abcd", "cd", {2}},
  60. {"a/bc/a/b", "", {0, 1, 2, 3, 4, 5, 6, 7, 8}},
  61. {"a/bc/a/b", "de", std::vector<size_t>()},
  62. {"a/bc/a/b", "a/", {0, 5}},
  63. {"a/bc/a/c", "a/c", {5}},
  64. {"a/bc/a/c", "a^c", {5}},
  65. {"a/bc/a/c", "a?c", std::vector<size_t>()},
  66. {"ab^cd", "ab/cd", std::vector<size_t>()},
  67. {"ab^cd", "b/c", std::vector<size_t>()},
  68. {"ab^cd", "ab^cd", {0}},
  69. {"ab^cd", "b^c", {1}},
  70. {"ab^b/b", "b/b", {3}},
  71. {"a/a/a/a", "a/a", {0, 2, 4}},
  72. {"a/a/a/a", "^a^a^a", {1}},
  73. {"a/a/a/a", "^a^a?a", std::vector<size_t>()},
  74. {"a/a/a/a", "?a?a?a", std::vector<size_t>()},
  75. };
  76. for (const auto& test_case : kTestCases) {
  77. SCOPED_TRACE(testing::Message()
  78. << "Test: " << test_case.text
  79. << "; Subpattern: " << test_case.subpattern);
  80. std::vector<size_t> occurrences;
  81. for (size_t position = 0; position <= test_case.text.size(); ++position) {
  82. position = FindFuzzy(test_case.text, test_case.subpattern, position);
  83. if (position == base::StringPiece::npos)
  84. break;
  85. occurrences.push_back(position);
  86. }
  87. EXPECT_EQ(test_case.expected_occurrences, occurrences);
  88. }
  89. }
  90. } // namespace url_pattern_index