package accrue.analysis.domination;

import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

import polyglot.ast.Call;
import polyglot.ast.CodeNode;
import polyglot.ast.ConstructorCall;
import polyglot.ast.New;
import polyglot.ast.Node;
import polyglot.ast.NodeFactory;
import polyglot.ast.Term;
import polyglot.frontend.Job;
import polyglot.main.Report;
import polyglot.types.SemanticException;
import polyglot.types.TypeSystem;
import polyglot.util.InternalCompilerError;
import polyglot.visit.DataFlow;
import polyglot.visit.FlowGraph;
import polyglot.visit.FlowGraph.Edge;
import polyglot.visit.FlowGraph.EdgeKey;
import polyglot.visit.FlowGraph.Peer;
import polyglot.visit.FlowGraph.PeerKey;
import accrue.analysis.ext.AccrueExt;
import accrue.analysis.ext.AccrueExt_c;
import accrue.analysis.interprocanalysis.AnalysisContext;
import accrue.analysis.interprocanalysis.DataFlowNodeIdentifier;
import accrue.analysis.interprocanalysis.DataFlowNodeIdentifier_c;
import accrue.analysis.interprocanalysis.PreciseDataFlow;
import accrue.analysis.interprocanalysis.Unit;

/**
 * This PreciseDataFlow finds dominators in the control flow graph.
 */
public class DominatorDataFlow extends PreciseDataFlow<ImmediateDominator> {

    public DominatorDataFlow(Job job, TypeSystem ts, NodeFactory nf,
            DominationAnalysisUtil autil) {
        super(autil, job, ts, nf, true);
        this.autil = autil;
    }

    private final ImmediateDominatorNull initialDFI =
            new ImmediateDominatorNull();
    private final DominationAnalysisUtil autil;

    private final Map<Peer<ImmediateDominator>, Integer> postordering =
            new LinkedHashMap<Peer<ImmediateDominator>, Integer>();
    private final Map<Peer<ImmediateDominator>, ImmediateDominator> doms =
            new LinkedHashMap<Peer<ImmediateDominator>, ImmediateDominator>();

    /**
     * Create an initial Item for the dataflow analysis. 
     */
    @Override
    protected ImmediateDominator createInitialItem(
            FlowGraph<ImmediateDominator> graph, Term node, boolean entry) {
        return initialDFI;
    }

    @Override
    protected void dataflow(FlowGraph<ImmediateDominator> graph) {
        if (graph.startPeers().size() != 1) {
            throw new InternalCompilerError("There are "
                    + graph.startPeers().size() + " start peers");
        }
        // construct a post ordering of the peers by visiting each Peer<ImmediateDominator> in a depth first manner
        visit(graph.startPeers().iterator().next(),
              0,
              new HashSet<Peer<ImmediateDominator>>());

        super.dataflow(graph);
    }

    public void performDataflow(CodeNode cd) throws SemanticException {
        dataflow(cd);
    }

    /**
     * Visit Peer<ImmediateDominator> p in order to construct a post ordering of the peers in this graph.
     */
    private int visit(Peer<ImmediateDominator> p, int count,
            Set<Peer<ImmediateDominator>> visited) {
        if (visited.contains(p)) return count;

        // visit all the successors of p, then visit p.
        visited.add(p);
        for (Edge<ImmediateDominator> e : p.succs()) {
            count = visit(e.getTarget(), count, visited);
        }

        // mark this Peer<ImmediateDominator> visited
        postordering.put(p, count++);
        return count;
    }

    @Override
    protected Map<EdgeKey, ImmediateDominator> flow(
            List<ImmediateDominator> inItems, List<EdgeKey> inItemKeys,
            FlowGraph<ImmediateDominator> graph, Peer<ImmediateDominator> peer) {
        ImmediateDominator id;
        Node n = peer.node();
        if (graph.startPeers().contains(peer)) {
            // this is a start Peer<ImmediateDominator>, i.e., is the entry node of the method
            id = initialDFI;
        }
        else if (peer.preds().size() >= 1) {
            // need to find the intersection of the post dominators of all of the preds
            id = intersect(peer.preds(), graph);
        }
        else {
            throw new InternalCompilerError("Don't know how to handle this case");
        }

        if (!peer.isEntry()) {
            if (n instanceof Call) {
                Call c = (Call) n;
                autil.call(c.methodInstance(), c);
            }
            else if (n instanceof ConstructorCall) {
                ConstructorCall cc = (ConstructorCall) n;
                autil.constructorCall(cc.constructorInstance(), cc);
                if (cc.kind().equals(ConstructorCall.SUPER)) {
                    try {
                        autil.analyzeInitializers(Unit.UNIT);
                    }
                    catch (SemanticException e) {
                        throw new InternalCompilerError(e);
                    }
                }
            }
            else if (n instanceof New) {
                New nn = (New) n;
                autil.call(nn.constructorInstance(), nn);
            }
        }

        doms.put(peer, id);
        return itemToMap(id, peer.succEdgeKeys());
    }

    @Override
    protected void check(FlowGraph<ImmediateDominator> graph,
            Peer<ImmediateDominator> p) throws SemanticException {
        //record the result if p branches
        if (p.preds().size() > 1) {
            ImmediateDominator id = doms.get(p);
            record(id, p);
        }
    }

    private void record(ImmediateDominator ipd, Peer<ImmediateDominator> p) {
        if (ipd instanceof ImmediateDominatorIntraPeer) {
            ImmediateDominatorIntraPeer ipdip =
                    (ImmediateDominatorIntraPeer) ipd;
            recordDominatorOf(ipdip.peer.node(), ipdip.peer.peerKey(), p);
            recordDominatedBy(p.node(), p.peerKey(), ipdip.peer);

            if (Report.should_report(this.autil.workQueue()
                                               .factory()
                                               .reportTopics(), 2)) {
                Report.report(1, "DominatorDataFlow: Recording dominator of "
                        + p.node() + " as " + ipdip.peer.node());
            }
        }
    }

    private void recordDominatorOf(Node n, PeerKey peerKey,
            Peer<ImmediateDominator> p) {
        AccrueExt ext = AccrueExt_c.ext(n);

        Set<DataFlowNodeIdentifier> s =
                ext.getAnalysisResult(DominationPass.ANALYSIS_RESULT_IMMED_DOMINATOR_OF,
                                      autil.currentContext(),
                                      peerKey);
        if (s == null) {
            s = new HashSet<DataFlowNodeIdentifier>();
            ext.recordAnalysisResult(DominationPass.ANALYSIS_RESULT_IMMED_DOMINATOR_OF,
                                     autil.currentContext(),
                                     peerKey,
                                     s);
        }
        s.add(new DataFlowNodeIdentifier_c(autil.currentContext(),
                                           p.peerKey(),
                                           p.node()));
    }

    private void recordDominatedBy(Node n, PeerKey peerKey,
            Peer<ImmediateDominator> p) {
        AccrueExt ext = AccrueExt_c.ext(n);

        Set<DataFlowNodeIdentifier> s =
                ext.getAnalysisResult(DominationPass.ANALYSIS_RESULT_IMMED_DOMINATED_BY,
                                      autil.currentContext(),
                                      peerKey);
        if (s == null) {
            s = new HashSet<DataFlowNodeIdentifier>();
            ext.recordAnalysisResult(DominationPass.ANALYSIS_RESULT_IMMED_DOMINATED_BY,
                                     autil.currentContext(),
                                     peerKey,
                                     s);
        }
        s.add(new DataFlowNodeIdentifier_c(autil.currentContext(),
                                           p.peerKey(),
                                           p.node()));
    }

    @Override
    protected void check(FlowGraph<ImmediateDominator> graph, Term n,
            boolean entry, ImmediateDominator inItem,
            Map<EdgeKey, ImmediateDominator> outItems) throws SemanticException {
        throw new InternalCompilerError("Unsupported");
    }

    @Override
    protected ImmediateDominator confluence(List<ImmediateDominator> items,
            Peer<ImmediateDominator> peer, FlowGraph<ImmediateDominator> graph) {
        return initialDFI;
        //throw new InternalCompilerError("Unsupported: confluence of " + items + " for " + node);
    }

    /**
     * Find immediate Dominator for all edges in edges. 
     */
    private ImmediateDominator intersect(List<Edge<ImmediateDominator>> edges,
            FlowGraph<ImmediateDominator> graph) {
        ImmediateDominatorIntraPeer curr = null;

        for (Edge<ImmediateDominator> e : edges) {
            ImmediateDominatorIntraPeer d =
                    (ImmediateDominatorIntraPeer) ipd(e, graph);
            // set curr to the dominator of curr and d
            if (curr == null) {
                curr = d;
            }
            else {
                curr = intersect(curr, d);
            }
        }
        return curr;
    }

    private ImmediateDominatorIntraPeer intersect(
            ImmediateDominatorIntraPeer a, ImmediateDominatorIntraPeer b) {
        while (a != null && b != null && !a.equals(b)) {
            // if a or b has no post ordering, then it is unreachable.
            if (!postordering.containsKey(a.peer)) {
                a = null;
                continue;
            }
            if (!postordering.containsKey(b.peer)) {
                b = null;
                continue;
            }

            if (lessThan(a, b)) {
                // advance a
                a = (ImmediateDominatorIntraPeer) doms.get(a.peer);
            }
            else {
                // advance b
                b = (ImmediateDominatorIntraPeer) doms.get(b.peer);
            }
        }
        if (a == null) return b;
        return a;
    }

    private ImmediateDominator ipd(Edge<ImmediateDominator> e,
            FlowGraph<ImmediateDominator> graph) {
        return new ImmediateDominatorIntraPeer(e.getTarget());
    }

    /**
     * 
     * @return true if a is less than b in the post ordering.
     */
    private boolean lessThan(ImmediateDominatorIntraPeer a,
            ImmediateDominatorIntraPeer b) {
        if (a == null || b == null)
            throw new IllegalArgumentException("Args should be non-null");
        return postordering.get(a.peer) < postordering.get(b.peer);
    }

    /**
     * Returns the set of all dominators of the given Peer<ImmediateDominator> within the flow graph.
     * Assumes that the Dominator analysis results have been recorded already.
     * Creates a new Set to return the results in (i.e., clients are free to alter the set)
     * @param  
     */
    public static <FlowItem extends DataFlow.Item> Set<DataFlowNodeIdentifier> dominatorsOf(
            DataFlowNodeIdentifier source, FlowGraph<FlowItem> graph,
            AnalysisContext currentContext) {
        Queue<DataFlowNodeIdentifier> queue =
                new LinkedList<DataFlowNodeIdentifier>();
        Set<DataFlowNodeIdentifier> doms =
                new LinkedHashSet<DataFlowNodeIdentifier>();
        queue.add(source);

        while (!queue.isEmpty()) {
            DataFlowNodeIdentifier current = queue.remove();
            if (current != source) doms.add(current);

            Peer<FlowItem> currentPeer =
                    peerForDataFlowNodeIdentifier(current, graph);
            if (graph.entryPeers().contains(currentPeer)) {
                // nothing to do, it's the entry of the current procedure
            }
            else if (currentPeer.preds().size() == 1) {
                // only a single predecessor
                Edge<FlowItem> e = currentPeer.preds().iterator().next();
                queue.add(dataFlowNodeIdentifierForPeer(e.getTarget(),
                                                        currentContext));
            }
            else if (currentPeer.preds().size() == 0) {
                // no predecessors, nothing to do
            }
            else {
                // there are 2 or more peers
                AccrueExt ext = AccrueExt_c.ext(currentPeer.node());

                Set<DataFlowNodeIdentifier> domBy =
                        ext.getAnalysisResult(DominationPass.ANALYSIS_RESULT_IMMED_DOMINATED_BY,
                                              currentContext,
                                              currentPeer.peerKey());
                if (domBy != null) {
                    // add all immediate dominators to the results.
                    queue.addAll(domBy);
                }
                else {
                    throw new InternalCompilerError("Should have domination results!"
                            + current);
                }
            }
        }
        return doms;
    }
}

/**
 * Represents the immediate post dominator of a branch in this code declaration.
 * The immediate post dominator may be a Peer<ImmediateDominator> in the same code declaration, or it may be
 * that the branch is not post dominated by a Peer<ImmediateDominator> in this code declaration, in which case
 * we record the exit edges of this code declaration that the branch may take.
 */
abstract class ImmediateDominator extends DataFlow.Item {
}

/**
 * Represents an immediate post dominator in this code declaration.
 */
class ImmediateDominatorIntraPeer extends ImmediateDominator {
    final Peer<ImmediateDominator> peer;

    public ImmediateDominatorIntraPeer(Peer<ImmediateDominator> peer) {
        this.peer = peer;
    }

    @Override
    public int hashCode() {
        return peer.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof ImmediateDominatorIntraPeer)) return false;
        ImmediateDominatorIntraPeer other = (ImmediateDominatorIntraPeer) obj;
        return this.peer.equals(other.peer);
    }

    @Override
    public String toString() {
        return "IDIntra-" + peer;
    }

}

class ImmediateDominatorNull extends ImmediateDominator {
    @Override
    public boolean equals(Object i) {
        return i instanceof ImmediateDominatorNull;
    }

    @Override
    public int hashCode() {
        return -348574;
    }

    @Override
    public String toString() {
        return "NULL-ID";
    }
}
