Index: src/cxa_demangle.cpp
===================================================================
--- src/cxa_demangle.cpp
+++ src/cxa_demangle.cpp
@@ -41,6 +41,1520 @@
     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());
+}
+
+class 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));
+        }
+    }
+
+    friend class stream_string_ref;
+
+public:
+    stream(char* start_buf, size_t sz)
+            : buffer(start_buf), current_position(0), buffer_capacity(sz) {}
+
+    stream& operator+=(string_ref r)
+    {
+        size_t sz = r.size();
+        grow(sz);
+        memmove(buffer + current_position, r.begin(), sz);
+        current_position += sz;
+        return *this;
+    }
+
+    stream& operator+=(char c)
+    {
+        grow(1);
+        buffer[current_position++] = c;
+        return *this;
+    }
+
+    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 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; }
+    };
+
+    stream& operator+=(stream_string_ref& s)
+    {
+        size_t sz = static_cast<size_t>(s.last - s.first);
+        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; }
+};
+
+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(stream &s) const {
+        print_left(s);
+        if (has_rhs_component())
+            print_right(s);
+    }
+
+    virtual void print_left(stream& s) const = 0;
+    virtual void print_right(stream&) const {}
+
+    virtual string_ref get_base_name() const { return string_ref(); }
+
+    // Silence compiler warnings, this dtor will never be called.
+    virtual ~node() {}
+};
+
+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(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(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(stream& s) const override
+    {
+        ext->print(s);
+        s += " ";
+        ty->print_left(s);
+    }
+
+    void print_right(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(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(stream& s) const override
+    {
+        child->print_left(s);
+        print_quals(s);
+    }
+
+    void print_right(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(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(stream& s) const override
+    {
+        ty->print_left(s);
+        s += postfix;
+    }
+
+    void print_right(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(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(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(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(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(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(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(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(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(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(stream& s) const override
+    {
+        if (member_type->has_array() || member_type->has_function())
+            s += ")";
+        member_type->print_right(s);
+    }
+};
+
+struct 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(stream& s) const override {
+        base->print_left(s);
+    }
+
+    void print_right(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(stream& s) const override
+    {
+        ret->print_left(s);
+        s += " ";
+    }
+
+    void print_right(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(stream& s) const override
+    {
+        if (ret) {
+            ret->print_left(s);
+            if (!ret->has_rhs_component())
+                s += " ";
+        }
+        name->print(s);
+    }
+
+    void print_right(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(stream& s) const
+    {
+        if (quals == fref_qual_lvalue)
+            s += " &";
+        else
+            s += " &&";
+    }
+
+    void print_left(stream& s) const override { fn->print_left(s); }
+
+    void print_right(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(stream& s) const override
+    {
+        child->print_left(s);
+    }
+
+    void print_right(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(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(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(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 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(stream& s) const override
+    {
+        if (!cache.empty())
+        {
+            s += cache;
+            return;
+        }
+
+        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(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(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 stream::stream_string_ref cache;
+public:
+    template_params(node_array params)
+            : node(k_template_params), params(params) {}
+
+    void print_left(stream& s) const override
+    {
+        if (!cache.empty())
+        {
+            s += cache;
+            return;
+        }
+
+        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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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
 {
@@ -204,50 +1718,112 @@
 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;
+
+    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);
+    }
 
-    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);}
+    ~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);
@@ -383,39 +1959,20 @@
 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)
+    if (static_cast<std::size_t>(last - first) <= N)
+        return first;
+    last = first + N;
+    const char* t = first;
+    for (; t != last; ++t)
     {
-        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 (!isxdigit(*t))
+            return first;
+    }
+    if (*t == 'E')
+    {
+        db.names.push_back(
+            db.make<float_expr<Float>>(string_ref(first, t)));
+        first = t + 1;
     }
     return first;
 }
@@ -440,11 +1997,11 @@
             }
             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;
             }
         }
@@ -473,27 +2030,32 @@
             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 '_':
@@ -578,87 +2140,87 @@
         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':
@@ -674,39 +2236,39 @@
                 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;
                 }
@@ -720,24 +2282,24 @@
 // <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;
         }
     }
@@ -766,7 +2328,7 @@
                 }
                 else
                 {
-                    db.names.push_back("T_");
+                    db.names.push_back(db.make<name_type>("T_"));
                     first += 2;
                     db.fix_forward_references = true;
                 }
@@ -791,7 +2353,8 @@
                 }
                 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;
                 }
@@ -816,11 +2379,12 @@
             {
                 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;
             }
         }
@@ -843,11 +2407,12 @@
             {
                 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;
             }
         }
@@ -870,11 +2435,12 @@
             {
                 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;
             }
         }
@@ -897,9 +2463,10 @@
             {
                 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;
             }
         }
@@ -933,7 +2500,8 @@
         {
             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;
         }
     }
@@ -952,7 +2520,8 @@
         {
             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;
         }
     }
@@ -969,20 +2538,11 @@
         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;
         }
     }
@@ -1001,18 +2561,19 @@
     {
         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')
             {
@@ -1021,7 +2582,8 @@
                 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;
                 }
             }
@@ -1042,7 +2604,8 @@
         {
             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;
         }
     }
@@ -1066,7 +2629,8 @@
         {
             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;
         }
     }
@@ -1085,7 +2649,7 @@
         {
             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;
         }
     }
@@ -1107,9 +2671,10 @@
             {
                 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;
             }
         }
@@ -1132,9 +2697,10 @@
             {
                 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;
         }
@@ -1196,7 +2762,8 @@
                     {
                         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;
                     }
@@ -1223,7 +2790,7 @@
         {
             if (db.names.empty())
                 return first;
-            db.names.back().first.insert(0, "~");
+            db.names.back() = db.make<dtor_name>(db.names.back());
             first = t;
         }
     }
@@ -1255,9 +2822,11 @@
                     {
                         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);
                     }
                 }
             }
@@ -1281,9 +2850,11 @@
                     {
                         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);
                     }
                 }
             }
@@ -1331,7 +2902,8 @@
             {
                 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;
         }
@@ -1349,9 +2921,10 @@
                 {
                     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)
                     {
@@ -1364,9 +2937,10 @@
                     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;
@@ -1379,9 +2953,10 @@
                 }
                 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
@@ -1396,9 +2971,11 @@
                     {
                         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);
@@ -1410,9 +2987,10 @@
                     }
                     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
@@ -1425,16 +3003,19 @@
                     {
                         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;
@@ -1447,9 +3028,10 @@
                     }
                     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;
                 }
             }
@@ -1473,11 +3055,11 @@
             {
                 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;
             }
         }
@@ -1493,44 +3075,25 @@
     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 || t == first + 2 || db.names.empty())
+            return first;
+        node* callee = db.names.back();
+        db.names.pop_back();
+        size_t args_begin = db.names.size();
+        while (*t != 'E')
         {
-            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())
+            const char* t1 = parse_expression(t, last, db);
+            if (t1 == last || t1 == t)
                 return first;
-            db.names.back().first.append(")");
-            first = t;
+            t = t1;
         }
+        if (db.names.size() < args_begin)
+            return first;
+        ++t;
+        call_expr* the_call = db.make<call_expr>(
+            callee, db.pop_trailing_node_array(args_begin));
+        db.names.push_back(the_call);
+        first = t;
     }
     return first;
 }
@@ -1559,31 +3122,18 @@
             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)
@@ -1594,65 +3144,25 @@
             {
                 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())
+            if (*t != 'E')
                 return first;
-            auto type = db.names.back().move_full();
+            auto type = db.names.back();
             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));
+            db.names.push_back(
+                db.make<new_expr>(expr_list, type, init_list,
+                                  parsed_gs, is_array));
             first = t+1;
         }
     }
@@ -1669,10 +3179,12 @@
     {
         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);
@@ -1685,41 +3197,30 @@
                 ++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;
         }
     }
@@ -1741,10 +3242,10 @@
             {
                 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;
             }
         }
@@ -1772,11 +3273,13 @@
                     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)
@@ -1797,45 +3300,30 @@
                     }
                     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;
             }
         }
@@ -1861,16 +3349,8 @@
                 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;
             }
         }
@@ -1893,9 +3373,7 @@
             {
                 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;
             }
         }
@@ -1909,9 +3387,9 @@
                 {
                     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;
                 }
             }
@@ -1926,13 +3404,11 @@
                 {
                     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;
                 }
             }
@@ -1959,7 +3435,8 @@
                 {
                     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;
                 }
             }
@@ -1997,21 +3474,24 @@
                     {
                         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 != '_')
             {
@@ -2020,7 +3500,7 @@
                 {
                     if (db.names.empty())
                         return first;
-                    num = db.names.back().move_full();
+                    num = db.names.back();
                     db.names.pop_back();
                     t1 = t;
                 }
@@ -2032,9 +3512,15 @@
                 {
                     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);
             }
         }
     }
@@ -2075,7 +3561,7 @@
             case 'V':
             case 'K':
               {
-                unsigned cv = 0;
+                qualifiers cv = qual_none;
                 const char* t = parse_cv_qualifiers(first, last, cv);
                 if (t != first)
                 {
@@ -2090,35 +3576,13 @@
                         db.subs.emplace_back(db.names.get_allocator());
                         for (size_t k = k0; k < k1; ++k)
                         {
-                            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");
-                            }
-                            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");
+                            if (cv) {
+                                if (is_function)
+                                    db.names[k] = db.make<function_qual_type>(
+                                        db.names[k], cv);
+                                else
+                                    db.names[k] =
+                                        db.make<qual_type>(db.names[k], cv);
                             }
                             db.subs.back().push_back(db.names[k]);
                         }
@@ -2154,7 +3618,8 @@
                         {
                             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()));
                         }
@@ -2175,7 +3640,8 @@
                         {
                             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()));
                         }
@@ -2200,18 +3666,8 @@
                             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;
@@ -2228,25 +3684,7 @@
                             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;
@@ -2263,18 +3701,8 @@
                             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;
@@ -2296,10 +3724,14 @@
                                 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;
                                 }
                             }
@@ -2318,24 +3750,25 @@
                                 {
                                     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()));
@@ -2369,9 +3802,11 @@
                                 {
                                     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;
@@ -2517,20 +3952,20 @@
             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;
             }
@@ -2539,15 +3974,15 @@
             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':
@@ -2560,7 +3995,8 @@
                     {
                         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;
                     }
@@ -2572,23 +4008,23 @@
             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;
             }
@@ -2597,15 +4033,15 @@
             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;
             }
@@ -2614,11 +4050,11 @@
             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;
             }
@@ -2626,7 +4062,7 @@
         case 'i':
             if (first[1] == 'x')
             {
-                db.names.push_back("operator[]");
+                db.names.push_back(db.make<name_type>("operator[]"));
                 first += 2;
             }
             break;
@@ -2634,7 +4070,7 @@
             switch (first[1])
             {
             case 'e':
-                db.names.push_back("operator<=");
+                db.names.push_back(db.make<name_type>("operator<="));
                 first += 2;
                 break;
             case 'i':
@@ -2644,21 +4080,22 @@
                     {
                         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;
             }
@@ -2667,23 +4104,23 @@
             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;
             }
@@ -2692,23 +4129,23 @@
             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;
             }
@@ -2717,15 +4154,15 @@
             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;
             }
@@ -2734,27 +4171,27 @@
             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;
             }
@@ -2762,7 +4199,7 @@
         case 'q':
             if (first[1] == 'u')
             {
-                db.names.push_back("operator?");
+                db.names.push_back(db.make<name_type>("operator?"));
                 first += 2;
             }
             break;
@@ -2770,19 +4207,19 @@
             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;
             }
@@ -2795,7 +4232,8 @@
                 {
                     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;
                 }
             }
@@ -2806,23 +4244,13 @@
 }
 
 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;
@@ -2855,11 +4283,11 @@
                 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;
                 }
@@ -3004,7 +4432,8 @@
                         {
                             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;
                         }
@@ -3021,69 +4450,22 @@
     return first;
 }
 
-template <class String>
-String
-base_name(String& s)
+node* maybe_change_special_sub_name(node* inp, Db& db)
 {
-    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")
+    if (inp->k != node::k_special_substitution)
+        return inp;
+    auto kind = static_cast<special_substitution*>(inp)->k;
+    switch (kind)
     {
-        s = "std::basic_iostream<char, std::char_traits<char> >";
-        return "basic_iostream";
+    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:
+        break;
     }
-    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);
+    return inp;
 }
 
 // <ctor-dtor-name> ::= C1    # complete object constructor
@@ -3111,7 +4493,10 @@
             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;
@@ -3126,7 +4511,8 @@
             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;
@@ -3154,106 +4540,63 @@
         {
         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();
+                if (db.names.size() < begin_pos)
                     return first;
-                }
-                if (db.names.empty() || db.names.size() - 1 != lambda_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;
-            }
+                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;
@@ -3334,7 +4677,8 @@
             {
                 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;
         }
@@ -3354,7 +4698,8 @@
         {
             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;
         }
     }
@@ -3373,7 +4718,8 @@
         {
             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;
         }
     }
@@ -3388,28 +4734,29 @@
     {
         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)
@@ -3419,16 +4766,10 @@
         {
             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())
@@ -3570,8 +4911,8 @@
                     {
                         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;
                     }
                 }
@@ -3591,8 +4932,8 @@
                     {
                         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;
                     }
                 }
@@ -3663,10 +5004,11 @@
                     {
                         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())
@@ -3736,7 +5078,8 @@
                     {
                         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;
                     }
                 }
@@ -3826,7 +5169,8 @@
                     {
                         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;
                     }
                 }
@@ -3855,12 +5199,13 @@
                         {
                             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
@@ -3945,7 +5290,7 @@
                 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':
@@ -4034,7 +5379,7 @@
         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)
@@ -4044,7 +5389,7 @@
             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)
             {
@@ -4052,24 +5397,12 @@
                 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;
 }
@@ -4096,32 +5429,29 @@
 {
     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')
@@ -4136,17 +5466,18 @@
                 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;
                 }
@@ -4157,14 +5488,13 @@
                 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;
@@ -4178,14 +5508,13 @@
                 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;
@@ -4197,12 +5526,12 @@
                 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;
                 }
@@ -4218,14 +5547,13 @@
                 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;
@@ -4301,7 +5629,8 @@
                 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)
@@ -4316,12 +5645,12 @@
                         {
                             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())
@@ -4339,12 +5668,12 @@
                         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();
@@ -4408,11 +5737,13 @@
                     {
                         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;
@@ -4432,11 +5763,13 @@
                     {
                         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;
@@ -4524,7 +5857,8 @@
                 {
                     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;
@@ -4535,7 +5869,8 @@
                 {
                     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;
@@ -4546,7 +5881,8 @@
                 {
                     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;
@@ -4557,7 +5893,8 @@
                 {
                     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;
@@ -4575,7 +5912,9 @@
                 {
                     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;
                 }
               }
@@ -4593,13 +5932,12 @@
                         {
                             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;
                         }
                     }
@@ -4611,8 +5949,10 @@
                 if (t != first + 2) 
                 {
                     if (db.names.empty())
-                    return first;
-                    db.names.back().first.insert(0, "thread-local wrapper routine for ");
+                        return first;
+                    db.names.back() =
+                        db.make<special_name>("thread-local wrapper routine for ",
+                                              db.names.back());
                     first = t;
                 }
                 break;
@@ -4622,8 +5962,9 @@
                 if (t != first + 2) 
                 {
                     if (db.names.empty())
-                    return first;
-                    db.names.back().first.insert(0, "thread-local initialization routine for ");
+                        return first;
+                    db.names.back() = db.make<special_name>(
+                        "thread-local initialization routine for ", db.names.back());
                     first = t;
                 }
                 break;
@@ -4640,12 +5981,16 @@
                         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;
                     }
                 }
@@ -4663,7 +6008,8 @@
                 {
                     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;
@@ -4674,7 +6020,9 @@
                 {
                     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;
@@ -4732,8 +6080,10 @@
             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 != '.')
@@ -4741,87 +6091,59 @@
                     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;
                         }
+                        if (db.names.size() < params_begin)
+                            return first;
+                        node_array params =
+                            db.pop_trailing_node_array(params_begin);
+                        if (db.names.empty())
+                            return first;
+                        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
@@ -4843,6 +6165,7 @@
 {
     if (last - first >= 13)
     {
+        // FIXME: strcmp?
         const char test[] = "_block_invoke";
         const char* t = first;
         for (int i = 0; i < 13; ++i, ++t)
@@ -4865,7 +6188,9 @@
         }
         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;
@@ -4881,7 +6206,8 @@
     {
         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;
@@ -4960,6 +6286,7 @@
     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())
     {
@@ -4971,30 +6298,25 @@
         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)
+        if (!buf)
         {
-            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;
-            }
+            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);
+            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;
Index: test/test_demangle.pass.cpp
===================================================================
--- test/test_demangle.pass.cpp
+++ test/test_demangle.pass.cpp
@@ -29600,8 +29600,7 @@
     {"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"},