#unit testris

[01d55]

Rust

Some time ago a tweet linked me to a blog post arguing that everyone should replace all their C code with Rust code. This implied that Rust was a programming language that could, in principle replace C - and therefore also C++.

The first question I asked was "but does it have a garbage collector?" Garbage collection is a feature of nearly every new language since Java, and not without good reason. For most purposes GC is just a better solution. But for some purposes, GC is a dealbreaker, and programmers who have those purposes must exclude GC'd languages from consideration.Thus, for a very long time those programmers have had to choose between C and C++.

Rust does not have a garbage collector. So I read more and it all sounded good enough that I decided to port Unit Testris to Rust. I've just got to the point where the three unit tests found in /tests/ are ported and I figure this is a good time to stop and write about the Experience So Far.

The book warns that the issue that takes up a new Rust programmer's time is dealing with the borrow checker. I feel that it didn't take that long to come to grips with it. What's been more persistent is the issues with value semantics and move vs. copy. When you pass anything to a function by value Rust wants to move it - but if you use that value later, a move is invalid and Rust will silently check the type for the Copy trait. If the type is Copy, the compiler will silently convert the move to a copy. Otherwise, you'll get a compiler error saying you can't move X for reason Y. So I'll do a thing with a Copy type, then do the same thing with not-Copy and get a move error. Most often, the not-Copy type is Clone, and then I generally decide to clone() it.

As I expected when I read the relevant chapter of the Rust Book, the greatest improvement going from C++ to Rust is templates. Rust calls them generics but I've been raised on C++ so I'm calling them by their C++ name. The issue with C++ templates is that they're permissive until the last moment - if you're writing a template function with type parameter T, and write t.frob(), C++ will allow it and thenceforth anyone who tries to call that function with a type that doesn't have a method named frob that takes no arguments will get a compiler error pointing to that specific line of your template. This is not the most helpful message. A solution has been proposed but has not yet been adopted into the most recent C++ standard: Concepts. Quoting from the link:

Formal specification of concepts (ISO/IEC TS 19217:2015) is an experimental technical specification, which makes it possible to verify that template arguments satisfy the expectations of a template or function during overload resolution and template specialization.

The library concepts listed on this page are the named requirements used in the normative text of the C++ standard to define the expectations of the standard library. It is expected that a future version of the C++ standard library will formalize these library concepts using the facilities of the above-mentioned technical specification. Until then, the burden is on the programmer to ensure that library templates are instantiated with template arguments that satisfy these concepts. Failure to do so may result in very complex compiler diagnostics.

There are at least two problems with concepts: First, they aren't in the standard yet. Second, they're not the default. Backwards compatibility will demand that conceptless templates continue to be permitted, and so the correctly restrictive behavior won't occur unless programmers choose to use the new feature.

In Rust, templates are restricted by default, which means that without a trait bound, a variable of a template type is limited to assignment. Doing anything else requires a trait, and so if the user of a template tries to use a type that doesn't support a needed operation, they'll get an error identifying the trait that defines that operation. The worst time I've had from Rust templates so far was due to the standard library implementing IntoIterator on references to arrays but not array values, and a confusing error message from the compiler trying a templated implementation of that same trait.

Rust's superior templates are also how I supported mocking without compromising performance. Rust doesn't copy the C/C++ compilation model, so I can't use it to isolate code for no additional charge. But Traits fill the role of both Concepts and Interfaces, allowing the same mechanism to control dynamic and static dispatch. Consider this implementation of the House example:

mod dependencies { pub struct Sink; impl Sink { pub fn new() -> Self { Sink } } pub struct Dishwasher; impl Dishwasher { pub fn new() -> Self { Dishwasher } } pub struct Refrigerator { is_locked: bool } impl Refrigerator { pub fn new() -> Self { Refrigerator { is_locked: false } } pub fn lock(&mut self) -> () { self.is_locked = true; } pub fn is_locked(&self) -> bool { self.is_locked } } } mod house { use dependencies::*; trait ISink { fn new() -> Self; } impl ISink for Sink { fn new() -> Self { Sink::new() } } trait IDishwasher { fn new() -> Self; } impl IDishwasher for Dishwasher { fn new() -> Self { Dishwasher::new() } } trait IRefrigerator { fn new() -> Self; fn lock(&mut self) -> (); } impl IRefrigerator for Refrigerator { fn new() -> Self { Refrigerator::new() } fn lock(&mut self) -> () { self.lock() } } struct HouseImplementation<S: ISink, D: IDishwasher, R: IRefrigerator> { sink: S, dishwasher: D, refrigerator: R, is_locked: bool } pub struct House { pimpl: HouseImplementation<Sink, Dishwasher, Refrigerator> } impl<S: ISink, D: IDishwasher, R: IRefrigerator> HouseImplementation<S, D, R> { fn new() -> Self { HouseImplementation { sink: S::new(), dishwasher: D::new(), refrigerator: R::new(), is_locked: false } } fn is_locked(&self) -> bool { self.is_locked } fn lock(&mut self) { self.is_locked = true; self.refrigerator.lock(); } } impl House { pub fn new() -> Self { House { pimpl: HouseImplementation::new() } } pub fn lock(&mut self) { self.pimpl.lock() } pub fn is_locked(&self) -> bool { self.pimpl.is_locked() } } }

With this setup, a house::test module can create a MockRefigerator, et. al., impl IRefrigerator for MockRefigerator, etc. and then instantiate HouseImplementation<MockSink, MockDishwasher, MockRefigerator>. I get value semantics and static dispatch while substituting mocks just as if I used reference semantics and dynamic dispatch. Further, if I used dynamic dispatch, I could, and would, use the same Traits.

Speaking of those traits, note that they're defined in mod house, rather than in mod dependencies. That's because the traits exist for the benefit of HouseImplementation. For example, IRefrigerator doesn't cover all the methods of Refrigerator - only those actually used by HouseImplementation. A different module could define its own IRefrigerator to cover the parts of Refrigerator that it uses. In Unit Testris, piece.rs and game.rs each have their own trait IField. Because they are both sparse traits, the two MockField structs get to skip implementing a bunch of functions that will never be called.

C++ templates could obtain the same result, but I prefer using the compilation model.

I strongly suspect that when I start porting implementation of the classes, Rust's safety rules will compel changes to the tests.

[01d55]

Making a Mockery of C++

Back when I wrote my first Mock, I seem to have completely forgotten to talk about my mocking strategy.

My understanding of Unit Testing comes from Miško Hevery's 2008 articles on the subject of writing testable code. I am basically convinced by Hevery's assertion that Unit Testing requires clean separation of code units, and that it is possible to block testing by writing inseperable code, but I do not use all of his suggested means of supporting tests. My point of disagreement is that I believe that changes to code design for the purpose of supporting testing should be A) invisible to consumers of code B) zero cost abstractions, i.e. performance should not be penalized.

Let us first consider this example with point A in mind. Here we see that instantiating a dependency in a constructor creates a tight binding, and a solution in which the binding is loosened at the expense of changing the signature of the constructor. Then, a new class is introduced whose sole purpose is to provide a function that reproduces the previous constructor's function. Not only have we changed the interface of House, we've introduced an entirely new interface for the consuming programmers to learn! I would prefer that instead of a factory class, we write a wrapper class, which will take the name House and present precisely the same interface as the tightly-bound House, but whose implementation defers entirely to a HouseImplementation class, and the constructor creates a HouseImplementation in the same way Hevery's ApplicationBuilder makes his House. HouseImplementation is exactly what Hevery calls House, and thus is testable, and the wrapper House does not need tests because its correctness is trivially identical to the correctness of HouseImplementation, Sink, Dishwasher, and Refrigerator. This is precisely the same testability gains, while preserving the interface of the untestable code. As for performance, I trust it's not too much to hope for that Java will optimize away the extra call in boolean isLocked() {return impl.isLocked();}.

Now, to discuss point B I will move from Java to C++. First, I'll present a naive implementation of House:

struct Sink { // etc. }; struct Dishwasher { // etc. }; struct Refrigerator { bool mIsLocked; void lock() { this->mIsLocked = true; } }; class House { private: Sink mSink; Dishwasher mDishwasher; Refrigerator mRefrigerator; bool mIsLocked; public: House(): mSink(), mDishwasher(), mRefrigerator() {} bool isLocked() { return this->mIsLocked; } void lock() { this->mIsLocked = true; mRefrigerator.lock(); } };

To fully explain all the tight bindings that are going on here, it'll be quicker to contrast an example that's been made testable in Hervey's style.

struct ISink { virtual void foo() = 0; }; struct Sink: public ISink { void foo() {} }; struct IDishwasher { virtual void foo() = 0; }; struct Dishwasher: IDishwasher { void foo() {} }; struct IRefrigerator { virtual void lock() = 0; }; struct Refrigerator: IRefrigerator { bool mIsLocked; void lock() { this->mIsLocked = true; } }; class House { private: ISink *mSink; IDishwasher *mDishwasher; IRefrigerator *mRefrigerator; bool mIsLocked; public: House(ISink *sink, IDishwasher *dishwasher, IRefrigerator *refrigerator): mSink(sink), mDishwasher(dishwasher), mRefrigerator(refrigerator) {} bool isLocked() { return this->mIsLocked; } void lock() { this->mIsLocked = true; mRefrigerator->lock(); } }; class ApplicationBuilder { House* build() { return new House(new Sink(), new Dishwasher(), new Refrigerator()); } };

I'll admit up front that this will leak memory. Fixing that correctly would add a lot of noise to the example. The topic at hand is the performance cost of moving to this implementation. To start with, all of the value members have been replaced with pointers to interfaces from which our actual dependencies inherit. This allows substitution of Mock classes with alternate implementation of their interface. Pointers to the old classes wouldn't have worked because a mock class that inherits them would still need to fully initialize the parent class, which is a tight binding. Furthermore, a mock child of the original Refrigerator would not be able to effectively replace the lock() method. This is because even if MockRefrigerator: public Refrigerator overrides lock(), mRefrigerator->lock() would invoke Refrigerator::lock, not MockRefrigerator::lock() when one would quite reasonably expect the latter. The virtual keyword is required to get the expected behavior. virtual is inherited, so when IRefrigerator declares lock() virtual, Refrigerator::lock is made virtual as well. Why extra syntax to get good behavior? Performance! Replacing a Sink value with a pointer costs both space (we store both the Sink and a pointer) and time (we allocate the Sink with a sperate call, any use of sink has to deref the pointer). Changing lock() from a non-virtual function to a virtual function creates an additional indirection. Furthermore, every object with at least one virtual method has a hidden pointer, which is a space cost. In Java these are sunk costs baked into the language (and they're partly clawed back by garbage collection, which should make allocation calls much faster) but C++ adopted as a design goal that performance costs should only be paid if the programmer uses the feature. (That doesn't excuse overriding non-virtual methods. I never want code to behave like that.) Can a wrapper save us here, as it did before?

class House { private: Sink implSink; Dishwasher implDishwasher; Refrigerator implRefrigerator; HouseImplementation impl; public: House(): implSink(), implDishwasher(), implRefrigerator(), impl(&implSink, &implDishwasher, &implRefrigerator) {} bool isLocked() { return impl.isLocked(); } void lock() { impl.lock(); } };

Remember when I said fixing the memory leak in the previous example would add noise? I had a secret ulterior motive. This code doesn't leak memory - with no changes to the implementation class! We've eliminated the 3 additional new operators. We've restored guaranteed locality. But we haven't eliminated the extra 3 pointers, nor have we gotten around virtual function dispatch, which includes 3 hidden pointers.

It may appear this is the best we can do. They say there are no free lunches. But there is another way, a lunch we paid for when we chose to use C++, just as we paid for reference semantics and dynamic dispatch when we chose to use Java. There's the C compilation model.

In idiomatic C++, each class is written in a matched pair of files: The header and source. The header contains declarations, which specify the interface and data of the class of the class. The source file contains the definitions of the class' methods, and an #include directive to automatically copy the header. Source files can and generally do include the headers of other units to see and use their declarations. The compiler can then turn each source file into an object file, which records every declared thing the file used and defined. To make an executable, the compiler links (with the assistance of the linker program) the object files together. To link correctly, everything that is used by at least one object file must be defined by at least one object file. Furthermore, nothing can have a contradictory definition - including a header with a definition is fine, but writing different definitions in different source files will cause an error.

We can think of object files as units of testable code. The code under test is the set of symbols defined by the object file, and the dependencies we want to replace are the symbols used but not defined by the object file. By writing alternate source files with different definitions of those symbols and linking these with the tests and object file under test, into a distinct test executable, we can isolate the code under test from all non-test code. We can mock out not only classes, but free functions! Even static state, bane of Java testers, falls under our exclusive control! And best of all, we don't have to change the code under test. We need only split it up into the proper files, as is already our custom. The test and mocks are completely invisible to consumers of our code - they can't be linked into the same executable as the real implementation of our dependencies.

The one limitation is that our mock object must have the same representation. So our mock Refrigerator::lock can be whatever we want, but the Refrigerator itself must be a single bool. So I just use static state to manipulate the behavior of the mock object. Note the namespace and reset_all function, which a test set can call in setup to ensure consistency.

[01d55]

Code Rot

It’s been four years since I last wrote a post on Unit Testris. I have commits for the next year after that but it’s been 3 years since I touched the project. Recently I thought I might try incrementally porting the program to Rust, and to start I had to get the old code to build again.

It turned out that simply reinstalling all the libraries and dev packages wasn’t enough - changes in the Gnu Compiler Collection broke my project. There were two issues of this kind: First, g++ is now enforcing constexpr rules that forbid certain kinds of casts in a constexpr. Specifically, I was reinterpret casting numbers to a pointer so I could pass it as an argument to an OpenGL function which internally reinterpret casts that pointer to a number. If you aren’t familiar with OpenGL and that sounds ridiculous to you, be assured that there is a reason OpenGL does that, and that reason is ridiculous. So now that number is const instead of constexpr in recognition of rules set out in the c++ standard, which is fair. But the g++ error message not having the word “constexpr” in it is not fair, I got the idea that some option was telling the compiler not to accept any cast from integer to pointer..

The second issue is that if you use the C++ standard library threads, the GNU/Linux linker will now fail unless you explicitly link pthreads with -lpthreads. The autotools macro to detect pthreads tests C compliation, because pthreads are a C library so of course it does that. But it means that the result of that macro is not necessarily correct for a C++ project and indeed that macro is useless to me, so I just manually put -pthreads in the Makefile.am because I have reached my limit, I can’t care about the portability of my toy self-teaching project that much.

I also had a test fail, but it was a timing test intended to see if the game loop was running at 60 frames per second and the failure was because it was producing 59 loops per second so I just put some tolerance in.

[01d55]

Autotroubles

I've just fixed a bunch of problems with how I had the GNU Autotools set up which were breaking compilation.

Basically, it turns out that $LDFLAGS is not the variable you want to put things like -lfltk to get them passed to the linker - for that you use $LDADD. The difference is which side of filename.o the variable is placed, which is something the linker cares about. Mine didn't used to care, or the autotools used to fix it for me. When your build environment silently ceases silently fixing a mistake you didn't know you were making, you get baffled. Thanks to linuxquestions.org for pointing out the ordering issue, after which Google® led me to $LDADD.

Meanwhile, I got a newer version of g++, and AX_CXX_COMPILE_STDCXX_0X reports that I now have access to c++11 (formerly known as c++0x)  features, provided that I pass one of two compiler options to g++. This macro is also helpfully defining the symbol which tells the preprocessor not to replace nullptr with 0. Much to my surprise, it did not helpfully insert the option which is required for c++11 support into CXXFLAGS, and so introduced a compilation failure.

I thus set out to write myself an m4 macro to handle the possible necessity of such an option. This is hard to do when you have no experience and the Internet is surprisingly reluctant to produce autotools tutorials that amount to more than presenting extremely basic configure.ac and Makefile.am files and telling you that these files do stuff for you. The generally accepted best source appears to be slides for a lecture. So far as I can tell, these are slides from a fine lecture. However, they don't stand up all that well on their own.

Thankfully, I've finally found a serious introduction to the autotools. I strongly recommend that anyone who intends to write c/c++ programs in unixkin environments read it and use the autotools. For all that I've suffered for them, Unit Testris would be unmanagable without them.

[01d55]

Unit Testris: Mocks

It's been a while since I last pushed to the github. Partly due to a slowdown in work done, but more recently because I was doing a big revision on PieceTest to use a mock Field implementation instead of the real implementation of Field.

This required significant changes to the testStep and testDrop functions, and some search-and-replace in testShift & testRotate. It took a while, but I did happen to find a couple of small edge-case errors the previous versions of the tests weren't revealing - swatting flies with an anvil, though.

It was easier doing it with a mock, but at this juncture it's like remembering that you could have taken a shortcut to where you are, and then going back so you can take the shortcut. Given the time investment, I'd say this wasn't a move I'd do on a project aimed at shipping, which this project is not. This project is about learning, and I think it was a very valuable learning experience.

A move I would do, if I thought anyone else would have to maintain this code, is use some std::vector< boost::array<coord,4> >s to refactor a lot of copypasta code into loops. testField.cpp is nearly 2000 lines.

[01d55]

Convincing

Earlier today I finished an implementation of Field that passes all the tests in FieldTest. In the course of this, I found some errors in the tests. This was less of a problem than it sounds - determining whether the error was in the test or in the implementation was generally pretty simple.

inline void checkLines() { - for(int j=0;j<FIELD_HEIGHT;++j) + for(int j=FIELD_HEIGHT-1;j>=0;--j) checkLine(j); }

This change did a lot to convince me that unit test driven development is a good idea. If my test hadn't failed - and that wouldn't have happened if I hadn't been careful to test clearing two lines right on top of each other - I wouldn't have seen the problem with the loop moving upward (the problem is clearing the lower row draws the upper, full row into the lower row, and then the loop moves on without clearing the still-full row again) until much later.

That said, the tests wind up being a lot more work than the implementation, and being generally longer and probably less efficient. That's acceptable to me, because all the complexity in the tests is complexity the users of the tested don't see!

I also noticed that I made a commit that didn't include all the changes (the .cpp file's changes were comitted, but the .hpp file wasn't) and so a broken build got pushed to github. Probably nobody tried to pull it down and compile it but it's very bad form to let that happen. Gotta be more careful with my git status when pushing.

[01d55]

Our Oldest Nemesis

This morning I discovered an off-by-one error caused by forgetting that indexes start at 0. If you know that the size of a Tetris field is 10x22, the error is visible in my last post - it started with those comment diagrams and worked their way from there into actual code. Cleaning them up wasn't too much time, thankfully.

As I expected, the Piece tests are much more work than the Field tests. They're also much more repetitive - due diligence demands testing at least the I block, O block, and one of the other 5 blocks, and it most cases I'm testing all 7. With that and comments, the file is now more than a thousand lines.

[01d55]

Unit Testris is now on GitHub

https://github.com/01d55/UnitTestris

I should have done this a long time ago; I expected getting the repo copied up exactly (i.e. with full commit history) to be a lot more complicated than it turned out to be (though I did need to look up an extra option in the man page to get the tags to go through).

I also just got done working on Unit Testris for a full 9-5 work day. I've been exercising deeply flawed time management since I finished classes. (and always had poor study habits. Carried through by talent.) When I started, I didn't seriously intend to finish it by any reasonable definition of the term - I was just curious to see how unit testing works. Now I think I'll keep at it until either it runs an actual game of Tetris, or my attention is called elsewhere by paying work.