Background

• The outer-most list represents “rows”. It collects all objects found. It has zero or more entries.
• The inner-most list represents a single field. It is a key value pair. It is a list of size 2. The first entry is the name of the field (column to FitNesse). The second field is the value. Both are strings.
• The middle list represents a single object. It is a collection of fields. It has zero or more entires.

I understand the need for this representation and it takes a little bit to get it built correctly. So much so, I built a simple tool to do it in java.

C++ is no different. In fact, the authors of cslim though the same thing and they created a C Abstract Data Type to help out (and an add-on method to create the correct final form):

• SlimList
• SlimList_Serializer

They use C because it can be used by both C and C++. I’m using C++ and I wanted to make building query results even easier, so I built a QueryResultAccumulator. The most recent source is in the previous blog and I’ll be putting it on github after I’ve had some more time to work on it.

Here’s the progression to my QueryResultAccumulator class:

• Wrote a Query-Table based fixture and followed the example provided with cslim (thank you for that!)
• Moved the code from functions into methods on a class
• Extracted a class, called SlimListWrapper, which made the fixture code easier to follow.
• Went to get takeout and realized that I had named the class incorrectly and that it was really accumulating query results (thus the name). The SlimList was a mechanism, not an intent.
• Refactored the class into QueryResultAccumulator (I left the original alone, created a new class, copied code from one to the other and changed it around a bit.

Now it might sound like I didn’t have any tests. In fact, I did. I had my original Acceptance Test in FitNesse. I kept running that, so in a sense I was practicing ATDD.

I was not happy with that, because I was not sure that I had properly handled memory allocation correctly. In fact, I had not. The final result is dynamically allocated and I was not releasing that. So I “fixed” it. (It needs to be released after the return from slim back to FitNesse, so the typical pattern is to lazily delete it, or release it in a “destroy” method called after the execution of a single table.)

I have a memory leak?!

TEST(QueryResultAccumulator, CanProduceFinalResultsMultipleTimes) {
    QueryResultAccumulator accumulator;
    accumulator.produceFinalResults();
    accumulator.produceFinalResults();
}

This caused a memory leak of 60 bytes. It was at this point I was up too late and banging my head against a wall. About 3 hours later I figured that out and went to bed. I fixed the problem and sent a patch to authors of cslim in maybe 45 minutes. So I should have gotten more sleep.

Where is that damn thing

  if(result)
    free(result);

This was the correct thing, but it was in the wrong location. Again, this was related to a preprocessor seam in cslim.

Eureka!

cslim depends on CppUTest and uses a different malloc/free

Ah ha! That’s it. So I tired to recompile my C++ code to use the same thing. However, I was not able to do that. CppUTest’s memory tracking implementation does not work with many of the C++ standard classes like <string> and <vector>. So I could not compile my code using the same approach.

I’m glad this happened becuase it made me realize that it was the wrong place anyway. Here’s the logic:

• CSlim has a preprocessor seam, comile with or without -Dfree=cpputest_free, -Dmalloc=cpputest_malloc
• I’m using a class in cslim to do the allocation, where the policy of allocation is stored
• I should not release the memory but instead allow the cslim library to release the memory becaue it has the allocation policy, and therefore the release policy.

cslim/include/CSlim/SlimListSerializer.h:

void SlimList_Release(char *serializedResults);

cslim/src/CSlim/SlimListSerializer.c:

void SlimList_Release(char *serializedResults)
{
  if(serializedResults)
    free(serializedResults);
}

I updated my QueryResultAccumulator to use SlimList_Release and my false positive disappeared.

It also turns out that this improved symmetry in the library. To allocate and release entries in an SlimList you use the following functions:

• SlimList* SlimList_Create()
• void SlimList_Destroy(SlimList*);

Now to serlalize a list and release the memory later you use:

• SlimList_Serialize
• SlimList_Release

As I write this, I think there’s a better name. I’ll let the authors give it a better name (like SlimList_Release_Serialization_Results). But in any case, if you use a function in the cslim library that allocates something, you use another method in the cslim library to release it.

Since the libray has a preprocessor seam, that symmetry removes a false-positive memory leak.

What took so long?

When I called free in the unit test, it was calling the correct version of free, cpputest_free, becasue it was a unit test using CppUTest. When I moved the code into the class, which has no knowledge of CppUTest (nor can it), the flow of the code was correct, but the compilation (preprocessor symbols) were different and it caused a false positive.

Since I changed the code, I assumed it was a problem with how I changed the code. To me more clear, I though it was a code-flow problem, not a preprocessor seam problem. So I spent a lot of time verifyig my code. Once I determined it was correct, I then moved into debugger mode.

It was not long after that when I finally figured out what was going on.

Conslusions

That cslim depends on CppUTest might be questionable. However, if I treat cslim as a (mostly) black box, and I don’t know its allocation policy, I should not assume a deallocation policy.

By putting the responsiblity in the correct library level, it fixed the problem and added symmetry to the overall solution.

I also really enjoyed this (after it was done). I’ve come across memory leaks using CppUTest in the past. Often they were my fault. Sometimes they were not. This was interesting because it both was and was not my fault. I originally had written the code incorrectly. When I put he correct steps in my code, I still had wrong code because I put the responsibility in the wrong place. It really was only correct after I moved the actual implementation into the library and then called it from my code that I had finally written it correctly.

I’m still trying different forms to figure out what I like the best.

By the way, that lastValue stuff in the fixtures has to do with the fact that all of the hook methods return a char* but I’m responsible for cleaning up after myself.

A Decision Table

!|ExecuteBinaryOperator    |
|lhs|rhs|operator|expected?|
|3  |4  |-       |-1       |
|5  |6  |*       |30       |

And Its Fixture Code

#include <stdlib.h>
#include <stdio.h>
#include <string>
#include "RpnCalculator.h"
#include "OperationFactory.h"
#include "Fixtures.h"
#include "SlimUtils.h"

struct ExecuteBinaryOperator {
    ExecuteBinaryOperator() {
        lastValue[0] = 0;
    }

    int execute() {
        RpnCalculator calculator(factory);
        calculator.enterNumber(lhs);
        calculator.enterNumber(rhs);
        calculator.executeOperator(op);
        return calculator.getX();
    }

    static ExecuteBinaryOperator* From(void *fixtureStorage) {
        return reinterpret_cast<ExecuteBinaryOperator*>(fixtureStorage);
    }

    OperationFactory factory;
    int lhs;
    int rhs;
    std::string op;
    char lastValue[32];
};

extern "C" {
void* ExecuteBinaryOperator_Create(StatementExecutor* errorHandler, SlimList* args) {
    return new ExecuteBinaryOperator;
}

void ExecuteBinaryOperator_Destroy(void* self) {
    delete ExecuteBinaryOperator::From(self);
}

static char* setLhs(void* fixture, SlimList* args) {
    ExecuteBinaryOperator *self = ExecuteBinaryOperator::From(fixture);
    self->lhs = getFirstInt(args);
    return self->lastValue;
}

static char* setRhs(void* fixture, SlimList* args) {
    ExecuteBinaryOperator *self = ExecuteBinaryOperator::From(fixture);
    self->rhs = getFirstInt(args);
    return self->lastValue;
}

static char* setOperator(void *fixture, SlimList* args) {
    ExecuteBinaryOperator *self = ExecuteBinaryOperator::From(fixture);
    self->op = getFirstString(args);
    return self->lastValue;
}
static char* expected(void* fixture, SlimList* args) {
    ExecuteBinaryOperator *self = ExecuteBinaryOperator::From(fixture);
    int result = self->execute();
    snprintf(self->lastValue, sizeof(self->lastValue), "%d", result);
    return self->lastValue;
}

SLIM_CREATE_FIXTURE(ExecuteBinaryOperator)
    SLIM_FUNCTION(setLhs)
    SLIM_FUNCTION(setRhs)
    SLIM_FUNCTION(setOperator)
    SLIM_FUNCTION(expected)
SLIM_END

}

A Script Table

!|script           |ProgramTheCalculator                   |
|startProgramCalled|primeFactorsOfSum                      |
|addOperation      |sum                                    |
|addOperation      |primeFactors                           |
|saveProgram                                               |
|enter             |4                                      |
|enter             |13                                     |
|enter             |7                                      |
|execute           |primeFactorsOfSum                      |
|check             |stackHas|3|then|2|then|2|then|2|is|true|

And Its Fixture Code

#include <stdlib.h>
#include <stdio.h>
#include <string>
#include "RpnCalculator.h"
#include "OperationFactory.h"
#include "SlimUtils.h"
#include "SlimList.h"
#include "Fixtures.h"

struct ProgramTheCalculator {
    ProgramTheCalculator() : calculator(factory) {
    }

    static ProgramTheCalculator* From(void *fixtureStorage) {
        return reinterpret_cast<ProgramTheCalculator*>(fixtureStorage);
    }

    OperationFactory factory;
    RpnCalculator calculator;
};

extern "C" {

void* ProgramTheCalculator_Create(StatementExecutor* errorHandler, SlimList* args) {
    return new ProgramTheCalculator;
}

void ProgramTheCalculator_Destroy(void *fixture) {
    delete ProgramTheCalculator::From(fixture);
}

static char* startProgramCalled(void *fixture, SlimList *args) {
    auto *self = ProgramTheCalculator::From(fixture);
    self->calculator.createProgramNamed(getFirstString(args));
    return remove_const("");
}

static char* addOperation(void *fixture, SlimList *args) {
    auto *self = ProgramTheCalculator::From(fixture);
    self->calculator.addOperation(getFirstString(args));
    return remove_const("");
}

static char* saveProgram(void *fixture, SlimList *args) {
    auto *self = ProgramTheCalculator::From(fixture);
    self->calculator.saveProgram();
    return remove_const("");
}

static char* enter(void *fixture, SlimList *args) {
    auto *self = ProgramTheCalculator::From(fixture);
    self->calculator.enterNumber(getFirstInt(args));
    return remove_const("");
}

static char* execute(void *fixture, SlimList *args) {
    auto *self = ProgramTheCalculator::From(fixture);
    self->calculator.executeOperator(getFirstString(args));
    return remove_const("");
}

static char* stackHasThenThenThenIs(void *fixture, SlimList *args) {
    auto *self = ProgramTheCalculator::From(fixture);
    for(int i = 0; i < 4; ++i) {
            if(self->calculator.getX() != getIntAt(args, i))
                return remove_const("false");
            self->calculator.executeOperator("drop");
    }

      return remove_const("true");
}

SLIM_CREATE_FIXTURE(ProgramTheCalculator)
    SLIM_FUNCTION(startProgramCalled)
    SLIM_FUNCTION(addOperation)
    SLIM_FUNCTION(saveProgram)
    SLIM_FUNCTION(enter)
    SLIM_FUNCTION(execute)
    SLIM_FUNCTION(stackHasThenThenThenIs)
SLIM_END

}

The Dreaded Query Table

Well here I am working C++ and I felt compelled to make it easier work with query results in C++.

!|Query: SingleCharacterNameOperators|
|op                                  |
|+                                   |
|*                                   |
|/                                   |
|!                                   |
|-                                   |

And Its Fixture Code

#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <string>
#include <memory>
#include "RpnCalculator.h"
#include "OperationFactory.h"
#include "Fixtures.h"
#include "SlimUtils.h"
#include "QueryResultAccumulator.h"

struct SingleCharacterNameOperators {
    OperationFactory factory;
    RpnCalculator calculator;

    SingleCharacterNameOperators() :
        calculator(factory), result(0) {
    }

    ~SingleCharacterNameOperators() {
        delete result;
    }
    static SingleCharacterNameOperators* From(void *fixtureStorage) {
        return reinterpret_cast<SingleCharacterNameOperators*> (fixtureStorage);
    }

    void resetResult(char *newResult) {
        delete result;
        result = newResult;
    }

    void conditionallyAddOperatorNamed(const std::string &name) {
        if (name.size() == 1) {
            accumulator.addFieldNamedWithValue("op", name);
            accumulator.finishCurrentObject();
        }
    }

    void buildResult() {
        v_string names = calculator.allOperatorNames();
        buildResult(names);
    }

    void buildResult(v_string &names) {
        for (v_string::iterator iter = names.begin(); iter != names.end(); ++iter)
            conditionallyAddOperatorNamed(*iter);

        resetResult(accumulator.produceFinalResults());
    }

    QueryResultAccumulator accumulator;
    char *result;
};

extern "C" {
void* SingleCharacterNameOperators_Create(StatementExecutor* errorHandler,
        SlimList* args) {
    return new SingleCharacterNameOperators;
}

void SingleCharacterNameOperators_Destroy(void *fixture) {
    delete SingleCharacterNameOperators::From(fixture);
}

static char* query(void *fixture, SlimList *args) {
    auto *self = SingleCharacterNameOperators::From(fixture);
    self->buildResult();
    return self->result;
}

SLIM_CREATE_FIXTURE(SingleCharacterNameOperators)
    SLIM_FUNCTION(query)SLIM_END
SLIM_END

And the Helper Class

#pragma once
#ifndef QUERYRESULTACCUMULATOR_H_
#define QUERYRESULTACCUMULATOR_H_

class SlimList;
#include <vector>
#include <string>
class QueryResultAccumulator {
public:
    typedef std::vector<SlimList*> v_SlimList;
    typedef v_SlimList::iterator iterator;

    QueryResultAccumulator();
    virtual ~QueryResultAccumulator();

    void finishCurrentObject();
    void addFieldNamedWithValue(const std::string &name, const std::string &value);
    char *produceFinalResults();

private:
    SlimList* allocate();
    void releaseAll();
    void setInitialConditions();

private:
    v_SlimList created;
    SlimList *list;
    SlimList *currentObject;
    int lastFieldCount;
    int currentFieldCount;
    char *result;

private:
    QueryResultAccumulator(const QueryResultAccumulator&);
    QueryResultAccumulator& operator=(const QueryResultAccumulator&);
};

#endif

I know there are too many fields. The counts help with validating correct usage. I also wrote it so one instance could be re-used and I tried to make sure it was in a “ready to receive fields” state when necessary. In any case, this error checking helped find a defect I introduced while refactoring.

#include "QueryResultAccumulator.h"
#include "DifferentFieldCountsInObjects.h"
#include "InvalidStateException.h"

extern "C" {
#include "SlimList.h"
#include "SlimListSerializer.h"
}

QueryResultAccumulator::QueryResultAccumulator() : result(0) {
    setInitialConditions();
}

QueryResultAccumulator::~QueryResultAccumulator() {
    releaseAll();
    SlimList_Release(result);
}

void QueryResultAccumulator::setInitialConditions() {
    releaseAll();
    list = allocate();
    currentObject = allocate();
    lastFieldCount = -1;
    currentFieldCount = -1;
}

SlimList* QueryResultAccumulator::allocate() {
    SlimList *list = SlimList_Create();
    created.push_back(list);
    return list;
}

void QueryResultAccumulator::releaseAll() {
    for (iterator i = created.begin(); i != created.end(); ++i)
        SlimList_Destroy(*i);
    created.clear();
}

void QueryResultAccumulator::finishCurrentObject() {
    if(lastFieldCount >= 0 && lastFieldCount != currentFieldCount)
        throw DifferentFieldCountsInObjects(lastFieldCount, currentFieldCount);

    SlimList_AddList(list, currentObject);
    currentObject = allocate();

    lastFieldCount = currentFieldCount;
    currentFieldCount = -1;
}

void QueryResultAccumulator::addFieldNamedWithValue(const std::string &name, const std::string &value) {
    SlimList *fieldList = allocate();
    SlimList_AddString(fieldList, name.c_str());
    SlimList_AddString(fieldList, value.c_str());
    SlimList_AddList(currentObject, fieldList);
    ++currentFieldCount;
}

char* QueryResultAccumulator::produceFinalResults() {
    if(currentFieldCount != -1)
        throw InvalidStateException("Current object not written");

    SlimList_Release(result);
    result = SlimList_Serialize(list);
    setInitialConditions();
    return result;
}

void SlimList_Release(char *serializedResults);

void SlimList_Release(char *serializedResults)
{
  if(serializedResults)
    free(serializedResults);
}

I needed to add these methods due to a false-positive memory leak indicated when using CppUTest to test this code. That’s another blog.

In a tell-don’t-ask system, the tells at the high level are relatively complex. They branch out into lower subsystems getting simpler, but more numerous as they descend. Testing these tells using mocks is not particularly difficult because we don’t need to depend on the lower level functions being there. The mocks make them irrelevant.

In an ask-don’t-tell system the asks at the low level are simple, but as the data moves upwards it gets grouped and composed into lists, maps, sets, and other complex data structures. At the top the data is in it’s most complex form. Writing tests against that complex data is difficult at best. And there is currently no way to mock out the lower levels¹ so all tests written at the high level depend on all the functions below.

The perception of writing tests from the bottom to the top can be horrific at first. Consider, for example, the Orbit program I just wrote. This program simulates N-body gravitation. Imagine that I am writing tests at the top level. I have three bodies at position Pa, Pb, and Pc. They have masses Ma, Mb, and Mc. They have velocity vectors of Va, Vb, Vc. The test I want to write needs to make sure that new positions Pa’, Pb’, Pc’, and new Velocity vectors Va’, Vb’, and Vc’ are computed correctly. How do I do that?

test-update {
  Pa = (1,1)
  Ma = 2
  Va = (0,0)

  Pb = (1,2)
  Mb = 3
  Vb = (0,0)

  Pc = (4,5)
  Mc = 4
  Vc = (0,0)

  update-all

  Pa should == (1.096, 4.128)
  Va should == (0.096, 3.128)

  Pb should == (1.1571348402636772, 0.1571348402636774)
  Vb should == (0.15713484026367727, -1.8428651597363226)

  Pc should == (3.834148869802242, 4.818148869802242)
  Vc should == (-0.16585113019775796, -0.18185113019775795)
}

But wait! I’m working in a functional language. That means that every function I call with certain inputs will always return the same value; no matter how many times I call it. Functions don’t change state! And that means that I can write my tests quite differently.

How does update-all work? Simple, given a list of objects it performs the following operations (written statefully):

  update-all(objects) {
    for each object in objects {
      accumulate-forces(object, objects)
    }
    for each object in objects {
      accelerate(object)
      reposition(object)
    }
  }

This is written in stateful form to make is easier for our non-functional friends to follow. First we accumulate the force of gravity between all the objects. This amounts to evaluating Newton’s F=Gm1m1/r^2 formula for each pair of objects, and adding up the force vectors.

Then, for each object we accelerate that object by applying the force vector to it’s mass, and adding the resultant delta-v vector to it’s velocity vector.

Then, for each object we reposition that object by applying the velocity vector to it’s current position.

Here’s the clojure code for update-all

(defn update-all [os]
  (reposition-all (accelerate-all (calculate-forces-on-all os))))

In this code you can clearly see the bottom-to-top flow of the application. First we calculate forces, then we accelerate, and finally we reposition.

Now, what do these -all functions look like? Here they are:

(defn calculate-forces-on-all [os]
  (map #(accumulate-forces % os) os))

(defn accelerate-all [os]
  (map accelerate os))

(defn reposition-all [os]
  (map reposition os))

If you don’t read clojure, don’t worry. the map function simply creates a new list from an old list by applying a function to each element of the old list. So in the case of reposition-all it simply calls reposition on the list of objects (os) producing a new list of objects that have been repositioned.

From this we can determine that the function of update-all is to call the three functions (accumulate-forces, accelerate, and reposition) on each element of the input list, producing a new list.

Notice how similar that is to a statement we might make about a high level method in an OO program. (It’s got to call these three functions on each element of the list). In an OO language we would mock out the three functions and just make sure they’d been called for each element. The calculations would be bypassed as irrelevant.

Oddly, we can make the same statement in clojure. Here’s the test for update-all

(testing "update-all" 
  (let [
    o1 (make-object ...)
    o2 (make-object ...)
    o3 (make-object ...)
    os [o1 o2 o3]
    us (update-all os)
    ]
    (is (= (nth us 0) (reposition (accelerate (accumulate-forces os o1)
    (is (= (nth us 1) (reposition (accelerate (accumulate-forces os o2)
    (is (= (nth us 2) (reposition (accelerate (accumulate-forces os o3)
    )
  )

If you don’t read clojure don’t worry. All this is saying is that we test the update-all function by calling the appropriate functions for each input object, and then see if the elements in the output list match them.

In an OO program we’d find this dangerous because of side-effects. We couldn’t be sure that the functions could safely be called without changing the state of some object in the system. But in a functional language it doesn’t matter how many times you call a function. So long as you pass in the same data, you will get the same result.

So this test simply checks that the appropriate three functions are getting called on each element of the list. This is exactly the same thing an OO programmer would do with a mock object!

Is TDD necessary in Clojure?

If you follow the code in the Orbit example, you’ll note that I wrote tests for all the computations, but did not write tests for the Swing-Gui. This is typical of the way that I work. I try to test all business rules, but I “fiddle” with the GUI until I like it.

If you look carefully you’ll find that amidst the GUI functions there are some “presentation” functions that could have been tested, but that I neglected to write with TDD[2]. These functions were the worst to get working. I continuously encountered NPEs and Illegal Cast exceptions while trying to get them to work.

My conclusion is that Clojure without TDD is just as much a nightmare as Java or Ruby without TDD.

Summary

In OO we tend to TDD our way from the top to the bottom by using Mocks. In Clojure we tend to TDD our way from the bottom to the top. In either case we can compose our tests in terms of the functions they should call on the lower level objects. In the case of OO we use mocks to tell us if the functions have been called properly. This protects us from side-effects and allows us to decouple our tests from the whole system. In clojure we can rely on the fact that the language is functional, and that no matter how many times you call a function it will return the same value.

¹ Brian Marick is working on something that looks a lot like a mocking framework for clojure. If his ideas pan out, we may be able to TDD from the top to the bottom in Clojure.

² This is an unconscious game we all play with ourselves. When we have a segment of code that we consider to be immune to TDD (like GUI) then we unconsciously move lots of otherwise testable code into that segment. Yes, I heard my green band complain every time I did it; but I ignored it because I was in the GUI. Whoops.