Supporting wildcards in max/min version specifications in VariationsService.

Adds a method CompareToWildcardString that will return -1/0/1, similar to 
CompareTo, when a version is smaller, equal to or greater than a wildcard
string such as "1.2.*". Added a method IsValidWildcardString that validates
the format of a wildcard string, and slightly refactored the Version class
to avoid code duplication. For example, CompareToWildcardString and CompareTo
share the new method CompareVersionComponents.

BUG=127077
TEST=See tests for VariationsService, Version

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

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

5 files changed, 238 insertions, 61 deletions

diff --git a/base/version.cc b/base/version.cc
index 1f9bd20..01bf84a 100644
--- a/base/version.cc
+++ b/base/version.cc
@@ -1,4 +1,4 @@
-// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Copyright (c) 2012 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.
 
@@ -11,33 +11,81 @@
 #include "base/string_split.h"
 #include "base/string_util.h"
 
-Version::Version() {
-}
-
-Version::~Version() {
-}
+namespace {
 
-Version::Version(const std::string& version_str) {
+// Parses the |numbers| vector representing the different numbers
+// inside the version string and constructs a vector of valid integers. It stops
+// when it reaches an invalid item (including the wildcard character). |parsed|
+// is the resulting integer vector. Function returns true if all numbers were
+// parsed successfully, false otherwise.
+bool ParseVersionNumbers(const std::string& version_str,
+                         std::vector<uint16>* parsed) {
   std::vector<std::string> numbers;
   base::SplitString(version_str, '.', &numbers);
   if (numbers.empty())
-    return;
-  std::vector<uint16> parsed;
-  for (std::vector<std::string>::iterator i = numbers.begin();
-       i != numbers.end(); ++i) {
+    return false;
+
+  for (std::vector<std::string>::const_iterator it = numbers.begin();
+       it != numbers.end(); ++it) {
     int num;
-    if (!base::StringToInt(*i, &num))
-      return;
+    if (!base::StringToInt(*it, &num))
+      return false;
+
     if (num < 0)
-      return;
+      return false;
+
     const uint16 max = 0xFFFF;
     if (num > max)
-      return;
+      return false;
+
     // This throws out things like +3, or 032.
-    if (base::IntToString(num) != *i)
-      return;
-    parsed.push_back(static_cast<uint16>(num));
+    if (base::IntToString(num) != *it)
+      return false;
+
+    parsed->push_back(static_cast<uint16>(num));
+  }
+  return true;
+}
+
+// Compares version components in |components1| with components in
+// |components2|. Returns -1, 0 or 1 if |components1| is greater than, equal to,
+// or less than |components2|, respectively.
+int CompareVersionComponents(const std::vector<uint16>& components1,
+                             const std::vector<uint16>& components2) {
+  const size_t count = std::min(components1.size(), components2.size());
+  for (size_t i = 0; i < count; ++i) {
+    if (components1[i] > components2[i])
+      return 1;
+    if (components1[i] < components2[i])
+      return -1;
+  }
+  if (components1.size() > components2.size()) {
+    for (size_t i = count; i < components1.size(); ++i) {
+      if (components1[i] > 0)
+        return 1;
+    }
+  } else if (components1.size() < components2.size()) {
+    for (size_t i = count; i < components2.size(); ++i) {
+      if (components2[i] > 0)
+        return -1;
+    }
   }
+  return 0;
+}
+
+}  // namespace
+
+Version::Version() {
+}
+
+Version::~Version() {
+}
+
+Version::Version(const std::string& version_str) {
+  std::vector<uint16> parsed;
+  if (!ParseVersionNumbers(version_str, &parsed))
+    return;
+
   components_.swap(parsed);
 }
 
@@ -45,6 +93,16 @@ bool Version::IsValid() const {
   return (!components_.empty());
 }
 
+// static
+bool Version::IsValidWildcardString(const std::string& wildcard_string) {
+  std::string version_string = wildcard_string;
+  if (EndsWith(wildcard_string.c_str(), ".*", false))
+    version_string = wildcard_string.substr(0, wildcard_string.size() - 2);
+
+  Version version(version_string);
+  return version.IsValid();
+}
+
 bool Version::IsOlderThan(const std::string& version_str) const {
   Version proposed_ver(version_str);
   if (!proposed_ver.IsValid())
@@ -52,6 +110,43 @@ bool Version::IsOlderThan(const std::string& version_str) const {
   return (CompareTo(proposed_ver) < 0);
 }
 
+int Version::CompareToWildcardString(const std::string& wildcard_string) const {
+  DCHECK(IsValid());
+  DCHECK(Version::IsValidWildcardString(wildcard_string));
+
+  // Default behavior if the string doesn't end with a wildcard.
+  if (!EndsWith(wildcard_string.c_str(), ".*", false)) {
+    Version version(wildcard_string);
+    DCHECK(version.IsValid());
+    return CompareTo(version);
+  }
+
+  std::vector<uint16> parsed;
+  const bool success = ParseVersionNumbers(
+      wildcard_string.substr(0, wildcard_string.length() - 2), &parsed);
+  DCHECK(success);
+  const int comparison = CompareVersionComponents(components_, parsed);
+  // If the version is smaller than the wildcard version's |parsed| vector,
+  // then the wildcard has no effect (e.g. comparing 1.2.3 and 1.3.*) and the
+  // version is still smaller. Same logic for equality (e.g. comparing 1.2.2 to
+  // 1.2.2.* is 0 regardless of the wildcard). Under this logic,
+  // 1.2.0.0.0.0 compared to 1.2.* is 0.
+  if (comparison == -1 || comparison == 0)
+    return comparison;
+
+  // Catch the case where the digits of |parsed| are found in |components_|,
+  // which means that the two are equal since |parsed| has a trailing "*".
+  // (e.g. 1.2.3 vs. 1.2.* will return 0). All other cases return 1 since
+  // components is greater (e.g. 3.2.3 vs 1.*).
+  DCHECK_GT(parsed.size(), 0UL);
+  const size_t min_num_comp = std::min(components_.size(), parsed.size());
+  for (size_t i = 0; i < min_num_comp; ++i) {
+    if (components_[i] != parsed[i])
+      return 1;
+  }
+  return 0;
+}
+
 // TODO(cpu): remove this method.
 Version* Version::GetVersionFromString(const std::string& version_str) {
   Version* vers = new Version(version_str);
@@ -77,23 +172,7 @@ bool Version::Equals(const Version& that) const {
 int Version::CompareTo(const Version& other) const {
   DCHECK(IsValid());
   DCHECK(other.IsValid());
-  size_t count = std::min(components_.size(), other.components_.size());
-  for (size_t i = 0; i < count; ++i) {
-    if (components_[i] > other.components_[i])
-      return 1;
-    if (components_[i] < other.components_[i])
-      return -1;
-  }
-  if (components_.size() > other.components_.size()) {
-    for (size_t i = count; i < components_.size(); ++i)
-      if (components_[i] > 0)
-        return 1;
-  } else if (components_.size() < other.components_.size()) {
-    for (size_t i = count; i < other.components_.size(); ++i)
-      if (other.components_[i] > 0)
-        return -1;
-  }
-  return 0;
+  return CompareVersionComponents(components_, other.components_);
 }
 
 const std::string Version::GetString() const {
diff --git a/base/version.h b/base/version.h
index b6029d3..8d45899 100644
--- a/base/version.h
+++ b/base/version.h
@@ -1,4 +1,4 @@
-// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Copyright (c) 2012 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.
 
@@ -30,6 +30,12 @@ class BASE_EXPORT Version {
   // Returns true if the object contains a valid version number.
   bool IsValid() const;
 
+  // Returns true if the version wildcard string is valid. The version wildcard
+  // string may end with ".*" (e.g. 1.2.*, 1.*). Any other arrangement with "*"
+  // is invalid (e.g. 1.*.3 or 1.2.3*). This functions defaults to standard
+  // Version behavior (IsValid) if no wildcard is present.
+  static bool IsValidWildcardString(const std::string& wildcard_string);
+
   // Commonly used pattern. Given a valid version object, compare if a
   // |version_str| results in a newer version. Returns true if the
   // string represents valid version and if the version is greater than
@@ -50,6 +56,12 @@ class BASE_EXPORT Version {
   // Returns -1, 0, 1 for <, ==, >.
   int CompareTo(const Version& other) const;
 
+  // Given a valid version object, compare if a |wildcard_string| results in a
+  // newer version. This function will default to CompareTo if the string does
+  // not end in wildcard sequence ".*". IsValidWildcard(wildcard_string) must be
+  // true before using this function.
+  int CompareToWildcardString(const std::string& wildcard_string) const;
+
   // Return the string representation of this version.
   const std::string GetString() const;
 
diff --git a/base/version_unittest.cc b/base/version_unittest.cc
index 342d0d6..3af2175 100644
--- a/base/version_unittest.cc
+++ b/base/version_unittest.cc
@@ -1,4 +1,4 @@
-// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Copyright (c) 2012 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.
 
@@ -89,3 +89,53 @@ TEST_F(VersionTest, Compare) {
     EXPECT_EQ(lhs->IsOlderThan(cases[i].rhs), (cases[i].expected == -1));
   }
 }
+
+TEST_F(VersionTest, CompareToWildcardString) {
+  static const struct version_compare {
+    const char* lhs;
+    const char* rhs;
+    int expected;
+  } cases[] = {
+    {"1.0", "1.*", 0},
+    {"1.0", "0.*", 1},
+    {"1.0", "2.*", -1},
+    {"1.2.3", "1.2.3.*", 0},
+    {"10.0", "1.0.*", 1},
+    {"1.0", "3.0.*", -1},
+    {"1.4", "1.3.0.*", 1},
+    {"1.3.9", "1.3.*", 0},
+    {"1.4.1", "1.3.*", 1},
+    {"1.3", "1.4.5.*", -1},
+    {"1.5", "1.4.5.*", 1},
+    {"1.3.9", "1.3.*", 0},
+    {"1.2.0.0.0.0", "1.2.*", 0},
+  };
+  for (size_t i = 0; i < ARRAYSIZE_UNSAFE(cases); ++i) {
+    const Version version(cases[i].lhs);
+    const int result = version.CompareToWildcardString(cases[i].rhs);
+    EXPECT_EQ(result, cases[i].expected) << cases[i].lhs << "?" << cases[i].rhs;
+  }
+}
+
+TEST_F(VersionTest, IsValidWildcardString) {
+  static const struct version_compare {
+    const char* version;
+    bool expected;
+  } cases[] = {
+    {"1.0", true},
+    {"", false},
+    {"1.2.3.4.5.6", true},
+    {"1.2.3.*", true},
+    {"1.2.3.5*", false},
+    {"1.2.3.56*", false},
+    {"1.*.3", false},
+    {"20.*", true},
+    {"+2.*", false},
+    {"*", false},
+    {"*.2", false},
+  };
+  for (size_t i = 0; i < ARRAYSIZE_UNSAFE(cases); ++i) {
+    EXPECT_EQ(Version::IsValidWildcardString(cases[i].version),
+        cases[i].expected) << cases[i].version << "?" << cases[i].expected;
+  }
+}
diff --git a/chrome/browser/metrics/variations_service.cc b/chrome/browser/metrics/variations_service.cc
index 57c794a..d2e3bc7 100644
--- a/chrome/browser/metrics/variations_service.cc
+++ b/chrome/browser/metrics/variations_service.cc
@@ -282,18 +282,12 @@ bool VariationsService::CheckStudyVersion(
   }
 
   if (filter.has_min_version()) {
-    const Version min_version(filter.min_version());
-    if (!min_version.IsValid())
-      return false;
-    if (version.CompareTo(min_version) < 0)
+    if (version.CompareToWildcardString(filter.min_version()) < 0)
       return false;
   }
 
   if (filter.has_max_version()) {
-    const Version max_version(filter.max_version());
-    if (!max_version.IsValid())
-      return false;
-    if (version.CompareTo(max_version) > 0)
+    if (version.CompareToWildcardString(filter.max_version()) > 0)
       return false;
   }
 
@@ -333,6 +327,18 @@ bool VariationsService::ValidateStudyAndComputeTotalProbability(
     DVLOG(1) << study.name() << " has no default experiment defined.";
     return false;
   }
+  if (study.filter().has_min_version() &&
+      !Version::IsValidWildcardString(study.filter().min_version())) {
+    DVLOG(1) << study.name() << " has invalid min version: "
+             << study.filter().min_version();
+    return false;
+  }
+  if (study.filter().has_max_version() &&
+      !Version::IsValidWildcardString(study.filter().max_version())) {
+    DVLOG(1) << study.name() << " has invalid max version: "
+             << study.filter().max_version();
+    return false;
+  }
 
   const std::string& default_group_name = study.default_experiment_name();
   base::FieldTrial::Probability divisor = 0;
diff --git a/chrome/browser/metrics/variations_service_unittest.cc b/chrome/browser/metrics/variations_service_unittest.cc
index 0008475..5c306a2 100644
--- a/chrome/browser/metrics/variations_service_unittest.cc
+++ b/chrome/browser/metrics/variations_service_unittest.cc
@@ -130,6 +130,13 @@ TEST(VariationsServiceTest, CheckStudyVersion) {
     { "1.3.2", "1.2.3", false },
     { "2.1.2", "1.2.3", false },
     { "0.3.4", "1.2.3", true },
+    // Wildcards.
+    { "1.*", "1.2.3", true },
+    { "1.2.*", "1.2.3", true },
+    { "1.2.3.*", "1.2.3", true },
+    { "1.2.4.*", "1.2.3", false },
+    { "2.*", "1.2.3", false },
+    { "0.3.*", "1.2.3", true },
   };
 
   const struct {
@@ -142,6 +149,15 @@ TEST(VariationsServiceTest, CheckStudyVersion) {
     { "1.2.4", "1.2.3", true },
     { "2.1.1", "1.2.3", true },
     { "2.1.1", "2.3.4", false },
+    // Wildcards
+    { "2.1.*", "2.3.4", false },
+    { "2.*", "2.3.4", true },
+    { "2.3.*", "2.3.4", true },
+    { "2.3.4.*", "2.3.4", true },
+    { "2.3.4.0.*", "2.3.4", true },
+    { "2.4.*", "2.3.4", true },
+    { "1.3.*", "2.3.4", false },
+    { "1.*", "2.3.4", false },
   };
 
   chrome_variations::Study_Filter filter;
@@ -154,7 +170,7 @@ TEST(VariationsServiceTest, CheckStudyVersion) {
     const bool result =
         VariationsService::CheckStudyVersion(filter, min_test_cases[i].version);
     EXPECT_EQ(min_test_cases[i].expected_result, result) <<
-        "Case " << i << " failed!";
+        "Min. version case " << i << " failed!";
   }
   filter.clear_min_version();
 
@@ -163,7 +179,7 @@ TEST(VariationsServiceTest, CheckStudyVersion) {
     const bool result =
         VariationsService::CheckStudyVersion(filter, max_test_cases[i].version);
     EXPECT_EQ(max_test_cases[i].expected_result, result) <<
-        "Case " << i << " failed!";
+        "Max version case " << i << " failed!";
   }
 
   // Check intersection semantics.
@@ -189,20 +205,6 @@ TEST(VariationsServiceTest, CheckStudyVersion) {
   }
 }
 
-// The current client logic does not handle version number strings containing
-// wildcards. Check that any such values received from the server result in the
-// study being disqualified.
-TEST(VariationsServiceTest, CheckStudyVersionWildcards) {
-  chrome_variations::Study_Filter filter;
-
-  filter.set_min_version("1.0.*");
-  EXPECT_FALSE(VariationsService::CheckStudyVersion(filter, "1.2.3"));
-
-  filter.clear_min_version();
-  filter.set_max_version("2.0.*");
-  EXPECT_FALSE(VariationsService::CheckStudyVersion(filter, "1.2.3"));
-}
-
 TEST(VariationsServiceTest, CheckStudyStartDate) {
   const base::Time now = base::Time::Now();
   const base::TimeDelta delta = base::TimeDelta::FromHours(1);
@@ -271,6 +273,34 @@ TEST(VariationsServiceTest, ValidateStudy) {
   EXPECT_TRUE(valid);
   EXPECT_EQ(300, total_probability);
 
+  // Min version checks.
+  study.mutable_filter()->set_min_version("1.2.3.*");
+  valid = VariationsService::ValidateStudyAndComputeTotalProbability(
+      study, &total_probability);
+  EXPECT_TRUE(valid);
+  study.mutable_filter()->set_min_version("1.*.3");
+  valid = VariationsService::ValidateStudyAndComputeTotalProbability(
+      study, &total_probability);
+  EXPECT_FALSE(valid);
+  study.mutable_filter()->set_min_version("1.2.3");
+  valid = VariationsService::ValidateStudyAndComputeTotalProbability(
+      study, &total_probability);
+  EXPECT_TRUE(valid);
+
+  // Max version checks.
+  study.mutable_filter()->set_max_version("2.3.4.*");
+  valid = VariationsService::ValidateStudyAndComputeTotalProbability(
+      study, &total_probability);
+  EXPECT_TRUE(valid);
+  study.mutable_filter()->set_max_version("*.3");
+  valid = VariationsService::ValidateStudyAndComputeTotalProbability(
+      study, &total_probability);
+  EXPECT_FALSE(valid);
+  study.mutable_filter()->set_max_version("2.3.4");
+  valid = VariationsService::ValidateStudyAndComputeTotalProbability(
+      study, &total_probability);
+  EXPECT_TRUE(valid);
+
   study.clear_default_experiment_name();
   valid = VariationsService::ValidateStudyAndComputeTotalProbability(study,
       &total_probability);