string.cpp

Go to the documentation of this file.

// Copyright 2020 Arthur Sonzogni. All rights reserved.
// Use of this source code is governed by the MIT license that can be found in
// the LICENSE file.
//
// Content of this file was created thanks to:
// -
// https://www.unicode.org/Public/UCD/latest/ucd/auxiliary/WordBreakProperty.txt
// - Markus Kuhn -- 2007-05-26 (Unicode 5.0)
//   http://www.cl.cam.ac.uk/~mgk25/ucs/wcwidth.c
// Thanks you!
 
#include "ftxui/screen/string.hpp"
 
#include <array>        // for array
#include <cstddef>      // for size_t
#include <cstdint>      // for uint32_t, uint8_t, uint16_t, int32_t
#include <string>       // for string, basic_string, wstring
#include <string_view>  // for string_view
#include <tuple>        // for _Swallow_assign, ignore
#include <vector>
 
#include "ftxui/screen/deprecated.hpp"       // for wchar_width, wstring_width
#include "ftxui/screen/string_internal.hpp"  // for WordBreakProperty, EatCodePoint, CodepointToWordBreakProperty, GlyphCount, GlyphIterate, GlyphNext, GlyphPrevious, IsCombining, IsControl, IsFullWidth, Utf8ToWordBreakProperty
 
namespace {
 
struct Interval {
  uint32_t first;
  uint32_t last;
};
 
using WBP = ftxui::WordBreakProperty;
struct WordBreakPropertyInterval {
  uint32_t first;
  uint32_t last;
  WBP property;
};
 
// g_full_width_characters et g_word_break_intervals, générés à partir de la
// base de données de caractères Unicode par tools/gen_unicode_tables.py.
#include "ftxui/screen/string_unicode_tables.ipp"
 
// Construit une table contenant uniquement les intervalles de caractères
// WBP::Extend
constexpr auto g_extend_characters{[]() constexpr {
  // Calcule le nombre d'intervalles de caractères « extend »
  constexpr size_t size = []() constexpr {
    size_t count = 0;
    for (auto interval : g_word_break_intervals) {
      if (interval.property == WBP::Extend) {
        count++;
      }
    }
    return count;
  }();
 
  // Crée le tableau des intervalles de caractères « extend »
  std::array<Interval, size> result{};
  size_t index = 0;
  for (auto interval : g_word_break_intervals) {
    if (interval.property == WBP::Extend) {
      result[index++] = {interval.first, interval.last};  // NOLINT
    }
  }
  return result;
}()};
 
// Recherche un point de code dans une liste triée d'Interval.
template <size_t N>
bool Bisearch(uint32_t ucs, const std::array<Interval, N>& table) {
  if (ucs < table.front().first || ucs > table.back().last) {  // NOLINT
    return false;
  }
 
  int min = 0;
  int max = N - 1;
  while (max >= min) {
    const int mid = (min + max) / 2;
    if (ucs > table[mid].last) {  // NOLINT
      min = mid + 1;
    } else if (ucs < table[mid].first) {  // NOLINT
      max = mid - 1;
    } else {
      return true;
    }
  }
 
  return false;
}
 
// Recherche une valeur dans une liste triée d'Interval + propriété.
template <class C, size_t N>
bool Bisearch(uint32_t ucs, const std::array<C, N>& table, C* out) {
  if (ucs < table.front().first || ucs > table.back().last) {  // NOLINT
    return false;
  }
 
  int min = 0;
  int max = N - 1;
  while (max >= min) {
    const int mid = (min + max) / 2;
    if (ucs > table[mid].last) {  // NOLINT
      min = mid + 1;
    } else if (ucs < table[mid].first) {  // NOLINT
      max = mid - 1;
    } else {
      *out = table[mid];  // NOLINT
      return true;
    }
  }
 
  return false;
}
 
int codepoint_width(uint32_t ucs) {
  if (ftxui::IsControl(ucs)) {
    return -1;
  }
 
  if (ftxui::IsCombining(ucs)) {
    return 0;
  }
 
  if (ftxui::IsFullWidth(ucs)) {
    return 2;
  }
 
  return 1;
}
 
}  // namespace
 
namespace ftxui {
 
// À partir de la chaîne encodée en UTF8 |input|, consomme entre 1 et 4 octets
// représentant un point de code. Place le point de code dans |ucs|. Démarre à
// |start| et met à jour |end| pour représenter le début du prochain octet à
// consommer lors d'exécutions consécutives.
bool EatCodePoint(std::string_view input,
                  size_t start,
                  size_t* end,
                  uint32_t* ucs) {
  if (start >= input.size()) {
    *end = start + 1;
    return false;
  }
  const uint8_t C0 = input[start];
 
  // Chaîne de 1 octet.
  if ((C0 & 0b1000'0000) == 0b0000'0000) {  // NOLINT
    *ucs = C0 & 0b0111'1111;                // NOLINT
    *end = start + 1;
    return true;
  }
 
  // Chaîne de 2 octets.
  if ((C0 & 0b1110'0000) == 0b1100'0000 &&  // NOLINT
      start + 1 < input.size()) {
    const uint8_t C1 = input[start + 1];
    *ucs = 0;
    *ucs += C0 & 0b0001'1111;  // NOLINT
    *ucs <<= 6;                // NOLINT
    *ucs += C1 & 0b0011'1111;  // NOLINT
    *end = start + 2;
    return true;
  }
 
  // Chaîne de 3 octets.
  if ((C0 & 0b1111'0000) == 0b1110'0000 &&  // NOLINT
      start + 2 < input.size()) {
    const uint8_t C1 = input[start + 1];
    const uint8_t C2 = input[start + 2];
    *ucs = 0;
    *ucs += C0 & 0b0000'1111;  // NOLINT
    *ucs <<= 6;                // NOLINT
    *ucs += C1 & 0b0011'1111;  // NOLINT
    *ucs <<= 6;                // NOLINT
    *ucs += C2 & 0b0011'1111;  // NOLINT
    *end = start + 3;
    return true;
  }
 
  // Chaîne de 4 octets.
  if ((C0 & 0b1111'1000) == 0b1111'0000 &&  // NOLINT
      start + 3 < input.size()) {
    const uint8_t C1 = input[start + 1];
    const uint8_t C2 = input[start + 2];
    const uint8_t C3 = input[start + 3];
    *ucs = 0;
    *ucs += C0 & 0b0000'0111;  // NOLINT
    *ucs <<= 6;                // NOLINT
    *ucs += C1 & 0b0011'1111;  // NOLINT
    *ucs <<= 6;                // NOLINT
    *ucs += C2 & 0b0011'1111;  // NOLINT
    *ucs <<= 6;                // NOLINT
    *ucs += C3 & 0b0011'1111;  // NOLINT
    *end = start + 4;
    return true;
  }
 
  *end = start + 1;
  return false;
}
 
// À partir de la chaîne encodée en UTF16 |input|, consomme entre 1 et 4
// octets représentant un point de code. Place le point de code dans |ucs|.
// Démarre à |start| et met à jour |end| pour représenter le début du
// prochain octet à consommer lors d'exécutions consécutives.
bool EatCodePoint(std::wstring_view input,
                  size_t start,
                  size_t* end,
                  uint32_t* ucs) {
  if (start >= input.size()) {
    *end = start + 1;
    return false;
  }
 
  // Sous Linux, wstring utilise l'encodage UTF32 :
  if constexpr (sizeof(wchar_t) == 4) {
    *ucs = input[start];  // NOLINT
    *end = start + 1;
    return true;
  }
 
  // Sous Windows, wstring utilise l'encodage UTF16 :
  int32_t C0 = input[start];  // NOLINT
 
  // Taille de 1 mot :
  if (C0 < 0xd800 || C0 >= 0xdc00) {  // NOLINT
    *ucs = C0;
    *end = start + 1;
    return true;
  }
 
  // Taille de 2 mots :
  if (start + 1 >= input.size()) {
    *end = start + 2;
    return false;
  }
 
  int32_t C1 = input[start + 1];                         // NOLINT
  *ucs = ((C0 & 0x3ff) << 10) + (C1 & 0x3ff) + 0x10000;  // NOLINT
  *end = start + 2;
  return true;
}
 
bool IsCombining(uint32_t ucs) {
  return Bisearch(ucs, g_extend_characters);
}
 
bool IsFullWidth(uint32_t ucs) {
  if (ucs < 0x0300) {  // Chemin rapide : // NOLINT
    return false;
  }
 
  return Bisearch(ucs, g_full_width_characters);
}
 
bool IsControl(uint32_t ucs) {
  if (ucs == 0) {
    return true;
  }
  if (ucs < 32) {  // NOLINT
    const uint32_t LINE_FEED = 10;
    return ucs != LINE_FEED;
  }
  if (ucs >= 0x7f && ucs < 0xa0) {  // NOLINT
    return true;
  }
  return false;
}
 
WordBreakProperty CodepointToWordBreakProperty(uint32_t codepoint) {
  WordBreakPropertyInterval interval = {0, 0, WBP::ALetter};
  std::ignore = Bisearch(codepoint, g_word_break_intervals, &interval);
  return interval.property;
}
 
int wchar_width(wchar_t ucs) {
  return codepoint_width(uint32_t(ucs));
}
 
int wstring_width(const std::wstring& text) {
  int width = 0;
 
  for (const wchar_t& it : text) {
    const int w = wchar_width(it);
    if (w < 0) {
      return -1;
    }
    width += w;
  }
  return width;
}
 
// Retourne le nombre de cellules occupées par la chaîne encodée en UTF8
// |input| lorsqu'elle est affichée. Les caractères de contrôle n'occupent
// aucun espace, les caractères combinants modifient le caractère précédent et
// n'occupent aucun espace, les caractères pleine largeur occupent deux
// cellules et tous les autres caractères occupent une cellule.
int string_width(std::string_view input) {
  // Optimisation 1 octet : cette fonction est souvent appelée sur un seul
  // caractère ASCII, on peut donc optimiser ce cas en sautant le décodage
  // UTF8.
  if (input.size() == 1) {
    const char c = input[0];
    if (c >= 32 && c < 127) {  // NOLINT
      return 1;
    }
  }
 
  // Optimisation ASCII : si la chaîne est purement ASCII, on peut sauter le
  // décodage UTF8 et simplement compter le nombre de caractères, en ignorant
  // les caractères de contrôle.
  bool is_pure_ascii = true;
  for (const char c : input) {
    if (c < 31 || c >= 127) {  // NOLINT
      is_pure_ascii = false;
      break;
    }
  }
  if (is_pure_ascii) {
    return static_cast<int>(input.size());
  }
 
  int width = 0;
  size_t start = 0;
  while (start < input.size()) {
    uint32_t codepoint = 0;
    if (!EatCodePoint(input, start, &start, &codepoint)) {
      continue;
    }
 
    if (IsControl(codepoint)) {
      continue;
    }
 
    if (IsCombining(codepoint)) {
      continue;
    }
 
    if (IsFullWidth(codepoint)) {
      width += 2;
      continue;
    }
 
    width += 1;
  }
  return width;
}
 
std::vector<std::string> Utf8ToGlyphs(std::string_view input) {
  std::vector<std::string> out;
  out.reserve(input.size());
  size_t start = 0;
  size_t end = 0;
  while (start < input.size()) {
    uint32_t codepoint = 0;
    if (!EatCodePoint(input, start, &end, &codepoint)) {
      start = end;
      continue;
    }
 
    const auto append = input.substr(start, end - start);
    start = end;
 
    // Ignore les caractères de contrôle.
    if (IsControl(codepoint)) {
      continue;
    }
 
    // Les caractères combinants sont ajoutés au glyphe précédent qu'ils
    // modifient.
    if (IsCombining(codepoint)) {
      if (!out.empty()) {
        out.back() += append;
      }
      continue;
    }
 
    // Les caractères pleine largeur occupent deux cellules. La seconde est
    // constituée d'une chaîne vide afin de réserver l'espace occupé par la
    // première.
    if (IsFullWidth(codepoint)) {
      out.emplace_back(append);
      out.emplace_back("");
      continue;
    }
 
    // Caractères normaux :
    out.emplace_back(append);
  }
  return out;
}
 
size_t GlyphPrevious(std::string_view input, size_t start) {
  while (true) {
    if (start == 0) {
      return 0;
    }
    start--;
 
    // Saute les octets de continuation UTF8.
    if ((input[start] & 0b1100'0000) == 0b1000'0000) {
      continue;
    }
 
    uint32_t codepoint = 0;
    size_t end = 0;
    const bool eaten = EatCodePoint(input, start, &end, &codepoint);
 
    // Ignore les caractères invalides, de contrôle et combinants.
    if (!eaten || IsControl(codepoint) || IsCombining(codepoint)) {
      continue;
    }
 
    return start;
  }
}
 
size_t GlyphNext(std::string_view input, size_t start) {
  bool glyph_found = false;
  while (start < input.size()) {
    size_t end = 0;
    uint32_t codepoint = 0;
    const bool eaten = EatCodePoint(input, start, &end, &codepoint);
 
    // Ignore les caractères invalides, de contrôle et combinants.
    if (!eaten || IsControl(codepoint) || IsCombining(codepoint)) {
      start = end;
      continue;
    }
 
    // On consomme le début du glyphe suivant. Si c'est celui demandé, on
    // retourne immédiatement sa position de départ.
    if (glyph_found) {
      return static_cast<int>(start);
    }
 
    // Sinon, on saute ce glyphe et on itère :
    glyph_found = true;
    start = end;
  }
  return static_cast<int>(input.size());
}
 
size_t GlyphIterate(std::string_view input, int glyph_offset, size_t start) {
  if (glyph_offset >= 0) {
    for (int i = 0; i < glyph_offset; ++i) {
      start = GlyphNext(input, start);
    }
    return start;
  } else {
    for (int i = 0; i < -glyph_offset; ++i) {
      start = GlyphPrevious(input, start);
    }
    return start;
  }
}
 
std::vector<int> CellToGlyphIndex(std::string_view input) {
  int x = -1;
  std::vector<int> out;
  out.reserve(input.size());
  size_t start = 0;
  size_t end = 0;
  while (start < input.size()) {
    uint32_t codepoint = 0;
    const bool eaten = EatCodePoint(input, start, &end, &codepoint);
    start = end;
 
    // Ignore les caractères invalides / de contrôle.
    if (!eaten || IsControl(codepoint)) {
      continue;
    }
 
    // Les caractères combinants sont ajoutés au glyphe précédent qu'ils
    // modifient.
    if (IsCombining(codepoint)) {
      if (x == -1) {
        ++x;
        out.push_back(x);
      }
      continue;
    }
 
    // Les caractères pleine largeur occupent deux cellules. La seconde est
    // constituée d'une chaîne vide afin de réserver l'espace occupé par la
    // première.
    if (IsFullWidth(codepoint)) {
      ++x;
      out.push_back(x);
      out.push_back(x);
      continue;
    }
 
    // Caractères normaux :
    ++x;
    out.push_back(x);
  }
  return out;
}
 
int GlyphCount(std::string_view input) {
  int size = 0;
  size_t start = 0;
  size_t end = 0;
  while (start < input.size()) {
    uint32_t codepoint = 0;
    const bool eaten = EatCodePoint(input, start, &end, &codepoint);
    start = end;
 
    // Ignore les caractères invalides :
    if (!eaten || IsControl(codepoint)) {
      continue;
    }
 
    // Ignore les caractères combinants, sauf s'ils n'ont pas de prédécesseur
    // avec lequel se combiner.
    if (IsCombining(codepoint)) {
      if (size == 0) {
        size++;
      }
      continue;
    }
 
    size++;
  }
  return size;
}
 
std::vector<WordBreakProperty> Utf8ToWordBreakProperty(std::string_view input) {
  std::vector<WordBreakProperty> out;
  out.reserve(input.size());
  size_t start = 0;
  size_t end = 0;
  while (start < input.size()) {
    uint32_t codepoint = 0;
    if (!EatCodePoint(input, start, &end, &codepoint)) {
      start = end;
      continue;
    }
    start = end;
 
    // Ignore les caractères de contrôle.
    if (IsControl(codepoint)) {
      continue;
    }
 
    // Ignore les caractères combinants.
    if (IsCombining(codepoint)) {
      continue;
    }
 
    WordBreakPropertyInterval interval = {0, 0, WBP::ALetter};
    std::ignore = Bisearch(codepoint, g_word_break_intervals, &interval);
    out.push_back(interval.property);
  }
  return out;
}
 
/// Convertit un std::wstring en std::string UTF8.
std::string to_string(std::wstring_view s) {
  std::string out;
 
  size_t i = 0;
  uint32_t codepoint = 0;
  while (EatCodePoint(s, i, &i, &codepoint)) {
    // Conversion point de code <-> UTF-8
    //
    // ┏━━━━━━━━┳━━━━━━━━┳━━━━━━━━┳━━━━━━━━┓
    // ┃Octet 1 ┃Octet 2 ┃Octet 3 ┃Octet 4 ┃
    // ┡━━━━━━━━╇━━━━━━━━╇━━━━━━━━╇━━━━━━━━┩
    // │0xxxxxxx│        │        │        │
    // ├────────┼────────┼────────┼────────┤
    // │110xxxxx│10xxxxxx│        │        │
    // ├────────┼────────┼────────┼────────┤
    // │1110xxxx│10xxxxxx│10xxxxxx│        │
    // ├────────┼────────┼────────┼────────┤
    // │11110xxx│10xxxxxx│10xxxxxx│10xxxxxx│
    // └────────┴────────┴────────┴────────┘
 
    // UTF8 sur 1 octet
    if (codepoint <= 0b000'0000'0111'1111) {  // NOLINT
      const uint8_t p1 = codepoint;
      out.push_back(p1);  // NOLINT
      continue;
    }
 
    // UTF8 sur 2 octets
    if (codepoint <= 0b000'0111'1111'1111) {  // NOLINT
      uint8_t p2 = codepoint & 0b111111;      // NOLINT
      codepoint >>= 6;                        // NOLINT
      uint8_t p1 = codepoint;                 // NOLINT
      out.push_back(0b11000000 + p1);         // NOLINT
      out.push_back(0b10000000 + p2);         // NOLINT
      continue;
    }
 
    // UTF8 sur 3 octets
    if (codepoint <= 0b1111'1111'1111'1111) {  // NOLINT
      uint8_t p3 = codepoint & 0b111111;       // NOLINT
      codepoint >>= 6;                         // NOLINT
      uint8_t p2 = codepoint & 0b111111;       // NOLINT
      codepoint >>= 6;                         // NOLINT
      uint8_t p1 = codepoint;                  // NOLINT
      out.push_back(0b11100000 + p1);          // NOLINT
      out.push_back(0b10000000 + p2);          // NOLINT
      out.push_back(0b10000000 + p3);          // NOLINT
      continue;
    }
 
    // UTF8 sur 4 octets
    if (codepoint <= 0b1'0000'1111'1111'1111'1111) {  // NOLINT
      uint8_t p4 = codepoint & 0b111111;              // NOLINT
      codepoint >>= 6;                                // NOLINT
      uint8_t p3 = codepoint & 0b111111;              // NOLINT
      codepoint >>= 6;                                // NOLINT
      uint8_t p2 = codepoint & 0b111111;              // NOLINT
      codepoint >>= 6;                                // NOLINT
      uint8_t p1 = codepoint;                         // NOLINT
      out.push_back(0b11110000 + p1);                 // NOLINT
      out.push_back(0b10000000 + p2);                 // NOLINT
      out.push_back(0b10000000 + p3);                 // NOLINT
      out.push_back(0b10000000 + p4);                 // NOLINT
      continue;
    }
 
    // Autre chose ?
  }
  return out;
}
 
/// Convertit un std::string UTF8 en std::wstring.
std::wstring to_wstring(std::string_view s) {
  std::wstring out;
 
  size_t i = 0;
  uint32_t codepoint = 0;
  while (EatCodePoint(s, i, &i, &codepoint)) {
    // Sous Linux, wstring est encodé en UTF32 :
    if constexpr (sizeof(wchar_t) == 4) {
      out.push_back(codepoint);  // NOLINT
      continue;
    }
 
    // Sous Windows, wstring est encodé en UTF16 :
 
    // Point de code encodé sur 1 mot :
    // NOLINTNEXTLINE
    if (codepoint < 0xD800 || (codepoint > 0xDFFF && codepoint < 0x10000)) {
      uint16_t p0 = codepoint;  // NOLINT
      out.push_back(p0);        // NOLINT
      continue;
    }
 
    // Point de code encodé sur 2 mots :
    codepoint -= 0x010000;                               // NOLINT
    uint16_t p0 = (((codepoint << 12) >> 22) + 0xD800);  // NOLINT
    uint16_t p1 = (((codepoint << 22) >> 22) + 0xDC00);  // NOLINT
    out.push_back(p0);                                   // NOLINT
    out.push_back(p1);                                   // NOLINT
  }
  return out;
}
 
}  // namespace ftxui