#include "PieceTree.hpp" #include #include 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& sink) const { for (const Part& part : mParts) sink(std::string_view(part.data, part.length)); } // ---------------------- Piece Tree ---------------------- // PieceTree::PieceTree() : mTree(std::make_unique()) {} 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(); mChunks.clear(); mAddChunk = kNoPosition; touched(); if (text.empty()) return; auto chunk = std::make_shared(); 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(); 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 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& 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 bool validateSubtree(const Node* node, const std::vector>& 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(); }