Omnibox: Make URLs of Bookmarks Searchable

components/query_parser/query_parser.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/query_parser/query_parser.h"
 
 #include <algorithm>
 
 #include "base/compiler_specific.h"
 #include "base/i18n/break_iterator.h"
@@ skipping 28 matching lines @@
        i != matches->end(); ) {
     if (SnippetIntersects(mp, *i)) {
       mp.second = std::max(mp.second, i->second);
       i = matches->erase(i);
     } else {
       return;
     }
   }
 }
 
-// Sorts the match positions in |matches| by their first index, then coalesces
-// any match positions that intersect each other.
-void CoalseAndSortMatchPositions(Snippet::MatchPositions* matches) {
-  std::sort(matches->begin(), matches->end(), &CompareMatchPosition);
-  // WARNING: we don't use iterator here as CoalesceMatchesFrom may remove
-  // from matches.
-  for (size_t i = 0; i < matches->size(); ++i)
-    CoalesceMatchesFrom(i, matches);
-}
-
 // Returns true if the character is considered a quote.
 bool IsQueryQuote(wchar_t ch) {
   return ch == '"' ||
          ch == 0xab ||    // left pointing double angle bracket
          ch == 0xbb ||    // right pointing double angle bracket
          ch == 0x201c ||  // left double quotation mark
          ch == 0x201d ||  // right double quotation mark
          ch == 0x201e;    // double low-9 quotation mark
 }
 
@@ skipping 12 matching lines @@
 
   const base::string16& word() const { return word_; }
 
   void set_literal(bool literal) { literal_ = literal; }
 
   // QueryNode:
   virtual int AppendToSQLiteQuery(base::string16* query) const OVERRIDE;
   virtual bool IsWord() const OVERRIDE;
   virtual bool Matches(const base::string16& word, bool exact) const OVERRIDE;
   virtual bool HasMatchIn(
-      const std::vector<QueryWord>& words,
+      const QueryWordVector& words,
       Snippet::MatchPositions* match_positions) const OVERRIDE;
   virtual bool HasMatchIn(
-      const std::vector<QueryWord>& words) const OVERRIDE;
+      const QueryWordVector& words) const OVERRIDE;
   virtual void AppendWords(std::vector<base::string16>* words) const OVERRIDE;
 
  private:
   base::string16 word_;
   bool literal_;
 
   DISALLOW_COPY_AND_ASSIGN(QueryNodeWord);
 };
 
 QueryNodeWord::QueryNodeWord(const base::string16& word)
@@ skipping 15 matching lines @@
   return true;
 }
 
 bool QueryNodeWord::Matches(const base::string16& word, bool exact) const {
   if (exact || !QueryParser::IsWordLongEnoughForPrefixSearch(word_))
     return word == word_;
   return word.size() >= word_.size() &&
          (word_.compare(0, word_.size(), word, 0, word_.size()) == 0);
 }
 
-bool QueryNodeWord::HasMatchIn(const std::vector<QueryWord>& words,
+bool QueryNodeWord::HasMatchIn(const QueryWordVector& words,
                                Snippet::MatchPositions* match_positions) const {
   bool matched = false;
   for (size_t i = 0; i < words.size(); ++i) {
     if (Matches(words[i].word, false)) {
       size_t match_start = words[i].position;
       match_positions->push_back(
           Snippet::MatchPosition(match_start,
                                  match_start + static_cast<int>(word_.size())));
       matched = true;
     }
   }
   return matched;
 }
 
-bool QueryNodeWord::HasMatchIn(const std::vector<QueryWord>& words) const {
+bool QueryNodeWord::HasMatchIn(const QueryWordVector& words) const {
   for (size_t i = 0; i < words.size(); ++i) {
     if (Matches(words[i].word, false))
       return true;
   }
   return false;
 }
 
 void QueryNodeWord::AppendWords(std::vector<base::string16>* words) const {
   words->push_back(word_);
 }
 
 // A QueryNodeList has a collection of QueryNodes which are deleted in the end.
 class QueryNodeList : public QueryNode {
  public:
-  typedef std::vector<QueryNode*> QueryNodeVector;
-
   QueryNodeList();
   virtual ~QueryNodeList();
 
-  QueryNodeVector* children() { return &children_; }
+  QueryNodeStarVector* children() { return &children_; }
 
   void AddChild(QueryNode* node);
 
   // Remove empty subnodes left over from other parsing.
   void RemoveEmptySubnodes();
 
   // QueryNode:
   virtual int AppendToSQLiteQuery(base::string16* query) const OVERRIDE;
   virtual bool IsWord() const OVERRIDE;
   virtual bool Matches(const base::string16& word, bool exact) const OVERRIDE;
   virtual bool HasMatchIn(
-      const std::vector<QueryWord>& words,
+      const QueryWordVector& words,
       Snippet::MatchPositions* match_positions) const OVERRIDE;
-  virtual bool HasMatchIn(
-      const std::vector<QueryWord>& words) const OVERRIDE;
+  virtual bool HasMatchIn(const QueryWordVector& words) const OVERRIDE;
   virtual void AppendWords(std::vector<base::string16>* words) const OVERRIDE;
 
  protected:
   int AppendChildrenToString(base::string16* query) const;
 
-  QueryNodeVector children_;
+  QueryNodeStarVector children_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(QueryNodeList);
 };
 
 QueryNodeList::QueryNodeList() {}
 
 QueryNodeList::~QueryNodeList() {
   STLDeleteElements(&children_);
 }
@@ skipping 23 matching lines @@
 
 bool QueryNodeList::IsWord() const {
   return false;
 }
 
 bool QueryNodeList::Matches(const base::string16& word, bool exact) const {
   NOTREACHED();
   return false;
 }
 
-bool QueryNodeList::HasMatchIn(const std::vector<QueryWord>& words,
+bool QueryNodeList::HasMatchIn(const QueryWordVector& words,
                                Snippet::MatchPositions* match_positions) const {
   NOTREACHED();
   return false;
 }
 
-bool QueryNodeList::HasMatchIn(const std::vector<QueryWord>& words) const {
+bool QueryNodeList::HasMatchIn(const QueryWordVector& words) const {
   NOTREACHED();
   return false;
 }
 
 void QueryNodeList::AppendWords(std::vector<base::string16>* words) const {
   for (size_t i = 0; i < children_.size(); ++i)
     children_[i]->AppendWords(words);
 }
 
 int QueryNodeList::AppendChildrenToString(base::string16* query) const {
   int num_words = 0;
-  for (QueryNodeVector::const_iterator node = children_.begin();
+  for (QueryNodeStarVector::const_iterator node = children_.begin();
        node != children_.end(); ++node) {
     if (node != children_.begin())
       query->push_back(L' ');
     num_words += (*node)->AppendToSQLiteQuery(query);
   }
   return num_words;
 }
 
 // A QueryNodePhrase is a phrase query ("quoted").
 class QueryNodePhrase : public QueryNodeList {
  public:
   QueryNodePhrase();
   virtual ~QueryNodePhrase();
 
   // QueryNodeList:
   virtual int AppendToSQLiteQuery(base::string16* query) const OVERRIDE;
   virtual bool HasMatchIn(
-      const std::vector<QueryWord>& words,
+      const QueryWordVector& words,
       Snippet::MatchPositions* match_positions) const OVERRIDE;
-  virtual bool HasMatchIn(
-      const std::vector<QueryWord>& words) const OVERRIDE;
+  virtual bool HasMatchIn(const QueryWordVector& words) const OVERRIDE;
 
  private:
-  bool MatchesAll(const std::vector<QueryWord>& words,
+  bool MatchesAll(const QueryWordVector& words,
                   const QueryWord** first_word,
                   const QueryWord** last_word) const;
   DISALLOW_COPY_AND_ASSIGN(QueryNodePhrase);
 };
 
 QueryNodePhrase::QueryNodePhrase() {}
 
 QueryNodePhrase::~QueryNodePhrase() {}
 
 int QueryNodePhrase::AppendToSQLiteQuery(base::string16* query) const {
   query->push_back(L'"');
   int num_words = AppendChildrenToString(query);
   query->push_back(L'"');
   return num_words;
 }
 
-bool QueryNodePhrase::MatchesAll(const std::vector<QueryWord>& words,
+bool QueryNodePhrase::MatchesAll(const QueryWordVector& words,
                                  const QueryWord** first_word,
                                  const QueryWord** last_word) const {
   if (words.size() < children_.size())
     return false;
 
   for (size_t i = 0, max = words.size() - children_.size() + 1; i < max; ++i) {
     bool matched_all = true;
     for (size_t j = 0; j < children_.size(); ++j) {
       if (!children_[j]->Matches(words[i + j].word, true)) {
         matched_all = false;
         break;
       }
     }
     if (matched_all) {
       *first_word = &words[i];
       *last_word = &words[i + children_.size() - 1];
       return true;
     }
   }
   return false;
 }
 
 bool QueryNodePhrase::HasMatchIn(
-    const std::vector<QueryWord>& words,
+    const QueryWordVector& words,
     Snippet::MatchPositions* match_positions) const {
   const QueryWord* first_word;
   const QueryWord* last_word;
 
   if (MatchesAll(words, &first_word, &last_word)) {
     match_positions->push_back(
         Snippet::MatchPosition(first_word->position,
                                last_word->position + last_word->word.length()));
       return true;
   }
   return false;
 }
 
-bool QueryNodePhrase::HasMatchIn(const std::vector<QueryWord>& words) const {
+bool QueryNodePhrase::HasMatchIn(const QueryWordVector& words) const {
   const QueryWord* first_word;
   const QueryWord* last_word;
   return MatchesAll(words, &first_word, &last_word);
 }
 
 QueryParser::QueryParser() {}
 
 // static
 bool QueryParser::IsWordLongEnoughForPrefixSearch(const base::string16& word) {
   DCHECK(!word.empty());
@@ skipping 16 matching lines @@
 
 void QueryParser::ParseQueryWords(const base::string16& query,
                                   std::vector<base::string16>* words) {
   QueryNodeList root;
   if (!ParseQueryImpl(query, &root))
     return;
   root.AppendWords(words);
 }
 
 void QueryParser::ParseQueryNodes(const base::string16& query,
-                                  std::vector<QueryNode*>* nodes) {
+                                  QueryNodeStarVector* nodes) {
   QueryNodeList root;
   if (ParseQueryImpl(base::i18n::ToLower(query), &root))
     nodes->swap(*root.children());
 }
 
 bool QueryParser::DoesQueryMatch(const base::string16& text,
-                                 const std::vector<QueryNode*>& query_nodes,
+                                 const QueryNodeStarVector& query_nodes,
                                  Snippet::MatchPositions* match_positions) {
   if (query_nodes.empty())
     return false;
 
-  std::vector<QueryWord> query_words;
+  QueryWordVector query_words;
   base::string16 lower_text = base::i18n::ToLower(text);
   ExtractQueryWords(lower_text, &query_words);
 
   if (query_words.empty())
     return false;
 
   Snippet::MatchPositions matches;
   for (size_t i = 0; i < query_nodes.size(); ++i) {
     if (!query_nodes[i]->HasMatchIn(query_words, &matches))
       return false;
   }
   if (lower_text.length() != text.length()) {
     // The lower case string differs from the original string. The matches are
     // meaningless.
     // TODO(sky): we need a better way to align the positions so that we don't
     // completely punt here.
     match_positions->clear();
   } else {
-    CoalseAndSortMatchPositions(&matches);
+    SortAndCoalesceMatchPositions(&matches);
     match_positions->swap(matches);
   }
   return true;
 }
 
-bool QueryParser::DoesQueryMatch(const std::vector<QueryWord>& query_words,
-                                 const std::vector<QueryNode*>& query_nodes) {
+bool QueryParser::DoesQueryMatch(const QueryWordVector& query_words,
+                                 const QueryNodeStarVector& query_nodes) {
   if (query_nodes.empty() || query_words.empty())
     return false;
 
   for (size_t i = 0; i < query_nodes.size(); ++i) {
     if (!query_nodes[i]->HasMatchIn(query_words))
       return false;
   }
   return true;
 }
 
@@ skipping 32 matching lines @@
         }
       }
     }
   }
 
   root->RemoveEmptySubnodes();
   return true;
 }
 
 void QueryParser::ExtractQueryWords(const base::string16& text,
-                                    std::vector<QueryWord>* words) {
+                                    QueryWordVector* words) {
   base::i18n::BreakIterator iter(text, base::i18n::BreakIterator::BREAK_WORD);
   // TODO(evanm): support a locale here
   if (!iter.Init())
     return;
 
   while (iter.Advance()) {
     // Just found a span between 'prev' (inclusive) and 'pos' (exclusive). It
     // is not necessarily a word, but could also be a sequence of punctuation
     // or whitespace.
     if (iter.IsWord()) {
       base::string16 word = iter.GetString();
       if (!word.empty()) {
         words->push_back(QueryWord());
         words->back().word = word;
         words->back().position = iter.prev();
-      }
+     }
     }
   }
 }
 
+// static
+void QueryParser::SortAndCoalesceMatchPositions(
+    Snippet::MatchPositions* matches) {
+  std::sort(matches->begin(), matches->end(), &CompareMatchPosition);
+  // WARNING: we don't use iterator here as CoalesceMatchesFrom may remove
+  // from matches.
+  for (size_t i = 0; i < matches->size(); ++i)
+    CoalesceMatchesFrom(i, matches);
+}
+
 }  // namespace query_parser