src/rt/rust_shape.h

   1 // Functions that interpret the shape of a type to perform various low-level
   2 // actions, such as copying, freeing, comparing, and so on.
   3
   4 #ifndef RUST_SHAPE_H
   5 #define RUST_SHAPE_H
   6
   7 // Tell ISAAC to let go of max() and min() defines.
   8 #undef max
   9 #undef min
  10
  11 #include <iostream>
  12 #include "rust_internal.h"
  13
  14 // ISAAC pollutes our namespace.
  15 #undef align
  16
  17 #define ARENA_SIZE          256
  18
  19 //#define DPRINT(fmt,...)     fprintf(stderr, fmt, ##__VA_ARGS__)
  20 //#define DPRINTCX(cx)        shape::print::print_cx(cx)
  21
  22 #define DPRINT(fmt,...)
  23 #define DPRINTCX(cx)
  24
  25
  26 namespace shape {
  27
  28 typedef unsigned long tag_variant_t;
  29 typedef unsigned long tag_align_t;
  30 typedef unsigned long ref_cnt_t;
  31
  32 // Constants
  33
  34 const uint8_t SHAPE_U8 = 0u;
  35 const uint8_t SHAPE_U16 = 1u;
  36 const uint8_t SHAPE_U32 = 2u;
  37 const uint8_t SHAPE_U64 = 3u;
  38 const uint8_t SHAPE_I8 = 4u;
  39 const uint8_t SHAPE_I16 = 5u;
  40 const uint8_t SHAPE_I32 = 6u;
  41 const uint8_t SHAPE_I64 = 7u;
  42 const uint8_t SHAPE_F32 = 8u;
  43 const uint8_t SHAPE_F64 = 9u;
  44 const uint8_t SHAPE_VEC = 11u;
  45 const uint8_t SHAPE_TAG = 12u;
  46 const uint8_t SHAPE_BOX = 13u;
  47 const uint8_t SHAPE_STRUCT = 17u;
  48 const uint8_t SHAPE_FN = 18u;
  49 const uint8_t SHAPE_OBJ = 19u;
  50 const uint8_t SHAPE_RES = 20u;
  51 const uint8_t SHAPE_VAR = 21u;
  52 const uint8_t SHAPE_UNIQ = 22u;
  53
  54 #ifdef _LP64
  55 const uint8_t SHAPE_PTR = SHAPE_U64;
  56 #else
  57 const uint8_t SHAPE_PTR = SHAPE_U32;
  58 #endif
  59
  60
  61 // Forward declarations
  62
  63 struct rust_obj;
  64 struct size_align;
  65 class ptr;
  66 class type_param;
  67
  68
  69 // Arenas; these functions must execute very quickly, so we use an arena
  70 // instead of malloc or new.
  71
  72 class arena {
  73     uint8_t *ptr;
  74     uint8_t data[ARENA_SIZE];
  75
  76 public:
  77     arena() : ptr(data) {}
  78
  79     template<typename T>
  80     inline T *alloc(size_t count = 1) {
  81         // FIXME: align
  82         size_t sz = count * sizeof(T);
  83         T *rv = (T *)ptr;
  84         ptr += sz;
  85         if (ptr > &data[ARENA_SIZE]) {
  86             fprintf(stderr, "Arena space exhausted, sorry\n");
  87             abort();
  88         }
  89         return rv;
  90     }
  91 };
  92
  93
  94 // Alignment inquiries
  95 //
  96 // We can't directly use __alignof__ everywhere because that returns the
  97 // preferred alignment of the type, which is different from the ABI-mandated
  98 // alignment of the type in some cases (e.g. doubles on x86). The latter is
  99 // what actually gets used for struct elements.
 100
 101 template<typename T>
 102 inline size_t
 103 alignof() {
 104 #ifdef _MSC_VER
 105     return __alignof(T);
 106 #else
 107     return __alignof__(T);
 108 #endif
 109 }
 110
 111 template<>
 112 inline size_t
 113 alignof<double>() {
 114     return 4;
 115 }
 116
 117
 118 // Utility classes
 119
 120 struct size_align {
 121     size_t size;
 122     size_t alignment;
 123
 124     size_align(size_t in_size = 0, size_t in_align = 1) :
 125         size(in_size), alignment(in_align) {}
 126
 127     bool is_set() const { return alignment != 0; }
 128
 129     inline void set(size_t in_size, size_t in_align) {
 130         size = in_size;
 131         alignment = in_align;
 132     }
 133
 134     inline void add(const size_align &other) {
 135         add(other.size, other.alignment);
 136     }
 137
 138     inline void add(size_t extra_size, size_t extra_align) {
 139         size += extra_size;
 140         alignment = std::max(alignment, extra_align);
 141     }
 142
 143     static inline size_align make(size_t in_size) {
 144         size_align sa;
 145         sa.size = sa.alignment = in_size;
 146         return sa;
 147     }
 148
 149     static inline size_align make(size_t in_size, size_t in_align) {
 150         size_align sa;
 151         sa.size = in_size;
 152         sa.alignment = in_align;
 153         return sa;
 154     }
 155 };
 156
 157 struct tag_info {
 158     uint16_t tag_id;                        // The tag ID.
 159     const uint8_t *info_ptr;                // Pointer to the info table.
 160     uint16_t variant_count;                 // Number of variants in the tag.
 161     const uint8_t *largest_variants_ptr;    // Ptr to largest variants table.
 162     size_align tag_sa;                      // Size and align of this tag.
 163     uint16_t n_params;                      // Number of type parameters.
 164     const type_param *params;               // Array of type parameters.
 165 };
 166
 167
 168 // Utility functions
 169
 170 inline uint16_t
 171 get_u16(const uint8_t *addr) {
 172     return *reinterpret_cast<const uint16_t *>(addr);
 173 }
 174
 175 inline uint16_t
 176 get_u16_bump(const uint8_t *&addr) {
 177     uint16_t result = get_u16(addr);
 178     addr += sizeof(uint16_t);
 179     return result;
 180 }
 181
 182 template<typename T>
 183 inline void
 184 fmt_number(std::ostream &out, T n) {
 185     out << n;
 186 }
 187
 188 // Override the character interpretation for these two.
 189 template<>
 190 inline void
 191 fmt_number<uint8_t>(std::ostream &out, uint8_t n) {
 192     out << (int)n;
 193 }
 194 template<>
 195 inline void
 196 fmt_number<int8_t>(std::ostream &out, int8_t n) {
 197     out << (int)n;
 198 }
 199
 200
 201 // Contexts
 202
 203 // The base context, an abstract class. We use the curiously recurring
 204 // template pattern here to avoid virtual dispatch.
 205 template<typename T>
 206 class ctxt {
 207 public:
 208     const uint8_t *sp;                  // shape pointer
 209     const type_param *params;           // shapes of type parameters
 210     const rust_shape_tables *tables;
 211     rust_task *task;
 212     bool align;
 213
 214     ctxt(rust_task *in_task,
 215          bool in_align,
 216          const uint8_t *in_sp,
 217          const type_param *in_params,
 218          const rust_shape_tables *in_tables)
 219     : sp(in_sp),
 220       params(in_params),
 221       tables(in_tables),
 222       task(in_task),
 223       align(in_align) {}
 224
 225     template<typename U>
 226     ctxt(const ctxt<U> &other,
 227          const uint8_t *in_sp = NULL,
 228          const type_param *in_params = NULL,
 229          const rust_shape_tables *in_tables = NULL)
 230     : sp(in_sp ? in_sp : other.sp),
 231       params(in_params ? in_params : other.params),
 232       tables(in_tables ? in_tables : other.tables),
 233       task(other.task),
 234       align(other.align) {}
 235
 236     void walk();
 237     void walk_reset();
 238
 239     std::pair<const uint8_t *,const uint8_t *>
 240     get_variant_sp(tag_info &info, tag_variant_t variant_id);
 241
 242 protected:
 243     inline uint8_t peek() { return *sp; }
 244
 245     inline size_align get_size_align(const uint8_t *&addr);
 246
 247 private:
 248     void walk_vec();
 249     void walk_tag();
 250     void walk_box();
 251     void walk_uniq();
 252     void walk_struct();
 253     void walk_res();
 254     void walk_var();
 255 };
 256
 257
 258 // Core Rust types
 259
 260 struct rust_fn {
 261     void (*code)(uint8_t *rv, rust_task *task, void *env, ...);
 262     void *env;
 263 };
 264
 265 struct rust_closure {
 266     type_desc *tydesc;
 267     uint32_t target_0;
 268     uint32_t target_1;
 269     uint32_t bindings[0];
 270
 271     uint8_t *get_bindings() const { return (uint8_t *)bindings; }
 272 };
 273
 274 struct rust_obj_box {
 275     type_desc *tydesc;
 276
 277     uint8_t *get_bindings() const { return (uint8_t *)this; }
 278 };
 279
 280 struct rust_vtable {
 281     CDECL void (*dtor)(void *rv, rust_task *task, rust_obj obj);
 282 };
 283
 284 struct rust_obj {
 285     rust_vtable *vtable;
 286     void *box;
 287 };
 288
 289
 290 // Type parameters
 291
 292 class type_param {
 293 private:
 294     static type_param *make(const type_desc **tydescs, unsigned n_tydescs,
 295                             arena &arena);
 296
 297 public:
 298     const uint8_t *shape;
 299     const rust_shape_tables *tables;
 300     const type_param *params;   // subparameters
 301
 302     // Constructs type parameters from a function shape.
 303     static type_param *from_fn_shape(const uint8_t *sp, ptr dp, arena &arena);
 304     // Creates type parameters from an object shape description.
 305     static type_param *from_obj_shape(const uint8_t *sp, ptr dp,
 306                                       arena &arena);
 307
 308     template<typename T>
 309     inline void set(ctxt<T> *cx) {
 310         shape = cx->sp;
 311         tables = cx->tables;
 312         params = cx->params;
 313     }
 314
 315     // Creates type parameters from a type descriptor.
 316     static inline type_param *from_tydesc(const type_desc *tydesc,
 317                                           arena &arena) {
 318         // In order to find the type parameters of objects and functions, we
 319         // have to actually have the data pointer, since we don't statically
 320         // know from the type of an object or function which type parameters
 321         // it closes over.
 322         assert(!tydesc->n_obj_params && "Type-parametric objects and "
 323                "functions must go through from_tydesc_and_data() instead!");
 324
 325         return make(tydesc->first_param, tydesc->n_params, arena);
 326     }
 327
 328     static type_param *from_tydesc_and_data(const type_desc *tydesc,
 329                                             uint8_t *dp, arena &arena) {
 330         if (tydesc->n_obj_params) {
 331             uintptr_t n_obj_params = tydesc->n_obj_params;
 332             const type_desc **first_param;
 333             if (n_obj_params & 0x80000000) {
 334                 // Function closure.
 335                 DPRINT("n_obj_params FN %lu, tydesc %p, starting at %p\n",
 336                        (unsigned long)n_obj_params, tydesc,
 337                        dp + sizeof(uintptr_t) + tydesc->size);
 338                 n_obj_params &= 0x7fffffff;
 339                 first_param = (const type_desc **)(dp + sizeof(uintptr_t));
 340             } else {
 341                 // Object closure.
 342                 DPRINT("n_obj_params OBJ %lu, tydesc %p, starting at %p\n",
 343                        (unsigned long)n_obj_params, tydesc,
 344                        dp + sizeof(uintptr_t) * 2);
 345                 first_param = (const type_desc **)(dp + sizeof(uintptr_t) * 2);
 346             }
 347             return make(first_param, n_obj_params, arena);
 348         }
 349
 350         return make(tydesc->first_param, tydesc->n_params, arena);
 351     }
 352 };
 353
 354
 355 // Traversals
 356
 357 #define WALK_NUMBER(c_type) \
 358     static_cast<T *>(this)->template walk_number<c_type>()
 359 #define WALK_SIMPLE(method) static_cast<T *>(this)->method()
 360
 361 template<typename T>
 362 void
 363 ctxt<T>::walk() {
 364     switch (*sp++) {
 365     case SHAPE_U8:      WALK_NUMBER(uint8_t);   break;
 366     case SHAPE_U16:     WALK_NUMBER(uint16_t);  break;
 367     case SHAPE_U32:     WALK_NUMBER(uint32_t);  break;
 368     case SHAPE_U64:     WALK_NUMBER(uint64_t);  break;
 369     case SHAPE_I8:      WALK_NUMBER(int8_t);    break;
 370     case SHAPE_I16:     WALK_NUMBER(int16_t);   break;
 371     case SHAPE_I32:     WALK_NUMBER(int32_t);   break;
 372     case SHAPE_I64:     WALK_NUMBER(int64_t);   break;
 373     case SHAPE_F32:     WALK_NUMBER(float);     break;
 374     case SHAPE_F64:     WALK_NUMBER(double);    break;
 375     case SHAPE_VEC:     walk_vec();             break;
 376     case SHAPE_TAG:     walk_tag();             break;
 377     case SHAPE_BOX:     walk_box();             break;
 378     case SHAPE_STRUCT:  walk_struct();          break;
 379     case SHAPE_FN:      WALK_SIMPLE(walk_fn);   break;
 380     case SHAPE_OBJ:     WALK_SIMPLE(walk_obj);  break;
 381     case SHAPE_RES:     walk_res();             break;
 382     case SHAPE_VAR:     walk_var();             break;
 383     case SHAPE_UNIQ:    walk_uniq();            break;
 384     default:            abort();
 385     }
 386 }
 387
 388 template<typename T>
 389 void
 390 ctxt<T>::walk_reset() {
 391     const uint8_t *old_sp = sp;
 392     walk();
 393     sp = old_sp;
 394 }
 395
 396 template<typename T>
 397 size_align
 398 ctxt<T>::get_size_align(const uint8_t *&addr) {
 399     size_align result;
 400     result.size = get_u16_bump(addr);
 401     result.alignment = *addr++;
 402     return result;
 403 }
 404
 405 // Returns a pointer to the beginning and a pointer to the end of the shape of
 406 // the tag variant with the given ID.
 407 template<typename T>
 408 std::pair<const uint8_t *,const uint8_t *>
 409 ctxt<T>::get_variant_sp(tag_info &tinfo, tag_variant_t variant_id) {
 410     uint16_t variant_offset = get_u16(tinfo.info_ptr +
 411                                       variant_id * sizeof(uint16_t));
 412     const uint8_t *variant_ptr = tables->tags + variant_offset;
 413     uint16_t variant_len = get_u16_bump(variant_ptr);
 414     const uint8_t *variant_end = variant_ptr + variant_len;
 415     return std::make_pair(variant_ptr, variant_end);
 416 }
 417
 418 template<typename T>
 419 void
 420 ctxt<T>::walk_vec() {
 421     bool is_pod = *sp++;
 422
 423     uint16_t sp_size = get_u16_bump(sp);
 424     const uint8_t *end_sp = sp + sp_size;
 425
 426     static_cast<T *>(this)->walk_vec(is_pod, sp_size);
 427
 428     sp = end_sp;
 429 }
 430
 431 template<typename T>
 432 void
 433 ctxt<T>::walk_tag() {
 434     tag_info tinfo;
 435     tinfo.tag_id = get_u16_bump(sp);
 436
 437     // Determine the info pointer.
 438     uint16_t info_offset = get_u16(tables->tags +
 439                                    tinfo.tag_id * sizeof(uint16_t));
 440     tinfo.info_ptr = tables->tags + info_offset;
 441
 442     tinfo.variant_count = get_u16_bump(tinfo.info_ptr);
 443
 444     // Determine the largest-variants pointer.
 445     uint16_t largest_variants_offset = get_u16_bump(tinfo.info_ptr);
 446     tinfo.largest_variants_ptr = tables->tags + largest_variants_offset;
 447
 448     // Determine the size and alignment.
 449     tinfo.tag_sa = get_size_align(tinfo.info_ptr);
 450
 451     // Determine the number of parameters.
 452     tinfo.n_params = get_u16_bump(sp);
 453
 454     // Read in the tag type parameters.
 455     type_param params[tinfo.n_params];
 456     for (uint16_t i = 0; i < tinfo.n_params; i++) {
 457         uint16_t len = get_u16_bump(sp);
 458         params[i].set(this);
 459         sp += len;
 460     }
 461
 462     tinfo.params = params;
 463
 464     // Call to the implementation.
 465     static_cast<T *>(this)->walk_tag(tinfo);
 466 }
 467
 468 template<typename T>
 469 void
 470 ctxt<T>::walk_box() {
 471     uint16_t sp_size = get_u16_bump(sp);
 472     const uint8_t *end_sp = sp + sp_size;
 473
 474     static_cast<T *>(this)->walk_box();
 475
 476     sp = end_sp;
 477 }
 478
 479 template<typename T>
 480 void
 481 ctxt<T>::walk_uniq() {
 482     uint16_t sp_size = get_u16_bump(sp);
 483     const uint8_t *end_sp = sp + sp_size;
 484
 485     static_cast<T *>(this)->walk_uniq();
 486
 487     sp = end_sp;
 488 }
 489
 490 template<typename T>
 491 void
 492 ctxt<T>::walk_struct() {
 493     uint16_t sp_size = get_u16_bump(sp);
 494     const uint8_t *end_sp = sp + sp_size;
 495
 496     static_cast<T *>(this)->walk_struct(end_sp);
 497
 498     sp = end_sp;
 499 }
 500
 501 template<typename T>
 502 void
 503 ctxt<T>::walk_res() {
 504     uint16_t dtor_offset = get_u16_bump(sp);
 505     const rust_fn **resources =
 506         reinterpret_cast<const rust_fn **>(tables->resources);
 507     const rust_fn *dtor = resources[dtor_offset];
 508
 509     uint16_t n_ty_params = get_u16_bump(sp);
 510
 511     // Read in the tag type parameters.
 512     type_param params[n_ty_params];
 513     for (uint16_t i = 0; i < n_ty_params; i++) {
 514         uint16_t ty_param_len = get_u16_bump(sp);
 515         const uint8_t *next_sp = sp + ty_param_len;
 516         params[i].set(this);
 517         sp = next_sp;
 518     }
 519
 520     uint16_t sp_size = get_u16_bump(sp);
 521     const uint8_t *end_sp = sp + sp_size;
 522
 523     static_cast<T *>(this)->walk_res(dtor, n_ty_params, params, end_sp);
 524
 525     sp = end_sp;
 526 }
 527
 528 template<typename T>
 529 void
 530 ctxt<T>::walk_var() {
 531     uint8_t param = *sp++;
 532     static_cast<T *>(this)->walk_var(param);
 533 }
 534
 535 // A shape printer, useful for debugging
 536
 537 class print : public ctxt<print> {
 538 public:
 539     template<typename T>
 540     print(const ctxt<T> &other,
 541           const uint8_t *in_sp = NULL,
 542           const type_param *in_params = NULL,
 543           const rust_shape_tables *in_tables = NULL)
 544     : ctxt<print>(other, in_sp, in_params, in_tables) {}
 545
 546     print(rust_task *in_task,
 547           bool in_align,
 548           const uint8_t *in_sp,
 549           const type_param *in_params,
 550           const rust_shape_tables *in_tables)
 551     : ctxt<print>(in_task, in_align, in_sp, in_params, in_tables) {}
 552
 553     void walk_tag(tag_info &tinfo);
 554     void walk_struct(const uint8_t *end_sp);
 555     void walk_res(const rust_fn *dtor, unsigned n_params,
 556                   const type_param *params, const uint8_t *end_sp);
 557     void walk_var(uint8_t param);
 558
 559     void walk_vec(bool is_pod, uint16_t sp_size) {
 560         DPRINT("vec<"); walk(); DPRINT(">");
 561     }
 562     void walk_box() {
 563         DPRINT("box<"); walk(); DPRINT(">");
 564     }
 565
 566     void walk_fn()  { DPRINT("fn"); }
 567     void walk_obj() { DPRINT("obj"); }
 568     void walk_closure();
 569
 570     template<typename T>
 571     void walk_number() {}
 572
 573     template<typename T>
 574     static void print_cx(const T *cx) {
 575         print self(*cx);
 576         self.align = false;
 577         self.walk();
 578     }
 579 };
 580
 581
 582 //
 583 // Size-of (which also computes alignment). Be warned: this is an expensive
 584 // operation.
 585 //
 586 // TODO: Maybe dynamic_size_of() should call into this somehow?
 587 //
 588
 589 class size_of : public ctxt<size_of> {
 590 private:
 591     size_align sa;
 592
 593 public:
 594     size_of(const size_of &other,
 595             const uint8_t *in_sp = NULL,
 596             const type_param *in_params = NULL,
 597             const rust_shape_tables *in_tables = NULL)
 598     : ctxt<size_of>(other, in_sp, in_params, in_tables) {}
 599
 600     template<typename T>
 601     size_of(const ctxt<T> &other,
 602             const uint8_t *in_sp = NULL,
 603             const type_param *in_params = NULL,
 604             const rust_shape_tables *in_tables = NULL)
 605     : ctxt<size_of>(other, in_sp, in_params, in_tables) {}
 606
 607     void walk_tag(tag_info &tinfo);
 608     void walk_struct(const uint8_t *end_sp);
 609
 610     void walk_box()     { sa.set(sizeof(void *),   sizeof(void *)); }
 611     void walk_fn()      { sa.set(sizeof(void *)*2, sizeof(void *)); }
 612     void walk_obj()     { sa.set(sizeof(void *)*2, sizeof(void *)); }
 613     void walk_closure();
 614
 615     void walk_vec(bool is_pod, uint16_t sp_size) {
 616         sa.set(sizeof(void *), sizeof(void *));
 617     }
 618
 619     void walk_var(uint8_t param_index) {
 620         const type_param *param = &params[param_index];
 621         size_of sub(*this, param->shape, param->params, param->tables);
 622         sub.walk();
 623         sa = sub.sa;
 624     }
 625
 626     void walk_res(const rust_fn *dtor, unsigned n_params,
 627                   const type_param *params, const uint8_t *end_sp) {
 628         abort();    // TODO
 629     }
 630
 631     template<typename T>
 632     void walk_number()  { sa.set(sizeof(T), alignof<T>()); }
 633
 634     void compute_tag_size(tag_info &tinfo);
 635
 636     template<typename T>
 637     static void compute_tag_size(const ctxt<T> &other_cx, tag_info &tinfo) {
 638         size_of cx(other_cx);
 639         cx.compute_tag_size(tinfo);
 640     }
 641
 642     template<typename T>
 643     static size_align get(const ctxt<T> &other_cx, unsigned back_up = 0) {
 644         size_of cx(other_cx, other_cx.sp - back_up);
 645         cx.align = false;
 646         cx.walk();
 647         assert(cx.sa.alignment > 0);
 648         return cx.sa;
 649     }
 650 };
 651
 652
 653 // Pointer wrappers for data traversals
 654
 655 class ptr {
 656 private:
 657     uint8_t *p;
 658
 659 public:
 660     template<typename T>
 661     struct data { typedef T t; };
 662
 663     ptr() : p(NULL) {}
 664     ptr(uint8_t *in_p) : p(in_p) {}
 665     ptr(uintptr_t in_p) : p((uint8_t *)in_p) {}
 666
 667     inline ptr operator+(const size_t amount) const {
 668         return make(p + amount);
 669     }
 670     inline ptr &operator+=(const size_t amount) { p += amount; return *this; }
 671     inline bool operator<(const ptr other) { return p < other.p; }
 672     inline ptr operator++() { ptr rv(*this); p++; return rv; }
 673     inline uint8_t operator*() { return *p; }
 674
 675     template<typename T>
 676     inline operator T *() { return (T *)p; }
 677
 678     inline operator bool() const { return p != NULL; }
 679     inline operator uintptr_t() const { return (uintptr_t)p; }
 680
 681     static inline ptr make(uint8_t *in_p) {
 682         ptr self(in_p);
 683         return self;
 684     }
 685 };
 686
 687 template<typename T>
 688 static inline T
 689 bump_dp(ptr &dp) {
 690     T x = *((T *)dp);
 691     dp += sizeof(T);
 692     return x;
 693 }
 694
 695 template<typename T>
 696 static inline T
 697 get_dp(ptr dp) {
 698     return *((T *)dp);
 699 }
 700
 701
 702 // Pointer pairs for structural comparison
 703
 704 template<typename T>
 705 class data_pair {
 706 public:
 707     T fst, snd;
 708
 709     data_pair() {}
 710     data_pair(T &in_fst, T &in_snd) : fst(in_fst), snd(in_snd) {}
 711
 712     inline void operator=(const T rhs) { fst = snd = rhs; }
 713
 714     static data_pair<T> make(T &fst, T &snd) {
 715         data_pair<T> data(fst, snd);
 716         return data;
 717     }
 718 };
 719
 720 class ptr_pair {
 721 public:
 722     uint8_t *fst, *snd;
 723
 724     template<typename T>
 725     struct data { typedef data_pair<T> t; };
 726
 727     ptr_pair() : fst(NULL), snd(NULL) {}
 728     ptr_pair(uint8_t *in_fst, uint8_t *in_snd) : fst(in_fst), snd(in_snd) {}
 729     ptr_pair(data_pair<uint8_t *> &other) : fst(other.fst), snd(other.snd) {}
 730
 731     inline void operator=(uint8_t *rhs) { fst = snd = rhs; }
 732
 733     inline operator bool() const { return fst != NULL && snd != NULL; }
 734
 735     inline ptr_pair operator+(size_t n) const {
 736         return make(fst + n, snd + n);
 737     }
 738
 739     inline ptr_pair operator+=(size_t n) {
 740         fst += n; snd += n;
 741         return *this;
 742     }
 743
 744     inline ptr_pair operator-(size_t n) const {
 745         return make(fst - n, snd - n);
 746     }
 747
 748     inline bool operator<(const ptr_pair &other) const {
 749         return fst < other.fst && snd < other.snd;
 750     }
 751
 752     static inline ptr_pair make(uint8_t *fst, uint8_t *snd) {
 753         ptr_pair self(fst, snd);
 754         return self;
 755     }
 756
 757     static inline ptr_pair make(const data_pair<uint8_t *> &pair) {
 758         ptr_pair self(pair.fst, pair.snd);
 759         return self;
 760     }
 761 };
 762
 763 // NB: This function does not align.
 764 template<typename T>
 765 inline data_pair<T>
 766 bump_dp(ptr_pair &ptr) {
 767     data_pair<T> data(*reinterpret_cast<T *>(ptr.fst),
 768                       *reinterpret_cast<T *>(ptr.snd));
 769     ptr += sizeof(T);
 770     return data;
 771 }
 772
 773 template<typename T>
 774 inline data_pair<T>
 775 get_dp(ptr_pair &ptr) {
 776     data_pair<T> data(*reinterpret_cast<T *>(ptr.fst),
 777                       *reinterpret_cast<T *>(ptr.snd));
 778     return data;
 779 }
 780
 781 }   // end namespace shape
 782
 783
 784 inline shape::ptr_pair
 785 align_to(const shape::ptr_pair &pair, size_t n) {
 786     return shape::ptr_pair::make(align_to(pair.fst, n),
 787                                  align_to(pair.snd, n));
 788 }
 789
 790
 791 namespace shape {
 792
 793 // An abstract class (again using the curiously recurring template pattern)
 794 // for methods that actually manipulate the data involved.
 795
 796 #define ALIGN_TO(alignment) \
 797     if (this->align) { \
 798         dp = align_to(dp, (alignment)); \
 799         if (this->end_dp && !(dp < this->end_dp)) \
 800             return; \
 801     }
 802
 803 #define DATA_SIMPLE(ty, call) \
 804     ALIGN_TO(alignof<ty>()); \
 805     U end_dp = dp + sizeof(ty); \
 806     static_cast<T *>(this)->call; \
 807     dp = end_dp;
 808
 809 template<typename T,typename U>
 810 class data : public ctxt< data<T,U> > {
 811 public:
 812     U dp;
 813
 814 protected:
 815     U end_dp;
 816
 817     void walk_box_contents();
 818     void walk_uniq_contents();
 819     void walk_fn_contents(ptr &dp);
 820     void walk_obj_contents(ptr &dp);
 821     void walk_variant(tag_info &tinfo, tag_variant_t variant);
 822
 823     static std::pair<uint8_t *,uint8_t *> get_vec_data_range(ptr dp);
 824     static std::pair<ptr_pair,ptr_pair> get_vec_data_range(ptr_pair &dp);
 825
 826 public:
 827     data(rust_task *in_task,
 828          bool in_align,
 829          const uint8_t *in_sp,
 830          const type_param *in_params,
 831          const rust_shape_tables *in_tables,
 832          U const &in_dp)
 833     : ctxt< data<T,U> >(in_task, in_align, in_sp, in_params, in_tables),
 834       dp(in_dp),
 835       end_dp() {}
 836
 837     void walk_tag(tag_info &tinfo);
 838
 839     void walk_struct(const uint8_t *end_sp) {
 840         static_cast<T *>(this)->walk_struct(end_sp);
 841     }
 842
 843     void walk_vec(bool is_pod, uint16_t sp_size) {
 844         DATA_SIMPLE(void *, walk_vec(is_pod, sp_size));
 845     }
 846
 847     void walk_box()     { DATA_SIMPLE(void *, walk_box()); }
 848
 849     void walk_uniq() { DATA_SIMPLE(void *, walk_uniq()); }
 850
 851     void walk_fn() {
 852         ALIGN_TO(alignof<void *>());
 853         U next_dp = dp + sizeof(void *) * 2;
 854         static_cast<T *>(this)->walk_fn();
 855         dp = next_dp;
 856     }
 857
 858     void walk_obj() {
 859         ALIGN_TO(alignof<void *>());
 860         U next_dp = dp + sizeof(void *) * 2;
 861         static_cast<T *>(this)->walk_obj();
 862         dp = next_dp;
 863     }
 864
 865     void walk_res(const rust_fn *dtor, unsigned n_params,
 866                   const type_param *params, const uint8_t *end_sp) {
 867         typename U::template data<uintptr_t>::t live = bump_dp<uintptr_t>(dp);
 868         // Delegate to the implementation.
 869         static_cast<T *>(this)->walk_res(dtor, n_params, params, end_sp,
 870                                          live);
 871     }
 872
 873     void walk_var(uint8_t param_index) {
 874         const type_param *param = &this->params[param_index];
 875         T sub(*static_cast<T *>(this), param->shape, param->params,
 876               param->tables);
 877         static_cast<T *>(this)->walk_subcontext(sub);
 878         dp = sub.dp;
 879     }
 880
 881     template<typename W>
 882     void walk_number() { DATA_SIMPLE(W, walk_number<W>()); }
 883 };
 884
 885 template<typename T,typename U>
 886 void
 887 data<T,U>::walk_box_contents() {
 888     typename U::template data<uint8_t *>::t box_ptr = bump_dp<uint8_t *>(dp);
 889
 890     U ref_count_dp(box_ptr);
 891     T sub(*static_cast<T *>(this), ref_count_dp + sizeof(ref_cnt_t));
 892     static_cast<T *>(this)->walk_box_contents(sub, ref_count_dp);
 893 }
 894
 895 template<typename T,typename U>
 896 void
 897 data<T,U>::walk_uniq_contents() {
 898     typename U::template data<uint8_t *>::t box_ptr = bump_dp<uint8_t *>(dp);
 899     U data_ptr(box_ptr);
 900     T sub(*static_cast<T *>(this), data_ptr);
 901     static_cast<T *>(this)->walk_uniq_contents(sub);
 902 }
 903
 904 template<typename T,typename U>
 905 void
 906 data<T,U>::walk_variant(tag_info &tinfo, tag_variant_t variant_id) {
 907     std::pair<const uint8_t *,const uint8_t *> variant_ptr_and_end =
 908         this->get_variant_sp(tinfo, variant_id);
 909     static_cast<T *>(this)->walk_variant(tinfo, variant_id,
 910                                          variant_ptr_and_end);
 911 }
 912
 913 template<typename T,typename U>
 914 std::pair<uint8_t *,uint8_t *>
 915 data<T,U>::get_vec_data_range(ptr dp) {
 916     rust_vec* ptr = bump_dp<rust_vec*>(dp);
 917     uint8_t* data = &ptr->data[0];
 918     return std::make_pair(data, data + ptr->fill);
 919 }
 920
 921 template<typename T,typename U>
 922 std::pair<ptr_pair,ptr_pair>
 923 data<T,U>::get_vec_data_range(ptr_pair &dp) {
 924     std::pair<uint8_t *,uint8_t *> fst = get_vec_data_range(dp.fst);
 925     std::pair<uint8_t *,uint8_t *> snd = get_vec_data_range(dp.snd);
 926     ptr_pair start(fst.first, snd.first);
 927     ptr_pair end(fst.second, snd.second);
 928     return std::make_pair(start, end);
 929 }
 930
 931 template<typename T,typename U>
 932 void
 933 data<T,U>::walk_tag(tag_info &tinfo) {
 934     size_of::compute_tag_size(*this, tinfo);
 935
 936     if (tinfo.variant_count > 1)
 937         ALIGN_TO(alignof<tag_align_t>());
 938
 939     U end_dp = dp + tinfo.tag_sa.size;
 940
 941     typename U::template data<tag_variant_t>::t tag_variant;
 942     if (tinfo.variant_count > 1)
 943         tag_variant = bump_dp<tag_variant_t>(dp);
 944     else
 945         tag_variant = 0;
 946
 947     static_cast<T *>(this)->walk_tag(tinfo, tag_variant);
 948
 949     dp = end_dp;
 950 }
 951
 952 template<typename T,typename U>
 953 void
 954 data<T,U>::walk_fn_contents(ptr &dp) {
 955     dp += sizeof(void *);   // Skip over the code pointer.
 956
 957     uint8_t *box_ptr = bump_dp<uint8_t *>(dp);
 958     if (!box_ptr)
 959         return;
 960
 961     type_desc *subtydesc =
 962         *reinterpret_cast<type_desc **>(box_ptr + sizeof(void *));
 963     ptr closure_dp(box_ptr + sizeof(void *));
 964
 965     arena arena;
 966     type_param *params = type_param::from_fn_shape(subtydesc->shape,
 967                                                    closure_dp, arena);
 968
 969     closure_dp += sizeof(void *);
 970     T sub(*static_cast<T *>(this), subtydesc->shape, params,
 971           subtydesc->shape_tables, closure_dp);
 972     sub.align = true;
 973     sub.walk();
 974 }
 975
 976 template<typename T,typename U>
 977 void
 978 data<T,U>::walk_obj_contents(ptr &dp) {
 979     dp += sizeof(void *);   // Skip over the vtable.
 980
 981     uint8_t *box_ptr = bump_dp<uint8_t *>(dp);
 982     type_desc *subtydesc =
 983         *reinterpret_cast<type_desc **>(box_ptr + sizeof(void *));
 984     ptr obj_closure_dp(box_ptr + sizeof(void *));
 985     if (!box_ptr)   // Null check.
 986         return;
 987
 988     arena arena;
 989     type_param *params = type_param::from_obj_shape(subtydesc->shape,
 990                                                     obj_closure_dp, arena);
 991     T sub(*static_cast<T *>(this), subtydesc->shape, params,
 992           subtydesc->shape_tables, obj_closure_dp);
 993     sub.align = true;
 994     sub.walk();
 995 }
 996
 997
 998 // Polymorphic logging, for convenience
 999
1000 class log : public data<log,ptr> {
1001     friend class data<log,ptr>;
1002
1003 private:
1004     std::ostream &out;
1005     const char *prefix;
1006     bool in_string;
1007
1008     log(log &other,
1009         const uint8_t *in_sp,
1010         const type_param *in_params,
1011         const rust_shape_tables *in_tables = NULL)
1012     : data<log,ptr>(other.task,
1013                     other.align,
1014                     in_sp,
1015                     in_params,
1016                     in_tables ? in_tables : other.tables,
1017                     other.dp),
1018       out(other.out),
1019       prefix("") {}
1020
1021     log(log &other,
1022         const uint8_t *in_sp,
1023         const type_param *in_params,
1024         const rust_shape_tables *in_tables,
1025         ptr in_dp)
1026     : data<log,ptr>(other.task,
1027                     other.align,
1028                     in_sp,
1029                     in_params,
1030                     in_tables,
1031                     in_dp),
1032       out(other.out),
1033       prefix("") {}
1034
1035     log(log &other, ptr in_dp)
1036     : data<log,ptr>(other.task,
1037                     other.align,
1038                     other.sp,
1039                     other.params,
1040                     other.tables,
1041                     in_dp),
1042       out(other.out),
1043       prefix("") {}
1044
1045     void walk_vec(bool is_pod, uint16_t sp_size) {
1046         if (!get_dp<void *>(dp))
1047             out << prefix << "(null)";
1048         else
1049             walk_vec(is_pod, get_vec_data_range(dp));
1050     }
1051
1052     void walk_tag(tag_info &tinfo, tag_variant_t tag_variant) {
1053         out << prefix << "tag" << tag_variant;
1054         data<log,ptr>::walk_variant(tinfo, tag_variant);
1055     }
1056
1057     void walk_box() {
1058         out << prefix << "@";
1059         prefix = "";
1060         data<log,ptr>::walk_box_contents();
1061     }
1062
1063     void walk_uniq() {
1064         out << prefix << "~";
1065         prefix = "";
1066         data<log,ptr>::walk_uniq_contents();
1067     }
1068
1069     void walk_fn() {
1070         out << prefix << "fn";
1071         prefix = "";
1072         data<log,ptr>::walk_fn_contents(dp);
1073     }
1074
1075     void walk_obj() {
1076         out << prefix << "obj";
1077         prefix = "";
1078         data<log,ptr>::walk_obj_contents(dp);
1079     }
1080
1081     void walk_subcontext(log &sub) { sub.walk(); }
1082
1083     void walk_box_contents(log &sub, ptr &ref_count_dp) {
1084         out << prefix;
1085         if (!ref_count_dp) {
1086             out << "(null)";
1087         } else {
1088             sub.align = true;
1089             sub.walk();
1090         }
1091     }
1092
1093     void walk_uniq_contents(log &sub) {
1094         out << prefix;
1095         sub.align = true;
1096         sub.walk();
1097     }
1098
1099     void walk_struct(const uint8_t *end_sp);
1100     void walk_vec(bool is_pod, const std::pair<ptr,ptr> &data);
1101     void walk_variant(tag_info &tinfo, tag_variant_t variant_id,
1102                       const std::pair<const uint8_t *,const uint8_t *>
1103                       variant_ptr_and_end);
1104     void walk_string(const std::pair<ptr,ptr> &data);
1105     void walk_res(const rust_fn *dtor, unsigned n_params,
1106                   const type_param *params, const uint8_t *end_sp, bool live);
1107
1108     template<typename T>
1109     inline void walk_number() {
1110         out << prefix;
1111         fmt_number(out, get_dp<T>(dp));
1112     }
1113
1114 public:
1115     log(rust_task *in_task,
1116         bool in_align,
1117         const uint8_t *in_sp,
1118         const type_param *in_params,
1119         const rust_shape_tables *in_tables,
1120         uint8_t *in_data,
1121         std::ostream &in_out)
1122     : data<log,ptr>(in_task, in_align, in_sp, in_params, in_tables, in_data),
1123       out(in_out),
1124       prefix("") {}
1125 };
1126
1127 }   // end namespace shape
1128
1129 #endif
1130