package accrue.analysis.pointer;

import java.io.PrintStream;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;

import polyglot.types.CodeInstance;
import polyglot.types.ProcedureInstance;
import polyglot.types.Type;
import polyglot.util.InternalCompilerError;
import polyglot.util.Position;
import accrue.analysis.pointer.PointsToEngine.StmtAndContext;
import accrue.analysis.pointer.analyses.HeapAbstractionFactory;

/**
 * A PointsToGraph is a data structure that describes what expressions/locations
 *  (i.e., PointsToGraphNodes) can point to what abstract objects
 * (i.e., HContexts)
 */
public abstract class PointsToGraph {
    protected final HeapAbstractionFactory af;
    protected PointsToEngine engine;
    /**
     * Has this graph been solved yet?
     * Various methods shoudl only be called once the points to graph
     * inference has finished.
     */
    protected boolean solved = false;

    public PointsToGraph(HeapAbstractionFactory af) {
        this.af = af;
    }

//    public final boolean addEdges(PointsToGraphNode src, Set<HContext> trgs,
//            Position origin);
//
//    public final boolean addEdge(PointsToGraphNode src, HContext trg,
//            Position origin);
//
//    public final boolean addCall(CodeDecl caller, CContext callerContext,
//            ProcedureInstance callee, CContext calleeContext, Position origin);

    public final Set<HContext> pointsTo(PointsToGraphNode r) {
        checkSolved();
        return pointsTo(null, r);
    }

    public final Set<HContext> pointsToFiltered(PointsToGraphNode r, Type t) {
        checkSolved();
        return pointsToFiltered(null, r, t);
    }

    public final Set<HContext> pointsToFiltered(PointsToGraphNode r, Type t,
            Set<Type> notT) {
        checkSolved();
        return pointsToFiltered(null, r, t, notT);
    }

    private void checkSolved() {
        if (!this.solved) {
            throw new InternalCompilerError("Don't use this method until the points to graph is solved.");
        }
    }

    /*
     * Methods for interaction with the PointsToEngine
     */
    void setSolved() {
        this.solved = true;
        // cut our ties to the engine, to allow garbage collection.
        this.engine = null;
    }

    public abstract boolean addEdges(StmtAndContext sac, PointsToGraphNode src,
            Set<HContext> trgs, Position origin);

    public abstract boolean addEdge(StmtAndContext sac, PointsToGraphNode src,
            HContext trg, Position origin);

    public abstract boolean addCall(StmtAndContext sac, CodeInstance caller,
            CContext callerContext, ProcedureInstance callee,
            CContext calleeContext, Position origin);

    public abstract Set<HContext> pointsTo(StmtAndContext sac,
            PointsToGraphNode r);

    final Set<HContext> pointsToFiltered(StmtAndContext sac,
            PointsToGraphNode r, Type t) {
        return pointsToFiltered(sac, r, t, null);
    }

    /**
     * Returns the set of ObjectNames that r may point to that are a subtype of t, and not a subtype of any type in
     * notT
     */
    Set<HContext> pointsToFiltered(StmtAndContext sac, PointsToGraphNode r,
            Type t, Set<Type> notT) {
        Set<HContext> s = this.pointsTo(sac, r);
        if (s.isEmpty()) {
            return Collections.emptySet();
        }

        // we're in the middle of solving the graph
        // We need to create a copy of set in case it changes concurrently, 
        // allowing objects in that should have been filtered out.
        Set<HContext> copy = new LinkedHashSet<HContext>(s);
        Iterator<HContext> iter = copy.iterator();
        while (iter.hasNext()) {
            HContext o = iter.next();
            Type ct = o.type();
            if (!o.hasPreciseType() || ct.isImplicitCastValid(t)) {
                if (notT != null && !notT.isEmpty()) {
                    for (Type nt : notT) {
                        if (ct.isImplicitCastValid(nt)) {
                            iter.remove();
                            break;
                        }
                    }
                    if (!o.hasPreciseType())
                        System.err.println("Warning: imprecise type for " + o
                                + ". Cannot guarantee it is not a subtype of "
                                + notT);
                }
                if (!o.hasPreciseType() && ct.isClass() && t.isClass()) {
                    // if o has no precise type, we can still rule out 
                    // this object if ct and t are class types and a subtype of
                    // ct cannot be assigned to a variable of type t.
                    boolean ctIsClass = !ct.toClass().flags().isInterface();
                    boolean tIsClass = !t.toClass().flags().isInterface();
                    if (ctIsClass && tIsClass && !ct.isSubtype(t)
                            && !t.isSubtype(ct)) {
                        iter.remove();
                    }
                }
            }
            else {
                iter.remove();
            }
        }

        return copy;
    }

    public abstract Set<CContext> getContexts(CodeInstance pi);

    abstract Set<PointsToGraphNode> getDomain();

    @Override
    public int hashCode() {
        return this.getDomain().hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof PointsToGraph) {
            PointsToGraph that = (PointsToGraph) obj;
            Set<PointsToGraphNode> domain =
                    new LinkedHashSet<PointsToGraphNode>(this.getDomain());
            domain.addAll(that.getDomain());
            for (PointsToGraphNode n : domain) {
                if (!this.pointsTo(n).equals(that.pointsTo(n))) {
                    return false;
//                    System.err.println("Disagree on node " + n);
//                    System.err.println("   this has " + this.pointsTo(n).size()
//                            + " nodes, that has " + that.pointsTo(n).size());
//                    for (HContext x : this.pointsTo(n)) {
//                        if (!that.pointsTo(n).contains(x)) {
//                            System.err.println("   this but not that contains "
//                                    + x);
//                        }
//                    }
//                    for (HContext x : that.pointsTo(n)) {
//                        if (!this.pointsTo(n).contains(x)) {
//                            System.err.println("   that but not this contains "
//                                    + x);
//                        }
//                    }

                }
            }
            return true;
        }
        return false;
    }

    /* Utility Methods */

    /**
     * Dump the graph in a human readable form.
     * @param out
     */
    public abstract void dump(PrintStream out);

    /**
     * Dump the graph in GraphViz dot format.
     * @param out
     */
    public abstract void dumpPointsToGraph(int level);

    public long nodeSize() {
        return this.getDomain().size();
    }

    public abstract long edgeSize();

    public abstract CallGraph callGraph();

}
