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 #ifndef COMPONENTS_OMNIBOX_BROWSER_SCORED_HISTORY_MATCH_H_
6 #define COMPONENTS_OMNIBOX_BROWSER_SCORED_HISTORY_MATCH_H_
7 
8 #include <stddef.h>
9 
10 #include <string>
11 #include <utility>
12 #include <vector>
13 
14 #include "base/gtest_prod_util.h"
15 #include "base/strings/string16.h"
16 #include "base/strings/utf_offset_string_conversions.h"
17 #include "base/time/time.h"
18 #include "components/history/core/browser/history_types.h"
19 #include "components/omnibox/browser/history_match.h"
20 #include "components/omnibox/browser/in_memory_url_index_types.h"
21 #include "components/omnibox/browser/omnibox_field_trial.h"
22 
23 class ScoredHistoryMatchTest;
24 
25 // An HistoryMatch that has a score as well as metrics defining where in the
26 // history item's URL and/or page title matches have occurred.
27 struct ScoredHistoryMatch : public history::HistoryMatch {
28   // ScoreMaxRelevance maps from an intermediate-score to the maximum
29   // final-relevance score given to a URL for this intermediate score.
30   // This is used to store the score ranges of relevance buckets.
31   // Please see GetFinalRelevancyScore() for details.
32   using ScoreMaxRelevance = std::pair<double, int>;
33 
34   // A sorted vector of ScoreMaxRelevance entries, used by taking a score and
35   // interpolating between consecutive buckets.  See GetFinalRelevancyScore()
36   // for details.
37   using ScoreMaxRelevances = std::vector<ScoreMaxRelevance>;
38 
39   // Required for STL, we don't use this directly.
40   ScoredHistoryMatch();
41   ScoredHistoryMatch(const ScoredHistoryMatch& other);
42   ScoredHistoryMatch(ScoredHistoryMatch&& other);
43   ScoredHistoryMatch& operator=(const ScoredHistoryMatch& other);
44   ScoredHistoryMatch& operator=(ScoredHistoryMatch&& other);
45 
46   // Initializes the ScoredHistoryMatch with a raw score calculated for the
47   // history item given in |row| with recent visits as indicated in |visits|. It
48   // first determines if the row qualifies by seeing if all of the terms in
49   // |terms_vector| occur in |row|.  If so, calculates a raw score.  This raw
50   // score is in part determined by whether the matches occur at word
51   // boundaries, the locations of which are stored in |word_starts|.  For some
52   // terms, it's appropriate to look for the word boundary within the term. For
53   // instance, the term ".net" should look for a word boundary at the "n".
54   // These offsets (".net" should have an offset of 1) come from
55   // |terms_to_word_starts_offsets|. |is_url_bookmarked| indicates whether the
56   // match's URL is referenced by any bookmarks, which can also affect the raw
57   // score.  |num_matching_pages| indicates how many URLs in the eligible URL
58   // database match the user's input; it can also affect the raw score.  The raw
59   // score allows the matches to be ordered and can be used to influence the
60   // final score calculated by the client of this index.  If the row does not
61   // qualify the raw score will be 0.
62   ScoredHistoryMatch(const history::URLRow& row,
63                      const VisitInfoVector& visits,
64                      const base::string16& lower_string,
65                      const String16Vector& terms_vector,
66                      const WordStarts& terms_to_word_starts_offsets,
67                      const RowWordStarts& word_starts,
68                      bool is_url_bookmarked,
69                      size_t num_matching_pages,
70                      base::Time now);
71 
72   ~ScoredHistoryMatch();
73 
74   // Compares two matches by score.  Functor supporting URLIndexPrivateData's
75   // HistoryItemsForTerms function.  Looks at particular fields within
76   // with url_info to make tie-breaking a bit smarter.
77   static bool MatchScoreGreater(const ScoredHistoryMatch& m1,
78                                 const ScoredHistoryMatch& m2);
79 
80   // Returns |term_matches| after removing all matches that are not at a
81   // word break that are in the range [|start_pos|, |end_pos|).
82   // start_pos == string::npos is treated as start_pos = length of string.
83   // (In other words, no matches will be filtered.)
84   // end_pos == string::npos is treated as end_pos = length of string. If
85   // |allow_midword_continuations| is true, matches not at a word break are not
86   // filtered if they continue where the previous match ended.
87   static TermMatches FilterTermMatchesByWordStarts(
88       const TermMatches& term_matches,
89       const WordStarts& terms_to_word_starts_offsets,
90       const WordStarts& word_starts,
91       size_t start_pos,
92       size_t end_pos,
93       bool allow_midword_continuations = false);
94 
95   // An interim score taking into consideration location and completeness
96   // of the match.
97   int raw_score;
98 
99   // Both these TermMatches contain the set of matches that are considered
100   // important.  At this time, that means they exclude mid-word matches
101   // except in the hostname of the URL.  (Technically, during early
102   // construction of ScoredHistoryMatch, they may contain all matches, but
103   // unimportant matches are eliminated by GetTopicalityScore(), called
104   // during construction.)
105 
106   // Term matches within the URL.
107   TermMatches url_matches;
108   // Term matches within the page title.
109   TermMatches title_matches;
110 
111  private:
112   friend class ScoredHistoryMatchTest;
113   FRIEND_TEST_ALL_PREFIXES(ScoredHistoryMatchTest, GetDocumentSpecificityScore);
114   FRIEND_TEST_ALL_PREFIXES(ScoredHistoryMatchTest, GetFinalRelevancyScore);
115   FRIEND_TEST_ALL_PREFIXES(ScoredHistoryMatchTest, GetFrequency);
116   FRIEND_TEST_ALL_PREFIXES(ScoredHistoryMatchTest, GetHQPBucketsFromString);
117   FRIEND_TEST_ALL_PREFIXES(ScoredHistoryMatchTest, ScoringBookmarks);
118   FRIEND_TEST_ALL_PREFIXES(ScoredHistoryMatchTest, ScoringScheme);
119   FRIEND_TEST_ALL_PREFIXES(ScoredHistoryMatchTest, ScoringTLD);
120 
121   // Initialize ScoredHistoryMatch statics. Must be called before any other
122   // method of ScoredHistoryMatch and before creating any instances.
123   static void Init();
124 
125   // Return a topicality score based on how many matches appear in the url and
126   // the page's title and where they are (e.g., at word boundaries).  Revises
127   // url_matches and title_matches in the process so they only reflect matches
128   // used for scoring.  (For instance, some mid-word matches are not given
129   // credit in scoring.)  Requires that |url_matches| and |title_matches| are
130   // sorted. |adjustments| must contain any adjustments used to format |url|.
131   float GetTopicalityScore(const int num_terms,
132                            const GURL& url,
133                            const base::OffsetAdjuster::Adjustments& adjustments,
134                            const WordStarts& terms_to_word_starts_offsets,
135                            const RowWordStarts& word_starts);
136 
137   // Returns a recency score based on |last_visit_days_ago|, which is
138   // how many days ago the page was last visited.
139   float GetRecencyScore(int last_visit_days_ago) const;
140 
141   // Examines the first |max_visits_to_score_| and returns a score (higher is
142   // better) based the rate of visits, whether the page is bookmarked, and
143   // how often those visits are typed navigations (i.e., explicitly
144   // invoked by the user).  |now| is passed in to avoid unnecessarily
145   // recomputing it frequently.
146   float GetFrequency(const base::Time& now,
147                      const bool bookmarked,
148                      const VisitInfoVector& visits) const;
149 
150   // Returns a document specificity score based on how many pages matched the
151   // user's input.
152   float GetDocumentSpecificityScore(size_t num_matching_pages) const;
153 
154   // Combines the three component scores into a final score that's
155   // an appropriate value to use as a relevancy score.
156   static float GetFinalRelevancyScore(float topicality_score,
157                                       float frequency_score,
158                                       float specificity_score);
159 
160   // Helper function that returns the string containing the scoring buckets
161   // (either the default ones or ones specified in an experiment).
162   static ScoreMaxRelevances GetHQPBuckets();
163 
164   // Helper function to parse the string containing the scoring buckets and
165   // return the results.  For example, with |buckets_str| as
166   // "0.0:400,1.5:600,12.0:1300,20.0:1399", it returns [(0.0, 400), (1.5, 600),
167   // (12.0, 1300), (20.0, 1399)]. It returns an empty vector in the case of a
168   // malformed |buckets_str|.
169   static ScoreMaxRelevances GetHQPBucketsFromString(
170       const std::string& buckets_str);
171 
172   // If true, assign raw scores to be max(whatever it normally would be, a
173   // score that's similar to the score HistoryURL provider would assign).
174   static bool also_do_hup_like_scoring_;
175 
176   // Untyped visits to bookmarked pages score this, compared to 1 for
177   // untyped visits to non-bookmarked pages and |typed_value_| for typed visits.
178   static float bookmark_value_;
179 
180   // Typed visits to page score this, compared to 1 for untyped visits.
181   static float typed_value_;
182 
183   // The maximum number of recent visits to examine in GetFrequency().
184   static size_t max_visits_to_score_;
185 
186   // If true, we allow input terms to match in the TLD (e.g., ".com").
187   static bool allow_tld_matches_;
188 
189   // If true, we allow input terms to match in the scheme (e.g., "http://").
190   static bool allow_scheme_matches_;
191 
192   // The number of title words examined when computing topicality scores.
193   // Words beyond this number are ignored.
194   static size_t num_title_words_to_allow_;
195 
196   // |topicality_threshold_| is used to control the topicality scoring.
197   // If |topicality_threshold_| > 0, then URLs with topicality-score less than
198   // the threshold are given topicality score of 0.
199   static float topicality_threshold_;
200 
201   // Used for testing.  A possibly null pointer to a vector.  If set,
202   // overrides the static local variable |relevance_buckets| declared in
203   // GetFinalRelevancyScore().
204   static ScoreMaxRelevances* relevance_buckets_override_;
205 
206   // Used for testing.  If this pointer is not null, it overrides the static
207   // local variable |default_matches_to_specificity| declared in
208   // GetDocumentSpecificityScore().
209   static OmniboxFieldTrial::NumMatchesScores* matches_to_specificity_override_;
210 };
211 typedef std::vector<ScoredHistoryMatch> ScoredHistoryMatches;
212 
213 #endif  // COMPONENTS_OMNIBOX_BROWSER_SCORED_HISTORY_MATCH_H_
214