はじめに

今回はparserの生成物である構文木についてのお話です。普段は主にparserとlexerについて考えていますが、たまに構文木について考えを巡らすこともあります。むしろparserの目指すべき実装が固まったいまだからこそ、その主な生成物である構文木の設計について考える必要があるとも言えます。

Rubyのparserの実装は複数あり、それぞれのparserが生成する構文木もまた微妙に異なります。それらの構文木は各parserのユースケースに合わせてアドホックに必要な要素が追加されているように見え、なにか原理原則に従っているように思えませんでした。そのため果たして構文木に設計というものがあるのだろうかという疑問をずっと抱いていました。

Rubyの開発ではユースケースを収集し、それらのユースケースに対してどのくらい応えられているかをもって設計の良し悪しを確認するというアプローチを取ることが多いと思います。なので今回は構文木の使われ方がこれまでどのように変わってきたのかを確認し、それぞれの用途でどのような機能が必要か整理します。そして必要な機能を提供するために求められる構文木の設計と実装について考えていきたいと思います。真理を理解するにはまず使われ方から理解する必要があるということです。

構文木の使われ方の変遷

時代の変化とともに構文木に求められる情報や機能も変化してきました。まずはじめに極めて原始的な言語を考え、そこから抽象構文木が必要になる理由をみていきます。その後、LSPやLinterといった現代的なツールを調べることで構文木に必要な機能の全体像への理解を深めていきましょう。

parserの生成物

parserとlexerは入力された文字列から抽象構文木を生成して後段の処理に渡すものと認識している人も多いかと思います。しかし実装する言語が単純な場合にはparserが構文解析から計算までを行うという実装を考えることもできます。

例えば原始的な電卓の実装では、parserが直接四則演算を行って答えを計算するという実装をすることも可能です。 github.com

対象となる言語が簡単なうちはパースしながら計算をするという方法でもよいですが、言語が複雑になるとこの方法はだんだんと辛くなってきます。例えばメソッドをもつ言語であれば、パースしていく順番と計算をする順番が一致しないこともあります。以下の例ではmというメソッドの定義をパースしたあとでそのメソッドを呼び出しています。この場合、メソッド定義をパースしたときにその文字列をどこかに保管しておき、メソッドを呼び出した時に文字列をパースするなどの"工夫"が必要になります。

def m
  p "in m"
end

m

また型システムを導入する場合などに、parserの中に型システムを実装することになり複雑性が上がります。このような理由からparserからプログラムの実行や型システムなどの処理を切り出し、パースした結果をなにかしらの形で表現して後続の処理に渡すという方法をとります。このとき構文木、なかでも抽象構文木(Abstract Syntax Tree: AST)をparserの生成物にすることが多いです。

構文木とはなにか

構文解析した結果を文法定義の構造に則って木構造にしたものが構文木です。

1 + 2

コードを実行するための構文木

parserが構文木を生成するといっても、その構文木のデザインにはいろいろなものがあります。構文木を作る理由がプログラムを実行することなのであれば、プログラムの意味に対応した構文木を作るのがよいでしょう。例えばRubyにはifという条件分岐を表現するための構文がいくつか用意されています。

# (普通の)if
if a == 1
  p :t
else
  p :f
end

# 後置if
p :t if a == 1

# 三項演算子
a == 1 ? (p :t) : (p :f)

これらは見た目こそ違うものの、a == 1を実行してその結果に応じてp :tを実行する、もしくはp :fを実行する(後置ifの場合はなにもしない)という意味では同じです。意味が同じなのであれば一種類のノードにまとめることができます。RubyではこれらをNODE_IFという1つのノードで扱っています。

またunlessについてもNODE_IFを用いて表現することが可能です。条件を満たすときに実行するコードとそうでないときのコードを逆にすることでNODE_IFとして処理できます。

unless a == 1
  p :t
else
  p :f
end

# =>

if a == 1
  p :f
else
  p :t
end

実際Ruby 2.5以前では #define NEW_UNLESS(c,t,e) NEW_IF(c,e,t) というように2つのコードを入れ替えることでunlessをNODE_IFで表現していました。

github.com

抽象構文木

コードの実行を目的とする場合には、入力されたプログラムの構造の一部を抽象化することができます。このような構文木を抽象構文木と呼びます。本来、抽象構文木はプログラムの意味に関する情報のみを残した構文木ですが、プログラミング言語の開発を続けていくと意味以外の情報が付け足されることがあります。

Rubyの抽象構文木でいうとNODE_UNLESS以外にノードの位置情報があげられます。位置情報はプログラムの意味に関係ないので抽象構文木に含めなくてもプログラムを実行することができます。しかし実際にはエラーや警告、カバレッジライブラリの実装などのために位置情報が必要になり、抽象構文木に位置情報を持たせています。

このようにRuby本体の抽象構文木も必要に応じてアドホックに拡張されてきました。

抽象構文木の辿り方

構文木のユースケースを考えるときには構文木にどのような情報を含める必要があるかという点だけでなく、構文木をどのように辿るかという点にも注意が必要です。いまのRubyはコードを実行するさいに構文木からバイトコードを生成し、そのバイトコードを実行するという手順をとります。 obj.m(1, 2)というコードを考えてみましょう。対応する構文木は以下の通りです。

この構文木から次のようなバイトコードを生成します。

0000 ~ 0001: objを評価する
0003 ~ 0004: 引数の1と2を準備する
0006: #mメソッドを呼び出す

== disasm: #<ISeq:<main>@-e:1 (1,0)-(1,11)>
0000 putself                                                          (   1)[Li]
0001 opt_send_without_block                 <calldata!mid:obj, argc:0, FCALL|VCALL|ARGS_SIMPLE>
0003 putobject_INT2FIX_1_
0004 putobject                              2
0006 opt_send_without_block                 <calldata!mid:m, argc:2, ARGS_SIMPLE>
0008 leave

構文木をバイトコードにコンパイルするときのことを考えてみましょう。メソッドの呼び出しを表すNODE_CALLのコンパイルは大きく3つのステップからなります。まずレシーバーのobjに対応するバイトコードを生成します。つぎに引数の1, 2に対応するバイトコードを生成します。さいごにメソッドのmを呼び出すバイトコードを生成します。このように構文木を上から下へと辿りながらバイトコードを生成します。

コードを解析するための構文木

構文木を扱うのが型システムやコンパイラだけであればよかったのですが、近年構文木を扱いたいというユースケースは拡大しています。 LSPやlinterやcode formatterといったツールもまた構文木を扱います。その結果、これらのツールも視野にいれた構文木を設計し直す必要が生じてきました。

LSPの場合

ruby-lsp gemを参考に、LSPのユースケースを見ていきましょう。

トークンを解析する

例えばSemanticTokensはSyntax Highlightをする機能です。以下のようなコードがあったときに、def, foo, 1, +といった各トークンについて、位置情報とトークンの種別をサーバーが返します。そのためには各トークンの位置情報や種別に関する情報を持っておく必要があります。

def foo
  1 + 2
end

コメントを解析する

LSPの機能のなかにはコメントの内容を解析したり、コメントの位置情報を利用する機能があります。

DocumentLinkはコード中のドキュメントを解析し、その中にあるlinkの情報を返す機能です。この機能を実装するためには少なくともコメントの内容と位置情報を取得できるようにする必要があります。もし全てのコメントではなく、メソッド定義やクラス定義のコメントだけを対象にしたい場合などには、コメントとノードを結びつけられるようにしておく必要があります。

FoldingRangeはクラス定義やメソッド定義などの単位で、表示を畳み込めるようにする機能です。コメントを畳み込めるようにするためには、コメントの位置情報を取得できるようにする必要があります。

コードを書き換える

LSPの機能のなかにはコードの一部を書き換える機能があります。コードを書き換えるといってもLanguage Serverがファイルを直接書き換えるわけではなく、TextEditというレスポンスで変更する範囲(range)と変更する内容(newText)を指定します。

ruby-lsp gemはCodeActionResolveをサポートしています。この機能はCodeActionと組み合わせて、警告されたコードの修正やリファクタリングなどいろいろなアクションを実装することができます。ここではリンク先のgif動画にもあるExtract Variableを見てみましょう。

以下のように新しい変数を導入して1 + 1を置き換えるというケースを考えてみましょう。このとき内部では3つのステップで変更内容を計算します。

代入式に対応するコードを生成する (new_variable = 1 + 1)
元のコードを新しい変数で置き換える
1で作ったコードを2のコードの前に挿入する

# Before:
1 + 1

# After:
new_variable = 1 + 1
new_variable

この書き換えという操作はコメントが絡むと少し考えることが増えます。操作の前後でコメントが消えたり、重複したりしないように気をつけて編集する必要があります。

# Before:
"!!" + obj.to_s + "!!" # Decorate string

# After:
new_variable = obj.to_s
"!!" + new_variable + "!!" # Decorate string

コードの書き換えを実装するためには、選択された範囲に対応するコードを取得できるようにする必要があります。またそのときにコメントや空白といった直接ノードに関係のない情報も扱える必要があります。

ここでコード書き換えの難しさについて触れておきましょう。 Extract Variableという機能を実装するときにどのような手順で書き換えればよいでしょうか。例えば

var = 指定された範囲というコードを一つ上の行に追加する
指定された範囲をvarで置き換える

という手順で書き換えるとしましょう。この方法ではうまくいかないケースがあります。ワンライナーのブロック内部のリファクタリングでは1行上に変数を定義してしまうと意図しない結果になります。

# i + 1 をExtract Variableする

# Before
10.times {|i| i + 1 }

# After
var = i + 1 # 1. `var = 指定された範囲`というコードを一つ上の行に追加する
10.times {|i| var }

# 期待する結果
10.times {|i| var = i + 1; var }

ワンライナーのブロックの場合は指定された範囲の前にvar = 指定された範囲;を追加する。という手順を加える必要がありそうです¹。ワンライナーだったらという判定基準も実は曲者で、厳密にはブロックの開始行と選択範囲の行が同じかどうかを判定する必要があります。そうしないと特殊なケースでブロックの外側に変数定義を括り出すことになります。

他にも複数行が選択されたときのコード書き換えは思わぬ結果を生むことがあります。

テキストファイルをいじるようにコードを書き換えるというのは実はエッジケースが多くて難しいということがわかっていただけたのではないでしょうか。

LSPの他の機能としてはFormattingやOnTypeFormattingもコードの書き換えを行う機能です。

ruby-lspの内部ではRuboCopを使用している場所もあるので、コードの書き換えに関してはRuboCopのユースケースを紹介するときに再度取り上げます。

構文木、下から見るか？上から見るか？

構文木からバイトコードを生成するときは、構文木の頂点から下にノードを辿っていけばよいのでした。ではLSPの機能を実装するときも同様に上から下へとノードを辿るのでしょうか。それとも下から上へと辿る必要があるのでしょうか。結論を言うとどちらの操作も必要です。

例えば次の機能を提供するときは、構文木を上から下へと辿っていくことになります。

一例としてFoldingRangesを見てみましょう。これはclass ... endやdef ... endという単位で表示を折りたたむ機能です。折りたたむ範囲を計算するさいには構文木を上から辿っていき、NODE_CLASSやNODE_DEFといったノードに遭遇するたびにその範囲を計算するという実装が自然な実装になるでしょう。

一方で次の機能では構文木の中の特定の位置から上へと辿っていくことになります。

例えばSelectionRangeを見てみましょう。これは徐々に選択範囲を広げたり狭めたりする機能です。

class C
  def m
    obj.m1
  end
end

最初にobj.m1を選択しているとして

obj.m1
def m ... end
class C ... end

と徐々に選択範囲が広がっていきます。Language ServerはレスポンスとしてSelectionRangeというデータ構造を返します。 parent?とあるようにこれは内側(子)の選択範囲から外側(親)の選択範囲への参照を持ちます。実装するさいには対象となるノードを取得し、そこから上へ構文木を辿りながらSelectionRangeを構築するという実装が自然な実装になるでしょう。

DocumentHighlightは選択された変数などをハイライトするための機能です。例えばローカル変数やインスタンス変数の代入及び参照をハイライトしたいとします。どのスコープでハイライトするかはLSPの実装によると思いますが、ローカル変数(bar)は同一メソッドの内部のものをハイライトし、インスタンス変数(@foo)は同一クラスの内部のものをハイライトするとしましょう。この場合は構文木を下から上、そして上から下へと辿って解析を進めるのが良さそうです。

4行目のbarが選択されたとしましょう。このときメソッドm1の中にあるローカル変数bar、つまり4行目と5行目のbarをハイライトします。 4行目のNODE_LASGNからスタートし、ノードを上へと辿っていきます。ローカル変数のスコープはメソッドの中なので、メソッドm1を定義しているNODE_DEFNを見つけたらそれより上のノードを辿る必要はありません。m1の中でbarを使用している場所をすべて洗い出すために、NODE_DEFNを起点に下へとノードを辿っていき、barを使用している箇所を見つけてレスポンスに含めます。

次に3行目の@fooが選択されたときのことを考えてみましょう。今度はm1とm2の2つのメソッドの中にあるインスタンス変数@fooをハイライトします。先ほどと同様に3行目のNODE_IASGNからスタートし、ノードを上へと辿っていきます。インスタンス変数は同じクラスの中の複数のメソッドで使われることがあるので、NODE_DEFNではなくさらに上のNODE_CLASSまでノードを上へ辿ります。そしてそこからノードを下へと辿ってメソッドm1とm2の中で@fooを使用している箇所を見つけてレスポンスに含めます。

class C
  def m1
    @foo = 1
    bar = 0
    bar + 1
  end

  def m2
    @foo + 1
    bar = 0
    bar + 1
  end
end

RuboCopの場合

つづいてlinterやcode formatterの代表的なユースケースとしてRuboCopを見てみましょう。

まずはlinterとしてのRuboCopです。例としてStyle::IfInsideElseを見てみましょう。 IfInsideElseは以下のような深いネストを警告してくれるCopです。

# lib/rubocop/cop/style/if_inside_else.rb

# bad
if condition_a
  action_a
else
  if condition_b
    action_b
  else
    action_c
  end
end

# good
if condition_a
  action_a
elsif condition_b
  action_b
else
  action_c
end

Copではまずチェック対象となるノードを検索します。 IfInsideElseのチェック対象はIfノードなのでdef on_if(node) ...というメソッドを定義して、Ifノードが来たときにメソッドが呼び出されるようにします。 IfInsideElseはunlessや三項演算子を対象にしませんが、内部で使っているparser gemではunlessや三項演算子をIfノードで表現しています。そのため#on_ifの先頭でnodeの種類を細かくチェックしてunlessや三項演算子のケースを排除します。またIfInsideElseにはAllowIfModifierというオプションがあります。このオプションの値によってelse句が後置ifのときの振る舞いが変わります。ということはelse句が後置ifかどうか判定する必要があります。

このような理由からRuboCopではparser gemのParser::AST::Nodeを継承したRuboCop::AST::Nodeというクラスをつくり、三項演算子かどうかを判定する#ternary?や、後置ifかを判定する#modifier_form?などのメソッドを独自に定義しています。

コードを実行することを目的としたときは通常のif, 後置if, 三項演算子を区別する必要はありませんでした。しかしlinterを実装するときにはそれらのifを区別したいケースもあります。ただし常に細かい粒度でノードを分割するのがいいというわけではありません。たとえばネストした三項演算子の使用を警告するNestedTernaryOperatorでは三項演算子の場合のみを対象にしたい一方で、条件式がリテラルであったときに警告するLiteralAsConditionでは全てのタイプのifを対象にしたいといったように、どのような粒度でノードを検索したいかは実装するルールに大きく依存します。

各種ノードに対してSyntaxからみたときのノードの種類と、Semanticsからみたときのノードの種類の2つの情報を持たせられるとよさそうです。

つづいてRuboCopのcode formatterとしての側面を見ていきましょう。 RuboCopにおけるコードの書き換えはcorrectorというオブジェクトへの操作という形をとります。 correctorはRuboCop::Cop::Correctorのインスタンスであり、このクラスはParser::Source::TreeRewriterというparser gemのクラスを継承しています。 TreeRewriterの提供する#replace(range, content), #remove(range), #insert_before(range, content), #insert_after(range, content)といったメソッドを使用してコードの書き換えを行ないます。これらのメソッドは書き換える範囲を表すrangeと書き換え後の内容を表す文字列contentを引数に取ります。

IfInsideElse#correct_to_elsif_from_if_inside_else_formを起点に# badなコードを# goodなコードに書き換えてみます。

(1) 書き換え前のコードです
(2) 118行目で親ノードのelseをelsif condition_bに置き換えます
(3) 123行目でif condition_bをaction_bで置き換えることで、if condition_bを削除します
(4) 102行目で内側のifの末尾にあるendを削除します
(5) 106行目で重複したaction_bを削除してコード全体の書き換えが完了します

TreeRewriterのアプローチにはおおきく2つの問題があります。

`TreeRewriter`の実装の複雑さ

ひとつめの問題点はTreeRewriterの実装がそれなりに複雑だということです。 TreeRewriterをつかってコードを書き換えると言っても、#replace(range, content), #remove(range)といったメソッドが直接文字列を編集するわけではありません。それぞれのメソッド呼び出しはTreeRewriter::Actionというインスタンスを作ります。最終的にTreeRewriter#processが呼び出されたときに、いままでに作ったActionを並び替えて適用し置換後の文字列を生成します。

このような複雑なことをしているのには2つの理由があると思います。

ひとつは文字列を都度書き換えるとコストが高いことです。文字列の途中に新しい文字列を削除・挿入したり、文字列の途中の一部を他の文字列で置き換えると、変更のあった箇所から後方の文字列の位置がずれることがあります。その場合は後方の文字列全体を移動しないといけません。 Auto Correctをするたびにそのようなコストを払うことは可能なら避けたいです。

もうひとつは文字列を直接書き換えると他のノードに影響するからです。 RuboCopのNodeはParser::AST::Nodeを継承したクラスで、Parser::AST::NodeはParser::Source::MapとParser::Source::Rangeを経由してソースコードの文字列を持っているParser::Source::Bufferを参照しています。つまりNodeは自身の範囲をもち、Parser::Source::Bufferからその範囲をとってくることでNodeに対応するコードが手に入るというわけです。 IfInsideElseの実装からもわかるように、ソースコードを編集(corrector#replaceなどの呼び出し)とノードに対応するソースコードの取得(#sourceの呼び出し)の両方が一回の書き換えの中で発生します。もし文字列を直接書き換えてしまうと#sourceの呼び出し結果が意図しないものになってしまいます。

これらの理由から編集作業をオブジェクトとして保存しておき、最後にまとめて新しいソースコードを生成するというアプローチをとっているのだと思います。

テキスト編集の煩雑さ

TreeRewriterのアプローチのふたつめの問題点は、テキストの編集が煩雑だということです。テキストを編集するようにコードの書き換えを行う場合、各操作を1ステップずつ理解していまどこまで書き換えたか理解していないといけません。またruby-lspのExtract Variableの説明でも触れたように、テキストを意識した編集はエッジケースにおいて意図しない結果を生み出しがちです。

構文木を編集することでコードを書き換える

せっかく構文解析を行ってソースコードから構文木を得ているのですから、構文木の構造を利用してコードを書き換えることはできないのでしょうか。例えばさきほどの# badなコードを# goodなコードに書き換えるケースを構文木の視点からみると以下のような操作になります。

NODE_IFの子要素であるNODE_ELSEからその唯一の子要素であるNODE_IFを取り出してNODE_ELSIFに置き換えて、親のNODE_IFのelse属性に紐づけるという操作であることがわかります。書き換えた後の構文木からソースコードを生成(復元)することができれば、RuboCopのそれぞれのCopでは構文木の構造を書き換えることに集中できます。 Copをノード書き換えで実装する場合、以下のようなコードになります。

def autocorrect(node)
  # Assume node.else has single If statement
  if_node = node.else_node.body[0]
  new_node = Node::Elsif.new(
    if_node.condition,     # condition
    if_node.then_node,     # then
    if_node.else_node.body # else
  )
  node.else_node = new_node
end

ruby-lspのExtract Variableについて再び考えみましょう。 1行上に変数代入のコードを挿入するというアプローチではエッジケースではうまくいかないことがあるのでした。構文木を編集することでExtract Variableを実装するとどうなるのでしょうか。

var = 指定された範囲というノード(NODE_LASGN)を一つ手前に追加する
指定された範囲のノードをNODE_LVARで置き換える

構文木の書き換えの場合、変数の代入式がブロックの子要素として表現されるので必ずブロックの内側に展開されます。先ほどのようにブロックの外側に変数の代入が飛び出てしまうことはありません。

では構文木からソースコードを生成するには何が必要なのでしょうか。各ノードがifやelseといったトークン、そして空白やコメントといったトークンにならない文字列の両方を漏れなく重複なく保持していれば、そのノードに対応するソースコードを生成することができます。

実は先ほどのノードを書き換えるコードには1つ欠けている要素があります。それはどのようにして新しいノードの位置情報を計算するかという点です。今日の実用的なノードは、多くの場合自分の位置情報を持っています。なのでElsifのinitializeメソッドはノード全体の位置情報を引数にとるようになっているはずです。

class Elsif
  def initialize(cond_node, then_node, else_node, loc)
  end
end

ここでは位置情報を{first_lineno, first_column, last_lineno, last_column}の組み合わせで表現することにしましょう。開始位置および最後の行番号は親ノードのelseを基準に計算し、最後の行のカラム番号は自身のelseからインデント1つ分を削った値を計算します。

def autocorrect(node)
  # Assume node.else has single If statement
  if_node = node.else_node.body[0]
  new_loc = Location.new(
    node.else_node.loc.first_lineno,  # first_lineno
    node.else_node.loc.first_column,  # first_column
    if_node.loc.last_lineno      - 1, # last_lineno
    if_node.else.loc.last_column - 2  # last_column
  )
  new_node = Node::Elsif.new(
    if_node.condition,     # condition
    if_node.then_node,     # then
    if_node.else_node.body # else
    new_loc                # loc
  )
  node.else_node = new_node
end

うまく計算できているように見えますが、ふたつ問題があります。

ひとつめの問題は位置情報の計算が煩雑だということです。もとのコードと生成されるコードをイメージしながら位置情報を考えないといけません。今回の例でいえば親ノードのelseの位置とaction_cの位置を基準に新しいノードの位置情報を計算しました。せっかくノードを書き換えるようにしたのに、位置情報を考えるときにテキストを意識した編集に似たようなことをしています。

ふたつめの問題はすでにあるノードについても位置情報を計算し直さないといけないことです。 Elsifの子ノードであるif_node.conditionなどのノードの位置ももとの状態から変わっています。また親のIfノードの位置が変わっているのですから、それ以降のノードの位置も全て変わっています。これらを適切に書き換えないと後続の処理の中で作られる新しいノードの位置情報が正しく計算できなくなってしまいます。

ノードの書き換えをする場合には部分的な書き換えによって他のノードの位置情報を再計算しなくていいように、位置情報の表現方法を工夫する必要がありそうです。

ここまでRuboCopについてみてきましたが、コードの書き換えというのはcode formatterに限りません。例えばRSpec 2からRSpec 3への移行の際にはTranspecというmigration toolが提供されました。

rspec.info

まとめ: 構文木はどのように使われるのか

ruby-lspとRuboCopを例に構文木に対して行いたい操作をみてきました。まとめると次のような要望を満たす機能を提供する必要があります。

親ノードから子ノード、子ノードから親ノードの両方向に辿りたい
トークンの位置情報を取得したい
コメントの内容や位置情報を取得したい
各種ノードに対してSyntaxからみたときのノードの種類と、Semanticsからみたときのノードの種類の2つの情報を持たせたい
ノードの書き換えを行うことで、コードの書き換えを行いたい
- ノードの持っている情報のみを用いて元のコードを完全に復元したい
- ノードの書き換えによってほかのノードの位置情報を更新するような事態は避けたい

抽象構文木を超えて

LSPやcode formatterにおける構文木の使われ方を考えると、既存の抽象構文木では機能が不足していることがわかりました。これらの問題を解決するための構文木の設計方法として具象構文木が、構文木の実装方法としてRed Green Treeというデータ構造があります。それぞれ詳しくみていきましょう。ちなみにこれらの組み合わせを用いているプログラミング言語やツールに以下のものがあります。

抽象構文木から具象構文木へ

まずは具象構文木(Concrete Syntax Tree: CST)を見ていきましょう。具象構文木によって、"ノードの持っている情報のみを用いて元のコードを完全に復元したいという"という要望を叶えることができます。

具象構文木のポイントは3つにまとめられます。

トークンを表すデータ構造を導入する
lexerで落としてしまう情報をトークンに紐づける
ノードがトークンを持つようにする

空白やコメントはあらゆるノードのあらゆる地点に出現することがあるので、ノードの情報として直接扱うのは構文解析の面からすると煩雑です。空白などをトークンに紐づく情報として管理することで、構文解析のさいにはトークンとノードを今まで通り扱うことができます。

トークンを表すデータ構造を導入する

いままで抽象構文木ではノードを表すデータ構造を定義して使用してきました。具象構文木ではさらにトークンを表すデータ構造を定義します。

トークンの種別を表すenum token_typeと対応する文字列であるstring *textを持ったstruct Tokenを導入しましょう²。

enum token_type {
    TOKEN_CLASS,
    TOKEN_MODULE,
    ...
};

struct Token {
    enum token_type type;
    string *text;
};

lexerで落としてしまう情報をトークンに紐づける

つぎに空白や改行、コメントといったlexerレベルで落としてしまう情報を扱うためのデータ構造を用意します。具象構文木の文脈ではこれらの情報を"Trivia"と呼ぶことが多いので、この記事でもTriviaと呼ぶことにします³。

struct Trivia {
    string *text;
};

トークンとTriviaを紐づけるためにstruct Tokenを拡張します。トークンはその前後にTriviaをもつことがあるので、leading_triviaとtrailing_triviaの2つのフィールドを追加します。

struct Token {
    enum token_type type;
    string *text;
    struct Trivia *leading_trivia;
    struct Trivia *trailing_trivia;
};

ノードがトークンを持つようにする

トークンとTriviaを管理するデータ構造を定義できたので、最後にノードとトークンを紐づけましょう。ここではノードの構造体にフィールドを足しておきましょう。

typedef struct RNode_IF {
    NODE node;

    struct Token *if_token;
    struct RNode *nd_cond;
    struct Token *then_token;
    struct RNode *nd_body;
    struct RNode *nd_else;
    struct Token *end_token;
} rb_node_if_t;

このように3つの変更を加えることで、ノードからトークンにアクセスできるようになり、そのトークンからTriviaにアクセスできるようになりました。

Triviaの設計において、あるTriviaを左右どちらのトークンに紐づけるかという点は注意が必要です。ここではSwiftの設計を参考にします。 Swiftでは2つのルールに従ってTriviaの所属するノードを決定します。

トークンは自身のあとに続くTriviaを保持する。このとき改行文字は含まない。
1で所属の決まらないTriviaはその直後のトークンに所属する

以下のようなコードを考えてみましょう。

if cond
  a = 1 + 2
end

特徴的なトークンとそのTriviaの関係は次のとおりです。

if
- leading_trivia: なし
- trailing_trivia: 空白1文字
cond
- leading_trivia: なし
- trailing_trivia: なし
a
- leading_trivia: 改行1文字と空白2文字
- trailing_trivia: 空白1文字

このルールは2つの点で優れています。

ひとつはコメントの扱いが直感的であることです。

def m1
end

# Comment for method m2
# In some cases, this is RDoc.
# In other case, this is type information...
def m2
  expr # comment for expr
end

このようなコードがあったとき、4-6行目のコメントは2つめルールに従って7行目のdefのleading_triviaになります。これはm2のメソッド定義に対するコメントであってほしいというユースケースに合致しています。

もうひとつはleading_triviaをみることで、そのトークンが行の最初のトークンかどうか判別できることです。

class C
  def m
    var = 1
  end
end

この例ではdef, var, end, endのleading_triviaに改行が含まれます。そしてそれらのトークンはすべて各行の最初に出現するトークンです。この特徴はインデントの計算を行うときに便利です⁴。

Red Green Tree

Triviaとトークン用のデータ構造を用意することで、構文木がコメントやトークンの情報をもてるようになりました。これによりトークンの位置情報の取得、コメントの内容と位置情報の取得、ノードの持っている情報のみを用いて元のコードを完全に復元することができるようになりました。

親ノードから子ノード、子ノードから親ノードの両方向に辿りたい
~~トークンの位置情報を取得したい~~
~~コメントの内容や位置情報を取得したい~~
各種ノードに対してSyntaxからみたときのノードの種類と、Semanticsからみたときのノードの種類の2つの情報を持たせたい
ノードの書き換えを行うことで、コードの書き換えを行いたい
- ~~ノードの持っている情報のみを用いて元のコードを完全に復元したい~~
- ノードの書き換えによってほかのノードの位置情報を更新するような事態は避けたい

残る要望のうちノードの書き換えと子ノードから親ノードへのアクセスを叶えるための構文木の実装方法が、C# (Roslyn)で発明されたRed Green Treeです。 Red Green Treeの特徴をまとめておきましょう⁵。

Red NodeとGreen Nodeという2つの異なるデータ構造を用いて構文木を表現する
Green Nodeは子ノード(Green Node)およびトークンへの参照をもつ
Green Nodeは自身をテキストで表現したときの幅(width)をもつ
Red Nodeは子ノード(Green Node)に加えて親ノード(Red Node)への参照をもつ
Red Nodeはファイルの先頭からの位置情報(offset)をもつ
Red Nodeの構築は必要に応じてlazyに行う
Red NodeもGreen Nodeもimmutableでpersistentなデータ構造とする
構文木のユーザーにはRed Nodeのみを公開し、Green Nodeはinternalなデータ構造とする

ちなみにpersistence-facades-and-roslyns-red-green-treesによると、赤緑木という名前はデータ構造を議論していたときに使っていたマーカーの色に由来しており、それ以上の意味はないようです。

Incidentally, these are called "red/green trees" because those were the whiteboard marker colours we used to draw the data structure in the design meeting. There's no other meaning to the colours.

Green Node

Green Nodeは子ノード(Green Node)およびトークンへの参照をもつデータ構造です。普段イメージする構文木のノードに近いデータ構造だと思います。特徴的なのはoffsetとしての位置情報を持たず、代わりに自身の幅(width)を持っていることです。 offsetはファイルの先頭からの位置情報を蓄積したものなので、ソースコードを書き換えるときにあるノードに対する変更が他の兄弟ノードのoffsetに影響することがあるのでした。一方で幅というのは子ノードおよびトークンから計算可能であり、ノードに閉じた範囲で計算することができます。あるノードに対する変更が後続のノード(兄弟ノード)の幅に影響することはありません。子ノードの幅が変わると親ノードの幅も変わるため、子ノードが変更されたときに親ノードを更新していく必要がありますが、変更のあったノードからrootノードまでを更新するだけですみます⁶。

Red Node

Red NodeはGreen Nodeのwrapperです。 Green Nodeへの参照以外に親のRed Nodeへの参照とファイルの先頭からの位置情報(offset)をもちます。 Red Nodeの作成は必要になるときまで遅延されます。具体的にはRedNode#childrenが呼び出されたときにはじめて、子ノードのRed Nodeのインスタンスを作成します。

class RedNode
  def children
    offset = @offset

    @green_children_nodes.map do |g|
      RedNode.new(parent: self, green_node: g, offset: offset)
      offset += g.width
    end
  end
end

Red NodeのNODE_IFはそれ以前にトークンがないのでoffsetが0になっています。 NODE_ELSEはGreen NodeのNODE_ELSEより前のノードのwidthを足し合わせた分(3 + 11 + 11 = 25)だけoffsetがずれています。

Red Green Treeに対するコード書き換え

先ほどのCopを例にRed Green Treeを利用したときのノードの書き換えについてみてみましょう。書き換え前後のコードを再掲します。

# bad
if condition_a
  action_a
else
  if condition_b
    action_b
  else
    action_c
  end
end

# good
if condition_a
  action_a
elsif condition_b
  action_b
else
  action_c
end

ノードを書き換えるコードは以下のようになります。

def autocorrect(node) # node is top level IF Node
  # Assume node.else has single If statement
  if_node = node.else_node.body[0]
  elsif_node = Node::Elsif.new(
    Token::Elsif.new(leading_trivia: "\n", trailing_trivia: " "),
    if_node.condition_node,
    if_node.then_node,
    Token::Else.new(leading_trivia: "\n"),
    if_node.else_node.body
  )
  return Node::If.new(
    node.if_token,
    node.condition,
    node.then,
    elsif_node,
    node.end_token
  )
end

書き換えによって新しく作られたノードを図の右側にまとめておきました。

NODE_IFとNODE_ELSIFに対応するRed NodeとGreen Node、およびELSIFとELSEトークンが作られます。 condition_aやaction_aに対応するGreen Nodeなど、多くのGreen Nodeが再利用されていることがわかります。

このようにノードに局所化された情報はGreen Nodeに、そうでない情報はRed Nodeに保持するようにすることでノードの書き換えの影響範囲を狭くすることができます。またRed NodeとGreen Nodeをimmutableなデータとして扱うことで、書き換え前後で変化のないノードやトークンについては安心して再利用することができます。

具象構文木と抽象構文木の両立

最後に残った要望について考えましょう。

各種ノードに対してSyntaxからみたときのノードの種類と、Semanticsからみたときのノードの種類の2つの情報を持たせたい

ここではノード(Green Node)にSyntaxとSemanticsの2つのtypeを持たせ、helper関数を定義します。再びifを表すノードを考えてみましょう。 enum node_syntax_typeはそれぞれのノードで異なりますが、enum node_semantics_typeは共通した値(例えばNODE_SEMANTICS_IF)を持ちます。

/* 普通のif */
typedef struct RNode_IF {
    enum node_syntax_type;
    enum node_semantics_type;

    struct Token *if_token;
    struct RNode *nd_cond;
    struct Token *then_token;
    struct RNode *nd_body;
    struct RNode *nd_else;
    struct Token *end_token;
} rb_node_if_t;

/* 後置if */
typedef struct RNode_IF_MODIFIER {
    enum node_syntax_type;
    enum node_semantics_type;

    struct RNode *nd_cond;
    struct Token *if_token;
    struct RNode *nd_body;
} rb_node_if_modifier_t;

/* 三項演算子 */
typedef struct RNode_IF_TERNARY {
    enum node_syntax_type;
    enum node_semantics_type;

    struct RNode *nd_cond;
    struct Token *question_token;
    struct RNode *nd_body;
    struct Token *colon_token;
    struct RNode *nd_else;
} rb_node_if_ternary_t;

例えばこれらのノードから共通して条件式を抽出するための関数としてnode_if_conditionを定義します。

static NODE *
node_if_condition(const NODE *node)
{
    switch (nd_type(node)) {
      case NODE_IF:
        return RNODE_IF(node)->nd_cond;
      case NODE_IF_MODIFIER:
        return RNODE_IF_MODIFIER(node)->nd_cond;
      case NODE_CALL:
        return RNODE_IF_TERNARY(node)->nd_cond;
      default:
        rb_bug("unexpected node: %s", ruby_node_name(nd_type(node)));
    }
}

こうすることでユースケースに応じてSyntax、Semanticsそれぞれのノードとして扱うことができるようになります。

Rubyに実装するにあたって

設計の大まかな方針は決まりましたが、Rubyに実装するにあたっては細かい部分でいくつか詰めておくべきことがあります。

例えば具体的にどの文字をtriviaとするか。ヒアドキュメントをどう表現するか。どのようなライブラリを提供するかといった点です。

triviaについては例えば改行(\n)をどう扱うかという問題があります。 Rubyでは改行がトークンとして扱われたり扱われなかったりします。トークンとして扱われているものはトークン、そうでないものはtriviaとして扱うという方法と、すべてをtriviaとして扱うという方法が考えられます。

ヒアドキュメントについては1行に二つ以上ヒアドキュメントがあったときでも元のコードを復元できるようにしないといけません。

ライブラリについては例えばRewriterを提供することが考えられます。 C#やSwiftではノードの効率的な書き換えをサポートするためにRewriterを提供しています⁷。 Rewriterの実装には汎用的なロジックが含まれるので、言語のコアに近いところで提供する価値があるでしょう。

今回の記事はだいぶ長くなってしまったので簡単に触れるだけにとどめ、別の機会に詳しくお話することにしましょう。

まとめ

これまで構文木は新しいユースケースが出てくる度にアドホックに拡張されてきました。そこで今回は構文木を設計するとはどういうことか探求するためにまずユースケースを調べて構文木が提供すべき機能を整理しました。主なユースケースとしてコードを実行するケースとコードを解析するケースにわけて構文木の使われ方とそのために必要な機能を考えました。とくにコードを解析するケースにおいては以下の4つの機能が必要であることがわかりました。

親ノードから子ノード、子ノードから親ノードの両方向にアクセスしたい
トークンの種別や位置情報、コメントの内容や位置情報にアクセスしたい
ノードの書き換えによってコードの書き換えを行いたい
各種ノードに対してSyntaxからみたときのノードの種類と、Semanticsからみたときのノードの種類の2つの情報を持たせたい

これらの機能を提供するために3つのアイデアを紹介しました。

Triviaを含めた具象構文木の定義と実装方法。これによりトークンの種別や位置情報、コメントの内容や位置情報を提供するとともにノードからソースコードが復元可能になります。
Red Green Tree。これにより親ノード・子ノード間での両方向のアクセスを提供するとともに、ノードの書き換えを現実的な方法で実装可能にします。
Semanticsに関する情報をノードに埋め込む。これにより文法定義に即した構文木を作りつつ、コンパイラなどに対して抽象度の高い構文木を提供することができます。またLinterに対しては柔軟な検索方法を提供できます。

実際にRubyに実装するにあたっては具体的なtriviaの内容を決めたりヒアドキュメントのことを考えたりと、Ruby固有の論点を整理する必要があります。これについてはまた次回以降の記事で書いていきたいと思います。

リンク集

LSPに関するリンク

Ruby LSP documentation
- ruby-lspのドキュメントサイト。gifアニメーションを用いてそれぞれの機能をわかりやすく説明している
Specification
- LSPの仕様に関する公式サイト。リクエストやレスポンスの仕様を調べるときなどに使う
Language Server Protocol の仕様及び実装方法
- LSP 3.17の仕様と実装方法を解説している
User Manual
- RustのLSP実装であるrust-analyzerの機能一覧

具象構文木(CST)やRed Green Treeに関するリンク

Persistence, façades and Roslyn’s red-green trees | Fabulous adventures in coding
- C# (Roslyn)のRed Green Treeについて書かれたポスト。
Roslyn Immutable Trees · KirillOsenkov/Bliki Wiki · GitHub
- Roslyn CodePlex discussions archive からスレッドをサルベージしたまとめ記事
swift/lib/Syntax at release/5.7 · swiftlang/swift · GitHub
- SwiftのRed Green Tree実装およびTriviaの実装について書かれている。
A New Swift Parser for SwiftSyntax - Source Tooling - Swift Forums
- swift-syntaxのゴールやDesign philosophyについて書かれている。
rust-analyzer/docs/dev/syntax.md at 2024-08-05 · rust-lang/rust-analyzer · GitHub
- rust-analyzerのRed Green Tree実装およびTriviaの実装について書かれている。Alternative designsとして他の言語における実装との比較なども書かれている。
Red Green Syntax Trees - an Overview - Plingdollar
- Red Green Treeについて書かれたポスト。(Green )Tokenに対応するRed Token(ポストではSyntaxToken)を定義している。

実際ruby-lspではonelinerのblockかどうかのチェックをしている ↩
より具体的な実装が知りたい場合はたとえばSwiftのTokenSyntaxやTokenKindを参照↩
より具体的な実装が知りたい場合はたとえばSwiftのTriviaやTriviaPieceを参照↩
RoslynのケースはHow are comments stored in the syntax tree and how to use the Syntax Visualizer?を、TypeScriptのケースはTypeScript Deep Diveを参照↩
rust-analyzerのドキュメントがわかりやすい↩
ノードを書き換えた時に内部的に起きることについてはC#の場合はCreate a modified treeが、Swiftの場合はSyntax.replacingSelfのコメントが参考になる。どちらのケースもrootまでRed Nodeを辿りながら新規にRed Nodeを作っていく↩
CSharpSyntaxRewriterおよびSyntaxRewriterを参照↩

かねこにっき

Ruby Parser開発日誌 (19) - 最高の構文木の設計 2024年版

はじめに

構文木の使われ方の変遷

parserの生成物

構文木とはなにか

コードを実行するための構文木

抽象構文木

抽象構文木の辿り方

コードを解析するための構文木

LSPの場合

トークンを解析する

コメントを解析する

コードを書き換える

構文木、下から見るか？上から見るか？

RuboCopの場合

`TreeRewriter`の実装の複雑さ

テキスト編集の煩雑さ

構文木を編集することでコードを書き換える

まとめ: 構文木はどのように使われるのか

抽象構文木を超えて

抽象構文木から具象構文木へ

トークンを表すデータ構造を導入する

lexerで落としてしまう情報をトークンに紐づける

ノードがトークンを持つようにする

Red Green Tree

Green Node

Red Node

Red Green Treeに対するコード書き換え

具象構文木と抽象構文木の両立

Rubyに実装するにあたって

まとめ

リンク集

LSPに関するリンク

具象構文木(CST)やRed Green Treeに関するリンク

はじめに

構文木の使われ方の変遷

parserの生成物

構文木とはなにか

コードを実行するための構文木

抽象構文木

抽象構文木の辿り方

コードを解析するための構文木

LSPの場合

トークンを解析する

コメントを解析する

コードを書き換える

構文木、下から見るか？上から見るか？

RuboCopの場合

TreeRewriterの実装の複雑さ

テキスト編集の煩雑さ

構文木を編集することでコードを書き換える

まとめ: 構文木はどのように使われるのか

抽象構文木を超えて

抽象構文木から具象構文木へ

トークンを表すデータ構造を導入する

lexerで落としてしまう情報をトークンに紐づける

ノードがトークンを持つようにする

Red Green Tree

Green Node

Red Node

Red Green Treeに対するコード書き換え

具象構文木と抽象構文木の両立

Rubyに実装するにあたって

まとめ

リンク集

LSPに関するリンク

具象構文木(CST)やRed Green Treeに関するリンク

`TreeRewriter`の実装の複雑さ