Quickly, what’s the matter with this code?
If you answered “nothing”, you would correct! It’s nothing more than a half-implemented reference-based Queue. Which is why I was very confused when I ran my tests, and they … didn’t stop. They didn’t fail nor succede, they simply just didn’t stop running.
Strange. Well, since this is clearly a runtime issue with my code somewhere, my first though, and probably everyone else’s, was to invoke the debugger and step through the code.
So I set a breakpoint on
enqueue(). In the first call, when the queue is empty, the code goes through the code path under the if statement successfully. In the second call, however, when the queue contains a single node, the programs runs perfectly fine all the way up to
last.next = newNode;, at which point the program and debugger hands indefinately, giving nothing but “Waiting for last debugger command to complete.”
Huh? What? Why?
Last time I checked, assignment operations were typically O(1). Out of all the places the program could be hanging at, that single line is the one that makes the least amount of sense.
Alright, well normal debugging is out of the question. Let’s try print debugginging. Throw in a few
public static void main(String args) aaaaaand, it works. No errors. No hang ups. The program runs and terminates.
The next few hours consisted of lots of Googling, Stack Overflow, and just plain throwing things at the wall. I won’t bore you with the details.
Take a look at this:
Recognize this? IDEA calls them “Data Views”. They simply display some useful properties of certain objects in the editor and in the stack view. You can implement your own if you need them, but IDEA already comes with presets for common Java object.
Like, for example, displaying the size of anything implementing
Since my Queue class implements
Collection<T>, it has to override
size(). Which means that IDEA must be calling
size() on my queue object.
So, here’s the size function for my Queue class:
You might notice the problem right away here. The while loop doesn’t have any thing to change the value of
c, which means that
c will never be equal to
last. Which means, hey, we have an infinite loop! In a function that IDEA calls while debugging!
On top of all this, my test case checks the size of the queue to determine success. Which means that under normal execution, my code gets caught in an infinite loop as well. But, I could never have never determined this, because my code quite literally injects a bug into my debugger.