/*
 * Copyright 2009 Google Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
 * use this file except in compliance with the License. You may obtain a copy of
 * the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 */
package com.google.gwt.dev.jjs.impl.gflow;

import com.google.gwt.dev.jjs.impl.gflow.TransformationFunction.Transformation;
import com.google.gwt.thirdparty.guava.common.base.Preconditions;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;

/**
 * A solver to solve all kinds of analyses defined in the package.
 * Uses iterative worklist algorithm.
 *
 * Solver might be forward or backwards working. Both directions will always
 * produce a valid fixed point, which depends on direction. As a rule,
 * forward analysis benefits from forward direction, backwards - from the
 * opposite.
 *
 * @param <N> graph node type.
 * @param <E> graph edge type.
 * @param <T> graph transformer type.
 * @param <G> graph type.
 * @param <A> assumption type.
 */
public class AnalysisSolver<N, E, T, G extends Graph<N, E, T>,
                            A extends Assumption<A>> {
  /**
   * Adapter from IntegratedFlowFunction to FlowFunction. If integrated function
   * decides to perform transformation, replacement graph is recursively
   * analyzed and result return without actually performing transformation,
   */
  private final class IntegratedFlowFunctionAdapter
      implements FlowFunction<N, E, G, A> {
    private IntegratedFlowFunction<N, E, T, G, A> flowFunction;

    private IntegratedFlowFunctionAdapter(
        IntegratedAnalysis<N, E, T, G, A> analysis) {
      flowFunction = analysis.getIntegratedFlowFunction();
    }

    @Override
    public void interpret(final N node, G graph,
        final AssumptionMap<E, A> assumptionMap) {
      final boolean[] mapWasModified = new boolean[1];
      Transformation<T, G> transformation = flowFunction.interpretOrReplace(
          node, graph, new AssumptionMap<E, A>() {
            @Override
            public A getAssumption(E edge) {
              return assumptionMap.getAssumption(edge);
            }

            @Override
            public void setAssumption(E edge, A assumption) {
              mapWasModified[0] = true;
              assumptionMap.setAssumption(edge, assumption);
            }
          });

      if (transformation == null) {
        return;
      }

      Preconditions.checkArgument(!mapWasModified[0]);

      final G newSubgraph = transformation.getNewSubgraph();

      if (debug) {
        System.err.println("Applying transformation: " + transformation);
        System.err.println("Replacing");
        System.err.println(node);
        System.err.println("With graph:");
        System.err.println(newSubgraph);
      }

      final List<E> inEdges = graph.getInEdges(node);
      final List<E> outEdges = graph.getOutEdges(node);

      Preconditions.checkArgument(newSubgraph.getGraphInEdges().size() ==
        inEdges.size());

      Preconditions.checkArgument(newSubgraph.getGraphOutEdges().size() ==
        outEdges.size());

      iterate(newSubgraph,
          new IntegratedAnalysis<N, E, T, G, A>() {
            @Override
            public IntegratedFlowFunction<N, E, T, G, A>
            getIntegratedFlowFunction() {
              return flowFunction;
            }

            @Override
            public void setInitialGraphAssumptions(G graph,
                AssumptionMap<E, A> newAssumptionMap) {
              for (int i = 0; i < inEdges.size(); ++i) {
                newAssumptionMap.setAssumption(newSubgraph.getGraphInEdges().get(i),
                    assumptionMap.getAssumption(inEdges.get(i)));
              }

              for (int i = 0; i < outEdges.size(); ++i) {
                newAssumptionMap.setAssumption(newSubgraph.getGraphOutEdges().get(i),
                    assumptionMap.getAssumption(outEdges.get(i)));
              }
            }

          });

      for (int i = 0; i < inEdges.size(); ++i) {
        assumptionMap.setAssumption(inEdges.get(i),
            getEdgeAssumption(newSubgraph, newSubgraph.getGraphInEdges().get(i)));
      }

      for (int i = 0; i < outEdges.size(); ++i) {
        assumptionMap.setAssumption(outEdges.get(i),
            getEdgeAssumption(newSubgraph, newSubgraph.getGraphOutEdges().get(i)));
      }
    }
  }

  public static boolean debug = false;

  /**
   * Solve a non-integrated analysis.
   *
   * @param <N> graph node type.
   * @param <E> graph edge type.
   * @param <T> graph transformer type.
   * @param <G> graph type.
   * @param <A> assumption type.
   */
  public static <N, E, T, G extends Graph<N, E, T>, A extends Assumption<A>>
  Map<E, A> solve(G g, Analysis<N, E, G, A> analysis, boolean forward) {
    return new AnalysisSolver<N, E, T, G, A>(forward).solve(g, analysis);
  }

  /**
   * Solve a integrated analysis.
   *
   * @param <N> graph node type.
   * @param <E> graph edge type.
   * @param <T> graph transformer type.
   * @param <G> graph type.
   * @param <A> assumption type.
   */
  public static <N, E, T, G extends Graph<N, E, T>, A extends Assumption<A>>
  boolean solveIntegrated(G g, IntegratedAnalysis<N, E, T, G, A> analysis,
      boolean forward) {
    return new AnalysisSolver<N, E, T, G, A>(forward).solveIntegrated(g,
        analysis);
  }

  /**
   * If <code>true</code>, then we are moving forward. Moving backwards
   * otherwise.
   */
  private final boolean forward;

  /**
   * @param forward <code>true</code> if solvers moves forward.
   */
  private AnalysisSolver(boolean forward) {
    this.forward = forward;
  }

  /**
   * Apply all transformations based on a found fixed point.
   */
  private boolean actualize(G graph,
      final IntegratedAnalysis<N, E, T, G, A> analysis) {
    TransformationFunction<N, E, T, G, A> function =
      new TransformationFunction<N, E, T, G, A>() {
      @Override
      public Transformation<T, G> transform(final N node, final G graph,
          AssumptionMap<E, A> assumptionMap) {
        final boolean[] didAssumptionChange = new boolean[1];
        Transformation<T, G> transformation = analysis.getIntegratedFlowFunction().interpretOrReplace(
              node, graph, new AssumptionMap<E, A>() {
                @Override
                public A getAssumption(E edge) {
                  Preconditions.checkArgument(graph.getStart(edge) == node
                      || graph.getEnd(edge) == node);
                  return getEdgeAssumption(graph, edge);
                }

                @Override
                public void setAssumption(E edge, A assumption) {
                  Preconditions.checkArgument(graph.getStart(edge) == node
                      || graph.getEnd(edge) == node);
                 didAssumptionChange[0] = true;
                }
              });
        Preconditions.checkArgument(transformation == null ||
            !didAssumptionChange[0]);
        return transformation;
      }
    };
    return applyTransformation(graph, function);
  }

  private boolean applyTransformation(final G graph,
      TransformationFunction<N, E, T, G, A> transformationFunction) {
    boolean didChange = false;

    for (final N node : graph.getNodes()) {
      Transformation<T, G> transformation = transformationFunction.transform(
          node, graph, new AssumptionMap<E, A>() {
            @Override
            public A getAssumption(E edge) {
              Preconditions.checkArgument(graph.getStart(edge) == node
                  || graph.getEnd(edge) == node);
              return getEdgeAssumption(graph, edge);
            }

            @Override
            public void setAssumption(E edge, A assumption) {
              throw new IllegalStateException(
                  "Transformations should not change assumptions");
            }
          });
      if (transformation != null) {
        T actualizer = transformation.getGraphTransformer();
        Preconditions.checkNotNull(actualizer, "Null actualizer from: %s",
            transformationFunction);
        didChange = graph.transform(node, actualizer) || didChange;
      }
    }

    return didChange;
  }

  private LinkedHashSet<N> buildInitialWorklist(G g) {
    ArrayList<N> nodes = new ArrayList<N>(g.getNodes());
    LinkedHashSet<N> worklist = new LinkedHashSet<N>(nodes.size());
    if (!forward) {
      Collections.reverse(nodes);
    }
    worklist.addAll(nodes);
    return worklist;
  }

  @SuppressWarnings("unchecked")
  private A getEdgeAssumption(G graph, E edge) {
    return (A) graph.getEdgeData(edge);
  }

  private void initGraphAssumptions(Analysis<N, E, G, A> analysis, final G graph) {
    analysis.setInitialGraphAssumptions(graph, new AssumptionMap<E, A>() {
      @Override
      public A getAssumption(E edge) {
        return getEdgeAssumption(graph, edge);
      }

      @Override
      public void setAssumption(E edge, A assumption) {
        setEdgeAssumption(graph, edge, assumption);
      }
    });
  }

  /**
   * Find a fixed point of integrated analysis by wrapping it with
   * IntegratedFlowFunctionAdapter and calling
   * {@link #solveImpl(Graph, Analysis)}.
   */
  private void iterate(G graph,
      final IntegratedAnalysis<N, E, T, G, A> integratedAnalysis) {
    if (debug) {
      System.err.println("-----------------------------------------");
      System.err.println("Iterate started on:");
      System.err.println(graph);
      System.err.println("-----------------------------------------");
    }
    final IntegratedFlowFunctionAdapter adapter =
      new IntegratedFlowFunctionAdapter(integratedAnalysis);

    Analysis<N, E, G, A> analysis = new Analysis<N, E, G, A>() {
      @Override
      public FlowFunction<N, E, G, A> getFlowFunction() {
        return adapter;
      }

      @Override
      public void setInitialGraphAssumptions(G graph,
          AssumptionMap<E, A> assumptionMap) {
        integratedAnalysis.setInitialGraphAssumptions(graph, assumptionMap);
      }
    };

    solveImpl(graph, analysis);
  }

  private void resetEdgeData(G graph) {
    for (N node : graph.getNodes()) {
      for (E e : graph.getInEdges(node)) {
        graph.setEdgeData(e, null);
      }
      for (E e : graph.getOutEdges(node)) {
        graph.setEdgeData(e, null);
      }
    }
    for (E e : graph.getGraphOutEdges()) {
      graph.setEdgeData(e, null);
    }
    for (E e : graph.getGraphInEdges()) {
      graph.setEdgeData(e, null);
    }
  }

  private void setEdgeAssumption(G graph, E edge, A assumption) {
    graph.setEdgeData(edge, assumption);
  }

  /**
   * Solve a non-integrated analysis.
   */
  private Map<E, A> solve(G g, Analysis<N, E, G, A> analysis) {
    solveImpl(g, analysis);

    Map<E, A> result = new HashMap<E, A>();

    for (N n : g.getNodes()) {
      for (E e : g.getInEdges(n)) {
        result.put(e, getEdgeAssumption(g, e));
      }
      for (E e : g.getOutEdges(n)) {
        result.put(e, getEdgeAssumption(g, e));
      }
    }
    for (E e : g.getGraphInEdges()) {
      result.put(e, getEdgeAssumption(g, e));
    }
    for (E e : g.getGraphOutEdges()) {
      result.put(e, getEdgeAssumption(g, e));
    }

    return result;
  }

  /**
   * Solve a non-integrated analysis.
   */
  private void solveImpl(final G graph, Analysis<N, E, G, A> analysis) {
    FlowFunction<N, E, G, A> flowFunction = analysis.getFlowFunction();

    final LinkedHashSet<N> worklist = buildInitialWorklist(graph);
    resetEdgeData(graph);
    initGraphAssumptions(analysis, graph);

    while (!worklist.isEmpty()) {
      Iterator<N> iterator = worklist.iterator();
      final N node = iterator.next();
      iterator.remove();

      flowFunction.interpret(node, graph, new AssumptionMap<E, A>() {
        @Override
        public A getAssumption(E edge) {
          Preconditions.checkArgument(graph.getStart(edge) == node
              || graph.getEnd(edge) == node);
          return getEdgeAssumption(graph, edge);
        }

        @Override
        public void setAssumption(E edge, A assumption) {
          N start = graph.getStart(edge);
          N end = graph.getEnd(edge);
          Preconditions.checkArgument(start == node || end == node);

          if (!AssumptionUtil.equals(getEdgeAssumption(graph, edge), assumption)) {
            setEdgeAssumption(graph, edge, assumption);

            if (start == node) {
              if (end != null) {
                worklist.add(end);
              }
            } else if (end == node) {
              if (start != null) {
                worklist.add(start);
              }
            } else {
              throw new IllegalStateException();
            }
          }
        }
      });
    }
  }

  /**
   * Solve an integrated analysis.
   *
   * Finds a fixed point by using an IntegratedFlowFunctionAdapter and
   * recursing into {@link #solve(Graph, Analysis)}. Applies analysis
   * transformations based on the found fixed point.
   */
  private boolean solveIntegrated(G g, IntegratedAnalysis<N, E, T, G, A> analysis) {
    iterate(g, analysis);
    return actualize(g, analysis);
  }
}
