1// Copyright (c) 2010 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 "chrome/common/json_schema_validator.h"
6
7#include <cfloat>
8#include <cmath>
9
10#include "base/string_number_conversions.h"
11#include "base/string_util.h"
12#include "base/values.h"
13#include "ui/base/l10n/l10n_util.h"
14
15namespace {
16
17double GetNumberValue(Value* value) {
18  double result = 0;
19  if (value->GetAsDouble(&result))
20    return result;
21
22  int int_result = 0;
23  if (value->GetAsInteger(&int_result)) {
24    return int_result;
25  }
26
27  CHECK(false) << "Unexpected value type: " << value->GetType();
28  return 0;
29}
30
31bool GetNumberFromDictionary(DictionaryValue* value, const std::string& key,
32                             double* number) {
33  if (value->GetDouble(key, number))
34    return true;
35
36  int int_value = 0;
37  if (value->GetInteger(key, &int_value)) {
38    *number = int_value;
39    return true;
40  }
41
42  return false;
43}
44
45}  // namespace
46
47
48JSONSchemaValidator::Error::Error() {
49}
50
51JSONSchemaValidator::Error::Error(const std::string& message)
52    : path(message) {
53}
54
55JSONSchemaValidator::Error::Error(const std::string& path,
56                                  const std::string& message)
57    : path(path), message(message) {
58}
59
60
61const char JSONSchemaValidator::kUnknownTypeReference[] =
62    "Unknown schema reference: *.";
63const char JSONSchemaValidator::kInvalidChoice[] =
64    "Value does not match any valid type choices.";
65const char JSONSchemaValidator::kInvalidEnum[] =
66    "Value does not match any valid enum choices.";
67const char JSONSchemaValidator::kObjectPropertyIsRequired[] =
68    "Property is required.";
69const char JSONSchemaValidator::kUnexpectedProperty[] =
70    "Unexpected property.";
71const char JSONSchemaValidator::kArrayMinItems[] =
72    "Array must have at least * items.";
73const char JSONSchemaValidator::kArrayMaxItems[] =
74    "Array must not have more than * items.";
75const char JSONSchemaValidator::kArrayItemRequired[] =
76    "Item is required.";
77const char JSONSchemaValidator::kStringMinLength[] =
78    "String must be at least * characters long.";
79const char JSONSchemaValidator::kStringMaxLength[] =
80    "String must not be more than * characters long.";
81const char JSONSchemaValidator::kStringPattern[] =
82    "String must match the pattern: *.";
83const char JSONSchemaValidator::kNumberMinimum[] =
84    "Value must not be less than *.";
85const char JSONSchemaValidator::kNumberMaximum[] =
86    "Value must not be greater than *.";
87const char JSONSchemaValidator::kInvalidType[] =
88    "Expected '*' but got '*'.";
89
90
91// static
92std::string JSONSchemaValidator::GetJSONSchemaType(Value* value) {
93  switch (value->GetType()) {
94    case Value::TYPE_NULL:
95      return "null";
96    case Value::TYPE_BOOLEAN:
97      return "boolean";
98    case Value::TYPE_INTEGER:
99      return "integer";
100    case Value::TYPE_DOUBLE: {
101      double double_value = 0;
102      value->GetAsDouble(&double_value);
103      if (std::abs(double_value) <= std::pow(2.0, DBL_MANT_DIG) &&
104          double_value == floor(double_value)) {
105        return "integer";
106      } else {
107        return "number";
108      }
109    }
110    case Value::TYPE_STRING:
111      return "string";
112    case Value::TYPE_DICTIONARY:
113      return "object";
114    case Value::TYPE_LIST:
115      return "array";
116    default:
117      CHECK(false) << "Unexpected value type: " << value->GetType();
118      return "";
119  }
120}
121
122// static
123std::string JSONSchemaValidator::FormatErrorMessage(const std::string& format,
124                                                    const std::string& s1) {
125  std::string ret_val = format;
126  ReplaceFirstSubstringAfterOffset(&ret_val, 0, "*", s1);
127  return ret_val;
128}
129
130// static
131std::string JSONSchemaValidator::FormatErrorMessage(const std::string& format,
132                                                    const std::string& s1,
133                                                    const std::string& s2) {
134  std::string ret_val = format;
135  ReplaceFirstSubstringAfterOffset(&ret_val, 0, "*", s1);
136  ReplaceFirstSubstringAfterOffset(&ret_val, 0, "*", s2);
137  return ret_val;
138}
139
140JSONSchemaValidator::JSONSchemaValidator(DictionaryValue* schema)
141    : schema_root_(schema), default_allow_additional_properties_(false) {
142}
143
144JSONSchemaValidator::JSONSchemaValidator(DictionaryValue* schema,
145                                         ListValue* types)
146    : schema_root_(schema), default_allow_additional_properties_(false) {
147  if (!types)
148    return;
149
150  for (size_t i = 0; i < types->GetSize(); ++i) {
151    DictionaryValue* type = NULL;
152    CHECK(types->GetDictionary(i, &type));
153
154    std::string id;
155    CHECK(type->GetString("id", &id));
156
157    CHECK(types_.find(id) == types_.end());
158    types_[id] = type;
159  }
160}
161
162JSONSchemaValidator::~JSONSchemaValidator() {}
163
164bool JSONSchemaValidator::Validate(Value* instance) {
165  errors_.clear();
166  Validate(instance, schema_root_, "");
167  return errors_.empty();
168}
169
170void JSONSchemaValidator::Validate(Value* instance,
171                                   DictionaryValue* schema,
172                                   const std::string& path) {
173  // If this schema defines itself as reference type, save it in this.types.
174  std::string id;
175  if (schema->GetString("id", &id)) {
176    TypeMap::iterator iter = types_.find(id);
177    if (iter == types_.end())
178      types_[id] = schema;
179    else
180      CHECK(iter->second == schema);
181  }
182
183  // If the schema has a $ref property, the instance must validate against
184  // that schema. It must be present in types_ to be referenced.
185  std::string ref;
186  if (schema->GetString("$ref", &ref)) {
187    TypeMap::iterator type = types_.find(ref);
188    if (type == types_.end()) {
189      errors_.push_back(
190          Error(path, FormatErrorMessage(kUnknownTypeReference, ref)));
191    } else {
192      Validate(instance, type->second, path);
193    }
194    return;
195  }
196
197  // If the schema has a choices property, the instance must validate against at
198  // least one of the items in that array.
199  ListValue* choices = NULL;
200  if (schema->GetList("choices", &choices)) {
201    ValidateChoices(instance, choices, path);
202    return;
203  }
204
205  // If the schema has an enum property, the instance must be one of those
206  // values.
207  ListValue* enumeration = NULL;
208  if (schema->GetList("enum", &enumeration)) {
209    ValidateEnum(instance, enumeration, path);
210    return;
211  }
212
213  std::string type;
214  schema->GetString("type", &type);
215  CHECK(!type.empty());
216  if (type != "any") {
217    if (!ValidateType(instance, type, path))
218      return;
219
220    // These casts are safe because of checks in ValidateType().
221    if (type == "object")
222      ValidateObject(static_cast<DictionaryValue*>(instance), schema, path);
223    else if (type == "array")
224      ValidateArray(static_cast<ListValue*>(instance), schema, path);
225    else if (type == "string")
226      ValidateString(static_cast<StringValue*>(instance), schema, path);
227    else if (type == "number" || type == "integer")
228      ValidateNumber(instance, schema, path);
229    else if (type != "boolean" && type != "null")
230      CHECK(false) << "Unexpected type: " << type;
231  }
232}
233
234void JSONSchemaValidator::ValidateChoices(Value* instance,
235                                          ListValue* choices,
236                                          const std::string& path) {
237  size_t original_num_errors = errors_.size();
238
239  for (size_t i = 0; i < choices->GetSize(); ++i) {
240    DictionaryValue* choice = NULL;
241    CHECK(choices->GetDictionary(i, &choice));
242
243    Validate(instance, choice, path);
244    if (errors_.size() == original_num_errors)
245      return;
246
247    // We discard the error from each choice. We only want to know if any of the
248    // validations succeeded.
249    errors_.resize(original_num_errors);
250  }
251
252  // Now add a generic error that no choices matched.
253  errors_.push_back(Error(path, kInvalidChoice));
254  return;
255}
256
257void JSONSchemaValidator::ValidateEnum(Value* instance,
258                                       ListValue* choices,
259                                       const std::string& path) {
260  for (size_t i = 0; i < choices->GetSize(); ++i) {
261    Value* choice = NULL;
262    CHECK(choices->Get(i, &choice));
263    switch (choice->GetType()) {
264      case Value::TYPE_NULL:
265      case Value::TYPE_BOOLEAN:
266      case Value::TYPE_STRING:
267        if (instance->Equals(choice))
268          return;
269        break;
270
271      case Value::TYPE_INTEGER:
272      case Value::TYPE_DOUBLE:
273        if (instance->IsType(Value::TYPE_INTEGER) ||
274            instance->IsType(Value::TYPE_DOUBLE)) {
275          if (GetNumberValue(choice) == GetNumberValue(instance))
276            return;
277        }
278        break;
279
280      default:
281        CHECK(false) << "Unexpected type in enum: " << choice->GetType();
282    }
283  }
284
285  errors_.push_back(Error(path, kInvalidEnum));
286}
287
288void JSONSchemaValidator::ValidateObject(DictionaryValue* instance,
289                                         DictionaryValue* schema,
290                                         const std::string& path) {
291  DictionaryValue* properties = NULL;
292  schema->GetDictionary("properties", &properties);
293  if (properties) {
294    for (DictionaryValue::key_iterator key = properties->begin_keys();
295         key != properties->end_keys(); ++key) {
296      std::string prop_path = path.empty() ? *key : (path + "." + *key);
297      DictionaryValue* prop_schema = NULL;
298      CHECK(properties->GetDictionary(*key, &prop_schema));
299
300      Value* prop_value = NULL;
301      if (instance->Get(*key, &prop_value)) {
302        Validate(prop_value, prop_schema, prop_path);
303      } else {
304        // Properties are required unless there is an optional field set to
305        // 'true'.
306        bool is_optional = false;
307        prop_schema->GetBoolean("optional", &is_optional);
308        if (!is_optional) {
309          errors_.push_back(Error(prop_path, kObjectPropertyIsRequired));
310        }
311      }
312    }
313  }
314
315  DictionaryValue* additional_properties_schema = NULL;
316  if (SchemaAllowsAnyAdditionalItems(schema, &additional_properties_schema))
317    return;
318
319  // Validate additional properties.
320  for (DictionaryValue::key_iterator key = instance->begin_keys();
321       key != instance->end_keys(); ++key) {
322    if (properties && properties->HasKey(*key))
323      continue;
324
325    std::string prop_path = path.empty() ? *key : path + "." + *key;
326    if (!additional_properties_schema) {
327      errors_.push_back(Error(prop_path, kUnexpectedProperty));
328    } else {
329      Value* prop_value = NULL;
330      CHECK(instance->Get(*key, &prop_value));
331      Validate(prop_value, additional_properties_schema, prop_path);
332    }
333  }
334}
335
336void JSONSchemaValidator::ValidateArray(ListValue* instance,
337                                        DictionaryValue* schema,
338                                        const std::string& path) {
339  DictionaryValue* single_type = NULL;
340  size_t instance_size = instance->GetSize();
341  if (schema->GetDictionary("items", &single_type)) {
342    int min_items = 0;
343    if (schema->GetInteger("minItems", &min_items)) {
344      CHECK(min_items >= 0);
345      if (instance_size < static_cast<size_t>(min_items)) {
346        errors_.push_back(Error(path, FormatErrorMessage(
347            kArrayMinItems, base::IntToString(min_items))));
348      }
349    }
350
351    int max_items = 0;
352    if (schema->GetInteger("maxItems", &max_items)) {
353      CHECK(max_items >= 0);
354      if (instance_size > static_cast<size_t>(max_items)) {
355        errors_.push_back(Error(path, FormatErrorMessage(
356            kArrayMaxItems, base::IntToString(max_items))));
357      }
358    }
359
360    // If the items property is a single schema, each item in the array must
361    // validate against that schema.
362    for (size_t i = 0; i < instance_size; ++i) {
363      Value* item = NULL;
364      CHECK(instance->Get(i, &item));
365      std::string i_str = base::UintToString(i);
366      std::string item_path = path.empty() ? i_str : (path + "." + i_str);
367      Validate(item, single_type, item_path);
368    }
369
370    return;
371  }
372
373  // Otherwise, the list must be a tuple type, where each item in the list has a
374  // particular schema.
375  ValidateTuple(instance, schema, path);
376}
377
378void JSONSchemaValidator::ValidateTuple(ListValue* instance,
379                                        DictionaryValue* schema,
380                                        const std::string& path) {
381  ListValue* tuple_type = NULL;
382  schema->GetList("items", &tuple_type);
383  size_t tuple_size = tuple_type ? tuple_type->GetSize() : 0;
384  if (tuple_type) {
385    for (size_t i = 0; i < tuple_size; ++i) {
386      std::string i_str = base::UintToString(i);
387      std::string item_path = path.empty() ? i_str : (path + "." + i_str);
388      DictionaryValue* item_schema = NULL;
389      CHECK(tuple_type->GetDictionary(i, &item_schema));
390      Value* item_value = NULL;
391      instance->Get(i, &item_value);
392      if (item_value && item_value->GetType() != Value::TYPE_NULL) {
393        Validate(item_value, item_schema, item_path);
394      } else {
395        bool is_optional = false;
396        item_schema->GetBoolean("optional", &is_optional);
397        if (!is_optional) {
398          errors_.push_back(Error(item_path, kArrayItemRequired));
399          return;
400        }
401      }
402    }
403  }
404
405  DictionaryValue* additional_properties_schema = NULL;
406  if (SchemaAllowsAnyAdditionalItems(schema, &additional_properties_schema))
407    return;
408
409  size_t instance_size = instance->GetSize();
410  if (additional_properties_schema) {
411    // Any additional properties must validate against the additionalProperties
412    // schema.
413    for (size_t i = tuple_size; i < instance_size; ++i) {
414      std::string i_str = base::UintToString(i);
415      std::string item_path = path.empty() ? i_str : (path + "." + i_str);
416      Value* item_value = NULL;
417      CHECK(instance->Get(i, &item_value));
418      Validate(item_value, additional_properties_schema, item_path);
419    }
420  } else if (instance_size > tuple_size) {
421    errors_.push_back(Error(path, FormatErrorMessage(
422        kArrayMaxItems, base::UintToString(tuple_size))));
423  }
424}
425
426void JSONSchemaValidator::ValidateString(StringValue* instance,
427                                         DictionaryValue* schema,
428                                         const std::string& path) {
429  std::string value;
430  CHECK(instance->GetAsString(&value));
431
432  int min_length = 0;
433  if (schema->GetInteger("minLength", &min_length)) {
434    CHECK(min_length >= 0);
435    if (value.size() < static_cast<size_t>(min_length)) {
436      errors_.push_back(Error(path, FormatErrorMessage(
437          kStringMinLength, base::IntToString(min_length))));
438    }
439  }
440
441  int max_length = 0;
442  if (schema->GetInteger("maxLength", &max_length)) {
443    CHECK(max_length >= 0);
444    if (value.size() > static_cast<size_t>(max_length)) {
445      errors_.push_back(Error(path, FormatErrorMessage(
446          kStringMaxLength, base::IntToString(max_length))));
447    }
448  }
449
450  CHECK(!schema->HasKey("pattern")) << "Pattern is not supported.";
451}
452
453void JSONSchemaValidator::ValidateNumber(Value* instance,
454                                         DictionaryValue* schema,
455                                         const std::string& path) {
456  double value = GetNumberValue(instance);
457
458  // TODO(aa): It would be good to test that the double is not infinity or nan,
459  // but isnan and isinf aren't defined on Windows.
460
461  double minimum = 0;
462  if (GetNumberFromDictionary(schema, "minimum", &minimum)) {
463    if (value < minimum)
464      errors_.push_back(Error(path, FormatErrorMessage(
465          kNumberMinimum, base::DoubleToString(minimum))));
466  }
467
468  double maximum = 0;
469  if (GetNumberFromDictionary(schema, "maximum", &maximum)) {
470    if (value > maximum)
471      errors_.push_back(Error(path, FormatErrorMessage(
472          kNumberMaximum, base::DoubleToString(maximum))));
473  }
474}
475
476bool JSONSchemaValidator::ValidateType(Value* instance,
477                                       const std::string& expected_type,
478                                       const std::string& path) {
479  std::string actual_type = GetJSONSchemaType(instance);
480  if (expected_type == actual_type ||
481      (expected_type == "number" && actual_type == "integer")) {
482    return true;
483  } else {
484    errors_.push_back(Error(path, FormatErrorMessage(
485        kInvalidType, expected_type, actual_type)));
486    return false;
487  }
488}
489
490bool JSONSchemaValidator::SchemaAllowsAnyAdditionalItems(
491    DictionaryValue* schema, DictionaryValue** additional_properties_schema) {
492  // If the validator allows additional properties globally, and this schema
493  // doesn't override, then we can exit early.
494  schema->GetDictionary("additionalProperties", additional_properties_schema);
495
496  if (*additional_properties_schema) {
497    std::string additional_properties_type("any");
498    CHECK((*additional_properties_schema)->GetString(
499        "type", &additional_properties_type));
500    return additional_properties_type == "any";
501  } else {
502    return default_allow_additional_properties_;
503  }
504}
505