サンプルコードで身につける: 挿入モードと開いている要素のスタック — トークンを木に置く場所の決め方

// 挿入モード(insertion mode)= 構文解析の主要な動作を決める状態変数(HTML Standard 13.2.6)。
// モードごとに「このトークンが来たらどうするか」が決まり、合わないトークンが来たら
// モードを切り替えて同じトークンをもう一度処理する(仕様の "reprocess the token")。
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum InsertionMode {
    Initial,
    BeforeHtml,
    BeforeHead,
    InHead,
    AfterHead,
    InBody,
    AfterBody,
}

#[derive(Debug)]
pub enum Token<'a> {
    Start(&'a str),
    End(&'a str),
    Eof,
}

/// 1 トークンを今のモードで処理し、(次のモード, もう一度処理するか) を返す
fn step(mode: InsertionMode, token: &Token) -> (InsertionMode, bool) {
    use self::InsertionMode::*;
    use self::Token::*;
    match (mode, token) {
        (Initial, _) => (BeforeHtml, true),
        (BeforeHtml, Start("html")) => (BeforeHead, false),
        (BeforeHtml, _) => (BeforeHead, true), // 暗黙の <html> を作って、同じトークンを再処理
        (BeforeHead, Start("head")) => (InHead, false),
        (BeforeHead, _) => (AfterHead, true), // 暗黙の <head></head>
        (InHead, End("head")) => (AfterHead, false),
        (InHead, Start("title")) | (InHead, End("title")) | (InHead, Start("meta")) => (InHead, false),
        (InHead, _) => (AfterHead, true), // head に置けないものが来た = head の終わり
        (AfterHead, Start("body")) => (InBody, false),
        (AfterHead, _) => (InBody, true), // 暗黙の <body>
        (InBody, End("body")) => (AfterBody, false),
        (InBody, _) => (InBody, false),
        (AfterBody, End("html")) | (AfterBody, Eof) => (AfterBody, false),
        (AfterBody, _) => (InBody, true), // </body> の後に中身が来た: body に戻る
    }
}

fn run(tokens: &[Token]) {
    let mut mode = InsertionMode::Initial;
    for t in tokens {
        loop {
            let (next, reprocess) = step(mode, t);
            if next != mode {
                println!("{:<10} → {:<10} ({:?}{})", format!("{:?}", mode), format!("{:?}", next), t,
                    if reprocess { " を再処理" } else { "" });
            }
            mode = next;
            if !reprocess {
                break;
            }
        }
    }
    println!("最終モード: {:?}\n", mode);
}

fn main() {
    use self::Token::*;
    println!("--- 全部書いた HTML ---");
    run(&[Start("html"), Start("head"), Start("title"), End("title"), End("head"), Start("body"), Start("p"), End("p"), End("body"), End("html"), Eof]);
    println!("--- <p> だけの HTML(html/head/body は暗黙) ---");
    run(&[Start("p"), End("p"), Eof]);
}

// 挿入モードと「開いている要素のスタック」(stack of open elements)を一緒に動かす。開始タグが来たら
// 要素をスタックに積み、終了タグが来たらその要素まで下ろす。一番上(= 今の要素)が次の要素の親になる。
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum InsertionMode {
    Initial,
    BeforeHtml,
    BeforeHead,
    InHead,
    AfterHead,
    InBody,
    AfterBody,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum HtmlToken {
    StartTag { tag: String },
    EndTag { tag: String },
    Eof,
}

pub struct HtmlParser {
    mode: InsertionMode,
    open_elements: Vec<String>,
    pub trace: Vec<String>,
}

impl HtmlParser {
    pub fn new() -> Self {
        HtmlParser { mode: InsertionMode::Initial, open_elements: Vec::new(), trace: Vec::new() }
    }
    fn insert_element(&mut self, tag: &str) {
        let parent = self.open_elements.last().cloned().unwrap_or_else(|| "#document".to_string());
        self.open_elements.push(tag.to_string());
        self.trace.push(format!("{:<11} <{}> を <{}> の子にして積む  stack={:?}", format!("{:?}", self.mode), tag, parent, self.open_elements));
    }
    fn pop_until(&mut self, tag: &str) {
        while let Some(top) = self.open_elements.pop() {
            if top == tag {
                break;
            }
        }
        self.trace.push(format!("{:<11} </{}> で下ろす  stack={:?}", format!("{:?}", self.mode), tag, self.open_elements));
    }
    /// 1 トークンを処理する。true なら同じトークンを新しいモードでもう一度処理する(reprocess)
    fn step(&mut self, token: &HtmlToken) -> bool {
        use self::HtmlToken::*;
        use self::InsertionMode::*;
        let tag = match token {
            StartTag { tag } | EndTag { tag } => tag.as_str(),
            Eof => "",
        };
        match (self.mode, token) {
            (Initial, _) => { self.mode = BeforeHtml; true }
            (BeforeHtml, StartTag { .. }) if tag == "html" => { self.insert_element("html"); self.mode = BeforeHead; false }
            (BeforeHtml, _) => { self.insert_element("html"); self.mode = BeforeHead; true }
            (BeforeHead, StartTag { .. }) if tag == "head" => { self.insert_element("head"); self.mode = InHead; false }
            (BeforeHead, _) => { self.insert_element("head"); self.mode = InHead; true }
            (InHead, EndTag { .. }) if tag == "head" => { self.pop_until("head"); self.mode = AfterHead; false }
            (InHead, StartTag { .. }) if tag == "title" || tag == "meta" => { self.insert_element(tag); self.open_elements.pop(); false }
            (InHead, _) => { self.pop_until("head"); self.mode = AfterHead; true }
            (AfterHead, StartTag { .. }) if tag == "body" => { self.insert_element("body"); self.mode = InBody; false }
            (AfterHead, _) => { self.insert_element("body"); self.mode = InBody; true }
            (InBody, StartTag { .. }) => { self.insert_element(tag); false }
            (InBody, EndTag { .. }) if tag == "body" => { self.mode = AfterBody; false }
            (InBody, EndTag { .. }) => { if self.open_elements.contains(&tag.to_string()) { self.pop_until(tag); } false }
            (InBody, Eof) => false,
            (AfterBody, EndTag { .. }) if tag == "html" => false,
            (AfterBody, Eof) => false,
            (AfterBody, _) => { self.mode = InBody; true }
        }
    }
    pub fn run(&mut self, tokens: &[HtmlToken]) {
        for t in tokens {
            while self.step(t) {}
        }
    }
}

fn main() {
    let start = |t: &str| HtmlToken::StartTag { tag: t.to_string() };
    let end = |t: &str| HtmlToken::EndTag { tag: t.to_string() };
    // <div><p><b></b></p></div> だけを書いた HTML。html / head / body は暗黙に作られる
    let tokens = vec![start("div"), start("p"), start("b"), end("b"), end("p"), end("div"), HtmlToken::Eof];
    let mut parser = HtmlParser::new();
    parser.run(&tokens);
    for line in &parser.trace {
        println!("{}", line);
    }
    println!("最終モード: {:?}, 残ったスタック: {:?}", parser.mode, parser.open_elements);
}

// 実務に写す: 「ヘッダ行 → 空行 → 本文」の形の文書(HTTP メッセージやメールと同じ形)を
// 挿入モードの考え方で読む。InHeaders で「ヘッダに見えない行」が来たら、ヘッダ部は終わったと
// 判断してモードを InBody に切り替え、その行を本文としてもう一度処理する(reprocess)。
// 空行が抜けていても止まらずに読めるのが、この書き方の利点。
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Mode {
    Start,     // 先頭の空行を読み飛ばす
    InHeaders, // "Name: value" の行
    InBody,    // それ以降は全部本文
}

#[derive(Debug, Default)]
struct Message {
    headers: Vec<(String, String)>,
    body: Vec<String>,
    trace: Vec<String>,
}

/// 1 行を今のモードで処理し、(次のモード, 同じ行をもう一度処理するか) を返す
fn step(mode: Mode, line: &str, msg: &mut Message) -> (Mode, bool) {
    match mode {
        Mode::Start => {
            if line.trim().is_empty() {
                (Mode::Start, false)
            } else {
                (Mode::InHeaders, true)
            }
        }
        Mode::InHeaders => {
            if line.trim().is_empty() {
                return (Mode::InBody, false); // 空行 = ヘッダの終わり(正規の形)
            }
            match line.split_once(':') {
                Some((name, value)) if !name.contains(' ') => {
                    msg.headers.push((name.trim().to_string(), value.trim().to_string()));
                    (Mode::InHeaders, false)
                }
                _ => {
                    // ヘッダに見えない行が来た: 空行が抜けている。本文へ切り替えて再処理
                    msg.trace.push(format!("InHeaders → InBody ({:?} を再処理)", line));
                    (Mode::InBody, true)
                }
            }
        }
        Mode::InBody => {
            msg.body.push(line.to_string());
            (Mode::InBody, false)
        }
    }
}

fn parse(text: &str) -> Message {
    let mut msg = Message::default();
    let mut mode = Mode::Start;
    for line in text.lines() {
        loop {
            let (next, reprocess) = step(mode, line, &mut msg);
            mode = next;
            if !reprocess {
                break;
            }
        }
    }
    msg
}

fn main() {
    let proper = "Subject: 週報\nFrom: kazu\n\n今週は字句解析を書いた。\n来週は DOM。\n";
    let broken = "\nSubject: 週報\nFrom: kazu\n今週は字句解析を書いた。\nTODO: 来週は DOM。\n";
    for (label, text) in [("正規の形", proper), ("空行が抜けた形", broken)] {
        let m = parse(text);
        println!("--- {} ---", label);
        println!("headers = {:?}", m.headers);
        println!("body    = {:?}", m.body);
        for t in &m.trace {
            println!("trace   : {}", t);
        }
    }
}