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"
20 class BookmarkService;
21 class HistoryQuickProviderTest;
23 namespace in_memory_url_index {
24 class InMemoryURLIndexCacheItem;
29 namespace imui = in_memory_url_index;
31 class HistoryDatabase;
32 class InMemoryURLIndex;
35 // Current version of the cache file.
36 static const int kCurrentCacheFileVersion = 4;
38 // A structure private to InMemoryURLIndex describing its internal data and
39 // providing for restoring, rebuilding and updating that internal data. As
40 // this class is for exclusive use by the InMemoryURLIndex class there should
41 // be no calls from any other class.
43 // All public member functions are called on the main thread unless otherwise
45 class URLIndexPrivateData
46 : public base::RefCountedThreadSafe<URLIndexPrivateData> {
48 URLIndexPrivateData();
50 // Given a base::string16 in |term_string|, scans the history index and
51 // returns a vector with all scored, matching history items. The
52 // |term_string| is broken down into individual terms (words), each of which
53 // must occur in the candidate history item's URL or page title for the item
54 // to qualify; however, the terms do not necessarily have to be adjacent. We
55 // also allow breaking |term_string| at |cursor_position| (if
56 // set). Once we have a set of candidates, they are filtered to ensure
57 // that all |term_string| terms, as separated by whitespace and the
58 // cursor (if set), occur within the candidate's URL or page title.
59 // Scores are then calculated on no more than |kItemsToScoreLimit|
60 // candidates, as the scoring of such a large number of candidates may
61 // cause perceptible typing response delays in the omnibox. This is
62 // likely to occur for short omnibox terms such as 'h' and 'w' which
63 // will be found in nearly all history candidates. Results are sorted by
64 // descending score. The full results set (i.e. beyond the
65 // |kItemsToScoreLimit| limit) will be retained and used for subsequent calls
66 // to this function. |bookmark_service| is used to boost a result's score if
67 // its URL is referenced by one or more of the user's bookmarks. |languages|
68 // is used to help parse/format the URLs in the history index.
69 ScoredHistoryMatches HistoryItemsForTerms(base::string16 term_string,
70 size_t cursor_position,
71 const std::string& languages,
72 BookmarkService* bookmark_service);
74 // Adds the history item in |row| to the index if it does not already already
75 // exist and it meets the minimum 'quick' criteria. If the row already exists
76 // in the index then the index will be updated if the row still meets the
77 // criteria, otherwise the row will be removed from the index. Returns true
78 // if the index was actually updated. |languages| gives a list of language
79 // encodings by which the URLs and page titles are broken down into words and
80 // characters. |scheme_whitelist| is used to filter non-qualifying schemes.
81 // |history_service| is used to schedule an update to the recent visits
82 // component of this URL's entry in the index.
83 bool UpdateURL(HistoryService* history_service,
85 const std::string& languages,
86 const std::set<std::string>& scheme_whitelist);
88 // Updates the entry for |url_id| in the index, replacing its
89 // recent visits information with |recent_visits|. If |url_id|
90 // is not in the index, does nothing.
91 void UpdateRecentVisits(URLID url_id,
92 const VisitVector& recent_visits);
94 // Using |history_service| schedules an update (using the historyDB
95 // thread) for the recent visits information for |url_id|. Unless
96 // something unexpectedly goes wrong, UdpateRecentVisits() should
97 // eventually be called from a callback.
98 void ScheduleUpdateRecentVisits(HistoryService* history_service,
101 // Deletes index data for the history item with the given |url|.
102 // The item may not have actually been indexed, which is the case if it did
103 // not previously meet minimum 'quick' criteria. Returns true if the index
104 // was actually updated.
105 bool DeleteURL(const GURL& url);
107 // Constructs a new object by restoring its contents from the cache file
108 // at |path|. Returns the new URLIndexPrivateData which on success will
109 // contain the restored data but upon failure will be empty. |languages|
110 // is used to break URLs and page titles into words. This function
111 // should be run on the the file thread.
112 static scoped_refptr<URLIndexPrivateData> RestoreFromFile(
113 const base::FilePath& path,
114 const std::string& languages);
116 // Constructs a new object by rebuilding its contents from the history
117 // database in |history_db|. Returns the new URLIndexPrivateData which on
118 // success will contain the rebuilt data but upon failure will be empty.
119 // |languages| gives a list of language encodings by which the URLs and page
120 // titles are broken down into words and characters.
121 static scoped_refptr<URLIndexPrivateData> RebuildFromHistory(
122 HistoryDatabase* history_db,
123 const std::string& languages,
124 const std::set<std::string>& scheme_whitelist);
126 // Writes |private_data| as a cache file to |file_path| and returns success.
127 static bool WritePrivateDataToCacheFileTask(
128 scoped_refptr<URLIndexPrivateData> private_data,
129 const base::FilePath& file_path);
131 // Stops all pending updates to recent visits fields. This should be
132 // called during shutdown.
133 void CancelPendingUpdates();
135 // Creates a copy of ourself.
136 scoped_refptr<URLIndexPrivateData> Duplicate() const;
138 // Returns true if there is no data in the index.
141 // Initializes all index data members in preparation for restoring the index
142 // from the cache or a complete rebuild from the history database.
146 friend class base::RefCountedThreadSafe<URLIndexPrivateData>;
147 ~URLIndexPrivateData();
149 friend class AddHistoryMatch;
150 friend class ::HistoryQuickProviderTest;
151 friend class InMemoryURLIndexTest;
152 FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, CacheSaveRestore);
153 FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, HugeResultSet);
154 FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, ReadVisitsFromHistory);
155 FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, RebuildFromHistoryIfCacheOld);
156 FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, Scoring);
157 FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, TitleSearch);
158 FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, TypedCharacterCaching);
159 FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, WhitelistedURLs);
160 FRIEND_TEST_ALL_PREFIXES(LimitedInMemoryURLIndexTest, Initialization);
162 // Support caching of term results so that we can optimize searches which
163 // build upon a previous search. Each entry in this map represents one
164 // search term from the most recent search. For example, if the user had
165 // typed "google blog trans" and then typed an additional 'l' (at the end,
166 // of course) then there would be four items in the cache: 'blog', 'google',
167 // 'trans', and 'transl'. All would be marked as being in use except for the
168 // 'trans' item; its cached data would have been used when optimizing the
169 // construction of the search results candidates for 'transl' but then would
172 // Items stored in the search term cache. If a search term exactly matches one
173 // in the cache then we can quickly supply the proper |history_id_set_| (and
174 // marking the cache item as being |used_|. If we find a prefix for a search
175 // term in the cache (which is very likely to occur as the user types each
176 // term into the omnibox) then we can short-circuit the index search for those
177 // characters in the prefix by returning the |word_id_set|. In that case we do
178 // not mark the item as being |used_|.
179 struct SearchTermCacheItem {
180 SearchTermCacheItem(const WordIDSet& word_id_set,
181 const HistoryIDSet& history_id_set);
182 // Creates a cache item for a term which has no results.
183 SearchTermCacheItem();
185 ~SearchTermCacheItem();
187 WordIDSet word_id_set_;
188 HistoryIDSet history_id_set_;
189 bool used_; // True if this item has been used for the current term search.
191 typedef std::map<base::string16, SearchTermCacheItem> SearchTermCacheMap;
193 // A helper class which performs the final filter on each candidate
194 // history URL match, inserting accepted matches into |scored_matches_|.
195 class AddHistoryMatch : public std::unary_function<HistoryID, void> {
197 AddHistoryMatch(const URLIndexPrivateData& private_data,
198 const std::string& languages,
199 BookmarkService* bookmark_service,
200 const base::string16& lower_string,
201 const String16Vector& lower_terms,
202 const base::Time now);
205 void operator()(const HistoryID history_id);
207 ScoredHistoryMatches ScoredMatches() const { return scored_matches_; }
210 const URLIndexPrivateData& private_data_;
211 const std::string& languages_;
212 BookmarkService* bookmark_service_;
213 ScoredHistoryMatches scored_matches_;
214 const base::string16& lower_string_;
215 const String16Vector& lower_terms_;
216 WordStarts lower_terms_to_word_starts_offsets_;
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_