Replace FTS in the history_service with a brute force text search.

chrome/browser/history/query_parser.cc

 // Copyright (c) 2011 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/query_parser.h"
 
 #include <algorithm>
 
 #include "base/compiler_specific.h"
 #include "base/i18n/break_iterator.h"
 #include "base/i18n/case_conversion.h"
 #include "base/logging.h"
 #include "base/stl_util.h"
+#include "base/strings/utf_string_conversions.h"
 
 namespace {
 
 // Returns true if |mp1.first| is less than |mp2.first|. This is used to
 // sort match positions.
 int CompareMatchPosition(const Snippet::MatchPosition& mp1,
                          const Snippet::MatchPosition& mp2) {
   return mp1.first < mp2.first;
 }
 
@@ skipping 57 matching lines @@
 
   void set_literal(bool literal) { literal_ = literal; }
 
   // QueryNode:
   virtual int AppendToSQLiteQuery(string16* query) const OVERRIDE;
   virtual bool IsWord() const OVERRIDE;
   virtual bool Matches(const string16& word, bool exact) const OVERRIDE;
   virtual bool HasMatchIn(
       const std::vector<QueryWord>& words,
       Snippet::MatchPositions* match_positions) const OVERRIDE;
+  virtual bool HasMatchIn(
+      const std::vector<QueryWord>& words) const OVERRIDE;
   virtual void AppendWords(std::vector<string16>* words) const OVERRIDE;
 
  private:
   string16 word_;
   bool literal_;
 
   DISALLOW_COPY_AND_ASSIGN(QueryNodeWord);
 };
 
 QueryNodeWord::QueryNodeWord(const string16& word)
@@ skipping 30 matching lines @@
       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 {
+  for (size_t i = 0; i < words.size(); ++i) {
+    if (Matches(words[i].word, false))
+      return true;
+  }
+  return false;
+}
+
 void QueryNodeWord::AppendWords(std::vector<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_; }
 
   void AddChild(QueryNode* node);
 
   // Remove empty subnodes left over from other parsing.
   void RemoveEmptySubnodes();
 
   // QueryNode:
   virtual int AppendToSQLiteQuery(string16* query) const OVERRIDE;
   virtual bool IsWord() const OVERRIDE;
   virtual bool Matches(const string16& word, bool exact) const OVERRIDE;
   virtual bool HasMatchIn(
       const std::vector<QueryWord>& words,
       Snippet::MatchPositions* match_positions) const OVERRIDE;
+  virtual bool HasMatchIn(
+      const std::vector<QueryWord>& words) const OVERRIDE;
   virtual void AppendWords(std::vector<string16>* words) const OVERRIDE;
 
  protected:
   int AppendChildrenToString(string16* query) const;
 
   QueryNodeVector children_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(QueryNodeList);
 };
@@ skipping 35 matching lines @@
   NOTREACHED();
   return false;
 }
 
 bool QueryNodeList::HasMatchIn(const std::vector<QueryWord>& words,
                                Snippet::MatchPositions* match_positions) const {
   NOTREACHED();
   return false;
 }
 
+bool QueryNodeList::HasMatchIn(const std::vector<QueryWord>& words) const {
+  NOTREACHED();
+  return false;
+}
+
 void QueryNodeList::AppendWords(std::vector<string16>* words) const {
   for (size_t i = 0; i < children_.size(); ++i)
     children_[i]->AppendWords(words);
 }
 
 int QueryNodeList::AppendChildrenToString(string16* query) const {
   int num_words = 0;
   for (QueryNodeVector::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(string16* query) const OVERRIDE;
   virtual bool HasMatchIn(
       const std::vector<QueryWord>& words,
       Snippet::MatchPositions* match_positions) const OVERRIDE;
+  virtual bool HasMatchIn(
+      const std::vector<QueryWord>& words) const OVERRIDE;
 
  private:
+  bool MatchesAll(const std::vector<QueryWord>& words,
+                  const QueryWord** first_word,
+                  const QueryWord** last_word) const;
   DISALLOW_COPY_AND_ASSIGN(QueryNodePhrase);
 };
 
 QueryNodePhrase::QueryNodePhrase() {}
 
 QueryNodePhrase::~QueryNodePhrase() {}
 
 int QueryNodePhrase::AppendToSQLiteQuery(string16* query) const {
   query->push_back(L'"');
   int num_words = AppendChildrenToString(query);
   query->push_back(L'"');
   return num_words;
 }
 
-bool QueryNodePhrase::HasMatchIn(
-    const std::vector<QueryWord>& words,
-    Snippet::MatchPositions* match_positions) const {
+bool QueryNodePhrase::MatchesAll(const std::vector<QueryWord>& 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) {
-      const QueryWord& last_word = words[i + children_.size() - 1];
-      match_positions->push_back(
-          Snippet::MatchPosition(words[i].position,
-                                 last_word.position + last_word.word.length()));
+      *first_word = &words[i];
+      *last_word = &words[i + children_.size() - 1];
       return true;
     }
   }
   return false;
 }
 
+bool QueryNodePhrase::HasMatchIn(
+    const std::vector<QueryWord>& 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 {
+  const QueryWord* first_word;
+  const QueryWord* last_word;
+  return MatchesAll(words, &first_word, &last_word);
+}
+
 QueryParser::QueryParser() {}
 
 // static
 bool QueryParser::IsWordLongEnoughForPrefixSearch(const string16& word) {
   DCHECK(!word.empty());
   size_t minimum_length = 3;
   // We intentionally exclude Hangul Jamos (both Conjoining and compatibility)
   // because they 'behave like' Latin letters. Moreover, we should
   // normalize the former before reaching here.
   if (0xAC00 <= word[0] && word[0] <= 0xD7A3)
@@ skipping 47 matching lines @@
     // 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);
     match_positions->swap(matches);
   }
   return true;
 }
 
+bool QueryParser::DoesQueryMatch(const std::vector<QueryWord>& query_words,
+                                 const std::vector<QueryNode*>& 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;
+}
+
 bool QueryParser::ParseQueryImpl(const string16& query, QueryNodeList* root) {
   base::i18n::BreakIterator iter(query, base::i18n::BreakIterator::BREAK_WORD);
   // TODO(evanm): support a locale here
   if (!iter.Init())
     return false;
 
   // To handle nesting, we maintain a stack of QueryNodeLists.
   // The last element (back) of the stack contains the current, deepest node.
   std::vector<QueryNodeList*> query_stack;
   query_stack.push_back(root);
@@ skipping 41 matching lines @@
     if (iter.IsWord()) {
       string16 word = iter.GetString();
       if (!word.empty()) {
         words->push_back(QueryWord());
         words->back().word = word;
         words->back().position = iter.prev();
       }
     }
   }
 }