Goは必ずしもEBNFに則しているとは限らない

Goは好きな言語の1つで普段から愛用しているのですが、先日Twitterで次のような不自然な挙動を目にしました。

このTweetのスレッドを読んでいくと、どうやらIf文の条件式中でstruct(anonymous struct)を初期化した場合はコンパイルに成功するが、foo(defined type)を初期化した場合はコンパイルに失敗するようです。

type foo struct { v int }

if struct{ v int }{1}.v == 1 {} // コンパイル成功
if foo{1}.v == 1 {} // コンパイル失敗

そこでGoの言語仕様であるThe Go Programming Language Specification(Version of Jan 14, 2020)を参照すると、該当するEBNF(Extended Backus-Naur Form)であるIfStmtは、

IfStmt = "if" [ SimpleStmt ";" ] Expression Block [ "else" ( IfStmt | Block ) ] .

となっていて、条件式にセミコロンはないので... == 1の部分はExpressionとしてパース^[1]されます。Expressionをさらに辿っていくと

Expression
→ UnaryExpr
→ PrimaryExpr
→ Operand
→ Literal
→ CompositeLit
→ LiteralType LiteralValue

となり、次のLiteralTypeのパースで、struct（正確にはstruct{ v int }）がStructTypeに、fooがTypeNameにそれぞれパースされるはずです（そして共通して続く{1}はもちろんLiteralValueに当たります）。

はずと言ったのは、上記のコードのASTを見るとfooのほうはそのようになっていないからです^[2]。

• structを含むIfStmt
  

• fooを含むIfStmt
  

まずは意図通りパースされているstructを含むIfStmtのほうから見てみましょう。ASTを見て分かる通り条件式は==で結ばれるCond : *ast.BinaryExpr (Op: ==)としてパースされています。そして、その下の階層には==の左辺であるX : *ast.SelectorExprと右辺であるY : *ast.BasicLit (Kind: INT)があります。Xのほうをさらに深掘っていくとコードと対応するようにパースされています。

一方でfooを含むIfStmtのほうはどうでしょう。ASTを見ると条件式は==ではなくただのfoo(Cond : *ast.Ident (Name: foo))になっていますね。

なぜこのようにパースされたかを知るにはパーサー自体を見ていくしかありません。幸にしてGoのパーサーはGoで書かれているので、コードを根気よく読んでいけばいつかこの謎を解くことができます。それでは見ていきましょう。

IfStmtのパーサーは文字通りparseIfStmt関数が担っています。特にIf文の初期化式と条件式はまとめてparseIfHeader関数でパースされます。パーサーを読み進めると問題のコードにはセミコロンがないので、1875行目からSimpleStmtをパースするparseSimpleStmt関数に入ります。実はEBNF上ではSimpleStmtとExpressionは分かれていますが、実際のパーサーでは両方ともparseSimpleStmt関数でパースします。

さらにEBNFとパーサー、問題のコードを対比させながら読み進めると、PrimaryExprをパースするparsePrimaryExpr関数に辿り着きます。この関数の中でx := p.parseOperand(lhs)にてOperand（fooのことですね）を取得した後、次のtokenが何であるかで場合分けの処理が入るのですが、fooの後に来るtokenはもちろん{なのでtoken.LBRACEの条件に入ります。そしてここで問題の根本原因である1510行目にようやく辿り着くことになります。

if isLiteralType(x) && (p.exprLev >= 0 || !isTypeName(x)) {

このtoken.LBRACEはLiteralTypeのものなのでisLiteralType関数の戻り値がtrueかどうかだけ判断すれば良いと一見思うかもしれません。しかし、何やらp.exprLev >= 0 || !isTypeName(x)と続いていますね。1つ目のp.exprLev >= 0の意味するところですが、これがtrueのとき、すなわちp.exprLevが0以上であるとき、パーサーは式（expression）を処理中であることを表しています。2つ目の!isTypeName(x)は、文字通り今処理中のノードがTypeNameではないことを判定しています。

なぜこのような条件が付加されているのか？GitHubにあるコミット履歴を2009年まで遡ってみましたが明示的に理由を説明しているコミットは見つかりませんでした。そこで推測になるのですが、この条件が付加されたのはGoはパース処理を簡略化する設計思想を持つ言語である（変数定義時に変数名の後に型を持ってくるのはそのため^[3]）からだと思いました。

例えばif foo{v: 1} {}をパースするとき、fooが変数名（identifier）なのかユーザー定義型（TypeName）なのかは{v: 1}をパースした時点では判断できません。それは{v: 1}単体だとLiteralValueとも、LabeledStmt in Blockとも取れるからです。その後の{}をパースして初めてTypeNameであると分かります^[4]。

• LabeledStmt in Block

{
v:
    1
}

この記事の「structを含むIfStmt」の図をもう1度見ていただくと、{}がBlockと分かった後にBlockの兄弟ノードに当たるCompositeLitの下の階層まで戻ってEBNFを決めていかなければならず、パース処理が複雑になることが容易に想像できます^[5]。

以上をまとめると、LiteralTypeの定義は

LiteralType   = StructType | ArrayType | "[" "..." "]" ElementType |
                SliceType | MapType | TypeName .

ですが、TypeNameを取ることは現時点ではできず、EBNFを満たしていません。また今回はIfStmtの例を見てきましたが、他のcontrol structuresであるSwitchStmt, ForStmtでも同様にEBNFを満たしていません^[6]。

脚注

1. この記事で言うパース、パーサーは構文解析、構文解析器のことを指しています。なので意味解析でエラーになってもパースに成功するか否かはEBNFに従った構文的に正しかだけで判断します。

2. 可視化にはGoAst Viewer を使わせていただきました🙏

3. Why are declarations backwards? - Go Frequently Asked Questions (FAQ)

4. @dqneo さんより。複数ファイルがある場合は、別のファイルに foo があるかもしれないため、この時点では TypeName かどうかはまだ判別できない。字句解析や構文解析後、ファイルごとの AST をマージする処理および型チェックによって初めて分かる。

5. {v: 1}をパースした後にくるtokenが.、つまりtoken.PERIODであれば{v: 1}はLiteralValueに絞られるので、問題のコードはパースに成功しても良いのになぁと思ったりもします。

6. @dqneo さんより。specには
   
   A parsing ambiguity arises when a composite literal using the TypeName form of the LiteralType appears as an operand between the keyword and the opening brace of the block of an "if", "for", or "switch" statement, and the composite literal is not enclosed in parentheses, square brackets, or curly braces. In this rare case, the opening brace of the literal is erroneously parsed as the one introducing the block of statements. To resolve the ambiguity, the composite literal must appear within parentheses.
   
   とある通り意図した挙動で、解決策としては括弧でくくるべきだと書かれています。