shiboken2: Improve error messages about cyclic dependencies

Return a struct instead of a plain list from
Graph::topologicalSort() which contains the offending indexes and
output the elements in case of failure.

Task-number: PYSIDE-1202
Change-Id: Ib7f70c78be0e84272f31d802677c7fc333aa32f4
Reviewed-by: Christian Tismer <tismer@stackless.com>

7 files changed, 55 insertions, 25 deletions

diff --git a/sources/shiboken2/ApiExtractor/abstractmetabuilder.cpp b/sources/shiboken2/ApiExtractor/abstractmetabuilder.cpp
index 1f126ba57..b176191c1 100644
--- a/sources/shiboken2/ApiExtractor/abstractmetabuilder.cpp
+++ b/sources/shiboken2/ApiExtractor/abstractmetabuilder.cpp
@@ -3099,7 +3099,7 @@ AbstractMetaClassList AbstractMetaBuilderPrivate::classesTopologicalSorted(const
 
     AbstractMetaClassList result;
     const auto unmappedResult = graph.topologicalSort();
-    if (unmappedResult.isEmpty() && graph.nodeCount()) {
+    if (!unmappedResult.isValid() && graph.nodeCount()) {
         QTemporaryFile tempFile(QDir::tempPath() + QLatin1String("/cyclic_depXXXXXX.dot"));
         tempFile.setAutoRemove(false);
         tempFile.open();
@@ -3107,11 +3107,16 @@ AbstractMetaClassList AbstractMetaBuilderPrivate::classesTopologicalSorted(const
         for (auto it = map.cbegin(), end = map.cend(); it != end; ++it)
             hash.insert(it.value(), it.key()->qualifiedCppName());
         graph.dumpDot(hash, tempFile.fileName());
-        qCWarning(lcShiboken).noquote().nospace()
-            << "Cyclic dependency found! Graph can be found at "
-            << QDir::toNativeSeparators(tempFile.fileName());
+
+        QString message;
+        QTextStream str(&message);
+        str << "Cyclic dependency of classes found:";
+        for (int c : unmappedResult.cyclic)
+            str << ' ' <<  reverseMap.value(c)->name();
+        str << ". Graph can be found at \"" << QDir::toNativeSeparators(tempFile.fileName()) << '"';
+        qCWarning(lcShiboken, "%s", qPrintable(message));
     } else {
-        for (int i : qAsConst(unmappedResult)) {
+        for (int i : qAsConst(unmappedResult.result)) {
             Q_ASSERT(reverseMap.contains(i));
             result << reverseMap[i];
         }
diff --git a/sources/shiboken2/ApiExtractor/abstractmetalang_typedefs.h b/sources/shiboken2/ApiExtractor/abstractmetalang_typedefs.h
index 418b9ba09..580af8170 100644
--- a/sources/shiboken2/ApiExtractor/abstractmetalang_typedefs.h
+++ b/sources/shiboken2/ApiExtractor/abstractmetalang_typedefs.h
@@ -46,6 +46,7 @@ using AbstractMetaEnumList = QVector<AbstractMetaEnum *>;
 using AbstractMetaEnumValueList = QVector<AbstractMetaEnumValue *>;
 using AbstractMetaFieldList = QVector<AbstractMetaField *>;
 using AbstractMetaFunctionList = QVector<AbstractMetaFunction *>;
+using AbstractMetaFunctionCList = QVector<const AbstractMetaFunction *>;
 using AbstractMetaTypeList = QVector<AbstractMetaType>;
 
 #endif // ABSTRACTMETALANG_TYPEDEFS_H
diff --git a/sources/shiboken2/ApiExtractor/graph.cpp b/sources/shiboken2/ApiExtractor/graph.cpp
index 53e20ebba..ccc9119b8 100644
--- a/sources/shiboken2/ApiExtractor/graph.cpp
+++ b/sources/shiboken2/ApiExtractor/graph.cpp
@@ -74,23 +74,28 @@ int Graph::nodeCount() const
     return m_d->edges.size();
 }
 
-Graph::Indexes Graph::topologicalSort() const
+Graph::SortResult Graph::topologicalSort() const
 {
     const int nodeCount = Graph::nodeCount();
-    Indexes result;
-    result.reserve(nodeCount);
+    SortResult result;
+    result.result.reserve(nodeCount);
 
     QVector<GraphPrivate::Color> colors(nodeCount, GraphPrivate::WHITE);
 
     for (int i = 0; i < nodeCount; ++i) {
         if (colors[i] == GraphPrivate::WHITE)
-            m_d->dfsVisit(i, result, colors);
+            m_d->dfsVisit(i, result.result, colors);
     }
 
-    if (result.size() == nodeCount)
-        std::reverse(result.begin(), result.end());
-    else
-        result.clear(); // Not a DAG!
+    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;
 }
 
diff --git a/sources/shiboken2/ApiExtractor/graph.h b/sources/shiboken2/ApiExtractor/graph.h
index 5dc8e21ea..ba28986d1 100644
--- a/sources/shiboken2/ApiExtractor/graph.h
+++ b/sources/shiboken2/ApiExtractor/graph.h
@@ -41,6 +41,13 @@ public:
 
     using Indexes = QVector<int>;
 
+    struct SortResult
+    {
+        bool isValid() const { return !result.isEmpty() && cyclic.isEmpty(); }
+        Indexes result;
+        Indexes cyclic;
+    };
+
     /// Create a new graph with \p numNodes nodes.
     Graph(int numNodes);
     ~Graph();
@@ -67,7 +74,7 @@ public:
     *   \return A collection with all nodes topologically sorted or an empty collection if a cyclic
     *   dependency was found.
     */
-    Indexes topologicalSort() const;
+    SortResult topologicalSort() const;
 private:
 
     struct GraphPrivate;
diff --git a/sources/shiboken2/ApiExtractor/tests/testtoposort.cpp b/sources/shiboken2/ApiExtractor/tests/testtoposort.cpp
index c59fa8c3d..25eb99e50 100644
--- a/sources/shiboken2/ApiExtractor/tests/testtoposort.cpp
+++ b/sources/shiboken2/ApiExtractor/tests/testtoposort.cpp
@@ -38,8 +38,10 @@ void TestTopoSort::testTopoSort()
         g.addEdge(1, 2);
         g.addEdge(0, 1);
         const auto result = g.topologicalSort();
-        QCOMPARE(result.size(), 3);
-        auto it = result.begin();
+        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);
@@ -47,21 +49,25 @@ void TestTopoSort::testTopoSort()
     {
         Graph g(2);
         const auto result = g.topologicalSort();
-        QCOMPARE(result.size(), 2);
-        auto it = result.begin();
+        QVERIFY(result.isValid());
+        QVERIFY(result.cyclic.isEmpty());
+        QCOMPARE(result.result.size(), 2);
+        auto it = result.result.begin();
         QCOMPARE(*it, 1);
         QCOMPARE(*(++it), 0);
     }
 }
 
-void TestTopoSort::testCiclicGraph()
+void TestTopoSort::testCyclicGraph()
 {
     Graph g(3);
     g.addEdge(0, 1);
     g.addEdge(1, 2);
     g.addEdge(2, 0);
     const auto result = g.topologicalSort();
-    QVERIFY(result.isEmpty());
+    QVERIFY(!result.isValid());
+    QVERIFY(result.result.isEmpty());
+    QVERIFY(!result.cyclic.isEmpty());
 }
 
 QTEST_APPLESS_MAIN(TestTopoSort)
diff --git a/sources/shiboken2/ApiExtractor/tests/testtoposort.h b/sources/shiboken2/ApiExtractor/tests/testtoposort.h
index 0770a8d0e..7caafc87f 100644
--- a/sources/shiboken2/ApiExtractor/tests/testtoposort.h
+++ b/sources/shiboken2/ApiExtractor/tests/testtoposort.h
@@ -36,7 +36,7 @@ class TestTopoSort : public QObject
 Q_OBJECT
 private slots:
     void testTopoSort();
-    void testCiclicGraph();
+    void testCyclicGraph();
 };
 
 #endif
diff --git a/sources/shiboken2/generator/shiboken2/overloaddata.cpp b/sources/shiboken2/generator/shiboken2/overloaddata.cpp
index 50e82b1e6..dd0cb39eb 100644
--- a/sources/shiboken2/generator/shiboken2/overloaddata.cpp
+++ b/sources/shiboken2/generator/shiboken2/overloaddata.cpp
@@ -155,13 +155,16 @@ static QString getImplicitConversionTypeName(const AbstractMetaType &containerTy
 
 // overloaddata.cpp
 static QString msgCyclicDependency(const QString &funcName, const QString &graphName,
+                                   const AbstractMetaFunctionCList &cyclic,
                                    const OverloadData::MetaFunctionList &involvedConversions)
 {
     QString result;
     QTextStream str(&result);
     str << "Cyclic dependency found on overloaddata for \"" << funcName
          << "\" method! The graph boy saved the graph at \"" << QDir::toNativeSeparators(graphName)
-         << "\".";
+         << "\". Cyclic functions:";
+    for (auto c : cyclic)
+        str << ' ' << c->signature();
     if (const int count = involvedConversions.size()) {
         str << " Implicit conversions (" << count << "): ";
         for (int i = 0; i < count; ++i) {
@@ -431,7 +434,7 @@ void OverloadData::sortNextOverloads()
 
     // sort the overloads topologically based on the dependency graph.
     const auto unmappedResult = graph.topologicalSort();
-    if (unmappedResult.isEmpty()) {
+    if (!unmappedResult.isValid()) {
         QString funcName = referenceFunction()->name();
         if (referenceFunction()->ownerClass())
             funcName.prepend(referenceFunction()->ownerClass()->name() + QLatin1Char('.'));
@@ -442,11 +445,14 @@ void OverloadData::sortNextOverloads()
         for (auto it = sortData.map.cbegin(), end = sortData.map.cend(); it != end; ++it)
             nodeNames.insert(it.value(), it.key());
         graph.dumpDot(nodeNames, graphName);
-        qCWarning(lcShiboken).noquote() << qPrintable(msgCyclicDependency(funcName, graphName, involvedConversions));
+        AbstractMetaFunctionCList cyclic;
+        for (int c : unmappedResult.cyclic)
+            cyclic.append(sortData.reverseMap.value(c)->referenceFunction());
+        qCWarning(lcShiboken, "%s", qPrintable(msgCyclicDependency(funcName, graphName, cyclic, involvedConversions)));
     }
 
     m_nextOverloadData.clear();
-    for (int i : unmappedResult) {
+    for (int i : unmappedResult.result) {
         if (!sortData.reverseMap[i])
             continue;
         m_nextOverloadData << sortData.reverseMap[i];