1const std = @import("std");
2const Ast = std.zig.Ast;
3const Walk = @This();
4const assert = std.debug.assert;
5const BuiltinFn = std.zig.BuiltinFn;
6
7ast: *const Ast,
8transformations: *std.array_list.Managed(Transformation),
9unreferenced_globals: std.array_hash_map.String(Ast.Node.Index),
10in_scope_names: std.array_hash_map.String(u32),
11replace_names: std.array_hash_map.String(u32),
12gpa: std.mem.Allocator,
13arena: std.mem.Allocator,
14
15pub const Transformation = union(enum) {
16 /// Replace the fn decl AST Node with one whose body is only `@trap()` with
17 /// discarded parameters.
18 gut_function: Ast.Node.Index,
19 /// Omit a global declaration.
20 delete_node: Ast.Node.Index,
21 /// Delete a local variable declaration and replace all of its references
22 /// with `undefined`.
23 delete_var_decl: struct {
24 var_decl_node: Ast.Node.Index,
25 /// Identifier nodes that reference the variable.
26 references: std.ArrayList(Ast.Node.Index),
27 },
28 /// Replace an expression with `undefined`.
29 replace_with_undef: Ast.Node.Index,
30 /// Replace an expression with `true`.
31 replace_with_true: Ast.Node.Index,
32 /// Replace an expression with `false`.
33 replace_with_false: Ast.Node.Index,
34 /// Replace a node with another node.
35 replace_node: struct {
36 to_replace: Ast.Node.Index,
37 replacement: Ast.Node.Index,
38 },
39 /// Replace an `@import` with the imported file contents wrapped in a struct.
40 inline_imported_file: InlineImportedFile,
41
42 pub const InlineImportedFile = struct {
43 builtin_call_node: Ast.Node.Index,
44 imported_string: []const u8,
45 /// Identifier names that must be renamed in the inlined code or else
46 /// will cause ambiguous reference errors.
47 in_scope_names: std.array_hash_map.String(void),
48 };
49};
50
51pub const Error = error{OutOfMemory};
52
53/// The result will be priority shuffled.
54pub fn findTransformations(
55 arena: std.mem.Allocator,
56 ast: *const Ast,
57 transformations: *std.array_list.Managed(Transformation),
58) !void {
59 transformations.clearRetainingCapacity();
60
61 var walk: Walk = .{
62 .ast = ast,
63 .transformations = transformations,
64 .gpa = transformations.allocator,
65 .arena = arena,
66 .unreferenced_globals = .empty,
67 .in_scope_names = .empty,
68 .replace_names = .empty,
69 };
70 defer {
71 walk.unreferenced_globals.deinit(walk.gpa);
72 walk.in_scope_names.deinit(walk.gpa);
73 walk.replace_names.deinit(walk.gpa);
74 }
75
76 try walkMembers(&walk, walk.ast.rootDecls());
77
78 const unreferenced_globals = walk.unreferenced_globals.values();
79 try transformations.ensureUnusedCapacity(unreferenced_globals.len);
80 for (unreferenced_globals) |node| {
81 transformations.appendAssumeCapacity(.{ .delete_node = node });
82 }
83}
84
85fn walkMembers(w: *Walk, members: []const Ast.Node.Index) Error!void {
86 // First we scan for globals so that we can delete them while walking.
87 try scanDecls(w, members, .add);
88
89 for (members) |member| {
90 try walkMember(w, member);
91 }
92
93 try scanDecls(w, members, .remove);
94}
95
96const ScanDeclsAction = enum { add, remove };
97
98fn scanDecls(w: *Walk, members: []const Ast.Node.Index, action: ScanDeclsAction) Error!void {
99 const ast = w.ast;
100 const gpa = w.gpa;
101
102 for (members) |member_node| {
103 const name_token = switch (ast.nodeTag(member_node)) {
104 .global_var_decl,
105 .local_var_decl,
106 .simple_var_decl,
107 .aligned_var_decl,
108 => ast.nodeMainToken(member_node) + 1,
109
110 .fn_proto_simple,
111 .fn_proto_multi,
112 .fn_proto_one,
113 .fn_proto,
114 .fn_decl,
115 => ast.nodeMainToken(member_node) + 1,
116
117 else => continue,
118 };
119
120 assert(ast.tokenTag(name_token) == .identifier);
121 const name_bytes = ast.tokenSlice(name_token);
122
123 switch (action) {
124 .add => {
125 try w.unreferenced_globals.put(gpa, name_bytes, member_node);
126
127 const gop = try w.in_scope_names.getOrPut(gpa, name_bytes);
128 if (!gop.found_existing) gop.value_ptr.* = 0;
129 gop.value_ptr.* += 1;
130 },
131 .remove => {
132 const entry = w.in_scope_names.getEntry(name_bytes).?;
133 if (entry.value_ptr.* <= 1) {
134 assert(w.in_scope_names.swapRemove(name_bytes));
135 } else {
136 entry.value_ptr.* -= 1;
137 }
138 },
139 }
140 }
141}
142
143fn walkMember(w: *Walk, decl: Ast.Node.Index) Error!void {
144 const ast = w.ast;
145 switch (ast.nodeTag(decl)) {
146 .fn_decl => {
147 const fn_proto, const body_node = ast.nodeData(decl).node_and_node;
148 try walkExpression(w, fn_proto);
149 if (!isFnBodyGutted(ast, body_node)) {
150 w.replace_names.clearRetainingCapacity();
151 try w.transformations.append(.{ .gut_function = decl });
152 try walkExpression(w, body_node);
153 }
154 },
155 .fn_proto_simple,
156 .fn_proto_multi,
157 .fn_proto_one,
158 .fn_proto,
159 => {
160 try walkExpression(w, decl);
161 },
162
163 .global_var_decl,
164 .local_var_decl,
165 .simple_var_decl,
166 .aligned_var_decl,
167 => try walkGlobalVarDecl(w, decl, ast.fullVarDecl(decl).?),
168
169 .test_decl => {
170 try w.transformations.append(.{ .delete_node = decl });
171 try walkExpression(w, ast.nodeData(decl).opt_token_and_node[1]);
172 },
173
174 .container_field_init,
175 .container_field_align,
176 .container_field,
177 => {
178 try w.transformations.append(.{ .delete_node = decl });
179 try walkContainerField(w, ast.fullContainerField(decl).?);
180 },
181
182 .@"comptime" => {
183 try w.transformations.append(.{ .delete_node = decl });
184 try walkExpression(w, decl);
185 },
186
187 .root => unreachable,
188 else => unreachable,
189 }
190}
191
192fn walkExpression(w: *Walk, node: Ast.Node.Index) Error!void {
193 const ast = w.ast;
194 switch (ast.nodeTag(node)) {
195 .identifier => {
196 const name_ident = ast.nodeMainToken(node);
197 assert(ast.tokenTag(name_ident) == .identifier);
198 const name_bytes = ast.tokenSlice(name_ident);
199 _ = w.unreferenced_globals.swapRemove(name_bytes);
200 if (w.replace_names.get(name_bytes)) |index| {
201 try w.transformations.items[index].delete_var_decl.references.append(w.arena, node);
202 }
203 },
204
205 .number_literal,
206 .char_literal,
207 .unreachable_literal,
208 .anyframe_literal,
209 .string_literal,
210 => {},
211
212 .multiline_string_literal => {},
213
214 .error_value => {},
215
216 .block_two,
217 .block_two_semicolon,
218 .block,
219 .block_semicolon,
220 => {
221 var buf: [2]Ast.Node.Index = undefined;
222 const statements = ast.blockStatements(&buf, node).?;
223 return walkBlock(w, node, statements);
224 },
225
226 .@"defer",
227 .@"errdefer",
228 .@"comptime",
229 .@"nosuspend",
230 .@"suspend",
231 => {
232 return walkExpression(w, ast.nodeData(node).node);
233 },
234
235 .field_access => {
236 try walkExpression(w, ast.nodeData(node).node_and_token[0]);
237 },
238
239 .for_range => {
240 const start, const opt_end = ast.nodeData(node).node_and_opt_node;
241 try walkExpression(w, start);
242 if (opt_end.unwrap()) |end| {
243 return walkExpression(w, end);
244 }
245 },
246
247 .add,
248 .add_wrap,
249 .add_sat,
250 .array_cat,
251 .assign,
252 .assign_bit_and,
253 .assign_bit_or,
254 .assign_shl,
255 .assign_shl_sat,
256 .assign_shr,
257 .assign_bit_xor,
258 .assign_div,
259 .assign_sub,
260 .assign_sub_wrap,
261 .assign_sub_sat,
262 .assign_mod,
263 .assign_add,
264 .assign_add_wrap,
265 .assign_add_sat,
266 .assign_mul,
267 .assign_mul_wrap,
268 .assign_mul_sat,
269 .bang_equal,
270 .bit_and,
271 .bit_or,
272 .shl,
273 .shl_sat,
274 .shr,
275 .bit_xor,
276 .bool_and,
277 .bool_or,
278 .div,
279 .equal_equal,
280 .greater_or_equal,
281 .greater_than,
282 .less_or_equal,
283 .less_than,
284 .merge_error_sets,
285 .mod,
286 .mul,
287 .mul_wrap,
288 .mul_sat,
289 .sub,
290 .sub_wrap,
291 .sub_sat,
292 .@"catch",
293 .error_union,
294 .switch_range,
295 .@"orelse",
296 .array_access,
297 => {
298 const lhs, const rhs = ast.nodeData(node).node_and_node;
299 try walkExpression(w, lhs);
300 try walkExpression(w, rhs);
301 },
302
303 .assign_destructure => {
304 const full = ast.assignDestructure(node);
305 for (full.ast.variables) |variable_node| {
306 switch (ast.nodeTag(variable_node)) {
307 .global_var_decl,
308 .local_var_decl,
309 .simple_var_decl,
310 .aligned_var_decl,
311 => try walkLocalVarDecl(w, ast.fullVarDecl(variable_node).?),
312
313 else => try walkExpression(w, variable_node),
314 }
315 }
316 return walkExpression(w, full.ast.value_expr);
317 },
318
319 .bit_not,
320 .bool_not,
321 .negation,
322 .negation_wrap,
323 .optional_type,
324 .address_of,
325 .@"try",
326 .@"resume",
327 .deref,
328 => {
329 return walkExpression(w, ast.nodeData(node).node);
330 },
331
332 .array_type,
333 .array_type_sentinel,
334 => {},
335
336 .ptr_type_aligned,
337 .ptr_type_sentinel,
338 .ptr_type,
339 .ptr_type_bit_range,
340 => {},
341
342 .array_init_one,
343 .array_init_one_comma,
344 .array_init_dot_two,
345 .array_init_dot_two_comma,
346 .array_init_dot,
347 .array_init_dot_comma,
348 .array_init,
349 .array_init_comma,
350 => {
351 var elements: [2]Ast.Node.Index = undefined;
352 return walkArrayInit(w, ast.fullArrayInit(&elements, node).?);
353 },
354
355 .struct_init_one,
356 .struct_init_one_comma,
357 .struct_init_dot_two,
358 .struct_init_dot_two_comma,
359 .struct_init_dot,
360 .struct_init_dot_comma,
361 .struct_init,
362 .struct_init_comma,
363 => {
364 var buf: [2]Ast.Node.Index = undefined;
365 return walkStructInit(w, node, ast.fullStructInit(&buf, node).?);
366 },
367
368 .call_one,
369 .call_one_comma,
370 .call,
371 .call_comma,
372 => {
373 var buf: [1]Ast.Node.Index = undefined;
374 return walkCall(w, ast.fullCall(&buf, node).?);
375 },
376
377 .slice_open, .slice, .slice_sentinel => return walkSlice(w, node, ast.fullSlice(node).?),
378
379 .unwrap_optional => {
380 try walkExpression(w, ast.nodeData(node).node_and_token[0]);
381 },
382
383 .@"break" => {
384 const label_token, const target = ast.nodeData(node).opt_token_and_opt_node;
385 if (label_token == .none and target == .none) {
386 // no expressions
387 } else if (label_token == .none and target != .none) {
388 try walkExpression(w, target.unwrap().?);
389 } else if (label_token != .none and target == .none) {
390 try walkIdentifier(w, label_token.unwrap().?);
391 } else if (label_token != .none and target != .none) {
392 try walkExpression(w, target.unwrap().?);
393 }
394 },
395
396 .@"continue" => {
397 const opt_label = ast.nodeData(node).opt_token_and_opt_node[0];
398 if (opt_label.unwrap()) |label| {
399 return walkIdentifier(w, label);
400 }
401 },
402
403 .@"return" => {
404 if (ast.nodeData(node).opt_node.unwrap()) |lhs| {
405 try walkExpression(w, lhs);
406 }
407 },
408
409 .grouped_expression => {
410 try walkExpression(w, ast.nodeData(node).node_and_token[0]);
411 },
412
413 .container_decl,
414 .container_decl_trailing,
415 .container_decl_arg,
416 .container_decl_arg_trailing,
417 .container_decl_two,
418 .container_decl_two_trailing,
419 .tagged_union,
420 .tagged_union_trailing,
421 .tagged_union_enum_tag,
422 .tagged_union_enum_tag_trailing,
423 .tagged_union_two,
424 .tagged_union_two_trailing,
425 => {
426 var buf: [2]Ast.Node.Index = undefined;
427 return walkContainerDecl(w, node, ast.fullContainerDecl(&buf, node).?);
428 },
429
430 .error_set_decl => {
431 const lbrace, const rbrace = ast.nodeData(node).token_and_token;
432
433 var i = lbrace + 1;
434 while (i < rbrace) : (i += 1) {
435 switch (ast.tokenTag(i)) {
436 .doc_comment => unreachable, // TODO
437 .identifier => try walkIdentifier(w, i),
438 .comma => {},
439 else => unreachable,
440 }
441 }
442 },
443
444 .builtin_call_two,
445 .builtin_call_two_comma,
446 .builtin_call,
447 .builtin_call_comma,
448 => {
449 var buf: [2]Ast.Node.Index = undefined;
450 const params = ast.builtinCallParams(&buf, node).?;
451 return walkBuiltinCall(w, node, params);
452 },
453
454 .fn_proto_simple,
455 .fn_proto_multi,
456 .fn_proto_one,
457 .fn_proto,
458 => {
459 var buf: [1]Ast.Node.Index = undefined;
460 return walkFnProto(w, ast.fullFnProto(&buf, node).?);
461 },
462
463 .anyframe_type => {
464 _, const child_type = ast.nodeData(node).token_and_node;
465 return walkExpression(w, child_type);
466 },
467
468 .@"switch",
469 .switch_comma,
470 => {
471 const full = ast.fullSwitch(node).?;
472 try walkExpression(w, full.ast.condition); // condition expression
473 try walkExpressions(w, full.ast.cases);
474 },
475
476 .switch_case_one,
477 .switch_case_inline_one,
478 .switch_case,
479 .switch_case_inline,
480 => return walkSwitchCase(w, ast.fullSwitchCase(node).?),
481
482 .while_simple,
483 .while_cont,
484 .@"while",
485 => return walkWhile(w, node, ast.fullWhile(node).?),
486
487 .for_simple,
488 .@"for",
489 => return walkFor(w, ast.fullFor(node).?),
490
491 .if_simple,
492 .@"if",
493 => return walkIf(w, node, ast.fullIf(node).?),
494
495 .asm_simple,
496 .@"asm",
497 => return walkAsm(w, ast.fullAsm(node).?),
498
499 .enum_literal => {
500 return walkIdentifier(w, ast.nodeMainToken(node)); // name
501 },
502
503 .fn_decl => unreachable,
504 .container_field => unreachable,
505 .container_field_init => unreachable,
506 .container_field_align => unreachable,
507 .root => unreachable,
508 .global_var_decl => unreachable,
509 .local_var_decl => unreachable,
510 .simple_var_decl => unreachable,
511 .aligned_var_decl => unreachable,
512 .test_decl => unreachable,
513 .asm_output => unreachable,
514 .asm_input => unreachable,
515 }
516}
517
518fn walkGlobalVarDecl(w: *Walk, decl_node: Ast.Node.Index, var_decl: Ast.full.VarDecl) Error!void {
519 _ = decl_node;
520
521 if (var_decl.ast.type_node.unwrap()) |type_node| {
522 try walkExpression(w, type_node);
523 }
524
525 if (var_decl.ast.align_node.unwrap()) |align_node| {
526 try walkExpression(w, align_node);
527 }
528
529 if (var_decl.ast.addrspace_node.unwrap()) |addrspace_node| {
530 try walkExpression(w, addrspace_node);
531 }
532
533 if (var_decl.ast.section_node.unwrap()) |section_node| {
534 try walkExpression(w, section_node);
535 }
536
537 if (var_decl.ast.init_node.unwrap()) |init_node| {
538 if (!isUndefinedIdent(w.ast, init_node)) {
539 try w.transformations.append(.{ .replace_with_undef = init_node });
540 }
541 try walkExpression(w, init_node);
542 }
543}
544
545fn walkLocalVarDecl(w: *Walk, var_decl: Ast.full.VarDecl) Error!void {
546 try walkIdentifierNew(w, var_decl.ast.mut_token + 1); // name
547
548 if (var_decl.ast.type_node.unwrap()) |type_node| {
549 try walkExpression(w, type_node);
550 }
551
552 if (var_decl.ast.align_node.unwrap()) |align_node| {
553 try walkExpression(w, align_node);
554 }
555
556 if (var_decl.ast.addrspace_node.unwrap()) |addrspace_node| {
557 try walkExpression(w, addrspace_node);
558 }
559
560 if (var_decl.ast.section_node.unwrap()) |section_node| {
561 try walkExpression(w, section_node);
562 }
563
564 if (var_decl.ast.init_node.unwrap()) |init_node| {
565 if (!isUndefinedIdent(w.ast, init_node)) {
566 try w.transformations.append(.{ .replace_with_undef = init_node });
567 }
568 try walkExpression(w, init_node);
569 }
570}
571
572fn walkContainerField(w: *Walk, field: Ast.full.ContainerField) Error!void {
573 if (field.ast.type_expr.unwrap()) |type_expr| {
574 try walkExpression(w, type_expr); // type
575 }
576 if (field.ast.align_expr.unwrap()) |align_expr| {
577 try walkExpression(w, align_expr); // alignment
578 }
579 if (field.ast.value_expr.unwrap()) |value_expr| {
580 try walkExpression(w, value_expr); // value
581 }
582}
583
584fn walkBlock(
585 w: *Walk,
586 block_node: Ast.Node.Index,
587 statements: []const Ast.Node.Index,
588) Error!void {
589 _ = block_node;
590 const ast = w.ast;
591
592 for (statements) |stmt| {
593 switch (ast.nodeTag(stmt)) {
594 .global_var_decl,
595 .local_var_decl,
596 .simple_var_decl,
597 .aligned_var_decl,
598 => {
599 const var_decl = ast.fullVarDecl(stmt).?;
600 if (var_decl.ast.init_node != .none and
601 isUndefinedIdent(w.ast, var_decl.ast.init_node.unwrap().?))
602 {
603 try w.transformations.append(.{ .delete_var_decl = .{
604 .var_decl_node = stmt,
605 .references = .empty,
606 } });
607 const name_tok = var_decl.ast.mut_token + 1;
608 const name_bytes = ast.tokenSlice(name_tok);
609 try w.replace_names.put(w.gpa, name_bytes, @intCast(w.transformations.items.len - 1));
610 } else {
611 try walkLocalVarDecl(w, var_decl);
612 }
613 },
614
615 else => {
616 switch (categorizeStmt(ast, stmt)) {
617 // Don't try to remove `_ = foo;` discards; those are handled separately.
618 .discard_identifier => {},
619 // definitely try to remove `_ = undefined;` though.
620 .discard_undefined, .trap_call, .other => {
621 try w.transformations.append(.{ .delete_node = stmt });
622 },
623 }
624 try walkExpression(w, stmt);
625 },
626 }
627 }
628}
629
630fn walkArrayType(w: *Walk, array_type: Ast.full.ArrayType) Error!void {
631 try walkExpression(w, array_type.ast.elem_count);
632 if (array_type.ast.sentinel.unwrap()) |sentinel| {
633 try walkExpression(w, sentinel);
634 }
635 return walkExpression(w, array_type.ast.elem_type);
636}
637
638fn walkArrayInit(w: *Walk, array_init: Ast.full.ArrayInit) Error!void {
639 if (array_init.ast.type_expr.unwrap()) |type_expr| {
640 try walkExpression(w, type_expr); // T
641 }
642 for (array_init.ast.elements) |elem_init| {
643 try walkExpression(w, elem_init);
644 }
645}
646
647fn walkStructInit(
648 w: *Walk,
649 struct_node: Ast.Node.Index,
650 struct_init: Ast.full.StructInit,
651) Error!void {
652 _ = struct_node;
653 if (struct_init.ast.type_expr.unwrap()) |type_expr| {
654 try walkExpression(w, type_expr); // T
655 }
656 for (struct_init.ast.fields) |field_init| {
657 try walkExpression(w, field_init);
658 }
659}
660
661fn walkCall(w: *Walk, call: Ast.full.Call) Error!void {
662 try walkExpression(w, call.ast.fn_expr);
663 try walkExpressions(w, call.ast.params);
664}
665
666fn walkSlice(
667 w: *Walk,
668 slice_node: Ast.Node.Index,
669 slice: Ast.full.Slice,
670) Error!void {
671 _ = slice_node;
672 try walkExpression(w, slice.ast.sliced);
673 try walkExpression(w, slice.ast.start);
674 if (slice.ast.end.unwrap()) |end| {
675 try walkExpression(w, end);
676 }
677 if (slice.ast.sentinel.unwrap()) |sentinel| {
678 try walkExpression(w, sentinel);
679 }
680}
681
682fn walkIdentifier(w: *Walk, name_ident: Ast.TokenIndex) Error!void {
683 const ast = w.ast;
684 assert(ast.tokenTag(name_ident) == .identifier);
685 const name_bytes = ast.tokenSlice(name_ident);
686 _ = w.unreferenced_globals.swapRemove(name_bytes);
687}
688
689fn walkIdentifierNew(w: *Walk, name_ident: Ast.TokenIndex) Error!void {
690 _ = w;
691 _ = name_ident;
692}
693
694fn walkContainerDecl(
695 w: *Walk,
696 container_decl_node: Ast.Node.Index,
697 container_decl: Ast.full.ContainerDecl,
698) Error!void {
699 _ = container_decl_node;
700 if (container_decl.ast.arg.unwrap()) |arg| {
701 try walkExpression(w, arg);
702 }
703 try walkMembers(w, container_decl.ast.members);
704}
705
706fn walkBuiltinCall(
707 w: *Walk,
708 call_node: Ast.Node.Index,
709 params: []const Ast.Node.Index,
710) Error!void {
711 const ast = w.ast;
712 const builtin_token = ast.nodeMainToken(call_node);
713 const builtin_name = ast.tokenSlice(builtin_token);
714 const info = BuiltinFn.list.get(builtin_name).?;
715 switch (info.tag) {
716 .import => {
717 const operand_node = params[0];
718 const str_lit_token = ast.nodeMainToken(operand_node);
719 const token_bytes = ast.tokenSlice(str_lit_token);
720 if (std.mem.endsWith(u8, token_bytes, ".zig\"")) {
721 const imported_string = std.zig.string_literal.parseAlloc(w.arena, token_bytes) catch
722 unreachable;
723 try w.transformations.append(.{ .inline_imported_file = .{
724 .builtin_call_node = call_node,
725 .imported_string = imported_string,
726 .in_scope_names = try std.array_hash_map.String(void).init(
727 w.arena,
728 w.in_scope_names.keys(),
729 &.{},
730 ),
731 } });
732 }
733 },
734 else => {},
735 }
736 for (params) |param_node| {
737 try walkExpression(w, param_node);
738 }
739}
740
741fn walkFnProto(w: *Walk, fn_proto: Ast.full.FnProto) Error!void {
742 const ast = w.ast;
743
744 {
745 var it = fn_proto.iterate(ast);
746 while (it.next()) |param| {
747 if (param.type_expr) |type_expr| {
748 try walkExpression(w, type_expr);
749 }
750 }
751 }
752
753 if (fn_proto.ast.align_expr.unwrap()) |align_expr| {
754 try walkExpression(w, align_expr);
755 }
756
757 if (fn_proto.ast.addrspace_expr.unwrap()) |addrspace_expr| {
758 try walkExpression(w, addrspace_expr);
759 }
760
761 if (fn_proto.ast.section_expr.unwrap()) |section_expr| {
762 try walkExpression(w, section_expr);
763 }
764
765 if (fn_proto.ast.callconv_expr.unwrap()) |callconv_expr| {
766 try walkExpression(w, callconv_expr);
767 }
768
769 const return_type = fn_proto.ast.return_type.unwrap().?;
770 try walkExpression(w, return_type);
771}
772
773fn walkExpressions(w: *Walk, expressions: []const Ast.Node.Index) Error!void {
774 for (expressions) |expression| {
775 try walkExpression(w, expression);
776 }
777}
778
779fn walkSwitchCase(w: *Walk, switch_case: Ast.full.SwitchCase) Error!void {
780 for (switch_case.ast.values) |value_expr| {
781 try walkExpression(w, value_expr);
782 }
783 try walkExpression(w, switch_case.ast.target_expr);
784}
785
786fn walkWhile(w: *Walk, node_index: Ast.Node.Index, while_node: Ast.full.While) Error!void {
787 // Perform these transformations in this priority order:
788 // 1. If the `else` expression is missing or an empty block, replace the condition with `if (true)` if it is not already.
789 // 2. If the `then` block is empty, replace the condition with `if (false)` if it is not already.
790 // 3. If the condition is `if (true)`, replace the `if` expression with the contents of the `then` expression.
791 // 4. If the condition is `if (false)`, replace the `if` expression with the contents of the `else` expression.
792 if (!isTrueIdent(w.ast, while_node.ast.cond_expr) and
793 (while_node.ast.else_expr == .none or isEmptyBlock(w.ast, while_node.ast.else_expr.unwrap().?)))
794 {
795 try w.transformations.ensureUnusedCapacity(1);
796 w.transformations.appendAssumeCapacity(.{ .replace_with_true = while_node.ast.cond_expr });
797 } else if (!isFalseIdent(w.ast, while_node.ast.cond_expr) and isEmptyBlock(w.ast, while_node.ast.then_expr)) {
798 try w.transformations.ensureUnusedCapacity(1);
799 w.transformations.appendAssumeCapacity(.{ .replace_with_false = while_node.ast.cond_expr });
800 } else if (isTrueIdent(w.ast, while_node.ast.cond_expr)) {
801 try w.transformations.ensureUnusedCapacity(1);
802 w.transformations.appendAssumeCapacity(.{ .replace_node = .{
803 .to_replace = node_index,
804 .replacement = while_node.ast.then_expr,
805 } });
806 } else if (isFalseIdent(w.ast, while_node.ast.cond_expr)) {
807 try w.transformations.ensureUnusedCapacity(1);
808 w.transformations.appendAssumeCapacity(.{ .replace_node = .{
809 .to_replace = node_index,
810 .replacement = while_node.ast.else_expr.unwrap().?,
811 } });
812 }
813
814 try walkExpression(w, while_node.ast.cond_expr); // condition
815
816 if (while_node.ast.cont_expr.unwrap()) |cont_expr| {
817 try walkExpression(w, cont_expr);
818 }
819
820 try walkExpression(w, while_node.ast.then_expr);
821
822 if (while_node.ast.else_expr.unwrap()) |else_expr| {
823 try walkExpression(w, else_expr);
824 }
825}
826
827fn walkFor(w: *Walk, for_node: Ast.full.For) Error!void {
828 try walkExpressions(w, for_node.ast.inputs);
829 try walkExpression(w, for_node.ast.then_expr);
830 if (for_node.ast.else_expr.unwrap()) |else_expr| {
831 try walkExpression(w, else_expr);
832 }
833}
834
835fn walkIf(w: *Walk, node_index: Ast.Node.Index, if_node: Ast.full.If) Error!void {
836 // Perform these transformations in this priority order:
837 // 1. If the `else` expression is missing or an empty block, replace the condition with `if (true)` if it is not already.
838 // 2. If the `then` block is empty, replace the condition with `if (false)` if it is not already.
839 // 3. If the condition is `if (true)`, replace the `if` expression with the contents of the `then` expression.
840 // 4. If the condition is `if (false)`, replace the `if` expression with the contents of the `else` expression.
841 if (!isTrueIdent(w.ast, if_node.ast.cond_expr) and
842 (if_node.ast.else_expr == .none or isEmptyBlock(w.ast, if_node.ast.else_expr.unwrap().?)))
843 {
844 try w.transformations.ensureUnusedCapacity(1);
845 w.transformations.appendAssumeCapacity(.{ .replace_with_true = if_node.ast.cond_expr });
846 } else if (!isFalseIdent(w.ast, if_node.ast.cond_expr) and isEmptyBlock(w.ast, if_node.ast.then_expr)) {
847 try w.transformations.ensureUnusedCapacity(1);
848 w.transformations.appendAssumeCapacity(.{ .replace_with_false = if_node.ast.cond_expr });
849 } else if (isTrueIdent(w.ast, if_node.ast.cond_expr)) {
850 try w.transformations.ensureUnusedCapacity(1);
851 w.transformations.appendAssumeCapacity(.{ .replace_node = .{
852 .to_replace = node_index,
853 .replacement = if_node.ast.then_expr,
854 } });
855 } else if (isFalseIdent(w.ast, if_node.ast.cond_expr)) {
856 try w.transformations.ensureUnusedCapacity(1);
857 w.transformations.appendAssumeCapacity(.{ .replace_node = .{
858 .to_replace = node_index,
859 .replacement = if_node.ast.else_expr.unwrap().?,
860 } });
861 }
862
863 try walkExpression(w, if_node.ast.cond_expr); // condition
864 try walkExpression(w, if_node.ast.then_expr);
865 if (if_node.ast.else_expr.unwrap()) |else_expr| {
866 try walkExpression(w, else_expr);
867 }
868}
869
870fn walkAsm(w: *Walk, asm_node: Ast.full.Asm) Error!void {
871 try walkExpression(w, asm_node.ast.template);
872 try walkExpressions(w, asm_node.ast.items);
873}
874
875/// Check if it is already gutted (i.e. its body replaced with `@trap()`).
876fn isFnBodyGutted(ast: *const Ast, body_node: Ast.Node.Index) bool {
877 // skip over discards
878 var statements_buf: [2]Ast.Node.Index = undefined;
879 const statements = switch (ast.nodeTag(body_node)) {
880 .block_two,
881 .block_two_semicolon,
882 .block,
883 .block_semicolon,
884 => ast.blockStatements(&statements_buf, body_node).?,
885
886 else => return false,
887 };
888 var i: usize = 0;
889 while (i < statements.len) : (i += 1) {
890 switch (categorizeStmt(ast, statements[i])) {
891 .discard_identifier => continue,
892 .trap_call => return i + 1 == statements.len,
893 else => return false,
894 }
895 }
896 return false;
897}
898
899const StmtCategory = enum {
900 discard_undefined,
901 discard_identifier,
902 trap_call,
903 other,
904};
905
906fn categorizeStmt(ast: *const Ast, stmt: Ast.Node.Index) StmtCategory {
907 switch (ast.nodeTag(stmt)) {
908 .builtin_call_two,
909 .builtin_call_two_comma,
910 .builtin_call,
911 .builtin_call_comma,
912 => {
913 var buf: [2]Ast.Node.Index = undefined;
914 const params = ast.builtinCallParams(&buf, stmt).?;
915 return categorizeBuiltinCall(ast, ast.nodeMainToken(stmt), params);
916 },
917 .assign => {
918 const lhs, const rhs = ast.nodeData(stmt).node_and_node;
919 if (isDiscardIdent(ast, lhs) and ast.nodeTag(rhs) == .identifier) {
920 const name_bytes = ast.tokenSlice(ast.nodeMainToken(rhs));
921 if (std.mem.eql(u8, name_bytes, "undefined")) {
922 return .discard_undefined;
923 } else {
924 return .discard_identifier;
925 }
926 }
927 return .other;
928 },
929 else => return .other,
930 }
931}
932
933fn categorizeBuiltinCall(
934 ast: *const Ast,
935 builtin_token: Ast.TokenIndex,
936 params: []const Ast.Node.Index,
937) StmtCategory {
938 if (params.len != 0) return .other;
939 const name_bytes = ast.tokenSlice(builtin_token);
940 if (std.mem.eql(u8, name_bytes, "@trap"))
941 return .trap_call;
942 return .other;
943}
944
945fn isDiscardIdent(ast: *const Ast, node: Ast.Node.Index) bool {
946 return isMatchingIdent(ast, node, "_");
947}
948
949fn isUndefinedIdent(ast: *const Ast, node: Ast.Node.Index) bool {
950 return isMatchingIdent(ast, node, "undefined");
951}
952
953fn isTrueIdent(ast: *const Ast, node: Ast.Node.Index) bool {
954 return isMatchingIdent(ast, node, "true");
955}
956
957fn isFalseIdent(ast: *const Ast, node: Ast.Node.Index) bool {
958 return isMatchingIdent(ast, node, "false");
959}
960
961fn isMatchingIdent(ast: *const Ast, node: Ast.Node.Index, string: []const u8) bool {
962 switch (ast.nodeTag(node)) {
963 .identifier => {
964 const token_index = ast.nodeMainToken(node);
965 const name_bytes = ast.tokenSlice(token_index);
966 return std.mem.eql(u8, name_bytes, string);
967 },
968 else => return false,
969 }
970}
971
972fn isEmptyBlock(ast: *const Ast, node: Ast.Node.Index) bool {
973 switch (ast.nodeTag(node)) {
974 .block_two => {
975 const opt_lhs, const opt_rhs = ast.nodeData(node).opt_node_and_opt_node;
976 return opt_lhs == .none and opt_rhs == .none;
977 },
978 else => return false,
979 }
980}