Omnibox: BookmarksProvider: Make Multiple Prefix Matches Work

components/bookmarks/browser/bookmark_index.cc

 // Copyright 2014 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/bookmarks/browser/bookmark_index.h"
 
 #include <algorithm>
 #include <functional>
 #include <iterator>
 #include <list>
@@ skipping 44 matching lines @@
 // Extract the const Node* stored in a BookmarkClient::NodeTypedCountPair.
 struct NodeTypedCountPairExtractNodeFunctor
     : std::unary_function<NodeTypedCountPair, const BookmarkNode*> {
   const BookmarkNode* operator()(const NodeTypedCountPair& pair) const {
     return pair.first;
   }
 };
 
 }  // namespace
 
-// Used when finding the set of bookmarks that match a query. Each match
-// represents a set of terms (as an interator into the Index) matching the
-// query as well as the set of nodes that contain those terms in their titles.
-struct BookmarkIndex::Match {
-  // List of terms matching the query.
-  std::list<Index::const_iterator> terms;
-
-  // The set of nodes matching the terms. As an optimization this is empty
-  // when we match only one term, and is filled in when we get more than one
-  // term. We can do this as when we have only one matching term we know
-  // the set of matching nodes is terms.front()->second.
-  //
-  // Use nodes_begin() and nodes_end() to get an iterator over the set as
-  // it handles the necessary switching between nodes and terms.front().
-  NodeSet nodes;
-
-  // Returns an iterator to the beginning of the matching nodes. See
-  // description of nodes for why this should be used over nodes.begin().
-  NodeSet::const_iterator nodes_begin() const;
-
-  // Returns an iterator to the beginning of the matching nodes. See
-  // description of nodes for why this should be used over nodes.end().
-  NodeSet::const_iterator nodes_end() const;
-};
-
-BookmarkIndex::NodeSet::const_iterator
-    BookmarkIndex::Match::nodes_begin() const {
-  return nodes.empty() ? terms.front()->second.begin() : nodes.begin();
-}
-
-BookmarkIndex::NodeSet::const_iterator BookmarkIndex::Match::nodes_end() const {
-  return nodes.empty() ? terms.front()->second.end() : nodes.end();
-}
-
 BookmarkIndex::BookmarkIndex(BookmarkClient* client,
                              const std::string& languages)
     : client_(client),
       languages_(languages) {
   DCHECK(client_);
 }
 
 BookmarkIndex::~BookmarkIndex() {
 }
 
@@ skipping 27 matching lines @@
 void BookmarkIndex::GetBookmarksMatching(
     const base::string16& input_query,
     size_t max_count,
     query_parser::MatchingAlgorithm matching_algorithm,
     std::vector<BookmarkMatch>* results) {
   const base::string16 query = Normalize(input_query);
   std::vector<base::string16> terms = ExtractQueryWords(query);
   if (terms.empty())
     return;
 
-  Matches matches;
+  NodeSet matches;
   for (size_t i = 0; i < terms.size(); ++i) {
     if (!GetBookmarksMatchingTerm(
             terms[i], i == 0, matching_algorithm, &matches)) {
       return;
     }
   }
 
   Nodes sorted_nodes;
   SortMatches(matches, &sorted_nodes);
 
   // We use a QueryParser to fill in match positions for us. It's not the most
   // efficient way to go about this, but by the time we get here we know what
   // matches and so this shouldn't be performance critical.
   query_parser::QueryParser parser;
   ScopedVector<query_parser::QueryNode> query_nodes;
   parser.ParseQueryNodes(query, matching_algorithm, &query_nodes.get());
 
   // The highest typed counts should be at the beginning of the results vector
   // so that the best matches will always be included in the results. The loop
   // that calculates result relevance in HistoryContentsProvider::ConvertResults
   // will run backwards to assure higher relevance will be attributed to the
   // best matches.
   for (Nodes::const_iterator i = sorted_nodes.begin();
        i != sorted_nodes.end() && results->size() < max_count;
        ++i)
     AddMatchToResults(*i, &parser, query_nodes.get(), results);
 }
 
-void BookmarkIndex::SortMatches(const Matches& matches,
+void BookmarkIndex::SortMatches(const NodeSet& matches,
                                 Nodes* sorted_nodes) const {
-  NodeSet nodes;
-  for (Matches::const_iterator i = matches.begin(); i != matches.end(); ++i) {
-#if !defined(OS_ANDROID)
-    nodes.insert(i->nodes_begin(), i->nodes_end());
-#else
-    // Work around a bug in the implementation of std::set::insert in the STL
-    // used on android (http://crbug.com/367050).
-    for (NodeSet::const_iterator n = i->nodes_begin(); n != i->nodes_end(); ++n)
-      nodes.insert(nodes.end(), *n);
-#endif
-  }
-  sorted_nodes->reserve(sorted_nodes->size() + nodes.size());
+  sorted_nodes->reserve(matches.size());
   if (client_->SupportsTypedCountForNodes()) {
     NodeTypedCountPairs node_typed_counts;
-    client_->GetTypedCountForNodes(nodes, &node_typed_counts);
+    client_->GetTypedCountForNodes(matches, &node_typed_counts);
     std::sort(node_typed_counts.begin(),
               node_typed_counts.end(),
               NodeTypedCountPairSortFunctor());
     std::transform(node_typed_counts.begin(),
                    node_typed_counts.end(),
                    std::back_inserter(*sorted_nodes),
                    NodeTypedCountPairExtractNodeFunctor());
   } else {
-    sorted_nodes->insert(sorted_nodes->end(), nodes.begin(), nodes.end());
+    sorted_nodes->insert(sorted_nodes->end(), matches.begin(), matches.end());
   }
 }
 
 void BookmarkIndex::AddMatchToResults(
     const BookmarkNode* node,
     query_parser::QueryParser* parser,
     const query_parser::QueryNodeStarVector& query_nodes,
     std::vector<BookmarkMatch>* results) {
   // Check that the result matches the query.  The previous search
   // was a simple per-word search, while the more complex matching
@@ skipping 36 matching lines @@
       BookmarkMatch::ReplaceOffsetsInMatchPositions(url_matches, offsets);
   match.url_match_positions.swap(url_matches);
   match.node = node;
   results->push_back(match);
 }
 
 bool BookmarkIndex::GetBookmarksMatchingTerm(
     const base::string16& term,
     bool first_term,
     query_parser::MatchingAlgorithm matching_algorithm,
-    Matches* matches) {
+    NodeSet* matches) {
   Index::const_iterator i = index_.lower_bound(term);
   if (i == index_.end())
     return false;
 
   if (!query_parser::QueryParser::IsWordLongEnoughForPrefixSearch(
       term, matching_algorithm)) {
     // Term is too short for prefix match, compare using exact match.
     if (i->first != term)
       return false;  // No bookmarks with this term.
 
     if (first_term) {
-      Match match;
-      match.terms.push_back(i);
-      matches->push_back(match);
+      (*matches) = i->second;
       return true;
     }
-    CombineMatchesInPlace(i, matches);
-  } else if (first_term) {
-    // This is the first term and we're doing a prefix match. Loop through
-    // index adding all entries that start with term to matches.
+    CombineMatchesInPlace(i->second, matches);

[Peter Kasting, 2015/01/28 01:59:40]

Is the efficiency gain of this function important, versus doing:

  *matches = STLSetIntersection(i->second, *matches);

...using stl_util.h?  (2 places)

[Mark P, 2015/01/28 18:35:10]

I don't know anything about the efficiency gain; I merely know this is how the
function was before.  I'm inclined to go with your cleaner suggestion (both
places).  Removed the whole CombineMatchesInPlace function.

+  } else {
+    // Loop through index adding all entries that start with term to
+    // |prefix_matches|.
+    NodeSet tmp_prefix_matches;
+    NodeSet* prefix_matches = &tmp_prefix_matches;
+    // If this is the first term, then store the result directly in |matches|
+    // to avoid calls to CombineMatchesInPlace (which does a copy).
+    if (first_term)
+      prefix_matches = matches;

[Peter Kasting, 2015/01/28 01:59:40]

Nit:

    NodeSet* prefix_matches = first_term ? matches : &tmp_prefix_matches;

[Mark P, 2015/01/28 18:35:10]

Done.

     while (i != index_.end() &&
            i->first.size() >= term.size() &&
            term.compare(0, term.size(), i->first, 0, term.size()) == 0) {
-      Match match;
-      match.terms.push_back(i);
-      matches->push_back(match);
+      prefix_matches->insert(i->second.begin(), i->second.end());
       ++i;
     }
-  } else {
-    // Prefix match and not the first term. Loop through index combining
-    // current matches in matches with term, placing result in result.
-    Matches result;
-    while (i != index_.end() &&
-           i->first.size() >= term.size() &&
-           term.compare(0, term.size(), i->first, 0, term.size()) == 0) {
-      CombineMatches(i, *matches, &result);
-      ++i;
-    }
-    matches->swap(result);
+    if (!first_term)
+      CombineMatchesInPlace(*prefix_matches, matches);
   }
   return !matches->empty();
 }
 
-void BookmarkIndex::CombineMatchesInPlace(const Index::const_iterator& index_i,
-                                          Matches* matches) {
-  for (size_t i = 0; i < matches->size(); ) {
-    Match* match = &((*matches)[i]);
-    NodeSet intersection;
-    std::set_intersection(match->nodes_begin(), match->nodes_end(),
-                          index_i->second.begin(), index_i->second.end(),
-                          std::inserter(intersection, intersection.begin()));
-    if (intersection.empty()) {
-      matches->erase(matches->begin() + i);
-    } else {
-      match->terms.push_back(index_i);
-      match->nodes.swap(intersection);
-      ++i;
-    }
+void BookmarkIndex::CombineMatchesInPlace(const NodeSet& matches_to_incorporate,
+                                          NodeSet* matches) {
+  NodeSet intersection;
+  std::set_intersection(matches->begin(),
+                        matches->end(),
+                        matches_to_incorporate.begin(),
+                        matches_to_incorporate.end(),
+                        std::inserter(intersection, intersection.begin()));
+  if (intersection.empty()) {
+    // In case of an empty intersection, skip the swap() for efficiency.

[Peter Kasting, 2015/01/28 01:59:40]

Nit: Can move this above conditional and eliminate {}

[Mark P, 2015/01/28 18:35:10]

Now obsolete.

+    matches->clear();
+  } else {
+    matches->swap(intersection);
   }
 }
 
-void BookmarkIndex::CombineMatches(const Index::const_iterator& index_i,
-                                   const Matches& current_matches,
-                                   Matches* result) {
-  for (size_t i = 0; i < current_matches.size(); ++i) {
-    const Match& match = current_matches[i];
-    NodeSet intersection;
-    std::set_intersection(match.nodes_begin(), match.nodes_end(),
-                          index_i->second.begin(), index_i->second.end(),
-                          std::inserter(intersection, intersection.begin()));
-    if (!intersection.empty()) {
-      result->push_back(Match());
-      Match& combined_match = result->back();
-      combined_match.terms = match.terms;
-      combined_match.terms.push_back(index_i);
-      combined_match.nodes.swap(intersection);
-    }
-  }
-}
-
 std::vector<base::string16> BookmarkIndex::ExtractQueryWords(
     const base::string16& query) {
   std::vector<base::string16> terms;
   if (query.empty())
     return std::vector<base::string16>();
   query_parser::QueryParser parser;
   parser.ParseQueryWords(base::i18n::ToLower(query),
                          query_parser::MatchingAlgorithm::DEFAULT,
                          &terms);
   return terms;
@@ skipping 11 matching lines @@
     // We can get here if the node has the same term more than once. For
     // example, a bookmark with the title 'foo foo' would end up here.
     return;
   }
   i->second.erase(node);
   if (i->second.empty())
     index_.erase(i);
 }
 
 }  // namespace bookmarks