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