INFINITE LOOP INJECTION

11 November 2017

Quickly, what’s the matter with this code?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Queue<T> implements Collection<T> {
    private class Node {
        Node next = null;
        T data = null;

        Node() {
            this.next = this;
        }

        Node(T item) {
            this.next = this;
            this.data = item;
        }
    }

    Node last;

    public void enqueue(T item) {
        if (last == null) {
            last = new Node(item);
            return;
        }

        //Store references
        Node newNode = new Node(item);
        Node first = last.next;

        //Insert into the linked list
        last.next = newNode;
        newNode.next = first;

        //Adjust the pointer
        last = newNode;
    }

    //dummy implementations of Collection methods
}

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 System.out.println(), a public static void main(String args) aaaaaand, it works. No errors. No hang ups. The program runs and terminates.

WHAT

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:

Example image

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 Collection<T>.

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
@Override
public int size() {
    if (last == null) return 0;
    if (last.next == last) return 1;

    Node c = last.next;
    int count = 1;

    while(c != last) count++;
    return count;
}

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!

Oh.

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.