Zenn
Open4

js-control-flow-analyzer

magurotunamagurotuna

Code Path Analysis Details - ESLint - Pluggable JavaScript linter

以下、ESLint の Code Path Analysis の説明をする際にはこのページを大いに参考にしています。画像もそのまま掲載しているものがあります。

Copyright JS Foundation and other contributors, https://js.foundation

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
magurotunamagurotuna

ESLint互換の Control Flow Analyzerを作る計画

ESLint Code path analysis に存在するオブジェクト

CodePath

  • id
  • initialSegment
  • finalSegments
  • returnedSegments
  • thrownSegments
  • currentSegments
  • upper
  • childCodePaths

をプロパティにもつオブジェクト。1つのfunction、あるいはグローバルが1つの CodePath に対応する。
CodePath 中の最初のセグメント（常に単一）と最後のセグメント（複数ある場合もある）への参照をもっている。

CodePathSegment

  • id
  • nextSegments
  • prevSegments
  • reachable

をプロパティにもつオブジェクト。上で「セグメント」と表現していたものはこれのこと。
CodePathSegment 同士が連なりあって、Doubly Linked Listのような構造をしている。ただし、通常の双方向連結リストとは異なり、前後のノードが複数個ある場合があることに注意が必要（例えば、if によって分岐する場合には next が複数に枝分かれする）。
このリストが CodePath に含まれることで、制御フローを表現する。

example of eslint's code path analysis

この図で言うと、全体が CodePath で個々のブロックが CodePathSegment を表している。もとのソースコードは以下

if (a && b) {
    foo();
}
bar();
magurotunamagurotuna

一般的な（？）制御フローグラフとの用語の対応

「コンパイラの構成と最適化」（中田育男著）によれば、CodePathSegment におよそ対応する用語として「基本ブロック」というものが出てきている。

制御フローグラフは、（中略）分岐も合流もない部分（これは基本ブロックを呼ばれる）を節点（node）として、それらの間を分岐や合流を表す有向辺（edge）で結んだ有向グラフである。

分岐も合流もない部分が基本ブロックになる、という事実が重要で、実際上の図を見直してみると、最初の基本ブロック (CodePathSegment)には、プログラムの始まりから Identifier (a) までが含まれている。これはつまり、Identifier (a) までは分岐も合流もなく、一本道で処理が進む、ということを示している。

magurotunamagurotuna

deno_lint の ControlFlow に求められる仕様

deno_lint は現状、

  • no-fallthrough
  • no-unreachable
  • getter-return

以上3つのルールを実装するために使用されている。
そして、これらのルールを作るために求められる制御グラフフローの機能を洗い出してみると、以下になる。

  • 任意の statement の位置(Span)をクエリとして、その statement が
    • unreachable か否かを返す
    • 同一スコープにあるそれより後ろの文の実行をスキップさせるのか否かを返す（unreachable 判定でまかなえるかも）

これを制御フローグラフで実現するためには、追加で

  • statement の位置をクエリとして、それがどの CodePath （~= スコープ？）に属しているのかを求めて、その CodePath を返す

といったインターフェースも必要になりそう