Crystalコンパイラ テスト問題集 解説付き解答

1. 全体アーキテクチャ

Q1. 三層の構成を説明せよ

Crystalのコンパイルは パース → 意味解析 → コード生成 の三層で構成されている。単なる処理の順序ではなく、「どのレベルの抽象を扱うか」という関心の分離でもある。

フロントエンドはソース文字列だけを相手にする。Lexer がそれをトークン列に変換し、Parser が構文規則に従ってASTを組み立てる。この段階では「型」の字は影も形もない。

意味解析層（ミドルエンド）に入って初めて、「このノードは何の型か」という問いが意味を持ち始める。Program#semantic が複数のパスを順に走らせ、宣言を収集し、型を推論し、整合性を検証していく。バックエンドはその先で、型が確定したASTをLLVMのIRへと翻訳する。あとはシステムリンカが引き継いで実行バイナリを生成するだけだ。

もう一つ押さえておきたいのは、このコンパイラ本体がCrystal自身で書かれているという事実だ。Crystalは自分自身を実装言語とする「セルフホスティング」のコンパイラである。

Q2. require "prelude" はどう扱われるか

compiler.cr の parse メソッドを見ると、答えは簡潔だ。

nodes = Expressions.new([Require.new(prelude).at(location), nodes] of ASTNode)

各ソースファイルをASTに変換した後、その先頭に Require.new(prelude) を差し込んでから program.normalize へ渡している。つまり require "prelude" はユーザーが書かなくても、コンパイラが自動で先頭に挿入してくれる。

Object、String、puts といった、何も書かなくても使える機能はすべてこの自動挿入を入口として定義されている。魔法があるわけではなく、メカニズムは配列の先頭に要素を一つ加えるだけの話だ。

Q3. --progress フラグで得られる情報

ProgressTracker のソースを開くと、まず STAGES = 14 という定数が目に入る。コンパイルは14もの段階に分かれているのだ。Parse から始まり、Semantic (top level)、Semantic (new)、Semantic (type declarations)、Semantic (abstract def check) と続き、最後は Codegen (crystal)、Codegen (bc+obj)、Codegen (linking) で締めくくられる。--progress を有効にするとこれらが [3/14] Semantic (main) のような形で随時表示される。

ただし --progress が担うのは「今どのステージにいるか」を示すことだけだ。各ステージにどれだけ時間が掛かったか、メモリはどう動いたかを知りたければ --stats を合わせて使う。「なぜこんなにビルドが遅いのか」を調べるときは、まず --progress でどのステージに詰まっているかを絞り込み、そこを --stats でさらに掘り下げる——という二段構えが有効だ。

2. ディレクトリ構造

Q4. 各ファイルの責務

program.cr は「コンパイル1回分の状態」をすべて収める箱だと思えばよい。initialize メソッドを展開すると、Object、Reference、Value、Int32、String、Array……と組み込み型を手作業で次々に登録していく処理が200行以上続く。Program クラス自身が NonGenericModuleType を継承しているところも見どころで、コンパイルの状態を管理しながら同時にトップレベルの名前空間としても機能するという、一石二鳥の設計になっている。

semantic/main_visitor.cr は型推論の中核を担うファイルで、行数は3700行を超える。MainVisitor < SemanticVisitor として、メソッド呼び出しを解決し、変数の型を追跡し、ブロックを処理する。「@vars が瞬間の型を保持し、@meta_vars が累積の型を保持する」というコメントが実装の思想をよく表しており、フロー依存の型推論がどのように管理されているかが見えてくる。

codegen/llvm_typer.cr はCrystalの型とLLVMの型を結びつける翻訳レイヤーだ。Int32 なら llvm_context.int(32)、Bool なら int1、クラスならポインタ、structならvalue型という対応関係を保持する。一見シンプルに見えるが、Union型のような「中身が不定」な型や、再帰的な構造体のサイズを確定させる処理になると、途端に複雑さが増す。

Q5. syntax/ と semantic/ の違い

syntax/ が知っているのはソーステキストだけだ。入力は文字列、出力は型のついていないASTノード群で、「型」という言葉はここには存在しない。

semantic/ に入ると様相が一変する。ASTノードに @type : Type? が付与され、依存グラフが張られ、型が伝播していく。意味解析が終わって初めて、すべてのノードが意味のある型を手に入れ、コード生成に渡せる状態になる。

この分離があるから、パーサーは型を一切気にせず書け、意味解析器はトークンを一切気にせず書ける。互いの関心を徹底的に切り離していることが、それぞれのコードを読みやすく保っている。

3. ASTノード体系

Q6. location / end_location の役割

location と end_location は、ASTノードが「ソースコードのどこから生まれたか」を記録するだけの値オブジェクトだ。それだけといえばそれだけなのだが、これがなければCrystalの丁寧なエラーメッセージは成り立たない。

Error: undefined method 'foobar' for Int32 (line 42, column 3)

こういったメッセージを出すには、ASTノードの生成時にソース位置を記録しておき、意味解析でエラーを検出した際にそれを参照する必要がある。クローン時にも位置情報がコピーされるため、マクロ展開で生成されたノードであっても「元のソースのどこから来たか」を遡ることができる。

Q7. dependencies / observers が必要な理由

Crystalの型推論はワンパスではない。型が一つ確定するたびに、それに依存するノードへ通知が波及していく。この「反応性」を支えるのが dependencies と @observers の仕組みだ。各 ASTNode は自分が依存しているノード群（dependencies）と、自分の型変化を待っているノード群（@observers）の二方向リンクを持ち、型が変化したとき通知が連鎖していく。

実装を見ると、SmallNodeList という構造体が使われている。最初の2要素をインラインに保持することで、平均的なノードでは Array のヒープアロケーションを回避している。「平均的なノードの依存数は2未満」という計測結果に基づいた、地道な最適化だ。

Q8. Visitor と Transformer の違い

Visitor の visit メソッドは true か false を返すだけで、ASTの構造には手を触れない。木を歩きながら情報を集めたり副作用を伴う処理を走らせたりするのが役割だ。

Transformer の transform メソッドは ASTNode を返す。受け取ったノードを別のノードに差し替えられるため、ASTの形そのものを書き換えられる。CleanupTransformer はこちらを使って不要な分岐を切り落とし、後段のコード生成が安全に動ける状態を整える。

「読むだけなら Visitor、書き換えるなら Transformer」——これだけ覚えておけば、使い分けに迷うことはない。

4. 型ヒエラルキー

Q9. Type 中心設計が重要な場面を2つ

一つ目はメソッドのディスパッチだ。Crystalはオーバーロードをサポートしており、呼び出し時に引数の型に応じて最適な def を選ぶ。「AはBのサブタイプか」「AはBを実装しているか」という判定はすべて Type オブジェクトを介して行われる。Type という共通の語彙があるから、パーサーはおろかコード生成器さえも型の詳細を知らなくてよい。

二つ目はUnion型の合成だ。type_merge は複数の型を受け取り、最小の共通型を生成する。Int32 と Int32 なら Int32、Int32 と String なら Int32 | String、どちらかが NoReturn なら残る一方をそのまま返す——この細かいルールが数十行にわたって types.cr に書かれており、すべて型ヒエラルキーの上に成り立っている。

Q10. Union型になる典型コード

x = condition ? 42 : "hello"

三項演算子の then 節は Int32、else 節は String を返す。コンパイラはどちらの分岐も実行される可能性を考慮して両方の型を合成し、x の型を Int32 | String と確定させる。ここで x + 1 などと書けば、String の可能性をコンパイラは見逃さない。問題をランタイムエラーではなくコンパイルエラーとして表面化させる——それが静的Union型の本質的な価値だ。

5. Crystal::Program

Q11. 「中央データベース」と呼ぶ理由

コンパイルに関わるすべてのパス——TopLevelVisitor も MainVisitor も LLVMTyper も——は program への参照を持っている。型が必要なら program.int32、require済みのファイルを確認したければ program.requires.includes?(...)、とここへ問い合わせる構造だ。グローバル変数で状態を持つ代わりに Program インスタンスを使うことで、テスト時に独立した複数のコンパイル環境を起動・廃棄できる。

Program クラスが NonGenericModuleType を継承している点も見逃せない。Program 自身がCrystalの型として存在しているわけで、トップレベルに書いてある puts "hello" の「実行主体」は何かと問われれば、それもまた Program という型が担っている。

Q12. Program が管理する情報を3つ

requires（Set(String)） はrequire済みのファイルパスを記録するコレクションだ。parse メソッドでは、ファイル名を program.requires.add した「後」にパースを開始する。この順序が重要で、循環requireや二重ロードをここで防いでいる。

unions（Hash(Array(UInt64), UnionType)） はUnion型のキャッシュだ。Int32 | String という型はコンパイル全体を通じて一つしか存在しないべきで、同値なUnionを同一インスタンスに束ねるのがこのハッシュである。各型のID（UInt64）をソートした配列をキーにしており、String | Int32 と Int32 | String は同じキーから同じインスタンスを返す。

symbols（Set(String)） はCrystalのシンボルリテラルを集約するコレクションだ。意味解析中に出現したシンボルが次々と追加され、コード生成では program.symbols.each_with_index を使って String -> Int32 の対応表を構築する。シンボルに番号を振ることで、実行時の比較を整数比較に落とし込める。

6. 字句解析・構文解析

Q13. LexerとParserの境界

class Parser < Lexer ——この一行に答えが書いてある。CrystalではParserがLexerを「継承」している。

教科書的なコンパイラ設計ではLexerとParserを別々のクラスに分け、トークンのやり取りをインタフェース経由で行う。しかしCrystalでは継承による一体化を選んでいる。ParserはLexerの内部状態を直接保持し、ASTを構築しながら必要なタイミングでトークンを一つずつ消費していく。クラス間のデータ受け渡しコストがなく、コードも一カ所にまとまるという実利的な選択だ。

Q14. 再帰下降パーサーの利点と注意点

再帰下降パーサーの強みは、文法規則とコードの対応が直感的なことにある。parse_if、parse_def、parse_call というメソッドが文法をそのまま体現しているので、読めばわかり、修正は局所的に収まる。パーサージェネレータを使わないぶん、エラーメッセージを細かくコントロールできるのも大きい。

注意すべき点が二つある。一つは左再帰（expr := expr '+' term のような文法）をそのまま書くと無限ループに陥ることだ。もう一つはCrystalの文法がかなり込み入っており、parser.cr は6500行を超える大ファイルだということ。一人で全体を把握するには、それなりの覚悟がいる。

7. requireシステム

Q15. crystal_path.cr の責務

CrystalPath#find は require "foo" の引数 "foo" を受け取り、実際に読み込むべきファイルの絶対パスを返す。

"./bar" のような相対パスなら、呼び出しもとのディレクトリからたどる。"json" のようなライブラリ名なら、CRYSTAL_PATH や設定由来の検索パスを順に当たる。さらに require "foo/bar" のような指定では、foo/src/bar.cr、foo/src/foo/bar.cr といったshardの命名規則に沿った複数候補をチェックする。ポータブルビルド向けに $ORIGIN というプレースホルダーを展開する仕組みまであり、パス解決の全体像はなかなか一筋縄ではいかない。

Q16. 重複ロード防止がないと何が起きるか

program.requires.add の呼び出しはパースの「前」に行われている。

program.requires.add source.filename
parse(program, source).as(ASTNode)

require "json" が50カ所に書かれていても、2回目以降は requires.includes? で弾かれてスキップされる。この仕組みがなければ、同じクラスが二重に定義されてコンパイルエラーになる。あるいは require "a" → require "b" → require "a" → … と循環を繰り返す無限ループに陥る。「追加してからパース」という順序は、循環検出のために不可欠な工夫だ。

8. 意味解析パス

Q17. トップレベル収集パスが先に必要な理由

次のコードを考えてみてほしい。

def greet(x : Greeter)
  x.hello
end

class Greeter
  def hello; "hi"; end
end

Greeter クラスが定義される前に greet がそれを参照している。それでもCrystalはこれをコンパイルできる。TopLevelVisitor が最初のパスで Greeter クラスと greet メソッドの「存在」を program.types に登録してしまうからだ。型推論の本パスが始まる頃には、Greeter はすでに登録済みで、前方参照でも難なく解決できる。この2パス構成がなければ、定義の出現順序がコンパイル成否を左右するような、かなり不便な言語になっていただろう。

Q18. abstract def チェックが検出する不整合

AbstractDefChecker はすべてのabstractクラス・モジュールを走査し、各abstractメソッドがサブタイプで実装されているかを確認する。単純に同名メソッドがあるかどうかだけでなく、引数の数・型制約・ブロック有無・戻り値型まで細かく照合する。

一つ興味深いルールがある。abstractメソッドが foo(x : Int32) という制約を持っていても、実装側が foo(x) と制約なしで書いた場合は「OK」と判定される。制約を緩める方向は許容されるが、より狭い制約を後から課すことはできない、というわけだ。

Q19. cleanup_transformer が取り除くもの

CleanupTransformer のコメントには「if true; 1; else; 2; end を 1 に書き換える」とある。

型推論が終わった段階では、is_a? や nil? によるチェックの結果が静的に確定していることがある。たとえば変数の型が Int32 のみと確定しているとき、value.is_a?(String) は常に false であり、else 側のブランチは絶対に実行されない。そのブランチのノードには型がついておらず、コード生成は型のないノードを扱えない。だから到達不能なコードはcleanupで事前に除去しておく必要がある——これがcleanupトランスフォームの核心的な役割だ。

9. 型推論システム

Q20. Call#recalculate が核心である理由

型推論の流れを追っていくと、あらゆる変化が最終的に recalculate へと収束していくことがわかる。あるメソッドの引数の型が変化すると、そのCallノードの update が呼ばれ、recalculate が起動する。recalculate はまず以前の target_defs（解決済み呼び出し先）とのバインドを切り離し、lookup_matches でオーバーロード解決をやり直して最良の候補を選ぶ。選んだ候補に再びバインドし、呼び出しの型を更新し、それに依存する次のノードへと変化を波及させる。

これが繰り返される。依存グラフに沿って型の変化が連鎖し、全体が収束したところで型推論は完了する。

Q21. オーバーロード解決が曖昧になる代表ケース

def foo(x : Int8); end
def foo(x : Int64); end
foo(1)

1 という整数リテラルは Int8 にも Int64 にもオートキャストできる。まずオートキャストなしで解決を試みると、どちらの定義ともマッチしない。そこで RetryLookupWithLiterals という例外を投げて with_autocast: true のリトライに切り替える。今度は両方にマッチするが、どちらがより適切か決定できず「ambiguous call」エラーになる。

「一度失敗して例外でリトライ」という流れは少し独特だが、オートキャストの有無を綺麗に分離するための工夫だと理解すれば、設計意図が見えてくる。

Q22. is_a? / nil? による型絞り込み

x : Int32 | Nil = get_value()

if x.nil?
  # ここでは x の型は Nil
else
  # ここでは x の型は Int32
  puts x + 1  # コンパイルOK
end

内部では TypeFilteredNode というノードでラップすることで、分岐ごとに異なる型を見せる仕組みになっている。TruthyFilter、SimpleTypeFilter、NotFilter といったフィルタが And/Or/Not で合成でき、ブール代数と同じ感覚で型フィルタを扱える設計だ。if x.nil? && x.is_a?(Foo) のような複合条件も、フィルタの合成として一貫して処理される。

10. マクロシステム

Q23. マクロが単なる文字列置換でない理由

Cのプリプロセッサを知っている人は、マクロを「テキストを別のテキストに置き換えるもの」として想像するかもしれない。Crystalのマクロはその発想とはかなり異なる。

MacroInterpreter は MacroIf、MacroFor、Var、StringInterpolation といったマクロ専用のASTノードを評価し、展開結果を IO::Memory に書き出す。その生成されたソースは parse_macro_source で再びパースされ、VirtualFile と結びついたASTとして本流に合流する。「ASTを評価してソースを生成し、そのソースを再パースしてASTに戻す」というサイクルだ。このためマクロ内から型情報やノード構造に基づいた、表現力の高いコード生成が可能になる。

Q24. MacroInterpreter が必要な理由

マクロはコンパイル時に実行されなければならない。しかしコンパイル時には、まだ実行バイナリが存在しない。通常の意味での「実行」はできないのだ。そこで MacroInterpreter がインタプリタとして機能する。

マクロと通常のコードの本質的な違いは、マクロが「今実行する処理」ではなく「コンパイルされるコード」を生み出すものだという点にある。{% if %} による条件分岐も {% for %} によるループも、最終的には展開済みの静的な構文としてASTに織り込まれる。MacroInterpreter がなければ、Crystalのマクロは文字列処理に毛が生えた程度のものになっていただろう。

Q25. マクロのトレードオフ

record Point, x : Float64, y : Float64 の一行から getter、initialize、==、to_s などが展開される便利さは確かに魅力的だ。しかし展開後のコードはソースファイルに直接現れないため、その位置を指したエラーメッセージを出すために「仮想ファイル」という概念まで持ちこむことになった。

コンパイル時間の面でも、{% for %} ループが大量の型や定義を生成すると意味解析の負荷は跳ね上がる。マクロは強力だが、「本当にコンパイル時評価が必要か」と立ち止まって考える習慣が、長期的なビルド速度を守ることになる。

11. LLVMコード生成

Q26. LLVMTyper の役割

LLVMTyper#llvm_type はCrystalの Type を受け取り、対応する LLVM::Type を返す。Bool なら i1、Int32 なら i32、クラスならポインタ型、structならvalue型——という対応関係を管理するのが役割だ。

特に工夫が必要になるのは再帰型への対処だ。llvm_type には wants_size フラグがあり、「サイズさえわかれば詳細は不要」なときにポインタを void* で近似する。Foo が Pointer(Foo) を含む再帰的なstructのサイズを求めるとき、循環を断ち切るための仕組みで、@wants_size_cache という専用のキャッシュまで用意されている。

Q27. Union型にタグが必要な理由

MixedUnionType のLLVM表現は、「型IDフィールド」と「値を格納する領域」からなる構造体だ。型IDは現在格納されている型の番号であり、値領域はそのUnionに入りうる型のうち最大サイズに合わせて確保される。

なぜタグが必要なのか。Union型の変数には Int32 が入っていることも String が入っていることもある。実行時に x.as(String) と書いたとき、本当に String が入っているかを確認しなければならない。その確認の依り所が型IDだ。タグなしにUnionの値を読み出せば、型安全性は即座に崩れる。

Q28. rescue/ensure をLLVMで扱う難しさ

ensure ブロックは例外の有無にかかわらず実行しなければならない。通常の経路では ensure を実行してから ret すればよい。しかし例外の経路では、LLVMの invoke 命令と landingpad を使って別のブロックへジャンプし、そこで ensure を実行してから例外を再スローする必要がある。

fun.cr の関数生成コードを見ると、@ensure_exception_handlers、@rescue_block、@catch_pad という3つの状態変数が関数生成の前後で保存・復元されている。例外ハンドラがネストする場合、これらはスタック的に積まれていく。どのrescueがどのensureに対応するかを正確に管理するコードはかなり複雑で、このあたりがCrystalのコード生成の中で最も入り組んだ部分の一つになっている。

12. コントリビュート

Q29. 小さな改善PRの推奨手順

まず手を付けるべきは現象の最小化だ。バグであれ改善であれ、最小限のコードで再現・確認できる状態を作ることから始める。spec/ 以下の関連するスペックを動かして、現在の挙動を自分の目で確かめる。

次は影響範囲の見積もり。変更するファイルはどれか、それに依存しているモジュールはどれか。変更は局所的であるほど好ましく、広がりすぎると意図しない回帰を生みやすい。

テストについては、少なくとも変更と並走させる。spec/compiler/ にはコンパイラのテストが豊富に揃っており、新しいケースを追加するか、既存のテストが壊れていないかを確認する。

そして最後に、これが最も重要かもしれないが、PRの本文で「なぜ」を語ること。差分は「何を変えたか」しか語らない。「なぜその設計を選んだのか」「他にどんな選択肢を検討したか」を書くことで、レビュワーはコードの意図を正しく評価できる。