Add regular expression support in json_schema component

components/json_schema/json_schema_validator.cc

 // Copyright 2013 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 "components/json_schema/json_schema_validator.h"
 
 #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;
 
 namespace {
 
 double GetNumberValue(const base::Value* value) {
   double result = 0;
   CHECK(value->GetAsDouble(&result))
       << "Unexpected value type: " << value->GetType();
   return result;
@@ skipping 52 matching lines @@
     { schema::kDescription,             base::Value::TYPE_STRING      },
     { schema::kEnum,                    base::Value::TYPE_LIST        },
     { schema::kId,                      base::Value::TYPE_STRING      },
     { schema::kMaxItems,                base::Value::TYPE_INTEGER     },
     { schema::kMaxLength,               base::Value::TYPE_INTEGER     },
     { schema::kMaximum,                 base::Value::TYPE_DOUBLE      },
     { schema::kMinItems,                base::Value::TYPE_INTEGER     },
     { 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      },
   };
 
   bool has_type_or_ref = false;
   const base::ListValue* list_value = NULL;
   const base::DictionaryValue* dictionary_value = NULL;
   std::string string_value;
 
   for (base::DictionaryValue::Iterator it(*dict); !it.IsAtEnd(); it.Advance()) {
@@ skipping 77 matching lines @@
     if (it.value().IsType(base::Value::TYPE_INTEGER)) {
       int integer_value;
       it.value().GetAsInteger(&integer_value);
       if (integer_value < 0) {
         *error = base::StringPrintf("Value of %s must be >= 0, got %d",
                                     it.key().c_str(), integer_value);
         return false;
       }
     }
 
+    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);
       for (base::DictionaryValue::Iterator it(*dictionary_value);
            !it.IsAtEnd(); it.Advance()) {
         if (!it.value().GetAsDictionary(&dictionary_value)) {
           *error = "Invalid value for properties attribute";
           return false;
         }
         if (!IsValidSchema(dictionary_value, options, error)) {
           DCHECK(!error->empty());
           return false;
         }
       }
     }
 
+    // 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);
       if (!IsValidSchema(dictionary_value, options, error)) {
         DCHECK(!error->empty());
         return false;
       }
     }
 
     // Validate the values contained in an "enum" attribute.
@@ skipping 355 matching lines @@
         // 'true'.
         bool is_optional = false;
         prop_schema->GetBoolean(schema::kOptional, &is_optional);
         if (!is_optional) {
           errors_.push_back(Error(prop_path, kObjectPropertyIsRequired));
         }
       }
     }
   }
 
+  // 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 {
       Validate(&it.value(), additional_properties_schema, prop_path);
     }
   }
 }
 
 void JSONSchemaValidator::ValidateArray(const base::ListValue* instance,
                                         const base::DictionaryValue* schema,
@@ skipping 102 matching lines @@
 
   int max_length = 0;
   if (schema->GetInteger(schema::kMaxLength, &max_length)) {
     CHECK(max_length >= 0);
     if (value.size() > static_cast<size_t>(max_length)) {
       errors_.push_back(Error(path, FormatErrorMessage(
           kStringMaxLength, base::IntToString(max_length))));
     }
   }
 
-  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,
                                          const base::DictionaryValue* schema,
                                          const std::string& path) {
   double value = GetNumberValue(instance);
 
   // TODO(aa): It would be good to test that the double is not infinity or nan,
   // but isnan and isinf aren't defined on Windows.
 
@@ skipping 40 matching lines @@
 
   if (*additional_properties_schema) {
     std::string additional_properties_type(schema::kAny);
     CHECK((*additional_properties_schema)->GetString(
         schema::kType, &additional_properties_type));
     return additional_properties_type == schema::kAny;
   } else {
     return default_allow_additional_properties_;
   }
 }