Add JSON Schema Validator
authorAndrey Goder <agoder@fb.com>
Sat, 7 Mar 2015 00:06:18 +0000 (16:06 -0800)
committerAndre Azevedo <aap@fb.com>
Wed, 18 Mar 2015 02:47:03 +0000 (19:47 -0700)
Summary:
This is a validator for  JSON schema (http://json-schema.org/) that works on
folly::dynamic. Apparently there are no good open source ones for C++,
especially not if you want to use folly::dynamic. I am going to use this to
validate JSON configs.

It supports basically everything from the standard, except for fetching schemas
via http, and using id refs. It supports enough to check schemas against the
metaschema.

Currently you can define a schema that will crash on validation, if it's
infinitely self-recursive. See the unit test case that reproduces this.
Fixing this seems hard though, so I didn't bother. It would also probably
be slower for normal usage.

Test Plan: unit test

Reviewed By: lesha@fb.com

Subscribers: trunkagent, folly-diffs@, yfeldblum

FB internal diff: D1847657

Signature: t1:1847657:1425605163:635dc523aeda1b588c3634d0dc1a48d50a53db79

folly/Makefile.am
folly/experimental/JSONSchema.cpp [new file with mode: 0644]
folly/experimental/JSONSchema.h [new file with mode: 0644]
folly/experimental/JSONSchemaTester.cpp [new file with mode: 0644]
folly/experimental/test/JSONSchemaTest.cpp [new file with mode: 0644]

index b6abbc6..c57494c 100644 (file)
@@ -78,6 +78,7 @@ nobase_follyinclude_HEADERS = \
        experimental/Singleton-inl.h \
        experimental/TestUtil.h \
        experimental/Select64.h \
+       experimental/JSONSchema.h \
        FBString.h \
        FBVector.h \
        File.h \
@@ -343,6 +344,7 @@ libfolly_la_SOURCES = \
        experimental/Singleton.cpp \
        experimental/TestUtil.cpp \
        experimental/Select64.cpp \
+       experimental/JSONSchema.cpp \
        wangle/acceptor/Acceptor.cpp \
        wangle/acceptor/ConnectionManager.cpp \
        wangle/acceptor/LoadShedConfiguration.cpp \
diff --git a/folly/experimental/JSONSchema.cpp b/folly/experimental/JSONSchema.cpp
new file mode 100644 (file)
index 0000000..7e0e499
--- /dev/null
@@ -0,0 +1,1027 @@
+/*
+ * Copyright 2015 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <folly/experimental/JSONSchema.h>
+
+#include <boost/algorithm/string/replace.hpp>
+#include <boost/regex.hpp>
+#include <folly/Conv.h>
+#include <folly/Memory.h>
+#include <folly/Optional.h>
+#include <folly/String.h>
+#include <folly/experimental/Singleton.h>
+#include <folly/json.h>
+
+namespace folly {
+namespace jsonschema {
+
+namespace {
+
+/**
+ * We throw this exception when schema validation fails.
+ */
+struct SchemaError : std::runtime_error {
+
+  SchemaError(SchemaError&&) = default;
+  SchemaError(const SchemaError&) = default;
+
+  SchemaError(folly::StringPiece expected, const dynamic& value)
+      : std::runtime_error(to<std::string>(
+            "Expected to get ", expected, " for value ", toJson(value))) {}
+  SchemaError(folly::StringPiece expected,
+              const dynamic& schema,
+              const dynamic& value)
+      : std::runtime_error(to<std::string>("Expected to get ",
+                                           expected,
+                                           toJson(schema),
+                                           " for value ",
+                                           toJson(value))) {}
+};
+
+template <class... Args>
+Optional<SchemaError> makeError(Args&&... args) {
+  return Optional<SchemaError>(SchemaError(std::forward<Args>(args)...));
+}
+
+struct ValidationContext;
+
+struct IValidator {
+  virtual ~IValidator() {}
+
+ private:
+  friend class ValidationContext;
+
+  virtual Optional<SchemaError> validate(ValidationContext&,
+                                         const dynamic& value) const = 0;
+};
+
+/**
+ * This is a 'context' used only when executing the validators to validate some
+ * json. It keeps track of which validators have been executed on which json so
+ * we can detect infinite recursion.
+ */
+struct ValidationContext {
+  Optional<SchemaError> validate(IValidator* validator, const dynamic& value) {
+    auto ret = seen.insert(std::make_pair(validator, &value));
+    if (!ret.second) {
+      throw std::runtime_error("Infinite recursion detected");
+    }
+    return validator->validate(*this, value);
+  }
+
+ private:
+  std::unordered_set<std::pair<const IValidator*, const dynamic*>> seen;
+};
+
+/**
+ * This is a 'context' used only when building the schema validators from a
+ * piece of json. It stores the original schema and the set of refs, so that we
+ * can have parts of the schema refer to other parts.
+ */
+struct SchemaValidatorContext final {
+  explicit SchemaValidatorContext(const dynamic& s) : schema(s) {}
+
+  const dynamic& schema;
+  std::unordered_map<fbstring, IValidator*> refs;
+};
+
+/**
+ * Root validator for a schema.
+ */
+struct SchemaValidator final : IValidator, public Validator {
+  SchemaValidator() {}
+  void loadSchema(SchemaValidatorContext& context, const dynamic& schema);
+
+  Optional<SchemaError> validate(ValidationContext&,
+                                 const dynamic& value) const override;
+
+  // Validator interface
+  void validate(const dynamic& value) const override;
+  exception_wrapper try_validate(const dynamic& value) const noexcept override;
+
+  static std::unique_ptr<SchemaValidator> make(SchemaValidatorContext& context,
+                                               const dynamic& schema) {
+    // We break apart the constructor and actually loading the schema so that
+    // we can handle the case where a schema refers to itself, e.g. via
+    // "$ref": "#".
+    auto v = make_unique<SchemaValidator>();
+    v->loadSchema(context, schema);
+    return v;
+  }
+
+ private:
+  std::vector<std::unique_ptr<IValidator>> validators_;
+};
+
+struct MultipleOfValidator final : IValidator {
+  explicit MultipleOfValidator(dynamic schema) : schema_(std::move(schema)) {}
+  Optional<SchemaError> validate(ValidationContext&,
+                                 const dynamic& value) const override {
+    if (!schema_.isNumber() || !value.isNumber()) {
+      return none;
+    }
+    if (schema_.isDouble() || value.isDouble()) {
+      const auto rem = std::remainder(value.asDouble(), schema_.asDouble());
+      if (std::abs(rem) > std::numeric_limits<double>::epsilon()) {
+        return makeError("a multiple of ", schema_, value);
+      }
+    } else { // both ints
+      if ((value.getInt() % schema_.getInt()) != 0) {
+        return makeError("a multiple of ", schema_, value);
+      }
+    }
+    return none;
+  }
+  dynamic schema_;
+};
+
+struct ComparisonValidator final : IValidator {
+  enum class Type { MIN, MAX };
+  ComparisonValidator(dynamic schema, const dynamic* exclusive, Type type)
+      : schema_(std::move(schema)), exclusive_(false), type_(type) {
+    if (exclusive && exclusive->isBool()) {
+      exclusive_ = exclusive->getBool();
+    }
+  }
+
+  template <typename Numeric>
+  Optional<SchemaError> validateHelper(const dynamic& value,
+                                       Numeric s,
+                                       Numeric v) const {
+    if (type_ == Type::MIN) {
+      if (exclusive_) {
+        if (v <= s) {
+          return makeError("greater than", schema_, value);
+        }
+      } else {
+        if (v < s) {
+          return makeError("greater than or equal to", schema_, value);
+        }
+      }
+    } else if (type_ == Type::MAX) {
+      if (exclusive_) {
+        if (v >= s) {
+          return makeError("less than", schema_, value);
+        }
+      } else {
+        if (v > s) {
+          return makeError("less than or equal to", schema_, value);
+        }
+      }
+    }
+    return none;
+  }
+
+  Optional<SchemaError> validate(ValidationContext&,
+                                 const dynamic& value) const override {
+    if (!schema_.isNumber() || !value.isNumber()) {
+      return none;
+    }
+    if (schema_.isDouble() || value.isDouble()) {
+      return validateHelper(value, schema_.asDouble(), value.asDouble());
+    } else { // both ints
+      return validateHelper(value, schema_.asInt(), value.asInt());
+    }
+  }
+
+  dynamic schema_;
+  bool exclusive_;
+  Type type_;
+};
+
+template <class Comparison>
+struct SizeValidator final : IValidator {
+  explicit SizeValidator(const dynamic& schema, dynamic::Type type)
+      : length_(-1), type_(type) {
+    if (schema.isInt()) {
+      length_ = schema.getInt();
+    }
+  }
+
+  Optional<SchemaError> validate(ValidationContext&,
+                                 const dynamic& value) const override {
+    if (length_ < 0) {
+      return none;
+    }
+    if (value.type() != type_) {
+      return none;
+    }
+    if (!Comparison()(length_, value.size())) {
+      return makeError("different length string/array/object", value);
+    }
+    return none;
+  }
+  int64_t length_;
+  dynamic::Type type_;
+};
+
+struct StringPatternValidator final : IValidator {
+  explicit StringPatternValidator(const dynamic& schema) {
+    if (schema.isString()) {
+      regex_ = boost::regex(schema.getString().toStdString());
+    }
+  }
+
+  Optional<SchemaError> validate(ValidationContext&,
+                                 const dynamic& value) const override {
+    if (!value.isString() || regex_.empty()) {
+      return none;
+    }
+    if (!boost::regex_search(value.getString().toStdString(), regex_)) {
+      return makeError("string matching regex", value);
+    }
+    return none;
+  }
+  boost::regex regex_;
+};
+
+struct ArrayUniqueValidator final : IValidator {
+  explicit ArrayUniqueValidator(const dynamic& schema) : unique_(false) {
+    if (schema.isBool()) {
+      unique_ = schema.getBool();
+    }
+  }
+
+  Optional<SchemaError> validate(ValidationContext&,
+                                 const dynamic& value) const override {
+    if (!unique_ || !value.isArray()) {
+      return none;
+    }
+    for (const auto& i : value) {
+      for (const auto& j : value) {
+        if (&i != &j && i == j) {
+          return makeError("unique items in array", value);
+        }
+      }
+    }
+    return none;
+  }
+  bool unique_;
+};
+
+struct ArrayItemsValidator final : IValidator {
+  ArrayItemsValidator(SchemaValidatorContext& context,
+                      const dynamic* items,
+                      const dynamic* additionalItems)
+      : allowAdditionalItems_(true) {
+    if (items && items->isObject()) {
+      itemsValidator_ = SchemaValidator::make(context, *items);
+      return; // Additional items is ignored
+    } else if (items && items->isArray()) {
+      for (const auto& item : *items) {
+        itemsValidators_.emplace_back(SchemaValidator::make(context, item));
+      }
+    } else {
+      // If items isn't present or is invalid, it defaults to an empty schema.
+      itemsValidator_ = SchemaValidator::make(context, dynamic::object);
+    }
+    if (additionalItems) {
+      if (additionalItems->isBool()) {
+        allowAdditionalItems_ = additionalItems->getBool();
+      } else if (additionalItems->isObject()) {
+        additionalItemsValidator_ =
+            SchemaValidator::make(context, *additionalItems);
+      }
+    }
+  }
+
+  Optional<SchemaError> validate(ValidationContext& vc,
+                                 const dynamic& value) const override {
+    if (!value.isArray()) {
+      return none;
+    }
+    if (itemsValidator_) {
+      for (const auto& v : value) {
+        if (auto se = vc.validate(itemsValidator_.get(), v)) {
+          return se;
+        }
+      }
+      return none;
+    }
+    size_t pos = 0;
+    for (; pos < value.size() && pos < itemsValidators_.size(); ++pos) {
+      if (auto se = vc.validate(itemsValidators_[pos].get(), value[pos])) {
+        return se;
+      }
+    }
+    if (!allowAdditionalItems_ && pos < value.size()) {
+      return makeError("no more additional items", value);
+    }
+    if (additionalItemsValidator_) {
+      for (; pos < value.size(); ++pos) {
+        if (auto se =
+                vc.validate(additionalItemsValidator_.get(), value[pos])) {
+          return se;
+        }
+      }
+    }
+    return none;
+  }
+  std::unique_ptr<IValidator> itemsValidator_;
+  std::vector<std::unique_ptr<IValidator>> itemsValidators_;
+  std::unique_ptr<IValidator> additionalItemsValidator_;
+  bool allowAdditionalItems_;
+};
+
+struct RequiredValidator final : IValidator {
+  explicit RequiredValidator(const dynamic& schema) {
+    if (schema.isArray()) {
+      for (const auto& item : schema) {
+        if (item.isString()) {
+          properties_.emplace_back(item.getString());
+        }
+      }
+    }
+  }
+
+  Optional<SchemaError> validate(ValidationContext&,
+                                 const dynamic& value) const override {
+    if (value.isObject()) {
+      for (const auto& prop : properties_) {
+        auto* p = value.get_ptr(prop);
+        if (!value.get_ptr(prop)) {
+          return makeError("to have property", prop, value);
+        }
+      }
+    }
+    return none;
+  }
+
+ private:
+  std::vector<fbstring> properties_;
+};
+
+struct PropertiesValidator final : IValidator {
+  PropertiesValidator(SchemaValidatorContext& context,
+                      const dynamic* properties,
+                      const dynamic* patternProperties,
+                      const dynamic* additionalProperties)
+      : allowAdditionalProperties_(true) {
+    if (properties && properties->isObject()) {
+      for (const auto& pair : properties->items()) {
+        if (pair.first.isString()) {
+          propertyValidators_[pair.first.getString()] =
+              SchemaValidator::make(context, pair.second);
+        }
+      }
+    }
+    if (patternProperties && patternProperties->isObject()) {
+      for (const auto& pair : patternProperties->items()) {
+        if (pair.first.isString()) {
+          patternPropertyValidators_.emplace_back(
+              make_pair(boost::regex(pair.first.getString().toStdString()),
+                        SchemaValidator::make(context, pair.second)));
+        }
+      }
+    }
+    if (additionalProperties) {
+      if (additionalProperties->isBool()) {
+        allowAdditionalProperties_ = additionalProperties->getBool();
+      } else if (additionalProperties->isObject()) {
+        additionalPropertyValidator_ =
+            SchemaValidator::make(context, *additionalProperties);
+      }
+    }
+  }
+
+  Optional<SchemaError> validate(ValidationContext& vc,
+                                 const dynamic& value) const override {
+    if (!value.isObject()) {
+      return none;
+    }
+    for (const auto& pair : value.items()) {
+      if (!pair.first.isString()) {
+        continue;
+      }
+      const fbstring& key = pair.first.getString();
+      auto it = propertyValidators_.find(key);
+      bool matched = false;
+      if (it != propertyValidators_.end()) {
+        if (auto se = vc.validate(it->second.get(), pair.second)) {
+          return se;
+        }
+        matched = true;
+      }
+
+      const std::string& strkey = key.toStdString();
+      for (const auto& ppv : patternPropertyValidators_) {
+        if (boost::regex_search(strkey, ppv.first)) {
+          if (auto se = vc.validate(ppv.second.get(), pair.second)) {
+            return se;
+          }
+          matched = true;
+        }
+      }
+      if (matched) {
+        continue;
+      }
+      if (!allowAdditionalProperties_) {
+        return makeError("no more additional properties", value);
+      }
+      if (additionalPropertyValidator_) {
+        if (auto se =
+                vc.validate(additionalPropertyValidator_.get(), pair.second)) {
+          return se;
+        }
+      }
+    }
+    return none;
+  }
+
+  std::unordered_map<fbstring, std::unique_ptr<IValidator>> propertyValidators_;
+  std::vector<std::pair<boost::regex, std::unique_ptr<IValidator>>>
+      patternPropertyValidators_;
+  std::unique_ptr<IValidator> additionalPropertyValidator_;
+  bool allowAdditionalProperties_;
+};
+
+struct DependencyValidator final : IValidator {
+  DependencyValidator(SchemaValidatorContext& context, const dynamic& schema) {
+    if (!schema.isObject()) {
+      return;
+    }
+    for (const auto& pair : schema.items()) {
+      if (!pair.first.isString()) {
+        continue;
+      }
+      if (pair.second.isArray()) {
+        auto p = make_pair(pair.first.getString(), std::vector<fbstring>());
+        for (const auto& item : pair.second) {
+          if (item.isString()) {
+            p.second.push_back(item.getString());
+          }
+        }
+        propertyDep_.emplace_back(std::move(p));
+      }
+      if (pair.second.isObject()) {
+        schemaDep_.emplace_back(
+            make_pair(pair.first.getString(),
+                      SchemaValidator::make(context, pair.second)));
+      }
+    }
+  }
+
+  Optional<SchemaError> validate(ValidationContext& vc,
+                                 const dynamic& value) const override {
+    if (!value.isObject()) {
+      return none;
+    }
+    for (const auto& pair : propertyDep_) {
+      if (value.count(pair.first)) {
+        for (const auto& prop : pair.second) {
+          if (!value.count(prop)) {
+            return makeError("property", prop, value);
+          }
+        }
+      }
+    }
+    for (const auto& pair : schemaDep_) {
+      if (value.count(pair.first)) {
+        if (auto se = vc.validate(pair.second.get(), value)) {
+          return se;
+        }
+      }
+    }
+    return none;
+  }
+
+  std::vector<std::pair<fbstring, std::vector<fbstring>>> propertyDep_;
+  std::vector<std::pair<fbstring, std::unique_ptr<IValidator>>> schemaDep_;
+};
+
+struct EnumValidator final : IValidator {
+  explicit EnumValidator(dynamic schema) : schema_(std::move(schema)) {}
+
+  Optional<SchemaError> validate(ValidationContext&,
+                                 const dynamic& value) const override {
+    if (!schema_.isArray()) {
+      return none;
+    }
+    for (const auto& item : schema_) {
+      if (value == item) {
+        return none;
+      }
+    }
+    return makeError("one of enum values: ", schema_, value);
+  }
+  dynamic schema_;
+};
+
+struct TypeValidator final : IValidator {
+  explicit TypeValidator(const dynamic& schema) {
+    if (schema.isString()) {
+      addType(schema.stringPiece());
+    } else if (schema.isArray()) {
+      for (const auto& item : schema) {
+        if (item.isString()) {
+          addType(item.stringPiece());
+        }
+      }
+    }
+  }
+
+  Optional<SchemaError> validate(ValidationContext&,
+                                 const dynamic& value) const override {
+    auto it =
+        std::find(allowedTypes_.begin(), allowedTypes_.end(), value.type());
+    if (it == allowedTypes_.end()) {
+      return makeError("a value of type ", typeStr_, value);
+    }
+    return none;
+  }
+
+ private:
+  std::vector<dynamic::Type> allowedTypes_;
+  std::string typeStr_; // for errors
+
+  void addType(StringPiece value) {
+    if (value == "array") {
+      allowedTypes_.push_back(dynamic::Type::ARRAY);
+    } else if (value == "boolean") {
+      allowedTypes_.push_back(dynamic::Type::BOOL);
+    } else if (value == "integer") {
+      allowedTypes_.push_back(dynamic::Type::INT64);
+    } else if (value == "number") {
+      allowedTypes_.push_back(dynamic::Type::INT64);
+      allowedTypes_.push_back(dynamic::Type::DOUBLE);
+    } else if (value == "null") {
+      allowedTypes_.push_back(dynamic::Type::NULLT);
+    } else if (value == "object") {
+      allowedTypes_.push_back(dynamic::Type::OBJECT);
+    } else if (value == "string") {
+      allowedTypes_.push_back(dynamic::Type::STRING);
+    } else {
+      return;
+    }
+    if (!typeStr_.empty()) {
+      typeStr_ += ", ";
+    }
+    typeStr_ += value.str();
+  }
+};
+
+struct AllOfValidator final : IValidator {
+  AllOfValidator(SchemaValidatorContext& context, const dynamic& schema) {
+    if (schema.isArray()) {
+      for (const auto& item : schema) {
+        validators_.emplace_back(SchemaValidator::make(context, item));
+      }
+    }
+  }
+
+  Optional<SchemaError> validate(ValidationContext& vc,
+                                 const dynamic& value) const override {
+    for (const auto& val : validators_) {
+      if (auto se = vc.validate(val.get(), value)) {
+        return se;
+      }
+    }
+    return none;
+  }
+
+  std::vector<std::unique_ptr<IValidator>> validators_;
+};
+
+struct AnyOfValidator final : IValidator {
+  enum class Type { EXACTLY_ONE, ONE_OR_MORE };
+
+  AnyOfValidator(SchemaValidatorContext& context,
+                 const dynamic& schema,
+                 Type type)
+      : type_(type) {
+    if (schema.isArray()) {
+      for (const auto& item : schema) {
+        validators_.emplace_back(SchemaValidator::make(context, item));
+      }
+    }
+  }
+
+  Optional<SchemaError> validate(ValidationContext& vc,
+                                 const dynamic& value) const override {
+    std::vector<SchemaError> errors;
+    for (const auto& val : validators_) {
+      if (auto se = vc.validate(val.get(), value)) {
+        errors.emplace_back(*se);
+      }
+    }
+    const int success = validators_.size() - errors.size();
+    if (success == 0) {
+      return makeError("at least one valid schema", value);
+    } else if (success > 1 && type_ == Type::EXACTLY_ONE) {
+      return makeError("exactly one valid schema", value);
+    }
+    return none;
+  }
+
+  Type type_;
+  std::vector<std::unique_ptr<IValidator>> validators_;
+};
+
+struct RefValidator final : IValidator {
+  explicit RefValidator(IValidator* validator) : validator_(validator) {}
+
+  Optional<SchemaError> validate(ValidationContext& vc,
+                                 const dynamic& value) const override {
+    return vc.validate(validator_, value);
+  }
+  IValidator* validator_;
+};
+
+struct NotValidator final : IValidator {
+  NotValidator(SchemaValidatorContext& context, const dynamic& schema)
+      : validator_(SchemaValidator::make(context, schema)) {}
+
+  Optional<SchemaError> validate(ValidationContext& vc,
+                                 const dynamic& value) const override {
+    if (vc.validate(validator_.get(), value)) {
+      return none;
+    }
+    return makeError("Expected schema validation to fail", value);
+  }
+  std::unique_ptr<IValidator> validator_;
+};
+
+void SchemaValidator::loadSchema(SchemaValidatorContext& context,
+                                 const dynamic& schema) {
+  if (!schema.isObject() || schema.empty()) {
+    return;
+  }
+
+  // Check for $ref, if we have one we won't apply anything else. Refs are
+  // pointers to other parts of the json, e.g. #/foo/bar points to the schema
+  // located at root["foo"]["bar"].
+  if (const auto* p = schema.get_ptr("$ref")) {
+    // We only support absolute refs, i.e. those starting with '#'
+    if (p->isString() && p->stringPiece()[0] == '#') {
+      auto it = context.refs.find(p->getString());
+      if (it != context.refs.end()) {
+        validators_.emplace_back(make_unique<RefValidator>(it->second));
+        return;
+      }
+
+      // This is a ref, but we haven't loaded it yet. Find where it is based on
+      // the root schema.
+      std::vector<std::string> parts;
+      split("/", p->stringPiece(), parts);
+      const auto* s = &context.schema; // First part is '#'
+      for (size_t i = 1; s && i < parts.size(); ++i) {
+        // Per the standard, we must replace ~1 with / and then ~0 with ~
+        boost::replace_all(parts[i], "~1", "/");
+        boost::replace_all(parts[i], "~0", "~");
+        if (s->isObject()) {
+          s = s->get_ptr(parts[i]);
+          continue;
+        }
+        if (s->isArray()) {
+          try {
+            const size_t pos = to<size_t>(parts[i]);
+            if (pos < s->size()) {
+              s = s->get_ptr(pos);
+              continue;
+            }
+          } catch (const std::range_error& e) {
+            // ignore
+          }
+        }
+        break;
+      }
+      // If you have a self-recursive reference, this avoids getting into an
+      // infinite recursion, where we try to load a schema that just references
+      // itself, and then we try to load it again, and so on.
+      // Instead we load a pointer to the schema into the refs, so that any
+      // future references to it will just see that pointer and won't try to
+      // keep parsing further.
+      if (s) {
+        auto v = make_unique<SchemaValidator>();
+        context.refs[p->getString()] = v.get();
+        v->loadSchema(context, *s);
+        validators_.emplace_back(std::move(v));
+        return;
+      }
+    }
+  }
+
+  // Numeric validators
+  if (const auto* p = schema.get_ptr("multipleOf")) {
+    validators_.emplace_back(make_unique<MultipleOfValidator>(*p));
+  }
+  if (const auto* p = schema.get_ptr("maximum")) {
+    validators_.emplace_back(
+        make_unique<ComparisonValidator>(*p,
+                                         schema.get_ptr("exclusiveMaximum"),
+                                         ComparisonValidator::Type::MAX));
+  }
+  if (const auto* p = schema.get_ptr("minimum")) {
+    validators_.emplace_back(
+        make_unique<ComparisonValidator>(*p,
+                                         schema.get_ptr("exclusiveMinimum"),
+                                         ComparisonValidator::Type::MIN));
+  }
+
+  // String validators
+  if (const auto* p = schema.get_ptr("maxLength")) {
+    validators_.emplace_back(
+        make_unique<SizeValidator<std::greater_equal<int64_t>>>(
+            *p, dynamic::Type::STRING));
+  }
+  if (const auto* p = schema.get_ptr("minLength")) {
+    validators_.emplace_back(
+        make_unique<SizeValidator<std::less_equal<int64_t>>>(
+            *p, dynamic::Type::STRING));
+  }
+  if (const auto* p = schema.get_ptr("pattern")) {
+    validators_.emplace_back(make_unique<StringPatternValidator>(*p));
+  }
+
+  // Array validators
+  const auto* items = schema.get_ptr("items");
+  const auto* additionalItems = schema.get_ptr("additionalItems");
+  if (items || additionalItems) {
+    validators_.emplace_back(
+        make_unique<ArrayItemsValidator>(context, items, additionalItems));
+  }
+  if (const auto* p = schema.get_ptr("maxItems")) {
+    validators_.emplace_back(
+        make_unique<SizeValidator<std::greater_equal<int64_t>>>(
+            *p, dynamic::Type::ARRAY));
+  }
+  if (const auto* p = schema.get_ptr("minItems")) {
+    validators_.emplace_back(
+        make_unique<SizeValidator<std::less_equal<int64_t>>>(
+            *p, dynamic::Type::ARRAY));
+  }
+  if (const auto* p = schema.get_ptr("uniqueItems")) {
+    validators_.emplace_back(make_unique<ArrayUniqueValidator>(*p));
+  }
+
+  // Object validators
+  const auto* properties = schema.get_ptr("properties");
+  const auto* patternProperties = schema.get_ptr("patternProperties");
+  const auto* additionalProperties = schema.get_ptr("additionalProperties");
+  if (properties || patternProperties || additionalProperties) {
+    validators_.emplace_back(make_unique<PropertiesValidator>(
+        context, properties, patternProperties, additionalProperties));
+  }
+  if (const auto* p = schema.get_ptr("maxProperties")) {
+    validators_.emplace_back(
+        make_unique<SizeValidator<std::greater_equal<int64_t>>>(
+            *p, dynamic::Type::OBJECT));
+  }
+  if (const auto* p = schema.get_ptr("minProperties")) {
+    validators_.emplace_back(
+        make_unique<SizeValidator<std::less_equal<int64_t>>>(
+            *p, dynamic::Type::OBJECT));
+  }
+  if (const auto* p = schema.get_ptr("required")) {
+    validators_.emplace_back(make_unique<RequiredValidator>(*p));
+  }
+
+  // Misc validators
+  if (const auto* p = schema.get_ptr("dependencies")) {
+    validators_.emplace_back(make_unique<DependencyValidator>(context, *p));
+  }
+  if (const auto* p = schema.get_ptr("enum")) {
+    validators_.emplace_back(make_unique<EnumValidator>(*p));
+  }
+  if (const auto* p = schema.get_ptr("type")) {
+    validators_.emplace_back(make_unique<TypeValidator>(*p));
+  }
+  if (const auto* p = schema.get_ptr("allOf")) {
+    validators_.emplace_back(make_unique<AllOfValidator>(context, *p));
+  }
+  if (const auto* p = schema.get_ptr("anyOf")) {
+    validators_.emplace_back(make_unique<AnyOfValidator>(
+        context, *p, AnyOfValidator::Type::ONE_OR_MORE));
+  }
+  if (const auto* p = schema.get_ptr("oneOf")) {
+    validators_.emplace_back(make_unique<AnyOfValidator>(
+        context, *p, AnyOfValidator::Type::EXACTLY_ONE));
+  }
+  if (const auto* p = schema.get_ptr("not")) {
+    validators_.emplace_back(make_unique<NotValidator>(context, *p));
+  }
+}
+
+void SchemaValidator::validate(const dynamic& value) const {
+  ValidationContext vc;
+  if (auto se = validate(vc, value)) {
+    throw * se;
+  }
+}
+
+exception_wrapper SchemaValidator::try_validate(const dynamic& value) const
+    noexcept {
+  try {
+    ValidationContext vc;
+    if (auto se = validate(vc, value)) {
+      return make_exception_wrapper<SchemaError>(*se);
+    }
+  } catch (const std::exception& e) {
+    return exception_wrapper(std::current_exception(), e);
+  } catch (...) {
+    return exception_wrapper(std::current_exception());
+  }
+  return exception_wrapper();
+}
+
+Optional<SchemaError> SchemaValidator::validate(ValidationContext& vc,
+                                                const dynamic& value) const {
+  for (const auto& validator : validators_) {
+    if (auto se = vc.validate(validator.get(), value)) {
+      return se;
+    }
+  }
+  return none;
+}
+
+/**
+ * Metaschema, i.e. schema for schema.
+ * Inlined from the $schema url
+ */
+const char* metaschemaJson =
+    "\
+{ \
+    \"id\": \"http://json-schema.org/draft-04/schema#\", \
+    \"$schema\": \"http://json-schema.org/draft-04/schema#\", \
+    \"description\": \"Core schema meta-schema\", \
+    \"definitions\": { \
+        \"schemaArray\": { \
+            \"type\": \"array\", \
+            \"minItems\": 1, \
+            \"items\": { \"$ref\": \"#\" } \
+        }, \
+        \"positiveInteger\": { \
+            \"type\": \"integer\", \
+            \"minimum\": 0 \
+        }, \
+        \"positiveIntegerDefault0\": { \
+            \"allOf\": [ \
+          { \"$ref\": \"#/definitions/positiveInteger\" }, { \"default\": 0 } ]\
+        }, \
+        \"simpleTypes\": { \
+            \"enum\": [ \"array\", \"boolean\", \"integer\", \
+                        \"null\", \"number\", \"object\", \"string\" ] \
+        }, \
+        \"stringArray\": { \
+            \"type\": \"array\", \
+            \"items\": { \"type\": \"string\" }, \
+            \"minItems\": 1, \
+            \"uniqueItems\": true \
+        } \
+    }, \
+    \"type\": \"object\", \
+    \"properties\": { \
+        \"id\": { \
+            \"type\": \"string\", \
+            \"format\": \"uri\" \
+        }, \
+        \"$schema\": { \
+            \"type\": \"string\", \
+            \"format\": \"uri\" \
+        }, \
+        \"title\": { \
+            \"type\": \"string\" \
+        }, \
+        \"description\": { \
+            \"type\": \"string\" \
+        }, \
+        \"default\": {}, \
+        \"multipleOf\": { \
+            \"type\": \"number\", \
+            \"minimum\": 0, \
+            \"exclusiveMinimum\": true \
+        }, \
+        \"maximum\": { \
+            \"type\": \"number\" \
+        }, \
+        \"exclusiveMaximum\": { \
+            \"type\": \"boolean\", \
+            \"default\": false \
+        }, \
+        \"minimum\": { \
+            \"type\": \"number\" \
+        }, \
+        \"exclusiveMinimum\": { \
+            \"type\": \"boolean\", \
+            \"default\": false \
+        }, \
+        \"maxLength\": { \"$ref\": \"#/definitions/positiveInteger\" }, \
+        \"minLength\": { \"$ref\": \"#/definitions/positiveIntegerDefault0\" },\
+        \"pattern\": { \
+            \"type\": \"string\", \
+            \"format\": \"regex\" \
+        }, \
+        \"additionalItems\": { \
+            \"anyOf\": [ \
+                { \"type\": \"boolean\" }, \
+                { \"$ref\": \"#\" } \
+            ], \
+            \"default\": {} \
+        }, \
+        \"items\": { \
+            \"anyOf\": [ \
+                { \"$ref\": \"#\" }, \
+                { \"$ref\": \"#/definitions/schemaArray\" } \
+            ], \
+            \"default\": {} \
+        }, \
+        \"maxItems\": { \"$ref\": \"#/definitions/positiveInteger\" }, \
+        \"minItems\": { \"$ref\": \"#/definitions/positiveIntegerDefault0\" }, \
+        \"uniqueItems\": { \
+            \"type\": \"boolean\", \
+            \"default\": false \
+        }, \
+        \"maxProperties\": { \"$ref\": \"#/definitions/positiveInteger\" }, \
+        \"minProperties\": { \
+        \"$ref\": \"#/definitions/positiveIntegerDefault0\" }, \
+        \"required\": { \"$ref\": \"#/definitions/stringArray\" }, \
+        \"additionalProperties\": { \
+            \"anyOf\": [ \
+                { \"type\": \"boolean\" }, \
+                { \"$ref\": \"#\" } \
+            ], \
+            \"default\": {} \
+        }, \
+        \"definitions\": { \
+            \"type\": \"object\", \
+            \"additionalProperties\": { \"$ref\": \"#\" }, \
+            \"default\": {} \
+        }, \
+        \"properties\": { \
+            \"type\": \"object\", \
+            \"additionalProperties\": { \"$ref\": \"#\" }, \
+            \"default\": {} \
+        }, \
+        \"patternProperties\": { \
+            \"type\": \"object\", \
+            \"additionalProperties\": { \"$ref\": \"#\" }, \
+            \"default\": {} \
+        }, \
+        \"dependencies\": { \
+            \"type\": \"object\", \
+            \"additionalProperties\": { \
+                \"anyOf\": [ \
+                    { \"$ref\": \"#\" }, \
+                    { \"$ref\": \"#/definitions/stringArray\" } \
+                ] \
+            } \
+        }, \
+        \"enum\": { \
+            \"type\": \"array\", \
+            \"minItems\": 1, \
+            \"uniqueItems\": true \
+        }, \
+        \"type\": { \
+            \"anyOf\": [ \
+                { \"$ref\": \"#/definitions/simpleTypes\" }, \
+                { \
+                    \"type\": \"array\", \
+                    \"items\": { \"$ref\": \"#/definitions/simpleTypes\" }, \
+                    \"minItems\": 1, \
+                    \"uniqueItems\": true \
+                } \
+            ] \
+        }, \
+        \"allOf\": { \"$ref\": \"#/definitions/schemaArray\" }, \
+        \"anyOf\": { \"$ref\": \"#/definitions/schemaArray\" }, \
+        \"oneOf\": { \"$ref\": \"#/definitions/schemaArray\" }, \
+        \"not\": { \"$ref\": \"#\" } \
+    }, \
+    \"dependencies\": { \
+        \"exclusiveMaximum\": [ \"maximum\" ], \
+        \"exclusiveMinimum\": [ \"minimum\" ] \
+    }, \
+    \"default\": {} \
+}";
+
+folly::Singleton<Validator> schemaValidator([]() {
+  return makeValidator(parseJson(metaschemaJson)).release();
+});
+}
+
+Validator::~Validator() {}
+
+std::unique_ptr<Validator> makeValidator(const dynamic& schema) {
+  auto v = make_unique<SchemaValidator>();
+  SchemaValidatorContext context(schema);
+  context.refs["#"] = v.get();
+  v->loadSchema(context, schema);
+  return std::move(v);
+}
+
+Validator* makeSchemaValidator() { return schemaValidator.get(); }
+}
+}
diff --git a/folly/experimental/JSONSchema.h b/folly/experimental/JSONSchema.h
new file mode 100644 (file)
index 0000000..7f98776
--- /dev/null
@@ -0,0 +1,73 @@
+/*
+ * Copyright 2015 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#include <folly/ExceptionWrapper.h>
+#include <folly/dynamic.h>
+#include <folly/Range.h>
+
+/**
+ * Validation according to the draft v4 standard: http://json-schema.org/
+ *
+ * If your schema is invalid, then it won't validate anything. For example, if
+ * you set "type": "invalid_type" in your schema, then it won't check for any
+ * type, as if you had left that property out. If you want to make sure your
+ * schema is valid, you can optionally validate it first according to the
+ * metaschema.
+ *
+ * Limitations:
+ * - We don't support fetching schemas via HTTP.
+ * - We don't support remote $refs.
+ * - We don't support $ref via id (only by path).
+ * - We don't support UTF-8 for string lengths, i.e. we will count bytes for
+ *   schemas that use minLength/maxLength.
+ */
+
+namespace folly {
+namespace jsonschema {
+
+/**
+ * Interface for a schema validator.
+ */
+struct Validator {
+  virtual ~Validator() = 0;
+
+  /**
+   * Check whether the given value passes the schema. Throws if it fails.
+   */
+  virtual void validate(const dynamic& value) const = 0;
+
+  /**
+   * Check whether the given value passes the schema. Returns an
+   * exception_wrapper indicating success or what the failure was.
+   */
+  virtual exception_wrapper try_validate(const dynamic& value) const
+      noexcept = 0;
+};
+
+/**
+ * Make a validator that can be used to check various json. Thread-safe.
+ */
+std::unique_ptr<Validator> makeValidator(const dynamic& schema);
+
+/**
+ * Makes a validator for schemas. You should probably check your schema with
+ * this before you use makeValidator().
+ */
+Validator* makeSchemaValidator();
+}
+}
diff --git a/folly/experimental/JSONSchemaTester.cpp b/folly/experimental/JSONSchemaTester.cpp
new file mode 100644 (file)
index 0000000..e2a0d3f
--- /dev/null
@@ -0,0 +1,55 @@
+/*
+ * Copyright 2015 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#include <folly/experimental/JSONSchema.h>
+#include <folly/json.h>
+#include <fstream>
+#include <string>
+
+/**
+ * A binary that supports testing against the official tests from:
+ * https://github.com/json-schema/JSON-Schema-Test-Suite
+ *
+ * Use it like:
+ *   ./jsonschema_tester /path/to/test.json
+ */
+
+int main(int argc, char** argv) {
+  if (argc < 2) {
+    printf("Usage: %s <testfile> [testfile2]...\n", argv[0]);
+    return -1;
+  }
+  for (int i = 1; i < argc; ++i) {
+    printf("FILE: %s\n", argv[i]);
+    std::ifstream fin(argv[i]);
+    std::stringstream buffer;
+    buffer << fin.rdbuf();
+    const folly::dynamic d = folly::parseJson(buffer.str());
+    for (const auto& item : d) {
+      printf("TEST: %s\n", item["description"].c_str());
+      auto v = folly::jsonschema::makeValidator(item["schema"]);
+      for (const auto& t : item["tests"]) {
+        printf("\t%s... ", t["description"].c_str());
+        auto ew = v->try_validate(t["data"]);
+        bool had_error = !static_cast<bool>(ew);
+        if (had_error == t["valid"].asBool()) {
+          printf("passed\n");
+        } else {
+          printf("FAILED\n");
+        }
+      }
+    }
+  }
+}
diff --git a/folly/experimental/test/JSONSchemaTest.cpp b/folly/experimental/test/JSONSchemaTest.cpp
new file mode 100644 (file)
index 0000000..72e64ac
--- /dev/null
@@ -0,0 +1,444 @@
+/*
+ * Copyright 2015 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+// Copyright 2004-present Facebook. All Rights Reserved.
+
+#include <folly/experimental/JSONSchema.h>
+#include <folly/json.h>
+#include <gtest/gtest.h>
+
+using folly::dynamic;
+using folly::parseJson;
+using namespace folly::jsonschema;
+using namespace std;
+
+bool check(const dynamic& schema, const dynamic& value, bool check = true) {
+  if (check) {
+    auto schemavalidator = makeSchemaValidator();
+    auto ew = schemavalidator->try_validate(schema);
+    if (ew) {
+      return false;
+    }
+  }
+
+  auto validator = makeValidator(schema);
+  auto ew = validator->try_validate(value);
+  if (validator->try_validate(value)) {
+    return false;
+  }
+  return true;
+}
+
+TEST(JSONSchemaTest, TestMultipleOfInt) {
+  dynamic schema = dynamic::object("multipleOf", 2);
+  ASSERT_TRUE(check(schema, "invalid"));
+  ASSERT_TRUE(check(schema, 30));
+  ASSERT_TRUE(check(schema, 24.0));
+  ASSERT_FALSE(check(schema, 5));
+  ASSERT_FALSE(check(schema, 2.01));
+}
+
+TEST(JSONSchemaTest, TestMultipleOfDouble) {
+  dynamic schema = dynamic::object("multipleOf", 1.5);
+  ASSERT_TRUE(check(schema, "invalid"));
+  ASSERT_TRUE(check(schema, 30));
+  ASSERT_TRUE(check(schema, 24.0));
+  ASSERT_FALSE(check(schema, 5));
+  ASSERT_FALSE(check(schema, 2.01));
+
+  schema = dynamic::object("multipleOf", 0.0001);
+  ASSERT_TRUE(check(schema, 0.0075));
+}
+
+TEST(JSONSchemaTest, TestMinimumIntInclusive) {
+  dynamic schema = dynamic::object("minimum", 2);
+  ASSERT_TRUE(check(schema, "invalid"));
+  ASSERT_TRUE(check(schema, 30));
+  ASSERT_TRUE(check(schema, 24.0));
+  ASSERT_TRUE(check(schema, 2));
+  ASSERT_FALSE(check(schema, 1));
+  ASSERT_FALSE(check(schema, 1.9999));
+}
+
+TEST(JSONSchemaTest, TestMinimumIntExclusive) {
+  dynamic schema = dynamic::object("minimum", 2)("exclusiveMinimum", true);
+  ASSERT_FALSE(check(schema, 2));
+}
+
+TEST(JSONSchemaTest, TestMaximumIntInclusive) {
+  dynamic schema = dynamic::object("maximum", 12);
+  ASSERT_TRUE(check(schema, "invalid"));
+  ASSERT_TRUE(check(schema, 3));
+  ASSERT_TRUE(check(schema, 3.1));
+  ASSERT_TRUE(check(schema, 12));
+  ASSERT_FALSE(check(schema, 13));
+  ASSERT_FALSE(check(schema, 12.0001));
+}
+
+TEST(JSONSchemaTest, TestMaximumIntExclusive) {
+  dynamic schema = dynamic::object("maximum", 2)("exclusiveMaximum", true);
+  ASSERT_FALSE(check(schema, 2));
+}
+
+TEST(JSONSchemaTest, TestMinimumDoubleInclusive) {
+  dynamic schema = dynamic::object("minimum", 1.75);
+  ASSERT_TRUE(check(schema, "invalid"));
+  ASSERT_TRUE(check(schema, 30));
+  ASSERT_TRUE(check(schema, 24.0));
+  ASSERT_TRUE(check(schema, 1.75));
+  ASSERT_FALSE(check(schema, 1));
+  ASSERT_FALSE(check(schema, 1.74));
+}
+
+TEST(JSONSchemaTest, TestMinimumDoubleExclusive) {
+  dynamic schema = dynamic::object("minimum", 1.75)("exclusiveMinimum", true);
+  ASSERT_FALSE(check(schema, 1.75));
+}
+
+TEST(JSONSchemaTest, TestMaximumDoubleInclusive) {
+  dynamic schema = dynamic::object("maximum", 12.75);
+  ASSERT_TRUE(check(schema, "invalid"));
+  ASSERT_TRUE(check(schema, 3));
+  ASSERT_TRUE(check(schema, 3.1));
+  ASSERT_TRUE(check(schema, 12.75));
+  ASSERT_FALSE(check(schema, 13));
+  ASSERT_FALSE(check(schema, 12.76));
+}
+
+TEST(JSONSchemaTest, TestMaximumDoubleExclusive) {
+  dynamic schema = dynamic::object("maximum", 12.75)("exclusiveMaximum", true);
+  ASSERT_FALSE(check(schema, 12.75));
+}
+
+TEST(JSONSchemaTest, TestInvalidSchema) {
+  dynamic schema = dynamic::object("multipleOf", "invalid");
+  // don't check the schema since it's meant to be invalid
+  ASSERT_TRUE(check(schema, 30, false));
+
+  schema = dynamic::object("minimum", "invalid")("maximum", "invalid");
+  ASSERT_TRUE(check(schema, 2, false));
+
+  schema = dynamic::object("minLength", "invalid")("maxLength", "invalid");
+  ASSERT_TRUE(check(schema, 2, false));
+  ASSERT_TRUE(check(schema, "foo", false));
+}
+
+TEST(JSONSchemaTest, TestMinimumStringLength) {
+  dynamic schema = dynamic::object("minLength", 3);
+  ASSERT_TRUE(check(schema, "abcde"));
+  ASSERT_TRUE(check(schema, "abc"));
+  ASSERT_FALSE(check(schema, "a"));
+}
+
+TEST(JSONSchemaTest, TestMaximumStringLength) {
+  dynamic schema = dynamic::object("maxLength", 3);
+  ASSERT_FALSE(check(schema, "abcde"));
+  ASSERT_TRUE(check(schema, "abc"));
+  ASSERT_TRUE(check(schema, "a"));
+}
+
+TEST(JSONSchemaTest, TestStringPattern) {
+  dynamic schema = dynamic::object("pattern", "[1-9]+");
+  ASSERT_TRUE(check(schema, "123"));
+  ASSERT_FALSE(check(schema, "abc"));
+}
+
+TEST(JSONSchemaTest, TestMinimumArrayItems) {
+  dynamic schema = dynamic::object("minItems", 3);
+  ASSERT_TRUE(check(schema, {1, 2, 3, 4, 5}));
+  ASSERT_TRUE(check(schema, {1, 2, 3}));
+  ASSERT_FALSE(check(schema, {1}));
+}
+
+TEST(JSONSchemaTest, TestMaximumArrayItems) {
+  dynamic schema = dynamic::object("maxItems", 3);
+  ASSERT_FALSE(check(schema, {1, 2, 3, 4, 5}));
+  ASSERT_TRUE(check(schema, {1, 2, 3}));
+  ASSERT_TRUE(check(schema, {1}));
+  ASSERT_TRUE(check(schema, "foobar"));
+}
+
+TEST(JSONSchemaTest, TestArrayUniqueItems) {
+  dynamic schema = dynamic::object("uniqueItems", true);
+  ASSERT_TRUE(check(schema, {1, 2, 3}));
+  ASSERT_FALSE(check(schema, {1, 2, 3, 1}));
+  ASSERT_FALSE(check(schema, {"cat", "dog", 1, 2, "cat"}));
+  ASSERT_TRUE(check(schema, {
+    dynamic::object("foo", "bar"),
+    dynamic::object("foo", "baz")
+  }));
+
+  schema = dynamic::object("uniqueItems", false);
+  ASSERT_TRUE(check(schema, {1, 2, 3, 1}));
+}
+
+TEST(JSONSchemaTest, TestArrayItems) {
+  dynamic schema = dynamic::object("items", dynamic::object("minimum", 2));
+  ASSERT_TRUE(check(schema, {2, 3, 4}));
+  ASSERT_FALSE(check(schema, {3, 4, 1}));
+}
+
+TEST(JSONSchemaTest, TestArrayAdditionalItems) {
+  dynamic schema = dynamic::object(
+      "items", {dynamic::object("minimum", 2), dynamic::object("minimum", 1)})(
+      "additionalItems", dynamic::object("minimum", 3));
+  ASSERT_TRUE(check(schema, {2, 1, 3, 3, 3, 3, 4}));
+  ASSERT_FALSE(check(schema, {2, 1, 3, 3, 3, 3, 1}));
+}
+
+TEST(JSONSchemaTest, TestArrayNoAdditionalItems) {
+  dynamic schema = dynamic::object("items", {dynamic::object("minimum", 2)})(
+      "additionalItems", false);
+  ASSERT_FALSE(check(schema, {3, 3, 3}));
+}
+
+TEST(JSONSchemaTest, TestArrayItemsNotPresent) {
+  dynamic schema = dynamic::object("additionalItems", false);
+  ASSERT_TRUE(check(schema, {3, 3, 3}));
+}
+
+TEST(JSONSchemaTest, TestRef) {
+  dynamic schema = dynamic::object(
+      "definitions",
+      dynamic::object("positiveInteger",
+                      dynamic::object("minimum", 1)("type", "integer")))(
+      "items", dynamic::object("$ref", "#/definitions/positiveInteger"));
+  ASSERT_TRUE(check(schema, {1, 2, 3, 4}));
+  ASSERT_FALSE(check(schema, {4, -5}));
+}
+
+TEST(JSONSchemaTest, TestRecursiveRef) {
+  dynamic schema = dynamic::object(
+      "properties", dynamic::object("more", dynamic::object("$ref", "#")));
+  dynamic d = dynamic::object;
+  ASSERT_TRUE(check(schema, d));
+  d["more"] = dynamic::object;
+  ASSERT_TRUE(check(schema, d));
+  d["more"]["more"] = dynamic::object;
+  ASSERT_TRUE(check(schema, d));
+  d["more"]["more"]["more"] = dynamic::object;
+  ASSERT_TRUE(check(schema, d));
+}
+
+TEST(JSONSchemaTest, TestDoubleRecursiveRef) {
+  dynamic schema =
+      dynamic::object("properties",
+                      dynamic::object("more", dynamic::object("$ref", "#"))(
+                          "less", dynamic::object("$ref", "#")));
+  dynamic d = dynamic::object;
+  ASSERT_TRUE(check(schema, d));
+  d["more"] = dynamic::object;
+  d["less"] = dynamic::object;
+  ASSERT_TRUE(check(schema, d));
+  d["more"]["less"] = dynamic::object;
+  d["less"]["mode"] = dynamic::object;
+  ASSERT_TRUE(check(schema, d));
+}
+
+TEST(JSONSchemaTest, TestInfinitelyRecursiveRef) {
+  dynamic schema = dynamic::object("not", dynamic::object("$ref", "#"));
+  auto validator = makeValidator(schema);
+  ASSERT_THROW(validator->validate({1, 2}), std::runtime_error);
+}
+
+TEST(JSONSchemaTest, TestRequired) {
+  dynamic schema = dynamic::object("required", {"foo", "bar"});
+  ASSERT_FALSE(check(schema, dynamic::object("foo", 123)));
+  ASSERT_FALSE(check(schema, dynamic::object("bar", 123)));
+  ASSERT_TRUE(check(schema, dynamic::object("bar", 123)("foo", 456)));
+}
+
+TEST(JSONSchemaTest, TestMinMaxProperties) {
+  dynamic schema = dynamic::object("minProperties", 1)("maxProperties", 3);
+  dynamic d = dynamic::object;
+  ASSERT_FALSE(check(schema, d));
+  d["a"] = 1;
+  ASSERT_TRUE(check(schema, d));
+  d["b"] = 2;
+  ASSERT_TRUE(check(schema, d));
+  d["c"] = 3;
+  ASSERT_TRUE(check(schema, d));
+  d["d"] = 4;
+  ASSERT_FALSE(check(schema, d));
+}
+
+TEST(JSONSchemaTest, TestProperties) {
+  dynamic schema = dynamic::object(
+      "properties", dynamic::object("p1", dynamic::object("minimum", 1)))(
+      "patternProperties", dynamic::object("[0-9]+", dynamic::object))(
+      "additionalProperties", dynamic::object("maximum", 5));
+  ASSERT_TRUE(check(schema, dynamic::object("p1", 1)));
+  ASSERT_FALSE(check(schema, dynamic::object("p1", 0)));
+  ASSERT_TRUE(check(schema, dynamic::object("123", "anything")));
+  ASSERT_TRUE(check(schema, dynamic::object("123", 500)));
+  ASSERT_TRUE(check(schema, dynamic::object("other_property", 4)));
+  ASSERT_FALSE(check(schema, dynamic::object("other_property", 6)));
+}
+TEST(JSONSchemaTest, TestPropertyAndPattern) {
+  dynamic schema = dynamic::object
+    ("properties", dynamic::object("p1", dynamic::object("minimum", 1)))
+    ("patternProperties", dynamic::object("p.", dynamic::object("maximum", 5)));
+  ASSERT_TRUE(check(schema, dynamic::object("p1", 3)));
+  ASSERT_FALSE(check(schema, dynamic::object("p1", 0)));
+  ASSERT_FALSE(check(schema, dynamic::object("p1", 6)));
+}
+
+TEST(JSONSchemaTest, TestPropertyDependency) {
+  dynamic schema =
+      dynamic::object("dependencies", dynamic::object("p1", {"p2"}));
+  ASSERT_TRUE(check(schema, dynamic::object));
+  ASSERT_TRUE(check(schema, dynamic::object("p1", 1)("p2", 1)));
+  ASSERT_FALSE(check(schema, dynamic::object("p1", 1)));
+}
+
+TEST(JSONSchemaTest, TestSchemaDependency) {
+  dynamic schema = dynamic::object(
+      "dependencies",
+      dynamic::object("p1", dynamic::object("required", {"p2"})));
+  ASSERT_TRUE(check(schema, dynamic::object));
+  ASSERT_TRUE(check(schema, dynamic::object("p1", 1)("p2", 1)));
+  ASSERT_FALSE(check(schema, dynamic::object("p1", 1)));
+}
+
+TEST(JSONSchemaTest, TestEnum) {
+  dynamic schema = dynamic::object("enum", {"a", 1});
+  ASSERT_TRUE(check(schema, "a"));
+  ASSERT_TRUE(check(schema, 1));
+  ASSERT_FALSE(check(schema, "b"));
+}
+
+TEST(JSONSchemaTest, TestType) {
+  dynamic schema = dynamic::object("type", "object");
+  ASSERT_TRUE(check(schema, dynamic::object));
+  ASSERT_FALSE(check(schema, dynamic(5)));
+}
+
+TEST(JSONSchemaTest, TestTypeArray) {
+  dynamic schema = dynamic::object("type", {"array", "number"});
+  ASSERT_TRUE(check(schema, dynamic(5)));
+  ASSERT_TRUE(check(schema, dynamic(1.1)));
+  ASSERT_FALSE(check(schema, dynamic::object));
+}
+
+TEST(JSONSchemaTest, TestAllOf) {
+  dynamic schema = dynamic::object(
+      "allOf",
+      {dynamic::object("minimum", 1), dynamic::object("type", "integer")});
+  ASSERT_TRUE(check(schema, 2));
+  ASSERT_FALSE(check(schema, 0));
+  ASSERT_FALSE(check(schema, 1.1));
+}
+
+TEST(JSONSchemaTest, TestAnyOf) {
+  dynamic schema = dynamic::object(
+      "anyOf",
+      {dynamic::object("minimum", 1), dynamic::object("type", "integer")});
+  ASSERT_TRUE(check(schema, 2)); // matches both
+  ASSERT_FALSE(check(schema, 0.1)); // matches neither
+  ASSERT_TRUE(check(schema, 1.1)); // matches first one
+  ASSERT_TRUE(check(schema, 0)); // matches second one
+}
+
+TEST(JSONSchemaTest, TestOneOf) {
+  dynamic schema = dynamic::object(
+      "oneOf",
+      {dynamic::object("minimum", 1), dynamic::object("type", "integer")});
+  ASSERT_FALSE(check(schema, 2)); // matches both
+  ASSERT_FALSE(check(schema, 0.1)); // matches neither
+  ASSERT_TRUE(check(schema, 1.1)); // matches first one
+  ASSERT_TRUE(check(schema, 0)); // matches second one
+}
+
+TEST(JSONSchemaTest, TestNot) {
+  dynamic schema =
+      dynamic::object("not", dynamic::object("minimum", 5)("maximum", 10));
+  ASSERT_TRUE(check(schema, 4));
+  ASSERT_FALSE(check(schema, 7));
+  ASSERT_TRUE(check(schema, 11));
+}
+
+// The tests below use some sample schema from json-schema.org
+
+TEST(JSONSchemaTest, TestMetaSchema) {
+  const char* example1 =
+      "\
+    { \
+      \"title\": \"Example Schema\", \
+      \"type\": \"object\", \
+      \"properties\": { \
+        \"firstName\": { \
+          \"type\": \"string\" \
+        }, \
+        \"lastName\": { \
+          \"type\": \"string\" \
+        }, \
+        \"age\": { \
+          \"description\": \"Age in years\", \
+          \"type\": \"integer\", \
+          \"minimum\": 0 \
+        } \
+      }, \
+      \"required\": [\"firstName\", \"lastName\"] \
+    }";
+
+  auto val = makeSchemaValidator();
+  val->validate(parseJson(example1)); // doesn't throw
+
+  ASSERT_THROW(val->validate("123"), std::runtime_error);
+}
+
+TEST(JSONSchemaTest, TestProductSchema) {
+  const char* productSchema =
+      "\
+  { \
+    \"$schema\": \"http://json-schema.org/draft-04/schema#\", \
+      \"title\": \"Product\", \
+      \"description\": \"A product from Acme's catalog\", \
+      \"type\": \"object\", \
+      \"properties\": { \
+        \"id\": { \
+          \"description\": \"The unique identifier for a product\", \
+          \"type\": \"integer\" \
+        }, \
+        \"name\": { \
+          \"description\": \"Name of the product\", \
+          \"type\": \"string\" \
+        }, \
+        \"price\": { \
+          \"type\": \"number\", \
+          \"minimum\": 0, \
+          \"exclusiveMinimum\": true \
+        }, \
+        \"tags\": { \
+          \"type\": \"array\", \
+          \"items\": { \
+            \"type\": \"string\" \
+          }, \
+          \"minItems\": 1, \
+          \"uniqueItems\": true \
+        } \
+      }, \
+      \"required\": [\"id\", \"name\", \"price\"] \
+  }";
+  const char* product =
+      "\
+  { \
+    \"id\": 1, \
+    \"name\": \"A green door\", \
+    \"price\": 12.50, \
+    \"tags\": [\"home\", \"green\"] \
+  }";
+  ASSERT_TRUE(check(parseJson(productSchema), parseJson(product)));
+}