Initialize Rust project with Markdown AST structure

5 files changed, 482 insertions, 0 deletions

diff --git a/src/ast.rs b/src/ast.rs
new file mode 100644
index 0000000..49cfd6f
--- /dev/null
+++ b/src/ast.rs
@@ -0,0 +1,95 @@
+use std::collections::HashMap;
+
+pub mod parser;
+pub mod renderer;
+
+pub struct MarkdownAST {
+    pub root: Layer,
+}
+
+pub type Level = u8;
+pub type Lang = String;
+pub type Title = String;
+pub type Url = String;
+
+pub struct Layer {
+    pub range_row_begin: u32,
+    pub range_row_end: u32,
+    pub lines: Vec<Line>,
+}
+
+pub struct Line {
+    pub row: u32,
+    pub tokens: Vec<Token>,
+}
+
+pub struct Token {
+    pub begin_row: u32,
+    pub begin_col: u16,
+    pub end_row: u32,
+    pub end_col: u16,
+    pub token: TokenData,
+}
+
+pub enum TokenData {
+    Normal(Fragment),
+    Newline,
+    Newlayer(Layer),
+
+    // Headings
+    Heading(Level, Line, Layer),
+
+    // Emphasis
+    Emphasis(Vec<TokenData>, EmphasisStyle),
+
+    // Lists
+    UnorderedList(Line, UnorderedListPrefix),
+    OrderedList(Line, u32),
+
+    // Links
+    Link(Vec<Fragment>, Url, Option<Title>, LinkType),
+
+    // Code
+    InlineCode(Vec<Fragment>),
+    CodeBlock(Vec<Line>, Option<Lang>),
+
+    // Blockquotes
+    Blockquotes(Layer),
+
+    // HorizontalRule
+    HorizontalRule(HorizontalRuleType),
+
+    // Table
+    Table(Table),
+}
+
+pub struct Fragment {
+    pub str: String,
+}
+
+pub struct EmphasisStyle {
+    pub bold: bool,
+    pub italic: bool,
+    pub strikethrough: bool,
+}
+
+pub enum UnorderedListPrefix {
+    Star,
+    Dash,
+    Plus,
+}
+
+pub enum LinkType {
+    Image,
+    Url,
+}
+
+pub enum HorizontalRuleType {
+    Stars,
+    Dashes,
+    Underscores,
+}
+
+pub struct Table {
+    pub contents: HashMap<(u32, u32), Vec<Fragment>>,
+}
diff --git a/src/ast/parser.rs b/src/ast/parser.rs
new file mode 100644
index 0000000..9add926
--- /dev/null
+++ b/src/ast/parser.rs
@@ -0,0 +1,281 @@
+use std::{any::Any, collections::HashMap, str::Chars};
+
+use crate::ast::{Layer, Line, MarkdownAST, Token};
+
+pub mod headings;
+
+type ProcessFn = fn(&char, &mut ParserInternalStatus) -> ParserMatchResult;
+
+fn match_fn_list() -> Vec<ProcessFn> {
+    // 要求以 预处理、词、行、层、后处理 的顺序编写列表
+    // 因为 词处理器 将会写入 records_tokens 由 行处理器 消费
+    // 接着 行处理器 将会写入 records_lines 由 层处理器 消费
+    // 最后 层处理器 将所有行写入当前层中
+    vec![
+        // 预处理器
+        // ...
+        // 词处理器
+        // ...
+        // 行处理器
+        headings::proc,
+        // 层处理器
+        // ...
+        // 后处理器
+        post,
+    ]
+}
+
+/// 错误类型
+pub enum MarkdownASTParseError {
+    /// 语法错误
+    SyntaxError {
+        msg: String,
+        raw: String,
+        begin_col: u16,
+        begin_row: u32,
+        end_col: u16,
+        end_row: u32,
+    },
+}
+
+/// 转换器规则
+pub struct MarkdownParserConfig {
+    ending_rule: LineEndingRule,
+}
+
+/// 换行规则
+#[derive(Debug, PartialEq, Eq)]
+#[repr(u8)]
+pub enum LineEndingRule {
+    CRLF,
+    LF,
+}
+
+pub(crate) struct ParserInternalStatus<'a> {
+    /// 语法树当前状态
+    ast: MarkdownAST,
+
+    /// 总配置
+    cfg: MarkdownParserConfig,
+
+    /// 当前行的所有已处理字符
+    lookback: String,
+
+    /// 所有字符
+    chars: Chars<'a>,
+
+    /// 当前扫描的行
+    row: u32,
+
+    /// 当前扫描的列
+    col: u16,
+
+    /// 记录的 Line, 用于暂存无归属的 Line
+    records_lines: Vec<Line>,
+
+    /// 记录的 Token，用于暂存无归属的 Token
+    records_tokens: Vec<Token>,
+
+    /// 临时类型表
+    tmp: HashMap<&'a str, Box<dyn Any>>,
+}
+
+impl<'a> ParserInternalStatus<'a> {
+    /// 通过字符键初始化或获取临时值
+    pub(crate) fn get_tmp_or_init<T>(&mut self, key: &'a str) -> &mut T
+    where
+        T: Any + Default,
+    {
+        if !self.tmp.contains_key(key) {
+            let value = Box::new(T::default());
+            self.tmp.insert(key, value);
+        }
+
+        // SAFETY: 前方代码可以保证此处一定能拿到 `tmp` 的可变借用
+        let boxed = unsafe { self.tmp.get_mut(key).unwrap_unchecked() };
+
+        // SAFETY: 此处类型安全由解析器内部实现保证，`ParserInternalStatus` 不会对外部 API 开放
+        unsafe { &mut *(boxed.as_mut() as *mut dyn Any as *mut T) }
+    }
+}
+
+pub(crate) enum ParserMatchResult {
+    /// 标记已完成，该字符无需继续处理
+    Done,
+
+    /// 标记未完成，该字符需要继续处理
+    Sad,
+
+    /// 标记放弃，该处理器本行内不参与计算
+    Abort,
+
+    /// 语法错误，需要立刻崩溃
+    SyntaxError {
+        begin_col: u16,
+        begin_row: u32,
+        end_col: u16,
+        end_row: u32,
+        msg: String,
+    },
+}
+
+pub fn markdown_parser(
+    content: &str,
+    cfg: MarkdownParserConfig,
+) -> Result<MarkdownAST, MarkdownASTParseError> {
+    // 创建空 AST，无任何内容
+    let ast = MarkdownAST {
+        root: Layer {
+            range_row_begin: 0,
+            range_row_end: 0,
+            lines: Vec::new(),
+        },
+    };
+
+    // 初始化内部状态
+    let mut inr = ParserInternalStatus {
+        ast,
+        cfg: cfg,
+        lookback: String::new(),
+        chars: content.chars(),
+        row: 0,
+        col: 0,
+        records_lines: Vec::new(),
+        records_tokens: Vec::new(),
+        tmp: HashMap::new(),
+    };
+
+    // 所有的匹配处理函数
+    let match_vec: Vec<ProcessFn> = match_fn_list();
+
+    // 放弃列表
+    // > 为什么不用 HashSet?
+    // > `aborted` 在整个生命周期内数量最大不超过 100 条
+    // > HashSet 虽然 O(1) 但是缓存不友好，更推荐使用 O(n) 线性扫描的 Vec 来处理
+    let mut aborted: Vec<u8> = Vec::new();
+
+    // 扫描循环
+    while let Some(c) = inr.chars.next() {
+        // 当 Lookback 为空时，说明当前为新行
+        if inr.lookback.is_empty() {
+            // 清空放弃列表
+            aborted.clear();
+        }
+
+        // 当前处理函数的索引值
+        let mut idx: u8 = 0;
+
+        for v in &match_vec {
+            // 当前处理函数在放弃列表中
+            if aborted.contains(&idx) {
+                // 跳过当前函数的处理逻辑
+                idx += 1;
+                continue;
+            }
+
+            match v(&c, &mut inr) {
+                // 本字符处理完成
+                ParserMatchResult::Done => {
+                    // 排除对 `\r` 和 `\n` 的完成处理
+                    //
+                    // 在 `post` 中，必须处理该字符的换行逻辑，否则会产生字符位置指针异常
+                    if !matches!(c, '\r' | '\n') {
+                        // 跳过当前步骤前，提前将列指针右移
+                        inr.col += 1;
+                        break;
+                    }
+                }
+
+                // 放弃整行的处理
+                ParserMatchResult::Abort => {
+                    // 将当前函数处理加入放弃列表
+                    aborted.push(idx);
+                }
+
+                // 本字符未处理完成
+                ParserMatchResult::Sad => {}
+
+                // 发生语法错误
+                ParserMatchResult::SyntaxError {
+                    begin_col,
+                    begin_row,
+                    end_col,
+                    end_row,
+                    msg,
+                } => {
+                    return Err(handle_syntax_error(
+                        content.to_string(),
+                        begin_col,
+                        begin_row,
+                        end_col,
+                        end_row,
+                        msg,
+                    ));
+                }
+            }
+            idx += 1;
+        }
+
+        // 将列指针右移
+        inr.col += 1;
+    }
+
+    // 当所有字符处理完成后，AST 应当已经构成，直接返回
+    Ok(inr.ast)
+}
+
+fn post(c: &char, inr: &mut ParserInternalStatus) -> ParserMatchResult {
+    // 将该字符加入 Lookback
+    inr.lookback.push(*c);
+
+    // 获得基础循环的结果
+    match c {
+        // 当 CRLF 模式：`\r` 处理为下移一行
+        // 当 LF 模式：`\r` 不处理
+        '\r' => {
+            if inr.cfg.ending_rule == LineEndingRule::CRLF {
+                inr.row += 1;
+            }
+
+            // 因为行指针被移动，所以清理 Lookback
+            inr.lookback.clear();
+
+            ParserMatchResult::Done
+        }
+        // 当 CRLF 模式：`\n` 为移动到行首
+        // 当 LF 模式：`\n` 为移动到下一行、然后移动到行首
+        '\n' => {
+            if inr.cfg.ending_rule != LineEndingRule::CRLF {
+                inr.row += 1;
+
+                // 因为行指针被移动，所以清理 Lookback
+                inr.lookback.clear();
+            }
+            inr.col = 0;
+
+            // 必须返回 `Sad`，原因如下：
+            // 1. 若返回 `Done`，会导致 `col` 指针被右移
+            // 2. 因为 `post` 在最后处理，所以 `Done` 的字符跳过是无用的
+            ParserMatchResult::Sad
+        }
+        _ => ParserMatchResult::Sad,
+    }
+}
+
+fn handle_syntax_error(
+    raw: String,
+    begin_col: u16,
+    begin_row: u32,
+    end_col: u16,
+    end_row: u32,
+    msg: String,
+) -> MarkdownASTParseError {
+    MarkdownASTParseError::SyntaxError {
+        msg,
+        raw,
+        begin_col,
+        begin_row,
+        end_col,
+        end_row,
+    }
+}
diff --git a/src/ast/parser/headings.rs b/src/ast/parser/headings.rs
new file mode 100644
index 0000000..260efa4
--- /dev/null
+++ b/src/ast/parser/headings.rs
@@ -0,0 +1,104 @@
+use std::mem::replace;
+
+use crate::ast::{
+    Line,
+    parser::{ParserInternalStatus, ParserMatchResult},
+};
+
+#[derive(Default)]
+struct HeadingTmp {
+    /// 当前输入的层级
+    lvl: u8,
+
+    /// 是否正在输入标题前缀
+    typing_heading_prefix: bool,
+
+    /// 是否正在输入标题内容
+    typing_heading_content: bool,
+
+    // 第一个 Sharp 符号的位置
+    first_sharp_col: Option<u16>,
+}
+
+pub(crate) fn proc(c: &char, inr: &mut ParserInternalStatus) -> ParserMatchResult {
+    // 如果本行在剔除开头所有字符后仍不为 # 开头，则说明本行无法用于标题解析
+    let lookback = inr.lookback.clone();
+    if !lookback.trim_start().starts_with('#') {
+        // 本行不是标题行，放弃整行的解析
+        return ParserMatchResult::Abort;
+    }
+
+    // 当前行
+    let row = inr.row;
+    let col = inr.col;
+
+    // 获得临时数据
+    let tmp = inr.get_tmp_or_init::<HeadingTmp>("headings_tmp");
+
+    // 如果是行首，则初始化 tmp 数据
+    if col == 0 {
+        tmp.lvl = 0;
+        tmp.typing_heading_prefix = false;
+        tmp.typing_heading_content = false;
+        tmp.first_sharp_col = None;
+    }
+
+    match c {
+        // 键入了 # 符号
+        '#' => {
+            // 如果正在输入标题前缀，则层级增加
+            if tmp.typing_heading_prefix {
+                tmp.lvl += 1;
+
+                // 如果层级大于 6 (6级标题)
+                if tmp.lvl > 6 {
+                    // 语法异常，抛出
+                    return ParserMatchResult::SyntaxError {
+                        begin_col: tmp.first_sharp_col.unwrap_or(col),
+                        begin_row: row,
+                        end_col: col,
+                        end_row: row,
+                        msg: "Heading level cannot exceed 6".to_string(),
+                    };
+                }
+            }
+            // 如果不在输入标题
+            else {
+                // 记录为正在输入前缀
+                tmp.typing_heading_prefix = true;
+
+                // 设置层级为 1
+                tmp.lvl = 1;
+
+                // 标记第一个 # 符号的位置
+                tmp.first_sharp_col = Some(col);
+            }
+        }
+        // 输入了空格
+        ' ' => {
+            // 如果正在输入标题前缀
+            if tmp.typing_heading_prefix {
+                // 标记为没输入前缀，并切换为正在输入内容
+                tmp.typing_heading_prefix = false;
+                tmp.typing_heading_content = true;
+            }
+        }
+        // 输入了换行
+        '\n' => {
+            // 如果正在输入标题内容
+            if tmp.typing_heading_content {
+                // 拿出所有 records_tokens
+                let tokens = replace(&mut inr.records_tokens, Vec::new());
+
+                // 建立标题行
+                let line = Line { row, tokens };
+
+                // 追加行
+                inr.records_lines.push(line);
+            }
+        }
+        _ => return ParserMatchResult::Sad,
+    }
+
+    ParserMatchResult::Done
+}
diff --git a/src/ast/renderer.rs b/src/ast/renderer.rs
new file mode 100644
index 0000000..8b13789
--- /dev/null
+++ b/src/ast/renderer.rs
@@ -0,0 +1 @@
+
diff --git a/src/lib.rs b/src/lib.rs
new file mode 100644
index 0000000..851c0bc
--- /dev/null
+++ b/src/lib.rs
@@ -0,0 +1 @@
+pub mod ast;