Debugging flaky infinite loops

There are tons of great open source solutions that help us every day to develop, test, and debug our software products — Symflower CLI, Visual Studio Code, the Delve debugger, or the testify unit testing framework are just a few wonderful examples. In the past few years, we’ve tweaked and extended this nifty set of little helpers and tools to even further improve our daily programming workflow. We want to give back to the amazing open source community by releasing some of our internal tools to the public. Therefore, we created the Symflower Garden: a collection of binaries, packages and scripts that we use on a daily basis to make our lives as programmers easier.

Today we’ll take a look at the first addition to the Garden: untilfail.

An Overview of untilfail

Have you ever had the uncomfortable feeling that some of your code is “flaky” and wanted to reproduce the fishy behavior to be sure? That’s where the shell script untilfail can help out. It is very simple to use, and aids in debugging such non-deterministic — or “flaky” — errors. All it does is execute a program until it encounters a non-zero exit code. Similar to russian roulette… except nobody has to get hurt, of course. One can also specify a timeout as we’ll see. Using untilfail does not guarantee that some code is “flaky”-free, but it’s usually a valuable aid in case we suspect non-determinism, and want to reproduce it to be sure. The remainder of this post will explain how to use the tool and show how it helps us find a flaky infinite loop in an example program.

Using untilfail

The tool can be used with the command pattern: untilfail [ -t TIMEOUT ] COMMAND where the to-be-executed program is directly given and an optional timeout can be set. Let’s look at some simple examples that should give us a clear idea on how unitfail works.

> untilfail true
# Will never fail so we see infinite tries.
# Abort with Ctrl+C.

> unitlfail false
# Will instantly fail so we see only one try.

> untilfail -t 2s sleep 1
# Will never take longer than one second so we see infinite tries.
# Abort with Ctrl+C.

> untilfail -t 1s sleep 2
# Will always take longer than one second so we see only one try.

These are of course only basic examples that show the corner cases of untilfail, so let’s go on a hunt for a flaky infinite loop and travel back in time to 19th century France.

Hunting flaky Infinite Loops

In roughly 1875, Charles Pierre Trémaux was about to invent the famous Depth First Search algorithm. He was a young inventor at this point, and was asking himself if there was a structured way of escaping mazes. In the following example, he had designed the logic for a mouse stuck in a labyrinth searching for some sweet, sweet gorgonzola cheese — yum! Of course, computers didn’t exist back then, but they do now, so we can just explore his experiments as Go code. The maze is represented as a graph through a map from node names to their edge set. The unfinished algorithm is a stack based, iterative approach that is still missing checks that ensure the same maze corridor is never searched twice (can you already guess where this is going?). All encountered possible choices at each intersection are pushed onto the search stack, and we run through the maze as long as there are choices to consider. The mouse needs to take a rest every once in a while, of course, so as not to get exhausted. This seems unnecessary at first, but it simulates internal computations that might be performed by a more practical example.

type Maze map[string]map[string]bool

type Stack struct {
	Item     string
	Previous *Stack
}

func FindTheCheese(maze Maze, root string) {
	stack := &Stack{
		Item: root,
	}

	for stack != nil {
		n := stack.Item
		stack = stack.Previous

		// This is exhausting, take a little nap.
		time.Sleep(time.Duration(rand.Int31n(4)) * time.Second)

		if n == "Cheese" {
			fmt.Println("Nom nom nom ...")
			return
		}

		for choice := range maze[n] {
			stack = &Stack{
				Item:     choice,
				Previous: stack,
			}
		}
	}
}

Charles Pierre also came up with a little example maze to try this algorithm, such as the following. You might already spot the problematic relationship between node d and node g. Once the mouse ends up in either one of them, it cannot get out anymore.

labyrinth := map[string]map[string]bool{
	"a": map[string]bool{
		"b": true,
		"c": true,
		"e": true,
	},
	"b": map[string]bool{
		"c": true,
		"e": true,
	},
	"c": map[string]bool{
		"b": true,
		"f": true,
	},
	"d": map[string]bool{
		"g": true,
	},
	"e": map[string]bool{
		"Cheese": true,
	},
	"f": map[string]bool{
		"a": true,
		"e": true,
		"c": true,
		"d": true,
	},
	"g": map[string]bool{
		"d": true,
	},
}

FindTheCheese(labyrinth, "a")

When running this example, the mouse will be busy for quite some time, but the program might eventually respond with the crunchy munching of cheese. Different runs take longer, finish quicker, or even seem to take forever, so Charles Pierre is starting to wonder if everything works as expected — there is some cheese hidden in the labyrinth after all! Let’s use untilfail to help our inventor and check if the logic might get stuck in an infinite loop. untilfail -t 1m go run maze/main.go will execute the example repeatedly until the computation takes longer than a minute. In our case, untilfail aborts after nine retries, which is where we hit the infinite loop case and get stuck in the maze for longer than one minute.

> untilfail -t 1m go run maze/main.go
 run 1
Nom nom nom ...
 run 2
Nom nom nom ...
 run 3
Nom nom nom ...
 run 4
Nom nom nom ...
 run 5
Nom nom nom ...
 run 6
Nom nom nom ...
 run 7
Nom nom nom ...
 run 8
Nom nom nom ...
 run 9

 executed 9 times

At this moment, we know something isn’t right. There are seven intersections, and the mouse sleeps for approximately two seconds at each intersection, so within one minute, the algorithm should be able to visit each intersection at least four times. Based on this, Monsieur Trémaux probably needs to go back and check for errors in the design. If you’re eager to implement a smarter version that can detect and properly handle such maze configurations containing infinite loops, try it on your own first — you can then check out how Charles Pierre Trémaux eventually solved the problem when he finished the complete Depth First Algorithm.

We’d love to hear from your own experiences with non-deterministic errors. Hit us up on Twitter and tell us about your worst debugging nightmares (or which cheese flavours are your favorite). If you’re interested in how untilfail works under the hood you can check out the source code on the symflower/garden GitHub repository. Please feel free to also report any bugs you encountered or open an issue or a pull request in case you have an idea on how to improve untilfail. You can also star and watch the repository to stay up to date with the next open source releases we’re planning for the future. Finally, feel free to subscribe to our newsletter or check out our Linkedin and Facebook pages.