diff options
Diffstat (limited to 'libbase')
| -rw-r--r-- | libbase/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | libbase/include/core/adt/STLFunctionalExtras.h | 4 | ||||
| -rw-r--r-- | libbase/include/core/adt/SmallVector.h | 16 | ||||
| -rw-r--r-- | libbase/include/core/adt/Twine.h | 679 | ||||
| -rw-r--r-- | libbase/include/core/error/Errno.h | 4 | ||||
| -rw-r--r-- | libbase/include/core/error/ErrorHandling.h | 18 | ||||
| -rw-r--r-- | libbase/include/core/math/MathExtras.h | 6 | ||||
| -rw-r--r-- | libbase/include/core/memory/Alignment.h | 8 | ||||
| -rw-r--r-- | libbase/include/core/memory/AllocatorBase.h | 4 | ||||
| -rw-r--r-- | libbase/include/core/memory/MemAlloc.h | 4 | ||||
| -rw-r--r-- | libbase/src/core/adt/SmallVector.cpp | 234 | ||||
| -rw-r--r-- | libbase/src/core/error/Errno.cc | 4 | ||||
| -rw-r--r-- | libbase/src/core/math/MathExtras.cc | 4 | ||||
| -rw-r--r-- | libbase/src/core/memory/MemAlloc.cpp | 4 |
14 files changed, 952 insertions, 38 deletions
diff --git a/libbase/CMakeLists.txt b/libbase/CMakeLists.txt index 798c850..461c02f 100644 --- a/libbase/CMakeLists.txt +++ b/libbase/CMakeLists.txt @@ -39,6 +39,7 @@ configure_file( "${LIBBASE_BINARY_INCLUDE_DIR}/core/config/libbase-config.h") add_library(RCCCore + src/core/adt/SmallVector.cpp src/core/math/MathExtras.cc src/core/memory/MemAlloc.cpp src/core/error/Errno.cc diff --git a/libbase/include/core/adt/STLFunctionalExtras.h b/libbase/include/core/adt/STLFunctionalExtras.h index 231dc5b..8c88905 100644 --- a/libbase/include/core/adt/STLFunctionalExtras.h +++ b/libbase/include/core/adt/STLFunctionalExtras.h @@ -43,7 +43,7 @@ #include <type_traits> #include <utility> -namespace rcc +namespace libbase { //===----------------------------------------------------------------------===// @@ -107,6 +107,6 @@ public: } }; -} // end namespace rcc +} // end namespace libbase #endif // LIBBASE_ADT_STLFUNCTIONALEXTRAS_H diff --git a/libbase/include/core/adt/SmallVector.h b/libbase/include/core/adt/SmallVector.h index 52cb6ca..f8de25e 100644 --- a/libbase/include/core/adt/SmallVector.h +++ b/libbase/include/core/adt/SmallVector.h @@ -52,7 +52,7 @@ #include <type_traits> #include <utility> -namespace rcc +namespace libbase { template <typename T> class ArrayRef; @@ -1879,20 +1879,20 @@ to_vector_of (R &&Range) } // Explicit instantiations -extern template class rcc::SmallVectorBase<uint32_t>; +extern template class libbase::SmallVectorBase<uint32_t>; #if SIZE_MAX > UINT32_MAX -extern template class rcc::SmallVectorBase<uint64_t>; +extern template class libbase::SmallVectorBase<uint64_t>; #endif -} // end namespace rcc +} // end namespace libbase namespace std { -template <typename T, unsigned N> struct hash<rcc::SmallVector<T, N>> +template <typename T, unsigned N> struct hash<libbase::SmallVector<T, N>> { size_t - operator() (const rcc::SmallVector<T, N> &Value) const + operator() (const libbase::SmallVector<T, N> &Value) const { size_t Seed = 0; for (const T &Element : Value) @@ -1908,7 +1908,7 @@ template <typename T, unsigned N> struct hash<rcc::SmallVector<T, N>> /// Implement std::swap in terms of SmallVector swap. template <typename T> inline void -swap (rcc::SmallVectorImpl<T> &LHS, rcc::SmallVectorImpl<T> &RHS) +swap (libbase::SmallVectorImpl<T> &LHS, libbase::SmallVectorImpl<T> &RHS) { LHS.swap (RHS); } @@ -1916,7 +1916,7 @@ swap (rcc::SmallVectorImpl<T> &LHS, rcc::SmallVectorImpl<T> &RHS) /// Implement std::swap in terms of SmallVector swap. template <typename T, unsigned N> inline void -swap (rcc::SmallVector<T, N> &LHS, rcc::SmallVector<T, N> &RHS) +swap (libbase::SmallVector<T, N> &LHS, libbase::SmallVector<T, N> &RHS) { LHS.swap (RHS); } diff --git a/libbase/include/core/adt/Twine.h b/libbase/include/core/adt/Twine.h new file mode 100644 index 0000000..66d8264 --- /dev/null +++ b/libbase/include/core/adt/Twine.h @@ -0,0 +1,679 @@ +/* + RCC-Project + + Copyright (C) 2026 Richard Qin + + This file is part of RCC-Project. + + RCC-Project is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your option) any + later version. + + RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A + PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + RCC-Project; see the file COPYING. If not see + <http://www.gnu.org/licenses/>. + */ + +//===- core/adt/Twine.h - Fast Temporary String Concatenation -*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LIBBASE_ADT_TWINE_H +#define LIBBASE_ADT_TWINE_H + +#include "core/adt/SmallVector.h" +#include "core/compiler/Compiler.h" +#include "core/error/ErrorHandling.h" +#include <cassert> +#include <cstddef> +#include <cstdint> +#include <string> +#include <string_view> + +namespace libbase +{ + +class formatv_object_base; +class raw_ostream; + +/// Twine - A lightweight data structure for efficiently representing the +/// concatenation of temporary values as strings. +/// +/// A Twine is a kind of rope, it represents a concatenated string using a +/// binary-tree, where the string is the preorder of the nodes. Since the +/// Twine can be efficiently rendered into a buffer when its result is used, +/// it avoids the cost of generating temporary values for intermediate string +/// results -- particularly in cases when the Twine result is never +/// required. By explicitly tracking the type of leaf nodes, we can also avoid +/// the creation of temporary strings for conversions operations (such as +/// appending an integer to a string). +/// +/// A Twine is not intended for use directly and should not be stored, its +/// implementation relies on the ability to store pointers to temporary stack +/// objects which may be deallocated at the end of a statement. Twines should +/// only be used as const references in arguments, when an API wishes +/// to accept possibly-concatenated strings. +/// +/// Twines support a special 'null' value, which always concatenates to form +/// itself, and renders as an empty string. This can be returned from APIs to +/// effectively nullify any concatenations performed on the result. +/// +/// \b Implementation +/// +/// Given the nature of a Twine, it is not possible for the Twine's +/// concatenation method to construct interior nodes; the result must be +/// represented inside the returned value. For this reason a Twine object +/// actually holds two values, the left- and right-hand sides of a +/// concatenation. We also have nullary Twine objects, which are effectively +/// sentinel values that represent empty strings. +/// +/// Thus, a Twine can effectively have zero, one, or two children. The \see +/// isNullary(), \see isUnary(), and \see isBinary() predicates exist for +/// testing the number of children. +/// +/// We maintain a number of invariants on Twine objects (FIXME: Why): +/// - Nullary twines are always represented with their Kind on the left-hand +/// side, and the Empty kind on the right-hand side. +/// - Unary twines are always represented with the value on the left-hand +/// side, and the Empty kind on the right-hand side. +/// - If a Twine has another Twine as a child, that child should always be +/// binary (otherwise it could have been folded into the parent). +/// +/// These invariants are check by \see isValid(). +/// +/// \b Efficiency Considerations +/// +/// The Twine is designed to yield efficient and small code for common +/// situations. For this reason, the concat() method is inlined so that +/// concatenations of leaf nodes can be optimized into stores directly into a +/// single stack allocated object. +/// +/// In practice, not all compilers can be trusted to optimize concat() fully, +/// so we provide two additional methods (and accompanying operator+ +/// overloads) to guarantee that particularly important cases (cstring plus +/// string view) codegen as desired. +class Twine +{ + /// NodeKind - Represent the type of an argument. + enum NodeKind : unsigned char + { + /// An empty string; the result of concatenating anything with it is also + /// empty. + NullKind, + + /// The empty string. + EmptyKind, + + /// A pointer to a Twine instance. + TwineKind, + + /// A pointer to a C string instance. + CStringKind, + + /// A pointer to an std::string instance. + StdStringKind, + + /// A pointer and length representation. Used for std::string_view and + /// SmallVector. It stores the pointer and length directly. + PtrAndLengthKind, + + /// A pointer to a formatv_object_base instance. + FormatvObjectKind, + + /// A char value, to render as a character. + CharKind, + + /// An unsigned int value, to render as an unsigned decimal integer. + DecUIKind, + + /// An int value, to render as a signed decimal integer. + DecIKind, + + /// An unsigned long value, to render as an unsigned decimal integer. + DecULKind, + + /// A long value, to render as a signed decimal integer. + DecLKind, + + /// An unsigned long long value, to render as an unsigned decimal integer. + DecULLKind, + + /// A long long value, to render as a signed decimal integer. + DecLLKind, + + /// A uint64_t value, to render as an unsigned hexadecimal integer. + UHexKind + }; + + union Child + { + const Twine *twine; + const char *cString; + const std::string *stdString; + struct + { + const char *ptr; + size_t length; + } ptrAndLength; + const formatv_object_base *formatvObject; + char character; + unsigned int decUI; + int decI; + unsigned long decUL; + long decL; + unsigned long long decULL; + long long decLL; + uint64_t uHex; + }; + + /// LHS - The prefix in the concatenation, which may be uninitialized for + /// Null or Empty kinds. + Child LHS; + + /// RHS - The suffix in the concatenation, which may be uninitialized for + /// Null or Empty kinds. + Child RHS; + + /// LHSKind - The NodeKind of the left hand side, \see getLHSKind(). + NodeKind LHSKind = EmptyKind; + + /// RHSKind - The NodeKind of the right hand side, \see getRHSKind(). + NodeKind RHSKind = EmptyKind; + + /// Construct a nullary twine; the kind must be NullKind or EmptyKind. + explicit Twine (NodeKind Kind) : LHSKind (Kind) + { + assert (isNullary () && "Invalid kind!"); + } + + /// Construct a binary twine. + explicit Twine (const Twine &LHS, const Twine &RHS) + : LHSKind (TwineKind), RHSKind (TwineKind) + { + this->LHS.twine = &LHS; + this->RHS.twine = &RHS; + assert (isValid () && "Invalid twine!"); + } + + /// Construct a twine from explicit values. + explicit Twine (Child LHS, NodeKind LHSKind, Child RHS, NodeKind RHSKind) + : LHS (LHS), RHS (RHS), LHSKind (LHSKind), RHSKind (RHSKind) + { + assert (isValid () && "Invalid twine!"); + } + + /// Check for the null twine. + bool + isNull () const + { + return getLHSKind () == NullKind; + } + + /// Check for the empty twine. + bool + isEmpty () const + { + return getLHSKind () == EmptyKind; + } + + /// Check if this is a nullary twine (null or empty). + bool + isNullary () const + { + return isNull () || isEmpty (); + } + + /// Check if this is a unary twine. + bool + isUnary () const + { + return getRHSKind () == EmptyKind && !isNullary (); + } + + /// Check if this is a binary twine. + bool + isBinary () const + { + return getLHSKind () != NullKind && getRHSKind () != EmptyKind; + } + + /// Check if this is a valid twine (satisfying the invariants on + /// order and number of arguments). + bool + isValid () const + { + // Nullary twines always have Empty on the RHS. + if (isNullary () && getRHSKind () != EmptyKind) + { + return false; + } + + // Null should never appear on the RHS. + if (getRHSKind () == NullKind) + { + return false; + } + + // The RHS cannot be non-empty if the LHS is empty. + if (getRHSKind () != EmptyKind && getLHSKind () == EmptyKind) + { + return false; + } + + // A twine child should always be binary. + if (getLHSKind () == TwineKind && !LHS.twine->isBinary ()) + { + return false; + } + if (getRHSKind () == TwineKind && !RHS.twine->isBinary ()) + { + return false; + } + + return true; + } + + /// Get the NodeKind of the left-hand side. + NodeKind + getLHSKind () const + { + return LHSKind; + } + + /// Get the NodeKind of the right-hand side. + NodeKind + getRHSKind () const + { + return RHSKind; + } + + /// Print one child from a twine. + void + printOneChild (raw_ostream &OS, Child Ptr, NodeKind Kind) const; + + /// Print the representation of one child from a twine. + void + printOneChildRepr (raw_ostream &OS, Child Ptr, NodeKind Kind) const; + +public: + /// @name Constructors + /// @{ + + /// Construct from an empty string. + /*implicit*/ Twine () + { + assert (isValid () && "Invalid twine!"); + } + + Twine (const Twine &) = default; + + /// Construct from a C string. + /// + /// We take care here to optimize "" into the empty twine -- this will be + /// optimized out for string constants. This allows Twine arguments have + /// default "" values, without introducing unnecessary string constants. + /*implicit*/ Twine (const char *Str) + { + if (Str[0] != '\0') + { + LHS.cString = Str; + LHSKind = CStringKind; + } + else + { + LHSKind = EmptyKind; + } + + assert (isValid () && "Invalid twine!"); + } + /// Delete the implicit conversion from nullptr as Twine(const char *) + /// cannot take nullptr. + /*implicit*/ Twine (std::nullptr_t) = delete; + + /// Construct from an std::string. + /*implicit*/ Twine (const std::string &Str) : LHSKind (StdStringKind) + { + LHS.stdString = &Str; + assert (isValid () && "Invalid twine!"); + } + + /// Construct from an std::string_view by converting it to a pointer and + /// length. This handles string_views on a pure API basis, and avoids + /// storing one (or a pointer to one) inside a Twine, which avoids problems + /// when mixing code compiled under various C++ standards. + /*implicit*/ Twine (std::string_view Str) : LHSKind (PtrAndLengthKind) + { + LHS.ptrAndLength.ptr = Str.data (); + LHS.ptrAndLength.length = Str.length (); + assert (isValid () && "Invalid twine!"); + } + + /// Construct from a SmallString. + /*implicit*/ Twine (const SmallVectorImpl<char> &Str) + : LHSKind (PtrAndLengthKind) + { + LHS.ptrAndLength.ptr = Str.data (); + LHS.ptrAndLength.length = Str.size (); + assert (isValid () && "Invalid twine!"); + } + + /// Construct from a formatv_object_base. + /*implicit*/ Twine (const formatv_object_base &Fmt) + : LHSKind (FormatvObjectKind) + { + LHS.formatvObject = &Fmt; + assert (isValid () && "Invalid twine!"); + } + + /// Construct from a char. + explicit Twine (char Val) : LHSKind (CharKind) + { + LHS.character = Val; + } + + /// Construct from a signed char. + explicit Twine (signed char Val) : LHSKind (CharKind) + { + LHS.character = static_cast<char> (Val); + } + + /// Construct from an unsigned char. + explicit Twine (unsigned char Val) : LHSKind (CharKind) + { + LHS.character = static_cast<char> (Val); + } + + /// Construct a twine to print \p Val as an unsigned decimal integer. + explicit Twine (unsigned Val) : LHSKind (DecUIKind) + { + LHS.decUI = Val; + } + + /// Construct a twine to print \p Val as a signed decimal integer. + explicit Twine (int Val) : LHSKind (DecIKind) + { + LHS.decI = Val; + } + + /// Construct a twine to print \p Val as an unsigned decimal integer. + explicit Twine (unsigned long Val) : LHSKind (DecULKind) + { + LHS.decUL = Val; + } + + /// Construct a twine to print \p Val as a signed decimal integer. + explicit Twine (long Val) : LHSKind (DecLKind) + { + LHS.decL = Val; + } + + /// Construct a twine to print \p Val as an unsigned decimal integer. + explicit Twine (unsigned long long Val) : LHSKind (DecULLKind) + { + LHS.decULL = Val; + } + + /// Construct a twine to print \p Val as a signed decimal integer. + explicit Twine (long long Val) : LHSKind (DecLLKind) + { + LHS.decLL = Val; + } + + // FIXME: Unfortunately, to make sure this is as efficient as possible we + // need extra binary constructors from particular types. We can't rely on + // the compiler to be smart enough to fold operator+()/concat() down to the + // right thing. Yet. + + /// Construct as the concatenation of a C string and a string view. + /*implicit*/ Twine (const char *LHS, std::string_view RHS) + : LHSKind (CStringKind), RHSKind (PtrAndLengthKind) + { + this->LHS.cString = LHS; + this->RHS.ptrAndLength.ptr = RHS.data (); + this->RHS.ptrAndLength.length = RHS.size (); + assert (isValid () && "Invalid twine!"); + } + + /// Construct as the concatenation of a string view and a C string. + /*implicit*/ Twine (std::string_view LHS, const char *RHS) + : LHSKind (PtrAndLengthKind), RHSKind (CStringKind) + { + this->LHS.ptrAndLength.ptr = LHS.data (); + this->LHS.ptrAndLength.length = LHS.size (); + this->RHS.cString = RHS; + assert (isValid () && "Invalid twine!"); + } + + /// Since the intended use of twines is as temporary objects, assignments + /// when concatenating might cause undefined behavior or stack corruptions + Twine & + operator= (const Twine &) = delete; + + /// Create a 'null' string, which is an empty string that always + /// concatenates to form another empty string. + static Twine + createNull () + { + return Twine (NullKind); + } + + /// @} + /// @name Numeric Conversions + /// @{ + + // Construct a twine to print \p Val as an unsigned hexadecimal integer. + static Twine + utohexstr (uint64_t Val) + { + Child LHS, RHS; + LHS.uHex = Val; + RHS.twine = nullptr; + return Twine (LHS, UHexKind, RHS, EmptyKind); + } + + /// @} + /// @name Predicate Operations + /// @{ + + /// Check if this twine is trivially empty; a false return value does not + /// necessarily mean the twine is empty. + bool + isTriviallyEmpty () const + { + return isNullary (); + } + + /// Return true if this twine can be dynamically accessed as a single + /// string view with getSingleStringView(). + bool + isSingleStringView () const + { + if (getRHSKind () != EmptyKind) + { + return false; + } + + switch (getLHSKind ()) + { + case EmptyKind: + case CStringKind: + case StdStringKind: + case PtrAndLengthKind: + return true; + default: + return false; + } + } + + /// @} + /// @name String Operations + /// @{ + + Twine + concat (const Twine &Suffix) const; + + /// @} + /// @name Output & Conversion. + /// @{ + + /// Return the twine contents as a std::string. + LIBBASE_ABI std::string + str () const; + + /// Append the concatenated string into the given SmallString or SmallVector. + LIBBASE_ABI void + toVector (SmallVectorImpl<char> &Out) const; + + /// This returns the twine as a single string view. This method is only valid + /// if isSingleStringView() is true. + std::string_view + getSingleStringView () const + { + assert (isSingleStringView () && + "This cannot be had as a single string view!"); + switch (getLHSKind ()) + { + default: + libbase_unreachable ("Out of sync with isSingleStringView"); + case EmptyKind: + return std::string_view (); + case CStringKind: + return std::string_view (LHS.cString); + case StdStringKind: + return std::string_view (*LHS.stdString); + case PtrAndLengthKind: + return std::string_view (LHS.ptrAndLength.ptr, LHS.ptrAndLength.length); + } + } + + /// This returns the twine as a single string view if it can be + /// represented as such. Otherwise the twine is written into the given + /// SmallVector and a string view to the SmallVector's data is returned. + std::string_view + toStringView (SmallVectorImpl<char> &Out) const + { + if (isSingleStringView ()) + { + return getSingleStringView (); + } + toVector (Out); + return std::string_view (Out.data (), Out.size ()); + } + + /// This returns the twine as a single null terminated string view if it + /// can be represented as such. Otherwise the twine is written into the + /// given SmallVector and a string view to the SmallVector's data is returned. + /// + /// The returned string view's size does not include the null terminator. + LIBBASE_ABI std::string_view + toNullTerminatedStringView (SmallVectorImpl<char> &Out) const; + + /// Write the concatenated string represented by this twine to the + /// stream \p OS. + LIBBASE_ABI void + print (raw_ostream &OS) const; + + /// Write the representation of this twine to the stream \p OS. + LIBBASE_ABI void + printRepr (raw_ostream &OS) const; + +#if !defined(NDEBUG) || defined(LIBBASE_ENABLE_DUMP) + /// Dump the concatenated string represented by this twine to stderr. + LIBBASE_DUMP_METHOD void + dump () const; + + /// Dump the representation of this twine to stderr. + LIBBASE_DUMP_METHOD void + dumpRepr () const; +#endif + + /// @} +}; + +/// @name Twine Inline Implementations +/// @{ + +inline Twine +Twine::concat (const Twine &Suffix) const +{ + // Concatenation with null is null. + if (isNull () || Suffix.isNull ()) + { + return Twine (NullKind); + } + + // Concatenation with empty yields the other side. + if (isEmpty ()) + { + return Suffix; + } + if (Suffix.isEmpty ()) + { + return *this; + } + + // Otherwise we need to create a new node, taking care to fold in unary + // twines. + Child NewLHS, NewRHS; + NewLHS.twine = this; + NewRHS.twine = &Suffix; + NodeKind NewLHSKind = TwineKind, NewRHSKind = TwineKind; + if (isUnary ()) + { + NewLHS = LHS; + NewLHSKind = getLHSKind (); + } + if (Suffix.isUnary ()) + { + NewRHS = Suffix.LHS; + NewRHSKind = Suffix.getLHSKind (); + } + + return Twine (NewLHS, NewLHSKind, NewRHS, NewRHSKind); +} + +inline Twine +operator+ (const Twine &LHS, const Twine &RHS) +{ + return LHS.concat (RHS); +} + +/// Additional overload to guarantee simplified codegen; this is equivalent to +/// concat(). + +inline Twine +operator+ (const char *LHS, std::string_view RHS) +{ + return Twine (LHS, RHS); +} + +/// Additional overload to guarantee simplified codegen; this is equivalent to +/// concat(). + +inline Twine +operator+ (std::string_view LHS, const char *RHS) +{ + return Twine (LHS, RHS); +} + +inline raw_ostream & +operator<< (raw_ostream &OS, const Twine &RHS) +{ + RHS.print (OS); + return OS; +} + +/// @} + +} // end namespace libbase + +#endif // LIBBASE_ADT_TWINE_H diff --git a/libbase/include/core/error/Errno.h b/libbase/include/core/error/Errno.h index 01d4ff8..9f0c3b9 100644 --- a/libbase/include/core/error/Errno.h +++ b/libbase/include/core/error/Errno.h @@ -29,7 +29,7 @@ #include <cerrno> #include <string> -namespace rcc +namespace libbase { namespace sys { @@ -59,6 +59,6 @@ RetryAfterSignal (const FailT &Fail, const Fun &F, const Args &...As) } } // namespace sys -} // namespace rcc +} // namespace libbase #endif // LIBBASE_SUPPORT_ERRNO_H diff --git a/libbase/include/core/error/ErrorHandling.h b/libbase/include/core/error/ErrorHandling.h index b27104c..485d2d1 100644 --- a/libbase/include/core/error/ErrorHandling.h +++ b/libbase/include/core/error/ErrorHandling.h @@ -37,7 +37,7 @@ #include "core/compiler/Compiler.h" -namespace rcc +namespace libbase { class StringRef; class Twine; @@ -177,9 +177,9 @@ report_bad_alloc_error (const char *Reason, bool GenCrashDiag = true); /// Use the llvm_unreachable macro (that adds location info), instead of /// calling this function directly. [[noreturn]] LIBBASE_ABI void -rcc_unreachable_internal (const char *msg = nullptr, const char *file = nullptr, - unsigned line = 0); -} // namespace rcc +libbase_unreachable_internal (const char *msg = nullptr, + const char *file = nullptr, unsigned line = 0); +} // namespace libbase /// Marks that the current location is not supposed to be reachable. /// In !NDEBUG builds, prints the message and location info to stderr. @@ -199,14 +199,14 @@ rcc_unreachable_internal (const char *msg = nullptr, const char *file = nullptr, /// diagnostics for unreachable code paths, and allows compilers to omit /// unnecessary code. #ifndef NDEBUG -#define rcc_unreachable(msg) \ - ::rcc::rcc_unreachable_internal (msg, __FILE__, __LINE__) +#define libbase_unreachable(msg) \ + ::libbase::libbase_unreachable_internal (msg, __FILE__, __LINE__) #elif !defined(LIBBASE_BUILTIN_UNREACHABLE) -#define rcc_unreachable(msg) ::rcc::rcc_unreachable_internal () +#define libbase_unreachable(msg) ::libbase::libbase_unreachable_internal () #elif LIBBASE_UNREACHABLE_OPTIMIZE -#define rcc_unreachable(msg) LIBBASE_BUILTIN_UNREACHABLE +#define libbase_unreachable(msg) LIBBASE_BUILTIN_UNREACHABLE #else -#define rcc_unreachable(msg) \ +#define libbase_unreachable(msg) \ do \ { \ LIBBASE_BUILTIN_TRAP; \ diff --git a/libbase/include/core/math/MathExtras.h b/libbase/include/core/math/MathExtras.h index 880ba74..732f82c 100644 --- a/libbase/include/core/math/MathExtras.h +++ b/libbase/include/core/math/MathExtras.h @@ -45,7 +45,7 @@ #include <type_traits> #include <utility> -namespace rcc +namespace libbase { /// Some template parameter helpers to optimize for bitwidth, for functions that /// take multiple arguments. @@ -432,7 +432,7 @@ template <size_t kValue> constexpr size_t ConstantLog2 () { - static_assert (rcc::isPowerOf2_64 (kValue), + static_assert (libbase::isPowerOf2_64 (kValue), "Value is not a valid power of 2"); return std::countr_zero (kValue); } @@ -1045,6 +1045,6 @@ using stack_float_t = float; LIBBASE_ABI int NumDigitsBase10 (uint64_t X); -} // namespace rcc +} // namespace libbase #endif diff --git a/libbase/include/core/memory/Alignment.h b/libbase/include/core/memory/Alignment.h index 22299e1..4078cd6 100644 --- a/libbase/include/core/memory/Alignment.h +++ b/libbase/include/core/memory/Alignment.h @@ -49,7 +49,7 @@ #include <string> #endif // NDEBUG -namespace rcc { +namespace libbase { #define ALIGN_CHECK_ISPOSITIVE(decl) \ assert(decl > 0 && (#decl " should be defined")) @@ -85,7 +85,7 @@ public: explicit Align(uint64_t Value) { assert(Value > 0 && "Value must not be 0"); - assert(rcc::isPowerOf2_64(Value) && "Alignment is not a power of 2"); + assert(libbase::isPowerOf2_64(Value) && "Alignment is not a power of 2"); ShiftValue = Log2_64(Value); assert(ShiftValue < 64 && "Broken invariant"); } @@ -146,7 +146,7 @@ public: constexpr MaybeAlign(std::nullopt_t None) : UP(None) {} constexpr MaybeAlign(Align Value) : UP(Value) {} explicit MaybeAlign(uint64_t Value) { - assert((Value == 0 || rcc::isPowerOf2_64(Value)) && + assert((Value == 0 || libbase::isPowerOf2_64(Value)) && "Alignment is neither 0 nor a power of 2"); if (Value) emplace(Value); @@ -337,6 +337,6 @@ inline std::string DebugStr(const MaybeAlign &MA) { #undef ALIGN_CHECK_ISPOSITIVE -} // namespace rcc +} // namespace libbase #endif // LIBBASE_SUPPORT_ALIGNMENT_H_ diff --git a/libbase/include/core/memory/AllocatorBase.h b/libbase/include/core/memory/AllocatorBase.h index 77cb84b..0f7f9f1 100644 --- a/libbase/include/core/memory/AllocatorBase.h +++ b/libbase/include/core/memory/AllocatorBase.h @@ -51,7 +51,7 @@ #include <type_traits> #include <utility> -namespace rcc { +namespace libbase { /// CRTP base class providing obvious overloads for the core \c /// Allocate() methods of LLVM-style allocators. @@ -149,6 +149,6 @@ public: } // namespace detail -} // namespace rcc +} // namespace libbase #endif // LIBBASE_SUPPORT_ALLOCATORBASE_H diff --git a/libbase/include/core/memory/MemAlloc.h b/libbase/include/core/memory/MemAlloc.h index bd98864..7b00ceb 100644 --- a/libbase/include/core/memory/MemAlloc.h +++ b/libbase/include/core/memory/MemAlloc.h @@ -41,7 +41,7 @@ #include "core/error/ErrorHandling.h" #include <cstdlib> -namespace rcc +namespace libbase { LIBBASE_ATTRIBUTE_RETURNS_NONNULL inline void * @@ -120,5 +120,5 @@ allocate_buffer (size_t Size, size_t Alignment); LIBBASE_ABI void deallocate_buffer (void *Ptr, size_t Size, size_t Alignment); -} // namespace rcc +} // namespace libbase #endif diff --git a/libbase/src/core/adt/SmallVector.cpp b/libbase/src/core/adt/SmallVector.cpp new file mode 100644 index 0000000..c28680c --- /dev/null +++ b/libbase/src/core/adt/SmallVector.cpp @@ -0,0 +1,234 @@ +/* + RCC-Project + + Copyright (C) 2026 Richard Qin + + This file is part of RCC-Project. + + RCC-Project is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your option) any + later version. + + RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR + A PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + RCC-Project; see the file COPYING. If not see + <http://www.gnu.org/licenses/>. +*/ + +//===- core/adt/SmallVector.cpp - 'Normally small' vectors ----------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file implements the SmallVector class. +// +//===----------------------------------------------------------------------===// + +#include "core/adt/SmallVector.h" +#include "core/adt/Twine.h" +#include "core/memory/MemAlloc.h" +#include <cstdint> +#if LIBBASE_ENABLE_EXCEPTIONS +#include <stdexcept> +#endif +using namespace libbase; + +// Check that no bytes are wasted and everything is well-aligned. +namespace +{ +// These structures may cause binary compat warnings on AIX. Suppress the +// warning since we are only using these types for the static assertions below. +#if defined(_AIX) +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Waix-compat" +#endif +struct Struct16B +{ + alignas (16) void *X; +}; +struct Struct32B +{ + alignas (32) void *X; +}; +#if defined(_AIX) +#pragma GCC diagnostic pop +#endif +} // namespace +static_assert (sizeof (SmallVector<void *, 0>) == + sizeof (unsigned) * 2 + sizeof (void *), + "wasted space in SmallVector size 0"); +static_assert (alignof (SmallVector<Struct16B, 0>) >= alignof (Struct16B), + "wrong alignment for 16-byte aligned T"); +static_assert (alignof (SmallVector<Struct32B, 0>) >= alignof (Struct32B), + "wrong alignment for 32-byte aligned T"); +static_assert (sizeof (SmallVector<Struct16B, 0>) >= alignof (Struct16B), + "missing padding for 16-byte aligned T"); +static_assert (sizeof (SmallVector<Struct32B, 0>) >= alignof (Struct32B), + "missing padding for 32-byte aligned T"); +static_assert (sizeof (SmallVector<void *, 1>) == + sizeof (unsigned) * 2 + sizeof (void *) * 2, + "wasted space in SmallVector size 1"); + +static_assert (sizeof (SmallVector<char, 0>) == + sizeof (void *) * 2 + sizeof (void *), + "1 byte elements have word-sized type for size and capacity"); + +/// Report that MinSize doesn't fit into this vector's size type. Throws +/// std::length_error or calls report_fatal_error. +[[noreturn]] static void +report_size_overflow (size_t MinSize, size_t MaxSize); +static void +report_size_overflow (size_t MinSize, size_t MaxSize) +{ + std::string Reason = "SmallVector unable to grow. Requested capacity (" + + std::to_string (MinSize) + + ") is larger than maximum value for size type (" + + std::to_string (MaxSize) + ")"; +#if LIBBASE_ENABLE_EXCEPTIONS + throw std::length_error (Reason); +#else + report_fatal_error (Twine (Reason)); +#endif +} + +/// Report that this vector is already at maximum capacity. Throws +/// std::length_error or calls report_fatal_error. +[[noreturn]] static void +report_at_maximum_capacity (size_t MaxSize); +static void +report_at_maximum_capacity (size_t MaxSize) +{ + std::string Reason = + "SmallVector capacity unable to grow. Already at maximum size " + + std::to_string (MaxSize); +#ifdef LIBBASE_ENABLE_EXCEPTIONS + throw std::length_error (Reason); +#else + report_fatal_error (Twine (Reason)); +#endif +} + +// Note: Moving this function into the header may cause performance regression. +template <class Size_T> +static size_t +getNewCapacity (size_t MinSize, size_t TSize, size_t OldCapacity) +{ + constexpr size_t MaxSize = std::numeric_limits<Size_T>::max (); + + // Ensure we can fit the new capacity. + // This is only going to be applicable when the capacity is 32 bit. + if (MinSize > MaxSize) + { + report_size_overflow (MinSize, MaxSize); + } + + // Ensure we can meet the guarantee of space for at least one more element. + // The above check alone will not catch the case where grow is called with a + // default MinSize of 0, but the current capacity cannot be increased. + // This is only going to be applicable when the capacity is 32 bit. + if (OldCapacity == MaxSize) + { + report_at_maximum_capacity (MaxSize); + } + + // In theory 2*capacity can overflow if the capacity is 64 bit, but the + // original capacity would never be large enough for this to be a problem. + size_t NewCapacity = 2 * OldCapacity + 1; // Always grow. + return std::clamp (NewCapacity, MinSize, MaxSize); +} + +/// If vector was first created with capacity 0, getFirstEl() points to the +/// memory right after, an area unallocated. If a subsequent allocation, +/// that grows the vector, happens to return the same pointer as getFirstEl(), +/// get a new allocation, otherwise isSmall() will falsely return that no +/// allocation was done (true) and the memory will not be freed in the +/// destructor. If a VSize is given (vector size), also copy that many +/// elements to the new allocation - used if realloca fails to increase +/// space, and happens to allocate precisely at BeginX. +/// This is unlikely to be called often, but resolves a memory leak when the +/// situation does occur. +static void * +replaceAllocation (void *NewElts, size_t TSize, size_t NewCapacity, + size_t VSize = 0) +{ + void *NewEltsReplace = libbase::safe_malloc (NewCapacity * TSize); + if (VSize) + { + memcpy (NewEltsReplace, NewElts, VSize * TSize); + } + free (NewElts); + return NewEltsReplace; +} + +// Note: Moving this function into the header may cause performance regression. +template <class Size_T> +void * +SmallVectorBase<Size_T>::mallocForGrow (void *FirstEl, size_t MinSize, + size_t TSize, size_t &NewCapacity) +{ + NewCapacity = getNewCapacity<Size_T> (MinSize, TSize, this->capacity ()); + // Even if capacity is not 0 now, if the vector was originally created with + // capacity 0, it's possible for the malloc to return FirstEl. + void *NewElts = libbase::safe_malloc (NewCapacity * TSize); + if (NewElts == FirstEl) + { + NewElts = replaceAllocation (NewElts, TSize, NewCapacity); + } + return NewElts; +} + +// Note: Moving this function into the header may cause performance regression. +template <class Size_T> +void +SmallVectorBase<Size_T>::grow_pod (void *FirstEl, size_t MinSize, size_t TSize) +{ + size_t NewCapacity = + getNewCapacity<Size_T> (MinSize, TSize, this->capacity ()); + void *NewElts; + if (BeginX == FirstEl) + { + NewElts = libbase::safe_malloc (NewCapacity * TSize); + if (NewElts == FirstEl) + { + NewElts = replaceAllocation (NewElts, TSize, NewCapacity); + } + + // Copy the elements over. No need to run dtors on PODs. + memcpy (NewElts, this->BeginX, size () * TSize); + } + else + { + // If this wasn't grown from the inline copy, grow the allocated space. + NewElts = libbase::safe_realloc (this->BeginX, NewCapacity * TSize); + if (NewElts == FirstEl) + { + NewElts = replaceAllocation (NewElts, TSize, NewCapacity, size ()); + } + } + + this->set_allocation_range (NewElts, NewCapacity); +} + +template class libbase::SmallVectorBase<uint32_t>; + +// Disable the uint64_t instantiation for 32-bit builds. +// Both uint32_t and uint64_t instantiations are needed for 64-bit builds. +// This instantiation will never be used in 32-bit builds, and will cause +// warnings when sizeof(Size_T) > sizeof(size_t). +#if SIZE_MAX > UINT32_MAX +template class libbase::SmallVectorBase<uint64_t>; + +// Assertions to ensure this #if stays in sync with SmallVectorSizeType. +static_assert (sizeof (SmallVectorSizeType<char>) == sizeof (uint64_t), + "Expected SmallVectorBase<uint64_t> variant to be in use."); +#else +static_assert (sizeof (SmallVectorSizeType<char>) == sizeof (uint32_t), + "Expected SmallVectorBase<uint32_t> variant to be in use."); +#endif diff --git a/libbase/src/core/error/Errno.cc b/libbase/src/core/error/Errno.cc index 3c85930..c861e46 100644 --- a/libbase/src/core/error/Errno.cc +++ b/libbase/src/core/error/Errno.cc @@ -27,7 +27,7 @@ #include <cstring> #include <errno.h> -namespace rcc +namespace libbase { namespace sys { @@ -76,4 +76,4 @@ StrError (int errnum) } } // namespace sys -} // namespace rcc +} // namespace libbase diff --git a/libbase/src/core/math/MathExtras.cc b/libbase/src/core/math/MathExtras.cc index 8d1798f..e691a3c 100644 --- a/libbase/src/core/math/MathExtras.cc +++ b/libbase/src/core/math/MathExtras.cc @@ -39,7 +39,7 @@ #include <cmath> #endif -namespace rcc +namespace libbase { #if defined(_MSC_VER) @@ -94,4 +94,4 @@ NumDigitsBase10 (uint64_t X) return Digits + (X >= Data.Boundaries[Digits]); } -} // namespace rcc +} // namespace libbase diff --git a/libbase/src/core/memory/MemAlloc.cpp b/libbase/src/core/memory/MemAlloc.cpp index b418d40..38e3bfd 100644 --- a/libbase/src/core/memory/MemAlloc.cpp +++ b/libbase/src/core/memory/MemAlloc.cpp @@ -33,7 +33,7 @@ // These are out of line to have __cpp_aligned_new not affect ABI. LIBBASE_ATTRIBUTE_RETURNS_NONNULL LIBBASE_ATTRIBUTE_RETURNS_NOALIAS void * -rcc::allocate_buffer (size_t Size, size_t Alignment) +libbase::allocate_buffer (size_t Size, size_t Alignment) { void *Result = ::operator new (Size, #ifdef __cpp_aligned_new @@ -48,7 +48,7 @@ rcc::allocate_buffer (size_t Size, size_t Alignment) } void -rcc::deallocate_buffer (void *Ptr, size_t Size, size_t Alignment) +libbase::deallocate_buffer (void *Ptr, size_t Size, size_t Alignment) { ::operator delete (Ptr #ifdef __cpp_sized_deallocation |