use std::borrow::Cow;
use std::cell::OnceCell;
use std::ops::Range;
pub const MAX_NESTING_DEPTH: usize = 128;
pub const MAX_HEADING_LEVEL: usize = u16::MAX as usize - 2 * MAX_NESTING_DEPTH;
pub const MAX_LEAF_LINES: usize = 16_384;
const LEAF_LINES_ON_THE_CALLERS_STACK: usize = 128;
const PARSER_STACK: usize = 2 << 20;
const STACK_PER_LEAF_LINE: usize = 8 << 10;
pub const FLATTENED_INDENT_COLUMNS: usize = 4 * super::list_depth::MAX_LIST_INDENT as usize;
pub fn nesting_depth(text: &str) -> usize {
deepest(text, usize::MAX)
}
pub fn is_too_deep(text: &str) -> bool {
let reach = reach(text, MAX_NESTING_DEPTH, MAX_HEADING_LEVEL, usize::MAX);
reach.depth > MAX_NESTING_DEPTH || reach.heading > MAX_HEADING_LEVEL
}
pub fn longest_leaf_lines(text: &str) -> usize {
reach(text, usize::MAX, usize::MAX, usize::MAX).longest_leaf
}
#[doc(hidden)]
pub fn crlf_to_lf(text: &str) -> Cow<'_, str> {
if text.contains("\r\n") {
Cow::Owned(text.replace("\r\n", "\n"))
} else {
Cow::Borrowed(text)
}
}
pub fn parsable(text: &str) -> Option<Parsable<'_>> {
let mut text = Cow::Borrowed(text);
let mut flattened = false;
let mut set_down = false;
loop {
let reach = reach(&text, MAX_NESTING_DEPTH, usize::MAX, MAX_LEAF_LINES);
if !reach.overlong_headings.is_empty() {
text = Cow::Owned(escape_at(&text, &reach.overlong_headings)?);
} else if reach.depth > MAX_NESTING_DEPTH {
if flattened {
return None;
}
text = Cow::Owned(flatten_deep_indentation(&text));
flattened = true;
} else if !reach.long_blocks.is_empty() {
if set_down {
return None;
}
text = Cow::Owned(set_down_as_lines(&text, &reach.long_blocks)?);
set_down = true;
} else {
return Some(Parsable {
text,
longest_leaf: reach.longest_leaf,
on_the_callers_stack: OnceCell::new(),
});
}
}
}
#[derive(Debug)]
pub struct Parsable<'a> {
text: Cow<'a, str>,
longest_leaf: usize,
on_the_callers_stack: OnceCell<Option<String>>,
}
type ReadOnAThread = for<'t> fn(&'t str, usize) -> std::io::Result<Option<Vec<jotdown::Event<'t>>>>;
impl Parsable<'_> {
pub fn text(&self) -> &str {
&self.text
}
pub fn events(&self) -> Option<DjotEvents<'_>> {
self.events_read_by(read_on_a_thread)
}
fn events_read_by(&self, read: ReadOnAThread) -> Option<DjotEvents<'_>> {
let text: &str = &self.text;
if self.longest_leaf <= LEAF_LINES_ON_THE_CALLERS_STACK {
return Some(DjotEvents::streamed(text));
}
let stack = PARSER_STACK + self.longest_leaf * STACK_PER_LEAF_LINE;
match read(text, stack) {
Ok(events) => events.map(|events| DjotEvents(EventSource::Read(events.into_iter()))),
Err(error) => {
log::warn!(
"no thread with a {stack}-byte stack for a Djot block of {} lines, so every \
block longer than {LEAF_LINES_ON_THE_CALLERS_STACK} lines is read as its \
lines: {error}",
self.longest_leaf
);
self.on_the_callers_stack
.get_or_init(|| set_down_long_blocks(text, LEAF_LINES_ON_THE_CALLERS_STACK))
.as_deref()
.map(DjotEvents::streamed)
}
}
}
}
fn read_on_a_thread(text: &str, stack: usize) -> std::io::Result<Option<Vec<jotdown::Event<'_>>>> {
std::thread::scope(|scope| {
let parser = std::thread::Builder::new()
.name("djot parser".to_owned())
.stack_size(stack)
.spawn_scoped(scope, || jotdown::Parser::new(text).collect::<Vec<_>>())?;
Ok(parser.join().ok())
})
}
pub struct DjotEvents<'s>(EventSource<'s>);
enum EventSource<'s> {
Streamed(Box<jotdown::Parser<'s>>),
Read(std::vec::IntoIter<jotdown::Event<'s>>),
}
impl<'s> DjotEvents<'s> {
fn streamed(text: &'s str) -> Self {
DjotEvents(EventSource::Streamed(Box::new(jotdown::Parser::new(text))))
}
}
impl<'s> Iterator for DjotEvents<'s> {
type Item = jotdown::Event<'s>;
fn next(&mut self) -> Option<Self::Item> {
match &mut self.0 {
EventSource::Streamed(parser) => parser.next(),
EventSource::Read(events) => events.next(),
}
}
}
fn escape_at(text: &str, offsets: &[usize]) -> Option<String> {
let mut out = String::with_capacity(text.len() + offsets.len());
let mut from = 0;
for &offset in offsets {
out.push_str(text.get(from..offset)?);
out.push('\\');
from = offset;
}
out.push_str(text.get(from..)?);
Some(out)
}
fn deepest(text: &str, limit: usize) -> usize {
reach(text, limit, usize::MAX, usize::MAX).depth
}
struct Reach {
depth: usize,
heading: usize,
overlong_headings: Vec<usize>,
longest_leaf: usize,
long_blocks: Vec<Range<usize>>,
}
fn reach(text: &str, depth: usize, heading: usize, long_block: usize) -> Reach {
let mut scan = Scan {
long_block,
..Scan::default()
};
let mut deepest = 0usize;
let mut whole = true;
for line in text.split_inclusive('\n') {
scan.line_end += line.len();
deepest = deepest.max(scan.read(line.as_bytes(), depth));
if deepest > depth || scan.heading > heading {
whole = false;
break;
}
}
if whole {
scan.begin_block(text.len());
}
Reach {
depth: deepest,
heading: scan.heading,
overlong_headings: scan.overlong_headings,
longest_leaf: scan.longest_leaf,
long_blocks: scan.long_blocks,
}
}
fn set_down_long_blocks(text: &str, lines: usize) -> Option<String> {
set_down_as_lines(
text,
&reach(text, usize::MAX, usize::MAX, lines).long_blocks,
)
}
fn set_down_as_lines(text: &str, blocks: &[Range<usize>]) -> Option<String> {
let mut out = String::with_capacity(text.len() + text.len() / 4);
let mut from = 0;
for block in blocks {
out.push_str(text.get(from..block.start)?);
out.push('\n');
for line in text.get(block.clone())?.lines() {
let line = line.trim_matches(|c: char| c.is_ascii_whitespace());
if line.is_empty() {
continue;
}
for c in line.chars() {
if c.is_ascii_punctuation() {
out.push('\\');
}
out.push(c);
}
out.push_str("\n\n");
}
from = block.end;
}
out.push_str(text.get(from..)?);
Some(out)
}
pub fn flatten_deep_indentation(text: &str) -> String {
let mut out = String::with_capacity(text.len());
for line in text.split_inclusive('\n') {
let mut columns_left = FLATTENED_INDENT_COLUMNS;
let mut markers = 0usize;
let mut rest = line;
loop {
let whitespace = rest.bytes().take_while(|&byte| is_space(byte)).count();
let indent = rest[..whitespace].find(['\r', '\n']).unwrap_or(whitespace);
let keep = indent.min(columns_left);
columns_left -= keep;
out.push_str(&rest[..keep]);
out.push_str(&rest[indent..whitespace]);
let content = &rest[whitespace..];
let marker = match identify(content.as_bytes()) {
(Block::Blockquote | Block::Item { .. }, end) if markers <= MAX_NESTING_DEPTH => {
end + usize::from(content.as_bytes().get(end).is_some_and(|&b| is_space(b)))
}
_ => {
out.push_str(content);
break;
}
};
markers += 1;
out.push_str(&content[..marker]);
rest = &content[marker..];
}
}
out
}
fn is_space(byte: u8) -> bool {
byte.is_ascii_whitespace()
}
fn is_blank(view: &[u8]) -> bool {
view.iter().all(|&byte| is_space(byte))
}
fn trimmed(view: &[u8]) -> (usize, &[u8]) {
let Some(start) = view.iter().position(|&byte| !is_space(byte)) else {
return (0, &[]);
};
let end = view.len()
- view
.iter()
.rev()
.take_while(|&&byte| is_space(byte))
.count();
(start, &view[start..end])
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Block {
Blank,
Paragraph,
Heading(usize),
Atom,
Blockquote,
Item { indent: usize },
LinkDefinition,
TableRow,
Fence {
mark: u8,
len: usize,
bare: bool,
indent: usize,
},
}
fn identify(view: &[u8]) -> (Block, usize) {
let indent = view
.iter()
.take_while(|&&byte| is_space(byte) && byte != b'\n')
.count();
let line = &view[indent..];
let content = line.len()
- line
.iter()
.rev()
.take_while(|&&byte| is_space(byte))
.count();
let line_t = &line[..content];
let Some(&first) = line.first() else {
return (Block::Blank, indent);
};
let ends_marker = |at: usize| line.get(at).is_none_or(|&byte| is_space(byte));
let found = match first {
b'\n' => Some((Block::Blank, indent + 1)),
b'#' => {
let level = line.iter().take_while(|&&byte| byte == b'#').count();
ends_marker(level).then_some((Block::Heading(level), indent + level))
}
b'>' => ends_marker(1).then_some((Block::Blockquote, indent + 1)),
b'{' => (attributes_len(line) == content).then_some((Block::Atom, indent + line.len())),
b'|' => (content >= 2 && line_t.ends_with(b"|") && !line_t.ends_with(b"\\|"))
.then_some((Block::TableRow, indent)),
b'[' => definition(line).map(|(label, footnote)| {
let end = indent + 3 + label;
if footnote {
(Block::Item { indent }, end)
} else {
(Block::LinkDefinition, end)
}
}),
b'-' | b'*' if is_thematic_break(&line[1..]) => Some((Block::Atom, indent + content)),
b'-' | b'*' | b'+' => line.get(1).is_none_or(|&byte| byte == b' ').then(|| {
let task = line.get(2) == Some(&b'[')
&& matches!(line.get(3), Some(b'x' | b'X' | b' '))
&& line.get(4) == Some(&b']')
&& ends_marker(5);
(Block::Item { indent }, indent + if task { 5 } else { 1 })
}),
b':' if ends_marker(1) => Some((Block::Item { indent }, indent + 1)),
b'`' | b':' | b'~' => fence(line_t, first).map(|(len, bare)| {
(
Block::Fence {
mark: first,
len,
bare,
indent,
},
indent + line.len(),
)
}),
_ => ordered_marker(line).map(|len| (Block::Item { indent }, indent + len)),
};
found.unwrap_or((Block::Paragraph, indent))
}
fn attributes_len(line: &[u8]) -> usize {
#[derive(Clone, Copy, PartialEq, Eq)]
enum State {
Start,
Whitespace,
CommentFirst,
Comment,
CommentNewline,
ClassFirst,
Class,
IdentifierFirst,
Identifier,
Key,
ValueFirst,
Value,
ValueQuoted,
ValueEscape,
ValueNewline,
ValueContinued,
Done,
Invalid,
}
fn is_name(byte: u8) -> bool {
byte.is_ascii_alphanumeric() || matches!(byte, b':' | b'_' | b'-')
}
fn step(state: State, c: u8) -> State {
use State::*;
match state {
Start if c == b'{' => Whitespace,
Start => Invalid,
Whitespace => match c {
b'}' => Done,
b'.' => ClassFirst,
b'#' => IdentifierFirst,
b'%' => CommentFirst,
c if is_name(c) => Key,
c if c.is_ascii_whitespace() => Whitespace,
_ => Invalid,
},
CommentFirst | Comment | CommentNewline if c == b'%' => Whitespace,
CommentFirst | Comment | CommentNewline if c == b'}' => Done,
CommentFirst | Comment | CommentNewline if c == b'\n' => CommentNewline,
CommentFirst | Comment | CommentNewline => Comment,
ClassFirst if is_name(c) => Class,
ClassFirst => Invalid,
IdentifierFirst if is_name(c) => Identifier,
IdentifierFirst => Invalid,
s @ (Class | Identifier | Value) if is_name(c) => s,
Class | Identifier | Value if c.is_ascii_whitespace() => Whitespace,
Class | Identifier | Value if c == b'}' => Done,
Class | Identifier | Value => Invalid,
Key if is_name(c) => Key,
Key if c == b'=' => ValueFirst,
Key => Invalid,
ValueFirst if is_name(c) => Value,
ValueFirst if c == b'"' => ValueQuoted,
ValueFirst => Invalid,
ValueQuoted | ValueNewline | ValueContinued if c == b'"' => Whitespace,
ValueQuoted | ValueNewline | ValueContinued | ValueEscape if c == b'\n' => ValueNewline,
ValueQuoted if c == b'\\' => ValueEscape,
ValueQuoted | ValueEscape => ValueQuoted,
ValueNewline | ValueContinued => ValueContinued,
Done | Invalid => state,
}
}
let mut state = State::Start;
for (at, &byte) in line.iter().enumerate() {
state = step(state, byte);
match state {
State::Done => return at + 1,
State::Invalid => return 0,
_ => {}
}
}
0
}
fn definition(line: &[u8]) -> Option<(usize, bool)> {
let rest = line.get(1..)?;
let label = rest.iter().position(|&byte| byte == b']')?;
(rest.get(label + 1) == Some(&b':')).then_some((label, rest.first() == Some(&b'^')))
}
fn is_thematic_break(after: &[u8]) -> bool {
let mut marks = 1usize;
for &byte in after {
if matches!(byte, b'-' | b'*') {
marks += 1;
} else if !is_space(byte) {
return false;
}
}
marks >= 3
}
fn fence(line: &[u8], mark: u8) -> Option<(usize, bool)> {
let len = line.iter().take_while(|&&byte| byte == mark).count();
let spec = &line[len..];
let spec = &spec[spec.iter().take_while(|&&byte| is_space(byte)).count()..];
let valid = if mark == b':' {
spec.iter()
.all(|&byte| byte.is_ascii_alphanumeric() || matches!(byte, b':' | b'_' | b'-'))
} else {
!spec.iter().any(|&byte| is_space(byte) || byte == b'`')
};
(valid && len >= 3).then_some((len, spec.is_empty()))
}
fn ordered_marker(line: &[u8]) -> Option<usize> {
fn roman_lower(byte: u8) -> bool {
matches!(byte, b'i' | b'v' | b'x' | b'l' | b'c' | b'd' | b'm')
}
fn roman_upper(byte: u8) -> bool {
matches!(byte, b'I' | b'V' | b'X' | b'L' | b'C' | b'D' | b'M')
}
let paren = line.first() == Some(&b'(');
let start = usize::from(paren);
let first = *line.get(start)?;
let (numeral, most): (fn(u8) -> bool, usize) = if first.is_ascii_digit() {
(|byte| byte.is_ascii_digit(), 19)
} else if roman_lower(first) {
(roman_lower, 13)
} else if roman_upper(first) {
(roman_upper, 13)
} else if first.is_ascii_lowercase() {
(|byte| byte.is_ascii_lowercase(), 1)
} else if first.is_ascii_uppercase() {
(|byte| byte.is_ascii_uppercase(), 1)
} else {
return None;
};
let number = 1 + line
.get(start + 1..)
.unwrap_or_default()
.iter()
.take(most - 1)
.take_while(|&&byte| numeral(byte))
.count();
let closes = match line.get(start + number) {
Some(b')') => true,
Some(b'.') => !paren,
_ => false,
};
let len = start + number + 1;
(closes && line.get(len).is_none_or(|&byte| is_space(byte))).then_some(len)
}
#[derive(Debug)]
enum Frame {
Quote,
Item {
indent: usize,
marker_end: usize,
last_blank: bool,
},
Div {
indent: usize,
len: usize,
raw: Option<(u8, usize)>,
closed: bool,
first: bool,
},
}
impl Frame {
fn continues(&mut self, view: &[u8]) -> bool {
match self {
Frame::Quote => matches!(identify(view).0, Block::Blockquote | Block::Paragraph),
Frame::Item {
indent, last_blank, ..
} => {
let whitespace = view.iter().take_while(|&&byte| is_space(byte)).count();
let next = identify(view).0;
let lazy = !*last_blank && next == Block::Paragraph;
*last_blank = next == Block::Blank;
*last_blank || whitespace > *indent || lazy
}
Frame::Div {
len, raw, closed, ..
} => {
if *closed {
return false;
}
if let Block::Fence {
mark,
len: fence_len,
bare,
..
} = identify(view).0
{
match *raw {
Some((open, open_len)) => {
if mark == open && fence_len >= open_len && bare {
*raw = None;
}
}
None if mark == b':' => *closed = fence_len >= *len && bare,
None => *raw = Some((mark, fence_len)),
}
}
true
}
}
}
fn strip<'a>(&mut self, view: &'a [u8]) -> &'a [u8] {
let body = view.iter().take_while(|&&byte| byte != b'\n').count();
let (whitespace, content) = trimmed(view);
let skip = match self {
Frame::Quote => {
if content == b">" {
whitespace + 1
} else if content.first() == Some(&b'>')
&& content.get(1).is_some_and(|&byte| is_space(byte))
{
whitespace + 2
} else {
0
}
}
Frame::Item { marker_end, .. } => whitespace.min(*marker_end),
Frame::Div { indent, first, .. } => {
if std::mem::take(first) {
0
} else {
whitespace.min(*indent)
}
}
};
&view[skip.min(body)..]
}
}
#[derive(Debug, Default)]
enum Leaf {
#[default]
None,
Paragraph,
Heading(usize),
LinkDefinition,
Code {
mark: u8,
len: usize,
closed: bool,
},
Table {
caption: bool,
blank: bool,
},
}
impl Leaf {
fn continues(&mut self, view: &[u8]) -> bool {
match self {
Leaf::None => false,
Leaf::Paragraph | Leaf::Table { caption: true, .. } => !is_blank(view),
Leaf::Heading(level) => match identify(view).0 {
Block::Paragraph => true,
Block::Heading(next) => next == *level,
_ => false,
},
Leaf::LinkDefinition => view.first() == Some(&b' ') && !is_blank(view),
Leaf::Code { mark, len, closed } => {
if *closed {
return false;
}
if let Block::Fence {
mark: fence_mark,
len: fence_len,
bare,
..
} = identify(view).0
&& fence_mark == *mark
{
*closed = fence_len >= *len && bare;
}
true
}
Leaf::Table { caption, blank } => {
let (_, row) = trimmed(view);
if row.is_empty() {
*blank = true;
true
} else if row.starts_with(b"^ ") {
*caption = true;
true
} else {
!*blank
&& row.starts_with(b"|")
&& row.ends_with(b"|")
&& !row.ends_with(b"\\|")
}
}
}
}
}
#[derive(Debug, Default)]
struct Scan {
frames: Vec<Frame>,
leaf: Leaf,
heading: usize,
overlong_headings: Vec<usize>,
line_end: usize,
leaf_lines: usize,
longest_leaf: usize,
block_start: usize,
block_longest: usize,
long_block: usize,
long_blocks: Vec<Range<usize>>,
}
impl Scan {
fn read(&mut self, line: &[u8], limit: usize) -> usize {
let mut view = line;
let mut level = 0;
while let Some(frame) = self.frames.get_mut(level) {
if !frame.continues(view) {
self.frames.truncate(level);
return self.open(view, limit);
}
if matches!(frame, Frame::Div { closed: true, .. }) {
self.frames.truncate(level + 1);
self.leaf = Leaf::None;
self.leaf_lines = 0;
return self.depth();
}
view = frame.strip(view);
level += 1;
}
let in_caption = matches!(self.leaf, Leaf::Table { caption: true, .. });
if self.leaf.continues(view) {
match self.leaf {
Leaf::Paragraph | Leaf::Heading(_) => self.leaf_line(),
Leaf::Table { caption: true, .. } if in_caption => self.leaf_line(),
Leaf::Table { .. } => {
self.leaf_lines = 0;
self.leaf_line();
}
Leaf::None | Leaf::LinkDefinition | Leaf::Code { .. } => {}
}
return self.depth();
}
self.open(view, limit)
}
fn leaf_line(&mut self) {
self.leaf_lines += 1;
self.longest_leaf = self.longest_leaf.max(self.leaf_lines);
self.block_longest = self.block_longest.max(self.leaf_lines);
}
fn begin_block(&mut self, at: usize) {
if self.block_longest > self.long_block {
self.long_blocks.push(self.block_start..at);
}
self.block_start = at;
self.block_longest = 0;
}
fn open(&mut self, mut view: &[u8], limit: usize) -> usize {
if self.frames.is_empty() {
self.begin_block(self.line_end - view.len());
}
self.leaf = Leaf::None;
self.leaf_lines = 0;
while self.frames.len() <= limit {
let (block, marker_end) = identify(view);
match block {
Block::Blank | Block::Atom => break,
Block::Paragraph => {
self.leaf = Leaf::Paragraph;
self.leaf_line();
break;
}
Block::Heading(level) => {
self.heading = self.heading.max(level);
if level > MAX_HEADING_LEVEL {
self.overlong_headings
.push(self.line_end - view.len() + marker_end - level);
}
self.leaf = Leaf::Heading(level);
self.leaf_line();
break;
}
Block::LinkDefinition => {
self.leaf = Leaf::LinkDefinition;
break;
}
Block::TableRow => {
self.leaf = Leaf::Table {
caption: false,
blank: false,
};
self.leaf_line();
break;
}
Block::Fence {
mark: b':',
len,
indent,
..
} => {
self.frames.push(Frame::Div {
indent,
len,
raw: None,
closed: false,
first: true,
});
break;
}
Block::Fence { mark, len, .. } => {
self.leaf = Leaf::Code {
mark,
len,
closed: false,
};
break;
}
Block::Blockquote => {
self.frames.push(Frame::Quote);
view = &view[marker_end..];
if matches!(view.first(), Some(b' ' | b'\t')) {
view = &view[1..];
}
}
Block::Item { indent } => {
self.frames.push(Frame::Item {
indent,
marker_end,
last_blank: false,
});
view = &view[marker_end..];
}
}
}
self.depth()
}
fn depth(&self) -> usize {
self.frames.len() + usize::from(matches!(self.leaf, Leaf::Table { .. }))
}
}
#[cfg(test)]
#[path = "djot_depth_tests.rs"]
mod tests;