diff options
author | Tor Norbye <tnorbye@google.com> | 2014-09-18 13:38:58 -0700 |
---|---|---|
committer | Tor Norbye <tnorbye@google.com> | 2014-09-18 13:38:58 -0700 |
commit | b5fb31ef6a38f19404859755dbd2e345215b97bf (patch) | |
tree | e8787c45e494dfcc558faf0f75956f8785c39b94 /plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/vars/VarVersionsGraph.java | |
parent | e222a9e1e66670a56e926a6b0f3e10231eeeb1fb (diff) | |
parent | e782c57d74000722f9db4c9426317410520670c6 (diff) | |
download | idea-b5fb31ef6a38f19404859755dbd2e345215b97bf.tar.gz |
Merge remote-tracking branch 'aosp/upstream-master' into merge
Conflicts:
.idea/libraries/asm_tools.xml
.idea/libraries/bouncy_castle.xml
.idea/libraries/builder_model.xml
.idea/libraries/commons_compress.xml
.idea/libraries/easymock_tools.xml
.idea/libraries/freemarker_2_3_20.xml
.idea/libraries/guava_tools.xml
.idea/libraries/kxml2.xml
.idea/libraries/lombok_ast.xml
.idea/libraries/mockito.xml
.idea/modules.xml
.idea/vcs.xml
build/scripts/layouts.gant
updater/src/com/intellij/updater/Runner.java
Change-Id: I8e1c173e00cd76c855b8a98543b0a0edfdd99d12
Diffstat (limited to 'plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/vars/VarVersionsGraph.java')
-rw-r--r-- | plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/vars/VarVersionsGraph.java | 167 |
1 files changed, 167 insertions, 0 deletions
diff --git a/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/vars/VarVersionsGraph.java b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/vars/VarVersionsGraph.java new file mode 100644 index 000000000000..f839a05819df --- /dev/null +++ b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/vars/VarVersionsGraph.java @@ -0,0 +1,167 @@ +/* + * 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.vars; + +import org.jetbrains.java.decompiler.modules.decompiler.decompose.GenericDominatorEngine; +import org.jetbrains.java.decompiler.modules.decompiler.decompose.IGraph; +import org.jetbrains.java.decompiler.modules.decompiler.decompose.IGraphNode; +import org.jetbrains.java.decompiler.util.VBStyleCollection; + +import java.util.*; + + +public class VarVersionsGraph { + + public int counter = 0; + + public VBStyleCollection<VarVersionNode, VarVersionPaar> nodes = new VBStyleCollection<VarVersionNode, VarVersionPaar>(); + + private GenericDominatorEngine engine; + + public VarVersionNode createNode(VarVersionPaar ver) { + VarVersionNode node; + nodes.addWithKey(node = new VarVersionNode(ver.var, ver.version), ver); + return node; + } + + public void addNodes(Collection<VarVersionNode> colnodes, Collection<VarVersionPaar> colpaars) { + nodes.addAllWithKey(colnodes, colpaars); + } + + public boolean isDominatorSet(VarVersionNode node, HashSet<VarVersionNode> domnodes) { + + if (domnodes.size() == 1) { + return engine.isDominator(node, domnodes.iterator().next()); + } + else { + + HashSet<VarVersionNode> marked = new HashSet<VarVersionNode>(); + + if (domnodes.contains(node)) { + return true; + } + + LinkedList<VarVersionNode> lstNodes = new LinkedList<VarVersionNode>(); + lstNodes.add(node); + + while (!lstNodes.isEmpty()) { + + VarVersionNode nd = lstNodes.remove(0); + if (marked.contains(nd)) { + continue; + } + else { + marked.add(nd); + } + + if (nd.preds.isEmpty()) { + return false; + } + + for (VarVersionEdge edge : nd.preds) { + VarVersionNode pred = edge.source; + if (!marked.contains(pred) && !domnodes.contains(pred)) { + lstNodes.add(pred); + } + } + } + } + + return true; + } + + public void initDominators() { + + final HashSet<VarVersionNode> roots = new HashSet<VarVersionNode>(); + + for (VarVersionNode node : nodes) { + if (node.preds.isEmpty()) { + roots.add(node); + } + } + + engine = new GenericDominatorEngine(new IGraph() { + public List<? extends IGraphNode> getReversePostOrderList() { + return getReversedPostOrder(roots); + } + + public Set<? extends IGraphNode> getRoots() { + return new HashSet<IGraphNode>(roots); + } + }); + + engine.initialize(); + } + + private static LinkedList<VarVersionNode> getReversedPostOrder(Collection<VarVersionNode> roots) { + + LinkedList<VarVersionNode> lst = new LinkedList<VarVersionNode>(); + HashSet<VarVersionNode> setVisited = new HashSet<VarVersionNode>(); + + for (VarVersionNode root : roots) { + + LinkedList<VarVersionNode> lstTemp = new LinkedList<VarVersionNode>(); + addToReversePostOrderListIterative(root, lstTemp, setVisited); + + lst.addAll(lstTemp); + } + + return lst; + } + + private static void addToReversePostOrderListIterative(VarVersionNode root, List<VarVersionNode> lst, HashSet<VarVersionNode> setVisited) { + + HashMap<VarVersionNode, List<VarVersionEdge>> mapNodeSuccs = new HashMap<VarVersionNode, List<VarVersionEdge>>(); + + LinkedList<VarVersionNode> stackNode = new LinkedList<VarVersionNode>(); + LinkedList<Integer> stackIndex = new LinkedList<Integer>(); + + stackNode.add(root); + stackIndex.add(0); + + while (!stackNode.isEmpty()) { + + VarVersionNode node = stackNode.getLast(); + int index = stackIndex.removeLast(); + + setVisited.add(node); + + List<VarVersionEdge> lstSuccs = mapNodeSuccs.get(node); + if (lstSuccs == null) { + mapNodeSuccs.put(node, lstSuccs = new ArrayList<VarVersionEdge>(node.succs)); + } + + for (; index < lstSuccs.size(); index++) { + VarVersionNode succ = lstSuccs.get(index).dest; + + if (!setVisited.contains(succ)) { + stackIndex.add(index + 1); + + stackNode.add(succ); + stackIndex.add(0); + + break; + } + } + + if (index == lstSuccs.size()) { + lst.add(0, node); + + stackNode.removeLast(); + } + } + } +} |