[demangler] Fix new/delete demangling

[urnathan]

Summary

I discovered some demangler problems:

a) parsing of new expressions was broken, ignoring any 'gs' prefix
b) (when #a is fixed) badly formatted global new expressions
c) formatting of new and delete failed to correctly add whitespace

(a) happens as parseExpr swallows the 'gs' prefix but doesn't pass it to 'parseNewExpr'. It seems simpler to me to just code the new expression parsing directly in parseExpr, as is done for delete expressions.

(b) global new should be rendered something like '::new T' not '::operator new T'

(c) is resolved by being a bit more careful with whitespace.

Best shown with some examples (don't worry that these symbols are for impossible instantiations, that's not the point):

Old behaviour:
build/bin/llvm-cxxfilt _ZN2FnIXgsnw_iEEXna_ipiLi4EEEEEvv _ZN2FnIXnwLj4E_iEEXgsnaLj4E_ipiLi4EEEEEvv _ZN2FnIXgsdlLi4EEXdaLi4EEEEvv _ZN2FnIXdlLj4EEXgsdaLj4EEEEvv
void Fn<new int, new[] int(4)>() # No ::new
void Fn<new (4u)int, new[] (4u)int(4)>() # No ::new, poor whitespace
void Fn<::delete4, delete[] 4>() # missing necessary space
void Fn<delete4u, ::delete[] 4u>() # missing necessary space

New behaviour:
build/bin/llvm-cxxfilt _ZN2FnIXgsnw_iEEXna_ipiLi4EEEEEvv _ZN2FnIXnwLj4E_iEEXgsnaLj4E_ipiLi4EEEEEvv _ZN2FnIXgsdlLi4EEXdaLi4EEEEvv _ZN2FnIXdlLj4EEXgsdaLj4EEEEvv
void Fn<::new int, new[] int(4)>()
void Fn<new(4u) int, ::new[](4u) int(4)>()
void Fn<::delete 4, delete[] 4>()
void Fn<delete 4u, ::delete[] 4u>()

Binutils' behaviour:
c++filt _ZN2FnIXgsnw_iEEXna_ipiLi4EEEEEvv _ZN2FnIXnwLj4E_iEEXgsnaLj4E_ipiLi4EEEEEvv _ZN2FnIXgsdlLi4EEXdaLi4EEEEvv _ZN2FnIXdlLj4EEXgsdaLj4EEEEvv
void Fn<::new int, new int(4)>()
void Fn<new (4u) int, ::new (4u) int(4)>()
void Fn<::delete (4), delete[] (4)>()
void Fn<delete (4u), ::delete[] (4u)>()

The fixed and binutils demanglings are the same modulo some whitespace and optional parens.

[ChuanqiXu]

libcxxabi/src/demangle/ItaniumDemangle.h

4802–4803

HaveInits is loop invariant, could we hoist the check?

4810

In case HaveInits is false and consumeIf('E') return true, the original behavior would be return make<NewExpr>(ExprList, Ty, NodeArray(), Global, IsArray);. Is the current behavior expected?

[urnathan]

libcxxabi/src/demangle/ItaniumDemangle.h

4802–4803

no, see below

4810

You're misreading the old code -- there's a negation on the non-looping consume( 'E'). There's always an 'E', it's just that without 'pi' that 'E'must be immediate (there are no expressions).

Here's the grammar -- you always reach an 'E'

[gs] nw <expression>* _ <type> E # new (expr-list) type
[gs] nw <expression>* _ <type> <initializer> # new (expr-list) type (init)
[gs] na <expression>* _ <type> E # new[] (expr-list) type
[gs] na <expression>* _ <type> <initializer> # new[] (expr-list) type (init)
// <initializer> ::= pi <expression>* E # parenthesized initialization

(Not sure why the 'pi' initializer introducer is needed, probably history.)

OLD:
if ('pi') { while not 'E' {read expr; } build newexpr (exprs)
else if not 'E'; fail
else build newexpr ();

NEW:
haveinits = 'pi';
while not 'E' { if !haveinits; fail, else read expr }
build newexpr (exprs)

[urnathan]

libcxxabi/src/demangle/ItaniumDemangle.h

4810

oh, of course 'pi' is needed as 'new int' and 'new int ()' are different. Not sure why 'new int {}' is not representable, perhaps no one's got there yet?

[ChuanqiXu]

libcxxabi/src/demangle/ItaniumDemangle.h

4810

Yeah, the point here is if 'pi' is not true, then there must be an immediate 'E'. Then the code makes sense. It is a little surprising to me that the parser of demangler wouldn't handle the wrong case. Maybe the basic assumption is that the input is valid.

For the case of 'new int {}', I guess it is represented as there are multiple <expression> between pi and 'E'.

[urnathan]

libcxxabi/src/demangle/ItaniumDemangle.h

4810

I'm not sure I follow about 'wouldn't handle the wrong case'. The parser should definitely not assume the input is valid. What invalid input have I missed?

[ChuanqiXu]

libcxxabi/src/demangle/ItaniumDemangle.h

4810

I mean the assumption: "There's always an 'E'. And without 'pi' that 'E' must be immediate". I think we get the conclusion from the grammar. But my question is "what if the input doesn't follow the grammar". Like there is not an immediate 'E' if 'p' is not presented.

[urnathan]

libcxxabi/src/demangle/ItaniumDemangle.h

4810

Yes, the grammar at this point permits either 'E' or 'pi' <expressions>* 'E' to appear. If we don't get 'pi' then HaveInits will be false. If we then don't get 'E' we'll enter the loop, and that will return nullptr as HaveInits is false. I don;t see a problem.

[ChuanqiXu]

libcxxabi/src/demangle/ItaniumDemangle.h

4810

Yeah, this is what I say about handling invalid input. If this is the policy or what demangler always tries to do, I have no problem.

libcxxabi/src/demangle/ItaniumDemangle.h

NewExpr(NodeArray ExprList_, Node *Type_, NodeArray InitList_, bool IsGlobal_,
         IsGlobal(IsGlobal_), IsArray(IsArray_) {}
 
   template<typename Fn> void match(Fn F) const {
     F(ExprList, Type, InitList, IsGlobal, IsArray);
   }
 
   void printLeft(OutputBuffer &OB) const override {
     if (IsGlobal)
-      OB += "::operator ";
+      OB += "::";
     OB += "new";
     if (IsArray)
       OB += "[]";
-    OB += ' ';
     if (!ExprList.empty()) {
       OB += "(";
       ExprList.printWithComma(OB);
       OB += ")";
     }
+    OB += ' ';
     Type->print(OB);
     if (!InitList.empty()) {
       OB += "(";
       InitList.printWithComma(OB);
       OB += ")";
     }
   }
 };
public:
 
   template<typename Fn> void match(Fn F) const { F(Op, IsGlobal, IsArray); }
 
   void printLeft(OutputBuffer &OB) const override {
     if (IsGlobal)
       OB += "::";
     OB += "delete";
     if (IsArray)
-      OB += "[] ";
+      OB += "[]";
+    OB += ' ';
     Op->print(OB);
   }
 };
 
 class PrefixExpr : public Node {
   StringView Prefix;
   Node *Child;
 
template <typename Derived, typename Alloc> struct AbstractManglingParser {
   /// Parse the <expr> production.
   Node *parseExpr();
   Node *parsePrefixExpr(StringView Kind);
   Node *parseBinaryExpr(StringView Kind);
   Node *parseIntegerLiteral(StringView Lit);
   Node *parseExprPrimary();
   template <class Float> Node *parseFloatingLiteral();
   Node *parseFunctionParam();
-  Node *parseNewExpr();
   Node *parseConversionExpr();
   Node *parseBracedExpr();
   Node *parseFoldExpr();
   Node *parsePointerToMemberConversionExpr();
   Node *parseSubobjectExpr();
 
   /// Parse the <type> production.
   Node *parseType();
if (consumeIf("fL")) {
     StringView Num = parseNumber();
     if (!consumeIf('_'))
       return nullptr;
     return make<FunctionParam>(Num);
   }
   return nullptr;
 }
 
-// [gs] nw <expression>* _ <type> E                     # new (expr-list) type
-// [gs] nw <expression>* _ <type> <initializer>         # new (expr-list) type (init)
-// [gs] na <expression>* _ <type> E                     # new[] (expr-list) type
-// [gs] na <expression>* _ <type> <initializer>         # new[] (expr-list) type (init)
-// <initializer> ::= pi <expression>* E                 # parenthesized initialization
-template <typename Derived, typename Alloc>
-Node *AbstractManglingParser<Derived, Alloc>::parseNewExpr() {
-  bool Global = consumeIf("gs");
-  bool IsArray = look(1) == 'a';
-  if (!consumeIf("nw") && !consumeIf("na"))
-    return nullptr;
-  size_t Exprs = Names.size();
-  while (!consumeIf('_')) {
-    Node *Ex = getDerived().parseExpr();
-    if (Ex == nullptr)
-      return nullptr;
-    Names.push_back(Ex);
-  }
-  NodeArray ExprList = popTrailingNodeArray(Exprs);
-  Node *Ty = getDerived().parseType();
-  if (Ty == nullptr)
-    return Ty;
-  if (consumeIf("pi")) {
-    size_t InitsBegin = Names.size();
-    while (!consumeIf('E')) {
-      Node *Init = getDerived().parseExpr();
-      if (Init == nullptr)
-        return Init;
-      Names.push_back(Init);
-    }
-    NodeArray Inits = popTrailingNodeArray(InitsBegin);
-    return make<NewExpr>(ExprList, Ty, Inits, Global, IsArray);
-  } else if (!consumeIf('E'))
-    return nullptr;
-  return make<NewExpr>(ExprList, Ty, NodeArray(), Global, IsArray);
-}
-
 // cv <type> <expression>                               # conversion with one argument
 // cv <type> _ <expression>* E                          # conversion with a different number of arguments
 template <typename Derived, typename Alloc>
 Node *AbstractManglingParser<Derived, Alloc>::parseConversionExpr() {
   if (!consumeIf("cv"))
     return nullptr;
   Node *Ty;
   {
case 'm':
       if (Ex == nullptr)
         return nullptr;
       return make<PostfixExpr>(Ex, "--");
     }
     return nullptr;
   case 'n':
     switch (First[1]) {
     case 'a':
-    case 'w':
-      return getDerived().parseNewExpr();
+    case 'w': {
+      // [gs] nw <expression>* _ <type> [pi <expression>*] E   # new (expr-list) type [(init)]
+      // [gs] na <expression>* _ <type> [pi <expression>*] E   # new[] (expr-list) type [(init)]
+      bool IsArray = First[1] == 'a';
+      First += 2;
+      size_t Exprs = Names.size();
+      while (!consumeIf('_')) {
+        Node *Ex = getDerived().parseExpr();
+        if (Ex == nullptr)
+          return nullptr;
+        Names.push_back(Ex);
+      }
+      NodeArray ExprList = popTrailingNodeArray(Exprs);
+      Node *Ty = getDerived().parseType();
+      if (Ty == nullptr)
+        return nullptr;
+      bool HaveInits = consumeIf("pi");
+      size_t InitsBegin = Names.size();
+      while (!consumeIf('E')) {
+        if (!HaveInits)
+          return nullptr;
+        Node *Init = getDerived().parseExpr();
+        if (Init == nullptr)
+          return Init;
+        Names.push_back(Init);
+      }
+      NodeArray Inits = popTrailingNodeArray(InitsBegin);
+      return make<NewExpr>(ExprList, Ty, Inits, Global, IsArray);
+    }
     case 'e':
       First += 2;
       return getDerived().parseBinaryExpr("!=");
     case 'g':
       First += 2;
       return getDerived().parsePrefixExpr("-");
     case 't':
       First += 2;

libcxxabi/test/test_demangle.pass.cpp

//    {"_Z1fM1XRFivEMS_OFivEMS_KOFivE", "f(int (X::*)() &, int (X::*)() &&, int (X::*)() const &&)"},
     {"_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<><>"},
 
     {"_ZN2FnIXgs4BaseEX4BaseEEEvv","void Fn<::Base, Base>()"},
     
+    {"_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)"},
 };
 
 const unsigned N = sizeof(cases) / sizeof(cases[0]);
 
 struct FPLiteralCase {
     const char *mangled;
     // There are four possible demanglings of a given float.

llvm/include/llvm/Demangle/ItaniumDemangle.h

NewExpr(NodeArray ExprList_, Node *Type_, NodeArray InitList_, bool IsGlobal_,
         IsGlobal(IsGlobal_), IsArray(IsArray_) {}
 
   template<typename Fn> void match(Fn F) const {
     F(ExprList, Type, InitList, IsGlobal, IsArray);
   }
 
   void printLeft(OutputBuffer &OB) const override {
     if (IsGlobal)
-      OB += "::operator ";
+      OB += "::";
     OB += "new";
     if (IsArray)
       OB += "[]";
-    OB += ' ';
     if (!ExprList.empty()) {
       OB += "(";
       ExprList.printWithComma(OB);
       OB += ")";
     }
+    OB += ' ';
     Type->print(OB);
     if (!InitList.empty()) {
       OB += "(";
       InitList.printWithComma(OB);
       OB += ")";
     }
   }
 };
public:
 
   template<typename Fn> void match(Fn F) const { F(Op, IsGlobal, IsArray); }
 
   void printLeft(OutputBuffer &OB) const override {
     if (IsGlobal)
       OB += "::";
     OB += "delete";
     if (IsArray)
-      OB += "[] ";
+      OB += "[]";
+    OB += ' ';
     Op->print(OB);
   }
 };
 
 class PrefixExpr : public Node {
   StringView Prefix;
   Node *Child;
 
template <typename Derived, typename Alloc> struct AbstractManglingParser {
   /// Parse the <expr> production.
   Node *parseExpr();
   Node *parsePrefixExpr(StringView Kind);
   Node *parseBinaryExpr(StringView Kind);
   Node *parseIntegerLiteral(StringView Lit);
   Node *parseExprPrimary();
   template <class Float> Node *parseFloatingLiteral();
   Node *parseFunctionParam();
-  Node *parseNewExpr();
   Node *parseConversionExpr();
   Node *parseBracedExpr();
   Node *parseFoldExpr();
   Node *parsePointerToMemberConversionExpr();
   Node *parseSubobjectExpr();
 
   /// Parse the <type> production.
   Node *parseType();
if (consumeIf("fL")) {
     StringView Num = parseNumber();
     if (!consumeIf('_'))
       return nullptr;
     return make<FunctionParam>(Num);
   }
   return nullptr;
 }
 
-// [gs] nw <expression>* _ <type> E                     # new (expr-list) type
-// [gs] nw <expression>* _ <type> <initializer>         # new (expr-list) type (init)
-// [gs] na <expression>* _ <type> E                     # new[] (expr-list) type
-// [gs] na <expression>* _ <type> <initializer>         # new[] (expr-list) type (init)
-// <initializer> ::= pi <expression>* E                 # parenthesized initialization
-template <typename Derived, typename Alloc>
-Node *AbstractManglingParser<Derived, Alloc>::parseNewExpr() {
-  bool Global = consumeIf("gs");
-  bool IsArray = look(1) == 'a';
-  if (!consumeIf("nw") && !consumeIf("na"))
-    return nullptr;
-  size_t Exprs = Names.size();
-  while (!consumeIf('_')) {
-    Node *Ex = getDerived().parseExpr();
-    if (Ex == nullptr)
-      return nullptr;
-    Names.push_back(Ex);
-  }
-  NodeArray ExprList = popTrailingNodeArray(Exprs);
-  Node *Ty = getDerived().parseType();
-  if (Ty == nullptr)
-    return Ty;
-  if (consumeIf("pi")) {
-    size_t InitsBegin = Names.size();
-    while (!consumeIf('E')) {
-      Node *Init = getDerived().parseExpr();
-      if (Init == nullptr)
-        return Init;
-      Names.push_back(Init);
-    }
-    NodeArray Inits = popTrailingNodeArray(InitsBegin);
-    return make<NewExpr>(ExprList, Ty, Inits, Global, IsArray);
-  } else if (!consumeIf('E'))
-    return nullptr;
-  return make<NewExpr>(ExprList, Ty, NodeArray(), Global, IsArray);
-}
-
 // cv <type> <expression>                               # conversion with one argument
 // cv <type> _ <expression>* E                          # conversion with a different number of arguments
 template <typename Derived, typename Alloc>
 Node *AbstractManglingParser<Derived, Alloc>::parseConversionExpr() {
   if (!consumeIf("cv"))
     return nullptr;
   Node *Ty;
   {
case 'm':
       if (Ex == nullptr)
         return nullptr;
       return make<PostfixExpr>(Ex, "--");
     }
     return nullptr;
   case 'n':
     switch (First[1]) {
     case 'a':
-    case 'w':
-      return getDerived().parseNewExpr();
+    case 'w': {
+      // [gs] nw <expression>* _ <type> [pi <expression>*] E   # new (expr-list) type [(init)]
+      // [gs] na <expression>* _ <type> [pi <expression>*] E   # new[] (expr-list) type [(init)]
+      bool IsArray = First[1] == 'a';
+      First += 2;
+      size_t Exprs = Names.size();
+      while (!consumeIf('_')) {
+        Node *Ex = getDerived().parseExpr();
+        if (Ex == nullptr)
+          return nullptr;
+        Names.push_back(Ex);
+      }
+      NodeArray ExprList = popTrailingNodeArray(Exprs);
+      Node *Ty = getDerived().parseType();
+      if (Ty == nullptr)
+        return nullptr;
+      bool HaveInits = consumeIf("pi");
+      size_t InitsBegin = Names.size();
+      while (!consumeIf('E')) {
+        if (!HaveInits)
+          return nullptr;
+        Node *Init = getDerived().parseExpr();
+        if (Init == nullptr)
+          return Init;
+        Names.push_back(Init);
+      }
+      NodeArray Inits = popTrailingNodeArray(InitsBegin);
+      return make<NewExpr>(ExprList, Ty, Inits, Global, IsArray);
+    }
     case 'e':
       First += 2;
       return getDerived().parseBinaryExpr("!=");
     case 'g':
       First += 2;
       return getDerived().parsePrefixExpr("-");
     case 't':
       First += 2;