0x00 前言
最近一直在做和 JS 语法分析、代码重构等有关的一些项目, 但是由于种种原因不能公开发布.
这些东西一直在私有库里吃灰也不太好, 就在博客稍微聊一下其中涉及到的 JavaScript 通过 AST 静态分析变量绑定的思路吧.
本文使用的语言是 PHP, AST 分析框架是 mck89/peast. 大部分框架生成的 AST 都大同小异, 本文的叙述应该是普遍适用的.
我的水平有限, 不能保证文章的绝对准确. 如文中有错漏请您在评论区留言或通过其他方式联系我更正, 非常感谢您的协助.
0x01 运行规范
查阅 ECMAScript® 2015 Language Specification 第8章和第13.3节可知, JavaScript 在执行的时候将创建一些 Code Execution Contexts, 在同一时间只会有一个 Context 被执行.
同时, 引擎将使用 Lexical Environment (简称为 Environment) 来实现变量的绑定, 即实现从 Identifier 到变量的映射. 每个 Environment 除了记录当前创建的变量外还可能会记录一个 outer environment, 以便寻找作用域更大的变量.
我们可以将 Lexical Environment 划分为下面这几个范围
- global, 即没有 outer environment 的 Environment, 简单的说就是管全局变量的
- module, 顾名思义, 范围比 global 小一些, 只负责当前 Module 里面的变量
- function, 范围更小, 只记录 当前函数中的变量, 函数的参数也会记录在这一 Environment 中
按照规范, 在执行代码时每个 Context 将会关联一个 LexicalEnvironment 和一个 VariableEnvironment, 注意这两个部分虽然名字不同, 但它们的类型都是 Lexical Environment.
其中前者负责记录在 这一 Context中 创建的局部变量 (let 和 const 关键词创建), 而后者用于记录 VariableStatements (var 关键字) 创建的变量.
但是这里讨论的都是运行时的情况. 在静态分析时, 我们要面临的一大难题就是根本没有 Context 和 Environment 之类的东西, 手上有的就是一个 AST, 因此我们得自己实现一个类似 Environment 的机制来帮助变量绑定.
0x02 创建绑定
为了简化实现, 这里我们将不完全按照规范的定义来, 进行下面几点修改
- 根据具体需求, 目前没有分析 Module 的需要, 因此剔除 module 这个类型
- 不需要实现 Context 和 Code Realm, 因为我们不需要真正的去执行代码
- 由于没有 Context, 我们直接使用 Environment 来替代它, 将 Environment 直接关联到代码 (即 AST Node)
- 由于没有实现 Context, 也就没有 LexicalEnvironment 和 VariableEnvironment 之分, 我们需要一些机制来区分 var 和 const/let 关键字定义的变量范围
- 基于上一条原因, 我们再增加一个 block 级别的 Environment 限定于块级变量的储存
- 最后, 我肯定不愿意把每个类型的 Environment 都写一次, 要采用尽可能统一的实现
有了这些修改, 我们就可以开始尝试实现了. 不难发现, Global, Function, Block 三个域应该呈现一个嵌套的关系, 采用下面的方式定义大小可比较的 LexicalEnvironment 类型会为我们实现绑定变量提供一定的便利.
接下来我们需要实现变量的绑定. 扫描 AST 的时候, 常见的扫描方式是从外往内一层一层的扫, 例如, 对于下面的代码:
StatementA;
{
StatementC;
StatementD;
}
StatementB;会生成类似于下图的 AST (画的不太好, 这个工具实在是不好排版)
那么扫描时我们处理的顺序就是 Program->BlockStatement(外面的)->StatementA->BlockStatement(里面那个)->StatementC->StatementD->StatementB
根据这个处理顺序来设计我们的程序, 我们可以考虑创建一个 $currentEnvironment 变量, 初始值为 GlobalEnvironment. 随后对扫描到的每一个 Node 都给它附加上 $currentEnvironment 当前对应的值, 就像下面这样 (打码是为了突出重点, 下面不再重复说明)
接下来我们扫描到每一个 BlockStatement(储存块的 Statement) 和 FunctionExpression/FunctionDeclaration 时都创建适当的 Environment, 并将 $currentEnvironment 设定到这个值, 这样就可以确保我们进行的创建/绑定操作都绑定到了正确的地方.
下图是一个简单的示例, 这里判断了 CatchClause 和 SwitchCase 是因为框架中这两个 Node 较为特别, 这里不深入研究.
如果您熟悉 Peast 生成的 AST, 您可能已经发现这里的逻辑有一些问题, 请先耐心往下看.
我们继续扫描, 当碰到 VariableDeclarator(定义变量的 Node) 就创建一个变量, 那么问题来了, 假如我有如下代码:
function real()
{
var winz = 233;
{
var sanae = 666;
}
}由于 FunctionDeclaration 的 $body (即函数体) 是一个 BlockStatement, 这必然会导致我们的程序创建一个下图的嵌套 Environment:
变量 winz 看似正确注册了, 但它实际上应该被放到外面的 FunctionEnvironment中, 变量 sanae 更不应该被放在这个地方, 因为它们都是用关键词 var 定义的.
还记得我们之前提到这三类 Environment 大小是可以比较的吗? 这就为解决问题提供了可能. 每个 Environment 在创建绑定之前先检查自身的类型值是否足够小, 如果不够小就调用 $outer 中的函数进行创建绑定, 这样一层一层往上传递就可以解决问题.
当然, 我们还需要在碰到 VariableDeclaration 时进行类型的检查, 告诉 Environment 我们到底需要哪个级别的绑定
这样一来, 我们就基本实现了可用的绑定. 但是这里会有一个浪费内存的地方, 您可能已经注意到了, 我们还没有解决 FunctionEnvironment 和 BlockEnvironment 重叠的问题. 当然这很好解决, 我们只要判断上一级 Node 并避免创建新的 Environment 就可以了.
0x03 赋值和引用
每个变量通常会有两种状态, 赋值和引用. 对变量的赋值通常只会由 AssignmentExpression 完成(毕竟 ES6 里不能传递引用参数, 这里说的是改变参数导致传入变量被改变的行为)
处理赋值较为简单, 我们只要在碰到 AssignmentExpression 时绑定即可.
但是对于引用, 简单的方案是碰到 Identifier 时进行处理, 这就涉及一些较为复杂的因素. 根据我们的 AST 扫描模式, 一个 Identifier 可能被放在 FunctionDeclaration->$id, 也可能是 Assignment 左边的运算符, 这会导致我们把奇怪的东西绑定到变量上.
解决这个问题花费了不少时间, 在这个阶段我采用传入一个 $ignoreIdentifier 数组说明哪些 Identifier 已经被处理过, 显然这个实现非常的不优雅并且会造成不可预期的问题(比如漏掉绑定).
此外, 在面对复杂代码的时候这一实现仍然不完美, 对于下面的代码:
function outer()
{
function inner()
{
berd++;
}
var berd = 233;
inner();
console.info(berd);
}在执行时自然是没有问题的, 当我们运行 inner() 时 Context 中已经有了 berd 这个变量, 并且根据规范它实际上在进入 outer 这个Context 时就已经被创建了, 只是还没有被初始化, 也就是某些面试题里经典的 “提升”
但是在我们的分析实现中, 扫描到 inner() 函数时我们的 Environment 中是没有 berd 这个变量的, 所以这一绑定会直接被跳过, 出现漏绑的问题
0x04 两次扫描
为了解决漏绑, 我最后得出的解决方案是扫描两遍. 这可能不是完美的解决方案, 但是已经解决了我踩到的所有坑.
在第一遍扫描中, 我们只负责为各个 Node 创建 Environment, 并且为找到的变量定义创建绑定.
您可能已经注意到了, 我在下面的图片中将 FunctionDeclaration 直接作为一个变量来处理, 因为这种处理方式并不会造成太大的问题并且较为优雅.
接下来在第二遍扫描中, 我们只管为扫描到的 Identifier 都执行一下绑定 get 就好了. 根据我们的扫描原理, 如果存在 AssignmentExpression, 我们会先尝试绑定 set, 因此只要在具体的 Binding 实现中忽略对同一个 Identifier 进行的重复绑定即可.
大概就写到这里吧, 具体的完整源码我不方便给出, 不过关键的思路和代码我已经贴出来了. 如果您有兴趣, 顺着这个思路补完剩下的实现并不是很难的事情. 希望这篇博客能对您有帮助.