package accrue.analysis.interprocvarcontext;

import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;

import polyglot.visit.FlowGraph.EdgeKey;
import accrue.analysis.interprocanalysis.Ordered;

/**
 * Stack of maps from CFG edge key to abstract dataflow value. This is used to 
 * pass values for exceptions and a return value leaving a try block through the 
 * associated finally block.
 * <p>
 * See Java Language Specification 5.0 section 14.20.2 for more detail.
 * <p>
 * @param <T> Type of the abstract dataflow value
 */
public class SuspendedExecutionStack<T extends AbstractValue<T>> implements
        Ordered<SuspendedExecutionStack<T>> {

    @SuppressWarnings("rawtypes")
    private static final SuspendedExecutionStack EMPTY =
            new SuspendedExecutionStack(Stack.EMPTY);
    /**
     * Internal stack that is delegated to. This class does not just extend 
     * {@link Stack} so client code does not have to deal with {@link KeyMap} objects.
     */
    private final Stack<KeyMap<T>> stack;

    /**
     * This is the only way to create a {@link SuspendedExecutionStack}
     */
    @SuppressWarnings("unchecked")
    public static final <T extends AbstractValue<T>> SuspendedExecutionStack<T> emptyStack() {
        return EMPTY;
    }

    /**
     * Create a {@link SuspendedExecutionStack} from the internal representation
     */
    private SuspendedExecutionStack(Stack<KeyMap<T>> s) {
        this.stack = s;
    }

    /**
     * Get the number of elements on the stack
     * 
     * @return the number of elements on the stack
     */
    public int size() {
        return stack.size();
    }

    /**
     * Get the element on top of the stack 
     * @return element on top of the stack 
     */
    public Map<EdgeKey, T> peek() {
        return stack.peek().getMap();
    }

    /**
     * Get the finally block the element on top of the stack was pushed on for
     * @return finally block the element on top of the stack was pushed on for
     */
    public Object peekSource() {
        return stack.peekSource();
    }

    /**
     * Get a new stack with the top element popped off
     * @return new stack with the top element popped off
     */
    public SuspendedExecutionStack<T> pop() {
        return new SuspendedExecutionStack<T>(stack.pop());
    }

    /**
     * Get a new stack by pushing the specified map onto this stack
     * 
     * @param v new map
     * @param source finally block the map is for (or node we are merging for if we are merging)
     * @return new stack with the new map on top
     */
    public SuspendedExecutionStack<T> push(Map<EdgeKey, T> v, Object source) {
        return new SuspendedExecutionStack<T>(stack.push(new KeyMap<T>(v),
                                                         source));
    }

    @Override
    public boolean leq(SuspendedExecutionStack<T> o) {
        return this.stack.leq(o.stack);
    }

    @Override
    public SuspendedExecutionStack<T> upperBound(SuspendedExecutionStack<T> o) {
        if (o == null) {
            return this;
        }
        return new SuspendedExecutionStack<T>(this.stack.upperBound(o.stack));
    }

    @Override
    public SuspendedExecutionStack<T> widen(SuspendedExecutionStack<T> o) {
        if (o == null) {
            return this;
        }
        return new SuspendedExecutionStack<T>(this.stack.widen(o.stack));
    }

    /**
     * True if there are no elements on the stack
     * 
     * @return true if there are no elements on the stack
     */
    public boolean isEmpty() {
        return stack.isEmpty();
    }

    @Override
    public String toString() {
        return stack.toString();
    }

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

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        SuspendedExecutionStack other = (SuspendedExecutionStack) obj;
        if (stack == null) {
            if (other.stack != null) return false;
        }
        else if (!stack.equals(other.stack)) return false;
        return true;
    }

    /**
     * Wrapper around a map from edge key to abstract value providing the 
     * {@link AbstractValue} interface for the map.
     * 
     * @param <T> type of the abstract value in the map
     */
    private static class KeyMap<T extends AbstractValue<T>> implements
            AbstractValue<KeyMap<T>> {

        /**
         * Internal map
         */
        private Map<EdgeKey, T> v;

        /**
         * Create a new map from the internal representation
         * 
         * @param v map from edge keys to abstract values to wrap around.
         */
        private KeyMap(Map<EdgeKey, T> v) {
            this.v = v;
        }

        /**
         * Get the actual map from edge key to abstract value
         * 
         * @return map from edge key to abstract value
         */
        public Map<EdgeKey, T> getMap() {
            return v;
        }

        @Override
        public boolean leq(KeyMap<T> o) {
            if (this == o) return true;
            Map<EdgeKey, T> other = o.getMap();

            if (!other.keySet().contains(v.keySet())) {
                return false;
            }

            for (EdgeKey ek : v.keySet()) {
                T val = v.get(ek);
                T otherVal = other.get(ek);
                if (!val.leq(otherVal)) {
                    return false;
                }
            }

            return true;
        }

        @Override
        public KeyMap<T> upperBound(KeyMap<T> o) {
            if (this == o) return this;
            Map<EdgeKey, T> other = o.getMap();
            Set<EdgeKey> dup = new LinkedHashSet<EdgeKey>(v.keySet());
            dup.retainAll(other.keySet());

            Map<EdgeKey, T> ret = new LinkedHashMap<EdgeKey, T>(v);
            ret.putAll(other);
            ret.keySet().removeAll(dup);

            for (EdgeKey ek : dup) {

                T value =
                        (v.get(ek) == null) ? other.get(ek)
                                : v.get(ek).upperBound(other.get(ek));
                ret.put(ek, value);
            }
            return new KeyMap<T>(ret);
        }

        @Override
        public KeyMap<T> widen(KeyMap<T> o) {
            if (this == o) return this;
            Map<EdgeKey, T> other = o.getMap();
            Set<EdgeKey> dup = new LinkedHashSet<EdgeKey>(v.keySet());
            dup.retainAll(other.keySet());

            Map<EdgeKey, T> ret = new LinkedHashMap<EdgeKey, T>(v);
            ret.putAll(other);
            ret.keySet().removeAll(dup);

            for (EdgeKey ek : dup) {
                T value = v.get(ek).widen(other.get(ek));
                ret.put(ek, value);
            }
            return new KeyMap<T>(ret);
        }

        @Override
        public boolean isBottom() {
            return v.isEmpty();
        }

        @Override
        public String toString() {
            return v.toString();
        }

        @Override
        public int hashCode() {
            return v.hashCode() ^ 40078478;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null) return false;
            if (getClass() != obj.getClass()) return false;
            KeyMap other = (KeyMap) obj;
            if (v == null) {
                if (other.v != null) return false;
            }
            else if (!v.equals(other.v)) return false;
            return true;
        }

    }
}
