package accrue.analysis.callgraph;

import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

import polyglot.ast.Block;
import polyglot.ast.Call;
import polyglot.ast.CodeNode;
import polyglot.ast.CompoundStmt;
import polyglot.ast.ConstructorCall;
import polyglot.ast.ConstructorDecl;
import polyglot.ast.Eval;
import polyglot.ast.Expr;
import polyglot.ast.If;
import polyglot.ast.Labeled;
import polyglot.ast.Loop;
import polyglot.ast.Node;
import polyglot.ast.ProcedureDecl;
import polyglot.ast.Return;
import polyglot.ast.Special;
import polyglot.ast.Synchronized;
import polyglot.ast.Term;
import polyglot.ast.Throw;
import polyglot.ast.Try;
import polyglot.main.Report;
import polyglot.types.ClassType;
import polyglot.types.ConstructorInstance;
import polyglot.types.MethodInstance;
import polyglot.types.ProcedureInstance;
import polyglot.types.SemanticException;
import polyglot.types.Type;
import polyglot.util.InternalCompilerError;
import accrue.AccrueExtensionInfo;
import accrue.analysis.ext.AccrueExt;
import accrue.analysis.ext.AccrueExt_c;
import accrue.analysis.ext.ExtCall;
import accrue.analysis.ext.ExtConstructorDecl;
import accrue.analysis.ext.ExtTerm;
import accrue.analysis.interprocanalysis.AnalysisContext;
import accrue.analysis.interprocanalysis.AnalysisUnit;
import accrue.analysis.interprocanalysis.AnalysisUtil;
import accrue.analysis.interprocanalysis.EdgeIdentifier;
import accrue.analysis.interprocanalysis.EdgeIdentifier.ExceptionEdge;
import accrue.analysis.interprocanalysis.EdgeIdentifier_c;
import accrue.analysis.interprocanalysis.ExitMap;
import accrue.analysis.interprocanalysis.NativeNodeIdentifier_c;
import accrue.analysis.interprocanalysis.NodeIdentifier;
import accrue.analysis.interprocanalysis.NodeIdentifier_c;
import accrue.analysis.interprocanalysis.WorkQueue;
import accrue.analysis.pointer.HContext;
import accrue.analysis.preciseExceptions.ThrowableType;

public class PreciseCallGraphAnalysisUtil extends AnalysisUtil<PCGAbsVal> {

    public PreciseCallGraphAnalysisUtil(WorkQueue<PCGAbsVal> workQueue,
            AnalysisUnit currentAnalysisUnit, AccrueExtensionInfo extInfo) {
        super(workQueue, currentAnalysisUnit, extInfo);
    }

    @Override
    public ExitMap<PCGAbsVal> analyze(CodeNode n, PCGAbsVal before)
            throws SemanticException {
        PreciseCallGraphVisitor v = new PreciseCallGraphVisitor(this);
        return createExitMap(v.performVisit(n));
    }

    @Override
    @Deprecated
    public ExitMap<PCGAbsVal> analyzeInitializers(PCGAbsVal input)
            throws SemanticException {
        throw new UnsupportedOperationException("Use analyzeInitializers(ConstructorCall, PCGAbsVal) instead");
    }

    public ExitMap<PCGAbsVal> analyzeInitializers(ConstructorCall cc,
            PCGAbsVal input) throws SemanticException {
        if (Report.should_report(this.workQueue.factory().reportTopics(), 3))
            Report.report(1, "Analyzing initializers in " + currentClass()
                    + " for " + analysisName());

        this.instanceInitializersChecked = true;
        List<CodeNode> toProcess =
                workQueue.registrar().getInstanceInitializers(currentClass());

        ExitMap<PCGAbsVal> res = workQueue().emptyExitMap();
        PCGAbsVal nt = input;
        res = res.normalTermination(nt);

        if (Report.should_report(this.workQueue.factory().reportTopics(), 2))
            Report.report(1, "Processing " + toProcess.size()
                    + " instance initializers");

        AnalysisContext fromContext = currentContext();
        EdgeIdentifier fromExit =
                new EdgeIdentifier_c(EdgeIdentifier.EDGE_INIT,
                                     new NodeIdentifier_c(fromContext, cc));

        for (CodeNode i : toProcess) {
            ExtTerm to = (ExtTerm) AccrueExt_c.ext(i);

            if (Report.should_report(this.workQueue.factory().reportTopics(), 3))
                Report.report(2, "Processing an instance initializer " + i);

            if (i.codeInstance().flags().isStatic()) {
                throw new InternalCompilerError("Should only have instance initializers here");
            }
            // analyze the initializer
            AnalysisUnit calleeAUnit =
                    new AnalysisUnit(i,
                                     this.currentContext()
                                         .constructorContext((ConstructorInstance) this.currentAnalysisUnit()
                                                                                       .procedureDecl()
                                                                                       .procedureInstance()));

            recordInitializerEdge(fromExit, to, calleeAUnit.context());

            fromExit =
                    new EdgeIdentifier_c(EdgeIdentifier.EDGE_INIT,
                                         new NodeIdentifier_c(calleeAUnit.context(),
                                                              i));
            fromContext = calleeAUnit.context();
            res =
                    res.upperBound(this.workQueue.getAnalysisResult(calleeAUnit,
                                                                    nt,
                                                                    this));
            // Add the input back in here because ignores it but
            // we still need to chain together the exception analyses of all of
            // the
            // initializers
            nt = nt.upperBound(res.normalTermination());
            res = res.removeNormalTermination();
        }

        return res.normalTermination(nt);
    }

    private void recordInitializerEdge(EdgeIdentifier fromExit, ExtTerm to,
            AnalysisContext toContext) {
        NodeIdentifier fromid = fromExit.getTarget();
        ExtTerm from = (ExtTerm) AccrueExt_c.ext(fromid.getNode());

        // from -> to
        Set<EdgeIdentifier> from_out =
                from.getAnalysisResult(PreciseCallGraphFactory.INIT_TARGETS,
                                       fromid.getContext());
        if (from_out == null) {
            from_out = new LinkedHashSet<EdgeIdentifier>();
            from.recordAnalysisResult(PreciseCallGraphFactory.INIT_TARGETS,
                                      fromid.getContext(),
                                      from_out);
        }
        EdgeIdentifier toEdge =
                new EdgeIdentifier_c(EdgeIdentifier.EDGE_INIT,
                                     new NodeIdentifier_c(toContext,
                                                          (Term) to.node()));
        from_out.add(toEdge);

        // to -> from
        Set<EdgeIdentifier> to_in =
                to.getAnalysisResult(PreciseCallGraphFactory.INIT_SOURCES,
                                     toContext);
        if (to_in == null) {
            to_in = new LinkedHashSet<EdgeIdentifier>();
            to.recordAnalysisResult(PreciseCallGraphFactory.INIT_SOURCES,
                                    toContext,
                                    to_in);
        }
        to_in.add(fromExit);
    }

    public PCGAbsVal call(MethodInstance mi, Call n) {
        Set<EdgeIdentifier> targets = new HashSet<EdgeIdentifier>();
        PCGAbsVal res;
        boolean isStaticCall = mi.flags().isStatic();
        if (isStaticCall) {
            res =
                    callNonVirtual(mi,
                                   workQueue.factory()
                                            .createAnalysisContext(this,
                                                                   mi,
                                                                   null,
                                                                   n),
                                   targets,
                                   n);
        }
        else {
            // this is a non-static call (and may be
            // a virtual call, or a call to super.m())
            // loop over the possible receivers.
            Expr receiver = (Expr) n.target();
            Set<HContext> pointsTo = pointsTo(receiver);

            if (pointsTo == null) {
                throw new InternalCompilerError("No points to info for the receiver: "
                        + n);
            }

            // analyze all method implementations that may potentially be
            // called, and
            // take an upper bound of the result.
            res = PCGAbsVal.EMPTY;
            for (HContext o : pointsTo) {
                // analyze the implementing method
                Type receiverType = o.type();
                MethodInstance omi = null;
                if (receiver instanceof Special
                        && ((Special) receiver).kind() == Special.SUPER) {
                    // it's a call to super.m(). Don't dynamically dismatch.
                    omi = mi;
                }
                else if (receiverType != null) {
                    omi =
                            extInfo.typeSystem()
                                   .findImplementingMethod(receiverType.toClass(),
                                                           mi);
                }
                else {
                    // System.err.println(" *** no receiver for virtual method invocation to "
                    // + mi + " " + n.position());
                    throw new InternalCompilerError("no receiver for virtual method invocation to "
                                                            + mi,
                                                    n.position());
                }
                if (omi == null) {
                    // no implementing method!
                    // we'll see if we have a signature for mi
                    omi = mi;
                }
                PCGAbsVal dfi =
                        callNonVirtual(omi,
                                       workQueue.factory()
                                                .createAnalysisContext(this,
                                                                       omi,
                                                                       o,
                                                                       n),
                                       targets,
                                       n);
                res = res.upperBound(dfi);
            }

            if (pointsTo.isEmpty()) {
                // suppress for strings
                if (!mi.container().equals(typeSystem().String())) {
                    System.err.println(" *** Receiver doesn't point to anything! May be a bug in the program? ");
                    System.err.println("     " + n + " " + mi.container() + "."
                            + mi.name() + "  at " + n.position());
                }
                // let's just do the best we can...
                PCGAbsVal dfi =
                        this.guessAnalysisForMissingCode(mi,
                                                         currentContext() /* XXX: should we do better? */,
                                                         targets,
                                                         n);
                res = res.upperBound(dfi);
            }
        }
        recordCallTargets(n, targets);
        return res;
    }

    public PCGAbsVal call(ConstructorInstance ci, Expr n) {
        Set<HContext> pointsTo = pointsTo(n);
        Set<EdgeIdentifier> targets = new HashSet<EdgeIdentifier>();
        if (pointsTo.size() > 1) {
            throw new InternalCompilerError("Invocation to constructor does not have unique pointsto: "
                                                    + pointsTo,
                                            n.position());
        }
        if (pointsTo.isEmpty()) {
            throw new InternalCompilerError("Constructor invocation doesn't point to anything!",
                                            n.position());

        }
        PCGAbsVal res =
                callNonVirtual(ci,
                               workQueue.factory()
                                        .createAnalysisContext(this,
                                                               ci,
                                                               pointsTo.iterator()
                                                                       .next(),
                                                               n),
                               targets,
                               n);
        recordCallTargets(n, targets);
        return res;
    }

    public PCGAbsVal constructorCall(ConstructorInstance ci, ConstructorCall n) {
        ConstructorDecl cd =
                (ConstructorDecl) this.currentAnalysisUnit().codeNode();
        ExtConstructorDecl ext = (ExtConstructorDecl) AccrueExt_c.ext(cd);
        Set<HContext> pointsTo =
                pointsTo(ext.getThisNode(), this.currentContext(), this.extInfo);
        if (pointsTo.isEmpty()) {
            throw new InternalCompilerError("Constructor invocation doesn't point to anything!",
                                            n.position());

        }
        else {
            Set<EdgeIdentifier> targets = new HashSet<EdgeIdentifier>();
            PCGAbsVal res = PCGAbsVal.EMPTY;

            for (HContext o : pointsTo) {
                PCGAbsVal dfi =
                        callNonVirtual(ci,
                                       workQueue.factory()
                                                .createAnalysisContext(this,
                                                                       ci,
                                                                       o,
                                                                       n),
                                       targets,
                                       n);
                res = res.upperBound(dfi);
            }
            recordCallTargets(n, targets);
            return res;
        }
    }

    /**
     * A non-virtual call to a method instance
     */
    private PCGAbsVal callNonVirtual(ProcedureInstance pi,
            AnalysisContext calleeContext, Set<EdgeIdentifier> targets,
            Term callSite) {
        // get the implementing method body to add the argument names...
        ProcedureDecl pd = (ProcedureDecl) workQueue.registrar().getCode(pi);
        AnalysisUnit callee = null;

        PCGAbsVal res;
        if (pd == null || pd.body() == null) {
            res =
                    guessAnalysisForMissingCode(pi,
                                                calleeContext,
                                                targets,
                                                callSite);
        }
        else {

            callee = new AnalysisUnit(pd, calleeContext);
            targets.add(new EdgeIdentifier_c(EdgeIdentifier.EDGE_CALL,
                                             new NodeIdentifier_c(calleeContext,
                                                                  pd)));
            try {
                ExitMap<PCGAbsVal> r =
                        this.workQueue.getAnalysisResult(callee,
                                                         PCGAbsVal.EMPTY,
                                                         this);
                res = r.normalTermination();
            }
            catch (SemanticException e) {
                throw new InternalCompilerError("Unexpected semantic exception",
                                                e);
            }
        }
        return res;
    }

    private PCGAbsVal guessAnalysisForMissingCode(ProcedureInstance pi,
            AnalysisContext calleeContext, Set<EdgeIdentifier> targets,
            Term callSite) {
        ExtTerm ext = (ExtTerm) AccrueExt_c.ext(callSite);
        Collection<ThrowableType> throwTypes =
                ext.throwTypes(pi.typeSystem(), currentContext());
        Set<EdgeIdentifier> throwSites = new HashSet<EdgeIdentifier>();
        for (ThrowableType t : throwTypes) {
            throwSites.add(new EdgeIdentifier_c(new ExceptionEdge((ClassType) t.type()),
                                                new NativeNodeIdentifier_c(calleeContext,
                                                                           pi)));
        }
        targets.add(new EdgeIdentifier_c(EdgeIdentifier.EDGE_CALL,
                                         new NativeNodeIdentifier_c(calleeContext,
                                                                    pi)));
        EdgeIdentifier ret =
                new EdgeIdentifier_c(EdgeIdentifier.EDGE_RETURN,
                                     new NativeNodeIdentifier_c(calleeContext,
                                                                pi));
        return new PCGAbsVal(new HashSet<ThrowableType>(throwTypes),
                             throwSites,
                             Collections.singleton(ret),
                             true);
    }

    public boolean canTerminateNormally(Node n) {
        if (n instanceof Call) {
            ExtCall ext = (ExtCall) AccrueExt_c.ext(n);
            return ext.canTerminateNormally(currentContext());
        }
        if (n instanceof Eval) return canTerminateNormally(((Eval) n).expr());
        if (n instanceof Return) {
            Return ret = (Return) n;
            if (ret.expr() == null) return true;
            return canTerminateNormally(ret.expr());
        }
        if (n instanceof Expr) return true;

        if (n instanceof Throw) return false;
        if (n instanceof CodeNode)
            return canTerminateNormally(((CodeNode) n).codeBody());
        if (!(n instanceof CompoundStmt)) return true;

        if (n instanceof Loop) return true;
        if (n instanceof Block) {
            Block b = (Block) n;
            if (b.statements().isEmpty()) return true;
            return canTerminateNormally(b.statements().get(b.statements()
                                                            .size() - 1));
        }
        if (n instanceof Labeled)
            return canTerminateNormally(((Labeled) n).statement());
        if (n instanceof Synchronized)
            return canTerminateNormally(((Synchronized) n).body());
        if (n instanceof If) {
            If i = (If) n;
            return (canTerminateNormally(i.consequent()) || canTerminateNormally(i.alternative()));
        }
        if (n instanceof Try) {
            Try t = (Try) n;
            if (t.finallyBlock() != null
                    && !canTerminateNormally(t.finallyBlock())) {
                // finally block can't terminate normally
                return false;
            }
            // let's be imprecise and just say it can
            return true;
        }
        throw new InternalCompilerError("Haven't implemented handling of " + n);
    }

    /**
     * There is a many-to-many relationship between call sites and CodeDecls. A
     * call site in a certain AnalysisContext has many potential target
     * CodeDecls, each with a distinct calleeContext.
     * 
     * callSite@currentContext <--> codeDecl@calleeContext
     */
    protected void recordCallTargets(Term n, Set<EdgeIdentifier> targets) {
        // call -> codedecl
        AccrueExt_c.ext(n)
                   .recordAnalysisResult(PreciseCallGraphFactory.CALL_TARGETS,
                                         currentContext(),
                                         targets);
        // codedecl -> call
        for (EdgeIdentifier e : targets) {
            NodeIdentifier enid = e.getTarget();
            if (!enid.isNative()) {
                Node target = enid.getNode();
                AccrueExt targetExt = AccrueExt_c.ext(target);
                Set<EdgeIdentifier> sources =
                        targetExt.getAnalysisResult(PreciseCallGraphFactory.CALL_SOURCES,
                                                    enid.getContext());
                if (sources == null) {
                    sources = new LinkedHashSet<EdgeIdentifier>();
                    targetExt.recordAnalysisResult(PreciseCallGraphFactory.CALL_SOURCES,
                                                   enid.getContext(),
                                                   sources);
                }
                NodeIdentifier nid = new NodeIdentifier_c(currentContext(), n);
                sources.add(new EdgeIdentifier_c(EdgeIdentifier.EDGE_CALL, nid));
            }
        }
    }
}
