mant_core/
search.rs

1//! Searches deterministic Markdown while retaining addressable manual nodes.
2//!
3//! Section and semantic-entry anchors emitted by the Markdown renderer form
4//! an internal source map. pulldown-cmark supplies a visible-text projection
5//! whose byte ranges map back into that exact Markdown document.
6
7use std::{error::Error, fmt, ops::Range};
8
9use grep_matcher::Matcher;
10use grep_regex::RegexMatcherBuilder;
11use mant_ast::{
12    MarkdownSchema, QueryBundle, QuerySearch, SearchCase, SearchContextLine, SearchMarkdownRange,
13    SearchMatch, SearchQuery, SearchRender, SearchRenderFormat, SearchRenderScope, SearchSchema,
14    SearchScope, SearchSyntax,
15};
16use pulldown_cmark::{Event, Parser, TagEnd};
17
18use crate::output::{MarkdownOptions, render_markdown_with_options};
19
20mod owners;
21
22use owners::{Owner, OwnerIndex};
23
24const MAX_PATTERN_BYTES: usize = 4096;
25const MAX_CONTEXT_LINES: u16 = 100;
26const MAX_SEARCH_LIMIT: u32 = 10_000;
27
28/// Invalid search input or matcher construction.
29#[derive(Debug, Clone, PartialEq, Eq)]
30pub enum SearchError {
31    EmptyPattern,
32    PatternTooLong,
33    InvalidLimit,
34    ContextTooLarge,
35    InvalidPattern(String),
36}
37
38impl fmt::Display for SearchError {
39    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
40        match self {
41            Self::EmptyPattern => formatter.write_str("search pattern must not be empty"),
42            Self::PatternTooLong => write!(
43                formatter,
44                "search pattern exceeds the {MAX_PATTERN_BYTES}-byte limit"
45            ),
46            Self::InvalidLimit => write!(
47                formatter,
48                "search limit must be between 1 and {MAX_SEARCH_LIMIT}"
49            ),
50            Self::ContextTooLarge => write!(
51                formatter,
52                "search context must not exceed {MAX_CONTEXT_LINES} lines"
53            ),
54            Self::InvalidPattern(message) => write!(formatter, "invalid search pattern: {message}"),
55        }
56    }
57}
58
59impl Error for SearchError {}
60
61/// Search one complete query and report coordinates in its canonical Markdown.
62///
63/// # Errors
64///
65/// Returns [`SearchError`] for empty or excessive inputs and invalid regular
66/// expressions. A valid search with no matches is a successful empty result.
67pub fn search_query(
68    query: &QueryBundle,
69    request: &SearchQuery,
70) -> Result<QuerySearch, SearchError> {
71    validate_request(request)?;
72    let markdown = render_markdown_with_options(query, MarkdownOptions::ADDRESSABLE);
73    let lines = LineIndex::new(&markdown);
74    let owners = OwnerIndex::new(query, &markdown);
75    let searchable = SearchableText::new(&markdown, request.scope);
76    let matcher = build_matcher(request)?;
77    let mut raw_matches = Vec::new();
78
79    matcher
80        .find_iter(searchable.text.as_bytes(), |found| {
81            let markdown_start = searchable.markdown_start(found.start());
82            let markdown_end = searchable.markdown_end(found.end());
83            if let Some(owner) = owners.owner(markdown_start) {
84                raw_matches.push(RawMatch {
85                    searchable: found.start()..found.end(),
86                    markdown: markdown_start..markdown_end,
87                    owner: owner.clone(),
88                });
89            }
90            true
91        })
92        .map_err(|error| SearchError::InvalidPattern(error.to_string()))?;
93
94    let total = u32::try_from(raw_matches.len()).unwrap_or(u32::MAX);
95    let offset = usize::try_from(request.offset).unwrap_or(usize::MAX);
96    let limit = usize::try_from(request.limit).unwrap_or(usize::MAX);
97    let selected = raw_matches
98        .iter()
99        .enumerate()
100        .skip(offset)
101        .take(limit)
102        .map(|(index, found)| {
103            build_match(
104                index,
105                found,
106                &searchable.text,
107                &markdown,
108                &lines,
109                request.context_lines,
110            )
111        })
112        .collect::<Vec<_>>();
113    let returned = u32::try_from(selected.len()).unwrap_or(u32::MAX);
114    let consumed = request.offset.saturating_add(returned);
115    let truncated = consumed < total;
116
117    Ok(QuerySearch {
118        schema: SearchSchema::V6,
119        label: query.label.clone(),
120        source: query
121            .document
122            .as_ref()
123            .map(|document| document.source.clone()),
124        meta: query
125            .document
126            .as_ref()
127            .map(|document| document.meta.clone()),
128        query: request.clone(),
129        render: SearchRender {
130            schema: MarkdownSchema::V1,
131            format: SearchRenderFormat::Markdown,
132            scope: SearchRenderScope::Full,
133            line_base: 1,
134            column_base: 1,
135            line_count: u32::try_from(lines.count()).unwrap_or(u32::MAX),
136        },
137        total,
138        returned,
139        offset: request.offset,
140        truncated,
141        next_offset: truncated.then_some(consumed),
142        matches: selected,
143    })
144}
145
146/// Validate search limits and compile its matcher without loading a manual.
147///
148/// # Errors
149///
150/// Returns the same [`SearchError`] variants as [`search_query`].
151pub fn validate_search_query(request: &SearchQuery) -> Result<(), SearchError> {
152    validate_request(request)?;
153    build_matcher(request).map(|_| ())
154}
155
156fn validate_request(request: &SearchQuery) -> Result<(), SearchError> {
157    if request.pattern.is_empty() {
158        return Err(SearchError::EmptyPattern);
159    }
160    if request.pattern.len() > MAX_PATTERN_BYTES {
161        return Err(SearchError::PatternTooLong);
162    }
163    if request.limit == 0 || request.limit > MAX_SEARCH_LIMIT {
164        return Err(SearchError::InvalidLimit);
165    }
166    if request.context_lines > MAX_CONTEXT_LINES {
167        return Err(SearchError::ContextTooLarge);
168    }
169    Ok(())
170}
171
172fn build_matcher(request: &SearchQuery) -> Result<grep_regex::RegexMatcher, SearchError> {
173    let mut builder = RegexMatcherBuilder::new();
174    builder
175        .fixed_strings(request.syntax == SearchSyntax::Literal)
176        .word(request.word);
177    match request.case {
178        SearchCase::Insensitive => {
179            builder.case_insensitive(true);
180        }
181        SearchCase::Sensitive => {
182            builder.case_insensitive(false);
183        }
184        SearchCase::Smart => {
185            builder.case_smart(true);
186        }
187    }
188    let matcher = builder
189        .build(&request.pattern)
190        .map_err(|error| SearchError::InvalidPattern(error.to_string()))?;
191    if matcher
192        .is_match(b"")
193        .map_err(|error| SearchError::InvalidPattern(error.to_string()))?
194    {
195        return Err(SearchError::InvalidPattern(
196            "pattern must not match empty text".to_owned(),
197        ));
198    }
199    Ok(matcher)
200}
201
202#[derive(Clone)]
203struct RawMatch {
204    searchable: Range<usize>,
205    markdown: Range<usize>,
206    owner: Owner,
207}
208
209fn build_match(
210    index: usize,
211    found: &RawMatch,
212    searchable: &str,
213    markdown: &str,
214    lines: &LineIndex,
215    context_lines: u16,
216) -> SearchMatch {
217    let start = lines.position(markdown, found.markdown.start);
218    let end = lines.position(markdown, found.markdown.end);
219    let preview = display_markdown_line(lines.line(markdown, start.line_index));
220    let context_start = start.line_index.saturating_sub(usize::from(context_lines));
221    let context_end = end
222        .line_index
223        .saturating_add(usize::from(context_lines))
224        .min(lines.count().saturating_sub(1));
225    let context = if context_lines == 0 {
226        Vec::new()
227    } else {
228        (context_start..=context_end)
229            .map(|line_index| SearchContextLine {
230                line: u32::try_from(line_index.saturating_add(1)).unwrap_or(u32::MAX),
231                text: display_markdown_line(lines.line(markdown, line_index)),
232                matched: (start.line_index..=end.line_index).contains(&line_index),
233            })
234            .collect()
235    };
236
237    SearchMatch {
238        ordinal: u32::try_from(index.saturating_add(1)).unwrap_or(u32::MAX),
239        node: found.owner.node.clone(),
240        section: found.owner.section.clone(),
241        matched_text: searchable[found.searchable.clone()].to_owned(),
242        markdown: SearchMarkdownRange {
243            start_byte: u64::try_from(found.markdown.start).unwrap_or(u64::MAX),
244            end_byte: u64::try_from(found.markdown.end).unwrap_or(u64::MAX),
245            start_line: u32::try_from(start.line_index.saturating_add(1)).unwrap_or(u32::MAX),
246            start_column: u32::try_from(start.column).unwrap_or(u32::MAX),
247            end_line: u32::try_from(end.line_index.saturating_add(1)).unwrap_or(u32::MAX),
248            end_column: u32::try_from(end.column).unwrap_or(u32::MAX),
249        },
250        source: found.owner.source,
251        preview,
252        context,
253    }
254}
255
256/// Hide `ManT`'s zero-width source-map anchors from human-facing snippets.
257fn display_markdown_line(line: &str) -> String {
258    let mut output = String::with_capacity(line.len());
259    let mut remaining = line.trim_end();
260    while let Some(start) = remaining.find("<a id=\"") {
261        output.push_str(&remaining[..start]);
262        let anchor = &remaining[start..];
263        let Some(end) = anchor.find("</a>") else {
264            output.push_str(anchor);
265            return output;
266        };
267        remaining = &anchor[end + "</a>".len()..];
268    }
269    output.push_str(remaining);
270    output
271}
272
273struct TextPosition {
274    line_index: usize,
275    column: usize,
276}
277
278struct LineIndex {
279    starts: Vec<usize>,
280}
281
282impl LineIndex {
283    fn new(text: &str) -> Self {
284        let mut starts = vec![0];
285        starts.extend(
286            text.bytes()
287                .enumerate()
288                .filter_map(|(index, byte)| (byte == b'\n').then_some(index + 1)),
289        );
290        Self { starts }
291    }
292
293    fn count(&self) -> usize {
294        self.starts.len()
295    }
296
297    fn position(&self, text: &str, offset: usize) -> TextPosition {
298        let offset = offset.min(text.len());
299        let line_index = self.starts.partition_point(|start| *start <= offset) - 1;
300        let line_start = self.starts[line_index];
301        TextPosition {
302            line_index,
303            column: text[line_start..offset].chars().count().saturating_add(1),
304        }
305    }
306
307    fn line<'a>(&self, text: &'a str, line_index: usize) -> &'a str {
308        let start = self.starts[line_index];
309        let end = self
310            .starts
311            .get(line_index + 1)
312            .copied()
313            .unwrap_or(text.len());
314        text[start..end]
315            .strip_suffix('\n')
316            .unwrap_or(&text[start..end])
317    }
318}
319
320struct SearchableText {
321    text: String,
322    segments: Vec<OffsetSegment>,
323    direct_markdown: bool,
324}
325
326#[derive(Debug)]
327struct OffsetSegment {
328    visible: Range<usize>,
329    markdown: Range<usize>,
330}
331
332impl SearchableText {
333    fn new(markdown: &str, scope: SearchScope) -> Self {
334        if scope == SearchScope::Markdown {
335            return Self {
336                text: markdown.to_owned(),
337                segments: Vec::new(),
338                direct_markdown: true,
339            };
340        }
341
342        let mut visible = VisibleBuilder::new(markdown);
343        for (event, source) in Parser::new(markdown).into_offset_iter() {
344            match event {
345                Event::Text(value)
346                | Event::Code(value)
347                | Event::InlineMath(value)
348                | Event::DisplayMath(value) => visible.push_aligned(&value, source),
349                Event::SoftBreak | Event::HardBreak => visible.push_break(source.start),
350                Event::End(
351                    TagEnd::Paragraph
352                    | TagEnd::Heading(_)
353                    | TagEnd::Item
354                    | TagEnd::CodeBlock
355                    | TagEnd::TableRow,
356                )
357                | Event::Rule => visible.push_break(source.end),
358                Event::Start(_)
359                | Event::End(_)
360                | Event::Html(_)
361                | Event::InlineHtml(_)
362                | Event::FootnoteReference(_)
363                | Event::TaskListMarker(_) => {}
364            }
365        }
366        visible.finish()
367    }
368
369    fn markdown_start(&self, offset: usize) -> usize {
370        if self.direct_markdown {
371            return offset;
372        }
373        self.segment_at(offset).map_or(0, |segment| {
374            if segment.visible.len() == segment.markdown.len() {
375                segment.markdown.start + offset.saturating_sub(segment.visible.start)
376            } else {
377                segment.markdown.start
378            }
379        })
380    }
381
382    fn markdown_end(&self, offset: usize) -> usize {
383        if self.direct_markdown {
384            return offset;
385        }
386        if offset == 0 {
387            return 0;
388        }
389        self.segment_at(offset - 1).map_or(0, |segment| {
390            if segment.visible.len() == segment.markdown.len() {
391                segment.markdown.start + offset.saturating_sub(segment.visible.start)
392            } else {
393                segment.markdown.end
394            }
395        })
396    }
397
398    fn segment_at(&self, offset: usize) -> Option<&OffsetSegment> {
399        let index = self
400            .segments
401            .partition_point(|segment| segment.visible.end <= offset);
402        self.segments
403            .get(index)
404            .filter(|segment| segment.visible.contains(&offset))
405    }
406}
407
408/// Largest char boundary not exceeding `offset`; stable stand-in for
409/// `str::floor_char_boundary`.
410fn floor_char_boundary(text: &str, offset: usize) -> usize {
411    let mut offset = offset.min(text.len());
412    while offset > 0 && !text.is_char_boundary(offset) {
413        offset -= 1;
414    }
415    offset
416}
417
418struct VisibleBuilder<'a> {
419    markdown: &'a str,
420    text: String,
421    segments: Vec<OffsetSegment>,
422}
423
424impl<'a> VisibleBuilder<'a> {
425    fn new(markdown: &'a str) -> Self {
426        Self {
427            markdown,
428            text: String::new(),
429            segments: Vec::new(),
430        }
431    }
432
433    fn push_aligned(&mut self, value: &str, source: Range<usize>) {
434        let mut markdown_cursor = source.start.min(self.markdown.len());
435        let markdown_end = floor_char_boundary(self.markdown, source.end);
436        for character in value.chars() {
437            let search_start = floor_char_boundary(self.markdown, markdown_cursor);
438            let search_end = markdown_end.max(search_start);
439            let found = self.markdown[search_start..search_end]
440                .find(character)
441                .map_or(search_start, |relative| search_start + relative);
442            let visible_start = self.text.len();
443            self.text.push(character);
444            let visible_end = self.text.len();
445            let source_end = floor_char_boundary(
446                self.markdown,
447                found.saturating_add(character.len_utf8()).min(search_end),
448            );
449            self.push_segment(OffsetSegment {
450                visible: visible_start..visible_end,
451                markdown: found..source_end,
452            });
453            markdown_cursor = source_end;
454        }
455    }
456
457    fn push_break(&mut self, markdown_offset: usize) {
458        if self.text.ends_with('\n') || self.text.is_empty() {
459            return;
460        }
461        let start = self.text.len();
462        self.text.push('\n');
463        self.push_segment(OffsetSegment {
464            visible: start..self.text.len(),
465            markdown: markdown_offset..markdown_offset,
466        });
467    }
468
469    fn push_segment(&mut self, segment: OffsetSegment) {
470        if let Some(previous) = self.segments.last_mut() {
471            let contiguous = previous.visible.end == segment.visible.start
472                && previous.markdown.end == segment.markdown.start
473                && previous.visible.len() == previous.markdown.len()
474                && segment.visible.len() == segment.markdown.len();
475            if contiguous {
476                previous.visible.end = segment.visible.end;
477                previous.markdown.end = segment.markdown.end;
478                return;
479            }
480        }
481        self.segments.push(segment);
482    }
483
484    fn finish(self) -> SearchableText {
485        SearchableText {
486            text: self.text,
487            segments: self.segments,
488            direct_markdown: false,
489        }
490    }
491}
492
493#[cfg(test)]
494mod tests {
495    use mant_ast::{
496        Block, DefinitionCase, DefinitionIdentity, DefinitionItem, DefinitionRole, DocumentMeta,
497        DocumentSchema, DocumentSource, Inline, LayoutHint, MantDocument, Producer, QueryBundle,
498        QuerySchema, SearchCase, SearchQuery, SearchScope, SearchSyntax, Section, SourceFormat,
499    };
500
501    use super::search_query;
502
503    fn query() -> QueryBundle {
504        QueryBundle {
505            schema: QuerySchema::V6,
506            label: "demo".to_owned(),
507            document: Some(MantDocument {
508                schema: DocumentSchema::V6,
509                producer: Producer {
510                    name: "test".to_owned(),
511                    version: "1".to_owned(),
512                    engine: None,
513                },
514                source: DocumentSource {
515                    format: SourceFormat::Man,
516                    path: None,
517                },
518                meta: DocumentMeta {
519                    section: Some("1".to_owned()),
520                    ..DocumentMeta::default()
521                },
522                diagnostics: Vec::new(),
523                blocks: Vec::new(),
524                sections: vec![Section {
525                    id: "options-1".to_owned(),
526                    title: "OPTIONS".to_owned(),
527                    spacing_before_lines: 0,
528                    blocks: vec![Block::DefinitionList {
529                        items: vec![DefinitionItem {
530                            inline_term: false,
531                            identity: Some(DefinitionIdentity {
532                                id: "option-acls".to_owned(),
533                                role: DefinitionRole::Option,
534                                case: DefinitionCase::Sensitive,
535                                names: vec!["--acls".to_owned()],
536                            }),
537                            terms: vec![vec![
538                                Inline::Anchor {
539                                    id: "option-acls".to_owned(),
540                                },
541                                Inline::Code {
542                                    value: "--acls".to_owned(),
543                                },
544                            ]],
545                            description: vec![Block::Paragraph {
546                                children: vec![
547                                    Inline::Text {
548                                        value: "Preserve ".to_owned(),
549                                    },
550                                    Inline::Strong {
551                                        children: vec![Inline::Text {
552                                            value: "access control".to_owned(),
553                                        }],
554                                    },
555                                    Inline::Text {
556                                        value: " lists".to_owned(),
557                                    },
558                                ],
559                                layout: LayoutHint::default(),
560                                source: None,
561                            }],
562                            spacing_before_lines: None,
563                        }],
564                        compact: true,
565                        layout: LayoutHint::default(),
566                        source: None,
567                    }],
568                    children: Vec::new(),
569                    source: None,
570                }],
571            }),
572            tldr: None,
573        }
574    }
575
576    fn request(pattern: &str) -> SearchQuery {
577        SearchQuery {
578            pattern: pattern.to_owned(),
579            syntax: SearchSyntax::Literal,
580            case: SearchCase::Insensitive,
581            scope: SearchScope::Visible,
582            word: false,
583            context_lines: 1,
584            limit: 100,
585            offset: 0,
586        }
587    }
588
589    #[test]
590    fn visible_search_maps_inline_formatting_to_markdown_and_option_nodes() {
591        let result = search_query(&query(), &request("access control")).expect("search");
592
593        assert_eq!(result.total, 1);
594        assert_eq!(result.matches[0].node.path(), "1/o1");
595        assert_eq!(result.matches[0].matched_text, "access control");
596        assert!(result.matches[0].markdown.start_line > 1);
597        assert!(result.matches[0].preview.contains("**access control**"));
598        assert!(!result.matches[0].preview.contains("<a id="));
599        assert!(!result.matches[0].context.is_empty());
600    }
601
602    #[test]
603    fn semantic_entry_ownership_ends_before_a_following_section_paragraph() {
604        let mut query = query();
605        query.document.as_mut().expect("manual").sections[0]
606            .blocks
607            .push(Block::Paragraph {
608                children: vec![Inline::Text {
609                    value: "General section tail".to_owned(),
610                }],
611                layout: LayoutHint::default(),
612                source: None,
613            });
614
615        let result = search_query(&query, &request("section tail")).expect("search");
616        assert!(matches!(
617            &result.matches[0].node,
618            mant_ast::SearchNode::DocumentSection { path, .. } if path == "1"
619        ));
620    }
621
622    #[test]
623    fn root_content_search_resolves_to_an_addressable_document_root() {
624        let mut query = query();
625        let document = query.document.as_mut().expect("document");
626        document.source.format = SourceFormat::Markdown;
627        document.blocks.push(Block::Paragraph {
628            children: vec![Inline::Text {
629                value: "Read the preface needle first.".to_owned(),
630            }],
631            layout: LayoutHint::default(),
632            source: None,
633        });
634
635        let result = search_query(&query, &request("preface needle")).expect("root search");
636
637        assert_eq!(result.total, 1);
638        assert!(matches!(
639            &result.matches[0].node,
640            mant_ast::SearchNode::DocumentRoot { path, id, .. }
641                if path == "root" && id == "document-overview"
642        ));
643        assert!(result.matches[0].section.is_none());
644        assert!(result.matches[0].preview.contains("preface needle"));
645    }
646
647    #[test]
648    fn embedded_tldr_and_markdown_body_keep_distinct_search_owners() {
649        let query = crate::query_markdown_text(
650            "\
651<!-- mant:tldr:start -->
652# demo
653
654> Quick needle.
655
656- Run:
657
658`demo quick-command`
659<!-- mant:tldr:end -->
660
661# Demo
662
663Read the overview needle.
664
665## Synopsis
666
667Manual needle.
668",
669            Some("demo.md".to_owned()),
670        )
671        .expect("Markdown query");
672
673        let quick = search_query(&query, &request("quick needle")).expect("tldr search");
674        assert!(matches!(
675            &quick.matches[0].node,
676            mant_ast::SearchNode::Tldr { path, id, .. }
677                if path == "0" && id == "tldr"
678        ));
679
680        let overview = search_query(&query, &request("overview needle")).expect("root search");
681        assert!(matches!(
682            &overview.matches[0].node,
683            mant_ast::SearchNode::DocumentRoot { path, .. } if path == "root"
684        ));
685
686        let manual = search_query(&query, &request("manual needle")).expect("section search");
687        assert!(matches!(
688            &manual.matches[0].node,
689            mant_ast::SearchNode::DocumentSection { path, id, .. }
690                if path == "1" && id == "synopsis"
691        ));
692    }
693
694    #[test]
695    fn regex_case_and_pagination_are_reported_without_losing_global_ordinals() {
696        let mut request = request("ACLS|control");
697        request.syntax = SearchSyntax::Regex;
698        request.case = SearchCase::Insensitive;
699        request.limit = 1;
700        request.offset = 1;
701        let result = search_query(&query(), &request).expect("search");
702
703        assert_eq!(result.total, 2);
704        assert_eq!(result.returned, 1);
705        assert_eq!(result.matches[0].ordinal, 2);
706        assert!(!result.truncated);
707    }
708
709    #[test]
710    fn regexes_that_match_empty_text_are_rejected() {
711        let mut request = request("$");
712        request.syntax = SearchSyntax::Regex;
713        let error = search_query(&query(), &request).expect_err("empty regex match");
714        assert!(error.to_string().contains("must not match empty text"));
715    }
716}
mant_core/search.rs

mant_core/
search.rs
