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

# 概要

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

# ソースコードに出てきた用語たち
<img width="200" alt="スクリーンショット 2015-12-05 22.56.12.png" src="https://qiita-image-store.s3.amazonaws.com/0/25820/b8c2f690-c4a7-ad7d-acb9-0104a1e88ca1.png">

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


# ソースコード
* IDEのテストケース
 * [swift/tools/swift-ide-test/swift-ide-test.cpp](https://github.com/apple/swift/blob/master/tools/swift-ide-test/swift-ide-test.cpp#L2434)
* IDEの構文定義など(見てるだけで面白い)
 * [swift/include/swift/IDE/SyntaxModel.h](https://github.com/apple/swift/blob/master/include/swift/IDE/SyntaxModel.h#L29)
 * [swift/include/swift/lib/IDE/SyntaxModel.cpp](https://github.com/apple/swift/blob/master/lib/IDE/SyntaxModel.cpp#L209)


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

```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`という関数を呼び出しています
* 第二引数がソースファイル名ですね

```cpp: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()`あたりは、なんとなくやってることが想像できますね

```cpp: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 *`を持っており、解析済みのソースファイルのノードを頭から舐めています


```cpp: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;
}
```

```cpp:PrintSyntaxColorWalkerのメンバ変数の一部
  const char *BufStart;
  const char *BufEnd;
  const char *CurrBufPtr;
```

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

```cpp: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リポジトリ](https://github.com/apple/swift)を見た時の自分の反応ですが、**この記事を見た人の反応でもあるかもしれない**と投稿してから気付きました。すみません。
* [とりあえずFix typoしたら2時間でマージされ](https://github.com/apple/swift/pull/172)て胸熱でした。
* お気づきの点がございましたら、お気軽にコメントください! 間違いなどご指摘いただけると大変ありがたいです👼

# 参考
* [プログラミング言語の実装の基礎](http://www.score.cs.tsukuba.ac.jp/~minamide/compiler-jikken/compiler003.html)

* [プログラミング言語処理: コンパイラの構造]
(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](http://steps.dodgson.org/bn/2011/04/26/)