1const std = @import("std");
2const Io = std.Io;
3const mem = std.mem;
4const Allocator = std.mem.Allocator;
5const assert = std.debug.assert;
6const Ast = std.zig.Ast;
7const Walk = @import("reduce/Walk.zig");
8const AstGen = std.zig.AstGen;
9const Zir = std.zig.Zir;
10
11const usage =
12 \\zig reduce [options] ./checker root_source_file.zig [-- [argv]]
13 \\
14 \\root_source_file.zig is relative to --main-mod-path.
15 \\
16 \\checker:
17 \\ An executable that communicates interestingness by returning these exit codes:
18 \\ exit(0): interesting
19 \\ exit(1): unknown (infinite loop or other mishap)
20 \\ exit(other): not interesting
21 \\
22 \\options:
23 \\ --seed [integer] Override the random seed. Defaults to 0
24 \\ --skip-smoke-test Skip interestingness check smoke test
25 \\ --mod [name]:[deps]:[src] Make a module available for dependency under the given name
26 \\ deps: [dep],[dep],...
27 \\ dep: [[import=]name]
28 \\ --deps [dep],[dep],... Set dependency names for the root package
29 \\ dep: [[import=]name]
30 \\ --main-mod-path Set the directory of the root module
31 \\
32 \\argv:
33 \\ Forwarded directly to the interestingness script.
34 \\
35;
36
37const Interestingness = enum { interesting, unknown, boring };
38
39// Roadmap:
40// - add thread pool
41// - add support for parsing the module flags
42// - more fancy transformations
43// - @import inlining of modules
44// - removing statements or blocks of code
45// - replacing operands of `and` and `or` with `true` and `false`
46// - replacing if conditions with `true` and `false`
47// - reduce flags sent to the compiler
48// - integrate with the build system?
49
50pub fn main(init: std.process.Init) !void {
51 const arena = init.arena.allocator();
52 const gpa = init.gpa;
53 const io = init.io;
54 const args = try init.minimal.args.toSlice(arena);
55
56 var opt_checker_path: ?[]const u8 = null;
57 var opt_root_source_file_path: ?[]const u8 = null;
58 var argv: []const []const u8 = &.{};
59 var seed: u32 = 0;
60 var skip_smoke_test = false;
61
62 {
63 var i: usize = 1;
64 while (i < args.len) : (i += 1) {
65 const arg = args[i];
66 if (mem.startsWith(u8, arg, "-")) {
67 if (mem.eql(u8, arg, "-h") or mem.eql(u8, arg, "--help")) {
68 try Io.File.stdout().writeStreamingAll(io, usage);
69 return std.process.cleanExit(io);
70 } else if (mem.eql(u8, arg, "--")) {
71 argv = args[i + 1 ..];
72 break;
73 } else if (mem.eql(u8, arg, "--skip-smoke-test")) {
74 skip_smoke_test = true;
75 } else if (mem.eql(u8, arg, "--main-mod-path")) {
76 @panic("TODO: implement --main-mod-path");
77 } else if (mem.eql(u8, arg, "--mod")) {
78 @panic("TODO: implement --mod");
79 } else if (mem.eql(u8, arg, "--deps")) {
80 @panic("TODO: implement --deps");
81 } else if (mem.eql(u8, arg, "--seed")) {
82 i += 1;
83 if (i >= args.len) fatal("expected 32-bit integer after {s}", .{arg});
84 const next_arg = args[i];
85 seed = std.fmt.parseUnsigned(u32, next_arg, 0) catch |err| {
86 fatal("unable to parse seed '{s}' as 32-bit integer: {t}", .{ next_arg, err });
87 };
88 } else {
89 fatal("unrecognized parameter: '{s}'", .{arg});
90 }
91 } else if (opt_checker_path == null) {
92 opt_checker_path = arg;
93 } else if (opt_root_source_file_path == null) {
94 opt_root_source_file_path = arg;
95 } else {
96 fatal("unexpected extra parameter: '{s}'", .{arg});
97 }
98 }
99 }
100
101 const checker_path = opt_checker_path orelse
102 fatal("missing interestingness checker argument; see -h for usage", .{});
103 const root_source_file_path = opt_root_source_file_path orelse
104 fatal("missing root source file path argument; see -h for usage", .{});
105
106 var interestingness_argv: std.ArrayList([]const u8) = .empty;
107 try interestingness_argv.ensureUnusedCapacity(arena, argv.len + 1);
108 interestingness_argv.appendAssumeCapacity(checker_path);
109 interestingness_argv.appendSliceAssumeCapacity(argv);
110
111 var rendered: std.Io.Writer.Allocating = .init(gpa);
112 defer rendered.deinit();
113
114 var astgen_input: std.Io.Writer.Allocating = .init(gpa);
115 defer astgen_input.deinit();
116
117 var tree = try parse(gpa, io, root_source_file_path);
118 defer {
119 gpa.free(tree.source);
120 tree.deinit(gpa);
121 }
122
123 if (!skip_smoke_test) {
124 std.debug.print("smoke testing the interestingness check...\n", .{});
125 switch (try runCheck(arena, io, interestingness_argv.items)) {
126 .interesting => {},
127 .boring, .unknown => |t| {
128 fatal("interestingness check returned {t} for unmodified input\n", .{t});
129 },
130 }
131 }
132
133 var fixups: Ast.Render.Fixups = .{};
134 defer fixups.deinit(gpa);
135
136 var more_fixups: Ast.Render.Fixups = .{};
137 defer more_fixups.deinit(gpa);
138
139 var rng = std.Random.DefaultPrng.init(seed);
140
141 // 1. Walk the AST of the source file looking for independent
142 // reductions and collecting them all into an array list.
143 // 2. Randomize the list of transformations. A future enhancement will add
144 // priority weights to the sorting but for now they are completely
145 // shuffled.
146 // 3. Apply a subset consisting of 1/2 of the transformations and check for
147 // interestingness.
148 // 4. If not interesting, half the subset size again and check again.
149 // 5. Repeat until the subset size is 1, then march the transformation
150 // index forward by 1 with each non-interesting attempt.
151 //
152 // At any point if a subset of transformations succeeds in producing an interesting
153 // result, restart the whole process, reparsing the AST and re-generating the list
154 // of all possible transformations and shuffling it again.
155
156 var transformations = std.array_list.Managed(Walk.Transformation).init(gpa);
157 defer transformations.deinit();
158 try Walk.findTransformations(arena, &tree, &transformations);
159 sortTransformations(transformations.items, rng.random());
160
161 fresh: while (transformations.items.len > 0) {
162 std.debug.print("found {d} possible transformations\n", .{
163 transformations.items.len,
164 });
165 var subset_size: usize = transformations.items.len;
166 var start_index: usize = 0;
167
168 while (start_index < transformations.items.len) {
169 const prev_subset_size = subset_size;
170 subset_size = @max(1, subset_size * 3 / 4);
171 if (prev_subset_size > 1 and subset_size == 1)
172 start_index = 0;
173
174 const this_set = transformations.items[start_index..][0..subset_size];
175 std.debug.print("trying {d} random transformations: ", .{subset_size});
176 for (this_set[0..@min(this_set.len, 20)]) |t| {
177 std.debug.print("{s} ", .{@tagName(t)});
178 }
179 std.debug.print("\n", .{});
180 try transformationsToFixups(gpa, arena, io, root_source_file_path, this_set, &fixups);
181
182 rendered.clearRetainingCapacity();
183 try tree.render(gpa, &rendered.writer, fixups);
184
185 // The transformations we applied may have resulted in unused locals,
186 // in which case we would like to add the respective discards.
187 {
188 try astgen_input.writer.writeAll(rendered.written());
189 try astgen_input.writer.writeByte(0);
190 const source_with_null = astgen_input.written()[0..(astgen_input.written().len - 1) :0];
191 var astgen_tree = try Ast.parse(gpa, source_with_null, .{});
192 defer astgen_tree.deinit(gpa);
193 if (astgen_tree.errors.len != 0) {
194 @panic("syntax errors occurred");
195 }
196 var zir = try AstGen.generate(gpa, astgen_tree);
197 defer zir.deinit(gpa);
198
199 if (zir.hasCompileErrors()) {
200 more_fixups.clearRetainingCapacity();
201 const payload_index = zir.extra[@backingInt(Zir.ExtraIndex.compile_errors)];
202 assert(payload_index != 0);
203 const header = zir.extraData(Zir.Inst.CompileErrors, payload_index);
204 var extra_index = header.end;
205 for (0..header.data.items_len) |_| {
206 const item = zir.extraData(Zir.Inst.CompileErrors.Item, extra_index);
207 extra_index = item.end;
208 const msg = zir.nullTerminatedString(item.data.msg);
209 if (mem.eql(u8, msg, "unused local constant") or
210 mem.eql(u8, msg, "unused local variable") or
211 mem.eql(u8, msg, "unused function parameter") or
212 mem.eql(u8, msg, "unused capture"))
213 {
214 const ident_token = item.data.token.unwrap().?;
215 try more_fixups.unused_var_decls.put(gpa, ident_token, {});
216 } else {
217 std.debug.print("found other ZIR error: '{s}'\n", .{msg});
218 }
219 }
220 if (more_fixups.count() != 0) {
221 rendered.clearRetainingCapacity();
222 try astgen_tree.render(gpa, &rendered.writer, more_fixups);
223 }
224 }
225 }
226
227 try Io.Dir.cwd().writeFile(io, .{ .sub_path = root_source_file_path, .data = rendered.written() });
228 // std.debug.print("trying this code:\n{s}\n", .{rendered.items});
229
230 const interestingness = try runCheck(arena, io, interestingness_argv.items);
231 std.debug.print("{d} random transformations: {t}. {d}/{d}\n", .{
232 subset_size, interestingness, start_index, transformations.items.len,
233 });
234 switch (interestingness) {
235 .interesting => {
236 const new_tree = try parse(gpa, io, root_source_file_path);
237 gpa.free(tree.source);
238 tree.deinit(gpa);
239 tree = new_tree;
240
241 try Walk.findTransformations(arena, &tree, &transformations);
242 sortTransformations(transformations.items, rng.random());
243
244 continue :fresh;
245 },
246 .unknown, .boring => {
247 // Continue to try the next set of transformations.
248 // If we tested only one transformation, move on to the next one.
249 if (subset_size == 1) {
250 start_index += 1;
251 } else {
252 start_index += subset_size;
253 if (start_index + subset_size > transformations.items.len) {
254 start_index = 0;
255 }
256 }
257 },
258 }
259 }
260 std.debug.print("all {d} remaining transformations are uninteresting\n", .{
261 transformations.items.len,
262 });
263
264 // Revert the source back to not be transformed.
265 fixups.clearRetainingCapacity();
266 rendered.clearRetainingCapacity();
267 try tree.render(gpa, &rendered.writer, fixups);
268 try Io.Dir.cwd().writeFile(io, .{ .sub_path = root_source_file_path, .data = rendered.written() });
269
270 return std.process.cleanExit(io);
271 }
272 std.debug.print("no more transformations found\n", .{});
273 return std.process.cleanExit(io);
274}
275
276fn sortTransformations(transformations: []Walk.Transformation, rng: std.Random) void {
277 rng.shuffle(Walk.Transformation, transformations);
278 // Stable sort based on priority to keep randomness as the secondary sort.
279 // TODO: introduce transformation priorities
280 // std.mem.sort(transformations);
281}
282
283fn termToInteresting(term: std.process.Child.Term) Interestingness {
284 return switch (term) {
285 .exited => |code| switch (code) {
286 0 => .interesting,
287 1 => .unknown,
288 else => .boring,
289 },
290 .signal => |sig| {
291 std.debug.print("interestingness check terminated with signal {t}\n", .{sig});
292 return .boring;
293 },
294 .stopped => |sig| {
295 std.debug.print("interestingness check stopped with signal {t}\n", .{sig});
296 return .boring;
297 },
298 .unknown => {
299 std.debug.print("interestingness check aborted unexpectedly\n", .{});
300 return .boring;
301 },
302 };
303}
304
305fn runCheck(arena: Allocator, io: Io, argv: []const []const u8) !Interestingness {
306 const result = try std.process.run(arena, io, .{ .argv = argv });
307 if (result.stderr.len != 0)
308 std.debug.print("{s}", .{result.stderr});
309 return termToInteresting(result.term);
310}
311
312fn transformationsToFixups(
313 gpa: Allocator,
314 arena: Allocator,
315 io: Io,
316 root_source_file_path: []const u8,
317 transforms: []const Walk.Transformation,
318 fixups: *Ast.Render.Fixups,
319) !void {
320 fixups.clearRetainingCapacity();
321
322 for (transforms) |t| switch (t) {
323 .gut_function => |fn_decl_node| {
324 try fixups.gut_functions.put(gpa, fn_decl_node, {});
325 },
326 .delete_node => |decl_node| {
327 try fixups.omit_nodes.put(gpa, decl_node, {});
328 },
329 .delete_var_decl => |delete_var_decl| {
330 try fixups.omit_nodes.put(gpa, delete_var_decl.var_decl_node, {});
331 for (delete_var_decl.references.items) |ident_node| {
332 try fixups.replace_nodes_with_string.put(gpa, ident_node, "undefined");
333 }
334 },
335 .replace_with_undef => |node| {
336 try fixups.replace_nodes_with_string.put(gpa, node, "undefined");
337 },
338 .replace_with_true => |node| {
339 try fixups.replace_nodes_with_string.put(gpa, node, "true");
340 },
341 .replace_with_false => |node| {
342 try fixups.replace_nodes_with_string.put(gpa, node, "false");
343 },
344 .replace_node => |r| {
345 try fixups.replace_nodes_with_node.put(gpa, r.to_replace, r.replacement);
346 },
347 .inline_imported_file => |inline_imported_file| {
348 const full_imported_path = try std.fs.path.join(gpa, &.{
349 std.fs.path.dirname(root_source_file_path) orelse ".",
350 inline_imported_file.imported_string,
351 });
352 defer gpa.free(full_imported_path);
353 var other_file_ast = try parse(gpa, io, full_imported_path);
354 defer {
355 gpa.free(other_file_ast.source);
356 other_file_ast.deinit(gpa);
357 }
358
359 var inlined_fixups: Ast.Render.Fixups = .{};
360 defer inlined_fixups.deinit(gpa);
361 if (std.fs.path.dirname(inline_imported_file.imported_string)) |dirname| {
362 inlined_fixups.rebase_imported_paths = dirname;
363 }
364 for (inline_imported_file.in_scope_names.keys()) |name| {
365 // This name needs to be mangled in order to not cause an
366 // ambiguous reference error.
367 var i: u32 = 2;
368 const mangled = while (true) : (i += 1) {
369 const mangled = try std.fmt.allocPrint(gpa, "{s}{d}", .{ name, i });
370 if (!inline_imported_file.in_scope_names.contains(mangled))
371 break mangled;
372 gpa.free(mangled);
373 };
374 try inlined_fixups.rename_identifiers.put(gpa, name, mangled);
375 }
376 defer {
377 for (inlined_fixups.rename_identifiers.values()) |v| {
378 gpa.free(v);
379 }
380 }
381
382 var other_source: std.Io.Writer.Allocating = .init(gpa);
383 defer other_source.deinit();
384 try other_source.writer.writeAll("struct {\n");
385 try other_file_ast.render(gpa, &other_source.writer, inlined_fixups);
386 try other_source.writer.writeAll("}");
387
388 try fixups.replace_nodes_with_string.put(
389 gpa,
390 inline_imported_file.builtin_call_node,
391 try arena.dupe(u8, other_source.written()),
392 );
393 },
394 };
395}
396
397fn parse(gpa: Allocator, io: Io, file_path: []const u8) !Ast {
398 const source_code = Io.Dir.cwd().readFileAllocOptions(
399 io,
400 file_path,
401 gpa,
402 .limited(std.math.maxInt(u32)),
403 .@"1",
404 0,
405 ) catch |err| {
406 fatal("unable to open '{s}': {s}", .{ file_path, @errorName(err) });
407 };
408 errdefer gpa.free(source_code);
409
410 var tree = try Ast.parse(gpa, source_code, .{});
411 errdefer tree.deinit(gpa);
412
413 if (tree.errors.len != 0) {
414 @panic("syntax errors occurred");
415 }
416
417 return tree;
418}
419
420fn fatal(comptime format: []const u8, args: anytype) noreturn {
421 std.log.err(format, args);
422 std.process.exit(1);
423}