use std::{error::Error, fmt, ops::Range};
use grep_matcher::Matcher;
use grep_regex::RegexMatcherBuilder;
use mant_protocol::{
MAX_SEARCH_PATTERN_CHARS, MarkdownSchema, QuerySearch, SearchCase, SearchContextLine,
SearchHit, SearchLineRange, SearchMarkdownRange, SearchOccurrence, SearchQuery, SearchRender,
SearchRenderFormat, SearchRenderScope, SearchSchema, SearchScope, SearchSyntax,
};
use pulldown_cmark::{Event, Parser, TagEnd};
use regex_syntax::ParserBuilder;
use crate::markdown_mapping::{InlineMappingKind, map_inline_characters};
use crate::{ResolvedContent, output::render_addressable_markdown};
mod owners;
use owners::{Owner, OwnerIndex};
const MAX_CONTEXT_LINES: u16 = 100;
const MAX_SEARCH_LIMIT: u32 = 10_000;
const MAX_OCCURRENCES_PER_MATCH: usize = 256;
const MAX_REGEX_COMPILED_BYTES: usize = 4 * 1024 * 1024;
const MAX_REGEX_DFA_CACHE_BYTES: usize = 8 * 1024 * 1024;
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum SearchError {
EmptyPattern,
PatternTooLong,
InvalidLimit,
ContextTooLarge,
InvalidPattern(String),
}
impl fmt::Display for SearchError {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::EmptyPattern => formatter.write_str("search pattern must not be empty"),
Self::PatternTooLong => write!(
formatter,
"search pattern exceeds the {MAX_SEARCH_PATTERN_CHARS}-character limit"
),
Self::InvalidLimit => write!(
formatter,
"search limit must be between 1 and {MAX_SEARCH_LIMIT}"
),
Self::ContextTooLarge => write!(
formatter,
"search context must not exceed {MAX_CONTEXT_LINES} lines"
),
Self::InvalidPattern(message) => write!(formatter, "invalid search pattern: {message}"),
}
}
}
impl Error for SearchError {}
pub fn search_query(
query: &ResolvedContent,
request: &SearchQuery,
) -> Result<QuerySearch, SearchError> {
validate_request(request)?;
let artifact = render_addressable_markdown(query);
let markdown = &artifact.text;
let lines = LineIndex::new(markdown);
let owners = OwnerIndex::new(&artifact);
let searchable = SearchableText::new(markdown, request.scope);
let matcher = build_matcher(request)?;
let offset = usize::try_from(request.offset).unwrap_or(usize::MAX);
let limit = usize::try_from(request.limit).unwrap_or(usize::MAX);
let mut collector = SearchCollector::new(markdown, &lines, offset, limit);
collect_occurrences(
&matcher,
&searchable,
markdown,
&lines,
&owners,
&mut collector,
)?;
let (raw_groups, total) = collector.finish();
let selected = raw_groups
.iter()
.map(|found| build_match(found, &searchable, markdown, &lines, request.context_lines))
.collect::<Vec<_>>();
let returned = u32::try_from(selected.len()).unwrap_or(u32::MAX);
let consumed = request.offset.saturating_add(returned);
let truncated = consumed < total;
Ok(QuerySearch {
schema: SearchSchema::V0Dot10,
label: query.label.clone(),
source: query
.document
.as_ref()
.map(|document| document.source.clone()),
meta: query
.document
.as_ref()
.map(|document| document.meta.clone()),
query: request.clone(),
render: SearchRender {
schema: MarkdownSchema::V1,
format: SearchRenderFormat::Markdown,
scope: SearchRenderScope::Full,
line_base: 1,
column_base: 1,
line_count: u32::try_from(lines.count()).unwrap_or(u32::MAX),
},
total,
returned,
offset: request.offset,
truncated,
next_offset: truncated.then_some(consumed),
matches: selected,
})
}
fn collect_occurrences(
matcher: &grep_regex::RegexMatcher,
searchable: &SearchableText,
markdown: &str,
lines: &LineIndex,
owners: &OwnerIndex,
collector: &mut SearchCollector<'_>,
) -> Result<(), SearchError> {
let mut invalid_utf8_match = false;
let mut invalid_zero_width_match = false;
matcher
.find_iter(searchable.text.as_bytes(), |found| {
if found.start() == found.end() {
invalid_zero_width_match = true;
return false;
}
if !searchable.text.is_char_boundary(found.start())
|| !searchable.text.is_char_boundary(found.end())
{
invalid_utf8_match = true;
return false;
}
let markdown_start = searchable.markdown_start(found.start());
let markdown_end = searchable.markdown_end(found.end());
if !markdown.is_char_boundary(markdown_start)
|| !markdown.is_char_boundary(markdown_end)
{
invalid_utf8_match = true;
return false;
}
if markdown_start >= markdown_end {
return true;
}
let line_ranges = occurrence_line_ranges(markdown_start..markdown_end, markdown, lines);
if line_ranges.is_empty() {
return true;
}
let owner = owners.owner(markdown_start);
let end_owner = owners.owner(markdown_end - 1);
if let (Some(owner), Some(end_owner)) = (owner, end_owner)
&& owner.key == end_owner.key
{
collector.push(
RawOccurrence {
searchable: found.start()..found.end(),
markdown: markdown_start..markdown_end,
line_ranges,
},
owner,
);
}
true
})
.map_err(matcher_error)?;
if invalid_utf8_match {
Err(non_utf8_pattern_error())
} else if invalid_zero_width_match {
Err(empty_match_error())
} else {
Ok(())
}
}
pub fn validate_search_query(request: &SearchQuery) -> Result<(), SearchError> {
validate_request(request)?;
build_matcher(request).map(|_| ())
}
fn validate_request(request: &SearchQuery) -> Result<(), SearchError> {
if request.pattern.is_empty() {
return Err(SearchError::EmptyPattern);
}
if request.pattern.chars().count() > MAX_SEARCH_PATTERN_CHARS {
return Err(SearchError::PatternTooLong);
}
if request.limit == 0 || request.limit > MAX_SEARCH_LIMIT {
return Err(SearchError::InvalidLimit);
}
if request.context_lines > MAX_CONTEXT_LINES {
return Err(SearchError::ContextTooLarge);
}
Ok(())
}
fn build_matcher(request: &SearchQuery) -> Result<grep_regex::RegexMatcher, SearchError> {
validate_pattern_semantics(request)?;
let mut builder = RegexMatcherBuilder::new();
builder
.fixed_strings(request.syntax == SearchSyntax::Literal)
.multi_line(true)
.size_limit(MAX_REGEX_COMPILED_BYTES)
.dfa_size_limit(MAX_REGEX_DFA_CACHE_BYTES)
.word(request.word);
match request.case {
SearchCase::Insensitive => {
builder.case_insensitive(true);
}
SearchCase::Sensitive => {
builder.case_insensitive(false);
}
SearchCase::Smart => {
builder.case_smart(true);
}
}
let matcher = builder.build(&request.pattern).map_err(matcher_error)?;
if matcher.is_match(b"").map_err(matcher_error)? {
return Err(empty_match_error());
}
Ok(matcher)
}
fn validate_pattern_semantics(request: &SearchQuery) -> Result<(), SearchError> {
if request.syntax == SearchSyntax::Literal {
return Ok(());
}
let hir = ParserBuilder::new()
.utf8(true)
.unicode(true)
.build()
.parse(&request.pattern)
.map_err(|error| {
let message = error.to_string();
if message.contains("pattern can match invalid UTF-8") {
non_utf8_pattern_error()
} else {
SearchError::InvalidPattern(message)
}
})?;
if hir.properties().minimum_len() == Some(0) {
return Err(empty_match_error());
}
Ok(())
}
fn empty_match_error() -> SearchError {
SearchError::InvalidPattern("pattern must not match empty text".to_owned())
}
fn non_utf8_pattern_error() -> SearchError {
SearchError::InvalidPattern(
"regular expressions must preserve UTF-8 character boundaries; Unicode mode cannot be disabled"
.to_owned(),
)
}
fn matcher_error(error: impl fmt::Display) -> SearchError {
let message = error.to_string();
if message.contains("compiled regex exceeds size limit") {
SearchError::InvalidPattern(
"regular expression exceeds ManT's compiled-size limit".to_owned(),
)
} else {
SearchError::InvalidPattern(message)
}
}
struct RawOccurrence {
searchable: Range<usize>,
markdown: Range<usize>,
line_ranges: Vec<SearchLineRange>,
}
struct RawMatchGroup {
ordinal: u32,
occurrences: Vec<RawOccurrence>,
occurrence_count: u32,
owner: Owner,
start_line_index: usize,
end_line_index: usize,
}
struct PendingRawMatchGroup {
ordinal: u32,
occurrences: Vec<RawOccurrence>,
occurrence_count: u32,
owner: PendingOwner,
start_line_index: usize,
end_line_index: usize,
}
enum PendingOwner {
Retained(Owner),
CountOnly(usize),
}
impl PendingOwner {
const fn key(&self) -> usize {
match self {
Self::Retained(owner) => owner.key,
Self::CountOnly(key) => *key,
}
}
}
struct SearchCollector<'a> {
markdown: &'a str,
lines: &'a LineIndex,
offset: usize,
limit: usize,
total: usize,
selected: Vec<RawMatchGroup>,
current: Option<PendingRawMatchGroup>,
}
impl<'a> SearchCollector<'a> {
fn new(markdown: &'a str, lines: &'a LineIndex, offset: usize, limit: usize) -> Self {
Self {
markdown,
lines,
offset,
limit,
total: 0,
selected: Vec::with_capacity(limit.min(256)),
current: None,
}
}
fn push(&mut self, occurrence: RawOccurrence, owner: &Owner) {
let start_line_index = self
.lines
.position(self.markdown, occurrence.markdown.start)
.line_index;
let end_line_index = self
.lines
.line_index_at_byte(occurrence.markdown.end.saturating_sub(1));
if let Some(group) = self.current.as_mut().filter(|group| {
group.start_line_index == start_line_index
&& group.end_line_index == end_line_index
&& group.owner.key() == owner.key
}) {
group.occurrence_count = group.occurrence_count.saturating_add(1);
if matches!(group.owner, PendingOwner::Retained(_))
&& group.occurrences.len() < MAX_OCCURRENCES_PER_MATCH
{
group.occurrences.push(occurrence);
}
return;
}
self.flush();
let retained = self.total >= self.offset && self.selected.len() < self.limit;
let occurrences = retained.then_some(occurrence).into_iter().collect();
self.current = Some(PendingRawMatchGroup {
ordinal: u32::try_from(self.total.saturating_add(1)).unwrap_or(u32::MAX),
occurrences,
occurrence_count: 1,
owner: if retained {
PendingOwner::Retained(owner.clone())
} else {
PendingOwner::CountOnly(owner.key)
},
start_line_index,
end_line_index,
});
}
fn flush(&mut self) {
let Some(group) = self.current.take() else {
return;
};
self.total = self.total.saturating_add(1);
if let PendingOwner::Retained(owner) = group.owner {
self.selected.push(RawMatchGroup {
ordinal: group.ordinal,
occurrences: group.occurrences,
occurrence_count: group.occurrence_count,
owner,
start_line_index: group.start_line_index,
end_line_index: group.end_line_index,
});
}
}
fn finish(mut self) -> (Vec<RawMatchGroup>, u32) {
self.flush();
(self.selected, u32::try_from(self.total).unwrap_or(u32::MAX))
}
}
impl RawMatchGroup {
fn occurrences_truncated(&self) -> bool {
usize::try_from(self.occurrence_count).map_or(true, |count| count > self.occurrences.len())
}
}
fn build_match(
found: &RawMatchGroup,
searchable: &SearchableText,
markdown: &str,
lines: &LineIndex,
context_lines: u16,
) -> SearchHit {
let first = &found.occurrences[0];
let start = lines.position(markdown, first.markdown.start);
let preview = display_markdown_line(lines.line(markdown, start.line_index));
let context_start = found
.start_line_index
.saturating_sub(usize::from(context_lines));
let context_end = found
.end_line_index
.saturating_add(usize::from(context_lines))
.min(lines.count().saturating_sub(1));
let context = if context_lines == 0 {
Vec::new()
} else {
(context_start..=context_end)
.map(|line_index| SearchContextLine {
line: u32::try_from(line_index.saturating_add(1)).unwrap_or(u32::MAX),
text: display_markdown_line(lines.line(markdown, line_index)),
matched: (found.start_line_index..=found.end_line_index).contains(&line_index),
})
.collect()
};
SearchHit {
ordinal: found.ordinal,
outline: found.owner.outline.clone(),
occurrences: found
.occurrences
.iter()
.map(|occurrence| {
let start = lines.position(markdown, occurrence.markdown.start);
let end = lines.position(markdown, occurrence.markdown.end);
SearchOccurrence {
matched_text: if searchable.direct_markdown {
presented_matched_text(occurrence, markdown, lines)
} else {
searchable.text[occurrence.searchable.clone()].to_owned()
},
markdown: SearchMarkdownRange {
start_byte: u64::try_from(occurrence.markdown.start).unwrap_or(u64::MAX),
end_byte: u64::try_from(occurrence.markdown.end).unwrap_or(u64::MAX),
start_line: u32::try_from(start.line_index.saturating_add(1))
.unwrap_or(u32::MAX),
start_column: u32::try_from(start.column).unwrap_or(u32::MAX),
end_line: u32::try_from(end.line_index.saturating_add(1))
.unwrap_or(u32::MAX),
end_column: u32::try_from(end.column).unwrap_or(u32::MAX),
},
line_ranges: occurrence.line_ranges.clone(),
}
})
.collect(),
occurrence_count: found.occurrence_count,
occurrences_truncated: found.occurrences_truncated(),
node_source: found.owner.source,
preview,
context,
}
}
fn occurrence_line_ranges(
markdown_range: Range<usize>,
markdown: &str,
lines: &LineIndex,
) -> Vec<SearchLineRange> {
let start = lines.position(markdown, markdown_range.start).line_index;
let end = lines.line_index_at_byte(markdown_range.end.saturating_sub(1));
(start..=end)
.flat_map(|line_index| {
let line_start = lines.start(line_index);
let line = lines.line(markdown, line_index).trim_end();
let line_end = line_start.saturating_add(line.len());
let intersection =
markdown_range.start.max(line_start)..markdown_range.end.min(line_end);
(intersection.start < intersection.end)
.then(|| AnchorStrippedLine::new(line))
.into_iter()
.flat_map(move |visible| {
visible.map_range(
intersection.start.saturating_sub(line_start)
..intersection.end.saturating_sub(line_start),
)
})
.map(move |range| SearchLineRange {
line: u32::try_from(line_index.saturating_add(1)).unwrap_or(u32::MAX),
start_byte: u32::try_from(range.start).unwrap_or(u32::MAX),
end_byte: u32::try_from(range.end).unwrap_or(u32::MAX),
})
})
.collect()
}
fn presented_matched_text(occurrence: &RawOccurrence, markdown: &str, lines: &LineIndex) -> String {
let mut text = String::new();
let mut previous_line = None;
for range in &occurrence.line_ranges {
let line_index = usize::try_from(range.line.saturating_sub(1)).unwrap_or(usize::MAX);
if previous_line.is_some_and(|previous| previous != line_index) {
text.push('\n');
}
let line = display_markdown_line(lines.line(markdown, line_index));
let start = usize::try_from(range.start_byte).unwrap_or(usize::MAX);
let end = usize::try_from(range.end_byte).unwrap_or(usize::MAX);
if let Some(fragment) = line.get(start..end) {
text.push_str(fragment);
}
previous_line = Some(line_index);
}
text
}
fn display_markdown_line(line: &str) -> String {
AnchorStrippedLine::new(line.trim_end()).text
}
struct AnchorStrippedLine {
text: String,
segments: Vec<OffsetSegment>,
}
impl AnchorStrippedLine {
fn new(line: &str) -> Self {
let mut text = String::with_capacity(line.len());
let mut segments = Vec::new();
let mut cursor = 0;
while let Some(relative_start) = line[cursor..].find("<a id=\"") {
let anchor_start = cursor + relative_start;
push_retained_line_segment(line, cursor..anchor_start, &mut text, &mut segments);
let anchor = &line[anchor_start..];
let Some(relative_end) = anchor.find("\"></a>") else {
push_retained_line_segment(
line,
anchor_start..line.len(),
&mut text,
&mut segments,
);
return Self { text, segments };
};
cursor = anchor_start + relative_end + "\"></a>".len();
}
push_retained_line_segment(line, cursor..line.len(), &mut text, &mut segments);
Self { text, segments }
}
fn map_range(&self, source: Range<usize>) -> Vec<Range<usize>> {
self.segments
.iter()
.filter_map(|segment| {
let start = source.start.max(segment.markdown.start);
let end = source.end.min(segment.markdown.end);
(start < end).then(|| {
segment.visible.start + start.saturating_sub(segment.markdown.start)
..segment.visible.start + end.saturating_sub(segment.markdown.start)
})
})
.collect()
}
}
fn push_retained_line_segment(
line: &str,
source: Range<usize>,
text: &mut String,
segments: &mut Vec<OffsetSegment>,
) {
if source.is_empty() {
return;
}
let visible_start = text.len();
text.push_str(&line[source.clone()]);
segments.push(OffsetSegment {
visible: visible_start..text.len(),
markdown: source,
linear: true,
});
}
struct TextPosition {
line_index: usize,
column: usize,
}
struct LineIndex {
starts: Vec<usize>,
}
impl LineIndex {
fn new(text: &str) -> Self {
let mut starts = vec![0];
starts.extend(
text.bytes()
.enumerate()
.filter_map(|(index, byte)| (byte == b'\n').then_some(index + 1)),
);
Self { starts }
}
fn count(&self) -> usize {
self.starts.len()
}
fn position(&self, text: &str, offset: usize) -> TextPosition {
let offset = offset.min(text.len());
let line_index = self.starts.partition_point(|start| *start <= offset) - 1;
let line_start = self.starts[line_index];
TextPosition {
line_index,
column: text[line_start..offset].chars().count().saturating_add(1),
}
}
fn line_index_at_byte(&self, offset: usize) -> usize {
self.starts.partition_point(|start| *start <= offset) - 1
}
fn line<'a>(&self, text: &'a str, line_index: usize) -> &'a str {
let start = self.starts[line_index];
let end = self
.starts
.get(line_index + 1)
.copied()
.unwrap_or(text.len());
text[start..end]
.strip_suffix('\n')
.unwrap_or(&text[start..end])
}
fn start(&self, line_index: usize) -> usize {
self.starts[line_index]
}
}
struct SearchableText {
text: String,
segments: Vec<OffsetSegment>,
direct_markdown: bool,
}
#[derive(Debug)]
struct OffsetSegment {
visible: Range<usize>,
markdown: Range<usize>,
linear: bool,
}
impl SearchableText {
fn new(markdown: &str, scope: SearchScope) -> Self {
if scope == SearchScope::Markdown {
return Self {
text: markdown.to_owned(),
segments: Vec::new(),
direct_markdown: true,
};
}
let mut visible = VisibleBuilder::new(markdown);
for (event, source) in Parser::new(markdown).into_offset_iter() {
match event {
Event::Text(value) | Event::InlineMath(value) | Event::DisplayMath(value) => {
visible.push_mapped(&value, source, InlineMappingKind::Text);
}
Event::Code(value) => {
visible.push_mapped(&value, source, InlineMappingKind::Code);
}
Event::SoftBreak | Event::HardBreak | Event::Rule => visible.push_break(source),
Event::End(
TagEnd::Paragraph
| TagEnd::Heading(_)
| TagEnd::Item
| TagEnd::CodeBlock
| TagEnd::TableRow,
) => visible.push_break(source.end..source.end),
Event::Start(_)
| Event::End(_)
| Event::Html(_)
| Event::InlineHtml(_)
| Event::FootnoteReference(_)
| Event::TaskListMarker(_) => {}
}
}
visible.finish()
}
fn markdown_start(&self, offset: usize) -> usize {
if self.direct_markdown {
return offset;
}
self.segment_at(offset).map_or(0, |segment| {
if segment.linear {
segment.markdown.start + offset.saturating_sub(segment.visible.start)
} else {
segment.markdown.start
}
})
}
fn markdown_end(&self, offset: usize) -> usize {
if self.direct_markdown {
return offset;
}
if offset == 0 {
return 0;
}
self.segment_at(offset - 1).map_or(0, |segment| {
if segment.linear {
segment.markdown.start + offset.saturating_sub(segment.visible.start)
} else {
segment.markdown.end
}
})
}
fn segment_at(&self, offset: usize) -> Option<&OffsetSegment> {
let index = self
.segments
.partition_point(|segment| segment.visible.end <= offset);
self.segments
.get(index)
.filter(|segment| segment.visible.contains(&offset))
}
}
struct VisibleBuilder<'a> {
markdown: &'a str,
text: String,
segments: Vec<OffsetSegment>,
}
impl<'a> VisibleBuilder<'a> {
fn new(markdown: &'a str) -> Self {
Self {
markdown,
text: String::new(),
segments: Vec::new(),
}
}
fn push_mapped(&mut self, value: &str, source: Range<usize>, kind: InlineMappingKind) {
for mapped in map_inline_characters(self.markdown, value, source, kind) {
let visible_start = self.text.len();
self.text.push(mapped.value);
let visible_end = self.text.len();
self.push_segment(OffsetSegment {
visible: visible_start..visible_end,
markdown: mapped.source,
linear: mapped.linear,
});
}
}
fn push_break(&mut self, markdown: Range<usize>) {
if self.text.ends_with('\n') || self.text.is_empty() {
return;
}
let start = self.text.len();
self.text.push('\n');
self.push_segment(OffsetSegment {
visible: start..self.text.len(),
markdown,
linear: false,
});
}
fn push_segment(&mut self, segment: OffsetSegment) {
if let Some(previous) = self.segments.last_mut() {
let contiguous = previous.visible.end == segment.visible.start
&& previous.markdown.end == segment.markdown.start
&& previous.linear
&& segment.linear;
if contiguous {
previous.visible.end = segment.visible.end;
previous.markdown.end = segment.markdown.end;
return;
}
}
self.segments.push(segment);
}
fn finish(self) -> SearchableText {
SearchableText {
text: self.text,
segments: self.segments,
direct_markdown: false,
}
}
}
#[cfg(test)]
mod tests {
use crate::ResolvedContent;
use mant_ir::{
Block, DefinitionCase, DefinitionIdentity, DefinitionItem, DefinitionRole, Document,
DocumentMeta, DocumentSource, Inline, LayoutHint, Section, SourceFormat,
};
use mant_protocol::{
MAX_SEARCH_PATTERN_CHARS, SearchCase, SearchQuery, SearchScope, SearchSyntax,
};
use super::{
LineIndex, MAX_OCCURRENCES_PER_MATCH, SearchError, display_markdown_line,
occurrence_line_ranges, render_addressable_markdown, search_query, validate_search_query,
};
fn query() -> ResolvedContent {
ResolvedContent {
address: None,
label: "demo".to_owned(),
document: Some(Document {
parser: None,
source: DocumentSource {
format: SourceFormat::Man,
path: None,
},
meta: DocumentMeta {
manual_section: Some("1".to_owned()),
..DocumentMeta::default()
},
diagnostics: Vec::new(),
blocks: Vec::new(),
sections: vec![Section {
id: "options-1".to_owned().into(),
title: "OPTIONS".to_owned(),
spacing_before_lines: 0,
blocks: vec![Block::DefinitionList {
items: vec![DefinitionItem {
inline_term: false,
identity: Some(DefinitionIdentity {
id: "option-acls".to_owned().into(),
role: DefinitionRole::Option,
case: DefinitionCase::Sensitive,
names: vec!["--acls".to_owned()],
}),
terms: vec![vec![
Inline::Anchor {
id: "option-acls".to_owned().into(),
},
Inline::Code {
value: "--acls".to_owned(),
},
]],
description: vec![Block::Paragraph {
children: vec![
Inline::Text {
value: "Preserve ".to_owned(),
},
Inline::Strong {
children: vec![Inline::Text {
value: "access control".to_owned(),
}],
},
Inline::Text {
value: " lists".to_owned(),
},
],
layout: LayoutHint::default(),
source: None,
}],
spacing_before_lines: None,
}],
compact: true,
layout: LayoutHint::default(),
source: None,
}],
children: Vec::new(),
source: None,
}],
}),
tldr: None,
}
}
fn request(pattern: &str) -> SearchQuery {
SearchQuery {
pattern: pattern.to_owned(),
syntax: SearchSyntax::Literal,
case: SearchCase::Insensitive,
scope: SearchScope::Visible,
word: false,
context_lines: 1,
limit: 100,
offset: 0,
}
}
#[test]
fn visible_search_maps_inline_formatting_to_markdown_and_option_nodes() {
let result = search_query(&query(), &request("access control")).expect("search");
assert_eq!(result.total, 1);
assert_eq!(result.matches[0].outline.node.path(), "1/e1");
assert_eq!(
result.matches[0].occurrences[0].matched_text,
"access control"
);
assert_eq!(result.matches[0].occurrences[0].line_ranges.len(), 1);
assert!(result.matches[0].occurrences[0].markdown.start_line > 1);
assert!(result.matches[0].preview.contains("**access control**"));
assert!(!result.matches[0].preview.contains("<a id="));
assert!(!result.matches[0].context.is_empty());
}
#[test]
fn presented_line_ranges_exclude_trimmed_unicode_trailing_space() {
let markdown = "zz 日本語 \nnext";
let lines = LineIndex::new(markdown);
let ranges = occurrence_line_ranges(3..15, markdown, &lines);
assert_eq!(display_markdown_line(lines.line(markdown, 0)), "zz 日本語");
assert_eq!(ranges.len(), 1);
assert_eq!(ranges[0].line, 1);
assert_eq!(ranges[0].start_byte, 3);
assert_eq!(ranges[0].end_byte, 12);
}
#[test]
fn searches_contiguous_text_across_an_unsafe_style_boundary() {
let mut query = query();
query.document.as_mut().expect("fixture document").sections[0]
.blocks
.push(Block::Paragraph {
children: vec![
Inline::Text {
value: "disabled with --".to_owned(),
},
Inline::Strong {
children: vec![Inline::Text {
value: "no-".to_owned(),
}],
},
Inline::Text {
value: "option".to_owned(),
},
],
layout: LayoutHint::default(),
source: None,
});
let visible = search_query(&query, &request("no-option")).expect("visible search");
assert_eq!(visible.total, 1);
assert_eq!(visible.matches[0].occurrences[0].matched_text, "no-option");
assert!(visible.matches[0].preview.contains("--no-option"));
assert!(!visible.matches[0].preview.contains("**no-**"));
let markdown = search_query(
&query,
&SearchQuery {
scope: SearchScope::Markdown,
..request("no-option")
},
)
.expect("Markdown search");
assert_eq!(markdown.total, 1);
assert_eq!(markdown.matches[0].occurrences[0].matched_text, "no-option");
}
#[test]
fn source_map_stripping_accepts_only_complete_empty_anchors() {
assert_eq!(
display_markdown_line("before<a id=\"node\"></a>after"),
"beforeafter"
);
assert_eq!(
display_markdown_line("before<a id=\"node\">payload</a>after"),
"before<a id=\"node\">payload</a>after"
);
assert_eq!(
display_markdown_line("before<a id=\"node\"after"),
"before<a id=\"node\"after"
);
}
#[test]
fn visible_regex_anchors_apply_to_rendered_lines_not_the_whole_document() {
for pattern in [r"^--acls", r"lists$"] {
let mut request = request(pattern);
request.syntax = SearchSyntax::Regex;
request.case = SearchCase::Sensitive;
let result = search_query(&query(), &request).expect("search");
assert_eq!(result.total, 1, "pattern {pattern:?}");
assert_eq!(result.matches[0].outline.node.path(), "1/e1");
}
}
#[test]
fn synthetic_visible_whitespace_occurrences_are_skipped_without_failing_the_query() {
for pattern in [r"\n", r"\s", r"\s+", "[[:space:]]"] {
let mut request = request(pattern);
request.syntax = SearchSyntax::Regex;
request.case = SearchCase::Sensitive;
let result = search_query(&query(), &request).expect("valid whitespace search");
assert!(
result
.matches
.iter()
.flat_map(|hit| &hit.occurrences)
.all(|occurrence| !occurrence.line_ranges.is_empty()),
"pattern {pattern:?} emitted an unpresentable occurrence"
);
}
}
#[test]
fn markdown_anchor_only_matches_do_not_become_phantom_results() {
let mut request = request("a id=");
request.scope = SearchScope::Markdown;
request.case = SearchCase::Sensitive;
let result = search_query(&query(), &request).expect("search internal anchor text");
assert_eq!(result.total, 0);
assert!(result.matches.is_empty());
}
#[test]
fn markdown_matches_crossing_an_anchor_expose_only_presented_text() {
let markdown = render_addressable_markdown(&query()).text;
let marker = "\"></a>`--acls";
assert!(
markdown.contains(marker),
"fixture anchor shape changed:\n{markdown}"
);
let mut request = request(marker);
request.scope = SearchScope::Markdown;
request.case = SearchCase::Sensitive;
let result = search_query(&query(), &request).expect("search across source-map anchor");
let occurrence = &result.matches[0].occurrences[0];
assert_eq!(occurrence.matched_text, "`--acls");
assert!(!occurrence.line_ranges.is_empty());
assert!(!result.matches[0].preview.contains("<a id="));
}
#[test]
fn visible_search_maps_padded_code_span_content_not_its_delimiters() {
for value in ["`x", "x`", " x", "x ", "`x`"] {
let mut query = query();
let Block::DefinitionList { items, .. } =
&mut query.document.as_mut().expect("manual").sections[0].blocks[0]
else {
panic!("fixture contains a definition list");
};
items[0].description = vec![Block::Paragraph {
children: vec![Inline::Code {
value: value.to_owned(),
}],
layout: LayoutHint::default(),
source: None,
}];
let markdown = render_addressable_markdown(&query).text;
let result = search_query(&query, &request(value)).expect("search");
let occurrence = &result.matches[0].occurrences[0];
let start = usize::try_from(occurrence.markdown.start_byte).expect("small fixture");
let end = usize::try_from(occurrence.markdown.end_byte).expect("small fixture");
assert_eq!(&markdown[start..end], value, "code value {value:?}");
assert_eq!(occurrence.line_ranges.len(), 1, "code value {value:?}");
let line = &occurrence.line_ranges[0];
let line_start = usize::try_from(line.start_byte).expect("small fixture");
let line_end = usize::try_from(line.end_byte).expect("small fixture");
assert_eq!(
&result.matches[0].preview[line_start..line_end],
value,
"code value {value:?}"
);
}
}
#[test]
fn visible_search_maps_an_explicit_line_break_to_its_markdown_byte() {
let mut query = query();
let Block::DefinitionList { items, .. } =
&mut query.document.as_mut().expect("manual").sections[0].blocks[0]
else {
panic!("fixture contains a definition list");
};
items[0].description = vec![Block::Paragraph {
children: vec![
Inline::Text {
value: "alpha".to_owned(),
},
Inline::LineBreak,
Inline::Text {
value: "beta".to_owned(),
},
],
layout: LayoutHint::default(),
source: None,
}];
let markdown = render_addressable_markdown(&query).text;
let result = search_query(&query, &request("alpha\n")).expect("search");
let occurrence = &result.matches[0].occurrences[0];
let start = usize::try_from(occurrence.markdown.start_byte).expect("small fixture");
let end = usize::try_from(occurrence.markdown.end_byte).expect("small fixture");
assert_eq!(&markdown[start..end], "alpha \n");
}
#[test]
fn same_line_occurrences_form_one_paginated_search_result() {
let mut query = query();
let Block::DefinitionList { items, .. } =
&mut query.document.as_mut().expect("manual").sections[0].blocks[0]
else {
panic!("fixture contains a definition list");
};
items[0].description = vec![Block::Paragraph {
children: vec![Inline::Text {
value: "needle, then another needle on one line".to_owned(),
}],
layout: LayoutHint::default(),
source: None,
}];
let mut request = request("needle");
request.limit = 1;
let result = search_query(&query, &request).expect("search");
assert_eq!(result.total, 1);
assert_eq!(result.returned, 1);
assert_eq!(result.matches[0].occurrences.len(), 2);
assert_eq!(
result.matches[0].occurrences[0].markdown.start_line,
result.matches[0].occurrences[1].markdown.start_line
);
assert!(!result.truncated);
}
#[test]
fn one_repetitive_line_has_bounded_occurrence_details() {
let mut query = query();
let Block::DefinitionList { items, .. } =
&mut query.document.as_mut().expect("manual").sections[0].blocks[0]
else {
panic!("fixture contains a definition list");
};
let occurrence_count = MAX_OCCURRENCES_PER_MATCH + 7;
items[0].description = vec![Block::Paragraph {
children: vec![Inline::Text {
value: vec!["needle"; occurrence_count].join(" "),
}],
layout: LayoutHint::default(),
source: None,
}];
let result = search_query(&query, &request("needle")).expect("search");
assert_eq!(result.total, 1);
assert_eq!(
result.matches[0].occurrence_count,
u32::try_from(occurrence_count).expect("small fixture")
);
assert_eq!(
result.matches[0].occurrences.len(),
MAX_OCCURRENCES_PER_MATCH
);
assert!(result.matches[0].occurrences_truncated);
}
#[test]
fn semantic_entry_ownership_ends_before_a_following_section_paragraph() {
let mut query = query();
query.document.as_mut().expect("manual").sections[0]
.blocks
.push(Block::Paragraph {
children: vec![Inline::Text {
value: "General section tail".to_owned(),
}],
layout: LayoutHint::default(),
source: None,
});
let result = search_query(&query, &request("section tail")).expect("search");
assert!(matches!(
&result.matches[0].outline.node,
mant_protocol::OutlineNodeReference::DocumentSection { path, .. } if path == "1"
));
}
#[test]
fn root_content_search_resolves_to_an_addressable_document_root() {
let mut query = query();
let document = query.document.as_mut().expect("document");
document.source.format = SourceFormat::Markdown;
document.blocks.push(Block::Paragraph {
children: vec![Inline::Text {
value: "Read the preface needle first.".to_owned(),
}],
layout: LayoutHint::default(),
source: None,
});
let result = search_query(&query, &request("preface needle")).expect("root search");
assert_eq!(result.total, 1);
assert!(matches!(
&result.matches[0].outline.node,
mant_protocol::OutlineNodeReference::DocumentRoot { path, id, .. }
if path == "root" && id == "document-overview"
));
assert!(result.matches[0].outline.ancestors.is_empty());
assert!(result.matches[0].preview.contains("preface needle"));
}
#[test]
fn embedded_tldr_and_markdown_body_keep_distinct_search_owners() {
let query = crate::query_markdown_text(
"\
<!-- mant:tldr:start -->
# demo
> Quick needle.
- Run:
`demo quick-command`
<!-- mant:tldr:end -->
# Demo
Read the overview needle.
## Synopsis
Manual needle.
",
Some("demo.md".to_owned()),
)
.expect("Markdown query");
let quick = search_query(&query, &request("quick needle")).expect("tldr search");
assert!(matches!(
&quick.matches[0].outline.node,
mant_protocol::OutlineNodeReference::Tldr { path, id, .. }
if path == "0" && id == "tldr"
));
let overview = search_query(&query, &request("overview needle")).expect("root search");
assert!(matches!(
&overview.matches[0].outline.node,
mant_protocol::OutlineNodeReference::DocumentRoot { path, .. } if path == "root"
));
let manual = search_query(&query, &request("manual needle")).expect("section search");
assert!(matches!(
&manual.matches[0].outline.node,
mant_protocol::OutlineNodeReference::DocumentSection { path, id, .. }
if path == "1" && id == "synopsis"
));
}
#[test]
fn regex_case_and_pagination_are_reported_without_losing_global_ordinals() {
let mut request = request("ACLS|control");
request.syntax = SearchSyntax::Regex;
request.case = SearchCase::Insensitive;
request.limit = 1;
request.offset = 1;
let result = search_query(&query(), &request).expect("search");
assert_eq!(result.total, 2);
assert_eq!(result.returned, 1);
assert_eq!(result.matches[0].ordinal, 2);
assert!(!result.truncated);
}
#[test]
fn regexes_that_match_empty_text_are_rejected() {
for pattern in ["$", r"\b", r"\B", "a*"] {
let mut request = request(pattern);
request.syntax = SearchSyntax::Regex;
let error = search_query(&query(), &request).expect_err("empty regex match");
assert!(
error.to_string().contains("must not match empty text"),
"pattern {pattern:?}: {error}"
);
}
}
#[test]
fn search_results_never_cross_addressable_owner_boundaries() {
let mut query = query();
query
.document
.as_mut()
.expect("document")
.sections
.push(Section {
id: "next".into(),
title: "NEXT".to_owned(),
spacing_before_lines: 0,
blocks: vec![Block::Paragraph {
children: vec![Inline::Text {
value: "Following owner".to_owned(),
}],
layout: LayoutHint::default(),
source: None,
}],
children: Vec::new(),
source: None,
});
let mut request = request(r"lists(?s:.*?)NEXT");
request.syntax = SearchSyntax::Regex;
request.scope = SearchScope::Markdown;
request.case = SearchCase::Sensitive;
let result = search_query(&query, &request).expect("bounded owner search");
assert_eq!(result.total, 0);
}
#[test]
fn exclusive_newline_end_does_not_mark_the_following_context_line() {
let mut query = query();
query.document.as_mut().expect("document").sections[0]
.blocks
.push(Block::Paragraph {
children: vec![
Inline::Text {
value: "alpha".to_owned(),
},
Inline::LineBreak,
Inline::Text {
value: "beta".to_owned(),
},
],
layout: LayoutHint::default(),
source: None,
});
let mut request = request("alpha \n");
request.scope = SearchScope::Markdown;
request.case = SearchCase::Sensitive;
let result = search_query(&query, &request).expect("newline search");
let hit = &result.matches[0];
let occurrence = &hit.occurrences[0];
assert_eq!(occurrence.line_ranges.len(), 1);
let following = hit
.context
.iter()
.find(|line| line.line == occurrence.markdown.end_line)
.expect("following context line");
assert!(!following.matched);
}
#[test]
fn multibyte_match_ends_remain_valid_coordinate_boundaries() {
let mut query = query();
query.document.as_mut().expect("document").sections[0]
.blocks
.push(Block::Paragraph {
children: vec![Inline::Text {
value: "café — 日本".to_owned(),
}],
layout: LayoutHint::default(),
source: None,
});
let mut request = request("—");
request.case = SearchCase::Sensitive;
let result = search_query(&query, &request).expect("Unicode search");
let occurrence = &result.matches[0].occurrences[0];
assert_eq!(occurrence.matched_text, "—");
assert_eq!(
occurrence.markdown.end_column,
occurrence.markdown.start_column + 1
);
}
#[test]
fn byte_mode_regexes_are_rejected_before_matching_unicode_text() {
let mut request = request("(?-u:.)");
request.syntax = SearchSyntax::Regex;
let error = search_query(&query(), &request).expect_err("byte-oriented regex");
assert!(error.to_string().contains("UTF-8 character boundaries"));
}
#[test]
fn regex_syntax_errors_retain_their_actual_cause() {
for (pattern, expected) in [
("(", "unclosed group"),
("a{2,1}", "invalid repetition count range"),
("[z-a]", "invalid character class range"),
] {
let mut request = request(pattern);
request.syntax = SearchSyntax::Regex;
let error = validate_search_query(&request).expect_err("invalid regex");
let message = error.to_string();
assert!(message.contains(expected), "{pattern}: {message}");
assert!(!message.contains("Unicode mode cannot be disabled"));
}
}
#[test]
fn compiled_regex_programs_use_the_project_resource_budget() {
let mut oversized = request("((a{100}){100}){100}");
oversized.syntax = SearchSyntax::Regex;
let error = validate_search_query(&oversized).expect_err("reject oversized regex program");
assert_eq!(
error,
SearchError::InvalidPattern(
"regular expression exceeds ManT's compiled-size limit".to_owned()
)
);
let mut ordinary = request("needle|ordinary");
ordinary.syntax = SearchSyntax::Regex;
assert_eq!(validate_search_query(&ordinary), Ok(()));
}
#[test]
fn search_pattern_limit_counts_unicode_scalars() {
let valid = request(&"界".repeat(MAX_SEARCH_PATTERN_CHARS));
assert_eq!(validate_search_query(&valid), Ok(()));
let request = request(&"界".repeat(MAX_SEARCH_PATTERN_CHARS + 1));
assert_eq!(
validate_search_query(&request),
Err(SearchError::PatternTooLong)
);
}
}