Repository Public
1// SP Notes Core2// File: Sources/SPNotesFeatures/Command/FuzzyMatch.swift3// Description: Fuzzy search of the command centre. A port of the web one (`src/lib/client/commands.ts` of the web app:4// `fuzzyMatch`, `fuzzyRank`, `pushRecent`, `recencyBoost`) with the same scoring rules, so that the same5// query ranks the same way on every platform: exact 1000, prefix 800 + coverage, substring 600 (+ 80 on6// a word boundary, − position), multi-word order-free, otherwise a subsequence scored per character7// (+16 word boundary, +10 consecutive, +2 else, gap and length penalties). Accent- and case-insensitive.8// Difference with the web: positions count Characters (grapheme clusters), not UTF-16 units.9//10// Author: Simon-Pierre Boucher11// Contact: contact@spboucher.ai12import Foundation1314public struct FuzzyMatch: Equatable, Sendable {15 /// Higher is better.16 public var score: Int17 /// Indexes (in Characters) of the matched characters of the text, ascending — for highlighting.18 public var positions: [Int]19}2021public struct FuzzyRanked<Item> {22 public var item: Item23 public var score: Int24 public var positions: [Int]25}2627extension FuzzyRanked: Sendable where Item: Sendable {}2829public enum Fuzzy {30 /// One folded character per original Character: lower-cased, without diacritics (é → e, Ç → c).31 static func fold(_ text: String) -> [Character] {32 text.map { character in33 let folded = String(character).folding(options: [.diacriticInsensitive, .caseInsensitive, .widthInsensitive], locale: nil)34 return folded.first ?? character35 }36 }3738 private static let separators: Set<Character> = [" ", "\t", "\n", "-", "_", "/", ".", ":", "·", "›", "("]3940 /// A character starts a word: first of the text, after a separator, or an upper-case letter after a lower-case one.41 static func isBoundary(_ text: [Character], _ index: Int) -> Bool {42 if index == 0 { return true }43 let previous = text[index - 1], current = text[index]44 if previous.isWhitespace || separators.contains(previous) { return true }45 return String(previous) == String(previous).lowercased() && String(current) != String(current).lowercased()46 }4748 /// Subsequence match of `query` in `text`; nil when `query` is not one. An empty query matches with score 0.49 public static func match(_ query: String, _ text: String) -> FuzzyMatch? {50 let q = fold(query.trimmingCharacters(in: .whitespacesAndNewlines))51 if q.isEmpty { return FuzzyMatch(score: 0, positions: []) }52 return match(folded: q, original: Array(text))53 }5455 private static func match(folded q: [Character], original: [Character]) -> FuzzyMatch? {56 let t = fold(String(original))57 guard !t.isEmpty, t.count == original.count else { return t.isEmpty ? nil : matchCore(q, t, t) }58 return matchCore(q, t, original)59 }6061 private static func matchCore(_ q: [Character], _ t: [Character], _ original: [Character]) -> FuzzyMatch? {62 if t == q { return FuzzyMatch(score: 1000, positions: Array(0..<q.count)) }63 if let at = firstIndex(of: q, in: t) {64 if at == 0 { return FuzzyMatch(score: 800 + Int((Double(q.count) / Double(t.count) * 100).rounded()), positions: Array(0..<q.count)) }65 return FuzzyMatch(score: 600 + (isBoundary(original, at) ? 80 : 0) - min(40, at), positions: Array(at..<(at + q.count)))66 }67 // Multi-word queries: every word must match somewhere, in any order ("dark mode" ~ "mode sombre dark").68 let words = q.split(whereSeparator: { $0.isWhitespace }).map(Array.init)69 if words.count > 1 {70 var score = 071 var positions = Set<Int>()72 for word in words {73 guard let found = matchCore(word, t, original) else { return nil }74 score += found.score75 positions.formUnion(found.positions)76 }77 return FuzzyMatch(score: Int((Double(score) / Double(words.count)).rounded()) - 20, positions: positions.sorted())78 }79 var score = 0, ti = 0, last = -280 var positions: [Int] = []81 for qi in 0..<q.count {82 var found = -183 // Prefer a word-boundary occurrence of this character if one exists ahead, else the next occurrence.84 var k = ti85 while k < t.count {86 if t[k] == q[qi] {87 if found < 0 { found = k }88 if isBoundary(original, k) { found = k; break }89 if k - ti > 24 { break }90 }91 k += 192 }93 guard found >= 0 else { return nil }94 // A boundary jump must not skip characters the rest of the query still needs.95 let nearest = t[ti...].firstIndex(of: q[qi]) ?? found96 if found != nearest, !isSubsequence(q[(qi + 1)...], t[(found + 1)...]) { found = nearest }97 score += isBoundary(original, found) ? 16 : (found == last + 1 ? 10 : 2)98 if last >= 0 { score -= min(6, found - last - 1) }99 positions.append(found)100 last = found101 ti = found + 1102 }103 return FuzzyMatch(score: max(1, score - Int((Double(t.count) / 12).rounded())), positions: positions)104 }105106 private static func firstIndex(of needle: [Character], in haystack: [Character]) -> Int? {107 guard !needle.isEmpty, needle.count <= haystack.count else { return nil }108 for start in 0...(haystack.count - needle.count) where haystack[start] == needle[0] {109 if Array(haystack[start..<(start + needle.count)]) == needle { return start }110 }111 return nil112 }113114 private static func isSubsequence(_ q: ArraySlice<Character>, _ t: ArraySlice<Character>) -> Bool {115 var remaining = q[...]116 for character in t {117 guard let next = remaining.first else { break }118 if character == next { remaining = remaining.dropFirst() }119 }120 return remaining.isEmpty121 }122123 /// Ranks `items` for `query`. The title counts fully; keywords count for 60 % (and give no highlight positions).124 /// `boost` is added to matching items only. Sorted by score, stable for equal scores. Empty query: every item with125 /// its boost as score (so input order when there is no boost).126 public static func rank<Item>(_ query: String, _ items: [Item], title: (Item) -> String, keywords: (Item) -> String? = { _ in nil },127 boost: (Item) -> Int = { _ in 0 }, limit: Int = 50) -> [FuzzyRanked<Item>] {128 let trimmed = query.trimmingCharacters(in: .whitespacesAndNewlines)129 var out: [(ranked: FuzzyRanked<Item>, index: Int)] = []130 for (index, item) in items.enumerated() {131 if trimmed.isEmpty {132 out.append((FuzzyRanked(item: item, score: boost(item), positions: []), index))133 continue134 }135 let a = match(trimmed, title(item))136 let b = keywords(item).flatMap { $0.isEmpty ? nil : match(trimmed, $0) }137 let sa = a?.score ?? -1138 let sb = b.map { Int((Double($0.score) * 0.6).rounded()) } ?? -1139 if sa < 0, sb < 0 { continue }140 out.append((FuzzyRanked(item: item, score: max(sa, sb) + boost(item), positions: sa >= sb ? (a?.positions ?? []) : []), index))141 }142 out.sort { $0.ranked.score != $1.ranked.score ? $0.ranked.score > $1.ranked.score : $0.index < $1.index }143 return out.prefix(max(0, limit)).map(\.ranked)144 }145}146147/// A recently used command or page (device-local).148public struct CommandRecent: Codable, Equatable, Sendable {149 public enum Kind: String, Codable, Sendable { case command, page }150 public var kind: Kind151 public var id: String152 public var title: String?153 public var icon: String?154 public var at: Date155156 public init(kind: Kind, id: String, title: String? = nil, icon: String? = nil, at: Date = Date()) {157 self.kind = kind158 self.id = id159 self.title = title160 self.icon = icon161 self.at = at162 }163}164165public enum CommandRecents {166 public static let maximum = 12167168 /// Most recent first, de-duplicated by kind + id, capped at 12.169 public static func push(_ list: [CommandRecent], _ entry: CommandRecent) -> [CommandRecent] {170 Array(([entry] + list.filter { !($0.kind == entry.kind && $0.id == entry.id) }).prefix(maximum))171 }172173 /// Boost for ranking: the most recent entry gets +40, decreasing by 4 per rank, never under 4; 0 when absent.174 public static func boost(_ list: [CommandRecent], kind: CommandRecent.Kind, id: String) -> Int {175 guard let index = list.firstIndex(where: { $0.kind == kind && $0.id == id }) else { return 0 }176 return max(4, 40 - index * 4)177 }178}179