kakoune

Fork of kakoune, an acceptable text editor
git clone git://git.laack.co/kakoune.git
Log | Files | Refs

string.hh (12527B)


      1 #ifndef string_hh_INCLUDED
      2 #define string_hh_INCLUDED
      3 
      4 #include "memory.hh"
      5 #include "hash.hh"
      6 #include "units.hh"
      7 #include "utf8.hh"
      8 
      9 #include <climits>
     10 #include <cstddef>
     11 #include <cstring>
     12 
     13 namespace Kakoune
     14 {
     15 
     16 class StringView;
     17 
     18 template<typename Type, typename CharType>
     19 class StringOps
     20 {
     21 public:
     22     using value_type = CharType;
     23 
     24     friend constexpr size_t hash_value(const Type& str)
     25     {
     26         return fnv1a(str.data(), (int)str.length());
     27     }
     28 
     29     using iterator = CharType*;
     30     using const_iterator = const CharType*;
     31     using reverse_iterator = std::reverse_iterator<iterator>;
     32     using const_reverse_iterator = std::reverse_iterator<const_iterator>;
     33 
     34     [[gnu::always_inline]]
     35     iterator begin() { return type().data(); }
     36 
     37     [[gnu::always_inline]]
     38     const_iterator begin() const { return type().data(); }
     39 
     40     [[gnu::always_inline]]
     41     iterator end() { return type().data() + type().length(); }
     42 
     43     [[gnu::always_inline]]
     44     const_iterator end() const { return type().data() + type().length(); }
     45 
     46     reverse_iterator rbegin() { return reverse_iterator{end()}; }
     47     const_reverse_iterator rbegin() const { return const_reverse_iterator{end()}; }
     48 
     49     reverse_iterator rend() { return reverse_iterator{begin()}; }
     50     const_reverse_iterator rend() const { return const_reverse_iterator{begin()}; }
     51 
     52     CharType& front() { return *type().data(); }
     53     const CharType& front() const { return *type().data(); }
     54     CharType& back() { return type().data()[(int)type().length() - 1]; }
     55     const CharType& back() const { return type().data()[(int)type().length() - 1]; }
     56 
     57     [[gnu::always_inline]]
     58     CharType& operator[](ByteCount pos) { return type().data()[(int)pos]; }
     59 
     60     [[gnu::always_inline]]
     61     const CharType& operator[](ByteCount pos) const { return type().data()[(int)pos]; }
     62 
     63     Codepoint operator[](CharCount pos) const
     64     { return utf8::codepoint(utf8::advance(begin(), end(), pos), end()); }
     65 
     66     CharCount char_length() const { return utf8::distance(begin(), end()); }
     67     ColumnCount column_length() const { return utf8::column_distance(begin(), end()); }
     68 
     69     [[gnu::always_inline]]
     70     bool empty() const { return type().length() == 0_byte; }
     71 
     72     bool starts_with(StringView str) const;
     73     bool ends_with(StringView str) const;
     74 
     75     ByteCount byte_count_to(CharCount count) const
     76     { return utf8::advance(begin(), end(), count) - begin(); }
     77 
     78     ByteCount byte_count_to(ColumnCount count) const
     79     { return utf8::advance(begin(), end(), count) - begin(); }
     80 
     81     CharCount char_count_to(ByteCount count) const
     82     { return utf8::distance(begin(), begin() + count); }
     83 
     84     ColumnCount column_count_to(ByteCount count) const
     85     { return utf8::column_distance(begin(), begin() + count); }
     86 
     87     StringView substr(ByteCount from, ByteCount length = -1) const;
     88     StringView substr(CharCount from, CharCount length = -1) const;
     89     StringView substr(ColumnCount from, ColumnCount length = -1) const;
     90 
     91 private:
     92     [[gnu::always_inline]]
     93     Type& type() { return *static_cast<Type*>(this); }
     94     [[gnu::always_inline]]
     95     const Type& type() const { return *static_cast<const Type*>(this); }
     96 };
     97 
     98 constexpr ByteCount strlen(const char* s)
     99 {
    100     int i = 0;
    101     while (*s++ != 0)
    102         ++i;
    103     return {i};
    104 }
    105 
    106 class String : public StringOps<String, char>
    107 {
    108 public:
    109     String() {}
    110     String(const char* content) : m_data(content, (size_t)strlen(content)) {}
    111     String(const char* content, ByteCount len) : m_data(content, (size_t)len) {}
    112     String(const char* begin, const char* end) : m_data(begin, end-begin) {}
    113     explicit String(Codepoint cp, CharCount count = 1);
    114     explicit String(Codepoint cp, ColumnCount count);
    115     explicit String(StringView str);
    116 
    117     struct NoCopy{};
    118     String(NoCopy, StringView str);
    119 
    120     static String no_copy(StringView str);
    121 
    122     [[gnu::always_inline]]
    123     char* data() { return m_data.data(); }
    124 
    125     [[gnu::always_inline]]
    126     const char* data() const { return m_data.data(); }
    127 
    128     [[gnu::always_inline]]
    129     ByteCount length() const { return m_data.size(); }
    130 
    131     [[gnu::always_inline]]
    132     const char* c_str() const { return m_data.data(); }
    133 
    134     [[gnu::always_inline]]
    135     void append(const char* data, ByteCount count) { m_data.append(data, (size_t)count); }
    136 
    137     void clear() { m_data.clear(); }
    138 
    139     void push_back(char c) { m_data.append(&c, 1); }
    140     void force_size(ByteCount size) { m_data.force_size((size_t)size); }
    141     void reserve(ByteCount size) { m_data.reserve((size_t)size); }
    142     void resize(ByteCount size, char c);
    143 
    144     static const String ms_empty;
    145     static constexpr const char* option_type_name = "str";
    146 
    147     // String data storage using small string optimization.
    148     //
    149     // The MSB of the last byte is used to flag if we are using the allocated buffer
    150     // (1) or in-situ storage, the small one (0). That means the allocated capacity
    151     // cannot use its most significant byte, so we effectively limit capacity to
    152     // 2^24 on 32bit arch, and 2^56 on 64bit.
    153     //
    154     // There is also a special NoCopy mode in which the data referred to is un-owned.
    155     // It is indicated by being in Long mode with capacity == 0.
    156     struct Data
    157     {
    158         using Alloc = Allocator<char, MemoryDomain::String>;
    159 
    160         Data() { set_empty(); }
    161         Data(NoCopy, const char* data, size_t size) : u{Long{const_cast<char*>(data),
    162                                                              size,
    163                                                              /*capacity=*/0,
    164                                                              /*mode=*/Long::active_mask}} {}
    165 
    166         Data(const char* data, size_t size, size_t capacity);
    167         Data(const char* data, size_t size) : Data(data, size, size) {}
    168         Data(const Data& other) : Data{other.data(), other.size()} {}
    169 
    170         ~Data() { release(); }
    171         Data(Data&& other) noexcept : u{other.u} { other.set_empty(); }
    172         Data& operator=(const Data& other);
    173         Data& operator=(Data&& other) noexcept;
    174 
    175         bool is_long() const { return (u.l.mode & Long::active_mask) != 0; }
    176         size_t size() const { return is_long() ? u.l.size : (Short::capacity - u.s.remaining_size); }
    177         size_t capacity() const { return is_long() ? u.l.capacity : Short::capacity; }
    178 
    179         const char* data() const { return is_long() ? u.l.ptr : u.s.string; }
    180         char* data() { return is_long() ? u.l.ptr : u.s.string; }
    181 
    182         template<bool copy = true>
    183         void reserve(size_t new_capacity);
    184         void set_size(size_t size);
    185         void force_size(size_t new_size);
    186         void append(const char* str, size_t len);
    187         void clear();
    188 
    189     private:
    190         struct Long
    191         {
    192             static constexpr size_t capacity_bits = CHAR_BIT * (sizeof(size_t) - 1);
    193             static constexpr size_t max_capacity = ((size_t)1 << capacity_bits) - 1;
    194 
    195             char* ptr;
    196             size_t size;
    197             size_t capacity : capacity_bits;
    198             unsigned char mode;
    199             static constexpr unsigned char active_mask = 0b1000'0000;
    200         };
    201         static_assert(sizeof(Long) == sizeof(char*) * 3);
    202 
    203         struct Short
    204         {
    205             static constexpr size_t capacity = sizeof(Long) - 1;
    206             char string[capacity];
    207             // When string is full remaining_size will be 0 and be the null terminator.
    208             // When string is empty remaining size will be 23 (0b00010111)
    209             // and not collide with Long::active_mask.
    210             unsigned char remaining_size;
    211         };
    212         static_assert(offsetof(Long, mode) == offsetof(Short, remaining_size));
    213 
    214         union
    215         {
    216             Long l;
    217             Short s;
    218         } u;
    219 
    220         void release()
    221         {
    222             if (is_long() and (u.l.capacity != 0))
    223                 Alloc{}.deallocate(u.l.ptr, u.l.capacity+1);
    224         }
    225 
    226         void set_empty() { u.s.remaining_size = Short::capacity; u.s.string[0] = '\0'; }
    227         void set_short(const char* data, size_t size);
    228     };
    229 
    230 private:
    231     Data m_data;
    232 };
    233 
    234 class StringView : public StringOps<StringView, const char>
    235 {
    236 public:
    237     StringView() = default;
    238     constexpr StringView(const char* data, ByteCount length)
    239         : m_data{data}, m_length{length} {}
    240     constexpr StringView(const char* data) : m_data{data}, m_length{data ? strlen(data) : 0} {}
    241     constexpr StringView(const char* begin, const char* end) : m_data{begin}, m_length{(int)(end - begin)} {}
    242     StringView(const String& str) : m_data{str.data()}, m_length{(int)str.length()} {}
    243     StringView(const char& c) : m_data(&c), m_length(1) {}
    244     StringView(int c) = delete;
    245     StringView(Codepoint c) = delete;
    246 
    247     [[gnu::always_inline]]
    248     constexpr const char* data() const { return m_data; }
    249 
    250     [[gnu::always_inline]]
    251     constexpr ByteCount length() const { return m_length; }
    252 
    253     String str() const { return {m_data, m_length}; }
    254 
    255     struct ZeroTerminatedString
    256     {
    257         ZeroTerminatedString(const char* begin, const char* end)
    258         {
    259             if (*end == '\0')
    260                 unowned = begin;
    261             else
    262                 owned = String::Data(begin, end - begin);
    263         }
    264         operator const char*() const { return unowned ? unowned : owned.data(); }
    265 
    266     private:
    267         String::Data owned;
    268         const char* unowned = nullptr;
    269     };
    270     ZeroTerminatedString zstr() const { return {begin(), end()}; }
    271 
    272 private:
    273     const char* m_data;
    274     ByteCount m_length;
    275 };
    276 
    277 static_assert(std::is_trivial<StringView>::value, "");
    278 
    279 template<> struct HashCompatible<String, StringView> : std::true_type {};
    280 template<> struct HashCompatible<StringView, String> : std::true_type {};
    281 
    282 inline String::String(StringView str) : String{str.begin(), str.length()} {}
    283 inline String::String(NoCopy, StringView str) : m_data{NoCopy{}, str.begin(), (size_t)str.length()} {}
    284 inline String String::no_copy(StringView str) { return {NoCopy{}, str}; }
    285 
    286 template<typename Type, typename CharType>
    287 inline StringView StringOps<Type, CharType>::substr(ByteCount from, ByteCount length) const
    288 {
    289     const auto str_length = type().length();
    290     const auto max_length = str_length - from;
    291     kak_assert(from >= 0 and max_length >= 0);
    292     return StringView{type().data() + (int)from, length >= 0 and length < max_length ? length : max_length};
    293 }
    294 
    295 template<typename Type, typename CharType>
    296 inline StringView StringOps<Type, CharType>::substr(CharCount from, CharCount length) const
    297 {
    298     auto beg = utf8::advance(begin(), end(), from);
    299     return StringView{beg, length >= 0 ? utf8::advance(beg, end(), length) : end()};
    300 }
    301 
    302 template<typename Type, typename CharType>
    303 inline StringView StringOps<Type, CharType>::substr(ColumnCount from, ColumnCount length) const
    304 {
    305     auto beg = utf8::advance(begin(), end(), from);
    306     return StringView{beg, (length >= 0) ? utf8::advance(beg, end(), length) : end()};
    307 }
    308 
    309 template<typename Type, typename CharType>
    310 inline bool StringOps<Type, CharType>::starts_with(StringView str) const
    311 {
    312     if (type().length() < str.length())
    313         return false;
    314     return substr(0, str.length()) == str;
    315 }
    316 
    317 template<typename Type, typename CharType>
    318 inline bool StringOps<Type, CharType>::ends_with(StringView str) const
    319 {
    320     if (type().length() < str.length())
    321         return false;
    322     return substr(type().length() - str.length()) == str;
    323 }
    324 
    325 inline String& operator+=(String& lhs, StringView rhs)
    326 {
    327     lhs.append(rhs.data(), rhs.length());
    328     return lhs;
    329 }
    330 
    331 inline String operator+(StringView lhs, StringView rhs)
    332 {
    333     String res;
    334     res.reserve(lhs.length() + rhs.length());
    335     res.append(lhs.data(), lhs.length());
    336     res.append(rhs.data(), rhs.length());
    337     return res;
    338 }
    339 
    340 [[gnu::always_inline]]
    341 inline bool operator==(const StringView& lhs, const StringView& rhs)
    342 {
    343     return lhs.length() == rhs.length() and
    344            (lhs.empty() or std::memcmp(lhs.begin(), rhs.begin(), (size_t)lhs.length()) == 0);
    345 }
    346 
    347 inline auto operator<=>(const StringView& lhs, const StringView& rhs)
    348 {
    349     auto lit = lhs.begin(), lend = lhs.end(), rit = rhs.begin(), rend = rhs.end();
    350     while (lit != lend and rit != rend) {
    351          if (auto cmp = *lit++ <=> *rit++; cmp != 0)
    352              return cmp;
    353     }
    354     if (lit == lend and rit == rend)
    355         return std::strong_ordering::equal;
    356     return lit == lend ? std::strong_ordering::less : std::strong_ordering::greater;
    357 
    358 }
    359 
    360 inline String operator""_str(const char* str, size_t)
    361 {
    362     return String(str);
    363 }
    364 
    365 inline StringView operator""_sv(const char* str, size_t)
    366 {
    367     return StringView{str};
    368 }
    369 
    370 }
    371 
    372 #endif // string_hh_INCLUDED