titled_url_index.h 5.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146
  1. // Copyright 2014 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 COMPONENTS_BOOKMARKS_BROWSER_TITLED_URL_INDEX_H_
  5. #define COMPONENTS_BOOKMARKS_BROWSER_TITLED_URL_INDEX_H_
  6. #include <stddef.h>
  7. #include <map>
  8. #include <memory>
  9. #include <string>
  10. #include <vector>
  11. #include "base/containers/flat_set.h"
  12. #include "components/bookmarks/browser/titled_url_node_sorter.h"
  13. #include "components/query_parser/query_parser.h"
  14. #include "third_party/abseil-cpp/absl/types/optional.h"
  15. namespace bookmarks {
  16. class TitledUrlNode;
  17. struct TitledUrlMatch;
  18. // TitledUrlIndex maintains an index of paired titles and URLs for quick lookup.
  19. //
  20. // TitledUrlIndex maintains the index (index_) as a map of sets. The map (type
  21. // Index) maps from a lower case string to the set (type TitledUrlNodeSet) of
  22. // TitledUrlNodes that contain that string in their title or URL.
  23. class TitledUrlIndex {
  24. public:
  25. using TitledUrlNodeSet = base::flat_set<const TitledUrlNode*>;
  26. // Constructs a TitledUrlIndex. |sorter| is used to construct a sorted list
  27. // of matches when matches are returned from the index. If null, matches are
  28. // returned unsorted.
  29. explicit TitledUrlIndex(
  30. std::unique_ptr<TitledUrlNodeSorter> sorter = nullptr);
  31. TitledUrlIndex(const TitledUrlIndex&) = delete;
  32. TitledUrlIndex& operator=(const TitledUrlIndex&) = delete;
  33. ~TitledUrlIndex();
  34. void SetNodeSorter(std::unique_ptr<TitledUrlNodeSorter> sorter);
  35. // Invoked when a title/URL pair has been added to the model.
  36. void Add(const TitledUrlNode* node);
  37. // Invoked when a title/URL pair has been removed from the model.
  38. void Remove(const TitledUrlNode* node);
  39. // Returns up to |max_count| of matches containing each term from the text
  40. // |query| in either the title, URL, or, if |match_ancestor_titles| is true,
  41. // the titles of ancestor nodes. |matching_algorithm| determines the algorithm
  42. // used by QueryParser internally to parse |query|.
  43. std::vector<TitledUrlMatch> GetResultsMatching(
  44. const std::u16string& query,
  45. size_t max_count,
  46. query_parser::MatchingAlgorithm matching_algorithm,
  47. bool match_ancestor_titles);
  48. // For testing only.
  49. TitledUrlNodeSet RetrieveNodesMatchingAllTermsForTesting(
  50. const std::vector<std::u16string>& terms,
  51. query_parser::MatchingAlgorithm matching_algorithm) const {
  52. return RetrieveNodesMatchingAllTerms(terms, matching_algorithm);
  53. }
  54. // For testing only.
  55. TitledUrlNodeSet RetrieveNodesMatchingAnyTermsForTesting(
  56. const std::vector<std::u16string>& terms,
  57. query_parser::MatchingAlgorithm matching_algorithm,
  58. size_t max_nodes) const {
  59. return RetrieveNodesMatchingAnyTerms(terms, matching_algorithm, max_nodes);
  60. }
  61. private:
  62. using TitledUrlNodes = std::vector<const TitledUrlNode*>;
  63. using Index = std::map<std::u16string, TitledUrlNodeSet>;
  64. // Constructs |sorted_nodes| by copying the matches in |matches| and sorting
  65. // them.
  66. void SortMatches(const TitledUrlNodeSet& matches,
  67. TitledUrlNodes* sorted_nodes) const;
  68. // For each node, calls `MatchTitledUrlNodeWithQuery()` and returns the
  69. // aggregated `TitledUrlMatch`s.
  70. std::vector<TitledUrlMatch> MatchTitledUrlNodesWithQuery(
  71. const TitledUrlNodes& nodes,
  72. const query_parser::QueryNodeVector& query_nodes,
  73. size_t max_count,
  74. bool match_ancestor_titles);
  75. // Finds |query_nodes| matches in |node| and returns a TitledUrlMatch
  76. // containing |node| and the matches.
  77. absl::optional<TitledUrlMatch> MatchTitledUrlNodeWithQuery(
  78. const TitledUrlNode* node,
  79. const query_parser::QueryNodeVector& query_nodes,
  80. bool match_ancestor_titles);
  81. // Return matches for the specified |terms|. This is an intersection of each
  82. // term's matches.
  83. TitledUrlNodeSet RetrieveNodesMatchingAllTerms(
  84. const std::vector<std::u16string>& terms,
  85. query_parser::MatchingAlgorithm matching_algorithm) const;
  86. // Return matches for the specified `terms`. This is approximately a union of
  87. // each term's match, with some limitations to avoid too many nodes being
  88. // returned: terms shorter than `term_min_length` or matching more than
  89. // `max_nodes_per_term` nodes won't have their nodes accumulated by union; and
  90. // accumulation is capped to `max_nodes`. Guaranteed to include any node
  91. // `RetrieveNodesMatchingAllTerms()` includes.
  92. TitledUrlNodeSet RetrieveNodesMatchingAnyTerms(
  93. const std::vector<std::u16string>& terms,
  94. query_parser::MatchingAlgorithm matching_algorithm,
  95. size_t max_nodes) const;
  96. // Return matches for the specified |term|. May return duplicates.
  97. TitledUrlNodes RetrieveNodesMatchingTerm(
  98. const std::u16string& term,
  99. query_parser::MatchingAlgorithm matching_algorithm) const;
  100. // Returns the set of query words from |query|.
  101. static std::vector<std::u16string> ExtractQueryWords(
  102. const std::u16string& query);
  103. // Return the index terms for |node|.
  104. static std::vector<std::u16string> ExtractIndexTerms(
  105. const TitledUrlNode* node);
  106. // Adds |node| to |index_|.
  107. void RegisterNode(const std::u16string& term, const TitledUrlNode* node);
  108. // Removes |node| from |index_|.
  109. void UnregisterNode(const std::u16string& term, const TitledUrlNode* node);
  110. Index index_;
  111. std::unique_ptr<TitledUrlNodeSorter> sorter_;
  112. };
  113. } // namespace bookmarks
  114. #endif // COMPONENTS_BOOKMARKS_BROWSER_TITLED_URL_INDEX_H_