The Quartermaster's Store

My eyes are dim, I cannot see.
I have not brought my specs with me.

Mission impossible?

It's said you can find anything in the Quartermaster's Store, even impossible things like fairy wings and unicorn tears. So that's where I went to find some virtual function templates.

The quartermaster is an old man now. His face is wrinkled, his hair grey, but his mind is sharp and there's a glint in his eye when I explain what I'm looking for. 'Virtual function templates?', he asks rhetorically, 'I think I can help you, but, tell me, what are you going to use them for?'

Persistence required

Several of our applications use information stored in a SQL database. Currently, each program accesses the database directly and there is some undesirable duplication of the read/write functions across those applications. We want to remove this duplication by introducing an Object Store layer which knows how to map the logic layer objects to database tables.

For example, our systems define Users and Groups a bit like the users and groups in Unix operating systems except that a User can only be in one Group and permissions are only associated with Groups. In this design reading a whole Group involves reading a Group record and multiple User records. One application might read the Group record and then, separately, read the corresponding User records; another application might use a SQL join to read the records in a single SQL statement.

A generic Object Store would provide the equivalent of SQL insert, delete, select and update operations, but working with C++ objects rather than database records. So, for the User/Group example, the Object Store would provide a single function that reads a Group object from the database and the several applications would all use it.

Double dispatch

Unit test programs will exercise logic layer components that use the Object Store and in these programs we will want to substitute an in-memory database for the usual on-disk SQL database. Although we could implement a fake version of the SQL database we use, we realised that the existence of an Object Store opens up the possibility of a radically different interface for the in-memory database - an interface with a trivial implementation. For example, instead of using the SQL database C API functions to read records from User and Group tables and building a Group object from the records, the test database could contain ready made Group objects in a std::map<Group_ID,Group> and simply return the result of a map look-up.

With this requirement the implementation of the Object Store functions depends on both the type of the storable object and the type of database that will store it.

Unwelcome visitor

The stock solution to the problem of implementing a double dispatch mechanism in C++ is the Visitor Pattern, as described in the Gang of Four book, Design Patterns [GoF]. Note, however, that the Visitor Pattern is asymmetric: although the Element base class only needs to know the type of the abstract Visitor class, the Visitor class has to provide separate overloaded functions for each concrete Element type. In the case of our Object Store that means that either there must be a Database base class that knows the concrete types of all the Storable objects or there must be a Storable base class that knows the concrete types of all the Databases.

It would be nice to be able to write Listing 1.

    // A persistent store for storable objects.  
    class Object_Store  
    {  
    public:  
      template<typename Storable>  
      virtual insert(Storable const&) = 0;  
      . . .  
    private:  
      . . .  
    };  

If this was possible we could write one concrete Object_Store class that stores objects in a real SQL database on disk and another that stores objects in a test database in memory. An application that uses the real database would not depend on the test database and, conversely, test programs would not depend on the real database. Similarly, any program that only used Group objects would not depend on any other storable objects.

A change of perspective

The quartermaster had listened carefully. 'Try these glasses', he said when I had finished. 'They might give you a different perspective on the problem.' He seemed to over-emphasise the 'spec' in perspective. Was he making a joke, alluding to his notoriously poor eyesight and reminding me of the old scout song? He thrust a battered pair of spectacles towards me. 'Go on', he said, 'Try them.' Hesitantly I took the glasses and settled them on the bridge of my nose. They were surprisingly comfortable. I could see clearly, too. The lenses hadn't changed what I could see in any way I could identify, but things did look different, somehow. 'Now, close your eyes, relax and think about your persistent object store again', said the quartermaster.

Without quite realising how bizarre this was I did as he said; and new thoughts began to take shape in my mind. Virtual functions are implemented by building a table of pointers to functions. Virtual function tables are one dimensional, but for double-dispatch we'd need a two-dimensional table. Furthermore, the size of a virtual function table is fixed at compile time, and we don't want to force applications to contain the full 2D table if they only need a few storable types. So we are looking for a dispatch mechanism that selects different functions according to the types of two parameters and doesn't require a look-up table whose size is determined at compile time.

'Overloading!', I cried, opening my eyes. The quartermaster was startled for a moment, but quickly regained his composure. 'Take your time', he said, 'Think it through.'

Seeing the light

In my Eureka moment I had realised that an Object Store could be implemented without using templates, virtual functions, or even classes. It could just be a collection of overloaded functions that define object ↔ database mappings (Listing 2).

    // Real database mapping functions.  
    void insert(Real_Database&, Group const&);  
    void insert(Real_Database&, User  const&);  
    . . .  
    // Test database mapping functions.  
    void insert(Test_Database&, Group const&);  
    void insert(Test_Database&, User  const&);  
    . . .  

There would, of course, be functions for delete, select and update operations, and functions for many more storable object types. These functions could be organised across source files in several different ways. Perhaps the natural organisation would be to put all the operations that map a particular object type to a particular type of database into a single file. The corresponding object modules could be stored in libraries, perhaps one library for the real database and another for the test database. This way a program that only used a test database wouldn't depend on a real database; and a program that used Group objects wouldn't depend on unrelated storable object types.

A fly in the ointment

Following the quartermaster's advice I started to think about how the object mapper functions would be used. Typically, the logic layer classes would access the database through an abstract interface. The application programs would pass a real database to the logic layer functions and the unit tests would pass a test database instead. So, for example, a function that creates a new Group might look like Listing 3.

    void create_group(Database& database)  
    {  
        Group new_group = ...;  
        insert(concrete(database), new_group);  // ???
    }

But, calling one of the object mapper functions requires a concrete database type and that can't be recovered from the abstract interface unless there is a suitable virtual function in the Database base class. So it looked as though we'd need an Object_Store class with virtual function template members after all.

A helping hand

I was gutted and my disappointment must have shown on my face because the quartermaster chose that moment to drop a big hint. 'Could you have a member function template that forwards to a virtual function?', he asked. I closed my eyes again and visualised Listing 4.

    class Object_Store  
    {  
    public:  
      template<typename Storable>  
      void insert(Storable const& storable)  
      {  
        insert_impl( Any_Storable(storable) );  
      }  
 
      . . .  
    private:  
      virtual void insert_impl(Any_Storable) = 0;  
      . . .  
    };

The Any_Storable class would have to be a wrapper that retains the concrete Storable type and provides a mechanism for its recovery. There is just such a class in the Boost library: boost::any. The insert_impl() functions would recover the Storable type and call the appropriate object mapper function.

The type of the object in a boost::any is provided by the any::type() function, which returns a std::type_info const&. Somehow the insert_impl() function must use this to generate a reference to the storable object held within the boost::any object. The insert_impl() function can't do this directly because it doesn't itself know the concrete type of the Storable object. But it can look up and call a function that does know the concrete Storable type. For example, the Object_Store class might store a function registry in the form of a std::map<std::type_info const*, insert_function*> where insert_function is a suitable function type.

The functions in the function registry also need to know the concrete database type so that they can invoke the corresponding object mapper functions. Providing the function registry, therefore, must be the responsibility of the concrete Object_Store classes. Listing 5 shows an example of an Object Store class that accesses a SQL database via the Database Template Library [DTL].

    class Real_Object_Store : public Object_Store  
    {  
    public:  
      Real_Object_Store(  
         std::string const& connection_parameters);  
      . . .  
 
    private:  
      virtual void insert_impl(boost::any storable);  
      dtl::DBConnection db;  
      typedef  
        std::map  
        <  
          std::type_info const*,  
          void (*)(dtl::DBConnection&,  
             boost::any const&)  
        >  
        function_map_type;  
 
      function_map_type insert_function_map;  
      . . .  
    };  

The database is represented by a dtl::DBConnection object, which is initialised from the connection parameters passed to the constructor as a string. The function registry stores pointers to functions taking dtl::DBConnection& and boost::any const& parameters. The insert_impl() function can then be implemented as shown in Listing 6.

    void Real_Object_Store::insert_impl(  
       boost::any storable)  
    {  
      function_map_type::iterator i =  
         insert_function_map.find(&storable.type());  
      if (i == insert_function_map.end())  
      {  
        // Report insert function look-up failure.  
      }  
      else  
      {  
        ((*i).second)(db, storable);  
      }  
    }  

Each function in the function registry handles a particular type of storable object; it simply recovers that type from the boost::any and forwards to the appropriate overloaded object mapper function. The registry functions are identical except for the concrete Storable type, so they can be generated from a trivial function template as shown in Listing 7. Note that the any_cast will not fail if the function registry has been correctly initialised.

    template< typename Storable >  
    inline  
    void insert_any(dtl::DBConnection& db,  
       boost::any const& storable)  
    {  
      insert(db,  
         boost::any_cast<Storable const&>(storable));  
    }  

Unlike designs based on virtual functions the function registry needs to be populated at run time and this is the responsibility of the programmer (not the compiler). That is the price we must pay to avoid coupling the Object Store source files to all the concrete Storable types.

Mission accomplished

Had I succeeded in my quest? Well, virtual function templates don't exist, but we can emulate them with a combination of member function templates that forward to a virtual function and function registries built at run-time. That was more than good enough for me.

I handed the glasses back to the quartermaster, thanked him and shook his hand warmly. 'I'm sorry that I couldn't get any virtual function templates for you', he said. 'Not at all', I replied. 'You have given me something much more valuable - a deeper understanding of an important design problem, complete with a practical solution.' But he wouldn't take any money, so I pushed a note into his charity collection box and bid him farewell.

References

[DTL] The Database Template Library is available from SourceForge at http://dtemplatelib.sourceforge.net/. There's also an article by one of its co-authors in Overload 43 (http://accu.org/index.php/journals/445).

[GoF] Design Patterns - Elements of Reusable Object-Oriented Software, by Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides. ISBN 0-201-63361-2.

[Love] For an Overload article applying the 'virtual function template' technique to iterators see http://accu.org/index.php/journals/479.