1 module bisect; 2 3 import core.thread; 4 5 import std.algorithm; 6 import std.exception; 7 import std.file; 8 import std.getopt : getopt; 9 import std.path; 10 import std.process; 11 import std.range; 12 import std.string; 13 14 import ae.sys.file; 15 import ae.sys.git; 16 import ae.utils.math; 17 import ae.utils.sini; 18 19 import common; 20 import config; 21 import custom; 22 import repo; 23 24 enum EXIT_UNTESTABLE = 125; 25 26 string bisectConfigFile; 27 struct BisectConfig 28 { 29 string bad, good; 30 bool reverse; 31 string tester; 32 bool bisectBuild; 33 bool bisectBuildTest; 34 string extraSpec; 35 36 DiggerManager.Config.Build* build; 37 DiggerManager.Config.Local* local; 38 39 string[string] environment; 40 } 41 BisectConfig bisectConfig; 42 43 /// Final build directory for bisect tests. 44 alias currentDir = subDir!"current"; 45 46 int doBisect(bool noVerify, string bisectConfigFile, string[] bisectConfigLines) 47 { 48 bisectConfig.build = &d.config.build; 49 bisectConfig.local = &d.config.local; 50 if (bisectConfigFile) 51 { 52 log("Loading bisect configuration from " ~ bisectConfigFile); 53 bisectConfigFile 54 .readText() 55 .splitLines() 56 .parseIniInto(bisectConfig); 57 } 58 else 59 log("No bisect.ini file specified! Using options from command-line only."); 60 bisectConfigLines.parseIniInto(bisectConfig); 61 62 void ensureDefault(ref string var, string which, string def) 63 { 64 if (!var) 65 { 66 log("No %s revision specified, assuming '%s'".format(which, def)); 67 var = def; 68 } 69 } 70 ensureDefault(bisectConfig.bad , "bad" , "master"); 71 ensureDefault(bisectConfig.good, "good", "@ 1 month ago"); 72 73 if (bisectConfig.bisectBuildTest) 74 { 75 bisectConfig.bisectBuild = true; 76 d.config.local.cache = "none"; 77 } 78 if (bisectConfig.bisectBuild) 79 enforce(!bisectConfig.tester, "bisectBuild and specifying a test command are mutually exclusive"); 80 enforce(bisectConfig.tester || bisectConfig.bisectBuild, "No tester specified (and bisectBuild is false)"); 81 82 auto repo = &d.getMetaRepo().git(); 83 84 d.needUpdate(); 85 86 void test(bool good, string rev) 87 { 88 auto name = good ? "GOOD" : "BAD"; 89 log("Sanity-check, testing %s revision %s...".format(name, rev)); 90 auto result = doBisectStep(rev); 91 enforce(result != EXIT_UNTESTABLE, 92 "%s revision %s is not testable" 93 .format(name, rev)); 94 enforce(!result == good, 95 "%s revision %s is not correct (exit status is %d)" 96 .format(name, rev, result)); 97 } 98 99 if (!noVerify) 100 { 101 auto good = getRev!true(); 102 auto bad = getRev!false(); 103 104 enforce(good != bad, "Good and bad revisions are both " ~ bad); 105 106 auto commonAncestor = repo.query("merge-base", good, bad); 107 if (bisectConfig.reverse) 108 { 109 enforce(good != commonAncestor, "Bad commit is newer than good commit (and reverse search is enabled)"); 110 test(false, bad); 111 test(true, good); 112 } 113 else 114 { 115 enforce(bad != commonAncestor, "Good commit is newer than bad commit"); 116 test(true, good); 117 test(false, bad); 118 } 119 } 120 121 auto p0 = getRev!true(); // good 122 auto p1 = getRev!false(); // bad 123 if (bisectConfig.reverse) 124 swap(p0, p1); 125 126 bool[string] cacheState, untestable; 127 if (!bisectConfig.extraSpec) 128 cacheState = d.getCacheState([p0, p1]); 129 130 bisectLoop: 131 while (true) 132 { 133 log("Finding shortest path between %s and %s...".format(p0, p1)); 134 auto fullPath = repo.pathBetween(p0, p1); // closed interval 135 enforce(fullPath.length >= 2 && fullPath[0].commit == p0 && fullPath[$-1].commit == p1, 136 "Bad path calculation result"); 137 auto path = fullPath[1..$-1].map!(step => step.commit).array; // open interval 138 log("%d commits (about %d tests) remaining.".format(path.length, ilog2(path.length+1))); 139 140 if (!path.length) 141 { 142 assert(fullPath.length == 2); 143 auto p = fullPath[1].downwards ? p0 : p1; 144 log("%s is the first %s commit".format(p, bisectConfig.reverse ? "good" : "bad")); 145 repo.run("--no-pager", "show", p); 146 log("Bisection completed successfully."); 147 return 0; 148 } 149 150 log("(%d total, %d cached, %d untestable)".format( 151 path.length, 152 path.filter!(commit => cacheState.get(commit, false)).walkLength, 153 path.filter!(commit => commit in untestable).walkLength, 154 )); 155 156 // First try all cached commits in the range (middle-most first). 157 // Afterwards, do a binary-log search across the commit range for a testable commit. 158 auto order = chain( 159 path.radial .filter!(commit => cacheState.get(commit, false)), 160 path.binaryOrder.filter!(commit => !cacheState.get(commit, false)) 161 ).filter!(commit => commit !in untestable).array; 162 163 foreach (i, p; order) 164 { 165 auto result = doBisectStep(p); 166 if (result == EXIT_UNTESTABLE) 167 { 168 log("Commit %s (%d/%d) is untestable.".format(p, i+1, order.length)); 169 untestable[p] = true; 170 continue; 171 } 172 173 if (bisectConfig.reverse) 174 result = result ? 0 : 1; 175 176 if (result == 0) // good 177 p0 = p; 178 else 179 p1 = p; 180 181 continue bisectLoop; 182 } 183 184 log("There are only untestable commits left to bisect."); 185 log("The first %s commit could be any of:".format(bisectConfig.reverse ? "good" : "bad")); 186 foreach (p; path ~ [p1]) 187 repo.run("log", "-1", "--pretty=format:%h %ci: %s", p); 188 log("We cannot bisect more!"); 189 return 2; 190 } 191 192 assert(false); 193 } 194 195 struct BisectStep 196 { 197 string commit; 198 bool downwards; // on the way to the common ancestor 199 } 200 201 BisectStep[] pathBetween(in Repository* repo, string p0, string p1) 202 { 203 auto commonAncestor = repo.query("merge-base", p0, p1); 204 return chain( 205 repo.commitsBetween(commonAncestor, p0).retro.map!(commit => BisectStep(commit, true )), 206 commonAncestor.only .map!(commit => BisectStep(commit, true )), 207 repo.commitsBetween(commonAncestor, p1) .map!(commit => BisectStep(commit, false)), 208 ).array; 209 } 210 211 string[] commitsBetween(in Repository* repo, string p0, string p1) 212 { 213 return repo.query("log", "--reverse", "--pretty=format:%H", p0 ~ ".." ~ p1).splitLines(); 214 } 215 216 /// Reorders [1, 2, ..., 98, 99] 217 /// into [50, 25, 75, 13, 38, 63, 88, ...] 218 T[] binaryOrder(T)(T[] items) 219 { 220 auto n = items.length; 221 assert(n); 222 auto seen = new bool[n]; 223 auto result = new T[n]; 224 size_t c = 0; 225 226 foreach (p; 0..30) 227 foreach (i; 0..1<<p) 228 { 229 auto x = cast(size_t)(n/(2<<p) + ulong(n+1)*i/(1<<p)); 230 if (x >= n || seen[x]) 231 continue; 232 seen[x] = true; 233 result[c++] = items[x]; 234 if (c == n) 235 return result; 236 } 237 assert(false); 238 } 239 240 unittest 241 { 242 assert(iota(1, 7+1).array.binaryOrder.equal([4, 2, 6, 1, 3, 5, 7])); 243 assert(iota(1, 100).array.binaryOrder.startsWith([50, 25, 75, 13, 38, 63, 88])); 244 } 245 246 int doBisectStep(string rev) 247 { 248 log("Testing revision: " ~ rev); 249 250 try 251 { 252 if (currentDir.exists) 253 { 254 version (Windows) 255 { 256 try 257 currentDir.rmdirRecurse(); 258 catch (Exception e) 259 { 260 log("Failed to clean up %s: %s".format(currentDir, e.msg)); 261 Thread.sleep(500.msecs); 262 log("Retrying..."); 263 currentDir.rmdirRecurse(); 264 } 265 } 266 else 267 currentDir.rmdirRecurse(); 268 } 269 270 auto state = parseSpec(rev ~ bisectConfig.extraSpec); 271 272 scope (exit) 273 if (d.buildDir.exists) 274 rename(d.buildDir, currentDir); 275 276 d.build(state); 277 } 278 catch (Exception e) 279 { 280 log("Build failed: " ~ e.toString()); 281 if (bisectConfig.bisectBuild && !bisectConfig.bisectBuildTest) 282 return 1; 283 return EXIT_UNTESTABLE; 284 } 285 286 if (bisectConfig.bisectBuild) 287 { 288 log("Build successful."); 289 290 if (bisectConfig.bisectBuildTest) 291 { 292 try 293 d.test(); 294 catch (Exception e) 295 { 296 log("Tests failed: " ~ e.toString()); 297 return 1; 298 } 299 log("Tests successful."); 300 } 301 302 return 0; 303 } 304 305 string[string] env = d.getBaseEnvironment(); 306 d.applyEnv(env, bisectConfig.environment); 307 308 auto oldPath = environment["PATH"]; 309 scope(exit) environment["PATH"] = oldPath; 310 311 // Add the final DMD to the environment PATH 312 env["PATH"] = buildPath(currentDir, "bin").absolutePath() ~ pathSeparator ~ env["PATH"]; 313 environment["PATH"] = env["PATH"]; 314 315 // Use host HOME for the test command 316 env["HOME"] = environment.get("HOME"); 317 318 // For bisecting bootstrapping issues - allows passing the revision to another Digger instance 319 env["DIGGER_REVISION"] = rev; 320 321 d.logProgress("Running test command..."); 322 auto result = spawnShell(bisectConfig.tester, env, Config.newEnv).wait(); 323 d.logProgress("Test command exited with status %s (%s).".format(result, result==0 ? "GOOD" : result==EXIT_UNTESTABLE ? "UNTESTABLE" : "BAD")); 324 return result; 325 } 326 327 /// Returns SHA-1 of the initial search points. 328 string getRev(bool good)() 329 { 330 static string result; 331 if (!result) 332 { 333 auto rev = good ? bisectConfig.good : bisectConfig.bad; 334 result = parseRev(rev); 335 log("Resolved %s revision `%s` to %s.".format(good ? "GOOD" : "BAD", rev, result)); 336 } 337 return result; 338 } 339 340 struct CommitRange 341 { 342 uint startTime; /// first bad commit 343 uint endTime; /// first good commit 344 } 345 /// Known unbuildable time ranges 346 const CommitRange[] badCommits = 347 [ 348 { 1342243766, 1342259226 }, // Messed up DMD make files 349 { 1317625155, 1319346272 }, // Missing std.stdio import in std.regex 350 ]; 351 352 /// Find the earliest revision that Digger can build. 353 /// Used during development to extend Digger's range. 354 int doDelve(bool inBisect) 355 { 356 if (inBisect) 357 { 358 log("Invoked by git-bisect - performing bisect step."); 359 360 import std.conv; 361 auto rev = d.getMetaRepo().getRef("BISECT_HEAD"); 362 auto t = d.getMetaRepo().git.query("log", "-n1", "--pretty=format:%ct", rev).to!int(); 363 foreach (r; badCommits) 364 if (r.startTime <= t && t < r.endTime) 365 { 366 log("This revision is known to be unbuildable, skipping."); 367 return EXIT_UNTESTABLE; 368 } 369 370 d.cacheFailures = false; 371 //d.config.build = bisectConfig.build; // TODO 372 auto state = parseSpec(rev ~ bisectConfig.extraSpec); 373 try 374 { 375 d.build(state); 376 return 1; 377 } 378 catch (Exception e) 379 { 380 log("Build failed: " ~ e.toString()); 381 return 0; 382 } 383 } 384 else 385 { 386 auto root = d.getMetaRepo().git.query("log", "--pretty=format:%H", "--reverse", "master").splitLines()[0]; 387 d.getMetaRepo().git.run(["bisect", "start", "--no-checkout", "master", root]); 388 d.getMetaRepo().git.run("bisect", "run", 389 thisExePath, 390 "--dir", getcwd(), 391 "--config-file", opts.configFile, 392 "delve", "--in-bisect", 393 ); 394 return 0; 395 } 396 }