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 + 4 files changed, 207 insertions(+), 2 deletions(-) create mode 100644 src/libs/installer/graph.h (limited to 'src/libs/installer') 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); -- cgit v1.2.3