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>
178 lines
6.4 KiB
C++
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));
|
|
}
|