Home | History | Annotate | Download | only in history 
      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 "chrome/browser/history/history_types.h"
     12 #include "testing/gtest/include/gtest/gtest.h"
     13 
     14 namespace {
     15 
     16 // So the tests won't go into the other day +/- several hours, return midday of
     17 // today.
     18 base::Time GetClosestMidday() {
     19   return base::Time::Now().LocalMidnight() + base::TimeDelta::FromHours(12);
     20 }
     21 
     22 }  // namespace
     23 
     24 namespace history {
     25 
     26 class VisitFilterTest : public testing::Test {
     27  public:
     28   VisitFilterTest();
     29 
     30  protected:
     31   virtual void SetUp();
     32   virtual void TearDown();
     33 };
     34 
     35 VisitFilterTest::VisitFilterTest() {
     36 }
     37 
     38 void VisitFilterTest::SetUp() {
     39 }
     40 
     41 void VisitFilterTest::TearDown() {
     42 }
     43 
     44 TEST_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 
     80 TEST_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 
     96 TEST_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 
    116 TEST_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 
    147 TEST_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 
    192 TEST_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 
    242 TEST_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