ld64-351.8.tar.gz

[apple/ld64.git] / src / ld / passes / objc.cpp

/* -*- mode: C++; c-basic-offset: 4; tab-width: 4 -*-
 *
 * Copyright (c) 2010-2011 Apple Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 *
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 *
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 *
 * @APPLE_LICENSE_HEADER_END@
 */


#include <stdint.h>
#include <math.h>
#include <unistd.h>
#include <dlfcn.h>
#include <mach/machine.h>

#include <vector>
#include <map>
#include <set>

#include "Architectures.hpp"
#include "MachOFileAbstraction.hpp"

#include "ld.hpp"
#include "objc.h"

namespace ld {
namespace passes {
namespace objc {



struct objc_image_info  {
        uint32_t        version;        // initially 0
        uint32_t        flags;
};

#define OBJC_IMAGE_SUPPORTS_GC                                          (1<<1)
#define OBJC_IMAGE_REQUIRES_GC                                          (1<<2)
#define OBJC_IMAGE_OPTIMIZED_BY_DYLD                            (1<<3)
#define OBJC_IMAGE_SUPPORTS_COMPACTION                          (1<<4)
#define OBJC_IMAGE_IS_SIMULATED                                         (1<<5)
#define OBJC_IMAGE_HAS_CATEGORY_CLASS_PROPERTIES        (1<<6)



//
// This class is the 8 byte section containing ObjC flags
//
template <typename A>
class ObjCImageInfoAtom : public ld::Atom {
public:
                                                                                        ObjCImageInfoAtom(ld::File::ObjcConstraint objcConstraint, 
                                                                                                                          bool compaction, bool abi2, bool hasCategoryClassProperties, uint8_t swiftVersion);

        virtual const ld::File*                                 file() const                                    { return NULL; }
        virtual const char*                                             name() const                                    { return "objc image info"; }
        virtual uint64_t                                                size() const                                    { return sizeof(objc_image_info); }
        virtual uint64_t                                                objectAddress() const                   { return 0; }
        virtual void                                                    setScope(Scope)                                 { }
        virtual void                                                    copyRawContent(uint8_t buffer[]) const {
                memcpy(buffer, &_content, sizeof(objc_image_info));
        }

private:        
        objc_image_info                                                 _content;

        static ld::Section                                              _s_sectionABI1;
        static ld::Section                                              _s_sectionABI2;
};

template <typename A> ld::Section ObjCImageInfoAtom<A>::_s_sectionABI1("__OBJC", "__image_info", ld::Section::typeUnclassified);
template <typename A> ld::Section ObjCImageInfoAtom<A>::_s_sectionABI2("__DATA", "__objc_imageinfo", ld::Section::typeUnclassified);


template <typename A>
ObjCImageInfoAtom<A>::ObjCImageInfoAtom(ld::File::ObjcConstraint objcConstraint, bool compaction, 
                                                                                bool abi2, bool hasCategoryClassProperties, uint8_t swiftVersion)
        : ld::Atom(abi2 ? _s_sectionABI2 : _s_sectionABI1, ld::Atom::definitionRegular, ld::Atom::combineNever,
                                                        ld::Atom::scopeLinkageUnit, ld::Atom::typeUnclassified, 
                                                        symbolTableNotIn, false, false, false, ld::Atom::Alignment(2))
{  
        
        uint32_t value = 0;
        switch ( objcConstraint ) {
                case ld::File::objcConstraintNone:
                case ld::File::objcConstraintRetainRelease:
                        if ( compaction ) 
                                warning("ignoring -objc_gc_compaction because code not compiled for ObjC garbage collection");
                        break;
                case ld::File::objcConstraintRetainReleaseOrGC:
                        value |= OBJC_IMAGE_SUPPORTS_GC;
                if ( compaction ) 
                        value |= OBJC_IMAGE_SUPPORTS_COMPACTION;
                        break;
                case ld::File::objcConstraintGC:
                        value |= OBJC_IMAGE_SUPPORTS_GC | OBJC_IMAGE_REQUIRES_GC;
                        if ( compaction ) 
                                value |= OBJC_IMAGE_SUPPORTS_COMPACTION;
                        break;
                case ld::File::objcConstraintRetainReleaseForSimulator:
                                value |= OBJC_IMAGE_IS_SIMULATED;
                        break;
        }

        if ( hasCategoryClassProperties ) {
                value |= OBJC_IMAGE_HAS_CATEGORY_CLASS_PROPERTIES;
        }

        // provide swift language version in final binary for runtime to inspect
        value |= (swiftVersion << 8);

        _content.version = 0;
        A::P::E::set32(_content.flags, value);
}



//
// This class is for a new Atom which is an ObjC method list created by merging method lists from categories
//
template <typename A>
class MethodListAtom : public ld::Atom {
public:
                                                                                        MethodListAtom(ld::Internal& state, const ld::Atom* baseMethodList, bool meta, 
                                                                                                                        const std::vector<const ld::Atom*>* categories, 
                                                                                                                        std::set<const ld::Atom*>& deadAtoms);

        virtual const ld::File*                                 file() const                                    { return _file; }
        virtual const char*                                             name() const                                    { return "objc merged method list"; }
        virtual uint64_t                                                size() const                                    { return _methodCount*3*sizeof(pint_t) + 8; }
        virtual uint64_t                                                objectAddress() const                   { return 0; }
        virtual void                                                    setScope(Scope)                                 { }
        virtual void                                                    copyRawContent(uint8_t buffer[]) const {
                bzero(buffer, size());
                A::P::E::set32(*((uint32_t*)(&buffer[0])), 3*sizeof(pint_t)); // entry size
                A::P::E::set32(*((uint32_t*)(&buffer[4])), _methodCount);
        }
        virtual ld::Fixup::iterator                             fixupsBegin() const     { return (ld::Fixup*)&_fixups[0]; }
        virtual ld::Fixup::iterator                             fixupsEnd()     const   { return (ld::Fixup*)&_fixups[_fixups.size()]; }

private:        
        typedef typename A::P::uint_t                   pint_t;

        const ld::File*                                                 _file;
        unsigned int                                                    _methodCount;
        std::vector<ld::Fixup>                                  _fixups;
        
        static ld::Section                                              _s_section;
};

template <typename A> 
ld::Section MethodListAtom<A>::_s_section("__DATA", "__objc_const", ld::Section::typeUnclassified);


//
// This class is for a new Atom which is an ObjC protocol list created by merging protocol lists from categories
//
template <typename A>
class ProtocolListAtom : public ld::Atom {
public:
                                                                                        ProtocolListAtom(ld::Internal& state, const ld::Atom* baseProtocolList, 
                                                                                                                        const std::vector<const ld::Atom*>* categories, 
                                                                                                                        std::set<const ld::Atom*>& deadAtoms);

        virtual const ld::File*                                 file() const                                    { return _file; }
        virtual const char*                                             name() const                                    { return "objc merged protocol list"; }
        virtual uint64_t                                                size() const                                    { return (_protocolCount+1)*sizeof(pint_t); }
        virtual uint64_t                                                objectAddress() const                   { return 0; }
        virtual void                                                    setScope(Scope)                                 { }
        virtual void                                                    copyRawContent(uint8_t buffer[]) const {
                bzero(buffer, size());
                A::P::setP(*((pint_t*)(buffer)), _protocolCount);
        }
        virtual ld::Fixup::iterator                             fixupsBegin() const     { return (ld::Fixup*)&_fixups[0]; }
        virtual ld::Fixup::iterator                             fixupsEnd()     const   { return (ld::Fixup*)&_fixups[_fixups.size()]; }

private:        
        typedef typename A::P::uint_t                   pint_t;

        const ld::File*                                                 _file;
        unsigned int                                                    _protocolCount;
        std::vector<ld::Fixup>                                  _fixups;
        
        static ld::Section                                              _s_section;
};

template <typename A> 
ld::Section ProtocolListAtom<A>::_s_section("__DATA", "__objc_const", ld::Section::typeUnclassified);



//
// This class is for a new Atom which is an ObjC property list created by merging property lists from categories
//
template <typename A>
class PropertyListAtom : public ld::Atom {
public:
        enum class PropertyKind { ClassProperties, InstanceProperties };

                                                                                        PropertyListAtom(ld::Internal& state, const ld::Atom* baseProtocolList, 
                                                                                                         const std::vector<const ld::Atom*>* categories, 
                                                                                                         std::set<const ld::Atom*>& deadAtoms, 
                                                                                                         PropertyKind kind);

        virtual const ld::File*                                 file() const                                    { return _file; }
        virtual const char*                                             name() const                                    { return "objc merged property list"; }
        virtual uint64_t                                                size() const                                    { return _propertyCount*2*sizeof(pint_t) + 8; }
        virtual uint64_t                                                objectAddress() const                   { return 0; }
        virtual void                                                    setScope(Scope)                                 { }
        virtual void                                                    copyRawContent(uint8_t buffer[]) const {
                bzero(buffer, size());
                A::P::E::set32(((uint32_t*)(buffer))[0], 2*sizeof(pint_t)); // sizeof(objc_property)
                A::P::E::set32(((uint32_t*)(buffer))[1], _propertyCount);
        }
        virtual ld::Fixup::iterator                             fixupsBegin() const     { return (ld::Fixup*)&_fixups[0]; }
        virtual ld::Fixup::iterator                             fixupsEnd()     const   { return (ld::Fixup*)&_fixups[_fixups.size()]; }

private:        
        typedef typename A::P::uint_t                   pint_t;

        const ld::File*                                                 _file;
        unsigned int                                                    _propertyCount;
        std::vector<ld::Fixup>                                  _fixups;
        
        static ld::Section                                              _s_section;
};

template <typename A> 
ld::Section PropertyListAtom<A>::_s_section("__DATA", "__objc_const", ld::Section::typeUnclassified);





//
// This class is used to create an Atom that replaces an atom from a .o file that holds a class_ro_t.
// It is needed because there is no way to add Fixups to an existing atom.
//
template <typename A>
class ClassROOverlayAtom : public ld::Atom {
public:
                                                                                        ClassROOverlayAtom(const ld::Atom* classROAtom);

        // overrides of ld::Atom
        virtual const ld::File*                         file() const            { return _atom->file(); }
        virtual const char*                                     name() const            { return _atom->name(); }
        virtual uint64_t                                        size() const            { return _atom->size(); }
        virtual uint64_t                                        objectAddress() const { return _atom->objectAddress(); }
        virtual void                                            copyRawContent(uint8_t buffer[]) const 
                                                                                                                        { _atom->copyRawContent(buffer); }
        virtual const uint8_t*                          rawContentPointer() const 
                                                                                                                        { return _atom->rawContentPointer(); }
        virtual unsigned long                           contentHash(const class ld::IndirectBindingTable& ibt) const 
                                                                                                                        { return _atom->contentHash(ibt); }
        virtual bool                                            canCoalesceWith(const ld::Atom& rhs, const class ld::IndirectBindingTable& ibt) const 
                                                                                                                        { return _atom->canCoalesceWith(rhs,ibt); }

        virtual ld::Fixup::iterator                     fixupsBegin() const     { return (ld::Fixup*)&_fixups[0]; }
        virtual ld::Fixup::iterator                     fixupsEnd()     const   { return (ld::Fixup*)&_fixups[_fixups.size()]; }

        void                                                            addProtocolListFixup();
        void                                                            addPropertyListFixup();
        void                                                            addMethodListFixup();

private:        
        typedef typename A::P::uint_t                   pint_t;

        void addFixupAtOffset(uint32_t offset);

        const ld::Atom*                                                 _atom;
        std::vector<ld::Fixup>                                  _fixups;
};

template <typename A>
ClassROOverlayAtom<A>::ClassROOverlayAtom(const ld::Atom* classROAtom)
        : ld::Atom(classROAtom->section(), ld::Atom::definitionRegular, ld::Atom::combineNever,
                        ld::Atom::scopeLinkageUnit, ld::Atom::typeUnclassified, 
                        classROAtom->symbolTableInclusion(), false, false, false, classROAtom->alignment()),
        _atom(classROAtom)
{
        // ensure all attributes are same as original
        this->setAttributesFromAtom(*classROAtom);

        // copy fixups from orginal atom
        for (ld::Fixup::iterator fit=classROAtom->fixupsBegin(); fit != classROAtom->fixupsEnd(); ++fit) {
                ld::Fixup fixup = *fit;
                _fixups.push_back(fixup);
        }
}


//
// Base class for reading and updating existing ObjC atoms from .o files
//
template <typename A>
class ObjCData {
public:
        static const ld::Atom*  getPointerInContent(ld::Internal& state, const ld::Atom* contentAtom, unsigned int offset, bool* hasAddend=NULL);
        static void                             setPointerInContent(ld::Internal& state, const ld::Atom* contentAtom, 
                                                                                                unsigned int offset, const ld::Atom* newAtom);
        typedef typename A::P::uint_t                   pint_t;
};

template <typename A>
const ld::Atom* ObjCData<A>::getPointerInContent(ld::Internal& state, const ld::Atom* contentAtom, unsigned int offset, bool* hasAddend)
{
        const ld::Atom* target = NULL;
        if ( hasAddend != NULL )
                *hasAddend = false;
        for (ld::Fixup::iterator fit=contentAtom->fixupsBegin(); fit != contentAtom->fixupsEnd(); ++fit) {
                if ( (fit->offsetInAtom == offset) && (fit->kind != ld::Fixup::kindNoneFollowOn) ) {
                        switch ( fit->binding ) {
                                case ld::Fixup::bindingsIndirectlyBound:
                                        target = state.indirectBindingTable[fit->u.bindingIndex];
                                        break;
                                case ld::Fixup::bindingDirectlyBound:
                                        target =  fit->u.target;
                                        break;
                                case ld::Fixup::bindingNone:
                                        if ( fit->kind == ld::Fixup::kindAddAddend ) {
                                                if ( hasAddend != NULL )
                                                        *hasAddend = true;
                                        }
                                        break;
                 default:
                    break;   
                        }
                }
        }
        return target;
}

template <typename A>
void ObjCData<A>::setPointerInContent(ld::Internal& state, const ld::Atom* contentAtom, 
                                                                                                                unsigned int offset, const ld::Atom* newAtom)
{
        for (ld::Fixup::iterator fit=contentAtom->fixupsBegin(); fit != contentAtom->fixupsEnd(); ++fit) {
                if ( fit->offsetInAtom == offset ) {
                        switch ( fit->binding ) {
                                case ld::Fixup::bindingsIndirectlyBound:
                                        state.indirectBindingTable[fit->u.bindingIndex] = newAtom;
                                        return;
                                case ld::Fixup::bindingDirectlyBound:
                                        fit->u.target = newAtom;
                                        return;
                default:
                     break;    
                        }
                }
        }
        assert(0 && "could not update method list");
}



//
// Helper class for reading and updating existing ObjC category atoms from .o files
//
template <typename A>
class Category : public ObjCData<A> {
public:
        static const ld::Atom*  getClass(ld::Internal& state, const ld::Atom* contentAtom, bool& hasAddend);
        static const ld::Atom*  getInstanceMethods(ld::Internal& state, const ld::Atom* contentAtom);
        static const ld::Atom*  getClassMethods(ld::Internal& state, const ld::Atom* contentAtom);
        static const ld::Atom*  getProtocols(ld::Internal& state, const ld::Atom* contentAtom);
        static const ld::Atom*  getInstanceProperties(ld::Internal& state, const ld::Atom* contentAtom);
        static const ld::Atom*  getClassProperties(ld::Internal& state, const ld::Atom* contentAtom);
        static uint32_t         size() { return 6*sizeof(pint_t); }
private:        
        typedef typename A::P::uint_t                   pint_t;
};


template <typename A>
const ld::Atom* Category<A>::getClass(ld::Internal& state, const ld::Atom* contentAtom, bool& hasAddend)
{
        return ObjCData<A>::getPointerInContent(state, contentAtom, sizeof(pint_t), &hasAddend); // category_t.cls
}

template <typename A>
const ld::Atom* Category<A>::getInstanceMethods(ld::Internal& state, const ld::Atom* contentAtom)
{
        return ObjCData<A>::getPointerInContent(state, contentAtom, 2*sizeof(pint_t)); // category_t.instanceMethods
}

template <typename A>
const ld::Atom* Category<A>::getClassMethods(ld::Internal& state, const ld::Atom* contentAtom)
{
        return ObjCData<A>::getPointerInContent(state, contentAtom, 3*sizeof(pint_t)); // category_t.classMethods
}

template <typename A>
const ld::Atom* Category<A>::getProtocols(ld::Internal& state, const ld::Atom* contentAtom)
{
        return ObjCData<A>::getPointerInContent(state, contentAtom, 4*sizeof(pint_t)); // category_t.protocols
}

template <typename A>
const ld::Atom* Category<A>::getInstanceProperties(ld::Internal& state, const ld::Atom* contentAtom)
{
        return ObjCData<A>::getPointerInContent(state, contentAtom, 5*sizeof(pint_t)); // category_t.instanceProperties
}

template <typename A>
const ld::Atom* Category<A>::getClassProperties(ld::Internal& state, const ld::Atom* contentAtom)
{
        // Only specially-marked files have this field.
        if (!contentAtom->file()->objcHasCategoryClassPropertiesField()) return NULL;

        return ObjCData<A>::getPointerInContent(state, contentAtom, 6*sizeof(pint_t)); // category_t.classProperties
}


template <typename A>
class MethodList : public ObjCData<A> {
public:
        static uint32_t count(ld::Internal& state, const ld::Atom* methodListAtom) {
                const uint32_t* methodListData = (uint32_t*)(methodListAtom->rawContentPointer());
                return A::P::E::get32(methodListData[1]); // method_list_t.count
        }
};

template <typename A>
class ProtocolList : public ObjCData<A> {
public:
        static uint32_t count(ld::Internal& state, const ld::Atom* protocolListAtom)  {
                pint_t* protocolListData = (pint_t*)(protocolListAtom->rawContentPointer());
                return A::P::getP(*protocolListData); // protocol_list_t.count
        }
private:
        typedef typename A::P::uint_t   pint_t;
};

template <typename A>
class PropertyList : public ObjCData<A> {
public:
        static uint32_t count(ld::Internal& state, const ld::Atom* protocolListAtom)  {
                uint32_t* protocolListData = (uint32_t*)(protocolListAtom->rawContentPointer());
                return A::P::E::get32(protocolListData[1]); // property_list_t.count
        }
private:
        typedef typename A::P::uint_t   pint_t;
};



//
// Helper class for reading and updating existing ObjC class atoms from .o files
//
template <typename A>
class Class : public ObjCData<A> {
public:
        static const ld::Atom*  getMetaClass(ld::Internal& state, const ld::Atom* classAtom);
        static const ld::Atom*  getInstanceMethodList(ld::Internal& state, const ld::Atom* classAtom);
        static const ld::Atom*  getInstanceProtocolList(ld::Internal& state, const ld::Atom* classAtom);
        static const ld::Atom*  getInstancePropertyList(ld::Internal& state, const ld::Atom* classAtom);
        static const ld::Atom*  getClassMethodList(ld::Internal& state, const ld::Atom* classAtom);
        static const ld::Atom*  getClassPropertyList(ld::Internal& state, const ld::Atom* classAtom);
        static const ld::Atom*  setInstanceMethodList(ld::Internal& state, const ld::Atom* classAtom, 
                                                                                                const ld::Atom* methodListAtom, std::set<const ld::Atom*>& deadAtoms);
        static const ld::Atom*  setInstanceProtocolList(ld::Internal& state, const ld::Atom* classAtom, 
                                                                                                const ld::Atom* protocolListAtom, std::set<const ld::Atom*>& deadAtoms);
        static const ld::Atom*  setInstancePropertyList(ld::Internal& state, const ld::Atom* classAtom, 
                                                                                                const ld::Atom* propertyListAtom, std::set<const ld::Atom*>& deadAtoms);
        static const ld::Atom*  setClassMethodList(ld::Internal& state, const ld::Atom* classAtom, 
                                                                                                const ld::Atom* methodListAtom, std::set<const ld::Atom*>& deadAtoms);
        static const ld::Atom*  setClassProtocolList(ld::Internal& state, const ld::Atom* classAtom, 
                                                                                                const ld::Atom* protocolListAtom, std::set<const ld::Atom*>& deadAtoms);
        static const ld::Atom*  setClassPropertyList(ld::Internal& state, const ld::Atom* classAtom, 
                                                                                                const ld::Atom* propertyListAtom, std::set<const ld::Atom*>& deadAtoms);
        static uint32_t         size() { return sizeof(Content); }

private:
        friend class ClassROOverlayAtom<A>;

        typedef typename A::P::uint_t                   pint_t;

        static const ld::Atom*  getROData(ld::Internal& state, const ld::Atom* classAtom);

        struct Content {
                pint_t isa;
                pint_t superclass;
                pint_t method_cache;
                pint_t vtable;
                pint_t data;
        };

        struct ROContent {
                uint32_t flags;
                uint32_t instanceStart;
                // Note there is 4-bytes of alignment padding between instanceSize 
                // and ivarLayout on 64-bit archs, but no padding on 32-bit archs.
                // This union is a way to model that.
                union {
                        uint32_t instanceSize;
                        pint_t pad;
                } instanceSize;
                pint_t ivarLayout;
                pint_t name;
                pint_t baseMethods;
                pint_t baseProtocols;
                pint_t ivars;
                pint_t weakIvarLayout;
                pint_t baseProperties;
        };
};

#define GET_FIELD(state, classAtom, field) \
        ObjCData<A>::getPointerInContent(state, classAtom, offsetof(Content, field))
#define SET_FIELD(state, classAtom, field, valueAtom) \
        ObjCData<A>::setPointerInContent(state, classAtom, offsetof(Content, field), valueAtom)

#define GET_RO_FIELD(state, classAtom, field) \
        ObjCData<A>::getPointerInContent(state, getROData(state, classAtom), offsetof(ROContent, field))
#define SET_RO_FIELD(state, classROAtom, field, valueAtom) \
        ObjCData<A>::setPointerInContent(state, getROData(state, classAtom), offsetof(ROContent, field), valueAtom)

template <typename A>
const ld::Atom* Class<A>::getMetaClass(ld::Internal& state, const ld::Atom* classAtom)
{
    const ld::Atom* metaClassAtom = GET_FIELD(state, classAtom, isa);
    assert(metaClassAtom != NULL);
    return metaClassAtom;
}

template <typename A>
const ld::Atom* Class<A>::getROData(ld::Internal& state, const ld::Atom* classAtom)
{
    const ld::Atom* classROAtom = GET_FIELD(state, classAtom, data);
    assert(classROAtom != NULL);
    return classROAtom;
}

template <typename A>
const ld::Atom* Class<A>::getInstanceMethodList(ld::Internal& state, const ld::Atom* classAtom)
{
        return GET_RO_FIELD(state, classAtom, baseMethods);
}

template <typename A>
const ld::Atom* Class<A>::getInstanceProtocolList(ld::Internal& state, const ld::Atom* classAtom)
{
        return GET_RO_FIELD(state, classAtom, baseProtocols);
}

template <typename A>
const ld::Atom* Class<A>::getInstancePropertyList(ld::Internal& state, const ld::Atom* classAtom)
{
        return GET_RO_FIELD(state, classAtom, baseProperties);
}

template <typename A>
const ld::Atom* Class<A>::getClassMethodList(ld::Internal& state, const ld::Atom* classAtom)
{
        return Class<A>::getInstanceMethodList(state, getMetaClass(state, classAtom));
}

template <typename A>
const ld::Atom* Class<A>::getClassPropertyList(ld::Internal& state, const ld::Atom* classAtom)
{
    return Class<A>::getInstancePropertyList(state, getMetaClass(state, classAtom));
}

template <typename A>
const ld::Atom* Class<A>::setInstanceMethodList(ld::Internal& state, const ld::Atom* classAtom, 
                                                                                                const ld::Atom* methodListAtom, std::set<const ld::Atom*>& deadAtoms)
{
        // if the base class does not already have a method list, we need to create an overlay
        if ( getInstanceMethodList(state, classAtom) == NULL ) {
                const ld::Atom* oldROAtom = getROData(state, classAtom);
                deadAtoms.insert(oldROAtom);
                ClassROOverlayAtom<A>* overlay = new ClassROOverlayAtom<A>(oldROAtom);
                //fprintf(stderr, "replace class RO atom %p with %p for method list in class atom %s\n", classROAtom, overlay, classAtom->name());
                overlay->addMethodListFixup();
                SET_FIELD(state, classAtom, data, overlay);
                SET_RO_FIELD(state, classAtom, baseMethods, methodListAtom);
                return overlay;
        }
        SET_RO_FIELD(state, classAtom, baseMethods, methodListAtom);
        return NULL; // means classRO atom was not replaced
}

template <typename A>
const ld::Atom* Class<A>::setInstanceProtocolList(ld::Internal& state, const ld::Atom* classAtom, 
                                                                        const ld::Atom* protocolListAtom, std::set<const ld::Atom*>& deadAtoms)
{
        // if the base class does not already have a protocol list, we need to create an overlay
        if ( getInstanceProtocolList(state, classAtom) == NULL ) {
                const ld::Atom* oldROAtom = getROData(state, classAtom);
                deadAtoms.insert(oldROAtom);
                ClassROOverlayAtom<A>* overlay = new ClassROOverlayAtom<A>(oldROAtom);
                //fprintf(stderr, "replace class RO atom %p with %p for protocol list in class atom %s\n", classROAtom, overlay, classAtom->name());
                overlay->addProtocolListFixup();
                SET_FIELD(state, classAtom, data, overlay);
                SET_RO_FIELD(state, classAtom, baseProtocols, protocolListAtom);
                return overlay;
        }
        //fprintf(stderr, "set class RO atom %p protocol list in class atom %s\n", classROAtom, classAtom->name());
        SET_RO_FIELD(state, classAtom, baseProtocols, protocolListAtom);
        return NULL;  // means classRO atom was not replaced
}

template <typename A>
const ld::Atom* Class<A>::setClassProtocolList(ld::Internal& state, const ld::Atom* classAtom, 
                                                                        const ld::Atom* protocolListAtom, std::set<const ld::Atom*>& deadAtoms)
{
        // meta class also points to same protocol list as class
        const ld::Atom* metaClassAtom = getMetaClass(state, classAtom);
        //fprintf(stderr, "setClassProtocolList(), classAtom=%p %s, metaClass=%p %s\n", classAtom, classAtom->name(), metaClassAtom, metaClassAtom->name());
        return setInstanceProtocolList(state, metaClassAtom, protocolListAtom, deadAtoms);
}



template <typename A>
const ld::Atom*  Class<A>::setInstancePropertyList(ld::Internal& state, const ld::Atom* classAtom, 
                                                                                                const ld::Atom* propertyListAtom, std::set<const ld::Atom*>& deadAtoms)
{
        // if the base class does not already have a property list, we need to create an overlay
        if ( getInstancePropertyList(state, classAtom) == NULL ) {
                const ld::Atom* oldROAtom = getROData(state, classAtom);
                deadAtoms.insert(oldROAtom);
                ClassROOverlayAtom<A>* overlay = new ClassROOverlayAtom<A>(oldROAtom);
                //fprintf(stderr, "replace class RO atom %p with %p for property list in class atom %s\n", classROAtom, overlay, classAtom->name());
                overlay->addPropertyListFixup();
                SET_FIELD(state, classAtom, data, overlay);
                SET_RO_FIELD(state, classAtom, baseProperties, propertyListAtom);
                return overlay;
        }
        SET_RO_FIELD(state, classAtom, baseProperties, propertyListAtom);
        return NULL;  // means classRO atom was not replaced
}

template <typename A>
const ld::Atom* Class<A>::setClassMethodList(ld::Internal& state, const ld::Atom* classAtom, 
                                                                                        const ld::Atom* methodListAtom, std::set<const ld::Atom*>& deadAtoms)
{
        // class methods is just instance methods of metaClass
        return setInstanceMethodList(state, getMetaClass(state, classAtom), methodListAtom, deadAtoms);
}

template <typename A>
const ld::Atom* Class<A>::setClassPropertyList(ld::Internal& state, const ld::Atom* classAtom, 
                                                                                        const ld::Atom* propertyListAtom, std::set<const ld::Atom*>& deadAtoms)
{
        // class properties is just instance properties of metaClass
        return setInstancePropertyList(state, getMetaClass(state, classAtom), propertyListAtom, deadAtoms);
}

#undef GET_FIELD
#undef SET_FIELD
#undef GET_RO_FIELD
#undef SET_RO_FIELD


template <typename P>
ld::Fixup::Kind pointerFixupKind();

template <> 
ld::Fixup::Kind pointerFixupKind<Pointer32<BigEndian>>() { 
        return ld::Fixup::kindStoreTargetAddressBigEndian32; 
}
template <> 
ld::Fixup::Kind pointerFixupKind<Pointer64<BigEndian>>() { 
        return ld::Fixup::kindStoreTargetAddressBigEndian64; 
}
template <> 
ld::Fixup::Kind pointerFixupKind<Pointer32<LittleEndian>>() { 
        return ld::Fixup::kindStoreTargetAddressLittleEndian32; 
}
template <> 
ld::Fixup::Kind pointerFixupKind<Pointer64<LittleEndian>>() { 
        return ld::Fixup::kindStoreTargetAddressLittleEndian64; 
}

template <typename A>
void ClassROOverlayAtom<A>::addFixupAtOffset(uint32_t offset)
{
        const ld::Atom* targetAtom = this; // temporary
        _fixups.push_back(ld::Fixup(offset, ld::Fixup::k1of1, pointerFixupKind<typename A::P>(), targetAtom));
}


template <typename A>
void ClassROOverlayAtom<A>::addMethodListFixup()
{
        addFixupAtOffset(offsetof(typename Class<A>::ROContent, baseMethods));
}

template <typename A>
void ClassROOverlayAtom<A>::addProtocolListFixup()
{
        addFixupAtOffset(offsetof(typename Class<A>::ROContent, baseProtocols));
}

template <typename A>
void ClassROOverlayAtom<A>::addPropertyListFixup()
{
        addFixupAtOffset(offsetof(typename Class<A>::ROContent, baseProperties));
}




//
// Encapsulates merging of ObjC categories
//
template <typename A>
class OptimizeCategories {
public:
        static void                             doit(const Options& opts, ld::Internal& state);
        static bool                             hasInstanceMethods(ld::Internal& state, const std::vector<const ld::Atom*>* categories);
        static bool                             hasClassMethods(ld::Internal& state, const std::vector<const ld::Atom*>* categories);
        static bool                             hasProtocols(ld::Internal& state, const std::vector<const ld::Atom*>* categories);
        static bool                             hasInstanceProperties(ld::Internal& state, const std::vector<const ld::Atom*>* categories);
        static bool                             hasClassProperties(ld::Internal& state, const std::vector<const ld::Atom*>* categories);
        
        static unsigned int             class_ro_baseMethods_offset();
private:
        typedef typename A::P::uint_t                   pint_t;

};


template <typename A>
bool OptimizeCategories<A>::hasInstanceMethods(ld::Internal& state, const std::vector<const ld::Atom*>* categories)
{
        for (std::vector<const ld::Atom*>::const_iterator it=categories->begin(); it != categories->end(); ++it) {
                const ld::Atom* categoryAtom = *it;
                const ld::Atom* methodList = Category<A>::getInstanceMethods(state, categoryAtom);
                if ( methodList != NULL ) {
                        if ( MethodList<A>::count(state, methodList) > 0 )
                                return true;
                }
        }
        return false;
}


template <typename A>
bool OptimizeCategories<A>::hasClassMethods(ld::Internal& state, const std::vector<const ld::Atom*>* categories)
{
        for (std::vector<const ld::Atom*>::const_iterator it=categories->begin(); it != categories->end(); ++it) {
                const ld::Atom* categoryAtom = *it;
                const ld::Atom* methodList = Category<A>::getClassMethods(state, categoryAtom);
                if ( methodList != NULL ) {
                        if ( MethodList<A>::count(state, methodList) > 0 )
                                return true;
                }
        }
        return false;
}

template <typename A>
bool OptimizeCategories<A>::hasProtocols(ld::Internal& state, const std::vector<const ld::Atom*>* categories)
{
        for (std::vector<const ld::Atom*>::const_iterator it=categories->begin(); it != categories->end(); ++it) {
                const ld::Atom* categoryAtom = *it;
                const ld::Atom* protocolListAtom = Category<A>::getProtocols(state, categoryAtom);
                if ( protocolListAtom != NULL ) {
                        if ( ProtocolList<A>::count(state, protocolListAtom) > 0 ) {    
                                return true;
                        }
                }
        }
        return false;
}


template <typename A>
bool OptimizeCategories<A>::hasInstanceProperties(ld::Internal& state, const std::vector<const ld::Atom*>* categories)
{
        for (std::vector<const ld::Atom*>::const_iterator it=categories->begin(); it != categories->end(); ++it) {
                const ld::Atom* categoryAtom = *it;
                const ld::Atom* propertyListAtom = Category<A>::getInstanceProperties(state, categoryAtom);
                if ( propertyListAtom != NULL ) {
                        if ( PropertyList<A>::count(state, propertyListAtom) > 0 )
                                return true;
                }
        }
        return false;
}


template <typename A>
bool OptimizeCategories<A>::hasClassProperties(ld::Internal& state, const std::vector<const ld::Atom*>* categories)
{
        for (std::vector<const ld::Atom*>::const_iterator it=categories->begin(); it != categories->end(); ++it) {
                const ld::Atom* categoryAtom = *it;
                const ld::Atom* propertyListAtom = Category<A>::getClassProperties(state, categoryAtom);
                if ( propertyListAtom != NULL ) {
                        if ( PropertyList<A>::count(state, propertyListAtom) > 0 )
                                return true;
                }
        }
        return false;
}


static const ld::Atom* fixClassAliases(const ld::Atom* classAtom)
{
        if ( (classAtom->size() != 0) || (classAtom->definition() == ld::Atom::definitionProxy) )
                return classAtom;

        for (ld::Fixup::iterator fit=classAtom->fixupsBegin(); fit != classAtom->fixupsEnd(); ++fit) {
                if ( fit->kind == ld::Fixup::kindNoneFollowOn ) {
                        assert(fit->offsetInAtom == 0);
                        assert(fit->binding == ld::Fixup::bindingDirectlyBound);
                        return fit->u.target;
                }
        }

        return classAtom;
}

//
// Helper for std::remove_if
//
class OptimizedAway {
public:
        OptimizedAway(const std::set<const ld::Atom*>& oa) : _dead(oa) {}
        bool operator()(const ld::Atom* atom) const {
                return ( _dead.count(atom) != 0 );
        }
private:
        const std::set<const ld::Atom*>& _dead;
};

        struct AtomSorter
        {       
                bool operator()(const Atom* left, const Atom* right)
                {
                        // sort by file ordinal, then object address, then zero size, then symbol name
                        // only file based atoms are supported (file() != NULL)
                        if (left==right) return false;
                        const File *leftf = left->file();
                        const File *rightf = right->file();
                        
                        if (leftf == rightf) {
                                if (left->objectAddress() != right->objectAddress()) {
                                        return left->objectAddress() < right->objectAddress();
                                } else {
                                        // for atoms in the same file with the same address, zero sized
                                        // atoms must sort before nonzero sized atoms
                                        if ((left->size() == 0 && right->size() > 0) || (left->size() > 0 && right->size() == 0))
                                                return left->size() < right->size();
                                        return strcmp(left->name(), right->name());
                                }
                        }
                        return  (leftf->ordinal() < rightf->ordinal());
                }
        };
        
        static void sortAtomVector(std::vector<const Atom*> &atoms) {
                std::sort(atoms.begin(), atoms.end(), AtomSorter());
        }


template <typename A>
void OptimizeCategories<A>::doit(const Options& opts, ld::Internal& state)
{
        // first find all categories referenced by __objc_nlcatlist section
        std::set<const ld::Atom*> nlcatListAtoms;
        for (std::vector<ld::Internal::FinalSection*>::iterator sit=state.sections.begin(); sit != state.sections.end(); ++sit) {
                ld::Internal::FinalSection* sect = *sit;
                if ( (strcmp(sect->sectionName(), "__objc_nlcatlist") == 0) && (strncmp(sect->segmentName(), "__DATA", 6) == 0) ) {
                        for (std::vector<const ld::Atom*>::iterator ait=sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
                                const ld::Atom* categoryListElementAtom = *ait;
                                for (unsigned int offset=0; offset < categoryListElementAtom->size(); offset += sizeof(pint_t)) {
                                        const ld::Atom* categoryAtom = ObjCData<A>::getPointerInContent(state, categoryListElementAtom, offset);
                                        //fprintf(stderr, "offset=%d, cat=%p %s\n", offset, categoryAtom, categoryAtom->name());
                                        assert(categoryAtom != NULL);
                                        nlcatListAtoms.insert(categoryAtom);
                                }
                        }
                }
        }
        
        // build map of all classes in this image that have categories on them
        typedef std::map<const ld::Atom*, std::vector<const ld::Atom*>*> CatMap;
        CatMap classToCategories;
        std::vector<const ld::Atom*> classOrder;
        std::set<const ld::Atom*> deadAtoms;
        ld::Internal::FinalSection* methodListSection = NULL;
        for (std::vector<ld::Internal::FinalSection*>::iterator sit=state.sections.begin(); sit != state.sections.end(); ++sit) {
                ld::Internal::FinalSection* sect = *sit;
                if ( sect->type() == ld::Section::typeObjC2CategoryList ) {
                        for (std::vector<const ld::Atom*>::iterator ait=sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
                                const ld::Atom* categoryListElementAtom = *ait;
                                bool hasAddend;
                                const ld::Atom* categoryAtom = ObjCData<A>::getPointerInContent(state, categoryListElementAtom, 0, &hasAddend);
                                if ( hasAddend || (categoryAtom->symbolTableInclusion() ==  ld::Atom::symbolTableNotIn)) {
                                        //<rdar://problem/8309530> gcc-4.0 uses 'L' labels on categories which disables this optimization
                                        //warning("__objc_catlist element does not point to start of category");
                                        continue;
                                }
                                assert(categoryAtom != NULL);
                                assert(categoryAtom->size() >= Category<A>::size());
                                // ignore categories also in __objc_nlcatlist
                                if ( nlcatListAtoms.count(categoryAtom) != 0 )
                                        continue;
                                const ld::Atom* categoryOnClassAtom = fixClassAliases(Category<A>::getClass(state, categoryAtom, hasAddend));
                                assert(categoryOnClassAtom != NULL);
                                // only look at classes defined in this image
                                if ( categoryOnClassAtom->definition() != ld::Atom::definitionProxy ) {
                                        // <rdar://problem/16107696> for now, back off optimization on new style classes
                                        if ( hasAddend != 0 )
                                                continue;
                                        // <rdar://problem/17249777> don't apply categories to swift classes
                                        if ( categoryOnClassAtom->hasFixupsOfKind(ld::Fixup::kindNoneGroupSubordinate) )
                                                continue;

                                        CatMap::iterator pos = classToCategories.find(categoryOnClassAtom);
                                        if ( pos == classToCategories.end() ) {
                                                classToCategories[categoryOnClassAtom] = new std::vector<const ld::Atom*>();
                                                classOrder.push_back(categoryOnClassAtom);
                                        }
                                        classToCategories[categoryOnClassAtom]->push_back(categoryAtom);
                                        // mark category atom and catlist atom as dead
                                        deadAtoms.insert(categoryAtom);
                                        deadAtoms.insert(categoryListElementAtom);
                                }
                        }
                }
                // record method list section
                if ( (strcmp(sect->sectionName(), "__objc_const") == 0) && (strncmp(sect->segmentName(), "__DATA", 6) == 0) )
                        methodListSection = sect;
        }

        // if found some categories
        if ( classToCategories.size() != 0 ) {
                assert(methodListSection != NULL);
                sortAtomVector(classOrder);
                // alter each class definition to have new method list which includes all category methods
                for (std::vector<const ld::Atom*>::iterator it = classOrder.begin(); it != classOrder.end(); it++) {
                        const ld::Atom* classAtom = *it;
                        const std::vector<const ld::Atom*>* categories = classToCategories[classAtom];
                        assert(categories->size() != 0);
                        // if any category adds instance methods, generate new merged method list, and replace
                        if ( OptimizeCategories<A>::hasInstanceMethods(state, categories) ) { 
                                const ld::Atom* baseInstanceMethodListAtom = Class<A>::getInstanceMethodList(state, classAtom); 
                                const ld::Atom* newInstanceMethodListAtom = new MethodListAtom<A>(state, baseInstanceMethodListAtom, false, categories, deadAtoms);
                                const ld::Atom* newClassRO = Class<A>::setInstanceMethodList(state, classAtom, newInstanceMethodListAtom, deadAtoms);
                                // add new method list to final sections
                                methodListSection->atoms.push_back(newInstanceMethodListAtom);
                                state.atomToSection[newInstanceMethodListAtom] = methodListSection;
                                if ( newClassRO != NULL ) {
                                        assert(strcmp(newClassRO->section().sectionName(), "__objc_const") == 0);
                                        methodListSection->atoms.push_back(newClassRO);
                                        state.atomToSection[newClassRO] = methodListSection;
                                }
                        }
                        // if any category adds class methods, generate new merged method list, and replace
                        if ( OptimizeCategories<A>::hasClassMethods(state, categories) ) { 
                                const ld::Atom* baseClassMethodListAtom = Class<A>::getClassMethodList(state, classAtom); 
                                const ld::Atom* newClassMethodListAtom = new MethodListAtom<A>(state, baseClassMethodListAtom, true, categories, deadAtoms);
                                const ld::Atom* newClassRO = Class<A>::setClassMethodList(state, classAtom, newClassMethodListAtom, deadAtoms);
                                // add new method list to final sections
                                methodListSection->atoms.push_back(newClassMethodListAtom);
                                state.atomToSection[newClassMethodListAtom] = methodListSection;
                                if ( newClassRO != NULL ) {
                                        assert(strcmp(newClassRO->section().sectionName(), "__objc_const") == 0);
                                        methodListSection->atoms.push_back(newClassRO);
                                        state.atomToSection[newClassRO] = methodListSection;
                                }
                        }
                        // if any category adds protocols, generate new merged protocol list, and replace
                        if ( OptimizeCategories<A>::hasProtocols(state, categories) ) { 
                                const ld::Atom* baseProtocolListAtom = Class<A>::getInstanceProtocolList(state, classAtom); 
                                const ld::Atom* newProtocolListAtom = new ProtocolListAtom<A>(state, baseProtocolListAtom, categories, deadAtoms);
                                const ld::Atom* newClassRO = Class<A>::setInstanceProtocolList(state, classAtom, newProtocolListAtom, deadAtoms);
                                const ld::Atom* newMetaClassRO = Class<A>::setClassProtocolList(state, classAtom, newProtocolListAtom, deadAtoms);
                                // add new protocol list to final sections
                                methodListSection->atoms.push_back(newProtocolListAtom);
                                state.atomToSection[newProtocolListAtom] = methodListSection;
                                if ( newClassRO != NULL ) {
                                        assert(strcmp(newClassRO->section().sectionName(), "__objc_const") == 0);
                                        methodListSection->atoms.push_back(newClassRO);
                                        state.atomToSection[newClassRO] = methodListSection;
                                }
                                if ( newMetaClassRO != NULL ) {
                                        assert(strcmp(newMetaClassRO->section().sectionName(), "__objc_const") == 0);
                                        methodListSection->atoms.push_back(newMetaClassRO);
                                        state.atomToSection[newMetaClassRO] = methodListSection;
                                }
                        }
                        // if any category adds instance properties, generate new merged property list, and replace
                        if ( OptimizeCategories<A>::hasInstanceProperties(state, categories) ) { 
                                const ld::Atom* basePropertyListAtom = Class<A>::getInstancePropertyList(state, classAtom); 
                                const ld::Atom* newPropertyListAtom = new PropertyListAtom<A>(state, basePropertyListAtom, categories, deadAtoms, PropertyListAtom<A>::PropertyKind::InstanceProperties);
                                const ld::Atom* newClassRO = Class<A>::setInstancePropertyList(state, classAtom, newPropertyListAtom, deadAtoms);
                                // add new property list to final sections
                                methodListSection->atoms.push_back(newPropertyListAtom);
                                state.atomToSection[newPropertyListAtom] = methodListSection;
                                if ( newClassRO != NULL ) {
                                        assert(strcmp(newClassRO->section().sectionName(), "__objc_const") == 0);
                                        methodListSection->atoms.push_back(newClassRO);
                                        state.atomToSection[newClassRO] = methodListSection;
                                }
                        }
                        // if any category adds class properties, generate new merged property list, and replace
                        if ( OptimizeCategories<A>::hasClassProperties(state, categories) ) { 
                                const ld::Atom* basePropertyListAtom = Class<A>::getClassPropertyList(state, classAtom); 
                                const ld::Atom* newPropertyListAtom = new PropertyListAtom<A>(state, basePropertyListAtom, categories, deadAtoms, PropertyListAtom<A>::PropertyKind::ClassProperties);
                                const ld::Atom* newClassRO = Class<A>::setClassPropertyList(state, classAtom, newPropertyListAtom, deadAtoms);
                                // add new property list to final sections
                                methodListSection->atoms.push_back(newPropertyListAtom);
                                state.atomToSection[newPropertyListAtom] = methodListSection;
                                if ( newClassRO != NULL ) {
                                        assert(strcmp(newClassRO->section().sectionName(), "__objc_const") == 0);
                                        methodListSection->atoms.push_back(newClassRO);
                                        state.atomToSection[newClassRO] = methodListSection;
                                }
                        }                
                }

                // remove dead atoms
                for (std::vector<ld::Internal::FinalSection*>::iterator sit=state.sections.begin(); sit != state.sections.end(); ++sit) {
                        ld::Internal::FinalSection* sect = *sit;
                        sect->atoms.erase(std::remove_if(sect->atoms.begin(), sect->atoms.end(), OptimizedAway(deadAtoms)), sect->atoms.end());
                }
        }
}



template <typename A> 
MethodListAtom<A>::MethodListAtom(ld::Internal& state, const ld::Atom* baseMethodList, bool meta, 
                                                                        const std::vector<const ld::Atom*>* categories, std::set<const ld::Atom*>& deadAtoms)
  : ld::Atom(_s_section, ld::Atom::definitionRegular, ld::Atom::combineNever,
                        ld::Atom::scopeLinkageUnit, ld::Atom::typeUnclassified, 
                        symbolTableNotIn, false, false, false, ld::Atom::Alignment(3)), _file(NULL), _methodCount(0) 
{
        unsigned int fixupCount = 0;
        std::set<const ld::Atom*> baseMethodListMethodNameAtoms;
        // if base class has method list, then associate new method list with file defining class
        if ( baseMethodList != NULL ) {
                _file = baseMethodList->file();
                // calculate total size of merge method lists
                _methodCount = MethodList<A>::count(state, baseMethodList);
                deadAtoms.insert(baseMethodList);
                fixupCount = baseMethodList->fixupsEnd() - baseMethodList->fixupsBegin();
                for (ld::Fixup::iterator fit=baseMethodList->fixupsBegin(); fit != baseMethodList->fixupsEnd(); ++fit) {
                        if ( (fit->offsetInAtom - 8) % (3*sizeof(pint_t)) == 0 ) {
                                assert(fit->binding == ld::Fixup::bindingsIndirectlyBound && "malformed method list");
                                const ld::Atom* target = state.indirectBindingTable[fit->u.bindingIndex];
                                assert(target->contentType() == ld::Atom::typeCString && "malformed method list");
                                baseMethodListMethodNameAtoms.insert(target);
                        }
                }
        }
        for (std::vector<const ld::Atom*>::const_iterator ait=categories->begin(); ait != categories->end(); ++ait) {
                const ld::Atom* categoryMethodListAtom;
                if ( meta )
                        categoryMethodListAtom = Category<A>::getClassMethods(state, *ait);
                else
                        categoryMethodListAtom = Category<A>::getInstanceMethods(state, *ait);
                if ( categoryMethodListAtom != NULL ) {
                        _methodCount += MethodList<A>::count(state, categoryMethodListAtom);
                        fixupCount += (categoryMethodListAtom->fixupsEnd() - categoryMethodListAtom->fixupsBegin());
                        deadAtoms.insert(categoryMethodListAtom);
                        // if base class did not have method list, associate new method list with file the defined category
                        if ( _file == NULL )
                                _file = categoryMethodListAtom->file();
                }
        }
        //if ( baseMethodList != NULL )
        //      fprintf(stderr, "total merged method count=%u for baseMethodList=%s\n", _methodCount, baseMethodList->name());
        //else
        //      fprintf(stderr, "total merged method count=%u\n", _methodCount);
        //fprintf(stderr, "total merged fixup count=%u\n", fixupCount);
        
        // copy fixups and adjust offsets (in reverse order to simulator objc runtime)
        _fixups.reserve(fixupCount);
        uint32_t slide = 0;
        std::set<const ld::Atom*> categoryMethodNameAtoms;
        for (std::vector<const ld::Atom*>::const_reverse_iterator rit=categories->rbegin(); rit != categories->rend(); ++rit) {
                const ld::Atom* categoryMethodListAtom;
                if ( meta )
                        categoryMethodListAtom = Category<A>::getClassMethods(state, *rit);
                else
                        categoryMethodListAtom = Category<A>::getInstanceMethods(state, *rit);
                if ( categoryMethodListAtom != NULL ) {
                        for (ld::Fixup::iterator fit=categoryMethodListAtom->fixupsBegin(); fit != categoryMethodListAtom->fixupsEnd(); ++fit) {
                                ld::Fixup fixup = *fit;
                                fixup.offsetInAtom += slide;
                                _fixups.push_back(fixup);
                                if ( (fixup.offsetInAtom - 8) % (3*sizeof(pint_t)) == 0 ) {
                                        // <rdar://problem/8642343> warning when a method is overridden in a category in the same link unit
                                        assert(fixup.binding == ld::Fixup::bindingsIndirectlyBound && "malformed category method list");
                                        const ld::Atom* target = state.indirectBindingTable[fixup.u.bindingIndex];
                                        assert(target->contentType() == ld::Atom::typeCString && "malformed method list");
                                        // this objc pass happens after cstrings are coalesced, so we can just compare the atom addres instead of its content
                                        if ( baseMethodListMethodNameAtoms.count(target) != 0 ) {
                                                warning("%s method '%s' in category from %s overrides method from class in %s", 
                                                        (meta ? "meta" : "instance"), target->rawContentPointer(),
                                                        categoryMethodListAtom->safeFilePath(), baseMethodList->safeFilePath() );
                                        }
                                        if ( categoryMethodNameAtoms.count(target) != 0 ) {
                                                warning("%s method '%s' in category from %s conflicts with same method from another category", 
                                                        (meta ? "meta" : "instance"), target->rawContentPointer(),
                                                        categoryMethodListAtom->safeFilePath());
                                        }
                                        categoryMethodNameAtoms.insert(target);
                                }
                        }
                        slide += 3*sizeof(pint_t) * MethodList<A>::count(state, categoryMethodListAtom);
                }
        }
        // add method list from base class last
        if ( baseMethodList != NULL ) {
                for (ld::Fixup::iterator fit=baseMethodList->fixupsBegin(); fit != baseMethodList->fixupsEnd(); ++fit) {
                        ld::Fixup fixup = *fit;
                        fixup.offsetInAtom += slide;
                        _fixups.push_back(fixup);
                }
        }
}


template <typename A> 
ProtocolListAtom<A>::ProtocolListAtom(ld::Internal& state, const ld::Atom* baseProtocolList, 
                                                                        const std::vector<const ld::Atom*>* categories, std::set<const ld::Atom*>& deadAtoms)
  : ld::Atom(_s_section, ld::Atom::definitionRegular, ld::Atom::combineNever,
                        ld::Atom::scopeLinkageUnit, ld::Atom::typeUnclassified, 
                        symbolTableNotIn, false, false, false, ld::Atom::Alignment(3)), _file(NULL), _protocolCount(0) 
{
        unsigned int fixupCount = 0;
        if ( baseProtocolList != NULL ) {
                // if base class has protocol list, then associate new protocol list with file defining class
                _file = baseProtocolList->file();
                // calculate total size of merged protocol list
                _protocolCount = ProtocolList<A>::count(state, baseProtocolList);
                deadAtoms.insert(baseProtocolList);
                fixupCount = baseProtocolList->fixupsEnd() - baseProtocolList->fixupsBegin();
        }
        for (std::vector<const ld::Atom*>::const_iterator ait=categories->begin(); ait != categories->end(); ++ait) {
                const ld::Atom* categoryProtocolListAtom = Category<A>::getProtocols(state, *ait);
                if ( categoryProtocolListAtom != NULL ) {
                        _protocolCount += ProtocolList<A>::count(state, categoryProtocolListAtom);
                        fixupCount += (categoryProtocolListAtom->fixupsEnd() - categoryProtocolListAtom->fixupsBegin());
                        deadAtoms.insert(categoryProtocolListAtom);
                        // if base class did not have protocol list, associate new protocol list with file the defined category
                        if ( _file == NULL )
                                _file = categoryProtocolListAtom->file();
                }
        }
        //fprintf(stderr, "total merged protocol count=%u\n", _protocolCount);
        //fprintf(stderr, "total merged fixup count=%u\n", fixupCount);
        
        // copy fixups and adjust offsets 
        _fixups.reserve(fixupCount);
        uint32_t slide = 0;
        for (std::vector<const ld::Atom*>::const_iterator it=categories->begin(); it != categories->end(); ++it) {
                const ld::Atom* categoryProtocolListAtom = Category<A>::getProtocols(state, *it);
                if ( categoryProtocolListAtom != NULL ) {
                        for (ld::Fixup::iterator fit=categoryProtocolListAtom->fixupsBegin(); fit != categoryProtocolListAtom->fixupsEnd(); ++fit) {
                                ld::Fixup fixup = *fit;
                                fixup.offsetInAtom += slide;
                                _fixups.push_back(fixup);
                                //if ( fixup.binding == ld::Fixup::bindingDirectlyBound )
                                //      fprintf(stderr, "offset=0x%08X, name=%s\n", fixup.offsetInAtom, fixup.u.target->name());
                        }
                        slide += sizeof(pint_t) * ProtocolList<A>::count(state, categoryProtocolListAtom);
                }
        }
        // add method list from base class last
        if ( baseProtocolList != NULL ) {
                for (ld::Fixup::iterator fit=baseProtocolList->fixupsBegin(); fit != baseProtocolList->fixupsEnd(); ++fit) {
                        ld::Fixup fixup = *fit;
                        fixup.offsetInAtom += slide;
                        _fixups.push_back(fixup);
                }
        }
}


template <typename A> 
PropertyListAtom<A>::PropertyListAtom(ld::Internal& state, const ld::Atom* basePropertyList, 
                                      const std::vector<const ld::Atom*>* categories, std::set<const ld::Atom*>& deadAtoms, PropertyKind kind)
  : ld::Atom(_s_section, ld::Atom::definitionRegular, ld::Atom::combineNever,
                        ld::Atom::scopeLinkageUnit, ld::Atom::typeUnclassified, 
                        symbolTableNotIn, false, false, false, ld::Atom::Alignment(3)), _file(NULL), _propertyCount(0) 
{
        unsigned int fixupCount = 0;
        if ( basePropertyList != NULL ) {
                // if base class has property list, then associate new property list with file defining class
                _file = basePropertyList->file();
                // calculate total size of merged property list
                _propertyCount = PropertyList<A>::count(state, basePropertyList);
                deadAtoms.insert(basePropertyList);
                fixupCount = basePropertyList->fixupsEnd() - basePropertyList->fixupsBegin();
        }
        for (std::vector<const ld::Atom*>::const_iterator ait=categories->begin(); ait != categories->end(); ++ait) {
                const ld::Atom* categoryPropertyListAtom = kind == PropertyKind::ClassProperties ? Category<A>::getClassProperties(state, *ait) : Category<A>::getInstanceProperties(state, *ait);
                if ( categoryPropertyListAtom != NULL ) {
                        _propertyCount += PropertyList<A>::count(state, categoryPropertyListAtom);
                        fixupCount += (categoryPropertyListAtom->fixupsEnd() - categoryPropertyListAtom->fixupsBegin());
                        deadAtoms.insert(categoryPropertyListAtom);
                        // if base class did not have property list, associate new property list with file the defined category
                        if ( _file == NULL )
                                _file = categoryPropertyListAtom->file();
                }
        }
        //fprintf(stderr, "total merged property count=%u\n", _propertyCount);
        //fprintf(stderr, "total merged fixup count=%u\n", fixupCount);
        
        // copy fixups and adjust offsets 
        _fixups.reserve(fixupCount);
        uint32_t slide = 0;
        for (std::vector<const ld::Atom*>::const_iterator it=categories->begin(); it != categories->end(); ++it) {
                const ld::Atom* categoryPropertyListAtom = kind == PropertyKind::ClassProperties ? Category<A>::getClassProperties(state, *it) : Category<A>::getInstanceProperties(state, *it);
                if ( categoryPropertyListAtom != NULL ) {
                        for (ld::Fixup::iterator fit=categoryPropertyListAtom->fixupsBegin(); fit != categoryPropertyListAtom->fixupsEnd(); ++fit) {
                                ld::Fixup fixup = *fit;
                                fixup.offsetInAtom += slide;
                                _fixups.push_back(fixup);
                                //fprintf(stderr, "offset=0x%08X, binding=%d\n", fixup.offsetInAtom, fixup.binding);
                                //if ( fixup.binding == ld::Fixup::bindingDirectlyBound )
                                //      fprintf(stderr, "offset=0x%08X, name=%s\n", fixup.offsetInAtom, fixup.u.target->name());
                                //else if ( fixup.binding == ld::Fixup::bindingsIndirectlyBound )
                                //      fprintf(stderr, "offset=0x%08X, indirect index=%u, name=%s\n", fixup.offsetInAtom, fixup.u.bindingIndex, 
                                //                      (char*)(state.indirectBindingTable[fixup.u.bindingIndex]->rawContentPointer()));
                        }
                        slide += 2*sizeof(pint_t) * PropertyList<A>::count(state, categoryPropertyListAtom);
                }
        }
        // add method list from base class last
        if ( basePropertyList != NULL ) {
                for (ld::Fixup::iterator fit=basePropertyList->fixupsBegin(); fit != basePropertyList->fixupsEnd(); ++fit) {
                        ld::Fixup fixup = *fit;
                        fixup.offsetInAtom += slide;
                        _fixups.push_back(fixup);
                }
        }
}


template <typename A>
void scanCategories(ld::Internal& state, 
                                        bool& haveCategoriesWithNonNullClassProperties, 
                                        bool& haveCategoriesWithoutClassPropertyStorage)
{
        haveCategoriesWithNonNullClassProperties = false;
        haveCategoriesWithoutClassPropertyStorage = false;
        
        for (std::vector<ld::Internal::FinalSection*>::iterator sit=state.sections.begin(); sit != state.sections.end(); ++sit) {
                ld::Internal::FinalSection* sect = *sit;
                if ( sect->type() == ld::Section::typeObjC2CategoryList ) {
                        for (std::vector<const ld::Atom*>::iterator ait=sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
                                const ld::Atom* categoryListElementAtom = *ait;
                                bool hasAddend;
                                const ld::Atom* categoryAtom = ObjCData<A>::getPointerInContent(state, categoryListElementAtom, 0, &hasAddend);
                                
                                if (Category<A>::getClassProperties(state, categoryAtom)) {
                                        haveCategoriesWithNonNullClassProperties = true;
                                        // fprintf(stderr, "category in file %s has non-null class properties\n", categoryAtom->safeFilePath());
                                }
                                
                                if (!categoryAtom->file()->objcHasCategoryClassPropertiesField()) {
                                        haveCategoriesWithoutClassPropertyStorage = true;
                                        // fprintf(stderr, "category in file %s has no storage for class properties\n", categoryAtom->safeFilePath());
                                }
                        }
                }
        }
}


template <typename A, bool isObjC2>
void doPass(const Options& opts, ld::Internal& state)
{
        // Do nothing if the output has no ObjC content.
        if ( state.objcObjectConstraint == ld::File::objcConstraintNone ) {
                return;
        }

        // verify dylibs are GC compatible with object files
        if ( state.objcObjectConstraint != state.objcDylibConstraint ) {
                if (   (state.objcDylibConstraint == ld::File::objcConstraintRetainRelease)
                        && (state.objcObjectConstraint == ld::File::objcConstraintGC) ) {
                                throw "Linked dylibs built for retain/release but object files built for GC-only";
                }
                else if (   (state.objcDylibConstraint == ld::File::objcConstraintGC)
                             && (state.objcObjectConstraint == ld::File::objcConstraintRetainRelease) ) {
                                throw "Linked dylibs built for GC-only but object files built for retain/release";
                }
        }

        if ( opts.objcCategoryMerging() ) {
                // optimize classes defined in this linkage unit by merging in categories also in this linkage unit
                OptimizeCategories<A>::doit(opts, state);
        }

        // Search for surviving categories that have a non-null class properties field.
        // Search for surviving categories that do not have storage for the class properties field.
        bool haveCategoriesWithNonNullClassProperties;
        bool haveCategoriesWithoutClassPropertyStorage;
        scanCategories<A>(state, haveCategoriesWithNonNullClassProperties, haveCategoriesWithoutClassPropertyStorage);

        // Complain about mismatched category ABI.
        // These can't be combined into a single linkage unit because there is only one size indicator for all categories in the file.
        // If there is a mismatch then we don't set the HasCategoryClassProperties bit in the output file, 
        // which has at runtime causes any class property metadata that was present to be ignored.
        if (haveCategoriesWithNonNullClassProperties  &&  haveCategoriesWithoutClassPropertyStorage) {
                warning("Some object files have incompatible Objective-C category definitions. Some category metadata may be lost. All files containing Objective-C categories should be built using the same compiler.");
        }

        // add image info atom
        // The HasCategoryClassProperties bit is set as often as possible.
        state.addAtom(*new ObjCImageInfoAtom<A>(state.objcObjectConstraint, opts.objcGcCompaction(), isObjC2,
                                                                                        !haveCategoriesWithoutClassPropertyStorage, state.swiftVersion));
}


void doPass(const Options& opts, ld::Internal& state)
{               
        switch ( opts.architecture() ) {
#if SUPPORT_ARCH_x86_64
                case CPU_TYPE_X86_64:
                        doPass<x86_64, true>(opts, state);
                        break;
#endif
#if SUPPORT_ARCH_i386
                case CPU_TYPE_I386:
                        if (opts.objCABIVersion2POverride()) {
                                doPass<x86, true>(opts, state);
                        } else {
                                doPass<x86, false>(opts, state);
                        }
                        break;
#endif
#if SUPPORT_ARCH_arm_any
                case CPU_TYPE_ARM:
                        doPass<arm, true>(opts, state);
                        break;
#endif
#if SUPPORT_ARCH_arm64
                case CPU_TYPE_ARM64:
                        doPass<arm64, true>(opts, state);
                        break;
#endif
                default:
                        assert(0 && "unknown objc arch");
        }
}


} // namespace objc
} // namespace passes 
} // namespace ld