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/memory/scoped_vector.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(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[static_cast<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 base::ScopedPtrMap<std::string, scoped_ptr<re2::RE2>> regex_cache_;
 251
 252   SchemaData schema_data_;
 253   std::vector<std::string> strings_;
 254   std::vector<SchemaNode> schema_nodes_;
 255   std::vector<PropertyNode> property_nodes_;
 256   std::vector<PropertiesNode> properties_nodes_;
 257   std::vector<RestrictionNode> restriction_nodes_;
 258   std::vector<int> int_enums_;
 259   std::vector<const char*> string_enums_;
 260
 261   DISALLOW_COPY_AND_ASSIGN(InternalStorage);
 262 };
 263
 264 Schema::InternalStorage::InternalStorage() {
 265 }
 266
 267 Schema::InternalStorage::~InternalStorage() {
 268 }
 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   base::ScopedPtrMap<std::string, scoped_ptr<re2::RE2>>::const_iterator it =
 346       regex_cache_.find(pattern);
 347   if (it == regex_cache_.end()) {
 348     scoped_ptr<re2::RE2> compiled(new re2::RE2(pattern));
 349     re2::RE2* compiled_ptr = compiled.get();
 350     regex_cache_.insert(pattern, compiled.Pass());
 351     return compiled_ptr;
 352   }
 353   return it->second;
 354 }
 355
 356 // static
 357 void Schema::InternalStorage::DetermineStorageSizes(
 358     const base::DictionaryValue& schema,
 359     StorageSizes* sizes) {
 360   std::string ref_string;
 361   if (schema.GetString(schema::kRef, &ref_string)) {
 362     // Schemas with a "$ref" attribute don't take additional storage.
 363     return;
 364   }
 365
 366   std::string type_string;
 367   base::Value::Type type = base::Value::TYPE_NULL;
 368   if (!schema.GetString(schema::kType, &type_string) ||
 369       !SchemaTypeToValueType(type_string, &type)) {
 370     // This schema is invalid.
 371     return;
 372   }
 373
 374   sizes->schema_nodes++;
 375
 376   if (type == base::Value::TYPE_LIST) {
 377     const base::DictionaryValue* items = NULL;
 378     if (schema.GetDictionary(schema::kItems, &items))
 379       DetermineStorageSizes(*items, sizes);
 380   } else if (type == base::Value::TYPE_DICTIONARY) {
 381     sizes->properties_nodes++;
 382
 383     const base::DictionaryValue* dict = NULL;
 384     if (schema.GetDictionary(schema::kAdditionalProperties, &dict))
 385       DetermineStorageSizes(*dict, sizes);
 386
 387     const base::DictionaryValue* properties = NULL;
 388     if (schema.GetDictionary(schema::kProperties, &properties)) {
 389       for (base::DictionaryValue::Iterator it(*properties);
 390            !it.IsAtEnd(); it.Advance()) {
 391         // This should have been verified by the JSONSchemaValidator.
 392         CHECK(it.value().GetAsDictionary(&dict));
 393         DetermineStorageSizes(*dict, sizes);
 394         sizes->strings++;
 395         sizes->property_nodes++;
 396       }
 397     }
 398
 399     const base::DictionaryValue* pattern_properties = NULL;
 400     if (schema.GetDictionary(schema::kPatternProperties, &pattern_properties)) {
 401       for (base::DictionaryValue::Iterator it(*pattern_properties);
 402            !it.IsAtEnd(); it.Advance()) {
 403         CHECK(it.value().GetAsDictionary(&dict));
 404         DetermineStorageSizes(*dict, sizes);
 405         sizes->strings++;
 406         sizes->property_nodes++;
 407       }
 408     }
 409   } else if (schema.HasKey(schema::kEnum)) {
 410     const base::ListValue* possible_values = NULL;
 411     if (schema.GetList(schema::kEnum, &possible_values)) {
 412       if (type == base::Value::TYPE_INTEGER) {
 413         sizes->int_enums += possible_values->GetSize();
 414       } else if (type == base::Value::TYPE_STRING) {
 415         sizes->string_enums += possible_values->GetSize();
 416         sizes->strings += possible_values->GetSize();
 417       }
 418       sizes->restriction_nodes++;
 419     }
 420   } else if (type == base::Value::TYPE_INTEGER) {
 421     if (schema.HasKey(schema::kMinimum) || schema.HasKey(schema::kMaximum))
 422       sizes->restriction_nodes++;
 423   } else if (type == base::Value::TYPE_STRING) {
 424     if (schema.HasKey(schema::kPattern)) {
 425       sizes->strings++;
 426       sizes->string_enums++;
 427       sizes->restriction_nodes++;
 428     }
 429   }
 430 }
 431
 432 bool Schema::InternalStorage::Parse(const base::DictionaryValue& schema,
 433                                     int* index,
 434                                     IdMap* id_map,
 435                                     ReferenceList* reference_list,
 436                                     std::string* error) {
 437   std::string ref_string;
 438   if (schema.GetString(schema::kRef, &ref_string)) {
 439     std::string id_string;
 440     if (schema.GetString(schema::kId, &id_string)) {
 441       *error = "Schemas with a $ref can't have an id";
 442       return false;
 443     }
 444     reference_list->push_back(std::make_pair(ref_string, index));
 445     return true;
 446   }
 447
 448   std::string type_string;
 449   if (!schema.GetString(schema::kType, &type_string)) {
 450     *error = "The schema type must be declared.";
 451     return false;
 452   }
 453
 454   base::Value::Type type = base::Value::TYPE_NULL;
 455   if (!SchemaTypeToValueType(type_string, &type)) {
 456     *error = "Type not supported: " + type_string;
 457     return false;
 458   }
 459
 460   *index = static_cast<int>(schema_nodes_.size());
 461   schema_nodes_.push_back(SchemaNode());
 462   SchemaNode* schema_node = &schema_nodes_.back();
 463   schema_node->type = type;
 464   schema_node->extra = kInvalid;
 465
 466   if (type == base::Value::TYPE_DICTIONARY) {
 467     if (!ParseDictionary(schema, schema_node, id_map, reference_list, error))
 468       return false;
 469   } else if (type == base::Value::TYPE_LIST) {
 470     if (!ParseList(schema, schema_node, id_map, reference_list, error))
 471       return false;
 472   } else if (schema.HasKey(schema::kEnum)) {
 473     if (!ParseEnum(schema, type, schema_node, error))
 474       return false;
 475   } else if (schema.HasKey(schema::kPattern)) {
 476     if (!ParseStringPattern(schema, schema_node, error))
 477       return false;
 478   } else if (schema.HasKey(schema::kMinimum) ||
 479              schema.HasKey(schema::kMaximum)) {
 480     if (type != base::Value::TYPE_INTEGER) {
 481       *error = "Only integers can have minimum and maximum";
 482       return false;
 483     }
 484     if (!ParseRangedInt(schema, schema_node, error))
 485       return false;
 486   }
 487   std::string id_string;
 488   if (schema.GetString(schema::kId, &id_string)) {
 489     if (ContainsKey(*id_map, id_string)) {
 490       *error = "Duplicated id: " + id_string;
 491       return false;
 492     }
 493     (*id_map)[id_string] = *index;
 494   }
 495
 496   return true;
 497 }
 498
 499 bool Schema::InternalStorage::ParseDictionary(
 500     const base::DictionaryValue& schema,
 501     SchemaNode* schema_node,
 502     IdMap* id_map,
 503     ReferenceList* reference_list,
 504     std::string* error) {
 505   int extra = static_cast<int>(properties_nodes_.size());
 506   properties_nodes_.push_back(PropertiesNode());
 507   properties_nodes_[extra].additional = kInvalid;
 508   schema_node->extra = extra;
 509
 510   const base::DictionaryValue* dict = NULL;
 511   if (schema.GetDictionary(schema::kAdditionalProperties, &dict)) {
 512     if (!Parse(*dict, &properties_nodes_[extra].additional,
 513                id_map, reference_list, error)) {
 514       return false;
 515     }
 516   }
 517
 518   properties_nodes_[extra].begin = static_cast<int>(property_nodes_.size());
 519
 520   const base::DictionaryValue* properties = NULL;
 521   if (schema.GetDictionary(schema::kProperties, &properties)) {
 522     // This and below reserves nodes for all of the |properties|, and makes sure
 523     // they are contiguous. Recursive calls to Parse() will append after these
 524     // elements.
 525     property_nodes_.resize(property_nodes_.size() + properties->size());
 526   }
 527
 528   properties_nodes_[extra].end = static_cast<int>(property_nodes_.size());
 529
 530   const base::DictionaryValue* pattern_properties = NULL;
 531   if (schema.GetDictionary(schema::kPatternProperties, &pattern_properties))
 532     property_nodes_.resize(property_nodes_.size() + pattern_properties->size());
 533
 534   properties_nodes_[extra].pattern_end =
 535       static_cast<int>(property_nodes_.size());
 536
 537   if (properties != NULL) {
 538     int base_index = properties_nodes_[extra].begin;
 539     int index = base_index;
 540
 541     for (base::DictionaryValue::Iterator it(*properties);
 542          !it.IsAtEnd(); it.Advance(), ++index) {
 543       // This should have been verified by the JSONSchemaValidator.
 544       CHECK(it.value().GetAsDictionary(&dict));
 545       strings_.push_back(it.key());
 546       property_nodes_[index].key = strings_.back().c_str();
 547       if (!Parse(*dict, &property_nodes_[index].schema,
 548                  id_map, reference_list, error)) {
 549         return false;
 550       }
 551     }
 552     CHECK_EQ(static_cast<int>(properties->size()), index - base_index);
 553   }
 554
 555   if (pattern_properties != NULL) {
 556     int base_index = properties_nodes_[extra].end;
 557     int index = base_index;
 558
 559     for (base::DictionaryValue::Iterator it(*pattern_properties);
 560          !it.IsAtEnd(); it.Advance(), ++index) {
 561       CHECK(it.value().GetAsDictionary(&dict));
 562       re2::RE2* compiled_regex = CompileRegex(it.key());
 563       if (!compiled_regex->ok()) {
 564         *error =
 565             "/" + it.key() + "/ is a invalid regex: " + compiled_regex->error();
 566         return false;
 567       }
 568       strings_.push_back(it.key());
 569       property_nodes_[index].key = strings_.back().c_str();
 570       if (!Parse(*dict, &property_nodes_[index].schema,
 571                  id_map, reference_list, error)) {
 572         return false;
 573       }
 574     }
 575     CHECK_EQ(static_cast<int>(pattern_properties->size()), index - base_index);
 576   }
 577
 578   if (properties_nodes_[extra].begin == properties_nodes_[extra].pattern_end) {
 579     properties_nodes_[extra].begin = kInvalid;
 580     properties_nodes_[extra].end = kInvalid;
 581     properties_nodes_[extra].pattern_end = kInvalid;
 582   }
 583
 584   return true;
 585 }
 586
 587 bool Schema::InternalStorage::ParseList(const base::DictionaryValue& schema,
 588                                         SchemaNode* schema_node,
 589                                         IdMap* id_map,
 590                                         ReferenceList* reference_list,
 591                                         std::string* error) {
 592   const base::DictionaryValue* dict = NULL;
 593   if (!schema.GetDictionary(schema::kItems, &dict)) {
 594     *error = "Arrays must declare a single schema for their items.";
 595     return false;
 596   }
 597   return Parse(*dict, &schema_node->extra, id_map, reference_list, error);
 598 }
 599
 600 bool Schema::InternalStorage::ParseEnum(const base::DictionaryValue& schema,
 601                                         base::Value::Type type,
 602                                         SchemaNode* schema_node,
 603                                         std::string* error) {
 604   const base::ListValue *possible_values = NULL;
 605   if (!schema.GetList(schema::kEnum, &possible_values)) {
 606     *error = "Enum attribute must be a list value";
 607     return false;
 608   }
 609   if (possible_values->empty()) {
 610     *error = "Enum attribute must be non-empty";
 611     return false;
 612   }
 613   int offset_begin;
 614   int offset_end;
 615   if (type == base::Value::TYPE_INTEGER) {
 616     offset_begin = static_cast<int>(int_enums_.size());
 617     int value;
 618     for (base::ListValue::const_iterator it = possible_values->begin();
 619          it != possible_values->end(); ++it) {
 620       if (!(*it)->GetAsInteger(&value)) {
 621         *error = "Invalid enumeration member type";
 622         return false;
 623       }
 624       int_enums_.push_back(value);
 625     }
 626     offset_end = static_cast<int>(int_enums_.size());
 627   } else if (type == base::Value::TYPE_STRING) {
 628     offset_begin = static_cast<int>(string_enums_.size());
 629     std::string value;
 630     for (base::ListValue::const_iterator it = possible_values->begin();
 631          it != possible_values->end(); ++it) {
 632       if (!(*it)->GetAsString(&value)) {
 633         *error = "Invalid enumeration member type";
 634         return false;
 635       }
 636       strings_.push_back(value);
 637       string_enums_.push_back(strings_.back().c_str());
 638     }
 639     offset_end = static_cast<int>(string_enums_.size());
 640   } else {
 641     *error = "Enumeration is only supported for integer and string.";
 642     return false;
 643   }
 644   schema_node->extra = static_cast<int>(restriction_nodes_.size());
 645   restriction_nodes_.push_back(RestrictionNode());
 646   restriction_nodes_.back().enumeration_restriction.offset_begin = offset_begin;
 647   restriction_nodes_.back().enumeration_restriction.offset_end = offset_end;
 648   return true;
 649 }
 650
 651 bool Schema::InternalStorage::ParseRangedInt(
 652     const base::DictionaryValue& schema,
 653     SchemaNode* schema_node,
 654     std::string* error) {
 655   int min_value = INT_MIN;
 656   int max_value = INT_MAX;
 657   int value;
 658   if (schema.GetInteger(schema::kMinimum, &value))
 659     min_value = value;
 660   if (schema.GetInteger(schema::kMaximum, &value))
 661     max_value = value;
 662   if (min_value > max_value) {
 663     *error = "Invalid range restriction for int type.";
 664     return false;
 665   }
 666   schema_node->extra = static_cast<int>(restriction_nodes_.size());
 667   restriction_nodes_.push_back(RestrictionNode());
 668   restriction_nodes_.back().ranged_restriction.max_value = max_value;
 669   restriction_nodes_.back().ranged_restriction.min_value = min_value;
 670   return true;
 671 }
 672
 673 bool Schema::InternalStorage::ParseStringPattern(
 674     const base::DictionaryValue& schema,
 675     SchemaNode* schema_node,
 676     std::string* error) {
 677   std::string pattern;
 678   if (!schema.GetString(schema::kPattern, &pattern)) {
 679     *error = "Schema pattern must be a string.";
 680     return false;
 681   }
 682   re2::RE2* compiled_regex = CompileRegex(pattern);
 683   if (!compiled_regex->ok()) {
 684     *error = "/" + pattern + "/ is invalid regex: " + compiled_regex->error();
 685     return false;
 686   }
 687   int index = static_cast<int>(string_enums_.size());
 688   strings_.push_back(pattern);
 689   string_enums_.push_back(strings_.back().c_str());
 690   schema_node->extra = static_cast<int>(restriction_nodes_.size());
 691   restriction_nodes_.push_back(RestrictionNode());
 692   restriction_nodes_.back().string_pattern_restriction.pattern_index = index;
 693   restriction_nodes_.back().string_pattern_restriction.pattern_index_backup =
 694       index;
 695   return true;
 696 }
 697
 698 // static
 699 bool Schema::InternalStorage::ResolveReferences(
 700     const IdMap& id_map,
 701     const ReferenceList& reference_list,
 702     std::string* error) {
 703   for (ReferenceList::const_iterator ref = reference_list.begin();
 704        ref != reference_list.end(); ++ref) {
 705     IdMap::const_iterator id = id_map.find(ref->first);
 706     if (id == id_map.end()) {
 707       *error = "Invalid $ref: " + ref->first;
 708       return false;
 709     }
 710     *ref->second = id->second;
 711   }
 712   return true;
 713 }
 714
 715 Schema::Iterator::Iterator(const scoped_refptr<const InternalStorage>& storage,
 716                            const PropertiesNode* node)
 717     : storage_(storage),
 718       it_(storage->property(node->begin)),
 719       end_(storage->property(node->end)) {}
 720
 721 Schema::Iterator::Iterator(const Iterator& iterator)
 722     : storage_(iterator.storage_),
 723       it_(iterator.it_),
 724       end_(iterator.end_) {}
 725
 726 Schema::Iterator::~Iterator() {}
 727
 728 Schema::Iterator& Schema::Iterator::operator=(const Iterator& iterator) {
 729   storage_ = iterator.storage_;
 730   it_ = iterator.it_;
 731   end_ = iterator.end_;
 732   return *this;
 733 }
 734
 735 bool Schema::Iterator::IsAtEnd() const {
 736   return it_ == end_;
 737 }
 738
 739 void Schema::Iterator::Advance() {
 740   ++it_;
 741 }
 742
 743 const char* Schema::Iterator::key() const {
 744   return it_->key;
 745 }
 746
 747 Schema Schema::Iterator::schema() const {
 748   return Schema(storage_, storage_->schema(it_->schema));
 749 }
 750
 751 Schema::Schema() : node_(NULL) {}
 752
 753 Schema::Schema(const scoped_refptr<const InternalStorage>& storage,
 754                const SchemaNode* node)
 755     : storage_(storage), node_(node) {}
 756
 757 Schema::Schema(const Schema& schema)
 758     : storage_(schema.storage_), node_(schema.node_) {}
 759
 760 Schema::~Schema() {}
 761
 762 Schema& Schema::operator=(const Schema& schema) {
 763   storage_ = schema.storage_;
 764   node_ = schema.node_;
 765   return *this;
 766 }
 767
 768 // static
 769 Schema Schema::Wrap(const SchemaData* data) {
 770   scoped_refptr<const InternalStorage> storage = InternalStorage::Wrap(data);
 771   return Schema(storage, storage->root_node());
 772 }
 773
 774 bool Schema::Validate(const base::Value& value,
 775                       SchemaOnErrorStrategy strategy,
 776                       std::string* error_path,
 777                       std::string* error) const {
 778   if (!valid()) {
 779     SchemaErrorFound(error_path, error, "The schema is invalid.");
 780     return false;
 781   }
 782
 783   if (!value.IsType(type())) {
 784     // Allow the integer to double promotion. Note that range restriction on
 785     // double is not supported now.
 786     if (value.IsType(base::Value::TYPE_INTEGER) &&
 787         type() == base::Value::TYPE_DOUBLE) {
 788       return true;
 789     }
 790
 791     SchemaErrorFound(
 792         error_path, error, "The value type doesn't match the schema type.");
 793     return false;
 794   }
 795
 796   const base::DictionaryValue* dict = NULL;
 797   const base::ListValue* list = NULL;
 798   int int_value;
 799   std::string str_value;
 800   if (value.GetAsDictionary(&dict)) {
 801     for (base::DictionaryValue::Iterator it(*dict); !it.IsAtEnd();
 802          it.Advance()) {
 803       SchemaList schema_list = GetMatchingProperties(it.key());
 804       if (schema_list.empty()) {
 805         // Unknown property was detected.
 806         SchemaErrorFound(error_path, error, "Unknown property: " + it.key());
 807         if (!StrategyAllowUnknownOnTopLevel(strategy))
 808           return false;
 809       } else {
 810         for (SchemaList::iterator subschema = schema_list.begin();
 811              subschema != schema_list.end(); ++subschema) {
 812           if (!subschema->Validate(it.value(),
 813                                    StrategyForNextLevel(strategy),
 814                                    error_path,
 815                                    error)) {
 816             // Invalid property was detected.
 817             AddDictKeyPrefixToPath(it.key(), error_path);
 818             if (!StrategyAllowInvalidOnTopLevel(strategy))
 819               return false;
 820           }
 821         }
 822       }
 823     }
 824   } else if (value.GetAsList(&list)) {
 825     for (base::ListValue::const_iterator it = list->begin(); it != list->end();
 826          ++it) {
 827       if (!*it ||
 828           !GetItems().Validate(**it,
 829                                StrategyForNextLevel(strategy),
 830                                error_path,
 831                                error)) {
 832         // Invalid list item was detected.
 833         AddListIndexPrefixToPath(it - list->begin(), error_path);
 834         if (!StrategyAllowInvalidOnTopLevel(strategy))
 835           return false;
 836       }
 837     }
 838   } else if (value.GetAsInteger(&int_value)) {
 839     if (node_->extra != kInvalid &&
 840         !ValidateIntegerRestriction(node_->extra, int_value)) {
 841       SchemaErrorFound(error_path, error, "Invalid value for integer");
 842       return false;
 843     }
 844   } else if (value.GetAsString(&str_value)) {
 845     if (node_->extra != kInvalid &&
 846         !ValidateStringRestriction(node_->extra, str_value.c_str())) {
 847       SchemaErrorFound(error_path, error, "Invalid value for string");
 848       return false;
 849     }
 850   }
 851
 852   return true;
 853 }
 854
 855 bool Schema::Normalize(base::Value* value,
 856                        SchemaOnErrorStrategy strategy,
 857                        std::string* error_path,
 858                        std::string* error,
 859                        bool* changed) const {
 860   if (!valid()) {
 861     SchemaErrorFound(error_path, error, "The schema is invalid.");
 862     return false;
 863   }
 864
 865   if (!value->IsType(type())) {
 866     // Allow the integer to double promotion. Note that range restriction on
 867     // double is not supported now.
 868     if (value->IsType(base::Value::TYPE_INTEGER) &&
 869         type() == base::Value::TYPE_DOUBLE) {
 870       return true;
 871     }
 872
 873     SchemaErrorFound(
 874         error_path, error, "The value type doesn't match the schema type.");
 875     return false;
 876   }
 877
 878   base::DictionaryValue* dict = NULL;
 879   base::ListValue* list = NULL;
 880   if (value->GetAsDictionary(&dict)) {
 881     std::vector<std::string> drop_list;  // Contains the keys to drop.
 882     for (base::DictionaryValue::Iterator it(*dict); !it.IsAtEnd();
 883          it.Advance()) {
 884       SchemaList schema_list = GetMatchingProperties(it.key());
 885       if (schema_list.empty()) {
 886         // Unknown property was detected.
 887         SchemaErrorFound(error_path, error, "Unknown property: " + it.key());
 888         if (StrategyAllowUnknownOnTopLevel(strategy))
 889           drop_list.push_back(it.key());
 890         else
 891           return false;
 892       } else {
 893         for (SchemaList::iterator subschema = schema_list.begin();
 894              subschema != schema_list.end(); ++subschema) {
 895           base::Value* sub_value = NULL;
 896           dict->GetWithoutPathExpansion(it.key(), &sub_value);
 897           if (!subschema->Normalize(sub_value,
 898                                     StrategyForNextLevel(strategy),
 899                                     error_path,
 900                                     error,
 901                                     changed)) {
 902             // Invalid property was detected.
 903             AddDictKeyPrefixToPath(it.key(), error_path);
 904             if (StrategyAllowInvalidOnTopLevel(strategy)) {
 905               drop_list.push_back(it.key());
 906               break;
 907             } else {
 908               return false;
 909             }
 910           }
 911         }
 912       }
 913     }
 914     if (changed && !drop_list.empty())
 915       *changed = true;
 916     for (std::vector<std::string>::const_iterator it = drop_list.begin();
 917          it != drop_list.end();
 918          ++it) {
 919       dict->RemoveWithoutPathExpansion(*it, NULL);
 920     }
 921     return true;
 922   } else if (value->GetAsList(&list)) {
 923     std::vector<size_t> drop_list;  // Contains the indexes to drop.
 924     for (size_t index = 0; index < list->GetSize(); index++) {
 925       base::Value* sub_value = NULL;
 926       list->Get(index, &sub_value);
 927       if (!sub_value || !GetItems().Normalize(sub_value,
 928                                               StrategyForNextLevel(strategy),
 929                                               error_path,
 930                                               error,
 931                                               changed)) {
 932         // Invalid list item was detected.
 933         AddListIndexPrefixToPath(index, error_path);
 934         if (StrategyAllowInvalidOnTopLevel(strategy))
 935           drop_list.push_back(index);
 936         else
 937           return false;
 938       }
 939     }
 940     if (changed && !drop_list.empty())
 941       *changed = true;
 942     for (std::vector<size_t>::reverse_iterator it = drop_list.rbegin();
 943          it != drop_list.rend(); ++it) {
 944       list->Remove(*it, NULL);
 945     }
 946     return true;
 947   }
 948
 949   return Validate(*value, strategy, error_path, error);
 950 }
 951
 952 // static
 953 Schema Schema::Parse(const std::string& content, std::string* error) {
 954   // Validate as a generic JSON schema, and ignore unknown attributes; they
 955   // may become used in a future version of the schema format.
 956   scoped_ptr<base::DictionaryValue> dict = JSONSchemaValidator::IsValidSchema(
 957       content, JSONSchemaValidator::OPTIONS_IGNORE_UNKNOWN_ATTRIBUTES, error);
 958   if (!dict)
 959     return Schema();
 960
 961   // Validate the main type.
 962   std::string string_value;
 963   if (!dict->GetString(schema::kType, &string_value) ||
 964       string_value != schema::kObject) {
 965     *error =
 966         "The main schema must have a type attribute with \"object\" value.";
 967     return Schema();
 968   }
 969
 970   // Checks for invalid attributes at the top-level.
 971   if (dict->HasKey(schema::kAdditionalProperties) ||
 972       dict->HasKey(schema::kPatternProperties)) {
 973     *error = "\"additionalProperties\" and \"patternProperties\" are not "
 974              "supported at the main schema.";
 975     return Schema();
 976   }
 977
 978   scoped_refptr<const InternalStorage> storage =
 979       InternalStorage::ParseSchema(*dict, error);
 980   if (!storage.get())
 981     return Schema();
 982   return Schema(storage, storage->root_node());
 983 }
 984
 985 base::Value::Type Schema::type() const {
 986   CHECK(valid());
 987   return node_->type;
 988 }
 989
 990 Schema::Iterator Schema::GetPropertiesIterator() const {
 991   CHECK(valid());
 992   CHECK_EQ(base::Value::TYPE_DICTIONARY, type());
 993   return Iterator(storage_, storage_->properties(node_->extra));
 994 }
 995
 996 namespace {
 997
 998 bool CompareKeys(const PropertyNode& node, const std::string& key) {
 999   return node.key < key;
1000 }
1001
1002 }  // namespace
1003
1004 Schema Schema::GetKnownProperty(const std::string& key) const {
1005   CHECK(valid());
1006   CHECK_EQ(base::Value::TYPE_DICTIONARY, type());
1007   const PropertiesNode* node = storage_->properties(node_->extra);
1008   const PropertyNode* begin = storage_->property(node->begin);
1009   const PropertyNode* end = storage_->property(node->end);
1010   const PropertyNode* it = std::lower_bound(begin, end, key, CompareKeys);
1011   if (it != end && it->key == key)
1012     return Schema(storage_, storage_->schema(it->schema));
1013   return Schema();
1014 }
1015
1016 Schema Schema::GetAdditionalProperties() const {
1017   CHECK(valid());
1018   CHECK_EQ(base::Value::TYPE_DICTIONARY, type());
1019   const PropertiesNode* node = storage_->properties(node_->extra);
1020   if (node->additional == kInvalid)
1021     return Schema();
1022   return Schema(storage_, storage_->schema(node->additional));
1023 }
1024
1025 SchemaList Schema::GetPatternProperties(const std::string& key) const {
1026   CHECK(valid());
1027   CHECK_EQ(base::Value::TYPE_DICTIONARY, type());
1028   const PropertiesNode* node = storage_->properties(node_->extra);
1029   const PropertyNode* begin = storage_->property(node->end);
1030   const PropertyNode* end = storage_->property(node->pattern_end);
1031   SchemaList matching_properties;
1032   for (const PropertyNode* it = begin; it != end; ++it) {
1033     if (re2::RE2::PartialMatch(key, *storage_->CompileRegex(it->key))) {
1034       matching_properties.push_back(
1035           Schema(storage_, storage_->schema(it->schema)));
1036     }
1037   }
1038   return matching_properties;
1039 }
1040
1041 Schema Schema::GetProperty(const std::string& key) const {
1042   Schema schema = GetKnownProperty(key);
1043   if (schema.valid())
1044     return schema;
1045   return GetAdditionalProperties();
1046 }
1047
1048 SchemaList Schema::GetMatchingProperties(const std::string& key) const {
1049   SchemaList schema_list;
1050
1051   Schema known_property = GetKnownProperty(key);
1052   if (known_property.valid())
1053     schema_list.push_back(known_property);
1054
1055   SchemaList pattern_properties = GetPatternProperties(key);
1056   schema_list.insert(
1057       schema_list.end(), pattern_properties.begin(), pattern_properties.end());
1058
1059   if (schema_list.empty()) {
1060     Schema additional_property = GetAdditionalProperties();
1061     if (additional_property.valid())
1062       schema_list.push_back(additional_property);
1063   }
1064
1065   return schema_list;
1066 }
1067
1068 Schema Schema::GetItems() const {
1069   CHECK(valid());
1070   CHECK_EQ(base::Value::TYPE_LIST, type());
1071   if (node_->extra == kInvalid)
1072     return Schema();
1073   return Schema(storage_, storage_->schema(node_->extra));
1074 }
1075
1076 bool Schema::ValidateIntegerRestriction(int index, int value) const {
1077   const RestrictionNode* rnode = storage_->restriction(index);
1078   if (rnode->ranged_restriction.min_value <=
1079       rnode->ranged_restriction.max_value) {
1080     return rnode->ranged_restriction.min_value <= value &&
1081            rnode->ranged_restriction.max_value >= value;
1082   } else {
1083     for (int i = rnode->enumeration_restriction.offset_begin;
1084          i < rnode->enumeration_restriction.offset_end; ++i) {
1085       if (*storage_->int_enums(i) == value)
1086         return true;
1087     }
1088     return false;
1089   }
1090 }
1091
1092 bool Schema::ValidateStringRestriction(int index, const char* str) const {
1093   const RestrictionNode* rnode = storage_->restriction(index);
1094   if (rnode->enumeration_restriction.offset_begin <
1095       rnode->enumeration_restriction.offset_end) {
1096     for (int i = rnode->enumeration_restriction.offset_begin;
1097          i < rnode->enumeration_restriction.offset_end; ++i) {
1098       if (strcmp(*storage_->string_enums(i), str) == 0)
1099         return true;
1100     }
1101     return false;
1102   } else {
1103     int index = rnode->string_pattern_restriction.pattern_index;
1104     DCHECK(index == rnode->string_pattern_restriction.pattern_index_backup);
1105     re2::RE2* regex = storage_->CompileRegex(*storage_->string_enums(index));
1106     return re2::RE2::PartialMatch(str, *regex);
1107   }
1108 }
1109
1110 }  // namespace policy