/* 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/.
 *
 * versionspass.cpp
 *
 * Author: pgess <v.melnychenko@xreate.org>
 * Created on January 4, 2017, 3:13 PM
 */

/** \class xreate::versions::VersionsPass
 * Has two parts:
 * - Validates correctness of versioned variables with regard to  variables lifespan
 * - Determines versioned variables computation order
 * \sa VersionsScopeDecorator, VersionsGraph, [Versions Concept](/w/concepts/versions)
 */

#include <boost/optional/optional.hpp>
#include "pass/versionspass.h"

namespace std{
    std::size_t
    hash<xreate::versions::SymbolOrPlaceholder>::operator()(xreate::versions::SymbolOrPlaceholder const& s) const
    {return std::hash<xreate::Symbol>()(s.symbol) + (s.flagEndOfLifePlaceholder? 9849 : 1);}

    bool
    equal_to<xreate::versions::SymbolOrPlaceholder>::operator()(const xreate::versions::SymbolOrPlaceholder& __x, const xreate::versions::SymbolOrPlaceholder& __y) const
    { return __x.flagEndOfLifePlaceholder == __y.flagEndOfLifePlaceholder && __x.symbol == __y.symbol; }
}

using namespace std;

namespace xreate{ namespace versions{

template<>
std::list<Symbol>
defaultValue<std::list<Symbol>>(){
    return std::list<Symbol>();
};

inline std::string
printSymbol(const SymbolOrPlaceholder& s){
    switch(s.flagEndOfLifePlaceholder){
        case SYMBOL: return string("(") + std::to_string(s.symbol.identifier.id) + ", "+ std::to_string(s.symbol.identifier.version) + ")";
        case PLACEHOLDER: return string("(") + std::to_string(s.symbol.identifier.id) + ", "+ std::to_string(s.symbol.identifier.version) + ")+";
    }

    return "";
}

void
VersionsGraph::__debug_print(std::ostream& output) const{
    for(auto entry: __inferiors){
        output << printSymbol(entry.second) << " <-" << printSymbol(entry.first) << "\n";
    }
}

void
VersionsGraph::defineEndOfLife(const Symbol& symbol, const Symbol& symbolSuccessor){
    if(__dictSuccessors.count(symbol)){
        assert("No version branches allowed yet" && false);
    }

    const SymbolOrPlaceholder& placeholder = getEndOfLife(symbol);

    auto inferiorsDeferred = __inferiors.equal_range(placeholder);
    std::unordered_multimap<SymbolOrPlaceholder, SymbolOrPlaceholder> inferiorsReassigned;

    for (const auto& inf: boost::make_iterator_range(inferiorsDeferred)){
        inferiorsReassigned.emplace(SymbolOrPlaceholder{SYMBOL, symbolSuccessor}, inf.second);
    }

    __inferiors.erase(placeholder);
    __inferiors.insert(inferiorsReassigned.begin(), inferiorsReassigned.end());
    __inferiors.emplace(SymbolOrPlaceholder{SYMBOL, symbolSuccessor}, SymbolOrPlaceholder{SYMBOL, symbol});

    __dictSuccessors.emplace(symbol, symbolSuccessor);
}

SymbolOrPlaceholder
VersionsGraph::getEndOfLife(const Symbol& s){
    if (__dictSuccessors.count(s)){
        return SymbolOrPlaceholder{SYMBOL, __dictSuccessors.at(s)};    }


    return SymbolOrPlaceholder{PLACEHOLDER, s};
}

void
VersionsGraph::applyNatualDependencies(const Symbol& symbol, const std::list<Symbol>& dependencies){
    for (const Symbol& right: dependencies){
        __inferiorsNatural.emplace(symbol, right);
    }
}

void
VersionsGraph::applyDependentEndOfLife(const SymbolOrPlaceholder& symbol, const list<Symbol>& dependencies){
    for (const Symbol& right: dependencies){
        auto rightEOF = getEndOfLife(right);

        __inferiors.emplace(rightEOF, symbol);
    }
}

bool
VersionsGraph::tryEliminateEofAliases(const std::list<SymbolOrPlaceholder>& aliases){

    if (aliases.size()==1){
        return true;
    }

    boost::optional<Symbol> symbolActualEoF;
    for(const SymbolOrPlaceholder alias: aliases){
        switch(alias.flagEndOfLifePlaceholder){
            case SYMBOL:
                if(symbolActualEoF){
                    return false;
                }

                symbolActualEoF = alias.symbol;
                break;

            case PLACEHOLDER:
                continue;
        }
    }

    if(!symbolActualEoF){
        return false;
    }

    for(const SymbolOrPlaceholder alias: aliases){
        switch(alias.flagEndOfLifePlaceholder){
            case SYMBOL:
                continue;

            case PLACEHOLDER:
                defineEndOfLife(alias.symbol, symbolActualEoF.get());
                break;
        }
    }

    return true;
}

std::list<SymbolOrPlaceholder>
VersionsGraph::extractCycle(const Path& path, const SymbolOrPlaceholder& symbolBeginning){
    unsigned int posBeginning = path.at(symbolBeginning);

    std::list<SymbolOrPlaceholder> result;

    auto i=path.begin();
    while(true){
        i = std::find_if(i, path.end(), [&posBeginning](const auto& el){return el.second >=posBeginning;});

        if (i!= path.end()){
            result.push_back(i->first);
            ++i;

        } else {break; }
    }

    return result;
}

bool
VersionsGraph::validateCycles(const SymbolOrPlaceholder& s,
                            std::unordered_multimap<SymbolOrPlaceholder, SymbolOrPlaceholder>& graph,
                            std::unordered_set<SymbolOrPlaceholder>& symbolsVisited,
                            Path& path)
{
    if (symbolsVisited.count(s)) return true;

    symbolsVisited.insert(s);
    path.emplace(s, path.size());

    if (graph.count(s)){
        //iterate over imposed dependencies
        auto candidates = graph.equal_range(s);
        for (auto candidate = candidates.first; candidate != candidates.second; ++candidate){
            if (path.count(candidate->second)) {
                std::list<SymbolOrPlaceholder> cycle = extractCycle(path, candidate->second);
                if (!tryEliminateEofAliases(cycle)) return false;
                continue;
            }

            if(!validateCycles(candidate->second, graph, symbolsVisited, path)) return false;
        }
    }

        //iterate over natural dependencies
    if (s.flagEndOfLifePlaceholder == SYMBOL) {
        auto candidates = __inferiorsNatural.equal_range(s.symbol);
        for (auto candidate = candidates.first; candidate != candidates.second; ++candidate){
            if (path.count(SymbolOrPlaceholder{SYMBOL, candidate->second})){
                return false;
            }

            if(!validateCycles(SymbolOrPlaceholder{SYMBOL,candidate->second}, graph, symbolsVisited, path)) return false;
        }
    }

        //check previous version
    if (s.flagEndOfLifePlaceholder == PLACEHOLDER){
        const Symbol& candidate = s.symbol;

        if (path.count(SymbolOrPlaceholder{SYMBOL, candidate})){
            std::list<SymbolOrPlaceholder> cycle = extractCycle(path, SymbolOrPlaceholder{SYMBOL, candidate});
            if (!tryEliminateEofAliases(cycle)) return false;
        }

        if(!validateCycles(SymbolOrPlaceholder{SYMBOL,candidate}, graph, symbolsVisited, path)) return false;
    }

    path.erase(s);
    return true;
}

bool
VersionsGraph::validateCycles(){
    std::unordered_set<SymbolOrPlaceholder> symbolsVisited;
    Path path;
    std::unordered_multimap<SymbolOrPlaceholder, SymbolOrPlaceholder> graph(__inferiors);

    std::unordered_multimap<SymbolOrPlaceholder, SymbolOrPlaceholder>::const_iterator s;
    for (s = graph.begin(); s != graph.end(); ++s){
        if(!validateCycles(s->first, graph, symbolsVisited, path)) return false;
    }

    return true;
}

bool
VersionsGraph::validate(){
    return validateCycles();
}

std::list<Symbol>
VersionsGraph::expandPlaceholder(const SymbolOrPlaceholder& symbol, const Symbol& symbolPrev) const{
    std::list<Symbol> result;

    switch (symbol.flagEndOfLifePlaceholder){
        case SYMBOL:
            //skip self-loops
            if (symbol.symbol == symbolPrev) return {};

            return {symbol.symbol};

        case PLACEHOLDER:
            for (const auto& entry: boost::make_iterator_range(__inferiors.equal_range(symbol))){
                list<Symbol>&& childResult = expandPlaceholder(entry.second, symbolPrev);
                result.insert(result.end(), childResult.begin(), childResult.end());
            }

            if (__dictSuccessors.count(symbol.symbol)){
                Symbol knownSuccessor = __dictSuccessors.at(symbol.symbol);

                //skip alias loop
                if (knownSuccessor == symbolPrev) return {};

                for (const auto& entry: boost::make_iterator_range(__inferiors.equal_range(SymbolOrPlaceholder{SYMBOL, knownSuccessor}))){
                    list<Symbol>&& childResult = expandPlaceholder(entry.second, knownSuccessor);
                    result.insert(result.end(), childResult.begin(), childResult.end());
                }
            }

            break;
    }

    return result;
}

AttachmentsContainerDefault<std::list<Symbol>>*
VersionsGraph::representAsAttachments() const {
    AttachmentsContainerDefault<std::list<Symbol>>* container =  new AttachmentsContainerDefault<std::list<Symbol>>();

    std::map<Symbol, std::list<Symbol>> containerData;

    for(const auto& entry: __inferiors){
        if(entry.first.flagEndOfLifePlaceholder == PLACEHOLDER) continue;

        list<Symbol>& infs = containerData[entry.first.symbol];
        list<Symbol>&& infsExpanded = expandPlaceholder(entry.second, entry.first.symbol);
        infs.insert(infs.begin(), infsExpanded.begin(), infsExpanded.end());
    }

    for(const auto& entry: containerData){
        container->put(entry.first, entry.second);
    }

    return container;
}

std::list<Symbol>
VersionsPass::process(const Expression& expression, PassContext context, const std::string& hintSymbol){
    if (expression.__state == Expression::COMPOUND){
        std::list<Symbol> resultDependencies;

        for (const Expression &op: expression.getOperands()) {
            std::list<Symbol> deps = process(op, context);

            resultDependencies.insert(resultDependencies.end(), deps.begin(), deps.end());
        }

        for (CodeScope* scope: expression.blocks) {
            std::list<Symbol> deps = Parent::process(scope, context);

            resultDependencies.insert(resultDependencies.end(), deps.begin(), deps.end());
        }

        return resultDependencies;
    }

    if (expression.__state == Expression::IDENT){
        const Symbol symb = Attachments::get<IdentifierSymbol>(expression);

        return processSymbol(symb, context, expression.getValueString());
    }

    return {};
}

//TODO versions, check (declaration.isDefined()) before processing declaration
list<Symbol>
VersionsPass::processSymbol(const Symbol& symbol, PassContext context, const std::string& hintSymbol){
    list<Symbol> result{symbol};

    if (__symbolsVisited.exists(symbol)){
        return result;
    }
    enum {MODE_ALIAS, MODE_COPY } mode = MODE_ALIAS;

    const Expression& declaration = CodeScope::getDefinition(symbol);

    if (declaration.op == Operator::CALL_INTRINSIC){
        if (declaration.getValueString() == "copy"){
            mode = MODE_COPY;
        }
    }

    if (symbol.identifier.version != VERSION_NONE){
        mode = MODE_COPY;

        if (symbol.identifier.version > 0){
            Symbol versionPrev = Symbol{ScopedSymbol{symbol.identifier.id, symbol.identifier.version-1}, symbol.scope};
            __graph.defineEndOfLife(versionPrev, symbol);
        }
    }

    PassContext context2 = context.updateScope(symbol.scope);
    std::list<Symbol> dependencies = process(declaration, context2, hintSymbol);

    switch (mode) {
        case MODE_COPY: __graph.applyDependentEndOfLife(SymbolOrPlaceholder{SYMBOL, symbol}, dependencies); break;
        case MODE_ALIAS: __graph.applyDependentEndOfLife(__graph.getEndOfLife(symbol), dependencies); break;
    }

    __graph.applyNatualDependencies(symbol, dependencies);
    __symbolsVisited.put(symbol, true);
    return list<Symbol>{symbol};
}

VersionsGraph&
VersionsPass::getResultGraph(){
    return __graph;
}

void
VersionsPass::finish(){
    assert(__graph.validate() && "Can't validate versions graph");

    Attachments::init<VersionImposedDependency>(__graph.representAsAttachments());
}

}} //end of namespace xreate::versions