path: root/indra/llcommon/lldoubledispatch.h

/**
 * @file   lldoubledispatch.h
 * @author Nat Goodspeed
 * @date   2008-11-11
 * @brief  function calls virtual on more than one parameter
 * 
 * $LicenseInfo:firstyear=2008&license=viewerlgpl$
 * Second Life Viewer Source Code
 * Copyright (C) 2010, Linden Research, Inc.
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation;
 * version 2.1 of the License only.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 * 
 * Linden Research, Inc., 945 Battery Street, San Francisco, CA  94111  USA
 * $/LicenseInfo$
 */

#if ! defined(LL_LLDOUBLEDISPATCH_H)
#define LL_LLDOUBLEDISPATCH_H

#include <list>
#include <boost/shared_ptr.hpp>
#include <boost/function.hpp>
#include <boost/bind.hpp>
#include <boost/ref.hpp>

/**
 * This class supports function calls which are virtual on the dynamic type of
 * more than one parameter. Specifically, we address a limited but useful
 * subset of that problem: function calls which accept two parameters, and
 * select which particular function to call depending on the dynamic type of
 * both.
 * 
 * Scott Meyers, in More Effective C++ (Item 31), talks about some of the perils
 * and pitfalls lurking down this pathway.  He discusses and dismisses the
 * straightforward approaches of using single-dispatch virtual functions twice,
 * and of using a family of single-dispatch virtual functions which each examine
 * RTTI for their other parameter.  He advocates using a registry in which you
 * look up the actual types of both parameters (he uses the classes' string names,
 * via typeid(param).name()) to obtain a pointer to a free (non-member) function
 * that will accept this pair of parameters.
 * 
 * He does point out that his approach doesn't handle inheritance.  If you have a
 * registry entry for SpaceShip, and you have in hand a MilitaryShip (subclass of
 * SpaceShip) and an Asteroid, you'd like to call the function appropriate for
 * SpaceShips and Asteroids -- but alas, his lookup fails because the class name
 * for your MilitaryShip subclass isn't in the registry.
 * 
 * This class extends his idea to build a registry whose entries can examine the
 * dynamic type of the parameter in a more flexible way -- using dynamic_cast<>
 * -- thereby supporting inheritance relationships.
 * 
 * Of course we must allow for the ambiguity this permits. We choose to use a
 * sequence container rather than a map, and require that the client code
 * specify the order in which dispatch-table entries should be searched. The
 * result resembles the semantics of the catch clauses for a try/catch block:
 * you must code catch clauses in decreasing order of specificity, because if
 * you catch ErrorBaseClass before you catch ErrorSubclass, then any
 * ErrorSubclass exceptions thrown by the protected code will always match
 * ErrorBaseClass, and you will never reach your catch(ErrorSubclass) clause.
 * 
 * So, in a similar way, if you have a specific routine to process
 * MilitaryShip and Asteroid, you'd better place that in the table @em before
 * your more general routine that processes SpaceShip and Asteroid, or else
 * the MilitaryShip variant will never be called.
 *
 * @todo This implementation doesn't attempt to deal with
 * <tt>const</tt>-correctness of arguments. Our container stores templated
 * objects into which the specific parameter types have been "frozen." But to
 * store all these in the same container, they are all instances of a base
 * class with a virtual invocation method. Naturally the base-class virtual
 * method definition cannot know the <tt>const</tt>-ness of the particular
 * types with which its template subclass is instantiated.
 *
 * One is tempted to suggest four different virtual methods, one for each
 * combination of @c const and non-<tt>const</tt> arguments. Then the client
 * will select the particular virtual method that best fits the
 * <tt>const</tt>-ness of the arguments in hand. The trouble with that idea is
 * that in order to instantiate the subclass instance, we must compile all
 * four of its virtual method overrides, which means we must be prepared to
 * pass all four combinations of @c const and non-<tt>const</tt> arguments to
 * the registered callable. That only works when the registered callable
 * accepts both parameters as @c const.
 *
 * Of course the virtual method overrides could use @c const_cast to force
 * them to compile correctly regardless of the <tt>const</tt>-ness of the
 * registered callable's parameter declarations. But if we're going to force
 * the issue with @c const_cast anyway, why bother with the four different
 * virtual methods? Why not just require canonical parameter
 * <tt>const</tt>-ness for any callables used with this mechanism?
 *
 * We therefore require that your callable accept both params as
 * non-<tt>const</tt>. (This is more general than @c const: you can perform @c
 * const operations on a non-<tt>const</tt> parameter, but you can't perform
 * non-<tt>const</tt> operations on a @c const parameter.)
 *
 * For ease of use, though, our invocation method accepts both params as @c
 * const. Again, you can pass a non-<tt>const</tt> object to a @c const param,
 * but not the other way around. We take care of the @c const_cast for you.
 */
// LLDoubleDispatch is a template because we have to assume that all parameter
// types are subclasses of some common base class -- but we don't have to
// impose that base class on client code.  Instead, we let IT tell US the
// common parameter base class.
template<class ReturnType, class ParamBaseType>
class LLDoubleDispatch
{
    typedef LLDoubleDispatch<ReturnType, ParamBaseType> self_type;

public:
    LLDoubleDispatch() {}

    /**
     * Call the first matching entry.  If there's no registered Functor
     * appropriate for this pair of parameter types, this call will do
     * @em nothing!  (If you want notification in this case, simply add a new
     * Functor for (ParamBaseType&, ParamBaseType&) at the end of the table.
     * The two base-class entries should match anything that isn't matched by
     * any more specific entry.)
     *
     * See note in class documentation about <tt>const</tt>-correctness.
     */
    inline
    ReturnType operator()(const ParamBaseType& param1, const ParamBaseType& param2) const;

    // Borrow a trick from Alexandrescu:  use a Type class to "wrap" a type
    // for purposes of passing the type itself into a template method.
    template<typename T>
    struct Type {};

    /**
     * Add a new Entry for a given @a Functor. As mentioned above, the order
     * in which you add these entries is very important.
     *
     * If you want symmetrical entries -- that is, if a B and an A can call
     * the same Functor as an A and a B -- then pass @c true for the last
     * parameter, and we'll add a (B, A) entry as well as an (A, B) entry. But
     * your @a Functor can still be written to expect exactly the pair of types
     * you've explicitly specified, because the Entry with the reversed params
     * will call a special thunk that swaps params before calling your @a
     * Functor.
     */
    template<typename Type1, typename Type2, class Functor>
    void add(const Type<Type1>& t1, const Type<Type2>& t2, Functor func, bool symmetrical=false)
    {
        insert(t1, t2, func);
        if (symmetrical)
        {
            // Use boost::bind() to construct a param-swapping thunk. Don't
            // forget to reverse the parameters too.
            insert(t2, t1, boost::bind(func, _2, _1));
        }
    }

    /**
     * Add a new Entry for a given @a Functor, explicitly passing instances of
     * the Functor's leaf param types to help us figure out where to insert.
     * Because it can use RTTI, this add() method isn't order-sensitive like
     * the other one.
     *
     * If you want symmetrical entries -- that is, if a B and an A can call
     * the same Functor as an A and a B -- then pass @c true for the last
     * parameter, and we'll add a (B, A) entry as well as an (A, B) entry. But
     * your @a Functor can still be written to expect exactly the pair of types
     * you've explicitly specified, because the Entry with the reversed params
     * will call a special thunk that swaps params before calling your @a
     * Functor.
     */
    template <typename Type1, typename Type2, class Functor>
    void add(const Type1& prototype1, const Type2& prototype2, Functor func, bool symmetrical=false)
    {
        // Because we expect our caller to pass leaf param types, we can just
        // perform an ordinary search to find the first matching iterator. If
        // we find an existing Entry that matches both params, either the
        // param types are the same, or the existing Entry uses the base class
        // for one or both params, and the new Entry must precede that. Assume
        // our client won't register two callables with exactly the SAME set
        // of types; in that case we'll insert the new one before any earlier
        // ones, meaning the last one registered will "win." Note that if
        // find() doesn't find any matching Entry, it will return end(),
        // meaning the new Entry will be last, which is fine.
        typename DispatchTable::iterator insertion = find(prototype1, prototype2);
        insert(Type<Type1>(), Type<Type2>(), func, insertion);
        if (symmetrical)
        {
            insert(Type<Type2>(), Type<Type1>(), boost::bind(func, _2, _1), insertion);
        }
    }

    /**
     * Add a new Entry for a given @a Functor, specifying the Functor's leaf
     * param types as explicit template arguments. This will instantiate
     * temporary objects of each of these types, which requires that they have
     * a lightweight default constructor.
     *
     * If you want symmetrical entries -- that is, if a B and an A can call
     * the same Functor as an A and a B -- then pass @c true for the last
     * parameter, and we'll add a (B, A) entry as well as an (A, B) entry. But
     * your @a Functor can still be written to expect exactly the pair of types
     * you've explicitly specified, because the Entry with the reversed params
     * will call a special thunk that swaps params before calling your @a
     * Functor.
     */
    template <typename Type1, typename Type2, class Functor>
    void add(Functor func, bool symmetrical=false)
    {
        // This is a convenience wrapper for the add() variant taking explicit
        // instances.
        add(Type1(), Type2(), func, symmetrical);
    }

private:
    /// This is the base class for each entry in our dispatch table.
    struct EntryBase
    {
        virtual ~EntryBase() {}
        virtual bool matches(const ParamBaseType& param1, const ParamBaseType& param2) const = 0;
        virtual ReturnType operator()(ParamBaseType& param1, ParamBaseType& param2) const = 0;
    };

    /// Here's the template subclass that actually creates each entry.
    template<typename Type1, typename Type2, class Functor>
    class Entry: public EntryBase
    {
    public:
        Entry(Functor func): mFunc(func) {}
        /// Is this entry appropriate for these arguments?
        virtual bool matches(const ParamBaseType& param1, const ParamBaseType& param2) const
        {
            return (dynamic_cast<const Type1*>(&param1) &&
                    dynamic_cast<const Type2*>(&param2));
        }
        /// invocation
        virtual ReturnType operator()(ParamBaseType& param1, ParamBaseType& param2) const
        {
            // We perform the downcast so callable can accept leaf param
            // types, instead of accepting ParamBaseType and downcasting
            // explicitly.
            return mFunc(dynamic_cast<Type1&>(param1), dynamic_cast<Type2&>(param2));
        }
    private:
        /// Bind whatever function or function object the instantiator passed.
        Functor mFunc;
    };

    /// shared_ptr manages Entry lifespan for us
    typedef boost::shared_ptr<EntryBase> EntryPtr;
    /// use a @c list to make it easy to insert
    typedef std::list<EntryPtr> DispatchTable;
    DispatchTable mDispatch;

    /// Look up the location of the first matching entry.
    typename DispatchTable::const_iterator find(const ParamBaseType& param1, const ParamBaseType& param2) const
    {
        // We assert that it's safe to call the non-const find() method on a
        // const LLDoubleDispatch instance. Cast away the const-ness of 'this'.
        return const_cast<self_type*>(this)->find(param1, param2);
    }

    /// Look up the location of the first matching entry.
    typename DispatchTable::iterator find(const ParamBaseType& param1, const ParamBaseType& param2)
    {
        return std::find_if(mDispatch.begin(), mDispatch.end(),
                            boost::bind(&EntryBase::matches, _1,
                                        boost::ref(param1), boost::ref(param2)));
    }

    /// Look up the first matching entry.
    EntryPtr lookup(const ParamBaseType& param1, const ParamBaseType& param2) const
    {
        typename DispatchTable::const_iterator found = find(param1, param2);            
        if (found != mDispatch.end())
        {
            // Dereferencing the list iterator gets us an EntryPtr
            return *found;
        }
        // not found
        return EntryPtr();
    }

    // Break out the actual insert operation so the public add() template
    // function can avoid calling itself recursively.  See add() comments.
    template<typename Type1, typename Type2, class Functor>
    void insert(const Type<Type1>& param1, const Type<Type2>& param2, Functor func)
    {
        insert(param1, param2, func, mDispatch.end());
    }

    // Break out the actual insert operation so the public add() template
    // function can avoid calling itself recursively.  See add() comments.
    template<typename Type1, typename Type2, class Functor>
    void insert(const Type<Type1>&, const Type<Type2>&, Functor func,
                typename DispatchTable::iterator where)
    {
        mDispatch.insert(where, EntryPtr(new Entry<Type1, Type2, Functor>(func)));
    }

    /// Don't implement the copy ctor.  Everyone will be happier if the
    /// LLDoubleDispatch object isn't copied.
    LLDoubleDispatch(const LLDoubleDispatch& src);
};

template <class ReturnType, class ParamBaseType>
ReturnType LLDoubleDispatch<ReturnType, ParamBaseType>::operator()(const ParamBaseType& param1,
                                                                   const ParamBaseType& param2) const
{
    EntryPtr found = lookup(param1, param2);
    if (found.get() == 0)
        return ReturnType();    // bogus return value

    // otherwise, call the Functor we found
    return (*found)(const_cast<ParamBaseType&>(param1), const_cast<ParamBaseType&>(param2));
}

#endif /* ! defined(LL_LLDOUBLEDISPATCH_H) */