无需中间抽象语法树解析JSON对象

# 无需中间AST的JSON对象解析 来源：https://arthi-chaud.github.io/posts/json-ir/ 让我们聊聊JSON。JSON无处不在。几乎没有编程语言缺少将数据序列化为JSON和解析JSON数据的库。 许多库通过中间表示（IR，通常是JSON对象的抽象语法树AST）来实现这一功能。若我们对性能有所要求，这就可能成为问题：依赖IR意味着额外的内存分配和计算，会拖慢整个流程... 本文将展示一种通过使用*部分初始化数据*来解析JSON对象的方法，无需借助中间表示。 我将使用Haskell来演示，但该方案应能在支持代数数据类型（ADT）和分阶段元编程的语言（如Rust）中实现。 ## 解析JSON数据：朴素方式 https://arthi-chaud.github.io/posts/json-ir/#parsing-json-data-the-naive-way 首先，让我们看看"朴素"JSON解析器的大致形态。我们先定义JSON的AST类型： ```haskell import Data.Text (Text) import Data.Map (Map) data JSON = Number Number | Bool Bool | List [JSON] | Null Null | String String | Object Object newtype String = String Text data Number = ... data Null = Null newtype Object = Object (Map Text JSON) ``` 然后，借助解析器组合子库，我们可以编写解析器： ```haskell parseNumber :: Parser Number parseBool :: Parser Bool parseNull :: Parser Null parseString :: Parser String parseObject :: Parser Object parseList :: Parser [JSON] parseJSON :: Parser JSON parseJSON = (Number <$> parseNumber) <|> (Bool <$> parseBool) <|> (Null <$> parseNull) ... ``` 最后，对于每个我们希望从JSON值解析的数据类型，我们定义一个函数，使用`JSON`值来构建该数据： ```haskell data Album = Album { title :: T.Text , artistName :: Maybe T.Text , songCount :: Int } fromJSON :: JSON -> Maybe Album fromJSON = \case Object obj -> do title <- obj !? "title" artistName <- obj !? "artist_name" songCount <- obj !? "song_count" return Album{..} _ -> Nothing ``` 幸好，像`fromJSON`这样的函数可以通过Template Haskell或泛型自动推导（分别参见[deriveFromJSON](https://hackage-content.haskell.org/package/aeson/docs/Data-Aeson-TH.html#v:deriveFromJSON)和[genericToJSON](https://hackage-content.haskell.org/package/aeson/docs/Data-Aeson.html#v:genericToJSON)）。 退一步看，数据反序列化过程可以概括为： ``` flowchart LR A[ByteString] --parseJSON-->B[JSON AST] B --fromJSON--> C[领域数据] ``` 第二步简化了开发者的工作：通过将解析步骤与向领域数据（此处为`Album`）的值转换分离，我们得到了更易维护的代码。 ## 能否从反序列化过程中移除这个JSON AST？ https://arthi-chaud.github.io/posts/json-ir/#can-we-remove-this-json-ast-from-the-deserialisation-process 如我在引言中所说，依赖JSON AST（充当IR）意味着在内存中分配一个额外的对象（该AST的大小*至少*与最终对象一样大），以及额外的计算（将此AST转换为`Album`时）。 因此我向自己提出这些问题： - 能否移除此IR？ - 加速效果会明显/显著吗？ - 我们还能自动/以编程方式推导代码吗？ - 安全性如何？ 在数据反序列化上下文中，*安全性*指能够从错误中恢复。此类错误可能包括： - 序列化对象中缺少一个（非空）字段 - 序列化对象中字段的类型与数据类型定义中的类型不匹配 此外，解析器应能跳过*未知*字段（即存在于序列化对象中，但在数据类型定义中缺失的字段）。 因此最终的问题是：没有IR，我们还能安全地解析数据吗？ ## 解决方案：部分初始化的对象与显式字段计数器 https://arthi-chaud.github.io/posts/json-ir/#solution-partially-initalised-objects-and-explicit-field-counter 如果我们传入一个部分初始化的对象（领域数据），并让解析函数在过程中设置其字段，会怎样？ ```haskell parseAlbum :: PartiallyInitalisedAlbum -> Parser PartiallyInitalisedAlbum ``` 在Haskell中，有几种方式表示部分初始化的值。例如，我们可以推导一个`PartialAlbum`数据类型，其中所有字段都包裹在`Maybe`中，或者使用一个带类型参数的数据类型来表示哪些字段存在或缺失。无论哪种方式，都需要编写类似`PartialAlbum -> Maybe Album`的函数。问题在于`PartialAlbum`本身就是一种IR，所以我们想避免它。 相反，我们将利用语言的惰性求值，并将所有对象字段设置为`undefined`，至少是没有"默认值"的那些字段。我知道，这听起来很可怕且极其不安全。但我相信这种方法能帮助编译器进行优化。 ```haskell album = Album undefined undefined undefined -- 或者这样，但编译器会报警 album = Album{} ``` 需要注意的是，由于这种方法，领域数据类型的字段不能是严格求值的！ 这引出了下一个问题：如何在解析函数终止后，检查所有字段是否都已被设置？ 求值`undefined`会引发错误，导致程序崩溃，因此我们显然不能这样做。 相反，我们可以传递一个位集（例如`Word64`），初始值设为`maxBound`，在设置一个字段后更新它，即清除位置`n`的位，其中`n`是字段在数据类型定义中的位置。 这样，一旦解析器终止，我们只需检查该位集是否等于0，即可判断对象是否已完全初始化。 ```haskell parseAlbum :: Parser Album parseAlbum = case runParser (go Album{} maxBound) of (a, 0) -> return a (_, bits) -> fail ... where go :: Album -> BitSet -> Parser (Album, BitSet) ``` 在`fail`分支中，我们可以检查`bits`中的每一位，并构建一个列出缺失字段的错误消息。如果所有剩余置位的位对应于类型包裹在`Maybe`中的字段，我们可以将这些字段设为`Nothing`并返回成功。 `go`函数可以这样实现： ```haskell import Data.Bits (clearBit) go :: Album -> BitSet -> Parser (Album, BitSet) go album bitset = do char '{' res <- manyWithSep (char ',') go' (album, bitset) char '}' return res -- | 运行 go'' 直到对象结束 manyWithSep :: Parser () -> (a -> Parser a) -> a -> Parser a manyWithSep sep parser state = do res <- parser state either (pure res) (manyWithSep sep parser res) (try sep) go'' :: Album -> BitSet -> Parser (Album, BitSet) go'' album bitset = do fieldName <- parseString char ':' case fieldName of "title" -> do title <- parseString return (album{title=title}, (bitset `clearBit` 0)) "artist_name" -> do artistName <- parseString return (album{artistName=artistName}, (bitset `clearBit` 1)) "song_count" -> do songCount <- parseInt return (album{songCount=songCount}, (bitset `clearBit` 2)) ``` 很容易观察到，`go''`中模式匹配表达式的结构可以从源数据类型推导出来，例如使用Template Haskell。 当然，还有几件事需要考虑，比如字节字符串中的空白处理、字段为`Maybe`时的错误恢复等。此代码片段为简洁起见刻意省略了这些内容。 ## 实现 https://arthi-chaud.github.io/posts/json-ir/#implementation 我使用`flatparse`库实现了这种方法，并依赖Template Haskell在编译时生成专门的解析器。 源代码可在[GitHub](https://github.com/Arthi-chaud/serth/tree/main/serth-json-parser)上找到。该库依赖于同一仓库中的另一个包，该包抽象了通过名称获取ADT信息的方式。这与本文关系不大，因此我不在此详述。 我应该指出，标量值的解析器并非100%兼容：字符串中转义字符的处理不完整，并且仅支持数字格式的子集。不过，由于这只是一个概念验证，我认为这是可接受的，足以进行评估。 ## 基准测试 https://arthi-chaud.github.io/posts/json-ir/#benchmarks 为了评估这种方法，我使用[Criterion](https://hackage.haskell.org/package/criterion)运行了几个基准测试案例。[^2] [^2]: 使用硬件：Intel机器，2块 Xeon Gold 6244 CPU @ 3.60 GHz，32GB RAM，Ubuntu 22.04 LTS 基准测试的代码及完整结果同样在[GitHub](https://github.com/Arthi-chaud/serth/blob/main/serth-json-parser/benchmark/Main.hs)上。 我将重点放在解析对象（大小与`Album`类似）的基准测试案例上。请记住，这些是微基准测试，可能无法反映真实应用中的性能。 我针对使用以下库的代码运行了基准测试： - `aeson` (https://hackage.haskell.org/package/aeson)，Haskell的*标准*JSON库，使用IR。 - 本库，无IR - 本库，但先将对象解析为通用`JSON`对象，然后使用手写的`fromJSON`函数。 采用后者是为了帮助隔离IR的成本。我们的JSON解析器与`aeson`的非常不同：我们的可能更慢，但`aeson`支持定制选项[^3]，这可能影响运行时性能。目前，该库不支持此类选项。 | 库/对象 | Book | Author（含书籍列表） | | :--- | :--- | :--- | | Aeson（带IR） | 1.051 μs | 2.901 μs | | 本库（带IR） | 922.7 ns | 2.813 μs | | 本库（无IR） | 314.2 ns | 1.027 μs | [^3]: https://arthi-chaud.github.io/posts/json-ir/#fn:3 使用IR与不使用IR的代码性能差异相当显著。使用IR时，解析速度大约慢3倍。这证实了IR确实对性能有影响。 ## 结论 https://arthi-chaud.github.io/posts/json-ir/#conclusion 当然，我们的实现并不完美，缺少真实世界解析器的一些功能，这可能会影响性能，最突出的是定制选项。这些选项允许定义缺失字段的行为、对象字段的大小写处理、ADT的处理等。 本文的目的并非指责像`aeson`这样依赖IR的库。IR*确实*有用，能够将解析过程与验证步骤解耦。我们的方法将两者合并，使代码更复杂、更难维护，但显著更快。 相反，我想强调IR在运行时的成本及其对性能的影响，并展示一个（可能不够优雅）的避免IR的解决方案。 IR对性能的影响并非新知。Rust的序列化框架`serde`利用分阶段编程将IR提升至编译时。