Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Go言語のパーサー（go/parserパッケージ）における内部エラー発生時の無限ループを回避するための修正です。具体的には、エラー回復処理中にパーサーがスキャナーを適切に進めない場合に発生する可能性のある無限ループを防ぐためのメカニズムが導入されました。これにより、エラー回復の質が若干低下する可能性はあるものの、パーサーが完全に停止してしまう事態を防ぎます。

コミット

commit f3c39d8f2bff2c1c5dde404dc533ac0b38326645
Author: Robert Griesemer <gri@golang.org>
Date:   Wed Mar 7 21:28:50 2012 -0800

    go/parser: avoid endless loop in case of internal error
    
    Factored the error synchronization code into two functions
    syncStmt and syncDecl. Because they may return w/o advancing
    the scanner, there is potential for endless loops across
    multiple parse functions; typically caused by an incorrect
    token list in these functions (e.g., adding token.ELSE to
    syncStmt will cause the parser to go into an endless loop
    for test/syntax/semi7.go without this mechanism). This would
    indicate a compiler bug, exposed only in an error situation
    for very specific source files. Added a mechanism to force
    scanner advance if an endless loop is detected. As a result,
    error recovery will be less good in those cases, but the parser
    reported a source error already and at least doesn't get stuck.
    
    R=rsc, rsc
    CC=golang-dev
    https://golang.org/cl/5784046

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

https://github.com/golang/go/commit/f3c39d8f2bff2c1c5dde404dc533ac0b38326645

元コミット内容

go/parser: avoid endless loop in case of internal error

Factored the error synchronization code into two functions
syncStmt and syncDecl. Because they may return w/o advancing
the scanner, there is potential for endless loops across
multiple parse functions; typically caused by an incorrect
token list in these functions (e.g., adding token.ELSE to
syncStmt will cause the parser to go into an endless loop
for test/syntax/semi7.go without this mechanism). This would
indicate a compiler bug, exposed only in an error situation
for very specific source files. Added a mechanism to force
scanner advance if an endless loop is detected. As a result,
error recovery will be less good in those cases, but the parser
reported a source error already and at least doesn't get stuck.

R=rsc, rsc
CC=golang-dev
https://golang.org/cl/5784046

変更の背景

Go言語のコンパイラの一部であるパーサー（go/parser）は、ソースコードを解析し、抽象構文木（AST）を構築する役割を担っています。このプロセス中に構文エラーが発生した場合、パーサーはエラー回復（Error Recovery）メカニズムを用いて、可能な限り解析を続行しようとします。これは、単一のエラーでコンパイルを中断するのではなく、複数のエラーを報告できるようにするためです。

しかし、既存のエラー同期コード（isStmtSyncやisDeclSyncのような関数）は、パーサーがエラー状態から回復しようとする際に、スキャナー（トークンを読み取る部分）を適切に進めない可能性がありました。特に、複数のパース関数がこれらの同期関数を呼び出す場合、スキャナーが進まない状態で無限にループしてしまう危険性がありました。コミットメッセージでは、test/syntax/semi7.goのような特定のソースファイルで、token.ELSEがsyncStmtに追加された場合に無限ループが発生する例が挙げられています。

このような無限ループは、コンパイラのバグを示唆するものであり、パーサーが応答不能になるという深刻な問題を引き起こします。このコミットは、この無限ループの潜在的な問題を解決し、パーサーの堅牢性を向上させることを目的としています。

前提知識の解説

このコミットを理解するためには、以下の概念について基本的な知識が必要です。

  • コンパイラのフロントエンド: コンパイラは通常、いくつかのフェーズに分かれています。フロントエンドは、ソースコードを解析し、中間表現に変換する部分です。これには、字句解析（Lexical Analysis）、構文解析（Syntactic Analysis）、意味解析（Semantic Analysis）などが含まれます。
  • 字句解析（Lexical Analysis）/スキャナー: ソースコードをトークン（意味を持つ最小単位、例: 識別子、キーワード、演算子）のストリームに変換するフェーズです。この処理を行うプログラムを「スキャナー」または「レキサー」と呼びます。
  • 構文解析（Syntactic Analysis）/パーサー: トークンのストリームが、プログラミング言語の文法規則に従っているかを検証し、抽象構文木（AST）を構築するフェーズです。この処理を行うプログラムを「パーサー」と呼びます。
  • 抽象構文木（AST: Abstract Syntax Tree）: ソースコードの構造を木構造で表現したものです。コンパイラの後のフェーズで、コードの分析や最適化、コード生成に利用されます。
  • エラー回復（Error Recovery）: 構文解析中にエラーが検出された場合、パーサーが解析を続行できるようにするための戦略です。一般的な方法としては、エラーが発生した場所から次の有効な構文要素までスキップしたり、不足している要素を挿入したりすることが挙げられます。
  • go/parserパッケージ: Go言語の標準ライブラリの一部で、Goのソースコードを解析し、ASTを生成するための機能を提供します。
  • token.Token: go/tokenパッケージで定義されている、Go言語のトークンを表す型です。例えば、token.SEMICOLONはセミコロン、token.IDENTは識別子を表します。
  • token.Pos: go/tokenパッケージで定義されている、ソースコード内の位置（行番号、列番号など）を表す型です。

技術的詳細

このコミットの核心は、Goパーサーのエラー回復メカニズムにおける無限ループの検出と回避です。

以前のパーサーでは、エラー回復のためにisStmtSyncやisDeclSyncといった関数が使用されていました。これらの関数は、現在のトークンが新しいステートメントや宣言の開始を示すかどうかを判断し、パーサーがエラー状態から回復するための同期ポイントを見つけるのに役立っていました。しかし、これらの関数がスキャナーを強制的に進めるロジックを持っていなかったため、特定の状況下（例えば、パーサーの内部的なバグにより、同期トークンリストが不正確な場合）で、パーサーが同じ位置で繰り返し同期関数を呼び出し、スキャナーが全く進まない無限ループに陥る可能性がありました。

この問題を解決するために、以下の変更が導入されました。

  1. parser構造体への新しいフィールドの追加:

    • syncPos token.Pos: 最後にスキャナーが進んだ同期位置を記録します。
    • syncCnt int: syncPosが更新されずにsyncXXX関数が呼び出された回数をカウントします。

  2. syncStmtとsyncDecl関数の導入:

    • 以前のisStmtSyncとisDeclSyncは、それぞれsyncStmtとsyncDeclという新しい関数に置き換えられました。これらの新しい関数は、*parser型のポインタを引数として受け取るようになりました。
    • これらの関数は、無限ループを検出するためのロジックを含んでいます。
      • 現在のパーサーの位置(p.pos)が前回の同期位置(p.syncPos)と同じであり、かつsyncCntが10未満の場合（つまり、10回連続でスキャナーが進まずに同期関数が呼び出された場合）、syncCntをインクリメントしてすぐにリターンします。これは、まだ無限ループではないと判断し、通常の同期処理を続行させます。
      • 現在のパーサーの位置(p.pos)が前回の同期位置(p.syncPos)よりも進んでいる場合、syncPosを現在の位置に更新し、syncCntを0にリセットしてリターンします。これは、パーサーが正常に進んだことを示します。
      • 上記のどちらの条件も満たさない場合（つまり、p.pos == p.syncPosかつp.syncCnt >= 10の場合）、これは無限ループの兆候と見なされます。この場合、p.next()を呼び出してスキャナーを強制的に1トークン進めます。これにより、パーサーは無限ループから抜け出すことができますが、エラー回復の質は低下する可能性があります。コミットメッセージでは、これを「コンパイラのバグ」と表現しており、このような状況ではエラー回復の質よりもパーサーが停止しないことの優先度が高いと判断されています。

これらの変更により、パーサーはエラー回復中に無限ループに陥ることを防ぎ、より堅牢になりました。

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

変更はすべて src/pkg/go/parser/parser.go ファイルで行われています。

  1. parser 構造体へのフィールド追加:

    type parser struct {
	// ... 既存のフィールド ...

	// Error recovery
	// (used to limit the number of calls to syncXXX functions
	// w/o making scanning progress - avoids potential endless
	// loops across multiple parser functions during error recovery)
	syncPos token.Pos // last synchronization position
	syncCnt int       // number of calls to syncXXX without progress

	// ... 既存のフィールド ...
}

  2. expectSemi() 関数内の変更: 以前はfor !isStmtSync(p.tok) { p.next() }というループでスキャナーを進めていましたが、これがsyncStmt(p)の呼び出しに置き換えられました。

    --- a/src/pkg/go/parser/parser.go
+++ b/src/pkg/go/parser/parser.go
@@ -377,9 +384,7 @@ func (p *parser) expectSemi() {
 		p.next()
 	} else {
 		p.errorExpected(p.pos, "';'")
-		for !isStmtSync(p.tok) {
-			p.next() // make progress
-		}
+		syncStmt(p)
 	}
 }

  3. isStmtSync から syncStmt への変更: isStmtSync関数が削除され、代わりにsyncStmt関数が導入されました。この関数は*parserを受け取り、内部でスキャナーの進行を制御します。

    --- a/src/pkg/go/parser/parser.go
+++ b/src/pkg/go/parser/parser.go
@@ -402,29 +407,66 @@ func assert(cond bool, msg string) {
 	}
 }
 
-// isStmtSync reports whether tok starts a new statement.
+// syncStmt advances to the next statement.
 // Used for synchronization after an error.
 //
-func isStmtSync(tok token.Token) bool {
-	switch tok {
-	case token.BREAK, token.CONST, token.CONTINUE, token.DEFER,
-		token.FALLTHROUGH, token.FOR, token.GO, token.GOTO,
-		token.IF, token.RETURN, token.SELECT, token.SWITCH,
-		token.TYPE, token.VAR, token.EOF:
-		return true
+func syncStmt(p *parser) {
+	for {
+		switch p.tok {
+		case token.BREAK, token.CONST, token.CONTINUE, token.DEFER,
+			token.FALLTHROUGH, token.FOR, token.GO, token.GOTO,
+			token.IF, token.RETURN, token.SELECT, token.SWITCH,
+			token.TYPE, token.VAR:
+			// Return only if parser made some progress since last
+			// sync or if it has not reached 10 sync calls without
+			// progress. Otherwise consume at least one token to
+			// avoid an endless parser loop (it is possible that
+			// both parseOperand and parseStmt call syncStmt and
+			// correctly do not advance, thus the need for the
+			// invocation limit p.syncCnt).
+			if p.pos == p.syncPos && p.syncCnt < 10 {
+				p.syncCnt++
+				return
+			}
+			if p.pos > p.syncPos {
+				p.syncPos = p.pos
+				p.syncCnt = 0
+				return
+			}
+			// Reaching here indicates a parser bug, likely an
+			// incorrect token list in this function, but it only
+			// leads to skipping of possibly correct code if a
+			// previous error is present, and thus is preferred
+			// over a non-terminating parse.
+		case token.EOF:
+			return
+		}
+		p.next()
 	}
-	return false
 }

  4. isDeclSync から syncDecl への変更: isDeclSync関数が削除され、代わりにsyncDecl関数が導入されました。syncStmtと同様のロジックを持ちます。

    --- a/src/pkg/go/parser/parser.go
+++ b/src/pkg/go/parser/parser.go
@@ -402,29 +407,66 @@ func assert(cond bool, msg string) {
 	}
 }
 
-// isStmtSync reports whether tok starts a new statement.
+// syncStmt advances to the next statement.
 // Used for synchronization after an error.
 //
-func isStmtSync(tok token.Token) bool {
-	switch tok {
-	case token.BREAK, token.CONST, token.CONTINUE, token.DEFER,
-		token.FALLTHROUGH, token.FOR, token.GO, token.GOTO,
-		token.IF, token.RETURN, token.SELECT, token.SWITCH,
-		token.TYPE, token.VAR, token.EOF:
-		return true
+func syncStmt(p *parser) {
+	for {
+		switch p.tok {
+		case token.BREAK, token.CONST, token.CONTINUE, token.DEFER,
+			token.FALLTHROUGH, token.FOR, token.GO, token.GOTO,
+			token.IF, token.RETURN, token.SELECT, token.SWITCH,
+			token.TYPE, token.VAR:
+			// Return only if parser made some progress since last
+			// sync or if it has not reached 10 sync calls without
+			// progress. Otherwise consume at least one token to
+			// avoid an endless parser loop (it is possible that
+			// both parseOperand and parseStmt call syncStmt and
+			// correctly do not advance, thus the need for the
+			// invocation limit p.syncCnt).
+			if p.pos == p.syncPos && p.syncCnt < 10 {
+				p.syncCnt++
+				return
+			}
+			if p.pos > p.syncPos {
+				p.syncPos = p.pos
+				p.syncCnt = 0
+				return
+				}
+			// Reaching here indicates a parser bug, likely an
+			// incorrect token list in this function, but it only
+			// leads to skipping of possibly correct code if a
+			// previous error is present, and thus is preferred
+			// over a non-terminating parse.
+		case token.EOF:
+			return
+		}
+		p.next()
 	}
-	return false
 }
 
-// isDeclSync reports whether tok starts a new declaration.
+// syncDecl advances to the next declaration.
 // Used for synchronization after an error.
 //
-func isDeclSync(tok token.Token) bool {
-	switch tok {
-	case token.CONST, token.TYPE, token.VAR, token.EOF:
-		return true
+func syncDecl(p *parser) {
+	for {
+		switch p.tok {
+		case token.CONST, token.TYPE, token.VAR:
+			// see comments in syncStmt
+			if p.pos == p.syncPos && p.syncCnt < 10 {
+				p.syncCnt++
+				return
+			}
+			if p.pos > p.syncPos {
+				p.syncPos = p.pos
+				p.syncCnt = 0
+				return
+			}
+		case token.EOF:
+			return
+		}
+		p.next()
 	}
-	return false
 }

  5. parseOperand(), parseStmt(), parseDecl(), parseFile() 内の呼び出し元の変更: isStmtSyncやisDeclSyncを直接呼び出していた箇所が、新しいsyncStmt(p)やsyncDecl(p)の呼び出しに置き換えられました。また、parseDecl関数のシグネチャも変更され、func(token.Token) bool型の関数を受け取る代わりに、func(*parser)型の関数を受け取るようになりました。

コアとなるコードの解説

このコミットの主要な変更は、parser構造体にsyncPosとsyncCntという2つのフィールドが追加され、エラー回復のための同期関数syncStmtとsyncDeclが大幅に修正された点です。

  • syncPos token.Pos: このフィールドは、パーサーが最後に「進んだ」と判断されたソースコード上の位置を記録します。パーサーがエラー回復中にトークンをスキップしたり、次の有効な構文要素を探したりする際、実際にスキャナーが進んだかどうかを追跡するために使用されます。

  • syncCnt int: このフィールドは、syncPosが更新されないまま（つまり、スキャナーが進まないまま）syncStmtまたはsyncDeclが呼び出された回数をカウントします。このカウンターは、パーサーが無限ループに陥っている可能性を検出するための閾値として機能します。

  • syncStmt(p *parser) および syncDecl(p *parser) のロジック: これらの関数は、エラー回復中にパーサーを次の有効なステートメントまたは宣言の開始位置に同期させる役割を担います。

    1. 進行の確認: 関数はループ内で現在のトークンをチェックし、ステートメント（BREAK, CONST, FOR, IFなど）または宣言（CONST, TYPE, VAR）の開始トークンであるかを確認します。
    2. 無限ループの検出と回避:
      • p.pos == p.syncPos && p.syncCnt < 10: もし現在の位置が前回の同期位置と同じで、かつsyncCntが10未満であれば、syncCntをインクリメントして関数を終了します。これは、まだ無限ループではないと判断し、パーサーが次のトークンを処理する機会を与えます。
      • p.pos > p.syncPos: もし現在の位置が前回の同期位置よりも進んでいれば、syncPosを現在の位置に更新し、syncCntをリセットして関数を終了します。これは、パーサーが正常に進んだことを示します。
      • 上記のどちらの条件も満たさない場合（つまり、p.pos == p.syncPosかつp.syncCnt >= 10）、これはパーサーが同じ位置で10回以上同期関数を呼び出し、スキャナーが全く進んでいないことを意味します。これは無限ループの兆候と見なされ、p.next()を呼び出してスキャナーを強制的に1トークン進めます。この強制的な進行は、エラー回復の質を犠牲にしてでも、パーサーが停止しないことを保証するためのものです。コミットメッセージにあるように、これは「コンパイラのバグ」によって引き起こされる可能性があり、パーサーが完全に停止するよりも、多少エラー回復の質が落ちても処理を続行する方が望ましいという判断です。
    3. EOFの処理: token.EOF（ファイルの終端）に達した場合は、それ以上進む必要がないため、関数を終了します。
    4. トークンの消費: 上記の条件に合致しない場合、p.next()を呼び出して次のトークンを読み込み、ループを続行します。

これらの変更により、Goパーサーはエラー回復の堅牢性が向上し、特定の内部エラー状況下での無限ループを効果的に回避できるようになりました。

関連リンク

参考にした情報源リンク

  • コミットメッセージと差分
  • Go言語のgo/parserパッケージの一般的な知識
  • コンパイラの設計に関する一般的な知識（字句解析、構文解析、エラー回復）