静的解析

Leah Hanson
目次

はじめに

コンパイルできないコードを書いたときに間違っている部分に赤い下線を引く機能を持つ IDE を使っている読者も多いだろう。フォーマットやスタイルに関する問題を検出するリンターを自分のコードに対して実行したこともあるだろうし、全ての警告を有効化した極端に神経質なモードでコンパイラを実行したこともあるかもしれない。これらはどれも静的解析を応用したツールである。

静的解析 (static analysis) とは、コードの問題を実行することなく検出する手法を言う。「静的」とは問題の検出をコードの実行時ではなくコンパイル時に実行することを意味する。上述したツールを使った経験があるなら、そのツールの動作が魔法のように感じられたかもしれない。しかしどんなツールもプログラムに過ぎない ── あなたのような人間のプログラマーによって書かれたソースコードから作られている。本章では、静的解析を使ってコードの性質をチェックする処理の実装方法を解説する。このためには、チェックしたい性質とその理由をまず理解する必要がある。

静的解析を使う処理を書くときは、そのプロセス全体を次の三つのステップに分解すると見通しがよくなるだろう:

  1. チェックする性質を決める。

    解決しようと思っている問題をプログラミング言語のユーザーが理解できる形で一般的に説明できなくてはならない。例えば:

    • 変数名のスペルミスを見つける。
    • 並列コードで発生する競合状態を見つける。
    • 未実装の関数を呼び出している箇所を見つける。
  2. 性質のチェック方法を正確に決める。

    上記のタスクをそのまま友達に任せたとしても、その友達はコンピューターに指示すべき正確な処理を理解できないだろう。例えば「変数名のスペルミスを見つける」というタスクをコンピューターに指示するには、何がスペルミスなのかを決める必要がある。一つの選択肢として「変数名は英語の辞書に載っている単語から構成されなければならない」と定める方法が考えられる。あるいは、一度だけ (スペルミスしたときにだけ) 使われる変数を探す方法も考えられるだろう。

    一度だけ使われる変数を探すなら、「変数が使われる」とは具体的にどんな処理なのか (代入と参照で扱いを変えるのか)、そしてどんなコードで警告を出すのか (そして出さないのか) を決める必要がある。

  3. 実装詳細を詰める。

    このステップに含まれるのは実際にコードを書いたり、使用するライブラリのドキュメントを読んだり、解析を書くのに必要な情報を抽出する方法を考えたりする作業が含まれる。例えばファイルを読み込み、読み込んだ文字列をパースしてデータ構造を組み立て、そのデータ構造を使って特定の性質をチェックするといった処理を実装することになる。

本章では、これら三つのステップをいくつかの性質に対してそれぞれ見ていく。ステップ 1 では、解析対象の言語を使うユーザーが直面する問題を理解できる程度に言語について知っておくことが求められる。本章のコードは全て Julia で書かれ、解析されるのも Julia コードである。

非常に簡単な Julia 入門

Julia は非常に若い技術計算向けの言語である。バージョン 0.1 がリリースされたのは 2012 年の春であり、本章が執筆された 2015 年時点ではバージョン 0.3 に到達している。簡単に言えば、Julia は Python によく似た言語でありながらも、省略可能な型注釈を持ち、オブジェクト指向の機能を持たない。多くのプログラマーが最も革新的だと感じる Julia の機能として多重ディスパッチ (mulitple dispatch) がある。この機能は Julia における API 設計をはじめとした様々な設計判断に影響を及ぼしている。

Julia コードの例を示す:

# increment に関するコメント
function increment(x::Int64)
  return x + 1
end

increment(5)

このコードは関数 increment のメソッドを定義する。このメソッドは Int64 型の引数 x を受け取り、x + 1 の値を返す。この定義の後には increment に 5 を渡す関数呼び出しがある。読者の想像通り、この呼び出しは 6 に評価される。

Int64 は型であり、その値は 64 ビットで表現される符号付き整数である。コンピューターが 64 ビットプロセッサを搭載しているなら、これはハードウェアが直接理解できる整数でもある。Julia の型はメソッドのディスパッチで使われるのに加えて、メモリ上におけるデータの表現も定義する。

上記のコードで名前 increment は汎用関数 (generic function) を意味する。現在 increment は一つのメソッドしか持たないものの、任意の汎用関数は複数のメソッドを持つことができる。多くのプログラミング言語で「関数」と「メソッド」は同じような意味で使われるのに対して、Julia では意味が大きく異なる。本章を読むときは、「関数」がメソッドの集合を表し、「メソッド」が特定の型シグネチャに対する特定の実装を表すことを意識すると理解が深まるだろう。前文の通り、本章ではこれから「汎用関数」を単に「関数」と呼ぶ。

increment 関数の異なるメソッドを定義してみよう:

# x と y を足す。
function increment(x::Int64, y::Number)
  return x + y
end

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

これで increment 関数は二つのメソッドを持つようになった。この関数が呼び出されると、Julia は引数の数と型から呼び出されるメソッドを決定する。この処理を動的多重ディスパッチ (dynamic multiple dispatch) と呼ぶ。つまり:

これに対して、典型的なオブジェクト指向言語は単一ディスパッチを採用する: 呼び出し x.foo(y) のディスパッチでは (事実上の) 第一引数 x だけが使われる。

単一ディスパッチと多重ディスパッチはいずれも引数の型を利用する。上のコードにある x::Int64 はディスパッチでのみ使用される型注釈である。Julia は動的型システムを持つので、単に x とした場合は関数内で任意の型の値を x に代入できる。

この簡単な説明では多重ディスパッチの真価を全く捉えられていない。Julia について興味があるなら、ぜひ自分で調べてみてほしい。私たちは静的解析を使ってプログラムの性質をチェックする処理の実装に進む。

ループの中で使われる変数の型のチェック

多くのプログラミング言語と同様に、Julia で非常に高速なコードを書くにはコンピューターの動作と Julia の動作を両方とも理解する必要がある。コンパイラに高速なコードを生成させる上で重要な概念として型安定性 (type-stability) がある。コードの特定の部分で変数の型が変化しない (安定である) と確信できるとき、コンパイラは変数の型が変化する可能性を排除できないときより多くの最適化を実行できる。型安定性は単相性 (monomorphism) とも呼ばれ、JavaScript における単相性の重要性を解説した記事に What's up with monomorphism? がある。

型安定性が重要な理由

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 である。そして Julia で Int64 型の値と Float64 型の値を足すと Float64 型の値となる。関数内で変数 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
end

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

二つの関数の唯一の違いは変数 sum の初期値である: Julia で 0 は Int64 型のリテラルを表し、0.0 は Float64 型のリテラルを表す。そのため sum = 0 と sum = 0.0 では sum の型が異なる。この小さな違いがどれほどの違いを生むだろうか？

Julia は JIT (Just-In-Time) コンパイルを行うので、関数の最初の実行は以降の実行より時間がかかる (関数が初めて呼び出されたときは、引数の型に対応するメソッドをコンパイルする時間が加わる)。そのため関数をベンチマークするときは、必ず測定の前に一度実行する (または事前コンパイルする) 必要がある:

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 B しかアロケートしていない。

unstable のコードがとても単純なことを考えれば、このアロケーションはループの中で発生していると推測できる。この推測が正しいかどうかを確認するには、ループの反復回数を増やしたときアロケーションが増えるかどうかを確認すればよい。反復を 100 から 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 にはボックス化 (boxing) が必要となるのに対して、stable の sum にはボックス化が必要にならないためである。ボックス化された値は型タグと実際の値を表すビット列から構成されるのに対して、ボックス化されない値は値を表すビット列だけから構成される。ただ型タグは小さいので、この表現の違いがアロケーションされるメモリの量の違いを説明するわけではない。

値のボックス化の有無はコンパイラが適用できる最適化の種類に影響する。変数の型が具象型かつ不変型の場合、コンパイラはその変数をボックスから出して関数のスタックに積むことができる。これができない場合、コンパイラはヒープにアロケートした領域に変数を配置してガベージコレクションの対象としなければならない。不変型 (immutable type) は Julia 特有の概念であり、不変型の値は変更できない。

多くの不変型は何らかの値を表す型であり、値の集合を表す型は不変型でないことが多い。例えば Int64 と Float64 を含む大部分の数値型は不変型である (Julia で数値型は通常の型であり、特別なプリミティブ型ではない。Int64 と同じように振る舞う MyInt64 を定義することもできる)。不変型は変更できないので、値を変更するには新しい値を作る必要がある。例えば 4 + 6 を評価するには、結果を保持する Int64 型の値を新しく作らなければならない。これに対して、可変型 (mutable type) の値はインプレースに更新できるので、値を変更するとき新しい値を作成する必要がない。

x = x + 2 を実行するとき新しい x の値に対応するメモリのアロケートが必要になるのは奇妙に思える: Int64 が不変型だとインプレースな更新ができないので、これほどに基礎的な操作が遅くなってしまう。なぜそのようにしているのだろうか？ ここでコンパイラによる最適化が話に入ってくる: 不変型を使っても (通常は) コードの実行は遅くならない。もし x が型安定で具象型 (例えば Int64) を持つなら、コンパイラは x をスタックにアロケートして x をインプレースに (古い値を破棄しながら) 改変できる。問題が起こるのは x が型安定でないときで、このときコンパイラは x の型が分からず、従って x がどれだけのメモリ領域を占めるかも分からない。このとき x をヒープにボックス化せざるを得ず、そうするとコードの他の部分が x の値を使う可能性が否定できなくなって x を改変できなくなる。

stable の sum は具象型 Float64 を持ち型安定なので、コンパイラは sum をボックス化せずに関数のスタックの中に埋め込み、その値を直接改変する。sum はヒープ上にアロケートされないので、i/2 を加えるたびに新しい値を作成する必要はない。

一方で unstable の sum は型安定でないので、コンパイラはヒープにアロケートしたメモリ領域に sum の値を格納する。そのため sum を改変するときは新しい値をヒープに作成しなければならない。ヒープに値を作成する (そして sum の値が必要になるたびにヒープから取得する) のに長い時間が費やされる。

変数の初期値が間違っているために変数が型不安定になってしまうミスは特に Julia の初心者が犯しがちなミスである。ループの中で使われる変数が型安定であることを自動的にチェックできれば、プログラマーは自身のコードの性能が求められる領域で使われている変数の型に関する情報を素早く得られるようになる。

実装詳細

ループの中で使用される型安定でない変数を見つける処理で必要になる具体的な操作は次の通りである:

最も中心的な四つ目の操作を最初に考える。これまでに型安定でない関数の例を示し、そこに含まれる型安定でない変数を理由と共に指摘した。同じことをプログラムに行わせるにはどうすればいいだろうか？ 値が変化する変数を見つけるには関数の動作をシミュレートする必要があるように思える ── 相当のコードが必要になるだろう。しかし幸いにも、Julia の型推論機構が関数の実行の流れを追跡して型を決定する処理を既に実行している。

unstable の sum は Union(Float64,Int64) 型を持つ。この型はユニオン型 (union type) と呼ばれる特殊な型の一種であり、ユニオン型の変数が保持できる値の型には複数の選択肢がある。例えば Union(Float64,Int64) 型の変数は Int64 型の値または Float64 型の値を保持する (同時に複数の値を保持することはできない)。UnionType は任意の個数の型を結合できる: 例えば UnionType(Float64, Int64, Int32) は三つの型を結合する。ユニオン型の変数は型安定でないので、ループに含まれる変数の中で UnionType が割り当てられたものを見つければよい。

コードを表す文字列を受け取り、そのコードを表すデータ構造を組み立てるパースは複雑な処理であり、言語の機能が多ければさらに複雑になる。本章では Julia のコンパイラが内部で用いるデータ構造を借用する。これは、ファイルの読み込みやパースといった処理を気にしないで済むことを意味する。しかし同時に、私たちが完全な制御を持たない、ときに不格好で使いやすいとも言えないデータ構造を扱わなければならない。

パースを Julia に任せることで書くコードが減って楽ができるのに加えて、コンパイラと同じデータ構造によって提供されるコンパイラの理解に即した正確な情報が利用可能になる ── 私たちが実装する処理の結果と実際の実行が矛盾することはない。

Julia コードで Julia コードを調べるこういった処理をイントロスぺクション (introspection) と呼ぶ。英単語 introspect は人間が自分の考えや感じ方について内省することを意味する。同様にコードの introspect とは、コードの表現や実行時の性質を同じ言語のコードで調べることを意味する。コードのイントロスぺクションを超えてコードの改変まで行うとき、その操作をメタプログラミング (metaprogramming, プログラムを作成・改変するプログラム) と呼ぶ。

Julia のイントロスぺクション

Julia は豊富なイントロスぺクション機能を持ち、コンパイラが扱うデータ構造を取得するための組み込み関数が四つ用意されている: code_lowered, code_typed, code_llvm, code_native である。これらの関数はコンパイル処理の順番に並んでおり、最初の code_lowered の出力は Julia コードを表す文字列に最も近く、最後の code_native の出力は CPU が実行するプログラムに最も近い。本章で考える静的解析処理では、最適化と型付けが終わった後の抽象構文木 (abstract syntax tree, AST) を出力する code_typed を利用する。

code_typed は処理対象の関数と引数の型のタプルという二つの引数を取る:。例えば、関数 foo に二つの Int64 型の値を渡して呼び出したときに実行されるメソッドの 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_type が与えられた引数の型にマッチする複数のメソッドに対する結果を返せることを意味する。例えば、Int64 ではなく Any を第二引数に渡すことができる。Any は型階層の頂点にある型であり、自身を含む任意の型は Any の部分型となる。引数の型タプルが Any を含みマッチするメソッドが複数あるなら、code_typed が返す Array には複数のメソッドが含まれる。

扱いやすいように、code_typed の返り値から 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 を表現する。AST はコンパイラがコードの意味を捉えるために組み立てるデータ構造であり、小学校で国語の授業に見たであろう文を単語ごとに分解して木の形に配置した図と似た役割を果たす。上記の例で Expr 型の値 e は一つのメソッドを表し、メソッドで使われる変数に関するメタデータとメソッド本体を表す式から構成される。

e から情報を抽出してみよう。

Expr の持つプロパティは names 関数で取得できる。names は任意の値または型に適用できる一般的な関数であり、その型 (または値の型) に定義されたプロパティの名前からなる 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 の args は次の三つの要素を持つ:

julia> e.args[1] # 引数の名前を表すシンボル
2-element Array{Any,1}:
 :x
 :y

e.args[1] には引数の名前を表すシンボルが含まれる。シンボル (Symbol) は変数・定数・関数・モジュールの名前を表すための特別な型である。プログラムの構成要素の名前を表現し、文字列とは区別される。

julia> e.args[2] # 変数のメタデータを収めたリストからなる三要素の Array
3-element Array{Any,1}:
 {:z}
 {{:x,Int64,0},{:y,Int64,0},{:z,Int64,18}}
 {}

e.args[2] の第一要素にはローカル変数の名前が含まれる。foo のローカル変数は z しか存在しない。第二要素にはメソッドの引数およびローカル変数ごとに一つのタプルが含まれる。それぞれのタプルは変数名、推論された変数の型、そして数値からなる。最後の数値は変数の使われ方に関する情報を機械が理解しやすい形式で示す。第三要素はキャプチャされた変数名からなるリストであり、この例では空となる。

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)

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 はメソッドの本体 (body) を表すので、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 で実装されてはいない。

ループがどのような Expr で表現されるかは確認していなかった。試してみよう:

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 や loop が含まれないことに気が付くだろう。コンパイラはプログラマーが書いたコードを CPU が理解できるバイナリ命令に変換する中で、人間には便利であるものの CPU には理解できないループなどの機能を削除していく。ループはラベルと goto 式を使って書き換えられる。goto は数値を持ち、ラベルも数値を持つ。goto 式を評価すると、引数と同じ数値を持つラベルに実行が移動する。

ループの検出と抽出

ループを見つけるには、自身より後方にジャンプする goto 式を探せばよい。具体的にはラベルと goto を全て見つけてから、条件を満たす goto を探すことになる。まず完全な実装を示し、その後に部分ごとに解説を加える:

# メソッドの本体に含まれるループを検出する。
# 一つ以上のループに含まれる行からなるリストを返す。
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 は次のように実装される:

# メソッドを表す Expr を受け取り、メソッドの本体を表す
# Array{Expr} を返す。
function body(e::Expr)
  return e.args[3].args
end

続いてローカル変数の初期化がある:

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

loops には処理中の式が含まれるループの終端となる goto を表す整数 (b に対する添え字) が格納される。nesting は処理中の式が含まれるループの個数を表す。lines は添え字と Expr からなるタプルが格納される配列である。

  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 に返り値 jumpback を追加し、nesting を 1 だけ大きくする。

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

もし処理中の式がループの中にあるなら、現在の行を返り値 lines に追加する。

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

もし処理中の式が GotoNode 型なら、それがループの終わりかどうかを判定する。もしそうなら loops から i を取り除き、nesting を 1 だけ小さくする。

この関数の返り値 lines は配列であり、各要素は (index, value) という形をしている。第一要素の index はメソッドの本体を表す Expr 型の配列に対する添え字であり、第二要素の value はその配列の i 番目の要素を表す。lines にはメソッドの中でループの内側にある式に対応する要素が全て含まれる。

型に関する変数を見つける

ループの内側にある式に関する情報を返す関数 loopcontents が実装できた。続いて、loopcontents の返り値を受け取って安定していない型を持つ変数を返す関数 loosetypes を実装する。

loosetypes はループの内側にある式から変数を抽出し、その変数の型が安定しているかどうかを調べる。AST では変数の参照が SymbolNode 型の値で表され、SymbolNode は変数の名前と推論された型を保持する。

一つの Expr に複数の Expr 型の値が含まれる可能性があるので、単純に Expr を一つずつ調べるだけでは十分でない。Expr に含まれる SymbolNode を全て抽出するには、入れ子になった Expr を隅々まで走査する必要がある。

# 式の情報と式のタプルからなる配列 lr を受け取り、
# そこに含まれる型安定でない変数からなる配列を返す。
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 ループは引数に含まれる 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

これで変数とその型からなるリストが手に入ったので、型安定性は簡単に調べられる。ここでは変数が UnionType という特定の非具象型を持つかどうかで型の安定性を調べている。この条件を「変数が任意の非具象型を持つかどうか」にしてしまうと、偽陽性が多く発生してしまう: メソッドの引数に付く型注釈は抽象型であることがよくある。

利便性を高める

これでコアの機能を実装できた。次はユーザーが使いやすいようにインターフェースを整えよう。次に示す checklooptypes は二つのメソッドを持ち、それぞれ処理が異なる:

# 与えられた関数の各メソッドに対して 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

# メソッドを表す Expr 型の値 e に対して、
# ループの中で使われる変数が具象型を持つかどうかを判定する。
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)

pretty print

上記のコードで示さなかった実装詳細が一つある: 結果はどのように REPL に出力されるのだろうか？

まず、新しい型をいくつか作成する。LoopResults は関数全体の解析結果を表し、関数の名前と各メソッドに対する結果を保持する。LoopResult は一つのメソッドの解析結果を表し、引数の型と型安定でない変数を保持する。

checklooptypes 関数は LoopResults 型の値を返し、この型に対する show 関数が定義されている。REPL は値をユーザーに表示するとき display 関数を使うようになっており、この関数が次に示す show の実装を呼び出す。

このコードは静的解析の利便性を向上させるために重要であるものの、静的解析とは関係がない。pretty printing は実装言語で書きやすいように実装するべきである。ここに示すのは 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) なら、コードを実行したとき実行時エラーが発生する。こういった状況に対する静的な警告があればエラーを早い段階で見つけられるものの、Julia ではコードを実行してみるまで問題があるかどうか分からない。

コードが長く複雑になるにつれて、スペルミスを見つけるのは難しくなる ── そして静的解析が大きな力となる。

右辺と左辺

変数に対する「読み込み」と「書き込み」の操作に言及するとき、変数の出現箇所が右辺 (right-hand side, RHS) と左辺 (left-hand side, LHS) のどちらなのかに言及しても同じ意味となる。

x の出現箇所の例を示す:

x = x + y + 2 と x += 2 が両方に現れている点に注意してほしい。x が = の両側で使われているためである。

単一の用途でしか使われない変数の検出

検出したい変数の特徴は二つある:

一つ目の特徴を持つ変数は二つ目の特徴を持つので、二つ目の特徴だけを考えればよい。これから変数が LHS でのみ使われるケースと RHS でのみ使われるケースを別々に考える。

変数が左辺で使われる箇所の検出

変数が LHS で使われるとき、その変数は = の左側にある。つまり、AST に含まれる = の左側にある変数を探せばよい。

代入演算子 = は AST で head フィールドに :(=) を持つ Expr 型の値で表される (括弧は別の演算子 := と区別するためにある)。この値の args フィールドには LHS にある変数名が含まれる。今回のようにコンパイラが単純化した後の AST を扱うとき、= 記号の左側には (ほぼ間違いなく) 記号が一つしか存在しない。

= 演算子の表す 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

代入演算子 = の LHS に出現する変数を見つける処理の実装を示す:

# 式に含まれる代入演算子 = の左辺 (LHS) に出現する変数を全て見つける。
#
# 引数:
#   e: code_typed を使って作成された、メソッドを表す Expr 型の値
#
# 返り値:
#   e に含まれる代入演算子の LHS に出現する変数を集めた Set{Symbol}
#
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}()

output は返り値となるシンボルの集合であり、代入演算子の LHS にある変数名が格納される。

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

code_typed が返す AST は十分に単純なので、e に含まれる式を再帰的に走査する必要はない: ループや条件分岐は goto を使った制御フローを持つ平らな文に変換されている。また、関数呼び出しの引数に代入演算子が含まれることはない。上記のコードは = の左側にシンボル以外の値があると失敗する。失敗する可能性のあるコーナーケースは二つある: a[5] のような配列アクセス (:ref 式で表される) と、a.head のようなプロパティ参照 (:. 式で表される) である。どちらの式でもシンボルは args の第一要素に含まれるので、少しだけ手間をかければシンボルを取り出せる。上記のコードはこれらのケースを無視しているものの、数行の if 文を追加すれば対処できる。

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

代入演算子の LHS に出現する変数が見つかったら、その名前を output に push! する。同じ名前を複数回 push! したとしても、Set は追加された名前を一度しか記憶しない。

変数が右辺で使われる箇所の検出

もう一方の変数の出現箇所を見つける処理でも、メソッドを構成する Expr 型の値を一つずつ調べることになる。今回は :(=) 以外の Expr も基本的に全て調べなければならず、入れ子になった式 (関数呼び出し式など) を扱うために再帰的な処理も必要になる。

完全な実装を次に示す:

# 式の中で RHS として出現する変数を全て見つける。
#
# 引数:
#   e: code_typed を使って作成された、メソッドを表す Expr 型の値
#
# 返り値:
#   e の中で RHS として出現する変数を集めた Set{Symbol}
#
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]  # LHS を飛ばす。
      union!(output,find_rhs_variables(ex))
    end
  elseif e.head == :return
    output = find_rhs_variables(e.args[1])
  elseif e.head == :call
    # 関数名を飛ばす。
    for ex in e.args[2:end]
      union!(output,find_rhs_variables(ex))
    end
  elseif e.head == :if
   for ex in e.args # 条件節も調べる。
     union!(output,find_rhs_variables(ex))
   end
  elseif e.head == :(::)
    output = find_rhs_variables(e.args[1])
  end

  return output
end

この関数は一つの大きな if-else 文がほとんどを占める。それぞれのケースは異なる head のシンボルを処理する。

  output = Set{Symbol}()

output は返り値となる変数名の集合である。注目しているのは変数が出現するかどうかだけなので、Set を使えば変数名の重複を考慮する必要がなくなる。

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

続いて if-else 文の最初のケースがある。:lambda は関数の本体を表すので、そこに含まれる式に find_rhs_variables を再帰的に呼び出した結果を output に加えている。

  elseif e.head == :(=)
    for ex in e.args[2:end]  # LHS を飛ばす。
      union!(output,find_rhs_variables(ex))
    end

もし e.head が :(=) なら、e は代入演算式を表す。このとき e.args の第一要素は代入される変数なので output に加えてはいけない。残りの部分は RHS なので、再帰的に処理して条件を満たす変数名を集める。

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

もし e.head が :return なら、e.args の第一要素は返り値となる式を表す。よって e.args[1] に対する再帰的な呼び出しの結果をそのまま返せばよい。

  elseif e.head == :call
    # 関数名を飛ばす。
    for ex in e.args[2:end]
      union!(output,find_rhs_variables(ex))
    end

e が関数呼び出しを表すときは、呼び出しの引数で使われる変数を全て output に加える必要がある。e.args[1] に含まれる関数の名前は飛ばして構わない。

  elseif e.head == :if
   for ex in e.args # 条件節も調べる。
     union!(output,find_rhs_variables(ex))
   end

if 文を表す Expr 型の値は head フィールドに :if を持つ。if 文の本体だけではなく条件節で使われる変数もチェックしたいので、e.args の全要素に対して再帰的に find_rhs_variables を呼び出す。

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

:(::) 演算子は型注釈を表す。その第一引数は型注釈の対象となる式または変数なので、それが条件を満たす変数かどうかをさらに調べる。

  return output

この関数は RHS に出現した変数からなる Set{Symbol} を最後に返す。

上記のメソッドは Expr 型の値しか処理せず、find_rhs_variables 関数の再帰的な呼び出しの中には Expr でない型を持つ値に対する呼び出しが含まれる。そのため、完全な実装とするには Expr でない型を受け取るメソッドが必要になる。

# これらのメソッドは再帰呼び出しのベースケースを処理する。
# 個別のメソッドとして用意することで、Expr 型の値を受け取る
# メソッドの制御フローが単純になる。
find_rhs_variables(s::Symbol) = Set{Symbol}([s])
find_rhs_variables(s::SymbolNode) = Set{Symbol}([s.name])
# それ以外のケースはおそらく即値 (Int など)
find_rhs_variables(a) = Set{Symbol}()

一つにまとめる

これまでに定義した二つの関数を使えば、読み込みだけまたは書き込みだけでしか使われていない変数を見つけることができる。この処理を実行する関数は unused_locals と呼ばれる:

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

unused_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 を操作する API を公開するものの、その AST は Lisp より格段に複雑な構造をしている。ユーザーがプログラムの内部表現にアクセスできるように設計されていない言語や言語ツールチェインも多い。オープンソースのツールチェイン (特に詳細なコメントを持つもの) では、AST にアクセスするフックを実装に仕込むことも一つの選択肢となる。

この選択肢が現実的でないときは、自分でパーサーを書くことが最後のフォールバックとなる。ただ、これは可能な限り避けるべきである: 多くの言語において、完全な文法をカバーするパーサーを書くには大変な手間がかかる。さらに、言語に新しい機能が追加されたときはパーサーを自分の手で更新しなければならない。解析する性質によっては完全なパーサーが必要とならず、一部の行や言語のサブセットをパースできれば十分なケースもある。このときはパーサーを書く手間が大きく削減される。

静的解析ツールの作成方法に関する新たな理解が、自分のコードに適用されるツールの理解を深めることにつながり、さらには自分で静的解析ツールを書くきっかけとなることを願っている。

広告
このページの文章はテキストゆれないくんを使って校正されました。