Modules/TextEditor/private/Utf8.cpp
Шурупов Илья Викторович 64562ff549 TextEditor: complete the piece-tree engine
The module is now a full editing engine, independent of widgets and the platform:

- PieceTree: offset-based piece table on the generic AvlTree. Nodes cache bytes and line
  breaks of their piece and both subtrees, so offset and line lookups are O(log pieces).
  Append-only chunks, piece merging, snapshots readable from another thread, compaction.
- Document: undo/redo as reversible diffs with groups, typing merge and stored selections,
  change listeners, anchors, modified tracking, line-break normalization (LF inside,
  CRLF/CR restored on output).
- Editor: multi-cursor command layer - motions, word and line operations, indentation,
  auto-closing pairs, clipboard text, occurrences, bracket matching.
- TextSearch: literal (case folding, whole word) and regular-expression search and replace.
- TextFile: UTF-8/UTF-16 with byte order marks, atomic save.
- utf8: grapheme boundaries, character classes, display widths, case mapping.

131 tests, including randomized runs against std::string and an editor command fuzz.

Co-Authored-By: Claude <noreply@anthropic.com>
2026-11-13 17:12:58 +03:00

260 lines
12 KiB
C++

#include "Utf8.hpp"
using namespace tp::text;
namespace {
struct CodeRange {
char32_t first;
char32_t last;
};
template <size_t Count>
bool inRanges(const CodeRange (&ranges)[Count], char32_t codePoint) {
// The tables are sorted, so a binary search finds the only range that could hold the code point.
size_t low = 0;
size_t high = Count;
while (low < high) {
const size_t middle = (low + high) / 2;
if (codePoint > ranges[middle].last) low = middle + 1;
else high = middle;
}
return low < Count && codePoint >= ranges[low].first;
}
// Nonspacing, enclosing and spacing combining marks of the scripts in common use, plus the characters
// that modify the preceding one (variation selectors, emoji skin tones, tag characters).
constexpr CodeRange kExtending[] = {
{ 0x0300, 0x036F }, { 0x0483, 0x0489 }, { 0x0591, 0x05BD }, { 0x05BF, 0x05BF }, { 0x05C1, 0x05C2 },
{ 0x05C4, 0x05C5 }, { 0x05C7, 0x05C7 }, { 0x0610, 0x061A }, { 0x064B, 0x065F }, { 0x0670, 0x0670 },
{ 0x06D6, 0x06DC }, { 0x06DF, 0x06E4 }, { 0x06E7, 0x06E8 }, { 0x06EA, 0x06ED }, { 0x0711, 0x0711 },
{ 0x0730, 0x074A }, { 0x07A6, 0x07B0 }, { 0x0816, 0x082D }, { 0x08D3, 0x08E1 }, { 0x08E3, 0x0903 },
{ 0x093A, 0x093C }, { 0x093E, 0x094F }, { 0x0951, 0x0957 }, { 0x0962, 0x0963 }, { 0x0981, 0x0983 },
{ 0x09BC, 0x09BC }, { 0x09BE, 0x09CD }, { 0x09D7, 0x09D7 }, { 0x09E2, 0x09E3 }, { 0x0A01, 0x0A03 },
{ 0x0A3C, 0x0A51 }, { 0x0A70, 0x0A71 }, { 0x0A75, 0x0A75 }, { 0x0A81, 0x0A83 }, { 0x0ABC, 0x0ABC },
{ 0x0ABE, 0x0ACD }, { 0x0AE2, 0x0AE3 }, { 0x0B01, 0x0B03 }, { 0x0B3C, 0x0B3C }, { 0x0B3E, 0x0B57 },
{ 0x0B82, 0x0B82 }, { 0x0BBE, 0x0BCD }, { 0x0BD7, 0x0BD7 }, { 0x0C00, 0x0C04 }, { 0x0C3E, 0x0C56 },
{ 0x0C81, 0x0C83 }, { 0x0CBC, 0x0CBC }, { 0x0CBE, 0x0CD6 }, { 0x0D00, 0x0D03 }, { 0x0D3B, 0x0D3C },
{ 0x0D3E, 0x0D4D }, { 0x0D57, 0x0D57 }, { 0x0D82, 0x0D83 }, { 0x0DCA, 0x0DDF }, { 0x0E31, 0x0E31 },
{ 0x0E34, 0x0E3A }, { 0x0E47, 0x0E4E }, { 0x0EB1, 0x0EB1 }, { 0x0EB4, 0x0EBC }, { 0x0EC8, 0x0ECD },
{ 0x0F18, 0x0F19 }, { 0x0F35, 0x0F35 }, { 0x0F37, 0x0F37 }, { 0x0F39, 0x0F39 }, { 0x0F3E, 0x0F3F },
{ 0x0F71, 0x0F84 }, { 0x0F86, 0x0F87 }, { 0x0F8D, 0x0FBC }, { 0x102B, 0x103E }, { 0x1056, 0x1059 },
{ 0x135D, 0x135F }, { 0x1712, 0x1714 }, { 0x17B4, 0x17D3 }, { 0x180B, 0x180D }, { 0x1AB0, 0x1AFF },
{ 0x1B00, 0x1B04 }, { 0x1B34, 0x1B44 }, { 0x1DC0, 0x1DFF }, { 0x200C, 0x200C }, { 0x20D0, 0x20F0 },
{ 0x302A, 0x302F }, { 0x3099, 0x309A }, { 0xA66F, 0xA672 }, { 0xA674, 0xA67D }, { 0xA8E0, 0xA8F1 },
{ 0xFB1E, 0xFB1E }, { 0xFE00, 0xFE0F }, { 0xFE20, 0xFE2F }, { 0x1F3FB, 0x1F3FF }, { 0xE0020, 0xE007F },
{ 0xE0100, 0xE01EF },
};
constexpr CodeRange kPictographic[] = {
{ 0x00A9, 0x00A9 }, { 0x00AE, 0x00AE }, { 0x203C, 0x203C }, { 0x2049, 0x2049 }, { 0x2122, 0x2122 },
{ 0x2139, 0x2139 }, { 0x2194, 0x21AA }, { 0x231A, 0x23FF }, { 0x24C2, 0x24C2 }, { 0x25AA, 0x25FE },
{ 0x2600, 0x27BF }, { 0x2934, 0x2935 }, { 0x2B05, 0x2B55 }, { 0x3030, 0x3030 }, { 0x303D, 0x303D },
{ 0x3297, 0x3299 }, { 0x1F000, 0x1F0FF }, { 0x1F10D, 0x1F10F }, { 0x1F12F, 0x1F12F }, { 0x1F16C, 0x1F171 },
{ 0x1F17E, 0x1F17F }, { 0x1F18E, 0x1F18E }, { 0x1F191, 0x1F19A }, { 0x1F1AD, 0x1F1E5 }, { 0x1F201, 0x1F20F },
{ 0x1F21A, 0x1F21A }, { 0x1F22F, 0x1F22F }, { 0x1F232, 0x1F23A }, { 0x1F23C, 0x1F23F }, { 0x1F249, 0x1F3FA },
{ 0x1F400, 0x1F53D }, { 0x1F546, 0x1F64F }, { 0x1F680, 0x1F6FF }, { 0x1F774, 0x1F77F }, { 0x1F7D5, 0x1F7FF },
{ 0x1F80C, 0x1F80F }, { 0x1F848, 0x1F84F }, { 0x1F85A, 0x1F85F }, { 0x1F888, 0x1F88F }, { 0x1F8AE, 0x1F8FF },
{ 0x1F90C, 0x1F93A }, { 0x1F93C, 0x1F945 }, { 0x1F947, 0x1FAFF }, { 0x1FC00, 0x1FFFD },
};
constexpr CodeRange kWide[] = {
{ 0x1100, 0x115F }, { 0x231A, 0x231B }, { 0x23E9, 0x23EC }, { 0x23F0, 0x23F0 }, { 0x23F3, 0x23F3 },
{ 0x25FD, 0x25FE }, { 0x2614, 0x2615 }, { 0x2648, 0x2653 }, { 0x267F, 0x267F }, { 0x2693, 0x2693 },
{ 0x26A1, 0x26A1 }, { 0x26AA, 0x26AB }, { 0x26BD, 0x26BE }, { 0x26C4, 0x26C5 }, { 0x26CE, 0x26CE },
{ 0x26D4, 0x26D4 }, { 0x26EA, 0x26EA }, { 0x26F2, 0x26F3 }, { 0x26F5, 0x26F5 }, { 0x26FA, 0x26FA },
{ 0x26FD, 0x26FD }, { 0x2705, 0x2705 }, { 0x270A, 0x270B }, { 0x2728, 0x2728 }, { 0x274C, 0x274C },
{ 0x274E, 0x274E }, { 0x2753, 0x2755 }, { 0x2757, 0x2757 }, { 0x2795, 0x2797 }, { 0x27B0, 0x27B0 },
{ 0x27BF, 0x27BF }, { 0x2B1B, 0x2B1C }, { 0x2B50, 0x2B50 }, { 0x2B55, 0x2B55 }, { 0x2E80, 0x303E },
{ 0x3041, 0x33FF }, { 0x3400, 0x4DBF }, { 0x4E00, 0x9FFF }, { 0xA000, 0xA4CF }, { 0xA960, 0xA97F },
{ 0xAC00, 0xD7A3 }, { 0xF900, 0xFAFF }, { 0xFE30, 0xFE4F }, { 0xFE50, 0xFE6F }, { 0xFF00, 0xFF60 },
{ 0xFFE0, 0xFFE6 }, { 0x1F004, 0x1F004 }, { 0x1F0CF, 0x1F0CF }, { 0x1F18E, 0x1F18E }, { 0x1F191, 0x1F19A },
{ 0x1F1E6, 0x1F1FF }, { 0x1F200, 0x1F251 }, { 0x1F300, 0x1F64F }, { 0x1F680, 0x1F6FF }, { 0x1F900, 0x1F9FF },
{ 0x1FA70, 0x1FAFF }, { 0x20000, 0x2FFFD }, { 0x30000, 0x3FFFD },
};
// Punctuation outside ASCII that separates words.
constexpr CodeRange kSeparators[] = {
{ 0x00A1, 0x00A1 }, { 0x00A7, 0x00A7 }, { 0x00AB, 0x00AB }, { 0x00B6, 0x00B7 }, { 0x00BB, 0x00BB },
{ 0x00BF, 0x00BF }, { 0x00D7, 0x00D7 }, { 0x00F7, 0x00F7 }, { 0x2010, 0x2027 }, { 0x2030, 0x205E },
{ 0x2190, 0x23FF }, { 0x2500, 0x25FF }, { 0x2E00, 0x2E7F }, { 0x3001, 0x3003 }, { 0x3008, 0x3011 },
{ 0x3014, 0x301F }, { 0xFF01, 0xFF0F }, { 0xFF1A, 0xFF20 }, { 0xFF3B, 0xFF40 }, { 0xFF5B, 0xFF65 },
};
// Pairs laid out as upper, lower, upper, lower...: the lower case letter is the odd or the even one.
bool isPairedBlock(char32_t codePoint, bool& upperIsEven) {
const bool even = (codePoint >= 0x0100 && codePoint <= 0x012F) || (codePoint >= 0x0132 && codePoint <= 0x0137) ||
(codePoint >= 0x014A && codePoint <= 0x0177) || (codePoint >= 0x0460 && codePoint <= 0x0481) ||
(codePoint >= 0x048A && codePoint <= 0x04BF) || (codePoint >= 0x04D0 && codePoint <= 0x052F) ||
(codePoint >= 0x1E00 && codePoint <= 0x1E95) || (codePoint >= 0x1EA0 && codePoint <= 0x1EFF);
const bool odd = (codePoint >= 0x0139 && codePoint <= 0x0148) || (codePoint >= 0x0179 && codePoint <= 0x017E) ||
(codePoint >= 0x04C1 && codePoint <= 0x04CE);
upperIsEven = even;
return even || odd;
}
}
void utf8::append(std::string& out, char32_t codePoint) {
if (codePoint > 0x10FFFF || (codePoint >= 0xD800 && codePoint <= 0xDFFF)) codePoint = kReplacement;
if (codePoint < 0x80) {
out += char(codePoint);
} else if (codePoint < 0x800) {
out += char(0xC0 | (codePoint >> 6));
out += char(0x80 | (codePoint & 0x3F));
} else if (codePoint < 0x10000) {
out += char(0xE0 | (codePoint >> 12));
out += char(0x80 | ((codePoint >> 6) & 0x3F));
out += char(0x80 | (codePoint & 0x3F));
} else {
out += char(0xF0 | (codePoint >> 18));
out += char(0x80 | ((codePoint >> 12) & 0x3F));
out += char(0x80 | ((codePoint >> 6) & 0x3F));
out += char(0x80 | (codePoint & 0x3F));
}
}
std::string utf8::encode(char32_t codePoint) {
std::string out;
append(out, codePoint);
return out;
}
bool utf8::isValid(std::string_view text) {
for (size_t position = 0; position < text.size();) {
size_t length = 1;
const char32_t codePoint = codePointAt(text, position, &length);
// A real U+FFFD is three bytes long; a decoding failure reports one.
if (codePoint == kReplacement && length == 1) return false;
position += length;
}
return true;
}
std::string utf8::sanitized(std::string_view text) {
if (isValid(text)) return std::string(text);
std::string out;
out.reserve(text.size());
for (size_t position = 0; position < text.size();) {
size_t length = 1;
const char32_t codePoint = codePointAt(text, position, &length);
if (codePoint == kReplacement && length == 1) append(out, kReplacement);
else out.append(text.substr(position, length));
position += length;
}
return out;
}
bool utf8::isExtending(char32_t codePoint) { return codePoint >= 0x0300 && inRanges(kExtending, codePoint); }
bool utf8::isRegionalIndicator(char32_t codePoint) { return codePoint >= 0x1F1E6 && codePoint <= 0x1F1FF; }
bool utf8::isPictographic(char32_t codePoint) { return codePoint >= 0x00A9 && inRanges(kPictographic, codePoint); }
bool utf8::isWhitespace(char32_t codePoint) {
if (codePoint < 0x80) return codePoint == ' ' || codePoint == '\t' || codePoint == '\n' || codePoint == '\r' ||
codePoint == '\f' || codePoint == '\v';
return codePoint == 0x00A0 || codePoint == 0x1680 || (codePoint >= 0x2000 && codePoint <= 0x200A) ||
codePoint == 0x2028 || codePoint == 0x2029 || codePoint == 0x202F || codePoint == 0x205F ||
codePoint == 0x3000;
}
int utf8::displayWidth(char32_t codePoint) {
if (codePoint < 0x20 || (codePoint >= 0x7F && codePoint < 0xA0)) return 0;
if (codePoint < 0x0300) return 1;
if (codePoint == kZeroWidthJoiner || codePoint == 0x200B || codePoint == 0xFEFF || isExtending(codePoint)) return 0;
return inRanges(kWide, codePoint) ? 2 : 1;
}
char32_t utf8::toLower(char32_t codePoint) {
if (codePoint < 0x80) return codePoint >= 'A' && codePoint <= 'Z' ? codePoint + 32 : codePoint;
if (codePoint >= 0x00C0 && codePoint <= 0x00DE && codePoint != 0x00D7) return codePoint + 32;
if (codePoint == 0x0178) return 0x00FF;
if ((codePoint >= 0x0391 && codePoint <= 0x03A9 && codePoint != 0x03A2) || (codePoint >= 0x0410 && codePoint <= 0x042F))
return codePoint + 32;
if (codePoint >= 0x0400 && codePoint <= 0x040F) return codePoint + 80;
bool upperIsEven = false;
if (isPairedBlock(codePoint, upperIsEven) && ((codePoint & 1) == 0) == upperIsEven) return codePoint + 1;
return codePoint;
}
char32_t utf8::toUpper(char32_t codePoint) {
if (codePoint < 0x80) return codePoint >= 'a' && codePoint <= 'z' ? codePoint - 32 : codePoint;
if (codePoint >= 0x00E0 && codePoint <= 0x00FE && codePoint != 0x00F7) return codePoint - 32;
if (codePoint == 0x00FF) return 0x0178;
if ((codePoint >= 0x03B1 && codePoint <= 0x03C9 && codePoint != 0x03C2) || (codePoint >= 0x0430 && codePoint <= 0x044F))
return codePoint - 32;
if (codePoint >= 0x0450 && codePoint <= 0x045F) return codePoint - 80;
bool upperIsEven = false;
if (isPairedBlock(codePoint, upperIsEven) && ((codePoint & 1) == 0) != upperIsEven) return codePoint - 1;
return codePoint;
}
namespace {
std::string mapped(std::string_view text, char32_t (*map)(char32_t)) {
std::string out;
out.reserve(text.size());
for (size_t position = 0; position < text.size();) {
size_t length = 1;
const char32_t codePoint = utf8::codePointAt(text, position, &length);
// Bytes that do not decode are kept as they are.
if (codePoint == utf8::kReplacement && length == 1) out += text[position];
else utf8::append(out, map(codePoint));
position += length;
}
return out;
}
}
std::string utf8::toLower(std::string_view text) { return mapped(text, &utf8::toLower); }
std::string utf8::toUpper(std::string_view text) { return mapped(text, &utf8::toUpper); }
utf8::CharClass utf8::classify(char32_t codePoint, std::string_view separators) {
if (isWhitespace(codePoint)) return CharClass::Whitespace;
if (codePoint < 0x80) {
return separators.find(char(codePoint)) != std::string_view::npos ? CharClass::Separator : CharClass::Word;
}
return inRanges(kSeparators, codePoint) ? CharClass::Separator : CharClass::Word;
}
namespace {
size_t cellsAfter(size_t visible, char32_t codePoint, size_t tabSize) {
if (codePoint != '\t') return visible + size_t(utf8::displayWidth(codePoint));
return tabSize ? visible + tabSize - visible % tabSize : visible + 1;
}
}
size_t utf8::visibleColumn(std::string_view line, size_t column, size_t tabSize) {
column = std::min(column, line.size());
size_t visible = 0;
for (size_t position = 0; position < column;) {
size_t length = 1;
visible = cellsAfter(visible, codePointAt(line, position, &length), tabSize);
position += length;
}
return visible;
}
size_t utf8::columnAtVisible(std::string_view line, size_t wanted, size_t tabSize) {
size_t visible = 0;
size_t position = 0;
while (position < line.size()) {
const size_t next = nextBoundary(line, position);
size_t after = visible;
for (size_t inside = position; inside < next;) {
size_t length = 1;
after = cellsAfter(after, codePointAt(line, inside, &length), tabSize);
inside += length;
}
if (after > wanted) {
// Land on the nearer edge of the cell that straddles the wanted column.
return wanted - visible < after - wanted ? position : next;
}
visible = after;
position = next;
}
return position;
}