1 // Copyright David Abrahams 2002.
2 // Distributed under the Boost Software License, Version 1.0. (See
3 // accompanying file LICENSE_1_0.txt or copy at
4 // http://www.boost.org/LICENSE_1_0.txt)
5 #include <boost/python/object/inheritance.hpp>
6 #include <boost/python/type_id.hpp>
7 #include <boost/graph/breadth_first_search.hpp>
8 #if _MSC_FULL_VER >= 13102171 && _MSC_FULL_VER <= 13102179
9 # include <boost/graph/reverse_graph.hpp>
11 #include <boost/graph/adjacency_list.hpp>
12 #include <boost/graph/reverse_graph.hpp>
13 #include <boost/property_map/property_map.hpp>
14 #include <boost/bind/bind.hpp>
15 #include <boost/integer_traits.hpp>
16 #include <boost/tuple/tuple.hpp>
17 #include <boost/tuple/tuple_comparison.hpp>
25 // The search is a BFS over the space of (type,address) pairs
26 // guided by the edges of the casting graph whose nodes
27 // correspond to classes, and whose edges are traversed by
28 // applying associated cast functions to an address. We use
29 // vertex distance to the goal node in the cast_graph to rate the
30 // paths. The vertex distance to any goal node is calculated on
31 // demand and outdated by the addition of edges to the graph.
36 enum edge_cast_t
{ edge_cast
= 8010 };
37 template <class T
> inline void unused_variable(const T
&) { }
41 BOOST_INSTALL_PROPERTY(edge
, cast
);
45 typedef void*(*cast_function
)(void*);
48 // Here we put together the low-level data structures of the
49 // casting graph representation.
51 typedef python::type_info class_id
;
53 // represents a graph of available casts
61 adjacency_list
<vecS
,vecS
, bidirectionalS
, no_property
63 // edge index property allows us to look up edges in the connectivity matrix
64 , property
<edge_index_t
,std::size_t
66 // The function which casts a void* from the edge's source type
67 // to its destination type.
68 , property
<edge_cast_t
,cast_function
> > >
75 typedef cast_graph::vertex_descriptor vertex_t
;
76 typedef cast_graph::edge_descriptor edge_t
;
80 typedef std::vector
<std::size_t>::const_iterator node_distance_map
;
82 typedef std::pair
<cast_graph::out_edge_iterator
83 , cast_graph::out_edge_iterator
> out_edges_t
;
85 // Return a map of the distances from any node to the given
87 node_distance_map
distances_to(vertex_t target
) const
89 std::size_t n
= num_vertices(m_topology
);
90 if (m_distances
.size() != n
* n
)
93 m_distances
.resize(n
* n
, (std::numeric_limits
<std::size_t>::max
)());
97 std::vector
<std::size_t>::iterator to_target
= m_distances
.begin() + n
* target
;
99 // this node hasn't been used as a target yet
100 if (to_target
[target
] != 0)
102 typedef reverse_graph
<cast_graph
> reverse_cast_graph
;
103 reverse_cast_graph
reverse_topology(m_topology
);
105 to_target
[target
] = 0;
107 breadth_first_search(
108 reverse_topology
, target
112 make_iterator_property_map(
114 , get(vertex_index
, reverse_topology
)
115 # ifdef BOOST_NO_STD_ITERATOR_TRAITS
126 cast_graph
& topology() { return m_topology
; }
127 cast_graph
const& topology() const { return m_topology
; }
130 : m_known_vertices(0)
134 cast_graph m_topology
;
135 mutable std::vector
<std::size_t> m_distances
;
136 mutable std::size_t m_known_vertices
;
139 smart_graph
& full_graph()
141 static smart_graph x
;
145 smart_graph
& up_graph()
147 static smart_graph x
;
152 // Our index of class types
154 using boost::python::objects::dynamic_id_function
;
155 typedef tuples::tuple
<
156 class_id
// static type
157 , vertex_t
// corresponding vertex
158 , dynamic_id_function
// dynamic_id if polymorphic, or 0
160 index_entry_interface
;
161 typedef index_entry_interface::inherited index_entry
;
162 enum { ksrc_static_t
, kvertex
, kdynamic_id
};
164 typedef std::vector
<index_entry
> type_index_t
;
167 type_index_t
& type_index()
169 static type_index_t x
;
173 template <class Tuple
>
176 typedef typename
tuples::element
<0, Tuple
>::type result_type
;
178 result_type
const& operator()(Tuple
const& x
) const
180 return tuples::get
<0>(x
);
184 // map a type to a position in the index
185 inline type_index_t::iterator
type_position(class_id type
)
187 using namespace boost::placeholders
;
188 typedef index_entry entry
;
190 return std::lower_bound(
191 type_index().begin(), type_index().end()
192 , boost::make_tuple(type
, vertex_t(), dynamic_id_function(0))
193 , boost::bind
<bool>(std::less
<class_id
>()
194 , boost::bind
<class_id
>(select1st
<entry
>(), _1
)
195 , boost::bind
<class_id
>(select1st
<entry
>(), _2
)));
198 inline index_entry
* seek_type(class_id type
)
200 type_index_t::iterator p
= type_position(type
);
201 if (p
== type_index().end() || tuples::get
<ksrc_static_t
>(*p
) != type
)
207 // Get the entry for a type, inserting if necessary
208 inline type_index_t::iterator
demand_type(class_id type
)
210 type_index_t::iterator p
= type_position(type
);
212 if (p
!= type_index().end() && tuples::get
<ksrc_static_t
>(*p
) == type
)
215 vertex_t v
= add_vertex(full_graph().topology());
216 vertex_t v2
= add_vertex(up_graph().topology());
219 return type_index().insert(p
, boost::make_tuple(type
, v
, dynamic_id_function(0)));
222 // Map a two types to a vertex in the graph, inserting if necessary
223 typedef std::pair
<type_index_t::iterator
, type_index_t::iterator
>
224 type_index_iterator_pair
;
226 inline type_index_iterator_pair
227 demand_types(class_id t1
, class_id t2
)
229 // be sure there will be no reallocation
230 type_index().reserve(type_index().size() + 2);
231 type_index_t::iterator first
= demand_type(t1
);
232 type_index_t::iterator second
= demand_type(t2
);
235 return std::make_pair(first
, second
);
240 q_elt(std::size_t distance
246 , src_address(src_address
)
251 std::size_t distance
;
256 bool operator<(q_elt
const& rhs
) const
258 return distance
< rhs
.distance
;
264 // Given p, src_t, dst_t
266 // Get a pointer pd to the most-derived object
267 // if it's polymorphic, dynamic_cast to void*
270 // Get the most-derived typeid src_td
272 // ptrdiff_t offset = p - pd
274 // Now we can keep a cache, for [src_t, offset, src_td, dst_t] of
275 // the cast transformation function to use on p and the next src_t
276 // in the chain. src_td, dst_t don't change throughout this
277 // process. In order to represent unreachability, when a pair is
278 // found to be unreachable, we stick a 0-returning "dead-cast"
279 // function in the cache.
281 // This is needed in a few places below
282 inline void* identity_cast(void* p
)
287 void* search(smart_graph
const& g
, void* p
, vertex_t src
, vertex_t dst
)
289 // I think this test was thoroughly bogus -- dwa
290 // If we know there's no path; bail now.
291 // if (src > g.known_vertices() || dst > g.known_vertices())
294 smart_graph::node_distance_map
d(g
.distances_to(dst
));
296 if (d
[src
] == (std::numeric_limits
<std::size_t>::max
)())
299 typedef property_map
<cast_graph
,edge_cast_t
>::const_type cast_map
;
300 cast_map casts
= get(edge_cast
, g
.topology());
302 typedef std::pair
<vertex_t
,void*> search_state
;
303 typedef std::vector
<search_state
> visited_t
;
305 std::priority_queue
<q_elt
> q
;
307 q
.push(q_elt(d
[src
], p
, src
, identity_cast
));
313 // Check to see if we have a real state
314 void* dst_address
= top
.cast(top
.src_address
);
315 if (dst_address
== 0)
318 if (top
.target
== dst
)
321 search_state
s(top
.target
,dst_address
);
323 visited_t::iterator pos
= std::lower_bound(
324 visited
.begin(), visited
.end(), s
);
326 // If already visited, continue
327 if (pos
!= visited
.end() && *pos
== s
)
330 visited
.insert(pos
, s
); // mark it
333 smart_graph::out_edges_t edges
= out_edges(s
.first
, g
.topology());
334 for (cast_graph::out_edge_iterator p
= edges
.first
335 , finish
= edges
.second
342 d
[target(e
, g
.topology())]
344 , target(e
, g
.topology())
345 , boost::get(casts
, e
)));
353 typedef tuples::tuple
<
354 class_id
// source static type
355 , class_id
// target type
356 , std::ptrdiff_t // offset within source object
357 , class_id
// source dynamic type
358 >::inherited key_type
;
360 cache_element(key_type
const& k
)
366 std::ptrdiff_t offset
;
368 BOOST_STATIC_CONSTANT(
369 std::ptrdiff_t, not_found
= integer_traits
<std::ptrdiff_t>::const_min
);
371 bool operator<(cache_element
const& rhs
) const
373 return this->key
< rhs
.key
;
376 bool unreachable() const
378 return offset
== not_found
;
382 enum { kdst_t
= ksrc_static_t
+ 1, koffset
, ksrc_dynamic_t
};
383 typedef std::vector
<cache_element
> cache_t
;
391 inline void* convert_type(void* const p
, class_id src_t
, class_id dst_t
, bool polymorphic
)
393 // Quickly rule out unregistered types
394 index_entry
* src_p
= seek_type(src_t
);
398 index_entry
* dst_p
= seek_type(dst_t
);
402 // Look up the dynamic_id function and call it to get the dynamic
404 boost::python::objects::dynamic_id_t dynamic_id
= polymorphic
405 ? tuples::get
<kdynamic_id
>(*src_p
)(p
)
406 : std::make_pair(p
, src_t
);
408 // Look in the cache first for a quickie address translation
409 std::ptrdiff_t offset
= (char*)p
- (char*)dynamic_id
.first
;
411 cache_element
seek(boost::make_tuple(src_t
, dst_t
, offset
, dynamic_id
.second
));
412 cache_t
& c
= cache();
413 cache_t::iterator
const cache_pos
414 = std::lower_bound(c
.begin(), c
.end(), seek
);
417 // if found in the cache, we're done
418 if (cache_pos
!= c
.end() && cache_pos
->key
== seek
.key
)
420 return cache_pos
->offset
== cache_element::not_found
421 ? 0 : (char*)p
+ cache_pos
->offset
;
424 // If we are starting at the most-derived type, only look in the up graph
425 smart_graph
const& g
= polymorphic
&& dynamic_id
.second
!= src_t
426 ? full_graph() : up_graph();
428 void* result
= search(
429 g
, p
, tuples::get
<kvertex
>(*src_p
)
430 , tuples::get
<kvertex
>(*dst_p
));
433 c
.insert(cache_pos
, seek
)->offset
434 = (result
== 0) ? cache_element::not_found
: (char*)result
- (char*)p
;
440 namespace python
{ namespace objects
{
442 BOOST_PYTHON_DECL
void* find_dynamic_type(void* p
, class_id src_t
, class_id dst_t
)
444 return convert_type(p
, src_t
, dst_t
, true);
447 BOOST_PYTHON_DECL
void* find_static_type(void* p
, class_id src_t
, class_id dst_t
)
449 return convert_type(p
, src_t
, dst_t
, false);
452 BOOST_PYTHON_DECL
void add_cast(
453 class_id src_t
, class_id dst_t
, cast_function cast
, bool is_downcast
)
455 // adding an edge will invalidate any record of unreachability in
457 static std::size_t expected_cache_len
= 0;
458 cache_t
& c
= cache();
459 if (c
.size() > expected_cache_len
)
461 c
.erase(std::remove_if(
463 mem_fn(&cache_element::unreachable
))
466 // If any new cache entries get added, we'll have to do this
467 // again when the next edge is added
468 expected_cache_len
= c
.size();
471 type_index_iterator_pair types
= demand_types(src_t
, dst_t
);
472 vertex_t src
= tuples::get
<kvertex
>(*types
.first
);
473 vertex_t dst
= tuples::get
<kvertex
>(*types
.second
);
475 cast_graph
* const g
[2] = { &up_graph().topology(), &full_graph().topology() };
477 for (cast_graph
*const* p
= g
+ (is_downcast
? 1 : 0); p
< g
+ 2; ++p
)
482 tie(e
, added
) = add_edge(src
, dst
, **p
);
485 put(get(edge_cast
, **p
), e
, cast
);
486 put(get(edge_index
, **p
), e
, num_edges(full_graph().topology()) - 1);
490 BOOST_PYTHON_DECL
void register_dynamic_id_aux(
491 class_id static_id
, dynamic_id_function get_dynamic_id
)
493 tuples::get
<kdynamic_id
>(*demand_type(static_id
)) = get_dynamic_id
;
496 }}} // namespace boost::python::objects