From 2677cffbb49008488ac37684a3657aa4c3298afa Mon Sep 17 00:00:00 2001
From: Tim Blazytko <tim.blazytko@rub.de>
Date: Tue, 12 May 2015 19:40:19 +0200
Subject: Tests/graph: extended regression tests

---
 test/core/graph.py | 42 +++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 41 insertions(+), 1 deletion(-)

(limited to 'test')

diff --git a/test/core/graph.py b/test/core/graph.py
index eb320542..4ef37040 100644
--- a/test/core/graph.py
+++ b/test/core/graph.py
@@ -54,12 +54,19 @@ g2.add_edge(2, 3)
 g2.add_edge(3, 4)
 g2.add_edge(5, 6)
 g2.add_edge(6, 3)
+g2.add_edge(4, 7)
+g2.add_edge(4, 8)
+g2.add_edge(7, 9)
+g2.add_edge(8, 9)
 
 dominators = g2.compute_dominators(5)
 assert(dominators == {3: set([3, 5, 6]),
                       4: set([3, 4, 5, 6]),
                       5: set([5]),
-                      6: set([5, 6])})
+                      6: set([5, 6]),
+                      7: set([3, 4, 5, 6, 7]),
+                      8: set([3, 4, 5, 6, 8]),
+                      9: set([3, 4, 5, 6, 9])})
 
 
 assert(list(g2.walk_dominators(1, dominators)) == [])
@@ -113,3 +120,36 @@ assert(list(g2.walk_postdominators(3, postdominators)) == [4])
 assert(list(g2.walk_postdominators(4, postdominators)) == [])
 assert(list(g2.walk_postdominators(5, postdominators)) == [6, 3, 4])
 assert(list(g2.walk_postdominators(6, postdominators)) == [3, 4])
+
+idoms = g1.compute_immediate_dominators(1)
+assert(idoms == {2: 1,
+                 3: 2,
+                 4: 2,
+                 5: 2,
+                 6: 2})
+
+idoms = g2.compute_immediate_dominators(1)
+assert(idoms == {2: 1,
+                 3: 2,
+                 4: 3,
+                 7: 4,
+                 8: 4,
+                 9: 4})
+
+idoms = g2.compute_immediate_dominators(5)
+assert(idoms == {3: 6,
+                 4: 3,
+                 6: 5,
+                 7: 4,
+                 8: 4,
+                 9: 4})
+
+frontier = g1.compute_dominance_frontier(1)
+assert(frontier == {2: set([2, 5]),
+                    5: set([3, 4])})
+
+frontier = g2.compute_dominance_frontier(1)
+assert(frontier == {9: set([7, 8])})
+
+frontier = g2.compute_dominance_frontier(5)
+assert(frontier == {9: set([7, 8])})
\ No newline at end of file
-- 
cgit 1.4.1


From 5fc740de493c80731de0d0767c54fb6c9516b617 Mon Sep 17 00:00:00 2001
From: Tim Blazytko <tim.blazytko@rub.de>
Date: Sat, 16 May 2015 03:45:50 +0200
Subject: DiGraph: fixed order in dominance_frontier

---
 miasm2/core/graph.py |  6 +++---
 test/core/graph.py   | 12 ++++++++----
 2 files changed, 11 insertions(+), 7 deletions(-)

(limited to 'test')

diff --git a/miasm2/core/graph.py b/miasm2/core/graph.py
index b0dc70d6..00c30d62 100644
--- a/miasm2/core/graph.py
+++ b/miasm2/core/graph.py
@@ -338,9 +338,9 @@ shape = "box"
                     if runner not in idoms:
                         continue
                     while runner != idoms[node]:
-                        if node not in frontier:
-                            frontier[node] = set()
+                        if runner not in frontier:
+                            frontier[runner] = set()
 
-                        frontier[node].add(runner)
+                        frontier[runner].add(node)
                         runner = idoms[runner]
         return frontier
diff --git a/test/core/graph.py b/test/core/graph.py
index 4ef37040..85218a1c 100644
--- a/test/core/graph.py
+++ b/test/core/graph.py
@@ -145,11 +145,15 @@ assert(idoms == {3: 6,
                  9: 4})
 
 frontier = g1.compute_dominance_frontier(1)
-assert(frontier == {2: set([2, 5]),
-                    5: set([3, 4])})
+assert(frontier == {2: set([2]),
+                    3: set([5]),
+                    4: set([5]),
+                    5: set([2])})
 
 frontier = g2.compute_dominance_frontier(1)
-assert(frontier == {9: set([7, 8])})
+assert(frontier == {7: set([9]),
+                    8: set([9])})
 
 frontier = g2.compute_dominance_frontier(5)
-assert(frontier == {9: set([7, 8])})
\ No newline at end of file
+assert(frontier == {7: set([9]),
+                    8: set([9])})
\ No newline at end of file
-- 
cgit 1.4.1


From f6e00985a3e59f1f4813751572b5981d4dd1e6f4 Mon Sep 17 00:00:00 2001
From: Tim Blazytko <tim.blazytko@rub.de>
Date: Tue, 2 Jun 2015 15:39:19 +0200
Subject: Test/Graph: extended regression tests for g2

---
 test/core/graph.py | 7 +++++++
 1 file changed, 7 insertions(+)

(limited to 'test')

diff --git a/test/core/graph.py b/test/core/graph.py
index 85218a1c..5100cf8d 100644
--- a/test/core/graph.py
+++ b/test/core/graph.py
@@ -75,6 +75,9 @@ assert(list(g2.walk_dominators(3, dominators)) == [6, 5])
 assert(list(g2.walk_dominators(4, dominators)) == [3, 6, 5])
 assert(list(g2.walk_dominators(5, dominators)) == [])
 assert(list(g2.walk_dominators(6, dominators)) == [5])
+assert(list(g2.walk_dominators(7, dominators)) == [4, 3, 6, 5])
+assert(list(g2.walk_dominators(8, dominators)) == [4, 3, 6, 5])
+assert(list(g2.walk_dominators(9, dominators)) == [4, 3, 6, 5])
 
 postdominators = g1.compute_postdominators(6)
 assert(postdominators == {1: set([1, 2, 6]),
@@ -120,6 +123,10 @@ assert(list(g2.walk_postdominators(3, postdominators)) == [4])
 assert(list(g2.walk_postdominators(4, postdominators)) == [])
 assert(list(g2.walk_postdominators(5, postdominators)) == [6, 3, 4])
 assert(list(g2.walk_postdominators(6, postdominators)) == [3, 4])
+assert(list(g2.walk_postdominators(7, postdominators)) == [])
+assert(list(g2.walk_postdominators(8, postdominators)) == [])
+assert(list(g2.walk_postdominators(9, postdominators)) == [])
+
 
 idoms = g1.compute_immediate_dominators(1)
 assert(idoms == {2: 1,
-- 
cgit 1.4.1