Something went wrong. Try again.
Markdown parser fork with extended syntax for personal use.
Something went wrong. Try again.
26 kB · 824 lines
Rust
at main
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825//! A tokenizer glues states from the state machine together.//!//! It facilitates everything needed to turn bytes into events with a state//! machine.//! It also enables the logic needed for parsing markdown, such as an//! [`attempt`][] to try and parse something, which can succeed or, when//! unsuccessful, revert the attempt.//!//! [`attempt`]: Tokenizer::attempt
use crate::event::{Content, Event, Kind, Link, Name, Point, VOID_EVENTS};use crate::message;use crate::parser::ParseState;use crate::resolve::{call as call_resolve, Name as ResolveName};use crate::state::{call, State};use crate::subtokenize::Subresult;
#[cfg(feature = "log")]use crate::util::char::format_byte_opt;
use crate::util::{constant::TAB_SIZE, edit_map::EditMap};use alloc::{boxed::Box, string::String, vec, vec::Vec};
/// Containers.////// Containers are found when tokenizing/// [document content][crate::construct::document]./// They parse a portion at the start of one or more lines./// The rest of those lines is a different content type (specifically, flow),/// which they “contain”.#[derive(Debug, Eq, PartialEq)]pub enum Container { /// [Block quote][crate::construct::block_quote]. BlockQuote, /// [List item][crate::construct::list_item]. ListItem, /// [GFM: Footnote definition][crate::construct::gfm_footnote_definition]. GfmFootnoteDefinition,}
/// Info used to tokenize a container.////// Practically, these fields are only used for list items.#[derive(Debug)]pub struct ContainerState { /// Kind. pub kind: Container, /// Whether the first line was blank. pub blank_initial: bool, /// Size. pub size: usize,}
/// How to handle a byte.#[derive(Debug, PartialEq)]enum ByteAction { /// This is a normal byte. /// /// Includes replaced bytes. Normal(u8), /// This byte must be ignored. Ignore, /// This is a new byte. Insert(u8),}
/// Label start kind.#[derive(Debug, PartialEq, Eq)]pub enum LabelKind { /// Label (image) start. /// /// ```markdown /// > | a ![b] c /// ^^ /// ``` /// /// Construct: [Label start (image)][crate::construct::label_start_image]. Image, /// Label (image) link. /// /// ```markdown /// > | a [b] c /// ^ /// ``` /// /// Construct: [Label start (link)][crate::construct::label_start_link]. Link, /// GFM: Label (footnote) link. /// /// ```markdown /// > | a [^b] c /// ^^ /// ``` /// /// Construct: [GFM: Label start (footnote)][crate::construct::gfm_label_start_footnote]. GfmFootnote, /// GFM: Label (footnote) link, not matching a footnote definition, so /// handled as a label (link) start. /// /// ```markdown /// > | a [^b](c) d /// ^^ /// ``` /// /// Construct: [Label end][crate::construct::label_end]. GfmUndefinedFootnote,}
/// Label start, looking for an end.#[derive(Debug)]pub struct LabelStart { /// Kind of start. pub kind: LabelKind, /// Indices of where the label starts and ends in `events`. pub start: (usize, usize), /// A boolean used internally to figure out if a (link) label start can’t /// be used anymore (because it would contain another link). /// That link start is still looking for a balanced closing bracket though, /// so we can’t remove it just yet. pub inactive: bool,}
/// Valid label.#[derive(Debug)]pub struct Label { pub kind: LabelKind, /// Indices of label start. pub start: (usize, usize), /// Indices of label end. pub end: (usize, usize),}
/// Different kinds of attempts.#[derive(Debug, PartialEq)]enum AttemptKind { /// Discard what was tokenized when unsuccessful. Attempt, /// Discard always. Check,}
/// How to handle [`State::Ok`][] or [`State::Nok`][].#[derive(Debug)]struct Attempt { /// Where to go to when successful. ok: State, /// Where to go to when unsuccessful. nok: State, /// Kind of attempt. kind: AttemptKind, /// If needed, the progress to revert to. /// /// It is not needed to discard an [`AttemptKind::Attempt`] that has a /// `nok` of [`State::Nok`][], because that means it is used in *another* /// attempt, which will receive that `Nok`, and has to handle it. progress: Option<Progress>,}
/// The internal state of a tokenizer.////// Not to be confused with states from the state machine, this instead is all/// the information on where we currently are and what’s going on.#[derive(Clone, Debug)]struct Progress { /// Length of `events`. /// /// It’s not allowed to remove events, so reverting will just pop stuff off. events_len: usize, /// Length of the stack. /// /// It’s not allowed to decrease the stack in an attempt. stack_len: usize, /// Previous code. previous: Option<u8>, /// Current code. current: Option<u8>, /// Current place in the file. point: Point,}
/// A lot of shared fields used to tokenize things.#[allow(clippy::struct_excessive_bools)]#[derive(Debug)]pub struct TokenizeState<'a> { // Couple complex fields used to tokenize the document. /// Tokenizer, used to tokenize flow in document. pub document_child: Option<Box<Tokenizer<'a>>>, /// State, used to tokenize containers. pub document_child_state: Option<State>, /// Stack of currently active containers. pub document_container_stack: Vec<ContainerState>, /// How many active containers continued. pub document_continued: usize, /// Index of last `data`. pub document_data_index: Option<usize>, /// Container exits by line number. pub document_exits: Vec<Option<Vec<Event>>>, /// Whether the previous flow was a paragraph or a definition. pub document_lazy_accepting_before: bool, /// Whether this is the first paragraph (potentially after definitions) in /// a list item. /// Used for GFM task list items. pub document_at_first_paragraph_of_list_item: bool,
// Couple of very frequent settings for parsing whitespace. pub space_or_tab_eol_content: Option<Content>, pub space_or_tab_eol_connect: bool, pub space_or_tab_eol_ok: bool, pub space_or_tab_connect: bool, pub space_or_tab_content: Option<Content>, pub space_or_tab_min: usize, pub space_or_tab_max: usize, pub space_or_tab_size: usize, pub space_or_tab_token: Name,
// Couple of media related fields. /// List of usable label starts. /// /// Used when tokenizing [text content][crate::construct::text]. pub label_starts: Vec<LabelStart>, /// List of unusable label starts. /// /// Used when tokenizing [text content][crate::construct::text]. pub label_starts_loose: Vec<LabelStart>, /// Stack of images and links. /// /// Used when tokenizing [text content][crate::construct::text]. pub labels: Vec<Label>,
/// List of defined definition identifiers. pub definitions: Vec<String>, /// List of defined GFM footnote definition identifiers. pub gfm_footnote_definitions: Vec<String>,
// Last error message provided at an EOF of an expression. pub mdx_last_parse_error: Option<(String, String, String)>,
/// Whether to connect events. pub connect: bool, /// Marker. pub marker: u8, /// Secondary marker. pub marker_b: u8, /// Several markers. pub markers: &'static [u8], /// Whether something was seen. pub seen: bool, /// Size. pub size: usize, /// Secondary size. pub size_b: usize, /// Tertiary size. pub size_c: usize, /// Index. pub start: usize, /// Index. pub end: usize, /// Slot for an event name. pub token_1: Name, /// Slot for an event name. pub token_2: Name, /// Slot for an event name. pub token_3: Name, /// Slot for an event name. pub token_4: Name, /// Slot for an event name. pub token_5: Name, /// Slot for an event name. pub token_6: Name,}
/// A tokenizer itself.#[allow(clippy::struct_excessive_bools)]#[derive(Debug)]pub struct Tokenizer<'a> { /// Jump between line endings. column_start: Vec<(usize, usize)>, // First line where this tokenizer starts. first_line: usize, /// Current point after the last line ending (excluding jump). line_start: Point, /// Track whether the current byte is already consumed (`true`) or expected /// to be consumed (`false`). /// /// Tracked to make sure everything’s valid. consumed: bool, /// Stack of how to handle attempts. attempts: Vec<Attempt>, /// Current byte. pub current: Option<u8>, /// Previous byte. pub previous: Option<u8>, /// Current relative and absolute place in the file. pub point: Point, /// Semantic labels. pub events: Vec<Event>, /// Hierarchy of semantic labels. /// /// Tracked to make sure everything’s valid. pub stack: Vec<Name>, /// Edit map, to batch changes. pub map: EditMap, /// List of resolvers. pub resolvers: Vec<ResolveName>, /// Shared parsing state across tokenizers. pub parse_state: &'a ParseState<'a>, /// A lot of shared fields used to tokenize things. pub tokenize_state: TokenizeState<'a>, /// Whether we would be interrupting something. /// /// Used when tokenizing [flow content][crate::construct::flow]. pub interrupt: bool, /// Whether containers cannot “pierce” into the current construct. /// /// Used when tokenizing [document content][crate::construct::document]. pub concrete: bool, /// Whether this row is piercing into the current construct with more /// containers. /// /// Used when tokenizing [document content][crate::construct::document]. pub pierce: bool, /// Whether this line is lazy: there are less containers than before. pub lazy: bool,}
impl<'a> Tokenizer<'a> { /// Create a new tokenizer. pub fn new(point: Point, parse_state: &'a ParseState) -> Tokenizer<'a> { Tokenizer { previous: None, current: None, // To do: reserve size when feeding? column_start: vec![], first_line: point.line, line_start: point.clone(), consumed: true, attempts: vec![], point, stack: vec![], events: vec![], parse_state, tokenize_state: TokenizeState { connect: false, document_container_stack: vec![], document_exits: vec![], document_continued: 0, document_lazy_accepting_before: false, document_data_index: None, document_child_state: None, document_child: None, document_at_first_paragraph_of_list_item: false, definitions: vec![], gfm_footnote_definitions: vec![], mdx_last_parse_error: None, end: 0, label_starts: vec![], label_starts_loose: vec![], marker: 0, marker_b: 0, markers: &[], labels: vec![], seen: false, size: 0, size_b: 0, size_c: 0, space_or_tab_eol_content: None, space_or_tab_eol_connect: false, space_or_tab_eol_ok: false, space_or_tab_connect: false, space_or_tab_content: None, space_or_tab_min: 0, space_or_tab_max: 0, space_or_tab_size: 0, space_or_tab_token: Name::SpaceOrTab, start: 0, token_1: Name::Data, token_2: Name::Data, token_3: Name::Data, token_4: Name::Data, token_5: Name::Data, token_6: Name::Data, }, map: EditMap::new(), interrupt: false, pierce: false, concrete: false, lazy: false, resolvers: vec![], } }
/// Register a resolver. pub fn register_resolver(&mut self, name: ResolveName) { if !self.resolvers.contains(&name) { self.resolvers.push(name); } }
/// Register a resolver, before others. pub fn register_resolver_before(&mut self, name: ResolveName) { if !self.resolvers.contains(&name) { self.resolvers.insert(0, name); } }
/// Define a jump between two places. /// /// This defines to which future index we move after a line ending. pub fn define_skip(&mut self, mut point: Point) { move_point_back(self, &mut point);
let info = (point.index, point.vs);
#[cfg(feature = "log")] log::trace!("position: define skip: {:?} -> ({:?})", point.line, info);
let at = point.line - self.first_line;
if at >= self.column_start.len() { self.column_start.push(info); } else { self.column_start[at] = info; }
self.account_for_potential_skip(); }
/// Increment the current positional info if we’re right after a line /// ending, which has a skip defined. fn account_for_potential_skip(&mut self) { let at = self.point.line - self.first_line;
if self.point.column == 1 && at != self.column_start.len() { self.move_to(self.column_start[at]); } }
/// Prepare for a next byte to get consumed. fn expect(&mut self, byte: Option<u8>) { debug_assert!(self.consumed, "expected previous byte to be consumed"); self.consumed = false; self.current = byte; }
/// Consume the current byte. /// Each state function is expected to call this to signal that this code is /// used, or call a next function. pub fn consume(&mut self) { debug_assert!(!self.consumed, "expected code to *not* have been consumed: this might be because `State::Retry(x)` instead of `State::Next(x)` was returned"); self.move_one();
self.previous = self.current; // While we’re not at eof, it is at least better to not have the // same current code as `previous` *and* `current`. self.current = None; // Mark as consumed. self.consumed = true; }
/// Move to the next (virtual) byte. fn move_one(&mut self) { match byte_action(self.parse_state.bytes, &self.point) { ByteAction::Ignore => { self.point.index += 1; } ByteAction::Insert(byte) => { self.previous = Some(byte); self.point.column += 1; self.point.vs += 1; } ByteAction::Normal(byte) => { self.previous = Some(byte); self.point.vs = 0; self.point.index += 1;
if byte == b'\n' { self.point.line += 1; self.point.column = 1;
if self.point.line - self.first_line + 1 > self.column_start.len() { self.column_start.push((self.point.index, self.point.vs)); }
self.line_start = self.point.clone();
self.account_for_potential_skip();
#[cfg(feature = "log")] log::trace!("position: after eol: `{:?}`", self.point); } else { self.point.column += 1; } } } }
/// Move (virtual) bytes. fn move_to(&mut self, to: (usize, usize)) { let (to_index, to_vs) = to; while self.point.index < to_index || self.point.index == to_index && self.point.vs < to_vs { self.move_one(); } }
/// Mark the start of a semantic label. pub fn enter(&mut self, name: Name) { enter_impl(self, name, None); }
/// Enter with a link. pub fn enter_link(&mut self, name: Name, link: Link) { enter_impl(self, name, Some(link)); }
/// Mark the end of a semantic label. pub fn exit(&mut self, name: Name) { let current = self.stack.pop().expect("cannot close w/o open tokens");
debug_assert_eq!(current, name, "expected exit event to match current event");
let previous = self.events.last().expect("cannot close w/o open event"); let mut point = self.point.clone();
debug_assert!( current != previous.name || previous.point.index != point.index || previous.point.vs != point.vs, "expected non-empty event" );
if VOID_EVENTS.iter().any(|d| d == &name) { debug_assert!( current == previous.name, "expected event to be void, instead of including something" ); }
// A bit weird, but if we exit right after a line ending, we *don’t* want to consider // potential skips. if matches!(self.previous, Some(b'\n')) { point = self.line_start.clone(); } else { move_point_back(self, &mut point); }
#[cfg(feature = "log")] log::debug!("exit: `{:?}`", name);
let event = Event { kind: Kind::Exit, name, point, link: None, }; self.events.push(event); }
/// Capture the tokenizer progress. fn capture(&mut self) -> Progress { Progress { previous: self.previous, current: self.current, point: self.point.clone(), events_len: self.events.len(), stack_len: self.stack.len(), } }
/// Apply tokenizer progress. fn free(&mut self, previous: Progress) { self.previous = previous.previous; self.current = previous.current; self.point = previous.point; debug_assert!( self.events.len() >= previous.events_len, "expected to restore less events than before" ); self.events.truncate(previous.events_len); debug_assert!( self.stack.len() >= previous.stack_len, "expected to restore less stack items than before" ); self.stack.truncate(previous.stack_len); }
/// Stack an attempt, moving to `ok` on [`State::Ok`][] and `nok` on /// [`State::Nok`][], reverting in both cases. pub fn check(&mut self, ok: State, nok: State) { // Always capture (and restore) when checking. // No need to capture (and restore) when `nok` is `State::Nok`, because the // parent attempt will do it. let progress = Some(self.capture()); let attempt = Attempt { kind: AttemptKind::Check, progress, ok, nok, }; self.attempts.push(attempt); }
/// Stack an attempt, moving to `ok` on [`State::Ok`][] and `nok` on /// [`State::Nok`][], reverting in the latter case. pub fn attempt(&mut self, ok: State, nok: State) { // Always capture (and restore) when checking. // No need to capture (and restore) when `nok` is `State::Nok`, because the // parent attempt will do it. let progress = if nok == State::Nok { None } else { Some(self.capture()) };
let attempt = Attempt { kind: AttemptKind::Attempt, progress, ok, nok, }; self.attempts.push(attempt); }
/// Tokenize. pub fn push(&mut self, from: (usize, usize), to: (usize, usize), state: State) -> State { push_impl(self, from, to, state, false) }
/// Flush. pub fn flush(&mut self, state: State, resolve: bool) -> Result<Subresult, message::Message> { let to = (self.point.index, self.point.vs); let state = push_impl(self, to, to, state, true);
state.to_result()?;
let mut value = Subresult { done: false, gfm_footnote_definitions: self.tokenize_state.gfm_footnote_definitions.split_off(0), definitions: self.tokenize_state.definitions.split_off(0), };
if resolve { let resolvers = self.resolvers.split_off(0); let mut index = 0; let defs = &mut value.definitions; let fn_defs = &mut value.gfm_footnote_definitions; while index < resolvers.len() { if let Some(mut result) = call_resolve(self, resolvers[index])? { fn_defs.append(&mut result.gfm_footnote_definitions); defs.append(&mut result.definitions); } index += 1; }
self.map.consume(&mut self.events); }
Ok(value) }}
/// Move back past ignored bytes.fn move_point_back(tokenizer: &mut Tokenizer, point: &mut Point) { while point.index > 0 { point.index -= 1; let action = byte_action(tokenizer.parse_state.bytes, point); if !matches!(action, ByteAction::Ignore) { point.index += 1; break; } }}
/// Enter.fn enter_impl(tokenizer: &mut Tokenizer, name: Name, link: Option<Link>) { let mut point = tokenizer.point.clone(); move_point_back(tokenizer, &mut point);
#[cfg(feature = "log")] log::debug!("enter: `{:?}`", name);
tokenizer.stack.push(name.clone()); tokenizer.events.push(Event { kind: Kind::Enter, name, point, link, });}
/// Run the tokenizer.fn push_impl( tokenizer: &mut Tokenizer, from: (usize, usize), to: (usize, usize), mut state: State, flush: bool,) -> State { debug_assert!( from.0 > tokenizer.point.index || (from.0 == tokenizer.point.index && from.1 >= tokenizer.point.vs), "cannot move backwards" );
tokenizer.move_to(from);
loop { match state { State::Error(_) => break, State::Ok | State::Nok => { if let Some(attempt) = tokenizer.attempts.pop() { if attempt.kind == AttemptKind::Check || state == State::Nok { if let Some(progress) = attempt.progress { tokenizer.free(progress); } }
tokenizer.consumed = true;
let next = if state == State::Ok { attempt.ok } else { attempt.nok };
#[cfg(feature = "log")] log::trace!("attempt: `{:?}` -> `{:?}`", state, next);
state = next; } else { break; } } State::Next(name) => { let action = if tokenizer.point.index < to.0 || (tokenizer.point.index == to.0 && tokenizer.point.vs < to.1) { Some(byte_action(tokenizer.parse_state.bytes, &tokenizer.point)) } else if flush { None } else { break; };
if let Some(ByteAction::Ignore) = action { tokenizer.move_one(); } else { let byte = if let Some(ByteAction::Insert(byte) | ByteAction::Normal(byte)) = action { Some(byte) } else { None };
#[cfg(feature = "log")] log::trace!("feed: {} to {:?}", format_byte_opt(byte), name);
tokenizer.expect(byte); state = call(tokenizer, name); } } State::Retry(name) => { #[cfg(feature = "log")] log::trace!("retry: `{:?}`", name);
state = call(tokenizer, name); } } }
tokenizer.consumed = true;
if flush { debug_assert!(matches!(state, State::Ok | State::Error(_)), "must be ok"); } else { debug_assert!( matches!(state, State::Next(_) | State::Error(_)), "must have a next state" ); }
state}
/// Figure out how to handle a byte.fn byte_action(bytes: &[u8], point: &Point) -> ByteAction { if point.index < bytes.len() { let byte = bytes[point.index];
if byte == b'\r' { // CRLF. if point.index < bytes.len() - 1 && bytes[point.index + 1] == b'\n' { ByteAction::Ignore } // CR. else { ByteAction::Normal(b'\n') } } else if byte == b'\t' { let remainder = point.column % TAB_SIZE; let vs = if remainder == 0 { 0 } else { TAB_SIZE - remainder };
// On the tab itself, first send it. if point.vs == 0 { if vs == 0 { ByteAction::Normal(byte) } else { ByteAction::Insert(byte) } } else if vs == 0 { ByteAction::Normal(b' ') } else { ByteAction::Insert(b' ') } } else { ByteAction::Normal(byte) } } else { unreachable!("out of bounds") }}