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

mant_engine/
search.rs
