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.
5 #ifndef CHROME_BROWSER_HISTORY_URL_INDEX_PRIVATE_DATA_H_
6 #define CHROME_BROWSER_HISTORY_URL_INDEX_PRIVATE_DATA_H_
11 #include "base/files/file_path.h"
12 #include "base/gtest_prod_util.h"
13 #include "base/memory/ref_counted.h"
14 #include "chrome/browser/common/cancelable_request.h"
15 #include "chrome/browser/history/history_service.h"
16 #include "chrome/browser/history/in_memory_url_index_cache.pb.h"
17 #include "chrome/browser/history/in_memory_url_index_types.h"
18 #include "chrome/browser/history/scored_history_match.h"
19 #include "content/public/browser/notification_details.h"
21 class BookmarkService;
22 class HistoryQuickProviderTest;
24 namespace in_memory_url_index {
25 class InMemoryURLIndexCacheItem;
30 namespace imui = in_memory_url_index;
32 class HistoryDatabase;
33 class InMemoryURLIndex;
36 // Current version of the cache file.
37 static const int kCurrentCacheFileVersion = 4;
39 // A structure private to InMemoryURLIndex describing its internal data and
40 // providing for restoring, rebuilding and updating that internal data. As
41 // this class is for exclusive use by the InMemoryURLIndex class there should
42 // be no calls from any other class.
44 // All public member functions are called on the main thread unless otherwise
46 class URLIndexPrivateData
47 : public base::RefCountedThreadSafe<URLIndexPrivateData> {
49 URLIndexPrivateData();
51 // Given a base::string16 in |term_string|, scans the history index and
52 // returns a vector with all scored, matching history items. The
53 // |term_string| is broken down into individual terms (words), each of which
54 // must occur in the candidate history item's URL or page title for the item
55 // to qualify; however, the terms do not necessarily have to be adjacent. We
56 // also allow breaking |term_string| at |cursor_position| (if
57 // set). Once we have a set of candidates, they are filtered to ensure
58 // that all |term_string| terms, as separated by whitespace and the
59 // cursor (if set), occur within the candidate's URL or page title.
60 // Scores are then calculated on no more than |kItemsToScoreLimit|
61 // candidates, as the scoring of such a large number of candidates may
62 // cause perceptible typing response delays in the omnibox. This is
63 // likely to occur for short omnibox terms such as 'h' and 'w' which
64 // will be found in nearly all history candidates. Results are sorted by
65 // descending score. The full results set (i.e. beyond the
66 // |kItemsToScoreLimit| limit) will be retained and used for subsequent calls
67 // to this function. |bookmark_service| is used to boost a result's score if
68 // its URL is referenced by one or more of the user's bookmarks. |languages|
69 // is used to help parse/format the URLs in the history index.
70 ScoredHistoryMatches HistoryItemsForTerms(base::string16 term_string,
71 size_t cursor_position,
72 const std::string& languages,
73 BookmarkService* bookmark_service);
75 // Adds the history item in |row| to the index if it does not already already
76 // exist and it meets the minimum 'quick' criteria. If the row already exists
77 // in the index then the index will be updated if the row still meets the
78 // criteria, otherwise the row will be removed from the index. Returns true
79 // if the index was actually updated. |languages| gives a list of language
80 // encodings by which the URLs and page titles are broken down into words and
81 // characters. |scheme_whitelist| is used to filter non-qualifying schemes.
82 // |history_service| is used to schedule an update to the recent visits
83 // component of this URL's entry in the index.
84 bool UpdateURL(HistoryService* history_service,
86 const std::string& languages,
87 const std::set<std::string>& scheme_whitelist);
89 // Updates the entry for |url_id| in the index, replacing its
90 // recent visits information with |recent_visits|. If |url_id|
91 // is not in the index, does nothing.
92 void UpdateRecentVisits(URLID url_id,
93 const VisitVector& recent_visits);
95 // Using |history_service| schedules an update (using the historyDB
96 // thread) for the recent visits information for |url_id|. Unless
97 // something unexpectedly goes wrong, UdpateRecentVisits() should
98 // eventually be called from a callback.
99 void ScheduleUpdateRecentVisits(HistoryService* history_service,
102 // Deletes index data for the history item with the given |url|.
103 // The item may not have actually been indexed, which is the case if it did
104 // not previously meet minimum 'quick' criteria. Returns true if the index
105 // was actually updated.
106 bool DeleteURL(const GURL& url);
108 // Constructs a new object by restoring its contents from the cache file
109 // at |path|. Returns the new URLIndexPrivateData which on success will
110 // contain the restored data but upon failure will be empty. |languages|
111 // is used to break URLs and page titles into words. This function
112 // should be run on the the file thread.
113 static scoped_refptr<URLIndexPrivateData> RestoreFromFile(
114 const base::FilePath& path,
115 const std::string& languages);
117 // Constructs a new object by rebuilding its contents from the history
118 // database in |history_db|. Returns the new URLIndexPrivateData which on
119 // success will contain the rebuilt data but upon failure will be empty.
120 // |languages| gives a list of language encodings by which the URLs and page
121 // titles are broken down into words and characters.
122 static scoped_refptr<URLIndexPrivateData> RebuildFromHistory(
123 HistoryDatabase* history_db,
124 const std::string& languages,
125 const std::set<std::string>& scheme_whitelist);
127 // Writes |private_data| as a cache file to |file_path| and returns success.
128 static bool WritePrivateDataToCacheFileTask(
129 scoped_refptr<URLIndexPrivateData> private_data,
130 const base::FilePath& file_path);
132 // Stops all pending updates to recent visits fields. This should be
133 // called during shutdown.
134 void CancelPendingUpdates();
136 // Creates a copy of ourself.
137 scoped_refptr<URLIndexPrivateData> Duplicate() const;
139 // Returns true if there is no data in the index.
142 // Initializes all index data members in preparation for restoring the index
143 // from the cache or a complete rebuild from the history database.
147 friend class base::RefCountedThreadSafe<URLIndexPrivateData>;
148 ~URLIndexPrivateData();
150 friend class AddHistoryMatch;
151 friend class ::HistoryQuickProviderTest;
152 friend class InMemoryURLIndexTest;
153 FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, CacheSaveRestore);
154 FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, HugeResultSet);
155 FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, ReadVisitsFromHistory);
156 FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, RebuildFromHistoryIfCacheOld);
157 FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, Scoring);
158 FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, TitleSearch);
159 FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, TypedCharacterCaching);
160 FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, WhitelistedURLs);
161 FRIEND_TEST_ALL_PREFIXES(LimitedInMemoryURLIndexTest, Initialization);
163 // Support caching of term results so that we can optimize searches which
164 // build upon a previous search. Each entry in this map represents one
165 // search term from the most recent search. For example, if the user had
166 // typed "google blog trans" and then typed an additional 'l' (at the end,
167 // of course) then there would be four items in the cache: 'blog', 'google',
168 // 'trans', and 'transl'. All would be marked as being in use except for the
169 // 'trans' item; its cached data would have been used when optimizing the
170 // construction of the search results candidates for 'transl' but then would
173 // Items stored in the search term cache. If a search term exactly matches one
174 // in the cache then we can quickly supply the proper |history_id_set_| (and
175 // marking the cache item as being |used_|. If we find a prefix for a search
176 // term in the cache (which is very likely to occur as the user types each
177 // term into the omnibox) then we can short-circuit the index search for those
178 // characters in the prefix by returning the |word_id_set|. In that case we do
179 // not mark the item as being |used_|.
180 struct SearchTermCacheItem {
181 SearchTermCacheItem(const WordIDSet& word_id_set,
182 const HistoryIDSet& history_id_set);
183 // Creates a cache item for a term which has no results.
184 SearchTermCacheItem();
186 ~SearchTermCacheItem();
188 WordIDSet word_id_set_;
189 HistoryIDSet history_id_set_;
190 bool used_; // True if this item has been used for the current term search.
192 typedef std::map<base::string16, SearchTermCacheItem> SearchTermCacheMap;
194 // A helper class which performs the final filter on each candidate
195 // history URL match, inserting accepted matches into |scored_matches_|.
196 class AddHistoryMatch : public std::unary_function<HistoryID, void> {
198 AddHistoryMatch(const URLIndexPrivateData& private_data,
199 const std::string& languages,
200 BookmarkService* bookmark_service,
201 const base::string16& lower_string,
202 const String16Vector& lower_terms,
203 const base::Time now);
206 void operator()(const HistoryID history_id);
208 ScoredHistoryMatches ScoredMatches() const { return scored_matches_; }
211 const URLIndexPrivateData& private_data_;
212 const std::string& languages_;
213 BookmarkService* bookmark_service_;
214 ScoredHistoryMatches scored_matches_;
215 const base::string16& lower_string_;
216 const String16Vector& lower_terms_;
217 const base::Time now_;
220 // A helper predicate class used to filter excess history items when the
221 // candidate results set is too large.
222 class HistoryItemFactorGreater
223 : public std::binary_function<HistoryID, HistoryID, void> {
225 explicit HistoryItemFactorGreater(const HistoryInfoMap& history_info_map);
226 ~HistoryItemFactorGreater();
228 bool operator()(const HistoryID h1, const HistoryID h2);
231 const history::HistoryInfoMap& history_info_map_;
234 // URL History indexing support functions.
236 // Composes a set of history item IDs by intersecting the set for each word
237 // in |unsorted_words|.
238 HistoryIDSet HistoryIDSetFromWords(const String16Vector& unsorted_words);
240 // Helper function to HistoryIDSetFromWords which composes a set of history
241 // ids for the given term given in |term|.
242 HistoryIDSet HistoryIDsForTerm(const base::string16& term);
244 // Given a set of Char16s, finds words containing those characters.
245 WordIDSet WordIDSetForTermChars(const Char16Set& term_chars);
247 // Indexes one URL history item as described by |row|. Returns true if the
248 // row was actually indexed. |languages| gives a list of language encodings by
249 // which the URLs and page titles are broken down into words and characters.
250 // |scheme_whitelist| is used to filter non-qualifying schemes. If
251 // |history_db| is not NULL then this function uses the history database
252 // synchronously to get the URL's recent visits information. This mode should
253 // only be used on the historyDB thread. If |history_db| is NULL, then
254 // this function uses |history_service| to schedule a task on the
255 // historyDB thread to fetch and update the recent visits
257 bool IndexRow(HistoryDatabase* history_db,
258 HistoryService* history_service,
260 const std::string& languages,
261 const std::set<std::string>& scheme_whitelist);
263 // Parses and indexes the words in the URL and page title of |row| and
264 // calculate the word starts in each, saving the starts in |word_starts|.
265 // |languages| gives a list of language encodings by which the URLs and page
266 // titles are broken down into words and characters.
267 void AddRowWordsToIndex(const URLRow& row,
268 RowWordStarts* word_starts,
269 const std::string& languages);
271 // Given a single word in |uni_word|, adds a reference for the containing
272 // history item identified by |history_id| to the index.
273 void AddWordToIndex(const base::string16& uni_word, HistoryID history_id);
275 // Creates a new entry in the word/history map for |word_id| and add
276 // |history_id| as the initial element of the word's set.
277 void AddWordHistory(const base::string16& uni_word, HistoryID history_id);
279 // Updates an existing entry in the word/history index by adding the
280 // |history_id| to set for |word_id| in the word_id_history_map_.
281 void UpdateWordHistory(WordID word_id, HistoryID history_id);
283 // Adds |word_id| to |history_id|'s entry in the history/word map,
284 // creating a new entry if one does not already exist.
285 void AddToHistoryIDWordMap(HistoryID history_id, WordID word_id);
287 // Removes |row| and all associated words and characters from the index.
288 void RemoveRowFromIndex(const URLRow& row);
290 // Removes all words and characters associated with |row| from the index.
291 void RemoveRowWordsFromIndex(const URLRow& row);
293 // Clears |used_| for each item in the search term cache.
294 void ResetSearchTermCache();
296 // Caches the index private data and writes the cache file to the profile
297 // directory. Called by WritePrivateDataToCacheFileTask.
298 bool SaveToFile(const base::FilePath& file_path);
300 // Encode a data structure into the protobuf |cache|.
301 void SavePrivateData(imui::InMemoryURLIndexCacheItem* cache) const;
302 void SaveWordList(imui::InMemoryURLIndexCacheItem* cache) const;
303 void SaveWordMap(imui::InMemoryURLIndexCacheItem* cache) const;
304 void SaveCharWordMap(imui::InMemoryURLIndexCacheItem* cache) const;
305 void SaveWordIDHistoryMap(imui::InMemoryURLIndexCacheItem* cache) const;
306 void SaveHistoryInfoMap(imui::InMemoryURLIndexCacheItem* cache) const;
307 void SaveWordStartsMap(imui::InMemoryURLIndexCacheItem* cache) const;
309 // Decode a data structure from the protobuf |cache|. Return false if there
310 // is any kind of failure. |languages| will be used to break URLs and page
312 bool RestorePrivateData(const imui::InMemoryURLIndexCacheItem& cache,
313 const std::string& languages);
314 bool RestoreWordList(const imui::InMemoryURLIndexCacheItem& cache);
315 bool RestoreWordMap(const imui::InMemoryURLIndexCacheItem& cache);
316 bool RestoreCharWordMap(const imui::InMemoryURLIndexCacheItem& cache);
317 bool RestoreWordIDHistoryMap(const imui::InMemoryURLIndexCacheItem& cache);
318 bool RestoreHistoryInfoMap(const imui::InMemoryURLIndexCacheItem& cache);
319 bool RestoreWordStartsMap(const imui::InMemoryURLIndexCacheItem& cache,
320 const std::string& languages);
322 // Determines if |gurl| has a whitelisted scheme and returns true if so.
323 static bool URLSchemeIsWhitelisted(const GURL& gurl,
324 const std::set<std::string>& whitelist);
326 // Cache of search terms.
327 SearchTermCacheMap search_term_cache_;
329 // Allows canceling pending requests to update recent visits information.
330 CancelableRequestConsumer recent_visits_consumer_;
332 // Start of data members that are cached -------------------------------------
334 // The version of the cache file most recently used to restore this instance
335 // of the private data. If the private data was rebuilt from the history
336 // database this will be 0.
337 int restored_cache_version_;
339 // The last time the data was rebuilt from the history database.
340 base::Time last_time_rebuilt_from_history_;
342 // A list of all of indexed words. The index of a word in this list is the
343 // ID of the word in the word_map_. It reduces the memory overhead by
344 // replacing a potentially long and repeated string with a simple index.
345 String16Vector word_list_;
347 // A list of available words slots in |word_list_|. An available word slot
348 // is the index of a unused word in word_list_ vector, also referred to as
349 // a WordID. As URL visits are added or modified new words may be added to
350 // the index, in which case any available words are used, if any, and then
351 // words are added to the end of the word_list_. When URL visits are
352 // modified or deleted old words may be removed from the index, in which
353 // case the slots for those words are added to available_words_ for resuse
354 // by future URL updates.
355 WordIDSet available_words_;
357 // A one-to-one mapping from the a word string to its slot number (i.e.
358 // WordID) in the |word_list_|.
361 // A one-to-many mapping from a single character to all WordIDs of words
362 // containing that character.
363 CharWordIDMap char_word_map_;
365 // A one-to-many mapping from a WordID to all HistoryIDs (the row_id as
366 // used in the history database) of history items in which the word occurs.
367 WordIDHistoryMap word_id_history_map_;
369 // A one-to-many mapping from a HistoryID to all WordIDs of words that occur
370 // in the URL and/or page title of the history item referenced by that
372 HistoryIDWordMap history_id_word_map_;
374 // A one-to-one mapping from HistoryID to the history item data governing
375 // index inclusion and relevance scoring.
376 HistoryInfoMap history_info_map_;
378 // A one-to-one mapping from HistoryID to the word starts detected in each
379 // item's URL and page title.
380 WordStartsMap word_starts_map_;
382 // End of data members that are cached ---------------------------------------
384 // For unit testing only. Specifies the version of the cache file to be saved.
385 // Used only for testing upgrading of an older version of the cache upon
387 int saved_cache_version_;
389 // Used for unit testing only. Records the number of candidate history items
390 // at three stages in the index searching process.
391 size_t pre_filter_item_count_; // After word index is queried.
392 size_t post_filter_item_count_; // After trimming large result set.
393 size_t post_scoring_item_count_; // After performing final filter/scoring.
396 } // namespace history
398 #endif // CHROME_BROWSER_HISTORY_URL_INDEX_PRIVATE_DATA_H_