[libcxxabi][demangler] Improve handling of variadic templates

[erik.pilkington]

Summary

This patch fixes some longstanding bugs in the demangler to do with it's handling of variadic templates.

Currently the demangler handles variadic templates by expanding them into the Names stack. A parse_* function can succeed and add 0 or more Node*s to the stack. Each production that can consume a variadic template was responsible for looping over all the names it parsed, and transforming the stack. Although its possible for a pack to appear in almost every production, most productions didn't implement this loop (all but pointer and reference types). The current demangler also doesn't respect "Dp" and "sp" productions, which correspond to pack expansions in type and expression contexts. It ignores these pack expansions, and just eagerly expands the pack in the nearest context where it would be possible. For example, we misdemangle the following:

template <class> struct unary {};
template <class... Ts> void f(unary<Ts>...) {}
template void f<int, char, float>(unary<int>, unary<char>, unary<float>);
// clang mangles to _Z1fIJicfEEvDp5unaryIT_E

The demangler misdemangles this symbol into:

void f<int, char, float>(unary<int, char, float>)

I think the best way to handle the Dp & sp productions is to parse an unexpanded AST, then expand it whenever we encounter the Dp/sp. One way of implementing this might be to do a recursive TreeTransform-like traversal of the AST, but we would have to do a bunch of allocations for all the expanded nodes and it would be pretty complex. This patch does the expanding during printing, by reusing the unexpanded AST. This also automatically gives us support for PackExpansions everywhere in the grammar. Most of the churn in this patch has to do with propagating up the the pack size and some other metadata as the AST is being constructed.

This patch also introduces a nice feature: Every parse_* function now either fails, or returns exactly 1 Node. I'm going to use this to clean up the parser a bit.

Thanks for taking a look!
Erik

[erik.pilkington]

src/cxa_demangle.cpp

130 ↗

(On Diff #129094)

This caching API is being removed because it is no longer valid: if a node has an unexpanded parameter pack it can generate multiple different strings.

1599 ↗

(On Diff #129094)

This type was an optimization that flattened the previously 2d vector of substitutions (index * pack) into two 1d vectors. Now that packs are represented with a single Node*, we can replace it with a simple vector.

test/test_demangle.pass.cpp

29607 ↗

(On Diff #129094)

I just generated this symbol by hand because I couldn't get clang to do it without crashing. Turns out I forgot the Dp!

[erik.pilkington]

Ping!

[dexonsmith]

Thanks for working on this!

src/cxa_demangle.cpp

260–261 ↗

(On Diff #129094)

Why is this behind #if 0? Should you just use something like LLVM_DUMP_METHOD?

604 ↗

(On Diff #129094)

I'd rather style changes like this were separated out into NFC commits (pre or post), since they make it hard to see what actually changed.

1412–1414 ↗

(On Diff #129094)

This seems like a super-common sequence in constructors of subclasses of Node. Can you pull out a common subclass of Node (say, CachingNode)?

test/test_demangle.pass.cpp

29607 ↗

(On Diff #129094)

Why was it crashing? (Did you file a bug?)

[erik.pilkington]

In this new patch:

• Make the cached values use a 3-way bool type, and default it to false. This simplifies all the Node ctors.
• Remove some minor style fixes to clean up the diff.

[erik.pilkington]

src/cxa_demangle.cpp

260–261 ↗

(On Diff #129094)

Do you mean conditionally defined based on NDEBUG and marked attribute((noinline,used)) for debuggers? I was just using it as a quick & simple little helper for debugging.

1412–1414 ↗

(On Diff #129094)

I had a hard time finding a nice way of abstracting the cache from the individual ctors, they all need to set it up based on their parameters. The new patch just defaults to setting the three cached values to false, with each ctor overriding when necessary. This gets rid of a lot of the duplication.

test/test_demangle.pass.cpp

29607 ↗

(On Diff #129094)

Yep, I filed https://bugs.llvm.org/show_bug.cgi?id=33092 to track this at the time. I didn't really look too far into the crash, but it seems pretty low-priority.

[dexonsmith]

LGTM once you clean up the #if 0.

src/cxa_demangle.cpp

260–261 ↗

(On Diff #129094)

Yup, those two things sound great to me. You might need some platform-specific logic to define the attributes correctly.

I figured it was a quick and simple helper, like the dump() methods throughout LLVM. Here's why I think you should change it:

• I imagine this will be useful in the future, too, and being able to call dump() from the debugger without recompiling is a great feature.
• #if 0s render as comments in some editors, and then bitrot because no one compiles them.

libcxxabi/trunk/src/cxa_demangle.cpp

 //===-------------------------- cxa_demangle.cpp --------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is dual licensed under the MIT and the University of Illinois Open
 // Source Licenses. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 // FIXME: (possibly) incomplete list of features that clang mangles that this
 // file does not yet support:
 //   - enable_if attribute
-//   - decomposition declarations
 //   - C++ modules TS
+//   - All C++14 and C++17 features
 
 #define _LIBCPP_NO_EXCEPTIONS
 
 #include "__cxxabi_config.h"
 
 #include <vector>
 #include <algorithm>
 #include <numeric>
+#include <cassert>
 #include <cstdio>
 #include <cstdlib>
 #include <cstring>
 #include <cctype>
 
 #ifdef _MSC_VER
 // snprintf is implemented in VS 2015
 #if _MSC_VER < 1900
 #define snprintf _snprintf_s
 #endif
 #endif
 
-namespace __cxxabiv1
-{
-
-namespace
-{
+#ifndef NDEBUG
+#if __has_attribute(noinline) && __has_attribute(used)
+#define DUMP_METHOD __attribute__((noinline,used))
+#else
+#define DUMP_METHOD
+#endif
+#endif
 
-enum
-{
-    unknown_error = -4,
-    invalid_args = -3,
-    invalid_mangled_name,
-    memory_alloc_failure,
-    success
-};
+namespace {
 
 class StringView {
   const char *First;
   const char *Last;
 
 public:
   template <size_t N>
   StringView(const char (&Str)[N]) : First(Str), Last(Str + N - 1) {}
bool startsWith(StringView Str) const {
     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; }
 };
 
 bool operator==(const StringView &LHS, const StringView &RHS) {
   return LHS.size() == RHS.size() &&
          std::equal(LHS.begin(), LHS.end(), RHS.begin());
 }
 
 // Stream that AST nodes write their string representation into after the AST
if (N + CurrentPosition >= BufferCapacity) {
       Buffer = static_cast<char *>(std::realloc(Buffer, BufferCapacity));
     }
   }
 
 public:
   OutputStream(char *StartBuf, size_t Size)
       : Buffer(StartBuf), CurrentPosition(0), BufferCapacity(Size) {}
 
+  /// If a ParameterPackExpansion (or similar type) is encountered, the offset
+  /// into the pack that we're currently printing.
+  unsigned CurrentPackIndex = std::numeric_limits<unsigned>::max();
+
   OutputStream &operator+=(StringView R) {
     size_t Size = R.size();
     if (Size == 0)
       return *this;
     grow(Size);
     memmove(Buffer + CurrentPosition, R.begin(), Size);
     CurrentPosition += Size;
     return *this;
   }
 
   OutputStream &operator+=(char C) {
     grow(1);
     Buffer[CurrentPosition++] = C;
     return *this;
   }
 
-  // Offset of position in buffer, used for building stream_string_view.
-  typedef unsigned StreamPosition;
-
-  // StringView into a stream, used for caching the ast nodes.
-  class StreamStringView {
-    StreamPosition First, Last;
-
-    friend class OutputStream;
-
-  public:
-    StreamStringView() : First(0), Last(0) {}
-
-    StreamStringView(StreamPosition First_, StreamPosition Last_)
-        : First(First_), Last(Last_) {}
-
-    bool empty() const { return First == Last; }
-  };
-
-  OutputStream &operator+=(StreamStringView &s) {
-    size_t Sz = static_cast<size_t>(s.Last - s.First);
-    if (Sz == 0)
-      return *this;
-    grow(Sz);
-    memmove(Buffer + CurrentPosition, Buffer + s.First, Sz);
-    CurrentPosition += Sz;
-    return *this;
-  }
-
-  StreamPosition getCurrentPosition() const {
-    return static_cast<StreamPosition>(CurrentPosition);
-  }
-
-  StreamStringView makeStringViewFromPastPosition(StreamPosition Pos) {
-    return StreamStringView(Pos, getCurrentPosition());
-  }
+  size_t getCurrentPosition() const { return CurrentPosition; };
 
   char back() const {
     return CurrentPosition ? Buffer[CurrentPosition - 1] : '\0';
   }
 
   bool empty() const { return CurrentPosition == 0; }
 
   char *getBuffer() { return Buffer; }
   char *getBufferEnd() { return Buffer + CurrentPosition - 1; }
   size_t getBufferCapacity() { return BufferCapacity; }
 };
 
+template <class T>
+class SwapAndRestore {
+  T &Restore;
+  T OriginalValue;
+public:
+  SwapAndRestore(T& Restore_, T NewVal)
+      : Restore(Restore_), OriginalValue(Restore) {
+    Restore = std::move(NewVal);
+  }
+  ~SwapAndRestore() { Restore = std::move(OriginalValue); }
+
+  SwapAndRestore(const SwapAndRestore &) = delete;
+  SwapAndRestore &operator=(const SwapAndRestore &) = delete;
+};
+
 // Base class of all AST nodes. The AST is built by the parser, then is
 // traversed by the printLeft/Right functions to produce a demangled string.
 class Node {
 public:
   enum Kind : unsigned char {
     KDotSuffix,
     KVendorExtQualType,
     KQualType,
     KConversionOperatorType,
     KPostfixQualifiedType,
     KNameType,
     KAbiTagAttr,
     KObjCProtoName,
     KPointerType,
     KLValueReferenceType,
     KRValueReferenceType,
     KPointerToMemberType,
     KArrayType,
     KFunctionType,
-    KTopLevelFunctionDecl,
+    KFunctionEncoding,
     KFunctionQualType,
     KFunctionRefQualType,
     KLiteralOperator,
     KSpecialName,
     KCtorVtableSpecialName,
     KQualifiedName,
     KEmptyName,
     KVectorType,
-    KTemplateParams,
+    KParameterPack,
+    KTemplateArgumentPack,
+    KParameterPackExpansion,
+    KTemplateArgs,
     KNameWithTemplateArgs,
     KGlobalQualifiedName,
     KStdQualifiedName,
     KExpandedSpecialSubstitution,
     KSpecialSubstitution,
     KCtorDtorName,
     KDtorName,
     KUnnamedTypeName,
     KLambdaTypeName,
     KExpr,
   };
 
-  const Kind K;
+  static constexpr unsigned NoParameterPack =
+    std::numeric_limits<unsigned>::max();
+  unsigned ParameterPackSize = NoParameterPack;
+
+  Kind K;
+
+  /// Three-way bool to track a cached value. Unknown is possible if this node
+  /// has an unexpanded parameter pack below it that may affect this cache.
+  enum class Cache : unsigned char { Yes, No, Unknown, };
+
+  /// Tracks if this node has a component on its right side, in which case we
+  /// need to call printRight.
+  Cache RHSComponentCache;
+
+  /// Track if this node is a (possibly qualified) array type. This can affect
+  /// how we format the output string.
+  Cache ArrayCache;
+
+  /// Track if this node is a (possibly qualified) function type. This can
+  /// affect how we format the output string.
+  Cache FunctionCache;
+
+  Node(Kind K_, unsigned ParameterPackSize_ = NoParameterPack,
+       Cache RHSComponentCache_ = Cache::No, Cache ArrayCache_ = Cache::No,
+       Cache FunctionCache_ = Cache::No)
+      : ParameterPackSize(ParameterPackSize_), K(K_),
+        RHSComponentCache(RHSComponentCache_), ArrayCache(ArrayCache_),
+        FunctionCache(FunctionCache_) {}
+
+  bool containsUnexpandedParameterPack() const {
+    return ParameterPackSize != NoParameterPack;
+  }
+
+  bool hasRHSComponent(OutputStream &S) const {
+    if (RHSComponentCache != Cache::Unknown)
+      return RHSComponentCache == Cache::Yes;
+    return hasRHSComponentSlow(S);
+  }
+
+  bool hasArray(OutputStream &S) const {
+    if (ArrayCache != Cache::Unknown)
+      return ArrayCache == Cache::Yes;
+    return hasArraySlow(S);
+  }
+
+  bool hasFunction(OutputStream &S) const {
+    if (FunctionCache != Cache::Unknown)
+      return FunctionCache == Cache::Yes;
+    return hasFunctionSlow(S);
+  }
+
+  Kind getKind() const { return K; }
+
+  virtual bool hasRHSComponentSlow(OutputStream &) const { return false; }
+  virtual bool hasArraySlow(OutputStream &) const { return false; }
+  virtual bool hasFunctionSlow(OutputStream &) const { return false; }
 
-private:
-  // If this Node has any RHS part, potentally many Nodes further down.
-  const unsigned HasRHSComponent : 1;
-  const unsigned HasFunction : 1;
-  const unsigned HasArray : 1;
-
-public:
-  Node(Kind K_, bool HasRHS_ = false, bool HasFunction_ = false,
-       bool HasArray_ = false)
-      : K(K_), HasRHSComponent(HasRHS_), HasFunction(HasFunction_),
-        HasArray(HasArray_) {}
-
-  bool hasRHSComponent() const { return HasRHSComponent; }
-  bool hasArray() const { return HasArray; }
-  bool hasFunction() const { return HasFunction; }
-
-  void print(OutputStream &s) const {
-    printLeft(s);
-    if (hasRHSComponent())
-      printRight(s);
+  /// If this node is a pack expansion that expands to 0 elements. This can have
+  /// an effect on how we should format the output.
+  bool isEmptyPackExpansion() const;
+
+  void print(OutputStream &S) const {
+    printLeft(S);
+    if (RHSComponentCache != Cache::No)
+      printRight(S);
   }
 
   // Print the "left" side of this Node into OutputStream.
   virtual void printLeft(OutputStream &) const = 0;
 
   // Print the "right". This distinction is necessary to represent C++ types
   // that appear on the RHS of their subtype, such as arrays or functions.
   // Since most types don't have such a component, provide a default
   // implemenation.
   virtual void printRight(OutputStream &) const {}
 
   virtual StringView getBaseName() const { return StringView(); }
 
   // Silence compiler warnings, this dtor will never be called.
   virtual ~Node() = default;
+
+#ifndef NDEBUG
+  DUMP_METHOD void dump() const {
+    char *Buffer = static_cast<char*>(std::malloc(1024));
+    OutputStream S(Buffer, 1024);
+    print(S);
+    S += '\0';
+    printf("Symbol dump for %p: %s\n", (const void*)this, S.getBuffer());
+    std::free(S.getBuffer());
+  }
+#endif
 };
 
 class NodeArray {
   Node **Elements;
   size_t NumElements;
 
 public:
-  NodeArray() : NumElements(0) {}
+  NodeArray() : Elements(nullptr), NumElements(0) {}
   NodeArray(Node **Elements_, size_t NumElements_)
       : Elements(Elements_), NumElements(NumElements_) {}
 
   bool empty() const { return NumElements == 0; }
   size_t size() const { return NumElements; }
 
-  void printWithSeperator(OutputStream &S, StringView Seperator) const {
+  Node **begin() const { return Elements; }
+  Node **end() const { return Elements + NumElements; }
+
+  Node *operator[](size_t Idx) const { return Elements[Idx]; }
+
+  void printWithComma(OutputStream &S) const {
+    bool FirstElement = true;
     for (size_t Idx = 0; Idx != NumElements; ++Idx) {
-      if (Idx)
-        S += Seperator;
+      if (Elements[Idx]->isEmptyPackExpansion())
+        continue;
+      if (!FirstElement)
+        S += ", ";
+      FirstElement = false;
       Elements[Idx]->print(S);
     }
   }
 };
 
 class DotSuffix final : public Node {
   const Node *Prefix;
   const StringView Suffix;
 
 public:
   DotSuffix(Node *Prefix_, StringView Suffix_)
       : Node(KDotSuffix), Prefix(Prefix_), Suffix(Suffix_) {}
 
   void printLeft(OutputStream &s) const override {
     Prefix->print(s);
     s += " (";
     s += Suffix;
     s += ")";
   }
 };
 
 class VendorExtQualType final : public Node {
-  const Node *Ext;
   const Node *Ty;
+  const Node *Ext;
 
 public:
-  VendorExtQualType(Node *Ext_, Node *Ty_)
-      : Node(KVendorExtQualType), Ext(Ext_), Ty(Ty_) {}
+  VendorExtQualType(Node *Ty_, Node *Ext_)
+      : Node(KVendorExtQualType,
+             std::min(Ty_->ParameterPackSize, Ext_->ParameterPackSize)),
+        Ty(Ty_), Ext(Ext_) {}
+
+  const Node* getQual() const { return Ext; }
 
   void printLeft(OutputStream &S) const override {
-    Ext->print(S);
+    Ty->print(S);
     S += " ";
-    Ty->printLeft(S);
+    Ext->print(S);
   }
-
-  void printRight(OutputStream &S) const override { Ty->printRight(S); }
 };
 
 enum Qualifiers {
   QualNone = 0,
   QualConst = 0x1,
   QualVolatile = 0x2,
   QualRestrict = 0x4,
 };
void printQuals(OutputStream &S) const {
     if (Quals & QualVolatile)
       S += " volatile";
     if (Quals & QualRestrict)
       S += " restrict";
   }
 
 public:
   QualType(Node *Child_, Qualifiers Quals_)
-      : Node(KQualType, Child_->hasRHSComponent(), Child_->hasFunction(),
-             Child_->hasArray()),
+      : Node(KQualType, Child_->ParameterPackSize, Child_->RHSComponentCache,
+             Child_->ArrayCache, Child_->FunctionCache),
         Quals(Quals_), Child(Child_) {}
 
-  QualType(Node::Kind ChildKind_, Node *Child_, Qualifiers Quals_)
-      : Node(ChildKind_, Child_->hasRHSComponent(), Child_->hasFunction(),
-             Child_->hasArray()),
-        Quals(Quals_), Child(Child_) {}
+  bool hasRHSComponentSlow(OutputStream &S) const override {
+    return Child->hasRHSComponent(S);
+  }
+  bool hasArraySlow(OutputStream &S) const override {
+    return Child->hasArray(S);
+  }
+  bool hasFunctionSlow(OutputStream &S) const override {
+    return Child->hasFunction(S);
+  }
 
   void printLeft(OutputStream &S) const override {
     Child->printLeft(S);
     printQuals(S);
   }
 
   void printRight(OutputStream &S) const override { Child->printRight(S); }
 };
 
 class ConversionOperatorType final : public Node {
   const Node *Ty;
 
 public:
-  ConversionOperatorType(Node *Ty_) : Node(KConversionOperatorType), Ty(Ty_) {}
+  ConversionOperatorType(Node *Ty_)
+      : Node(KConversionOperatorType, Ty_->ParameterPackSize), Ty(Ty_) {}
 
   void printLeft(OutputStream &S) const override {
     S += "operator ";
     Ty->print(S);
   }
 };
 
 class PostfixQualifiedType final : public Node {
   const Node *Ty;
   const StringView Postfix;
 
 public:
   PostfixQualifiedType(Node *Ty_, StringView Postfix_)
-      : Node(KPostfixQualifiedType), Ty(Ty_), Postfix(Postfix_) {}
+      : Node(KPostfixQualifiedType, Ty_->ParameterPackSize),
+        Ty(Ty_), Postfix(Postfix_) {}
 
   void printLeft(OutputStream &s) const override {
     Ty->printLeft(s);
     s += Postfix;
   }
-
-  void printRight(OutputStream &S) const override { Ty->printRight(S); }
 };
 
 class NameType final : public Node {
   const StringView Name;
 
 public:
   NameType(StringView Name_) : Node(KNameType), Name(Name_) {}
 
   StringView getName() const { return Name; }
   StringView getBaseName() const override { return Name; }
 
   void printLeft(OutputStream &s) const override { s += Name; }
 };
 
 class AbiTagAttr final : public Node {
   const Node* Base;
   StringView Tag;
 public:
   AbiTagAttr(const Node* Base_, StringView Tag_)
-      : Node(KAbiTagAttr), Base(Base_), Tag(Tag_) {}
+      : Node(KAbiTagAttr, Base_->ParameterPackSize, Base_->RHSComponentCache,
+             Base_->ArrayCache, Base_->FunctionCache),
+        Base(Base_), Tag(Tag_) {}
 
   void printLeft(OutputStream &S) const override {
     Base->printLeft(S);
     S += "[abi:";
     S += Tag;
     S += "]";
   }
 };
 
 class ObjCProtoName : public Node {
   Node *Ty;
   Node *Protocol;
 
   friend class PointerType;
 
 public:
   ObjCProtoName(Node *Ty_, Node *Protocol_)
       : Node(KObjCProtoName), Ty(Ty_), Protocol(Protocol_) {}
 
   bool isObjCObject() const {
-    return Ty->K == KNameType &&
+    return Ty->getKind() == KNameType &&
            static_cast<NameType *>(Ty)->getName() == "objc_object";
   }
 
   void printLeft(OutputStream &S) const override {
-    Ty->printLeft(S);
+    Ty->print(S);
     S += "<";
-    Protocol->printLeft(S);
+    Protocol->print(S);
     S += ">";
   }
 };
 
 class PointerType final : public Node {
   const Node *Pointee;
 
 public:
   PointerType(Node *Pointee_)
-      : Node(KPointerType, Pointee_->hasRHSComponent()), Pointee(Pointee_) {}
+      : Node(KPointerType, Pointee_->ParameterPackSize,
+             Pointee_->RHSComponentCache),
+        Pointee(Pointee_) {}
+
+  bool hasRHSComponentSlow(OutputStream &S) const override {
+    return Pointee->hasRHSComponent(S);
+  }
 
   void printLeft(OutputStream &s) const override {
     // We rewrite objc_object<SomeProtocol>* into id<SomeProtocol>.
-    if (Pointee->K != KObjCProtoName ||
+    if (Pointee->getKind() != KObjCProtoName ||
         !static_cast<const ObjCProtoName *>(Pointee)->isObjCObject()) {
       Pointee->printLeft(s);
-      if (Pointee->hasArray())
+      if (Pointee->hasArray(s))
         s += " ";
-      if (Pointee->hasArray() || Pointee->hasFunction())
+      if (Pointee->hasArray(s) || Pointee->hasFunction(s))
         s += "(";
       s += "*";
     } else {
       const auto *objcProto = static_cast<const ObjCProtoName *>(Pointee);
       s += "id<";
       objcProto->Protocol->print(s);
       s += ">";
     }
   }
 
   void printRight(OutputStream &s) const override {
-    if (Pointee->K != KObjCProtoName ||
+    if (Pointee->getKind() != KObjCProtoName ||
         !static_cast<const ObjCProtoName *>(Pointee)->isObjCObject()) {
-      if (Pointee->hasArray() || Pointee->hasFunction())
+      if (Pointee->hasArray(s) || Pointee->hasFunction(s))
         s += ")";
       Pointee->printRight(s);
     }
   }
 };
 
 class LValueReferenceType final : public Node {
   const Node *Pointee;
 
 public:
   LValueReferenceType(Node *Pointee_)
-      : Node(KLValueReferenceType, Pointee_->hasRHSComponent()),
+      : Node(KLValueReferenceType, Pointee_->ParameterPackSize,
+             Pointee_->RHSComponentCache),
         Pointee(Pointee_) {}
 
+  bool hasRHSComponentSlow(OutputStream &S) const override {
+    return Pointee->hasRHSComponent(S);
+  }
+
   void printLeft(OutputStream &s) const override {
     Pointee->printLeft(s);
-    if (Pointee->hasArray())
+    if (Pointee->hasArray(s))
       s += " ";
-    if (Pointee->hasArray() || Pointee->hasFunction())
+    if (Pointee->hasArray(s) || Pointee->hasFunction(s))
       s += "(&";
     else
       s += "&";
   }
   void printRight(OutputStream &s) const override {
-    if (Pointee->hasArray() || Pointee->hasFunction())
+    if (Pointee->hasArray(s) || Pointee->hasFunction(s))
       s += ")";
     Pointee->printRight(s);
   }
 };
 
 class RValueReferenceType final : public Node {
   const Node *Pointee;
 
 public:
   RValueReferenceType(Node *Pointee_)
-      : Node(KRValueReferenceType, Pointee_->hasRHSComponent()),
+      : Node(KRValueReferenceType, Pointee_->ParameterPackSize,
+             Pointee_->RHSComponentCache),
         Pointee(Pointee_) {}
 
+  bool hasRHSComponentSlow(OutputStream &S) const override {
+    return Pointee->hasRHSComponent(S);
+  }
+
   void printLeft(OutputStream &s) const override {
     Pointee->printLeft(s);
-    if (Pointee->hasArray())
+    if (Pointee->hasArray(s))
       s += " ";
-    if (Pointee->hasArray() || Pointee->hasFunction())
+    if (Pointee->hasArray(s) || Pointee->hasFunction(s))
       s += "(&&";
     else
       s += "&&";
   }
 
   void printRight(OutputStream &s) const override {
-    if (Pointee->hasArray() || Pointee->hasFunction())
+    if (Pointee->hasArray(s) || Pointee->hasFunction(s))
       s += ")";
     Pointee->printRight(s);
   }
 };
 
 class PointerToMemberType final : public Node {
   const Node *ClassType;
   const Node *MemberType;
 
 public:
   PointerToMemberType(Node *ClassType_, Node *MemberType_)
-      : Node(KPointerToMemberType, MemberType_->hasRHSComponent()),
+      : Node(KPointerToMemberType,
+             std::min(MemberType_->ParameterPackSize,
+                      ClassType_->ParameterPackSize),
+             MemberType_->RHSComponentCache),
         ClassType(ClassType_), MemberType(MemberType_) {}
 
+  bool hasRHSComponentSlow(OutputStream &S) const override {
+    return MemberType->hasRHSComponent(S);
+  }
+
   void printLeft(OutputStream &s) const override {
     MemberType->printLeft(s);
-    if (MemberType->hasArray() || MemberType->hasFunction())
+    if (MemberType->hasArray(s) || MemberType->hasFunction(s))
       s += "(";
     else
       s += " ";
     ClassType->print(s);
     s += "::*";
   }
 
   void printRight(OutputStream &s) const override {
-    if (MemberType->hasArray() || MemberType->hasFunction())
+    if (MemberType->hasArray(s) || MemberType->hasFunction(s))
       s += ")";
     MemberType->printRight(s);
   }
 };
 
 class NodeOrString {
   const void *First;
   const void *Second;

 };
 
 class ArrayType final : public Node {
   Node *Base;
   NodeOrString Dimension;
 
 public:
   ArrayType(Node *Base_, NodeOrString Dimension_)
-      : Node(KArrayType, true, false, true), Base(Base_), Dimension(Dimension_) {}
+      : Node(KArrayType, Base_->ParameterPackSize,
+             /*RHSComponentCache=*/Cache::Yes,
+             /*ArrayCache=*/Cache::Yes),
+        Base(Base_), Dimension(Dimension_) {
+    if (Dimension.isNode())
+      ParameterPackSize =
+          std::min(ParameterPackSize, Dimension.asNode()->ParameterPackSize);
+  }
 
   // Incomplete array type.
-  ArrayType(Node *Base_) : Node(KArrayType, true, false, true), Base(Base_) {}
+  ArrayType(Node *Base_)
+      : Node(KArrayType, Base_->ParameterPackSize,
+             /*RHSComponentCache=*/Cache::Yes,
+             /*ArrayCache=*/Cache::Yes),
+        Base(Base_) {}
+
+  bool hasRHSComponentSlow(OutputStream &) const override { return true; }
+  bool hasArraySlow(OutputStream &) const override { return true; }
 
   void printLeft(OutputStream &S) const override { Base->printLeft(S); }
 
   void printRight(OutputStream &S) const override {
     if (S.back() != ']')
       S += " ";
     S += "[";
     if (Dimension.isString())
       S += Dimension.asString();
     else if (Dimension.isNode())
       Dimension.asNode()->print(S);
     S += "]";
     Base->printRight(S);
   }
 };
 
 class FunctionType final : public Node {
   Node *Ret;
   NodeArray Params;
 
 public:
   FunctionType(Node *Ret_, NodeArray Params_)
-      : Node(KFunctionType, true, true), Ret(Ret_), Params(Params_) {}
+      : Node(KFunctionType, Ret_->ParameterPackSize,
+             /*RHSComponentCache=*/Cache::Yes, /*ArrayCache=*/Cache::No,
+             /*FunctionCache=*/Cache::Yes),
+        Ret(Ret_), Params(Params_) {
+    for (Node *P : Params)
+      ParameterPackSize = std::min(ParameterPackSize, P->ParameterPackSize);
+  }
+
+  bool hasRHSComponentSlow(OutputStream &) const override { return true; }
+  bool hasFunctionSlow(OutputStream &) const override { return true; }
 
   // Handle C++'s ... quirky decl grammer by using the left & right
   // distinction. Consider:
   //   int (*f(float))(char) {}
   // f is a function that takes a float and returns a pointer to a function
   // that takes a char and returns an int. If we're trying to print f, start
   // by printing out the return types's left, then print our parameters, then
   // finally print right of the return type.
   void printLeft(OutputStream &S) const override {
     Ret->printLeft(S);
     S += " ";
   }
 
   void printRight(OutputStream &S) const override {
     S += "(";
-    Params.printWithSeperator(S, ", ");
+    Params.printWithComma(S);
     S += ")";
     Ret->printRight(S);
   }
 };
 
-class TopLevelFunctionDecl final : public Node {
+class FunctionEncoding final : public Node {
   const Node *Ret;
   const Node *Name;
   NodeArray Params;
 
 public:
-  TopLevelFunctionDecl(Node *Ret_, Node *Name_, NodeArray Params_)
-      : Node(KTopLevelFunctionDecl, true, true), Ret(Ret_), Name(Name_),
-        Params(Params_) {}
+  FunctionEncoding(Node *Ret_, Node *Name_, NodeArray Params_)
+      : Node(KFunctionEncoding, NoParameterPack,
+             /*RHSComponentCache=*/Cache::Yes, /*ArrayCache=*/Cache::No,
+             /*FunctionCache=*/Cache::Yes),
+        Ret(Ret_), Name(Name_), Params(Params_) {
+    for (Node *P : Params)
+      ParameterPackSize = std::min(ParameterPackSize, P->ParameterPackSize);
+    if (Ret)
+      ParameterPackSize = std::min(ParameterPackSize, Ret->ParameterPackSize);
+  }
+
+  bool hasRHSComponentSlow(OutputStream &) const override { return true; }
+  bool hasFunctionSlow(OutputStream &) const override { return true; }
+
+  Node *getName() { return const_cast<Node *>(Name); }
 
   void printLeft(OutputStream &S) const override {
     if (Ret) {
       Ret->printLeft(S);
-      if (!Ret->hasRHSComponent())
+      if (!Ret->hasRHSComponent(S))
         S += " ";
     }
     Name->print(S);
   }
 
   void printRight(OutputStream &S) const override {
     S += "(";
-    Params.printWithSeperator(S, ", ");
+    Params.printWithComma(S);
     S += ")";
     if (Ret)
       Ret->printRight(S);
   }
 };
 
 enum FunctionRefQual : unsigned char {
   FrefQualNone,
   FrefQualLValue,
   FrefQualRValue,
 };
 
 class FunctionRefQualType : public Node {
   Node *Fn;
   FunctionRefQual Quals;
 
   friend class FunctionQualType;
 
 public:
   FunctionRefQualType(Node *Fn_, FunctionRefQual Quals_)
-      : Node(KFunctionRefQualType, true, true), Fn(Fn_), Quals(Quals_) {}
+      : Node(KFunctionRefQualType, Fn_->ParameterPackSize,
+             /*RHSComponentCache=*/Cache::Yes, /*ArrayCache=*/Cache::No,
+             /*FunctionCache=*/Cache::Yes),
+        Fn(Fn_), Quals(Quals_) {}
+
+  bool hasFunctionSlow(OutputStream &) const override { return true; }
+  bool hasRHSComponentSlow(OutputStream &) const override { return true; }
 
   void printQuals(OutputStream &S) const {
     if (Quals == FrefQualLValue)
       S += " &";
     else
       S += " &&";
   }
 
   void printLeft(OutputStream &S) const override { Fn->printLeft(S); }
 
   void printRight(OutputStream &S) const override {
     Fn->printRight(S);
     printQuals(S);
   }
 };
 
 class FunctionQualType final : public QualType {
 public:
   FunctionQualType(Node *Child_, Qualifiers Quals_)
-      : QualType(KFunctionQualType, Child_, Quals_) {}
+      : QualType(Child_, Quals_) {
+    K = KFunctionQualType;
+  }
 
   void printLeft(OutputStream &S) const override { Child->printLeft(S); }
 
   void printRight(OutputStream &S) const override {
-    if (Child->K == KFunctionRefQualType) {
+    if (Child->getKind() == KFunctionRefQualType) {
       auto *RefQuals = static_cast<const FunctionRefQualType *>(Child);
       RefQuals->Fn->printRight(S);
       printQuals(S);
       RefQuals->printQuals(S);
     } else {
       Child->printRight(S);
       printQuals(S);
     }
   }
 };
 
 class LiteralOperator : public Node {
   const Node *OpName;
 
 public:
-  LiteralOperator(Node *OpName_) : Node(KLiteralOperator), OpName(OpName_) {}
+  LiteralOperator(Node *OpName_)
+      : Node(KLiteralOperator, OpName_->ParameterPackSize), OpName(OpName_) {}
 
   void printLeft(OutputStream &S) const override {
     S += "operator\"\" ";
     OpName->print(S);
   }
 };
 
 class SpecialName final : public Node {
   const StringView Special;
   const Node *Child;
 
 public:
-  SpecialName(StringView Special_, Node *Child_)
-      : Node(KSpecialName), Special(Special_), Child(Child_) {}
+  SpecialName(StringView Special_, Node* Child_)
+      : Node(KSpecialName, Child_->ParameterPackSize), Special(Special_),
+        Child(Child_) {}
 
   void printLeft(OutputStream &S) const override {
     S += Special;
     Child->print(S);
   }
 };
 
 class CtorVtableSpecialName final : public Node {
   const Node *FirstType;
   const Node *SecondType;
 
 public:
   CtorVtableSpecialName(Node *FirstType_, Node *SecondType_)
-      : Node(KCtorVtableSpecialName), FirstType(FirstType_),
-        SecondType(SecondType_) {}
+      : Node(KCtorVtableSpecialName, std::min(FirstType_->ParameterPackSize,
+                                              SecondType_->ParameterPackSize)),
+        FirstType(FirstType_), SecondType(SecondType_) {}
 
   void printLeft(OutputStream &S) const override {
     S += "construction vtable for ";
     FirstType->print(S);
     S += "-in-";
     SecondType->print(S);
   }
 };
 
 class QualifiedName final : public Node {
   // qualifier::name
   const Node *Qualifier;
   const Node *Name;
 
-  mutable OutputStream::StreamStringView Cache;
-
 public:
-  QualifiedName(Node *Qualifier_, Node *Name_)
-      : Node(KQualifiedName), Qualifier(Qualifier_), Name(Name_) {}
+  QualifiedName(Node* Qualifier_, Node* Name_)
+      : Node(KQualifiedName,
+             std::min(Qualifier_->ParameterPackSize, Name_->ParameterPackSize)),
+        Qualifier(Qualifier_), Name(Name_) {}
 
   StringView getBaseName() const override { return Name->getBaseName(); }
 
   void printLeft(OutputStream &S) const override {
-    if (!Cache.empty()) {
-      S += Cache;
-      return;
-    }
-
-    OutputStream::StreamPosition Start = S.getCurrentPosition();
-    if (Qualifier->K != KEmptyName) {
-      Qualifier->print(S);
-      S += "::";
-    }
     Name->print(S);
-    Cache = S.makeStringViewFromPastPosition(Start);
   }
 };
 
 class EmptyName : public Node {
 public:
   EmptyName() : Node(KEmptyName) {}
   void printLeft(OutputStream &) const override {}
 };
 
 class VectorType final : public Node {
   const Node *BaseType;
   const NodeOrString Dimension;
   const bool IsPixel;
 
 public:
   VectorType(NodeOrString Dimension_)
       : Node(KVectorType), BaseType(nullptr), Dimension(Dimension_),
-        IsPixel(true) {}
+        IsPixel(true) {
+    if (Dimension.isNode())
+      ParameterPackSize = Dimension.asNode()->ParameterPackSize;
+  }
   VectorType(Node *BaseType_, NodeOrString Dimension_)
-      : Node(KVectorType), BaseType(BaseType_), Dimension(Dimension_),
-        IsPixel(false) {}
+      : Node(KVectorType, BaseType_->ParameterPackSize), BaseType(BaseType_),
+        Dimension(Dimension_), IsPixel(false) {
+    if (Dimension.isNode())
+      ParameterPackSize =
+          std::min(ParameterPackSize, Dimension.asNode()->ParameterPackSize);
+  }
 
   void printLeft(OutputStream &S) const override {
     if (IsPixel) {
       S += "pixel vector[";
       S += Dimension.asString();
       S += "]";
     } else {
       BaseType->print(S);
       S += " vector[";
       if (Dimension.isNode())
         Dimension.asNode()->print(S);
       else if (Dimension.isString())
         S += Dimension.asString();
       S += "]";
     }
   }
 };
 
-class TemplateParams final : public Node {
-  NodeArray Params;
+/// An unexpanded parameter pack (either in the expression or type context). If
+/// this AST is correct, this node will have a ParameterPackExpansion node above
+/// it.
+///
+/// This node is created when some <template-args> are found that apply to an
+/// <encoding>, and is stored in the TemplateParams table. In order for this to
+/// appear in the final AST, it has to referenced via a <template-param> (ie,
+/// T_).
+class ParameterPack final : public Node {
+  NodeArray Data;
+public:
+  ParameterPack(NodeArray Data_)
+      : Node(KParameterPack, static_cast<unsigned>(Data_.size())), Data(Data_) {
+    ArrayCache = FunctionCache = RHSComponentCache = Cache::Unknown;
+    if (std::all_of(Data.begin(), Data.end(), [](Node* P) {
+          return P->ArrayCache == Cache::No;
+        }))
+      ArrayCache = Cache::No;
+    if (std::all_of(Data.begin(), Data.end(), [](Node* P) {
+          return P->FunctionCache == Cache::No;
+        }))
+      FunctionCache = Cache::No;
+    if (std::all_of(Data.begin(), Data.end(), [](Node* P) {
+          return P->RHSComponentCache == Cache::No;
+        }))
+      RHSComponentCache = Cache::No;
+  }
+
+  bool hasRHSComponentSlow(OutputStream &S) const override {
+    size_t Idx = S.CurrentPackIndex;
+    return Idx < Data.size() && Data[Idx]->hasRHSComponent(S);
+  }
+  bool hasArraySlow(OutputStream &S) const override {
+    size_t Idx = S.CurrentPackIndex;
+    return Idx < Data.size() && Data[Idx]->hasArray(S);
+  }
+  bool hasFunctionSlow(OutputStream &S) const override {
+    size_t Idx = S.CurrentPackIndex;
+    return Idx < Data.size() && Data[Idx]->hasFunction(S);
+  }
+
+  void printLeft(OutputStream &S) const override {
+    size_t Idx = S.CurrentPackIndex;
+    if (Idx < Data.size())
+      Data[Idx]->printLeft(S);
+  }
+  void printRight(OutputStream &S) const override {
+    size_t Idx = S.CurrentPackIndex;
+    if (Idx < Data.size())
+      Data[Idx]->printRight(S);
+  }
+};
+
+/// A variadic template argument. This node represents an occurance of
+/// J<something>E in some <template-args>. It isn't itself unexpanded, unless
+/// one of it's Elements is. The parser inserts a ParameterPack into the
+/// TemplateParams table if the <template-args> this pack belongs to apply to an
+/// <encoding>.
+class TemplateArgumentPack final : public Node {
+  NodeArray Elements;
+public:
+  TemplateArgumentPack(NodeArray Elements_)
+      : Node(KTemplateArgumentPack), Elements(Elements_) {
+    for (Node *E : Elements)
+      ParameterPackSize = std::min(E->ParameterPackSize, ParameterPackSize);
+  }
+
+  NodeArray getElements() const { return Elements; }
+
+  void printLeft(OutputStream &S) const override {
+    Elements.printWithComma(S);
+  }
+};
 
-  mutable OutputStream::StreamStringView Cache;
+/// A pack expansion. Below this node, there are some unexpanded ParameterPacks
+/// which each have Child->ParameterPackSize elements.
+class ParameterPackExpansion final : public Node {
+  const Node *Child;
 
 public:
-  TemplateParams(NodeArray Params_) : Node(KTemplateParams), Params(Params_) {}
+  ParameterPackExpansion(Node* Child_)
+      : Node(KParameterPackExpansion), Child(Child_) {}
+
+  const Node *getChild() const { return Child; }
 
   void printLeft(OutputStream &S) const override {
-    if (!Cache.empty()) {
-      S += Cache;
+    unsigned PackSize = Child->ParameterPackSize;
+    if (PackSize == NoParameterPack) {
+      Child->print(S);
+      S += "...";
       return;
     }
 
-    OutputStream::StreamPosition Start = S.getCurrentPosition();
+    SwapAndRestore<unsigned> SavePackIndex(S.CurrentPackIndex, 0);
+    for (unsigned I = 0; I != PackSize; ++I) {
+      if (I != 0)
+        S += ", ";
+      S.CurrentPackIndex = I;
+      Child->print(S);
+    }
+  }
+};
+
+inline bool Node::isEmptyPackExpansion() const {
+  if (getKind() == KParameterPackExpansion) {
+    auto *AsPack = static_cast<const ParameterPackExpansion *>(this);
+    return AsPack->getChild()->isEmptyPackExpansion();
+  }
+  if (getKind() == KTemplateArgumentPack) {
+    auto *AsTemplateArg = static_cast<const TemplateArgumentPack *>(this);
+    for (Node *E : AsTemplateArg->getElements())
+      if (!E->isEmptyPackExpansion())
+        return false;
+    return true;
+  }
+  return ParameterPackSize == 0;
+}
+
+class TemplateArgs final : public Node {
+  NodeArray Params;
+
+public:
+  TemplateArgs(NodeArray Params_) : Node(KTemplateArgs), Params(Params_) {
+    for (Node *P : Params)
+      ParameterPackSize = std::min(ParameterPackSize, P->ParameterPackSize);
+  }
+
+  NodeArray getParams() { return Params; }
 
+  void printLeft(OutputStream &S) const override {
     S += "<";
-    Params.printWithSeperator(S, ", ");
+    bool FirstElement = true;
+    for (size_t Idx = 0, E = Params.size(); Idx != E; ++Idx) {
+      if (Params[Idx]->isEmptyPackExpansion())
+        continue;
+      if (!FirstElement)
+        S += ", ";
+      FirstElement = false;
+      Params[Idx]->print(S);
+    }
     if (S.back() == '>')
       S += " ";
     S += ">";
-
-    Cache = S.makeStringViewFromPastPosition(Start);
   }
 };
 
 class NameWithTemplateArgs final : public Node {
   // name<template_args>
   Node *Name;
   Node *TemplateArgs;
 
 public:
   NameWithTemplateArgs(Node *Name_, Node *TemplateArgs_)
-      : Node(KNameWithTemplateArgs), Name(Name_), TemplateArgs(TemplateArgs_) {}
+      : Node(KNameWithTemplateArgs, std::min(Name_->ParameterPackSize,
+                                             TemplateArgs_->ParameterPackSize)),
+        Name(Name_), TemplateArgs(TemplateArgs_) {}
 
   StringView getBaseName() const override { return Name->getBaseName(); }
 
   void printLeft(OutputStream &S) const override {
     Name->print(S);
     TemplateArgs->print(S);
   }
 };
 
 class GlobalQualifiedName final : public Node {
   Node *Child;
 
 public:
-  GlobalQualifiedName(Node *Child_) : Node(KGlobalQualifiedName), Child(Child_) {}
+  GlobalQualifiedName(Node* Child_)
+      : Node(KGlobalQualifiedName, Child_->ParameterPackSize), Child(Child_) {}
 
   StringView getBaseName() const override { return Child->getBaseName(); }
 
   void printLeft(OutputStream &S) const override {
     S += "::";
     Child->print(S);
   }
 };
 
 class StdQualifiedName final : public Node {
   Node *Child;
 
 public:
-  StdQualifiedName(Node *Child_) : Node(KStdQualifiedName), Child(Child_) {}
+  StdQualifiedName(Node *Child_)
+      : Node(KStdQualifiedName, Child_->ParameterPackSize), Child(Child_) {}
 
   StringView getBaseName() const override { return Child->getBaseName(); }
 
   void printLeft(OutputStream &S) const override {
     S += "std::";
     Child->print(S);
   }
 };

 };
 
 class CtorDtorName final : public Node {
   const Node *Basename;
   const bool IsDtor;
 
 public:
   CtorDtorName(Node *Basename_, bool IsDtor_)
-      : Node(KCtorDtorName), Basename(Basename_), IsDtor(IsDtor_) {}
+      : Node(KCtorDtorName, Basename_->ParameterPackSize),
+        Basename(Basename_), IsDtor(IsDtor_) {}
 
   void printLeft(OutputStream &S) const override {
     if (IsDtor)
       S += "~";
     S += Basename->getBaseName();
   }
 };
 
 class DtorName : public Node {
   const Node *Base;
 
 public:
-  DtorName(Node *Base_) : Node(KDtorName), Base(Base_) {}
+  DtorName(Node *Base_) : Node(KDtorName), Base(Base_) {
+    ParameterPackSize = Base->ParameterPackSize;
+  }
 
   void printLeft(OutputStream &S) const override {
     S += "~";
     Base->printLeft(S);
   }
 };
 
 class UnnamedTypeName : public Node {

 };
 
 class LambdaTypeName : public Node {
   NodeArray Params;
   StringView Count;
 
 public:
   LambdaTypeName(NodeArray Params_, StringView Count_)
-      : Node(KLambdaTypeName), Params(Params_), Count(Count_) {}
+      : Node(KLambdaTypeName), Params(Params_), Count(Count_) {
+    for (Node *P : Params)
+      ParameterPackSize = std::min(ParameterPackSize, P->ParameterPackSize);
+  }
 
   void printLeft(OutputStream &S) const override {
     S += "\'lambda";
     S += Count;
     S += "\'(";
-    Params.printWithSeperator(S, ", ");
+    Params.printWithComma(S);
     S += ")";
   }
 };
 
 // -- Expression Nodes --
 
 struct Expr : public Node {
   Expr() : Node(KExpr) {}
 };
 
 class BinaryExpr : public Expr {
   const Node *LHS;
   const StringView InfixOperator;
   const Node *RHS;
 
 public:
   BinaryExpr(Node *LHS_, StringView InfixOperator_, Node *RHS_)
-      : LHS(LHS_), InfixOperator(InfixOperator_), RHS(RHS_) {}
+      : LHS(LHS_), InfixOperator(InfixOperator_), RHS(RHS_) {
+    ParameterPackSize =
+      std::min(LHS->ParameterPackSize, RHS->ParameterPackSize);
+  }
 
   void printLeft(OutputStream &S) const override {
     // might be a template argument expression, then we need to disambiguate
     // with parens.
     if (InfixOperator == ">")
       S += "(";
 
     S += "(";
public:
   }
 };
 
 class ArraySubscriptExpr : public Expr {
   const Node *Op1;
   const Node *Op2;
 
 public:
-  ArraySubscriptExpr(Node *Op1_, Node *Op2_) : Op1(Op1_), Op2(Op2_) {}
+  ArraySubscriptExpr(Node *Op1_, Node *Op2_) : Op1(Op1_), Op2(Op2_) {
+    ParameterPackSize =
+      std::min(Op1->ParameterPackSize, Op2->ParameterPackSize);
+  }
 
   void printLeft(OutputStream &S) const override {
     S += "(";
     Op1->print(S);
     S += ")[";
     Op2->print(S);
     S += "]";
   }
 };
 
 class PostfixExpr : public Expr {
   const Node *Child;
   const StringView Operand;
 
 public:
   PostfixExpr(Node *Child_, StringView Operand_)
-      : Child(Child_), Operand(Operand_) {}
+      : Child(Child_), Operand(Operand_) {
+    ParameterPackSize = Child->ParameterPackSize;
+  }
 
   void printLeft(OutputStream &S) const override {
     S += "(";
     Child->print(S);
     S += ")";
     S += Operand;
   }
 };
 
 class ConditionalExpr : public Expr {
   const Node *Cond;
   const Node *Then;
   const Node *Else;
 
 public:
   ConditionalExpr(Node *Cond_, Node *Then_, Node *Else_)
-      : Cond(Cond_), Then(Then_), Else(Else_) {}
+      : Cond(Cond_), Then(Then_), Else(Else_) {
+    ParameterPackSize =
+        std::min(Cond->ParameterPackSize,
+                 std::min(Then->ParameterPackSize, Else->ParameterPackSize));
+  }
 
   void printLeft(OutputStream &S) const override {
     S += "(";
     Cond->print(S);
     S += ") ? (";
     Then->print(S);
     S += ") : (";
     Else->print(S);
     S += ")";
   }
 };
 
 class MemberExpr : public Expr {
   const Node *LHS;
   const StringView Kind;
   const Node *RHS;
 
 public:
   MemberExpr(Node *LHS_, StringView Kind_, Node *RHS_)
-      : LHS(LHS_), Kind(Kind_), RHS(RHS_) {}
+      : LHS(LHS_), Kind(Kind_), RHS(RHS_) {
+    ParameterPackSize =
+      std::min(LHS->ParameterPackSize, RHS->ParameterPackSize);
+  }
 
   void printLeft(OutputStream &S) const override {
     LHS->print(S);
     S += Kind;
     RHS->print(S);
   }
 };
 
 class EnclosingExpr : public Expr {
   const StringView Prefix;
   const Node *Infix;
   const StringView Postfix;
 
 public:
   EnclosingExpr(StringView Prefix_, Node *Infix_, StringView Postfix_)
-      : Prefix(Prefix_), Infix(Infix_), Postfix(Postfix_) {}
+      : Prefix(Prefix_), Infix(Infix_), Postfix(Postfix_) {
+    ParameterPackSize = Infix->ParameterPackSize;
+  }
 
   void printLeft(OutputStream &S) const override {
     S += Prefix;
     Infix->print(S);
     S += Postfix;
   }
 };
 
 class CastExpr : public Expr {
   // cast_kind<to>(from)
   const StringView CastKind;
   const Node *To;
   const Node *From;
 
 public:
   CastExpr(StringView CastKind_, Node *To_, Node *From_)
-      : CastKind(CastKind_), To(To_), From(From_) {}
+      : CastKind(CastKind_), To(To_), From(From_) {
+    ParameterPackSize =
+      std::min(To->ParameterPackSize, From->ParameterPackSize);
+  }
 
   void printLeft(OutputStream &S) const override {
     S += CastKind;
     S += "<";
     To->printLeft(S);
     S += ">(";
     From->printLeft(S);
     S += ")";
   }
 };
 
 class SizeofParamPackExpr : public Expr {
-  NodeArray Args;
+  Node *Pack;
 
 public:
-  SizeofParamPackExpr(NodeArray Args_) : Args(Args_) {}
+  SizeofParamPackExpr(Node *Pack_) : Pack(Pack_) {}
 
   void printLeft(OutputStream &S) const override {
     S += "sizeof...(";
-    Args.printWithSeperator(S, ", ");
+    ParameterPackExpansion PPE(Pack);
+    PPE.printLeft(S);
     S += ")";
   }
 };
 
 class CallExpr : public Expr {
   const Node *Callee;
   NodeArray Args;
 
 public:
-  CallExpr(Node *Callee_, NodeArray Args_) : Callee(Callee_), Args(Args_) {}
+  CallExpr(Node *Callee_, NodeArray Args_) : Callee(Callee_), Args(Args_) {
+    for (Node *P : Args)
+      ParameterPackSize = std::min(ParameterPackSize, P->ParameterPackSize);
+    ParameterPackSize = std::min(ParameterPackSize, Callee->ParameterPackSize);
+  }
 
   void printLeft(OutputStream &S) const override {
     Callee->print(S);
     S += "(";
-    Args.printWithSeperator(S, ", ");
+    Args.printWithComma(S);
     S += ")";
   }
 };
 
 class NewExpr : public Expr {
   // new (expr_list) type(init_list)
   NodeArray ExprList;
   Node *Type;
   NodeArray InitList;
   bool IsGlobal; // ::operator new ?
   bool IsArray;  // new[] ?
 public:
   NewExpr(NodeArray ExprList_, Node *Type_, NodeArray InitList_, bool IsGlobal_,
           bool IsArray_)
-      : ExprList(ExprList_), Type(Type_), InitList(InitList_), IsGlobal(IsGlobal_),
-        IsArray(IsArray_) {}
+      : ExprList(ExprList_), Type(Type_), InitList(InitList_),
+        IsGlobal(IsGlobal_), IsArray(IsArray_) {
+    for (Node *E : ExprList)
+      ParameterPackSize = std::min(ParameterPackSize, E->ParameterPackSize);
+    for (Node *I : InitList)
+      ParameterPackSize = std::min(ParameterPackSize, I->ParameterPackSize);
+    if (Type)
+      ParameterPackSize = std::min(ParameterPackSize, Type->ParameterPackSize);
+  }
 
   void printLeft(OutputStream &S) const override {
     if (IsGlobal)
       S += "::operator ";
     S += "new";
     if (IsArray)
       S += "[]";
     if (!ExprList.empty()) {
       S += "(";
-      ExprList.printWithSeperator(S, ", ");
+      ExprList.printWithComma(S);
       S += ")";
     }
     Type->print(S);
     if (!InitList.empty()) {
       S += "(";
-      InitList.printWithSeperator(S, ", ");
+      InitList.printWithComma(S);
       S += ")";
     }
+
   }
 };
 
 class DeleteExpr : public Expr {
   Node *Op;
   bool IsGlobal;
   bool IsArray;
 
 public:
   DeleteExpr(Node *Op_, bool IsGlobal_, bool IsArray_)
-      : Op(Op_), IsGlobal(IsGlobal_), IsArray(IsArray_) {}
+      : Op(Op_), IsGlobal(IsGlobal_), IsArray(IsArray_) {
+    ParameterPackSize = Op->ParameterPackSize;
+  }
 
   void printLeft(OutputStream &S) const override {
     if (IsGlobal)
       S += "::";
     S += "delete";
     if (IsArray)
       S += "[] ";
     Op->print(S);
   }
 };
 
 class PrefixExpr : public Expr {
   StringView Prefix;
   Node *Child;
 
 public:
-  PrefixExpr(StringView Prefix_, Node *Child_) : Prefix(Prefix_), Child(Child_) {}
+  PrefixExpr(StringView Prefix_, Node *Child_) : Prefix(Prefix_), Child(Child_) {
+    ParameterPackSize = Child->ParameterPackSize;
+  }
 
   void printLeft(OutputStream &S) const override {
     S += Prefix;
     S += "(";
     Child->print(S);
     S += ")";
   }
 };
 
 class FunctionParam : public Expr {
   StringView Number;
 
 public:
   FunctionParam(StringView Number_) : Number(Number_) {}
 
   void printLeft(OutputStream &S) const override {
     S += "fp";
     S += Number;
   }
 };
 
-class ExprList : public Expr {
-  NodeArray SubExprs;
-
-public:
-  ExprList(NodeArray SubExprs_) : SubExprs(SubExprs_) {}
-
-  void printLeft(OutputStream &S) const override {
-    S += "(";
-    SubExprs.printWithSeperator(S, ", ");
-    S += ")";
-  }
-};
-
 class ConversionExpr : public Expr {
+  const Node *Type;
   NodeArray Expressions;
-  NodeArray Types;
 
 public:
-  ConversionExpr(NodeArray Expressions_, NodeArray Types_)
-      : Expressions(Expressions_), Types(Types_) {}
+  ConversionExpr(const Node *Type_, NodeArray Expressions_)
+      : Type(Type_), Expressions(Expressions_) {
+    for (Node *E : Expressions)
+      ParameterPackSize = std::min(ParameterPackSize, E->ParameterPackSize);
+    ParameterPackSize = std::min(ParameterPackSize, Type->ParameterPackSize);
+  }
 
   void printLeft(OutputStream &S) const override {
     S += "(";
-    Expressions.printWithSeperator(S, ", ");
+    Type->print(S);
     S += ")(";
-    Types.printWithSeperator(S, ", ");
+    Expressions.printWithComma(S);
     S += ")";
   }
 };
 
 class ThrowExpr : public Expr {
   const Node *Op;
 
 public:
-  ThrowExpr(Node *Op_) : Op(Op_) {}
+  ThrowExpr(Node *Op_) : Op(Op_) {
+    ParameterPackSize = Op->ParameterPackSize;
+  }
 
   void printLeft(OutputStream &S) const override {
     S += "throw ";
     Op->print(S);
   }
 };
 
 class BoolExpr : public Expr {
   bool Value;
 
 public:
   BoolExpr(bool Value_) : Value(Value_) {}
 
   void printLeft(OutputStream &S) const override {
     S += Value ? StringView("true") : StringView("false");
   }
 };
 
 class IntegerCastExpr : public Expr {
   // ty(integer)
   Node *Ty;
   StringView Integer;
 
 public:
-  IntegerCastExpr(Node *Ty_, StringView Integer_) : Ty(Ty_), Integer(Integer_) {}
+  IntegerCastExpr(Node *Ty_, StringView Integer_) : Ty(Ty_), Integer(Integer_) {
+    ParameterPackSize = Ty->ParameterPackSize;
+  }
 
   void printLeft(OutputStream &S) const override {
     S += "(";
     Ty->print(S);
     S += ")";
     S += Integer;
   }
 };
public:
   void clear() { Last = First; }
 
   ~PODSmallVector() {
     if (!isInline())
       std::free(First);
   }
 };
 
-// Substitution table. This type is used to track the substitutions that are
-// known by the parser.
-template <size_t Size>
-class SubstitutionTable {
-  // Substitutions hold the actual entries in the table, and PackIndices tells
-  // us which entries are members of which pack. For example, if the
-  // substitutions we're tracking are: {int, {float, FooBar}, char}, with
-  // {float, FooBar} being a parameter pack, we represent the substitutions as:
-  // Substitutions: int, float, FooBar, char
-  // PackIndices:     0,             1,    3
-  // So, PackIndicies[I] holds the offset of the begin of the Ith pack, and
-  // PackIndices[I + 1] holds the offset of the end.
-  PODSmallVector<Node*, Size> Substitutions;
-  PODSmallVector<unsigned, Size> PackIndices;
-
-public:
-  // Add a substitution that represents a single name to the table. This is
-  // modeled as a parameter pack with just one element.
-  void pushSubstitution(Node* Entry) {
-    pushPack();
-    pushSubstitutionIntoPack(Entry);
-  }
-
-  // Add a new empty pack to the table. Subsequent calls to
-  // pushSubstitutionIntoPack() will add to this pack.
-  void pushPack() {
-    PackIndices.push_back(static_cast<unsigned>(Substitutions.size()));
-  }
-  void pushSubstitutionIntoPack(Node* Entry) {
-    assert(!PackIndices.empty() && "No pack to push substitution into!");
-    Substitutions.push_back(Entry);
-  }
-
-  // Remove the last pack from the table.
-  void popPack() {
-    unsigned Last = PackIndices.back();
-    PackIndices.pop_back();
-    Substitutions.dropBack(Last);
-  }
-
-  // For use in a range-for loop.
-  struct NodeRange {
-    Node** First;
-    Node** Last;
-    Node** begin() { return First; }
-    Node** end() { return Last; }
-  };
-
-  // Retrieve the Nth substitution. This is represented as a range, as the
-  // substitution could be referring to a parameter pack.
-  NodeRange nthSubstitution(size_t N) {
-    assert(PackIndices[N] <= Substitutions.size());
-    // The Nth parameter pack starts at offset PackIndices[N], and ends at
-    // PackIndices[N + 1].
-    Node** Begin = Substitutions.begin() + PackIndices[N];
-    Node** End;
-    if (N + 1 != PackIndices.size()) {
-      assert(PackIndices[N + 1] <= Substitutions.size());
-      End = Substitutions.begin() + PackIndices[N + 1];
-    } else
-      End = Substitutions.end();
-    assert(Begin <= End);
-    return NodeRange{Begin, End};
-  }
-
-  size_t size() const { return PackIndices.size(); }
-  bool empty() const { return PackIndices.empty(); }
-  void clear() {
-    Substitutions.clear();
-    PackIndices.clear();
-  }
-};
-
 struct Db
 {
     // Name stack, this is used by the parser to hold temporary names that were
     // parsed. The parser colapses multiple names into new nodes to construct
     // the AST. Once the parser is finished, names.size() == 1.
     PODSmallVector<Node*, 32> Names;
 
     // Substitution table. Itanium supports name substitutions as a means of
-    // compression. The string "S42_" refers to the 42nd entry in this table.
-    SubstitutionTable<32> Subs;
+    // compression. The string "S42_" refers to the 44nd entry (base-36) in this
+    // table.
+    PODSmallVector<Node*, 32> Subs;
 
     // Template parameter table. Like the above, but referenced like "T42_".
     // This has a smaller size compared to Subs and Names because it can be
     // stored on the stack.
-    SubstitutionTable<4> TemplateParams;
+    PODSmallVector<Node *, 8> TemplateParams;
 
     Qualifiers CV = QualNone;
     FunctionRefQual RefQuals = FrefQualNone;
     unsigned EncodingDepth = 0;
     bool ParsedCtorDtorCV = false;
     bool TagTemplates = true;
     bool FixForwardReferences = false;
     bool TryToParseTemplateArgs = true;
if (last - first >= 2)
                 break;
             case 'd':
                 db.Names.push_back(db.make<SpecialSubstitution>(SpecialSubKind::iostream));
                 first += 2;
                 break;
             case '_':
                 if (!db.Subs.empty())
                 {
-                    for (Node* n : db.Subs.nthSubstitution(0))
-                        db.Names.push_back(n);
+                    db.Names.push_back(db.Subs[0]);
                     first += 2;
                 }
                 break;
             default:
                 if (std::isdigit(first[1]) || std::isupper(first[1]))
                 {
                     size_t sub = 0;
                     const char* t = first+1;
if (last - first >= 2)
                         else
                             sub += static_cast<size_t>(*t - 'A') + 10;
                     }
                     if (t == last || *t != '_')
                         return first;
                     ++sub;
                     if (sub < db.Subs.size())
                     {
-                        for (Node* n : db.Subs.nthSubstitution(sub))
-                            db.Names.push_back(n);
+                        db.Names.push_back(db.Subs[sub]);
                         first = t+1;
                     }
                 }
                 break;
             }
         }
     }
     return first;
parse_template_param(const char* first, const char* last, Db& db)
     if (last - first >= 2)
     {
         if (*first == 'T')
         {
             if (first[1] == '_')
             {
                 if (!db.TemplateParams.empty())
                 {
-                    for (Node *t : db.TemplateParams.nthSubstitution(0))
-                        db.Names.push_back(t);
+                    db.Names.push_back(db.TemplateParams[0]);
                     first += 2;
                 }
                 else
                 {
                     db.Names.push_back(db.make<NameType>("T_"));
                     first += 2;
                     db.FixForwardReferences = true;
                 }
             }
             else if (isdigit(first[1]))
             {
                 const char* t = first+1;
                 size_t sub = static_cast<size_t>(*t - '0');
                 for (++t; t != last && isdigit(*t); ++t)
                 {
                     sub *= 10;
                     sub += static_cast<size_t>(*t - '0');
                 }
                 if (t == last || *t != '_')
                     return first;
                 ++sub;
                 if (sub < db.TemplateParams.size())
                 {
-                    for (Node *temp : db.TemplateParams.nthSubstitution(sub))
-                        db.Names.push_back(temp);
+                    db.Names.push_back(db.TemplateParams[sub]);
                     first = t+1;
                 }
                 else
                 {
                     db.Names.push_back(
                         db.make<NameType>(StringView(first, t + 1)));
                     first = t+1;
                     db.FixForwardReferences = true;

 
 // sp <expression>                                  # pack expansion
 
 const char*
 parse_pack_expansion(const char* first, const char* last, Db& db)
 {
     if (last - first >= 3 && first[0] == 's' && first[1] == 'p')
     {
+        size_t before = db.Names.size();
         const char* t = parse_expression(first+2, last, db);
+        if (before + 1 != db.Names.size())
+            return first;
         if (t != first+2)
             first = t;
+        db.Names.back() = db.make<ParameterPackExpansion>(db.Names.back());
     }
     return first;
 }
 
 // st <type>                                            # sizeof (a type)
 
 const char*
 parse_sizeof_type_expr(const char* first, const char* last, Db& db)

 const char*
 parse_sizeof_param_pack_expr(const char* first, const char* last, Db& db)
 {
     if (last - first >= 3 && first[0] == 's' && first[1] == 'Z' && first[2] == 'T')
     {
         size_t k0 = db.Names.size();
         const char* t = parse_template_param(first+2, last, db);
         size_t k1 = db.Names.size();
-        if (t != first+2 && k0 <= k1)
+        if (t != first+2 && k0 + 1 == k1)
         {
-            Node* sizeof_expr = db.make<SizeofParamPackExpr>(
-                db.popTrailingNodeArray(k0));
-            db.Names.push_back(sizeof_expr);
+            db.Names.back() = db.make<SizeofParamPackExpr>(db.Names.back());
             first = t;
         }
     }
     return first;
 }
 
 // <function-param> ::= fp <top-level CV-Qualifiers> _                                     # L == 0, first parameter
 //                  ::= fp <top-level CV-Qualifiers> <parameter-2 non-negative number> _   # L == 0, second and later parameters
if (first != last)
         {
         case 'T':
           {
             size_t k0 = db.Names.size();
             t = parse_template_param(first, last, db);
             size_t k1 = db.Names.size();
             if (t != first && k1 == k0 + 1)
             {
-                db.Subs.pushSubstitution(db.Names.back());
+                db.Subs.push_back(db.Names.back());
                 first = t;
             }
             else
             {
                 for (; k1 != k0; --k1)
                     db.Names.pop_back();
             }
             break;
           }
         case 'D':
             t = parse_decltype(first, last, db);
             if (t != first)
             {
                 if (db.Names.empty())
                     return first;
-                db.Subs.pushSubstitution(db.Names.back());
+                db.Subs.push_back(db.Names.back());
                 first = t;
             }
             break;
         case 'S':
             t = parse_substitution(first, last, db);
             if (t != first)
                 first = t;
             else
             {
                 if (last - first > 2 && first[1] == 't')
                 {
                     t = parse_unqualified_name(first+2, last, db);
                     if (t != first+2)
                     {
                         if (db.Names.empty())
                             return first;
                         db.Names.back() =
                             db.make<StdQualifiedName>(db.Names.back());
-                        db.Subs.pushSubstitution(db.Names.back());
+                        db.Subs.push_back(db.Names.back());
                         first = t;
                     }
                 }
             }
             break;
        }
     }
     return first;

 
 const char*
 parse_conversion_expr(const char* first, const char* last, Db& db)
 {
     if (last - first >= 3 && first[0] == 'c' && first[1] == 'v')
     {
         bool TryToParseTemplateArgs = db.TryToParseTemplateArgs;
         db.TryToParseTemplateArgs = false;
-        size_t type_begin = db.Names.size();
+        size_t type_index = db.Names.size();
         const char* t = parse_type(first+2, last, db);
         db.TryToParseTemplateArgs = TryToParseTemplateArgs;
         if (t != first+2 && t != last)
         {
             size_t expr_list_begin = db.Names.size();
             if (*t != '_')
             {
                 const char* t1 = parse_expression(t, last, db);
if (last - first >= 3 && first[0] == 'c' && first[1] == 'v')
                         if (t1 == t || t1 == last)
                             return first;
                         t = t1;
                     }
                 }
                 ++t;
             }
             if (db.Names.size() < expr_list_begin ||
-                type_begin > expr_list_begin)
+                type_index + 1 != expr_list_begin)
                 return first;
             NodeArray expressions = db.makeNodeArray(
                 db.Names.begin() + (long)expr_list_begin, db.Names.end());
-            NodeArray types = db.makeNodeArray(
-                db.Names.begin() + (long)type_begin,
-                db.Names.begin() + (long)expr_list_begin);
             auto* conv_expr = db.make<ConversionExpr>(
-                types, expressions);
-            db.Names.dropBack(type_begin);
+                db.Names[type_index], expressions);
+            db.Names.dropBack(type_index);
             db.Names.push_back(conv_expr);
             first = t;
         }
     }
     return first;
 }
 
 // pt <expression> <expression>                    # expr->name
if (first != last)
                 Qualifiers cv = QualNone;
                 const char* t = parse_cv_qualifiers(first, last, cv);
                 if (t != first)
                 {
                     bool is_function = *t == 'F';
                     size_t k0 = db.Names.size();
                     const char* t1 = parse_type(t, last, db);
                     size_t k1 = db.Names.size();
-                    if (t1 != t)
+                    if (t1 != t && k0 + 1 == k1)
                     {
                         if (is_function)
-                            db.Subs.popPack();
-                        db.Subs.pushPack();
-                        for (size_t k = k0; k < k1; ++k)
+                            db.Subs.pop_back();
+                        if (cv)
                         {
-                            if (cv) {
-                                if (is_function)
-                                    db.Names[k] = db.make<FunctionQualType>(
-                                        db.Names[k], cv);
-                                else
-                                    db.Names[k] =
-                                        db.make<QualType>(db.Names[k], cv);
-                            }
-                            db.Subs.pushSubstitutionIntoPack(db.Names[k]);
+                                db.Names.back() = db.make<FunctionQualType>(
+                                    db.Names.back(), cv);
+                                db.Names.back() =
+                                    db.make<QualType>(db.Names.back(), cv);
                         }
+                        db.Subs.push_back(db.Names.back());
                         first = t1;
                     }
                 }
               }
                 break;
             default:
               {
                 const char* t = parse_builtin_type(first, last, db);
                 if (t != first)
                 {
                     first = t;
                 }
                 else
                 {
                     switch (*first)
                     {
                     case 'A':
                         t = parse_array_type(first, last, db);
                         if (t != first)
                         {
                             if (db.Names.empty())
                                 return first;
                             first = t;
-                            db.Subs.pushSubstitution(db.Names.back());
+                            db.Subs.push_back(db.Names.back());
                         }
                         break;
                     case 'C':
                         t = parse_type(first+1, last, db);
                         if (t != first+1)
                         {
                             if (db.Names.empty())
                                 return first;
                             db.Names.back() = db.make<PostfixQualifiedType>(
                                 db.Names.back(), " complex");
                             first = t;
-                            db.Subs.pushSubstitution(db.Names.back());
+                            db.Subs.push_back(db.Names.back());
                         }
                         break;
                     case 'F':
                         t = parse_function_type(first, last, db);
                         if (t != first)
                         {
                             if (db.Names.empty())
                                 return first;
                             first = t;
-                            db.Subs.pushSubstitution(db.Names.back());
+                            db.Subs.push_back(db.Names.back());
                         }
                         break;
                     case 'G':
                         t = parse_type(first+1, last, db);
                         if (t != first+1)
                         {
                             if (db.Names.empty())
                                 return first;
                             db.Names.back() = db.make<PostfixQualifiedType>(
                                 db.Names.back(), " imaginary");
                             first = t;
-                            db.Subs.pushSubstitution(db.Names.back());
+                            db.Subs.push_back(db.Names.back());
                         }
                         break;
                     case 'M':
                         t = parse_pointer_to_member_type(first, last, db);
                         if (t != first)
                         {
                             if (db.Names.empty())
                                 return first;
                             first = t;
-                            db.Subs.pushSubstitution(db.Names.back());
+                            db.Subs.push_back(db.Names.back());
                         }
                         break;
                     case 'O':
                       {
                         size_t k0 = db.Names.size();
                         t = parse_type(first+1, last, db);
                         size_t k1 = db.Names.size();
-                        if (t != first+1)
-                        {
-                            db.Subs.pushPack();
-                            for (size_t k = k0; k < k1; ++k)
-                            {
-                                db.Names[k] =
-                                    db.make<RValueReferenceType>(db.Names[k]);
-                                db.Subs.pushSubstitutionIntoPack(db.Names[k]);
-                            }
+                        if (t != first+1 && k0 + 1 == k1)
+                            db.Names.back() =
+                                db.make<RValueReferenceType>(db.Names.back());
+                            db.Subs.push_back(db.Names.back());
                             first = t;
                         }
                         break;
                       }
                     case 'P':
                       {
                         size_t k0 = db.Names.size();
                         t = parse_type(first+1, last, db);
                         size_t k1 = db.Names.size();
-                        if (t != first+1)
-                        {
-                            db.Subs.pushPack();
-                            for (size_t k = k0; k < k1; ++k)
-                            {
-                                db.Names[k] = db.make<PointerType>(db.Names[k]);
-                                db.Subs.pushSubstitutionIntoPack(db.Names[k]);
-                            }
+                        if (t != first+1 && k0 + 1 == k1)
+                            db.Names.back() = db.make<PointerType>(db.Names.back());
+                            db.Subs.push_back(db.Names.back());
                             first = t;
                         }
                         break;
                       }
                     case 'R':
                       {
                         size_t k0 = db.Names.size();
                         t = parse_type(first+1, last, db);
                         size_t k1 = db.Names.size();
-                        if (t != first+1)
+                        if (t != first+1 && k0 + 1 == k1)
                         {
-                            db.Subs.pushPack();
-                            for (size_t k = k0; k < k1; ++k)
-                            {
-                                db.Names[k] =
-                                    db.make<LValueReferenceType>(db.Names[k]);
-                                db.Subs.pushSubstitutionIntoPack(db.Names[k]);
-                            }
+                            db.Names.back() =
+                                db.make<LValueReferenceType>(db.Names.back());
+                            db.Subs.push_back(db.Names.back());
                             first = t;
                         }
                         break;
                       }
                     case 'T':
                       {
                         size_t k0 = db.Names.size();
                         t = parse_template_param(first, last, db);
                         size_t k1 = db.Names.size();
-                        if (t != first)
+                        if (t != first && k0 + 1 == k1)
                         {
-                            db.Subs.pushPack();
-                            for (size_t k = k0; k < k1; ++k)
-                                db.Subs.pushSubstitutionIntoPack(db.Names[k]);
+                            db.Subs.push_back(db.Names.back());
                             if (db.TryToParseTemplateArgs && k1 == k0+1)
                             {
                                 const char* t1 = parse_template_args(t, last, db);
                                 if (t1 != t)
                                 {
                                     auto args = db.Names.back();
                                     db.Names.pop_back();
                                     db.Names.back() = db.make<
                                         NameWithTemplateArgs>(
                                         db.Names.back(), args);
-                                    db.Subs.pushSubstitution(db.Names.back());
+                                    db.Subs.push_back(db.Names.back());
                                     t = t1;
                                 }
                             }
                             first = t;
                         }
                         break;
                       }
                     case 'U':
if (first != last)
                                         {
                                             db.Names.back() = db.make<ObjCProtoName>(type, db.Names.back());
                                         }
                                         else
                                         {
                                             db.Names.push_back(db.make<VendorExtQualType>(type, proto));
                                         }
                                     }
-                                    db.Subs.pushSubstitution(db.Names.back());
+                                    db.Subs.push_back(db.Names.back());
                                     first = t2;
                                 }
                             }
                         }
                         break;
                     case 'S':
                         if (first+1 != last && first[1] == 't')
                         {
                             t = parse_name(first, last, db);
                             if (t != first)
                             {
                                 if (db.Names.empty())
                                     return first;
-                                db.Subs.pushSubstitution(db.Names.back());
+                                db.Subs.push_back(db.Names.back());
                                 first = t;
                             }
                         }
                         else
                         {
                             t = parse_substitution(first, last, db);
                             if (t != first)
                             {
                                 first = t;
                                 // Parsed a substitution.  If the substitution is a
                                 //  <template-param> it might be followed by <template-args>.
                                 if (db.TryToParseTemplateArgs)
                                 {
                                     t = parse_template_args(first, last, db);
                                     if (t != first)
                                     {
                                         if (db.Names.size() < 2)
                                             return first;
                                         auto template_args = db.Names.back();
                                         db.Names.pop_back();
                                         db.Names.back() = db.make<
                                           NameWithTemplateArgs>(
                                               db.Names.back(), template_args);
                                         // Need to create substitution for <template-template-param> <template-args>
-                                        db.Subs.pushSubstitution(db.Names.back());
+                                        db.Subs.push_back(db.Names.back());
                                         first = t;
                                     }
                                 }
                             }
                         }
                         break;
                     case 'D':
                         if (first+1 != last)
                         {
                             switch (first[1])
                             {
                             case 'p':
                               {
                                 size_t k0 = db.Names.size();
                                 t = parse_type(first+2, last, db);
                                 size_t k1 = db.Names.size();
-                                if (t != first+2)
+                                if (t != first+2 && k0 + 1 == k1)
                                 {
-                                    db.Subs.pushPack();
-                                    for (size_t k = k0; k < k1; ++k)
-                                        db.Subs.pushSubstitutionIntoPack(db.Names[k]);
+                                    db.Names.back() =
+                                        db.make<ParameterPackExpansion>(
+                                            db.Names.back());
+                                    db.Subs.push_back(db.Names.back());
                                     first = t;
                                     return first;
                                 }
                                 break;
                               }
                             case 't':
                             case 'T':
                                 t = parse_decltype(first, last, db);
                                 if (t != first)
                                 {
                                     if (db.Names.empty())
                                         return first;
-                                    db.Subs.pushSubstitution(db.Names.back());
+                                    db.Subs.push_back(db.Names.back());
                                     first = t;
                                     return first;
                                 }
                                 break;
                             case 'v':
                                 t = parse_vector_type(first, last, db);
                                 if (t != first)
                                 {
                                     if (db.Names.empty())
                                         return first;
-                                    db.Subs.pushSubstitution(db.Names.back());
+                                    db.Subs.push_back(db.Names.back());
                                     first = t;
                                     return first;
                                 }
                                 break;
                             }
                         }
                         _LIBCPP_FALLTHROUGH();
                     default:
                         // must check for builtin-types before class-enum-types to avoid
                         // ambiguities with operator-names
                         t = parse_builtin_type(first, last, db);
                         if (t != first)
                         {
                             first = t;
                         }
                         else
                         {
                             t = parse_name(first, last, db);
                             if (t != first)
                             {
                                 if (db.Names.empty())
                                     return first;
-                                db.Subs.pushSubstitution(db.Names.back());
+                                db.Subs.push_back(db.Names.back());
                                 first = t;
                             }
                         }
                         break;
                     }
               }
                 break;
             }
parse_expression(const char* first, const char* last, Db& db)
     return first;
 }
 
 // <template-arg> ::= <type>                                             # type or template
 //                ::= X <expression> E                                   # expression
 //                ::= <expr-primary>                                     # simple expressions
 //                ::= J <template-arg>* E                                # argument pack
 //                ::= LZ <encoding> E                                    # extension
-
 const char*
 parse_template_arg(const char* first, const char* last, Db& db)
 {
     if (first != last)
     {
         const char* t;
         switch (*first)
         {
         case 'X':
             t = parse_expression(first+1, last, db);
             if (t != first+1)
             {
                 if (t != last && *t == 'E')
                     first = t+1;
             }
             break;
-        case 'J':
+        case 'J': {
             t = first+1;
             if (t == last)
                 return first;
+            size_t ArgsBegin = db.Names.size();
             while (*t != 'E')
             {
                 const char* t1 = parse_template_arg(t, last, db);
                 if (t1 == t)
                     return first;
                 t = t1;
             }
+            NodeArray Args = db.popTrailingNodeArray(ArgsBegin);
+            db.Names.push_back(db.make<TemplateArgumentPack>(Args));
             first = t+1;
             break;
+        }
         case 'L':
             // <expr-primary> or LZ <encoding> E
             if (first+1 != last && first[1] == 'Z')
             {
                 t = parse_encoding(first+2, last, db);
                 if (t != first+2 && t != last && *t == 'E')
                     first = t+1;
             }
             else
                 first = parse_expr_primary(first, last, db);
             break;
         default:
             // <type>
             first = parse_type(first, last, db);
             break;
         }
     }
     return first;
 }
 
 // <template-args> ::= I <template-arg>* E
 //     extension, the abi says <template-arg>+
-
 const char*
 parse_template_args(const char* first, const char* last, Db& db)
 {
     if (last - first >= 2 && *first == 'I')
     {
         if (db.TagTemplates)
             db.TemplateParams.clear();
         const char* t = first+1;
         size_t begin_idx = db.Names.size();
         while (*t != 'E')
         {
             if (db.TagTemplates)
             {
                 auto TmpParams = std::move(db.TemplateParams);
                 size_t k0 = db.Names.size();
                 const char* t1 = parse_template_arg(t, last, db);
                 size_t k1 = db.Names.size();
                 db.TemplateParams = std::move(TmpParams);
-
-                if (t1 == t || t1 == last || k0 > k1)
+                if (t1 == t || t1 == last || k0 + 1 != k1)
                     return first;
-                db.TemplateParams.pushPack();
-                for (size_t k = k0; k < k1; ++k)
-                    db.TemplateParams.pushSubstitutionIntoPack(db.Names[k]);
+                Node *TableEntry = db.Names.back();
+                if (TableEntry->getKind() == Node::KTemplateArgumentPack)
+                  TableEntry = db.make<ParameterPack>(
+                      static_cast<TemplateArgumentPack*>(TableEntry)
+                          ->getElements());
+                db.TemplateParams.push_back(TableEntry);
                 t = t1;
                 continue;
             }
             size_t k0 = db.Names.size();
             const char* t1 = parse_template_arg(t, last, db);
             size_t k1 = db.Names.size();
             if (t1 == t || t1 == last || k0 > k1)
               return first;
             t = t1;
         }
         if (begin_idx > db.Names.size())
             return first;
         first = t + 1;
-        TemplateParams* tp = db.make<TemplateParams>(
+        auto *tp = db.make<TemplateArgs>(
             db.popTrailingNodeArray(begin_idx));
         db.Names.push_back(tp);
     }
     return first;
 }
 
 // <nested-name> ::= N [<CV-Qualifiers>] [<ref-qualifier>] <prefix> <unqualified-name> E
 //               ::= N [<CV-Qualifiers>] [<ref-qualifier>] <template-prefix> <template-args> E
if (first != last && *first == 'N')
                     if (db.Names.size() < 2)
                         return first;
                     auto name = db.Names.back();
                     db.Names.pop_back();
                     if (db.Names.back()->K != Node::KEmptyName)
                     {
                         db.Names.back() = db.make<QualifiedName>(
                             db.Names.back(), name);
-                        db.Subs.pushSubstitution(db.Names.back());
+                        db.Subs.push_back(db.Names.back());
                     }
                     else
                         db.Names.back() = name;
                     pop_subs = true;
                     t0 = t1;
                 }
                 else
                     return first;
                 break;
             case 'T':
                 t1 = parse_template_param(t0, last, db);
                 if (t1 != t0 && t1 != last)
                 {
                     if (db.Names.size() < 2)
                         return first;
                     auto name = db.Names.back();
                     db.Names.pop_back();
                     if (db.Names.back()->K != Node::KEmptyName)
                         db.Names.back() =
                             db.make<QualifiedName>(db.Names.back(), name);
                     else
                         db.Names.back() = name;
-                    db.Subs.pushSubstitution(db.Names.back());
+                    db.Subs.push_back(db.Names.back());
                     pop_subs = true;
                     t0 = t1;
                 }
                 else
                     return first;
                 break;
             case 'D':
                 if (t0 + 1 != last && t0[1] != 't' && t0[1] != 'T')
                     goto do_parse_unqualified_name;
                 t1 = parse_decltype(t0, last, db);
                 if (t1 != t0 && t1 != last)
                 {
                     if (db.Names.size() < 2)
                         return first;
                     auto name = db.Names.back();
                     db.Names.pop_back();
                     if (db.Names.back()->K != Node::KEmptyName)
                         db.Names.back() =
                             db.make<QualifiedName>(db.Names.back(), name);
                     else
                         db.Names.back() = name;
-                    db.Subs.pushSubstitution(db.Names.back());
+                    db.Subs.push_back(db.Names.back());
                     pop_subs = true;
                     t0 = t1;
                 }
                 else
                     return first;
                 break;
             case 'I':
                 t1 = parse_template_args(t0, last, db);
                 if (t1 != t0 && t1 != last)
                 {
                     if (db.Names.size() < 2)
                         return first;
                     auto name = db.Names.back();
                     db.Names.pop_back();
                     db.Names.back() = db.make<NameWithTemplateArgs>(
                         db.Names.back(), name);
-                    db.Subs.pushSubstitution(db.Names.back());
+                    db.Subs.push_back(db.Names.back());
                     t0 = t1;
                     component_ends_with_template_args = true;
                 }
                 else
                     return first;
                 break;
             case 'L':
                 if (++t0 == last)
                     return first;
                 break;
             default:
             do_parse_unqualified_name:
                 t1 = parse_unqualified_name(t0, last, db);
                 if (t1 != t0 && t1 != last)
                 {
                     if (db.Names.size() < 2)
                         return first;
                     auto name = db.Names.back();
                     db.Names.pop_back();
                     if (db.Names.back()->K != Node::KEmptyName)
                         db.Names.back() =
                             db.make<QualifiedName>(db.Names.back(), name);
                     else
                         db.Names.back() = name;
-                    db.Subs.pushSubstitution(db.Names.back());
+                    db.Subs.push_back(db.Names.back());
                     pop_subs = true;
                     t0 = t1;
                 }
                 else
                     return first;
             }
         }
         first = t0 + 1;
         db.CV = cv;
         if (pop_subs && !db.Subs.empty())
-            db.Subs.popPack();
+            db.Subs.pop_back();
         if (ends_with_template_args)
             *ends_with_template_args = component_ends_with_template_args;
     }
     return first;
 }
 
 // <discriminator> := _ <non-negative number>      # when number < 10
 //                 := __ <non-negative number> _   # when number >= 10
if (last - first >= 2)
           {
             const char* t1 = parse_unscoped_name(t0, last, db);
             if (t1 != t0)
             {
                 if (t1 != last && *t1 == 'I')  // <unscoped-template-name> <template-args>
                 {
                     if (db.Names.empty())
                         return first;
-                    db.Subs.pushSubstitution(db.Names.back());
+                    db.Subs.push_back(db.Names.back());
                     t0 = t1;
                     t1 = parse_template_args(t0, last, db);
                     if (t1 != t0)
                     {
                         if (db.Names.size() < 2)
                             return first;
                         auto tmp = db.Names.back();
                         db.Names.pop_back();
if (first != last)
 
                     if (t != last && *t == 'v')
                     {
                         ++t;
                         if (db.Names.empty())
                             return first;
                         Node* name = db.Names.back();
                         db.Names.pop_back();
-                        result = db.make<TopLevelFunctionDecl>(
+                        result = db.make<FunctionEncoding>(
                             return_type, name, NodeArray());
                     }
                     else
                     {
                         size_t params_begin = db.Names.size();
                         while (true)
                         {
                             t2 = parse_type(t, last, db);
                             if (t2 == t)
                                 break;
                             t = t2;
                         }
                         if (db.Names.size() < params_begin)
                             return first;
                         NodeArray params =
                             db.popTrailingNodeArray(params_begin);
                         if (db.Names.empty())
                             return first;
                         Node* name = db.Names.back();
                         db.Names.pop_back();
-                        result = db.make<TopLevelFunctionDecl>(
+                        result = db.make<FunctionEncoding>(
                             return_type, name, params);
                     }
                     if (ref != FrefQualNone)
                         result = db.make<FunctionRefQualType>(result, ref);
                     if (cv != QualNone)
                         result = db.make<FunctionQualType>(result, cv);
                     db.Names.push_back(result);
                     first = t;
if (first != last && *first == '.')
             return first;
         db.Names.back() =
             db.make<DotSuffix>(db.Names.back(), StringView(first, last));
         first = last;
     }
     return first;
 }
 
+enum {
+    unknown_error = -4,
+    invalid_args = -3,
+    invalid_mangled_name,
+    memory_alloc_failure,
+    success
+};
+
 // <block-involcaton-function> ___Z<encoding>_block_invoke
 // <block-involcaton-function> ___Z<encoding>_block_invoke<decimal-digit>+
 // <block-involcaton-function> ___Z<encoding>_block_invoke_<decimal-digit>+
 // <mangled-name> ::= _Z<encoding>
 //                ::= <type>
-
 void
 demangle(const char* first, const char* last, Db& db, int& status)
 {
     if (first >= last)
     {
         status = invalid_mangled_name;
         return;
     }
else
             status = invalid_mangled_name;
     }
     if (status == success && db.Names.empty())
         status = invalid_mangled_name;
 }
 
 }  // unnamed namespace
 
+
+namespace __cxxabiv1 {
 extern "C" _LIBCXXABI_FUNC_VIS char *
 __cxa_demangle(const char *mangled_name, char *buf, size_t *n, int *status) {
     if (mangled_name == nullptr || (buf != nullptr && n == nullptr))
     {
         if (status)
             *status = invalid_args;
         return nullptr;
     }
if (internal_status == success && db.FixForwardReferences &&
         db.TagTemplates = false;
         db.Names.clear();
         db.Subs.clear();
         demangle(mangled_name, mangled_name + len, db, internal_status);
         if (db.FixForwardReferences)
             internal_status = invalid_mangled_name;
     }
 
+    if (internal_status == success &&
+        db.Names.back()->containsUnexpandedParameterPack())
+        internal_status = invalid_mangled_name;
+
     if (internal_status == success)
     {
         if (!buf)
         {
             internal_size = 1024;
             buf = static_cast<char*>(std::malloc(internal_size));
         }
 
if (internal_status == success)
             internal_status = memory_alloc_failure;
     }
     else
         buf = nullptr;
     if (status)
         *status = internal_status;
     return buf;
 }
-
 }  // __cxxabiv1

libcxxabi/trunk/test/test_demangle.pass.cpp

//    {"_Z1fM1XRFivEMS_OFivEMS_KOFivE", "f(int (X::*)() &, int (X::*)() &&, int (X::*)() const &&)"},
     {"_Z1fIiEDTeqfp_LDnEEPT_", "decltype((fp) == (std::nullptr_t)) f<int>(int*)"},
     {"_Z1fIiEDTeqfp1_LDnEEicPT_", "decltype((fp1) == (std::nullptr_t)) f<int>(int, char, int*)"},
     {"_ZZN1S1fEiiEd0_NKUlvE_clEv", "S::f(int, int)::'lambda'()::operator()() const"},
     {"_Z3fooPM2ABi", "foo(int AB::**)"},
     {"_Z1rM1GFivEMS_KFivES_M1HFivES1_4whatIKS_E5what2IS8_ES3_", "r(int (G::*)(), int (G::*)() const, G, int (H::*)(), int (G::*)(), what<G const>, what2<G const>, int (G::*)() const)"},
     {"_Z1fPU11objcproto1A11objc_object", "f(id<A>)"},
     {"_Z1fPKU11objcproto1A7NSArray", "f(NSArray<A> const*)"},
     {"_ZNK1AIJ1Z1Y1XEEcv1BIJDpPT_EEIJS2_S1_S0_EEEv", "A<Z, Y, X>::operator B<X*, Y*, Z*><X, Y, Z>() const"},
-    {"_ZNK3Ncr6Silver7Utility6detail12CallOnThreadIZ53-[DeploymentSetupController handleManualServerEntry:]E3$_5EclIJEEEDTclclL_ZNS2_4getTIS4_EERT_vEEspclsr3stdE7forwardIT_Efp_EEEDpOSA_", "decltype(-[DeploymentSetupController handleManualServerEntry:]::$_5& Ncr::Silver::Utility::detail::getT<-[DeploymentSetupController handleManualServerEntry:]::$_5>()()(std::forward<-[DeploymentSetupController handleManualServerEntry:]::$_5>(fp))) Ncr::Silver::Utility::detail::CallOnThread<-[DeploymentSetupController handleManualServerEntry:]::$_5>::operator()<>(-[DeploymentSetupController handleManualServerEntry:]::$_5&&) const"},
+    {"_ZNK3Ncr6Silver7Utility6detail12CallOnThreadIZ53-[DeploymentSetupController handleManualServerEntry:]E3$_5EclIJEEEDTclclL_ZNS2_4getTIS4_EERT_vEEspclsr3stdE7forwardIT_Efp_EEEDpOSA_", "decltype(-[DeploymentSetupController handleManualServerEntry:]::$_5& Ncr::Silver::Utility::detail::getT<-[DeploymentSetupController handleManualServerEntry:]::$_5>()()(std::forward<-[DeploymentSetupController handleManualServerEntry:]::$_5>(fp)...)) Ncr::Silver::Utility::detail::CallOnThread<-[DeploymentSetupController handleManualServerEntry:]::$_5>::operator()<>(-[DeploymentSetupController handleManualServerEntry:]::$_5&&...) const"},
     {"_Zli2_xy", "operator\"\" _x(unsigned long long)"},
     {"_Z1fIiEDcT_", "decltype(auto) f<int>(int)"},
     {"_ZZ4testvEN1g3fooE5Point", "test()::g::foo(Point)"},
     {"_ZThn12_NSt9strstreamD0Ev",   "non-virtual thunk to std::strstream::~strstream()"},
     {"_ZTv0_n12_NSt9strstreamD0Ev",     "virtual thunk to std::strstream::~strstream()"},
 
     // NOTE: disable this test since it is a negative test case, you cannot demangle a non-mangled symbol
     // {"\x6D", nullptr},   // This use to crash with ASAN
     {"_ZTIU4_farrVKPi", "typeinfo for int* const volatile restrict _far"},
 
     // mangled names can include type manglings too, which don't start with _Z:
     {"i", "int"},
 
     {"PKFvRiE", "void (*)(int&) const"},
     {"PVFvRmOE", "void (*)(unsigned long&) volatile &&"},
     {"PFvRmOE", "void (*)(unsigned long&) &&"},
     {"_ZTW1x", "thread-local wrapper routine for x"},
     {"_ZTHN3fooE", "thread-local initialization routine for foo"},
-    {"_Z4algoIJiiiEEvZ1gEUlT_E_", "void algo<int, int, int>(g::'lambda'(int, int, int))"},
+    {"_Z4algoIJiiiEEvZ1gEUlDpT_E_", "void algo<int, int, int>(g::'lambda'(int, int, int))"},
     // attribute abi_tag
     {"_Z1fB3foov", "f[abi:foo]()"},
     {"_Z1fB3fooB3barv", "f[abi:foo][abi:bar]()"},
     {"_ZN1SB5outer1fB5innerEv", "S[abi:outer]::f[abi:inner]()"},
     {"_ZN1SC2B8ctor_tagEv", "S::S[abi:ctor_tag]()"},
     {"_ZplB4MERP1SS_", "operator+[abi:MERP](S, S)"},
+
+    {"_Z1fIJifcEEvDp5unaryIT_E", "void f<int, float, char>(unary<int>, unary<float>, unary<char>)"},
+    {"_Z1fIJEJiEEvDpT_DpT0_", "void f<int>(int)"},
+    {"_Z1fIJicEEvDp7MuncherIAstT__S1_E", "void f<int, char>(Muncher<int [sizeof (int)]>, Muncher<char [sizeof (char)]>)"},
+    {"_ZN1SIJifcEE1fIJdjEEEiDp4MerpIJifcT_EE", "int S<int, float, char>::f<double, unsigned int>(Merp<int, float, char, double>, Merp<int, float, char, unsigned int>)"},
+    {"_Z1pIJicEEiDp4MerpIXsZT_EJT_EE", "int p<int, char>(Merp<sizeof...(int, char), int>, Merp<sizeof...(int, char), char>)"},
 };
 
 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];

libcxxabi/trunk/test/unittest_demangle.pass.cpp

void testPODSmallVector() {
     }
     for (int x : PSV1) {
       assert(false);
       (void)x;
     }
   }
 }
 
-void testSubstitutionTable() {
-  {
-    SubstitutionTable<2> Tab;
-
-    NameType Names[] = {{"MERP"}, {"MARP"}, {"MAMP"}};
-    Tab.pushPack();
-    Tab.pushSubstitutionIntoPack(&Names[0]);
-    Tab.pushSubstitutionIntoPack(&Names[1]);
-    Tab.pushSubstitutionIntoPack(&Names[2]);
-
-    int Index = 0;
-    for (Node* N : Tab.nthSubstitution(0)) {
-      assert(static_cast<NameType*>(N)->getName() == Names[Index].getName());
-      ++Index;
-    }
-    assert(Index == 3);
-
-    Tab.popPack();
-    assert(Tab.empty() && Tab.size() == 0);
-    Tab.pushSubstitution(&Names[0]);
-    Tab.pushSubstitution(&Names[1]);
-    assert(!Tab.empty() && Tab.size() == 2);
-
-    int I = 0;
-    for (Node* N : Tab.nthSubstitution(0)) {
-      assert(static_cast<NameType*>(N)->getName() == "MERP");
-      assert(I == 0);
-      ++I;
-    }
-    for (Node* N : Tab.nthSubstitution(1)) {
-      assert(static_cast<NameType*>(N)->getName() == "MARP");
-      assert(I == 1);
-      ++I;
-    }
-  }
-}
-
 int main() {
   testPODSmallVector();
-  testSubstitutionTable();
 }