🚀 go-pugleaf

Howard Hinnant <hinnant@antispam.metrowerks.com> wrote:

> STL Container Invariants
> ========================
> 
> Most non-trivial C++ classes have what are called /class invariants/.
> My well-dog-eared copy of Bjarne Stroustrup's excellent "The C++
> Programming Language 3rd ed" has a nice summary of what a class
> invariant is in section 24.3.7.1.  In a nutshell, a class invariant is
> a self consistent state that is set up by an object's constructor, and
> maintained throughout the lifetime of the object.
> 
> A simple and convenient example of a class invariant can be shown with
> std::vector.  One of the invariants of this class is (this is not the
> only invariant for vector):
> 
>     For any vector v:  v.size() <= v.capacity()
> 
> Well duh!  Of course we all know that from our careful study of
> vectors.  And we count on the implementor of our std::vector to make
> sure this invariant will always hold.  But ...
> 
> As the implementor of the std::vector in MSL C++, I am going to give
> you the unfortunate truth:  Even in a 100% guaranteed bug-free vector,
> I can not absolutely promise that the size() will /always/ be less than
> or equal to capacity.  The reason?  Code unrelated to vector might
> accidently overwrite parts of the vector.  Or perhaps client code could
> misuse the vector in such a way as to invalidate a class invariant.
> 
> Bugs happen!
> 
> Starting with Pro 8, (almost*) all of the MSL C++ containers have a new
> member function added:
> 
>     bool invariants() const;
> 
> [*Footnote:  The Pro 8 basic_string is lacking this method, but not for
> long...]
> 
> This is an extension to the standard, so you can not count on it being
> portable.  But it sure can be useful.  You can call this function at
> any time, and the container will go through a diagnostic self check. 
> If any of the container's invariants have been compromised,
> invariants() will return false, else it will return true.  This is most
> easily used in conjunction with an assert statement:
> 
>     assert(c.invariants());
> 
> Below are some brief examples that demonstrate the use of the
> invariants function:
> 
> #include <vector>
> #include <cassert>
> 
> int main()
> {
>     int ia[4];
>     std::vector<int> v(4);
>     assert(v.invariants());
>     for (int i = 1; i <= 4; ++i)
>         ia[i] = 0;
>     assert(v.invariants());
> }
> 
> After construction, v's invariants are checked and everything looks ok.
> Then the raw array is initialized to 0.  v's invariants are checked
> again and ... oops!
> 
> Assertion (v.invariants()) failed in "main.cpp", line 11
> 
> The for-loop indexes from 1 to 4 instead of from 0 to 3.  The last
> ia[i] initialization happens to step on v (such behavior is undefined
> so stepping on v can not be guaranteed).
> 
> Here's an example where one list violates another by accidently writing
> to *end():
> 
> #include <list>
> #include <cassert>
> 
> int main()
> {
>     std::list<int> list1, list2;
>     assert(list1.invariants());
>     assert(list2.invariants());
>     std::list<int>::iterator i = list1.end();
>     *i = 200;
>     assert(list1.invariants());
>     assert(list2.invariants());
> }
> 
> Assertion (list2.invariants()) failed in "main.cpp", line 12
> 
> And yet another example caused by compromising the order of a set's
> elements:
> 
> #include <set>
> #include <cassert>
> 
> int main()
> {
>     std::set<int> s;
>     for (int i = 0; i < 100; ++i)
>         s.insert(i);
>     assert(s.invariants());
>     std::set<int>::iterator i = s.begin();
>     const_cast<int&>(*i) = 3;
>     assert(s.invariants());
> }
> 
> Assertion (s.invariants()) failed in "main.cpp", line 12
> 
> All of the "bugs" demonstrated here are extremely simple and contrived
> for the purposes of a clarity.  We all know that real bugs are much
> harder to find.  It is our hope that invariants() will make the task of
> finding bugs much easier.

 Seems like a polution of standard containers, but I can live with that.
I suppose one should provide a templated function outside of namespace
std, that does the actual call to the 'public' member.  Then
modifacation is easier to handle.

namespace Metrowerks // anything but std
{
  template <class C>
  inline invariant(C &x) {return x.invariant();}
}
 is a first step in that direction.