[demangler][NFC] Refactor some parsing

[urnathan]

Summary

There's some unnecessary code duplication in the demangler's parser. This refactors that, deploying boolean variable technology to avoid the duplication. These also happen to help adding module demangling (with an updated mangling scheme that I am working on).

1a) The grammar requires some lookahead concerning <template-args>. We may discover an <unscoped-name> is actually <unscoped-template-name> <template-args>. (When <unscoped-name> was a substitution, there must be a following <template-args>.) Refactor parseName to only have one code path looking for the 'I' indicating <template-args>.

1b) While there I altered the control flow to hold the result in a variable, rather than tail call. Made it easier to debug (and of course an optimizer will DTRT here anyway).

2a) An <unscoped-name> can have an St or StL prefix. No need for completely separate code paths handling the following unqualified-name though.

2b) Also no need to look for both 'St' and 'StL' separately. Look for 'St' and then conditionally swallow an 'L'.

3. We get a similar issue as #1a when parsing a typeName. Here I just change the control flow slightly to bring the 'break' out to the end of the 'S' block and embed the early return inside an if. That's more in keeping with the code style.

4. Although NFC, there's a new testcase as that's not covered by the existing demangler tests and is significant in the #1a case above.

[aaron.ballman]

libcxxabi/src/demangle/ItaniumDemangle.h

2595–2598

Personally, I think the early returns are a bit easier to follow along with. WDYT?

2628

4076–4078

Was this change NFC, or did we drop a needed check for \0 because there is nothing to lookahead to?

[urnathan]

libcxxabi/src/demangle/ItaniumDemangle.h

2595–2598

I can ramble on a bit here. TL;DR: not particularly wedded to this particular change. This variant has a helpful blank line after the 'if () return ...' sequence.

4076–4078

This is NFC. The previous 'look ()' test would cause us not to enter this block, but then fail later as 'S\0'[*] has no encoding. Removing that test causes us to enter this block and barf sooner.

look returns NUL on both end-of-string and of course an actual NUL. They're both equally ill-formed.

[ChuanqiXu]

libcxxabi/src/demangle/ItaniumDemangle.h

2671–2673

This looks equal to:

bool IsStd = consumeIf("St") || consumeIf('L');

llvm/include/llvm/Demangle/StringView.h

45–49

I thought the original logic is simpler.

[urnathan]

libcxxabi/src/demangle/ItaniumDemangle.h

2671–2673

It turns out the original logic gets in the way of some later nonNFC changes I want to make.

llvm/include/llvm/Demangle/StringView.h

45–49

This change surprised me -- I did not intentionally make it. These files in llvm/include/llvm/Demangle are synced from libcxxabi/src/demangle via that director's cp-to-llvm.sh script, which I applied. It seems that commit 1f9e18b6565fd1bb69c4b649b9efd3467b3c7c7d
Author: serge-sans-paille <[e-mail]>
Date: Thu Jan 20 11:21:47 2022 +0100

[llvm] Remove (some) LLVMDemangle header dependencies

just jumped in between my recent resync and this diff. Paging Serge!?

[urnathan]

it looks like porting Serge's patches to libcxxabi is fine. working on that, expect a diff shortly -- thanks for noticing ChuanqiXu!

[serge-sans-paille]

llvm/include/llvm/Demangle/StringView.h

45–49

Sorry, I wasn't aware of the sync... (/me checks) and it's written in the header file, my bad.

[urnathan]

llvm/include/llvm/Demangle/StringView.h

45–49

np, you;ll see my later diffs (a)D117990 fixing this and (b) D118008 making it harder to make this mistake. it'd be great if you could review those!

[ChuanqiXu]

I've checked that the change should be NFC.

libcxxabi/src/demangle/ItaniumDemangle.h

 Node *AbstractManglingParser<Derived, Alloc>::parseName(NameState *State) {
   consumeIf('L'); // extension
 
   if (look() == 'N')
     return getDerived().parseNestedName(State);
   if (look() == 'Z')
     return getDerived().parseLocalName(State);
 
+  Node *Result = nullptr;
+  bool IsSubst = look() == 'S' && look(1) != 't';
+  if (IsSubst) {
+    // A substitution must lead to:
     //        ::= <unscoped-template-name> <template-args>
-  if (look() == 'S' && look(1) != 't') {
-    Node *S = getDerived().parseSubstitution();
-    if (S == nullptr)
-      return nullptr;
-    if (look() != 'I')
-      return nullptr;
-    Node *TA = getDerived().parseTemplateArgs(State != nullptr);
-    if (TA == nullptr)
-      return nullptr;
-    if (State) State->EndsWithTemplateArgs = true;
-    return make<NameWithTemplateArgs>(S, TA);
+    Result = getDerived().parseSubstitution();
+  } else {
+    // An unscoped name can be one of:
+    //        ::= <unscoped-name>
+    //        ::= <unscoped-template-name> <template-args>
+    Result = getDerived().parseUnscopedName(State);
   }
-
-  Node *N = getDerived().parseUnscopedName(State);
-  if (N == nullptr)
+  if (Result == nullptr)
     return nullptr;
-  //        ::= <unscoped-template-name> <template-args>
+
   if (look() == 'I') {
-    Subs.push_back(N);
+    //        ::= <unscoped-template-name> <template-args>
+    if (!IsSubst)
+      // An unscoped-template-name is substitutable.
+      Subs.push_back(Result);
     Node *TA = getDerived().parseTemplateArgs(State != nullptr);
     if (TA == nullptr)
       return nullptr;
-    if (State) State->EndsWithTemplateArgs = true;
-    return make<NameWithTemplateArgs>(N, TA);
+    if (State)
+      State->EndsWithTemplateArgs = true;
+    Result = make<NameWithTemplateArgs>(Result, TA);
+  } else if (IsSubst) {
+    // The substitution case must be followed by <template-args>.
+    return nullptr;
   }
-  //        ::= <unscoped-name>
-  return N;
+
+  return Result;
 }
 
 // <local-name> := Z <function encoding> E <entity name> [<discriminator>]
 //              := Z <function encoding> E s [<discriminator>]
 //              := Z <function encoding> Ed [ <parameter number> ] _ <entity name>
 template <typename Derived, typename Alloc>
 Node *AbstractManglingParser<Derived, Alloc>::parseLocalName(NameState *State) {
   if (!consumeIf('Z'))
     return nullptr;
   Node *Encoding = getDerived().parseEncoding();

 }
 
 // <unscoped-name> ::= <unqualified-name>
 //                 ::= St <unqualified-name>   # ::std::
 // extension       ::= StL<unqualified-name>
 template <typename Derived, typename Alloc>
 Node *
 AbstractManglingParser<Derived, Alloc>::parseUnscopedName(NameState *State) {
-  if (consumeIf("StL") || consumeIf("St")) {
-    Node *R = getDerived().parseUnqualifiedName(State);
-    if (R == nullptr)
-      return nullptr;
-    return make<StdQualifiedName>(R);
-  }
-  return getDerived().parseUnqualifiedName(State);
+  bool IsStd = consumeIf("St");
+  if (IsStd)
+    consumeIf('L');
+
+  Node *Result = getDerived().parseUnqualifiedName(State);
+  if (Result == nullptr)
+  if (IsStd)
+    Result = make<StdQualifiedName>(Result);
+
+  return Result;
 }
 
 // <unqualified-name> ::= <operator-name> [abi-tags]
 //                    ::= <ctor-dtor-name>
 //                    ::= <source-name>
 //                    ::= <unnamed-type-name>
 //                    ::= DC <source-name>+ E      # structured binding declaration
 template <typename Derived, typename Alloc>
case 'G': {
     Node *P = getDerived().parseType();
     if (P == nullptr)
       return P;
     Result = make<PostfixQualifiedType>(P, " imaginary");
     break;
   }
   //             ::= <substitution>  # See Compression below
   case 'S': {
-    if (look(1) && look(1) != 't') {
-      Node *Sub = getDerived().parseSubstitution();
-      if (Sub == nullptr)
+    if (look(1) != 't') {
+      Result = getDerived().parseSubstitution();
+      if (Result == nullptr)
         return nullptr;
 
       // Sub could be either of:
       //   <type>        ::= <substitution>
       //   <type>        ::= <template-template-param> <template-args>
       //
       //   <template-template-param> ::= <template-param>
       //                             ::= <substitution>
       //
       // If this is followed by some <template-args>, and we're permitted to
       // parse them, take the second production.
 
       if (TryToParseTemplateArgs && look() == 'I') {
         Node *TA = getDerived().parseTemplateArgs();
         if (TA == nullptr)
           return nullptr;
-        Result = make<NameWithTemplateArgs>(Sub, TA);
-        break;
-      }
-
+        Result = make<NameWithTemplateArgs>(Result, TA);
+      } else {
         // If all we parsed was a substitution, don't re-insert into the
         // substitution table.
-      return Sub;
+        return Result;
+      }
+      break;
     }
     DEMANGLE_FALLTHROUGH;
   }
   //        ::= <class-enum-type>
   default: {
     Result = getDerived().parseClassEnumType();
     break;
   }

libcxxabi/test/test_demangle.pass.cpp

//    {"_Z1fM1XRFivEMS_OFivEMS_KOFivE", "f(int (X::*)() &, int (X::*)() &&, int (X::*)() const &&)"},
     // See https://bugs.llvm.org/show_bug.cgi?id=48009.
     {"_Z3fooILi79EEbU7_ExtIntIXT_EEi", "bool foo<79>(int _ExtInt<79>)"},
 
     {"_ZN3xxx3yyyIvNS_1AILm0EEEZNS_2bb2cc2ddILNS_1eE1EEEvRKNS_1fERKNS_1g1hINS_1iEEERKNS_1jEfRKNS_1kEiPhEUlvE_JEEEvT1_DpT2_", "void xxx::yyy<void, xxx::A<0ul>, void xxx::bb::cc::dd<(xxx::e)1>(xxx::f const&, xxx::g::h<xxx::i> 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<xxx::i> 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<><>"},
+
+    {"_Z3TPLIiET_S0_", "int TPL<int>(int)"},
 };
 
 const unsigned N = sizeof(cases) / sizeof(cases[0]);
 
 struct FPLiteralCase {
     const char *mangled;
     // There are four possible demanglings of a given float.
     std::string expecting[4];

llvm/include/llvm/Demangle/ItaniumDemangle.h

 
 // FIXME: (possibly) incomplete list of features that clang mangles that this
 // file does not yet support:
 //   - C++ modules TS
 
 #include "DemangleConfig.h"
 #include "StringView.h"
 #include "Utility.h"
-#include <algorithm>
 #include <cassert>
 #include <cctype>
 #include <cstdio>
 #include <cstdlib>
 #include <cstring>
-#include <limits>
+#include <numeric>
 #include <utility>
 
 #define FOR_EACH_NODE_KIND(X) \
     X(NodeArrayNode) \
     X(DotSuffix) \
     X(VendorExtQualType) \
     X(QualType) \
     X(ConversionOperatorType) \

 Node *AbstractManglingParser<Derived, Alloc>::parseName(NameState *State) {
   consumeIf('L'); // extension
 
   if (look() == 'N')
     return getDerived().parseNestedName(State);
   if (look() == 'Z')
     return getDerived().parseLocalName(State);
 
+  Node *Result = nullptr;
+  bool IsSubst = look() == 'S' && look(1) != 't';
+  if (IsSubst) {
+    // A substitution must lead to:
     //        ::= <unscoped-template-name> <template-args>
-  if (look() == 'S' && look(1) != 't') {
-    Node *S = getDerived().parseSubstitution();
-    if (S == nullptr)
-      return nullptr;
-    if (look() != 'I')
-      return nullptr;
-    Node *TA = getDerived().parseTemplateArgs(State != nullptr);
-    if (TA == nullptr)
-      return nullptr;
-    if (State) State->EndsWithTemplateArgs = true;
-    return make<NameWithTemplateArgs>(S, TA);
+    Result = getDerived().parseSubstitution();
+  } else {
+    // An unscoped name can be one of:
+    //        ::= <unscoped-name>
+    //        ::= <unscoped-template-name> <template-args>
+    Result = getDerived().parseUnscopedName(State);
   }
-
-  Node *N = getDerived().parseUnscopedName(State);
-  if (N == nullptr)
+  if (Result == nullptr)
     return nullptr;
-  //        ::= <unscoped-template-name> <template-args>
+
   if (look() == 'I') {
-    Subs.push_back(N);
+    //        ::= <unscoped-template-name> <template-args>
+    if (!IsSubst)
+      // An unscoped-template-name is substitutable.
+      Subs.push_back(Result);
     Node *TA = getDerived().parseTemplateArgs(State != nullptr);
     if (TA == nullptr)
       return nullptr;
-    if (State) State->EndsWithTemplateArgs = true;
-    return make<NameWithTemplateArgs>(N, TA);
+    if (State)
+      State->EndsWithTemplateArgs = true;
+    Result = make<NameWithTemplateArgs>(Result, TA);
+  } else if (IsSubst) {
+    // The substitution case must be followed by <template-args>.
+    return nullptr;
   }
-  //        ::= <unscoped-name>
-  return N;
+
+  return Result;
 }
 
 // <local-name> := Z <function encoding> E <entity name> [<discriminator>]
 //              := Z <function encoding> E s [<discriminator>]
 //              := Z <function encoding> Ed [ <parameter number> ] _ <entity name>
 template <typename Derived, typename Alloc>
 Node *AbstractManglingParser<Derived, Alloc>::parseLocalName(NameState *State) {
   if (!consumeIf('Z'))

 }
 
 // <unscoped-name> ::= <unqualified-name>
 //                 ::= St <unqualified-name>   # ::std::
 // extension       ::= StL<unqualified-name>
 template <typename Derived, typename Alloc>
 Node *
 AbstractManglingParser<Derived, Alloc>::parseUnscopedName(NameState *State) {
-  if (consumeIf("StL") || consumeIf("St")) {
-    Node *R = getDerived().parseUnqualifiedName(State);
-    if (R == nullptr)
-      return nullptr;
-    return make<StdQualifiedName>(R);
-  }
-  return getDerived().parseUnqualifiedName(State);
+  bool IsStd = consumeIf("St");
+  if (IsStd)
+    consumeIf('L');
+
+  Node *Result = getDerived().parseUnqualifiedName(State);
+  if (Result == nullptr)
+  if (IsStd)
+    Result = make<StdQualifiedName>(Result);
+
+  return Result;
 }
 
 // <unqualified-name> ::= <operator-name> [abi-tags]
 //                    ::= <ctor-dtor-name>
 //                    ::= <source-name>
 //                    ::= <unnamed-type-name>
 //                    ::= DC <source-name>+ E      # structured binding declaration
 template <typename Derived, typename Alloc>
case 'G': {
     Node *P = getDerived().parseType();
     if (P == nullptr)
       return P;
     Result = make<PostfixQualifiedType>(P, " imaginary");
     break;
   }
   //             ::= <substitution>  # See Compression below
   case 'S': {
-    if (look(1) && look(1) != 't') {
-      Node *Sub = getDerived().parseSubstitution();
-      if (Sub == nullptr)
+    if (look(1) != 't') {
+      Result = getDerived().parseSubstitution();
+      if (Result == nullptr)
         return nullptr;
 
       // Sub could be either of:
       //   <type>        ::= <substitution>
       //   <type>        ::= <template-template-param> <template-args>
       //
       //   <template-template-param> ::= <template-param>
       //                             ::= <substitution>
       //
       // If this is followed by some <template-args>, and we're permitted to
       // parse them, take the second production.
 
       if (TryToParseTemplateArgs && look() == 'I') {
         Node *TA = getDerived().parseTemplateArgs();
         if (TA == nullptr)
           return nullptr;
-        Result = make<NameWithTemplateArgs>(Sub, TA);
-        break;
-      }
-
+        Result = make<NameWithTemplateArgs>(Result, TA);
+      } else {
         // If all we parsed was a substitution, don't re-insert into the
         // substitution table.
-      return Sub;
+        return Result;
+      }
+      break;
     }
     DEMANGLE_FALLTHROUGH;
   }
   //        ::= <class-enum-type>
   default: {
     Result = getDerived().parseClassEnumType();
     break;
   }

llvm/include/llvm/Demangle/StringView.h

 //===--- StringView.h -------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // FIXME: Use std::string_view instead when we support C++17.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef DEMANGLE_STRINGVIEW_H
 #define DEMANGLE_STRINGVIEW_H
 
 #include "DemangleConfig.h"
+#include <algorithm>
 #include <cassert>
 #include <cstring>
 
 DEMANGLE_NAMESPACE_BEGIN
 
 class StringView {
   const char *First;
   const char *Last;
 
 public:
   static const size_t npos = ~size_t(0);
 
   template <size_t N>
   StringView(const char (&Str)[N]) : First(Str), Last(Str + N - 1) {}
   StringView(const char *First_, const char *Last_)
       : First(First_), Last(Last_) {}
   StringView(const char *First_, size_t Len)
       : First(First_), Last(First_ + Len) {}
   StringView(const char *Str) : First(Str), Last(Str + std::strlen(Str)) {}
   StringView() : First(nullptr), Last(nullptr) {}
 
   StringView substr(size_t Pos, size_t Len = npos) const {
     assert(Pos <= size());
-    if (Len > size() - Pos)
-      Len = size() - Pos;
-    return StringView(begin() + Pos, Len);
+    return StringView(begin() + Pos, std::min(Len, size() - Pos));
   }
 
   size_t find(char C, size_t From = 0) const {
+    size_t FindBegin = std::min(From, size());
     // Avoid calling memchr with nullptr.
-    if (From < size()) {
+    if (FindBegin < size()) {
       // Just forward to memchr, which is faster than a hand-rolled loop.
-      if (const void *P = ::memchr(First + From, C, size() - From))
+      if (const void *P = ::memchr(First + FindBegin, C, size() - FindBegin))
         return size_t(static_cast<const char *>(P) - First);
     }
     return npos;
   }
 
   StringView dropFront(size_t N = 1) const {
     if (N >= size())
       N = size();
bool consumeFront(StringView S) {
     return true;
   }
 
   bool startsWith(char C) const { return !empty() && *begin() == C; }
 
   bool startsWith(StringView Str) const {
     if (Str.size() > size())
       return false;
-    return std::strncmp(Str.begin(), begin(), Str.size()) == 0;
+    return std::equal(Str.begin(), Str.end(), begin());
   }
 
   const char &operator[](size_t Idx) const { return *(begin() + Idx); }
 
   const char *begin() const { return First; }
   const char *end() const { return Last; }
   size_t size() const { return static_cast<size_t>(Last - First); }
   bool empty() const { return First == Last; }
 };
 
 inline bool operator==(const StringView &LHS, const StringView &RHS) {
   return LHS.size() == RHS.size() &&
-         std::strncmp(LHS.begin(), RHS.begin(), LHS.size()) == 0;
+         std::equal(LHS.begin(), LHS.end(), RHS.begin());
 }
 
 DEMANGLE_NAMESPACE_END
 
 #endif

llvm/include/llvm/Demangle/Utility.h

 //===--- Utility.h ----------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Provide some utility classes for use in the demangler(s).
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef DEMANGLE_UTILITY_H
 #define DEMANGLE_UTILITY_H
 
 #include "StringView.h"
-#include <array>
 #include <cstdint>
 #include <cstdlib>
 #include <cstring>
-#include <exception>
+#include <iterator>
 #include <limits>
 
 DEMANGLE_NAMESPACE_BEGIN
 
 // Stream that AST nodes write their string representation into after the AST
 // has been parsed.
 class OutputBuffer {
   char *Buffer = nullptr;
class OutputBuffer {
 
   void writeUnsigned(uint64_t N, bool isNeg = false) {
     // Handle special case...
     if (N == 0) {
       *this << '0';
       return;
     }
 
-    std::array<char, 21> Temp;
-    char *TempPtr = Temp.data() + Temp.size();
+    char Temp[21];
+    char *TempPtr = std::end(Temp);
 
     while (N) {
       *--TempPtr = char('0' + N % 10);
       N /= 10;
     }
 
     // Add negative sign...
     if (isNeg)
       *--TempPtr = '-';
-    this->operator<<(StringView(TempPtr, Temp.data() + Temp.size()));
+    this->operator<<(StringView(TempPtr, std::end(Temp)));
   }
 
 public:
   OutputBuffer(char *StartBuf, size_t Size)
       : Buffer(StartBuf), CurrentPosition(0), BufferCapacity(Size) {}
   OutputBuffer() = default;
   void reset(char *Buffer_, size_t BufferCapacity_) {
     CurrentPosition = 0;