Lua AST静态分析探索

在日常测试中，我们不乏遇到一些修改了问题A却产生问题B，而且这两个问题间的联系并不是那么直观的情况。

面对此类问题，有没有办法通过自动化的方式，将改动关联的功能展示出来，推荐给功能测试同学进行回归呢？

通过浅试与思考，发现存在以下几个问题：

（1）插桩的开销非常大，行级别的插桩会使客户端直接卡死无法运行，函数级别的插桩也会造成明显的卡顿。

（2）游戏的操作较互联网APP会更为复杂，自动化用例涉及的操作可能涵盖多个功能，功能间耦合度高，很难做到用例和代码的精确对应。

（3）该方案完全依赖项目自动化测试，用例的完整度直接决定了代码的覆盖率，且项目后续迭代开发所带来的维护成本也是非常高昂的。

显然，动态方案想在游戏项目中进行应用，和互联网产品相比，复杂度更高、前期准备更多、维护成本也更高。

AST是抽象语法树（Abstract Syntax Tree）的简称，通常是编译器语法分析（syntax analysis）阶段的结果。它以树状结构表示代码，是编译工作的基础部分。

local skillSlotCounts = {}

比如这一行代码展开，如下图：

可以看到，由于是Local变量的赋值，因此它的类型为LocalStatement，并且包含两个key，分别为variables和init。variables表示变量名称，变量可以为多个，因此以数组表示。此处的变量名skillSlotCounts以最基础的类型Identifier表示，并通过name来存储其具体的值。同理，右侧赋值对象同样为数组类型的init表示，由于是个空的Table，因此以TableConstructorExPression表示，且fields为一个空数组，表示Table无任何子变量。

AST将代码转换为了一个标准树状结构，我们以它为基础，进行后续的Lua代码静态分析。

在想要找到某个函数的改动会对哪些功能产生影响，我们需要收集哪些信息呢？

首先需要识别所有变量的类型，包括Table、函数，都可归纳为不同类型的变量；其次还需要识别所有函数的调用，识别函数调用本身不难，AST中通过CallStatement等类型表示，关键点仍在第一步，就是识别所有的函数变量。

对于Lua，共包含6种基础类型（UserData和Threads暂不作讨论），分别为：

• Nil（AST类型NiLiteral）

• Boolean（AST类型BooleanLiteral）

• Number（AST类型NumericLiteral）

• String（AST类型的StringLiteral）

• Table（AST类型TableConstructorExpression）

• Function（AST类型FunctionDeclaration）

除了基本类型的直接定义，还需考虑变量间的传递。如下例，变量a的类型为number，变量b通过a传递赋值，类型也应识别为Number。

local a = 1local b = a

分析过程中，有可能出现无法识别变量类型的情况，因此我们定义第7种变量类型UnKnown，来表示尚未识别的类型。

讨论完变量类型，我们开始对分析流程进行梳理。大致可从Lua文件和Lua函数两个维度进行分析。

Lua AST静态分析，从Lua文件开始。Lua文件中定义了各种变量和函数，可以将所有Lua文件遍历进行第一层级分析，而不对函数内部进行分析，可以得到最基础的变量和函数列表。这是我们分析的入口数据，也是后续分析的基础。在此称这一过程为L1分析。

经过以Lua文件为目标的L1分析，便可进入以Lua函数为目标的L2分析。思路和L1分析类似，将L1分析得到的所有函数进行遍历，对函数内部进行分析，从而得到更全面的变量和函数列表。

那么，经过L1、L2两个阶段的分析后，是否就代表分析结束了呢？答案显然不是。让我们看个例子：

--file1local b = require "file2"local a = {}local b_func = b.funcfunction a.func()    b_func()endreturn a

-- file2local b = {}function b.func()    print("...")endreturn b

当L1分析过程中，file1首先被分析，那么在进行require解析时，还尚未知道file2能够返回Table b ，因此file1的local变量b将被解析为UnKnown类型，同理，b_func也将被解析为UnKnown类型。而当L2函数级别分析时，由于b_func为UnKnown类型，也就无法解析出a.func()调用了b.func()这一信息。

为了解决这个问题，我们引入了循环的概念。完成一次L1和L2分析称为一次循环，每当一次循环中有解析出新的变量、函数，或变量类型发生改变时，就需进行下一个循环，直至循环不再产生新的函数、变量且没有变量类型的更新。

仍以file1、file2为例，第一轮循环有新的变量，函数新增，因此需进入第二轮循环；第二轮循环中，file1的local变量b和b_func能够解析出类型，因此变量类型从UnKnown更新为了Table和Function，由于发生了变量类型的变更，因此还需进入第三轮循环；第三轮循环中，不再有新的变量、函数新增和变量类型的变更，因此不再进入下一个循环，分析结束。

总体分析流程可用下图表示：

上文讨论了整体的思路和分析流程，本小节我们来讨论具体的语法分析。语法分析涉及的内容较广，在此作一个概述，将主要语法和对应的AST类型进行概括介绍。

1. 赋值语句：LocalStatement、AssignmentStatement

local a = 1B = {}local bb = B   -- AssignmentStatement, 但b仍是local变量

赋值语句包括local赋值LocalStatement和global赋值AssignmentStatement。Lua变量的类型已在上文介绍。需要注意的是，示例代码中的最后一行赋值操作，属于变量间的传递，而变量b已在之前定义且为local，因此虽然AST语法上属于AssignmentStatement，但不改变它是local变量的事实。

2. 函数定义：FunctionDeclaration

local function func1(param1, param2)    local a = param1 + param2    return a end

函数定义FunctionDeclaration，是对函数的声明。我们可以通过它来识别函数变量。一个函数包含了参数、函数体等，因此在分析过程中需一并将这些数据保存，用作后续分析。

3. 函数调用：CallStatement

local function func2()    local a = func1(1, 2)end

函数调用CallStatement，代表一次函数调用。这也是我们分析调用链的关键。

4. 返回语句：ReturnStatement

-- file_alocal a = {test = "test"}return a

返回语句ReturnStatement，不仅会在Lua函数中会用到，Lua文件同样也会用到。通过调用具体函数，会将return的变量进行传递；而通过require Lua文件，同样能够将Lua文件的return变量进行传递。

-- file_blocal a = require "file_a"print(a.test)-- test

除了上述语法，还包括IfStatement、ForGenericStatement、WhileStatement等，在此不再展开介绍。

上文介绍了Lua AST静态分析的基本思路，这是我们进行分析的基础。但是想要实现自动化生成代码调用链的目标，还有许多难点需要解决。本节将重点介绍部分关键问题及其解决方案。

由于分析的核心问题在于变量类型的识别，因此对已有变量的保存和查找就显得尤为重要。

首先，需对变量名进行处理。对于一般变量，变量名无需特别处理，直接保存即可，复杂点在于Table类型子变量的处理。

localt = {        {x = "test1"},    b = {c = "test2", "test3"}}print(t.b.c)print(t.b[1])-- t.b.1print(t["b"]["c"])  -- t.b.cprint(t[1].x)       -- t.1.x

Table类型子变量，可通过“.”和数组两种形式调用，分别对应AST类型MemberExpression和IndexExpression。为了存储上保持一致，在变量名的分析过程中，会统一转换成MemberExpression的形式后进行保持。需要注意的是，Table子变量在无Key的情况下，会给予一个从1开始计数的index作为Key。

其次，我们引入了Level属性来表示变量的层级。

local a = "level_1 a"local function func()    print(a)                 -- level_1 a    local a = "level_2 a"    for i = 1, 3 do        local a = "level_3 a"        print(a)             -- level_3 a    end    print(a)                 -- level_2 aendfunc()

上述示例代码中，我们定义了3个名称都为“a”的变量，我们赋予它们不同的Level来识别为3个不同的变量。Lua文件第一层级的变量Leve=1；Lua函数中的变量Level=2；在if或for循环的语句中，Level在当前基础上增加1。在查找变量过程中，只能找到和当前环境相等或小的Level的变量，且优先找相等的变量。

另外还需要考虑变量的作用域。

local function func1()    local a = 1endlocal function func2()    local a = 1end

上述示例代码中，func1和func2均包含名为“a”的变量，且都是Level=2。这种情况下就需要考虑变量的作用域。对于func1中的local变量a，它的作用域仅在func1的函数体中，因此func2中去查找名为“a”的变量时，是无法查找到已有变量的，因此可以新建一个名称为“a”，作用域为func2函数体的local变量。

变量的查找过程，我们可以总结如下：对变量名称作一致性转换，并通过变量所在层级、作用域，从已有变量列表中进行查找。当然，以上分析都是变量为local的情况下展开，对于global变量，直接从global变量列表中查找即可。

L2函数级别分析时，函数是否存在参数变量，情况将大有不同。

local param1 = {value = 1}local param2 = {value = "test"}local function func(param)     return param.valueendlocal a = func(param1)  -- Number, 1local b = func(param2)  -- String, "test"

如上示例代码所示，函数func的返回值依赖传递进来的参数变量。当传递参数为param1时，函数返回变量类型为Number，而当传递参数为param2时，函数返回变量类型为String。因此，对于这类函数，简单分析函数本身是没有意义的，还需结合被调用时传递的参数变量相结合进行分析。我们将这一分析过程称之为“仿运行时分析”。

那么，是否传递的参数变量类型是Table才需要结合参数分析，其他类型参数就不需要了呢？答案是否定的。举个例子：

local t = {}local function declare(key, value)    rawset(t, key, value)enddeclare("test", 1)print(t.test)

示例代码中，调用函数declare传递了两个参数变量，类型分别为String、Number，通过buildin函数rawset在Table类型变量t中定义了新的子变量t.test。由此可见，当函数依赖外部Table变量的值，或函数执行过程中会对外部Table变量产生变化时，都需进行“仿运行时分析”。

所谓Buildin，指内置函数或内置全局变量，内置函数如上文提到的rawset，内置变量则以_G为代表。

内置函数从分析上看，可以当做是特殊的全局函数，在进行分析之前，应首先对内置函数进行初始化分析，主要是对其参数变量和返回值的处理。由于内置函数的作用各不相同，因此免不了需对每个内置函数进行单独处理，在结构上应与普通的函数变量作兼容。

内置变量_G在Lua用于存储global变量，即所有global变量均可通过_G表获得。因此在处理上也相对简单，新建一个global Table变量_G，解析得到的新global变量均保存进_G中。

Buildin的处理是一个相对枯燥的过程，理论上应涵盖Lua的所有内置函数和变量。

Lua支持闭包。关于闭包和Upvalue，可以先看以下示例代码。

local function closure_func(param)    local cf = function ()        return param     end    return cf endt1 = {name = "t1"}t2 = {name = "t2"}f1 = closure_func(t1)f2 = closure_func(t2)tt1 = f1()tt2 = f2()print(tt1.name, tt2.name)  -- t1    t2

函数cf定义在函数closure_func中，并可访问cf函数体作用域外的变量param。变量f1，f2分别通过传递变量t1，t2作为参数，调用closure_func方式获得。当调用f1，f2时，我们可以看到，虽然此时t1，t2已经在作用域外，但仍可正确对其进行调用。我们称之为闭包，t1、t2则分别为f1、f2的Upvalue。

为了正确处理闭包和Upvalue，我们在分析上作了以下处理：

（1）定义闭包原函数。如示例代码中的cf，将其作闭包标记。

（2）定义被传递闭包变量，并保存传递时的参数变量列表。如示例代码中的f1、f2，将其标记为被传递闭包变量，并分别保存t1、t2作为Upvalue与f1、f2绑定。

（3）当被传递闭包变量被调用时，需先分析闭包函数的母函数，并还原参数变量列表，再分析闭包原函数。如示例代码中f1被调用时，首先将绑定的t1还原回函数closure_func的参数变量列表，并对closure_func进行分析，然后再对函数cf进行分析。

通过上述3个步骤，我们对f1或f2的调用分析所返回的结果才会是正确的。

Metatable是Lua语言中非常精妙的设计，可以通过它实现诸多机制，如面向对象的类等。也正因为使用上的灵活，使得对Metatable的静态分析非常困难。此小节，主要讨论两个MetaMetods。

首先讨论_index方法。当从一个Table类型的变量中取子变量但不存在时，会从它的Metatable的index方法中尝试取这个变量。《Programming in Lua》中的示例代码很好的作了解释。

Window = {}Window.prototype = {x=0, y=0, width=100, height=100, }Window.mt = {}function Window.new (o)  setmetatable(o, Window.mt)  return o endWindow.mt.__index = function (table, key)  return Window.prototype[key]endw = Window.new{x=10, y=20}print(w.width)    -- 100

_index也可以直接赋值为一个Table变量，此时会变成从该Table变量中查找子变量。

我们接着讨论_call方法。call方法的作用是可以让Table变量像函数一样调用。如下示例代码所示，Table类型变量c的Metatable_M包含call方法，因此可以直接调用。

local function Class()    localCls = {}    Cls.__index = Cls    local _M = {}    setmetatable(Cls, _M)    _M.__call = function (_, ...)        local inst = {}        setmetatable(inst, Cls)        return inst    end    return Clsendlocal c = Class()local test = c()

为了正确处理Metatable，我们在分析过程中，需对Table类型变量保存好相关的变量和方法，并在查找变量时参考Lua的实现，返回正确的子变量或函数调用。

对于_call方法的示例代码，我们稍作改变，来看下Metatable和闭包的混合使用。

local c = Class()function c.func()    print("c.func print...")endlocal test = c()test.func() -- c.func print...

修改后的示例代码中，我们给Table变量c新增了函数c.func。通过直接调用c，触发了Metamethod _call并返回了Table类型变量，生成Table变量类型test。而当我们调用test.func时，它也是生效的，这是为什么呢？

我们看回call函数，发现将Cls设置为了inst的Metatable，而Cls的index指向它自己。而在调用call函数的过程中，Cls实际上是Upvalue，此时的真实变量为c，因此test中也就包含了c中全部的子变量和函数。

这是个较为复杂的例子。我们在分析过程，需要处理好这类return形式返回后再调用闭包函数的情况，将Upvalue替换为正确的变量。

细心的读者可能发现，上一小节Metatable的示例代码中，已经实现了面向对象类与实例的应用。通过灵活使用Metatable和闭包的特性，可以很好地在Lua语言中实现面向对象的设计：函数Class可以认为是一个类的实现，通过定义index函数，可以在类中实现基本方法和属性；通过call函数，可方便地供外部调用生成实例。

以上代码是在笔者项目中类实现的简化例子，相信读者也可在自己项目中找到类似的实现和应用。

本文总结了Lua AST静态分析的原理和部分难点，那么，Lua AST静态分析的结果，除了本文提到的通过调用链关联对应功能的应用，是否还有别的应用场景呢？我想答案是肯定的。我们做这方面探索的初衷，是希望静态分析能够尽可能多地保存中间分析数据，供上层应用进行二次开发，进而应用到更多场景中。

• 如配表变量，分析其在代码中的传递和比较，我们可以分析得到不同配表字段的关联，进而辅助配表检查规则的编写；

• 如和多语言相关的全局变量，分析其在函数中的调用情况，找到所有可能出现的功能场景，帮助QA迅速定位功能点；

• 如保存美术资源路径的变量在代码中由于进行了拼接等操作而无法直接定位，通过分析还原其对应的具体资源，辅助进行美术资源调用分析和冗余检查。

精准测试的相关探索开发仍在进行中，Lua AST静态分析也仍有不少问题亟待解决。我相信，游戏领域的精准测试，应用的场景可以很多，面临的困难也会很多。希望未来，精准测试能够为大家的测试工作带来切实的帮助。

推荐阅读

美术资源精准测试

如何从工作中提取工具需求

接口测试快速上手指南

我对探索式测试的探索