From 499cfb75b818e67e997b566583058d0b37badb8e Mon Sep 17 00:00:00 2001 From: Tim Jenssen Date: Tue, 6 Aug 2013 16:11:11 +0200 Subject: use dependency solver to order the installed operations - in case of single updates the order of the installed operations were wrong, now we reorder that till we are using that code for the install order aswell - added initial autotest for the dependency resolve code Task-number: QTIFW-318 Change-Id: If411a684cb02ef9e7d0316084075e86702bf839d Reviewed-by: Karsten Heimrich --- src/libs/installer/graph.h | 158 ++++++++++++++++++++++++++++ src/libs/installer/installer.pro | 3 +- src/libs/installer/packagemanagercore_p.cpp | 47 ++++++++- src/libs/installer/packagemanagercore_p.h | 1 + tests/auto/installer/installer.pro | 4 +- tests/auto/installer/solver/solver.pro | 5 + tests/auto/installer/solver/tst_solver.cpp | 134 +++++++++++++++++++++++ 7 files changed, 349 insertions(+), 3 deletions(-) create mode 100644 src/libs/installer/graph.h create mode 100644 tests/auto/installer/solver/solver.pro create mode 100644 tests/auto/installer/solver/tst_solver.cpp 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 +#include +#include +#include + +namespace QInstaller { + +template class Graph +{ +public: + inline Graph() {} + explicit Graph(const QList &nodes) + { + addNodes(nodes); + } + + const QList nodes() const + { + return m_graph.keys(); + } + + void addNode(const T &node) + { + m_graph.insert(node, QSet()); + } + + void addNodes(const QList &nodes) + { + foreach (const T &node, nodes) + addNode(node); + } + + QList 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 &edges) + { + foreach (const T &edge, edges) + addEdge(node, edge); + } + + bool hasCycle() const + { + return m_hasCycle; + } + + QPair cycle() const + { + return m_cycle; + } + + QList sort() const + { + QSet visitedNodes; + QList resolvedNodes; + + m_hasCycle = false; + m_cycle = qMakePair(T(), T()); + foreach (const T &node, nodes()) + visit(node, &resolvedNodes, &visitedNodes); + return resolvedNodes; + } + + QList sortReverse() const + { + QList result = sort(); + std::reverse(result.begin(), result.end()); + return result; + } + +private: + void visit(const T &node, QList *const resolvedNodes, QSet *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 > m_graph; + mutable QPair 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 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 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 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 + +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 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 resolved = graph.sort(); + foreach (const QString &value, resolved) + qDebug(qPrintable(value)); + } + + void sortGraphReverse() + { + Graph graph; + graph.addEdge("Krawatte", "Jacke"); + graph.addEdge("Guertel", "Jacke"); + graph.addEdge("Shirt", "Guertel"); + graph.addEdges("Shirt", QList() << "Krawatte" << "Schuhe"); + graph.addEdges("Hose", QList() << "Schuhe" << "Guertel" << "Shirt"); + graph.addEdges("Socken", QList() << "Schuhe" << "Hose"); + graph.addEdges("Unterwaesche", QList() << "Socken" << "Hose" << "Guertel" << "Shirt" + << "Krawatte" << "Schuhe"); + + QList 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 graph; + graph.addEdge(a, b); + graph.addEdge(b, c); + graph.addEdge(c, d); + graph.addEdge(d, e); + graph.addEdge(e, a); + + QList resolved = graph.sort(); + foreach (const Data &value, resolved) + qDebug(qPrintable(value.data())); + + QPair 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" -- cgit v1.2.3