src/inheritance.cpp

   1 // Copyright Daniel Wallin 2009. Use, modification and distribution is
   2 // subject to the Boost Software License, Version 1.0. (See accompanying
   3 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   4
   5 #include <limits>
   6 #include <map>
   7 #include <vector>
   8 #include <queue>
   9 #include <boost/dynamic_bitset.hpp>
  10 #include <boost/foreach.hpp>
  11 #include <boost/tuple/tuple.hpp>
  12 #include <boost/tuple/tuple_comparison.hpp>
  13 #include <luabind/typeid.hpp>
  14 #include <luabind/detail/inheritance.hpp>
  15
  16 namespace luabind { namespace detail {
  17
  18 class_id const class_id_map::local_id_base =
  19     std::numeric_limits<class_id>::max() / 2;
  20
  21 namespace
  22 {
  23
  24   struct edge
  25   {
  26       edge(class_id target, cast_function cast)
  27         : target(target)
  28         , cast(cast)
  29       {}
  30
  31       class_id target;
  32       cast_function cast;
  33   };
  34
  35   bool operator<(edge const& x, edge const& y)
  36   {
  37       return x.target < y.target;
  38   }
  39
  40   struct vertex
  41   {
  42       vertex(class_id id)
  43         : id(id)
  44       {}
  45
  46       class_id id;
  47       std::vector<edge> edges;
  48   };
  49
  50   typedef std::pair<std::ptrdiff_t, std::size_t> cache_entry;
  51
  52   class cache
  53   {
  54   public:
  55       static std::ptrdiff_t const unknown;
  56       static std::ptrdiff_t const invalid;
  57
  58       cache_entry get(
  59           class_id src, class_id target, class_id dynamic_id
  60         , std::ptrdiff_t object_offset) const;
  61
  62       void put(
  63           class_id src, class_id target, class_id dynamic_id
  64         , std::ptrdiff_t object_offset
  65         , std::size_t distance, std::ptrdiff_t offset);
  66
  67       void invalidate();
  68
  69   private:
  70       typedef boost::tuple<
  71           class_id, class_id, class_id, std::ptrdiff_t> key_type;
  72       typedef std::map<key_type, cache_entry> map_type;
  73       map_type m_cache;
  74   };
  75
  76   std::ptrdiff_t const cache::unknown =
  77       std::numeric_limits<std::ptrdiff_t>::max();
  78   std::ptrdiff_t const cache::invalid = cache::unknown - 1;
  79
  80   cache_entry cache::get(
  81       class_id src, class_id target, class_id dynamic_id
  82     , std::ptrdiff_t object_offset) const
  83   {
  84       map_type::const_iterator i = m_cache.find(
  85           key_type(src, target, dynamic_id, object_offset));
  86       return i != m_cache.end() ? i->second : cache_entry(unknown, -1);
  87   }
  88
  89   void cache::put(
  90       class_id src, class_id target, class_id dynamic_id
  91     , std::ptrdiff_t object_offset, std::size_t distance, std::ptrdiff_t offset)
  92   {
  93       m_cache.insert(std::make_pair(
  94           key_type(src, target, dynamic_id, offset)
  95         , cache_entry(offset, distance)
  96       ));
  97   }
  98
  99   void cache::invalidate()
 100   {
 101       m_cache.clear();
 102   }
 103
 104 } // namespace unnamed
 105
 106 class cast_graph::impl
 107 {
 108 public:
 109     std::pair<void*, std::size_t> cast(
 110         void* p, class_id src, class_id target
 111       , class_id dynamic_id, void const* dynamic_ptr) const;
 112     void insert(class_id src, class_id target, cast_function cast);
 113
 114 private:
 115     std::vector<vertex> m_vertices;
 116     mutable cache m_cache;
 117 };
 118
 119 namespace
 120 {
 121
 122   struct queue_entry
 123   {
 124       queue_entry(void* p, class_id vertex_id, std::size_t distance)
 125         : p(p)
 126         , vertex_id(vertex_id)
 127         , distance(distance)
 128       {}
 129
 130       void* p;
 131       class_id vertex_id;
 132       std::size_t distance;
 133   };
 134
 135 } // namespace unnamed
 136
 137 std::pair<void*, std::size_t> cast_graph::impl::cast(
 138     void* const p, class_id src, class_id target
 139   , class_id dynamic_id, void const* dynamic_ptr) const
 140 {
 141     if (src == target)
 142         return std::make_pair(p, 0);
 143
 144     if (src >= m_vertices.size() || target >= m_vertices.size())
 145         return std::pair<void*, std::size_t>(0, -1);
 146
 147     std::ptrdiff_t const object_offset =
 148         (char const*)dynamic_ptr - (char const*)p;
 149
 150     cache_entry cached = m_cache.get(src, target, dynamic_id, object_offset);
 151
 152     if (cached.first != cache::unknown)
 153     {
 154         if (cached.first == cache::invalid)
 155             return std::pair<void*, std::size_t>(0, -1);
 156         return std::make_pair((char*)p + cached.first, cached.second);
 157     }
 158
 159     std::queue<queue_entry> q;
 160     q.push(queue_entry(p, src, 0));
 161
 162     boost::dynamic_bitset<> visited(m_vertices.size());
 163
 164     while (!q.empty())
 165     {
 166         queue_entry const qe = q.front();
 167         q.pop();
 168
 169         visited[qe.vertex_id] = true;
 170         vertex const& v = m_vertices[qe.vertex_id];
 171
 172         if (v.id == target)
 173         {
 174             m_cache.put(
 175                 src, target, dynamic_id, object_offset
 176               , qe.distance, (char*)qe.p - (char*)p
 177             );
 178
 179             return std::make_pair(qe.p, qe.distance);
 180         }
 181
 182         BOOST_FOREACH(edge const& e, v.edges)
 183         {
 184             if (visited[e.target])
 185                 continue;
 186             if (void* casted = e.cast(qe.p))
 187                 q.push(queue_entry(casted, e.target, qe.distance + 1));
 188         }
 189     }
 190
 191     m_cache.put(src, target, dynamic_id, object_offset, cache::invalid, -1);
 192
 193     return std::pair<void*, std::size_t>(0, -1);
 194 }
 195
 196 void cast_graph::impl::insert(
 197     class_id src, class_id target, cast_function cast)
 198 {
 199     class_id const max_id = std::max(src, target);
 200
 201     if (max_id >= m_vertices.size())
 202     {
 203         m_vertices.reserve(max_id + 1);
 204         for (class_id i = m_vertices.size(); i < max_id + 1; ++i)
 205             m_vertices.push_back(vertex(i));
 206     }
 207
 208     std::vector<edge>& edges = m_vertices[src].edges;
 209
 210     std::vector<edge>::iterator i = std::lower_bound(
 211         edges.begin(), edges.end(), edge(target, 0)
 212     );
 213
 214     if (i == edges.end() || i->target != target)
 215     {
 216         edges.insert(i, edge(target, cast));
 217         m_cache.invalidate();
 218     }
 219 }
 220
 221 std::pair<void*, std::size_t> cast_graph::cast(
 222     void* p, class_id src, class_id target
 223   , class_id dynamic_id, void const* dynamic_ptr) const
 224 {
 225     return m_impl->cast(p, src, target, dynamic_id, dynamic_ptr);
 226 }
 227
 228 void cast_graph::insert(class_id src, class_id target, cast_function cast)
 229 {
 230     m_impl->insert(src, target, cast);
 231 }
 232
 233 cast_graph::cast_graph()
 234   : m_impl(new impl)
 235 {}
 236
 237 cast_graph::~cast_graph()
 238 {}
 239
 240 LUABIND_API class_id allocate_class_id()
 241 {
 242     static class_id id = 0;
 243     return id++;
 244 }
 245
 246 }} // namespace luabind::detail