package accrue.analysis.interprocvarcontext;

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

import polyglot.ast.Call;
import polyglot.ast.ConstructorCall;
import polyglot.ast.ConstructorDecl;
import polyglot.ast.Expr;
import polyglot.ast.Formal;
import polyglot.ast.New;
import polyglot.ast.ProcedureDecl;
import polyglot.ast.Special;
import polyglot.ast.Term;
import polyglot.main.Report;
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_c;
import accrue.analysis.ext.ExtCall;
import accrue.analysis.ext.ExtConstructorCall;
import accrue.analysis.ext.ExtConstructorDecl;
import accrue.analysis.ext.ExtNew;
import accrue.analysis.interprocanalysis.AnalysisContext;
import accrue.analysis.interprocanalysis.AnalysisUnit;
import accrue.analysis.interprocanalysis.DataFlowNodeIdentifier;
import accrue.analysis.interprocanalysis.ExitMap;
import accrue.analysis.interprocanalysis.ExitMap.ExceptionKey;
import accrue.analysis.interprocanalysis.ExitMap.Key;
import accrue.analysis.interprocanalysis.Ordered;
import accrue.analysis.interprocanalysis.WorkQueue;
import accrue.analysis.pointer.HContext;

/**
 * Abstract utility class for performing an interprocedural dataflow analysis.
 * 
 * @param <A>
 *            Type of analysis results
 * @param <T>
 *            Value type for analysis items in the context
 */
public abstract class AnalysisUtilVarContextDataFlow<A extends Ordered<A>, T extends AbstractValue<T>>
        extends AnalysisUtilVarContext<A, T> {

    /**
     * Create a new utility class
     * 
     * @param workQueue
     *            Queue of analysis units
     * @param currentAnalysisUnit
     *            Current analysis unit from the queue
     * @param extInfo
     *            compiler analysis unit
     */
    public AnalysisUtilVarContextDataFlow(WorkQueue<A> workQueue,
            AnalysisUnit currentAnalysisUnit, AccrueExtensionInfo extInfo) {
        super(workQueue, currentAnalysisUnit, extInfo);
    }

    /**
     * Process a call to <code>ci</code> with {@link VarContext}
     * <code>input</code>. 
     * 
     * @param ci
     *            constructor to analyze
     * @param input
     *            variable context before analyzing the method
     * @param receiverAbsVal
     *            The abstract value to use for the newly created object, i.e.,
     *            the abstract value that "this" will map to in the invoked constructor.            
     * @param callSite
     *            the site of the call to the constructor
     * 
     * @return new map of variables to their values after the analysis
     * @throws SemanticException
     *             if analysis fails
     */
    public FinalVarContext<T> callFromNew(ConstructorInstance ci,
            VarContext<T> input, T receiverAbsVal,
            DataFlowNodeIdentifier callSite) throws SemanticException {
        New n = (New) callSite.getNode();
        if (input == null) return this.emptyFinalVarContext();
        Set<HContext> pointsTo = pointsTo(n);
        if (pointsTo.size() > 1) {
            throw new InternalCompilerError("Invocation to constructor does not have unique pointsto: "
                                                    + pointsTo,
                                            n.position());
        }
        if (pointsTo.isEmpty()) {
            // XXX MISSING RECIEVER COMMENT
            // System.err.println(" *** Receiver of new doesn't point to anything! May be a bug in the program? ");
            // System.err.println("     " + n + " " + ci.container()+"."+
            // ci.signature() + "  at " + n.position());
            return this.getAnalysisForMissingReceiver(ci, input, n, callSite);
        }
        HContext receiver = pointsTo.iterator().next();
        return callNonVirtual(ci,
                              workQueue.factory()
                                       .createAnalysisContext(this,
                                                              ci,
                                                              receiver,
                                                              n),
                              receiver,
                              receiverAbsVal,
                              input,
                              callSite,
                              ((ExtNew) AccrueExt_c.ext(n)).canTerminateNormally(callSite.getContext()));
    }

    /**
     * Process a call to <code>mi</code> with {@link VarContext}
     * <code>input</code>.
     * 
     * @param mi
     *            method to analyze
     * @param input
     *            variable context before analyzing the method
     * @param callSite
     *            the call site of the method call
     * 
     * @return new map of variables to their values after the analysis
     * @throws SemanticException
     *             if analysis fails
     */
    public FinalVarContext<T> call(MethodInstance mi, VarContext<T> input,
            DataFlowNodeIdentifier callSite) throws SemanticException {
        Call n = (Call) callSite.getNode();

        ExtCall ext = (ExtCall) AccrueExt_c.ext(n);
        boolean canTerminateNormally =
                ext.canTerminateNormally(this.currentContext());

        boolean isStaticCall = mi.flags().isStatic();
        if (isStaticCall) {
            return callNonVirtual(mi,
                                  workQueue.factory()
                                           .createAnalysisContext(this,
                                                                  mi,
                                                                  null,
                                                                  n),
                                  null,
                                  null,
                                  input,
                                  callSite,
                                  canTerminateNormally);
        }
        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.
            Map<HContext, FinalVarContext<T>> resMap =
                    new LinkedHashMap<HContext, FinalVarContext<T>>();
            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 dispatch.
                    omi = mi;
                }
                else if (receiverType != null) {
                    // it's a virtual call, so find
                    // the appropriate implementing method.
                    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;
                }
                resMap.put(o,
                           callNonVirtual(omi,
                                          workQueue.factory()
                                                   .createAnalysisContext(this,
                                                                          omi,
                                                                          o,
                                                                          n),
                                          o,
                                          null,
                                          input,
                                          callSite,
                                          canTerminateNormally));
            }
            FinalVarContext<T> res = mergeCallResults(resMap, callSite);
            if (pointsTo.isEmpty()) {
                // XXX MISSING RECIEVER COMMENT
                // 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());
                res =
                        this.getAnalysisForMissingReceiver(mi,
                                                           input,
                                                           n,
                                                           callSite);
            }

            return res;
        }
    }

    /**
     * Merge the results of analyzing a virtual method call which may have
     * multiple targets
     * 
     * @param resMap
     *            Map of heap contexts to analysis results
     * @param callSite
     *            DFI for the call site of the call
     * @param graph
     *            Control flow graph
     * @return Context with the results for different targets merged
     */
    protected FinalVarContext<T> mergeCallResults(
            Map<HContext, FinalVarContext<T>> resMap,
            DataFlowNodeIdentifier callSite) {
        FinalVarContext<T> res = emptyFinalVarContext();
        for (FinalVarContext<T> c : resMap.values()) {
            res = (FinalVarContext<T>) res.upperBound(c);
        }
        return res;
    }

    /**
     * Process a call to a non-virtual call to <code>pi</code> with
     * {@link VarContext} <code>input</code>.
     * 
     * @param pi
     *            call to analyze
     * @param calleeContext
     *            procedure analysis context
     * @param receiver
     *            abstract heap object for the callee
     * @param preCall
     *            variable context before analyzing the method
     * @param callSite
     *            the call site for the procedure call
     * @param canTerminateNormally
     *            true if the called procedure can terminate normally
     * 
     * @return new map of variables to their values after the analysis
     * @throws SemanticException
     *             if analysis fails
     */
    public FinalVarContext<T> callNonVirtual(ProcedureInstance pi,
            AnalysisContext calleeContext, HContext receiver, T receiverAbsVal,
            VarContext<T> preCall, DataFlowNodeIdentifier callSite,
            boolean canTerminateNormally) throws SemanticException {
        Term n = callSite.getNode();
        if (Report.should_report(this.workQueue.factory().reportTopics(), 3)) {
            Report.report(2, this.workQueue.factory().analysisName()
                    + ": callNonVirtual " + pi);
        }

        if (preCall == null) {
            // no point in processing this...
            if (Report.should_report(this.workQueue.factory().reportTopics(), 4)) {
                Report.report(3, "Null input context, so skipping call to "
                        + pi);
            }

            if (!canTerminateNormally) {
                return (FinalVarContext<T>) this.emptyFinalVarContext()
                                                .removeNormalTermination();
            }
            return this.emptyFinalVarContext();
        }

        preCall = preCallNonVirtual(pi, calleeContext, preCall, n);

        int numArgs = pi.formalTypes().size();
        List<T> argAbsVals = preCall.peekExprResults(numArgs);
        // reverse the list of argAbsVals since they are given to us in stack
        // order (i.e., last arg is at the top of the stack, and is in position
        // 0).
        Collections.reverse(argAbsVals);
        preCall = preCall.popExprResults(numArgs);

        if (Report.should_report(this.workQueue.factory().reportTopics(), 4)) {
            Report.report(3, "   argAbsVals : " + argAbsVals);
        }

        if (pi instanceof MethodInstance) {
            // The receiver is on the expression stack.
            T t = preCall.peekExprResult();
            if (receiverAbsVal == null) {
                receiverAbsVal = t;
            }
            preCall = preCall.popExprResult();
        }
        else if (n instanceof New) {
            // the type node is on the expression stack.
            preCall = preCall.popExprResult();
        }

        SuspendedExecutionStack<T> precallSuspendedExecutionStack =
                preCall.suspendedExecutionStack();
        if (precallSuspendedExecutionStack == null) {
            precallSuspendedExecutionStack =
                    SuspendedExecutionStack.emptyStack();
        }
        VarContext<T> input = preCall.popSuspendedExecutionStackToDepth(0);

        // get the implementing method body to add the argument names...
        ProcedureDecl pd = (ProcedureDecl) workQueue.registrar().getCode(pi);
        AnalysisUnit callee = null;

        boolean preparedCalleeContext = false;
        FinalVarContext<T> res;
        if (pd == null || pd.body() == null) {
            LibrarySignature<A, T> sig =
                    this.getSignatureForMissingCode(pi,
                                                    receiverAbsVal,
                                                    argAbsVals);
            if (sig != null) {
                res =
                        sig.process(pi,
                                    calleeContext,
                                    receiver,
                                    input,
                                    receiverAbsVal,
                                    argAbsVals,
                                    this,
                                    computeExpectedExits(n),
                                    callSite);
                if (res == null)
                    throw new InternalCompilerError("Null returned by signature: "
                            + sig.getClass());
                if (!canTerminateNormally) {
                    res = (FinalVarContext<T>) res.removeNormalTermination();
                }

                // restore preCall context elements
                res = res.restoreContext(preCall, false);

                return res;
            }
            else {
                recordMissingCode(pi);
                res =
                        guessAnalysisForMissingCode(pi,
                                                    calleeContext,
                                                    receiver,
                                                    input,
                                                    receiverAbsVal,
                                                    argAbsVals,
                                                    computeExpectedExits(n),
                                                    callSite);
                if (!canTerminateNormally) {
                    res = (FinalVarContext<T>) res.removeNormalTermination();
                }

                // restore preCall context elements
                res = res.restoreContext(preCall, false);

                return res;
            }
        }
        else {
            callee = new AnalysisUnit(pd, calleeContext);
            VarContext<T> beforeCall =
                    prepareCalleeContext(callee,
                                         receiverAbsVal,
                                         argAbsVals,
                                         input,
                                         callSite);
            res =
                    this.getAnalysisResultsFromWorkQueue(callee,
                                                         beforeCall,
                                                         callSite);
            if (maybeRecursiveCall(callee)) {
                res = this.handleRecursiveCall(res, beforeCall, callee);
            }
            preparedCalleeContext = true;

        }

        // join the return context and the normal termination context
        res =
                (FinalVarContext<T>) res.normalTermination(upperBound(res.normalTermination(),
                                                                      res.returnItem()));

        res = (FinalVarContext<T>) res.removeReturnItem();

        // Restore the appropriate elements of the caller context
        res = res.restoreContext(preCall, preparedCalleeContext);

        // restore the result stack on the normal termination only.
        if (res.normalTermination() != null) {
            VarContext<T> nt = res.normalTermination();

            // push the return value if there was one.
            if (pi instanceof MethodInstance) {
                MethodInstance mi = (MethodInstance) pi;
                if (!mi.returnType().isVoid()) {
                    // this method should have returned a result.
                    // it may not have, if we haven't actually got around to
                    // processing it yet.
                    T returnedResult = res.normalTermination().returnResult();
                    if (returnedResult == null) {
                        returnedResult = this.bottomAbstractValue();
                    }
                    nt = nt.pushExprResult(returnedResult, "returnX2-" + pi);
                }
            }

            nt = nt.clearReturnResult();

            res = (FinalVarContext<T>) res.normalTermination(nt);
        }

        if (!canTerminateNormally) {
            res = (FinalVarContext<T>) res.removeNormalTermination();
        }

        return res;
    }

    /**
     * Get analysis results for procedures for which the source code is missing.
     * 
     * @param pi 
     *          procedure instance for which the code is missing
     * @param calleeContext 
     *          context for the procedure missing source code
     * @param receiver 
     *          Abstract heap object for the receiver of the missing procedure
     * @param input 
     *          context before analyzing the missing procedure
     * @param receiverAbsVal 
     *          abstract value for the receiver of the missing procedure
     * @param argAbsVals 
     *          abstract values for the arguments to the missing procedure
     * @param computeExpectedExits 
     *          expected exit keys for the missing procedure (for many analyses 
     *          the {@link FinalVarContext} must have an entry for each exit key)
     * @param callSite 
     *          AST node and analysis context for the call site
     *          
     * @return {@link FinalVarContext} estimating the results of analyzing the 
     *          missing code 
     */
    protected FinalVarContext<T> guessAnalysisForMissingCode(
            ProcedureInstance pi, AnalysisContext calleeContext,
            HContext receiver, VarContext<T> input, T receiverAbsVal,
            List<T> argAbsVals, Set<Key> computeExpectedExits,
            DataFlowNodeIdentifier callSite) {
        return guessAnalysisForMissingCode(pi,
                                           calleeContext,
                                           receiver,
                                           input,
                                           receiverAbsVal,
                                           argAbsVals,
                                           computeExpectedExits,
                                           callSite.getNode());
    }

    /**
     * Create a new context appropriate for analyzing the method instance
     * 
     * @param callee
     *            Analysis unit for the callee
     * @param receiverAbsVal
     *            value for the reciever
     * @param argAbsVals
     *            list of values for the procedure arguments
     * @param callerPreCall
     *            variable context before the procedure call
     * @param callSite
     *            procedure call site
     * @return new variable context ready for the procedure analysis
     */
    protected VarContext<T> prepareCalleeContext(AnalysisUnit callee,
            T receiverAbsVal, List<T> argAbsVals, VarContext<T> callerPreCall,
            DataFlowNodeIdentifier callSite) {
        // Create a new context appropriate for analyzing the method instance
        Map<String, T> newLocals = new LinkedHashMap<String, T>();
        if (receiverAbsVal != null
                && !callee.procedureDecl()
                          .procedureInstance()
                          .flags()
                          .isStatic()) {
            newLocals.put("this", receiverAbsVal);
        }

        List<Formal> calleeFormals = callee.procedureDecl().formals();
        if (calleeFormals.size() != argAbsVals.size()) {
            throw new InternalCompilerError("Mismatched arguments");
        }
        for (int i = 0; i < argAbsVals.size(); i++) {
            Formal f = calleeFormals.get(i);
            T arg = argAbsVals.get(i);
            newLocals.put(f.name(), arg);
        }
        return callerPreCall.locals(newLocals)
                            .clearExprResultStack()
                            .suspendedExecutionStack(SuspendedExecutionStack.<T> emptyStack());
    }

    /**
     * Process a call to <code>ci</code> with {@link VarContext}
     * <code>input</code>. This is different from call(ConstructorInstance ci, 
     * VarContext<T> input, T receiverAbsVal, DataFlowNodeIdentifier callSite), which is used when a
     *  "new C(...)" expression is encountered. By contrast, this is used when
     *  a "this(...)" or "super(...)" constructor call is encountered.
     * 
     * @param ci
     *            constructor to analyze
     * @param input
     *            variable context before analyzing the method
     * @param callSite
     *            the site of the call to the constructor
     * 
     * @return new map of variables to their values after the analysis
     * @throws SemanticException
     *             if analysis fails
     */
    public FinalVarContext<T> constructorCallFromConstructor(
            ConstructorInstance ci, VarContext<T> input,
            DataFlowNodeIdentifier callSite) throws SemanticException {
        // Make sure we are called from an appropriate place 
        ConstructorCall cc = (ConstructorCall) callSite.getNode();

        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()) {
            // XXX MISSING RECIEVER COMMENT
//            System.err.println(" *** Receiver of constructor doesn't point to anything! May be a bug in the program? ");
//            System.err.println("     current context is "
//                    + this.currentContext());
//            System.err.println("     should we be using a different context? the callee context is :"
//                    + this.currentContext());
//            System.err.println("     this node is " + ext.getThisNode()
//                    + " for constructor decl " + cd + " in container "
//                    + ci.container() + "." + ci.signature() + "  at "
//                    + ext.getThisNode());

            return this.getAnalysisForMissingReceiver(ci, input, cc, callSite);
        }
        else {
            FinalVarContext<T> res = this.emptyFinalVarContext();
            for (HContext receiver : pointsTo) {
                AnalysisContext calleeContext =
                        workQueue.factory().createAnalysisContext(this,
                                                                  ci,
                                                                  receiver,
                                                                  cc);
                res =
                        (FinalVarContext<T>) res.upperBound(callNonVirtual(ci,
                                                                           calleeContext,
                                                                           receiver,
                                                                           input.getLocalAbsVal("this",
                                                                                                ci.container()),
                                                                           input,
                                                                           callSite,
                                                                           ((ExtConstructorCall) AccrueExt_c.ext(callSite.getNode())).canTerminateNormally(callSite.getContext())));
//                System.err.println("Analyzing constructor call to " + ci
//                        + " and res keys are " + res.allKeys());
            }
            return res;
        }
    }

    /**
     * Use
     * {@link #call(ConstructorInstance, VarContext, DataFlowNodeIdentifier)}
     */
    @Deprecated
    @Override
    public final FinalVarContext<T> call(ConstructorInstance ci,
            VarContext<T> input, T receiverAbsVal, New n,
            DataFlowNodeIdentifier callSiteNode) throws SemanticException {
        throw new UnsupportedOperationException("AnalysisUtilVarContext call methods are not supported for AnalysisUtilDataFlow.  Use the dataflow-specific counterparts.");
    }

    /**
     * Use {@link #call(MethodInstance, VarContext, DataFlowNodeIdentifier)}
     */
    @Deprecated
    @Override
    public final FinalVarContext<T> call(MethodInstance mi,
            VarContext<T> input, Call n, DataFlowNodeIdentifier callSiteNode)
            throws SemanticException {
        throw new UnsupportedOperationException("AnalysisUtilVarContext call methods are not supported for AnalysisUtilDataFlow.  Use the dataflow-specific counterparts.");
    }

    /**
     * Use
     * {@link #constructorCall(ConstructorInstance, VarContext, DataFlowNodeIdentifier)}
     */
    @Deprecated
    @Override
    public final FinalVarContext<T> constructorCall(ConstructorInstance ci,
            VarContext<T> input, ConstructorCall n,
            DataFlowNodeIdentifier callSiteNode) throws SemanticException {
        throw new UnsupportedOperationException("AnalysisUtilVarContext call methods are not supported for AnalysisUtilDataFlow.  Use the dataflow-specific counterparts.");
    }

    /**
     * Use
     * {@link #getAnalysisResultsFromWorkQueue(AnalysisUnit, VarContext, DataFlowNodeIdentifier)}
     */
    @Deprecated
    @Override
    protected final FinalVarContext<T> getAnalysisResultsFromWorkQueue(
            AnalysisUnit callee, VarContext<T> beforeCall)
            throws SemanticException {
        throw new UnsupportedOperationException("AnalysisUtilVarContext call methods are not supported for AnalysisUtilDataFlow.  Use the dataflow-specific counterparts.");
    }

    /**
     * Get the analysis results for the given callee and variable context.
     * 
     * @param callee
     *            Code for a callee that is to be analyzed
     * @param beforeCall
     *            variable context before the call to the callee
     * @return new variable context after performing the analysis
     * @throws SemanticException
     *             thrown for an analysis error
     */
    protected abstract FinalVarContext<T> getAnalysisResultsFromWorkQueue(
            AnalysisUnit callee, VarContext<T> beforeCall,
            DataFlowNodeIdentifier callSite) throws SemanticException;

    /**
     * Analyze the initializers for the current analysis unit given the current
     * analysis results
     * 
     * @param input
     *            current analysis results
     * @return Map from exit condition to analysis result
     * @throws SemanticException
     *             thrown if the analysis fails
     */
    public abstract FinalVarContext<T> analyzeInitializersForDataFlow(
            VarContext<T> before) throws SemanticException;

    /**
     * Make a final var context for the given normal and exceptional var
     * contexts
     * 
     * @param expectedExits
     *            Exit keys
     * @param normal
     *            var context for normal termination
     * @param exceptional
     *            var context for an exception path
     * @return final var context for the given normal and exceptional var
     *         contexts
     */
    protected FinalVarContext<T> makeFinalVarContext(
            Set<ExitMap.Key> expectedExits, VarContext<T> normal,
            VarContext<T> exceptional) {
        FinalVarContext<T> ret = this.createFinalVarContext(normal);
        if (!expectedExits.contains(ExitMap.KEY_NORM_TERM)) {
            ret = (FinalVarContext<T>) ret.removeNormalTermination();
        }
        for (ExitMap.Key k : expectedExits) {
            if (ExitMap.KEY_NORM_TERM.equals(k)) {
                // already in there
                continue;
            }
            if (k instanceof ExceptionKey) {
                ret = (FinalVarContext<T>) ret.addKey(k, exceptional);
            }
            else {
                ret = (FinalVarContext<T>) ret.addKey(k, normal);
            }
        }
        return ret;
    }
}
