Omnibox - HistoryQuick Provider - Don't Run Duplicate Searches

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>
 #include <limits>
 #include <numeric>
+#include <set>
 #include <string>
 #include <vector>
 
 #include "base/files/file_util.h"
 #include "base/i18n/break_iterator.h"
 #include "base/i18n/case_conversion.h"
 #include "base/macros.h"
 #include "base/metrics/histogram_macros.h"
 #include "base/strings/string_split.h"
 #include "base/strings/string_util.h"
@@ skipping 118 matching lines @@
     : restored_cache_version_(0),
       saved_cache_version_(kCurrentCacheFileVersion) {}
 
 ScoredHistoryMatches URLIndexPrivateData::HistoryItemsForTerms(
     base::string16 original_search_string,
     size_t cursor_position,
     size_t max_matches,
     bookmarks::BookmarkModel* bookmark_model,
     TemplateURLService* template_url_service) {
   // This list will contain the original search string and any other string
   // transformations.

[Peter Kasting, 2017/05/05 23:07:34]

This comment sounds as if we envision many different transformations.  Do we
think we'll add more in the future?  You vetoed checking the vector length
(instead of using a set) on the basis of confusion/maintenance risk here; it
would be nice to just make this more explicitly about this specific
transformation, if that's all we ever planned to do.

(Secretly I'm still hoping to get back to the vector length check to reduce heap
churn in inner loops.)

[Mark P, 2017/05/08 22:46:19]

One obvious one that comes to mind is rewriting 's away.  I.e., if I type
mark's, we also search for mark.  This doesn't change the number of terms.

   String16Vector search_strings;
   search_strings.push_back(original_search_string);
   if ((cursor_position != base::string16::npos) &&
       (cursor_position < original_search_string.length()) &&
       (cursor_position > 0)) {
     // The original search_string broken at cursor position. This is one type of
     // transformation.

[Peter Kasting, 2017/05/05 23:07:34]

Nit: It might be nice, either here or below, to comment about the connection
between this and the "duplicate check", i.e. that this may not actually break
any words and that's why we check for duplicates later.

[Mark P, 2017/05/08 22:46:19]

Done.

     base::string16 transformed_search_string(original_search_string);
     transformed_search_string.insert(cursor_position, base::ASCIIToUTF16(" "));
     search_strings.push_back(transformed_search_string);
   }
 
   ScoredHistoryMatches scored_items;
   // Invalidate the term cache and return if we have indexed no words (probably
   // because we've not been initialized yet).
   if (word_list_.empty()) {
     search_term_cache_.clear();
     return scored_items;
   }
   // Reset used_ flags for search_term_cache_. We use a basic mark-and-sweep
   // approach.
   ResetSearchTermCache();
 
   bool history_ids_were_trimmed = false;
+  // A set containing the list of words extracted from each search string,
+  // used to prevent running duplicate searches.
+  std::set<String16Vector> search_string_words;
   for (const base::string16& search_string : search_strings) {
     // 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_unescaped_string = 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 comment in
     // HistoryIdsToScoredMatches()) 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));
     if (lower_words.empty())
       continue;
+    // If we've already searched for this list of words, don't do it again.
+    if (search_string_words.find(lower_words) != search_string_words.end())

[Peter Kasting, 2017/05/05 23:07:34]

Nit: Or base::ContainsKey(search_string_words, lower_words)

(You may or may not find this easier to read)

[Mark P, 2017/05/08 22:46:19]

Left as-is.  I find the current code a bit more readable.  It also better fits
local style (see lines 1211, 1267, and 1270 for examples).

+      continue;
+    search_string_words.insert(lower_words);
 
     HistoryIDVector history_ids = HistoryIDsFromWords(lower_words);
     history_ids_were_trimmed |= TrimHistoryIdsPool(&history_ids);
 
     HistoryIdsToScoredMatches(std::move(history_ids), lower_raw_string,
                               template_url_service, bookmark_model,
                               &scored_items);
   }
   // Select and sort only the top |max_matches| results.
   if (scored_items.size() > max_matches) {
@@ skipping 1061 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());
 }