diff options
Diffstat (limited to 'plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose')
6 files changed, 868 insertions, 0 deletions
diff --git a/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/DominatorEngine.java b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/DominatorEngine.java new file mode 100644 index 000000000000..aeab0d2cf948 --- /dev/null +++ b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/DominatorEngine.java @@ -0,0 +1,128 @@ +/* + * 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.VBStyleCollection; + +import java.util.List; + +public class DominatorEngine { + + private Statement statement; + + private VBStyleCollection<Integer, Integer> colOrderedIDoms = new VBStyleCollection<Integer, Integer>(); + + + public DominatorEngine(Statement statement) { + this.statement = statement; + } + + public void initialize() { + calcIDoms(); + } + + private void orderStatements() { + + for (Statement stat : statement.getReversePostOrderList()) { + colOrderedIDoms.addWithKey(null, stat.id); + } + } + + private static Integer getCommonIDom(Integer key1, Integer key2, VBStyleCollection<Integer, Integer> orderedIDoms) { + + if (key1 == null) { + return key2; + } + else if (key2 == null) { + return key1; + } + + int index1 = orderedIDoms.getIndexByKey(key1); + int index2 = orderedIDoms.getIndexByKey(key2); + + while (index1 != index2) { + if (index1 > index2) { + key1 = orderedIDoms.getWithKey(key1); + index1 = orderedIDoms.getIndexByKey(key1); + } + else { + key2 = orderedIDoms.getWithKey(key2); + index2 = orderedIDoms.getIndexByKey(key2); + } + } + + return key1; + } + + private void calcIDoms() { + + orderStatements(); + + colOrderedIDoms.putWithKey(statement.getFirst().id, statement.getFirst().id); + + // exclude first statement + List<Integer> lstIds = colOrderedIDoms.getLstKeys().subList(1, colOrderedIDoms.getLstKeys().size()); + + while (true) { + + boolean changed = false; + + for (Integer id : lstIds) { + + Statement stat = statement.getStats().getWithKey(id); + Integer idom = null; + + for (StatEdge edge : stat.getAllPredecessorEdges()) { + if (colOrderedIDoms.getWithKey(edge.getSource().id) != null) { + idom = getCommonIDom(idom, edge.getSource().id, colOrderedIDoms); + } + } + + Integer oldidom = colOrderedIDoms.putWithKey(idom, id); + if (!idom.equals(oldidom)) { + changed = true; + } + } + + if (!changed) { + break; + } + } + } + + public VBStyleCollection<Integer, Integer> getOrderedIDoms() { + return colOrderedIDoms; + } + + public boolean isDominator(Integer node, Integer dom) { + + while (!node.equals(dom)) { + + Integer idom = colOrderedIDoms.getWithKey(node); + + if (idom.equals(node)) { + return false; // root node + } + else { + node = idom; + } + } + + return true; + } +} diff --git a/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/DominatorTreeExceptionFilter.java b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/DominatorTreeExceptionFilter.java new file mode 100644 index 000000000000..c11d5bf0c67e --- /dev/null +++ b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/DominatorTreeExceptionFilter.java @@ -0,0 +1,184 @@ +/* + * 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.VBStyleCollection; + +import java.util.*; +import java.util.Map.Entry; + +public class DominatorTreeExceptionFilter { + + private Statement statement; + + // idom, nodes + private Map<Integer, Set<Integer>> mapTreeBranches = new HashMap<Integer, Set<Integer>>(); + + // handler, range nodes + private Map<Integer, Set<Integer>> mapExceptionRanges = new HashMap<Integer, Set<Integer>>(); + + // handler, head dom + private Map<Integer, Integer> mapExceptionDoms = new HashMap<Integer, Integer>(); + + // statement, handler, exit nodes + private Map<Integer, Map<Integer, Integer>> mapExceptionRangeUniqueExit = new HashMap<Integer, Map<Integer, Integer>>(); + + private DominatorEngine domEngine; + + public DominatorTreeExceptionFilter(Statement statement) { + this.statement = statement; + } + + public void initialize() { + + domEngine = new DominatorEngine(statement); + domEngine.initialize(); + + buildDominatorTree(); + + buildExceptionRanges(); + + buildFilter(statement.getFirst().id); + + // free resources + mapTreeBranches.clear(); + mapExceptionRanges.clear(); + } + + public boolean acceptStatementPair(Integer head, Integer exit) { + + Map<Integer, Integer> filter = mapExceptionRangeUniqueExit.get(head); + for (Entry<Integer, Integer> entry : filter.entrySet()) { + if (!head.equals(mapExceptionDoms.get(entry.getKey()))) { + Integer filterExit = entry.getValue(); + if (filterExit.intValue() == -1 || !filterExit.equals(exit)) { + return false; + } + } + } + + return true; + } + + private void buildDominatorTree() { + + VBStyleCollection<Integer, Integer> orderedIDoms = domEngine.getOrderedIDoms(); + + List<Integer> lstKeys = orderedIDoms.getLstKeys(); + for (int index = lstKeys.size() - 1; index >= 0; index--) { + Integer key = lstKeys.get(index); + Integer idom = orderedIDoms.get(index); + + Set<Integer> set = mapTreeBranches.get(idom); + if (set == null) { + mapTreeBranches.put(idom, set = new HashSet<Integer>()); + } + set.add(key); + } + + Integer firstid = statement.getFirst().id; + mapTreeBranches.get(firstid).remove(firstid); + } + + private void buildExceptionRanges() { + + for (Statement stat : statement.getStats()) { + List<Statement> lstPreds = stat.getNeighbours(StatEdge.TYPE_EXCEPTION, Statement.DIRECTION_BACKWARD); + if (!lstPreds.isEmpty()) { + + Set<Integer> set = new HashSet<Integer>(); + + for (Statement st : lstPreds) { + set.add(st.id); + } + + mapExceptionRanges.put(stat.id, set); + } + } + + mapExceptionDoms = buildExceptionDoms(statement.getFirst().id); + } + + private Map<Integer, Integer> buildExceptionDoms(Integer id) { + + Map<Integer, Integer> map = new HashMap<Integer, Integer>(); + + Set<Integer> children = mapTreeBranches.get(id); + if (children != null) { + for (Integer childid : children) { + Map<Integer, Integer> mapChild = buildExceptionDoms(childid); + for (Integer handler : mapChild.keySet()) { + map.put(handler, map.containsKey(handler) ? id : mapChild.get(handler)); + } + } + } + + for (Entry<Integer, Set<Integer>> entry : mapExceptionRanges.entrySet()) { + if (entry.getValue().contains(id)) { + map.put(entry.getKey(), id); + } + } + + return map; + } + + + private void buildFilter(Integer id) { + + Map<Integer, Integer> map = new HashMap<Integer, Integer>(); + + Set<Integer> children = mapTreeBranches.get(id); + if (children != null) { + for (Integer childid : children) { + + buildFilter(childid); + + Map<Integer, Integer> mapChild = mapExceptionRangeUniqueExit.get(childid); + + for (Entry<Integer, Set<Integer>> entry : mapExceptionRanges.entrySet()) { + + Integer handler = entry.getKey(); + Set<Integer> range = entry.getValue(); + + if (range.contains(id)) { + + Integer exit = null; + + if (!range.contains(childid)) { + exit = childid; + } + else { + // exit = map.containsKey(handler)?-1:mapChild.get(handler); FIXME: Eclipse bug? + exit = map.containsKey(handler) ? new Integer(-1) : mapChild.get(handler); + } + + if (exit != null) { + map.put(handler, exit); + } + } + } + } + } + + mapExceptionRangeUniqueExit.put(id, map); + } + + public DominatorEngine getDomEngine() { + return domEngine; + } +} diff --git a/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/FastExtendedPostdominanceHelper.java b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/FastExtendedPostdominanceHelper.java new file mode 100644 index 000000000000..f029016e5efe --- /dev/null +++ b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/FastExtendedPostdominanceHelper.java @@ -0,0 +1,355 @@ +/* + * 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); + } +} diff --git a/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/GenericDominatorEngine.java b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/GenericDominatorEngine.java new file mode 100644 index 000000000000..c6eb35722eb6 --- /dev/null +++ b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/GenericDominatorEngine.java @@ -0,0 +1,152 @@ +/* + * 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.util.VBStyleCollection; + +import java.util.List; +import java.util.Set; + +public class GenericDominatorEngine { + + private IGraph graph; + + private VBStyleCollection<IGraphNode, IGraphNode> colOrderedIDoms = new VBStyleCollection<IGraphNode, IGraphNode>(); + + private Set<? extends IGraphNode> setRoots; + + public GenericDominatorEngine(IGraph graph) { + this.graph = graph; + } + + public void initialize() { + calcIDoms(); + } + + private void orderNodes() { + + setRoots = graph.getRoots(); + + for (IGraphNode node : graph.getReversePostOrderList()) { + colOrderedIDoms.addWithKey(null, node); + } + } + + private static IGraphNode getCommonIDom(IGraphNode node1, IGraphNode node2, VBStyleCollection<IGraphNode, IGraphNode> orderedIDoms) { + + IGraphNode nodeOld; + + if (node1 == null) { + return node2; + } + else if (node2 == null) { + return node1; + } + + int index1 = orderedIDoms.getIndexByKey(node1); + int index2 = orderedIDoms.getIndexByKey(node2); + + while (index1 != index2) { + if (index1 > index2) { + nodeOld = node1; + node1 = orderedIDoms.getWithKey(node1); + + if (nodeOld == node1) { // no idom - root or merging point + return null; + } + + index1 = orderedIDoms.getIndexByKey(node1); + } + else { + nodeOld = node2; + node2 = orderedIDoms.getWithKey(node2); + + if (nodeOld == node2) { // no idom - root or merging point + return null; + } + + index2 = orderedIDoms.getIndexByKey(node2); + } + } + + return node1; + } + + private void calcIDoms() { + + orderNodes(); + + List<IGraphNode> lstNodes = colOrderedIDoms.getLstKeys(); + + while (true) { + + boolean changed = false; + + for (IGraphNode node : lstNodes) { + + IGraphNode idom = null; + + if (!setRoots.contains(node)) { + for (IGraphNode pred : node.getPredecessors()) { + if (colOrderedIDoms.getWithKey(pred) != null) { + idom = getCommonIDom(idom, pred, colOrderedIDoms); + if (idom == null) { + break; // no idom found: merging point of two trees + } + } + } + } + + if (idom == null) { + idom = node; + } + + IGraphNode oldidom = colOrderedIDoms.putWithKey(idom, node); + if (!idom.equals(oldidom)) { // oldidom is null iff the node is touched for the first time + changed = true; + } + } + + if (!changed) { + break; + } + } + } + + public VBStyleCollection<IGraphNode, IGraphNode> getOrderedIDoms() { + return colOrderedIDoms; + } + + public boolean isDominator(IGraphNode node, IGraphNode dom) { + + while (!node.equals(dom)) { + + IGraphNode idom = colOrderedIDoms.getWithKey(node); + + if (idom == node) { + return false; // root node or merging point + } + else if (idom == null) { + throw new RuntimeException("Inconsistent idom sequence discovered!"); + } + else { + node = idom; + } + } + + return true; + } +} diff --git a/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/IGraph.java b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/IGraph.java new file mode 100644 index 000000000000..faaf4c6b66cf --- /dev/null +++ b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/IGraph.java @@ -0,0 +1,26 @@ +/* + * 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 java.util.List; +import java.util.Set; + +public interface IGraph { + + List<? extends IGraphNode> getReversePostOrderList(); + + Set<? extends IGraphNode> getRoots(); +} diff --git a/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/IGraphNode.java b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/IGraphNode.java new file mode 100644 index 000000000000..19d59b5acb32 --- /dev/null +++ b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/decompose/IGraphNode.java @@ -0,0 +1,23 @@ +/* + * 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 java.util.List; + +public interface IGraphNode { + + List<? extends IGraphNode> getPredecessors(); +} |