This article was orignally published in my personal blog.
Intro
From the dark ol’ days of writing an entire application and only then starting to test it (often, manually) till nowadays, I have scoured a painful path of unending bug-fixing in production through the nights, many times not even knowing what was causing those bugs.
Since I first heard of Test Driven Development, it changed the way I think about software development.
I will not be digressing about TDD philosophy and its implications here, because a lot of more qualified people have done it before me. So let’s get to the code!
First, the problem and its solution
A long time ago in a galaxy far far away, I ended up in a problem: I had to monitor a “stream” (more like a polling) of events that were being created at a certain application in my Node.JS backend. This “stream” was not uniform and, most of the time, no event occurred.
I could not use websockets, so I would have to buffer these events in my backend. I thought using a database (even an in-memory one like Redis) just for that was too much. Then I decided that I would keep the events in memory and as my application did not care for all events that ever happened, I would keep only the last N of them.
Since Node.JS arrays are dynamic, they did not fit my needs. I did not want a fixed-size array implementation, what I needed was a fixed-sized first-in/first-out (FIFO) data structure, AKA a queue, which instead of overflowing when full, should pop its first element and then add the new one at the end.
Expected behavior
The data structure described above is rather simple. Its expected behavior could be summarized as follows:
Adding elements:
- When it is not full, it should add the new element to the end; its size should be increased by 1.
- When it is full, it should remove the first element and then add the new element to the end; its size must not change.
- The removed element should be returned.
Removing elements:
- When it is not empty, it should remove the first element and return it; its size should be decreased by 1.
- When it is empty, it should throw an error.
A Mocha to go, please!
From the docs:
Mocha is a feature-rich JavaScript test framework running on Node.js and in the browser, making asynchronous testing simple and fun. Mocha tests run serially, allowing for flexible and accurate reporting, while mapping uncaught exceptions to the correct test cases. Hosted on GitHub.
Installation
yarn add --dev mocha
# or with NPM:
# npm install --save-dev mocha
Writing tests
To create a test suite, you use a globally defined function called describe. To add test cases to a suite, you should use another global function it:
Suites can be nested indefinitely when you want to group your test cases. Mocha will collect all your suites recursively and execute all test cases it find within them in the order they are declared.
And that’s probably about all you need to tedknow about Mocha to get star (at least for basic usage). It excels so much for simplicity and extensibility, that it allows you to use whatever assertion library and other plugins you want.
Running tests
yarn mocha '<path-to-test-file>'
# or with NPM's npx:
# npx mocha '<path-to-test-file>'
Enter Chai
By default, Mocha can be used along with Node.js native assert module. It works just fine, however I don't find its developer experience to be exactly great. For that reason, we will use a 3rd-party assertion library called Chai.
From the docs:
Chai is a BDD / TDD assertion library for node and the browser that can be delightfully paired with any JavaScript testing framework.
Installation
yarn add --dev chai
# or with NPM:
# npm install --save-dev chai
Usage
Chai offers 3 different styles for writing assertions:
All of them have the same capabilities, so choosing one or another is more a matter of preference than of objective facts. I like to use the expect interface.
Oh, tests! Oh, dreaded tests!
Going back to our original problem, let’s translate the expected behavior into mocha test suites. But first, let’s do some setup:
const chai = require("chai");
const expect = chai.expect;
const RoundQueue = require("./round-linked-queue");
describe("Round-Queue", () => {
});
Testing queue creation
The main reason why we are creating this data structure is that it has to be a limited size, so let's make sure it has such property:
const chai = require("chai");
const expect = chai.expect;
const RoundQueue = require("./round-linked-queue");
describe("Round-Queue", () => {
describe("When creating an instance", () => {
it("Should properly set the maxLength property", () => {
const queueLength = 3;
const queue = new RoundQueue(queueLength);
expect(queue.maxLength).to.equal(queueLength);
});
});
});
Next we implement just enough code to make the test above pass:
class RoundLinkedQueue {
constructor(maxLength) {
this._maxLength = maxLength;
}
get maxLength() {
return this._maxLength;
}
}
module.exports = RoundLinkedQueue;
To run the suite, we do:
yarn mocha round-linked-queue.test.js
Keep moving and we must ensure that a queue is created empty:
it("Should initially set the length to zero", () => {
const queueLength = 3;
const queue = new RoundQueue(queueLength);
expect(queue.length).to.equal(0);
});
In order to make the new test pass, we can do as follows:
class RoundLinkedQueue {
constructor(maxLength) {
this._maxLength = maxLength;
this._length = 0;
}
get maxLength() {
return this._maxLength;
}
get length() {
return this._length;
}
}
Testing adding elements
Next we create another test suite inside the top-level suite to test the behavior of adding elements to a queue.
Our base use case happens when the queue is empty and we want to add an element to it:
describe("When adding elements", () => {
it("Should add an element to an empty queue", () => {
const queue = new RoundQueue(3);
const originalLength = queue.length;
const elementToAdd = 1;
queue.add(elementToAdd);
// Element should've been added to the end of the queue
expect(queue.last).to.equal(elementToAdd);
// But since it is now the only element, it should also be the at beginning as well
expect(queue.first).to.equal(elementToAdd);
// Length should've been increased by 1
expect(queue.length).to.equal(originalLength + 1);
});
});
If you run the test suite right now, you will get the following error:
The test failed because we didn't implement the add method yet. Now we add just enough code to make this first test case pass.
Important: the code bellow is not entirely correct, we will have to modify it further in order to make the add method work as expected. However, it does make our first test case "adding element to an empty queue" pass.
class RoundLinkedQueue {
// ...
add(element) {
this._root = element;
this._first = element;
this._last = element;
this._length += 1;
}
}
Now let's try adding a test for when the queue is not empty anymore and yet we still want to add an element to it:
it("Should add an element to the end of a non-empty queue", () => {
const queue = new RoundQueue(3);
const previousElement = 1;
const elementToAdd = 2;
// Make the queue non-empty
queue.add(previousElement);
queue.add(elementToAdd);
// Element should've been added to the end of the queue
expect(queue.last).to.equal(elementToAdd, "last not properly set");
// But the first pointer must remain the first element added
expect(queue.first).to.equal(previousElement, "first not properly set");
// Length should've been increased by 2
expect(queue.length).to.equal(2, "length not properly set");
});
If we once again run the test suite without changing the implementation, we will get a failure:
The more attentive readers should probably be expecting this error because the way we implemented the add method before would simply overwrite the elements in the queue. To fix this, we will need some more code:
class RoundLinkedQueue {
// ...
add(element) {
const node = {
data: element,
next: null,
};
if (!this._root) {
this._root = node;
this._first = node;
this._last = node;
} else {
const previousLast = this._last;
previousLast.next = node;
this._last = node;
}
this._length += 1;
}
}
We had to convert our _root, _first and _last into a node object containing data — the actual value of the item — and next — a pointer to the next node in the linked list.
Moving on, now it's time to something a little bit more challenging. Whenever our queue is at capacity, adding a new element should should cause the removal of the element that was first added:
it("Should remove the first element and add the new element to the end of a full queue", () => {
const queue = new RoundQueue(3);
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);
// Element should've been added to the end of the queue
expect(queue.last).to.equal(4, "last not properly set");
// The second element should've been shifted to the first position
expect(queue.first).to.equal(2, "first not properly set");
// Length should still be the same
expect(queue.length).to.equal(3, "length not properly set");
});
Running tests once more we get:
Looks like we will need some conditionals to make the new test case pass along with the previous ones:
class RoundLinkedQueue {
// ...
add(element) {
const node = {
data: element,
next: null,
};
if (this.length < this.maxLength) {
if (!this._root) {
this._root = node;
this._first = node;
this._last = node;
} else {
const previousLast = this._last;
previousLast.next = node;
this._last = node;
}
this._length += 1;
} else {
this._root = this._root.next;
this._last.next = node;
this._first = this._root;
this._last = node;
}
}
}
Halt! Refactor time
So far we were writing code in a rather linear fashion: make a failing test, implement code to make it pass; make another failing test, write just enough code to make it pass, and so on.
In TDD jargon, creating a failing test is called the red phase, while implementing the code that will make it pass is the green phase.
In reality, things are not so pretty-neaty. You will not always get how to write the best code possible the first time. The truth is we've been cheating a little: we were skipping the refactor phase of the TDD cycle:
Right now I see some possible improvements in our data structure:
- Having both
_rootand_firstproperties seem redundant. - There is some duplication of code in the
addmethod (remember DRY?)
Because we already know the expected behavior, which is coded in our test suite, we are comfortable to refactor mercilessly.
class RoundLinkedQueue {
// ...
add(element) {
const node = {
data: element,
next: null,
};
if (this.length < this.maxLength) {
if (!this._first) {
this._first = node;
this._last = node;
}
this._length += 1;
} else {
this._first = this._first.next;
}
this._last.next = node;
this._last = node;
}
}
Hopefully, our tests are still green:
Taking some shortcuts
Now we are going to cheat a little bit.
The last requirement is that the add method should return the removed element when the queue is full. What to return when the queue is not full is not in the specification though. In JavaScript, uninitialized values have a special value called undefined. It makes sense to return that when adding to the queue does not remove any element, so we can add the following two test cases.
it("Should return the removed element from a full queue", () => {
const queue = new RoundQueue(3);
queue.add(1);
queue.add(2);
queue.add(3);
const result = queue.add(4);
expect(result).to.equal(1, "removed wrong element");
});
it("Should return undefined when the queue is not full", () => {
const queue = new RoundQueue(3);
const result = queue.add(1);
expect(result).to.equal(undefined, "should not return an element");
});
Cool, so let's just return the element from the node we just removed:
class RoundLinkedQueue {
// ...
add(element) {
const node = {
data: element,
next: null,
};
let removedElement;
if (this.length < this.maxLength) {
if (!this._first) {
this._first = node;
this._last = node;
}
this._length += 1;
} else {
removedElement = this._first.data;
this._first = this._first.next;
}
this._last.next = node;
this._last = node;
return removedElement;
}
}
Look like we are are done with the add method!
Testing removing elements
Removing elements seems like a simpler operation. Our base use case is when the queue is not empty. We remove an element from it and decrease its length by one:
describe("When removing elements", () => {
it("Should remove the first element of a non-empty queue", () => {
const queue = new RoundQueue(3);
queue.add(1);
queue.add(2);
queue.add(3);
const lengthBefore = queue.length;
const result = queue.remove();
const lengthAfter = queue.length;
expect(lengthAfter).to.equal(lengthBefore - 1, "length should decrease by 1");
expect(result).to.equal(1, "first element should the one being removed");
expect(queue.first).to.equal(2, "should shift the second element to the head of the queue");
expect(queue.last).to.equal(3, "should not change the last element");
});
});
Running the tests will once again give us an error:
Now we add some code just to make the test pass:
class RoundLinkedQueue {
// ...
remove() {
const removedElement = this.first;
this._first = this._first.next;
this._length -= 1;
return removedElement;
}
}
The only other use case is when the queue is empty and we try to remove an element from it. When this happens, the queue should throw an exception:
it("Should throw an error when the queue is empty", () => {
const queue = new RoundQueue(3);
expect(() => queue.remove()).to.throw("Cannot remove element from an empty queue");
});
Running the test suite as is:
Adding some conditions to test for emptyness and throw the proper error:
class RoundLinkedQueue {
// ...
remove() {
const removedNode = this._first;
if (!removedNode) {
throw new Error("Cannot remove element from an empty queue");
}
this._first = this._first.next;
this._length -= 1;
return removedNode.data;
}
}
And that's it!
Testing edge cases
There are still some bugs in or code. When we wrote the add method, we included the first and last getters as well. But what happens if we try to access them when the queue is empty? Let's find out! first things first (ba dum tsss!):
describe("When accessing elements", () => {
it("Should throw a proper error when acessing the first element of an empty queue", () => {
const queue = new RoundQueue(3);
expect(() => queue.first).to.throw("Cannot access the first element of an empty queue");
});
});
Running the tests:
Looks like the error message is not really helpful. In fact, it is a little too low level. Let's make it better:
class RoundLinkedQueue {
// ...
get first() {
if (!this._first) {
throw new Error("Cannot access the first element of an empty queue");
}
return this._first.data;
}
// ...
}
Lastly, for the last getter, we will do the same:
it("Should throw a proper error when acessing the last element of an empty queue", () => {
const queue = new RoundQueue(3);
expect(() => queue.last).to.throw("Cannot access the last element of an empty queue");
});
First the failing result:
Then fixing the code:
class RoundLinkedQueue {
// ...
get last() {
if (!this._last) {
throw new Error("Cannot access the last element of an empty queue");
}
return this._last.data;
}
// ...
}
Aaaaaaand that's about it!
Conclusion
I tried to make this a comprehensive introduction to TDD with the Node.js/JavaScript ecosystem. The data structure we had to implement here was intentionally simple so we could follow the methodology as much as possible.
When doing TDD in real world applications, things are usually not so linear. You will find yourself struggling from time to time with the design choices you make while writing your tests. It can be a little frustrating in the beginning, but once you get the gist of it, you will develop a "muscle memory" to avoid the most common pitfalls.
TDD is great, but as almost everything in life, it is not a silver bullet.
Be safe out there!
T-t-th-tha-that's i-is a-a-all f-f-fo-f-folks!
Did you like what you just read? Why don’t you buy me a beer (or a coffee if it is before 5pm 😅) with tippin.me?
Oldest comments (0)