コマ12: 構造体とヒープ（struct / . / -> / sizeof / malloc / 連結リスト）

struct Point { int x; int y; };                 // スタック上に置く例
struct Node { int val; struct Node *next; };    // ヒープ上に置く例

この回で扱う範囲

対象にする機能は次の通り。

言語仕様どおり、構造体のフィールドは int、char、ポインタに限られる。 扱わない範囲（struct 値の入れ子、構造体代入、グローバル構造体変数）は「注意」節にまとめた。 malloc 自体も自作しない。lib.h の宣言を使い、リンク時に libc の malloc を呼び出す。

include_dir ::= '#' 'include' '"' FILENAME '"' NEWLINE   /* #define はコマ14 */

stars       ::= '*' { '*' }

scalar_type ::= 'int'  [ stars ]
              | 'char' [ stars ]
              | 'void' stars
              | 'struct' IDENT stars
obj_type    ::= scalar_type
              | 'struct' IDENT
ret_type    ::= scalar_type
              | 'void'
type_name   ::= obj_type

program       ::= external_decl { external_decl }
external_decl ::= struct_decl
                | func_proto
                | func_def       /* グローバル変数はコマ13 */
struct_decl   ::= 'struct' IDENT '{' field_decl { field_decl } '}' ';'
                | 'struct' IDENT ';'
field_decl    ::= scalar_type IDENT ';'
var_decl      ::= obj_type IDENT ';'

param       ::= scalar_type IDENT
param_list  ::= param { ',' param }
func_proto  ::= ret_type IDENT '(' [ param_list [ ',' '...' ] ] ')' ';'
func_def    ::= ret_type IDENT '(' [ param_list ] ')' func_body
func_body   ::= '{' { var_decl } { stmt } '}'

stmt        ::= expr_stmt
              | block
              | if_stmt
              | while_stmt
              | for_stmt
              | 'break' ';'
              | 'continue' ';'
              | 'return' [ expr ] ';'
expr_stmt   ::= [ expr ] ';'
block       ::= '{' { stmt } '}'
if_stmt     ::= 'if' '(' expr ')' stmt [ 'else' stmt ]
while_stmt  ::= 'while' '(' expr ')' stmt
for_stmt    ::= 'for' '(' [ expr ] ';' [ expr ] ';' [ expr ] ')' stmt

expr        ::= assign_expr
assign_expr ::= unary_expr '=' assign_expr   /* 右結合 */
              | cond_expr
cond_expr   ::= binary_expr [ '?' expr ':' cond_expr ]   /* 右結合 */
binary_expr ::= unary_expr { bin_op unary_expr }
bin_op      ::= '*' | '/' | '%'  /* 論理 && || はコマ13 */
              | '+' | '-'
              | '<' | '>' | '<=' | '>='
              | '==' | '!='
unary_expr  ::= postfix_expr
              | '-'  unary_expr
              | '*'  unary_expr
              | '&'  unary_expr
              | '++' unary_expr
              | '--' unary_expr
              | 'sizeof' '(' type_name ')'

postfix_expr   ::= primary_expr { postfix_suffix }
postfix_suffix ::= '[' expr ']'
                 | '.'  IDENT
                 | '->' IDENT

primary_expr ::= INT_LITERAL
               | CHAR_LITERAL
               | STRING_LITERAL
               | IDENT '(' [ arg_list ] ')'
               | IDENT
               | '(' expr ')'
arg_list    ::= assign_expr { ',' assign_expr }

AST を確認する: . と ->

まず、メンバアクセスがどのような AST になるか確認する。

python3 scaffold/parse_viewer.py sessions/12_struct_malloc_list/tests/dot_access.c

このプログラムの内容は次の通り。

struct Point {
    int x;
    int y;
};

int main() {
    struct Point p;
    p.x = 3;
    p.y = 4;
    return p.x + p.y;
}

実行すると、次のようなS式が表示される。

(program
  (funcdef "main" :type int (params)
    (block
      (decl "p" :type (struct "Point"))
      (exprstmt
        (assign (member "." "x" (var "p")) (num 3)))
      (exprstmt
        (assign (member "." "y" (var "p")) (num 4)))
      (return
        (add
          (member "." "x" (var "p"))
          (member "." "y" (var "p")))))))

p.x は AST 上では (member "." "x" (var "p")) になる。

次に、構造体ポインタを使う arrow_access.c を見る。

python3 scaffold/parse_viewer.py sessions/12_struct_malloc_list/tests/arrow_access.c

int distance_sq(struct Point *p) {
    return p->x * p->x + p->y * p->y;
}

この関数の部分は次のS式になる。

  (funcdef "distance_sq" :type int
    (params
      (param "p" :type (ptr (struct "Point"))))
    (block
      (return
        (add
          (mul (member "->" "x" (var "p")) (member "->" "x" (var "p")))
          (mul (member "->" "y" (var "p")) (member "->" "y" (var "p")))))))

p->x は AST 上では (member "->" "x" (var "p")) になる。 意味としては (*p).x と考えればよい。 . と -> は同じ member ノードで、1つ目の要素が違うだけである。

AST を確認する: sizeof と malloc

sizeof の AST はコマ9 で見たものと同じである。

python3 scaffold/parse_viewer.py sessions/12_struct_malloc_list/tests/sizeof_test.c

int main() {
    return sizeof(int) + sizeof(char);
}

(program
  (funcdef "main" :type int (params)
    (block
      (return
        (add (sizeof-type int) (sizeof-type char))))))

sizeof(int) は (sizeof-type int)、sizeof(char) は (sizeof-type char) になる。 どちらも実行時に計算する必要はなく、翻訳時に型サイズを見て定数を出せばよい。

次に、malloc と struct Node *next を含む list_min.c を見る。

python3 scaffold/parse_viewer.py sessions/12_struct_malloc_list/tests/list_min.c

#include "lib.h"

struct Node {
    int val;
    struct Node *next;
};

int main() {
    struct Node *n;
    n = malloc(sizeof(struct Node));
    n->val = 10;
    n->next = NULL;
    return n->val;
}

先頭には lib.h の関数プロトタイプが並び（#include がファイル結合であることが そのまま見える）、その後に main が続く。main の部分は次のようになる。

  (funcdef "main" :type int (params)
    (block
      (decl "n" :type (ptr (struct "Node")))
      (exprstmt
        (assign (var "n")
          (call "malloc" (args (sizeof-type (struct "Node"))))))
      (exprstmt
        (assign (member "->" "val" (var "n")) (num 10)))
      (exprstmt
        (assign (member "->" "next" (var "n")) (num 0)))
      (return
        (member "->" "val" (var "n"))))))

見どころは3つある。

• sizeof(struct Node) は (sizeof-type (struct "Node")) で、sizeof(int) と同じノードである。
• malloc(...) はただの call である。関数呼び出しはコマ6 で作ったものがそのまま働く。
• NULL は (num 0) になっている。理由は後の「NULL」節で述べる。

lib.h の宣言は void *malloc(int size); である。void * は任意の T * へ暗黙変換されるので、 そのまま struct Node *n に代入できる。逆向き（T * から void *）も同じで、 void *v; のような変数や int f(void *p) のような仮引数も書ける （void 単独の変数は書けない。* を伴う形だけである）。 この言語にキャスト (type)expr は無いので、ポインタの型を変える手段はこの暗黙変換だけである。 どちらもサイズ 8 のポインタなので、変換のための命令は出ない。

構造体のメモリレイアウト

構造体のサイズとフィールドのオフセットは、フィールドの並びから決める。 この講義では、各フィールドをその型サイズに応じた自然な境界に揃え、 構造体全体のサイズは最大フィールドの境界の倍数へ切り上げる。

struct Point は int x; int y; を持つ。int は4バイトなので、余白は入らない。

struct Point 全体のサイズは8バイトである。

図の q は &p を代入した struct Point *q である（distance_sq(&p) の仮引数も同じ状態になる）。 . は構造体変数のアドレスから、-> はポインタの値から、どちらも「+ フィールドオフセット」で場所が決まる。

一方 struct Node は int val; struct Node *next; を持つ。 ポインタは8バイト境界に置くため、val の後に4バイトの余白（パディング）が入る。

sizeof(struct Node) は 16 であって、4 + 8 = 12 ではない。 この差はあとで malloc に渡すサイズに効いてくる。

next は struct Node そのものではなく、struct Node へのポインタである。 ポインタのサイズは中身を知らなくても8バイトで確定するので、 定義の途中でも自分自身へのポインタを持てる。自己参照構造体が書けるのはこのためである。

構造体型の名前は常に struct タグ名 の形だけである。 そのため、構造体情報表のキーも "struct Node" の形で持てば、 型文字列（ty_str）をそのままキーとして使える。

struct 定義を読む

Parser は struct Point { ... }; のフィールド一覧を構文解析結果の prog.struct_defs に残す。この回では、その情報から構造体のレイアウトを計算する。

# スケルトンがあらかじめ prog.struct_defs から構造体情報を収集し、
# self._struct_defs としてコンストラクタに渡す設計

self._struct_defs は "struct Point" の形の型名をキーとする辞書である。 たとえば struct Point のエントリは次の形をとる。

{
    "size": 8,
    "align": 4,
    "fields": {
        "x": (0, "int"),        # (オフセット, ty_str)
        "y": (4, "int"),
    },
}

タプルの中身を直接取り出す必要はない。スケルトンは次の2つを提供している。

情報を集めるのはクラスメソッド parse_struct_defs(prog) で、これもスケルトンにある。 Parser が構文解析の結果として残す struct 定義（prog.struct_defs）から読み取るので、 フィールド間のコメントや、文字列・コメント内の struct タグ { 風のテキストに惑わされない。

size_of_ty_str に引数が増える

コマ8 の size_of_ty_str(ty) は int / char / ポインタしか知らなかった。 struct Point のサイズは定義を見ないと分からないので、この回で第2引数が増える。

size_of_ty_str(ty_str) -> int                    # コマ8〜コマ11
size_of_ty_str(ty_str, struct_defs=None) -> int  # この回以降

struct_defs は省略でき、省略した場合の結果はコマ8 と同じである。 そのため、コマ11 までに書いた呼び出しはそのまま動く。 ただし struct のサイズが要る場所では self._struct_defs を必ず渡す。 渡し忘れるとエラーにならないまま結果だけがずれる。

self.size_of_ty_str("struct Point", self._struct_defs)   # 8
self.size_of_ty_str("struct Point")                      # 4（渡し忘れ）

alloc_local / _scale_index / _load_ty / _store_ty / codegen_SizeofType は、 この引数を渡す形に直す必要がある。以降のコマ13〜コマ15 でもこの2引数の形を使う。

. と -> のコード生成

'Member' ノードの lvalue を作るのは codegen_lval_Member(node) ハンドラである （codegen_lval() のディスパッチはスケルトンに書かれているので、書くのはハンドラだけでよい）。 p->x は (*p).x と同じ意味なので、どちらもアドレス計算は同じ形になる。

address(p.x)  = address(p) + offset(x)      # . は p のアドレス
address(p->x) = value(p)   + offset(x)      # -> は p の値

違うのは2点だけである。 ベースアドレスを codegen_lval で求めるか codegen で求めるか、 そして対象の構造体型名を左辺値型からそのまま取るか、 ポインタ型から elem_ty_str で1段はがすかである。

def codegen_lval_Member(self, node):
    struct_ty = self._member_struct_type(node)       # "struct Point"
    if node.is_arrow:
        self.codegen(node.operand)                   # -> はポインタの値
    else:
        self.codegen_lval(node.operand)              # . は変数のアドレス
    offset = self.field_offset(struct_ty, node.name, self._struct_defs, node.line)
    self.emit(f"  addi a0, a0, {offset}")

構造体型名を求める部分はスケルトンで self._member_struct_type(node) に切り出してある。 中身は「. なら _type_of_lval(node.operand)、-> なら _type_of_expr(node.operand) を elem_ty_str に通す」だけで、これも実装対象である。

sizeof のコード生成 — コマ9 からの差分

sizeof(型名) そのものはコマ9 で導入済みである。 AST ノードも (sizeof-type ...) のままで増えていないし、 「型情報からサイズを調べ、即値を a0 に入れる」という形もそこで決まっている。

この回で新しいのは、被演算子に struct タグ名 が来る場合だけである。

違いは、構造体のサイズが型名だけでは決まらないことである。 フィールドの並びと境界合わせの余白まで見て初めてサイズが決まるので、 この回で作った構造体情報表を参照する必要がある。 そのため size_of_ty_str() に第2引数として self._struct_defs を渡す。

def codegen_SizeofType(self, node):
    self.emit(f"  li a0, {self.size_of_ty_str(node.ty_str, self._struct_defs)}")

たとえば sizeof(struct Node) は、self._struct_defs["struct Node"]["size"] が16なら li a0, 16 を出す。 コマ9 と同じく、出るのは即値1命令だけで、実行時に型を調べる処理は生成されない。

sizeof の被演算子は型名だけである。sizeof 式（sizeof x のように式を書く形）は 言語仕様の対象外なので（language_spec.md の「除外」節）、スキャフォールドの AST にも 対応するノードは無い。これはコマ9 と同じで、この回でも変わらない。

malloc を呼び出すと何が起きるか

malloc は、指定されたバイト数ぶんのメモリ領域をヒープから確保し、 その先頭アドレスを返すライブラリ関数である。

n = malloc(sizeof(struct Node));

コンパイラが行うことは、通常の関数呼び出しと同じである。 まず sizeof(struct Node) を a0 に計算し、それを第1引数として malloc を呼び出す。 戻り値も a0 に返る。この回で追加の実装は要らない。

返ってきた値は、構造体そのものではなく、確保されたメモリ領域の先頭アドレスである。 そのアドレスを struct Node *n に代入することで、以後その領域を struct Node として扱える。

n->val = 10;
n->next = NULL;

重要なのは、malloc はメモリを確保するだけで、中身を初期化しないことである。 確保直後の n->val や n->next の値は未定義なので、使う前に自分で代入する必要がある。

実際の malloc の内部では、未使用のヒープ領域を管理し、要求されたサイズに合う領域を探して返す。 足りなければ OS から追加のメモリを取得する。ただし今回のコンパイラでは、その仕組みを実装しない。 コンパイラが担当するのは、引数を a0 に置き、呼び出し規約に従って libc の malloc を 呼び出すところまでである。本来必要な free による解放も、プログラムがすぐ終了する 小さな例だけを扱うこの回では実装範囲に含めない。

NULL — 「どこも指していない」ポインタ

n->next = NULL; の NULL は、この回で初めて使う名前である。

NULL は言語のキーワードではなく、lib.h の最後にある1行のマクロである。

#define NULL 0

#include "lib.h"（コマ10）でこの定義が取り込まれ、 スキャフォールドの前処理が NULL を 0 に置き換えてから Lexer に渡す。 list_min.c のS式で n->next = NULL; が (assign (member "->" "next" (var "n")) (num 0)) になっているのは、 Parser が見る時点ではすでに 0 になっているからである。

そのため、コンパイラ側に NULL のための処理は要らない。 NULL を書くために必要なのは #include "lib.h" だけである。

意味の上では、NULL は「どのオブジェクトも指していない」ことを表すポインタ値である。 アドレス 0 にはプログラムのデータが置かれないので、 「有効なアドレスではない」印として 0 を使える。 p = NULL; は「まだどこも指していない」、p != NULL は「NULLではない」 という意味になる。非NULLであることだけでは、参照先が有効であるとは保証できない。 NULL のポインタを間接参照してはいけない（未定義動作であり、クラッシュし得る）。 連結リストでは、この規則がそのまま「終端に着いたら止まる」という走査の条件になる。

連結リストの走査

連結リストは、各ノードが次のノードへのポインタを持つ構造である。

int list_sum(struct Node *head) {
    int sum;
    sum = 0;
    while (head != NULL) {
        sum = sum + head->val;
        head = head->next;
    }
    return sum;
}

各ノードが有効な次のノードまたはNULLを指すように構築された連結リストでは、 head != NULL はまだ終端に着いていないことを調べる （前処理を通った後は head != 0 になる）。 head->val で現在のノードの値を読み、head = head->next で次のノードへ進む。

head はスタック上のローカル変数だが、各ノードは malloc で確保したヒープ上にある。 head = head->next は、head の指す先を矢印1つぶん右のノードへ進める。

編集するファイル

• mycc.py

importlib でコマ11 の Codegen11 を継承した Codegen12 に、以下の機能を追加する。

スケルトンにあらかじめ書かれているものは次の通りで、実装対象ではない。

実装対象は、スケルトンの raise NotImplementedError が置かれている次の12個である。

2〜5 の4つは、コマ11 まで動いていたコードに self._struct_defs を足すだけの修正である。 ただし直し忘れに気づけるよう、スケルトンでは4つとも raise NotImplementedError を置き、 コマ11 版のコードは TODO コメントの中に残してある。

11・12 の2つを書けば malloc と自己参照構造体と連結リストが動く。 malloc 呼び出しはコマ6 の関数呼び出しが、-> は 1〜10 で書いた構造体処理が、 そのまま働くからである。

実装手順

1. スケルトンの importlib 継承によりコマ11の Codegen クラスを引き継ぐ（あらかじめ書かれている）
2. parse_struct_defs(prog) で構造体定義のレイアウトを求め、コンストラクタで self._struct_defs に渡す（あらかじめ書かれている）
3. alloc_local() / _scale_index() / _load_ty() / _store_ty() の size_of_ty_str 呼び出しに self._struct_defs を渡す （_store_ty() はコマ8の規則を保ち、char 格納後の a0 も縮小・符号拡張する）
4. _load_ty() は struct 型のときロードせず、アドレスのまま扱う（is_struct_ty_str で判定）
5. _member_struct_type(node) を実装する（. は _type_of_lval、-> は _type_of_expr + elem_ty_str）
6. type_of_lval_Member(node) と type_of_expr_Member(node) を実装する（フィールドの型は field_ty で引く）
7. codegen_lval_Member(node) を実装する（ベースアドレスに field_offset を足す）
8. codegen_Member(node) を実装する（codegen_lval_Member のアドレスを _load_ty でロードする）
9. collect_strings_expr_Member(node) を実装する（Member の operand を走査する）
10. dot_access.c を通し、続けて arrow_access.c を通す
11. type_of_expr_SizeofType(node) を実装する（'int' を返すだけでよい）
12. codegen_SizeofType(node) を実装する（self.size_of_ty_str(node.ty_str, self._struct_defs) の値を li a0, <size> で出す。self._struct_defs を渡し忘れると struct のサイズが 4 になる）
13. sizeof_test.c を通す（sizeof(int) + sizeof(char)）
14. malloc_struct.c / list_min.c を通す
    （parse_struct_defs() は自己参照フィールド struct Node *next をそのまま扱える。ポインタは中身を知らなくてもサイズ 8 で確定するからである。malloc(sizeof(struct Node)) はコマ6 の関数呼び出しがそのまま働くので、追加の実装は要らない。）
15. list_sum.c まで通す
16. void_ptr.c を通す
    （void * と任意の T * の相互変換。void * の変数・仮引数も書ける。ポインタ同士なのでサイズは常に 8 で、変換のための命令は要らない。）
17. sizeof_void_ptr.c を通す（sizeof(void *) も他のポインタ型と同じくサイズ 8 として求まる）

コマ8のtype_of_expr_Cond・固定引数型の表・char変換を引き継ぐ。 型判定を上書きするときも、条件式はthen側だけの型に戻さない。 今回の型と配置での回帰はcond_struct_pointer.c・char_assign_value.cで確認する。

tests/

テスト

python3 scaffold/test_runner.py sessions/12_struct_malloc_list

tests/dot_access.c がコンパイルでき、終了コード 7 になれば基本形は成功。

個別に動かす場合は、次のようにする。

DIR=sessions/12_struct_malloc_list
python3 $DIR/mycc.py $DIR/tests/dot_access.c \
  | riscv64-linux-gnu-gcc -x assembler -static - -o out
qemu-riscv64 ./out
echo $?

注意

構造体代入は言語仕様にないため扱わない。 struct Point a; a = b; のように構造体そのものを代入することはできず、 フィールドを1つずつ代入するか、ポインタで渡す。 関数の引数・戻り値も同じで、構造体を値で受け渡すことはしない（struct Point * を渡す）。 構造体代入は発展課題 S3 で、 引数・戻り値の値渡し・値返しは発展課題 L5 で実装する。

フィールドに書けるのは int、char、ポインタだけである。 struct 値を入れ子にすることはできない（struct Node *next のようなポインタは書ける）。

構造体のサイズを手で数えてはいけない。 struct Node { int val; struct Node *next; } は余白を含めて 16 バイトなので、 4 + 8 = 12 と数えて malloc に渡すと next の書き込みが領域外に出る。 サイズは必ず sizeof で求める。

sizeof は翻訳時に値が決まる。扱うのは sizeof(型名) の形だけで、sizeof(式) は扱わない。

malloc は自作しない。lib.h の宣言を使い、リンク時に libc の malloc に解決する。 free を呼ばないので、確保した領域はプログラム終了まで残る。

グローバルな構造体変数はコマ13 で扱う。この回はローカル変数と引数だけである。

ここまでで着手できる発展課題

構造体と malloc まで学んだので、構造体の代入を仕様（不可）へ合わせる S3、型検査パスを足す Q1、自前 malloc（バンプ割り当て → フリーリスト）を作る R3 に着手できる。

ここでの「着手」は、概念を学び実装を検討し始めることである。 S3・Q1の単体検査を進められるが、完成したコンパイラを使う実行検査は 各READMEの前提を確認すること。R3の check.py は既定の経路で コマ15の完成した final/mycc.py を使うため、コマ12の時点では完走できない。

生成したアセンブリでメンバの offset 計算や malloc が返すアドレスを1命令ずつ確認したいときは、学習ツールの実行表示 に貼り付ける。

この回の完成形に相当する OCaml 版参考実装が ../../workbook/ocaml/README.md にある。完成相当の実装なので、まず自分の実装方針を検討してから確認すること。

この資料の原稿を見る