Generating autocomplete results with and without word breaks in the Omnibox.

components/omnibox/browser/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 "components/omnibox/browser/url_index_private_data.h"
 
 #include <stdint.h>
 
 #include <functional>
 #include <iterator>
@@ skipping 134 matching lines @@
 // URLIndexPrivateData ---------------------------------------------------------
 
 URLIndexPrivateData::URLIndexPrivateData()
     : restored_cache_version_(0),
       saved_cache_version_(kCurrentCacheFileVersion),
       pre_filter_item_count_(0),
       post_filter_item_count_(0),
       post_scoring_item_count_(0) {
 }
 
-ScoredHistoryMatches URLIndexPrivateData::HistoryItemsForTerms(
-    base::string16 search_string,
-    size_t cursor_position,
-    size_t max_matches,
-    bookmarks::BookmarkModel* bookmark_model,
-    TemplateURLService* template_url_service) {
-  // If cursor position is set and useful (not at either end of the
-  // string), allow the search string to be broken at cursor position.
-  // We do this by pretending there's a space where the cursor is.
-  if ((cursor_position != base::string16::npos) &&
-      (cursor_position < search_string.length()) &&
-      (cursor_position > 0)) {
-    search_string.insert(cursor_position, base::ASCIIToUTF16(" "));
-  }
-  pre_filter_item_count_ = 0;
-  post_filter_item_count_ = 0;
-  post_scoring_item_count_ = 0;
+HistoryIDSet URLIndexPrivateData::HistoryItemsForWords(
+  base::string16 search_string) {
+
+  HistoryIDSet history_id_set;

[Mark P, 2016/08/10 17:46:19]

This variable isn't needed; simply return HistoryIDSet() at the first return
below and return HistoryIDSetFromWords(lower_words) at the second return, no
need to create an intermediate copy within the function.

[Lavar Askew, 2016/08/18 03:07:51]

Done.

+
   // The search string we receive may contain escaped characters. For reducing
   // the index we need individual, lower-cased words, ignoring escapings. For
   // the final filtering we need whitespace separated substrings possibly
   // containing escaped characters.
-  base::string16 lower_raw_string(base::i18n::ToLower(search_string));
+  base::string16 lower_raw_string(
+    base::i18n::ToLower(search_string));
   base::string16 lower_unescaped_string =
-      net::UnescapeURLComponent(lower_raw_string,
-          net::UnescapeRule::SPACES | net::UnescapeRule::PATH_SEPARATORS |
-          net::UnescapeRule::URL_SPECIAL_CHARS_EXCEPT_PATH_SEPARATORS);
+    net::UnescapeURLComponent(lower_raw_string,
+      net::UnescapeRule::SPACES | net::UnescapeRule::PATH_SEPARATORS |
+      net::UnescapeRule::URL_SPECIAL_CHARS_EXCEPT_PATH_SEPARATORS);
   // 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(
-      String16VectorFromString16(lower_unescaped_string, false, nullptr));
-  ScoredHistoryMatches scored_items;
+    String16VectorFromString16(
+      lower_unescaped_string, false, nullptr));
 
   // 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;
+    return history_id_set;
   }
 
-  // Reset used_ flags for search_term_cache_. We use a basic mark-and-sweep
-  // approach.
-  ResetSearchTermCache();
+  history_id_set =
+    HistoryIDSetFromWords(lower_words);
 
-  HistoryIDSet history_id_set = HistoryIDSetFromWords(lower_words);
+  return history_id_set;
+}
 
-  // Trim the candidate pool if it is large. Note that we do not filter out
-  // items that do not contain the search terms as proper substrings -- doing
-  // so is the performance-costly operation we are trying to avoid in order
-  // to maintain omnibox responsiveness.
-  const size_t kItemsToScoreLimit = 500;
-  pre_filter_item_count_ = history_id_set.size();
-  // If we trim the results set we do not want to cache the results for next
-  // time as the user's ultimately desired result could easily be eliminated
-  // in this early rough filter.
-  bool was_trimmed = (pre_filter_item_count_ > kItemsToScoreLimit);
-  if (was_trimmed) {
-    HistoryIDVector history_ids;
-    std::copy(history_id_set.begin(), history_id_set.end(),
-              std::back_inserter(history_ids));
-    // Trim down the set by sorting by typed-count, visit-count, and last
-    // visit.
-    HistoryItemFactorGreater
-        item_factor_functor(history_info_map_);
-    std::partial_sort(history_ids.begin(),
-                      history_ids.begin() + kItemsToScoreLimit,
-                      history_ids.end(),
-                      item_factor_functor);
-    history_id_set.clear();
-    std::copy(history_ids.begin(), history_ids.begin() + kItemsToScoreLimit,
-              std::inserter(history_id_set, history_id_set.end()));
-    post_filter_item_count_ = history_id_set.size();
-  }
+ScoredHistoryMatches URLIndexPrivateData::GetScoredItemsForSearchString (
+    base::string16 search_string,
+    HistoryIDSet history_id_set,
+    size_t max_matches,
+    bookmarks::BookmarkModel* bookmark_model,
+    TemplateURLService* template_url_service) {
+  ScoredHistoryMatches scored_items;
 
   // Pass over all of the candidates filtering out any without a proper
   // substring match, inserting those which pass in order by score. Note that
   // in this step we are using the raw search string complete with escaped
   // URL elements. When the user has specifically typed something akin to
   // "sort=pri&colspec=ID%20Mstone%20Release" we want to make sure that that
   // specific substring appears in the URL or page title.
 
   // We call these 'terms' (as opposed to 'words'; see above) as in this case
   // we only want to break up the search string on 'true' whitespace rather than
   // escaped whitespace. When the user types "colspec=ID%20Mstone Release" we
   // get two 'terms': "colspec=id%20mstone" and "release".
+  base::string16 lower_raw_string(
+    base::i18n::ToLower(search_string));
   String16Vector lower_raw_terms = base::SplitString(
       lower_raw_string, base::kWhitespaceUTF16, base::KEEP_WHITESPACE,
       base::SPLIT_WANT_NONEMPTY);
+
   if (lower_raw_terms.empty()) {
     // Don't score matches when there are no terms to score against.  (It's
     // possible that the word break iterater that extracts words to search
     // for in the database allows some whitespace "words" whereas SplitString
     // excludes a long list of whitespace.)  One could write a scoring
     // function that gives a reasonable order to matches when there
     // are no terms (i.e., all the words are some form of whitespace),
     // but this is such a rare edge case that it's not worth the time.
     return scored_items;
   }
   scored_items =
       std::for_each(
           history_id_set.begin(), history_id_set.end(),
           AddHistoryMatch(bookmark_model, template_url_service, *this,
                           lower_raw_string, lower_raw_terms,
                           base::Time::Now())).ScoredMatches();
 
   // Select and sort only the top |max_matches| results.
   if (scored_items.size() > max_matches) {
     std::partial_sort(scored_items.begin(),
                       scored_items.begin() +
                           max_matches,
                       scored_items.end(),
                       ScoredHistoryMatch::MatchScoreGreater);
-      scored_items.resize(max_matches);
-  } else {
+    scored_items.resize(max_matches);
+  }
+  else {
     std::sort(scored_items.begin(), scored_items.end(),
               ScoredHistoryMatch::MatchScoreGreater);
   }
-  post_scoring_item_count_ = scored_items.size();
-
-  if (was_trimmed) {
-    search_term_cache_.clear();  // Invalidate the term cache.
-  } else {
-    // Remove any stale SearchTermCacheItems.
-    for (SearchTermCacheMap::iterator cache_iter = search_term_cache_.begin();
-         cache_iter != search_term_cache_.end(); ) {
-      if (!cache_iter->second.used_)
-        search_term_cache_.erase(cache_iter++);
-      else
-        ++cache_iter;
-    }
-  }
 
   return scored_items;
 }
 
+
+bool URLIndexPrivateData::TrimCandidatePool (HistoryIDSet history_id_set) {
+
+  // Trim the candidate pool if it is large. Note that we do not filter out

[Mark P, 2016/08/10 17:46:19]

I assume this whole block was copied with no modifications.

[Lavar Askew, 2016/08/18 03:07:51]

Yes, you are correct.

Done.

+  // items that do not contain the search terms as proper substrings -- doing
+  // so is the performance-costly operation we are trying to avoid in order
+  // to maintain omnibox responsiveness.
+  const size_t kItemsToScoreLimit = 500;
+  pre_filter_item_count_ = history_id_set.size();
+  // If we trim the results set we do not want to cache the results for next
+  // time as the user's ultimately desired result could easily be eliminated
+  // in this early rough filter.
+  bool was_trimmed = (pre_filter_item_count_ > kItemsToScoreLimit);
+  if (was_trimmed) {
+    HistoryIDVector history_ids;
+    std::copy(history_id_set.begin(), history_id_set.end(),
+              std::back_inserter(history_ids));
+    // Trim down the set by sorting by typed-count, visit-count, and last
+    // visit.
+    HistoryItemFactorGreater
+        item_factor_functor(history_info_map_);
+    std::partial_sort(history_ids.begin(),
+                      history_ids.begin() + kItemsToScoreLimit,
+                      history_ids.end(),
+                      item_factor_functor);
+    history_id_set.clear();
+    std::copy(history_ids.begin(), history_ids.begin() + kItemsToScoreLimit,
+              std::inserter(history_id_set, history_id_set.end()));
+    post_filter_item_count_ = history_id_set.size();
+  }
+
+  return was_trimmed;
+}
+
+ScoredHistoryMatches URLIndexPrivateData::HistoryItemsForTerms(
+    base::string16 search_string,
+    size_t cursor_position,
+    size_t max_matches,
+    bookmarks::BookmarkModel* bookmark_model,
+    TemplateURLService* template_url_service) {
+  pre_filter_item_count_ = 0;
+  post_filter_item_count_ = 0;
+  post_scoring_item_count_ = 0;
+
+  // Reset used_ flags for search_term_cache_. We use a basic mark-and-sweep
+  // approach.
+  ResetSearchTermCache();
+
+  HistoryIDSet history_id_set = HistoryItemsForWords(search_string);
+
+  bool history_id_set_without_word_break_was_trimmed =
+    TrimCandidatePool(history_id_set);
+
+  ScoredHistoryMatches scored_items_without_word_break =
+    GetScoredItemsForSearchString(
+      search_string,
+      history_id_set,
+      max_matches,
+      bookmark_model,
+      template_url_service);
+
+  ScoredHistoryMatches all_scored_items;
+  ScoredHistoryMatches scored_items_with_word_break;
+
+  bool history_id_set_with_word_break_was_trimmed = false;
+
+  // If cursor position is set and useful (not at either end of the
+  // string), allow the search string to be broken at cursor position.
+  // We do this by pretending there's a space where the cursor is.
+  if ((cursor_position != base::string16::npos) &&
+      (cursor_position < search_string.length()) &&
+      (cursor_position > 0)) {
+    base::string16 search_string_with_word_break = search_string;
+    HistoryIDSet history_id_set_with_word_break;
+
+    base::string16 word_break =
+      base::ASCIIToUTF16(" ");
+    search_string_with_word_break.insert(cursor_position, word_break);
+
+    // Add to history_id_set the ids that are related to the original
+    // search string, but with the word break.
+    history_id_set_with_word_break =
+      HistoryItemsForWords(search_string_with_word_break);

[Mark P, 2016/08/10 17:46:19]

This might do unnecessary work if the new search string breaks into the same
words as the old one.  The search term cache may help avoid some of this
unnecessary work, but I think we can do better here.  Can you please improve
this?  Let's not slow down users unnecessarily.

+
+    history_id_set_with_word_break_was_trimmed =
+      TrimCandidatePool (history_id_set_with_word_break);
+
+    scored_items_with_word_break = GetScoredItemsForSearchString(
+      search_string_with_word_break,
+      history_id_set_with_word_break,
+      max_matches,
+      bookmark_model,
+      template_url_service);
+  }
+
+  if (history_id_set_without_word_break_was_trimmed ||
+      history_id_set_with_word_break_was_trimmed) {
+    search_term_cache_.clear();  // Invalidate the term cache.
+  }
+  else {
+    // Remove any stale SearchTermCacheItems.
+    for (SearchTermCacheMap::iterator cache_iter = search_term_cache_.begin();
+         cache_iter != search_term_cache_.end(); ) {
+      if (!cache_iter->second.used_) {
+        search_term_cache_.erase(cache_iter++);
+      }
+      else {
+        ++cache_iter;
+      }
+    }
+  }
+
+  // all_scored_items represents the unification the
+  //ScoredHistoryMatches for the search string with and without the word break.

[Mark P, 2016/08/10 17:46:19]

The code below can be made more efficient and easier to read.  Approximately:
if (without_word_break.empty())
  return with_word_break
with_word_break.insert(with_word_break.end(), without.begin(), without.end())
return with_word_break;

( http://stackoverflow.com/a/2208313 is good reading by the way about what I
skipped the reserve.  Also this technique doesn't need another variable, no need
to copy all those entries to a third variable.)

[Lavar Askew, 2016/08/18 03:07:51]

Done.

+  if (scored_items_without_word_break.size() > 0 &&
+      scored_items_with_word_break.size() > 0) {
+    post_scoring_item_count_ =
+      scored_items_without_word_break.size()
+      + scored_items_with_word_break.size();
+
+    all_scored_items.reserve(post_scoring_item_count_);
+    all_scored_items.insert(all_scored_items.end(),
+                            scored_items_without_word_break.begin(),
+                            scored_items_without_word_break.end());
+    all_scored_items.insert(all_scored_items.end(),
+                            scored_items_with_word_break.begin(),
+                            scored_items_with_word_break.end());
+  }
+  else if (scored_items_without_word_break.size() == 0 &&
+           scored_items_with_word_break.size() > 0) {
+    all_scored_items = scored_items_with_word_break;
+  }
+  else if (scored_items_without_word_break.size() > 0 &&
+           scored_items_with_word_break.size() == 0) {
+    all_scored_items = scored_items_without_word_break;
+  }
+

[Mark P, 2016/08/10 17:46:19]

I could imagine situations where the items overlap.  You should be removing
duplicates (smartly) here.

[Lavar Askew, 2016/08/18 03:07:51]

Done.

+  return all_scored_items;

[Mark P, 2016/08/10 17:46:19]

Also, the number of items we're supposed to return should be no more than
max_matches.  You need to truncate the list if necessary.  Right now you may be
returning twice that number.

[Lavar Askew, 2016/08/18 03:07:52]

Done.

+}
+
 bool URLIndexPrivateData::UpdateURL(
     history::HistoryService* history_service,
     const history::URLRow& row,
     const std::set<std::string>& scheme_whitelist,
     base::CancelableTaskTracker* tracker) {
   // The row may or may not already be in our index. If it is not already
   // indexed and it qualifies then it gets indexed. If it is already
   // indexed and still qualifies then it gets updated, otherwise it
   // is deleted from the index.
   bool row_was_updated = false;
@@ skipping 1054 matching lines @@
   // First cut: typed count, visit count, recency.
   // TODO(mrossetti): This is too simplistic. Consider an approach which ranks
   // recently visited (within the last 12/24 hours) as highly important. Get
   // input from mpearson.
   if (r1.typed_count() != r2.typed_count())
     return (r1.typed_count() > r2.typed_count());
   if (r1.visit_count() != r2.visit_count())
     return (r1.visit_count() > r2.visit_count());
   return (r1.last_visit() > r2.last_visit());
 }