Menu
Article

RapidJSON源码剖析

NodeKey

NodeKey

• 9 min read

前言

RapidJSON是腾讯开发的一个开源json解析代码库，因为在公司里经常用到，并且总是会踩坑，因此我这里也开个坑用来记录我对RapidJSON的学习与理解。

学习一个json库，我们关注的无非有以下几点：

  1. json如何存储
  2. json如何解析与反解析

而选择使用一个json库，我们关注的则是以下几点：

  1. 安全性
  2. 运行效率
  3. 易用性

下面我会按照以上几点一一展开

json存储

关于其存储结构，就我而言第一个想法肯定是直接先构造一个支持增删改查的树，再将这个树运用在json存储中。但其实相当意外的，因为json使用时候的特殊性，其存储结构只要线性（伪）即可。

// AddMember
GenericValue& AddMember(GenericValue& name, GenericValue& value, Allocator& allocator) {
    RAPIDJSON_ASSERT(IsObject());
    RAPIDJSON_ASSERT(name.IsString());

    ObjectData& o = data_.o;
    if (o.size >= o.capacity)
            MemberReserve(o.capacity == 0 ? kDefaultObjectCapacity : (o.capacity + (o.capacity + 1) / 2), allocator);
    Member* members = GetMembersPointer();
    members[o.size].name.RawAssign(name);
    members[o.size].value.RawAssign(value);
    o.size++;
    return *this;
}

众所周知，json中除了object与array以外就是基础类型。那么每一个object与array就让他是动态的，实现方法很简单，即让上一层中对于object与array只保留指针。而在每一个object与array中则是动态线性数组。
（当然值得注意的小细节是在Reserve的时候其首指针可能会发生变化，不过这就是在编码时候的事情了）

下面来看下这样的数据结构的增删改查操作：

  • 查: 可以直接遍历每一个object或array，查找相应的目标即可。因为json是以字符串索引的，也可以建立字典树或hash增快索引速度。
  • 增: 增加操作只能对object与array操作，因此，先找到相应的节点，然后再在这个线性数组后面增加这个key:value即可。
  • 删除: 稍微耗时一点的操作应该就是删除这个，可以直接删除这个元素，然后将后面的元素向前推进。也可以用内存换耗时，只删除，然后在扩展数组的时候重新排列。
  • 改: 删+增即可。

至此，这个（伪）线性结构已经可以满足json的需求，不必需求更加复杂的了。

json解析与反解析

json解析与反解析其实在已有树与构造树的方法的基础的时候，只要使用深度优先搜索算法即可。（很简单就可以想到的……）

但是程序 = 数据结构 + 算法。
算法已经了然，rapidjson的数据结构与其架构还是十分值得讨论的。

architecture-1
如图所示，这是官方给出的SAX与DOM的UML图，然后以下是官方给出的架构解释：

关系的核心是 Handler 概念。在 SAX 一边，Reader 从流解析 JSON 并将事件发送到 Handler。Writer 实现了 Handler 概念，用于处理相同的事件。在 DOM 一边，Document 实现了 Handler 概念，用于通过这些时间来构建 DOM。Value 支持了 Value::Accept(Handler&) 函数，它可以将 DOM 转换为事件进行发送。
在这个设计，SAX 是不依赖于 DOM 的。甚至 Reader 和 Writer 之间也没有依赖。这提供了连接事件发送器和处理器的灵活性。除此之外，Value 也是不依赖于 SAX 的。所以，除了将 DOM 序列化为 JSON 之外，用户也可以将其序列化为 XML，或者做任何其他事情。

至少我看着有点累蛤……

我比较喜欢结合代码理解。下面示例一下核心代码对其解释。

解析

简单说其实json解析的时候会调用Parse方法，该方法会使用 SAX 的Reader，真正解析的实际在与Reader，在这之后Reader会使用Document的函数进行回调。

template <unsigned parseFlags, typename SourceEncoding, typename InputStream>
GenericDocument& ParseStream(InputStream& is) {
    GenericReader<SourceEncoding, Encoding, StackAllocator> reader(
        stack_.HasAllocator() ? &stack_.GetAllocator() : 0);
    ClearStackOnExit scope(*this);
    parseResult_ = reader.template Parse<parseFlags>(is, *this); // 实际解析操作
    if (parseResult_) {
        RAPIDJSON_ASSERT(stack_.GetSize() == sizeof(ValueType)); // Got one and only one root object
        ValueType::operator=(*stack_.template Pop<ValueType>(1));// Move value from stack to document
    }
    return *this
}

然后我们看下Reader的Parse源码，可以看到的是，Document以自身实现handler，并将自身传递给Reader，Reader的所有消息都将传给Document再由Document处理。

template <unsigned parseFlags, typename InputStream, typename Handler>
    ParseResult Parse(InputStream& is, Handler& handler) {
        if (parseFlags & kParseIterativeFlag)
            return IterativeParse<parseFlags>(is, handler);

        parseResult_.Clear();

        ClearStackOnExit scope(*this);

        SkipWhitespaceAndComments<parseFlags>(is);
        RAPIDJSON_PARSE_ERROR_EARLY_RETURN(parseResult_);

        if (RAPIDJSON_UNLIKELY(is.Peek() == '\0')) {
            RAPIDJSON_PARSE_ERROR_NORETURN(kParseErrorDocumentEmpty, is.Tell());
            RAPIDJSON_PARSE_ERROR_EARLY_RETURN(parseResult_);
        }
        else {
            ParseValue<parseFlags>(is, handler); // 整个函数实际操作的只有在这个函数
            RAPIDJSON_PARSE_ERROR_EARLY_RETURN(parseResult_);

            if (!(parseFlags & kParseStopWhenDoneFlag)) {
                SkipWhitespaceAndComments<parseFlags>(is);
                RAPIDJSON_PARSE_ERROR_EARLY_RETURN(parseResult_);

                if (RAPIDJSON_UNLIKELY(is.Peek() != '\0')) {
                    RAPIDJSON_PARSE_ERROR_NORETURN(kParseErrorDocumentRootNotSingular, is.Tell());
                    RAPIDJSON_PARSE_ERROR_EARLY_RETURN(parseResult_);
                }
            }
        }

        return parseResult_;
    }

在这之后则是ParseValue，而它则是根据解析的字符串判断类型再对其差异处理

template<unsigned parseFlags, typename InputStream, typename Handler>
void ParseValue(InputStream& is, Handler& handler) {
    switch (is.Peek()) {
        case 'n': ParseNull  <parseFlags>(is, handler); break;
        case 't': ParseTrue  <parseFlags>(is, handler); break;
        case 'f': ParseFalse <parseFlags>(is, handler); break;
        case '"': ParseString<parseFlags>(is, handler); break;
        case '{': ParseObject<parseFlags>(is, handler); break;
        case '[': ParseArray <parseFlags>(is, handler); break;
        default :
                  ParseNumber<parseFlags>(is, handler);
                  break;
    }
}

下面我以字符串源码为例子

template<unsigned parseFlags, typename InputStream, typename Handler>
void ParseString(InputStream& is, Handler& handler, bool isKey = false) {
    internal::StreamLocalCopy<InputStream> copy(is);
    InputStream& s(copy.s);
    
    RAPIDJSON_ASSERT(s.Peek() == '\"');
    s.Take();  // Skip '\"'

    bool success = false;
    if (parseFlags & kParseInsituFlag) {
        typename InputStream::Ch *head = s.PutBegin();
        ParseStringToStream<parseFlags, SourceEncoding, SourceEncoding>(s, s);
        RAPIDJSON_PARSE_ERROR_EARLY_RETURN_VOID;
        size_t length = s.PutEnd(head) - 1;
        RAPIDJSON_ASSERT(length <= 0xFFFFFFFF);
        const typename TargetEncoding::Ch* const str = reinterpret_cast<typename TargetEncoding::Ch*>(head);
        success = (isKey ? handler.Key(str, SizeType(length), false) : handler.String(str, SizeType(length), false)); // 看看看看这里，截取出字符串后，回调了handler的处理方法
    }
    else {
        StackStream<typename TargetEncoding::Ch> stackStream(stack_);
        ParseStringToStream<parseFlags, SourceEncoding, TargetEncoding>(s, stackStream);
        RAPIDJSON_PARSE_ERROR_EARLY_RETURN_VOID;
        SizeType length = static_cast<SizeType>(stackStream.Length()) - 1;
        const typename TargetEncoding::Ch* const str = stackStream.Pop();
        success = (isKey ? handler.Key(str, length, true) : handler.String(str, length, true)); // 同上
    }
    if (RAPIDJSON_UNLIKELY(!success))
        RAPIDJSON_PARSE_ERROR(kParseErrorTermination, s.Tell());
}

反解析

反解析则更为直接，在Value的Accept函数中，直接根据类型调用Handler的方法，而这Handler都是Writer或者其子类。

bool Accept(Handler& handler) const {
    switch(GetType()) {
    case kNullType:     return handler.Null();
    case kFalseType:    return handler.Bool(false);
    case kTrueType:     return handler.Bool(true);

    case kObjectType:
        if (RAPIDJSON_UNLIKELY(!handler.StartObject()))
            return false;
        for (ConstMemberIterator m = MemberBegin(); m != MemberEnd(); ++m) {
            RAPIDJSON_ASSERT(m->name.IsString()); // User may change the type of name by MemberIterator.
            if (RAPIDJSON_UNLIKELY(!handler.Key(m->name.GetString(), m->name.GetStringLength(), (m->name.data_.f.flags & kCopyFlag) != 0)))
                return false;
            if (RAPIDJSON_UNLIKELY(!m->value.Accept(handler)))
                return false;
        }
        return handler.EndObject(data_.o.size);
        
    case kArrayType:
        if (RAPIDJSON_UNLIKELY(!handler.StartArray()))
            return false;
        for (const GenericValue* v = Begin(); v != End(); ++v)
            if (RAPIDJSON_UNLIKELY(!v->Accept(handler)))
                return false;
            return handler.EndArray(data_.a.size);
    
    case kStringType:
            return handler.String(GetString(), GetStringLength(), (data_.f.flags & kCopyFlag) != 0);
    
    default:
        RAPIDJSON_ASSERT(GetType() == kNumberType);            
        if (IsDouble())         return handler.Double(data_.n.d);
        else if (IsInt())       return handler.Int(data_.n.i.i);
        else if (IsUint())      return handler.Uint(data_.n.u.u);
        else if (IsInt64())     return handler.Int64(data_.n.i64);
        else                    return handler.Uint64(data_.n.u64);
    }
}

安全性

在普通的业务需求中，我们最常使用的无非是Parse()，AddMember()，Accept()。
其中Parse函数只要保证所解析字符串是标准的json字符串即可，如果要谨慎的可以在解析之后调用HasParseError，Accept则使用规范即可。
而麻烦的则是AddMember，稍不留意就会出core。

AddMember

AddMember函数被重载了很多次，但实际上最后都会执行到下面这个代码。可以看到，实际上增加Member只是在Members这个动态数组中，使用RawAssign这个函数对给定的key: valule进行赋值。

GenericValue& AddMember(GenericValue& name, GenericValue& value, Allocator& allocator) {
    RAPIDJSON_ASSERT(IsObject());
    RAPIDJSON_ASSERT(name.IsString());

    ObjectData& o = data_.o;
    if (o.size >= o.capacity)
            MemberReserve(o.capacity == 0 ? kDefaultObjectCapacity : (o.capacity + (o.capacity + 1) / 2), allocator);
    Member* members = GetMembersPointer();
    members[o.size].name.RawAssign(name);
    members[o.size].value.RawAssign(value);
    o.size++;
    return *this;
}

再看一下RawAssign吧，RawAssign函数只是将其最关键的参数data_使用operator =赋值了一下，还有个flag赋值，这个可以暂时不需要关心。关于这个data_，其类型为一个union Data, 其operator =当然也不会进行重载。而其union中的所有类型中，除开基础类型和定长字符串外都为指针

void RawAssign(GenericValue& rhs) RAPIDJSON_NOEXCEPT {
    data_ = rhs.data_;
    // data_.f.flags = rhs.data_.f.flags;
    rhs.data_.f.flags = kNullFlag;
}

简单来说AddMember是将指针赋予给members数组，并且在这整个过程中并没有调用什么构造函数。
因此在使用AddMember的时候，务必保证自己参数的生存周期。
尤其是字符串之类的，若将string类型的字符串以c_str的方式传给AddMember, 函数会首先以赋值指针的方式新建一个Value（这里跟上文不同，是因为上文是指具体展示的函数，其他重载函数会新建Value，再传给上述函数）。

运行效率

以下是官方的比对参考。但基本是13年的，略显老旧。但也暂时没有找到合适的比对目标。
http://rapidjson.org/zh-cn/md_doc_performance_8zh-cn.html#autotoc_md57

10.6更新，以前同学推荐了一个比较新的json库，可以拿来做比对，时间关系，暂时搁置

github 传送门

易用性

因为rapidjson是几乎不依赖STL的库，个人觉得有些过于执着，其中最好用的功能，map与json互相转换并没有实现，总是AddMember十分麻烦又又隐患，我们宁可用适当内存换取安全与简便。希望上面那个号称modern C++的json库能有这个feature。

其他学到的地方

混合类型数据结构

举例来说就是python中list，它的成员可以是任意类型的变量。
其实现方法其实出乎意料的简单，简单说就是包含模板成员函数。这个模板类型必须与所在类区分开来，它们是相互独立的。在 internal/stack.h中有定义这个混合类型栈，简单易懂。

class Stack {
    Stack(Allocator* allocator, size_t stackCapacity);
    ~Stack();

    void Clear();
    void ShrinkToFit();
    
    template<typename T> T* Push(size_t count = 1);
    template<typename T> T* Pop(size_t count);
    template<typename T> T* Top();
    template<typename T> T* Bottom();

    Allocator& GetAllocator();
    bool Empty() const;
    size_t GetSize();
    size_t GetCapacity();
};

Share