Modules/TextEditor/private/PieceTree.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

421 lines
13 KiB
C++

#include "PieceTree.hpp"
#include <algorithm>
#include <cstring>
using namespace tp;
using namespace tp::text;
namespace {
// Insertions are collected in chunks of at least this many bytes. A chunk never grows past the capacity it
// was created with, so the bytes a snapshot points at stay where they are.
constexpr size_t kAddChunkCapacity = 64 * 1024;
}
// ---------------------- Chunk ---------------------- //
void TextChunk::append(std::string_view text) {
const size_t base = data.size();
data.append(text);
for (size_t index = 0; index < text.size(); index++) {
if (text[index] == '\n') lineStarts.push_back(base + index + 1);
}
}
size_t TextChunk::lineBreaksIn(size_t start, size_t end) const {
// A break at byte b is recorded as b + 1, so the breaks of [start, end) are the entries in (start, end].
const auto from = std::upper_bound(lineStarts.begin(), lineStarts.end(), start);
const auto to = std::upper_bound(from, lineStarts.end(), end);
return size_t(to - from);
}
size_t TextChunk::offsetPastBreak(size_t start, size_t index) const {
const auto from = std::upper_bound(lineStarts.begin(), lineStarts.end(), start);
return *(from + (index - 1));
}
// ---------------------- Piece Key ---------------------- //
PieceKey PieceKey::forOffset(size_t offset) {
PieceKey out;
out.mLookup = offset;
return out;
}
PieceKey PieceKey::forLine(size_t line) {
PieceKey out;
out.mLookup = line;
out.mLookupLine = true;
return out;
}
bool PieceKey::descentRight(const PieceKey& query) const {
if (query.mLookupLine) return query.mLookup > mLeftBreaks + mBreaks;
return query.mLookup >= mLeftLength + mLength;
}
bool PieceKey::exactNode(const PieceKey& query) const {
if (query.mLookupLine) return query.mLookup > mLeftBreaks && query.mLookup <= mLeftBreaks + mBreaks;
return query.mLookup >= mLeftLength && query.mLookup < mLeftLength + mLength;
}
PieceKey PieceKey::keyInRightSubtree(const PieceKey& query) const {
PieceKey out = query;
out.mLookup -= query.mLookupLine ? mLeftBreaks + mBreaks : mLeftLength + mLength;
return out;
}
// ---------------------- Snapshot ---------------------- //
std::string TextSnapshot::text() const {
std::string out;
out.reserve(mSize);
for (const Part& part : mParts)
out.append(part.data, part.length);
return out;
}
void TextSnapshot::read(const std::function<void(std::string_view)>& sink) const {
for (const Part& part : mParts)
sink(std::string_view(part.data, part.length));
}
// ---------------------- Piece Tree ---------------------- //
PieceTree::PieceTree() :
mTree(std::make_unique<Tree>()) {}
PieceTree::PieceTree(std::string text) :
PieceTree() {
assign(std::move(text));
}
PieceTree::~PieceTree() = default;
PieceTree::PieceTree(PieceTree&&) noexcept = default;
PieceTree& PieceTree::operator=(PieceTree&&) noexcept = default;
void PieceTree::assign(std::string text) {
mTree = std::make_unique<Tree>();
mChunks.clear();
mAddChunk = kNoPosition;
touched();
if (text.empty()) return;
auto chunk = std::make_shared<TextChunk>();
const size_t length = text.size();
chunk->data = std::move(text);
for (size_t index = 0; index < length; index++) {
if (chunk->data[index] == '\n') chunk->lineStarts.push_back(index + 1);
}
mChunks.push_back(std::move(chunk));
mTree->insertAfter(nullptr, PieceKey(), makePiece(0, 0, length));
}
size_t PieceTree::size() const { return mTree->head() ? mTree->head()->key.subtreeLength() : 0; }
size_t PieceTree::lineCount() const { return (mTree->head() ? mTree->head()->key.subtreeBreaks() : 0) + 1; }
size_t PieceTree::pieceCount() const { return mTree->size(); }
size_t PieceTree::storedBytes() const {
size_t bytes = 0;
for (const auto& chunk : mChunks)
bytes += chunk->data.size();
return bytes;
}
void PieceTree::touched() { mCache = {}; }
auto PieceTree::first() const -> Node* { return mTree->minNode(mTree->head()); }
auto PieceTree::last() const -> Node* { return mTree->maxNode(mTree->head()); }
const char* PieceTree::pieceData(const Piece& piece) const { return mChunks[piece.chunk]->data.data() + piece.start; }
Piece PieceTree::makePiece(size_t chunk, size_t start, size_t length) const {
return { chunk, start, length, mChunks[chunk]->lineBreaksIn(start, start + length) };
}
auto PieceTree::locate(Node* node) const -> Located {
Located out{ node, node->key.leftLength(), node->key.leftBreaks() };
for (const Node* iter = node; iter->mParent; iter = iter->mParent) {
const Node* parent = iter->mParent;
if (parent->mRight != iter) continue;
out.start += parent->key.leftLength() + parent->key.length();
out.breaksBefore += parent->key.leftBreaks() + parent->key.breaks();
}
return out;
}
auto PieceTree::locateOffset(size_t offset) const -> Located {
return locate(mTree->find(PieceKey::forOffset(offset)));
}
void PieceTree::setPiece(Node* node, size_t start, size_t length) {
node->data = makePiece(node->data.chunk, start, length);
mTree->refreshNode(node);
}
Piece PieceTree::appendToAddChunk(std::string_view text) {
const bool fits = mAddChunk != kNoPosition &&
mChunks[mAddChunk]->data.capacity() - mChunks[mAddChunk]->data.size() >= text.size();
if (!fits) {
auto chunk = std::make_shared<TextChunk>();
chunk->data.reserve(std::max(kAddChunkCapacity, text.size()));
mAddChunk = mChunks.size();
mChunks.push_back(std::move(chunk));
}
TextChunk& chunk = *mChunks[mAddChunk];
const size_t start = chunk.data.size();
chunk.append(text);
return makePiece(mAddChunk, start, text.size());
}
bool PieceTree::mergeWithNext(Node* left) {
Node* right = left ? mTree->next(left) : nullptr;
if (!right) return false;
const Piece& a = left->data;
const Piece& b = right->data;
if (a.chunk != b.chunk || a.start + a.length != b.start) return false;
const size_t length = a.length + b.length;
mTree->removeNode(right);
setPiece(left, left->data.start, length);
return true;
}
void PieceTree::insert(size_t offset, std::string_view text) {
if (text.empty()) return;
touched();
const size_t total = size();
offset = std::min(offset, total);
const Piece added = appendToAddChunk(text);
if (!mTree->head()) {
mTree->insertAfter(nullptr, PieceKey(), added);
return;
}
// The piece the new text follows, and how far into it. Text typed in sequence lands right after the piece
// that holds the previous keystroke, which then only grows.
Node* before = nullptr;
if (offset == total) {
before = last();
} else {
const Located at = locateOffset(offset);
const size_t within = offset - at.start;
if (within == 0) {
before = mTree->prev(at.node);
} else {
const Piece whole = at.node->data;
setPiece(at.node, whole.start, within);
mTree->insertAfter(at.node, PieceKey(), makePiece(whole.chunk, whole.start + within, whole.length - within));
before = at.node;
}
}
if (before && before->data.chunk == added.chunk && before->data.start + before->data.length == added.start) {
setPiece(before, before->data.start, before->data.length + added.length);
return;
}
mTree->insertAfter(before, PieceKey(), added);
}
void PieceTree::erase(size_t offset, size_t length) {
const size_t total = size();
if (offset >= total) return;
length = std::min(length, total - offset);
if (!length) return;
touched();
const Located at = locateOffset(offset);
const size_t within = offset - at.start;
const Piece whole = at.node->data;
// Inside one piece with text left on both sides: the piece splits around the hole.
if (within > 0 && within + length < whole.length) {
setPiece(at.node, whole.start, within);
const size_t resume = within + length;
mTree->insertAfter(at.node, PieceKey(), makePiece(whole.chunk, whole.start + resume, whole.length - resume));
return;
}
// Otherwise the range covers the tail of the first piece (possibly all of it), any number of whole
// pieces, and the head of the last one.
std::vector<Node*> emptied;
Node* node = at.node;
size_t remaining = length;
Node* keptBefore = nullptr;
if (within > 0) {
remaining -= whole.length - within;
keptBefore = node;
node = mTree->next(node);
setPiece(at.node, whole.start, within);
} else {
keptBefore = mTree->prev(node);
}
while (remaining > 0 && node) {
const Piece piece = node->data;
if (piece.length <= remaining) {
remaining -= piece.length;
emptied.push_back(node);
node = mTree->next(node);
continue;
}
setPiece(node, piece.start + remaining, piece.length - remaining);
remaining = 0;
}
for (Node* gone : emptied)
mTree->removeNode(gone);
// Erasing what was inserted between two halves of one run leaves them adjacent again.
if (keptBefore) mergeWithNext(keptBefore);
}
void PieceTree::replace(size_t offset, size_t length, std::string_view text) {
erase(offset, length);
insert(std::min(offset, size()), text);
}
char PieceTree::at(size_t offset) const {
if (offset >= mCache.start && offset < mCache.end) return mCache.data[offset - mCache.start];
if (offset >= size()) return '\0';
const Located found = locateOffset(offset);
mCache = { pieceData(found.node->data), found.start, found.start + found.node->data.length };
return mCache.data[offset - mCache.start];
}
void PieceTree::read(size_t offset, size_t length, const std::function<void(std::string_view)>& sink) const {
const size_t total = size();
if (offset >= total) return;
length = std::min(length, total - offset);
if (!length) return;
const Located found = locateOffset(offset);
size_t skip = offset - found.start;
for (Node* node = found.node; node && length; node = mTree->next(node)) {
const size_t count = std::min(length, node->data.length - skip);
sink(std::string_view(pieceData(node->data) + skip, count));
length -= count;
skip = 0;
}
}
std::string PieceTree::substr(size_t offset, size_t length) const {
const size_t total = size();
std::string out;
if (offset >= total) return out;
out.reserve(std::min(length, total - offset));
read(offset, length, [&out](std::string_view run) { out.append(run); });
return out;
}
size_t PieceTree::lineStart(size_t line) const {
if (line == 0) return 0;
if (line >= lineCount()) return size();
const Located found = locate(mTree->find(PieceKey::forLine(line)));
const Piece& piece = found.node->data;
const size_t past = mChunks[piece.chunk]->offsetPastBreak(piece.start, line - found.breaksBefore);
return found.start + (past - piece.start);
}
size_t PieceTree::lineEnd(size_t line) const {
if (line + 1 >= lineCount()) return size();
return lineStart(line + 1) - 1;
}
size_t PieceTree::lineOf(size_t offset) const {
if (offset >= size()) return lineCount() - 1;
const Located found = locateOffset(offset);
const Piece& piece = found.node->data;
return found.breaksBefore + mChunks[piece.chunk]->lineBreaksIn(piece.start, piece.start + (offset - found.start));
}
Position PieceTree::positionAt(size_t offset) const {
offset = std::min(offset, size());
const size_t line = lineOf(offset);
return { line, offset - lineStart(line) };
}
size_t PieceTree::offsetAt(Position position) const {
if (position.line >= lineCount()) return size();
const size_t start = lineStart(position.line);
return std::min(start + position.column, lineEnd(position.line));
}
std::string PieceTree::line(size_t line) const {
const size_t start = lineStart(line);
return substr(start, lineEnd(line) - start);
}
TextSnapshot PieceTree::snapshot() const {
TextSnapshot out;
out.mChunks.assign(mChunks.begin(), mChunks.end());
out.mParts.reserve(pieceCount());
for (Node* node = first(); node; node = mTree->next(node)) {
out.mParts.push_back({ pieceData(node->data), node->data.length });
out.mSize += node->data.length;
}
return out;
}
void PieceTree::compact() {
if (pieceCount() <= 1 && storedBytes() == size()) return;
assign(text());
}
namespace {
template <typename Node>
bool validateSubtree(const Node* node, const std::vector<std::shared_ptr<TextChunk>>& chunks, long& height) {
// Leaves hang off a shared sentinel whose height is -1 and whose key is all zeros.
if (node->mHeight < 0) {
height = -1;
return node->key.subtreeLength() == 0 && node->key.subtreeBreaks() == 0;
}
long left = 0;
long right = 0;
if (!validateSubtree(node->mLeft, chunks, left) || !validateSubtree(node->mRight, chunks, right)) return false;
height = 1 + std::max(left, right);
const Piece& piece = node->data;
const bool balanced = left - right <= 1 && right - left <= 1 && node->mHeight == height;
const bool stored = piece.length > 0 && piece.chunk < chunks.size() &&
piece.start + piece.length <= chunks[piece.chunk]->data.size();
if (!balanced || !stored) return false;
const TextChunk& chunk = *chunks[piece.chunk];
size_t breaks = 0;
for (size_t index = 0; index < piece.length; index++)
breaks += chunk.data[piece.start + index] == '\n';
return piece.lineBreaks == breaks && node->key.length() == piece.length && node->key.breaks() == breaks &&
node->key.leftLength() == node->mLeft->key.subtreeLength() &&
node->key.leftBreaks() == node->mLeft->key.subtreeBreaks() &&
node->key.subtreeLength() ==
node->mLeft->key.subtreeLength() + piece.length + node->mRight->key.subtreeLength() &&
node->key.subtreeBreaks() == node->mLeft->key.subtreeBreaks() + breaks + node->mRight->key.subtreeBreaks();
}
}
bool PieceTree::validate() const {
if (!mTree->head()) return mTree->size() == 0;
long height = 0;
if (mTree->head()->mParent || !validateSubtree(mTree->head(), mChunks, height)) return false;
size_t pieces = 0;
for (Node* node = first(); node; node = mTree->next(node))
pieces++;
return pieces == mTree->size();
}