mypy のソースコードをちょっと読んだメモ

mypy は Python の型アノテーションを元に静的な型チェックを行うライブラリ。型推論を行い返り値の型などもチェックする。

起動からアルゴリズム部分に到達するまで

  • mypy コマンドは scripts/mypy が起動される
  • main.py の main
  • mypy.build.build が呼ばれる
  • dispatch メソッドが色々やってそう

全体の流れ

  • build.py の中にアルゴリズムや設計思想がテキストで説明してある
  • dispatch は ① load_graph(source) して ② process_graph(graph) する

load_graph

  • Graph とは str->State の dict
  • State は 1 つのモジュールに対応
  • エッジは基本的に import に対応
  • 空の graph からスタートし、BFS して依存関係を全列挙する
  • State はファイル名を与えられていながら依存性を出したりしてるので中でパースしてそう
  • State の self.tree が構文木っぽい
  • mypy.fastparse.parse がパースを担当する
  • 最初に Python 公式の typed-ast を使ってパースする https://github.com/python/typed_ast
  • それを ASTConverter という輩が mypy 独自の AST にコンバートする
  • 変換後の AST は nodes.py

process_graph

  • State を依存関係で SCC に分解し末尾から順に処理していく
  • fresh: キャッシュが既に有り処理不要
  • stale: キャッシュが古いので解析が必要
  • process_stale_scc の中で SCC 内部の解析が行われるようだ

process_stale_scc

  • Semantic Analysis
    • semantic_analysis
    • semantic_analysis_pass_three
    • semanal.pyの冒頭に説明がある
  • Type Check
    • type_check_first_pass
    • type_check_second_passを更新がなくなるまで繰り返す
    • checker.py

なんとなく何をしてるかは説明でわかったけど、具体的な処理を追うのは TODO。Any 型等の噂の見どころ(?)に到達したい。

感想

  • 循環 import を何とかするための工夫がかなり多い
  • 解析を高速化するためにファイルに対するキャッシュを作るらしく、そのキャッシュがあるか無いかとか、あっても後々の解析のために読まないといけないのかとか、その辺の場合分けのコードが多い