Don't strip punctuation inside quotes in history search queries.

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/string_util.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 15 matching lines @@
       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) {
+void CoalesceAndSortMatchPositions(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
 }
 
+// Returns true if the character is considered non-breaking when it appears in
+// the middle of a word. This can be used to prevent an URL-like query from
+// being broken into multiple words.
+bool IsNonBreakingSymbol(wchar_t ch) {
+  return ch == '.' || ch == '-';
+}
+
 }  // namespace
 
 // Inheritance structure:
 // Queries are represented as trees of QueryNodes.
 // QueryNodes are either a collection of subnodes (a QueryNodeList)
 // or a single word (a QueryNodeWord).
 
-// A QueryNodeWord is a single word in the query.
+// A QueryNodeWord is a sequence of consecutive characters in a query.
+// It can be an actual word or an URL-like sequence of characters.
 class QueryNodeWord : public QueryNode {
  public:
   explicit QueryNodeWord(const string16& word);
   virtual ~QueryNodeWord();
 
   const string16& word() const { return word_; }
 
   void set_literal(bool literal) { literal_ = literal; }
+  void Append(const string16& word);
 
   // 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 void AppendWords(std::vector<string16>* words) const OVERRIDE;
 
@@ skipping 41 matching lines @@
       return true;
     }
   }
   return false;
 }
 
 void QueryNodeWord::AppendWords(std::vector<string16>* words) const {
   words->push_back(word_);
 }
 
+void QueryNodeWord::Append(const string16& str) {

[sky, 2012/02/10 16:53:35]

Definition should match declaration order (this should be above
AppendToSQLiteQuery.

[Patrick Dubroy, 2012/02/20 11:00:36]

Done.

+  word_ += str;
+}
+
 // 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_; }
 
@@ skipping 186 matching lines @@
     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);
+    CoalesceAndSortMatchPositions(&matches);
     match_positions->swap(matches);
   }
   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);

[Scott Hess - ex-Googler, 2012/02/17 22:34:59]

I don't understand why a stack is needed to parse quoted text.  If !in_quotes,
put the string in a new node and append to root, if in_quotes put the string in
a new node and append to the last node of root (which is the phrase), and if
in_quotes and embedded punctuation, append the string to the last child node of
the last node in root.  But probably not for resolving today :-).

[Patrick Dubroy, 2012/02/20 11:00:36]

I agree. I can fix this up in a follow-up CL if you'd like.

On 2012/02/17 22:34:59, shess wrote:

 
   bool in_quotes = false;  // whether we're currently in a quoted phrase
+  QueryNodeWord* current_word = NULL;
   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()) {
-      QueryNodeWord* word_node = new QueryNodeWord(iter.GetString());
-      if (in_quotes)
-        word_node->set_literal(true);
-      query_stack.back()->AddChild(word_node);
-    } else {  // Punctuation.
-      if (IsQueryQuote(query[iter.prev()])) {
-        if (!in_quotes) {
-          QueryNodeList* quotes_node = new QueryNodePhrase;
-          query_stack.back()->AddChild(quotes_node);
-          query_stack.push_back(quotes_node);
-          in_quotes = true;
-        } else {
-          query_stack.pop_back();  // Stop adding to the quoted phrase.
-          in_quotes = false;
-        }
+    // is not necessarily a word, it could also be a punctuation or whitespace
+    // character. Punctuation is preserved inside quotes, and otherwise removed
+    // except if it is a non-breaking character in the middle of a word.
+
+    wchar_t last_char = query[iter.prev()];

[Scott Hess - ex-Googler, 2012/02/17 22:34:59]

I'm not sure "last_char" is the best description.  AFAICT this is the break
point between the previous token and this token, when used as an index it will
be the first character of the current token.  Reading this line sounds like it's
saying the last character of the previous token.  Maybe first_char?

[Patrick Dubroy, 2012/02/20 11:00:36]

You're right. Not sure why I named it like that. Done.

+    if (IsQueryQuote(last_char)) {

[sky, 2012/02/10 16:53:35]

Should we require the trailing quote character to match the starting quote
character?

[mrossetti, 2012/02/10 17:33:43]

I almost commented on that as well but the existing code doesn't take that into
account. :^/

On 2012/02/10 16:53:35, sky wrote:

[Patrick Dubroy, 2012/02/20 11:00:36]

I think we should. I can address this in a follow-up CL.

+      if (!in_quotes) {
+        QueryNodeList* quotes_node = new QueryNodePhrase;
+        query_stack.back()->AddChild(quotes_node);
+        query_stack.push_back(quotes_node);
+        in_quotes = true;
+      } else {
+        query_stack.pop_back();  // Stop adding to the quoted phrase.
+        in_quotes = false;
       }
+      current_word = NULL;
+    } else if (iter.IsWord() || (in_quotes && !IsWhitespace(last_char))) {
+      // Append to the current word if the new token is a word or a non-
+      // whitespace character inside quotes.

[Scott Hess - ex-Googler, 2012/02/17 22:34:59]

If it's not a word, is it always a single character?  I'd say "non-whitespace
token", just in case that's not a safe assumption.

[Patrick Dubroy, 2012/02/20 11:00:36]

Done.

+      if (current_word) {
+        current_word->Append(iter.GetString());
+      } else {
+        current_word = new QueryNodeWord(iter.GetString());
+        current_word->set_literal(in_quotes);
+        query_stack.back()->AddChild(current_word);
+      }
+    } else if (current_word != NULL) {
+      // Allow non-breaking symbols inside a word.
+      // Any other punctuation or whitespace character ends the current word.
+
+      // TODO(dubroy): Consider sharing code with the omnibox to allow a more
+      // accurate "best guess" of whether a sequence of characters is a URL.
+      if (IsNonBreakingSymbol(last_char))
+        current_word->Append(iter.GetString());

[Scott Hess - ex-Googler, 2012/02/17 22:34:59]

If I understand this right, I'm not sure I buy it.  This means that unquoted
{google.com} will be passed as {google.com}, which the tokenizer will convert to
{google AND . AND com}.  It may be an improvement in that it will filter out
documents which contain {google} and {com} but not {.}, but I'm not sure the
matches will really make sense, as they'll include things like "google
commercial.".  How important do you think prefix matching is in a case like
this?  I think converting it to match {"google.com"} would make some sense.

Mostly I'm thinking that describing out it works is odd.  Saying that it ignores
punctuation is easy, saying that it finds them in that order is easy, but saying
that it treats . like a word is weird (to non-engineer types).

[Patrick Dubroy, 2012/02/20 11:00:36]

I agree. I don't think it's very common to include punctuation but not want to
do an exact match. I also think that the prefix matching for such strings is
also not that important. As long as [google.com] matches things like
"www.google.com" and "google.com/images", I think that's fine. I don't think
people would suffer if a search for [google.co] didn't match "google.com".

There's still the question of whether exact matching should be implemented by
quoting such strings, or by filtering them after the fact. I'm starting to think
that it should just be done here -- it's simpler and less error-prone, I think.

So, the question is: should any punctuation character not surrounded by
whitespace trigger this behaviour? Or only some subset of characters (e.g. those
that can appear in a URL).

+      else
+        current_word = NULL;
     }
   }
 
   root->RemoveEmptySubnodes();
   return true;
 }
 
 void QueryParser::ExtractQueryWords(const string16& text,
                                     std::vector<QueryWord>* 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()) {
       string16 word = iter.GetString();
       if (!word.empty()) {
         words->push_back(QueryWord());
         words->back().word = word;
         words->back().position = iter.prev();
       }
     }
   }
 }