ceph/src/rapidjson/include/rapidjson/schema.h

   1 // Tencent is pleased to support the open source community by making RapidJSON available->
   2 //
   3 // Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip-> All rights reserved->
   4 //
   5 // Licensed under the MIT License (the "License"); you may not use this file except
   6 // in compliance with the License-> You may obtain a copy of the License at
   7 //
   8 // http://opensource->org/licenses/MIT
   9 //
  10 // Unless required by applicable law or agreed to in writing, software distributed
  11 // under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
  12 // CONDITIONS OF ANY KIND, either express or implied-> See the License for the
  13 // specific language governing permissions and limitations under the License->
  14
  15 #ifndef RAPIDJSON_SCHEMA_H_
  16 #define RAPIDJSON_SCHEMA_H_
  17
  18 #include "document.h"
  19 #include "pointer.h"
  20 #include <cmath> // abs, floor
  21
  22 #if !defined(RAPIDJSON_SCHEMA_USE_INTERNALREGEX)
  23 #define RAPIDJSON_SCHEMA_USE_INTERNALREGEX 1
  24 #else
  25 #define RAPIDJSON_SCHEMA_USE_INTERNALREGEX 0
  26 #endif
  27
  28 #if !RAPIDJSON_SCHEMA_USE_INTERNALREGEX && !defined(RAPIDJSON_SCHEMA_USE_STDREGEX) && (__cplusplus >=201103L || (defined(_MSC_VER) && _MSC_VER >= 1800))
  29 #define RAPIDJSON_SCHEMA_USE_STDREGEX 1
  30 #else
  31 #define RAPIDJSON_SCHEMA_USE_STDREGEX 0
  32 #endif
  33
  34 #if RAPIDJSON_SCHEMA_USE_INTERNALREGEX
  35 #include "internal/regex.h"
  36 #elif RAPIDJSON_SCHEMA_USE_STDREGEX
  37 #include <regex>
  38 #endif
  39
  40 #if RAPIDJSON_SCHEMA_USE_INTERNALREGEX || RAPIDJSON_SCHEMA_USE_STDREGEX
  41 #define RAPIDJSON_SCHEMA_HAS_REGEX 1
  42 #else
  43 #define RAPIDJSON_SCHEMA_HAS_REGEX 0
  44 #endif
  45
  46 #ifndef RAPIDJSON_SCHEMA_VERBOSE
  47 #define RAPIDJSON_SCHEMA_VERBOSE 0
  48 #endif
  49
  50 #if RAPIDJSON_SCHEMA_VERBOSE
  51 #include "stringbuffer.h"
  52 #endif
  53
  54 RAPIDJSON_DIAG_PUSH
  55
  56 #if defined(__GNUC__)
  57 RAPIDJSON_DIAG_OFF(effc++)
  58 #endif
  59
  60 #ifdef __clang__
  61 RAPIDJSON_DIAG_OFF(weak-vtables)
  62 RAPIDJSON_DIAG_OFF(exit-time-destructors)
  63 RAPIDJSON_DIAG_OFF(c++98-compat-pedantic)
  64 RAPIDJSON_DIAG_OFF(variadic-macros)
  65 #endif
  66
  67 #ifdef _MSC_VER
  68 RAPIDJSON_DIAG_OFF(4512) // assignment operator could not be generated
  69 #endif
  70
  71 RAPIDJSON_NAMESPACE_BEGIN
  72
  73 ///////////////////////////////////////////////////////////////////////////////
  74 // Verbose Utilities
  75
  76 #if RAPIDJSON_SCHEMA_VERBOSE
  77
  78 namespace internal {
  79
  80 inline void PrintInvalidKeyword(const char* keyword) {
  81     printf("Fail keyword: %s\n", keyword);
  82 }
  83
  84 inline void PrintInvalidKeyword(const wchar_t* keyword) {
  85     wprintf(L"Fail keyword: %ls\n", keyword);
  86 }
  87
  88 inline void PrintInvalidDocument(const char* document) {
  89     printf("Fail document: %s\n\n", document);
  90 }
  91
  92 inline void PrintInvalidDocument(const wchar_t* document) {
  93     wprintf(L"Fail document: %ls\n\n", document);
  94 }
  95
  96 inline void PrintValidatorPointers(unsigned depth, const char* s, const char* d) {
  97     printf("S: %*s%s\nD: %*s%s\n\n", depth * 4, " ", s, depth * 4, " ", d);
  98 }
  99
 100 inline void PrintValidatorPointers(unsigned depth, const wchar_t* s, const wchar_t* d) {
 101     wprintf(L"S: %*ls%ls\nD: %*ls%ls\n\n", depth * 4, L" ", s, depth * 4, L" ", d);
 102 }
 103
 104 } // namespace internal
 105
 106 #endif // RAPIDJSON_SCHEMA_VERBOSE
 107
 108 ///////////////////////////////////////////////////////////////////////////////
 109 // RAPIDJSON_INVALID_KEYWORD_RETURN
 110
 111 #if RAPIDJSON_SCHEMA_VERBOSE
 112 #define RAPIDJSON_INVALID_KEYWORD_VERBOSE(keyword) internal::PrintInvalidKeyword(keyword)
 113 #else
 114 #define RAPIDJSON_INVALID_KEYWORD_VERBOSE(keyword)
 115 #endif
 116
 117 #define RAPIDJSON_INVALID_KEYWORD_RETURN(keyword)\
 118 RAPIDJSON_MULTILINEMACRO_BEGIN\
 119     context.invalidKeyword = keyword.GetString();\
 120     RAPIDJSON_INVALID_KEYWORD_VERBOSE(keyword.GetString());\
 121     return false;\
 122 RAPIDJSON_MULTILINEMACRO_END
 123
 124 ///////////////////////////////////////////////////////////////////////////////
 125 // Forward declarations
 126
 127 template <typename ValueType, typename Allocator>
 128 class GenericSchemaDocument;
 129
 130 namespace internal {
 131
 132 template <typename SchemaDocumentType>
 133 class Schema;
 134
 135 ///////////////////////////////////////////////////////////////////////////////
 136 // ISchemaValidator
 137
 138 class ISchemaValidator {
 139 public:
 140     virtual ~ISchemaValidator() {}
 141     virtual bool IsValid() const = 0;
 142 };
 143
 144 ///////////////////////////////////////////////////////////////////////////////
 145 // ISchemaStateFactory
 146
 147 template <typename SchemaType>
 148 class ISchemaStateFactory {
 149 public:
 150     virtual ~ISchemaStateFactory() {}
 151     virtual ISchemaValidator* CreateSchemaValidator(const SchemaType&) = 0;
 152     virtual void DestroySchemaValidator(ISchemaValidator* validator) = 0;
 153     virtual void* CreateHasher() = 0;
 154     virtual uint64_t GetHashCode(void* hasher) = 0;
 155     virtual void DestroryHasher(void* hasher) = 0;
 156     virtual void* MallocState(size_t size) = 0;
 157     virtual void FreeState(void* p) = 0;
 158 };
 159
 160 ///////////////////////////////////////////////////////////////////////////////
 161 // Hasher
 162
 163 // For comparison of compound value
 164 template<typename Encoding, typename Allocator>
 165 class Hasher {
 166 public:
 167     typedef typename Encoding::Ch Ch;
 168
 169     Hasher(Allocator* allocator = 0, size_t stackCapacity = kDefaultSize) : stack_(allocator, stackCapacity) {}
 170
 171     bool Null() { return WriteType(kNullType); }
 172     bool Bool(bool b) { return WriteType(b ? kTrueType : kFalseType); }
 173     bool Int(int i) { Number n; n.u.i = i; n.d = static_cast<double>(i); return WriteNumber(n); }
 174     bool Uint(unsigned u) { Number n; n.u.u = u; n.d = static_cast<double>(u); return WriteNumber(n); }
 175     bool Int64(int64_t i) { Number n; n.u.i = i; n.d = static_cast<double>(i); return WriteNumber(n); }
 176     bool Uint64(uint64_t u) { Number n; n.u.u = u; n.d = static_cast<double>(u); return WriteNumber(n); }
 177     bool Double(double d) {
 178         Number n;
 179         if (d < 0) n.u.i = static_cast<int64_t>(d);
 180         else       n.u.u = static_cast<uint64_t>(d);
 181         n.d = d;
 182         return WriteNumber(n);
 183     }
 184
 185     bool RawNumber(const Ch* str, SizeType len, bool) {
 186         WriteBuffer(kNumberType, str, len * sizeof(Ch));
 187         return true;
 188     }
 189
 190     bool String(const Ch* str, SizeType len, bool) {
 191         WriteBuffer(kStringType, str, len * sizeof(Ch));
 192         return true;
 193     }
 194
 195     bool StartObject() { return true; }
 196     bool Key(const Ch* str, SizeType len, bool copy) { return String(str, len, copy); }
 197     bool EndObject(SizeType memberCount) {
 198         uint64_t h = Hash(0, kObjectType);
 199         uint64_t* kv = stack_.template Pop<uint64_t>(memberCount * 2);
 200         for (SizeType i = 0; i < memberCount; i++)
 201             h ^= Hash(kv[i * 2], kv[i * 2 + 1]);  // Use xor to achieve member order insensitive
 202         *stack_.template Push<uint64_t>() = h;
 203         return true;
 204     }
 205
 206     bool StartArray() { return true; }
 207     bool EndArray(SizeType elementCount) {
 208         uint64_t h = Hash(0, kArrayType);
 209         uint64_t* e = stack_.template Pop<uint64_t>(elementCount);
 210         for (SizeType i = 0; i < elementCount; i++)
 211             h = Hash(h, e[i]); // Use hash to achieve element order sensitive
 212         *stack_.template Push<uint64_t>() = h;
 213         return true;
 214     }
 215
 216     bool IsValid() const { return stack_.GetSize() == sizeof(uint64_t); }
 217
 218     uint64_t GetHashCode() const {
 219         RAPIDJSON_ASSERT(IsValid());
 220         return *stack_.template Top<uint64_t>();
 221     }
 222
 223 private:
 224     static const size_t kDefaultSize = 256;
 225     struct Number {
 226         union U {
 227             uint64_t u;
 228             int64_t i;
 229         }u;
 230         double d;
 231     };
 232
 233     bool WriteType(Type type) { return WriteBuffer(type, 0, 0); }
 234
 235     bool WriteNumber(const Number& n) { return WriteBuffer(kNumberType, &n, sizeof(n)); }
 236
 237     bool WriteBuffer(Type type, const void* data, size_t len) {
 238         // FNV-1a from http://isthe.com/chongo/tech/comp/fnv/
 239         uint64_t h = Hash(RAPIDJSON_UINT64_C2(0x84222325, 0xcbf29ce4), type);
 240         const unsigned char* d = static_cast<const unsigned char*>(data);
 241         for (size_t i = 0; i < len; i++)
 242             h = Hash(h, d[i]);
 243         *stack_.template Push<uint64_t>() = h;
 244         return true;
 245     }
 246
 247     static uint64_t Hash(uint64_t h, uint64_t d) {
 248         static const uint64_t kPrime = RAPIDJSON_UINT64_C2(0x00000100, 0x000001b3);
 249         h ^= d;
 250         h *= kPrime;
 251         return h;
 252     }
 253
 254     Stack<Allocator> stack_;
 255 };
 256
 257 ///////////////////////////////////////////////////////////////////////////////
 258 // SchemaValidationContext
 259
 260 template <typename SchemaDocumentType>
 261 struct SchemaValidationContext {
 262     typedef Schema<SchemaDocumentType> SchemaType;
 263     typedef ISchemaStateFactory<SchemaType> SchemaValidatorFactoryType;
 264     typedef typename SchemaType::ValueType ValueType;
 265     typedef typename ValueType::Ch Ch;
 266
 267     enum PatternValidatorType {
 268         kPatternValidatorOnly,
 269         kPatternValidatorWithProperty,
 270         kPatternValidatorWithAdditionalProperty
 271     };
 272
 273     SchemaValidationContext(SchemaValidatorFactoryType& f, const SchemaType* s) :
 274         factory(f),
 275         schema(s),
 276         valueSchema(),
 277         invalidKeyword(),
 278         hasher(),
 279         arrayElementHashCodes(),
 280         validators(),
 281         validatorCount(),
 282         patternPropertiesValidators(),
 283         patternPropertiesValidatorCount(),
 284         patternPropertiesSchemas(),
 285         patternPropertiesSchemaCount(),
 286         valuePatternValidatorType(kPatternValidatorOnly),
 287         propertyExist(),
 288         inArray(false),
 289         valueUniqueness(false),
 290         arrayUniqueness(false)
 291     {
 292     }
 293
 294     ~SchemaValidationContext() {
 295         if (hasher)
 296             factory.DestroryHasher(hasher);
 297         if (validators) {
 298             for (SizeType i = 0; i < validatorCount; i++)
 299                 factory.DestroySchemaValidator(validators[i]);
 300             factory.FreeState(validators);
 301         }
 302         if (patternPropertiesValidators) {
 303             for (SizeType i = 0; i < patternPropertiesValidatorCount; i++)
 304                 factory.DestroySchemaValidator(patternPropertiesValidators[i]);
 305             factory.FreeState(patternPropertiesValidators);
 306         }
 307         if (patternPropertiesSchemas)
 308             factory.FreeState(patternPropertiesSchemas);
 309         if (propertyExist)
 310             factory.FreeState(propertyExist);
 311     }
 312
 313     SchemaValidatorFactoryType& factory;
 314     const SchemaType* schema;
 315     const SchemaType* valueSchema;
 316     const Ch* invalidKeyword;
 317     void* hasher; // Only validator access
 318     void* arrayElementHashCodes; // Only validator access this
 319     ISchemaValidator** validators;
 320     SizeType validatorCount;
 321     ISchemaValidator** patternPropertiesValidators;
 322     SizeType patternPropertiesValidatorCount;
 323     const SchemaType** patternPropertiesSchemas;
 324     SizeType patternPropertiesSchemaCount;
 325     PatternValidatorType valuePatternValidatorType;
 326     PatternValidatorType objectPatternValidatorType;
 327     SizeType arrayElementIndex;
 328     bool* propertyExist;
 329     bool inArray;
 330     bool valueUniqueness;
 331     bool arrayUniqueness;
 332 };
 333
 334 ///////////////////////////////////////////////////////////////////////////////
 335 // Schema
 336
 337 template <typename SchemaDocumentType>
 338 class Schema {
 339 public:
 340     typedef typename SchemaDocumentType::ValueType ValueType;
 341     typedef typename SchemaDocumentType::AllocatorType AllocatorType;
 342     typedef typename SchemaDocumentType::PointerType PointerType;
 343     typedef typename ValueType::EncodingType EncodingType;
 344     typedef typename EncodingType::Ch Ch;
 345     typedef SchemaValidationContext<SchemaDocumentType> Context;
 346     typedef Schema<SchemaDocumentType> SchemaType;
 347     typedef GenericValue<EncodingType, AllocatorType> SValue;
 348     friend class GenericSchemaDocument<ValueType, AllocatorType>;
 349
 350     Schema(SchemaDocumentType* schemaDocument, const PointerType& p, const ValueType& value, const ValueType& document, AllocatorType* allocator) :
 351         allocator_(allocator),
 352         enum_(),
 353         enumCount_(),
 354         not_(),
 355         type_((1 << kTotalSchemaType) - 1), // typeless
 356         validatorCount_(),
 357         properties_(),
 358         additionalPropertiesSchema_(),
 359         patternProperties_(),
 360         patternPropertyCount_(),
 361         propertyCount_(),
 362         minProperties_(),
 363         maxProperties_(SizeType(~0)),
 364         additionalProperties_(true),
 365         hasDependencies_(),
 366         hasRequired_(),
 367         hasSchemaDependencies_(),
 368         additionalItemsSchema_(),
 369         itemsList_(),
 370         itemsTuple_(),
 371         itemsTupleCount_(),
 372         minItems_(),
 373         maxItems_(SizeType(~0)),
 374         additionalItems_(true),
 375         uniqueItems_(false),
 376         pattern_(),
 377         minLength_(0),
 378         maxLength_(~SizeType(0)),
 379         exclusiveMinimum_(false),
 380         exclusiveMaximum_(false)
 381     {
 382         typedef typename SchemaDocumentType::ValueType ValueType;
 383         typedef typename ValueType::ConstValueIterator ConstValueIterator;
 384         typedef typename ValueType::ConstMemberIterator ConstMemberIterator;
 385
 386         if (!value.IsObject())
 387             return;
 388
 389         if (const ValueType* v = GetMember(value, GetTypeString())) {
 390             type_ = 0;
 391             if (v->IsString())
 392                 AddType(*v);
 393             else if (v->IsArray())
 394                 for (ConstValueIterator itr = v->Begin(); itr != v->End(); ++itr)
 395                     AddType(*itr);
 396         }
 397
 398         if (const ValueType* v = GetMember(value, GetEnumString()))
 399             if (v->IsArray() && v->Size() > 0) {
 400                 enum_ = static_cast<uint64_t*>(allocator_->Malloc(sizeof(uint64_t) * v->Size()));
 401                 for (ConstValueIterator itr = v->Begin(); itr != v->End(); ++itr) {
 402                     typedef Hasher<EncodingType, MemoryPoolAllocator<> > EnumHasherType;
 403                     char buffer[256 + 24];
 404                     MemoryPoolAllocator<> hasherAllocator(buffer, sizeof(buffer));
 405                     EnumHasherType h(&hasherAllocator, 256);
 406                     itr->Accept(h);
 407                     enum_[enumCount_++] = h.GetHashCode();
 408                 }
 409             }
 410
 411         if (schemaDocument) {
 412             AssignIfExist(allOf_, *schemaDocument, p, value, GetAllOfString(), document);
 413             AssignIfExist(anyOf_, *schemaDocument, p, value, GetAnyOfString(), document);
 414             AssignIfExist(oneOf_, *schemaDocument, p, value, GetOneOfString(), document);
 415         }
 416
 417         if (const ValueType* v = GetMember(value, GetNotString())) {
 418             schemaDocument->CreateSchema(&not_, p.Append(GetNotString(), allocator_), *v, document);
 419             notValidatorIndex_ = validatorCount_;
 420             validatorCount_++;
 421         }
 422
 423         // Object
 424
 425         const ValueType* properties = GetMember(value, GetPropertiesString());
 426         const ValueType* required = GetMember(value, GetRequiredString());
 427         const ValueType* dependencies = GetMember(value, GetDependenciesString());
 428         {
 429             // Gather properties from properties/required/dependencies
 430             SValue allProperties(kArrayType);
 431
 432             if (properties && properties->IsObject())
 433                 for (ConstMemberIterator itr = properties->MemberBegin(); itr != properties->MemberEnd(); ++itr)
 434                     AddUniqueElement(allProperties, itr->name);
 435
 436             if (required && required->IsArray())
 437                 for (ConstValueIterator itr = required->Begin(); itr != required->End(); ++itr)
 438                     if (itr->IsString())
 439                         AddUniqueElement(allProperties, *itr);
 440
 441             if (dependencies && dependencies->IsObject())
 442                 for (ConstMemberIterator itr = dependencies->MemberBegin(); itr != dependencies->MemberEnd(); ++itr) {
 443                     AddUniqueElement(allProperties, itr->name);
 444                     if (itr->value.IsArray())
 445                         for (ConstValueIterator i = itr->value.Begin(); i != itr->value.End(); ++i)
 446                             if (i->IsString())
 447                                 AddUniqueElement(allProperties, *i);
 448                 }
 449
 450             if (allProperties.Size() > 0) {
 451                 propertyCount_ = allProperties.Size();
 452                 properties_ = static_cast<Property*>(allocator_->Malloc(sizeof(Property) * propertyCount_));
 453                 for (SizeType i = 0; i < propertyCount_; i++) {
 454                     new (&properties_[i]) Property();
 455                     properties_[i].name = allProperties[i];
 456                     properties_[i].schema = GetTypeless();
 457                 }
 458             }
 459         }
 460
 461         if (properties && properties->IsObject()) {
 462             PointerType q = p.Append(GetPropertiesString(), allocator_);
 463             for (ConstMemberIterator itr = properties->MemberBegin(); itr != properties->MemberEnd(); ++itr) {
 464                 SizeType index;
 465                 if (FindPropertyIndex(itr->name, &index))
 466                     schemaDocument->CreateSchema(&properties_[index].schema, q.Append(itr->name, allocator_), itr->value, document);
 467             }
 468         }
 469
 470         if (const ValueType* v = GetMember(value, GetPatternPropertiesString())) {
 471             PointerType q = p.Append(GetPatternPropertiesString(), allocator_);
 472             patternProperties_ = static_cast<PatternProperty*>(allocator_->Malloc(sizeof(PatternProperty) * v->MemberCount()));
 473             patternPropertyCount_ = 0;
 474
 475             for (ConstMemberIterator itr = v->MemberBegin(); itr != v->MemberEnd(); ++itr) {
 476                 new (&patternProperties_[patternPropertyCount_]) PatternProperty();
 477                 patternProperties_[patternPropertyCount_].pattern = CreatePattern(itr->name);
 478                 schemaDocument->CreateSchema(&patternProperties_[patternPropertyCount_].schema, q.Append(itr->name, allocator_), itr->value, document);
 479                 patternPropertyCount_++;
 480             }
 481         }
 482
 483         if (required && required->IsArray())
 484             for (ConstValueIterator itr = required->Begin(); itr != required->End(); ++itr)
 485                 if (itr->IsString()) {
 486                     SizeType index;
 487                     if (FindPropertyIndex(*itr, &index)) {
 488                         properties_[index].required = true;
 489                         hasRequired_ = true;
 490                     }
 491                 }
 492
 493         if (dependencies && dependencies->IsObject()) {
 494             PointerType q = p.Append(GetDependenciesString(), allocator_);
 495             hasDependencies_ = true;
 496             for (ConstMemberIterator itr = dependencies->MemberBegin(); itr != dependencies->MemberEnd(); ++itr) {
 497                 SizeType sourceIndex;
 498                 if (FindPropertyIndex(itr->name, &sourceIndex)) {
 499                     if (itr->value.IsArray()) {
 500                         properties_[sourceIndex].dependencies = static_cast<bool*>(allocator_->Malloc(sizeof(bool) * propertyCount_));
 501                         std::memset(properties_[sourceIndex].dependencies, 0, sizeof(bool)* propertyCount_);
 502                         for (ConstValueIterator targetItr = itr->value.Begin(); targetItr != itr->value.End(); ++targetItr) {
 503                             SizeType targetIndex;
 504                             if (FindPropertyIndex(*targetItr, &targetIndex))
 505                                 properties_[sourceIndex].dependencies[targetIndex] = true;
 506                         }
 507                     }
 508                     else if (itr->value.IsObject()) {
 509                         hasSchemaDependencies_ = true;
 510                         schemaDocument->CreateSchema(&properties_[sourceIndex].dependenciesSchema, q.Append(itr->name, allocator_), itr->value, document);
 511                         properties_[sourceIndex].dependenciesValidatorIndex = validatorCount_;
 512                         validatorCount_++;
 513                     }
 514                 }
 515             }
 516         }
 517
 518         if (const ValueType* v = GetMember(value, GetAdditionalPropertiesString())) {
 519             if (v->IsBool())
 520                 additionalProperties_ = v->GetBool();
 521             else if (v->IsObject())
 522                 schemaDocument->CreateSchema(&additionalPropertiesSchema_, p.Append(GetAdditionalPropertiesString(), allocator_), *v, document);
 523         }
 524
 525         AssignIfExist(minProperties_, value, GetMinPropertiesString());
 526         AssignIfExist(maxProperties_, value, GetMaxPropertiesString());
 527
 528         // Array
 529         if (const ValueType* v = GetMember(value, GetItemsString())) {
 530             PointerType q = p.Append(GetItemsString(), allocator_);
 531             if (v->IsObject()) // List validation
 532                 schemaDocument->CreateSchema(&itemsList_, q, *v, document);
 533             else if (v->IsArray()) { // Tuple validation
 534                 itemsTuple_ = static_cast<const Schema**>(allocator_->Malloc(sizeof(const Schema*) * v->Size()));
 535                 SizeType index = 0;
 536                 for (ConstValueIterator itr = v->Begin(); itr != v->End(); ++itr, index++)
 537                     schemaDocument->CreateSchema(&itemsTuple_[itemsTupleCount_++], q.Append(index, allocator_), *itr, document);
 538             }
 539         }
 540
 541         AssignIfExist(minItems_, value, GetMinItemsString());
 542         AssignIfExist(maxItems_, value, GetMaxItemsString());
 543
 544         if (const ValueType* v = GetMember(value, GetAdditionalItemsString())) {
 545             if (v->IsBool())
 546                 additionalItems_ = v->GetBool();
 547             else if (v->IsObject())
 548                 schemaDocument->CreateSchema(&additionalItemsSchema_, p.Append(GetAdditionalItemsString(), allocator_), *v, document);
 549         }
 550
 551         AssignIfExist(uniqueItems_, value, GetUniqueItemsString());
 552
 553         // String
 554         AssignIfExist(minLength_, value, GetMinLengthString());
 555         AssignIfExist(maxLength_, value, GetMaxLengthString());
 556
 557         if (const ValueType* v = GetMember(value, GetPatternString()))
 558             pattern_ = CreatePattern(*v);
 559
 560         // Number
 561         if (const ValueType* v = GetMember(value, GetMinimumString()))
 562             if (v->IsNumber())
 563                 minimum_.CopyFrom(*v, *allocator_);
 564
 565         if (const ValueType* v = GetMember(value, GetMaximumString()))
 566             if (v->IsNumber())
 567                 maximum_.CopyFrom(*v, *allocator_);
 568
 569         AssignIfExist(exclusiveMinimum_, value, GetExclusiveMinimumString());
 570         AssignIfExist(exclusiveMaximum_, value, GetExclusiveMaximumString());
 571
 572         if (const ValueType* v = GetMember(value, GetMultipleOfString()))
 573             if (v->IsNumber() && v->GetDouble() > 0.0)
 574                 multipleOf_.CopyFrom(*v, *allocator_);
 575     }
 576
 577     ~Schema() {
 578         if (allocator_) {
 579             allocator_->Free(enum_);
 580         }
 581         if (properties_) {
 582             for (SizeType i = 0; i < propertyCount_; i++)
 583                 properties_[i].~Property();
 584             AllocatorType::Free(properties_);
 585         }
 586         if (patternProperties_) {
 587             for (SizeType i = 0; i < patternPropertyCount_; i++)
 588                 patternProperties_[i].~PatternProperty();
 589             AllocatorType::Free(patternProperties_);
 590         }
 591         AllocatorType::Free(itemsTuple_);
 592 #if RAPIDJSON_SCHEMA_HAS_REGEX
 593         if (pattern_) {
 594             pattern_->~RegexType();
 595             allocator_->Free(pattern_);
 596         }
 597 #endif
 598     }
 599
 600     bool BeginValue(Context& context) const {
 601         if (context.inArray) {
 602             if (uniqueItems_)
 603                 context.valueUniqueness = true;
 604
 605             if (itemsList_)
 606                 context.valueSchema = itemsList_;
 607             else if (itemsTuple_) {
 608                 if (context.arrayElementIndex < itemsTupleCount_)
 609                     context.valueSchema = itemsTuple_[context.arrayElementIndex];
 610                 else if (additionalItemsSchema_)
 611                     context.valueSchema = additionalItemsSchema_;
 612                 else if (additionalItems_)
 613                     context.valueSchema = GetTypeless();
 614                 else
 615                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetItemsString());
 616             }
 617             else
 618                 context.valueSchema = GetTypeless();
 619
 620             context.arrayElementIndex++;
 621         }
 622         return true;
 623     }
 624
 625     RAPIDJSON_FORCEINLINE bool EndValue(Context& context) const {
 626         if (context.patternPropertiesValidatorCount > 0) {
 627             bool otherValid = false;
 628             SizeType count = context.patternPropertiesValidatorCount;
 629             if (context.objectPatternValidatorType != Context::kPatternValidatorOnly)
 630                 otherValid = context.patternPropertiesValidators[--count]->IsValid();
 631
 632             bool patternValid = true;
 633             for (SizeType i = 0; i < count; i++)
 634                 if (!context.patternPropertiesValidators[i]->IsValid()) {
 635                     patternValid = false;
 636                     break;
 637                 }
 638
 639             if (context.objectPatternValidatorType == Context::kPatternValidatorOnly) {
 640                 if (!patternValid)
 641                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetPatternPropertiesString());
 642             }
 643             else if (context.objectPatternValidatorType == Context::kPatternValidatorWithProperty) {
 644                 if (!patternValid || !otherValid)
 645                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetPatternPropertiesString());
 646             }
 647             else if (!patternValid && !otherValid) // kPatternValidatorWithAdditionalProperty)
 648                 RAPIDJSON_INVALID_KEYWORD_RETURN(GetPatternPropertiesString());
 649         }
 650
 651         if (enum_) {
 652             const uint64_t h = context.factory.GetHashCode(context.hasher);
 653             for (SizeType i = 0; i < enumCount_; i++)
 654                 if (enum_[i] == h)
 655                     goto foundEnum;
 656             RAPIDJSON_INVALID_KEYWORD_RETURN(GetEnumString());
 657             foundEnum:;
 658         }
 659
 660         if (allOf_.schemas)
 661             for (SizeType i = allOf_.begin; i < allOf_.begin + allOf_.count; i++)
 662                 if (!context.validators[i]->IsValid())
 663                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetAllOfString());
 664
 665         if (anyOf_.schemas) {
 666             for (SizeType i = anyOf_.begin; i < anyOf_.begin + anyOf_.count; i++)
 667                 if (context.validators[i]->IsValid())
 668                     goto foundAny;
 669             RAPIDJSON_INVALID_KEYWORD_RETURN(GetAnyOfString());
 670             foundAny:;
 671         }
 672
 673         if (oneOf_.schemas) {
 674             bool oneValid = false;
 675             for (SizeType i = oneOf_.begin; i < oneOf_.begin + oneOf_.count; i++)
 676                 if (context.validators[i]->IsValid()) {
 677                     if (oneValid)
 678                         RAPIDJSON_INVALID_KEYWORD_RETURN(GetOneOfString());
 679                     else
 680                         oneValid = true;
 681                 }
 682             if (!oneValid)
 683                 RAPIDJSON_INVALID_KEYWORD_RETURN(GetOneOfString());
 684         }
 685
 686         if (not_ && context.validators[notValidatorIndex_]->IsValid())
 687             RAPIDJSON_INVALID_KEYWORD_RETURN(GetNotString());
 688
 689         return true;
 690     }
 691
 692     bool Null(Context& context) const {
 693         if (!(type_ & (1 << kNullSchemaType)))
 694             RAPIDJSON_INVALID_KEYWORD_RETURN(GetTypeString());
 695         return CreateParallelValidator(context);
 696     }
 697
 698     bool Bool(Context& context, bool) const {
 699         if (!(type_ & (1 << kBooleanSchemaType)))
 700             RAPIDJSON_INVALID_KEYWORD_RETURN(GetTypeString());
 701         return CreateParallelValidator(context);
 702     }
 703
 704     bool Int(Context& context, int i) const {
 705         if (!CheckInt(context, i))
 706             return false;
 707         return CreateParallelValidator(context);
 708     }
 709
 710     bool Uint(Context& context, unsigned u) const {
 711         if (!CheckUint(context, u))
 712             return false;
 713         return CreateParallelValidator(context);
 714     }
 715
 716     bool Int64(Context& context, int64_t i) const {
 717         if (!CheckInt(context, i))
 718             return false;
 719         return CreateParallelValidator(context);
 720     }
 721
 722     bool Uint64(Context& context, uint64_t u) const {
 723         if (!CheckUint(context, u))
 724             return false;
 725         return CreateParallelValidator(context);
 726     }
 727
 728     bool Double(Context& context, double d) const {
 729         if (!(type_ & (1 << kNumberSchemaType)))
 730             RAPIDJSON_INVALID_KEYWORD_RETURN(GetTypeString());
 731
 732         if (!minimum_.IsNull() && !CheckDoubleMinimum(context, d))
 733             return false;
 734
 735         if (!maximum_.IsNull() && !CheckDoubleMaximum(context, d))
 736             return false;
 737
 738         if (!multipleOf_.IsNull() && !CheckDoubleMultipleOf(context, d))
 739             return false;
 740
 741         return CreateParallelValidator(context);
 742     }
 743
 744     bool String(Context& context, const Ch* str, SizeType length, bool) const {
 745         if (!(type_ & (1 << kStringSchemaType)))
 746             RAPIDJSON_INVALID_KEYWORD_RETURN(GetTypeString());
 747
 748         if (minLength_ != 0 || maxLength_ != SizeType(~0)) {
 749             SizeType count;
 750             if (internal::CountStringCodePoint<EncodingType>(str, length, &count)) {
 751                 if (count < minLength_)
 752                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetMinLengthString());
 753                 if (count > maxLength_)
 754                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetMaxLengthString());
 755             }
 756         }
 757
 758         if (pattern_ && !IsPatternMatch(pattern_, str, length))
 759             RAPIDJSON_INVALID_KEYWORD_RETURN(GetPatternString());
 760
 761         return CreateParallelValidator(context);
 762     }
 763
 764     bool StartObject(Context& context) const {
 765         if (!(type_ & (1 << kObjectSchemaType)))
 766             RAPIDJSON_INVALID_KEYWORD_RETURN(GetTypeString());
 767
 768         if (hasDependencies_ || hasRequired_) {
 769             context.propertyExist = static_cast<bool*>(context.factory.MallocState(sizeof(bool) * propertyCount_));
 770             std::memset(context.propertyExist, 0, sizeof(bool) * propertyCount_);
 771         }
 772
 773         if (patternProperties_) { // pre-allocate schema array
 774             SizeType count = patternPropertyCount_ + 1; // extra for valuePatternValidatorType
 775             context.patternPropertiesSchemas = static_cast<const SchemaType**>(context.factory.MallocState(sizeof(const SchemaType*) * count));
 776             context.patternPropertiesSchemaCount = 0;
 777             std::memset(context.patternPropertiesSchemas, 0, sizeof(SchemaType*) * count);
 778         }
 779
 780         return CreateParallelValidator(context);
 781     }
 782
 783     bool Key(Context& context, const Ch* str, SizeType len, bool) const {
 784         if (patternProperties_) {
 785             context.patternPropertiesSchemaCount = 0;
 786             for (SizeType i = 0; i < patternPropertyCount_; i++)
 787                 if (patternProperties_[i].pattern && IsPatternMatch(patternProperties_[i].pattern, str, len))
 788                     context.patternPropertiesSchemas[context.patternPropertiesSchemaCount++] = patternProperties_[i].schema;
 789         }
 790
 791         SizeType index;
 792         if (FindPropertyIndex(ValueType(str, len).Move(), &index)) {
 793             if (context.patternPropertiesSchemaCount > 0) {
 794                 context.patternPropertiesSchemas[context.patternPropertiesSchemaCount++] = properties_[index].schema;
 795                 context.valueSchema = GetTypeless();
 796                 context.valuePatternValidatorType = Context::kPatternValidatorWithProperty;
 797             }
 798             else
 799                 context.valueSchema = properties_[index].schema;
 800
 801             if (context.propertyExist)
 802                 context.propertyExist[index] = true;
 803
 804             return true;
 805         }
 806
 807         if (additionalPropertiesSchema_) {
 808             if (additionalPropertiesSchema_ && context.patternPropertiesSchemaCount > 0) {
 809                 context.patternPropertiesSchemas[context.patternPropertiesSchemaCount++] = additionalPropertiesSchema_;
 810                 context.valueSchema = GetTypeless();
 811                 context.valuePatternValidatorType = Context::kPatternValidatorWithAdditionalProperty;
 812             }
 813             else
 814                 context.valueSchema = additionalPropertiesSchema_;
 815             return true;
 816         }
 817         else if (additionalProperties_) {
 818             context.valueSchema = GetTypeless();
 819             return true;
 820         }
 821
 822         if (context.patternPropertiesSchemaCount == 0) // patternProperties are not additional properties
 823             RAPIDJSON_INVALID_KEYWORD_RETURN(GetAdditionalPropertiesString());
 824
 825         return true;
 826     }
 827
 828     bool EndObject(Context& context, SizeType memberCount) const {
 829         if (hasRequired_)
 830             for (SizeType index = 0; index < propertyCount_; index++)
 831                 if (properties_[index].required)
 832                     if (!context.propertyExist[index])
 833                         RAPIDJSON_INVALID_KEYWORD_RETURN(GetRequiredString());
 834
 835         if (memberCount < minProperties_)
 836             RAPIDJSON_INVALID_KEYWORD_RETURN(GetMinPropertiesString());
 837
 838         if (memberCount > maxProperties_)
 839             RAPIDJSON_INVALID_KEYWORD_RETURN(GetMaxPropertiesString());
 840
 841         if (hasDependencies_) {
 842             for (SizeType sourceIndex = 0; sourceIndex < propertyCount_; sourceIndex++)
 843                 if (context.propertyExist[sourceIndex]) {
 844                     if (properties_[sourceIndex].dependencies) {
 845                         for (SizeType targetIndex = 0; targetIndex < propertyCount_; targetIndex++)
 846                             if (properties_[sourceIndex].dependencies[targetIndex] && !context.propertyExist[targetIndex])
 847                                 RAPIDJSON_INVALID_KEYWORD_RETURN(GetDependenciesString());
 848                     }
 849                     else if (properties_[sourceIndex].dependenciesSchema)
 850                         if (!context.validators[properties_[sourceIndex].dependenciesValidatorIndex]->IsValid())
 851                             RAPIDJSON_INVALID_KEYWORD_RETURN(GetDependenciesString());
 852                 }
 853         }
 854
 855         return true;
 856     }
 857
 858     bool StartArray(Context& context) const {
 859         if (!(type_ & (1 << kArraySchemaType)))
 860             RAPIDJSON_INVALID_KEYWORD_RETURN(GetTypeString());
 861
 862         context.arrayElementIndex = 0;
 863         context.inArray = true;
 864
 865         return CreateParallelValidator(context);
 866     }
 867
 868     bool EndArray(Context& context, SizeType elementCount) const {
 869         context.inArray = false;
 870
 871         if (elementCount < minItems_)
 872             RAPIDJSON_INVALID_KEYWORD_RETURN(GetMinItemsString());
 873
 874         if (elementCount > maxItems_)
 875             RAPIDJSON_INVALID_KEYWORD_RETURN(GetMaxItemsString());
 876
 877         return true;
 878     }
 879
 880     // Generate functions for string literal according to Ch
 881 #define RAPIDJSON_STRING_(name, ...) \
 882     static const ValueType& Get##name##String() {\
 883         static const Ch s[] = { __VA_ARGS__, '\0' };\
 884         static const ValueType v(s, sizeof(s) / sizeof(Ch) - 1);\
 885         return v;\
 886     }
 887
 888     RAPIDJSON_STRING_(Null, 'n', 'u', 'l', 'l')
 889     RAPIDJSON_STRING_(Boolean, 'b', 'o', 'o', 'l', 'e', 'a', 'n')
 890     RAPIDJSON_STRING_(Object, 'o', 'b', 'j', 'e', 'c', 't')
 891     RAPIDJSON_STRING_(Array, 'a', 'r', 'r', 'a', 'y')
 892     RAPIDJSON_STRING_(String, 's', 't', 'r', 'i', 'n', 'g')
 893     RAPIDJSON_STRING_(Number, 'n', 'u', 'm', 'b', 'e', 'r')
 894     RAPIDJSON_STRING_(Integer, 'i', 'n', 't', 'e', 'g', 'e', 'r')
 895     RAPIDJSON_STRING_(Type, 't', 'y', 'p', 'e')
 896     RAPIDJSON_STRING_(Enum, 'e', 'n', 'u', 'm')
 897     RAPIDJSON_STRING_(AllOf, 'a', 'l', 'l', 'O', 'f')
 898     RAPIDJSON_STRING_(AnyOf, 'a', 'n', 'y', 'O', 'f')
 899     RAPIDJSON_STRING_(OneOf, 'o', 'n', 'e', 'O', 'f')
 900     RAPIDJSON_STRING_(Not, 'n', 'o', 't')
 901     RAPIDJSON_STRING_(Properties, 'p', 'r', 'o', 'p', 'e', 'r', 't', 'i', 'e', 's')
 902     RAPIDJSON_STRING_(Required, 'r', 'e', 'q', 'u', 'i', 'r', 'e', 'd')
 903     RAPIDJSON_STRING_(Dependencies, 'd', 'e', 'p', 'e', 'n', 'd', 'e', 'n', 'c', 'i', 'e', 's')
 904     RAPIDJSON_STRING_(PatternProperties, 'p', 'a', 't', 't', 'e', 'r', 'n', 'P', 'r', 'o', 'p', 'e', 'r', 't', 'i', 'e', 's')
 905     RAPIDJSON_STRING_(AdditionalProperties, 'a', 'd', 'd', 'i', 't', 'i', 'o', 'n', 'a', 'l', 'P', 'r', 'o', 'p', 'e', 'r', 't', 'i', 'e', 's')
 906     RAPIDJSON_STRING_(MinProperties, 'm', 'i', 'n', 'P', 'r', 'o', 'p', 'e', 'r', 't', 'i', 'e', 's')
 907     RAPIDJSON_STRING_(MaxProperties, 'm', 'a', 'x', 'P', 'r', 'o', 'p', 'e', 'r', 't', 'i', 'e', 's')
 908     RAPIDJSON_STRING_(Items, 'i', 't', 'e', 'm', 's')
 909     RAPIDJSON_STRING_(MinItems, 'm', 'i', 'n', 'I', 't', 'e', 'm', 's')
 910     RAPIDJSON_STRING_(MaxItems, 'm', 'a', 'x', 'I', 't', 'e', 'm', 's')
 911     RAPIDJSON_STRING_(AdditionalItems, 'a', 'd', 'd', 'i', 't', 'i', 'o', 'n', 'a', 'l', 'I', 't', 'e', 'm', 's')
 912     RAPIDJSON_STRING_(UniqueItems, 'u', 'n', 'i', 'q', 'u', 'e', 'I', 't', 'e', 'm', 's')
 913     RAPIDJSON_STRING_(MinLength, 'm', 'i', 'n', 'L', 'e', 'n', 'g', 't', 'h')
 914     RAPIDJSON_STRING_(MaxLength, 'm', 'a', 'x', 'L', 'e', 'n', 'g', 't', 'h')
 915     RAPIDJSON_STRING_(Pattern, 'p', 'a', 't', 't', 'e', 'r', 'n')
 916     RAPIDJSON_STRING_(Minimum, 'm', 'i', 'n', 'i', 'm', 'u', 'm')
 917     RAPIDJSON_STRING_(Maximum, 'm', 'a', 'x', 'i', 'm', 'u', 'm')
 918     RAPIDJSON_STRING_(ExclusiveMinimum, 'e', 'x', 'c', 'l', 'u', 's', 'i', 'v', 'e', 'M', 'i', 'n', 'i', 'm', 'u', 'm')
 919     RAPIDJSON_STRING_(ExclusiveMaximum, 'e', 'x', 'c', 'l', 'u', 's', 'i', 'v', 'e', 'M', 'a', 'x', 'i', 'm', 'u', 'm')
 920     RAPIDJSON_STRING_(MultipleOf, 'm', 'u', 'l', 't', 'i', 'p', 'l', 'e', 'O', 'f')
 921
 922 #undef RAPIDJSON_STRING_
 923
 924 private:
 925     enum SchemaValueType {
 926         kNullSchemaType,
 927         kBooleanSchemaType,
 928         kObjectSchemaType,
 929         kArraySchemaType,
 930         kStringSchemaType,
 931         kNumberSchemaType,
 932         kIntegerSchemaType,
 933         kTotalSchemaType
 934     };
 935
 936 #if RAPIDJSON_SCHEMA_USE_INTERNALREGEX
 937         typedef internal::GenericRegex<EncodingType> RegexType;
 938 #elif RAPIDJSON_SCHEMA_USE_STDREGEX
 939         typedef std::basic_regex<Ch> RegexType;
 940 #else
 941         typedef char RegexType;
 942 #endif
 943
 944     struct SchemaArray {
 945         SchemaArray() : schemas(), count() {}
 946         ~SchemaArray() { AllocatorType::Free(schemas); }
 947         const SchemaType** schemas;
 948         SizeType begin; // begin index of context.validators
 949         SizeType count;
 950     };
 951
 952     static const SchemaType* GetTypeless() {
 953         static SchemaType typeless(0, PointerType(), ValueType(kObjectType).Move(), ValueType(kObjectType).Move(), 0);
 954         return &typeless;
 955     }
 956
 957     template <typename V1, typename V2>
 958     void AddUniqueElement(V1& a, const V2& v) {
 959         for (typename V1::ConstValueIterator itr = a.Begin(); itr != a.End(); ++itr)
 960             if (*itr == v)
 961                 return;
 962         V1 c(v, *allocator_);
 963         a.PushBack(c, *allocator_);
 964     }
 965
 966     static const ValueType* GetMember(const ValueType& value, const ValueType& name) {
 967         typename ValueType::ConstMemberIterator itr = value.FindMember(name);
 968         return itr != value.MemberEnd() ? &(itr->value) : 0;
 969     }
 970
 971     static void AssignIfExist(bool& out, const ValueType& value, const ValueType& name) {
 972         if (const ValueType* v = GetMember(value, name))
 973             if (v->IsBool())
 974                 out = v->GetBool();
 975     }
 976
 977     static void AssignIfExist(SizeType& out, const ValueType& value, const ValueType& name) {
 978         if (const ValueType* v = GetMember(value, name))
 979             if (v->IsUint64() && v->GetUint64() <= SizeType(~0))
 980                 out = static_cast<SizeType>(v->GetUint64());
 981     }
 982
 983     void AssignIfExist(SchemaArray& out, SchemaDocumentType& schemaDocument, const PointerType& p, const ValueType& value, const ValueType& name, const ValueType& document) {
 984         if (const ValueType* v = GetMember(value, name)) {
 985             if (v->IsArray() && v->Size() > 0) {
 986                 PointerType q = p.Append(name, allocator_);
 987                 out.count = v->Size();
 988                 out.schemas = static_cast<const Schema**>(allocator_->Malloc(out.count * sizeof(const Schema*)));
 989                 memset(out.schemas, 0, sizeof(Schema*)* out.count);
 990                 for (SizeType i = 0; i < out.count; i++)
 991                     schemaDocument.CreateSchema(&out.schemas[i], q.Append(i, allocator_), (*v)[i], document);
 992                 out.begin = validatorCount_;
 993                 validatorCount_ += out.count;
 994             }
 995         }
 996     }
 997
 998 #if RAPIDJSON_SCHEMA_USE_INTERNALREGEX
 999     template <typename ValueType>
1000     RegexType* CreatePattern(const ValueType& value) {
1001         if (value.IsString()) {
1002             RegexType* r = new (allocator_->Malloc(sizeof(RegexType))) RegexType(value.GetString());
1003             if (!r->IsValid()) {
1004                 r->~RegexType();
1005                 AllocatorType::Free(r);
1006                 r = 0;
1007             }
1008             return r;
1009         }
1010         return 0;
1011     }
1012
1013     static bool IsPatternMatch(const RegexType* pattern, const Ch *str, SizeType) {
1014         return pattern->Search(str);
1015     }
1016 #elif RAPIDJSON_SCHEMA_USE_STDREGEX
1017     template <typename ValueType>
1018     RegexType* CreatePattern(const ValueType& value) {
1019         if (value.IsString())
1020             try {
1021                 return new (allocator_->Malloc(sizeof(RegexType))) RegexType(value.GetString(), std::size_t(value.GetStringLength()), std::regex_constants::ECMAScript);
1022             }
1023             catch (const std::regex_error&) {
1024             }
1025         return 0;
1026     }
1027
1028     static bool IsPatternMatch(const RegexType* pattern, const Ch *str, SizeType length) {
1029         std::match_results<const Ch*> r;
1030         return std::regex_search(str, str + length, r, *pattern);
1031     }
1032 #else
1033     template <typename ValueType>
1034     RegexType* CreatePattern(const ValueType&) { return 0; }
1035
1036     static bool IsPatternMatch(const RegexType*, const Ch *, SizeType) { return true; }
1037 #endif // RAPIDJSON_SCHEMA_USE_STDREGEX
1038
1039     void AddType(const ValueType& type) {
1040         if      (type == GetNullString()   ) type_ |= 1 << kNullSchemaType;
1041         else if (type == GetBooleanString()) type_ |= 1 << kBooleanSchemaType;
1042         else if (type == GetObjectString() ) type_ |= 1 << kObjectSchemaType;
1043         else if (type == GetArrayString()  ) type_ |= 1 << kArraySchemaType;
1044         else if (type == GetStringString() ) type_ |= 1 << kStringSchemaType;
1045         else if (type == GetIntegerString()) type_ |= 1 << kIntegerSchemaType;
1046         else if (type == GetNumberString() ) type_ |= (1 << kNumberSchemaType) | (1 << kIntegerSchemaType);
1047     }
1048
1049     bool CreateParallelValidator(Context& context) const {
1050         if (enum_ || context.arrayUniqueness)
1051             context.hasher = context.factory.CreateHasher();
1052
1053         if (validatorCount_) {
1054             RAPIDJSON_ASSERT(context.validators == 0);
1055             context.validators = static_cast<ISchemaValidator**>(context.factory.MallocState(sizeof(ISchemaValidator*) * validatorCount_));
1056             context.validatorCount = validatorCount_;
1057
1058             if (allOf_.schemas)
1059                 CreateSchemaValidators(context, allOf_);
1060
1061             if (anyOf_.schemas)
1062                 CreateSchemaValidators(context, anyOf_);
1063
1064             if (oneOf_.schemas)
1065                 CreateSchemaValidators(context, oneOf_);
1066
1067             if (not_)
1068                 context.validators[notValidatorIndex_] = context.factory.CreateSchemaValidator(*not_);
1069
1070             if (hasSchemaDependencies_) {
1071                 for (SizeType i = 0; i < propertyCount_; i++)
1072                     if (properties_[i].dependenciesSchema)
1073                         context.validators[properties_[i].dependenciesValidatorIndex] = context.factory.CreateSchemaValidator(*properties_[i].dependenciesSchema);
1074             }
1075         }
1076
1077         return true;
1078     }
1079
1080     void CreateSchemaValidators(Context& context, const SchemaArray& schemas) const {
1081         for (SizeType i = 0; i < schemas.count; i++)
1082             context.validators[schemas.begin + i] = context.factory.CreateSchemaValidator(*schemas.schemas[i]);
1083     }
1084
1085     // O(n)
1086     bool FindPropertyIndex(const ValueType& name, SizeType* outIndex) const {
1087         SizeType len = name.GetStringLength();
1088         const Ch* str = name.GetString();
1089         for (SizeType index = 0; index < propertyCount_; index++)
1090             if (properties_[index].name.GetStringLength() == len &&
1091                 (std::memcmp(properties_[index].name.GetString(), str, sizeof(Ch) * len) == 0))
1092             {
1093                 *outIndex = index;
1094                 return true;
1095             }
1096         return false;
1097     }
1098
1099     bool CheckInt(Context& context, int64_t i) const {
1100         if (!(type_ & ((1 << kIntegerSchemaType) | (1 << kNumberSchemaType))))
1101             RAPIDJSON_INVALID_KEYWORD_RETURN(GetTypeString());
1102
1103         if (!minimum_.IsNull()) {
1104             if (minimum_.IsInt64()) {
1105                 if (exclusiveMinimum_ ? i <= minimum_.GetInt64() : i < minimum_.GetInt64())
1106                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetMinimumString());
1107             }
1108             else if (minimum_.IsUint64()) {
1109                 RAPIDJSON_INVALID_KEYWORD_RETURN(GetMinimumString()); // i <= max(int64_t) < minimum.GetUint64()
1110             }
1111             else if (!CheckDoubleMinimum(context, static_cast<double>(i)))
1112                 return false;
1113         }
1114
1115         if (!maximum_.IsNull()) {
1116             if (maximum_.IsInt64()) {
1117                 if (exclusiveMaximum_ ? i >= maximum_.GetInt64() : i > maximum_.GetInt64())
1118                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetMaximumString());
1119             }
1120             else if (maximum_.IsUint64())
1121                 /* do nothing */; // i <= max(int64_t) < maximum_.GetUint64()
1122             else if (!CheckDoubleMaximum(context, static_cast<double>(i)))
1123                 return false;
1124         }
1125
1126         if (!multipleOf_.IsNull()) {
1127             if (multipleOf_.IsUint64()) {
1128                 if (static_cast<uint64_t>(i >= 0 ? i : -i) % multipleOf_.GetUint64() != 0)
1129                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetMultipleOfString());
1130             }
1131             else if (!CheckDoubleMultipleOf(context, static_cast<double>(i)))
1132                 return false;
1133         }
1134
1135         return true;
1136     }
1137
1138     bool CheckUint(Context& context, uint64_t i) const {
1139         if (!(type_ & ((1 << kIntegerSchemaType) | (1 << kNumberSchemaType))))
1140             RAPIDJSON_INVALID_KEYWORD_RETURN(GetTypeString());
1141
1142         if (!minimum_.IsNull()) {
1143             if (minimum_.IsUint64()) {
1144                 if (exclusiveMinimum_ ? i <= minimum_.GetUint64() : i < minimum_.GetUint64())
1145                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetMinimumString());
1146             }
1147             else if (minimum_.IsInt64())
1148                 /* do nothing */; // i >= 0 > minimum.Getint64()
1149             else if (!CheckDoubleMinimum(context, static_cast<double>(i)))
1150                 return false;
1151         }
1152
1153         if (!maximum_.IsNull()) {
1154             if (maximum_.IsUint64()) {
1155                 if (exclusiveMaximum_ ? i >= maximum_.GetUint64() : i > maximum_.GetUint64())
1156                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetMaximumString());
1157             }
1158             else if (maximum_.IsInt64())
1159                 RAPIDJSON_INVALID_KEYWORD_RETURN(GetMaximumString()); // i >= 0 > maximum_
1160             else if (!CheckDoubleMaximum(context, static_cast<double>(i)))
1161                 return false;
1162         }
1163
1164         if (!multipleOf_.IsNull()) {
1165             if (multipleOf_.IsUint64()) {
1166                 if (i % multipleOf_.GetUint64() != 0)
1167                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetMultipleOfString());
1168             }
1169             else if (!CheckDoubleMultipleOf(context, static_cast<double>(i)))
1170                 return false;
1171         }
1172
1173         return true;
1174     }
1175
1176     bool CheckDoubleMinimum(Context& context, double d) const {
1177         if (exclusiveMinimum_ ? d <= minimum_.GetDouble() : d < minimum_.GetDouble())
1178             RAPIDJSON_INVALID_KEYWORD_RETURN(GetMinimumString());
1179         return true;
1180     }
1181
1182     bool CheckDoubleMaximum(Context& context, double d) const {
1183         if (exclusiveMaximum_ ? d >= maximum_.GetDouble() : d > maximum_.GetDouble())
1184             RAPIDJSON_INVALID_KEYWORD_RETURN(GetMaximumString());
1185         return true;
1186     }
1187
1188     bool CheckDoubleMultipleOf(Context& context, double d) const {
1189         double a = std::abs(d), b = std::abs(multipleOf_.GetDouble());
1190         double q = std::floor(a / b);
1191         double r = a - q * b;
1192         if (r > 0.0)
1193             RAPIDJSON_INVALID_KEYWORD_RETURN(GetMultipleOfString());
1194         return true;
1195     }
1196
1197     struct Property {
1198         Property() : schema(), dependenciesSchema(), dependenciesValidatorIndex(), dependencies(), required(false) {}
1199         ~Property() { AllocatorType::Free(dependencies); }
1200         SValue name;
1201         const SchemaType* schema;
1202         const SchemaType* dependenciesSchema;
1203         SizeType dependenciesValidatorIndex;
1204         bool* dependencies;
1205         bool required;
1206     };
1207
1208     struct PatternProperty {
1209         PatternProperty() : schema(), pattern() {}
1210         ~PatternProperty() {
1211             if (pattern) {
1212                 pattern->~RegexType();
1213                 AllocatorType::Free(pattern);
1214             }
1215         }
1216         const SchemaType* schema;
1217         RegexType* pattern;
1218     };
1219
1220     AllocatorType* allocator_;
1221     uint64_t* enum_;
1222     SizeType enumCount_;
1223     SchemaArray allOf_;
1224     SchemaArray anyOf_;
1225     SchemaArray oneOf_;
1226     const SchemaType* not_;
1227     unsigned type_; // bitmask of kSchemaType
1228     SizeType validatorCount_;
1229     SizeType notValidatorIndex_;
1230
1231     Property* properties_;
1232     const SchemaType* additionalPropertiesSchema_;
1233     PatternProperty* patternProperties_;
1234     SizeType patternPropertyCount_;
1235     SizeType propertyCount_;
1236     SizeType minProperties_;
1237     SizeType maxProperties_;
1238     bool additionalProperties_;
1239     bool hasDependencies_;
1240     bool hasRequired_;
1241     bool hasSchemaDependencies_;
1242
1243     const SchemaType* additionalItemsSchema_;
1244     const SchemaType* itemsList_;
1245     const SchemaType** itemsTuple_;
1246     SizeType itemsTupleCount_;
1247     SizeType minItems_;
1248     SizeType maxItems_;
1249     bool additionalItems_;
1250     bool uniqueItems_;
1251
1252     RegexType* pattern_;
1253     SizeType minLength_;
1254     SizeType maxLength_;
1255
1256     SValue minimum_;
1257     SValue maximum_;
1258     SValue multipleOf_;
1259     bool exclusiveMinimum_;
1260     bool exclusiveMaximum_;
1261 };
1262
1263 template<typename Stack, typename Ch>
1264 struct TokenHelper {
1265     RAPIDJSON_FORCEINLINE static void AppendIndexToken(Stack& documentStack, SizeType index) {
1266         *documentStack.template Push<Ch>() = '/';
1267         char buffer[21];
1268         size_t length = static_cast<size_t>((sizeof(SizeType) == 4 ? u32toa(index, buffer) : u64toa(index, buffer)) - buffer);
1269         for (size_t i = 0; i < length; i++)
1270             *documentStack.template Push<Ch>() = buffer[i];
1271     }
1272 };
1273
1274 // Partial specialized version for char to prevent buffer copying.
1275 template <typename Stack>
1276 struct TokenHelper<Stack, char> {
1277     RAPIDJSON_FORCEINLINE static void AppendIndexToken(Stack& documentStack, SizeType index) {
1278         if (sizeof(SizeType) == 4) {
1279             char *buffer = documentStack.template Push<char>(1 + 10); // '/' + uint
1280             *buffer++ = '/';
1281             const char* end = internal::u32toa(index, buffer);
1282              documentStack.template Pop<char>(static_cast<size_t>(10 - (end - buffer)));
1283         }
1284         else {
1285             char *buffer = documentStack.template Push<char>(1 + 20); // '/' + uint64
1286             *buffer++ = '/';
1287             const char* end = internal::u64toa(index, buffer);
1288             documentStack.template Pop<char>(static_cast<size_t>(20 - (end - buffer)));
1289         }
1290     }
1291 };
1292
1293 } // namespace internal
1294
1295 ///////////////////////////////////////////////////////////////////////////////
1296 // IGenericRemoteSchemaDocumentProvider
1297
1298 template <typename SchemaDocumentType>
1299 class IGenericRemoteSchemaDocumentProvider {
1300 public:
1301     typedef typename SchemaDocumentType::Ch Ch;
1302
1303     virtual ~IGenericRemoteSchemaDocumentProvider() {}
1304     virtual const SchemaDocumentType* GetRemoteDocument(const Ch* uri, SizeType length) = 0;
1305 };
1306
1307 ///////////////////////////////////////////////////////////////////////////////
1308 // GenericSchemaDocument
1309
1310 //! JSON schema document.
1311 /*!
1312     A JSON schema document is a compiled version of a JSON schema.
1313     It is basically a tree of internal::Schema.
1314
1315     \note This is an immutable class (i.e. its instance cannot be modified after construction).
1316     \tparam ValueT Type of JSON value (e.g. \c Value ), which also determine the encoding.
1317     \tparam Allocator Allocator type for allocating memory of this document.
1318 */
1319 template <typename ValueT, typename Allocator = CrtAllocator>
1320 class GenericSchemaDocument {
1321 public:
1322     typedef ValueT ValueType;
1323     typedef IGenericRemoteSchemaDocumentProvider<GenericSchemaDocument> IRemoteSchemaDocumentProviderType;
1324     typedef Allocator AllocatorType;
1325     typedef typename ValueType::EncodingType EncodingType;
1326     typedef typename EncodingType::Ch Ch;
1327     typedef internal::Schema<GenericSchemaDocument> SchemaType;
1328     typedef GenericPointer<ValueType, Allocator> PointerType;
1329     friend class internal::Schema<GenericSchemaDocument>;
1330     template <typename, typename, typename>
1331     friend class GenericSchemaValidator;
1332
1333     //! Constructor.
1334     /*!
1335         Compile a JSON document into schema document.
1336
1337         \param document A JSON document as source.
1338         \param remoteProvider An optional remote schema document provider for resolving remote reference. Can be null.
1339         \param allocator An optional allocator instance for allocating memory. Can be null.
1340     */
1341     explicit GenericSchemaDocument(const ValueType& document, IRemoteSchemaDocumentProviderType* remoteProvider = 0, Allocator* allocator = 0) :
1342         remoteProvider_(remoteProvider),
1343         allocator_(allocator),
1344         ownAllocator_(),
1345         root_(),
1346         schemaMap_(allocator, kInitialSchemaMapSize),
1347         schemaRef_(allocator, kInitialSchemaRefSize)
1348     {
1349         if (!allocator_)
1350             ownAllocator_ = allocator_ = RAPIDJSON_NEW(Allocator());
1351
1352         // Generate root schema, it will call CreateSchema() to create sub-schemas,
1353         // And call AddRefSchema() if there are $ref.
1354         CreateSchemaRecursive(&root_, PointerType(), document, document);
1355
1356         // Resolve $ref
1357         while (!schemaRef_.Empty()) {
1358             SchemaRefEntry* refEntry = schemaRef_.template Pop<SchemaRefEntry>(1);
1359             if (const SchemaType* s = GetSchema(refEntry->target)) {
1360                 if (refEntry->schema)
1361                     *refEntry->schema = s;
1362
1363                 // Create entry in map if not exist
1364                 if (!GetSchema(refEntry->source)) {
1365                     new (schemaMap_.template Push<SchemaEntry>()) SchemaEntry(refEntry->source, const_cast<SchemaType*>(s), false, allocator_);
1366                 }
1367             }
1368             refEntry->~SchemaRefEntry();
1369         }
1370
1371         RAPIDJSON_ASSERT(root_ != 0);
1372
1373         schemaRef_.ShrinkToFit(); // Deallocate all memory for ref
1374     }
1375
1376 #if RAPIDJSON_HAS_CXX11_RVALUE_REFS
1377     //! Move constructor in C++11
1378     GenericSchemaDocument(GenericSchemaDocument&& rhs) RAPIDJSON_NOEXCEPT :
1379         remoteProvider_(rhs.remoteProvider_),
1380         allocator_(rhs.allocator_),
1381         ownAllocator_(rhs.ownAllocator_),
1382         root_(rhs.root_),
1383         schemaMap_(std::move(rhs.schemaMap_)),
1384         schemaRef_(std::move(rhs.schemaRef_))
1385     {
1386         rhs.remoteProvider_ = 0;
1387         rhs.allocator_ = 0;
1388         rhs.ownAllocator_ = 0;
1389     }
1390 #endif
1391
1392     //! Destructor
1393     ~GenericSchemaDocument() {
1394         while (!schemaMap_.Empty())
1395             schemaMap_.template Pop<SchemaEntry>(1)->~SchemaEntry();
1396
1397         RAPIDJSON_DELETE(ownAllocator_);
1398     }
1399
1400     //! Get the root schema.
1401     const SchemaType& GetRoot() const { return *root_; }
1402
1403 private:
1404     //! Prohibit copying
1405     GenericSchemaDocument(const GenericSchemaDocument&);
1406     //! Prohibit assignment
1407     GenericSchemaDocument& operator=(const GenericSchemaDocument&);
1408
1409     struct SchemaRefEntry {
1410         SchemaRefEntry(const PointerType& s, const PointerType& t, const SchemaType** outSchema, Allocator *allocator) : source(s, allocator), target(t, allocator), schema(outSchema) {}
1411         PointerType source;
1412         PointerType target;
1413         const SchemaType** schema;
1414     };
1415
1416     struct SchemaEntry {
1417         SchemaEntry(const PointerType& p, SchemaType* s, bool o, Allocator* allocator) : pointer(p, allocator), schema(s), owned(o) {}
1418         ~SchemaEntry() {
1419             if (owned) {
1420                 schema->~SchemaType();
1421                 Allocator::Free(schema);
1422             }
1423         }
1424         PointerType pointer;
1425         SchemaType* schema;
1426         bool owned;
1427     };
1428
1429     void CreateSchemaRecursive(const SchemaType** schema, const PointerType& pointer, const ValueType& v, const ValueType& document) {
1430         if (schema)
1431             *schema = SchemaType::GetTypeless();
1432
1433         if (v.GetType() == kObjectType) {
1434             const SchemaType* s = GetSchema(pointer);
1435             if (!s)
1436                 CreateSchema(schema, pointer, v, document);
1437
1438             for (typename ValueType::ConstMemberIterator itr = v.MemberBegin(); itr != v.MemberEnd(); ++itr)
1439                 CreateSchemaRecursive(0, pointer.Append(itr->name, allocator_), itr->value, document);
1440         }
1441         else if (v.GetType() == kArrayType)
1442             for (SizeType i = 0; i < v.Size(); i++)
1443                 CreateSchemaRecursive(0, pointer.Append(i, allocator_), v[i], document);
1444     }
1445
1446     void CreateSchema(const SchemaType** schema, const PointerType& pointer, const ValueType& v, const ValueType& document) {
1447         RAPIDJSON_ASSERT(pointer.IsValid());
1448         if (v.IsObject()) {
1449             if (!HandleRefSchema(pointer, schema, v, document)) {
1450                 SchemaType* s = new (allocator_->Malloc(sizeof(SchemaType))) SchemaType(this, pointer, v, document, allocator_);
1451                 new (schemaMap_.template Push<SchemaEntry>()) SchemaEntry(pointer, s, true, allocator_);
1452                 if (schema)
1453                     *schema = s;
1454             }
1455         }
1456     }
1457
1458     bool HandleRefSchema(const PointerType& source, const SchemaType** schema, const ValueType& v, const ValueType& document) {
1459         static const Ch kRefString[] = { '$', 'r', 'e', 'f', '\0' };
1460         static const ValueType kRefValue(kRefString, 4);
1461
1462         typename ValueType::ConstMemberIterator itr = v.FindMember(kRefValue);
1463         if (itr == v.MemberEnd())
1464             return false;
1465
1466         if (itr->value.IsString()) {
1467             SizeType len = itr->value.GetStringLength();
1468             if (len > 0) {
1469                 const Ch* s = itr->value.GetString();
1470                 SizeType i = 0;
1471                 while (i < len && s[i] != '#') // Find the first #
1472                     i++;
1473
1474                 if (i > 0) { // Remote reference, resolve immediately
1475                     if (remoteProvider_) {
1476                         if (const GenericSchemaDocument* remoteDocument = remoteProvider_->GetRemoteDocument(s, i - 1)) {
1477                             PointerType pointer(&s[i], len - i, allocator_);
1478                             if (pointer.IsValid()) {
1479                                 if (const SchemaType* sc = remoteDocument->GetSchema(pointer)) {
1480                                     if (schema)
1481                                         *schema = sc;
1482                                     return true;
1483                                 }
1484                             }
1485                         }
1486                     }
1487                 }
1488                 else if (s[i] == '#') { // Local reference, defer resolution
1489                     PointerType pointer(&s[i], len - i, allocator_);
1490                     if (pointer.IsValid()) {
1491                         if (const ValueType* nv = pointer.Get(document))
1492                             if (HandleRefSchema(source, schema, *nv, document))
1493                                 return true;
1494
1495                         new (schemaRef_.template Push<SchemaRefEntry>()) SchemaRefEntry(source, pointer, schema, allocator_);
1496                         return true;
1497                     }
1498                 }
1499             }
1500         }
1501         return false;
1502     }
1503
1504     const SchemaType* GetSchema(const PointerType& pointer) const {
1505         for (const SchemaEntry* target = schemaMap_.template Bottom<SchemaEntry>(); target != schemaMap_.template End<SchemaEntry>(); ++target)
1506             if (pointer == target->pointer)
1507                 return target->schema;
1508         return 0;
1509     }
1510
1511     PointerType GetPointer(const SchemaType* schema) const {
1512         for (const SchemaEntry* target = schemaMap_.template Bottom<SchemaEntry>(); target != schemaMap_.template End<SchemaEntry>(); ++target)
1513             if (schema == target->schema)
1514                 return target->pointer;
1515         return PointerType();
1516     }
1517
1518     static const size_t kInitialSchemaMapSize = 64;
1519     static const size_t kInitialSchemaRefSize = 64;
1520
1521     IRemoteSchemaDocumentProviderType* remoteProvider_;
1522     Allocator *allocator_;
1523     Allocator *ownAllocator_;
1524     const SchemaType* root_;                //!< Root schema.
1525     internal::Stack<Allocator> schemaMap_;  // Stores created Pointer -> Schemas
1526     internal::Stack<Allocator> schemaRef_;  // Stores Pointer from $ref and schema which holds the $ref
1527 };
1528
1529 //! GenericSchemaDocument using Value type.
1530 typedef GenericSchemaDocument<Value> SchemaDocument;
1531 //! IGenericRemoteSchemaDocumentProvider using SchemaDocument.
1532 typedef IGenericRemoteSchemaDocumentProvider<SchemaDocument> IRemoteSchemaDocumentProvider;
1533
1534 ///////////////////////////////////////////////////////////////////////////////
1535 // GenericSchemaValidator
1536
1537 //! JSON Schema Validator.
1538 /*!
1539     A SAX style JSON schema validator.
1540     It uses a \c GenericSchemaDocument to validate SAX events.
1541     It delegates the incoming SAX events to an output handler.
1542     The default output handler does nothing.
1543     It can be reused multiple times by calling \c Reset().
1544
1545     \tparam SchemaDocumentType Type of schema document.
1546     \tparam OutputHandler Type of output handler. Default handler does nothing.
1547     \tparam StateAllocator Allocator for storing the internal validation states.
1548 */
1549 template <
1550     typename SchemaDocumentType,
1551     typename OutputHandler = BaseReaderHandler<typename SchemaDocumentType::SchemaType::EncodingType>,
1552     typename StateAllocator = CrtAllocator>
1553 class GenericSchemaValidator :
1554     public internal::ISchemaStateFactory<typename SchemaDocumentType::SchemaType>,
1555     public internal::ISchemaValidator
1556 {
1557 public:
1558     typedef typename SchemaDocumentType::SchemaType SchemaType;
1559     typedef typename SchemaDocumentType::PointerType PointerType;
1560     typedef typename SchemaType::EncodingType EncodingType;
1561     typedef typename EncodingType::Ch Ch;
1562
1563     //! Constructor without output handler.
1564     /*!
1565         \param schemaDocument The schema document to conform to.
1566         \param allocator Optional allocator for storing internal validation states.
1567         \param schemaStackCapacity Optional initial capacity of schema path stack.
1568         \param documentStackCapacity Optional initial capacity of document path stack.
1569     */
1570     GenericSchemaValidator(
1571         const SchemaDocumentType& schemaDocument,
1572         StateAllocator* allocator = 0,
1573         size_t schemaStackCapacity = kDefaultSchemaStackCapacity,
1574         size_t documentStackCapacity = kDefaultDocumentStackCapacity)
1575         :
1576         schemaDocument_(&schemaDocument),
1577         root_(schemaDocument.GetRoot()),
1578         outputHandler_(GetNullHandler()),
1579         stateAllocator_(allocator),
1580         ownStateAllocator_(0),
1581         schemaStack_(allocator, schemaStackCapacity),
1582         documentStack_(allocator, documentStackCapacity),
1583         valid_(true)
1584 #if RAPIDJSON_SCHEMA_VERBOSE
1585         , depth_(0)
1586 #endif
1587     {
1588     }
1589
1590     //! Constructor with output handler.
1591     /*!
1592         \param schemaDocument The schema document to conform to.
1593         \param allocator Optional allocator for storing internal validation states.
1594         \param schemaStackCapacity Optional initial capacity of schema path stack.
1595         \param documentStackCapacity Optional initial capacity of document path stack.
1596     */
1597     GenericSchemaValidator(
1598         const SchemaDocumentType& schemaDocument,
1599         OutputHandler& outputHandler,
1600         StateAllocator* allocator = 0,
1601         size_t schemaStackCapacity = kDefaultSchemaStackCapacity,
1602         size_t documentStackCapacity = kDefaultDocumentStackCapacity)
1603         :
1604         schemaDocument_(&schemaDocument),
1605         root_(schemaDocument.GetRoot()),
1606         outputHandler_(outputHandler),
1607         stateAllocator_(allocator),
1608         ownStateAllocator_(0),
1609         schemaStack_(allocator, schemaStackCapacity),
1610         documentStack_(allocator, documentStackCapacity),
1611         valid_(true)
1612 #if RAPIDJSON_SCHEMA_VERBOSE
1613         , depth_(0)
1614 #endif
1615     {
1616     }
1617
1618     //! Destructor.
1619     ~GenericSchemaValidator() {
1620         Reset();
1621         RAPIDJSON_DELETE(ownStateAllocator_);
1622     }
1623
1624     //! Reset the internal states.
1625     void Reset() {
1626         while (!schemaStack_.Empty())
1627             PopSchema();
1628         documentStack_.Clear();
1629         valid_ = true;
1630     }
1631
1632     //! Checks whether the current state is valid.
1633     // Implementation of ISchemaValidator
1634     virtual bool IsValid() const { return valid_; }
1635
1636     //! Gets the JSON pointer pointed to the invalid schema.
1637     PointerType GetInvalidSchemaPointer() const {
1638         return schemaStack_.Empty() ? PointerType() : schemaDocument_->GetPointer(&CurrentSchema());
1639     }
1640
1641     //! Gets the keyword of invalid schema.
1642     const Ch* GetInvalidSchemaKeyword() const {
1643         return schemaStack_.Empty() ? 0 : CurrentContext().invalidKeyword;
1644     }
1645
1646     //! Gets the JSON pointer pointed to the invalid value.
1647     PointerType GetInvalidDocumentPointer() const {
1648         return documentStack_.Empty() ? PointerType() : PointerType(documentStack_.template Bottom<Ch>(), documentStack_.GetSize() / sizeof(Ch));
1649     }
1650
1651 #if RAPIDJSON_SCHEMA_VERBOSE
1652 #define RAPIDJSON_SCHEMA_HANDLE_BEGIN_VERBOSE_() \
1653 RAPIDJSON_MULTILINEMACRO_BEGIN\
1654     *documentStack_.template Push<Ch>() = '\0';\
1655     documentStack_.template Pop<Ch>(1);\
1656     internal::PrintInvalidDocument(documentStack_.template Bottom<Ch>());\
1657 RAPIDJSON_MULTILINEMACRO_END
1658 #else
1659 #define RAPIDJSON_SCHEMA_HANDLE_BEGIN_VERBOSE_()
1660 #endif
1661
1662 #define RAPIDJSON_SCHEMA_HANDLE_BEGIN_(method, arg1)\
1663     if (!valid_) return false; \
1664     if (!BeginValue() || !CurrentSchema().method arg1) {\
1665         RAPIDJSON_SCHEMA_HANDLE_BEGIN_VERBOSE_();\
1666         return valid_ = false;\
1667     }
1668
1669 #define RAPIDJSON_SCHEMA_HANDLE_PARALLEL_(method, arg2)\
1670     for (Context* context = schemaStack_.template Bottom<Context>(); context != schemaStack_.template End<Context>(); context++) {\
1671         if (context->hasher)\
1672             static_cast<HasherType*>(context->hasher)->method arg2;\
1673         if (context->validators)\
1674             for (SizeType i_ = 0; i_ < context->validatorCount; i_++)\
1675                 static_cast<GenericSchemaValidator*>(context->validators[i_])->method arg2;\
1676         if (context->patternPropertiesValidators)\
1677             for (SizeType i_ = 0; i_ < context->patternPropertiesValidatorCount; i_++)\
1678                 static_cast<GenericSchemaValidator*>(context->patternPropertiesValidators[i_])->method arg2;\
1679     }
1680
1681 #define RAPIDJSON_SCHEMA_HANDLE_END_(method, arg2)\
1682     return valid_ = EndValue() && outputHandler_.method arg2
1683
1684 #define RAPIDJSON_SCHEMA_HANDLE_VALUE_(method, arg1, arg2) \
1685     RAPIDJSON_SCHEMA_HANDLE_BEGIN_   (method, arg1);\
1686     RAPIDJSON_SCHEMA_HANDLE_PARALLEL_(method, arg2);\
1687     RAPIDJSON_SCHEMA_HANDLE_END_     (method, arg2)
1688
1689     bool Null()             { RAPIDJSON_SCHEMA_HANDLE_VALUE_(Null,   (CurrentContext()   ), ( )); }
1690     bool Bool(bool b)       { RAPIDJSON_SCHEMA_HANDLE_VALUE_(Bool,   (CurrentContext(), b), (b)); }
1691     bool Int(int i)         { RAPIDJSON_SCHEMA_HANDLE_VALUE_(Int,    (CurrentContext(), i), (i)); }
1692     bool Uint(unsigned u)   { RAPIDJSON_SCHEMA_HANDLE_VALUE_(Uint,   (CurrentContext(), u), (u)); }
1693     bool Int64(int64_t i)   { RAPIDJSON_SCHEMA_HANDLE_VALUE_(Int64,  (CurrentContext(), i), (i)); }
1694     bool Uint64(uint64_t u) { RAPIDJSON_SCHEMA_HANDLE_VALUE_(Uint64, (CurrentContext(), u), (u)); }
1695     bool Double(double d)   { RAPIDJSON_SCHEMA_HANDLE_VALUE_(Double, (CurrentContext(), d), (d)); }
1696     bool RawNumber(const Ch* str, SizeType length, bool copy)
1697                                     { RAPIDJSON_SCHEMA_HANDLE_VALUE_(String, (CurrentContext(), str, length, copy), (str, length, copy)); }
1698     bool String(const Ch* str, SizeType length, bool copy)
1699                                     { RAPIDJSON_SCHEMA_HANDLE_VALUE_(String, (CurrentContext(), str, length, copy), (str, length, copy)); }
1700
1701     bool StartObject() {
1702         RAPIDJSON_SCHEMA_HANDLE_BEGIN_(StartObject, (CurrentContext()));
1703         RAPIDJSON_SCHEMA_HANDLE_PARALLEL_(StartObject, ());
1704         return valid_ = outputHandler_.StartObject();
1705     }
1706
1707     bool Key(const Ch* str, SizeType len, bool copy) {
1708         if (!valid_) return false;
1709         AppendToken(str, len);
1710         if (!CurrentSchema().Key(CurrentContext(), str, len, copy)) return valid_ = false;
1711         RAPIDJSON_SCHEMA_HANDLE_PARALLEL_(Key, (str, len, copy));
1712         return valid_ = outputHandler_.Key(str, len, copy);
1713     }
1714
1715     bool EndObject(SizeType memberCount) {
1716         if (!valid_) return false;
1717         RAPIDJSON_SCHEMA_HANDLE_PARALLEL_(EndObject, (memberCount));
1718         if (!CurrentSchema().EndObject(CurrentContext(), memberCount)) return valid_ = false;
1719         RAPIDJSON_SCHEMA_HANDLE_END_(EndObject, (memberCount));
1720     }
1721
1722     bool StartArray() {
1723         RAPIDJSON_SCHEMA_HANDLE_BEGIN_(StartArray, (CurrentContext()));
1724         RAPIDJSON_SCHEMA_HANDLE_PARALLEL_(StartArray, ());
1725         return valid_ = outputHandler_.StartArray();
1726     }
1727
1728     bool EndArray(SizeType elementCount) {
1729         if (!valid_) return false;
1730         RAPIDJSON_SCHEMA_HANDLE_PARALLEL_(EndArray, (elementCount));
1731         if (!CurrentSchema().EndArray(CurrentContext(), elementCount)) return valid_ = false;
1732         RAPIDJSON_SCHEMA_HANDLE_END_(EndArray, (elementCount));
1733     }
1734
1735 #undef RAPIDJSON_SCHEMA_HANDLE_BEGIN_VERBOSE_
1736 #undef RAPIDJSON_SCHEMA_HANDLE_BEGIN_
1737 #undef RAPIDJSON_SCHEMA_HANDLE_PARALLEL_
1738 #undef RAPIDJSON_SCHEMA_HANDLE_VALUE_
1739
1740     // Implementation of ISchemaStateFactory<SchemaType>
1741     virtual ISchemaValidator* CreateSchemaValidator(const SchemaType& root) {
1742         return new (GetStateAllocator().Malloc(sizeof(GenericSchemaValidator))) GenericSchemaValidator(*schemaDocument_, root,
1743 #if RAPIDJSON_SCHEMA_VERBOSE
1744         depth_ + 1,
1745 #endif
1746         &GetStateAllocator());
1747     }
1748
1749     virtual void DestroySchemaValidator(ISchemaValidator* validator) {
1750         GenericSchemaValidator* v = static_cast<GenericSchemaValidator*>(validator);
1751         v->~GenericSchemaValidator();
1752         StateAllocator::Free(v);
1753     }
1754
1755     virtual void* CreateHasher() {
1756         return new (GetStateAllocator().Malloc(sizeof(HasherType))) HasherType(&GetStateAllocator());
1757     }
1758
1759     virtual uint64_t GetHashCode(void* hasher) {
1760         return static_cast<HasherType*>(hasher)->GetHashCode();
1761     }
1762
1763     virtual void DestroryHasher(void* hasher) {
1764         HasherType* h = static_cast<HasherType*>(hasher);
1765         h->~HasherType();
1766         StateAllocator::Free(h);
1767     }
1768
1769     virtual void* MallocState(size_t size) {
1770         return GetStateAllocator().Malloc(size);
1771     }
1772
1773     virtual void FreeState(void* p) {
1774         return StateAllocator::Free(p);
1775     }
1776
1777 private:
1778     typedef typename SchemaType::Context Context;
1779     typedef GenericValue<UTF8<>, StateAllocator> HashCodeArray;
1780     typedef internal::Hasher<EncodingType, StateAllocator> HasherType;
1781
1782     GenericSchemaValidator(
1783         const SchemaDocumentType& schemaDocument,
1784         const SchemaType& root,
1785 #if RAPIDJSON_SCHEMA_VERBOSE
1786         unsigned depth,
1787 #endif
1788         StateAllocator* allocator = 0,
1789         size_t schemaStackCapacity = kDefaultSchemaStackCapacity,
1790         size_t documentStackCapacity = kDefaultDocumentStackCapacity)
1791         :
1792         schemaDocument_(&schemaDocument),
1793         root_(root),
1794         outputHandler_(GetNullHandler()),
1795         stateAllocator_(allocator),
1796         ownStateAllocator_(0),
1797         schemaStack_(allocator, schemaStackCapacity),
1798         documentStack_(allocator, documentStackCapacity),
1799         valid_(true)
1800 #if RAPIDJSON_SCHEMA_VERBOSE
1801         , depth_(depth)
1802 #endif
1803     {
1804     }
1805
1806     StateAllocator& GetStateAllocator() {
1807         if (!stateAllocator_)
1808             stateAllocator_ = ownStateAllocator_ = RAPIDJSON_NEW(StateAllocator());
1809         return *stateAllocator_;
1810     }
1811
1812     bool BeginValue() {
1813         if (schemaStack_.Empty())
1814             PushSchema(root_);
1815         else {
1816             if (CurrentContext().inArray)
1817                 internal::TokenHelper<internal::Stack<StateAllocator>, Ch>::AppendIndexToken(documentStack_, CurrentContext().arrayElementIndex);
1818
1819             if (!CurrentSchema().BeginValue(CurrentContext()))
1820                 return false;
1821
1822             SizeType count = CurrentContext().patternPropertiesSchemaCount;
1823             const SchemaType** sa = CurrentContext().patternPropertiesSchemas;
1824             typename Context::PatternValidatorType patternValidatorType = CurrentContext().valuePatternValidatorType;
1825             bool valueUniqueness = CurrentContext().valueUniqueness;
1826             if (CurrentContext().valueSchema)
1827                 PushSchema(*CurrentContext().valueSchema);
1828
1829             if (count > 0) {
1830                 CurrentContext().objectPatternValidatorType = patternValidatorType;
1831                 ISchemaValidator**& va = CurrentContext().patternPropertiesValidators;
1832                 SizeType& validatorCount = CurrentContext().patternPropertiesValidatorCount;
1833                 va = static_cast<ISchemaValidator**>(MallocState(sizeof(ISchemaValidator*) * count));
1834                 for (SizeType i = 0; i < count; i++)
1835                     va[validatorCount++] = CreateSchemaValidator(*sa[i]);
1836             }
1837
1838             CurrentContext().arrayUniqueness = valueUniqueness;
1839         }
1840         return true;
1841     }
1842
1843     bool EndValue() {
1844         if (!CurrentSchema().EndValue(CurrentContext()))
1845             return false;
1846
1847 #if RAPIDJSON_SCHEMA_VERBOSE
1848         GenericStringBuffer<EncodingType> sb;
1849         schemaDocument_->GetPointer(&CurrentSchema()).Stringify(sb);
1850
1851         *documentStack_.template Push<Ch>() = '\0';
1852         documentStack_.template Pop<Ch>(1);
1853         internal::PrintValidatorPointers(depth_, sb.GetString(), documentStack_.template Bottom<Ch>());
1854 #endif
1855
1856         uint64_t h = CurrentContext().arrayUniqueness ? static_cast<HasherType*>(CurrentContext().hasher)->GetHashCode() : 0;
1857
1858         PopSchema();
1859
1860         if (!schemaStack_.Empty()) {
1861             Context& context = CurrentContext();
1862             if (context.valueUniqueness) {
1863                 HashCodeArray* a = static_cast<HashCodeArray*>(context.arrayElementHashCodes);
1864                 if (!a)
1865                     CurrentContext().arrayElementHashCodes = a = new (GetStateAllocator().Malloc(sizeof(HashCodeArray))) HashCodeArray(kArrayType);
1866                 for (typename HashCodeArray::ConstValueIterator itr = a->Begin(); itr != a->End(); ++itr)
1867                     if (itr->GetUint64() == h)
1868                         RAPIDJSON_INVALID_KEYWORD_RETURN(SchemaType::GetUniqueItemsString());
1869                 a->PushBack(h, GetStateAllocator());
1870             }
1871         }
1872
1873         // Remove the last token of document pointer
1874         while (!documentStack_.Empty() && *documentStack_.template Pop<Ch>(1) != '/')
1875             ;
1876
1877         return true;
1878     }
1879
1880     void AppendToken(const Ch* str, SizeType len) {
1881         documentStack_.template Reserve<Ch>(1 + len * 2); // worst case all characters are escaped as two characters
1882         *documentStack_.template PushUnsafe<Ch>() = '/';
1883         for (SizeType i = 0; i < len; i++) {
1884             if (str[i] == '~') {
1885                 *documentStack_.template PushUnsafe<Ch>() = '~';
1886                 *documentStack_.template PushUnsafe<Ch>() = '0';
1887             }
1888             else if (str[i] == '/') {
1889                 *documentStack_.template PushUnsafe<Ch>() = '~';
1890                 *documentStack_.template PushUnsafe<Ch>() = '1';
1891             }
1892             else
1893                 *documentStack_.template PushUnsafe<Ch>() = str[i];
1894         }
1895     }
1896
1897     RAPIDJSON_FORCEINLINE void PushSchema(const SchemaType& schema) { new (schemaStack_.template Push<Context>()) Context(*this, &schema); }
1898
1899     RAPIDJSON_FORCEINLINE void PopSchema() {
1900         Context* c = schemaStack_.template Pop<Context>(1);
1901         if (HashCodeArray* a = static_cast<HashCodeArray*>(c->arrayElementHashCodes)) {
1902             a->~HashCodeArray();
1903             StateAllocator::Free(a);
1904         }
1905         c->~Context();
1906     }
1907
1908     const SchemaType& CurrentSchema() const { return *schemaStack_.template Top<Context>()->schema; }
1909     Context& CurrentContext() { return *schemaStack_.template Top<Context>(); }
1910     const Context& CurrentContext() const { return *schemaStack_.template Top<Context>(); }
1911
1912     static OutputHandler& GetNullHandler() {
1913         static OutputHandler nullHandler;
1914         return nullHandler;
1915     }
1916
1917     static const size_t kDefaultSchemaStackCapacity = 1024;
1918     static const size_t kDefaultDocumentStackCapacity = 256;
1919     const SchemaDocumentType* schemaDocument_;
1920     const SchemaType& root_;
1921     OutputHandler& outputHandler_;
1922     StateAllocator* stateAllocator_;
1923     StateAllocator* ownStateAllocator_;
1924     internal::Stack<StateAllocator> schemaStack_;    //!< stack to store the current path of schema (BaseSchemaType *)
1925     internal::Stack<StateAllocator> documentStack_;  //!< stack to store the current path of validating document (Ch)
1926     bool valid_;
1927 #if RAPIDJSON_SCHEMA_VERBOSE
1928     unsigned depth_;
1929 #endif
1930 };
1931
1932 typedef GenericSchemaValidator<SchemaDocument> SchemaValidator;
1933
1934 ///////////////////////////////////////////////////////////////////////////////
1935 // SchemaValidatingReader
1936
1937 //! A helper class for parsing with validation.
1938 /*!
1939     This helper class is a functor, designed as a parameter of \ref GenericDocument::Populate().
1940
1941     \tparam parseFlags Combination of \ref ParseFlag.
1942     \tparam InputStream Type of input stream, implementing Stream concept.
1943     \tparam SourceEncoding Encoding of the input stream.
1944     \tparam SchemaDocumentType Type of schema document.
1945     \tparam StackAllocator Allocator type for stack.
1946 */
1947 template <
1948     unsigned parseFlags,
1949     typename InputStream,
1950     typename SourceEncoding,
1951     typename SchemaDocumentType = SchemaDocument,
1952     typename StackAllocator = CrtAllocator>
1953 class SchemaValidatingReader {
1954 public:
1955     typedef typename SchemaDocumentType::PointerType PointerType;
1956     typedef typename InputStream::Ch Ch;
1957
1958     //! Constructor
1959     /*!
1960         \param is Input stream.
1961         \param sd Schema document.
1962     */
1963     SchemaValidatingReader(InputStream& is, const SchemaDocumentType& sd) : is_(is), sd_(sd), invalidSchemaKeyword_(), isValid_(true) {}
1964
1965     template <typename Handler>
1966     bool operator()(Handler& handler) {
1967         GenericReader<SourceEncoding, typename SchemaDocumentType::EncodingType, StackAllocator> reader;
1968         GenericSchemaValidator<SchemaDocumentType, Handler> validator(sd_, handler);
1969         parseResult_ = reader.template Parse<parseFlags>(is_, validator);
1970
1971         isValid_ = validator.IsValid();
1972         if (isValid_) {
1973             invalidSchemaPointer_ = PointerType();
1974             invalidSchemaKeyword_ = 0;
1975             invalidDocumentPointer_ = PointerType();
1976         }
1977         else {
1978             invalidSchemaPointer_ = validator.GetInvalidSchemaPointer();
1979             invalidSchemaKeyword_ = validator.GetInvalidSchemaKeyword();
1980             invalidDocumentPointer_ = validator.GetInvalidDocumentPointer();
1981         }
1982
1983         return parseResult_;
1984     }
1985
1986     const ParseResult& GetParseResult() const { return parseResult_; }
1987     bool IsValid() const { return isValid_; }
1988     const PointerType& GetInvalidSchemaPointer() const { return invalidSchemaPointer_; }
1989     const Ch* GetInvalidSchemaKeyword() const { return invalidSchemaKeyword_; }
1990     const PointerType& GetInvalidDocumentPointer() const { return invalidDocumentPointer_; }
1991
1992 private:
1993     InputStream& is_;
1994     const SchemaDocumentType& sd_;
1995
1996     ParseResult parseResult_;
1997     PointerType invalidSchemaPointer_;
1998     const Ch* invalidSchemaKeyword_;
1999     PointerType invalidDocumentPointer_;
2000     bool isValid_;
2001 };
2002
2003 RAPIDJSON_NAMESPACE_END
2004 RAPIDJSON_DIAG_POP
2005
2006 #endif // RAPIDJSON_SCHEMA_H_