/* 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 if (nodeRoots.size()==1){
//            tree->nodeRoot = tree->getOrCreateNode(nodeRoots.front());
//
//        } else {
//            ScopeNode* nodeGlobalRoot = tree->getOrCreateNode(SCOPE_ABSTRACT_GLOBAL);
//            tree->nodeRoot = nodeGlobalRoot;
//        }
//
//        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, false> {
//public:
//    DominatorTree() : llvm::DominatorTreeBase<ScopeNode, false>() {}
//
//    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)
//                <<std::endl;
//        }
//    }
//
//private:
//    DominatorsTreeAnalysisProvider::Dominators dominators;
//};
//
//class PostDominatorTree : public llvm::DominatorTreeBase<ScopeNode, true> {
//public:
//    PostDominatorTree() : llvm::DominatorTreeBase<ScopeNode, true>() {}
//
//    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)
//                <<std::endl;
//        }
//    }
//
//private:
//    DominatorsTreeAnalysisProvider::Dominators dominators;
//};
//

class DominatorsProviderPrivate{
public:
    DominatorsProviderPrivate()
//        : treeForwardDominators(new DominatorTree())
//        , treePostDominators(new PostDominatorTree())
    { }

//    boost::scoped_ptr<DominatorTree> treeForwardDominators;
//    boost::scoped_ptr<PostDominatorTree> treePostDominators;
};


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()
    : __private(new DominatorsProviderPrivate()) {}

DominatorsTreeAnalysisProvider::~DominatorsTreeAnalysisProvider() { }


}} //end of namespace xreate::dominators