diff --git a/libcxxabi/src/demangle/ItaniumDemangle.h b/libcxxabi/src/demangle/ItaniumDemangle.h --- a/libcxxabi/src/demangle/ItaniumDemangle.h +++ b/libcxxabi/src/demangle/ItaniumDemangle.h @@ -651,8 +651,15 @@ // Dig through any refs to refs, collapsing the ReferenceTypes as we go. The // rule here is rvalue ref to rvalue ref collapses to a rvalue ref, and any // other combination collapses to a lvalue ref. + // + // A combination of a TemplateForwardReference and a back-ref Substitution + // from an ill-formed string may have created a cycle; use cycle detection to + // avoid looping forever. std::pair collapse(OutputStream &S) const { auto SoFar = std::make_pair(RK, Pointee); + // Track the chain of nodes for the Floyd's 'tortoise and hare' + // cycle-detection algorithm, since getSyntaxNode(S) is impure + PODSmallVector Prev; for (;;) { const Node *SN = SoFar.second->getSyntaxNode(S); if (SN->getKind() != KReferenceType) @@ -660,6 +667,14 @@ auto *RT = static_cast(SN); SoFar.second = RT->Pointee; SoFar.first = std::min(SoFar.first, RT->RK); + + // The middle of Prev is the 'slow' pointer moving at half speed + Prev.push_back(SoFar.second); + if (Prev.size() > 1 && SoFar.second == Prev[(Prev.size() - 1) / 2]) { + // Cycle detected + SoFar.second = nullptr; + break; + } } return SoFar; } @@ -680,6 +695,8 @@ return; SwapAndRestore SavePrinting(Printing, true); std::pair Collapsed = collapse(s); + if (!Collapsed.second) + return; Collapsed.second->printLeft(s); if (Collapsed.second->hasArray(s)) s += " "; @@ -693,6 +710,8 @@ return; SwapAndRestore SavePrinting(Printing, true); std::pair Collapsed = collapse(s); + if (!Collapsed.second) + return; if (Collapsed.second->hasArray(s) || Collapsed.second->hasFunction(s)) s += ")"; Collapsed.second->printRight(s); diff --git a/libcxxabi/test/test_demangle.pass.cpp b/libcxxabi/test/test_demangle.pass.cpp --- a/libcxxabi/test/test_demangle.pass.cpp +++ b/libcxxabi/test/test_demangle.pass.cpp @@ -9,6 +9,11 @@ // The demangler does not pass all these tests with the system dylibs on macOS. // XFAIL: use_system_cxx_lib && target={{.+}}-apple-macosx10.{{9|10|11|12|13|14|15}} +// https://llvm.org/PR51407 was not fixed in some previously-released +// demanglers, which causes them to run into the infinite loop. +// UNSUPPORTED: use_system_cxx_lib && target={{.+}}-apple-macosx10.{{9|10|11|12|13|14|15}} +// UNSUPPORTED: use_system_cxx_lib && target={{.+}}-apple-macosx11.0 + #include "support/timer.h" #include #include @@ -29844,6 +29849,9 @@ {"_ZN3xxx3yyyIvNS_1AILm0EEEZNS_2bb2cc2ddILNS_1eE1EEEvRKNS_1fERKNS_1g1hINS_1iEEERKNS_1jEfRKNS_1kEiPhEUlvE_JEEEvT1_DpT2_", "void xxx::yyy, void xxx::bb::cc::dd<(xxx::e)1>(xxx::f const&, xxx::g::h const&, xxx::j const&, float, xxx::k const&, int, unsigned char*)::'lambda'()>(void xxx::bb::cc::dd<(xxx::e)1>(xxx::f const&, xxx::g::h const&, xxx::j const&, float, xxx::k const&, int, unsigned char*)::'lambda'())"}, + // This should be invalid, but it is currently not recognized as such + // See https://llvm.org/PR51407 + {"_Zcv1BIRT_EIS1_E", "operator B<><>"}, }; const unsigned N = sizeof(cases) / sizeof(cases[0]); diff --git a/llvm/include/llvm/Demangle/ItaniumDemangle.h b/llvm/include/llvm/Demangle/ItaniumDemangle.h --- a/llvm/include/llvm/Demangle/ItaniumDemangle.h +++ b/llvm/include/llvm/Demangle/ItaniumDemangle.h @@ -651,8 +651,15 @@ // Dig through any refs to refs, collapsing the ReferenceTypes as we go. The // rule here is rvalue ref to rvalue ref collapses to a rvalue ref, and any // other combination collapses to a lvalue ref. + // + // A combination of a TemplateForwardReference and a back-ref Substitution + // from an ill-formed string may have created a cycle; use cycle detection to + // avoid looping forever. std::pair collapse(OutputStream &S) const { auto SoFar = std::make_pair(RK, Pointee); + // Track the chain of nodes for the Floyd's 'tortoise and hare' + // cycle-detection algorithm, since getSyntaxNode(S) is impure + PODSmallVector Prev; for (;;) { const Node *SN = SoFar.second->getSyntaxNode(S); if (SN->getKind() != KReferenceType) @@ -660,6 +667,14 @@ auto *RT = static_cast(SN); SoFar.second = RT->Pointee; SoFar.first = std::min(SoFar.first, RT->RK); + + // The middle of `Prev` is the 'slow' pointer moving at half speed + Prev.push_back(SoFar.second); + if (Prev.size() > 1 && SoFar.second == Prev[(Prev.size() - 1) / 2]) { + // Cycle detected + SoFar.second = nullptr; + break; + } } return SoFar; } @@ -680,6 +695,8 @@ return; SwapAndRestore SavePrinting(Printing, true); std::pair Collapsed = collapse(s); + if (!Collapsed.second) + return; Collapsed.second->printLeft(s); if (Collapsed.second->hasArray(s)) s += " "; @@ -693,6 +710,8 @@ return; SwapAndRestore SavePrinting(Printing, true); std::pair Collapsed = collapse(s); + if (!Collapsed.second) + return; if (Collapsed.second->hasArray(s) || Collapsed.second->hasFunction(s)) s += ")"; Collapsed.second->printRight(s);