1/*
2 * Copyright (c) 2004-2008 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#include "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* compress_layout
57* Allocates and returns a compressed string matching the given layout bitmap.
58**********************************************************************/
59static unsigned char *
60compress_layout(const uint8_t *bits, size_t bitmap_bits, BOOL weak)
61{
62    BOOL all_set = YES;
63    BOOL none_set = YES;
64    unsigned char *result;
65
66    // overallocate a lot; reallocate at correct size later
67    unsigned char * const layout = (unsigned char *)
68        _calloc_internal(bitmap_bits + 1, 1);
69    unsigned char *l = layout;
70
71    size_t i = 0;
72    while (i < bitmap_bits) {
73        size_t skip = 0;
74        size_t scan = 0;
75
76        // Count one range each of skip and scan.
77        while (i < bitmap_bits) {
78            uint8_t bit = (uint8_t)((bits[i/8] >> (i % 8)) & 1);
79            if (bit) break;
80            i++;
81            skip++;
82        }
83        while (i < bitmap_bits) {
84            uint8_t bit = (uint8_t)((bits[i/8] >> (i % 8)) & 1);
85            if (!bit) break;
86            i++;
87            scan++;
88            none_set = NO;
89        }
90
91        // Record skip and scan
92        if (skip) all_set = NO;
93        if (scan) none_set = NO;
94        while (skip > 0xf) {
95            *l++ = 0xf0;
96            skip -= 0xf;
97        }
98        if (skip || scan) {
99            *l = (uint8_t)(skip << 4);    // NOT incremented - merges with scan
100            while (scan > 0xf) {
101                *l++ |= 0x0f;  // May merge with short skip; must calloc
102                scan -= 0xf;
103            }
104            *l++ |= scan;      // NOT checked for zero - always increments
105                               // May merge with short skip; must calloc
106        }
107    }
108
109    // insert terminating byte
110    *l++ = '\0';
111
112    // return result
113    if (none_set  &&  weak) {
114        result = NULL;  // NULL weak layout means none-weak
115    } else if (all_set  &&  !weak) {
116        result = NULL;  // NULL ivar layout means all-scanned
117    } else {
118        result = (unsigned char *)_strdup_internal((char *)layout);
119    }
120    _free_internal(layout);
121    return result;
122}
123
124
125static void set_bits(layout_bitmap bits, size_t which, size_t count)
126{
127    // fixme optimize for byte/word at a time
128    size_t bit;
129    for (bit = which; bit < which + count  &&  bit < bits.bitCount; bit++) {
130        bits.bits[bit/8] |= 1 << (bit % 8);
131    }
132    if (bit == bits.bitCount  &&  bit < which + count) {
133        // couldn't fit full type in bitmap
134        _objc_fatal("layout bitmap too short");
135    }
136}
137
138static void clear_bits(layout_bitmap bits, size_t which, size_t count)
139{
140    // fixme optimize for byte/word at a time
141    size_t bit;
142    for (bit = which; bit < which + count  &&  bit < bits.bitCount; bit++) {
143        bits.bits[bit/8] &= ~(1 << (bit % 8));
144    }
145    if (bit == bits.bitCount  &&  bit < which + count) {
146        // couldn't fit full type in bitmap
147        _objc_fatal("layout bitmap too short");
148    }
149}
150
151static void move_bits(layout_bitmap bits, size_t src, size_t dst,
152                      size_t count)
153{
154    // fixme optimize for byte/word at a time
155
156    if (dst == src) {
157        return;
158    }
159    else if (dst > src) {
160        // Copy backwards in case of overlap
161        size_t pos = count;
162        while (pos--) {
163            size_t srcbit = src + pos;
164            size_t dstbit = dst + pos;
165            if (bits.bits[srcbit/8] & (1 << (srcbit % 8))) {
166                bits.bits[dstbit/8] |= 1 << (dstbit % 8);
167            } else {
168                bits.bits[dstbit/8] &= ~(1 << (dstbit % 8));
169            }
170        }
171    }
172    else {
173        // Copy forwards in case of overlap
174        size_t pos;
175        for (pos = 0; pos < count; pos++) {
176            size_t srcbit = src + pos;
177            size_t dstbit = dst + pos;
178            if (bits.bits[srcbit/8] & (1 << (srcbit % 8))) {
179                bits.bits[dstbit/8] |= 1 << (dstbit % 8);
180            } else {
181                bits.bits[dstbit/8] &= ~(1 << (dstbit % 8));
182            }
183        }
184    }
185}
186
187// emacs autoindent hack - it doesn't like the loop in set_bits/clear_bits
188#if 0
189} }
190#endif
191
192
193static void decompress_layout(const unsigned char *layout_string, layout_bitmap bits)
194{
195    unsigned char c;
196    size_t bit = 0;
197    while ((c = *layout_string++)) {
198        unsigned char skip = (c & 0xf0) >> 4;
199        unsigned char scan = (c & 0x0f);
200        bit += skip;
201        set_bits(bits, bit, scan);
202        bit += scan;
203    }
204}
205
206
207/***********************************************************************
208* layout_bitmap_create
209* Allocate a layout bitmap.
210* The new bitmap spans the given instance size bytes.
211* The start of the bitmap is filled from the given layout string (which
212*   spans an instance size of layoutStringSize); the rest is zero-filled.
213* The returned bitmap must be freed with layout_bitmap_free().
214**********************************************************************/
215layout_bitmap
216layout_bitmap_create(const unsigned char *layout_string,
217                     size_t layoutStringInstanceSize,
218                     size_t instanceSize, BOOL weak)
219{
220    layout_bitmap result;
221    size_t words = instanceSize / sizeof(id);
222
223    result.weak = weak;
224    result.bitCount = words;
225    result.bitsAllocated = words;
226    result.bits = (uint8_t *)_calloc_internal((words+7)/8, 1);
227
228    if (!layout_string) {
229        if (!weak) {
230            // NULL ivar layout means all-scanned
231            // (but only up to layoutStringSize instance size)
232            set_bits(result, 0, layoutStringInstanceSize/sizeof(id));
233        } else {
234            // NULL weak layout means none-weak.
235        }
236    } else {
237        decompress_layout(layout_string, result);
238    }
239
240    return result;
241}
242
243
244/***********************************************************************
245 * layout_bitmap_create_empty
246 * Allocate a layout bitmap.
247 * The new bitmap spans the given instance size bytes.
248 * The bitmap is empty, to represent an object whose ivars are completely unscanned.
249 * The returned bitmap must be freed with layout_bitmap_free().
250 **********************************************************************/
251layout_bitmap
252layout_bitmap_create_empty(size_t instanceSize, BOOL weak)
253{
254    layout_bitmap result;
255    size_t words = instanceSize / sizeof(id);
256
257    result.weak = weak;
258    result.bitCount = words;
259    result.bitsAllocated = words;
260    result.bits = (uint8_t *)_calloc_internal((words+7)/8, 1);
261
262    return result;
263}
264
265void
266layout_bitmap_free(layout_bitmap bits)
267{
268    if (bits.bits) _free_internal(bits.bits);
269}
270
271const unsigned char *
272layout_string_create(layout_bitmap bits)
273{
274    const unsigned char *result =
275        compress_layout(bits.bits, bits.bitCount, bits.weak);
276
277#ifndef NDEBUG
278    // paranoia: cycle to bitmap and back to string again, and compare
279    layout_bitmap check = layout_bitmap_create(result, bits.bitCount*sizeof(id),
280                                               bits.bitCount*sizeof(id), bits.weak);
281    unsigned char *result2 =
282        compress_layout(check.bits, check.bitCount, check.weak);
283    if (result != result2  &&  0 != strcmp((char*)result, (char *)result2)) {
284        layout_bitmap_print(bits);
285        layout_bitmap_print(check);
286        _objc_fatal("libobjc bug: mishandled layout bitmap");
287    }
288    free(result2);
289    layout_bitmap_free(check);
290#endif
291
292    return result;
293}
294
295
296void
297layout_bitmap_set_ivar(layout_bitmap bits, const char *type, size_t offset)
298{
299    // fixme only handles some types
300    size_t bit = offset / sizeof(id);
301
302    if (!type) return;
303    if (type[0] == '@'  ||  0 == strcmp(type, "^@")) {
304        // id
305        // id *
306        // Block ("@?")
307        set_bits(bits, bit, 1);
308    }
309    else if (type[0] == '[') {
310        // id[]
311        char *t;
312        unsigned long count = strtoul(type+1, &t, 10);
313        if (t  &&  t[0] == '@') {
314            set_bits(bits, bit, count);
315        }
316    }
317    else if (strchr(type, '@')) {
318        _objc_inform("warning: failing to set GC layout for '%s'\n", type);
319    }
320}
321
322
323
324/***********************************************************************
325* layout_bitmap_grow
326* Expand a layout bitmap to span newCount bits.
327* The new bits are undefined.
328**********************************************************************/
329void
330layout_bitmap_grow(layout_bitmap *bits, size_t newCount)
331{
332    if (bits->bitCount >= newCount) return;
333    bits->bitCount = newCount;
334    if (bits->bitsAllocated < newCount) {
335        size_t newAllocated = bits->bitsAllocated * 2;
336        if (newAllocated < newCount) newAllocated = newCount;
337        bits->bits = (uint8_t *)
338            _realloc_internal(bits->bits, (newAllocated+7) / 8);
339        bits->bitsAllocated = newAllocated;
340    }
341    assert(bits->bitsAllocated >= bits->bitCount);
342    assert(bits->bitsAllocated >= newCount);
343}
344
345
346/***********************************************************************
347* layout_bitmap_slide
348* Slide the end of a layout bitmap farther from the start.
349* Slides bits [oldPos, bits.bitCount) to [newPos, bits.bitCount+newPos-oldPos)
350* Bits [oldPos, newPos) are zero-filled.
351* The bitmap is expanded and bitCount updated if necessary.
352* newPos >= oldPos.
353**********************************************************************/
354void
355layout_bitmap_slide(layout_bitmap *bits, size_t oldPos, size_t newPos)
356{
357    size_t shift;
358    size_t count;
359
360    if (oldPos == newPos) return;
361    if (oldPos > newPos) _objc_fatal("layout bitmap sliding backwards");
362
363    shift = newPos - oldPos;
364    count = bits->bitCount - oldPos;
365    layout_bitmap_grow(bits, bits->bitCount + shift);
366    move_bits(*bits, oldPos, newPos, count);  // slide
367    clear_bits(*bits, oldPos, shift);         // zero-fill
368}
369
370
371/***********************************************************************
372* layout_bitmap_slide_anywhere
373* Slide the end of a layout bitmap relative to the start.
374* Like layout_bitmap_slide, but can slide backwards too.
375* The end of the bitmap is truncated.
376**********************************************************************/
377void
378layout_bitmap_slide_anywhere(layout_bitmap *bits, size_t oldPos, size_t newPos)
379{
380    size_t shift;
381    size_t count;
382
383    if (oldPos == newPos) return;
384
385    if (oldPos < newPos) {
386        layout_bitmap_slide(bits, oldPos, newPos);
387        return;
388    }
389
390    shift = oldPos - newPos;
391    count = bits->bitCount - oldPos;
392    move_bits(*bits, oldPos, newPos, count);  // slide
393    bits->bitCount -= shift;
394}
395
396
397/***********************************************************************
398* layout_bitmap_splat
399* Pastes the contents of bitmap src to the start of bitmap dst.
400* dst bits between the end of src and oldSrcInstanceSize are zeroed.
401* dst must be at least as long as src.
402* Returns YES if any of dst's bits were changed.
403**********************************************************************/
404BOOL
405layout_bitmap_splat(layout_bitmap dst, layout_bitmap src,
406                    size_t oldSrcInstanceSize)
407{
408    BOOL changed;
409    size_t oldSrcBitCount;
410    size_t bit;
411
412    if (dst.bitCount < src.bitCount) _objc_fatal("layout bitmap too short");
413
414    changed = NO;
415    oldSrcBitCount = oldSrcInstanceSize / sizeof(id);
416
417    // fixme optimize for byte/word at a time
418    for (bit = 0; bit < oldSrcBitCount; bit++) {
419        int dstset = dst.bits[bit/8] & (1 << (bit % 8));
420        int srcset = (bit < src.bitCount)
421            ? src.bits[bit/8] & (1 << (bit % 8))
422            : 0;
423        if (dstset != srcset) {
424            changed = YES;
425            if (srcset) {
426                dst.bits[bit/8] |= 1 << (bit % 8);
427            } else {
428                dst.bits[bit/8] &= ~(1 << (bit % 8));
429            }
430        }
431    }
432
433    return changed;
434}
435
436
437/***********************************************************************
438* layout_bitmap_or
439* Set dst=dst|src.
440* dst must be at least as long as src.
441* Returns YES if any of dst's bits were changed.
442**********************************************************************/
443BOOL
444layout_bitmap_or(layout_bitmap dst, layout_bitmap src, const char *msg)
445{
446    BOOL changed = NO;
447    size_t bit;
448
449    if (dst.bitCount < src.bitCount) {
450        _objc_fatal("layout_bitmap_or: layout bitmap too short%s%s",
451                    msg ? ": " : "", msg ? msg : "");
452    }
453
454    // fixme optimize for byte/word at a time
455    for (bit = 0; bit < src.bitCount; bit++) {
456        int dstset = dst.bits[bit/8] & (1 << (bit % 8));
457        int srcset = src.bits[bit/8] & (1 << (bit % 8));
458        if (srcset  &&  !dstset) {
459            changed = YES;
460            dst.bits[bit/8] |= 1 << (bit % 8);
461        }
462    }
463
464    return changed;
465}
466
467
468/***********************************************************************
469* layout_bitmap_clear
470* Set dst=dst&~src.
471* dst must be at least as long as src.
472* Returns YES if any of dst's bits were changed.
473**********************************************************************/
474BOOL
475layout_bitmap_clear(layout_bitmap dst, layout_bitmap src, const char *msg)
476{
477    BOOL changed = NO;
478    size_t bit;
479
480    if (dst.bitCount < src.bitCount) {
481        _objc_fatal("layout_bitmap_clear: layout bitmap too short%s%s",
482                    msg ? ": " : "", msg ? msg : "");
483    }
484
485    // fixme optimize for byte/word at a time
486    for (bit = 0; bit < src.bitCount; bit++) {
487        int dstset = dst.bits[bit/8] & (1 << (bit % 8));
488        int srcset = src.bits[bit/8] & (1 << (bit % 8));
489        if (srcset  &&  dstset) {
490            changed = YES;
491            dst.bits[bit/8] &= ~(1 << (bit % 8));
492        }
493    }
494
495    return changed;
496}
497
498
499void
500layout_bitmap_print(layout_bitmap bits)
501{
502    size_t i;
503    printf("%zu: ", bits.bitCount);
504    for (i = 0; i < bits.bitCount; i++) {
505        int set = bits.bits[i/8] & (1 << (i % 8));
506        printf("%c", set ? '#' : '.');
507    }
508    printf("\n");
509}
510
511#if 0
512// The code below may be useful when interpreting ivar types more precisely.
513
514/**********************************************************************
515* mark_offset_for_layout
516*
517* Marks the appropriate bit in the bits array cooresponding to a the
518* offset of a reference.  If we are scanning a nested pointer structure
519* then the bits array will be NULL then this function does nothing.
520*
521**********************************************************************/
522static void mark_offset_for_layout(long offset, long bits_size, unsigned char *bits) {
523    // references are ignored if bits is NULL
524    if (bits) {
525        long slot = offset / sizeof(long);
526
527        // determine byte index using (offset / 8 bits per byte)
528        long i_byte = slot >> 3;
529
530        // if the byte index is valid
531        if (i_byte < bits_size) {
532            // set the (offset / 8 bits per byte)th bit
533            bits[i_byte] |= 1 << (slot & 7);
534        } else {
535            // offset not within instance size
536            _objc_inform ("layout - offset exceeds instance size");
537        }
538    }
539}
540
541/**********************************************************************
542* skip_ivar_type_name
543*
544* Skip over the name of a field/class in an ivar type string.  Names
545* are in the form of a double-quoted string.  Returns the remaining
546* string.
547*
548**********************************************************************/
549static char *skip_ivar_type_name(char *type) {
550    // current character
551    char ch;
552
553    // if there is an open quote
554    if (*type == '\"') {
555        // skip quote
556        type++;
557
558        // while no closing quote
559        while ((ch = *type) != '\"') {
560            // if end of string return end of string
561            if (!ch) return type;
562
563            // skip character
564            type++;
565        }
566
567        // skip closing quote
568        type++;
569    }
570
571    // return remaining string
572    return type;
573}
574
575
576/**********************************************************************
577* skip_ivar_struct_name
578*
579* Skip over the name of a struct in an ivar type string.  Names
580* may be followed by an equals sign.  Returns the remaining string.
581*
582**********************************************************************/
583static char *skip_ivar_struct_name(char *type) {
584    // get first character
585    char ch = *type;
586
587    if (ch == _C_UNDEF) {
588        // skip undefined name
589        type++;
590    } else if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || ch == '_') {
591        // if alphabetic
592
593        // scan alphanumerics
594        do {
595            // next character
596            ch = *++type;
597        } while ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || ch == '_' || (ch >= '0' && ch <= '9'));
598    } else {
599        // no struct name present
600        return type;
601    }
602
603    // skip equals sign
604    if (*type == '=') type++;
605
606    return type;
607}
608
609
610/**********************************************************************
611* scan_basic_ivar_type
612*
613* Determines the size and alignment of a basic ivar type.  If the basic
614* type is a possible reference to another garbage collected type the
615* is_reference is set to true (false otherwise.)  Returns the remaining
616* string.
617*
618**********************************************************************/
619static char *scan_ivar_type_for_layout(char *type, long offset, long bits_size, unsigned char *bits, long *next_offset);
620static char *scan_basic_ivar_type(char *type, long *size, long *alignment, BOOL *is_reference) {
621    // assume it is a non-reference type
622    *is_reference = NO;
623
624    // get the first character (advancing string)
625    const char *full_type = type;
626    char ch = *type++;
627
628    // GCC 4 uses for const type*.
629    if (ch == _C_CONST) ch = *type++;
630
631    // act on first character
632    switch (ch) {
633        case _C_ID: {
634            // ID type
635
636            // skip over optional class name
637            type = skip_ivar_type_name(type);
638
639            // size and alignment of an id type
640            *size = sizeof(id);
641            *alignment = __alignof(id);
642
643            // is a reference type
644            *is_reference = YES;
645            break;
646        }
647        case _C_PTR: {
648            // C pointer type
649
650            // skip underlying type
651            long ignored_offset;
652            type = scan_ivar_type_for_layout(type, 0, 0, NULL, &ignored_offset);
653
654            // size and alignment of a generic pointer type
655            *size = sizeof(void *);
656            *alignment = __alignof(void *);
657
658            // is a reference type
659            *is_reference = YES;
660            break;
661        }
662        case _C_CHARPTR: {
663            // C string
664
665           // size and alignment of a char pointer type
666            *size = sizeof(char *);
667            *alignment = __alignof(char *);
668
669            // is a reference type
670            *is_reference = YES;
671            break;
672        }
673        case _C_CLASS:
674        case _C_SEL: {
675            // classes and selectors are ignored for now
676            *size = sizeof(void *);
677            *alignment = __alignof(void *);
678            break;
679        }
680        case _C_CHR:
681        case _C_UCHR: {
682            // char and unsigned char
683            *size = sizeof(char);
684            *alignment = __alignof(char);
685            break;
686        }
687        case _C_SHT:
688        case _C_USHT: {
689            // short and unsigned short
690            *size = sizeof(short);
691            *alignment = __alignof(short);
692            break;
693        }
694        case _C_ATOM:
695        case _C_INT:
696        case _C_UINT: {
697            // int and unsigned int
698            *size = sizeof(int);
699            *alignment = __alignof(int);
700            break;
701        }
702        case _C_LNG:
703        case _C_ULNG: {
704            // long and unsigned long
705            *size = sizeof(long);
706            *alignment = __alignof(long);
707            break;
708        }
709        case _C_LNG_LNG:
710        case _C_ULNG_LNG: {
711            // long long and unsigned long long
712            *size = sizeof(long long);
713            *alignment = __alignof(long long);
714            break;
715        }
716        case _C_VECTOR: {
717            // vector
718            *size = 16;
719            *alignment = 16;
720            break;
721        }
722        case _C_FLT: {
723            // float
724            *size = sizeof(float);
725            *alignment = __alignof(float);
726            break;
727        }
728        case _C_DBL: {
729            // double
730            *size = sizeof(double);
731            *alignment = __alignof(double);
732            break;
733        }
734        case _C_BFLD: {
735            // bit field
736
737            // get number of bits in bit field (advance type string)
738            long lng = strtol(type, &type, 10);
739
740            // while next type is a bit field
741            while (*type == _C_BFLD) {
742                // skip over _C_BFLD
743                type++;
744
745                // get next bit field length
746                long next_lng = strtol(type, &type, 10);
747
748                // if spans next word then align to next word
749                if ((lng & ~31) != ((lng + next_lng) & ~31)) lng = (lng + 31) & ~31;
750
751                // increment running length
752                lng += next_lng;
753
754                // skip over potential field name
755                type = skip_ivar_type_name(type);
756            }
757
758            // determine number of bytes bits represent
759            *size = (lng + 7) / 8;
760
761            // byte alignment
762            *alignment = __alignof(char);
763            break;
764        }
765        case _C_BOOL: {
766            // double
767            *size = sizeof(BOOL);
768            *alignment = __alignof(BOOL);
769            break;
770        }
771        case _C_VOID: {
772            // skip void types
773            *size = 0;
774            *alignment = __alignof(char);
775            break;
776        }
777        case _C_UNDEF: {
778            *size = 0;
779            *alignment = __alignof(char);
780            break;
781        }
782        default: {
783            // unhandled type
784            _objc_fatal("unrecognized character \'%c\' in ivar type: \"%s\"", ch, full_type);
785        }
786    }
787
788    return type;
789}
790
791
792/**********************************************************************
793* scan_ivar_type_for_layout
794*
795* Scan an ivar type string looking for references.  The offset indicates
796* where the ivar begins.  bits is a byte array of size bits_size used to
797* contain the references bit map.  next_offset is the offset beyond the
798* ivar.  Returns the remaining string.
799*
800**********************************************************************/
801static char *scan_ivar_type_for_layout(char *type, long offset, long bits_size, unsigned char *bits, long *next_offset) {
802    long size;                                   // size of a basic type
803    long alignment;                              // alignment of the basic type
804    BOOL is_reference;                      // true if the type indicates a reference to a garbage collected object
805
806    // get the first character
807    char ch = *type;
808
809    // GCC 4 uses for const type*.
810    if (ch == _C_CONST) ch = *++type;
811
812    // act on first character
813    switch (ch) {
814        case _C_ARY_B: {
815            // array type
816
817            // get the array length
818            long lng = strtol(type + 1, &type, 10);
819
820            // next type will be where to advance the type string once the array is processed
821            char *next_type = type;
822
823            // repeat the next type x lng
824            if (!lng) {
825                next_type = scan_ivar_type_for_layout(type, 0, 0, NULL, &offset);
826            } else {
827                while (lng--) {
828                    // repeatedly scan the same type
829                    next_type = scan_ivar_type_for_layout(type, offset, bits_size, bits, &offset);
830                }
831            }
832
833            // advance the type now
834            type = next_type;
835
836            // after the end of the array
837            *next_offset = offset;
838
839            // advance over closing bracket
840            if (*type == _C_ARY_E) type++;
841            else                   _objc_inform("missing \'%c\' in ivar type.", _C_ARY_E);
842
843            break;
844        }
845        case _C_UNION_B: {
846            // union type
847
848            // skip over possible union name
849            type = skip_ivar_struct_name(type + 1);
850
851            // need to accumulate the maximum element offset
852            long max_offset = 0;
853
854            // while not closing paren
855            while ((ch = *type) && ch != _C_UNION_E) {
856                // skip over potential field name
857                type = skip_ivar_type_name(type);
858
859                // scan type
860                long union_offset;
861                type = scan_ivar_type_for_layout(type, offset, bits_size, bits, &union_offset);
862
863                // adjust the maximum element offset
864                if (max_offset < union_offset) max_offset = union_offset;
865            }
866
867            // after the largest element
868            *next_offset = max_offset;
869
870            // advance over closing paren
871            if (ch == _C_UNION_E) {
872              type++;
873            } else {
874              _objc_inform("missing \'%c\' in ivar type", _C_UNION_E);
875            }
876
877            break;
878        }
879        case _C_STRUCT_B: {
880            // struct type
881
882            // skip over possible struct name
883            type = skip_ivar_struct_name(type + 1);
884
885            // while not closing brace
886            while ((ch = *type) && ch != _C_STRUCT_E) {
887                // skip over potential field name
888                type = skip_ivar_type_name(type);
889
890                // scan type
891                type = scan_ivar_type_for_layout(type, offset, bits_size, bits, &offset);
892            }
893
894            // after the end of the struct
895            *next_offset = offset;
896
897            // advance over closing brace
898            if (ch == _C_STRUCT_E) type++;
899            else                   _objc_inform("missing \'%c\' in ivar type", _C_STRUCT_E);
900
901            break;
902        }
903        default: {
904            // basic type
905
906            // scan type
907            type = scan_basic_ivar_type(type, &size, &alignment, &is_reference);
908
909            // create alignment mask
910            alignment--;
911
912            // align offset
913            offset = (offset + alignment) & ~alignment;
914
915            // if is a reference then mark in the bit map
916            if (is_reference) mark_offset_for_layout(offset, bits_size, bits);
917
918            // after the basic type
919            *next_offset = offset + size;
920            break;
921        }
922    }
923
924    // return remainder of type string
925    return type;
926}
927
928#endif
929