crosspoint-reader/lib/LibraryIndex/LibraryText.cpp

#include "LibraryText.h"

#include <Utf8.h>

#include <algorithm>
#include <array>
#include <cstring>

namespace library {
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));
}

// Articles stripped from the head of sort and search keys. Display text never
// goes through this.
constexpr const char* ARTICLES[] = {"the ", "a ",   "an ", "le ",  "la ",  "les ", "l'",   "un ",
                                    "une ", "de ",  "du ", "des ", "der ", "die ", "das ", "el ",
                                    "los ", "las ", "il ", "lo ",  "gli ", "i ",   "o ",   "os "};

// 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);
  }
}

}  // namespace

std::string fold(const std::string_view text, const bool stripArticle) {
  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 (utf8IsCombiningMark(cp)) continue;  // already-decomposed input

    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;
    }

    // Everything else — punctuation, symbols, unmapped scripts — separates
    // words. Deferring the space keeps runs collapsed and drops trailing ones.
    if (!out.empty()) pendingSpace = true;
  }

  if (stripArticle) {
    for (const char* article : ARTICLES) {
      const size_t len = strlen(article);
      if (out.size() > len && out.compare(0, len, article) == 0) {
        out.erase(0, len);
        break;
      }
    }
  }
  return out;
}

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) {
  // Drop bracketed spans ("George Sand [Sand, George]") and everything after
  // a multi-author separator.
  std::string cleaned;
  cleaned.reserve(author.size());
  int depth = 0;
  for (const char c : author) {
    if (c == '[' || c == '(') {
      depth++;
      continue;
    }
    if (c == ']' || c == ')') {
      if (depth > 0) depth--;
      continue;
    }
    if (c == ';') break;
    if (depth == 0) cleaned.push_back(c);
  }

  const std::string folded = fold(cleaned);

  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 (tokens[i].size() > 1) 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(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 {};

  size_t lastStart = std::string::npos;
  size_t lastEnd = folded.size();
  size_t i = folded.size();
  while (i > 0) {
    i--;
    if (folded[i] != ' ') {
      if (lastStart == std::string::npos) lastEnd = i + 1;
      lastStart = i;
    } else if (lastStart != std::string::npos) {
      break;
    }
  }
  if (lastStart == std::string::npos) return {};

  std::string key;
  key.reserve(folded.size() + 1);
  key.append(folded, lastStart, lastEnd - lastStart);
  // 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.
  if (lastStart > 0) {
    key.push_back(' ');
    key.append(folded, 0, lastStart);
    while (!key.empty() && key.back() == ' ') key.pop_back();
  }
  return key;
}

}  // namespace library