20160501

How to untangle a commit

To untangle a commit you have incrementally to 1) commit, 2) stash save, 3) test, 4) commit fix (optional), 5) revert fix (optional) and 6) stash apply.

Every now and then you have a commit that is 100% working and following your quality standards, but it is simply to big to be consumed in one code review. What you need to do is to break it up in multiple commits.

You can just to do that with git in a safe way and with reasonable afford using some git yoga. The process is pretty much like swapping a carpet with a sofa on it.

Let's start a session with three files a, b and c.

$ cd $(mktemp -d)
$ git init
Initialized empty Git repository in /tmp/tmp.a1UbQEZsn2/.git/
$ git checkout -b initial
Switched to a new branch 'initial'
$ git commit --allow-empty -m"Initial" 
$ git checkout -b big_one
$ echo "a" > a
$ echo "b" > b
$ echo "c" > c
$ git add a b c
$ git commit -m"the big one"
[big_one 35beda3] the big one
 3 files changed, 3 insertions(+)
 create mode 100644 a
 create mode 100644 b
 create mode 100644 c
We added a, b and c. This is the state we consider too large for one code review. Let's go back to the initial state with files a, b and c unstaged:

$ git checkout initial
$ git cherry-pick --no-commit big_one
$ git reset HEAD
$ git status
On branch initial
Untracked files:
  (use "git add file..." to include in what will be committed)

 a
 b
 c
We want to add a, b and c in three separate commits we can send out as three independent code reviews.

The overall process is simple for the happy case. Add a file and commit it. We use stash to clean the workspace. Then we check if the latest commit was successful. The example uses bash conditions as a check. This feedback would normally come from your test suite.

$ git checkout -b a
Switched to a new branch 'a'
$ git add a
$ git commit -m"a"
[a b73878a] a
 1 file changed, 1 insertion(+)
 create mode 100644 a
$ git stash save -u stash_b_c
Saved working directory and index state On a: stash_b_c
HEAD is now at b73878a a
$ [ -f a ] && [ ! -f b ] && [ ! -f c ] && echo Well done # we run a test
Well done


$ git stash apply
On branch a
Untracked files:
  (use "git add file..." to include in what will be committed)

 b
 c
$ git checkout -b b
Switched to a new branch 'b'
$ git add b
$ git commit -m"b"
[b 64fac68] b
 1 file changed, 1 insertion(+)
 create mode 100644 b
$ git stash save -u stash_c
Saved working directory and index state On b: stash_c
HEAD is now at 64fac68 b
$ [ -f a ] && [ -f b ] && [ ! -f c ] && echo Well done # we run a test
Well done

$ git stash apply
On branch b
Untracked files:
  (use "git add file..." to include in what will be committed)
 c
$ git checkout -b c
Switched to a new branch 'c'
$ git add c
$ git commit -m"c"
[c 2f66c1b] c
 1 file changed, 1 insertion(+)
 create mode 100644 c
$ [ -f a ] && [ -f b ] && [ -f c ] && echo Well done # we run a test
Well done
When we diff with big_one they have the same content:
$ git diff big_one && echo Passed
Passed
The stash is the trail of changes we made, when we "removed" files from the working directory temporarily.

$ git stash list
stash@{0}: On b: stash_c
stash@{1}: On a: stash_b_c
For now we only used stash to clean the working directory to be able to commit and to restore those files after commit. By using git stash apply we keep the trail of changes.

If you're trying this with real code it won't be so simple. Things will go wrong. We forgot to add files to a commit and our tests might start failing. We have to be able to backtrack and restore previous state. We never want to lose work.

Using stash we can do all this safely and methodically. Let's go back to the initial state with the big_one branch containing all changes and the files a, b, and c as untracked changes.

$ cd $(mktemp -d)
$ git init
$ git checkout -b initial
$ git commit --allow-empty -m"Initial" 
$ git checkout -b big_one
$ echo "a" > a
$ echo "b" > b
$ echo "c" > c
$ git add a b c
$ git commit -m"the big one"
$ git checkout initial
$ git cherry-pick --no-commit big_one
$ git reset HEAD

$ git status 
On branch initial
Untracked files:
  (use "git add file..." to include in what will be committed)

 a
 b
 c
In this session we make the error of adding a and b in the first commit, when we actually only should add a.

$ git checkout -b a
Switched to a new branch 'a'
$ git add a 
$ git add b                                  # b - problem to fix 
$ git commit -m"Adding a (actually also b)"
[a c604de5] Adding a (actually also b)
 2 files changed, 2 insertions(+)
 create mode 100644 a
 create mode 100644 b
$ git stash save -u stash_c
Saved working directory and index state On a: stash_c
HEAD is now at 5d031e6 Adding a (actually also b)
$ [ -f a ] && [ ! -f b ] && [ ! -f c ] && echo Well done || echo Error # we run a test
Error
The tests fails now. We have to remove b, then the test passes.

$ git rm b                                               # remove b
$ git commit -m"Remove b"
[a 043f3a7] Remove b
 1 file changed, 1 deletion(-)
 delete mode 100644 b
$ [ -f a ] && [ ! -f b ] && [ ! -f c ] && echo Well done || echo Error # we run a test
Well done
The branch a has the right state now - only the file a, but the stashed change only contains c. We lost b.

How can we recover from this state if the desired state is a subset of changes from the branch and the last stashed changes? We need some git yoga to get where we want.

We added a and b in the first commit and removed b in the second commit. Together both commits leave only a and pass the test. This is the valid state we want for branch a.

The stash contains only c, so we have to restore b. We do this by reverting the state before we removed b. This is the state of the working directory when the change was stashed. Then we apply the latest change from on the stash which is c. The result is that we have a, b and c ((a + b) – b + b + c = a + b + c) in the working directory. The file a is committed. The files b and c are uncommitted changes.

 
$ git revert --no-commit HEAD                            # restore b
$ git stash apply                                        # b & c
On branch a

Changes to be committed:
  (use "git reset HEAD file..." to unstage)

 new file:   b

Untracked files:
  (use "git add file..." to include in what will be committed)

 c
When we look at the history of branch a, it's not exactly the result we wanted. The branch a now contains two commits. We squash those to one commit.

$ git stash
Saved working directory and index state WIP on a: 043f3a7 Remove b
HEAD is now at 043f3a7 Remove b
$ git reset --soft HEAD~
$ git commit --amend -m"Add a for real"
[a bd012df] Add a for real
 1 file changed, 1 insertion(+)
 create mode 100644 a
$ git stash apply
On branch a
Changes to be committed:
  (use "git reset HEAD file..." to unstage)

 new file:   b

Untracked files:
  (use "git add file..." to include in what will be committed)

 c

The squashing is optimal and be done later using a interactive rebase git rebase -i initial for the branch a. From here we can commit b and c separately just as in the happy case before. This gives us the same result:

$ git stash apply
$ git checkout -b b
$ git add b
$ git commit -m"b"
$ git stash save -u stash_c
$ [ -f a ] && [ -f b ] && [ ! -f c ] && echo Well done # we run a test
Well done

$ git stash apply
$ git checkout -b c
$ git add c
$ git commit -m"c"
$ [ -f a ] && [ -f b ] && [ -f c ] && echo Well done # we run a test
Well done

$ git diff big_one && echo Passed
Passed
With stash we can keep safe-points of our changes, clean and restore the working directory. We also use it together with git revert to undo changes.

This process is also applicable to save results from explorative coding. If I hack together a solution end-to-end to see that it's actually works, I can keep those results. I rebuild it then cleanly from the ground and at the same time make sure that the overall end-to-end solution works. This gives you the quick feedback for the exploration, end-to-end testing and quality of actually building it incrementally with the quality you want. It's the best of both worlds.

In a real world scenario the untangling isn't that rigid with strictly adding a, b and c in single commits, such that the the sum of all incremental commits is strictly the same as the big initial commit. Most of the time you will see small problems on the way you want to address in the process. It's strictly speaking less safe because now diffing isn't a simple binary result any more, but it allows a more fluid more workflow. If you're uncomfortable with that you can also split the results in n commits first, keep notes of the necessary changes, and add the fixes in separate commits later (on the branches a, b and c).

In the given session the result are the branches initial, a, b, c that build on each other in this order. We can still improve on that. If you observe that a, b, c are actually orthogonal then the can rebase b, c on the initial branch. This makes the review work parallelizable. Not all features are orthogal. If you have two different ways to cut a commit you should choose the one that makes the changes as independent as possible. This also makes rebasing and merging easier.
$ git log --pretty=oneline --patch a --
bd012df01c7889182c6295725faf942f90fa251e Add a for real
diff --git a/a b/a
new file mode 100644
index 0000000..7898192
--- /dev/null
+++ b/a
@@ -0,0 +1 @@
+a
7a358aa4a6c6d4cb52cc403c3cc7d3b59c208c70 Initial

$ git checkout initial
$ git checkout -b b_orthogonal
$ git cherry-pick b
$ git log --pretty=oneline --patch b_orthogonal
006022af90003f57bde0ad2700201aee73163b95 b
diff --git a/b b/b
new file mode 100644
index 0000000..6178079
--- /dev/null
+++ b/b
@@ -0,0 +1 @@
+b
7a358aa4a6c6d4cb52cc403c3cc7d3b59c208c70 Initial

$ git checkout initial
$ git checkout -b c_orthogonal
$ git cherry-pick c

$ git log --pretty=oneline --patch c_orthogonal
43a58337baf1e337f0ff1fae72c2c5b955874027 c
diff --git a/c b/c
new file mode 100644
index 0000000..f2ad6c7
--- /dev/null
+++ b/c
@@ -0,0 +1 @@
+c
7a358aa4a6c6d4cb52cc403c3cc7d3b59c208c70 Initial
The overall process isn't trivial, but once you know the necessary bits of git (stash, revert, checkout, commit, branch) it should be fairly easy to remember that the only steps necessary are to 1) commit, 2) stash save, 3) test, 4) commit fix (optional), 5) revert fix (optional) and 6) stash apply. If you can keep that in your head you know one solution to this problem.

20160430

Revert 2016 edition

Five years ago I wrote about how reverting can speed you up. The main argument is that retrying to go from a new broken state to a new good state can be incredibly hard. The problem is that you did too many steps and you don't know which of the steps actually broke your system.

My experience is that it is hard for people to let go and try a new start. I always see more of a positive edge. You still know all the things you learnt in the process. Making smaller steps will give you predictable progress. Carrying on might lead to nothing. It is high risk.

I'm reverting more on the enjoyable work days. I did something I didn't know yet how it would work out. I learnt something: it doesn't work this way and the problem is a bit more challenging than I though initially. Failures are the most interesting bits of information. I remember my failures way more vividly than the stuff that actually worked. Digesting failures fully gives you lots of information and an opportunity to grow.

I don't like to arrive on a development battle field with corpses all over the place. There are twenty different changes you made from the last good state - all potentially breaking - and now I should find the one line change that broke it all. I want to see how we got from the pristine state of goodness to this. This is the safe approach. Every developer should be able to minimize the breaking change. It's fine to not know the solution for this minimal problem. This is where the investigation starts.

The easiest way to go from a broken state to a good state is to undo all your changes. Go to the known good state and make smaller steps from there.

With git this all became cheaper and safer. The main tools are git add and git stash.

If you're making progress and everything works like it should you can do git add -A between all good states to stage them. Using staged changes is a lightweight way to safe your work. It's the right tool if the change is not big enough that commit is worth it.

In example I'll use bash conditional expressions as a stand-in for a test suite. It tests the presents or absence of a file.

We start with an initial commit that we know works:
$ cd $(mktemp -d)
$ git init
Initialized empty Git repository
$ echo a > a
$ [ -f a ] && echo works || echo broken # run test
works
$ git add -A
$ git commit -m'working'
[master (root-commit) 263f908] working
 1 file changed, 1 insertion(+)
 create mode 100644 a
Now we can change the source, run our test and use add to stage the change.

$ echo -n b > a
$ [ "$(cat a)" == "b" ] && echo works || echo broken #run test
works
$ git add -A
Then we can do another change, find out that it was breaking the test and revert back by checking out the change we staged.

$ echo -n c > a
$ [ "$(cat a)" == "b" ] && echo works || echo broken #run test
broken
$ git checkout a
$ [ "$(cat a)" == "b" ] && echo works || echo broken #run test
works
We can repeat git add until we are ready to commit. This process adds minimum overhead.

Using git stash we make safe points on the way. This will help recover if something went wrong in the process, for example if we recovered to the wrong intermediate state.

The same session with some safe points added.
$ cd $(mktemp -d)
$ git init
$ echo a > a
$ [ -f a ] && echo works || echo broken # run test
$ git add -A
$ git commit -m'working'

$ echo -n b > a
$ [ "$(cat a)" == "b" ] && echo works || echo broken #run test
works
$ git add -A

$ echo -n c > a
$ [ "$(cat a)" == "b" ] && echo works || echo broken #run test
broken
$ git stash
Saved working directory and index state WIP on master: df9056f working
HEAD is now at df9056f working

$ # Oh, no the test was actually wrong!
$ [ "$(cat a)" == "c" ] && echo works || echo broken #run test
broken

$ git stash apply
On branch master
Changes not staged for commit:
  (use "git add file..." to update what will be committed)
  (use "git checkout -- file..." to discard changes in working directory)

 modified:   a

no changes added to commit (use "git add" and/or "git commit -a")

$ [ "$(cat a)" == "c" ] && echo works || echo broken #run test
works
$ git add -A
$ git commit -m"working again"
[master 3faee04] working again
 1 file changed, 1 insertion(+), 1 deletion(-)
I'd advise to not use stash pop. Apply leaves the safe points in case you tried to applied the stash incorrectly. You can always recover from all your safe points starting from the last commit and you will never lose work. They can be safely discarded once you reached a git commit.

A process with more overhead but similar results is to use git add, git commit, git revert and git rebase -i. You use commit regularly between states and you revert bad states. Finally you squash with git rebase -i to have a clean history. Depending on your preference this process or stash is the better choice. Try both and you'll see which one is the appropriate for your situation.

Coming back to the old post about reverting, git stash is the cheapest way to clean a workspace. You can fire away git stash left and right. If you were wrong you can always go back and scavenge the bits of the changes that were important after all. Given these tools the overall process got massively better.

20130527

Speed-up your project build without the tmpfs hassle

Running all tests in my current project takes some time. With 26 GB of free memory, why not use it for something useful? tmpfs is one way to speed up the test execution by keeping a complete file system in memory.

The problem with tmpfs is that it's only kept in memory. You have to setup the scripts yourself to flush content back to disk. These scripts should better work perfect, otherwise you'll loose parts of your work.

A common approach is to work directly in a tmpfs folder and backup your work to a folder on disk. When your machine is booting you restore the tmpfs folder from this backup folder. Once booted cron is used to synch the tmpfs folder and disk folder.

I found this setup a bit complicated and error prone. I never really trusted my own setup on boot time and with cron. Now I use a much simpler setup that is not using cron at all.

The performance on my machine running a single test, using the IDE and deploying in a web server was always reasonable. Just running all tests takes to much time.

The sweet spot I found is to setup a workspace on disk, sync to tmpfs under /dev/shm and run all tests there. This keeps my setup more or less unchanged and removes the possibility to loose work just because I'm too dump to setup things correctly.

The resulting performance increase is reasonable:

$ nosetests && run_tests.py
........................................................................................................................................................................................................................................................
----------------------------------------------------------------------
Ran 248 tests in 107.070s

OK
........................................................................................................................................................................................................................................................
----------------------------------------------------------------------
Ran 248 tests in 19.423s

OK

It's now five times faster than before.

With python the setup the setup is quite simple:

#!/bin/bash -e

WORK=src/py
LOG=$(pwd)/test.log
TARGET=$(hg root)
SHADOW=/dev/shm/shadow/$TARGET

date > $LOG
mkdir -p $SHADOW

cd $SHADOW
rsync --update --delete --exclude=".*" --exclude=ENV --archive $TARGET ./..

if [ ! -d ENV ]
then
    virtualenv ENV
fi
. ENV/bin/activate

cd $WORK
python setup.py develop >> $LOG
nosetests $* | tee -a $LOG
exit ${PIPESTATUS[0]}

I'm just resyncing into a /dev/shm folder, setup the test environment there (virtualenv and python setup.py) and run the tests (nosetests).

It's is still possible to run single tests from the command line on the tmpfs folder. It's also possible to kick this off from your IDE but you'll loose your test runner and debugging capabilities. As I sad earlier I don't need these right now.

I hope my little twist with tmpfs helps with setting up a faster development environment without all the scripting hassle.

20130501

How to use the Mercurial Rebase extension to collapse and move change sets

Every now and then I like to combine change sets to one change set. You can do this with the rebase extension. I will show you how rebase works with some examples.

The other mayor use case for the rebase extension is to keep the history of your mercurial linear when working with a team of developers. The extension gets its name from this use case: changing the parent change set of your changes to another change set (often the tip). As long as every developer uses pull, rebase, push the history is free of merge change sets.

I setup a repository with three change sets.

hg init repo
cd repo

echo a > a
hg commit -A -m"add a"
ID_A=$(hg id -n)

echo b > b
hg commit -A -m"add b"
ID_B=$(hg id -n)

echo c > c
hg commit -A -m"add c"
ID_C=$(hg id -n)

hg version | head -n 1 ; echo
hg glog --patch

Mercurial Distributed SCM (version 2.5.4)

@  changeset:   2:aa77f078beed
|  tag:         tip
|  user:        blob79
|  date:        Wed May 01 12:14:27 2013 +0200
|  summary:     add c
|
|  diff -r a692ab61aad8 -r aa77f078beed c
|  --- /dev/null        Thu Jan 01 00:00:00 1970 +0000
|  +++ b/c      Wed May 01 12:14:27 2013 +0200
|  @@ -0,0 +1,1 @@
|  +c
|
o  changeset:   1:a692ab61aad8
|  user:        blob79
|  date:        Wed May 01 12:14:27 2013 +0200
|  summary:     add b
|
|  diff -r e31426a230b0 -r a692ab61aad8 b
|  --- /dev/null        Thu Jan 01 00:00:00 1970 +0000
|  +++ b/b      Wed May 01 12:14:27 2013 +0200
|  @@ -0,0 +1,1 @@
|  +b
|
o  changeset:   0:e31426a230b0
   user:        blob79
   date:        Wed May 01 12:14:27 2013 +0200
   summary:     add a

   diff -r 000000000000 -r e31426a230b0 a
   --- /dev/null        Thu Jan 01 00:00:00 1970 +0000
   +++ b/a      Wed May 01 12:14:27 2013 +0200
   @@ -0,0 +1,1 @@
   +a

After the collapsing the change sets $ID_B and $ID_C a new change set is in the history containing changes of both. This change set can then be pulled or imported as one unit making the history of the repository a bit easier to read.

hg rebase --collapse --source $ID_B --dest $ID_A -m"collapse change sets"
hg glog --patch

saved backup bundle to /home/thomas/Desktop/rebaseblob/repo/.hg/strip-backup/a692ab61aad8-backup.hg
@  changeset:   1:bb2e0cde315f
|  tag:         tip
|  user:        blob79
|  date:        Wed May 01 12:14:28 2013 +0200
|  summary:     collapse change sets
|
|  diff -r e31426a230b0 -r bb2e0cde315f b
|  --- /dev/null        Thu Jan 01 00:00:00 1970 +0000
|  +++ b/b      Wed May 01 12:14:28 2013 +0200
|  @@ -0,0 +1,1 @@
|  +b
|  diff -r e31426a230b0 -r bb2e0cde315f c
|  --- /dev/null        Thu Jan 01 00:00:00 1970 +0000
|  +++ b/c      Wed May 01 12:14:28 2013 +0200
|  @@ -0,0 +1,1 @@
|  +c
|
o  changeset:   0:e31426a230b0
   user:        blob79
   date:        Wed May 01 12:14:27 2013 +0200
   summary:     add a

   diff -r 000000000000 -r e31426a230b0 a
   --- /dev/null        Thu Jan 01 00:00:00 1970 +0000
   +++ b/a      Wed May 01 12:14:27 2013 +0200
   @@ -0,0 +1,1 @@
   +a

If you have to keep the change sets because they were already published, you can also keep the old change sets adding the new collapsed change set as a separate branch.

hg rebase --keep --collapse --source $ID_B --dest $ID_A -m"collapse change sets"
hg glog

@  changeset:   3:0fa31b1ebcf1
|  tag:         tip
|  parent:      0:448200734313
|  user:        blob79
|  date:        Wed May 01 12:14:28 2013 +0200
|  summary:     collapse change sets
|
| o  changeset:   2:0a6400bebe21
| |  user:        blob79
| |  date:        Wed May 01 12:14:28 2013 +0200
| |  summary:     add c
| |
| o  changeset:   1:a93228700dc1
|/   user:        blob79
|    date:        Wed May 01 12:14:28 2013 +0200
|    summary:     add b
|
o  changeset:   0:448200734313
   user:        blob79
   date:        Wed May 01 12:14:28 2013 +0200
   summary:     add a


hg log -r "::tip" --patch

changeset:   0:448200734313
user:        blob79
date:        Wed May 01 12:14:28 2013 +0200
summary:     add a

diff -r 000000000000 -r 448200734313 a
--- /dev/null   Thu Jan 01 00:00:00 1970 +0000
+++ b/a Wed May 01 12:14:28 2013 +0200
@@ -0,0 +1,1 @@
+a

changeset:   3:0fa31b1ebcf1
tag:         tip
parent:      0:448200734313
user:        blob79
date:        Wed May 01 12:14:28 2013 +0200
summary:     collapse change sets

diff -r 448200734313 -r 0fa31b1ebcf1 b
--- /dev/null   Thu Jan 01 00:00:00 1970 +0000
+++ b/b Wed May 01 12:14:28 2013 +0200
@@ -0,0 +1,1 @@
+b
diff -r 448200734313 -r 0fa31b1ebcf1 c
--- /dev/null   Thu Jan 01 00:00:00 1970 +0000
+++ b/c Wed May 01 12:14:28 2013 +0200
@@ -0,0 +1,1 @@
+c

As I already mentioned you can use the rebase extension to move change sets around. A small exercise is to change the order of two change sets. With the same setup of three change sets as in the collapse example before, we move the changes from the initial change set $ID_C before the changes made in change set $ID_B.

hg rebase --source $ID_C --dest $ID_A
hg rebase --source $ID_B --dest tip

@  changeset:   2:673889b80c51
|  tag:         tip
|  user:        blob79
|  date:        Wed May 01 12:14:29 2013 +0200
|  files:       b
|  description:
|  add b
|
|
o  changeset:   1:175e0515be8b
|  user:        blob79
|  date:        Wed May 01 12:14:29 2013 +0200
|  files:       c
|  description:
|  add c
|
|
o  changeset:   0:16ef477c54cb
   user:        blob79
   date:        Wed May 01 12:14:29 2013 +0200
   files:       a
   description:
   add a


A nice exercise for the reader is to extend the example to fourth change set. This change set is the tip of the repository as a child of change set $ID_C. After the change set move it should be the child of the change set $ID_B.

In real world repositories changes are not fully independent, so while rebasing you have to resolve conflicts, but this another blog post for another day.

20130423

Mini-Quickcheck for Python

I wanted an implementation of a mini-Quickcheck in Python. This is the API I came up with. It is also a good way to see what’s at the heart of Quicheck: generators.

I cut every corner I could. Some methods are not random, but this can be easily fixed.

There is a runner decorator (dependent on the decorator library) than run’s test methods repeatedly.

import random

def oneof(*values):
    return random.choice(values)

def optional(param):
    return oneof(None, param)

def boolean():
    return oneof(True, False)

def integer(min=0,max=1<<30):
    return random.randint(min,max)

def char():
    return chr(integer(min=2,max=ord('z')))

def string(min=0):
    return "".join([char() for _ in xrange(integer(min=min, max=10))])

def nonempty_string():
    return string(min=1)

def substring(string):
    if not string:
           return string
    start = integer(0, len(string) - 1)
    end = start + integer(len(string) - start)
    return string[start:end]

def date():
    return datetime.date.today()

def subset(*vs):
    return [e for e in vs if boolean()]

def list(gen):
    return [gen() for _ in xrange(integer(max=5))]
    
@decorator
def runner(func, *args, **kwargs):
    for r in xrange(4):
        test_instance = args[0]

About

My blog did not have an about page for years. Now that blogs get out of fashion I can get one as well, as the chances that someone actually reads it diminishes.

Having an about page is nice for everybody involved. There is a nice personal touch to the site full of otherwise dry articles. This is also the space where a blogger can do some navel-gazing and bragging: a nice photo from a place I was you were not, I can tell you what a great company I work for and what an amazingly smart guy I am.

The problem is: I like to stay at home most of the time, I work for a normal company and I'm definitely not smart. (My best trait is productive laziness.)

If you read this far the one thing you should consider is becoming an organ donor. You won't mind. You may help somebody in a lot of trouble. At least I tried! Maybe you like to read a bit about organ donation...


(The fact that I wrote this after reading an about page is a mere coincidence. You should not ask somebody who they are. It's probably the worst question possible.)

20121219

Analogous function testing

For a long time I wanted to write about a testing technique I call analogous function testing. Some time ago I already wrote about the inverse function test pattern and the analogous function testing pattern is mentioned in my piece about functional hash functions.

Instead of describing some synthetic examples I can now present the pattern with a real world example. I wrote tests for a Java port of a small C library. The phonet library returns the same string for words with the same pronunciation in German. In this way it’s similar to the Soundex and Metaphone algorithms in English.

The test, I’m going to present, found bugs in the Java port. More surprisingly it also found bugs in the C library (that’s more than 10 years old) and the JNI-bridge code we used for years.

If you have a look at the C code you’ll find out that it is not trivial. Well, that’s the most polite way to say that it’s devilish hard to read. It’s beyond my means to read a code that initializes 10 static variables and has 26 automatic variables in the main function. It’s not obvious how you can port this code to Java. Luckily, there was already a Java port that is more or less analogous to the C code - it’s not very idiomatic Java.

My goal was to fix the port. I ignored performance and maintainability issues.

How who you figure out that the quite complex function behaves the same way in the original and the ported version?

The trivial test approach to explicit check values is costly and it’s hard to get good code coverage.

assertEquals("a", phonet("a"));

This way you need a lot of test code before you get some coverage. Line and branch coverage might be easy to attain, but the phonet library has 200+ rules that are evaluated by precedence. Now are we going to write x * 200 tests to check that the right values are returned? If we check all rules there are still all characters left that have to be processed consistently. When we are done with that phonet rules could change and we have to redo some of them. Not very exciting.

The trivial test approach is simply too expensive (and boring). Let’s try another approach that reduces our work to one line of code: write the test as an analogous function test.

The analogous test ensures that f(x) = g(x) for all x. f(x) is the C version and g(x) is the Java version. The only thing left is to generate x and see if f(x) == g(x) holds.

That’s the single line of code we have to write to get the test coverage. Okay, we have to write one line to check that f(x) = g(x) and some code to generate x. It all boils down to comparing the output of the C and the Java versions.

assertEquals(in, cPhonet.phonet(in), jphonet.code(in));

Unfortunately, we cannot create all values with brute force. The challenge is to find ways to generate the right input values and the quality of the test depends on the generated input values. I wrote the same test with multiple approaches each and every one useful for a facet of input values:
  • There’s a Quickcheck-based random generator test for large input
  • There’s a test with German dictionaries of known values
  • There’s a exhaustive test that generates all possible values up to a certain (small) size
As an example I’ll show you the exhaustive test for small strings. It uses Permutation.kPermutationWithRepetition(all, STRING_ADD, size) to create an Iterable that returns all permutations of size k from a set of input values with repetition of values (i.e. for the input AB and the size k = 2 it generates AA, AB, BA, BB).
@Test public void phonetDefinedCharacters() {
    Coder jphonet = createCoder();
    CPhonet cPhonet = new CPhonet();

    for (int size = 1; size <= 2; size++) {
        for (String in : kPermutationWithRepetition(
                CharEncoding.allChars(), STRING_ADD, size)) {
            assertEquals(in, cPhonet.phonet(in, rules()), jphonet.code(in));
        }
    }
}

You can have a look at the full implementation in the CPhonetVsPhonetikTest class.

As you can see from the test code the idea is simple. Following this approach will not guarantee 100% test coverage as long as you cannot generate all values. The hard part is to come up with the right test data. A pure Quickcheck-based approach is a good start, but might need to run too long to find critical bugs and additional tests are necessary.

Porting is only one class of tests to use the analogous function testing for. Another class are tests where you already have a simple implementation. You are able to verify the correctness of the simple code easily. The simple implementation is then used to test the harder implementation (with preferable non-functional characteristics).  It might be a good approach if you do not trust a piece of code, but you’re unable to read all of the source code. Just check it against a simple implementation.

A blind spot of an analogous function test is that bugs in f(x) and g(x) can mask each other. If you implement the same bug in both versions the test will not indicate the problem.

The moral from this story is that black-box tests with generated values can be a valuable tool besides classical tests and code reviews - but as everything in life it’s not perfect. It’s only one tool. Quality is still expensive.