Re: [boost] Invariants & Contracts in C++?

From: Jesse Jones (jejones_at_[hidden])
Date: 2001-03-14 23:13:01

>Does anyone have any thoughts or working code for validating class invariants
>and enforcing programming by contract in C++?

I'm the author of the Whisper framework you posted a link to and I've been
using Design By Contract (DBC) in C++ for a few years now. DBC is
definitely worthwhile when thinking about how a class should work, but
except for a few limited cases I'm not sure Whisper has gained a lot from
DBC.

I think that it's best for classes with a lot of complex state or in base
classes to make sure that client subclasses are well behaved. An example of
the former is a red-black tree implementation I wrote in a prior life. IIRC
there are four properties that a binary tree must have to be red-black (eg
nodes must alternate between being red and black). I wrote an invariant to
check all four that was very useful given how complex the red-black tree
code is (the non-constant time checks were only enabled if an intense
debugging flag was set). If you don't have an invariant you have to rely on
unit tests, but that's tricky to do since you have start checking the
performance guarantees to ensure that a bug isn't resulting in a degenerate
tree.

For the subclass case it's arguably better to prevent subclasses from
freely changing the base class state by doing things like making the data
private or arranging things so that implementation inheritance isn't needed
at all. I've taken the second approach in Whisper 2.0: clients essentialy
do no implementation inheritance (this is something I've just spent some
time on and the online docs aren't quite up to date).

>I'm particularly interested in how this might be handled in the face of:
>
>- templates
>- polymorphism

The best technique to handle invariants in a class hierarchy is to use the
template method pattern. For example, the base class might have a
HandleOperation() method and OnPart1() and OnPart2() methods. The calls to
the invariants are in HandleOperation and subclasses override OnPart1
and/or OnPart2. The invariant method is virtual so subclasses can check
their state.

The big problem with this is that objects can fall into an invalid state
while they're executing a method. This means that you cannot blindly call
the invariant when you (re)enter/exit a public method. If you use
invariants heavily I think you'll find that this is a real problem. Whisper
uses a base class to keep track of the nesting count because Whisper 1.0
relied heavily on mixins and I wanted to check invariants within the mixins
(ie the PRECONDITION macro can dynamic_cast 'this' to XInvariantMixin to
get to the counter). Introducing a vtable into your typical template class
would be a bit annoying though (but maybe OK if it was debug only).

>In a recent project I found the following simple code invaluable: I created
>member functions named "MembersValid()" that were included only in debug
>builds:
>
>class Example{
>	public:
>		void AMemberFunction();
>#ifndef NDEBUG
>		bool MembersValid();
>#endif
>	private:
>		// ... some data members whose validity get checked here
>};
>
>Then I'd test MembersValid() at the entry point of all my member functions:
>
>void Example::AMemberFunction()
>{
>	assert( MembersValid() );
>}

One big problem with this is that when you have a complex invariant you'll
have no clue where things went wrong. Much better I think is to have the
invariant assert instead.

>My thinking is that the invariant must always hold true "outside" any public
>or protected member function, and should hold true for private functions, but
>not necessarily - if two private member functions are used in a two step
>process that breaks and restores the invariant, I would think this is
>permissible, although potentially troublesome.

It's pretty common and I don't think you can disallow it. Although it might
be interesting to try, especially when you consider exception safety :-).

>Here's the class invariant header file for the Whisper cross-platform
>framework:
>
>http://magnes.augsburg.edu/Whisper/html/xinvariant_h-source.html
>
>While it could be very helpful to use programming by contract in a template,
>it would be troublesome to require any class its instantiated with to provide
>validation functions - but it would also be very helpful to do so.  What
>do I do?

It's a thorny problem all things considered. There have been a number of
magazine articles on this, but no one has come up with *the* solution. In
fact, from what I remember they were all pretty lame. However Boost really
needs to provide some debugging tools to the masses. The C assert is pretty
nearly useless and I regard things like a reasonable assert, unit tests,
tracing, and invariants as a cornerstone of quality software development.

>And what about polymorphism?  The whole point of programming by contract is
>that the derived classes must have the same contract as the base classes, but
>they may impose additional constraints on the invariant - the base class
>invariant must hold true, but they may have invariants of their own.

If you follow the template method pattern I outlined above you can allow
clients to augment the invariant. What you cannot do is allow subclasses to
weaken pre-conditions or strengthen post-conditions. This is a theoritical
problem, but I haven't found it to be a problem at all in practice.

  -- Jesse