components/json_schema/json_schema_validator.cc

   1 // Copyright 2013 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "components/json_schema/json_schema_validator.h"
   6
   7 #include <algorithm>
   8 #include <cfloat>
   9 #include <cmath>
  10 #include <vector>
  11
  12 #include "base/json/json_reader.h"
  13 #include "base/logging.h"
  14 #include "base/memory/scoped_vector.h"
  15 #include "base/strings/string_number_conversions.h"
  16 #include "base/strings/string_util.h"
  17 #include "base/strings/stringprintf.h"
  18 #include "base/values.h"
  19 #include "components/json_schema/json_schema_constants.h"
  20 #include "third_party/re2/re2/re2.h"
  21
  22 namespace schema = json_schema_constants;
  23
  24 namespace {
  25
  26 double GetNumberValue(const base::Value* value) {
  27   double result = 0;
  28   CHECK(value->GetAsDouble(&result))
  29       << "Unexpected value type: " << value->GetType();
  30   return result;
  31 }
  32
  33 bool IsValidType(const std::string& type) {
  34   static const char* kValidTypes[] = {
  35     schema::kAny,
  36     schema::kArray,
  37     schema::kBoolean,
  38     schema::kInteger,
  39     schema::kNull,
  40     schema::kNumber,
  41     schema::kObject,
  42     schema::kString,
  43   };
  44   const char** end = kValidTypes + arraysize(kValidTypes);
  45   return std::find(kValidTypes, end, type) != end;
  46 }
  47
  48 // Maps a schema attribute name to its expected type.
  49 struct ExpectedType {
  50   const char* key;
  51   base::Value::Type type;
  52 };
  53
  54 // Helper for std::lower_bound.
  55 bool CompareToString(const ExpectedType& entry, const std::string& key) {
  56   return entry.key < key;
  57 }
  58
  59 // If |value| is a dictionary, returns the "name" attribute of |value| or NULL
  60 // if |value| does not contain a "name" attribute. Otherwise, returns |value|.
  61 const base::Value* ExtractNameFromDictionary(const base::Value* value) {
  62   const base::DictionaryValue* value_dict = NULL;
  63   const base::Value* name_value = NULL;
  64   if (value->GetAsDictionary(&value_dict)) {
  65     value_dict->Get("name", &name_value);
  66     return name_value;
  67   }
  68   return value;
  69 }
  70
  71 bool IsValidSchema(const base::DictionaryValue* dict,
  72                    int options,
  73                    std::string* error) {
  74   // This array must be sorted, so that std::lower_bound can perform a
  75   // binary search.
  76   static const ExpectedType kExpectedTypes[] = {
  77     // Note: kRef == "$ref", kSchema == "$schema"
  78     { schema::kRef,                     base::Value::TYPE_STRING      },
  79     { schema::kSchema,                  base::Value::TYPE_STRING      },
  80
  81     { schema::kAdditionalProperties,    base::Value::TYPE_DICTIONARY  },
  82     { schema::kChoices,                 base::Value::TYPE_LIST        },
  83     { schema::kDescription,             base::Value::TYPE_STRING      },
  84     { schema::kEnum,                    base::Value::TYPE_LIST        },
  85     { schema::kId,                      base::Value::TYPE_STRING      },
  86     { schema::kMaxItems,                base::Value::TYPE_INTEGER     },
  87     { schema::kMaxLength,               base::Value::TYPE_INTEGER     },
  88     { schema::kMaximum,                 base::Value::TYPE_DOUBLE      },
  89     { schema::kMinItems,                base::Value::TYPE_INTEGER     },
  90     { schema::kMinLength,               base::Value::TYPE_INTEGER     },
  91     { schema::kMinimum,                 base::Value::TYPE_DOUBLE      },
  92     { schema::kOptional,                base::Value::TYPE_BOOLEAN     },
  93     { schema::kPattern,                 base::Value::TYPE_STRING      },
  94     { schema::kPatternProperties,       base::Value::TYPE_DICTIONARY  },
  95     { schema::kProperties,              base::Value::TYPE_DICTIONARY  },
  96     { schema::kTitle,                   base::Value::TYPE_STRING      },
  97   };
  98
  99   bool has_type_or_ref = false;
 100   const base::ListValue* list_value = NULL;
 101   const base::DictionaryValue* dictionary_value = NULL;
 102   std::string string_value;
 103
 104   for (base::DictionaryValue::Iterator it(*dict); !it.IsAtEnd(); it.Advance()) {
 105     // Validate the "type" attribute, which may be a string or a list.
 106     if (it.key() == schema::kType) {
 107       switch (it.value().GetType()) {
 108         case base::Value::TYPE_STRING:
 109           it.value().GetAsString(&string_value);
 110           if (!IsValidType(string_value)) {
 111             *error = "Invalid value for type attribute";
 112             return false;
 113           }
 114           break;
 115         case base::Value::TYPE_LIST:
 116           it.value().GetAsList(&list_value);
 117           for (size_t i = 0; i < list_value->GetSize(); ++i) {
 118             if (!list_value->GetString(i, &string_value) ||
 119                 !IsValidType(string_value)) {
 120               *error = "Invalid value for type attribute";
 121               return false;
 122             }
 123           }
 124           break;
 125         default:
 126           *error = "Invalid value for type attribute";
 127           return false;
 128       }
 129       has_type_or_ref = true;
 130       continue;
 131     }
 132
 133     // Validate the "items" attribute, which is a schema or a list of schemas.
 134     if (it.key() == schema::kItems) {
 135       if (it.value().GetAsDictionary(&dictionary_value)) {
 136         if (!IsValidSchema(dictionary_value, options, error)) {
 137           DCHECK(!error->empty());
 138           return false;
 139         }
 140       } else if (it.value().GetAsList(&list_value)) {
 141         for (size_t i = 0; i < list_value->GetSize(); ++i) {
 142           if (!list_value->GetDictionary(i, &dictionary_value)) {
 143             *error = base::StringPrintf(
 144                 "Invalid entry in items attribute at index %d",
 145                 static_cast<int>(i));
 146             return false;
 147           }
 148           if (!IsValidSchema(dictionary_value, options, error)) {
 149             DCHECK(!error->empty());
 150             return false;
 151           }
 152         }
 153       } else {
 154         *error = "Invalid value for items attribute";
 155         return false;
 156       }
 157       continue;
 158     }
 159
 160     // All the other attributes have a single valid type.
 161     const ExpectedType* end = kExpectedTypes + arraysize(kExpectedTypes);
 162     const ExpectedType* entry = std::lower_bound(
 163         kExpectedTypes, end, it.key(), CompareToString);
 164     if (entry == end || entry->key != it.key()) {
 165       if (options & JSONSchemaValidator::OPTIONS_IGNORE_UNKNOWN_ATTRIBUTES)
 166         continue;
 167       *error = base::StringPrintf("Invalid attribute %s", it.key().c_str());
 168       return false;
 169     }
 170
 171     // Integer can be converted to double.
 172     if (!(it.value().IsType(entry->type) ||
 173           (it.value().IsType(base::Value::TYPE_INTEGER) &&
 174            entry->type == base::Value::TYPE_DOUBLE))) {
 175       *error = base::StringPrintf("Invalid value for %s attribute",
 176                                   it.key().c_str());
 177       return false;
 178     }
 179
 180     // base::Value::TYPE_INTEGER attributes must be >= 0.
 181     // This applies to "minItems", "maxItems", "minLength" and "maxLength".
 182     if (it.value().IsType(base::Value::TYPE_INTEGER)) {
 183       int integer_value;
 184       it.value().GetAsInteger(&integer_value);
 185       if (integer_value < 0) {
 186         *error = base::StringPrintf("Value of %s must be >= 0, got %d",
 187                                     it.key().c_str(), integer_value);
 188         return false;
 189       }
 190     }
 191
 192     // Validate the "properties" attribute. Each entry maps a key to a schema.
 193     if (it.key() == schema::kProperties) {
 194       it.value().GetAsDictionary(&dictionary_value);
 195       for (base::DictionaryValue::Iterator iter(*dictionary_value);
 196            !iter.IsAtEnd(); iter.Advance()) {
 197         if (!iter.value().GetAsDictionary(&dictionary_value)) {
 198           *error = "properties must be a dictionary";
 199           return false;
 200         }
 201         if (!IsValidSchema(dictionary_value, options, error)) {
 202           DCHECK(!error->empty());
 203           return false;
 204         }
 205       }
 206     }
 207
 208     // Validate the "patternProperties" attribute. Each entry maps a regular
 209     // expression to a schema. The validity of the regular expression expression
 210     // won't be checked here for performance reasons. Instead, invalid regular
 211     // expressions will be caught as validation errors in Validate().
 212     if (it.key() == schema::kPatternProperties) {
 213       it.value().GetAsDictionary(&dictionary_value);
 214       for (base::DictionaryValue::Iterator iter(*dictionary_value);
 215            !iter.IsAtEnd(); iter.Advance()) {
 216         if (!iter.value().GetAsDictionary(&dictionary_value)) {
 217           *error = "patternProperties must be a dictionary";
 218           return false;
 219         }
 220         if (!IsValidSchema(dictionary_value, options, error)) {
 221           DCHECK(!error->empty());
 222           return false;
 223         }
 224       }
 225     }
 226
 227     // Validate "additionalProperties" attribute, which is a schema.
 228     if (it.key() == schema::kAdditionalProperties) {
 229       it.value().GetAsDictionary(&dictionary_value);
 230       if (!IsValidSchema(dictionary_value, options, error)) {
 231         DCHECK(!error->empty());
 232         return false;
 233       }
 234     }
 235
 236     // Validate the values contained in an "enum" attribute.
 237     if (it.key() == schema::kEnum) {
 238       it.value().GetAsList(&list_value);
 239       for (size_t i = 0; i < list_value->GetSize(); ++i) {
 240         const base::Value* value = NULL;
 241         list_value->Get(i, &value);
 242         // Sometimes the enum declaration is a dictionary with the enum value
 243         // under "name".
 244         value = ExtractNameFromDictionary(value);
 245         if (!value) {
 246           *error = "Invalid value in enum attribute";
 247           return false;
 248         }
 249         switch (value->GetType()) {
 250           case base::Value::TYPE_NULL:
 251           case base::Value::TYPE_BOOLEAN:
 252           case base::Value::TYPE_INTEGER:
 253           case base::Value::TYPE_DOUBLE:
 254           case base::Value::TYPE_STRING:
 255             break;
 256           default:
 257             *error = "Invalid value in enum attribute";
 258             return false;
 259         }
 260       }
 261     }
 262
 263     // Validate the schemas contained in a "choices" attribute.
 264     if (it.key() == schema::kChoices) {
 265       it.value().GetAsList(&list_value);
 266       for (size_t i = 0; i < list_value->GetSize(); ++i) {
 267         if (!list_value->GetDictionary(i, &dictionary_value)) {
 268           *error = "Invalid choices attribute";
 269           return false;
 270         }
 271         if (!IsValidSchema(dictionary_value, options, error)) {
 272           DCHECK(!error->empty());
 273           return false;
 274         }
 275       }
 276     }
 277
 278     if (it.key() == schema::kRef)
 279       has_type_or_ref = true;
 280   }
 281
 282   if (!has_type_or_ref) {
 283     *error = "Schema must have a type or a $ref attribute";
 284     return false;
 285   }
 286
 287   return true;
 288 }
 289
 290 }  // namespace
 291
 292
 293 JSONSchemaValidator::Error::Error() {
 294 }
 295
 296 JSONSchemaValidator::Error::Error(const std::string& message)
 297     : path(message) {
 298 }
 299
 300 JSONSchemaValidator::Error::Error(const std::string& path,
 301                                   const std::string& message)
 302     : path(path), message(message) {
 303 }
 304
 305
 306 const char JSONSchemaValidator::kUnknownTypeReference[] =
 307     "Unknown schema reference: *.";
 308 const char JSONSchemaValidator::kInvalidChoice[] =
 309     "Value does not match any valid type choices.";
 310 const char JSONSchemaValidator::kInvalidEnum[] =
 311     "Value does not match any valid enum choices.";
 312 const char JSONSchemaValidator::kObjectPropertyIsRequired[] =
 313     "Property is required.";
 314 const char JSONSchemaValidator::kUnexpectedProperty[] =
 315     "Unexpected property.";
 316 const char JSONSchemaValidator::kArrayMinItems[] =
 317     "Array must have at least * items.";
 318 const char JSONSchemaValidator::kArrayMaxItems[] =
 319     "Array must not have more than * items.";
 320 const char JSONSchemaValidator::kArrayItemRequired[] =
 321     "Item is required.";
 322 const char JSONSchemaValidator::kStringMinLength[] =
 323     "String must be at least * characters long.";
 324 const char JSONSchemaValidator::kStringMaxLength[] =
 325     "String must not be more than * characters long.";
 326 const char JSONSchemaValidator::kStringPattern[] =
 327     "String must match the pattern: *.";
 328 const char JSONSchemaValidator::kNumberMinimum[] =
 329     "Value must not be less than *.";
 330 const char JSONSchemaValidator::kNumberMaximum[] =
 331     "Value must not be greater than *.";
 332 const char JSONSchemaValidator::kInvalidType[] =
 333     "Expected '*' but got '*'.";
 334 const char JSONSchemaValidator::kInvalidTypeIntegerNumber[] =
 335     "Expected 'integer' but got 'number', consider using Math.round().";
 336 const char JSONSchemaValidator::kInvalidRegex[] =
 337     "Regular expression /*/ is invalid: *";
 338
 339
 340 // static
 341 std::string JSONSchemaValidator::GetJSONSchemaType(const base::Value* value) {
 342   switch (value->GetType()) {
 343     case base::Value::TYPE_NULL:
 344       return schema::kNull;
 345     case base::Value::TYPE_BOOLEAN:
 346       return schema::kBoolean;
 347     case base::Value::TYPE_INTEGER:
 348       return schema::kInteger;
 349     case base::Value::TYPE_DOUBLE: {
 350       double double_value = 0;
 351       value->GetAsDouble(&double_value);
 352       if (std::abs(double_value) <= std::pow(2.0, DBL_MANT_DIG) &&
 353           double_value == floor(double_value)) {
 354         return schema::kInteger;
 355       } else {
 356         return schema::kNumber;
 357       }
 358     }
 359     case base::Value::TYPE_STRING:
 360       return schema::kString;
 361     case base::Value::TYPE_DICTIONARY:
 362       return schema::kObject;
 363     case base::Value::TYPE_LIST:
 364       return schema::kArray;
 365     default:
 366       NOTREACHED() << "Unexpected value type: " << value->GetType();
 367       return std::string();
 368   }
 369 }
 370
 371 // static
 372 std::string JSONSchemaValidator::FormatErrorMessage(const std::string& format,
 373                                                     const std::string& s1) {
 374   std::string ret_val = format;
 375   ReplaceFirstSubstringAfterOffset(&ret_val, 0, "*", s1);
 376   return ret_val;
 377 }
 378
 379 // static
 380 std::string JSONSchemaValidator::FormatErrorMessage(const std::string& format,
 381                                                     const std::string& s1,
 382                                                     const std::string& s2) {
 383   std::string ret_val = format;
 384   ReplaceFirstSubstringAfterOffset(&ret_val, 0, "*", s1);
 385   ReplaceFirstSubstringAfterOffset(&ret_val, 0, "*", s2);
 386   return ret_val;
 387 }
 388
 389 // static
 390 scoped_ptr<base::DictionaryValue> JSONSchemaValidator::IsValidSchema(
 391     const std::string& schema,
 392     std::string* error) {
 393   return JSONSchemaValidator::IsValidSchema(schema, 0, error);
 394 }
 395
 396 // static
 397 scoped_ptr<base::DictionaryValue> JSONSchemaValidator::IsValidSchema(
 398     const std::string& schema,
 399     int validator_options,
 400     std::string* error) {
 401   base::JSONParserOptions json_options = base::JSON_PARSE_RFC;
 402   scoped_ptr<base::Value> json(
 403       base::JSONReader::ReadAndReturnError(schema, json_options, NULL, error));
 404   if (!json)
 405     return scoped_ptr<base::DictionaryValue>();
 406   base::DictionaryValue* dict = NULL;
 407   if (!json->GetAsDictionary(&dict)) {
 408     *error = "Schema must be a JSON object";
 409     return scoped_ptr<base::DictionaryValue>();
 410   }
 411   if (!::IsValidSchema(dict, validator_options, error))
 412     return scoped_ptr<base::DictionaryValue>();
 413   ignore_result(json.release());
 414   return make_scoped_ptr(dict);
 415 }
 416
 417 JSONSchemaValidator::JSONSchemaValidator(base::DictionaryValue* schema)
 418     : schema_root_(schema), default_allow_additional_properties_(false) {
 419 }
 420
 421 JSONSchemaValidator::JSONSchemaValidator(base::DictionaryValue* schema,
 422                                          base::ListValue* types)
 423     : schema_root_(schema), default_allow_additional_properties_(false) {
 424   if (!types)
 425     return;
 426
 427   for (size_t i = 0; i < types->GetSize(); ++i) {
 428     base::DictionaryValue* type = NULL;
 429     CHECK(types->GetDictionary(i, &type));
 430
 431     std::string id;
 432     CHECK(type->GetString(schema::kId, &id));
 433
 434     CHECK(types_.find(id) == types_.end());
 435     types_[id] = type;
 436   }
 437 }
 438
 439 JSONSchemaValidator::~JSONSchemaValidator() {}
 440
 441 bool JSONSchemaValidator::Validate(const base::Value* instance) {
 442   errors_.clear();
 443   Validate(instance, schema_root_, std::string());
 444   return errors_.empty();
 445 }
 446
 447 void JSONSchemaValidator::Validate(const base::Value* instance,
 448                                    const base::DictionaryValue* schema,
 449                                    const std::string& path) {
 450   // If this schema defines itself as reference type, save it in this.types.
 451   std::string id;
 452   if (schema->GetString(schema::kId, &id)) {
 453     TypeMap::iterator iter = types_.find(id);
 454     if (iter == types_.end())
 455       types_[id] = schema;
 456     else
 457       DCHECK(iter->second == schema);
 458   }
 459
 460   // If the schema has a $ref property, the instance must validate against
 461   // that schema. It must be present in types_ to be referenced.
 462   std::string ref;
 463   if (schema->GetString(schema::kRef, &ref)) {
 464     TypeMap::iterator type = types_.find(ref);
 465     if (type == types_.end()) {
 466       errors_.push_back(
 467           Error(path, FormatErrorMessage(kUnknownTypeReference, ref)));
 468     } else {
 469       Validate(instance, type->second, path);
 470     }
 471     return;
 472   }
 473
 474   // If the schema has a choices property, the instance must validate against at
 475   // least one of the items in that array.
 476   const base::ListValue* choices = NULL;
 477   if (schema->GetList(schema::kChoices, &choices)) {
 478     ValidateChoices(instance, choices, path);
 479     return;
 480   }
 481
 482   // If the schema has an enum property, the instance must be one of those
 483   // values.
 484   const base::ListValue* enumeration = NULL;
 485   if (schema->GetList(schema::kEnum, &enumeration)) {
 486     ValidateEnum(instance, enumeration, path);
 487     return;
 488   }
 489
 490   std::string type;
 491   schema->GetString(schema::kType, &type);
 492   CHECK(!type.empty());
 493   if (type != schema::kAny) {
 494     if (!ValidateType(instance, type, path))
 495       return;
 496
 497     // These casts are safe because of checks in ValidateType().
 498     if (type == schema::kObject) {
 499       ValidateObject(static_cast<const base::DictionaryValue*>(instance),
 500                      schema,
 501                      path);
 502     } else if (type == schema::kArray) {
 503       ValidateArray(static_cast<const base::ListValue*>(instance),
 504                     schema, path);
 505     } else if (type == schema::kString) {
 506       // Intentionally NOT downcasting to StringValue*. TYPE_STRING only implies
 507       // GetAsString() can safely be carried out, not that it's a StringValue.
 508       ValidateString(instance, schema, path);
 509     } else if (type == schema::kNumber || type == schema::kInteger) {
 510       ValidateNumber(instance, schema, path);
 511     } else if (type != schema::kBoolean && type != schema::kNull) {
 512       NOTREACHED() << "Unexpected type: " << type;
 513     }
 514   }
 515 }
 516
 517 void JSONSchemaValidator::ValidateChoices(const base::Value* instance,
 518                                           const base::ListValue* choices,
 519                                           const std::string& path) {
 520   size_t original_num_errors = errors_.size();
 521
 522   for (size_t i = 0; i < choices->GetSize(); ++i) {
 523     const base::DictionaryValue* choice = NULL;
 524     CHECK(choices->GetDictionary(i, &choice));
 525
 526     Validate(instance, choice, path);
 527     if (errors_.size() == original_num_errors)
 528       return;
 529
 530     // We discard the error from each choice. We only want to know if any of the
 531     // validations succeeded.
 532     errors_.resize(original_num_errors);
 533   }
 534
 535   // Now add a generic error that no choices matched.
 536   errors_.push_back(Error(path, kInvalidChoice));
 537   return;
 538 }
 539
 540 void JSONSchemaValidator::ValidateEnum(const base::Value* instance,
 541                                        const base::ListValue* choices,
 542                                        const std::string& path) {
 543   for (size_t i = 0; i < choices->GetSize(); ++i) {
 544     const base::Value* choice = NULL;
 545     CHECK(choices->Get(i, &choice));
 546     // Sometimes the enum declaration is a dictionary with the enum value under
 547     // "name".
 548     choice = ExtractNameFromDictionary(choice);
 549     if (!choice) {
 550       NOTREACHED();
 551     }
 552     switch (choice->GetType()) {
 553       case base::Value::TYPE_NULL:
 554       case base::Value::TYPE_BOOLEAN:
 555       case base::Value::TYPE_STRING:
 556         if (instance->Equals(choice))
 557           return;
 558         break;
 559
 560       case base::Value::TYPE_INTEGER:
 561       case base::Value::TYPE_DOUBLE:
 562         if (instance->IsType(base::Value::TYPE_INTEGER) ||
 563             instance->IsType(base::Value::TYPE_DOUBLE)) {
 564           if (GetNumberValue(choice) == GetNumberValue(instance))
 565             return;
 566         }
 567         break;
 568
 569       default:
 570        NOTREACHED() << "Unexpected type in enum: " << choice->GetType();
 571     }
 572   }
 573
 574   errors_.push_back(Error(path, kInvalidEnum));
 575 }
 576
 577 void JSONSchemaValidator::ValidateObject(const base::DictionaryValue* instance,
 578                                          const base::DictionaryValue* schema,
 579                                          const std::string& path) {
 580   const base::DictionaryValue* properties = NULL;
 581   if (schema->GetDictionary(schema::kProperties, &properties)) {
 582     for (base::DictionaryValue::Iterator it(*properties); !it.IsAtEnd();
 583          it.Advance()) {
 584       std::string prop_path = path.empty() ? it.key() : (path + "." + it.key());
 585       const base::DictionaryValue* prop_schema = NULL;
 586       CHECK(it.value().GetAsDictionary(&prop_schema));
 587
 588       const base::Value* prop_value = NULL;
 589       if (instance->Get(it.key(), &prop_value)) {
 590         Validate(prop_value, prop_schema, prop_path);
 591       } else {
 592         // Properties are required unless there is an optional field set to
 593         // 'true'.
 594         bool is_optional = false;
 595         prop_schema->GetBoolean(schema::kOptional, &is_optional);
 596         if (!is_optional) {
 597           errors_.push_back(Error(prop_path, kObjectPropertyIsRequired));
 598         }
 599       }
 600     }
 601   }
 602
 603   const base::DictionaryValue* additional_properties_schema = NULL;
 604   bool allow_any_additional_properties =
 605       SchemaAllowsAnyAdditionalItems(schema, &additional_properties_schema);
 606
 607   const base::DictionaryValue* pattern_properties = NULL;
 608   ScopedVector<re2::RE2> pattern_properties_pattern;
 609   std::vector<const base::DictionaryValue*> pattern_properties_schema;
 610
 611   if (schema->GetDictionary(schema::kPatternProperties, &pattern_properties)) {
 612     for (base::DictionaryValue::Iterator it(*pattern_properties); !it.IsAtEnd();
 613          it.Advance()) {
 614       re2::RE2* prop_pattern = new re2::RE2(it.key());
 615       if (!prop_pattern->ok()) {
 616         LOG(WARNING) << "Regular expression /" << it.key()
 617                      << "/ is invalid: " << prop_pattern->error() << ".";
 618         errors_.push_back(
 619             Error(path,
 620                   FormatErrorMessage(
 621                       kInvalidRegex, it.key(), prop_pattern->error())));
 622         continue;
 623       }
 624       const base::DictionaryValue* prop_schema = NULL;
 625       CHECK(it.value().GetAsDictionary(&prop_schema));
 626       pattern_properties_pattern.push_back(prop_pattern);
 627       pattern_properties_schema.push_back(prop_schema);
 628     }
 629   }
 630
 631   // Validate pattern properties and additional properties.
 632   for (base::DictionaryValue::Iterator it(*instance); !it.IsAtEnd();
 633        it.Advance()) {
 634     std::string prop_path = path.empty() ? it.key() : path + "." + it.key();
 635
 636     bool found_matching_pattern = false;
 637     for (size_t index = 0; index < pattern_properties_pattern.size(); ++index) {
 638       if (re2::RE2::PartialMatch(it.key(),
 639                                  *pattern_properties_pattern[index])) {
 640         found_matching_pattern = true;
 641         Validate(&it.value(), pattern_properties_schema[index], prop_path);
 642         break;
 643       }
 644     }
 645
 646     if (found_matching_pattern || allow_any_additional_properties ||
 647         (properties && properties->HasKey(it.key())))
 648       continue;
 649
 650     if (!additional_properties_schema) {
 651       errors_.push_back(Error(prop_path, kUnexpectedProperty));
 652     } else {
 653       Validate(&it.value(), additional_properties_schema, prop_path);
 654     }
 655   }
 656 }
 657
 658 void JSONSchemaValidator::ValidateArray(const base::ListValue* instance,
 659                                         const base::DictionaryValue* schema,
 660                                         const std::string& path) {
 661   const base::DictionaryValue* single_type = NULL;
 662   size_t instance_size = instance->GetSize();
 663   if (schema->GetDictionary(schema::kItems, &single_type)) {
 664     int min_items = 0;
 665     if (schema->GetInteger(schema::kMinItems, &min_items)) {
 666       CHECK(min_items >= 0);
 667       if (instance_size < static_cast<size_t>(min_items)) {
 668         errors_.push_back(Error(path, FormatErrorMessage(
 669             kArrayMinItems, base::IntToString(min_items))));
 670       }
 671     }
 672
 673     int max_items = 0;
 674     if (schema->GetInteger(schema::kMaxItems, &max_items)) {
 675       CHECK(max_items >= 0);
 676       if (instance_size > static_cast<size_t>(max_items)) {
 677         errors_.push_back(Error(path, FormatErrorMessage(
 678             kArrayMaxItems, base::IntToString(max_items))));
 679       }
 680     }
 681
 682     // If the items property is a single schema, each item in the array must
 683     // validate against that schema.
 684     for (size_t i = 0; i < instance_size; ++i) {
 685       const base::Value* item = NULL;
 686       CHECK(instance->Get(i, &item));
 687       std::string i_str = base::Uint64ToString(i);
 688       std::string item_path = path.empty() ? i_str : (path + "." + i_str);
 689       Validate(item, single_type, item_path);
 690     }
 691
 692     return;
 693   }
 694
 695   // Otherwise, the list must be a tuple type, where each item in the list has a
 696   // particular schema.
 697   ValidateTuple(instance, schema, path);
 698 }
 699
 700 void JSONSchemaValidator::ValidateTuple(const base::ListValue* instance,
 701                                         const base::DictionaryValue* schema,
 702                                         const std::string& path) {
 703   const base::ListValue* tuple_type = NULL;
 704   schema->GetList(schema::kItems, &tuple_type);
 705   size_t tuple_size = tuple_type ? tuple_type->GetSize() : 0;
 706   if (tuple_type) {
 707     for (size_t i = 0; i < tuple_size; ++i) {
 708       std::string i_str = base::Uint64ToString(i);
 709       std::string item_path = path.empty() ? i_str : (path + "." + i_str);
 710       const base::DictionaryValue* item_schema = NULL;
 711       CHECK(tuple_type->GetDictionary(i, &item_schema));
 712       const base::Value* item_value = NULL;
 713       instance->Get(i, &item_value);
 714       if (item_value && item_value->GetType() != base::Value::TYPE_NULL) {
 715         Validate(item_value, item_schema, item_path);
 716       } else {
 717         bool is_optional = false;
 718         item_schema->GetBoolean(schema::kOptional, &is_optional);
 719         if (!is_optional) {
 720           errors_.push_back(Error(item_path, kArrayItemRequired));
 721           return;
 722         }
 723       }
 724     }
 725   }
 726
 727   const base::DictionaryValue* additional_properties_schema = NULL;
 728   if (SchemaAllowsAnyAdditionalItems(schema, &additional_properties_schema))
 729     return;
 730
 731   size_t instance_size = instance->GetSize();
 732   if (additional_properties_schema) {
 733     // Any additional properties must validate against the additionalProperties
 734     // schema.
 735     for (size_t i = tuple_size; i < instance_size; ++i) {
 736       std::string i_str = base::Uint64ToString(i);
 737       std::string item_path = path.empty() ? i_str : (path + "." + i_str);
 738       const base::Value* item_value = NULL;
 739       CHECK(instance->Get(i, &item_value));
 740       Validate(item_value, additional_properties_schema, item_path);
 741     }
 742   } else if (instance_size > tuple_size) {
 743     errors_.push_back(Error(path, FormatErrorMessage(
 744         kArrayMaxItems, base::Uint64ToString(tuple_size))));
 745   }
 746 }
 747
 748 void JSONSchemaValidator::ValidateString(const base::Value* instance,
 749                                          const base::DictionaryValue* schema,
 750                                          const std::string& path) {
 751   std::string value;
 752   CHECK(instance->GetAsString(&value));
 753
 754   int min_length = 0;
 755   if (schema->GetInteger(schema::kMinLength, &min_length)) {
 756     CHECK(min_length >= 0);
 757     if (value.size() < static_cast<size_t>(min_length)) {
 758       errors_.push_back(Error(path, FormatErrorMessage(
 759           kStringMinLength, base::IntToString(min_length))));
 760     }
 761   }
 762
 763   int max_length = 0;
 764   if (schema->GetInteger(schema::kMaxLength, &max_length)) {
 765     CHECK(max_length >= 0);
 766     if (value.size() > static_cast<size_t>(max_length)) {
 767       errors_.push_back(Error(path, FormatErrorMessage(
 768           kStringMaxLength, base::IntToString(max_length))));
 769     }
 770   }
 771
 772   std::string pattern;
 773   if (schema->GetString(schema::kPattern, &pattern)) {
 774     re2::RE2 compiled_regex(pattern);
 775     if (!compiled_regex.ok()) {
 776       LOG(WARNING) << "Regular expression /" << pattern
 777                    << "/ is invalid: " << compiled_regex.error() << ".";
 778       errors_.push_back(Error(
 779           path,
 780           FormatErrorMessage(kInvalidRegex, pattern, compiled_regex.error())));
 781     } else if (!re2::RE2::PartialMatch(value, compiled_regex)) {
 782       errors_.push_back(
 783           Error(path, FormatErrorMessage(kStringPattern, pattern)));
 784     }
 785   }
 786 }
 787
 788 void JSONSchemaValidator::ValidateNumber(const base::Value* instance,
 789                                          const base::DictionaryValue* schema,
 790                                          const std::string& path) {
 791   double value = GetNumberValue(instance);
 792
 793   // TODO(aa): It would be good to test that the double is not infinity or nan,
 794   // but isnan and isinf aren't defined on Windows.
 795
 796   double minimum = 0;
 797   if (schema->GetDouble(schema::kMinimum, &minimum)) {
 798     if (value < minimum)
 799       errors_.push_back(Error(path, FormatErrorMessage(
 800           kNumberMinimum, base::DoubleToString(minimum))));
 801   }
 802
 803   double maximum = 0;
 804   if (schema->GetDouble(schema::kMaximum, &maximum)) {
 805     if (value > maximum)
 806       errors_.push_back(Error(path, FormatErrorMessage(
 807           kNumberMaximum, base::DoubleToString(maximum))));
 808   }
 809 }
 810
 811 bool JSONSchemaValidator::ValidateType(const base::Value* instance,
 812                                        const std::string& expected_type,
 813                                        const std::string& path) {
 814   std::string actual_type = GetJSONSchemaType(instance);
 815   if (expected_type == actual_type ||
 816       (expected_type == schema::kNumber && actual_type == schema::kInteger)) {
 817     return true;
 818   } else if (expected_type == schema::kInteger &&
 819              actual_type == schema::kNumber) {
 820     errors_.push_back(Error(path, kInvalidTypeIntegerNumber));
 821     return false;
 822   } else {
 823     errors_.push_back(Error(path, FormatErrorMessage(
 824         kInvalidType, expected_type, actual_type)));
 825     return false;
 826   }
 827 }
 828
 829 bool JSONSchemaValidator::SchemaAllowsAnyAdditionalItems(
 830     const base::DictionaryValue* schema,
 831     const base::DictionaryValue** additional_properties_schema) {
 832   // If the validator allows additional properties globally, and this schema
 833   // doesn't override, then we can exit early.
 834   schema->GetDictionary(schema::kAdditionalProperties,
 835                         additional_properties_schema);
 836
 837   if (*additional_properties_schema) {
 838     std::string additional_properties_type(schema::kAny);
 839     CHECK((*additional_properties_schema)->GetString(
 840         schema::kType, &additional_properties_type));
 841     return additional_properties_type == schema::kAny;
 842   } else {
 843     return default_allow_additional_properties_;
 844   }
 845 }