// 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/python/detail/pymutex.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/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)

{

using namespace boost::placeholders;

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)

{

BOOST_PYTHON_LOCK_STATE();

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

{

BOOST_PYTHON_LOCK_STATE();

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

{

BOOST_PYTHON_LOCK_STATE();

tuples::get<kdynamic_id>(*demand_type(static_id)) = get_dynamic_id;

}

}}} // namespace boost::python::objects