Add missing curly brackets in STDREGEX's CreatePattern().
[rapidjson.git] / 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 "stringbuffer.h"
21 #include <cmath> // abs, floor
22
23 #if !defined(RAPIDJSON_SCHEMA_USE_INTERNALREGEX)
24 #define RAPIDJSON_SCHEMA_USE_INTERNALREGEX 1
25 #else
26 #define RAPIDJSON_SCHEMA_USE_INTERNALREGEX 0
27 #endif
28
29 #if !RAPIDJSON_SCHEMA_USE_INTERNALREGEX && defined(RAPIDJSON_SCHEMA_USE_STDREGEX) && (__cplusplus >=201103L || (defined(_MSC_VER) && _MSC_VER >= 1800))
30 #define RAPIDJSON_SCHEMA_USE_STDREGEX 1
31 #else
32 #define RAPIDJSON_SCHEMA_USE_STDREGEX 0
33 #endif
34
35 #if RAPIDJSON_SCHEMA_USE_INTERNALREGEX
36 #include "internal/regex.h"
37 #elif RAPIDJSON_SCHEMA_USE_STDREGEX
38 #include <regex>
39 #endif
40
41 #if RAPIDJSON_SCHEMA_USE_INTERNALREGEX || RAPIDJSON_SCHEMA_USE_STDREGEX
42 #define RAPIDJSON_SCHEMA_HAS_REGEX 1
43 #else
44 #define RAPIDJSON_SCHEMA_HAS_REGEX 0
45 #endif
46
47 #ifndef RAPIDJSON_SCHEMA_VERBOSE
48 #define RAPIDJSON_SCHEMA_VERBOSE 0
49 #endif
50
51 #if RAPIDJSON_SCHEMA_VERBOSE
52 #include "stringbuffer.h"
53 #endif
54
55 RAPIDJSON_DIAG_PUSH
56
57 #if defined(__GNUC__)
58 RAPIDJSON_DIAG_OFF(effc++)
59 #endif
60
61 #ifdef __clang__
62 RAPIDJSON_DIAG_OFF(weak-vtables)
63 RAPIDJSON_DIAG_OFF(exit-time-destructors)
64 RAPIDJSON_DIAG_OFF(c++98-compat-pedantic)
65 RAPIDJSON_DIAG_OFF(variadic-macros)
66 #elif defined(_MSC_VER)
67 RAPIDJSON_DIAG_OFF(4512) // assignment operator could not be generated
68 #endif
69
70 RAPIDJSON_NAMESPACE_BEGIN
71
72 ///////////////////////////////////////////////////////////////////////////////
73 // Verbose Utilities
74
75 #if RAPIDJSON_SCHEMA_VERBOSE
76
77 namespace internal {
78
79 inline void PrintInvalidKeyword(const char* keyword) {
80     printf("Fail keyword: %s\n", keyword);
81 }
82
83 inline void PrintInvalidKeyword(const wchar_t* keyword) {
84     wprintf(L"Fail keyword: %ls\n", keyword);
85 }
86
87 inline void PrintInvalidDocument(const char* document) {
88     printf("Fail document: %s\n\n", document);
89 }
90
91 inline void PrintInvalidDocument(const wchar_t* document) {
92     wprintf(L"Fail document: %ls\n\n", document);
93 }
94
95 inline void PrintValidatorPointers(unsigned depth, const char* s, const char* d) {
96     printf("S: %*s%s\nD: %*s%s\n\n", depth * 4, " ", s, depth * 4, " ", d);
97 }
98
99 inline void PrintValidatorPointers(unsigned depth, const wchar_t* s, const wchar_t* d) {
100     wprintf(L"S: %*ls%ls\nD: %*ls%ls\n\n", depth * 4, L" ", s, depth * 4, L" ", d);
101 }
102
103 } // namespace internal
104
105 #endif // RAPIDJSON_SCHEMA_VERBOSE
106
107 ///////////////////////////////////////////////////////////////////////////////
108 // RAPIDJSON_INVALID_KEYWORD_RETURN
109
110 #if RAPIDJSON_SCHEMA_VERBOSE
111 #define RAPIDJSON_INVALID_KEYWORD_VERBOSE(keyword) internal::PrintInvalidKeyword(keyword)
112 #else
113 #define RAPIDJSON_INVALID_KEYWORD_VERBOSE(keyword)
114 #endif
115
116 #define RAPIDJSON_INVALID_KEYWORD_RETURN(keyword)\
117 RAPIDJSON_MULTILINEMACRO_BEGIN\
118     context.invalidKeyword = keyword.GetString();\
119     RAPIDJSON_INVALID_KEYWORD_VERBOSE(keyword.GetString());\
120     return false;\
121 RAPIDJSON_MULTILINEMACRO_END
122
123 ///////////////////////////////////////////////////////////////////////////////
124 // Forward declarations
125
126 template <typename ValueType, typename Allocator>
127 class GenericSchemaDocument;
128
129 namespace internal {
130
131 template <typename SchemaDocumentType>
132 class Schema;
133
134 ///////////////////////////////////////////////////////////////////////////////
135 // ISchemaValidator
136
137 class ISchemaValidator {
138 public:
139     virtual ~ISchemaValidator() {}
140     virtual bool IsValid() const = 0;
141 };
142
143 ///////////////////////////////////////////////////////////////////////////////
144 // ISchemaStateFactory
145
146 template <typename SchemaType>
147 class ISchemaStateFactory {
148 public:
149     virtual ~ISchemaStateFactory() {}
150     virtual ISchemaValidator* CreateSchemaValidator(const SchemaType&) = 0;
151     virtual void DestroySchemaValidator(ISchemaValidator* validator) = 0;
152     virtual void* CreateHasher() = 0;
153     virtual uint64_t GetHashCode(void* hasher) = 0;
154     virtual void DestroryHasher(void* hasher) = 0;
155     virtual void* MallocState(size_t size) = 0;
156     virtual void FreeState(void* p) = 0;
157 };
158
159 ///////////////////////////////////////////////////////////////////////////////
160 // IValidationErrorHandler
161
162 template <typename SchemaType>
163 class IValidationErrorHandler {
164 public:
165     typedef typename SchemaType::Ch Ch;
166     typedef typename SchemaType::SValue SValue;
167
168     virtual ~IValidationErrorHandler() {}
169
170     virtual void NotMultipleOf(int64_t actual, const SValue& expected) = 0;
171     virtual void NotMultipleOf(uint64_t actual, const SValue& expected) = 0;
172     virtual void NotMultipleOf(double actual, const SValue& expected) = 0;
173     virtual void AboveMaximum(int64_t actual, const SValue& expected, bool exclusive) = 0;
174     virtual void AboveMaximum(uint64_t actual, const SValue& expected, bool exclusive) = 0;
175     virtual void AboveMaximum(double actual, const SValue& expected, bool exclusive) = 0;
176     virtual void BelowMinimum(int64_t actual, const SValue& expected, bool exclusive) = 0;
177     virtual void BelowMinimum(uint64_t actual, const SValue& expected, bool exclusive) = 0;
178     virtual void BelowMinimum(double actual, const SValue& expected, bool exclusive) = 0;
179
180     virtual void TooLong(const Ch* str, SizeType length, SizeType expected) = 0;
181     virtual void TooShort(const Ch* str, SizeType length, SizeType expected) = 0;
182     virtual void DoesNotMatch(const Ch* str, SizeType length) = 0;
183
184     virtual void DisallowedItem(SizeType index) = 0;
185     virtual void TooFewItems(SizeType actualCount, SizeType expectedCount) = 0;
186     virtual void TooManyItems(SizeType actualCount, SizeType expectedCount) = 0;
187     virtual void DuplicateItems(SizeType index1, SizeType index2) = 0;
188
189     virtual void TooManyProperties(SizeType actualCount, SizeType expectedCount) = 0;
190     virtual void TooFewProperties(SizeType actualCount, SizeType expectedCount) = 0;
191     virtual void StartMissingProperties() = 0;
192     virtual void AddMissingProperty(const SValue& name) = 0;
193     virtual bool EndMissingProperties() = 0;
194     virtual void PropertyViolations(ISchemaValidator** subvalidators, SizeType count) = 0;
195     virtual void DisallowedProperty(const Ch* name, SizeType length) = 0;
196
197     virtual void StartDependencyErrors() = 0;
198     virtual void StartMissingDependentProperties() = 0;
199     virtual void AddMissingDependentProperty(const SValue& targetName) = 0;
200     virtual void EndMissingDependentProperties(const SValue& sourceName) = 0;
201     virtual void AddDependencySchemaError(const SValue& souceName, ISchemaValidator* subvalidator) = 0;
202     virtual bool EndDependencyErrors() = 0;
203
204     virtual void DisallowedValue() = 0;
205     virtual void StartDisallowedType() = 0;
206     virtual void AddExpectedType(const typename SchemaType::ValueType& expectedType) = 0;
207     virtual void EndDisallowedType(const typename SchemaType::ValueType& actualType) = 0;
208     virtual void NotAllOf(ISchemaValidator** subvalidators, SizeType count) = 0;
209     virtual void NoneOf(ISchemaValidator** subvalidators, SizeType count) = 0;
210     virtual void NotOneOf(ISchemaValidator** subvalidators, SizeType count) = 0;
211     virtual void Disallowed() = 0;
212 };
213
214
215 ///////////////////////////////////////////////////////////////////////////////
216 // Hasher
217
218 // For comparison of compound value
219 template<typename Encoding, typename Allocator>
220 class Hasher {
221 public:
222     typedef typename Encoding::Ch Ch;
223
224     Hasher(Allocator* allocator = 0, size_t stackCapacity = kDefaultSize) : stack_(allocator, stackCapacity) {}
225
226     bool Null() { return WriteType(kNullType); }
227     bool Bool(bool b) { return WriteType(b ? kTrueType : kFalseType); }
228     bool Int(int i) { Number n; n.u.i = i; n.d = static_cast<double>(i); return WriteNumber(n); }
229     bool Uint(unsigned u) { Number n; n.u.u = u; n.d = static_cast<double>(u); return WriteNumber(n); }
230     bool Int64(int64_t i) { Number n; n.u.i = i; n.d = static_cast<double>(i); return WriteNumber(n); }
231     bool Uint64(uint64_t u) { Number n; n.u.u = u; n.d = static_cast<double>(u); return WriteNumber(n); }
232     bool Double(double d) { 
233         Number n; 
234         if (d < 0) n.u.i = static_cast<int64_t>(d);
235         else       n.u.u = static_cast<uint64_t>(d); 
236         n.d = d;
237         return WriteNumber(n);
238     }
239
240     bool RawNumber(const Ch* str, SizeType len, bool) {
241         WriteBuffer(kNumberType, str, len * sizeof(Ch));
242         return true;
243     }
244
245     bool String(const Ch* str, SizeType len, bool) {
246         WriteBuffer(kStringType, str, len * sizeof(Ch));
247         return true;
248     }
249
250     bool StartObject() { return true; }
251     bool Key(const Ch* str, SizeType len, bool copy) { return String(str, len, copy); }
252     bool EndObject(SizeType memberCount) { 
253         uint64_t h = Hash(0, kObjectType);
254         uint64_t* kv = stack_.template Pop<uint64_t>(memberCount * 2);
255         for (SizeType i = 0; i < memberCount; i++)
256             h ^= Hash(kv[i * 2], kv[i * 2 + 1]);  // Use xor to achieve member order insensitive
257         *stack_.template Push<uint64_t>() = h;
258         return true;
259     }
260     
261     bool StartArray() { return true; }
262     bool EndArray(SizeType elementCount) { 
263         uint64_t h = Hash(0, kArrayType);
264         uint64_t* e = stack_.template Pop<uint64_t>(elementCount);
265         for (SizeType i = 0; i < elementCount; i++)
266             h = Hash(h, e[i]); // Use hash to achieve element order sensitive
267         *stack_.template Push<uint64_t>() = h;
268         return true;
269     }
270
271     bool IsValid() const { return stack_.GetSize() == sizeof(uint64_t); }
272
273     uint64_t GetHashCode() const {
274         RAPIDJSON_ASSERT(IsValid());
275         return *stack_.template Top<uint64_t>();
276     }
277
278 private:
279     static const size_t kDefaultSize = 256;
280     struct Number {
281         union U {
282             uint64_t u;
283             int64_t i;
284         }u;
285         double d;
286     };
287
288     bool WriteType(Type type) { return WriteBuffer(type, 0, 0); }
289     
290     bool WriteNumber(const Number& n) { return WriteBuffer(kNumberType, &n, sizeof(n)); }
291     
292     bool WriteBuffer(Type type, const void* data, size_t len) {
293         // FNV-1a from http://isthe.com/chongo/tech/comp/fnv/
294         uint64_t h = Hash(RAPIDJSON_UINT64_C2(0x84222325, 0xcbf29ce4), type);
295         const unsigned char* d = static_cast<const unsigned char*>(data);
296         for (size_t i = 0; i < len; i++)
297             h = Hash(h, d[i]);
298         *stack_.template Push<uint64_t>() = h;
299         return true;
300     }
301
302     static uint64_t Hash(uint64_t h, uint64_t d) {
303         static const uint64_t kPrime = RAPIDJSON_UINT64_C2(0x00000100, 0x000001b3);
304         h ^= d;
305         h *= kPrime;
306         return h;
307     }
308
309     Stack<Allocator> stack_;
310 };
311
312 ///////////////////////////////////////////////////////////////////////////////
313 // SchemaValidationContext
314
315 template <typename SchemaDocumentType>
316 struct SchemaValidationContext {
317     typedef Schema<SchemaDocumentType> SchemaType;
318     typedef ISchemaStateFactory<SchemaType> SchemaValidatorFactoryType;
319     typedef IValidationErrorHandler<SchemaType> ErrorHandlerType;
320     typedef typename SchemaType::ValueType ValueType;
321     typedef typename ValueType::Ch Ch;
322
323     enum PatternValidatorType {
324         kPatternValidatorOnly,
325         kPatternValidatorWithProperty,
326         kPatternValidatorWithAdditionalProperty
327     };
328
329     SchemaValidationContext(SchemaValidatorFactoryType& f, ErrorHandlerType& eh, const SchemaType* s) :
330         factory(f),
331         error_handler(eh),
332         schema(s),
333         valueSchema(),
334         invalidKeyword(),
335         hasher(),
336         arrayElementHashCodes(),
337         validators(),
338         validatorCount(),
339         patternPropertiesValidators(),
340         patternPropertiesValidatorCount(),
341         patternPropertiesSchemas(),
342         patternPropertiesSchemaCount(),
343         valuePatternValidatorType(kPatternValidatorOnly),
344         propertyExist(),
345         inArray(false),
346         valueUniqueness(false),
347         arrayUniqueness(false)
348     {
349     }
350
351     ~SchemaValidationContext() {
352         if (hasher)
353             factory.DestroryHasher(hasher);
354         if (validators) {
355             for (SizeType i = 0; i < validatorCount; i++)
356                 factory.DestroySchemaValidator(validators[i]);
357             factory.FreeState(validators);
358         }
359         if (patternPropertiesValidators) {
360             for (SizeType i = 0; i < patternPropertiesValidatorCount; i++)
361                 factory.DestroySchemaValidator(patternPropertiesValidators[i]);
362             factory.FreeState(patternPropertiesValidators);
363         }
364         if (patternPropertiesSchemas)
365             factory.FreeState(patternPropertiesSchemas);
366         if (propertyExist)
367             factory.FreeState(propertyExist);
368     }
369
370     SchemaValidatorFactoryType& factory;
371     ErrorHandlerType& error_handler;
372     const SchemaType* schema;
373     const SchemaType* valueSchema;
374     const Ch* invalidKeyword;
375     void* hasher; // Only validator access
376     void* arrayElementHashCodes; // Only validator access this
377     ISchemaValidator** validators;
378     SizeType validatorCount;
379     ISchemaValidator** patternPropertiesValidators;
380     SizeType patternPropertiesValidatorCount;
381     const SchemaType** patternPropertiesSchemas;
382     SizeType patternPropertiesSchemaCount;
383     PatternValidatorType valuePatternValidatorType;
384     PatternValidatorType objectPatternValidatorType;
385     SizeType arrayElementIndex;
386     bool* propertyExist;
387     bool inArray;
388     bool valueUniqueness;
389     bool arrayUniqueness;
390 };
391
392 ///////////////////////////////////////////////////////////////////////////////
393 // Schema
394
395 template <typename SchemaDocumentType>
396 class Schema {
397 public:
398     typedef typename SchemaDocumentType::ValueType ValueType;
399     typedef typename SchemaDocumentType::AllocatorType AllocatorType;
400     typedef typename SchemaDocumentType::PointerType PointerType;
401     typedef typename ValueType::EncodingType EncodingType;
402     typedef typename EncodingType::Ch Ch;
403     typedef SchemaValidationContext<SchemaDocumentType> Context;
404     typedef Schema<SchemaDocumentType> SchemaType;
405     typedef GenericValue<EncodingType, AllocatorType> SValue;
406     typedef IValidationErrorHandler<Schema> ErrorHandler;
407     friend class GenericSchemaDocument<ValueType, AllocatorType>;
408
409     Schema(SchemaDocumentType* schemaDocument, const PointerType& p, const ValueType& value, const ValueType& document, AllocatorType* allocator) :
410         allocator_(allocator),
411         uri_(schemaDocument->GetURI(), *allocator),
412         pointer_(p, allocator),
413         typeless_(schemaDocument->GetTypeless()),
414         enum_(),
415         enumCount_(),
416         not_(),
417         type_((1 << kTotalSchemaType) - 1), // typeless
418         validatorCount_(),
419         notValidatorIndex_(),
420         properties_(),
421         additionalPropertiesSchema_(),
422         patternProperties_(),
423         patternPropertyCount_(),
424         propertyCount_(),
425         minProperties_(),
426         maxProperties_(SizeType(~0)),
427         additionalProperties_(true),
428         hasDependencies_(),
429         hasRequired_(),
430         hasSchemaDependencies_(),
431         additionalItemsSchema_(),
432         itemsList_(),
433         itemsTuple_(),
434         itemsTupleCount_(),
435         minItems_(),
436         maxItems_(SizeType(~0)),
437         additionalItems_(true),
438         uniqueItems_(false),
439         pattern_(),
440         minLength_(0),
441         maxLength_(~SizeType(0)),
442         exclusiveMinimum_(false),
443         exclusiveMaximum_(false),
444         defaultValueLength_(0)
445     {
446         typedef typename SchemaDocumentType::ValueType ValueType;
447         typedef typename ValueType::ConstValueIterator ConstValueIterator;
448         typedef typename ValueType::ConstMemberIterator ConstMemberIterator;
449
450         if (!value.IsObject())
451             return;
452
453         if (const ValueType* v = GetMember(value, GetTypeString())) {
454             type_ = 0;
455             if (v->IsString())
456                 AddType(*v);
457             else if (v->IsArray())
458                 for (ConstValueIterator itr = v->Begin(); itr != v->End(); ++itr)
459                     AddType(*itr);
460         }
461
462         if (const ValueType* v = GetMember(value, GetEnumString()))
463             if (v->IsArray() && v->Size() > 0) {
464                 enum_ = static_cast<uint64_t*>(allocator_->Malloc(sizeof(uint64_t) * v->Size()));
465                 for (ConstValueIterator itr = v->Begin(); itr != v->End(); ++itr) {
466                     typedef Hasher<EncodingType, MemoryPoolAllocator<> > EnumHasherType;
467                     char buffer[256u + 24];
468                     MemoryPoolAllocator<> hasherAllocator(buffer, sizeof(buffer));
469                     EnumHasherType h(&hasherAllocator, 256);
470                     itr->Accept(h);
471                     enum_[enumCount_++] = h.GetHashCode();
472                 }
473             }
474
475         if (schemaDocument) {
476             AssignIfExist(allOf_, *schemaDocument, p, value, GetAllOfString(), document);
477             AssignIfExist(anyOf_, *schemaDocument, p, value, GetAnyOfString(), document);
478             AssignIfExist(oneOf_, *schemaDocument, p, value, GetOneOfString(), document);
479         }
480
481         if (const ValueType* v = GetMember(value, GetNotString())) {
482             schemaDocument->CreateSchema(&not_, p.Append(GetNotString(), allocator_), *v, document);
483             notValidatorIndex_ = validatorCount_;
484             validatorCount_++;
485         }
486
487         // Object
488
489         const ValueType* properties = GetMember(value, GetPropertiesString());
490         const ValueType* required = GetMember(value, GetRequiredString());
491         const ValueType* dependencies = GetMember(value, GetDependenciesString());
492         {
493             // Gather properties from properties/required/dependencies
494             SValue allProperties(kArrayType);
495
496             if (properties && properties->IsObject())
497                 for (ConstMemberIterator itr = properties->MemberBegin(); itr != properties->MemberEnd(); ++itr)
498                     AddUniqueElement(allProperties, itr->name);
499             
500             if (required && required->IsArray())
501                 for (ConstValueIterator itr = required->Begin(); itr != required->End(); ++itr)
502                     if (itr->IsString())
503                         AddUniqueElement(allProperties, *itr);
504
505             if (dependencies && dependencies->IsObject())
506                 for (ConstMemberIterator itr = dependencies->MemberBegin(); itr != dependencies->MemberEnd(); ++itr) {
507                     AddUniqueElement(allProperties, itr->name);
508                     if (itr->value.IsArray())
509                         for (ConstValueIterator i = itr->value.Begin(); i != itr->value.End(); ++i)
510                             if (i->IsString())
511                                 AddUniqueElement(allProperties, *i);
512                 }
513
514             if (allProperties.Size() > 0) {
515                 propertyCount_ = allProperties.Size();
516                 properties_ = static_cast<Property*>(allocator_->Malloc(sizeof(Property) * propertyCount_));
517                 for (SizeType i = 0; i < propertyCount_; i++) {
518                     new (&properties_[i]) Property();
519                     properties_[i].name = allProperties[i];
520                     properties_[i].schema = typeless_;
521                 }
522             }
523         }
524
525         if (properties && properties->IsObject()) {
526             PointerType q = p.Append(GetPropertiesString(), allocator_);
527             for (ConstMemberIterator itr = properties->MemberBegin(); itr != properties->MemberEnd(); ++itr) {
528                 SizeType index;
529                 if (FindPropertyIndex(itr->name, &index))
530                     schemaDocument->CreateSchema(&properties_[index].schema, q.Append(itr->name, allocator_), itr->value, document);
531             }
532         }
533
534         if (const ValueType* v = GetMember(value, GetPatternPropertiesString())) {
535             PointerType q = p.Append(GetPatternPropertiesString(), allocator_);
536             patternProperties_ = static_cast<PatternProperty*>(allocator_->Malloc(sizeof(PatternProperty) * v->MemberCount()));
537             patternPropertyCount_ = 0;
538
539             for (ConstMemberIterator itr = v->MemberBegin(); itr != v->MemberEnd(); ++itr) {
540                 new (&patternProperties_[patternPropertyCount_]) PatternProperty();
541                 patternProperties_[patternPropertyCount_].pattern = CreatePattern(itr->name);
542                 schemaDocument->CreateSchema(&patternProperties_[patternPropertyCount_].schema, q.Append(itr->name, allocator_), itr->value, document);
543                 patternPropertyCount_++;
544             }
545         }
546
547         if (required && required->IsArray())
548             for (ConstValueIterator itr = required->Begin(); itr != required->End(); ++itr)
549                 if (itr->IsString()) {
550                     SizeType index;
551                     if (FindPropertyIndex(*itr, &index)) {
552                         properties_[index].required = true;
553                         hasRequired_ = true;
554                     }
555                 }
556
557         if (dependencies && dependencies->IsObject()) {
558             PointerType q = p.Append(GetDependenciesString(), allocator_);
559             hasDependencies_ = true;
560             for (ConstMemberIterator itr = dependencies->MemberBegin(); itr != dependencies->MemberEnd(); ++itr) {
561                 SizeType sourceIndex;
562                 if (FindPropertyIndex(itr->name, &sourceIndex)) {
563                     if (itr->value.IsArray()) {
564                         properties_[sourceIndex].dependencies = static_cast<bool*>(allocator_->Malloc(sizeof(bool) * propertyCount_));
565                         std::memset(properties_[sourceIndex].dependencies, 0, sizeof(bool)* propertyCount_);
566                         for (ConstValueIterator targetItr = itr->value.Begin(); targetItr != itr->value.End(); ++targetItr) {
567                             SizeType targetIndex;
568                             if (FindPropertyIndex(*targetItr, &targetIndex))
569                                 properties_[sourceIndex].dependencies[targetIndex] = true;
570                         }
571                     }
572                     else if (itr->value.IsObject()) {
573                         hasSchemaDependencies_ = true;
574                         schemaDocument->CreateSchema(&properties_[sourceIndex].dependenciesSchema, q.Append(itr->name, allocator_), itr->value, document);
575                         properties_[sourceIndex].dependenciesValidatorIndex = validatorCount_;
576                         validatorCount_++;
577                     }
578                 }
579             }
580         }
581
582         if (const ValueType* v = GetMember(value, GetAdditionalPropertiesString())) {
583             if (v->IsBool())
584                 additionalProperties_ = v->GetBool();
585             else if (v->IsObject())
586                 schemaDocument->CreateSchema(&additionalPropertiesSchema_, p.Append(GetAdditionalPropertiesString(), allocator_), *v, document);
587         }
588
589         AssignIfExist(minProperties_, value, GetMinPropertiesString());
590         AssignIfExist(maxProperties_, value, GetMaxPropertiesString());
591
592         // Array
593         if (const ValueType* v = GetMember(value, GetItemsString())) {
594             PointerType q = p.Append(GetItemsString(), allocator_);
595             if (v->IsObject()) // List validation
596                 schemaDocument->CreateSchema(&itemsList_, q, *v, document);
597             else if (v->IsArray()) { // Tuple validation
598                 itemsTuple_ = static_cast<const Schema**>(allocator_->Malloc(sizeof(const Schema*) * v->Size()));
599                 SizeType index = 0;
600                 for (ConstValueIterator itr = v->Begin(); itr != v->End(); ++itr, index++)
601                     schemaDocument->CreateSchema(&itemsTuple_[itemsTupleCount_++], q.Append(index, allocator_), *itr, document);
602             }
603         }
604
605         AssignIfExist(minItems_, value, GetMinItemsString());
606         AssignIfExist(maxItems_, value, GetMaxItemsString());
607
608         if (const ValueType* v = GetMember(value, GetAdditionalItemsString())) {
609             if (v->IsBool())
610                 additionalItems_ = v->GetBool();
611             else if (v->IsObject())
612                 schemaDocument->CreateSchema(&additionalItemsSchema_, p.Append(GetAdditionalItemsString(), allocator_), *v, document);
613         }
614
615         AssignIfExist(uniqueItems_, value, GetUniqueItemsString());
616
617         // String
618         AssignIfExist(minLength_, value, GetMinLengthString());
619         AssignIfExist(maxLength_, value, GetMaxLengthString());
620
621         if (const ValueType* v = GetMember(value, GetPatternString()))
622             pattern_ = CreatePattern(*v);
623
624         // Number
625         if (const ValueType* v = GetMember(value, GetMinimumString()))
626             if (v->IsNumber())
627                 minimum_.CopyFrom(*v, *allocator_);
628
629         if (const ValueType* v = GetMember(value, GetMaximumString()))
630             if (v->IsNumber())
631                 maximum_.CopyFrom(*v, *allocator_);
632
633         AssignIfExist(exclusiveMinimum_, value, GetExclusiveMinimumString());
634         AssignIfExist(exclusiveMaximum_, value, GetExclusiveMaximumString());
635
636         if (const ValueType* v = GetMember(value, GetMultipleOfString()))
637             if (v->IsNumber() && v->GetDouble() > 0.0)
638                 multipleOf_.CopyFrom(*v, *allocator_);
639
640         // Default
641         if (const ValueType* v = GetMember(value, GetDefaultValueString()))
642             if (v->IsString())
643                 defaultValueLength_ = v->GetStringLength();
644
645     }
646
647     ~Schema() {
648         AllocatorType::Free(enum_);
649         if (properties_) {
650             for (SizeType i = 0; i < propertyCount_; i++)
651                 properties_[i].~Property();
652             AllocatorType::Free(properties_);
653         }
654         if (patternProperties_) {
655             for (SizeType i = 0; i < patternPropertyCount_; i++)
656                 patternProperties_[i].~PatternProperty();
657             AllocatorType::Free(patternProperties_);
658         }
659         AllocatorType::Free(itemsTuple_);
660 #if RAPIDJSON_SCHEMA_HAS_REGEX
661         if (pattern_) {
662             pattern_->~RegexType();
663             AllocatorType::Free(pattern_);
664         }
665 #endif
666     }
667
668     const SValue& GetURI() const {
669         return uri_;
670     }
671
672     const PointerType& GetPointer() const {
673         return pointer_;
674     }
675
676     bool BeginValue(Context& context) const {
677         if (context.inArray) {
678             if (uniqueItems_)
679                 context.valueUniqueness = true;
680
681             if (itemsList_)
682                 context.valueSchema = itemsList_;
683             else if (itemsTuple_) {
684                 if (context.arrayElementIndex < itemsTupleCount_)
685                     context.valueSchema = itemsTuple_[context.arrayElementIndex];
686                 else if (additionalItemsSchema_)
687                     context.valueSchema = additionalItemsSchema_;
688                 else if (additionalItems_)
689                     context.valueSchema = typeless_;
690                 else {
691                     context.error_handler.DisallowedItem(context.arrayElementIndex);
692                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetItemsString());
693                 }
694             }
695             else
696                 context.valueSchema = typeless_;
697
698             context.arrayElementIndex++;
699         }
700         return true;
701     }
702
703     RAPIDJSON_FORCEINLINE bool EndValue(Context& context) const {
704         if (context.patternPropertiesValidatorCount > 0) {
705             bool otherValid = false;
706             SizeType count = context.patternPropertiesValidatorCount;
707             if (context.objectPatternValidatorType != Context::kPatternValidatorOnly)
708                 otherValid = context.patternPropertiesValidators[--count]->IsValid();
709
710             bool patternValid = true;
711             for (SizeType i = 0; i < count; i++)
712                 if (!context.patternPropertiesValidators[i]->IsValid()) {
713                     patternValid = false;
714                     break;
715                 }
716
717             if (context.objectPatternValidatorType == Context::kPatternValidatorOnly) {
718                 if (!patternValid) {
719                     context.error_handler.PropertyViolations(context.patternPropertiesValidators, count);
720                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetPatternPropertiesString());
721                 }
722             }
723             else if (context.objectPatternValidatorType == Context::kPatternValidatorWithProperty) {
724                 if (!patternValid || !otherValid) {
725                     context.error_handler.PropertyViolations(context.patternPropertiesValidators, count + 1);
726                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetPatternPropertiesString());
727                 }
728             }
729             else if (!patternValid && !otherValid) { // kPatternValidatorWithAdditionalProperty)
730                 context.error_handler.PropertyViolations(context.patternPropertiesValidators, count + 1);
731                 RAPIDJSON_INVALID_KEYWORD_RETURN(GetPatternPropertiesString());
732             }
733         }
734
735         if (enum_) {
736             const uint64_t h = context.factory.GetHashCode(context.hasher);
737             for (SizeType i = 0; i < enumCount_; i++)
738                 if (enum_[i] == h)
739                     goto foundEnum;
740             context.error_handler.DisallowedValue();
741             RAPIDJSON_INVALID_KEYWORD_RETURN(GetEnumString());
742             foundEnum:;
743         }
744
745         if (allOf_.schemas)
746             for (SizeType i = allOf_.begin; i < allOf_.begin + allOf_.count; i++)
747                 if (!context.validators[i]->IsValid()) {
748                     context.error_handler.NotAllOf(&context.validators[allOf_.begin], allOf_.count);
749                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetAllOfString());
750                 }
751         
752         if (anyOf_.schemas) {
753             for (SizeType i = anyOf_.begin; i < anyOf_.begin + anyOf_.count; i++)
754                 if (context.validators[i]->IsValid())
755                     goto foundAny;
756             context.error_handler.NoneOf(&context.validators[anyOf_.begin], anyOf_.count);
757             RAPIDJSON_INVALID_KEYWORD_RETURN(GetAnyOfString());
758             foundAny:;
759         }
760
761         if (oneOf_.schemas) {
762             bool oneValid = false;
763             for (SizeType i = oneOf_.begin; i < oneOf_.begin + oneOf_.count; i++)
764                 if (context.validators[i]->IsValid()) {
765                     if (oneValid) {
766                         context.error_handler.NotOneOf(&context.validators[oneOf_.begin], oneOf_.count);
767                         RAPIDJSON_INVALID_KEYWORD_RETURN(GetOneOfString());
768                     } else
769                         oneValid = true;
770                 }
771             if (!oneValid) {
772                 context.error_handler.NotOneOf(&context.validators[oneOf_.begin], oneOf_.count);
773                 RAPIDJSON_INVALID_KEYWORD_RETURN(GetOneOfString());
774             }
775         }
776
777         if (not_ && context.validators[notValidatorIndex_]->IsValid()) {
778             context.error_handler.Disallowed();
779             RAPIDJSON_INVALID_KEYWORD_RETURN(GetNotString());
780         }
781
782         return true;
783     }
784
785     bool Null(Context& context) const {
786         if (!(type_ & (1 << kNullSchemaType))) {
787             DisallowedType(context, GetNullString());
788             RAPIDJSON_INVALID_KEYWORD_RETURN(GetTypeString());
789         }
790         return CreateParallelValidator(context);
791     }
792     
793     bool Bool(Context& context, bool) const {
794         if (!(type_ & (1 << kBooleanSchemaType))) {
795             DisallowedType(context, GetBooleanString());
796             RAPIDJSON_INVALID_KEYWORD_RETURN(GetTypeString());
797         }
798         return CreateParallelValidator(context);
799     }
800
801     bool Int(Context& context, int i) const {
802         if (!CheckInt(context, i))
803             return false;
804         return CreateParallelValidator(context);
805     }
806
807     bool Uint(Context& context, unsigned u) const {
808         if (!CheckUint(context, u))
809             return false;
810         return CreateParallelValidator(context);
811     }
812
813     bool Int64(Context& context, int64_t i) const {
814         if (!CheckInt(context, i))
815             return false;
816         return CreateParallelValidator(context);
817     }
818
819     bool Uint64(Context& context, uint64_t u) const {
820         if (!CheckUint(context, u))
821             return false;
822         return CreateParallelValidator(context);
823     }
824
825     bool Double(Context& context, double d) const {
826         if (!(type_ & (1 << kNumberSchemaType))) {
827             DisallowedType(context, GetNumberString());
828             RAPIDJSON_INVALID_KEYWORD_RETURN(GetTypeString());
829         }
830
831         if (!minimum_.IsNull() && !CheckDoubleMinimum(context, d))
832             return false;
833
834         if (!maximum_.IsNull() && !CheckDoubleMaximum(context, d))
835             return false;
836         
837         if (!multipleOf_.IsNull() && !CheckDoubleMultipleOf(context, d))
838             return false;
839         
840         return CreateParallelValidator(context);
841     }
842     
843     bool String(Context& context, const Ch* str, SizeType length, bool) const {
844         if (!(type_ & (1 << kStringSchemaType))) {
845             DisallowedType(context, GetStringString());
846             RAPIDJSON_INVALID_KEYWORD_RETURN(GetTypeString());
847         }
848
849         if (minLength_ != 0 || maxLength_ != SizeType(~0)) {
850             SizeType count;
851             if (internal::CountStringCodePoint<EncodingType>(str, length, &count)) {
852                 if (count < minLength_) {
853                     context.error_handler.TooShort(str, length, minLength_);
854                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetMinLengthString());
855                 }
856                 if (count > maxLength_) {
857                     context.error_handler.TooLong(str, length, maxLength_);
858                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetMaxLengthString());
859                 }
860             }
861         }
862
863         if (pattern_ && !IsPatternMatch(pattern_, str, length)) {
864             context.error_handler.DoesNotMatch(str, length);
865             RAPIDJSON_INVALID_KEYWORD_RETURN(GetPatternString());
866         }
867
868         return CreateParallelValidator(context);
869     }
870
871     bool StartObject(Context& context) const {
872         if (!(type_ & (1 << kObjectSchemaType))) {
873             DisallowedType(context, GetObjectString());
874             RAPIDJSON_INVALID_KEYWORD_RETURN(GetTypeString());
875         }
876
877         if (hasDependencies_ || hasRequired_) {
878             context.propertyExist = static_cast<bool*>(context.factory.MallocState(sizeof(bool) * propertyCount_));
879             std::memset(context.propertyExist, 0, sizeof(bool) * propertyCount_);
880         }
881
882         if (patternProperties_) { // pre-allocate schema array
883             SizeType count = patternPropertyCount_ + 1; // extra for valuePatternValidatorType
884             context.patternPropertiesSchemas = static_cast<const SchemaType**>(context.factory.MallocState(sizeof(const SchemaType*) * count));
885             context.patternPropertiesSchemaCount = 0;
886             std::memset(context.patternPropertiesSchemas, 0, sizeof(SchemaType*) * count);
887         }
888
889         return CreateParallelValidator(context);
890     }
891     
892     bool Key(Context& context, const Ch* str, SizeType len, bool) const {
893         if (patternProperties_) {
894             context.patternPropertiesSchemaCount = 0;
895             for (SizeType i = 0; i < patternPropertyCount_; i++)
896                 if (patternProperties_[i].pattern && IsPatternMatch(patternProperties_[i].pattern, str, len)) {
897                     context.patternPropertiesSchemas[context.patternPropertiesSchemaCount++] = patternProperties_[i].schema;
898                     context.valueSchema = typeless_;
899                 }
900         }
901
902         SizeType index;
903         if (FindPropertyIndex(ValueType(str, len).Move(), &index)) {
904             if (context.patternPropertiesSchemaCount > 0) {
905                 context.patternPropertiesSchemas[context.patternPropertiesSchemaCount++] = properties_[index].schema;
906                 context.valueSchema = typeless_;
907                 context.valuePatternValidatorType = Context::kPatternValidatorWithProperty;
908             }
909             else
910                 context.valueSchema = properties_[index].schema;
911
912             if (context.propertyExist)
913                 context.propertyExist[index] = true;
914
915             return true;
916         }
917
918         if (additionalPropertiesSchema_) {
919             if (additionalPropertiesSchema_ && context.patternPropertiesSchemaCount > 0) {
920                 context.patternPropertiesSchemas[context.patternPropertiesSchemaCount++] = additionalPropertiesSchema_;
921                 context.valueSchema = typeless_;
922                 context.valuePatternValidatorType = Context::kPatternValidatorWithAdditionalProperty;
923             }
924             else
925                 context.valueSchema = additionalPropertiesSchema_;
926             return true;
927         }
928         else if (additionalProperties_) {
929             context.valueSchema = typeless_;
930             return true;
931         }
932
933         if (context.patternPropertiesSchemaCount == 0) { // patternProperties are not additional properties
934             context.error_handler.DisallowedProperty(str, len);
935             RAPIDJSON_INVALID_KEYWORD_RETURN(GetAdditionalPropertiesString());
936         }
937
938         return true;
939     }
940
941     bool EndObject(Context& context, SizeType memberCount) const {
942         if (hasRequired_) {
943             context.error_handler.StartMissingProperties();
944             for (SizeType index = 0; index < propertyCount_; index++)
945                 if (properties_[index].required && !context.propertyExist[index])
946                     if (properties_[index].schema->defaultValueLength_ == 0 )
947                         context.error_handler.AddMissingProperty(properties_[index].name);
948             if (context.error_handler.EndMissingProperties())
949                 RAPIDJSON_INVALID_KEYWORD_RETURN(GetRequiredString());
950         }
951
952         if (memberCount < minProperties_) {
953             context.error_handler.TooFewProperties(memberCount, minProperties_);
954             RAPIDJSON_INVALID_KEYWORD_RETURN(GetMinPropertiesString());
955         }
956
957         if (memberCount > maxProperties_) {
958             context.error_handler.TooManyProperties(memberCount, maxProperties_);
959             RAPIDJSON_INVALID_KEYWORD_RETURN(GetMaxPropertiesString());
960         }
961
962         if (hasDependencies_) {
963             context.error_handler.StartDependencyErrors();
964             for (SizeType sourceIndex = 0; sourceIndex < propertyCount_; sourceIndex++) {
965                 const Property& source = properties_[sourceIndex];
966                 if (context.propertyExist[sourceIndex]) {
967                     if (source.dependencies) {
968                         context.error_handler.StartMissingDependentProperties();
969                         for (SizeType targetIndex = 0; targetIndex < propertyCount_; targetIndex++)
970                             if (source.dependencies[targetIndex] && !context.propertyExist[targetIndex])
971                                 context.error_handler.AddMissingDependentProperty(properties_[targetIndex].name);
972                         context.error_handler.EndMissingDependentProperties(source.name);
973                     }
974                     else if (source.dependenciesSchema) {
975                         ISchemaValidator* dependenciesValidator = context.validators[source.dependenciesValidatorIndex];
976                         if (!dependenciesValidator->IsValid())
977                             context.error_handler.AddDependencySchemaError(source.name, dependenciesValidator);
978                     }
979                 }
980             }
981             if (context.error_handler.EndDependencyErrors())
982                 RAPIDJSON_INVALID_KEYWORD_RETURN(GetDependenciesString());
983         }
984
985         return true;
986     }
987
988     bool StartArray(Context& context) const {
989         if (!(type_ & (1 << kArraySchemaType))) {
990             DisallowedType(context, GetArrayString());
991             RAPIDJSON_INVALID_KEYWORD_RETURN(GetTypeString());
992         }
993
994         context.arrayElementIndex = 0;
995         context.inArray = true;
996
997         return CreateParallelValidator(context);
998     }
999
1000     bool EndArray(Context& context, SizeType elementCount) const {
1001         context.inArray = false;
1002         
1003         if (elementCount < minItems_) {
1004             context.error_handler.TooFewItems(elementCount, minItems_);
1005             RAPIDJSON_INVALID_KEYWORD_RETURN(GetMinItemsString());
1006         }
1007         
1008         if (elementCount > maxItems_) {
1009             context.error_handler.TooManyItems(elementCount, maxItems_);
1010             RAPIDJSON_INVALID_KEYWORD_RETURN(GetMaxItemsString());
1011         }
1012
1013         return true;
1014     }
1015
1016     // Generate functions for string literal according to Ch
1017 #define RAPIDJSON_STRING_(name, ...) \
1018     static const ValueType& Get##name##String() {\
1019         static const Ch s[] = { __VA_ARGS__, '\0' };\
1020         static const ValueType v(s, static_cast<SizeType>(sizeof(s) / sizeof(Ch) - 1));\
1021         return v;\
1022     }
1023
1024     RAPIDJSON_STRING_(Null, 'n', 'u', 'l', 'l')
1025     RAPIDJSON_STRING_(Boolean, 'b', 'o', 'o', 'l', 'e', 'a', 'n')
1026     RAPIDJSON_STRING_(Object, 'o', 'b', 'j', 'e', 'c', 't')
1027     RAPIDJSON_STRING_(Array, 'a', 'r', 'r', 'a', 'y')
1028     RAPIDJSON_STRING_(String, 's', 't', 'r', 'i', 'n', 'g')
1029     RAPIDJSON_STRING_(Number, 'n', 'u', 'm', 'b', 'e', 'r')
1030     RAPIDJSON_STRING_(Integer, 'i', 'n', 't', 'e', 'g', 'e', 'r')
1031     RAPIDJSON_STRING_(Type, 't', 'y', 'p', 'e')
1032     RAPIDJSON_STRING_(Enum, 'e', 'n', 'u', 'm')
1033     RAPIDJSON_STRING_(AllOf, 'a', 'l', 'l', 'O', 'f')
1034     RAPIDJSON_STRING_(AnyOf, 'a', 'n', 'y', 'O', 'f')
1035     RAPIDJSON_STRING_(OneOf, 'o', 'n', 'e', 'O', 'f')
1036     RAPIDJSON_STRING_(Not, 'n', 'o', 't')
1037     RAPIDJSON_STRING_(Properties, 'p', 'r', 'o', 'p', 'e', 'r', 't', 'i', 'e', 's')
1038     RAPIDJSON_STRING_(Required, 'r', 'e', 'q', 'u', 'i', 'r', 'e', 'd')
1039     RAPIDJSON_STRING_(Dependencies, 'd', 'e', 'p', 'e', 'n', 'd', 'e', 'n', 'c', 'i', 'e', 's')
1040     RAPIDJSON_STRING_(PatternProperties, 'p', 'a', 't', 't', 'e', 'r', 'n', 'P', 'r', 'o', 'p', 'e', 'r', 't', 'i', 'e', 's')
1041     RAPIDJSON_STRING_(AdditionalProperties, 'a', 'd', 'd', 'i', 't', 'i', 'o', 'n', 'a', 'l', 'P', 'r', 'o', 'p', 'e', 'r', 't', 'i', 'e', 's')
1042     RAPIDJSON_STRING_(MinProperties, 'm', 'i', 'n', 'P', 'r', 'o', 'p', 'e', 'r', 't', 'i', 'e', 's')
1043     RAPIDJSON_STRING_(MaxProperties, 'm', 'a', 'x', 'P', 'r', 'o', 'p', 'e', 'r', 't', 'i', 'e', 's')
1044     RAPIDJSON_STRING_(Items, 'i', 't', 'e', 'm', 's')
1045     RAPIDJSON_STRING_(MinItems, 'm', 'i', 'n', 'I', 't', 'e', 'm', 's')
1046     RAPIDJSON_STRING_(MaxItems, 'm', 'a', 'x', 'I', 't', 'e', 'm', 's')
1047     RAPIDJSON_STRING_(AdditionalItems, 'a', 'd', 'd', 'i', 't', 'i', 'o', 'n', 'a', 'l', 'I', 't', 'e', 'm', 's')
1048     RAPIDJSON_STRING_(UniqueItems, 'u', 'n', 'i', 'q', 'u', 'e', 'I', 't', 'e', 'm', 's')
1049     RAPIDJSON_STRING_(MinLength, 'm', 'i', 'n', 'L', 'e', 'n', 'g', 't', 'h')
1050     RAPIDJSON_STRING_(MaxLength, 'm', 'a', 'x', 'L', 'e', 'n', 'g', 't', 'h')
1051     RAPIDJSON_STRING_(Pattern, 'p', 'a', 't', 't', 'e', 'r', 'n')
1052     RAPIDJSON_STRING_(Minimum, 'm', 'i', 'n', 'i', 'm', 'u', 'm')
1053     RAPIDJSON_STRING_(Maximum, 'm', 'a', 'x', 'i', 'm', 'u', 'm')
1054     RAPIDJSON_STRING_(ExclusiveMinimum, 'e', 'x', 'c', 'l', 'u', 's', 'i', 'v', 'e', 'M', 'i', 'n', 'i', 'm', 'u', 'm')
1055     RAPIDJSON_STRING_(ExclusiveMaximum, 'e', 'x', 'c', 'l', 'u', 's', 'i', 'v', 'e', 'M', 'a', 'x', 'i', 'm', 'u', 'm')
1056     RAPIDJSON_STRING_(MultipleOf, 'm', 'u', 'l', 't', 'i', 'p', 'l', 'e', 'O', 'f')
1057     RAPIDJSON_STRING_(DefaultValue, 'd', 'e', 'f', 'a', 'u', 'l', 't')
1058
1059 #undef RAPIDJSON_STRING_
1060
1061 private:
1062     enum SchemaValueType {
1063         kNullSchemaType,
1064         kBooleanSchemaType,
1065         kObjectSchemaType,
1066         kArraySchemaType,
1067         kStringSchemaType,
1068         kNumberSchemaType,
1069         kIntegerSchemaType,
1070         kTotalSchemaType
1071     };
1072
1073 #if RAPIDJSON_SCHEMA_USE_INTERNALREGEX
1074         typedef internal::GenericRegex<EncodingType, AllocatorType> RegexType;
1075 #elif RAPIDJSON_SCHEMA_USE_STDREGEX
1076         typedef std::basic_regex<Ch> RegexType;
1077 #else
1078         typedef char RegexType;
1079 #endif
1080
1081     struct SchemaArray {
1082         SchemaArray() : schemas(), count() {}
1083         ~SchemaArray() { AllocatorType::Free(schemas); }
1084         const SchemaType** schemas;
1085         SizeType begin; // begin index of context.validators
1086         SizeType count;
1087     };
1088
1089     template <typename V1, typename V2>
1090     void AddUniqueElement(V1& a, const V2& v) {
1091         for (typename V1::ConstValueIterator itr = a.Begin(); itr != a.End(); ++itr)
1092             if (*itr == v)
1093                 return;
1094         V1 c(v, *allocator_);
1095         a.PushBack(c, *allocator_);
1096     }
1097
1098     static const ValueType* GetMember(const ValueType& value, const ValueType& name) {
1099         typename ValueType::ConstMemberIterator itr = value.FindMember(name);
1100         return itr != value.MemberEnd() ? &(itr->value) : 0;
1101     }
1102
1103     static void AssignIfExist(bool& out, const ValueType& value, const ValueType& name) {
1104         if (const ValueType* v = GetMember(value, name))
1105             if (v->IsBool())
1106                 out = v->GetBool();
1107     }
1108
1109     static void AssignIfExist(SizeType& out, const ValueType& value, const ValueType& name) {
1110         if (const ValueType* v = GetMember(value, name))
1111             if (v->IsUint64() && v->GetUint64() <= SizeType(~0))
1112                 out = static_cast<SizeType>(v->GetUint64());
1113     }
1114
1115     void AssignIfExist(SchemaArray& out, SchemaDocumentType& schemaDocument, const PointerType& p, const ValueType& value, const ValueType& name, const ValueType& document) {
1116         if (const ValueType* v = GetMember(value, name)) {
1117             if (v->IsArray() && v->Size() > 0) {
1118                 PointerType q = p.Append(name, allocator_);
1119                 out.count = v->Size();
1120                 out.schemas = static_cast<const Schema**>(allocator_->Malloc(out.count * sizeof(const Schema*)));
1121                 memset(out.schemas, 0, sizeof(Schema*)* out.count);
1122                 for (SizeType i = 0; i < out.count; i++)
1123                     schemaDocument.CreateSchema(&out.schemas[i], q.Append(i, allocator_), (*v)[i], document);
1124                 out.begin = validatorCount_;
1125                 validatorCount_ += out.count;
1126             }
1127         }
1128     }
1129
1130 #if RAPIDJSON_SCHEMA_USE_INTERNALREGEX
1131     template <typename ValueType>
1132     RegexType* CreatePattern(const ValueType& value) {
1133         if (value.IsString()) {
1134             RegexType* r = new (allocator_->Malloc(sizeof(RegexType))) RegexType(value.GetString(), allocator_);
1135             if (!r->IsValid()) {
1136                 r->~RegexType();
1137                 AllocatorType::Free(r);
1138                 r = 0;
1139             }
1140             return r;
1141         }
1142         return 0;
1143     }
1144
1145     static bool IsPatternMatch(const RegexType* pattern, const Ch *str, SizeType) {
1146         GenericRegexSearch<RegexType> rs(*pattern);
1147         return rs.Search(str);
1148     }
1149 #elif RAPIDJSON_SCHEMA_USE_STDREGEX
1150     template <typename ValueType>
1151     RegexType* CreatePattern(const ValueType& value) {
1152         if (value.IsString()) {
1153             RegexType *r = static_cast<RegexType*>(allocator_->Malloc(sizeof(RegexType)));
1154             try {
1155                 return new (r) RegexType(value.GetString(), std::size_t(value.GetStringLength()), std::regex_constants::ECMAScript);
1156             }
1157             catch (const std::regex_error&) {
1158                 AllocatorType::Free(r);
1159             }
1160         }
1161         return 0;
1162     }
1163
1164     static bool IsPatternMatch(const RegexType* pattern, const Ch *str, SizeType length) {
1165         std::match_results<const Ch*> r;
1166         return std::regex_search(str, str + length, r, *pattern);
1167     }
1168 #else
1169     template <typename ValueType>
1170     RegexType* CreatePattern(const ValueType&) { return 0; }
1171
1172     static bool IsPatternMatch(const RegexType*, const Ch *, SizeType) { return true; }
1173 #endif // RAPIDJSON_SCHEMA_USE_STDREGEX
1174
1175     void AddType(const ValueType& type) {
1176         if      (type == GetNullString()   ) type_ |= 1 << kNullSchemaType;
1177         else if (type == GetBooleanString()) type_ |= 1 << kBooleanSchemaType;
1178         else if (type == GetObjectString() ) type_ |= 1 << kObjectSchemaType;
1179         else if (type == GetArrayString()  ) type_ |= 1 << kArraySchemaType;
1180         else if (type == GetStringString() ) type_ |= 1 << kStringSchemaType;
1181         else if (type == GetIntegerString()) type_ |= 1 << kIntegerSchemaType;
1182         else if (type == GetNumberString() ) type_ |= (1 << kNumberSchemaType) | (1 << kIntegerSchemaType);
1183     }
1184
1185     bool CreateParallelValidator(Context& context) const {
1186         if (enum_ || context.arrayUniqueness)
1187             context.hasher = context.factory.CreateHasher();
1188
1189         if (validatorCount_) {
1190             RAPIDJSON_ASSERT(context.validators == 0);
1191             context.validators = static_cast<ISchemaValidator**>(context.factory.MallocState(sizeof(ISchemaValidator*) * validatorCount_));
1192             context.validatorCount = validatorCount_;
1193
1194             if (allOf_.schemas)
1195                 CreateSchemaValidators(context, allOf_);
1196
1197             if (anyOf_.schemas)
1198                 CreateSchemaValidators(context, anyOf_);
1199             
1200             if (oneOf_.schemas)
1201                 CreateSchemaValidators(context, oneOf_);
1202             
1203             if (not_)
1204                 context.validators[notValidatorIndex_] = context.factory.CreateSchemaValidator(*not_);
1205             
1206             if (hasSchemaDependencies_) {
1207                 for (SizeType i = 0; i < propertyCount_; i++)
1208                     if (properties_[i].dependenciesSchema)
1209                         context.validators[properties_[i].dependenciesValidatorIndex] = context.factory.CreateSchemaValidator(*properties_[i].dependenciesSchema);
1210             }
1211         }
1212
1213         return true;
1214     }
1215
1216     void CreateSchemaValidators(Context& context, const SchemaArray& schemas) const {
1217         for (SizeType i = 0; i < schemas.count; i++)
1218             context.validators[schemas.begin + i] = context.factory.CreateSchemaValidator(*schemas.schemas[i]);
1219     }
1220
1221     // O(n)
1222     bool FindPropertyIndex(const ValueType& name, SizeType* outIndex) const {
1223         SizeType len = name.GetStringLength();
1224         const Ch* str = name.GetString();
1225         for (SizeType index = 0; index < propertyCount_; index++)
1226             if (properties_[index].name.GetStringLength() == len && 
1227                 (std::memcmp(properties_[index].name.GetString(), str, sizeof(Ch) * len) == 0))
1228             {
1229                 *outIndex = index;
1230                 return true;
1231             }
1232         return false;
1233     }
1234
1235     bool CheckInt(Context& context, int64_t i) const {
1236         if (!(type_ & ((1 << kIntegerSchemaType) | (1 << kNumberSchemaType)))) {
1237             DisallowedType(context, GetIntegerString());
1238             RAPIDJSON_INVALID_KEYWORD_RETURN(GetTypeString());
1239         }
1240
1241         if (!minimum_.IsNull()) {
1242             if (minimum_.IsInt64()) {
1243                 if (exclusiveMinimum_ ? i <= minimum_.GetInt64() : i < minimum_.GetInt64()) {
1244                     context.error_handler.BelowMinimum(i, minimum_, exclusiveMinimum_);
1245                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetMinimumString());
1246                 }
1247             }
1248             else if (minimum_.IsUint64()) {
1249                 context.error_handler.BelowMinimum(i, minimum_, exclusiveMinimum_);
1250                 RAPIDJSON_INVALID_KEYWORD_RETURN(GetMinimumString()); // i <= max(int64_t) < minimum.GetUint64()
1251             }
1252             else if (!CheckDoubleMinimum(context, static_cast<double>(i)))
1253                 return false;
1254         }
1255
1256         if (!maximum_.IsNull()) {
1257             if (maximum_.IsInt64()) {
1258                 if (exclusiveMaximum_ ? i >= maximum_.GetInt64() : i > maximum_.GetInt64()) {
1259                     context.error_handler.AboveMaximum(i, maximum_, exclusiveMaximum_);
1260                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetMaximumString());
1261                 }
1262             }
1263             else if (maximum_.IsUint64()) { }
1264                 /* do nothing */ // i <= max(int64_t) < maximum_.GetUint64()
1265             else if (!CheckDoubleMaximum(context, static_cast<double>(i)))
1266                 return false;
1267         }
1268
1269         if (!multipleOf_.IsNull()) {
1270             if (multipleOf_.IsUint64()) {
1271                 if (static_cast<uint64_t>(i >= 0 ? i : -i) % multipleOf_.GetUint64() != 0) {
1272                     context.error_handler.NotMultipleOf(i, multipleOf_);
1273                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetMultipleOfString());
1274                 }
1275             }
1276             else if (!CheckDoubleMultipleOf(context, static_cast<double>(i)))
1277                 return false;
1278         }
1279
1280         return true;
1281     }
1282
1283     bool CheckUint(Context& context, uint64_t i) const {
1284         if (!(type_ & ((1 << kIntegerSchemaType) | (1 << kNumberSchemaType)))) {
1285             DisallowedType(context, GetIntegerString());
1286             RAPIDJSON_INVALID_KEYWORD_RETURN(GetTypeString());
1287         }
1288
1289         if (!minimum_.IsNull()) {
1290             if (minimum_.IsUint64()) {
1291                 if (exclusiveMinimum_ ? i <= minimum_.GetUint64() : i < minimum_.GetUint64()) {
1292                     context.error_handler.BelowMinimum(i, minimum_, exclusiveMinimum_);
1293                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetMinimumString());
1294                 }
1295             }
1296             else if (minimum_.IsInt64())
1297                 /* do nothing */; // i >= 0 > minimum.Getint64()
1298             else if (!CheckDoubleMinimum(context, static_cast<double>(i)))
1299                 return false;
1300         }
1301
1302         if (!maximum_.IsNull()) {
1303             if (maximum_.IsUint64()) {
1304                 if (exclusiveMaximum_ ? i >= maximum_.GetUint64() : i > maximum_.GetUint64()) {
1305                     context.error_handler.AboveMaximum(i, maximum_, exclusiveMaximum_);
1306                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetMaximumString());
1307                 }
1308             }
1309             else if (maximum_.IsInt64()) {
1310                 context.error_handler.AboveMaximum(i, maximum_, exclusiveMaximum_);
1311                 RAPIDJSON_INVALID_KEYWORD_RETURN(GetMaximumString()); // i >= 0 > maximum_
1312             }
1313             else if (!CheckDoubleMaximum(context, static_cast<double>(i)))
1314                 return false;
1315         }
1316
1317         if (!multipleOf_.IsNull()) {
1318             if (multipleOf_.IsUint64()) {
1319                 if (i % multipleOf_.GetUint64() != 0) {
1320                     context.error_handler.NotMultipleOf(i, multipleOf_);
1321                     RAPIDJSON_INVALID_KEYWORD_RETURN(GetMultipleOfString());
1322                 }
1323             }
1324             else if (!CheckDoubleMultipleOf(context, static_cast<double>(i)))
1325                 return false;
1326         }
1327
1328         return true;
1329     }
1330
1331     bool CheckDoubleMinimum(Context& context, double d) const {
1332         if (exclusiveMinimum_ ? d <= minimum_.GetDouble() : d < minimum_.GetDouble()) {
1333             context.error_handler.BelowMinimum(d, minimum_, exclusiveMinimum_);
1334             RAPIDJSON_INVALID_KEYWORD_RETURN(GetMinimumString());
1335         }
1336         return true;
1337     }
1338
1339     bool CheckDoubleMaximum(Context& context, double d) const {
1340         if (exclusiveMaximum_ ? d >= maximum_.GetDouble() : d > maximum_.GetDouble()) {
1341             context.error_handler.AboveMaximum(d, maximum_, exclusiveMaximum_);
1342             RAPIDJSON_INVALID_KEYWORD_RETURN(GetMaximumString());
1343         }
1344         return true;
1345     }
1346
1347     bool CheckDoubleMultipleOf(Context& context, double d) const {
1348         double a = std::abs(d), b = std::abs(multipleOf_.GetDouble());
1349         double q = std::floor(a / b);
1350         double r = a - q * b;
1351         if (r > 0.0) {
1352             context.error_handler.NotMultipleOf(d, multipleOf_);
1353             RAPIDJSON_INVALID_KEYWORD_RETURN(GetMultipleOfString());
1354         }
1355         return true;
1356     }
1357
1358     void DisallowedType(Context& context, const ValueType& actualType) const {
1359         ErrorHandler& eh = context.error_handler;
1360         eh.StartDisallowedType();
1361
1362         if (type_ & (1 << kNullSchemaType)) eh.AddExpectedType(GetNullString());
1363         if (type_ & (1 << kBooleanSchemaType)) eh.AddExpectedType(GetBooleanString());
1364         if (type_ & (1 << kObjectSchemaType)) eh.AddExpectedType(GetObjectString());
1365         if (type_ & (1 << kArraySchemaType)) eh.AddExpectedType(GetArrayString());
1366         if (type_ & (1 << kStringSchemaType)) eh.AddExpectedType(GetStringString());
1367
1368         if (type_ & (1 << kNumberSchemaType)) eh.AddExpectedType(GetNumberString());
1369         else if (type_ & (1 << kIntegerSchemaType)) eh.AddExpectedType(GetIntegerString());
1370
1371         eh.EndDisallowedType(actualType);
1372     }
1373
1374     struct Property {
1375         Property() : schema(), dependenciesSchema(), dependenciesValidatorIndex(), dependencies(), required(false) {}
1376         ~Property() { AllocatorType::Free(dependencies); }
1377         SValue name;
1378         const SchemaType* schema;
1379         const SchemaType* dependenciesSchema;
1380         SizeType dependenciesValidatorIndex;
1381         bool* dependencies;
1382         bool required;
1383     };
1384
1385     struct PatternProperty {
1386         PatternProperty() : schema(), pattern() {}
1387         ~PatternProperty() { 
1388             if (pattern) {
1389                 pattern->~RegexType();
1390                 AllocatorType::Free(pattern);
1391             }
1392         }
1393         const SchemaType* schema;
1394         RegexType* pattern;
1395     };
1396
1397     AllocatorType* allocator_;
1398     SValue uri_;
1399     PointerType pointer_;
1400     const SchemaType* typeless_;
1401     uint64_t* enum_;
1402     SizeType enumCount_;
1403     SchemaArray allOf_;
1404     SchemaArray anyOf_;
1405     SchemaArray oneOf_;
1406     const SchemaType* not_;
1407     unsigned type_; // bitmask of kSchemaType
1408     SizeType validatorCount_;
1409     SizeType notValidatorIndex_;
1410
1411     Property* properties_;
1412     const SchemaType* additionalPropertiesSchema_;
1413     PatternProperty* patternProperties_;
1414     SizeType patternPropertyCount_;
1415     SizeType propertyCount_;
1416     SizeType minProperties_;
1417     SizeType maxProperties_;
1418     bool additionalProperties_;
1419     bool hasDependencies_;
1420     bool hasRequired_;
1421     bool hasSchemaDependencies_;
1422
1423     const SchemaType* additionalItemsSchema_;
1424     const SchemaType* itemsList_;
1425     const SchemaType** itemsTuple_;
1426     SizeType itemsTupleCount_;
1427     SizeType minItems_;
1428     SizeType maxItems_;
1429     bool additionalItems_;
1430     bool uniqueItems_;
1431
1432     RegexType* pattern_;
1433     SizeType minLength_;
1434     SizeType maxLength_;
1435
1436     SValue minimum_;
1437     SValue maximum_;
1438     SValue multipleOf_;
1439     bool exclusiveMinimum_;
1440     bool exclusiveMaximum_;
1441     
1442     SizeType defaultValueLength_;
1443 };
1444
1445 template<typename Stack, typename Ch>
1446 struct TokenHelper {
1447     RAPIDJSON_FORCEINLINE static void AppendIndexToken(Stack& documentStack, SizeType index) {
1448         *documentStack.template Push<Ch>() = '/';
1449         char buffer[21];
1450         size_t length = static_cast<size_t>((sizeof(SizeType) == 4 ? u32toa(index, buffer) : u64toa(index, buffer)) - buffer);
1451         for (size_t i = 0; i < length; i++)
1452             *documentStack.template Push<Ch>() = static_cast<Ch>(buffer[i]);
1453     }
1454 };
1455
1456 // Partial specialized version for char to prevent buffer copying.
1457 template <typename Stack>
1458 struct TokenHelper<Stack, char> {
1459     RAPIDJSON_FORCEINLINE static void AppendIndexToken(Stack& documentStack, SizeType index) {
1460         if (sizeof(SizeType) == 4) {
1461             char *buffer = documentStack.template Push<char>(1 + 10); // '/' + uint
1462             *buffer++ = '/';
1463             const char* end = internal::u32toa(index, buffer);
1464              documentStack.template Pop<char>(static_cast<size_t>(10 - (end - buffer)));
1465         }
1466         else {
1467             char *buffer = documentStack.template Push<char>(1 + 20); // '/' + uint64
1468             *buffer++ = '/';
1469             const char* end = internal::u64toa(index, buffer);
1470             documentStack.template Pop<char>(static_cast<size_t>(20 - (end - buffer)));
1471         }
1472     }
1473 };
1474
1475 } // namespace internal
1476
1477 ///////////////////////////////////////////////////////////////////////////////
1478 // IGenericRemoteSchemaDocumentProvider
1479
1480 template <typename SchemaDocumentType>
1481 class IGenericRemoteSchemaDocumentProvider {
1482 public:
1483     typedef typename SchemaDocumentType::Ch Ch;
1484
1485     virtual ~IGenericRemoteSchemaDocumentProvider() {}
1486     virtual const SchemaDocumentType* GetRemoteDocument(const Ch* uri, SizeType length) = 0;
1487 };
1488
1489 ///////////////////////////////////////////////////////////////////////////////
1490 // GenericSchemaDocument
1491
1492 //! JSON schema document.
1493 /*!
1494     A JSON schema document is a compiled version of a JSON schema.
1495     It is basically a tree of internal::Schema.
1496
1497     \note This is an immutable class (i.e. its instance cannot be modified after construction).
1498     \tparam ValueT Type of JSON value (e.g. \c Value ), which also determine the encoding.
1499     \tparam Allocator Allocator type for allocating memory of this document.
1500 */
1501 template <typename ValueT, typename Allocator = CrtAllocator>
1502 class GenericSchemaDocument {
1503 public:
1504     typedef ValueT ValueType;
1505     typedef IGenericRemoteSchemaDocumentProvider<GenericSchemaDocument> IRemoteSchemaDocumentProviderType;
1506     typedef Allocator AllocatorType;
1507     typedef typename ValueType::EncodingType EncodingType;
1508     typedef typename EncodingType::Ch Ch;
1509     typedef internal::Schema<GenericSchemaDocument> SchemaType;
1510     typedef GenericPointer<ValueType, Allocator> PointerType;
1511     typedef GenericValue<EncodingType, Allocator> URIType;
1512     friend class internal::Schema<GenericSchemaDocument>;
1513     template <typename, typename, typename>
1514     friend class GenericSchemaValidator;
1515
1516     //! Constructor.
1517     /*!
1518         Compile a JSON document into schema document.
1519
1520         \param document A JSON document as source.
1521         \param uri The base URI of this schema document for purposes of violation reporting.
1522         \param uriLength Length of \c name, in code points.
1523         \param remoteProvider An optional remote schema document provider for resolving remote reference. Can be null.
1524         \param allocator An optional allocator instance for allocating memory. Can be null.
1525     */
1526     explicit GenericSchemaDocument(const ValueType& document, const Ch* uri = 0, SizeType uriLength = 0,
1527         IRemoteSchemaDocumentProviderType* remoteProvider = 0, Allocator* allocator = 0) :
1528         remoteProvider_(remoteProvider),
1529         allocator_(allocator),
1530         ownAllocator_(),
1531         root_(),
1532         typeless_(),
1533         schemaMap_(allocator, kInitialSchemaMapSize),
1534         schemaRef_(allocator, kInitialSchemaRefSize)
1535     {
1536         if (!allocator_)
1537             ownAllocator_ = allocator_ = RAPIDJSON_NEW(Allocator)();
1538
1539         Ch noUri[1] = {0};
1540         uri_.SetString(uri ? uri : noUri, uriLength, *allocator_);
1541
1542         typeless_ = static_cast<SchemaType*>(allocator_->Malloc(sizeof(SchemaType)));
1543         new (typeless_) SchemaType(this, PointerType(), ValueType(kObjectType).Move(), ValueType(kObjectType).Move(), allocator_);
1544
1545         // Generate root schema, it will call CreateSchema() to create sub-schemas,
1546         // And call AddRefSchema() if there are $ref.
1547         CreateSchemaRecursive(&root_, PointerType(), document, document);
1548
1549         // Resolve $ref
1550         while (!schemaRef_.Empty()) {
1551             SchemaRefEntry* refEntry = schemaRef_.template Pop<SchemaRefEntry>(1);
1552             if (const SchemaType* s = GetSchema(refEntry->target)) {
1553                 if (refEntry->schema)
1554                     *refEntry->schema = s;
1555
1556                 // Create entry in map if not exist
1557                 if (!GetSchema(refEntry->source)) {
1558                     new (schemaMap_.template Push<SchemaEntry>()) SchemaEntry(refEntry->source, const_cast<SchemaType*>(s), false, allocator_);
1559                 }
1560             }
1561             else if (refEntry->schema)
1562                 *refEntry->schema = typeless_;
1563
1564             refEntry->~SchemaRefEntry();
1565         }
1566
1567         RAPIDJSON_ASSERT(root_ != 0);
1568
1569         schemaRef_.ShrinkToFit(); // Deallocate all memory for ref
1570     }
1571
1572 #if RAPIDJSON_HAS_CXX11_RVALUE_REFS
1573     //! Move constructor in C++11
1574     GenericSchemaDocument(GenericSchemaDocument&& rhs) RAPIDJSON_NOEXCEPT :
1575         remoteProvider_(rhs.remoteProvider_),
1576         allocator_(rhs.allocator_),
1577         ownAllocator_(rhs.ownAllocator_),
1578         root_(rhs.root_),
1579         typeless_(rhs.typeless_),
1580         schemaMap_(std::move(rhs.schemaMap_)),
1581         schemaRef_(std::move(rhs.schemaRef_)),
1582         uri_(std::move(rhs.uri_))
1583     {
1584         rhs.remoteProvider_ = 0;
1585         rhs.allocator_ = 0;
1586         rhs.ownAllocator_ = 0;
1587         rhs.typeless_ = 0;
1588     }
1589 #endif
1590
1591     //! Destructor
1592     ~GenericSchemaDocument() {
1593         while (!schemaMap_.Empty())
1594             schemaMap_.template Pop<SchemaEntry>(1)->~SchemaEntry();
1595
1596         if (typeless_) {
1597             typeless_->~SchemaType();
1598             Allocator::Free(typeless_);
1599         }
1600
1601         RAPIDJSON_DELETE(ownAllocator_);
1602     }
1603
1604     const URIType& GetURI() const { return uri_; }
1605
1606     //! Get the root schema.
1607     const SchemaType& GetRoot() const { return *root_; }
1608
1609 private:
1610     //! Prohibit copying
1611     GenericSchemaDocument(const GenericSchemaDocument&);
1612     //! Prohibit assignment
1613     GenericSchemaDocument& operator=(const GenericSchemaDocument&);
1614
1615     struct SchemaRefEntry {
1616         SchemaRefEntry(const PointerType& s, const PointerType& t, const SchemaType** outSchema, Allocator *allocator) : source(s, allocator), target(t, allocator), schema(outSchema) {}
1617         PointerType source;
1618         PointerType target;
1619         const SchemaType** schema;
1620     };
1621
1622     struct SchemaEntry {
1623         SchemaEntry(const PointerType& p, SchemaType* s, bool o, Allocator* allocator) : pointer(p, allocator), schema(s), owned(o) {}
1624         ~SchemaEntry() {
1625             if (owned) {
1626                 schema->~SchemaType();
1627                 Allocator::Free(schema);
1628             }
1629         }
1630         PointerType pointer;
1631         SchemaType* schema;
1632         bool owned;
1633     };
1634
1635     void CreateSchemaRecursive(const SchemaType** schema, const PointerType& pointer, const ValueType& v, const ValueType& document) {
1636         if (schema)
1637             *schema = typeless_;
1638
1639         if (v.GetType() == kObjectType) {
1640             const SchemaType* s = GetSchema(pointer);
1641             if (!s)
1642                 CreateSchema(schema, pointer, v, document);
1643
1644             for (typename ValueType::ConstMemberIterator itr = v.MemberBegin(); itr != v.MemberEnd(); ++itr)
1645                 CreateSchemaRecursive(0, pointer.Append(itr->name, allocator_), itr->value, document);
1646         }
1647         else if (v.GetType() == kArrayType)
1648             for (SizeType i = 0; i < v.Size(); i++)
1649                 CreateSchemaRecursive(0, pointer.Append(i, allocator_), v[i], document);
1650     }
1651
1652     void CreateSchema(const SchemaType** schema, const PointerType& pointer, const ValueType& v, const ValueType& document) {
1653         RAPIDJSON_ASSERT(pointer.IsValid());
1654         if (v.IsObject()) {
1655             if (!HandleRefSchema(pointer, schema, v, document)) {
1656                 SchemaType* s = new (allocator_->Malloc(sizeof(SchemaType))) SchemaType(this, pointer, v, document, allocator_);
1657                 new (schemaMap_.template Push<SchemaEntry>()) SchemaEntry(pointer, s, true, allocator_);
1658                 if (schema)
1659                     *schema = s;
1660             }
1661         }
1662     }
1663
1664     bool HandleRefSchema(const PointerType& source, const SchemaType** schema, const ValueType& v, const ValueType& document) {
1665         static const Ch kRefString[] = { '$', 'r', 'e', 'f', '\0' };
1666         static const ValueType kRefValue(kRefString, 4);
1667
1668         typename ValueType::ConstMemberIterator itr = v.FindMember(kRefValue);
1669         if (itr == v.MemberEnd())
1670             return false;
1671
1672         if (itr->value.IsString()) {
1673             SizeType len = itr->value.GetStringLength();
1674             if (len > 0) {
1675                 const Ch* s = itr->value.GetString();
1676                 SizeType i = 0;
1677                 while (i < len && s[i] != '#') // Find the first #
1678                     i++;
1679
1680                 if (i > 0) { // Remote reference, resolve immediately
1681                     if (remoteProvider_) {
1682                         if (const GenericSchemaDocument* remoteDocument = remoteProvider_->GetRemoteDocument(s, i)) {
1683                             PointerType pointer(&s[i], len - i, allocator_);
1684                             if (pointer.IsValid()) {
1685                                 if (const SchemaType* sc = remoteDocument->GetSchema(pointer)) {
1686                                     if (schema)
1687                                         *schema = sc;
1688                                     new (schemaMap_.template Push<SchemaEntry>()) SchemaEntry(source, const_cast<SchemaType*>(sc), false, allocator_);
1689                                     return true;
1690                                 }
1691                             }
1692                         }
1693                     }
1694                 }
1695                 else if (s[i] == '#') { // Local reference, defer resolution
1696                     PointerType pointer(&s[i], len - i, allocator_);
1697                     if (pointer.IsValid()) {
1698                         if (const ValueType* nv = pointer.Get(document))
1699                             if (HandleRefSchema(source, schema, *nv, document))
1700                                 return true;
1701
1702                         new (schemaRef_.template Push<SchemaRefEntry>()) SchemaRefEntry(source, pointer, schema, allocator_);
1703                         return true;
1704                     }
1705                 }
1706             }
1707         }
1708         return false;
1709     }
1710
1711     const SchemaType* GetSchema(const PointerType& pointer) const {
1712         for (const SchemaEntry* target = schemaMap_.template Bottom<SchemaEntry>(); target != schemaMap_.template End<SchemaEntry>(); ++target)
1713             if (pointer == target->pointer)
1714                 return target->schema;
1715         return 0;
1716     }
1717
1718     PointerType GetPointer(const SchemaType* schema) const {
1719         for (const SchemaEntry* target = schemaMap_.template Bottom<SchemaEntry>(); target != schemaMap_.template End<SchemaEntry>(); ++target)
1720             if (schema == target->schema)
1721                 return target->pointer;
1722         return PointerType();
1723     }
1724
1725     const SchemaType* GetTypeless() const { return typeless_; }
1726
1727     static const size_t kInitialSchemaMapSize = 64;
1728     static const size_t kInitialSchemaRefSize = 64;
1729
1730     IRemoteSchemaDocumentProviderType* remoteProvider_;
1731     Allocator *allocator_;
1732     Allocator *ownAllocator_;
1733     const SchemaType* root_;                //!< Root schema.
1734     SchemaType* typeless_;
1735     internal::Stack<Allocator> schemaMap_;  // Stores created Pointer -> Schemas
1736     internal::Stack<Allocator> schemaRef_;  // Stores Pointer from $ref and schema which holds the $ref
1737     URIType uri_;
1738 };
1739
1740 //! GenericSchemaDocument using Value type.
1741 typedef GenericSchemaDocument<Value> SchemaDocument;
1742 //! IGenericRemoteSchemaDocumentProvider using SchemaDocument.
1743 typedef IGenericRemoteSchemaDocumentProvider<SchemaDocument> IRemoteSchemaDocumentProvider;
1744
1745 ///////////////////////////////////////////////////////////////////////////////
1746 // GenericSchemaValidator
1747
1748 //! JSON Schema Validator.
1749 /*!
1750     A SAX style JSON schema validator.
1751     It uses a \c GenericSchemaDocument to validate SAX events.
1752     It delegates the incoming SAX events to an output handler.
1753     The default output handler does nothing.
1754     It can be reused multiple times by calling \c Reset().
1755
1756     \tparam SchemaDocumentType Type of schema document.
1757     \tparam OutputHandler Type of output handler. Default handler does nothing.
1758     \tparam StateAllocator Allocator for storing the internal validation states.
1759 */
1760 template <
1761     typename SchemaDocumentType,
1762     typename OutputHandler = BaseReaderHandler<typename SchemaDocumentType::SchemaType::EncodingType>,
1763     typename StateAllocator = CrtAllocator>
1764 class GenericSchemaValidator :
1765     public internal::ISchemaStateFactory<typename SchemaDocumentType::SchemaType>, 
1766     public internal::ISchemaValidator,
1767     public internal::IValidationErrorHandler<typename SchemaDocumentType::SchemaType>
1768 {
1769 public:
1770     typedef typename SchemaDocumentType::SchemaType SchemaType;
1771     typedef typename SchemaDocumentType::PointerType PointerType;
1772     typedef typename SchemaType::EncodingType EncodingType;
1773     typedef typename SchemaType::SValue SValue;
1774     typedef typename EncodingType::Ch Ch;
1775     typedef GenericStringRef<Ch> StringRefType;
1776     typedef GenericValue<EncodingType, StateAllocator> ValueType;
1777
1778     //! Constructor without output handler.
1779     /*!
1780         \param schemaDocument The schema document to conform to.
1781         \param allocator Optional allocator for storing internal validation states.
1782         \param schemaStackCapacity Optional initial capacity of schema path stack.
1783         \param documentStackCapacity Optional initial capacity of document path stack.
1784     */
1785     GenericSchemaValidator(
1786         const SchemaDocumentType& schemaDocument,
1787         StateAllocator* allocator = 0, 
1788         size_t schemaStackCapacity = kDefaultSchemaStackCapacity,
1789         size_t documentStackCapacity = kDefaultDocumentStackCapacity)
1790         :
1791         schemaDocument_(&schemaDocument),
1792         root_(schemaDocument.GetRoot()),
1793         stateAllocator_(allocator),
1794         ownStateAllocator_(0),
1795         schemaStack_(allocator, schemaStackCapacity),
1796         documentStack_(allocator, documentStackCapacity),
1797         outputHandler_(0),
1798         error_(kObjectType),
1799         currentError_(),
1800         missingDependents_(),
1801         valid_(true)
1802 #if RAPIDJSON_SCHEMA_VERBOSE
1803         , depth_(0)
1804 #endif
1805     {
1806     }
1807
1808     //! Constructor with output handler.
1809     /*!
1810         \param schemaDocument The schema document to conform to.
1811         \param allocator Optional allocator for storing internal validation states.
1812         \param schemaStackCapacity Optional initial capacity of schema path stack.
1813         \param documentStackCapacity Optional initial capacity of document path stack.
1814     */
1815     GenericSchemaValidator(
1816         const SchemaDocumentType& schemaDocument,
1817         OutputHandler& outputHandler,
1818         StateAllocator* allocator = 0, 
1819         size_t schemaStackCapacity = kDefaultSchemaStackCapacity,
1820         size_t documentStackCapacity = kDefaultDocumentStackCapacity)
1821         :
1822         schemaDocument_(&schemaDocument),
1823         root_(schemaDocument.GetRoot()),
1824         stateAllocator_(allocator),
1825         ownStateAllocator_(0),
1826         schemaStack_(allocator, schemaStackCapacity),
1827         documentStack_(allocator, documentStackCapacity),
1828         outputHandler_(&outputHandler),
1829         error_(kObjectType),
1830         currentError_(),
1831         missingDependents_(),
1832         valid_(true)
1833 #if RAPIDJSON_SCHEMA_VERBOSE
1834         , depth_(0)
1835 #endif
1836     {
1837     }
1838
1839     //! Destructor.
1840     ~GenericSchemaValidator() {
1841         Reset();
1842         RAPIDJSON_DELETE(ownStateAllocator_);
1843     }
1844
1845     //! Reset the internal states.
1846     void Reset() {
1847         while (!schemaStack_.Empty())
1848             PopSchema();
1849         documentStack_.Clear();
1850         error_.SetObject();
1851         currentError_.SetNull();
1852         missingDependents_.SetNull();
1853         valid_ = true;
1854     }
1855
1856     //! Checks whether the current state is valid.
1857     // Implementation of ISchemaValidator
1858     virtual bool IsValid() const { return valid_; }
1859
1860     //! Gets the error object.
1861     ValueType& GetError() { return error_; }
1862     const ValueType& GetError() const { return error_; }
1863
1864     //! Gets the JSON pointer pointed to the invalid schema.
1865     PointerType GetInvalidSchemaPointer() const {
1866         return schemaStack_.Empty() ? PointerType() : CurrentSchema().GetPointer();
1867     }
1868
1869     //! Gets the keyword of invalid schema.
1870     const Ch* GetInvalidSchemaKeyword() const {
1871         return schemaStack_.Empty() ? 0 : CurrentContext().invalidKeyword;
1872     }
1873
1874     //! Gets the JSON pointer pointed to the invalid value.
1875     PointerType GetInvalidDocumentPointer() const {
1876         if (documentStack_.Empty()) {
1877             return PointerType();
1878         }
1879         else {
1880             return PointerType(documentStack_.template Bottom<Ch>(), documentStack_.GetSize() / sizeof(Ch));
1881         }
1882     }
1883
1884     void NotMultipleOf(int64_t actual, const SValue& expected) {
1885         AddNumberError(SchemaType::GetMultipleOfString(), ValueType(actual).Move(), expected);
1886     }
1887     void NotMultipleOf(uint64_t actual, const SValue& expected) {
1888         AddNumberError(SchemaType::GetMultipleOfString(), ValueType(actual).Move(), expected);
1889     }
1890     void NotMultipleOf(double actual, const SValue& expected) {
1891         AddNumberError(SchemaType::GetMultipleOfString(), ValueType(actual).Move(), expected);
1892     }
1893     void AboveMaximum(int64_t actual, const SValue& expected, bool exclusive) {
1894         AddNumberError(SchemaType::GetMaximumString(), ValueType(actual).Move(), expected,
1895             exclusive ? &SchemaType::GetExclusiveMaximumString : 0);
1896     }
1897     void AboveMaximum(uint64_t actual, const SValue& expected, bool exclusive) {
1898         AddNumberError(SchemaType::GetMaximumString(), ValueType(actual).Move(), expected,
1899             exclusive ? &SchemaType::GetExclusiveMaximumString : 0);
1900     }
1901     void AboveMaximum(double actual, const SValue& expected, bool exclusive) {
1902         AddNumberError(SchemaType::GetMaximumString(), ValueType(actual).Move(), expected,
1903             exclusive ? &SchemaType::GetExclusiveMaximumString : 0);
1904     }
1905     void BelowMinimum(int64_t actual, const SValue& expected, bool exclusive) {
1906         AddNumberError(SchemaType::GetMinimumString(), ValueType(actual).Move(), expected,
1907             exclusive ? &SchemaType::GetExclusiveMinimumString : 0);
1908     }
1909     void BelowMinimum(uint64_t actual, const SValue& expected, bool exclusive) {
1910         AddNumberError(SchemaType::GetMinimumString(), ValueType(actual).Move(), expected,
1911             exclusive ? &SchemaType::GetExclusiveMinimumString : 0);
1912     }
1913     void BelowMinimum(double actual, const SValue& expected, bool exclusive) {
1914         AddNumberError(SchemaType::GetMinimumString(), ValueType(actual).Move(), expected,
1915             exclusive ? &SchemaType::GetExclusiveMinimumString : 0);
1916     }
1917
1918     void TooLong(const Ch* str, SizeType length, SizeType expected) {
1919         AddNumberError(SchemaType::GetMaxLengthString(),
1920             ValueType(str, length, GetStateAllocator()).Move(), SValue(expected).Move());
1921     }
1922     void TooShort(const Ch* str, SizeType length, SizeType expected) {
1923         AddNumberError(SchemaType::GetMinLengthString(),
1924             ValueType(str, length, GetStateAllocator()).Move(), SValue(expected).Move());
1925     }
1926     void DoesNotMatch(const Ch* str, SizeType length) {
1927         currentError_.SetObject();
1928         currentError_.AddMember(GetActualString(), ValueType(str, length, GetStateAllocator()).Move(), GetStateAllocator());
1929         AddCurrentError(SchemaType::GetPatternString());
1930     }
1931
1932     void DisallowedItem(SizeType index) {
1933         currentError_.SetObject();
1934         currentError_.AddMember(GetDisallowedString(), ValueType(index).Move(), GetStateAllocator());
1935         AddCurrentError(SchemaType::GetAdditionalItemsString(), true);
1936     }
1937     void TooFewItems(SizeType actualCount, SizeType expectedCount) {
1938         AddNumberError(SchemaType::GetMinItemsString(),
1939             ValueType(actualCount).Move(), SValue(expectedCount).Move());
1940     }
1941     void TooManyItems(SizeType actualCount, SizeType expectedCount) {
1942         AddNumberError(SchemaType::GetMaxItemsString(),
1943             ValueType(actualCount).Move(), SValue(expectedCount).Move());
1944     }
1945     void DuplicateItems(SizeType index1, SizeType index2) {
1946         ValueType duplicates(kArrayType);
1947         duplicates.PushBack(index1, GetStateAllocator());
1948         duplicates.PushBack(index2, GetStateAllocator());
1949         currentError_.SetObject();
1950         currentError_.AddMember(GetDuplicatesString(), duplicates, GetStateAllocator());
1951         AddCurrentError(SchemaType::GetUniqueItemsString(), true);
1952     }
1953
1954     void TooManyProperties(SizeType actualCount, SizeType expectedCount) {
1955         AddNumberError(SchemaType::GetMaxPropertiesString(),
1956             ValueType(actualCount).Move(), SValue(expectedCount).Move());
1957     }
1958     void TooFewProperties(SizeType actualCount, SizeType expectedCount) {
1959         AddNumberError(SchemaType::GetMinPropertiesString(),
1960             ValueType(actualCount).Move(), SValue(expectedCount).Move());
1961     }
1962     void StartMissingProperties() {
1963         currentError_.SetArray();
1964     }
1965     void AddMissingProperty(const SValue& name) {
1966         currentError_.PushBack(ValueType(name, GetStateAllocator()).Move(), GetStateAllocator());
1967     }
1968     bool EndMissingProperties() {
1969         if (currentError_.Empty())
1970             return false;
1971         ValueType error(kObjectType);
1972         error.AddMember(GetMissingString(), currentError_, GetStateAllocator());
1973         currentError_ = error;
1974         AddCurrentError(SchemaType::GetRequiredString());
1975         return true;
1976     }
1977     void PropertyViolations(ISchemaValidator** subvalidators, SizeType count) {
1978         for (SizeType i = 0; i < count; ++i)
1979             MergeError(static_cast<GenericSchemaValidator*>(subvalidators[i])->GetError());
1980     }
1981     void DisallowedProperty(const Ch* name, SizeType length) {
1982         currentError_.SetObject();
1983         currentError_.AddMember(GetDisallowedString(), ValueType(name, length, GetStateAllocator()).Move(), GetStateAllocator());
1984         AddCurrentError(SchemaType::GetAdditionalPropertiesString(), true);
1985     }
1986
1987     void StartDependencyErrors() {
1988         currentError_.SetObject();
1989     }
1990     void StartMissingDependentProperties() {
1991         missingDependents_.SetArray();
1992     }
1993     void AddMissingDependentProperty(const SValue& targetName) {
1994         missingDependents_.PushBack(ValueType(targetName, GetStateAllocator()).Move(), GetStateAllocator());
1995     }
1996     void EndMissingDependentProperties(const SValue& sourceName) {
1997         if (!missingDependents_.Empty())
1998             currentError_.AddMember(ValueType(sourceName, GetStateAllocator()).Move(),
1999                 missingDependents_, GetStateAllocator());
2000     }
2001     void AddDependencySchemaError(const SValue& sourceName, ISchemaValidator* subvalidator) {
2002         currentError_.AddMember(ValueType(sourceName, GetStateAllocator()).Move(),
2003             static_cast<GenericSchemaValidator*>(subvalidator)->GetError(), GetStateAllocator());
2004     }
2005     bool EndDependencyErrors() {
2006         if (currentError_.ObjectEmpty())
2007             return false;
2008         ValueType error(kObjectType);
2009         error.AddMember(GetErrorsString(), currentError_, GetStateAllocator());
2010         currentError_ = error;
2011         AddCurrentError(SchemaType::GetDependenciesString());
2012         return true;
2013     }
2014
2015     void DisallowedValue() {
2016         currentError_.SetObject();
2017         AddCurrentError(SchemaType::GetEnumString());
2018     }
2019     void StartDisallowedType() {
2020         currentError_.SetArray();
2021     }
2022     void AddExpectedType(const typename SchemaType::ValueType& expectedType) {
2023         currentError_.PushBack(ValueType(expectedType, GetStateAllocator()).Move(), GetStateAllocator());
2024     }
2025     void EndDisallowedType(const typename SchemaType::ValueType& actualType) {
2026         ValueType error(kObjectType);
2027         error.AddMember(GetExpectedString(), currentError_, GetStateAllocator());
2028         error.AddMember(GetActualString(), ValueType(actualType, GetStateAllocator()).Move(), GetStateAllocator());
2029         currentError_ = error;
2030         AddCurrentError(SchemaType::GetTypeString());
2031     }
2032     void NotAllOf(ISchemaValidator** subvalidators, SizeType count) {
2033         for (SizeType i = 0; i < count; ++i) {
2034             MergeError(static_cast<GenericSchemaValidator*>(subvalidators[i])->GetError());
2035         }
2036     }
2037     void NoneOf(ISchemaValidator** subvalidators, SizeType count) {
2038         AddErrorArray(SchemaType::GetAnyOfString(), subvalidators, count);
2039     }
2040     void NotOneOf(ISchemaValidator** subvalidators, SizeType count) {
2041         AddErrorArray(SchemaType::GetOneOfString(), subvalidators, count);
2042     }
2043     void Disallowed() {
2044         currentError_.SetObject();
2045         AddCurrentError(SchemaType::GetNotString());
2046     }
2047
2048 #define RAPIDJSON_STRING_(name, ...) \
2049     static const StringRefType& Get##name##String() {\
2050         static const Ch s[] = { __VA_ARGS__, '\0' };\
2051         static const StringRefType v(s, static_cast<SizeType>(sizeof(s) / sizeof(Ch) - 1)); \
2052         return v;\
2053     }
2054
2055     RAPIDJSON_STRING_(InstanceRef, 'i', 'n', 's', 't', 'a', 'n', 'c', 'e', 'R', 'e', 'f')
2056     RAPIDJSON_STRING_(SchemaRef, 's', 'c', 'h', 'e', 'm', 'a', 'R', 'e', 'f')
2057     RAPIDJSON_STRING_(Expected, 'e', 'x', 'p', 'e', 'c', 't', 'e', 'd')
2058     RAPIDJSON_STRING_(Actual, 'a', 'c', 't', 'u', 'a', 'l')
2059     RAPIDJSON_STRING_(Disallowed, 'd', 'i', 's', 'a', 'l', 'l', 'o', 'w', 'e', 'd')
2060     RAPIDJSON_STRING_(Missing, 'm', 'i', 's', 's', 'i', 'n', 'g')
2061     RAPIDJSON_STRING_(Errors, 'e', 'r', 'r', 'o', 'r', 's')
2062     RAPIDJSON_STRING_(Duplicates, 'd', 'u', 'p', 'l', 'i', 'c', 'a', 't', 'e', 's')
2063
2064 #undef RAPIDJSON_STRING_
2065
2066 #if RAPIDJSON_SCHEMA_VERBOSE
2067 #define RAPIDJSON_SCHEMA_HANDLE_BEGIN_VERBOSE_() \
2068 RAPIDJSON_MULTILINEMACRO_BEGIN\
2069     *documentStack_.template Push<Ch>() = '\0';\
2070     documentStack_.template Pop<Ch>(1);\
2071     internal::PrintInvalidDocument(documentStack_.template Bottom<Ch>());\
2072 RAPIDJSON_MULTILINEMACRO_END
2073 #else
2074 #define RAPIDJSON_SCHEMA_HANDLE_BEGIN_VERBOSE_()
2075 #endif
2076
2077 #define RAPIDJSON_SCHEMA_HANDLE_BEGIN_(method, arg1)\
2078     if (!valid_) return false; \
2079     if (!BeginValue() || !CurrentSchema().method arg1) {\
2080         RAPIDJSON_SCHEMA_HANDLE_BEGIN_VERBOSE_();\
2081         return valid_ = false;\
2082     }
2083
2084 #define RAPIDJSON_SCHEMA_HANDLE_PARALLEL_(method, arg2)\
2085     for (Context* context = schemaStack_.template Bottom<Context>(); context != schemaStack_.template End<Context>(); context++) {\
2086         if (context->hasher)\
2087             static_cast<HasherType*>(context->hasher)->method arg2;\
2088         if (context->validators)\
2089             for (SizeType i_ = 0; i_ < context->validatorCount; i_++)\
2090                 static_cast<GenericSchemaValidator*>(context->validators[i_])->method arg2;\
2091         if (context->patternPropertiesValidators)\
2092             for (SizeType i_ = 0; i_ < context->patternPropertiesValidatorCount; i_++)\
2093                 static_cast<GenericSchemaValidator*>(context->patternPropertiesValidators[i_])->method arg2;\
2094     }
2095
2096 #define RAPIDJSON_SCHEMA_HANDLE_END_(method, arg2)\
2097     return valid_ = EndValue() && (!outputHandler_ || outputHandler_->method arg2)
2098
2099 #define RAPIDJSON_SCHEMA_HANDLE_VALUE_(method, arg1, arg2) \
2100     RAPIDJSON_SCHEMA_HANDLE_BEGIN_   (method, arg1);\
2101     RAPIDJSON_SCHEMA_HANDLE_PARALLEL_(method, arg2);\
2102     RAPIDJSON_SCHEMA_HANDLE_END_     (method, arg2)
2103
2104     bool Null()             { RAPIDJSON_SCHEMA_HANDLE_VALUE_(Null,   (CurrentContext()), ( )); }
2105     bool Bool(bool b)       { RAPIDJSON_SCHEMA_HANDLE_VALUE_(Bool,   (CurrentContext(), b), (b)); }
2106     bool Int(int i)         { RAPIDJSON_SCHEMA_HANDLE_VALUE_(Int,    (CurrentContext(), i), (i)); }
2107     bool Uint(unsigned u)   { RAPIDJSON_SCHEMA_HANDLE_VALUE_(Uint,   (CurrentContext(), u), (u)); }
2108     bool Int64(int64_t i)   { RAPIDJSON_SCHEMA_HANDLE_VALUE_(Int64,  (CurrentContext(), i), (i)); }
2109     bool Uint64(uint64_t u) { RAPIDJSON_SCHEMA_HANDLE_VALUE_(Uint64, (CurrentContext(), u), (u)); }
2110     bool Double(double d)   { RAPIDJSON_SCHEMA_HANDLE_VALUE_(Double, (CurrentContext(), d), (d)); }
2111     bool RawNumber(const Ch* str, SizeType length, bool copy)
2112                                     { RAPIDJSON_SCHEMA_HANDLE_VALUE_(String, (CurrentContext(), str, length, copy), (str, length, copy)); }
2113     bool String(const Ch* str, SizeType length, bool copy)
2114                                     { RAPIDJSON_SCHEMA_HANDLE_VALUE_(String, (CurrentContext(), str, length, copy), (str, length, copy)); }
2115
2116     bool StartObject() {
2117         RAPIDJSON_SCHEMA_HANDLE_BEGIN_(StartObject, (CurrentContext()));
2118         RAPIDJSON_SCHEMA_HANDLE_PARALLEL_(StartObject, ());
2119         return valid_ = !outputHandler_ || outputHandler_->StartObject();
2120     }
2121     
2122     bool Key(const Ch* str, SizeType len, bool copy) {
2123         if (!valid_) return false;
2124         AppendToken(str, len);
2125         if (!CurrentSchema().Key(CurrentContext(), str, len, copy)) return valid_ = false;
2126         RAPIDJSON_SCHEMA_HANDLE_PARALLEL_(Key, (str, len, copy));
2127         return valid_ = !outputHandler_ || outputHandler_->Key(str, len, copy);
2128     }
2129     
2130     bool EndObject(SizeType memberCount) { 
2131         if (!valid_) return false;
2132         RAPIDJSON_SCHEMA_HANDLE_PARALLEL_(EndObject, (memberCount));
2133         if (!CurrentSchema().EndObject(CurrentContext(), memberCount)) return valid_ = false;
2134         RAPIDJSON_SCHEMA_HANDLE_END_(EndObject, (memberCount));
2135     }
2136
2137     bool StartArray() {
2138         RAPIDJSON_SCHEMA_HANDLE_BEGIN_(StartArray, (CurrentContext()));
2139         RAPIDJSON_SCHEMA_HANDLE_PARALLEL_(StartArray, ());
2140         return valid_ = !outputHandler_ || outputHandler_->StartArray();
2141     }
2142     
2143     bool EndArray(SizeType elementCount) {
2144         if (!valid_) return false;
2145         RAPIDJSON_SCHEMA_HANDLE_PARALLEL_(EndArray, (elementCount));
2146         if (!CurrentSchema().EndArray(CurrentContext(), elementCount)) return valid_ = false;
2147         RAPIDJSON_SCHEMA_HANDLE_END_(EndArray, (elementCount));
2148     }
2149
2150 #undef RAPIDJSON_SCHEMA_HANDLE_BEGIN_VERBOSE_
2151 #undef RAPIDJSON_SCHEMA_HANDLE_BEGIN_
2152 #undef RAPIDJSON_SCHEMA_HANDLE_PARALLEL_
2153 #undef RAPIDJSON_SCHEMA_HANDLE_VALUE_
2154
2155     // Implementation of ISchemaStateFactory<SchemaType>
2156     virtual ISchemaValidator* CreateSchemaValidator(const SchemaType& root) {
2157         return new (GetStateAllocator().Malloc(sizeof(GenericSchemaValidator))) GenericSchemaValidator(*schemaDocument_, root, documentStack_.template Bottom<char>(), documentStack_.GetSize(),
2158 #if RAPIDJSON_SCHEMA_VERBOSE
2159         depth_ + 1,
2160 #endif
2161         &GetStateAllocator());
2162     }
2163
2164     virtual void DestroySchemaValidator(ISchemaValidator* validator) {
2165         GenericSchemaValidator* v = static_cast<GenericSchemaValidator*>(validator);
2166         v->~GenericSchemaValidator();
2167         StateAllocator::Free(v);
2168     }
2169
2170     virtual void* CreateHasher() {
2171         return new (GetStateAllocator().Malloc(sizeof(HasherType))) HasherType(&GetStateAllocator());
2172     }
2173
2174     virtual uint64_t GetHashCode(void* hasher) {
2175         return static_cast<HasherType*>(hasher)->GetHashCode();
2176     }
2177
2178     virtual void DestroryHasher(void* hasher) {
2179         HasherType* h = static_cast<HasherType*>(hasher);
2180         h->~HasherType();
2181         StateAllocator::Free(h);
2182     }
2183
2184     virtual void* MallocState(size_t size) {
2185         return GetStateAllocator().Malloc(size);
2186     }
2187
2188     virtual void FreeState(void* p) {
2189         StateAllocator::Free(p);
2190     }
2191
2192 private:
2193     typedef typename SchemaType::Context Context;
2194     typedef GenericValue<UTF8<>, StateAllocator> HashCodeArray;
2195     typedef internal::Hasher<EncodingType, StateAllocator> HasherType;
2196
2197     GenericSchemaValidator( 
2198         const SchemaDocumentType& schemaDocument,
2199         const SchemaType& root,
2200         const char* basePath, size_t basePathSize,
2201 #if RAPIDJSON_SCHEMA_VERBOSE
2202         unsigned depth,
2203 #endif
2204         StateAllocator* allocator = 0,
2205         size_t schemaStackCapacity = kDefaultSchemaStackCapacity,
2206         size_t documentStackCapacity = kDefaultDocumentStackCapacity)
2207         :
2208         schemaDocument_(&schemaDocument),
2209         root_(root),
2210         stateAllocator_(allocator),
2211         ownStateAllocator_(0),
2212         schemaStack_(allocator, schemaStackCapacity),
2213         documentStack_(allocator, documentStackCapacity),
2214         outputHandler_(0),
2215         error_(kObjectType),
2216         currentError_(),
2217         missingDependents_(),
2218         valid_(true)
2219 #if RAPIDJSON_SCHEMA_VERBOSE
2220         , depth_(depth)
2221 #endif
2222     {
2223         if (basePath && basePathSize)
2224             memcpy(documentStack_.template Push<char>(basePathSize), basePath, basePathSize);
2225     }
2226
2227     StateAllocator& GetStateAllocator() {
2228         if (!stateAllocator_)
2229             stateAllocator_ = ownStateAllocator_ = RAPIDJSON_NEW(StateAllocator)();
2230         return *stateAllocator_;
2231     }
2232
2233     bool BeginValue() {
2234         if (schemaStack_.Empty())
2235             PushSchema(root_);
2236         else {
2237             if (CurrentContext().inArray)
2238                 internal::TokenHelper<internal::Stack<StateAllocator>, Ch>::AppendIndexToken(documentStack_, CurrentContext().arrayElementIndex);
2239
2240             if (!CurrentSchema().BeginValue(CurrentContext()))
2241                 return false;
2242
2243             SizeType count = CurrentContext().patternPropertiesSchemaCount;
2244             const SchemaType** sa = CurrentContext().patternPropertiesSchemas;
2245             typename Context::PatternValidatorType patternValidatorType = CurrentContext().valuePatternValidatorType;
2246             bool valueUniqueness = CurrentContext().valueUniqueness;
2247             RAPIDJSON_ASSERT(CurrentContext().valueSchema);
2248             PushSchema(*CurrentContext().valueSchema);
2249
2250             if (count > 0) {
2251                 CurrentContext().objectPatternValidatorType = patternValidatorType;
2252                 ISchemaValidator**& va = CurrentContext().patternPropertiesValidators;
2253                 SizeType& validatorCount = CurrentContext().patternPropertiesValidatorCount;
2254                 va = static_cast<ISchemaValidator**>(MallocState(sizeof(ISchemaValidator*) * count));
2255                 for (SizeType i = 0; i < count; i++)
2256                     va[validatorCount++] = CreateSchemaValidator(*sa[i]);
2257             }
2258
2259             CurrentContext().arrayUniqueness = valueUniqueness;
2260         }
2261         return true;
2262     }
2263
2264     bool EndValue() {
2265         if (!CurrentSchema().EndValue(CurrentContext()))
2266             return false;
2267
2268 #if RAPIDJSON_SCHEMA_VERBOSE
2269         GenericStringBuffer<EncodingType> sb;
2270         schemaDocument_->GetPointer(&CurrentSchema()).Stringify(sb);
2271
2272         *documentStack_.template Push<Ch>() = '\0';
2273         documentStack_.template Pop<Ch>(1);
2274         internal::PrintValidatorPointers(depth_, sb.GetString(), documentStack_.template Bottom<Ch>());
2275 #endif
2276
2277         uint64_t h = CurrentContext().arrayUniqueness ? static_cast<HasherType*>(CurrentContext().hasher)->GetHashCode() : 0;
2278         
2279         PopSchema();
2280
2281         if (!schemaStack_.Empty()) {
2282             Context& context = CurrentContext();
2283             if (context.valueUniqueness) {
2284                 HashCodeArray* a = static_cast<HashCodeArray*>(context.arrayElementHashCodes);
2285                 if (!a)
2286                     CurrentContext().arrayElementHashCodes = a = new (GetStateAllocator().Malloc(sizeof(HashCodeArray))) HashCodeArray(kArrayType);
2287                 for (typename HashCodeArray::ConstValueIterator itr = a->Begin(); itr != a->End(); ++itr)
2288                     if (itr->GetUint64() == h) {
2289                         DuplicateItems(static_cast<SizeType>(itr - a->Begin()), a->Size());
2290                         RAPIDJSON_INVALID_KEYWORD_RETURN(SchemaType::GetUniqueItemsString());
2291                     }
2292                 a->PushBack(h, GetStateAllocator());
2293             }
2294         }
2295
2296         // Remove the last token of document pointer
2297         while (!documentStack_.Empty() && *documentStack_.template Pop<Ch>(1) != '/')
2298             ;
2299
2300         return true;
2301     }
2302
2303     void AppendToken(const Ch* str, SizeType len) {
2304         documentStack_.template Reserve<Ch>(1 + len * 2); // worst case all characters are escaped as two characters
2305         *documentStack_.template PushUnsafe<Ch>() = '/';
2306         for (SizeType i = 0; i < len; i++) {
2307             if (str[i] == '~') {
2308                 *documentStack_.template PushUnsafe<Ch>() = '~';
2309                 *documentStack_.template PushUnsafe<Ch>() = '0';
2310             }
2311             else if (str[i] == '/') {
2312                 *documentStack_.template PushUnsafe<Ch>() = '~';
2313                 *documentStack_.template PushUnsafe<Ch>() = '1';
2314             }
2315             else
2316                 *documentStack_.template PushUnsafe<Ch>() = str[i];
2317         }
2318     }
2319
2320     RAPIDJSON_FORCEINLINE void PushSchema(const SchemaType& schema) { new (schemaStack_.template Push<Context>()) Context(*this, *this, &schema); }
2321     
2322     RAPIDJSON_FORCEINLINE void PopSchema() {
2323         Context* c = schemaStack_.template Pop<Context>(1);
2324         if (HashCodeArray* a = static_cast<HashCodeArray*>(c->arrayElementHashCodes)) {
2325             a->~HashCodeArray();
2326             StateAllocator::Free(a);
2327         }
2328         c->~Context();
2329     }
2330
2331     void AddErrorLocation(ValueType& result, bool parent) {
2332         GenericStringBuffer<EncodingType> sb;
2333         PointerType instancePointer = GetInvalidDocumentPointer();
2334         ((parent && instancePointer.GetTokenCount() > 0)
2335             ? PointerType(instancePointer.GetTokens(), instancePointer.GetTokenCount() - 1)
2336             : instancePointer).StringifyUriFragment(sb);
2337         ValueType instanceRef(sb.GetString(), static_cast<SizeType>(sb.GetSize() / sizeof(Ch)),
2338             GetStateAllocator());
2339         result.AddMember(GetInstanceRefString(), instanceRef, GetStateAllocator());
2340         sb.Clear();
2341         memcpy(sb.Push(CurrentSchema().GetURI().GetStringLength()),
2342             CurrentSchema().GetURI().GetString(),
2343             CurrentSchema().GetURI().GetStringLength() * sizeof(Ch));
2344         GetInvalidSchemaPointer().StringifyUriFragment(sb);
2345         ValueType schemaRef(sb.GetString(), static_cast<SizeType>(sb.GetSize() / sizeof(Ch)),
2346             GetStateAllocator());
2347         result.AddMember(GetSchemaRefString(), schemaRef, GetStateAllocator());
2348     }
2349
2350     void AddError(ValueType& keyword, ValueType& error) {
2351         typename ValueType::MemberIterator member = error_.FindMember(keyword);
2352         if (member == error_.MemberEnd())
2353             error_.AddMember(keyword, error, GetStateAllocator());
2354         else {
2355             if (member->value.IsObject()) {
2356                 ValueType errors(kArrayType);
2357                 errors.PushBack(member->value, GetStateAllocator());
2358                 member->value = errors;
2359             }
2360             member->value.PushBack(error, GetStateAllocator());
2361         }
2362     }
2363
2364     void AddCurrentError(const typename SchemaType::ValueType& keyword, bool parent = false) {
2365         AddErrorLocation(currentError_, parent);
2366         AddError(ValueType(keyword, GetStateAllocator(), false).Move(), currentError_);
2367     }
2368
2369     void MergeError(ValueType& other) {
2370         for (typename ValueType::MemberIterator it = other.MemberBegin(), end = other.MemberEnd(); it != end; ++it) {
2371             AddError(it->name, it->value);
2372         }
2373     }
2374
2375     void AddNumberError(const typename SchemaType::ValueType& keyword, ValueType& actual, const SValue& expected,
2376         const typename SchemaType::ValueType& (*exclusive)() = 0) {
2377         currentError_.SetObject();
2378         currentError_.AddMember(GetActualString(), actual, GetStateAllocator());
2379         currentError_.AddMember(GetExpectedString(), ValueType(expected, GetStateAllocator()).Move(), GetStateAllocator());
2380         if (exclusive)
2381             currentError_.AddMember(ValueType(exclusive(), GetStateAllocator()).Move(), true, GetStateAllocator());
2382         AddCurrentError(keyword);
2383     }
2384
2385     void AddErrorArray(const typename SchemaType::ValueType& keyword,
2386         ISchemaValidator** subvalidators, SizeType count) {
2387         ValueType errors(kArrayType);
2388         for (SizeType i = 0; i < count; ++i)
2389             errors.PushBack(static_cast<GenericSchemaValidator*>(subvalidators[i])->GetError(), GetStateAllocator());
2390         currentError_.SetObject();
2391         currentError_.AddMember(GetErrorsString(), errors, GetStateAllocator());
2392         AddCurrentError(keyword);
2393     }
2394
2395     const SchemaType& CurrentSchema() const { return *schemaStack_.template Top<Context>()->schema; }
2396     Context& CurrentContext() { return *schemaStack_.template Top<Context>(); }
2397     const Context& CurrentContext() const { return *schemaStack_.template Top<Context>(); }
2398
2399     static const size_t kDefaultSchemaStackCapacity = 1024;
2400     static const size_t kDefaultDocumentStackCapacity = 256;
2401     const SchemaDocumentType* schemaDocument_;
2402     const SchemaType& root_;
2403     StateAllocator* stateAllocator_;
2404     StateAllocator* ownStateAllocator_;
2405     internal::Stack<StateAllocator> schemaStack_;    //!< stack to store the current path of schema (BaseSchemaType *)
2406     internal::Stack<StateAllocator> documentStack_;  //!< stack to store the current path of validating document (Ch)
2407     OutputHandler* outputHandler_;
2408     ValueType error_;
2409     ValueType currentError_;
2410     ValueType missingDependents_;
2411     bool valid_;
2412 #if RAPIDJSON_SCHEMA_VERBOSE
2413     unsigned depth_;
2414 #endif
2415 };
2416
2417 typedef GenericSchemaValidator<SchemaDocument> SchemaValidator;
2418
2419 ///////////////////////////////////////////////////////////////////////////////
2420 // SchemaValidatingReader
2421
2422 //! A helper class for parsing with validation.
2423 /*!
2424     This helper class is a functor, designed as a parameter of \ref GenericDocument::Populate().
2425
2426     \tparam parseFlags Combination of \ref ParseFlag.
2427     \tparam InputStream Type of input stream, implementing Stream concept.
2428     \tparam SourceEncoding Encoding of the input stream.
2429     \tparam SchemaDocumentType Type of schema document.
2430     \tparam StackAllocator Allocator type for stack.
2431 */
2432 template <
2433     unsigned parseFlags,
2434     typename InputStream,
2435     typename SourceEncoding,
2436     typename SchemaDocumentType = SchemaDocument,
2437     typename StackAllocator = CrtAllocator>
2438 class SchemaValidatingReader {
2439 public:
2440     typedef typename SchemaDocumentType::PointerType PointerType;
2441     typedef typename InputStream::Ch Ch;
2442     typedef GenericValue<SourceEncoding, StackAllocator> ValueType;
2443
2444     //! Constructor
2445     /*!
2446         \param is Input stream.
2447         \param sd Schema document.
2448     */
2449     SchemaValidatingReader(InputStream& is, const SchemaDocumentType& sd) : is_(is), sd_(sd), invalidSchemaKeyword_(), error_(kObjectType), isValid_(true) {}
2450
2451     template <typename Handler>
2452     bool operator()(Handler& handler) {
2453         GenericReader<SourceEncoding, typename SchemaDocumentType::EncodingType, StackAllocator> reader;
2454         GenericSchemaValidator<SchemaDocumentType, Handler> validator(sd_, handler);
2455         parseResult_ = reader.template Parse<parseFlags>(is_, validator);
2456
2457         isValid_ = validator.IsValid();
2458         if (isValid_) {
2459             invalidSchemaPointer_ = PointerType();
2460             invalidSchemaKeyword_ = 0;
2461             invalidDocumentPointer_ = PointerType();
2462             error_.SetObject();
2463         }
2464         else {
2465             invalidSchemaPointer_ = validator.GetInvalidSchemaPointer();
2466             invalidSchemaKeyword_ = validator.GetInvalidSchemaKeyword();
2467             invalidDocumentPointer_ = validator.GetInvalidDocumentPointer();
2468             error_.CopyFrom(validator.GetError(), allocator_);
2469         }
2470
2471         return parseResult_;
2472     }
2473
2474     const ParseResult& GetParseResult() const { return parseResult_; }
2475     bool IsValid() const { return isValid_; }
2476     const PointerType& GetInvalidSchemaPointer() const { return invalidSchemaPointer_; }
2477     const Ch* GetInvalidSchemaKeyword() const { return invalidSchemaKeyword_; }
2478     const PointerType& GetInvalidDocumentPointer() const { return invalidDocumentPointer_; }
2479     const ValueType& GetError() const { return error_; }
2480
2481 private:
2482     InputStream& is_;
2483     const SchemaDocumentType& sd_;
2484
2485     ParseResult parseResult_;
2486     PointerType invalidSchemaPointer_;
2487     const Ch* invalidSchemaKeyword_;
2488     PointerType invalidDocumentPointer_;
2489     StackAllocator allocator_;
2490     ValueType error_;
2491     bool isValid_;
2492 };
2493
2494 RAPIDJSON_NAMESPACE_END
2495 RAPIDJSON_DIAG_POP
2496
2497 #endif // RAPIDJSON_SCHEMA_H_