TypeAnalysisでは、各部分式に型をつけていきます。また、制御構文により暗に生成されるラベルの生成も行っています（ここでやる必要はなかったですね……）。
もうこの辺では空間計算量を気にする余裕がなくなってきていたので、全部愚直な線形再帰で処理しています。
とはいっても、抽象構文木として暗に再帰的な構造になっているので、ふつうのケースでは問題になることは少ないと思われます。
変なケースとしては、int a1, a2, a3, ……, a1000;とか、a1+a2+a3+……+a1000;とか、void f() {{{{{……{{{{{}}}}}……}}}}}とか、こういうのがくると厳しいです。
ただ、こういうケースはそもそもParserの段階で厳しいので、Parserを通ってきた出力なら大丈夫でしょう、ということで手抜きをしています。
C言語における型は、ltmpcに実装されている範囲だと、「void・char・int」×「ポインタの数・配列・関数」×「左辺値・右辺値」くらいが必要な情報です。 C言語における型付けのルールを理解していないため、実装は全然正しくなっていません。特に、条件演算子の実装は完全に間違っています。
Typed<Ty, AST, Lval>
抽象構文木のノードをラップして、型の情報の左辺値であるかの情報を付け加えているノードです。
IsParameterListValid
関数の引数の型に、void型が混ざっていないかをチェックしています。sizeof...(Params) && falseというのは、無理やり依存式にしてstatic_assertを起こすのを遅延させるために行っています。
あれ、この書き方だと引数の最後にvoidがある場合に正しいと判定してしまうような気がしますね……。
ParseDeclare
C言語の型宣言の構文をパースしてできる抽象構文木は使いたいものと逆順になっているため、使いやすいようにひっくり返しています。末尾再帰のreverse関数のような方法で行っています。
TypeEnvironment
型の環境を保持するためのもので、変数や関数の識別子名から、その型を引くことができる辞書になっています。多重継承を利用した型の辞書イディオムを使っています。
NestEnviroment
制御構文（if, forなど）で暗に定義される一意なラベルを生成するための情報を保持するための物です。break、continueは最内のループの末尾に飛ぶため、ifのネストだけは別にカウントしないといけないので面倒です。
Convertible
C言語における暗黙の型変換が許されるかの定義ですが、これってあっているんでしょうか…………。
Error
Parserと違ってTypeAnalysisでは、エラーを発見した時にちゃんとstatic_assertで落とすようにしました（未既定の挙動を引き起こす諸悪の根源です……）。
Error_Assign_Type_Not_Convertible<T, U, N>だけTやUが存在するのは、デバッグ時の名残のようです（このようにすると、ltmpcの内部表現とはいえテンプレート実引数がエラーメッセージとして出力される（コンパイラを使っている）のでデバッグが楽になります）。
NonVoidCondition
bool的文脈に現れることができる型かのチェックをしています。void以外は全部大丈夫でしたよね……？
FunctionApply
関数適用について、型があっているかのチェックを再帰的に行い、すべての型があっていれば返り値の型を返しています。
addType
二項加算演算について、その結果の型を導出しています。オペランドがポインタであるかそうでないかで四通りの結果があります。本当は関数ポインタと整数の加算は正しくないのですが、はじけていません。また、longなどのintより大きな型が含まれる加算が返す型はintではなくlongなどにしないといけないのですが、今回はそういう型は存在しないので手抜き実装しています。
makeAddTyped
addTypeの結果を使い、実際に型付けされたノードTypedを作る関数です。
subType, makeSubTyped
addType, makeAddTypedとほぼ同じです。
integralBinaryOpTyped
その他のほとんどの二項演算子は両オペランド共に整数しか受け取らないので、それを扱うものです。
Assign系
代入演算では、代入の時に型変換が発生するので、その型変換が可能かをチェックしています。加算代入と減算代入の場合はポインタ演算の可能性があるので、追加の実装がしてあります。
makeConditionalTyped
条件演算子の型付け規則ですが、then部の型にそろえる、という完全に間違った実装になっています。共通の型を見つける方法がよくわからなかったので手抜き実装になっています……。
makeCommaTyped
順次演算子は、void型のオペランドを受け取ることもあり、右オペランドの型が全体の型になるという他の二項演算子と違う特徴を持っているため、別に実装してあります。
makeBinaryTyped, makeMultiBinaryTyped
ほとんどの二項演算子は、整数を二つ受け取って整数を返すのでそれを全てまとめた実装です。MultiBinaryというのは、Parserでも出てきた、複数の優先順位が同じ演算子をまとめて取り扱う抽象化に対応します。
makePtrCompareTyped, makePtrEqCompTyped
整数以外を受け取ることもある二項演算には、加減算だけでなく、比較演算も該当します。それを別に実装しています（実はNクイーン問題をコンパイルするときまで気づいていませんでした……）。
makeAddressOf
単項アドレス演算子の型付け規則の実装です。左辺値でないとエラーにしている点に注意が必要です。
これ、別に関数ポインタの時と区別する必要はなかったですね……。
以下、同様の単項演算子のmake系関数が続きますが、ほとんどやっていることは同じです。左辺値でないといけないだとか、ポインタでないといけないだとか、関数ポインタでないといけないとか、条件により振り分けて間違っている場合はエラーにしています。
promote
以下の四つの汎用的な自動変換を実装しています。
- 左辺値から右辺値への自動変換
- 配列のdecay
- 整数昇格（現状は
char→intのみしか存在しない） - 関数の関数ポインタへのdecay
うち、配列のdecayが発生したかはアセンブリコード生成の際に重要な情報になるので、ArrayDecayというノードを新たに生成しています。
また、void型のものをpromoteしようとした、ということはvoid型の物をオペランドにとって演算しようとしたということなので、エラーにしています。条件演算子や順次演算子など、void型の物をオペランドにとれる演算子の場合でこのエラーを出したくない場合は、代わりにpromote_void関数を使います。
関数から関数ポインタへのdecayを実装しているため、(*****fp)()みたいなコードもコンパイルすることができます。
typed_expr
抽象構文木のノードを受け取り、再帰的に型付けを行う関数です。型環境Environmentを受け取っているため、ADLの対象となり、関数を使うタイプのTMPであっても相互再帰が可能になっています。
typed_expr_impl
ほとんどの二項演算ではpromoteを使い、一部の二項演算子でだけpromote_voidを使う、というのを先ほど説明しました。これを、関数の実質的な特殊化、つまりオーバーロード優先順位が高い、より詳しいテンプレート引数指定の関数で上書きする、という手法でやろうとするのですが、
「オーバーロード解決に不必要なテンプレートの実体化はしてもしなくてもよい（未規定）」
という未既定の挙動をまさに踏みました。
先の手法だと、たしかに思い通りのオーバーロード優先順位にはなるのですが、必要ない方（generalな、promoteを使う方）もインスタンス化され、そちらでstatic_assertを起こしてしまうのです。
これを防ぐために、この問題の発生する部分だけは、関数を使う形式のTMPをあきらめ、構造体を使う形式のTMPに切り替えました。それがtyped_expr_implです。TypeAnalysisでは暗黙の変換を使っているところは全くないので、この点は問題になることはありません。
また、clangはテンプレート引数が三つのConditional_Nodeについてもバグった挙動を示してBinaryNode<T, U>にマッチして同様の問題を引き起こすため、これも除外しています。
typed_expr
その下には、MultiBinaryに該当するEqComp_Node、Compare_Node、Shift_Node、Mult_Node、についての定義が並んでいます。enum classの型を推論してくれるとまとめることができるのですが、非型テンプレートパラメターの型を推論することは、C++11ではできないようです（コンパイラの動作を見る限りにおいては、C++17ではできるようになったようです）（ltmpcを作るにあたってはC++11で十分で、C++14やC++17の機能は役に立たないと思っていたのですが、この点だけはほんの少しだけ不便ですね）。
StatementFold
文ごとに、含まれる式に型付けを行い、型環境とネスト環境を更新していきます。また、break文とcontinue文について、どこにジャンプするべきかのラベル割り当ても行っています。
おわりに
基本的に、Parserまでが面倒な部分であって、それ以降はやるだけなのであまり面白い解説ではなかったと思います。まぁ、やるだけと言いつつC言語の型付けは暗黙のルールが多くてやたらに複雑なので正しく実装できていないませんが……。
全然関係ない話
ltmpcの未実装部分を実装したり、非効率な部分を書き換えたりしたいとずっと思っているのですが、最近忙しくてここ一か月くらいなにもできていません。
ltmpcの解説だけは、なんか毎週日曜日にブログを更新するみたいな感じになっているので書き続けていこうとしています。
