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/policy/core/common/schema.h"
6
7#include <algorithm>
8#include <climits>
9#include <map>
10#include <utility>
11
12#include "base/compiler_specific.h"
13#include "base/logging.h"
14#include "base/memory/scoped_ptr.h"
15#include "base/memory/scoped_vector.h"
16#include "base/stl_util.h"
17#include "base/strings/stringprintf.h"
18#include "components/json_schema/json_schema_constants.h"
19#include "components/json_schema/json_schema_validator.h"
20#include "components/policy/core/common/schema_internal.h"
21#include "third_party/re2/re2/re2.h"
22
23namespace schema = json_schema_constants;
24
25namespace policy {
26
27using internal::PropertiesNode;
28using internal::PropertyNode;
29using internal::RestrictionNode;
30using internal::SchemaData;
31using internal::SchemaNode;
32
33namespace {
34
35// Maps schema "id" attributes to the corresponding SchemaNode index.
36typedef std::map<std::string, int> IdMap;
37
38// List of pairs of references to be assigned later. The string is the "id"
39// whose corresponding index should be stored in the pointer, once all the IDs
40// are available.
41typedef std::vector<std::pair<std::string, int*> > ReferenceList;
42
43// Sizes for the storage arrays. These are calculated in advance so that the
44// arrays don't have to be resized during parsing, which would invalidate
45// pointers into their contents (i.e. string's c_str() and address of indices
46// for "$ref" attributes).
47struct StorageSizes {
48  StorageSizes()
49      : strings(0), schema_nodes(0), property_nodes(0), properties_nodes(0),
50        restriction_nodes(0), int_enums(0), string_enums(0) { }
51  size_t strings;
52  size_t schema_nodes;
53  size_t property_nodes;
54  size_t properties_nodes;
55  size_t restriction_nodes;
56  size_t int_enums;
57  size_t string_enums;
58};
59
60// An invalid index, indicating that a node is not present; similar to a NULL
61// pointer.
62const int kInvalid = -1;
63
64bool SchemaTypeToValueType(const std::string& type_string,
65                           base::Value::Type* type) {
66  // Note: "any" is not an accepted type.
67  static const struct {
68    const char* schema_type;
69    base::Value::Type value_type;
70  } kSchemaToValueTypeMap[] = {
71    { schema::kArray,        base::Value::TYPE_LIST       },
72    { schema::kBoolean,      base::Value::TYPE_BOOLEAN    },
73    { schema::kInteger,      base::Value::TYPE_INTEGER    },
74    { schema::kNull,         base::Value::TYPE_NULL       },
75    { schema::kNumber,       base::Value::TYPE_DOUBLE     },
76    { schema::kObject,       base::Value::TYPE_DICTIONARY },
77    { schema::kString,       base::Value::TYPE_STRING     },
78  };
79  for (size_t i = 0; i < ARRAYSIZE_UNSAFE(kSchemaToValueTypeMap); ++i) {
80    if (kSchemaToValueTypeMap[i].schema_type == type_string) {
81      *type = kSchemaToValueTypeMap[i].value_type;
82      return true;
83    }
84  }
85  return false;
86}
87
88bool StrategyAllowInvalidOnTopLevel(SchemaOnErrorStrategy strategy) {
89  return strategy == SCHEMA_ALLOW_INVALID ||
90         strategy == SCHEMA_ALLOW_INVALID_TOPLEVEL ||
91         strategy == SCHEMA_ALLOW_INVALID_TOPLEVEL_AND_ALLOW_UNKNOWN;
92}
93
94bool StrategyAllowUnknownOnTopLevel(SchemaOnErrorStrategy strategy) {
95  return strategy != SCHEMA_STRICT;
96}
97
98SchemaOnErrorStrategy StrategyForNextLevel(SchemaOnErrorStrategy strategy) {
99  static SchemaOnErrorStrategy next_level_strategy[] = {
100    SCHEMA_STRICT,         // SCHEMA_STRICT
101    SCHEMA_STRICT,         // SCHEMA_ALLOW_UNKNOWN_TOPLEVEL
102    SCHEMA_ALLOW_UNKNOWN,  // SCHEMA_ALLOW_UNKNOWN
103    SCHEMA_STRICT,         // SCHEMA_ALLOW_INVALID_TOPLEVEL
104    SCHEMA_ALLOW_UNKNOWN,  // SCHEMA_ALLOW_INVALID_TOPLEVEL_AND_ALLOW_UNKNOWN
105    SCHEMA_ALLOW_INVALID,  // SCHEMA_ALLOW_INVALID
106  };
107  return next_level_strategy[(int)strategy];
108}
109
110void SchemaErrorFound(std::string* error_path,
111                     std::string* error,
112                     const std::string& msg) {
113  if (error_path)
114    *error_path = "";
115  *error = msg;
116}
117
118void AddListIndexPrefixToPath(int index, std::string* path) {
119  if (path) {
120    if (path->empty())
121      *path = base::StringPrintf("items[%d]", index);
122    else
123      *path = base::StringPrintf("items[%d].", index) + *path;
124  }
125}
126
127void AddDictKeyPrefixToPath(const std::string& key, std::string* path) {
128  if (path) {
129    if (path->empty())
130      *path = key;
131    else
132      *path = key + "." + *path;
133  }
134}
135
136}  // namespace
137
138// Contains the internal data representation of a Schema. This can either wrap
139// a SchemaData owned elsewhere (currently used to wrap the Chrome schema, which
140// is generated at compile time), or it can own its own SchemaData.
141class Schema::InternalStorage
142    : public base::RefCountedThreadSafe<InternalStorage> {
143 public:
144  static scoped_refptr<const InternalStorage> Wrap(const SchemaData* data);
145
146  static scoped_refptr<const InternalStorage> ParseSchema(
147      const base::DictionaryValue& schema,
148      std::string* error);
149
150  const SchemaData* data() const { return &schema_data_; }
151
152  const SchemaNode* root_node() const {
153    return schema(0);
154  }
155
156  const SchemaNode* schema(int index) const {
157    return schema_data_.schema_nodes + index;
158  }
159
160  const PropertiesNode* properties(int index) const {
161    return schema_data_.properties_nodes + index;
162  }
163
164  const PropertyNode* property(int index) const {
165    return schema_data_.property_nodes + index;
166  }
167
168  const RestrictionNode* restriction(int index) const {
169    return schema_data_.restriction_nodes + index;
170  }
171
172  const int* int_enums(int index) const {
173    return schema_data_.int_enums + index;
174  }
175
176  const char** string_enums(int index) const {
177    return schema_data_.string_enums + index;
178  }
179
180  // Compiles regular expression |pattern|. The result is cached and will be
181  // returned directly next time.
182  re2::RE2* CompileRegex(const std::string& pattern) const;
183
184 private:
185  friend class base::RefCountedThreadSafe<InternalStorage>;
186
187  InternalStorage();
188  ~InternalStorage();
189
190  // Determines the expected |sizes| of the storage for the representation
191  // of |schema|.
192  static void DetermineStorageSizes(const base::DictionaryValue& schema,
193                                   StorageSizes* sizes);
194
195  // Parses the JSON schema in |schema|.
196  //
197  // If |schema| has a "$ref" attribute then a pending reference is appended
198  // to the |reference_list|, and nothing else is done.
199  //
200  // Otherwise, |index| gets assigned the index of the corresponding SchemaNode
201  // in |schema_nodes_|. If the |schema| contains an "id" then that ID is mapped
202  // to the |index| in the |id_map|.
203  //
204  // If |schema| is invalid then |error| gets the error reason and false is
205  // returned. Otherwise returns true.
206  bool Parse(const base::DictionaryValue& schema,
207             int* index,
208             IdMap* id_map,
209             ReferenceList* reference_list,
210             std::string* error);
211
212  // Helper for Parse() that gets an already assigned |schema_node| instead of
213  // an |index| pointer.
214  bool ParseDictionary(const base::DictionaryValue& schema,
215                       SchemaNode* schema_node,
216                       IdMap* id_map,
217                       ReferenceList* reference_list,
218                       std::string* error);
219
220  // Helper for Parse() that gets an already assigned |schema_node| instead of
221  // an |index| pointer.
222  bool ParseList(const base::DictionaryValue& schema,
223                 SchemaNode* schema_node,
224                 IdMap* id_map,
225                 ReferenceList* reference_list,
226                 std::string* error);
227
228  bool ParseEnum(const base::DictionaryValue& schema,
229                 base::Value::Type type,
230                 SchemaNode* schema_node,
231                 std::string* error);
232
233  bool ParseRangedInt(const base::DictionaryValue& schema,
234                       SchemaNode* schema_node,
235                       std::string* error);
236
237  bool ParseStringPattern(const base::DictionaryValue& schema,
238                          SchemaNode* schema_node,
239                          std::string* error);
240
241  // Assigns the IDs in |id_map| to the pending references in the
242  // |reference_list|. If an ID is missing then |error| is set and false is
243  // returned; otherwise returns true.
244  static bool ResolveReferences(const IdMap& id_map,
245                                const ReferenceList& reference_list,
246                                std::string* error);
247
248  // Cache for CompileRegex(), will memorize return value of every call to
249  // CompileRegex() and return results directly next time.
250  mutable std::map<std::string, re2::RE2*> regex_cache_;
251  STLValueDeleter<std::map<std::string, re2::RE2*> > regex_cache_deleter_;
252
253  SchemaData schema_data_;
254  std::vector<std::string> strings_;
255  std::vector<SchemaNode> schema_nodes_;
256  std::vector<PropertyNode> property_nodes_;
257  std::vector<PropertiesNode> properties_nodes_;
258  std::vector<RestrictionNode> restriction_nodes_;
259  std::vector<int> int_enums_;
260  std::vector<const char*> string_enums_;
261
262  DISALLOW_COPY_AND_ASSIGN(InternalStorage);
263};
264
265Schema::InternalStorage::InternalStorage()
266    : regex_cache_deleter_(&regex_cache_) {}
267
268Schema::InternalStorage::~InternalStorage() {}
269
270// static
271scoped_refptr<const Schema::InternalStorage> Schema::InternalStorage::Wrap(
272    const SchemaData* data) {
273  InternalStorage* storage = new InternalStorage();
274  storage->schema_data_.schema_nodes = data->schema_nodes;
275  storage->schema_data_.property_nodes = data->property_nodes;
276  storage->schema_data_.properties_nodes = data->properties_nodes;
277  storage->schema_data_.restriction_nodes = data->restriction_nodes;
278  storage->schema_data_.int_enums = data->int_enums;
279  storage->schema_data_.string_enums = data->string_enums;
280  return storage;
281}
282
283// static
284scoped_refptr<const Schema::InternalStorage>
285Schema::InternalStorage::ParseSchema(const base::DictionaryValue& schema,
286                                     std::string* error) {
287  // Determine the sizes of the storage arrays and reserve the capacity before
288  // starting to append nodes and strings. This is important to prevent the
289  // arrays from being reallocated, which would invalidate the c_str() pointers
290  // and the addresses of indices to fix.
291  StorageSizes sizes;
292  DetermineStorageSizes(schema, &sizes);
293
294  scoped_refptr<InternalStorage> storage = new InternalStorage();
295  storage->strings_.reserve(sizes.strings);
296  storage->schema_nodes_.reserve(sizes.schema_nodes);
297  storage->property_nodes_.reserve(sizes.property_nodes);
298  storage->properties_nodes_.reserve(sizes.properties_nodes);
299  storage->restriction_nodes_.reserve(sizes.restriction_nodes);
300  storage->int_enums_.reserve(sizes.int_enums);
301  storage->string_enums_.reserve(sizes.string_enums);
302
303  int root_index = kInvalid;
304  IdMap id_map;
305  ReferenceList reference_list;
306  if (!storage->Parse(schema, &root_index, &id_map, &reference_list, error))
307    return NULL;
308
309  if (root_index == kInvalid) {
310    *error = "The main schema can't have a $ref";
311    return NULL;
312  }
313
314  // None of this should ever happen without having been already detected.
315  // But, if it does happen, then it will lead to corrupted memory; drop
316  // everything in that case.
317  if (root_index != 0 ||
318      sizes.strings != storage->strings_.size() ||
319      sizes.schema_nodes != storage->schema_nodes_.size() ||
320      sizes.property_nodes != storage->property_nodes_.size() ||
321      sizes.properties_nodes != storage->properties_nodes_.size() ||
322      sizes.restriction_nodes != storage->restriction_nodes_.size() ||
323      sizes.int_enums != storage->int_enums_.size() ||
324      sizes.string_enums != storage->string_enums_.size()) {
325    *error = "Failed to parse the schema due to a Chrome bug. Please file a "
326             "new issue at http://crbug.com";
327    return NULL;
328  }
329
330  if (!ResolveReferences(id_map, reference_list, error))
331    return NULL;
332
333  SchemaData* data = &storage->schema_data_;
334  data->schema_nodes = vector_as_array(&storage->schema_nodes_);
335  data->property_nodes = vector_as_array(&storage->property_nodes_);
336  data->properties_nodes = vector_as_array(&storage->properties_nodes_);
337  data->restriction_nodes = vector_as_array(&storage->restriction_nodes_);
338  data->int_enums = vector_as_array(&storage->int_enums_);
339  data->string_enums = vector_as_array(&storage->string_enums_);
340  return storage;
341}
342
343re2::RE2* Schema::InternalStorage::CompileRegex(
344    const std::string& pattern) const {
345  std::map<std::string, re2::RE2*>::iterator it = regex_cache_.find(pattern);
346  if (it == regex_cache_.end()) {
347    re2::RE2* compiled = new re2::RE2(pattern);
348    regex_cache_[pattern] = compiled;
349    return compiled;
350  }
351  return it->second;
352}
353
354// static
355void Schema::InternalStorage::DetermineStorageSizes(
356    const base::DictionaryValue& schema,
357    StorageSizes* sizes) {
358  std::string ref_string;
359  if (schema.GetString(schema::kRef, &ref_string)) {
360    // Schemas with a "$ref" attribute don't take additional storage.
361    return;
362  }
363
364  std::string type_string;
365  base::Value::Type type = base::Value::TYPE_NULL;
366  if (!schema.GetString(schema::kType, &type_string) ||
367      !SchemaTypeToValueType(type_string, &type)) {
368    // This schema is invalid.
369    return;
370  }
371
372  sizes->schema_nodes++;
373
374  if (type == base::Value::TYPE_LIST) {
375    const base::DictionaryValue* items = NULL;
376    if (schema.GetDictionary(schema::kItems, &items))
377      DetermineStorageSizes(*items, sizes);
378  } else if (type == base::Value::TYPE_DICTIONARY) {
379    sizes->properties_nodes++;
380
381    const base::DictionaryValue* dict = NULL;
382    if (schema.GetDictionary(schema::kAdditionalProperties, &dict))
383      DetermineStorageSizes(*dict, sizes);
384
385    const base::DictionaryValue* properties = NULL;
386    if (schema.GetDictionary(schema::kProperties, &properties)) {
387      for (base::DictionaryValue::Iterator it(*properties);
388           !it.IsAtEnd(); it.Advance()) {
389        // This should have been verified by the JSONSchemaValidator.
390        CHECK(it.value().GetAsDictionary(&dict));
391        DetermineStorageSizes(*dict, sizes);
392        sizes->strings++;
393        sizes->property_nodes++;
394      }
395    }
396
397    const base::DictionaryValue* pattern_properties = NULL;
398    if (schema.GetDictionary(schema::kPatternProperties, &pattern_properties)) {
399      for (base::DictionaryValue::Iterator it(*pattern_properties);
400           !it.IsAtEnd(); it.Advance()) {
401        CHECK(it.value().GetAsDictionary(&dict));
402        DetermineStorageSizes(*dict, sizes);
403        sizes->strings++;
404        sizes->property_nodes++;
405      }
406    }
407  } else if (schema.HasKey(schema::kEnum)) {
408    const base::ListValue* possible_values = NULL;
409    if (schema.GetList(schema::kEnum, &possible_values)) {
410      if (type == base::Value::TYPE_INTEGER) {
411        sizes->int_enums += possible_values->GetSize();
412      } else if (type == base::Value::TYPE_STRING) {
413        sizes->string_enums += possible_values->GetSize();
414        sizes->strings += possible_values->GetSize();
415      }
416      sizes->restriction_nodes++;
417    }
418  } else if (type == base::Value::TYPE_INTEGER) {
419    if (schema.HasKey(schema::kMinimum) || schema.HasKey(schema::kMaximum))
420      sizes->restriction_nodes++;
421  } else if (type == base::Value::TYPE_STRING) {
422    if (schema.HasKey(schema::kPattern)) {
423      sizes->strings++;
424      sizes->string_enums++;
425      sizes->restriction_nodes++;
426    }
427  }
428}
429
430bool Schema::InternalStorage::Parse(const base::DictionaryValue& schema,
431                                    int* index,
432                                    IdMap* id_map,
433                                    ReferenceList* reference_list,
434                                    std::string* error) {
435  std::string ref_string;
436  if (schema.GetString(schema::kRef, &ref_string)) {
437    std::string id_string;
438    if (schema.GetString(schema::kId, &id_string)) {
439      *error = "Schemas with a $ref can't have an id";
440      return false;
441    }
442    reference_list->push_back(std::make_pair(ref_string, index));
443    return true;
444  }
445
446  std::string type_string;
447  if (!schema.GetString(schema::kType, &type_string)) {
448    *error = "The schema type must be declared.";
449    return false;
450  }
451
452  base::Value::Type type = base::Value::TYPE_NULL;
453  if (!SchemaTypeToValueType(type_string, &type)) {
454    *error = "Type not supported: " + type_string;
455    return false;
456  }
457
458  *index = static_cast<int>(schema_nodes_.size());
459  schema_nodes_.push_back(SchemaNode());
460  SchemaNode* schema_node = &schema_nodes_.back();
461  schema_node->type = type;
462  schema_node->extra = kInvalid;
463
464  if (type == base::Value::TYPE_DICTIONARY) {
465    if (!ParseDictionary(schema, schema_node, id_map, reference_list, error))
466      return false;
467  } else if (type == base::Value::TYPE_LIST) {
468    if (!ParseList(schema, schema_node, id_map, reference_list, error))
469      return false;
470  } else if (schema.HasKey(schema::kEnum)) {
471    if (!ParseEnum(schema, type, schema_node, error))
472      return false;
473  } else if (schema.HasKey(schema::kPattern)) {
474    if (!ParseStringPattern(schema, schema_node, error))
475      return false;
476  } else if (schema.HasKey(schema::kMinimum) ||
477             schema.HasKey(schema::kMaximum)) {
478    if (type != base::Value::TYPE_INTEGER) {
479      *error = "Only integers can have minimum and maximum";
480      return false;
481    }
482    if (!ParseRangedInt(schema, schema_node, error))
483      return false;
484  }
485  std::string id_string;
486  if (schema.GetString(schema::kId, &id_string)) {
487    if (ContainsKey(*id_map, id_string)) {
488      *error = "Duplicated id: " + id_string;
489      return false;
490    }
491    (*id_map)[id_string] = *index;
492  }
493
494  return true;
495}
496
497bool Schema::InternalStorage::ParseDictionary(
498    const base::DictionaryValue& schema,
499    SchemaNode* schema_node,
500    IdMap* id_map,
501    ReferenceList* reference_list,
502    std::string* error) {
503  int extra = static_cast<int>(properties_nodes_.size());
504  properties_nodes_.push_back(PropertiesNode());
505  properties_nodes_[extra].additional = kInvalid;
506  schema_node->extra = extra;
507
508  const base::DictionaryValue* dict = NULL;
509  if (schema.GetDictionary(schema::kAdditionalProperties, &dict)) {
510    if (!Parse(*dict, &properties_nodes_[extra].additional,
511               id_map, reference_list, error)) {
512      return false;
513    }
514  }
515
516  properties_nodes_[extra].begin = static_cast<int>(property_nodes_.size());
517
518  const base::DictionaryValue* properties = NULL;
519  if (schema.GetDictionary(schema::kProperties, &properties)) {
520    // This and below reserves nodes for all of the |properties|, and makes sure
521    // they are contiguous. Recursive calls to Parse() will append after these
522    // elements.
523    property_nodes_.resize(property_nodes_.size() + properties->size());
524  }
525
526  properties_nodes_[extra].end = static_cast<int>(property_nodes_.size());
527
528  const base::DictionaryValue* pattern_properties = NULL;
529  if (schema.GetDictionary(schema::kPatternProperties, &pattern_properties))
530    property_nodes_.resize(property_nodes_.size() + pattern_properties->size());
531
532  properties_nodes_[extra].pattern_end =
533      static_cast<int>(property_nodes_.size());
534
535  if (properties != NULL) {
536    int base_index = properties_nodes_[extra].begin;
537    int index = base_index;
538
539    for (base::DictionaryValue::Iterator it(*properties);
540         !it.IsAtEnd(); it.Advance(), ++index) {
541      // This should have been verified by the JSONSchemaValidator.
542      CHECK(it.value().GetAsDictionary(&dict));
543      strings_.push_back(it.key());
544      property_nodes_[index].key = strings_.back().c_str();
545      if (!Parse(*dict, &property_nodes_[index].schema,
546                 id_map, reference_list, error)) {
547        return false;
548      }
549    }
550    CHECK_EQ(static_cast<int>(properties->size()), index - base_index);
551  }
552
553  if (pattern_properties != NULL) {
554    int base_index = properties_nodes_[extra].end;
555    int index = base_index;
556
557    for (base::DictionaryValue::Iterator it(*pattern_properties);
558         !it.IsAtEnd(); it.Advance(), ++index) {
559      CHECK(it.value().GetAsDictionary(&dict));
560      re2::RE2* compiled_regex = CompileRegex(it.key());
561      if (!compiled_regex->ok()) {
562        *error =
563            "/" + it.key() + "/ is a invalid regex: " + compiled_regex->error();
564        return false;
565      }
566      strings_.push_back(it.key());
567      property_nodes_[index].key = strings_.back().c_str();
568      if (!Parse(*dict, &property_nodes_[index].schema,
569                 id_map, reference_list, error)) {
570        return false;
571      }
572    }
573    CHECK_EQ(static_cast<int>(pattern_properties->size()), index - base_index);
574  }
575
576  if (properties_nodes_[extra].begin == properties_nodes_[extra].pattern_end) {
577    properties_nodes_[extra].begin = kInvalid;
578    properties_nodes_[extra].end = kInvalid;
579    properties_nodes_[extra].pattern_end = kInvalid;
580  }
581
582  return true;
583}
584
585bool Schema::InternalStorage::ParseList(const base::DictionaryValue& schema,
586                                        SchemaNode* schema_node,
587                                        IdMap* id_map,
588                                        ReferenceList* reference_list,
589                                        std::string* error) {
590  const base::DictionaryValue* dict = NULL;
591  if (!schema.GetDictionary(schema::kItems, &dict)) {
592    *error = "Arrays must declare a single schema for their items.";
593    return false;
594  }
595  return Parse(*dict, &schema_node->extra, id_map, reference_list, error);
596}
597
598bool Schema::InternalStorage::ParseEnum(const base::DictionaryValue& schema,
599                                        base::Value::Type type,
600                                        SchemaNode* schema_node,
601                                        std::string* error) {
602  const base::ListValue *possible_values = NULL;
603  if (!schema.GetList(schema::kEnum, &possible_values)) {
604    *error = "Enum attribute must be a list value";
605    return false;
606  }
607  if (possible_values->empty()) {
608    *error = "Enum attribute must be non-empty";
609    return false;
610  }
611  int offset_begin;
612  int offset_end;
613  if (type == base::Value::TYPE_INTEGER) {
614    offset_begin = static_cast<int>(int_enums_.size());
615    int value;
616    for (base::ListValue::const_iterator it = possible_values->begin();
617         it != possible_values->end(); ++it) {
618      if (!(*it)->GetAsInteger(&value)) {
619        *error = "Invalid enumeration member type";
620        return false;
621      }
622      int_enums_.push_back(value);
623    }
624    offset_end = static_cast<int>(int_enums_.size());
625  } else if (type == base::Value::TYPE_STRING) {
626    offset_begin = static_cast<int>(string_enums_.size());
627    std::string value;
628    for (base::ListValue::const_iterator it = possible_values->begin();
629         it != possible_values->end(); ++it) {
630      if (!(*it)->GetAsString(&value)) {
631        *error = "Invalid enumeration member type";
632        return false;
633      }
634      strings_.push_back(value);
635      string_enums_.push_back(strings_.back().c_str());
636    }
637    offset_end = static_cast<int>(string_enums_.size());
638  } else {
639    *error = "Enumeration is only supported for integer and string.";
640    return false;
641  }
642  schema_node->extra = static_cast<int>(restriction_nodes_.size());
643  restriction_nodes_.push_back(RestrictionNode());
644  restriction_nodes_.back().enumeration_restriction.offset_begin = offset_begin;
645  restriction_nodes_.back().enumeration_restriction.offset_end = offset_end;
646  return true;
647}
648
649bool Schema::InternalStorage::ParseRangedInt(
650    const base::DictionaryValue& schema,
651    SchemaNode* schema_node,
652    std::string* error) {
653  int min_value = INT_MIN;
654  int max_value = INT_MAX;
655  int value;
656  if (schema.GetInteger(schema::kMinimum, &value))
657    min_value = value;
658  if (schema.GetInteger(schema::kMaximum, &value))
659    max_value = value;
660  if (min_value > max_value) {
661    *error = "Invalid range restriction for int type.";
662    return false;
663  }
664  schema_node->extra = static_cast<int>(restriction_nodes_.size());
665  restriction_nodes_.push_back(RestrictionNode());
666  restriction_nodes_.back().ranged_restriction.max_value = max_value;
667  restriction_nodes_.back().ranged_restriction.min_value = min_value;
668  return true;
669}
670
671bool Schema::InternalStorage::ParseStringPattern(
672    const base::DictionaryValue& schema,
673    SchemaNode* schema_node,
674    std::string* error) {
675  std::string pattern;
676  if (!schema.GetString(schema::kPattern, &pattern)) {
677    *error = "Schema pattern must be a string.";
678    return false;
679  }
680  re2::RE2* compiled_regex = CompileRegex(pattern);
681  if (!compiled_regex->ok()) {
682    *error = "/" + pattern + "/ is invalid regex: " + compiled_regex->error();
683    return false;
684  }
685  int index = static_cast<int>(string_enums_.size());
686  strings_.push_back(pattern);
687  string_enums_.push_back(strings_.back().c_str());
688  schema_node->extra = static_cast<int>(restriction_nodes_.size());
689  restriction_nodes_.push_back(RestrictionNode());
690  restriction_nodes_.back().string_pattern_restriction.pattern_index = index;
691  restriction_nodes_.back().string_pattern_restriction.pattern_index_backup =
692      index;
693  return true;
694}
695
696// static
697bool Schema::InternalStorage::ResolveReferences(
698    const IdMap& id_map,
699    const ReferenceList& reference_list,
700    std::string* error) {
701  for (ReferenceList::const_iterator ref = reference_list.begin();
702       ref != reference_list.end(); ++ref) {
703    IdMap::const_iterator id = id_map.find(ref->first);
704    if (id == id_map.end()) {
705      *error = "Invalid $ref: " + ref->first;
706      return false;
707    }
708    *ref->second = id->second;
709  }
710  return true;
711}
712
713Schema::Iterator::Iterator(const scoped_refptr<const InternalStorage>& storage,
714                           const PropertiesNode* node)
715    : storage_(storage),
716      it_(storage->property(node->begin)),
717      end_(storage->property(node->end)) {}
718
719Schema::Iterator::Iterator(const Iterator& iterator)
720    : storage_(iterator.storage_),
721      it_(iterator.it_),
722      end_(iterator.end_) {}
723
724Schema::Iterator::~Iterator() {}
725
726Schema::Iterator& Schema::Iterator::operator=(const Iterator& iterator) {
727  storage_ = iterator.storage_;
728  it_ = iterator.it_;
729  end_ = iterator.end_;
730  return *this;
731}
732
733bool Schema::Iterator::IsAtEnd() const {
734  return it_ == end_;
735}
736
737void Schema::Iterator::Advance() {
738  ++it_;
739}
740
741const char* Schema::Iterator::key() const {
742  return it_->key;
743}
744
745Schema Schema::Iterator::schema() const {
746  return Schema(storage_, storage_->schema(it_->schema));
747}
748
749Schema::Schema() : node_(NULL) {}
750
751Schema::Schema(const scoped_refptr<const InternalStorage>& storage,
752               const SchemaNode* node)
753    : storage_(storage), node_(node) {}
754
755Schema::Schema(const Schema& schema)
756    : storage_(schema.storage_), node_(schema.node_) {}
757
758Schema::~Schema() {}
759
760Schema& Schema::operator=(const Schema& schema) {
761  storage_ = schema.storage_;
762  node_ = schema.node_;
763  return *this;
764}
765
766// static
767Schema Schema::Wrap(const SchemaData* data) {
768  scoped_refptr<const InternalStorage> storage = InternalStorage::Wrap(data);
769  return Schema(storage, storage->root_node());
770}
771
772bool Schema::Validate(const base::Value& value,
773                      SchemaOnErrorStrategy strategy,
774                      std::string* error_path,
775                      std::string* error) const {
776  if (!valid()) {
777    SchemaErrorFound(error_path, error, "The schema is invalid.");
778    return false;
779  }
780
781  if (!value.IsType(type())) {
782    // Allow the integer to double promotion. Note that range restriction on
783    // double is not supported now.
784    if (value.IsType(base::Value::TYPE_INTEGER) &&
785        type() == base::Value::TYPE_DOUBLE) {
786      return true;
787    }
788
789    SchemaErrorFound(
790        error_path, error, "The value type doesn't match the schema type.");
791    return false;
792  }
793
794  const base::DictionaryValue* dict = NULL;
795  const base::ListValue* list = NULL;
796  int int_value;
797  std::string str_value;
798  if (value.GetAsDictionary(&dict)) {
799    for (base::DictionaryValue::Iterator it(*dict); !it.IsAtEnd();
800         it.Advance()) {
801      SchemaList schema_list = GetMatchingProperties(it.key());
802      if (schema_list.empty()) {
803        // Unknown property was detected.
804        SchemaErrorFound(error_path, error, "Unknown property: " + it.key());
805        if (!StrategyAllowUnknownOnTopLevel(strategy))
806          return false;
807      } else {
808        for (SchemaList::iterator subschema = schema_list.begin();
809             subschema != schema_list.end(); ++subschema) {
810          if (!subschema->Validate(it.value(),
811                                   StrategyForNextLevel(strategy),
812                                   error_path,
813                                   error)) {
814            // Invalid property was detected.
815            AddDictKeyPrefixToPath(it.key(), error_path);
816            if (!StrategyAllowInvalidOnTopLevel(strategy))
817              return false;
818          }
819        }
820      }
821    }
822  } else if (value.GetAsList(&list)) {
823    for (base::ListValue::const_iterator it = list->begin(); it != list->end();
824         ++it) {
825      if (!*it ||
826          !GetItems().Validate(**it,
827                               StrategyForNextLevel(strategy),
828                               error_path,
829                               error)) {
830        // Invalid list item was detected.
831        AddListIndexPrefixToPath(it - list->begin(), error_path);
832        if (!StrategyAllowInvalidOnTopLevel(strategy))
833          return false;
834      }
835    }
836  } else if (value.GetAsInteger(&int_value)) {
837    if (node_->extra != kInvalid &&
838        !ValidateIntegerRestriction(node_->extra, int_value)) {
839      SchemaErrorFound(error_path, error, "Invalid value for integer");
840      return false;
841    }
842  } else if (value.GetAsString(&str_value)) {
843    if (node_->extra != kInvalid &&
844        !ValidateStringRestriction(node_->extra, str_value.c_str())) {
845      SchemaErrorFound(error_path, error, "Invalid value for string");
846      return false;
847    }
848  }
849
850  return true;
851}
852
853bool Schema::Normalize(base::Value* value,
854                       SchemaOnErrorStrategy strategy,
855                       std::string* error_path,
856                       std::string* error,
857                       bool* changed) const {
858  if (!valid()) {
859    SchemaErrorFound(error_path, error, "The schema is invalid.");
860    return false;
861  }
862
863  if (!value->IsType(type())) {
864    // Allow the integer to double promotion. Note that range restriction on
865    // double is not supported now.
866    if (value->IsType(base::Value::TYPE_INTEGER) &&
867        type() == base::Value::TYPE_DOUBLE) {
868      return true;
869    }
870
871    SchemaErrorFound(
872        error_path, error, "The value type doesn't match the schema type.");
873    return false;
874  }
875
876  base::DictionaryValue* dict = NULL;
877  base::ListValue* list = NULL;
878  if (value->GetAsDictionary(&dict)) {
879    std::vector<std::string> drop_list;  // Contains the keys to drop.
880    for (base::DictionaryValue::Iterator it(*dict); !it.IsAtEnd();
881         it.Advance()) {
882      SchemaList schema_list = GetMatchingProperties(it.key());
883      if (schema_list.empty()) {
884        // Unknown property was detected.
885        SchemaErrorFound(error_path, error, "Unknown property: " + it.key());
886        if (StrategyAllowUnknownOnTopLevel(strategy))
887          drop_list.push_back(it.key());
888        else
889          return false;
890      } else {
891        for (SchemaList::iterator subschema = schema_list.begin();
892             subschema != schema_list.end(); ++subschema) {
893          base::Value* sub_value = NULL;
894          dict->GetWithoutPathExpansion(it.key(), &sub_value);
895          if (!subschema->Normalize(sub_value,
896                                    StrategyForNextLevel(strategy),
897                                    error_path,
898                                    error,
899                                    changed)) {
900            // Invalid property was detected.
901            AddDictKeyPrefixToPath(it.key(), error_path);
902            if (StrategyAllowInvalidOnTopLevel(strategy)) {
903              drop_list.push_back(it.key());
904              break;
905            } else {
906              return false;
907            }
908          }
909        }
910      }
911    }
912    if (changed && !drop_list.empty())
913      *changed = true;
914    for (std::vector<std::string>::const_iterator it = drop_list.begin();
915         it != drop_list.end();
916         ++it) {
917      dict->RemoveWithoutPathExpansion(*it, NULL);
918    }
919    return true;
920  } else if (value->GetAsList(&list)) {
921    std::vector<size_t> drop_list;  // Contains the indexes to drop.
922    for (size_t index = 0; index < list->GetSize(); index++) {
923      base::Value* sub_value = NULL;
924      list->Get(index, &sub_value);
925      if (!sub_value || !GetItems().Normalize(sub_value,
926                                              StrategyForNextLevel(strategy),
927                                              error_path,
928                                              error,
929                                              changed)) {
930        // Invalid list item was detected.
931        AddListIndexPrefixToPath(index, error_path);
932        if (StrategyAllowInvalidOnTopLevel(strategy))
933          drop_list.push_back(index);
934        else
935          return false;
936      }
937    }
938    if (changed && !drop_list.empty())
939      *changed = true;
940    for (std::vector<size_t>::reverse_iterator it = drop_list.rbegin();
941         it != drop_list.rend(); ++it) {
942      list->Remove(*it, NULL);
943    }
944    return true;
945  }
946
947  return Validate(*value, strategy, error_path, error);
948}
949
950// static
951Schema Schema::Parse(const std::string& content, std::string* error) {
952  // Validate as a generic JSON schema, and ignore unknown attributes; they
953  // may become used in a future version of the schema format.
954  scoped_ptr<base::DictionaryValue> dict = JSONSchemaValidator::IsValidSchema(
955      content, JSONSchemaValidator::OPTIONS_IGNORE_UNKNOWN_ATTRIBUTES, error);
956  if (!dict)
957    return Schema();
958
959  // Validate the main type.
960  std::string string_value;
961  if (!dict->GetString(schema::kType, &string_value) ||
962      string_value != schema::kObject) {
963    *error =
964        "The main schema must have a type attribute with \"object\" value.";
965    return Schema();
966  }
967
968  // Checks for invalid attributes at the top-level.
969  if (dict->HasKey(schema::kAdditionalProperties) ||
970      dict->HasKey(schema::kPatternProperties)) {
971    *error = "\"additionalProperties\" and \"patternProperties\" are not "
972             "supported at the main schema.";
973    return Schema();
974  }
975
976  scoped_refptr<const InternalStorage> storage =
977      InternalStorage::ParseSchema(*dict, error);
978  if (!storage.get())
979    return Schema();
980  return Schema(storage, storage->root_node());
981}
982
983base::Value::Type Schema::type() const {
984  CHECK(valid());
985  return node_->type;
986}
987
988Schema::Iterator Schema::GetPropertiesIterator() const {
989  CHECK(valid());
990  CHECK_EQ(base::Value::TYPE_DICTIONARY, type());
991  return Iterator(storage_, storage_->properties(node_->extra));
992}
993
994namespace {
995
996bool CompareKeys(const PropertyNode& node, const std::string& key) {
997  return node.key < key;
998}
999
1000}  // namespace
1001
1002Schema Schema::GetKnownProperty(const std::string& key) const {
1003  CHECK(valid());
1004  CHECK_EQ(base::Value::TYPE_DICTIONARY, type());
1005  const PropertiesNode* node = storage_->properties(node_->extra);
1006  const PropertyNode* begin = storage_->property(node->begin);
1007  const PropertyNode* end = storage_->property(node->end);
1008  const PropertyNode* it = std::lower_bound(begin, end, key, CompareKeys);
1009  if (it != end && it->key == key)
1010    return Schema(storage_, storage_->schema(it->schema));
1011  return Schema();
1012}
1013
1014Schema Schema::GetAdditionalProperties() const {
1015  CHECK(valid());
1016  CHECK_EQ(base::Value::TYPE_DICTIONARY, type());
1017  const PropertiesNode* node = storage_->properties(node_->extra);
1018  if (node->additional == kInvalid)
1019    return Schema();
1020  return Schema(storage_, storage_->schema(node->additional));
1021}
1022
1023SchemaList Schema::GetPatternProperties(const std::string& key) const {
1024  CHECK(valid());
1025  CHECK_EQ(base::Value::TYPE_DICTIONARY, type());
1026  const PropertiesNode* node = storage_->properties(node_->extra);
1027  const PropertyNode* begin = storage_->property(node->end);
1028  const PropertyNode* end = storage_->property(node->pattern_end);
1029  SchemaList matching_properties;
1030  for (const PropertyNode* it = begin; it != end; ++it) {
1031    if (re2::RE2::PartialMatch(key, *storage_->CompileRegex(it->key))) {
1032      matching_properties.push_back(
1033          Schema(storage_, storage_->schema(it->schema)));
1034    }
1035  }
1036  return matching_properties;
1037}
1038
1039Schema Schema::GetProperty(const std::string& key) const {
1040  Schema schema = GetKnownProperty(key);
1041  if (schema.valid())
1042    return schema;
1043  return GetAdditionalProperties();
1044}
1045
1046SchemaList Schema::GetMatchingProperties(const std::string& key) const {
1047  SchemaList schema_list;
1048
1049  Schema known_property = GetKnownProperty(key);
1050  if (known_property.valid())
1051    schema_list.push_back(known_property);
1052
1053  SchemaList pattern_properties = GetPatternProperties(key);
1054  schema_list.insert(
1055      schema_list.end(), pattern_properties.begin(), pattern_properties.end());
1056
1057  if (schema_list.empty()) {
1058    Schema additional_property = GetAdditionalProperties();
1059    if (additional_property.valid())
1060      schema_list.push_back(additional_property);
1061  }
1062
1063  return schema_list;
1064}
1065
1066Schema Schema::GetItems() const {
1067  CHECK(valid());
1068  CHECK_EQ(base::Value::TYPE_LIST, type());
1069  if (node_->extra == kInvalid)
1070    return Schema();
1071  return Schema(storage_, storage_->schema(node_->extra));
1072}
1073
1074bool Schema::ValidateIntegerRestriction(int index, int value) const {
1075  const RestrictionNode* rnode = storage_->restriction(index);
1076  if (rnode->ranged_restriction.min_value <=
1077      rnode->ranged_restriction.max_value) {
1078    return rnode->ranged_restriction.min_value <= value &&
1079           rnode->ranged_restriction.max_value >= value;
1080  } else {
1081    for (int i = rnode->enumeration_restriction.offset_begin;
1082         i < rnode->enumeration_restriction.offset_end; ++i) {
1083      if (*storage_->int_enums(i) == value)
1084        return true;
1085    }
1086    return false;
1087  }
1088}
1089
1090bool Schema::ValidateStringRestriction(int index, const char* str) const {
1091  const RestrictionNode* rnode = storage_->restriction(index);
1092  if (rnode->enumeration_restriction.offset_begin <
1093      rnode->enumeration_restriction.offset_end) {
1094    for (int i = rnode->enumeration_restriction.offset_begin;
1095         i < rnode->enumeration_restriction.offset_end; ++i) {
1096      if (strcmp(*storage_->string_enums(i), str) == 0)
1097        return true;
1098    }
1099    return false;
1100  } else {
1101    int index = rnode->string_pattern_restriction.pattern_index;
1102    DCHECK(index == rnode->string_pattern_restriction.pattern_index_backup);
1103    re2::RE2* regex = storage_->CompileRegex(*storage_->string_enums(index));
1104    return re2::RE2::PartialMatch(str, *regex);
1105  }
1106}
1107
1108}  // namespace policy
1109