Computer Science 136 Data Structures and Advanced Programming Williams College Fall 2005

Short Answers

Complete the following problems from the book and turn them in as a text file lab6.txt.

Since there is no lab meeting this week, I am making this lab optional. There is nothing to submit, but getting some practice this week with the debugger will help you as we continue to tackle more complex Java programming tasks in lab.

Occasionally, even the best of programmers, such as those found in data structures classes at small liberal arts colleges in the scenic Berkshire hills of western Massachusetts, make mistakes. Their code has bugs, necessitating a debugging session. So far, we have done our debugging by thinking about the output and what might have going wrong to cause the incorrect behavior. If that fails, we try to narrow down the problem by looking at values of variables at key points in the program by printing them out with System.out.println(), adding printouts until we pinpoint just where things started to go wrong.

This is often an effective approach, and it is probably the most commonly-used debugging technique. However, there are tools out there, known as debuggers, that can help. Many integrated development environments (IDEs) such as Eclipse, include debuggers. Since we are not using an IDE, we will consider a simple, command-driven debugger called jdb, the Java debugger. It comes standard with all Java distributions. I encourage you to try out some of the graphical debuggers available as well, including Eclipse and Xcode on the lab Macs.

But for today, we will just consider a few simple examples in jdb. To run using jdb, the first step is to compile your Java program with the debugging flag turned on:

  javac -g MyClass.java

The -g tells Java to keep some extra information around that it normally would throw away. This will allow the debugger more information about your program, and it can better identify the names of variables at run time.

Then you need to run your program in jdb. To do this, you would put jdb on your command line where you would normally put java:

  jdb MyClass is fun

This will start an application with a main method found in class MyClass and pass it "is" and "fun" as command-line parameters.

Copy the file Crash.java from the labs/debugging directory in the CS 136 common area. Compile it with the -g option and run it in the debugger:

  javac -g Crash.java
  jdb Crash 1 2 3 4

You should see:

Initializing jdb ...
>

This is the jdb prompt, and it is ready to run your program. To run it, type "run" at the prompt, and you should see that in fact this program crashes:

run Crash 1 2 3 4
Set uncaught java.lang.Throwable
Set deferred uncaught java.lang.Throwable
>
VM Started:
Exception occurred: java.lang.ArrayIndexOutOfBoundsException (uncaught)"thread=main", Crash.main(), line=13 bci=6
5       System.out.println(args[17]);

main[1]

You can see that you already have a bit more of information than you'd get from a regular stack trace. It shows you the source code at the line that caused the exception.

The main[1] is a prompt at this point informs you that you have stopped in the "main" thread and you are at level 1 in the call stack. Try the "help" command to see all of the things you can do at this prompt.

Let's try a few. At this point, you can see the full call stack with the command "where":

main[1] where
  [1] Crash.main (Crash.java:13)

We learn nothing much from this, since we already knew we stopped at line 13 of Crash.java. However, we can also print the values of any variables. There's only one here, so let's print it with "print args":

main[1] print args
 args = instance of java.lang.String[3] (id=312)

We know it is an array of 4 Strings. We can also query its length:

main[1] print args.length
 args.length = 4

This is probably enough to tell us that there's no 17th element in this array (which you probably figured out before we started this exercise anyway).

Let's move on to a slightly more complicated example. Copy Crash2.java from the same place in the CS 136 common directory. This program creates a Vector, adds one element to it, then tries to access element 11, which, of course, doesn't exist. When you compile the program, don't forget the -g flag, then run it in the debugger.

You should get an ArrayIndexOutOfBoundsException. Now, "where" gives us some slightly more useful information:

main[1] where
  [1] structure.Vector.get (Vector.java:398)
  [2] Crash2.main (Crash2.java:16)

We're in the get() method of structure.Vector. This means we can do very useful things like print the instance variables of this Vector:

main[1] print elementData
 elementData = instance of java.lang.Object[10] (id=406)
main[1] print elementData[0]
 elementData[0] = "17"
main[1] print elementCount
 elementCount = 1

Note that jdb uses the toString method of the Integer that we have in the Vector.

We can also call this Vector's toString method by trying to print "this":

main[1] print this
 this = "<Vector: 17>"

Maybe we're not interested in things going on in this method. We want something higher up the call stack. We can get there with the "up" command, which will change our prompt to "main[2]" meaning we're at level 2 on the call stack (second to last method called). From there, we can look at variables in the main method of Crash2:

main[2] print v
 v = "<Vector: 17>"

We can also get more context from the source file with the "list" command:

main[2] list
12        public static void main(String[] args) {
13    
14      Vector<Integer> v = new Vector<Integer>();
15      v.add(17);
16 =>   System.out.println(v.get(11));
17        }

Often, we don't just want to do a post-mortem on a program that crashed with an exception. We want to know when something bad happened to cause the exception. jdb also allows us to set breakpoints, where it will stop execution of the program and give us a prompt, so we can inspect values of variables and the call stack without waiting for the actual crash.

Now, copy the file BadSort.java. This implements a selection sort on a short array of ints, but an off-by-one error keeps it from working correctly. Let's experiment with the debugger to track down this error. We first compile it up with the -g and start it in the debugger:

-> jdb BadSort
Initializing jdb ...
>

If we simply run the program at this point, it runs to completion and it's too late to do anything with the debugger. We just see the wrong answer printed. What we want to do is to stop in the sort method and see what's going on along the way to see if we can figure out what's wrong. So first, let's set a breakpoint that will tell jdb to stop when it gets to a certain place. In this case, it is when the sort method is first invoked:

> stop in BadSort.sort
Deferring breakpoint BadSort.sort.
It will be set after the class is loaded.
>

Now if we run the program, it will stop as soon as we get into sort:

> stop in BadSort.sort
Deferring breakpoint BadSort.sort.
It will be set after the class is loaded.
> run
run BadSort
Set uncaught java.lang.Throwable
Set deferred uncaught java.lang.Throwable
> 
VM Started: Set deferred breakpoint BadSort.sort

Breakpoint hit: "thread=main", BadSort.sort(), line=29 bci=0
29      int numUnsorted = array.length-1; /* oops, we forgot one */

main[1]

And from this point, we can look at variables and the stack, but we can also step through the execution, with one of four commands:

• step - execute the next line of code, stopping inside of method calls, if the line calls methods
• step up - execute until the current method returns
• next - execute the next line of code, not stopping in any method calls
• cont - continue to the next breakpoint or program termination

Try a few "step" commands to see it trace through your code. Print out some of the variables. If you say "print this", it will call BadSort's toString method, which includes a printout of the array elements. You can trace through to see how the array evolves. Set a breakpoint within the loop with "stop at BadSort:33" and "cont" around the loop, printing the array after each loop. You can see how the selection sort is (incorrectly) proceeding. Hopefully if you were actually trying to debug this, you would get the idea that it's not doing the right thing to the last element of the array.

Debuggers are also especially useful when developing more complicated structures like linked lists. Keep this in mind as we move forward into bigger and better structures. For practice, trace through some of your previous lab programs with jdb.

Also experiment with some of the other jdb commands that you can find with the "help" command. Graphical debuggers are even more useful in many situations and I encourage you to try them out and see which ones you like.