/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 *
 * File:   DominatorsTreeAnalysisProvider.cpp
 * Author: pgess  <v.melnychenko@xreate.org>
 *
 * Created on May 13, 2016, 11:39 AM
 */

/**
 *  \file DominatorsTreeAnalysisProvider.h
 *  \brief Dominators Tree analysis
 */

#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;

namespace xreate {
namespace dominators {

struct CFAGraphAdapter;

struct ScopeNode {
    ScopePacked id;
    std::list<ScopeNode*> nodesFrom;
    std::list<ScopeNode*> nodesTo;
};

struct CFAGraphAdapter {
    std::list<ScopeNode> nodes;
    ScopeNode* nodeRoot;

    ScopeNode* getOrCreateNode(ScopePacked id){
        ScopeNode elemNew; elemNew.id = id;
        auto fnComp = [](const ScopeNode &a, const ScopeNode &b){return a.id < b.id;};
        auto posLowerBound = std::lower_bound(nodes.begin(), nodes.end(), elemNew, fnComp);

        if(posLowerBound==nodes.end()|| posLowerBound->id > id){
            return &*nodes.insert(posLowerBound, elemNew);
        }

        return &*posLowerBound;
    }

    static CFAGraphAdapter* build(const cfa::CFAGraph* graph) {
        CFAGraphAdapter* tree=new CFAGraphAdapter();

        enum NODE_MARK{NO_ROOT, POSSIBLE_ROOT};
        std::unordered_map<unsigned int, NODE_MARK> nodeMarks;
        for (const auto& edge: graph->__dependencyRelations){

            ScopeNode* nodeTo = tree->getOrCreateNode(edge.first);
            ScopeNode* nodeFrom = tree->getOrCreateNode(edge.second);
            nodeTo->nodesFrom.push_back(nodeFrom);
            nodeFrom->nodesTo.push_back(nodeTo);

            nodeMarks.emplace(edge.second, POSSIBLE_ROOT); //weak optional insert
            auto result = nodeMarks.emplace(edge.first, NO_ROOT); //strong insert or update
            if(!result.second){
                result.first->second = NO_ROOT;
            }
        }

        std::list<ScopePacked> nodeRoots;
        for(auto nodeMark: nodeMarks){
            if(nodeMark.second == POSSIBLE_ROOT) nodeRoots.push_back(nodeMark.first);
        }

        if(nodeRoots.size()>1){
            ScopeNode* nodeGlobalRoot = tree->getOrCreateNode(SCOPE_ABSTRACT_GLOBAL);
            for(auto rootLocal: nodeRoots){
                ScopeNode* nodeLocalRoot = tree->getOrCreateNode(rootLocal);
                nodeLocalRoot->nodesFrom.push_back(nodeGlobalRoot);
                nodeGlobalRoot->nodesTo.push_back(nodeLocalRoot);
            }
        } else {
            assert(nodeRoots.size()==1);
            tree->nodeRoot = tree->getOrCreateNode(nodeRoots.front());
        }

        return tree;
    }

    CFAGraphAdapter() { }
};
}
} //end of namespace xreate::dominators

namespace llvm {
using namespace xreate::dominators;

template<>
struct GraphTraits<ScopeNode*> {
    typedef ScopeNode NodeType;
    typedef std::list<ScopeNode*>::iterator ChildIteratorType;

    static ChildIteratorType
    child_begin(NodeType* node) {
        return node->nodesTo.begin();
    }

    static ChildIteratorType
    child_end(NodeType* node) {
        return node->nodesTo.end();
    }
};

template<>
struct GraphTraits<CFAGraphAdapter*> : public GraphTraits<ScopeNode*> {
    typedef std::list<ScopeNode>::iterator nodes_iterator;

    static nodes_iterator
    nodes_begin(CFAGraphAdapter* graph) {
        return graph->nodes.begin();
    }

    static nodes_iterator
    nodes_end(CFAGraphAdapter* graph) {
        return graph->nodes.end();
    }

    static NodeType*
    getEntryNode(CFAGraphAdapter* F) {
        return F->nodeRoot;
    }

    static unsigned int
    size(CFAGraphAdapter* graph) {
        return graph->nodes.size();
    }
};


template<>
struct GraphTraits<Inverse<ScopeNode*>>
{
    typedef ScopeNode NodeType;
    typedef std::list<ScopeNode*>::iterator ChildIteratorType;

    static ChildIteratorType
    child_begin(NodeType* node) {
        return node->nodesFrom.begin();
    }

    static ChildIteratorType
    child_end(NodeType* node) {
        return node->nodesFrom.end();
    }
};
}

namespace xreate {
namespace dominators {

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

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

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

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

            dominators.emplace(entry.getFirst()->id, 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 cfa::CFAGraph* graph) {
    boost::scoped_ptr<CFAGraphAdapter> program(CFAGraphAdapter::build(graph));

    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() { }

}
} //end of namespace xreate::dominators


//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;
//        }
//    }
//}