Add regular expression support in json_schema component

Add support of "pattern" and "patternProperties" attribute into json_schema, with third_party/re2 as regular expression implementation.

BUG=348551

Review URL: https://codereview.chromium.org/195193002

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

6 files changed, 161 insertions, 34 deletions

diff --git a/components/json_schema/DEPS b/components/json_schema/DEPS
index e7cf2c6f..62035fb 100644
--- a/components/json_schema/DEPS
+++ b/components/json_schema/DEPS
@@ -1,3 +1,4 @@
 include_rules = [
+  "+third_party/re2",
   "+ui/base",
 ]
diff --git a/components/json_schema/json_schema_validator.cc b/components/json_schema/json_schema_validator.cc
index 18558d0..1899ad6 100644
--- a/components/json_schema/json_schema_validator.cc
+++ b/components/json_schema/json_schema_validator.cc
@@ -7,13 +7,17 @@
 #include <algorithm>
 #include <cfloat>
 #include <cmath>
+#include <vector>
 
 #include "base/json/json_reader.h"
+#include "base/logging.h"
+#include "base/memory/scoped_vector.h"
 #include "base/strings/string_number_conversions.h"
 #include "base/strings/string_util.h"
 #include "base/strings/stringprintf.h"
 #include "base/values.h"
 #include "components/json_schema/json_schema_constants.h"
+#include "third_party/re2/re2/re2.h"
 
 namespace schema = json_schema_constants;
 
@@ -86,6 +90,8 @@ bool IsValidSchema(const base::DictionaryValue* dict,
     { schema::kMinLength,               base::Value::TYPE_INTEGER     },
     { schema::kMinimum,                 base::Value::TYPE_DOUBLE      },
     { schema::kOptional,                base::Value::TYPE_BOOLEAN     },
+    { schema::kPattern,                 base::Value::TYPE_STRING      },
+    { schema::kPatternProperties,       base::Value::TYPE_DICTIONARY  },
     { schema::kProperties,              base::Value::TYPE_DICTIONARY  },
     { schema::kTitle,                   base::Value::TYPE_STRING      },
   };
@@ -186,10 +192,29 @@ bool IsValidSchema(const base::DictionaryValue* dict,
     // Validate the "properties" attribute. Each entry maps a key to a schema.
     if (it.key() == schema::kProperties) {
       it.value().GetAsDictionary(&dictionary_value);
-      for (base::DictionaryValue::Iterator it(*dictionary_value);
-           !it.IsAtEnd(); it.Advance()) {
-        if (!it.value().GetAsDictionary(&dictionary_value)) {
-          *error = "Invalid value for properties attribute";
+      for (base::DictionaryValue::Iterator iter(*dictionary_value);
+           !iter.IsAtEnd(); iter.Advance()) {
+        if (!iter.value().GetAsDictionary(&dictionary_value)) {
+          *error = "properties must be a dictionary";
+          return false;
+        }
+        if (!IsValidSchema(dictionary_value, options, error)) {
+          DCHECK(!error->empty());
+          return false;
+        }
+      }
+    }
+
+    // Validate the "patternProperties" attribute. Each entry maps a regular
+    // expression to a schema. The validity of the regular expression expression
+    // won't be checked here for performance reasons. Instead, invalid regular
+    // expressions will be caught as validation errors in Validate().
+    if (it.key() == schema::kPatternProperties) {
+      it.value().GetAsDictionary(&dictionary_value);
+      for (base::DictionaryValue::Iterator iter(*dictionary_value);
+           !iter.IsAtEnd(); iter.Advance()) {
+        if (!iter.value().GetAsDictionary(&dictionary_value)) {
+          *error = "patternProperties must be a dictionary";
           return false;
         }
         if (!IsValidSchema(dictionary_value, options, error)) {
@@ -308,6 +333,8 @@ const char JSONSchemaValidator::kInvalidType[] =
     "Expected '*' but got '*'.";
 const char JSONSchemaValidator::kInvalidTypeIntegerNumber[] =
     "Expected 'integer' but got 'number', consider using Math.round().";
+const char JSONSchemaValidator::kInvalidRegex[] =
+    "Regular expression /*/ is invalid: *";
 
 
 // static
@@ -551,8 +578,7 @@ void JSONSchemaValidator::ValidateObject(const base::DictionaryValue* instance,
                                          const base::DictionaryValue* schema,
                                          const std::string& path) {
   const base::DictionaryValue* properties = NULL;
-  schema->GetDictionary(schema::kProperties, &properties);
-  if (properties) {
+  if (schema->GetDictionary(schema::kProperties, &properties)) {
     for (base::DictionaryValue::Iterator it(*properties); !it.IsAtEnd();
          it.Advance()) {
       std::string prop_path = path.empty() ? it.key() : (path + "." + it.key());
@@ -575,16 +601,52 @@ void JSONSchemaValidator::ValidateObject(const base::DictionaryValue* instance,
   }
 
   const base::DictionaryValue* additional_properties_schema = NULL;
-  if (SchemaAllowsAnyAdditionalItems(schema, &additional_properties_schema))
-    return;
+  bool allow_any_additional_properties =
+      SchemaAllowsAnyAdditionalItems(schema, &additional_properties_schema);
 
-  // Validate additional properties.
+  const base::DictionaryValue* pattern_properties = NULL;
+  ScopedVector<re2::RE2> pattern_properties_pattern;
+  std::vector<const base::DictionaryValue*> pattern_properties_schema;
+
+  if (schema->GetDictionary(schema::kPatternProperties, &pattern_properties)) {
+    for (base::DictionaryValue::Iterator it(*pattern_properties); !it.IsAtEnd();
+         it.Advance()) {
+      re2::RE2* prop_pattern = new re2::RE2(it.key());
+      if (!prop_pattern->ok()) {
+        LOG(WARNING) << "Regular expression /" << it.key()
+                     << "/ is invalid: " << prop_pattern->error() << ".";
+        errors_.push_back(
+            Error(path,
+                  FormatErrorMessage(
+                      kInvalidRegex, it.key(), prop_pattern->error())));
+        continue;
+      }
+      const base::DictionaryValue* prop_schema = NULL;
+      CHECK(it.value().GetAsDictionary(&prop_schema));
+      pattern_properties_pattern.push_back(prop_pattern);
+      pattern_properties_schema.push_back(prop_schema);
+    }
+  }
+
+  // Validate pattern properties and additional properties.
   for (base::DictionaryValue::Iterator it(*instance); !it.IsAtEnd();
        it.Advance()) {
-    if (properties && properties->HasKey(it.key()))
+    std::string prop_path = path.empty() ? it.key() : path + "." + it.key();
+
+    bool found_matching_pattern = false;
+    for (size_t index = 0; index < pattern_properties_pattern.size(); ++index) {
+      if (re2::RE2::PartialMatch(it.key(),
+                                 *pattern_properties_pattern[index])) {
+        found_matching_pattern = true;
+        Validate(&it.value(), pattern_properties_schema[index], prop_path);
+        break;
+      }
+    }
+
+    if (found_matching_pattern || allow_any_additional_properties ||
+        (properties && properties->HasKey(it.key())))
       continue;
 
-    std::string prop_path = path.empty() ? it.key() : path + "." + it.key();
     if (!additional_properties_schema) {
       errors_.push_back(Error(prop_path, kUnexpectedProperty));
     } else {
@@ -707,7 +769,20 @@ void JSONSchemaValidator::ValidateString(const base::Value* instance,
     }
   }
 
-  CHECK(!schema->HasKey(schema::kPattern)) << "Pattern is not supported.";
+  std::string pattern;
+  if (schema->GetString(schema::kPattern, &pattern)) {
+    re2::RE2 compiled_regex(pattern);
+    if (!compiled_regex.ok()) {
+      LOG(WARNING) << "Regular expression /" << pattern
+                   << "/ is invalid: " << compiled_regex.error() << ".";
+      errors_.push_back(Error(
+          path,
+          FormatErrorMessage(kInvalidRegex, pattern, compiled_regex.error())));
+    } else if (!re2::RE2::PartialMatch(value, compiled_regex)) {
+      errors_.push_back(
+          Error(path, FormatErrorMessage(kStringPattern, pattern)));
+    }
+  }
 }
 
 void JSONSchemaValidator::ValidateNumber(const base::Value* instance,
diff --git a/components/json_schema/json_schema_validator.h b/components/json_schema/json_schema_validator.h
index 4e8acad..ad429ef 100644
--- a/components/json_schema/json_schema_validator.h
+++ b/components/json_schema/json_schema_validator.h
@@ -32,7 +32,6 @@ class Value;
 // - disallow
 // - union types (but replaced with 'choices')
 // - number.maxDecimal
-// - string.pattern
 //
 // The following properties are not applicable to the interface exposed by
 // this class:
@@ -52,6 +51,8 @@ class Value;
 // - by default an "object" typed schema does not allow additional properties.
 //   if present, "additionalProperties" is to be a schema against which all
 //   additional properties will be validated.
+// - regular expression supports all syntaxes that re2 accepts.
+//   See https://code.google.com/p/re2/wiki/Syntax for details.
 //==============================================================================
 class JSONSchemaValidator {
  public:
@@ -92,6 +93,7 @@ class JSONSchemaValidator {
   static const char kNumberMaximum[];
   static const char kInvalidType[];
   static const char kInvalidTypeIntegerNumber[];
+  static const char kInvalidRegex[];
 
   // Classifies a Value as one of the JSON schema primitive types.
   static std::string GetJSONSchemaType(const base::Value* value);
@@ -110,6 +112,10 @@ class JSONSchemaValidator {
   // and that DictionaryValue can be used to build a JSONSchemaValidator.
   // Returns the parsed DictionaryValue when |schema| validated, otherwise
   // returns NULL. In that case, |error| contains an error description.
+  // For performance reasons, currently IsValidSchema() won't check the
+  // correctness of regular expressions used in "pattern" and
+  // "patternProperties" and in Validate() invalid regular expression don't
+  // accept any strings.
   static scoped_ptr<base::DictionaryValue> IsValidSchema(
       const std::string& schema,
       std::string* error);
diff --git a/components/json_schema/json_schema_validator_unittest.cc b/components/json_schema/json_schema_validator_unittest.cc
index 73809de..aaa2555 100644
--- a/components/json_schema/json_schema_validator_unittest.cc
+++ b/components/json_schema/json_schema_validator_unittest.cc
@@ -9,9 +9,7 @@
 
 class JSONSchemaValidatorCPPTest : public JSONSchemaValidatorTestBase {
  public:
-  JSONSchemaValidatorCPPTest()
-      : JSONSchemaValidatorTestBase(JSONSchemaValidatorTestBase::CPP) {
-  }
+  JSONSchemaValidatorCPPTest() : JSONSchemaValidatorTestBase() {}
 
  protected:
   virtual void ExpectValid(const std::string& test_source,
@@ -134,6 +132,19 @@ TEST(JSONSchemaValidator, IsValidSchema) {
   EXPECT_TRUE(JSONSchemaValidator::IsValidSchema(
       "{"
       "  \"type\": \"object\","
+      "  \"patternProperties\": {"
+      "    \".\": { \"type\": \"any\" },"
+      "    \"foo\": { \"type\": \"any\" },"
+      "    \"^foo$\": { \"type\": \"any\" },"
+      "    \"foo+\": { \"type\": \"any\" },"
+      "    \"foo?\": { \"type\": \"any\" },"
+      "    \"fo{2,4}\": { \"type\": \"any\" },"
+      "    \"(left)|(right)\": { \"type\": \"any\" }"
+      "  }"
+      "}", &error)) << error;
+  EXPECT_TRUE(JSONSchemaValidator::IsValidSchema(
+      "{"
+      "  \"type\": \"object\","
       "  \"unknown attribute\": \"that should just be ignored\""
       "}",
       JSONSchemaValidator::OPTIONS_IGNORE_UNKNOWN_ATTRIBUTES,
diff --git a/components/json_schema/json_schema_validator_unittest_base.cc b/components/json_schema/json_schema_validator_unittest_base.cc
index 2e936a2..5c9f1a5 100644
--- a/components/json_schema/json_schema_validator_unittest_base.cc
+++ b/components/json_schema/json_schema_validator_unittest_base.cc
@@ -67,9 +67,7 @@ base::DictionaryValue* LoadDictionary(const std::string& filename) {
 }  // namespace
 
 
-JSONSchemaValidatorTestBase::JSONSchemaValidatorTestBase(
-    JSONSchemaValidatorTestBase::ValidatorType type)
-    : type_(type) {
+JSONSchemaValidatorTestBase::JSONSchemaValidatorTestBase() {
 }
 
 void JSONSchemaValidatorTestBase::RunTests() {
@@ -118,10 +116,6 @@ void JSONSchemaValidatorTestBase::TestComplex() {
 }
 
 void JSONSchemaValidatorTestBase::TestStringPattern() {
-  // Regex patterns not supported in CPP validator.
-  if (type_ == CPP)
-    return;
-
   scoped_ptr<base::DictionaryValue> schema(new base::DictionaryValue());
   schema->SetString(schema::kType, schema::kString);
   schema->SetString(schema::kPattern, "foo+");
@@ -224,8 +218,8 @@ void JSONSchemaValidatorTestBase::TestObject() {
   instance->SetBoolean("extra", true);
   ExpectNotValid(TEST_SOURCE, instance.get(), schema.get(), NULL,
                  "extra", JSONSchemaValidator::kUnexpectedProperty);
-
   instance->Remove("extra", NULL);
+
   instance->Remove("bar", NULL);
   ExpectNotValid(TEST_SOURCE, instance.get(), schema.get(), NULL, "bar",
                  JSONSchemaValidator::kObjectPropertyIsRequired);
@@ -236,12 +230,47 @@ void JSONSchemaValidatorTestBase::TestObject() {
                      JSONSchemaValidator::kInvalidType,
                      schema::kInteger,
                      schema::kString));
+  instance->SetInteger("bar", 42);
+
+  // Test "patternProperties".
+  instance->SetInteger("extra", 42);
+  ExpectNotValid(TEST_SOURCE, instance.get(), schema.get(), NULL,
+                 "extra", JSONSchemaValidator::kUnexpectedProperty);
+  schema->SetString("patternProperties.extra+.type",
+                    schema::kInteger);
+  ExpectValid(TEST_SOURCE, instance.get(), schema.get(), NULL);
+  instance->Remove("extra", NULL);
+  instance->SetInteger("extraaa", 42);
+  ExpectValid(TEST_SOURCE, instance.get(), schema.get(), NULL);
+  instance->Remove("extraaa", NULL);
+  instance->SetInteger("extr", 42);
+  ExpectNotValid(TEST_SOURCE, instance.get(), schema.get(), NULL,
+                 "extr", JSONSchemaValidator::kUnexpectedProperty);
+  instance->Remove("extr", NULL);
+  schema->Remove(schema::kPatternProperties, NULL);
+
+  // Test "patternProperties" and "properties" schemas are both checked if
+  // applicable.
+  schema->SetString("patternProperties.fo+.type", schema::kInteger);
+  ExpectNotValid(TEST_SOURCE, instance.get(), schema.get(), NULL, "foo",
+                 JSONSchemaValidator::FormatErrorMessage(
+                     JSONSchemaValidator::kInvalidType,
+                     schema::kInteger,
+                     schema::kString));
+  instance->SetInteger("foo", 123);
+  ExpectNotValid(TEST_SOURCE, instance.get(), schema.get(), NULL, "foo",
+                 JSONSchemaValidator::FormatErrorMessage(
+                     JSONSchemaValidator::kInvalidType,
+                     schema::kString,
+                     schema::kInteger));
+  instance->SetString("foo", "foo");
+  schema->Remove(schema::kPatternProperties, NULL);
 
+  // Test additional properties.
   base::DictionaryValue* additional_properties = new base::DictionaryValue();
   additional_properties->SetString(schema::kType, schema::kAny);
   schema->Set(schema::kAdditionalProperties, additional_properties);
 
-  instance->SetInteger("bar", 42);
   instance->SetBoolean("extra", true);
   ExpectValid(TEST_SOURCE, instance.get(), schema.get(), NULL);
 
@@ -258,6 +287,7 @@ void JSONSchemaValidatorTestBase::TestObject() {
                      JSONSchemaValidator::kInvalidType,
                      schema::kBoolean,
                      schema::kString));
+  instance->Remove("extra", NULL);
 
   base::DictionaryValue* properties = NULL;
   base::DictionaryValue* bar_property = NULL;
@@ -265,7 +295,6 @@ void JSONSchemaValidatorTestBase::TestObject() {
   ASSERT_TRUE(properties->GetDictionary("bar", &bar_property));
 
   bar_property->SetBoolean(schema::kOptional, true);
-  instance->Remove("extra", NULL);
   ExpectValid(TEST_SOURCE, instance.get(), schema.get(), NULL);
   instance->Remove("bar", NULL);
   ExpectValid(TEST_SOURCE, instance.get(), schema.get(), NULL);
@@ -281,6 +310,18 @@ void JSONSchemaValidatorTestBase::TestObject() {
                      JSONSchemaValidator::kInvalidType,
                      schema::kInteger,
                      schema::kString));
+
+  // Verify that JSON parser handles dot in "patternProperties" well.
+  schema.reset(LoadDictionary("pattern_properties_dot.json"));
+  ASSERT_TRUE(schema->GetDictionary(schema::kPatternProperties, &properties));
+  ASSERT_TRUE(properties->HasKey("^.$"));
+
+  instance.reset(new base::DictionaryValue());
+  instance->SetString("a", "whatever");
+  ExpectValid(TEST_SOURCE, instance.get(), schema.get(), NULL);
+  instance->SetString("foo", "bar");
+  ExpectNotValid(TEST_SOURCE, instance.get(), schema.get(), NULL,
+                 "foo", JSONSchemaValidator::kUnexpectedProperty);
 }
 
 void JSONSchemaValidatorTestBase::TestTypeReference() {
diff --git a/components/json_schema/json_schema_validator_unittest_base.h b/components/json_schema/json_schema_validator_unittest_base.h
index 7b4854e..4edb994 100644
--- a/components/json_schema/json_schema_validator_unittest_base.h
+++ b/components/json_schema/json_schema_validator_unittest_base.h
@@ -20,12 +20,7 @@ class Value;
 // JSONSchemaValidatorJSTest that inherits from this.
 class JSONSchemaValidatorTestBase : public testing::Test {
  public:
-  enum ValidatorType {
-    CPP = 1,
-    JS = 2
-  };
-
-  explicit JSONSchemaValidatorTestBase(ValidatorType type);
+  JSONSchemaValidatorTestBase();
 
   void RunTests();
 
@@ -56,8 +51,6 @@ class JSONSchemaValidatorTestBase : public testing::Test {
   void TestNumber();
   void TestTypeClassifier();
   void TestTypes();
-
-  ValidatorType type_;
 };
 
 #endif  // COMPONENTS_JSON_SCHEMA_JSON_SCHEMA_VALIDATOR_UNITTEST_BASE_H_