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