500 lines or less 是對(duì)開(kāi)源程序架構(gòu)中一些典型過(guò)程進(jìn)行講解的系列文章，github英文項(xiàng)目地址：https://github.com/aosabook/500lines。在看的過(guò)程中發(fā)現(xiàn)github上已有中文翻譯項(xiàng)目
，項(xiàng)目中還沒(méi)有 static analysis 一文的翻譯，因此嘗試了一下（已PR翻譯項(xiàng)目），不足之處還請(qǐng)不吝指教。

標(biāo)題：靜態(tài)分析
作者：Leah Hanson

Leah Hanson是令Hacker School感到自豪的校友，而且喜歡幫助人們了解Julia語(yǔ)言。她的博客：http://blog.leahhanson.us/，以及推特：@astrieanna。

介紹

你可能對(duì)一些精致的IDE感到熟悉，它們會(huì)將你無(wú)法編譯的部分代碼劃上紅色下劃線(xiàn)。你可能在你的代碼上運(yùn)行了一個(gè)代碼檢查工具來(lái)檢查格式或樣式問(wèn)題。你可能在打開(kāi)了所有警告，在超級(jí)挑剔的模式下運(yùn)行著編譯器。所有這些工具都應(yīng)用了靜態(tài)分析。

靜態(tài)分析是一種在不運(yùn)行代碼的情況下檢查其中問(wèn)題的方法。 “靜態(tài)”的意思是在編譯時(shí)而非運(yùn)行時(shí)，“分析”則意味著我們正在分析代碼。當(dāng)你使用我上面提到的工具時(shí)，它可能感覺(jué)像是魔術(shù)。但這些工具只是程序——它們是由一個(gè)人（像你這樣的程序員）編寫(xiě)的源代碼構(gòu)成的。在這個(gè)章節(jié)中，我們將討論如何實(shí)現(xiàn)一些靜態(tài)分析檢查。為了做到這一點(diǎn)，我們需要知道我們希望通過(guò)檢查實(shí)現(xiàn)什么，以及我們要怎樣完成檢查。

通過(guò)將所有流程分三個(gè)階段陳述，我們可以更加具體地了解你需要了解的內(nèi)容：

1. 決定你要檢查的內(nèi)容。

你要能用讓該編程語(yǔ)言的用戶(hù)能夠識(shí)別的方式，解釋你想要解決的一般問(wèn)題。例子包括：

• 找出拼寫(xiě)錯(cuò)誤的變量名稱(chēng)
• 找出在并行代碼中存在的競(jìng)爭(zhēng)
• 找出對(duì)未實(shí)現(xiàn)的函數(shù)的調(diào)用

2. 決定具體如何去檢查。

雖然我們可以要求一個(gè)朋友完成上面列出的任務(wù)之一，但他們?nèi)詿o(wú)法向計(jì)算機(jī)解釋得足夠清楚。例如，要解決“找出拼寫(xiě)錯(cuò)誤的變量名稱(chēng)”這個(gè)問(wèn)題時(shí)，我們需要定義“拼寫(xiě)錯(cuò)誤”在此處的含義。一種辦法是提倡變量名應(yīng)該由字典中的英文單詞組成；另一個(gè)辦法是查找僅使用過(guò)一次的變量（就是你輸錯(cuò)的那一次）。

如果我們知道我們正在尋找僅使用過(guò)一次的變量，我們可以討論各種變量用法（將其值分配或讀?。┮约澳男┐a會(huì)、或不會(huì)觸發(fā)警告。

3. 實(shí)施細(xì)節(jié)。

這包括真正去編寫(xiě)代碼的行為，閱讀你所使用的庫(kù)的文檔所花費(fèi)的時(shí)間，以及弄清楚如何獲取你所需的信息來(lái)編寫(xiě)分析。這可能涉及讀取代碼文件，解析代碼以理解結(jié)構(gòu)，然后對(duì)該結(jié)構(gòu)進(jìn)行特定的檢查。

對(duì)于本章中實(shí)施的每項(xiàng)檢查，我們將逐項(xiàng)完成這些步驟。第1步需要充分了解我們正在分析的語(yǔ)言，以理解其用戶(hù)所面臨的問(wèn)題。本章將全部使用Julia代碼編寫(xiě)，同時(shí)也用來(lái)分析Julia代碼。

Julia語(yǔ)言簡(jiǎn)介

Julia是一門(mén)針對(duì)技術(shù)計(jì)算的年輕語(yǔ)言。它于2012年春季發(fā)布于0.1版；截至2015年初，它的版本號(hào)已經(jīng)升到了0.3。一般來(lái)說(shuō)，Julia看起來(lái)很像Python，但多了一些可選的類(lèi)型注釋?zhuān)彝耆珱](méi)有任何面向?qū)ο蟮臇|西。大多數(shù)程序員會(huì)對(duì)Julia的多次調(diào)度特性感到新奇，這對(duì)API設(shè)計(jì)和語(yǔ)言中的其他設(shè)計(jì)選擇都有著普遍的影響。

這是Julia代碼的片段：

# 關(guān)于increment的一段注釋
function increment(x::Int64)
  return x + 1
end

increment(5)

這段代碼定義了increment函數(shù)的一個(gè)方法，該方法接受一個(gè)名為x、類(lèi)型為Int64的參數(shù)。該方法返回x + 1的值。接著，使用參數(shù)5去調(diào)用這個(gè)剛剛定義的方法；正如你可能已經(jīng)猜到的那樣，這次函數(shù)調(diào)用求得了6 。

Int64是在內(nèi)存中以64位表示的帶符號(hào)的整數(shù)類(lèi)型；如果你的計(jì)算機(jī)具有64位處理器，那么它們是你的硬件能夠理解的整數(shù)。除了影響方法調(diào)度之外，Julia中的類(lèi)型定義了數(shù)據(jù)在內(nèi)存中表示形式。

名稱(chēng)increment指的是一個(gè)一般函數(shù)，這個(gè)函數(shù)可能有許多方法。我們剛剛為它定義了一種方法。在許多語(yǔ)言中，術(shù)語(yǔ)“函數(shù)”和“方法”可互換指代；但在Julia里，他們有不同的含義。如果你細(xì)心地將“函數(shù)”理解為一個(gè)眾多方法的命名集合，其中“方法”是特定類(lèi)型簽名的特定實(shí)現(xiàn)，那么本章將更好理解。

讓我們定義increment函數(shù)的另一個(gè)方法：

# 使x增加y
function increment(x::Int64, y::Number)
  return x + y
end

increment(5) # =\> 6
increment(5,4) # =\> 9

現(xiàn)在函數(shù)increment有了兩種方法。Julia根據(jù)參數(shù)的數(shù)量和類(lèi)型決定為指定的調(diào)用運(yùn)行哪個(gè)方法；這稱(chēng)為動(dòng)態(tài)多次調(diào)度 ：

• 動(dòng)態(tài)是指它基于運(yùn)行時(shí)使用的值的類(lèi)型。
• 多次是指它查看所有參數(shù)的類(lèi)型和順序。
• 調(diào)度是指這是一種將函數(shù)調(diào)用和方法定義匹配起來(lái)的辦法。

用你可能已經(jīng)了解的語(yǔ)言環(huán)境來(lái)舉例，面向?qū)ο笳Z(yǔ)言使用單次調(diào)度，因?yàn)樗鼈冎豢紤]第一個(gè)參數(shù)。（在x.foo(y)中 ，第一個(gè)參數(shù)是x 。）

單次和多次調(diào)度都基于參數(shù)的類(lèi)型。上面的x::Int64是一個(gè)純粹用于調(diào)度的類(lèi)型注釋。在Julia的動(dòng)態(tài)類(lèi)型系統(tǒng)中，你可以在函數(shù)中為x分配任何類(lèi)型的值而不會(huì)出錯(cuò)。

我們還沒(méi)有真正看到“多次”的部分，但如果你對(duì)Julia很好奇，你就必須得自己查查看了。我們要繼續(xù)我們的第一個(gè)檢查了。

檢查循環(huán)中的變量類(lèi)型

與大多數(shù)編程語(yǔ)言一樣，在Julia中編寫(xiě)非?？焖俚拇a需要了解計(jì)算機(jī)和Julia的工作原理。幫助編譯器為你創(chuàng)建快速代碼的一個(gè)重要部分是編寫(xiě)類(lèi)型穩(wěn)定的代碼；這在Julia和JavaScript中很重要，在其他JIT的語(yǔ)言中也很有用。相對(duì)于編譯器認(rèn)為某個(gè)變量存在多種可能的類(lèi)型（無(wú)論正確與否）的情況，當(dāng)編譯器明白代碼段中的某個(gè)變量將始終包含相同的特定類(lèi)型時(shí)，編譯器可以完成更多優(yōu)化工作。有關(guān)為什么類(lèi)型穩(wěn)定性（也稱(chēng)為“單態(tài)”）對(duì)于JavaScript重要的原因，你可以 在線(xiàn)閱讀，了解更多。

為什么這很重要

讓我們編寫(xiě)一個(gè)函數(shù)，它接受Int64并將其增大一些。如果數(shù)字比較小（小于10），我們將它加上一個(gè)大數(shù)字（50），但如果數(shù)字很大，那么我們只增加0.5。

function increment(x::Int64)
  if x < 10
    x = x + 50
  else
    x = x + 0.5
  end
  return x
end

這個(gè)函數(shù)看起來(lái)非常簡(jiǎn)單，但x的類(lèi)型是不穩(wěn)定的。我選擇了兩個(gè)數(shù)字：一個(gè)Int64 類(lèi)型：50，和一個(gè)Float64 類(lèi)型：0.5。取決于x的值，它可能會(huì)和兩者中的任何一個(gè)相加。如果你將例如22的Int64和例如0.5這樣的Float64相加 ，你會(huì)得到一個(gè)Float64類(lèi)型數(shù)據(jù)（22.5）。因?yàn)楹瘮?shù)(x )的變量類(lèi)型會(huì)根據(jù)傳給函數(shù)(x )的參數(shù)變化，increment的這一方法，尤其是變量x，是類(lèi)型不穩(wěn)定的。

Float64是一種表示以64位存儲(chǔ)的浮點(diǎn)值的類(lèi)型;在C語(yǔ)言中，它被稱(chēng)為雙精度浮點(diǎn)型（double） 。這是64位處理器理解的浮點(diǎn)類(lèi)型之一。

與大多數(shù)效率問(wèn)題一樣，這個(gè)問(wèn)題在循環(huán)中發(fā)生時(shí)將更加明顯。for和while循環(huán)中的代碼會(huì)運(yùn)行很多、很多次，所以讓循環(huán)快速運(yùn)行，要比讓僅運(yùn)行一兩次的代碼加快速度更加重要。因此，我們的第一個(gè)檢查是查找循環(huán)中具有不穩(wěn)定類(lèi)型的變量。

首先，讓我們看一下我們想要捕捉的例子。我們將查看兩個(gè)函數(shù)。兩個(gè)函數(shù)都從1加到100，但是它們不是對(duì)整數(shù)進(jìn)行求和，而是在求和之前先將每個(gè)數(shù)除以2。兩個(gè)函數(shù)都會(huì)得到相同的答案（2525.0）；兩者都將返回相同的類(lèi)型（ Float64 ）。然而，第一個(gè)函數(shù)：unstable ，受到類(lèi)型不穩(wěn)定的影響，而第二個(gè)函數(shù)： stable ，則不會(huì)。

function unstable()
  sum = 0
  for i=1:100
    sum += i/2
  end
  return sum
end

function stable()
  sum = 0.0
  for i=1:100
    sum += i/2
  end
  return sum
end

兩個(gè)函數(shù)之間唯一字面上的差異在于sum的初始化： sum = 0和sum = 0.0 。在Julia中，從字面上來(lái)說(shuō)， 0是Int64類(lèi)型， 而0.0則是Float64類(lèi)型。這個(gè)微小的變化能造成多大差別？

由于Julia是實(shí)時(shí)（JIT）編譯的，因此第一次運(yùn)行函數(shù)所需的時(shí)間比該函數(shù)后續(xù)運(yùn)行的時(shí)間長(zhǎng)。（第一次運(yùn)行包括為這些參數(shù)類(lèi)型編譯函數(shù)所花費(fèi)的時(shí)間。）當(dāng)我們對(duì)函數(shù)進(jìn)行基準(zhǔn)測(cè)試時(shí)，我們必須確保在對(duì)它們進(jìn)行計(jì)時(shí)之前先運(yùn)行它們一次（或者把它們預(yù)編譯好）。

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宏打印出函數(shù)運(yùn)行的時(shí)間以及運(yùn)行時(shí)分配的字節(jié)數(shù)。每次需要新內(nèi)存時(shí)，分配的字節(jié)數(shù)就會(huì)增加；即便垃圾回收機(jī)制清理不再使用的內(nèi)存時(shí)，它也不會(huì)減少。也就是說(shuō)，分配的字節(jié)數(shù)與我們分配和管理內(nèi)存所花費(fèi)的時(shí)間有關(guān)，并不表示我們?cè)谕粫r(shí)刻使用了所有這些內(nèi)存。

如果我們想要獲得關(guān)于stable與unstable更有力的對(duì)比數(shù)據(jù)，我們需要更長(zhǎng)的循環(huán)或更多次地運(yùn)行函數(shù)。然而，看起來(lái)unstable可能更慢。更有趣的是，我們可以發(fā)現(xiàn)分配的字節(jié)數(shù)有很大差距;。unstable分配了大約3 KB的內(nèi)存，而stable僅使用64字節(jié)。

既然我們明白unstable是多么簡(jiǎn)單，我們會(huì)去猜想這種分配是在循環(huán)中發(fā)生的。為了測(cè)試這一點(diǎn)，我們可以使循環(huán)更長(zhǎng)，并查看分配是否相應(yīng)地增加。把循環(huán)改成從1到10000，是原先迭代次數(shù)的100倍。我們所期望看到的是分配的字節(jié)數(shù)也增加約100倍，達(dá)到約300 KB。

function unstable()
  sum = 0
  for i=1:10000
    sum += i/2
  end
  return sum
end

由于我們重新定義了函數(shù)，因此我們需要運(yùn)行它，使其在測(cè)量之前完成編譯。我們期望從新的函數(shù)定義中得到一個(gè)不同的、更大的答案，因?yàn)樗F(xiàn)在對(duì)更多的數(shù)字進(jìn)行了求和運(yùn)算。

julia> unstable()
2.50025e7

julia>@time unstable()
elapsed time: 0.000667613 seconds (320048 bytes allocated)
2.50025e7

新的unstable分配了大約320 KB內(nèi)存，這符合我們對(duì)于“內(nèi)存分配在循環(huán)中發(fā)生”這一期望。為了解釋這里發(fā)生了什么，我們將看看Julia在幕后是如何工作的。

unstable和stable之間的差異是因?yàn)?code>unstable的sum必須進(jìn)行裝箱轉(zhuǎn)換，而stable中的sum可以不必如此。裝箱值由類(lèi)型標(biāo)簽和表示該值的實(shí)際比特位組成；而拆箱值只含有實(shí)際比特位。但是類(lèi)型標(biāo)簽很小，所以這不是裝箱值分配更多內(nèi)存的原因。

真正的差異來(lái)自編譯器可以進(jìn)行的優(yōu)化。當(dāng)變量具有具體的、不可變類(lèi)型時(shí)，編譯器可以在函數(shù)內(nèi)將它拆箱。如果不是這種情況，則必須在堆上分配變量，并參與垃圾回收。不可變類(lèi)型是Julia特有的概念。不可變類(lèi)型的值無(wú)法更改。

不可變類(lèi)型通常是表示值的類(lèi)型，而不是值的集合。例如，大多數(shù)數(shù)字類(lèi)型（包括Int64和Float64 ）都是不可變的。（Julia中的數(shù)字類(lèi)型是普通類(lèi)型，而不是特殊的原始類(lèi)型。你可以定義一個(gè)與Julia所提供的類(lèi)型相同的新的MyInt64 。）由于無(wú)法修改不可變類(lèi)型，因此每次當(dāng)你想要更改時(shí)都必須創(chuàng)建一個(gè)新的副本。例如， 4 + 6必須創(chuàng)建一個(gè)新的Int64來(lái)保存結(jié)果。反之，可變類(lèi)型的成員可以就地（in-place）更新。這意味著你不必在修改過(guò)程中做一次完整的復(fù)制。

用x = x + 2來(lái)分配內(nèi)存的想法可能聽(tīng)起來(lái)很奇怪。為什么你要使Int64值不可變，從而導(dǎo)致這樣的基本操作變慢？這就是那些編譯器優(yōu)化的用武之地：使用不可變類(lèi)型（通常）不會(huì)使它變慢。如果x具有穩(wěn)定的具體類(lèi)型（例如Int64 ），則編譯器可以自由地在堆棧上分配x，并就地變換x 。問(wèn)題是當(dāng)x具有不穩(wěn)定類(lèi)型時(shí)（因此編譯器對(duì)它的大小或類(lèi)型一無(wú)所知），一旦x被裝箱并且在堆上，編譯器就不能完全確定有沒(méi)有其他代碼使用該值，因此無(wú)法編輯它。

因?yàn)?code>stable中的sum有具體類(lèi)型（ Float64 ），編譯器知道它可以在函數(shù)本地拆箱存儲(chǔ)它并改變其值。這里的sum不會(huì)被分配到堆上，并且每次添加i/2時(shí)都不需要?jiǎng)?chuàng)建新副本。

因?yàn)?code>unstable中的sum沒(méi)有具體類(lèi)型，所以編譯器會(huì)在堆上分配它。每次我們修改sum時(shí)，我們?cè)诙焉隙挤峙淞艘粋€(gè)新值。所有這些在堆上分配值（以及每次我們想要讀取sum的值時(shí)進(jìn)行的檢索）所花費(fèi)的時(shí)間都是寶貴的。

使用0而不是0.0是一個(gè)容易犯的錯(cuò)誤，尤其是當(dāng)你剛接觸Julia時(shí)。自動(dòng)檢查循環(huán)中使用的變量是否是類(lèi)型穩(wěn)定的，有助于程序員更深入理解他們的代碼性能關(guān)鍵（performance-critical）部分中的變量類(lèi)型。

實(shí)施細(xì)節(jié)

我們需要找出循環(huán)中使用的變量，并且識(shí)別這些變量的類(lèi)型。然后我們需要決定如何以人類(lèi)可讀的格式打印它們。

• 我們?nèi)绾握业窖h(huán)？
• 我們?nèi)绾卧谘h(huán)中找到變量？
• 我們?nèi)绾巫R(shí)別變量的類(lèi)型？
• 我們?nèi)绾未蛴〗Y(jié)果？
• 我們?nèi)绾闻袛囝?lèi)型是否不穩(wěn)定？

我將首先解決最后一個(gè)問(wèn)題，因?yàn)檎麄€(gè)嘗試是否成功都取決于它。我們已經(jīng)研究了一個(gè)不穩(wěn)定的函數(shù)，作為程序員，也看到了如何識(shí)別不穩(wěn)定的變量，但是我們需要程序去找到它們。這聽(tīng)起來(lái)像是需要通過(guò)模擬函數(shù)來(lái)查找值可能會(huì)發(fā)生變化的變量——聽(tīng)起來(lái)需要好些工作。對(duì)我們來(lái)說(shuō)幸運(yùn)的是，Julia的類(lèi)型推斷已經(jīng)通過(guò)跟蹤函數(shù)執(zhí)行完成了類(lèi)型檢測(cè)。

unstable中的sum的類(lèi)型是Union(Float64,Int64) 。這是一種UnionType，是一種特殊類(lèi)型。這種類(lèi)型的變量可以保存一組類(lèi)型值中的任一類(lèi)型值。比如Union(Float64,Int64)類(lèi)型的變量既可以保存Int64，也可以保存Float64類(lèi)型的值，但這個(gè)值只能是其中一種。UnionType可以連接任意數(shù)量的類(lèi)型（例如，UnionType(Float64, Int64, Int32)連接了三種類(lèi)型）。我們要在循環(huán)中查找UnionType 類(lèi)型的變量。

將代碼解析為代表性結(jié)構(gòu)是一項(xiàng)復(fù)雜的業(yè)務(wù)，并且它隨著語(yǔ)言的發(fā)展變得越來(lái)越復(fù)雜。在本章中，我們將依賴(lài)于編譯器使用的內(nèi)部數(shù)據(jù)結(jié)構(gòu)。這意味著我們不必?fù)?dān)心讀取文件或解析它們，但它確實(shí)意味著我們必須和一些不受我們控制、有時(shí)感覺(jué)笨拙或丑陋的數(shù)據(jù)結(jié)構(gòu)打交道。

除去因無(wú)需自己解析代碼所節(jié)省下來(lái)的所有工作，使用與編譯器相同的數(shù)據(jù)結(jié)構(gòu)意味著我們的檢查將是基于一種編譯器理解的準(zhǔn)確評(píng)估——這意味著我們的檢查將與代碼實(shí)際運(yùn)行的方式保持一致。

從Julia代碼中檢查Julia代碼的過(guò)程稱(chēng)為自?。╥ntrospection）。當(dāng)你我自省時(shí)，我們思考的正是我們思考和感受的方式和原因。當(dāng)代碼自省時(shí)，它會(huì)檢查相同語(yǔ)言（可能是自己的代碼）的代碼的表達(dá)或執(zhí)行屬性。當(dāng)代碼的自省擴(kuò)展到修改被檢查的代碼時(shí)，它被稱(chēng)為元編程（編寫(xiě)或修改程序的程序）。

Julia的自省

Julia的自省很簡(jiǎn)單。它有四個(gè)內(nèi)置函數(shù)，能讓我們看到編譯器在想什么： code_lowered ， code_typed ， code_llvm和code_native 。編譯過(guò)程中哪個(gè)步驟越先有輸出，哪個(gè)函數(shù)就越排在前面。第一個(gè)函數(shù)最接近我們輸入的代碼，而最后一個(gè)最接近CPU運(yùn)行的代碼。在本章中，我們將重點(diǎn)關(guān)注code_typed ，它為我們提供了優(yōu)化的，類(lèi)型推斷的抽象語(yǔ)法樹(shù)（AST）。

code_typed需要兩個(gè)參數(shù)：感興趣的函數(shù)和一個(gè)參數(shù)類(lèi)型的元組。例如，如果我們想在使用兩個(gè)Int64參數(shù)調(diào)用函數(shù)foo時(shí)觀(guān)察它的AST，那么我們將調(diào)用code_typed(foo, (Int64,Int64)) 。

function foo(x,y)
  z = x + y
  return 2 * z
end

code_typed(foo,(Int64,Int64))

這是code_typed將會(huì)返回的結(jié)構(gòu)：

    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))))

這是一個(gè)Array，它允許code_typed返回多個(gè)匹配方法。函數(shù)和參數(shù)類(lèi)型的某些組合可能無(wú)法完全確定應(yīng)調(diào)用哪個(gè)方法。例如，你可以傳入類(lèi)似Any的類(lèi)型（而不是Int64 ）。Any是類(lèi)型層次結(jié)構(gòu)的頂部類(lèi)型。所有類(lèi)型都是Any （包括Any）的子類(lèi)型。如果我們?cè)趨?shù)類(lèi)型的元組中包含Any ，并且有多個(gè)匹配方法，那么code_typed的Array將包含多個(gè)元素，每個(gè)匹配方法都會(huì)有一個(gè)元素。

為了方便討論，讓我們將Expr的例子單獨(dú)拉出來(lái)。

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))))

我們感興趣的結(jié)構(gòu)在Array之中：它是一個(gè)Expr 。Julia使用Expr （表達(dá)式的縮寫(xiě)）來(lái)表示其AST。 （抽象語(yǔ)法樹(shù)是編譯器對(duì)代碼含義的理解。這有點(diǎn)像你在小學(xué)時(shí)做的語(yǔ)句圖解。）我們得到的Expr代表了一種方法。它包含了一些元數(shù)據(jù)（關(guān)于方法中出現(xiàn)的變量）和構(gòu)成方法主體的表達(dá)式。

現(xiàn)在我們可以問(wèn)一些關(guān)于e的問(wèn)題了。

我們可以通過(guò)使用names函數(shù)來(lái)詢(xún)問(wèn)Expr具有哪些屬性，該函數(shù)適用于任何Julia的值或類(lèi)型。它返回由該類(lèi)型（或值的類(lèi)型）定義的名稱(chēng)Array 。

julia> names(e)
3-element Array{Symbol,1}:
 :head
 :args
 :typ 

我們只是詢(xún)問(wèn)了e有什么樣的名稱(chēng)，現(xiàn)在我們可以詢(xún)問(wèn)每個(gè)名稱(chēng)對(duì)應(yīng)的值。Expr有三個(gè)屬性： 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)

馬上我們就看到打印出了一些值，但關(guān)于它們的含義或使用方式，還無(wú)法給我們足夠的信息。

• head告訴我們這是什么樣的表達(dá)式。通常，你會(huì)在Julia中使用單獨(dú)的類(lèi)型，但Expr是一種對(duì)解析器中使用的結(jié)構(gòu)進(jìn)行建模的類(lèi)型。解析器是用某種Scheme語(yǔ)言編寫(xiě)的，它將所有內(nèi)容都構(gòu)造為嵌套列表。 head告訴我們Expr的其余部分是如何組織的以及它代表了什么樣的表達(dá)式。
• typ是表達(dá)式自動(dòng)推斷的返回類(lèi)型。當(dāng)你求解任何表達(dá)式時(shí)，它會(huì)產(chǎn)生一些值。 typ是表達(dá)式求得的值的類(lèi)型。對(duì)于幾乎所有Expr ，該值將為Any （這永遠(yuǎn)都正確，因?yàn)槊糠N可能的類(lèi)型都是Any的子類(lèi)型）。只有類(lèi)型推斷方法的body和它們內(nèi)部的大多數(shù)表達(dá)式才會(huì)將其typ設(shè)置為更具體的類(lèi)型。（由于type是關(guān)鍵字，因此該字段不能用type作為其名稱(chēng)。）
• args是Expr最復(fù)雜的部分。它的結(jié)構(gòu)根據(jù)head的值而變化。它始終是一個(gè)Array{Any} （一個(gè)無(wú)類(lèi)型數(shù)組），但除此之外，結(jié)構(gòu)也會(huì)發(fā)生變化。

在表示一個(gè)方法的Expr中， e.args中將有三個(gè)元素：

julia> e.args[1] # 參數(shù)名稱(chēng)的符號(hào)
2-element Array{Any,1}:
 :x
 :y

符號(hào)是一種特殊類(lèi)型，用于表示變量，常量，函數(shù)和模塊的名稱(chēng)。它們與字符串的類(lèi)型不同，因?yàn)樗鼈儗?zhuān)門(mén)用來(lái)表示程序構(gòu)造的名稱(chēng)。

julia> e.args[2] # 變量元數(shù)據(jù)的3個(gè)列表
3-element Array{Any,1}:
 {:z}                                     
 {{:x,Int64,0},{:y,Int64,0},{:z,Int64,18}}
 {}                                       

上面的第一個(gè)列表包含所有局部變量的名稱(chēng)，這里我們只有一個(gè)（ z ）。第二個(gè)列表包含方法中每個(gè)變量和參數(shù)的元組。每個(gè)元組都有變量名，變量的推斷類(lèi)型和數(shù)字。該數(shù)字以機(jī)器友好（而不是人類(lèi)友好）的方式傳達(dá)了有關(guān)變量如何使用的信息。最后一個(gè)列表是捕獲的變量名稱(chēng)，在這個(gè)例子中它是空的。

julia> 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)

前兩個(gè)args元素是第三個(gè)元素的元數(shù)據(jù)。雖然元數(shù)據(jù)非常有趣，但現(xiàn)在不是必須的。重要的部分是方法的主體，而這就是第三個(gè)要素。下面是另一個(gè)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

這個(gè)Expr的頭是:body，因?yàn)樗欠椒ǖ闹黧w。

julia> body.typ
Int64

typ是方法的推斷返回類(lèi)型。

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包含一個(gè)表達(dá)式列表：即方法主體中的表達(dá)式列表。有一些行號(hào)注釋?zhuān)ㄈ?::( # line 3:) ），但主體的大部分在做的是設(shè)置z （ z = x + y ）的值并返回2 * z 。注意，這些操作已被特定的Int64類(lèi)型的內(nèi)部函數(shù)替換。top(function-name)表示了一個(gè)內(nèi)在函數(shù)，這是在Julia的代碼生成中實(shí)現(xiàn)的東西，而不是Julia本身實(shí)現(xiàn)的東西。

我們還沒(méi)有看過(guò)循環(huán)是什么樣子，所以讓我們嘗試一下。

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)

你會(huì)注意到主題中并沒(méi)有for或while循環(huán)。當(dāng)編譯器將代碼從我們編寫(xiě)的代碼轉(zhuǎn)換為CPU理解的二進(jìn)制指令時(shí)，會(huì)刪除對(duì)人類(lèi)有用但不被CPU理解的功能（如循環(huán)）。循環(huán)已被重寫(xiě)為label和goto表達(dá)式。goto后有一個(gè)數(shù)字，每個(gè)label也有一個(gè)數(shù)字。goto將跳轉(zhuǎn)到具有相同數(shù)字的label 。

檢測(cè)和提取循環(huán)

我們將通過(guò)查找后向跳轉(zhuǎn)的goto表達(dá)式來(lái)識(shí)別循環(huán)。

我們需要找到標(biāo)簽和那些goto，并弄清匹配的部分。我打算先把全部實(shí)現(xiàn)給你。在代碼墻之后，我們?cè)俜纸夂蜋z查這些代碼片段。

# 這是一個(gè)嘗試檢測(cè)方法體內(nèi)循環(huán)的函數(shù)
# 返回一個(gè)或多個(gè)循環(huán)函數(shù)中的行
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

現(xiàn)在解釋一下：

b = body(e)

我們首先將方法主體中的所有表達(dá)式作為Array 。 body是我已經(jīng)實(shí)現(xiàn)的函數(shù)：

  ＃返回方法的主體。
  ＃參數(shù)是表示方法的Expr，
  ＃返回向量{Expr}。
  function body(e::Expr)
    return e.args[3].args
  end

然后：

  loops = Int[]
  nesting = 0
  lines = {}

loops是個(gè)用來(lái)保存標(biāo)簽行號(hào)的Array，這些行號(hào)是產(chǎn)生循環(huán)的goto所對(duì)應(yīng)的標(biāo)簽行號(hào)。nesting表示我們當(dāng)前所處的循環(huán)次數(shù)。lines是一個(gè)保存（索引， 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主體中的每個(gè)表達(dá)式。如果它是一個(gè)標(biāo)簽，我們檢查是否有跳轉(zhuǎn)到此標(biāo)簽的goto（并且發(fā)生在當(dāng)前索引之后）。如果findnext的結(jié)果大于零，那么這樣的goto節(jié)點(diǎn)就存在，所以我們將它添加到loops （我們當(dāng)前所在的循環(huán)的Array ）并增加嵌套級(jí)別。

    if nesting > 0
      push!(lines,(i,b[i]))
    end

如果我們當(dāng)前正處在循環(huán)中，我們將當(dāng)前行推到我們的返回行數(shù)組中。

    if typeof(b[i]) == GotoNode && in(i,loops)
      splice!(loops,findfirst(loops,i))
      nesting -= 1
    end
  end
  lines
end

如果我們?cè)?code>GotoNode中 ，那么我們檢查它是否是循環(huán)的結(jié)束。如果是，我們從loops中刪除該條目并降低嵌套級(jí)別。

這個(gè)函數(shù)的結(jié)果是lines數(shù)組，一個(gè)（索引，值）元組的數(shù)組。這意味著數(shù)組中的每個(gè)值都有一個(gè)到方法-主體- Expr的主體的索引，和該索引處的值。lines中的每個(gè)元素都是循環(huán)中的一個(gè)表達(dá)式。

查找和鍵入變量

我們剛剛完成了loopcontents函數(shù) ，它返回了循環(huán)內(nèi)部的所有Expr 。我們的下一個(gè)函數(shù)是loosetypes ，它獲取Expr的列表并返回松散類(lèi)型的變量列表。稍后，我們將loopcontents的輸出傳遞給loosetypes 。

在循環(huán)內(nèi)發(fā)生的每個(gè)表達(dá)式中， loosetypes搜索符號(hào)及其相關(guān)類(lèi)型的出現(xiàn)次數(shù)。變量的使用在AST中表示為SymbolNode ; SymbolNode保存變量的名稱(chēng)和其推斷類(lèi)型。

我們不能檢查每個(gè)loopcontents收集到的表達(dá)式，來(lái)判斷它是否是一個(gè)SymbolNode 。問(wèn)題是每個(gè)Expr可能包含一個(gè)或多個(gè)Expr ;每個(gè)Expr也可能包含一個(gè)或多個(gè)SymbolNode 。這意味著我們需要提取任何嵌套的Expr ，以便我們可以依次從中查找SymbolNode 。

# 給定\`lr\`，一個(gè)表達(dá)式向量（Expr + 文本等）
# 嘗試在\`lr\`中查找所有出現(xiàn)的變量
# 并確定它們的類(lèi)型函數(shù)
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
  end

while循環(huán)以遞歸方式遍歷所有Expr的內(nèi)部。每次循環(huán)找到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

現(xiàn)在我們有一個(gè)變量列表及其類(lèi)型，因此很容易檢查類(lèi)型是否松散。這種檢查由 loosetypes查找特定類(lèi)型的非具體類(lèi)型（ UnionType）完成 。當(dāng)我們認(rèn)為所有非具體類(lèi)型都屬于“失敗”時(shí)，我們會(huì)得到許多“失敗”的結(jié)果。這是因?yàn)槲覀冋谑褂脦ё⑨尩膮?shù)類(lèi)型來(lái)評(píng)估每個(gè)方法，這些參數(shù)類(lèi)型可能是抽象的。

提高可用性

既然我們已經(jīng)可以對(duì)表達(dá)式進(jìn)行檢查，我們應(yīng)該讓它能更方便地調(diào)用用戶(hù)代碼。我們將創(chuàng)造兩種調(diào)用checklooptypes 的辦法：

1. 對(duì)整個(gè)函數(shù)調(diào)用：檢查給定函數(shù)的每個(gè)方法。

2. 對(duì)一個(gè)表達(dá)式調(diào)用：用于用戶(hù)自己提取code_typed結(jié)果的場(chǎng)合。

## 對(duì)于一個(gè)給定函數(shù)，對(duì)每個(gè)方法運(yùn)行checklooptypes
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

# 對(duì)于表示一個(gè)方法的Expr，
# 檢查循環(huán)中使用的每個(gè)變量的類(lèi)型
# 都有具體類(lèi)型
checklooptypes(e::Expr;kwargs...) = 
 LoopResult(MethodSignature(e),loosetypes(loopcontents(e)))

對(duì)于只有一種方法的函數(shù)，我們可以看到兩種方式的效果幾乎相同：

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)

漂亮的輸出

我在這里跳過(guò)了一個(gè)實(shí)現(xiàn)細(xì)節(jié)：我們是如何將結(jié)果打印到REPL（交互式編譯器）的？

首先，我制造了一些新的類(lèi)型。LoopResults是對(duì)整個(gè)函數(shù)的檢查結(jié)果，它具有函數(shù)名稱(chēng)和每個(gè)方法的結(jié)果。LoopResult是單個(gè)方法的檢查結(jié)果，它具有參數(shù)類(lèi)型和松散類(lèi)型的變量。

checklooptypes函數(shù)返回一個(gè)LoopResults 。該類(lèi)型定義了一個(gè)名為show的函數(shù)。REPL對(duì)它想要顯示的值調(diào)用display，然后 display將調(diào)用執(zhí)行我們的show。

此代碼對(duì)于此靜態(tài)分析的可用性非常重要，但它本身不進(jìn)行靜態(tài)分析。你應(yīng)該在你的實(shí)現(xiàn)語(yǔ)言中，為漂亮的打印類(lèi)型和輸出采用更喜歡的方法。這只是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

查找未使用的變量

有時(shí)，當(dāng)你在編寫(xiě)程序時(shí)，輸錯(cuò)了變量名稱(chēng)。程序無(wú)法辨別你輸錯(cuò)的變量實(shí)際上是指之前拼寫(xiě)正確的那個(gè)變量。它看到的是一個(gè)只使用了一次的變量，而你可能看到的是變量名稱(chēng)拼寫(xiě)錯(cuò)誤。需要變量聲明的語(yǔ)言自然會(huì)捕獲這些拼寫(xiě)錯(cuò)誤，但許多動(dòng)態(tài)語(yǔ)言不需要聲明，因此需要額外的分析層來(lái)捕獲這些錯(cuò)誤。

我們可以通過(guò)查找僅使用一次、或僅以一種方式使用過(guò)的變量來(lái)查找拼寫(xiě)錯(cuò)誤的變量名稱(chēng)（以及其他未使用的變量）。

下面是一個(gè)帶有一個(gè)拼寫(xiě)錯(cuò)誤名稱(chēng)的代碼示例。

function foo(variable_name::Int)
  sum = 0
  for i=1:variable_name
    sum += variable_name
  end
  variable_nme = sum
  return variable_name
end

這種錯(cuò)誤可能會(huì)導(dǎo)致代碼中出現(xiàn)問(wèn)題，而只有在運(yùn)行時(shí)才能發(fā)現(xiàn)。假設(shè)你的每個(gè)變量名稱(chēng)都只打錯(cuò)一次。我們可以將變量的用法分為讀和寫(xiě)。如果拼寫(xiě)錯(cuò)誤發(fā)生在寫(xiě)時(shí)（如， worng = 5 ），則不會(huì)拋出錯(cuò)誤。你只是默默地將值放在錯(cuò)誤的變量中——查找錯(cuò)誤的過(guò)程可能令人懊惱。如果拼寫(xiě)錯(cuò)誤發(fā)生在讀時(shí)（如， right = worng + 2 ），那么在運(yùn)行代碼時(shí)會(huì)出現(xiàn)運(yùn)行時(shí)錯(cuò)誤。我們希望對(duì)此有一個(gè)靜態(tài)警告，以便你可以更快地找到此錯(cuò)誤，但你還是需要等到運(yùn)行代碼才能發(fā)現(xiàn)這個(gè)問(wèn)題。

隨著代碼變得越來(lái)越長(zhǎng)、越來(lái)越復(fù)雜，要發(fā)現(xiàn)錯(cuò)誤也變得更加困難——除非靜態(tài)分析能幫到你。

左側(cè)和右側(cè)

另一個(gè)討論“讀”和“寫(xiě)”這兩種用法的方式是稱(chēng)它們?yōu)椤坝覀?cè)”（RHS）和“左側(cè)”（LHS）用法。這是指變量相對(duì)于 = 符號(hào)的位置。

以下是x一些用法：

• 左側(cè)：
  • x = 2
  • x = y + 22
  • x = x + y + 2
  • x += 2 (轉(zhuǎn)換為 x = x + 2)
• 右側(cè)：
  • y = x + 22
  • x = x + y + 2
  • x += 2 (轉(zhuǎn)換為 x = x + 2)
  • 2 * x
  • X

注意， x = x + y + 2和x += 2這兩個(gè)表達(dá)式在左側(cè)和右側(cè)都出現(xiàn)了，因?yàn)?code>x出現(xiàn)在=符號(hào)的兩側(cè)。

尋找一次性變量

我們需要查找兩種情況：

1. 使用一次的變量。
2. 只在左側(cè)或右側(cè)使用的變量。

我們將查找所有變量用法，但我們將分別查找左側(cè)和右側(cè)用法，以涵蓋這兩種情況。

尋找左側(cè)用法

變量在左側(cè)，是指變量需要處在=的左邊。這意味著我們可以在AST中查找=符號(hào)，然后查看它們的左側(cè)以找到相關(guān)變量。

在AST中， =是帶有:(=)頭部的Expr 。（括號(hào)是為了清楚地表明這是=的符號(hào)而不是另一個(gè)運(yùn)算符， := .）args的第一個(gè)值將是其左側(cè)的變量名稱(chēng)。因?yàn)槲覀冋诓榭淳幾g器已經(jīng)清理過(guò)的AST，所以我們的=符號(hào)左側(cè)（幾乎）總是只有一個(gè)符號(hào)。

讓我們看看代碼中的含義：

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

下面是完整的實(shí)現(xiàn)，隨后是解釋。

# 返回賦值（=）左側(cè)使用的所有變量列表
#
# 參數(shù)：
#   e: 一個(gè)表示方法的Expr，正如code_typed中得到的
#
# 返回：
#   一個(gè){符號(hào)}集合，其中每個(gè)元素都出現(xiàn)在e中賦值的左側(cè)。
#
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}()

我們有一個(gè)符號(hào)集合，這些是我們?cè)谧髠?cè)找到的變量名稱(chēng)。

  for ex in body(e)
    if Base.is_expr(ex,:(=))
      push!(output,ex.args[1])
    end
  end

我們沒(méi)有深入研究表達(dá)式，因?yàn)?code>code_typed 的AST非常扁平。循環(huán)和條件語(yǔ)句已轉(zhuǎn)換為goto控制流的扁平語(yǔ)句。在函數(shù)調(diào)用的參數(shù)中不會(huì)隱藏有任何賦值。如果等號(hào)左側(cè)有任何符號(hào)以外的東西，則此代碼將失敗。這沒(méi)有考慮到兩個(gè)特定的邊緣情況：數(shù)組訪(fǎng)問(wèn)（如a[5] ，將表示為:ref表達(dá)式）和屬性（如a.head ，將表示為:.表達(dá)式）。這些仍始終將相關(guān)符號(hào)作為其args的第一個(gè)值，它可能只是藏得深一些（如在a.property.name.head.other_property ）。此代碼無(wú)法處理這些情況，但if語(yǔ)句中的幾行代碼可以解決這個(gè)問(wèn)題。

      push!(output,ex.args[1])

當(dāng)我們找到左側(cè)變量時(shí)，我們將變量名稱(chēng)push! 到Set中 。該Set能確保我們每個(gè)名稱(chēng)只有一個(gè)副本。

尋找右側(cè)用法

要查找所有其他變量的使用，我們還需要查看每個(gè)Expr 。這更加復(fù)雜，因?yàn)槲覀兓旧详P(guān)心所有的Expr ，而不僅僅是有:(=)的那些。還因?yàn)槲覀儽仨毶钊胙芯壳短椎?code>Expr （以處理嵌套函數(shù)調(diào)用）。

這是完整的實(shí)現(xiàn)，隨后是解釋。

# 給定一個(gè)表達(dá)式，查找其中使用的（右側(cè)）變量
#
# 參數(shù)：e: 一個(gè)Expr
#
# 返回: 一個(gè){符號(hào)}集合, 其中每個(gè)e都在e的右側(cè)表達(dá)式中
#
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

該函數(shù)的主要結(jié)構(gòu)是一個(gè)龐大的if-else語(yǔ)句，其中每個(gè)分支處理一種不同的頭部符號(hào)。

  output = Set{Symbol}()

output是變量名稱(chēng)的集合，我們將在函數(shù)末尾返回。由于我們只關(guān)心一件事，那就是每個(gè)變量至少被讀取一次。因此使用Set可以使我們免于擔(dān)心變量名稱(chēng)的唯一性。

  if e.head == :lambda
    for ex in body(e)
      union!(output,find_rhs_variables(ex))
    end

這是if-else語(yǔ)句中的第一個(gè)條件。:lambda代表函數(shù)體。我們對(duì)定義的主體進(jìn)行了遞歸，這樣應(yīng)該能從定義中獲得所有右側(cè)變量。

  elseif e.head == :(=)
    for ex in e.args[2:end]  # skip lhs
      union!(output,find_rhs_variables(ex))
    end

如果頭部是:(=) ，則表達(dá)式是一個(gè)賦值過(guò)程。我們跳過(guò)args的第一個(gè)元素，因?yàn)檫@是被賦值的變量。對(duì)于每個(gè)剩余的表達(dá)式，我們遞歸地找到右側(cè)變量并將它們添加到我們的集合中。

  elseif e.head == :return
    output = find_rhs_variables(e.args[1])

如果這是一個(gè)return語(yǔ)句，那么args的第一個(gè)元素是返回了值的表達(dá)式。我們將把其中的任何變量添加到我們的集合中。

  elseif e.head == :call
    # 跳過(guò)函數(shù)名
    for ex in e.args[2:end]
      union!(output,find_rhs_variables(ex))
    end

對(duì)于函數(shù)調(diào)用，我們希望獲得調(diào)用的所有參數(shù)中使用的所有變量。我們跳過(guò)函數(shù)名，它是args的第一個(gè)元素。

  elseif e.head == :if
   for ex in e.args # want to check condition, too
     union!(output,find_rhs_variables(ex))
   end

表示if語(yǔ)句的Expr具有值為:if的head 。我們希望從if語(yǔ)句主體中的所有表達(dá)式中獲取變量用法，因此我們對(duì)args每個(gè)元素進(jìn)行遞歸。

  elseif e.head == :(::)
    output = find_rhs_variables(e.args[1])
  end

:(::)運(yùn)算符用于添加類(lèi)型注釋。第一個(gè)參數(shù)是被注釋的表達(dá)式或變量。我們檢查被注釋的表達(dá)式中的變量用法。

  return output

在函數(shù)的最后，我們返回一組右側(cè)變量。

還有一些代碼可以簡(jiǎn)化上述方法。因?yàn)樯厦娴陌姹局惶幚?code>Expr ，但是遞歸傳遞的某些值可能不是Expr ，我們還需要一些方法來(lái)適當(dāng)?shù)靥幚砥渌赡艿念?lèi)型。

# 遞歸基本用例，用于簡(jiǎn)化Expr版本中的控制流
find_rhs_variables(a) = Set{Symbol}()  # 未經(jīng)處理，應(yīng)當(dāng)是立即值，如Int
find_rhs_variables(s::Symbol) = Set{Symbol}([s])
find_rhs_variables(s::SymbolNode) = Set{Symbol}([s.name])

組合起來(lái)

現(xiàn)在我們已經(jīng)定義了上述的兩個(gè)函數(shù)，我們可以一起使用它們來(lái)查找只進(jìn)行了讀取或?qū)懭氲淖兞?。將查找它們的函?shù)命名為unused_locals 。

function unused_locals(e::Expr)
  lhs = find_lhs_variables(e)
  rhs = find_rhs_variables(e)
  setdiff(lhs,rhs)
end

unused_locals將返回一組變量名稱(chēng)。很容易就可以編寫(xiě)一個(gè)函數(shù)，來(lái)確定unused_locals的輸出是否可以計(jì)為“通過(guò)”。如果該集為空，則該方法通過(guò)。如果一個(gè)函數(shù)的所有方法都通過(guò)，則此函數(shù)通過(guò)。下面的函數(shù)check_locals實(shí)現(xiàn)了這個(gè)邏輯。

check_locals(f::Callable) = all([check_locals(e) for e in code_typed(f)])
check_locals(e::Expr) = isempty(unused_locals(e))

結(jié)論

我們對(duì)Julia代碼進(jìn)行了兩次靜態(tài)分析——一種基于類(lèi)型，一種基于變量使用。

靜態(tài)類(lèi)型語(yǔ)言已經(jīng)完成了我們基于類(lèi)型的分析所做的工作；額外的基于類(lèi)型的靜態(tài)分析在動(dòng)態(tài)類(lèi)型語(yǔ)言中最常用。已經(jīng)有很多（主要是研究）項(xiàng)目試圖為Python，Ruby和Lisp等語(yǔ)言構(gòu)建靜態(tài)類(lèi)型推斷系統(tǒng)。這些系統(tǒng)通常圍繞可選的類(lèi)型注釋構(gòu)建。你可以在需要時(shí)使用靜態(tài)類(lèi)型，而在不需要時(shí)轉(zhuǎn)而使用動(dòng)態(tài)類(lèi)型。這對(duì)于將一些靜態(tài)類(lèi)型集成到現(xiàn)有代碼庫(kù)中特別有用。

非類(lèi)型基礎(chǔ)的檢查（如我們的變量使用檢查）皆適用于動(dòng)態(tài)和靜態(tài)類(lèi)型語(yǔ)言。但是，許多靜態(tài)類(lèi)型的語(yǔ)言（如C ++和Java）要求你聲明變量，并且已經(jīng)提供了類(lèi)似我們創(chuàng)建的基本警告。仍然可以編寫(xiě)自定義檢查。例如，特定于項(xiàng)目樣式指南的檢查，或基于安全策略的額外安全預(yù)防檢查。

雖然Julia確實(shí)有很好的工具可以實(shí)現(xiàn)靜態(tài)分析，但它并不孤單。顯然，Lisp出了名的地方，就是能使其代碼成為嵌套列表的數(shù)據(jù)結(jié)構(gòu)，所以它往往很容易獲得AST。 Java也暴露了它的AST，盡管它的AST比Lisp復(fù)雜得多。某些語(yǔ)言或語(yǔ)言工具鏈的設(shè)計(jì)不允許純用戶(hù)在內(nèi)部表達(dá)式中肆意搜索。對(duì)于開(kāi)源工具鏈（特別是有良好注釋的工具鏈），一種選擇是在環(huán)境中添加鉤子（hook），以使你能訪(fǎng)問(wèn)AST。

如果這不起作用，最后的退路就是自己寫(xiě)一個(gè)解析器，不過(guò)要盡可能避免這種情況。覆蓋大多數(shù)編程語(yǔ)言的完整語(yǔ)法需要做很多工作，并且當(dāng)有新功能添加到語(yǔ)言中時(shí)，你必須自己去更新它（而無(wú)法從上游自動(dòng)獲取更新）。根據(jù)你要執(zhí)行的檢查，你可能只需解析某些行或某個(gè)語(yǔ)言功能的子集，這將大大降低編寫(xiě)自己的解析器的成本。

希望你對(duì)靜態(tài)分析工具如何編寫(xiě)的新理解能幫助你理解你代碼中使用的工具，并且也許還能激發(fā)你編寫(xiě)自己的工具。