substring_set_matcher.h 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336
  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. #ifndef BASE_SUBSTRING_SET_MATCHER_SUBSTRING_SET_MATCHER_H_
  5. #define BASE_SUBSTRING_SET_MATCHER_SUBSTRING_SET_MATCHER_H_
  6. #include <stdint.h>
  7. #include <limits>
  8. #include <set>
  9. #include <string>
  10. #include <vector>
  11. #include "base/base_export.h"
  12. #include "base/check_op.h"
  13. #include "base/substring_set_matcher/matcher_string_pattern.h"
  14. namespace base {
  15. // Class that store a set of string patterns and can find for a string S,
  16. // which string patterns occur in S.
  17. class BASE_EXPORT SubstringSetMatcher {
  18. public:
  19. SubstringSetMatcher() = default;
  20. SubstringSetMatcher(const SubstringSetMatcher&) = delete;
  21. SubstringSetMatcher& operator=(const SubstringSetMatcher&) = delete;
  22. ~SubstringSetMatcher();
  23. // Registers all |patterns|. Each pattern needs to have a unique ID and all
  24. // pattern strings must be unique. Build() should be called exactly once
  25. // (before it is called, the tree is empty).
  26. //
  27. // Complexity:
  28. // Let n = number of patterns.
  29. // Let S = sum of pattern lengths.
  30. // Let k = range of char. Generally 256.
  31. // Complexity = O(nlogn + S * logk)
  32. // nlogn comes from sorting the patterns.
  33. // log(k) comes from our usage of std::map to store edges.
  34. //
  35. // Returns true on success (may fail if e.g. if the tree gets too many nodes).
  36. bool Build(const std::vector<MatcherStringPattern>& patterns);
  37. bool Build(std::vector<const MatcherStringPattern*> patterns);
  38. // Matches |text| against all registered MatcherStringPatterns. Stores the IDs
  39. // of matching patterns in |matches|. |matches| is not cleared before adding
  40. // to it.
  41. // Complexity:
  42. // Let t = length of |text|.
  43. // Let k = range of char. Generally 256.
  44. // Let z = number of matches returned.
  45. // Complexity = O(t * logk + zlogz)
  46. bool Match(const std::string& text,
  47. std::set<MatcherStringPattern::ID>* matches) const;
  48. // As Match(), except it returns immediately on the first match.
  49. // This allows true/false matching to be done without any dynamic
  50. // memory allocation.
  51. // Complexity = O(t * logk)
  52. bool AnyMatch(const std::string& text) const;
  53. // Returns true if this object retains no allocated data.
  54. bool IsEmpty() const { return is_empty_; }
  55. // Returns the dynamically allocated memory usage in bytes. See
  56. // base/trace_event/memory_usage_estimator.h for details.
  57. size_t EstimateMemoryUsage() const;
  58. private:
  59. // Represents the index of the node within |tree_|. It is specifically
  60. // uint32_t so that we can be sure it takes up 4 bytes when stored together
  61. // with the 9-bit label (so 23 bits are allocated to the NodeID, even though
  62. // it is exposed as uint32_t). If the computed size of |tree_| is
  63. // larger than what can be stored within 23 bits, Build() will fail.
  64. using NodeID = uint32_t;
  65. // This is the maximum possible size of |tree_| and hence can't be a valid ID.
  66. static constexpr NodeID kInvalidNodeID = (1u << 23) - 1;
  67. static constexpr NodeID kRootID = 0;
  68. // A node of an Aho Corasick Tree. See
  69. // http://web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/02/Small02.pdf
  70. // to understand the algorithm.
  71. //
  72. // The algorithm is based on the idea of building a trie of all registered
  73. // patterns. Each node of the tree is annotated with a set of pattern
  74. // IDs that are used to report matches.
  75. //
  76. // The root of the trie represents an empty match. If we were looking whether
  77. // any registered pattern matches a text at the beginning of the text (i.e.
  78. // whether any pattern is a prefix of the text), we could just follow
  79. // nodes in the trie according to the matching characters in the text.
  80. // E.g., if text == "foobar", we would follow the trie from the root node
  81. // to its child labeled 'f', from there to child 'o', etc. In this process we
  82. // would report all pattern IDs associated with the trie nodes as matches.
  83. //
  84. // As we are not looking for all prefix matches but all substring matches,
  85. // this algorithm would need to compare text.substr(0), text.substr(1), ...
  86. // against the trie, which is in O(|text|^2).
  87. //
  88. // The Aho Corasick algorithm improves this runtime by using failure edges.
  89. // In case we have found a partial match of length k in the text
  90. // (text[i, ..., i + k - 1]) in the trie starting at the root and ending at
  91. // a node at depth k, but cannot find a match in the trie for character
  92. // text[i + k] at depth k + 1, we follow a failure edge. This edge
  93. // corresponds to the longest proper suffix of text[i, ..., i + k - 1] that
  94. // is a prefix of any registered pattern.
  95. //
  96. // If your brain thinks "Forget it, let's go shopping.", don't worry.
  97. // Take a nap and read an introductory text on the Aho Corasick algorithm.
  98. // It will make sense. Eventually.
  99. // An edge internal to the tree. We pack the label (character we are
  100. // matching on) and the destination node ID into 32 bits, to save memory.
  101. // We also use these edges as a sort of generic key/value store for
  102. // some special values that not all nodes will have; this also saves on
  103. // memory over the otherwise obvious choice of having them as struct fields,
  104. // as it means we do not to store them when they are not present.
  105. struct AhoCorasickEdge {
  106. // char (unsigned, so [0..255]), or a special label below.
  107. uint32_t label : 9;
  108. NodeID node_id : 23;
  109. };
  110. // Node index that failure edge leads to. The failure node corresponds to
  111. // the node which represents the longest proper suffix (include empty
  112. // string) of the string represented by this node. Not stored if it is
  113. // equal to kRootID (since that is the most common value).
  114. //
  115. // NOTE: Assigning |root| as the failure edge for itself doesn't strictly
  116. // abide by the definition of "proper" suffix. The proper suffix of an empty
  117. // string should probably be defined as null, but we assign it to the |root|
  118. // to simplify the code and have the invariant that the failure edge is always
  119. // defined.
  120. static constexpr uint32_t kFailureNodeLabel = 0x100;
  121. static constexpr uint32_t kFirstSpecialLabel = kFailureNodeLabel;
  122. // Node index that corresponds to the longest proper suffix (including empty
  123. // suffix) of this node and which also represents the end of a pattern.
  124. // Does not have to exist.
  125. static constexpr uint32_t kOutputLinkLabel = 0x101;
  126. // If present, this node represents the end of a pattern. It stores the ID of
  127. // the corresponding pattern (ie., it is not really a NodeID, but a
  128. // MatcherStringPattern::ID).
  129. static constexpr uint32_t kMatchIDLabel = 0x102;
  130. // Used for uninitialized label slots; used so that we do not have to test for
  131. // them in other ways, since we know the data will be initialized and never
  132. // match any other labels.
  133. static constexpr uint32_t kEmptyLabel = 0x103;
  134. // A node in the trie, packed tightly together so that it occupies 12 bytes
  135. // (both on 32- and 64-bit platforms), but aligned to at least 4 (see the
  136. // comment on edges_).
  137. class alignas(AhoCorasickEdge) AhoCorasickNode {
  138. public:
  139. AhoCorasickNode();
  140. ~AhoCorasickNode();
  141. AhoCorasickNode(AhoCorasickNode&& other);
  142. AhoCorasickNode& operator=(AhoCorasickNode&& other);
  143. NodeID GetEdge(uint32_t label) const {
  144. if (edges_capacity_ != 0) {
  145. return GetEdgeNoInline(label);
  146. }
  147. static_assert(kNumInlineEdges == 2, "Code below needs updating");
  148. if (edges_.inline_edges[0].label == label) {
  149. return edges_.inline_edges[0].node_id;
  150. }
  151. if (edges_.inline_edges[1].label == label) {
  152. return edges_.inline_edges[1].node_id;
  153. }
  154. return kInvalidNodeID;
  155. }
  156. NodeID GetEdgeNoInline(uint32_t label) const;
  157. void SetEdge(uint32_t label, NodeID node);
  158. const AhoCorasickEdge* edges() const {
  159. // NOTE: Returning edges_.inline_edges here is fine, because it's
  160. // the first thing in the struct (see the comment on edges_).
  161. DCHECK_EQ(0u, reinterpret_cast<uintptr_t>(edges_.inline_edges) %
  162. alignof(AhoCorasickEdge));
  163. return edges_capacity_ == 0 ? edges_.inline_edges : edges_.edges;
  164. }
  165. NodeID failure() const {
  166. // NOTE: Even if num_edges_ == 0, we are not doing anything
  167. // undefined, as we will have room for at least two edges
  168. // and empty edges are set to kEmptyLabel.
  169. const AhoCorasickEdge& first_edge = *edges();
  170. if (first_edge.label == kFailureNodeLabel) {
  171. return first_edge.node_id;
  172. } else {
  173. return kRootID;
  174. }
  175. }
  176. void SetFailure(NodeID failure);
  177. void SetMatchID(MatcherStringPattern::ID id) {
  178. DCHECK(!IsEndOfPattern());
  179. DCHECK(id < kInvalidNodeID); // This is enforced by Build().
  180. SetEdge(kMatchIDLabel, static_cast<NodeID>(id));
  181. has_outputs_ = true;
  182. }
  183. // Returns true if this node corresponds to a pattern.
  184. bool IsEndOfPattern() const {
  185. if (!has_outputs_) {
  186. // Fast reject.
  187. return false;
  188. }
  189. return GetEdge(kMatchIDLabel) != kInvalidNodeID;
  190. }
  191. // Must only be called if |IsEndOfPattern| returns true for this node.
  192. MatcherStringPattern::ID GetMatchID() const {
  193. DCHECK(IsEndOfPattern());
  194. return GetEdge(kMatchIDLabel);
  195. }
  196. void SetOutputLink(NodeID node) {
  197. if (node != kInvalidNodeID) {
  198. SetEdge(kOutputLinkLabel, node);
  199. has_outputs_ = true;
  200. }
  201. }
  202. NodeID output_link() const { return GetEdge(kOutputLinkLabel); }
  203. size_t EstimateMemoryUsage() const;
  204. size_t num_edges() const {
  205. if (edges_capacity_ == 0) {
  206. return kNumInlineEdges - num_free_edges_;
  207. } else {
  208. return edges_capacity_ - num_free_edges_;
  209. }
  210. }
  211. bool has_outputs() const { return has_outputs_; }
  212. private:
  213. // Outgoing edges of current node, including failure edge and output links.
  214. // Most nodes have only one or two (or even zero) edges, not the last
  215. // because many of them are leaves. Thus, we make an optimization for this
  216. // common case; instead of a pointer to an edge array on the heap, we can
  217. // pack two edges inline where the pointer would otherwise be. This reduces
  218. // memory usage dramatically, as well as saving us a cache-line fetch.
  219. //
  220. // Note that even though most nodes have fewer outgoing edges, most nodes
  221. // that we actually traverse will have any of them. This apparent
  222. // contradiction is because we tend to spend more of our time near the root
  223. // of the trie, where it is wide. This means that another layout would be
  224. // possible: If we wanted to, non-inline nodes could simply store an array
  225. // of 259 (256 possible characters plus the three special label types)
  226. // edges, indexed directly by label type. This would use 20–50% more RAM,
  227. // but also increases the speed of lookups due to removing the search loop.
  228. //
  229. // The nodes are generally unordered; since we typically index text, even
  230. // the root will rarely be more than 20–30 wide, and at that point, it's
  231. // better to just do a linear search than a binary one (which fares poorly
  232. // on branch predictors). However, a special case, we put kFailureNodeLabel
  233. // in the first slot if it exists (ie., is not equal to kRootID), since we
  234. // need to access that label during every single node we look at during
  235. // traversal.
  236. //
  237. // NOTE: Keep this the first member in the struct, so that inline_edges gets
  238. // 4-aligned (since the class is marked as such, despite being packed.
  239. // Otherwise, edges() can return an unaligned pointer marked as aligned
  240. // (the unalignedness gets lost).
  241. static constexpr int kNumInlineEdges = 2;
  242. union {
  243. // Out-of-line edge storage, having room for edges_capacity_ elements.
  244. // Note that due to __attribute__((packed)) below, this pointer may be
  245. // unaligned on 64-bit platforms, causing slightly less efficient
  246. // access to it in some cases.
  247. AhoCorasickEdge* edges;
  248. // Inline edge storage, used if edges_capacity_ == 0.
  249. AhoCorasickEdge inline_edges[kNumInlineEdges];
  250. } edges_;
  251. // Whether we have an edge for kMatchIDLabel or kOutputLinkLabel,
  252. // ie., hitting this node during traversal will create one or more
  253. // matches. This is redundant, but since every single lookup during
  254. // traversal needs this, it saves a few searches for us.
  255. bool has_outputs_ = false;
  256. // Number of unused left in edges_. Edges are always allocated from the
  257. // beginning and never deleted; those after num_edges_ will be marked with
  258. // kEmptyLabel (and have an undefined node_id). We store the number of
  259. // free edges instead of the more common number of _used_ edges, to be
  260. // sure that we are able to fit it in an uint8_t. num_edges() provides
  261. // a useful abstraction over this.
  262. uint8_t num_free_edges_ = kNumInlineEdges;
  263. // How many edges we have allocated room for (can never be more than
  264. // kEmptyLabel + 1). If equal to zero, we are not using heap storage,
  265. // but instead are using inline_edges.
  266. //
  267. // If not equal to zero, will be a multiple of 4, so that we can use
  268. // SIMD to accelerate looking for edges.
  269. uint16_t edges_capacity_ = 0;
  270. } __attribute__((packed));
  271. using SubstringPatternVector = std::vector<const MatcherStringPattern*>;
  272. // Given the set of patterns, compute how many nodes will the corresponding
  273. // Aho-Corasick tree have. Note that |patterns| need to be sorted.
  274. NodeID GetTreeSize(
  275. const std::vector<const MatcherStringPattern*>& patterns) const;
  276. void BuildAhoCorasickTree(const SubstringPatternVector& patterns);
  277. // Inserts a path for |pattern->pattern()| into the tree and adds
  278. // |pattern->id()| to the set of matches.
  279. void InsertPatternIntoAhoCorasickTree(const MatcherStringPattern* pattern);
  280. void CreateFailureAndOutputEdges();
  281. // Adds all pattern IDs to |matches| which are a suffix of the string
  282. // represented by |node|.
  283. void AccumulateMatchesForNode(
  284. const AhoCorasickNode* node,
  285. std::set<MatcherStringPattern::ID>* matches) const;
  286. // The nodes of a Aho-Corasick tree.
  287. std::vector<AhoCorasickNode> tree_;
  288. bool is_empty_ = true;
  289. };
  290. } // namespace base
  291. #endif // BASE_SUBSTRING_SET_MATCHER_SUBSTRING_SET_MATCHER_H_