1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
// Copyright 2021 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "components/history_clusters/core/clusterer.h"
#include <unordered_map>
#include "base/containers/adapters.h"
#include "components/history/core/browser/history_types.h"
#include "components/history_clusters/core/config.h"
#include "components/history_clusters/core/on_device_clustering_features.h"
#include "components/history_clusters/core/similar_visit.h"
namespace history_clusters {
namespace {
// Returns whether |visit| should be added to |cluster|.
bool ShouldAddVisitToCluster(const history::ClusterVisit& visit,
const history::Cluster& cluster) {
if ((visit.annotated_visit.visit_row.visit_time -
cluster.visits.back().annotated_visit.visit_row.visit_time) >
GetConfig().cluster_navigation_time_cutoff) {
return false;
}
if (!visit.annotated_visit.content_annotations.search_terms.empty()) {
// If we want to split the clusters at search visits and we are at a search
// visit, only add the visit to the cluster if the last search visit was
// also a search visit with the same terms. Also break the cluster if there
// was not already a search visit already.
for (const auto& existing_visit : base::Reversed(cluster.visits)) {
if (!existing_visit.annotated_visit.content_annotations.search_terms
.empty()) {
return existing_visit.annotated_visit.content_annotations
.search_terms ==
visit.annotated_visit.content_annotations.search_terms;
}
}
return false;
}
return true;
}
} // namespace
Clusterer::Clusterer() = default;
Clusterer::~Clusterer() = default;
std::vector<history::Cluster> Clusterer::CreateInitialClustersFromVisits(
std::vector<history::ClusterVisit> visits) {
// Sort visits by visit time.
std::sort(visits.begin(), visits.end(),
[](const history::ClusterVisit& a, const history::ClusterVisit& b) {
return a.annotated_visit.visit_row < b.annotated_visit.visit_row;
});
std::unordered_map<SimilarVisit, size_t, SimilarVisit::Hash,
SimilarVisit::Equals>
similar_visit_to_cluster_map;
base::flat_map<history::VisitID, size_t> visit_id_to_cluster_map;
std::vector<history::Cluster> clusters;
for (auto& visit : visits) {
std::optional<size_t> cluster_idx;
std::vector<history::VisitID> previous_visit_ids_to_check;
if (visit.annotated_visit.opener_visit_of_redirect_chain_start != 0) {
previous_visit_ids_to_check.push_back(
visit.annotated_visit.opener_visit_of_redirect_chain_start);
}
if (visit.annotated_visit.referring_visit_of_redirect_chain_start != 0) {
previous_visit_ids_to_check.push_back(
visit.annotated_visit.referring_visit_of_redirect_chain_start);
}
if (!previous_visit_ids_to_check.empty()) {
// See if we have clustered any of the previous visits with opener taking
// precedence.
for (history::VisitID previous_visit_id : previous_visit_ids_to_check) {
auto it = visit_id_to_cluster_map.find(previous_visit_id);
if (it != visit_id_to_cluster_map.end()) {
cluster_idx = it->second;
break;
}
}
} else {
// See if we have clustered the URL. (forward-back, reload, etc.)
auto it = similar_visit_to_cluster_map.find(SimilarVisit(visit));
if (it != similar_visit_to_cluster_map.end()) {
cluster_idx = it->second;
}
}
DCHECK(!cluster_idx || (*cluster_idx < clusters.size()));
// Even if above conditions were met, see if we should add it to the cluster
// based on the characteristics of the in progress cluster and the current
// visit we are processing.
if (cluster_idx) {
auto& in_progress_cluster = clusters[*cluster_idx];
if (!ShouldAddVisitToCluster(visit, in_progress_cluster)) {
// Erase all visits in the cluster from the maps since we no longer
// want to consider anything in the cluster as a referrer.
for (const auto& finalized_visit : in_progress_cluster.visits) {
visit_id_to_cluster_map.erase(
finalized_visit.annotated_visit.visit_row.visit_id);
similar_visit_to_cluster_map.erase(SimilarVisit(finalized_visit));
}
// Reset the working cluster index so we start a new cluster for this
// visit.
cluster_idx = std::nullopt;
}
}
if (!cluster_idx) {
// Create a new cluster.
cluster_idx = clusters.size();
history::Cluster new_cluster;
clusters.push_back(std::move(new_cluster));
}
// Add to mapping.
visit_id_to_cluster_map[visit.annotated_visit.visit_row.visit_id] =
*cluster_idx;
similar_visit_to_cluster_map[SimilarVisit(visit)] = *cluster_idx;
// By default, the current visit will be assigned a max score of 1.0 until
// otherwise scored during finalization.
visit.score = 1.0;
// Add to its cluster.
clusters[*cluster_idx].visits.push_back(std::move(visit));
}
return clusters;
}
} // namespace history_clusters
|
