history_clusters_util.cc 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319
  1. // Copyright 2022 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/history_clusters/core/history_clusters_util.h"
  5. #include <algorithm>
  6. #include "base/containers/contains.h"
  7. #include "base/i18n/case_conversion.h"
  8. #include "base/ranges/algorithm.h"
  9. #include "base/strings/string_piece.h"
  10. #include "base/strings/string_util.h"
  11. #include "base/strings/utf_string_conversions.h"
  12. #include "components/history/core/browser/history_types.h"
  13. #include "components/history/core/browser/visitsegment_database.h"
  14. #include "components/history_clusters/core/config.h"
  15. #include "components/history_clusters/core/features.h"
  16. #include "components/query_parser/query_parser.h"
  17. #include "components/query_parser/snippet.h"
  18. #include "components/url_formatter/url_formatter.h"
  19. namespace history_clusters {
  20. namespace {
  21. // Returns true if `find_nodes` matches `cluster_keywords`.
  22. bool DoesQueryMatchClusterKeywords(
  23. const query_parser::QueryNodeVector& find_nodes,
  24. const std::vector<std::u16string>& cluster_keywords) {
  25. // All of the cluster's `keyword`s go into `find_in_words`.
  26. // Each `keyword` may have multiple terms, so loop over them.
  27. query_parser::QueryWordVector find_in_words;
  28. for (auto& keyword : cluster_keywords) {
  29. query_parser::QueryParser::ExtractQueryWords(base::i18n::ToLower(keyword),
  30. &find_in_words);
  31. }
  32. return query_parser::QueryParser::DoesQueryMatch(find_in_words, find_nodes);
  33. }
  34. // Flags any elements within `cluster_visits` that match `find_nodes`. The
  35. // matching is deliberately meant to closely mirror the History implementation.
  36. // Returns the total score of matching visits, and returns 0 if no visits match.
  37. float MarkMatchesAndGetScore(const query_parser::QueryNodeVector& find_nodes,
  38. history::Cluster* cluster) {
  39. DCHECK(cluster);
  40. float total_matching_visit_score = 0.0;
  41. if (cluster->label &&
  42. query_parser::QueryParser::DoesQueryMatch(
  43. *(cluster->label), find_nodes, &(cluster->label_match_positions))) {
  44. total_matching_visit_score += 1.0;
  45. }
  46. for (auto& visit : cluster->visits) {
  47. bool match_found = false;
  48. // Search through the visible elements and highlight match positions.
  49. GURL gurl = visit.annotated_visit.url_row.url();
  50. auto url_for_display_lower = base::i18n::ToLower(visit.url_for_display);
  51. match_found |= query_parser::QueryParser::DoesQueryMatch(
  52. url_for_display_lower, find_nodes,
  53. &visit.url_for_display_match_positions);
  54. auto title_lower =
  55. base::i18n::ToLower(visit.annotated_visit.url_row.title());
  56. match_found |= query_parser::QueryParser::DoesQueryMatch(
  57. title_lower, find_nodes, &visit.title_match_positions);
  58. // If we couldn't find it in the visible elements, try a second search
  59. // where we put all the text into one bag and try again. We need to do this
  60. // to be as exhaustive as History.
  61. // TODO(tommycli): Downgrade the score of these matches, or investigate if
  62. // we can discard this second pass. The consequence of discarding the second
  63. // pass is to omit matches that span both the URL and title.
  64. if (!match_found) {
  65. query_parser::QueryWordVector find_in_words;
  66. std::u16string url_lower =
  67. base::i18n::ToLower(base::UTF8ToUTF16(gurl.possibly_invalid_spec()));
  68. query_parser::QueryParser::ExtractQueryWords(url_lower, &find_in_words);
  69. query_parser::QueryParser::ExtractQueryWords(url_for_display_lower,
  70. &find_in_words);
  71. query_parser::QueryParser::ExtractQueryWords(title_lower, &find_in_words);
  72. match_found |=
  73. query_parser::QueryParser::DoesQueryMatch(find_in_words, find_nodes);
  74. }
  75. if (match_found) {
  76. visit.matches_search_query = true;
  77. DCHECK_GE(visit.score, 0);
  78. total_matching_visit_score += visit.score;
  79. }
  80. }
  81. return total_matching_visit_score;
  82. }
  83. // Re-scores and re-sorts `cluster_visits` so that all visits that match the
  84. // search query are promoted above all visits that don't match the search query.
  85. // All visits are likely to be rescored in this case.
  86. //
  87. // Note, this should NOT be called for `cluster_visits` with NO matching visits.
  88. void PromoteMatchingVisitsAboveNonMatchingVisits(
  89. std::vector<history::ClusterVisit>& cluster_visits) {
  90. for (auto& visit : cluster_visits) {
  91. if (visit.matches_search_query) {
  92. // Smash all matching scores into the range that's above the fold.
  93. visit.score =
  94. GetConfig().min_score_to_always_show_above_the_fold +
  95. visit.score *
  96. (1 - GetConfig().min_score_to_always_show_above_the_fold);
  97. } else {
  98. // Smash all non-matching scores into the range that's below the fold.
  99. visit.score =
  100. visit.score * GetConfig().min_score_to_always_show_above_the_fold;
  101. }
  102. }
  103. StableSortVisits(cluster_visits);
  104. }
  105. } // namespace
  106. GURL ComputeURLForDeduping(const GURL& url) {
  107. // Below is a simplified version of `AutocompleteMatch::GURLToStrippedGURL`
  108. // that is thread-safe, stateless, never hits the disk, a lot more aggressive,
  109. // and without a dependency on omnibox components.
  110. if (!url.is_valid())
  111. return url;
  112. GURL url_for_deduping = url;
  113. GURL::Replacements replacements;
  114. // Strip out www, but preserve the eTLD+1. This matches the omnibox behavior.
  115. // Make an explicit local, as a StringPiece can't point to a temporary.
  116. std::string stripped_host = url_formatter::StripWWW(url_for_deduping.host());
  117. replacements.SetHostStr(base::StringPiece(stripped_host));
  118. // Replace http protocol with https. It's just for deduplication.
  119. if (url_for_deduping.SchemeIs(url::kHttpScheme))
  120. replacements.SetSchemeStr(url::kHttpsScheme);
  121. // It's unusual to clear the query for deduping, because it's normally
  122. // considered a meaningful part of the URL. However, the return value of this
  123. // function isn't used naively. Details at `ClusterVisit::url_for_deduping`.
  124. if (url.has_query())
  125. replacements.ClearQuery();
  126. if (url.has_ref())
  127. replacements.ClearRef();
  128. url_for_deduping = url_for_deduping.ReplaceComponents(replacements);
  129. return url_for_deduping;
  130. }
  131. std::string ComputeURLKeywordForLookup(const GURL& url) {
  132. return history::VisitSegmentDatabase::ComputeSegmentName(
  133. ComputeURLForDeduping(url));
  134. }
  135. std::u16string ComputeURLForDisplay(const GURL& url, bool trim_after_host) {
  136. // Use URL formatting options similar to the omnibox popup. The url_formatter
  137. // component does IDN hostname conversion as well.
  138. url_formatter::FormatUrlTypes format_types =
  139. url_formatter::kFormatUrlOmitDefaults |
  140. url_formatter::kFormatUrlOmitHTTPS |
  141. url_formatter::kFormatUrlOmitTrivialSubdomains;
  142. if (trim_after_host)
  143. format_types |= url_formatter::kFormatUrlTrimAfterHost;
  144. return url_formatter::FormatUrl(url, format_types, base::UnescapeRule::SPACES,
  145. nullptr, nullptr, nullptr);
  146. }
  147. void StableSortVisits(std::vector<history::ClusterVisit>& visits) {
  148. base::ranges::stable_sort(visits, [](auto& v1, auto& v2) {
  149. if (v1.score != v2.score) {
  150. // Use v1 > v2 to get higher scored visits BEFORE lower scored visits.
  151. return v1.score > v2.score;
  152. }
  153. // Use v1 > v2 to get more recent visits BEFORE older visits.
  154. return v1.annotated_visit.visit_row.visit_time >
  155. v2.annotated_visit.visit_row.visit_time;
  156. });
  157. }
  158. void ApplySearchQuery(const std::string& query,
  159. std::vector<history::Cluster>& clusters) {
  160. if (query.empty())
  161. return;
  162. // Extract query nodes from the query string.
  163. query_parser::QueryNodeVector find_nodes;
  164. query_parser::QueryParser::ParseQueryNodes(
  165. base::UTF8ToUTF16(query),
  166. query_parser::MatchingAlgorithm::ALWAYS_PREFIX_SEARCH, &find_nodes);
  167. // Move all the passed in `clusters` into `all_clusters`, and start rebuilding
  168. // `clusters` to only contain the matching ones.
  169. std::vector<history::Cluster> all_clusters;
  170. std::swap(all_clusters, clusters);
  171. for (auto& cluster : all_clusters) {
  172. const float total_matching_visit_score =
  173. MarkMatchesAndGetScore(find_nodes, &cluster);
  174. DCHECK_GE(total_matching_visit_score, 0);
  175. if (total_matching_visit_score > 0 &&
  176. GetConfig().rescore_visits_within_clusters_for_query) {
  177. PromoteMatchingVisitsAboveNonMatchingVisits(cluster.visits);
  178. }
  179. cluster.search_match_score = total_matching_visit_score;
  180. if (DoesQueryMatchClusterKeywords(find_nodes, cluster.GetKeywords())) {
  181. // Arbitrarily chosen that cluster keyword matches are worth three points.
  182. // TODO(crbug.com/1307071): Use relevancy score for each cluster keyword
  183. // once support for that is added to the backend.
  184. cluster.search_match_score += 3.0;
  185. }
  186. if (cluster.search_match_score > 0) {
  187. // Move the matching clusters into the final list.
  188. clusters.push_back(std::move(cluster));
  189. }
  190. }
  191. if (GetConfig().sort_clusters_within_batch_for_query) {
  192. base::ranges::stable_sort(clusters, [](auto& c1, auto& c2) {
  193. // Use c1 > c2 to get higher scored clusters BEFORE lower scored clusters.
  194. return c1.search_match_score > c2.search_match_score;
  195. });
  196. }
  197. }
  198. void CullNonProminentOrDuplicateClusters(
  199. std::string query,
  200. std::vector<history::Cluster>& clusters,
  201. std::set<GURL>* seen_single_visit_cluster_urls) {
  202. DCHECK(seen_single_visit_cluster_urls);
  203. if (query.empty()) {
  204. // For the empty-query state, only show clusters with
  205. // `should_show_on_prominent_ui_surfaces` set to true. This restriction is
  206. // NOT applied when the user is searching for a specific keyword.
  207. clusters.erase(base::ranges::remove_if(
  208. clusters,
  209. [](const history::Cluster& cluster) {
  210. return !cluster.should_show_on_prominent_ui_surfaces;
  211. }),
  212. clusters.end());
  213. } else {
  214. clusters.erase(base::ranges::remove_if(
  215. clusters,
  216. [&](const history::Cluster& cluster) {
  217. // Erase all duplicate single-visit non-prominent
  218. // clusters.
  219. if (!cluster.should_show_on_prominent_ui_surfaces &&
  220. cluster.visits.size() == 1) {
  221. auto [unused_iterator, newly_inserted] =
  222. seen_single_visit_cluster_urls->insert(
  223. cluster.visits[0].url_for_deduping);
  224. return !newly_inserted;
  225. }
  226. return false;
  227. }),
  228. clusters.end());
  229. }
  230. }
  231. void HideAndCullLowScoringVisits(std::vector<history::Cluster>& clusters) {
  232. for (auto& cluster : clusters) {
  233. for (size_t i = 0; i < cluster.visits.size(); ++i) {
  234. auto& visit = cluster.visits[i];
  235. // Even a 0.0 visit shouldn't be hidden if this is the first visit we
  236. // encounter. The assumption is that the visits are always ranked by score
  237. // in a descending order.
  238. // TODO(crbug.com/1313631): Simplify this after removing "Show More" UI.
  239. if ((visit.score == 0.0 && i != 0) ||
  240. (visit.score < GetConfig().min_score_to_always_show_above_the_fold &&
  241. i >= GetConfig().num_visits_to_always_show_above_the_fold)) {
  242. visit.hidden = true;
  243. }
  244. }
  245. if (GetConfig().drop_hidden_visits) {
  246. cluster.visits.erase(
  247. base::ranges::remove_if(
  248. cluster.visits, [](const auto& visit) { return visit.hidden; }),
  249. cluster.visits.end());
  250. }
  251. }
  252. }
  253. void CoalesceRelatedSearches(std::vector<history::Cluster>& clusters) {
  254. constexpr size_t kMaxRelatedSearches = 5;
  255. for (auto& cluster : clusters) {
  256. for (const auto& visit : cluster.visits) {
  257. // Coalesce the unique related searches of this visit into the cluster
  258. // until the cap is reached.
  259. for (const auto& search_query :
  260. visit.annotated_visit.content_annotations.related_searches) {
  261. if (cluster.related_searches.size() >= kMaxRelatedSearches) {
  262. return;
  263. }
  264. if (!base::Contains(cluster.related_searches, search_query)) {
  265. cluster.related_searches.push_back(search_query);
  266. }
  267. }
  268. }
  269. }
  270. }
  271. } // namespace history_clusters