# HG changeset patch # User Bryan O'Sullivan # Date 1167343575 28800 # Node ID 26b7a4e943aa22bb75491c5b69365cae603f74bf # Parent 73efa1a01a6c10b33979b3b5252b5bbbdd6ad8ea Describe the bisect extension. diff -r 73efa1a01a6c -r 26b7a4e943aa en/examples/bisect --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/en/examples/bisect Thu Dec 28 14:06:15 2006 -0800 @@ -0,0 +1,80 @@ +#!/bin/bash + +echo '[extensions]' >> $HGRC +echo 'hbisect =' >> $HGRC + +#$ name: init + +hg init mybug +cd mybug + +#$ name: commits + +buggy_change=37 + +for (( i = 0; i < 50; i++ )); do + if [[ $i = $buggy_change ]]; then + echo 'i have a gub' > myfile$i + hg commit -q -A -m 'buggy changeset' + else + echo 'nothing to see here, move along' > myfile$i + hg commit -q -A -m 'normal changeset' + fi +done + +#$ name: help + +hg help bisect +hg bisect help + +#$ name: search.init + +hg bisect init + +#$ name: search.bad-init + +hg bisect bad + +#$ name: search.good-init + +hg bisect good 10 + +#$ name: search.step1 + +if grep -q 'i have a gub' * +then + result=bad +else + result=good +fi + +echo this revision is $result +hg bisect $result + +#$ name: mytest + +mytest() { + if grep -q 'i have a gub' * + then + result=bad + else + result=good + fi + + echo this revision is $result + hg bisect $result +} + +#$ name: search.step2 + +mytest + +#$ name: search.rest + +mytest +mytest +mytest + +#$ name: search.reset + +hg bisect reset diff -r 73efa1a01a6c -r 26b7a4e943aa en/undo.tex --- a/en/undo.tex Thu Dec 28 09:56:47 2006 -0800 +++ b/en/undo.tex Thu Dec 28 14:06:15 2006 -0800 @@ -454,6 +454,296 @@ \texttt{examples} directory works, but doesn't handle merge changesets. Kind of an important omission. +\section{Finding the source of a bug} + +While it's all very well to be able to back out a changeset that +introduced a bug, this requires that you know which changeset to back +out. Mercurial provides an invaluable extension, called +\hgext{bisect}, that helps you to automate this process and accomplish +it very efficiently. + +The idea behind the \hgext{bisect} extension is that a changeset has +introduced some change of behaviour that you can identify with a +simple binary test. You don't know which piece of code introduced the +change, but you know how to test for the presence of the bug. The +\hgext{bisect} extension uses your test to direct its search for the +changeset that introduced the code that caused the bug. + +Here are a few scenarios to help you understand how you might apply this +extension. +\begin{itemize} +\item The most recent version of your software has a bug that you + remember wasn't present a few weeks ago, but you don't know when it + was introduced. Here, your binary test checks for the presence of + that bug. +\item You fixed a bug in a rush, and now it's time to close the entry + in your team's bug database. The bug database requires a changeset + ID when you close an entry, but you don't remember which changeset + you fixed the bug in. Once again, your binary test checks for the + presence of the bug. +\item Your software works correctly, but runs~15\% slower than the + last time you measured it. You want to know which changeset + introduced the performance regression. In this case, your binary + test measures the performance of your software, to see whether it's + ``fast'' or ``slow''. +\item The sizes of the components of your project that you ship + exploded recently, and you suspect that something changed in the way + you build your project. +\end{itemize} + +From these examples, it should be clear that the \hgext{bisect} +extension is not useful only for finding the sources of bugs. You can +use it to find any ``emergent property'' of a repository (anything +that you can't find from a simple text search of the files in the +tree) for which you can write a binary test. + +We'll introduce a little bit of terminology here, just to make it +clear which parts of the search process are your responsibility, and +which are Mercurial's. A \emph{test} is something that \emph{you} run +when \hgext{bisect} chooses a changeset. A \emph{probe} is what +\hgext{bisect} runs to tell whether a revision is good. Finally, +we'll use the word ``bisect'', as both a noun and a verb, to stand in +for the phrase ``search using the \hgext{bisect} extension''. + +One simple way to automate the searching process would be simply to +probe every changeset. However, this scales poorly. If it took ten +minutes to test a single changeset, and you had 10,000 changesets in +your repository, the exhaustive approach would take on average~35 +\emph{days} to find the changeset that introduced a bug. Even if you +knew that the bug was introduced by one of the last 500 changesets, +and limited your search to those, you'd still be looking at over 40 +hours to find the changeset that introduced your bug. + +What the \emph{bisect} extension does is use its knowledge of the +``shape'' of your project's revision history to perform a search in +time proportional to the \emph{logarithm} of the number of changesets +to check (the kind of search it performs is called a dichotomic +search). With this approach, searching through 10,000 changesets will +take less than two hours, even at ten minutes per test. Limit your +search to the last 500 changesets, and it will take less than an hour. + +The \hgext{bisect} extension is aware of the ``branchy'' nature of a +Mercurial project's revision history, so it has no problems dealing +with branches, merges, or multiple heads in a repoository. It can +prune entire branches of history with a single probe, which is how it +operates so efficiently. + +\subsection{Using the \hgext{bisect} extension} + +Here's an example of \hgext{bisect} in action. To keep the core of +Mercurial simple, \hgext{bisect} is packaged as an extension; this +means that it won't be present unless you explicitly enable it. To do +this, edit your \hgrc\ and add the following section header (if it's +not already present): +\begin{codesample2} + [extensions] +\end{codesample2} +Then add a line to this section to enable the extension: +\begin{codesample2} + hbisect = +\end{codesample2} +\begin{note} + That's right, there's a ``\texttt{h}'' at the front of the name of + the \hgext{bisect} extension. The reason is that Mercurial is + written in Python, and uses a standard Python package called + \texttt{bisect}. If you omit the ``\texttt{h}'' from the name + ``\texttt{hbisect}'', Mercurial will erroneously find the standard + Python \texttt{bisect} package, and try to use it as a Mercurial + extension. This won't work, and Mercurial will crash repeatedly + until you fix the spelling in your \hgrc. Ugh. +\end{note} + +Now let's create a repository, so that we can try out the +\hgext{bisect} extension in isolation. +\interaction{bisect.init} +We'll simulate a project that has a bug in it in a simple-minded way: +create trivial changes in a loop, and nominate one specific change +that will have the ``bug''. This loop creates 50 changesets, each +adding a single file to the repository. We'll represent our ``bug'' +with a file that contains the text ``i have a gub''. +\interaction{bisect.commits} + +The next thing that we'd like to do is figure out how to use the +\hgext{bisect} extension. We can use Mercurial's normal built-in help +mechanism for this. +\interaction{bisect.help} + +The \hgext{bisect} extension works in steps. Each step proceeds as follows. +\begin{enumerate} +\item You run your binary test. + \begin{itemize} + \item If the test succeeded, you tell \hgext{bisect} by running the + \hgcmdargs{bisect}{good} command. + \item If it failed, use the \hgcmdargs{bisect}{bad} command to let + the \hgext{bisect} extension know. + \end{itemize} +\item The extension uses your information to decide which changeset to + test next. +\item It updates the working directory to that changeset, and the + process begins again. +\end{enumerate} +The process ends when \hgext{bisect} identifies a unique changeset +that marks the point where your test transitioned from ``succeeding'' +to ``failing''. + +To start the search, we must run the \hgcmdargs{bisect}{init} command. +\interaction{bisect.search.init} + +In our case, the binary test we use is simple: we check to see if any +file in the repository contains the string ``i have a gub''. If it +does, this changeset contains the change that ``caused the bug''. By +convention, a changeset that has the property we're searching for is +``bad'', while one that doesn't is ``good''. + +Most of the time, the revision to which the working directory is +synced (usually the tip) already exhibits the problem introduced by +the buggy change, so we'll mark it as ``bad''. +\interaction{bisect.search.bad-init} + +Our next task is to nominate a changeset that we know \emph{doesn't} +have the bug; the \hgext{bisect} extension will ``bracket'' its search +between the first pair of good and bad changesets. In our case, we +know that revision~10 didn't have the bug. (I'll have more words +about choosing the first ``good'' changeset later.) +\interaction{bisect.search.good-init} + +Notice that this command printed some output. +\begin{itemize} +\item It told us how many changesets it must consider before it can + identify the one that introduced the bug, and how many tests that + will require. +\item It updated the working directory to the next changeset to test, + and told us which changeset it's testing. +\end{itemize} + +We now run our test in the working directory. We use the +\command{grep} command to see if our ``bad'' file is present in the +working directory. If it is, this revision is bad; if not, this +revision is good. +\interaction{search.step1} + +This test looks like a perfect candidate for automation, so let's turn +it into a shell function. +\interaction{search.mytest} +We can now run an entire test step with a single command, +\texttt{mytest}. +\interaction{search.step2} +A few more invocations of our canned test step command, and we're +done. +\interaction{search.rest} + +Even though we had~40 changesets to search through, the \hgext{bisect} +extension let us find the changeset that introduced our ``bug'' with +only five tests. Because the number of tests that the \hgext{bisect} +extension grows logarithmically with the number of changesets to +search, the advantage that it has over the ``brute force'' search +approach increases with every changeset you add. + +\subsection{Cleaning up after your search} + +When you're finished using the \hgext{bisect} extension in a +repository, you can use the \hgcmdargs{bisect}{reset} command to drop +the information it was using to drive your search. The extension +doesn't use much space, so it doesn't matter if you forget to run this +command. However, \hgext{bisect} won't let you start a new search in +that repository until you do a \hgcmdargs{bisect}{reset}. +\interaction{search.reset} + +\section{Tips for finding bugs effectively} + +\subsection{Give consistent input} + +The \hgext{bisect} extension requires that you correctly report the +result of every test you perform. If you tell it that a test failed +when it really succeeded, it \emph{might} be able to detect the +inconsistency. If it can identify an inconsistency in your reports, +it will tell you that a particular changeset is both good and bad. +However, it can't do this perfectly; it's about as likely to report +the wrong changeset as the source of the bug. + +\subsection{Automate as much as possible} + +When I started using the \hgext{bisect} extension, I tried a few times +to run my tests by hand, on the command line. This is an approach +that I, at least, am not suited to. After a few tries, I found that I +was making enough mistakes that I was having to restart my searches +several times before finally getting correct results. + +My initial problems with driving the \hgext{bisect} extension by hand +occurred even with simple searches on small repositories; if the +problem you're looking for is more subtle, or the number of tests that +\hgext{bisect} must perform increases, the likelihood of operator +error ruining the search is much higher. Once I started automating my +tests, I had much better results. + +The key to automated testing is twofold: +\begin{itemize} +\item always test for the same symptom, and +\item always feed consistent input to the \hgcmd{bisect} command. +\end{itemize} +In my tutorial example above, the \command{grep} command tests for the +symptom, and the \texttt{if} statement takes the result of this check +and ensures that we always feed the same input to the \hgcmd{bisect} +command. The \texttt{mytest} function marries these together in a +reproducible way, so that every test is uniform and consistent. + +\subsection{Check your results} + +Because the output of a \hgext{bisect} search is only as good as the +input you give it, don't take the changeset it reports as the +absolute truth. A simple way to cross-check its report is to manually +run your test at each of the following changesets: +\begin{itemize} +\item The changeset that it reports as the first bad revision. Your + test should still report this as bad. +\item The parent of that changeset (either parent, if it's a merge). + Your test should report this changeset as good. +\item A child of that changeset. Your test should report this + changeset as bad. +\end{itemize} + +\subsection{Beware interference between bugs} + +It's possible that your search for one bug could be disrupted by the +presence of another. For example, let's say your software crashes at +revision 100, and worked correctly at revision 50. Unknown to you, +someone else introduced a different crashing bug at revision 60, and +fixed it at revision 80. This could distort your results in one of +several ways. + +It is possible that this other bug completely ``masks'' yours, which +is to say that it occurs before your bug has a chance to manifest +itself. If you can't avoid that other bug (for example, it prevents +your project from building), and so can't tell whether your bug is +present in a particular changeset, the \hgext{bisect} extension cannot +help you directly. Instead, you'll need to manually avoid the +changesets where that bug is present, and do separate searches +``around'' it. + +A different problem could arise if your test for a bug's presence is +not specific enough. If you checks for ``my program crashes'', then +both your crashing bug and an unrelated crashing bug that masks it +will look like the same thing, and mislead \hgext{bisect}. + +\subsection{Bracket your search lazily} + +Choosing the first ``good'' and ``bad'' changesets that will mark the +end points of your search is often easy, but it bears a little +discussion neverthheless. From the perspective of \hgext{bisect}, the +``newest'' changeset is conventionally ``bad'', and the older +changeset is ``good''. + +If you're having trouble remembering when a suitable ``good'' change +was, so that you can tell \hgext{bisect}, you could do worse than +testing changesets at random. Just remember to eliminate contenders +that can't possibly exhibit the bug (perhaps because the feature with +the bug isn't present yet) and those where another problem masks the +bug (as I discussed above). + +Even if you end up ``early'' by thousands of changesets or months of +history, you will only add a handful of tests to the total number that +\hgext{bisect} must perform, thanks to its logarithmic behaviour. + %%% Local Variables: %%% mode: latex %%% TeX-master: "00book"