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
22namespace schema = json_schema_constants;
23
24namespace {
25
26double 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
33bool 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.
49struct ExpectedType {
50  const char* key;
51  base::Value::Type type;
52};
53
54// Helper for std::lower_bound.
55bool 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|.
61const 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
71bool 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
293JSONSchemaValidator::Error::Error() {
294}
295
296JSONSchemaValidator::Error::Error(const std::string& message)
297    : path(message) {
298}
299
300JSONSchemaValidator::Error::Error(const std::string& path,
301                                  const std::string& message)
302    : path(path), message(message) {
303}
304
305
306const char JSONSchemaValidator::kUnknownTypeReference[] =
307    "Unknown schema reference: *.";
308const char JSONSchemaValidator::kInvalidChoice[] =
309    "Value does not match any valid type choices.";
310const char JSONSchemaValidator::kInvalidEnum[] =
311    "Value does not match any valid enum choices.";
312const char JSONSchemaValidator::kObjectPropertyIsRequired[] =
313    "Property is required.";
314const char JSONSchemaValidator::kUnexpectedProperty[] =
315    "Unexpected property.";
316const char JSONSchemaValidator::kArrayMinItems[] =
317    "Array must have at least * items.";
318const char JSONSchemaValidator::kArrayMaxItems[] =
319    "Array must not have more than * items.";
320const char JSONSchemaValidator::kArrayItemRequired[] =
321    "Item is required.";
322const char JSONSchemaValidator::kStringMinLength[] =
323    "String must be at least * characters long.";
324const char JSONSchemaValidator::kStringMaxLength[] =
325    "String must not be more than * characters long.";
326const char JSONSchemaValidator::kStringPattern[] =
327    "String must match the pattern: *.";
328const char JSONSchemaValidator::kNumberMinimum[] =
329    "Value must not be less than *.";
330const char JSONSchemaValidator::kNumberMaximum[] =
331    "Value must not be greater than *.";
332const char JSONSchemaValidator::kInvalidType[] =
333    "Expected '*' but got '*'.";
334const char JSONSchemaValidator::kInvalidTypeIntegerNumber[] =
335    "Expected 'integer' but got 'number', consider using Math.round().";
336const char JSONSchemaValidator::kInvalidRegex[] =
337    "Regular expression /*/ is invalid: *";
338
339
340// static
341std::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
372std::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
380std::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
390scoped_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
397scoped_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
417JSONSchemaValidator::JSONSchemaValidator(base::DictionaryValue* schema)
418    : schema_root_(schema), default_allow_additional_properties_(false) {
419}
420
421JSONSchemaValidator::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
439JSONSchemaValidator::~JSONSchemaValidator() {}
440
441bool JSONSchemaValidator::Validate(const base::Value* instance) {
442  errors_.clear();
443  Validate(instance, schema_root_, std::string());
444  return errors_.empty();
445}
446
447void 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
517void 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
540void 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
577void 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
658void 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
700void 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
748void 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
788void 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
811bool 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
829bool 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}
846