重写 500 Lines or Less 项目 - Static Analysis

版权声明:所有博客文章除特殊声明外均为原创,允许转载,但要求注明出处。

概述

本文章是 重写 500 Lines or Less 系列项目其中一篇,目标是重写 500 Lines or Less 系列的原有项目:静态分析/Static Analysis。原文章代码是基于 Julia 这种新型的编程语言,主要分析目标是该语言中比较被强调的一个特性:多重分派(multiple dispatch)。考虑到 Julia 语言并不是特别普及,同时多重分派在其他语言中也并非常见特性(也有与之相近的概念),可能大部分读者对它会比较陌生,影响对于原文的理解。因此,本文选择基于主流、同时也比较便于学习和理解的 Python 来演示静态分析的原理和过程,不再按照原文的体例。

示例代码

本文及系列文章的所有代码都开源在 Github 仓库:500lines-rewrite。本文相关代码位于 static_analytics 目录,其中 main.py 为执行程序的入口点,tests 目录则是用内置模块 unittest 编写的单元测试代码。

读者可以在命令行或者集成开发环境中直接执行上述程序或测试代码,来检查实际效果。需要说明的是,程序和测试在执行过程中可能会生成一些辅助性的文件(默认位于 dump 目录下),如果程序运行所在的工作目录不是 static_analysis 的话,那么执行有可能会出错,或者把文件输出到其他意外的位置。

静态分析

虽然听起来像一个比较高深的概念,实际上从用户角度讲,使用各种编程语言的开发者对静态分析技术已经非常熟悉了。当我们在自己喜爱的编辑器或 IDE 中编辑代码的时候,这些工具会在幕后自动解析源码,将其中可疑或有错误的部分用红色波浪线标记出来。熟练的开发者会把执行代码风格检查、或者叫做 Linting 的工具加入自己的工具箱,通过持续集成之类的技术,让它们在每次签入代码时自动执行,其结果也可以作为评估代码质量或开发节奏的辅助信息。

Python 来说,从著名的 PEP8 开始,很多推荐的代码风格和指导性建议被陆续引进官方规范之中。在此基础上也诞生了众多静态分析和检查工具,比如 pylintpydockstylepyflakesflake8,以及各个 IDE 集成的同类功能。大家可能或多或少已经用过上述工具的其中一些了。

要想实现对程序代码的静态分析功能,首先要将源码解析成能够理解的结构化数据,也就是所谓的抽象语法树(AST)。这是个有相当难度的工作,好在我们不需要从头做起,以 “自带电池” 而著称的 Python 已经内置了这个功能。让我们先来了解这个有用的模块:ast

Python 内置模块:ast

ast 模块的基本用法是相当简单的:解析源码,得到抽象语法树。

import ast

code = """print('Hello World!')"""
root = ast.parse(code)
print(root)

以上代码会在命令行输出(实际数字当然在每台机器上结果不同):

<_ast.Module object at 0x0000021C9ECA6BE0>

Python 程序以模块为代码组织的基本单位,因此解析到的根节点总是一个 Module 对象。所有节点都是 ast.AST 的子类。要了解完整的节点类型列表,我们可以参考官方文档 Abstract Syntax Trees:

AST Documentation

以上是一个并不完整的列表。我们从名字大概就可以知道它们的含义:赋值(Assign)、返回(Return)、循环(For)、条件判断(If),以及更加高层的块级语法,包括函数定义(FunctionDef)、类定义(ClassDef),等等。异步方法的元素则是单独定义的(名字带有 Async 前缀)。

除了知道有哪些可能的语法元素外,我们还需要了解 AST 的结构是什么样的。当然,每种节点有自己的数据定义,不过从一般角度讲,所有节点都有两个重要成员(都有下划线):

  • _attributes 节点自身的属性。它们通常是一些简单的值,几乎所有节点都包括以下四个属性:lineno/col_offset/end_lineno/end_col_offset。显然,它们表示元素在代码中的起止位置。有点不太直观的是,lineno 是从 1 开始计数,而 col_offset 却是从 0 开始计数的。这是设计上一点缺乏一致性的地方。
  • _fields 包含节点持有的“子节点”。这是一个有点抽象的说法,实际上它可能是以下三种情况之一:

  • 节点本身持有的信息,通常是比较复杂的对象

  • 另一个 AST 节点,也就是该节点的子节点
  • 在更复杂的情况下可能是列表(list),表示多个子节点的集合。

由于 AST 本身是一个树状结构,用来处理它的算法几乎总是递归的。为了支持节点遍历这种常见需求,ast 模块提供了一个抽象类:NodeVisitor,从名称可知,它使用了 Design Patterns 中的访问者模式。我们的实现会大量使用该类,所以先对它有一个深入的了解是很有必要的。(此外还有一个更加高级的 NodeTransformer,不过本文不涉及转换 AST 的内容,因此不作讨论。)

NodeVisitor 是一个抽象基类。要使用它,我们需要继承它得到一个派生类,再按照自己的要求添加成员。常见的实现模式有以下两种:

  • 如果我们关心某种特定类型的的节点,按照 NodeVisitor 的约定,需要添加一个名为 visit_XXXX 的方法,其名称和节点的类名严格对应(各种节点对应的类型可参考前面给出的 AST 文档),参数是访问到的节点。例如,要访问函数定义,则添加方法 visit_FunctionDef(node),依此类推;
  • 如果想要同时支持多种节点类型,或有其他特殊要求,可以重载其 visit(node) 方法。

不管使用哪种方式,如果要继续遍历的话,必须调用基类的 generic_visit(node) 方法,否则遍历过程将会中断。

典型示例如下所示:

class MyVisitor(ast.NodeVisitor):
    def visit(self, node: ast.AST):
        print('visit node:', node)
        return self.generic_visit(node)

    def visit_FunctionDef(self, node: ast.FunctionDef):
        print('visit function:', node)
        return self.generic_visit(node)

实际上,NodeVisitor 的实现并不复杂,而且可以帮助我们理解为什么会有上述要求。我们不妨看一下源码:

class NodeVisitor(object):
    def visit(self, node):
        method = 'visit_' + node.__class__.__name__
        visitor = getattr(self, method, self.generic_visit)
        return visitor(node)

    def generic_visit(self, node):
        for field, value in iter_fields(node):
            if isinstance(value, list):
                for item in value:
                    if isinstance(item, AST):
                        self.visit(item)
            elif isinstance(value, AST):
                self.visit(value)

从源码可以发现,visit 方法会根据节点类型寻找对应的处理函数,如果没有定义的话,则调用 generic_visit()。而 generic_visit() 的做法则是访问所有字段,如果是 AST 节点的话,就递归执行下去。值得注意的是,根据字段值是否为列表需要进行不同的处理。

输出 AST

理论性的东西我们已经讲了很多,不过眼见为实,具体的语法树到底是什么样子?Pythonast 模块有一个辅助方法 dump() 可以输出 AST 内容,大家可以自己试试看。一个基本的输出大概是类似这样的:

Module(body=[FunctionDef(name='add', args=arguments(posonlyargs=[], args=[arg(arg='a', annotation=None, type_comment=None), arg(arg='b', annotation=None, type_comment=None)], vararg=None, kwonlyargs=[], kw_defaults=[], kwarg=None, defaults=[]), body=[Return(value=BinOp(left=Name(id='a', ctx=Load()), op=Add(), right=Name(id='b', ctx=Load())))], decorator_list=[], returns=None, type_comment=None)], type_ignores=[])

可见内容并没有得到很好的整理,看上去相当吃力,即便手工格式以后也还是不够清晰。社区也存在一些第三方工具,比如 instaviz 可以把 AST 结构渲染成图形,有兴趣的同学也可以尝试。然而说实话,instaviz 生成的界面非常复杂且缺少重点,缺乏经验的用户很容易看得一头雾水。

为了实现静态分析,我们需要对目标代码的 AST有一个清楚的了解,因此帮助我们查看 AST 结构的辅助工具是非常有必要的。既然没有理想的工具,不妨自己来写一个。本文将要实现的工具使用另外一种思路:将 AST 结构输出到 XML 文件。之所以选择这个方法,主要是出于以下几方面原因:

  • 首先,AST 的复杂性可能会超出你的预料。输出到普通文本,哪怕是带有缩进的文本,其内容仍然过于复杂。而 XML 可以很好地展示内部结构;
  • 其次,现代编辑器对 XML 这样的结构化文本都有完善的支持,用户可以展开或折叠特定地节点,逐步了解各个层次结构,同时忽略那些不需要关心的部分;
  • 有的朋友可能会问,为什么不使用 JSON?网络上很多资料会告诉你 JSONXML 更简单,但那是有条件的。对于 AST 这种复杂的结构,XML 每个元素都有明确的名字,可以清楚地看到每个节点的类型,而 JSON 必须付出额外的努力,才能理解每一层大括号到底表示什么含义。另外,JSON 文档格式化以后太过冗长,同时嵌套层次又非常深,对于阅读来说其实是非常不利的。使用 XML 还有一个好处,那就是 AST_attributes_fields 恰好能匹配到 XML 中 AttributeElement 的概念,所以处理起来更加自然。

我把生成 XML 的操作封装到源码中的 astxml.py 模块。因为这只是个辅助工具,就不再占用文章篇幅了,读者有兴趣的话可以去阅读源码。现在,我们可以用一个简单的源码来进行测试:

import ast
from astxml import AstXml

code = """
def add(a, b):
    return a + b
""".strip()

ast_node = ast.parse(source_code)
AstXml(ast_node).save_file('filename.xml')

然后打开生成的 XML 文件,应该会看到类似这样的内容(部分):

AST Dump XML

初学者首次看到 AST 结构往往会吓一跳,因为它比起对应的源码来说实在是复杂太多了。不过仔细多看几遍,还是能看出一些规律的:

  • AST 的根节点总是从 Module 开始;
  • 除了 Module 之外,所有 AST 节点几乎都包含起止位置的行号/列号,也就是 lineno/col_offset/end_lineno/end_col_offset 这几个字段;
  • 每种 Python 语法有自己的 AST 结构。比如 print() 方法调用,我们可以再分析其结构:
  • 它是一个表达式(Expr
  • 表达式内容是函数调用(Call
  • 函数引用是一个 NameName.id 记录其具体名称
  • 参数是一个集合,对于常量参数,表示为 Constant

以上虽然是一个简单的示例,但也揭示了静态分析工具的典型开发方法:不论多么复杂的语法处理,首先要做的是理解它的 AST 结构是什么样的,然后才能做出相应的处理。

编写程序

现在,我们理解了 AST 的基本原理和分析方法,是时候开发一个真正的静态分析工具了。

本文的实现目标是:挑选出一些常见的 Python 代码问题,通过自己编写静态分析工具来识别到这些问题,并返回明确的出错(或警告)信息给用户。

我们已经看到,AST 结构是相当复杂的,可想而知解析的工作也比较容易出错。因此用测试驱动开发(TDD)来保证程序质量是一个不错的主意。我们也会采用自底向上的方式,先逐个实现对每种问题的单独检查,再把所有功能组合起来形成完整的程序。

数据结构设计

在实现检查之前,首先设计一下程序需要的数据模型。我们需要一个数据结构来表示出错的信息,可以想象,它应该包括文件名、出错位置、错误信息等。为了便于处理,很多工具还会给每种错误类型分配一个内部编号。本文系列的基本原则是充分利用语言特性,不用特意考虑对低版本的兼容性问题,因此用新的数据类(dataclass)来描述:

@dataclass
class CodeIssue:
    filename: str = None
    line: int = 0
    column: int = 0
    code: str = None
    message: str = None

    def __str__(self):
        pattern = '{file}({line},{col}) {code}: {message}'
        return pattern.format(file=self.filename,
                              line=self.line,
                              col=self.column,
                              code=self.code,
                              message=self.message)

考虑到检查过程通常会找到多个错误,再实现一个 Context 类来管理找到的内容:

class AnalysisContext:
    def __init__(self, filename: str):
        self.filename = filename
        self.issues = []

    def add_issue(self, node: ast.AST, code: str, message: str):
        issue = CodeIssue(filename=self.filename,
                          line=node.lineno,
                          column=node.col_offset,
                          code=code,
                          message=message)
        self.issues.append(issue)

该类基于一个简化的假定:本示例实现的检测都是针对单个代码文件的。实际开发中当然需要支持多个源文件,但管理多个文件及其与问题的映射关系需要很多额外的工作,且显得有点偏离主题。读者如果觉得不满意的话,可以在实现基本功能之后再进一步扩展。

代码长度检查

PEP8 中对代码长度有这样的要求:

Limit all lines to a maximum of 79 characters.

For flowing long blocks of text with fewer structural restrictions (docstrings or comments), the line length should be limited to 72 characters.

我们已经知道,几乎所有 AST 节点都包含行号/列号信息,因此实现长度检查的要求是非常容易的。不过,AST 结构不是固定的,要访问所有节点就必须使用递归遍历的方法,也就是前面介绍过的 NodeVisitor。针对长度检测这个要求而言,我们计划实现一个派生类称为 LineLengthVisitor。按照 TDD 的要求,首先为它编写一个测试:

class LineLengthVisitorTest(TestCase, VisitorTestMixin):
    visitor_type = LineLengthVisitor

    def test_visit(self):
        code = """
print('short line')
print('this is a very, very, very, very, very, very, very, very, very, very, very, very long line...')
        """.strip()
        ctx = AnalysisContext('test.py')
        visitor = LineLengthVisitor(self.ctx)
        ast_node = ast.parse(code)
        visitor.visit(ast_node)
        AstXml(ast_node).save_file('dump/line-length.xml')
        self.assertEqual(1, len(ctx.issues))
        issue = ctx.issues[0]
        self.assertEqual((2, 'W0001'), (issue.line, issue.code))

这段代码略微有点长,但其中的逻辑不难理解。代码创建 LineLengthVisitor 来遍历AST 结构,如果实现正确的话,应该发现第 2 行超过了允许的长度(回忆一下,行号从 1 开始计数)。按照约定的规则,我们应该给错误信息一个编号。这是第一个目标问题,且应该视为警告(Warning)而不是错误,所以我们把它编号为 W0001

上述测试选择行号和信息编号两个字段来检查,是因为它们通常是相对稳定的。列号和消息通常变化比较大,容易引起测试的不稳定。当然,在产品级别的代码中还是应该想办法加以验证,作为演示程序来说就不在这上面费力气了。

能够通过测试的实现逻辑很简单:

class LineLengthVisitor(ast.NodeVisitor):
    max_length = 79

    def __init__(self, ctx: AnalysisContext):
        super().__init__()
        self.ctx = ctx

    def visit(self, node: ast.AST):
        if 'end_col_offset' in node._attributes and node.end_col_offset > self.max_length:
            self.ctx.add_issue(node, 'W0001', f'Exceed max line length({self.max_length})')
        else:
            self.generic_visit(node)

尽管绝大部分 AST 节点都包含行列号,但也有个别节点不支持(比如 Module),为了避免出错,我们先验证这些字段确实存在,然后再去检查它们的值。如果当前节点没有问题的话,再检查它们的子节点,所以别忘了调用 generic_visit()

现在运行测试的话,应该是正常通过的。很好!我们成功迈出了第一步。

要完整实现 PEP8,还需要注意关于文档的补充条款:

For flowing long blocks of text with fewer structural restrictions (docstrings or comments), the line length should be limited to 72 characters.

我们可以自己写一段带注释的 Python 代码,用上文实现过的辅助工具去分析其结构。但我们会发现一个棘手的问题:分析到的 AST 结构并不包含文档内容!这是因为 ast 模块主要是为执行 Python 程序服务的,它出于效率考虑去掉了一些在执行时无关紧要的信息,尤其是注释。不过好消息是,文档注释(docstring)还是保留下来了(如果我们是用 -OO 开关运行 Python 的,那么文档信息可能不会保留)。因此我们不得不降低要求,不去考虑注释,只分析 docstring

再编写一个针对 docstring 的测试:

    def test_visit_docstring(self):
        code = """
def fn():
   '''
   This is a very, very, very, very, very, very, very, very, very, very, very, very long doc string
   The second line
   '''
   pass        
        """.strip()
        ...
        issue = ctx.issues[0]
        self.assertEqual((3, 'W0001'), (issue.line, issue.code))

除了源码和错误信息之外,其他大部分代码是重复的,为节约篇幅就不再完整列出了。大家可以参考 Github 上的完整代码。

当我们试图实现上述规则的时候又会遇到一个棘手的问题。文档字符串(docstring)并没有单独的 AST 类型,而是表示为常量(Constant)。但要分析一个 Constant 是否是 docstring 不得不做一些额外的分析工作。实际上,ast 模块为我们提供了一个辅助方法 get_docstring(),但尝试一下就会发现,它返回的只是注释内容,不包含节点信息,因此无法获得准确的行号。我们不得不自己去做一些额外的工作:从 get_docstring 实现复制代码,并修改为返回节点:

    def get_docstring_node(self, node):
        """Return the AST node of docstring"""
        if not isinstance(node, (ast.AsyncFunctionDef, ast.FunctionDef, ast.ClassDef, ast.Module)):
            raise TypeError("%r can't have docstrings" % node.__class__.__name__)
        if not(node.body and isinstance(node.body[0], ast.Expr)):
            return None
        value_node = node.body[0].value
        if isinstance(value_node, ast.Constant) and isinstance(value_node.value, str):
            return value_node
        return None

然后,修改 visit 方法,增加对注释内容的判断:

class LineLengthVisitor(BaseVisitor):
    max_length = 79
    max_docstring_length = 72

    def visit(self, node: ast.AST):
        if isinstance(node, ast.FunctionDef):
            self.check_docstring(node)
        # ... origin code

    def check_docstring(self, node: ast.AST):
        doc_node = self.get_docstring_node(node)
        if not doc_node:
            return self.generic_visit(node)
        for offset, line in enumerate(doc_node.value.split('\n')):
            if len(line) >= self.max_docstring_length:
                lineno = doc_node.lineno + offset
                self.ctx.add_issue(node, 'W0001',
                                   f'Docstring for {node.name} exceed max length({self.max_docstring_length})',
                                   lineno=lineno)

上述代码有带来一个新的要求:add_issue() 方法需要增加可选参数 lineno,因为具体行号和节点的开始位置有可能不是完全对应的。这个修改很容易实现,本文也不再具体列出了。

现在新增的两个测试都应该正常通过了。不过在开始下一个任务之前,我们应该考虑一下如何清理现有代码。目前仅有的两个测试已经出现了一些重复,特别是遍历 AST 和检查结果的部分。可以有把握地说:后面的测试仍然会使用类似的结构,只是参数和结果有所不同。为了简化后续的工作,有必要把这些重复的代码提取出来。

因为测试用例都是从 TestCase 派生而来的,重用代码最直观的思路是继承。(由于测试类本身持有一些状态,所以单纯的函数并不太适用)但是,使用派生类也存在一些潜在的问题,特别是抽象类可能会被错误地当作需要执行的用例。因此,我选择使用 Mixin 模式和多重继承,因为 Mixin 不是从 TestCase 继承而来,也就不会有被错误执行的风险。

将访问 AST 并检查结果的基本模式提取如下:

class VisitorTestMixin:
    visitor_type = None

    def run_visitor(self, code: str, xml_filename: str = None):
        self.assertIsNotNone(self.visitor_type, 'Visitor type not defined.')
        self.ctx = AnalysisContext('test.py')
        visitor = self.visitor_type(self.ctx)
        ast_node = ast.parse(code)
        visitor.visit(ast_node)
        if xml_filename:
            AstXml(ast_node).save_file('dump/' + xml_filename)

然后,测试代码就可以简化成:

class LineLengthVisitorTest(TestCase, VisitorTestMixin):
    visitor_type = LineLengthVisitor

        def test_visit(self):
        code = ...
        self.run_visitor(code, xml_filename='line-length.xml')
        self.assert_found_issue(2, 'W0001')

异常类型检查

接下来要实现的问题有关异常。按照业界的最佳实践,在多数情况下,我们应当尽量避免捕获所有异常,而是明确指定特定类型,从而使得异常处理更有针对性。以下是一个简单示例:

# Correct
try:
  x = my_dict[key]
except KeyError:
  ...

# Wrong
try:
  x = my_dict[key]
except Exception:
# or except:
  ...

为实现此要求,用辅助工具检查一下异常处理代码的 AST 结构:

Try handler dump

可见:异常处理的主体是一个 Try 节点,我们需要重点关注的是其中的 handlers 部分。不过要注意,Try 结构包含其他一些变化形式,比如:

  • 同时捕获多个异常类型,如 except (ValueError, KeyError)
  • 不指定具体类型,只包含一个简单的 except

上述变体在结构上也是有所差别的。为保证代码足够健壮,我们也应该在单元测试中包含各种可能的场景,保证代码在所有边界情况下都能正常执行。

相信大家已经熟悉这个步骤,我们可以稍稍加快一点节奏,一次编写两个测试,分别针对没有异常处理、以及基本的异常处理代码:

class ExceptionTypeVisitorTest(TestCase, VisitorTestMixin):
    visitor_type = ExceptionTypeVisitor

    def test_no_handler(self):
        code = """print('hello')""".strip()
        self.run_visitor(code, xml_filename='exception-no-handler.xml')
        self.assert_no_issue()

    def test_handler_generic(self):
        code = """
try:
   calc()
except Exception as e:
   print(e)
        """.strip()
        self.run_visitor(code, xml_filename='exception-catch-generic.xml')
        self.assert_found_issue(3, 'W0002')

我们已经知道异常代码的 AST 结构,实现起来毫无难度:

class ExceptionTypeVisitor(BaseVisitor):
    def visit_ExceptHandler(self, node: ast.ExceptHandler):
        exp_type = node.type
        if isinstance(exp_type, ast.Name) and exp_type.id == 'Exception':
            self.ctx.add_issue(node, 'W0002', f'Avoid catch generic Exception.')
        self.generic_visit(node)

但是,再增加一个针对边界情况的用例,就会发现上述实现还不够完善:

    def test_catch_multiple_types_with_issue(self):
        code = """
try:
   calc()
except (Exception, ValueError) as e:
   print(e)
        """.strip()
        self.run_visitor(code, xml_filename='exception-catch-multi-with-issue.xml')
        self.assert_found_issue(3, 'W0002')

我们应该根据输出的 XML 文件来验证一下。在同时匹配多个异常的情况下,ExceptionHandlertype 部分是一个 tuple,其中包括所有要捕获的异常类型。为了避免重写所有代码,让我们编写一个辅助函数,统一将异常类型作为集合返回,这样访问异常节点的代码主体可以保持不变:

class ExceptionTypeVisitor(BaseVisitor):
    AVOID_TYPES = ('Exception', 'BaseException')

    def iter_exception_types(self, node: ast.AST):
        if isinstance(node, ast.Name):
            yield node
        elif isinstance(node, ast.Tuple):
            for name_node in node.elts:
                if isinstance(name_node, ast.Name):
                    yield name_node

    def visit_ExceptHandler(self, node: ast.ExceptHandler):
        for name_node in self.iter_exception_types(node.type):
            if name_node.id in self.AVOID_TYPES:
                self.ctx.add_issue(name_node, 'W0002', f'Avoid catch generic Exception.')
        self.generic_visit(node)

这样测试又可以正常通过了。

最后是无异常类型的检查:

    def test_catch_no_type(self):
        code = """
try:
   calc()
except:
   print(e)
        """.strip()
        self.run_visitor(code, xml_filename='exception-catch-no-type.xml')
        self.assert_found_issue(3, 'W0002')

这种情况下,用分析工具可以看到 ASTtype 节点为 None。因此我们只需要简单增加一个检查即可:

    def visit_ExceptHandler(self, node: ast.ExceptHandler):
        if not node.type:
            self.ctx.add_issue(node, 'W0002', f'Please specify exception type to catch.')
        # ... origin code

变量使用检查

声明过的变量从未被使用,是程序中非常常见且值得关注的一类问题。出现这类问题可能是因为开发者修改了实现、但未能清理原有代码,也可能纯粹是开发者打错了字。在 Python 中这类问题尤其值得关注,因为没有编译器来捕获这类错误(单元测试当然也是一个途径,但不在本文讨论范围之内)。接下来我们考虑如何用静态分析来发现这种问题。

用辅助工具来检查代码对应的 AST,我们会发现:变量无论是声明还是引用,都会表示为 Name 节点。区别在于,在 Python 中并没有单独的变量声明,而是赋值就自动生成变量,它对应到语法树的 Assign 节点。Assign 之外的 Name 都可以视为引用。

我们还是编写测试,来检查在变量被使用和未被引用的情况下,程序是否能正确检查到问题:

class VariableUsageVisitorTest(TestCase, VisitorTestMixin):
    visitor_type = VariableUsageVisitor

    def test_vars_all_used(self):
        code = """
def fn():
    name = 'user'
    print(name)        
        """.strip()
        self.run_visitor(code, xml_filename='var-used.xml')
        self.assert_no_issue()

    def test_vars_not_used(self):
        code = """
def fn():
    name = 'user'
    print('hello')        
        """.strip()
        self.run_visitor(code, xml_filename='vars-unused.xml')
        self.assert_found_issue(2, 'W0003')

表面看起来,实现这个要求并不复杂,只要看 Name 节点是否出现在 Assign 内部就行了。但实际上,我们需要考虑作用域的问题:函数内部变量和全局变量(实际上应该是模块级变量)是不一样的。在 Python 中,函数还可以嵌套定义,这让问题进一步复杂化了。

还是首先编写测试。我们需要验证,在没有定义变量、定义并使用、或者定义但未使用等场景下,程序能检查到预期的问题:

class VariableUsageVisitorTest(TestCase, VisitorTestMixin):
    visitor_type = VariableUsageVisitor

    def test_no_func(self):
        code = """print('hello')""".strip()
        self.run_visitor(code, xml_filename='var-no-func.xml')
        self.assert_no_issue()

    def test_global_vars_used(self):
        code = """
name = 'user'
print(name)        
        """.strip()
        self.run_visitor(code, xml_filename='global-vars-used.xml')
        self.assert_no_issue()

    def test_global_vars_unused(self):
        code = """
name = 'user'
print('hello')        
        """.strip()
        self.run_visitor(code, xml_filename='global-vars-unused.xml')
        self.assert_found_issue(1, 'W0003')

实现部分有些复杂,所以我们分步讲解。为了记录哪些变量被定义/引用,我们需要增加额外的成员变量,此外还要记录当前是否在赋值(Assign)作用范围内,以判断是否变量定义。

细心的同学会发现声明/使用两个集合的定义是不对称的。当发现未使用的变量时,我们需要输出其原始位置,但多次赋值(AST节点不同)应视为同一变量,所以记录为 {var_name: node} 的形式。而哪些变量被使用只要知道变量名即可,所以可以定义为 set

class VariableUsageVisitor(BaseVisitor):
    def __init__(self, ctx: AnalysisContext):
        super().__init__(ctx)
        self.in_assign = False
        self.declare_vars = {}
        self.used_vars = set()

    def visit_Assign(self, node: ast.Assign):
        self.in_assign = True
        self.generic_visit(node)
        self.in_assign = False

当访问到 Name 节点时,根据是否赋值记录其用途:

    def visit_Name(self, node: ast.Name):
        var_name = node.id
        if self.in_assign:
            self.declare_vars[var_name] = node
        else:
            self.used_vars.add(var_name)

最后,当访问完毕后,将定义/引用的变量列表转换成 set 进行集合运算,其差就是那些未被引用的变量:

    def visit_Module(self, node: ast.Module):
        self.generic_visit(node)
        unused_vars = set(self.declare_vars) - self.used_vars
        for var_name in unused_vars:
            node = self.declare_vars[var_name]
            self.ctx.add_issue(node, 'W0003', f"Variable '{var_name}' declared but never used")

到此,我们实现了对变量使用情况的基本检查逻辑,但还没有考虑到的一个问题是作用域。再编写一个测试:

    def test_nested_funcs(self):
        code = """
def outer():
  def inner():
      name = 'inner'
      print('hello')
  name = 'outer'
  print(name)
        """.strip()
        self.run_visitor(code, xml_filename='vars-nested-func.xml')
        self.assert_found_issue(3, 'W0003')

该代码中有两个 name 变量,它们从属于不同的作用域,第一个变量是没有被使用的。我们目前的实现无法检查出这个问题,因为它会把两个 name 当作同一个。为解决此问题,我们还有对原代码做比较大的修改。

所谓变量的作用域,从本质上来说也是一棵树,但是在访问时它的表现更像一个堆栈:进入函数(或类)定义是“入栈”,从函数返回是“出栈”。栈上的每一项都应该记录哪些变量在该范围内被使用,而不是使用全局数据结构。因此,我们先要把记录变量信息的记录提取出来作为一个数据结构,我把它命名为 VariableScope。它基本上就是把前面代码中对 declare_varsused_vars 相关的处理集中起来,计算方法完全相同,这里也不再列出了,读者可以阅读源码。

VariableUsageVisitor 的实现也需要做比较大的修改。我们在其构造函数中增加一个列表,用来记录作用域的堆栈:

class VariableUsageVisitor(BaseVisitor):
    def __init__(self, ctx: AnalysisContext):
        super().__init__(ctx)
        self.in_assign = False
        self.scope_stack = []

当进入一个新的作用域时,我们将该节点压入堆栈,调用完毕后弹出,并检查变量的使用情况:

    def visit(self, node: ast.AST):
        is_scope_ast = isinstance(node,
                                  (ast.Module, ast.FunctionDef, ast.ClassDef))
        if is_scope_ast:
            scope = VariableScope(node)
            self.scope_stack.append(scope)
        super().visit(node)
        if is_scope_ast:
            self.scope_stack.remove(scope)
            scope.check(self.ctx)

最后,在访问 Name 节点时,我们把它记录在当前作用域(也就是堆栈的最顶层一项)中:

    def visit_Name(self, node: ast.Name):
        if self.scope_stack:
            scope = self.scope_stack[-1]
            scope.use(node, self.in_assign)
        self.generic_visit(node)

完成这些修改之后,对于嵌套定义的测试用例也可以正确通过了。

需要说明的是,对于作用域问题,我们还是做了一些简化。特别是 Python 中有一些特殊语句,比如 global/nonlocal 等,它们会改变变量的查找逻辑,而我们并未考虑如何去处理这些规则。考虑到我们实现的是一个不到 500 行的演示程序,这样的缺点也还是可以接受的。

语序问题检查

Python 以简洁易懂而著称,也特别重视语句是否直观、自然。比如,以下两种写法在逻辑上是等效的,但 PEP8 明确指出:应该尽可能地使用第一种写法。

# Correct
if foo is not None: pass
# Wrong
if not foo is None: pass

为了检查类似这样的问题,我们还是用辅助工具观察一下它的 AST 是什么结构。结果大概如下:

Not Is Dump XML

其中重点是 Not 和 Is 两个关键元素出现的位置。

了解完结构,按照规则还是先写单元测试:

class PreferIsNotVisitorTest(TestCase, VisitorTestMixin):
    visitor_type = PreferIsNotVisitor

    def test_is_not(self):
        code = """
if a is not None:
    print(a)
        """.strip()
        self.run_visitor(code, xml_filename='is-not.xml')
        self.assert_no_issue()

    def test_not_is(self):
        code = """
if not a is None:
    print(a)
        """.strip()
        self.run_visitor(code, xml_filename='not-is.xml')
        self.assert_found_issue(1, 'W0004')

因为语法结构是固定的,所以不再需要遍历,只考虑目标节点即可。以下实现非常直接,但因为做了很多类型检查,所以显得有点繁冗。经验告诉我们,对于 AST 这种变化多端的结构,检查太多总好过太少。当然读者可以有不同的见解。

class PreferIsNotVisitor(BaseVisitor):
    def visit_If(self, node: ast.If):
        if isinstance(node.test, ast.UnaryOp) and \
                isinstance(node.test.op, ast.Not):
            operand = node.test.operand
            if isinstance(operand, ast.Compare) and \
                    len(operand.ops) == 1 and \
                    isinstance(operand.ops[0], ast.Is):
                self.ctx.add_issue(node, 'W0004', 'Use if ... is not instead')
        self.generic_visit(node)

这次的目标非常简单,也没有其他变化,所以这样的实现就足以通过测试了。

汇总

完成以上四种问题的检查,我们把它们合成一个完整的静态分析工具。这一步就很轻松了。

class CodeAnalyzer:
    def visitors(self, ctx: AnalysisContext):
        yield LineLengthVisitor(ctx)
        yield ExceptionTypeVisitor(ctx)
        yield VariableUsageVisitor(ctx)
        yield PreferIsNotVisitor(ctx)

    def analysis(self, filename: str, code: str):
        self.ctx = AnalysisContext(filename)
        ast_root = ast.parse(code)
        for visitor in self.visitors(self.ctx):
            visitor.visit(ast_root)

    def print(self):
        for issue in self.ctx.issues:
            print(issue)

if __name__ == '__main__':
    analyzer = CodeAnalyzer()
    analyzer.analysis('test.py', CODE)
    analyzer.print()

CodeAnalyzer 使用所有支持的 NodeVisitor 来访问程序,并记录检查结果。如果以后实现了新的 visitor,只要简单地把它加入 visitors 集合即可。

总结

本文以四种典型的代码问题为例,演示了静态分析工具是如何通过遍历代码 AST 去查找问题的。相信读者在阅读本文后,举一反三,能够检测更多其他问题,或者从各个方面去完善上述程序。

但是在实现此程序的过程中,我们也意识到,Pythonast 模块是有一些限制的。尤其是它不包含空格、换行、注释等貌似冗余的信息,但这就使得部分代码风格的分析变得困难。与此同时,现实的静态分析工具很多时候要使用某种特殊格式的注释去调整静态分析的行为,而去掉了注释使得这种调整变得不可能。当然,从理论上讲,我们可以根据位置信息和源码的文本反推来获得一些额外的信息,但这显然是不合理的。由于 ast 模块主要是为执行程序而设计的,为了保证速度,在信息的完整性上的确有所欠缺。如果有更高级的要求,我们可以考虑采用其他第三方的实现,比如说,著名的静态检测工具 pylint 就附带了一个更加完整的 AST 分析库:astroid,有兴趣的同学可以去了解。

另一个问题是,本文所实现的各种 visitor 都是针对单个问题而实现的。这种设计固然让类的功能专一而内聚,但对于每种可能的问题都对整个 AST 执行遍历,显然容易引起性能上的问题。对于生产级别的工具而言,我们可能需要考虑把一些逻辑上类似或有关联的 Visitor 合并起来,让它能够通过单次遍历找到多个代码问题。当然,这也要我们首先编写出一定数量的 visitor,然后才能看到其中的规律。

如果读者觉得本文的实现还不够深入的话,也可以去参考真正具有现实价值的项目,包括本文开头部分曾经提到过的各种广泛使用的静态分析工具。好消息是,它们几乎都是开源的。即便读者并不打算自己去实现一个,相信通过本文也可以体会到:编写静态分析工具在原理上不见得有多复杂,主要难点在于实现上的繁琐,以及正确处理各种语法的变体。也能够体会到,在貌似简单的背后,各种编译器和开发辅助工具实际上完成了大量困难的工作,为开发者的日常工作带来了便利。我们应该深深感谢开发出这些工具的前辈们。

文章索引