[libcxxabi][demangler] Improve representation of substitutions/templates

[erik.pilkington]

Summary

This patch changes the demangler so that it represents substitutions/templates more linearly. Previously, substitions were represented by a vector<vector<Node*>> and template parameter substitutions by a vector<vector<vector<Node*>>>! I wrote a comment in SubTable describing how this is done.
This patch gives a 20%-25% time reduction to demangle the symbols in LLVM, a 25% reduction in code size for the demangler on my machine, and makes the demangler a lot easier to read, IMO.

Thanks for taking a look!
Erik

[dexonsmith]

This looks like a great improvement. I've littered the patch with nit-picks, but my main concern is that there aren't any unit tests for the new data structures. I wonder if there's a hacky way to set that up...

src/cxa_demangle.cpp

1460–1461 ↗

(On Diff #110080)

This seems like a facility that should/could be unit tested (in C++).

I realize there's no precedent for that for the demangler. Perhaps this file could be #included by a test file:

// unittest/PODSmallVectorTest.h
#include "../src/cxa_demangle.cpp"

namespace {

TEST(PODSmallVectorTest, ...) {
}

} // namespace

Thoughts?

1462 ↗

(On Diff #110080)

Please add an assertion string, such as "T is required to be a plain-old data type".

1499–1501 ↗

(On Diff #110080)

This is identical to code in the move constructor. Separate it out into a helper?

1511–1517 ↗

(On Diff #110080)

Helper?

1527–1535 ↗

(On Diff #110080)

Should we assert when nullptr is returned from std::malloc or std::realloc?

1540–1542 ↗

(On Diff #110080)

Assertions on popping/dropping past empty?

1549–1550 ↗

(On Diff #110080)

Assertions on invalid access?

1562 ↗

(On Diff #110080)

As I read this patch, I keep reading "sub" as a prefix. Can we just spell this out as "SubstitutionTable"?

Also, this probably deserves unit tests as well.

1577–1580 ↗

(On Diff #110080)

Can/should this be implemented using pushPack() and pushSubIntoPack()?

1585 ↗

(On Diff #110080)

Do you need to assert that pushPack has been called at least once (i.e., !PackIndices.empty())?

1595 ↗

(On Diff #110080)

Perhaps NodeRange would be more clear.

1596–1599 ↗

(On Diff #110080)

Please be consistent with pointer style in this patch.

• I suspect the rest of the file attaches to the type, i.e., Node** First, which is why I didn't comment earlier on, e.g., Node* Entry.
• LLVM style is to attach to the name, like here.

I have a slight preference for switching toward LLVM style, but if the file consistently uses pointers attached to types, that's fine too. (Just be consistent within the patch.)

1602 ↗

(On Diff #110080)

This could perhaps use a comment. At least, inside the function to explain the math.

1603 ↗

(On Diff #110080)

Once you add this assertion to operator[] you can delete it here.

1604 ↗

(On Diff #110080)

Should there be some assertion on Subs.size() here? Perhaps, if so, this should be &Subs[PackIndices[N]], so that Subs.operator[]() handles it for you. Same below.

1605–1607 ↗

(On Diff #110080)

Does this deserve its own helper function (e.g., packEnd())? (I haven't read ahead to see if this logic is duplicated anywhere; probably not a separate function if it's not duplicated.)

1621–1631 ↗

(On Diff #110080)

How much have you thought about these sizes (32, 32, and 4)? Any evidence to back up these specific choices?

[dexonsmith]

Oh, also found a couple of things you should likely split into prep commits to simplify this patch.

src/cxa_demangle.cpp

1575–1577 ↗

(On Diff #110080)

• Why not rename names as well?
• Please rename these in a separate prep commit to minimize noise on the final patch.

[erik.pilkington]

Address review comments.
Thanks!
Erik

src/cxa_demangle.cpp

1575–1577 ↗

(On Diff #110080)

Sure, r310415.

1604 ↗

(On Diff #110080)

We can't use operator[] here because if all we have is an empty parameter pack then &Subs[PackIndices[N]] needs to point the the end() iterator, which is out of bounds. The new patch adds an assert though.

1621–1631 ↗

(On Diff #110080)

Yep, 32 is enough for the Subs table/names to never overflow when demangling the symbols in LLVM, and 4 seldom overflows TemplateParams. TemplateParams is temporary held on the stack in parse_template_args(), so I wanted it to be smaller.

[dexonsmith]

I have a few more nitpicks; LGTM after you fix those.

src/cxa_demangle.cpp

1626–1630 ↗

(On Diff #110281)

This assertion won't be meaningful in the case that matters: when PackIndices[N + 1] is larger than Substitutions.size(). In that case, End is in the middle of nowhere, and the result of End <= Substitutions.end() is undefined. A smart optimizer would fold that to true.

You should assert PackIndices[N + 1] <= Substitutions.size().

5195–5199 ↗

(On Diff #110281)

This looks really hairy. This is the only (non-recursive) caller of parse_template_arg... it doesn't seem reasonable for parse_template_arg to modify template params, if we're just going to reset them after without looking.

Please add a FIXME to sort this out (at least to document the logic, if not to refactor it somehow).

5207–5209 ↗

(On Diff #110281)

Early continue instead of else, if you leave the logic like this.

I'm a little skeptical that this structure is better than before, though, since there's some non-trivial duplicated code. I'll let you decide.

1621–1631 ↗

(On Diff #110080)

Sounds great. Please add comments to that effect.

libcxxabi/trunk/src/cxa_demangle.cpp

 #endif
       char num[FloatData<Float>::max_demangled_size] = {0};
       int n = snprintf(num, sizeof(num), FloatData<Float>::spec, value);
       s += StringView(num, num + n);
     }
   }
 };
 
-template <std::size_t N>
-class arena
-{
-    static const std::size_t alignment = 16;
-    alignas(alignment) char buf_[N];
-    char* ptr_;
-
-    std::size_t 
-    align_up(std::size_t n) noexcept
-        {return (n + (alignment-1)) & ~(alignment-1);}
-
-    bool
-    pointer_in_buffer(char* p) noexcept
-        {return buf_ <= p && p <= buf_ + N;}
-
-public:
-    arena() noexcept : ptr_(buf_) {}
-    ~arena() {ptr_ = nullptr;}
-    arena(const arena&) = delete;
-    arena& operator=(const arena&) = delete;
-
-    char* allocate(std::size_t n);
-    void deallocate(char* p, std::size_t n) noexcept;
-
-    static constexpr std::size_t size() {return N;}
-    std::size_t used() const {return static_cast<std::size_t>(ptr_ - buf_);}
-    void reset() {ptr_ = buf_;}
-};
-
-template <std::size_t N>
-char*
-arena<N>::allocate(std::size_t n)
-{
-    n = align_up(n);
-    if (static_cast<std::size_t>(buf_ + N - ptr_) >= n)
-    {
-        char* r = ptr_;
-        ptr_ += n;
-        return r;
-    }
-    return static_cast<char*>(std::malloc(n));
-}
-
-template <std::size_t N>
-void
-arena<N>::deallocate(char* p, std::size_t n) noexcept
-{
-    if (pointer_in_buffer(p))
-    {
-        n = align_up(n);
-        if (p + n == ptr_)
-            ptr_ = p;
-    }
-    else
-        std::free(p);
-}
-
-template <class T, std::size_t N>
-class short_alloc
-{
-    arena<N>& a_;
-public:
-    typedef T value_type;
-
-public:
-    template <class _Up> struct rebind {typedef short_alloc<_Up, N> other;};
-
-    short_alloc(arena<N>& a) noexcept : a_(a) {}
-    template <class U>
-        short_alloc(const short_alloc<U, N>& a) noexcept
-            : a_(a.a_) {}
-    short_alloc(const short_alloc&) = default;
-    short_alloc& operator=(const short_alloc&) = delete;
-
-    T* allocate(std::size_t n)
-    {
-        return reinterpret_cast<T*>(a_.allocate(n*sizeof(T)));
-    }
-    void deallocate(T* p, std::size_t n) noexcept
-    {
-        a_.deallocate(reinterpret_cast<char*>(p), n*sizeof(T));
-    }
-
-    template <class T1, std::size_t N1, class U, std::size_t M>
-    friend
-    bool
-    operator==(const short_alloc<T1, N1>& x, const short_alloc<U, M>& y) noexcept;
-
-    template <class U, std::size_t M> friend class short_alloc;
-};
-
-template <class T, std::size_t N, class U, std::size_t M>
-inline
-bool
-operator==(const short_alloc<T, N>& x, const short_alloc<U, M>& y) noexcept
-{
-    return N == M && &x.a_ == &y.a_;
-}
-
-template <class T, std::size_t N, class U, std::size_t M>
-inline
-bool
-operator!=(const short_alloc<T, N>& x, const short_alloc<U, M>& y) noexcept
-{
-    return !(x == y);
-}
-
-const size_t bs = 4 * 1024;
-template <class T> using Alloc = short_alloc<T, bs>;
-template <class T> using Vector = std::vector<T, Alloc<T>>;
-
 class BumpPointerAllocator {
   struct BlockMeta {
     BlockMeta* Next;
     size_t Current;
   };
 
   static constexpr size_t AllocSize = 4096;
   static constexpr size_t UsableAllocSize = AllocSize - sizeof(BlockMeta);
while (BlockList) {
       BlockMeta* Tmp = BlockList;
       BlockList = BlockList->Next;
       if (reinterpret_cast<char*>(Tmp) != InitialBuffer)
         delete[] reinterpret_cast<char*>(Tmp);
     }
   }
 };
 
+template <class T, size_t N>
+class PODSmallVector {
+  static_assert(std::is_pod<T>::value,
+                "T is required to be a plain old data type");
+
+  T* First;
+  T* Last;
+  T* Cap;
+  T Inline[N];
+
+  bool isInline() const { return First == Inline; }
+
+  void clearInline() {
+    First = Inline;
+    Last = Inline;
+    Cap = Inline + N;
+  }
+
+  void reserve(size_t NewCap) {
+    size_t S = size();
+    if (isInline()) {
+      auto* Tmp = static_cast<T*>(std::malloc(NewCap * sizeof(T)));
+      std::copy(First, Last, Tmp);
+      First = Tmp;
+    } else
+      First = static_cast<T*>(std::realloc(First, NewCap * sizeof(T)));
+    Last = First + S;
+    Cap = First + NewCap;
+  }
+
+public:
+  PODSmallVector() : First(Inline), Last(First), Cap(Inline + N) {}
+
+  PODSmallVector(const PODSmallVector&) = delete;
+  PODSmallVector& operator=(const PODSmallVector&) = delete;
+
+  PODSmallVector(PODSmallVector&& Other) : PODSmallVector() {
+    if (Other.isInline()) {
+      std::copy(Other.begin(), Other.end(), First);
+      Last = First + Other.size();
+      Other.clear();
+      return;
+    }
+
+    First = Other.First;
+    Last = Other.Last;
+    Cap = Other.Cap;
+    Other.clearInline();
+  }
+
+  PODSmallVector& operator=(PODSmallVector&& Other) {
+    if (Other.isInline()) {
+      if (!isInline()) {
+        std::free(First);
+        clearInline();
+      }
+      std::copy(Other.begin(), Other.end(), First);
+      Last = First + Other.size();
+      Other.clear();
+      return *this;
+    }
+
+    if (isInline()) {
+      First = Other.First;
+      Last = Other.Last;
+      Cap = Other.Cap;
+      Other.clearInline();
+      return *this;
+    }
+
+    std::swap(First, Other.First);
+    std::swap(Last, Other.Last);
+    std::swap(Cap, Other.Cap);
+    Other.clear();
+    return *this;
+  }
+
+  void push_back(const T& Elem) {
+    if (Last == Cap)
+      reserve(size() * 2);
+    *Last++ = Elem;
+  }
+
+  void pop_back() {
+    assert(Last != First && "Popping empty vector!");
+    --Last;
+  }
+
+  void dropBack(size_t Index) {
+    assert(Index <= size() && "dropBack() can't expand!");
+    Last = First + Index;
+  }
+
+  T* begin() { return First; }
+  T* end() { return Last; }
+
+  bool empty() const { return First == Last; }
+  size_t size() const { return static_cast<size_t>(Last - First); }
+  T& back() {
+    assert(Last != First && "Calling back() on empty vector!");
+    return *(Last - 1);
+  }
+  T& operator[](size_t Index) {
+    assert(Index < size() && "Invalid access!");
+    return *(begin() + Index);
+  }
+  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
 {
-    typedef Vector<Node*> sub_type;
-    typedef Vector<sub_type> template_param_type;
-    sub_type Names;
-    template_param_type Subs;
-    Vector<template_param_type> TemplateParams;
+    // 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;
+
+    // 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;
+
     Qualifiers CV = QualNone;
     FunctionRefQual RefQuals = FrefQualNone;
     unsigned EncodingDepth = 0;
     bool ParsedCtorDtorCV = false;
     bool TagTemplates = true;
     bool FixForwardReferences = false;
     bool TryToParseTemplateArgs = true;
 
     BumpPointerAllocator ASTAllocator;
 
-    template <size_t N>
-    Db(arena<N>& ar) :
-        Names(ar),
-        Subs(0, Names, ar),
-        TemplateParams(0, Subs, ar)
-    {}
-
     template <class T, class... Args> T* make(Args&& ...args)
     {
         return new (ASTAllocator.allocate(sizeof(T)))
             T(std::forward<Args>(args)...);
     }
 
     template <class It> NodeArray makeNodeArray(It begin, It end)
     {
         size_t sz = static_cast<size_t>(end - begin);
         void* mem = ASTAllocator.allocate(sizeof(Node*) * sz);
         Node** data = new (mem) Node*[sz];
         std::copy(begin, end, data);
         return NodeArray(data, sz);
     }
 
     NodeArray popTrailingNodeArray(size_t FromPosition)
     {
         assert(FromPosition <= Names.size());
         NodeArray res = makeNodeArray(
             Names.begin() + (long)FromPosition, Names.end());
-        Names.erase(Names.begin() + (long)FromPosition, Names.end());
+        Names.dropBack(FromPosition);
         return res;
     }
 };
 
 const char* parse_type(const char* first, const char* last, Db& db);
 const char* parse_encoding(const char* first, const char* last, Db& db);
 const char* parse_name(const char* first, const char* last, Db& db,
                        bool* ends_with_template_args = 0);
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 (const auto& n : db.Subs.front())
+                    for (Node* n : db.Subs.nthSubstitution(0))
                         db.Names.push_back(n);
                     first += 2;
                 }
                 break;
             default:
                 if (std::isdigit(first[1]) || std::isupper(first[1]))
                 {
                     size_t sub = 0;
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 (const auto& n : db.Subs[sub])
+                        for (Node* n : db.Subs.nthSubstitution(sub))
                             db.Names.push_back(n);
                         first = t+1;
                     }
                 }
                 break;
             }
         }
     }

 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())
-                    return first;
-                if (!db.TemplateParams.back().empty())
+                if (!db.TemplateParams.empty())
                 {
-                    for (auto& t : db.TemplateParams.back().front())
+                    for (Node *t : db.TemplateParams.nthSubstitution(0))
                         db.Names.push_back(t);
                     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 != '_' || db.TemplateParams.empty())
+                if (t == last || *t != '_')
                     return first;
                 ++sub;
-                if (sub < db.TemplateParams.back().size())
+                if (sub < db.TemplateParams.size())
                 {
-                    for (auto& temp : db.TemplateParams.back()[sub])
+                    for (Node *temp : db.TemplateParams.nthSubstitution(sub))
                         db.Names.push_back(temp);
                     first = t+1;
                 }
                 else
                 {
                     db.Names.push_back(
                         db.make<NameType>(StringView(first, t + 1)));
                     first = t+1;
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.push_back(Db::sub_type(1, db.Names.back(), db.Names.get_allocator()));
+                db.Subs.pushSubstitution(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.push_back(Db::sub_type(1, db.Names.back(), db.Names.get_allocator()));
+                db.Subs.pushSubstitution(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.push_back(Db::sub_type(1, db.Names.back(), db.Names.get_allocator()));
+                        db.Subs.pushSubstitution(db.Names.back());
                         first = t;
                     }
                 }
             }
             break;
        }
     }
     return first;
if (last - first >= 3 && first[0] == 'c' && first[1] == 'v')
                 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.erase(
-                db.Names.begin() + (long)type_begin, db.Names.end());
+            db.Names.dropBack(type_begin);
             db.Names.push_back(conv_expr);
             first = t;
         }
     }
     return first;
 }
 
 // pt <expression> <expression>                    # expr->name
if (first != last)
                 {
                     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 (is_function)
-                            db.Subs.pop_back();
-                        db.Subs.emplace_back(db.Names.get_allocator());
+                            db.Subs.popPack();
+                        db.Subs.pushPack();
                         for (size_t k = k0; k < k1; ++k)
                         {
                             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.back().push_back(db.Names[k]);
+                            db.Subs.pushSubstitutionIntoPack(db.Names[k]);
                         }
                         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.push_back(Db::sub_type(1, db.Names.back(), db.Names.get_allocator()));
+                            db.Subs.pushSubstitution(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.push_back(Db::sub_type(1, db.Names.back(), db.Names.get_allocator()));
+                            db.Subs.pushSubstitution(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.push_back(Db::sub_type(1, db.Names.back(), db.Names.get_allocator()));
+                            db.Subs.pushSubstitution(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.push_back(Db::sub_type(1, db.Names.back(), db.Names.get_allocator()));
+                            db.Subs.pushSubstitution(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.push_back(Db::sub_type(1, db.Names.back(), db.Names.get_allocator()));
+                            db.Subs.pushSubstitution(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.emplace_back(db.Names.get_allocator());
+                            db.Subs.pushPack();
                             for (size_t k = k0; k < k1; ++k)
                             {
                                 db.Names[k] =
                                     db.make<RValueReferenceType>(db.Names[k]);
-                                db.Subs.back().push_back(db.Names[k]);
+                                db.Subs.pushSubstitutionIntoPack(db.Names[k]);
                             }
                             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.emplace_back(db.Names.get_allocator());
+                            db.Subs.pushPack();
                             for (size_t k = k0; k < k1; ++k)
                             {
                                 db.Names[k] = db.make<PointerType>(db.Names[k]);
-                                db.Subs.back().push_back(db.Names[k]);
+                                db.Subs.pushSubstitutionIntoPack(db.Names[k]);
                             }
                             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)
                         {
-                            db.Subs.emplace_back(db.Names.get_allocator());
+                            db.Subs.pushPack();
                             for (size_t k = k0; k < k1; ++k)
                             {
                                 db.Names[k] =
                                     db.make<LValueReferenceType>(db.Names[k]);
-                                db.Subs.back().push_back(db.Names[k]);
+                                db.Subs.pushSubstitutionIntoPack(db.Names[k]);
                             }
                             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)
                         {
-                            db.Subs.emplace_back(db.Names.get_allocator());
+                            db.Subs.pushPack();
                             for (size_t k = k0; k < k1; ++k)
-                                db.Subs.back().push_back(db.Names[k]);
+                                db.Subs.pushSubstitutionIntoPack(db.Names[k]);
                             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.push_back(Db::sub_type(
-                                        1, db.Names.back(),
-                                        db.Names.get_allocator()));
+                                    db.Subs.pushSubstitution(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.push_back(Db::sub_type(1, db.Names.back(), db.Names.get_allocator()));
+                                    db.Subs.pushSubstitution(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.push_back(Db::sub_type(1, db.Names.back(), db.Names.get_allocator()));
+                                db.Subs.pushSubstitution(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.push_back(Db::sub_type(1, db.Names.back(), db.Names.get_allocator()));
+                                        db.Subs.pushSubstitution(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)
                                 {
-                                    db.Subs.emplace_back(db.Names.get_allocator());
+                                    db.Subs.pushPack();
                                     for (size_t k = k0; k < k1; ++k)
-                                        db.Subs.back().push_back(db.Names[k]);
+                                        db.Subs.pushSubstitutionIntoPack(db.Names[k]);
                                     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.push_back(Db::sub_type(1, db.Names.back(), db.Names.get_allocator()));
+                                    db.Subs.pushSubstitution(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.push_back(Db::sub_type(1, db.Names.back(), db.Names.get_allocator()));
+                                    db.Subs.pushSubstitution(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.push_back(Db::sub_type(1, db.Names.back(), db.Names.get_allocator()));
+                                db.Subs.pushSubstitution(db.Names.back());
                                 first = t;
                             }
                         }
                         break;
                     }
               }
                 break;
             }

 //     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.back().clear();
+            db.TemplateParams.clear();
         const char* t = first+1;
         size_t begin_idx = db.Names.size();
         while (*t != 'E')
         {
             if (db.TagTemplates)
-                db.TemplateParams.emplace_back(db.Names.get_allocator());
+            {
+                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();
-            if (db.TagTemplates)
-                db.TemplateParams.pop_back();
+                db.TemplateParams = std::move(TmpParams);
+
                 if (t1 == t || t1 == last || k0 > k1)
                     return first;
-            if (db.TagTemplates)
-            {
-                db.TemplateParams.back().emplace_back(db.Names.get_allocator());
+                db.TemplateParams.pushPack();
                 for (size_t k = k0; k < k1; ++k)
-                    db.TemplateParams.back().back().push_back(db.Names[k]);
+                    db.TemplateParams.pushSubstitutionIntoPack(db.Names[k]);
+                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>(
             db.popTrailingNodeArray(begin_idx));
         db.Names.push_back(tp);
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.push_back(
-                            Db::sub_type(1, db.Names.back(),
-                                         db.Names.get_allocator()));
+                        db.Subs.pushSubstitution(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.push_back(Db::sub_type(1, db.Names.back(), db.Names.get_allocator()));
+                    db.Subs.pushSubstitution(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.push_back(Db::sub_type(1, db.Names.back(), db.Names.get_allocator()));
+                    db.Subs.pushSubstitution(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.push_back(Db::sub_type(
-                        1, db.Names.back(), db.Names.get_allocator()));
+                    db.Subs.pushSubstitution(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.push_back(Db::sub_type(1, db.Names.back(), db.Names.get_allocator()));
+                    db.Subs.pushSubstitution(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.pop_back();
+            db.Subs.popPack();
         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.push_back(Db::sub_type(1, db.Names.back(), db.Names.get_allocator()));
+                    db.Subs.pushSubstitution(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();
__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;
     }
 
     size_t internal_size = buf != nullptr ? *n : 0;
-    arena<bs> a;
-    Db db(a);
-    db.TemplateParams.emplace_back(a);
+    Db db;
     int internal_status = success;
     size_t len = std::strlen(mangled_name);
     demangle(mangled_name, mangled_name + len, db,
              internal_status);
 
     if (internal_status == success && db.FixForwardReferences &&
-        !db.TemplateParams.empty() && !db.TemplateParams.front().empty())
+        !db.TemplateParams.empty())
     {
         db.FixForwardReferences = false;
         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;

libcxxabi/trunk/test/unittest_demangle.pass.cpp

+//===----------------------- unittest_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.
+//
+//===----------------------------------------------------------------------===//
+
+#include "../src/cxa_demangle.cpp"
+
+using namespace __cxxabiv1;
+
+void testPODSmallVector() {
+  { // {push/pop}_back
+    PODSmallVector<int, 1> PSV;
+    PSV.push_back(0);
+    PSV.push_back(1);
+    PSV.push_back(2);
+    PSV.push_back(3);
+    for (int i = 0; i < 4; ++i)
+      assert(PSV[i] == i);
+    PSV.pop_back();
+    for (int i = 0; i < 3; ++i)
+      assert(PSV[i] == i);
+    PSV.pop_back();
+    PSV.pop_back();
+    assert(!PSV.empty() && PSV.size() == 1);
+    PSV.pop_back();
+    assert(PSV.empty() && PSV.size() == 0);
+  }
+
+  {
+    PODSmallVector<int, 1> PSV1;
+    PSV1.push_back(1);
+    PSV1.push_back(2);
+    PSV1.push_back(3);
+
+    PODSmallVector<int, 1> PSV2;
+    std::swap(PSV1, PSV2);
+    assert(PSV1.size() == 0);
+    assert(PSV2.size() == 3);
+    int i = 1;
+    for (int x : PSV2) {
+      assert(x == i);
+      ++i;
+    }
+    assert(i == 4);
+    std::swap(PSV1, PSV2);
+    assert(PSV1.size() == 3);
+    assert(PSV2.size() == 0);
+    i = 1;
+    for (int x : PSV1) {
+      assert(x == i);
+      ++i;
+    }
+    assert(i == 4);
+  }
+
+  {
+    PODSmallVector<int, 10> PSV1;
+    PODSmallVector<int, 10> PSV2;
+    PSV1.push_back(0);
+    PSV1.push_back(1);
+    PSV1.push_back(2);
+    assert(PSV1.size() == 3);
+    assert(PSV2.size() == 0);
+    std::swap(PSV1, PSV2);
+    assert(PSV1.size() == 0);
+    assert(PSV2.size() == 3);
+    int i = 0;
+    for (int x : PSV2) {
+      assert(x == i);
+      ++i;
+    }
+    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();
+}