The Halting Problem
One of the best known problems in all of computer science is the halting problem. Basically this is the problem of determining, from a description of a computer program and an input, whether the program will finish running or continue to run forever. Way back in 1936 the famous Alan Turing proved that it’s impossible to provide a general algorithm to solve the halting problem for all possible program — input pairs. In other words, you can’t write code that will always be able to determine whether your program is going to finish, or will get stuck in an infinite loop. Obviously I’m not going to prove Alan Turing wrong, but I have recently came up with some code that can make sure that a specific code, which is very common to many JavaScript applications, won’t enter an infinite loop.
JavaScript Callbacks
The JavaScript language relies heavily on callbacks to perform asynchronous processing. This is a pattern that is very common when writing JavaScript code for the browser, or for environments such as NodeJS. JavaScript callbacks are most commonly implemented as functions, that are passed as arguments to other functions, that instigate some asynchronous operations. When the operations are completed, the callback functions are invoked, often indicating success or failure. This is possible because in JavaScript, functions are first-class citizens, and can be passed as arguments to functions just like any other value.
The callback mechanism can be generalized by allowing multiple callbacks to subscribe for a single event. A callback subscribe function could accept two values: the name of the event, and the actual callback function to be invoked when that event occurs. Thus allowing multiple external modules to hook their desired functionality into the current flow while enabling separation of concerns between the different modules. This is most commonly referred to as the classical Event Emitter pattern or Pub-Sub.
Basically the classic implementation for this would be holding a private map of event names + callbacks pairs, and adding a public method for subscribing (and unsubscribing if you wish) these pairs. We would also want to add an execution method (the emit function) for the subscribed callbacks, in order to actually run them. This method can be completely internal or an external one if we wish to trigger it from outside.
Obviously the one who call the subscribe method has to be aware of the supported keys or event names/types, otherwise they won’t ever be executed.
This would typically look something like this:
So let’s get back to infinite loops!
I was developing a similar mechanism and while doing so, I thought about a theoretical case, which didn’t happen yet, but if it does, can be very hard to track; where the emit function which executes the callbacks can keep calling itself endlessly.
Suppose someone subscribes with a callback to my mechanism, and inside their callback they will trigger another known event (from my set of known event names), unknowingly that that event is also executing the event’s callbacks, so the callback will be called again… and again… and again…
The one who’ll call the other event externally in their callback, wouldn’t necessarily know that the event execution is triggering an additional set of callbacks executions and the code will enter an infinite loop, and quite an elusive one, to be frank.
Let’s have some TDD fun :)
So I decided to attack the problem with TDD style! because I didn’t have an actual use case for this alleged bug and it was purely theoretical, I thought that a TDD approach can really help me define the problem in its simplest and purest way. Moreover, I knew that if I add a real maintainable and stable test for this case, it will never happen in production.
So first, I wanted to write the simplest and shortest test possible (even if it’s something that no one will ever write in a real life code example) that will first simulate the problem, and only then figure out how to solve it.
I ran it. The result was maximum call stack exceeded, exactly as I wanted. So I had a failing test with the dangerous scenario on my hand and obviously it was failing. I thought about the passing scenario and what do I want to occur there. I realized I don’t even need any assertions at all, all I care about is that the test is ending.
The solution itself for the alleged bug was quite simple, I decided to store a state variable that marks whenever a callback is executed, and gets resets to default when the callback execution is ended.
So if I get a callback that will trigger additional callbacks again, they would just be ignored and reported.
I added my code, ran the test again and it passed. Sweetest simple and clean TDD, no assertions. Just plain green test :)
After that I could refactor my code and make it prettier and nicer. All I needed to do was to re-run my test and make sure it’s still green!
Well, actually the best part about it is that it’s bulletproof for the future. If someone else alters my solution for the problem or remove it, the test will get a maximum call stack exceeded again and will obviously fail :)
Excercise side note
Note that my solution will only work if the additional event emitting is done in a synchronous way. What would you do if the subscribed callback is triggering the execution of other callbacks in an asynchronous way like the test bellow? I’d leave it as a challenge for my readers, would love to hear whatever you can come up with :)