package accrue.analysis.defuse;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import polyglot.ast.Expr;
import polyglot.ast.ProcedureCall;
import polyglot.types.FieldInstance;
import polyglot.types.MethodInstance;
import polyglot.types.ProcedureInstance;
import accrue.analysis.defuse.DefUseAnalysisUtil.Mode;
import accrue.analysis.ext.AccrueExt;
import accrue.analysis.ext.AccrueExt_c;
import accrue.analysis.interprocanalysis.AbstractLocation;
import accrue.analysis.interprocanalysis.AnalysisContext;
import accrue.analysis.interprocanalysis.DataFlowNodeIdentifier;
import accrue.analysis.interprocanalysis.EdgeIdentifier;
import accrue.analysis.interprocanalysis.EdgeIdentifier.HeapUseKey;
import accrue.analysis.interprocanalysis.EdgeIdentifier_c;
import accrue.analysis.interprocanalysis.ExitMap;
import accrue.analysis.interprocanalysis.ExitMap.ExceptionKey;
import accrue.analysis.interprocanalysis.ExitMap.Key;
import accrue.analysis.interprocanalysis.NodeIdentifier;
import accrue.analysis.interprocvarcontext.AnalysisUtilVarContextDataFlow;
import accrue.analysis.interprocvarcontext.FinalVarContext;
import accrue.analysis.interprocvarcontext.LibrarySignature;
import accrue.analysis.interprocvarcontext.VarContext;
import accrue.analysis.pointer.HContext;

/**
 * Signature classes for Def/Use analysis.
 * 
 * @param object
 * @param name
 * @return
 */
// TODO: Use the expectedExits parameter.
public class DefUseLibrarySignature extends
        LibrarySignature<VarContext<DefUseAbsVal>, DefUseAbsVal> {

    public final static class Join extends DefUseLibrarySignature {
        public Join(DefUseLibrarySignature left, DefUseLibrarySignature right) {
            super(join(left.receiver_defs, right.receiver_defs), join(
                    left.receiver_uses, right.receiver_uses), join(
                    left.global_defs, right.global_defs), join(
                    left.global_uses, right.global_uses), join(left.arg_defs,
                    right.arg_defs), join(left.arg_uses, right.arg_uses),
                    left.uses_defs | right.uses_defs, left.returns_newalloc
                            & right.returns_newalloc);
        }
    }

    public final static AbstractLocation PSEUDOLOC(HContext object, String name) {
        return AbstractLocation.create(object, name);
    }

    public static <T> List<T> join(List<T> left, List<T> right) {
        List<T> join = new ArrayList<T>(left);
        join.addAll(right);
        return join;
    }

    protected final boolean returns_newalloc;
    protected final boolean uses_defs;

    protected final List<String> receiver_defs;
    protected final List<String> receiver_uses;
    protected final List<List<String>> arg_defs;
    protected final List<List<String>> arg_uses;
    protected final List<String> global_defs;
    protected final List<String> global_uses;
    /** Generic hidden state of a native object. */
    public static String HIDDEN = "$HIDDEN$";
    /** The state of the clock */
    public static String CLOCK = "$CLOCK$";

    /**
     * A signature that defines and uses locations on the receiver
     * 
     * @param receiver_defs
     * @param receiver_uses
     * @param uses_defs
     * @param returns_newalloc
     */
    public DefUseLibrarySignature(List<String> receiver_defs,
            List<String> receiver_uses, boolean uses_defs,
            boolean returns_newalloc) {
        this(receiver_defs, receiver_uses, Collections.<String> emptyList(),
                Collections.<String> emptyList(), uses_defs, returns_newalloc);
    }

    /**
     * A signature that defines and uses locations on the receiver and arguments
     * 
     * @param receiver_defs
     * @param receiver_uses
     * @param uses_defs
     * @param returns_newalloc
     */
    public DefUseLibrarySignature(List<String> receiver_defs,
            List<String> receiver_uses, List<String> global_defs,
            List<String> global_uses, boolean uses_defs,
            boolean returns_newalloc) {
        this(receiver_defs, receiver_uses, global_defs, global_uses,
                Collections.<List<String>> emptyList(), Collections
                        .<List<String>> emptyList(), uses_defs,
                returns_newalloc);
    }

    /**
     * A signature that defines and uses locations on the receiver and arguments
     * 
     * @param receiver_defs
     * @param receiver_uses
     * @param uses_defs
     * @param returns_newalloc
     */
    public DefUseLibrarySignature(List<String> receiver_defs,
            List<String> receiver_uses, List<String> global_defs,
            List<String> global_uses, List<List<String>> arg_defs,
            List<List<String>> arg_uses, boolean uses_defs,
            boolean returns_newalloc) {
        this.receiver_defs = receiver_defs;
        this.receiver_uses = receiver_uses;
        this.arg_defs = arg_defs;
        this.arg_uses = arg_uses;
        this.global_defs = global_defs;
        this.global_uses = global_uses;
        this.uses_defs = uses_defs;
        this.returns_newalloc = returns_newalloc;
    }

    @Override
    public FinalVarContext<DefUseAbsVal> process(ProcedureInstance pi,
            AnalysisContext calleeContext, HContext receiver,
            VarContext<DefUseAbsVal> input, DefUseAbsVal receiverAbsVal,
            List<DefUseAbsVal> argAbsVals,
            AnalysisUtilVarContextDataFlow<VarContext<DefUseAbsVal>, DefUseAbsVal> autil,
            Set<ExitMap.Key> expectedExits, DataFlowNodeIdentifier callSite) {

        if (uses_defs) {
            input = processDefs(pi, calleeContext, receiver, input,
                    receiverAbsVal, argAbsVals, autil, callSite);
            input = processUses(pi, calleeContext, receiver, input,
                    receiverAbsVal, argAbsVals, autil, callSite);
        } else {
            input = processUses(pi, calleeContext, receiver, input,
                    receiverAbsVal, argAbsVals, autil, callSite);
            input = processDefs(pi, calleeContext, receiver, input,
                    receiverAbsVal, argAbsVals, autil, callSite);
        }
        if (pi instanceof MethodInstance) {
            MethodInstance mi = (MethodInstance) pi;
            if (!mi.returnType().isVoid()) {
                if (returns_newalloc) {
                    Expr call = (Expr) callSite.getNode();
                    DefUseAbsVal ret = new NewAllocAbsVal(autil.pointsTo(call));
                    input = input.pushExprResult(ret, "defuse signature for "
                            + pi);
                } else {
                    DefUseAbsVal ret = autil.bottomAbstractValue();
                    input = input.pushExprResult(ret, "defuse signature for "
                            + pi);
                }
            }
        }
        return addExceptions(input, autil, expectedExits);
    }

    protected VarContext<DefUseAbsVal> processUses(ProcedureInstance pi,
            AnalysisContext calleeContext, HContext receiver,
            VarContext<DefUseAbsVal> input, DefUseAbsVal receiverAbsVal,
            List<DefUseAbsVal> argAbsVals,
            AnalysisUtilVarContextDataFlow<VarContext<DefUseAbsVal>, DefUseAbsVal> autil,
            DataFlowNodeIdentifier callSite) {
        String data_dep_results_key = (((DefUseAnalysisUtil) autil).mode() == Mode.INTER_EDGES) ? DefUseAnalysisFactory.DATA_DEPENDENCIES
                : DefUseAnalysisFactory.INTRA_DATA_DEPENDENCIES;

        AccrueExt ext = AccrueExt_c.ext(callSite.getNode());
        // USES
        Set<AbstractLocation> used_locs = new HashSet<AbstractLocation>();
        for (String name : receiver_uses) {
            used_locs.add(PSEUDOLOC(receiver, name));
        }

        for (String name : global_uses) {
            used_locs.add(PSEUDOLOC(null, name));
        }

        // by default, use all fields of the arguments
        DefUseAnalysisUtil duAutil = (DefUseAnalysisUtil) autil;
        ProcedureCall c = (ProcedureCall) callSite.getNode();
        List<Expr> args = c.arguments();

        for (int i = 0; i < argAbsVals.size(); i++) {
            if (args.get(i).type().isReference()) {
                if (args.get(i).type().equals(pi.typeSystem().String())) {
                    if (((DefUseAnalysisUtil) autil).trackStrings())
                        used_locs.addAll(duAutil.stringLocations(
                                argAbsVals.get(i), args.get(i)));
                    continue;
                }
                Set<HContext> hcs = duAutil.pointsTo(argAbsVals.get(i),
                        args.get(i));
                for (HContext hc : hcs) {
                    for (FieldInstance fi : hc.type().toReference().fields()) {
                        if (!fi.flags().isStatic())
                            used_locs.addAll(autil.abstractLocations(hc, fi));
                    }
                    if (!arg_uses.isEmpty()) {
                        for (String fname : arg_uses.get(i)) {
                            used_locs
                                    .addAll(autil.abstractLocations(hc, fname));
                        }
                    }
                }
            }
        }

        DefUseAbsVal used = autil.getLocationAbsVal(input, used_locs);
        if (used == null)
            used = autil.bottomAbstractValue();
        addResults(DefUseAnalysisFactory.OBSERVED_LOCATIONS, ext,
                calleeContext, used_locs);
        addResults(data_dep_results_key, ext, calleeContext,
                used.reachingDefinitions());
        return input;
    }

    protected VarContext<DefUseAbsVal> processDefs(ProcedureInstance pi,
            AnalysisContext calleeContext, HContext receiver,
            VarContext<DefUseAbsVal> input, DefUseAbsVal receiverAbsVal,
            List<DefUseAbsVal> argAbsVals,
            AnalysisUtilVarContextDataFlow<VarContext<DefUseAbsVal>, DefUseAbsVal> autil,
            DataFlowNodeIdentifier callSite) {
        AccrueExt ext = AccrueExt_c.ext(callSite.getNode());

        // DEFS
        Set<AbstractLocation> def_locs = new HashSet<AbstractLocation>();
        // NodeIdentifier ni = new NativeNodeIdentifier_c(calleeContext, pi);
        NodeIdentifier ni = callSite;
        input = addDefs(receiver, input, autil, receiver_defs, def_locs, ni);
        input = addDefs(null, input, autil, global_defs, def_locs, ni);
        addResults(DefUseAnalysisFactory.MODIFIED_LOCATIONS, ext,
                calleeContext, def_locs);
        // TODO support arg_defs
        return input;
    }

    protected VarContext<DefUseAbsVal> addDefs(HContext receiver,
            VarContext<DefUseAbsVal> input,
            AnalysisUtilVarContextDataFlow<VarContext<DefUseAbsVal>, DefUseAbsVal> autil,
            List<String> defs, Set<AbstractLocation> locs, NodeIdentifier ni) {
        DefUseAnalysisUtil duAutil = (DefUseAnalysisUtil) autil;
        for (String name : defs) {
            Set<AbstractLocation> loc = Collections.singleton(PSEUDOLOC(
                    receiver, name));
            // Generate a new update loc
            HeapUseKey key = new HeapUseKey(loc,
                    duAutil.mode() == Mode.INTRA_EDGES);
            EdgeIdentifier use = new EdgeIdentifier_c(key, ni);

            DefUseAbsVal defined = autil.getLocationAbsVal(input, loc);
            if (defined == null)
                defined = autil.bottomAbstractValue();
            // XXX: here we could strong update if receiver (and pseudoloc) is a
            // singleton
            input = autil.addLocations(input, loc, defined.addReachingDef(use));
            locs.addAll(loc);
        }
        return input;
    }

    protected FinalVarContext<DefUseAbsVal> addExceptions(
            VarContext<DefUseAbsVal> input,
            AnalysisUtilVarContextDataFlow<VarContext<DefUseAbsVal>, DefUseAbsVal> autil,
            Set<Key> expectedExits) {
        FinalVarContext<DefUseAbsVal> output = autil
                .createFinalVarContext(input);
        for (Key ex : expectedExits) {
            if (ex instanceof ExceptionKey) {
                ExceptionKey exKey = (ExceptionKey) ex;
                // XXX: exAlloc really could be a NewAllocAbsVal, but it's
                // unclear how to
                // get the correct HContext for the exception. Also, I don't
                // quite understand
                // how pointsto for catch formals really works.
                DefUseAbsVal exAlloc = autil.bottomAbstractValue();
                output = (FinalVarContext<DefUseAbsVal>) output.addKey(exKey,
                        input.clearExprResultStack().returnResult(exAlloc));
            }
        }
        return output;
    }

    /**
     * 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 <T> void addResults(String resultKey, AccrueExt rec,
            AnalysisContext ctx, Set<T> results) {
        // Get all the control dependencies of this dep
        Set<T> cur_results = rec.getAnalysisResult(resultKey, ctx);
        // If none exists, create a new one
        if (cur_results == null) {
            cur_results = new HashSet<T>();
            rec.recordAnalysisResult(resultKey, ctx, cur_results);
        }
        cur_results.addAll(results);
    }

    private static List<String> EMPTY = Collections.<String> emptyList();

    private static List<List<String>> ONEARG(int numargs, int arg,
            String fieldName) {
        List<String> names = new ArrayList<String>(numargs);
        for (int i = 0; i < numargs; i++) {
            if (i == arg)
                names.add(fieldName);
            else
                names.add("");
        }
        return ARGFIELDS(names);
    }

    private static List<List<String>> ARGS(int numargs, List<Integer> args,
            List<String> fieldName) {
        List<String> names = new ArrayList<String>(numargs);
        for (int i = 0; i < numargs; i++) {
            int idx = -1;
            if ((idx = args.indexOf(i)) >= 0)
                names.add(fieldName.get(idx));
            else
                names.add("");
        }
        return ARGFIELDS(names);
    }

    private static List<List<String>> ARGFIELDS(List<String> fieldNames) {
        List<List<String>> args = new ArrayList<List<String>>(fieldNames.size());
        for (String fname : fieldNames) {
            if (fname.isEmpty())
                args.add(Collections.<String> emptyList());
            else
                args.add(Collections.<String> singletonList(fname));
        }
        return args;
    }

    public static final DefUseLibrarySignature NOOP = new DefUseLibrarySignature(
            EMPTY, EMPTY, false, false);

    public static final DefUseLibrarySignature NEWALLOC = new DefUseLibrarySignature(
            EMPTY, EMPTY, false, false);

    public static final class USE_DEF_HIDDEN extends DefUseLibrarySignature {
        public USE_DEF_HIDDEN(String... hiddens) {
            super(Arrays.asList(hiddens), Arrays.asList(hiddens), false, false);
        }
    }

    public static final class USE_DEF_USEARG_HIDDEN extends
            DefUseLibrarySignature {
        public USE_DEF_USEARG_HIDDEN(String hiddens, int numargs, int arg,
                String argHidden) {
            super(Arrays.asList(hiddens), Arrays.asList(hiddens), EMPTY, EMPTY,
                    Collections.<List<String>> emptyList(), // defs
                    ONEARG(numargs, arg, argHidden), // uses
                    false, false);
        }

        public USE_DEF_USEARG_HIDDEN(List<String> hiddens, int numargs,
                List<Integer> args, List<String> argHiddens) {
            super(hiddens, hiddens, EMPTY, EMPTY, Collections
                    .<List<String>> emptyList(), // defs
                    ARGS(numargs, args, argHiddens), // uses
                    false, false);
        }

    }

    public static final class USE_HIDDEN extends DefUseLibrarySignature {
        public USE_HIDDEN(String... hiddens) {
            super(EMPTY, Arrays.asList(hiddens), false, false);
        }

    }

    public static final class DEF_HIDDEN extends DefUseLibrarySignature {
        public DEF_HIDDEN(String... hiddens) {
            super(Arrays.asList(hiddens), EMPTY, false, false);
        }

    }

    public static final class DEF_ARG extends DefUseLibrarySignature {
        public DEF_ARG(int numArgs, int argIndex, String hidden) {
            super(EMPTY, EMPTY, EMPTY, EMPTY,
                    ONEARG(numArgs, argIndex, hidden), // defs
                    Collections.<List<String>> emptyList(), // uses
                    false, false);
        }

    }

    public static final DefUseLibrarySignature USES_CLOCK = new DefUseLibrarySignature(
            EMPTY, EMPTY, List(DefUseLibrarySignature.CLOCK),
            List(DefUseLibrarySignature.CLOCK), false, false);

    protected static List<String> List(String s1) {
        return Collections.singletonList(s1);
    }

}
