1//! Search as OneNote 2010 searches: each query word matches the start of a word, ignoring
2//! case and diacritics; a page matches when all its words appear in its title or text, and
3//! pages whose titles hold every word come first, then the most recently modified.
4
5use crate::document::{TextPosition, descendants};
6use crate::editor::{CanvasEditor, Selection};
7use icu_normalizer::DecomposingNormalizerBorrowed;
8use onestore::ExGuid;
9use onestore::document::Kind;
10use onestore::page::{Page, PageObject, PageParagraph, ParagraphContent, text::Paragraph};
11use std::ops::Range;
12
13/// Characters around a hit a snippet shows before it, and in all.
14const BEFORE: usize = 24;
15const SNIPPET: usize = 90;
16
17/// A query's words, lowered and stripped of diacritics; a quoted phrase is one word.
18#[derive(Clone, Debug, Default, PartialEq)]
19pub struct Query {
20 terms: Vec<String>,
21}
22
23impl Query {
24 pub fn new(text: &str) -> Self {
25 let mut terms = Vec::new();
26 for (index, part) in text.split('"').enumerate() {
27 if index % 2 == 1 {
28 terms.push(fold(part).split_whitespace().collect::<Vec<_>>().join(" "));
29 } else {
30 terms.extend(fold(part).split_whitespace().map(str::to_owned));
31 }
32 }
33 terms.retain(|term| !term.is_empty());
34 Self { terms }
35 }
36
37 pub fn is_empty(&self) -> bool {
38 self.terms.is_empty()
39 }
40
41 /// Where the words start words of `folded`, as `fold` leaves text, in order and merged
42 /// where they overlap.
43 fn hits(&self, folded: &str) -> Vec<Range<usize>> {
44 let mut hits: Vec<Range<usize>> = self
45 .terms
46 .iter()
47 .flat_map(|term| {
48 folded
49 .match_indices(term.as_str())
50 .filter(|(at, _)| word_start(folded, *at))
51 .map(|(at, term)| at..at + term.len())
52 })
53 .collect();
54 hits.sort_by_key(|hit| (hit.start, std::cmp::Reverse(hit.end)));
55 let mut merged: Vec<Range<usize>> = Vec::with_capacity(hits.len());
56 for hit in hits {
57 match merged.last_mut() {
58 Some(last) if hit.start <= last.end => last.end = last.end.max(hit.end),
59 _ => merged.push(hit),
60 }
61 }
62 merged
63 }
64
65 fn all_in(&self, folded: &str) -> bool {
66 self.terms.iter().all(|term| starts_word(term, folded))
67 }
68
69 /// Where the query's words start words of `text`, as byte ranges of it.
70 pub(crate) fn find(&self, text: &str) -> Vec<Range<usize>> {
71 let (folded, source) = fold_mapped(text);
72 self.hits(&folded)
73 .into_iter()
74 .map(|hit| source_range(text, &source, hit))
75 .collect()
76 }
77}
78
79/// Ideographs and kana are words of their own, as their text has no spaces between words.
80pub(crate) fn ideographic(character: char) -> bool {
81 matches!(u32::from(character),
82 0x3040..=0x30ff | 0x3400..=0x4dbf | 0x4e00..=0x9fff | 0xf900..=0xfaff | 0x20000..=0x3ffff)
83}
84
85fn starts_word(term: &str, folded: &str) -> bool {
86 folded
87 .match_indices(term)
88 .any(|(at, _)| word_start(folded, at))
89}
90
91fn word_start(text: &str, at: usize) -> bool {
92 match text[..at].chars().next_back() {
93 None => true,
94 Some(before) => {
95 !before.is_alphanumeric()
96 || ideographic(before)
97 || text[at..].chars().next().is_some_and(ideographic)
98 }
99 }
100}
101
102fn diacritic(character: char) -> bool {
103 matches!(u32::from(character),
104 0x300..=0x36f | 0x1ab0..=0x1aff | 0x1dc0..=0x1dff | 0x20d0..=0x20ff | 0xfe20..=0xfe2f)
105}
106
107/// Appends `character` lowered and without diacritics; line breaks stay and other spaces
108/// become one space each.
109fn fold_char(character: char, out: &mut String) {
110 const DECOMPOSE: DecomposingNormalizerBorrowed = DecomposingNormalizerBorrowed::new_nfd();
111 if character.is_ascii() {
112 out.push(match character {
113 '\n' => '\n',
114 space if space.is_whitespace() => ' ',
115 other => other.to_ascii_lowercase(),
116 });
117 return;
118 }
119 match character {
120 '\u{2018}' | '\u{2019}' | '\u{02bc}' => out.push('\''),
121 '\u{201c}' | '\u{201d}' => out.push('"'),
122 'ß' => out.push_str("ss"),
123 'æ' | 'Æ' => out.push_str("ae"),
124 'œ' | 'Œ' => out.push_str("oe"),
125 'ø' | 'Ø' => out.push('o'),
126 'ł' | 'Ł' => out.push('l'),
127 'đ' | 'Đ' => out.push('d'),
128 'ı' => out.push('i'),
129 space if space.is_whitespace() => out.push(' '),
130 other => out.extend(
131 DECOMPOSE
132 .normalize_iter(other.to_lowercase())
133 .filter(|part| !diacritic(*part)),
134 ),
135 }
136}
137
138/// `text` as search compares it: lowered and without diacritics.
139pub fn fold(text: &str) -> String {
140 let mut out = String::with_capacity(text.len());
141 for character in text.chars() {
142 fold_char(character, &mut out);
143 }
144 out
145}
146
147/// `fold`, with the byte of `text` each folded byte came from.
148fn fold_mapped(text: &str) -> (String, Vec<usize>) {
149 let mut out = String::with_capacity(text.len());
150 let mut source = Vec::with_capacity(text.len());
151 for (at, character) in text.char_indices() {
152 fold_char(character, &mut out);
153 source.resize(out.len(), at);
154 }
155 (out, source)
156}
157
158/// The bytes of `text` a range of its folding came from, whole characters.
159fn source_range(text: &str, source: &[usize], hit: Range<usize>) -> Range<usize> {
160 let start = source[hit.start];
161 let last = source[hit.end - 1];
162 let end = last + text[last..].chars().next().map_or(0, char::len_utf8);
163 start..end
164}
165
166/// The text a paragraph shows, without hidden field codes.
167pub fn shown(paragraph: &Paragraph) -> String {
168 let mut start = 0;
169 paragraph
170 .spans()
171 .iter()
172 .filter_map(|span| {
173 let run = &paragraph.text()[start..span.end];
174 start = span.end;
175 (span.format.hidden != Some(true)).then_some(run)
176 })
177 .collect()
178}
179
180/// Calls `visit` with each text paragraph of the page's outlines, in page order, tables
181/// cell by cell.
182fn text_paragraphs<'a>(page: &'a Page, mut visit: impl FnMut(&'a PageParagraph, &'a Paragraph)) {
183 for object in &page.objects {
184 if let PageObject::Outline(outline) = object {
185 for (_, _, node) in descendants(&outline.paragraphs, None) {
186 if let ParagraphContent::Text(text) = &node.content {
187 visit(node, &text.text);
188 }
189 }
190 }
191 }
192}
193
194/// The text OneNote recognised in each of the page's pictures, or printed on a printout's
195/// pages, in page order.
196fn picture_text(page: &Page) -> Vec<&str> {
197 let pictures = page.objects.iter().flat_map(|object| match object {
198 PageObject::Outline(outline) => descendants(&outline.paragraphs, None)
199 .filter_map(|(_, _, node)| match &node.content {
200 ParagraphContent::Image(image) => Some(image),
201 _ => None,
202 })
203 .collect(),
204 PageObject::Image(image) => vec![image],
205 _ => Vec::new(),
206 });
207 pictures
208 .filter_map(|image| Some(image.text.as_ref()?.text.as_str()))
209 .collect()
210}
211
212/// A page's text outside its title, a paragraph to a line, then the text in its pictures,
213/// which OneNote searches too.
214pub fn page_text(page: &Page) -> String {
215 let mut out = Vec::new();
216 text_paragraphs(page, |_, text| out.push(shown(text)));
217 out.extend(
218 picture_text(page)
219 .into_iter()
220 .flat_map(str::lines)
221 .map(str::to_owned),
222 );
223 out.retain(|line| !line.trim().is_empty());
224 out.join("\n")
225}
226
227/// A tagged paragraph, as OneNote's Tags Summary lists it: once for each of its tags.
228#[derive(Clone, Debug, PartialEq)]
229pub struct Tagged {
230 pub section: String,
231 pub space: ExGuid,
232 /// The page's title.
233 pub title: String,
234 pub paragraph: ExGuid,
235 /// The tag's name, as its definition stores it.
236 pub name: String,
237 /// The tag's symbol, as its definition stores it.
238 pub shape: u16,
239 /// A check box tag is checked.
240 pub checked: bool,
241 pub text: String,
242 /// When the tag was applied, in Time32, or the page's modification time where unknown.
243 pub created: u64,
244}
245
246/// The page's tagged paragraphs, oldest tag first on each, as OneNote lists them; a tag
247/// without a definition, as an Outlook task's, is left out.
248fn tagged(section: &str, space: ExGuid, page: &Page, modified: u64) -> Vec<Tagged> {
249 let mut out = Vec::new();
250 text_paragraphs(page, |paragraph, text| {
251 let ParagraphContent::Text(object) = &paragraph.content else {
252 return;
253 };
254 // Stored newest first.
255 for tag in paragraph.tags.iter().chain(&object.tags).rev() {
256 let Some(Kind::TagDefinition {
257 label: Some(name),
258 shape,
259 ..
260 }) = tag
261 .definition
262 .and_then(|id| page.definitions.get(&id))
263 .map(|definition| &definition.kind)
264 else {
265 continue;
266 };
267 out.push(Tagged {
268 section: section.to_owned(),
269 space,
270 title: page.title.clone(),
271 paragraph: paragraph.id,
272 name: name.to_string(),
273 shape: shape.unwrap_or(0),
274 checked: tag.status & 1 != 0,
275 text: shown(text),
276 created: tag.created.map_or(modified, u64::from),
277 });
278 }
279 });
280 out
281}
282
283/// A page as search knows it.
284pub struct Entry {
285 /// The section's key, which the host chooses.
286 pub section: String,
287 pub space: ExGuid,
288 /// The page's own identity, which it keeps moving to another section.
289 pub identity: Option<[u8; 16]>,
290 pub title: String,
291 /// When the page last changed, in any unit that orders.
292 pub modified: u64,
293 text: String,
294 folded_title: String,
295 folded_text: String,
296 tagged: Vec<Tagged>,
297}
298
299impl Entry {
300 /// Page `space` of `section` as `page` shows it.
301 pub fn new(section: &str, space: ExGuid, page: &Page, modified: u64) -> Self {
302 let text = page_text(page);
303 Self {
304 section: section.to_owned(),
305 space,
306 identity: page.identity,
307 folded_title: fold(&page.title),
308 folded_text: fold(&text),
309 title: page.title.clone(),
310 modified,
311 text,
312 tagged: tagged(section, space, page, modified),
313 }
314 }
315}
316
317/// A page matching a query.
318#[derive(Clone, Debug, PartialEq)]
319pub struct Found {
320 pub section: String,
321 pub space: ExGuid,
322 pub title: String,
323 pub modified: u64,
324 /// The page's place in the index, which keeps each section's pages in order.
325 pub order: usize,
326 /// Every word is in the title, as OneNote's "Title contains" lists it.
327 pub in_title: bool,
328 /// Byte ranges of the title the words match.
329 pub title_hits: Vec<Range<usize>>,
330 /// The line around the first match in the page's text, or its first line.
331 pub snippet: String,
332 pub snippet_hits: Vec<Range<usize>>,
333}
334
335impl Found {
336 /// Where OneNote lists the page: title matches first, then the most recently modified.
337 pub fn rank(&self) -> (bool, std::cmp::Reverse<u64>) {
338 (!self.in_title, std::cmp::Reverse(self.modified))
339 }
340}
341
342/// Pages of any number of sections, searchable together.
343#[derive(Default)]
344pub struct Index {
345 entries: Vec<Entry>,
346}
347
348impl Index {
349 pub fn len(&self) -> usize {
350 self.entries.len()
351 }
352
353 pub fn is_empty(&self) -> bool {
354 self.entries.is_empty()
355 }
356
357 /// Every page, each section's in order.
358 pub fn entries(&self) -> &[Entry] {
359 &self.entries
360 }
361
362 /// Adds `entry`, replacing the page it names.
363 pub fn set(&mut self, entry: Entry) {
364 match self
365 .entries
366 .iter_mut()
367 .find(|old| old.space == entry.space && old.section == entry.section)
368 {
369 Some(old) => *old = entry,
370 None => self.entries.push(entry),
371 }
372 }
373
374 /// Keeps the pages whose section `keep` accepts.
375 pub fn retain(&mut self, mut keep: impl FnMut(&Entry) -> bool) {
376 self.entries.retain(|entry| keep(entry));
377 }
378
379 /// The page `space` of `section`, when indexed.
380 pub fn get(&self, section: &str, space: ExGuid) -> Option<&Entry> {
381 self.entries
382 .iter()
383 .find(|entry| entry.space == space && entry.section == section)
384 }
385
386 /// Pages of the sections `scope` accepts that hold every word of `query`, title hits
387 /// first, then the most recently modified.
388 pub fn search(&self, query: &Query, scope: impl Fn(&str) -> bool) -> Vec<Found> {
389 if query.is_empty() {
390 return Vec::new();
391 }
392 let mut found: Vec<Found> = self
393 .entries
394 .iter()
395 .enumerate()
396 .filter(|(_, entry)| scope(&entry.section))
397 .filter_map(|(order, entry)| {
398 let in_title = query.all_in(&entry.folded_title);
399 let matches = in_title
400 || query.terms.iter().all(|term| {
401 starts_word(term, &entry.folded_title)
402 || starts_word(term, &entry.folded_text)
403 });
404 matches.then_some((order, entry, in_title))
405 })
406 .map(|(order, entry, in_title)| {
407 let (snippet, snippet_hits) = snippet(entry, query);
408 Found {
409 section: entry.section.clone(),
410 space: entry.space,
411 title: entry.title.clone(),
412 modified: entry.modified,
413 order,
414 in_title,
415 title_hits: query.find(&entry.title),
416 snippet,
417 snippet_hits,
418 }
419 })
420 .collect();
421 found.sort_by_key(Found::rank);
422 found
423 }
424
425 /// The tagged paragraphs of the pages whose section and page `scope` accepts, in page
426 /// order.
427 pub fn tagged(&self, scope: impl Fn(&Entry) -> bool) -> Vec<Tagged> {
428 self.entries
429 .iter()
430 .filter(|entry| scope(entry))
431 .flat_map(|entry| entry.tagged.iter().cloned())
432 .collect()
433 }
434}
435
436/// Part of the line holding the first match in the entry's text, the matches within it;
437/// the text's first line when nothing there matches.
438fn snippet(entry: &Entry, query: &Query) -> (String, Vec<Range<usize>>) {
439 let first = query.hits(&entry.folded_text).first().map(|hit| hit.start);
440 let line = first.map_or(0, |at| {
441 entry.folded_text[..at]
442 .bytes()
443 .filter(|byte| *byte == b'\n')
444 .count()
445 });
446 let text = entry.text.split('\n').nth(line).unwrap_or_default();
447 let hits = query.find(text);
448 let chars: Vec<(usize, char)> = text.char_indices().collect();
449 let at = hits.first().map_or(0, |hit| {
450 chars.partition_point(|(byte, _)| *byte < hit.start)
451 });
452 let mut start = at.saturating_sub(BEFORE);
453 let mut end = (start + SNIPPET).min(chars.len());
454 // Cut ends fall back to the nearest space, so no word shows in part.
455 if start > 0
456 && let Some(space) = chars[start..at]
457 .iter()
458 .position(|(_, char)| char.is_whitespace())
459 {
460 start += space + 1;
461 }
462 if end < chars.len()
463 && let Some(space) = chars[at..end]
464 .iter()
465 .rposition(|(_, char)| char.is_whitespace())
466 {
467 end = at + space;
468 }
469 let byte = |index: usize| chars.get(index).map_or(text.len(), |(byte, _)| *byte);
470 let [from, to] = [byte(start), byte(end)];
471 let lead = if start > 0 { "…" } else { "" };
472 let shown = format!(
473 "{lead}{}{}",
474 text[from..to].trim_end(),
475 if end < chars.len() { "…" } else { "" }
476 );
477 let hits = hits
478 .into_iter()
479 .filter(|hit| hit.start >= from && hit.end <= to)
480 .map(|hit| hit.start - from + lead.len()..hit.end - from + lead.len())
481 .filter(|hit| hit.end <= shown.len())
482 .collect();
483 (shown, hits)
484}
485
486/// A match on a page: the outline it is in and its range there.
487pub type PageMatch = (ExGuid, Selection);
488
489/// Where `query` matches the page `editor` shows, from the page's top: outlines by where
490/// they stand, then their shown paragraphs in order.
491pub fn page_matches(editor: &CanvasEditor, query: &Query) -> Vec<PageMatch> {
492 if query.is_empty() {
493 return Vec::new();
494 }
495 let mut outlines: Vec<_> = editor.outlines().iter().collect();
496 outlines.sort_by(|a, b| {
497 let [ax, ay] = a.origin();
498 let [bx, by] = b.origin();
499 ay.total_cmp(&by).then(ax.total_cmp(&bx))
500 });
501 let mut matches = Vec::new();
502 for outline in outlines {
503 for (index, _) in outline.layouts() {
504 let Some(paragraph) = outline.document().paragraph(index) else {
505 continue;
506 };
507 // Hidden field codes are left out, and each shown byte keeps its source byte.
508 let mut shown = String::new();
509 let mut source = Vec::new();
510 let mut start = 0;
511 for span in paragraph.spans() {
512 if span.format.hidden != Some(true) {
513 shown.push_str(&paragraph.text()[start..span.end]);
514 source.extend(start..span.end);
515 }
516 start = span.end;
517 }
518 for hit in query.find(&shown) {
519 let end = source[hit.end - 1] + 1;
520 let (Ok(from), Ok(to)) = (
521 paragraph.utf16_offset(source[hit.start]),
522 paragraph.utf16_offset(end),
523 ) else {
524 continue;
525 };
526 let at = |offset| TextPosition {
527 paragraph: index,
528 offset,
529 };
530 matches.push((outline.id, [at(from), at(to)].into()));
531 }
532 }
533 }
534 matches
535}
536
537/// The whole of paragraph `id` on the page `editor` shows, as a tag summary selects it.
538pub fn paragraph_match(editor: &CanvasEditor, id: ExGuid) -> Option<PageMatch> {
539 editor.outlines().iter().find_map(|outline| {
540 let document = outline.document();
541 let index = document.text_nodes().position(|node| node.id == id)?;
542 let paragraph = document.paragraph(index)?;
543 let end = paragraph.utf16_offset(paragraph.text().len()).ok()?;
544 let at = |offset| TextPosition {
545 paragraph: index,
546 offset,
547 };
548 Some((outline.id, [at(0), at(end)].into()))
549 })
550}