autocomplete: Add AutocompleteMatch::MergeClassifications()

This just moves a classifications-merging loop from
ShortcutsProvider::ClassifyAllMatchesInString() into a
utility method.

BUG=141877
TEST=none


Review URL: https://chromiumcodereview.appspot.com/10911188

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@155919 0039d316-1c4b-4281-b951-d872f2087c98

5 files changed, 122 insertions, 20 deletions

diff --git a/chrome/browser/autocomplete/autocomplete_match.cc b/chrome/browser/autocomplete/autocomplete_match.cc
index d00ac97..a8b092d 100644
--- a/chrome/browser/autocomplete/autocomplete_match.cc
+++ b/chrome/browser/autocomplete/autocomplete_match.cc
@@ -19,6 +19,16 @@
 #include "content/public/common/url_constants.h"
 #include "grit/theme_resources.h"
 
+namespace {
+
+bool IsTrivialClassification(const ACMatchClassifications& classifications) {
+  return classifications.empty() ||
+      ((classifications.size() == 1) &&
+       (classifications.back().style == ACMatchClassification::NONE));
+}
+
+}  // namespace
+
 // AutocompleteMatch ----------------------------------------------------------
 
 // static
@@ -233,6 +243,37 @@ void AutocompleteMatch::ClassifyLocationInString(
 }
 
 // static
+AutocompleteMatch::ACMatchClassifications
+    AutocompleteMatch::MergeClassifications(
+    const ACMatchClassifications& classifications1,
+    const ACMatchClassifications& classifications2) {
+  // We must return the empty vector only if both inputs are truly empty.
+  // The result of merging an empty vector with a single (0, NONE)
+  // classification is the latter one-entry vector.
+  if (IsTrivialClassification(classifications1))
+    return classifications2.empty() ? classifications1 : classifications2;
+  if (IsTrivialClassification(classifications2))
+    return classifications1;
+
+  ACMatchClassifications output;
+  for (ACMatchClassifications::const_iterator i = classifications1.begin(),
+       j = classifications2.begin(); i != classifications1.end();) {
+    AutocompleteMatch::AddLastClassificationIfNecessary(&output,
+        std::max(i->offset, j->offset), i->style | j->style);
+    const size_t next_i_offset = (i + 1) == classifications1.end() ?
+        static_cast<size_t>(-1) : (i + 1)->offset;
+    const size_t next_j_offset = (j + 1) == classifications2.end() ?
+        static_cast<size_t>(-1) : (j + 1)->offset;
+    if (next_i_offset >= next_j_offset)
+      ++j;
+    if (next_j_offset >= next_i_offset)
+      ++i;
+  }
+
+  return output;
+}
+
+// static
 std::string AutocompleteMatch::ClassificationsToString(
     const ACMatchClassifications& classifications) {
   std::string serialized_classifications;
diff --git a/chrome/browser/autocomplete/autocomplete_match.h b/chrome/browser/autocomplete/autocomplete_match.h
index 3296ac4..ca32458 100644
--- a/chrome/browser/autocomplete/autocomplete_match.h
+++ b/chrome/browser/autocomplete/autocomplete_match.h
@@ -144,6 +144,12 @@ struct AutocompleteMatch {
                                        int style,
                                        ACMatchClassifications* classifications);
 
+  // Returns a new vector of classifications containing the merged contents of
+  // |classifications1| and |classifications2|.
+  static ACMatchClassifications MergeClassifications(
+      const ACMatchClassifications& classifications1,
+      const ACMatchClassifications& classifications2);
+
   // Converts classifications to and from a serialized string representation
   // (using comma-separated integers to sequentially list positions and styles).
   static std::string ClassificationsToString(
diff --git a/chrome/browser/autocomplete/autocomplete_match_unittest.cc b/chrome/browser/autocomplete/autocomplete_match_unittest.cc
index b8fe4ed..1d0e4d2 100644
--- a/chrome/browser/autocomplete/autocomplete_match_unittest.cc
+++ b/chrome/browser/autocomplete/autocomplete_match_unittest.cc
@@ -31,3 +31,73 @@ TEST(AutocompleteMatchTest, MoreRelevant) {
               AutocompleteMatch::MoreRelevant(m1, m2));
   }
 }
+
+TEST(AutocompleteMatchTest, MergeClassifications) {
+  // Merging two empty vectors should result in an empty vector.
+  EXPECT_EQ(std::string(),
+      AutocompleteMatch::ClassificationsToString(
+          AutocompleteMatch::MergeClassifications(
+              AutocompleteMatch::ACMatchClassifications(),
+              AutocompleteMatch::ACMatchClassifications())));
+
+  // If one vector is empty and the other is "trivial" but non-empty (i.e. (0,
+  // NONE)), the non-empty vector should be returned.
+  EXPECT_EQ("0,0",
+      AutocompleteMatch::ClassificationsToString(
+          AutocompleteMatch::MergeClassifications(
+              AutocompleteMatch::ClassificationsFromString("0,0"),
+              AutocompleteMatch::ACMatchClassifications())));
+  EXPECT_EQ("0,0",
+      AutocompleteMatch::ClassificationsToString(
+          AutocompleteMatch::MergeClassifications(
+              AutocompleteMatch::ACMatchClassifications(),
+              AutocompleteMatch::ClassificationsFromString("0,0"))));
+
+  // Ditto if the one-entry vector is non-trivial.
+  EXPECT_EQ("0,1",
+      AutocompleteMatch::ClassificationsToString(
+          AutocompleteMatch::MergeClassifications(
+              AutocompleteMatch::ClassificationsFromString("0,1"),
+              AutocompleteMatch::ACMatchClassifications())));
+  EXPECT_EQ("0,1",
+      AutocompleteMatch::ClassificationsToString(
+          AutocompleteMatch::MergeClassifications(
+              AutocompleteMatch::ACMatchClassifications(),
+              AutocompleteMatch::ClassificationsFromString("0,1"))));
+
+  // Merge an unstyled one-entry vector with a styled one-entry vector.
+  EXPECT_EQ("0,1",
+      AutocompleteMatch::ClassificationsToString(
+          AutocompleteMatch::MergeClassifications(
+              AutocompleteMatch::ClassificationsFromString("0,0"),
+              AutocompleteMatch::ClassificationsFromString("0,1"))));
+
+  // Test simple cases of overlap.
+  EXPECT_EQ("0,3," "1,2",
+      AutocompleteMatch::ClassificationsToString(
+          AutocompleteMatch::MergeClassifications(
+              AutocompleteMatch::ClassificationsFromString("0,1," "1,0"),
+              AutocompleteMatch::ClassificationsFromString("0,2"))));
+  EXPECT_EQ("0,3," "1,2",
+      AutocompleteMatch::ClassificationsToString(
+          AutocompleteMatch::MergeClassifications(
+              AutocompleteMatch::ClassificationsFromString("0,2"),
+              AutocompleteMatch::ClassificationsFromString("0,1," "1,0"))));
+
+  // Test the case where both vectors have classifications at the same
+  // positions.
+  EXPECT_EQ("0,3",
+      AutocompleteMatch::ClassificationsToString(
+          AutocompleteMatch::MergeClassifications(
+              AutocompleteMatch::ClassificationsFromString("0,1," "1,2"),
+              AutocompleteMatch::ClassificationsFromString("0,2," "1,1"))));
+
+  // Test an arbitrary complicated case.
+  EXPECT_EQ("0,2," "1,0," "2,1," "4,3," "5,7," "6,3," "7,7," "15,1," "17,0",
+      AutocompleteMatch::ClassificationsToString(
+          AutocompleteMatch::MergeClassifications(
+              AutocompleteMatch::ClassificationsFromString(
+                  "0,0," "2,1," "4,3," "7,7," "10,6," "15,0"),
+              AutocompleteMatch::ClassificationsFromString(
+                  "0,2," "1,0," "5,7," "6,1," "17,0"))));
+}
diff --git a/chrome/browser/autocomplete/shortcuts_provider.cc b/chrome/browser/autocomplete/shortcuts_provider.cc
index 5e320e7..0b52176 100644
--- a/chrome/browser/autocomplete/shortcuts_provider.cc
+++ b/chrome/browser/autocomplete/shortcuts_provider.cc
@@ -294,25 +294,7 @@ ACMatchClassifications ShortcutsProvider::ClassifyAllMatchesInString(
     last_position = std::max(last_position, next_character);
   }
 
-  // Merge match-marking data with original classifications.
-  if ((match_class.size() == 1) &&
-      (match_class.back().style == ACMatchClassification::NONE))
-    return original_class;
-  ACMatchClassifications output;
-  for (ACMatchClassifications::const_iterator i = original_class.begin(),
-       j = match_class.begin(); i != original_class.end();) {
-    AutocompleteMatch::AddLastClassificationIfNecessary(&output,
-        std::max(i->offset, j->offset), i->style | j->style);
-    const size_t next_i_offset = (i + 1) == original_class.end() ?
-        static_cast<size_t>(-1) : (i + 1)->offset;
-    const size_t next_j_offset = (j + 1) == match_class.end() ?
-        static_cast<size_t>(-1) : (j + 1)->offset;
-    if (next_i_offset >= next_j_offset)
-      ++j;
-    if (next_j_offset >= next_i_offset)
-      ++i;
-  }
-  return output;
+  return AutocompleteMatch::MergeClassifications(original_class, match_class);
 }
 
 history::ShortcutsBackend::ShortcutMap::const_iterator
diff --git a/chrome/browser/autocomplete/shortcuts_provider_unittest.cc b/chrome/browser/autocomplete/shortcuts_provider_unittest.cc
index 85a6524..740846e 100644
--- a/chrome/browser/autocomplete/shortcuts_provider_unittest.cc
+++ b/chrome/browser/autocomplete/shortcuts_provider_unittest.cc
@@ -506,7 +506,10 @@ TEST_F(ShortcutsProviderTest, ClassifyAllMatchesInString) {
   // Extra parens in the next line hack around C++03's "most vexing parse".
   class ClassifyTest classify_test5((string16()), ACMatchClassifications());
   ACMatchClassifications spans_j = classify_test5.RunTest(ASCIIToUTF16("man"));
-  ASSERT_EQ(0U, spans_j.size());
+  ASSERT_EQ(1U, spans_j.size());
+  EXPECT_EQ(0U, spans_j.front().offset);
+  EXPECT_EQ(AutocompleteMatch::ACMatchClassification::NONE,
+      spans_j.front().style);
 
   // Matches which end at beginning of classification merge properly.
   matches.clear();