// 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