Vincent Chan 的巴士站 🚉

使用 OCaml 解析 JavaScript

起因

最近在写一个关于 JavaScript 的静态分析器,作为我的毕业设计。我写静态分析主要是为了 ES6 层面的语法做更好的 DCE(Dead Code Elimination)。我选择 OCaml 来实现这个静态分析工具,用 flow 来 parse JavaScript。

为什么选择 OCaml

在和导师讨论题目的时候,我跟导师说这个项目用 Java 来写,主要是 Java 比较容易说服老师。实际上开始写的时候就塞了很多私货,我的第一个版本其实用的是 Scala,原因是:

  • Scala 里面的很多语言特性非常有 FP 风格,也很适合用来写编译器和静态分析工具。
  • 运行在 JVM 上面更容易做多线程,可以使静态分析过程有较大的提升。
  • 如果有需要,Scala 可以编译成 JS。JVM 上面也有很多可以和 JS 联动的方案,方便和其他 JS library 联动。

但是开始使用 Scala 的时候却发现了许多问题:

  • 我使用的 Parser 和 AST 结构都是 Java 写的(使用了 Graal.js 的 Parser),因此无法使用 Scala 的 case class 风格,这意味着我要在 Scala 里面写 Java Style 的代码,我表示很拒绝。我当然可以用 implicit 语法写一层转换层,但是我觉得这样很蛋疼,所以放弃。
  • 我要进行的静态分析是基于图(Graph)的,似乎没办法进行并行计算,即使可以,也会有超级多 overhead,还不如使用单线程。
  • 巨慢的编译速度和启动时间。编译速度不说了。运行速度 Scala 应该是很快的,但是启动(预热)却很慢。

种种蛋疼的情况让我重新审视用 Scala 是不是特别好的方案,我想要一门执行速度相对较快,语法对写编译器相对友好的语言。Scala 已经很接近了,但是还不够。这让我想起之前用过 OCaml 来写过编译器,感觉代数形式的数据结构天生对编译器和静态分析非常友好。而且有两个项目非常启发到我:

  • Flow:静态分析工具,但是已经演化到类似 TypeScript 那样,变成一门语言了。我个人用过 flow,但是感觉非常慢,比 TypeScript 慢很多,但是我觉得不是 OCaml 慢,而是 flow 本身设计的问题。设计 TypeScript 的 Anders Hejlsberg 毕竟是编译器领域的大牛,很多坑都踩过,像 TypeScript 和 VSCode 联动体验这么好肯定是经过优良设计的。
  • BuckleScript:把 OCaml 编译到 JS 的编译器(其实也算一门语言?)。作者号称编译速度最快的语言,编译速度比 TypeScript 还快,并附上了 benchmark。这点也可以理解。毕竟 OCaml 这门语言比 TypeScript 简单太多了。这让我看到了一线生机,OCaml 写出来的编译器也可以很快的啊。

优点:

  • ADT
  • 冷启动速度却可以秒杀 Scala。想象一下编译几个文件的项目,Scala 还要等 JVM 预热才能达到峰值,其实很蛋疼。
  • 编译速度很快(相比 Scala)

缺点:

  • 现在 OCaml 依然没有办法实现真正意义上的多线程:有 GIL。而我觉得这不是痛点,而且 multi-core OCaml 准备推出了(2020 年?)。
  • 如果需要和 JS 联动,需要编译成 JS

使用 Flow Parser

Github: https://github.com/facebook/flow

Flow 是利器。

自己从头开始写 ES 的 Parser 是不太现实的。很幸运 flow 就提供了这么一个工具。Flow 的代码结构还是蛮清晰,我一看项目目录基本了解各个模块的作用,而 parser 是作为独立的一部分:Flow Parser

AST 定义:https://github.com/facebook/flow/blob/master/src/parser/flow_ast.ml

Flow 的 AST 都写在一个文件里面,我们看 program 的定义:

type ('M, 'T) program = 'M * ('M, 'T) Statement.t list * 'M Comment.t list [@@deriving show]

一个 program 就是 list of Statment.t。有两个泛型参数 'M'T 充斥着整个 AST,虽然它的作用很巧妙,但是却并不是那么直观。实际上 parser 输出的结果中,'M'T 都是 Loc.t,就是 AST 的位置信息,那么为什么需要两个范型呢?我们只要看 StatementExpression 两个地方的定义就明白了:

Statement

  and ('M, 'T) t = 'M * ('M, 'T) t'
  and ('M, 'T) t' =
    | Block of ('M, 'T) Block.t
    | Break of 'M Break.t
    | ClassDeclaration of ('M, 'T) Class.t
    | Continue of 'M Continue.t
    | Debugger
    | DeclareClass of ('M, 'T) DeclareClass.t
    | DeclareExportDeclaration of ('M, 'T) DeclareExportDeclaration.t
    | DeclareFunction of ('M, 'T) DeclareFunction.t
    | DeclareInterface of ('M, 'T) Interface.t
    | DeclareModule of ('M, 'T) DeclareModule.t
    | DeclareModuleExports of ('M, 'T) Type.annotation
    | DeclareTypeAlias of ('M, 'T) TypeAlias.t
    | DeclareOpaqueType of ('M, 'T) OpaqueType.t
    | DeclareVariable of ('M, 'T) DeclareVariable.t
    | DoWhile of ('M, 'T) DoWhile.t
    | Empty
    | ExportDefaultDeclaration of ('M, 'T) ExportDefaultDeclaration.t
    | ExportNamedDeclaration of ('M, 'T) ExportNamedDeclaration.t
    | Expression of ('M, 'T) Expression.t
    | For of ('M, 'T) For.t
    | ForIn of ('M, 'T) ForIn.t
    | ForOf of ('M, 'T) ForOf.t
    | FunctionDeclaration of ('M, 'T) Function.t
    | If of ('M, 'T) If.t
    | ImportDeclaration of ('M, 'T) ImportDeclaration.t
    | InterfaceDeclaration of ('M, 'T) Interface.t
    | Labeled of ('M, 'T) Labeled.t
    | Return of ('M, 'T) Return.t
    | Switch of ('M, 'T) Switch.t
    | Throw of ('M, 'T) Throw.t
    | Try of ('M, 'T) Try.t
    | TypeAlias of ('M, 'T) TypeAlias.t
    | OpaqueType of ('M, 'T) OpaqueType.t
    | VariableDeclaration of ('M, 'T) VariableDeclaration.t
    | While of ('M, 'T) While.t
    | With of ('M, 'T) With.t

Expression

  type ('M, 'T) t = 'T * ('M, 'T) t'
  and ('M, 'T) t' =
    | Array of ('M, 'T) Array.t
    | ArrowFunction of ('M, 'T) Function.t
    | Assignment of ('M, 'T) Assignment.t
    | Binary of ('M, 'T) Binary.t
    | Call of ('M, 'T) Call.t
    | Class of ('M, 'T) Class.t
    | Comprehension of ('M, 'T) Comprehension.t
    | Conditional of ('M, 'T) Conditional.t
    | Function of ('M, 'T) Function.t
    | Generator of ('M, 'T) Generator.t
    | Identifier of 'T Identifier.t
    | Import of ('M, 'T) t
    | JSXElement of ('M, 'T) JSX.element
    | JSXFragment of ('M, 'T) JSX.fragment
    | Literal of Literal.t
    | Logical of ('M, 'T) Logical.t
    | Member of ('M, 'T) Member.t
    | MetaProperty of 'M MetaProperty.t
    | New of ('M, 'T) New.t
    | Object of ('M, 'T) Object.t
    | OptionalCall of ('M, 'T) OptionalCall.t
    | OptionalMember of ('M, 'T) OptionalMember.t
    | Sequence of ('M, 'T) Sequence.t
    | Super
    | TaggedTemplate of ('M, 'T) TaggedTemplate.t
    | TemplateLiteral of ('M, 'T) TemplateLiteral.t
    | This
    | TypeCast of ('M, 'T) TypeCast.t
    | Unary of ('M, 'T) Unary.t
    | Update of ('M, 'T) Update.t
    | Yield of ('M, 'T) Yield.t

上述代码就是在说,所有的 Expression 结点都会附上一个 'T 信息,所有的 Statement 都会附上一个 'M 信息,这就很容易理解了。所以这两个范型是用来区分 Statement 和 Expression 的。在 flow 里面进行 type infer 和 type check 的时候,实际上 'T 会是 (Loc.t * Type.t)。这个是 type check 阶段附上的信息,而 Statement 不需要这个信息,所以它仍然是 Loc.t。举个类型推导例子 🌰 来说明 'T 附在表达式上的作用:

var a = 1 + 1;

var a = ((1: 'T) + (1: 'T)): 'T
var a = ((1: number) + (1: number)): 'T
var a = ((1: number) + (1: number)): number
var a: number = ((1: number) + (1: number)): number

从上述过程可以推出 a 的类型是 number,这个类型信息挂在所有 expression 的 AST 的上面,而 var 语句的 node 不需要这个信息。

安装 Flow Parser

原本 flow_parser 可以从 opam 安装,但是我更新了 opam 之后似乎因为一些安全策略禁止包里面的 bash 脚本执行(当时社区发生了一件事,一个包的 bash 脚本把用户的整个 ~ 目录删掉,似乎是手滑写的脚本就发布了,后来 opam 对 bash 脚本做了些限制)。所以后来我只能 clone 了 flow 的代码本地进行安装

进入 src/parser 目录执行:

$ make ocamlfind-install

即可安装成功。如果使用 ocamlbuild 编译,进入 _tag 文件,加上 flowparser。我的 `tag`:

true: package(ppx_deriving.show), package(flow_parser), package(core_kernel)
<dist>: -traverse

使用方法

使用 Flow_ast 自带的 ppshow 方法可以把 AST 打印出来,前提是你要传入 'T'M 的 pretty print 方法, 这里我把 Loc.pp 传进去即可:

let ast, _ = Parser_flow.program code in
Flow_ast.show_program Loc.pp Loc.pp ast |> print_endline;

大功告成!

相关阅读