Implemented substring matching within page titles. Fixed bug where URL was be...

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>
 #include <set>
 #include <string>
 #include <vector>
 
 #include "app/sql/connection.h"
 #include "base/basictypes.h"
 #include "base/file_path.h"
 #include "base/gtest_prod_util.h"
 #include "base/linked_ptr.h"
 #include "base/scoped_ptr.h"
 #include "base/string16.h"
+#include "chrome/browser/autocomplete/autocomplete_match.h"
 #include "chrome/browser/autocomplete/history_provider_util.h"
 #include "chrome/browser/history/history_types.h"
 #include "chrome/browser/history/in_memory_url_index_cache.pb.h"
 #include "testing/gtest/include/gtest/gtest_prod.h"
 
 class Profile;
 
 namespace base {
 class Time;
 }
 
 namespace in_memory_url_index {
 class InMemoryURLIndexCacheItem;
 }
 
 namespace history {
 
 namespace imui = in_memory_url_index;
 
 class URLDatabase;
 
+// Specifies where an omnibox term occurs within a string. Used for specifying
+// highlights in AutocompleteMatches (ACMatchClassifications) and to assist in
+// scoring a result.
+struct TermMatch {
+  TermMatch(int term_num, size_t offset, size_t length)
+      : term_num(term_num),
+        offset(offset),
+        length(length) {}
+
+  int term_num;  // The index of the term in the original search string.
+  size_t offset;  // The starting offset of the substring match.
+  size_t length;  // The length of the substring match.
+};
+typedef std::vector<TermMatch> TermMatches;
+
 // Used for intermediate history result operations.
 struct ScoredHistoryMatch : public HistoryMatch {
-  // Required for STL, we don't use this directly.
-  ScoredHistoryMatch();
-
-  ScoredHistoryMatch(const URLRow& url_info,
-                     size_t input_location,
-                     bool match_in_scheme,
-                     bool innermost_match,
-                     int score);
+  ScoredHistoryMatch();  // Required by STL.
+  explicit ScoredHistoryMatch(const URLRow& url_info);
 
   // An interim score taking into consideration location and completeness
   // of the match.
   int raw_score;
+  TermMatches url_matches;  // Term matches within the URL.
+  TermMatches title_matches;  // Term matches within the page title.
+  size_t prefix_adjust;  // The length of a prefix which should be ignored.
 };
 typedef std::vector<ScoredHistoryMatch> ScoredHistoryMatches;
 
 // The URL history source.
 // Holds portions of the URL database in memory in an indexed form.  Used to
 // quickly look up matching URLs for a given query string.  Used by
 // the HistoryURLProvider for inline autocomplete and to provide URL
 // matches to the omnibox.
 //
 // Note about multi-byte codepoints and the data structures in the
@@ skipping 40 matching lines @@
   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 for the item to
   // qualify; however, the terms do not necessarily have to be adjacent.
-  // Results are sorted with higher scoring items first.
+  // Results are sorted with higher scoring items first. Each term from |terms|
+  // may contain punctuation but should not contain spaces.
   ScoredHistoryMatches HistoryItemsForTerms(const String16Vector& terms);
 
-  // Returns the date threshold for considering an history item as significant.
-  static base::Time RecentThreshold();
-
   // 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);
 
+  // Breaks the |uni_string| string down into individual words and return
+  // a vector with the individual words in their original order. Break on
+  // whitespace if |break_on_space| also on special characters.
+  static String16Vector WordVectorFromString16(const string16& uni_string,
+                                               bool break_on_space);
+
  private:
   friend class AddHistoryMatch;
-  FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, Initialization);
-  FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, Char16Utilities);
-  FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, TypedCharacterCaching);
+  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, Scoring);
+  FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, StaticFunctions);
+  FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, TitleSearch);
+  FRIEND_TEST_ALL_PREFIXES(InMemoryURLIndexTest, TypedCharacterCaching);
 
   // Signals that there are no previously cached results for the typed term.
   static const size_t kNoCachedResultForTerm;
 
   // Creating one of me without a history path is not allowed (tests excepted).
   InMemoryURLIndex();
 
   // Convenience types.
   typedef std::set<string16> String16Set;
   typedef std::set<char16> Char16Set;
@@ skipping 68 matching lines @@
   WordIDSet WordIDSetForTermChars(const Char16Vector& uni_chars);
 
   // Given a vector of Char16s in |uni_chars|, compare those characters, in
   // order, with the previously searched term, returning the index of the
   // cached results in the term_char_word_set_cache_ of the set with best
   // matching number of characters. Returns kNoCachedResultForTerm if there
   // was no match at all (i.e. the first character of |uni-chars| is not the
   // same as the character of the first entry in term_char_word_set_cache_).
   size_t CachedResultsIndexForTerm(const Char16Vector& uni_chars);
 
+  // Creates a TermMatches which has an entry for each occurrence of the string
+  // |term| found in the string |string|. Mark each match with |term_num| so
+  // that the resulting TermMatches can be merged with other TermMatches for
+  // other terms.
+  static TermMatches MatchTermInString(const string16& term,
+                                       const string16& string,
+                                       int term_num);
+
   // URL History indexing support functions.
 
   // Indexes one URL history item.
   bool IndexRow(const URLRow& row);
 
   // Breaks a string down into unique, individual characters in the order
   // in which the characters are first encountered in the |uni_word| string.
   static Char16Vector Char16VectorFromString16(const string16& uni_word);
 
   // Breaks the |uni_word| string down into its individual characters.
@@ skipping 32 matching lines @@
   HistoryIDSet HistoryIDsForTerm(const string16& uni_word);
 
   // 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
   // visit time, and 5) number of visits.
   // This raw score allows the results to be ordered and can be used
   // to influence the final score calculated by the client of this
-  // index. Return the starting location of the first term in
-  // |first_term_location|.
-  static int RawScoreForURL(const URLRow& row,
-                            const String16Vector& terms_vector,
-                            size_t* first_term_location);
+  // index. Returns a ScoredHistoryMatch structure with the raw score and
+  // substring matching metrics.
+  static ScoredHistoryMatch ScoredMatchForURL(
+      const URLRow& row,
+      const String16Vector& terms_vector);
+
+  // Calculates a partial raw score based on position, ordering and total
+  // substring match size using metrics recorded in |matches|. |max_length|
+  // is the length of the string against which the terms are being searched.
+  static int RawScoreForMatches(const TermMatches& matches,
+                                size_t max_length);
+
+  // Sorts and removes overlapping substring matches from |matches| and
+  // returns the cleaned up matches.
+  static TermMatches SortAndDeoverlap(const TermMatches& matches);
 
   // Utility functions supporting RestoreFromCache and SaveToCache.
 
   // Construct a file path for the cache file within the same directory where
   // the history database is kept and saves that path to |file_path|. Returns
   // true if |file_path| can be successfully constructed. (This function
   // provided as a hook for unit testing.)
   bool GetCacheFilePath(FilePath* file_path);
 
   // Encode a data structure into the protobuf |cache|.
@@ skipping 41 matching lines @@
   TermCharWordSetVector term_char_word_set_cache_;
   HistoryInfoMap history_info_map_;
   std::string languages_;
 
   DISALLOW_COPY_AND_ASSIGN(InMemoryURLIndex);
 };
 
 }  // namespace history
 
 #endif  // CHROME_BROWSER_HISTORY_IN_MEMORY_URL_INDEX_H_