Interpreting "Supporting the 'Cheshire Cat' Idiom"

AN:

One of the nice thing about being Treasurer of the ACCU was the opportunity to learn by rubbing shoulders with "real" programmers. Often after committee meetings or phone calls with officers on Association business we would drift into talking about programming. One such conversation with AG lead to the idea that we could take his article on the Cheshire Cat and run a recorded discussion where I could ask the sort of question that maybe a student/learner would ask a Tutor or mentor. What you see below is the result, I hope that by asking some questions I learn from the answers and that maybe others who are to shy to ask will also learn. I also hope that this project will reassure potential authors for CVu and Overload that there is a need for teaching as well as cutting edge articles.

The Cheshire Cat idiom is a great solution to a set of problems that have existed since the pre-history of C++. This idiom first emerged in the late '80s in a cross-platform GUI class library called CommonView and was described by John Carolan (" Constructing bullet-proof classes" - Proceedings: C++ at Work '89 - SIGS). It has been reinvented a number of times since and is also known as "compilation firewall" and as "pimpl". The "Gang of Four" classifies it as a special case of the "Bridge" pattern (ISBN 0-201-63361-2 Design Pattern - Addison-Wesley).

AN:

Is this really a pattern? I had got the impression that patterns were far more sophisticated and had avoided them as being beyond my comprehension. What actually is a pattern? How much do I need to know about them?"

AG:

What constitutes a "Pattern" is a subject of debate amongst the experts. I'd be happy calling "Bridge" a pattern, but I use the less ambitious term "idiom" where both the issues to be resolved and the solution are language specific - which is the case with "Cheshire Cat". Patterns are not inherently hard to understand - they are descriptions of recurring design problems and corresponding "neat" solutions. Although some presentations of patterns can be difficult much of the material will give the experienced developer the warm glow of familiarity (I said they were recurring problems) or the warm glow of embarrassment upon seeing a much neater solution than the one she's just implemented."

More recently I have examined the development of this idiom in an article Ending with the Grin in EXE magazine (March 2000), the latter part of the EXE article describes the use of a smart pointer - arg::grin_ptr<> - that simplifies the writing of "Cheshire Cat" classes. The current article discusses the implementation of this smart pointer.

However, before looking at this template class let us make review the problems the "Cheshire Cat" idiom solves and the way in which it resolves them. These problems stem from three areas:

Ensuring that a header file includes nothing that the client code needn't be aware of. (In the case of CommonView, this includes the native windowing APIs.)

Making it possible to distribute updates to object code library without requiring the client code to be recompiled. If a class definition (or anything else in a header) changes, then any compilation unit that includes it must be recompiled.

Protecting intellectual property by concealing implementation techniques used.

Which of these is most important to you will differ according to circumstance, but the "Cheshire Cat" idiom addresses them all.

The "classical" Cheshire Cat

When Glockenspiel (the suppliers of CommonView) started developing their cross-platform GUI library they were influenced by all three of the above reasons for hiding the implementation. Here is a simplified telephone list class implemented in the style of the CommonView library:

struct phone_list_implementation;

class phone_list
{
public:
  phone_list(const char *name);
  phone_list(const phone_list& rhs);
  phone_list& operator
              (const phone_list& rhs);
  ~phone_list();

  const char* list_name();
  const char* find_number
                (const char *person);
  void add(const char *name
        , const char *number);
private:
  phone_list_implementation* grin;
};

Note the need for a copy constructor and assignment operator. These are required because phone_list owns the phone_list_implementation to which it holds a pointer. (The default behaviour of just copying the pointer value is obviously inappropriate.)

Once you've written a few classes using this idiom it will occur to you that you are writing the same functions again and again to manage the implementation. Specifically the copy constructor, assignment operator and destructor of a Cheshire Cat class are generic - they always look the same, they only differ in the types of the interface and implementation classes.

This sounds like a job for a template. A template that looks after an implementation object allocated on the heap, and ensures it is copied or deleted when appropriate. It is tempting to reach for the standard library, but the closest thing we find there is auto_ptr<> .

AN:

I can see why we need to be careful about copy and assignment operations but do we have to as careful if we can promise that we only create one instance of phone list and that it is not copied or assigned by our code. In other words will the compiler sneak in copy or assignment operation unbeknown to the code writer. I accept that when writing a library for general use this would be an unacceptable limitation.

AG:

I would like to say that this is the difference between an amateur approach and that of a professional - because you can say it in the code that you won't be copying or assigning an object. By declaring a private copy constructor and assignment operator (and not implementing them) you'll ensure either a compile error or a link error if you break this guarantee. Sadly, if I were to say such a thing I'd also have to admit that there are some very highly paid "amateurs" in the industry.

If the author of a class fails to declare these methods, then the compiler generates inline versions based on memberwise copying - and copying a pointer member rarely gives the correct result.

On your final point about a library for general use - even when I write "throw away" code for quick & dirty utilities I find that someone on the project will mine it for solutions to their problems and re-apply it in situations I cannot predict. (I admit that sometimes that someone is me months or years later - but I am more careful than most about ensuring that the code works in the new context.) It is simpler to ensure that the code cannot be abused than to enter a debate about the sanity of this practice."

AN:

A slight diversion here, is this the reason that for some of the failure of code re-use? Have people written code with specific applications in mind and then the code has just not been sufficiently widely applicable for re-use?

AG:

I think the main reason for the failure of re-use is the failure of management to identify the development of reusable components as a separately resourced project. It is too often something that is expected to happen for free as a side effect of the first project that needs to incorporate a facility. Either the necessary resources to tackle the more general solution are not made available in the project budget, or if they are available they are expended on work with a more direct application to the problem in hand.

On std::auto_ptr<>

Although auto_ptr<> does not meet our current needs it is instructive to know why since at least one of the reasons is not immediately obvious…

The standard library auto_ptr<> has what I will politely describe as "interesting" copy semantics. Specifically, if one auto_ptr<> is assigned (or copy constructed) from another then they are both changed - the auto_ptr<> that originally owned the object loses ownership and becomes 0. This is a trap for the unwary! There are situations that call for this behaviour, but on this occasions the copy semantics cause a problem.

If we substitute auto_ptr<implementation> for implementation* in the phone_list class we will find that we still need to write the copy constructor and assignment operator. (To avoid an implementation being passed from one phone_list to another.) Fortunately the compiler detects the non-standard copy and assignment of the auto_ptr<> data member and issue a diagnostic to prompt us to write these functions.

A subtler problem is that we also need to write the destructor - if we don't, the one the compiler silently generates for us will not correctly destroy the implementation . This is because by default the phone_list destructor is generated by the compiler without having seen the class definition for implementation . This forces it to instantiate the auto_ptr<> destructor without having seen the class definition for implementation . If implementation has a non-trivial destructor this leads to "undefined behaviour". A good compiler may give a warning about deleting an incomplete type. But the language standard only allows the compiler to refuse to compile the code (a helpful form of "undefined behaviour") if there is a non-trivial destructor - and the compiler cannot know this at compile time without first seeing the definition.

Using auto_ptr<> would save us nothing - we would still need to write the copy constructor, assignment operator and destructor.

AN:

Every mention of auto_ptr<> in books and magazines seems so loaded with caveats and warnings that I wonder what use is it to a learning programmer? Just to reassure me can someone give me an example of where auto_ptr<> can be safely used.

AG:

I refuse to defend auto_ptr ! I believe that its inclusion in the standard library as the sole representative of the possible range of smart pointers was a mistake. (If there had been half a dozen others - see my website for a few of the possibilities, or none, then I would have less complaint.) It distracts the learning programmer from the need to identify a suitable smart pointer for the needs of the moment.

Sorry, to take up your challenge:

void foo()
{
  const auto_ptr<bar> pbar(condition ? 
        new default_bar() 
      : new alternate_bar());
  . . .
  pbar->f();
  . . .
};

AN:

So really auto_ptr<> is but one example of a concept of smart pointers and I should learn more about this concept. Then I use or design the proper pointer for a job, not try (and fail!!!) to make the job suit auto_ptr<> ?

AG:

Precisely. In fact that is the starting point for the current article - there was a discussion on comp.lang.c++ moderated where the participants were discussing the techniques needed to make the "Cheshire Cat" job suitable for auto_ptr<> . I realised that, since the last time I considered the matter, I had acquired the techniques necessary to implement a suitable smart pointer type. So I did.

arg::grin_ptr<>

Let us suppose for a moment that such a smart pointer exists and is called arg::grin_ptr<> . This would allow the phone_list class to be rewritten as shown in listing 1.

Listing 1: Using arg::grin_ptr<>

class phone_list
{
public:
  explicit phone_list(std::string name);

  std::string name() const;

  std::pair<bool, std::string>
      number(std::string person) const;

  phone_list& add (std::string name,
                 std::string number);
private:
  class implementation;
  arg::grin_ptr<implementation> grin;
};

Note that there is no longer a need to supply the copy constructor, assignment operator, or destructor as we are assuming that the necessary logic is supplied by the grin_ptr<> template. I have also taken the opportunity to use a more contemporary style of C++, but the ideas are the same. The resulting simplification looks good, but how can it be achieved?

Implementing arg::grin_ptr<>

The principle problem to overcome in implementing grin_ptr<> is the last point mentioned in the discussion of auto_ptr<> - how to cope with deleting an incomplete type. The destructor of grin_ptr<> cannot be a simple " delete p; " because at the point of instantiation the pointer is to an "incomplete type".

To avoid this I make use of the fact that the constructor for grin_ptr<> is instantiated in the implementation file, where the class definition for implementation resides. At this point I force the compiler to generate a deletion function using a trick I first saw in Richard Hickey's article Callbacks in C++ Using Template Functors (C ++ Gems ISBN 1 884842 37 2): the constructor stores a pointer to this function in the grin_ptr<> . This provides a safe method for the destructor to delete the object it owns. The point of passing around function pointers instead of the apparently more natural use of virtual member functions is that everything can be done "by value" and no dynamic allocation is required.

A similar function is used for copying the object, so because it contains two function pointers a grin_ptr<> is a bit bigger than a raw pointer but this isn't likely to be an issue in most uses. The complete code for grin_ptr<> is shown in listing 2:

AN:

This is where I hit my intellectual brick wall!!!

Let me get this straight, we need a pointer to an object but we must have very specific action when we copy a class/structure containing the pointer. Also when a class/structure that contains the pointer has its destructor called then we need to call the destructor of what is pointed to?

AG:

Correct, you are with me so far!

AN:

Looking at the code I have problems at two intermingled levels, the structure and the detail of each line. I have put some comments in the code.

I see that p is the "real" pointer but am rather confused. I assume that the function calls in Listing 1 are implemented as calls to the thing pointed to by p . Thus the function declared as

std::pair<bool, std::string>
       number(std::string person) const;

will have code like

std::pair<bool, std::string>
   phonelist::number(std::string person)
{
  return p->ps_number(person) ;
}

AG:

Looking at the original article I see that I failed to mention that the members functions just forward to the implementation class. Thanks for pulling me up on this - it is very easy to misjudge an audience and assume background knowledge. Since you are unfamiliar with the idiom you did well to get this close. Only a small correction is required - remember that phonelist can only "see" the externals - the actual code is:

std::pair<bool, std::string>
  phonelist::number(std::string person)
{
  return grin->number(person);
}

This (behind the scenes, and inlined in a manner that ought to generate extra no code) calls the indirection operator which replaces the sub expression " grin-> " with the value of grin::p . Of course, thinking at this level is akin to thinking about which controls you are using when you are driving - liable to cause accidents.

grin_ptr is designed to act "just like" a pointer in all relevant ways while taking the burden of ownership management. Naturally, "all relevant ways" does not include such things as support for pointer arithmetic since this is inappropriate for pointers used in implementing "Cheshire Cat". (Acting "just like a pointer in all relevant ways" is the signature of a "smart pointer".)

By using a compatible substitute for a "real" pointer you save yourself the need to write boilerplate code, everything else is the same. (We are both old enough to remember manual chokes, the advent of automatic chokes and/or fuel injection in popular models did not significantly change the way we drive, just removed a source of errors.)

Listing 2: arg::grin_ptr<>

template<typename p_type>
class grin_ptr
{
// Pointers to utility functions
  typedef void (*delete_ftn)(p_type* p);
  typedef p_type* 
          (*copy_ftn)(const p_type* p);
public:
  explicit grin_ptr(p_type* pointee) 
    : do_copy(&my_copy_ftn), p(pointee), do_delete(my_delete_ftn) {}

AN:

Why do we use explicit here? The other statements are merely initialisers for the various members?

AG:

To answer the second question first: yes, this is the syntax for initialising the class members. The reason for using explicit is to prevent the user could accidentally converting a pointer (of type T* say) to a smart pointer (type grin_ptr<T> ) since the temporary smart pointer would assume ownership of the original, and delete it at a point the user does not expect.

  grin_ptr(const grin_ptr& rhs);

AN:

This is the copy constructor?

AG:

Yes.

  ~grin_ptr() throw() { do_delete(p); }

AN:

This is the destructor which calls do_delete .

  const p_type* get() const { return p; }
  p_type* get() { return p; }
  const p_type* operator->() const {
    return p; 
  }
  p_type* operator->() { return p; }
  const p_type& operator*() const { 
    return *p; 
}

AN:

are we overloading the operator ' * ' here?

AG:

Yes, this is the dereference operator.

AN:

Glad you reminded me, most of my work is numerical and I always get confused by the use of " * " to dereference and to multiply.

  p_type& operator*() { return *p; }
  void swap(grin_ptr& with) throw() { 
    p_type* pp = p; 
    p = with.p; with.p = pp; 
  }
    grin_ptr& operator= (
                const grin_ptr& rhs);
private:
  copy_ftn  do_copy;
  p_type*    p;
  delete_ftn  do_delete;

AN:

The two lines copy_ftn and delete_ftn confuse me. copy_ftn and delete_ftn are what? Did I miss their definition? They seem to be pointer like but are they?

AG:

If you look back to the top of the class definition you will see a couple of typedef s. These declare copy_ftn and delete_ftn as pointers to functions. I cannot think of a good reason for separating the declarations from the point of use like this - I should probably move them to this vicinity.

  static void my_delete_ftn(p_type* p) {
    delete p;
  }

AN:

What is the relationship between my_delete_ftn and delete_ftn . Are they both the same type of object?

AG:

They are related, but not quite the same, delete_ftn is a type whose instances can hold a pointer to a function with they same signature as my_delete_ftn .

  static p_type* my_copy_ftn(
                    const p_type* p) {
    return deep_copy(p);
  }
};
template<typename p_type>
inline grin_ptr<p_type>::grin_ptr(
              const grin_ptr& rhs)
    :  do_copy(rhs.do_copy),
      p(do_copy(rhs.p)),
      do_delete(rhs.do_delete) { }

AN:

The impression is that there is a lot of work going on in the constructor, exactly what is happening?

AG:

The grin_ptr has three data members, a pointer to a function that knows how to make copies of the subject, a pointer to the subject and a pointer to a function that knows how to delete the subject. In this copy constructor they are initialised by copying the function pointers and using the first of these functions to copy the subject.

template<typename p_type>
inline grin_ptr<p_type>& grin_ptr<p_type>::operator=(
                const grin_ptr& rhs){
  p_type* pp = do_copy(rhs.p);
  do_delete(p);
  p = pp;
  return *this;
}

Deep copying with arg::deep_copy()

The copying mechanism is in fact a bit more flexible than the current discussion would indicate, since the copying method has also been factored out into the arg::deep_copy() algorithm but if you do nothing special then copying will take place using new implementation(*p); as you probably expect.

The arg::deep_copy() algorithm allows a clone() method (or any other name) to be used to copy the owned object. The code for deep_copy() is shown in listing 3:

Listing 3: The arg::grin_ptr<> Algorithm

struct Cloneable {};

template<class p_type>
inline p_type* deep_copy(const p_type* p, const void*) 
{
  return p ? new p_type(*p) : 0;
}

template<class p_type>
inline p_type* deep_copy(const p_type *p, const cloneable *)
{
  return p ? p->clone() : 0;
}

template<class p_type>
inline p_type* deep_copy(const p_type *p, const Cloneable *)
{
  return p ? p->makeClone() : 0;
}

template<class p_type>
inline p_type* deep_copy(const p_type* p) 
{
  return deep_copy(p, p);
}

The effect is that: any class that inherits from arg::clonable() will be copied by p->clone(); and any class that inherits from arg::Cloneable will be copied using p->makeClone() . (These two versions exist to support both my currently favoured naming style and the one that I am required to use at work.) In addition any class that has a deep_copy() algorithm defined in a suitable namespace will be copied using it in preference to the above.

In conclusion

In this article I have shown how it is possible to remove some of the repetitive work from the development of "Cheshire Cat". In addition, I have put a sample implementation of grin_ptr<> into the "arglib" library on my website: ( http://www.octopull.demon.co.uk/arglib/ ).

It would be possible to develop grin_ptr<> further and to implement a regime known as "copy on write". "Copy on write" shares the implementation between interface classes unless or until one of them makes a change ("writes") to the implementation. Only at this point is a copy taken of the implementation object.