#include "blocks.h"
//#include "collections.h"
#include "duchain.h"

struct _use {
    Node node;
    Use next;
};
    
struct duchain {
    Node defn;
    Use first;
    Use last;
    int max_depth;
    int order;
};

static DuChain duchain_new(Node defn, int order) {
    assert(defn);
    DuChain chain = allocate(sizeof(struct duchain), FUNC);
    chain->defn = defn;
    chain->first = NULL;
    chain->last = NULL;
    chain->order = order;
    return chain;
}

Symbol duchain_symbol(DuChain chain) {
    return chain->defn->syms[0];
}    

Node duchain_defn(DuChain chain) {
    return chain->defn;    
}

Use duchain_firstUse(DuChain chain) {
    return chain->first;    
}

Use duchain_nextUse(Use use) {
    return use->next;    
}

Node duchain_useNode(Use use) {
    return use->node;
}

static void duchain_addUse(DuChain chain, Node use) {
    Use addedUse = allocate(sizeof(struct _use), FUNC);
    addedUse->node = use;
    addedUse->next = NULL;
    if (chain->first == NULL) {
        chain->first = addedUse;
        chain->last = addedUse;
    } else {
        chain->last->next = addedUse;
        chain->last = addedUse;
    }
    if(getTotalDepth(use) > chain->max_depth)
        chain->max_depth = getTotalDepth(use);
}

int compareByOccurence(DuChain* chain1, DuChain* chain2) {
    return (*chain1)->order - (*chain2)->order;
}

int compareByID(DuChain* chain1, DuChain* chain2) {
    return getTempIndex((*chain1)->defn) - getTempIndex((*chain2)->defn); 
}

int duchain_getID(DuChain chain) {
    return getTempIndex(chain->defn);
}

static void findUse(Node p, DuChain* indexedChains) {
    if (p->kids[0]) {
        if (generic(p->kids[0]->op) == VREG) {
            DuChain chain = indexedChains[getTempIndex(p->kids[0])];
            if (chain)
                duchain_addUse(chain, p->kids[0]);
        } else {
            findUse(p->kids[0], indexedChains);
            if (p->kids[1])
                findUse(p->kids[1], indexedChains);
        }
    }
}

int duchain_maxDepth(DuChain chain) {
    return chain->max_depth;    
}

ArrayList duchain_getChains(Block b) {
    int i, order = 0;
    Node p, end, kid;
    ArrayList chains = list_new(16);
    if (local_variable_count == 0)
        return chains;
    BitSet livein = block_livein(b);
    DuChain* indexedChains = allocate(sizeof(DuChain) * local_variable_count, FUNC);
    for (i = 0; i < local_variable_count; i++) {
        indexedChains[i] = NULL;
    }
    end = block_lastNode(b)->x.next;
    for (p = block_firstNode(b); p != end; p = p->x.next) {
        if (generic(p->op) == ASGN) {
            kid = p->kids[0];
            findUse(kid, indexedChains);
            kid = p->kids[1];
            if (generic(kid->op) == VREG) {
                DuChain completed = indexedChains[getTempIndex(kid)];
                if (completed != NULL && completed->first != NULL) {
                    list_add(chains, completed);
                }
                indexedChains[getTempIndex(kid)] = duchain_new(kid, order++);
            } else {
                findUse(kid, indexedChains);
            }
        } else {
            findUse(p, indexedChains);
        }
    }
    for (i = 0; i < local_variable_count; i++) {
        if (indexedChains[i] != NULL && indexedChains[i]->first != NULL)
            list_add(chains, indexedChains[i]);
    }
    return chains;
}