Add the 3.3.3 sources for class-dump.

class-dump/src/CDStructureTable.m

+// -*- mode: ObjC -*-
+
+//  This file is part of class-dump, a utility for examining the Objective-C segment of Mach-O files.
+//  Copyright (C) 1997-1998, 2000-2001, 2004-2010 Steve Nygard.
+
+#import "CDStructureTable.h"
+
+#import "NSArray-Extensions.h"
+#import "NSError-CDExtensions.h"
+#import "NSString-Extensions.h"
+#import "CDClassDump.h"
+#import "CDSymbolReferences.h"
+#import "CDType.h"
+#import "CDTypeController.h"
+#import "CDTypeFormatter.h"
+#import "CDTypeName.h"
+#import "CDStructureInfo.h"
+
+// Phase 0 - This is driven by CDClassDump, registering types from all of the classes, categories, and protocols.
+//         - This collects all the top level types (or struct/unions?), keeps a reference count, and flags any that were used in a method.
+//         - If a top level struct was used in a method, then the type MUST be declared at the top.
+//         - At the end of phase 0, these types are recursively visited, renaming structs whose name starts with $ (like $_12345) to ?, so
+//           that we'll treat them as anonymous structures.
+//            - Those names must be generated by the compiler.  It can end up with different numbers for the same type.
+
+// Phase 1 - This goes through all the types collected in phase 0, and recursively registers each structure and union with the type controller.
+//         - We are not concerned about reference counts or the isUsedInMethod flags.
+//         - Since structures and unions can be nested in each other, we need to process each table before doing the end-of-phase work.
+//         - We record the maximum structure depth.
+//           - Since the deepest union may be buriend in a structure instead of referenced at the top level, we can't calculate the max depth from phase 0.
+//           - On the other hand, since we're only interested in the max combined depth of structures and unions, the end result would be the same.
+//         - The result of phase 1 is phase1_groupedByDepth: a dictionary keyed by the structure depth, containing arrays of CDStructureInfo.
+
+// Phase 2 - This is driven by CDTypeController.
+//         - The goal of phase 2 is to gather member names and types (@"NSObject" vs just @).
+//         - It goes through all of the phase1 groups, shallowest to deepest.
+//         - For each level group:
+//           - First it merges the results of all previous groups with the types at this depth.
+//           - Then we group the CDStructureInfos, named structures by name, anon structures by reallyBareTypeString
+//             - If they could be combined, the combined CDStructureInfo is to phase2_namedStructureInfo or phase2_anonStructureInfo.
+//             - If they couldn't be combined, the uncombined CDStructureInfos are added to phase2_nameExceptions or phase2_anonExceptions.
+
+// Phase 3 - Using all of the information available from the merged types from phase 2, we merge these types with the types from phase 0
+//           to fill in missing member names, and the occasional object type.
+
+// After all the phases are done, typedef names are generated for all anonymous structures, and then field names are added for missing fields.
+//  - bitfields don't need to have a name, so they can be blank.
+//  - the typedef name is calculated from a hash of the typeString.
+//    - Doing it before adding missing fields means we could change the field names without changing the typedef name.
+//    - Makes the name independant of the order they were encountered (like the previous indexes were).  You can get meaningful diffs between
+//      framework changes now.
+
+static BOOL debug = NO;
+static BOOL debugNamedStructures = NO;
+static BOOL debugAnonStructures = NO;
+
+@implementation CDStructureTable
+
+- (id)init;
+{
+    if ([super init] == nil)
+        return nil;
+
+    identifier = nil;
+    anonymousBaseName = nil;
+
+    phase0_structureInfo = [[NSMutableDictionary alloc] init];
+
+    phase1_structureInfo = [[NSMutableDictionary alloc] init];
+    phase1_maxDepth = 0;
+    phase1_groupedByDepth = [[NSMutableDictionary alloc] init];
+
+    phase2_namedStructureInfo = [[NSMutableDictionary alloc] init];
+    phase2_anonStructureInfo = [[NSMutableDictionary alloc] init];
+    phase2_nameExceptions = [[NSMutableArray alloc] init];
+    phase2_anonExceptions = [[NSMutableArray alloc] init];
+
+    phase3_namedStructureInfo = [[NSMutableDictionary alloc] init];
+    phase3_anonStructureInfo = [[NSMutableDictionary alloc] init];
+    phase3_nameExceptions = [[NSMutableDictionary alloc] init];
+    phase3_anonExceptions = [[NSMutableDictionary alloc] init];
+
+    phase3_exceptionalNames = [[NSMutableSet alloc] init];
+    phase3_inMethodNameExceptions = [[NSMutableSet alloc] init];
+
+    flags.shouldDebug = NO;
+
+    debugNames = [[NSMutableSet alloc] init];
+    debugAnon = [[NSMutableSet alloc] init];
+
+    return self;
+}
+
+- (void)dealloc;
+{
+    [identifier release];
+    [anonymousBaseName release];
+
+    [phase0_structureInfo release];
+
+    [phase1_structureInfo release];
+    [phase1_groupedByDepth release];
+
+    [phase2_namedStructureInfo release];
+    [phase2_anonStructureInfo release];
+    [phase2_nameExceptions release];
+    [phase2_anonExceptions release];
+
+    [phase3_namedStructureInfo release];
+    [phase3_anonStructureInfo release];
+    [phase3_nameExceptions release];
+    [phase3_anonExceptions release];
+
+    [phase3_exceptionalNames release];
+    [phase3_inMethodNameExceptions release];
+
+    [debugNames release];
+    [debugAnon release];
+
+    [super dealloc];
+}
+
+- (NSString *)identifier;
+{
+    return identifier;
+}
+
+- (void)setIdentifier:(NSString *)newIdentifier;
+{
+    if (newIdentifier == identifier)
+        return;
+
+    [identifier release];
+    identifier = [newIdentifier retain];
+}
+
+- (NSString *)anonymousBaseName;
+{
+    return anonymousBaseName;
+}
+
+- (void)setAnonymousBaseName:(NSString *)newName;
+{
+    if (newName == anonymousBaseName)
+        return;
+
+    [anonymousBaseName release];
+    anonymousBaseName = [newName retain];
+}
+
+- (BOOL)shouldDebug;
+{
+    return flags.shouldDebug;
+}
+
+- (void)setShouldDebug:(BOOL)newFlag;
+{
+    flags.shouldDebug = newFlag;
+}
+
+//
+// Phase 0
+//
+
+- (void)phase0RegisterStructure:(CDType *)aStructure usedInMethod:(BOOL)isUsedInMethod;
+{
+    NSString *key;
+    CDStructureInfo *info;
+
+    key = [aStructure typeString];
+    info = [phase0_structureInfo objectForKey:key];
+    if (info == nil) {
+        info = [[CDStructureInfo alloc] initWithType:aStructure];
+        if (isUsedInMethod)
+            [info setIsUsedInMethod:YES];
+        [phase0_structureInfo setObject:info forKey:key];
+        [info release];
+    } else {
+        [info addReferenceCount:1];
+        if (isUsedInMethod)
+            [info setIsUsedInMethod:YES];
+    }
+}
+
+- (void)finishPhase0;
+{
+    if (debug) NSLog(@"[%@] %s, changing struct names that start with $", identifier, _cmd);
+    for (CDStructureInfo *info in [phase0_structureInfo allValues]) {
+        [[info type] phase0RecursivelyFixStructureNames:debug];
+    }
+
+    if ([debugNames count] > 0) {
+        NSLog(@"======================================================================");
+        NSLog(@"[%@] %s", identifier, _cmd);
+        NSLog(@"debug names: %@", [[debugNames allObjects] componentsJoinedByString:@", "]);
+        for (CDStructureInfo *info in [[phase0_structureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
+            if ([debugNames containsObject:[[[info type] typeName] description]])
+                NSLog(@"%@", [info shortDescription]);
+        }
+        NSLog(@"======================================================================");
+    }
+
+    if ([debugAnon count] > 0) {
+        NSLog(@"======================================================================");
+        NSLog(@"[%@] %s", identifier, _cmd);
+        NSLog(@"debug anon: %@", [[debugAnon allObjects] componentsJoinedByString:@", "]);
+        for (CDStructureInfo *info in [[phase0_structureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
+            if ([debugAnon containsObject:[[info type] reallyBareTypeString]])
+                NSLog(@"%@", [info shortDescription]);
+        }
+        NSLog(@"======================================================================");
+    }
+}
+
+- (void)logPhase0Info;
+{
+    NSLog(@"======================================================================");
+    NSLog(@"[%@] %s", identifier, _cmd);
+    for (CDStructureInfo *info in [[phase0_structureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
+        NSLog(@"%@", [info shortDescription]);
+    }
+    NSLog(@"======================================================================");
+}
+
+//
+// Phase 1
+//
+
+- (void)phase1WithTypeController:(CDTypeController *)typeController;
+{
+    for (CDStructureInfo *info in [phase0_structureInfo allValues]) {
+        [[info type] phase1RegisterStructuresWithObject:typeController];
+    }
+}
+
+// Need to gather all of the structures, since some substructures may have member names we'd otherwise miss.
+- (void)phase1RegisterStructure:(CDType *)aStructure;
+{
+    NSString *key;
+    CDStructureInfo *info;
+
+    key = [aStructure typeString];
+    info = [phase1_structureInfo objectForKey:key];
+    if (info == nil) {
+        info = [[CDStructureInfo alloc] initWithType:aStructure];
+        [phase1_structureInfo setObject:info forKey:key];
+        [info release];
+    }
+}
+
+// Need to merge names bottom-up to catch cases like: {?=@@iiffff{_NSRect={_NSPoint=ff}{_NSSize=ff}}{?=b1b1b1b1b1b27}}
+
+- (void)finishPhase1;
+{
+    if (debug) {
+        NSLog(@"======================================================================");
+        NSLog(@"[%@] %s", identifier, _cmd);
+    }
+
+    // The deepest union may not be at the top level (buried in a structure instead), so need to get the depth here.
+    // But we'll take the max of structure and union depths in the CDTypeController anyway.
+
+    for (CDStructureInfo *info in [phase1_structureInfo allValues]) {
+        NSUInteger depth;
+
+        depth = [[info type] structureDepth];
+        if (phase1_maxDepth < depth)
+            phase1_maxDepth = depth;
+    }
+    if (debug) NSLog(@"[%@] Maximum structure depth is: %u", identifier, phase1_maxDepth);
+
+    for (CDStructureInfo *info in [phase1_structureInfo allValues]) {
+        NSNumber *key;
+        NSMutableArray *group;
+
+        key = [NSNumber numberWithUnsignedInteger:[[info type] structureDepth]];
+        group = [phase1_groupedByDepth objectForKey:key];
+        if (group == nil) {
+            group = [[NSMutableArray alloc] init];
+            [group addObject:info];
+            [phase1_groupedByDepth setObject:group forKey:key];
+            [group release];
+        } else {
+            [group addObject:info];
+        }
+    }
+
+    if (debug) NSLog(@"depth groups: %@", [[phase1_groupedByDepth allKeys] sortedArrayUsingSelector:@selector(compare:)]);
+}
+
+- (NSUInteger)phase1_maxDepth;
+{
+    return phase1_maxDepth;
+}
+
+//
+// Phase 2
+//
+
+// From lowest to highest depths:
+// - Go through all infos at that level
+//   - recursively (bottom up) try to merge substructures into that type, to get names/full types
+// - merge all mergeable infos at that level
+
+- (void)phase2AtDepth:(NSUInteger)depth typeController:(CDTypeController *)typeController;
+{
+    NSNumber *depthKey;
+    NSArray *infos;
+    NSMutableDictionary *nameDict, *anonDict;
+
+    //NSLog(@"[%@] %s, depth: %u", identifier, _cmd, depth);
+    depthKey = [NSNumber numberWithUnsignedInt:depth];
+    infos = [phase1_groupedByDepth objectForKey:depthKey];
+
+    for (CDStructureInfo *info in infos) {
+        // recursively (bottom up) try to merge substructures into that type, to get names/full types
+        //NSLog(@"----------------------------------------");
+        //NSLog(@"Trying phase2Merge with on %@", [[info type] typeString]);
+        [[info type] phase2MergeWithTypeController:typeController debug:debug];
+    }
+
+    // merge all mergeable infos at that level
+    nameDict = [NSMutableDictionary dictionary];
+    anonDict = [NSMutableDictionary dictionary];
+
+    // Group named structures by name.
+    // Group anon structures by reallyBareTypeString.
+    for (CDStructureInfo *info in infos) {
+        NSString *name;
+        NSMutableArray *group;
+
+        name = [[[info type] typeName] description];
+
+        if ([@"?" isEqualToString:name]) {
+            NSString *key;
+
+            key = [[info type] reallyBareTypeString];
+            group = [anonDict objectForKey:key];
+            if (group == nil) {
+                group = [[NSMutableArray alloc] init];
+                [group addObject:info];
+                [anonDict setObject:group forKey:key];
+                [group release];
+            } else {
+                [group addObject:info];
+            }
+        } else {
+            group = [nameDict objectForKey:name];
+            if (group == nil) {
+                group = [[NSMutableArray alloc] init];
+                [group addObject:info];
+                [nameDict setObject:group forKey:name];
+                [group release];
+            } else {
+                [group addObject:info];
+            }
+        }
+    }
+
+    // Now... for each group, make sure we can combine them all together.
+    // If not, this means that either the types or the member names conflicted, and we save the entire group as an exception.
+    for (NSString *key in [nameDict allKeys]) {
+        NSMutableArray *group;
+        CDStructureInfo *combined = nil;
+        BOOL canBeCombined = YES;
+
+        //NSLog(@"key... %@", key);
+        group = [nameDict objectForKey:key];
+        for (CDStructureInfo *info in group) {
+            if (combined == nil) {
+                combined = [info copy];
+            } else {
+                //NSLog(@"old: %@", [[combined type] typeString]);
+                //NSLog(@"new: %@", [[info type] typeString]);
+                if ([[combined type] canMergeWithType:[info type]]) {
+                    [[combined type] mergeWithType:[info type]];
+                    [combined addReferenceCount:[info referenceCount]];
+#if 0
+                    if ([info isUsedInMethod])
+                        [combined setIsUsedInMethod:YES];
+#endif
+                } else {
+                    canBeCombined = NO;
+                    break;
+                }
+            }
+        }
+
+        if (canBeCombined) {
+            CDStructureInfo *previousInfo;
+
+            previousInfo = [phase2_namedStructureInfo objectForKey:key];
+            if (previousInfo != nil) {
+                // struct _Vector_impl in HALLab.
+                [phase2_nameExceptions addObject:previousInfo];
+                //[phase2_nameExceptions addObjectsFromArray:group]; // Or just add the combined?
+                [phase2_nameExceptions addObject:combined];
+                [phase2_namedStructureInfo removeObjectForKey:key];
+                if (debugNamedStructures) {
+                    NSLog(@"[%@] %s, WARNING: depth %u name %@ has conflict(?) at lower level", identifier, _cmd, depth, key);
+                    NSLog(@"previous: %@", [[phase2_namedStructureInfo objectForKey:key] shortDescription]);
+                    NSLog(@" current: %@", [combined shortDescription]);
+                }
+            } else {
+                [phase2_namedStructureInfo setObject:combined forKey:key];
+            }
+        } else {
+            if (debugNamedStructures) {
+                NSLog(@"----------------------------------------");
+                NSLog(@"Can't be combined: %@", key);
+                NSLog(@"group: %@", group);
+            }
+            [phase2_nameExceptions addObjectsFromArray:group];
+        }
+
+        [combined release];
+    }
+
+    //NSLog(@"======================================================================");
+    for (NSString *key in [anonDict allKeys]) {
+        NSMutableArray *group;
+        CDStructureInfo *combined = nil;
+        BOOL canBeCombined = YES;
+
+        //NSLog(@"key... %@", key);
+        group = [anonDict objectForKey:key];
+        for (CDStructureInfo *info in group) {
+            if (combined == nil) {
+                combined = [info copy];
+                //NSLog(@"info: %@", [info shortDescription]);
+                //NSLog(@"combined: %@", [combined shortDescription]);
+            } else {
+                //NSLog(@"old: %@", [combined shortDescription]);
+                //NSLog(@"new: %@", [info shortDescription]);
+                if ([[combined type] canMergeWithType:[info type]]) {
+                    [[combined type] mergeWithType:[info type]];
+                    [combined addReferenceCount:[info referenceCount]];
+#if 0
+                    if ([info isUsedInMethod])
+                        [combined setIsUsedInMethod:YES];
+#endif
+                } else {
+                    if (debugAnonStructures) {
+                        NSLog(@"previous: %@", [[combined type] typeString]);
+                        NSLog(@"    This: %@", [[info type] typeString]);
+                    }
+                    canBeCombined = NO;
+                    break;
+                }
+            }
+        }
+
+        if (canBeCombined) {
+            if ([phase2_anonStructureInfo objectForKey:key] != nil) {
+                // This shouldn't happen, but the named case might.
+                NSLog(@"[%@] %s, WARNING: depth %u type %@ has conflict(?) at lower level", identifier, _cmd, depth, key);
+                NSLog(@"previous: %@", [[phase2_anonStructureInfo objectForKey:key] shortDescription]);
+                NSLog(@" current: %@", [combined shortDescription]);
+            }
+            [phase2_anonStructureInfo setObject:combined forKey:key];
+        } else {
+            if (debugAnonStructures) {
+                NSLog(@"----------------------------------------");
+                NSLog(@"Can't be combined: %@", key);
+                NSLog(@"group: %@", group);
+            }
+            [phase2_anonExceptions addObjectsFromArray:group];
+        }
+
+        [combined release];
+    }
+}
+
+- (CDType *)phase2ReplacementForType:(CDType *)type;
+{
+    NSString *name;
+
+    name = [[type typeName] description];
+    if ([@"?" isEqualToString:name]) {
+        return [(CDStructureInfo *)[phase2_anonStructureInfo objectForKey:[type reallyBareTypeString]] type];
+    } else {
+        return [(CDStructureInfo *)[phase2_namedStructureInfo objectForKey:name] type];
+    }
+
+    return nil;
+}
+
+- (void)finishPhase2;
+{
+    if ([debugNames count] > 0) {
+        NSLog(@"======================================================================");
+        NSLog(@"[%@] %s", identifier, _cmd);
+        NSLog(@"debug names: %@", [[debugNames allObjects] componentsJoinedByString:@", "]);
+        for (CDStructureInfo *info in [[phase2_namedStructureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
+            if ([debugNames containsObject:[[[info type] typeName] description]])
+                NSLog(@"%@", [info shortDescription]);
+        }
+        NSLog(@"======================================================================");
+    }
+
+    if ([debugAnon count] > 0) {
+        NSLog(@"======================================================================");
+        NSLog(@"[%@] %s", identifier, _cmd);
+        NSLog(@"debug anon: %@", [[debugAnon allObjects] componentsJoinedByString:@", "]);
+        for (CDStructureInfo *info in [[phase2_anonStructureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
+            if ([debugAnon containsObject:[[info type] reallyBareTypeString]])
+                NSLog(@"%@", [info shortDescription]);
+        }
+        NSLog(@"======================================================================");
+    }
+
+    //[self logPhase2Info];
+}
+
+- (void)logPhase2Info;
+{
+#if 0
+    NSLog(@"======================================================================");
+    NSLog(@"[%@] %s, named:", identifier, _cmd);
+    for (CDStructureInfo *info in [[phase2_namedStructureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
+        NSLog(@"%@", [info shortDescription]);
+    }
+#endif
+#if 0
+    NSLog(@"======================================================================");
+    NSLog(@"[%@] %s, anon:", identifier, _cmd);
+    for (CDStructureInfo *info in [[phase2_anonStructureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
+        NSLog(@"%@", [info shortDescription]);
+    }
+#endif
+#if 1
+    NSLog(@"======================================================================");
+    NSLog(@"[%@] %s, named exceptions:", identifier, _cmd);
+    for (CDStructureInfo *info in [phase2_nameExceptions sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
+        NSLog(@"%@", [info shortDescription]);
+    }
+#endif
+#if 0
+    NSLog(@"======================================================================");
+    NSLog(@"[%@] %s, anon exceptions:", identifier, _cmd);
+    for (CDStructureInfo *info in [phase2_anonExceptions sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
+        NSLog(@"%@", [info shortDescription]);
+    }
+#endif
+}
+
+//
+// Phase 3
+//
+
+- (void)phase2ReplacementOnPhase0WithTypeController:(CDTypeController *)typeController;
+{
+    if (debug) {
+        NSLog(@"======================================================================");
+        NSLog(@"[%@]  > %s", identifier, _cmd);
+    }
+
+    for (CDStructureInfo *info in [phase0_structureInfo allValues]) {
+        [[info type] phase2MergeWithTypeController:typeController debug:debug];
+    }
+
+    if (debug) NSLog(@"[%@] <  %s", identifier, _cmd);
+}
+
+// Go through all updated phase0_structureInfo types
+// - start merging these into a new table
+//   - If this is the first time a structure has been added:
+//     - add one reference for each subtype
+//   - otherwise just merge them.
+// - end result should be CDStructureInfos with counts and method reference flags
+
+- (void)buildPhase3Exceptions;
+{
+    for (CDStructureInfo *info in phase2_nameExceptions) {
+        CDStructureInfo *newInfo;
+
+        newInfo = [info copy];
+        [newInfo setReferenceCount:0];
+        [newInfo setIsUsedInMethod:NO];
+        [phase3_nameExceptions setObject:newInfo forKey:[[newInfo type] typeString]];
+        [phase3_exceptionalNames addObject:[newInfo name]];
+        [newInfo release];
+    }
+
+    for (CDStructureInfo *info in phase2_anonExceptions) {
+        CDStructureInfo *newInfo;
+
+        newInfo = [info copy];
+        [newInfo setReferenceCount:0];
+        [newInfo setIsUsedInMethod:NO];
+        [phase3_anonExceptions setObject:newInfo forKey:[[newInfo type] typeString]];
+        [newInfo release];
+    }
+
+    //NSLog(@"phase3 name exceptions: %@", [[phase3_nameExceptions allKeys] componentsJoinedByString:@", "]);
+    //NSLog(@"phase3 anon exceptions: %@", [[phase3_anonExceptions allKeys] componentsJoinedByString:@"\n"]);
+    //exit(99);
+}
+
+- (void)phase3WithTypeController:(CDTypeController *)typeController;
+{
+    //NSLog(@"[%@]  > %s", identifier, _cmd);
+
+    for (CDStructureInfo *info in [[phase0_structureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
+        [self phase3RegisterStructure:[info type] count:[info referenceCount] usedInMethod:[info isUsedInMethod] typeController:typeController];
+    }
+
+    //NSLog(@"[%@] <  %s", identifier, _cmd);
+}
+
+- (void)phase3RegisterStructure:(CDType *)aStructure
+                          count:(NSUInteger)referenceCount
+                   usedInMethod:(BOOL)isUsedInMethod
+                 typeController:(CDTypeController *)typeController;
+{
+    NSString *name;
+
+    //NSLog(@"[%@]  > %s", identifier, _cmd);
+
+    name = [[aStructure typeName] description];
+    if ([@"?" isEqualToString:name]) {
+        NSString *key;
+        CDStructureInfo *info;
+
+        key = [aStructure reallyBareTypeString];
+        //NSLog(@"key: %@, isUsedInMethod: %u", key, isUsedInMethod);
+        info = [phase3_anonExceptions objectForKey:[aStructure typeString]];
+        if (info != nil) {
+            if (debugAnonStructures) NSLog(@"%s, anon key %@ has exception from phase 2", _cmd, [aStructure typeString]);
+            [info addReferenceCount:referenceCount];
+            if (isUsedInMethod)
+                [info setIsUsedInMethod:isUsedInMethod];
+
+            if ([info referenceCount] == referenceCount) { // i.e. the first time we've encounter this struct
+                // And then... add 1 reference for each substructure, stopping recursion when we've encountered a previous structure
+                [aStructure phase3RegisterMembersWithTypeController:typeController];
+            }
+        } else {
+            info = [phase3_anonStructureInfo objectForKey:key];
+            if (info == nil) {
+                info = [[CDStructureInfo alloc] initWithType:aStructure];
+                [info setReferenceCount:referenceCount];
+                if (isUsedInMethod)
+                    [info setIsUsedInMethod:isUsedInMethod];
+                [phase3_anonStructureInfo setObject:info forKey:key];
+                [info release];
+
+                // And then... add 1 reference for each substructure, stopping recursion when we've encountered a previous structure
+                [aStructure phase3RegisterMembersWithTypeController:typeController];
+            } else {
+                [info addReferenceCount:referenceCount];
+                if (isUsedInMethod)
+                    [info setIsUsedInMethod:isUsedInMethod];
+            }
+        }
+    } else {
+        CDStructureInfo *info;
+
+        if ([debugNames containsObject:name]) NSLog(@"[%@] %s, type= %@", identifier, _cmd, [aStructure typeString]);
+        //NSLog(@"[%@] %s, name: %@", identifier, _cmd, name);
+        if ([phase3_exceptionalNames containsObject:name]) {
+            if (debugNamedStructures) NSLog(@"%s, name %@ has exception from phase 2", _cmd, name);
+            info = [phase3_nameExceptions objectForKey:[aStructure typeString]];
+            // Info can be nil.  For example, from {_CommandStackEntry}
+            if (info != nil) {
+                [info addReferenceCount:referenceCount];
+                if (isUsedInMethod)
+                    [phase3_inMethodNameExceptions addObject:name];
+
+                if ([info referenceCount] == referenceCount) { // i.e. the first time we've encounter this struct
+                    // And then... add 1 reference for each substructure, stopping recursion when we've encountered a previous structure
+                    [aStructure phase3RegisterMembersWithTypeController:typeController];
+                }
+            }
+        } else {
+            info = [phase3_namedStructureInfo objectForKey:name];
+            if (info == nil) {
+                if ([debugNames containsObject:name]) NSLog(@"[%@] %s, info was nil for %@", identifier, _cmd, name);
+                info = [[CDStructureInfo alloc] initWithType:aStructure];
+                [info setReferenceCount:referenceCount];
+                if (isUsedInMethod)
+                    [info setIsUsedInMethod:isUsedInMethod];
+                [phase3_namedStructureInfo setObject:info forKey:name];
+                [info release];
+
+                // And then... add 1 reference for each substructure, stopping recursion when we've encountered a previous structure
+                [aStructure phase3RegisterMembersWithTypeController:typeController];
+            } else {
+                if ([debugNames containsObject:name]) NSLog(@"[%@] %s, info before: %@", identifier, _cmd, [info shortDescription]);
+                // Handle the case where {foo} occurs before {foo=iii}
+                if ([[[info type] members] count] == 0) {
+                    [[info type] mergeWithType:aStructure];
+
+                    // And then... add 1 reference for each substructure, stopping recursion when we've encountered a previous structure
+                    [aStructure phase3RegisterMembersWithTypeController:typeController];
+                }
+                [info addReferenceCount:referenceCount];
+                if (isUsedInMethod)
+                    [info setIsUsedInMethod:isUsedInMethod];
+                if ([debugNames containsObject:name]) {
+                    NSLog(@"[%@] %s, added ref count: %u, isUsedInMethod: %u", identifier, _cmd, referenceCount, isUsedInMethod);
+                    NSLog(@"[%@] %s, info after: %@", identifier, _cmd, [info shortDescription]);
+                }
+            }
+        }
+    }
+
+    //NSLog(@"[%@] <  %s", identifier, _cmd);
+}
+
+- (void)finishPhase3;
+{
+    if ([debugNames count] > 0) {
+        NSLog(@"======================================================================");
+        NSLog(@"[%@] %s", identifier, _cmd);
+        NSLog(@"names: %@", [[debugNames allObjects] componentsJoinedByString:@", "]);
+        for (CDStructureInfo *info in [[phase3_namedStructureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
+            if ([debugNames containsObject:[[[info type] typeName] description]])
+                NSLog(@"%@", [info shortDescription]);
+        }
+        for (CDStructureInfo *info in [phase3_nameExceptions allValues]) {
+            if ([debugNames containsObject:[info name]])
+                NSLog(@"%@ is in the name exceptions", [info name]);
+        }
+        NSLog(@"======================================================================");
+    }
+
+    if ([debugAnon count] > 0) {
+        NSLog(@"======================================================================");
+        NSLog(@"[%@] %s", identifier, _cmd);
+        NSLog(@"debug anon: %@", [[debugAnon allObjects] componentsJoinedByString:@", "]);
+        for (CDStructureInfo *info in [[phase3_anonStructureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
+            if ([debugAnon containsObject:[[info type] reallyBareTypeString]])
+                NSLog(@"%@", [info shortDescription]);
+        }
+        for (NSString *str in debugAnon)
+            if ([phase3_anonExceptions objectForKey:str] != nil)
+                NSLog(@"%@ is in the anon exceptions", str);
+        NSLog(@"======================================================================");
+    }
+
+    //[self logPhase3Info];
+}
+
+- (void)logPhase3Info;
+{
+    NSLog(@"[%@]  > %s", identifier, _cmd);
+#if 0
+    NSLog(@"----------------------------------------------------------------------");
+    NSLog(@"named:");
+    for (NSString *name in [[phase3_namedStructureInfo allKeys] sortedArrayUsingSelector:@selector(compare:)]) {
+        CDStructureInfo *info;
+
+        info = [phase3_namedStructureInfo objectForKey:name];
+        NSLog(@"%@", [info shortDescription]);
+    }
+
+    NSLog(@"----------------------------------------------------------------------");
+    NSLog(@"anon:");
+    for (CDStructureInfo *info in [[phase3_anonStructureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
+        NSLog(@"%@", [info shortDescription]);
+    }
+#endif
+    NSLog(@"======================================================================");
+    NSLog(@"[%@] %s, anon exceptions:", identifier, _cmd);
+    for (CDStructureInfo *info in [[phase3_anonExceptions allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
+        NSLog(@"%@", [info shortDescription]);
+    }
+
+    NSLog(@"[%@] <  %s", identifier, _cmd);
+}
+
+- (CDType *)phase3ReplacementForType:(CDType *)type;
+{
+    NSString *name;
+
+    name = [[type typeName] description];
+    if ([@"?" isEqualToString:name]) {
+        return [(CDStructureInfo *)[phase3_anonStructureInfo objectForKey:[type reallyBareTypeString]] type];
+    } else {
+        return [(CDStructureInfo *)[phase3_namedStructureInfo objectForKey:name] type];
+    }
+
+    return nil;
+}
+
+//
+// Other
+//
+
+// TODO (2003-12-23): Add option to show/hide this section
+// TODO (2003-12-23): sort by name or by dependency
+// TODO (2003-12-23): declare in modules where they were first used
+
+- (void)appendNamedStructuresToString:(NSMutableString *)resultString
+                            formatter:(CDTypeFormatter *)aTypeFormatter
+                     symbolReferences:(CDSymbolReferences *)symbolReferences
+                             markName:(NSString *)markName;
+{
+    BOOL hasAddedMark = NO;
+    BOOL hasShownExceptions = NO;
+
+    for (NSString *key in [[phase3_namedStructureInfo allKeys] sortedArrayUsingSelector:@selector(compare:)]) {
+        CDStructureInfo *info;
+        BOOL shouldShow;
+
+        info = [phase3_namedStructureInfo objectForKey:key];
+        shouldShow = ![self shouldExpandStructureInfo:info];
+        if (shouldShow || debugNamedStructures) {
+            CDType *type;
+
+            if (hasAddedMark == NO) {
+                [resultString appendFormat:@"#pragma mark %@\n\n", markName];
+                hasAddedMark = YES;
+            }
+
+            type = [info type];
+            if ([[aTypeFormatter typeController] shouldShowName:[[type typeName] description]]) {
+                NSString *formattedString;
+
+                if (debugNamedStructures) {
+                    [resultString appendFormat:@"// would normally show? %u\n", shouldShow];
+                    [resultString appendFormat:@"// depth: %u, ref count: %u, used in method? %u\n", [[info type] structureDepth], [info referenceCount], [info isUsedInMethod]];
+                }
+                formattedString = [aTypeFormatter formatVariable:nil parsedType:type symbolReferences:symbolReferences];
+                if (formattedString != nil) {
+                    [resultString appendString:formattedString];
+                    [resultString appendString:@";\n\n"];
+                }
+            }
+        }
+    }
+
+    for (CDStructureInfo *info in [[phase3_nameExceptions allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
+        BOOL shouldShow;
+
+        shouldShow = ![self shouldExpandStructureInfo:info];
+        if (shouldShow || debugNamedStructures) {
+            CDType *type;
+
+            if (hasAddedMark == NO) {
+                [resultString appendFormat:@"#pragma mark %@\n\n", markName];
+                hasAddedMark = YES;
+            }
+
+            if (hasShownExceptions == NO) {
+                [resultString appendString:@"#if 0\n"];
+                [resultString appendString:@"// Names with conflicting types:\n"];
+                hasShownExceptions = YES;
+            }
+
+            type = [info type];
+            if ([[aTypeFormatter typeController] shouldShowName:[[type typeName] description]]) {
+                NSString *formattedString;
+
+                if (debugNamedStructures) {
+                    [resultString appendFormat:@"// depth: %u, ref count: %u, used in method? %u\n", [[info type] structureDepth], [info referenceCount], [info isUsedInMethod]];
+                    //[resultString appendFormat:@"// typedefName: %@\n", [info typedefName]];
+                }
+                formattedString = [aTypeFormatter formatVariable:nil parsedType:type symbolReferences:symbolReferences];
+                if (formattedString != nil) {
+                    [resultString appendFormat:@"typedef %@ %@;\n\n", formattedString, [info typedefName]];
+                }
+            }
+        }
+    }
+    if (hasShownExceptions)
+        [resultString appendString:@"#endif\n\n"];
+
+    if (debugNamedStructures) {
+        [resultString appendString:@"\n// Name exceptions:\n"];
+        for (CDStructureInfo *info in [[phase3_nameExceptions allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)])
+            [resultString appendFormat:@"// %@\n", [info shortDescription]];
+        [resultString appendString:@"\n"];
+    }
+}
+
+- (void)appendTypedefsToString:(NSMutableString *)resultString
+                     formatter:(CDTypeFormatter *)aTypeFormatter
+              symbolReferences:(CDSymbolReferences *)symbolReferences
+                      markName:(NSString *)markName;
+{
+    BOOL hasAddedMark = NO;
+    BOOL hasShownExceptions = NO;
+
+    for (CDStructureInfo *info in [[phase3_anonStructureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
+        BOOL shouldShow;
+
+        shouldShow = ![self shouldExpandStructureInfo:info];
+        if (shouldShow || debugAnonStructures) {
+            NSString *formattedString;
+
+            if (hasAddedMark == NO) {
+                [resultString appendFormat:@"#pragma mark %@\n\n", markName];
+                hasAddedMark = YES;
+            }
+
+            if (debugAnonStructures) {
+                [resultString appendFormat:@"// would normally show? %u\n", shouldShow];
+                [resultString appendFormat:@"// %@\n", [[info type] reallyBareTypeString]];
+                [resultString appendFormat:@"// depth: %u, ref: %u, used in method? %u\n", [[info type] structureDepth], [info referenceCount], [info isUsedInMethod]];
+            }
+            formattedString = [aTypeFormatter formatVariable:nil parsedType:[info type] symbolReferences:symbolReferences];
+            if (formattedString != nil) {
+                [resultString appendFormat:@"typedef %@ %@;\n\n", formattedString, [info typedefName]];
+            }
+        }
+    }
+
+    // TODO (2009-08-25): Need same ref count rules for anon exceptions.
+    for (CDStructureInfo *info in [[phase3_anonExceptions allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
+        BOOL shouldShow;
+
+        shouldShow = ![self shouldExpandStructureInfo:info];
+        if (shouldShow || debugAnonStructures) {
+            NSString *formattedString;
+
+            if (hasAddedMark == NO) {
+                [resultString appendFormat:@"#pragma mark %@\n\n", markName];
+                hasAddedMark = YES;
+            }
+
+            if (hasShownExceptions == NO) {
+                [resultString appendString:@"// Ambiguous groups\n"];
+                hasShownExceptions = YES;
+            }
+
+            if (debugAnonStructures) {
+                [resultString appendFormat:@"// %@\n", [[info type] reallyBareTypeString]];
+                [resultString appendFormat:@"// depth: %u, ref: %u, used in method? %u\n", [[info type] structureDepth], [info referenceCount], [info isUsedInMethod]];
+            }
+            formattedString = [aTypeFormatter formatVariable:nil parsedType:[info type] symbolReferences:symbolReferences];
+            if (formattedString != nil) {
+                //[resultString appendFormat:@"%@;\n\n", formattedString];
+                [resultString appendFormat:@"typedef %@ %@;\n\n", formattedString, [info typedefName]];
+            }
+        }
+    }
+
+    for (NSString *key in [[phase3_namedStructureInfo allKeys] sortedArrayUsingSelector:@selector(compare:)]) {
+        CDStructureInfo *info;
+        BOOL shouldShow;
+
+        info = [phase3_namedStructureInfo objectForKey:key];
+        shouldShow = [[info type] isTemplateType] && [info isUsedInMethod];
+        if (shouldShow || debugAnonStructures) {
+            NSString *formattedString;
+
+            if (hasAddedMark == NO) {
+                [resultString appendFormat:@"#pragma mark %@\n\n", markName];
+                hasAddedMark = YES;
+            }
+
+            if (hasShownExceptions == NO) {
+                [resultString appendString:@"// Template types\n"];
+                hasShownExceptions = YES;
+            }
+
+            if (debugAnonStructures) {
+                [resultString appendFormat:@"// %@\n", [[info type] reallyBareTypeString]];
+                [resultString appendFormat:@"// depth: %u, ref: %u, used in method? %u\n", [[info type] structureDepth], [info referenceCount], [info isUsedInMethod]];
+            }
+            formattedString = [aTypeFormatter formatVariable:nil parsedType:[info type] symbolReferences:symbolReferences];
+            if (formattedString != nil) {
+                //[resultString appendFormat:@"%@;\n\n", formattedString];
+                [resultString appendFormat:@"typedef %@ %@;\n\n", formattedString, [info typedefName]];
+            }
+        }
+    }
+}
+
+- (void)generateTypedefNames;
+{
+    for (CDStructureInfo *info in [phase3_anonStructureInfo allValues]) {
+        [info generateTypedefName:anonymousBaseName];
+    }
+
+    // And do the same for each of the anon exceptions
+    for (CDStructureInfo *info in [phase3_anonExceptions allValues]) {
+        [info generateTypedefName:anonymousBaseName];
+    }
+
+    for (CDStructureInfo *info in [phase3_nameExceptions allValues]) {
+        [info generateTypedefName:[NSString stringWithFormat:@"%@_", [[[info type] typeName] name]]];
+        [[[info type] typeName] setName:@"?"];
+    }
+
+    for (CDStructureInfo *info in [phase3_namedStructureInfo allValues]) {
+        if ([[info type] isTemplateType] && [info isUsedInMethod]) {
+            [info generateTypedefName:[NSString stringWithFormat:@"%@_", [[[info type] typeName] name]]];
+        }
+    }
+}
+
+- (void)generateMemberNames;
+{
+    for (CDStructureInfo *info in [phase3_namedStructureInfo allValues]) {
+        [[info type] generateMemberNames];
+    }
+
+    for (CDStructureInfo *info in [phase3_anonStructureInfo allValues]) {
+        [[info type] generateMemberNames];
+    }
+
+    for (CDStructureInfo *info in [phase3_nameExceptions allValues]) {
+        [[info type] generateMemberNames];
+    }
+
+    // And do the same for each of the anon exceptions
+    for (CDStructureInfo *info in [phase3_anonExceptions allValues]) {
+        [[info type] generateMemberNames];
+    }
+}
+
+- (BOOL)shouldExpandStructureInfo:(CDStructureInfo *)info;
+{
+    return (info == nil)
+        || ([info isUsedInMethod] == NO
+            && ([[info type] isTemplateType] == NO || [info isUsedInMethod] == NO)
+            && [info referenceCount] < 2
+            && (([[info name] hasPrefix:@"_"] && [[info name] hasUnderscoreCapitalPrefix] == NO) // TODO: Don't need the first hasPrefix check now.
+                || [@"?" isEqualToString:[info name]]));
+}
+
+// For automatic expansion?
+- (BOOL)shouldExpandType:(CDType *)type;
+{
+    NSString *name;
+    CDStructureInfo *info;
+
+    name = [[type typeName] description];
+    if ([@"?" isEqualToString:name]) {
+        NSString *key;
+
+        key = [type reallyBareTypeString];
+        info = [phase3_anonStructureInfo objectForKey:key];
+        if (info == nil) {
+            // Look for an exception
+            info = [phase3_anonExceptions objectForKey:[type typeString]];
+        }
+    } else {
+        info = [phase3_namedStructureInfo objectForKey:name];
+        if (info == nil) {
+            info = [phase3_nameExceptions objectForKey:[type typeString]];
+            if (info != nil) {
+                //NSLog(@"[%@] %s, found phase3 name exception... %@", identifier, _cmd, [info shortDescription]);
+                //return NO;
+            }
+        }
+    }
+
+    return [self shouldExpandStructureInfo:info];
+}
+
+- (NSString *)typedefNameForType:(CDType *)type;
+{
+    CDStructureInfo *info;
+
+    info = [phase3_anonStructureInfo objectForKey:[type reallyBareTypeString]];
+    if (info == nil) {
+        info = [phase3_anonExceptions objectForKey:[type typeString]];
+        //NSLog(@"fallback typedef info? %@ -- %@", [info shortDescription], [info typedefName]);
+    }
+
+    if (info == nil) {
+        // Check name exceptions
+        info = [phase3_nameExceptions objectForKey:[type typeString]];
+#if 0
+        if (info != nil)
+            NSLog(@"Got typedef name for phase3 name exception: %@", [info typedefName]);
+#endif
+    }
+
+    if (info == nil) {
+        info = [phase3_namedStructureInfo objectForKey:[[type typeName] description]];
+    }
+#if 0
+    if ([type isTemplateType] && [info typedefName] == nil) {
+        NSLog(@"Warning: no typedef name for type: %@", [type typeString]);
+    }
+#endif
+
+    return [info typedefName];
+}
+
+- (void)debugName:(NSString *)name;
+{
+    [debugNames addObject:name];
+}
+
+- (void)debugAnon:(NSString *)str;
+{
+    [debugAnon addObject:str];
+}
+
+@end