SPB Git

Repository Public

FuzzyMatch.swift 8.7 KB 179 lines swift

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
Files main
Menu

Theme