CppEditor: Properly handle multiple inheritance

... in "Insert Virtual Functions" quickfix.

Fixes: QTCREATORBUG-12223
Change-Id: I7dad7c219017a8c7b10b08190e35d1899ca5dfe6
Reviewed-by: Christian Stenger <christian.stenger@qt.io>

3 files changed, 175 insertions, 52 deletions

diff --git a/src/plugins/cppeditor/cppinsertvirtualmethods.cpp b/src/plugins/cppeditor/cppinsertvirtualmethods.cpp
index 8de8e3013c..6ee831e6ab 100644
--- a/src/plugins/cppeditor/cppinsertvirtualmethods.cpp
+++ b/src/plugins/cppeditor/cppinsertvirtualmethods.cpp
@@ -584,21 +584,23 @@ public:
                     if (!name || name->asDestructorNameId())
                         continue;
 
-                    const Function *firstVirtual = nullptr;
+                    QList<const Function * > firstVirtuals;
                     const bool isVirtual = FunctionUtils::isVirtualFunction(
-                                func, interface.context(), &firstVirtual);
+                                func, interface.context(), &firstVirtuals);
                     if (!isVirtual)
                         continue;
 
                     if (func->isFinal()) {
-                        if (FunctionItem *first = virtualFunctions[firstVirtual]) {
-                            FunctionItem *next = nullptr;
-                            for (FunctionItem *removed = first; next != first; removed = next) {
-                                next = removed->nextOverride;
-                                m_factory->classFunctionModel->removeFunction(removed);
-                                delete removed;
-                            };
-                            virtualFunctions.remove(firstVirtual);
+                        for (const Function *firstVirtual : qAsConst(firstVirtuals)) {
+                            if (FunctionItem *first = virtualFunctions[firstVirtual]) {
+                                FunctionItem *next = nullptr;
+                                for (FunctionItem *removed = first; next != first; removed = next) {
+                                    next = removed->nextOverride;
+                                    m_factory->classFunctionModel->removeFunction(removed);
+                                    delete removed;
+                                };
+                                virtualFunctions.remove(firstVirtual);
+                            }
                         }
                         continue;
                     }
@@ -606,15 +608,21 @@ public:
                     //   - virtual const QMetaObject *metaObject() const;
                     //   - virtual void *qt_metacast(const char *);
                     //   - virtual int qt_metacall(QMetaObject::Call, int, void **);
-                    if (printer.prettyName(firstVirtual->enclosingClass()->name())
-                            == QLatin1String("QObject")) {
-                        const QString funcName = printer.prettyName(func->name());
-                        if (funcName == QLatin1String("metaObject")
-                                || funcName == QLatin1String("qt_metacast")
-                                || funcName == QLatin1String("qt_metacall")) {
-                            continue;
+                    bool skip = false;
+                    for (const Function *firstVirtual : qAsConst(firstVirtuals)) {
+                        if (printer.prettyName(firstVirtual->enclosingClass()->name())
+                                == QLatin1String("QObject")) {
+                            const QString funcName = printer.prettyName(func->name());
+                            if (funcName == QLatin1String("metaObject")
+                                    || funcName == QLatin1String("qt_metacast")
+                                    || funcName == QLatin1String("qt_metacall")) {
+                                skip = true;
+                                break;
+                            }
                         }
                     }
+                    if (skip)
+                        continue;
 
                     // Do not implement existing functions inside target class
                     bool funcExistsInClass = false;
@@ -634,7 +642,7 @@ public:
                     }
 
                     // Construct function item
-                    const bool isReimplemented = (func != firstVirtual);
+                    const bool isReimplemented = !firstVirtuals.contains(func);
                     const bool isPureVirtual = func->isPureVirtual();
                     QString itemName = printer.prettyType(func->type(), func->name());
                     if (isPureVirtual)
@@ -648,16 +656,24 @@ public:
                         factory->setHasReimplementedFunctions(true);
                         funcItem->reimplemented = true;
                         funcItem->alreadyFound = funcExistsInClass;
-                        if (FunctionItem *first = virtualFunctions[firstVirtual]) {
-                            if (!first->alreadyFound) {
-                                while (first->checked != isPureVirtual) {
-                                    first->checked = isPureVirtual;
-                                    first = first->nextOverride;
+                        for (const Function *firstVirtual : qAsConst(firstVirtuals)) {
+                            if (FunctionItem *first = virtualFunctions[firstVirtual]) {
+                                if (!first->alreadyFound) {
+                                    while (first->checked != isPureVirtual) {
+                                        first->checked = isPureVirtual;
+                                        first = first->nextOverride;
+                                    }
                                 }
+                                funcItem->checked = first->checked;
+
+                                FunctionItem *prev = funcItem;
+                                for (FunctionItem *next = funcItem->nextOverride;
+                                     next && next != funcItem; next = next->nextOverride) {
+                                    prev = next;
+                                }
+                                prev->nextOverride = first->nextOverride;
+                                first->nextOverride = funcItem;
                             }
-                            funcItem->checked = first->checked;
-                            funcItem->nextOverride = first->nextOverride;
-                            first->nextOverride = funcItem;
                         }
                     } else {
                         if (!funcExistsInClass) {
@@ -758,6 +774,7 @@ public:
             targetCoN = targetContext.globalNamespace();
         UseMinimalNames useMinimalNames(targetCoN);
         Control *control = context().bindings()->control().data();
+        QList<const Function *> insertedFunctions;
         foreach (ClassItem *classItem, m_factory->classFunctionModel->classes) {
             if (classItem->checkState() == Qt::Unchecked)
                 continue;
@@ -769,6 +786,14 @@ public:
                 if (funcItem->reimplemented || funcItem->alreadyFound || !funcItem->checked)
                     continue;
 
+                const auto cmp = [funcItem](const Function *f) {
+                    return f->name()->match(funcItem->function->name())
+                                    && f->type().match(funcItem->function->type());
+                };
+                if (Utils::contains(insertedFunctions, cmp))
+                    continue;
+                insertedFunctions.append(funcItem->function);
+
                 if (first) {
                     // Add comment
                     const QString comment = QLatin1String("\n// ") +
@@ -824,10 +849,13 @@ public:
         }
 
         // Write header file
-        headerFile->setChangeSet(headerChangeSet);
-        headerFile->appendIndentRange(Utils::ChangeSet::Range(m_insertPosDecl, m_insertPosDecl + 1));
-        headerFile->setOpenEditor(true, m_insertPosDecl);
-        headerFile->apply();
+        if (!headerChangeSet.isEmpty()) {
+            headerFile->setChangeSet(headerChangeSet);
+            headerFile->appendIndentRange(Utils::ChangeSet::Range(m_insertPosDecl,
+                                                                  m_insertPosDecl + 1));
+            headerFile->setOpenEditor(true, m_insertPosDecl);
+            headerFile->apply();
+        }
 
         // Insert in implementation file
         if (m_factory->settings()->implementationMode
@@ -877,9 +905,12 @@ public:
                 implementationChangeSet.insert(insertPos,  QLatin1String("\n\n") + defText);
             }
 
-            implementationFile->setChangeSet(implementationChangeSet);
-            implementationFile->appendIndentRange(Utils::ChangeSet::Range(insertPos, insertPos + 1));
-            implementationFile->apply();
+            if (!implementationChangeSet.isEmpty()) {
+                implementationFile->setChangeSet(implementationChangeSet);
+                implementationFile->appendIndentRange(Utils::ChangeSet::Range(insertPos,
+                                                                              insertPos + 1));
+                implementationFile->apply();
+            }
         }
     }
 
@@ -1761,6 +1792,56 @@ void CppEditorPlugin::test_quickfix_InsertVirtualMethods_data()
         "    virtual int d();\n"
         "};\n"
     );
+
+    // Check: Insert multiply-inherited virtual function only once.
+    QTest::newRow("multiple_inheritance_insert")
+        << InsertVirtualMethodsDialog::ModeOnlyDeclarations << false << true << _(
+        "struct Base1 {\n"
+        "    virtual void virt() = 0;\n"
+        "};\n\n"
+        "struct Base2 {\n"
+        "    virtual void virt() = 0;\n"
+        "};\n\n"
+        "struct @Derived : Base1, Base2 {\n"
+        "};\n") << _(
+        "struct Base1 {\n"
+        "    virtual void virt() = 0;\n"
+        "};\n\n"
+        "struct Base2 {\n"
+        "    virtual void virt() = 0;\n"
+        "};\n\n"
+        "struct Derived : Base1, Base2 {\n\n"
+        "    // Base2 interface\n"
+        "public:\n"
+        "    void virt() override;\n"
+        "};\n");
+
+    // Check: Do not insert multiply-inherited virtual function that has been re-implemented
+    //        along the way.
+    QTest::newRow("multiple_inheritance_no_insert")
+        << InsertVirtualMethodsDialog::ModeOnlyDeclarations << false << true << _(
+        "struct Base1 {\n"
+        "    virtual void virt() = 0;\n"
+        "};\n\n"
+        "struct Base2 {\n"
+        "    virtual void virt() = 0;\n"
+        "};\n\n"
+        "struct Derived1 : Base1, Base2 {\n"
+        "    void virt() override;\n"
+        "};\n\n"
+        "struct @Derived2 : Derived1\n"
+        "};\n") << _(
+        "struct Base1 {\n"
+        "    virtual void virt() = 0;\n"
+        "};\n\n"
+        "struct Base2 {\n"
+        "    virtual void virt() = 0;\n"
+        "};\n\n"
+        "struct Derived1 : Base1, Base2 {\n"
+        "    void virt() override;\n"
+        "};\n\n"
+        "struct Derived2 : Derived1\n"
+        "};\n");
 }
 
 void CppEditorPlugin::test_quickfix_InsertVirtualMethods()
diff --git a/src/plugins/cpptools/functionutils.cpp b/src/plugins/cpptools/functionutils.cpp
index fa82fece8a..b19fe43958 100644
--- a/src/plugins/cpptools/functionutils.cpp
+++ b/src/plugins/cpptools/functionutils.cpp
@@ -33,6 +33,11 @@
 #include <utils/qtcassert.h>
 
 #include <QList>
+#include <QPair>
+
+#include <limits>
+
+#include <cplusplus/TypePrettyPrinter.h>
 
 using namespace CPlusPlus;
 using namespace CppTools;
@@ -42,12 +47,12 @@ enum VirtualType { Virtual, PureVirtual };
 static bool isVirtualFunction_helper(const Function *function,
                                      const LookupContext &context,
                                      VirtualType virtualType,
-                                     const Function **firstVirtual)
+                                     QList<const Function *> *firstVirtuals)
 {
     enum { Unknown, False, True } res = Unknown;
 
-    if (firstVirtual)
-        *firstVirtual = nullptr;
+    if (firstVirtuals)
+        firstVirtuals->clear();
 
     if (!function)
         return false;
@@ -55,14 +60,51 @@ static bool isVirtualFunction_helper(const Function *function,
     if (virtualType == PureVirtual)
         res = function->isPureVirtual() ? True : False;
 
+    const Class * const klass = function->enclosingScope()
+            ? function->enclosingScope()->asClass() : nullptr;
+    if (!klass)
+        return false;
+
+    int hierarchyDepthOfFirstVirtuals = -1;
+    const auto updateFirstVirtualsList
+            = [&hierarchyDepthOfFirstVirtuals, &context, firstVirtuals, klass](Function *candidate) {
+        const Class * const candidateClass = candidate->enclosingScope()
+                ? candidate->enclosingScope()->asClass() : nullptr;
+        if (!candidateClass)
+            return;
+        QList<QPair<const Class *, int>> classes{{klass, 0}};
+        while (!classes.isEmpty()) {
+            const auto c = classes.takeFirst();
+            if (c.first == candidateClass) {
+                QTC_ASSERT(c.second != 0, return);
+                if (c.second >= hierarchyDepthOfFirstVirtuals) {
+                    if (c.second > hierarchyDepthOfFirstVirtuals) {
+                        firstVirtuals->clear();
+                        hierarchyDepthOfFirstVirtuals = c.second;
+                    }
+                    firstVirtuals->append(candidate);
+                }
+                return;
+            }
+            for (int i = 0; i < c.first->baseClassCount(); ++i) {
+                const ClassOrNamespace * const base = context.lookupType(
+                            c.first->baseClassAt(i)->name(), c.first->enclosingScope());
+                if (base && base->rootClass())
+                    classes.append({base->rootClass(), c.second + 1});
+            }
+        }
+    };
+
     if (function->isVirtual()) {
-        if (firstVirtual)
-            *firstVirtual = function;
+        if (firstVirtuals) {
+            hierarchyDepthOfFirstVirtuals = 0;
+            firstVirtuals->append(function);
+        }
         if (res == Unknown)
             res = True;
     }
 
-    if (!firstVirtual && res != Unknown)
+    if (!firstVirtuals && res != Unknown)
         return res == True;
 
     QList<LookupItem> results = context.lookup(function->name(), function->enclosingScope());
@@ -80,11 +122,11 @@ static bool isVirtualFunction_helper(const Function *function,
                     if (functionType->isFinal())
                         return res == True;
                     if (functionType->isVirtual()) {
-                        if (!firstVirtual)
+                        if (!firstVirtuals)
                             return true;
                         if (res == Unknown)
                             res = True;
-                        *firstVirtual = functionType;
+                        updateFirstVirtualsList(functionType);
                     }
                 }
             }
@@ -96,16 +138,16 @@ static bool isVirtualFunction_helper(const Function *function,
 
 bool FunctionUtils::isVirtualFunction(const Function *function,
                                       const LookupContext &context,
-                                      const Function **firstVirtual)
+                                      QList<const Function *> *firstVirtuals)
 {
-    return isVirtualFunction_helper(function, context, Virtual, firstVirtual);
+    return isVirtualFunction_helper(function, context, Virtual, firstVirtuals);
 }
 
 bool FunctionUtils::isPureVirtualFunction(const Function *function,
                                           const LookupContext &context,
-                                          const Function **firstVirtual)
+                                          QList<const Function *> *firstVirtuals)
 {
-    return isVirtualFunction_helper(function, context, PureVirtual, firstVirtual);
+    return isVirtualFunction_helper(function, context, PureVirtual, firstVirtuals);
 }
 
 QList<Function *> FunctionUtils::overrides(Function *function, Class *functionsClass,
@@ -191,7 +233,7 @@ void CppToolsPlugin::test_functionutils_virtualFunctions()
     QCOMPARE(document->diagnosticMessages().size(), 0);
     QVERIFY(document->translationUnit()->ast());
     QList<const Function *> allFunctions;
-    const Function *firstVirtual = nullptr;
+    QList<const Function *> firstVirtuals;
 
     // Iterate through Function symbols
     Snapshot snapshot;
@@ -206,9 +248,9 @@ void CppToolsPlugin::test_functionutils_virtualFunctions()
             Virtuality virtuality = virtualityList.takeFirst();
             QTC_ASSERT(!firstVirtualList.isEmpty(), return);
             int firstVirtualIndex = firstVirtualList.takeFirst();
-            bool isVirtual = FunctionUtils::isVirtualFunction(function, context, &firstVirtual);
+            bool isVirtual = FunctionUtils::isVirtualFunction(function, context, &firstVirtuals);
             bool isPureVirtual = FunctionUtils::isPureVirtualFunction(function, context,
-                                                                      &firstVirtual);
+                                                                      &firstVirtuals);
 
             // Test for regressions introduced by firstVirtual
             QCOMPARE(FunctionUtils::isVirtualFunction(function, context), isVirtual);
@@ -225,9 +267,9 @@ void CppToolsPlugin::test_functionutils_virtualFunctions()
                 QCOMPARE(virtuality, NotVirtual);
             }
             if (firstVirtualIndex == -1)
-                QVERIFY(!firstVirtual);
+                QVERIFY(firstVirtuals.isEmpty());
             else
-                QCOMPARE(firstVirtual, allFunctions.at(firstVirtualIndex));
+                QCOMPARE(firstVirtuals, {allFunctions.at(firstVirtualIndex)});
         }
     }
     QVERIFY(virtualityList.isEmpty());
diff --git a/src/plugins/cpptools/functionutils.h b/src/plugins/cpptools/functionutils.h
index d238fd6b85..56c13f0da6 100644
--- a/src/plugins/cpptools/functionutils.h
+++ b/src/plugins/cpptools/functionutils.h
@@ -44,11 +44,11 @@ class CPPTOOLS_EXPORT FunctionUtils
 public:
     static bool isVirtualFunction(const CPlusPlus::Function *function,
                                   const CPlusPlus::LookupContext &context,
-                                  const CPlusPlus::Function **firstVirtual = nullptr);
+                                  QList<const CPlusPlus::Function *> *firstVirtuals = nullptr);
 
     static bool isPureVirtualFunction(const CPlusPlus::Function *function,
                                       const CPlusPlus::LookupContext &context,
-                                      const CPlusPlus::Function **firstVirtual = nullptr);
+                                      QList<const CPlusPlus::Function *> *firstVirtuals = nullptr);
 
     static QList<CPlusPlus::Function *> overrides(CPlusPlus::Function *function,
                                                   CPlusPlus::Class *functionsClass,