namescopepiece-node.diff

diff --git a/llvm/include/llvm/Demangle/MicrosoftDemangle.h b/llvm/include/llvm/Demangle/MicrosoftDemangle.h
index c6f26061bed..96d015f2ded 100644
--- a/llvm/include/llvm/Demangle/MicrosoftDemangle.h
+++ b/llvm/include/llvm/Demangle/MicrosoftDemangle.h
@@ -202,7 +202,7 @@ private:
 
   QualifiedNameNode *demangleNameScopeChain(StringView &MangledName,
                                             IdentifierNode *UnqualifiedName);
-  IdentifierNode *demangleNameScopePiece(StringView &MangledName);
+  Node *demangleNameScopePiece(StringView &MangledName);
 
   NamedIdentifierNode *demangleBackRefName(StringView &MangledName);
   IdentifierNode *demangleTemplateInstantiationName(StringView &MangledName,
@@ -238,7 +238,8 @@ private:
   NamedIdentifierNode *demangleSimpleName(StringView &MangledName,
                                           bool Memorize);
   NamedIdentifierNode *demangleAnonymousNamespaceName(StringView &MangledName);
-  NamedIdentifierNode *demangleLocallyScopedNamePiece(StringView &MangledName);
+  LocallyScopedNamePieceNode *
+  demangleLocallyScopedNamePiece(StringView &MangledName);
   EncodedStringLiteralNode *demangleStringLiteral(StringView &MangledName);
   FunctionSymbolNode *demangleVcallThunkNode(StringView &MangledName);
 
diff --git a/llvm/include/llvm/Demangle/MicrosoftDemangleNodes.h b/llvm/include/llvm/Demangle/MicrosoftDemangleNodes.h
index 81b279fe237..939a735fd51 100644
--- a/llvm/include/llvm/Demangle/MicrosoftDemangleNodes.h
+++ b/llvm/include/llvm/Demangle/MicrosoftDemangleNodes.h
@@ -250,7 +250,8 @@ enum class NodeKind {
   LocalStaticGuardVariable,
   FunctionSymbol,
   VariableSymbol,
-  SpecialTableSymbol
+  SpecialTableSymbol,
+  LocallyScopedNamePiece,
 };
 
 struct Node {
@@ -294,6 +295,7 @@ struct SymbolNode;
 struct FunctionSymbolNode;
 struct VariableSymbolNode;
 struct SpecialTableSymbolNode;
+struct LocallyScopedNamePieceNode;
 
 struct TypeNode : public Node {
   explicit TypeNode(NodeKind K) : Node(K) {}
@@ -587,6 +589,16 @@ struct SpecialTableSymbolNode : public SymbolNode {
   Qualifiers Quals;
 };
 
+struct LocallyScopedNamePieceNode : public Node {
+  LocallyScopedNamePieceNode(uint64_t Number, Node *Scope)
+      : Node(NodeKind::LocallyScopedNamePiece), Number(Number), Scope(Scope) {}
+
+  void output(OutputStream &OS, OutputFlags Flags) const override;
+
+  uint64_t Number;
+  Node* Scope;
+};
+
 struct LocalStaticGuardVariableNode : public SymbolNode {
   LocalStaticGuardVariableNode()
       : SymbolNode(NodeKind::LocalStaticGuardVariable) {}
diff --git a/llvm/lib/Demangle/MicrosoftDemangle.cpp b/llvm/lib/Demangle/MicrosoftDemangle.cpp
index c681d6e25b8..7b02c114331 100644
--- a/llvm/lib/Demangle/MicrosoftDemangle.cpp
+++ b/llvm/lib/Demangle/MicrosoftDemangle.cpp
@@ -1427,11 +1427,10 @@ Demangler::demangleAnonymousNamespaceName(StringView &MangledName) {
   return Node;
 }
 
-NamedIdentifierNode *
+LocallyScopedNamePieceNode *
 Demangler::demangleLocallyScopedNamePiece(StringView &MangledName) {
   assert(startsWithLocalScopePattern(MangledName));
 
-  NamedIdentifierNode *Identifier = Arena.alloc<NamedIdentifierNode>();
   MangledName.consumeFront('?');
   uint64_t Number = 0;
   bool IsNegative = false;
@@ -1445,21 +1444,7 @@ Demangler::demangleLocallyScopedNamePiece(StringView &MangledName) {
   Node *Scope = parse(MangledName);
   if (Error)
     return nullptr;
-
-  // Render the parent symbol's name into a buffer.
-  OutputStream OS;
-  if (!initializeOutputStream(nullptr, nullptr, OS, 1024))
-    // FIXME: Propagate out-of-memory as an error?
-    std::terminate();
-  OS << '`';
-  Scope->output(OS, OF_Default);
-  OS << '\'';
-  OS << "::`" << Number << "'";
-  OS << '\0';
-  char *Result = OS.getBuffer();
-  Identifier->Name = copyString(Result);
-  std::free(Result);
-  return Identifier;
+  return Arena.alloc<LocallyScopedNamePieceNode>(Number, Scope);
 }
 
 // Parses a type name in the form of A@B@C@@ which represents C::B::A.
@@ -1505,6 +1490,10 @@ Demangler::demangleFullyQualifiedSymbolName(StringView &MangledName) {
     StructorIdentifierNode *SIN =
         static_cast<StructorIdentifierNode *>(Identifier);
     Node *ClassNode = QN->Components->Nodes[QN->Components->Count - 2];
+    if (ClassNode->kind() != NodeKind::Identifier) {
+      Error = true;
+      return nullptr;
+    }
     SIN->Class = static_cast<IdentifierNode *>(ClassNode);
   }
   assert(QN);
@@ -1538,7 +1527,7 @@ Demangler::demangleUnqualifiedSymbolName(StringView &MangledName,
   return demangleSimpleName(MangledName, /*Memorize=*/(NBB & NBB_Simple) != 0);
 }
 
-IdentifierNode *Demangler::demangleNameScopePiece(StringView &MangledName) {
+Node *Demangler::demangleNameScopePiece(StringView &MangledName) {
   if (startsWithDigit(MangledName))
     return demangleBackRefName(MangledName);
 
@@ -1586,7 +1575,7 @@ Demangler::demangleNameScopeChain(StringView &MangledName,
     }
 
     assert(!Error);
-    IdentifierNode *Elem = demangleNameScopePiece(MangledName);
+    Node *Elem = demangleNameScopePiece(MangledName);
     if (Error)
       return nullptr;
 
diff --git a/llvm/lib/Demangle/MicrosoftDemangleNodes.cpp b/llvm/lib/Demangle/MicrosoftDemangleNodes.cpp
index 9cee975231a..42974cd4446 100644
--- a/llvm/lib/Demangle/MicrosoftDemangleNodes.cpp
+++ b/llvm/lib/Demangle/MicrosoftDemangleNodes.cpp
@@ -649,5 +649,12 @@ void SpecialTableSymbolNode::output(OutputStream &OS, OutputFlags Flags) const {
     TargetName->output(OS, Flags);
     OS << "'}";
   }
-  return;
+}
+
+void LocallyScopedNamePieceNode::output(OutputStream &OS,
+                                        OutputFlags Flags) const {
+  OS << '`';
+  Scope->output(OS, Flags);
+  OS << '\'';
+  OS << "::`" << Number << "'";
 }
diff --git a/test.py b/test.py
new file mode 100755
index 00000000000..7e9c5dc74ba
--- /dev/null
+++ b/test.py
@@ -0,0 +1,47 @@
+#!/usr/bin/env python
+import re
+from subprocess import Popen, PIPE
+
+def sizeof_fmt(num, suffix='B'):
+    for unit in ['','Ki','Mi','Gi','Ti','Pi','Ei','Zi']:
+        if abs(num) < 1024.0:
+            return "%3.1f%s%s" % (num, unit, suffix)
+        num /= 1024.0
+    return "%.1f%s%s" % (num, 'Yi', suffix)
+
+# clang-cl prints strings like this for
+# extern int e();
+# void f() {
+#   ^{ [...] ^{ static int i = e(); }(); [...] }();
+# }
+# where [...] and [...] are N repetitions of `^{` and `}();`.
+#s = '?i@' + n * '?1??foo@@YAXXZ' + '@4HA'
+# ...however, here the recursive parse call always just returns 37 bytes
+# which is boring.
+
+# The below can't be produced by compilers as far as I know,
+# but it causes n^2 memory use in theory.
+#s = '?i@' + n*'?1??foo@' + n*'@4HA' + '@4HA'
+
+with open('tmp.txt', 'w') as f:
+  n = 10000
+  f.write('?i@' + n*'?1??foo@' + n*'@4HA' + '@4HA')
+
+
+# ?i@                        @4HA
+# ?i@?1??foo@            @4HA@4HA
+# ?i@?1??foo@?1??foo@@4HA@4HA@4HA
+
+n = 1000
+while n <= 100000000:
+    #s = '?i@' + n * '?1??foo@@YAXXZ' + '@4HA'
+    s = '?i@' + n*'?1??foo@' + n*'@4HA' + '@4HA'
+    p = Popen(['/usr/bin/time', '-l', 'out/gn/bin/llvm-undname'],
+              stdin=PIPE, stdout=PIPE, stderr=PIPE)
+    p.stdin.write(s)
+    stdout, stderr = p.communicate()
+    p.stdin.close()
+    t = float(re.search(r'(\d+\.\d+) real', stderr).group(1))
+    mem = int(re.search(r'(\d+)  maximum resident set size', stderr).group(1))
+    print n, t, sizeof_fmt(mem)
+    n *= 10