[インデックス 14575] ファイルの概要

このコミットは、Goコンパイラのパーサーにおける、else if文の長いチェーンが原因で発生するスタックオーバーフローのバグを修正するものです。具体的には、src/cmd/gc/go.y (Bisonの文法定義ファイル)、src/cmd/gc/y.tab.c (Bisonによって生成されたパーサーのCソースコード)、src/cmd/gc/y.tab.h (パーサーのヘッダーファイル)、src/cmd/gc/yerr.h、そしてバグを再現するためのテストケースtest/fixedbugs/issue2615.goが変更されています。

コミット

commit 9146ac14ee1e7516e2bb4212c0fcf054c6dde640
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Thu Dec 6 08:09:17 2012 +0100

    cmd/gc: do not overflow parser stack on a long chain of else if.
    
    Fixes #2615.
    
    R=dave, minux.ma, iant, daniel.morsing, rsc
    CC=golang-dev
    https://golang.org/cl/6847078

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/9146ac14ee1e7516e2bb4212c0fcf054c6dde640

元コミット内容

cmd/gc: do not overflow parser stack on a long chain of else if.

Fixes #2615.

R=dave, minux.ma, iant, daniel.morsing, rsc
CC=golang-dev
https://golang.org/cl/6847078

変更の背景

Goコンパイラのフロントエンドは、構文解析にBison（Yacc互換のパーサージェネレータ）を使用しています。BisonはLALR(1)パーサーを生成し、これは内部的にスタックを使用して構文解析の状態を管理します。従来のif-else if-elseの構文解析ルールでは、else ifが連続するような長いチェーンの場合、パーサースタックが過度に深くなり、スタックオーバーフローを引き起こす可能性がありました。これは、特に大規模なコードベースや、自動生成されたコードで長いelse ifチェーンが出現する場合に問題となります。

このコミットは、Go issue #2615で報告されたこの問題を解決することを目的としています。

前提知識の解説

• Goコンパイラ (cmd/gc): Go言語の公式コンパイラの一部であり、ソースコードを解析し、中間表現に変換する役割を担います。
• Bison (GNU Bison): Yacc（Yet Another Compiler Compiler）互換のパーサージェネレータです。文法規則（.yファイル）から、C言語などのソースコード（パーサー）を生成します。生成されたパーサーは、入力ストリームが文法規則に準拠しているかを検証し、抽象構文木（AST）などの構造を構築します。
• LALR(1)パーサー: Bisonが生成するパーサーのタイプの一つです。これは、左から右へ（L）読み込み、右端導出（R）を逆順に適用し、1トークン先読み（1）を行うことで構文解析を行います。LALR(1)パーサーは効率的ですが、特定の文法構造（特に左再帰や、今回のelse ifのような構造）によっては、パーサースタックの深さが問題になることがあります。
• パーサースタック: LALR(1)パーサーが構文解析の途中で状態や解析済みのシンボルを一時的に保持するために使用するデータ構造です。文法規則の適用に伴い、スタックに要素がプッシュされたりポップされたりします。
• go.y: Goコンパイラの構文解析器の文法規則を定義するBisonの入力ファイルです。Go言語の構文がここで定義されています。
• y.tab.c / y.tab.h: go.yファイルからBisonによって自動生成されるC言語のソースファイルおよびヘッダーファイルです。これらが実際のパーサーの実装となります。
• %type: Bisonのディレクティブで、非終端記号に関連付けられるセマンティック値の型を定義します。
• %left, %right, %nonassoc: 演算子の結合性（左結合、右結合、非結合）と優先順位を定義するBisonのディレクティブです。
• Node / NodeList: Goコンパイラ内部で抽象構文木（AST）のノードを表すデータ構造です。NodeListはノードのリストを表します。
• popdcl() / markdcl(): Goコンパイラのパーサーにおけるスコープ管理に関連する関数です。markdcl()は新しいスコープの開始をマークし、popdcl()は現在のスコープを終了します。if文やfor文などのブロックは新しいスコープを導入するため、これらの関数が使用されます。

技術的詳細

このコミットの核心は、Bisonの文法定義ファイルsrc/cmd/gc/go.yにおけるif_stmt（if文）の構文規則の変更と、それに伴う生成されたパーサーコードy.tab.cの更新です。

従来のif_stmtの定義は、else部分が直接if_stmtまたはcompound_stmt（複合文、つまりブロック）を受け入れる形になっていました。これにより、if ... else if ... else if ...のような長いチェーンが再帰的に処理され、パーサースタックが深く積まれる原因となっていました。

修正では、if_stmtのelse部分を直接再帰させるのではなく、新たにelseifとelseif_listという非終端記号を導入しています。

• elseif: LELSE LIF if_header loop_bodyという形式で、単一のelse ifブロックを表現します。markdcl()で新しいスコープをマークし、popdcl()でスコープを終了します。
• elseif_list: 複数のelseifブロックを連結するためのリストです。これにより、else ifのチェーンが再帰的にスタックを深くするのではなく、リストとしてフラットに処理されるようになります。
• else: 最後のelseブロック（LELSE compound_stmt）を表現します。

if_stmtのルールは以下のように変更されました。

--- a/src/cmd/gc/go.y
+++ b/src/cmd/gc/go.y
@@ -661,25 +661,56 @@ if_stmt:
  	{
  		$3->nbody = $5;
  	}
-	else
+	elseif_list else
  	{
-		popdcl();
+		Node *n;
+		NodeList *nn;
+
  		$$ = $3;
-		if($7 != N)
-			$$->nelse = list1($7);
+		n = $3;
+		popdcl();
+		for(nn = concat($7, $8); nn; nn = nn->next) {
+			if(nn->n->op == OIF)
+				popdcl();
+			n->nelse = list1(nn->n);
+			n = nn->n;
+		}
  	}

この変更により、if_stmtのelse部分がelseif_listとelse（単一のelseブロック）を受け取るようになります。concat($7, $8)は、elseif_listと最終的なelseブロックを連結したリストを生成します。このリストをイテレートし、各ifノードのnelseフィールドに次のノードを割り当てることで、if-else if-elseのチェーンを構築します。

重要なのは、popdcl()の呼び出しが、各OIF（ifノード）が処理されるたびに行われるようになった点です。これにより、各else ifブロックが独自のスコープを持つことを適切に反映し、パーサースタックの深さが不必要に増大するのを防ぎます。

y.tab.cとy.tab.hはBisonによって自動生成されるファイルであるため、go.yの変更に伴い、Bisonのバージョンアップ（2.3から2.6.5へ）と、生成されるコードの変更が反映されています。特に、y.tab.cでは、Bisonの内部的なテーブル（yyprhs, yyrhs, yyrline, yydefact, yypact, yypgoto, yytable, yycheckなど）が大幅に更新されています。これは、文法規則の変更がパーサーの内部状態遷移に直接影響するためです。

test/fixedbugs/issue2615.goは、このバグを再現するためのテストケースです。非常に長いelse ifチェーンを含むコードが含まれており、この修正がなければスタックオーバーフローでコンパイルに失敗するはずです。

コアとなるコードの変更箇所

• src/cmd/gc/go.y:
  • %typeディレクティブにelseifとelseif_listが追加されました。
  • if_stmtのルールが変更され、elseの代わりにelseif_list elseを受け入れるようになりました。
  • elseifとelseif_listの新しいルールが追加されました。
  • elseのルールが変更され、if_stmtを直接受け入れなくなり、compound_stmtのみを受け入れるようになりました。
• src/cmd/gc/y.tab.c:
  • Bisonのバージョンが2.3から2.6.5に更新されました。
  • 文法規則の変更に伴い、内部的なテーブル（yyprhs, yyrhs, yyrline, yydefact, yypact, yypgoto, yytable, yycheckなど）が大幅に更新されました。
• src/cmd/gc/y.tab.h:
  • y.tab.cと同様に、Bisonのバージョン更新と文法変更に伴う定義の変更が反映されました。
• src/cmd/gc/yerr.h:
  • 小さな変更（コメントの修正など）。
• test/fixedbugs/issue2615.go:
  • 長いelse ifチェーンを含むテストケースが追加されました。

コアとなるコードの解説

src/cmd/gc/go.yの変更

// 変更前 (簡略化)
if_stmt:
    LIF if_header loop_body
    | LIF if_header loop_body LELSE if_stmt // 再帰的にif_stmtを受け入れる
    | LIF if_header loop_body LELSE compound_stmt
;

// 変更後 (簡略化)
if_stmt:
    LIF if_header loop_body
    elseif_list else // 新しい非終端記号を導入
;

elseif:
    LELSE LIF if_header loop_body // 単一のelse ifブロック
;

elseif_list:
    /* empty */
    | elseif_list elseif // else ifのリスト
;

else:
    /* empty */
    | LELSE compound_stmt // 最後のelseブロック
;

この変更の肝は、if_stmtが直接else ifの再帰的な定義を持たなくなったことです。代わりに、elseif_listという新しい非終端記号が導入され、これが複数のelse ifブロックをリストとして扱います。これにより、パーサーはelse ifの各ブロックを個別の要素として処理し、スタックの深さを不必要に増やすことなく、線形に処理できるようになります。

if_stmtのセマンティックアクション（{ ... }内のCコード）も変更され、concat($7, $8)によってelseif_listと最終的なelseブロックを連結し、そのリストをイテレートしてn->nelse = list1(nn->n);で各ifノードのnelseポインタを適切に設定しています。これにより、論理的なif-else if-elseのツリー構造が正しく構築されます。

また、if(nn->n->op == OIF) popdcl();という行が追加され、各else ifブロックが新しいスコープを導入する場合（OIFはifノードのオペレーションコード）、そのスコープが適切に閉じられるようにpopdcl()が呼び出されます。これにより、スコープ管理も正しく行われます。

src/cmd/gc/y.tab.cとsrc/cmd/gc/y.tab.hの変更

これらのファイルはBisonによって自動生成されるため、go.yの文法規則の変更が直接反映されます。Bisonのバージョンが2.3から2.6.5に上がったことも、生成されるコードに影響を与えています。主な変更は、パーサーの内部テーブル（状態遷移テーブル、ルールテーブルなど）の更新です。これらのテーブルは、新しい文法規則を効率的に解析するためにBisonが生成するものです。

test/fixedbugs/issue2615.goの追加

このテストファイルは、以下のような構造の非常に長いelse ifチェーンを含んでいます。

package main

func main() {
    if false {
    } else if false {
    } else if false {
    } // ... 非常に長いelse ifチェーン ...
    else if false {
    } else {
    }
}

このようなコードは、修正前のパーサーではスタックオーバーフローを引き起こしましたが、修正後は正常にコンパイルされるようになります。これにより、バグが修正されたことを検証します。

関連リンク

• Go issue #2615 (GitHub上では見つかりませんでしたが、コミットメッセージに記載されています)
• Go CL 6847078: https://golang.org/cl/6847078 (GoのコードレビューシステムGerritのリンク)

参考にした情報源リンク

• GNU Bison Documentation: https://www.gnu.org/software/bison/manual/
• Go言語のソースコード: https://github.com/golang/go
• Yacc / Bisonのスタックオーバーフローに関する一般的な情報 (例: https://stackoverflow.com/questions/tagged/yacc+bison+stack-overflow)
• LALR(1)パーサーの動作原理に関する情報 (例: コンパイラ理論の教科書)