path: root/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/FastExtendedPostdominanceHelper.java

/*
 * Copyright 2000-2014 JetBrains s.r.o.
 *
 * 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 org.jetbrains.java.decompiler.modules.decompiler.decompose;

import org.jetbrains.java.decompiler.modules.decompiler.StatEdge;
import org.jetbrains.java.decompiler.modules.decompiler.stats.Statement;
import org.jetbrains.java.decompiler.util.FastFixedSetFactory;
import org.jetbrains.java.decompiler.util.FastFixedSetFactory.FastFixedSet;
import org.jetbrains.java.decompiler.util.InterpreterUtil;

import java.util.*;
import java.util.Map.Entry;

public class FastExtendedPostdominanceHelper {

  private List<Statement> lstReversePostOrderList;

  private HashMap<Integer, FastFixedSet<Integer>> mapSupportPoints = new HashMap<Integer, FastFixedSet<Integer>>();

  private HashMap<Integer, FastFixedSet<Integer>> mapExtPostdominators = new HashMap<Integer, FastFixedSet<Integer>>();

  private Statement statement;

  private FastFixedSetFactory<Integer> factory;

  public HashMap<Integer, Set<Integer>> getExtendedPostdominators(Statement statement) {

    this.statement = statement;

    HashSet<Integer> set = new HashSet<Integer>();
    for (Statement st : statement.getStats()) {
      set.add(st.id);
    }
    this.factory = new FastFixedSetFactory<Integer>(set);

    lstReversePostOrderList = statement.getReversePostOrderList();

    //		try {
    //			DotExporter.toDotFile(statement, new File("c:\\Temp\\stat1.dot"));
    //		} catch (Exception ex) {
    //			ex.printStackTrace();
    //		}

    calcDefaultReachableSets();

    removeErroneousNodes();

    DominatorTreeExceptionFilter filter = new DominatorTreeExceptionFilter(statement);
    filter.initialize();

    filterOnExceptionRanges(filter);

    filterOnDominance(filter);

    HashMap<Integer, Set<Integer>> res = new HashMap<Integer, Set<Integer>>();
    for (Entry<Integer, FastFixedSet<Integer>> entry : mapExtPostdominators.entrySet()) {
      res.put(entry.getKey(), entry.getValue().toPlainSet());
    }

    return res;
  }


  private void filterOnDominance(DominatorTreeExceptionFilter filter) {

    DominatorEngine engine = filter.getDomEngine();

    for (Integer head : new HashSet<Integer>(mapExtPostdominators.keySet())) {

      FastFixedSet<Integer> setPostdoms = mapExtPostdominators.get(head);

      LinkedList<Statement> stack = new LinkedList<Statement>();
      LinkedList<FastFixedSet<Integer>> stackPath = new LinkedList<FastFixedSet<Integer>>();

      stack.add(statement.getStats().getWithKey(head));
      stackPath.add(factory.spawnEmptySet());

      Set<Statement> setVisited = new HashSet<Statement>();

      while (!stack.isEmpty()) {

        Statement stat = stack.removeFirst();
        FastFixedSet<Integer> path = stackPath.removeFirst();

        if (setPostdoms.contains(stat.id)) {
          path.add(stat.id);
        }

        if (path.contains(setPostdoms)) {
          continue;
        }

        setVisited.add(stat);

        int domflag = 0;

        for (Iterator<Integer> it = setPostdoms.iterator(); it.hasNext(); ) {
          Integer post = it.next();

          if (!path.contains(post)) {
            if (domflag == 0) {
              domflag = engine.isDominator(stat.id, head) ? 2 : 1;
            }

            if (domflag == 1) { // not a dominator
              it.remove();
            }
          }
        }

        for (StatEdge edge : stat.getSuccessorEdges(StatEdge.TYPE_REGULAR)) {
          if (!setVisited.contains(edge.getDestination())) {
            stack.add(edge.getDestination());
            stackPath.add(path.getCopy());
          }
        }
      }

      if (setPostdoms.isEmpty()) {
        mapExtPostdominators.remove(head);
      }
    }
  }


  private void filterOnExceptionRanges(DominatorTreeExceptionFilter filter) {


    for (Integer head : new HashSet<Integer>(mapExtPostdominators.keySet())) {

      FastFixedSet<Integer> set = mapExtPostdominators.get(head);
      for (Iterator<Integer> it = set.iterator(); it.hasNext(); ) {
        if (!filter.acceptStatementPair(head, it.next())) {
          it.remove();
        }
      }
      if (set.isEmpty()) {
        mapExtPostdominators.remove(head);
      }
    }
  }


  private void removeErroneousNodes() {

    mapSupportPoints = new HashMap<Integer, FastFixedSet<Integer>>();

    calcReachabilitySuppPoints(StatEdge.TYPE_REGULAR);

    iterateReachability(new IReachabilityAction() {
      public boolean action(Statement node, HashMap<Integer, FastFixedSet<Integer>> mapSets) {

        Integer nodeid = node.id;

        FastFixedSet<Integer> setReachability = mapSets.get(nodeid);
        List<FastFixedSet<Integer>> lstPredSets = new ArrayList<FastFixedSet<Integer>>();

        for (StatEdge prededge : node.getPredecessorEdges(StatEdge.TYPE_REGULAR)) {
          FastFixedSet<Integer> setPred = mapSets.get(prededge.getSource().id);
          if (setPred == null) {
            setPred = mapSupportPoints.get(prededge.getSource().id);
          }

          // setPred cannot be empty as it is a reachability set
          lstPredSets.add(setPred);
        }

        for (Integer id : setReachability.toPlainSet()) {

          FastFixedSet<Integer> setReachabilityCopy = setReachability.getCopy();

          FastFixedSet<Integer> setIntersection = factory.spawnEmptySet();
          boolean isIntersectionInitialized = false;

          for (FastFixedSet<Integer> predset : lstPredSets) {
            if (predset.contains(id)) {
              if (!isIntersectionInitialized) {
                setIntersection.union(predset);
                isIntersectionInitialized = true;
              }
              else {
                setIntersection.intersection(predset);
              }
            }
          }

          if (nodeid != id.intValue()) {
            setIntersection.add(nodeid);
          }
          else {
            setIntersection.remove(nodeid);
          }

          setReachabilityCopy.complement(setIntersection);

          mapExtPostdominators.get(id).complement(setReachabilityCopy);
        }

        return false;
      }
    }, StatEdge.TYPE_REGULAR);

    // exception handlers cannot be postdominator nodes
    // TODO: replace with a standard set?
    FastFixedSet<Integer> setHandlers = factory.spawnEmptySet();
    boolean handlerfound = false;

    for (Statement stat : statement.getStats()) {
      if (stat.getPredecessorEdges(Statement.STATEDGE_DIRECT_ALL).isEmpty() &&
          !stat.getPredecessorEdges(StatEdge.TYPE_EXCEPTION).isEmpty()) { // exception handler
        setHandlers.add(stat.id);
        handlerfound = true;
      }
    }

    if (handlerfound) {
      for (FastFixedSet<Integer> set : mapExtPostdominators.values()) {
        set.complement(setHandlers);
      }
    }
  }


  private void calcDefaultReachableSets() {

    int edgetype = StatEdge.TYPE_REGULAR | StatEdge.TYPE_EXCEPTION;

    calcReachabilitySuppPoints(edgetype);

    for (Statement stat : statement.getStats()) {
      mapExtPostdominators.put(stat.id, factory.spawnEmptySet());
    }

    iterateReachability(new IReachabilityAction() {
      public boolean action(Statement node, HashMap<Integer, FastFixedSet<Integer>> mapSets) {

        Integer nodeid = node.id;
        FastFixedSet<Integer> setReachability = mapSets.get(nodeid);

        for (Integer id : setReachability.toPlainSet()) {
          mapExtPostdominators.get(id).add(nodeid);
        }

        return false;
      }
    }, edgetype);
  }


  private void calcReachabilitySuppPoints(final int edgetype) {

    iterateReachability(new IReachabilityAction() {
      public boolean action(Statement node, HashMap<Integer, FastFixedSet<Integer>> mapSets) {

        // consider to be a support point
        for (StatEdge sucedge : node.getAllSuccessorEdges()) {
          if ((sucedge.getType() & edgetype) != 0) {
            if (mapSets.containsKey(sucedge.getDestination().id)) {
              FastFixedSet<Integer> setReachability = mapSets.get(node.id);

              if (!InterpreterUtil.equalObjects(setReachability, mapSupportPoints.get(node.id))) {
                mapSupportPoints.put(node.id, setReachability);
                return true;
              }
            }
          }
        }

        return false;
      }
    }, edgetype);
  }

  private void iterateReachability(IReachabilityAction action, int edgetype) {

    while (true) {

      boolean iterate = false;

      HashMap<Integer, FastFixedSet<Integer>> mapSets = new HashMap<Integer, FastFixedSet<Integer>>();

      for (Statement stat : lstReversePostOrderList) {

        FastFixedSet<Integer> set = factory.spawnEmptySet();
        set.add(stat.id);

        for (StatEdge prededge : stat.getAllPredecessorEdges()) {
          if ((prededge.getType() & edgetype) != 0) {
            Statement pred = prededge.getSource();

            FastFixedSet<Integer> setPred = mapSets.get(pred.id);
            if (setPred == null) {
              setPred = mapSupportPoints.get(pred.id);
            }

            if (setPred != null) {
              set.union(setPred);
            }
          }
        }

        mapSets.put(stat.id, set);

        if (action != null) {
          iterate |= action.action(stat, mapSets);
        }

        // remove reachability information of fully processed nodes (saves memory)
        for (StatEdge prededge : stat.getAllPredecessorEdges()) {
          if ((prededge.getType() & edgetype) != 0) {
            Statement pred = prededge.getSource();

            if (mapSets.containsKey(pred.id)) {
              boolean remstat = true;
              for (StatEdge sucedge : pred.getAllSuccessorEdges()) {
                if ((sucedge.getType() & edgetype) != 0) {
                  if (!mapSets.containsKey(sucedge.getDestination().id)) {
                    remstat = false;
                    break;
                  }
                }
              }

              if (remstat) {
                mapSets.put(pred.id, null);
              }
            }
          }
        }
      }

      if (!iterate) {
        break;
      }
    }
  }


  private interface IReachabilityAction {
    boolean action(Statement node, HashMap<Integer, FastFixedSet<Integer>> mapSets);
  }
}