1 files changed, 128 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;
+  }
+}