aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/lib/buildgraph/buildgraph.cpp57
-rw-r--r--src/lib/buildgraph/buildgraph.h5
-rw-r--r--src/lib/buildgraph/buildgraph.pri6
-rw-r--r--src/lib/buildgraph/cycledetector.cpp82
-rw-r--r--src/lib/buildgraph/cycledetector.h60
-rw-r--r--src/lib/buildgraph/executor.cpp3
-rw-r--r--tests/auto/auto.pro1
-rw-r--r--tests/auto/buildgraph/buildgraph.pro17
-rw-r--r--tests/auto/buildgraph/tst_buildgraph.cpp105
-rw-r--r--tests/auto/buildgraph/tst_buildgraph.h58
10 files changed, 335 insertions, 59 deletions
diff --git a/src/lib/buildgraph/buildgraph.cpp b/src/lib/buildgraph/buildgraph.cpp
index 09f33946b..02d8561fe 100644
--- a/src/lib/buildgraph/buildgraph.cpp
+++ b/src/lib/buildgraph/buildgraph.cpp
@@ -28,7 +28,9 @@
****************************************************************************/
#include "buildgraph.h"
+
#include "artifact.h"
+#include "cycledetector.h"
#include "command.h"
#include "rulegraph.h"
#include "transformer.h"
@@ -230,38 +232,13 @@ void BuildGraph::applyRules(BuildProduct *product, ArtifactsPerFileTagMap &artif
rulesApplier.applyAllRules();
}
-/*!
- * Runs a cycle detection on the BG and throws an exception if there is one.
- */
-void BuildGraph::detectCycle(BuildProject *project)
-{
- const QString description = QString::fromLocal8Bit("Cycle detection for project '%1'")
- .arg(project->resolvedProject()->id());
- TimedActivityLogger timeLogger(description, QLatin1String("[BG] "), LoggerTrace);
-
- foreach (const BuildProduct::ConstPtr &product, project->buildProducts())
- detectCycle(product);
-}
-
-void BuildGraph::detectCycle(const BuildProduct::ConstPtr &product)
-{
- foreach (Artifact *artifact, product->targetArtifacts)
- detectCycle(artifact);
-}
-
-void BuildGraph::detectCycle(Artifact *a)
-{
- QSet<Artifact *> done, currentBranch;
- detectCycle(a, done, currentBranch);
-}
-
void BuildGraph::setProgressObserver(ProgressObserver *observer)
{
m_progressObserver = observer;
}
-static bool findPath(Artifact *u, Artifact *v, QList<Artifact*> &path)
+bool BuildGraph::findPath(Artifact *u, Artifact *v, QList<Artifact*> &path)
{
if (u == v) {
path.append(v);
@@ -278,30 +255,6 @@ static bool findPath(Artifact *u, Artifact *v, QList<Artifact*> &path)
return false;
}
-void BuildGraph::detectCycle(Artifact *v, QSet<Artifact *> &done, QSet<Artifact *> &currentBranch)
-{
- currentBranch += v;
- for (ArtifactList::const_iterator it = v->children.begin(); it != v->children.end(); ++it) {
- Artifact *u = *it;
- if (currentBranch.contains(u)) {
- Error error(Tr::tr("Cycle in build graph detected."));
- QList<Artifact *> path;
- findPath(u, v, path);
- foreach (Artifact *a, path)
- error.append(Tr::tr("path1: ") + a->filePath());
- path.clear();
- findPath(v, u, path);
- foreach (Artifact *a, path)
- error.append(Tr::tr("path2: ") + a->filePath());
- throw error;
- }
- if (!done.contains(u))
- detectCycle(u, done, currentBranch);
- }
- currentBranch -= v;
- done += v;
-}
-
static AbstractCommand *createCommandFromScriptValue(const QScriptValue &scriptValue, const CodeLocation &codeLocation)
{
if (scriptValue.isUndefined() || !scriptValue.isValid())
@@ -537,7 +490,7 @@ BuildProject::Ptr BuildGraph::resolveProject(ResolvedProject::Ptr rProject)
foreach (ResolvedProduct::Ptr rProduct, rProject->products) {
resolveProduct(project.data(), rProduct);
}
- detectCycle(project.data());
+ CycleDetector().visitProject(project);
return project;
}
@@ -1033,7 +986,7 @@ void BuildProject::restoreBuildGraph(const QString &projectFilePath, BuildGraph
project->onProductRemoved(product);
}
- BuildGraph::detectCycle(project.data());
+ CycleDetector().visitProject(project);
}
}
diff --git a/src/lib/buildgraph/buildgraph.h b/src/lib/buildgraph/buildgraph.h
index d82900af0..104e48c11 100644
--- a/src/lib/buildgraph/buildgraph.h
+++ b/src/lib/buildgraph/buildgraph.h
@@ -166,9 +166,6 @@ public:
BuildProject::Ptr resolveProject(ResolvedProject::Ptr);
void applyRules(BuildProduct *product, ArtifactsPerFileTagMap &artifactsPerFileTag);
- static void detectCycle(BuildProject *project);
- static void detectCycle(const BuildProduct::ConstPtr &product);
- static void detectCycle(Artifact *a);
void setProgressObserver(ProgressObserver *observer);
void setOutputDirectoryRoot(const QString &buildDirectoryRoot) { m_outputDirectoryRoot = buildDirectoryRoot; }
@@ -176,6 +173,7 @@ public:
QString buildDirectory(const QString &projectId) const;
QString buildGraphFilePath(const QString &projectId) const;
+ static bool findPath(Artifact *u, Artifact *v, QList<Artifact*> &path);
static void connect(Artifact *p, Artifact *c);
static void loggedConnect(Artifact *u, Artifact *v);
static bool safeConnect(Artifact *u, Artifact *v);
@@ -206,7 +204,6 @@ private:
BuildProduct::Ptr resolveProduct(BuildProject *, ResolvedProduct::Ptr);
Artifact *createArtifact(BuildProduct::Ptr product, SourceArtifact::ConstPtr sourceArtifact);
void updateNodeThatMustGetNewTransformer(Artifact *artifact);
- static void detectCycle(Artifact *v, QSet<Artifact *> &done, QSet<Artifact *> &currentBranch);
class EngineInitializer
{
diff --git a/src/lib/buildgraph/buildgraph.pri b/src/lib/buildgraph/buildgraph.pri
index ba0bb3805..7ced8195f 100644
--- a/src/lib/buildgraph/buildgraph.pri
+++ b/src/lib/buildgraph/buildgraph.pri
@@ -15,7 +15,8 @@ SOURCES += \
$$PWD/artifact.cpp \
$$PWD/inputartifactscanner.cpp \
$$PWD/artifactvisitor.cpp \
- $$PWD/artifactcleaner.cpp
+ $$PWD/artifactcleaner.cpp \
+ $$PWD/cycledetector.cpp
HEADERS += \
$$PWD/automoc.h\
@@ -33,4 +34,5 @@ HEADERS += \
$$PWD/artifact.h \
$$PWD/inputartifactscanner.h \
$$PWD/artifactvisitor.h \
- $$PWD/artifactcleaner.h
+ $$PWD/artifactcleaner.h \
+ $$PWD/cycledetector.h
diff --git a/src/lib/buildgraph/cycledetector.cpp b/src/lib/buildgraph/cycledetector.cpp
new file mode 100644
index 000000000..da3b99242
--- /dev/null
+++ b/src/lib/buildgraph/cycledetector.cpp
@@ -0,0 +1,82 @@
+/****************************************************************************
+**
+** 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 "cycledetector.h"
+
+#include "artifact.h"
+#include "buildgraph.h"
+
+#include <logging/logger.h>
+#include <logging/translator.h>
+
+namespace qbs {
+namespace Internal {
+
+CycleDetector::CycleDetector() : ArtifactVisitor(0), m_parent(0)
+{
+}
+
+void CycleDetector::visitProject(const BuildProject::ConstPtr &project)
+{
+ const QString description = QString::fromLocal8Bit("Cycle detection for project '%1'")
+ .arg(project->resolvedProject()->id());
+ TimedActivityLogger timeLogger(description, QLatin1String("[BG] "), LoggerTrace);
+ ArtifactVisitor::visitProject(project);
+}
+
+void CycleDetector::visitArtifact(Artifact *artifact)
+{
+ if (m_artifactsInCurrentPath.contains(artifact)) {
+ Error error(Tr::tr("Cycle in build graph detected."));
+ foreach (const Artifact * const a, cycle(artifact))
+ error.append(a->filePath());
+ throw error;
+ }
+
+ if (m_allArtifacts.contains(artifact))
+ return;
+
+ m_artifactsInCurrentPath += artifact;
+ m_parent = artifact;
+ foreach (Artifact * const child, artifact->children)
+ visitArtifact(child);
+ m_artifactsInCurrentPath -= artifact;
+ m_allArtifacts += artifact;
+}
+
+void CycleDetector::doVisit(Artifact *) { }
+
+QList<Artifact *> CycleDetector::cycle(Artifact *doubleEntry)
+{
+ QList<Artifact *> path;
+ BuildGraph::findPath(doubleEntry, m_parent, path);
+ return path << doubleEntry;
+}
+
+} // namespace Internal
+} // namespace qbs
diff --git a/src/lib/buildgraph/cycledetector.h b/src/lib/buildgraph/cycledetector.h
new file mode 100644
index 000000000..ff5023fb8
--- /dev/null
+++ b/src/lib/buildgraph/cycledetector.h
@@ -0,0 +1,60 @@
+/****************************************************************************
+**
+** 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 CYCLEDETECTOR_H
+#define CYCLEDETECTOR_H
+
+#include "artifactvisitor.h"
+
+#include <QSet>
+
+namespace qbs {
+namespace Internal {
+
+class CycleDetector : public ArtifactVisitor
+{
+public:
+ CycleDetector();
+
+ void visitProject(const BuildProject::ConstPtr &project);
+ void visitArtifact(Artifact *artifact);
+
+private:
+ void doVisit(Artifact *artifact);
+
+ QList<Artifact *> cycle(Artifact *doubleEntry);
+
+ QSet<Artifact *> m_allArtifacts;
+ QSet<Artifact *> m_artifactsInCurrentPath;
+ Artifact *m_parent;
+};
+
+} // namespace Internal
+} // namespace qbs
+
+#endif // CYCLEDETECTOR_H
diff --git a/src/lib/buildgraph/executor.cpp b/src/lib/buildgraph/executor.cpp
index 901c36596..c5251cfaf 100644
--- a/src/lib/buildgraph/executor.cpp
+++ b/src/lib/buildgraph/executor.cpp
@@ -29,6 +29,7 @@
#include "artifactvisitor.h"
#include "automoc.h"
+#include "cycledetector.h"
#include "executor.h"
#include "executorjob.h"
#include "inputartifactscanner.h"
@@ -603,7 +604,7 @@ bool Executor::runAutoMoc()
}
if (autoMocApplied)
foreach (const BuildProduct::ConstPtr &product, m_productsToBuild)
- BuildGraph::detectCycle(product);
+ CycleDetector().visitProduct(product);
return true;
}
diff --git a/tests/auto/auto.pro b/tests/auto/auto.pro
index d893cec39..f1a902aba 100644
--- a/tests/auto/auto.pro
+++ b/tests/auto/auto.pro
@@ -2,4 +2,5 @@ TEMPLATE=subdirs
SUBDIRS= \
blackbox \
language \
+ buildgraph \
tools
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
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-14 16:54:05 +0000