text: // Copyright David Abrahams 2002.
  // Distributed under the Boost Software License, Version 1.0. (See
  // accompanying file LICENSE_1_0.txt or copy at
  // http://www.boost.org/LICENSE_1_0.txt)
  #include <boost/python/object/inheritance.hpp>
  #include <boost/python/type_id.hpp>
  #include <boost/graph/breadth_first_search.hpp>
  #if _MSC_FULL_VER >= 13102171 && _MSC_FULL_VER <= 13102179
  # include <boost/graph/reverse_graph.hpp>
  #endif
  #include <boost/graph/adjacency_list.hpp>
  #include <boost/graph/reverse_graph.hpp>
  #include <boost/property_map/property_map.hpp>
  #include <boost/bind.hpp>
  #include <boost/integer_traits.hpp>
  #include <boost/tuple/tuple.hpp>
  #include <boost/tuple/tuple_comparison.hpp>
  #include <queue>
  #include <vector>
  #include <functional>
  
  //
  // Procedure:
  //
  //      The search is a BFS over the space of (type,address) pairs
  //      guided by the edges of the casting graph whose nodes
  //      correspond to classes, and whose edges are traversed by
  //      applying associated cast functions to an address. We use
  //      vertex distance to the goal node in the cast_graph to rate the
  //      paths. The vertex distance to any goal node is calculated on
  //      demand and outdated by the addition of edges to the graph.
  
  namespace boost {
  namespace
  {
    enum edge_cast_t { edge_cast = 8010 };
    template <class T> inline void unused_variable(const T&) { }
  }
  
  // Install properties
  BOOST_INSTALL_PROPERTY(edge, cast);
  
  namespace
  {
    typedef void*(*cast_function)(void*);
  
    //
    // Here we put together the low-level data structures of the
    // casting graph representation.
    //
    typedef python::type_info class_id;
  
    // represents a graph of available casts
  
  #if 0
    struct cast_graph
        :
  #else
          typedef
  #endif
          adjacency_list<vecS,vecS, bidirectionalS, no_property
  
        // edge index property allows us to look up edges in the connectivity matrix
        , property<edge_index_t,std::size_t
  
                   // The function which casts a void* from the edge's source type
                   // to its destination type.
                   , property<edge_cast_t,cast_function> > >
  #if 0
    {};
  #else
    cast_graph;
  #endif
  
    typedef cast_graph::vertex_descriptor vertex_t;
    typedef cast_graph::edge_descriptor edge_t;
  
    struct smart_graph
    {
        typedef std::vector<std::size_t>::const_iterator node_distance_map;
  
        typedef std::pair<cast_graph::out_edge_iterator
                          , cast_graph::out_edge_iterator> out_edges_t;
  
        // Return a map of the distances from any node to the given
        // target node
        node_distance_map distances_to(vertex_t target) const
        {
            std::size_t n = num_vertices(m_topology);
            if (m_distances.size() != n * n)
            {
                m_distances.clear();
                m_distances.resize(n * n, (std::numeric_limits<std::size_t>::max)());
                m_known_vertices = n;
            }
  
            std::vector<std::size_t>::iterator to_target = m_distances.begin() + n * target;
  
            // this node hasn't been used as a target yet
            if (to_target[target] != 0)
            {
                typedef reverse_graph<cast_graph> reverse_cast_graph;
                reverse_cast_graph reverse_topology(m_topology);
  
                to_target[target] = 0;
  
                breadth_first_search(
                    reverse_topology, target
                    , visitor(
                        make_bfs_visitor(
                            record_distances(
                                make_iterator_property_map(
                                    to_target
                                    , get(vertex_index, reverse_topology)
  # ifdef BOOST_NO_STD_ITERATOR_TRAITS
                                    , *to_target
  # endif
                                    )
                                , on_tree_edge()
                                ))));
            }
  
            return to_target;
        }
  
        cast_graph& topology() { return m_topology; }
        cast_graph const& topology() const { return m_topology; }
  
        smart_graph()
            : m_known_vertices(0)
        {}
  
     private:
        cast_graph m_topology;
        mutable std::vector<std::size_t> m_distances;
        mutable std::size_t m_known_vertices;
    };
  
    smart_graph& full_graph()
    {
        static smart_graph x;
        return x;
    }
  
    smart_graph& up_graph()
    {
        static smart_graph x;
        return x;
    }
  
    //
    // Our index of class types
    //
    using boost::python::objects::dynamic_id_function;
    typedef tuples::tuple<
        class_id               // static type
        , vertex_t             // corresponding vertex
        , dynamic_id_function  // dynamic_id if polymorphic, or 0
        >
    index_entry_interface;
    typedef index_entry_interface::inherited index_entry;
    enum { ksrc_static_t, kvertex, kdynamic_id };
  
    typedef std::vector<index_entry> type_index_t;
  
  
    type_index_t& type_index()
    {
        static type_index_t x;
        return x;
    }
  
    template <class Tuple>
    struct select1st
    {
        typedef typename tuples::element<0, Tuple>::type result_type;
  
        result_type const& operator()(Tuple const& x) const
        {
            return tuples::get<0>(x);
        }
    };
  
    // map a type to a position in the index
    inline type_index_t::iterator type_position(class_id type)
    {
        typedef index_entry entry;
  
        return std::lower_bound(
            type_index().begin(), type_index().end()
            , boost::make_tuple(type, vertex_t(), dynamic_id_function(0))
            , boost::bind<bool>(std::less<class_id>()
                 , boost::bind<class_id>(select1st<entry>(), _1)
                 , boost::bind<class_id>(select1st<entry>(), _2)));
    }
  
    inline index_entry* seek_type(class_id type)
    {
        type_index_t::iterator p = type_position(type);
        if (p == type_index().end() || tuples::get<ksrc_static_t>(*p) != type)
            return 0;
        else
            return &*p;
    }
  
    // Get the entry for a type, inserting if necessary
    inline type_index_t::iterator demand_type(class_id type)
    {
        type_index_t::iterator p = type_position(type);
  
        if (p != type_index().end() && tuples::get<ksrc_static_t>(*p) == type)
            return p;
  
        vertex_t v = add_vertex(full_graph().topology());
        vertex_t v2 = add_vertex(up_graph().topology());
        unused_variable(v2);
        assert(v == v2);
        return type_index().insert(p, boost::make_tuple(type, v, dynamic_id_function(0)));
    }
  
    // Map a two types to a vertex in the graph, inserting if necessary
    typedef std::pair<type_index_t::iterator, type_index_t::iterator>
          type_index_iterator_pair;
  
    inline type_index_iterator_pair
    demand_types(class_id t1, class_id t2)
    {
        // be sure there will be no reallocation
        type_index().reserve(type_index().size() + 2);
        type_index_t::iterator first = demand_type(t1);
        type_index_t::iterator second = demand_type(t2);
        if (first == second)
            ++first;
        return std::make_pair(first, second);
    }
  
    struct q_elt
    {
        q_elt(std::size_t distance
              , void* src_address
              , vertex_t target
              , cast_function cast
              )
            : distance(distance)
            , src_address(src_address)
            , target(target)
            , cast(cast)
        {}
  
        std::size_t distance;
        void* src_address;
        vertex_t target;
        cast_function cast;
  
        bool operator<(q_elt const& rhs) const
        {
            return distance < rhs.distance;
        }
    };
  
    // Optimization:
    //
    // Given p, src_t, dst_t
    //
    // Get a pointer pd to the most-derived object
    //    if it's polymorphic, dynamic_cast to void*
    //    otherwise pd = p
    //
    // Get the most-derived typeid src_td
    //
    // ptrdiff_t offset = p - pd
    //
    // Now we can keep a cache, for [src_t, offset, src_td, dst_t] of
    // the cast transformation function to use on p and the next src_t
    // in the chain.  src_td, dst_t don't change throughout this
    // process. In order to represent unreachability, when a pair is
    // found to be unreachable, we stick a 0-returning "dead-cast"
    // function in the cache.
  
    // This is needed in a few places below
    inline void* identity_cast(void* p)
    {
        return p;
    }
  
    void* search(smart_graph const& g, void* p, vertex_t src, vertex_t dst)
    {
        // I think this test was thoroughly bogus -- dwa
        // If we know there's no path; bail now.
        // if (src > g.known_vertices() || dst > g.known_vertices())
        //    return 0;
  
        smart_graph::node_distance_map d(g.distances_to(dst));
  
        if (d[src] == (std::numeric_limits<std::size_t>::max)())
            return 0;
  
        typedef property_map<cast_graph,edge_cast_t>::const_type cast_map;
        cast_map casts = get(edge_cast, g.topology());
  
        typedef std::pair<vertex_t,void*> search_state;
        typedef std::vector<search_state> visited_t;
        visited_t visited;
        std::priority_queue<q_elt> q;
  
        q.push(q_elt(d[src], p, src, identity_cast));
        while (!q.empty())
        {
            q_elt top = q.top();
            q.pop();
  
            // Check to see if we have a real state
            void* dst_address = top.cast(top.src_address);
            if (dst_address == 0)
                continue;
  
            if (top.target == dst)
                return dst_address;
  
            search_state s(top.target,dst_address);
  
            visited_t::iterator pos = std::lower_bound(
                visited.begin(), visited.end(), s);
  
            // If already visited, continue
            if (pos != visited.end() && *pos == s)
                continue;
  
            visited.insert(pos, s); // mark it
  
            // expand it:
            smart_graph::out_edges_t edges = out_edges(s.first, g.topology());
            for (cast_graph::out_edge_iterator p = edges.first
                     , finish = edges.second
                     ; p != finish
                     ; ++p
                )
            {
                edge_t e = *p;
                q.push(q_elt(
                           d[target(e, g.topology())]
                           , dst_address
                           , target(e, g.topology())
                           , boost::get(casts, e)));
            }
        }
        return 0;
    }
  
    struct cache_element
    {
        typedef tuples::tuple<
            class_id              // source static type
            , class_id            // target type
            , std::ptrdiff_t      // offset within source object
            , class_id            // source dynamic type
            >::inherited key_type;
  
        cache_element(key_type const& k)
            : key(k)
            , offset(0)
        {}
  
        key_type key;
        std::ptrdiff_t offset;
  
        BOOST_STATIC_CONSTANT(
            std::ptrdiff_t, not_found = integer_traits<std::ptrdiff_t>::const_min);
  
        bool operator<(cache_element const& rhs) const
        {
            return this->key < rhs.key;
        }
  
        bool unreachable() const
        {
            return offset == not_found;
        }
    };
  
    enum { kdst_t = ksrc_static_t + 1, koffset, ksrc_dynamic_t };
    typedef std::vector<cache_element> cache_t;
  
    cache_t& cache()
    {
        static cache_t x;
        return x;
    }
  
    inline void* convert_type(void* const p, class_id src_t, class_id dst_t, bool polymorphic)
    {
        // Quickly rule out unregistered types
        index_entry* src_p = seek_type(src_t);
        if (src_p == 0)
            return 0;
  
        index_entry* dst_p = seek_type(dst_t);
        if (dst_p == 0)
            return 0;
  
        // Look up the dynamic_id function and call it to get the dynamic
        // info
        boost::python::objects::dynamic_id_t dynamic_id = polymorphic
            ? tuples::get<kdynamic_id>(*src_p)(p)
            : std::make_pair(p, src_t);
  
        // Look in the cache first for a quickie address translation
        std::ptrdiff_t offset = (char*)p - (char*)dynamic_id.first;
  
        cache_element seek(boost::make_tuple(src_t, dst_t, offset, dynamic_id.second));
        cache_t& c = cache();
        cache_t::iterator const cache_pos
            = std::lower_bound(c.begin(), c.end(), seek);
  
  
        // if found in the cache, we're done
        if (cache_pos != c.end() && cache_pos->key == seek.key)
        {
            return cache_pos->offset == cache_element::not_found
                ? 0 : (char*)p + cache_pos->offset;
        }
  
        // If we are starting at the most-derived type, only look in the up graph
        smart_graph const& g = polymorphic && dynamic_id.second != src_t
            ? full_graph() : up_graph();
  
        void* result = search(
            g, p, tuples::get<kvertex>(*src_p)
            , tuples::get<kvertex>(*dst_p));
  
        // update the cache
        c.insert(cache_pos, seek)->offset
            = (result == 0) ? cache_element::not_found : (char*)result - (char*)p;
  
        return result;
    }
  }
  
  namespace python { namespace objects {
  
  BOOST_PYTHON_DECL void* find_dynamic_type(void* p, class_id src_t, class_id dst_t)
  {
      return convert_type(p, src_t, dst_t, true);
  }
  
  BOOST_PYTHON_DECL void* find_static_type(void* p, class_id src_t, class_id dst_t)
  {
      return convert_type(p, src_t, dst_t, false);
  }
  
  BOOST_PYTHON_DECL void add_cast(
      class_id src_t, class_id dst_t, cast_function cast, bool is_downcast)
  {
      // adding an edge will invalidate any record of unreachability in
      // the cache.
      static std::size_t expected_cache_len = 0;
      cache_t& c = cache();
      if (c.size() > expected_cache_len)
      {
          c.erase(std::remove_if(
                      c.begin(), c.end(),
                      mem_fn(&cache_element::unreachable))
                  , c.end());
  
          // If any new cache entries get added, we'll have to do this
          // again when the next edge is added
          expected_cache_len = c.size();
      }
  
      type_index_iterator_pair types = demand_types(src_t, dst_t);
      vertex_t src = tuples::get<kvertex>(*types.first);
      vertex_t dst = tuples::get<kvertex>(*types.second);
  
      cast_graph* const g[2] = { &up_graph().topology(), &full_graph().topology() };
  
      for (cast_graph*const* p = g + (is_downcast ? 1 : 0); p < g + 2; ++p)
      {
          edge_t e;
          bool added;
  
          tie(e, added) = add_edge(src, dst, **p);
          assert(added);
  
          put(get(edge_cast, **p), e, cast);
          put(get(edge_index, **p), e, num_edges(full_graph().topology()) - 1);
      }
  }
  
  BOOST_PYTHON_DECL void register_dynamic_id_aux(
      class_id static_id, dynamic_id_function get_dynamic_id)
  {
      tuples::get<kdynamic_id>(*demand_type(static_id)) = get_dynamic_id;
  }
  
  }}} // namespace boost::python::objects
  