Gather word-start Information to Aid in Scoring.

chrome/browser/history/url_index_private_data.cc

 // Copyright (c) 2012 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.
 
 #include "chrome/browser/history/url_index_private_data.h"
 
 #include <algorithm>
 #include <functional>
 #include <iterator>
 #include <limits>
@@ skipping 24 matching lines @@
 typedef imui::InMemoryURLIndexCacheItem_CharWordMapItem_CharWordMapEntry
     CharWordMapEntry;
 typedef imui::InMemoryURLIndexCacheItem_WordIDHistoryMapItem
     WordIDHistoryMapItem;
 typedef imui::
     InMemoryURLIndexCacheItem_WordIDHistoryMapItem_WordIDHistoryMapEntry
     WordIDHistoryMapEntry;
 typedef imui::InMemoryURLIndexCacheItem_HistoryInfoMapItem HistoryInfoMapItem;
 typedef imui::InMemoryURLIndexCacheItem_HistoryInfoMapItem_HistoryInfoMapEntry
     HistoryInfoMapEntry;
+typedef imui::InMemoryURLIndexCacheItem_WordStartsMapItem WordStartsMapItem;
+typedef imui::InMemoryURLIndexCacheItem_WordStartsMapItem_WordStartsMapEntry
+    WordStartsMapEntry;
 
 // The maximum score any candidate result can achieve.
 const int kMaxTotalScore = 1425;
 
 // Score ranges used to get a 'base' score for each of the scoring factors
 // (such as recency of last visit, times visited, times the URL was typed,
 // and the quality of the string match). There is a matching value range for
 // each of these scores for each factor. Note that the top score is greater
 // than |kMaxTotalScore|. The score for each candidate will be capped in the
 // final calculation.
@@ skipping 53 matching lines @@
     score += (value - value_ranks[i]) *
         (kScoreRank[i - 1] - kScoreRank[i]) /
         (value_ranks[i - 1] - value_ranks[i]);
   }
   return score;
 }
 
 // InMemoryURLIndex's Private Data ---------------------------------------------
 
 URLIndexPrivateData::URLIndexPrivateData()
-    : pre_filter_item_count_(0),
+    : restored_cache_version_(0),
+      saved_cache_version_(kCurrentCacheFileVersion),
+      pre_filter_item_count_(0),
       post_filter_item_count_(0),
       post_scoring_item_count_(0) {
   URLIndexPrivateData::InitializeSchemeWhitelist(&scheme_whitelist_);
 }
 
 URLIndexPrivateData::~URLIndexPrivateData() {}
 
 void URLIndexPrivateData::Clear() {
   word_list_.clear();
   available_words_.clear();
   word_map_.clear();
   char_word_map_.clear();
   word_id_history_map_.clear();
   history_id_word_map_.clear();
   history_info_map_.clear();
+  word_starts_map_.clear();
 }
 
 // Cache Updating --------------------------------------------------------------
 
 bool URLIndexPrivateData::IndexRow(const URLRow& row) {
   const GURL& gurl(row.url());
 
   // Index only URLs with a whitelisted scheme.
   if (!URLIndexPrivateData::URLSchemeIsWhitelisted(gurl))
     return false;
@@ skipping 10 matching lines @@
 
   // Add the row for quick lookup in the history info store.
   URLRow new_row(GURL(url), row_id);
   new_row.set_visit_count(row.visit_count());
   new_row.set_typed_count(row.typed_count());
   new_row.set_last_visit(row.last_visit());
   new_row.set_title(row.title());
   history_info_map_[history_id] = new_row;
 
   // Index the words contained in the URL and title of the row.
-  AddRowWordsToIndex(new_row);
+  RowWordStarts word_starts;
+  AddRowWordsToIndex(new_row, &word_starts);
+  word_starts_map_[history_id] = word_starts;
   return true;
 }
 
-void URLIndexPrivateData::AddRowWordsToIndex(const URLRow& row) {
+void URLIndexPrivateData::AddRowWordsToIndex(const URLRow& row,
+                                             RowWordStarts* word_starts) {
   HistoryID history_id = static_cast<HistoryID>(row.id());
   // Split URL into individual, unique words then add in the title words.
   const GURL& gurl(row.url());
   string16 url(net::FormatUrl(gurl, languages_,
       net::kFormatUrlOmitUsernamePassword,
       net::UnescapeRule::SPACES | net::UnescapeRule::URL_SPECIAL_CHARS,
       NULL, NULL, NULL));
   url = base::i18n::ToLower(url);
-  String16Set url_words = String16SetFromString16(url);
-  String16Set title_words = String16SetFromString16(row.title());
+  String16Set url_words = String16SetFromString16(url,
+      word_starts ? &word_starts->url_word_starts_ : NULL);
+  String16Set title_words = String16SetFromString16(row.title(),
+      word_starts ? &word_starts->title_word_starts_ : NULL);
   String16Set words;
   std::set_union(url_words.begin(), url_words.end(),
                  title_words.begin(), title_words.end(),
                  std::insert_iterator<String16Set>(words, words.begin()));
   for (String16Set::iterator word_iter = words.begin();
        word_iter != words.end(); ++word_iter)
     AddWordToIndex(*word_iter, history_id);
 
   search_term_cache_.clear();  // Invalidate the term cache.
 }
@@ skipping 50 matching lines @@
       word_id_set.insert(word_id);
       char_word_map_[uni_char] = word_id_set;
     }
   }
 }
 
 void URLIndexPrivateData::RemoveRowFromIndex(const URLRow& row) {
   RemoveRowWordsFromIndex(row);
   HistoryID history_id = static_cast<HistoryID>(row.id());
   history_info_map_.erase(history_id);
+  word_starts_map_.erase(history_id);
 }
 
 void URLIndexPrivateData::RemoveRowWordsFromIndex(const URLRow& row) {
   // Remove the entries in history_id_word_map_ and word_id_history_map_ for
   // this row.
   HistoryID history_id = static_cast<HistoryID>(row.id());
   WordIDSet word_id_set = history_id_word_map_[history_id];
   history_id_word_map_.erase(history_id);
 
   // Reconcile any changes to word usage.
@@ skipping 62 matching lines @@
       row_to_update.set_visit_count(row.visit_count());
       row_to_update.set_typed_count(row.typed_count());
       row_to_update.set_last_visit(row.last_visit());
       // While the URL is guaranteed to remain stable, the title may have
       // changed. If so, then update the index with the changed words.
       if (title_updated) {
         // Clear all words associated with this row and re-index both the
         // URL and title.
         RemoveRowWordsFromIndex(row_to_update);
         row_to_update.set_title(row.title());
-        AddRowWordsToIndex(row_to_update);
+        RowWordStarts word_starts;
+        AddRowWordsToIndex(row_to_update, &word_starts);
+        word_starts_map_[row_id] = word_starts;
       }
       row_was_updated = true;
     }
   } else {
     // This indexed row no longer qualifies and will be de-indexed by
     // clearing all words associated with this row.
     RemoveRowFromIndex(row);
     row_was_updated = true;
   }
   if (row_was_updated)
@@ skipping 75 matching lines @@
   // the final filtering we need whitespace separated substrings possibly
   // containing escaped characters.
   string16 lower_raw_string(base::i18n::ToLower(search_string));
   string16 lower_unescaped_string =
       net::UnescapeURLComponent(lower_raw_string,
           net::UnescapeRule::SPACES | net::UnescapeRule::URL_SPECIAL_CHARS);
   // Extract individual 'words' (as opposed to 'terms'; see below) from the
   // search string. When the user types "colspec=ID%20Mstone Release" we get
   // four 'words': "colspec", "id", "mstone" and "release".
   String16Vector lower_words(
-      history::String16VectorFromString16(lower_unescaped_string, false));
+      history::String16VectorFromString16(lower_unescaped_string, false, NULL));
   ScoredHistoryMatches scored_items;
 
   // Do nothing if we have indexed no words (probably because we've not been
   // initialized yet) or the search string has no words.
   if (word_list_.empty() || lower_words.empty()) {
     search_term_cache_.clear();  // Invalidate the term cache.
     return scored_items;
   }
 
   // Reset used_ flags for search_term_cache_. We use a basic mark-and-sweep
@@ skipping 91 matching lines @@
 
 void URLIndexPrivateData::AddHistoryMatch::operator()(
     const HistoryID history_id) {
   HistoryInfoMap::const_iterator hist_pos =
       private_data_.history_info_map_.find(history_id);
   // Note that a history_id may be present in the word_id_history_map_ yet not
   // be found in the history_info_map_. This occurs when an item has been
   // deleted by the user or the item no longer qualifies as a quick result.
   if (hist_pos != private_data_.history_info_map_.end()) {
     const URLRow& hist_item = hist_pos->second;
-    ScoredHistoryMatch match(
-        ScoredMatchForURL(hist_item, lower_string_, lower_terms_));
+    WordStartsMap::const_iterator starts_pos =
+        private_data_.word_starts_map_.find(history_id);
+    DCHECK(starts_pos != private_data_.word_starts_map_.end());
+    ScoredHistoryMatch match(ScoredMatchForURL(hist_item, lower_string_,
+                                               lower_terms_,
+                                               starts_pos->second));
     if (match.raw_score > 0)
       scored_matches_.push_back(match);
   }
 }
 
 // static
 // TODO(mrossetti): This can be made a ctor for ScoredHistoryMatch.
 ScoredHistoryMatch URLIndexPrivateData::ScoredMatchForURL(
     const URLRow& row,
     const string16& lower_string,
-    const String16Vector& terms) {
+    const String16Vector& terms,
+    const RowWordStarts& word_starts) {
   ScoredHistoryMatch match(row);
   GURL gurl = row.url();
   if (!gurl.is_valid())
     return match;
 
   // Figure out where each search term appears in the URL and/or page title
   // so that we can score as well as provide autocomplete highlighting.
   string16 url = base::i18n::ToLower(UTF8ToUTF16(gurl.spec()));
   string16 title = base::i18n::ToLower(row.title());
   int term_num = 0;
@@ skipping 95 matching lines @@
     for (size_t i = 1; i < matches.size(); ++i) {
       if (matches[i - 1].term_num > matches[i].term_num)
         ++out_of_order;
     }
     order_value = (max_possible_out_of_order - out_of_order) * kOrderMaxValue /
         max_possible_out_of_order;
   }
 
   // Score component for how early in the match string the first search term
   // appears.  Start with kStartMaxValue points and discount by
-  // kStartMaxValue/kMaxSignificantStart points for each character later than
+  // kStartMaxValue/kMaxSignificantChars points for each character later than
   // the first at which the term begins. No points are earned if the start of
-  // the match occurs at or after kMaxSignificantStart.
-  const size_t kMaxSignificantStart = 50;
+  // the match occurs at or after kMaxSignificantChars.
   const int kStartMaxValue = 1000;
-  int start_value = (kMaxSignificantStart -
-      std::min(kMaxSignificantStart, matches[0].offset)) * kStartMaxValue /
-      kMaxSignificantStart;
+  int start_value = (kMaxSignificantChars -
+      std::min(kMaxSignificantChars, matches[0].offset)) * kStartMaxValue /
+      kMaxSignificantChars;
 
   // Score component for how much of the matched string the input terms cover.
   // kCompleteMaxValue points times the fraction of the URL/page title string
   // that was matched.
   size_t term_length_total = std::accumulate(matches.begin(), matches.end(),
                                              0, AccumulateMatchLength);
   const size_t kMaxSignificantLength = 50;
   size_t max_significant_length =
       std::min(max_length, std::max(term_length_total, kMaxSignificantLength));
   const int kCompleteMaxValue = 1000;
@@ skipping 236 matching lines @@
   }
   UMA_HISTOGRAM_TIMES("History.InMemoryURLIndexSaveCacheTime",
                       base::TimeTicks::Now() - beginning_time);
   return true;
 }
 
 void URLIndexPrivateData::SavePrivateData(
     InMemoryURLIndexCacheItem* cache) const {
   DCHECK(cache);
   cache->set_timestamp(base::Time::Now().ToInternalValue());
+  cache->set_version(saved_cache_version_);
   // history_item_count_ is no longer used but rather than change the protobuf
   // definition use a placeholder. This will go away with the switch to SQLite.
   cache->set_history_item_count(0);
   SaveWordList(cache);
   SaveWordMap(cache);
   SaveCharWordMap(cache);
   SaveWordIDHistoryMap(cache);
   SaveHistoryInfoMap(cache);
+  SaveWordStartsMap(cache);
 }
 
 void URLIndexPrivateData::SaveWordList(InMemoryURLIndexCacheItem* cache) const {
   if (word_list_.empty())
     return;
   WordListItem* list_item = cache->mutable_word_list();
   list_item->set_word_count(word_list_.size());
   for (String16Vector::const_iterator iter = word_list_.begin();
        iter != word_list_.end(); ++iter)
     list_item->add_word(UTF16ToUTF8(*iter));
@@ skipping 64 matching lines @@
     // is no need to save search_term_cache_ (not persistent),
     // languages_, etc.
     map_entry->set_visit_count(url_row.visit_count());
     map_entry->set_typed_count(url_row.typed_count());
     map_entry->set_last_visit(url_row.last_visit().ToInternalValue());
     map_entry->set_url(url_row.url().spec());
     map_entry->set_title(UTF16ToUTF8(url_row.title()));
   }
 }
 
+void URLIndexPrivateData::SaveWordStartsMap(
+    InMemoryURLIndexCacheItem* cache) const {
+  if (word_starts_map_.empty())
+    return;
+  // For unit testing: Enable saving of the cache as an earlier version to
+  // allow testing of cache file upgrading in ReadFromFile().
+  // TODO(mrossetti): Instead of intruding on production code with this kind of
+  // test harness, save a copy of an older version cache with known results.
+  // Implement this when switching the caching over to SQLite.
+  if (saved_cache_version_ < 1)
+    return;
+
+  WordStartsMapItem* map_item = cache->mutable_word_starts_map();
+  map_item->set_item_count(word_starts_map_.size());
+  for (WordStartsMap::const_iterator iter = word_starts_map_.begin();
+       iter != word_starts_map_.end(); ++iter) {
+    WordStartsMapEntry* map_entry = map_item->add_word_starts_map_entry();
+    map_entry->set_history_id(iter->first);
+    const RowWordStarts& word_starts(iter->second);
+    for (WordStarts::const_iterator i = word_starts.url_word_starts_.begin();
+         i != word_starts.url_word_starts_.end(); ++i)
+      map_entry->add_url_word_starts(*i);
+    for (WordStarts::const_iterator i = word_starts.title_word_starts_.begin();
+         i != word_starts.title_word_starts_.end(); ++i)
+      map_entry->add_title_word_starts(*i);
+  }
+}
+
 // Cache Restoring -------------------------------------------------------------
 
 bool URLIndexPrivateData::RestoreFromFile(const FilePath& file_path) {
   // TODO(mrossetti): Figure out how to determine if the cache is up-to-date.
   // That is: ensure that the database has not been modified since the cache
   // was last saved. DB file modification date is inadequate. There are no
   // SQLite table checksums automatically stored.
   Clear();  // Start with a clean slate.
 
   // FIXME(mrossetti): Move File IO to another thread.
@@ skipping 50 matching lines @@
                        rebuilt_data->history_id_word_map_.size());
   UMA_HISTOGRAM_COUNTS_10000("History.InMemoryURLWords",
                              rebuilt_data->word_map_.size());
   UMA_HISTOGRAM_COUNTS_10000("History.InMemoryURLChars",
                              rebuilt_data->char_word_map_.size());
   return rebuilt_data.release();
 }
 
 bool URLIndexPrivateData::RestorePrivateData(
     const InMemoryURLIndexCacheItem& cache) {
+  if (cache.has_version())
+    restored_cache_version_ = cache.version();
   return RestoreWordList(cache) && RestoreWordMap(cache) &&
       RestoreCharWordMap(cache) && RestoreWordIDHistoryMap(cache) &&
-      RestoreHistoryInfoMap(cache);
+      RestoreHistoryInfoMap(cache) && RestoreWordStartsMap(cache);
 }
 
 bool URLIndexPrivateData::RestoreWordList(
     const InMemoryURLIndexCacheItem& cache) {
   if (!cache.has_word_list())
     return false;
   const WordListItem& list_item(cache.word_list());
   uint32 expected_item_count = list_item.word_count();
   uint32 actual_item_count = list_item.word_size();
   if (actual_item_count == 0 || actual_item_count != expected_item_count)
@@ skipping 100 matching lines @@
     url_row.set_last_visit(base::Time::FromInternalValue(iter->last_visit()));
     if (iter->has_title()) {
       string16 title(UTF8ToUTF16(iter->title()));
       url_row.set_title(title);
     }
     history_info_map_[history_id] = url_row;
   }
   return true;
 }
 
+bool URLIndexPrivateData::RestoreWordStartsMap(
+    const InMemoryURLIndexCacheItem& cache) {
+  // Note that this function must be called after RestoreHistoryInfoMap() has
+  // been run as the word starts may have to be recalculated from the urls and
+  // page titles.
+  if (cache.has_word_starts_map()) {
+    const WordStartsMapItem& list_item(cache.word_starts_map());
+    uint32 expected_item_count = list_item.item_count();
+    uint32 actual_item_count = list_item.word_starts_map_entry_size();
+    if (actual_item_count == 0 || actual_item_count != expected_item_count)
+      return false;
+    const RepeatedPtrField<WordStartsMapEntry>&
+        entries(list_item.word_starts_map_entry());
+    for (RepeatedPtrField<WordStartsMapEntry>::const_iterator iter =
+         entries.begin(); iter != entries.end(); ++iter) {
+      HistoryID history_id = iter->history_id();
+      RowWordStarts word_starts;
+      // Restore the URL word starts.
+      const RepeatedField<int32>& url_starts(iter->url_word_starts());
+      for (RepeatedField<int32>::const_iterator jiter = url_starts.begin();
+           jiter != url_starts.end(); ++jiter)
+        word_starts.url_word_starts_.push_back(*jiter);
+      // Restore the page title word starts.
+      const RepeatedField<int32>& title_starts(iter->title_word_starts());
+      for (RepeatedField<int32>::const_iterator jiter = title_starts.begin();
+           jiter != title_starts.end(); ++jiter)
+        word_starts.title_word_starts_.push_back(*jiter);
+      word_starts_map_[history_id] = word_starts;
+    }
+  } else {
+    // Since the cache did not contain any word starts we must rebuild then from
+    // the URL and page titles.
+    for (HistoryInfoMap::const_iterator iter = history_info_map_.begin();
+         iter != history_info_map_.end(); ++iter) {
+      RowWordStarts word_starts;
+      const URLRow& row(iter->second);
+      string16 url(net::FormatUrl(row.url(), languages_,
+          net::kFormatUrlOmitUsernamePassword,
+          net::UnescapeRule::SPACES | net::UnescapeRule::URL_SPECIAL_CHARS,
+          NULL, NULL, NULL));
+      url = base::i18n::ToLower(url);
+      String16VectorFromString16(url, false, &word_starts.url_word_starts_);
+      String16VectorFromString16(
+          row.title(), false, &word_starts.title_word_starts_);
+      word_starts_map_[iter->first] = word_starts;
+    }
+  }
+  return true;
+}
+
 }  // namespace history