// This is a personal academic project. Dear PVS-Studio, please check it.
// PVS-Studio Static Code Analyzer for C, C++, C#, and Java: https://pvs-studio.com
/*********************************************************************
 Intermediate code generator for COOL: SKELETON

 Read the comments carefully and add code to build an LLVM program
*********************************************************************/

#define EXTERN
#include "cgen.h"

#include <cmath>
#include <sstream>
#include <string>
#include <llvm/Support/FileSystem.h>

// special assert that allows debugging to continue
// https://nullprogram.com/blog/2024/01/28/
#ifdef _MSC_VER
#undef assert
#define assert(c) do if (!(c)) { fprintf(stderr, "Assertion %s failed [%d]\n", #c, __LINE__); __debugbreak(); } while (0)
#define assertm(c, msg) do if (!(c)) { fprintf(stderr, "Assertion %s failed [%d]: %s\n", #c, __LINE__, msg); __debugbreak(); } while (0)
#elif defined __x86_64__
#undef assert
#define assert(c) do if (!(c)) { fprintf(stderr, "Assertion %s failed [%d]\n", #c, __LINE__); asm ("int3; nop"); } while (0)
#define assertm(c, msg) do if (!(c)) { fprintf(stderr, "Assertion %s failed [%d]: %s\n", #c, __LINE__, msg); asm ("int3; nop"); } while (0)
#endif


extern int cgen_debug, curr_lineno;
using namespace llvm;
/*********************************************************************
 For convenience, a large number of symbols are predefined here.
 These symbols include the primitive type and method names, as well
 as fixed names used by the runtime system. Feel free to add your
 own definitions as you see fit.
*********************************************************************/
EXTERN Symbol
    // required classes
    Object,
    IO, String, Int, Bool, Main,

    // class methods
    cool_abort, type_name, cool_copy, out_string, out_int, in_string, in_int,
    length, concat, substr,

    // class members
    val,

    // special symbols
    No_class, // symbol that can't be the name of any user-defined class
    No_type, // If e : No_type, then no code is generated for e.
    SELF_TYPE, // Special code is generated for new SELF_TYPE.
    self, // self generates code differently than other references

    // extras
    arg, arg2, newobj, Mainmain, prim_string, prim_int, prim_bool;

namespace
{
std::string as_string(Symbol) __attribute((pure));

std::vector<Expression> unfuck(Expressions) __attribute((pure));

std::vector<Formal> unfuck(Formals) __attribute((pure));

std::vector<Feature> unfuck(Features) __attribute((pure));

std::pair<Type*, Value*> resolve_opaque(Value*) __attribute((pure));

std::pair<std::string, std::string> split(const std::string&, char) __attribute((pure));

template<class T, class R>
std::vector<R> map(std::vector<T> src, std::function<R(T const &)> mapper) __attribute((pure, optimize("O3")));

    
// Initializing the predefined symbols.
void initialize_constants()
{
    Object = idtable.add_string("Object");
    IO = idtable.add_string("IO");
    String = idtable.add_string("String");
    Int = idtable.add_string("Int");
    Bool = idtable.add_string("Bool");
    Main = idtable.add_string("Main");

    cool_abort = idtable.add_string("abort");
    type_name = idtable.add_string("type_name");
    cool_copy = idtable.add_string("copy");
    out_string = idtable.add_string("out_string");
    out_int = idtable.add_string("out_int");
    in_string = idtable.add_string("in_string");
    in_int = idtable.add_string("in_int");
    length = idtable.add_string("length");
    ::concat = idtable.add_string("concat");
    substr = idtable.add_string("substr");

    val = idtable.add_string("val");

    No_class = idtable.add_string("_no_class");
    No_type = idtable.add_string("_no_type");
    SELF_TYPE = idtable.add_string("SELF_TYPE");
    self = idtable.add_string("self");

    arg = idtable.add_string("arg");
    arg2 = idtable.add_string("arg2");
    newobj = idtable.add_string("_newobj");
    Mainmain = idtable.add_string("main");
    prim_string = idtable.add_string("sbyte*");
    prim_int = idtable.add_string("int");
    prim_bool = idtable.add_string("bool");
}
}

#pragma region "CgenClassTable"
// CgenClassTable constructor orchestrates all code generation
CgenClassTable::CgenClassTable(Classes classes)
    : nds(), current_tag(0), context(), builder(this->context),
      the_module(stringtable.get_file(), this->context), di_builder(the_module)
{
    if (cgen_debug)
        std::cerr << "Building CgenClassTable" << std::endl;

    i1 = Type::getInt1Ty(this->context);
    i8 = Type::getInt8Ty(this->context);
    i32 = Type::getInt32Ty(this->context);
    ptr = i8->getPointerTo();
    void_ = Type::getVoidTy(this->context);

    #ifdef EMIT_DBG
    the_module.addModuleFlag(Module::Warning, "Debug Info Version", DEBUG_METADATA_VERSION);

    di_file = di_builder.createFile(stringtable.get_file(), ".");
    di_cu = di_builder.createCompileUnit(dwarf::DW_LANG_C, di_file, "ibn222_ece479k_lab2",
        false, (cgen_debug) ? "-d" : "", 0);

    di1 = di_builder.createBasicType("bool", 1, dwarf::DW_ATE_signed);
    di8 = di_builder.createBasicType("cbool", 8, dwarf::DW_ATE_signed);
    di32 = di_builder.createBasicType("int", 32, dwarf::DW_ATE_signed);
    dptr = di_builder.createPointerType(di8, 64, 0, std::nullopt, "opaque_ptr");
    dvoid = di_builder.createNullPtrType();
    #endif


    // Make sure we have a scope, both for classes and for constants
    enterscope();

    // Create an inheritance tree with one CgenNode per class.
    install_basic_classes();
    install_classes(classes);
    build_inheritance_tree();

    // First pass
    setup();

    // Second pass
    code_module();
    // Done with code generation: exit scopes
    exitscope();

    #ifdef EMIT_DBG
    // finalize debug info
    di_builder.finalize();
    #endif
}

// Creates AST nodes for the basic classes and installs them in the class list
void CgenClassTable::install_basic_classes()
{
    // The tree package uses these globals to annotate the classes built below.
    curr_lineno = 0;
    Symbol filename = stringtable.add_string("<basic class>");

    //
    // A few special class names are installed in the lookup table but not
    // the class list. Thus, these classes exist, but are not part of the
    // inheritance hierarchy.

    // No_class serves as the parent of Object and the other special classes.
    Class_ noclasscls = class_(No_class, No_class, nil_Features(), filename);
    install_special_class(new CgenNode(noclasscls, CgenNode::Basic, this));
    delete noclasscls;


    // SELF_TYPE is the self class; it cannot be redefined or inherited.
    Class_ selftypecls = class_(SELF_TYPE, No_class, nil_Features(), filename);
    install_special_class(new CgenNode(selftypecls, CgenNode::Basic, this));
    delete selftypecls;
    //
    // Primitive types masquerading as classes. This is done so we can
    // get the necessary Symbols for the innards of String, Int, and Bool
    //
    Class_ primstringcls =
            class_(prim_string, No_class, nil_Features(), filename);
    install_special_class(new CgenNode(primstringcls, CgenNode::Basic, this));
    delete primstringcls;

    Class_ primintcls = class_(prim_int, No_class, nil_Features(), filename);
    install_special_class(new CgenNode(primintcls, CgenNode::Basic, this));
    delete primintcls;
    Class_ primboolcls = class_(prim_bool, No_class, nil_Features(), filename);
    install_special_class(new CgenNode(primboolcls, CgenNode::Basic, this));
    delete primboolcls;
    //
    // The Object class has no parent class. Its methods are
    //    cool_abort() : Object    aborts the program
    //    type_name() : Str        returns a string representation of class name
    //    copy() : SELF_TYPE       returns a copy of the object
    //
    // There is no need for method bodies in the basic classes---these
    // are already built in to the runtime system.
    //
    Class_ objcls = class_(
        Object, No_class,
        append_Features(
            append_Features(single_Features(method(cool_abort, nil_Formals(),
                                                   Object, no_expr())),
                            single_Features(method(type_name, nil_Formals(),
                                                   String, no_expr()))),
            single_Features(
                method(cool_copy, nil_Formals(), SELF_TYPE, no_expr()))),
        filename);
    install_class(new CgenNode(objcls, CgenNode::Basic, this));
    delete objcls;

    //
    // The Int class has no methods and only a single attribute, the
    // "val" for the integer.
    //
    Class_ intcls = class_(
        Int, Object, single_Features(attr(val, prim_int, no_expr())), filename);
    install_class(new CgenNode(intcls, CgenNode::Basic, this));
    delete intcls;

    //
    // Bool also has only the "val" slot.
    //
    Class_ boolcls = class_(
        Bool, Object, single_Features(attr(val, prim_bool, no_expr())),
        filename);
    install_class(new CgenNode(boolcls, CgenNode::Basic, this));
    delete boolcls;


    //
    // The class String has a number of slots and operations:
    //       val                                  the string itself
    //       length() : Int                       length of the string
    //       concat(arg: Str) : Str               string concatenation
    //       substr(arg: Int, arg2: Int): Str     substring
    //
    Class_ stringcls =
            class_(String, Object,
                   append_Features(
                       append_Features(
                           append_Features(
                               single_Features(
                                   attr(val, prim_string, no_expr())),
                               single_Features(
                                   method(length, nil_Formals(), Int,
                                          no_expr()))),
                           single_Features(method(::concat,
                                                  single_Formals(
                                                      formal(arg, String)),
                                                  String, no_expr()))),
                       single_Features(
                           method(substr,
                                  append_Formals(
                                      single_Formals(formal(arg, Int)),
                                      single_Formals(formal(arg2, Int))),
                                  String, no_expr()))),
                   filename);
    install_class(new CgenNode(stringcls, CgenNode::Basic, this));
    delete stringcls;


    //
    // The IO class inherits from Object. Its methods are
    //        out_string(Str) : SELF_TYPE          writes a string to the output
    //        out_int(Int) : SELF_TYPE               "    an int    "  "     "
    //        in_string() : Str                    reads a string from the input
    //        in_int() : Int                         "   an int     "  "     "
    //
    Class_ iocls = class_(
        IO, Object,
        append_Features(
            append_Features(
                append_Features(
                    single_Features(method(out_string,
                                           single_Formals(formal(arg, String)),
                                           SELF_TYPE, no_expr())),
                    single_Features(method(out_int,
                                           single_Formals(formal(arg, Int)),
                                           SELF_TYPE, no_expr()))),
                single_Features(
                    method(in_string, nil_Formals(), String, no_expr()))),
            single_Features(method(in_int, nil_Formals(), Int, no_expr()))),
        filename);
    install_class(new CgenNode(iocls, CgenNode::Basic, this));
    delete iocls;
}

// install_classes enters a list of classes in the symbol table.
void CgenClassTable::install_classes(Classes cs)
{
    for (auto cls: cs) {
        install_class(new CgenNode(cls, CgenNode::NotBasic, this));
    }
}

// Add this CgenNode to the class list and the lookup table
void CgenClassTable::install_class(CgenNode* nd)
{
    Symbol name = nd->get_name();
    if (!this->find(name)) {
        // The class name is legal, so add it to the list of classes
        // and the symbol table.
        nds.push_back(nd);
        this->insert(name, nd);
    }
    // Prevent circular dependency issues when using this CgenNode later
    nd->premake_type();
    // nd->premake_debug_type();
}

// Add this CgenNode to the special class list and the lookup table
void CgenClassTable::install_special_class(CgenNode* nd)
{
    Symbol name = nd->get_name();
    if (!this->find(name)) {
        // The class name is legal, so add it to the list of special classes
        // and the symbol table.
        special_nds.push_back(nd);
        this->insert(name, nd);
    }
}

// CgenClassTable::build_inheritance_tree
void CgenClassTable::build_inheritance_tree()
{
    for (auto node: nds)
        set_relations(node);
}

// CgenClassTable::set_relations
// Takes a CgenNode and locates its, and its parent's, inheritance nodes
// via the class table. Parent and child pointers are added as appropriate.
//
void CgenClassTable::set_relations(CgenNode* nd)
{
    Symbol parent = nd->get_parent();
    auto parent_node = this->find(parent);
    if (!parent_node) {
        throw std::runtime_error("Class " + nd->get_name()->get_string() +
                                 " inherits from an undefined class " +
                                 parent->get_string());
    }
    nd->set_parent(parent_node);
}

// Sets up declarations for extra functions needed for code generation
// You should not need to modify this code for Lab1
void CgenClassTable::setup_external_functions()
{
    // setup function: external int strcmp(ptr, ptr)
    create_llvm_function("strcmp", i32, {ptr, ptr}, false);
    // setup function: external int printf(ptr, ...)
    create_llvm_function("printf", i32, {ptr}, true);
    // setup function: external void abort(void)
    create_llvm_function("abort", void_, {}, false);
    // setup function: external ptr malloc(i32)
    create_llvm_function("malloc", ptr, {i32}, false);
    // setup function: external void free(ptr)
    create_llvm_function("free", void_, {ptr}, false);


    auto* ObjectTy = ptr;
    create_function("Object_new", ObjectTy, {}, GlobalValue::ExternalLinkage);

    auto* IntTy = ptr;
    create_function("Int_new", IntTy, {}, GlobalValue::ExternalLinkage);
    create_function("Int_init", IntTy, {IntTy, i32}, GlobalValue::ExternalLinkage);

    auto* BoolTy = ptr;
    create_function("Bool_new", BoolTy, {}, GlobalValue::ExternalLinkage);
    // this takes a i8 because C's bool is byte
    create_function("Bool_init", BoolTy, {BoolTy, i8}, GlobalValue::ExternalLinkage);

    auto* StringTy = ptr;
    create_function("String_new", StringTy, {}, GlobalValue::ExternalLinkage);

    auto* IoTy = ptr;
    create_function("IO_new", IoTy, {}, GlobalValue::ExternalLinkage);
}

void CgenClassTable::setup_classes(CgenNode* c, int depth)
{
    c->setup(current_tag++, depth);
    for (auto child: c->get_children()) {
        setup_classes(child, depth + 1);
    }
    c->set_max_child(current_tag - 1);
}

// The code generation first pass. Define these two functions to traverse
// the tree and setup each CgenNode
void CgenClassTable::setup()
{
    setup_external_functions();
    setup_classes(root(), 0);

    // setup_external_functions();
}

// The code generation second pass. Add code here to traverse the tree and
// emit code for each CgenNode
void CgenClassTable::code_module()
{
    code_constants();
    code_classes(root());
    code_main();

    if (cgen_debug)
        std::cerr << "\n";
}


void CgenClassTable::code_classes(CgenNode* c)
{
    // emit Object first
    if (c->get_type_name() == "Object") {
        if (cgen_debug)
            std::cerr << "\n\nEmitting classes\n";
        c->code_class();
    }

    std::vector classes{c->get_children()};

    for (auto const i: classes)
        i->code_class();

    // we need to generate top down so that the types are populated for inherited classes
    for (auto* i: classes)
        code_classes(i);
}


// Create global definitions for constant Cool objects
void CgenClassTable::code_constants()
{
    if (cgen_debug)
        std::cerr << "\n\nEmitting constants\n";

    stringtable.code_string_table(this);
}

// Create LLVM entry point. This function will initiate our Cool program
// by generating the code to execute (new Main).main()
//
void CgenClassTable::code_main()
{
    if (cgen_debug)
        std::cerr << "\n\nEmitting main\n";
    // Define a function main that has no parameters and returns an i32
    auto* fn = create_function("main", i32, {},
                               GlobalValue::ExternalLinkage);
    // Define an entry basic block
    auto* bb = BasicBlock::Create(this->context, "main_entry_point", fn);
    builder.SetInsertPoint(bb);

    // Call Main_new() to create a Main
    auto* main_new = the_module.getFunction("Main_new");
    assertm(main_new, "Main_new exists");
    auto* main = builder.CreateCall(main_new, {});

    // Call Main_main
    auto* main_main = the_module.getFunction("Main_main");
    assertm(main_main, "Main_main exists");
    auto* main_returned = builder.CreateCall(main_main, {main});

    // Always return 0
    builder.CreateRet(builder.getInt32(0));
}

// Get the root of the class tree.
CgenNode* CgenClassTable::root()
{
    auto root = this->find(Object);
    if (!root) {
        throw std::runtime_error("Class Object is not defined.");
    }
    return root;
}


Function* CgenClassTable::create_llvm_function(const std::string &funcName,
                                               Type* retType,
                                               ArrayRef<Type *> argTypes,
                                               bool isVarArgs)
{
    assert(retType);
    auto* ft = FunctionType::get(retType, argTypes, isVarArgs);
    auto* func = Function::Create(ft, Function::ExternalLinkage, funcName,
                                  this->the_module);
    if (!func) {
        errs() << "Function creation failed for function " << funcName;
        llvm_unreachable("Function creation failed");
    }
    return func;
}

Function* CgenClassTable::create_function(const std::string &name,
                                          Type* ret_type,
                                          ArrayRef<Type *> arg_types,
                                          GlobalValue::LinkageTypes linkage)
{
    assert(ret_type);
    auto* ft = FunctionType::get(ret_type, arg_types, false);
    auto* func = Function::Create(ft, linkage, name,
                                  this->the_module);
    if (!func) {
        errs() << "Function creation failed for function " << name;
        llvm_unreachable("Function creation failed");
    }
    return func;
}

Function* CgenClassTable::create_var_function(const std::string &name,
                                              Type* ret_type,
                                              ArrayRef<Type *> arg_types,
                                              GlobalValue::LinkageTypes linkage)
{
    assert(ret_type);
    auto* ft = FunctionType::get(ret_type, arg_types, true);
    auto* func = Function::Create(ft, linkage, name,
                                  this->the_module);
    if (!func) {
        errs() << "Function creation failed for function " << name;
        llvm_unreachable("Function creation failed");
    }
    return func;
}

#pragma endregion

#pragma region "stringtab"
/*********************************************************************

  StrTable / IntTable methods

 Coding string, int, and boolean constants

 Cool has three kinds of constants: strings, ints, and booleans.
 This section defines code generation for each type.

 All string constants are listed in the global "stringtable" and have
 type stringEntry. stringEntry methods are defined both for string
 constant definitions and references.

 All integer constants are listed in the global "inttable" and have
 type IntEntry. IntEntry methods are defined for Int constant references only.

 Since there are only two Bool values, there is no need for a table.
 The two booleans are represented by instances of the class BoolConst,
 which defines the definition and reference methods for Bools.

*********************************************************************/

// Create definitions for all String constants
void StrTable::code_string_table(CgenClassTable* ct)
{
    if (cgen_debug)
        std::cerr << "Emitting string table\n";

    for (auto &[_, entry]: this->_table) {
        entry.code_def(ct);
    }
}

std::string StrTable::get_file() const
{
    auto it = _table.cbegin();
    for (int i = 0; i < _table.size() - 1; ++i)
        it++;
    return it->first;
}


// generate code to define a global string constant
void StringEntry::code_def(CgenClassTable* ct)
{
    if (cgen_debug)
        std::cerr << "\tEmitting \"" << this->str << "\"\n";

    auto* string = ct->find(String);

    auto* gstr = ct->builder.CreateGlobalStringPtr(this->str, "", 0, &ct->the_module);
    auto* init = ConstantStruct::get(string->type, {string->vtable, gstr});

    ptr = new GlobalVariable(ct->the_module, string->type, true,
        GlobalValue::InternalLinkage, init);
}

void StringEntry::code_ref(CgenClassTable *ct)
{
    // TODO: add code here
}

void IntEntry::code_ref(CgenClassTable *ct)
{
    // TODO: add code here
}
#pragma endregion

#pragma region "CgenNode"
//
// Class setup. You may need to add parameters to this function so that
// the classtable can provide setup information (such as the class tag
// that should be used by this class).
//
// Things that setup should do:
//  - layout the features of the class
//  - create the types for the class and its vtable
//  - create global definitions used by the class such as the class vtable
//
void CgenNode::setup(int const tag, int const depth)
{
    if (cgen_debug)
        std::cerr << "Setting up " << get_type_name() << "\n";

    this->tag = tag;

    auto* env = new CgenEnvironment(this);

    layout_features();

    this->make_vtable_type(env);
    this->make_type_forrealz(env);
    this->make_vtable_prototype(env);

    if (cgen_debug) {
        std::cerr << "\t";
        this->type->print(errs(), true), errs() << "\n";
        std::cerr << "\t";
        this->vtable_type->print(errs(), true), errs() << "\n";
    }

    // need to declare an init function if it doesn't already exist
    if (!basic())
        class_table->create_function(get_init_function_name(), type->getPointerTo(), {}, GlobalValue::ExternalLinkage);

    delete env;
}


// Laying out the features involves creating a Function for each method
// and assigning each attribute a slot in the class structure.
void CgenNode::layout_features()
{
    // append parent's shit to our shit (so that the object methods come first)
    if (parentnd && parentnd->get_type_name() != "_no_class") {
        methods.insert(methods.end(), parentnd->methods.begin(), parentnd->methods.end());
        attributes.insert(attributes.end(), parentnd->attributes.begin(), parentnd->attributes.end());
    }

    // the type for the class is declared when its CgenNode is installed
    // so that other classes can be referenced when features are laid out
    for (int i = features->first(); features->more(i); i = features->next(i))
        features->nth(i)->layout_feature(this);
}

// Class codegen. This should performed after every class has been setup.
// Generate code for each method of the class.
void CgenNode::code_class()
{
    // No code generation for basic classes. The runtime will handle that.
    if (basic())
        return;

    if (cgen_debug)
        std::cerr << "\n\nEmitting " + get_type_name() << "\n";

    auto* env = new CgenEnvironment(this);

    if (cgen_debug)
        std::cerr << "Emitting methods\n";
    for (auto [m, _]: methods) {
        if (cgen_debug)
            std::cerr << "\tEmitting " << m->qualified_name << "\n";

        m->code(env);
    }

    this->code_init_function(env);

    delete env;
}


void CgenNode::code_init_function(CgenEnvironment* env) const
{
    assert(type != nullptr);
    assert(vtable_type != nullptr);
    assert(vtable != nullptr);
    if (cgen_debug)
        std::cerr << "Emitting constructor " << get_init_function_name() << "\n";

    auto* init = env->the_module.getFunction(get_init_function_name());
    assert(init);
    auto* bb = BasicBlock::Create(env->context, "constructor", init);
    auto* gbb = BasicBlock::Create(env->context, "alloc_success", init);
    auto* abort = env->get_or_insert_abort_block(init);
    env->builder.SetInsertPoint(bb);

    // allocate space for ptr to type
    assert(type->isSized());
    auto* heap = env->builder.CreateCall(env->the_module.getFunction("malloc"), {
        ConstantInt::get(i32,
            env->data_layout.getTypeAllocSize(type))
    });

    Value* is_nullptr = env->builder.CreateICmpEQ(heap, ConstantPointerNull::get(ptr));
    env->builder.CreateCondBr(is_nullptr, abort, gbb);

    env->builder.SetInsertPoint(gbb);
    auto* mem = env->insert_alloca_at_head(type->getPointerTo(), "n.mem");
    env->builder.CreateStore(heap, mem);
    auto* hptr = env->builder.CreateLoad(type->getPointerTo(), mem, "n.hptr");

    env->builder.CreateStore(vtable, env->builder.CreateStructGEP(type, hptr, 0, "n.set_vtbl"));

    // create a fake self pointer in case any methods are called during init
    env->open_scope();
    env->add_binding(self, mem);

    for (int i = 0; i < attributes.size(); ++i) {
        auto* val = attributes.at(i).first->code(env); // code attrs here so that we can conform them as needed
        auto* attrptr = env->builder.CreateStructGEP(type, hptr, i + 1, "n.attrptr_" + attributes.at(i).first->get_name()->get_string());
        // make sure we default init
        if (val == ConstantPointerNull::get(env->ptr))
            env->builder.CreateStore(env->conform(env->default_value(attributes.at(i).second), env->ptr), attrptr);
        else
            env->builder.CreateStore(env->conform(val, env->ptr), attrptr);
    }

    env->close_scope();

    env->builder.CreateRet(env->builder.CreateLoad(type->getPointerTo(), mem));
}

void CgenNode::make_vtable_type(CgenEnvironment *env)
{
    assert(vtable_type == nullptr);
    vtable_type = StructType::create(this->ctx, std::string{"_"} + name->get_string() + "_vtable");

    if (cgen_debug)
        std::cerr << "Creating vtable type\n";

    // tag, size, ptr to name
    std::vector<Type*> vtable_elems{
        i32, i32,
        ptr
    };
    for (auto [_, t] : methods)
        vtable_elems.emplace_back(t->getPointerTo());

    vtable_type->setBody(vtable_elems);
    assert(vtable_type != nullptr);
}

void CgenNode::make_type_forrealz(CgenEnvironment *env)
{
    assert(type != nullptr);
    assert(vtable_type != nullptr);

    std::vector<Type *> type_elems{vtable_type->getPointerTo()};
    type_elems.reserve(attributes.size() + 1);

    // prior art: clang codegen record / cxxRecord
    if (cgen_debug)
        std::cerr << "Creating type\n";

    for (auto [_, i] : attributes) {
        type_elems.emplace_back(env->ptr); // we always box everything
    }

    type->setBody(type_elems);
}

void CgenNode::make_vtable_prototype(CgenEnvironment *env)
{
    assert(vtable_type != nullptr);
    assert(vtable == nullptr);
    // Build global with vtable
    if (cgen_debug)
        std::cerr << "Emitting vtable " << get_vtable_name() << "\n";

    using me = std::pair<method_class*, FunctionType*>;
    auto methods = map<me, Constant*>(this->methods,
        [this](me fn) -> Constant* {
            auto f = this->class_table->the_module.getFunction(fn.first->qualified_name);
            assertm(f, ("Couldn't find " + fn.first->qualified_name).c_str());
            return f;
    });

    auto* str = env->builder.CreateGlobalStringPtr(get_type_name(), name->get_string() + "_str", 0, &env->the_module);

    assert(type->isSized());
    std::vector consts{ConstantInt::get(i32, tag), ConstantInt::get(i32,
            env->data_layout.getTypeAllocSize(type)),
        str,
    };
    consts.insert(consts.end(), methods.begin(), methods.end());

    auto* cstrct = ConstantStruct::get(vtable_type, {consts});
    vtable = new GlobalVariable(env->the_module, this->vtable_type, true, GlobalValue::ExternalLinkage,
        cstrct, get_vtable_name());
    assert(vtable != nullptr);
}

void CgenNode::make_debug_type(CgenEnvironment* env)
{
    auto scope = class_table->di_cu;
    auto name = get_type_name();
    auto file = class_table->di_file;
    auto line_num = this->name->get_index();
    auto size_in_bits = env->data_layout.getTypeSizeInBits(type);
    auto align_in_bits = env->data_layout.getABITypeAlign(type).value();
    auto offset_in_bits = 0;
    auto flags = DINode::FlagZero;
    DIType* derived_from = nullptr;
    if (parentnd && parentnd->get_type_name() != "_no_class")
        derived_from = parentnd->dtype;
    auto elements = di_builder.getOrCreateArray(dfeats);

    this->dtype = di_builder.createClassType(scope, name, file, line_num,
        size_in_bits, align_in_bits, offset_in_bits, flags, derived_from,
        elements);
}

void CgenNode::premake_debug_type()
{
    auto scope = class_table->di_cu;
    auto name = get_type_name();
    auto file = class_table->di_file;
    auto line_num = this->name->get_index();
    auto size_in_bits = 0;
    auto align_in_bits = 0;
    auto offset_in_bits = 0;
    auto flags = DINode::FlagZero;
    DIType* derived_from = nullptr;
    auto elements = di_builder.getOrCreateArray(dfeats);

    this->dtype = di_builder.createClassType(scope, name, file, line_num,
        size_in_bits, align_in_bits, offset_in_bits, flags, derived_from,
        elements);
}

#pragma endregion

#pragma region "CgenEvironment"
// Look up a CgenNode given a symbol
CgenNode* CgenEnvironment::type_to_class(Symbol t) const
{
    return t == SELF_TYPE
       ? get_class()
       : get_class()->get_classtable()->find_in_scopes(t);
}

BasicBlock* CgenEnvironment::get_or_insert_abort_block(Function* f)
{
    for (auto &bb: *f) {
        if (bb.getName() == "abort") {
            return &bb;
        }
    }
    auto* abort_bb = BasicBlock::Create(this->context, "abort", f);
    Type* void_ = Type::getVoidTy(this->context);
    IRBuilder<> builder(abort_bb);
    FunctionCallee abort = this->the_module.getOrInsertFunction("abort", void_);
    builder.CreateCall(abort, {});
    builder.CreateUnreachable();
    return abort_bb;
}

std::optional<Value*> CgenEnvironment::find_if_exists(Symbol name) const
{
    if (auto* f = vars.find_in_scopes(name)) {
        return std::make_optional(f);
    }

    return std::nullopt;
}

std::pair<Type*, Value*> CgenEnvironment::find_in_scopes(Symbol name) const
{
    // Value* val;
    // if (name->get_string() == "self")
    //     val = vars.find_in_scopes(self);
    // else
    //     val = vars.find_in_scopes(name);
    // TODO: will there be an issue if there is a self that doesn't have an indentical index as the self global?
    auto val = find_if_exists(name);

    assertm(val, ("Variable " + name->get_string() + " not found").c_str());

    return resolve_opaque(*val);
}

AllocaInst* CgenEnvironment::insert_alloca_at_head(Type* ty)
{
    BasicBlock &entry_bb = builder.GetInsertBlock()->getParent()->
            getEntryBlock();
    if (entry_bb.empty()) {
        // Insert "at the end" of this bb
        return new AllocaInst(ty, 0, "", &entry_bb);
    } else {
        // Insert before the first instruction of this bb
        return new AllocaInst(ty, 0, "", &entry_bb.front());
    }
}

AllocaInst* CgenEnvironment::insert_alloca_at_head(Type* ty, Twine const &msg)
{
    assert(builder.GetInsertBlock());
    BasicBlock &entry_bb = builder.GetInsertBlock()->getParent()->
            getEntryBlock();
    if (entry_bb.empty()) {
        // Insert "at the end" of this bb
        return new AllocaInst(ty, 0, msg, &entry_bb);
    } else {
        // Insert before the first instruction of this bb
        return new AllocaInst(ty, 0, msg, &entry_bb.front());
    }
}

Type* CgenEnvironment::as_type(Symbol const s) const
{
    auto const _s = as_string(s);

    if (_s == "Int" || _s == "int" /* prim int */) return i32;
    if (_s == "Bool" || _s == "bool" /* prim bool */) return i1;
    if (_s == "sbyte*" /* prim string */) return ptr;

    return this->type_to_class(s)->type;
}

Type* CgenEnvironment::as_mostly_boxed_type(Symbol const s) const
{
    auto const _s = as_string(s);

    if (_s == "Int" || _s == "int" /* prim int */) return i32;
    if (_s == "Bool" || _s == "bool" /* prim bool */) return i1;

    return ptr;
}

DIType* CgenEnvironment::as_boxed_dtype(Symbol s) const
{
    auto const _s = as_string(s);

    // if (_s == "Int" || _s == "int" /* prim int */) return class_table.di32;
    // if (_s == "Bool" || _s == "bool" /* prim bool */) return class_table.di1;

    // return class_table.di_builder.createPointerType(type_to_class(s)->dtype, 64);
    // return type_to_class(s)->dtype;
    return class_table.dptr;
}

Value* CgenEnvironment::default_value(Type* ty) const
{
    if (ty->isIntegerTy())
        switch (ty->getIntegerBitWidth()) {
            case 1: return builder.getFalse();
            case 32: return builder.getInt32(0);
            default: llvm_unreachable(
                    "Unhandled integer bit with");
        }
    if (ty->isStructTy() && ty->getStructName() == "String")
        return builder.CreateGlobalString("");

    return ConstantPointerNull::get(ptr);
}

Value* CgenEnvironment::conform(Value* src, Type* dest_type)
{
    Type* src_type = src->getType();
    if (src_type == dest_type)
        return src;

    if (src_type->isPointerTy() && dest_type->isPointerTy())
        return src;

    if (src_type->isIntegerTy() && dest_type->isIntegerTy()) {
        return builder.CreateZExtOrTrunc(src, dest_type);
    }

    // box to Int or Bool
    if (src_type->isIntegerTy() && dest_type->isPointerTy()) {
        // if (cgen_debug) errs() << "\t\t\t\tBoxing ", src->print(errs(), true), errs() << " to object\n";
        switch (src_type->getIntegerBitWidth()) {
            case 1: {
                auto* bool_new = the_module.getFunction("Bool_new");
                assert(bool_new);
                auto* bool_init = the_module.getFunction("Bool_init");
                assert(bool_init);

                // allocate storage for ptr to Bool
                auto* r = insert_alloca_at_head(ptr, "box.i1");
                // create a new Bool
                auto* b = builder.CreateCall(bool_new->getFunctionType(), bool_new, {});
                // store the ptr to the bool so we can return it later
                builder.CreateStore(b, r);
                // upconvert to a cbool
                auto* c = builder.CreateZExt(src, i8);
                // initalize the bool
                auto* bptr1 = builder.CreateLoad(ptr, r);
                builder.CreateCall(bool_init->getFunctionType(), bool_init, {bptr1, c});
                // return the initalized bool
                return builder.CreateLoad(ptr, r, "boxed.i1");
            }
            case 32: {
                auto* int_new = the_module.getFunction("Int_new");
                assert(int_new);
                auto* int_init = the_module.getFunction("Int_init");
                assert(int_init);

                // allocate storage for ptr to Int
                auto* r = insert_alloca_at_head(ptr, "box.i32");
                // create a new Int
                auto* b = builder.CreateCall(int_new->getFunctionType(), int_new, {});
                // store the ptr to the int so we can return it later
                builder.CreateStore(b, r);
                // initalize the int
                auto* iptr1 = builder.CreateLoad(ptr, r);
                builder.CreateCall(int_init->getFunctionType(), int_init, {iptr1, src});
                // return the initalized int
                return builder.CreateLoad(ptr, r, "boxed.i32");
            }
            default: llvm_unreachable("Unsupported integer width to conform to");
        }
    }

    // rawdog a gep and hope for the best
    if (src_type->isPointerTy() && dest_type->isIntegerTy()) {
        // if (cgen_debug) errs() << "\t\t\t\tUnboxing ", src->print(errs(), true), errs() << " to prim\n";
        auto* ptr =  builder.CreateStructGEP(type_to_class(Int)->type, src, 1, "unboxedptr");
        return builder.CreateLoad(dest_type, ptr, "unboxed");
    }

    errs() << "Source ty: ", src_type->print(errs(), true), errs() << "\n";
    errs() << "Dest ty: ", dest_type->print(errs(), true), errs() << "\n";
    llvm_unreachable("Couldn't conform types");
}

#pragma endregion

/*********************************************************************

  APS class methods

    Fill in the following methods to produce code for the
    appropriate expression. You may add or remove parameters
    as you wish, but if you do, remember to change the parameters
    of the declarations in `cool-tree.handcode.h'.

*********************************************************************/
void program_class::cgen(const std::optional<std::string> &outfile)
{
    initialize_constants();
    class_table = new CgenClassTable(classes);
    if (outfile) {
        std::error_code err;
        raw_fd_ostream s(*outfile, err, sys::fs::FA_Write);
        if (err) {
            std::cerr << "Cannot open output file " << *outfile << std::endl;
            exit(1);
        }
        s << class_table->the_module;
    } else {
        outs() << class_table->the_module;
    }
}

// Create a method body
Value* method_class::code(CgenEnvironment* env)
{
    if (env->get_class()->get_type_name() != split(qualified_name, '_').first)
        return nullptr;

    if (cgen_debug) {
        std::cerr << "\t\tmethod" << std::endl;
    }

    env->open_scope();

    auto* bb = BasicBlock::Create(env->context, "entry", fn);
    env->builder.SetInsertPoint(bb);

    // name and bind function args
    assert(fn->arg_size() == formals->len() + 1);
    for (auto* arg = fn->arg_begin(); arg != fn->arg_end(); ++arg) {
        int idx = arg->getArgNo();

        // store arg
        auto* arg_ptr = env->insert_alloca_at_head(arg->getType());
        env->builder.CreateStore(arg, arg_ptr);

        // name and bind arg
        if (0 == idx) {
            arg->setName("self");
            env->add_binding(self, arg_ptr);
        } else {
            auto* name = formals->nth(idx - 1)->get_name();
            arg->setName(name->get_string());
            env->add_binding(name, arg_ptr);
        }
    }

    env->open_scope(); // body can redef args
    Value* val = expr->code(env);
    env->builder.CreateRet(env->conform(val, fn->getFunctionType()->getReturnType()));
    env->close_scope();

    env->close_scope();
    return fn;
}

// Codegen for expressions. Note that each expression has a value.

Value* assign_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tassign" << std::endl;

    Value* r = expr->code(env);

    if (auto ptr = env->find_if_exists(name)) {
        auto [ty, val] = resolve_opaque(*ptr);
        env->builder.CreateStore(env->conform(r, ty), val, "a.local");
        return r;
    }

    // since we are here, it must be a class attribute
    assert(env->get_class()->type->getNumElements() > 1);
    auto attrs = env->get_class()->attributes;
    for (int i = 0; i < attrs.size(); ++i)
        if (attrs.at(i).first->get_name() == name) {
            // TODO: will this just check pointer equality, or is this a real comparision?
            // emit a load to the element in self
            auto [ty, val] = env->find_in_scopes(self);
            auto* self = env->builder.CreateLoad(ty, val, "a.self");
            // TODO: figure out how to resolve an actual self out of this properly
            // hardcoding it for now
            auto v = env->builder.CreateStructGEP(env->get_class()->type, self, 1 + i, "a.attrptr");
            auto x = env->builder.CreateStore(env->conform(r, env->ptr), v, "a.attr");
            return r;
        }

    llvm_unreachable(("Couldn't assign to " + name->get_string() + ", reference not found").c_str());
}

Value* cond_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tcond" << std::endl;

    // allocate the result
    auto* res = env->insert_alloca_at_head(env->as_mostly_boxed_type(type), "cond");
    BasicBlock* startbb = env->builder.GetInsertBlock();
    Function* fn = startbb->getParent();

    // create basic blocks for the true and false branches
    auto* truebb = BasicBlock::Create(env->context, "true", fn);
    auto* falsebb = BasicBlock::Create(env->context, "false", fn);
    // and a basic block for the result
    auto* mergebb = BasicBlock::Create(env->context, "merge", fn);

    // branch
    env->builder.SetInsertPoint(startbb);
    Value* cond = env->conform(pred->code(env), env->i1);
    env->builder.CreateCondBr(cond, truebb, falsebb);

    // emit true
    env->builder.SetInsertPoint(truebb);
    env->builder.CreateStore(then_exp->code(env), res);
    env->builder.CreateBr(mergebb); // jump to merge to close bb

    // emit false
    env->builder.SetInsertPoint(falsebb);
    env->builder.CreateStore(else_exp->code(env), res);
    env->builder.CreateBr(mergebb); // jump to merge to close bb

    // load and return result
    env->builder.SetInsertPoint(mergebb);
    return env->builder.CreateLoad(res->getAllocatedType(), res);
}

Value* loop_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tloop" << std::endl;

    BasicBlock* startbb = env->builder.GetInsertBlock();
    Function* fn = startbb->getParent();

    // create basic blocks for conditional, loop, and end
    auto* condbb = BasicBlock::Create(env->context, "conditional", fn);
    auto* loopbb = BasicBlock::Create(env->context, "loop", fn);
    auto* endbb = BasicBlock::Create(env->context, "end", fn);

    // explicitly jump to conditional
    env->builder.SetInsertPoint(startbb);
    env->builder.CreateBr(condbb);

    // emit conditional
    env->builder.SetInsertPoint(condbb);
    // check loop conditional
    Value* cond = env->conform(pred->code(env), env->i1);
    env->builder.CreateCondBr(cond, loopbb, endbb);

    // emit loop
    env->builder.SetInsertPoint(loopbb);
    body->code(env);
    // end bb by jumping to conditional
    env->builder.CreateBr(condbb);

    // emit end
    env->builder.SetInsertPoint(endbb);
    // loops return void
    return ConstantPointerNull::get(env->ptr);
}

Value* block_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tblock" << std::endl;

    return map<Expression, Value *>(unfuck(body),
                                    [env](Expression const &e) -> Value* {
                                        return e->code(env);
                                    }).back();
}

Value* let_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\tlet" << std::endl;

    auto* ty = env->as_mostly_boxed_type(type_decl);
    // allocate let variable
    auto* var_ptr = env->insert_alloca_at_head(ty, "let");

    // store inital code to var_ptr
    Value* initial_val = init->code(env);
    if (!ConstantPointerNull::classof(initial_val))
        env->builder.CreateStore(initial_val, var_ptr);
    else // otherwise init with default value
        env->builder.CreateStore(env->default_value(ty), var_ptr);

    // bind memory location so the body can use it
    env->open_scope();
    env->add_binding(identifier, var_ptr);
    // return result of the let expr
    Value* r = body->code(env);

    env->close_scope();
    return r;
}

Value* plus_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tplus" << std::endl;

    Value* r1 = env->conform(e1->code(env), env->i32);
    Value* r2 = env->conform(e2->code(env), env->i32);
    return env->builder.CreateAdd(r1, r2, "add");
}

Value* sub_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tsub" << std::endl;

    Value* r1 = env->conform(e1->code(env), env->i32);
    Value* r2 = env->conform(e2->code(env), env->i32);
    return env->builder.CreateSub(r1, r2, "sub");
}

Value* mul_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tmul" << std::endl;

    Value* r1 = env->conform(e1->code(env), env->i32);
    Value* r2 = env->conform(e2->code(env), env->i32);
    return env->builder.CreateMul(r1, r2, "mul");
}

Value* divide_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tdiv" << std::endl;

    Value* r1 = env->conform(e1->code(env), env->i32);
    Value* r2 = env->conform(e2->code(env), env->i32);

    auto* curbb = env->builder.GetInsertBlock();
    auto* div = BasicBlock::Create(env->context, "div", curbb->getParent());
    auto* abort = env->get_or_insert_abort_block(curbb->getParent());

    env->builder.SetInsertPoint(curbb);
    Value* is_zero = env->builder.CreateICmpEQ(env->builder.getInt32(0), r2);
    env->builder.CreateCondBr(is_zero, abort, div);

    env->builder.SetInsertPoint(div);
    return env->builder.CreateSDiv(r1, r2, "div");
}

Value* neg_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tneg" << std::endl;

    Value* r = env->conform(e1->code(env), env->i32);
    return env->builder.CreateNeg(r, "neg");
}

Value* lt_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tlt" << std::endl;

    Value* r1 = env->conform(e1->code(env), env->i32);
    Value* r2 = env->conform(e2->code(env), env->i32);
    return env->builder.CreateICmpSLT(r1, r2, "cmpl");
}

Value* eq_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\teq" << std::endl;

    Value* r1 = e1->code(env);
    Value* r2 = e2->code(env);
    if (env->as_type(e1->get_type())->isIntegerTy() || env->as_type(e2->get_type())->isIntegerTy())
        return env->builder.CreateICmpEQ(env->conform(r1, env->i32), env->conform(r2, env->i32));

    return env->builder.CreateICmpEQ(r1, r2, "eq");
}

Value* leq_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tleq" << std::endl;

    Value* r1 = env->conform(e1->code(env), env->i32);
    Value* r2 = env->conform(e2->code(env), env->i32);
    return env->builder.CreateICmpSLE(r1, r2, "leq");
}

Value* comp_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tcomplement" << std::endl;

    Value* r = env->conform(e1->code(env), env->i1); // todo: check you can get an i32 here
    return env->builder.CreateNot(r, "comp");
}

Value* int_const_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tint_const" << std::endl;

    return env->builder.getInt32((uint32_t) std::stol(token->get_string()));
}

Value* bool_const_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tbool_const" << std::endl;

    return env->builder.getInt1(this->val);
}

Value* object_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tobject" << std::endl;

    if (auto f = env->find_if_exists(name)) {
        auto [ty, val] = resolve_opaque(*f);
        return env->builder.CreateLoad(ty, val, "o.local_" + name->get_string());
    }

    // since we are here, it must be a class attribute
    assert(env->get_class()->type->getNumElements() > 1);
    auto attrs = env->get_class()->attributes;
    for (int i = 0; i < attrs.size(); ++i)
        if (attrs.at(i).first->get_name() == name) {
            // TODO: will this just check pointer equality, or is this a real comparision?
            // emit a load to the element in self
            auto [ty, val] = env->find_in_scopes(self);
            auto* self = env->builder.CreateLoad(ty, val, "o.self");
            // TODO: figure out how to resolve an actual self out of this properly
            // hardcoding it for now
            auto v = env->builder.CreateStructGEP(env->get_class()->type, self, 1 + i, "o.attrptr_" + name->get_string());
            auto r = env->builder.CreateLoad(env->ptr, v, "o.attr_" + name->get_string());
            return r;
        }

    llvm_unreachable(("Couldn't resolve a reference to " + name->get_string()).c_str());
}

Value* no_expr_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tno expr" << std::endl;

    // emit a nullptr
    return ConstantPointerNull::get(env->ptr);
}

//*****************************************************************
// The next few functions are for node types not supported in Phase 1
// but these functions must be defined because they are declared as
// methods via the Expression_SHARED_EXTRAS hack.
//*****************************************************************

Value* static_dispatch_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tstatic dispatch" << std::endl;


    // evaluate args
    auto args = map<Expression, Value*>(unfuck(actual), [env](Expression const& e) -> Value* {
        return e->code(env);
    });

    // figure out the calling class
    auto* caller_class = env->type_to_class(type_name);
    auto* caller = expr->code(env);

    // box prims
    if (caller->getType()->isIntegerTy()) {
        auto* orig = caller;
        caller = env->conform(orig, env->ptr);
    }
    // sanity check caller
    assert(caller->getType()->isPointerTy());

    if (cgen_debug)
        errs() << "\t\t\tLooking for " << as_string(name) << "\n";

    // figure out method index into vtable
    auto get_method_idx = [](CgenNode* cls, Symbol name) -> int {
        auto methods = cls->methods;
        // search in reverse so we get the overload instead of the original
        for (int i = methods.size() - 1; i > 0; --i) {
            if (methods.at(i).first->get_name() == name) {
                return i;
            }
        }

        llvm_unreachable(("Couldn't find " + as_string(name) + " in " + as_string(cls->get_name())).c_str());
    };
    int method_idx = get_method_idx(caller_class, name);

    auto n = as_string(name);
    auto* curbb = env->builder.GetInsertBlock();
    auto* abort = env->get_or_insert_abort_block(curbb->getParent());
    auto* validbb = BasicBlock::Create(env->context, "sdispatch_" + n, curbb->getParent());

    // emit nulltpr check
    env->builder.SetInsertPoint(curbb);
    Value* is_nullptr = env->builder.CreateICmpEQ(caller, ConstantPointerNull::get(env->ptr));
    env->builder.CreateCondBr(is_nullptr, abort, validbb);

    // emit call global vtable if successful
    env->builder.SetInsertPoint(validbb);
    // get method's signature
    auto* method_ty = caller_class->methods.at(method_idx).second;
    // get pointer from vtable
    Value* method_ptr = env->builder.CreateStructGEP(caller_class->vtable_type,
        caller_class->vtable, method_idx + 3, "sd.mptr"); // first three elems of the vtable aren't methods
    auto* method = env->builder.CreateLoad(method_ty->getPointerTo(), method_ptr, "sd." + n);
    // build method args
    std::vector real_args{caller};
    real_args.reserve(1 + args.size());
    for (int i = 0; i < args.size(); ++i) { // make sure args are unboxed as needed
        real_args.emplace_back(env->conform(args.at(i), method_ty->getParamType(i + 1)));
    }
    // call method
    return env->builder.CreateCall(method_ty, method, real_args);
}

Value* string_const_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tstring_const" << std::endl;

    auto* e = stringtable.lookup_string(as_string(token));
    auto* global =  reinterpret_cast<StringEntry*>(e)->ptr;
    return global;
}

Value* dispatch_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tdispatch\n" << std::endl;

    // evaluate args
    auto args = map<Expression, Value*>(unfuck(actual), [env](Expression const& e) -> Value* {
        return e->code(env);
    });

    // figure out the calling class
    auto* caller_class = env->type_to_class(expr->get_type());
    Value* caller = expr->code(env);

    // box prims
    if (caller->getType()->isIntegerTy()) {
        auto* orig = caller;
        caller = env->conform(orig, env->ptr);
    }
    // sanity check caller
    assert(caller->getType()->isPointerTy());

    if (cgen_debug)
        errs() << "\t\t\tLooking for " << as_string(name) << "\n";

    // figure out method index into vtable
    auto get_method_idx = [](CgenNode* cls, Symbol name) -> int {
        auto methods = cls->methods;
        // search in reverse so we get the overload instead of the original
        for (int i = methods.size() - 1; i >= 0; --i) {
            if (methods.at(i).first->get_name() == name) {
                return i;
            }
        }

        llvm_unreachable(("Couldn't find " + as_string(name) + " in " + as_string(cls->get_name())).c_str());
    };
    int method_idx = get_method_idx(caller_class, name);

    auto n = as_string(name);
    auto* curbb = env->builder.GetInsertBlock();
    auto* abort = env->get_or_insert_abort_block(curbb->getParent());
    auto* validbb = BasicBlock::Create(env->context, "dispatch_" + n, curbb->getParent());

    // emit nulltpr check
    env->builder.SetInsertPoint(curbb);
    Value* is_nullptr = env->builder.CreateICmpEQ(caller, ConstantPointerNull::get(env->ptr));
    env->builder.CreateCondBr(is_nullptr, abort, validbb);


    // emit call through vtable if successful
    env->builder.SetInsertPoint(validbb);
    // get vtable ptr
    auto* vtable_ptr = env->builder.CreateStructGEP(caller_class->type, caller, 0, "d.vtblptr");
    // load vtable
    auto* vtable = env->builder.CreateLoad(env->ptr, vtable_ptr, "d.vtbl");
    // get method's signature
    auto* method_ty = caller_class->methods.at(method_idx).second;
    // get pointer from vtable
    Value* method_ptr = env->builder.CreateStructGEP(caller_class->vtable_type,
        vtable, method_idx + 3, "d.mptr"); // first three elems of the vtable aren't methods
    auto* method = env->builder.CreateLoad(method_ty->getPointerTo(), method_ptr, "d." + n);
    // build method args
    std::vector real_args{caller};
    real_args.reserve(1 + args.size());
    for (int i = 0; i < args.size(); ++i) { // make sure args are unboxed as needed
        // if (cgen_debug) errs() << "\t\t\t", method_ty->getParamType(i + 1)->print(errs(), true), errs() << " <- ", args.at(i)->print(errs(), true), errs() << "\n";
        real_args.emplace_back(env->conform(args.at(i), method_ty->getParamType(i + 1)));
        // if (cgen_debug) errs() << "\t\t\t", real_args.at(i + 1)->print(errs(), true), errs() << "\n";
        assert(real_args.at(i + 1)->getType() == method_ty->getParamType(i + 1));
    }
    assert(real_args.size() == method_ty->getNumParams());
    // call method

    if (cgen_debug)
        errs() << "\t\tend dispatch\n";
    return env->builder.CreateCall(method_ty, method, real_args);
}

// Handle a Cool case expression (selecting based on the type of an object)
Value* typcase_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\ttype case" << std::endl;

    auto e_class = env->type_to_class(expr->get_type());
    auto sumty = env->type_to_class(type);
    Value* e = expr->code(env);

    // box prims
    if (e->getType()->isIntegerTy()) {
        auto* orig = e;
        e = env->conform(orig, env->ptr);
    }
    assert(e->getType()->isPointerTy());


    auto* curbb = env->builder.GetInsertBlock();
    auto* abort = env->get_or_insert_abort_block(curbb->getParent());
    auto* goodbb = BasicBlock::Create(env->context, "typcase.good", curbb->getParent());
    auto* matchbb = BasicBlock::Create(env->context, "typcase.match", curbb->getParent());
    auto* resbb = BasicBlock::Create(env->context, "typcase.result", curbb->getParent());

    // emit void check
    env->builder.SetInsertPoint(curbb);
    auto* test = env->builder.CreateICmpEQ(e, ConstantPointerNull::get(env->ptr), "typcase.isvoid");
    env->builder.CreateCondBr(test, abort, goodbb);

    env->builder.SetInsertPoint(goodbb);
    // get tag
    auto* vtable_ptr = env->builder.CreateStructGEP(e_class->type, e, 0, "typcase.vtblptr");
    auto* vtable = env->builder.CreateLoad(env->ptr, vtable_ptr, "typcase.vtbl");
    auto* tag_ptr = env->builder.CreateStructGEP(e_class->vtable_type, vtable, 0, "typcase.tagptr");
    auto* tag = env->builder.CreateLoad(env->i32, tag_ptr, "typcase.tag");

    // stack slot for result, case is always boxed
    auto* res = env->insert_alloca_at_head(env->ptr);
    // store nullptr
    env->builder.CreateStore(ConstantPointerNull::get(env->ptr), res);

    // sort cases largest tag to smallest
    std::vector<Case> branches;
    branches.reserve(cases->len());
    for (auto c: cases) {
        branches.emplace_back(c);
    }
    std::sort(branches.begin(), branches.end(), [env](Case a, Case b) {
        return env->type_to_class(a->get_type_decl())->get_tag() > env->type_to_class(b->get_type_decl())->get_tag();
    });
    std::for_each(branches.begin(), branches.end(), [env, e, tag, res, matchbb](Case c) {
       c->code(e, tag, res, matchbb, env);
    });
    // abort if no match
    env->builder.CreateBr(abort);

    env->builder.SetInsertPoint(matchbb);
    // test if result is null
    auto* r = env->builder.CreateLoad(env->ptr, res, "typcase.res");
    auto* test_res = env->builder.CreateICmpEQ(r, ConstantPointerNull::get(env->ptr), "typcase.res.isvoid");
    env->builder.CreateCondBr(test_res, abort, resbb);

    // clean up
    env->builder.SetInsertPoint(resbb);
    return r;
}

Value* new__class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tnew" << std::endl;

    // return nullptr;

    auto init = env->type_to_class(type_name)->get_init_function_name();
    auto* initfn = env->the_module.getFunction(init);
    assert(initfn);
    return env->builder.CreateCall(initfn->getFunctionType(), initfn, {});
}

Value* isvoid_class::code(CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tisvoid" << std::endl;

    Value* e = e1->code(env);

    if (e->getType()->isIntegerTy())
        return env->builder.getTrue();

    assert(e->getType()->isPointerTy());

    auto* ret = env->insert_alloca_at_head(env->i1);
    auto* curbb = env->builder.GetInsertBlock();
    auto* truebb = BasicBlock::Create(env->context, "isvoid.true", curbb->getParent());
    auto* falsebb = BasicBlock::Create(env->context, "isvoid.false", curbb->getParent());
    auto* mergebb = BasicBlock::Create(env->context, "isvoid.result", curbb->getParent());

    env->builder.SetInsertPoint(curbb);
    auto* test = env->builder.CreateICmpEQ(e, ConstantPointerNull::get(env->ptr), "isvoid");
    env->builder.CreateCondBr(test, truebb, falsebb);

    env->builder.SetInsertPoint(truebb);
    env->builder.CreateStore(env->builder.getTrue(), ret);
    env->builder.CreateBr(mergebb);

    env->builder.SetInsertPoint(falsebb);
    env->builder.CreateStore(env->builder.getFalse(), ret);
    env->builder.CreateBr(mergebb);

    env->builder.SetInsertPoint(mergebb);
    return env->builder.CreateLoad(env->i1, ret);
}

// Record the method
void method_class::layout_feature(CgenNode* cls)
{
    // if (cls->basic())
    //     return; // handled by the runtime
    auto* env = new CgenEnvironment(cls);

    assert(qualified_name.empty());
    qualified_name = cls->get_type_name() + "_" + this->get_name()->get_string();

    std::vector<Type*> real_args;
    real_args.reserve(formals->len() + 1);
    real_args.emplace_back(env->ptr); // first arg is always self ptr
    auto _formals = unfuck(formals);
    auto args =  map<Formal, Type *>(_formals,
       [env](Formal const &f) -> Type* {
           return env->as_mostly_boxed_type(f->get_type_decl());
       });
    real_args.insert(real_args.end(), args.begin(), args.end());

    // real function
    auto* ty = CgenNode::create_functionty(env->as_mostly_boxed_type(return_type), real_args);
    fn = cls->create_function(as_string(get_name()), ty);

    #ifdef EMIT_DBG
    if (!cls->basic()) {
        // debug function type
        std::vector<Metadata*> dtys;
        dtys.emplace_back(env->as_boxed_dtype(return_type));
        for (auto f: _formals)
            dtys.emplace_back(env->as_boxed_dtype(f->get_type_decl()));
        auto dty = cls->di_builder.createSubroutineType(cls->di_builder.getOrCreateTypeArray(dtys));
        auto dfn = cls->di_builder.createFunction(env->class_table.di_cu, this->get_name()->get_string(), cls->get_type_name() + "_" + this->get_name()->get_string(), env->class_table.di_file, this->get_name()->get_index(), dty,this->get_name()->get_index(), DINode::FlagPrototyped, DISubprogram::SPFlagDefinition);
        fn->setSubprogram(dfn);
        cls->dfeats.emplace_back(dfn);
    }
    #endif

    cls->methods.emplace_back(this, ty);
    delete env;
}

// Handle one branch of a Cool case expression.
// If the source tag is >= the branch tag
// and <= (max child of the branch class) tag,
// then the branch is a superclass of the source.
// See the LAB2 handout for more information about our use of class tags.
void branch_class::code(Value* expr_val, Value* tag, Value* mem, BasicBlock* sbb, CgenEnvironment* env)
{
    if (cgen_debug)
        std::cerr << "\t\tbranch\n";

    auto cls = env->type_to_class(type_decl);
    int start_tag = cls->get_tag();
    int end_tag = cls->get_max_child();

    auto* curbb = env->builder.GetInsertBlock();
    auto* maxbb = BasicBlock::Create(env->context, "typcase.br.match.max." + name->get_string(), curbb->getParent());
    auto* minbb = BasicBlock::Create(env->context, "typcase.br.match.min." + name->get_string(), curbb->getParent());
    auto* endbb = BasicBlock::Create(env->context, "typcase.br.nomatch." + name->get_string(), curbb->getParent());

    env->builder.SetInsertPoint(curbb);
    // test min tag first, since we test largest to smallest cases
    auto* mintest = env->builder.CreateICmpSGE(tag, ConstantInt::get(env->i32, start_tag, true), "typcase.br.min." + name->get_string());
    env->builder.CreateCondBr(mintest, minbb, endbb);

    env->builder.SetInsertPoint(minbb);
    // test max tag
    auto* maxtest = env->builder.CreateICmpSLE(tag, ConstantInt::get(env->i32, end_tag, true), "typcase.br.max." + name->get_string());
    env->builder.CreateCondBr(maxtest, maxbb, endbb);

    env->builder.SetInsertPoint(maxbb);
    auto* branchptr = env->insert_alloca_at_head(env->ptr);
    env->builder.CreateStore(expr_val, branchptr);
    env->open_scope(); // eval branch with new scope
    env->add_binding(name, branchptr);
    auto* res = expr->code(env);
    env->close_scope();
    // store into result
    env->builder.CreateStore(res, mem);
    env->builder.CreateBr(sbb);

    env->builder.SetInsertPoint(endbb);
}

// Assign this attribute a slot in the class structure
void attr_class::layout_feature(CgenNode* cls)
{
    auto* env = new CgenEnvironment(cls);
    auto ty = env->as_mostly_boxed_type(type_decl);
    cls->attributes.emplace_back(this, ty);
    #ifdef EMIT_DBG
    // build debug info
    cls->dfeats.emplace_back(env->as_boxed_dtype(type_decl));
    #endif
    delete env;
}

Value* attr_class::code(CgenEnvironment* env)
{
    val = init->code(env);
    // return env->conform(val, env->ptr);
    return val;
}

#pragma region "utils"
namespace
{
std::string as_string(Symbol const s)
{
    return s->get_string();
}

std::vector<Expression> unfuck(Expressions const fuck_this)
{
    std::vector<Expression> r{};
    r.reserve(fuck_this->len());

    for (int i = fuck_this->first(); fuck_this->more(i); i = fuck_this->next(i))
        r.push_back(fuck_this->nth(i));

    return r;
}

std::vector<Formal> unfuck(Formals const fuck_this)
{
    std::vector<Formal> r{};
    r.reserve(fuck_this->len());

    for (int i = fuck_this->first(); fuck_this->more(i); i = fuck_this->next(i))
        r.push_back(fuck_this->nth(i));

    return r;
}

std::vector<Feature> unfuck(Features const fuck_this)
{
    std::vector<Feature> r{};
    r.reserve(fuck_this->len());

    for (int i = fuck_this->first(); fuck_this->more(i); i = fuck_this->next(i))
        r.push_back(fuck_this->nth(i));

    return r;
}

std::pair<Type*, Value*> resolve_opaque(Value* val)
{
    // TODO: resolve malloced things

    if (auto* a = dyn_cast<AllocaInst>(val))
        return {a->getAllocatedType(), val};

    if (auto* g = dyn_cast<GlobalVariable>(val))
        return {g->getValueType(), val};

    if (auto* s = dyn_cast<GetElementPtrInst>(val))
        return {s->getSourceElementType(), val};

    errs() << "Unresolved opaque value: ", val->print(errs(), true), errs() << "\n";
    llvm_unreachable("couldn't get original type for value");
}

template<class T, class R>
std::vector<R> map(std::vector<T> src, std::function<R(T const &)> mapper)
{
    std::vector<R> r{};
    r.reserve(src.size());

    for (auto i: src)
        r.emplace_back(mapper(i));

    return r;
}

std::pair<std::string, std::string> split(const std::string& s, char const c)
{
    size_t pos = s.find(c);
    if (pos == std::string::npos)
        return {s, ""};


    return {s.substr(0, pos), s.substr(pos + 1)};
}
}
#pragma endregion