/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/*
 * File:   DominatorsTreeAnalysisProvider.cpp
 * Author: pgess
 *
 * Created on May 13, 2016, 11:39 AM
 */

#include "analysis/cfagraph.h"
#include "analysis/DominatorsTreeAnalysisProvider.h"

#include "llvm/ADT/GraphTraits.h"
#include "llvm/Support/GenericDomTreeConstruction.h"
#include "llvm/Support/GenericDomTree.h"

#include <list>
#include <iostream>
#include <boost/format.hpp>

using namespace std;
using namespace xreate;
using namespace boost;
using namespace boost::bimaps;

struct ControlFlowTree;

struct Node {
    ScopePacked scope;
    ControlFlowTree* tree;
};

/*
bool operator !=(const Node& a, const Node& b){
    return (a.tree != b.tree) || (a.scope != b.scope);
}

Node& operator++(Node& a){
    ++a.scope;
    return a;
}
 */

struct ControlFlowTree{
    typedef bimap<multiset_of<ScopePacked>, multiset_of<ScopePacked>> CHILD_RELATIONS;
    CHILD_RELATIONS edges;
    std::vector<Node> nodes;
    Node* entry = nullptr;
    size_t size;

    ControlFlowTree(const size_t nodesCount): nodes(nodesCount), size(nodesCount){
    }

    static ControlFlowTree* build(const ClaspLayer* engine){
        ControlFlowTree* tree = new ControlFlowTree(engine->getScopesCount());

        xreate::analysis::CFAGraph* graph = engine->dataCFA.get();

        for (const auto& edge: graph->__parentScopeRelations){
            tree->edges.insert(CHILD_RELATIONS::value_type(edge.second, edge.first));
        }

        for (const auto& edge: graph->__callRelations){
            unsigned int calleeFunction = edge.right;
            ScopePacked caller = edge.left;

            auto range = graph->__parentFunctionRelations.right.equal_range(calleeFunction);
            for (auto& i=range.first; i!= range.second; ++i){
                tree->edges.insert(CHILD_RELATIONS::value_type(caller, i->second));
            }
        }

        for (size_t i=0; i<tree->size; ++i){
            tree->nodes[i]= Node{(unsigned int) i, tree};
        }

        return tree;
    }

    std::list<unsigned int> getRootFunctions() const{
        size_t idMax = size;
        size_t id =0;
        std::list<unsigned int> results;
        auto i = edges.right.begin();

        while (id < idMax) {
            if (i!= edges.right.end() && i->first == id){
                i = edges.right.upper_bound(i->first);

            } else {
                results.push_back(id);
            }

            ++id;
        }

        return std::move(results);
    }
};

namespace llvm {
    template <> struct GraphTraits<Node*> {
        typedef Node* nodes_iterator;
        typedef Node NodeType;

        typedef std::function<Node*(ControlFlowTree::CHILD_RELATIONS::left_value_type)> Transformer;
        typedef typename boost::transform_iterator<Transformer, ControlFlowTree::CHILD_RELATIONS::left_iterator> ChildIteratorType;

        static ChildIteratorType child_begin(const nodes_iterator& node) {
            auto range = node->tree->edges.left.equal_range(node->scope);
            Transformer x = [node](auto edge){return &node->tree->nodes[edge.second];};

            return boost::make_transform_iterator(range.first, x);
        }

        static ChildIteratorType child_end(const nodes_iterator& node) {
            auto range = node->tree->edges.left.equal_range(node->scope);
            Transformer x = [node](auto edge){return &node->tree->nodes[edge.second];};

            return boost::make_transform_iterator(range.second, x);
        }
    };

    template <> struct GraphTraits<Inverse<Node*>> {
        typedef Node* nodes_iterator;
        typedef Node NodeType;

        typedef std::function<Node*(ControlFlowTree::CHILD_RELATIONS::right_value_type)> Transformer;
        typedef typename boost::transform_iterator<Transformer, ControlFlowTree::CHILD_RELATIONS::right_iterator> ChildIteratorType;

        static ChildIteratorType child_begin(const nodes_iterator& node) {
            auto range = node->tree->edges.right.equal_range(node->scope);
            Transformer x = [node](auto edge){return &node->tree->nodes[edge.second];};

            return boost::make_transform_iterator(range.first, x);
        }

        static ChildIteratorType child_end(const nodes_iterator& node) {
            auto range = node->tree->edges.right.equal_range(node->scope);
            Transformer x = [node](auto edge){return &node->tree->nodes[edge.second];};

            return boost::make_transform_iterator(range.second, x);
        }
    };

    template <> struct GraphTraits<ControlFlowTree*>: public GraphTraits<Node*> {
        static NodeType*
        getEntryNode(ControlFlowTree* F) {
            if (F->entry) return F->entry;

            list<unsigned int>&& roots = F->getRootFunctions();
            assert(roots.size()==1);

            return F->entry = &F->nodes[roots.front()];
        }

        static nodes_iterator nodes_begin(ControlFlowTree* F) { return &F->nodes[0]; }
        static nodes_iterator   nodes_end(ControlFlowTree* F) { return &F->nodes[F->size]; }
        static size_t              size(ControlFlowTree* F) { return F->size; }
    };
}

class xreate::DominatorTree: public llvm::DominatorTreeBase<Node> {
public:
    DominatorsTreeAnalysisProvider::Dominators dominators;

    DominatorTree(bool isPostDom): llvm::DominatorTreeBase<Node>(isPostDom) {}

    void run(ControlFlowTree& program){
        recalculate(program);

        //extract dominators info
        for (auto& entry: DomTreeNodes){
            if (!entry.getFirst()) continue;

            dominators.emplace(entry.getFirst()->scope, make_pair(entry.getSecond()->getDFSNumIn(), entry.getSecond()->getDFSNumOut()));
        }
    }

    void print(std::ostringstream& output, const std::string& atom) const {
        boost::format formatAtom(atom + "(%1%, range(%2%, %3%)).");
        for (auto entry: dominators){
            output << formatAtom % (entry.first) % (entry.second.first) % (entry.second.second)
                    << endl;
        }
    }
};

void
DominatorsTreeAnalysisProvider::run(const ClaspLayer* engine){
   boost::scoped_ptr<ControlFlowTree> program(ControlFlowTree::build(engine));

   treeForwardDominators->run(*program);
   treePostDominators->run(*program);
}

void
DominatorsTreeAnalysisProvider::print(std::ostringstream& output) const{
    treeForwardDominators->print(output, "cfa_forwdom");
    treePostDominators->print(output, "cfa_postdom");
}

const DominatorsTreeAnalysisProvider::Dominators&
DominatorsTreeAnalysisProvider::getForwardDominators() const{
    return treeForwardDominators->dominators;
}

const DominatorsTreeAnalysisProvider::Dominators&
DominatorsTreeAnalysisProvider::getPostDominators() const{
    return treePostDominators->dominators;
}

DominatorsTreeAnalysisProvider::DominatorsTreeAnalysisProvider()
    : treeForwardDominators(new DominatorTree(false))
    , treePostDominators(new DominatorTree(true))
{}

DominatorsTreeAnalysisProvider::~DominatorsTreeAnalysisProvider() {}

//void
//CodeScopesTree::print(){
//    typedef llvm::GraphTraits<Node*> Traits;
//    for (size_t i=0; i<size; ++i){
//
//        for (auto j = Traits::child_begin(&nodes[i]); j!= Traits::child_end(&nodes[i]); ++j){
//            cout << i << "->" << (*j)->scope << endl;
//        }
//    }
//}