Move cycle detection into its own class.

It has the characteristics of a visitor, so let's make
it one.
Also introduce test case.

Change-Id: Ibfe14ca71268f73afe5e524fa1a15b3ab67058f1
Reviewed-by: Joerg Bornemann <joerg.bornemann@digia.com>

3 files changed, 180 insertions, 0 deletions

diff --git a/tests/auto/buildgraph/buildgraph.pro b/tests/auto/buildgraph/buildgraph.pro
new file mode 100644
index 000000000..173cbbae5
--- /dev/null
+++ b/tests/auto/buildgraph/buildgraph.pro
@@ -0,0 +1,17 @@
+TEMPLATE = app
+TARGET = tst_buildgraph
+DESTDIR = ./
+DEPENDPATH += .
+INCLUDEPATH += . ../../../src/lib/
+DEFINES += SRCDIR=\\\"$$PWD/\\\"
+
+QT = core testlib
+CONFIG += testcase
+
+include(../../../src/lib/use.pri)
+
+HEADERS += \
+    tst_buildgraph.h
+
+SOURCES += \
+    tst_buildgraph.cpp
diff --git a/tests/auto/buildgraph/tst_buildgraph.cpp b/tests/auto/buildgraph/tst_buildgraph.cpp
new file mode 100644
index 000000000..babeac25a
--- /dev/null
+++ b/tests/auto/buildgraph/tst_buildgraph.cpp
@@ -0,0 +1,105 @@
+/****************************************************************************
+**
+** Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/legal
+**
+** This file is part of the Qt Build Suite.
+**
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and Digia.  For licensing terms and
+** conditions see http://qt.digia.com/licensing.  For further information
+** use the contact form at http://qt.digia.com/contact-us.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Digia gives you certain additional
+** rights.  These rights are described in the Digia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+****************************************************************************/
+#include "tst_buildgraph.h"
+
+#include <buildgraph/artifact.h>
+#include <buildgraph/cycledetector.h>
+#include <tools/error.h>
+
+#include <QtTest>
+
+using namespace qbs;
+using namespace qbs::Internal;
+
+void TestBuildGraph::initTestCase()
+{
+}
+
+void TestBuildGraph::cleanupTestCase()
+{
+    qDeleteAll(m_artifacts);
+}
+
+
+static bool cycleDetected(const BuildProduct::ConstPtr &product)
+{
+    try {
+        CycleDetector().visitProduct(product);
+        return false;
+    } catch (const Error &error) {
+        return true;
+    }
+}
+
+BuildProduct::ConstPtr TestBuildGraph::productWithDirectCycle()
+{
+    Artifact * const root = new Artifact;
+    Artifact * const child = new Artifact;
+    m_artifacts << root << child;
+    root->children.insert(child);
+    child->children.insert(root);
+    const BuildProduct::Ptr product = BuildProduct::create();
+    product->targetArtifacts.insert(root);
+    return product;
+}
+
+BuildProduct::ConstPtr TestBuildGraph::productWithLessDirectCycle()
+{
+    Artifact * const root = new Artifact;
+    Artifact * const child = new Artifact;
+    Artifact * const grandchild = new Artifact;
+    m_artifacts << root << child << grandchild;
+    root->children.insert(child);
+    child->children.insert(grandchild);
+    grandchild->children.insert(root);
+    const BuildProduct::Ptr product = BuildProduct::create();
+    product->targetArtifacts << root;
+    return product;
+}
+
+// root appears as a child, but in a different tree
+BuildProduct::ConstPtr TestBuildGraph::productWithNoCycle()
+{
+    Artifact * const root = new Artifact;
+    Artifact * const root2 = new Artifact;
+    m_artifacts << root << root2;
+    root2->children.insert(root);
+    const BuildProduct::Ptr product = BuildProduct::create();
+    product->targetArtifacts << root << root2;
+    return product;
+}
+
+void TestBuildGraph::testCycle()
+{
+    QVERIFY(cycleDetected(productWithDirectCycle()));
+    QVERIFY(cycleDetected(productWithLessDirectCycle()));
+    QVERIFY(!cycleDetected(productWithNoCycle()));
+}
+
+QTEST_MAIN(TestBuildGraph)
diff --git a/tests/auto/buildgraph/tst_buildgraph.h b/tests/auto/buildgraph/tst_buildgraph.h
new file mode 100644
index 000000000..835764c8d
--- /dev/null
+++ b/tests/auto/buildgraph/tst_buildgraph.h
@@ -0,0 +1,58 @@
+/****************************************************************************
+**
+** Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/legal
+**
+** This file is part of the Qt Build Suite.
+**
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and Digia.  For licensing terms and
+** conditions see http://qt.digia.com/licensing.  For further information
+** use the contact form at http://qt.digia.com/contact-us.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Digia gives you certain additional
+** rights.  These rights are described in the Digia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+****************************************************************************/
+#ifndef TST_BUILDGRAPH_H
+#define TST_BUILDGRAPH_H
+
+#include <buildgraph/buildgraph.h>
+
+#include <QList>
+#include <QObject>
+
+namespace qbs { namespace Internal { class Artifact; } }
+
+class TestBuildGraph : public QObject
+{
+    Q_OBJECT
+public:
+
+private slots:
+    void initTestCase();
+    void cleanupTestCase();
+    void testCycle();
+
+private:
+    qbs::Internal::BuildProduct::ConstPtr productWithDirectCycle();
+    qbs::Internal::BuildProduct::ConstPtr productWithLessDirectCycle();
+    qbs::Internal::BuildProduct::ConstPtr productWithNoCycle();
+
+    QList<qbs::Internal::Artifact *> m_artifacts;
+};
+
+
+#endif // TST_BUILDGRAPH_H