diff options
-rw-r--r-- | src/libs/installer/graph.h | 158 | ||||
-rw-r--r-- | src/libs/installer/installer.pro | 3 | ||||
-rw-r--r-- | src/libs/installer/packagemanagercore_p.cpp | 47 | ||||
-rw-r--r-- | src/libs/installer/packagemanagercore_p.h | 1 | ||||
-rw-r--r-- | tests/auto/installer/installer.pro | 4 | ||||
-rw-r--r-- | tests/auto/installer/solver/solver.pro | 5 | ||||
-rw-r--r-- | tests/auto/installer/solver/tst_solver.cpp | 134 |
7 files changed, 349 insertions, 3 deletions
diff --git a/src/libs/installer/graph.h b/src/libs/installer/graph.h new file mode 100644 index 000000000..59778a440 --- /dev/null +++ b/src/libs/installer/graph.h @@ -0,0 +1,158 @@ +/************************************************************************** +** +** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the Qt Installer Framework. +** +** $QT_BEGIN_LICENSE:LGPL$ +** 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. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** +** $QT_END_LICENSE$ +** +**************************************************************************/ + +#ifndef GRAPH_H +#define GRAPH_H + +#include <QHash> +#include <QList> +#include <QPair> +#include <QSet> + +namespace QInstaller { + +template <class T> class Graph +{ +public: + inline Graph() {} + explicit Graph(const QList<T> &nodes) + { + addNodes(nodes); + } + + const QList<T> nodes() const + { + return m_graph.keys(); + } + + void addNode(const T &node) + { + m_graph.insert(node, QSet<T>()); + } + + void addNodes(const QList<T> &nodes) + { + foreach (const T &node, nodes) + addNode(node); + } + + QList<T> edges(const T &node) const + { + return m_graph.value(node).toList(); + } + + void addEdge(const T &node, const T &edge) + { + m_graph[node].insert(edge); + } + + void addEdges(const T &node, const QList<T> &edges) + { + foreach (const T &edge, edges) + addEdge(node, edge); + } + + bool hasCycle() const + { + return m_hasCycle; + } + + QPair<T, T> cycle() const + { + return m_cycle; + } + + QList<T> sort() const + { + QSet<T> visitedNodes; + QList<T> resolvedNodes; + + m_hasCycle = false; + m_cycle = qMakePair(T(), T()); + foreach (const T &node, nodes()) + visit(node, &resolvedNodes, &visitedNodes); + return resolvedNodes; + } + + QList<T> sortReverse() const + { + QList<T> result = sort(); + std::reverse(result.begin(), result.end()); + return result; + } + +private: + void visit(const T &node, QList<T> *const resolvedNodes, QSet<T> *const visitedNodes) const + { + if (m_hasCycle) + return; + + // if we visited this node already + if (visitedNodes->contains(node)) { + // and if the node is already in the ordered list + if (resolvedNodes->contains(node)) + return; + + m_hasCycle = true; + m_cycle.second = node; + return; // if not yet in the ordered list, we detected a cycle + } + + // mark this node as visited + visitedNodes->insert(node); + + m_cycle.first = node; + // recursively visit all adjacency + foreach (const T &adjacency, edges(node)) + visit(adjacency, resolvedNodes, visitedNodes); + + // append this node the the ordered list + resolvedNodes->append(node); + } + +private: + mutable bool m_hasCycle; + QHash<T, QSet<T> > m_graph; + mutable QPair<T,T> m_cycle; +}; + +} +#endif // GRAPH_H diff --git a/src/libs/installer/installer.pro b/src/libs/installer/installer.pro index ab28aa72b..653b65d6f 100644 --- a/src/libs/installer/installer.pro +++ b/src/libs/installer/installer.pro @@ -111,7 +111,8 @@ HEADERS += packagemanagercore.h \ packagemanagercoredata.h \ registerqtincreatorqnxoperation.h \ applyproductkeyoperation.h \ - globals.h + globals.h \ + graph.h SOURCES += packagemanagercore.cpp \ packagemanagercore_p.cpp \ diff --git a/src/libs/installer/packagemanagercore_p.cpp b/src/libs/installer/packagemanagercore_p.cpp index 40ddf1c3a..17b7560aa 100644 --- a/src/libs/installer/packagemanagercore_p.cpp +++ b/src/libs/installer/packagemanagercore_p.cpp @@ -49,6 +49,7 @@ #include "fileutils.h" #include "fsengineclient.h" #include "globals.h" +#include "graph.h" #include "messageboxhandler.h" #include "packagemanagercore.h" #include "progresscoordinator.h" @@ -1329,9 +1330,15 @@ void PackageManagerCorePrivate::writeUninstaller(OperationList performedOperatio #endif } + performedOperations = sortOperationsBasedOnComponentDependencies( + performedOperations); + + m_core->setValue(QLatin1String("installedOperationAreSorted"), QLatin1String("true")); + try { KDSaveFile file(dataFile + QLatin1String(".new")); openForWrite(&file, file.fileName()); + writeUninstallerBinaryData(&file, &input, performedOperations, layout); appendInt64(&file, MagicCookieDat); file.setPermissions(file.permissions() | QFile::WriteUser | QFile::ReadGroup @@ -1612,8 +1619,14 @@ bool PackageManagerCorePrivate::runPackageUpdater() OperationList nonRevertedOperations; QHash<QString, Component *> componentsByName; + // order the operations in the right component dependency order + // next loop will save the needed operations in reverse order for uninstallation + OperationList performedOperationsOld = m_performedOperationsOld; + if (m_core->value(QLatin1String("installedOperationAreSorted")) != QLatin1String("true")) + performedOperationsOld = sortOperationsBasedOnComponentDependencies(m_performedOperationsOld); + // build a list of undo operations based on the checked state of the component - foreach (Operation *operation, m_performedOperationsOld) { + foreach (Operation *operation, performedOperationsOld) { const QString &name = operation->value(QLatin1String("component")).toString(); Component *component = componentsByName.value(name, 0); if (!component) @@ -1664,6 +1677,7 @@ bool PackageManagerCorePrivate::runPackageUpdater() continue; } + // uninstallation should be in reverse order so prepend it here undoOperations.prepend(operation); updateAdminRights |= operation->value(QLatin1String("admin")).toBool(); } @@ -2355,6 +2369,37 @@ void PackageManagerCorePrivate::connectOperationCallMethodRequest(Operation *con } } +OperationList PackageManagerCorePrivate::sortOperationsBasedOnComponentDependencies(const OperationList &operationList) +{ + OperationList sortedOperations; + QHash<QString, OperationList> componentOperationHash; + + // sort component unrelated operations to the beginning + foreach (Operation *operation, operationList) { + const QString componentName = operation->value(QLatin1String("component")).toString(); + if (componentName.isEmpty()) + sortedOperations.append(operation); + else { + OperationList componentOperationList = componentOperationHash.value(componentName); + componentOperationList.append(operation); + componentOperationHash.insert(operation->value(QLatin1String("component")).toString(), + componentOperationList); + } + } + + // create the complete component graph + Graph<QString> componentGraph; + foreach (const Component* componentNode, m_core->availableComponents()) { + componentGraph.addNode(componentNode->name()); + componentGraph.addEdges(componentNode->name(), componentNode->dependencies()); + } + + foreach (const QString &componentName, componentGraph.sort()) + sortedOperations.append(componentOperationHash.value(componentName)); + + return sortedOperations; +} + void PackageManagerCorePrivate::handleMethodInvocationRequest(const QString &invokableMethodName) { QObject *obj = QObject::sender(); diff --git a/src/libs/installer/packagemanagercore_p.h b/src/libs/installer/packagemanagercore_p.h index 11ed23230..d5bdc78fd 100644 --- a/src/libs/installer/packagemanagercore_p.h +++ b/src/libs/installer/packagemanagercore_p.h @@ -167,6 +167,7 @@ public: int countProgressOperations(const OperationList &operations); void connectOperationToInstaller(Operation *const operation, double progressOperationPartSize); void connectOperationCallMethodRequest(Operation *const operation); + OperationList sortOperationsBasedOnComponentDependencies(const OperationList &operationList); Operation *createOwnedOperation(const QString &type); Operation *takeOwnedOperation(Operation *operation); diff --git a/tests/auto/installer/installer.pro b/tests/auto/installer/installer.pro index f96e5f420..5873a8db8 100644 --- a/tests/auto/installer/installer.pro +++ b/tests/auto/installer/installer.pro @@ -11,4 +11,6 @@ SUBDIRS += \ scriptengine \ consumeoutputoperationtest \ mkdiroperationtest \ - copyoperationtest
\ No newline at end of file + copyoperationtest \ + solver + diff --git a/tests/auto/installer/solver/solver.pro b/tests/auto/installer/solver/solver.pro new file mode 100644 index 000000000..0094bc090 --- /dev/null +++ b/tests/auto/installer/solver/solver.pro @@ -0,0 +1,5 @@ +include(../../qttest.pri) + +QT -= gui + +SOURCES += tst_solver.cpp diff --git a/tests/auto/installer/solver/tst_solver.cpp b/tests/auto/installer/solver/tst_solver.cpp new file mode 100644 index 000000000..f0596b31e --- /dev/null +++ b/tests/auto/installer/solver/tst_solver.cpp @@ -0,0 +1,134 @@ +/************************************************************************** +** +** Copyright (C) 2012-2013 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the Qt Installer Framework. +** +** $QT_BEGIN_LICENSE:LGPL$ +** 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. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** +** $QT_END_LICENSE$ +** +**************************************************************************/ + +#include "graph.h" + +#include <QTest> + +using namespace QInstaller; + +class Data { +public: + Data() {} + explicit Data(const QString &data) + : m_data(data) {} + inline uint qHash(const Data &test); + QString data() const { return m_data; } + bool operator==(const Data &rhs) const { return m_data == rhs.m_data; } + const Data &operator=(const Data &rhs) { if (this != &rhs) { m_data = rhs.m_data; } return *this; } + +private: + QString m_data; +}; +inline uint qHash(const Data &data) +{ + return qHash(data.data()); +} + + +class tst_Solver : public QObject +{ + Q_OBJECT + +private slots: + // TODO: add failing cases + void sortGraph() + { + Graph<QString> graph; + graph.addNode("Hut"); + graph.addEdge("Jacke", "Shirt"); + graph.addEdge("Guertel", "Hose"); + graph.addEdge("Guertel", "Shirt"); + graph.addEdge("Shirt", "Socken"); + graph.addEdge("Socken", "Unterwaesche"); + graph.addEdge("Shirt", "Unterwaesche"); + graph.addEdges("Hose", QStringList() << "Unterwaesche" << "Socken"); + graph.addEdges("Krawatte", QStringList() << "Shirt" << "Hose" << "Guertel"); + graph.addEdges("Schuhe", QStringList() << "Socken" << "Unterwaesche" << "Hose"); + graph.addEdges("Jacke", QStringList() << "Hose" << "Shirt" << "Guertel" << "Schuhe" << "Krawatte"); + + QList<QString> resolved = graph.sort(); + foreach (const QString &value, resolved) + qDebug(qPrintable(value)); + } + + void sortGraphReverse() + { + Graph<QString> graph; + graph.addEdge("Krawatte", "Jacke"); + graph.addEdge("Guertel", "Jacke"); + graph.addEdge("Shirt", "Guertel"); + graph.addEdges("Shirt", QList<QString>() << "Krawatte" << "Schuhe"); + graph.addEdges("Hose", QList<QString>() << "Schuhe" << "Guertel" << "Shirt"); + graph.addEdges("Socken", QList<QString>() << "Schuhe" << "Hose"); + graph.addEdges("Unterwaesche", QList<QString>() << "Socken" << "Hose" << "Guertel" << "Shirt" + << "Krawatte" << "Schuhe"); + + QList<QString> resolved = graph.sortReverse(); + foreach (const QString &value, resolved) + qDebug(qPrintable(value)); + } + + void sortGraphCycle() + { + Data a("A"), b("B"), c("C"), d("D"), e("E"); + + Graph<Data> graph; + graph.addEdge(a, b); + graph.addEdge(b, c); + graph.addEdge(c, d); + graph.addEdge(d, e); + graph.addEdge(e, a); + + QList<Data> resolved = graph.sort(); + foreach (const Data &value, resolved) + qDebug(qPrintable(value.data())); + + QPair<Data, Data> cycle = graph.cycle(); + qDebug("Found cycle: %s", graph.hasCycle() ? "true" : "false"); + qDebug("(%s) has a indirect dependency on (%s).", qPrintable(cycle.second.data()), + qPrintable(cycle.first.data())); + } +}; + +QTEST_MAIN(tst_Solver) + +#include "tst_solver.moc" |