#include <typeinfo> // needed for cmm-ss builds.

#include "dispatch.h"

#ifdef _POSIX_THREADS
    #include <pthread.h>
#endif

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <assert.h>

#include <errno.h>

#ifdef NDEBUG
    #define debug if (1) {} else std::cerr
#else
    #define debug if (0) {} else std::cerr
#endif

namespace
{
    #ifdef _POSIX_THREADS
        /*
        In threaded builds, the function cmm_global_lock()
        returns a reference to a singleton
        lock object that is used to protect all access to dispatch table
        data. The classes cmm_scoped_readlock and cmm_scoped_writelock
        are used to claim/release this lock.
        
        if_t cmm_USE_RW_LOCK is defined, the global lock object is a
        pthread_rwlock_t. Otherwise it is a global pthread_mutex_t,
        and cmm_scoped_readlock and cmm_scoped_writelock are identical.
        
        On OpenBSD 3.2/i386, using rwlocks seems to be 20-30% slower than a mutex for
        a simple single-threaded (sic) test (make test100 top_build=gcc-release-threads-x11).
        Actually, Butenhof argues that in general there's little advantage of
        rwlock over a mutex - see:
        http://groups.google.co.uk/groups?hl=en&lr=&ie=UTF-8&selm=FZPZ9.17%24fw1.13%40news.cpqcorp.net&rnum=5
        
        Hence by default we don't define cmm_USE_RW_LOCK */
        
        //#define cmm_USE_RW_LOCK
        
        #ifdef cmm_USE_RW_LOCK
            struct cmm_scoped_readlock
            {
                explicit cmm_scoped_readlock( pthread_rwlock_t& lock0)
                : lock( lock0)
                {
                    if ( int e = pthread_rwlock_rdlock( &this->lock))
                    {
                        std::cerr << "cmm_scoped_readlock(): pthread_rwlock_rdlock failed. e=" << e << ", calling abort\n";
                        abort();
                    }
                }
                ~cmm_scoped_readlock()
                {
                    if ( int e = pthread_rwlock_unlock( &this->lock))
                    {
                        std::cerr << "cmm_scoped_readlock(): pthread_rwlock_unlock failed. e=" << e << ", calling abort\n";
                        abort();
                    }
                }
                pthread_rwlock_t&   lock;
            };
            struct cmm_scoped_writelock
            {
                explicit cmm_scoped_writelock( pthread_rwlock_t& lock0)
                : lock( lock0)
                {
                    if ( int e = pthread_rwlock_wrlock( &this->lock))
                    {
                        std::cerr << "cmm_scoped_writelock(): pthread_rwlock_wrlock failed. e=" << e << ", calling abort\n";
                        abort();
                    }
                }
                ~cmm_scoped_writelock()
                {
                    if ( int e = pthread_rwlock_unlock( &this->lock))
                    {
                        std::cerr << "cmm_scoped_writelock(): pthread_rwlock_unlock failed. e=" << e << ", calling abort\n";
                        abort();
                    }
                }
                 pthread_rwlock_t&  lock;
            };
            pthread_rwlock_t&   cmm_global_lock()
            {
                static pthread_rwlock_t  lock = PTHREAD_RWLOCK_INITIALIZER;
                return lock;
            }
    
        #else
            struct cmm_scopedlock_internal
            {
                explicit cmm_scopedlock_internal( pthread_mutex_t& mutex0)
                :
                mutex( mutex0)
                {
                    if ( int e = pthread_mutex_lock( &this->mutex))
                    {
                        std::cerr << "cmm_scopedlock_internal(): pthread_mutex_lock failed. e=" << e << ", calling abort\n";
                        abort();
                    }
                }

                ~cmm_scopedlock_internal()
                {
                    if ( pthread_mutex_unlock( &this->mutex))
                    {
                        std::cerr << "~cmm_scopedlock_internal(): pthread_mutex_unlock failed. calling abort\n";
                        abort();
                    }
                }

                private:
                pthread_mutex_t&    mutex;
            };

            typedef cmm_scopedlock_internal cmm_scoped_readlock;
            typedef cmm_scopedlock_internal cmm_scoped_writelock;

            pthread_mutex_t&    cmm_global_lock()
            {
                static pthread_mutex_t  mutex = PTHREAD_MUTEX_INITIALIZER;
                return mutex;
            }
            
        #endif
    #endif
    
    
    /* Below are structs that represent the types in multimethods, including
    if about inheritance. */
    
    struct cmm_text
    /* Represents a C++ name, e.g. `Foo' or `Parser::Bar'. */
    {
        const char* begin;
        const char* end;
        cmm_text( const char* b, const char* e)
        : begin( b), end( e)
        {}
    };

    struct cmm_name
    /* Represents a sequence of names, typically a set of inherited names
    such as `Base', `Derived'. */
    {
        std::vector< cmm_text>   elements;
    };

    struct  cmm_types
    /* Represents types taken by a function. */
    {
        std::string             spec;   // copy of mangled name passed to ctr.
        std::vector< cmm_name>  types;
        explicit cmm_types( const char* mangledname);
        // e.g. "3foo_2_1_4Base_2_4Base_7Derived
    };
    
    
    /* Functions for extracting type information encoded by Cmm into
    C-style strings. */
    
    int
    cmm_read_number( const char*& s)
    /* Reads number at start of s, and increments s past the number. */
    {
        assert( s);
        errno = 0;
        char*   next;
        long int    len = strtol( s, &next, 10);
        if ( errno)
        {
            std::string buffer = "Expecting number at start of `";
            buffer += s;
            buffer += "'";
            debug << buffer << "\n";
            throw std::runtime_error( buffer.c_str());
        }
        if ( len<0)
        {
            throw std::runtime_error(
                std::string()
                + "Expecting positive number at start of `"
                + s + "'");
        }
        s = next;
        return static_cast< int>( len);
    }

    cmm_text
    cmm_readnextname( const char*& s)
    /* Reads next identifier from s, and increments s past the identifier.
    The identifier is expected to be of the form
    <number of letters><letters>. E.g 3Fooxyz would return `Foo' and leave
    s pointing to `xyz'.*/
    {
        long int    len = cmm_read_number( s);
        const char* start=s;
        s += len;
        return cmm_text( start, s);
    }

    void
    cmm_skip_underscore( const char*& pos)
    {
        if ( *pos!='_')   throw std::runtime_error( "expecting '_' in mangled name");
        ++pos;
    }

    cmm_types::cmm_types( const char* mangledname)
    : spec( mangledname)
    {
        const char* pos = mangledname;
        cmm_readnextname( pos); // skip initial function name.
        int num_params = cmm_read_number( pos);
        assert( num_params>=0);
        cmm_skip_underscore( pos);
        for ( int i=0; i<num_params; ++i)
        {
            this->types.push_back( cmm_name());
            int num_elements = cmm_read_number( pos);
            cmm_skip_underscore( pos);
            for ( int j=0; j<num_elements; ++j)
            {
                this->types.back().elements.push_back( cmm_readnextname( pos));
            }
        }
        assert( *pos==0);
    }


    /* Things for the small-int cache */

    struct cmm_smallint_entry;
    
    struct cmm_smallint_cache
    {
        typedef std::vector< cmm_smallint_entry>    items_t;
        items_t items;
        void clear( int depth);
    };
    
    struct cmm_smallint_entry
    /* An entry in the small-int cache is either a pointer to an array
    of more cmm_smallint_entry's, or a pointer to an implementation
    function pointer. This struct simply wraps up the union into
    something that can be put into a C++ container. */
    {
        explicit cmm_smallint_entry( cmm_fnptr fn0)
        :
        fn( fn0)
        {}
        explicit cmm_smallint_entry( cmm_smallint_cache* array0)
        :
        array( array0)
        {}
        
        union
        {
            cmm_smallint_cache* array;
            cmm_fnptr           fn;
        };
    };
    
    
    void cmm_smallint_cache::clear( int depth)
    /* assumes that we are top of a depth-deep cache. Note that this function
    doesn't free any memory, it just sets all of the leaf function pointers
    to NULL. */
    {
        assert( depth > 0);
        
        //debug << "cmm_smallint_cache::clear: depth=" << depth << "\n";
        for ( items_t::iterator it=this->items.begin(); it!=this->items.end(); ++it)
        {
            if ( depth==1)
            {
                //debug << "setting it->fn to NULL. &it->fn=" << &(it->fn) << "\n";
                it->fn = NULL;
                //debug << "set it->fn to NULL\n";
            }
            else
            {
                if ( it->array)
                {
                    //debug << "clearing array at address " << it->array << "\n";
                    it->array->clear( depth-1);
                }
            }
        }
        //debug << "cmm_smallint_cache::clear: depth=" << depth << ". returning\n";
    }
}


cmm_implementation_holder::cmm_implementation_holder(
    const char* virt_spec, 
    const char* impl_spec, 
    cmm_matchfn fn_match, 
    cmm_fnptr   fn_call)
:
handle(
    cmm_register_implementation(
        virt_spec,
        impl_spec,
        fn_match,
        fn_call))
{
}

cmm_implementation_holder::~cmm_implementation_holder()
{
    cmm_unregister_implementation( this->handle);
}

struct cmm_virtualfn;

struct cmm_implementation
{
    cmm_implementation(
        cmm_virtualfn&  virtualfn0,
        const char*     spec, 
        cmm_matchfn     match, 
        cmm_fnptr       call);
        
    cmm_virtualfn&   virtualfn;
    cmm_types   types;      // Used when comparing matching implementations
    cmm_matchfn fn_match;   // Returns true iff impl can accept particular set of dynamic types.
    cmm_fnptr   fn_call;
};

struct cmm_virtualfn
{
    typedef std::vector< cmm_implementation*>
        implementations_t;
    
    typedef std::map< std::vector< const std::type_info*>, cmm_fnptr>
        cache_t;
    
    const char*         spec;   // as passed to cmm_get_virtualfn().
    cmm_types           types;
    implementations_t   implementations;
    cache_t             cache;
    cmm_smallint_cache  smallint_cache;
    
    explicit cmm_virtualfn( const char* spec0);
    ~cmm_virtualfn();
};



namespace
{
    /* Exception types */
    
    struct  cmm_exception_data
    /* Represents generic information about a failed multimethod dispatch,
    i.e. info about the virtual function, and (if available) information
    about the dynamic types that caused the failure .*/
    {
        const cmm_virtualfn&                virtfn;
        std::vector< const std::type_info*> types;
        
        cmm_exception_data(
            const cmm_virtualfn&    virtfn0,
            const std::type_info**  types);
        /* types is assumed to be array of virtfn0.types.types.size() elements. */
        
        cmm_exception_data( 
            const cmm_virtualfn&    virtfn0);
        /* Leaves types empty. */
    };

    struct  cmm_exception_ambiguous_internal : cmm_exception_ambiguous
    {
        cmm_exception_ambiguous_internal(
            const cmm_virtualfn&    virtfn0, 
            const void**            params, 
            const std::type_info**  types,
            std::vector< int>       matching_implementations);
        
        cmm_exception_ambiguous_internal(
            const cmm_virtualfn&    virtfn0, 
            const void**            params, 
            std::vector< int>       matching_implementations);
        
        /* matching_implementations contains indexes into
        virtfn0.implementations[]. */
        
        virtual const char* what()  const throw();
        virtual ~cmm_exception_ambiguous_internal() throw() {}
        
        cmm_exception_data  data;
        std::vector< int>   matching_implementations;
        mutable std::string message;
    };

    struct  cmm_exception_unmatched_internal : cmm_exception_unmatched
    {
        cmm_exception_unmatched_internal(
            const cmm_virtualfn&    virtfn0,
            const void**            params,
            const std::type_info**  types);
            
        cmm_exception_unmatched_internal(
            const cmm_virtualfn&    virtfn0,
            const void**            params);

        virtual const char* what()  const throw();
        
        virtual ~cmm_exception_unmatched_internal() throw() {}
        
        cmm_exception_data  data;
        mutable std::string message;
    };

    struct  cmm_exception_bad_implementation_internal : cmm_exception_bad_implementation
    {
        cmm_exception_bad_implementation_internal(
            const cmm_virtualfn&        virtfn, 
            const cmm_implementation&   impl);

        virtual const char* what()  const throw();
        
        virtual ~cmm_exception_bad_implementation_internal() throw() {}

        const cmm_virtualfn&        virtfn;
        const cmm_implementation&   implfn;
        mutable std::string         message;
    };
}    
    

namespace
{
    /* Things for comparing implementations. */

    enum    cmm_comparison
    {
        cmm_comparison_LESSTHAN,
        cmm_comparison_GREATERTHAN,
        cmm_comparison_EQUAL,
        cmm_comparison_UNRELATED
    };

    bool
    operator != ( const cmm_text& a, const cmm_text& b)
    {
        if ( a.end-a.begin != b.end-b.begin)    return true;
        return strncmp( a.begin, b.begin, a.end-a.begin);
    }

    cmm_comparison
    cmm_compare0( const cmm_name& a, const cmm_name& b)
    /*
    if_t type `a' isidentical to type `b', returns cmm_comparison_EQUAL.
    if_t type `a' is derived from type `b', returns cmm_comparison_GREATERTHAN.
    if_t type `b' is derived from type `a', returns cmm_comparison_LESSTHAN.
    Otherwise returns cmm_comparison_UNRELATED
    */
    {
        for ( unsigned int i=0;; ++i)
        {
            if ( i==a.elements.size() && i==b.elements.size())  return cmm_comparison_EQUAL;
            if ( i==a.elements.size())                          return cmm_comparison_LESSTHAN;
            if ( i==b.elements.size())                          return cmm_comparison_GREATERTHAN;
            if ( a.elements[i] != b.elements[i])                return cmm_comparison_UNRELATED;
        }
        assert( 0);
    }
    cmm_comparison
    cmm_compare( const cmm_name& a, const cmm_name& b)
    /* Wrapper for cmm_compare0, for debugging only */
    {
        cmm_comparison c = cmm_compare0( a, b);
        //std::cerr << "comparing " << a << " and " << b << " returns " << c << "\n";
        return c;
    }
    
    cmm_comparison
    cmm_compare0( const cmm_types& a, const cmm_types& b)
    /*
    if_t all types in a are same as all types in b, returns cmm_comparison_EQUAL.
    if_t one or more types in `a' are derived from the equivalent types in `b',
    and the rest are identical to the equivalent types in `b', returns
    cmm_comparison_GREATERTHAN.
    if_t one or more types in `b' are derived from the equivalent types in `a',
    and the rest are identical to the equivalent types in `a', returns
    cmm_comparison_LESSTHAN.
    Otherwise, returns cmm_comparison_UNRELATED.
    */
    {
        assert( a.types.size() == b.types.size());
        cmm_comparison  compare = cmm_comparison_EQUAL;
        for ( unsigned int i=0; i<a.types.size(); ++i)
        {
            cmm_comparison  c = cmm_compare( a.types[i], b.types[i]);
            
            // The logic here looks rather odd, but it is correct I think.
            if ( 0) ;
            else if ( c==cmm_comparison_UNRELATED)  return cmm_comparison_UNRELATED;
            else if ( c==cmm_comparison_EQUAL)      continue;
            else if ( compare==cmm_comparison_EQUAL)    compare=c;
            else if ( compare!=c)                       return cmm_comparison_UNRELATED;
        }
        return compare;
    }
    
    cmm_comparison
    cmm_compare( const cmm_types& a, const cmm_types& b)
    /* Simple wrapper for cmm_compare0, for debug purposes only. */
    {
        cmm_comparison  c = cmm_compare0( a, b);
        //std::cerr << "comparing " << a << " and " << b << " returns " << c << "\n";
        return c;
    }
}

cmm_implementation::cmm_implementation(
    cmm_virtualfn&  virtualfn0,
    const char*     spec,
    cmm_matchfn     match,
    cmm_fnptr       call)
:
virtualfn( virtualfn0), 
types( spec), 
fn_match( match), 
fn_call( call)
{}


cmm_virtualfn::cmm_virtualfn( const char* spec0)
:
spec( spec0), 
types( spec0)
{
};

cmm_virtualfn::~cmm_virtualfn()
{
}


namespace
{
    cmm_fnptr
        cmm_lookup_nocache_internal( 
            cmm_virtualfn&          virtfn, 
            const void**            params, 
            const std::type_info**  types)
    /* types is only used when generating error. can be null.
    This function assumes that we already own the global lock, in threaded
    builds.*/
    {
        std::vector< int>   matching_impls;

        for ( unsigned int impl=0; impl<virtfn.implementations.size(); ++impl)
        {
            if ( virtfn.implementations[ impl]->fn_match( params))
            {
                matching_impls.push_back( impl);
            }
        }
        
        if ( matching_impls.empty())
        {
            if ( types) throw cmm_exception_unmatched_internal( virtfn, params, types);
            else        throw cmm_exception_unmatched_internal( virtfn, params);
        }
        
        /* Look for a matching implementation that is at least as good as all other
        matching implementations. using_t a very inefficient O(N^2) algorithm  but we
        won't be called very often so it's probably ok. */
        for ( unsigned int i=0; i<matching_impls.size(); ++i)
        {
            unsigned int j;
            for ( j=0; j<matching_impls.size(); ++j)
            {
                cmm_comparison c = cmm_compare( 
                    virtfn.implementations[ matching_impls[i]]->types,
                    virtfn.implementations[ matching_impls[j]]->types);
                if ( c==cmm_comparison_LESSTHAN || c==cmm_comparison_UNRELATED)    break;  // impl i isn't the best.
            }
            if ( j==matching_impls.size())
            {
                // implementation i is the best.
                return virtfn.implementations[ matching_impls[i]]->fn_call;
            }
        }
        
        // if we reach here, there is no outright winner.
        if ( types) throw cmm_exception_ambiguous_internal( virtfn, params, types, matching_impls);
        else        throw cmm_exception_ambiguous_internal( virtfn, params, matching_impls);
    }
}


cmm_fnptr
    cmm_lookup_nocache(
        cmm_virtualfn&          virtfn, 
        const void**            params, 
        const std::type_info**  types)
{
    #ifdef _POSIX_THREADS
        cmm_scoped_readlock lock( cmm_global_lock());
    #endif
    return cmm_lookup_nocache_internal( virtfn, params, types);
}


cmm_fnptr
    cmm_lookup( cmm_virtualfn& virtfn, const void** params, const std::type_info** types)
{
    #ifdef _POSIX_THREADS
        cmm_scoped_readlock lock( cmm_global_lock());
    #endif
    
    //std::cerr << "cmm_lookup called:\n";
    //cmm_debug_showall();
    assert( types);
    
    std::vector< const std::type_info*>   dynamictypes( types, types+virtfn.types.types.size());
    // should try to use the raw array, not this std::vector copy.
    
    cmm_fnptr   fn = virtfn.cache[ dynamictypes];
    
    if ( fn)    return fn;
    
    // not in the cache. have to figure it out the hard way.
    
    fn = cmm_lookup_nocache_internal( virtfn, params, types);
    virtfn.cache[ dynamictypes] = fn;
    
    //std::cerr << "cmm_lookup: virtfn=" << &virtfn << ", cache size=" << virtfn.cache.size() << "\n";
    
    //std::cerr << "cmm_lookup returning " << ((void*) fn) << "\n";
    return fn;
}

cmm_fnptr
    cmm_lookup(
        cmm_virtualfn&  virtfn, 
        const void**    params, 
        const int*      types)
/* Lookup using constant-time cache. */
{
    #ifdef _POSIX_THREADS
        cmm_scoped_readlock lock( cmm_global_lock());
    #endif
    
    cmm_smallint_cache* c = &virtfn.smallint_cache;
    for ( unsigned int vparam=0; vparam<virtfn.types.types.size(); ++vparam)
    {
        assert( c);
        
        int  small_int = types[ vparam];
        assert( small_int > 0); // all small ints are > 0.
        
        if ( vparam < virtfn.types.types.size()-1)
        {
            /* for all but the last lookup, we indirect to a new array. */
            if ( c->items.size() < 1u + small_int)
            {
                c->items.resize( 1 + small_int, cmm_smallint_entry( (cmm_smallint_cache*) NULL));
            }
            assert( c->items.size() >= 1u + small_int);
            
            if ( !c->items[ small_int].array)
            {
                c->items[ small_int].array = new cmm_smallint_cache;
            }
            c = c->items[ small_int].array;
        }
        else
        {
            /* last step looks up a function pointer. */
            if ( c->items.size() < 1u + small_int)
            {
                c->items.resize( 1 + small_int, cmm_smallint_entry( (cmm_fnptr) NULL));
            }
            assert( c->items.size() >= 1u + small_int);
            
            if ( !c->items[ small_int].fn)
            {
                c->items[ small_int].fn = cmm_lookup_nocache_internal( virtfn, params, NULL);
            }
            return c->items[ small_int].fn;
        }
    }
    assert( 0);
    return NULL;
}


namespace
{
    typedef std::vector< cmm_virtualfn*>   cmm_global_virtualfns_t;
    
    cmm_global_virtualfns_t&    cmm_global_virtualfns()
    {
        static cmm_global_virtualfns_t* fns = NULL;
        if ( !fns)  fns = new cmm_global_virtualfns_t;
        return *fns;
    };

    void
    cmm_debug_showall();

    bool
    cmm_ptr_virtual_spec_eq( const cmm_virtualfn* a, const char* b)
    {
        return ( 0==strcmp( a->spec, b)) ? true : false;
    }

    cmm_virtualfn&
    cmm_get_virtualfn_internal( const char* virt_spec)
    /* Assumes that we already hold the global lock, in multithreaded builds. */
    {
        //cmm_debug_showall();
        /* Look for an existing matching cmm_virtualfn. We're using a
        crude linear search; not really a problem since usually we are only called
        once per implementation. */
        cmm_global_virtualfns_t::const_iterator v;
        for (
            v=cmm_global_virtualfns().begin();
            v!=cmm_global_virtualfns().end();
            ++v)
        {
            if ( cmm_ptr_virtual_spec_eq( *v, virt_spec))   break;
        }
        
        if ( v!=cmm_global_virtualfns().end()) return **v;

        cmm_global_virtualfns().push_back( new cmm_virtualfn( virt_spec));
        // this leaks if push_back throws...
        return *cmm_global_virtualfns().back();
    }
}


cmm_virtualfn&
cmm_get_virtualfn( const char* virt_spec)
/* Makes a new cmm_virtualfn if can't find a matching one. Implemented
as a separate function cmm_get_virtualfn_internal() so that it can be
called from cmm_register_implementation without us self-deadlocking. */
{
    #ifdef _POSIX_THREADS
        cmm_scoped_readlock lock( cmm_global_lock());
    #endif
    return cmm_get_virtualfn_internal( virt_spec);
}


cmm_implementation&
    cmm_register_implementation(
        const char* virt_spec, 
        const char* impl_spec, 
        cmm_matchfn fn_match, 
        cmm_fnptr   fn_call)
{
    #ifdef _POSIX_THREADS
        cmm_scoped_writelock    lock( cmm_global_lock());
    #endif
    
    /* We should probably check whether this impl has already been registered. */
    cmm_virtualfn&  virtualfn = cmm_get_virtualfn_internal( virt_spec);
    cmm_implementation& impl = * new cmm_implementation( virtualfn, impl_spec, fn_match, fn_call);
    virtualfn.implementations.push_back( &impl);
    virtualfn.cache.clear();
    virtualfn.smallint_cache.clear( virtualfn.types.types.size());
    
    /*debug << "cmm_register_implementation, virt_spec=" << virt_spec
        << ", impl_spec=" << impl_spec << "\n";*/
    
    return impl;
}


void
    cmm_unregister_implementation(
        cmm_implementation& implementation)
{
    #ifdef _POSIX_THREADS
        cmm_scoped_writelock    lock( cmm_global_lock());
    #endif
    
    cmm_virtualfn&  virtualfn = implementation.virtualfn;
    
    /* the following doesn't easily allow an assert.
    implementation.virtualfn.implementations.erase(
        std::remove(
            implementation.virtualfn.implementations.begin(),
            implementation.virtualfn.implementations.end(),
            &implementation),
        implementation.virtualfn.implementations.end());*/
    
    cmm_virtualfn::implementations_t::iterator it =
        std::find(
            virtualfn.implementations.begin(),
            virtualfn.implementations.end(),
            &implementation);
    
    assert( it != virtualfn.implementations.end());
    
    delete *it;
    virtualfn.implementations.erase( it);
    virtualfn.cache.clear();
    virtualfn.smallint_cache.clear( virtualfn.types.types.size());
    
    //debug << "cmm_unregister_implementation, virt_spec=" << virtualfn.spec << "\n";
}


namespace
{
    // Lifted from Loki
    ////////////////////////////////////////////////////////////////////////////////
    // The Loki Library
    // Copyright (c) 2001 by Andrei Alexandrescu
    // This code accompanies the book:
    // Alexandrescu, Andrei. "Modern C++ Design: Generic Programming and Design 
    //     Patterns Applied". Copyright (c) 2001. Addison-Wesley.
    // Permission to use, copy, modify, distribute and sell this software for any 
    //     purpose is hereby granted without fee, provided that the above copyright 
    //     notice appear in all copies and that both that copyright notice and this 
    //     permission notice appear in supporting documentation.
    // The author or Addison-Wesley Longman make no representations about the 
    //     suitability of this software for any purpose. It is provided "as is" 
    //     without express or implied warranty.
    ////////////////////////////////////////////////////////////////////////////////
    class TypeInfo
    {
    public:
        // Constructors
        TypeInfo(); // needed for containers
        TypeInfo(const std::type_info&); // non-explicit

        // access_t for the wrapped std::type_info
        const std::type_info& Get() const;
        // Compatibility functions
        bool before(const TypeInfo& rhs) const;
        const char* name() const;

    private:
        const std::type_info* pInfo_;
    };
    
    // Implementation
    
    inline TypeInfo::TypeInfo()
    {
        class Nil {};
        pInfo_ = &typeid(Nil);
        assert(pInfo_);
    }
    
    inline TypeInfo::TypeInfo(const std::type_info& ti)
    : pInfo_(&ti)
    { assert(pInfo_); }
    
    inline bool TypeInfo::before(const TypeInfo& rhs) const
    {
        assert(pInfo_);
        return pInfo_->before(*rhs.pInfo_);
    }

    inline const std::type_info& TypeInfo::Get() const
    {
        assert(pInfo_);
        return *pInfo_;
    }
    
    inline const char* TypeInfo::name() const
    {
        assert(pInfo_);
        return pInfo_->name();
    }

    // Comparison operators
    
    inline bool operator==(const TypeInfo& lhs, const TypeInfo& rhs)
    { return lhs.Get() == rhs.Get(); }

    inline bool operator<(const TypeInfo& lhs, const TypeInfo& rhs)
    { return lhs.before(rhs); }

    inline bool operator!=(const TypeInfo& lhs, const TypeInfo& rhs)
    { return !(lhs == rhs); }    
    
    inline bool operator>(const TypeInfo& lhs, const TypeInfo& rhs)
    { return rhs < lhs; }
    
    inline bool operator<=(const TypeInfo& lhs, const TypeInfo& rhs)
    { return !(lhs > rhs); }
     
    inline bool operator>=(const TypeInfo& lhs, const TypeInfo& rhs)
    { return !(lhs < rhs); }
    
}

int
    cmm_create_small_integer( 
        const std::type_info& type)
{
    #ifdef _POSIX_THREADS
        cmm_scoped_writelock lock( cmm_global_lock());
    #endif
    typedef std::map< const TypeInfo, int> map_type_to_int_t;
            
    static map_type_to_int_t    map_type_to_int;
    
    #ifndef NDEBUG
        int old_size = map_type_to_int.size();
    #endif
    
    if ( map_type_to_int[ type]==0)
    {
        debug << "cmm_create_small_integer(): creating id " 
            << map_type_to_int.size() 
            << " for type " << type.name() << "\n";
        assert( map_type_to_int.size() == 1u+old_size);
        map_type_to_int[ type] = map_type_to_int.size();
        assert( map_type_to_int.size() == 1u+old_size);
    }
    return map_type_to_int[ type];
}




namespace
{    
    /* Following fns are for outputing info about types/implementation
    functions to a stream. Used by the exception object's what()
    methods, and also useful for debugging. */
    
    std::ostream&
    operator << ( std::ostream& out, const cmm_text& text)
    {
        for ( const char* c=text.begin; c!=text.end; ++c)
        {
            out << *c;
        }
        return out;
    }

    std::ostream&
    operator << ( std::ostream& out, const cmm_name& name)
    {
        for ( unsigned int i=0; i<name.elements.size(); ++i)
        {
            if ( i>0)   out << ":";
            out << name.elements[i];
        }
        return out;
    }

    std::ostream&
    operator << ( std::ostream& out, const cmm_types& types)
    {
        for ( unsigned int i=0; i<types.types.size(); ++i)
        {
            if ( i>0)   out << ", ";
            out << types.types[i];
        }
        return out;
    }

    std::ostream&
    operator << ( std::ostream& out, const cmm_implementation& impl)
    {
        out << impl.types;
        return out;
    }
    
    std::ostream&
    operator << ( std::ostream& out, const cmm_virtualfn& virtfn)
    {
        out << "Virtual fn `" << virtfn.spec << "' (base types: " << virtfn.types << ")\n";
        out << "has " << virtfn.implementations.size() << " implementations:\n";
        for ( unsigned int i=0; i<virtfn.implementations.size(); ++i)
        {
            out << "    " << i << ": " << *virtfn.implementations[i] << ".\n";
        }
        return out;
    }

    std::ostream&
    operator << ( std::ostream& out, const cmm_exception_data& data)
    {
        out << data.virtfn;
        if ( data.types.empty())
        {
            out << "No std::type_info's available for dynamic types";
        }
        else
        {
            out << "std::type_info's for the " << data.types.size() << " dynamic types are: ";
            //std::cerr << "(there are " << data.types.size() << " types\n";
            for ( unsigned int i=0; i<data.types.size(); ++i)
            {
                if ( i>0)   out << ", ";
                assert( data.types[ i]);
                if ( !data.types[ i]->name())   continue;   // non-virtual param
                //std::cerr << i << ": " << (void*) data.types[ i]->name() << "\n";
                assert( data.types[ i]->name());
                out << data.types[ i]->name();
            }
        }
        out << ".\n";
        return out;
    }
    
    std::ostream&
    operator << ( std::ostream& out, cmm_comparison c)
    {
        if ( 0) ;
        else if ( c==cmm_comparison_LESSTHAN)    out << "cmm_comparison_LESSTHAN";
        else if ( c==cmm_comparison_GREATERTHAN) out << "cmm_comparison_GREATERTHAN";
        else if ( c==cmm_comparison_EQUAL)       out << "cmm_comparison_EQUAL";
        else if ( c==cmm_comparison_UNRELATED)   out << "cmm_comparison_UNRELATED";
        else    assert(0);
        return out;
    }
    
    void
    cmm_debug_showall( std::ostream& out)
    {
        out << "virtual functions are (" 
            << &cmm_global_virtualfns() << ", " 
            << cmm_global_virtualfns().size() << "):\n"
            ;
        for ( unsigned int i=0; i<cmm_global_virtualfns().size(); ++i)
        {
            out << *cmm_global_virtualfns()[ i] << "\n";
        }
        out << "-- end of virtual functions--\n";
    }

}



cmm_exception_data::cmm_exception_data(
    const cmm_virtualfn&    virtfn0, 
    const std::type_info**  types0)
:
virtfn( virtfn0),
types( types0, types0 + virtfn.types.types.size())
{
    assert( types0);
    //std::cerr << "cmm_exception_data::cmm_exception_data( const cmm_virtualfn& virtfn0, const std::type_info** types0) called\n";
}

cmm_exception_data::cmm_exception_data(
    const cmm_virtualfn& virtfn0)
:
virtfn( virtfn0),
types()
{
    //std::cerr << "cmm_exception_data::cmm_exception_data( const cmm_virtualfn& virtfn0) called\n";
}

cmm_exception_ambiguous_internal::cmm_exception_ambiguous_internal(
    const cmm_virtualfn&    virtfn0,
    const void**            params,
    const std::type_info**  types,
    std::vector< int>       matching_implementations0)
:
data( virtfn0, types), 
matching_implementations( matching_implementations0)
{
    (void) params;
}

cmm_exception_ambiguous_internal::cmm_exception_ambiguous_internal(
    const cmm_virtualfn&    virtfn0,
    const void**            params,
    std::vector< int>       matching_implementations0)
:
data( virtfn0), 
matching_implementations( matching_implementations0)
{
    (void) params;
}



cmm_exception_unmatched_internal::cmm_exception_unmatched_internal(
    const cmm_virtualfn&    virtfn0,
    const void**            params,
    const std::type_info**  types)
: data( virtfn0, types)
{
    (void) params;
    #ifndef NDEBUG
    std::cerr << "Cmm unmatched exception has been created:\n"
        << this->what() << "\n";
    #endif
}

cmm_exception_unmatched_internal::cmm_exception_unmatched_internal(
    const cmm_virtualfn&    virtfn0,
    const void**            params)
: data( virtfn0)
{
    (void) params;
    #ifndef NDEBUG
    std::cerr << "Cmm unmatched exception has been created:\n"
        << this->what() << "\n";
    #endif
}


const char*
cmm_exception_unmatched_internal::what() const throw()
{
    if ( this->message=="")
    {
        std::stringstream   buffer;
        buffer << "Unmatched virtual dispatch:\n" << this->data;
        this->message = buffer.str();
    }
    return this->message.c_str();
}
const char*
cmm_exception_ambiguous_internal::what() const throw()
{
    if ( this->message=="")
    {
        std::stringstream   buffer;
        buffer << "Ambiguous virtual dispatch: implementations";
        for ( unsigned int i=0; i<this->matching_implementations.size(); ++i)
        {
            if ( i>0)   buffer << ",";
            buffer << " " << this->matching_implementations[ i];
        }
        buffer << " match.\n" << this->data;
        this->message = buffer.str();
    }
    return this->message.c_str();
}

cmm_exception_bad_implementation_internal::cmm_exception_bad_implementation_internal(
    const cmm_virtualfn&        virtfn0,
    const cmm_implementation&   implfn0)
: virtfn( virtfn0), implfn( implfn0)
{
}

const char*
cmm_exception_bad_implementation_internal::what() const throw()
{
    if ( this->message=="")
    {
        std::stringstream   buffer;
        buffer << "bad virtual function implementation:\n"
            << "virtfn: " << this->virtfn
            << "\nbad implementation:" << this->implfn;
            this->message = buffer.str();
    }
    return this->message.c_str();
}