shiboken6: Rewite the graph sorter

Change the Graph used for dependency sorting from a graph
using integer node numbers to a template taking the Node value,
relying on operator==() (and its qDebug() operators).

The mapping of node to indexes can then be removed from the client code,
leading to a significant simplification.

As a side effect, this fixes undefined behavior of the overload
sorter in conjunction with reverse binary operators. It was not handling
overloads of the same decisor argument type correctly, leading to
graphs with duplicated node types for them.

Rewrite the toposort test to be data driven.

Change-Id: Idbe896dc81d7272099db6dab3d2673643fc17401
Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org>
Reviewed-by: Cristian Maureira-Fredes <cristian.maureira-fredes@qt.io>
(cherry picked from commit 7626f04ac855a56d4b364eac7b8350bdd561fef0)

7 files changed, 430 insertions, 395 deletions

diff --git a/sources/shiboken6/ApiExtractor/CMakeLists.txt b/sources/shiboken6/ApiExtractor/CMakeLists.txt
index f1adffbf6..c4bb5f09c 100644
--- a/sources/shiboken6/ApiExtractor/CMakeLists.txt
+++ b/sources/shiboken6/ApiExtractor/CMakeLists.txt
@@ -18,7 +18,6 @@ abstractmetalang.cpp
 documentation.cpp
 enclosingclassmixin.cpp
 fileout.cpp
-graph.cpp
 messages.cpp
 modifications.cpp
 propertyspec.cpp
diff --git a/sources/shiboken6/ApiExtractor/abstractmetabuilder.cpp b/sources/shiboken6/ApiExtractor/abstractmetabuilder.cpp
index 5e914a989..ad354d901 100644
--- a/sources/shiboken6/ApiExtractor/abstractmetabuilder.cpp
+++ b/sources/shiboken6/ApiExtractor/abstractmetabuilder.cpp
@@ -2998,55 +2998,29 @@ void AbstractMetaBuilderPrivate::dumpLog() const
     writeRejectLogFile(m_logDirectory + QLatin1String("mjb_rejected_fields.log"), m_rejectedFields);
 }
 
-using ClassIndexHash = QHash<const AbstractMetaClass *, int>;
-
-static ClassIndexHash::ConstIterator findByTypeEntry(const ClassIndexHash &map,
-                                                     const TypeEntry *typeEntry)
-{
-    auto it = map.cbegin();
-    for (auto end = map.cend(); it != end; ++it) {
-        if (it.key()->typeEntry() == typeEntry)
-            break;
-    }
-    return it;
-}
+using ClassGraph = Graph<AbstractMetaClass *>;
 
 // Add a dependency of the class associated with typeEntry on clazz
-static void addClassDependency(const TypeEntry *typeEntry,
-                               const AbstractMetaClass *clazz,
-                               int classIndex, const  ClassIndexHash &map,
-                               Graph *graph)
+static bool addClassDependency(const AbstractMetaClassList &classList,
+                               const TypeEntry *typeEntry,
+                               AbstractMetaClass *clazz,
+                               ClassGraph *graph)
 {
-    if (typeEntry->isComplex() && typeEntry != clazz->typeEntry()) {
-        const auto it = findByTypeEntry(map, typeEntry);
-        if (it != map.cend() && it.key()->enclosingClass() != clazz)
-            graph->addEdge(it.value(), classIndex);
-    }
+    if (!typeEntry->isComplex() || typeEntry == clazz->typeEntry())
+        return false;
+    const auto c = AbstractMetaClass::findClass(classList, typeEntry);
+    if (c == nullptr || c->enclosingClass() == clazz)
+        return false;
+    return graph->addEdge(c, clazz);
 }
 
 AbstractMetaClassList AbstractMetaBuilderPrivate::classesTopologicalSorted(const AbstractMetaClassList &classList,
                                                                            const Dependencies &additionalDependencies) const
 {
-    ClassIndexHash map;
-    QHash<int, AbstractMetaClass *> reverseMap;
-
-    int i = 0;
-    for (AbstractMetaClass *clazz : classList) {
-        if (map.contains(clazz))
-            continue;
-        map.insert(clazz, i);
-        reverseMap.insert(i, clazz);
-        i++;
-    }
-
-    Graph graph(map.count());
+    ClassGraph graph(classList.cbegin(), classList.cend());
 
     for (const auto &dep : additionalDependencies) {
-        const int parentIndex = map.value(dep.parent, -1);
-        const int childIndex = map.value(dep.child, -1);
-        if (parentIndex >= 0 && childIndex >= 0) {
-            graph.addEdge(parentIndex, childIndex);
-        } else {
+        if (!graph.addEdge(dep.parent, dep.child)) {
             qCWarning(lcShiboken).noquote().nospace()
                 << "AbstractMetaBuilder::classesTopologicalSorted(): Invalid additional dependency: "
                 << dep.child->name() << " -> " << dep.parent->name() << '.';
@@ -3054,19 +3028,14 @@ AbstractMetaClassList AbstractMetaBuilderPrivate::classesTopologicalSorted(const
     }
 
     for (AbstractMetaClass *clazz : classList) {
-        const int classIndex = map.value(clazz);
-        if (auto enclosing = clazz->enclosingClass()) {
-            const auto enclosingIt = map.constFind(const_cast< AbstractMetaClass *>(enclosing));
-            if (enclosingIt!= map.cend())
-                graph.addEdge(enclosingIt.value(), classIndex);
+        if (auto enclosingC = clazz->enclosingClass()) {
+            auto enclosing = const_cast<AbstractMetaClass *>(enclosingC);
+            graph.addEdge(enclosing, clazz);
         }
 
         const AbstractMetaClassList &bases = getBaseClasses(clazz);
-        for (AbstractMetaClass *baseClass : bases) {
-            const auto baseIt = map.constFind(baseClass);
-            if (baseIt!= map.cend())
-                graph.addEdge(baseIt.value(), classIndex);
-        }
+        for (AbstractMetaClass *baseClass : bases)
+            graph.addEdge(baseClass, clazz);
 
         for (const auto &func : clazz->functions()) {
             const AbstractMetaArgumentList &arguments = func->arguments();
@@ -3075,44 +3044,36 @@ AbstractMetaClassList AbstractMetaBuilderPrivate::classesTopologicalSorted(const
                 // ("QString s = QString()"), add a dependency.
                 if (!arg.originalDefaultValueExpression().isEmpty()
                     && arg.type().isValue()) {
-                    addClassDependency(arg.type().typeEntry(), clazz, classIndex,
-                                       map, &graph);
+                    addClassDependency(classList, arg.type().typeEntry(),
+                                       clazz, &graph);
                 }
             }
         }
         // Member fields need to be initialized
         for (const AbstractMetaField &field : clazz->fields()) {
-            addClassDependency(field.type().typeEntry(), clazz, classIndex,
-                               map, &graph);
+            addClassDependency(classList, field.type().typeEntry(),
+                               clazz, &graph);
         }
     }
 
-    AbstractMetaClassList result;
-    const auto unmappedResult = graph.topologicalSort();
-    if (!unmappedResult.isValid() && graph.nodeCount()) {
+    const auto result = graph.topologicalSort();
+    if (!result.isValid() && graph.nodeCount()) {
         QTemporaryFile tempFile(QDir::tempPath() + QLatin1String("/cyclic_depXXXXXX.dot"));
         tempFile.setAutoRemove(false);
         tempFile.open();
-        QHash<int, QString> hash;
-        for (auto it = map.cbegin(), end = map.cend(); it != end; ++it)
-            hash.insert(it.value(), it.key()->qualifiedCppName());
-        graph.dumpDot(hash, tempFile.fileName());
+        graph.dumpDot(tempFile.fileName(),
+                      [] (const AbstractMetaClass *c) { return c->name(); });
 
         QString message;
         QTextStream str(&message);
         str << "Cyclic dependency of classes found:";
-        for (int c : unmappedResult.cyclic)
-            str << ' ' <<  reverseMap.value(c)->name();
+        for (auto c : result.cyclic)
+            str << ' ' << c->name();
         str << ". Graph can be found at \"" << QDir::toNativeSeparators(tempFile.fileName()) << '"';
         qCWarning(lcShiboken, "%s", qPrintable(message));
-    } else {
-        for (int i : qAsConst(unmappedResult.result)) {
-            Q_ASSERT(reverseMap.contains(i));
-            result << reverseMap[i];
-        }
     }
 
-    return result;
+    return result.result;
 }
 
 void AbstractMetaBuilderPrivate::pushScope(const NamespaceModelItem &item)
diff --git a/sources/shiboken6/ApiExtractor/graph.cpp b/sources/shiboken6/ApiExtractor/graph.cpp
deleted file mode 100644
index da7d7a2a1..000000000
--- a/sources/shiboken6/ApiExtractor/graph.cpp
+++ /dev/null
@@ -1,139 +0,0 @@
-/****************************************************************************
-**
-** Copyright (C) 2016 The Qt Company Ltd.
-** Contact: https://www.qt.io/licensing/
-**
-** This file is part of Qt for Python.
-**
-** $QT_BEGIN_LICENSE:GPL-EXCEPT$
-** 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 The Qt Company. For licensing terms
-** and conditions see https://www.qt.io/terms-conditions. For further
-** information use the contact form at https://www.qt.io/contact-us.
-**
-** GNU General Public License Usage
-** Alternatively, this file may be used under the terms of the GNU
-** General Public License version 3 as published by the Free Software
-** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
-** included in the packaging of this file. Please review the following
-** information to ensure the GNU General Public License requirements will
-** be met: https://www.gnu.org/licenses/gpl-3.0.html.
-**
-** $QT_END_LICENSE$
-**
-****************************************************************************/
-
-#include "graph.h"
-#include <QList>
-#include <QDebug>
-#include <QSet>
-#include <iterator>
-#include <algorithm>
-#include <iostream>
-#include <QFile>
-
-struct Graph::GraphPrivate
-{
-    enum Color { WHITE, GRAY, BLACK };
-    using Edges = QList<QSet<int> >;
-
-    Edges edges;
-
-    GraphPrivate(int numNodes) : edges(numNodes)
-    {
-    }
-
-    void dfsVisit(int node, Graph::Indexes &result, QList<Color> &colors) const
-    {
-        colors[node] = GRAY;
-        for (const auto &c : edges.at(node)) {
-            if (colors[c] == WHITE)
-                dfsVisit(c, result, colors);
-            else if (colors[c] == GRAY) // This is not a DAG!
-                return;
-        }
-        colors[node] = BLACK;
-        result.append(node);
-    }
-};
-
-Graph::Graph(int numNodes) : m_d(new GraphPrivate(numNodes))
-{
-}
-
-Graph::~Graph()
-{
-    delete m_d;
-}
-
-int Graph::nodeCount() const
-{
-    return m_d->edges.size();
-}
-
-Graph::SortResult Graph::topologicalSort() const
-{
-    const int nodeCount = Graph::nodeCount();
-    SortResult result;
-    result.result.reserve(nodeCount);
-
-    QList<GraphPrivate::Color> colors(nodeCount, GraphPrivate::WHITE);
-
-    for (int i = 0; i < nodeCount; ++i) {
-        if (colors[i] == GraphPrivate::WHITE)
-            m_d->dfsVisit(i, result.result, colors);
-    }
-
-    if (result.result.size() == nodeCount) {
-        std::reverse(result.result.begin(), result.result.end());
-    } else {
-        for (int i = 0; i < nodeCount; ++i) {
-            if (!result.result.contains(i))
-                result.cyclic.append(i);
-        }
-        result.result.clear(); // Not a DAG!
-    }
-    return result;
-}
-
-bool Graph::containsEdge(int from, int to)
-{
-    return m_d->edges[from].contains(to);
-}
-
-void Graph::addEdge(int from, int to)
-{
-    Q_ASSERT(to < m_d->edges.size());
-    m_d->edges[from].insert(to);
-}
-
-void Graph::removeEdge(int from, int to)
-{
-    m_d->edges[from].remove(to);
-}
-
-void Graph::dump() const
-{
-    for (int i = 0; i < m_d->edges.size(); ++i) {
-        std::cout << i << " -> ";
-        std::copy(m_d->edges[i].begin(), m_d->edges[i].end(), std::ostream_iterator<int>(std::cout, " "));
-        std::cout << std::endl;
-    }
-}
-
-void Graph::dumpDot(const QHash< int, QString >& nodeNames, const QString& fileName) const
-{
-    QFile output(fileName);
-    if (!output.open(QIODevice::WriteOnly))
-        return;
-    QTextStream s(&output);
-    s << "digraph D {\n";
-    for (int i = 0; i < m_d->edges.size(); ++i) {
-        for (auto it = m_d->edges[i].cbegin(), end = m_d->edges[i].cend(); it != end; ++it)
-            s << '"' << nodeNames[i] << "\" -> \"" << nodeNames[*it] << "\"\n";
-    }
-    s << "}\n";
-}
diff --git a/sources/shiboken6/ApiExtractor/graph.h b/sources/shiboken6/ApiExtractor/graph.h
index ffba00834..0961f85af 100644
--- a/sources/shiboken6/ApiExtractor/graph.h
+++ b/sources/shiboken6/ApiExtractor/graph.h
@@ -1,6 +1,6 @@
 /****************************************************************************
 **
-** Copyright (C) 2016 The Qt Company Ltd.
+** Copyright (C) 2020 The Qt Company Ltd.
 ** Contact: https://www.qt.io/licensing/
 **
 ** This file is part of Qt for Python.
@@ -29,56 +29,294 @@
 #ifndef GRAPH_H
 #define GRAPH_H
 
-#include <QList>
-#include <QHash>
-#include <QString>
+#include <QtCore/QDebug>
+#include <QtCore/QFile>
+#include <QtCore/QHash>
+#include <QtCore/QList>
+#include <QtCore/QString>
+#include <QtCore/QTextStream>
 
-/// A graph that can have their nodes topologically sorted.
+#include <algorithm>
+
+/// Result of topologically sorting of a graph (list of nodes in order
+/// or list of nodes that have cyclic dependencies).
+template <class Node>
+struct GraphSortResult
+{
+    using NodeList = QList<Node>;
+
+    bool isValid() const { return !result.isEmpty() && cyclic.isEmpty(); }
+    void format(QDebug &debug) const;
+
+    NodeList result;
+    NodeList cyclic;
+};
+
+/// A graph that can have its nodes topologically sorted. The nodes need to
+/// have operator==().
+template <class Node>
 class Graph
 {
 public:
-    Q_DISABLE_COPY(Graph)
+    using NodeList = QList<Node>;
+
+    Graph() = default;
 
-    using Indexes = QList<int>;
+    // Construct from a sequence of nodes
+    template<class It>
+    explicit Graph(It i1, It i2) { setNodes(i1, i2); }
 
-    struct SortResult
+    template<class It>
+    void setNodes(It i1, It i2)
     {
-        bool isValid() const { return !result.isEmpty() && cyclic.isEmpty(); }
-        Indexes result;
-        Indexes cyclic;
-    };
+        for (; i1 != i2; ++i1)
+            addNode(*i1);
+    }
+
+    bool addNode(Node n);
 
-    /// Create a new graph with \p numNodes nodes.
-    Graph(int numNodes);
-    ~Graph();
+    /// Returns whether node was registered
+    bool hasNode(Node node) { return indexOfNode(node) != -1; }
 
     /// Returns the numbed of nodes in this graph.
-    int nodeCount() const;
+    qsizetype nodeCount() const { return m_nodeEntries.size(); }
+
     /// Returns true if the graph contains the edge from -> to
-    bool containsEdge(int from, int to);
+    bool containsEdge(Node from, Node to) const;
+    /// Returns true if the graph has any edges
+    bool hasEdges() const;
+
     /// Adds an edge to this graph.
-    void addEdge(int from, int to);
-    /// Removes an edge out of this graph.
-    void removeEdge(int from, int to);
-    /// Print this graph to stdout.
-    void dump() const;
-    /**
-    *   Dumps a dot graph to a file named \p filename.
-    *   \param nodeNames map used to translate node ids to human readable text.
-    *   \param fileName file name where the output should be written.
-    */
-    void dumpDot(const QHash<int, QString>& nodeNames, const QString& fileName) const;
+    bool addEdge(Node from, Node to);
+    /// Removes an edge from this graph.
+    bool removeEdge(Node from, Node to);
+    /// Clears the graph
+    void clear() { m_nodeEntries.clear(); }
+
+    /// Dumps a dot graph to a file named \p filename.
+    /// \param fileName file name where the output should be written.
+    /// \param f function returning the name of a node
+    template <class NameFunction>
+    bool dumpDot(const QString& fileName, NameFunction f) const;
+
+    void format(QDebug &debug) const;
 
     /**
     *   Topologically sort this graph.
     *   \return A collection with all nodes topologically sorted or an empty collection if a cyclic
     *   dependency was found.
     */
-    SortResult topologicalSort() const;
+    GraphSortResult<Node> topologicalSort() const;
+
 private:
+    enum Color { WHITE, GRAY, BLACK };
+
+    struct NodeEntry
+    {
+        Node node;
+        NodeList targets;
+        mutable Color color;
+    };
+
+    Color colorAt(qsizetype i) const { return m_nodeEntries.at(i).color; }
+    qsizetype indexOfNode(Node n) const;
+    void depthFirstVisit(qsizetype i, NodeList &result) const;
 
-    struct GraphPrivate;
-    GraphPrivate* m_d;
+    QList<NodeEntry> m_nodeEntries;
 };
 
-#endif
+template <class Node>
+qsizetype Graph<Node>::indexOfNode(Node n) const
+{
+    for (qsizetype i = 0, size = m_nodeEntries.size(); i < size; ++i) {
+        if (m_nodeEntries.at(i).node == n)
+            return i;
+    }
+    return -1;
+}
+
+template <class Node>
+bool Graph<Node>::addNode(Node n)
+{
+    if (hasNode(n))
+        return false;
+    m_nodeEntries.append({n, {}, WHITE});
+    return true;
+}
+
+template <class Node>
+void Graph<Node>::depthFirstVisit(qsizetype i, NodeList &result) const
+{
+    m_nodeEntries[i].color = GRAY;
+
+    for (auto to : m_nodeEntries[i].targets) {
+        const qsizetype toIndex = indexOfNode(to);
+        Q_ASSERT(toIndex != -1);
+        switch (colorAt(toIndex)) {
+        case WHITE:
+            depthFirstVisit(toIndex, result);
+            break;
+        case GRAY:
+            return; // This is not a DAG!
+        case BLACK:
+            break;
+        }
+    }
+
+    m_nodeEntries[i].color = BLACK;
+
+    result.append(m_nodeEntries.at(i).node);
+}
+
+template <class Node>
+GraphSortResult<Node> Graph<Node>::topologicalSort() const
+{
+    const qsizetype size = m_nodeEntries.size();
+
+    GraphSortResult<Node> result;
+    result.result.reserve(size);
+
+    if (hasEdges()) {
+        for (qsizetype i = 0; i < size; ++i)
+            m_nodeEntries[i].color = WHITE;
+        for (qsizetype i = 0; i < size; ++i)  {
+            if (colorAt(i) == WHITE) // recursive calls may have set it to black
+                depthFirstVisit(i, result.result);
+        }
+    } else { // no edges, shortcut
+        std::transform(m_nodeEntries.cbegin(), m_nodeEntries.cend(),
+                       std::back_inserter(result.result),
+                       [](const NodeEntry &ne) { return ne.node; });
+    }
+
+    if (result.result.size() == size) {
+        std::reverse(result.result.begin(), result.result.end());
+    } else {
+        for (const auto &nodeEntry : m_nodeEntries) {
+            if (!result.result.contains(nodeEntry.node))
+                result.cyclic.append(nodeEntry.node);
+        }
+        result.result.clear(); // Not a DAG!
+    }
+    return result;
+}
+
+template <class Node>
+bool Graph<Node>::containsEdge(Node from, Node to) const
+{
+    const qsizetype i = indexOfNode(from);
+    return i != -1 && m_nodeEntries.at(i).targets.contains(to);
+}
+
+template <class Node>
+bool Graph<Node>::hasEdges() const
+{
+    for (const auto &nodeEntry : m_nodeEntries) {
+        if (!nodeEntry.targets.isEmpty())
+            return true;
+    }
+    return false;
+}
+
+template <class Node>
+bool Graph<Node>::addEdge(Node from, Node to)
+{
+    const qsizetype i = indexOfNode(from);
+    if (i == -1 || !hasNode(to) || m_nodeEntries.at(i).targets.contains(to))
+        return false;
+    m_nodeEntries[i].targets.append(to);
+    return true;
+}
+
+template <class Node>
+bool Graph<Node>::removeEdge(Node from, Node to)
+{
+    const qsizetype i = indexOfNode(from);
+    if (i == -1)
+        return false;
+    auto &targets = m_nodeEntries[i].targets;
+    const qsizetype toIndex = targets.indexOf(to);
+    if (toIndex == -1)
+        return false;
+    targets.removeAt(toIndex);
+    return true;
+}
+
+template <class Node>
+template <class NameFunction>
+bool Graph<Node>::dumpDot(const QString& fileName,
+                          NameFunction nameFunction) const
+{
+    QFile output(fileName);
+    if (!output.open(QIODevice::WriteOnly))
+        return false;
+    QTextStream s(&output);
+    s << "digraph D {\n";
+    for (const auto &nodeEntry : m_nodeEntries) {
+        if (!nodeEntry.targets.isEmpty()) {
+            const QString fromName = nameFunction(nodeEntry.node);
+            for (const Node &to : nodeEntry.targets)
+                s << '"' << fromName << "\" -> \"" << nameFunction(to) << "\"\n";
+        }
+    }
+    s << "}\n";
+    return true;
+}
+
+template <class Node>
+void Graph<Node>::format(QDebug &debug) const
+{
+    const qsizetype size = m_nodeEntries.size();
+    debug << "nodes[" << size << "] = (";
+    for (qsizetype i = 0; i < size; ++i) {
+        const auto &nodeEntry = m_nodeEntries.at(i);
+        if (i)
+            debug << ", ";
+        debug << nodeEntry.node;
+        if (!nodeEntry.targets.isEmpty()) {
+            debug << " -> [";
+            for (qsizetype t = 0, tsize = nodeEntry.targets.size(); t < tsize; ++t) {
+                if (t)
+                    debug << ", ";
+                debug << nodeEntry.targets.at(t);
+            }
+            debug << ']';
+        }
+    }
+    debug << ')';
+}
+
+template <class Node>
+QDebug operator<<(QDebug debug, const Graph<Node> &g)
+{
+    QDebugStateSaver saver(debug);
+    debug.noquote();
+    debug.nospace();
+    debug << "Graph(";
+    g.format(debug);
+    debug << ')';
+    return debug;
+}
+
+template <class Node>
+void GraphSortResult<Node>::format(QDebug &debug) const
+{
+    if (isValid())
+        debug << "Valid, " << result;
+    else
+        debug << "Invalid, cyclic dependencies: " << cyclic;
+}
+
+template <class Node>
+QDebug operator<<(QDebug debug, const GraphSortResult<Node> &r)
+{
+    QDebugStateSaver saver(debug);
+    debug.noquote();
+    debug.nospace();
+    debug << "Graph::SortResult(";
+    r.format(debug);
+    debug << ')';
+    return debug;
+}
+
+#endif // GRAPH_H
diff --git a/sources/shiboken6/ApiExtractor/tests/testtoposort.cpp b/sources/shiboken6/ApiExtractor/tests/testtoposort.cpp
index 25eb99e50..6126c2b42 100644
--- a/sources/shiboken6/ApiExtractor/tests/testtoposort.cpp
+++ b/sources/shiboken6/ApiExtractor/tests/testtoposort.cpp
@@ -1,6 +1,6 @@
 /****************************************************************************
 **
-** Copyright (C) 2016 The Qt Company Ltd.
+** Copyright (C) 2020 The Qt Company Ltd.
 ** Contact: https://www.qt.io/licensing/
 **
 ** This file is part of the test suite of Qt for Python.
@@ -27,47 +27,59 @@
 ****************************************************************************/
 
 #include "testtoposort.h"
-#include <QtTest/QTest>
 #include "graph.h"
-#include <QDebug>
 
-void TestTopoSort::testTopoSort()
-{
-    {
-        Graph g(3);
-        g.addEdge(1, 2);
-        g.addEdge(0, 1);
-        const auto result = g.topologicalSort();
-        QVERIFY(result.isValid());
-        QVERIFY(result.cyclic.isEmpty());
-        QCOMPARE(result.result.size(), 3);
-        auto it = result.result.begin();
-        QCOMPARE(*it, 0);
-        QCOMPARE(*(++it), 1);
-        QCOMPARE(*(++it), 2);
-    }
-    {
-        Graph g(2);
-        const auto result = g.topologicalSort();
-        QVERIFY(result.isValid());
-        QVERIFY(result.cyclic.isEmpty());
-        QCOMPARE(result.result.size(), 2);
-        auto it = result.result.begin();
-        QCOMPARE(*it, 1);
-        QCOMPARE(*(++it), 0);
-    }
-}
+#include <QtTest/QTest>
+#include <QtCore/QDebug>
+
+using IntGraph = Graph<int>;
+
+Q_DECLARE_METATYPE(IntGraph)
+
+using IntList = QList<int>;
 
-void TestTopoSort::testCyclicGraph()
+void TestTopoSort::testTopoSort_data()
 {
-    Graph g(3);
+    QTest::addColumn<IntGraph>("graph");
+    QTest::addColumn<bool>("expectedValid");
+    QTest::addColumn<IntList>("expectedOrder");
+
+    const int nodes1[] = {0, 1, 2};
+    IntGraph g(std::begin(nodes1), std::end(nodes1));
+    g.addEdge(1, 2);
+    g.addEdge(0, 1);
+    IntList expected = {0, 1, 2};
+    QTest::newRow("DAG") << g << true << expected;
+
+    const int nodes2[] = {0, 1};
+    g.clear();
+    g.setNodes(std::begin(nodes2), std::end(nodes2));
+    expected = {1, 0};
+    QTest::newRow("No edges") << g << true << expected;
+
+    g.clear();
+    g.setNodes(std::begin(nodes1), std::end(nodes1));
     g.addEdge(0, 1);
     g.addEdge(1, 2);
     g.addEdge(2, 0);
-    const auto result = g.topologicalSort();
-    QVERIFY(!result.isValid());
-    QVERIFY(result.result.isEmpty());
-    QVERIFY(!result.cyclic.isEmpty());
+    expected.clear();
+    QTest::newRow("Cyclic") << g << false << expected;
+}
+
+void TestTopoSort::testTopoSort()
+{
+    QFETCH(IntGraph, graph);
+    QFETCH(bool, expectedValid);
+    QFETCH(IntList, expectedOrder);
+
+    const auto result = graph.topologicalSort();
+    QCOMPARE(result.isValid(), expectedValid);
+    if (expectedValid) {
+        QCOMPARE(result.result, expectedOrder);
+        QVERIFY(result.cyclic.isEmpty());
+    } else {
+        QVERIFY(!result.cyclic.isEmpty());
+    }
 }
 
 QTEST_APPLESS_MAIN(TestTopoSort)
diff --git a/sources/shiboken6/ApiExtractor/tests/testtoposort.h b/sources/shiboken6/ApiExtractor/tests/testtoposort.h
index 7caafc87f..012156dc9 100644
--- a/sources/shiboken6/ApiExtractor/tests/testtoposort.h
+++ b/sources/shiboken6/ApiExtractor/tests/testtoposort.h
@@ -1,6 +1,6 @@
 /****************************************************************************
 **
-** Copyright (C) 2016 The Qt Company Ltd.
+** Copyright (C) 2020 The Qt Company Ltd.
 ** Contact: https://www.qt.io/licensing/
 **
 ** This file is part of the test suite of Qt for Python.
@@ -35,8 +35,8 @@ class TestTopoSort : public QObject
 {
 Q_OBJECT
 private slots:
+    void testTopoSort_data();
     void testTopoSort();
-    void testCyclicGraph();
 };
 
 #endif
diff --git a/sources/shiboken6/generator/shiboken/overloaddata.cpp b/sources/shiboken6/generator/shiboken/overloaddata.cpp
index 1ff9a74a8..4f887fc87 100644
--- a/sources/shiboken6/generator/shiboken/overloaddata.cpp
+++ b/sources/shiboken6/generator/shiboken/overloaddata.cpp
@@ -91,43 +91,6 @@ static bool typesAreEqual(const AbstractMetaType &typeA, const AbstractMetaType
     return false;
 }
 
-
-/**
- * OverloadSortData just helps writing clearer code in the
- * OverloadData::sortNextOverloads method.
- */
-struct OverloadSortData
-{
-    /**
-     * Adds a typeName into the type map without associating it with
-     * a OverloadData. This is done to express type dependencies that could
-     * or could not appear in overloaded signatures not processed yet.
-     */
-    void mapType(const QString &typeName)
-    {
-        if (map.contains(typeName))
-            return;
-        map[typeName] = counter;
-        if (!reverseMap.contains(counter))
-            reverseMap[counter] = nullptr;
-        counter++;
-    }
-
-    void mapType(OverloadData *overloadData)
-    {
-        QString typeName = getTypeName(overloadData);
-        map[typeName] = counter;
-        reverseMap[counter] = overloadData;
-        counter++;
-    }
-
-    int lastProcessedItemId() { return counter - 1; }
-
-    int counter = 0;
-    QHash<QString, int> map;                // typeName -> id
-    QHash<int, OverloadData *> reverseMap;   // id -> OverloadData;
-};
-
 /**
  * Helper function that returns the name of a container get from containerType argument and
  * an instantiation taken either from an implicit conversion expressed by the function argument,
@@ -197,6 +160,12 @@ bool OverloadData::sortByOverloadNumberModification()
     return true;
 }
 
+static inline QString pyObjectT() { return QStringLiteral("PyObject"); }
+static inline QString pySequenceT() { return QStringLiteral("PySequence"); }
+static inline QString pyBufferT() { return QStringLiteral("PyBuffer"); }
+
+using OverloadGraph = Graph<QString>;
+
 /**
  * Topologically sort the overloads by implicit convertion order
  *
@@ -209,17 +178,13 @@ bool OverloadData::sortByOverloadNumberModification()
  */
 void OverloadData::sortNextOverloads()
 {
-    OverloadSortData sortData;
+    QHash<QString, OverloadDataList> typeToOverloads;
+
     bool checkPyObject = false;
-    int pyobjectIndex = 0;
     bool checkPySequence = false;
-    int pySeqIndex = 0;
     bool checkQString = false;
-    int qstringIndex = 0;
     bool checkQVariant = false;
-    int qvariantIndex = 0;
     bool checkPyBuffer = false;
-    int pyBufferIndex = 0;
 
     // Primitive types that are not int, long, short,
     // char and their respective unsigned counterparts.
@@ -238,32 +203,32 @@ void OverloadData::sortNextOverloads()
     // Populates the OverloadSortData object containing map and reverseMap, to map type names to ids,
     // these ids will be used by the topological sort algorithm, because is easier and faster to work
     // with graph sorting using integers.
-    for (OverloadData *ov : qAsConst(m_nextOverloadData)) {
-        sortData.mapType(ov);
 
-        const QString typeName(getTypeName(ov));
+    OverloadGraph graph;
+    for (OverloadData *ov : qAsConst(m_nextOverloadData)) {
+        const QString typeName = getTypeName(ov);
+        auto it = typeToOverloads.find(typeName);
+        if (it == typeToOverloads.end()) {
+            typeToOverloads.insert(typeName, {ov});
+            graph.addNode(typeName);
+        } else {
+            it.value().append(ov);
+        }
 
-        if (!checkPyObject && typeName.contains(QLatin1String("PyObject"))) {
+        if (!checkPyObject && typeName == pyObjectT())
             checkPyObject = true;
-            pyobjectIndex = sortData.lastProcessedItemId();
-        } else if (!checkPySequence && typeName == QLatin1String("PySequence")) {
+        else if (!checkPySequence && typeName == pySequenceT())
             checkPySequence = true;
-            pySeqIndex = sortData.lastProcessedItemId();
-        } else if (!checkPyBuffer && typeName == QLatin1String("PyBuffer")) {
+        else if (!checkPyBuffer && typeName == pyBufferT())
             checkPyBuffer = true;
-            pyBufferIndex = sortData.lastProcessedItemId();
-        } else if (!checkQVariant && typeName == qVariantT()) {
+        else if (!checkQVariant && typeName == qVariantT())
             checkQVariant = true;
-            qvariantIndex = sortData.lastProcessedItemId();
-        } else if (!checkQString && typeName == qStringT()) {
+        else if (!checkQString && typeName == qStringT())
             checkQString = true;
-            qstringIndex = sortData.lastProcessedItemId();
-        }
 
         for (const auto &instantiation : ov->argType().instantiations()) {
             // Add dependencies for type instantiation of container.
-            QString typeName = getTypeName(instantiation);
-            sortData.mapType(typeName);
+            graph.addNode(getTypeName(instantiation));
 
             // Build dependency for implicit conversion types instantiations for base container.
             // For example, considering signatures "method(list<PointF>)" and "method(list<Point>)",
@@ -272,32 +237,30 @@ void OverloadData::sortNextOverloads()
             // be called. In the case of primitive types, list<double> must come before list<int>.
             if (instantiation.isPrimitive() && (signedIntegerPrimitives.contains(instantiation.name()))) {
                 for (const QString &primitive : qAsConst(nonIntegerPrimitives))
-                    sortData.mapType(getImplicitConversionTypeName(ov->argType(), instantiation, nullptr, primitive));
+                    graph.addNode(getImplicitConversionTypeName(ov->argType(), instantiation, nullptr, primitive));
             } else {
                 const auto &funcs = m_generator->implicitConversions(instantiation);
                 for (const auto &function : funcs)
-                    sortData.mapType(getImplicitConversionTypeName(ov->argType(), instantiation, function));
+                    graph.addNode(getImplicitConversionTypeName(ov->argType(), instantiation, function));
             }
         }
     }
 
 
     // Create the graph of type dependencies based on implicit conversions.
-    Graph graph(sortData.reverseMap.count());
     // All C++ primitive types, add any forgotten type AT THE END OF THIS LIST!
     static const QStringList primitiveTypes{intT(), unsignedIntT(), longT(), unsignedLongT(),
         shortT(), unsignedShortT(), boolT(), unsignedCharT(), charT(), floatT(),
         doubleT(), constCharPtrT()};
 
-    QList<int> foundPrimitiveTypeIds;
+    QStringList foundPrimitiveTypeIds;
     for (const auto &p : primitiveTypes) {
-        const auto it = sortData.map.constFind(p);
-        if (it != sortData.map.cend())
-            foundPrimitiveTypeIds.append(it.value());
+        if (graph.hasNode(p))
+            foundPrimitiveTypeIds.append(p);
     }
 
     if (checkPySequence && checkPyObject)
-        graph.addEdge(pySeqIndex, pyobjectIndex);
+        graph.addEdge(pySequenceT(), pyObjectT());
 
     QStringList classesWithIntegerImplicitConversion;
 
@@ -305,8 +268,7 @@ void OverloadData::sortNextOverloads()
 
     for (OverloadData *ov : qAsConst(m_nextOverloadData)) {
         const AbstractMetaType &targetType = ov->argType();
-        const QString targetTypeEntryName(getTypeName(ov));
-        int targetTypeId = sortData.map[targetTypeEntryName];
+        const QString targetTypeEntryName = getTypeName(ov);
 
         // Process implicit conversions
         const auto &functions = m_generator->implicitConversions(targetType);
@@ -320,15 +282,13 @@ void OverloadData::sortNextOverloads()
             if (convertibleType == intT() || convertibleType == unsignedIntT())
                 classesWithIntegerImplicitConversion << targetTypeEntryName;
 
-            if (!sortData.map.contains(convertibleType))
+            if (!graph.hasNode(convertibleType))
                 continue;
 
-            int convertibleTypeId = sortData.map[convertibleType];
-
             // If a reverse pair already exists, remove it. Probably due to the
             // container check (This happened to QVariant and QHash)
-            graph.removeEdge(targetTypeId, convertibleTypeId);
-            graph.addEdge(convertibleTypeId, targetTypeId);
+            graph.removeEdge(targetTypeEntryName, convertibleType);
+            graph.addEdge(convertibleType, targetTypeEntryName);
             involvedConversions.append(function);
         }
 
@@ -338,35 +298,37 @@ void OverloadData::sortNextOverloads()
             const AbstractMetaClassList &ancestors = metaClass->allTypeSystemAncestors();
             for (const AbstractMetaClass *ancestor : ancestors) {
                 QString ancestorTypeName = ancestor->typeEntry()->name();
-                if (!sortData.map.contains(ancestorTypeName))
+                if (!graph.hasNode(ancestorTypeName))
                     continue;
-                int ancestorTypeId = sortData.map[ancestorTypeName];
-                graph.removeEdge(ancestorTypeId, targetTypeId);
-                graph.addEdge(targetTypeId, ancestorTypeId);
+                graph.removeEdge(ancestorTypeName, targetTypeEntryName);
+                graph.addEdge(targetTypeEntryName, ancestorTypeName);
             }
         }
 
         // Process template instantiations
         for (const auto &instantiation : targetType.instantiations()) {
-            if (sortData.map.contains(getTypeName(instantiation))) {
-                int convertible = sortData.map[getTypeName(instantiation)];
-
-                if (!graph.containsEdge(targetTypeId, convertible)) // Avoid cyclic dependency.
-                    graph.addEdge(convertible, targetTypeId);
+            const QString convertible = getTypeName(instantiation);
+            if (graph.hasNode(convertible)) {
+                if (!graph.containsEdge(targetTypeEntryName, convertible)) // Avoid cyclic dependency.
+                    graph.addEdge(convertible, targetTypeEntryName);
 
                 if (instantiation.isPrimitive() && (signedIntegerPrimitives.contains(instantiation.name()))) {
                     for (const QString &primitive : qAsConst(nonIntegerPrimitives)) {
-                        QString convertibleTypeName = getImplicitConversionTypeName(ov->argType(), instantiation, nullptr, primitive);
-                        if (!graph.containsEdge(targetTypeId, sortData.map[convertibleTypeName])) // Avoid cyclic dependency.
-                            graph.addEdge(sortData.map[convertibleTypeName], targetTypeId);
+                        QString convertibleTypeName =
+                            getImplicitConversionTypeName(ov->argType(), instantiation, nullptr, primitive);
+                        // Avoid cyclic dependency.
+                        if (!graph.containsEdge(targetTypeEntryName, convertibleTypeName))
+                            graph.addEdge(convertibleTypeName, targetTypeEntryName);
                     }
 
                 } else {
                     const auto &funcs = m_generator->implicitConversions(instantiation);
                     for (const auto &function : funcs) {
-                        QString convertibleTypeName = getImplicitConversionTypeName(ov->argType(), instantiation, function);
-                        if (!graph.containsEdge(targetTypeId, sortData.map[convertibleTypeName])) { // Avoid cyclic dependency.
-                            graph.addEdge(sortData.map[convertibleTypeName], targetTypeId);
+                        QString convertibleTypeName =
+                            getImplicitConversionTypeName(ov->argType(), instantiation, function);
+                        // Avoid cyclic dependency.
+                        if (!graph.containsEdge(targetTypeEntryName, convertibleTypeName)) {
+                            graph.addEdge(convertibleTypeName, targetTypeEntryName);
                             involvedConversions.append(function);
                         }
                     }
@@ -376,40 +338,40 @@ void OverloadData::sortNextOverloads()
 
 
         if ((checkPySequence || checkPyObject || checkPyBuffer)
-            && !targetTypeEntryName.contains(QLatin1String("PyObject"))
-            && !targetTypeEntryName.contains(QLatin1String("PyBuffer"))
-            && !targetTypeEntryName.contains(QLatin1String("PySequence"))) {
+            && !targetTypeEntryName.contains(pyObjectT())
+            && !targetTypeEntryName.contains(pyBufferT())
+            && !targetTypeEntryName.contains(pySequenceT())) {
             if (checkPySequence) {
                 // PySequence will be checked after all more specific types, but before PyObject.
-                graph.addEdge(targetTypeId, pySeqIndex);
+                graph.addEdge(targetTypeEntryName, pySequenceT());
             } else if (checkPyBuffer) {
                 // PySequence will be checked after all more specific types, but before PyObject.
-                graph.addEdge(targetTypeId, pyBufferIndex);
+                graph.addEdge(targetTypeEntryName, pyBufferT());
             } else {
                 // Add dependency on PyObject, so its check is the last one (too generic).
-                graph.addEdge(targetTypeId, pyobjectIndex);
+                graph.addEdge(targetTypeEntryName, pyObjectT());
             }
         } else if (checkQVariant && targetTypeEntryName != qVariantT()) {
-            if (!graph.containsEdge(qvariantIndex, targetTypeId)) // Avoid cyclic dependency.
-                graph.addEdge(targetTypeId, qvariantIndex);
+            if (!graph.containsEdge(qVariantT(), targetTypeEntryName)) // Avoid cyclic dependency.
+                graph.addEdge(targetTypeEntryName, qVariantT());
         } else if (checkQString && ov->argType().isPointer()
             && targetTypeEntryName != qStringT()
             && targetTypeEntryName != qByteArrayT()
-            && (!checkPyObject || targetTypeId != pyobjectIndex)) {
-            if (!graph.containsEdge(qstringIndex, targetTypeId)) // Avoid cyclic dependency.
-                graph.addEdge(targetTypeId, qstringIndex);
+            && (!checkPyObject || targetTypeEntryName != pyObjectT())) {
+            if (!graph.containsEdge(qStringT(), targetTypeEntryName)) // Avoid cyclic dependency.
+                graph.addEdge(targetTypeEntryName, qStringT());
         }
 
         if (targetType.isEnum()) {
             // Enum values must precede primitive types.
-            for (auto id : foundPrimitiveTypeIds)
-                    graph.addEdge(targetTypeId, id);
+            for (const auto &id : foundPrimitiveTypeIds)
+                graph.addEdge(targetTypeEntryName, id);
         }
     }
 
     // QByteArray args need to be checked after QString args
-    if (sortData.map.contains(qStringT()) && sortData.map.contains(qByteArrayT()))
-        graph.addEdge(sortData.map.value(qStringT()), sortData.map.value(qByteArrayT()));
+    if (graph.hasNode(qStringT()) && graph.hasNode(qByteArrayT()))
+        graph.addEdge(qStringT(), qByteArrayT());
 
     for (OverloadData *ov : qAsConst(m_nextOverloadData)) {
         const AbstractMetaType &targetType = ov->argType();
@@ -419,16 +381,16 @@ void OverloadData::sortNextOverloads()
         QString targetTypeEntryName = getTypeName(targetType);
         // Enum values must precede types implicitly convertible from "int" or "unsigned int".
         for (const QString &implicitFromInt : qAsConst(classesWithIntegerImplicitConversion))
-            graph.addEdge(sortData.map[targetTypeEntryName], sortData.map[implicitFromInt]);
+            graph.addEdge(targetTypeEntryName, implicitFromInt);
     }
 
 
     // Special case for double(int i) (not tracked by m_generator->implicitConversions
     for (const QString &signedIntegerName : qAsConst(signedIntegerPrimitives)) {
-        if (sortData.map.contains(signedIntegerName)) {
+        if (graph.hasNode(signedIntegerName)) {
             for (const QString &nonIntegerName : qAsConst(nonIntegerPrimitives)) {
-                if (sortData.map.contains(nonIntegerName))
-                    graph.addEdge(sortData.map[nonIntegerName], sortData.map[signedIntegerName]);
+                if (graph.hasNode(nonIntegerName))
+                    graph.addEdge(nonIntegerName, signedIntegerName);
             }
         }
     }
@@ -442,21 +404,23 @@ void OverloadData::sortNextOverloads()
 
         // Dump overload graph
         QString graphName = QDir::tempPath() + QLatin1Char('/') + funcName + QLatin1String(".dot");
-        QHash<int, QString> nodeNames;
-        for (auto it = sortData.map.cbegin(), end = sortData.map.cend(); it != end; ++it)
-            nodeNames.insert(it.value(), it.key());
-        graph.dumpDot(nodeNames, graphName);
+        graph.dumpDot(graphName, [] (const QString &n) { return n; });
         AbstractMetaFunctionCList cyclic;
-        for (int c : unmappedResult.cyclic)
-            cyclic.append(sortData.reverseMap.value(c)->referenceFunction());
+        for (const auto &typeName : unmappedResult.cyclic) {
+            const auto oit = typeToOverloads.constFind(typeName);
+            if (oit != typeToOverloads.cend())
+                cyclic.append(oit.value().constFirst()->referenceFunction());
+        }
         qCWarning(lcShiboken, "%s", qPrintable(msgCyclicDependency(funcName, graphName, cyclic, involvedConversions)));
     }
 
     m_nextOverloadData.clear();
-    for (int i : unmappedResult.result) {
-        if (!sortData.reverseMap[i])
-            continue;
-        m_nextOverloadData << sortData.reverseMap[i];
+    for (const auto &typeName : unmappedResult.result) {
+        const auto oit = typeToOverloads.constFind(typeName);
+        if (oit != typeToOverloads.cend()) {
+            std::copy(oit.value().crbegin(), oit.value().crend(),
+                      std::back_inserter(m_nextOverloadData));
+        }
     }
 }