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);
+  WordStarts 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,
+                                             WordStarts* 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);
+        WordStarts 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 WordStarts& 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().

[Peter Kasting, 2012/03/09 02:37:43]

Nit: Is this the best way of doing this?  For most other versioned data storage
migration tests, we keep a copy of an old version in chrome/test/data and then
write code that directly opens and migrates it to check that it does what we
want.  This avoids being as intrusive to the real code that saves these.

[mrossetti, 2012/03/14 23:23:49]

I hear you, and understand. Since saving using protobuf is going to be replaced
in the near future (for some definition of 'near') and because this is pretty
complex data I'm going to leave it as-is for now and see how difficult it would
be to take the proper approach once this caching has moved over to SQLite. I've
added a TODO to remind me of this.

+  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 WordStarts& word_starts(iter->second);
+    for (std::vector<int>::const_iterator siter =
+         word_starts.url_word_starts_.begin();
+         siter != word_starts.url_word_starts_.end(); ++siter)
+      map_entry->add_url_word_starts(*siter);
+    for (std::vector<int>::const_iterator siter =
+         word_starts.title_word_starts_.begin();
+         siter != word_starts.title_word_starts_.end(); ++siter)
+      map_entry->add_title_word_starts(*siter);
+  }
+}
+
 // 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();
+      WordStarts 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();

[Peter Kasting, 2012/03/09 02:37:43]

Nit: Argh... use |i| and |j| rather than |iter| and |jiter|, as |jiter| looks
like a misspelling of "jitter"

+           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) {
+      WordStarts 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