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