plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/FastExtendedPostdominanceHelper.java - platform/tools/idea - Git at Google

 /*
  * 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);
   }
 }
	/*
	* 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);
	}
	}