[libcxxabi][demangler] Use an AST to represent the demangled name

[erik.pilkington]

Summary

This patch changes cxa_demangle.cpp to use an AST instead of manipulating std::strings to produce a demangled name. This is good because:

• Performance: 3.7x faster to demangle symbols in LLVM
• Code size: 40% reduction for a release build on my machine
• Better readability: Now the formatting code is separated from the parsing code

This is probably correctish because:

• The fuzzer doesn't seem to have any problems with this patch.
• Demangles symbols in llvm identically to old demangler

Sorry for the mega-patch, I couldn't figure out a sane way of dividing this up further.

Please see a recent thread on llvm-dev for more context: http://lists.llvm.org/pipermail/llvm-dev/2017-June/114448.html

NOTE: this patch depends on: https://reviews.llvm.org/D35158

Thanks for taking a look!
Erik

[erik.pilkington]

Forgot to add context lines!

[mehdi_amini]

src/cxa_demangle.cpp

44

If this is supposed to be *the* ultimate LLVM demangler, can we follow LLVM coding standard?

[mehdi_amini]

src/cxa_demangle.cpp

87

Doc
(same for non trivial APIs)

125

Doc

173

Doc

239

Why is one pure virtual and not the other? Why isn't the stream const?

244

= default;

[EricWF]

This patch causes test_demangle.pass.cpp to fail with UBSan.

Standard Error:
--
/home/eric/workspace/libcxxabi/src/cxa_demangle.cpp:113:44: runtime error: null pointer passed as argument 2, which is declared to never be null
/usr/include/string.h:47:14: note: nonnull attribute specified here
    #0 0x7ff62aae12fb in __cxxabiv1::(anonymous namespace)::stream::operator+=(__cxxabiv1::(anonymous namespace)::string_ref) /home/eric/workspace/libcxxabi/src/cxa_demangle.cpp:113:9
    #1 0x7ff62aaf9494 in __cxxabiv1::(anonymous namespace)::lambda_type_name::print_left(__cxxabiv1::(anonymous namespace)::stream&) const /home/eric/workspace/libcxxabi/src/cxa_demangle.cpp:1135:11
    #2 0x7ff62aae711a in __cxxabiv1::(anonymous namespace)::node::print(__cxxabiv1::(anonymous namespace)::stream&) const /home/eric/workspace/libcxxabi/src/cxa_demangle.cpp:233:9
    #3 0x7ff62aae711a in __cxxabiv1::(anonymous namespace)::qualified_name::print_left(__cxxabiv1::(anonymous namespace)::stream&) const /home/eric/workspace/libcxxabi/src/cxa_demangle.cpp:837
    #4 0x7ff62aaf0da3 in __cxxabiv1::(anonymous namespace)::node::print(__cxxabiv1::(anonymous namespace)::stream&) const /home/eric/workspace/libcxxabi/src/cxa_demangle.cpp:233:9
    #5 0x7ff62aaf0da3 in __cxxabiv1::(anonymous namespace)::node_array::print_with_seperator(__cxxabiv1::(anonymous namespace)::stream&, __cxxabiv1::(anonymous namespace)::string_ref) const /home/eric/workspace/libcxxabi/src/cxa_demangle.cpp:266
    #6 0x7ff62aafa85d in __cxxabiv1::(anonymous namespace)::template_params::print_left(__cxxabiv1::(anonymous namespace)::stream&) const /home/eric/workspace/libcxxabi/src/cxa_demangle.cpp:901:16
    #7 0x7ff62aafaab1 in __cxxabiv1::(anonymous namespace)::node::print(__cxxabiv1::(anonymous namespace)::stream&) const /home/eric/workspace/libcxxabi/src/cxa_demangle.cpp:233:9
    #8 0x7ff62aafaab1 in __cxxabiv1::(anonymous namespace)::name_with_template_args::print_left(__cxxabiv1::(anonymous namespace)::stream&) const /home/eric/workspace/libcxxabi/src/cxa_demangle.cpp:926
    #9 0x7ff62aae70b9 in __cxxabiv1::(anonymous namespace)::node::print(__cxxabiv1::(anonymous namespace)::stream&) const /home/eric/workspace/libcxxabi/src/cxa_demangle.cpp:233:9
    #10 0x7ff62aae70b9 in __cxxabiv1::(anonymous namespace)::qualified_name::print_left(__cxxabiv1::(anonymous namespace)::stream&) const /home/eric/workspace/libcxxabi/src/cxa_demangle.cpp:834
    #11 0x7ff62aafb102 in __cxxabiv1::(anonymous namespace)::node::print(__cxxabiv1::(anonymous namespace)::stream&) const /home/eric/workspace/libcxxabi/src/cxa_demangle.cpp:233:9
    #12 0x7ff62aafb102 in __cxxabiv1::(anonymous namespace)::top_level_function_decl::print_left(__cxxabiv1::(anonymous namespace)::stream&) const /home/eric/workspace/libcxxabi/src/cxa_demangle.cpp:679
    #13 0x7ff62aad779f in __cxxabiv1::(anonymous namespace)::node::print(__cxxabiv1::(anonymous namespace)::stream&) const /home/eric/workspace/libcxxabi/src/cxa_demangle.cpp:233:9
    #14 0x7ff62aad779f in __cxa_demangle /home/eric/workspace/libcxxabi/src/cxa_demangle.cpp:6313
    #15 0x4218a8 in test() /home/eric/workspace/libcxxabi/test/test_demangle.pass.cpp:29682:24
    #16 0x422204 in main /home/eric/workspace/libcxxabi/test/test_demangle.pass.cpp:29761:9
    #17 0x7ff629f8c82f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
    #18 0x403a78 in _start (/home/eric/workspace/build-libcxxabi/test/Output/test_demangle.pass.cpp.exe+0x403a78)

Other than that I don't see any issues with this change. Thanks for working on this.

[erik.pilkington]

In this new patch:

• Fix UB @EricWF pointed out; memmove(something, nullptr, 0) was being called.
• Add some comments
• rename stream -> output_stream

Thanks!
Erik

[erik.pilkington]

src/cxa_demangle.cpp

44

I would like if this followed LLVM conventions too, but this file is already written following this style and leaving it in some middle state would be ugly. All of libcxx[abi] follows this convention too, so this isn't a problem that is isolated to this file.

239

The second isn't pure virtual because its only implemented by nodes that have a part that goes on the right of the declarator, such as array types or functions types, but every node should implements print_left. The stream is where the AST is printed into, so making it const doesn't make sense. I renamed it to output_stream and wrote a comment to make this more clear in the new patch.

[dexonsmith]

This LGTM. Mehdi, do you have any other concerns?

src/cxa_demangle.cpp

44

I agree. I'd be fine with clang-formatting the entire project, but that seems independent from this change.

[mehdi_amini]

src/cxa_demangle.cpp

44

I'm not talking about pure "clang-format" but also naming for instance.

I would like if this followed LLVM conventions too, but this file is already written following this style and leaving it in some middle state would be ugly.

Right, but in the meantime you're adding a significant amount of "debt".

All of libcxx[abi] follows this convention too, so this isn't a problem that is isolated to this file.

This file is "special": it is shared (duplicated...) with LLVM.

[ruiu]

Looks like this demangler's design is similar to my demangler for Microsoft name mangling scheme (https://reviews.llvm.org/D34667). Is that a coincidence? Both demanglers create AST, stringize it using print_left/print_right (I named them write_pre/write_post), and use custom memory allocator. Looks like both demangler can share more code once both land.

Do you think you can avoid STL containers so that your demangler don't need any destructors? I observed that that makes my demangler faster.

[mehdi_amini]

In D35159#807075, @dexonsmith wrote:

This LGTM. Mehdi, do you have any other concerns?

No other concern (haven't looked further for any either)

[dexonsmith]

+mclow.lists

src/cxa_demangle.cpp

44

This is a patch for libcxxabi. Duplicating the file in LLVM is what created technical debt, and that file has already diverged from libcxxabi. That's where the bug is.

AFAICT, there is no requirement for LLVM subprojects to use LLVM naming schemes, and since libcxx and libcxxabi are implementing STL facilities, it's reasonable for them to use STL naming conventions (even in private implementations that aren't exposed to users).

(It would also be reasonable to follow LLVM naming conventions in private implementations, but that's not the current practice, and it would certainly inhibit code readability here to do so just for one type.)

Perhaps a compromise would be to rename string_ref to string_view, so that it sounds more like the equivalent STL type than the equivalent LLVM type.

@mclow.lists, would you like to weigh in as code owner here? Should the naming scheme for new types in libcxxabi private implementations follow LLVM coding conventions, or libcxxabi coding conventions?

[erik.pilkington]

Looks like this demangler's design is similar to my demangler for Microsoft name mangling scheme (https://reviews.llvm.org/D34667). Is that a coincidence? Both demanglers create AST, stringize it using print_left/print_right (I named them write_pre/write_post), and use custom memory allocator. Looks like both demangler can share more code once both land.

Yep, that was coincidental. I glanced at your patch and I think we could end up sharing some code here, which would be really neat.

Do you think you can avoid STL containers so that your demangler don't need any destructors? I observed that that makes my demangler faster.

The AST doesn't have destruction now for this reason, I used a bump pointer to allocate the AST. Looks like your patch followed this strategy too!

[EricWF]

+1 for moving this file to LLVM's internal style.

src/cxa_demangle.cpp

44

I'm not talking about pure "clang-format" but also naming for instance.

+1 to that.

[erik.pilkington]

Rebase. I don't think the issue of purging underscores from this file/libcxx should block this, if we want to discuss that cfe-dev would probably be the place. I agree that it would be nice to clang-format this file, would anyone have any problems with me committing that after this? I found the git-blame of this file to be pretty useless, almost every line just points to r184097.
Are there any other thoughts on this change?
Thanks,
Erik

[dexonsmith]

In D35159#809724, @erik.pilkington wrote:

Rebase. I don't think the issue of purging underscores from this file/libcxx should block this, if we want to discuss that cfe-dev would probably be the place. I agree that it would be nice to clang-format this file, would anyone have any problems with me committing that after this? I found the git-blame of this file to be pretty useless, almost every line just points to r184097.
Are there any other thoughts on this change?

I suppose you may as well pick a new name for "string_ref" that doesn't have underscores, since it's a new type, if someone is going to follow up to drop underscores. Perhaps "StringView"?

[erik.pilkington]

s/string_ref/StringView

[erik.pilkington]

Use LLVM naming conventions for all the new stuff in this patch.

[dexonsmith]

In D35159#823211, @erik.pilkington wrote:

Use LLVM naming conventions for all the new stuff in this patch.

Thanks for renaming everything. LGTM!

src/cxa_demangle.cpp

 {
     unknown_error = -4,
     invalid_args = -3,
     invalid_mangled_name,
     memory_alloc_failure,
     success
 };
 
+class string_ref
+{
+    const char *first, *last;
+public:
+    template <size_t N> string_ref(const char (&str)[N])
+            : first(str), last(str + N - 1) {}
+    string_ref(const char* first, const char* last)
+            : first(first), last(last) {}
+    string_ref() : first(nullptr), last(nullptr) {}
+
+    string_ref substr(size_t from, size_t to)
+    {
+        if (to >= size()) to = size() - 1;
+        if (from >= size()) from = size() - 1;
+        return string_ref(first + from, first + to);
+    }
+
+    string_ref drop_front(size_t n) const
+    {
+        if (n >= size()) n = size() - 1;
+        return string_ref(first + n, last);
+    }
+
+    bool starts_with(string_ref str) const
+    {
+        if (str.size() > size())
+            return false;
+        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 operator==(const string_ref& lhs, const string_ref& 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
+// has been parsed.
+class output_stream
+{
+    char* buffer;
+    size_t current_position;
+    size_t buffer_capacity;
+
+    // Ensure there is at least n more positions in buffer.
+    void grow(size_t n) {
+        if (n + current_position >= buffer_capacity) {
+            buffer_capacity *= 2;
+            if (buffer_capacity < n + current_position)
+                buffer_capacity = n + current_position;
+            buffer = static_cast<char*>(std::realloc(buffer, buffer_capacity));
+        }
+    }
+
+public:
+    output_stream(char* start_buf, size_t sz)
+            : buffer(start_buf), current_position(0), buffer_capacity(sz) {}
+
+    output_stream& operator+=(string_ref r)
+    {
+        size_t sz = r.size();
+        if (sz == 0)
+            return *this;
+        grow(sz);
+        memmove(buffer + current_position, r.begin(), sz);
+        current_position += sz;
+        return *this;
+    }
+
+    output_stream& operator+=(char c)
+    {
+        grow(1);
+        buffer[current_position++] = c;
+        return *this;
+    }
+
+    // Offset of position in buffer, used for building stream_string_ref.
+    typedef unsigned stream_position;
+
+    // string_ref into a stream, used for caching the ast nodes.
+    class stream_string_ref
+    {
+        stream_position first, last;
+
+        friend class output_stream;
+    public:
+        stream_string_ref() : first(0), last(0) {}
+
+        stream_string_ref(stream_position first, stream_position last)
+                : first(first), last(last) {}
+
+        bool empty() const { return first == last; }
+    };
+
+    output_stream& operator+=(stream_string_ref& s)
+    {
+        size_t sz = static_cast<size_t>(s.last - s.first);
+        if (sz == 0)
+            return *this;
+        grow(sz);
+        memmove(buffer + current_position, buffer + s.first, sz);
+        current_position += sz;
+        return *this;
+    }
+
+    stream_position get_current_position() const
+    {
+        return static_cast<stream_position>(current_position);
+    }
+
+    stream_string_ref make_string_ref_from_past_position(stream_position pos)
+    {
+        return stream_string_ref(pos, get_current_position());
+    }
+
+    char back() const
+    {
+        return current_position ? buffer[current_position - 1] : '\0';
+    }
+
+    bool empty() const { return current_position == 0; }
+
+    char* get_buffer() { return buffer; }
+    char* get_buffer_end() { return buffer + current_position - 1; }
+    size_t get_buffer_capacity() { return buffer_capacity; }
+};
+
+// Base class of all AST nodes. The AST is built by the parser, then is
+// traversed by the print_(left|right) functions to produce a demangled string.
+class node
+{
+public:
+    enum kind : unsigned char
+    {
+        k_dot_suffix,
+        k_vendor_ext_qual_type,
+        k_qual_type,
+        k_conversion_operator_type,
+        k_postfix_qualified_type,
+        k_name_type,
+        k_objcproto_name,
+        k_pointer_type,
+        k_lvalue_reference_type,
+        k_rvalue_reference_type,
+        k_pointer_to_member_type,
+        k_array_type,
+        k_function_type,
+        k_top_level_function_decl,
+        k_function_qual_type,
+        k_function_ref_qual_type,
+        k_literal_operator,
+        k_special_name,
+        k_ctor_vtable_special_name,
+        k_qualified_name,
+        k_empty_name,
+        k_vector_type,
+        k_template_params,
+        k_name_with_template_args,
+        k_global_qualified_name,
+        k_std_qualified_name,
+        k_expanded_special_substitution,
+        k_special_substitution,
+        k_ctor_dtor_name,
+        k_dtor_name,
+        k_unnamed_type_name,
+        k_lambda_type_name,
+        k_expr,
+    };
+
+    kind k;
+
+private:
+
+    // If this node has any rhs part, potentally many nodes further down.
+    const unsigned has_rhs_component_ : 1;
+    const unsigned has_function_ : 1;
+    const unsigned has_array_ : 1;
+
+public:
+    node(kind k, bool has_rhs = false, bool has_function = false,
+         bool has_array = false)
+            : k(k), has_rhs_component_(has_rhs), has_function_(has_function),
+              has_array_(has_array) {}
+
+    bool has_rhs_component() const { return has_rhs_component_; }
+    bool has_array() const { return has_array_; }
+    bool has_function() const { return has_function_; }
+
+    void print(output_stream &s) const
+    {
+        print_left(s);
+        if (has_rhs_component())
+            print_right(s);
+    }
+
+    // Print the "left" side of this node into output_stream.
+    virtual void print_left(output_stream& s) 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 print_right(output_stream&) const {}
+
+    virtual string_ref get_base_name() const { return string_ref(); }
+
+    // Silence compiler warnings, this dtor will never be called.
+    virtual ~node() = default;
+};
+
+class node_array
+{
+    node** elems;
+    size_t nelems;
+
+public:
+    node_array() : nelems(0) {}
+
+    node_array(node** elems, size_t nelems)
+            : elems(elems), nelems(nelems) {}
+
+    bool empty() const { return nelems == 0; }
+    size_t size() const { return nelems; }
+
+    void print_with_seperator(output_stream& s, string_ref seperator) const
+    {
+        for (size_t i = 0; i < nelems; ++i)
+        {
+            if (i) s += seperator;
+            elems[i]->print(s);
+        }
+    }
+};
+
+class dot_suffix final : public node
+{
+    const node* prefix;
+    const string_ref suffix;
+
+public:
+    dot_suffix(node* prefix, string_ref suffix)
+            : node(k_dot_suffix), prefix(prefix), suffix(suffix) {}
+
+    void print_left(output_stream& s) const override
+    {
+        prefix->print(s);
+        s += " (";
+        s += suffix;
+        s += ")";
+    }
+};
+
+class vendor_ext_qual_type final : public node
+{
+    const node* ext;
+    const node* ty;
+
+public:
+    vendor_ext_qual_type(node* ext, node* ty)
+            : node(k_vendor_ext_qual_type), ext(ext), ty(ty) {}
+
+    void print_left(output_stream& s) const override
+    {
+        ext->print(s);
+        s += " ";
+        ty->print_left(s);
+    }
+
+    void print_right(output_stream& s) const override
+    {
+        ty->print_right(s);
+    }
+};
+
+enum qualifiers
+{
+    qual_none = 0,
+    qual_const = 0x1,
+    qual_volatile = 0x2,
+    qual_restrict = 0x4,
+};
+
+void add_qualifiers(qualifiers &q1, qualifiers q2)
+{
+    q1 = static_cast<qualifiers>(q1 | q2);
+}
+
+class qual_type : public node {
+protected:
+    const qualifiers quals;
+    const node* child;
+
+    void print_quals(output_stream& s) const
+    {
+        if (quals & qual_const)
+            s += " const";
+        if (quals & qual_volatile)
+            s += " volatile";
+        if (quals & qual_restrict)
+            s += " restrict";
+    }
+
+public:
+    qual_type(node* child, qualifiers quals)
+            : node(k_qual_type, child->has_rhs_component(),
+                   child->has_function(), child->has_array()),
+              quals(quals), child(child) {}
+
+    void print_left(output_stream& s) const override
+    {
+        child->print_left(s);
+        print_quals(s);
+    }
+
+    void print_right(output_stream& s) const override
+    {
+        child->print_right(s);
+    }
+};
+
+class conversion_operator_type final : public node
+{
+    const node* ty;
+
+public:
+    conversion_operator_type(node* ty)
+            : node(k_conversion_operator_type), ty(ty) {}
+
+    void print_left(output_stream& s) const override
+    {
+        s += "operator ";
+        ty->print(s);
+    }
+};
+
+class postfix_qualified_type final : public node
+{
+    const node* ty;
+    const string_ref postfix;
+
+public:
+    postfix_qualified_type(node* ty, string_ref postfix)
+            : node(k_postfix_qualified_type), ty(ty), postfix(postfix) {}
+
+    void print_left(output_stream& s) const override
+    {
+        ty->print_left(s);
+        s += postfix;
+    }
+
+    void print_right(output_stream& s) const override
+    {
+        ty->print_right(s);
+    }
+};
+
+class name_type final : public node
+{
+    const string_ref name;
+
+public:
+    name_type(string_ref name) : node(k_name_type), name(name) {}
+
+    string_ref get_name() const { return name; }
+    string_ref get_base_name() const override { return name; }
+
+    void print_left(output_stream& s) const override
+    {
+        s += name;
+    }
+};
+
+class objcproto_name : public node
+{
+    node* ty;
+    node* protocol;
+
+    friend class pointer_type;
+public:
+    objcproto_name(node* ty, node* protocol)
+            : node(k_objcproto_name), ty(ty), protocol(protocol) {}
+
+    bool is_objc_object() const
+    {
+        return ty->k == k_name_type &&
+            static_cast<name_type*>(ty)->get_name() == "objc_object";
+    }
+
+    void print_left(output_stream& s) const override
+    {
+        ty->print_left(s);
+        s += "<";
+        protocol->print_left(s);
+        s += ">";
+    }
+};
+
+class pointer_type final : public node
+{
+    const node* pointee;
+
+public:
+    pointer_type(node* pointee)
+            : node(k_pointer_type, pointee->has_rhs_component()),
+              pointee(pointee) {}
+
+    void print_left(output_stream& s) const override
+    {
+        // We rewrite objc_object<SomeProtocol>* into id<SomeProtocol>.
+        if (pointee->k != k_objcproto_name ||
+            !static_cast<const objcproto_name*>(pointee)->is_objc_object())
+        {
+            pointee->print_left(s);
+            if (pointee->has_array())
+                s += " ";
+            if (pointee->has_array() || pointee->has_function())
+                s += "(";
+            s += "*";
+        }
+        else
+        {
+            const auto* objc_proto =
+                static_cast<const objcproto_name*>(pointee);
+            s += "id<";
+            objc_proto->protocol->print(s);
+            s += ">";
+        }
+    }
+
+    void print_right(output_stream& s) const override
+    {
+        if (pointee->k != k_objcproto_name ||
+            !static_cast<const objcproto_name*>(pointee)->is_objc_object())
+        {
+            if (pointee->has_array() || pointee->has_function())
+                s += ")";
+            pointee->print_right(s);
+        }
+    }
+};
+
+class lvalue_reference_type final : public node {
+    const node* pointee;
+
+public:
+    lvalue_reference_type(node* pointee)
+            : node(k_lvalue_reference_type, pointee->has_rhs_component()),
+              pointee(pointee) {}
+
+    void print_left(output_stream& s) const override
+    {
+        pointee->print_left(s);
+        if (pointee->has_array())
+            s += " ";
+        if (pointee->has_array() || pointee->has_function())
+            s += "(&";
+        else
+            s += "&";
+    }
+    void print_right(output_stream& s) const override
+    {
+        if (pointee->has_array() || pointee->has_function())
+            s += ")";
+        pointee->print_right(s);
+    }
+};
+
+class rvalue_reference_type final : public node
+{
+    const node* pointee;
+
+public:
+    rvalue_reference_type(node* pointee)
+            : node(k_rvalue_reference_type, pointee->has_rhs_component()),
+              pointee(pointee) {}
+
+    void print_left(output_stream& s) const override
+    {
+        pointee->print_left(s);
+        if (pointee->has_array())
+            s += " ";
+        if (pointee->has_array() || pointee->has_function())
+            s += "(&&";
+        else
+            s += "&&";
+    }
+
+    void print_right(output_stream& s) const override
+    {
+        if (pointee->has_array() || pointee->has_function())
+            s += ")";
+        pointee->print_right(s);
+    }
+};
+
+class pointer_to_member_type final : public node
+{
+    const node* class_type;
+    const node* member_type;
+
+public:
+    pointer_to_member_type(node* class_type, node* member_type)
+            : node(k_pointer_to_member_type, member_type->has_rhs_component()),
+              class_type(class_type), member_type(member_type) {}
+
+    void print_left(output_stream& s) const override
+    {
+        member_type->print_left(s);
+        if (member_type->has_array() || member_type->has_function())
+            s += "(";
+        else
+            s += " ";
+        class_type->print(s);
+        s += "::*";
+    }
+
+    void print_right(output_stream& s) const override
+    {
+        if (member_type->has_array() || member_type->has_function())
+            s += ")";
+        member_type->print_right(s);
+    }
+};
+
+class node_or_string
+{
+    const void* first;
+    const void* second;
+
+public:
+    /* implicit */ node_or_string(string_ref str)
+    {
+        const char* first_char = str.begin();
+        const char* second_char = str.end();
+        if (second_char == nullptr)
+        {
+            assert(first_char == second_char);
+            ++first_char, ++second_char;
+        }
+        first = static_cast<const void*>(first_char);
+        second = static_cast<const void*>(second_char);
+    }
+    /* implicit */ node_or_string(node* n)
+            : first(static_cast<const void*>(n)), second(nullptr) {}
+    node_or_string() : first(nullptr), second(nullptr) {}
+
+    bool is_string() const { return second && first; }
+    bool is_node() const { return first && !second; }
+    bool is_empty() const { return !first && !second; }
+
+    string_ref as_string() const
+    {
+        assert(is_string());
+        return string_ref(static_cast<const char*>(first),
+                          static_cast<const char*>(second));
+    }
+
+    const node* as_node() const
+    {
+        assert(is_node());
+        return static_cast<const node*>(first);
+    }
+};
+
+class array_type final : public node {
+    node* base;
+    node_or_string dimension;
+
+public:
+    array_type(node* base, node_or_string dimension)
+            : node(k_array_type, true, false, true),
+              base(base), dimension(dimension) {}
+
+    // Incomplete array type.
+    array_type(node* base) : node(k_array_type, true, false, true), base(base) {}
+
+    void print_left(output_stream& s) const override
+    {
+        base->print_left(s);
+    }
+
+    void print_right(output_stream& s) const override
+    {
+        if (s.back() != ']')
+            s += " ";
+        s += "[";
+        if (dimension.is_string())
+            s += dimension.as_string();
+        else if (dimension.is_node())
+            dimension.as_node()->print(s);
+        s += "]";
+        base->print_right(s);
+    }
+};
+
+class function_type final : public node {
+    node* ret;
+    node_array params;
+
+public:
+    function_type(node* ret, node_array params)
+            : node(k_function_type, true, true),
+              ret(ret), params(params) {}
+
+    // 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 print_left(output_stream& s) const override
+    {
+        ret->print_left(s);
+        s += " ";
+    }
+
+    void print_right(output_stream& s) const override
+    {
+        s += "(";
+        params.print_with_seperator(s, ", ");
+        s += ")";
+        ret->print_right(s);
+    }
+};
+
+class top_level_function_decl final : public node
+{
+    const node* ret;
+    const node* name;
+    node_array params;
+
+public:
+    top_level_function_decl(node* ret, node* name, node_array params)
+            : node(k_top_level_function_decl, true, true), ret(ret),
+              name(name), params(params) {}
+
+    void print_left(output_stream& s) const override
+    {
+        if (ret) {
+            ret->print_left(s);
+            if (!ret->has_rhs_component())
+                s += " ";
+        }
+        name->print(s);
+    }
+
+    void print_right(output_stream& s) const override
+    {
+        s += "(";
+        params.print_with_seperator(s, ", ");
+        s += ")";
+        if (ret) ret->print_right(s);
+    }
+};
+
+enum function_ref_qual : unsigned char
+{
+    fref_qual_none,
+    fref_qual_lvalue,
+    fref_qual_rvalue,
+};
+
+class function_ref_qual_type : public node
+{
+    node* fn;
+    function_ref_qual quals;
+
+    friend class function_qual_type;
+public:
+    function_ref_qual_type(node* fn, function_ref_qual quals)
+            : node(k_function_ref_qual_type, true, true), fn(fn),
+              quals(quals) {}
+
+    void print_quals(output_stream& s) const
+    {
+        if (quals == fref_qual_lvalue)
+            s += " &";
+        else
+            s += " &&";
+    }
+
+    void print_left(output_stream& s) const override { fn->print_left(s); }
+
+    void print_right(output_stream& s) const override
+    {
+        fn->print_right(s);
+        print_quals(s);
+    }
+};
+
+class function_qual_type final : public qual_type
+{
+public:
+    function_qual_type(node* child, qualifiers quals)
+            : qual_type(child, quals)
+    {
+        k = k_function_qual_type;
+    }
+
+    void print_left(output_stream& s) const override
+    {
+        child->print_left(s);
+    }
+
+    void print_right(output_stream& s) const override
+    {
+        if (child->k == k_function_ref_qual_type)
+        {
+            auto* ref_quals = static_cast<const function_ref_qual_type*>(child);
+            ref_quals->fn->print_right(s);
+            print_quals(s);
+            ref_quals->print_quals(s);
+        }
+        else
+        {
+            child->print_right(s);
+            print_quals(s);
+        }
+    }
+};
+
+class literal_operator : public node
+{
+    const node* op_name;
+public:
+    literal_operator(node* op_name)
+            : node(k_literal_operator), op_name(op_name) {}
+
+    void print_left(output_stream& s) const override
+    {
+        s += "operator\"\" ";
+        op_name->print(s);
+    }
+};
+
+class special_name final : public node
+{
+    const string_ref special;
+    const node* child;
+
+public:
+    special_name(string_ref special, node* child)
+            : node(k_special_name), special(special), child(child) {}
+
+    void print_left(output_stream& s) const override
+    {
+        s += special;
+        child->print(s);
+    }
+};
+
+class ctor_vtable_special_name final : public node
+{
+    const node* first_type;
+    const node* second_type;
+public:
+    ctor_vtable_special_name(node* first_type, node* second_type)
+            : node(k_ctor_vtable_special_name),
+              first_type(first_type), second_type(second_type) {}
+
+    void print_left(output_stream& s) const override
+    {
+        s += "construction vtable for ";
+        first_type->print(s);
+        s += "-in-";
+        second_type->print(s);
+    }
+};
+
+class qualified_name final : public node
+{
+    // qualifier::name
+    const node* qualifier;
+    const node* name;
+
+    mutable output_stream::stream_string_ref cache;
+
+public:
+    qualified_name(node* qualifier, node* name)
+            : node(k_qualified_name), qualifier(qualifier), name(name) {
+    }
+
+    string_ref get_base_name() const override
+    {
+        return name->get_base_name();
+    }
+
+    void print_left(output_stream& s) const override
+    {
+        if (!cache.empty())
+        {
+            s += cache;
+            return;
+        }
+
+        output_stream::stream_position start = s.get_current_position();
+        if (qualifier->k != k_empty_name)
+        {
+            qualifier->print(s);
+            s += "::";
+        }
+        name->print(s);
+        cache = s.make_string_ref_from_past_position(start);
+    }
+};
+
+class empty_name : public node
+{
+public:
+    empty_name() : node(k_empty_name) {}
+    void print_left(output_stream&) const override {}
+};
+
+class vector_type final : public node
+{
+    const node* base_type;
+    const node_or_string dimension;
+    const bool is_pixel;
+
+public:
+    vector_type(node_or_string dimension)
+            : node(k_vector_type), base_type(nullptr), dimension(dimension),
+              is_pixel(true) {}
+    vector_type(node* base_type, node_or_string dimension)
+            : node(k_vector_type), base_type(base_type), dimension(dimension),
+              is_pixel(false) {}
+
+    void print_left(output_stream& s) const override
+    {
+        if (is_pixel) {
+            s += "pixel vector[";
+            s += dimension.as_string();
+            s += "]";
+        } else {
+            base_type->print(s);
+            s += " vector[";
+            if (dimension.is_node())
+                dimension.as_node()->print(s);
+            else if (dimension.is_string())
+                s += dimension.as_string();
+            s += "]";
+        }
+    }
+};
+
+class template_params final : public node
+{
+    node_array params;
+
+    mutable output_stream::stream_string_ref cache;
+public:
+    template_params(node_array params)
+            : node(k_template_params), params(params) {}
+
+    void print_left(output_stream& s) const override
+    {
+        if (!cache.empty())
+        {
+            s += cache;
+            return;
+        }
+
+        output_stream::stream_position start = s.get_current_position();
+
+        s += "<";
+        params.print_with_seperator(s, ", ");
+        if (s.back() == '>')
+            s += " ";
+        s += ">";
+
+        cache = s.make_string_ref_from_past_position(start);
+    }
+};
+
+class name_with_template_args final : public node
+{
+    // name<template_args>
+    node* name;
+    node* template_args;
+
+public:
+    name_with_template_args(node* name, node* template_args)
+            : node(k_name_with_template_args), name(name),
+              template_args(template_args) {}
+
+    string_ref get_base_name() const override { return name->get_base_name(); }
+
+    void print_left(output_stream& s) const override
+    {
+        name->print(s);
+        template_args->print(s);
+    }
+};
+
+class global_qualified_name final : public node {
+    node* child;
+
+public:
+    global_qualified_name(node* child)
+            : node(k_global_qualified_name), child(child) {}
+
+    string_ref get_base_name() const override
+    {
+        return child->get_base_name();
+    }
+
+    void print_left(output_stream& s) const override
+    {
+        s += "::";
+        child->print(s);
+    }
+};
+
+class std_qualified_name final : public node
+{
+    node* child;
+public:
+    std_qualified_name(node* child)
+            : node(k_std_qualified_name), child(child) {}
+
+    string_ref get_base_name() const override
+    {
+        return child->get_base_name();
+    }
+
+    void print_left(output_stream& s) const override
+    {
+        s += "std::";
+        child->print(s);
+    }
+};
+
+enum class special_sub_kind {
+    allocator,
+    basic_string,
+    string,
+    istream,
+    ostream,
+    iostream,
+};
+
+class expanded_special_substitution final : public node
+{
+    special_sub_kind ssk;
+
+public:
+    expanded_special_substitution(special_sub_kind ssk)
+            : node(k_expanded_special_substitution), ssk(ssk) {}
+
+    string_ref get_base_name() const override
+    {
+        switch (ssk)
+        {
+        case special_sub_kind::allocator:
+            return string_ref("allocator");
+        case special_sub_kind::basic_string:
+            return string_ref("basic_string");
+        case special_sub_kind::string:
+            return string_ref("basic_string");
+        case special_sub_kind::istream:
+            return string_ref("basic_istream");
+        case special_sub_kind::ostream:
+            return string_ref("basic_ostream");
+        case special_sub_kind::iostream:
+            return string_ref("basic_iostream");
+        }
+    }
+
+    void print_left(output_stream& s) const override
+    {
+        switch (ssk)
+        {
+        case special_sub_kind::allocator:
+            s += "std::basic_string<char, std::char_traits<char>, std::allocator<char> >";
+            break;
+        case special_sub_kind::basic_string:
+        case special_sub_kind::string:
+            s += "std::basic_string<char, std::char_traits<char>, std::allocator<char> >";
+            break;
+        case special_sub_kind::istream:
+            s += "std::basic_istream<char, std::char_traits<char> >";
+            break;
+        case special_sub_kind::ostream:
+            s += "std::basic_ostream<char, std::char_traits<char> >";
+            break;
+        case special_sub_kind::iostream:
+            s += "std::basic_iostream<char, std::char_traits<char> >";
+            break;
+        }
+    }
+};
+
+class special_substitution final : public node
+{
+public:
+    special_sub_kind k;
+
+    special_substitution(special_sub_kind k)
+            : node(k_special_substitution), k(k) {}
+
+    string_ref get_base_name() const override
+    {
+        switch (k) {
+        case special_sub_kind::allocator:
+            return string_ref("allocator");
+        case special_sub_kind::basic_string:
+            return string_ref("basic_string");
+        case special_sub_kind::string:
+            return string_ref("string");
+        case special_sub_kind::istream:
+            return string_ref("istream");
+        case special_sub_kind::ostream:
+            return string_ref("ostream");
+        case special_sub_kind::iostream:
+            return string_ref("iostream");
+        }
+    }
+
+    void print_left(output_stream& s) const override
+    {
+        switch (k) {
+        case special_sub_kind::allocator:
+            s += "std::allocator";
+            break;
+        case special_sub_kind::basic_string:
+            s += "std::basic_string";
+            break;
+        case special_sub_kind::string:
+            s += "std::string";
+            break;
+        case special_sub_kind::istream:
+            s += "std::istream";
+            break;
+        case special_sub_kind::ostream:
+            s += "std::ostream";
+            break;
+        case special_sub_kind::iostream:
+            s += "std::iostream";
+            break;
+        }
+    }
+};
+
+class ctor_dtor_name final : public node
+{
+    const node* basename;
+    const bool is_dtor;
+
+public:
+    ctor_dtor_name(node* basename, bool is_dtor)
+            : node(k_ctor_dtor_name), basename(basename), is_dtor(is_dtor) {}
+
+    void print_left(output_stream& s) const override
+    {
+        if (is_dtor)
+            s += "~";
+        s += basename->get_base_name();
+    }
+};
+
+class dtor_name : public node
+{
+    const node* base;
+public:
+    dtor_name(node* base) : node(k_dtor_name), base(base) {}
+
+    void print_left(output_stream& s) const override
+    {
+        s += "~";
+        base->print_left(s);
+    }
+};
+
+class unnamed_type_name : public node
+{
+    const string_ref count;
+public:
+    unnamed_type_name(string_ref count)
+            : node(k_unnamed_type_name), count(count) {}
+
+    void print_left(output_stream& s) const override
+    {
+        s += "'unnamed";
+        s += count;
+        s += "\'";
+    }
+};
+
+class lambda_type_name : public node
+{
+    node_array params;
+    string_ref count;
+public:
+    lambda_type_name(node_array params, string_ref count)
+            : node(k_lambda_type_name), params(params), count(count) {}
+
+    void print_left(output_stream& s) const override
+    {
+        s += "\'lambda";
+        s += count;
+        s += "\'(";
+        params.print_with_seperator(s, ", ");
+        s += ")";
+    }
+};
+
+// -- Expression nodes --
+
+struct expr : public node
+{
+    expr() : node(k_expr) {}
+};
+
+class binary_expr : public expr
+{
+    const node* lhs;
+    const string_ref infix_operator;
+    const node* rhs;
+public:
+    binary_expr(node* lhs, string_ref infix_operator, node* rhs)
+            : lhs(lhs), infix_operator(infix_operator), rhs(rhs) {}
+
+    void print_left(output_stream& s) const override
+    {
+        // might be a template argument expression, then we need to disambiguate
+        // with parens.
+        if (infix_operator == ">")
+            s += "(";
+
+        s += "(";
+        lhs->print(s);
+        s += ") ";
+        s += infix_operator;
+        s += " (";
+        rhs->print(s);
+        s += ")";
+
+        if (infix_operator == ">")
+            s += ")";
+    }
+};
+
+class array_subscript_expr : public expr
+{
+    const node* op1;
+    const node* op2;
+public:
+    array_subscript_expr(node* op1, node* op2) : op1(op1), op2(op2) {}
+
+    void print_left(output_stream& s) const override
+    {
+        s += "(";
+        op1->print(s);
+        s += ")[";
+        op2->print(s);
+        s += "]";
+    }
+};
+
+class postfix_expr : public expr
+{
+    const node* child;
+    const string_ref operand;
+public:
+    postfix_expr(node* child, string_ref operand)
+            : child(child), operand(operand) {}
+
+    void print_left(output_stream& s) const override
+    {
+        s += "(";
+        child->print(s);
+        s += ")";
+        s += operand;
+    }
+};
+
+class conditional_expr : public expr
+{
+    const node* cond;
+    const node* then;
+    const node* _else;
+public:
+    conditional_expr(node* cond, node* then, node* _else)
+            : cond(cond), then(then), _else(_else) {}
+
+    void print_left(output_stream& s) const override
+    {
+        s += "(";
+        cond->print(s);
+        s += ") ? (";
+        then->print(s);
+        s += ") : (";
+        _else->print(s);
+        s += ")";
+    }
+};
+
+class member_expr : public expr
+{
+    const node* lhs;
+    const string_ref kind;
+    const node* rhs;
+public:
+    member_expr(node* lhs, string_ref kind, node* rhs)
+            : lhs(lhs), kind(kind), rhs(rhs) {}
+
+    void print_left(output_stream& s) const override
+    {
+        lhs->print(s);
+        s += kind;
+        rhs->print(s);
+    }
+};
+
+
+class enclosing_expr : public expr
+{
+    const string_ref prefix;
+    const node* infix;
+    const string_ref postfix;
+
+public:
+    enclosing_expr(string_ref prefix, node* infix, string_ref postfix)
+            : prefix(prefix), infix(infix), postfix(postfix) {}
+
+    void print_left(output_stream& s) const override
+    {
+        s += prefix;
+        infix->print(s);
+        s += postfix;
+    }
+};
+
+class cast_expr : public expr
+{
+    // cast_kind<to>(from)
+    const string_ref cast_kind;
+    const node* to;
+    const node* from;
+public:
+    cast_expr(string_ref cast_kind, node* to, node* from)
+            : cast_kind(cast_kind), to(to), from(from) {}
+
+    void print_left(output_stream& s) const override
+    {
+        s += cast_kind;
+        s += "<";
+        to->print_left(s);
+        s += ">(";
+        from->print_left(s);
+        s += ")";
+    }
+};
+
+class sizeof_param_pack_expr : public expr
+{
+    node_array args;
+public:
+    sizeof_param_pack_expr(node_array args) : args(args) {}
+
+    void print_left(output_stream& s) const override
+    {
+        s += "sizeof...(";
+        args.print_with_seperator(s, ", ");
+        s += ")";
+    }
+};
+
+class call_expr : public expr
+{
+    const node* callee;
+    node_array args;
+public:
+    call_expr(node* callee, node_array args) : callee(callee), args(args) {}
+
+    void print_left(output_stream& s) const override
+    {
+        callee->print(s);
+        s += "(";
+        args.print_with_seperator(s, ", ");
+        s += ")";
+    }
+};
+
+class new_expr : public expr
+{
+    // new (expr_list) type(init_list)
+    node_array expr_list;
+    node* type;
+    node_array init_list;
+    bool is_global; // ::operator new ?
+    bool is_array; // new[] ?
+public:
+    new_expr(node_array expr_list, node* type, node_array init_list,
+             bool is_global, bool is_array)
+            : expr_list(expr_list), type(type), init_list(init_list),
+              is_global(is_global), is_array(is_array) {}
+
+    void print_left(output_stream& s) const override
+    {
+        if (is_global)
+            s += "::operator ";
+        s += "new";
+        if (is_array)
+            s += "[]";
+        if (!expr_list.empty()) {
+            s += "(";
+            expr_list.print_with_seperator(s, ", ");
+            s += ")";
+        }
+        type->print(s);
+        if (!init_list.empty())
+        {
+            s += "(";
+            init_list.print_with_seperator(s, ", ");
+            s += ")";
+        }
+    }
+};
+
+class delete_expr : public expr
+{
+    node* op;
+    bool is_global;
+    bool is_array;
+public:
+    delete_expr(node* op, bool is_global, bool is_array)
+            : op(op), is_global(is_global), is_array(is_array) {}
+
+    void print_left(output_stream& s) const override
+    {
+        if (is_global)
+            s += "::";
+        s += "delete";
+        if (is_array)
+            s += "[] ";
+        op->print(s);
+    }
+};
+
+class prefix_expr : public expr
+{
+    string_ref prefix;
+    node* child;
+
+public:
+    prefix_expr(string_ref prefix, node* child)
+            : prefix(prefix), child(child) {}
+
+    void print_left(output_stream& s) const override
+    {
+        s += prefix;
+        s += "(";
+        child->print(s);
+        s += ")";
+    }
+};
+
+class function_param : public expr
+{
+    string_ref number;
+public:
+    function_param(string_ref number) : number(number) {}
+
+    void print_left(output_stream& s) const override
+    {
+        s += "fp";
+        s += number;
+    }
+};
+
+class expr_list : public expr
+{
+    node_array sub_exprs;
+
+public:
+    expr_list(node_array sub_exprs) : sub_exprs(sub_exprs) {}
+
+    void print_left(output_stream& s) const override
+    {
+        s += "(";
+        sub_exprs.print_with_seperator(s, ", ");
+        s += ")";
+    }
+};
+
+class conversion_expr : public expr
+{
+    node_array expressions;
+    node_array types;
+
+public:
+    conversion_expr(node_array expressions, node_array types)
+            : expressions(expressions), types(types) {}
+
+    void print_left(output_stream& s) const override
+    {
+        s += "(";
+        expressions.print_with_seperator(s, ", ");
+        s += ")(";
+        types.print_with_seperator(s, ", ");
+        s += ")";
+    }
+};
+
+class throw_expr : public expr
+{
+    const node* op;
+public:
+    throw_expr(node* op) : op(op) {}
+
+    void print_left(output_stream& s) const override
+    {
+        s += "throw ";
+        op->print(s);
+    }
+};
+
+class bool_expr : public expr
+{
+    bool value;
+
+public:
+    bool_expr(bool value) : value(value) {}
+
+    void print_left(output_stream& s) const override
+    {
+        s += value ? string_ref("true") : string_ref("false");
+    }
+};
+
+class integer_cast_expr : public expr
+{
+    // ty(integer)
+    node* ty;
+    string_ref integer;
+public:
+    integer_cast_expr(node* ty, string_ref integer)
+            : ty(ty), integer(integer) {}
+
+    void print_left(output_stream& s) const override
+    {
+        s += "(";
+        ty->print(s);
+        s += ")";
+        s += integer;
+    }
+};
+
+class integer_expr : public expr
+{
+    string_ref type;
+    string_ref value;
+public:
+    integer_expr(string_ref type, string_ref value)
+            : type(type), value(value) {}
+
+    void print_left(output_stream& s) const override
+    {
+        if (type.size() > 3) {
+            s += "(";
+            s += type;
+            s += ")";
+        }
+
+        if (value[0] == 'n') {
+            s += "-";
+            s += value.drop_front(1);
+        } else
+            s += value;
+
+        if (type.size() <= 3) {
+            s += type;
+        }
+    }
+};
+
+template <class Float>
+struct float_data;
+
+template <class Float>
+class float_expr : public expr
+{
+    const string_ref contents;
+public:
+    float_expr(string_ref contents) : contents(contents) {}
+
+    void print_left(output_stream& s) const override
+    {
+        const char* first = contents.begin();
+        const char* last = contents.end() + 1;
+
+        const size_t N = float_data<Float>::mangled_size;
+        if (static_cast<std::size_t>(last - first) > N)
+        {
+            last = first + N;
+            union
+            {
+                Float value;
+                char buf[sizeof(Float)];
+            };
+            const char* t = first;
+            char* e = buf;
+            for (; t != last; ++t, ++e)
+            {
+                unsigned d1 = isdigit(*t) ? static_cast<unsigned>(*t - '0') :
+                    static_cast<unsigned>(*t - 'a' + 10);
+                ++t;
+                unsigned d0 = isdigit(*t) ? static_cast<unsigned>(*t - '0') :
+                    static_cast<unsigned>(*t - 'a' + 10);
+                *e = static_cast<char>((d1 << 4) + d0);
+            }
+#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+            std::reverse(buf, e);
+#endif
+            char num[float_data<Float>::max_demangled_size] = {0};
+            int n = snprintf(num, sizeof(num), float_data<Float>::spec, value);
+            s += string_ref(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 

 {
     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>>;
 
-template <class StrT>
-struct string_pair
+class bump_pointer_allocator
 {
-    StrT first;
-    StrT second;
+    struct block_meta
+    {
+        block_meta* next;
+        size_t current;
+    };
 
-    string_pair() = default;
-    string_pair(StrT f) : first(std::move(f)) {}
-    string_pair(StrT f, StrT s)
-        : first(std::move(f)), second(std::move(s)) {}
-    template <size_t N>
-        string_pair(const char (&s)[N]) : first(s, N-1) {}
+    static constexpr size_t alloc_size = 4096;
+    static constexpr size_t usable_alloc_size = alloc_size - sizeof(block_meta);
+
+    char initial_buffer[alloc_size];
+    block_meta* block_list = nullptr;
 
-    size_t size() const {return first.size() + second.size();}
-    bool empty() const { return first.empty() && second.empty(); }
-    StrT full() const {return first + second;}
-    StrT move_full() {return std::move(first) + std::move(second);}
+    void grow()
+    {
+        char* new_meta = new char[alloc_size];
+        block_list = new (new_meta) block_meta{block_list, 0};
+    }
+
+    void* allocate_massive(size_t nbytes)
+    {
+        nbytes += sizeof(block_meta);
+        block_meta* new_meta = reinterpret_cast<block_meta*>(new char[nbytes]);
+        block_list->next = new (new_meta) block_meta{block_list->next, 0};
+        return static_cast<void*>(new_meta + 1);
+    }
+
+public:
+    bump_pointer_allocator()
+            : block_list(new (initial_buffer) block_meta{nullptr, 0}) {}
+
+    void* allocate(size_t n)
+    {
+        n = (n + 15u) & ~15u;
+        if (n + block_list->current >= usable_alloc_size)
+        {
+            if (n > usable_alloc_size)
+                return allocate_massive(n);
+            grow();
+        }
+        block_list->current += n;
+        return static_cast<void*>(
+            reinterpret_cast<char*>(block_list + 1) + block_list->current - n);
+    }
+
+    ~bump_pointer_allocator()
+    {
+        while (block_list)
+        {
+            block_meta* tmp = block_list;
+            block_list = block_list->next;
+            if (reinterpret_cast<char*>(tmp) != initial_buffer)
+                delete[] reinterpret_cast<char*>(tmp);
+        }
+    }
 };
 
 struct Db
 {
-    typedef std::basic_string<char, std::char_traits<char>,
-                              malloc_alloc<char>> String;
-    typedef Vector<string_pair<String>> sub_type;
+    typedef Vector<node*> sub_type;
     typedef Vector<sub_type> template_param_type;
     sub_type names;
     template_param_type subs;
     Vector<template_param_type> template_param;
-    unsigned cv = 0;
-    unsigned ref = 0;
+    qualifiers cv = qual_none;
+    function_ref_qual ref = fref_qual_none;
     unsigned encoding_depth = 0;
     bool parsed_ctor_dtor_cv = false;
     bool tag_templates = true;
     bool fix_forward_references = false;
     bool try_to_parse_template_args = true;
 
+    bump_pointer_allocator ast_allocator;
+
     template <size_t N>
     Db(arena<N>& ar) :
         names(ar),
         subs(0, names, ar),
         template_param(0, subs, ar)
     {}
-};
 
+    template <class T, class... Args> T* make(Args&& ...args)
+    {
+        return new (ast_allocator.allocate(sizeof(T)))
+            T(std::forward<Args>(args)...);
+    }
+
+    template <class It> node_array make_node_array(It begin, It end)
+    {
+        size_t sz = static_cast<size_t>(end - begin);
+        void* mem = ast_allocator.allocate(sizeof(node*) * sz);
+        node** data = new (mem) node*[sz];
+        std::copy(begin, end, data);
+        return node_array(data, sz);
+    }
+
+    node_array pop_trailing_node_array(size_t from_position)
+    {
+        assert(from_position <= names.size());
+        node_array res = make_node_array(
+            names.begin() + (long)from_position, names.end());
+        names.erase(names.begin() + (long)from_position, names.end());
+        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);
 const char* parse_expression(const char* first, const char* last, Db& db);
 const char* parse_template_args(const char* first, const char* last, Db& db);
 const char* parse_operator_name(const char* first, const char* last, Db& db);

 
 constexpr const char* float_data<long double>::spec;
 
 template <class Float>
 const char*
 parse_floating_number(const char* first, const char* last, Db& db)
 {
     const size_t N = float_data<Float>::mangled_size;
-    if (static_cast<std::size_t>(last - first) > N)
-    {
-        last = first + N;
-        union
-        {
-            Float value;
-            char buf[sizeof(Float)];
-        };
-        const char* t = first;
-        char* e = buf;
-        for (; t != last; ++t, ++e)
-        {
-            if (!isxdigit(*t))
-                return first;
-            unsigned d1 = isdigit(*t) ? static_cast<unsigned>(*t - '0') :
-                                        static_cast<unsigned>(*t - 'a' + 10);
-            ++t;
-            unsigned d0 = isdigit(*t) ? static_cast<unsigned>(*t - '0') :
-                                        static_cast<unsigned>(*t - 'a' + 10);
-            *e = static_cast<char>((d1 << 4) + d0);
-        }
-        if (*t == 'E')
-        {
-#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
-            std::reverse(buf, e);
-#endif
-            char num[float_data<Float>::max_demangled_size] = {0};
-            int n = snprintf(num, sizeof(num), float_data<Float>::spec, value);
-            if (static_cast<std::size_t>(n) >= sizeof(num))
-                return first;
-            db.names.push_back(Db::String(num, static_cast<std::size_t>(n)));
-            first = t+1;
-        }
-    }
+    if (static_cast<std::size_t>(last - first) <= N)
+        return first;
+    for (; t != last; ++t)
+        db.names.push_back(
+            db.make<float_expr<Float>>(string_ref(first, t)));
+        first = t + 1;
     return first;
 }
 
 // <source-name> ::= <positive length number> <identifier>
 
 const char*
 parse_source_name(const char* first, const char* last, Db& db)
 {
     if (first != last)
     {
         char c = *first;
         if (isdigit(c) && first+1 != last)
         {
             const char* t = first+1;
             size_t n = static_cast<size_t>(c - '0');
             for (c = *t; isdigit(c); c = *t)
             {
                 n = n * 10 + static_cast<size_t>(c - '0');
                 if (++t == last)
                     return first;
             }
             if (static_cast<size_t>(last - t) >= n)
             {
-                Db::String r(t, n);
+                string_ref r(t, t + n);
                 if (r.substr(0, 10) == "_GLOBAL__N")
-                    db.names.push_back("(anonymous namespace)");
+                    db.names.push_back(db.make<name_type>("(anonymous namespace)"));
                 else
-                    db.names.push_back(std::move(r));
+                    db.names.push_back(db.make<name_type>(r));
                 first = t + n;
             }
         }
     }
     return first;
 }
 
 // <substitution> ::= S <seq-id> _

 {
     if (last - first >= 2)
     {
         if (*first == 'S')
         {
             switch (first[1])
             {
             case 'a':
-                db.names.push_back("std::allocator");
+                db.names.push_back(
+                    db.make<special_substitution>(
+                        special_sub_kind::allocator));
                 first += 2;
                 break;
             case 'b':
-                db.names.push_back("std::basic_string");
+                db.names.push_back(
+                    db.make<special_substitution>(special_sub_kind::basic_string));
                 first += 2;
                 break;
             case 's':
-                db.names.push_back("std::string");
+                db.names.push_back(
+                    db.make<special_substitution>(
+                        special_sub_kind::string));
                 first += 2;
                 break;
             case 'i':
-                db.names.push_back("std::istream");
+                db.names.push_back(db.make<special_substitution>(special_sub_kind::istream));
                 first += 2;
                 break;
             case 'o':
-                db.names.push_back("std::ostream");
+                db.names.push_back(db.make<special_substitution>(special_sub_kind::ostream));
                 first += 2;
                 break;
             case 'd':
-                db.names.push_back("std::iostream");
+                db.names.push_back(db.make<special_substitution>(special_sub_kind::iostream));
                 first += 2;
                 break;
             case '_':
                 if (!db.subs.empty())
                 {
                     for (const auto& n : db.subs.front())
                         db.names.push_back(n);
                     first += 2;

 const char*
 parse_builtin_type(const char* first, const char* last, Db& db)
 {
     if (first != last)
     {
         switch (*first)
         {
         case 'v':
-            db.names.push_back("void");
+            db.names.push_back(db.make<name_type>("void"));
             ++first;
             break;
         case 'w':
-            db.names.push_back("wchar_t");
+            db.names.push_back(db.make<name_type>("wchar_t"));
             ++first;
             break;
         case 'b':
-            db.names.push_back("bool");
+            db.names.push_back(db.make<name_type>("bool"));
             ++first;
             break;
         case 'c':
-            db.names.push_back("char");
+            db.names.push_back(db.make<name_type>("char"));
             ++first;
             break;
         case 'a':
-            db.names.push_back("signed char");
+            db.names.push_back(db.make<name_type>("signed char"));
             ++first;
             break;
         case 'h':
-            db.names.push_back("unsigned char");
+            db.names.push_back(db.make<name_type>("unsigned char"));
             ++first;
             break;
         case 's':
-            db.names.push_back("short");
+            db.names.push_back(db.make<name_type>("short"));
             ++first;
             break;
         case 't':
-            db.names.push_back("unsigned short");
+            db.names.push_back(db.make<name_type>("unsigned short"));
             ++first;
             break;
         case 'i':
-            db.names.push_back("int");
+            db.names.push_back(db.make<name_type>("int"));
             ++first;
             break;
         case 'j':
-            db.names.push_back("unsigned int");
+            db.names.push_back(db.make<name_type>("unsigned int"));
             ++first;
             break;
         case 'l':
-            db.names.push_back("long");
+            db.names.push_back(db.make<name_type>("long"));
             ++first;
             break;
         case 'm':
-            db.names.push_back("unsigned long");
+            db.names.push_back(db.make<name_type>("unsigned long"));
             ++first;
             break;
         case 'x':
-            db.names.push_back("long long");
+            db.names.push_back(db.make<name_type>("long long"));
             ++first;
             break;
         case 'y':
-            db.names.push_back("unsigned long long");
+            db.names.push_back(db.make<name_type>("unsigned long long"));
             ++first;
             break;
         case 'n':
-            db.names.push_back("__int128");
+            db.names.push_back(db.make<name_type>("__int128"));
             ++first;
             break;
         case 'o':
-            db.names.push_back("unsigned __int128");
+            db.names.push_back(db.make<name_type>("unsigned __int128"));
             ++first;
             break;
         case 'f':
-            db.names.push_back("float");
+            db.names.push_back(db.make<name_type>("float"));
             ++first;
             break;
         case 'd':
-            db.names.push_back("double");
+            db.names.push_back(db.make<name_type>("double"));
             ++first;
             break;
         case 'e':
-            db.names.push_back("long double");
+            db.names.push_back(db.make<name_type>("long double"));
             ++first;
             break;
         case 'g':
-            db.names.push_back("__float128");
+            db.names.push_back(db.make<name_type>("__float128"));
             ++first;
             break;
         case 'z':
-            db.names.push_back("...");
+            db.names.push_back(db.make<name_type>("..."));
             ++first;
             break;
         case 'u':
             {
                 const char*t = parse_source_name(first+1, last, db);
                 if (t != first+1)
                     first = t;
             }
             break;
         case 'D':
             if (first+1 != last)
             {
                 switch (first[1])
                 {
                 case 'd':
-                    db.names.push_back("decimal64");
+                    db.names.push_back(db.make<name_type>("decimal64"));
                     first += 2;
                     break;
                 case 'e':
-                    db.names.push_back("decimal128");
+                    db.names.push_back(db.make<name_type>("decimal128"));
                     first += 2;
                     break;
                 case 'f':
-                    db.names.push_back("decimal32");
+                    db.names.push_back(db.make<name_type>("decimal32"));
                     first += 2;
                     break;
                 case 'h':
-                    db.names.push_back("decimal16");
+                    db.names.push_back(db.make<name_type>("decimal16"));
                     first += 2;
                     break;
                 case 'i':
-                    db.names.push_back("char32_t");
+                    db.names.push_back(db.make<name_type>("char32_t"));
                     first += 2;
                     break;
                 case 's':
-                    db.names.push_back("char16_t");
+                    db.names.push_back(db.make<name_type>("char16_t"));
                     first += 2;
                     break;
                 case 'a':
-                    db.names.push_back("auto");
+                    db.names.push_back(db.make<name_type>("auto"));
                     first += 2;
                     break;
                 case 'c':
-                    db.names.push_back("decltype(auto)");
+                    db.names.push_back(db.make<name_type>("decltype(auto)"));
                     first += 2;
                     break;
                 case 'n':
-                    db.names.push_back("std::nullptr_t");
+                    db.names.push_back(db.make<name_type>("std::nullptr_t"));
                     first += 2;
                     break;
                 }
             }
             break;
         }
     }
     return first;
 }
 
 // <CV-qualifiers> ::= [r] [V] [K]
 
 const char*
-parse_cv_qualifiers(const char* first, const char* last, unsigned& cv)
+parse_cv_qualifiers(const char* first, const char* last, qualifiers& cv)
 {
-    cv = 0;
+    cv = qual_none;
     if (first != last)
     {
         if (*first == 'r')
         {
-            cv |= 4;
+            add_qualifiers(cv, qual_restrict);
             ++first;
         }
         if (*first == 'V')
         {
-            cv |= 2;
+            add_qualifiers(cv, qual_volatile);
             ++first;
         }
         if (*first == 'K')
         {
-            cv |= 1;
+            add_qualifiers(cv, qual_const);
             ++first;
         }
     }
     return first;
 }
 
 // <template-param> ::= T_    # first template parameter
 //                  ::= T <parameter-2 non-negative number> _
if (last - first >= 2)
                 if (!db.template_param.back().empty())
                 {
                     for (auto& t : db.template_param.back().front())
                         db.names.push_back(t);
                     first += 2;
                 }
                 else
                 {
-                    db.names.push_back("T_");
+                    db.names.push_back(db.make<name_type>("T_"));
                     first += 2;
                     db.fix_forward_references = 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.template_param.empty())
                     return first;
                 ++sub;
                 if (sub < db.template_param.back().size())
                 {
                     for (auto& temp : db.template_param.back()[sub])
                         db.names.push_back(temp);
                     first = t+1;
                 }
                 else
                 {
-                    db.names.push_back(Db::String(first, t+1));
+                    db.names.push_back(
+                        db.make<name_type>(string_ref(first, t + 1)));
                     first = t+1;
                     db.fix_forward_references = true;
                 }
             }
         }
     }
     return first;
 }
 
 // cc <type> <expression>                               # const_cast<type> (expression)
 
 const char*
 parse_const_cast_expr(const char* first, const char* last, Db& db)
 {
     if (last - first >= 3 && first[0] == 'c' && first[1] == 'c')
     {
         const char* t = parse_type(first+2, last, db);
         if (t != first+2)
         {
             const char* t1 = parse_expression(t, last, db);
             if (t1 != t)
             {
                 if (db.names.size() < 2)
                     return first;
-                auto expr = db.names.back().move_full();
+                auto from_expr = db.names.back();
                 db.names.pop_back();
                 if (db.names.empty())
                     return first;
-                db.names.back() = "const_cast<" + db.names.back().move_full() + ">(" + expr + ")";
+                db.names.back() = db.make<cast_expr>(
+                    "const_cast", db.names.back(), from_expr);
                 first = t1;
             }
         }
     }
     return first;
 }
 
 // dc <type> <expression>                               # dynamic_cast<type> (expression)
 
 const char*
 parse_dynamic_cast_expr(const char* first, const char* last, Db& db)
 {
     if (last - first >= 3 && first[0] == 'd' && first[1] == 'c')
     {
         const char* t = parse_type(first+2, last, db);
         if (t != first+2)
         {
             const char* t1 = parse_expression(t, last, db);
             if (t1 != t)
             {
                 if (db.names.size() < 2)
                     return first;
-                auto expr = db.names.back().move_full();
+                auto from_expr = db.names.back();
                 db.names.pop_back();
                 if (db.names.empty())
                     return first;
-                db.names.back() = "dynamic_cast<" + db.names.back().move_full() + ">(" + expr + ")";
+                db.names.back() = db.make<cast_expr>(
+                    "dynamic_cast", db.names.back(), from_expr);
                 first = t1;
             }
         }
     }
     return first;
 }
 
 // rc <type> <expression>                               # reinterpret_cast<type> (expression)
 
 const char*
 parse_reinterpret_cast_expr(const char* first, const char* last, Db& db)
 {
     if (last - first >= 3 && first[0] == 'r' && first[1] == 'c')
     {
         const char* t = parse_type(first+2, last, db);
         if (t != first+2)
         {
             const char* t1 = parse_expression(t, last, db);
             if (t1 != t)
             {
                 if (db.names.size() < 2)
                     return first;
-                auto expr = db.names.back().move_full();
+                auto from_expr = db.names.back();
                 db.names.pop_back();
                 if (db.names.empty())
                     return first;
-                db.names.back() = "reinterpret_cast<" + db.names.back().move_full() + ">(" + expr + ")";
+                db.names.back() = db.make<cast_expr>(
+                    "reinterpret_cast", db.names.back(), from_expr);
                 first = t1;
             }
         }
     }
     return first;
 }
 
 // sc <type> <expression>                               # static_cast<type> (expression)
 
 const char*
 parse_static_cast_expr(const char* first, const char* last, Db& db)
 {
     if (last - first >= 3 && first[0] == 's' && first[1] == 'c')
     {
         const char* t = parse_type(first+2, last, db);
         if (t != first+2)
         {
             const char* t1 = parse_expression(t, last, db);
             if (t1 != t)
             {
                 if (db.names.size() < 2)
                     return first;
-                auto expr = db.names.back().move_full();
+                auto from_expr = db.names.back();
                 db.names.pop_back();
-                db.names.back() = "static_cast<" + db.names.back().move_full() + ">(" + expr + ")";
+                db.names.back() = db.make<cast_expr>(
+                    "static_cast", db.names.back(), from_expr);
                 first = t1;
             }
         }
     }
     return first;
 }
 
 // sp <expression>                                  # pack expansion

 {
     if (last - first >= 3 && first[0] == 's' && first[1] == 't')
     {
         const char* t = parse_type(first+2, last, db);
         if (t != first+2)
         {
             if (db.names.empty())
                 return first;
-            db.names.back() = "sizeof (" + db.names.back().move_full() + ")";
+            db.names.back() = db.make<enclosing_expr>(
+                "sizeof (", db.names.back(), ")");
             first = t;
         }
     }
     return first;
 }
 
 // sz <expr>                                            # sizeof (a expression)
 
 const char*
 parse_sizeof_expr_expr(const char* first, const char* last, Db& db)
 {
     if (last - first >= 3 && first[0] == 's' && first[1] == 'z')
     {
         const char* t = parse_expression(first+2, last, db);
         if (t != first+2)
         {
             if (db.names.empty())
                 return first;
-            db.names.back() = "sizeof (" + db.names.back().move_full() + ")";
+            db.names.back() = db.make<enclosing_expr>(
+                "sizeof (", db.names.back(), ")");
             first = t;
         }
     }
     return first;
 }
 
 // sZ <template-param>                                  # size of a parameter pack
 
 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)
+        if (t != first+2 && k0 <= k1)
         {
-            Db::String tmp("sizeof...(");
-            size_t k = k0;
-            if (k != k1)
-            {
-                tmp += db.names[k].move_full();
-                for (++k; k != k1; ++k)
-                    tmp += ", " + db.names[k].move_full();
-            }
-            tmp += ")";
-            for (; k1 != k0; --k1)
-                db.names.pop_back();
-            db.names.push_back(std::move(tmp));
+            node* sizeof_expr = db.make<sizeof_param_pack_expr>(
+                db.pop_trailing_node_array(k0));
+            db.names.push_back(sizeof_expr);
             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
 //                  ::= fL <L-1 non-negative number> p <top-level CV-qualifiers> _         # L > 0, first parameter
 //                  ::= fL <L-1 non-negative number> p <top-level CV-qualifiers> <parameter-2 non-negative number> _   # L > 0, second and later parameters
 
 const char*
 parse_function_param(const char* first, const char* last, Db& db)
 {
     if (last - first >= 3 && *first == 'f')
     {
         if (first[1] == 'p')
         {
-            unsigned cv;
+            qualifiers cv;
             const char* t = parse_cv_qualifiers(first+2, last, cv);
             const char* t1 = parse_number(t, last);
             if (t1 != last && *t1 == '_')
             {
-                db.names.push_back("fp" + Db::String(t, t1));
+                db.names.push_back(
+                    db.make<function_param>(string_ref(t, t1)));
                 first = t1+1;
             }
         }
         else if (first[1] == 'L')
         {
-            unsigned cv;
+            qualifiers cv;
             const char* t0 = parse_number(first+2, last);
             if (t0 != last && *t0 == 'p')
             {
                 ++t0;
                 const char* t = parse_cv_qualifiers(t0, last, cv);
                 const char* t1 = parse_number(t, last);
                 if (t1 != last && *t1 == '_')
                 {
-                    db.names.push_back("fp" + Db::String(t, t1));
+                    db.names.push_back(
+                        db.make<function_param>(string_ref(t, t1)));
                     first = t1+1;
                 }
             }
         }
     }
     return first;
 }
 
 // sZ <function-param>                                  # size of a function parameter pack
 
 const char*
 parse_sizeof_function_param_pack_expr(const char* first, const char* last, Db& db)
 {
     if (last - first >= 3 && first[0] == 's' && first[1] == 'Z' && first[2] == 'f')
     {
         const char* t = parse_function_param(first+2, last, db);
         if (t != first+2)
         {
             if (db.names.empty())
                 return first;
-            db.names.back() = "sizeof...(" + db.names.back().move_full() + ")";
+            db.names.back() = db.make<enclosing_expr>(
+                "sizeof...(", db.names.back(), ")");
             first = t;
         }
     }
     return first;
 }
 
 // te <expression>                                      # typeid (expression)
 // ti <type>                                            # typeid (type)
 
 const char*
 parse_typeid_expr(const char* first, const char* last, Db& db)
 {
     if (last - first >= 3 && first[0] == 't' && (first[1] == 'e' || first[1] == 'i'))
     {
         const char* t;
         if (first[1] == 'e')
             t = parse_expression(first+2, last, db);
         else
             t = parse_type(first+2, last, db);
         if (t != first+2)
         {
             if (db.names.empty())
                 return first;
-            db.names.back() = "typeid(" + db.names.back().move_full() + ")";
+            db.names.back() = db.make<enclosing_expr>(
+                "typeid(", db.names.back(), ")");
             first = t;
         }
     }
     return first;
 }
 
 // tw <expression>                                      # throw expression
 
 const char*
 parse_throw_expr(const char* first, const char* last, Db& db)
 {
     if (last - first >= 3 && first[0] == 't' && first[1] == 'w')
     {
         const char* t = parse_expression(first+2, last, db);
         if (t != first+2)
         {
             if (db.names.empty())
                 return first;
-            db.names.back() = "throw " + db.names.back().move_full();
+            db.names.back() = db.make<throw_expr>(db.names.back());
             first = t;
         }
     }
     return first;
 }
 
 // ds <expression> <expression>                         # expr.*expr
 
 const char*
 parse_dot_star_expr(const char* first, const char* last, Db& db)
 {
     if (last - first >= 3 && first[0] == 'd' && first[1] == 's')
     {
         const char* t = parse_expression(first+2, last, db);
         if (t != first+2)
         {
             const char* t1 = parse_expression(t, last, db);
             if (t1 != t)
             {
                 if (db.names.size() < 2)
                     return first;
-                auto expr = db.names.back().move_full();
+                auto rhs_expr = db.names.back();
                 db.names.pop_back();
-                db.names.back().first += ".*" + expr;
+                db.names.back() = db.make<member_expr>(
+                    db.names.back(), ".*", rhs_expr);
                 first = t1;
             }
         }
     }
     return first;
 }
 
 // <simple-id> ::= <source-name> [ <template-args> ]
 
 const char*
 parse_simple_id(const char* first, const char* last, Db& db)
 {
     if (first != last)
     {
         const char* t = parse_source_name(first, last, db);
         if (t != first)
         {
             const char* t1 = parse_template_args(t, last, db);
             if (t1 != t)
             {
                 if (db.names.size() < 2)
                     return first;
-                auto args = db.names.back().move_full();
+                auto args = db.names.back();
                 db.names.pop_back();
-                db.names.back().first += std::move(args);
+                db.names.back() =
+                    db.make<name_with_template_args>(db.names.back(), args);
             }
             first = t1;
         }
         else
             first = t;
     }
     return first;
 }
if (first != last)
             {
                 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().first.insert(0, "std::");
+                        db.names.back() =
+                            db.make<std_qualified_name>(db.names.back());
                         db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
                         first = t;
                     }
                 }
             }
             break;
        }
     }
parse_destructor_name(const char* first, const char* last, Db& db)
     {
         const char* t = parse_unresolved_type(first, last, db);
         if (t == first)
             t = parse_simple_id(first, last, db);
         if (t != first)
         {
             if (db.names.empty())
                 return first;
-            db.names.back().first.insert(0, "~");
+            db.names.back() = db.make<dtor_name>(db.names.back());
             first = t;
         }
     }
     return first;
 }
 
 // <base-unresolved-name> ::= <simple-id>                                # unresolved name
 //          extension     ::= <operator-name>                            # unresolved operator-function-id
if (last - first >= 2)
                 const char* t = parse_operator_name(first+2, last, db);
                 if (t != first+2)
                 {
                     first = parse_template_args(t, last, db);
                     if (first != t)
                     {
                         if (db.names.size() < 2)
                             return first;
-                        auto args = db.names.back().move_full();
+                        auto args = db.names.back();
                         db.names.pop_back();
-                        db.names.back().first += std::move(args);
+                        db.names.back() =
+                            db.make<name_with_template_args>(
+                                db.names.back(), args);
                     }
                 }
             }
             else
             {
                 const char* t = parse_destructor_name(first+2, last, db);
                 if (t != first+2)
                     first = t;
             }
         }
         else
         {
             const char* t = parse_simple_id(first, last, db);
             if (t == first)
             {
                 t = parse_operator_name(first, last, db);
                 if (t != first)
                 {
                     first = parse_template_args(t, last, db);
                     if (first != t)
                     {
                         if (db.names.size() < 2)
                             return first;
-                        auto args = db.names.back().move_full();
+                        auto args = db.names.back();
                         db.names.pop_back();
-                        db.names.back().first += std::move(args);
+                        db.names.back() =
+                            db.make<name_with_template_args>(
+                                db.names.back(), args);
                     }
                 }
             }
             else
                 first = t;
         }
     }
     return first;
if (last - first > 2)
         }
         const char* t2 = parse_base_unresolved_name(t, last, db);
         if (t2 != t)
         {
             if (global)
             {
                 if (db.names.empty())
                     return first;
-                db.names.back().first.insert(0, "::");
+                db.names.back() =
+                    db.make<global_qualified_name>(db.names.back());
             }
             first = t2;
         }
         else if (last - t > 2 && t[0] == 's' && t[1] == 'r')
         {
             if (t[2] == 'N')
             {
                 t += 3;
                 const char* t1 = parse_unresolved_type(t, last, db);
                 if (t1 == t || t1 == last)
                     return first;
                 t = t1;
                 t1 = parse_template_args(t, last, db);
                 if (t1 != t)
                 {
                     if (db.names.size() < 2)
                         return first;
-                    auto args = db.names.back().move_full();
+                    auto args = db.names.back();
                     db.names.pop_back();
-                    db.names.back().first += std::move(args);
+                    db.names.back() = db.make<name_with_template_args>(
+                        db.names.back(), args);
                     t = t1;
                     if (t == last)
                     {
                         db.names.pop_back();
                         return first;
                     }
                 }
                 while (*t != 'E')
                 {
                     t1 = parse_unresolved_qualifier_level(t, last, db);
                     if (t1 == t || t1 == last || db.names.size() < 2)
                         return first;
-                    auto s = db.names.back().move_full();
+                    auto s = db.names.back();
                     db.names.pop_back();
-                    db.names.back().first += "::" + std::move(s);
+                    db.names.back() =
+                        db.make<qualified_name>(db.names.back(), s);
                     t = t1;
                 }
                 ++t;
                 t1 = parse_base_unresolved_name(t, last, db);
                 if (t1 == t)
                 {
                     if (!db.names.empty())
                         db.names.pop_back();
                     return first;
                 }
                 if (db.names.size() < 2)
                     return first;
-                auto s = db.names.back().move_full();
+                auto s = db.names.back();
                 db.names.pop_back();
-                db.names.back().first += "::" + std::move(s);
+                db.names.back() =
+                    db.make<qualified_name>(db.names.back(), s);
                 first = t1;
             }
             else
             {
                 t += 2;
                 const char* t1 = parse_unresolved_type(t, last, db);
                 if (t1 != t)
                 {
                     t = t1;
                     t1 = parse_template_args(t, last, db);
                     if (t1 != t)
                     {
                         if (db.names.size() < 2)
                             return first;
-                        auto args = db.names.back().move_full();
+                        auto args = db.names.back();
                         db.names.pop_back();
-                        db.names.back().first += std::move(args);
+                        db.names.back() =
+                            db.make<name_with_template_args>(
+                                db.names.back(), args);
                         t = t1;
                     }
                     t1 = parse_base_unresolved_name(t, last, db);
                     if (t1 == t)
                     {
                         if (!db.names.empty())
                             db.names.pop_back();
                         return first;
                     }
                     if (db.names.size() < 2)
                         return first;
-                    auto s = db.names.back().move_full();
+                    auto s = db.names.back();
                     db.names.pop_back();
-                    db.names.back().first += "::" + std::move(s);
+                    db.names.back() =
+                        db.make<qualified_name>(db.names.back(), s);
                     first = t1;
                 }
                 else
                 {
                     t1 = parse_unresolved_qualifier_level(t, last, db);
                     if (t1 == t || t1 == last)
                         return first;
                     t = t1;
                     if (global)
                     {
                         if (db.names.empty())
                             return first;
-                        db.names.back().first.insert(0, "::");
+                        db.names.back() =
+                            db.make<global_qualified_name>(
+                                db.names.back());
                     }
                     while (*t != 'E')
                     {
                         t1 = parse_unresolved_qualifier_level(t, last, db);
                         if (t1 == t || t1 == last || db.names.size() < 2)
                             return first;
-                        auto s = db.names.back().move_full();
+                        auto s = db.names.back();
                         db.names.pop_back();
-                        db.names.back().first += "::" + std::move(s);
+                        db.names.back() = db.make<qualified_name>(
+                            db.names.back(), s);
                         t = t1;
                     }
                     ++t;
                     t1 = parse_base_unresolved_name(t, last, db);
                     if (t1 == t)
                     {
                         if (!db.names.empty())
                             db.names.pop_back();
                         return first;
                     }
                     if (db.names.size() < 2)
                         return first;
-                    auto s = db.names.back().move_full();
+                    auto s = db.names.back();
                     db.names.pop_back();
-                    db.names.back().first += "::" + std::move(s);
+                    db.names.back() =
+                        db.make<qualified_name>(db.names.back(), s);
                     first = t1;
                 }
             }
         }
     }
     return first;
 }
 
 // dt <expression> <unresolved-name>                    # expr.name
 
 const char*
 parse_dot_expr(const char* first, const char* last, Db& db)
 {
     if (last - first >= 3 && first[0] == 'd' && first[1] == 't')
     {
         const char* t = parse_expression(first+2, last, db);
         if (t != first+2)
         {
             const char* t1 = parse_unresolved_name(t, last, db);
             if (t1 != t)
             {
                 if (db.names.size() < 2)
                     return first;
-                auto name = db.names.back().move_full();
+                auto name = db.names.back();
                 db.names.pop_back();
                 if (db.names.empty())
                     return first;
-                db.names.back().first += "." + name;
+                db.names.back() = db.make<member_expr>(db.names.back(), ".", name);
                 first = t1;
             }
         }
     }
     return first;
 }
 
 // cl <expression>+ E                                   # call
 
 const char*
 parse_call_expr(const char* first, const char* last, Db& db)
 {
     if (last - first >= 4 && first[0] == 'c' && first[1] == 'l')
     {
         const char* t = parse_expression(first+2, last, db);
-        if (t != first+2)
-        {
-            if (t == last)
-                return first;
-            if (db.names.empty())
-                return first;
-            db.names.back().first += db.names.back().second;
-            db.names.back().second = Db::String();
-            db.names.back().first.append("(");
-            bool first_expr = true;
-            while (*t != 'E')
-            {
-                const char* t1 = parse_expression(t, last, db);
-                if (t1 == t || t1 == last)
-                    return first;
-                if (db.names.empty())
-                    return first;
-                auto tmp = db.names.back().move_full();
-                db.names.pop_back();
-                if (!tmp.empty())
-                {
-                    if (db.names.empty())
-                        return first;
-                    if (!first_expr)
-                    {
-                        db.names.back().first.append(", ");
-                        first_expr = false;
-                    }
-                    db.names.back().first.append(tmp);
-                }
-                t = t1;
-            }
-            ++t;
-            if (db.names.empty())
-                return first;
-            db.names.back().first.append(")");
-            first = t;
-        }
-    }
+        if (t == last || t == first + 2 || db.names.empty())
+        node* callee = db.names.back();
+        db.names.pop_back();
+        size_t args_begin = db.names.size();
+            if (t1 == last || t1 == t)
+        if (db.names.size() < args_begin)
+        ++t;
+        call_expr* the_call = db.make<call_expr>(
+            callee, db.pop_trailing_node_array(args_begin));
+        db.names.push_back(the_call);
     return first;
 }
 
 // [gs] nw <expression>* _ <type> E                     # new (expr-list) type
 // [gs] nw <expression>* _ <type> <initializer>         # new (expr-list) type (init)
 // [gs] na <expression>* _ <type> E                     # new[] (expr-list) type
 // [gs] na <expression>* _ <type> <initializer>         # new[] (expr-list) type (init)
 // <initializer> ::= pi <expression>* E                 # parenthesized initialization
if (last - first >= 4)
             parsed_gs = true;
         }
         if (t[0] == 'n' && (t[1] == 'w' || t[1] == 'a'))
         {
             bool is_array = t[1] == 'a';
             t += 2;
             if (t == last)
                 return first;
-            bool has_expr_list = false;
-            bool first_expr = true;
+            size_t first_expr_in_list = db.names.size();
+            node_array expr_list, init_list;
             while (*t != '_')
             {
                 const char* t1 = parse_expression(t, last, db);
                 if (t1 == t || t1 == last)
                     return first;
-                has_expr_list = true;
-                if (!first_expr)
-                {
-                    if (db.names.empty())
-                        return first;
-                    auto tmp = db.names.back().move_full();
-                    db.names.pop_back();
-                    if (!tmp.empty())
-                    {
-                        if (db.names.empty())
-                            return first;
-                        db.names.back().first.append(", ");
-                        db.names.back().first.append(tmp);
-                        first_expr = false;
-                    }
-                }
                 t = t1;
             }
+            if (first_expr_in_list < db.names.size())
+                return first;
+            expr_list = db.pop_trailing_node_array(first_expr_in_list);
             ++t;
             const char* t1 = parse_type(t, last, db);
             if (t1 == t || t1 == last)
                 return first;
             t = t1;
             bool has_init = false;
             if (last - t >= 3 && t[0] == 'p' && t[1] == 'i')
             {
                 t += 2;
                 has_init = true;
-                first_expr = true;
+                size_t init_list_begin = db.names.size();
                 while (*t != 'E')
                 {
                     t1 = parse_expression(t, last, db);
                     if (t1 == t || t1 == last)
                         return first;
-                    if (!first_expr)
-                    {
-                        if (db.names.empty())
-                            return first;
-                        auto tmp = db.names.back().move_full();
-                        db.names.pop_back();
-                        if (!tmp.empty())
-                        {
-                            if (db.names.empty())
-                                return first;
-                            db.names.back().first.append(", ");
-                            db.names.back().first.append(tmp);
-                            first_expr = false;
-                        }
-                    }
                     t = t1;
                 }
-            }
-            if (*t != 'E')
-                return first;
-            Db::String init_list;
-            if (has_init)
-            {
-                if (db.names.empty())
+                if (init_list_begin < db.names.size())
                     return first;
-                init_list = db.names.back().move_full();
-                db.names.pop_back();
+                init_list = db.pop_trailing_node_array(init_list_begin);
             }
-            if (db.names.empty())
-                return first;
-            auto type = db.names.back().move_full();
-            db.names.pop_back();
-            Db::String expr_list;
-            if (has_expr_list)
-            {
-                if (db.names.empty())
-                    return first;
-                expr_list = db.names.back().move_full();
-                db.names.pop_back();
-            }
-            Db::String r;
-            if (parsed_gs)
-                r = "::";
-            if (is_array)
-                r += "[] ";
-            else
-                r += " ";
-            if (has_expr_list)
-                r += "(" + expr_list + ") ";
-            r += type;
-            if (has_init)
-                r += " (" + init_list + ")";
-            db.names.push_back(std::move(r));
+            if (*t != 'E')
+            auto type = db.names.back();
+            db.names.push_back(
+                db.make<new_expr>(expr_list, type, init_list,
+                                  parsed_gs, is_array));
             first = t+1;
         }
     }
     return first;
 }
 
 // cv <type> <expression>                               # conversion with one argument
 // cv <type> _ <expression>* E                          # conversion with a different number of arguments
 
 const char*
 parse_conversion_expr(const char* first, const char* last, Db& db)
 {
     if (last - first >= 3 && first[0] == 'c' && first[1] == 'v')
     {
         bool try_to_parse_template_args = db.try_to_parse_template_args;
         db.try_to_parse_template_args = false;
+        size_t type_begin = db.names.size();
         const char* t = parse_type(first+2, last, db);
         db.try_to_parse_template_args = try_to_parse_template_args;
         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 (t1 == t)
                     return first;
                 t = t1;
             }
             else
             {
                 ++t;
                 if (t == last)
                     return first;
-                if (*t == 'E')
-                    db.names.emplace_back();
-                else
+                if (*t != 'E')
                 {
-                    bool first_expr = true;
                     while (*t != 'E')
                     {
                         const char* t1 = parse_expression(t, last, db);
                         if (t1 == t || t1 == last)
                             return first;
-                        if (!first_expr)
-                        {
-                            if (db.names.empty())
-                                return first;
-                            auto tmp = db.names.back().move_full();
-                            db.names.pop_back();
-                            if (!tmp.empty())
-                            {
-                                if (db.names.empty())
-                                    return first;
-                                db.names.back().first.append(", ");
-                                db.names.back().first.append(tmp);
-                                first_expr = false;
-                            }
-                        }
                         t = t1;
                     }
                 }
                 ++t;
             }
-            if (db.names.size() < 2)
+            if (db.names.size() < expr_list_begin)
                 return first;
-            auto tmp = db.names.back().move_full();
-            db.names.pop_back();
-            db.names.back() = "(" + db.names.back().move_full() + ")(" + tmp + ")";
+            node_array expressions = db.make_node_array(
+                db.names.begin() + (long)expr_list_begin, db.names.end());
+            node_array types = db.make_node_array(
+                db.names.begin() + (long)type_begin,
+                db.names.begin() + (long)expr_list_begin);
+            auto* conv_expr = db.make<conversion_expr>(
+                types, expressions);
+            db.names.erase(
+                db.names.begin() + (long)type_begin, db.names.end());
+            db.names.push_back(conv_expr);
             first = t;
         }
     }
     return first;
 }
 
 // pt <expression> <expression>                    # expr->name
 
 const char*
 parse_arrow_expr(const char* first, const char* last, Db& db)
 {
     if (last - first >= 3 && first[0] == 'p' && first[1] == 't')
     {
         const char* t = parse_expression(first+2, last, db);
         if (t != first+2)
         {
             const char* t1 = parse_expression(t, last, db);
             if (t1 != t)
             {
                 if (db.names.size() < 2)
                     return first;
-                auto tmp = db.names.back().move_full();
+                auto tmp = db.names.back();
                 db.names.pop_back();
-                db.names.back().first += "->";
-                db.names.back().first += tmp;
+                db.names.back() = db.make<member_expr>(
+                    db.names.back(), "->", tmp);
                 first = t1;
             }
         }
     }
     return first;
 }
 
 //  <ref-qualifier> ::= R                   # & ref-qualifier
if (first != last && *first == 'F')
         {
             if (*t == 'Y')
             {
                 /* extern "C" */
                 if (++t == last)
                     return first;
             }
             const char* t1 = parse_type(t, last, db);
-            if (t1 != t)
+            if (t1 != t && !db.names.empty())
             {
+                node* ret_type = db.names.back();
+                db.names.pop_back();
+                size_t params_begin = db.names.size();
                 t = t1;
-                Db::String sig("(");
-                int ref_qual = 0;
+                function_ref_qual ref_quals = fref_qual_none;
                 while (true)
                 {
                     if (t == last)
                     {
                         if (!db.names.empty())
                           db.names.pop_back();
                         return first;
                     }
                     if (*t == 'E')
                     {
                         ++t;
                         break;
                     }
                     if (*t == 'v')
                     {
                         ++t;
                         continue;
                     }
                     if (*t == 'R' && t+1 != last && t[1] == 'E')
                     {
-                        ref_qual = 1;
+                        ref_quals = fref_qual_lvalue;
                         ++t;
                         continue;
                     }
                     if (*t == 'O' && t+1 != last && t[1] == 'E')
                     {
-                        ref_qual = 2;
+                        ref_quals = fref_qual_rvalue;
                         ++t;
                         continue;
                     }
                     size_t k0 = db.names.size();
                     t1 = parse_type(t, last, db);
                     size_t k1 = db.names.size();
-                    if (t1 == t || t1 == last)
+                    if (t1 == t || t1 == last || k1 < k0)
                         return first;
-                    for (size_t k = k0; k < k1; ++k)
-                    {
-                        if (sig.size() > 1)
-                            sig += ", ";
-                        sig += db.names[k].move_full();
-                    }
-                    for (size_t k = k0; k < k1; ++k)
-                        db.names.pop_back();
                     t = t1;
                 }
-                sig += ")";
-                switch (ref_qual)
-                {
-                case 1:
-                    sig += " &";
-                    break;
-                case 2:
-                    sig += " &&";
-                    break;
-                }
                 if (db.names.empty())
                     return first;
-                db.names.back().first += " ";
-                db.names.back().second.insert(0, sig);
+                node* fty = db.make<function_type>(
+                    ret_type, db.pop_trailing_node_array(params_begin));
+                if (ref_quals)
+                    fty = db.make<function_ref_qual_type>(fty, ref_quals);
+                db.names.push_back(fty);
                 first = t;
             }
         }
     }
     return first;
 }
 
 // <pointer-to-member-type> ::= M <class type> <member type>
if (first != last && *first == 'M')
             const char* t2 = parse_type(t, last, db);
             if (t2 != t)
             {
                 if (db.names.size() < 2)
                     return first;
                 auto func = std::move(db.names.back());
                 db.names.pop_back();
                 auto class_type = std::move(db.names.back());
-                if (!func.second.empty() && func.second.front() == '(')
-                {
-                    db.names.back().first = std::move(func.first) + "(" + class_type.move_full() + "::*";
-                    db.names.back().second = ")" + std::move(func.second);
-                }
-                else
-                {
-                    db.names.back().first = std::move(func.first) + " " + class_type.move_full() + "::*";
-                    db.names.back().second = std::move(func.second);
-                }
+                db.names.back() =
+                    db.make<pointer_to_member_type>(class_type, func);
                 first = t2;
             }
         }
     }
     return first;
 }
 
 // <array-type> ::= A <positive dimension number> _ <element type>
 //              ::= A [<dimension expression>] _ <element type>
 
 const char*
 parse_array_type(const char* first, const char* last, Db& db)
 {
     if (first != last && *first == 'A' && first+1 != last)
     {
         if (first[1] == '_')
         {
             const char* t = parse_type(first+2, last, db);
             if (t != first+2)
             {
                 if (db.names.empty())
                     return first;
-                if (db.names.back().second.substr(0, 2) == " [")
-                    db.names.back().second.erase(0, 1);
-                db.names.back().second.insert(0, " []");
+                db.names.back() = db.make<array_type>(db.names.back());
                 first = t;
             }
         }
         else if ('1' <= first[1] && first[1] <= '9')
         {
             const char* t = parse_number(first+1, last);
             if (t != last && *t == '_')
             {
                 const char* t2 = parse_type(t+1, last, db);
                 if (t2 != t+1)
                 {
                     if (db.names.empty())
                         return first;
-                    if (db.names.back().second.substr(0, 2) == " [")
-                        db.names.back().second.erase(0, 1);
-                    db.names.back().second.insert(0, " [" + Db::String(first+1, t) + "]");
+                    db.names.back() =
+                        db.make<array_type>(db.names.back(),
+                                            string_ref(first + 1, t));
                     first = t2;
                 }
             }
         }
         else
         {
             const char* t = parse_expression(first+1, last, db);
             if (t != first+1 && t != last && *t == '_')
             {
                 const char* t2 = parse_type(++t, last, db);
                 if (t2 != t)
                 {
                     if (db.names.size() < 2)
                         return first;
-                    auto type = std::move(db.names.back());
+                    auto base_type = std::move(db.names.back());
                     db.names.pop_back();
-                    auto expr = std::move(db.names.back());
-                    db.names.back().first = std::move(type.first);
-                    if (type.second.substr(0, 2) == " [")
-                        type.second.erase(0, 1);
-                    db.names.back().second = " [" + expr.move_full() + "]" + std::move(type.second);
+                    auto dimension_expr = std::move(db.names.back());
+                    db.names.back() =
+                        db.make<array_type>(base_type, dimension_expr);
                     first = t2;
                 }
             }
         }
     }
     return first;
 }
 
if (last - first >= 4 && first[0] == 'D')
         case 't':
         case 'T':
             {
                 const char* t = parse_expression(first+2, last, db);
                 if (t != first+2 && t != last && *t == 'E')
                 {
                     if (db.names.empty())
                         return first;
-                    db.names.back() = "decltype(" + db.names.back().move_full() + ")";
+                    db.names.back() = db.make<enclosing_expr>(
+                        "decltype(", db.names.back(), ")");
                     first = t+1;
                 }
             }
             break;
         }
     }
     return first;
 }
if (last - first > 3 && first[0] == 'D' && first[1] == 'v')
             {
                 if (*t != 'p')
                 {
                     const char* t1 = parse_type(t, last, db);
                     if (t1 != t)
                     {
                         if (db.names.empty())
                             return first;
-                        db.names.back().first += " vector[" + Db::String(num, sz) + "]";
+                        db.names.back() =
+                            db.make<vector_type>(db.names.back(),
+                                                 string_ref(num, num + sz));
                         first = t1;
                     }
                 }
                 else
                 {
                     ++t;
-                    db.names.push_back("pixel vector[" + Db::String(num, sz) + "]");
+                    db.names.push_back(
+                        db.make<vector_type>(string_ref(num, num + sz)));
                     first = t;
                 }
             }
         }
         else
         {
-            Db::String num;
+            node* num = nullptr;
             const char* t1 = first+2;
             if (*t1 != '_')
             {
                 const char* t = parse_expression(t1, last, db);
                 if (t != t1)
                 {
                     if (db.names.empty())
                         return first;
-                    num = db.names.back().move_full();
+                    num = db.names.back();
                     db.names.pop_back();
                     t1 = t;
                 }
             }
             if (t1 != last && *t1 == '_' && ++t1 != last)
             {
                 const char* t = parse_type(t1, last, db);
                 if (t != t1)
                 {
                     if (db.names.empty())
                         return first;
-                    db.names.back().first += " vector[" + num + "]";
+                    if (num)
+                        db.names.back() =
+                            db.make<vector_type>(db.names.back(), num);
+                    else
+                        db.names.back() =
+                            db.make<vector_type>(db.names.back(), string_ref());
                     first = t;
-                }
+                } else if (num)
+                    db.names.push_back(num);
             }
         }
     }
     return first;
 }
 
 // <type> ::= <builtin-type>
 //        ::= <function-type>
parse_type(const char* first, const char* last, Db& db)
     if (first != last)
     {
         switch (*first)
         {
             case 'r':
             case 'V':
             case 'K':
               {
-                unsigned cv = 0;
+                qualifiers cv = qual_none;
                 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 (is_function)
                             db.subs.pop_back();
                         db.subs.emplace_back(db.names.get_allocator());
                         for (size_t k = k0; k < k1; ++k)
                         {
+                            if (cv) {
                                 if (is_function)
-                            {
-                                size_t p = db.names[k].second.size();
-                                if (db.names[k].second[p - 2] == '&' &&
-                                    db.names[k].second[p - 1] == '&')
-                                    p -= 2;
-                                else if (db.names[k].second.back() == '&')
-                                    p -= 1;
-                                if (cv & 1)
-                                {
-                                    db.names[k].second.insert(p, " const");
-                                    p += 6;
-                                }
-                                if (cv & 2)
-                                {
-                                    db.names[k].second.insert(p, " volatile");
-                                    p += 9;
-                                }
-                                if (cv & 4)
-                                    db.names[k].second.insert(p, " restrict");
-                            }
+                                    db.names[k] = db.make<function_qual_type>(
+                                        db.names[k], cv);
                                 else
-                            {
-                                if (cv & 1)
-                                    db.names[k].first.append(" const");
-                                if (cv & 2)
-                                    db.names[k].first.append(" volatile");
-                                if (cv & 4)
-                                    db.names[k].first.append(" restrict");
+                                    db.names[k] =
+                                        db.make<qual_type>(db.names[k], cv);
                             }
                             db.subs.back().push_back(db.names[k]);
                         }
                         first = t1;
                     }
                 }
               }
                 break;
if (first != last)
                         }
                         break;
                     case 'C':
                         t = parse_type(first+1, last, db);
                         if (t != first+1)
                         {
                             if (db.names.empty())
                                 return first;
-                            db.names.back().first.append(" complex");
+                            db.names.back() = db.make<postfix_qualified_type>(
+                                db.names.back(), " complex");
                             first = t;
                             db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
                         }
                         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()));
                         }
                         break;
                     case 'G':
                         t = parse_type(first+1, last, db);
                         if (t != first+1)
                         {
                             if (db.names.empty())
                                 return first;
-                            db.names.back().first.append(" imaginary");
+                            db.names.back() = db.make<postfix_qualified_type>(
+                                db.names.back(), " imaginary");
                             first = t;
                             db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
                         }
                         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()));
                         }
                         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());
                             for (size_t k = k0; k < k1; ++k)
                             {
-                                if (db.names[k].second.substr(0, 2) == " [")
-                                {
-                                    db.names[k].first += " (";
-                                    db.names[k].second.insert(0, ")");
-                                }
-                                else if (!db.names[k].second.empty() &&
-                                          db.names[k].second.front() == '(')
-                                {
-                                    db.names[k].first += "(";
-                                    db.names[k].second.insert(0, ")");
-                                }
-                                db.names[k].first.append("&&");
+                                db.names[k] =
+                                    db.make<rvalue_reference_type>(db.names[k]);
                                 db.subs.back().push_back(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());
                             for (size_t k = k0; k < k1; ++k)
                             {
-                                if (db.names[k].second.substr(0, 2) == " [")
-                                {
-                                    db.names[k].first += " (";
-                                    db.names[k].second.insert(0, ")");
-                                }
-                                else if (!db.names[k].second.empty() &&
-                                          db.names[k].second.front() == '(')
-                                {
-                                    db.names[k].first += "(";
-                                    db.names[k].second.insert(0, ")");
-                                }
-                                if (first[1] != 'U' || db.names[k].first.substr(0, 12) != "objc_object<")
-                                {
-                                    db.names[k].first.append("*");
-                                }
-                                else
-                                {
-                                    db.names[k].first.replace(0, 11, "id");
-                                }
+                                db.names[k] = db.make<pointer_type>(db.names[k]);
                                 db.subs.back().push_back(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());
                             for (size_t k = k0; k < k1; ++k)
                             {
-                                if (db.names[k].second.substr(0, 2) == " [")
-                                {
-                                    db.names[k].first += " (";
-                                    db.names[k].second.insert(0, ")");
-                                }
-                                else if (!db.names[k].second.empty() &&
-                                          db.names[k].second.front() == '(')
-                                {
-                                    db.names[k].first += "(";
-                                    db.names[k].second.insert(0, ")");
-                                }
-                                db.names[k].first.append("&");
+                                db.names[k] =
+                                    db.make<lvalue_reference_type>(db.names[k]);
                                 db.subs.back().push_back(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());
                             for (size_t k = k0; k < k1; ++k)
                                 db.subs.back().push_back(db.names[k]);
                             if (db.try_to_parse_template_args && k1 == k0+1)
                             {
                                 const char* t1 = parse_template_args(t, last, db);
                                 if (t1 != t)
                                 {
-                                    auto args = db.names.back().move_full();
+                                    auto args = db.names.back();
                                     db.names.pop_back();
-                                    db.names.back().first += std::move(args);
-                                    db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+                                    db.names.back() = db.make<
+                                        name_with_template_args>(
+                                        db.names.back(), args);
+                                    db.subs.push_back(Db::sub_type(
+                                        1, db.names.back(),
+                                        db.names.get_allocator()));
                                     t = t1;
                                 }
                             }
                             first = t;
                         }
                         break;
                       }
                     case 'U':
                         if (first+1 != last)
                         {
                             t = parse_source_name(first+1, last, db);
                             if (t != first+1)
                             {
                                 const char* t2 = parse_type(t, last, db);
                                 if (t2 != t)
                                 {
                                     if (db.names.size() < 2)
                                         return first;
-                                    auto type = db.names.back().move_full();
+                                    auto type = db.names.back();
                                     db.names.pop_back();
-                                    if (db.names.back().first.substr(0, 9) != "objcproto")
+                                    if (db.names.back()->k != node::k_name_type ||
+                                        !static_cast<name_type*>(db.names.back())->get_name().starts_with("objcproto"))
                                     {
-                                        db.names.back() = type + " " + db.names.back().move_full();
+                                        db.names.back() = db.make<vendor_ext_qual_type>(type, db.names.back());
                                     }
                                     else
                                     {
-                                        auto proto = db.names.back().move_full();
+                                        auto* proto = static_cast<name_type*>(db.names.back());
                                         db.names.pop_back();
-                                        t = parse_source_name(proto.data() + 9, proto.data() + proto.size(), db);
-                                        if (t != proto.data() + 9)
+                                        t = parse_source_name(proto->get_name().begin() + 9, proto->get_name().end(), db);
+                                        if (t != proto->get_name().begin() + 9)
                                         {
-                                            db.names.back() = type + "<" + db.names.back().move_full() + ">";
+                                            db.names.back() = db.make<objcproto_name>(type, db.names.back());
                                         }
                                         else
                                         {
-                                            db.names.push_back(type + " " + proto);
+                                            db.names.push_back(db.make<vendor_ext_qual_type>(type, proto));
                                         }
                                     }
                                     db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
                                     first = t2;
                                 }
                             }
                         }
                         break;
if (first != last)
                                 first = t;
                                 // Parsed a substitution.  If the substitution is a
                                 //  <template-param> it might be followed by <template-args>.
                                 t = parse_template_args(first, last, db);
                                 if (t != first)
                                 {
                                     if (db.names.size() < 2)
                                         return first;
-                                    auto template_args = db.names.back().move_full();
+                                    auto template_args = db.names.back();
                                     db.names.pop_back();
-                                    db.names.back().first += template_args;
+                                    db.names.back() = db.make<
+                                        name_with_template_args>(
+                                        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()));
                                     first = t;
                                 }
                             }
                         }
                         break;
                     case 'D':
if (first != last)
                                         return first;
                                     db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
                                     first = t;
                                     return first;
                                 }
                                 break;
                             }
                         }
-                        _LIBCPP_FALLTHROUGH();
+                        // _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;
                         }
parse_operator_name(const char* first, const char* last, Db& db)
     if (last - first >= 2)
     {
         switch (first[0])
         {
         case 'a':
             switch (first[1])
             {
             case 'a':
-                db.names.push_back("operator&&");
+                db.names.push_back(db.make<name_type>("operator&&"));
                 first += 2;
                 break;
             case 'd':
             case 'n':
-                db.names.push_back("operator&");
+                db.names.push_back(db.make<name_type>("operator&"));
                 first += 2;
                 break;
             case 'N':
-                db.names.push_back("operator&=");
+                db.names.push_back(db.make<name_type>("operator&="));
                 first += 2;
                 break;
             case 'S':
-                db.names.push_back("operator=");
+                db.names.push_back(db.make<name_type>("operator="));
                 first += 2;
                 break;
             }
             break;
         case 'c':
             switch (first[1])
             {
             case 'l':
-                db.names.push_back("operator()");
+                db.names.push_back(db.make<name_type>("operator()"));
                 first += 2;
                 break;
             case 'm':
-                db.names.push_back("operator,");
+                db.names.push_back(db.make<name_type>("operator,"));
                 first += 2;
                 break;
             case 'o':
-                db.names.push_back("operator~");
+                db.names.push_back(db.make<name_type>("operator~"));
                 first += 2;
                 break;
             case 'v':
                 {
                     bool try_to_parse_template_args = db.try_to_parse_template_args;
                     db.try_to_parse_template_args = false;
                     const char* t = parse_type(first+2, last, db);
                     db.try_to_parse_template_args = try_to_parse_template_args;
                     if (t != first+2)
                     {
                         if (db.names.empty())
                             return first;
-                        db.names.back().first.insert(0, "operator ");
+                        db.names.back() =
+                            db.make<conversion_operator_type>(db.names.back());
                         db.parsed_ctor_dtor_cv = true;
                         first = t;
                     }
                 }
                 break;
             }
             break;
         case 'd':
             switch (first[1])
             {
             case 'a':
-                db.names.push_back("operator delete[]");
+                db.names.push_back(db.make<name_type>("operator delete[]"));
                 first += 2;
                 break;
             case 'e':
-                db.names.push_back("operator*");
+                db.names.push_back(db.make<name_type>("operator*"));
                 first += 2;
                 break;
             case 'l':
-                db.names.push_back("operator delete");
+                db.names.push_back(db.make<name_type>("operator delete"));
                 first += 2;
                 break;
             case 'v':
-                db.names.push_back("operator/");
+                db.names.push_back(db.make<name_type>("operator/"));
                 first += 2;
                 break;
             case 'V':
-                db.names.push_back("operator/=");
+                db.names.push_back(db.make<name_type>("operator/="));
                 first += 2;
                 break;
             }
             break;
         case 'e':
             switch (first[1])
             {
             case 'o':
-                db.names.push_back("operator^");
+                db.names.push_back(db.make<name_type>("operator^"));
                 first += 2;
                 break;
             case 'O':
-                db.names.push_back("operator^=");
+                db.names.push_back(db.make<name_type>("operator^="));
                 first += 2;
                 break;
             case 'q':
-                db.names.push_back("operator==");
+                db.names.push_back(db.make<name_type>("operator=="));
                 first += 2;
                 break;
             }
             break;
         case 'g':
             switch (first[1])
             {
             case 'e':
-                db.names.push_back("operator>=");
+                db.names.push_back(db.make<name_type>("operator>="));
                 first += 2;
                 break;
             case 't':
-                db.names.push_back("operator>");
+                db.names.push_back(db.make<name_type>("operator>"));
                 first += 2;
                 break;
             }
             break;
         case 'i':
             if (first[1] == 'x')
             {
-                db.names.push_back("operator[]");
+                db.names.push_back(db.make<name_type>("operator[]"));
                 first += 2;
             }
             break;
         case 'l':
             switch (first[1])
             {
             case 'e':
-                db.names.push_back("operator<=");
+                db.names.push_back(db.make<name_type>("operator<="));
                 first += 2;
                 break;
             case 'i':
                 {
                     const char* t = parse_source_name(first+2, last, db);
                     if (t != first+2)
                     {
                         if (db.names.empty())
                             return first;
-                        db.names.back().first.insert(0, "operator\"\" ");
+                        db.names.back() =
+                            db.make<literal_operator>(db.names.back());
                         first = t;
                     }
                 }
                 break;
             case 's':
-                db.names.push_back("operator<<");
+                db.names.push_back(db.make<name_type>("operator<<"));
                 first += 2;
                 break;
             case 'S':
-                db.names.push_back("operator<<=");
+                db.names.push_back(db.make<name_type>("operator<<="));
                 first += 2;
                 break;
             case 't':
-                db.names.push_back("operator<");
+                db.names.push_back(db.make<name_type>("operator<"));
                 first += 2;
                 break;
             }
             break;
         case 'm':
             switch (first[1])
             {
             case 'i':
-                db.names.push_back("operator-");
+                db.names.push_back(db.make<name_type>("operator-"));
                 first += 2;
                 break;
             case 'I':
-                db.names.push_back("operator-=");
+                db.names.push_back(db.make<name_type>("operator-="));
                 first += 2;
                 break;
             case 'l':
-                db.names.push_back("operator*");
+                db.names.push_back(db.make<name_type>("operator*"));
                 first += 2;
                 break;
             case 'L':
-                db.names.push_back("operator*=");
+                db.names.push_back(db.make<name_type>("operator*="));
                 first += 2;
                 break;
             case 'm':
-                db.names.push_back("operator--");
+                db.names.push_back(db.make<name_type>("operator--"));
                 first += 2;
                 break;
             }
             break;
         case 'n':
             switch (first[1])
             {
             case 'a':
-                db.names.push_back("operator new[]");
+                db.names.push_back(db.make<name_type>("operator new[]"));
                 first += 2;
                 break;
             case 'e':
-                db.names.push_back("operator!=");
+                db.names.push_back(db.make<name_type>("operator!="));
                 first += 2;
                 break;
             case 'g':
-                db.names.push_back("operator-");
+                db.names.push_back(db.make<name_type>("operator-"));
                 first += 2;
                 break;
             case 't':
-                db.names.push_back("operator!");
+                db.names.push_back(db.make<name_type>("operator!"));
                 first += 2;
                 break;
             case 'w':
-                db.names.push_back("operator new");
+                db.names.push_back(db.make<name_type>("operator new"));
                 first += 2;
                 break;
             }
             break;
         case 'o':
             switch (first[1])
             {
             case 'o':
-                db.names.push_back("operator||");
+                db.names.push_back(db.make<name_type>("operator||"));
                 first += 2;
                 break;
             case 'r':
-                db.names.push_back("operator|");
+                db.names.push_back(db.make<name_type>("operator|"));
                 first += 2;
                 break;
             case 'R':
-                db.names.push_back("operator|=");
+                db.names.push_back(db.make<name_type>("operator|="));
                 first += 2;
                 break;
             }
             break;
         case 'p':
             switch (first[1])
             {
             case 'm':
-                db.names.push_back("operator->*");
+                db.names.push_back(db.make<name_type>("operator->*"));
                 first += 2;
                 break;
             case 'l':
-                db.names.push_back("operator+");
+                db.names.push_back(db.make<name_type>("operator+"));
                 first += 2;
                 break;
             case 'L':
-                db.names.push_back("operator+=");
+                db.names.push_back(db.make<name_type>("operator+="));
                 first += 2;
                 break;
             case 'p':
-                db.names.push_back("operator++");
+                db.names.push_back(db.make<name_type>("operator++"));
                 first += 2;
                 break;
             case 's':
-                db.names.push_back("operator+");
+                db.names.push_back(db.make<name_type>("operator+"));
                 first += 2;
                 break;
             case 't':
-                db.names.push_back("operator->");
+                db.names.push_back(db.make<name_type>("operator->"));
                 first += 2;
                 break;
             }
             break;
         case 'q':
             if (first[1] == 'u')
             {
-                db.names.push_back("operator?");
+                db.names.push_back(db.make<name_type>("operator?"));
                 first += 2;
             }
             break;
         case 'r':
             switch (first[1])
             {
             case 'm':
-                db.names.push_back("operator%");
+                db.names.push_back(db.make<name_type>("operator%"));
                 first += 2;
                 break;
             case 'M':
-                db.names.push_back("operator%=");
+                db.names.push_back(db.make<name_type>("operator%="));
                 first += 2;
                 break;
             case 's':
-                db.names.push_back("operator>>");
+                db.names.push_back(db.make<name_type>("operator>>"));
                 first += 2;
                 break;
             case 'S':
-                db.names.push_back("operator>>=");
+                db.names.push_back(db.make<name_type>("operator>>="));
                 first += 2;
                 break;
             }
             break;
         case 'v':
             if (std::isdigit(first[1]))
             {
                 const char* t = parse_source_name(first+2, last, db);
                 if (t != first+2)
                 {
                     if (db.names.empty())
                         return first;
-                    db.names.back().first.insert(0, "operator ");
+                    db.names.back() =
+                        db.make<conversion_operator_type>(db.names.back());
                     first = t;
                 }
             }
             break;
         }
     }
     return first;
 }
 
 const char*
-parse_integer_literal(const char* first, const char* last, const Db::String& lit, Db& db)
+parse_integer_literal(const char* first, const char* last, string_ref lit, Db& db)
 {
     const char* t = parse_number(first, last);
     if (t != first && t != last && *t == 'E')
     {
-        if (lit.size() > 3)
-            db.names.push_back("(" + lit + ")");
-        else
-            db.names.emplace_back();
-        if (*first == 'n')
-        {
-            db.names.back().first += '-';
-            ++first;
-        }
-        db.names.back().first.append(first, t);
-        if (lit.size() <= 3)
-            db.names.back().first += lit;
+        db.names.push_back(
+            db.make<integer_expr>(lit, string_ref(first, t)));
         first = t+1;
     }
     return first;
 }
 
 // <expr-primary> ::= L <type> <value number> E                          # integer literal
 //                ::= L <type> <value float> E                           # floating literal
 //                ::= L <string type> E                                  # string literal
if (last - first >= 4 && *first == 'L')
             }
             break;
         case 'b':
             if (first[3] == 'E')
             {
                 switch (first[2])
                 {
                 case '0':
-                    db.names.push_back("false");
+                    db.names.push_back(db.make<bool_expr>(0));
                     first += 4;
                     break;
                 case '1':
-                    db.names.push_back("true");
+                    db.names.push_back(db.make<bool_expr>(1));
                     first += 4;
                     break;
                 }
             }
             break;
         case 'c':
             {
             const char* t = parse_integer_literal(first+2, last, "char", db);
if (last - first >= 4 && *first == 'L')
                     {
                         const char* n = t;
                         for (; n != last && isdigit(*n); ++n)
                             ;
                         if (n != t && n != last && *n == 'E')
                         {
                             if (db.names.empty())
                                 return first;
-                            db.names.back() = "(" + db.names.back().move_full() + ")" + Db::String(t, n);
+                            db.names.back() = db.make<integer_cast_expr>(
+                                db.names.back(), string_ref(t, n));
                             first = n+1;
                             break;
                         }
                     }
                     else
                     {
                         first = t+1;
                         break;
                     }
                 }
             }
         }
     }
     return first;
 }
 
-template <class String>
-String
-base_name(String& s)
-{
-    if (s.empty())
-        return s;
-    if (s == "std::string")
-    {
-        s = "std::basic_string<char, std::char_traits<char>, std::allocator<char> >";
-        return "basic_string";
-    }
-    if (s == "std::istream")
-    {
-        s = "std::basic_istream<char, std::char_traits<char> >";
-        return "basic_istream";
-    }
-    if (s == "std::ostream")
-    {
-        s = "std::basic_ostream<char, std::char_traits<char> >";
-        return "basic_ostream";
-    }
-    if (s == "std::iostream")
-    {
-        s = "std::basic_iostream<char, std::char_traits<char> >";
-        return "basic_iostream";
-    }
-    const char* const pf = s.data();
-    const char* pe = pf + s.size();
-    if (pe[-1] == '>')
-    {
-        unsigned c = 1;
-        while (true)
-        {
-            if (--pe == pf)
-                return String();
-            if (pe[-1] == '<')
-            {
-                if (--c == 0)
-                {
-                    --pe;
-                    break;
-                }
-            }
-            else if (pe[-1] == '>')
-                ++c;
-        }
-    }
-    if (pe - pf <= 1)
-      return String();
-    const char* p0 = pe - 1;
-    for (; p0 != pf; --p0)
-    {
-        if (*p0 == ':')
-        {
-            ++p0;
-            break;
-        }
-        if (!isalpha(*p0) && !isdigit(*p0) && *p0 != '_')
-        {
-            return String();
-        }
-    }
-    return String(p0, pe);
+node* maybe_change_special_sub_name(node* inp, Db& db)
+    if (inp->k != node::k_special_substitution)
+        return inp;
+    auto kind = static_cast<special_substitution*>(inp)->k;
+    switch (kind)
+    {
+    case special_sub_kind::string:
+    case special_sub_kind::istream:
+    case special_sub_kind::ostream:
+    case special_sub_kind::iostream:
+        return db.make<expanded_special_substitution>(kind);
+    default:
+    return inp;
 }
 
 // <ctor-dtor-name> ::= C1    # complete object constructor
 //                  ::= C2    # base object constructor
 //                  ::= C3    # complete object allocating constructor
 //   extension      ::= C5    # ?
 //                  ::= D0    # deleting destructor
 //                  ::= D1    # complete object destructor
if (last-first >= 2 && !db.names.empty())
             switch (first[1])
             {
             case '1':
             case '2':
             case '3':
             case '5':
                 if (db.names.empty())
                     return first;
-                db.names.push_back(base_name(db.names.back().first));
+                db.names.back() =
+                    maybe_change_special_sub_name(db.names.back(), db);
+                db.names.push_back(
+                    db.make<ctor_dtor_name>(db.names.back(), false));
                 first += 2;
                 db.parsed_ctor_dtor_cv = true;
                 break;
             }
             break;
         case 'D':
             switch (first[1])
             {
             case '0':
             case '1':
             case '2':
             case '5':
                 if (db.names.empty())
                     return first;
-                db.names.push_back("~" + base_name(db.names.back().first));
+                db.names.push_back(
+                    db.make<ctor_dtor_name>(db.names.back(), true));
                 first += 2;
                 db.parsed_ctor_dtor_cv = true;
                 break;
             }
             break;
         }
     }
     return first;

 {
     if (last - first > 2 && first[0] == 'U')
     {
         char type = first[1];
         switch (type)
         {
         case 't':
           {
-            db.names.push_back(Db::String("'unnamed"));
             const char* t0 = first+2;
             if (t0 == last)
-            {
-                db.names.pop_back();
                 return first;
-            }
+            string_ref count;
             if (std::isdigit(*t0))
             {
                 const char* t1 = t0 + 1;
                 while (t1 != last && std::isdigit(*t1))
                     ++t1;
-                db.names.back().first.append(t0, t1);
+                count = string_ref(t0, t1);
                 t0 = t1;
             }
-            db.names.back().first.push_back('\'');
             if (t0 == last || *t0 != '_')
-            {
-                db.names.pop_back();
                 return first;
-            }
+            db.names.push_back(db.make<unnamed_type_name>(count));
             first = t0 + 1;
           }
             break;
         case 'l':
           {
-            size_t lambda_pos = db.names.size();
-            db.names.push_back(Db::String("'lambda'("));
+            size_t begin_pos = db.names.size();
             const char* t0 = first+2;
+            node_array lambda_params;
             if (first[2] == 'v')
             {
-                db.names.back().first += ')';
                 ++t0;
             }
             else
             {
-                bool is_first_it = true;
                 while (true)
                 {
-                    long k0 = static_cast<long>(db.names.size());
                     const char* t1 = parse_type(t0, last, db);
-                    long k1 = static_cast<long>(db.names.size());
                     if (t1 == t0)
                         break;
-                    if (k0 >= k1)
-                        return first;
-                    // If the call to parse_type above found a pack expansion
-                    // substitution, then multiple names could have been
-                    // inserted into the name table. Walk through the names,
-                    // appending each onto the lambda's parameter list.
-                    std::for_each(db.names.begin() + k0, db.names.begin() + k1,
-                                  [&](Db::sub_type::value_type &pair) {
-                                      if (pair.empty())
-                                          return;
-                                      auto &lambda = db.names[lambda_pos].first;
-                                      if (!is_first_it)
-                                          lambda.append(", ");
-                                      is_first_it = false;
-                                      lambda.append(pair.move_full());
-                                  });
-                    db.names.erase(db.names.begin() + k0, db.names.end());
                     t0 = t1;
                 }
-                if (is_first_it)
-                {
-                    if (!db.names.empty())
-                        db.names.pop_back();
-                    return first;
-                }
-                if (db.names.empty() || db.names.size() - 1 != lambda_pos)
+                if (db.names.size() < begin_pos)
                     return first;
-                db.names.back().first.append(")");
+                lambda_params = db.pop_trailing_node_array(begin_pos);
             }
             if (t0 == last || *t0 != 'E')
-            {
-              if (!db.names.empty())
-                db.names.pop_back();
                 return first;
-            }
             ++t0;
             if (t0 == last)
-            {
-                if(!db.names.empty())
-                  db.names.pop_back();
                 return first;
-            }
+            string_ref count;
             if (std::isdigit(*t0))
             {
                 const char* t1 = t0 + 1;
                 while (t1 != last && std::isdigit(*t1))
                     ++t1;
-                db.names.back().first.insert(db.names.back().first.begin()+7, t0, t1);
+                count = string_ref(t0, t1);
                 t0 = t1;
             }
             if (t0 == last || *t0 != '_')
-            {
-                if(!db.names.empty())
-                  db.names.pop_back();
                 return first;
-            }
+            db.names.push_back(db.make<lambda_type_name>(lambda_params, count));
             first = t0 + 1;
           }
             break;
         }
     }
     return first;
 }
 
if (last - first >= 2)
         }
         const char* t1 = parse_unqualified_name(t0, last, db);
         if (t1 != t0)
         {
             if (St)
             {
                 if (db.names.empty())
                     return first;
-                db.names.back().first.insert(0, "std::");
+                db.names.back() =
+                    db.make<std_qualified_name>(db.names.back());
             }
             first = t1;
         }
     }
     return first;
 }
 
 // at <type>                                            # alignof (a type)
 
 const char*
 parse_alignof_type(const char* first, const char* last, Db& db)
 {
     if (last - first >= 3 && first[0] == 'a' && first[1] == 't')
     {
         const char* t = parse_type(first+2, last, db);
         if (t != first+2)
         {
             if (db.names.empty())
                 return first;
-            db.names.back().first = "alignof (" + db.names.back().move_full() + ")";
+            db.names.back() =
+                db.make<enclosing_expr>("alignof (", db.names.back(), ")");
             first = t;
         }
     }
     return first;
 }
 
 // az <expression>                                            # alignof (a expression)
 
 const char*
 parse_alignof_expr(const char* first, const char* last, Db& db)
 {
     if (last - first >= 3 && first[0] == 'a' && first[1] == 'z')
     {
         const char* t = parse_expression(first+2, last, db);
         if (t != first+2)
         {
             if (db.names.empty())
                 return first;
-            db.names.back().first = "alignof (" + db.names.back().move_full() + ")";
+            db.names.back() =
+                db.make<enclosing_expr>("alignof (", db.names.back(), ")");
             first = t;
         }
     }
     return first;
 }
 
 const char*
 parse_noexcept_expression(const char* first, const char* last, Db& db)
 {
     const char* t1 = parse_expression(first, last, db);
     if (t1 != first)
     {
         if (db.names.empty())
             return first;
-        db.names.back().first =  "noexcept (" + db.names.back().move_full() + ")";
+        db.names.back() =
+            db.make<enclosing_expr>("noexcept (", db.names.back(), ")");
         first = t1;
     }
     return first;
 }
 
 const char*
-parse_prefix_expression(const char* first, const char* last, const Db::String& op, Db& db)
+parse_prefix_expression(const char* first, const char* last, string_ref op, Db& db)
 {
     const char* t1 = parse_expression(first, last, db);
     if (t1 != first)
     {
         if (db.names.empty())
             return first;
-        db.names.back().first =  op + "(" + db.names.back().move_full() + ")";
+        db.names.back() = db.make<prefix_expr>(op, db.names.back());
         first = t1;
     }
     return first;
 }
 
 const char*
-parse_binary_expression(const char* first, const char* last, const Db::String& op, Db& db)
+parse_binary_expression(const char* first, const char* last, string_ref op, Db& db)
 {
     const char* t1 = parse_expression(first, last, db);
     if (t1 != first)
     {
         const char* t2 = parse_expression(t1, last, db);
         if (t2 != t1)
         {
             if (db.names.size() < 2)
                 return first;
-            auto op2 = db.names.back().move_full();
+            auto op2 = db.names.back();
             db.names.pop_back();
-            auto op1 = db.names.back().move_full();
-            auto& nm = db.names.back().first;
-            nm.clear();
-            if (op == ">")
-                nm += '(';
-            nm += "(" + op1 + ") " + op + " (" + op2 + ")";
-            if (op == ">")
-                nm += ')';
+            auto op1 = db.names.back();
+            db.names.back() = db.make<binary_expr>(op1, op, op2);
             first = t2;
         }
         else if(!db.names.empty())
             db.names.pop_back();
     }
     return first;
 }
 
if (last - first >= 2)
             {
             case 'a':
                 {
                     const char* t1 = parse_expression(t+2, last, db);
                     if (t1 != t+2)
                     {
                         if (db.names.empty())
                             return first;
-                        db.names.back().first = (parsed_gs ? Db::String("::") : Db::String()) +
-                                          "delete[] " + db.names.back().move_full();
+                        db.names.back() = db.make<delete_expr>(
+                            db.names.back(), parsed_gs, /*is_array=*/true);
                         first = t1;
                     }
                 }
                 break;
             case 'c':
                 first = parse_dynamic_cast_expr(first, last, db);
                 break;
             case 'e':
                 t = parse_prefix_expression(first+2, last, "*", db);
                 if (t != first+2)
                     first = t;
                 break;
             case 'l':
                 {
                     const char* t1 = parse_expression(t+2, last, db);
                     if (t1 != t+2)
                     {
                         if (db.names.empty())
                             return first;
-                        db.names.back().first = (parsed_gs ? Db::String("::") : Db::String()) +
-                                          "delete " + db.names.back().move_full();
+                        db.names.back() = db.make<delete_expr>(
+                            db.names.back(), parsed_gs, /*is_array=*/false);
                         first = t1;
                     }
                 }
                 break;
             case 'n':
                 return parse_unresolved_name(first, last, db);
             case 's':
                 first = parse_dot_star_expr(first, last, db);
if (last - first >= 2)
                 const char* t1 = parse_expression(first+2, last, db);
                 if (t1 != first+2)
                 {
                     const char* t2 = parse_expression(t1, last, db);
                     if (t2 != t1)
                     {
                         if (db.names.size() < 2)
                             return first;
-                        auto op2 = db.names.back().move_full();
+                        auto op2 = db.names.back();
                         db.names.pop_back();
-                        auto op1 = db.names.back().move_full();
-                        db.names.back() = "(" + op1 + ")[" + op2 + "]";
+                        auto op1 = db.names.back();
+                        db.names.back() =
+                            db.make<array_subscript_expr>(op1, op2);
                         first = t2;
                     }
                     else if (!db.names.empty())
                         db.names.pop_back();
                 }
             }
             break;
         case 'l':
if (last - first >= 2)
                 }
                 else
                 {
                     const char* t1 = parse_expression(first+2, last, db);
                     if (t1 != first+2)
                     {
                         if (db.names.empty())
                             return first;
-                        db.names.back() = "(" + db.names.back().move_full() + ")--";
+                        db.names.back() =
+                            db.make<postfix_expr>(db.names.back(), "--");
                         first = t1;
                     }
                 }
                 break;
             }
             break;
         case 'n':
             switch (t[1])
if (last - first >= 2)
                 }
                 else
                 {
                     const char* t1 = parse_expression(first+2, last, db);
                     if (t1 != first+2)
                     {
                         if (db.names.empty())
                             return first;
-                        db.names.back() = "(" + db.names.back().move_full() + ")++";
+                        db.names.back() =
+                            db.make<postfix_expr>(db.names.back(), "++");
                         first = t1;
                     }
                 }
                 break;
             case 's':
                 t = parse_prefix_expression(first+2, last, "+", db);
                 if (t != first+2)
                     first = t;
if (last - first >= 2)
                     const char* t2 = parse_expression(t1, last, db);
                     if (t2 != t1)
                     {
                         const char* t3 = parse_expression(t2, last, db);
                         if (t3 != t2)
                         {
                             if (db.names.size() < 3)
                                 return first;
-                            auto op3 = db.names.back().move_full();
+                            auto op3 = db.names.back();
                             db.names.pop_back();
-                            auto op2 = db.names.back().move_full();
+                            auto op2 = db.names.back();
                             db.names.pop_back();
-                            auto op1 = db.names.back().move_full();
-                            db.names.back() = "(" + op1 + ") ? (" + op2 + ") : (" + op3 + ")";
+                            auto op1 = db.names.back();
+                            db.names.back() =
+                                db.make<conditional_expr>(op1, op2, op3);
                             first = t3;
                         }
                         else
                         {
                             if (db.names.size() < 2)
                               return first;
                             db.names.pop_back();
                             db.names.pop_back();
if (last - first >= 2)
         case 't':
             switch (t[1])
             {
             case 'e':
             case 'i':
                 first = parse_typeid_expr(first, last, db);
                 break;
             case 'r':
-                db.names.push_back("throw");
+                db.names.push_back(db.make<name_type>("throw"));
                 first += 2;
                 break;
             case 'w':
                 first = parse_throw_expr(first, last, db);
                 break;
             }
             break;
         case '1':

 const char*
 parse_template_args(const char* first, const char* last, Db& db)
 {
     if (last - first >= 2 && *first == 'I')
     {
         if (db.tag_templates)
             db.template_param.back().clear();
         const char* t = first+1;
-        Db::String args("<");
+        size_t begin_idx = db.names.size();
         while (*t != 'E')
         {
             if (db.tag_templates)
                 db.template_param.emplace_back(db.names.get_allocator());
             size_t k0 = db.names.size();
             const char* t1 = parse_template_arg(t, last, db);
             size_t k1 = db.names.size();
             if (db.tag_templates)
                 db.template_param.pop_back();
-            if (t1 == t || t1 == last)
+            if (t1 == t || t1 == last || k0 > k1)
                 return first;
             if (db.tag_templates)
             {
                 db.template_param.back().emplace_back(db.names.get_allocator());
                 for (size_t k = k0; k < k1; ++k)
                     db.template_param.back().back().push_back(db.names[k]);
             }
-            for (size_t k = k0; k < k1; ++k)
-            {
-                if (args.size() > 1)
-                    args += ", ";
-                args += db.names[k].move_full();
-            }
-            for (; k1 > k0; --k1)
-                if (!db.names.empty())
-                    db.names.pop_back();
             t = t1;
         }
         first = t + 1;
-        if (args.back() != '>')
-            args += ">";
-        else
-            args += " >";
-        db.names.push_back(std::move(args));
-        
+        template_params* tp = db.make<template_params>(
+            db.pop_trailing_node_array(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
 // 
 // <prefix> ::= <prefix> <unqualified-name>

 //                   ::= <substitution>
 
 const char*
 parse_nested_name(const char* first, const char* last, Db& db,
                   bool* ends_with_template_args)
 {
     if (first != last && *first == 'N')
     {
-        unsigned cv;
+        qualifiers cv;
         const char* t0 = parse_cv_qualifiers(first+1, last, cv);
         if (t0 == last)
             return first;
-        db.ref = 0;
+        db.ref = fref_qual_none;
         if (*t0 == 'R')
         {
-            db.ref = 1;
+            db.ref = fref_qual_lvalue;
             ++t0;
         }
         else if (*t0 == 'O')
         {
-            db.ref = 2;
+            db.ref = fref_qual_rvalue;
             ++t0;
         }
-        db.names.emplace_back();
+        db.names.push_back(db.make<empty_name>());
         if (last - t0 >= 2 && t0[0] == 'S' && t0[1] == 't')
         {
             t0 += 2;
-            db.names.back().first = "std";
+            db.names.back() = db.make<name_type>("std");
         }
         if (t0 == last)
-        {
-            db.names.pop_back();
             return first;
-        }
         bool pop_subs = false;
         bool component_ends_with_template_args = false;
         while (*t0 != 'E')
         {
             component_ends_with_template_args = false;
             const char* t1;
             switch (*t0)
             {
             case 'S':
                 if (t0 + 1 != last && t0[1] == 't')
                     goto do_parse_unqualified_name;
                 t1 = parse_substitution(t0, last, db);
                 if (t1 != t0 && t1 != last)
                 {
-                    auto name = db.names.back().move_full();
+                    auto name = db.names.back();
                     db.names.pop_back();
-                    if (db.names.empty())
-                        return first;
-                    if (!db.names.back().first.empty())
+                    if (db.names.back()->k != node::k_empty_name)
                     {
-                        db.names.back().first += "::" + name;
-                        db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+                        db.names.back() = db.make<qualified_name>(
+                            db.names.back(), name);
+                        db.subs.push_back(
+                            Db::sub_type(1, db.names.back(),
+                                         db.names.get_allocator()));
                     }
                     else
-                        db.names.back().first = name;
+                        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)
                 {
-                    auto name = db.names.back().move_full();
+                    auto name = db.names.back();
                     db.names.pop_back();
-                    if (db.names.empty())
-                        return first;
-                    if (!db.names.back().first.empty())
-                        db.names.back().first += "::" + name;
+                    if (db.names.back()->k != node::k_empty_name)
+                        db.names.back() =
+                            db.make<qualified_name>(db.names.back(), name);
                     else
-                        db.names.back().first = name;
+                        db.names.back() = name;
                     db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
                     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)
                 {
-                    auto name = db.names.back().move_full();
+                    auto name = db.names.back();
                     db.names.pop_back();
-                    if (db.names.empty())
-                        return first;
-                    if (!db.names.back().first.empty())
-                        db.names.back().first += "::" + name;
+                    if (db.names.back()->k != node::k_empty_name)
+                        db.names.back() =
+                            db.make<qualified_name>(db.names.back(), name);
                     else
-                        db.names.back().first = name;
+                        db.names.back() = name;
                     db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
                     pop_subs = true;
                     t0 = t1;
                 }
                 else
                     return first;
                 break;
             case 'I':
                 t1 = parse_template_args(t0, last, db);
                 if (t1 != t0 && t1 != last)
                 {
-                    auto name = db.names.back().move_full();
+                    auto name = db.names.back();
                     db.names.pop_back();
-                    if (db.names.empty())
-                        return first;
-                    db.names.back().first += name;
-                    db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+                    db.names.back() = db.make<name_with_template_args>(
+                        db.names.back(), name);
+                    db.subs.push_back(Db::sub_type(
+                        1, db.names.back(), db.names.get_allocator()));
                     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)
                 {
-                    auto name = db.names.back().move_full();
+                    auto name = db.names.back();
                     db.names.pop_back();
-                    if (db.names.empty())
-                        return first;
-                    if (!db.names.back().first.empty())
-                        db.names.back().first += "::" + name;
+                    if (db.names.back()->k != node::k_empty_name)
+                        db.names.back() =
+                            db.make<qualified_name>(db.names.back(), name);
                     else
-                        db.names.back().first = name;
+                        db.names.back() = name;
                     db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
                     pop_subs = true;
                     t0 = t1;
                 }
                 else
                     return first;
             }
         }
if (first != last && *first == 'Z')
         if (t != first+1 && t != last && *t == 'E' && ++t != last)
         {
             switch (*t)
             {
             case 's':
                 first = parse_discriminator(t+1, last);
                 if (db.names.empty())
                     return first;
-                db.names.back().first.append("::string literal");
+                db.names.back() = db.make<qualified_name>(
+                    db.names.back(), db.make<name_type>("string literal"));
                 break;
             case 'd':
                 if (++t != last)
                 {
                     const char* t1 = parse_number(t, last);
                     if (t1 != last && *t1 == '_')
                     {
                         t = t1 + 1;
                         t1 = parse_name(t, last, db,
                                         ends_with_template_args);
                         if (t1 != t)
                         {
                             if (db.names.size() < 2)
                                 return first;
-                            auto name = db.names.back().move_full();
+                            auto name = db.names.back();
                             db.names.pop_back();
                             if (db.names.empty())
                                 return first;
-                            db.names.back().first.append("::");
-                            db.names.back().first.append(name);
+                            db.names.back() =
+                                db.make<qualified_name>(db.names.back(), name);
                             first = t1;
                         }
                         else if (!db.names.empty())
                             db.names.pop_back();
                     }
                 }
                 break;
             default:
                 {
                     const char* t1 = parse_name(t, last, db,
                                                 ends_with_template_args);
                     if (t1 != t)
                     {
                         // parse but ignore discriminator
                         first = parse_discriminator(t1, last);
                         if (db.names.size() < 2)
                             return first;
-                        auto name = db.names.back().move_full();
+                        auto name = db.names.back();
                         db.names.pop_back();
                         if (db.names.empty())
                             return first;
-                        db.names.back().first.append("::");
-                        db.names.back().first.append(name);
+                        db.names.back() =
+                            db.make<qualified_name>(db.names.back(), name);
                     }
                     else if (!db.names.empty())
                         db.names.pop_back();
                 }
                 break;
             }
         }
     }
if (last - first >= 2)
                         return first;
                     db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
                     t0 = t1;
                     t1 = parse_template_args(t0, last, db);
                     if (t1 != t0)
                     {
                         if (db.names.size() < 2)
                             return first;
-                        auto tmp = db.names.back().move_full();
+                        auto tmp = db.names.back();
                         db.names.pop_back();
                         if (db.names.empty())
                             return first;
-                        db.names.back().first += tmp;
+                        db.names.back() =
+                            db.make<name_with_template_args>(
+                                db.names.back(), tmp);
                         first = t1;
                         if (ends_with_template_args)
                             *ends_with_template_args = true;
                     }
                 }
                 else   // <unscoped-name>
                     first = t1;
             }
             else
             {   // try <substitution> <template-args>
                 t1 = parse_substitution(t0, last, db);
                 if (t1 != t0 && t1 != last && *t1 == 'I')
                 {
                     t0 = t1;
                     t1 = parse_template_args(t0, last, db);
                     if (t1 != t0)
                     {
                         if (db.names.size() < 2)
                             return first;
-                        auto tmp = db.names.back().move_full();
+                        auto tmp = db.names.back();
                         db.names.pop_back();
                         if (db.names.empty())
                             return first;
-                        db.names.back().first += tmp;
+                        db.names.back() =
+                            db.make<name_with_template_args>(
+                                db.names.back(), tmp);
                         first = t1;
                         if (ends_with_template_args)
                             *ends_with_template_args = true;
                     }
                 }
             }
             break;
           }
if (last - first > 2)
             {
             case 'V':
                 // TV <type>    # virtual table
                 t = parse_type(first+2, last, db);
                 if (t != first+2)
                 {
                     if (db.names.empty())
                         return first;
-                    db.names.back().first.insert(0, "vtable for ");
+                    db.names.back() =
+                        db.make<special_name>("vtable for ", db.names.back());
                     first = t;
                 }
                 break;
             case 'T':
                 // TT <type>    # VTT structure (construction vtable index)
                 t = parse_type(first+2, last, db);
                 if (t != first+2)
                 {
                     if (db.names.empty())
                         return first;
-                    db.names.back().first.insert(0, "VTT for ");
+                    db.names.back() =
+                        db.make<special_name>("VTT for ", db.names.back());
                     first = t;
                 }
                 break;
             case 'I':
                 // TI <type>    # typeinfo structure
                 t = parse_type(first+2, last, db);
                 if (t != first+2)
                 {
                     if (db.names.empty())
                         return first;
-                    db.names.back().first.insert(0, "typeinfo for ");
+                    db.names.back() =
+                        db.make<special_name>("typeinfo for ", db.names.back());
                     first = t;
                 }
                 break;
             case 'S':
                 // TS <type>    # typeinfo name (null-terminated byte string)
                 t = parse_type(first+2, last, db);
                 if (t != first+2)
                 {
                     if (db.names.empty())
                         return first;
-                    db.names.back().first.insert(0, "typeinfo name for ");
+                    db.names.back() =
+                        db.make<special_name>("typeinfo name for ", db.names.back());
                     first = t;
                 }
                 break;
             case 'c':
                 // Tc <call-offset> <call-offset> <base encoding>
               {
                 const char* t0 = parse_call_offset(first+2, last);
                 if (t0 == first+2)
                     break;
                 const char* t1 = parse_call_offset(t0, last);
                 if (t1 == t0)
                     break;
                 t = parse_encoding(t1, last, db);
                 if (t != t1)
                 {
                     if (db.names.empty())
                         return first;
-                    db.names.back().first.insert(0, "covariant return thunk to ");
+                    db.names.back() =
+                        db.make<special_name>("covariant return thunk to ",
+                                              db.names.back());
                     first = t;
                 }
               }
                 break;
             case 'C':
                 // extension ::= TC <first type> <number> _ <second type> # construction vtable for second-in-first
                 t = parse_type(first+2, last, db);
                 if (t != first+2)
                 {
                     const char* t0 = parse_number(t, last);
                     if (t0 != t && t0 != last && *t0 == '_')
                     {
                         const char* t1 = parse_type(++t0, last, db);
                         if (t1 != t0)
                         {
                             if (db.names.size() < 2)
                                 return first;
-                            auto left = db.names.back().move_full();
+                            auto left = db.names.back();
                             db.names.pop_back();
                             if (db.names.empty())
                                 return first;
-                            db.names.back().first = "construction vtable for " +
-                                                    std::move(left) + "-in-" +
-                                                    db.names.back().move_full();
+                            db.names.back() = db.make<ctor_vtable_special_name>(
+                                left, db.names.back());
                             first = t1;
                         }
                     }
                 }
                 break;
             case 'W':
                 // TW <object name> # Thread-local wrapper
                 t = parse_name(first + 2, last, db);
                 if (t != first + 2) 
                 {
                     if (db.names.empty())
                         return first;
-                    db.names.back().first.insert(0, "thread-local wrapper routine for ");
+                    db.names.back() =
+                        db.make<special_name>("thread-local wrapper routine for ",
+                                              db.names.back());
                     first = t;
                 }
                 break;
             case 'H':
                 //TH <object name> # Thread-local initialization
                 t = parse_name(first + 2, last, db);
                 if (t != first + 2) 
                 {
                     if (db.names.empty())
                         return first;
-                    db.names.back().first.insert(0, "thread-local initialization routine for ");
+                    db.names.back() = db.make<special_name>(
+                        "thread-local initialization routine for ", db.names.back());
                     first = t;
                 }
                 break;
             default:
                 // T <call-offset> <base encoding>
                 {
                 const char* t0 = parse_call_offset(first+1, last);
                 if (t0 == first+1)
                     break;
                 t = parse_encoding(t0, last, db);
                 if (t != t0)
                 {
                     if (db.names.empty())
                         return first;
                     if (first[1] == 'v')
                     {
-                        db.names.back().first.insert(0, "virtual thunk to ");
+                        db.names.back() =
+                            db.make<special_name>("virtual thunk to ",
+                                                  db.names.back());
                         first = t;
                     }
                     else
                     {
-                        db.names.back().first.insert(0, "non-virtual thunk to ");
+                        db.names.back() =
+                            db.make<special_name>("non-virtual thunk to ",
+                                                  db.names.back());
                         first = t;
                     }
                 }
                 }
                 break;
             }
             break;
         case 'G':
             switch (first[1])
             {
             case 'V':
                 // GV <object name> # Guard variable for one-time initialization
                 t = parse_name(first+2, last, db);
                 if (t != first+2)
                 {
                     if (db.names.empty())
                         return first;
-                    db.names.back().first.insert(0, "guard variable for ");
+                    db.names.back() =
+                        db.make<special_name>("guard variable for ", db.names.back());
                     first = t;
                 }
                 break;
             case 'R':
                 // extension ::= GR <object name> # reference temporary for object
                 t = parse_name(first+2, last, db);
                 if (t != first+2)
                 {
                     if (db.names.empty())
                         return first;
-                    db.names.back().first.insert(0, "reference temporary for ");
+                    db.names.back() =
+                        db.make<special_name>("reference temporary for ",
+                                              db.names.back());
                     first = t;
                 }
                 break;
             }
             break;
         }
     }
     return first;
if (first != last)
         case 'T':
             first = parse_special_name(first, last, db);
             break;
         default:
           {
             bool ends_with_template_args = false;
             const char* t = parse_name(first, last, db,
                                        &ends_with_template_args);
-            unsigned cv = db.cv;
-            unsigned ref = db.ref;
+            if (db.names.empty())
+                return first;
+            qualifiers cv = db.cv;
+            function_ref_qual ref = db.ref;
             if (t != first)
             {
                 if (t != last && *t != 'E' && *t != '.')
                 {
                     save_value<bool> sb2(db.tag_templates);
                     db.tag_templates = false;
                     const char* t2;
-                    Db::String ret2;
                     if (db.names.empty())
                         return first;
-                    const Db::String& nm = db.names.back().first;
-                    if (nm.empty())
+                    if (!db.names.back())
                         return first;
+                    node* return_type = nullptr;
                     if (!db.parsed_ctor_dtor_cv && ends_with_template_args)
                     {
                         t2 = parse_type(t, last, db);
                         if (t2 == t)
                             return first;
-                        if (db.names.size() < 2)
+                        if (db.names.size() < 1)
                             return first;
-                        auto ret1 = std::move(db.names.back().first);
-                        ret2 = std::move(db.names.back().second);
-                        if (ret2.empty())
-                            ret1 += ' ';
+                        return_type = db.names.back();
                         db.names.pop_back();
-                        if (db.names.empty())
-                            return first;
-
-                        db.names.back().first.insert(0, ret1);
                         t = t2;
                     }
-                    db.names.back().first += '(';
+
+                    node* result = nullptr;
+
                     if (t != last && *t == 'v')
                     {
                         ++t;
+                        node* name = db.names.back();
+                        db.names.pop_back();
+                        result = db.make<top_level_function_decl>(
+                            return_type, name, node_array());
                     }
                     else
                     {
-                        bool first_arg = true;
+                        size_t params_begin = db.names.size();
                         while (true)
                         {
-                            size_t k0 = db.names.size();
                             t2 = parse_type(t, last, db);
-                            size_t k1 = db.names.size();
                             if (t2 == t)
                                 break;
-                            if (k1 > k0)
-                            {
-                                Db::String tmp;
-                                for (size_t k = k0; k < k1; ++k)
-                                {
-                                    if (!tmp.empty())
-                                        tmp += ", ";
-                                    tmp += db.names[k].move_full();
-                                }
-                                for (size_t k = k0; k < k1; ++k) {
-                                    if (db.names.empty())
-                                        return first;
-                                    db.names.pop_back();
-                                }
-                                if (!tmp.empty())
-                                {
-                                    if (db.names.empty())
-                                        return first;
-                                    if (!first_arg)
-                                        db.names.back().first += ", ";
-                                    else
-                                        first_arg = false;
-                                    db.names.back().first += tmp;
-                                }
-                            }
-                            t = t2;
-                        }
+                            t = t2;
+                        if (db.names.size() < params_begin)
+                        node_array params =
+                            db.pop_trailing_node_array(params_begin);
+                        node* name = db.names.back();
+                        db.names.pop_back();
+                        result = db.make<top_level_function_decl>(
+                            return_type, name, params);
                     }
-                    if (db.names.empty())
-                        return first;
-                    db.names.back().first += ')';
-                    if (cv & 1)
-                        db.names.back().first.append(" const");
-                    if (cv & 2)
-                        db.names.back().first.append(" volatile");
-                    if (cv & 4)
-                        db.names.back().first.append(" restrict");
-                    if (ref == 1)
-                        db.names.back().first.append(" &");
-                    else if (ref == 2)
-                        db.names.back().first.append(" &&");
-                    db.names.back().first += ret2;
+                    if (ref != fref_qual_none)
+                        result = db.make<function_ref_qual_type>(result, ref);
+                    if (cv != qual_none)
+                        result = db.make<function_qual_type>(result, cv);
+                    db.names.push_back(result);
                     first = t;
                 }
                 else
                     first = t;
             }
             break;
           }
         }
     }
     return first;
 }
 
 // _block_invoke
 // _block_invoke<decimal-digit>+
 // _block_invoke_<decimal-digit>+
 
 const char*
 parse_block_invoke(const char* first, const char* last, Db& db)
 {
     if (last - first >= 13)
     {
+        // FIXME: strcmp?
         const char test[] = "_block_invoke";
         const char* t = first;
         for (int i = 0; i < 13; ++i, ++t)
         {
             if (*t != test[i])
                 return first;
         }
         if (t != last)
         {
             if (*t == '_')
             {
                 // must have at least 1 decimal digit
                 if (++t == last || !std::isdigit(*t))
                     return first;
                 ++t;
             }
             // parse zero or more digits
             while (t != last && isdigit(*t))
                 ++t;
         }
         if (db.names.empty())
             return first;
-        db.names.back().first.insert(0, "invocation function for block in ");
+        db.names.back() =
+            db.make<special_name>("invocation function for block in ",
+                                  db.names.back());
         first = t;
     }
     return first;
 }
 
 // extension
 // <dot-suffix> := .<anything and everything>
 
 const char*
 parse_dot_suffix(const char* first, const char* last, Db& db)
 {
     if (first != last && *first == '.')
     {
         if (db.names.empty())
             return first;
-        db.names.back().first += " (" + Db::String(first, last) + ")";
+        db.names.back() =
+            db.make<dot_suffix>(db.names.back(), string_ref(first, last));
         first = last;
     }
     return first;
 }
 
 // <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>+
__cxa_demangle(const char *mangled_name, char *buf, size_t *n, int *status) {
     size_t internal_size = buf != nullptr ? *n : 0;
     arena<bs> a;
     Db db(a);
     db.template_param.emplace_back(a);
     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.fix_forward_references &&
            !db.template_param.empty() && !db.template_param.front().empty())
     {
         db.fix_forward_references = false;
         db.tag_templates = false;
         db.names.clear();
         db.subs.clear();
         demangle(mangled_name, mangled_name + len, db, internal_status);
         if (db.fix_forward_references)
             internal_status = invalid_mangled_name;
     }
+
     if (internal_status == success)
     {
-        size_t sz = db.names.back().size() + 1;
-        if (sz > internal_size)
-        {
-            char* newbuf = static_cast<char*>(std::realloc(buf, sz));
-            if (newbuf == nullptr)
-            {
-                internal_status = memory_alloc_failure;
-                buf = nullptr;
-            }
-            else
-            {
-                buf = newbuf;
-                if (n != nullptr)
-                    *n = sz;
-            }
+        if (!buf)
+            internal_size = 1024;
+            buf = static_cast<char*>(std::malloc(internal_size));
         }
-        if (buf != nullptr)
+
+        if (buf)
         {
-            db.names.back().first += db.names.back().second;
-            std::memcpy(buf, db.names.back().first.data(), sz-1);
-            buf[sz-1] = char(0);
+            output_stream s(buf, internal_size);
+            db.names.back()->print(s);
+            s += '\0';
+            if (n) *n = s.get_current_position();
+            buf = s.get_buffer();
         }
+        else
+            internal_status = memory_alloc_failure;
     }
     else
         buf = nullptr;
     if (status)
         *status = internal_status;
     return buf;
 }
 
 }  // __cxxabiv1

test/test_demangle.pass.cpp

     // 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"},
-    // FIXME(compnerd) pretty print this as void (*)(unsigned long &) volatile &&
-    {"PVFvRmOE", "void (*)(unsigned long&)  volatile&&"},
+    {"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))"},
 };
 
 const unsigned N = sizeof(cases) / sizeof(cases[0]);