Add regular expression support in json_schema component

components/json_schema/json_schema_validator.cc

Index: components/json_schema/json_schema_validator.cc
diff --git a/components/json_schema/json_schema_validator.cc b/components/json_schema/json_schema_validator.cc
index 18558d0e111213bd789ac96633b8bc43afaaa53f..698450672aedb887b5b8139df29f11f20892ea7d 100644
--- a/components/json_schema/json_schema_validator.cc
+++ b/components/json_schema/json_schema_validator.cc
@@ -7,13 +7,16 @@
 #include <algorithm>
 #include <cfloat>
 #include <cmath>
+#include <vector>
 
 #include "base/json/json_reader.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 +89,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      },
   };
@@ -183,6 +188,14 @@ bool IsValidSchema(const base::DictionaryValue* dict,
       }
     }
 
+    if (it.key() == schema::kPattern) {
+      it.value().GetAsString(&string_value);
+      if (!re2::RE2(string_value).ok()) {

[not at google - send to devlin, 2014/03/11 14:53:39]

How often does Validate get called? If it's a lot it might be valuable to cache
the compiled expressions since compilation, I presume, is expensive. But the
memory tradeoff (whatever that may be) may not be worth it.

[binjin, 2014/03/11 16:27:36]

Yes, regular expression compiling is not very cheap in re2 as far as I know.

IsValidSchema() is a recursive function, but for each occurrence of "pattern"
and "patternProperties" regular expression compilation will only be called once.
This is a stand alone library, and typical usage is calling IsValidSchema() and
then build a JSONSchemaValidator with it. I think it's reasonable to call
IsValidSchema() only once.

Compiled regular expression can't be passed as result in a simple way. It
requires changes to IsValidSchema(), JSONSchemaValidator() and Validate(). On
the other hand, caching will introduce memory overhead and will potential hurt
the thread safety.

Another option is not to check the correctness of regular expression in
IsValidSchema() and assume invalid regular expression won't accept any string
Later in JsonSchemaValidator::Validate(). It's not a ugly approach but will
works well in practical.

What do you think?

[not at google - send to devlin, 2014/03/11 18:37:16]

Good point re uncachability of this stuff. Ok. Your last comment makes sense.

+        *error = "Invalid regular expression in pattern attribute";

[not at google - send to devlin, 2014/03/11 14:53:39]

Could you include the RE2 error message here?

https://code.google.com/p/chromium/codesearch#chromium/src/third_party/re2/re...

[binjin, 2014/03/11 16:27:36]

Done.

+        return false;
+      }
+    }
+
     // Validate the "properties" attribute. Each entry maps a key to a schema.
     if (it.key() == schema::kProperties) {
       it.value().GetAsDictionary(&dictionary_value);
@@ -199,6 +212,27 @@ bool IsValidSchema(const base::DictionaryValue* dict,
       }
     }
 
+    // Validate the "patternProperties" attribute. Each entry maps a valid
+    // regular expression to a schema.
+    if (it.key() == schema::kPatternProperties) {
+      it.value().GetAsDictionary(&dictionary_value);
+      for (base::DictionaryValue::Iterator it(*dictionary_value);

[not at google - send to devlin, 2014/03/11 14:53:39]

huh, how does the |it| declaration here not kill the outer |it| variable... I
didn't know C++ let you do that.

[Joao da Silva, 2014/03/11 16:20:13]

IIUC this is the same as shadowing an outer variable, and some compilers issue a
warning about this.

I think it's better to rename the iterator to avoid any confusion.

[binjin, 2014/03/11 16:27:36]

My bad, I just copy-and-modified code from above block for "properties".

Done(for this and above).

+           !it.IsAtEnd(); it.Advance()) {
+        if (!re2::RE2(it.key()).ok()) {
+          *error = "Invalid regular expression in patternProperties attribute";

[not at google - send to devlin, 2014/03/11 14:53:39]

ditto error message

[binjin, 2014/03/11 16:27:36]

Done.

+          return false;
+        }
+        if (!it.value().GetAsDictionary(&dictionary_value)) {
+          *error = "Invalid value for patternProperties attribute";

[not at google - send to devlin, 2014/03/11 14:53:39]

How about "patternProperties must be a dictionary" or something?

[binjin, 2014/03/11 16:27:36]

Done(for this and above).

+          return false;
+        }
+        if (!IsValidSchema(dictionary_value, options, error)) {
+          DCHECK(!error->empty());
+          return false;
+        }
+      }
+    }
+
     // Validate "additionalProperties" attribute, which is a schema.
     if (it.key() == schema::kAdditionalProperties) {
       it.value().GetAsDictionary(&dictionary_value);
@@ -574,17 +608,49 @@ void JSONSchemaValidator::ValidateObject(const base::DictionaryValue* instance,
     }
   }
 
+  // Allowing any additional items will ignore pattern properties as well.
   const base::DictionaryValue* additional_properties_schema = NULL;
   if (SchemaAllowsAnyAdditionalItems(schema, &additional_properties_schema))
     return;
 
-  // Validate additional properties.
+  const base::DictionaryValue* pattern_properties = NULL;
+  ScopedVector<re2::RE2> pattern_properties_pattern;
+  std::vector<const base::DictionaryValue*> pattern_properties_schema;
+
+  schema->GetDictionary(schema::kPatternProperties, &pattern_properties);
+  if (pattern_properties) {

[not at google - send to devlin, 2014/03/11 14:53:39]

usual style I see would be to have the schema->GetDictionary as part of the
conditional here.

[binjin, 2014/03/11 16:27:36]

Done(for this and above).

+    for (base::DictionaryValue::Iterator it(*pattern_properties); !it.IsAtEnd();
+         it.Advance()) {
+      re2::RE2* prop_pattern = new re2::RE2(it.key());
+      CHECK(prop_pattern->ok());

[not at google - send to devlin, 2014/03/11 14:53:39]

See comment above about caching these. In fact could you basically cache all of
this block in a sensible way? It seems wasteful (and a bit odd to read) to be
re-parsing it all.

Perhaps at least share code with the parsing stage, e.g. a function which
populates a couple of vectors and returns an error.

+      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()))
       continue;
 
     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++) {

[not at google - send to devlin, 2014/03/11 14:53:39]

++index

[binjin, 2014/03/11 16:27:36]

Done.

+      if (re2::RE2::PartialMatch(it.key(),
+                                 *pattern_properties_pattern[index])) {
+        found_matching_pattern = true;
+        Validate(&it.value(), pattern_properties_schema[index], prop_path);
+        break;
+      }
+    }

[Joao da Silva, 2014/03/11 16:20:13]

The order of these checks is not correct. See
http://tools.ietf.org/html/draft-zyp-json-schema-03#section-5.3:

"If the pattern matches the name of a property on the instance object, the value
of the instance's property MUST be valid against the pattern name's schema
value."

And for additionalProperties:

"This attribute defines a schema for all properties that are not explicitly
defined in an object type definition."

So from my understanding the right validation is:

- for each pattern that matches a property key, the property's value must match
the schema from that pattern;
- then if the key matches a known property, it must match its schema;
- else if the key didn't match any patterns, then it must match the
additionalProperties (if they exist)

In pseudo code (this is just to make this more concrete, other implementations
are possibly better):

  ValidateObject(instance, schema) {
    properties = schema->GetDictionary(kProperties);
    additionalProperties = schema->GetDictionary(additionalProperties);
    patternProperties = schema->GetDictionary(patternProperties);

    vector<RE2*> patterns;
    vector<DictionaryValue*> pattern_schemas;
    for (pattern, value in patternProperties) {
      patterns.push_back(re2::RE2(pattern));
      pattern_schemas.push_back(value);
    }

    // Validation starts here.
    for (key, value in instance) {
      bool defined_by_pattern = false;
      // Validate against any matching patterns.
      for (i from 0 to patterns.size()) {
        if (re2::RE2::PartialMatch(patterns[i], key)) {
          defined_by_pattern = true;
          Validate(value, pattern_schemas[i]);
        }
      }

      property_schema = properties->GetDictionary(key);
      if (property) {
        Validate(value, property_schema);
      } else if (!defined_by_schema &&
!SchemaAllowsAnyAdditionalProperties(schema)) {
        if (!additionalProperties) {
          errors_.push_back(kUnexpectedProperty);
        } else {
          Validate(value, additionalProperties);
        }
      }
    }
  }

Can you also add tests that cover combinations of these cases?

[binjin, 2014/03/11 17:20:04]

I just read the specification, and from what I understood, if a property in
instance match against both "properties" and "patternProperties", it must
conform to both schema.

So modification is still needed but it's much easier I think.

+
+    if (found_matching_pattern)
+      continue;
+
     if (!additional_properties_schema) {
       errors_.push_back(Error(prop_path, kUnexpectedProperty));
     } else {
@@ -707,7 +773,11 @@ 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::PartialMatch(value, pattern)) {
+    errors_.push_back(Error(path, FormatErrorMessage(kStringPattern, pattern)));
+  }
 }
 
 void JSONSchemaValidator::ValidateNumber(const base::Value* instance,