Refactoring Algorithmic Code using a Golden Master Record

Introduction

There are days when I find a piece of code I simply have to refactor. Sometimes because I actually have to for project-related reasons, sometimes because it’s easy to, and sometimes because I just want to. One definition of a nice day is when all these reasons meet.

Enter the Portuguese tax number verification.

For those who don’t know, in most countries the tax number has one or more check digits which are calculated according to some algorithm the country’s legislators think is up for the task. If you have a frontend where customers enter tax numbers, it’s a good first step to actually check the validity of the number according to the check digit in order to provide fast feedback to the user.

Usually I don’t do the research on the algorithms we implement for this myself. Someone else on my team calls someone from the country in the same organization and we code monkeys usually get code snippets, such as this one . In this case I got curious. The portuguese wiki  contains a nice explanation of the check digit algorithm, which is a variation of an algorithm called (according to google) the modulus 11 check digit algorithm.

• Implementing this from scratch probably would have been straightforward, but I decided to refactor for several reasons:
  Sometimes web sources can be wrong. Take, for example, this community wiki : Here they seem to have forgotten about a part of the algorithm. If this had been my first source, I’d have had a bug report. Thus I usually try to stay near the scripts my customers provide me with.
• Refactoring this very isolated piece of code would be easy.
• Sometimes the scripts we get from our colleagues contain a little bit of extra logic which make sense in the context where we use them. In this one, for example, I was told to “just don’t worry about the extra cases at the beginning. We are not interested in these and it’s okay to delete them.”

Side note: For the purposes of this exercise, I used ES6 transpiled with Babel. For my tests, I use mocha and chai.

Enough introduction! Let’s have a look at:

The Code

I admit I did a tiny bit of untested refactoring first: Returning true or false instead of an alert, exporting the function and deleting the, as per our definition unnecessary, lines.

1export function validaContribuinte(contribuinte) {
2// algoritmo de validação do NIF de acordo com
3// http://pt.wikipedia.org/wiki/N%C3%BAmero_de_identifica%C3%A7%C3%A3o_fiscal
4    let comparador;
5    var temErro = 0;
6 
7    var check1 = contribuinte.substr(0, 1) * 9;
8    var check2 = contribuinte.substr(1, 1) * 8;
9    var check3 = contribuinte.substr(2, 1) * 7;
10    var check4 = contribuinte.substr(3, 1) * 6;
11    var check5 = contribuinte.substr(4, 1) * 5;
12    var check6 = contribuinte.substr(5, 1) * 4;
13    var check7 = contribuinte.substr(6, 1) * 3;
14    var check8 = contribuinte.substr(7, 1) * 2;
15 
16    var total = check1 + check2 + check3 + check4 + check5 + check6 + check7 + check8;
17    var divisao = total / 11;
18    var modulo11 = total - parseInt(divisao) * 11;
19    if (modulo11 == 1 || modulo11 == 0) {
20        comparador = 0;
21    } // excepção
22    else {
23        comparador = 11 - modulo11;
24    }
25 
26    var ultimoDigito = contribuinte.substr(8, 1) * 1;
27    if (ultimoDigito != comparador) {
28        temErro = 1;
29    }
30 
31    if (temErro == 1) {
32        return false;
33    }
34    return true;
35}

Where to start

The first thing you want to do when you refactor code is have unit tests for the code. Since most code to refactor is hard to understand, a lot of people prefer to not even try and rather create a Golden Master test. A detailed explanation as well as a walkthrough in Java can be found here .

Creating a Golden Master

So the steps to creating a Golden Master test are:

1.  Create a number of random inputs for your testee
2. Use these inputs to generate a number of outputs
3. Record the inputs and outputs.

Why are we doing this?

If the number of random inputs is high enough, it’s very probable that we have all test cases in there somewhere. If we capture the state of the testee before we start changing anything, we can be sure we won’t break anything later.

There’s one thing I want to say now: A Golden Master record should in most cases be only a temporary solution. You do not really want files or databases full of randomly generated crap to clog your server, and you don’t want long-running tests with way too many redundant test cases on your CI server.

Step 1: Create A Number Of Random Inputs

For this, we have to actually look at the code to be refactored. A quick glance says: “This function takes strings of length 9 which contain only digits as valid input”.

My first instinct was to try and calculate all of them. After a few frustrating minutes which I spent discussing with my computer’s memory, I did a small back-of-an-envelope calculation (16 Bit x 9 x 899999999 > 15 TB). So this turned out to be a Bad Idea™.

The next best thing was to create some random numbers between 100000000 and 99999999. After a bit of experimentation, because I “have no idea of the algorithm” for the purpose of this exercise, I settled on 10000 random fake tax numbers, which corresponded to three seconds overall test runtime on my machine. The code to generate these is wrapped in a testcase for easy access (remember, this is temporary):

1describe('validatePortugueseTaxNumber', () => {
2    describe('goldenMaster', () => {
3        it('should generate a golden master', () => {
4            const gen = random.create('My super Golden Master seed'),
5                expectedResultsAndInputs = [ ...new Array(1000000) ].map(() => {
6                    const input = gen.intBetween(100000000, 999999999),
7                        ...
8                });
9        }).timeout(10000);
10    });
11});

Side note: It is often recommended to use a seedable random generator. Since at that point I was not sure whether I wanted to actually save the inputs or not, I ended up using this PRNG . It’s not strictly necessary for this exercise, though.

Step 2: Use These Inputs To Generate A Number Of Outputs.

Just call the function.

1...
2    const input = gen.intBetween(100000000, 999999999),
3        result = validaContribuinte(input.toString(10));
4 
5        return { input, result };
6...

Step 3: Record The Inputs And Outputs

This also was pretty straightforward. I used the built-in mechanisms of node.js to write the output to a ~3.5MB file.

1fs.writeFileSync('goldenMaster.json', JSON.stringify(expectedResultsAndInputs));

And just like that, a Golden Master was created.

Create a test based on the Golden Master

The next step is to use the Golden Master in a test case. For each input, the corresponding output has to correlate to the file.
My test looks like this:

1it('should always conform to golden master test', () => {
2    const buffer = fs.readFileSync('goldenMaster.json'),
3    data = JSON.parse(buffer);
4 
5    data.map(({ input, result }) => {
6        return expect(validaContribuinte(nextNumber.toString(10))).to.equal(result);
7    });
8}).timeout(10000);

Side note: I stopped running the Golden Master generation every time; even though it would never produce different results unless the seed changed, it would’ve been a waste of resources to run every time.

I ran this a couple of times just for the heck of it. Then I started playing around with the code under test, deleting a line here, changing a number there, until I was confident that my Golden Master was sufficiently capturing all the cases. I encourage you to do this, it’s one of the very few times that you get to be happy about red tests.

I was not really satisfied with the output yet. “expected false to equal true” in which case, exactly? Again, in this simple case it would probably not have been necessary, but sometimes it can be useful to also record the failing input. So, after some refactoring, this happened:

1data.map(expectedResult => {
2    const { input } = expectedResult;
3    const result = validatePortugueseTaxNumber(input.toString(10));
4 
5    return expect({ input, result}).to.deep.equal(expectedResult);
6    });
7}).timeout(10000);

Refactoring

The refactoring itself was pretty straightforward. For the sake of brevity, most of the steps are skipped in this post.
Renaming the function and a few variables:

1export function validatePortugueseTaxNumber(taxNumber) {
2// algoritmo de validação do NIF de acordo com
3// http://pt.wikipedia.org/wiki/N%C3%BAmero_de_identifica%C3%A7%C3%A3o_fiscal
4    let comparator;
5    let checkDigitWrong = 0;
6 
7    const check1 = taxNumber.substr(0, 1) * 9;
8    const check2 = taxNumber.substr(1, 1) * 8;
9    const check3 = taxNumber.substr(2, 1) * 7;
10    const check4 = taxNumber.substr(3, 1) * 6;
11    const check5 = taxNumber.substr(4, 1) * 5;
12    const check6 = taxNumber.substr(5, 1) * 4;
13    const check7 = taxNumber.substr(6, 1) * 3;
14    const check8 = taxNumber.substr(7, 1) * 2;
15 
16    const total = check1 + check2 + check3 + check4 + check5 + check6 + check7 + check8;
17    const divisao = total / 11;
18    const modulo11 = total - parseInt(divisao) * 11;
19    if (modulo11 == 1 || modulo11 == 0) {
20        comparator = 0;
21    }
22    else {
23        comparator = 11 - modulo11;
24    }
25 
26    const ultimoDigito = taxNumber.substr(8, 1) * 1;
27    if (ultimoDigito != comparator) {
28        checkDigitWrong = 1;
29    }
30 
31    if (checkDigitWrong == 1) {
32        return false;
33    }
34    return true;
35}

Simplifying (a lot):

1export function validatePortugueseTaxNumber(taxNumber) {
2    const checkSumMod11 = taxNumber.substr(0,8)
3                                   .split('')
4                                   .map(
5                                       (digit, index) => {
6                                       return parseInt(digit, 10) * (9 - index);
7                                       })
8                                   .reduce((a, b) => a + b) % 11,
9          comparator = checkSumMod11 > 1? 11 - checkSumMod11 : 0;
10 
11    return parseInt(taxNumber.substr(8, 1), 10) === comparator;
12}

This is where I stopped.

Writing unit tests

By now I had a better understanding of what my piece of code did. And, as was said above, it’s a good idea to get rid of a golden master, so the time had come to think about valid test inputs.

Apparently a remainder of 0 and 1 was important. To this, I added the edge case of remainder 10, and some remainder in the middle range just to be sure. As for generating the corresponding inputs, I cheated a little:

1...
2if (checkSumMod11 === 0 && lastDigit === comparator) {
3    console.log(taxNumber);
4}
5...

Using this generator function, I created the final unit tests for the portugueseTaxNumberValidator:

1describe('validatePortugueseTaxNumber', () => {
2    it('should return false for 520363144 (case checkSum % 11 === 0) ', () => {
3        expect(validatePortugueseTaxNumber('520363144')).to.equal(false);
4    });
5 
6    it('should return false for 480073977 (case checkSum % 11 === 1) ', () => {
7        expect(validatePortugueseTaxNumber('480073977')).to.equal(false);
8    });
9 
10    it('should return false for 291932333 (case checkSum % 11 === 2) ', () => {
11        expect(validatePortugueseTaxNumber('291932333')).to.equal(false);
12    });
13 
14    it('should return false for 872711478 (case checkSum % 11 === 10) ', () => {
15        expect(validatePortugueseTaxNumber('872711478')).to.equal(false);
16    });
17 
18    it('should return true for 504917951 (case checkSum % 11 === 0) ', () => {
19        expect(validatePortugueseTaxNumber('523755600')).to.equal(true);
20    });
21 
22    it('should return true for 850769990 (case checkSum % 11 === 2) ', () => {
23        expect(validatePortugueseTaxNumber('998757039')).to.equal(true);
24    });
25 
26    it('should return true for 504917951 (case checkSum % 11 === 10) ', () => {
27        expect(validatePortugueseTaxNumber('504917951')).to.equal(true);
28    });
29});

Conclusion

Creating a Golden Master and using it during refactoring feels like you’re wrapped in a big, fluffy cotton ball. If the Golden Master record is detailed enough, nothing can go wrong. Or rather, if it does, you will notice in an instant. There are no qualms about deleting code, replacing it with something you think will do the same, because it’s a safe experiment. It was a fun exercise and I would do it again in an instant.