Minimal Single Header Objective-C and Blocks Runtime

objc.h

/*
 * Creator: Naman Dixit
 * Notice: © Copyright 2024 Naman Dixit
 * License: BSD Zero Clause License
 * SPDX: 0BSD (https://spdx.org/licenses/0BSD.html)
 * Language: -*- objective-c -*-
 */

/*
 * This is a minimal Objective-C runtime designed for easy embeddability and DLL-based hot-reloading.
 *
 * Characteristics:
 *   1. This emulates the GCC Runtime ABI since it is the only one that can be implemented in pure C without
 *      any inline assembly. This means that the features of Objective-C 2.0 are not available.
 *   2. Since we allow for hot-reloading which will invalidate all pointers to data inside the DLL, the output
 *      of any primitives that returns pointers to interal data (like @selector(...) and @protocol(...))
 *      should not be cached across reload.
 *
 * Usage:
 *     In one translation unit, define OBJC_IMPLEMENTATION macro.
 *     Call `objcLoad(runtime, miface, forward_func)` after every load (including the first).
 *     Compilation command should be: clang -fobjc-runtime=gcc -fblocks <source> -o <output>
 */

#if !defined(OBJC_HEADER_GUARD)
# define OBJC_HEADER_GUARD

// Download from here: https://gist.github.com/namandixit/22d61e7e416f7e4637730d3e5ff2a479
# include "std.h"
#include <stdatomic.h>

# if !defined(ENV_COMPILER_CLANG)
#  error objc.h is only supported with Clang compiler
# endif

// Type Declaration ===============================================================================================

typedef struct ObjC__Runtime * Runtime;
typedef struct ObjC__Class   * Class;
typedef struct ObjC__Object {
    Class class_pointer;
} *id;
typedef const struct ObjC__Selector * SEL;

# define OBJC_METHOD_DECL(name) id name ([[maybe_unused]] id obj, [[maybe_unused]] SEL sel, ...)
typedef OBJC_METHOD_DECL((*IMP));

# define Nil ((Class)(void*)nullptr)
# define nil ((id)(void*)nullptr)

@class Protocol;

# define OBJC_FORWARD_FUNC_DECL(name) id name ([[maybe_unused]] id obj, [[maybe_unused]] SEL sel, va_list args)

// Function Declarations ==========================================================================================

// Runtime --------------------------------------------------------------------------------------------------------

// This (re-)initializes the ObjC runtime.
// `runtime`: The value of `runtime` can either be a pointer to a ObjC_Runtime variables, or NULL.
//            If the value of `runtime` is non-NULL, that variable is used as the runtime handle. The same value is returned.
//            If it is NULL, then a new runtime is allocated using `miface` and is used and returned.
//            When initializing for the first time, use the NULL variant. Otherwise (during hotloading), use the non-NULL variant.
// `miface`: Memory Allocator, should support memRescind
// `optional_forward_func`: If the method can not be found, this function is called. Can be NULL.
Runtime objcLoad (Runtime runtime, Memory_Allocator_Interface *miface, OBJC_FORWARD_FUNC_DECL((*optional_forward_func)));

// Class ----------------------------------------------------------------------------------------------------------

const Char* objcClsGetName (Class cls);

// These functions return Class pointer (since id is compatible with Class)
Class objcClsLookup (const Char *name); // Called to get class pointer from class name, return nil if not found
Class objcClsExpect (const Char *name); // Called to get class pointer from class name, error if not found

Class objcClsGetSuper    (Class cls); // Get Super class
Class objcClsGetFirstSub (Class cls); // Get first child class in the inheritance tree
Class objcClsGetNextPeer (Class cls); // Get the next sibling class in the inheritance tree

id objcClsCreateInstance (Class cls, Size extra_bytes);

Size objcClsGetInstanceSize (Class cls);

Bool   objcClsHasMethod (Class cls, SEL op, Bool instance_method);

Bool objcClsConformsToProtocol (Class cls, Protocol *proto);

// Object ---------------------------------------------------------------------------------------------------------

Class   objcObjGetClass   (id obj);

void objcObjDispose (id obj);
id   objcObjCopy    (id src_obj, Size extra_bytes);

// Selector -------------------------------------------------------------------------------------------------------

const Char* objcSelGetName (SEL sel);

Bool objcSelIsEqual (SEL a, SEL b);
Bool objcSelIsSame  (SEL a, const Char *b);

// Protocol -------------------------------------------------------------------------------------------------------

const Char* objcProtoGetName (Protocol *proto);

Protocol* objcProtoLookup (const Char *name);
Protocol* objcProtoExpect (const Char *name);

Bool objcProtoConformsToProtocol (Protocol *proto, Protocol *other);
Bool objcProtoIsEqual            (Protocol *proto, Protocol *other);

SEL         objcProtoGetMethodName (Protocol *proto, SEL op, Bool instance_method);
const Char* objcProtoGetMethodType (Protocol *proto, SEL op, Bool instance_method);

// Block ----------------------------------------------------------------------------------------------------------

void *objcBlockCopyFunc (void *aBlock);
void  objcBlockFreeFunc (void *aBlock);

# define objcBlockCopy(...) ((__typeof(__VA_ARGS__))objcBlockCopyFunc((void *)(__VA_ARGS__)))
# define objcBlockFree(...) objcBlockFreeFunc((void *)(__VA_ARGS__))

// Class Declaration ==============================================================================================

[[clang::objc_root_class]]
@interface Object {
    Class class_pointer;
}

// Initializing the class ........................................................................................

// This method is automatically invoked on any class which implements it when the class is loaded into the runtime.
// It is also invoked on any category where the method is implemented when that category is loaded into the runtime.
// The +load method is called directly by the runtime and you should never send a +load message to a class yourself.
// This method is called before the +initialize message is sent to the class, so you cannot depend on class initialisation
// having been performed, or upon other classes existing (apart from superclasses of the receiver, since +load is called
// on superclasses before it is called on their subclasses).
// As a gross generalisation, it is safe to use C code, including most ObjectiveC runtime functions within +load , but
// attempting to send messages to ObjectiveC objects is likely to fail.
+ (void)load;
// Initializes the class before it's used (before it receives its first message). The run-time
// system generates an +initialize message to each class just before the class, or any class that
// inherits from it, is sent its first message from within the program. Each class object receives
// the initialize message just once. Superclasses receive it before subclasses do.
+ (void)initialize;

// Creating, copying, and freeing instances ......................................................................

// Returns a new instance of the receiving class. The isa instance variable of the new object is initialized
// to a data structure that describes the class; memory for all other instance variables is set to O.
// A version of the init method should be used to complete the initialization process.
// WARN(naman): Other classes shouldn't override alloc to add code that initializes the new instance.
//      Instead, class-specific versions of the init method should be implemented for that purpose.
//      Versions of the +new method can also be implemented to combine allocation and initialization.
//      The +alloc method doesn't invoke +allocWithAllocator:. The two methods work independently.
+ (instancetype)alloc;
// Creates a new instance of the receiving class, sends it an -init message, and returns the
// initialized object returned by -init.
// As defined in the Object class, new is essentially a combination of +alloc and -init. Like
// +alloc, it initializes the isa instance variable of the new object so that it points to the class
// data structure. It then invokes the init method to complete the initialization process.
// Unlike +alloc, +new is sometimes reimplemented in subclasses to have it invoke a class-
// specific initialization method. If the -init method includes arguments, they're typically
// reflected in the +new method as well.
// WARN(naman): There's little point in implementing a +new method if it's simply a shorthand for
//              +alloc and -init. Often +new methods will do more than just allocation and initialization.
//              Therefore, implementing -init should suffice.
// NOTE(naman): In some classes, they manage a set of instances, returning the one with the requested properties
//              if it already exists, allocating and initializing a new one only if necessary.
//              Although it's appropriate to define new +new methods in this way, the +alloc methods should never
//              be augmented to include initialization code.
+ (instancetype)new;
// Returns a new instance that's an exact copy of the receiver. This method creates only one
// new object. If the receiver has instance variables that point to other objects, the instance
// variables in the copy will point to the same objects. The values of the instance variables
// are copied, but the objects they point to are not.
// This method does its work by invoking the -copyWithAllocator: method and specifying that
// the copy should be allocated from the same memory allocator as the receiver. If a subclass
// implements its own -copyWithAllocator: method, this -copy method will use it to copy
// instances of the subclass. Therefore, a class can support copying from both methods just
// by implementing a class-specific version of -copyWithAllocator:.
- (instancetype)copy;
// Returns nil. This method is implemented to prevent class objects, which are "owned" by
// the run-time system, from being accidentally freed. To free an instance, use the instance
// method -free.
+ (instancetype)free;
// Frees the memory occupied by the receiver and returns nil. Subsequent messages to the
// object will generate an error indicating that a message was sent to a freed object (provided
// that the freed memory hasn't been reused yet).
// Subclasses must implement their own versions of -free to deallocate any additional memory
// consumed by the object - such as dynamically allocated storage for data, or other objects
// that are tightly coupled to the freed object and are of no use without it. After performing
// the class-specific deallocation, the subclass method should incorporate superclass versions
// of -free through a message to super.
// If, under special circumstances, a subclass version of -free refuses to free the receiver, it
// should return self instead of nil. Object's default version of this method always frees the
// receiver and always returns nil.
- (instancetype)free [[clang::objc_requires_super]];

// Initializing a new instance ...................................................................................

// Implemented by subclasses to initialize a new object (the receiver) immediately after
// memory for it has been allocated. An -init message is generally coupled with an +alloc or
// +allocWithAllocator: message in the same line of code.
// An object isn't ready to be used until it has been initialized. The version of the -init method
// defined in the Object class does no initialization; it simply returns self.
// Subclass versions of this method should return the new object (self) after it has been
// successfully initialized. If it can't be initialized, they should free the object and return nil.
// In some cases, an -init method might free the new object and return a substitute. Programs
// should therefore always use the object returned by -init, and not necessarily the one returned
// by +alloc, in subsequent code.
// Every class must guarantee that the -init method returns a fully functional instance of the
// class. Typically this means overriding the method to add class-specific initialization code.
// Subclass versions of -init need to incorporate the initialization code for the classes they
// inherit from, through a message to super:
// Note that the message to super precedes the initialization code added in the method. This
// ensures that initialization proceeds in the order of inheritance.
// This -init method is the designated initializer for the Object class. Subclasses that do their
// own initialization should override it, as described above.
- (instancetype)init [[clang::objc_requires_super]];

// Identifying classes ...........................................................................................

// Returns a null-terminated string containing the name of the class. This information is often
// used in error messages or debugging statements.
+ (const Char*)name;
// Returns self. Since this is a class method, it returns the class object.
// When a class is the receiver of a message, it can be referred to by name. In all other cases,
// the class object must be obtained through this, or a similar method.
+ (Class)class;
// Returns the class object for the receiver's class.
- (Class)class;
// Returns the class object for the receiver's superclass.
+ (Class)superclass;
// Returns the class object for the receiver's superclass.
- (Class)superclass;

// Identifying and comparing instances ...........................................................................

// Returns true if the receiver is the same as arg_obj, and false if it isn't. This is determined
// by comparing the id of the receiver to the id of arg_obj.
// Subclasses may need to override this method to provide a different test of equivalence. For
// example, in some contexts, two objects might be said to be the same if they're both the same
// kind of object and they both contain the same data.
- (Bool)isEqual:(id)object;
// Returns an unsigned integer that's derived from the id of the receiver. The integer is
// guaranteed to always be the same for the same id.
- (Uint64)hash;
// Returns the receiver.
- (id)self;
// Implemented by subclasses to return a name associated with the receiver.
// By default, the string returned contains the name of the receiver's class. However, this
// method is commonly overridden to return a more object-specific name. You should
// therefore not rely on it to return the name of the class.
- (const Char*)name;

// Testing inheritance relationships .............................................................................

// Returns true if the receiver is an instance of `class` or an instance of any class that
// inherits from `class`. Otherwise, it returns false.
// When the receiver is a class object, this method returns true if a Class Object is the Object
// class, and false otherwise.
- (Bool)isKindOf:(Class)class;
// Returns true if the receiver is an instance of `classname` or an instance of any class that
// inherits from `classname`. This method is the same as isKindOf:, except it takes the class
// name, rather than the class id, as its argument.
- (Bool)isKindOfClassNamed:(const Char*)classname;
// Returns true if the receiver is an instance of `class`. Otherwise, it returns false.
- (Bool)isMemberOf:(Class)class;
// Returns true if the receiver is an instance of `classname`, and false if it isn't. This method
// is the same as isMemberOf:, except it takes the class name, rather than the class id, as
// its argument.
- (Bool)isMemberOfClassNamed:(const Char*)classname;

// Testing class functionality ...................................................................................

// Returns `true` if the receiver implements or inherits a method that can respond to `selector`
// messages, and `false` if it doesn't. The application is responsible for determining whether a
// `false` response should be considered an error.
// Note that if the receiver is able to forward `selector` messages to another object, it will be
// able to respond to the message, albeit indirectly, even though this method returns `false`.
+ (Bool)respondsTo:(SEL)op;
- (Bool)respondsTo:(SEL)op;
// Returns `true` if instances of the class are capable of responding to `selector` messages, and
// `false` if they're not. To ask the class whether it, rather than its instances, can respond to a
// particular message, use the `respondsTo:` instance method instead of `instancesRespondTo:`.
// If `selector` messages are forwarded to other objects, instances of the class will be able to
// receive those messages without error even though this method returns `false`.
+ (Bool)instancesRespondTo:(SEL)op;

// Testing for protocol conformance ..............................................................................

// Returns `true` if the receiving class conforms to `protocol`, and `false` if it doesn't.
// A class is said to "conform to" a protocol if it adopts the protocol or inherits from another
// class that adopts it. Protocols are adopted by listing them within angle brackets after the
// interface declaration. A class also conforms to any protocols that are incorporated in the protocols
// it adopts or inherits. Protocols incorporate other protocols in the same way that classes adopt them.
// When a class adopts a protocol, it must implement all the methods the protocol declares. If
// it adopts a protocol that incorporates another protocol, it must also implement all the
// methods in the incorporated protocol or inherit those methods from a class that adopts it.
// When these conventions are followed and all the methods in adopted and incorporated
// protocols are in fact implemented, the `conformsTo:` test for a set of methods becomes
// roughly equivalent to the `respondsTo:` test for a single method.
// However, `conformsTo:` judges conformance solely on the basis of the formal declarations
// in source code, as illustrated above. It doesn't check to see whether the methods declared
// in the protocol are actually implemented. It's the programmer's responsibility to see that
// they are. The `Protocol` object required as this method's argument can be specified using the
// @protocol directive.
+ (Bool)conformsTo:(Protocol *)protocol;
// Returns `true` if the class of the receiver conforms to `protocol`, and `true` if it doesn't. This
// method invokes the `conformsTo:` class method to do its work. It's provided as a
// convenience so that you don't need to get the class object to find out whether an instance
// can respond to a given set of messages.
- (Bool)conformsTo:(Protocol *)protocol;

// Obtaining method information ..................................................................................

// Locates and returns the address of the receiver's implementation of the `selector` method,
// so that it can be called as a function. If the receiver is an instance, `selector` should refer
// to an instance method; if the receiver is a class, it should refer to a class method.
// `selector` must be a valid, non-NULL selector. If in doubt, use the `respondsTo:` method to
// check before passing the selector to `methodFor:`.
+ (IMP)methodFor:(SEL)op;
- (IMP)methodFor:(SEL)op;
// Locates and returns the address of the implementation of the `selector` instance method.
// An error is generated if instances of the receiver can't respond to `selector` messages.
// This method is used to ask the class object for the implementation of an instance method.
// To ask the class for the implementation of a class method, use the instance method
// `methodFor:` instead of this one.
// `instanceMethodFor:`, and the function pointer it returns, are subject to the same
// constraints as those described for `methodFor:`.
+ (IMP)instanceMethodFor:(SEL)op;

// Enforcing intentions ..........................................................................................

// Used in the body of a method definition to indicate that the programmer intended to
// implement the method, but left it as a stub for the time being. `selector` is the selector for
// the unimplemented method; `notImplemented:` messages are sent to self. For example,
// `notImplemented:` can invoke the `error:` method.
+ (void)notImplemented:(SEL)op;
- (void)notImplemented:(SEL)op;
// Used in an abstract class to indicate that its subclasses are expected to implement `selector`
// methods. If a subclass fails to implement the method, it will inherit it from the abstract
// superclass. That version of the method generates an error when it's invoked. To avoid the
// error, subclasses must override the superclass method.
// Subclass implementations of the `selector` method shouldn't include messages to super to
// incorporate the superclass version. If they do, they'll also generate an error.
+ (void)subclassResponsibility:(SEL)op;
- (void)subclassResponsibility:(SEL)op;

// Error handling ................................................................................................

// Handles `selector` messages that the receiver doesn't recognize. The run-time system
// invokes this method whenever an object receives an `selector` message that it can't respond
// to or forward. This method, in turn, invokes the `error:` method to generate an error message
// and abort the current process.
// `doesNotRecognize:` messages should be sent only by the run-time system. Although
// they're sometimes used in program code to prevent a method from being inherited, it's
// better to use the `error:` method directly.
+ (void)doesNotRecognize:(SEL)op;
- (void)doesNotRecognize:(SEL)op;
// Generates a formatted error message, in the manner of `printf`, from `format` followed by
// a variable number of arguments.
// This method doesn't return. It calls the run-time `error(id, fmt, ...)` function, which
// first generates the error message and then calls `abort` to terminate the process.
- (void)error:(const Char *)format, ...;
@end

@interface Protocol : Object
{
@public
    const Char *name;
    struct ObjC__Protocol_List *protocol_list;
    struct ObjC__Method_Description_List *instance_methods;
    struct ObjC__Method_Description_List *class_methods;
}

// Obtaining attributes intrinsic to the protocol
- (const Char*) name;

// Testing protocol conformance
- (Bool) conformsTo:(Protocol *)protocol;

// Looking up information specific to a protocol
- (struct ObjC_Method_Description *) descriptionForInstanceMethod:(SEL)op;
- (struct ObjC_Method_Description *) descriptionForClassMethod:(SEL)op;
@end

#endif // OBJC_HEADER_GUARD

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////

# if defined(OBJC_IMPLEMENTATION)

// Type Definition ================================================================================================

typedef signed   long ObjC__Slong;
typedef unsigned long ObjC__Ulong;

typedef struct ObjC__Runtime {
    Hashmap string_map;

    Hashmap class_map;
    Hashmap protocol_map;
    Hashmap selector_seq_map;
    Uptr selector_sequence;

    Memory_Allocator_Interface *miface;
    OBJC_FORWARD_FUNC_DECL((*forward_func));

    Bool initialized;
} ObjC__Runtime;

typedef struct ObjC__Super_Reciever {
    id reciever;
    Char *super_class_name;
} ObjC__Super_Reciever;

typedef struct ObjC__Selector {
    Char *name;
    Uptr seq;
} ObjC__Selector;
static_assert(sizeof(ObjC__Selector) == (2 * sizeof(Char *)));

typedef struct ObjC__Ivar_List     ObjC__Ivar_List;
typedef struct ObjC__Method_List   ObjC__Method_List;
typedef struct ObjC__Protocol_List ObjC__Protocol_List;

typedef struct ObjC__Class {
    Class meta_class;
    Char *super_class_name;

    Char *name;

    union ObjC__Class_Ancillary_Data {
        struct {
            atomic_char initialization_status;
        };

        ObjC__Slong _ignore_version;
    } ancillary;
    static_assert(sizeof(union ObjC__Class_Ancillary_Data) == sizeof(ObjC__Slong));

    ObjC__Ulong info; // ObjC__Class_Info_flags
    ObjC__Slong instance_size;

    ObjC__Ivar_List *ivars; // NULL means no ivars. Does not include super class variables.

    ObjC__Method_List *instance_methods; // Linked list of instance methods (pre-filled, but does not include categories)
    ObjC__Method_List *class_methods; // meta_class->instance_methods, NULL by default

    // Inheritance hierarchy
    Class first_sub; // Pointer to the first child of the class hierarchy tree (points to the first subclass)
    Class next_peer; // Pointer to the next class on same level in the inheritance hierarchy

    ObjC__Protocol_List *protocols; // Protocols conformed to.

    void *unused;
} ObjC__Class;

typedef enum ObjC__Class_Info_Flags {
    // Compiler Generated
    ObjC__Class_Info_CLASS           = 0x1 << 0, // Type is class
    ObjC__Class_Info_META            = 0x1 << 1, // Type is metaclass
    ObjC__Class_Info_INITIALIZED     = 0x1 << 2, // Invoked +initialize
    ObjC__Class_Info_RESOLVED        = 0x1 << 3, // Correct super and sublinks assigned
    ObjC__Class_Info_IN_CONSTRUCTION = 0x1 << 4, // alloc’d but not exec’d
    // Custom
    ObjC__Class_Info_LOADED          = 0x1 << 5, // Invoked +load
} ObjC__Class_Info_Flags;
# define OBJC_CLS_GETINFO(cls,infomask)   ((cls)->info &   (ObjC__Ulong)ObjC__Class_Info_##infomask)
# define OBJC_CLS_SETINFO(cls,infomask)   ((cls)->info |=  (ObjC__Ulong)ObjC__Class_Info_##infomask)
# define OBJC_CLS_RESETINFO(cls,infomask) ((cls)->info &= ~(ObjC__Ulong)ObjC__Class_Info_##infomask)

typedef struct ObjC__Category {
    Char *name;
    union ObjC__Category_List {
        Char *name; // Class name, filled in by the compiler
        Class class; // Starts out as Char*, we replace it with Class
    } list;
    static_assert(sizeof(Char*) == sizeof(union ObjC__Category_List));
    ObjC__Method_List   *instance_methods;
    ObjC__Method_List   *class_methods;
    ObjC__Protocol_List *protocols;
} ObjC__Category;

typedef struct ObjC__Ivar {
    Char *name;
    Char *type; // Encoded as strings
    Uint offset; // Offset from the base address of the instance (in bytes)
} ObjC__Ivar;

struct ObjC__Ivar_List {
    Uint count;
    ObjC__Ivar list[];
};

typedef struct ObjC__Method {
    union ObjC__Method_Name {
        Char *str;
        // SEL sel; // TODO(naman): Test out selector interning
    } name;
    static_assert(sizeof(union ObjC__Method_Name) == sizeof(Char *));
    Char *type; // Description of the method's parameter list.
    IMP funcptr;
} ObjC__Method;

typedef struct ObjC__Method_List {
    ObjC__Method_List *next; // Single linked list (used when pointed to from ObjC__Class)
    Uint count;
    ObjC__Method list[];
} ObjC__Method_List;

typedef struct ObjC__Protocol_List {
    ObjC__Protocol_List *next;
    Size count;
    Protocol *list[];
} ObjC__Protocol_List;

typedef enum Objc__Type_Code {
    Objc__Type_Code_ID    = '@',
    Objc__Type_Code_CLASS = '#',
    Objc__Type_Code_SEL   = ':',

    Objc__Type_Code_S_CHAR_      = 'c',
    Objc__Type_Code_U_CHAR_      = 'C',
    Objc__Type_Code_S_SHORT_     = 's',
    Objc__Type_Code_U_SHORT_     = 'S',
    Objc__Type_Code_S_INT_       = 'i',
    Objc__Type_Code_U_INT_       = 'I',
    Objc__Type_Code_S_LONG_      = 'l',
    Objc__Type_Code_U_LONG_      = 'L',
    Objc__Type_Code_S_LONG_LONG_ = 'q',
    Objc__Type_Code_U_LONG_LONG_ = 'Q',

# if ENV_LANG_C >= 1999
    Objc__Type_Code_BOOL   = 'B',
# else
    Objc__Type_Code_BOOL   = Objc__Type_Code_S_CHAR_,
# endif
# if defined(__CHAR_UNSIGNED__)
    Objc__Type_Code_CHAR   = Objc__Type_Code_U_CHAR_,
# else
    Objc__Type_Code_CHAR   = Objc__Type_Code_S_CHAR_,
# endif
    Objc__Type_Code_BYTE   = Objc__Type_Code_U_CHAR_,
    Objc__Type_Code_SINT8  = Objc__Type_Code_S_CHAR_,
    Objc__Type_Code_UINT8  = Objc__Type_Code_U_CHAR_,
    Objc__Type_Code_SINT16 = Objc__Type_Code_S_SHORT_,
    Objc__Type_Code_UINT16 = Objc__Type_Code_U_SHORT_,
    Objc__Type_Code_SINT32 = Objc__Type_Code_S_INT_,
    Objc__Type_Code_UINT32 = Objc__Type_Code_U_INT_,
    Objc__Type_Code_SINT64 = Objc__Type_Code_S_LONG_LONG_,
    Objc__Type_Code_UINT64 = Objc__Type_Code_U_LONG_LONG_,

# if defined(ENV_BITWIDTH_32)
    Objc__Type_Code_UPTR   = Objc__Type_Code_UINT32,
    Objc__Type_Code_SPTR   = Objc__Type_Code_SINT32,
    Objc__Type_Code_SIZE   = Objc__Type_Code_UINT32,
# elif defined(ENV_BITWIDTH_64)
    Objc__Type_Code_UPTR   = Objc__Type_Code_UINT64,
    Objc__Type_Code_SPTR   = Objc__Type_Code_SINT64,
    Objc__Type_Code_SIZE   = Objc__Type_Code_UINT64,
# endif

    Objc__Type_Code_FLOAT32 = 'f',
    Objc__Type_Code_FLOAT64 = 'd',

    Objc__Type_Code_VOID     = 'v',
    Objc__Type_Code_PTR      = '^', // ^ type :: int* = ^i
    Objc__Type_Code_CHARPTR  = '*',
    Objc__Type_Code_BITFIELD = 'b', // b bit-offset type bitfield-size :: struct { float; int a:3; } => b32i3
    Objc__Type_Code_COMPLEX  = 'j', // j inner-type :: _Complex double => jd

    Objc__Type_Code_ARY_B    = '[', // [ element-count type ] :: int a[10] => [10i]
    Objc__Type_Code_ARY_E    = ']',
    Objc__Type_Code_UNION_B  = '(', // ( name-or-? = member-types ) :: union A {int i;} => (A=i)
    Objc__Type_Code_UNION_E  = ')',
    Objc__Type_Code_STRUCT_B = '{', // {name-or-? = member-types} :: struct {int i;int a:3,b:2;char c;} => {?=ib32i3b35i2c}
    Objc__Type_Code_STRUCT_E = '}',

    Objc__Type_Code_UNDEF = '?',

    // Used for distributed objects and RPC
    Objc__Type_Code_ARG_CONST  = 'r',
    Objc__Type_Code_ARG_IN     = 'n',
    Objc__Type_Code_ARG_INOUT  = 'N',
    Objc__Type_Code_ARG_OUT    = 'o',
    Objc__Type_Code_ARG_BYCOPY = 'O',
    Objc__Type_Code_RET_ONEWAY = 'V',
} Objc__Type_Code;

typedef struct ObjC__Method_Description {
    SEL name;
    Char *type;
} ObjC__Method_Description;

typedef struct ObjC__Method_Description_List {
    Uint count;
    ObjC__Method_Description list[];
} ObjC__Method_Description_List;

typedef struct ObjC__Static_Instances {
    Char *class_name;
    id instances[];
} ObjC__Static_Instances;

// Holds an array of pointers to the classes and categories defined in the module
typedef struct ObjC__Symbol_Table {
    ObjC__Ulong ref_count; // Initializes as zero, filled in by the runtime init
    ObjC__Selector *refs; // Terminated by a selector with NULL sel_id and sel_types (not typed as SEL since that is const)
    Uint16 class_count;
    Uint16 category_count;
    void *defs[]; // class_count of Class, then category_count of ObjC__Category*, then a NULL terminated array of ObjC__Static_Instances
} ObjC__Symbol_Table;

typedef struct ObjC__Module {
    union ObjC__Module_List_Element {
        struct ObjC__Module *next; // Used to setup the module list so that we can initialize stuff later
        struct ObjC__Module_Metadata { ObjC__Ulong version, size; } metadata;
    } list;
    static_assert(sizeof(union ObjC__Module_List_Element) == sizeof(struct ObjC__Module_Metadata));
    static_assert(sizeof(union ObjC__Module_List_Element) >= sizeof(struct ObjC__Module *));

    Char *filename;
    ObjC__Symbol_Table *symbol_table;
} ObjC__Module;
# if defined(ENV_OS_LINUX)
static_assert(sizeof(ObjC__Module) == 32);
# elif defined(ENV_OS_WINDOWS)
static_assert(sizeof(ObjC__Module) == 24);
# endif

typedef enum ObjC__Block_Field_Flags {
    ObjC__Block_Field_IS_OBJECT   =  3,  // id, NSObject, __attribute__((NSObject)), block, ...
    ObjC__Block_Field_IS_BLOCK    =  7,  // a block variable
    ObjC__Block_Field_IS_CAPTURED =  8,  // the on stack structure holding the __block variable
    ObjC__Block_Field_CALLER      = 128  // called from __block (capture) copy/dispose support routines
} ObjC__Block_Field_Flags;
# define OBJC_BLOCK_FIELD_TEST(v, f) (((v) & ObjC__Block_Field_##f) == ObjC__Block_Field_##f)

typedef enum ObjC__Block_Memory_Management_Flags {
    ObjC__Block_Memory_ON_HEAP   = (1 <<  8), // Copied to heap, use free()
    ObjC__Block_Memory_USE_FUNCS = (1 <<  9), // Use the copy and dispose function pointers in ObjC__Block_Object
    ObjC__Block_Memory_IS_GLOBAL = (1 << 12), // Declared globally, no memory management required
} ObjC__Block_Memory_Management_Flags;
# define OBJC_BLOCK_MEMORY_TEST(v, f) (((v) & ObjC__Block_Memory_##f) == ObjC__Block_Memory_##f)

typedef struct ObjC__Block_Object {
    void *isa;

    struct {
        // WARN(naman): The compiler generates these in the form of a single int, whose lower 16 bits serve to
        // store the reference-count, and the top 16 bits serve to store ObjC__Block_Memory_Management_Flags.
        // This means that this formatting will only work for 32/64-bit little endian platforms.
        // FIXME(naman): We never do atomic_init() for this, since we never have an opportunity to do that.
        atomic_short ref;
        Uint16 flags;
    };
    Sint _ignore0;

    void (*invoke)(void *, ...);

    struct {
        ObjC__Ulong _ignore0;
        ObjC__Ulong size;
        void (*init)(void *dst, void *src);
        void (*fini)(void *);
    } *descriptor;

    // NOTE(naman): Copied (NOT captured) variables of auto class are stored after this point.
} ObjC__Block_Object;
static_assert(sizeof(ObjC__Block_Object) == 32);

typedef struct ObjC__Block_Captured {
    void *isa;

    // Indirection to the active instance of these __block variables, used so that all access
    // to variable `a` can be like `captured.forwarding->a` instead of `captured.a`, so that
    // we can move __block variables from stack to heap seamlessly and have multiple blocks
    // access a single instance of them.
    struct ObjC__Block_Captured *forwarding;

    struct {
        // WARN(naman): The compiler generates these in the form of a single int, whose lower 16 bits serve to
        // store the reference-count, and the top 16 bits serve to store ObjC__Block_Memory_Management_Flags.
        // This means that this formatting will only work for 32/64-bit little endian platforms.
        // FIXME(naman): We never do atomic_init() for this, since we never have an opportunity to do that.
        atomic_short ref;
        Uint16 flags;
    };

    Sint size;

    void (*init)(struct ObjC__Block_Captured *dst, struct ObjC__Block_Captured *src);
    void (*fini)(struct ObjC__Block_Captured *);

    // NOTE(naman): Captured variables of __block class are stored after this point.
} ObjC__Block_Captured;
static_assert(sizeof(ObjC__Block_Captured) == 40);

// Runtime --------------------------------------------------------------------------------------------------------

// Global variable that contains all runtime information about the running Objective-C program
global_variable ObjC__Module  *GLOBAL__objc__module_list;
global_variable ObjC__Runtime *GLOBAL__objc__runtime_ptr;

pragma_clang("clang diagnostic push");
pragma_clang("clang diagnostic ignored \"-Wreserved-identifier\"");
global_variable void * _NSConcreteGlobalBlock[32];
global_variable void * _NSConcreteStackBlock[32];
global_variable void * _NSConcreteHeapBlock[32];
pragma_clang("clang diagnostic pop");

pragma_clang("clang diagnostic push");
pragma_clang("clang diagnostic ignored \"-Wunused-function\"");

internal_function
COMPARE_FUNC(objc_CompareString) {
    Bool result = strcmp(a, b);
    return result;
}

internal_function
ObjC__Method* objc_GetMethodFromEntireList (ObjC__Method_List *methods, SEL op)
{
    for (ObjC__Method_List *ml = methods; ml; ml = ml->next) {
        for (Uint i = 0; i < ml->count; i++) {
            ObjC__Method *method = &ml->list[i];
            if (objcSelIsSame(op, method->name.str)) {
                return method;
            }
        }
    }

    return nullptr;
}

internal_function
void objc_ClassInvokeLoadRecursive (Class cls)
{
    SEL load = @selector(load);

    for (ObjC__Method_List *ml = cls->class_methods; ml; ml = ml->next) {
        ObjC__Method *loadfunc = objc_GetMethodFromEntireList(ml, load);
        if (loadfunc) loadfunc->funcptr(cls, load);
    }

    OBJC_CLS_SETINFO(cls, LOADED);

    for (Class c = objcClsGetFirstSub(cls); c != Nil; c = objcClsGetNextPeer(c)) {
        objc_ClassInvokeLoadRecursive(c);
    }

    OBJC_CLS_SETINFO(cls, INITIALIZED);
}

internal_function
Char* objc_InternString (const Char *str)
{
    ObjC__Runtime *rt = GLOBAL__objc__runtime_ptr;

    Size len = strlen(str);
    Uint64 hash = hash64(str, len, 0);
    Char *result = hashmapSearch(&rt->string_map, hash, (Uint64)str);
    if (!result) {
        result = memIRequest(rt->miface, len + 1);
        memcpy(result, str, len + 1);
        hashmapInsert(&rt->string_map, hash, (Uint64)str, result);
    }
    return result;
}

Runtime objcLoad (Runtime runtime, Memory_Allocator_Interface *miface, OBJC_FORWARD_FUNC_DECL((*optional_forward_func)))
{
    // ObjC__Class_Info_IN_CONSTRUCTION is always set
    // Either ObjC__Class_Info_CLASS or ObjC__Class_Info_META is also set.

    debugAssert(GLOBAL__objc__runtime_ptr == nullptr);

    ObjC__Module *modlist = GLOBAL__objc__module_list;

    ObjC__Runtime *rt = runtime;
    if (rt == nullptr) {
        rt = memIRequest(miface, sizeof(*rt));
    }

    GLOBAL__objc__runtime_ptr = rt;
    debugAssert(GLOBAL__objc__runtime_ptr);

    if (rt->initialized == false) {
        debugAssert(miface);

        hashmapCreate(&rt->string_map,       objc_CompareString, miface, miface);
        hashmapCreate(&rt->class_map,        objc_CompareString, miface, miface);
        hashmapCreate(&rt->protocol_map,     objc_CompareString, miface, miface);
        hashmapCreate(&rt->selector_seq_map, objc_CompareString, miface, miface);

        rt->miface = miface;
        rt->forward_func = optional_forward_func;

        rt->initialized = true;
    } else {
        debugAssert(rt->miface == miface);
        debugAssert(rt->forward_func == optional_forward_func);
    }

    // First, register all selectors, classes, categories and protocols.
    for (ObjC__Module *mod = modlist; mod; mod = mod->list.next) {
        // Selectors ------------------------------------------------------------------------------
        ObjC__Symbol_Table *symtab = mod->symbol_table;

        for (symtab->ref_count = 0; ; symtab->ref_count++) {
            ObjC__Ulong i = symtab->ref_count;

            ObjC__Selector *sel = &symtab->refs[i];

            if (sel->name) {
                const Char *sel_name = objcSelGetName((SEL)sel);
                sel_name = objc_InternString(sel_name);

                Uint64 sel_name_hash = hash64(sel_name, strlen(sel_name), 0);

                Uptr stored_seq; {
                    void *ptr = hashmapSearch(&rt->selector_seq_map, sel_name_hash, (Uint64)sel_name);
                    stored_seq = (Uptr)ptr;
                }

                if (stored_seq) {
                    sel->seq = stored_seq;
                } else {
                    stored_seq = ++(rt->selector_sequence);
                    sel->seq = stored_seq;
                    hashmapInsert(&rt->selector_seq_map, sel_name_hash, (Uint64)sel_name, (void*)stored_seq);
                }
            } else {
                break;
            }
        }

        // Classes --------------------------------------------------------------------------------
        // NOTE(naman): Make a map of class name to class pointer
        Size    cls_count = symtab->class_count;
        Class    *cls_ptr = (Class*)&symtab->defs[0];

        for (Size i = 0; i < cls_count; i++) {
            Class cls = cls_ptr[i];

            atomic_init(&cls->ancillary.initialization_status, 0);

            const Char *cls_name = objcClsGetName(cls);
            cls_name = objc_InternString(cls_name);
            Uint64 cls_name_hash = hash64(cls_name, strlen(cls_name), 0);

            debugAssert(hashmapSearch(&rt->class_map, cls_name_hash, (Uint64)cls_name) == nullptr);
            hashmapInsert(&rt->class_map, cls_name_hash, (Uint64)cls_name, cls);

            for (ObjC__Protocol_List *list = cls->protocols; list != nullptr; list = list->next) {
                for (Size j = 0; j < list->count; j++) {
                    Protocol *proto = list->list[j];
                    const Char *proto_name = objcProtoGetName(proto);
                    proto_name = objc_InternString(proto_name);
                    if (objcProtoLookup(proto_name) == nullptr) {
                        Uint64 proto_hash = hash64(proto_name, strlen(proto_name), 0);
                        hashmapInsert(&rt->protocol_map, proto_hash, (Uint64)proto_name, proto);
                    }
                }
            }
        }

        // Categories -----------------------------------------------------------------------------
        // NOTE(naman): Make a map of category names and category pointers
        Size    cat_count = symtab->category_count;
        ObjC__Category **cat_ptr = (ObjC__Category**)&symtab->defs[cls_count];

        for (Size i = 0; i < cat_count; i++) {
            ObjC__Category *cat = cat_ptr[i];
            for (ObjC__Protocol_List *list = cat->protocols; list != nullptr; list = list->next) {
                for (Size j = 0; j < list->count; j++) {
                    Protocol *proto = list->list[j];
                    const Char *proto_name = objcProtoGetName(proto);
                    proto_name = objc_InternString(proto_name);
                    if (objcProtoLookup(proto_name) == nullptr) {
                        Uint64 proto_hash = hash64(proto_name, strlen(proto_name), 0);
                        hashmapInsert(&rt->protocol_map, proto_hash, (Uint64)proto_name, proto);
                    }
                }
            }
        }
    }

    Class root_class = Nil;

    // Then, set up links for super classes and subclasses, and class pointers for categories
    for (ObjC__Module *mod = modlist; mod; mod = mod->list.next) {
        ObjC__Symbol_Table *symtab = mod->symbol_table;

        Size    cls_count = symtab->class_count;
        Class    *cls_ptr = (Class*)&symtab->defs[0];
        Size    cat_count = symtab->category_count;
        ObjC__Category **cat_ptr = (ObjC__Category**)&symtab->defs[cls_count];

        // Classes
        for (Size i = 0; i < cls_count; i++) {
            Class cls = cls_ptr[i];

            cls->class_methods = cls->meta_class->instance_methods;

            if (cls->super_class_name) { // Non-root class
                Class supcls = objcClsGetSuper(cls);

                if (supcls->first_sub == Nil) {
                    supcls->first_sub = cls;
                } else {
                    Class last = supcls->first_sub;
                    while (last->next_peer) {
                        last = last->next_peer;
                    }
                    last->next_peer = cls;
                }
            } else { // Root class
                debugAssert(root_class == Nil);
                root_class = cls;
            }

            OBJC_CLS_RESETINFO(cls, IN_CONSTRUCTION);
            OBJC_CLS_SETINFO(cls, RESOLVED);
        }

        // Categories
        for (Size i = 0; i < cat_count; i++) {
            ObjC__Category *cat = cat_ptr[i];
            Class cls = objcClsLookup((const Char *)cat->list.class);
            cat->list.class = cls;
        }
    }

    // Then, add category methods to classes
    for (ObjC__Module *mod = modlist; mod; mod = mod->list.next) {
        ObjC__Symbol_Table *symtab = mod->symbol_table;

        Size    cls_count = symtab->class_count;
        Size    cat_count = symtab->category_count;
        ObjC__Category **cat_ptr = (ObjC__Category**)&symtab->defs[cls_count];

        for (Size i = 0; i < cat_count; i++) {
            ObjC__Category *cat = cat_ptr[i];
            Class cls = cat->list.class;
            if (cls) { // To skip the AnotherHack category with __ObjC_Protocol_Holder_Ugly_Hack class
                {
                    ObjC__Method_List *old_cls = cls->class_methods;
                    ObjC__Method_List *new_cls = cat->class_methods;
                    if (new_cls) {
                        cls->class_methods = new_cls;
                        debugAssert(new_cls->next == nullptr);
                        new_cls->next = old_cls;
                    }
                } {
                    ObjC__Method_List *old_ins = cls->instance_methods;
                    ObjC__Method_List *new_ins = cat->instance_methods;
                    if (new_ins) {
                        cls->instance_methods = new_ins;
                        debugAssert(new_ins->next == nullptr);
                        new_ins->next = old_ins;
                    }
                }
            }
        }
    }

    objc_ClassInvokeLoadRecursive(root_class);

    // Finally, deal with Static Instances
    for (ObjC__Module *mod = modlist; mod; mod = mod->list.next) {
        ObjC__Symbol_Table *symtab = mod->symbol_table;

        Size    cls_count = symtab->class_count;
        Size    cat_count = symtab->category_count;
        ObjC__Static_Instances **static_instances = symtab->defs[cls_count + cat_count];

        if (static_instances) {
            for (Size i = 0; static_instances[i]; i++) {
                ObjC__Static_Instances *stins = static_instances[i];

                Class cls = objcClsExpect(stins->class_name);

                for (Size j = 0; stins->instances[j]; j++) {
                    id obj = stins->instances[j];
                    obj->class_pointer = cls;
                }
            }
        }
    }

    return rt;
}

// Class ----------------------------------------------------------------------------------------------------------

const Char* objcClsGetName (Class cls)
{
    if (cls == Nil) return nullptr;
    Char *result = objc_InternString(cls->name);
    return result;
}

Class objcClsLookup (const Char* name)
{
    if (name == nullptr) return nullptr;

    ObjC__Runtime *rt = GLOBAL__objc__runtime_ptr;

    Uint64 name_hash = hash64(name, strlen(name), 0);
    static_assert(sizeof(Uint64) >= sizeof(Uptr));
    Class cls = hashmapSearch(&rt->class_map, name_hash, (Uint64)name);

    return cls;
}

Class objcClsExpect (const Char* name)
{
    if (name == nullptr) return nullptr;
    id cls = objcClsLookup(name);
    debugAssert(cls);
    return cls;
}

Class objcClsGetSuper (Class cls)
{
    if (cls == Nil) return Nil;
    const Char *supclsname = cls->super_class_name;
    Class supcls = objcClsLookup(supclsname);
    return supcls;
}

Class objcClsGetFirstSub (Class cls)
{
    if (cls == Nil) return Nil;
    Class sub = cls->first_sub;
    return sub;
}

Class objcClsGetNextPeer (Class cls)
{
    if (cls == Nil) return Nil;
    Class peer = cls->next_peer;
    return peer;
}

id objcClsCreateInstance (Class cls, Size extra_bytes)
{
    ObjC__Runtime *rt = GLOBAL__objc__runtime_ptr;

    if (cls == Nil) return nil;
    id obj = nil; {
        Size total_size = (Size)cls->instance_size + extra_bytes;
        obj = memIRequest(rt->miface, total_size);
        if (obj == nil) return nil;
        memset(obj, 0, total_size);
    } {
        obj->class_pointer = cls;
    }
    return obj;
}

Size objcClsGetInstanceSize (Class cls)
{
    if (cls == Nil) return 0;
    Size size = (Size)cls->instance_size;
    return size;
}

internal_function
ObjC__Ivar* objc_ClsGetField (Class cls, const Char *name)
{
    if (cls == Nil) return nullptr;
    ObjC__Ivar_List *ivars = cls->ivars;
    for (Uint i = 0; i < ivars->count; i++) {
        ObjC__Ivar *ivar = &(ivars->list[i]);
        if (streq(name, ivar->name)) {
            return ivar;
        }
    }

    Class supcls = objcClsGetSuper(cls);
    ObjC__Ivar *inherited = objc_ClsGetField(supcls, name);
    return inherited;
}

internal_function
void objc_ClsInitializeRecursive (Class cls)
{
    if (cls == Nil) {
        return;
    }

    const Char *clsname [[maybe_unused]] = objcClsGetName(cls);

    enum initialization_status { uninit = 0, initing, inited, };

    if (atomic_load(&cls->ancillary.initialization_status) == inited) {
        return;
    }

    Class supcls = objcClsGetSuper(cls);
    objc_ClsInitializeRecursive(supcls);

    { // Send +initialize the first time
        Char uninit_status = uninit; // Has to be char, since CAS does equivalent of memcmp for bitwise comparison
        if (atomic_compare_exchange_strong(&cls->ancillary.initialization_status, &uninit_status, initing) == true) {
            SEL initialize_sel = @selector(initialize);
            ObjC__Method *initialize = nullptr;
            // Go to the last +initialize method (to ensure we don't end up calling a Category's +initialize)
            for (ObjC__Method_List *ml = cls->class_methods; ml; ml = ml->next) {
                ObjC__Method *i = objc_GetMethodFromEntireList(ml, initialize_sel);
                if (i) initialize = i;
            }
            debugAssert(initialize);
            initialize->funcptr(cls, initialize_sel);

            atomic_exchange(&cls->ancillary.initialization_status, inited);
        }
        while (atomic_load(&cls->ancillary.initialization_status) != inited) { /* spin lock */ }
    }

    return;
}

internal_function
OBJC_METHOD_DECL(objc_MissingMethod)
{
    ObjC__Runtime *rt = GLOBAL__objc__runtime_ptr;

    va_list args;
    va_start(args, sel);

    id result = nil;
    if (rt->forward_func) {
        result = rt->forward_func(obj, sel, args);
    } else {
        debugBreak();
    }

    va_end(args);

    return result;
}

global_variable ObjC__Method GLOBAL_objc_missing_method = {
    .name.str    = "objc_MissingMethod",
# if defined(ENV_BITWIDTH_32)
    .type   = "I@:",
# elif defined(ENV_BITWIDTH_64)
    .type   = "Q@:",
# endif
    .funcptr = &objc_MissingMethod,
};

// WARN(naman): Only pass real classes here, not metaclasses or whatever
internal_function
ObjC__Method* objc_ClsGetMethod (Class cls, SEL op, Bool instance_method)
{
    if (cls == Nil) {
        return &GLOBAL_objc_missing_method;
    }
    const char *clsname [[maybe_unused]] = cls->name;

    if (OBJC_CLS_GETINFO(cls, LOADED) && !OBJC_CLS_GETINFO(cls, INITIALIZED)) {
        objc_ClsInitializeRecursive(cls);
    }

    {
        ObjC__Method_List *ml = instance_method ? cls->instance_methods : cls->class_methods;
        ObjC__Method *result = objc_GetMethodFromEntireList(ml, op);
        if (result) return result;
    }

    if (cls->super_class_name == nullptr) {
        return &GLOBAL_objc_missing_method;
    }

    Class supcls = objcClsGetSuper(cls);
    ObjC__Method *method = objc_ClsGetMethod(supcls, op, instance_method);
    return method;
}

Bool objcClsHasMethod (Class cls, SEL op, Bool instance_method)
{
    if (cls == Nil) return false;
    const char *clsname [[maybe_unused]] = cls->name;
    ObjC__Method *method = objc_ClsGetMethod(cls, op, instance_method);
    Bool result = (method != &GLOBAL_objc_missing_method);
    return result;
}

Bool objcClsConformsToProtocol (Class cls, Protocol *protocol)
{
    if (cls == Nil) return false;

    ObjC__Protocol_List *protos = cls->protocols;
    for (Size i = 0; i < protos->count; i++) {
        Protocol *proto = protos->list[i];
        if (proto == protocol) return true;
    }

    Class supcls = objcClsGetSuper(cls);
    Bool result = objcClsConformsToProtocol(supcls, protocol);
    return result;
}

// Object ---------------------------------------------------------------------------------------------------------

Class objcObjGetClass (id obj)
{
    Class cls = obj->class_pointer;
    return cls;
}

void objcObjDispose (id obj)
{
    ObjC__Runtime *rt = GLOBAL__objc__runtime_ptr;
    memIRescind(rt->miface, obj);
}

id objcObjCopy (id src_obj, Size extra_bytes)
{
    Class cls = objcObjGetClass(src_obj);

    id dst_obj = objcClsCreateInstance(cls, extra_bytes);

    Size root_size = objcClsGetInstanceSize([Object class]);
    Size cls_size  = (Size)cls->instance_size;
    debugAssert(cls_size >= root_size);
    Size ivar_size = cls_size - root_size;

    if (ivar_size > 0) {
        void *src_ivar_ptr = (Byte*)src_obj + sizeof(Object);
        void *dst_ivar_ptr = (Byte*)dst_obj + sizeof(Object);
        memcpy(dst_ivar_ptr, src_ivar_ptr, ivar_size);
    }

    return dst_obj;
}

// Selector -------------------------------------------------------------------------------------------------------

const Char* objcSelGetName (SEL op)
{
    Char *result = objc_InternString(op->name);
    return result;
}

Bool objcSelIsEqual (SEL a, SEL b)
{
    if (!a) return false;
    if (!b) return false;
    Bool result = a->seq == b->seq;
    return result;
}

Bool objcSelIsSame (SEL a, const Char *b_name)
{
    ObjC__Runtime *rt = GLOBAL__objc__runtime_ptr;

    Uint64 b_name_hash = hash64(b_name, strlen(b_name), 0);
    Uptr b_seq; {
        void *ptr = hashmapSearch(&rt->selector_seq_map, b_name_hash, (Uint64)b_name);
        b_seq = (Uptr)ptr;
    }
    Bool result = (a->seq == b_seq);
    return result;
}

// Method ---------------------------------------------------------------------------------------------------------

internal_function
const Char* objc_MethodGetName (ObjC__Method *method)
{
    return method->name.str;
}

internal_function
const Char* objc_MethodGetType (ObjC__Method *method)
{
    return method->type;
}

internal_function
IMP objc_MethodGetImp (ObjC__Method *method)
{
    IMP impl = method->funcptr;
    return impl;
}

internal_function
IMP objc_MethodSetImp (ObjC__Method *method, IMP imp)
{
    IMP old_imp = method->funcptr;
    method->funcptr = imp;
    return old_imp;
}

// Instance Variables ---------------------------------------------------------------------------------------------

internal_function
const Char* objc_IvarGetName (ObjC__Ivar *ivar)
{
    return ivar->name;
}

internal_function
Size objc_IvarGetOffset (ObjC__Ivar *ivar)
{
    Size offset = ivar->offset;
    return offset;
}

internal_function
const Char* objc_IvarGetType (ObjC__Ivar *ivar)
{
    return ivar->type;
}

// Protocol -------------------------------------------------------------------------------------------------------

pragma_clang("clang diagnostic push");
pragma_clang("clang diagnostic ignored \"-Wdirect-ivar-access\"");

const Char* objcProtoGetName (Protocol *proto)
{
    Char *result = objc_InternString(proto->name);
    return result;
}

Protocol* objcProtoExpect (const Char *name)
{
    if (name == nullptr) return nullptr;
    Protocol *proto = objcProtoLookup(name);
    debugAssert(proto);
    return proto;
}

Protocol* objcProtoLookup (const Char *name)
{
    if (name == nullptr) return nullptr;

    ObjC__Runtime *rt = GLOBAL__objc__runtime_ptr;

    Uint64 name_hash = hash64(name, strlen(name), 0);
    static_assert(sizeof(Uint64) >= sizeof(Uptr));

    Protocol *proto = hashmapSearch(&rt->protocol_map, name_hash, (Uint64)name);
    return proto;
}

Bool objcProtoConformsToProtocol (Protocol *proto, Protocol *other)
{
    if (proto == nullptr) return false;
    if (other == nullptr) return false;

    if (objcProtoIsEqual(proto, other)) return true;

    ObjC__Protocol_List *protolists = proto->protocol_list;
    if (protolists == nullptr) return false;

    for (ObjC__Protocol_List *pl = protolists; pl; pl = pl->next) {
        for (Size i = 0; i < pl->count; i++) {
            Protocol *p = pl->list[i];
            if (objcProtoConformsToProtocol((Protocol*)p, other)) {
                return true;
            }
        }
    }

    return false;
}

Bool objcProtoIsEqual (Protocol *proto, Protocol *other)
{
    if (proto == nullptr) return false;
    if (other == nullptr) return false;

    Bool result = streq(objcProtoGetName(proto), objcProtoGetName(other));
    return result;
}

internal_function
ObjC__Method_Description objc_ProtoGetMethodDescription (Protocol *proto, SEL op, Bool instance_method)
{
    ObjC__Method_Description EMPTY = {};

    if (proto == nullptr) return EMPTY;
    if (op == nullptr) return EMPTY;

    ObjC__Method_Description_List *methods = nullptr;

    if (instance_method) {
        methods = proto->instance_methods;
    } else {
        methods = proto->class_methods;
    }

    if (methods) {
        for (Size i = 0; i < methods->count; i++) {
            ObjC__Method_Description *desc = &methods->list[i];
            if (objcSelIsEqual(desc->name, op)) {
                return *desc;
            }
        }
    }

    ObjC__Protocol_List *protolists = proto->protocol_list;
    if (protolists) {
        for (ObjC__Protocol_List *pl = protolists; pl; pl = pl->next) {
            for (Size i = 0; i < pl->count; i++) {
                Protocol *p = pl->list[i];

                ObjC__Method_Description result = objc_ProtoGetMethodDescription(p, op, instance_method);
                if (result.name) {
                    return result;
                }
            }
        }
    }

    return EMPTY;
}

SEL objcProtoGetMethodName (Protocol *proto, SEL op, Bool instance_method)
{
    ObjC__Method_Description desc = objc_ProtoGetMethodDescription(proto, op, instance_method);
    return desc.name;
}

const Char* objcProtoGetMethodType (Protocol *proto, SEL op, Bool instance_method)
{
    ObjC__Method_Description desc = objc_ProtoGetMethodDescription(proto, op, instance_method);
    return objc_InternString(desc.type);
}

pragma_clang("clang diagnostic pop");

// Block ----------------------------------------------------------------------------------------------------------

header_function
Bool objc_BlockCompareExchange (Sint16 old, Sint16 new, atomic_short *dst)
{
    Sint16 expected = old;
    Bool result = atomic_compare_exchange_strong(dst, &expected, new);
    return result;
}

header_function
Sint16 objc_BlockIncrementReference (atomic_short *where)
{
    while (true) {
        Sint16 old_value = atomic_load(where);
        if (old_value == 0x7FFF) return 0x7FFF;
        if (objc_BlockCompareExchange(old_value, old_value+1, where)) {
            return old_value+1;
        }
    }
}

header_function
Sint16 objc_BlockDecrementReference (atomic_short *where)
{
    while (true) {
        Sint16 old_value = atomic_load(where);
        if (old_value == 0x7FFF) return 0x7FFF;
        if (old_value == 0) return 0;
        if (objc_BlockCompareExchange(old_value, old_value-1, where)) {
            return old_value-1;
        }
    }
}

header_function
void objc_BlockMemMove (void *dst, void *src, Size size)
{
    ObjC__Runtime *rt = GLOBAL__objc__runtime_ptr;
    void *buffer = memIRequest(rt->miface, size);
    memcpy(buffer, src, size);
    memcpy(dst, buffer, size);
    memIRescind(rt->miface, buffer);
}

// Called for each variable in a ObjC__Block_Captured
internal_function
void objc_BlockVariableCopy(void **capture_slot, void *captured_value, int flags)
{
    if (OBJC_BLOCK_FIELD_TEST(flags, CALLER)) { // Internal calls
        *capture_slot = captured_value;
    } else if (OBJC_BLOCK_FIELD_TEST(flags, IS_CAPTURED)) { // Copying a __block variable from the stack Block to the heap
        ObjC__Runtime *rt = GLOBAL__objc__runtime_ptr;

        ObjC__Block_Captured **slot = (ObjC__Block_Captured **)capture_slot;
        ObjC__Block_Captured  *src  = captured_value;

        if (atomic_load(&src->forwarding->ref) == 0) { // Currently on stack
            ObjC__Block_Captured *copy = memIRequest(rt->miface, (size_t)src->size);
            *copy = (typeof(*copy)) {
                .flags = ObjC__Block_Memory_ON_HEAP | src->flags,
                .forwarding = copy,
                .size = src->size,
            };
            atomic_init(&copy->ref, 2);

            src->forwarding = copy;  // Variables moved to heap, so read from there

            if (src->flags & ObjC__Block_Memory_USE_FUNCS) {
                copy->init = src->init;
                copy->fini = src->fini;
                (*src->init)(copy, src);
            } else {
                // NOTE(naman): This copies the last two function pointers and all the subsequent data
                Size size = (Size)src->size - (sizeof(ObjC__Block_Captured) - (2 * sizeof(void*)));
                objc_BlockMemMove(&copy->init, &src->init, size);
            }
        } else if (OBJC_BLOCK_MEMORY_TEST(src->forwarding->flags, ON_HEAP)) { // Already on heap
            objc_BlockIncrementReference(&src->forwarding->ref);
        } else {
            debugBreak(); // Has to be either on stack or on heap
        }

        // Store either the original `forwarding` pointer or
        // the newly allocated `copy` pointer (that is not in scope anymore).
        *slot = src->forwarding;
    } else if (OBJC_BLOCK_FIELD_TEST(flags, IS_BLOCK)) { // Check for Block before checking for Object
        *capture_slot = objcBlockCopyFunc(captured_value);
    } else if (OBJC_BLOCK_FIELD_TEST(flags, IS_OBJECT)) {
        *capture_slot = captured_value;
    }
}

// Called for each variable in a ObjC__Block_Captured
internal_function
void objc_BlockVariableFree(ObjC__Block_Captured *captured, int flags)
{
    if (flags & ObjC__Block_Field_IS_CAPTURED)  {
        captured = captured->forwarding;
        if ((captured->flags & ObjC__Block_Memory_ON_HEAP) == 0) return;
        if (atomic_load(&captured->ref) <= 0) {
            // Reference count underflowed
            debugBreak();
        } else if (objc_BlockDecrementReference(&captured->ref) == 0) {
            ObjC__Runtime *rt = GLOBAL__objc__runtime_ptr;

            if (captured->flags & ObjC__Block_Memory_USE_FUNCS) {
                (*captured->fini)(captured);
            }
            memIRescind(rt->miface, captured);
        }
    } else if ((flags & (ObjC__Block_Field_IS_BLOCK|ObjC__Block_Field_CALLER)) == ObjC__Block_Field_IS_BLOCK) {
        objcBlockFreeFunc(captured);
    }
}

void *objcBlockCopyFunc (void *arg)
{
    if (!arg) return NULL;

    ObjC__Block_Object *block = arg;

    if (block->flags & ObjC__Block_Memory_ON_HEAP) {
        objc_BlockIncrementReference(&block->ref);
        return block;
    } else if (block->flags & ObjC__Block_Memory_IS_GLOBAL) {
        return block;
    } else { // On stack (so copy it to heap)
        ObjC__Runtime *rt = GLOBAL__objc__runtime_ptr;

        ObjC__Block_Object *result = memIRequest(rt->miface, block->descriptor->size);
        debugAssert(result);
        objc_BlockMemMove(result, block, block->descriptor->size);
        atomic_init(&result->ref, 1);
        result->flags |= ObjC__Block_Memory_ON_HEAP;
        result->isa = _NSConcreteHeapBlock;
        if (result->flags & ObjC__Block_Memory_USE_FUNCS) {
            (*block->descriptor->init)(result, block);
        }
        return result;
    }
}

void objcBlockFreeFunc(void *arg)
{
    if (!arg) return;

    ObjC__Block_Object *block = arg;

    Sint16 refcount = objc_BlockDecrementReference(&block->ref);

    if (refcount > 0) return;

    if (block->flags & ObjC__Block_Memory_ON_HEAP) {
        if (block->flags & ObjC__Block_Memory_USE_FUNCS) {
            (*block->descriptor->fini)(block);
        }
        ObjC__Runtime *rt = GLOBAL__objc__runtime_ptr;
        memIRescind(rt->miface, block);
    } else if (block->flags & ObjC__Block_Memory_IS_GLOBAL) {
        // Do nothing
    } else {
        // Free called on a stack block
        debugBreak();
    }
}

// Internal Implementation (compiler generates calls to these functions -------------------------------------------

// NOTE(naman): These functions are generated by the Clang compiler, thus their naming scheme is different.
// WARN(naman): Don't call these functions directly.
pragma_clang("clang diagnostic push");
pragma_clang("clang diagnostic ignored \"-Wreserved-identifier\"");
pragma_clang("clang diagnostic ignored \"-Wmissing-prototypes\"");
pragma_clang("clang diagnostic ignored \"-Wincompatible-pointer-types-discards-qualifiers\"");

void __objc_exec_class (ObjC__Module *module) // Called automatically for each module before calling main
{
    debugAssert(module->list.metadata.size == sizeof(ObjC__Module));
    debugAssert(module->list.metadata.version == 8);

    ObjC__Module *mod = GLOBAL__objc__module_list;

    if (mod) {
        while (mod->list.next) mod = mod->list.next;
        mod->list.next = module;
        mod = mod->list.next;
    } else {
        mod = module;
        GLOBAL__objc__module_list = mod;
    }
    mod->list.next = nullptr;
}

Class objc_lookup_class (const Char* name) // Called to get class pointer from class name
{
    ObjC__Runtime *rt = GLOBAL__objc__runtime_ptr;
    debugAssert(rt);
    debugAssert(rt->initialized);

    if (name == nullptr) return Nil;

    Uint64 name_hash = hash64(name, strlen(name), 0);
    Class cls = hashmapSearch(&rt->class_map, name_hash, (Uint64)name);
    debugAssert(cls);
    objc_ClsInitializeRecursive(cls);
    return cls;
}

IMP objc_msg_lookup (id obj, SEL op) // Get method implementation from selector
{
    ObjC__Runtime *rt = GLOBAL__objc__runtime_ptr;
    debugAssert(rt);
    debugAssert(rt->initialized);

    Class cls = Nil;
    const char *clsname [[maybe_unused]] = nullptr;

    if (obj) {
        cls = obj->class_pointer;
        clsname = cls->name;
    }

    Bool instance_methods = true;
    if (OBJC_CLS_GETINFO(cls, META)) {
        cls = objcClsLookup(cls->name);
        clsname = cls->name;
        instance_methods = false;
    }

    ObjC__Method *method = objc_ClsGetMethod(cls, op, instance_methods);
    return method->funcptr;
}

IMP objc_msg_lookup_super (ObjC__Super_Reciever *super, SEL op) // Get method implementation from selector for [super ...]
{
    ObjC__Runtime *rt = GLOBAL__objc__runtime_ptr;
    debugAssert(rt);
    debugAssert(rt->initialized);

    Class cls = Nil;
    const char *clsname = nullptr;

    if (super) {
        cls = objcClsLookup(super->super_class_name);
        clsname = cls->name;
    }

    Bool instance_methods = true;
    if (OBJC_CLS_GETINFO(cls, META)) {
        cls = objcClsLookup(clsname);
        clsname = cls->name;
        instance_methods = false;
    }

    ObjC__Method *method = objc_ClsGetMethod(cls, op, instance_methods);
    return method->funcptr;
}

// Called for each variable in a ObjC__Block_Captured
// When ObjC__Block_Object or ObjC__Block_Captured hold objects,
// then their `copy` routine helpers use this entry point to do the assignment.
void _Block_object_assign(void *dest_addr, const void *object, const int flags)
{
    objc_BlockVariableCopy(dest_addr, object, flags);
}

// Called for each variable in a ObjC__Block_Captured
// When ObjC__Block_Object or ObjC__Block_Captured hold objects,
// their `free` helper routines call this entry point to help dispose of the contents.
// Used initially only for __attribute__((NSObject)) marked pointers.
void _Block_object_dispose(const void *object, const int flags)
{
    objc_BlockVariableFree(object, flags);
}

pragma_clang("clang diagnostic pop");

pragma_clang("clang diagnostic pop");

pragma_clang("clang diagnostic push");
pragma_clang("clang diagnostic ignored \"-Wobjc-messaging-id\"");
pragma_clang("clang diagnostic ignored \"-Wdirect-ivar-access\"");

@implementation Object

// Initializing the class ........................................................................................

+ (void)load {}
+ (void)initialize {}

// Creating, copying, and freeing instances ......................................................................

+ (instancetype)alloc {
    id obj = objcClsCreateInstance(self, 0);
    return obj;
}
+ (instancetype)new {
    id obj = [[self alloc] init];
    return obj;
}
- (instancetype)copy {
    id new = objcObjCopy(self, 0);
    return new;
}
+ (instancetype)free {
    return nil;
}
- (instancetype)free {
    objcObjDispose(self);
    return nil;
}

// Initializing a new instance ...................................................................................

- (instancetype)init {
    return self;
}

// Identifying classes ...........................................................................................

+ (const Char*)name {
    const Char *name = objcClsGetName(self);
    return name;
}
+ (Class)class {
    Class cls = objcClsLookup([self name]);
    return cls;
}
- (Class)class {
    Class cls = objcObjGetClass(self);
    return cls;
}
+ (Class)superclass {
    Class cls = [self class];
    Class supcls = objcClsGetSuper(cls);
    return supcls;
}
- (Class)superclass {
    Class cls = objcObjGetClass(self);
    Class supcls = objcClsGetSuper(cls);
    return supcls;
}

// Identifying and comparing instances ...........................................................................

- (Bool)isEqual:(id)other_obj {
    id obj = self;
    Bool equal = (obj == other_obj);
    return equal;
}
- (Uint64)hash {
    id obj = self;
    static_assert(sizeof(obj) == sizeof(Uptr));
    Uptr ptr = (Uptr)obj;
    static_assert(sizeof(ptr) == sizeof(Uint64));
    Uint64 hash = ptr;
    return hash;
}
- (id)self {
    id obj = self;
    return obj;
}
- (const Char*)name {
    Class cls = objcObjGetClass(self);
    const Char *name = objcClsGetName(cls);
    return name;
}

// Testing inheritance relationships .............................................................................

- (Bool)isKindOf:(Class)other_class {
    Class cls = objcObjGetClass(self);
    while (cls) {
        if (other_class == cls) return true;
        cls = objcClsGetSuper(cls);
    }
    return false;
}
- (Bool)isKindOfClassNamed:(const Char*)name {
    id obj = self;
    Class class = objcClsLookup(name);
    Bool result = [obj isKindOf:class];
    return result;
}
- (Bool)isMemberOf:(Class)other_class {
    Class cls = objcObjGetClass(self);
    Bool result = (cls == other_class);
    return result;
}
- (Bool)isMemberOfClassNamed:(const Char*)name {
    Class named_class = objcClsLookup(name);
    Class cls = objcObjGetClass(self);
    Bool result = (cls == named_class);
    return result;
}

// Testing class functionality ...................................................................................

+ (Bool)respondsTo:(SEL)op {
    Class cls = [self class];
    Bool result = objcClsHasMethod(cls, op, false);
    return result;
}

- (Bool)respondsTo:(SEL)op {
    Bool result = objcClsHasMethod(class_pointer, op, true);
    return result;
}

+ (Bool)instancesRespondTo:(SEL)op {
    Class cls = [self class];
    Bool result = objcClsHasMethod(cls, op, true);
    return result;
}

// Testing for protocol conformance ..............................................................................

+ (Bool)conformsTo:(Protocol *)proto {
    Class cls = [self class];
    Bool result = objcClsConformsToProtocol(cls, proto);
    return result;
}
- (Bool)conformsTo:(Protocol *)proto {
    Class cls = objcObjGetClass(self);
    Bool result = objcClsConformsToProtocol(cls, proto);
    return result;
}

// Sending messages determined at run time .......................................................................

- (id)perform:(SEL)op, ... {
    va_list args;
    va_start(args, op);
    id result = [self performv:op :args];
    va_end(args);
    return result;
}
- (id)performv:(SEL)op :(va_list)args {
    Class cls = objcObjGetClass(self);
    ObjC__Method *method = objc_ClsGetMethod(cls, op, true);
    id result = method->funcptr(self, op, args);
    return result;
}

// Forwarding messages ...........................................................................................

- (Uptr)forward:(SEL)op, ... {
    va_list args;
    va_start(args, op);

    Uptr result = 0;
    //result = [self performv:op args]; // Implementations in the subclass will do something like this
    [self doesNotRecognize:_cmd];

    va_end(args);
    return result;
}

// Obtaining method information ..................................................................................

+ (IMP)methodFor:(SEL)op {
    Class cls = [self class];
    IMP imp = objc_msg_lookup(cls, op);
    return imp;
}
- (IMP)methodFor:(SEL)op {
    id obj = self;
    IMP imp = objc_msg_lookup(obj, op);
    return imp;
}
+ (IMP)instanceMethodFor:(SEL)op {
    Class cls = [self class];
    ObjC__Method *method = &GLOBAL_objc_missing_method;
    if (cls != nil) {
        const char *clsname [[maybe_unused]] = cls->name;
        method = objc_ClsGetMethod(cls, op, true);
    }
    return method->funcptr;
}

// Enforcing intentions ..........................................................................................

+ (void)notImplemented:(SEL)op {
    Class cls = [self class];
    [self error:"%s method not found in class %s" , op->name, cls->name];
}
- (void)notImplemented:(SEL)op {
    [self error:"%s method not found in class %s" , op->name, class_pointer->name];
}
+ (void)subclassResponsibility:(SEL)op {
    Class cls = [self class];
    [self error:"%s method should have been implemented in a subclass of %s" , op->name, cls->name];
}
- (void)subclassResponsibility:(SEL)op {
    [self error:"%s method should have been implemented in a subclass of %s" , op->name, class_pointer->name];
}

// Error handling ................................................................................................

+ (void)doesNotRecognize:(SEL)op {
    Class cls = [self class];
    [self error:"%s method not found in class %s" , op->name, cls->name];
}
- (void)doesNotRecognize:(SEL)op {
    [self error:"%s method not found in class %s" , op->name, class_pointer->name];
}
- (void)error:(const Char *)format, ... {
    debugBreak();
}

@end

pragma_clang("clang diagnostic pop");

#endif // OBJC_IMPLEMENTATION