[demangler] Add support for C++20 modules

[urnathan]

Summary

Now all the prerequisite demangler patches are in, here's the patch for module demangling. As with the mangler patch (D118352) this is the updated scheme described at: https://drive.google.com/file/d/1quPYyByXqOpCyAPlxYt1JleA70TSFMrp/view?usp=sharing

We have two new demangler nodes -- ModuleName and ModuleEntity. The former represents a module name in a hierarchical fashion. The latter is the combination of a (name) node and a module name. Because module names and entity identities use the same substitution encoding, we have to adjust the flow of how substitutions are handled, and examine the substituted node to know how to deal with it.

There is one difference to that doc, the global initializer _ZGI <module-name> lacks the 'v' suffix. I don't think that necessary -- my original thought was of describing something more like a regular void function mangling. I'll be updating the google doc with this alteration and some other clarifications that don't affect the demangler.

[ChuanqiXu]

Let's add D118352 as a related revision?

[urnathan]

In D119933#3328106, @ChuanqiXu wrote:

Let's add D118352 as a related revision?

It's related. but it is neither a child nor parent. And we've now noted it here :)

[urnathan]

rebase, & fix formats

[urnathan]

fix CI formatting

[urnathan]

rebase again

[urnathan]

remove trailing whitespace

[urnathan]

rebased, the clang-format CI fail is due to testcase formatting that I have not touched.

[urnathan]

ping? AFAICT the CI build failures are not consistent and not caused by this patch

[dblaikie]

I don't have much context for the mangler, but this generally looks OK to me. (one minor question, probably just a comment update)

llvm/include/llvm/Demangle/ItaniumDemangle.h

2829–2835

Is the comment about S out of date, and should say W instead?

[urnathan]

llvm/include/llvm/Demangle/ItaniumDemangle.h

2829–2835

oops, I'd think'od that, it is indeed 'W'

[MaskRay]

Seems that abi::__cxa_demangle("W2.c", nullptr, nullptr, &ignored); crashes on libcxxabi/src/demangle/ItaniumDemangle.h:355 printLeft(OB); (virtual function call).

At the call site libcxxabi/src/cxa_demangle.cpp:358, Node *AST is parsed as a type which does not seem to have the left child.

[MaskRay]

libcxxabi/src/demangle/ItaniumDemangle.h

1033

Name can be nullptr here when the input is "W2.c" (would be parsed as a type). See my main comment.

[dblaikie]

Made a fix here: 6f5ecd089f77e0da9af44bb7211ad1b11ea582d4 - could have a _Z* test case too as I think it'd come up there too.

libcxxabi/src/demangle/ItaniumDemangle.h

 // libcxxabi is the original and the one under llvm is the copy.  Use
 // cp-to-llvm.sh to update the copy.  See README.txt for more details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef DEMANGLE_ITANIUMDEMANGLE_H
 #define 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>
#define FOR_EACH_NODE_KIND(X)                                                  \
   X(DynamicExceptionSpec)                                                      \
   X(FunctionEncoding)                                                          \
   X(LiteralOperator)                                                           \
   X(SpecialName)                                                               \
   X(CtorVtableSpecialName)                                                     \
   X(QualifiedName)                                                             \
   X(NestedName)                                                                \
   X(LocalName)                                                                 \
+  X(ModuleName)                                                                \
+  X(ModuleEntity)                                                              \
   X(VectorType)                                                                \
   X(PixelVectorType)                                                           \
   X(BinaryFPType)                                                              \
   X(SyntheticTemplateParamName)                                                \
   X(TypeTemplateParamDecl)                                                     \
   X(NonTypeTemplateParamDecl)                                                  \
   X(TemplateTemplateParamDecl)                                                 \
   X(TemplateParamPackDecl)                                                     \
struct NestedName : Node {
 
   void printLeft(OutputBuffer &OB) const override {
     Qual->print(OB);
     OB += "::";
     Name->print(OB);
   }
 };
 
+struct ModuleName : Node {
+  ModuleName *Parent;
+  Node *Name;
+  bool IsPartition;
+
+  ModuleName(ModuleName *Parent_, Node *Name_, bool IsPartition_ = false)
+      : Node(KModuleName), Parent(Parent_), Name(Name_),
+        IsPartition(IsPartition_) {}
+
+  template <typename Fn> void match(Fn F) const { F(Parent, Name); }
+
+  void printLeft(OutputBuffer &OB) const override {
+    if (Parent)
+      Parent->print(OB);
+    if (Parent || IsPartition)
+      OB += IsPartition ? ':' : '.';
+    Name->print(OB);
+  }
+};
+
+struct ModuleEntity : Node {
+  ModuleName *Module;
+  Node *Name;
+
+  ModuleEntity(ModuleName *Module_, Node *Name_)
+      : Node(KModuleEntity), Module(Module_), Name(Name_) {}
+
+  template <typename Fn> void match(Fn F) const { F(Module, Name); }
+
+  StringView getBaseName() const override { return Name->getBaseName(); }
+
+  void printLeft(OutputBuffer &OB) const override {
+    Name->print(OB);
+    OB += '@';
+    Module->print(OB);
+  }
+};
+
 struct LocalName : Node {
   Node *Encoding;
   Node *Entity;
 
   LocalName(Node *Encoding_, Node *Entity_)
       : Node(KLocalName), Encoding(Encoding_), Entity(Entity_) {}
 
   template<typename Fn> void match(Fn F) const { F(Encoding, Entity); }
bool resolveForwardTemplateRefs(NameState &State) {
     ForwardTemplateRefs.dropBack(State.ForwardTemplateRefsBegin);
     return false;
   }
 
   /// Parse the <name> production>
   Node *parseName(NameState *State = nullptr);
   Node *parseLocalName(NameState *State);
   Node *parseOperatorName(NameState *State);
-  Node *parseUnqualifiedName(NameState *State, Node *Scope);
+  bool parseModuleNameOpt(ModuleName *&Module);
+  Node *parseUnqualifiedName(NameState *State, Node *Scope, ModuleName *Module);
   Node *parseUnnamedTypeName(NameState *State);
   Node *parseSourceName(NameState *State);
-  Node *parseUnscopedName(NameState *State);
+  Node *parseUnscopedName(NameState *State, bool *isSubstName);
   Node *parseNestedName(NameState *State);
   Node *parseCtorDtorName(Node *&SoFar, NameState *State);
 
   Node *parseAbiTags(Node *N);
 
   struct OperatorInfo {
     enum OIKind : unsigned char {
       Prefix,      // Prefix unary: @ expr

 template <typename Derived, typename Alloc>
 Node *AbstractManglingParser<Derived, Alloc>::parseName(NameState *State) {
   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>
-    Result = getDerived().parseSubstitution();
-  } else {
-    // An unscoped name can be one of:
-    //        ::= <unscoped-name>
-    //        ::= <unscoped-template-name> <template-args>
-    Result = getDerived().parseUnscopedName(State);
-  }
-  if (Result == nullptr)
+  bool IsSubst = false;
+
+  Result = getDerived().parseUnscopedName(State, &IsSubst);
+  if (!Result)
     return nullptr;
 
   if (look() == 'I') {
     //        ::= <unscoped-template-name> <template-args>
     if (!IsSubst)
       // An unscoped-template-name is substitutable.
       Subs.push_back(Result);
     Node *TA = getDerived().parseTemplateArgs(State != nullptr);
Node *AbstractManglingParser<Derived, Alloc>::parseLocalName(NameState *State) {
   return make<LocalName>(Encoding, Entity);
 }
 
 // <unscoped-name> ::= [L]* <unqualified-name>
 //                 ::= St [L]* <unqualified-name>   # ::std::
 // [*] extension
 template <typename Derived, typename Alloc>
 Node *
-AbstractManglingParser<Derived, Alloc>::parseUnscopedName(NameState *State) {
+AbstractManglingParser<Derived, Alloc>::parseUnscopedName(NameState *State,
+                                                          bool *IsSubst) {
+
   Node *Std = nullptr;
   if (consumeIf("St")) {
     Std = make<NameType>("std");
     if (Std == nullptr)
       return nullptr;
   }
   consumeIf('L');
 
-  return getDerived().parseUnqualifiedName(State, Std);
+  Node *Res = nullptr;
+  ModuleName *Module = nullptr;
+  if (look() == 'S') {
+    Node *S = getDerived().parseSubstitution();
+    if (!S)
+      return nullptr;
+    if (S->getKind() == Node::KModuleName)
+      Module = static_cast<ModuleName *>(S);
+    else if (IsSubst && Std == nullptr) {
+      Res = S;
+      *IsSubst = true;
+    } else {
+      return nullptr;
+    }
   }
 
-// <unqualified-name> ::= <operator-name> [abi-tags]
-//                    ::= <ctor-dtor-name> [<abi-tags>]
-//                    ::= <source-name> [<abi-tags>]
-//                    ::= <unnamed-type-name> [<abi-tags>]
-//                    ::= DC <source-name>+ E      # structured binding declaration
-template <typename Derived, typename Alloc>
-Node *
-AbstractManglingParser<Derived, Alloc>::parseUnqualifiedName(NameState *State,
-                                                             Node *Scope) {
+  if (Res == nullptr)
+    Res = getDerived().parseUnqualifiedName(State, Std, Module);
+
+  return Res;
+}
+
+// <unqualified-name> ::= [<module-name>] <operator-name> [<abi-tags>]
+//                    ::= [<module-name>] <ctor-dtor-name> [<abi-tags>]
+//                    ::= [<module-name>] <source-name> [<abi-tags>]
+//                    ::= [<module-name>] <unnamed-type-name> [<abi-tags>]
+//      # structured binding declaration
+//                    ::= [<module-name>] DC <source-name>+ E
+template <typename Derived, typename Alloc>
+Node *AbstractManglingParser<Derived, Alloc>::parseUnqualifiedName(
+    NameState *State, Node *Scope, ModuleName *Module) {
+  if (getDerived().parseModuleNameOpt(Module))
+    return nullptr;
+
   Node *Result;
-  if (look() == 'U')
+  if (look() == 'U') {
     Result = getDerived().parseUnnamedTypeName(State);
-  else if (look() >= '1' && look() <= '9')
+  } else if (look() >= '1' && look() <= '9') {
     Result = getDerived().parseSourceName(State);
-  else if (consumeIf("DC")) {
+  } else if (consumeIf("DC")) {
     // Structured binding
     size_t BindingsBegin = Names.size();
     do {
       Node *Binding = getDerived().parseSourceName(State);
       if (Binding == nullptr)
         return nullptr;
       Names.push_back(Binding);
     } while (!consumeIf('E'));
     Result = make<StructuredBindingName>(popTrailingNodeArray(BindingsBegin));
   } else if (look() == 'C' || look() == 'D') {
     // A <ctor-dtor-name>.
-    if (Scope == nullptr)
+    if (Scope == nullptr || Module != nullptr)
       return nullptr;
     Result = getDerived().parseCtorDtorName(Scope, State);
   } else {
     Result = getDerived().parseOperatorName(State);
   }
+
+  if (Module)
+    Result = make<ModuleEntity>(Module, Result);
   if (Result != nullptr)
     Result = getDerived().parseAbiTags(Result);
   if (Result != nullptr && Scope != nullptr)
     Result = make<NestedName>(Scope, Result);
+
   return Result;
 }
 
+// <module-name> ::= <module-subname>
+//     ::= <module-name> <module-subname>
+//     ::= <substitution>  # passed in by caller
+// <module-subname> ::= W <source-name>
+//        ::= W P <source-name>
+template <typename Derived, typename Alloc>
+bool AbstractManglingParser<Derived, Alloc>::parseModuleNameOpt(
+    ModuleName *&Module) {
+  while (consumeIf('W')) {
+    bool IsPartition = consumeIf('P');
+    Node *Sub = getDerived().parseSourceName(nullptr);
+    if (!Sub)
+      return true;
+    Module =
+        static_cast<ModuleName *>(make<ModuleName>(Module, Sub, IsPartition));
+    Subs.push_back(Module);
+  }
+
+  return false;
+}
+
 // <unnamed-type-name> ::= Ut [<nonnegative number>] _
 //                     ::= <closure-type-name>
 //
 // <closure-type-name> ::= Ul <lambda-sig> E [ <nonnegative number> ] _
 //
 // <lambda-sig> ::= <parameter type>+  # Parameter types or "v" if the lambda has no parameters
 template <typename Derived, typename Alloc>
 Node *
if (look() == 'T') {
       if (State)
         State->EndsWithTemplateArgs = true;
       SoFar = make<NameWithTemplateArgs>(SoFar, TA);
     } else if (look() == 'D' && (look(1) == 't' || look(1) == 'T')) {
       //          ::= <decltype>
       if (SoFar != nullptr)
         return nullptr; // Cannot have a prefix.
       SoFar = getDerived().parseDecltype();
-    } else if (look() == 'S') {
+    } else {
+      ModuleName *Module = nullptr;
+      bool IsLocal = consumeIf('L'); // extension
+
+      if (look() == 'S') {
         //          ::= <substitution>
-      if (SoFar != nullptr)
-        return nullptr; // Cannot have a prefix.
+        Node *S = nullptr;
         if (look(1) == 't') {
-        // parseSubstition does not handle 'St'.
           First += 2;
-        SoFar = make<NameType>("std");
+          S = make<NameType>("std");
         } else {
-        SoFar = getDerived().parseSubstitution();
+          S = getDerived().parseSubstitution();
         }
-      if (SoFar == nullptr)
+        if (!S)
           return nullptr;
-      continue; // Do not push a new substitution.
+        if (S->getKind() == Node::KModuleName) {
+          Module = static_cast<ModuleName *>(S);
+        } else if (SoFar != nullptr || IsLocal) {
+          return nullptr; // Cannot have a prefix.
         } else {
-      consumeIf('L'); // extension
+          SoFar = S;
+          continue; // Do not push a new substitution.
+        }
+      }
+
       //          ::= [<prefix>] <unqualified-name>
-      SoFar = getDerived().parseUnqualifiedName(State, SoFar);
+      SoFar = getDerived().parseUnqualifiedName(State, SoFar, Module);
     }
+
     if (SoFar == nullptr)
       return nullptr;
     Subs.push_back(SoFar);
 
     // No longer used.
     // <data-member-prefix> := <member source-name> [<template-args>] M
     consumeIf('M');
   }
case 'G': {
     if (P == nullptr)
       return P;
     Result = make<PostfixQualifiedType>(P, " imaginary");
     break;
   }
   //             ::= <substitution>  # See Compression below
   case 'S': {
     if (look(1) != 't') {
-      Result = getDerived().parseSubstitution();
-      if (Result == nullptr)
+      bool IsSubst = false;
+      Result = getDerived().parseUnscopedName(nullptr, &IsSubst);
+      if (!Result)
         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') {
+      if (look() == 'I' && (!IsSubst || TryToParseTemplateArgs)) {
+        if (!IsSubst)
+          Subs.push_back(Result);
         Node *TA = getDerived().parseTemplateArgs();
         if (TA == nullptr)
           return nullptr;
         Result = make<NameWithTemplateArgs>(Result, TA);
-      } else {
+      } else if (IsSubst) {
         // If all we parsed was a substitution, don't re-insert into the
         // substitution table.
         return Result;
       }
       break;
     }
     DEMANGLE_FALLTHROUGH;
   }

 //                ::= TI <type>    # typeinfo structure
 //                ::= TS <type>    # typeinfo name (null-terminated byte string)
 //                ::= Tc <call-offset> <call-offset> <base encoding>
 //                    # base is the nominal target function of thunk
 //                    # first call-offset is 'this' adjustment
 //                    # second call-offset is result adjustment
 //                ::= T <call-offset> <base encoding>
 //                    # base is the nominal target function of thunk
-//                ::= GV <object name> # Guard variable for one-time initialization
+//                # Guard variable for one-time initialization
+//                ::= GV <object name>
 //                                     # No <type>
 //                ::= TW <object name> # Thread-local wrapper
 //                ::= TH <object name> # Thread-local initialization
 //                ::= GR <object name> _             # First temporary
 //                ::= GR <object name> <seq-id> _    # Subsequent temporaries
-//      extension ::= TC <first type> <number> _ <second type> # construction vtable for second-in-first
+//                # construction vtable for second-in-first
+//      extension ::= TC <first type> <number> _ <second type>
 //      extension ::= GR <object name> # reference temporary for object
+//      extension ::= GI <module name> # module global initializer
 template <typename Derived, typename Alloc>
 Node *AbstractManglingParser<Derived, Alloc>::parseSpecialName() {
   switch (look()) {
   case 'T':
     switch (look(1)) {
     // TA <template-arg>    # template parameter object
     //
     // Not yet in the spec: https://github.com/itanium-cxx-abi/cxx-abi/issues/63
case 'R': {
       if (Name == nullptr)
         return nullptr;
       size_t Count;
       bool ParsedSeqId = !parseSeqId(&Count);
       if (!consumeIf('_') && ParsedSeqId)
         return nullptr;
       return make<SpecialName>("reference temporary for ", Name);
     }
+    // GI <module-name> v
+    case 'I': {
+      First += 2;
+      ModuleName *Module = nullptr;
+      if (getDerived().parseModuleNameOpt(Module))
+        return nullptr;
+      if (Module == nullptr)
+        return nullptr;
+      return make<SpecialName>("initializer for module ", Module);
+    }
     }
   }
   return nullptr;
 }
 
 // <encoding> ::= <function name> <bare-function-type>
 //            ::= <data name>
 //            ::= <special-name>

libcxxabi/test/test_demangle.pass.cpp

//    {"_Z1fM1XRFivEMS_OFivEMS_KOFivE", "f(int (X::*)() &, int (X::*)() &&, int (X::*)() const &&)"},
     {"_ZN2FnIXgsnw_iEEXna_ipiLi4EEEEEvv", "void Fn<::new int, new[] int(4)>()"},
     {"_ZN2FnIXnwLj4E_iEEXgsnaLj4E_ipiLi4EEEEEvv", "void Fn<new(4u) int, ::new[](4u) int(4)>()"},
     {"_ZN2FnIXgsdlLi4EEXdaLi4EEEEvv", "void Fn<::delete 4, delete[] 4>()"},
     {"_ZN2FnIXdlLj4EEXgsdaLj4EEEEvv", "void Fn<delete 4u, ::delete[] 4u>()"},
 
     {"_Z3TPLIiET_S0_", "int TPL<int>(int)"},
 
     {"_ZN1XawEv", "X::operator co_await()"},
+
+    // C++20 modules
+    {"_ZN5Outer5InnerW3FOO2FnERNS0_1XE", "Outer::Inner::Fn@FOO(Outer::Inner::X&)"},
+    {"_ZN5OuterW3FOO5Inner2FnERNS1_1XE", "Outer::Inner@FOO::Fn(Outer::Inner@FOO::X&)"},
+    {"_ZN4Quux4TotoW3FooW3Bar3BazEPNS0_S2_5PlughE", "Quux::Toto::[e-mail](Quux::Toto::[e-mail]*)"},
+    {"_ZW6Module1fNS_1a1bENS0_1cE", "f@Module(a@Module::b, a@Module::c)"},
+    {"_ZN3BobW3FOOW3BAR3BarEPS1_1APNS_S1_1BE", "Bob::[e-mail]([e-mail]*, Bob::[e-mail]*)"},
+    {"_ZW3FOOW3BAR3FooPS0_1APN3BobS0_1BE", "[e-mail]([e-mail]*, Bob::[e-mail]*)"},
+    {"_ZN3BobW3FOOW3BAZ3FooEPS0_W3BAR1APNS_S2_1BE", "Bob::[e-mail]([e-mail]*, Bob::[e-mail]*)"},
+    {"_ZW3FOOW3BAZ3BarPS_W3BAR1APN3BobS1_1BE", "[e-mail]([e-mail]*, Bob::[e-mail]*)"},
+    {"_ZNW3FOO3TPLIS_3OneE1MEPS1_", "TPL@FOO<One@FOO>::M(One@FOO*)"},
+    {"_ZNW3FOO3TPLIS_3OneE1NIS_3TwoEEvPS1_PT_", "void TPL@FOO<One@FOO>::N<Two@FOO>(One@FOO*, Two@FOO*)"},
+    {"_ZN3NMSW3FOO3TPLINS_S0_3OneEE1MEPS2_", "NMS::TPL@FOO<NMS::One@FOO>::M(NMS::One@FOO*)"},
+    {"_ZN3NMSW3FOO3TPLINS_S0_3OneEE1NINS_S0_3TwoEEEvPS2_PT_",
+     "void NMS::TPL@FOO<NMS::One@FOO>::N<NMS::Two@FOO>(NMS::One@FOO*, NMS::Two@FOO*)"},
+    {"_ZNStW3STD9allocatorIiE1MEPi", "std::allocator@STD<int>::M(int*)"},
+    {"_ZNStW3STD9allocatorIiE1NIfEEPT_Pi", "float* std::allocator@STD<int>::N<float>(int*)"},
+    {"_ZNStW3STD9allocatorI4PoohE1MEPS1_", "std::allocator@STD<Pooh>::M(Pooh*)"},
+    {"_ZNStW3STD9allocatorI4PoohE1NI6PigletEEPT_PS1_", "Piglet* std::allocator@STD<Pooh>::N<Piglet>(Pooh*)"},
+    {"_ZW3FooDC1a1bE", "[a, b]@Foo"},
+    {"_ZN1NW3FooDC1a1bEE", "N::[a, b]@Foo"},
+    {"_ZN3NMSW3MOD3FooB3ABIEv", "NMS::Foo@MOD[abi:ABI]()"},
+    {"_ZGIW3Foo", "initializer for module Foo"},
+    {"_ZGIW3FooW3Bar", "initializer for module Foo.Bar"},
+    {"_ZGIW3FooWP3BarW3Baz", "initializer for module Foo:Bar.Baz"},
 };
 
 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];
// The following test cases were found by libFuzzer+ASAN
     "_ZN3CLSIiEIiEE",
     "_ZN3CLSDtLi0EEE",
     "_ZN3CLSIiEEvNS_T_Ev",
 
     "_ZN1fIiEEvNTUt_E",
     "_ZNDTUt_Ev",
 
     "_ZN1fIXawLi0EEEEvv",
+
+    "_ZNWUt_3FOOEv",
+    "_ZWDC3FOOEv",
+    "_ZGI3Foo",
+    "_ZGIW3Foov",
 };
 
 const unsigned NI = sizeof(invalid_cases) / sizeof(invalid_cases[0]);
 
 void test()
 {
     std::size_t len = 0;
     char* buf = nullptr;
for (unsigned i = 0; i < NI; ++i)
         if (demang)
           buf = demang;
     }
     free(buf);
     assert(!passed && "demangle did not fail");
 }
 
 const char *xfail_cases[] = {
-    "_ZW6FooBarE2f3v", // C++ modules TS
-
     // FIXME: Why does clang generate the "cp" expr?
     "_ZN5test11bIsEEDTcp3foocvT__EEES1_",
 };
 
 const size_t num_xfails = sizeof(xfail_cases) / sizeof(xfail_cases[0]);
 
 void test_xfail_cases()
 {

llvm/include/llvm/Demangle/ItaniumDemangle.h

 // libcxxabi is the original and the one under llvm is the copy.  Use
 // cp-to-llvm.sh to update the copy.  See README.txt for more details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef DEMANGLE_ITANIUMDEMANGLE_H
 #define 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>
#define FOR_EACH_NODE_KIND(X)                                                  \
   X(DynamicExceptionSpec)                                                      \
   X(FunctionEncoding)                                                          \
   X(LiteralOperator)                                                           \
   X(SpecialName)                                                               \
   X(CtorVtableSpecialName)                                                     \
   X(QualifiedName)                                                             \
   X(NestedName)                                                                \
   X(LocalName)                                                                 \
+  X(ModuleName)                                                                \
+  X(ModuleEntity)                                                              \
   X(VectorType)                                                                \
   X(PixelVectorType)                                                           \
   X(BinaryFPType)                                                              \
   X(SyntheticTemplateParamName)                                                \
   X(TypeTemplateParamDecl)                                                     \
   X(NonTypeTemplateParamDecl)                                                  \
   X(TemplateTemplateParamDecl)                                                 \
   X(TemplateParamPackDecl)                                                     \
struct NestedName : Node {
 
   void printLeft(OutputBuffer &OB) const override {
     Qual->print(OB);
     OB += "::";
     Name->print(OB);
   }
 };
 
+struct ModuleName : Node {
+  ModuleName *Parent;
+  Node *Name;
+  bool IsPartition;
+
+  ModuleName(ModuleName *Parent_, Node *Name_, bool IsPartition_ = false)
+      : Node(KModuleName), Parent(Parent_), Name(Name_),
+        IsPartition(IsPartition_) {}
+
+  template <typename Fn> void match(Fn F) const { F(Parent, Name); }
+
+  void printLeft(OutputBuffer &OB) const override {
+    if (Parent)
+      Parent->print(OB);
+    if (Parent || IsPartition)
+      OB += IsPartition ? ':' : '.';
+    Name->print(OB);
+  }
+};
+
+struct ModuleEntity : Node {
+  ModuleName *Module;
+  Node *Name;
+
+  ModuleEntity(ModuleName *Module_, Node *Name_)
+      : Node(KModuleEntity), Module(Module_), Name(Name_) {}
+
+  template <typename Fn> void match(Fn F) const { F(Module, Name); }
+
+  StringView getBaseName() const override { return Name->getBaseName(); }
+
+  void printLeft(OutputBuffer &OB) const override {
+    Name->print(OB);
+    OB += '@';
+    Module->print(OB);
+  }
+};
+
 struct LocalName : Node {
   Node *Encoding;
   Node *Entity;
 
   LocalName(Node *Encoding_, Node *Entity_)
       : Node(KLocalName), Encoding(Encoding_), Entity(Entity_) {}
 
   template<typename Fn> void match(Fn F) const { F(Encoding, Entity); }
bool resolveForwardTemplateRefs(NameState &State) {
     ForwardTemplateRefs.dropBack(State.ForwardTemplateRefsBegin);
     return false;
   }
 
   /// Parse the <name> production>
   Node *parseName(NameState *State = nullptr);
   Node *parseLocalName(NameState *State);
   Node *parseOperatorName(NameState *State);
-  Node *parseUnqualifiedName(NameState *State, Node *Scope);
+  bool parseModuleNameOpt(ModuleName *&Module);
+  Node *parseUnqualifiedName(NameState *State, Node *Scope, ModuleName *Module);
   Node *parseUnnamedTypeName(NameState *State);
   Node *parseSourceName(NameState *State);
-  Node *parseUnscopedName(NameState *State);
+  Node *parseUnscopedName(NameState *State, bool *isSubstName);
   Node *parseNestedName(NameState *State);
   Node *parseCtorDtorName(Node *&SoFar, NameState *State);
 
   Node *parseAbiTags(Node *N);
 
   struct OperatorInfo {
     enum OIKind : unsigned char {
       Prefix,      // Prefix unary: @ expr

 template <typename Derived, typename Alloc>
 Node *AbstractManglingParser<Derived, Alloc>::parseName(NameState *State) {
   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>
-    Result = getDerived().parseSubstitution();
-  } else {
-    // An unscoped name can be one of:
-    //        ::= <unscoped-name>
-    //        ::= <unscoped-template-name> <template-args>
-    Result = getDerived().parseUnscopedName(State);
-  }
-  if (Result == nullptr)
+  bool IsSubst = false;
+
+  Result = getDerived().parseUnscopedName(State, &IsSubst);
+  if (!Result)
     return nullptr;
 
   if (look() == 'I') {
     //        ::= <unscoped-template-name> <template-args>
     if (!IsSubst)
       // An unscoped-template-name is substitutable.
       Subs.push_back(Result);
     Node *TA = getDerived().parseTemplateArgs(State != nullptr);
Node *AbstractManglingParser<Derived, Alloc>::parseLocalName(NameState *State) {
   return make<LocalName>(Encoding, Entity);
 }
 
 // <unscoped-name> ::= [L]* <unqualified-name>
 //                 ::= St [L]* <unqualified-name>   # ::std::
 // [*] extension
 template <typename Derived, typename Alloc>
 Node *
-AbstractManglingParser<Derived, Alloc>::parseUnscopedName(NameState *State) {
+AbstractManglingParser<Derived, Alloc>::parseUnscopedName(NameState *State,
+                                                          bool *IsSubst) {
+
   Node *Std = nullptr;
   if (consumeIf("St")) {
     Std = make<NameType>("std");
     if (Std == nullptr)
       return nullptr;
   }
   consumeIf('L');
 
-  return getDerived().parseUnqualifiedName(State, Std);
+  Node *Res = nullptr;
+  ModuleName *Module = nullptr;
+  if (look() == 'S') {
+    Node *S = getDerived().parseSubstitution();
+    if (!S)
+      return nullptr;
+    if (S->getKind() == Node::KModuleName)
+      Module = static_cast<ModuleName *>(S);
+    else if (IsSubst && Std == nullptr) {
+      Res = S;
+      *IsSubst = true;
+    } else {
+      return nullptr;
+    }
   }
 
-// <unqualified-name> ::= <operator-name> [abi-tags]
-//                    ::= <ctor-dtor-name> [<abi-tags>]
-//                    ::= <source-name> [<abi-tags>]
-//                    ::= <unnamed-type-name> [<abi-tags>]
-//                    ::= DC <source-name>+ E      # structured binding declaration
-template <typename Derived, typename Alloc>
-Node *
-AbstractManglingParser<Derived, Alloc>::parseUnqualifiedName(NameState *State,
-                                                             Node *Scope) {
+  if (Res == nullptr)
+    Res = getDerived().parseUnqualifiedName(State, Std, Module);
+
+  return Res;
+}
+
+// <unqualified-name> ::= [<module-name>] <operator-name> [<abi-tags>]
+//                    ::= [<module-name>] <ctor-dtor-name> [<abi-tags>]
+//                    ::= [<module-name>] <source-name> [<abi-tags>]
+//                    ::= [<module-name>] <unnamed-type-name> [<abi-tags>]
+//      # structured binding declaration
+//                    ::= [<module-name>] DC <source-name>+ E
+template <typename Derived, typename Alloc>
+Node *AbstractManglingParser<Derived, Alloc>::parseUnqualifiedName(
+    NameState *State, Node *Scope, ModuleName *Module) {
+  if (getDerived().parseModuleNameOpt(Module))
+    return nullptr;
+
   Node *Result;
-  if (look() == 'U')
+  if (look() == 'U') {
     Result = getDerived().parseUnnamedTypeName(State);
-  else if (look() >= '1' && look() <= '9')
+  } else if (look() >= '1' && look() <= '9') {
     Result = getDerived().parseSourceName(State);
-  else if (consumeIf("DC")) {
+  } else if (consumeIf("DC")) {
     // Structured binding
     size_t BindingsBegin = Names.size();
     do {
       Node *Binding = getDerived().parseSourceName(State);
       if (Binding == nullptr)
         return nullptr;
       Names.push_back(Binding);
     } while (!consumeIf('E'));
     Result = make<StructuredBindingName>(popTrailingNodeArray(BindingsBegin));
   } else if (look() == 'C' || look() == 'D') {
     // A <ctor-dtor-name>.
-    if (Scope == nullptr)
+    if (Scope == nullptr || Module != nullptr)
       return nullptr;
     Result = getDerived().parseCtorDtorName(Scope, State);
   } else {
     Result = getDerived().parseOperatorName(State);
   }
+
+  if (Module)
+    Result = make<ModuleEntity>(Module, Result);
   if (Result != nullptr)
     Result = getDerived().parseAbiTags(Result);
   if (Result != nullptr && Scope != nullptr)
     Result = make<NestedName>(Scope, Result);
+
   return Result;
 }
 
+// <module-name> ::= <module-subname>
+//     ::= <module-name> <module-subname>
+//     ::= <substitution>  # passed in by caller
+// <module-subname> ::= W <source-name>
+//        ::= W P <source-name>
+template <typename Derived, typename Alloc>
+bool AbstractManglingParser<Derived, Alloc>::parseModuleNameOpt(
+    ModuleName *&Module) {
+  while (consumeIf('W')) {
+    bool IsPartition = consumeIf('P');
+    Node *Sub = getDerived().parseSourceName(nullptr);
+    if (!Sub)
+      return true;
+    Module =
+        static_cast<ModuleName *>(make<ModuleName>(Module, Sub, IsPartition));
+    Subs.push_back(Module);
+  }
+
+  return false;
+}
+
 // <unnamed-type-name> ::= Ut [<nonnegative number>] _
 //                     ::= <closure-type-name>
 //
 // <closure-type-name> ::= Ul <lambda-sig> E [ <nonnegative number> ] _
 //
 // <lambda-sig> ::= <parameter type>+  # Parameter types or "v" if the lambda has no parameters
 template <typename Derived, typename Alloc>
 Node *
if (look() == 'T') {
       if (State)
         State->EndsWithTemplateArgs = true;
       SoFar = make<NameWithTemplateArgs>(SoFar, TA);
     } else if (look() == 'D' && (look(1) == 't' || look(1) == 'T')) {
       //          ::= <decltype>
       if (SoFar != nullptr)
         return nullptr; // Cannot have a prefix.
       SoFar = getDerived().parseDecltype();
-    } else if (look() == 'S') {
+    } else {
+      ModuleName *Module = nullptr;
+      bool IsLocal = consumeIf('L'); // extension
+
+      if (look() == 'S') {
         //          ::= <substitution>
-      if (SoFar != nullptr)
-        return nullptr; // Cannot have a prefix.
+        Node *S = nullptr;
         if (look(1) == 't') {
-        // parseSubstition does not handle 'St'.
           First += 2;
-        SoFar = make<NameType>("std");
+          S = make<NameType>("std");
         } else {
-        SoFar = getDerived().parseSubstitution();
+          S = getDerived().parseSubstitution();
         }
-      if (SoFar == nullptr)
+        if (!S)
           return nullptr;
-      continue; // Do not push a new substitution.
+        if (S->getKind() == Node::KModuleName) {
+          Module = static_cast<ModuleName *>(S);
+        } else if (SoFar != nullptr || IsLocal) {
+          return nullptr; // Cannot have a prefix.
         } else {
-      consumeIf('L'); // extension
+          SoFar = S;
+          continue; // Do not push a new substitution.
+        }
+      }
+
       //          ::= [<prefix>] <unqualified-name>
-      SoFar = getDerived().parseUnqualifiedName(State, SoFar);
+      SoFar = getDerived().parseUnqualifiedName(State, SoFar, Module);
     }
+
     if (SoFar == nullptr)
       return nullptr;
     Subs.push_back(SoFar);
 
     // No longer used.
     // <data-member-prefix> := <member source-name> [<template-args>] M
     consumeIf('M');
   }
case 'G': {
     if (P == nullptr)
       return P;
     Result = make<PostfixQualifiedType>(P, " imaginary");
     break;
   }
   //             ::= <substitution>  # See Compression below
   case 'S': {
     if (look(1) != 't') {
-      Result = getDerived().parseSubstitution();
-      if (Result == nullptr)
+      bool IsSubst = false;
+      Result = getDerived().parseUnscopedName(nullptr, &IsSubst);
+      if (!Result)
         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') {
+      if (look() == 'I' && (!IsSubst || TryToParseTemplateArgs)) {
+        if (!IsSubst)
+          Subs.push_back(Result);
         Node *TA = getDerived().parseTemplateArgs();
         if (TA == nullptr)
           return nullptr;
         Result = make<NameWithTemplateArgs>(Result, TA);
-      } else {
+      } else if (IsSubst) {
         // If all we parsed was a substitution, don't re-insert into the
         // substitution table.
         return Result;
       }
       break;
     }
     DEMANGLE_FALLTHROUGH;
   }

 //                ::= TI <type>    # typeinfo structure
 //                ::= TS <type>    # typeinfo name (null-terminated byte string)
 //                ::= Tc <call-offset> <call-offset> <base encoding>
 //                    # base is the nominal target function of thunk
 //                    # first call-offset is 'this' adjustment
 //                    # second call-offset is result adjustment
 //                ::= T <call-offset> <base encoding>
 //                    # base is the nominal target function of thunk
-//                ::= GV <object name> # Guard variable for one-time initialization
+//                # Guard variable for one-time initialization
+//                ::= GV <object name>
 //                                     # No <type>
 //                ::= TW <object name> # Thread-local wrapper
 //                ::= TH <object name> # Thread-local initialization
 //                ::= GR <object name> _             # First temporary
 //                ::= GR <object name> <seq-id> _    # Subsequent temporaries
-//      extension ::= TC <first type> <number> _ <second type> # construction vtable for second-in-first
+//                # construction vtable for second-in-first
+//      extension ::= TC <first type> <number> _ <second type>
 //      extension ::= GR <object name> # reference temporary for object
+//      extension ::= GI <module name> # module global initializer
 template <typename Derived, typename Alloc>
 Node *AbstractManglingParser<Derived, Alloc>::parseSpecialName() {
   switch (look()) {
   case 'T':
     switch (look(1)) {
     // TA <template-arg>    # template parameter object
     //
     // Not yet in the spec: https://github.com/itanium-cxx-abi/cxx-abi/issues/63
case 'R': {
       if (Name == nullptr)
         return nullptr;
       size_t Count;
       bool ParsedSeqId = !parseSeqId(&Count);
       if (!consumeIf('_') && ParsedSeqId)
         return nullptr;
       return make<SpecialName>("reference temporary for ", Name);
     }
+    // GI <module-name> v
+    case 'I': {
+      First += 2;
+      ModuleName *Module = nullptr;
+      if (getDerived().parseModuleNameOpt(Module))
+        return nullptr;
+      if (Module == nullptr)
+        return nullptr;
+      return make<SpecialName>("initializer for module ", Module);
+    }
     }
   }
   return nullptr;
 }
 
 // <encoding> ::= <function name> <bare-function-type>
 //            ::= <data name>
 //            ::= <special-name>

llvm/lib/Demangle/ItaniumDemangle.cpp

char *ItaniumPartialDemangler::getFunctionBaseName(char *Buf, size_t *N) const {
 
   const Node *Name = static_cast<const FunctionEncoding *>(RootNode)->getName();
 
   while (true) {
     switch (Name->getKind()) {
     case Node::KAbiTagAttr:
       Name = static_cast<const AbiTagAttr *>(Name)->Base;
       continue;
+    case Node::KModuleEntity:
+      Name = static_cast<const ModuleEntity *>(Name)->Name;
+      continue;
     case Node::KNestedName:
       Name = static_cast<const NestedName *>(Name)->Name;
       continue;
     case Node::KLocalName:
       Name = static_cast<const LocalName *>(Name)->Entity;
       continue;
     case Node::KNameWithTemplateArgs:
       Name = static_cast<const NameWithTemplateArgs *>(Name)->Name;
while (true) {
     }
     if (Name->getKind() == Node::KNameWithTemplateArgs) {
       Name = static_cast<const NameWithTemplateArgs *>(Name)->Name;
       continue;
     }
     break;
   }
 
+  if (Name->getKind() == Node::KModuleEntity)
+    Name = static_cast<const ModuleEntity *>(Name)->Name;
+
   switch (Name->getKind()) {
   case Node::KNestedName:
     static_cast<const NestedName *>(Name)->Qual->print(OB);
     break;
   case Node::KLocalName: {
     auto *LN = static_cast<const LocalName *>(Name);
     LN->Encoding->print(OB);
     OB += "::";
case Node::KLocalName:
       N = static_cast<const LocalName *>(N)->Entity;
       break;
     case Node::KNameWithTemplateArgs:
       N = static_cast<const NameWithTemplateArgs *>(N)->Name;
       break;
     case Node::KNestedName:
       N = static_cast<const NestedName *>(N)->Name;
       break;
+    case Node::KModuleEntity:
+      N = static_cast<const ModuleEntity *>(N)->Name;
+      break;
     }
   }
   return false;
 }
 
 bool ItaniumPartialDemangler::isFunction() const {
   assert(RootNode != nullptr && "must call partialDemangle()");
   return static_cast<const Node *>(RootNode)->getKind() ==