pointer.h Source File

pointer.h Source File#

Composable Kernel: pointer.h Source File
// Tencent is pleased to support the open source community by making RapidJSON available.
//
// Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip.
//
// Licensed under the MIT License (the "License"); you may not use this file except
// in compliance with the License. You may obtain a copy of the License at
//
// http://opensource.org/licenses/MIT
//
// Unless required by applicable law or agreed to in writing, software distributed
// under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
// CONDITIONS OF ANY KIND, either express or implied. See the License for the
// specific language governing permissions and limitations under the License.
 
#ifndef RAPIDJSON_POINTER_H_
#define RAPIDJSON_POINTER_H_
 
#include "document.h"
#include "uri.h"
#include "internal/itoa.h"
#include "error/error.h" // PointerParseErrorCode
 
#ifdef __clang__
RAPIDJSON_DIAG_PUSH
RAPIDJSON_DIAG_OFF(switch - enum)
#elif defined(_MSC_VER)
RAPIDJSON_DIAG_PUSH
RAPIDJSON_DIAG_OFF(4512) // assignment operator could not be generated
#endif
 
#if defined(RAPIDJSON_CPLUSPLUS) && RAPIDJSON_CPLUSPLUS >= 201703L
#define RAPIDJSON_IF_CONSTEXPR if constexpr
#else
#define RAPIDJSON_IF_CONSTEXPR if
#endif
 
RAPIDJSON_NAMESPACE_BEGIN
 
static const SizeType kPointerInvalidIndex =
    ~SizeType(0); 
// GenericPointer
template <typename ValueType, typename Allocator = CrtAllocator>
class GenericPointer
{
    public:
    typedef typename ValueType::EncodingType EncodingType; 
    typedef typename ValueType::Ch Ch;                     
    typedef GenericUri<ValueType, Allocator> UriType;
    struct Token
    {
        const Ch* name;  
        SizeType length; 
        SizeType index;  
    };
    GenericPointer(Allocator* allocator = 0)
        : allocator_(allocator),
          ownAllocator_(),
          nameBuffer_(),
          tokens_(),
          tokenCount_(),
          parseErrorOffset_(),
          parseErrorCode_(kPointerParseErrorNone)
    {
    }
    explicit GenericPointer(const Ch* source, Allocator* allocator = 0)
        : allocator_(allocator),
          ownAllocator_(),
          nameBuffer_(),
          tokens_(),
          tokenCount_(),
          parseErrorOffset_(),
          parseErrorCode_(kPointerParseErrorNone)
    {
        Parse(source, internal::StrLen(source));
    }
 
#if RAPIDJSON_HAS_STDSTRING
    explicit GenericPointer(const std::basic_string<Ch>& source, Allocator* allocator = 0)
        : allocator_(allocator),
          ownAllocator_(),
          nameBuffer_(),
          tokens_(),
          tokenCount_(),
          parseErrorOffset_(),
          parseErrorCode_(kPointerParseErrorNone)
    {
        Parse(source.c_str(), source.size());
    }
#endif
    GenericPointer(const Ch* source, size_t length, Allocator* allocator = 0)
        : allocator_(allocator),
          ownAllocator_(),
          nameBuffer_(),
          tokens_(),
          tokenCount_(),
          parseErrorOffset_(),
          parseErrorCode_(kPointerParseErrorNone)
    {
        Parse(source, length);
    }
    GenericPointer(const Token* tokens, size_t tokenCount)
        : allocator_(),
          ownAllocator_(),
          nameBuffer_(),
          tokens_(const_cast<Token*>(tokens)),
          tokenCount_(tokenCount),
          parseErrorOffset_(),
          parseErrorCode_(kPointerParseErrorNone)
    {
    }
    GenericPointer(const GenericPointer& rhs)
        : allocator_(),
          ownAllocator_(),
          nameBuffer_(),
          tokens_(),
          tokenCount_(),
          parseErrorOffset_(),
          parseErrorCode_(kPointerParseErrorNone)
    {
        *this = rhs;
    }
    GenericPointer(const GenericPointer& rhs, Allocator* allocator)
        : allocator_(allocator),
          ownAllocator_(),
          nameBuffer_(),
          tokens_(),
          tokenCount_(),
          parseErrorOffset_(),
          parseErrorCode_(kPointerParseErrorNone)
    {
        *this = rhs;
    }
    ~GenericPointer()
    {
        if(nameBuffer_) // If user-supplied tokens constructor is used, nameBuffer_ is nullptr and
                        // tokens_ are not deallocated.
            Allocator::Free(tokens_);
        RAPIDJSON_DELETE(ownAllocator_);
    }
    GenericPointer& operator=(const GenericPointer& rhs)
    {
        if(this != &rhs)
        {
            // Do not delete ownAllcator
            if(nameBuffer_)
                Allocator::Free(tokens_);
 
            tokenCount_       = rhs.tokenCount_;
            parseErrorOffset_ = rhs.parseErrorOffset_;
            parseErrorCode_   = rhs.parseErrorCode_;
 
            if(rhs.nameBuffer_)
                CopyFromRaw(rhs); // Normally parsed tokens.
            else
            {
                tokens_     = rhs.tokens_; // User supplied const tokens.
                nameBuffer_ = 0;
            }
        }
        return *this;
    }
    GenericPointer& Swap(GenericPointer& other) RAPIDJSON_NOEXCEPT
    {
        internal::Swap(allocator_, other.allocator_);
        internal::Swap(ownAllocator_, other.ownAllocator_);
        internal::Swap(nameBuffer_, other.nameBuffer_);
        internal::Swap(tokens_, other.tokens_);
        internal::Swap(tokenCount_, other.tokenCount_);
        internal::Swap(parseErrorOffset_, other.parseErrorOffset_);
        internal::Swap(parseErrorCode_, other.parseErrorCode_);
        return *this;
    }
    friend inline void swap(GenericPointer& a, GenericPointer& b) RAPIDJSON_NOEXCEPT { a.Swap(b); }
    GenericPointer Append(const Token& token, Allocator* allocator = 0) const
    {
        GenericPointer r;
        r.allocator_ = allocator;
        Ch* p        = r.CopyFromRaw(*this, 1, token.length + 1);
        std::memcpy(p, token.name, (token.length + 1) * sizeof(Ch));
        r.tokens_[tokenCount_].name   = p;
        r.tokens_[tokenCount_].length = token.length;
        r.tokens_[tokenCount_].index  = token.index;
        return r;
    }
    GenericPointer Append(const Ch* name, SizeType length, Allocator* allocator = 0) const
    {
        Token token = {name, length, kPointerInvalidIndex};
        return Append(token, allocator);
    }
    template <typename T>
    RAPIDJSON_DISABLEIF_RETURN(
        (internal::NotExpr<internal::IsSame<typename internal::RemoveConst<T>::Type, Ch>>),
        (GenericPointer))
    Append(T* name, Allocator* allocator = 0) const
    {
        return Append(name, internal::StrLen(name), allocator);
    }
 
#if RAPIDJSON_HAS_STDSTRING
    GenericPointer Append(const std::basic_string<Ch>& name, Allocator* allocator = 0) const
    {
        return Append(name.c_str(), static_cast<SizeType>(name.size()), allocator);
    }
#endif
    GenericPointer Append(SizeType index, Allocator* allocator = 0) const
    {
        char buffer[21];
        char* end       = sizeof(SizeType) == 4 ? internal::u32toa(index, buffer)
                                                : internal::u64toa(index, buffer);
        SizeType length = static_cast<SizeType>(end - buffer);
        buffer[length]  = '\0';
 
        RAPIDJSON_IF_CONSTEXPR(sizeof(Ch) == 1)
        {
            Token token = {reinterpret_cast<Ch*>(buffer), length, index};
            return Append(token, allocator);
        }
        else
        {
            Ch name[21];
            for(size_t i = 0; i <= length; i++)
                name[i] = static_cast<Ch>(buffer[i]);
            Token token = {name, length, index};
            return Append(token, allocator);
        }
    }
    GenericPointer Append(const ValueType& token, Allocator* allocator = 0) const
    {
        if(token.IsString())
            return Append(token.GetString(), token.GetStringLength(), allocator);
        else
        {
            RAPIDJSON_ASSERT(token.IsUint64());
            RAPIDJSON_ASSERT(token.GetUint64() <= SizeType(~0));
            return Append(static_cast<SizeType>(token.GetUint64()), allocator);
        }
    }
    bool IsValid() const { return parseErrorCode_ == kPointerParseErrorNone; }
    size_t GetParseErrorOffset() const { return parseErrorOffset_; }
    PointerParseErrorCode GetParseErrorCode() const { return parseErrorCode_; }
    Allocator& GetAllocator() { return *allocator_; }
    const Token* GetTokens() const { return tokens_; }
    size_t GetTokenCount() const { return tokenCount_; }
    bool operator==(const GenericPointer& rhs) const
    {
        if(!IsValid() || !rhs.IsValid() || tokenCount_ != rhs.tokenCount_)
            return false;
 
        for(size_t i = 0; i < tokenCount_; i++)
        {
            if(tokens_[i].index != rhs.tokens_[i].index ||
               tokens_[i].length != rhs.tokens_[i].length ||
               (tokens_[i].length != 0 &&
                std::memcmp(tokens_[i].name, rhs.tokens_[i].name, sizeof(Ch) * tokens_[i].length) !=
                    0))
            {
                return false;
            }
        }
 
        return true;
    }
    bool operator!=(const GenericPointer& rhs) const { return !(*this == rhs); }
    bool operator<(const GenericPointer& rhs) const
    {
        if(!IsValid())
            return false;
        if(!rhs.IsValid())
            return true;
 
        if(tokenCount_ != rhs.tokenCount_)
            return tokenCount_ < rhs.tokenCount_;
 
        for(size_t i = 0; i < tokenCount_; i++)
        {
            if(tokens_[i].index != rhs.tokens_[i].index)
                return tokens_[i].index < rhs.tokens_[i].index;
 
            if(tokens_[i].length != rhs.tokens_[i].length)
                return tokens_[i].length < rhs.tokens_[i].length;
 
            if(int cmp = std::memcmp(
                   tokens_[i].name, rhs.tokens_[i].name, sizeof(Ch) * tokens_[i].length))
                return cmp < 0;
        }
 
        return false;
    }
    template <typename OutputStream>
    bool Stringify(OutputStream& os) const
    {
        return Stringify<false, OutputStream>(os);
    }
    template <typename OutputStream>
    bool StringifyUriFragment(OutputStream& os) const
    {
        return Stringify<true, OutputStream>(os);
    }
    ValueType& Create(ValueType& root,
                      typename ValueType::AllocatorType& allocator,
                      bool* alreadyExist = 0) const
    {
        RAPIDJSON_ASSERT(IsValid());
        ValueType* v = &root;
        bool exist   = true;
        for(const Token* t = tokens_; t != tokens_ + tokenCount_; ++t)
        {
            if(v->IsArray() && t->name[0] == '-' && t->length == 1)
            {
                v->PushBack(ValueType().Move(), allocator);
                v     = &((*v)[v->Size() - 1]);
                exist = false;
            }
            else
            {
                if(t->index == kPointerInvalidIndex)
                { // must be object name
                    if(!v->IsObject())
                        v->SetObject(); // Change to Object
                }
                else
                { // object name or array index
                    if(!v->IsArray() && !v->IsObject())
                        v->SetArray(); // Change to Array
                }
 
                if(v->IsArray())
                {
                    if(t->index >= v->Size())
                    {
                        v->Reserve(t->index + 1, allocator);
                        while(t->index >= v->Size())
                            v->PushBack(ValueType().Move(), allocator);
                        exist = false;
                    }
                    v = &((*v)[t->index]);
                }
                else
                {
                    typename ValueType::MemberIterator m = v->FindMember(
                        GenericValue<EncodingType>(GenericStringRef<Ch>(t->name, t->length)));
                    if(m == v->MemberEnd())
                    {
                        v->AddMember(ValueType(t->name, t->length, allocator).Move(),
                                     ValueType().Move(),
                                     allocator);
                        m     = v->MemberEnd();
                        v     = &(--m)->value; // Assumes AddMember() appends at the end
                        exist = false;
                    }
                    else
                        v = &m->value;
                }
            }
        }
 
        if(alreadyExist)
            *alreadyExist = exist;
 
        return *v;
    }
    template <typename stackAllocator>
    ValueType& Create(
        GenericDocument<EncodingType, typename ValueType::AllocatorType, stackAllocator>& document,
        bool* alreadyExist = 0) const
    {
        return Create(document, document.GetAllocator(), alreadyExist);
    }
    //  For use with JSON pointers into JSON schema documents.
    UriType GetUri(ValueType& root,
                   const UriType& rootUri,
                   size_t* unresolvedTokenIndex = 0,
                   Allocator* allocator         = 0) const
    {
        static const Ch kIdString[] = {'i', 'd', '\0'};
        static const ValueType kIdValue(kIdString, 2);
        UriType base = UriType(rootUri, allocator);
        RAPIDJSON_ASSERT(IsValid());
        ValueType* v = &root;
        for(const Token* t = tokens_; t != tokens_ + tokenCount_; ++t)
        {
            switch(v->GetType())
            {
            case kObjectType: {
                // See if we have an id, and if so resolve with the current base
                typename ValueType::MemberIterator m = v->FindMember(kIdValue);
                if(m != v->MemberEnd() && (m->value).IsString())
                {
                    UriType here = UriType(m->value, allocator).Resolve(base, allocator);
                    base         = here;
                }
                m = v->FindMember(
                    GenericValue<EncodingType>(GenericStringRef<Ch>(t->name, t->length)));
                if(m == v->MemberEnd())
                    break;
                v = &m->value;
            }
                continue;
            case kArrayType:
                if(t->index == kPointerInvalidIndex || t->index >= v->Size())
                    break;
                v = &((*v)[t->index]);
                continue;
            default: break;
            }
 
            // Error: unresolved token
            if(unresolvedTokenIndex)
                *unresolvedTokenIndex = static_cast<size_t>(t - tokens_);
            return UriType(allocator);
        }
        return base;
    }
 
    UriType GetUri(const ValueType& root,
                   const UriType& rootUri,
                   size_t* unresolvedTokenIndex = 0,
                   Allocator* allocator         = 0) const
    {
        return GetUri(const_cast<ValueType&>(root), rootUri, unresolvedTokenIndex, allocator);
    }
    ValueType* Get(ValueType& root, size_t* unresolvedTokenIndex = 0) const
    {
        RAPIDJSON_ASSERT(IsValid());
        ValueType* v = &root;
        for(const Token* t = tokens_; t != tokens_ + tokenCount_; ++t)
        {
            switch(v->GetType())
            {
            case kObjectType: {
                typename ValueType::MemberIterator m = v->FindMember(
                    GenericValue<EncodingType>(GenericStringRef<Ch>(t->name, t->length)));
                if(m == v->MemberEnd())
                    break;
                v = &m->value;
            }
                continue;
            case kArrayType:
                if(t->index == kPointerInvalidIndex || t->index >= v->Size())
                    break;
                v = &((*v)[t->index]);
                continue;
            default: break;
            }
 
            // Error: unresolved token
            if(unresolvedTokenIndex)
                *unresolvedTokenIndex = static_cast<size_t>(t - tokens_);
            return 0;
        }
        return v;
    }
    const ValueType* Get(const ValueType& root, size_t* unresolvedTokenIndex = 0) const
    {
        return Get(const_cast<ValueType&>(root), unresolvedTokenIndex);
    }
    ValueType& GetWithDefault(ValueType& root,
                              const ValueType& defaultValue,
                              typename ValueType::AllocatorType& allocator) const
    {
        bool alreadyExist;
        ValueType& v = Create(root, allocator, &alreadyExist);
        return alreadyExist ? v : v.CopyFrom(defaultValue, allocator);
    }
    ValueType& GetWithDefault(ValueType& root,
                              const Ch* defaultValue,
                              typename ValueType::AllocatorType& allocator) const
    {
        bool alreadyExist;
        ValueType& v = Create(root, allocator, &alreadyExist);
        return alreadyExist ? v : v.SetString(defaultValue, allocator);
    }
 
#if RAPIDJSON_HAS_STDSTRING
    ValueType& GetWithDefault(ValueType& root,
                              const std::basic_string<Ch>& defaultValue,
                              typename ValueType::AllocatorType& allocator) const
    {
        bool alreadyExist;
        ValueType& v = Create(root, allocator, &alreadyExist);
        return alreadyExist ? v : v.SetString(defaultValue, allocator);
    }
#endif
    template <typename T>
    RAPIDJSON_DISABLEIF_RETURN(
        (internal::OrExpr<internal::IsPointer<T>, internal::IsGenericValue<T>>), (ValueType&))
    GetWithDefault(ValueType& root,
                   T defaultValue,
                   typename ValueType::AllocatorType& allocator) const
    {
        return GetWithDefault(root, ValueType(defaultValue).Move(), allocator);
    }
    template <typename stackAllocator>
    ValueType& GetWithDefault(
        GenericDocument<EncodingType, typename ValueType::AllocatorType, stackAllocator>& document,
        const ValueType& defaultValue) const
    {
        return GetWithDefault(document, defaultValue, document.GetAllocator());
    }
    template <typename stackAllocator>
    ValueType& GetWithDefault(
        GenericDocument<EncodingType, typename ValueType::AllocatorType, stackAllocator>& document,
        const Ch* defaultValue) const
    {
        return GetWithDefault(document, defaultValue, document.GetAllocator());
    }
 
#if RAPIDJSON_HAS_STDSTRING
    template <typename stackAllocator>
    ValueType& GetWithDefault(
        GenericDocument<EncodingType, typename ValueType::AllocatorType, stackAllocator>& document,
        const std::basic_string<Ch>& defaultValue) const
    {
        return GetWithDefault(document, defaultValue, document.GetAllocator());
    }
#endif
    template <typename T, typename stackAllocator>
    RAPIDJSON_DISABLEIF_RETURN(
        (internal::OrExpr<internal::IsPointer<T>, internal::IsGenericValue<T>>), (ValueType&))
    GetWithDefault(
        GenericDocument<EncodingType, typename ValueType::AllocatorType, stackAllocator>& document,
        T defaultValue) const
    {
        return GetWithDefault(document, defaultValue, document.GetAllocator());
    }
    ValueType&
    Set(ValueType& root, ValueType& value, typename ValueType::AllocatorType& allocator) const
    {
        return Create(root, allocator) = value;
    }
    ValueType&
    Set(ValueType& root, const ValueType& value, typename ValueType::AllocatorType& allocator) const
    {
        return Create(root, allocator).CopyFrom(value, allocator);
    }
    ValueType&
    Set(ValueType& root, const Ch* value, typename ValueType::AllocatorType& allocator) const
    {
        return Create(root, allocator) = ValueType(value, allocator).Move();
    }
 
#if RAPIDJSON_HAS_STDSTRING
    ValueType& Set(ValueType& root,
                   const std::basic_string<Ch>& value,
                   typename ValueType::AllocatorType& allocator) const
    {
        return Create(root, allocator) = ValueType(value, allocator).Move();
    }
#endif
    template <typename T>
    RAPIDJSON_DISABLEIF_RETURN(
        (internal::OrExpr<internal::IsPointer<T>, internal::IsGenericValue<T>>), (ValueType&))
    Set(ValueType& root, T value, typename ValueType::AllocatorType& allocator) const
    {
        return Create(root, allocator) = ValueType(value).Move();
    }
    template <typename stackAllocator>
    ValueType&
    Set(GenericDocument<EncodingType, typename ValueType::AllocatorType, stackAllocator>& document,
        ValueType& value) const
    {
        return Create(document) = value;
    }
    template <typename stackAllocator>
    ValueType&
    Set(GenericDocument<EncodingType, typename ValueType::AllocatorType, stackAllocator>& document,
        const ValueType& value) const
    {
        return Create(document).CopyFrom(value, document.GetAllocator());
    }
    template <typename stackAllocator>
    ValueType&
    Set(GenericDocument<EncodingType, typename ValueType::AllocatorType, stackAllocator>& document,
        const Ch* value) const
    {
        return Create(document) = ValueType(value, document.GetAllocator()).Move();
    }
 
#if RAPIDJSON_HAS_STDSTRING
    template <typename stackAllocator>
    ValueType&
    Set(GenericDocument<EncodingType, typename ValueType::AllocatorType, stackAllocator>& document,
        const std::basic_string<Ch>& value) const
    {
        return Create(document) = ValueType(value, document.GetAllocator()).Move();
    }
#endif
    template <typename T, typename stackAllocator>
    RAPIDJSON_DISABLEIF_RETURN(
        (internal::OrExpr<internal::IsPointer<T>, internal::IsGenericValue<T>>), (ValueType&))
    Set(GenericDocument<EncodingType, typename ValueType::AllocatorType, stackAllocator>& document,
        T value) const
    {
        return Create(document) = value;
    }
    ValueType&
    Swap(ValueType& root, ValueType& value, typename ValueType::AllocatorType& allocator) const
    {
        return Create(root, allocator).Swap(value);
    }
    template <typename stackAllocator>
    ValueType&
    Swap(GenericDocument<EncodingType, typename ValueType::AllocatorType, stackAllocator>& document,
         ValueType& value) const
    {
        return Create(document).Swap(value);
    }
    bool Erase(ValueType& root) const
    {
        RAPIDJSON_ASSERT(IsValid());
        if(tokenCount_ == 0) // Cannot erase the root
            return false;
 
        ValueType* v      = &root;
        const Token* last = tokens_ + (tokenCount_ - 1);
        for(const Token* t = tokens_; t != last; ++t)
        {
            switch(v->GetType())
            {
            case kObjectType: {
                typename ValueType::MemberIterator m = v->FindMember(
                    GenericValue<EncodingType>(GenericStringRef<Ch>(t->name, t->length)));
                if(m == v->MemberEnd())
                    return false;
                v = &m->value;
            }
            break;
            case kArrayType:
                if(t->index == kPointerInvalidIndex || t->index >= v->Size())
                    return false;
                v = &((*v)[t->index]);
                break;
            default: return false;
            }
        }
 
        switch(v->GetType())
        {
        case kObjectType: return v->EraseMember(GenericStringRef<Ch>(last->name, last->length));
        case kArrayType:
            if(last->index == kPointerInvalidIndex || last->index >= v->Size())
                return false;
            v->Erase(v->Begin() + last->index);
            return true;
        default: return false;
        }
    }
 
    private:
    Ch*
    CopyFromRaw(const GenericPointer& rhs, size_t extraToken = 0, size_t extraNameBufferSize = 0)
    {
        if(!allocator_) // allocator is independently owned.
            ownAllocator_ = allocator_ = RAPIDJSON_NEW(Allocator)();
 
        size_t nameBufferSize = rhs.tokenCount_; // null terminators for tokens
        for(Token* t = rhs.tokens_; t != rhs.tokens_ + rhs.tokenCount_; ++t)
            nameBufferSize += t->length;
 
        tokenCount_ = rhs.tokenCount_ + extraToken;
        tokens_     = static_cast<Token*>(allocator_->Malloc(
            tokenCount_ * sizeof(Token) + (nameBufferSize + extraNameBufferSize) * sizeof(Ch)));
        nameBuffer_ = reinterpret_cast<Ch*>(tokens_ + tokenCount_);
        if(rhs.tokenCount_ > 0)
        {
            std::memcpy(tokens_, rhs.tokens_, rhs.tokenCount_ * sizeof(Token));
        }
        if(nameBufferSize > 0)
        {
            std::memcpy(nameBuffer_, rhs.nameBuffer_, nameBufferSize * sizeof(Ch));
        }
 
        // The names of each token point to a string in the nameBuffer_. The
        // previous memcpy copied over string pointers into the rhs.nameBuffer_,
        // but they should point to the strings in the new nameBuffer_.
        for(size_t i = 0; i < rhs.tokenCount_; ++i)
        {
            // The offset between the string address and the name buffer should
            // still be constant, so we can just get this offset and set each new
            // token name according the new buffer start + the known offset.
            std::ptrdiff_t name_offset = rhs.tokens_[i].name - rhs.nameBuffer_;
            tokens_[i].name            = nameBuffer_ + name_offset;
        }
 
        return nameBuffer_ + nameBufferSize;
    }
    bool NeedPercentEncode(Ch c) const
    {
        return !((c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') ||
                 c == '-' || c == '.' || c == '_' || c == '~');
    }
#ifndef __clang__ // -Wdocumentation
#endif
    void Parse(const Ch* source, size_t length)
    {
        RAPIDJSON_ASSERT(source != NULL);
        RAPIDJSON_ASSERT(nameBuffer_ == 0);
        RAPIDJSON_ASSERT(tokens_ == 0);
 
        // Create own allocator if user did not supply.
        if(!allocator_)
            ownAllocator_ = allocator_ = RAPIDJSON_NEW(Allocator)();
 
        // Count number of '/' as tokenCount
        tokenCount_ = 0;
        for(const Ch* s = source; s != source + length; s++)
            if(*s == '/')
                tokenCount_++;
 
        Token* token = tokens_ = static_cast<Token*>(
            allocator_->Malloc(tokenCount_ * sizeof(Token) + length * sizeof(Ch)));
        Ch* name = nameBuffer_ = reinterpret_cast<Ch*>(tokens_ + tokenCount_);
        size_t i               = 0;
 
        // Detect if it is a URI fragment
        bool uriFragment = false;
        if(source[i] == '#')
        {
            uriFragment = true;
            i++;
        }
 
        if(i != length && source[i] != '/')
        {
            parseErrorCode_ = kPointerParseErrorTokenMustBeginWithSolidus;
            goto error;
        }
 
        while(i < length)
        {
            RAPIDJSON_ASSERT(source[i] == '/');
            i++; // consumes '/'
 
            token->name   = name;
            bool isNumber = true;
 
            while(i < length && source[i] != '/')
            {
                Ch c = source[i];
                if(uriFragment)
                {
                    // Decoding percent-encoding for URI fragment
                    if(c == '%')
                    {
                        PercentDecodeStream is(&source[i], source + length);
                        GenericInsituStringStream<EncodingType> os(name);
                        Ch* begin = os.PutBegin();
                        if(!Transcoder<UTF8<>, EncodingType>().Validate(is, os) || !is.IsValid())
                        {
                            parseErrorCode_ = kPointerParseErrorInvalidPercentEncoding;
                            goto error;
                        }
                        size_t len = os.PutEnd(begin);
                        i += is.Tell() - 1;
                        if(len == 1)
                            c = *name;
                        else
                        {
                            name += len;
                            isNumber = false;
                            i++;
                            continue;
                        }
                    }
                    else if(NeedPercentEncode(c))
                    {
                        parseErrorCode_ = kPointerParseErrorCharacterMustPercentEncode;
                        goto error;
                    }
                }
 
                i++;
 
                // Escaping "~0" -> '~', "~1" -> '/'
                if(c == '~')
                {
                    if(i < length)
                    {
                        c = source[i];
                        if(c == '0')
                            c = '~';
                        else if(c == '1')
                            c = '/';
                        else
                        {
                            parseErrorCode_ = kPointerParseErrorInvalidEscape;
                            goto error;
                        }
                        i++;
                    }
                    else
                    {
                        parseErrorCode_ = kPointerParseErrorInvalidEscape;
                        goto error;
                    }
                }
 
                // First check for index: all of characters are digit
                if(c < '0' || c > '9')
                    isNumber = false;
 
                *name++ = c;
            }
            token->length = static_cast<SizeType>(name - token->name);
            if(token->length == 0)
                isNumber = false;
            *name++ = '\0'; // Null terminator
 
            // Second check for index: more than one digit cannot have leading zero
            if(isNumber && token->length > 1 && token->name[0] == '0')
                isNumber = false;
 
            // String to SizeType conversion
            SizeType n = 0;
            if(isNumber)
            {
                for(size_t j = 0; j < token->length; j++)
                {
                    SizeType m = n * 10 + static_cast<SizeType>(token->name[j] - '0');
                    if(m < n)
                    { // overflow detection
                        isNumber = false;
                        break;
                    }
                    n = m;
                }
            }
 
            token->index = isNumber ? n : kPointerInvalidIndex;
            token++;
        }
 
        RAPIDJSON_ASSERT(name <= nameBuffer_ + length); // Should not overflow buffer
        parseErrorCode_ = kPointerParseErrorNone;
        return;
 
    error:
        Allocator::Free(tokens_);
        nameBuffer_       = 0;
        tokens_           = 0;
        tokenCount_       = 0;
        parseErrorOffset_ = i;
        return;
    }
    template <bool uriFragment, typename OutputStream>
    bool Stringify(OutputStream& os) const
    {
        RAPIDJSON_ASSERT(IsValid());
 
        if(uriFragment)
            os.Put('#');
 
        for(Token* t = tokens_; t != tokens_ + tokenCount_; ++t)
        {
            os.Put('/');
            for(size_t j = 0; j < t->length; j++)
            {
                Ch c = t->name[j];
                if(c == '~')
                {
                    os.Put('~');
                    os.Put('0');
                }
                else if(c == '/')
                {
                    os.Put('~');
                    os.Put('1');
                }
                else if(uriFragment && NeedPercentEncode(c))
                {
                    // Transcode to UTF8 sequence
                    GenericStringStream<typename ValueType::EncodingType> source(&t->name[j]);
                    PercentEncodeStream<OutputStream> target(os);
                    if(!Transcoder<EncodingType, UTF8<>>().Validate(source, target))
                        return false;
                    j += source.Tell() - 1;
                }
                else
                    os.Put(c);
            }
        }
        return true;
    }
    class PercentDecodeStream
    {
        public:
        typedef typename ValueType::Ch Ch;
        PercentDecodeStream(const Ch* source, const Ch* end)
            : src_(source), head_(source), end_(end), valid_(true)
        {
        }
 
        Ch Take()
        {
            if(*src_ != '%' || src_ + 3 > end_)
            { // %XY triplet
                valid_ = false;
                return 0;
            }
            src_++;
            Ch c = 0;
            for(int j = 0; j < 2; j++)
            {
                c    = static_cast<Ch>(c << 4);
                Ch h = *src_;
                if(h >= '0' && h <= '9')
                    c = static_cast<Ch>(c + h - '0');
                else if(h >= 'A' && h <= 'F')
                    c = static_cast<Ch>(c + h - 'A' + 10);
                else if(h >= 'a' && h <= 'f')
                    c = static_cast<Ch>(c + h - 'a' + 10);
                else
                {
                    valid_ = false;
                    return 0;
                }
                src_++;
            }
            return c;
        }
 
        size_t Tell() const { return static_cast<size_t>(src_ - head_); }
        bool IsValid() const { return valid_; }
 
        private:
        const Ch* src_;  
        const Ch* head_; 
        const Ch* end_;  
        bool valid_;     
    };
    template <typename OutputStream>
    class PercentEncodeStream
    {
        public:
        PercentEncodeStream(OutputStream& os) : os_(os) {}
        void Put(char c)
        { // UTF-8 must be byte
            unsigned char u                 = static_cast<unsigned char>(c);
            static const char hexDigits[16] = {
                '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
            os_.Put('%');
            os_.Put(static_cast<typename OutputStream::Ch>(hexDigits[u >> 4]));
            os_.Put(static_cast<typename OutputStream::Ch>(hexDigits[u & 15]));
        }
 
        private:
        OutputStream& os_;
    };
 
    Allocator* allocator_;    
    Allocator* ownAllocator_; 
    Ch* nameBuffer_;          
    Token* tokens_;           
    size_t tokenCount_;       
    size_t parseErrorOffset_; 
    PointerParseErrorCode parseErrorCode_; 
};
typedef GenericPointer<Value> Pointer;
 
template <typename T>
typename T::ValueType& CreateValueByPointer(T& root,
                                            const GenericPointer<typename T::ValueType>& pointer,
                                            typename T::AllocatorType& a)
{
    return pointer.Create(root, a);
}
 
template <typename T, typename CharType, size_t N>
typename T::ValueType&
CreateValueByPointer(T& root, const CharType (&source)[N], typename T::AllocatorType& a)
{
    return GenericPointer<typename T::ValueType>(source, N - 1).Create(root, a);
}
 
// No allocator parameter
 
template <typename DocumentType>
typename DocumentType::ValueType&
CreateValueByPointer(DocumentType& document,
                     const GenericPointer<typename DocumentType::ValueType>& pointer)
{
    return pointer.Create(document);
}
 
template <typename DocumentType, typename CharType, size_t N>
typename DocumentType::ValueType& CreateValueByPointer(DocumentType& document,
                                                       const CharType (&source)[N])
{
    return GenericPointer<typename DocumentType::ValueType>(source, N - 1).Create(document);
}
 
template <typename T>
typename T::ValueType* GetValueByPointer(T& root,
                                         const GenericPointer<typename T::ValueType>& pointer,
                                         size_t* unresolvedTokenIndex = 0)
{
    return pointer.Get(root, unresolvedTokenIndex);
}
 
template <typename T>
const typename T::ValueType* GetValueByPointer(const T& root,
                                               const GenericPointer<typename T::ValueType>& pointer,
                                               size_t* unresolvedTokenIndex = 0)
{
    return pointer.Get(root, unresolvedTokenIndex);
}
 
template <typename T, typename CharType, size_t N>
typename T::ValueType*
GetValueByPointer(T& root, const CharType (&source)[N], size_t* unresolvedTokenIndex = 0)
{
    return GenericPointer<typename T::ValueType>(source, N - 1).Get(root, unresolvedTokenIndex);
}
 
template <typename T, typename CharType, size_t N>
const typename T::ValueType*
GetValueByPointer(const T& root, const CharType (&source)[N], size_t* unresolvedTokenIndex = 0)
{
    return GenericPointer<typename T::ValueType>(source, N - 1).Get(root, unresolvedTokenIndex);
}
 
template <typename T>
typename T::ValueType&
GetValueByPointerWithDefault(T& root,
                             const GenericPointer<typename T::ValueType>& pointer,
                             const typename T::ValueType& defaultValue,
                             typename T::AllocatorType& a)
{
    return pointer.GetWithDefault(root, defaultValue, a);
}
 
template <typename T>
typename T::ValueType&
GetValueByPointerWithDefault(T& root,
                             const GenericPointer<typename T::ValueType>& pointer,
                             const typename T::Ch* defaultValue,
                             typename T::AllocatorType& a)
{
    return pointer.GetWithDefault(root, defaultValue, a);
}
 
#if RAPIDJSON_HAS_STDSTRING
template <typename T>
typename T::ValueType&
GetValueByPointerWithDefault(T& root,
                             const GenericPointer<typename T::ValueType>& pointer,
                             const std::basic_string<typename T::Ch>& defaultValue,
                             typename T::AllocatorType& a)
{
    return pointer.GetWithDefault(root, defaultValue, a);
}
#endif
 
template <typename T, typename T2>
RAPIDJSON_DISABLEIF_RETURN(
    (internal::OrExpr<internal::IsPointer<T2>, internal::IsGenericValue<T2>>),
    (typename T::ValueType&))
GetValueByPointerWithDefault(T& root,
                             const GenericPointer<typename T::ValueType>& pointer,
                             T2 defaultValue,
                             typename T::AllocatorType& a)
{
    return pointer.GetWithDefault(root, defaultValue, a);
}
 
template <typename T, typename CharType, size_t N>
typename T::ValueType& GetValueByPointerWithDefault(T& root,
                                                    const CharType (&source)[N],
                                                    const typename T::ValueType& defaultValue,
                                                    typename T::AllocatorType& a)
{
    return GenericPointer<typename T::ValueType>(source, N - 1)
        .GetWithDefault(root, defaultValue, a);
}
 
template <typename T, typename CharType, size_t N>
typename T::ValueType& GetValueByPointerWithDefault(T& root,
                                                    const CharType (&source)[N],
                                                    const typename T::Ch* defaultValue,
                                                    typename T::AllocatorType& a)
{
    return GenericPointer<typename T::ValueType>(source, N - 1)
        .GetWithDefault(root, defaultValue, a);
}
 
#if RAPIDJSON_HAS_STDSTRING
template <typename T, typename CharType, size_t N>
typename T::ValueType&
GetValueByPointerWithDefault(T& root,
                             const CharType (&source)[N],
                             const std::basic_string<typename T::Ch>& defaultValue,
                             typename T::AllocatorType& a)
{
    return GenericPointer<typename T::ValueType>(source, N - 1)
        .GetWithDefault(root, defaultValue, a);
}
#endif
 
template <typename T, typename CharType, size_t N, typename T2>
RAPIDJSON_DISABLEIF_RETURN(
    (internal::OrExpr<internal::IsPointer<T2>, internal::IsGenericValue<T2>>),
    (typename T::ValueType&))
GetValueByPointerWithDefault(T& root,
                             const CharType (&source)[N],
                             T2 defaultValue,
                             typename T::AllocatorType& a)
{
    return GenericPointer<typename T::ValueType>(source, N - 1)
        .GetWithDefault(root, defaultValue, a);
}
 
// No allocator parameter
 
template <typename DocumentType>
typename DocumentType::ValueType&
GetValueByPointerWithDefault(DocumentType& document,
                             const GenericPointer<typename DocumentType::ValueType>& pointer,
                             const typename DocumentType::ValueType& defaultValue)
{
    return pointer.GetWithDefault(document, defaultValue);
}
 
template <typename DocumentType>
typename DocumentType::ValueType&
GetValueByPointerWithDefault(DocumentType& document,
                             const GenericPointer<typename DocumentType::ValueType>& pointer,
                             const typename DocumentType::Ch* defaultValue)
{
    return pointer.GetWithDefault(document, defaultValue);
}
 
#if RAPIDJSON_HAS_STDSTRING
template <typename DocumentType>
typename DocumentType::ValueType&
GetValueByPointerWithDefault(DocumentType& document,
                             const GenericPointer<typename DocumentType::ValueType>& pointer,
                             const std::basic_string<typename DocumentType::Ch>& defaultValue)
{
    return pointer.GetWithDefault(document, defaultValue);
}
#endif
 
template <typename DocumentType, typename T2>
RAPIDJSON_DISABLEIF_RETURN(
    (internal::OrExpr<internal::IsPointer<T2>, internal::IsGenericValue<T2>>),
    (typename DocumentType::ValueType&))
GetValueByPointerWithDefault(DocumentType& document,
                             const GenericPointer<typename DocumentType::ValueType>& pointer,
                             T2 defaultValue)
{
    return pointer.GetWithDefault(document, defaultValue);
}
 
template <typename DocumentType, typename CharType, size_t N>
typename DocumentType::ValueType&
GetValueByPointerWithDefault(DocumentType& document,
                             const CharType (&source)[N],
                             const typename DocumentType::ValueType& defaultValue)
{
    return GenericPointer<typename DocumentType::ValueType>(source, N - 1)
        .GetWithDefault(document, defaultValue);
}
 
template <typename DocumentType, typename CharType, size_t N>
typename DocumentType::ValueType&
GetValueByPointerWithDefault(DocumentType& document,
                             const CharType (&source)[N],
                             const typename DocumentType::Ch* defaultValue)
{
    return GenericPointer<typename DocumentType::ValueType>(source, N - 1)
        .GetWithDefault(document, defaultValue);
}
 
#if RAPIDJSON_HAS_STDSTRING
template <typename DocumentType, typename CharType, size_t N>
typename DocumentType::ValueType&
GetValueByPointerWithDefault(DocumentType& document,
                             const CharType (&source)[N],
                             const std::basic_string<typename DocumentType::Ch>& defaultValue)
{
    return GenericPointer<typename DocumentType::ValueType>(source, N - 1)
        .GetWithDefault(document, defaultValue);
}
#endif
 
template <typename DocumentType, typename CharType, size_t N, typename T2>
RAPIDJSON_DISABLEIF_RETURN(
    (internal::OrExpr<internal::IsPointer<T2>, internal::IsGenericValue<T2>>),
    (typename DocumentType::ValueType&))
GetValueByPointerWithDefault(DocumentType& document, const CharType (&source)[N], T2 defaultValue)
{
    return GenericPointer<typename DocumentType::ValueType>(source, N - 1)
        .GetWithDefault(document, defaultValue);
}
 
template <typename T>
typename T::ValueType& SetValueByPointer(T& root,
                                         const GenericPointer<typename T::ValueType>& pointer,
                                         typename T::ValueType& value,
                                         typename T::AllocatorType& a)
{
    return pointer.Set(root, value, a);
}
 
template <typename T>
typename T::ValueType& SetValueByPointer(T& root,
                                         const GenericPointer<typename T::ValueType>& pointer,
                                         const typename T::ValueType& value,
                                         typename T::AllocatorType& a)
{
    return pointer.Set(root, value, a);
}
 
template <typename T>
typename T::ValueType& SetValueByPointer(T& root,
                                         const GenericPointer<typename T::ValueType>& pointer,
                                         const typename T::Ch* value,
                                         typename T::AllocatorType& a)
{
    return pointer.Set(root, value, a);
}
 
#if RAPIDJSON_HAS_STDSTRING
template <typename T>
typename T::ValueType& SetValueByPointer(T& root,
                                         const GenericPointer<typename T::ValueType>& pointer,
                                         const std::basic_string<typename T::Ch>& value,
                                         typename T::AllocatorType& a)
{
    return pointer.Set(root, value, a);
}
#endif
 
template <typename T, typename T2>
RAPIDJSON_DISABLEIF_RETURN(
    (internal::OrExpr<internal::IsPointer<T2>, internal::IsGenericValue<T2>>),
    (typename T::ValueType&))
SetValueByPointer(T& root,
                  const GenericPointer<typename T::ValueType>& pointer,
                  T2 value,
                  typename T::AllocatorType& a)
{
    return pointer.Set(root, value, a);
}
 
template <typename T, typename CharType, size_t N>
typename T::ValueType& SetValueByPointer(T& root,
                                         const CharType (&source)[N],
                                         typename T::ValueType& value,
                                         typename T::AllocatorType& a)
{
    return GenericPointer<typename T::ValueType>(source, N - 1).Set(root, value, a);
}
 
template <typename T, typename CharType, size_t N>
typename T::ValueType& SetValueByPointer(T& root,
                                         const CharType (&source)[N],
                                         const typename T::ValueType& value,
                                         typename T::AllocatorType& a)
{
    return GenericPointer<typename T::ValueType>(source, N - 1).Set(root, value, a);
}
 
template <typename T, typename CharType, size_t N>
typename T::ValueType& SetValueByPointer(T& root,
                                         const CharType (&source)[N],
                                         const typename T::Ch* value,
                                         typename T::AllocatorType& a)
{
    return GenericPointer<typename T::ValueType>(source, N - 1).Set(root, value, a);
}
 
#if RAPIDJSON_HAS_STDSTRING
template <typename T, typename CharType, size_t N>
typename T::ValueType& SetValueByPointer(T& root,
                                         const CharType (&source)[N],
                                         const std::basic_string<typename T::Ch>& value,
                                         typename T::AllocatorType& a)
{
    return GenericPointer<typename T::ValueType>(source, N - 1).Set(root, value, a);
}
#endif
 
template <typename T, typename CharType, size_t N, typename T2>
RAPIDJSON_DISABLEIF_RETURN(
    (internal::OrExpr<internal::IsPointer<T2>, internal::IsGenericValue<T2>>),
    (typename T::ValueType&))
SetValueByPointer(T& root, const CharType (&source)[N], T2 value, typename T::AllocatorType& a)
{
    return GenericPointer<typename T::ValueType>(source, N - 1).Set(root, value, a);
}
 
// No allocator parameter
 
template <typename DocumentType>
typename DocumentType::ValueType&
SetValueByPointer(DocumentType& document,
                  const GenericPointer<typename DocumentType::ValueType>& pointer,
                  typename DocumentType::ValueType& value)
{
    return pointer.Set(document, value);
}
 
template <typename DocumentType>
typename DocumentType::ValueType&
SetValueByPointer(DocumentType& document,
                  const GenericPointer<typename DocumentType::ValueType>& pointer,
                  const typename DocumentType::ValueType& value)
{
    return pointer.Set(document, value);
}
 
template <typename DocumentType>
typename DocumentType::ValueType&
SetValueByPointer(DocumentType& document,
                  const GenericPointer<typename DocumentType::ValueType>& pointer,
                  const typename DocumentType::Ch* value)
{
    return pointer.Set(document, value);
}
 
#if RAPIDJSON_HAS_STDSTRING
template <typename DocumentType>
typename DocumentType::ValueType&
SetValueByPointer(DocumentType& document,
                  const GenericPointer<typename DocumentType::ValueType>& pointer,
                  const std::basic_string<typename DocumentType::Ch>& value)
{
    return pointer.Set(document, value);
}
#endif
 
template <typename DocumentType, typename T2>
RAPIDJSON_DISABLEIF_RETURN(
    (internal::OrExpr<internal::IsPointer<T2>, internal::IsGenericValue<T2>>),
    (typename DocumentType::ValueType&))
SetValueByPointer(DocumentType& document,
                  const GenericPointer<typename DocumentType::ValueType>& pointer,
                  T2 value)
{
    return pointer.Set(document, value);
}
 
template <typename DocumentType, typename CharType, size_t N>
typename DocumentType::ValueType& SetValueByPointer(DocumentType& document,
                                                    const CharType (&source)[N],
                                                    typename DocumentType::ValueType& value)
{
    return GenericPointer<typename DocumentType::ValueType>(source, N - 1).Set(document, value);
}
 
template <typename DocumentType, typename CharType, size_t N>
typename DocumentType::ValueType& SetValueByPointer(DocumentType& document,
                                                    const CharType (&source)[N],
                                                    const typename DocumentType::ValueType& value)
{
    return GenericPointer<typename DocumentType::ValueType>(source, N - 1).Set(document, value);
}
 
template <typename DocumentType, typename CharType, size_t N>
typename DocumentType::ValueType& SetValueByPointer(DocumentType& document,
                                                    const CharType (&source)[N],
                                                    const typename DocumentType::Ch* value)
{
    return GenericPointer<typename DocumentType::ValueType>(source, N - 1).Set(document, value);
}
 
#if RAPIDJSON_HAS_STDSTRING
template <typename DocumentType, typename CharType, size_t N>
typename DocumentType::ValueType&
SetValueByPointer(DocumentType& document,
                  const CharType (&source)[N],
                  const std::basic_string<typename DocumentType::Ch>& value)
{
    return GenericPointer<typename DocumentType::ValueType>(source, N - 1).Set(document, value);
}
#endif
 
template <typename DocumentType, typename CharType, size_t N, typename T2>
RAPIDJSON_DISABLEIF_RETURN(
    (internal::OrExpr<internal::IsPointer<T2>, internal::IsGenericValue<T2>>),
    (typename DocumentType::ValueType&))
SetValueByPointer(DocumentType& document, const CharType (&source)[N], T2 value)
{
    return GenericPointer<typename DocumentType::ValueType>(source, N - 1).Set(document, value);
}
 
template <typename T>
typename T::ValueType& SwapValueByPointer(T& root,
                                          const GenericPointer<typename T::ValueType>& pointer,
                                          typename T::ValueType& value,
                                          typename T::AllocatorType& a)
{
    return pointer.Swap(root, value, a);
}
 
template <typename T, typename CharType, size_t N>
typename T::ValueType& SwapValueByPointer(T& root,
                                          const CharType (&source)[N],
                                          typename T::ValueType& value,
                                          typename T::AllocatorType& a)
{
    return GenericPointer<typename T::ValueType>(source, N - 1).Swap(root, value, a);
}
 
template <typename DocumentType>
typename DocumentType::ValueType&
SwapValueByPointer(DocumentType& document,
                   const GenericPointer<typename DocumentType::ValueType>& pointer,
                   typename DocumentType::ValueType& value)
{
    return pointer.Swap(document, value);
}
 
template <typename DocumentType, typename CharType, size_t N>
typename DocumentType::ValueType& SwapValueByPointer(DocumentType& document,
                                                     const CharType (&source)[N],
                                                     typename DocumentType::ValueType& value)
{
    return GenericPointer<typename DocumentType::ValueType>(source, N - 1).Swap(document, value);
}
 
template <typename T>
bool EraseValueByPointer(T& root, const GenericPointer<typename T::ValueType>& pointer)
{
    return pointer.Erase(root);
}
 
template <typename T, typename CharType, size_t N>
bool EraseValueByPointer(T& root, const CharType (&source)[N])
{
    return GenericPointer<typename T::ValueType>(source, N - 1).Erase(root);
}
 
RAPIDJSON_NAMESPACE_END
 
#if defined(__clang__) || defined(_MSC_VER)
RAPIDJSON_DIAG_POP
#endif
 
#endif // RAPIDJSON_POINTER_H_