Testing and debugging · Lesson 70 of 77 · practice
Debugging by bisection
About 50 minutes.
By the end of this lesson you can
- Turn 'it does not work' into a case that fails the same way every time.
- Halve the search space instead of reading the whole program.
- Use a printed value to test one hypothesis rather than to look around.
- Shrink a failing input until nothing left in it is irrelevant.
Nothing starts until it fails on demand
Explanation
The first move is never to look for the bug. It is to make the bug happen whenever you want. A fault you can only trigger sometimes cannot be investigated, because every experiment has two possible explanations, and it cannot be declared fixed either - all you will ever know is that it has not happened lately.
So begin by finding the smallest input that fails, and put it in a test. That test is now three things at once: proof the bug is real, the experiment you will run after every change, and the thing that stops the bug coming back in six months. This is the moment the previous lessons pay off - a failing test IS a reproduction, written in a form that never gets forgotten.
If you cannot reproduce it, that is information too, and it points somewhere specific: something outside the function is varying. The clock, a random value, the order the tests ran in, data left behind by something else. Every one of those has a name from the last lesson, and the fix is to bring it under control rather than to keep re-running and hoping.
Halving turns a thousand suspects into ten questions
An analogy
Think of the old guessing game. Someone picks a number between 1 and 1000 and answers only 'higher' or 'lower'. Guessing 1, 2, 3 could take you a thousand turns. Guessing the middle each time takes ten, because each answer throws away half of everything that is left.
Debugging works the same way, and the reason it feels harder is that people forget they are allowed to ask a question in the middle. Instead of reading a program from the top hoping to spot the mistake, pick a point halfway through, print the value that is passing through it, and ask one question: is the data still correct here? If yes, the bug is downstream and the whole first half is innocent. If no, it is upstream and the second half is irrelevant. Either way, one look eliminated half the program.
The arithmetic is worth internalising because it is what makes the technique feel like magic on a big codebase. Ten checks cover a thousand lines. Twenty cover a million. And the same halving works over anything ordered: the steps of a pipeline, the rows of an input file, or the history of a project - which is precisely what 'git bisect' does with commits, asking you to say 'good' or 'bad' about a handful of versions instead of reading every change since the last release.
Print to answer a question, not to have a look around
Explanation
Sprinkling twenty prints through a file and reading the flood is not debugging; it is hoping. The version that works is: say out loud what you believe - 'by this line, words must be an array of three names' - then print exactly that one value, and see whether reality agrees.
The reason this is so much faster is that a specific prediction can be wrong in a specific way. If you expected three names and got four, with an empty one in the middle, you have not merely spotted an oddity - you have learned that the splitting step is where truth and expectation part company, and the whole loop below it is exonerated in the same instant.
Change one thing at a time, for the same reason. Two changes at once and a fixed bug tells you nothing about which change fixed it, so you keep both, including the one that did nothing except add a new problem next month. Change one thing, re-run the failing test, and write down what you learned before touching anything else.
Then shrink the input until every part of it matters
Explanation
When the failing input is a 500-row file, the same halving applies to the data. Run the first half. Still broken? The culprit is in there; halve again. Not broken? It is in the other half. Nine or ten rounds and you are holding the single row that causes it.
The final step is to remove everything that turns out not to matter, one piece at a time, checking after each removal that the failure is still there. What you are left with is a minimal reproduction: an input where every remaining part is load-bearing. This is exactly what a good bug report contains, and it is why a report saying 'this three-line input fails' gets fixed while 'the import is broken' does not.
Do not skip the confirmation step at the end. Undo your fix and check that the failure comes back, then redo it. Otherwise you may have fixed nothing and merely disturbed the conditions - and 'it works now' with no explanation is a bug that has gone quiet, not a bug that has gone.
What to hold on to
Recap
Reproduce it first and put the reproduction in a test. Then halve: pick the middle of the pipeline, the middle of the data, or the middle of the history, and ask one yes-or-no question that eliminates half the suspects. Print to test a prediction, not to browse. Change one thing at a time. Shrink the input until every part of it is needed. And prove the fix by watching the failure return when you undo it.
Worked examples
Every output below was produced by actually running the code in the same sandbox your exercises run in — it is not a prediction.
One printed value convicts the right line
initials works on one name and produces nonsense on another. Rather than reading the loop, the third line asks a single question about the value in the middle of the pipeline - and the answer names the culprit immediately.
1function normalise(name) {2 return name.trim().toLowerCase();3}4 5function initials(fullName) {6 const words = normalise(fullName).split(" ");7 let letters = "";8 for (const word of words) {9 letters = letters + word[0];10 }11 return letters.toUpperCase();12}13 14console.log(initials("Ada Lovelace"));15console.log(initials(" Grace Hopper "));16console.log(normalise(" Grace Hopper "));17console.log(normalise(" Grace Hopper ").split(" "));- line 14
AL. The happy path works, which is why nobody noticed - and why a test built only on this input proves nothing.
- line 15
GUNDEFINEDH. Not a crash, just nonsense: word[0] on an empty string is undefined, and adding undefined to a string quietly writes the word 'undefined' into your data.
- line 16
The midpoint question, part one. trim removed the outer spaces but the DOUBLE space between the names survived - so normalise is behaving exactly as documented.
- line 17
Part two, the verdict: ["grace","","hopper"]. A single space between two spaces splits into an empty string, so words has three entries and the middle one has no first letter. The loop is innocent; the fix belongs at the split - found in two lines, without re-reading anything.
What it prints
ALGUNDEFINEDHgrace hopper["grace","","hopper"]
Finding the one bad row in three questions
Eight rows, one of them malformed, and a parser that throws on it. Instead of eyeballing the file, the search runs the parser on halves and lets the failures point the way. Count the checks it used.
1function parseRow(row) {2 const parts = row.split(":");3 return { key: parts[0], value: parts[1].trim() };4}5 6function parsesCleanly(rows) {7 try {8 rows.map(parseRow);9 return true;10 } catch (error) {11 return false;12 }13}14 15function firstBadIndex(rows) {16 let low = 0;17 let high = rows.length;18 let checks = 0;19 while (high - low > 1) {20 const middle = Math.floor((low + high) / 2);21 checks = checks + 1;22 if (parsesCleanly(rows.slice(low, middle))) {23 low = middle;24 } else {25 high = middle;26 }27 }28 console.log("checks used:", checks);29 return low;30}31 32const rows = ["a: 1", "b: 2", "c: 3", "d: 4", "e", "f: 6", "g: 7", "h: 8"];33 34console.log(parsesCleanly(rows));35const bad = firstBadIndex(rows);36console.log(bad);37console.log(rows[bad]);- line 6
The whole search rests on being able to ask one yes-or-no question about any slice of the data. Turning a crash into true-or-false is what makes the halving possible.
- line 20
The midpoint. Everything below is either kept or discarded by a single answer - this is the guessing game, applied to rows.
- line 22
If the first half is clean the culprit is in the second half, so the floor moves up. Otherwise the ceiling comes down. One check, half the rows gone.
- line 34
false - the file is broken, which is where every debugging session starts: a reproduction that fails on demand.
- line 36
Three checks over eight rows, and index 4 is the answer: the row 'e' with no colon, so parts[1] is undefined and .trim() throws. With 1000 rows the same loop would have asked ten questions.
What it prints
falsechecks used: 34e
Check yourself
Not scored, not stored. Getting one wrong is the useful part.
Eight possible indexes, and everything from index 6 onwards is broken. Predict the index the loop settles on, and how many times it asked.
let calls = 0;function isBroken(index) { calls = calls + 1; return index >= 6;}let low = 0;let high = 8;while (low < high) { const middle = Math.floor((low + high) / 2); if (isBroken(middle)) { high = middle; } else { low = middle + 1; }}console.log(low);console.log(calls);
A user reports that the report page sometimes shows the wrong total. What is the first thing to do?
You change two things and the failing test now passes. Why is that a worse position than changing one?
Write it yourself
Exercise · core · 8 tests
Ten questions instead of a thousand
Write findFirstBroken(count, isBroken). The indexes run from 0 up to count - 1, and isBroken(index) answers true or false. You may rely on the answers being ordered: once an index is broken, every later index is broken too - which is exactly the shape of a bug introduced by one commit or one bad row. Return the smallest broken index, or -1 when nothing is broken. The starter already returns the right answer; it just asks about every index in turn, and one of the tests measures how many questions you needed.
findFirstBroken returns the lowest index for which isBroken is true, or -1 if isBroken is false for every index below count. It works when count is 0, when index 0 is already broken, and when nothing is broken. It never calls isBroken with an index of count or higher, and for 1024 indexes it must use no more than about a dozen calls.
Define findFirstBroken at the top level of your code — the tests call it by name.
Exercise · stretch · 7 tests
Cut the reproduction down to what matters
You have an input that fails and no idea which part of it is to blame. Write shrink(items, stillFails), where stillFails(list) returns true when a list still shows the failure. Try removing each item in turn: if the shorter list still fails, keep the shorter one and carry on; if it stops failing, that item was needed, so put it back and move to the next. Return the smallest list you reach, and do not modify the array you were handed. The starter returns the input untouched - a bug report as long as the original file.
shrink returns a list that still satisfies stillFails, with every item removed that could be removed one at a time, keeping the original relative order. Removing the first possible item first is the required order, so [1,2,3] under 'length is at least 2' gives [2,3]. The array passed in is never changed, and an empty input comes back empty.
Define shrink at the top level of your code — the tests call it by name.
Worth remembering
- What is the first step when investigating a bug?
Make it fail on demand and write that as a test. Without a reliable reproduction you cannot tell a fix from a coincidence.
- How many checks does halving need for 1000 possibilities?
About ten, because each answer discards half of what is left. A one-at-a-time scan needs up to a thousand.
- Why change only one thing at a time while debugging?
Two changes and a passing test tells you nothing about which one mattered, so you keep an unexplained edit forever.
- What is a minimal reproduction?
A failing input with everything unnecessary removed, so every part that remains is load-bearing. It is what a good bug report contains.
Check this lesson against the source
We wrote the explanation; we did not invent the facts. This is the page that backs them.
MDN — String.prototype.split()
Check there: Splitting on a separator that appears at the start, at the end, or twice in a row produces empty strings in the returned array - the array's length is not the number of words.
Check there: slice returns a new array containing a shallow copy of the selected portion and does not change the array it was called on.
Check there: Math.floor rounds down to the nearest integer, which keeps a midpoint index whole.
Prefer to read the source in a structured breakdown? Turn this doc into a breakdown