C(のサブセット)コンパイラを書く上でハマった点：配列編
初めに
「配列編」と銘打っていますが、続編が投稿される保証はありません。
そうそう
この記事は言語実装 Advent Calendar 2018とC言語 Advent Calendar 2018の17日目の記事です。
想定している読者層
（どういう読者層を想定しているんだろう、書いていて自分でもよく分からなくなった）（Cコンパイラ書いていて「配列の配列（いわゆる二次元配列）がなんかバグるなぁ」となった人のための記事かもなぁ）（というか、多分バグらせていた当時の自分への手紙）
本題に入ろう
Cコンパイラを書く上で微妙にハマった、配列へのポインタの話、それに付随して構造体を実装する際の話について軽く書きます。
まずは結論から
配列の識別子には値がない、というのがその原因かもしれません。ということでちょっと図を書いてみました（そういうことじゃない気もする）。 pic.twitter.com/2Y9PQlLaeT
— hikalium (@hikalium) 2018年8月10日
そうそうそう、配列だけアドレスが指す先をメモリから読むって処理を飛ばさないといけないのよね(ちょうど散歩しながら考えてた)
— Shinya Kato (@0x19f) 2018年8月10日
正直上2ツイートで私が今回言おうとしている話はだいたい尽くされているんですが、一応書いていきます。
ポインタ+整数
C言語では、「ポインタが難しい」と良く言われますが、 実際に初心者がCを学習する過程を見ると、以下のことだけは すぐに理解しているようです。
「ポインタっつーのは、要するにアドレスのことなんだな」
ここまでは簡単、誰でもすぐに理解します。
ポインタに1足したら、2byteとか4byteとか進む、ということを習った時から ? が点灯する。「ポインタってアドレスなんだろ? そんなもん1進むに決まってるんじゃないのか?」
一般にT *型のポインタpに1を足すと、アドレスはsizeof(T)だけ増える*1ので、C言語においてポインタを扱う際には、アドレスだけではなくポインタの型が何であるかという情報も不可欠です。まあそもそも型が分かっていないと間接参照((ポインタに*を適用すること))もできませんが。
ちなみに、話が逸れますが、アドレスが同一で型が同一でもポインタとして同一であるとは限りません。
ポインターは簡単だ。それはただの整数じゃないか。いいえ、そんなことはありません。みたいな話がありますね https://t.co/mkqidkaYTb
— Masaki Hara (@qnighy) 2018年9月26日
これを知らないと、
どこも間違っていないのに何故か間違った答えのでるバグの原因が、コンパイラのundefined behavior検出によるものでした。
— ゆかたゆ (@yukata_yu) 2018年9月6日
int d[4][8]に対して
for(int n=0; n<4*8; ++n) d[0][n] = f(n);
でub吐かないで欲しいのです…。
ポインタに一旦入れたら治りました。
そりゃ完璧にUB踏んでるしなぁ。
— yoh2 (@yoh2_sdj) 2018年9月6日
それにしてもこのパターンでもおかしくなることがあるのか。今度ネタにしよう。
規格を読んだことがないのですが、
— ゆかたゆ (@yukata_yu) 2018年9月6日
このケースでd[0][8a+b]とd[a][b]が同じものを指す保証はされないのでしょうか？
メモリ配置が連続してるのは保証されてますが、 d[0]の型が int [8] である以上、d[0]を通してのアクセスはd[0]〜d[7] (アドレスを得るだけなら&d[8]も可) に限るんです。
— yoh2 (@yoh2_sdj) 2018年9月6日
みたいなことになったりするようです。私も上のやりとり見て初めてこの話を知りました（そして前述のqnighyさんのツイートで腑に落ちた）
配列とポインタ、&と*
C言語には、「配列」と「配列の先頭要素へのポインタ」と「配列全体へのポインタ」があります。例えば、int arr[8]; int *p1 = arr;とあるとき、arrは配列であり、p1は「配列の先頭要素へのポインタ」であり、&arrは「配列全体へのポインタ」です。&p1は「ポインタへのポインタ」ですね。int *p1 = arr;と書けるのは、式の中では基本的に「配列」が「配列の先頭要素へのポインタ」へと勝手に読み替えられるからですね。
Cコンパイラを書いた時点で私がちゃんと分かっていなかったのは、「ポインタ&arrのアドレス値『は』ポインタp1のアドレス値と等しく、これを間接参照する際には
アドレスが指す先をメモリから読むって処理を飛ばさないといけない
」という話です。
やっぱりみんなこれ疑問に思いますよね
今学期（2018年秋学期）取っていた授業で、配列arrがメモリ上のどこにあるのかを調べる際、講師がgdbでp &arrとしていました。その結果、授業のQ&Aフォーラムで次のような質問がなされることとなりました：
文字列
sに対して、gdbでp sしたときとp &sしたときでアドレスが違うんですが、これはなぜでしょう？
これに対して私が返した解説をそのまま日本語訳すればいい説が出てきたので、ほぼそのまま和訳して載せていこうと思います。
「講義だとp &arrで文字列のアドレスが得られたのになぜ今回はそうならないのか、ということですよね？これは配列とポインタが別物であることに由来します。Cでは、 sizeofか&のオペランドになっている場合を除き、配列はその先頭要素へのポインタに暗黙に変換されます。sがcharへのポインタである場合、sというのはとあるアドレスを表すビットパターンであり、そのビットパターンはまたメモリのどこかに格納されています。前者がsで後者が&sなので、値が違うわけです。」
「sがcharの配列である場合は話が少し変わってきます。sが配列で、アドレス0x7fffffffe900から始まるとしましょう。sは配列なので、先頭要素へのポインタへと変換されます。先頭要素は0x7fffffffe900という場所にあるので、sの値は0x7fffffffe900です。」
「では、sがcharの配列であるとき、&sはどうなるでしょう？実はこれは配列全体へのポインタという意味になります。講義のビデオをよく見ると、gdbで&sの型がchar (*)[6]と表示されていることが分かります。これは、&sが（ポインタへのポインタではなく）配列へのポインタであるという意味です。さて、ということで&sは配列が格納されているアドレスですが、これも0x7fffffffe900です。ゆえにsと&sは同じアドレスとなる（けれども型は違う）のです。」
「では、そもそもなぜこの『配列全体へのポインタ』とかいうよく分からないものが存在するのでしょう？これは主に多次元配列というものを許容するためにあります。*2。」
「Cでは、intの配列の配列を作ることができます。具体例として、3つの『5個のintからなる配列』からなる配列を考えましょう。これはint arr[3][5];として宣言できます。arrはなんかの配列なので、大体の文脈でなんかへのポインタに変換されます。変換されてできるものは何でしょう？『5個のintからなる配列』へのポインタです。（Cの構文は奇怪なので、これをint (*p)[5]と書きます。）」
「3つの『5個のintからなる配列』からなる配列int arr[3][5];では、intを格納する15個の『箱』全てが隣り合って存在することが保証されています。この条件の元で多次元配列を正しくサポートするという要請こそが、sが真の配列であるときにsと&sのアドレス値が一致しなければならない理由です。int arr[3][5];に対して、arr[2][4]、つまり*(*(arr+2)+4)が最後の箱を表すようになってほしいわけです。」
（原文ではここに*(*(arr+2)+4)を追いかける文章が入るが、K&Rとか「C言語ポインタ完全制覇」とかに載っている図の方が分かりやすいので割愛）
「ということで、コンパイラが『配列全体へのポインタ』を間接参照するときには、実は型が変わっているだけであり、間接参照に対応するアセンブリが吐かれたりしません。このことによって、多次元配列が動いてくれるので、一貫性のため、全ての『配列全体へのポインタ』はこの性質を満たさないといけないのです。」
補足：構造体
struct A s; のとき、s.a というのは *( (char *)&s + offsetof(struct A, a) ) のことだけれど、arrが配列型なら (char *)&s + offsetof(struct A, arr) で得られるポインタは配列へのポインタなので、C言語上での間接参照はno-opにしてやらないといけない
— hsjoihs (@hsjoihs) 2018年10月25日
注: (char *)&s + offsetof(struct A, arr)を間接参照する前に当然*(s.a)の型にキャストして戻さないといけないが、上ツイートではその話が抜けている
最後に
今日あと4分しかないのでとても雑
