package accrue.analysis.ctldep;

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

import polyglot.ast.Call;
import polyglot.ast.CodeDecl;
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.util.SubtypeSet;
import polyglot.visit.FlowGraph;
import polyglot.visit.FlowGraph.Edge;
import polyglot.visit.FlowGraph.EdgeKey;
import polyglot.visit.FlowGraph.ExceptionEdgeKey;
import polyglot.visit.FlowGraph.Peer;
import polyglot.visit.FlowGraph.PeerKey;
import accrue.analysis.callgraph.PreciseCallGraphFactory;
import accrue.analysis.domination.DominationPass;
import accrue.analysis.ext.AccrueExt;
import accrue.analysis.ext.AccrueExt_c;
import accrue.analysis.ext.ExtTerm;
import accrue.analysis.interprocanalysis.AnalysisContext;
import accrue.analysis.interprocanalysis.DataFlowNodeIdentifier;
import accrue.analysis.interprocanalysis.EdgeIdentifier;
import accrue.analysis.interprocanalysis.EdgeIdentifier_c;
import accrue.analysis.interprocanalysis.ExitMap;
import accrue.analysis.interprocanalysis.NodeIdentifier;
import accrue.analysis.interprocanalysis.NodeIdentifier_c;
import accrue.analysis.interprocanalysis.PreciseDataFlow;

public class CtlDepDataFlow extends PreciseDataFlow<CDAbsVal> {

    protected CtlDepAnalysisUtil autil;
    protected SubtypeSet ignoredExceptions;

    public CtlDepDataFlow(CtlDepAnalysisUtil autil, Job job, TypeSystem ts,
            NodeFactory nf) {
        super(autil, job, ts, nf, true, false, false);
        this.autil = autil;
        this.ignoredExceptions = new SubtypeSet(ts.Throwable());
        this.ignoredExceptions.add(ts.Error());
    }

    public ExitMap<CDAbsVal> dataflow(CodeNode cd, CDAbsVal in)
            throws SemanticException {
        // ignore input since only concerned with intra deps
        super.dataflow(cd);
        return autil.createExitMap(CDAbsVal.BOTTOM);
    }

    @Override
    protected void check(FlowGraph<CDAbsVal> graph, Peer<CDAbsVal> p)
            throws SemanticException {
        CDAbsVal dfIn = p.inItem();
        if (dfIn == null) {
            if (p.node().reachable())
                throw new InternalCompilerError("Null inItem for " + p + " at "
                        + p.node().position());
            else dfIn = createInitialItem(graph, p.node(), p.isEntry());
        }
        recordBranches(dfIn, graph, p);
    }

    @Override
    protected CDAbsVal confluence(List<CDAbsVal> items, Peer<CDAbsVal> peer,
            FlowGraph<CDAbsVal> graph) {
        return CDAbsVal.upperBound(items);
    }

    // @Override
    // protected Map<EdgeKey, CDAbsVal> flow(
    // List<CDAbsVal> inItems, List<EdgeKey> inItemKeys,
    // List<Peer<CDAbsVal>> inItemPeers,
    // List<Boolean> isBackEdges,
    // FlowGraph<CDAbsVal> graph,
    // Peer<CDAbsVal> p) {
    // if (!autil.dropBackEdges())
    // return flow(inItems, inItemKeys, graph, p);
    //
    // Iterator<Boolean> bkIt = isBackEdges.iterator();
    // Iterator<CDAbsVal> avIt = inItems.iterator();
    // List<CDAbsVal> newInItems = new ArrayList<CDAbsVal>();
    // while (bkIt.hasNext()) {
    // boolean isBackEdge = bkIt.next();
    // CDAbsVal vc = avIt.next();
    // if (!isBackEdge)
    // newInItems.add(vc);
    // else {
    // newInItems.add(CDAbsVal.BOTTOM);
    // }
    // }
    // return flow(newInItems, inItemKeys, graph, p);
    // }

    @Override
    protected Map<EdgeKey, CDAbsVal> flow(List<CDAbsVal> inItems,
            List<EdgeKey> inItemKeys, FlowGraph<CDAbsVal> graph,
            Peer<CDAbsVal> peer) {

        CDAbsVal dfIn = safeConfluence(inItems, inItemKeys, peer, graph);
        dfIn = removePostDomDeps(idForPeer(peer), dfIn);
        Map<EdgeKey, CDAbsVal> m = flowControlDeps(dfIn, graph, peer);
        if (!peer.isEntry()) {
            Node n = peer.node();
            if (n instanceof Call) {
                autil.call((Call) n);
            }
            else if (n instanceof New) {
                autil.call((New) n);
            }
            else if (n instanceof ConstructorCall) {
                ConstructorCall cc = (ConstructorCall) n;
                autil.call(cc);
                if (cc.kind().equals(ConstructorCall.SUPER)) {
                    try {
                        autil.analyzeInitializers(CDAbsVal.BOTTOM);
                    }
                    catch (SemanticException e) {
                        throw new InternalCompilerError("Unexpected SemanticException",
                                                        e);
                    }
                }
            }
        }
        return m;
    }

    public DataFlowNodeIdentifier idForPeer(Peer<CDAbsVal> p) {
        return dataFlowNodeIdentifierForPeer(p);
    }

    protected CDAbsVal ENTRY = null;

    @Override
    protected CDAbsVal createInitialItem(FlowGraph<CDAbsVal> graph, Term node,
            boolean entry) {
        if (entry) {
            if (ENTRY == null) {
                Peer<CDAbsVal> p = graph.peer(node, Term.ENTRY);
                ENTRY =
                        new CDAbsVal(null,
                                     new EdgeIdentifier_c(EdgeIdentifier.EDGE_CONTROL,
                                                          idForPeer(p)));
                ENTRY.setParent(ENTRY);
            }
            return ENTRY;
        }
        return CDAbsVal.BOTTOM;
    }

    @Override
    public CtlDepAnalysisUtil autil() {
        return autil;
    }

    public CDAbsVal removePostDomDeps(DataFlowNodeIdentifier nodeID,
            CDAbsVal dfIn) {
        // remove ctl deps that are post-dominated by this node
        Set<EdgeIdentifier> depEdges =
                new HashSet<EdgeIdentifier>(dfIn.controlDeps());
        boolean deps_chg = false;
        for (EdgeIdentifier edge : dfIn.controlDeps()) {
            DataFlowNodeIdentifier depNodeID =
                    (DataFlowNodeIdentifier) edge.getTarget();
            // skip ctldeps on external code or exceptions
            // NodeIdentifier ni = peer.getTarget();
            if (depNodeID.getNode() instanceof CodeDecl) continue;
            AccrueExt niExt = AccrueExt_c.ext(depNodeID.getNode());
            // if the current node is a postdom of a ctl dep, remove that
            // dep
            Set<NodeIdentifier> postdoms =
                    niExt.getAnalysisResult(DominationPass.ANALYSIS_RESULT_IMMED_POST_DOMINATED_BY,
                                            depNodeID.getContext(),
                                            depNodeID.getPeerKey());
            if (postdoms == null) {
                continue;
            }
            if (postdoms.contains(nodeID)) {
                if (Report.should_report(autil().workQueue()
                                                .factory()
                                                .reportTopics(), 3)) {
                    Report.report(3,
                                  "Removing postdominated control dependency "
                                          + depNodeID);
                }
                depEdges.remove(edge);
                deps_chg = true;
            }
        }
        if (deps_chg) {
            // at the exit node of an branching statement, we get 
            // the T/F deps as well as the "real" ctl dep of the 
            // if statement. For other nodes, we will have an empty
            // set here, and need to pop to the parent's dependencies.
            if (depEdges.isEmpty()) dfIn = dfIn.popControlDeps();
        }
        return dfIn;
    }

    protected Map<EdgeKey, CDAbsVal> flowControlDeps(CDAbsVal dfIn,
            FlowGraph<CDAbsVal> graph, Peer<CDAbsVal> peer) {
        DataFlowNodeIdentifier nodeID = idForPeer(peer);
        // Does this peer have multiple successors or a handled exception?
        // TODO: should special case Try here? statements in try block 
        //       are ctl dep on entry to try, but they may also postdominate it.
        if (peer.succs().size() > 1) {
            Map<EdgeKey, CDAbsVal> dfOut =
                    new LinkedHashMap<EdgeKey, CDAbsVal>(peer.succs().size());
            if (Report.should_report(autil().workQueue()
                                            .factory()
                                            .reportTopics(), 3)) {
                Report.report(3, "Adding control dependency at " + peer);
            }
            // Only record control deps for normal termination if
            // Determine what exceptions are handled within the current CodeDecl
            int ignored = 0;
            for (Edge<CDAbsVal> edge : peer.succs()) {
                EdgeKey key = edge.getKey();
                // Flow an exceptional control dependency
                if (key instanceof ExceptionEdgeKey) {

                    ExceptionEdgeKey exc = (ExceptionEdgeKey) key;
                    // we only care about exceptions that DO NOT escape this
                    // method. Interprocedural edges are taken care of in
                    // another anlaysis.
                    if (!(edge.getTarget().node() instanceof CodeDecl)) {
                        dfOut.put(exc,
                                  new CDAbsVal(dfIn,
                                               new EdgeIdentifier_c(EdgeIdentifier.EDGE_CONTROL,
                                                                    nodeID)));

                    }
                    else {
                        // XXX Just flow bottom for these. we take care of them
                        // in the call graph analysis.
                        dfOut.put(exc, dfIn);
                        ignored++;
                    }
                }
                else if (FlowGraph.EDGE_KEY_OTHER.equals(key)) {
                    // Add normal control dependency, but only if any exception
                    // may be thrown and caught
                    if (throwsNonFatalExceptions(peer.node())) {
                        if (Report.should_report(autil.workQueue()
                                                      .factory()
                                                      .reportTopics(), 2)) {
                            Report.report(2, "Creating NT dep for " + peer);
                        }

                        dfOut.put(FlowGraph.EDGE_KEY_OTHER,
                                  new CDAbsVal(dfIn,
                                               new EdgeIdentifier_c(EdgeIdentifier.EDGE_CONTROL,
                                                                    nodeID)));
                    }
                    else {
                        if (Report.should_report(autil.workQueue()
                                                      .factory()
                                                      .reportTopics(), 4)) {
                            Report.report(4, "Omitting NT dep for " + peer);
                        }
                        ignored++;
                        dfOut.put(FlowGraph.EDGE_KEY_OTHER, dfIn);
                    }
                }
                else if (FlowGraph.EDGE_KEY_TRUE.equals(key)) {
                    if (Report.should_report(autil.workQueue()
                                                  .factory()
                                                  .reportTopics(), 2)) {
                        Report.report(2, "Creating a TRUE dep for " + peer);
                    }
                    dfOut.put(FlowGraph.EDGE_KEY_TRUE,
                              new CDAbsVal(dfIn,
                                           new EdgeIdentifier_c(EdgeIdentifier.EDGE_TRUE,
                                                                nodeID)));
                }
                else if (FlowGraph.EDGE_KEY_FALSE.equals(key)) {
                    if (Report.should_report(autil.workQueue()
                                                  .factory()
                                                  .reportTopics(), 2)) {
                        Report.report(2, "Creating a FALSE dep for " + peer);
                    }
                    dfOut.put(FlowGraph.EDGE_KEY_FALSE,
                              new CDAbsVal(dfIn,
                                           new EdgeIdentifier_c(EdgeIdentifier.EDGE_FALSE,
                                                                nodeID)));
                }
                else {
                    throw new InternalCompilerError("Unknown FlowGraph edge: "
                            + key);
                }
            }
            // could be smaller if we had ignorable edges
            if (dfOut.size() - ignored > 1) return dfOut;
        }
        return itemToMap(dfIn, peer.succEdgeKeys());
    }

    /**
     * Returns true if this node throws exceptions that may be caught.
     */
    public boolean throwsNonFatalExceptions(Term n) {
        ExtTerm ext = (ExtTerm) AccrueExt_c.ext(n);
        Set<EdgeIdentifier> catchSites =
                ext.getAnalysisResult(PreciseCallGraphFactory.CATCH_TARGETS,
                                      currentContext());
        if (catchSites == null || catchSites.isEmpty()) {
            //
            if (Report.should_report(autil.workQueue().factory().reportTopics(),
                                     3)) {
                Report.report(3, "All exceptions thrown by " + n
                        + " are fatal.");
            }
            return false;
        }
        return true;
    }

    /**
     * Adds a set of results to the current set
     * 
     * @param resultKey
     *            The key of the analysis result to record.
     * @param rec
     *            The extension object to record these results on.
     * @param ctx
     *            The AnalysisContext to associate these results with.
     * @param pk
     *            The PeerKey to associate these results with.
     * @param results
     */
    public static void addResults(String resultKey, AccrueExt rec,
            AnalysisContext ctx, PeerKey pk, Set<EdgeIdentifier> results) {
        // Get all the control dependencies of this dep
        Set<EdgeIdentifier> cur_results =
                rec.getAnalysisResult(resultKey, ctx, pk);
        // If none exists, create a new one
        if (cur_results == null) {
            cur_results = new HashSet<EdgeIdentifier>();
            rec.recordAnalysisResult(resultKey, ctx, pk, cur_results);
        }
        cur_results.addAll(results);
    }

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

    public void recordBranches(CDAbsVal dfIn, FlowGraph<CDAbsVal> graph,
            Peer<CDAbsVal> peer) {
        DataFlowNodeIdentifier nodeID = idForPeer(peer);
        // assert autil.currentContext() == nodeID.getContext()
        Term n = peer.node();
        // if (peer.isEntry())
        dfIn = removePostDomDeps(nodeID, dfIn);

        Set<EdgeIdentifier> ctlDeps = dfIn.controlDeps();
        // target -> branch
        AccrueExt_c.ext(n)
                   .recordAnalysisResult(CtlDepAnalysisFactory.BRANCH_SOURCES,
                                         autil.currentContext(),
                                         ctlDeps);
        // branch -> target
        for (EdgeIdentifier e : ctlDeps) {
            NodeIdentifier enid = e.getTarget();
            if (!enid.isNative()) {
                Node target = enid.getNode();
                AccrueExt returnExt = AccrueExt_c.ext(target);
                Set<EdgeIdentifier> branches =
                        returnExt.getAnalysisResult(CtlDepAnalysisFactory.BRANCH_TARGETS,
                                                    enid.getContext());
                if (branches == null) {
                    branches = new LinkedHashSet<EdgeIdentifier>();
                    returnExt.recordAnalysisResult(CtlDepAnalysisFactory.BRANCH_TARGETS,
                                                   enid.getContext(),
                                                   branches);
                }
                NodeIdentifier nid =
                        new NodeIdentifier_c(autil.currentContext(), n);
                branches.add(new EdgeIdentifier_c(e.getKey(), nid));
            }
        }
    }
}
