python/src/object/inheritance.cpp at python313 · boostorg/python · GitHub

History

502 lines (414 loc) · 14.5 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501

502

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

python/src/object/inheritance.cpp at python313 · boostorg/python · GitHub

Uh oh!

Expand file tree

Breadcrumbs

inheritance.cpp

Latest commit

History

Breadcrumbs

inheritance.cpp

File metadata and controls