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

178 lines
6.4 KiB
C++

#include "TextSearch.hpp"
#include "Utf8.hpp"
#include <algorithm>
#include <regex>
using namespace tp;
using namespace tp::text;
struct TextSearch::Regex {
std::regex expression;
};
TextSearch::~TextSearch() = default;
TextSearch::TextSearch(TextSearch&&) noexcept = default;
TextSearch& TextSearch::operator=(TextSearch&&) noexcept = default;
TextSearch::TextSearch(std::string_view query, SearchOptions options) :
mOptions(std::move(options)) {
if (mOptions.wordSeparators.empty()) mOptions.wordSeparators = utf8::kDefaultWordSeparators;
if (query.empty()) return;
if (mOptions.regex) {
auto flags = std::regex::ECMAScript | std::regex::optimize;
if (!mOptions.caseSensitive) flags |= std::regex::icase;
try {
mRegex = std::make_unique<Regex>();
mRegex->expression.assign(query.begin(), query.end(), flags);
mMultiline = query.find("\\n") != std::string_view::npos || query.find('\n') != std::string_view::npos;
mValid = true;
} catch (const std::regex_error& failure) {
mRegex.reset();
mError = failure.what();
}
return;
}
// Case folding keeps byte lengths (see utf8::toLower), so folded offsets are the document's offsets.
mNeedle = mOptions.caseSensitive ? std::string(query) : utf8::toLower(query);
mFailure.assign(mNeedle.size(), 0);
for (size_t index = 1, matched = 0; index < mNeedle.size(); index++) {
while (matched > 0 && mNeedle[index] != mNeedle[matched])
matched = mFailure[matched - 1];
if (mNeedle[index] == mNeedle[matched]) matched++;
mFailure[index] = matched;
}
mValid = true;
}
bool TextSearch::isWholeWord(const PieceTree& text, Range match) const {
if (match.empty()) return false;
const auto classAt = [&](size_t offset) { return utf8::classify(utf8::codePointAt(text, offset), mOptions.wordSeparators); };
const auto word = utf8::CharClass::Word;
// An edge is a word boundary unless a word character sits on both sides of it.
if (match.start > 0) {
const size_t before = utf8::previousCodePoint(text, match.start);
if (classAt(before) == word && classAt(match.start) == word) return false;
}
if (match.end < text.size()) {
const size_t last = utf8::previousCodePoint(text, match.end);
if (classAt(last) == word && classAt(match.end) == word) return false;
}
return true;
}
void TextSearch::scanLiteral(const PieceTree& text, Range within, size_t limit, std::vector<Range>& out) const {
const size_t length = mNeedle.size();
size_t matched = 0;
size_t lastEnd = within.start;
const auto feed = [&](char byte, size_t offset) {
while (matched > 0 && byte != mNeedle[matched])
matched = mFailure[matched - 1];
if (byte == mNeedle[matched]) matched++;
if (matched < length) return;
const Range match{ offset + 1 - length, offset + 1 };
matched = mFailure[matched - 1];
// Matches never overlap: after one is taken the next may only start where it ended.
if (match.start < lastEnd) return;
if (mOptions.wholeWord && !isWholeWord(text, match)) return;
out.push_back(match);
lastEnd = match.end;
};
size_t offset = within.start;
while (offset < within.end && out.size() < limit) {
if (mOptions.caseSensitive) {
feed(text.at(offset), offset);
offset++;
continue;
}
size_t sequence = 1;
const char32_t codePoint = utf8::codePointAt(text, offset, &sequence);
if (sequence == 1) {
const char byte = text.at(offset);
feed(byte >= 'A' && byte <= 'Z' ? char(byte + 32) : byte, offset);
} else {
const std::string folded = utf8::encode(utf8::toLower(codePoint));
for (size_t index = 0; index < sequence && out.size() < limit; index++)
feed(index < folded.size() ? folded[index] : text.at(offset + index), offset + index);
}
offset += sequence;
}
}
void TextSearch::scanRegex(const PieceTree& text, Range within, size_t limit, std::vector<Range>& out) const {
const auto scan = [&](const std::string& subject, size_t base) {
auto flags = std::regex_constants::match_default;
for (std::sregex_iterator match(subject.begin(), subject.end(), mRegex->expression, flags), end; match != end; ++match) {
if (out.size() >= limit) return;
const Range found{ base + size_t(match->position()), base + size_t(match->position() + match->length()) };
// An empty match selects nothing and would never let "find next" advance.
if (found.empty()) continue;
if (mOptions.wholeWord && !isWholeWord(text, found)) continue;
out.push_back(found);
}
};
if (mMultiline) {
scan(text.substr(within.start, within.length()), within.start);
return;
}
const size_t lastLine = text.lineOf(within.end);
for (size_t line = text.lineOf(within.start); line <= lastLine && out.size() < limit; line++) {
const size_t start = std::max(text.lineStart(line), within.start);
const size_t end = std::min(text.lineEnd(line), within.end);
if (end > start) scan(text.substr(start, end - start), start);
}
}
std::vector<Range> TextSearch::all(const PieceTree& text, Range within, size_t limit) const {
std::vector<Range> out;
if (!mValid || !limit) return out;
within.end = std::min(within.end, text.size());
within.start = std::min(within.start, within.end);
if (mRegex) scanRegex(text, within, limit, out);
else scanLiteral(text, within, limit, out);
return out;
}
std::vector<Range> TextSearch::all(const PieceTree& text, size_t limit) const {
return all(text, { 0, text.size() }, limit);
}
std::optional<Range> TextSearch::next(const PieceTree& text, size_t from, bool wrap) const {
from = std::min(from, text.size());
std::vector<Range> found = all(text, { from, text.size() }, 1);
if (found.empty() && wrap && from > 0) {
// A match may start before `from` and reach past it, so the wrapped pass covers the whole text.
found = all(text, { 0, text.size() }, 1);
}
if (found.empty()) return std::nullopt;
return found.front();
}
std::optional<Range> TextSearch::previous(const PieceTree& text, size_t from, bool wrap) const {
from = std::min(from, text.size());
std::vector<Range> found = all(text, { 0, from });
if (found.empty() && wrap) found = all(text, { 0, text.size() });
if (found.empty()) return std::nullopt;
return found.back();
}
std::string TextSearch::replacement(const PieceTree& text, Range match, std::string_view with) const {
if (!mRegex) return std::string(with);
const std::string subject = text.substr(match.start, match.length());
std::smatch groups;
if (!std::regex_match(subject, groups, mRegex->expression)) return std::string(with);
return groups.format(std::string(with));
}