Speed up cycle checking

When run on a codebase with a large dependency tree
the cycle checking can take an enormous amount of time.

In my tests, attempting to make JOM work with ghostscript's
makefiles, it can basically take forever (I gave up after
10 minutes).

There is a simple fix for this, implemented here. Once we have
cycle checked downwards from a given node, we know that whenever
we reach that node again, we need not bother to recheck it as
the results will be no different.

Hence whenever we successfully return from the recursive call,
set a flag meaning "NoCyclesRootedAtThisNode". Whenever we
step into a node, if that flag is set, there is no need to
recurse at all.

This is sufficient to make the cycle checking instant for the
Ghostscript makefiles.

This does mean that we are left with a 'dirty' tree, in that
the NoCyclesRootedAtThisNode flags are left set. I don't think
this is an issue, (does Parser:apply ever get called more than
once? And if it does, might the tree have changed between calls?)
but just in case, I have introduced another pass where we run
through the tree clearing the nodes.

Task-number: QTCREATORBUG-29412
Change-Id: I957cfb15df04b62e1a01476e3fd76b1e5b544a26
Reviewed-by: Joerg Bornemann <joerg.bornemann@qt.io>
Reviewed-by: Oliver Wolff <oliver.wolff@qt.io>

4 files changed, 45 insertions, 0 deletions

diff --git a/src/jomlib/makefile.cpp b/src/jomlib/makefile.cpp
index 720be01..94ef2d4 100644
--- a/src/jomlib/makefile.cpp
+++ b/src/jomlib/makefile.cpp
@@ -114,6 +114,7 @@ void Command::evaluateModifiers()
 DescriptionBlock::DescriptionBlock(Makefile* mkfile)
 :   m_bFileExists(false),
     m_bVisitedByCycleCheck(false),
+    m_bNoCyclesRootedHere(false),
     m_canAddCommands(ACSUnknown),
     m_pMakefile(mkfile)
 {
diff --git a/src/jomlib/makefile.h b/src/jomlib/makefile.h
index 4199b8a..84ae63d 100644
--- a/src/jomlib/makefile.h
+++ b/src/jomlib/makefile.h
@@ -103,6 +103,7 @@ public:
     FileTime m_timeStamp;
     bool m_bFileExists;
     bool m_bVisitedByCycleCheck;
+    bool m_bNoCyclesRootedHere;
     QVector<InferenceRule*> m_inferenceRules;
 
     enum AddCommandsState { ACSUnknown, ACSEnabled, ACSDisabled };
diff --git a/src/jomlib/parser.cpp b/src/jomlib/parser.cpp
index 260db5a..ec21a35 100644
--- a/src/jomlib/parser.cpp
+++ b/src/jomlib/parser.cpp
@@ -149,6 +149,11 @@ void Parser::apply(Preprocessor* pp,
         checkForCycles(target);
         preselectInferenceRules(target);
     }
+    // reset the droppings left by the cycle checker
+    foreach (const QString& targetName, m_activeTargets) {
+        DescriptionBlock *target = m_makefile->target(targetName);
+        resetCycleChecker(target);
+    }
 }
 
 MacroTable* Parser::macroTable()
@@ -637,20 +642,57 @@ void Parser::parseDotDirective()
 
 void Parser::checkForCycles(DescriptionBlock* target)
 {
+#ifdef DEBUG_CYCLE_CHECKER
+    static int depth = 0;
+#endif
+
     if (!target)
         return;
 
+#ifdef DEBUG_CYCLE_CHECKER
+    {
+        int i = depth;
+        while (i--)
+            putc(' ', stdout);
+    }
+    printf("%s\n", qPrintable(target->targetName()));
+#endif
+
+    if (target->m_bNoCyclesRootedHere)
+        return;
+
     if (target->m_bVisitedByCycleCheck) {
         QString msg = QLatin1String("cycle in targets detected: %1");
         throw Exception(msg.arg(target->targetName()));
     }
 
+#ifdef DEBUG_CYCLE_CHECKER
+    depth++;
+#endif
     target->m_bVisitedByCycleCheck = true;
     for (int i = target->m_dependents.count(); --i >= 0;) {
         DescriptionBlock *const dep = m_makefile->target(target->m_dependents.at(i));
         checkForCycles(dep);
     }
     target->m_bVisitedByCycleCheck = false;
+#ifdef DEBUG_CYCLE_CHECKER
+    depth--;
+#endif
+
+    target->m_bNoCyclesRootedHere = true;
+}
+
+void Parser::resetCycleChecker(DescriptionBlock* target)
+{
+    if (!target || !target->m_bNoCyclesRootedHere)
+        return;
+
+    for (int i = target->m_dependents.count(); --i >= 0;) {
+        DescriptionBlock *const dep = m_makefile->target(target->m_dependents.at(i));
+        resetCycleChecker(dep);
+    }
+
+    target->m_bNoCyclesRootedHere = false;
 }
 
 QVector<InferenceRule*> Parser::findRulesByTargetName(const QString& targetFilePath)
diff --git a/src/jomlib/parser.h b/src/jomlib/parser.h
index 60c3dcd..f746ba1 100644
--- a/src/jomlib/parser.h
+++ b/src/jomlib/parser.h
@@ -64,6 +64,7 @@ private:
     void parseCommandLine(const QString& cmdLine, QList<Command>& commands, bool inferenceRule);
     void parseInlineFiles(Command& cmd, bool inferenceRule);
     void checkForCycles(DescriptionBlock* target);
+    void resetCycleChecker(DescriptionBlock* target);
     QVector<InferenceRule*> findRulesByTargetName(const QString& targetFilePath);
     void preselectInferenceRules(DescriptionBlock *target);
     void error(const QString& msg);