notes vault library and CLI (Obsidian-compatible)
git clone https://git.lucas.co/cce-vault.git
src/search.rs (14.5K)
1 //! Finding notes: a fuzzy match on names for the quick switcher, a
2 //! full-text scan for the search pane, and unlinked mentions for the
3 //! backlinks pane.
4 //!
5 //! Full text is a scan of the files, not an index. Reading a few thousand
6 //! notes from the page cache takes tens of milliseconds, spread over the
7 //! machine's cores; a real index (tantivy) is worth its weight only once a
8 //! scan is measurably slow on a real vault.
9
10 use serde::Serialize;
11
12 use crate::index::{par_map, stem, FileKind, Index};
13 use crate::parse;
14
15 #[derive(Debug, Clone, PartialEq, Serialize)]
16 pub struct NameMatch {
17 pub path: String,
18 /// What matched: the note's name, one of its aliases, or its path.
19 pub matched: String,
20 pub score: i64,
21 }
22
23 #[derive(Debug, Clone, PartialEq, Serialize)]
24 pub struct LineHit {
25 pub line: usize,
26 pub text: String,
27 }
28
29 #[derive(Debug, Clone, PartialEq, Serialize)]
30 pub struct FileHits {
31 pub path: String,
32 /// Lines holding a match, capped at [`LINES_PER_FILE`].
33 pub lines: Vec<LineHit>,
34 /// Matching lines in all, including those past the cap.
35 pub total: usize,
36 }
37
38 pub const LINES_PER_FILE: usize = 5;
39
40 /// Subsequence match of `query` in `candidate`, case-insensitive. Scores
41 /// reward consecutive runs, matches at word starts and a match at the very
42 /// start, and slightly penalise long candidates — the ordering a quick
43 /// switcher needs so that `mt` finds "Meeting Topics" before "Mortgage".
44 ///
45 /// The alignment is the best one, not the leftmost: a greedy match would
46 /// spend the `t` of `mt` on "Mee*t*ing" and never see "*T*opics". A small
47 /// dynamic programme over (query char, candidate position) finds it; names
48 /// are short, so O(query × candidate) is nothing.
49 pub fn fuzzy_score(query: &str, candidate: &str) -> Option<i64> {
50 let q: Vec<char> = query.chars().flat_map(char::to_lowercase).filter(|c| !c.is_whitespace()).collect();
51 if q.is_empty() {
52 return Some(0);
53 }
54 let c: Vec<char> = candidate.chars().collect();
55 let lower: Vec<char> = c.iter().map(|ch| ch.to_lowercase().next().unwrap_or(*ch)).collect();
56 let n = c.len();
57 let gain = |j: usize| -> i64 {
58 let word_start = j == 0 || !c[j - 1].is_alphanumeric() || (c[j].is_uppercase() && c[j - 1].is_lowercase());
59 1 + if word_start { 8 } else { 0 } + if j == 0 { 6 } else { 0 }
60 };
61 const NONE: i64 = i64::MIN / 4;
62 // prev[j]: best score with the previous query char matched at j.
63 let mut prev: Vec<i64> = (0..n).map(|j| if lower[j] == q[0] { gain(j) } else { NONE }).collect();
64 for &qc in &q[1..] {
65 let mut cur = vec![NONE; n];
66 let mut best_before = NONE; // max of prev[..j-1]
67 for j in 0..n {
68 if j >= 2 {
69 best_before = best_before.max(prev[j - 2]);
70 }
71 if lower[j] != qc {
72 continue;
73 }
74 let run = if j >= 1 && prev[j - 1] > NONE { prev[j - 1] + 5 } else { NONE };
75 let gap = best_before;
76 let base = run.max(gap);
77 if base > NONE {
78 cur[j] = base + gain(j);
79 }
80 }
81 prev = cur;
82 }
83 let best = prev.into_iter().max().filter(|&s| s > NONE)?;
84 Some(best * 10 - n as i64)
85 }
86
87 /// Terms of a search: words, and `"quoted phrases"` kept whole, lowercased.
88 pub fn terms(query: &str) -> Vec<String> {
89 let mut out = Vec::new();
90 let mut rest = query.trim();
91 while !rest.is_empty() {
92 if let Some(r) = rest.strip_prefix('"') {
93 let end = r.find('"').unwrap_or(r.len());
94 out.push(r[..end].to_lowercase());
95 rest = r.get(end + 1..).unwrap_or("").trim_start();
96 } else {
97 let end = rest.find(char::is_whitespace).unwrap_or(rest.len());
98 out.push(rest[..end].to_lowercase());
99 rest = rest[end..].trim_start();
100 }
101 }
102 out.retain(|t| !t.is_empty());
103 out
104 }
105
106 /// Byte offsets where `needle` (already lowercase) occurs in `hay`,
107 /// case-insensitively, as whole words when `words` is set.
108 fn find_ci(hay: &str, needle: &str, words: bool) -> Vec<usize> {
109 let mut out = Vec::new();
110 if needle.is_empty() {
111 return out;
112 }
113 let first = needle.chars().next().unwrap();
114 for (i, ch) in hay.char_indices() {
115 if ch.to_lowercase().next() != Some(first) {
116 continue;
117 }
118 let mut hay_chars = hay[i..].chars().flat_map(char::to_lowercase);
119 let mut end = i;
120 let mut ok = true;
121 for n in needle.chars() {
122 match hay_chars.next() {
123 Some(h) if h == n => {}
124 _ => {
125 ok = false;
126 break;
127 }
128 }
129 }
130 if !ok {
131 continue;
132 }
133 // Find the byte end: count needle chars through the original.
134 let mut taken = 0;
135 for (j, ch) in hay[i..].char_indices() {
136 if taken >= needle.chars().count() {
137 end = i + j;
138 break;
139 }
140 taken += ch.to_lowercase().count();
141 end = i + j + ch.len_utf8();
142 }
143 if words {
144 let before = hay[..i].chars().next_back();
145 let after = hay[end..].chars().next();
146 if before.is_some_and(char::is_alphanumeric) || after.is_some_and(char::is_alphanumeric) {
147 continue;
148 }
149 }
150 out.push(i);
151 }
152 out
153 }
154
155 impl Index {
156 /// Notes (and other files) whose name, alias or path fuzzy-matches.
157 pub fn find(&self, query: &str, limit: usize) -> Vec<NameMatch> {
158 let mut out: Vec<NameMatch> = Vec::new();
159 for (path, entry) in self.files() {
160 let name = stem(path);
161 let mut best: Option<(i64, String)> = None;
162 let mut consider = |text: &str, bonus: i64| {
163 if let Some(s) = fuzzy_score(query, text) {
164 let s = s + bonus;
165 if best.as_ref().is_none_or(|(b, _)| s > *b) {
166 best = Some((s, text.to_string()));
167 }
168 }
169 };
170 consider(name, 0);
171 if let Some(note) = &entry.note {
172 for alias in parse::aliases(¬e.properties) {
173 consider(&alias, -5);
174 }
175 }
176 // Paths match too, so `proj/meet` narrows by folder, but a name
177 // match beats them.
178 consider(path, -40);
179 // Notes first: an attachment is rarely what a switcher wants.
180 let kind_bonus = if entry.kind == FileKind::Attachment { -30 } else { 0 };
181 if let Some((score, matched)) = best {
182 out.push(NameMatch { path: path.clone(), matched, score: score + kind_bonus });
183 }
184 }
185 out.sort_by(|a, b| b.score.cmp(&a.score).then(a.path.cmp(&b.path)));
186 out.truncate(limit);
187 out
188 }
189
190 /// Notes containing every term of `query`, anywhere in the text or the
191 /// path. Notes whose name holds a term come first, then those with the
192 /// most matching lines.
193 pub fn search(&self, query: &str, limit: usize) -> Vec<FileHits> {
194 let terms = terms(query);
195 if terms.is_empty() {
196 return Vec::new();
197 }
198 let paths: Vec<&str> = self.notes().map(|(p, _)| p).collect();
199 let mut hits = par_map(&paths, |path: &&str| {
200 let text = std::fs::read_to_string(self.abs(path)).ok()?;
201 let lower_text = text.to_lowercase();
202 let lower_path = path.to_lowercase();
203 if !terms.iter().all(|t| lower_text.contains(t.as_str()) || lower_path.contains(t.as_str())) {
204 return None;
205 }
206 let mut lines = Vec::new();
207 let mut total = 0;
208 for (n, line) in text.lines().enumerate() {
209 let l = line.to_lowercase();
210 if terms.iter().any(|t| l.contains(t.as_str())) {
211 total += 1;
212 if lines.len() < LINES_PER_FILE {
213 lines.push(LineHit { line: n, text: line.trim().to_string() });
214 }
215 }
216 }
217 Some(FileHits { path: path.to_string(), lines, total })
218 });
219 let name_hit = |h: &FileHits| {
220 let n = stem(&h.path).to_lowercase();
221 terms.iter().any(|t| n.contains(t.as_str()))
222 };
223 hits.sort_by(|a, b| {
224 name_hit(b).cmp(&name_hit(a)).then(b.total.cmp(&a.total)).then(a.path.cmp(&b.path))
225 });
226 hits.truncate(limit);
227 hits
228 }
229
230 /// Places in other notes that name `path` (by its name or an alias) as
231 /// a whole word, outside any link, code or frontmatter — the "unlinked
232 /// mentions" Obsidian offers to turn into links.
233 pub fn unlinked_mentions(&self, path: &str) -> Vec<FileHits> {
234 let mut names = vec![stem(path).to_lowercase()];
235 if let Some(note) = self.note(path) {
236 names.extend(parse::aliases(¬e.properties).iter().map(|a| a.to_lowercase()));
237 }
238 names.retain(|n| n.chars().count() >= 2);
239 names.sort();
240 names.dedup();
241 if names.is_empty() {
242 return Vec::new();
243 }
244 let paths: Vec<&str> = self.notes().map(|(p, _)| p).filter(|p| *p != path).collect();
245 let mut out = par_map(&paths, |source: &&str| {
246 let text = std::fs::read_to_string(self.abs(source)).ok()?;
247 let lower = text.to_lowercase();
248 if !names.iter().any(|n| lower.contains(n.as_str())) {
249 return None;
250 }
251 // Parse fresh: the spans must match the text just read.
252 let note = parse::parse(&text);
253 let body_start = note.frontmatter.as_ref().map(|r| r.end).unwrap_or(0);
254 let linked = |at: usize| note.links.iter().any(|l| l.span.contains(&at));
255 let lines = parse::LineIndex::new(&text);
256 let code = code_ranges(&text);
257 let mut hit_lines: Vec<usize> = Vec::new();
258 for name in &names {
259 for at in find_ci(&text, name, true) {
260 if at < body_start || linked(at) || code.iter().any(|r| r.contains(&at)) {
261 continue;
262 }
263 hit_lines.push(lines.line_of(at));
264 }
265 }
266 hit_lines.sort();
267 hit_lines.dedup();
268 if hit_lines.is_empty() {
269 return None;
270 }
271 let all: Vec<&str> = text.lines().collect();
272 Some(FileHits {
273 path: source.to_string(),
274 total: hit_lines.len(),
275 lines: hit_lines
276 .iter()
277 .take(LINES_PER_FILE)
278 .map(|&n| LineHit { line: n, text: all.get(n).unwrap_or(&"").trim().to_string() })
279 .collect(),
280 })
281 });
282 out.sort_by(|a, b| a.path.cmp(&b.path));
283 out
284 }
285 }
286
287 /// Code blocks and spans, where a mention is not prose.
288 fn code_ranges(text: &str) -> Vec<std::ops::Range<usize>> {
289 use pulldown_cmark::{Event, Options, Parser, Tag};
290 Parser::new_ext(text, Options::ENABLE_YAML_STYLE_METADATA_BLOCKS)
291 .into_offset_iter()
292 .filter_map(|(e, r)| match e {
293 Event::Start(Tag::CodeBlock(_)) | Event::Code(_) => Some(r),
294 _ => None,
295 })
296 .collect()
297 }
298
299 #[cfg(test)]
300 mod tests {
301 use super::*;
302
303 fn vault(files: &[(&str, &str)]) -> (tempfile::TempDir, Index) {
304 let dir = tempfile::tempdir().unwrap();
305 for (path, text) in files {
306 let p = dir.path().join(path);
307 std::fs::create_dir_all(p.parent().unwrap()).unwrap();
308 std::fs::write(p, text).unwrap();
309 }
310 let index = Index::open(dir.path(), false).unwrap();
311 (dir, index)
312 }
313
314 #[test]
315 fn fuzzy_ordering() {
316 assert!(fuzzy_score("mtg", "Meeting notes").is_some());
317 assert!(fuzzy_score("xyz", "Meeting").is_none());
318 let a = fuzzy_score("mt", "Meeting Topics").unwrap();
319 let b = fuzzy_score("mt", "mortgage").unwrap();
320 assert!(a > b, "{a} {b}");
321 assert!(fuzzy_score("dn", "DailyNotes").unwrap() > fuzzy_score("dn", "Adenine").unwrap());
322 }
323
324 #[test]
325 fn find_names_aliases_paths() {
326 let (_d, ix) = vault(&[
327 ("Meeting Topics.md", ""),
328 ("Mortgage.md", ""),
329 ("people/Robert.md", "---\naliases: [Bob]\n---\n"),
330 ("img/meeting.png", ""),
331 ]);
332 let got: Vec<_> = ix.find("mt", 10).into_iter().map(|m| m.path).collect();
333 assert_eq!(got[0], "Meeting Topics.md");
334 let bob = ix.find("bob", 1);
335 assert_eq!((bob[0].path.as_str(), bob[0].matched.as_str()), ("people/Robert.md", "Bob"));
336 let meet: Vec<_> = ix.find("meeting", 10).into_iter().map(|m| m.path).collect();
337 assert_eq!(meet, ["Meeting Topics.md", "img/meeting.png"]);
338 assert_eq!(ix.find("people/rob", 1)[0].path, "people/Robert.md");
339 }
340
341 #[test]
342 fn full_text() {
343 let (_d, ix) = vault(&[
344 ("a.md", "The quick brown fox\nsecond line\nfox again"),
345 ("b.md", "quick but no animal"),
346 ("Fox facts.md", "nothing quick here"),
347 ]);
348 assert_eq!(terms(r#"quick "brown fox" x"#), ["quick", "brown fox", "x"]);
349 let r = ix.search("quick fox", 10);
350 let paths: Vec<_> = r.iter().map(|h| h.path.as_str()).collect();
351 // A name hit ranks first; b.md lacks "fox".
352 assert_eq!(paths, ["Fox facts.md", "a.md"]);
353 assert_eq!(r[1].total, 2);
354 assert_eq!(r[1].lines[0], LineHit { line: 0, text: "The quick brown fox".into() });
355 assert!(ix.search("\"brown fox\"", 10).len() == 1);
356 assert!(ix.search(" ", 10).is_empty());
357 }
358
359 #[test]
360 fn unlinked() {
361 let (_d, ix) = vault(&[
362 ("Rust.md", "---\naliases: [rustlang]\n---\n"),
363 ("a.md", "---\ntopic: Rust\n---\nI like Rust.\n[[Rust]] is linked\n`Rust` in code\nTrusty is not\n"),
364 ("b.md", "all about RUSTLANG today"),
365 ("c.md", "nothing"),
366 ]);
367 let m = ix.unlinked_mentions("Rust.md");
368 let got: Vec<_> = m.iter().map(|h| (h.path.as_str(), h.lines.iter().map(|l| l.line).collect::<Vec<_>>())).collect();
369 assert_eq!(got, [("a.md", vec![3]), ("b.md", vec![0])]);
370 }
371
372 #[test]
373 fn case_insensitive_offsets() {
374 assert_eq!(find_ci("Straße STRASSE", "straße", true), [0]);
375 assert_eq!(find_ci("ÄRGER ärger", "ärger", true), [0, 7]);
376 assert_eq!(find_ci("arust rust", "rust", true), [6]);
377 }
378 }