C++: Check for cycled parents

In the struct _Wrap_alloc (see test code) the rebind struct has
_Wrap_alloc as parent. However, within rebind the typedef of type
_Wrap_alloc has rebind as parent.

We will refactor that in master by introducing a "parent iterator"
class checking for cycles, so the client code looks less noisy.

Task-number: QTCREATORBUG-13703
Change-Id: I7b6cf819ea869139d2403e15ba085d8fba19763e
Reviewed-by: Cristian Adam <cristian.adam@gmail.com>
Reviewed-by: Przemyslaw Gorszkowski <pgorszkowski@gmail.com>
Reviewed-by: Eike Ziller <eike.ziller@theqtcompany.com>
Reviewed-by: Erik Verbruggen <erik.verbruggen@theqtcompany.com>

2 files changed, 86 insertions, 28 deletions

diff --git a/src/libs/cplusplus/LookupContext.cpp b/src/libs/cplusplus/LookupContext.cpp
index fdbbf74444..7dd5bcf43c 100644
--- a/src/libs/cplusplus/LookupContext.cpp
+++ b/src/libs/cplusplus/LookupContext.cpp
@@ -631,10 +631,15 @@ QList<LookupItem> ClassOrNamespace::lookup_helper(const Name *name, bool searchI
                 // a qualified name. For instance, a nested class which is forward declared
                 // in the class but defined outside it - we should capture both.
                 Symbol *match = 0;
+                QSet<ClassOrNamespace *> processed;
                 for (ClassOrNamespace *parentBinding = binding->parent();
                         parentBinding && !match;
-                        parentBinding = parentBinding->parent())
+                        parentBinding = parentBinding->parent()) {
+                    if (processed.contains(parentBinding))
+                        break;
+                    processed.insert(parentBinding);
                     match = parentBinding->lookupInScope(fullName);
+                }
 
                 if (match) {
                     LookupItem item;
@@ -648,8 +653,12 @@ QList<LookupItem> ClassOrNamespace::lookup_helper(const Name *name, bool searchI
         }
 
         QSet<ClassOrNamespace *> processed;
+        QSet<ClassOrNamespace *> processedOwnParents;
         ClassOrNamespace *binding = this;
         do {
+            if (processedOwnParents.contains(binding))
+                break;
+            processedOwnParents.insert(binding);
             lookup_helper(name, binding, &result, &processed, /*templateId = */ 0);
             binding = binding->_parent;
         } while (searchInEnclosingScope && binding);
diff --git a/tests/auto/cplusplus/checksymbols/tst_checksymbols.cpp b/tests/auto/cplusplus/checksymbols/tst_checksymbols.cpp
index 3b1e2024d8..7125d459b9 100644
--- a/tests/auto/cplusplus/checksymbols/tst_checksymbols.cpp
+++ b/tests/auto/cplusplus/checksymbols/tst_checksymbols.cpp
@@ -193,6 +193,7 @@ private slots:
     void test_checksymbols_macroUses();
     void test_checksymbols_macroUses_data();
 
+    void test_checksymbols_infiniteLoop_data();
     void test_checksymbols_infiniteLoop();
 };
 
@@ -1756,36 +1757,12 @@ void tst_CheckSymbols::test_checksymbols_macroUses_data()
 
 void tst_CheckSymbols::test_checksymbols_infiniteLoop()
 {
-    const QByteArray source1 =
-        "#include \"file2.h\"\n"
-        "\n"
-        "template<class _Elem, class _Traits>\n"
-        "class basic_ios {\n"
-        "        typedef basic_ostream<_Elem, _Traits> _Myos;\n"
-        "};\n"
-        "\n"
-        "template<class _Elem, class _Traits>\n"
-        "class basic_ostream {\n"
-        "        typedef basic_ostream<_Elem, _Traits> _Myt;\n"
-        "        typedef ostreambuf_iterator<_Elem, _Traits> _Iter;\n"
-        "};\n"
-        ;
+    QFETCH(QByteArray, source1);
+    QFETCH(QByteArray, source2);
+
     const QString filePath1 = QDir::tempPath() + QLatin1String("/file1.h");
     CppTools::Tests::TestCase::writeFile(filePath1, source1);
 
-    const QByteArray source2 =
-        "template<class _Elem, class _Traits>\n"
-        "class basic_streambuf {\n"
-        "        typedef basic_streambuf<_Elem, _Traits> _Myt;\n"
-        "};\n"
-        "\n"
-        "template<class _Elem, class _Traits>\n"
-        "class ostreambuf_iterator {\n"
-        "    typedef _Traits traits_type;\n"
-        "        typedef basic_streambuf<_Elem, _Traits> streambuf_type;\n"
-        "        typedef basic_ostream<_Elem, _Traits> ostream_type;\n"
-        "};\n"
-        ;
     const QString filePath2 = QDir::tempPath() + QLatin1String("/file2.h");
     CppTools::Tests::TestCase::writeFile(filePath2, source2);
 
@@ -1798,5 +1775,77 @@ void tst_CheckSymbols::test_checksymbols_infiniteLoop()
     TestCase::runCheckSymbols(document1, snapshot);
 }
 
+void tst_CheckSymbols::test_checksymbols_infiniteLoop_data()
+{
+    QTest::addColumn<QByteArray>("source1");
+    QTest::addColumn<QByteArray>("source2");
+
+    QTest::newRow("1")
+        <<
+         _("#include \"file2.h\"\n"
+           "\n"
+           "template<class _Elem, class _Traits>\n"
+           "class basic_ios {\n"
+           "        typedef basic_ostream<_Elem, _Traits> _Myos;\n"
+           "};\n"
+           "\n"
+           "template<class _Elem, class _Traits>\n"
+           "class basic_ostream {\n"
+           "        typedef basic_ostream<_Elem, _Traits> _Myt;\n"
+           "        typedef ostreambuf_iterator<_Elem, _Traits> _Iter;\n"
+           "};\n")
+        <<
+         _("template<class _Elem, class _Traits>\n"
+           "class basic_streambuf {\n"
+           "        typedef basic_streambuf<_Elem, _Traits> _Myt;\n"
+           "};\n"
+           "\n"
+           "template<class _Elem, class _Traits>\n"
+           "class ostreambuf_iterator {\n"
+           "    typedef _Traits traits_type;\n"
+           "        typedef basic_streambuf<_Elem, _Traits> streambuf_type;\n"
+           "        typedef basic_ostream<_Elem, _Traits> ostream_type;\n"
+           "};\n")
+           ;
+
+    QTest::newRow("2")
+        <<
+         _("#include \"file2.h\"\n"
+           "\n"
+           "template<class _Ty >\n"
+           "struct _List_base_types\n"
+           "{\n"
+           "        typedef typename _Wrap_alloc<_Alloc>::template rebind<_Ty>::other _Alty;\n"
+           "        typedef typename _Alty::template rebind<_Node>::other _Alnod_type;\n"
+           "};\n"
+           "\n"
+           "template<class _Alloc_types>\n"
+           "struct _List_alloc \n"
+           "{\n"
+           "        const _Alloc_types::_Alnod_type& _Getal() const {}\n"
+           "};\n"
+           "\n"
+           "template<class _Ty, class _Alloc>\n"
+           "struct _List_buy : public _List_alloc< _List_base_types<_Ty> >\n"
+           "{\n"
+           "        void foo()\n"
+           "        {\n"
+           "                this->_Getal().construct(1, 2);\n"
+           "                this->_Getal().deallocate(0, 1);\n"
+           "        }\n"
+           "};\n")
+        <<
+         _("template<class _Alloc>\n"
+           "struct _Wrap_alloc : public _Alloc\n"
+           "{\n"
+           "    typedef _Alloc _Mybase;\n"
+           "    template<class _Other> struct rebind { typedef _Wrap_alloc<_Other_alloc> other; };\n"
+           "\n"
+           "    void deallocate(pointer _Ptr, size_type _Count) {}\n"
+           "    void construct(value_type *_Ptr) {}\n"
+           "};\n")
+           ;
+}
+
 QTEST_APPLESS_MAIN(tst_CheckSymbols)
 #include "tst_checksymbols.moc"