为什么重复写脚本？

最近在参与的一个 TypeScript 项目上出现了一个功能，即通过读取 xml 文件的属性信息来检查特定的动作是否执行完成。当然作为一名合格的模块战士，最好的方式就是用第三方库来解析 xml 文件，但作为一个折腾玩家，自己实现的功能才更加具有可控性。

json 相较于 xml 更加通用和方便，虽然 npm 上已经有 sax 这个开源库提供现成的 xml 解析方案了，但这些方案由于需要兼容很多“阴间” xml 样例，不得已会存在很多匹配上的的冗余代码。因此，考虑到项目中的 xml 并不存在特殊格式，所以可以简化很多步骤，在执行速度以及体积大小上会存在一定的优势。

方案简要

这一次的算法实现，我并没有过多地考虑性能优化——这并不只是因为我偷懒——主要还是先实现一个可用的 Demo 为主。xml 的内容解析类似于文本分析，所以在实现时很自然地就往递归遍历想了，简单粗暴，效果拔群。具体思路就是正确找出标签的开头位置和结尾位置进行解析，然后中间的内容递归到下一层进行匹配解析。

从这个角度出发，要解决的问题就分为了三个：标签文本拆分，json 对象构建，内容解析。

标签文本拆分

xml 始终以 <> 为标签进行内容分割，夹着子文本和子标签。所以如果要正确进行后续的匹配，只需要按照 <> 标记进行内容上的分割即可，然后将生成的字符串列表交给下一层进行处理。最终的实现效果是这样的：

源文本：
  "   </param>   Hello World!<a>test</a>Cest la vie   </param>"    // 使用 .trim() 去除两边多余的空格回车
目标字符串列表：
  [
    "</param>",
    "Hello World!",
    "<a>",
    "test",
    "</a>",
    "Cest la vie",
    "</param>"
  ]

这样便可以方便得按照标签为单位进行处理了，这一部分在实现上没有考虑太多，直接新开辟了一个容器（再次偷懒），然后双指针遍历一遍匹配 <> 存入内存即可。后续再根据该列表的内容以及对应的规则进行 json 对象构建和参数匹配。

json 对象构建

内容解析部分需要根据 xml 的文本内容来构建 json 结构。首先是捣鼓这个结构到底长啥样，不仅需要具有通用性，而且不能够丢失原文本的信息（能够反向还原回去）。

首先是确定类型，根据解析功能的需求，内容类型一共分为三种，一种是纯文本内容，一种是标签，一种是注释（未完成）。内容的类型则使用 nodeType 参数进行标记，不同的内容有着不同的对象属性；然后是确定结构，不同的内容类型对应的不同的对象结构，解析 json 的时候直接通过 nodeType 识别后使用对应的方法解析子内容即可。

在确定了具体结构之后，就开始往框架上填内容了。这里我最早想使用的方法是使用一个指针去遍历内容，然后用另一个变量存储当前的状态（在第几层，标签信息），最后根据当前状态去生成对应结构里面的信息，复杂度为 O(n)。在 TypeScript 中，我使用了稍微简单的解法来实现，即用数字作为栈标志，外加双指针递归遍历，该方法抛去递归栈开销也比较接近 O(n) 了，实测效果也挺不错。

内容解析

由于前面标签文本拆分部分已经做了处理，所以在这儿可直接通过前缀来对解析流程进行区分。带 </ 的为闭合标签，转入递归子流程；带 < 的即为开始标签，转入标签内容匹配流程；不带 < 的即为文本内容，转入文本内容处理流程。但转入流程不能仅仅依靠前缀进行判断，正所谓“门当户对”，</ 对应的有可能是另一个开始标签。所以还需要一个 stack 作为层级的 token，遇到开始标签则 stack++， 遇到闭合标签则 stack--；只有当 stack = 0 时 </ 为正确匹配，此时才可进入递归。

此外还有个单标签的情况，本实现直接额外进行了 if 判断匹配末尾的 />。这里由于是在完成整体算法后才实现的，所以写的比较丑，额外增加了匹配的时间。

正确匹配结构之后，最终要根据标签内的文本内容匹配出标签参数。这里大量使用了正则表达式来提取，同时也测试了大量的字符串匹配去保证这一块匹配的正确性，最终效果也挺不错。

问题和部分优化

当然，这个方案从设计之初就存在了设计问题。

首先是这种分割再分析的方式，注定了与大型 xml 数据无缘。大文件测试中，40MB 需要 600+ms 到 1+s（复杂结构），110+MB 下当场报废，nodejs 的进程直接卡住没反应。如果使用字符串流 + 缓存状态信息的方式的话，大文件读取和解析上会好使很多，但由于时间问题我就没有继续进行效率改进。

这波啊，这波是汪汪队丢大脸。

第二，这个方案扩展性不够，如果要匹配额外的一些情况（注释，或者其他奇奇怪怪的标签），就必须要重写部分代码。这一块我做了结构上的优化，可以通过叠 if 的方式去匹配额外的情况。这个优化虽然不能说是毫无裨益吧，但至少也是一无是处了。

第三，本实现虽然鲁棒性高，能够忽略掉绝大部分的格式问题，但残缺的结构是没有办法正常解析的。后来我又返回看了 sax 的源码，好像它也是遇到困难睡大觉，直接在 README 上写了 It does a little validation when in strict mode, but not much。

从匹配算法上考虑，主要的耗时点就是各种情况的 if 匹配上，30MB 体量的 xml 文件解析中，每减少一个 if 的匹配可以减少近 100ms 的时间。一般来说 xml 文件前面会有 <?xml> 和 <!DOCTYPE> 之类的特殊标签，而这在后面的匹配中是完全不会再碰见的。所以在完成了整体的实现后，我又把这一部分的匹配规则给抽离出来单独匹配，尽量去减少额外的条件判断。

我不太了解 nodejs 的解释器优化，在 Python 中进行字符串切片会额外新生成一个字符串对象，相比于双指针会更加耗时。TS 中我直接使用了 .slice() 进行切片，可能相应的效率也会差一些。

最后，其实源码也是比较丑的，有着明显的赶工痕迹，结构上也不够完善。同时这是我第一次用 TypeScript 来丢人完整实现一个功能，所以有些小马拉大车，遇上了很多坑。

源码

由于一些小问题，暂时不作公开。