设计了一个数据格式
最近一段时间在忙着设计和实现我们游戏引擎用到的数据格式。
在此之前，我们一直在直接使用 lua 描述数据；但最近随着数据类型系统的完善，同事建议设计一种专有数据格式会更好。希望专用格式手写和阅读起来能比 lua 方便，对 diff 更友好，还能更贴近我们的类型系统，同时解析也能更高效一些。lua 的解析器虽然已经效率很高，但是在描述复杂数据结构时，它其实是先生成的构造数据结构的字节码，然后再通常虚拟机运行字节码才构造出最终的数据结构。这样的两步工作会比一趟扫描解析构造要慢一些且消耗更多的内存。
现有的流行数据格式都有一些我们不太喜欢的缺点：
json 是目前最流行的，但是它更适合通讯协议，数据由程序生成。对手写和阅读不是很友好：json 不支持注释；字典结构中 key 需要给字符串加引号，显得累赘。支持的数据类型有限，不易扩展数据类型。另外，标准 json 无法对浮点数做精确表达。
xml 是另一种通用选择。它比 json 更严谨，在扩展数据类型方面很方便。但 json 有的缺点它更盛：在手写的时候，往往一个很简单的值，需要额外写很多格式要求的信息，不借助专有编辑器时，书写不太方便。阅读起来有效信息比很低，需要借助专有查看器才能变得方便。冗余信息太多导致对 diff 也不算太友好。
ini 格式在 windows 上很流行，在 windows 之外也有很多人用。但是它做配置文件很舒服，描述复杂数据结构的话却有点力不从心。ini 只是在键值对的数据组加了一个层次，如果要描述多层结构，就很难沿用一致的语法。
lisp 是我所青睐的。Paradox 的数据格式就是采用的类 lisp 结构 。据说顽皮狗的引擎也使用了 lisp 做内部数据结构。不过同事不太喜欢太多的括号，我也觉得这点值得改进。
yaml 看起来是最符合易于书写和阅读的格式。但它的解析器过于复杂，虽然格式设计上是为了方便一趟扫描解析，但现在依然没有一个特别高效的实现。我曾经跟踪过很长时间 libyaml 这个项目，贡献过 bugfix ，提过建议 。其中一个建议被开发团队持续讨论了一年多。因为要考虑多语言实现的 yaml 的一致性，所有细节都必须被反复推敲。不能产生方言：否则在一种语言环境上编码的数据，去到另一个环境就无法正常解析，这就失去了数据交换格式的意义。考虑到 yaml 相当复杂的格式定义，和诸多的实现版本，这太难了。后面我还会提到一些小的特殊需求，实际上扩展 yaml 是不实际的（很难被接纳），还不如干脆自己设计一套不是 yaml 的新格式，这也是最近这些工作的动机。
设计并实现一个专有数据文件格式，在提出要做这么一件事之前，我觉得我们的项目并不需要多复杂的东西。保留一定的通用性的前提下，设计的足够简单，满足我们的需求就好了。已有的数据格式不喜欢，那么改成我们喜欢的样子，我觉得有一个下午就能搞定。
在那个冬日的周末，中午的太阳晒得人懒洋洋的。我乘娃打了个哈欠，赶紧把他哄睡着。打开编辑器，想着儿子醒来前这几个小时差不多够用了。
事实上并没有这么简单。
第一版我对 Paradox 的数据格式做了一个简单的模仿。曾考虑过用 lua / lpeg 来实现，但又感觉未来可能需要更高的性能，且格式不复杂，用 C 实现也可以很清晰，不必列出 BNF ，不需要用 yacc 。手写一个解析器不过几小时的工作。实现的时候，我还顺手加上了一点我觉得方便的特性：在解析到 lua 中时，可以通过使用 [] 或 {} 来选择把字典解析成列表还是字典。整个解析器不过几百行 C 代码，一趟扫描就可以完成，并生成 lua 的数据结构。
周一拿给同事看的时候，并不满意。从原来 lua 数据文件中转过来的数据文本中太多的括号看起来并没有比原来 lua 版本好看多少。尤其是在序列化内存的大量 Entity 时，最外层结构需要一个数据列表，感觉 ini 风格的 section 分段会漂亮很多。
ini 风格的 section 是用 [name] 这样的形式来区分段落的。因为缺少括号，必须依赖下一个段落的开始来结束上一个段落。这样，就很难表达多级层次。我考虑借鉴 markdown 的方法，用 ### title 来表示段落。井号的数量可区分不同层。同时，还是想保留括号作为可选项。因为在描述一个向量的时候，我更希望沿用 { 0,0,0,1 } 这样的风格。
没有结束符的区段结构，解析器写起来要麻烦许多。更重要的是要防止人误用产生有歧义的结构文本。我决定让段落标识只能出现在最外层，一旦使用 {} 表示内部层次，内部层次中就不可以再出现段落符号。
做这个新特性时，我发现之前快速写出来的词法解析及语法解析模块很按新需求扩展。我意识到未来很可能还会做大改变，干脆就推倒重写，这次不图快，尽可能的写清晰，用更直白（但更啰嗦）的实现。
完成之后，我们查看了生成的数据，发现虽然语法上可以表达出层次，但是没有缩进的多层结构实在惨不忍睹。或许是程序员早已习惯了视觉空间上的变化来表达层次结构吧，光有标签是不够的。最后还是为生成的数据加上了缩进。而解释器会简单的将缩进当成分隔符忽略掉。
可是既然有了缩进表示层次，我们何必再用蹩脚的段落表示方法呢。
再一次的大改就是去掉新加的特性，转而用缩进来表示层次。当然，{} 的层次表示方法还是保留的。同样不能混杂使用，只能从外层开始使用缩进，一旦开始用 {} 后，缩进就变成了简单的分割符。
这里我们不想规定缩进到底是 tab 还是空格，是 2 个还是 4 个或 8 个。我对 yaml 略有怨言的地方就是它不能用 tab 缩进，这不符合我的编辑习惯。本质上，缩进就是把层次信息加在每行元素上，从而可以省略层次结构结束的标记。我们只需要认为同样的缩进串表示的是同级的层次，不同的缩进串将关闭前一个层次。理论上，你想把外层向内部从长到短反着排版都没关系，只要保证同层的行的缩进串是相同的就够了。
但我并不想给这种灵活性，允许排版成奇怪的样子没什么好处。最终我还是规定更深的层次必须有更长的缩进串，但不规定每个新层次需要累加固定的长度。比如第二层可以用两个空格，第三层加到 6 个或者家一个 tab 也是没关系的。
另外，我增加了 yaml 里用 --- 表示区段的方法。这可以减少最外层的缩进。这是一个喜闻乐见的特性，在很多数据文件格式中都可以看到类似的东西。比如 record-jar 就用 %% 来表示分段。
主体功能完成后，整个结构看起来就像一个简化版的 yaml 。最直接的改进就是可以比标准 yaml 解析要高效的多。如果做配置文件，效率不会是问题，但我们的游戏引擎打算把它做成通用数据格式，效率高一点可以缩短日后的管卡数据加载时间。
接下来就是加一些 yaml 中没有，或是难以实现，但我们又需要的特性了。
其一就是 anchor 的向后引用。yaml 可以用 &anchor 的方式对一组数据做一个锚点，然后之后用 *anchor 对之前的结构进行引用。这是一个很有用的特性，在别的格式中很难做到。我们在序列化场景树时就用的上：*anchor 相当于一个指针，可以指向另一个数据结构。这可以避免直接序列化整棵树导致的缩进层次过大。且能解决 DAG （有向无环图）的序列化问题：多个孩子引用了同一个子节点。
但是 yaml 为了解析器实现方便（保证可以一次扫描解析完毕），它规定，对锚点只能做向前引用，即必须先声明锚点，才可以对其引用。锚点可以重复，总是引用最近的一个。
这导致有环的图无法被描述出来。我想去掉这个限制。在 Lua 中，所有复杂数据结构都是用 table 统一承载的，而我们几乎只在 Lua 中使用这个数据结构，这就可以用一种技巧来解决向后引用的问题：我们只需要在解析的时候碰到未定义的锚点时，提前把一个空 table 出来，等到锚点被定义时，再去填充这个 table 即可。
btw, Unity 就是使用 yaml 做数据描述，但并只是部分使用了锚点的机制。它定义了锚点，却没有用 yaml 的语法去引用它们。
另一个想改进的地方是自定义数据类型。yaml 是用自定义 tag 来实现的。通常解析器会提供 event 机制来触发自定义 tag ，动态语言封装解析库的时，接管这个事件来处理自定义数据。不过现有的实现做起来还是太麻烦且低效。
既然我们是专有格式，且只给 Lua 使用，就可以用一种取巧的方法来实现一个简化版本。
我的做法是，允许用户用 [] 取代 {} 来描述一个数据结构。但一旦采用 [] ，解析器在解析完毕后，回调一个用户函数，把数据过滤一次。对于 [ 0, 0, 0 ,1 ] 这样的向量，我们就可以简单的做一次后处理，加工成 lua userdata 返回出去。还可以对外部文件引用写成 [ file path ] 的形式，这是一个列表，第一个字段 file 表示这个自定义结构的类型，后面的是参数。Unity 在类似问题上处理要复杂一些，它对外部文件引用生成了一个类似 {fileID: 400000, guid: 5df3a2b3f00ce8a418ad24d290ed5deb, type: 3} 的数据结构，我猜测这依赖更高层模块的解析，而无法在读取 yaml 的时候同步完成。
这个项目的 github 仓库在这里 。原本以为一个下午就可以搞定，可目前距离第一次提交已经三周了。
等稳定后，我会将这个仓库合并入引擎的主干。
