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 及 g_word_break_intervals，由
// tools/gen_unicode_tables.py 從 Unicode Character Database 產生。
#include "ftxui/screen/string_unicode_tables.ipp"
 
// 建構僅包含 WBP::Extend 字元區間的表格
constexpr auto g_extend_characters{[]() constexpr {
  // 計算延伸字元區間的數量
  constexpr size_t size = []() constexpr {
    size_t count = 0;
    for (auto interval : g_word_break_intervals) {
      if (interval.property == WBP::Extend) {
        count++;
      }
    }
    return count;
  }();
 
  // 建立延伸字元區間的陣列
  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;
}()};
 
// 在 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;
}
 
// 在 Interval + 屬性的排序列表中查找一個值。
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 {
 
// 從 UTF8 編碼的字串 |input| 中，讀取介於 1 到 4 個位元組，表示一個碼點。
// 將碼點放入 |ucs| 中。從 |start| 開始，並更新 |end| 以表示下一個要讀取的位元組的開頭，
// 以便連續執行。
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];
 
  // 1 位元組字串。
  if ((C0 & 0b1000'0000) == 0b0000'0000) {  // NOLINT
    *ucs = C0 & 0b0111'1111;                // NOLINT
    *end = start + 1;
    return true;
  }
 
  // 2 位元組字串。
  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;
  }
 
  // 3 位元組字串。
  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;
  }
 
  // 4 位元組字串。
  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;
}
 
// 從 UTF16 編碼的字串 |input| 中，讀取介於 1 到 4 個位元組，表示一個碼點。
// 將碼點放入 |ucs| 中。從 |start| 開始，並更新 |end| 以表示下一個要讀取的位元組的開頭，
// 以便連續執行。
bool EatCodePoint(std::wstring_view input,
                  size_t start,
                  size_t* end,
                  uint32_t* ucs) {
  if (start >= input.size()) {
    *end = start + 1;
    return false;
  }
 
  // 在 linux 上，wstring 使用 UTF32 編碼：
  if constexpr (sizeof(wchar_t) == 4) {
    *ucs = input[start];  // NOLINT
    *end = start + 1;
    return true;
  }
 
  // 在 windows 上，wstring 使用 UTF16 編碼：
  int32_t C0 = input[start];  // NOLINT
 
  // 1 word 大小：
  if (C0 < 0xd800 || C0 >= 0xdc00) {  // NOLINT
    *ucs = C0;
    *end = start + 1;
    return true;
  }
 
  // 2 word 大小：
  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) {  // 快速路徑： // 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;
}
 
// 傳回 UTF8 編碼字串 |input| 在印出時佔用的 cell 數量。
// 控制字元不佔用任何空間，組合字元
// 會修改前一個字元且不佔用任何空間，全形
// 字元佔用兩個 cell，而其他所有字元則佔用一個
// cell。
int string_width(std::string_view input) {
  // 1 位元組最佳化：此函式通常在單一 ASCII
  // 字元上被呼叫，因此我們可以透過跳過 UTF8 解碼來最佳化這種情況。
  if (input.size() == 1) {
    const char c = input[0];
    if (c >= 32 && c < 127) {  // NOLINT
      return 1;
    }
  }
 
  // ASCII 最佳化：如果字串為純 ASCII，我們可以跳過 UTF8
  // 解碼，只計算字元的數量，並忽略控制
  // 字元。
  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;
 
    // 忽略控制字元。
    if (IsControl(codepoint)) {
      continue;
    }
 
    // 組合字元會與它們正在修改的前一個字符放在一起。
    if (IsCombining(codepoint)) {
      if (!out.empty()) {
        out.back() += append;
      }
      continue;
    }
 
    // Fullwidth characters take two cells. The second is made of the empty
    // 全形字元佔用兩個單元格。第二個是空字串，用於保留第一個佔用的空間。
    if (IsFullWidth(codepoint)) {
      out.emplace_back(append);
      out.emplace_back("");
      continue;
    }
 
    // 一般字元：
    out.emplace_back(append);
  }
  return out;
}
 
size_t GlyphPrevious(std::string_view input, size_t start) {
  while (true) {
    if (start == 0) {
      return 0;
    }
    start--;
 
    // 跳過 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);
 
    // 忽略無效、控制字元及組合字元。
    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);
 
    // 忽略無效、控制字元及組合字元。
    if (!eaten || IsControl(codepoint) || IsCombining(codepoint)) {
      start = end;
      continue;
    }
 
    // 我們吃掉下一個字符的開頭。如果我們正在吃掉的正是
    // 請求的那一個，立即回傳它的起始位置。
    if (glyph_found) {
      return static_cast<int>(start);
    }
 
    // 否則，跳過這個字符並繼續迭代：
    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;
 
    // 忽略無效／控制字元。
    if (!eaten || IsControl(codepoint)) {
      continue;
    }
 
    // 組合字元會與它們正在修改的前一個字符放在一起。
    if (IsCombining(codepoint)) {
      if (x == -1) {
        ++x;
        out.push_back(x);
      }
      continue;
    }
 
    // Fullwidth characters take two cells. The second is made of the empty
    // 全形字元佔用兩個單元格。第二個是空字串，用於保留第一個佔用的空間。
    if (IsFullWidth(codepoint)) {
      ++x;
      out.push_back(x);
      out.push_back(x);
      continue;
    }
 
    // 一般字元：
    ++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;
 
    // 忽略無效字元：
    if (!eaten || IsControl(codepoint)) {
      continue;
    }
 
    // 忽略組合字元，除非它們沒有可
    // 組合的前置字元。
    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;
 
    // 忽略控制字元。
    if (IsControl(codepoint)) {
      continue;
    }
 
    // 忽略組合字元。
    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;
}
 
/// 將 std::wstring 轉換為 UTF8 std::string。
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)) {
    // 碼位 <-> UTF-8 轉換
    //
    // ┏━━━━━━━━┳━━━━━━━━┳━━━━━━━━┳━━━━━━━━┓
    // ┃Byte 1  ┃Byte 2  ┃Byte 3  ┃Byte 4  ┃
    // ┡━━━━━━━━╇━━━━━━━━╇━━━━━━━━╇━━━━━━━━┩
    // │0xxxxxxx│        │        │        │
    // ├────────┼────────┼────────┼────────┤
    // │110xxxxx│10xxxxxx│        │        │
    // ├────────┼────────┼────────┼────────┤
    // │1110xxxx│10xxxxxx│10xxxxxx│        │
    // ├────────┼────────┼────────┼────────┤
    // │11110xxx│10xxxxxx│10xxxxxx│10xxxxxx│
    // └────────┴────────┴────────┴────────┘
 
    // 1 位元組 UTF8
    if (codepoint <= 0b000'0000'0111'1111) {  // NOLINT
      const uint8_t p1 = codepoint;
      out.push_back(p1);  // NOLINT
      continue;
    }
 
    // 2 位元組 UTF8
    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;
    }
 
    // 3 位元組 UTF8
    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;
    }
 
    // 4 位元組 UTF8
    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;
    }
 
    // 其他情況？
  }
  return out;
}
 
/// 將 UTF8 std::string 轉換為 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)) {
    // 在 Linux 上，wstring 使用 UTF32 編碼：
    if constexpr (sizeof(wchar_t) == 4) {
      out.push_back(codepoint);  // NOLINT
      continue;
    }
 
    // 在 Windows 上，wstring 使用 UTF16 編碼：
 
    // 使用 1 個字組編碼的碼點：
    // NOLINTNEXTLINE
    if (codepoint < 0xD800 || (codepoint > 0xDFFF && codepoint < 0x10000)) {
      uint16_t p0 = codepoint;  // NOLINT
      out.push_back(p0);        // NOLINT
      continue;
    }
 
    // 使用 2 個 word 編碼的碼位：
    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