retex-engine 1.3.0-alpha.2

//! The input stack and the tokenizer (*TeX: The Program* §300–§365).
//!
//! TeX reads from a stack of input levels. Each level is either a text
//! source read line by line (a file, the terminal, a `\read` stream, a
//! `\scantokens` pseudo-file or lines printed from Lua) or a token list (a
//! macro body, a parameter, backed-up tokens, `\everypar`, …). `get_next`
//! produces the next token from the top level, converting characters into
//! tokens according to their category codes.

use std::rc::Rc;

use crate::Engine;
use crate::cmd::Cmd;
use crate::hash::{CsId, NO_CS, NULL_CS};
use crate::token::{Token, TokenList};
use crate::utf8x;

/// The scanner state of a text level (`state`).
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum LexState {
    /// In the middle of a line.
    MidLine,
    /// Skipping blanks after a control word or space.
    SkipBlanks,
    /// At the beginning of a line.
    NewLine,
}

/// The kind of a token-list input level (`token_type`).
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum TokKind {
    /// A macro parameter.
    Parameter,
    /// The `u` part of an alignment template.
    UTemplate,
    /// The `v` part of an alignment template.
    VTemplate,
    /// Tokens backed up by `back_input`.
    BackedUp,
    /// A backed-up character (LuaTeX distinguishes it in context lines).
    BackedUpChar,
    /// Tokens inserted during error recovery or by TeX itself.
    Inserted,
    /// A macro body.
    Macro,
    /// `\output`.
    OutputText,
    /// `\everypar`.
    EveryParText,
    /// `\everymath`.
    EveryMathText,
    /// `\everydisplay`.
    EveryDisplayText,
    /// `\everyhbox`.
    EveryHboxText,
    /// `\everyvbox`.
    EveryVboxText,
    /// `\everyjob`.
    EveryJobText,
    /// `\everycr`.
    EveryCrText,
    /// A `\mark` text.
    MarkText,
    /// `\everyeof`.
    EveryEofText,
    /// A `\write` text.
    WriteText,
    /// Tokens produced by Lua (`token.put_next`, `tex.runtoks`, …).
    LocalText,
}

/// The category-code regime of a line printed from Lua.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum CatMode {
    /// The current catcode table.
    Current,
    /// A specific `\catcodetable`.
    Table(u32),
    /// `-2`: everything other (12) except space (10), as `\the\toks`.
    String,
    /// All characters get this category (`tex.cprint`, `tex.write` uses
    /// [`CatMode::String`]).
    Single(u8),
}

/// How a line printed from Lua is fed to the scanner.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum LuaLineKind {
    /// `tex.print`: a full line with `\endlinechar`.
    Print,
    /// `tex.sprint`: a partial line, no `\endlinechar`, mid-line state.
    Sprint,
}

/// One item printed from Lua during a `\directlua` call.
#[derive(Clone, Debug)]
pub enum LuaItem {
    /// A line of text.
    Text {
        /// The bytes (UTF-8).
        text: Vec<u8>,
        /// How it is scanned.
        kind: LuaLineKind,
        /// Its catcode regime.
        catmode: CatMode,
    },
    /// Tokens injected directly.
    Tokens(Vec<Token>),
}

/// Where the lines of a text level come from.
#[derive(Clone, Debug)]
pub enum LineSource {
    /// A file held in memory, with the byte offset of the next line.
    File {
        /// The file content.
        data: Rc<[u8]>,
        /// Offset of the next unread line.
        pos: usize,
    },
    /// The terminal (or the command line for the first line).
    Terminal,
    /// A `\read` stream: the level holds one line only.
    Read(u32),
    /// Lines of a `\scantokens` pseudo-file or of Lua `tex.print`.
    Lines {
        /// The remaining lines.
        lines: std::collections::VecDeque<Vec<u8>>,
        /// For Lua lines: the catcode table to use, if any.
        catcodes: Option<u32>,
        /// Whether this is a pseudo-file (`\scantokens`) that counts lines.
        pseudo: bool,
    },
    /// Output of `tex.print` and friends.
    Lua(std::collections::VecDeque<LuaItem>),
}

/// A text input level.
#[derive(Clone, Debug)]
pub struct TextLevel {
    /// The scanner state.
    pub state: LexState,
    /// The characters of the current line, including the end-of-line
    /// character if one was appended.
    pub buf: Vec<u32>,
    /// Index of the next character in `buf`.
    pub loc: usize,
    /// Where further lines come from.
    pub source: LineSource,
    /// The current line number in this source.
    pub line: i32,
    /// The printable name of the file (for context lines and `(` … `)`).
    pub name: Vec<u8>,
    /// Whether this level was opened by `\input` (prints parentheses).
    pub is_input_file: bool,
    /// Whether `\everyeof` has already been inserted for this file.
    pub eof_seen: bool,
    /// The group level when the file was opened (e-TeX `grp_stack`).
    pub grp_boundary: usize,
    /// The conditional depth when the file was opened (e-TeX `if_stack`).
    pub if_depth: usize,
    /// The catcode regime of the current line.
    pub catmode: CatMode,
    /// The SyncTeX tag and line of this level: those of the file, or tag
    /// 0 and the number of lines read for other text (observed).
    pub sync: (u32, i32),
    /// The file's id for the profiler and origins (see
    /// [`crate::profile`]); 0 until given.
    pub profile_file: u32,
}

/// A token-list input level.
#[derive(Clone, Debug)]
pub struct TokLevel {
    /// The tokens.
    pub list: TokenList,
    /// Index of the next token.
    pub loc: usize,
    /// The kind of list.
    pub kind: TokKind,
    /// Start of this macro's parameters in the parameter stack.
    pub param_start: usize,
    /// For macros: the control sequence being expanded.
    pub name: CsId,
}

/// An input level.
#[derive(Clone, Debug)]
pub enum Level {
    /// Reading characters from lines of text.
    Text(Box<TextLevel>),
    /// Reading a token list.
    Tokens(TokLevel),
}

/// What the scanner is doing, for runaway diagnostics (`scanner_status`).
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub enum ScannerStatus {
    /// Nothing special.
    Normal,
    /// Skipping conditional text.
    Skipping,
    /// Scanning a macro definition.
    Defining,
    /// Scanning macro arguments.
    Matching,
    /// Scanning an alignment preamble.
    Aligning,
    /// Scanning a balanced text (`\message`, `\write`, …).
    Absorbing,
}

/// The number of input levels above the terminal's (LuaTeX's
/// `stack_size`, observed).
const INPUT_STACK_SIZE: usize = 10_000;

/// LuaTeX's limit on nested text input levels (`max_in_open`, observed:
/// "text input levels=15").
pub const MAX_IN_OPEN: usize = 15;

/// Whether a text level counts towards [`MAX_IN_OPEN`]: files,
/// `\scantokens` pseudo-files, `\read` streams and the output of Lua
/// code (observed: a `tex.print` with 15 files open overflows), but not
/// the terminal.
fn counts_as_open(source: &LineSource) -> bool {
    match source {
        LineSource::File { .. } | LineSource::Read(_) | LineSource::Lua(_) => true,
        LineSource::Lines { pseudo, .. } => *pseudo,
        _ => false,
    }
}

/// The most one-token lists kept for reuse by `back_input`.
const SPARE_TOKENS: usize = 16;

/// The input stack.
#[derive(Debug)]
pub struct InputState {
    /// All levels; the last one is the current input (`cur_input`).
    pub stack: Vec<Level>,
    /// Arguments of macros being expanded.
    pub param_stack: Vec<TokenList>,
    /// Brace balance for alignments (`align_state`).
    pub align_state: i32,
    /// What the scanner is doing.
    pub scanner_status: ScannerStatus,
    /// The macro or definition being scanned, for diagnostics.
    pub warning_index: CsId,
    /// Number of open parentheses printed for input files.
    pub open_parens: usize,
    /// Whether `\endinput` was seen in the current file.
    pub force_eof: bool,
    /// Line number of the most recent `\read` line, etc.
    pub last_line: i32,
    /// Text levels open on files, `\scantokens` pseudo-files and `\read`
    /// streams (TeX's `in_open`).
    pub in_open: usize,
    /// One-token lists of backed-up levels that ended, for `back_input` to
    /// reuse (it runs very often; this saves an allocation each time).
    pub spare_tokens: Vec<TokenList>,
}

impl Default for InputState {
    fn default() -> Self {
        InputState {
            stack: Vec::new(),
            param_stack: Vec::new(),
            align_state: 1_000_000,
            scanner_status: ScannerStatus::Normal,
            warning_index: NO_CS,
            open_parens: 0,
            force_eof: false,
            last_line: 0,
            in_open: 0,
            spare_tokens: Vec::new(),
        }
    }
}

/// `no_expand_flag`: the modifier of the special `\relax` produced by
/// `\noexpand` (TeX uses 257; LuaTeX uses a value outside the char range).
pub const NO_EXPAND_FLAG: u32 = 0x11_0001;

impl InputState {
    /// Number of text levels that are input files (TeX's `in_open`).
    pub fn in_open(&self) -> usize {
        self.stack
            .iter()
            .filter(|l| matches!(l, Level::Text(t) if t.is_input_file))
            .count()
    }

    /// The innermost text level, if any.
    pub fn cur_text(&self) -> Option<&TextLevel> {
        self.stack.iter().rev().find_map(|l| match l {
            Level::Text(t) => Some(&**t),
            Level::Tokens(_) => None,
        })
    }

    /// The current line number (`line`): the line of the innermost file.
    pub fn line(&self) -> i32 {
        self.stack
            .iter()
            .rev()
            .find_map(|l| match l {
                Level::Text(t) if !matches!(t.source, LineSource::Read(_)) => Some(t.line),
                _ => None,
            })
            .unwrap_or(0)
    }

    /// Whether the current level is a token list.
    pub fn in_token_list(&self) -> bool {
        matches!(self.stack.last(), Some(Level::Tokens(_)))
    }

    /// Whether we are reading from the terminal (`terminal_input`).
    pub fn terminal_input(&self) -> bool {
        matches!(self.stack.last(), Some(Level::Text(t)) if matches!(t.source, LineSource::Terminal))
    }
}

/// Splits the next line off `data[pos..]`. Lines end at LF, CR or CR LF.
/// Returns the line bytes and the new position, or `None` at end of data.
pub fn next_line(data: &[u8], pos: usize) -> Option<(&[u8], usize)> {
    if pos >= data.len() {
        return None;
    }
    let rest = &data[pos..];
    match rest.iter().position(|&b| b == b'\n' || b == b'\r') {
        Some(i) => {
            let mut next = pos + i + 1;
            if rest[i] == b'\r' && rest.get(i + 1) == Some(&b'\n') {
                next += 1;
            }
            Some((&rest[..i], next))
        }
        None => Some((rest, data.len())),
    }
}

/// Decodes a line of input into characters, removing trailing spaces
/// (TeX's `input_ln`; tabs are kept, as in LuaTeX).
pub fn decode_line(bytes: &[u8]) -> Vec<u32> {
    let mut end = bytes.len();
    while end > 0 && bytes[end - 1] == b' ' {
        end -= 1;
    }
    utf8x::chars_marking_invalid(&bytes[..end])
}

fn is_hex(c: u32) -> bool {
    matches!(c, 0x30..=0x39 | 0x61..=0x66)
}

fn hex_val(c: u32) -> u32 {
    if c <= 0x39 { c - 0x30 } else { c - 0x61 + 10 }
}

/// Result of looking for a `^^` sequence at a position.
enum Expanded {
    /// No expanded character here.
    None,
    /// An expanded character of `len` input characters.
    Char { c: u32, len: usize },
    /// A malformed `^^^^`/`^^^^^^` sequence; `short` if the line ends
    /// before the digits could (LuaTeX's "…, end of input").
    Bad { six: bool, short: bool },
}

/// Examines `buf[k..]` for an expanded character introduced by the
/// superscript character `sup` at `buf[k]` (the caller checks its catcode).
fn expanded_at(buf: &[u32], k: usize) -> Expanded {
    let sup = buf[k];
    if buf.get(k + 1) != Some(&sup) {
        return Expanded::None;
    }
    // LuaTeX: ^^^^^^ + six hex digits, or ^^^^ + four hex digits.
    let run = buf[k..].iter().take(6).take_while(|&&c| c == sup).count();
    if run >= 4 {
        let six = run == 6;
        let n = if six { 6 } else { 4 };
        let start = k + run;
        let digits = buf.get(start..start + n);
        return match digits {
            Some(d) if d.iter().all(|&c| is_hex(c)) => {
                let c = d.iter().fold(0u32, |acc, &c| acc * 16 + hex_val(c));
                if c > 0x10_FFFF {
                    Expanded::Bad { six, short: false }
                } else {
                    Expanded::Char { c, len: run + n }
                }
            }
            _ => Expanded::Bad {
                six,
                short: start + n > buf.len(),
            },
        };
    }
    // Classic TeX ^^ notation.
    let Some(&c) = buf.get(k + 2) else {
        return Expanded::None;
    };
    if c >= 0o200 {
        return Expanded::None;
    }
    if is_hex(c)
        && let Some(&cc) = buf.get(k + 3)
        && is_hex(cc)
    {
        return Expanded::Char {
            c: hex_val(c) * 16 + hex_val(cc),
            len: 4,
        };
    }
    Expanded::Char {
        c: if c < 0o100 { c + 0o100 } else { c - 0o100 },
        len: 3,
    }
}

impl Engine {
    // ----- input levels ---------------------------------------------------

    /// Pushes a token list onto the input stack (`begin_token_list`).
    pub fn begin_token_list(&mut self, list: TokenList, kind: TokKind) {
        // tex.web §323: with \tracingmacros>1, token lists that TeX
        // inserts itself are shown (`\everypar->...`).
        let name = match kind {
            TokKind::OutputText => Some("output"),
            TokKind::EveryParText => Some("everypar"),
            TokKind::EveryMathText => Some("everymath"),
            TokKind::EveryDisplayText => Some("everydisplay"),
            TokKind::EveryHboxText => Some("everyhbox"),
            TokKind::EveryVboxText => Some("everyvbox"),
            TokKind::EveryJobText => Some("everyjob"),
            TokKind::EveryCrText => Some("everycr"),
            TokKind::EveryEofText => Some("everyeof"),
            TokKind::MarkText => Some("mark"),
            TokKind::WriteText => Some("write"),
            _ => None,
        };
        if let Some(name) = name
            && self
                .eqtb
                .int(crate::primitives_gen::assign_int::TRACINGMACROS)
                > 1
        {
            self.begin_diagnostic();
            self.printer.print_nl("");
            self.print_esc_str(name);
            self.printer.print_str("->");
            self.token_show_list(&list, 0, list.len(), 10_000_000);
            self.end_diagnostic(false);
        }
        self.push_input(Level::Tokens(TokLevel {
            list,
            loc: 0,
            kind,
            param_start: self.input.param_stack.len(),
            name: NO_CS,
        }));
    }

    /// Pushes an input level (`push_input`), within LuaTeX's input stack
    /// size.
    fn push_input(&mut self, level: Level) {
        if self.input.stack.len() > INPUT_STACK_SIZE {
            self.overflow("input stack size", INPUT_STACK_SIZE as i64);
        }
        self.input.stack.push(level);
    }

    /// Pushes a macro body with its parameters (already on the parameter
    /// stack starting at `param_start`).
    pub fn begin_macro(&mut self, list: TokenList, start: usize, name: CsId, param_start: usize) {
        self.push_input(Level::Tokens(TokLevel {
            list,
            loc: start,
            kind: TokKind::Macro,
            param_start,
            name,
        }));
    }

    /// Inserts a token list for immediate reading (`ins_list`).
    pub fn ins_list(&mut self, list: TokenList) {
        self.begin_token_list(list, TokKind::Inserted);
    }

    /// Pops the current token-list level (`end_token_list`).
    pub fn end_token_list(&mut self) {
        if let Some(Level::Tokens(t)) = self.input.stack.pop() {
            if matches!(t.kind, TokKind::BackedUp | TokKind::Inserted)
                && t.list.len() == 1
                && Rc::strong_count(&t.list) == 1
                && self.input.spare_tokens.len() < SPARE_TOKENS
            {
                self.input.spare_tokens.push(t.list);
                self.check_interrupt();
                return;
            }
            match t.kind {
                TokKind::Macro => {
                    self.input.param_stack.truncate(t.param_start);
                }
                TokKind::UTemplate => {
                    if self.input.align_state > 500_000 {
                        self.input.align_state = 0;
                    } else {
                        self.fatal_error("(interwoven alignment preambles are not allowed)");
                    }
                }
                _ => {}
            }
        } else {
            debug_assert!(false, "end_token_list on a text level");
        }
        self.check_interrupt();
    }

    /// Puts the current token back into the input (`back_input`).
    pub fn back_input(&mut self) {
        // Pop exhausted token lists first (but not v templates).
        while let Some(Level::Tokens(t)) = self.input.stack.last() {
            if t.loc < t.list.len() || t.kind == TokKind::VTemplate {
                break;
            }
            self.end_token_list();
        }
        let tok = self.cur_tok;
        if tok.0 < crate::token::CS_TOKEN_FLAG {
            let cmd = tok.cmd_code();
            if cmd == Cmd::RightBrace as u32 {
                self.input.align_state += 1;
            } else if cmd == Cmd::LeftBrace as u32 {
                self.input.align_state -= 1;
            }
        }
        let list = match self.input.spare_tokens.pop() {
            Some(mut list) => {
                // Only this level held it.
                if let Some(slot) = Rc::get_mut(&mut list) {
                    slot[0] = tok;
                    list
                } else {
                    Rc::from([tok])
                }
            }
            None => Rc::from([tok]),
        };
        self.push_input(Level::Tokens(TokLevel {
            list,
            loc: 0,
            kind: TokKind::BackedUp,
            param_start: self.input.param_stack.len(),
            name: NO_CS,
        }));
    }

    /// Backs up the current token and marks it as inserted
    /// (`back_error` uses this through `ins_error`).
    pub fn back_input_inserted(&mut self) {
        self.back_input();
        if let Some(Level::Tokens(t)) = self.input.stack.last_mut() {
            t.kind = TokKind::Inserted;
        }
    }

    /// Pushes a text level reading `source`. Files, pseudo-files and
    /// `\read` streams nest at most [`MAX_IN_OPEN`] deep, as in LuaTeX.
    pub fn begin_file_reading(&mut self, source: LineSource, name: Vec<u8>, is_input_file: bool) {
        if counts_as_open(&source) {
            self.check_in_open();
            self.input.in_open += 1;
        }
        self.push_input(Level::Text(Box::new(TextLevel {
            state: LexState::NewLine,
            buf: Vec::new(),
            loc: 0,
            source,
            line: 0,
            name,
            is_input_file,
            eof_seen: false,
            grp_boundary: self.save.cur_boundary,
            if_depth: self.cond.stack.len(),
            catmode: CatMode::Current,
            sync: (0, 0),
            profile_file: 0,
        })));
        self.sync_input_changed();
    }

    /// Stops if no further file can be opened (`begin_file_reading`
    /// checks this before `\input` shows the file name).
    pub(crate) fn check_in_open(&mut self) {
        if self.input.in_open >= MAX_IN_OPEN {
            self.overflow("text input levels", MAX_IN_OPEN as i64);
        }
    }

    /// Pops the current text level (`end_file_reading`).
    pub fn end_file_reading(&mut self) {
        let lvl = self.input.stack.pop();
        if let Some(Level::Text(t)) = lvl
            && counts_as_open(&t.source)
        {
            self.input.in_open = self.input.in_open.saturating_sub(1);
        }
        self.sync_input_changed();
    }

    /// Reads the next line of the current text level into its buffer,
    /// appending `\endlinechar`. Returns `false` at end of source.
    fn read_next_line(&mut self) -> bool {
        self.check_begun();
        let end_line_char = self
            .eqtb
            .int(crate::primitives_gen::assign_int::ENDLINECHAR);
        let Some(Level::Text(t)) = self.input.stack.last_mut() else {
            return false;
        };
        // \scantextokens text gets no \endlinechar after its last line.
        let mut eol = true;
        let line: Vec<u32> = match &mut t.source {
            LineSource::File { data, pos } => match next_line(data, *pos) {
                Some((bytes, next)) => {
                    let l = decode_line(bytes);
                    *pos = next;
                    l
                }
                None => return false,
            },
            LineSource::Lines { lines, pseudo, .. } => match lines.pop_front() {
                Some(bytes) => {
                    eol = *pseudo || !lines.is_empty();
                    decode_line(&bytes)
                }
                None => return false,
            },
            LineSource::Lua(items) => {
                let last = items.len() == 1;
                match items.pop_front() {
                    Some(LuaItem::Text {
                        text,
                        kind,
                        catmode,
                    }) => {
                        t.catmode = catmode;
                        t.loc = 0;
                        t.sync.1 += 1;
                        // Observed: each printed line, `tex.sprint` string
                        // or token item is a line of the Lua level for
                        // `\inputlineno`, counted from 1.
                        t.line += 1;
                        if kind == LuaLineKind::Sprint {
                            t.buf = utf8x::chars(&text);
                            t.state = LexState::MidLine;
                            self.sync_input_changed();
                            return true;
                        }
                        t.buf = decode_line(&text);
                        t.state = LexState::NewLine;
                        if !last && (0..=0x10_FFFF).contains(&end_line_char) {
                            t.buf.push(end_line_char as u32);
                        }
                        self.sync_input_changed();
                        return true;
                    }
                    Some(LuaItem::Tokens(toks)) => {
                        t.buf.clear();
                        t.loc = 0;
                        t.line += 1;
                        self.pending_lua_tokens = Some(toks);
                        return true;
                    }
                    None => return false,
                }
            }
            LineSource::Terminal | LineSource::Read(_) => return false,
        };
        t.buf = line;
        if eol && (0..=0x10_FFFF).contains(&end_line_char) {
            t.buf.push(end_line_char as u32);
        }
        t.loc = 0;
        t.line += 1;
        t.sync.1 = t.line;
        self.sync_input_changed();
        true
    }

    // ----- the tokenizer ---------------------------------------------------

    /// Sets `cur_cmd`, `cur_chr` and `cur_cs` to the next token
    /// (`get_next`).
    #[inline]
    pub fn get_next(&mut self) {
        // Fast path: the next token of a token list, when it needs none of
        // the special handling below (parameters, the end of the list,
        // outer macros, \noexpand markers, alignment entries).
        if let Some(Level::Tokens(t)) = self.input.stack.last_mut()
            && let Some(&tok) = t.list.get(t.loc)
        {
            if tok.is_cs() {
                let cs = tok.cs_id();
                let m = self.eqtb.meaning(cs);
                if m.cmd < Cmd::TabMark || (m.cmd > Cmd::CarRet && !m.cmd.is_outer_or_special()) {
                    t.loc += 1;
                    self.cur_cs = cs;
                    self.cur_cmd = m.cmd;
                    self.cur_chr = m.chr;
                    return;
                }
            } else {
                let cmd = tok.cmd();
                if cmd > Cmd::CarRet || cmd < Cmd::MathShift {
                    t.loc += 1;
                    match cmd {
                        Cmd::LeftBrace => self.input.align_state += 1,
                        Cmd::RightBrace => self.input.align_state -= 1,
                        _ => {}
                    }
                    self.cur_cs = NO_CS;
                    self.cur_cmd = cmd;
                    self.cur_chr = tok.chr();
                    return;
                }
            }
        }
        self.get_next_slow();
    }

    /// [`get_next`](Self::get_next) for everything but the fast path.
    #[inline(never)]
    fn get_next_slow(&mut self) {
        'restart: loop {
            self.cur_cs = NO_CS;
            let Some(top) = self.input.stack.last_mut() else {
                // Nothing left to read: behave like the end of the terminal.
                self.cur_cmd = Cmd::Relax;
                self.cur_chr = 0;
                self.fatal_error("*** (job aborted, no legal \\end found)");
            };
            match top {
                Level::Tokens(t) => {
                    if t.loc < t.list.len() {
                        let tok = t.list[t.loc];
                        t.loc += 1;
                        if tok.is_cs() {
                            let cs = tok.cs_id();
                            self.cur_cs = cs;
                            let m = self.eqtb.meaning(cs);
                            self.cur_cmd = m.cmd;
                            self.cur_chr = m.chr;
                            if self.cur_cmd.is_outer_or_special() {
                                if self.cur_cmd == Cmd::DontExpand {
                                    // The next token is a cs whose expansion
                                    // is suppressed.
                                    let next = t.list[t.loc];
                                    t.loc = t.list.len();
                                    let cs = next.cs_id();
                                    self.cur_cs = cs;
                                    let m = self.eqtb.meaning(cs);
                                    self.cur_cmd = m.cmd;
                                    self.cur_chr = m.chr;
                                    if self.cur_cmd > Cmd::MAX_COMMAND {
                                        self.cur_cmd = Cmd::Relax;
                                        self.cur_chr = NO_EXPAND_FLAG;
                                    }
                                } else {
                                    self.check_outer_validity();
                                }
                            }
                        } else {
                            self.cur_cmd = tok.cmd();
                            self.cur_chr = tok.chr();
                            match self.cur_cmd {
                                Cmd::LeftBrace => self.input.align_state += 1,
                                Cmd::RightBrace => self.input.align_state -= 1,
                                Cmd::CarRet => {
                                    // out_param: insert the macro parameter.
                                    // Lua code can make out_param tokens
                                    // outside macros (token.set_macro with
                                    // a character of category 5); they
                                    // stand for no parameter and vanish.
                                    let p = (self.cur_chr as usize)
                                        .checked_sub(1)
                                        .and_then(|i| self.input.param_stack.get(t.param_start + i))
                                        .cloned();
                                    if let Some(p) = p {
                                        self.begin_token_list(p, TokKind::Parameter);
                                    }
                                    continue 'restart;
                                }
                                _ => {}
                            }
                        }
                    } else {
                        self.end_token_list();
                        continue 'restart;
                    }
                }
                Level::Text(_) => {
                    if !self.get_next_from_text() {
                        continue 'restart;
                    }
                }
            }
            // If an alignment entry has just ended, take appropriate action.
            if self.cur_cmd <= Cmd::CarRet
                && self.cur_cmd >= Cmd::TabMark
                && self.input.align_state == 0
            {
                self.insert_v_template();
                continue 'restart;
            }
            return;
        }
    }

    /// Tokenizes from the current text level. Returns `false` if the caller
    /// must restart (a level was popped or an error occurred).
    fn get_next_from_text(&mut self) -> bool {
        loop {
            // `switch`: get the next character, reading a new line if needed.
            let (c, catmode, state) = {
                let Some(Level::Text(t)) = self.input.stack.last_mut() else {
                    return false;
                };
                if t.loc < t.buf.len() {
                    let c = t.buf[t.loc];
                    t.loc += 1;
                    (c, t.catmode, t.state)
                } else {
                    if matches!(t.source, LineSource::Read(_)) {
                        // End of a \read line: TeX's null token
                        // (`cur_cmd = cur_chr = 0`) tells `read_toks`.
                        self.cur_cmd = Cmd::Relax;
                        self.cur_chr = 0;
                        return true;
                    }
                    if !self.next_line_or_pop() {
                        return false;
                    }
                    continue;
                }
            };
            let c = if utf8x::is_raw(c) {
                self.invalid_utf8_sequence()
            } else {
                c
            };
            self.cur_chr = c;
            // `reswitch`
            let mut c = c;
            loop {
                let cat = self.catcode_in_mode(c, catmode);
                self.cur_cmd = Cmd::from_u8(cat);
                match (cat, state) {
                    // Ignored characters, and spaces at the start of lines or
                    // after control words.
                    (9, _) | (10, LexState::SkipBlanks | LexState::NewLine) => break,
                    (0, _) => {
                        self.scan_control_sequence();
                        return true;
                    }
                    (13, _) => {
                        let cs = self.hash.active(c);
                        self.cur_cs = cs;
                        let m = self.eqtb.meaning(cs);
                        self.cur_cmd = m.cmd;
                        self.cur_chr = m.chr;
                        self.set_state(LexState::MidLine);
                        if self.cur_cmd.is_outer_or_special() {
                            self.check_outer_validity();
                        }
                        return true;
                    }
                    (7, _) => {
                        match self.expanded_in_line() {
                            Expanded::Char { c: nc, len } => {
                                if let Some(Level::Text(t)) = self.input.stack.last_mut() {
                                    t.loc += len - 1;
                                }
                                c = nc;
                                self.cur_chr = c;
                                continue; // reswitch
                            }
                            Expanded::Bad { six, short } => {
                                self.print_err(match (six, short) {
                                    (true, false) => "^^^^^^ needs six hex digits",
                                    (true, true) => "^^^^^^ needs six hex digits, end of input",
                                    (false, false) => "^^^^ needs four hex digits",
                                    (false, true) => "^^^^ needs four hex digits, end of input",
                                });
                                self.help(&[]);
                                self.error();
                                // Observed: LuaTeX then reads the first three
                                // superscript characters the classic way
                                // (`^^^` is U+001E).
                                if let Some(Level::Text(t)) = self.input.stack.last_mut() {
                                    t.loc += 2;
                                }
                                c = if c < 0o100 { c + 0o100 } else { c - 0o100 };
                                self.cur_chr = c;
                                continue; // reswitch
                            }
                            Expanded::None => {
                                self.set_state(LexState::MidLine);
                                return true;
                            }
                        }
                    }
                    (15, _) => {
                        self.print_err("Text line contains an invalid character");
                        self.help(&[
                            "A funny symbol that I can't read has just been input.",
                            "Continue, and I'll forget that it ever happened.",
                        ]);
                        self.err.deletions_allowed = false;
                        self.error();
                        self.err.deletions_allowed = true;
                        return false;
                    }
                    (10, LexState::MidLine) => {
                        self.set_state(LexState::SkipBlanks);
                        self.cur_chr = ' ' as u32;
                        return true;
                    }
                    (5, LexState::MidLine) => {
                        self.finish_line();
                        self.cur_cmd = Cmd::Spacer;
                        self.cur_chr = ' ' as u32;
                        return true;
                    }
                    (5, LexState::SkipBlanks) | (14, _) => {
                        self.finish_line();
                        break;
                    }
                    (5, LexState::NewLine) => {
                        self.finish_line();
                        let par = self.cs.par;
                        self.cur_cs = par;
                        let m = self.eqtb.meaning(par);
                        self.cur_cmd = m.cmd;
                        self.cur_chr = m.chr;
                        if self.cur_cmd.is_outer_or_special() {
                            self.check_outer_validity();
                        }
                        return true;
                    }
                    (1, s) => {
                        if s != LexState::MidLine {
                            self.set_state(LexState::MidLine);
                        }
                        self.input.align_state += 1;
                        return true;
                    }
                    (2, s) => {
                        if s != LexState::MidLine {
                            self.set_state(LexState::MidLine);
                        }
                        self.input.align_state -= 1;
                        return true;
                    }
                    (_, s) => {
                        if s != LexState::MidLine {
                            self.set_state(LexState::MidLine);
                        }
                        return true;
                    }
                }
            }
        }
    }

    /// Reports the invalid byte just read from the current line and
    /// skips it with the bytes that follow it, three in all (observed:
    /// LuaTeX replaces that many bytes, up to the end of the line, by
    /// U+FFFD, which is returned).
    #[cold]
    fn invalid_utf8_sequence(&mut self) -> u32 {
        // The context shows the line up to the invalid byte.
        if let Some(Level::Text(t)) = self.input.stack.last_mut() {
            t.loc -= 1;
        }
        self.print_err("String contains an invalid utf-8 sequence");
        self.help(&[
            "A funny symbol that I can't read has just been (re)read.",
            "Just continue, I'll change it to 0xFFFD.",
        ]);
        self.error();
        if let Some(Level::Text(t)) = self.input.stack.last_mut() {
            let mut bytes = 0;
            while bytes < 3 && t.loc < t.buf.len() {
                let c = t.buf[t.loc];
                bytes += if utf8x::is_raw(c) { 1 } else { utf8x::len(c) };
                t.loc += 1;
            }
        }
        0xFFFD
    }

    /// The category code of `c` under a line's catcode regime.
    #[inline]
    pub fn catcode_in_mode(&self, c: u32, mode: CatMode) -> u8 {
        match mode {
            CatMode::Current => self.eqtb.catcode(c),
            CatMode::Table(t) => self.eqtb.catcode_in(t, c),
            CatMode::String => {
                if c == ' ' as u32 {
                    10
                } else {
                    12
                }
            }
            CatMode::Single(k) => k,
        }
    }

    /// Pushes the output collected from a Lua call as a new input level.
    pub fn push_lua_output(&mut self, items: Vec<LuaItem>) {
        if items.is_empty() {
            return;
        }
        self.begin_file_reading(
            LineSource::Lua(items.into_iter().collect()),
            Vec::new(),
            false,
        );
        if let Some(Level::Text(t)) = self.input.stack.last_mut() {
            t.line = self.input_line_for_lua;
        }
    }

    fn set_state(&mut self, s: LexState) {
        if let Some(Level::Text(t)) = self.input.stack.last_mut() {
            t.state = s;
        }
    }

    fn finish_line(&mut self) {
        if let Some(Level::Text(t)) = self.input.stack.last_mut() {
            t.loc = t.buf.len();
        }
    }

    /// Checks for an expanded character at the character just read.
    fn expanded_in_line(&self) -> Expanded {
        let Some(Level::Text(t)) = self.input.stack.last() else {
            return Expanded::None;
        };
        expanded_at(&t.buf, t.loc - 1)
    }

    /// Moves to the next line of the current text level, or pops the level
    /// at its end (TeX §360–§362). Returns `false` when the caller must
    /// restart from the top of `get_next`.
    fn next_line_or_pop(&mut self) -> bool {
        let (is_terminal, is_read, is_file) = match self.input.stack.last() {
            Some(Level::Text(t)) => (
                matches!(t.source, LineSource::Terminal),
                matches!(t.source, LineSource::Read(_)),
                t.is_input_file,
            ),
            _ => return false,
        };
        if is_read {
            return false;
        }
        if is_terminal {
            // The command line (or terminal input) is exhausted.
            if self.input.stack.len() > 1 {
                // Text inserted during error recovery.
                self.end_file_reading();
                return false;
            }
            self.terminal_exhausted();
            return false;
        }
        let is_lua = matches!(
            self.input.stack.last(),
            Some(Level::Text(t)) if matches!(t.source, LineSource::Lua(_))
        );
        if !self.input.force_eof && self.read_next_line() {
            if let Some(toks) = self.pending_lua_tokens.take() {
                self.begin_token_list(std::rc::Rc::from(toks), TokKind::Inserted);
                return false;
            }
            if !is_lua {
                self.set_state(LexState::NewLine);
            }
            return true;
        }
        // End of file (or \endinput).
        let is_pseudo = matches!(
            self.input.stack.last(),
            Some(Level::Text(t)) if matches!(t.source, LineSource::Lines { pseudo: true, .. })
        );
        if !self.input.force_eof && (is_file || is_pseudo) {
            // e-TeX: insert \everyeof once, for files and \scantokens
            // pseudo-files.
            let every_eof = self
                .eqtb
                .toks_param(crate::primitives_gen::assign_toks::EVERYEOF)
                .clone();
            let seen = match self.input.stack.last_mut() {
                Some(Level::Text(t)) => std::mem::replace(&mut t.eof_seen, true),
                _ => true,
            };
            if !seen && !every_eof.is_empty() {
                if let Some(Level::Text(t)) = self.input.stack.last_mut() {
                    t.buf.clear();
                    t.loc = 0;
                }
                self.begin_token_list(every_eof, TokKind::EveryEofText);
                return false;
            }
        }
        if is_file {
            self.printer.print_char(')' as u32);
            if is_pseudo {
                // Observed: a traced \scantokens pseudo-file closes with
                // two parentheses.
                self.printer.print_char(')' as u32);
            }
            self.input.open_parens -= 1;
            self.printer.update_terminal();
            self.file_closed_checks();
        }
        self.input.force_eof = false;
        // Output printed from Lua and \scantextokens text may end anywhere;
        // only files and \scantokens pseudo-files are checked.
        let check = match self.input.stack.last() {
            Some(Level::Text(t)) => match &t.source {
                LineSource::Lua(_) => false,
                LineSource::Lines { pseudo, .. } => *pseudo,
                _ => true,
            },
            _ => true,
        };
        self.end_file_reading();
        if check {
            self.check_outer_validity();
        }
        false
    }

    /// Scans a control sequence name after an escape character (§354).
    fn scan_control_sequence(&mut self) {
        'start_cs: loop {
            let Some(Level::Text(t)) = self.input.stack.last() else {
                return;
            };
            let len = t.buf.len();
            let loc = t.loc;
            let catmode = t.catmode;
            if loc >= len {
                self.cur_cs = NULL_CS;
                break;
            }
            let mut k = loc;
            let mut ch = t.buf[k];
            let mut cat = self.catcode_in_mode(ch, catmode);
            k += 1;
            let state = if cat == 11 || cat == 10 {
                LexState::SkipBlanks
            } else {
                LexState::MidLine
            };
            if cat == 11 && k < len {
                // Scan ahead until finding a nonletter.
                loop {
                    ch = t.buf[k];
                    cat = self.catcode_in_mode(ch, catmode);
                    k += 1;
                    if cat != 11 || k >= len {
                        break;
                    }
                }
                if self.reduce_expanded(k, ch, cat) {
                    continue 'start_cs;
                }
                if cat != 11 {
                    k -= 1;
                }
                if k > loc + 1 {
                    let mut name = Vec::with_capacity(k - loc);
                    if let Some(Level::Text(t)) = self.input.stack.last() {
                        for &c in &t.buf[loc..k] {
                            utf8x::push(&mut name, c);
                        }
                    }
                    self.cur_cs = self.hash.lookup_or_insert(&name);
                    if let Some(Level::Text(t)) = self.input.stack.last_mut() {
                        t.loc = k;
                        t.state = state;
                    }
                    break;
                }
            } else if self.reduce_expanded(k, ch, cat) {
                continue 'start_cs;
            }
            let c = match self.input.stack.last() {
                Some(Level::Text(t)) => t.buf[loc],
                _ => return,
            };
            self.cur_cs = self.hash.single(c);
            if let Some(Level::Text(t)) = self.input.stack.last_mut() {
                t.loc = loc + 1;
                t.state = state;
            }
            break;
        }
        let m = self.eqtb.meaning(self.cur_cs);
        self.cur_cmd = m.cmd;
        self.cur_chr = m.chr;
        if self.cur_cmd.is_outer_or_special() {
            self.check_outer_validity();
        }
    }

    /// If an expanded code (`^^A`, `^^df`, `^^^^xxxx`) starts at
    /// `buf[k-1]` (whose character is `ch` with category `cat`), reduces it
    /// in the buffer and returns `true` (§355).
    fn reduce_expanded(&mut self, k: usize, ch: u32, cat: u8) -> bool {
        if cat != 7 {
            return false;
        }
        let Some(Level::Text(t)) = self.input.stack.last_mut() else {
            return false;
        };
        if t.buf.get(k) != Some(&ch) {
            return false;
        }
        match expanded_at(&t.buf, k - 1) {
            Expanded::Char { c, len } => {
                t.buf[k - 1] = c;
                t.buf.drain(k..k - 1 + len);
                true
            }
            _ => false,
        }
    }

    /// Gets the next token, setting `cur_tok` too (`get_token`).
    pub fn get_token(&mut self) {
        self.err.no_new_control_sequence = false;
        self.get_next();
        self.err.no_new_control_sequence = true;
        self.cur_tok = self.make_cur_tok();
    }

    /// The token corresponding to `cur_cmd`/`cur_chr`/`cur_cs`.
    #[inline]
    pub fn make_cur_tok(&self) -> Token {
        if self.cur_cs == NO_CS {
            Token::char(self.cur_cmd, self.cur_chr)
        } else {
            Token::cs(self.cur_cs)
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn line_splitting() {
        let data = b"ab  \r\ncd\rx\n\nlast";
        let mut pos = 0;
        let mut lines = Vec::new();
        while let Some((l, next)) = next_line(data, pos) {
            lines.push(decode_line(l));
            pos = next;
        }
        let strs: Vec<String> = lines
            .iter()
            .map(|l| l.iter().map(|&c| char::from_u32(c).unwrap()).collect())
            .collect();
        assert_eq!(strs, vec!["ab", "cd", "x", "", "last"]);
        assert_eq!(decode_line(b"x\t "), vec!['x' as u32, 9]);
    }

    #[test]
    fn expanded_chars() {
        let s = |x: &str| x.chars().map(|c| c as u32).collect::<Vec<_>>();
        assert!(matches!(
            expanded_at(&s("^^A"), 0),
            Expanded::Char { c: 1, len: 3 }
        ));
        assert!(matches!(
            expanded_at(&s("^^e9"), 0),
            Expanded::Char { c: 0xE9, len: 4 }
        ));
        assert!(matches!(
            expanded_at(&s("^^?"), 0),
            Expanded::Char { c: 127, len: 3 }
        ));
        assert!(matches!(
            expanded_at(&s("^^^^00e9"), 0),
            Expanded::Char { c: 0xE9, len: 8 }
        ));
        assert!(matches!(
            expanded_at(&s("^^^^^^01f600"), 0),
            Expanded::Char {
                c: 0x1F600,
                len: 12
            }
        ));
        assert!(matches!(
            expanded_at(&s("^^^^zz"), 0),
            Expanded::Bad {
                six: false,
                short: true
            }
        ));
        assert!(matches!(expanded_at(&s("^x"), 0), Expanded::None));
    }
}