package accrue.analysis.pointer;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

import polyglot.frontend.ExtensionInfo;
import polyglot.main.Report;
import polyglot.types.ProcedureInstance;
import polyglot.util.ErrorInfo;
import accrue.analysis.AnalysisTopics;
import accrue.analysis.pointer.StmtRegistrar.CodeInfo;
import accrue.analysis.pointer.analyses.HeapAbstractionFactory;

public class PointsToEngineSingleThread extends PointsToEngine {
    public PointsToEngineSingleThread(HeapAbstractionFactory haf) {
        super(haf);
    }

    @Override
    public PointsToGraph solveImpl(StmtRegistrar registrar,
            ExtensionInfo extInfo) {
        return solveSmarter(registrar, extInfo);
        //return solveSimple(registrar, extInfo);
    }

    /**
     * A simple and inefficient solution technique: iterate through all statements
     * until no more changes
     */
    public PointsToGraph solveSimple(StmtRegistrar registrar,
            ExtensionInfo extInfo) {
        PointsToGraphSerial g =
                new PointsToGraphSerial(this.heapAbstractionFactory(),
                                        registrar);
        g.setRecordUsage(false);
        boolean changed = true;

        if (Report.should_report(AnalysisTopics.POINTSTO, 1)) {
            Report.report(1, registrar.stmts().size()
                    + " pointer statements to process");
        }

        // We'll be very inefficient, and just go over the list until
        // nothing changes. We could sort the procedure instances
        // by the call graph, and process the stmts in topo order,
        // waiting until strongly connected components do not change.
        // That should reduce the number of times we need to go through
        // the list. 
        int count = 0;
        while (changed) {
            changed = false;
            int changeCount = 0;
            int totalCount = 0;
            for (PointsToStmt s : registrar.stmts()) {
                // check whether we need to timeout 
                checkTimeout();

                for (CContext context : new ArrayList<CContext>(g.getContexts(s.codeInstance))) {
                    boolean thisChanged =
                            s.process(context,
                                      g,
                                      registrar,
                                      this.heapAbstractionFactory(),
                                      new StmtAndContext(s, context));
                    if (thisChanged) changeCount++;
                    totalCount++;

                    changed = thisChanged || changed;
                }
            }
            count++;
            if (Report.should_report(AnalysisTopics.POINTSTO, 2)) {
                Report.report(2, "Completed iteration " + count
                        + " through statements: number of nodes: "
                        + g.getDomain().size() + " edges : " + g.edgeSize());
                Report.report(2, "          Stmts changing/stmts considered: "
                        + changeCount + " / " + totalCount);
            }
        }
        long end = System.currentTimeMillis();

        if (Report.should_report(AnalysisTopics.POINTSTO, 1)) {
            Report.report(1, "Iterated through statements " + count
                    + " times (" + (end - this.startTime()) + " millisecs)");
        }
        //        System.err.println("Dumping call graph");
        //        g.callGraph.dump(System.err);

        // record warnings about missing code.
        for (ErrorInfo ei : registrar.missingCode()) {
            extInfo.compiler().errorQueue().enqueue(ei);
        }

        return g;
    }

    private LinkedList<StmtAndContext> queue = new LinkedList<StmtAndContext>();
    private Set<StmtAndContext> queueMembers = new HashSet<StmtAndContext>();
    private Map<PointsToGraphNode, Set<StmtAndContext>> depedencies =
            new HashMap<PointsToGraphNode, Set<StmtAndContext>>();

    /**
     * A better solution techniques that tracks dependencies between points-to sets
     * and statements.
     */
    public PointsToGraphSerial solveSmarter(StmtRegistrar registrar,
            ExtensionInfo extInfo) {
        PointsToGraphSerial g =
                new PointsToGraphSerial(this.heapAbstractionFactory(),
                                        registrar);
        if (Report.should_report(AnalysisTopics.POINTSTO, 1)) {
            Report.report(1, "Starting PointsTo Engine using "
                    + heapAbstractionFactory().getClass().getSimpleName());
            Report.report(1, registrar.stmts().size()
                    + " pointer statements to process");
        }

        // add all the initial stmts and their contexts to the list. 
        for (PointsToStmt s : registrar.stmts()) {
            for (CContext context : g.getContexts(s.codeInstance)) {
                addToQueue(new StmtAndContext(s, context));
            }
        }

        int count = 0;
        while (!queue.isEmpty()) {
            StmtAndContext active = queue.removeFirst();
            queueMembers.remove(active);

            active.stmt.process(active.context,
                                g,
                                registrar,
                                this.heapAbstractionFactory(),
                                active);
            count++;

            if (count % (1 << 20) == 0) {
                // see if we want to timeout yet.
                checkTimeout();
            }
//            if (count % 10000 == 0) {
//                System.err.println("Process statement " + count
//                        + "  and total size: " + g.totalSize());
//            }

            // gather the dependencies from g
            Map<ProcedureInstance, Set<CContext>> newContexts =
                    g.getAndClearNewContexts();
            Set<PointsToGraphNode> changedNodes = g.getAndClearChangedNodes();
            Set<PointsToGraphNode> readNodes = g.getAndClearReadNodes();

            // there have been some new contexts added.
            for (ProcedureInstance pi : newContexts.keySet()) {
                CodeInfo codeInfo = registrar.getCodeInfo(pi);
                if (codeInfo != null) {
                    for (PointsToStmt s : registrar.stmtsForCode(pi)) {
                        for (CContext context : newContexts.get(pi)) {
                            addToQueue(new StmtAndContext(s, context));
                        }
                    }
                }
            }

            // read nodes are nodes that this Foo depends on.
            // i.e., if a readNode changes, then this statement should be recomputed.
            for (PointsToGraphNode n : readNodes) {
                addDependencies(n, active);
            }

            // changed nodes have changed, so wake up some things
            for (PointsToGraphNode n : changedNodes) {
                addToQueue(getDependencies(n));
            }

            if (count % 10000 == 0) {
                if (Report.should_report(AnalysisTopics.POINTSTO, 1)) {
                    long curTime = System.currentTimeMillis();
                    Report.report(1, count + "\t"
                            + (curTime - this.startTime()));
//                    Report.report(1, "  number of nodes: " + g.nodeSize()
//                            + " total size : " + g.totalSize());
                }
            }
        }

        g.setRecordUsage(false);

        checkReachedFixedpoint(registrar, g);

        long end = System.currentTimeMillis();

        if (Report.should_report(AnalysisTopics.POINTSTO, 1)) {
            Report.report(1, "Processed " + count + " statements ("
                    + (end - this.startTime()) + " millisecs)");
            Report.report(1, "  number of nodes: " + g.getDomain().size()
                    + " total size : " + g.edgeSize());
        }

        if (Report.should_report(AnalysisTopics.POINTSTOGRAPH, 2)) {
            g.dumpPointsToGraph(2);
        }
        else if (Report.should_report(AnalysisTopics.POINTSTOGRAPH, 1)) {
            g.dumpPointsToGraph(1);
        }

        // record warnings about missing code.
        for (ErrorInfo ei : registrar.missingCode()) {
            extInfo.compiler().errorQueue().enqueue(ei);
        }

        return g;
    }

    private void addDependencies(PointsToGraphNode n, StmtAndContext foo) {
        Set<StmtAndContext> s = depedencies.get(n);
        if (s == null) {
            s = new HashSet<StmtAndContext>();
            depedencies.put(n, s);
        }
        s.add(foo);
    }

    private Collection<StmtAndContext> getDependencies(PointsToGraphNode n) {
        Collection<StmtAndContext> ret = depedencies.get(n);
        if (ret == null) return Collections.emptySet();
        return ret;
    }

    private void addToQueue(StmtAndContext foo) {
        if (!queueMembers.contains(foo)) {
            queue.addLast(foo);
            queueMembers.add(foo);
        }
    }

    private void addToQueue(Collection<StmtAndContext> foos) {
        for (StmtAndContext foo : foos) {
            addToQueue(foo);
        }
    }

    @Override
    void recordRead(StmtAndContext sac, PointsToGraphNode r) {
        throw new UnsupportedOperationException();
    }

    @Override
    void newContext(ProcedureInstance callee, CContext calleeContext) {
        throw new UnsupportedOperationException();
    }

    @Override
    void changedNode(PointsToGraphNode n) {
        throw new UnsupportedOperationException();
    }
}
