substring_set_matcher.cc 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493
  1. // Copyright 2013 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 "base/substring_set_matcher/substring_set_matcher.h"
  5. #include <stddef.h>
  6. #include <algorithm>
  7. #include <queue>
  8. #ifdef __SSE2__
  9. #include <immintrin.h>
  10. #include "base/bits.h"
  11. #endif
  12. #include "base/check_op.h"
  13. #include "base/containers/contains.h"
  14. #include "base/containers/queue.h"
  15. #include "base/numerics/checked_math.h"
  16. #include "base/trace_event/memory_usage_estimator.h" // no-presubmit-check
  17. namespace base {
  18. namespace {
  19. // Compare MatcherStringPattern instances based on their string patterns.
  20. bool ComparePatterns(const MatcherStringPattern* a,
  21. const MatcherStringPattern* b) {
  22. return a->pattern() < b->pattern();
  23. }
  24. std::vector<const MatcherStringPattern*> GetVectorOfPointers(
  25. const std::vector<MatcherStringPattern>& patterns) {
  26. std::vector<const MatcherStringPattern*> pattern_pointers;
  27. pattern_pointers.reserve(patterns.size());
  28. for (const MatcherStringPattern& pattern : patterns)
  29. pattern_pointers.push_back(&pattern);
  30. return pattern_pointers;
  31. }
  32. } // namespace
  33. bool SubstringSetMatcher::Build(
  34. const std::vector<MatcherStringPattern>& patterns) {
  35. return Build(GetVectorOfPointers(patterns));
  36. }
  37. bool SubstringSetMatcher::Build(
  38. std::vector<const MatcherStringPattern*> patterns) {
  39. // Ensure there are no duplicate IDs and all pattern strings are distinct.
  40. #if DCHECK_IS_ON()
  41. {
  42. std::set<MatcherStringPattern::ID> ids;
  43. std::set<std::string> pattern_strings;
  44. for (const MatcherStringPattern* pattern : patterns) {
  45. CHECK(!base::Contains(ids, pattern->id()));
  46. CHECK(!base::Contains(pattern_strings, pattern->pattern()));
  47. ids.insert(pattern->id());
  48. pattern_strings.insert(pattern->pattern());
  49. }
  50. }
  51. #endif
  52. // Check that all the match labels fit into an edge.
  53. for (const MatcherStringPattern* pattern : patterns) {
  54. if (pattern->id() >= kInvalidNodeID) {
  55. return false;
  56. }
  57. }
  58. // Compute the total number of tree nodes needed.
  59. std::sort(patterns.begin(), patterns.end(), ComparePatterns);
  60. NodeID tree_size = GetTreeSize(patterns);
  61. if (tree_size >= kInvalidNodeID) {
  62. return false;
  63. }
  64. tree_.reserve(GetTreeSize(patterns));
  65. BuildAhoCorasickTree(patterns);
  66. // Sanity check that no new allocations happened in the tree and our computed
  67. // size was correct.
  68. DCHECK_EQ(tree_.size(), static_cast<size_t>(GetTreeSize(patterns)));
  69. is_empty_ = patterns.empty() && tree_.size() == 1u;
  70. return true;
  71. }
  72. SubstringSetMatcher::~SubstringSetMatcher() = default;
  73. bool SubstringSetMatcher::Match(
  74. const std::string& text,
  75. std::set<MatcherStringPattern::ID>* matches) const {
  76. const size_t old_number_of_matches = matches->size();
  77. // Handle patterns matching the empty string.
  78. const AhoCorasickNode* const root = &tree_[kRootID];
  79. AccumulateMatchesForNode(root, matches);
  80. const AhoCorasickNode* current_node = root;
  81. for (const char c : text) {
  82. NodeID child = current_node->GetEdge(static_cast<unsigned char>(c));
  83. // If the child not can't be found, progressively iterate over the longest
  84. // proper suffix of the string represented by the current node. In a sense
  85. // we are pruning prefixes from the text.
  86. while (child == kInvalidNodeID && current_node != root) {
  87. current_node = &tree_[current_node->failure()];
  88. child = current_node->GetEdge(static_cast<unsigned char>(c));
  89. }
  90. if (child != kInvalidNodeID) {
  91. // The string represented by |child| is the longest possible suffix of the
  92. // current position of |text| in the trie.
  93. current_node = &tree_[child];
  94. AccumulateMatchesForNode(current_node, matches);
  95. } else {
  96. // The empty string is the longest possible suffix of the current position
  97. // of |text| in the trie.
  98. DCHECK_EQ(root, current_node);
  99. }
  100. }
  101. return old_number_of_matches != matches->size();
  102. }
  103. bool SubstringSetMatcher::AnyMatch(const std::string& text) const {
  104. // Handle patterns matching the empty string.
  105. const AhoCorasickNode* const root = &tree_[kRootID];
  106. if (root->has_outputs()) {
  107. return true;
  108. }
  109. const AhoCorasickNode* current_node = root;
  110. for (const char c : text) {
  111. NodeID child = current_node->GetEdge(static_cast<unsigned char>(c));
  112. // If the child not can't be found, progressively iterate over the longest
  113. // proper suffix of the string represented by the current node. In a sense
  114. // we are pruning prefixes from the text.
  115. while (child == kInvalidNodeID && current_node != root) {
  116. current_node = &tree_[current_node->failure()];
  117. child = current_node->GetEdge(static_cast<unsigned char>(c));
  118. }
  119. if (child != kInvalidNodeID) {
  120. // The string represented by |child| is the longest possible suffix of the
  121. // current position of |text| in the trie.
  122. current_node = &tree_[child];
  123. if (current_node->has_outputs()) {
  124. return true;
  125. }
  126. } else {
  127. // The empty string is the longest possible suffix of the current position
  128. // of |text| in the trie.
  129. DCHECK_EQ(root, current_node);
  130. }
  131. }
  132. return false;
  133. }
  134. size_t SubstringSetMatcher::EstimateMemoryUsage() const {
  135. return base::trace_event::EstimateMemoryUsage(tree_);
  136. }
  137. // static
  138. constexpr SubstringSetMatcher::NodeID SubstringSetMatcher::kInvalidNodeID;
  139. constexpr SubstringSetMatcher::NodeID SubstringSetMatcher::kRootID;
  140. SubstringSetMatcher::NodeID SubstringSetMatcher::GetTreeSize(
  141. const std::vector<const MatcherStringPattern*>& patterns) const {
  142. DCHECK(std::is_sorted(patterns.begin(), patterns.end(), ComparePatterns));
  143. base::CheckedNumeric<NodeID> result = 1u; // 1 for the root node.
  144. if (patterns.empty())
  145. return result.ValueOrDie();
  146. auto last = patterns.begin();
  147. auto current = last + 1;
  148. // For the first pattern, each letter is a label of an edge to a new node.
  149. result += (*last)->pattern().size();
  150. // For the subsequent patterns, only count the edges which were not counted
  151. // yet. For this it suffices to test against the previous pattern, because the
  152. // patterns are sorted.
  153. for (; current != patterns.end(); ++last, ++current) {
  154. const std::string& last_pattern = (*last)->pattern();
  155. const std::string& current_pattern = (*current)->pattern();
  156. size_t prefix_bound = std::min(last_pattern.size(), current_pattern.size());
  157. size_t common_prefix = 0;
  158. while (common_prefix < prefix_bound &&
  159. last_pattern[common_prefix] == current_pattern[common_prefix]) {
  160. ++common_prefix;
  161. }
  162. result -= common_prefix;
  163. result += current_pattern.size();
  164. }
  165. return result.ValueOrDie();
  166. }
  167. void SubstringSetMatcher::BuildAhoCorasickTree(
  168. const SubstringPatternVector& patterns) {
  169. DCHECK(tree_.empty());
  170. // Initialize root node of tree.
  171. tree_.emplace_back();
  172. // Build the initial trie for all the patterns.
  173. for (const MatcherStringPattern* pattern : patterns)
  174. InsertPatternIntoAhoCorasickTree(pattern);
  175. CreateFailureAndOutputEdges();
  176. }
  177. void SubstringSetMatcher::InsertPatternIntoAhoCorasickTree(
  178. const MatcherStringPattern* pattern) {
  179. const std::string& text = pattern->pattern();
  180. const std::string::const_iterator text_end = text.end();
  181. // Iterators on the tree and the text.
  182. AhoCorasickNode* current_node = &tree_[kRootID];
  183. std::string::const_iterator i = text.begin();
  184. // Follow existing paths for as long as possible.
  185. while (i != text_end) {
  186. NodeID child = current_node->GetEdge(static_cast<unsigned char>(*i));
  187. if (child == kInvalidNodeID)
  188. break;
  189. current_node = &tree_[child];
  190. ++i;
  191. }
  192. // Create new nodes if necessary.
  193. while (i != text_end) {
  194. tree_.emplace_back();
  195. current_node->SetEdge(static_cast<unsigned char>(*i),
  196. static_cast<NodeID>(tree_.size() - 1));
  197. current_node = &tree_.back();
  198. ++i;
  199. }
  200. // Register match.
  201. current_node->SetMatchID(pattern->id());
  202. }
  203. void SubstringSetMatcher::CreateFailureAndOutputEdges() {
  204. base::queue<AhoCorasickNode*> queue;
  205. // Initialize the failure edges for |root| and its children.
  206. AhoCorasickNode* const root = &tree_[0];
  207. root->SetOutputLink(kInvalidNodeID);
  208. NodeID root_output_link = root->IsEndOfPattern() ? kRootID : kInvalidNodeID;
  209. for (unsigned edge_idx = 0; edge_idx < root->num_edges(); ++edge_idx) {
  210. const AhoCorasickEdge& edge = root->edges()[edge_idx];
  211. if (edge.label >= kFirstSpecialLabel) {
  212. continue;
  213. }
  214. AhoCorasickNode* child = &tree_[edge.node_id];
  215. // Failure node is kept as the root.
  216. child->SetOutputLink(root_output_link);
  217. queue.push(child);
  218. }
  219. // Do a breadth first search over the trie to create failure edges. We
  220. // maintain the invariant that any node in |queue| has had its |failure_| and
  221. // |output_link_| edge already initialized.
  222. while (!queue.empty()) {
  223. AhoCorasickNode* current_node = queue.front();
  224. queue.pop();
  225. // Compute the failure and output edges of children using the failure edges
  226. // of the current node.
  227. for (unsigned edge_idx = 0; edge_idx < current_node->num_edges();
  228. ++edge_idx) {
  229. const AhoCorasickEdge& edge = current_node->edges()[edge_idx];
  230. if (edge.label >= kFirstSpecialLabel) {
  231. continue;
  232. }
  233. AhoCorasickNode* child = &tree_[edge.node_id];
  234. const AhoCorasickNode* failure_candidate_parent =
  235. &tree_[current_node->failure()];
  236. NodeID failure_candidate_id =
  237. failure_candidate_parent->GetEdge(edge.label);
  238. while (failure_candidate_id == kInvalidNodeID &&
  239. failure_candidate_parent != root) {
  240. failure_candidate_parent = &tree_[failure_candidate_parent->failure()];
  241. failure_candidate_id = failure_candidate_parent->GetEdge(edge.label);
  242. }
  243. if (failure_candidate_id == kInvalidNodeID) {
  244. DCHECK_EQ(root, failure_candidate_parent);
  245. // |failure_candidate| is invalid and we can't proceed further since we
  246. // have reached the root. Hence the longest proper suffix of this string
  247. // represented by this node is the empty string (represented by root).
  248. failure_candidate_id = kRootID;
  249. } else {
  250. child->SetFailure(failure_candidate_id);
  251. }
  252. const AhoCorasickNode* failure_candidate = &tree_[failure_candidate_id];
  253. // Now |failure_candidate| is |child|'s longest possible proper suffix in
  254. // the trie. We also know that since we are doing a breadth first search,
  255. // we would have established |failure_candidate|'s output link by now.
  256. // Hence we can define |child|'s output link as follows:
  257. child->SetOutputLink(failure_candidate->IsEndOfPattern()
  258. ? failure_candidate_id
  259. : failure_candidate->output_link());
  260. queue.push(child);
  261. }
  262. }
  263. }
  264. void SubstringSetMatcher::AccumulateMatchesForNode(
  265. const AhoCorasickNode* node,
  266. std::set<MatcherStringPattern::ID>* matches) const {
  267. DCHECK(matches);
  268. if (!node->has_outputs()) {
  269. // Fast reject.
  270. return;
  271. }
  272. if (node->IsEndOfPattern())
  273. matches->insert(node->GetMatchID());
  274. NodeID node_id = node->output_link();
  275. while (node_id != kInvalidNodeID) {
  276. node = &tree_[node_id];
  277. matches->insert(node->GetMatchID());
  278. node_id = node->output_link();
  279. }
  280. }
  281. SubstringSetMatcher::AhoCorasickNode::AhoCorasickNode() {
  282. static_assert(kNumInlineEdges == 2, "Code below needs updating");
  283. edges_.inline_edges[0].label = kEmptyLabel;
  284. edges_.inline_edges[1].label = kEmptyLabel;
  285. }
  286. SubstringSetMatcher::AhoCorasickNode::~AhoCorasickNode() {
  287. if (edges_capacity_ != 0) {
  288. delete[] edges_.edges;
  289. }
  290. }
  291. SubstringSetMatcher::AhoCorasickNode::AhoCorasickNode(AhoCorasickNode&& other) {
  292. *this = std::move(other);
  293. }
  294. SubstringSetMatcher::AhoCorasickNode&
  295. SubstringSetMatcher::AhoCorasickNode::operator=(AhoCorasickNode&& other) {
  296. if (edges_capacity_ != 0) {
  297. // Delete the old heap allocation if needed.
  298. delete[] edges_.edges;
  299. }
  300. if (other.edges_capacity_ == 0) {
  301. static_assert(kNumInlineEdges == 2, "Code below needs updating");
  302. edges_.inline_edges[0] = other.edges_.inline_edges[0];
  303. edges_.inline_edges[1] = other.edges_.inline_edges[1];
  304. } else {
  305. // Move over the heap allocation.
  306. edges_.edges = other.edges_.edges;
  307. other.edges_.edges = nullptr;
  308. }
  309. num_free_edges_ = other.num_free_edges_;
  310. edges_capacity_ = other.edges_capacity_;
  311. return *this;
  312. }
  313. SubstringSetMatcher::NodeID
  314. SubstringSetMatcher::AhoCorasickNode::GetEdgeNoInline(uint32_t label) const {
  315. DCHECK(edges_capacity_ != 0);
  316. #ifdef __SSE2__
  317. const __m128i lbl = _mm_set1_epi32(static_cast<int>(label));
  318. const __m128i mask = _mm_set1_epi32(0x1ff);
  319. for (unsigned edge_idx = 0; edge_idx < num_edges(); edge_idx += 4) {
  320. const __m128i four = _mm_loadu_si128(
  321. reinterpret_cast<const __m128i*>(&edges_.edges[edge_idx]));
  322. const __m128i match = _mm_cmpeq_epi32(_mm_and_si128(four, mask), lbl);
  323. const uint32_t match_mask = static_cast<uint32_t>(_mm_movemask_epi8(match));
  324. if (match_mask != 0) {
  325. if (match_mask & 0x1u) {
  326. return edges_.edges[edge_idx].node_id;
  327. }
  328. if (match_mask & 0x10u) {
  329. return edges_.edges[edge_idx + 1].node_id;
  330. }
  331. if (match_mask & 0x100u) {
  332. return edges_.edges[edge_idx + 2].node_id;
  333. }
  334. DCHECK(match_mask & 0x1000u);
  335. return edges_.edges[edge_idx + 3].node_id;
  336. }
  337. }
  338. #else
  339. for (unsigned edge_idx = 0; edge_idx < num_edges(); ++edge_idx) {
  340. const AhoCorasickEdge& edge = edges_.edges[edge_idx];
  341. if (edge.label == label)
  342. return edge.node_id;
  343. }
  344. #endif
  345. return kInvalidNodeID;
  346. }
  347. void SubstringSetMatcher::AhoCorasickNode::SetEdge(uint32_t label,
  348. NodeID node) {
  349. DCHECK_LT(node, kInvalidNodeID);
  350. #if DCHECK_IS_ON()
  351. // We don't support overwriting existing edges.
  352. for (unsigned edge_idx = 0; edge_idx < num_edges(); ++edge_idx) {
  353. DCHECK_NE(label, edges()[edge_idx].label);
  354. }
  355. #endif
  356. if (edges_capacity_ == 0 && num_free_edges_ > 0) {
  357. // Still space in the inline storage, so use that.
  358. edges_.inline_edges[num_edges()] = AhoCorasickEdge{label, node};
  359. if (label == kFailureNodeLabel) {
  360. // Make sure that kFailureNodeLabel is first.
  361. // NOTE: We don't use std::swap here, because the compiler doesn't
  362. // understand that inline_edges[] is 4-aligned and can give
  363. // a warning or error.
  364. AhoCorasickEdge temp = edges_.inline_edges[0];
  365. edges_.inline_edges[0] = edges_.inline_edges[num_edges()];
  366. edges_.inline_edges[num_edges()] = temp;
  367. }
  368. --num_free_edges_;
  369. return;
  370. }
  371. if (num_free_edges_ == 0) {
  372. // We are out of space, so double our capacity. This can either be
  373. // because we are converting from inline to heap storage, or because
  374. // we are increasing the size of our heap storage.
  375. unsigned old_capacity =
  376. edges_capacity_ == 0 ? kNumInlineEdges : edges_capacity_;
  377. unsigned new_capacity = old_capacity * 2;
  378. DCHECK_EQ(0u, new_capacity % 4);
  379. // TODO(pkasting): The header claims this condition holds, but I don't
  380. // understand why. If you do, please comment.
  381. DCHECK_LE(new_capacity, kEmptyLabel + 1);
  382. AhoCorasickEdge* new_edges = new AhoCorasickEdge[new_capacity];
  383. memcpy(new_edges, edges(), sizeof(AhoCorasickEdge) * old_capacity);
  384. for (unsigned edge_idx = old_capacity; edge_idx < new_capacity;
  385. ++edge_idx) {
  386. new_edges[edge_idx].label = kEmptyLabel;
  387. }
  388. if (edges_capacity_ != 0) {
  389. delete[] edges_.edges;
  390. }
  391. edges_.edges = new_edges;
  392. // These casts are safe due to the DCHECK above.
  393. edges_capacity_ = static_cast<uint16_t>(new_capacity);
  394. num_free_edges_ = static_cast<uint8_t>(new_capacity - old_capacity);
  395. }
  396. // Insert the new edge at the end of our heap storage.
  397. edges_.edges[num_edges()] = AhoCorasickEdge{label, node};
  398. if (label == kFailureNodeLabel) {
  399. // Make sure that kFailureNodeLabel is first.
  400. std::swap(edges_.edges[0], edges_.edges[num_edges()]);
  401. }
  402. --num_free_edges_;
  403. }
  404. void SubstringSetMatcher::AhoCorasickNode::SetFailure(NodeID node) {
  405. DCHECK_NE(kInvalidNodeID, node);
  406. if (node != kRootID) {
  407. SetEdge(kFailureNodeLabel, node);
  408. }
  409. }
  410. size_t SubstringSetMatcher::AhoCorasickNode::EstimateMemoryUsage() const {
  411. if (edges_capacity_ == 0) {
  412. return 0;
  413. } else {
  414. return base::trace_event::EstimateMemoryUsage(edges_.edges,
  415. edges_capacity_);
  416. }
  417. }
  418. } // namespace base