detect cycles in rule dependencies

This fixes a stack overflow that occurred when having cycles in rule
dependencies.

Task-number: QBS-396

Change-Id: I1907ef66d74340c090b09be72d2352892baca986
Reviewed-by: Christian Kandeler <christian.kandeler@digia.com>

2 files changed, 23 insertions, 4 deletions

diff --git a/src/lib/buildgraph/rulegraph.cpp b/src/lib/buildgraph/rulegraph.cpp
index c2653ad7e..b33c8891d 100644
--- a/src/lib/buildgraph/rulegraph.cpp
+++ b/src/lib/buildgraph/rulegraph.cpp
@@ -29,6 +29,7 @@
 
 #include "rulegraph.h"
 #include <language/language.h>
+#include <logging/translator.h>
 #include <tools/error.h>
 
 namespace qbs {
@@ -79,7 +80,9 @@ QList<RuleConstPtr> RuleGraph::topSorted()
     QList<RuleConstPtr> result;
     foreach (int rootIndex, rootRules) {
         RuleConstPtr rule = m_artifacts.at(rootIndex);
-        result.append(topSort(rule));
+        QSet<const Rule *> seenRules;
+        QList<const Rule *> rulePath;
+        result.append(topSort(rule, &seenRules, &rulePath));
     }
 
     // remove duplicates from the result of our post-order traversal
@@ -182,13 +185,28 @@ void RuleGraph::removeSiblings(const Rule *rule)
     }
 }
 
-QList<RuleConstPtr> RuleGraph::topSort(const RuleConstPtr &rule)
+QList<RuleConstPtr> RuleGraph::topSort(const RuleConstPtr &rule, QSet<const Rule *> *seenRules,
+        QList<const Rule *> *rulePath)
 {
+    if (seenRules->contains(rule.data())) {
+        QString pathstr;
+        foreach (const Rule *r, *rulePath) {
+            pathstr += QLatin1Char('\n') + r->toString() + QLatin1Char('\t')
+                    + r->script->location.toString();
+        }
+        throw ErrorInfo(Tr::tr("Cycle detected in rule dependencies: %1").arg(pathstr));
+    }
+
+    seenRules->insert(rule.data());
+    rulePath->prepend(rule.data());
+
     QList<RuleConstPtr> result;
     foreach (int childIndex, m_children.at(rule->ruleGraphId))
-        result.append(topSort(m_artifacts.at(childIndex)));
+        result.append(topSort(m_artifacts.at(childIndex), seenRules, rulePath));
 
     result.append(rule);
+    seenRules->remove(rule.data());
+    rulePath->removeFirst();
     return result;
 }
 
diff --git a/src/lib/buildgraph/rulegraph.h b/src/lib/buildgraph/rulegraph.h
index e1a511751..510a4789c 100644
--- a/src/lib/buildgraph/rulegraph.h
+++ b/src/lib/buildgraph/rulegraph.h
@@ -59,7 +59,8 @@ private:
     void remove(Rule *rule);
     void removeParents(const Rule *rule);
     void removeSiblings(const Rule *rule);
-    QList<RuleConstPtr> topSort(const RuleConstPtr &rule);
+    QList<RuleConstPtr> topSort(const RuleConstPtr &rule, QSet<const Rule *> *seenRules,
+            QList<const Rule *> *rulePath);
 
 private:
     QMap<FileTag, QList<const Rule*> > m_outputFileTagToRule;