src/components/policy/core/common/schema.cc

   1 // Copyright 2013 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "components/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
  23 namespace schema = json_schema_constants;
  24
  25 namespace policy {
  26
  27 using internal::PropertiesNode;
  28 using internal::PropertyNode;
  29 using internal::RestrictionNode;
  30 using internal::SchemaData;
  31 using internal::SchemaNode;
  32
  33 namespace {
  34
  35 // Maps schema "id" attributes to the corresponding SchemaNode index.
  36 typedef 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.
  41 typedef 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).
  47 struct 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.
  62 const int kInvalid = -1;
  63
  64 bool 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
  88 bool 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
  94 bool StrategyAllowUnknownOnTopLevel(SchemaOnErrorStrategy strategy) {
  95   return strategy != SCHEMA_STRICT;
  96 }
  97
  98 SchemaOnErrorStrategy 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
 110 void 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
 118 void 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
 127 void 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.
 141 class 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
 265 Schema::InternalStorage::InternalStorage()
 266     : regex_cache_deleter_(&regex_cache_) {}
 267
 268 Schema::InternalStorage::~InternalStorage() {}
 269
 270 // static
 271 scoped_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
 284 scoped_refptr<const Schema::InternalStorage>
 285 Schema::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
 343 re2::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
 355 void 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
 430 bool 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
 497 bool 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
 585 bool 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
 598 bool 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
 649 bool 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
 671 bool 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
 697 bool 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
 713 Schema::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
 719 Schema::Iterator::Iterator(const Iterator& iterator)
 720     : storage_(iterator.storage_),
 721       it_(iterator.it_),
 722       end_(iterator.end_) {}
 723
 724 Schema::Iterator::~Iterator() {}
 725
 726 Schema::Iterator& Schema::Iterator::operator=(const Iterator& iterator) {
 727   storage_ = iterator.storage_;
 728   it_ = iterator.it_;
 729   end_ = iterator.end_;
 730   return *this;
 731 }
 732
 733 bool Schema::Iterator::IsAtEnd() const {
 734   return it_ == end_;
 735 }
 736
 737 void Schema::Iterator::Advance() {
 738   ++it_;
 739 }
 740
 741 const char* Schema::Iterator::key() const {
 742   return it_->key;
 743 }
 744
 745 Schema Schema::Iterator::schema() const {
 746   return Schema(storage_, storage_->schema(it_->schema));
 747 }
 748
 749 Schema::Schema() : node_(NULL) {}
 750
 751 Schema::Schema(const scoped_refptr<const InternalStorage>& storage,
 752                const SchemaNode* node)
 753     : storage_(storage), node_(node) {}
 754
 755 Schema::Schema(const Schema& schema)
 756     : storage_(schema.storage_), node_(schema.node_) {}
 757
 758 Schema::~Schema() {}
 759
 760 Schema& Schema::operator=(const Schema& schema) {
 761   storage_ = schema.storage_;
 762   node_ = schema.node_;
 763   return *this;
 764 }
 765
 766 // static
 767 Schema Schema::Wrap(const SchemaData* data) {
 768   scoped_refptr<const InternalStorage> storage = InternalStorage::Wrap(data);
 769   return Schema(storage, storage->root_node());
 770 }
 771
 772 bool 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
 853 bool 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
 951 Schema 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
 983 base::Value::Type Schema::type() const {
 984   CHECK(valid());
 985   return node_->type;
 986 }
 987
 988 Schema::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
 994 namespace {
 995
 996 bool CompareKeys(const PropertyNode& node, const std::string& key) {
 997   return node.key < key;
 998 }
 999
1000 }  // namespace
1001
1002 Schema 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
1014 Schema 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
1023 SchemaList 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
1039 Schema Schema::GetProperty(const std::string& key) const {
1040   Schema schema = GetKnownProperty(key);
1041   if (schema.valid())
1042     return schema;
1043   return GetAdditionalProperties();
1044 }
1045
1046 SchemaList 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
1066 Schema 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
1074 bool 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
1090 bool 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