Index: src/cxa_demangle.cpp =================================================================== --- src/cxa_demangle.cpp +++ src/cxa_demangle.cpp @@ -1407,117 +1407,6 @@ } }; -template -class arena -{ - static const std::size_t alignment = 16; - alignas(alignment) char buf_[N]; - char* ptr_; - - std::size_t - align_up(std::size_t n) noexcept - {return (n + (alignment-1)) & ~(alignment-1);} - - bool - pointer_in_buffer(char* p) noexcept - {return buf_ <= p && p <= buf_ + N;} - -public: - arena() noexcept : ptr_(buf_) {} - ~arena() {ptr_ = nullptr;} - arena(const arena&) = delete; - arena& operator=(const arena&) = delete; - - char* allocate(std::size_t n); - void deallocate(char* p, std::size_t n) noexcept; - - static constexpr std::size_t size() {return N;} - std::size_t used() const {return static_cast(ptr_ - buf_);} - void reset() {ptr_ = buf_;} -}; - -template -char* -arena::allocate(std::size_t n) -{ - n = align_up(n); - if (static_cast(buf_ + N - ptr_) >= n) - { - char* r = ptr_; - ptr_ += n; - return r; - } - return static_cast(std::malloc(n)); -} - -template -void -arena::deallocate(char* p, std::size_t n) noexcept -{ - if (pointer_in_buffer(p)) - { - n = align_up(n); - if (p + n == ptr_) - ptr_ = p; - } - else - std::free(p); -} - -template -class short_alloc -{ - arena& a_; -public: - typedef T value_type; - -public: - template struct rebind {typedef short_alloc<_Up, N> other;}; - - short_alloc(arena& a) noexcept : a_(a) {} - template - short_alloc(const short_alloc& a) noexcept - : a_(a.a_) {} - short_alloc(const short_alloc&) = default; - short_alloc& operator=(const short_alloc&) = delete; - - T* allocate(std::size_t n) - { - return reinterpret_cast(a_.allocate(n*sizeof(T))); - } - void deallocate(T* p, std::size_t n) noexcept - { - a_.deallocate(reinterpret_cast(p), n*sizeof(T)); - } - - template - friend - bool - operator==(const short_alloc& x, const short_alloc& y) noexcept; - - template friend class short_alloc; -}; - -template -inline -bool -operator==(const short_alloc& x, const short_alloc& y) noexcept -{ - return N == M && &x.a_ == &y.a_; -} - -template -inline -bool -operator!=(const short_alloc& x, const short_alloc& y) noexcept -{ - return !(x == y); -} - -const size_t bs = 4 * 1024; -template using Alloc = short_alloc; -template using Vector = std::vector>; - class BumpPointerAllocator { struct BlockMeta { BlockMeta* Next; @@ -1568,13 +1457,179 @@ } }; +template +class PODSmallVector { + static_assert(std::is_pod::value, ""); + + T *First; + T *Last; + T *Cap; + T Inline[N]; + + bool isInline() const { return First == Inline; } + +public: + PODSmallVector() : First(Inline), Last(First), Cap(Inline + N) {} + + PODSmallVector(const PODSmallVector &) = delete; + PODSmallVector& operator=(const PODSmallVector&) = delete; + + PODSmallVector(PODSmallVector&& Other) { + if (Other.isInline()) { + std::copy(Other.begin(), Other.end(), Inline); + First = Inline; + Last = First + Other.size(); + Cap = Inline + N; + Other.clear(); + return; + } + + First = Other.First; + Last = Other.Last; + Cap = Other.Cap; + Other.First = Other.Inline; + Other.Last = Other.Inline; + Other.Cap = Other.Inline + N; + } + + PODSmallVector& operator=(PODSmallVector&& Other) { + if (Other.isInline()) { + if (!isInline()) { + std::free(First); + First = Inline; + Last = Inline; + Cap = Inline + N; + } + std::copy(Other.begin(), Other.end(), begin()); + Last = First + Other.size(); + return *this; + } + + if (!isInline()) + std::free(First); + + First = Other.First; + Last = Other.Last; + Cap = Other.Cap; + + Other.First = Other.Inline; + Other.Last = Other.Inline; + Other.Cap = Other.Inline + N; + return *this; + } + + void push_back(const T &Elem) { + if (Last != Cap) { + *Last++ = Elem; + return; + } + + size_t S = size(); + if (!isInline()) { + First = static_cast(std::realloc(First, sizeof(T) * S * 2)); + } else { + First = static_cast(std::malloc(sizeof(T) * S * 2)); + std::copy(std::begin(Inline), std::end(Inline), First); + } + Last = First + S; + Cap = First + S * 2; + *Last++ = Elem; + return; + } + + void pop_back() { --Last; } + + void dropBack(size_t Index) { Last = First + Index; } + + T *begin() { return First; } + T *end() { return Last; } + + bool empty() const { return First == Last; } + size_t size() const { return static_cast(Last - First); } + T& back() { return *(Last - 1); } + T& operator[](size_t Index) { return *(begin() + Index); } + void clear() { Last = First; } + + ~PODSmallVector() { + if (!isInline()) + std::free(First); + } +}; + +// Substitution table. This type is used to track the substitutions that are +// known by the parser. +template +class SubTable { + // Subs hold the actual entries in the table, and PackIndices tells us which + // entries are members of which pack. For example, if the substitutions we're + // tracking are: {int, {float, FooBar}, char}, with {float, FooBar} being a + // parameter pack, we represent the substitutions as: + // Subs: int, float, FooBar, char + // PackIndices: 0, 1, 3 + // So, PackIndicies[I] holds the offset of the begin of the Ith pack, and + // PackIndices[I + 1] holds the offset of the end. + PODSmallVector Subs; + PODSmallVector PackIndices; + +public: + // Add a substitution that represents a single name to the table. This is + // modeled as a parameter pack with just one element. + void pushSub(Node* Entry) { + PackIndices.push_back(static_cast(Subs.size())); + Subs.push_back(Entry); + } + + // Add a new empty pack to the table. Subsequent calls to pushSubIntoPack() + // will add to this pack. + void pushPack() { PackIndices.push_back(static_cast(Subs.size())); } + void pushSubIntoPack(Node* Entry) { Subs.push_back(Entry); } + + // Remove the last pack from the table. + void popPack() { + unsigned Last = PackIndices.back(); + PackIndices.pop_back(); + Subs.dropBack(Last); + } + + // For use in a range-for loop. + struct NodePair { + Node **First; + Node **Last; + Node **begin() { return First; } + Node **end() { return Last; } + }; + + NodePair nthSub(size_t N) { + assert(N < PackIndices.size()); + Node **Begin = Subs.begin() + PackIndices[N]; + Node **End = (N + 1 == PackIndices.size()) + ? Subs.end() + : Subs.begin() + PackIndices[N + 1]; + return NodePair{Begin, End}; + } + + size_t size() const { return PackIndices.size(); } + bool empty() const { return PackIndices.empty(); } + void clear() { + Subs.clear(); + PackIndices.clear(); + } +}; + struct Db { - typedef Vector sub_type; - typedef Vector template_param_type; - sub_type names; - template_param_type subs; - Vector template_param; + // Name stack, this is used by the parser to hold temporary names that were + // parsed. The parser colapses multiple names into new nodes to construct + // the AST. Once the parser is finished, names.size() == 1. + PODSmallVector names; + + // Substitution table. Itanium supports name substitutions as a means of + // compression. The string "S42_" refers to the 42nd entry in this table. + SubTable<32> Subs; + + // Template parameter table. Like the above, but referenced like "T42_". + SubTable<4> TemplateParams; + Qualifiers cv = QualNone; FunctionRefQual ref = FrefQualNone; unsigned encoding_depth = 0; @@ -1585,13 +1640,6 @@ BumpPointerAllocator ASTAllocator; - template - Db(arena& ar) : - names(ar), - subs(0, names, ar), - template_param(0, subs, ar) - {} - template T* make(Args&& ...args) { return new (ASTAllocator.allocate(sizeof(T))) @@ -1612,7 +1660,7 @@ assert(FromPosition <= names.size()); NodeArray res = makeNodeArray( names.begin() + (long)FromPosition, names.end()); - names.erase(names.begin() + (long)FromPosition, names.end()); + names.dropBack(FromPosition); return res; } }; @@ -1799,9 +1847,9 @@ first += 2; break; case '_': - if (!db.subs.empty()) + if (!db.Subs.empty()) { - for (const auto& n : db.subs.front()) + for (Node* n : db.Subs.nthSub(0)) db.names.push_back(n); first += 2; } @@ -1826,9 +1874,9 @@ if (t == last || *t != '_') return first; ++sub; - if (sub < db.subs.size()) + if (sub < db.Subs.size()) { - for (const auto& n : db.subs[sub]) + for (Node* n : db.Subs.nthSub(sub)) db.names.push_back(n); first = t+1; } @@ -2058,11 +2106,9 @@ { if (first[1] == '_') { - if (db.template_param.empty()) - return first; - if (!db.template_param.back().empty()) + if (!db.TemplateParams.empty()) { - for (auto& t : db.template_param.back().front()) + for (Node* t : db.TemplateParams.nthSub(0)) db.names.push_back(t); first += 2; } @@ -2082,12 +2128,12 @@ sub *= 10; sub += static_cast(*t - '0'); } - if (t == last || *t != '_' || db.template_param.empty()) + if (t == last || *t != '_') return first; ++sub; - if (sub < db.template_param.back().size()) + if (sub < db.TemplateParams.size()) { - for (auto& temp : db.template_param.back()[sub]) + for (Node* temp : db.TemplateParams.nthSub(sub)) db.names.push_back(temp); first = t+1; } @@ -2469,7 +2515,7 @@ size_t k1 = db.names.size(); if (t != first && k1 == k0 + 1) { - db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator())); + db.Subs.pushSub(db.names.back()); first = t; } else @@ -2485,7 +2531,7 @@ { if (db.names.empty()) return first; - db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator())); + db.Subs.pushSub(db.names.back()); first = t; } break; @@ -2504,7 +2550,7 @@ return first; db.names.back() = db.make(db.names.back()); - db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator())); + db.Subs.pushSub(db.names.back()); first = t; } } @@ -2959,8 +3005,7 @@ db.names.begin() + (long)expr_list_begin); auto* conv_expr = db.make( types, expressions); - db.names.erase( - db.names.begin() + (long)type_begin, db.names.end()); + db.names.dropBack(type_begin); db.names.push_back(conv_expr); first = t; } @@ -3313,8 +3358,8 @@ if (t1 != t) { if (is_function) - db.subs.pop_back(); - db.subs.emplace_back(db.names.get_allocator()); + db.Subs.popPack(); + db.Subs.pushPack(); for (size_t k = k0; k < k1; ++k) { if (cv) { @@ -3325,7 +3370,7 @@ db.names[k] = db.make(db.names[k], cv); } - db.subs.back().push_back(db.names[k]); + db.Subs.pushSubIntoPack(db.names[k]); } first = t1; } @@ -3350,7 +3395,7 @@ if (db.names.empty()) return first; first = t; - db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator())); + db.Subs.pushSub(db.names.back()); } break; case 'C': @@ -3362,7 +3407,7 @@ db.names.back() = db.make( db.names.back(), " complex"); first = t; - db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator())); + db.Subs.pushSub(db.names.back()); } break; case 'F': @@ -3372,7 +3417,7 @@ if (db.names.empty()) return first; first = t; - db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator())); + db.Subs.pushSub(db.names.back()); } break; case 'G': @@ -3384,7 +3429,7 @@ db.names.back() = db.make( db.names.back(), " imaginary"); first = t; - db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator())); + db.Subs.pushSub(db.names.back()); } break; case 'M': @@ -3394,7 +3439,7 @@ if (db.names.empty()) return first; first = t; - db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator())); + db.Subs.pushSub(db.names.back()); } break; case 'O': @@ -3404,12 +3449,12 @@ size_t k1 = db.names.size(); if (t != first+1) { - db.subs.emplace_back(db.names.get_allocator()); + db.Subs.pushPack(); for (size_t k = k0; k < k1; ++k) { db.names[k] = db.make(db.names[k]); - db.subs.back().push_back(db.names[k]); + db.Subs.pushSubIntoPack(db.names[k]); } first = t; } @@ -3422,11 +3467,11 @@ size_t k1 = db.names.size(); if (t != first+1) { - db.subs.emplace_back(db.names.get_allocator()); + db.Subs.pushPack(); for (size_t k = k0; k < k1; ++k) { db.names[k] = db.make(db.names[k]); - db.subs.back().push_back(db.names[k]); + db.Subs.pushSubIntoPack(db.names[k]); } first = t; } @@ -3439,12 +3484,12 @@ size_t k1 = db.names.size(); if (t != first+1) { - db.subs.emplace_back(db.names.get_allocator()); + db.Subs.pushPack(); for (size_t k = k0; k < k1; ++k) { db.names[k] = db.make(db.names[k]); - db.subs.back().push_back(db.names[k]); + db.Subs.pushSubIntoPack(db.names[k]); } first = t; } @@ -3457,9 +3502,9 @@ size_t k1 = db.names.size(); if (t != first) { - db.subs.emplace_back(db.names.get_allocator()); + db.Subs.pushPack(); for (size_t k = k0; k < k1; ++k) - db.subs.back().push_back(db.names[k]); + db.Subs.pushSubIntoPack(db.names[k]); if (db.try_to_parse_template_args && k1 == k0+1) { const char* t1 = parse_template_args(t, last, db); @@ -3470,9 +3515,7 @@ db.names.back() = db.make< NameWithTemplateArgs>( db.names.back(), args); - db.subs.push_back(Db::sub_type( - 1, db.names.back(), - db.names.get_allocator())); + db.Subs.pushSub(db.names.back()); t = t1; } } @@ -3512,7 +3555,7 @@ db.names.push_back(db.make(type, proto)); } } - db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator())); + db.Subs.pushSub(db.names.back()); first = t2; } } @@ -3526,7 +3569,7 @@ { if (db.names.empty()) return first; - db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator())); + db.Subs.pushSub(db.names.back()); first = t; } } @@ -3551,7 +3594,7 @@ NameWithTemplateArgs>( db.names.back(), template_args); // Need to create substitution for - db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator())); + db.Subs.pushSub(db.names.back()); first = t; } } @@ -3570,9 +3613,9 @@ size_t k1 = db.names.size(); if (t != first+2) { - db.subs.emplace_back(db.names.get_allocator()); + db.Subs.pushPack(); for (size_t k = k0; k < k1; ++k) - db.subs.back().push_back(db.names[k]); + db.Subs.pushSubIntoPack(db.names[k]); first = t; return first; } @@ -3585,7 +3628,7 @@ { if (db.names.empty()) return first; - db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator())); + db.Subs.pushSub(db.names.back()); first = t; return first; } @@ -3596,7 +3639,7 @@ { if (db.names.empty()) return first; - db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator())); + db.Subs.pushSub(db.names.back()); first = t; return first; } @@ -3619,7 +3662,7 @@ { if (db.names.empty()) return first; - db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator())); + db.Subs.pushSub(db.names.back()); first = t; } } @@ -5119,27 +5162,35 @@ if (last - first >= 2 && *first == 'I') { if (db.tag_templates) - db.template_param.back().clear(); + db.TemplateParams.clear(); const char* t = first+1; size_t begin_idx = db.names.size(); while (*t != 'E') { if (db.tag_templates) - db.template_param.emplace_back(db.names.get_allocator()); - size_t k0 = db.names.size(); - const char* t1 = parse_template_arg(t, last, db); - size_t k1 = db.names.size(); - if (db.tag_templates) - db.template_param.pop_back(); - if (t1 == t || t1 == last || k0 > k1) - return first; - if (db.tag_templates) { - db.template_param.back().emplace_back(db.names.get_allocator()); + auto TmpParams = std::move(db.TemplateParams); + size_t k0 = db.names.size(); + const char* t1 = parse_template_arg(t, last, db); + size_t k1 = db.names.size(); + db.TemplateParams = std::move(TmpParams); + + if (t1 == t || t1 == last || k0 > k1) + return first; + db.TemplateParams.pushPack(); for (size_t k = k0; k < k1; ++k) - db.template_param.back().back().push_back(db.names[k]); + db.TemplateParams.pushSubIntoPack(db.names[k]); + t = t1; + } + else + { + size_t k0 = db.names.size(); + const char* t1 = parse_template_arg(t, last, db); + size_t k1 = db.names.size(); + if (t1 == t || t1 == last || k0 > k1) + return first; + t = t1; } - t = t1; } if (begin_idx > db.names.size()) return first; @@ -5218,9 +5269,7 @@ { db.names.back() = db.make( db.names.back(), name); - db.subs.push_back( - Db::sub_type(1, db.names.back(), - db.names.get_allocator())); + db.Subs.pushSub(db.names.back()); } else db.names.back() = name; @@ -5243,7 +5292,7 @@ db.make(db.names.back(), name); else db.names.back() = name; - db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator())); + db.Subs.pushSub(db.names.back()); pop_subs = true; t0 = t1; } @@ -5265,7 +5314,7 @@ db.make(db.names.back(), name); else db.names.back() = name; - db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator())); + db.Subs.pushSub(db.names.back()); pop_subs = true; t0 = t1; } @@ -5282,8 +5331,7 @@ db.names.pop_back(); db.names.back() = db.make( db.names.back(), name); - db.subs.push_back(Db::sub_type( - 1, db.names.back(), db.names.get_allocator())); + db.Subs.pushSub(db.names.back()); t0 = t1; component_ends_with_template_args = true; } @@ -5308,7 +5356,7 @@ db.make(db.names.back(), name); else db.names.back() = name; - db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator())); + db.Subs.pushSub(db.names.back()); pop_subs = true; t0 = t1; } @@ -5318,8 +5366,8 @@ } first = t0 + 1; db.cv = cv; - if (pop_subs && !db.subs.empty()) - db.subs.pop_back(); + if (pop_subs && !db.Subs.empty()) + db.Subs.popPack(); if (ends_with_template_args) *ends_with_template_args = component_ends_with_template_args; } @@ -5484,7 +5532,7 @@ { if (db.names.empty()) return first; - db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator())); + db.Subs.pushSub(db.names.back()); t0 = t1; t1 = parse_template_args(t0, last, db); if (t1 != t0) @@ -6035,21 +6083,19 @@ } size_t internal_size = buf != nullptr ? *n : 0; - arena a; - Db db(a); - db.template_param.emplace_back(a); + Db db; int internal_status = success; size_t len = std::strlen(mangled_name); demangle(mangled_name, mangled_name + len, db, internal_status); if (internal_status == success && db.fix_forward_references && - !db.template_param.empty() && !db.template_param.front().empty()) + !db.TemplateParams.empty()) { db.fix_forward_references = false; db.tag_templates = false; db.names.clear(); - db.subs.clear(); + db.Subs.clear(); demangle(mangled_name, mangled_name + len, db, internal_status); if (db.fix_forward_references) internal_status = invalid_mangled_name;