Merge pull request #347 from serpilliere/dg_has_loop

Dg has loop

4 files changed, 33 insertions, 5 deletions

diff --git a/miasm2/analysis/depgraph.py b/miasm2/analysis/depgraph.py
index aec159aa..b574e421 100644
--- a/miasm2/analysis/depgraph.py
+++ b/miasm2/analysis/depgraph.py
@@ -252,10 +252,10 @@ class DependencyResult(DependencyState):
 
     @property
     def has_loop(self):
-        """True if current dictionary has a loop"""
+        """True iff there is at least one data dependencies cycle (regarding
+        the associated depgraph)"""
         if self._has_loop is None:
-            self._has_loop = (len(self.relevant_labels) !=
-                              len(set(self.relevant_labels)))
+            self._has_loop = self.graph.has_loop()
         return self._has_loop
 
     def irblock_slice(self, irb):
diff --git a/miasm2/core/graph.py b/miasm2/core/graph.py
index c98bf8a9..d97ca8be 100644
--- a/miasm2/core/graph.py
+++ b/miasm2/core/graph.py
@@ -478,6 +478,34 @@ class DiGraph(object):
         """Performs a depth first search on the reversed graph from @head"""
         return self._walk_generic_first(head, -1, self.predecessors_iter)
 
+    def has_loop(self):
+        """Return True if the graph contains at least a cycle"""
+        todo = list(self.nodes())
+        # tested nodes
+        done = set()
+        # current DFS nodes
+        current = set()
+        while todo:
+            node = todo.pop()
+            if node in done:
+                continue
+
+            if node in current:
+                # DFS branch end
+                for succ in self.successors_iter(node):
+                    if succ in current:
+                        return True
+                # A node cannot be in current AND in done
+                current.remove(node)
+                done.add(node)
+            else:
+                # Launch DFS from node
+                todo.append(node)
+                current.add(node)
+                todo += self.successors(node)
+
+        return False
+
     def compute_natural_loops(self, head):
         """
         Computes all natural loops in the graph.
diff --git a/test/analysis/dg_test_06_expected.json b/test/analysis/dg_test_06_expected.json
index 7d823131..c181cd2d 100644
--- a/test/analysis/dg_test_06_expected.json
+++ b/test/analysis/dg_test_06_expected.json
@@ -1 +1 @@
-[{"EAX": "0x1", "has_loop": false}, {"EAX": "0x2", "has_loop": true}]
+[{"EAX": "0x1", "has_loop": false}, {"EAX": "0x2", "has_loop": false}]
diff --git a/test/analysis/dg_test_06_implicit_expected.json b/test/analysis/dg_test_06_implicit_expected.json
index 050915c1..bda75296 100644
--- a/test/analysis/dg_test_06_implicit_expected.json
+++ b/test/analysis/dg_test_06_implicit_expected.json
@@ -1 +1 @@
-[{"has_loop": false, "EAX": "0x1", "satisfiability": true, "constraints": {"EAX_init": "0xffffffff"}}, {"has_loop": true, "EAX": "0x2", "satisfiability": false, "constraints": {}}]
+[{"has_loop": false, "EAX": "0x1", "satisfiability": true, "constraints": {"EAX_init": "0xffffffff"}}, {"has_loop": false, "EAX": "0x2", "satisfiability": false, "constraints": {}}]