Something went wrong. Try again.
A fork of https://github.com/crosspoint-reader/crosspoint-reader
Something went wrong. Try again.
15 kB · 401 lines
C++
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402#include "LibraryText.h"
#include <Utf8.h>
#include <algorithm>
namespace library {
std::string joinLibraryPath(const std::string_view folder, const std::string_view name) { std::string path; path.reserve(folder.size() + name.size() + 1); if (folder.empty()) { path.push_back('/'); } else { path.append(folder); if (folder.back() != '/') path.push_back('/'); } path.append(name); return path;}
namespace {
// Letters with no canonical decomposition, plus the punctuation that would// otherwise become a space and break word shapes. Everything here is a distinct// letter in Unicode, so no amount of NFD gets us the ASCII form.struct CharMap { uint32_t cp; const char* replacement;};constexpr CharMap EXPLICIT_MAP[] = { {0x00D8, "o"}, // Ø {0x00F8, "o"}, // ø — "Søren" folds to "soren", not "nesb" {0x00C6, "ae"}, // Æ {0x00E6, "ae"}, // æ {0x0152, "oe"}, // Œ {0x0153, "oe"}, // œ {0x00DF, "ss"}, // ß {0x0141, "l"}, // Ł {0x0142, "l"}, // ł {0x00D0, "d"}, // Ð {0x00F0, "d"}, // ð {0x0110, "d"}, // Đ {0x0111, "d"}, // đ {0x00DE, "th"}, // Þ {0x00FE, "th"}, // þ {0x0131, "i"}, // ı {0x0027, "'"}, // ' — kept, not turned into a space, so "O'Brien" stays one word {0x2019, "'"}, // ’ — and so the curly form folds to the same thing {0x2018, "'"}, // ‘};
const char* explicitMapping(const uint32_t cp) { for (const auto& e : EXPLICIT_MAP) { if (e.cp == cp) return e.replacement; } return nullptr;}
// Reverse lookup in the NFC table: given a precomposed codepoint, return the// base letter it was composed from, or 0.//// The table is sorted by (base, mark) so this is a linear scan rather than a// binary search. It runs once per non-ASCII character at index-build time and// over a short query per keystroke, never over the whole index, so the scan is// not on any hot path. Reusing the generated table costs no extra flash — it is// already linked for utf8ComposeNfc().// Fully decompose: é -> e, and the rare doubly-accented forms (ế -> ê -> e).uint32_t stripDiacritics(uint32_t cp) { for (int guard = 0; guard < 4; guard++) { const uint32_t base = utf8DecomposedBase(cp); if (base == 0) break; cp = base; } return cp;}
bool isAsciiAlnum(const uint32_t cp) { return (cp >= '0' && cp <= '9') || (cp >= 'a' && cp <= 'z') || (cp >= 'A' && cp <= 'Z');}
void appendLowerAscii(const uint32_t cp, std::string& out) { out.push_back(static_cast<char>(cp >= 'A' && cp <= 'Z' ? cp - 'A' + 'a' : cp));}
struct CodepointRange { uint32_t first; uint32_t last;};
constexpr bool inRanges(const uint32_t cp, const CodepointRange* ranges, const size_t count) { for (size_t i = 0; i < count; i++) { if (cp >= ranges[i].first && cp <= ranges[i].last) return true; } return false;}
// Script coverage follows the SD-font catalog. Keeping the ranges here costs a// few hundred flash bytes; linking libunibreak solely for its general-category// table would add roughly 75 KiB of tables plus the classifier code.constexpr CodepointRange LETTER_RANGES[] = { {0x0041, 0x005A}, {0x0061, 0x007A}, {0x00C0, 0x02AF}, // Latin and IPA {0x0370, 0x03FF}, {0x1F00, 0x1FFF}, // Greek {0x0400, 0x0481}, {0x048A, 0x052F}, // Cyrillic {0x0531, 0x0556}, {0x0560, 0x0588}, // Armenian {0x05D0, 0x05EA}, {0x05EF, 0x05F2}, {0xFB1D, 0xFB4F}, // Hebrew {0x0620, 0x064A}, {0x066E, 0x066F}, {0x0671, 0x06D3}, {0x06D5, 0x06D5}, {0x06E5, 0x06E6}, {0x06EE, 0x06EF}, {0x06FA, 0x06FC}, {0x06FF, 0x06FF}, {0x0750, 0x077F}, {0x08A0, 0x08C9}, {0xFB50, 0xFDF9}, {0xFE70, 0xFEFC}, // Arabic {0x10A0, 0x10C5}, {0x10D0, 0x10FF}, {0x1C90, 0x1CBF}, {0x2D00, 0x2D25}, // Georgian {0x1200, 0x135A}, {0x1380, 0x138F}, {0x2D80, 0x2DDE}, // Ethiopic {0x13A0, 0x13F5}, {0x13F8, 0x13FD}, {0xAB70, 0xABBF}, // Cherokee {0x2D30, 0x2D67}, // Tifinagh {0x3041, 0x3096}, {0x30A1, 0x30FA}, {0x3105, 0x312F}, {0x31A0, 0x31BF}, // Kana/Bopomofo {0x3400, 0x4DBF}, {0x4E00, 0x9FFF}, {0xF900, 0xFAFF}, // Han {0x1100, 0x11FF}, {0x3131, 0x318E}, {0xA960, 0xA97F}, {0xAC00, 0xD7FF}, // Hangul {0x20000, 0x2EBEF}, {0x2F800, 0x2FA1F}, {0x30000, 0x323AF}, // Han extensions};
constexpr CodepointRange NUMBER_RANGES[] = { {0x0030, 0x0039}, {0x0660, 0x0669}, {0x06F0, 0x06F9}, {0x0966, 0x096F}, {0xFF10, 0xFF19},};
constexpr CodepointRange MARK_RANGES[] = { {0x0483, 0x0489}, {0x0591, 0x05BD}, {0x05BF, 0x05BF}, {0x05C1, 0x05C2}, {0x05C4, 0x05C5}, {0x05C7, 0x05C7}, {0x0610, 0x061A}, {0x064B, 0x065F}, {0x0670, 0x0670}, {0x06D6, 0x06DC}, {0x06DF, 0x06E4}, {0x06E7, 0x06E8}, {0x06EA, 0x06ED}, {0x08D3, 0x08FF}, {0xFB1E, 0xFB1E},};
bool isUnicodeNumber(const uint32_t cp) { return inRanges(cp, NUMBER_RANGES, sizeof(NUMBER_RANGES) / sizeof(NUMBER_RANGES[0]));}
bool isUnicodeMark(const uint32_t cp) { return utf8IsCombiningMark(cp) || inRanges(cp, MARK_RANGES, sizeof(MARK_RANGES) / sizeof(MARK_RANGES[0]));}
bool isUnicodeLetter(const uint32_t cp) { if (isUnicodeMark(cp) || isUnicodeNumber(cp) || cp == 0x00D7 || cp == 0x00F7 || cp == 0x0374 || cp == 0x0375 || cp == 0x037E || cp == 0x0387 || cp == 0x03F6) return false; return inRanges(cp, LETTER_RANGES, sizeof(LETTER_RANGES) / sizeof(LETTER_RANGES[0]));}
// Views into `folded`, not copies: the caller keeps that string alive for as// long as the tokens, and a std::string per token costs an allocation each plus// 24 bytes of stack apiece -- 288 B for the twelve, over the 256 B this repo// asks callers to justify.void splitTokens(std::string_view folded, std::string_view* out, size_t maxTokens, size_t& count) { count = 0; size_t i = 0; while (i < folded.size() && count < maxTokens) { while (i < folded.size() && folded[i] == ' ') i++; const size_t start = i; while (i < folded.size() && folded[i] != ' ') i++; if (i > start) out[count++] = folded.substr(start, i - start); }}
bool isSingleCodepoint(const std::string_view text) { if (text.empty()) return false; const auto* cursor = reinterpret_cast<const unsigned char*>(text.data()); utf8NextCodepoint(&cursor); return cursor == reinterpret_cast<const unsigned char*>(text.data() + text.size());}
} // namespace
std::string fold(const std::string_view text) { std::string out; out.reserve(text.size());
const auto* cursor = reinterpret_cast<const unsigned char*>(text.data()); const auto* end = cursor + text.size(); bool pendingSpace = false;
while (cursor < end) { // The shared decoder stops on NUL and every std::string source is // NUL-terminated, but fold's contract is string_view — and a view may end // mid-sequence. Refuse to decode a lead byte whose continuation bytes lie // past the end rather than trusting whatever sits there. const unsigned char lead = *cursor; const ptrdiff_t promised = lead < 0x80 ? 1 : (lead >> 5) == 0x06 ? 2 : (lead >> 4) == 0x0E ? 3 : (lead >> 3) == 0x1E ? 4 : 1; if (promised > end - cursor) break; const uint32_t cp = utf8NextCodepoint(&cursor); if (cp == 0) break;
if (isUnicodeMark(cp)) continue;
const char* mapped = explicitMapping(cp); if (mapped != nullptr) { if (pendingSpace && !out.empty()) out.push_back(' '); pendingSpace = false; out.append(mapped); continue; }
const uint32_t base = stripDiacritics(cp); if (isAsciiAlnum(base)) { if (pendingSpace && !out.empty()) out.push_back(' '); pendingSpace = false; appendLowerAscii(base, out); continue; }
if (base >= 0x80 && (isUnicodeLetter(base) || isUnicodeNumber(base))) { if (pendingSpace && !out.empty()) out.push_back(' '); pendingSpace = false; utf8AppendCodepoint(base, out); continue; }
// Everything else — punctuation, symbols, unmapped scripts — separates // words. Deferring the space keeps runs collapsed and drops trailing ones. if (!out.empty()) pendingSpace = true; }
return out;}
uint32_t foldedGroupInitial(const std::string_view folded) { if (folded.empty()) return 0; const auto* cursor = reinterpret_cast<const unsigned char*>(folded.data()); const uint32_t cp = utf8NextCodepoint(&cursor); return isUnicodeLetter(cp) ? cp : 0;}
std::string cleanPersonName(const std::string_view author) { std::string out; out.reserve(author.size()); int depth = 0; for (size_t i = 0; i < author.size(); i++) { const char c = author[i]; if (c == '[' || c == '(') { depth++; continue; } if (c == ']' || c == ')') { if (depth > 0) depth--; continue; } if (c == ';') break; // secondary authors if (depth > 0) continue; if (c == '_') { // "Herbert G_ Wells" — the underscore stands in for a full stop the // filesystem would not take. Between letters it is an abbreviation dot; // at the end of a word it is just noise. const bool betweenLetters = i > 0 && i + 1 < author.size() && isalpha(static_cast<unsigned char>(author[i - 1])) && isalpha(static_cast<unsigned char>(author[i + 1])); out.push_back(betweenLetters ? '.' : ' '); continue; } out.push_back(c); }
while (!out.empty() && (out.back() == ' ' || out.back() == ',' || out.back() == '-' || out.back() == '.' || out.back() == '_')) { out.pop_back(); } size_t start = 0; while (start < out.size() && out[start] == ' ') start++; out.erase(0, start);
// Collapse the space runs left behind by the removals. std::string collapsed; collapsed.reserve(out.size()); bool space = false; for (const char c : out) { if (c == ' ') { space = true; continue; } if (space && !collapsed.empty()) collapsed.push_back(' '); space = false; collapsed.push_back(c); }
// "Austen, Jane" is the same person as "Jane Austen", and publishers use both. // The spelling vote cannot settle it — with one book per author there is no // majority — so the inverted form is turned round here instead. Only a single // comma qualifies: "Smith, John, Jr." and lists of several authors are left // exactly as they are rather than being scrambled. const size_t comma = collapsed.find(','); if (comma != std::string::npos && collapsed.find(',', comma + 1) == std::string::npos) { std::string_view last(collapsed.data(), comma); std::string_view first(collapsed.data() + comma + 1, collapsed.size() - comma - 1); while (!first.empty() && first.front() == ' ') first.remove_prefix(1); while (!last.empty() && last.back() == ' ') last.remove_suffix(1); if (!first.empty() && !last.empty()) { std::string swapped; swapped.reserve(collapsed.size()); swapped.append(first); swapped.push_back(' '); swapped.append(last); return swapped; } } return collapsed;}
std::string authorKey(const std::string_view author) { // The same cleanup the display name gets: bracketed spans dropped // ("George Sand [Sand, George]") and everything after a multi-author // separator cut. cleanPersonName also turns "Austen, Jane" round, which makes // no difference here — the tokens are sorted below, so word order is already // irrelevant to the key. const std::string folded = fold(cleanPersonName(author));
constexpr size_t MAX_TOKENS = 12; std::string_view tokens[MAX_TOKENS]; size_t count = 0; splitTokens(folded, tokens, MAX_TOKENS, count);
// Initials carry no identity and appear inconsistently ("Herbert G Wells" vs // "Herbert Wells"), so they must not change the key. size_t kept = 0; for (size_t i = 0; i < count; i++) { if (!isSingleCodepoint(tokens[i])) tokens[kept++] = tokens[i]; } std::sort(tokens, tokens + kept);
std::string key; for (size_t i = 0; i < kept; i++) { if (!key.empty()) key.push_back(' '); key.append(tokens[i]); } // Truncate on bytes, not on a token boundary. Sorting puts a short forename // first, so a whole-token cut would reduce "Wollstonecraft, Mary" to the key // "alex" and merge every Alex in the library; the byte cut keeps // "mary wollsto", which stays a prefix of the full key and discriminates. if (key.size() > AUTHOR_KEY_MAX_BYTES) { key.resize(static_cast<size_t>(utf8SafeTruncateBuffer(key.data(), AUTHOR_KEY_MAX_BYTES))); } while (!key.empty() && key.back() == ' ') key.pop_back(); return key;}
// fold() keeps the apostrophe, which is right for sorting — "L'Eneide" belongs// under L. For searching it is wrong: in French the word worth typing is the one// AFTER the apostrophe, so "eneide" must reach "L'Eneide" and "cote" must// reach "d'a cote". Treating it as a word boundary here leaves the sort untouched.bool isWordBreak(const char c) { return c == ' ' || c == '\''; }
bool matchesQuery(const std::string_view haystack, const std::string_view needle) { if (needle.empty()) return true;
// Walk the query one word at a time, and for each one scan the book's words for // a prefix hit. Both strings are at most a couple of hundred bytes and this // runs once per book per keypress, so a plain scan is cheaper than anything // that would need building first. size_t qs = 0; while (qs < needle.size()) { while (qs < needle.size() && isWordBreak(needle[qs])) qs++; if (qs >= needle.size()) break; size_t qe = qs; while (qe < needle.size() && !isWordBreak(needle[qe])) qe++; const std::string_view word = needle.substr(qs, qe - qs);
bool found = false; size_t hs = 0; while (hs < haystack.size() && !found) { while (hs < haystack.size() && isWordBreak(haystack[hs])) hs++; if (hs >= haystack.size()) break; if (haystack.compare(hs, word.size(), word) == 0) { found = true; break; } while (hs < haystack.size() && !isWordBreak(haystack[hs])) hs++; } if (!found) return false; qs = qe; } return true;}
std::string surnameKey(const std::string_view displayAuthor) { const std::string folded = fold(displayAuthor); if (folded.empty()) return {};
// fold() defers its spaces, so the result has no leading, trailing or repeated // space. The last one is therefore the separator before the surname, and a name // with no space at all is its own key. const size_t sep = folded.rfind(' '); if (sep == std::string::npos) return folded;
std::string key; key.reserve(folded.size()); key.append(folded.substr(sep + 1)); // The given names follow, so two people sharing a surname stay in a stable, // readable order rather than whichever the disk walk happened to produce. key.push_back(' '); key.append(folded.substr(0, sep)); return key;}
} // namespace library