runtime/objc-layout.m

   1 /*
   2  * Copyright (c) 2004-2007 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23
  24 #include <stdlib.h>
  25 #include <assert.h>
  26
  27 #import "objc-private.h"
  28
  29 /**********************************************************************
  30 * Object Layouts.
  31 *
  32 * Layouts are used by the garbage collector to identify references from
  33 * the object to other objects.
  34 *
  35 * Layout information is in the form of a '\0' terminated byte string.
  36 * Each byte contains a word skip count in the high nibble and a
  37 * consecutive references count in the low nibble. Counts that exceed 15 are
  38 * continued in the succeeding byte with a zero in the opposite nibble.
  39 * Objects that should be scanned conservatively will have a NULL layout.
  40 * Objects that have no references have a empty byte string.
  41 *
  42 * Example;
  43 *
  44 *   For a class with pointers at offsets 4,12, 16, 32-128
  45 *   the layout is { 0x11, 0x12, 0x3f, 0x0a, 0x00 } or
  46 *       skip 1 - 1 reference (4)
  47 *       skip 1 - 2 references (12, 16)
  48 *       skip 3 - 15 references (32-88)
  49 *       no skip - 10 references (92-128)
  50 *       end
  51 *
  52 **********************************************************************/
  53
  54
  55 /**********************************************************************
  56 * generate_layout_bytes
  57 *
  58 * Generates the layout bytes representing the specified skip and run.
  59 * If layout is NULL the can be used to determine the number of bytes added
  60 * to the layout.  Returns number of bytes added.
  61 *
  62 **********************************************************************/
  63 #define NIBBLE_MAX 0xf
  64 static long generate_layout_bytes(long skip, long run, unsigned char *layout) {
  65     // number of bytes added
  66     long count = 0;
  67
  68     // if the skip is greater what can be put in a nibble
  69     while (skip > NIBBLE_MAX) {
  70         // add a skip with no run if layout is not NULL
  71         if (layout) *layout++ = NIBBLE_MAX << 4;
  72
  73         // another byte added
  74         count++;
  75
  76         // decrement skip by nibble maximum
  77         skip -= NIBBLE_MAX;
  78     }
  79
  80     // add remaining skip and run (modulo nibble size) if layout is not NULL
  81     if (layout) *layout++ = (skip << 4) | (run % NIBBLE_MAX);
  82
  83     // another byte added
  84     count++;
  85
  86
  87     // if the run is greater what can be put in a nibble
  88     while (run > NIBBLE_MAX) {
  89         // add a run with no skip if layout is not NULL
  90         if (layout) *layout++ = NIBBLE_MAX;
  91
  92         // another byte added
  93         count++;
  94
  95         // decrement run by nibble maximum
  96         run -= NIBBLE_MAX;
  97     }
  98
  99     // return number of bytes added
 100     return count;
 101 }
 102
 103
 104 /**********************************************************************
 105 * scan_bits_for_layout
 106 *
 107 * Generate the layout from the bit map.  If layout is NULL then can be used to
 108 * determine the size of the layout.  Returns size of layout array in bytes
 109 * including the '\0' terminator.
 110 *
 111 **********************************************************************/
 112 static unsigned char *compress_layout(const uint8_t *bits, size_t bitmap_bits, BOOL weak)
 113 {
 114     long count = 0;                     // number of bytes generated
 115     long skip = 0;                      // number of slots to skip to get to next references
 116     long run = 0;                       // number of consecutive references
 117     long last_bit = 0;                  // state of last bit encountered
 118     BOOL all_set = YES;
 119     BOOL none_set = YES;
 120
 121     unsigned char *layout = _calloc_internal(bitmap_bits + 1, 1);
 122
 123     // iterate through bits in bits array
 124     long i;
 125     for (i = 0; i < bitmap_bits; i++) {
 126         // determine next bit, 0 = not a reference, 1 indicates a reference
 127         long bit = (bits[i/8] >> (i % 8)) & 1;
 128
 129         // if not a reference and last bit was a reference then record skip and run
 130         if (!bit && last_bit) {
 131             //  record skip and run
 132             count += generate_layout_bytes(skip, run, layout + count);
 133
 134             // reset counts
 135             skip = 0; run = 0;
 136         }
 137
 138         // record the skip or run
 139         if (bit) run++, none_set = NO;
 140         else skip++, all_set = NO;
 141
 142         // track state of last bit
 143         last_bit = bit;
 144     }
 145
 146     // Record last skip and run, if any.
 147     if (skip || run) count += generate_layout_bytes(skip, run, layout + count);
 148
 149     // insert terminating byte
 150     layout[count] = '\0';
 151     count++;
 152
 153     // return result
 154     unsigned char *result;
 155     if (none_set  &&  weak) {
 156         result = NULL;  // NULL weak layout means none-weak
 157     } else if (all_set  &&  !weak) {
 158         result = NULL;  // NULL ivar layout means all-scanned
 159     } else {
 160         result = (unsigned char *)_strdup_internal((char *)layout);
 161     }
 162     _free_internal(layout);
 163     return result;
 164 }
 165
 166
 167 static void set_bits(layout_bitmap bits, size_t which, size_t count)
 168 {
 169     // fixme optimize for byte/word at a time
 170     size_t bit;
 171     for (bit = which; bit < which + count  &&  bit < bits.bitCount; bit++) {
 172         bits.bits[bit/8] |= 1 << (bit % 8);
 173     }
 174     if (bit == bits.bitCount  &&  bit < which + count) {
 175         // couldn't fit full type in bitmap
 176         _objc_fatal("layout bitmap too short");
 177     }
 178 }
 179
 180 static void clear_bits(layout_bitmap bits, size_t which, size_t count)
 181 {
 182     // fixme optimize for byte/word at a time
 183     size_t bit;
 184     for (bit = which; bit < which + count  &&  bit < bits.bitCount; bit++) {
 185         bits.bits[bit/8] &= ~(1 << (bit % 8));
 186     }
 187     if (bit == bits.bitCount  &&  bit < which + count) {
 188         // couldn't fit full type in bitmap
 189         _objc_fatal("layout bitmap too short");
 190     }
 191 }
 192
 193 static void move_bits(layout_bitmap bits, size_t src, size_t dst,
 194                       size_t count)
 195 {
 196     // fixme optimize for byte/word at a time
 197     // Copy backwards in case of overlap
 198     assert(dst >= src);
 199     while (count--) {
 200         size_t srcbit = src + count;
 201         size_t dstbit = dst + count;
 202         if (bits.bits[srcbit/8] & (1 << (srcbit % 8))) {
 203             bits.bits[dstbit/8] |= 1 << (dstbit % 8);
 204         } else {
 205             bits.bits[dstbit/8] &= ~(1 << (dstbit % 8));
 206         }
 207     }
 208 }
 209
 210 // emacs autoindent hack - it doesn't like the loop in set_bits/clear_bits
 211 #if 0
 212 } }
 213 #endif
 214
 215
 216 static void decompress_layout(const unsigned char *layout_string, layout_bitmap bits)
 217 {
 218     unsigned char c;
 219     size_t bit = 0;
 220     while ((c = *layout_string++)) {
 221         unsigned char skip = (c & 0xf0) >> 4;
 222         unsigned char scan = (c & 0x0f);
 223         bit += skip;
 224         set_bits(bits, bit, scan);
 225         bit += scan;
 226     }
 227 }
 228
 229
 230 /***********************************************************************
 231 * layout_bitmap_create
 232 * Allocate a layout bitmap.
 233 * The new bitmap spans the given instance size bytes.
 234 * The start of the bitmap is filled from the given layout string (which
 235 *   spans an instance size of layoutStringSize); the rest is zero-filled.
 236 * The returned bitmap must be freed with layout_bitmap_free().
 237 **********************************************************************/
 238 __private_extern__ layout_bitmap
 239 layout_bitmap_create(const unsigned char *layout_string,
 240                      size_t layoutStringInstanceSize,
 241                      size_t instanceSize, BOOL weak)
 242 {
 243     layout_bitmap result;
 244     size_t words = instanceSize / sizeof(id);
 245     size_t bitmap_bytes = (words+7)/8;
 246
 247     result.bits = _calloc_internal(bitmap_bytes, 1);
 248     result.weak = weak;
 249     result.bitCount = words;
 250     result.bitsAllocated = bitmap_bytes * 8;
 251     assert(bits->bitsAllocated % 8 == 0);
 252
 253     if (!layout_string) {
 254         if (!weak) {
 255             // NULL ivar layout means all-scanned
 256             // (but only up to layoutStringSize instance size)
 257             set_bits(result, 0, layoutStringInstanceSize/sizeof(id));
 258         } else {
 259             // NULL weak layout means none-weak.
 260         }
 261     } else {
 262         decompress_layout(layout_string, result);
 263     }
 264
 265     return result;
 266 }
 267
 268 __private_extern__ void
 269 layout_bitmap_free(layout_bitmap bits)
 270 {
 271     if (bits.bits) _free_internal(bits.bits);
 272 }
 273
 274 __private_extern__ const unsigned char *
 275 layout_string_create(layout_bitmap bits)
 276 {
 277     return compress_layout(bits.bits, bits.bitCount, bits.weak);
 278 }
 279
 280
 281 /***********************************************************************
 282 * layout_bitmap_or
 283 * Set dst=dst|src.
 284 * dst must be at least as long as src.
 285 * Returns YES if any of dst's bits were changed.
 286 **********************************************************************/
 287 __private_extern__ BOOL
 288 layout_bitmap_or(layout_bitmap dst, layout_bitmap src, const char *msg)
 289 {
 290     if (dst.bitCount < src.bitCount) {
 291       _objc_fatal("layout bitmap too short%s%s", msg ? ": " : "", msg ?: "");
 292     }
 293
 294     BOOL changed = NO;
 295
 296     // fixme optimize for byte/word at a time
 297     size_t bit;
 298     for (bit = 0; bit < src.bitCount; bit++) {
 299         int dstset = dst.bits[bit/8] & (1 << (bit % 8));
 300         int srcset = src.bits[bit/8] & (1 << (bit % 8));
 301         if (srcset  &&  !dstset) {
 302             changed = YES;
 303             dst.bits[bit/8] |= 1 << (bit % 8);
 304         }
 305     }
 306
 307     return changed;
 308 }
 309
 310
 311 __private_extern__ void
 312 layout_bitmap_set_ivar(layout_bitmap bits, const char *type, size_t offset)
 313 {
 314     // fixme only handles id and array of id
 315     size_t bit = offset / sizeof(id);
 316
 317     if (!type) return;
 318     if (type[0] == '@') {
 319         set_bits(bits, bit, 1);
 320     } else if (type[0] == '[') {
 321         char *t;
 322         unsigned long count = strtoul(type+1, &t, 10);
 323         if (t  &&  t[0] == '@') {
 324             set_bits(bits, bit, count);
 325         }
 326     } else if (strchr(type, '@')) {
 327         _objc_inform("warning: failing to set GC layout for '%s'\n", type);
 328     }
 329 }
 330
 331
 332
 333 /***********************************************************************
 334 * layout_bitmap_grow
 335 * Expand a layout bitmap to span newCount bits.
 336 * The new bits are undefined.
 337 **********************************************************************/
 338 __private_extern__ void
 339 layout_bitmap_grow(layout_bitmap *bits, size_t newCount)
 340 {
 341     if (bits->bitCount >= newCount) return;
 342     size_t addition = newCount - bits->bitCount;
 343     bits->bitCount = newCount;
 344     if (bits->bitCount > bits->bitsAllocated) {
 345         bits->bitsAllocated += bits->bitsAllocated + (addition+7)/8;
 346         bits->bits = _realloc_internal(bits->bits, bits->bitsAllocated);
 347     }
 348     assert(bits->bitsAllocated % 8 == 0);
 349 }
 350
 351
 352 /***********************************************************************
 353 * layout_bitmap_slide
 354 * Slide the end of a layout bitmap farther from the start.
 355 * Slides bits [oldPos, bits.bitCount) to [newPos, bits.bitCount+newPos-oldPos)
 356 * Bits [oldPos, newPos) are zero-filled.
 357 * The bitmap is expanded and bitCount updated if necessary.
 358 * newPos >= oldPos.
 359 **********************************************************************/
 360 __private_extern__ void
 361 layout_bitmap_slide(layout_bitmap *bits, size_t oldPos, size_t newPos)
 362 {
 363     if (oldPos >= newPos) _objc_fatal("layout bitmap sliding backwards");
 364
 365     size_t shift = newPos - oldPos;
 366     size_t count = bits->bitCount - oldPos;
 367     layout_bitmap_grow(bits, bits->bitCount + shift);
 368     move_bits(*bits, oldPos, newPos, count);  // slide
 369     clear_bits(*bits, oldPos, shift);         // zero-fill
 370 }
 371
 372
 373 /***********************************************************************
 374 * layout_bitmap_splat
 375 * Pastes the contents of bitmap src to the start of bitmap dst.
 376 * dst bits between the end of src and oldSrcInstanceSize are zeroed.
 377 * dst must be at least as long as src.
 378 * Returns YES if any of dst's bits were changed.
 379 **********************************************************************/
 380 __private_extern__ BOOL
 381 layout_bitmap_splat(layout_bitmap dst, layout_bitmap src,
 382                     size_t oldSrcInstanceSize)
 383 {
 384     if (dst.bitCount < src.bitCount) _objc_fatal("layout bitmap too short");
 385
 386     BOOL changed = NO;
 387     size_t oldSrcBitCount = oldSrcInstanceSize / sizeof(id);
 388
 389     // fixme optimize for byte/word at a time
 390     size_t bit;
 391     for (bit = 0; bit < oldSrcBitCount; bit++) {
 392         int dstset = dst.bits[bit/8] & (1 << (bit % 8));
 393         int srcset = (bit < src.bitCount)
 394             ? src.bits[bit/8] & (1 << (bit % 8))
 395             : 0;
 396         if (dstset != srcset) {
 397             changed = YES;
 398             if (srcset) {
 399                 dst.bits[bit/8] |= 1 << (bit % 8);
 400             } else {
 401                 dst.bits[bit/8] &= ~(1 << (bit % 8));
 402             }
 403         }
 404     }
 405
 406     return changed;
 407 }
 408
 409
 410 #if 0
 411 // The code below may be useful when interpreting ivar types more precisely.
 412
 413 /**********************************************************************
 414 * mark_offset_for_layout
 415 *
 416 * Marks the appropriate bit in the bits array cooresponding to a the
 417 * offset of a reference.  If we are scanning a nested pointer structure
 418 * then the bits array will be NULL then this function does nothing.
 419 *
 420 **********************************************************************/
 421 static void mark_offset_for_layout(long offset, long bits_size, unsigned char *bits) {
 422     // references are ignored if bits is NULL
 423     if (bits) {
 424         long slot = offset / sizeof(long);
 425
 426         // determine byte index using (offset / 8 bits per byte)
 427         long i_byte = slot >> 3;
 428
 429         // if the byte index is valid
 430         if (i_byte < bits_size) {
 431             // set the (offset / 8 bits per byte)th bit
 432             bits[i_byte] |= 1 << (slot & 7);
 433         } else {
 434             // offset not within instance size
 435             _objc_inform ("layout - offset exceeds instance size");
 436         }
 437     }
 438 }
 439
 440 /**********************************************************************
 441 * skip_ivar_type_name
 442 *
 443 * Skip over the name of a field/class in an ivar type string.  Names
 444 * are in the form of a double-quoted string.  Returns the remaining
 445 * string.
 446 *
 447 **********************************************************************/
 448 static char *skip_ivar_type_name(char *type) {
 449     // current character
 450     char ch;
 451
 452     // if there is an open quote
 453     if (*type == '\"') {
 454         // skip quote
 455         type++;
 456
 457         // while no closing quote
 458         while ((ch = *type) != '\"') {
 459             // if end of string return end of string
 460             if (!ch) return type;
 461
 462             // skip character
 463             type++;
 464         }
 465
 466         // skip closing quote
 467         type++;
 468     }
 469
 470     // return remaining string
 471     return type;
 472 }
 473
 474
 475 /**********************************************************************
 476 * skip_ivar_struct_name
 477 *
 478 * Skip over the name of a struct in an ivar type string.  Names
 479 * may be followed by an equals sign.  Returns the remaining string.
 480 *
 481 **********************************************************************/
 482 static char *skip_ivar_struct_name(char *type) {
 483     // get first character
 484     char ch = *type;
 485
 486     if (ch == _C_UNDEF) {
 487         // skip undefined name
 488         type++;
 489     } else if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || ch == '_') {
 490         // if alphabetic
 491
 492         // scan alphanumerics
 493         do {
 494             // next character
 495             ch = *++type;
 496         } while ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || ch == '_' || (ch >= '0' && ch <= '9'));
 497     } else {
 498         // no struct name present
 499         return type;
 500     }
 501
 502     // skip equals sign
 503     if (*type == '=') type++;
 504
 505     return type;
 506 }
 507
 508
 509 /**********************************************************************
 510 * scan_basic_ivar_type
 511 *
 512 * Determines the size and alignment of a basic ivar type.  If the basic
 513 * type is a possible reference to another garbage collected type the
 514 * is_reference is set to true (false otherwise.)  Returns the remaining
 515 * string.
 516 *
 517 **********************************************************************/
 518 static char *scan_ivar_type_for_layout(char *type, long offset, long bits_size, unsigned char *bits, long *next_offset);
 519 static char *scan_basic_ivar_type(char *type, long *size, long *alignment, BOOL *is_reference) {
 520     // assume it is a non-reference type
 521     *is_reference = NO;
 522
 523     // get the first character (advancing string)
 524     const char *full_type = type;
 525     char ch = *type++;
 526
 527     // GCC 4 uses for const type*.
 528     if (ch == _C_CONST) ch = *type++;
 529
 530     // act on first character
 531     switch (ch) {
 532         case _C_ID: {
 533             // ID type
 534
 535             // skip over optional class name
 536             type = skip_ivar_type_name(type);
 537
 538             // size and alignment of an id type
 539             *size = sizeof(id);
 540             *alignment = __alignof(id);
 541
 542             // is a reference type
 543             *is_reference = YES;
 544             break;
 545         }
 546         case _C_PTR: {
 547             // C pointer type
 548
 549             // skip underlying type
 550             long ignored_offset;
 551             type = scan_ivar_type_for_layout(type, 0, 0, NULL, &ignored_offset);
 552
 553             // size and alignment of a generic pointer type
 554             *size = sizeof(void *);
 555             *alignment = __alignof(void *);
 556
 557             // is a reference type
 558             *is_reference = YES;
 559             break;
 560         }
 561         case _C_CHARPTR: {
 562             // C string
 563
 564            // size and alignment of a char pointer type
 565             *size = sizeof(char *);
 566             *alignment = __alignof(char *);
 567
 568             // is a reference type
 569             *is_reference = YES;
 570             break;
 571         }
 572         case _C_CLASS:
 573         case _C_SEL: {
 574             // classes and selectors are ignored for now
 575             *size = sizeof(void *);
 576             *alignment = __alignof(void *);
 577             break;
 578         }
 579         case _C_CHR:
 580         case _C_UCHR: {
 581             // char and unsigned char
 582             *size = sizeof(char);
 583             *alignment = __alignof(char);
 584             break;
 585         }
 586         case _C_SHT:
 587         case _C_USHT: {
 588             // short and unsigned short
 589             *size = sizeof(short);
 590             *alignment = __alignof(short);
 591             break;
 592         }
 593         case _C_ATOM:
 594         case _C_INT:
 595         case _C_UINT: {
 596             // int and unsigned int
 597             *size = sizeof(int);
 598             *alignment = __alignof(int);
 599             break;
 600         }
 601         case _C_LNG:
 602         case _C_ULNG: {
 603             // long and unsigned long
 604             *size = sizeof(long);
 605             *alignment = __alignof(long);
 606             break;
 607         }
 608         case _C_LNG_LNG:
 609         case _C_ULNG_LNG: {
 610             // long long and unsigned long long
 611             *size = sizeof(long long);
 612             *alignment = __alignof(long long);
 613             break;
 614         }
 615         case _C_VECTOR: {
 616             // vector
 617             *size = 16;
 618             *alignment = 16;
 619             break;
 620         }
 621         case _C_FLT: {
 622             // float
 623             *size = sizeof(float);
 624             *alignment = __alignof(float);
 625             break;
 626         }
 627         case _C_DBL: {
 628             // double
 629             *size = sizeof(double);
 630             *alignment = __alignof(double);
 631             break;
 632         }
 633         case _C_BFLD: {
 634             // bit field
 635
 636             // get number of bits in bit field (advance type string)
 637             long lng = strtol(type, &type, 10);
 638
 639             // while next type is a bit field
 640             while (*type == _C_BFLD) {
 641                 // skip over _C_BFLD
 642                 type++;
 643
 644                 // get next bit field length
 645                 long next_lng = strtol(type, &type, 10);
 646
 647                 // if spans next word then align to next word
 648                 if ((lng & ~31) != ((lng + next_lng) & ~31)) lng = (lng + 31) & ~31;
 649
 650                 // increment running length
 651                 lng += next_lng;
 652
 653                 // skip over potential field name
 654                 type = skip_ivar_type_name(type);
 655             }
 656
 657             // determine number of bytes bits represent
 658             *size = (lng + 7) / 8;
 659
 660             // byte alignment
 661             *alignment = __alignof(char);
 662             break;
 663         }
 664         case _C_BOOL: {
 665             // double
 666             *size = sizeof(BOOL);
 667             *alignment = __alignof(BOOL);
 668             break;
 669         }
 670         case _C_VOID: {
 671             // skip void types
 672             *size = 0;
 673             *alignment = __alignof(char);
 674             break;
 675         }
 676         case _C_UNDEF: {
 677             *size = 0;
 678             *alignment = __alignof(char);
 679             break;
 680         }
 681         default: {
 682             // unhandled type
 683             _objc_fatal("unrecognized character \'%c\' in ivar type: \"%s\"", ch, full_type);
 684         }
 685     }
 686
 687     return type;
 688 }
 689
 690
 691 /**********************************************************************
 692 * scan_ivar_type_for_layout
 693 *
 694 * Scan an ivar type string looking for references.  The offset indicates
 695 * where the ivar begins.  bits is a byte array of size bits_size used to
 696 * contain the references bit map.  next_offset is the offset beyond the
 697 * ivar.  Returns the remaining string.
 698 *
 699 **********************************************************************/
 700 static char *scan_ivar_type_for_layout(char *type, long offset, long bits_size, unsigned char *bits, long *next_offset) {
 701     long size;                                   // size of a basic type
 702     long alignment;                              // alignment of the basic type
 703     BOOL is_reference;                      // true if the type indicates a reference to a garbage collected object
 704
 705     // get the first character
 706     char ch = *type;
 707
 708     // GCC 4 uses for const type*.
 709     if (ch == _C_CONST) ch = *++type;
 710
 711     // act on first character
 712     switch (ch) {
 713         case _C_ARY_B: {
 714             // array type
 715
 716             // get the array length
 717             long lng = strtol(type + 1, &type, 10);
 718
 719             // next type will be where to advance the type string once the array is processed
 720             char *next_type = type;
 721
 722             // repeat the next type x lng
 723             if (!lng) {
 724                 next_type = scan_ivar_type_for_layout(type, 0, 0, NULL, &offset);
 725             } else {
 726                 while (lng--) {
 727                     // repeatedly scan the same type
 728                     next_type = scan_ivar_type_for_layout(type, offset, bits_size, bits, &offset);
 729                 }
 730             }
 731
 732             // advance the type now
 733             type = next_type;
 734
 735             // after the end of the array
 736             *next_offset = offset;
 737
 738             // advance over closing bracket
 739             if (*type == _C_ARY_E) type++;
 740             else                   _objc_inform("missing \'%c\' in ivar type.", _C_ARY_E);
 741
 742             break;
 743         }
 744         case _C_UNION_B: {
 745             // union type
 746
 747             // skip over possible union name
 748             type = skip_ivar_struct_name(type + 1);
 749
 750             // need to accumulate the maximum element offset
 751             long max_offset = 0;
 752
 753             // while not closing paren
 754             while ((ch = *type) && ch != _C_UNION_E) {
 755                 // skip over potential field name
 756                 type = skip_ivar_type_name(type);
 757
 758                 // scan type
 759                 long union_offset;
 760                 type = scan_ivar_type_for_layout(type, offset, bits_size, bits, &union_offset);
 761
 762                 // adjust the maximum element offset
 763                 if (max_offset < union_offset) max_offset = union_offset;
 764             }
 765
 766             // after the largest element
 767             *next_offset = max_offset;
 768
 769             // advance over closing paren
 770             if (ch == _C_UNION_E) {
 771               type++;
 772             } else {
 773               _objc_inform("missing \'%c\' in ivar type", _C_UNION_E);
 774             }
 775
 776             break;
 777         }
 778         case _C_STRUCT_B: {
 779             // struct type
 780
 781             // skip over possible struct name
 782             type = skip_ivar_struct_name(type + 1);
 783
 784             // while not closing brace
 785             while ((ch = *type) && ch != _C_STRUCT_E) {
 786                 // skip over potential field name
 787                 type = skip_ivar_type_name(type);
 788
 789                 // scan type
 790                 type = scan_ivar_type_for_layout(type, offset, bits_size, bits, &offset);
 791             }
 792
 793             // after the end of the struct
 794             *next_offset = offset;
 795
 796             // advance over closing brace
 797             if (ch == _C_STRUCT_E) type++;
 798             else                   _objc_inform("missing \'%c\' in ivar type", _C_STRUCT_E);
 799
 800             break;
 801         }
 802         default: {
 803             // basic type
 804
 805             // scan type
 806             type = scan_basic_ivar_type(type, &size, &alignment, &is_reference);
 807
 808             // create alignment mask
 809             alignment--;
 810
 811             // align offset
 812             offset = (offset + alignment) & ~alignment;
 813
 814             // if is a reference then mark in the bit map
 815             if (is_reference) mark_offset_for_layout(offset, bits_size, bits);
 816
 817             // after the basic type
 818             *next_offset = offset + size;
 819             break;
 820         }
 821     }
 822
 823     // return remainder of type string
 824     return type;
 825 }
 826
 827 #endif