package accrue.analysis.domination;

import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

import polyglot.ast.Call;
import polyglot.ast.CodeNode;
import polyglot.ast.ConstructorCall;
import polyglot.ast.Loop;
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.Item;
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.DataFlowNodeIdentifier;
import accrue.analysis.interprocanalysis.DataFlowNodeIdentifier_c;
import accrue.analysis.interprocanalysis.PreciseDataFlow;
import accrue.analysis.interprocanalysis.Unit;

/**
 * This PreciseDataFlow finds postdominators. For any branch X that is postdominated by a peer Y in the same analysis unit (i.e.,
 * the same code decl), it (a) records with X that it is postdominated by Y, and (b) records with Y that it postdominates X.
 * In addition, this analysis determines the different exit paths from this code decl. This is useful in determining
 * the post dominator of method calls.
 */
public class PostDominatorDataFlow extends
        PreciseDataFlow<ImmediatePostDominator> {

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

    private final ImmediatePostDominatorNull initialDFI =
            new ImmediatePostDominatorNull();
    protected final DominationAnalysisUtil autil;

    private final Map<Peer<ImmediatePostDominator>, Integer> postordering =
            new LinkedHashMap<Peer<ImmediatePostDominator>, Integer>();
    protected final Map<Peer<ImmediatePostDominator>, ImmediatePostDominator> postdoms =
            new LinkedHashMap<Peer<ImmediatePostDominator>, ImmediatePostDominator>();

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

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

    @Override
    protected void dataflow(FlowGraph<ImmediatePostDominator> 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 in a depth first manner
        visit(graph.startPeers().iterator().next(),
              0,
              new HashSet<Peer<ImmediatePostDominator>>());

        super.dataflow(graph);
    }

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

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

        // mark this peer visited
        postordering.put(p, count++);
        return count;
    }

    @Override
    protected Map<EdgeKey, ImmediatePostDominator> flow(
            List<ImmediatePostDominator> inItems, List<EdgeKey> inItemKeys,
            FlowGraph<ImmediatePostDominator> graph,
            Peer<ImmediatePostDominator> peer) {
        ImmediatePostDominator ipd;
        Node n = peer.node();
        if (graph.startPeers().contains(peer)) {
            // this is a start peer, i.e., is the exit node of the method
            ipd = initialDFI;
        }
        else if (peer.preds().size() >= 1
                || (!peer.isEntry() && (n instanceof Call
                        || n instanceof ConstructorCall || n instanceof New))) {
            // need to find the intersection of the post dominators of all of the preds
            ipd = 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);
            }
        }

        postdoms.put(peer, ipd);
        return itemToMap(ipd, peer.succEdgeKeys());
    }

    @Override
    protected void check(FlowGraph<ImmediatePostDominator> graph,
            Peer<ImmediatePostDominator> p) throws SemanticException {
        //record the result if p branches
        if (p.preds().size() > 1
                || (p.isEntry() && p.node() instanceof Loop)
                || (!p.isEntry() && ((p.node() instanceof Call
                        || p.node() instanceof ConstructorCall || p.node() instanceof New)))) {
            ImmediatePostDominator ipd = postdoms.get(p);
            record(ipd, p);
        }
    }

    protected void record(ImmediatePostDominator ipd,
            Peer<ImmediatePostDominator> p) {
        if (ipd instanceof ImmediatePostDominatorIntraPeer) {
            ImmediatePostDominatorIntraPeer ipdip =
                    (ImmediatePostDominatorIntraPeer) ipd;
            recordPostDominatorOf(ipdip.peer.node(), ipdip.peer.peerKey(), p);
            recordPostDominatedBy(p.node(), p.peerKey(), ipdip.peer);

            if (Report.should_report(this.autil.workQueue()
                                               .factory()
                                               .reportTopics(), 2)) {
                Report.report(1,
                              "PostDominatorDataFlow: Recording post dominator of "
                                      + p.node() + " as " + ipdip.peer.node());
            }
        }
        else if (ipd instanceof ImmediatePostDominatorExternal) {
            // the immediate postdominator is external.
            // nothing to record.
        }
    }

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

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

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

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

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

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

    /**
     * Find immediate postdominator for all edges in edges. 
     */
    protected ImmediatePostDominator intersect(
            List<Edge<ImmediatePostDominator>> edges,
            FlowGraph<ImmediatePostDominator> graph) {
        ImmediatePostDominator curr = null;

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

    protected ImmediatePostDominator intersect(ImmediatePostDominator a,
            ImmediatePostDominator b) {
        while (a != null && b != null && !a.equals(b)) {
            if (a instanceof ImmediatePostDominatorExternal
                    && b instanceof ImmediatePostDominatorExternal) {
                // it's external
                return a;

            }
            else if (lessThan(a, b)) {
                // advance a, which must be a ImmediatePostDominatorIntraPeer
                ImmediatePostDominatorIntraPeer intraA =
                        (ImmediatePostDominatorIntraPeer) a;
                a = postdoms.get(intraA.peer);
            }
            else {
                // advance b, which must be a ImmediatePostDominatorIntraPeer
                ImmediatePostDominatorIntraPeer intraB =
                        (ImmediatePostDominatorIntraPeer) b;
                b = postdoms.get(intraB.peer);
            }
        }
        if (a == null) return b;
        return a;
    }

    protected ImmediatePostDominator ipd(Edge<ImmediatePostDominator> e,
            FlowGraph<ImmediatePostDominator> graph) {
        if (graph.exitPeers().contains(e.getTarget())) {
            return new ImmediatePostDominatorExternal();
        }
        return new ImmediatePostDominatorIntraPeer(e.getTarget());
    }

    /**
     * 
     * @return true if a is less than b in the post ordering.
     */
    private boolean lessThan(ImmediatePostDominator a, ImmediatePostDominator b) {
        if (a == null || b == null)
            throw new IllegalArgumentException("Args should be non-null");
        if (a instanceof ImmediatePostDominatorExternal
                && b instanceof ImmediatePostDominatorExternal) {
            throw new InternalCompilerError("Incomparable");
        }
        if (a instanceof ImmediatePostDominatorExternal) {
            return false;
        }
        if (b instanceof ImmediatePostDominatorExternal) {
            return true;
        }
        ImmediatePostDominatorIntraPeer aa =
                (ImmediatePostDominatorIntraPeer) a;
        ImmediatePostDominatorIntraPeer bb =
                (ImmediatePostDominatorIntraPeer) b;
        if (!postordering.containsKey(aa.peer)) {
            // no postordering, it cannot reach the exit node
            return false;
        }
        if (!postordering.containsKey(bb.peer)) {
            // no postordering, it cannot reach the exit node
            return true;
        }
        return postordering.get(aa.peer) < postordering.get(bb.peer);
    }
}

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

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

    public ImmediatePostDominatorIntraPeer(Peer<ImmediatePostDominator> 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 ImmediatePostDominatorIntraPeer)) return false;
        ImmediatePostDominatorIntraPeer other =
                (ImmediatePostDominatorIntraPeer) obj;
        return this.peer.equals(other.peer);
    }

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

}

/**
 * Represents an immediate post dominator outside of this code declaration.
 */
class ImmediatePostDominatorExternal extends ImmediatePostDominator {
    public ImmediatePostDominatorExternal() {
    }

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

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof ImmediatePostDominatorExternal)) return false;
        return true;
    }

    @Override
    public String toString() {
        return "IPD-Unknown";
    }
}

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

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

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