The Artima Developer Community
Sponsored Link

Weblogs Forum
Testing Invariants in C++

11 replies on 1 page. Most recent reply: May 5, 2005 10:51 AM by Kristian Dupont

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 11 replies on 1 page
Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Testing Invariants in C++ (View in Weblogs)
Posted: Apr 30, 2005 2:20 PM
Reply to this message Reply
Summary
Assuring invariants can be a tricky endeavour in C++. Here are some techniques included a simple pointer class, which can help make life easier.
Advertisement
Let's consider the case of a simple OddNumber class. The invariant is relatively straightforward, the class must always contain an odd number. Here is a simple implementation for demonstration purposes:
  class OddNumber1 {
  public:
    OddNumber1() : m(1) {
    }
    int GetValue() const {
      return m;
    }
    int SetValue(int x) {
      return m = x;
    }
    int AddValue(int x) {
      return m += x;
    }
    int ThrowException() {
      throw std::runtime_error("boom");
      return 0;
    }
    void CheckInvariant() const {
      if (m % 2 != 1) {
        std::cerr << "invariant violated\n";
      }
    }
  private:
    int m;
  };
In order to assure the invariant through all control paths, the most obvious way would be as follows:
  class OddNumber2 {
  public:
    OddNumber2() : m(1) {
      CheckInvariant();
    }
    int GetValue() {
      CheckInvariant();
      return m;
    }
    int SetValue(int x) {
      CheckInvariant();
      m = x;
      CheckInvariant();
      return m;
    }
    int AddValue(int x) {
      CheckInvariant();
      m += x;
      CheckInvariant();
      return m;
    }
    int ThrowException() {
      CheckInvariant();
      int ret;
      try
      {
        throw std::runtime_error("boom");
        return 0;
      }
      catch(...)
      {
        CheckInvariant();
        throw;
      }
      CheckInvariant();
      return ret;
    }
    void CheckInvariant() const {
      if (m % 2 != 1) {
        std::cerr << "invariant violated\n";
      }
    }
  private:
    int m;
  };
The problem with this approach is that it requires a significant amount of extra code and rewriting of the various functions. A more sophisticated solution is to use an invariant checking class which uses the well-known -- and rather bizarrely named -- RAII (Resource Acquisition Is Initialiation) idiom.
  template<typename T>
  class InvariantChecker {
  public:
    InvariantChecker(const T* x) : m(x) {
      m->CheckInvariant();
    }
    ~InvariantChecker() {
      m->CheckInvariant();
    }
  private:
    const T* m;
  };

  class OddNumber3 {
    typedef InvariantChecker<OddNumber3> guard;
  public:
    OddNumber3() : m(1) {
      guard g(this);
    }
    int GetValue() {
      guard g(this);
      return m;
    }
    int SetValue(int x) {
      guard g(this);
      return m = x;
    }
    int AddValue(int x) {
      guard g(this);
      return m += x;
    }
    int ThrowException() {
      guard g(this);
      throw std::runtime_error("boom");
      return 0;
    }
    void CheckInvariant() const {
      if (m % 2 != 1) {
        std::cerr << "invariant violated\n";
      }
    }
  private:
    int m;
  };
This significantly cuts down on the extra code and complexity needed to assure the invariant. If we don't mind adding an extra level of indirection however, an even more elegant solution can be achieved by overloading the indirection operator->().
  template<typename T>
  class GuardedPtr {
  public:
    struct Wrapper {
      Wrapper(T* x) : m(x) {
        m->CheckInvariant();
      }
      T* operator->() {
        return m;
      }
      const T* operator->() const {
        return m;
      }
      ~Wrapper() {
        m->CheckInvariant();
      }
    private:
      T* m;
    };
  public:
    GuardedPtr(T* x) : m(x) {
    }
    Wrapper operator->() {
      return m;
    }
    const Wrapper operator->() const {
      return m;
    }
  private:
    T* m;
  };
You can use this like you would any normal pointer, but whenever you call a member function through the operator->() the invariant is checked before and after the call. For example:
  OddNumber1 o;
  GuardedPtr<OddNumber1> p(&o);
  p->SetValue(3);
  p->GetValue();
  p->AddValue(1);
  try {
    p->ThrowException();
  }
  catch(...) {
  }
This code will notify us of three invariant violations. I'll leave it as an exercise to the reader to figure out where.


Matthew Wilson

Posts: 145
Nickname: bigboy
Registered: Jun, 2004

Re: Testing Invariants in C++ Posted: Apr 30, 2005 9:24 PM
Reply to this message Reply
Backwards and bonkers, I'm afraid. We're reasonably good down to OddNumber3 (neglecting the use of std::runtime_error, but that's a whole huge separate debate that there's no point getting into here).

But of what use is OddNumber1 as distinct from GuardedPtr<OddNumber1>? I'd say: none whatsoever. Indeed, it's positively dangerous and an abuse of the type system, i.e. what's to stop someone doing something like the following?

OddNumber1 o;
o.SetValue(3);
o.GetValue();
o.AddValue(1);

or

OddNumber1 o;
GuardedPtr<OddNumber1> p(&o);
p->SetValue(3);
p->GetValue();
o.AddValue(1);

I think this is a really bad thing to be proposing. :-(

Oh, and why in Bob's name is ThrowException public?! If it's just that way for pedagogical purposes, I think you're unnecessarily weakening your position for the sake of saving typing a few "private:" characters

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Testing Invariants in C++ Posted: May 1, 2005 10:10 AM
Reply to this message Reply
> Backwards and bonkers, I'm afraid.

Harrumph. I am not proposing an end-solution, I am proposing a step towards possible interesting things. You don't need to be insulting.

> We're reasonably good
> down to OddNumber3 (neglecting the use of
> std::runtime_error, but that's a whole huge separate
> debate that there's no point getting into here).

Thank you for not going down that path.

> But of what use is OddNumber1 as distinct from
> GuardedPtr<OddNumber1>? I'd say: none whatsoever. Indeed,
> it's positively dangerous and an abuse of the type system,

Abuse of the type system! You are really given to hyperbole aren't you?

> i.e. what's to stop someone doing something like the
> following?

Nothing. It is not a complete solution.

> I think this is a really bad thing to be proposing. :-(

Clearly it would only be of any use if some technique was used to protect access to the unguarded collection

> Oh, and why in Bob's name is ThrowException public?! If
> it's just that way for pedagogical purposes,

Yes. It should have been DoSomethingWhichMightThrowException(), but I thought that was too long to type.

> I think
> you're unnecessarily weakening your position for the sake
> of saving typing a few "private:" characters

I think you are obsessing over details.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Testing Invariants in C++ Posted: May 1, 2005 10:21 AM
Reply to this message Reply
I thought I should tack on another possibility which I left out (and might more appeal to Matthew):


template<typename T>
class GuardedVeneer {
public:
struct Wrapper {
Wrapper(T* x) : m(x) {
m->CheckInvariant();
}
T* operator->() {
return m;
}
const T* operator->() const {
return m;
}
~Wrapper() {
m->CheckInvariant();
}
private:
T* m;
};
public:
Wrapper operator->() {
return m;
}
const Wrapper operator->() const {
return m;
}
private:
T m;
};


This would cause the example to be rewritten:


GuardedVeneer<OddNumber1> o;
o->SetValue(3);
o->GetValue();
o->AddValue(1);
try {
o->DoSomethingWhichMightThrowException();
}
catch(...) {
}

Max Lybbert

Posts: 314
Nickname: mlybbert
Registered: Apr, 2005

Re: Testing Invariants in C++ Posted: May 2, 2005 7:34 PM
Reply to this message Reply
Before I say something Really Wrong, let me announce that I am a computer science student, and I have limited real world programming experience.

It seems to me that:

(1) there's no need to test the invariant both before and after each operation, as each operation should be given a valid object (the end result of the previous operation, which was the end result of the operation before that, all the way to the constructor). I believe if you could guarantee that each operation checked the invariant before returning, then you wouldn't need to check before doing anything. I realize that's a big "if," especially during development.

(2) Maybe it's my exposure to closures, but I wonder if overloading operator= wouldn't be a better solution. My reasoning is that (in a number-centric case) operator= is where the value actually changes. OK, perhaps that's oversimplified, since several other operations may modify the value of the class. Overloading operator-> guarantees that all access to the class is checked, but it feels like a belt and suspenders approach.

Matthew Wilson

Posts: 145
Nickname: bigboy
Registered: Jun, 2004

Re: Testing Invariants in C++ Posted: May 2, 2005 7:50 PM
Reply to this message Reply
> Before I say something Really Wrong, let me
> announce that I am a computer science student, and I have
> limited real world programming experience.

That characterisation applies to each and every honest software engineer, no matter how long they've been at it. :-)

> It seems to me that:
>
> (1) there's no need to test the invariant both before and
> after each operation, as each operation should be
> given a valid object (the end result of the previous
> operation, which was the end result of the operation
> before that, all the way to the constructor). I believe
> if you could guarantee that each operation checked the
> invariant before returning, then you wouldn't need to
> check before doing anything. I realize that's a big "if,"
> especially during development.

Ah, but what about the effects of rogue pointer use?

Basically, if your instance is scribbled on between calls on its members, it's possible to call on an object that's become invalid through some other code's misdeeds. For all that that can sometimes mislead one in applying blame, it's still a hell of a lot better to catch such conditions as soon as possible. I'm sure you can appreciate that the greater the delay in detecting the symptoms of a bug, the greater the challenge in finding its cause.

Terje Slettebø

Posts: 205
Nickname: tslettebo
Registered: Jun, 2004

Re: Testing Invariants in C++ Posted: May 4, 2005 7:24 AM
Reply to this message Reply
I just thought I'd mention that there exists a proposal to add support for Design by Contract to C++ (http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1773.html).

In the proposal, as in your examples, invariants are checked before and after calls to (public and protected) member functions, as well as at the end of the constructor, and beginning of the destructor.

With it, your example could have been written as:

class OddNumber1 {
invariant {
m % 2 == 1;
}
public:
OddNumber1() : m(1) {
}
int GetValue() const {
return m;
}
int SetValue(int x) {
return m = x;
}
int AddValue(int x) {
return m += x;
}
int ThrowException() {
throw std::runtime_error("boom");
return 0;
}
private:
int m;
};

Regards,

Terje

Harrison Ainsworth

Posts: 57
Nickname: hxa7241
Registered: Apr, 2005

Re: Testing Invariants in C++ Posted: May 4, 2005 9:22 AM
Reply to this message Reply
I agree with Mr Lybbert, point (1): it's only necessary to check invariants after the method has changed something -- at the end, and before self-delegatory calls to other methods.

If something else has free access to the object through a pointer, then either: encapsulation has not been secured somewhere -- and that part of the design needs addressing. Or whatever else owns that pointer is behaving faultily -- and that's a failure of its class invariant checking. Either way, the cautionary code should be local, not spread across all other code in the program. It's part of the modularisation.

And it is worth noting that const methods (queries) don't need any invariant checks, which would reduce checking by maybe half. (And const classes don't need any.)

indranil banerjee

Posts: 38
Nickname: indranil
Registered: Nov, 2004

Re: Testing Invariants in C++ Posted: May 4, 2005 6:01 PM
Reply to this message Reply
> In the proposal, as in your examples, invariants are
> checked before and after calls to (public and protected)
> member functions, as well as at the end of the
> constructor, and beginning of the destructor.
>

Why would you want to check invariants at the beginning of the destructor. What could you do about it at that stage? You cant throw an exception.

Similarly I dont understand why Christopher's Wrapper class does invariant checking in its destructor. See kinda dangerous

Terje Slettebø

Posts: 205
Nickname: tslettebo
Registered: Jun, 2004

Re: Testing Invariants in C++ Posted: May 4, 2005 6:23 PM
Reply to this message Reply
> > In the proposal, as in your examples, invariants are
> > checked before and after calls to (public and
> protected)
> > member functions, as well as at the end of the
> > constructor, and beginning of the destructor.
> >
>
> Why would you want to check invariants at the beginning of
> the destructor. What could you do about it at that stage?
> You cant throw an exception.

Well, you can abort (which amounts to the same thing, at that point :) ). After all, contracts are quite like asserts are used today, meaning that a broken contract is a bug (and they might be disabled in release builds, for efficiency), so they shouldn't test anything that may fail in a correct program.

Regards,

Terje

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Testing Invariants in C++ Posted: May 4, 2005 11:07 PM
Reply to this message Reply
> Why would you want to check invariants at the beginning of
> the destructor. What could you do about it at that stage?
> You cant throw an exception.

It indicates a design error which needs to be corrected.

> Similarly I dont understand why Christopher's Wrapper
> class does invariant checking in its destructor. See kinda
> dangerous

It is, I believe, a mistake to check the invariant upon leaving the destructor.

Kristian Dupont

Posts: 22
Nickname: chryler
Registered: Dec, 2003

Re: Testing Invariants in C++ Posted: May 5, 2005 10:51 AM
Reply to this message Reply
>I agree with Mr Lybbert, point (1): it's only necessary to
>check invariants after the method has changed something.

So do I. That is because I see the invariant as a way of convincing myself that _this_ particular class is well behaved. After all, some other thread might be actively destroying my data while I am somewhere in the middle of a method call.
The invariant tells me if I did something in this particular method that broke it.

Flat View: This topic has 11 replies on 1 page
Topic: Contract Enforcement for humanity ... ? Previous Topic   Next Topic Topic: I Hope I Work with Mediocre People


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us