okf_studio/
search.rs

1//! Fuzzy matching, the omnisearch index, and the shared query syntax.
2//!
3//! One scorer serves omnisearch, the palette's command mode, refactor form
4//! completion, tree type-ahead, and graph filtering. The syntax layer adds
5//! the cheap, composable filters (`#tag`, `type:Policy`, `tier:unverified`,
6//! `is:stale`, `is:broken`) reused by every filterable view.
7
8use okf_core::{ConceptId, Status, TrustTier};
9use std::str::FromStr;
10
11/// One concept's searchable representation, precomputed at snapshot build.
12#[derive(Clone, Debug)]
13pub struct SearchEntry {
14    /// The concept id.
15    pub id: ConceptId,
16    /// Display title.
17    pub title: String,
18    /// One-line description (may be empty).
19    pub description: String,
20    /// Frontmatter tags.
21    pub tags: Vec<String>,
22    /// Body headings, for heading-level hits.
23    pub headings: Vec<String>,
24    /// The concept `type`.
25    pub type_: String,
26    /// Trust tier, for `tier:` filters.
27    pub tier: TrustTier,
28    /// Lifecycle status, for `status:` filters.
29    pub status: Status,
30    /// Whether the concept is stale today, for `is:stale`.
31    pub stale: bool,
32    /// Whether the concept has broken outgoing links, for `is:broken`.
33    pub broken: bool,
34}
35
36/// The precomputed omnisearch index over a snapshot's concepts.
37#[derive(Clone, Debug, Default)]
38pub struct SearchIndex {
39    /// One entry per concept, in bundle order.
40    pub entries: Vec<SearchEntry>,
41}
42
43/// A single omnisearch result.
44#[derive(Clone, Debug)]
45pub struct SearchHit {
46    /// The concept the hit points at.
47    pub id: ConceptId,
48    /// The heading within the concept, when the hit is heading-level.
49    pub heading: Option<String>,
50    /// Fuzzy score (higher is better).
51    pub score: i32,
52    /// Char indices of the query match within [`SearchHit::label`].
53    pub indices: Vec<usize>,
54    /// The text the match was scored against.
55    pub label: String,
56}
57
58/// A structured filter parsed from the shared query syntax.
59#[derive(Clone, Debug, PartialEq, Eq)]
60pub enum Filter {
61    /// `#tag`
62    Tag(String),
63    /// `type:Policy`
64    Type(String),
65    /// `tier:unverified`
66    Tier(TrustTier),
67    /// `status:draft`
68    Status(String),
69    /// `is:stale`
70    Stale,
71    /// `is:broken`
72    Broken,
73}
74
75/// A parsed query: free text plus zero or more filters.
76#[derive(Clone, Debug, Default)]
77pub struct Query {
78    /// The fuzzy free-text part.
79    pub text: String,
80    /// The structured filters.
81    pub filters: Vec<Filter>,
82}
83
84impl Query {
85    /// Parses the shared query syntax: whitespace-separated terms, where
86    /// `#x`, `type:x`, `tier:x`, `status:x`, `is:stale`, and `is:broken`
87    /// become filters and everything else joins the fuzzy text.
88    #[must_use]
89    pub fn parse(raw: &str) -> Self {
90        let mut text_terms: Vec<&str> = Vec::new();
91        let mut filters = Vec::new();
92        for term in raw.split_whitespace() {
93            if let Some(tag) = term.strip_prefix('#') {
94                if !tag.is_empty() {
95                    filters.push(Filter::Tag(tag.to_string()));
96                    continue;
97                }
98            } else if let Some(t) = term.strip_prefix("type:") {
99                filters.push(Filter::Type(t.to_string()));
100                continue;
101            } else if let Some(t) = term.strip_prefix("tier:") {
102                if let Ok(tier) = TrustTier::from_str(t) {
103                    filters.push(Filter::Tier(tier));
104                    continue;
105                }
106            } else if let Some(s) = term.strip_prefix("status:") {
107                filters.push(Filter::Status(s.to_string()));
108                continue;
109            } else if term == "is:stale" {
110                filters.push(Filter::Stale);
111                continue;
112            } else if term == "is:broken" {
113                filters.push(Filter::Broken);
114                continue;
115            }
116            text_terms.push(term);
117        }
118        Self {
119            text: text_terms.join(" "),
120            filters,
121        }
122    }
123
124    /// Whether an entry passes every filter.
125    #[must_use]
126    pub fn matches_filters(&self, entry: &SearchEntry) -> bool {
127        self.filters.iter().all(|f| match f {
128            Filter::Tag(tag) => entry.tags.iter().any(|t| t.eq_ignore_ascii_case(tag)),
129            Filter::Type(t) => entry.type_.eq_ignore_ascii_case(t),
130            Filter::Tier(tier) => entry.tier == *tier,
131            Filter::Status(s) => entry.status.as_str().eq_ignore_ascii_case(s),
132            Filter::Stale => entry.stale,
133            Filter::Broken => entry.broken,
134        })
135    }
136}
137
138impl SearchIndex {
139    /// Runs a query over the index, returning at most `limit` hits, best
140    /// first. An empty free-text query returns every entry passing the
141    /// filters, in index order.
142    #[must_use]
143    pub fn search(&self, raw_query: &str, limit: usize) -> Vec<SearchHit> {
144        let query = Query::parse(raw_query);
145        let mut hits: Vec<SearchHit> = Vec::new();
146        for entry in &self.entries {
147            if !query.matches_filters(entry) {
148                continue;
149            }
150            if query.text.is_empty() {
151                hits.push(SearchHit {
152                    id: entry.id.clone(),
153                    heading: None,
154                    score: 0,
155                    indices: Vec::new(),
156                    label: entry.id.to_string(),
157                });
158                continue;
159            }
160            // Concept-level hit: best score across id, title, description,
161            // and tags.
162            let id_str = entry.id.to_string();
163            let mut best: Option<SearchHit> = None;
164            let candidates: Vec<&str> = std::iter::once(id_str.as_str())
165                .chain(std::iter::once(entry.title.as_str()))
166                .chain(std::iter::once(entry.description.as_str()))
167                .chain(entry.tags.iter().map(String::as_str))
168                .collect();
169            for hay in candidates {
170                if let Some((score, indices)) = fuzzy_match(&query.text, hay)
171                    && best.as_ref().is_none_or(|b| score > b.score)
172                {
173                    best = Some(SearchHit {
174                        id: entry.id.clone(),
175                        heading: None,
176                        score,
177                        indices,
178                        label: hay.to_string(),
179                    });
180                }
181            }
182            if let Some(hit) = best {
183                hits.push(hit);
184            }
185            // Heading-level hits are separate result rows.
186            for heading in &entry.headings {
187                if let Some((score, indices)) = fuzzy_match(&query.text, heading) {
188                    hits.push(SearchHit {
189                        id: entry.id.clone(),
190                        heading: Some(heading.clone()),
191                        // Slightly discounted so the concept row leads.
192                        score: score - 1,
193                        indices,
194                        label: heading.clone(),
195                    });
196                }
197            }
198        }
199        hits.sort_by(|a, b| b.score.cmp(&a.score).then_with(|| a.id.cmp(&b.id)));
200        hits.truncate(limit);
201        hits
202    }
203}
204
205const BONUS_BOUNDARY: i32 = 16;
206const BONUS_CAMEL: i32 = 12;
207const BONUS_CONSECUTIVE: i32 = 8;
208const BONUS_FIRST_CHAR: i32 = 20;
209const PENALTY_GAP_START: i32 = -3;
210const PENALTY_GAP_EXTEND: i32 = -1;
211const MATCH_SCORE: i32 = 16;
212
213/// Scores `query` against `haystack` with a Smith-Waterman-style alignment.
214///
215/// Subsequence match with affine gap penalties, plus bonuses at the start of
216/// the haystack, after `/ _ - . :` separators and whitespace, and at
217/// camelCase boundaries — tuned so `pte` finds `policies/travel_expenses`
218/// via segment initials.
219///
220/// Case-insensitive by default; a query char written in uppercase must match
221/// exactly (smart-case). Returns the score and the matched char indices, or
222/// `None` when `query` is not a subsequence of `haystack`.
223#[must_use]
224pub fn fuzzy_match(query: &str, haystack: &str) -> Option<(i32, Vec<usize>)> {
225    const NEG: i32 = i32::MIN / 4;
226
227    let query_chars: Vec<char> = query.chars().filter(|c| !c.is_whitespace()).collect();
228    let haystack_chars: Vec<char> = haystack.chars().collect();
229    if query_chars.is_empty() {
230        return Some((0, Vec::new()));
231    }
232    if query_chars.len() > haystack_chars.len() {
233        return None;
234    }
235
236    let eq = |qc: char, hc: char| {
237        if qc.is_uppercase() {
238            qc == hc
239        } else {
240            qc.to_lowercase().eq(hc.to_lowercase())
241        }
242    };
243    let bonus_at = |idx: usize| -> i32 {
244        if idx == 0 {
245            return BONUS_FIRST_CHAR;
246        }
247        let prev = haystack_chars[idx - 1];
248        if matches!(prev, '/' | '_' | '-' | '.' | ':') || prev.is_whitespace() {
249            BONUS_BOUNDARY
250        } else if prev.is_lowercase() && haystack_chars[idx].is_uppercase() {
251            BONUS_CAMEL
252        } else {
253            0
254        }
255    };
256
257    let (q_len, h_len) = (query_chars.len(), haystack_chars.len());
258    // dp[i][j]: best score with query_chars[i] aligned at haystack_chars[j]; parent[i][j] is the
259    // position of query_chars[i-1] on that best path.
260    let mut dp = vec![vec![NEG; h_len]; q_len];
261    let mut parent = vec![vec![usize::MAX; h_len]; q_len];
262
263    for (j, &hc) in haystack_chars.iter().enumerate() {
264        if eq(query_chars[0], hc) {
265            // A leading gap is free: matching later in the haystack is not
266            // penalized, only rewarded less when it lacks a boundary bonus.
267            dp[0][j] = MATCH_SCORE + bonus_at(j);
268        }
269    }
270    for i in 1..q_len {
271        // best_prev = max over k <= j-2 of dp[i-1][k] plus the affine gap
272        // cost of the cells between k and the current j; every candidate
273        // decays at the same rate, so a running max suffices.
274        let mut best_prev = NEG;
275        let mut best_prev_j = usize::MAX;
276        for j in i..h_len {
277            if best_prev > NEG {
278                best_prev += PENALTY_GAP_EXTEND;
279            }
280            if j >= 2 && dp[i - 1][j - 2] > NEG {
281                let candidate = dp[i - 1][j - 2] + PENALTY_GAP_START;
282                if candidate > best_prev {
283                    best_prev = candidate;
284                    best_prev_j = j - 2;
285                }
286            }
287            if !eq(query_chars[i], haystack_chars[j]) {
288                continue;
289            }
290            let consecutive = if dp[i - 1][j - 1] > NEG {
291                dp[i - 1][j - 1] + MATCH_SCORE + BONUS_CONSECUTIVE + bonus_at(j)
292            } else {
293                NEG
294            };
295            let gapped = if best_prev > NEG {
296                best_prev + MATCH_SCORE + bonus_at(j)
297            } else {
298                NEG
299            };
300            if consecutive >= gapped {
301                if consecutive > NEG {
302                    dp[i][j] = consecutive;
303                    parent[i][j] = j - 1;
304                }
305            } else {
306                dp[i][j] = gapped;
307                parent[i][j] = best_prev_j;
308            }
309        }
310    }
311
312    let (mut best_j, mut best_score) = (usize::MAX, NEG);
313    for (j, &score) in dp[q_len - 1].iter().enumerate() {
314        if score > best_score {
315            best_score = score;
316            best_j = j;
317        }
318    }
319    if best_j == usize::MAX {
320        return None;
321    }
322    let mut indices = vec![0usize; q_len];
323    let mut cursor = best_j;
324    for i in (0..q_len).rev() {
325        indices[i] = cursor;
326        if i > 0 {
327            cursor = parent[i][cursor];
328        }
329    }
330    Some((best_score, indices))
331}
332
333#[cfg(test)]
334mod tests {
335    use super::*;
336
337    #[test]
338    fn matches_segment_initials() {
339        let (score, idx) = fuzzy_match("pte", "policies/travel_expenses").unwrap();
340        assert!(score > 0);
341        assert_eq!(idx, vec![0, 9, 16]);
342    }
343
344    #[test]
345    fn prefers_boundary_matches() {
346        let (loose, _) = fuzzy_match("te", "notes").unwrap();
347        let (boundary, _) = fuzzy_match("te", "travel_expenses").unwrap();
348        assert!(boundary > loose);
349    }
350
351    #[test]
352    fn non_subsequence_is_none() {
353        assert!(fuzzy_match("xyz", "policies").is_none());
354        assert!(fuzzy_match("aa", "a").is_none());
355    }
356
357    #[test]
358    fn smart_case() {
359        assert!(fuzzy_match("Pol", "policies").is_none());
360        assert!(fuzzy_match("pol", "Policies").is_some());
361    }
362
363    #[test]
364    fn query_syntax_parses_filters() {
365        let q = Query::parse("trav #hr type:Policy tier:unverified is:stale is:broken");
366        assert_eq!(q.text, "trav");
367        assert_eq!(q.filters.len(), 5);
368        assert!(q.filters.contains(&Filter::Tag("hr".into())));
369        assert!(q.filters.contains(&Filter::Type("Policy".into())));
370        assert!(q.filters.contains(&Filter::Tier(TrustTier::Unverified)));
371        assert!(q.filters.contains(&Filter::Stale));
372        assert!(q.filters.contains(&Filter::Broken));
373    }
374}
okf_studio/search.rs

okf_studio/
search.rs
