markdown_link/spanned.rs
1//! The body link scanner: every link in a body, with its byte span.
2//!
3//! [`crate::body_links`] is this scanner with the spans dropped.
4//! [`scan_body_with`] also reports each `[[` it gave up on, so a caller can
5//! flag link syntax that was left in the text. The rules for
6//! a markdown link are delegated ([`crate::is_vault_link_url`],
7//! [`crate::md_link_target`]) rather than restated: two spellings of "is this
8//! a link" is how two scanners start disagreeing about what the vault
9//! contains.
10
11use crate::code::{CodeRules, strip_code_with};
12use crate::{Size, is_vault_link_url, md_link_target, parse_inner, parse_inner_self};
13
14/// What a body scan counts as a link. [`ScanOptions::default`] is what
15/// [`body_links_spanned`] and [`crate::body_links`] use.
16///
17/// # Examples
18///
19/// ```
20/// use markdown_link::code::CodeRules;
21/// use markdown_link::{ScanOptions, body_links_spanned_with};
22///
23/// let options = ScanOptions {
24/// code_rules: CodeRules::SkillExport,
25/// skip_html_comments: true,
26/// self_links: true,
27/// };
28/// let links = body_links_spanned_with("<!-- [[hidden]] --> [[#Intro]]", &options);
29/// assert_eq!(links.len(), 1);
30/// assert_eq!(links[0].target, "");
31/// assert_eq!(links[0].heading.as_deref(), Some("Intro"));
32/// ```
33#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
34pub struct ScanOptions {
35 /// Which rules decide what is code. Links in code are not links.
36 pub code_rules: CodeRules,
37 /// Skip links inside HTML comments, `<!--` to `-->` or the end of the
38 /// body. Off by default: a comment's links are found.
39 pub skip_html_comments: bool,
40 /// Read a wikilink with no target and a `#` fragment, `[[#Heading]]` or
41 /// `[[#^block]]`, as a link to the note it is written in, with an empty
42 /// [`BodyLink::target`]. Off by default: such a link is dropped.
43 pub self_links: bool,
44}
45
46/// What syntax produced a [`BodyLink`].
47///
48/// Not the same three as [`crate::LinkKind`]: this scanner reads bodies only,
49/// so there is no `Frontmatter`, and it harvests relative markdown links, which
50/// the bracket dialect has no variant for.
51#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
52pub enum BodyLinkKind {
53 /// A `[[target]]` link.
54 Wikilink,
55 /// A `![[target]]` embed.
56 Embed,
57 /// A relative markdown link, `[text](path)`.
58 Markdown,
59}
60
61/// One outgoing reference found in a body, with its span, before resolution.
62///
63/// Separate from a resolved link because extraction and resolution have
64/// different lifetimes: a note's links change when the note is edited, and what
65/// they *resolve to* changes when any other note in the vault is created or
66/// renamed. A caller that caches the first and recomputes the second needs
67/// them to be two types.
68#[derive(Debug, Clone, PartialEq, Eq)]
69pub struct BodyLink {
70 /// Which syntax produced the link.
71 pub kind: BodyLinkKind,
72 /// The reference as written between the delimiters, with any code inside it
73 /// blanked to spaces.
74 pub raw: String,
75 /// What resolution runs against. A wikilink's `raw` minus `#heading` /
76 /// `^block` / `|alias` and the `\` escaping the pipe; a markdown link's URL
77 /// percent-decoded and minus a trailing `.md`. Empty for a link to the
78 /// note it is written in (see [`ScanOptions::self_links`]).
79 pub target: String,
80 /// A wikilink's `#heading`, as [`crate::WikiLink::heading`]. `None` for a
81 /// markdown link.
82 pub heading: Option<String>,
83 /// A wikilink's `#^block`, as [`crate::WikiLink::block`]. `None` for a
84 /// markdown link.
85 pub block: Option<String>,
86 /// A wikilink's or embed's `|alias`: the text after the first `|` outside
87 /// code, read from the body so code inside it is kept. `None` when there
88 /// is none or it is empty, and for a markdown link.
89 pub alias: Option<String>,
90 /// An embed's size, `|300` or `|300x200`, as [`crate::WikiLink::size`].
91 pub size: Option<Size>,
92 /// Byte offset within the **body** where the whole link syntax starts. An
93 /// embed's leading `!` is inside it.
94 pub byte_start: usize,
95 /// Byte offset within the **body** just past the end of the link syntax.
96 pub byte_end: usize,
97}
98
99/// Why the scanner gave up on a `[[`. See [`AbandonedLink`].
100#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
101pub enum AbandonReason {
102 /// A `[` or `]` came before the closing `]]`: `[[` never nests, so
103 /// `[[a [1]]]` and `[[x]y]]` are not links.
104 Bracket,
105 /// Closed, but the target is empty once the code inside it is blanked:
106 /// ``[[`Note`]]``.
107 Code,
108 /// Closed with an empty target: `[[]]`, `[[ |alias]]`, or `[[#Heading]]`
109 /// when [`ScanOptions::self_links`] is off.
110 EmptyTarget,
111 /// No `]]` before the end of the body.
112 Unclosed,
113}
114
115/// A `[[` the scanner found outside code and did not read as a link.
116///
117/// What a renderer or a publisher would otherwise leave in its output as
118/// literal brackets. A `[[` inside code, or inside an HTML comment when
119/// [`ScanOptions::skip_html_comments`] is on, is not reported, and nor is one
120/// that a link found after it starts inside: `[[[Note]]` is a literal `[`
121/// and a link. A run of `[` with no link after it, such as `[[[TODO`, is
122/// one entry: from the first `[[`, with the reason and end of the last.
123#[derive(Debug, Clone, PartialEq, Eq)]
124pub struct AbandonedLink {
125 /// Why it is not a link.
126 pub reason: AbandonReason,
127 /// Whether a `!` came before the `[[`.
128 pub embed: bool,
129 /// Byte offset within the **body** of the `[[`, or of the `!` before it.
130 pub byte_start: usize,
131 /// Byte offset just past what the scanner read: past the `]]` for
132 /// [`AbandonReason::Code`] and [`AbandonReason::EmptyTarget`], up to the
133 /// `[` or `]` it stopped at for [`AbandonReason::Bracket`], and the end of
134 /// the body for [`AbandonReason::Unclosed`].
135 pub byte_end: usize,
136}
137
138/// What [`scan_body_with`] found: the links, and the `[[` it gave up on.
139#[derive(Debug, Clone, Default, PartialEq, Eq)]
140pub struct BodyScan {
141 /// The links, as [`body_links_spanned_with`] returns them.
142 pub links: Vec<BodyLink>,
143 /// Each `[[` that is not a link, in encounter order.
144 pub abandoned: Vec<AbandonedLink>,
145}
146
147/// Every wikilink, embed and relative markdown link in a body, in encounter
148/// order, **with byte spans**.
149///
150/// Code is blanked before matching, `[[` never nests, and a markdown link
151/// counts only when `is_vault_link_url` accepts its URL and it carries no
152/// scheme. The span is what an editor decoration, a hover preview and a
153/// rename's link rewrite need: which bytes to touch.
154///
155/// # Why the offsets need a char table
156///
157/// [`crate::strip_code`] preserves the **character** count of its input, not the byte
158/// count — a multi-byte char inside a code span comes back as a one-byte space.
159/// So a position found in the stripped text is a valid char index into the
160/// original and never a valid byte index, and the two tables below are what
161/// convert. Scanning the original directly is not an option: that is how
162/// `[[example]]` inside a fenced block becomes a link.
163///
164/// # Examples
165///
166/// ```
167/// use markdown_link::{BodyLinkKind, body_links_spanned};
168///
169/// let body = "é ![[img.png|300]] and [[Note#h|alias]]";
170/// let links = body_links_spanned(body);
171/// assert_eq!(links.len(), 2);
172/// assert_eq!(links[0].kind, BodyLinkKind::Embed);
173/// assert_eq!(links[0].target, "img.png");
174/// assert_eq!(&body[links[0].byte_start..links[0].byte_end], "![[img.png|300]]");
175/// assert_eq!(links[1].alias.as_deref(), Some("alias"));
176/// assert_eq!(&body[links[1].byte_start..links[1].byte_end], "[[Note#h|alias]]");
177/// ```
178pub fn body_links_spanned(body: &str) -> Vec<BodyLink> {
179 body_links_spanned_with(body, &ScanOptions::default())
180}
181
182/// [`body_links_spanned`] under `options`: which code rules apply, whether
183/// HTML comments hide links, and whether `[[#Heading]]` is a link.
184///
185/// A comment is found after code is blanked, so a `<!--` inside code does not
186/// open one.
187pub fn body_links_spanned_with(body: &str, options: &ScanOptions) -> Vec<BodyLink> {
188 scan_body_with(body, options).links
189}
190
191/// [`body_links_spanned_with`], and each `[[` it gave up on
192/// ([`AbandonedLink`]): one holding a `[` or `]`, one whose target is empty
193/// or only code, and one never closed.
194///
195/// # Examples
196///
197/// ```
198/// use markdown_link::{AbandonReason, ScanOptions, scan_body_with};
199///
200/// let body = "[[Note]] [[a [1]]] [[]]";
201/// let scan = scan_body_with(body, &ScanOptions::default());
202/// assert_eq!(scan.links.len(), 1);
203/// let reasons: Vec<_> = scan.abandoned.iter().map(|a| a.reason).collect();
204/// assert_eq!(reasons, [AbandonReason::Bracket, AbandonReason::EmptyTarget]);
205/// let first = &scan.abandoned[0];
206/// assert_eq!(&body[first.byte_start..first.byte_end], "[[a ");
207/// ```
208pub fn scan_body_with(body: &str, options: &ScanOptions) -> BodyScan {
209 let code_blanked = strip_code_with(body, options.code_rules);
210 let comments_blanked = options
211 .skip_html_comments
212 .then(|| blank_comments(&code_blanked));
213 let chars: Vec<char> = comments_blanked
214 .as_deref()
215 .unwrap_or(&code_blanked)
216 .chars()
217 .collect();
218 // With comments blanked too, the chars with only code blanked, made the
219 // first time an abandoned link needs them.
220 let mut code_chars: Option<Vec<char>> = None;
221 // char index -> byte offset, in the ORIGINAL body, plus an end sentinel so
222 // an exclusive range that runs to the end of the body is representable.
223 let mut at: Vec<usize> = body.char_indices().map(|(i, _)| i).collect();
224 at.push(body.len());
225 if chars.len() + 1 != at.len() {
226 // `strip_code` must preserve the char count. If it ever does not,
227 // reporting no links beats reporting spans that index the wrong bytes
228 // and would splice mid-character.
229 return BodyScan::default();
230 }
231
232 let mut out = Vec::new();
233 let mut abandoned = Vec::new();
234 let mut scan = UrlScan::default();
235 let mut i = 0usize;
236 while i < chars.len() {
237 if chars[i] == '[' && chars.get(i + 1) == Some(&'[') {
238 let embed = i > 0 && chars[i - 1] == '!';
239 let start = at[if embed { i - 1 } else { i }];
240 let mut j = i + 2;
241 let mut inner = String::new();
242 let mut closed = false;
243 let mut bracket = false;
244 while j + 1 < chars.len() {
245 if chars[j] == ']' && chars[j + 1] == ']' {
246 closed = true;
247 break;
248 }
249 // `[[` never nests, and `[`/`]` inside would be a malformed
250 // link — bail rather than swallow the rest of the note.
251 if chars[j] == '[' || chars[j] == ']' {
252 bracket = true;
253 break;
254 }
255 inner.push(chars[j]);
256 j += 1;
257 }
258 if !closed {
259 abandoned.push(AbandonedLink {
260 reason: if bracket {
261 AbandonReason::Bracket
262 } else {
263 AbandonReason::Unclosed
264 },
265 embed,
266 byte_start: start,
267 byte_end: if bracket { at[j] } else { body.len() },
268 });
269 }
270 if closed {
271 let parsed = if inner.is_empty() {
272 None
273 } else if options.self_links {
274 parse_inner_self(&inner, embed)
275 } else {
276 parse_inner(&inner, embed)
277 };
278 if parsed.is_none() {
279 // Code inside was blanked to spaces, so the body's bytes
280 // there differ from the code-blanked chars. A blanked
281 // comment is not code.
282 let code = match comments_blanked {
283 Some(_) => code_chars
284 .get_or_insert_with(|| code_blanked.chars().collect())
285 .as_slice(),
286 None => chars.as_slice(),
287 };
288 let held_code = body[at[i + 2]..at[j]]
289 .chars()
290 .ne(code[i + 2..j].iter().copied());
291 abandoned.push(AbandonedLink {
292 reason: if held_code {
293 AbandonReason::Code
294 } else {
295 AbandonReason::EmptyTarget
296 },
297 embed,
298 byte_start: start,
299 byte_end: at[j + 2],
300 });
301 }
302 if let Some(link) = parsed {
303 // Split at the pipe `parse_inner` used, found in the
304 // stripped chars so a `|` in code is not one, then read
305 // the alias from the body so code inside it is kept.
306 let alias = chars[i + 2..j]
307 .iter()
308 .position(|&c| c == '|')
309 .map(|p| body[at[i + 3 + p]..at[j]].trim())
310 .filter(|alias| !alias.is_empty())
311 .map(str::to_string);
312 drop_overlapped(&mut abandoned, at[i]);
313 out.push(BodyLink {
314 kind: if embed {
315 BodyLinkKind::Embed
316 } else {
317 BodyLinkKind::Wikilink
318 },
319 raw: inner,
320 target: link.target,
321 heading: link.heading,
322 block: link.block,
323 size: link.size,
324 alias,
325 // An embed's `!` is part of the syntax a rename has to
326 // rewrite, so it is inside the span.
327 byte_start: start,
328 byte_end: at[j + 2],
329 });
330 }
331 i = j + 2;
332 continue;
333 }
334 }
335 if chars[i] == '['
336 && let Some(link) = spanned_markdown_link(&chars, i, &at, &mut scan)
337 {
338 drop_overlapped(&mut abandoned, at[i]);
339 i = link.1;
340 out.push(link.0);
341 continue;
342 }
343 i += 1;
344 }
345 BodyScan {
346 links: out,
347 abandoned: merge_runs(abandoned),
348 }
349}
350
351/// Folds each abandoned `[[` that starts inside the one before it into that
352/// one, so a run of `[` such as `[[[TODO` is one entry: from the first `[[`,
353/// with the reason and end of the last. As in [`drop_overlapped`], an
354/// embed's `!` does not count: in `[[x![[y` the embed is its own entry.
355fn merge_runs(abandoned: Vec<AbandonedLink>) -> Vec<AbandonedLink> {
356 let mut out: Vec<AbandonedLink> = Vec::with_capacity(abandoned.len());
357 for next in abandoned {
358 match out.last_mut() {
359 Some(run) if next.byte_start + usize::from(next.embed) < run.byte_end => {
360 run.reason = next.reason;
361 run.byte_end = next.byte_end;
362 }
363 _ => out.push(next),
364 }
365 }
366 out
367}
368
369/// Drops each abandoned `[[` whose second `[` opens a link: `bracket` is the
370/// byte offset of the link's first `[`, after any `!`. After a `[` or `]` the
371/// scanner moves on one char, so `[[[Note]]` is a literal `[` and a link,
372/// not a `[[` given up on. An embed's `!` right after an abandoned `[[`, as
373/// in `[[x![[B]]`, does not count.
374fn drop_overlapped(abandoned: &mut Vec<AbandonedLink>, bracket: usize) {
375 while abandoned
376 .last()
377 .is_some_and(|a| a.byte_start + usize::from(a.embed) + 2 > bracket)
378 {
379 abandoned.pop();
380 }
381}
382
383/// `text` with every HTML comment, `<!--` to `-->` or the end, blanked to
384/// spaces, newlines kept. The character count does not change.
385fn blank_comments(text: &str) -> String {
386 let mut out = String::with_capacity(text.len());
387 let mut rest = text;
388 while let Some(open) = rest.find("<!--") {
389 out.push_str(&rest[..open]);
390 let after = &rest[open + 4..];
391 let end = after.find("-->").map_or(rest.len(), |at| open + 4 + at + 3);
392 out.extend(
393 rest[open..end]
394 .chars()
395 .map(|c| if c == '\n' { '\n' } else { ' ' }),
396 );
397 rest = &rest[end..];
398 }
399 out.push_str(rest);
400 out
401}
402
403/// `[text](relative/note.md)` starting at `start`, and the char index just
404/// past it. `None` when this is not one.
405///
406/// The shape is the regex `\[[^\]]*\]\(<?([^)>\s]+?)>?\)`, walked by hand so
407/// positions index the original body. [`is_vault_link_url`] decides "is this a
408/// reference" and [`md_link_target`] "what does it point at". A URL containing
409/// whitespace is not a link: `[c](<sp ace.md>)` matches nothing. The URL is
410/// read in place and built only for a link, so a body of failed attempts
411/// stays linear.
412fn spanned_markdown_link(
413 chars: &[char],
414 start: usize,
415 at: &[usize],
416 scan: &mut UrlScan,
417) -> Option<(BodyLink, usize)> {
418 let mut j = start + 1;
419 while j < chars.len() && chars[j] != ']' && chars[j] != '[' {
420 j += 1;
421 }
422 if chars.get(j) != Some(&']') || chars.get(j + 1) != Some(&'(') {
423 return None;
424 }
425 let angled = chars.get(j + 2) == Some(&'<');
426 let url_start = if angled { j + 3 } else { j + 2 };
427 let url_end = scan.url_end(chars, url_start);
428 let mut end = url_end;
429 if angled {
430 if chars.get(end) != Some(&'>') {
431 return None;
432 }
433 end += 1;
434 }
435 if chars.get(end) != Some(&')') {
436 return None;
437 }
438 end += 1;
439 if !scan.is_vault_link(chars, url_start, url_end) || has_scheme(&chars[url_start..url_end]) {
440 // Not a link this dialect harvests. The caller advances ONE character
441 // rather than skipping past the `[text](…)` it just walked, so a match
442 // may start at an inner `[`: `[a[b](x.md)` is a link.
443 return None;
444 }
445 let url: String = chars[url_start..url_end].iter().collect();
446 Some((
447 BodyLink {
448 kind: BodyLinkKind::Markdown,
449 target: md_link_target(&url),
450 heading: None,
451 block: None,
452 alias: None,
453 size: None,
454 raw: url,
455 byte_start: at[start],
456 byte_end: at[end],
457 },
458 end,
459 ))
460}
461
462/// What earlier markdown link attempts learned about the URLs they read. Each
463/// attempt starts later than the one before, so remembering the last answer
464/// of each kind keeps a body of failed attempts linear.
465#[derive(Debug, Default)]
466struct UrlScan {
467 /// `(from, stop)`: the first `)`, `>` or whitespace at or after `from` is
468 /// at `stop`.
469 stop: Option<(usize, usize)>,
470 tail: Option<UrlTail>,
471}
472
473/// URLs ending at `end`: the last `.` or `/` at or after `from`, and
474/// [`is_vault_link_url`] of each tail asked so far, by its start.
475#[derive(Debug)]
476struct UrlTail {
477 end: usize,
478 from: usize,
479 mark: Option<usize>,
480 answers: Vec<(usize, bool)>,
481}
482
483impl UrlScan {
484 /// Where a URL starting at `from` ends: the first `)`, `>` or whitespace.
485 fn url_end(&mut self, chars: &[char], from: usize) -> usize {
486 if let Some((start, stop)) = self.stop
487 && (start..=stop).contains(&from)
488 {
489 return stop;
490 }
491 let mut k = from;
492 while k < chars.len() && !matches!(chars[k], ')' | '>') && !chars[k].is_whitespace() {
493 k += 1;
494 }
495 self.stop = Some((from, k));
496 k
497 }
498
499 /// [`is_vault_link_url`] of `chars[from..end]`. That answer depends only
500 /// on whether the URL ends in `.md` after at least one character and on
501 /// the extension of its last segment. So the URL from the character before
502 /// its last `.` gives the same answer, and that tail is shared by every
503 /// attempt ending at `end`.
504 fn is_vault_link(&mut self, chars: &[char], from: usize, end: usize) -> bool {
505 let tail = match &mut self.tail {
506 Some(tail) if tail.end == end && tail.from <= from => tail,
507 slot => slot.insert(UrlTail {
508 end,
509 from,
510 mark: chars[from..end]
511 .iter()
512 .rposition(|c| matches!(c, '.' | '/'))
513 .map(|i| from + i),
514 answers: Vec::new(),
515 }),
516 };
517 let Some(mark) = tail.mark.filter(|&mark| mark >= from && chars[mark] == '.') else {
518 return false;
519 };
520 let tail_start = from.max(mark.saturating_sub(1));
521 if let Some(&(_, answer)) = tail.answers.iter().find(|(at, _)| *at == tail_start) {
522 return answer;
523 }
524 let answer = is_vault_link_url(&chars[tail_start..end].iter().collect::<String>());
525 tail.answers.push((tail_start, answer));
526 answer
527 }
528}
529
530/// `http:`, `mailto:`, an app-specific scheme — anything with a URI scheme is external.
531fn has_scheme(url: &[char]) -> bool {
532 let mut chars = url.iter();
533 match chars.next() {
534 Some(c) if c.is_ascii_alphabetic() => {}
535 _ => return false,
536 }
537 for &c in chars {
538 if c == ':' {
539 return true;
540 }
541 if !(c.is_ascii_alphanumeric() || c == '+' || c == '.' || c == '-') {
542 return false;
543 }
544 }
545 false
546}
547
548#[cfg(test)]
549mod tests {
550 use super::*;
551
552 /// A quadratic URL scan takes tens of seconds on the largest of these in a
553 /// debug build; a linear one takes well under a second, even on a loaded
554 /// machine. The bound is that wide on purpose: it catches the shape of the
555 /// cost, not a slowdown.
556 #[test]
557 fn the_url_scan_is_linear_in_failed_link_attempts() {
558 for n in [25_000, 50_000, 100_000] {
559 for body in [
560 "[](a".repeat(n),
561 format!("{})", "[](a".repeat(n)),
562 format!("{}.md)", "[](a:".repeat(n)),
563 format!("{}.x)", "[](a/".repeat(n)),
564 ] {
565 let started = std::time::Instant::now();
566 assert!(body_links_spanned(&body).is_empty());
567 let elapsed = started.elapsed();
568 assert!(
569 elapsed < std::time::Duration::from_secs(10),
570 "{} KB took {elapsed:?}",
571 body.len() / 1000
572 );
573 }
574 }
575 }
576}