[demangler] stricter NestedName parsing

[urnathan]

Summary

The parsing of nested names is a little lax. This corrects that.

1. The 'L' local name prefix cannot appear before a NestedName -- only

within it. Let's remove that check from parseName, and then adjust
parseUnscopedName to allow it with or without the 'St' prefix.

2. In a nested name, a <template-param>, <decltype> or <substitution>

can only appear as the first element. Let's enforce that. Note I do
not remove these from the loop, to make the change easier to follow
(such a change will come later).

3. Given that, there's no need to special case 'St' outside of the

loop, handle it with the other 'S' elements.

4. There's no need to reset 'EndsWithTemplateArgs' after each

non-template-arg component. Rather, always clear it and then set it
in the template-args case.

5. An template-args cannot immediately follow a template-args.

6. The parsing of a CDtor name with ABITags would attach the tags to

the NestedName node, rather than the CDTor node. This is different to
how ABITags are attached to an unscopedName. Make it consistent.

7. We remain with only CDTor and UnscopedName requireing construction

of a NestedName, so let's drop the PushComponent lambda.

8. Add some tests to catch the new rejected manglings.

[ChuanqiXu]

Thanks for adding me as reviewer. It is good for me to learn about CXXABI. Due to the same reason, maybe I couldn't give a high quality feedback. I read code with your description. I think they are basically consistent with your description. But I couldn't found problem in the description if any.

BTW, I feel the if { continue; } style is more simpler than if {} else if {} else if{} style. The cyclomatic complexity is lower. Although there is a little bit redundant, but I feel it more clear and explicit to read and understand.

libcxxabi/src/demangle/ItaniumDemangle.h

3175

This change looks not necessary.

3189–3190

I am not sure about the style guide of libcxxabi. But I feel it is necessary to add comment here. I get the logic from your description of the patch, but I can't get it from the code simply.

3190–3191

Similarly, I can get this from your description that "In a nested name, a <template-param>, <decltype> or <substitution>
can only appear as the first element." I think it would be helpful to add a comment. Personally, I think it would be more easy to read if we move this outside the loop if we want enforce something that could only be at the start.

3204–3229

This line might require further knowledge. Does it implies that if the kind of SoFar is not Node::KNameWithTemplateArgs, the result of make<NameWithTemplateArgs>(SoFar, TA); wouldn't be nullptr?

3231–3232

At least we need a comment some like:

::= St [L]* <unqualified-name>   # ::std::

[urnathan]

libcxxabi/src/demangle/ItaniumDemangle.h

3175

FWIW I've been informed that one must put braces on all the elses or none of them -- not a mixture. I dunno.

[urnathan]

While I would probably agree about 'if () {... continue;}' if all those conditionals had different bodies, that;s not the case here. All but one end with 'if (!SoFar) return; Subs.push_back(SoFar);' I find it much easier to understand when that code is not duplicated. The case were we don't push_back remains a continue.

[urnathan]

libcxxabi/src/demangle/ItaniumDemangle.h

3190–3191

It's a semantic restriction. I've added a comment, but I'm not totally wedded to this particular change.

3204–3229

There is no such inference. Not sure what you're asking here.

3231–3232

That;s not the grammar being parsed though. This is simply a substitution that parseSubstitution does not handle. I've added comments.

[ChuanqiXu]

OK, it looks consistency for me now. Due to I don't have experience in demangler before, I think it would be better to not give a LGTM by me immediately. But if there is no other reviewers to review this in the next week, I would try to look at it again and make the status green. I understand that sometime it is hard to find someone to review : )

[ChuanqiXu]

We need to format this before landing.

[urnathan]

In D118132#3299846, @ChuanqiXu wrote:

We need to format this before landing.

I'm going to decline that.
(a) the comment formatting is breaking the long lines of the grammar -- and making that hard to read. Also, not lines I've changed.
(b) the if(state) ... formatting is idiomatic in this file. Also, not something I've changed.

libcxxabi/src/demangle/ItaniumDemangle.h

 //        ::= <local-name> # See Scope Encoding below  // Z
 //        ::= <unscoped-template-name> <template-args>
 //        ::= <unscoped-name>
 //
 // <unscoped-template-name> ::= <unscoped-name>
 //                          ::= <substitution>
 template <typename Derived, typename Alloc>
 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) {
Node *AbstractManglingParser<Derived, Alloc>::parseLocalName(NameState *State) {
 
   Node *Entity = getDerived().parseName(State);
   if (Entity == nullptr)
     return nullptr;
   First = parse_discriminator(First, Last);
   return make<LocalName>(Encoding, Entity);
 }
 
-// <unscoped-name> ::= <unqualified-name>
-//                 ::= St <unqualified-name>   # ::std::
-// extension       ::= StL<unqualified-name>
+// <unscoped-name> ::= [L]* <unqualified-name>
+//                 ::= St [L]* <unqualified-name>   # ::std::
+// [*] extension
 template <typename Derived, typename Alloc>
 Node *
 AbstractManglingParser<Derived, Alloc>::parseUnscopedName(NameState *State) {
   bool IsStd = consumeIf("St");
-  if (IsStd)
-    consumeIf('L');
 
   Node *Result = getDerived().parseUnqualifiedName(State);
   if (Result == nullptr)
     return nullptr;
   if (IsStd) {
     if (auto *Std = make<NameType>("std"))
       Result = make<NestedName>(Std, Result);
     else
AbstractManglingParser<Derived, Alloc>::parseCtorDtorName(Node *&SoFar,
   }
 
   return nullptr;
 }
 
 // <nested-name> ::= N [<CV-Qualifiers>] [<ref-qualifier>] <prefix> <unqualified-name> E
 //               ::= N [<CV-Qualifiers>] [<ref-qualifier>] <template-prefix> <template-args> E
 //
-// <prefix> ::= <prefix> <unqualified-name>
+// <prefix> ::= <prefix> [L]* <unqualified-name>
 //          ::= <template-prefix> <template-args>
 //          ::= <template-param>
 //          ::= <decltype>
 //          ::= # empty
 //          ::= <substitution>
 //          ::= <prefix> <data-member-prefix>
-//  extension ::= L
+// [*] extension
 //
 // <data-member-prefix> := <member source-name> [<template-args>] M
 //
 // <template-prefix> ::= <prefix> <template unqualified-name>
 //                   ::= <template-param>
 //                   ::= <substitution>
 template <typename Derived, typename Alloc>
 Node *
 AbstractManglingParser<Derived, Alloc>::parseNestedName(NameState *State) {
   if (!consumeIf('N'))
     return nullptr;
 
   Qualifiers CVTmp = parseCVQualifiers();
   if (State) State->CVQualifiers = CVTmp;
 
   if (consumeIf('O')) {
     if (State) State->ReferenceQualifier = FrefQualRValue;
   } else if (consumeIf('R')) {
     if (State) State->ReferenceQualifier = FrefQualLValue;
-  } else
+  } else {
     if (State) State->ReferenceQualifier = FrefQualNone;
-
-  Node *SoFar = nullptr;
-  auto PushComponent = [&](Node *Comp) {
-    if (!Comp) return false;
-    if (SoFar) SoFar = make<NestedName>(SoFar, Comp);
-    else       SoFar = Comp;
-    if (State) State->EndsWithTemplateArgs = false;
-    return SoFar != nullptr;
-  };
-
-  if (consumeIf("St")) {
-    SoFar = make<NameType>("std");
-    if (!SoFar)
-      return nullptr;
   }
 
+  Node *SoFar = nullptr;
   while (!consumeIf('E')) {
     consumeIf('L'); // extension
 
-    // <data-member-prefix> := <member source-name> [<template-args>] M
     if (consumeIf('M')) {
+      // <data-member-prefix> := <member source-name> [<template-args>] M
       if (SoFar == nullptr)
         return nullptr;
       continue;
     }
 
-    //          ::= <template-param>
-    if (look() == 'T') {
-      if (!PushComponent(getDerived().parseTemplateParam()))
-        return nullptr;
-      Subs.push_back(SoFar);
-      continue;
-    }
+    if (State)
+      // Only set end-with-template on the case that does that.
+      State->EndsWithTemplateArgs = false;
 
+    if (look() == 'T') {
+      //          ::= <template-param>
+      if (SoFar != nullptr)
+        return nullptr; // Cannot have a prefix.
+      SoFar = getDerived().parseTemplateParam();
+    } else if (look() == 'I') {
       //          ::= <template-prefix> <template-args>
-    if (look() == 'I') {
+      if (SoFar == nullptr)
+        return nullptr; // Must have a prefix.
       Node *TA = getDerived().parseTemplateArgs(State != nullptr);
-      if (TA == nullptr || SoFar == nullptr)
+      if (TA == nullptr)
         return nullptr;
-      SoFar = make<NameWithTemplateArgs>(SoFar, TA);
-      if (!SoFar)
+      if (SoFar->getKind() == Node::KNameWithTemplateArgs)
+        // Semantically <template-args> <template-args> cannot be generated by a
+        // C++ entity.  There will always be [something like] a name between
+        // them.
         return nullptr;
-      if (State) State->EndsWithTemplateArgs = true;
-      Subs.push_back(SoFar);
-      continue;
-    }
-
+      if (State)
+        State->EndsWithTemplateArgs = true;
+      SoFar = make<NameWithTemplateArgs>(SoFar, TA);
+    } else if (look() == 'D' && (look(1) == 't' || look(1) == 'T')) {
       //          ::= <decltype>
-    if (look() == 'D' && (look(1) == 't' || look(1) == 'T')) {
-      if (!PushComponent(getDerived().parseDecltype()))
-        return nullptr;
-      Subs.push_back(SoFar);
-      continue;
-    }
-
+      if (SoFar != nullptr)
+        return nullptr; // Cannot have a prefix.
+      SoFar = getDerived().parseDecltype();
+    } else if (look() == 'S') {
       //          ::= <substitution>
-    if (look() == 'S' && look(1) != 't') {
-      Node *S = getDerived().parseSubstitution();
-      if (!PushComponent(S))
-        return nullptr;
-      if (SoFar != S)
-        Subs.push_back(S);
-      continue;
+      if (SoFar != nullptr)
+        return nullptr; // Cannot have a prefix.
+      if (look(1) == 't') {
+        // parseSubstition does not handle 'St'.
+        First += 2;
+        SoFar = make<NameType>("std");
+      } else {
+        SoFar = getDerived().parseSubstitution();
       }
-
-    // Parse an <unqualified-name> thats actually a <ctor-dtor-name>.
-    if (look() == 'C' || (look() == 'D' && look(1) != 'C')) {
       if (SoFar == nullptr)
         return nullptr;
-      if (!PushComponent(getDerived().parseCtorDtorName(SoFar, State)))
-        return nullptr;
-      SoFar = getDerived().parseAbiTags(SoFar);
+      continue; // Do not push a new substitution.
+    } else {
+      Node *N = nullptr;
+      if (look() == 'C' || (look() == 'D' && look(1) != 'C')) {
+        // An <unqualified-name> that's actually a <ctor-dtor-name>.
         if (SoFar == nullptr)
           return nullptr;
-      Subs.push_back(SoFar);
-      continue;
-    }
-
+        N = getDerived().parseCtorDtorName(SoFar, State);
+        if (N != nullptr)
+          N = getDerived().parseAbiTags(N);
+      } else {
         //          ::= <prefix> <unqualified-name>
-    if (!PushComponent(getDerived().parseUnqualifiedName(State)))
+        N = getDerived().parseUnqualifiedName(State);
+      }
+      if (N == nullptr)
+        return nullptr;
+      if (SoFar)
+        SoFar = make<NestedName>(SoFar, N);
+      else
+        SoFar = N;
+    }
+    if (SoFar == nullptr)
       return nullptr;
     Subs.push_back(SoFar);
   }
 
   if (SoFar == nullptr || Subs.empty())
     return nullptr;
 
   Subs.pop_back();

 // <substitution> ::= Sa # ::std::allocator
 // <substitution> ::= Sb # ::std::basic_string
 // <substitution> ::= Ss # ::std::basic_string < char,
 //                                               ::std::char_traits<char>,
 //                                               ::std::allocator<char> >
 // <substitution> ::= Si # ::std::basic_istream<char,  std::char_traits<char> >
 // <substitution> ::= So # ::std::basic_ostream<char,  std::char_traits<char> >
 // <substitution> ::= Sd # ::std::basic_iostream<char, std::char_traits<char> >
+// The St case is handled specially in parseNestedName.
 template <typename Derived, typename Alloc>
 Node *AbstractManglingParser<Derived, Alloc>::parseSubstitution() {
   if (!consumeIf('S'))
     return nullptr;
 
   if (look() >= 'a' && look() <= 'z') {
     SpecialSubKind Kind;
     switch (look()) {

libcxxabi/test/test_demangle.pass.cpp

// The following test cases were found by libFuzzer+ASAN
     "Z1 Z1 IJEEAcvZcvT_EcvT_T_",
     "T_IZaaIJEEAnaaaT_T__",
     "PT_IJPNT_IJEET_T_T_T_)J)JKE",
     "1 IJEVNT_T_T_EE",
     "AT__ZSiIJEEAnwscT_T__",
     "FSiIJEENT_IoE ",
     "ZTVSiIZTVSiIZTVSiIZTVSiINIJEET_T_T_T_T_ ",
     "Ana_T_E_T_IJEffffffffffffffersfffffrsrsffffffbgE",
+
+    "_ZN3TPLS_E",
+    "_ZN3CLSIiEIiEE",
+    "_ZN3CLSDtLi0EEE",
+    "_ZN3CLSIiEEvNS_T_Ev",
 };
 
 const unsigned NI = sizeof(invalid_cases) / sizeof(invalid_cases[0]);
 
 void test()
 {
     std::size_t len = 0;
     char* buf = nullptr;

llvm/include/llvm/Demangle/ItaniumDemangle.h

 //        ::= <local-name> # See Scope Encoding below  // Z
 //        ::= <unscoped-template-name> <template-args>
 //        ::= <unscoped-name>
 //
 // <unscoped-template-name> ::= <unscoped-name>
 //                          ::= <substitution>
 template <typename Derived, typename Alloc>
 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) {
Node *AbstractManglingParser<Derived, Alloc>::parseLocalName(NameState *State) {
 
   Node *Entity = getDerived().parseName(State);
   if (Entity == nullptr)
     return nullptr;
   First = parse_discriminator(First, Last);
   return make<LocalName>(Encoding, Entity);
 }
 
-// <unscoped-name> ::= <unqualified-name>
-//                 ::= St <unqualified-name>   # ::std::
-// extension       ::= StL<unqualified-name>
+// <unscoped-name> ::= [L]* <unqualified-name>
+//                 ::= St [L]* <unqualified-name>   # ::std::
+// [*] extension
 template <typename Derived, typename Alloc>
 Node *
 AbstractManglingParser<Derived, Alloc>::parseUnscopedName(NameState *State) {
   bool IsStd = consumeIf("St");
-  if (IsStd)
-    consumeIf('L');
 
   Node *Result = getDerived().parseUnqualifiedName(State);
   if (Result == nullptr)
     return nullptr;
   if (IsStd) {
     if (auto *Std = make<NameType>("std"))
       Result = make<NestedName>(Std, Result);
     else
AbstractManglingParser<Derived, Alloc>::parseCtorDtorName(Node *&SoFar,
   }
 
   return nullptr;
 }
 
 // <nested-name> ::= N [<CV-Qualifiers>] [<ref-qualifier>] <prefix> <unqualified-name> E
 //               ::= N [<CV-Qualifiers>] [<ref-qualifier>] <template-prefix> <template-args> E
 //
-// <prefix> ::= <prefix> <unqualified-name>
+// <prefix> ::= <prefix> [L]* <unqualified-name>
 //          ::= <template-prefix> <template-args>
 //          ::= <template-param>
 //          ::= <decltype>
 //          ::= # empty
 //          ::= <substitution>
 //          ::= <prefix> <data-member-prefix>
-//  extension ::= L
+// [*] extension
 //
 // <data-member-prefix> := <member source-name> [<template-args>] M
 //
 // <template-prefix> ::= <prefix> <template unqualified-name>
 //                   ::= <template-param>
 //                   ::= <substitution>
 template <typename Derived, typename Alloc>
 Node *
 AbstractManglingParser<Derived, Alloc>::parseNestedName(NameState *State) {
   if (!consumeIf('N'))
     return nullptr;
 
   Qualifiers CVTmp = parseCVQualifiers();
   if (State) State->CVQualifiers = CVTmp;
 
   if (consumeIf('O')) {
     if (State) State->ReferenceQualifier = FrefQualRValue;
   } else if (consumeIf('R')) {
     if (State) State->ReferenceQualifier = FrefQualLValue;
-  } else
+  } else {
     if (State) State->ReferenceQualifier = FrefQualNone;
-
-  Node *SoFar = nullptr;
-  auto PushComponent = [&](Node *Comp) {
-    if (!Comp) return false;
-    if (SoFar) SoFar = make<NestedName>(SoFar, Comp);
-    else       SoFar = Comp;
-    if (State) State->EndsWithTemplateArgs = false;
-    return SoFar != nullptr;
-  };
-
-  if (consumeIf("St")) {
-    SoFar = make<NameType>("std");
-    if (!SoFar)
-      return nullptr;
   }
 
+  Node *SoFar = nullptr;
   while (!consumeIf('E')) {
     consumeIf('L'); // extension
 
-    // <data-member-prefix> := <member source-name> [<template-args>] M
     if (consumeIf('M')) {
+      // <data-member-prefix> := <member source-name> [<template-args>] M
       if (SoFar == nullptr)
         return nullptr;
       continue;
     }
 
-    //          ::= <template-param>
-    if (look() == 'T') {
-      if (!PushComponent(getDerived().parseTemplateParam()))
-        return nullptr;
-      Subs.push_back(SoFar);
-      continue;
-    }
+    if (State)
+      // Only set end-with-template on the case that does that.
+      State->EndsWithTemplateArgs = false;
 
+    if (look() == 'T') {
+      //          ::= <template-param>
+      if (SoFar != nullptr)
+        return nullptr; // Cannot have a prefix.
+      SoFar = getDerived().parseTemplateParam();
+    } else if (look() == 'I') {
       //          ::= <template-prefix> <template-args>
-    if (look() == 'I') {
+      if (SoFar == nullptr)
+        return nullptr; // Must have a prefix.
       Node *TA = getDerived().parseTemplateArgs(State != nullptr);
-      if (TA == nullptr || SoFar == nullptr)
+      if (TA == nullptr)
         return nullptr;
-      SoFar = make<NameWithTemplateArgs>(SoFar, TA);
-      if (!SoFar)
+      if (SoFar->getKind() == Node::KNameWithTemplateArgs)
+        // Semantically <template-args> <template-args> cannot be generated by a
+        // C++ entity.  There will always be [something like] a name between
+        // them.
         return nullptr;
-      if (State) State->EndsWithTemplateArgs = true;
-      Subs.push_back(SoFar);
-      continue;
-    }
-
+      if (State)
+        State->EndsWithTemplateArgs = true;
+      SoFar = make<NameWithTemplateArgs>(SoFar, TA);
+    } else if (look() == 'D' && (look(1) == 't' || look(1) == 'T')) {
       //          ::= <decltype>
-    if (look() == 'D' && (look(1) == 't' || look(1) == 'T')) {
-      if (!PushComponent(getDerived().parseDecltype()))
-        return nullptr;
-      Subs.push_back(SoFar);
-      continue;
-    }
-
+      if (SoFar != nullptr)
+        return nullptr; // Cannot have a prefix.
+      SoFar = getDerived().parseDecltype();
+    } else if (look() == 'S') {
       //          ::= <substitution>
-    if (look() == 'S' && look(1) != 't') {
-      Node *S = getDerived().parseSubstitution();
-      if (!PushComponent(S))
-        return nullptr;
-      if (SoFar != S)
-        Subs.push_back(S);
-      continue;
+      if (SoFar != nullptr)
+        return nullptr; // Cannot have a prefix.
+      if (look(1) == 't') {
+        // parseSubstition does not handle 'St'.
+        First += 2;
+        SoFar = make<NameType>("std");
+      } else {
+        SoFar = getDerived().parseSubstitution();
       }
-
-    // Parse an <unqualified-name> thats actually a <ctor-dtor-name>.
-    if (look() == 'C' || (look() == 'D' && look(1) != 'C')) {
       if (SoFar == nullptr)
         return nullptr;
-      if (!PushComponent(getDerived().parseCtorDtorName(SoFar, State)))
-        return nullptr;
-      SoFar = getDerived().parseAbiTags(SoFar);
+      continue; // Do not push a new substitution.
+    } else {
+      Node *N = nullptr;
+      if (look() == 'C' || (look() == 'D' && look(1) != 'C')) {
+        // An <unqualified-name> that's actually a <ctor-dtor-name>.
         if (SoFar == nullptr)
           return nullptr;
-      Subs.push_back(SoFar);
-      continue;
-    }
-
+        N = getDerived().parseCtorDtorName(SoFar, State);
+        if (N != nullptr)
+          N = getDerived().parseAbiTags(N);
+      } else {
         //          ::= <prefix> <unqualified-name>
-    if (!PushComponent(getDerived().parseUnqualifiedName(State)))
+        N = getDerived().parseUnqualifiedName(State);
+      }
+      if (N == nullptr)
+        return nullptr;
+      if (SoFar)
+        SoFar = make<NestedName>(SoFar, N);
+      else
+        SoFar = N;
+    }
+    if (SoFar == nullptr)
       return nullptr;
     Subs.push_back(SoFar);
   }
 
   if (SoFar == nullptr || Subs.empty())
     return nullptr;
 
   Subs.pop_back();

 // <substitution> ::= Sa # ::std::allocator
 // <substitution> ::= Sb # ::std::basic_string
 // <substitution> ::= Ss # ::std::basic_string < char,
 //                                               ::std::char_traits<char>,
 //                                               ::std::allocator<char> >
 // <substitution> ::= Si # ::std::basic_istream<char,  std::char_traits<char> >
 // <substitution> ::= So # ::std::basic_ostream<char,  std::char_traits<char> >
 // <substitution> ::= Sd # ::std::basic_iostream<char, std::char_traits<char> >
+// The St case is handled specially in parseNestedName.
 template <typename Derived, typename Alloc>
 Node *AbstractManglingParser<Derived, Alloc>::parseSubstitution() {
   if (!consumeIf('S'))
     return nullptr;
 
   if (look() >= 'a' && look() <= 'z') {
     SpecialSubKind Kind;
     switch (look()) {