As a reminder last time UnitTest's behaviour wasn't quite up to par. The test results weren't being reported in the same order that they were being executed. The problem is the use of map<>, more specifically when iterating through a map the order of traversal has nothing to do with the order that the elements were added. To fix this the data structure being used needs to be switched to a linear data structure, either a vector, deque or list. In this case elements will always be added to one end of the structure and traversals will only take place twice, once to count the number of tests passed and once to print out the results. Given those requirements a vector is definitely out, each time the vector grows beyond its current capacity it allocates more memory and potentially recopies all of the elements in vector. This will not happen as the deque and list grow. Since the items being stored will be small (only a pair<string, bool>) relative to the overhead associated with handling a list, deque is the structure of choice.
So
class UnitTest {
private:
map<string, bool> testResults_;
class UnitTest {
private:
deque<pair<string, bool> > testResults_;
By storing the string and bool in a pair, just like map did, the
only function that needs to be rewritten is score(). This is the
beauty of using the algorithms and iterators in the
STL. We have changed the fundamental data structure of UnitTest
but we only need to re-write one of its member functions. Score
was:
void UnitTest::score(bool result, const string & unitTestName) {
testResults_[unitTestName] = result;
}
void UnitTest::score(bool result, const string & unitTestName) {
testResults_.push_back(make_pair(unitTestName, result));
}
We also have to update our includes to include the deque header file and to drop the inclusion of the map header file. Compile and re-run our test suite shows we're still passing 100% of our tests.
One further change to UnitTest before turning to Forth. The results() function should
be changed so that UnitTest can be streamed like other objects. This is done by creating a standalone
operator<<() that works on UnitTest objects. Since it has
to access the private data of UnitTest is has to be a friend of UnitTest:
friend ostream & operator<<(ostream &, const UnitTest &);
ostream & operator<<(ostream & o, const UnitTest & test) {
unsigned int totalPassed = accumulate(test.testResults_.begin(), test.testResults_.end(), 0, incIfPassed);
copy(test.testResults_.begin(), test.testResults_.end(), ostream_iterator<pair<string, bool> >(o, "\n"));
o << endl << "Total Test Cases: " << test.testResults_.size() << endl;
o << "Total Test Cases Passed: " << totalPassed << endl;
if (test.testResults_.size() != totalPassed) {
o << "100% of the test cases must pass before release!" << endl;
}
return o;
}
test.results(cout);
cout << test;
The code above is very clear; we are printing the test object on the cout stream. Look
back at how this line of code used to read: test.results(cout);. Out of
context this is pretty unclear and could mean any number of things:
The current set of tests is pretty thin. More should be added to test
the Forth class more thoroughly. The first tests to add will exercise the
copy constructor and assignment operator of the Forth class.
Forth g(f);
test.score(g.stack_.front() == 6, "Forth Copy Constructor 1");
g.execute("3 4 *");
test.score(g.stack_.front() == 12, "Forth Copy Constructor 2");
Forth h;
h = f;
test.score(h.stack_.front() == 6, "Forth Assignment Operator 1");
h.execute("3 4 *");
test.score(h.stack_.front() == 12, "Forth Assignment Operator 2");
cout << test;
return 0;
}
StackSize Passed
Addition Passed
Multiplication Passed
Forth Copy Constructor 1 Passed
Forth Copy Constructor 2 Failed
Forth Assignment Operator 1 Passed
Forth Assignment Operator 2 Failed
Total Test Cases: 7
Total Test Cases Passed: 5
100% of the test cases must pass before release!
What happened? Our tests indicate that there is a problem
in the copy constructor and assignment operator. Inspecting
them reveals that we failed to add dictionary_ to the
copy constructor and assignment operator when we added
it to the class. For example the copy constructor
was:
Forth::Forth(const Forth & rhs) {
stack_ = rhs.stack_;
}
Forth::Forth(const Forth & rhs) {
stack_ = rhs.stack_;
dictionary_ = rhs.dictionary_;
}
The return value of execute() is never checked. Fixing this results
in the test suite becoming:
int main() {
UnitTest test;
Forth f;
f.addFunction("+", Forth_Plus);
f.addFunction("*", Forth_Multiply);
test.score(f.execute("1 2 +"), "Addition execute");
test.score(f.stack_.size() == 1, "StackSize");
test.score(f.stack_.front() == 3, "Addition");
test.score(f.execute("2 3 *"), "Multiplication execute");
test.score(f.stack_.front() == 6, "Multiplication");
Forth g(f);
test.score(g.stack_.front() == 6, "Forth Copy Constructor 1");
test.score(g.execute("3 4 *"), "Forth Copy Execute");
test.score(g.stack_.front() == 12, "Forth Copy Constructor 2");
Forth h;
h = f;
test.score(h.stack_.front() == 6, "Forth Assignment Operator 1");
test.score(h.execute("3 4 *"), "Forth Assignment Execute");
test.score(h.stack_.front() == 12, "Forth Assignment Operator 2");
cout << test;
return 0;
}
More functions can be added easily. Forth defines a number of functions for basic math and manipulating the stack.
First add the test cases to make sure they fail:
f.stack_.clear();
test.score(f.execute("2 1 drop"), "Drop Execute");
test.score(f.stack_.size() == 1, "Drop 1");
test.score(f.execute("2 dup"), "Dup Execute");
test.score(f.stack_.size() == 2, "Dup 1");
test.score(f.execute("2 1 over"), "Drop Execute");
test.score(f.stack_.size() == 2, "Over 1");
test.score(f.execute("2 1 pick"), "Pick Execute");
test.score(f.stack_.size() == 2, "Pick 1");
Compile and run does get us our failed tests:
.
.
.
Drop Execute Passed
Drop 1 Failed
Dup Execute Passed
Dup 1 Failed
Over Execute Passed
Over 1 Failed
Pick Execute Passed
Pick 1 Failed
Total Test Cases: 19
Total Test Cases Passed: 15
100% of the test cases must pass before release!
But there is a problem, more of the tests should have failed. For example the test labelled "Drop Execute" should have failed but instead it passed. The algorithm in execute() is too simple. When it gets a token it looks it up to see if there is a matching function, if there is none it assumes the token is a number. Execute() has to be enhanced to detect missing functions before the implementations of drop, dup, over and pick are added.
The fix is to explicitly check if a token is a number. By adding a
check isNumber() to determine if a token is a number our execute() code
becomes:
bool Forth::execute(const string & command) {
bool returnValue = true;
char * s = strdup(command.c_str());
char * token = strtok(s, " ");
while (token) {
if (isNumber(token)) {
stack_.push_front(atoi(token));
} else if (dictionary_.find(token) != dictionary_.end()) {
returnValue = (*dictionary_[token])(*this);
} else {
returnValue = false;
}
token = strtok(NULL, " ");
}
free(s);
return returnValue;
}
All that's left to do is the implementation for isNumber():
static bool isNumber(const char * s) {
bool returnValue = true;
while (*s) {
if (!isdigit(*s)) {
returnValue = false;
break;
}
s++;
}
return returnValue;
}
Compiling a running gives us the results we expected, i.e. all of the
new test cases we just added should fail:
Addition execute Passed
StackSize Passed
Addition Passed
Multiplication execute Passed
Multiplication Passed
Forth Copy Constructor 1 Passed
Forth Copy Execute Passed
Forth Copy Constructor 2 Passed
Forth Assignment Operator 1 Passed
Forth Assignment Execute Passed
Forth Assignment Operator 2 Passed
Drop Execute Failed
Drop 1 Failed
Dup Execute Failed
Dup 1 Failed
Over Execute Failed
Over 1 Failed
Pick Execute Failed
Pick 1 Failed
Total Test Cases: 19
Total Test Cases Passed: 11
100% of the test cases must pass before release!
A minor detour at this point. That report is still not pretty to look at. It would be easier to read
if Failed/Passed lined up on every row. Adding setw(), left() and setfill()
stream manipulators to operator<< makes the output much more legible, so:
ostream & operator<<(ostream & o, const pair<string, bool> & unitTestResult) {
o << unitTestResult.first << " " << (unitTestResult.second ? "Passed" : "Failed");
return o;
}
ostream & operator<<(ostream & o, const pair<string, bool> & unitTestResult) {
o << setfill('-') << left << setw(30) << unitTestResult.first << " " << (unitTestResult.second ? "Passed" : "Failed");
return o;
}
This will also require adding the <iomanip> header.
And now the output is much easier to read:
Addition execute-------------- Passed
StackSize--------------------- Passed
Addition---------------------- Passed
Multiplication execute-------- Passed
Multiplication---------------- Passed
Forth Copy Constructor 1------ Passed
Forth Copy Execute------------ Passed
Forth Copy Constructor 2------ Passed
Forth Assignment Operator 1--- Passed
Forth Assignment Execute------ Passed
Forth Assignment Operator 2--- Passed
Drop Execute------------------ Failed
Drop 1------------------------ Failed
Dup Execute------------------- Failed
Dup 1------------------------- Failed
Over Execute------------------ Failed
Over 1------------------------ Failed
Pick Execute------------------ Failed
Pick 1------------------------ Failed
Total Test Cases: 19
Total Test Cases Passed: 11
100% of the test cases must pass before release!
Now back to adding our new Forth functions. Each function, drop, dup, over and
pick gets a standalone function that then gets registered with an instance
of the Forth class. Dup, for example, is:
bool Forth_Dup(Forth & f) {
bool returnValue = false;
if (f.stack_.size()) {
f.stack_.push_front(f.stack_.front());
returnValue = true;
}
return returnValue;
}
f.addFunction("dup", Forth_Dup);
The addition of the functions for -, /, drop, over and pick
are all similar. Here are the function definitions for dup, drop, pick and over:
bool Forth_Drop(Forth & f) {
if (f.stack_.size()) {
f.stack_.pop_front();
}
return true;
}
bool Forth_Dup(Forth & f) {
bool returnValue = false;
if (f.stack_.size()) {
f.stack_.push_front(f.stack_.front());
returnValue = true;
}
return returnValue;
}
bool Forth_Over(Forth & f) {
bool returnValue = false;
if (f.stack_.size() >= 2) {
f.stack_.push_front(f.stack_[1]);
returnValue = true;
}
return returnValue;
}
bool Forth_Pick(Forth & f) {
bool returnValue = false;
if (f.stack_.size() >= 2) {
int num1 = f.stack_.front();
f.stack_.pop_front();
if ((int)f.stack_.size() >= num1) {
f.stack_.push_front(f.stack_[num1 - 1]);
returnValue = true;
}
}
return returnValue;
}
There is a lot of similar looking code between dup, over and pick. Patterns in code often signal an opportunity to refactor. That opportunity will be explored next time.
In this installment we found bugs two ways. The most obvious was to write test cases and have them fail when we expected them to pass, as when we wrote the test cases for the copy constructor and assignment operator for the class Forth. We also found a bug in the implementation of Forth::execute() when we wrote test cases for dup, drop, over and pick and they didn't fail the first time we ran them. This reinforces the Extreme Programming practice of writing the test cases first, make sure they fail, then add in code until they pass.
Next installment the possibility of refactoring all that similar looking code in dup, drop and pick will be explored. Also next installment the implementation will start to diverge from 'standard' Forth by adding strings as a fundamental data type. Right now the implementation can only handle integers, they are the only type in the system. Strings will be added as a fundamental data type, which means we can push and pop them from the stack. Once that work is complete then the ability to create colon definitions, the terminology for functions in Forth, can be added.