reduce.zig (17382B) - Raw
1 const std = @import("std"); 2 const mem = std.mem; 3 const Allocator = std.mem.Allocator; 4 const assert = std.debug.assert; 5 const Ast = std.zig.Ast; 6 const Walk = @import("reduce/Walk.zig"); 7 const AstGen = std.zig.AstGen; 8 const Zir = std.zig.Zir; 9 10 const 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 36 const 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 49 pub 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().deprecatedWriter(); 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.ArrayListUnmanaged([]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 284 fn 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 291 fn 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 305 fn 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 315 fn 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 399 fn parse(gpa: Allocator, file_path: []const u8) !Ast { 400 const source_code = std.fs.cwd().readFileAllocOptions( 401 gpa, 402 file_path, 403 std.math.maxInt(u32), 404 null, 405 .fromByteUnits(1), 406 0, 407 ) catch |err| { 408 fatal("unable to open '{s}': {s}", .{ file_path, @errorName(err) }); 409 }; 410 errdefer gpa.free(source_code); 411 412 var tree = try Ast.parse(gpa, source_code, .zig); 413 errdefer tree.deinit(gpa); 414 415 if (tree.errors.len != 0) { 416 @panic("syntax errors occurred"); 417 } 418 419 return tree; 420 } 421 422 fn fatal(comptime format: []const u8, args: anytype) noreturn { 423 std.log.err(format, args); 424 std.process.exit(1); 425 }