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