titled_url_index.cc 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431
  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. #include "components/bookmarks/browser/titled_url_index.h"
  5. #include <stdint.h>
  6. #include <algorithm>
  7. #include <unordered_set>
  8. #include <utility>
  9. #include "base/containers/cxx20_erase.h"
  10. #include "base/i18n/case_conversion.h"
  11. #include "base/i18n/unicodestring.h"
  12. #include "base/logging.h"
  13. #include "base/metrics/histogram_functions.h"
  14. #include "base/metrics/histogram_macros.h"
  15. #include "base/ranges/algorithm.h"
  16. #include "base/stl_util.h"
  17. #include "base/strings/utf_offset_string_conversions.h"
  18. #include "build/build_config.h"
  19. #include "components/bookmarks/browser/bookmark_utils.h"
  20. #include "components/bookmarks/browser/titled_url_match.h"
  21. #include "components/bookmarks/browser/titled_url_node.h"
  22. #include "components/query_parser/snippet.h"
  23. #include "third_party/icu/source/common/unicode/normalizer2.h"
  24. #include "third_party/icu/source/common/unicode/utypes.h"
  25. namespace bookmarks {
  26. namespace {
  27. // The maximum number of nodes to fetch when looking for nodes that match any
  28. // term (i.e. when invoking `RetrieveNodesMatchingAnyTerms()`). Parameterized
  29. // for testing.
  30. constexpr size_t kMatchingAnyTermsMaxNodes = 3000;
  31. // Returns a normalized version of the UTF16 string |text|. If it fails to
  32. // normalize the string, returns |text| itself as a best-effort.
  33. std::u16string Normalize(const std::u16string& text) {
  34. UErrorCode status = U_ZERO_ERROR;
  35. const icu::Normalizer2* normalizer2 =
  36. icu::Normalizer2::getInstance(nullptr, "nfkc", UNORM2_COMPOSE, status);
  37. if (U_FAILURE(status)) {
  38. // Log and crash right away to capture the error code in the crash report.
  39. LOG(FATAL) << "failed to create a normalizer: " << u_errorName(status);
  40. }
  41. icu::UnicodeString unicode_text(
  42. text.data(), static_cast<int32_t>(text.length()));
  43. icu::UnicodeString unicode_normalized_text;
  44. normalizer2->normalize(unicode_text, unicode_normalized_text, status);
  45. if (U_FAILURE(status)) {
  46. // This should not happen. Log the error and fall back.
  47. LOG(ERROR) << "normalization failed: " << u_errorName(status);
  48. return text;
  49. }
  50. return base::i18n::UnicodeStringToString16(unicode_normalized_text);
  51. }
  52. } // namespace
  53. TitledUrlIndex::TitledUrlIndex(std::unique_ptr<TitledUrlNodeSorter> sorter)
  54. : sorter_(std::move(sorter)) {
  55. }
  56. TitledUrlIndex::~TitledUrlIndex() {
  57. }
  58. void TitledUrlIndex::SetNodeSorter(
  59. std::unique_ptr<TitledUrlNodeSorter> sorter) {
  60. sorter_ = std::move(sorter);
  61. }
  62. void TitledUrlIndex::Add(const TitledUrlNode* node) {
  63. for (const std::u16string& term : ExtractIndexTerms(node))
  64. RegisterNode(term, node);
  65. }
  66. void TitledUrlIndex::Remove(const TitledUrlNode* node) {
  67. for (const std::u16string& term : ExtractIndexTerms(node))
  68. UnregisterNode(term, node);
  69. }
  70. std::vector<TitledUrlMatch> TitledUrlIndex::GetResultsMatching(
  71. const std::u16string& input_query,
  72. size_t max_count,
  73. query_parser::MatchingAlgorithm matching_algorithm,
  74. bool match_ancestor_titles) {
  75. SCOPED_UMA_HISTOGRAM_TIMER("Bookmarks.GetResultsMatching.Timing.Total");
  76. const std::u16string query = Normalize(input_query);
  77. std::vector<std::u16string> terms = ExtractQueryWords(query);
  78. base::UmaHistogramExactLinear("Bookmarks.GetResultsMatching.Terms.TermsCount",
  79. terms.size(), 16);
  80. if (terms.empty())
  81. return {};
  82. for (const std::u16string& term : terms) {
  83. base::UmaHistogramExactLinear(
  84. "Bookmarks.GetResultsMatching.Terms.TermLength", term.size(), 16);
  85. }
  86. // When |match_ancestor_titles| is true, |matches| shouldn't exclude nodes
  87. // that don't match every query term, as the query terms may match in the
  88. // ancestors. |MatchTitledUrlNodeWithQuery()| below will filter out nodes that
  89. // neither match nor ancestor-match every query term.
  90. TitledUrlNodeSet matches;
  91. {
  92. SCOPED_UMA_HISTOGRAM_TIMER(
  93. "Bookmarks.GetResultsMatching.Timing.RetrievingNodes");
  94. matches = match_ancestor_titles
  95. ? RetrieveNodesMatchingAnyTerms(terms, matching_algorithm,
  96. kMatchingAnyTermsMaxNodes)
  97. : RetrieveNodesMatchingAllTerms(terms, matching_algorithm);
  98. }
  99. base::UmaHistogramBoolean("Bookmarks.GetResultsMatching.AnyTermApproach.Used",
  100. match_ancestor_titles);
  101. base::UmaHistogramCounts10000("Bookmarks.GetResultsMatching.Nodes.Count",
  102. matches.size());
  103. // Slice by 3, the default value of
  104. // `kShortBookmarkSuggestionsByTotalInputLengthThreshold`. Shorter inputs will
  105. // likely have many fewer nodes than longer queries.
  106. if (input_query.size() < 3) {
  107. base::UmaHistogramCounts10000(
  108. "Bookmarks.GetResultsMatching.Nodes.Count."
  109. "InputsShorterThan3CharsLong",
  110. matches.size());
  111. } else {
  112. base::UmaHistogramCounts10000(
  113. "Bookmarks.GetResultsMatching.Nodes.Count.InputsAtLeast3CharsLong",
  114. matches.size());
  115. }
  116. if (matches.empty())
  117. return {};
  118. TitledUrlNodes sorted_nodes;
  119. SortMatches(matches, &sorted_nodes);
  120. // We use a QueryParser to fill in match positions for us. It's not the most
  121. // efficient way to go about this, but by the time we get here we know what
  122. // matches and so this shouldn't be performance critical.
  123. query_parser::QueryNodeVector query_nodes;
  124. query_parser::QueryParser::ParseQueryNodes(query, matching_algorithm,
  125. &query_nodes);
  126. std::vector<TitledUrlMatch> results = MatchTitledUrlNodesWithQuery(
  127. sorted_nodes, query_nodes, max_count, match_ancestor_titles);
  128. // In practice, `max_count`, is always 50 (`kMaxBookmarkMatches`), so
  129. // `results.size()` is at most 50.
  130. base::UmaHistogramExactLinear(
  131. "Bookmarks.GetResultsMatching.Matches.ReturnedCount", results.size(), 51);
  132. return results;
  133. }
  134. void TitledUrlIndex::SortMatches(const TitledUrlNodeSet& matches,
  135. TitledUrlNodes* sorted_nodes) const {
  136. SCOPED_UMA_HISTOGRAM_TIMER(
  137. "Bookmarks.GetResultsMatching.Timing.SortingNodes");
  138. if (sorter_) {
  139. sorter_->SortMatches(matches, sorted_nodes);
  140. } else {
  141. sorted_nodes->insert(sorted_nodes->end(), matches.begin(), matches.end());
  142. }
  143. }
  144. std::vector<TitledUrlMatch> TitledUrlIndex::MatchTitledUrlNodesWithQuery(
  145. const TitledUrlNodes& nodes,
  146. const query_parser::QueryNodeVector& query_nodes,
  147. size_t max_count,
  148. bool match_ancestor_titles) {
  149. SCOPED_UMA_HISTOGRAM_TIMER(
  150. "Bookmarks.GetResultsMatching.Timing.CreatingMatches");
  151. // The highest typed counts should be at the beginning of the `matches` vector
  152. // so that the best matches will always be included in the results. The loop
  153. // that calculates match relevance in
  154. // `HistoryContentsProvider::ConvertResults()` will run backwards to assure
  155. // higher relevance will be attributed to the best matches.
  156. std::vector<TitledUrlMatch> matches;
  157. int nodes_considered = 0;
  158. for (TitledUrlNodes::const_iterator i = nodes.begin();
  159. i != nodes.end() && matches.size() < max_count; ++i) {
  160. absl::optional<TitledUrlMatch> match =
  161. MatchTitledUrlNodeWithQuery(*i, query_nodes, match_ancestor_titles);
  162. if (match)
  163. matches.emplace_back(std::move(match).value());
  164. ++nodes_considered;
  165. }
  166. base::UmaHistogramCounts10000(
  167. "Bookmarks.GetResultsMatching.Matches.ConsideredCount", nodes_considered);
  168. return matches;
  169. }
  170. absl::optional<TitledUrlMatch> TitledUrlIndex::MatchTitledUrlNodeWithQuery(
  171. const TitledUrlNode* node,
  172. const query_parser::QueryNodeVector& query_nodes,
  173. bool match_ancestor_titles) {
  174. if (!node) {
  175. return absl::nullopt;
  176. }
  177. // Check that the result matches the query. The previous search
  178. // was a simple per-word search, while the more complex matching
  179. // of QueryParser may filter it out. For example, the query
  180. // ["thi"] will match the title [Thinking], but since
  181. // ["thi"] is quoted we don't want to do a prefix match.
  182. query_parser::QueryWordVector title_words, url_words, ancestor_words;
  183. const std::u16string lower_title =
  184. base::i18n::ToLower(Normalize(node->GetTitledUrlNodeTitle()));
  185. query_parser::QueryParser::ExtractQueryWords(lower_title, &title_words);
  186. base::OffsetAdjuster::Adjustments adjustments;
  187. query_parser::QueryParser::ExtractQueryWords(
  188. CleanUpUrlForMatching(node->GetTitledUrlNodeUrl(), &adjustments),
  189. &url_words);
  190. if (match_ancestor_titles) {
  191. for (auto ancestor : node->GetTitledUrlNodeAncestorTitles()) {
  192. query_parser::QueryParser::ExtractQueryWords(
  193. base::i18n::ToLower(Normalize(std::u16string(ancestor))),
  194. &ancestor_words);
  195. }
  196. }
  197. query_parser::Snippet::MatchPositions title_matches, url_matches;
  198. bool query_has_ancestor_matches = false;
  199. for (const auto& query_node : query_nodes) {
  200. const bool has_title_matches =
  201. query_node->HasMatchIn(title_words, &title_matches);
  202. const bool has_url_matches =
  203. query_node->HasMatchIn(url_words, &url_matches);
  204. const bool has_ancestor_matches =
  205. match_ancestor_titles && query_node->HasMatchIn(ancestor_words, false);
  206. query_has_ancestor_matches =
  207. query_has_ancestor_matches || has_ancestor_matches;
  208. if (!has_title_matches && !has_url_matches && !has_ancestor_matches)
  209. return absl::nullopt;
  210. query_parser::QueryParser::SortAndCoalesceMatchPositions(&title_matches);
  211. query_parser::QueryParser::SortAndCoalesceMatchPositions(&url_matches);
  212. }
  213. TitledUrlMatch match;
  214. if (lower_title.length() == node->GetTitledUrlNodeTitle().length()) {
  215. // Only use title matches if the lowercase string is the same length
  216. // as the original string, otherwise the matches are meaningless.
  217. // TODO(mpearson): revise match positions appropriately.
  218. match.title_match_positions.swap(title_matches);
  219. }
  220. // Now that we're done processing this entry, correct the offsets of the
  221. // matches in |url_matches| so they point to offsets in the original URL
  222. // spec, not the cleaned-up URL string that we used for matching.
  223. std::vector<size_t> offsets =
  224. TitledUrlMatch::OffsetsFromMatchPositions(url_matches);
  225. base::OffsetAdjuster::UnadjustOffsets(adjustments, &offsets);
  226. url_matches =
  227. TitledUrlMatch::ReplaceOffsetsInMatchPositions(url_matches, offsets);
  228. match.url_match_positions.swap(url_matches);
  229. match.has_ancestor_match = query_has_ancestor_matches;
  230. match.node = node;
  231. return match;
  232. }
  233. TitledUrlIndex::TitledUrlNodeSet TitledUrlIndex::RetrieveNodesMatchingAllTerms(
  234. const std::vector<std::u16string>& terms,
  235. query_parser::MatchingAlgorithm matching_algorithm) const {
  236. DCHECK(!terms.empty());
  237. TitledUrlNodeSet matches =
  238. RetrieveNodesMatchingTerm(terms[0], matching_algorithm);
  239. for (size_t i = 1; i < terms.size() && !matches.empty(); ++i) {
  240. TitledUrlNodeSet term_matches =
  241. RetrieveNodesMatchingTerm(terms[i], matching_algorithm);
  242. // Compute intersection between the two sets.
  243. base::EraseIf(matches, base::IsNotIn<TitledUrlNodeSet>(term_matches));
  244. }
  245. return matches;
  246. }
  247. TitledUrlIndex::TitledUrlNodeSet TitledUrlIndex::RetrieveNodesMatchingAnyTerms(
  248. const std::vector<std::u16string>& terms,
  249. query_parser::MatchingAlgorithm matching_algorithm,
  250. size_t max_nodes) const {
  251. DCHECK(!terms.empty());
  252. std::vector<TitledUrlNodes> matches_per_term;
  253. bool some_term_had_empty_matches = false;
  254. for (const std::u16string& term : terms) {
  255. // Use `matching_algorithm`, as opposed to exact matching, to allow inputs
  256. // like 'myFolder goog' to match a 'google.com' bookmark in a 'myFolder'
  257. // folder.
  258. TitledUrlNodes term_matches =
  259. RetrieveNodesMatchingTerm(term, matching_algorithm);
  260. base::UmaHistogramCounts1000(
  261. "Bookmarks.GetResultsMatching.AnyTermApproach.NodeCountPerTerm",
  262. term_matches.size());
  263. if (term_matches.empty())
  264. some_term_had_empty_matches = true;
  265. else
  266. matches_per_term.push_back(std::move(term_matches));
  267. }
  268. base::UmaHistogramExactLinear(
  269. "Bookmarks.GetResultsMatching.AnyTermApproach.TermsUnionedCount",
  270. matches_per_term.size(), 16);
  271. // Sort `matches_per_term` least frequent first. This prevents terms like
  272. // 'https', which match a lot of nodes, from wasting `max_nodes` capacity.
  273. base::ranges::sort(
  274. matches_per_term,
  275. [](size_t first, size_t second) { return first < second; },
  276. [](const auto& matches) { return matches.size(); });
  277. // Use an `unordered_set` to avoid potentially 1000's of linear time
  278. // insertions into the ordered `TitledUrlNodeSet` (i.e. `flat_set`).
  279. std::unordered_set<const TitledUrlNode*> matches;
  280. for (const auto& term_matches : matches_per_term) {
  281. for (const TitledUrlNode* node : term_matches) {
  282. matches.insert(node);
  283. if (matches.size() == max_nodes)
  284. break;
  285. }
  286. if (matches.size() == max_nodes)
  287. break;
  288. }
  289. base::UmaHistogramCounts10000(
  290. "Bookmarks.GetResultsMatching.AnyTermApproach.NodeCountAnyTerms",
  291. matches.size());
  292. // Append all nodes that match every input term. This is necessary because
  293. // with the `max_nodes` threshold above, it's possible that `matches` is
  294. // missing some nodes that match every input term. Since `matches_per_term[i]`
  295. // is a superset of the intersection of `matches_per_term`s, if
  296. // `matches_per_term[0].size() <= max_nodes`, all of `matches_per_term[0]`,
  297. // and therefore the intersection matches`, are already in `matches`.
  298. TitledUrlNodeSet all_term_matches;
  299. if (!some_term_had_empty_matches && matches_per_term[0].size() > max_nodes) {
  300. all_term_matches = matches_per_term[0];
  301. for (size_t i = 1; i < matches_per_term.size() && !all_term_matches.empty();
  302. ++i) {
  303. // Compute intersection between the two sets.
  304. base::EraseIf(all_term_matches,
  305. base::IsNotIn<TitledUrlNodeSet>(matches_per_term[i]));
  306. }
  307. // `all_term_matches` is the intersection of each term's node matches; the
  308. // same as `RetrieveNodesMatchingAllTerms()`. We don't call the latter as a
  309. // performance optimization.
  310. DCHECK(all_term_matches ==
  311. RetrieveNodesMatchingAllTerms(terms, matching_algorithm));
  312. }
  313. base::UmaHistogramCounts1000(
  314. "Bookmarks.GetResultsMatching.AnyTermApproach.NodeCountAllTerms",
  315. all_term_matches.size());
  316. matches.insert(all_term_matches.begin(), all_term_matches.end());
  317. base::UmaHistogramCounts10000(
  318. "Bookmarks.GetResultsMatching.AnyTermApproach.NodeCount", matches.size());
  319. return TitledUrlNodeSet(matches.begin(), matches.end());
  320. }
  321. TitledUrlIndex::TitledUrlNodes TitledUrlIndex::RetrieveNodesMatchingTerm(
  322. const std::u16string& term,
  323. query_parser::MatchingAlgorithm matching_algorithm) const {
  324. Index::const_iterator i = index_.lower_bound(term);
  325. if (i == index_.end())
  326. return {};
  327. if (!query_parser::QueryParser::IsWordLongEnoughForPrefixSearch(
  328. term, matching_algorithm)) {
  329. // Term is too short for prefix match, compare using exact match.
  330. if (i->first != term)
  331. return {}; // No title/URL pairs with this term.
  332. return TitledUrlNodes(i->second.begin(), i->second.end());
  333. }
  334. // Loop through index adding all entries that start with term to
  335. // |prefix_matches|.
  336. TitledUrlNodes prefix_matches;
  337. while (i != index_.end() && i->first.size() >= term.size() &&
  338. term.compare(0, term.size(), i->first, 0, term.size()) == 0) {
  339. prefix_matches.insert(prefix_matches.end(), i->second.begin(),
  340. i->second.end());
  341. ++i;
  342. }
  343. return prefix_matches;
  344. }
  345. // static
  346. std::vector<std::u16string> TitledUrlIndex::ExtractQueryWords(
  347. const std::u16string& query) {
  348. std::vector<std::u16string> terms;
  349. if (query.empty())
  350. return std::vector<std::u16string>();
  351. query_parser::QueryParser::ParseQueryWords(
  352. base::i18n::ToLower(query), query_parser::MatchingAlgorithm::DEFAULT,
  353. &terms);
  354. return terms;
  355. }
  356. // static
  357. std::vector<std::u16string> TitledUrlIndex::ExtractIndexTerms(
  358. const TitledUrlNode* node) {
  359. std::vector<std::u16string> terms;
  360. for (const std::u16string& term :
  361. ExtractQueryWords(Normalize(node->GetTitledUrlNodeTitle()))) {
  362. terms.push_back(term);
  363. }
  364. for (const std::u16string& term : ExtractQueryWords(CleanUpUrlForMatching(
  365. node->GetTitledUrlNodeUrl(), /*adjustments=*/nullptr))) {
  366. terms.push_back(term);
  367. }
  368. return terms;
  369. }
  370. void TitledUrlIndex::RegisterNode(const std::u16string& term,
  371. const TitledUrlNode* node) {
  372. index_[term].insert(node);
  373. }
  374. void TitledUrlIndex::UnregisterNode(const std::u16string& term,
  375. const TitledUrlNode* node) {
  376. auto i = index_.find(term);
  377. if (i == index_.end()) {
  378. // We can get here if the node has the same term more than once. For
  379. // example, a node with the title 'foo foo' would end up here.
  380. return;
  381. }
  382. i->second.erase(node);
  383. if (i->second.empty())
  384. index_.erase(i);
  385. }
  386. } // namespace bookmarks