pointer.h

Go to the documentation of this 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. All
// rights reserved.
//
// 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 "internal/itoa.h"

#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

RAPIDJSON_NAMESPACE_BEGIN

static const SizeType kPointerInvalidIndex =
    ~SizeType(0);  


enum PointerParseErrorCode {
  kPointerParseErrorNone = 0,  

  kPointerParseErrorTokenMustBeginWithSolidus,  
  kPointerParseErrorInvalidEscape,              
  kPointerParseErrorInvalidPercentEncoding,     
  kPointerParseErrorCharacterMustPercentEncode  
};

// GenericPointer


template <typename ValueType, typename Allocator = CrtAllocator>
class GenericPointer {
 public:
  typedef typename ValueType::EncodingType
      EncodingType;                   
  typedef typename ValueType::Ch Ch;  


  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_(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';

    if (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);
  }





  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));
    }

    // Adjust pointers to name buffer
    std::ptrdiff_t diff = nameBuffer_ - rhs.nameBuffer_;
    for (Token *t = tokens_; t != tokens_ + rhs.tokenCount_; ++t)
      t->name += diff;

    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_