莉娅·汉森是黑客学校的骄傲校友，喜欢帮助人们学习 Julia。她在 http://blog.leahhanson.us/ 上写博客，并在 @astrieanna 上发推文。
您可能熟悉一个花哨的 IDE，它会在代码中无法编译的部分下面画出红线。您可能已经对代码运行过 linter 来检查格式或样式问题。您可能会以超级挑剔的模式运行编译器，并开启所有警告。所有这些工具都是静态分析的应用。
静态分析是一种在不运行代码的情况下检查代码中问题的方法。“静态”是指在编译时而不是运行时，而“分析”是指我们正在分析代码。当您使用过我上面提到的工具时，您可能觉得这很神奇。但这些工具只是程序——它们是由人编写的源代码组成的，比如您这样的程序员。在本章中，我们将讨论如何实现一些静态分析检查。为了做到这一点，我们需要知道我们希望检查什么以及我们希望如何检查。
我们可以通过将过程描述为三个阶段，更具体地说明您需要了解的内容。
您应该能够用编程语言用户可以识别的术语解释您想要解决的总体问题。示例包括
虽然我们可以要求朋友完成上面列出的任务之一，但它们不够具体，无法向计算机解释。例如，要解决“拼写错误的变量名”，我们需要确定这里拼写错误是什么意思。一种选择是声称变量名应该由字典中的英文单词组成；另一种选择是查找只使用一次的变量（您误输入它的那一次）。
如果我们知道我们正在寻找只使用一次的变量，我们可以讨论变量使用类型（为其分配值与读取值），以及什么代码会或不会触发警告。
这涵盖了实际编写代码的行为，花费在阅读所用库文档上的时间，以及弄清楚如何获取编写分析所需的信息。这可能涉及读取代码文件，解析它以理解结构，然后对该结构进行特定检查。
我们将针对本章中实现的每个单独检查逐步完成这些步骤。步骤 1 需要对我们正在分析的语言有足够的了解，才能设身处地地体会到其用户面临的问题。本章中的所有代码都是 Julia 代码，用于分析 Julia 代码。
Julia 是一种面向技术计算的年轻语言。它于 2012 年春季发布了 0.1 版本；截至 2015 年初，它已经发布了 0.3 版本。总的来说，Julia 看起来很像 Python，但有一些可选的类型注释，没有面向对象的东西。大多数程序员会发现 Julia 中新颖的功能是多重分派，它对 API 设计和语言中的其他设计选择具有普遍的影响。
这是一段 Julia 代码片段
# A comment about increment
function increment(x::Int64)
return x + 1
end
increment(5)这段代码定义了函数 increment 的一个方法，该方法接受一个名为 x 的参数，类型为 Int64。该方法返回 x + 1 的值。然后，这个新定义的方法用值 5 调用；函数调用，正如您可能猜到的，将计算为 6。
Int64 是一种类型，其值是有符号整数，在内存中用 64 位表示；如果您的计算机具有 64 位处理器，它们就是您的硬件理解的整数。Julia 中的类型定义了数据在内存中的表示方式，此外还影响方法分派。
名称 increment 指的是一个泛型函数，它可能具有许多方法。我们刚刚定义了它的一种方法。在许多语言中，术语“函数”和“方法”可以互换使用；在 Julia 中，它们具有不同的含义。如果您仔细理解“函数”作为一个命名方法集合，其中“方法”是对特定类型签名的特定实现，本章将更有意义。
让我们定义 increment 函数的另一种方法
# Increment x by y
function increment(x::Int64, y::Number)
return x + y
end
increment(5) # => 6
increment(5,4) # => 9现在函数 increment 有两个方法。Julia 根据参数的数量和类型来决定为给定调用运行哪个方法；这称为动态多重分派
为了将其置于您可能已经知道的语言的上下文中，面向对象的语言使用单一分派，因为它们只考虑第一个参数。（在 x.foo(y) 中，第一个参数是 x。）
单一分派和多重分派都是基于参数的类型。上面的 x::Int64 只是一个用于分派的类型注释。在 Julia 的动态类型系统中，您可以在函数中将任何类型的赋值分配给 x，而不会出现错误。
我们还没有真正看到“多重”部分，但如果您对 Julia 感兴趣，您将不得不自己去查看它。我们需要继续进行我们的第一个检查。
与大多数编程语言一样，在 Julia 中编写速度非常快的代码需要了解计算机的工作原理以及 Julia 的工作原理。帮助编译器为您创建快速代码的重要部分是编写类型稳定的代码；这在 Julia 和 JavaScript 中很重要，并且在其他 JIT 语言中也很有用。当编译器可以看出代码段中的变量将始终包含相同的特定类型时，编译器可以进行比认为（正确与否）该变量有多种可能类型时更多的优化。您可以在 网上 阅读更多关于为什么类型稳定性（也称为“单态性”）对 JavaScript 很重要的内容。
让我们编写一个接受一个 Int64 并将其增加一定数量的函数。如果数字很小（小于 10），让我们将其增加一个大数（50），但如果数字很大，让我们只将其增加 0.5。
function increment(x::Int64)
if x < 10
x = x + 50
else
x = x + 0.5
end
return x
end这个函数看起来很简单，但 x 的类型是不稳定的。我选择了两个数字：50，一个 Int64，和 0.5，一个 Float64。根据 x 的值，它可能会添加到其中的任何一个。如果将像 22 这样的 Int64 添加到像 0.5 这样的 Float64，您将得到一个 Float64（22.5）。因为函数（x）中变量的类型可能会根据函数（x）参数的值而改变，所以这种 increment 的方法，特别是变量 x 是类型不稳定的。
Float64 是一种类型，它表示以 64 位存储的浮点值；在 C 中，它被称为 double。这是 64 位处理器理解的浮点类型之一。
与大多数效率问题一样，这个问题在循环中发生时更为突出。for 循环和 while 循环内部的代码会运行很多很多次，所以使其快速运行比加快只运行一次或两次的代码更重要。因此，我们的第一个检查是查找循环内部具有不稳定类型的变量。
首先，让我们看看我们想捕获的示例。我们将查看两个函数。它们都将 1 到 100 的数字求和，但不是求和整个数字，而是先将每个数字除以 2，然后再求和。这两个函数都将得到相同的答案（2525.0）；两者都将返回相同的类型（Float64）。但是，第一个函数 unstable 会出现类型不稳定，而第二个函数 stable 不会出现。
function unstable()
sum = 0
for i=1:100
sum += i/2
end
return sum
endfunction stable()
sum = 0.0
for i=1:100
sum += i/2
end
return sum
end这两个函数之间唯一的文本差异在于 sum 的初始化：sum = 0 与 sum = 0.0。在 Julia 中，0 是一个 Int64 字面量，而 0.0 是一个 Float64 字面量。这个微小的变化会造成多大的影响呢？
因为 Julia 是 Just-In-Time (JIT) 编译的，所以函数的第一次运行将比后续运行花费更长的时间。（第一次运行包括为这些参数类型编译函数所花费的时间。）当我们对函数进行基准测试时，我们必须确保在计时之前先运行它们一次（或预编译它们）。
julia> unstable()
2525.0
julia> stable()
2525.0
julia> @time unstable()
elapsed time: 9.517e-6 seconds (3248 bytes allocated)
2525.0
julia> @time stable()
elapsed time: 2.285e-6 seconds (64 bytes allocated)
2525.0@time 宏打印出函数运行花费的时间以及在运行时分配的字节数。分配的字节数每次需要新内存时都会增加；当垃圾收集器清除不再使用的内存时，它不会减少。这意味着分配的字节数与我们花费在分配和管理内存上的时间有关，但不意味着我们同时使用了所有这些内存。
如果我们想要获得 stable 与 unstable 的可靠数字，我们需要使循环更长，或者运行函数多次。但是，看起来 unstable 可能更慢。更有趣的是，我们可以看到分配的字节数存在很大差距；unstable 分配了大约 3 KB 的内存，而 stable 正在使用 64 字节。
由于我们可以看到 unstable 是多么简单，我们可能猜到这种分配发生在循环中。为了测试这一点，我们可以使循环更长，看看分配是否相应增加。让我们使循环从 1 到 10000，这比以前多 100 次迭代；我们希望分配的字节数也增加大约 100 倍，达到大约 300 KB。
function unstable()
sum = 0
for i=1:10000
sum += i/2
end
return sum
end由于我们重新定义了函数，我们需要运行它，以便在测量之前进行编译。我们预计从新的函数定义中得到一个不同的、更大的答案，因为它现在正在求和更多的数字。
julia> unstable()
2.50025e7
julia>@time unstable()
elapsed time: 0.000667613 seconds (320048 bytes allocated)
2.50025e7新的 unstable 分配了大约 320 KB，这是我们预计的结果，如果分配发生在循环中。为了解释这里发生的事情，我们将看看 Julia 在幕后是如何工作的。
unstable 和 stable 之间的这种差异是由于 unstable 中的 sum 必须装箱，而 stable 中的 sum 可以取消装箱。装箱值由一个类型标记和表示值的实际位组成；取消装箱值只有它们的实际位。但类型标记很小，所以这不是装箱值分配更多内存的原因。
差异来自编译器可以进行哪些优化。当一个变量具有具体、不可变的类型时，编译器可以在函数内部取消装箱。如果不是这种情况，那么该变量必须在堆上分配，并参与垃圾收集。不可变类型是 Julia 特有的概念。不可变类型的
不可变类型通常表示值而不是值集合的类型。例如，大多数数值类型，包括 `Int64` 和 `Float64`，都是不可变的。（Julia 中的数值类型是普通类型，而不是特殊的原始类型；您可以定义一个新的 `MyInt64`，它与提供的类型相同。）由于不可变类型不能被修改，因此每次您想要更改一个不可变类型时，都必须创建一个新副本。例如，`4 + 6` 必须创建一个新的 `Int64` 来保存结果。相比之下，可变类型的成员可以在原地更新；这意味着您不必为了进行更改而创建整个类型的副本。
`x = x + 2` 分配内存的想法可能听起来很奇怪；为什么要通过使 `Int64` 值不可变来使这种基本操作变慢？这就是编译器优化发挥作用的地方：使用不可变类型通常不会减慢速度。如果 `x` 具有稳定的、具体的类型（例如 `Int64`），那么编译器就可以自由地在堆栈上分配 `x` 并在原地修改 `x`。问题仅在于 `x` 具有不稳定的类型时（因此编译器不知道它的大小或类型）；一旦 `x` 被装箱并位于堆上，编译器就无法完全确定其他代码是否正在使用该值，因此无法编辑它。
因为 `stable` 中的 `sum` 具有具体的类型（`Float64`），所以编译器知道它可以在函数中本地存储未装箱的 `sum` 并修改其值；`sum` 不会在堆上分配，并且每次我们添加 `i/2` 时都不必创建新的副本。
因为 `unstable` 中的 `sum` 没有具体的类型，所以编译器在堆上分配了它。每次我们修改 `sum` 时，都会在堆上分配一个新值。所有这些在堆上分配值（并在每次我们想要读取 `sum` 的值时检索它们）所花费的时间都是昂贵的。
使用 `0` 与 `0.0` 是一个容易犯的错误，尤其是在您刚开始学习 Julia 时。自动检查循环中使用的变量是否类型稳定有助于程序员更深入地了解代码性能关键部分中变量的类型。
我们需要找出哪些变量在循环内使用，以及需要找到这些变量的类型。然后，我们需要决定如何以人类可读的格式打印它们。
我将首先解决最后一个问题，因为整个工作都取决于它。我们已经查看了一个不稳定的函数，并看到了程序员如何识别不稳定的变量，但我们需要程序来找到它们。这听起来需要模拟函数来查找可能更改值的变量——这听起来需要一些工作。幸运的是，Julia 的类型推断已经跟踪了函数的执行以确定类型。
`unstable` 中的 `sum` 的类型是 `Union(Float64,Int64)`。这是一个 `UnionType`，一种特殊的类型，表示变量可以保存一组类型的值中的任何一个。类型为 `Union(Float64,Int64)` 的变量可以保存类型为 `Int64` 或 `Float64` 的值；一个值只能具有一种类型。`UnionType` 连接任意数量的类型（例如，`UnionType(Float64, Int64, Int32)` 连接三种类型）。我们要寻找的是循环内部的 `UnionType` 变量。
将代码解析为有代表性的结构是一项复杂的工作，随着语言的发展变得更加复杂。在本章中，我们将依赖编译器使用的内部数据结构。这意味着我们不必担心读取文件或解析它们，但这确实意味着我们必须使用不受我们控制且有时感觉笨拙或丑陋的数据结构。
除了通过不自己解析代码而节省的所有工作之外，使用与编译器相同的数据结构意味着我们的检查将基于对编译器理解的准确评估——这意味着我们的检查将与代码的实际运行方式一致。
这个从 Julia 代码中检查 Julia 代码的过程称为内省。当您或我进行内省时，我们正在思考我们如何以及为什么思考和感受。当代码进行内省时，它会检查相同语言中代码的表示或执行属性（可能是它自己的代码）。当代码的内省扩展到修改被检查的代码时，它被称为元编程（编写或修改程序的程序）。
Julia 使内省变得容易。有四个内置函数可让我们查看编译器的想法：`code_lowered`、`code_typed`、`code_llvm` 和 `code_native`。这些函数按其输出来自编译过程的哪个步骤列出；第一个函数最接近我们输入的代码，最后一个函数最接近 CPU 运行的代码。在本章中，我们将重点关注 `code_typed`，它提供给我们优化的、类型推断的抽象语法树 (AST)。
`code_typed` 接受两个参数：感兴趣的函数和一个参数类型元组。例如，如果我们想要查看在用两个 `Int64` 调用函数 `foo` 时对应的 AST，那么我们将调用 `code_typed(foo, (Int64,Int64))`。
function foo(x,y)
z = x + y
return 2 * z
end
code_typed(foo,(Int64,Int64))这是 `code_typed` 将返回的结构
1-element Array{Any,1}:
:($(Expr(:lambda, {:x,:y}, {{:z},{{:x,Int64,0},{:y,Int64,0},{:z,Int64,18}},{}},
:(begin # none, line 2:
z = (top(box))(Int64,(top(add_int))(x::Int64,y::Int64))::Int64 # line 3:
return (top(box))(Int64,(top(mul_int))(2,z::Int64))::Int64
end::Int64))))这是一个 `Array`；这使 `code_typed` 可以返回多个匹配的方法。函数和参数类型的某些组合可能无法完全确定应该调用哪个方法。例如，您可以传递像 `Any`（而不是 `Int64`）这样的类型。`Any` 是类型层次结构顶部的类型；所有类型都是 `Any` 的子类型（包括 `Any`）。如果我们在参数类型的元组中包含 `Any`，并且有多个匹配的方法，那么来自 `code_typed` 的 `Array` 将包含多个元素；它将为每个匹配的方法包含一个元素。
让我们提取我们的示例 `Expr`，以便更容易地讨论。
julia> e = code_typed(foo,(Int64,Int64))[1]
:($(Expr(:lambda, {:x,:y}, {{:z},{{:x,Int64,0},{:y,Int64,0},{:z,Int64,18}},{}},
:(begin # none, line 2:
z = (top(box))(Int64,(top(add_int))(x::Int64,y::Int64))::Int64 # line 3:
return (top(box))(Int64,(top(mul_int))(2,z::Int64))::Int64
end::Int64))))我们感兴趣的结构在 `Array` 内部：它是一个 `Expr`。Julia 使用 `Expr`（表示表达式的缩写）来表示其 AST。（抽象语法树是编译器如何考虑代码的含义；这有点像您在小学时必须用图表的形式来表示句子。）我们返回的 `Expr` 表示一种方法。它有一些元数据（关于方法中出现的变量）以及构成方法主体的方法。
现在我们可以问 `e` 一些问题了。
我们可以使用 `names` 函数询问 `Expr` 具有哪些属性，该函数适用于任何 Julia 值或类型。它返回一个由该类型（或值的类型）定义的名称的 `Array`。
julia> names(e)
3-element Array{Symbol,1}:
:head
:args
:typ 我们刚刚询问 `e` 它有哪些名称，现在我们可以询问每个名称对应什么值。`Expr` 具有三个属性：`head`、`typ` 和 `args`。
julia> e.head
:lambda
julia> e.typ
Any
julia> e.args
3-element Array{Any,1}:
{:x,:y}
{{:z},{{:x,Int64,0},{:y,Int64,0},{:z,Int64,18}},{}}
:(begin # none, line 2:
z = (top(box))(Int64,(top(add_int))(x::Int64,y::Int64))::Int64 # line 3:
return (top(box))(Int64,(top(mul_int))(2,z::Int64))::Int64
end::Int64)我们刚刚看到了一些打印出来的值，但这并没有告诉我们太多关于它们的含义或如何使用它们的信息。
在表示方法的 `Expr` 中，`e.args` 中将有三个元素
julia> e.args[1] # names of arguments as symbols
2-element Array{Any,1}:
:x
:y符号是用于表示变量、常量、函数和模块名称的特殊类型。它们与字符串不同，因为它们专门表示程序结构的名称。
julia> e.args[2] # three lists of variable metadata
3-element Array{Any,1}:
{:z}
{{:x,Int64,0},{:y,Int64,0},{:z,Int64,18}}
{} 上面的第一个列表包含所有局部变量的名称；这里我们只有一个 (z)。第二个列表为方法中的每个变量和参数包含一个元组；每个元组都有变量名称、变量的推断类型和一个数字。该数字以机器友好的方式（而不是人类友好的方式）传达有关变量使用方式的信息。最后一个列表是捕获的变量名称；在本例中它为空。
julia> e.args[3] # the body of the method
:(begin # none, line 2:
z = (top(box))(Int64,(top(add_int))(x::Int64,y::Int64))::Int64 # line 3:
return (top(box))(Int64,(top(mul_int))(2,z::Int64))::Int64
end::Int64)前两个 `args` 元素是关于第三个元素的元数据。虽然元数据非常有趣，但现在并不需要。重要的是方法的主体，它是第三个元素。这是另一个 `Expr`。
julia> body = e.args[3]
:(begin # none, line 2:
z = (top(box))(Int64,(top(add_int))(x::Int64,y::Int64))::Int64 # line 3:
return (top(box))(Int64,(top(mul_int))(2,z::Int64))::Int64
end::Int64)
julia> body.head
:body这个 `Expr` 的 `head` 为 `:body`，因为它代表方法的主体。
julia> body.typ
Int64`typ` 是方法的推断返回类型。
julia> body.args
4-element Array{Any,1}:
:( # none, line 2:)
:(z = (top(box))(Int64,(top(add_int))(x::Int64,y::Int64))::Int64)
:( # line 3:)
:(return (top(box))(Int64,(top(mul_int))(2,z::Int64))::Int64) `args` 保存表达式列表：方法主体中的表达式列表。有一些行号注释（即 `:( # line 3:)`），但主体的大部分是设置 `z` 的值 (z = x + y) 和返回 `2 * z`。请注意，这些操作已被替换为 `Int64` 特定的内在函数。`top(function-name)` 表示一个内在函数；它是在 Julia 的代码生成中实现的，而不是在 Julia 中实现的。
我们还没有看到循环是什么样子，所以让我们试一试。
julia> function lloop(x)
for x = 1:100
x *= 2
end
end
lloop (generic function with 1 method)
julia> code_typed(lloop, (Int,))[1].args[3]
:(begin # none, line 2:
#s120 = $(Expr(:new, UnitRange{Int64}, 1, :(((top(getfield))(Intrinsics,
:select_value))((top(sle_int))(1,100)::Bool,100,(top(box))(Int64,(top(
sub_int))(1,1))::Int64)::Int64)))::UnitRange{Int64}
#s119 = (top(getfield))(#s120::UnitRange{Int64},:start)::Int64 unless
(top(box))(Bool,(top(not_int))(#s119::Int64 === (top(box))(Int64,(top(
add_int))((top(getfield))
(#s120::UnitRange{Int64},:stop)::Int64,1))::Int64::Bool))::Bool goto 1
2:
_var0 = #s119::Int64
_var1 = (top(box))(Int64,(top(add_int))(#s119::Int64,1))::Int64
x = _var0::Int64
#s119 = _var1::Int64 # line 3:
x = (top(box))(Int64,(top(mul_int))(x::Int64,2))::Int64
3:
unless (top(box))(Bool,(top(not_int))((top(box))(Bool,(top(not_int))
(#s119::Int64 === (top(box))(Int64,(top(add_int))((top(getfield))(
#s120::UnitRange{Int64},:stop)::Int64,1))::Int64::Bool))::Bool))::Bool
goto 2
1: 0:
return
end::Nothing)你会注意到主体中没有 for 循环或 while 循环。当编译器将代码从我们编写的代码转换为 CPU 理解的二进制指令时，对人类有用但 CPU 不理解的功能（如循环）将被删除。循环已被重写为 `label` 和 `goto` 表达式。`goto` 中有一个数字；每个 `label` 也都有一个数字。`goto` 跳到具有相同数字的 `label`。
我们将通过查找向后跳转的 `goto` 表达式来查找循环。
我们需要找到标签和 goto，并确定哪些匹配。我将首先向您提供完整的实现。在代码墙之后，我们将把它拆开并检查各个部分。
# This is a function for trying to detect loops in the body of a Method
# Returns lines that are inside one or more loops
function loopcontents(e::Expr)
b = body(e)
loops = Int[]
nesting = 0
lines = {}
for i in 1:length(b)
if typeof(b[i]) == LabelNode
l = b[i].label
jumpback = findnext(x-> (typeof(x) == GotoNode && x.label == l)
|| (Base.is_expr(x,:gotoifnot) && x.args[end] == l),
b, i)
if jumpback != 0
push!(loops,jumpback)
nesting += 1
end
end
if nesting > 0
push!(lines,(i,b[i]))
end
if typeof(b[i]) == GotoNode && in(i,loops)
splice!(loops,findfirst(loops,i))
nesting -= 1
end
end
lines
end现在开始分段解释
b = body(e)我们首先从方法主体中获取所有表达式，作为一个 `Array`。`body` 是我已经实现的一个函数
# Return the body of a Method.
# Takes an Expr representing a Method,
# returns Vector{Expr}.
function body(e::Expr)
return e.args[3].args
end然后
loops = Int[]
nesting = 0
lines = {}loops 是一个包含循环中 goto 语句所在行号的 Array。nesting 表示当前嵌套的循环层级。lines 是一个包含 (索引, Expr) 元组的 Array。
for i in 1:length(b)
if typeof(b[i]) == LabelNode
l = b[i].label
jumpback = findnext(
x-> (typeof(x) == GotoNode && x.label == l)
|| (Base.is_expr(x,:gotoifnot) && x.args[end] == l),
b, i)
if jumpback != 0
push!(loops,jumpback)
nesting += 1
end
end我们遍历 e 的主体中的每个表达式。如果它是一个标签，我们检查是否有 goto 语句跳转到这个标签（并且发生在当前索引之后）。如果 findnext 的结果大于零，则存在这样的 goto 节点，因此我们将它添加到 loops（我们当前所在的循环的 Array）中，并增加我们的 nesting 层级。
if nesting > 0
push!(lines,(i,b[i]))
end如果我们当前位于循环内部，我们将当前行推入要返回的行数组。
if typeof(b[i]) == GotoNode && in(i,loops)
splice!(loops,findfirst(loops,i))
nesting -= 1
end
end
lines
end如果我们位于 GotoNode，则检查它是否是循环的结尾。如果是，我们将从 loops 中删除条目并减少我们的嵌套层级。
此函数的结果是 lines 数组，一个包含 (索引, 值) 元组的数组。这意味着数组中的每个值都具有指向方法主体 Expr 的索引，以及该索引处的 value。lines 中的每个元素是在循环内部发生的表达式。
我们刚刚完成了 loopcontents 函数，它返回在循环内部的 Expr。我们的下一个函数将是 loosetypes，它接受一个 Expr 列表并返回一个松散类型变量的列表。稍后，我们将 loopcontents 的输出传递给 loosetypes。
在循环内部发生的每个表达式中，loosetypes 搜索符号及其关联类型的出现。变量使用显示为 AST 中的 SymbolNode；SymbolNode 包含变量的名称和推断类型。
我们不能仅仅检查 loopcontents 收集的每个表达式来查看它是否是 SymbolNode。问题是每个 Expr 可能包含一个或多个 Expr；每个 Expr 可能包含一个或多个 SymbolNode。这意味着我们需要提取任何嵌套的 Expr，以便我们可以在它们中的每一个中查找 SymbolNode。
# given `lr`, a Vector of expressions (Expr + literals, etc)
# try to find all occurrences of a variables in `lr`
# and determine their types
function loosetypes(lr::Vector)
symbols = SymbolNode[]
for (i,e) in lr
if typeof(e) == Expr
es = copy(e.args)
while !isempty(es)
e1 = pop!(es)
if typeof(e1) == Expr
append!(es,e1.args)
elseif typeof(e1) == SymbolNode
push!(symbols,e1)
end
end
end
end
loose_types = SymbolNode[]
for symnode in symbols
if !isleaftype(symnode.typ) && typeof(symnode.typ) == UnionType
push!(loose_types, symnode)
end
end
return loose_types
end symbols = SymbolNode[]
for (i,e) in lr
if typeof(e) == Expr
es = copy(e.args)
while !isempty(es)
e1 = pop!(es)
if typeof(e1) == Expr
append!(es,e1.args)
elseif typeof(e1) == SymbolNode
push!(symbols,e1)
end
end
end
endwhile 循环递归地遍历所有 Expr 的内部。每次循环找到 SymbolNode 时，它都会将它添加到向量 symbols 中。
loose_types = SymbolNode[]
for symnode in symbols
if !isleaftype(symnode.typ) && typeof(symnode.typ) == UnionType
push!(loose_types, symnode)
end
end
return loose_types
end现在我们有了变量及其类型的列表，所以很容易检查类型是否松散。loosetypes 通过查找一种特定的非具体类型，UnionType 来做到这一点。当我们认为所有非具体类型都“失败”时，我们获得了更多“失败”的结果。这是因为我们正在使用其带注释的参数类型评估每个方法，这些类型可能是抽象的。
现在我们可以在表达式上进行检查，我们应该使其更容易调用用户的代码。我们将创建两种调用 checklooptypes 的方式
在整个函数上；这将检查给定函数的每个方法。
在表达式上；如果用户自己提取了 code_typed 的结果，这将有效。
## for a given Function, run checklooptypes on each Method
function checklooptypes(f::Callable;kwargs...)
lrs = LoopResult[]
for e in code_typed(f)
lr = checklooptypes(e)
if length(lr.lines) > 0 push!(lrs,lr) end
end
LoopResults(f.env.name,lrs)
end
# for an Expr representing a Method,
# check that the type of each variable used in a loop
# has a concrete type
checklooptypes(e::Expr;kwargs...) =
LoopResult(MethodSignature(e),loosetypes(loopcontents(e)))我们可以看到这两个选项对于具有一个方法的函数的效果大致相同
julia> using TypeCheck
julia> function foo(x::Int)
s = 0
for i = 1:x
s += i/2
end
return s
end
foo (generic function with 1 method)
julia> checklooptypes(foo)
foo(Int64)::Union(Int64,Float64)
s::Union(Int64,Float64)
s::Union(Int64,Float64)
julia> checklooptypes(code_typed(foo,(Int,))[1])
(Int64)::Union(Int64,Float64)
s::Union(Int64,Float64)
s::Union(Int64,Float64)我在这里跳过了实现细节：我们是如何让结果打印到 REPL 上的？
首先，我创建了一些新的类型。LoopResults 是检查整个函数的结果；它包含函数名称和每个方法的结果。LoopResult 是检查一个方法的结果；它包含参数类型和松散类型的变量。
checklooptypes 函数返回一个 LoopResults。这种类型为其定义了一个名为 show 的函数。REPL 在它想要显示的值上调用 display；display 然后将调用我们的 show 实现。
这段代码对于使此静态分析可用非常重要，但它没有进行静态分析。您应该使用您实现语言中首选的方法来漂亮打印类型和输出；这只是在 Julia 中的实现方式。
type LoopResult
msig::MethodSignature
lines::Vector{SymbolNode}
LoopResult(ms::MethodSignature,ls::Vector{SymbolNode}) = new(ms,unique(ls))
end
function Base.show(io::IO, x::LoopResult)
display(x.msig)
for snode in x.lines
println(io,"\t",string(snode.name),"::",string(snode.typ))
end
end
type LoopResults
name::Symbol
methods::Vector{LoopResult}
end
function Base.show(io::IO, x::LoopResults)
for lr in x.methods
print(io,string(x.name))
display(lr)
end
end有时，当您在程序中输入时，您会误输入变量名。程序无法判断您是否希望这与您之前拼写正确的变量相同；它看到一个只使用一次的变量，而您可能看到一个拼写错误的变量名。需要变量声明的语言会自然地捕获这些拼写错误，但许多动态语言不需要声明，因此需要额外的分析层来捕获它们。
我们可以通过查找只使用一次或只使用一种方式的变量来查找拼写错误的变量名（和其他未使用的变量）。
以下是一小段代码示例，其中包含一个拼写错误的名称。
function foo(variable_name::Int)
sum = 0
for i=1:variable_name
sum += variable_name
end
variable_nme = sum
return variable_name
end这种错误可能会导致您的代码在运行时才发现的问题。假设您只将每个变量名拼写错误一次。我们可以将变量使用分为写入和读取。如果拼写错误是写入（即 worng = 5），则不会抛出错误；您只会将值静默地放入错误的变量中——这可能会令人沮丧地发现错误。如果拼写错误是读取（即 right = worng + 2），则在代码运行时会得到运行时错误；我们希望为此提供静态警告，以便您可以更早地发现此错误，但您仍然需要等到运行代码才能看到问题。
随着代码变得越来越长和复杂，就越难发现错误——除非您有静态分析的帮助。
另一种谈论“读取”和“写入”使用方式的方法是将它们称为“右侧”（RHS）和“左侧”（LHS）使用方式。这指的是变量相对于 = 符号的位置。
以下是一些 x 的使用方式
x = 2x = y + 22x = x + y + 2x += 2（它转换为 x = x + 2）y = x + 22x = x + y + 2x += 2（它转换为 x = x + 2）2 * xx注意，像 x = x + y + 2 和 x += 2 这样的表达式同时出现在这两个部分中，因为 x 出现在 = 符号的两侧。
我们需要查找两种情况
我们将查找所有变量使用，但我们将分别查找 LHS 和 RHS 使用，以涵盖这两种情况。
要出现在 LHS 上，变量需要有一个 = 符号在其左侧。这意味着我们可以在 AST 中查找 = 符号，然后查看其左侧以找到相关的变量。
在 AST 中，= 是一个带有头 :(=) 的 Expr。（括号是为了清楚地表明这是 = 的符号，而不是另一个运算符 :=。）args 中的第一个值将是其 LHS 上的变量名。因为我们正在查看编译器已经清理过的 AST，所以几乎总是只有一个符号位于我们的 = 符号的左侧。
让我们看看代码中的含义
julia> :(x = 5)
:(x = 5)
julia> :(x = 5).head
:(=)
julia> :(x = 5).args
2-element Array{Any,1}:
:x
5
julia> :(x = 5).args[1]
:x以下是完整的实现，后面是解释。
# Return a list of all variables used on the left-hand-side of assignment (=)
#
# Arguments:
# e: an Expr representing a Method, as from code_typed
#
# Returns:
# a Set{Symbol}, where each element appears on the LHS of an assignment in e.
#
function find_lhs_variables(e::Expr)
output = Set{Symbol}()
for ex in body(e)
if Base.is_expr(ex,:(=))
push!(output,ex.args[1])
end
end
return output
end output = Set{Symbol}()我们有一组 Symbols；这些是我们已在 LHS 上找到的变量名。
for ex in body(e)
if Base.is_expr(ex,:(=))
push!(output,ex.args[1])
end
end我们没有深入挖掘表达式，因为 code_typed AST 非常扁平；循环和 if 语句已被转换为带有 goto 的扁平语句来进行控制流。在函数调用的参数内部不会有任何赋值。如果在等号左侧有超过一个符号，则此代码将失败。这错过了两个特定的边缘情况：数组访问（例如 a[5]，它将表示为 :ref 表达式）和属性（例如 a.head，它将表示为 :. 表达式）。这些仍然总是将相关符号作为其 args 中的第一个值，它可能只是被掩盖了一点（如 a.property.name.head.other_property）。这段代码没有处理这些情况，但是 if 语句内部的几行代码可以解决这个问题。
push!(output,ex.args[1])当我们找到一个 LHS 变量使用时，我们将变量名 push! 到 Set 中。Set 将确保我们每个名称只有一个副本。
要查找所有其他变量使用，我们还需要查看每个 Expr。这有点复杂，因为我们基本上关心所有 Expr，而不仅仅是 :(=)，而且我们必须深入嵌套的 Expr（以处理嵌套的函数调用）。
以下是完整的实现，后面是解释。
# Given an Expression, finds variables used in it (on right-hand-side)
#
# Arguments: e: an Expr
#
# Returns: a Set{Symbol}, where each e is used in a rhs expression in e
#
function find_rhs_variables(e::Expr)
output = Set{Symbol}()
if e.head == :lambda
for ex in body(e)
union!(output,find_rhs_variables(ex))
end
elseif e.head == :(=)
for ex in e.args[2:end] # skip lhs
union!(output,find_rhs_variables(ex))
end
elseif e.head == :return
output = find_rhs_variables(e.args[1])
elseif e.head == :call
start = 2 # skip function name
e.args[1] == TopNode(:box) && (start = 3) # skip type name
for ex in e.args[start:end]
union!(output,find_rhs_variables(ex))
end
elseif e.head == :if
for ex in e.args # want to check condition, too
union!(output,find_rhs_variables(ex))
end
elseif e.head == :(::)
output = find_rhs_variables(e.args[1])
end
return output
end此函数的主要结构是一个大型 if-else 语句，其中每种情况都处理一个不同的头符号。
output = Set{Symbol}()output 是变量名称的集合，我们将在函数结束时返回它。由于我们只关心这些变量中的每一个至少被读取过一次这一事实，使用 Set 使我们不必担心每个名称的唯一性。
if e.head == :lambda
for ex in body(e)
union!(output,find_rhs_variables(ex))
end这是 if-else 语句中的第一个条件。:lambda 表示函数体。我们对定义的主体进行递归，这应该会获得定义中的所有 RHS 变量使用。
elseif e.head == :(=)
for ex in e.args[2:end] # skip lhs
union!(output,find_rhs_variables(ex))
end如果头是 :(=)，则表达式是赋值。我们跳过 args 的第一个元素，因为那是被赋值的变量。对于剩下的每个表达式，我们递归地找到 RHS 变量并将它们添加到我们的集合中。
elseif e.head == :return
output = find_rhs_variables(e.args[1])如果这是一个返回语句，则 args 的第一个元素是返回值的表达式；我们将添加其中的任何变量到我们的集合中。
elseif e.head == :call
# skip function name
for ex in e.args[2:end]
union!(output,find_rhs_variables(ex))
end对于函数调用，我们想要获取调用中所有参数中使用的所有变量。我们跳过函数名，它是 args 的第一个元素。
elseif e.head == :if
for ex in e.args # want to check condition, too
union!(output,find_rhs_variables(ex))
end表示 if 语句的 Expr 具有 head 值 :if。我们想要从 if 语句体中的所有表达式中获取变量使用，因此我们在 args 的每个元素上进行递归。
elseif e.head == :(::)
output = find_rhs_variables(e.args[1])
end:(::) 运算符用于添加类型注释。第一个参数是被注释的表达式或变量；我们检查注释表达式中的变量使用。
return output在函数结束时，我们返回 RHS 变量使用的集合。
还有更多代码简化了上面的方法。因为上面的版本只处理 Expr，但递归传递的一些值可能不是 Expr，所以我们需要一些方法来适当地处理其他可能的类型。
# Recursive Base Cases, to simplify control flow in the Expr version
find_rhs_variables(a) = Set{Symbol}() # unhandled, should be immediate val e.g. Int
find_rhs_variables(s::Symbol) = Set{Symbol}([s])
find_rhs_variables(s::SymbolNode) = Set{Symbol}([s.name])现在我们已经定义了上面的两个函数，我们可以将它们一起使用来查找仅从其读取或仅写入的变量。查找它们的函数将被称为 unused_locals。
function unused_locals(e::Expr)
lhs = find_lhs_variables(e)
rhs = find_rhs_variables(e)
setdiff(lhs,rhs)
endunused_locals 将返回一个变量名称集合。很容易编写一个函数来确定 unused_locals 的输出是否算作“通过”。如果集合为空，则方法通过。如果函数的所有方法都通过，则函数通过。以下的 check_locals 函数实现了此逻辑。
check_locals(f::Callable) = all([check_locals(e) for e in code_typed(f)])
check_locals(e::Expr) = isempty(unused_locals(e))我们对 Julia 代码进行了两种静态分析 - 一种基于类型，另一种基于变量使用情况。
静态类型语言已经完成了我们基于类型分析的工作；额外的基于类型的静态分析主要在动态类型语言中才有用。一些（主要是研究）项目已经构建了静态类型推断系统，用于包括 Python、Ruby 和 Lisp 在内的语言。这些系统通常围绕可选类型注释构建；您可以根据需要使用静态类型，在不需要时则回退到动态类型。这对于将一些静态类型集成到现有代码库中特别有用。
非基于类型的检查，例如我们的变量使用检查，适用于动态类型和静态类型语言。但是，许多静态类型语言，如 C++ 和 Java，要求您声明变量，并且已经提供了像我们创建的警告一样的基本警告。仍然可以编写自定义检查；例如，特定于您的项目样式指南的检查或基于安全策略的额外安全措施。
虽然 Julia 拥有强大的工具来启用静态分析，但它并非孤军奋战。Lisp 当然以代码是嵌套列表的数据结构而闻名，因此它往往很容易获取 AST。Java 也公开其 AST，尽管 AST 比 Lisp 的要复杂得多。某些语言或语言工具链的设计不允许普通用户窥视内部表示。对于开源工具链（尤其是注释良好的工具链），一个选择是在环境中添加钩子，让您可以访问 AST。
在无法使用上述方法的情况下，最终的解决方法是自己编写一个解析器；尽可能避免这样做。要涵盖大多数编程语言的完整语法，需要花费大量工作，而且您必须在语言添加新功能时自己更新它（而不是从上游自动获取更新）。根据您要执行的检查，您可能只需解析某些行或语言功能的子集，这将大大降低编写解析器的成本。
希望您对静态分析工具编写方式的全新理解，能够帮助您理解您在代码中使用的工具，或许还能激发您编写自己的工具。