#include "TextSearch.hpp" #include "Utf8.hpp" #include #include 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(); 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& 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& 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 TextSearch::all(const PieceTree& text, Range within, size_t limit) const { std::vector 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 TextSearch::all(const PieceTree& text, size_t limit) const { return all(text, { 0, text.size() }, limit); } std::optional TextSearch::next(const PieceTree& text, size_t from, bool wrap) const { from = std::min(from, text.size()); std::vector 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 TextSearch::previous(const PieceTree& text, size_t from, bool wrap) const { from = std::min(from, text.size()); std::vector 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)); }