123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201 |
- // Copyright 2013 The Chromium Authors. All rights reserved.
- // Use of this source code is governed by a BSD-style license that can be
- // found in the LICENSE file.
- #include "base/substring_set_matcher/substring_set_matcher.h"
- #include <stddef.h>
- #include <set>
- #include <string>
- #include <vector>
- #include "testing/gmock/include/gmock/gmock.h"
- #include "testing/gtest/include/gtest/gtest.h"
- namespace base {
- namespace {
- void TestOnePattern(const std::string& test_string,
- const std::string& pattern,
- bool is_match) {
- std::string test = "TestOnePattern(" + test_string + ", " + pattern + ", " +
- (is_match ? "1" : "0") + ")";
- std::vector<MatcherStringPattern> patterns;
- patterns.emplace_back(pattern, 1);
- SubstringSetMatcher matcher;
- ASSERT_TRUE(matcher.Build(patterns));
- std::set<MatcherStringPattern::ID> matches;
- matcher.Match(test_string, &matches);
- size_t expected_matches = (is_match ? 1 : 0);
- EXPECT_EQ(expected_matches, matches.size()) << test;
- EXPECT_EQ(is_match, matches.find(1) != matches.end()) << test;
- }
- void TestTwoPatterns(const std::string& test_string,
- const std::string& pattern_1,
- const std::string& pattern_2,
- bool is_match_1,
- bool is_match_2) {
- std::string test = "TestTwoPatterns(" + test_string + ", " + pattern_1 +
- ", " + pattern_2 + ", " + (is_match_1 ? "1" : "0") + ", " +
- (is_match_2 ? "1" : "0") + ")";
- ASSERT_NE(pattern_1, pattern_2);
- MatcherStringPattern substring_pattern_1(pattern_1, 1);
- MatcherStringPattern substring_pattern_2(pattern_2, 2);
- // In order to make sure that the order in which patterns are registered
- // does not make any difference we try both permutations.
- for (int permutation = 0; permutation < 2; ++permutation) {
- std::vector<const MatcherStringPattern*> patterns;
- if (permutation == 0) {
- patterns.push_back(&substring_pattern_1);
- patterns.push_back(&substring_pattern_2);
- } else {
- patterns.push_back(&substring_pattern_2);
- patterns.push_back(&substring_pattern_1);
- }
- SubstringSetMatcher matcher;
- ASSERT_TRUE(matcher.Build(patterns));
- std::set<MatcherStringPattern::ID> matches;
- matcher.Match(test_string, &matches);
- size_t expected_matches = (is_match_1 ? 1 : 0) + (is_match_2 ? 1 : 0);
- EXPECT_EQ(expected_matches, matches.size()) << test;
- EXPECT_EQ(is_match_1, matches.find(1) != matches.end()) << test;
- EXPECT_EQ(is_match_2, matches.find(2) != matches.end()) << test;
- }
- }
- } // namespace
- TEST(SubstringSetMatcherTest, TestMatcher) {
- // Test overlapping patterns
- // String abcde
- // Pattern 1 bc
- // Pattern 2 cd
- TestTwoPatterns("abcde", "bc", "cd", true, true);
- if (HasFatalFailure())
- return;
- // Test subpatterns - part 1
- // String abcde
- // Pattern 1 bc
- // Pattern 2 b
- TestTwoPatterns("abcde", "bc", "b", true, true);
- if (HasFatalFailure())
- return;
- // Test subpatterns - part 2
- // String abcde
- // Pattern 1 bc
- // Pattern 2 c
- TestTwoPatterns("abcde", "bc", "c", true, true);
- if (HasFatalFailure())
- return;
- // Test identical matches
- // String abcde
- // Pattern 1 abcde
- TestOnePattern("abcde", "abcde", true);
- if (HasFatalFailure())
- return;
- // Test multiple matches
- // String aaaaa
- // Pattern 1 a
- TestOnePattern("abcde", "a", true);
- if (HasFatalFailure())
- return;
- // Test matches at beginning and end
- // String abcde
- // Pattern 1 ab
- // Pattern 2 de
- TestTwoPatterns("abcde", "ab", "de", true, true);
- if (HasFatalFailure())
- return;
- // Test non-match
- // String abcde
- // Pattern 1 fg
- TestOnePattern("abcde", "fg", false);
- if (HasFatalFailure())
- return;
- // Test empty pattern and too long pattern
- // String abcde
- // Pattern 1
- // Pattern 2 abcdef
- TestTwoPatterns("abcde", std::string(), "abcdef", true, false);
- if (HasFatalFailure())
- return;
- }
- TEST(SubstringSetMatcherTest, TestMatcher2) {
- MatcherStringPattern pattern_1("a", 1);
- MatcherStringPattern pattern_2("b", 2);
- MatcherStringPattern pattern_3("c", 3);
- std::vector<const MatcherStringPattern*> patterns = {&pattern_1, &pattern_2,
- &pattern_3};
- auto matcher = std::make_unique<SubstringSetMatcher>();
- ASSERT_TRUE(matcher->Build(patterns));
- std::set<MatcherStringPattern::ID> matches;
- matcher->Match("abd", &matches);
- EXPECT_EQ(2u, matches.size());
- EXPECT_TRUE(matches.end() != matches.find(1));
- EXPECT_TRUE(matches.end() != matches.find(2));
- patterns = {&pattern_1, &pattern_3};
- matcher = std::make_unique<SubstringSetMatcher>();
- ASSERT_TRUE(matcher->Build(patterns));
- matches.clear();
- matcher->Match("abd", &matches);
- EXPECT_EQ(1u, matches.size());
- EXPECT_TRUE(matches.end() != matches.find(1));
- EXPECT_TRUE(matches.end() == matches.find(2));
- matcher = std::make_unique<SubstringSetMatcher>();
- ASSERT_TRUE(matcher->Build(std::vector<const MatcherStringPattern*>()));
- EXPECT_TRUE(matcher->IsEmpty());
- }
- TEST(SubstringSetMatcherTest, TestMatcher3) {
- std::string text = "abcde";
- std::vector<MatcherStringPattern> patterns;
- int id = 0;
- // Add all substrings of this string, including empty string.
- patterns.emplace_back("", id++);
- for (size_t i = 0; i < text.length(); i++) {
- for (size_t j = i; j < text.length(); j++) {
- patterns.emplace_back(text.substr(i, j - i + 1), id++);
- }
- }
- SubstringSetMatcher matcher;
- matcher.Build(patterns);
- std::set<MatcherStringPattern::ID> matches;
- matcher.Match(text, &matches);
- EXPECT_EQ(patterns.size(), matches.size());
- for (const MatcherStringPattern& pattern : patterns) {
- EXPECT_TRUE(matches.find(pattern.id()) != matches.end())
- << pattern.pattern();
- }
- }
- TEST(SubstringSetMatcherTest, TestEmptyMatcher) {
- std::vector<MatcherStringPattern> patterns;
- SubstringSetMatcher matcher;
- matcher.Build(patterns);
- std::set<MatcherStringPattern::ID> matches;
- matcher.Match("abd", &matches);
- EXPECT_TRUE(matches.empty());
- EXPECT_TRUE(matcher.IsEmpty());
- }
- } // namespace base
|