history_clusters_db_tasks.cc 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342
  1. // Copyright 2021 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_db_tasks.h"
  5. #include <algorithm>
  6. #include "base/containers/contains.h"
  7. #include "base/metrics/histogram_functions.h"
  8. #include "base/ranges/algorithm.h"
  9. #include "base/time/time.h"
  10. #include "base/timer/elapsed_timer.h"
  11. #include "components/history/core/browser/history_backend.h"
  12. #include "components/history/core/browser/history_database.h"
  13. #include "components/history/core/browser/history_types.h"
  14. #include "components/history_clusters/core/config.h"
  15. #include "components/history_clusters/core/history_clusters_types.h"
  16. namespace {
  17. // Is the transition user-visible.
  18. bool IsTransitionUserVisible(int32_t transition) {
  19. ui::PageTransition page_transition = ui::PageTransitionFromInt(transition);
  20. return (ui::PAGE_TRANSITION_CHAIN_END & transition) != 0 &&
  21. ui::PageTransitionIsMainFrame(page_transition) &&
  22. !ui::PageTransitionCoreTypeIs(page_transition,
  23. ui::PAGE_TRANSITION_KEYWORD_GENERATED);
  24. }
  25. } // namespace
  26. namespace history_clusters {
  27. // static
  28. base::Time GetAnnotatedVisitsToCluster::GetBeginTimeOnDayBoundary(
  29. base::Time time) {
  30. DCHECK(!time.is_null());
  31. // Subtract 16 hrs. Chosen to be halfway between boundaries; i.e. 4pm is 12
  32. // hrs from 4am. This guarantees fetching at least 12 hrs of visits regardless
  33. // of whether iterating recent or oldest visits first.
  34. time -= base::Hours(16);
  35. time = time.LocalMidnight();
  36. time += base::Hours(4);
  37. return time;
  38. }
  39. GetAnnotatedVisitsToCluster::GetAnnotatedVisitsToCluster(
  40. IncompleteVisitMap incomplete_visit_map,
  41. base::Time begin_time_limit,
  42. QueryClustersContinuationParams continuation_params,
  43. bool recent_first,
  44. int days_of_clustered_visits,
  45. bool recluster,
  46. Callback callback)
  47. : incomplete_visit_map_(incomplete_visit_map),
  48. begin_time_limit_(
  49. std::max(begin_time_limit, base::Time::Now() - base::Days(90))),
  50. continuation_params_(continuation_params),
  51. recent_first_(recent_first),
  52. days_of_clustered_visits_(days_of_clustered_visits),
  53. recluster_(recluster),
  54. callback_(std::move(callback)) {
  55. // Callers shouldn't ask for more visits if they've been exhausted.
  56. DCHECK(!continuation_params.exhausted_unclustered_visits);
  57. DCHECK_GE(days_of_clustered_visits_, 0);
  58. }
  59. GetAnnotatedVisitsToCluster::~GetAnnotatedVisitsToCluster() = default;
  60. bool GetAnnotatedVisitsToCluster::RunOnDBThread(
  61. history::HistoryBackend* backend,
  62. history::HistoryDatabase* db) {
  63. base::ElapsedThreadTimer query_visits_timer;
  64. // Because `base::Time::Now()` may change during the async history request,
  65. // and because determining whether history was exhausted depends on whether
  66. // the query reached `Now()`, `now` tracks `Now()` at the time the query
  67. // options were created.
  68. const auto now = base::Time::Now();
  69. // It's very unlikely for `now == begin_time_limit_`, but it's theoretically
  70. // possible if e.g. the keyword cooldown is set to 0ms, and it took 0ms from
  71. // initiating the `GetAnnotatedVisitsToCluster()` to reach here.
  72. if (now == begin_time_limit_) {
  73. continuation_params_.exhausted_unclustered_visits = true;
  74. continuation_params_.exhausted_all_visits = true;
  75. }
  76. history::QueryOptions options;
  77. // Accumulate 1 day at a time of visits to avoid breaking up clusters.
  78. while (annotated_visits_.empty() &&
  79. !continuation_params_.exhausted_unclustered_visits) {
  80. options = GetHistoryQueryOptions(backend, now);
  81. DCHECK(!options.begin_time.is_null());
  82. DCHECK(!options.end_time.is_null());
  83. DCHECK(options.begin_time != options.end_time);
  84. bool limited_by_max_count = AddUnclusteredVisits(backend, db, options);
  85. AddIncompleteVisits(backend, options.begin_time, options.end_time);
  86. IncrementContinuationParams(options, limited_by_max_count, now);
  87. }
  88. AddClusteredVisits(backend, db, options.begin_time);
  89. base::UmaHistogramTimes(
  90. "History.Clusters.Backend.QueryAnnotatedVisits.ThreadTime",
  91. query_visits_timer.Elapsed());
  92. return true;
  93. }
  94. history::QueryOptions GetAnnotatedVisitsToCluster::GetHistoryQueryOptions(
  95. history::HistoryBackend* backend,
  96. base::Time now) {
  97. history::QueryOptions options;
  98. // History Clusters wants a complete navigation graph and internally handles
  99. // de-duplication.
  100. options.duplicate_policy = history::QueryOptions::KEEP_ALL_DUPLICATES;
  101. // We hard cap at `options.max_count` which is enforced at the database level
  102. // to avoid any request getting too many visits causing OOM errors. See
  103. // https://crbug.com/1262016.
  104. options.max_count =
  105. GetConfig().max_visits_to_cluster - annotated_visits_.size();
  106. // Determine the begin & end times.
  107. // 1st, set `continuation_time`, either from `continuation_params_`for
  108. // continuation requests or computed for initial requests.
  109. base::Time continuation_time;
  110. if (continuation_params_.is_continuation) {
  111. continuation_time = continuation_params_.continuation_time;
  112. } else if (recent_first_) {
  113. continuation_time = now;
  114. } else {
  115. continuation_time =
  116. std::max(backend->FindMostRecentClusteredTime(), begin_time_limit_);
  117. }
  118. // 2nd, derive the other boundary, approximately 1 day before or after
  119. // `continuation_time`, depending on `recent_first`, and rounded to a day
  120. // boundary.
  121. if (recent_first_) {
  122. options.begin_time = GetBeginTimeOnDayBoundary(continuation_time);
  123. options.end_time = continuation_time;
  124. } else {
  125. options.begin_time = continuation_time;
  126. options.end_time =
  127. GetBeginTimeOnDayBoundary(continuation_time) + base::Days(2);
  128. }
  129. // 3rd, lastly, make sure the times don't surpass `begin_time_limit_` or
  130. // `now`.
  131. options.begin_time = std::clamp(options.begin_time, begin_time_limit_, now);
  132. options.end_time = std::clamp(options.end_time, begin_time_limit_, now);
  133. options.visit_order = recent_first_
  134. ? history::QueryOptions::VisitOrder::RECENT_FIRST
  135. : history::QueryOptions::VisitOrder::OLDEST_FIRST;
  136. return options;
  137. }
  138. bool GetAnnotatedVisitsToCluster::AddUnclusteredVisits(
  139. history::HistoryBackend* backend,
  140. history::HistoryDatabase* db,
  141. history::QueryOptions options) {
  142. bool limited_by_max_count = false;
  143. for (const auto& visit :
  144. backend->GetAnnotatedVisits(options, &limited_by_max_count)) {
  145. const bool is_clustered =
  146. GetConfig().persist_clusters_in_history_db && !recluster_
  147. ? db->GetClusterIdContainingVisit(visit.visit_row.visit_id) > 0
  148. : false;
  149. if (is_clustered && recent_first_)
  150. continuation_params_.exhausted_unclustered_visits = true;
  151. // Filter out visits from sync.
  152. // TODO(manukh): Consider allowing the clustering backend to handle sync
  153. // visits.
  154. if (!is_clustered && visit.source != history::SOURCE_SYNCED)
  155. annotated_visits_.push_back(std::move(visit));
  156. }
  157. return limited_by_max_count;
  158. }
  159. void GetAnnotatedVisitsToCluster::AddIncompleteVisits(
  160. history::HistoryBackend* backend,
  161. base::Time begin_time,
  162. base::Time end_time) {
  163. // Now we have enough visits for clustering, add all incomplete visits
  164. // between the current `options.begin_time` and `original_end_time`, as
  165. // otherwise they will be mysteriously missing from the Clusters UI. They
  166. // haven't recorded the page end metrics yet, but that's fine. Filter
  167. // incomplete visits to those that have a `url_row`, have a `visit_row`, and
  168. // match `options`.
  169. for (const auto& item : incomplete_visit_map_) {
  170. auto& incomplete_visit_context_annotations = item.second;
  171. // Discard incomplete visits that don't have a `url_row` and `visit_row`.
  172. // It's possible that the `url_row` and `visit_row` will be available
  173. // before they're needed (i.e. before
  174. // `GetAnnotatedVisitsToCluster::RunOnDBThread()`). But since it'll only
  175. // have a copy of the incomplete context annotations, the copy won't have
  176. // the fields updated. A weak ptr won't help since it can't be accessed on
  177. // different threads. A `scoped_refptr` could work. However, only very
  178. // recently opened tabs won't have the rows set, so we don't bother using
  179. // `scoped_refptr`s.
  180. if (!incomplete_visit_context_annotations.status.history_rows)
  181. continue;
  182. // Discard incomplete visits outside the time bounds of the actual visits
  183. // we fetched, accounting for the fact that we may have been limited by
  184. // `options.max_count`.
  185. const auto& visit_time =
  186. incomplete_visit_context_annotations.visit_row.visit_time;
  187. if (visit_time < begin_time || visit_time >= end_time)
  188. continue;
  189. // Discard any incomplete visits that were already fetched from History.
  190. // This can happen when History finishes writing the rows after we snapshot
  191. // the incomplete visits at the beginning of this task.
  192. // https://crbug.com/1252047.
  193. history::VisitID visit_id =
  194. incomplete_visit_context_annotations.visit_row.visit_id;
  195. if (base::Contains(annotated_visits_, visit_id, [](const auto& visit) {
  196. return visit.visit_row.visit_id;
  197. })) {
  198. continue;
  199. }
  200. // Discard any incomplete visits that are not visible to the user.
  201. if (!IsTransitionUserVisible(
  202. incomplete_visit_context_annotations.visit_row.transition)) {
  203. continue;
  204. }
  205. // Compute `referring_visit_of_redirect_chain_start` for each incomplete
  206. // visit.
  207. const auto& first_redirect = backend->GetRedirectChainStart(
  208. incomplete_visit_context_annotations.visit_row);
  209. // Compute `visit_source` for each incomplete visit.
  210. history::VisitSource visit_source;
  211. backend->GetVisitSource(
  212. incomplete_visit_context_annotations.visit_row.visit_id, &visit_source);
  213. annotated_visits_.push_back(
  214. {incomplete_visit_context_annotations.url_row,
  215. incomplete_visit_context_annotations.visit_row,
  216. incomplete_visit_context_annotations.context_annotations,
  217. // TODO(tommycli): Add content annotations.
  218. {},
  219. first_redirect.referring_visit,
  220. first_redirect.opener_visit,
  221. visit_source});
  222. }
  223. }
  224. void GetAnnotatedVisitsToCluster::IncrementContinuationParams(
  225. history::QueryOptions options,
  226. bool limited_by_max_count,
  227. base::Time now) {
  228. continuation_params_.is_continuation = true;
  229. // If `limited_by_max_count` is true, `annotated_visits_` "shouldn't" be
  230. // empty. But it actually can be if a visit's URL is missing from the URL
  231. // table. `limited_by_max_count` is set before visits are filtered to
  232. // those whose URL is found.
  233. // TODO(manukh): We shouldn't skip the day's remaining visits when
  234. // `annotated_visits_` is empty.
  235. if (limited_by_max_count && !annotated_visits_.empty()) {
  236. continuation_params_.continuation_time =
  237. annotated_visits_.back().visit_row.visit_time;
  238. continuation_params_.is_partial_day = true;
  239. } else {
  240. DCHECK(!continuation_params_.exhausted_unclustered_visits || recent_first_);
  241. // Prepare `continuation_time` for the next day of visits. It will include
  242. // all unclustered visits iterated. Except, if `exhausted_unclustered_visits
  243. // is true, which is only possible if `recent_first_` is true and it just
  244. // reached the clustering boundary, then prepare `continuation_time` to
  245. // re-iterate the last iterated day, as the to include the clustered visits
  246. // of that day.
  247. continuation_params_.continuation_time =
  248. (recent_first_ && !continuation_params_.exhausted_unclustered_visits)
  249. ? options.begin_time
  250. : options.end_time;
  251. continuation_params_.is_partial_day = false;
  252. // We've exhausted history if we've reached `begin_time_limit_` (bound to be
  253. // at most 90 days old) or `Now()`. This does not necessarily mean we've
  254. // added all visits; e.g. `begin_time_limit_` can be more recent than 90
  255. // days ago or the initial `continuation_end_time_` could have been older
  256. // than now.
  257. if ((continuation_params_.continuation_time <= begin_time_limit_ &&
  258. recent_first_) ||
  259. (continuation_params_.continuation_time >= now && !recent_first_)) {
  260. continuation_params_.exhausted_unclustered_visits = true;
  261. continuation_params_.exhausted_all_visits = true;
  262. }
  263. }
  264. }
  265. void GetAnnotatedVisitsToCluster::AddClusteredVisits(
  266. history::HistoryBackend* backend,
  267. history::HistoryDatabase* db,
  268. base::Time unclustered_begin_time) {
  269. if (annotated_visits_.empty() ||
  270. annotated_visits_.size() >=
  271. static_cast<size_t>(GetConfig().max_visits_to_cluster) ||
  272. days_of_clustered_visits_ == 0) {
  273. return;
  274. }
  275. // Get the clusters within `days_of_clustered_visits_` days older than the
  276. // unclustered visits.
  277. const auto cluster_ids = db->GetMostRecentClusterIds(
  278. unclustered_begin_time - base::Days(days_of_clustered_visits_),
  279. unclustered_begin_time, 1000);
  280. // If we found a cluster and are iterating recent_first_, then we've reached
  281. // the cluster threshold and have no more unclustered visits remaining.
  282. if (!cluster_ids.empty() && recent_first_)
  283. continuation_params_.exhausted_unclustered_visits = true;
  284. // Add the clustered visits, adding 1 cluster at a time so that partial
  285. // clusters aren't added.
  286. for (const auto cluster_id : cluster_ids) {
  287. const auto visit_ids_of_cluster = db->GetVisitIdsInCluster(cluster_id);
  288. if (annotated_visits_.size() + visit_ids_of_cluster.size() >
  289. static_cast<size_t>(GetConfig().max_visits_to_cluster))
  290. break;
  291. cluster_ids_.push_back(cluster_id);
  292. base::ranges::move(backend->ToAnnotatedVisits(visit_ids_of_cluster),
  293. std::back_inserter(annotated_visits_));
  294. }
  295. }
  296. void GetAnnotatedVisitsToCluster::DoneRunOnMainThread() {
  297. std::move(callback_).Run(cluster_ids_, annotated_visits_,
  298. continuation_params_);
  299. }
  300. } // namespace history_clusters