1// Copyright (c) 2012 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
5#include "chrome/browser/history/visit_filter.h"
6
7#include <math.h>
8
9#include "base/logging.h"
10#include "base/time/time.h"
11#include "components/history/core/browser/history_types.h"
12#include "testing/gtest/include/gtest/gtest.h"
13
14namespace {
15
16// So the tests won't go into the other day +/- several hours, return midday of
17// today.
18base::Time GetClosestMidday() {
19  return base::Time::Now().LocalMidnight() + base::TimeDelta::FromHours(12);
20}
21
22}  // namespace
23
24namespace history {
25
26class VisitFilterTest : public testing::Test {
27 public:
28  VisitFilterTest();
29
30 protected:
31  virtual void SetUp();
32  virtual void TearDown();
33};
34
35VisitFilterTest::VisitFilterTest() {
36}
37
38void VisitFilterTest::SetUp() {
39}
40
41void VisitFilterTest::TearDown() {
42}
43
44TEST_F(VisitFilterTest, CheckFilters) {
45  base::Time t(GetClosestMidday());
46  base::TimeDelta two_hours(base::TimeDelta::FromHours(2));
47  VisitFilter f;
48  f.set_max_results(21U);
49  f.SetFilterTime(t);
50  f.SetFilterWidth(two_hours);
51  EXPECT_EQ(21U, f.times().size());
52  for (size_t i = 0; i < f.times().size(); ++i) {
53    base::Time t_interval(t);
54    t_interval -= base::TimeDelta::FromDays(i);
55    EXPECT_EQ(t_interval - two_hours, f.times()[i].first) <<
56        "Fails at index:" << i;
57    EXPECT_EQ(t_interval + two_hours, f.times()[i].second) <<
58        "Fails at index:" << i;
59  }
60  base::Time::Exploded et;
61  t.LocalExplode(&et);
62  f.SetDayOfTheWeekFilter(et.day_of_week);
63  // 3 weeks in 21 days.
64  ASSERT_EQ(3U, f.times().size());
65  for (size_t i = 1; i < f.times().size(); ++i) {
66    base::Time t_interval(t);
67    t_interval -= base::TimeDelta::FromDays(i);
68    EXPECT_EQ(f.times()[i].first + base::TimeDelta::FromDays(7),
69              f.times()[i - 1].first) <<
70        "Fails at index:" << i;
71    EXPECT_EQ(f.times()[i].second + base::TimeDelta::FromDays(7),
72              f.times()[i - 1].second) <<
73        "Fails at index:" << i;
74    EXPECT_EQ(two_hours * 2,
75              f.times()[i].second - f.times()[i].first) <<
76        "Fails at index:" << i;
77  }
78}
79
80TEST_F(VisitFilterTest, GetTimesInRange) {
81  base::Time::Exploded et = { 2011, 7, 0, 19, 22, 15, 11, 0 };
82  base::Time t(base::Time::FromLocalExploded(et));
83  base::TimeDelta two_hours(base::TimeDelta::FromHours(2));
84  VisitFilter::TimeVector times;
85  VisitFilter::GetTimesInRange(t - two_hours, t + two_hours, 10U, &times);
86  EXPECT_GT(11U, times.size());
87  for (size_t i = 0; i < times.size(); ++i) {
88    base::Time t_interval(t);
89    t_interval -= base::TimeDelta::FromDays(i);
90    EXPECT_EQ(t_interval - two_hours, times[i].first) << "Fails at index:" << i;
91    EXPECT_EQ(t_interval + two_hours, times[i].second) <<
92        "Fails at index:" << i;
93  }
94}
95
96TEST_F(VisitFilterTest, GetTimesOnTheDayOfTheWeek) {
97  base::Time t(GetClosestMidday());
98  VisitFilter::TimeVector times;
99  base::Time::Exploded et;
100  t.LocalExplode(&et);
101  VisitFilter::GetTimesOnTheDayOfTheWeek(et.day_of_week, t, 10U, &times);
102  EXPECT_GT(11U, times.size());
103  et.hour = 0;
104  et.minute = 0;
105  et.second = 0;
106  et.millisecond = 0;
107  for (size_t i = 0; i < times.size(); ++i) {
108    base::Time t_interval(base::Time::FromLocalExploded(et));
109    t_interval -= base::TimeDelta::FromDays(7 * i);
110    EXPECT_EQ(t_interval, times[i].first) << "Fails at index:" << i;
111    EXPECT_EQ(t_interval + base::TimeDelta::FromDays(1), times[i].second) <<
112        "Fails at index:" << i;
113  }
114}
115
116TEST_F(VisitFilterTest, GetTimesOnTheSameDayType) {
117  base::Time::Exploded et = { 2011, 7, 0, 19, 22, 15, 11, 0 };
118  base::Time t(base::Time::FromLocalExploded(et));
119  VisitFilter::TimeVector times;
120  t.LocalExplode(&et);
121  VisitFilter::GetTimesOnTheSameDayType(et.day_of_week, t, 10U, &times);
122  EXPECT_GT(11U, times.size());
123  et.hour = 0;
124  et.minute = 0;
125  et.second = 0;
126  et.millisecond = 0;
127  base::Time t_start(base::Time::FromLocalExploded(et));
128  base::TimeDelta t_length;
129  if (et.day_of_week == 0 || et.day_of_week == 6) {
130    // Sunday and Saturday.
131    t_length = base::TimeDelta::FromDays(2);
132    if (et.day_of_week == 0)
133      t_start -= base::TimeDelta::FromDays(1);
134  } else {
135    t_length = base::TimeDelta::FromDays(5);
136    if (et.day_of_week != 1)
137      t_start -= base::TimeDelta::FromDays(et.day_of_week - 1);
138  }
139  for (size_t i = 0; i < times.size(); ++i) {
140    base::Time t_interval(t_start);
141    t_interval -= base::TimeDelta::FromDays(7 * i);
142    EXPECT_EQ(t_interval, times[i].first) << "Fails at index:" << i;
143    EXPECT_EQ(t_interval + t_length, times[i].second) << "Fails at index:" << i;
144  }
145}
146
147TEST_F(VisitFilterTest, UniteTimeVectors) {
148  base::Time t(base::Time::Now());
149  base::TimeDelta one_hour(base::TimeDelta::FromHours(1));
150  base::TimeDelta one_day(base::TimeDelta::FromDays(1));
151  VisitFilter::TimeVector times1;
152  times1.push_back(std::make_pair(t - one_hour, t + one_hour));
153  times1.push_back(std::make_pair(t - one_hour - one_day,
154                                  t + one_hour - one_day));
155  times1.push_back(std::make_pair(t - one_hour - one_day * 2,
156                                  t + one_hour - one_day * 2));
157  times1.push_back(std::make_pair(t - one_hour - one_day * 3,
158                                  t + one_hour - one_day * 3));
159
160  VisitFilter::TimeVector times2;
161  // Should lie completely within times1[0].
162  times2.push_back(std::make_pair(t - one_hour / 2, t + one_hour / 2));
163  // Should lie just before times1[1].
164  times2.push_back(std::make_pair(t + one_hour * 2 - one_day,
165                                  t + one_hour * 3 - one_day));
166  // Should intersect with times1.
167  times2.push_back(std::make_pair(t - one_day * 2,
168                                  t + one_hour * 2 - one_day * 2));
169  times2.push_back(std::make_pair(t - one_hour * 2 - one_day * 3,
170                                  t - one_day * 3));
171
172  VisitFilter::TimeVector result;
173  EXPECT_TRUE(VisitFilter::UniteTimeVectors(times1, times2, &result));
174  ASSERT_EQ(5U, result.size());
175  EXPECT_EQ(t - one_hour, result[0].first);
176  EXPECT_EQ(t + one_hour, result[0].second);
177  EXPECT_EQ(t + one_hour * 2 - one_day, result[1].first);
178  EXPECT_EQ(t + one_hour * 3 - one_day, result[1].second);
179  EXPECT_EQ(t - one_hour - one_day, result[2].first);
180  EXPECT_EQ(t + one_hour - one_day, result[2].second);
181  EXPECT_EQ(t - one_hour - one_day * 2, result[3].first);
182  EXPECT_EQ(t + one_hour * 2 - one_day * 2, result[3].second);
183  EXPECT_EQ(t - one_hour * 2 - one_day * 3, result[4].first);
184  EXPECT_EQ(t + one_hour - one_day * 3, result[4].second);
185
186  EXPECT_FALSE(VisitFilter::UniteTimeVectors(VisitFilter::TimeVector(),
187                                             VisitFilter::TimeVector(),
188                                             &result));
189  EXPECT_TRUE(result.empty());
190}
191
192TEST_F(VisitFilterTest, IntersectTimeVectors) {
193  base::Time t(base::Time::Now());
194  base::TimeDelta one_hour(base::TimeDelta::FromHours(1));
195  base::TimeDelta one_day(base::TimeDelta::FromDays(1));
196  VisitFilter::TimeVector times1;
197  times1.push_back(std::make_pair(t - one_hour, t + one_hour));
198
199  VisitFilter::TimeVector times2;
200  // Should lie just before times1[0].
201  times2.push_back(std::make_pair(t + one_hour * 2,
202                                  t + one_hour * 3));
203
204  VisitFilter::TimeVector result;
205  EXPECT_FALSE(VisitFilter::IntersectTimeVectors(times1, times2, &result));
206  EXPECT_TRUE(result.empty());
207
208  times1.push_back(std::make_pair(t - one_hour - one_day,
209                                  t + one_hour - one_day));
210  times1.push_back(std::make_pair(t - one_hour - one_day * 2,
211                                  t + one_hour - one_day * 2));
212  times1.push_back(std::make_pair(t - one_hour - one_day * 3,
213                                  t + one_hour - one_day * 3));
214
215  // Should lie completely within times1[1].
216  times2.push_back(std::make_pair(t - one_hour / 2 - one_day,
217                                  t + one_hour / 2 - one_day));
218  // Should intersect with times1.
219  times2.push_back(std::make_pair(t - one_day * 2,
220                                  t + one_hour * 2 - one_day * 2));
221  times2.push_back(std::make_pair(t - one_hour * 2 - one_day * 3,
222                                  t - one_day * 3));
223
224  EXPECT_TRUE(VisitFilter::IntersectTimeVectors(times1, times2, &result));
225  ASSERT_EQ(3U, result.size());
226  EXPECT_EQ(t - one_hour / 2 - one_day, result[0].first);
227  EXPECT_EQ(t + one_hour / 2 - one_day, result[0].second);
228  EXPECT_EQ(t - one_day * 2, result[1].first);
229  EXPECT_EQ(t + one_hour - one_day * 2, result[1].second);
230  EXPECT_EQ(t - one_hour - one_day * 3, result[2].first);
231  EXPECT_EQ(t - one_day * 3, result[2].second);
232
233  // Check that touching ranges do not intersect.
234  times1.clear();
235  times1.push_back(std::make_pair(t - one_hour, t));
236  times2.clear();
237  times2.push_back(std::make_pair(t, t + one_hour));
238  EXPECT_FALSE(VisitFilter::IntersectTimeVectors(times1, times2, &result));
239  EXPECT_TRUE(result.empty());
240}
241
242TEST_F(VisitFilterTest, GetVisitScore) {
243  base::Time filter_time;
244  ASSERT_TRUE(base::Time::FromString("Tue, 24 Apr 2012, 12:00:00",
245                                     &filter_time));
246  VisitFilter filter;
247  VisitRow visit;
248
249  filter.set_sorting_order(VisitFilter::ORDER_BY_RECENCY);
250  filter.SetFilterTime(filter_time);
251  filter.SetFilterWidth(base::TimeDelta::FromHours(1));
252
253  double one_week_one_hour_staleness = pow(2, -(24.0 * 7.0 + 1.0) /
254                                               (24.0 * 7.0));
255
256  // No decay on current visit.
257  visit.visit_time = filter_time;
258  EXPECT_DOUBLE_EQ(1.0, filter.GetVisitScore(visit));
259  // Half score after a week.
260  visit.visit_time = filter_time - base::TimeDelta::FromDays(7);
261  EXPECT_DOUBLE_EQ(0.5, filter.GetVisitScore(visit));
262  // Future visits should be treated as current.
263  visit.visit_time = filter_time + base::TimeDelta::FromDays(1);
264  EXPECT_DOUBLE_EQ(1.0, filter.GetVisitScore(visit));
265
266  filter.set_sorting_order(VisitFilter::ORDER_BY_VISIT_COUNT);
267  // Every visit should score 1 with this filter.
268  visit.visit_time = filter_time;
269  EXPECT_DOUBLE_EQ(1.0, filter.GetVisitScore(visit));
270  visit.visit_time = filter_time - base::TimeDelta::FromDays(7);
271  EXPECT_DOUBLE_EQ(1.0, filter.GetVisitScore(visit));
272  visit.visit_time = filter_time + base::TimeDelta::FromDays(7);
273  EXPECT_DOUBLE_EQ(1.0, filter.GetVisitScore(visit));
274
275  filter.set_sorting_order(VisitFilter::ORDER_BY_TIME_LINEAR);
276  visit.visit_time = filter_time;
277  EXPECT_DOUBLE_EQ(1.0, filter.GetVisitScore(visit));
278  // Half the filter width forward in time should get half the score for the
279  // time difference, but no staleness decay.
280  visit.visit_time = filter_time + base::TimeDelta::FromMinutes(30);
281  EXPECT_DOUBLE_EQ(0.5, filter.GetVisitScore(visit));
282  // One week back in time gets full time difference score, but a staleness
283  // factor of 0.5
284  visit.visit_time = filter_time - base::TimeDelta::FromDays(7);
285  EXPECT_DOUBLE_EQ(0.5, filter.GetVisitScore(visit));
286  // One week plus half a filter width should have it's score halved before
287  // the staleness factor.
288  filter.SetFilterWidth(base::TimeDelta::FromHours(2));
289  visit.visit_time = filter_time - base::TimeDelta::FromDays(7) -
290                     base::TimeDelta::FromHours(1);
291  EXPECT_DOUBLE_EQ(0.5 * one_week_one_hour_staleness,
292                   filter.GetVisitScore(visit));
293  filter.SetFilterWidth(base::TimeDelta::FromHours(1));
294
295  filter.set_sorting_order(VisitFilter::ORDER_BY_TIME_GAUSSIAN);
296  visit.visit_time = filter_time;
297  EXPECT_DOUBLE_EQ(1.0, filter.GetVisitScore(visit));
298  // Going forward in time to test the normal distribution function.
299  visit.visit_time = filter_time + base::TimeDelta::FromHours(1);
300  EXPECT_DOUBLE_EQ(exp(-0.5), filter.GetVisitScore(visit));
301  visit.visit_time = filter_time + base::TimeDelta::FromMinutes(30);
302  EXPECT_DOUBLE_EQ(exp(-0.125), filter.GetVisitScore(visit));
303  // One week back in time gets full time difference score, but a staleness
304  // factor of 0.5
305  visit.visit_time = filter_time - base::TimeDelta::FromDays(7);
306  EXPECT_DOUBLE_EQ(0.5, filter.GetVisitScore(visit));
307  // One standard deviation of decay, plus the staleness factor.
308  visit.visit_time = filter_time - base::TimeDelta::FromDays(7) -
309                     base::TimeDelta::FromHours(1);
310  EXPECT_DOUBLE_EQ(exp(-0.5) * one_week_one_hour_staleness,
311                   filter.GetVisitScore(visit));
312}
313
314}  // namespace history
315