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-2011 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 ((self = [super init])) {
        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: %lu", 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 numberWithUnsignedInteger: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 %lu 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 %lu 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: %lu, 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