Swiftの構文解析の流れを超ざっくり追ってみる

概要

• 祝!Swiftオープンソース化から1日経ちました👼
• 皆さんそろそろC++に慣れてきた頃でしょうか
• せっかくなので構文解析の部分を読みたい!
• とソースコードを眺めていたら、IDEのテストケースで **「ノードの種類(予約語なのかコメントなのかなど)によってターミナルにカラーコードを出力する」**コードを見つけたので、ふんわり追ってみました

ソースコードに出てきた用語たち

• Lex, Lexical Analysis : 字句解析。文字列を字句(トークン)に分割する
• Parse / Syntax Analysis : 構文解析。トークンの列から抽象構文木を作成
• Sema, Semantic Analysis : 意味解析。型チェックや引数の個数チェックなど
• Token : 字句解析の結果、分割された文字たち
• AST, Abstract Syntax Tree: 抽象構文木. 必要なトークンを精査し木構造で表したデータ
• Node : 構文木の各要素

ソースコード

• IDEのテストケース
• swift/tools/swift-ide-test/swift-ide-test.cpp
• IDEの構文定義など(見てるだけで面白い)
• swift/include/swift/IDE/SyntaxModel.h
• swift/include/swift/lib/IDE/SyntaxModel.cpp

本題

テストメソッド

• 最終的に呼び出しているのは、以下のテスト用メソッドです
• ノードの種類(予約語なのかコメントなのかなど)に応じてカラーコードをターミナルに出力しています

swift-ide-test.cpp(733-768_PrintSyntaxColorWalkerクラス内)

  void wrapForTerminal(SyntaxNodeKind Kind, bool Begin) {
    llvm::raw_ostream::Colors Col;
    switch (Kind) {
    case SyntaxNodeKind::Keyword: Col = llvm::raw_ostream::MAGENTA; break;
    // Skip identifier.
    case SyntaxNodeKind::Identifier: return;
    case SyntaxNodeKind::DollarIdent: Col = llvm::raw_ostream::MAGENTA; break;
    case SyntaxNodeKind::Integer: Col = llvm::raw_ostream::BLUE; break;
    case SyntaxNodeKind::Floating: Col = llvm::raw_ostream::BLUE; break;
    case SyntaxNodeKind::String: Col = llvm::raw_ostream::RED; break;
    case SyntaxNodeKind::StringInterpolationAnchor: Col = llvm::raw_ostream::CYAN; break;
    case SyntaxNodeKind::CommentLine: Col = llvm::raw_ostream::GREEN; break;
    case SyntaxNodeKind::CommentBlock: Col = llvm::raw_ostream::GREEN; break;
    case SyntaxNodeKind::CommentMarker: Col = llvm::raw_ostream::MAGENTA; break;
    case SyntaxNodeKind::DocCommentLine: Col = llvm::raw_ostream::CYAN; break;
    case SyntaxNodeKind::DocCommentBlock: Col = llvm::raw_ostream::CYAN; break;
    case SyntaxNodeKind::DocCommentField: Col = llvm::raw_ostream::WHITE; break;
    case SyntaxNodeKind::CommentURL: Col = llvm::raw_ostream::RED; break;
    case SyntaxNodeKind::TypeId: Col = llvm::raw_ostream::CYAN; break;
    case SyntaxNodeKind::BuildConfigKeyword: Col = llvm::raw_ostream::YELLOW; break;
    case SyntaxNodeKind::BuildConfigId: Col = llvm::raw_ostream::YELLOW; break;
    case SyntaxNodeKind::AttributeId: Col = llvm::raw_ostream::CYAN; break;
    case SyntaxNodeKind::AttributeBuiltin: Col = llvm::raw_ostream::MAGENTA; break;
    case SyntaxNodeKind::EditorPlaceholder: Col = llvm::raw_ostream::YELLOW; break;
    case SyntaxNodeKind::ObjectLiteral: return;
    }

    if (Begin) {
      if (const char *CStr =
          llvm::sys::Process::OutputColor(Col, false, false)) {
        OS << CStr;
      }
    } else {
      OS << llvm::sys::Process::ResetColor();
    }
  }

main関数

• swift-ide-test.cppの2434行目あたりにあるmain関数から、ActionTypeごとに分岐して、doSyntaxColoringという関数を呼び出しています
• 第二引数がソースファイル名ですね

swift-ide-test.cpp(2652-2657_main関数内)

  case ActionType::SyntaxColoring:
    ExitCode = doSyntaxColoring(InitInvok,
                                options::SourceFilename,
                                options::TerminalOutput,
                                options::Typecheck);
    break;

構文解析~テストメソッドの呼び出し

• このdoSyntaxColoring関数内で
• ソースコードを構文解析
• 取得したノードをすべて走査
• ノードごとに先ほどのwrapForTerminalテストメソッドを呼び出して出力
• を行ってるようです。(詳細まで理解できていません)
• CI.performParseOnly()やCI.performSema()あたりは、なんとなくやってることが想像できますね

swift-ide-test.cpp(777-803_doSyntaxColoring関数前半)

static int doSyntaxColoring(const CompilerInvocation &InitInvok,
                            StringRef SourceFilename,
                            bool TerminalOutput,
                            bool RunTypeChecker) {
  CompilerInvocation Invocation(InitInvok);
  Invocation.addInputFilename(SourceFilename);
  Invocation.getLangOptions().DisableAvailabilityChecking = false;

  CompilerInstance CI;

  // Display diagnostics to stderr.
  PrintingDiagnosticConsumer PrintDiags;
  CI.addDiagnosticConsumer(&PrintDiags);
  if (CI.setup(Invocation))
    return 1;
  if (!RunTypeChecker)
    CI.performParseOnly();
  else
    CI.performSema();

  unsigned BufID = CI.getInputBufferIDs().back();
  SourceFile *SF = nullptr;
  for (auto Unit : CI.getMainModule()->getFiles()) {
    SF = dyn_cast<SourceFile>(Unit);
    if (SF)
      break;
  }

• 後半に出てくるWalkerクラスがメンバ変数にChar *を持っており、解析済みのソースファイルのノードを頭から舐めています

swift-ide-test.cpp(804-812_doSyntaxColoring関数後半)

  assert(SF && "no source file?");
  ide::SyntaxModelContext ColorContext(*SF);
  PrintSyntaxColorWalker ColorWalker(CI.getSourceMgr(), BufID, llvm::outs(),
                                     TerminalOutput);
  ColorContext.walk(ColorWalker);
  ColorWalker.finished();

  return 0;
}

PrintSyntaxColorWalkerのメンバ変数の一部

  const char *BufStart;
  const char *BufEnd;
  const char *CurrBufPtr;

継承関係

• 肝心のdoSyntaxColoring関数を呼び出しているのはどこでしょうか。
• じつは、PrintSyntaxColorWalkerクラスは親クラスであるSyntaxModelWalkerクラスの下記メソッドをオーバーライドしています。
• そのため、SyntaxModelContext::walkメソッドの中でModelASTWalker::passNodeメソッドが呼ばれる度にテストメソッドも呼び出されるようです

SyntaxModel.h(154-167)

class SyntaxModelWalker {
// (中略)
  /// \brief Called when first visiting a syntax node, before walking into its
  /// children.  If it returns false, the subtree is skipped.
  ///
  virtual bool walkToNodePre(SyntaxNode Node) { return true; }

  /// \brief Called after visiting the children of a syntax node. If it returns
  /// false, the remaining traversal is terminated and returns failure.
  virtual bool walkToNodePost(SyntaxNode Node) { return true; }

まとめ

• 今回は構文解析のロジックを理解するには至りませんでした。
• ですが、CompilerInstance::performSema()メソッドあたりを深追いすれば、ParseやSemaの流れがいい感じに把握できそうです
• テストケースから追っていくのはとっつきやすくてGOODだと思いました😇

その他

• あ...ありのまま今起こった事を話すぜ... Swiftを読みに来たらC++だった...何を言ってるのかわか
• ↑Swiftリポジトリを見た時の自分の反応ですが、この記事を見た人の反応でもあるかもしれないと投稿してから気付きました。すみません。
• とりあえずFix typoしたら2時間でマージされて胸熱でした。
• お気づきの点がございましたら、お気軽にコメントください! 間違いなどご指摘いただけると大変ありがたいです👼

参考

• プログラミング言語の実装の基礎

• [プログラミング言語処理: コンパイラの構造]
  (http://www.seto.nanzan-u.ac.jp/~hachisu/compiler/samp/comp0104.html)

• [問20 意味解析のフェーズで行う処理 平成25年秋期｜応用情報技術者試験.com]
  (http://www.ap-siken.com/kakomon/25_aki/q20.html)

• Clang のコード補完 - Backnumbers: Steps to Phantasien