spxml：使用 state pattern 实现 xml pull/dom parser

spxml 是一个实现了 pull 和 dom 两种解释模型的 xml 解释器。
spxml 使用 c++ 实现，除系统库之外，不依赖第三方库，目前实现了以下功能：
1.实现了 xml pull parser 的功能；
2.基于 xml pull parser 构造一个 dom tree；
3.能够对 dom tree 进行修改；
4.能把 dom tree 重新序列化为一个字符流；
5.处于底层的 xml pull parser 是一个面向流的解释器，用户不需要一次把一个完整的 xml 字符流传递给 spxml ，极端情况下，可以每次只传入一个字符。解释到一个文档结束时，自动生成 EndDocument 事件；
6.xml dom parser 同样继承了面向流的特性；
7.使用 xmlbench 框架做压力测试，性能与 expat 相当接近。

源代码下载：
http://spxml.googlecode.com/files/spxml-0.3.src.tar.gz

一些设计思路的说明：

最近在使用 cpp 做 xmlrpc 相关的内容，顺便看了一下几个 xmlrpc 的实现，连带看了一下 expat 的实现。
发现 expat 的接口非常的精简，不过实现的代码比较长，比较难读。
看完之后，有空的时候就在思考有什么办法可以简化 xml parser 的实现。
想了几天之后，想到一个方法：expat 里面有很多的 switch case 结构，要简化这些 switch ，最好使用 state pattern 。

具体的想法如下：
<<1>> 设计一个 XmlReader 类，作为 state pattern 中的 State 类。
  XmlReader 的多个子类作为 state pattern 的 ConcreteState 类，
  每个 reader 代表 xml parser 的一个状态。
  比如有：XmlDocDeclReader，XmlStartTagReader，XmlEndTagReader，XmlCDataReader，
  XmlCommentReader，XmlDocTypeReader等等。
<<2>> xml parser 本身作为 state pattern 中的 Context 类。

这样设计的好处（为描述方便，称这个 xml parser 为 spxml）：
<<1>> 每个 XmlReader 识别特定的开始符和结束符，把属于它自己的字符保存下来。
  在遇到它的结束符之后，设置 spxml 的后继 XmlReader。
<<2>> 每个 XmlReader 在读取到结束符之后，把保存下来的字符串转换成 parser 相应的事件。
  比如：对于 XmlStartTagReader 来说，如果是一个 pull-model 的 xml parser，
  将产生一个 START_TAG event；如果是一个 sax-model 的 xml parser，那么将产生
  StartElement event。
<<3>> 这样把 xml 的各个部分的处理分散到了不同的类里面，每个类只处理一类情况，
  这就使得 spxml 的实现从整体上简化了。
<<4>> spxml 像 expat 一样，是一个面向流的解释器。
  使用者可以把任意大小的 xml 片断（从一个字节到完整的 xml document）传递给 spxml 进行解释。
  expat 需要由使用者指出 xml document 何时结束；相反，spxml 不需要由调用者指定 xml document
  何时结束，在解释完 root element 之后，spxml 将返回 END_DOCUMENT 事件。
  因此 spxml 适合使用在类似 jabber 这类协议的通讯中。
  因为 jabber 的传输协议中，任意两个请求包中是没有明显的分隔符的，每个请求只是一个完整的 xml element。

为了验证一下自己的想法，趁这段时间休假，花了几天时间实现了一下，初步看起来还是不错的。目前针对简单的 xml 实现了 xml pull parser 和 xml dom parser，足够用来处理 xmlrpc。

实现完全不是问题.
不过...如果我记得没有错expat是纯C的代码，所以很多地方不得不如此实现，而且大量使用了C中的一些小技巧，所以可读性降低.
但是它的功能很强大,速度方面也很好，而且因为是C的，所以移植性很好，可以很容易用于很多不支持C++开发的平台。

对 spxml 和 expat 做了一下性能测试。
以 [url] http://xmlbench.sourceforge.net/ [/url] 作为测试框架。

测试环境是在 vmware 上，并且机器性能不好，只能测试 4k 和 256k 的样本。

由于 spxml 没有 sax 接口，而 expat 只有 sax 接口，所以无法直接进行对比，只能借助 Sablot ，双方对 dom 进行测试。

采用的版本：expat-2.0.0  + Sablot-1.0.3

--->Running <expat-sablotron-dom> benchmarks:
-> xmlgen 4 KB
Initialisation time 0.106 + 0.613(6.48%) ms, Parsing Time 1.620(2.45%) ms
-> xmlgen 256 KB
Initialisation time 0.137 + 1.121(114.60%) ms, Parsing Time 126.102(1.02%) ms

--->Running <spxml-dom> benchmarks:
-> xmlgen 4 KB
Initialisation time 0.022 + 0.433(19.64%) ms, Parsing Time 2.534(3.36%) ms
-> xmlgen 256 KB
Initialisation time 0.033 + 0.000(0.00%) ms, Parsing Time 3449.899(0.08%) ms

在 256k 的时候，spxml 实在太糟糕了。初步猜想是因为 spxml 是基于 pull 接口来构造 dom 的，pull 接口返回的是一个 event object， 然后在 event object 的基础上，再封装了一个 node object。 而 expat + sablot 直接通过 sax 接口构造 dom，少了一次的 object 构造。

做了这些测试之后，重新 review 了一下 spxml 的代码，希望可以通过一些简单的改动，减少 object 的构造。之后对 StartTagReader 和 DomParser 做了一些改动，然后重新测试。

--->Running <spxml-dom> benchmarks:
-> xmlgen 4 KB
Initialisation time 0.002 + 0.388(16.89%) ms, Parsing Time 1.601(4.09%) ms
-> xmlgen 256 KB
Initialisation time 0.002 + 5.474(30.01%) ms, Parsing Time 164.281(1.00%) ms

看来这次的改动还是比较成功的，大幅缩短了运行时间。

详细考察改进的细节，发现最耗时间的地方是在 ArrayList 的操作上。
这个 ArrayList 是仿照 java.util.ArrayList 实现的一个列表。
之所以需要 ArrayList 操作，是在 PULL parser 的实现中，遇到一个两难的选择：
pull parser 要支持面向流的功能，有一个 append 方法；
pull parser 对外提供的主要方法是 getNext 方法，用来获得当前已经生成的 xml event。

问题在于：
1.在 append 方法中做实际的 xml 解释，把解释得到的 xml event 保存到一个 ArrayList 中，getNext 方法只是从 ArrayList 中取的 xml event；
2.在 append 中只是把字符流保存起来，在 getNext 中才进行解释。

目前的实现是采用方法一。原因是方法二导致额外的内存复制操作。
目前改进了 ArrayList 的操作，所以在性能上有很大的提高。

学习~