\documentclass[11pt]{article} \usepackage{colortbl} \usepackage[screen,panelright]{pdfscreen} \margins{0.5in}{0.5in}{0.5in}{0.5in} \screensize{6.25in}{8.25in} \urlid{heather.cs.ucdavis.edu/~matloff/debug.html} \usepackage{url} \begin{document} \begin{slide} \begin{centering} \textbf{ The Student's Guide to the Secret Art of Debugging } \bigskip Professor Norm Matloff \\ UC Davis \bigskip September 25, 2001 \bigskip \copyright{2001} \end{centering} \end{slide} \begin{slide} Why should you use a debugging tool in {\bf ALL} of your programming courses? \begin{itemize} \item [(a)] To please your professors. \item [(b)] To answer questions on debugging tools on final exams. \item [(c)] Because professional programmers make heavy usage of debugging tools. \item [(d)] To save {\bf yourself} time and frustration. \end{itemize} Answer: Choice (c) is true but the best answer is (d)! \end{slide} \begin{slide} We will use the Data Display Debugger (DDD) debugging tool. \begin{itemize} \item ``You see one, you've seen 'em all'': Other good debuggers have similar features. \item DDD is a GUI to the gdb debugger. \item DDD usable on C, C++, Java (DDD version 3.3 onward), perl, etc. \end{itemize} \end{slide} \begin{slide} \textbf{Fundamental Principle of Debugging: Confirmation} \bigskip \textcolor{red}{Finding your bug is a process of confirming the many things that you believe are true --- until you find one which is \underline{not} true.} \bigskip Examples of things to confirm: \begin{itemize} \item Your \underline{belief} that a variable X = 12 at a certain time. \item Your \underline{belief} that in a certain if-then-else statement, the ``else'' gets executed. \item Your \underline{belief} that in the function call F(Y,5), the parameters Y and 5 are received correctly. \end{itemize} \end{slide} \begin{slide} So, \underline{how} do you confirm such things? \textcolor{red}{Use a debugging tool!} \bigskip Use (for example) DDD to check each belief, until you find one that is false. \bigskip \textcolor{red}{Don't use printf() or cout statements}, as they \begin{itemize} \item make you lose precious time/concentration \item make you do lots of time-consuming editing and recompiling to add/remove them \item are less informative \end{itemize} \end{slide} \begin{slide} Our running example: An insert sort. \bigskip NumInputs numbers to be placed in array Y, ascending order. \bigskip Pseudocode: \begin{verbatim} set Y array to empty get NumInputs numbers from command line for I = 1 to NumInputs get new element NewY find first Y[J] for which NewY < Y[J] shift Y[J], Y[J+1], ... to right, to make room for NewY set Y[J] = NewY \end{verbatim} \bigskip Call tree: \begin{verbatim} main() -> GetArgs() -> ProcessData() -> Insert() -> ScootOver() -> PrintResults() \end{verbatim} \end{slide} \begin{slide} \includegraphics[width=6.0in]{Fig0.jpg} \end{slide} \begin{slide} Let's try compiling (note -g option) and running the program: \bigskip \begin{verbatim} % gcc -o ins -g Ins.c % ins 12 5 9 3 2 25 8 19 200 10 (no output, no return to OS prompt) \end{verbatim} % \textcolor{red}{Symptom:} Program just hangs! \bigskip OK, let's apply DDD: \bigskip \begin{verbatim} % ddd ins \end{verbatim} Or: \begin{verbatim} % ddd --separate ins \end{verbatim} \end{slide} \begin{slide} \includegraphics[width=6.0in]{Fig1.jpg} \end{slide} \begin{slide} DDD displays: \begin{itemize} \item The Source File window, displaying Ins.c. \item The Command Tool window, including buttons such as: \begin{itemize} \item Run: Run the program. \item Step: Execute the current source line, entering called function if any. \item Next: Same as Step, but do not enter the called function. \item Cont: Continue execution, not single-stepping. \item Finish: Execute until we finish the current function. \end{itemize} \item The Debugger Console window, showing: \begin{itemize} \item GDB commands. \item Keyboard input and screen output. \end{itemize} \end{itemize} The windows will be separate if the --separate option was used when you started DDD. \end{slide} \begin{slide} Well, where should we start? \bigskip No magic formula, but a loose guide is: \bigskip {\bf The Binary Search Principle:} \bigskip \textcolor{red}{First try to confirm that everything is OK at the ``approximate'' halfway point in the program. If so, then check at the approximate 3/4-way point; if not, check at the 1/4-way point. Each time, narrow down the big's location to one half of the previous portion.} \bigskip This of course is not a hard-and-fast, exact rule; it is just a way to suggest where to get started in applying DDD in searching for our bug. \end{slide} \begin{slide} Where is our ``approximate halfway point'' here in Ins.c? A look at main(), \bigskip \begin{verbatim} GetArgs(Argc,Argv); ProcessData(); PrintResults(); \end{verbatim} suggests we take as our first confirmation point the beginning of ProcessData(). \bigskip So, we will set a {\it breakpoint} --- a place where DDD will make execution of the program pause --- at the call to ProcessData(): \end{slide} \begin{slide} \begin{itemize} \item Move the mouse cursor to the line where ProcessData() is called. \item Click on the left end of the line. \item Click on Break (stop-sign icon). \end{itemize} \bigskip A red stop sign will then appear on the line, showing that DDD will stop there: \end{slide} \begin{slide} \includegraphics[width=6.0in]{Fig2.jpg} \end{slide} \begin{slide} Now, let's run the program via DDD: \begin{itemize} \item Click on Program, then on Run to get the Run Program window. \item Fill in the command line arguments (12, 5, ...) in that window. \item Click on Run in that window. \end{itemize} \end{slide} \begin{slide} \includegraphics[width=6.0in]{Fig2a.jpg} \end{slide} \begin{slide} DDD runs our program, stopping at the breakpoint. The green arrow shows our current line, i.e. the one about to be executed: \end{slide} \begin{slide} \includegraphics[width=6.0in]{Fig3.jpg} \end{slide} \begin{slide} Now, \textcolor{red}{let's confirm that the program is running correctly so far.} All it's done is set NumInputs and the array X, so let's check them: \bigskip So, let's verify that NumInputs = 10, and that X has the correct values (12, 5, ...): \bigskip \begin{itemize} \item Move the mouse cursor to any place where NumInputs appears in the Source Code window. Rest there for a half second or so. \item The value of NumInputs will appear in a yellow box near the mouse cursor (the cursor doesn't appear here), and at the edge below the Debugger Console. \item Do the same for X. \end{itemize} \end{slide} \begin{slide} \includegraphics[width=6.0in]{Fig4.jpg} \end{slide} \begin{slide} \includegraphics[width=6.0in]{Fig5.jpg} \end{slide} \begin{slide} OK, both NumInputs and X are all right. \bigskip But if there had been a bug within GetArgs(), say \begin{verbatim} X[I] = atoi(AV[I]); \end{verbatim} we would have found it here, by checking the values of the AV strings, etc. \bigskip By the way, if we had just wanted to check the value of X[I] here, not all of X (what if X had had 10,000 elements instead of just 10?), we could have used the mouse to highlight the whole expression ``X[I]'', then right-clicked on it and selected ``Print X[I]''. The value would be printed to the Debugger Console. \bigskip Or we could select ``Display X[I]'', which would create a subwindow in which X[I] would be continuously displayed. \end{slide} \begin{slide} Let's browse some more, say in Insert(). \bigskip \begin{itemize} \item Place a breakpoint in the definition of Insert(). \item Hit Cont to continue to the next breakpoint, which will be the one we just placed in Insert(). \item Once we get into Insert(), the green arrow points to the line \begin{verbatim} if (NumY = 0) { // Y empty so far, easy case \end{verbatim} \end{itemize} \end{slide} \begin{slide} \includegraphics[width=6.0in]{Fig6.jpg} \end{slide} \begin{slide} \begin{itemize} \item This is the first time we've hit Insert(), so NumY should be 0. \textcolor{red}{But we need to confirm it}, by moving the mouse cursor to NumY. Yep, it's 0. \item Hitting Step (or Next) that ``should'' take us to the line \begin{verbatim} Y[0] = NewY; \end{verbatim} but once again, \textcolor{red}{we must confirm it}. Here's what we get: \end{itemize} \end{slide} \begin{slide} \includegraphics[width=6.0in]{Fig7.jpg} \end{slide} \begin{slide} Oh, no! It skipped right over the {\bf if}, going straight to the {\bf for} loop! \bigskip So (NumY = 0) must have been false. But we confirmed that NumY was 0! \bigskip Hmm...aha! The old classic C learner's error -- we used = instead of ==! The {\bf if} line should have been \begin{verbatim} if (NumY == 0) { \end{verbatim} \bigskip That's what made the program hang: It kept assigning 0 to NumY, so the Y array never grew. \end{slide} \begin{slide} We recompile, then run the program outside of DDD, in another window to see if it works now. We get: \begin{verbatim} % ins 12 5 9 3 2 25 8 19 200 10 Segmentation fault % \end{verbatim} % \textcolor{red}{Symptom:} A seg fault in Unix means an execution error due to the program's accessing memory which is not allocated to it. \bigskip {\bf Fundamental Principle for Execution Errors:} \textcolor{red}{The \underline{first} step to take after an execution error is to run the program through DDD (if the error occurred when run without DDD), to determine \underline{where} the execution error occurred.} \end{slide} \begin{slide} So, let's re-rerun the program within DDD. \bigskip \begin{itemize} \item We don't want to stop at the breakpoints, so: \begin{itemize} \item Go to each breakpoint. \item Right-click on the stop sign at the breakpoint. \item Choose Disable. (The red stop signs turn to gray.) \end{itemize} \item We simply hit the Run button in the Command Tool window. \item DDD will automatically load the newly-compiled files. \item We don't have to specify the command-line arguments again, as they are re-used with each run within DDD unless we change them. \end{itemize} \bigskip \end{slide} \begin{slide} \includegraphics[width=6.0in]{Fig8.jpg} \end{slide} \begin{slide} DDD's red arrow tells us that the execution error occurred on the line \begin{verbatim} Y[K] = Y[K-1]; \end{verbatim} \bigskip Remember, a seg fault occurs when the program is accessing a portion of memory to which it is not permitted access. \textcolor{red}{So, we suspect that K has a value outside the range of Y, which has only 10 elements.} \bigskip Let's check, once again by moving the mouse cursor to any place K appears: \end{slide} \begin{slide} \includegraphics[width=6.0in]{Fig9.jpg} \end{slide} \begin{slide} Whoa! K = 504 is way out of range. \bigskip (By the way, K = 10 or 11 did not cause a seg fault, as we were still in the same page of virtual memory.) \bigskip Let's look at the code which is setting K: \begin{verbatim} for (K = NumY-1; K > JJ; K++) Y[K] = Y[K-1]; \end{verbatim} \bigskip Recall that this code was supposed to shift the Ys over to the right, first moving the rightmost Y, then shifting the next-to-rightmost Y, etc. \bigskip In other words, this was supposed to be a ``down'' loop; K++ should be K--. \end{slide} \begin{slide} OK, we recompile and then re-run: \begin{verbatim} % ins 12 5 9 3 2 25 8 19 200 10 2 3 5 0 0 0 0 0 0 0 % \end{verbatim} Not correct yet, but at least the first 3 elements are correct. \end{slide} \begin{slide} \bigskip Let's go to ProcessData() and do some spot checks for various values of NumY in the loop there: \begin{verbatim} for (NumY = 0; NumY < NumInputs; NumY++) // insert new Y in the proper place // among Y[0],...,Y[NumY-1] Insert(X[NumY]); \end{verbatim} \bigskip Trying the Binary Search Principle, let's first do a check for the NumY value which is halfway through, i.e. NumInputs/2 = 5: \end{slide} \begin{slide} \begin{itemize} \item Put a breakpoint on the line which calls Insert(). \item Right-click on this breakpoint's stop-sign icon. \item Select Properties. \item Specify Condition as NumY == 5 (not NumY = 5!). \item Hit the Run button. \end{itemize} DDD will stop at the call to Insert() when NumY is 5, skipping the previous calls to Insert(). \bigskip This is a small convenience for this case in which X is only 10 elements, but would be crucial of X had 10,000 elements. \end{slide} \begin{slide} We then check Y (by moving mouse cursor to Y). It turns out that \begin{verbatim} Y = {2,3,5,0,0,0,0,0,0,0} \end{verbatim} just as after the end of full execution. \bigskip So, the problem occurred during ``the first half.'' Well, let's start at the beginning, since the first X, 12, doesn't appear in Y: \begin{itemize} \item Remove the Condition NumY == 5 from the breakpoint at the call to Insert(): Right-click on its stop sign icon, choose Properties, erase the Condition. \item Hit the Run button to restart. \item Each time DDD stops at the call to Insert(), do: \begin{itemize} \item Check Y (as usual, by moving the mouse to an instance of Y anywhere in the code) to \textcolor{red}{confirm it is what it should be at this stage}. \item Hit the Cont button to have DDD continue until the next breakpoint (which will be this one again). \end{itemize} \end{itemize} \end{slide} \begin{slide} We find that the case NumY = 0 works fine, i.e. Y[0] = 12. But the next case, NumY = 1, fails: Y[0] becomes 5, and the 12 disappears. \bigskip So, \textcolor{red}{we've narrowed the problem down to the events within Insert() when NumY = 1.} \bigskip Here's the main part of Insert(): \begin{verbatim} for (J = 0; J < NumY; J++) { if (NewY < Y[J]) { // shift Y[J], Y[J+1],... rightward // before inserting NewY ScootOver(J); Y[J] = NewY; return; } } \end{verbatim} We need to step through these lines for this case NumY = 1: \end{slide} \begin{slide} \begin{itemize} \item Re-run by hitting Run. \item The first time we hit the breakpoint at the call to Insert(), NumY is 0, so hit Cont. \item Hit Step (not Next) to enter Insert(). \item Hit Step or Next twice to get to the {\bf if} within the {\bf for} loop. \item Take a look around: \textcolor{red}{Confirm our expected values for NumY (should be 1), NewY (should be 5), and Y (should be 12, 0, 0, ...).} Yes, all OK. \item Now \verb|(NewY < Y[J])| should be true; \textcolor{red}{confirm it}: Hit Step or Next. Yes, we do go to the call to ScootOver(). \item Let's skip over ScootOver(), i.e. execute it but not enter it: Hit Next (not Step). \item Let's \textcolor{red}{confirm that the Y array was shifted rightward}: Move the mouse cursor to display the values in Y. Aha! The 12 is still in Y[0], instead of in Y[1]. \end{itemize} \end{slide} \begin{slide} So, we need to go into ScootOver(). \begin{itemize} \item Disable existing breakpoints, and add a new one at the call to ScootOver(). \item Re-run the program. \item The first time the breakpoint is hit, this should be the case NumY = 1, but \textcolor{red}{confirm it}. Yes, OK. \item Hit Step (not Next) to enter ScootOver(). \item Remember, at this time Y consists of just one element, 12, which we must shift to the right to make room for NewY, 5, which is to be inserted. \textcolor{red}{We will try to confirm this.} \item Hit Step or Next to execute the first line. \end{itemize} \end{slide} \begin{slide} \includegraphics[width=6.0in]{Fig10.jpg} \end{slide} \begin{slide} % \textcolor{red}{Symptom:} The loop to shift Y rightward wasn't executed at all. \bigskip A closer look shows why: Since NumY was 1 and JJ was 0, the loop amounted to \begin{verbatim} for (K = 0; K > 0; K--) \end{verbatim} so the loop wasn't executed. \bigskip A bit more thought reveals that the expression NumY-1 in the loop should have been NumY. \end{slide} \begin{slide} So, recompile and re-run: \begin{verbatim} % ins 12 5 9 3 2 25 8 19 200 10 2 3 5 8 9 10 12 0 0 0 \end{verbatim} Looks like we are almost done, possibly with just one bug remaining. \end{slide} \begin{slide} \bigskip The first element missing in the output above is 25, so let's see what happened when it was inserted into Y. \begin{itemize} \item Re-enable the breakpoint at the call to Insert(). \item Add the condition X[NumY] == 25. \item Hit the Run button, then Step to enter Insert(). \item We anticipate that we may be checking Y a lot, so it's easier to continuously display it: \begin{itemize} \item Go to any instance of Y in the Source File window. \item Right-click on it. \item Select ``Display Y''. \item A Data window will open above the Source File window. \item You may wish to resize the DDD window, and the Data and Source File windows. \end{itemize} \item Keep hitting Next until we see a change in Y. \end{itemize} \end{slide} \begin{slide} \includegraphics[width=6.0in]{Fig11.jpg} \end{slide} \begin{slide} Y never changed! The 25 was ignored. \bigskip After some thought, we realize that the {\bf for} loop only handles the case in which NewY is inserted within Y. We need separate code for the case in which NewY is added at the right end of Y. \bigskip After the {\bf for} loop, add the code: \begin{verbatim} // one more case: NewY > all existing Y elements Y[NumY] = NewY; \end{verbatim} \end{slide} \begin{slide} Examining arrays passed as function arguments: \bigskip Many people avoid using global variables. Suppose for example the arrays X and Y in our insert-sort example had been declared local to main(). The call to GetArgs(), for instance, would now be \begin{verbatim} GetArgs(X,Argc,Argv); \end{verbatim} and GetArgs() itself would look like this: \begin{verbatim} void GetArgs(int XX[], int AC, char **AV) { int I; NumInputs = AC - 1; for (I = 0; I < NumInputs; I++) XX[I] = atoi(AV[I+1]); } \end{verbatim} \end{slide} \begin{slide} Suppose we wish to examine XX while in GetArgs(). Our old method of moving the mouse cursor to XX is no longer useful; only the memory address in the pointer XX will be shown. \bigskip However, we can still easily view individual array elements, as mentioned earlier. In this context we would: \begin{itemize} \item Use the mouse to highlight ``XX[I]''. \item Right-click on the highlighted item. \item Select ``Print XX[I]''. (Or choose ``Display XX[I]'' for continuous viewing in a Data window.) \item The value of XX[I] will be printed to the Debugger Console window. \end{itemize} \end{slide} \begin{slide} Examining linked data structures: \bigskip Some debuggers, including DDD, GVD and JSwat, have nice facilities for displaying linked data structures, which are of great value. To illustrate how this is done in DDD, we've rewritten Ins.c as Lnk.c, which implements Y as a linear linked list instead of as an array: \begin{verbatim} struct ListElt { int Elt; struct ListElt *NextElt; }; struct ListElt *Y; // ptr to workspace list \end{verbatim} \end{slide} \begin{slide} Here is how to display the list: \begin{itemize} \item [(a)] Right-click anywhere Y appears in the Source File window, and choose ``Display *Y''. \item [(b)] A Data window will be created, and a box will appear there showing the contents of the {\bf struct} pointed to by Y. \item [(c)] If NextElt in that {\bf struct} is nonnull, right-click on it, and select ``Display *()'. \item [(d)] Repeat step (c) until the entire list (or the portion of interest to you) is displayed. \end{itemize} \end{slide} \begin{slide} \includegraphics[width=6.0in]{Fig12.jpg} \end{slide} \begin{slide} Using the display: \begin{itemize} \item The display will automatically update as you step through the program (except when items are appended, in which case you must add the new link manually). \item If the list is too large for the window, use the scrollbars to view different sections of it. \item To delete part or all of the display, right-click on the displayed item and choose Undisplay. \end{itemize} \end{slide} \begin{slide} Summary: \bigskip \textcolor{red}{A debugging tool cannot determine \underline{what} your bug is, but it is great value in determining \underline{where} it is. You should use one in all of your programming work.} \bigskip (See related links, next slide.) \end{slide} \begin{slide} Good debugging tools: \bigskip My criteria: \begin{itemize} \item Free (especially helpful for classroom use). \item Advanced features (e.g. display of linked data structures). \item Small memory footprint. \item I prefer standalone debuggers, not integrated development environments (IDEs) --- I want to use my own favorite text editor. \end{itemize} \end{slide} \begin{slide} Standalone debuggers: \begin{itemize} \item DDD; featured here; \url{http://heather.cs.ucdavis.edu/~matloff/ddd.html}. \item GVD: Very similar to DDD, less general but trimmer, faster-loading; available for both UNIX and Windows; \url{http://heather.cs.ucdavis.edu/~matloff/gvd.html}. \item JSwat: Excellent debugger for Java; works on most platforms; can be used as standalone or with the JIPE IDE (see below); \url{http://heather.cs.ucdavis.edu/~matloff/jswat.html}. \end{itemize} \end{slide} \begin{slide} IDEs: \begin{itemize} \item KDevelop: For C/C++, on Linux under KDE. \item BlueJ: For Java, especially for learners; works on most platforms; \url{http://heather.cs.ucdavis.edu/~matloff/bluej.html}. \item JIPE: For Java; works on most platforms; \url{http://jipe.sourceforge.net/}. \end{itemize} \end{slide} \begin{slide} Software development is faster and more pleasant if you make good use of a text editor: \begin{itemize} \item My tutorial on general editing tips for programmers: \url{http://heather.cs.ucdavis.edu/~matloff/progedit.html}. \item Vim: Very advanced extension of vi; very popular; multi-platform; free; \url{http://heather.cs.ucdavis.edu/~matloff/vim.html}. \item Emacs: A classic; programmable; multi-platform; free; \url{http://heather.cs.ucdavis.edu/~matloff/UnixAndC/Editors/Emacs.html}. \item JEdit: Beautiful product; great features; for C/C++/Java/etc; free; \url{http://www.jedit.org}. \end{itemize} \end{slide} \end{document}