Improve Autocomplete Matches and Handling of Large Results Sets

chrome/browser/history/in_memory_url_index.h

 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef CHROME_BROWSER_HISTORY_IN_MEMORY_URL_INDEX_H_
 #define CHROME_BROWSER_HISTORY_IN_MEMORY_URL_INDEX_H_
 #pragma once
 
 #include <functional>
 #include <map>
@@ skipping 72 matching lines @@
   void ShutDown();
 
   // Restores the index's private data from the cache file stored in the
   // profile directory and returns true if successful.
   bool RestoreFromCacheFile();
 
   // Caches the index private data and writes the cache file to the profile
   // directory.
   bool SaveToCacheFile();
 
-  // Given a vector containing one or more words as string16s, scans the
-  // history index and return a vector with all scored, matching history items.
-  // Each term must occur somewhere in the history item's URL or page title for
-  // the item to qualify; however, the terms do not necessarily have to be
-  // adjacent. Results are sorted with higher scoring items first. Each term
-  // from |terms| may contain punctuation but should not contain spaces.
-  // A search request which results in more than |kItemsToScoreLimit| total
-  // candidate items returns no matches (though the results set will be
-  // retained and used for subsequent calls to this function) as the scoring
-  // of such a large number of candidates may cause perceptible typing response
-  // delays in the omnibox. This is likely to occur for short omnibox terms
-  // such as 'h' and 'w' which will be found in nearly all history candidates.
-  ScoredHistoryMatches HistoryItemsForTerms(const String16Vector& terms);
+  // Given a string16 in |term_string|, scans the history index and returns a
+  // vector with all scored, matching history items. The |term_string| is
+  // broken down into individual terms (words), each of which must occur in the
+  // candidate history item's URL or page title for the item to qualify;
+  // however, the terms do not necessarily have to be adjacent. Once we have
+  // a set of candidates, they are filtered to insure that all |term_string|
+  // terms, as separated by whitespace, occur within the candidate's URL
+  // or page title. Scores are then calculated on no more than
+  // |kItemsToScoreLimit| candidates, as the scoring of such a large number of
+  // candidates may cause perceptible typing response delays in the omnibox.
+  // This is likely to occur for short omnibox terms such as 'h' and 'w' which
+  // will be found in nearly all history candidates. Results are sorted by
+  // descending score. The full results set (i.e. beyond the
+  // |kItemsToScoreLimit| limit) will be retained and used for subsequent calls
+  // to this function.
+  ScoredHistoryMatches HistoryItemsForTerms(const string16& term_string);
 
   // Updates or adds an history item to the index if it meets the minimum
   // 'quick' criteria.
   void UpdateURL(URLID row_id, const URLRow& row);
 
   // Deletes indexing data for an history item. The item may not have actually
   // been indexed (which is the case if it did not previously meet minimum
   // 'quick' criteria).
   void DeleteURL(URLID row_id);
 
  private:
   friend class AddHistoryMatch;
   friend class InMemoryURLIndexTest;
   FRIEND_TEST_ALL_PREFIXES(LimitedInMemoryURLIndexTest, Initialization);
   FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, CacheFilePath);
   FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, CacheSaveRestore);
-  FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, Char16Utilities);
+  FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, HugeResultSet);
   FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, NonUniqueTermCharacterSets);
   FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, Scoring);
   FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, StaticFunctions);
   FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, TitleSearch);
   FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, TitleChange);
   FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, TypedCharacterCaching);
   FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, WhitelistedURLs);
 
   // Signals that there are no previously cached results for the typed term.
   static const size_t kNoCachedResultForTerm;
@@ skipping 44 matching lines @@
     void operator()(const HistoryID history_id);
 
     ScoredHistoryMatches ScoredMatches() const { return scored_matches_; }
 
    private:
     const InMemoryURLIndex& index_;
     ScoredHistoryMatches scored_matches_;
     const String16Vector& lower_terms_;
   };
 
+  // A helper predicate class used to filter excess history items when the
+  // candidate results set is too large.
+  class HistoryItemFactorGreater
+      : public std::binary_function<HistoryID, HistoryID, void> {
+   public:
+    explicit HistoryItemFactorGreater(const HistoryInfoMap& history_info_map);
+    ~HistoryItemFactorGreater();
+
+    bool operator()(const HistoryID h1, const HistoryID h2);
+
+  private:
+    const history::HistoryInfoMap& history_info_map_;
+  };
+
   // Initializes all index data members in preparation for restoring the index
   // from the cache or a complete rebuild from the history database.
   void ClearPrivateData();
 
   // Initializes the whitelist of URL schemes.
   static void InitializeSchemeWhitelist(std::set<std::string>* whitelist);
 
   // URL History indexing support functions.
 
   // Indexes one URL history item.
@@ skipping 17 matching lines @@
   void UpdateWordHistory(WordID word_id, HistoryID history_id);
 
   // Creates a new entry in the word/history map for |word_id| and add
   // |history_id| as the initial element of the word's set.
   void AddWordHistory(const string16& uni_word, HistoryID history_id);
 
   // Clears |used_| for each item in the search term cache.
   void ResetSearchTermCache();
 
   // Composes a set of history item IDs by intersecting the set for each word
-  // in |uni_string|.
-  HistoryIDSet HistoryIDSetFromWords(const string16& uni_string);
+  // in |unsorted_words|.
+  HistoryIDSet HistoryIDSetFromWords(const String16Vector& unsorted_words);
 
   // Helper function to HistoryIDSetFromWords which composes a set of history
   // ids for the given term given in |term|.
   HistoryIDSet HistoryIDsForTerm(const string16& term);
 
   // Calculates a raw score for this history item by first determining
   // if all of the terms in |terms_vector| occur in |row| and, if so,
   // calculating a raw score based on 1) starting position of each term
   // in the user input, 2) completeness of each term's match, 3) ordering
   // of the occurrence of each term (i.e. they appear in order), 4) last
@@ skipping 63 matching lines @@
   // Only URLs with a whitelisted scheme are indexed.
   std::set<std::string> scheme_whitelist_;
 
   // Set to true at shutdown when the cache has been written to disk. Used
   // as a temporary safety check to insure that the cache is saved before
   // the index has been destructed.
   // TODO(mrossetti): Eliminate once the transition to SQLite has been done.
   // http://crbug.com/83659
   bool cached_at_shutdown_;
 
+  // Used for unit testing only. Records the number of candidate history items
+  // at three stages in the index searching process.
+  size_t pre_filter_item_count;    // After word index is queried.
+  size_t post_filter_item_count;   // After trimming large result set.
+  size_t post_scoring_item_count;  // After performing final filter and scoring.
+
   DISALLOW_COPY_AND_ASSIGN(InMemoryURLIndex);
 };
 
 }  // namespace history
 
 #endif  // CHROME_BROWSER_HISTORY_IN_MEMORY_URL_INDEX_H_