Seven done of Writing a C Compiler, a few more to go. Now is the time for loops.
Lexer, AST and Parser
The lexer is just a few new keywords. Been there, done that. Changes to the AST are more interesting. No less than five new statements, one for every new keyword. Here is the new Stmt without further ado:
pub const Stmt = union(enum) {
@"return": *Expr,
expr: *Expr,
@"if": struct { cond: *Expr, then: *Stmt, @"else": ?*Stmt },
compound: Block,
@"break": ?[:0]const u8,
@"continue": ?[:0]const u8,
@"while": While,
do_while: While,
@"for": For,
null: void,
const While = struct {
cond: *Expr,
body: *Stmt,
label: ?[:0]const u8,
};
pub const For = struct {
label: ?[:0]const u8,
init: Init,
cond: ?*Expr,
post: ?*Expr,
body: *Stmt,
pub const Init = union(enum) { decl: *Decl, expr: *Expr, none },
};
}
A few notes. Each of these statements have an optional label argument. This label is used later to associate breaks and continues with their associated loops during semantic analysis. You cannot actually assign labels to loops in C as far as I know.
Also, usually for a one off subtype like For here, I put it inline. But this one is big and hairy and has a subtype of its own that it warrants the special treatment. Init itself is named because I am naming it later in the parser. To map the fields to the actually for loop in code, it is basically this:
for (init, cond, post) body
All the three first fields are optional. The reason that none is a state of init instead of using an optional is to shave a few bytes from the size of init (and therefore the whole For type and then the whole Stmt type).
Parsing these is a bit more interesting. First, the straightforward break and continue.
.keyword_break => {
try expect(.semicolon, tokens);
return .{ .@"break" = null };
},
.keyword_continue => {
try expect(.semicolon, tokens);
return .{ .@"continue" = null };
},
while and do while are slightly more interesting. They're similar to if.
.keyword_while => {
try expect(.l_paren, tokens);
const cond = try parse_expr(arena, tokens, 0);
const cond_ptr = try utils.create(arena, cond);
try expect(.r_paren, tokens);
const body = try parse_stmt(arena, tokens);
const body_ptr = try utils.create(arena, body);
return .{ .@"while" = .{
.cond = cond_ptr,
.body = body_ptr,
.label = null,
} };
},
.keyword_do => {
const body = try parse_stmt(arena, tokens);
const body_ptr = try utils.create(arena, body);
try expect(.keyword_while, tokens);
try expect(.l_paren, tokens);
const cond = try parse_expr(arena, tokens, 0);
const cond_ptr = try utils.create(arena, cond);
try expect(.r_paren, tokens);
try expect(.semicolon, tokens);
return .{ .do_while = .{
.cond = cond_ptr,
.body = body_ptr,
.label = null,
} };
},
Now time for the final boss. for. There is a funny complication here that I hit on my previous Rust implementation. The parsing code for variable declarations already expects a semicolon, but the one for expressions does not. So if I determine the init statement is a variable declaration, I need not check for a semicolon, whereas I do if it turns out to be empty or an expression.
There is another problem that's perhaps unique to the current implementation, which is that, if you remember, when parsing statements divorced from parsing variable declarations, parse_stmt moved into its own home, while parsing declarations still clung to the old home of parse_block_item. Now that variable declarations have a new partner, they need to move to their own home. The divorce is finally complete.
fn parse_block_item(
arena: std.mem.Allocator,
tokens: *lexer.Tokenizer,
) Error!ast.BlockItem {
const current = tokens.next() orelse
return error.NotEnoughJunk;
tokens.put_back(current);
switch (current.tag) {
.type_int => return .decl(try parse_var_decl(arena, tokens)),
else => return .stmt(try parse_stmt(arena, tokens)),
}
}
fn parse_var_decl(
arena: std.mem.Allocator,
tokens: *lexer.Tokenizer,
) Error!ast.Decl {
try expect(.type_int, tokens);
const name = try expect(.identifier, tokens);
const new_token = tokens.next() orelse
return error.NotEnoughJunk;
const init: ?*ast.Expr = switch (new_token.tag) {
.equals => ret: {
const expr = try parse_expr(arena, tokens, 0);
const expr_ptr = try utils.create(arena, expr);
try expect(.semicolon, tokens);
break :ret expr_ptr;
},
.semicolon => null,
else => return error.SyntaxError,
};
return .{ .name = name, .init = init };
}
Now that I am properly equipped, time to take on for. After the left parenthesis, take it one piece at a time. First is init:
// I needed the type here so I had to name it and make it pub in the AST
const init: ast.Stmt.For.Init = init: {
const new_token = tokens.next() orelse
return error.NotEnoughJunk;
switch (new_token.tag) {
.semicolon => break :init .none,
.type_int => {
tokens.put_back(new_token);
const decl = try parse_var_decl(arena, tokens);
const decl_ptr = try utils.create(arena, decl);
break :init .{ .decl = decl_ptr };
},
else => {
tokens.put_back(new_token);
const expr = try parse_expr(arena, tokens, 0);
const expr_ptr = try utils.create(arena, expr);
try expect(.semicolon, tokens);
break :init .{ .expr = expr_ptr };
},
}
};
The other two are tamer beasts. A small difference between cond and post is the post does not require a semicolon to terminate it, so it is compared to the right parenthesis instead.
const cond: ?*ast.Expr = cond: {
const new_token = tokens.next() orelse
return error.NotEnoughJunk;
switch (new_token.tag) {
.semicolon => break :cond null,
else => {
tokens.put_back(new_token);
const expr = try parse_expr(arena, tokens, 0);
const expr_ptr = try utils.create(arena, expr);
try expect(.semicolon, tokens);
break :cond expr_ptr;
},
}
};
const post: ?*ast.Expr = post: {
const new_token = tokens.next() orelse
return error.NotEnoughJunk;
switch (new_token.tag) {
.r_paren => break :post null,
else => {
tokens.put_back(new_token);
const expr = try parse_expr(arena, tokens, 0);
const expr_ptr = try utils.create(arena, expr);
try expect(.r_paren, tokens);
break :post expr_ptr;
},
}
};
Then finally, the coup de grace:
const body = try parse_stmt(arena, tokens);
const body_ptr = try utils.create(arena, body);
return .{ .@"for" = .{
.init = init,
.cond = cond,
.post = post,
.body = body_ptr,
.label = null,
} };
This about covers it I think. One tiny complication remains: in implementing the pretty printer last chapter, I used the keyword DO for blocks. So instead of repeating myself, I am going to use a different keyword for do while loops: UNTIL. These look fine. Time to move on.
int main(void) {
int sum = 0;
for (int i = 0; i < 10;) {
i = i + 1;
if (i % 2)
continue;
sum = sum + i;
}
return sum;
}
// PROGRAM
// FUNCTION main
// int sum <- 0
// FOR int i <- 0; (< i 10); ---
// (i <- (+ i 1));
// IF (% i 2)
// CONTINUE
// (sum <- (+ sum i));
// RETURN sum
int main(void) {
int a = 1;
do {
a = a * 2;
} while(a < 11);
return a;
}
// PROGRAM
// FUNCTION main
// int a <- 1
// UNTIL (< a 11)
// (a <- (* a 2));
// RETURN a
Semantic Analysis
In addition to variable resolution, this chapter will also do loop labelling, attaching each break and continue to their parent loops. While C does not have labelled loops, goto aside, this is still needed to generate the proper labels for IR and assembly jump instructions.
Resolving variables in while and do while is fairly simple, just like an if statement. break and continue have nothing to resolve. for loops, are, once again, more complicated. A new scope is introduced, similarly to compound statements, on top of the scope introduced by the inner compound statement. Instead of duplicating the boilerplate, I thought to combine for statements and compound statements into one branch as follows:
.@"for", .compound => {
var variable_map = try bp.variable_map.clone(bp.gpa);
defer variable_map.deinit(bp.gpa);
var iter = variable_map.valueIterator();
while (iter.next()) |value|
value.* = .{ .name = value.name, .scope = .parent };
const inner_bp: Boilerplate = .{
.gpa = bp.gpa,
.strings = bp.strings,
.variable_map = &variable_map,
};
switch (stmt.*) {
.compound => |*b| try resolve_block(inner_bp, b),
.@"for" => |f| {
switch (f.init) {
.decl => |d| try resolve_decl(inner_bp, d),
.expr => |e| try resolve_expr(inner_bp, e),
.none => {},
}
if (f.cond) |c| try resolve_expr(inner_bp, c);
if (f.post) |p| try resolve_expr(inner_bp, p);
try resolve_stmt(inner_bp, f.body);
},
else => unreachable,
}
},
Regarding loop labelling, the Book does this in a separate pass from variable resolution. I do not particularly feel like creating yet another file (as I have each compiler pass in its own file), so I will try to do it within resolve_stmt. After all, all the related structures are statements.
Since it is being called recursively, an additional parameter is needed. I will pass it separately to avoid updating the Boilerplate struct for every time resolve_stmt is called, which would, ironically, increase the boilerplate.
This is the new resolve_stmt in all its glory.
fn resolve_stmt(
bp: Boilerplate,
current_label: ?[:0]const u8,
stmt: *ast.Stmt,
) Error!void {
switch (stmt.*) {
.null => {},
.@"break", .@"continue" => |*l| l.* = current_label orelse
return error.BreakOutsideLoop,
.@"return", .expr => |expr| try resolve_expr(bp, expr),
.@"if" => |i| {
try resolve_expr(bp, i.cond);
try resolve_stmt(bp, current_label, i.then);
if (i.@"else") |e|
try resolve_stmt(bp, current_label, e);
},
.@"while", .do_while => |*w| {
const label = try bp.make_temporary("while");
w.label = label; // forgot this on the first pass!
try resolve_expr(bp, w.cond);
try resolve_stmt(bp, label, w.body);
},
.@"for", .compound => {
var variable_map = try bp.variable_map.clone(bp.gpa);
defer variable_map.deinit(bp.gpa);
var iter = variable_map.valueIterator();
while (iter.next()) |value|
value.* = .{ .name = value.name, .scope = .parent };
const inner_bp: Boilerplate = .{
.gpa = bp.gpa,
.strings = bp.strings,
.variable_map = &variable_map,
};
switch (stmt.*) {
.compound => |*b| try resolve_block(inner_bp, current_label, b),
.@"for" => |*f| {
const label = try bp.make_temporary("for");
f.label = label;
switch (f.init) {
.decl => |d| try resolve_decl(inner_bp, d),
.expr => |e| try resolve_expr(inner_bp, e),
.none => {},
}
if (f.cond) |c| try resolve_expr(inner_bp, c);
if (f.post) |p| try resolve_expr(inner_bp, p);
try resolve_stmt(inner_bp, label, f.body);
},
else => unreachable,
}
},
}
}
With tiny related adjustments to resolve_block's body and signature and resolve_func_def's body, the code is good to go. The Eye Test I set up a couple of chapters earlier allowed me to catch that I was not actually assigning the labels to the blocks, a mistake I would not have caught otherwise until much later.
IR Generation
All the new structures in this chapter can be implemented by the same IR instructions done in previous ones. Jumps and Labels. Who needs structured programming anyway?
Now, labels are needed for break and continue statements's translation to jumps. To make sure the labels are consistent, they should be generated out of the loop labels constructed last section. So first I am adding another helper function to my Boilerplate struct, that creates new strings out of old ones.
fn augment_label(
self: @This(),
comptime prefix: []const u8,
label: [:0]const u8,
) Error![:0]const u8 {
const cat = try std.fmt.allocPrint(self.alloc, prefix ++ "_{s}", .{label});
defer self.alloc.free(cat);
const name = try self.strings.get_or_put(self.alloc, cat);
return name.string;
}
do while loops are perhaps the easiest.
.do_while => |w| {
const st = try bp.augment_label("st", w.label.?);
const br = try bp.augment_label("br", w.label.?);
const cn = try bp.augment_label("cn", w.label.?);
try bp.append(.{ .label = st });
try stmt_emit_ir(bp, w.body);
try bp.append(.{ .label = cn });
const v = try expr_emit_ir(bp, w.cond);
bp.append(.{ .jump_nz = .init(v, st) });
try bp.append(.{ .label = br });
},
Everything else is, to be honest, just copied off the Book.
.@"while" => |w| {
const br = try bp.augment_label("br", w.label.?);
const cn = try bp.augment_label("cn", w.label.?);
try bp.append(.{ .label = cn });
const v = try expr_emit_ir(bp, w.cond);
try bp.append(.{ .jump_z = .init(v, br) });
try stmt_emit_ir(bp, w.body);
try bp.append(.{ .jump = cn });
try bp.append(.{ .label = br });
},
.@"for" => |f| {
const st = try bp.augment_label("st", f.label.?);
const br = try bp.augment_label("br", f.label.?);
const cn = try bp.augment_label("cn", f.label.?);
switch (f.init) {
.decl => |d| try decl_emit_ir(bp, d),
.expr => |e| _ = try expr_emit_ir(bp, e),
.none => {},
}
try bp.append(.{ .label = st });
if (f.cond) |c| {
const v = try expr_emit_ir(bp, c);
try bp.append(.{ .jump_z = .init(v, br) });
}
try stmt_emit_ir(bp, f.body);
try bp.append(.{ .label = cn });
if (f.post) |p|
_ = try expr_emit_ir(bp, p);
try bp.append(.{ .jump = st });
try bp.append(.{ .label = br });
},
.@"break" => |l| try bp.append(.{
.jump = try bp.augment_label("br", l.?),
}),
.@"continue" => |l| try bp.append(.{
.jump = try bp.augment_label("cn", l.?),
}),
One fun detail here, the last two calls to augment_label will not allocate the string again. The string interner should just use the same string allocated previously. I'd perhaps test that to make sure, but eh.
Segmentation Faults and How to Fix Them
Running the eye test on Chapter 8's valid code, I quickly hit a segmentation fault when printing the IR instructions for this code.
int main(void) {
int acc = 0;
int x = 100;
while (x) {
int y = 10;
x = x - y;
while (y) {
acc = acc + 1;
y = y - 1;
}
}
return acc == 100 && x == 0;
}
I am sure the smart ones of you figured out the problem back in chapter 3. When I figured out what caused it, I got amused it did not happen sooner.
The problem, my dear reader, is that my beloved string interner exceeded its capacity and reallocated its inner ArrayList, invalidating all the pointers I had around the codebase to its slices. Rust would've never!
Changing this is really trivial. All I need to do really is replace almost every occurrence of [:0]const u8 in the code (which is usually the interned string), with StringInterner.ID. The actual problem, which is why I chose to put the string slices around in the first place, is that I cannot access the String Interner from the pretty printers. Allow me to demonstrate. This is ir.FuncDef in its entirety.
pub const FuncDef = struct {
name: [:0]const u8,
instrs: std.ArrayListUnmanaged(Instr),
fn deinit(self: *@This(), alloc: std.mem.Allocator) void {
self.instrs.deinit(alloc);
}
pub fn format(
self: @This(),
comptime _: []const u8,
options: std.fmt.FormatOptions,
writer: anytype,
) !void {
const w = options.width orelse 0;
try writer.writeByteNTimes('\t', w);
try writer.print("FUNCTION {s}\n", .{self.name}); // <- printing name here
for (self.instrs.items) |instr|
try writer.print("{:[1]}\n", .{
instr,
w + 1,
});
}
};
I could store the numerical ID that is assigned to each string. But where else am I even using the strings, then? I am also using the same format mechanism to output the final assembly code.
The most straightforward, and annoying, solution is to add a pointer to the string interner for almost every single type in my program. The other solution is to have a global StringInterner, and I have avoided using globals in the program so far.
A completely insane solution would be to store the pointer to the StringInterner (not a pointer to its bytes array,) in the Idx object I'd use instead of [:0]const u8.
So first let's do the easy part. get_or_put now returns a small struct with Idx and a string slice, and I can make it return only the Idx, and let the Zig compiler tell me where I need to fix the types.
pub fn get_or_put(
self: *StringInterner,
gpa: std.mem.Allocator,
string: []const u8,
) std.mem.Allocator.Error!Idx { // <-- change here
try self.bytes.ensureUnusedCapacity(gpa, string.len + 1);
try self.map.ensureUnusedCapacityContext(gpa, 1, .{ .bytes = &self.bytes });
const adapter: std.hash_map.StringIndexAdapter = .{ .bytes = &self.bytes };
const gop = self.map.getOrPutAssumeCapacityAdapted(string, adapter);
if (gop.found_existing)
return gop.key_ptr.*; // <-- and here
const new_id: Idx = @intCast(self.bytes.items.len);
self.bytes.appendSliceAssumeCapacity(string);
self.bytes.appendAssumeCapacity(0);
gop.key_ptr.* = new_id;
return new_id; // <-- and here
}
Simple enough. zig build tells me I am using this type in 4 places. All of them look like name.string. So I will just make them return name (which is really Idx), and fix the return types of their surrounding functions. One example is the one mentioned earlier, augment_label.
fn augment_label(
self: @This(),
comptime prefix: []const u8,
label: utils.StringInterner.Idx, // <-- change here
) Error!utils.StringInterner.Idx { // <-- and here
const st_label = self.strings.get_string(label).?; // <-- addition
const cat = try std.fmt.allocPrint(self.alloc, prefix ++ "_{s}", .{st_label});
defer self.alloc.free(cat);
const name = try self.strings.get_or_put(self.alloc, cat);
return name; // <-- and here.
}
So many errors!! Now we go over the types. A search for [:0]const u8 is going to return a shitton of results, but persevere I must. The previously mentioned ir.FuncDef for example, becomes the following. Pretend the formatting problem is solved for now.
pub const FuncDef = struct {
name: utils.StringInterner.Idx,
instrs: std.ArrayListUnmanaged(Instr),
fn deinit(self: *@This(), alloc: std.mem.Allocator) void {
self.instrs.deinit(alloc);
}
}
Then the functions must ne changed. If I am not mistaken, all the functions dealing with the string interner actually live in Boilerplate structs. So time to check those. Here is the new ir_gen.Boilerplate.make_temporary.
fn make_temporary(
self: @This(),
comptime prefix: []const u8,
) Error!utils.StringInterner.Idx { // <- only here
return try self.strings.make_temporary(self.alloc, prefix);
}
There is a lot of leg work here that I will spare you the boring details of.
A few details that came up showing how deep the assumption is within the codebase. One of them is the different StringHashMaps around the code. They do not manage the strings, I do. And now they are all invalidated! What if I just solve this with a much bigger starting capacity for the string interner?[^branch]
The other big one is that in semantic analysis, I replaced the pointers to the old names (which are allocated from the source) with pointers within the string interner. It means, if I were to keep to the same structure of files, I need to replace the name fields in all AST types dealing with variables with an Identifier type, defined thus.
pub const Identifier = union(enum) {
name: []const u8,
idx: utils.StringInterner.Idx,
};
And now ast.Decl is like this.
pub const Decl = struct {
name: Identifier,
init: ?*Expr,
};
After changing all the types, and fixing all the compilation errors, I wanted to make sure this thing works before trying to solve the formatting problem. So I took the C file mentioned above and sent it through all the stages up to codegen. First goes parsing:
PROGRAM
FUNCTION { 109, 97, 105, 110 }
int ast.Identifier{ .name = { 97, 99, 99 } } <- 0
int ast.Identifier{ .name = { 120 } } <- 100
WHILE ast.Identifier{ .name = { 120 } }
int ast.Identifier{ .name = { 121 } } <- 10
(ast.Identifier{ .name = { 120 } } <- (- ast.Identifier{ .name = { 120 } } ast.Identifier{ .name = { 121 } }));
WHILE ast.Identifier{ .name = { 121 } }
(ast.Identifier{ .name = { 97, 99, 99 } } <- (+ ast.Identifier{ .name = { 97, 99, 99 } } 1));
(ast.Identifier{ .name = { 121 } } <- (- ast.Identifier{ .name = { 121 } } 1));
RETURN (&& (== ast.Identifier{ .name = { 97, 99, 99 } } 100) (== ast.Identifier{ .name = { 120 } } 0))
Second is semantic analysis. Note how most of the numbers (outside of ast.identifier.etc) are actually variable names, or rather indices to variable names.
PROGRAM
FUNCTION { 109, 97, 105, 110 }
int ast.Identifier{ .idx = 0 } <- 0
int ast.Identifier{ .idx = 6 } <- 100
10: WHILE ast.Identifier{ .idx = 6 }
int ast.Identifier{ .idx = 18 } <- 10
(ast.Identifier{ .idx = 6 } <- (- ast.Identifier{ .idx = 6 } ast.Identifier{ .idx = 18 }));
22: WHILE ast.Identifier{ .idx = 18 }
(ast.Identifier{ .idx = 0 } <- (+ ast.Identifier{ .idx = 0 } 1));
(ast.Identifier{ .idx = 18 } <- (- ast.Identifier{ .idx = 18 } 1));
RETURN (&& (== ast.Identifier{ .idx = 0 } 100) (== ast.Identifier{ .idx = 6 } 0))
Following it up is the IR. 0 <- 0 is a funny one. Assigning a constant 0 to a variable whose name is at index 0. main amusingly, is actually at index 30.
PROGRAM
FUNCTION 30
0 <- 0
6 <- 100
=> 46
jz 6 => 35
18 <- 10
57 <- 6 - 18
6 <- 57
=> 74
jz 18 => 63
85 <- 0 + 1
0 <- 85
91 <- 18 - 1
18 <- 91
jump => 74
=> 63
jump => 46
=> 35
130 <- 0 == 100
jz 130 => 97
137 <- 6 == 0
jz 137 => 97
119 <- 1
jump => 109
=> 97
119 <- 0
=> 109
ret 119
ret 0
And finally, codegen.
PROGRAM
FUNCTION 30
allocate 36
mov imm 0 -> stack -4
mov imm 100 -> stack -8
=> .L46
cmp imm 0 -> stack -8
jmpe .L35
mov imm 10 -> stack -12
mov stack -8 -> R10
mov R10 -> stack -16
mov stack -12 -> R10
sub R10 -> stack -16
mov stack -16 -> R10
mov R10 -> stack -8
=> .L74
cmp imm 0 -> stack -12
jmpe .L63
mov stack -4 -> R10
mov R10 -> stack -20
add imm 1 -> stack -20
mov stack -20 -> R10
mov R10 -> stack -4
mov stack -12 -> R10
mov R10 -> stack -24
sub imm 1 -> stack -24
mov stack -24 -> R10
mov R10 -> stack -12
jmp .L74
=> .L63
jmp .L46
=> .L35
cmp imm 100 -> stack -4
mov imm 0 -> stack -28
sete stack -28
cmp imm 0 -> stack -28
jmpe .L97
cmp imm 0 -> stack -8
mov imm 0 -> stack -32
sete stack -32
cmp imm 0 -> stack -32
jmpe .L97
mov imm 1 -> stack -36
jmp .L109
=> .L97
mov imm 0 -> stack -36
=> .L109
mov stack -36 -> AX
ret
mov imm 0 -> AX
ret
It occurs to me looking at this last one is that only strings that survive to the final stage are labels and function names. (Only main for now). Even the labels can actually just be a .L35, or whatever number, which is a perfectly valid label identifier. So, now to get a working compiler all I need to actually fix in this stage is printing the function's name. To test that theory, I added a *utils.StringInterner field to both assembly.Prgm and assembly.FuncDef to get the name of the function out. It is a fairly small change in both assembly.zig and asm_gen.zig. You get this final assembly.
.globl _main
_main:
pushq %rbp
movq %rsp, %rbp
subq $36, %rsp
movl $0, -4(%rsp)
movl $100, -8(%rsp)
.L46:
cmpl $0, -8(%rsp)
je .L35
movl $10, -12(%rsp)
movl -8(%rsp), %r10d
movl %r10d, -16(%rsp)
movl -12(%rsp), %r10d
subl %r10d, -16(%rsp)
movl -16(%rsp), %r10d
movl %r10d, -8(%rsp)
.L74:
cmpl $0, -12(%rsp)
je .L63
movl -4(%rsp), %r10d
movl %r10d, -20(%rsp)
addl $1, -20(%rsp)
movl -20(%rsp), %r10d
movl %r10d, -4(%rsp)
movl -12(%rsp), %r10d
movl %r10d, -24(%rsp)
subl $1, -24(%rsp)
movl -24(%rsp), %r10d
movl %r10d, -12(%rsp)
jmp .L74
.L63:
jmp .L46
.L35:
cmpl $100, -4(%rsp)
movl $0, -28(%rsp)
sete -28(%rsp)
cmpl $0, -28(%rsp)
je .L97
cmpl $0, -8(%rsp)
movl $0, -32(%rsp)
sete -32(%rsp)
cmpl $0, -32(%rsp)
je .L97
movl $1, -36(%rsp)
jmp .L109
.L97:
movl $0, -36(%rsp)
.L109:
movl -36(%rsp), %eax
movq %rbp, %rsp
popq %rbp
ret
movl $0, %eax
movq %rbp, %rsp
popq %rbp
ret
I ran the program at its current stage through the test suite, and it passed all tests with flying colors. No segmentation faults!
Before actually tackling the printing problem, it would perhaps be better to change the utils.StringInterner.Idx type to be a wrapper around u32 rather than a straight up u32. It makes types a little bit safer (no adding two indices together). The change in the declaration is as simple as the following.1
pub const Idx = enum(u32) {
_,
pub fn format(
self: @This(),
comptime _: []const u8,
_: std.fmt.FormatOptions,
writer: anytype,
) !void {
try writer.print("[{d}]", .{@intFromEnum(self)});
}
};
And inside StringInterner's functions, the two builtin @intFromEnum and, you will never guess, @enumFromInt. Putting these in a few strategic places hides the u32 implementation, (including the formatting as .Lutils.StringInterner.Idx(28) is not actually a valid label identifier), and the tests keep on passing.
Looking at jj diff --stat, all the changes are summarized in the following. Not bad.
c_files/nested_loop | 2 ++
src/asm_gen.zig | 5 ++++-
src/asm_passes/pseudos.zig | 5 ++++-
src/assembly.zig | 30 ++++++++++++++++--------------
src/ast.zig | 34 ++++++++++++++++++++--------------
src/ir.zig | 24 ++++++++++++------------
src/ir_gen.zig | 17 +++++++++--------
src/main.zig | 2 +-
src/parser.zig | 8 ++++----
src/sema.zig | 28 ++++++++++++++++------------
src/utils.zig | 44 ++++++++++++++++++++++----------------------
11 files changed, 110 insertions(+), 89 deletions(-)
Fixing the Formatting Problem
As mentioned before, there are four options, on different levels of unhingedness.
- Add a
*utils.StringInternerfield to every type that may contain a string (as done already in this example forassembly.FuncDef) and every function that generates them (a lot of them do already via theBoilerplatestructs). Then when formatting, one just refers to the inner field. - Add a global
*utils.StringInterner, and remove it from theBoilerplatestructs. I do not like globals too much, but this is the least disruptive to the code. - Change the
Idxtype to hold its own pointer to the string interner.I have no idea how this would even begin to look like and it is probably insane.It works perfectly and it is definitely insane. - Just .. increase the starting buffer for interner to a large enough size that it never needs to reallocate. This is a terrible idea for a real program but this is not actually a real program.
- Forgo pretty printing the middle stages entirely. The current status runs and passes fine as is.
As insane as it sounds, I went with 3. The resulting type is no larger than a slice, which I already had. It keeps the relevant data where it is (in the Idx). I still think it is a totally insane idea. But the tests pass, the printer prints, things work.
And this wraps chapter 8.
Lessons Learned
- Loops are interesting
- Do not add a
forloop to my language. - To love Rust more. Rust would never have let me segfault!
- Er .. refactoring in Zig, I guess? The last section as a whole is a Lessons Learned, to be honest.