parse.rs

//! Turns a sequence of tokens into a syntax tree

use crate::error::Error;
use crate::node::{self, Align, Class, Level, Limits, Node, Spacing};
use crate::symbol;
use crate::token::{Located, Token, tokenize};


/// The style indicated by the wrapper that was around a formula
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Wrapper {
    /// There was no wrapper
    None,
    /// A wrapper for placing within text: $…$, \(…\) and \begin{math}
    Inline,
    /// A wrapper for a line of its own: $$…$$, \[…\] and \begin{equation}, and also
    /// \begin{align} and \begin{gather}
    Display,
}


/// Turns a LaTeX string into a syntax tree. Removes the wrapper if there is one
pub fn parse(source: &str) -> Result<Node, Error> {
    Ok(parse_wrapped(source)?.0)
}


/// Returns the syntax tree and the style that the wrapper indicated
///
/// The wrapper is optional. If there is one, it decides between display and inline.
/// If there is none, the caller's choice is used as it is
pub fn parse_wrapped(source: &str) -> Result<(Node, Wrapper), Error> {
    let (tokens, wrapper) = unwrap(tokenize(source)?);

    if let Some(stray) = tokens.iter().find(|found| found.token == Token::Character('$')) {
        let message = "$ wraps a formula. Write \\$ for a literal dollar sign";

        return Err(Error::new(message, stray.position));
    }

    let mut parser = Parser {
        tokens,
        position: 0,
        end: source.chars().count(),
        stop_at_bracket: false,
        last_limits: Limits::Never,
    };
    let row = parser.parse_row()?;

    if parser.position < parser.tokens.len() {
        return Err(parser.unexpected());
    }

    Ok((row, wrapper))
}


/// Returns the style the wrapper indicates, or the given value if it indicates none
pub fn display_of(wrapper: Wrapper, fallback: bool) -> bool {
    match wrapper {
        Wrapper::Display => true,
        Wrapper::Inline => false,
        Wrapper::None => fallback,
    }
}


fn is_character(found: &Located, character: char) -> bool {
    found.token == Token::Character(character)
}


fn is_command(found: &Located, name: &str) -> bool {
    matches!(&found.token, Token::Command(found) if found == name)
}


/// Drops head tokens from the front and tail tokens from the back
fn trim(tokens: Vec<Located>, head: usize, tail: usize) -> Vec<Located> {
    let keep = tokens.len().saturating_sub(head + tail);

    tokens.into_iter().skip(head).take(keep).collect()
}


/// Removes the wrapper around a formula
fn unwrap(tokens: Vec<Located>) -> (Vec<Located>, Wrapper) {
    let count = tokens.len();

    if count < 2 {
        return (tokens, Wrapper::None);
    }

    if is_character(&tokens[0], '$') && is_character(&tokens[count - 1], '$') {
        if count >= 4 && is_character(&tokens[1], '$') && is_character(&tokens[count - 2], '$') {
            return (trim(tokens, 2, 2), Wrapper::Display);
        }

        return (trim(tokens, 1, 1), Wrapper::Inline);
    }

    if is_command(&tokens[0], "[") && is_command(&tokens[count - 1], "]") {
        return (trim(tokens, 1, 1), Wrapper::Display);
    }

    if is_command(&tokens[0], "(") && is_command(&tokens[count - 1], ")") {
        return (trim(tokens, 1, 1), Wrapper::Inline);
    }

    unwrap_environment(tokens)
}


/// Removes an environment that starts math mode. Environments used inside math, such as
/// matrices, are not removed here
///
/// In LaTeX, align and gather are used outside math and are typeset in display style.
/// Their contents are typeset in aligned rows, so the environment is kept and display is indicated
fn unwrap_environment(tokens: Vec<Located>) -> (Vec<Located>, Wrapper) {
    let Some(name) = environment_name(&tokens, 0, "begin") else {
        return (tokens, Wrapper::None);
    };
    let (wrapper, keep) = match name.as_str() {
        "equation" | "equation*" | "displaymath" => (Wrapper::Display, false),
        "math" => (Wrapper::Inline, false),
        "align" | "align*" | "alignat" | "alignat*" | "gather" | "gather*" => (Wrapper::Display, true),
        _ => return (tokens, Wrapper::None),
    };
    // \begin{name} and \end{name} each have the command, two braces and the name's characters
    let edge = name.chars().count() + 3;

    if tokens.len() < edge * 2 {
        return (tokens, Wrapper::None);
    }

    match environment_name(&tokens, tokens.len() - edge, "end") {
        Some(closing) if closing == name && keep => (tokens, wrapper),
        Some(closing) if closing == name => (trim(tokens, edge, edge), wrapper),
        _ => (tokens, Wrapper::None),
    }
}


/// Reads the name of a \begin{name} or \end{name} that starts at index at
fn environment_name(tokens: &[Located], at: usize, keyword: &str) -> Option<String> {
    if !is_command(tokens.get(at)?, keyword) || tokens.get(at + 1)?.token != Token::LeftBrace {
        return None;
    }

    let mut name = String::new();
    let mut index = at + 2;

    while let Some(found) = tokens.get(index) {
        match &found.token {
            Token::Character(character)
                if character.is_ascii_alphanumeric() || *character == '*' =>
            {
                name.push(*character);
                index += 1;
            }
            Token::RightBrace => return Some(name),
            _ => return None,
        }
    }

    None
}


struct Parser {
    tokens: Vec<Located>,
    position: usize,
    /// The length of the source string, used as the error position at the end of input
    end: usize,
    /// true only while reading inside \sqrt[...]
    stop_at_bracket: bool,
    /// Whether the last atom read takes its scripts above and below
    last_limits: Limits,
}


impl Parser {
    fn peek(&self) -> Option<Token> {
        self.tokens.get(self.position).map(|located| located.token.clone())
    }

    /// The position of the current token in the source string
    fn spot(&self) -> usize {
        match self.tokens.get(self.position) {
            Some(located) => located.position,
            None => self.end.saturating_sub(1),
        }
    }

    fn unexpected(&self) -> Error {
        let message = match self.tokens.get(self.position).map(|located| &located.token) {
            None => "the formula ends too early".to_string(),
            Some(Token::RightBrace) => "a closing brace has no matching opening brace".to_string(),
            Some(Token::Ampersand) => "& can only be used inside a matrix".to_string(),
            Some(Token::RowBreak) => "\\\\ can only be used inside a matrix".to_string(),
            Some(Token::Caret) => "^ is in the wrong place".to_string(),
            Some(Token::Underscore) => "_ is in the wrong place".to_string(),
            Some(Token::Text(_)) => "\\text is in the wrong place".to_string(),
            Some(Token::LeftBrace) => "an opening brace is in the wrong place".to_string(),
            Some(Token::Command(name)) if name == "end" => {
                "\\end has no matching \\begin".to_string()
            }
            Some(Token::Command(name)) if name == "right" => {
                "\\right has no matching \\left".to_string()
            }
            Some(Token::Command(name)) => format!("unexpected \\{name}"),
            Some(Token::Character(character)) => format!("unexpected character {character}"),
        };
        Error::new(message, self.spot())
    }

    /// Whether the row of items ends here
    fn at_boundary(&self) -> bool {
        match self.tokens.get(self.position).map(|located| &located.token) {
            None | Some(Token::RightBrace) | Some(Token::Ampersand) | Some(Token::RowBreak) => true,
            Some(Token::Command(name)) => name == "end" || name == "right",
            Some(Token::Character(']')) => self.stop_at_bracket,
            _ => false,
        }
    }

    /// Reads items up to a boundary into a Row. Does not consume the boundary token
    fn parse_row(&mut self) -> Result<Node, Error> {
        self.parse_row_from(Vec::new())
    }

    fn parse_row_from(&mut self, mut items: Vec<Node>) -> Result<Node, Error> {
        while !self.at_boundary() {
            // A style switch applies to everything after it
            if let Some(level) = self.style_switch() {
                let rest = self.parse_row()?;
                items.push(Node::Sized {level, body: Box::new(rest)});
                break;
            }
            items.push(self.parse_item()?);
        }
        fix_unary(&mut items);
        Ok(Node::Row(items))
    }

    /// One item. If it has a superscript or subscript, reads them along with it
    fn parse_item(&mut self) -> Result<Node, Error> {
        let base = if matches!(self.peek(), Some(Token::Caret) | Some(Token::Underscore)) {
            node::empty()
        } else {
            self.parse_atom()?
        };
        let mut limits = self.last_limits;
        let mut superscript = None;
        let mut subscript = None;
        loop {
            match self.peek() {
                Some(Token::Caret) => self.parse_script(&mut superscript, '^')?,
                Some(Token::Underscore) => self.parse_script(&mut subscript, '_')?,
                Some(Token::Command(name)) if name == "limits" => {
                    self.position += 1;
                    limits = Limits::Always;
                }
                Some(Token::Command(name)) if name == "nolimits" => {
                    self.position += 1;
                    limits = Limits::Never;
                }
                _ => break,
            }
        }
        if superscript.is_none() && subscript.is_none() {
            return Ok(base);
        }
        Ok(Node::Scripts {base: Box::new(base), superscript, subscript, limits})
    }

    /// From a ^ or _, reads its argument and puts it in slot
    fn parse_script(&mut self, slot: &mut Option<Box<Node>>, mark: char) -> Result<(), Error> {
        let start = self.spot();
        self.position += 1;
        if slot.is_some() {
            return Err(Error::new(format!("{mark} appears twice"), start));
        }
        let argument = self
            .parse_atom()
            .map_err(|error| prefix(error, &format!("after {mark}: ")))?;
        *slot = Some(Box::new(argument));
        Ok(())
    }

    /// One atom: a group in braces, a command or a single character
    fn parse_atom(&mut self) -> Result<Node, Error> {
        self.last_limits = Limits::Never;
        let start = self.spot();
        match self.peek() {
            Some(Token::LeftBrace) => {
                self.position += 1;
                self.finish_group(start)
            }
            Some(Token::Character(character)) => {
                self.position += 1;
                Ok(character_node(character))
            }
            Some(Token::Text(body)) => {
                self.position += 1;
                Ok(Node::Text(body))
            }
            Some(Token::Command(name)) if name != "end" && name != "right" => {
                self.position += 1;
                self.parse_command(&name, start)
            }
            _ => Err(self.unexpected()),
        }
    }

    /// Reads from just after an opening brace up to the closing brace
    fn finish_group(&mut self, start: usize) -> Result<Node, Error> {
        let inside = self.parse_row()?;
        match self.peek() {
            Some(Token::RightBrace) => {
                self.position += 1;
                Ok(inside)
            }
            None => Err(Error::new("an opening brace has no matching closing brace", start)),
            _ => Err(self.unexpected()),
        }
    }

    fn parse_command(&mut self, name: &str, start: usize) -> Result<Node, Error> {
        match name {
            "frac" | "dfrac" | "tfrac" => {
                let numerator = self.argument(&format!("\\{name} numerator"))?;
                let denominator = self.argument(&format!("\\{name} denominator"))?;
                let fraction = Node::Fraction {
                    numerator: Box::new(numerator),
                    denominator: Box::new(denominator),
                    bar: true,
                };
                Ok(fixed_level(name, fraction))
            }
            "binom" | "dbinom" | "tbinom" => {
                let upper = self.argument(&format!("\\{name} above"))?;
                let lower = self.argument(&format!("\\{name} below"))?;
                let stack = Node::Fraction {
                    numerator: Box::new(upper),
                    denominator: Box::new(lower),
                    bar: false,
                };
                let fenced = Node::Fenced {left: "(", right: ")", body: Box::new(stack)};
                Ok(fixed_level(name, fenced))
            }
            "sqrt" => {
                let index = self.parse_optional()?;
                let body = self.argument("\\sqrt body")?;
                Ok(Node::Root {index: index.map(Box::new), body: Box::new(body)})
            }
            "overline" | "bar" => {
                let body = self.argument(&format!("\\{name} body"))?;
                Ok(Node::Line {body: Box::new(body), above: true})
            }
            "cfrac" => {
                let numerator = self.argument("\\cfrac numerator")?;
                let denominator = self.argument("\\cfrac denominator")?;
                let fraction = Node::Fraction {
                    numerator: Box::new(numerator),
                    denominator: Box::new(denominator),
                    bar: true,
                };
                Ok(Node::Sized {level: Level::Display, body: Box::new(fraction)})
            }
            "overset" | "stackrel" => {
                let above = self.argument(&format!("\\{name} above"))?;
                let base = self.argument(&format!("\\{name} base"))?;
                Ok(Node::Scripts {
                    base: Box::new(base),
                    superscript: Some(Box::new(above)),
                    subscript: None,
                    limits: Limits::Always,
                })
            }
            "underset" => {
                let below = self.argument("\\underset below")?;
                let base = self.argument("\\underset base")?;
                Ok(Node::Scripts {
                    base: Box::new(base),
                    superscript: None,
                    subscript: Some(Box::new(below)),
                    limits: Limits::Always,
                })
            }
            "overbrace" | "underbrace" => {
                let above = name == "overbrace";
                let body = self.argument(&format!("\\{name} body"))?;
                let mark = if above {"\u{23de}"} else {"\u{23df}"};
                self.last_limits = Limits::Always;
                Ok(Node::Accent {mark, body: Box::new(body), above})
            }
            "overrightarrow" | "overleftarrow" => {
                let body = self.argument(&format!("\\{name} body"))?;
                let mark = if name == "overrightarrow" {"\u{20d7}"} else {"\u{20d6}"};
                Ok(Node::Accent {mark, body: Box::new(body), above: true})
            }
            "xrightarrow" | "xleftarrow" | "xhookrightarrow" | "xrightleftharpoons" => {
                let below = self.parse_optional()?;
                let above = self.argument(&format!("\\{name} above"))?;
                let mark = match name {
                    "xleftarrow" => "\u{27f5}",
                    "xhookrightarrow" => "\u{21aa}",
                    "xrightleftharpoons" => "\u{21cc}",
                    _ => "\u{27f6}",
                };
                Ok(Node::Extend {
                    mark,
                    above: Some(Box::new(above)),
                    below: below.map(Box::new),
                })
            }
            "substack" => self.parse_substack(start),
            "pmod" | "mod" => {
                let value = self.argument(&format!("\\{name} body"))?;
                Ok(modulo(value, name == "pmod"))
            }
            "big" | "Big" | "bigg" | "Bigg" | "bigl" | "Bigl" | "biggl" | "Biggl"
            | "bigr" | "Bigr" | "biggr" | "Biggr" | "bigm" | "Bigm" | "biggm" | "Biggm" => {
                self.parse_sized_delimiter(name)
            }
            "displaystyle" | "textstyle" | "scriptstyle" | "scriptscriptstyle" => {
                Err(Error::new(format!("\\{name} must come at the start of a group"), start))
            }
            "underline" => {
                let body = self.argument("\\underline body")?;
                Ok(Node::Line {body: Box::new(body), above: false})
            }
            "phantom" | "hphantom" | "vphantom" => {
                let body = self.argument(&format!("\\{name} body"))?;

                Ok(Node::Phantom {
                    body: Box::new(body),
                    width: name != "vphantom",
                    height: name != "hphantom",
                })
            }
            "operatorname" => {
                // Like \lim, \operatorname* puts its scripts above and below in display style
                let starred = matches!(self.peek(), Some(Token::Character('*')));

                if starred {
                    self.position += 1;
                }

                let body = self.argument("\\operatorname body")?;
                self.last_limits = if starred {Limits::Auto} else {Limits::Never};

                Ok(Node::Operator {body: Box::new(body)})
            }
            "left" => self.parse_fence(start),
            "begin" => self.parse_environment(start),
            "limits" | "nolimits" => Err(Error::new(
                format!("\\{name} can only come right after an operator"),
                start,
            )),
            "hline" => Err(Error::new("\\hline can only come at the start of a matrix row", start)),
            "[" | "]" | "(" | ")" => Err(Error::new(
                format!("\\{name} can only wrap a whole formula"),
                start,
            )),
            _ => self.parse_named(name, start),
        }
    }

    /// Commands that are resolved by looking them up in the tables
    fn parse_named(&mut self, name: &str, start: usize) -> Result<Node, Error> {
        if let Some(style) = symbol::style(name) {
            let body = self.argument(&format!("\\{name} body"))?;
            return Ok(Node::Styled {style, body: Box::new(body)});
        }
        if let Some(mark) = symbol::accent(name) {
            let body = self.argument(&format!("\\{name} body"))?;
            return Ok(Node::Accent {mark, body: Box::new(body), above: true});
        }
        if let Some(width) = symbol::space(name) {
            return Ok(Node::Symbol {text: String::new(), class: Class::Space(width)});
        }
        match symbol::symbol(name) {
            Some((text, class)) => {
                self.last_limits = if symbol::takes_limits(name) {
                    Limits::Auto
                } else {
                    Limits::Never
                };
                Ok(Node::Symbol {text: text.to_string(), class})
            }
            None => Err(Error::new(format!("unsupported command: \\{name}"), start)),
        }
    }

    /// Reads one argument of a command. On failure, notes which command the argument was for
    fn argument(&mut self, owner: &str) -> Result<Node, Error> {
        self.parse_atom().map_err(|error| prefix(error, &format!("{owner}: ")))
    }

    /// If the next token is a command that switches the style, returns its level and moves past it
    fn style_switch(&mut self) -> Option<Level> {
        let Some(Token::Command(name)) = self.peek() else {
            return None;
        };
        let level = match name.as_str() {
            "displaystyle" => Level::Display,
            "textstyle" => Level::Text,
            "scriptstyle" => Level::Script,
            "scriptscriptstyle" => Level::ScriptScript,
            _ => return None,
        };
        self.position += 1;
        Some(level)
    }


    /// Reads a delimiter with a fixed size, such as \big
    fn parse_sized_delimiter(&mut self, name: &str) -> Result<Node, Error> {
        let text = self.read_delimiter(&format!("\\{name}"))?;
        let height = if name.starts_with("Bigg") {
            3.0
        } else if name.starts_with("bigg") {
            2.4
        } else if name.starts_with("Big") {
            1.8
        } else {
            1.2
        };
        let class = match name.chars().last() {
            Some('l') => Class::Open,
            Some('r') => Class::Close,
            Some('m') => Class::Relation,
            _ => Class::Ordinary,
        };
        Ok(Node::Delimiter {text, height, class})
    }


    /// Reads \substack{a \\ b}
    fn parse_substack(&mut self, start: usize) -> Result<Node, Error> {
        if self.peek() != Some(Token::LeftBrace) {
            return Err(Error::new("\\substack must be followed by {…}", start));
        }

        self.position += 1;
        let mut rows = Vec::new();

        loop {
            rows.push(vec![self.parse_row()?]);

            match self.peek() {
                Some(Token::RowBreak) => self.position += 1,
                Some(Token::RightBrace) => {
                    self.position += 1;

                    return Ok(Node::Matrix {
                        rows,
                        left: "",
                        right: "",
                        align: vec![Align::Center],
                        lines: Vec::new(),
                        spacing: Spacing::Matrix,
                    });
                }
                _ => return Err(self.unexpected()),
            }
        }
    }


    /// Reads the [3] in \sqrt[3]
    fn parse_optional(&mut self) -> Result<Option<Node>, Error> {
        if self.peek() != Some(Token::Character('[')) {
            return Ok(None);
        }
        let start = self.spot();
        self.position += 1;
        let outer = self.stop_at_bracket;
        self.stop_at_bracket = true;
        let inside = self.parse_row();
        self.stop_at_bracket = outer;
        let inside = inside?;
        match self.peek() {
            Some(Token::Character(']')) => {
                self.position += 1;
                Ok(Some(inside))
            }
            _ => Err(Error::new("[ has no matching ]", start)),
        }
    }

    /// Reads from \left to \right
    fn parse_fence(&mut self, start: usize) -> Result<Node, Error> {
        let left = self.read_delimiter("\\left")?;
        let body = self.parse_row()?;
        match self.peek() {
            Some(Token::Command(name)) if name == "right" => {
                self.position += 1;
                let right = self.read_delimiter("\\right")?;
                Ok(Node::Fenced {left, right, body: Box::new(body)})
            }
            _ => Err(Error::new("\\left has no matching \\right", start)),
        }
    }

    /// Reads the delimiter after \left or \right
    fn read_delimiter(&mut self, owner: &str) -> Result<&'static str, Error> {
        let spot = self.spot();
        let key = match self.peek() {
            Some(Token::Character(character)) => character.to_string(),
            Some(Token::Command(name)) => format!("\\{name}"),
            _ => return Err(Error::new(format!("{owner} must be followed by a delimiter"), spot)),
        };
        match symbol::delimiter(&key) {
            Some(found) => {
                self.position += 1;
                Ok(found)
            }
            None => Err(Error::new(format!("{owner} does not accept this delimiter: {key}"), spot)),
        }
    }

    fn parse_environment(&mut self, start: usize) -> Result<Node, Error> {
        let name = self.parse_environment_name(start)?;

        if let Some(spacing) = aligned_spacing(&name) {
            return self.parse_aligned(&name, spacing, start);
        }

        let (left, right, default_align) = match name.as_str() {
            "matrix" => ("", "", Align::Center),
            "pmatrix" => ("(", ")", Align::Center),
            "bmatrix" => ("[", "]", Align::Center),
            "Bmatrix" => ("{", "}", Align::Center),
            "vmatrix" => ("|", "|", Align::Center),
            "Vmatrix" => ("‖", "‖", Align::Center),
            "array" => ("", "", Align::Center),
            "cases" => ("{", "", Align::Left),
            _ => return Err(Error::new(format!("unsupported environment: {name}"), start)),
        };
        let mut align = if name == "array" {
            self.parse_column_spec(start)?
        } else {
            Vec::new()
        };
        let (rows, lines) = self.parse_cells(&name, start, false)?;
        self.close_environment(&name, start)?;
        let columns = rows.iter().map(Vec::len).max().unwrap_or(0);
        while align.len() < columns {
            align.push(default_align);
        }
        Ok(Node::Matrix {rows, left, right, align, lines, spacing: Spacing::Matrix})
    }

    fn parse_aligned(&mut self, name: &str, spacing: Spacing, start: usize) -> Result<Node, Error> {
        let gather = matches!(name, "gather" | "gather*" | "gathered");
        let pair_count = if spacing == Spacing::Alignat {Some(self.parse_pair_count(start)?)} else {None};
        let (rows, lines) = self.parse_cells(name, start, !gather)?;
        self.close_environment(name, start)?;
        let columns = rows.iter().map(Vec::len).max().unwrap_or(0);

        if gather && columns > 1 {
            return Err(Error::new(format!("& cannot be used in {name}"), start));
        }

        if let Some(count) = pair_count.filter(|count| columns > count * 2) {
            let message = format!("{name} has more columns than the pairs in {{{count}}} allow");
            return Err(Error::new(message, start));
        }

        let align = (0..columns)
            .map(|index| match (gather, index % 2) {
                (true, _) => Align::Center,
                (false, 0) => Align::Right,
                _ => Align::Left,
            })
            .collect();
        let rows = rows
            .into_iter()
            .map(|row| {
                row.into_iter()
                    .map(|cell| Node::Sized {level: Level::Display, body: Box::new(cell)})
                    .collect()
            })
            .collect();

        Ok(Node::Matrix {rows, left: "", right: "", align, lines, spacing})
    }

    fn parse_pair_count(&mut self, start: usize) -> Result<usize, Error> {
        if self.peek() != Some(Token::LeftBrace) {
            return Err(Error::new("alignat must be followed by {number of pairs}", start));
        }

        self.position += 1;
        let mut digits = String::new();

        while let Some(Token::Character(character)) = self.peek() {
            if !character.is_ascii_digit() {
                break;
            }

            digits.push(character);
            self.position += 1;
        }

        if self.peek() != Some(Token::RightBrace) {
            return Err(Error::new("the number of pairs must be written in digits", self.spot()));
        }

        self.position += 1;

        match digits.parse::<usize>() {
            Ok(count) if count > 0 => Ok(count),
            _ => Err(Error::new("the number of pairs must be 1 or more", start)),
        }
    }

    fn close_environment(&mut self, name: &str, start: usize) -> Result<(), Error> {
        let closing = self.parse_environment_name(start)?;

        if closing != name {
            let message = format!("\\begin{{{name}}} does not match \\end{{{closing}}}");
            return Err(Error::new(message, start));
        }

        Ok(())
    }

    /// The {environment name} after \begin or \end
    fn parse_environment_name(&mut self, start: usize) -> Result<String, Error> {
        if self.peek() != Some(Token::LeftBrace) {
            return Err(Error::new("\\begin and \\end must be followed by {environment name}", start));
        }
        self.position += 1;
        let mut name = String::new();
        loop {
            match self.peek() {
                Some(Token::Character(character))
                    if character.is_ascii_alphanumeric() || character == '*' =>
                {
                    name.push(character);
                    self.position += 1;
                }
                Some(Token::RightBrace) => {
                    self.position += 1;
                    return Ok(name);
                }
                _ => return Err(Error::new("environment names must be alphanumeric", self.spot())),
            }
        }
    }

    /// Reads the {ccc} of array
    fn parse_column_spec(&mut self, start: usize) -> Result<Vec<Align>, Error> {
        if self.peek() != Some(Token::LeftBrace) {
            return Err(Error::new("array must be followed by {column format}", start));
        }
        self.position += 1;
        let mut align = Vec::new();
        loop {
            let found = match self.peek() {
                Some(Token::Character('l')) => Some(Align::Left),
                Some(Token::Character('c')) => Some(Align::Center),
                Some(Token::Character('r')) => Some(Align::Right),
                Some(Token::Character('|')) => None,
                Some(Token::RightBrace) => {
                    self.position += 1;
                    return Ok(align);
                }
                _ => return Err(Error::new("the column format allows only l, c and r", self.spot())),
            };
            self.position += 1;
            if let Some(found) = found {
                align.push(found);
            }
        }
    }

    /// The contents of a matrix. Cells are separated by & and rows by \\
    ///
    /// If seed is true, puts an empty group at the start of columns 2, 4 and so on.
    /// As in LaTeX's align, the = in &= then gets the space of a relation even when
    /// there is nothing on its left
    fn parse_cells(
        &mut self,
        name: &str,
        start: usize,
        seed: bool,
    ) -> Result<(Vec<Vec<Node>>, Vec<usize>), Error> {
        let mut rows: Vec<Vec<Node>> = Vec::new();
        let mut lines: Vec<usize> = Vec::new();
        let mut row: Vec<Node> = Vec::new();
        loop {
            if row.is_empty() {
                while self.peek() == Some(Token::Command("hline".to_string())) {
                    self.position += 1;
                    lines.push(rows.len());
                }
            }
            let lead = if seed && row.len() % 2 == 1 {vec![node::empty()]} else {Vec::new()};
            row.push(self.parse_row_from(lead)?);
            match self.peek() {
                Some(Token::Ampersand) => self.position += 1,
                Some(Token::RowBreak) => {
                    self.position += 1;
                    rows.push(std::mem::take(&mut row));
                }
                Some(Token::Command(command)) if command == "end" => {
                    self.position += 1;
                    let trailing = row.len() == 1 && node::is_empty(&row[0]) && !rows.is_empty();
                    if !trailing {
                        rows.push(row);
                    }
                    return Ok((rows, lines));
                }
                None => {
                    let message = format!("\\begin{{{name}}} has no matching \\end");
                    return Err(Error::new(message, start));
                }
                _ => return Err(self.unexpected()),
            }
        }
    }
}


fn aligned_spacing(name: &str) -> Option<Spacing> {
    match name {
        "align" | "align*" | "aligned" | "split" | "gather" | "gather*" | "gathered" => Some(Spacing::Align),
        "alignat" | "alignat*" | "alignedat" => Some(Spacing::Alignat),
        _ => None,
    }
}


/// Builds \pmod{n} and \mod{n}
fn modulo(value: Node, parenthesis: bool) -> Node {
    let space = |width: f64| Node::Symbol {text: String::new(), class: Class::Space(width)};
    let word = |text: &str, class: Class| Node::Symbol {text: text.to_string(), class};
    let mut items = vec![space(1.0)];

    if parenthesis {
        items.push(word("(", Class::Open));
    }

    items.push(word("mod", Class::Ordinary));
    items.push(space(4.0 / 18.0));
    items.push(value);

    if parenthesis {
        items.push(word(")", Class::Close));
    }

    Node::Row(items)
}


/// Wraps a command such as \dfrac or \tbinom, whose name fixes the style level
///
/// Names starting with d are typeset in display style, and names starting with t in text style.
/// This is built the same way as \cfrac
fn fixed_level(name: &str, body: Node) -> Node {
    let level = match name.chars().next() {
        Some('d') => Level::Display,
        Some('t') => Level::Text,
        _ => return body,
    };

    Node::Sized {level, body: Box::new(body)}
}


/// Puts where the error happened in front of its message
fn prefix(error: Error, text: &str) -> Error {
    Error {message: format!("{text}{}", error.message), position: error.position}
}


/// Turns a single character into a symbol node
fn character_node(character: char) -> Node {
    let (text, class) = match character {
        'a'..='z' | 'A'..='Z' => (character.to_string(), Class::Variable),
        '+' => ("+".to_string(), Class::Binary),
        '-' => ("−".to_string(), Class::Binary),
        '*' => ("∗".to_string(), Class::Binary),
        '=' | '<' | '>' => (character.to_string(), Class::Relation),
        ':' => (":".to_string(), Class::Relation),
        '(' | '[' => (character.to_string(), Class::Open),
        ')' | ']' => (character.to_string(), Class::Close),
        ',' | ';' => (character.to_string(), Class::Punctuation),
        '\'' => ("′".to_string(), Class::Ordinary),
        _ => (character.to_string(), Class::Ordinary),
    };
    Node::Symbol {text, class}
}


/// A + or − at the start of a row or right after a symbol is not a binary operator, so it is
/// changed to an ordinary symbol
fn fix_unary(items: &mut [Node]) {
    let mut wants_operand = true;
    for item in items.iter_mut() {
        match item {
            Node::Symbol {class, ..} => {
                if matches!(class, Class::Space(_)) {
                    continue;
                }
                if *class == Class::Binary && wants_operand {
                    *class = Class::Ordinary;
                }
                wants_operand = matches!(
                    *class,
                    Class::Binary
                        | Class::Relation
                        | Class::Open
                        | Class::Punctuation
                        | Class::Large
                        | Class::Function
                );
            }
            // After \operatorname, as after \sin, + and − become signs
            Node::Operator {..} => wants_operand = true,
            _ => wants_operand = false,
        }
    }
}


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

    fn symbol_at(node: &Node, index: usize) -> (String, Class) {
        match node {
            Node::Row(items) => match &items[index] {
                Node::Symbol {text, class} => (text.clone(), *class),
                other => panic!("not a symbol: {other:?}"),
            },
            other => panic!("not a Row: {other:?}"),
        }
    }

    #[test]
    fn reads_a_fraction() {
        let tree = parse(r"\frac{a}{b}").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        assert!(matches!(items[0], Node::Fraction {bar: true, ..}));
    }

    #[test]
    fn fixed_fractions_carry_their_level() {
        for (source, wanted) in [
            (r"\dfrac{a}{b}", Level::Display),
            (r"\tfrac{a}{b}", Level::Text),
            (r"\dbinom{n}{k}", Level::Display),
            (r"\tbinom{n}{k}", Level::Text),
        ] {
            let tree = parse(source).unwrap();
            let Node::Row(items) = &tree else {panic!("not a Row")};
            assert!(
                matches!(&items[0], Node::Sized {level, ..} if *level == wanted),
                "no level attached: {source}"
            );
        }

        let tree = parse(r"\frac{a}{b}").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        assert!(matches!(items[0], Node::Fraction {..}), "\\frac has a level attached");
    }

    #[test]
    fn unary_minus_becomes_ordinary() {
        assert_eq!(symbol_at(&parse("-x").unwrap(), 0).1, Class::Ordinary);
        assert_eq!(symbol_at(&parse("a-b").unwrap(), 1).1, Class::Binary);
        assert_eq!(symbol_at(&parse("=-1").unwrap(), 1).1, Class::Ordinary);
    }

    #[test]
    fn spaces_do_not_break_the_unary_rule() {
        assert_eq!(symbol_at(&parse(r"a \quad - b").unwrap(), 2).1, Class::Binary);
    }

    #[test]
    fn reads_scripts() {
        let tree = parse("x_i^2").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        let Node::Scripts {superscript, subscript, ..} = &items[0] else {
            panic!("not Scripts")
        };
        assert!(superscript.is_some());
        assert!(subscript.is_some());
    }

    #[test]
    fn large_operators_take_limits_by_default() {
        let tree = parse(r"\sum_{k}^{n}").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        assert!(matches!(items[0], Node::Scripts {limits: Limits::Auto, ..}));

        let tree = parse(r"\int_0^1").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        assert!(matches!(items[0], Node::Scripts {limits: Limits::Never, ..}));

        let tree = parse(r"\sum\nolimits_k").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        assert!(matches!(items[0], Node::Scripts {limits: Limits::Never, ..}));
    }

    #[test]
    fn reads_root_with_an_index() {
        let tree = parse(r"\sqrt[3]{x}").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        let Node::Root {index, ..} = &items[0] else {panic!("not a Root")};
        assert!(index.is_some());
        assert!(matches!(parse(r"\sqrt{x}").unwrap(), Node::Row(ref items)
            if matches!(items[0], Node::Root {index: None, ..})));
    }

    #[test]
    fn reads_fences() {
        let tree = parse(r"\left( x \right)").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        assert!(matches!(&items[0], Node::Fenced {left: "(", right: ")", ..}));

        let tree = parse(r"\left. x \right|").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        assert!(matches!(&items[0], Node::Fenced {left: "", right: "|", ..}));
    }

    #[test]
    fn matrix_shape_and_lines() {
        fn shape(source: &str) -> (Vec<usize>, Vec<usize>) {
            match parse(source).unwrap() {
                Node::Row(items) => match &items[0] {
                    Node::Matrix {rows, lines, ..} => {
                        (rows.iter().map(Vec::len).collect(), lines.clone())
                    }
                    other => panic!("not a matrix: {other:?}"),
                },
                other => panic!("not a Row: {other:?}"),
            }
        }
        assert_eq!(shape(r"\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix}").0, vec![3, 3]);
        assert_eq!(shape(r"\begin{matrix} a \\ b \\ \end{matrix}").0, vec![1, 1]);
        assert_eq!(shape(r"\begin{array}{cc} \hline a & b \\ \hline \end{array}").1, vec![0, 1]);
    }

    #[test]
    fn array_reads_its_column_spec() {
        let tree = parse(r"\begin{array}{l|rc} a & b & c \end{array}").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        let Node::Matrix {align, ..} = &items[0] else {panic!("not a matrix")};
        assert_eq!(align, &vec![Align::Left, Align::Right, Align::Center]);
    }

    #[test]
    fn cases_align_to_the_left() {
        let tree = parse(r"\begin{cases} a & b \\ c & d \end{cases}").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        let Node::Matrix {align, left, ..} = &items[0] else {panic!("not a matrix")};
        assert_eq!(*left, "{");
        assert_eq!(align, &vec![Align::Left, Align::Left]);
    }

    #[test]
    fn reads_text_and_styles() {
        assert_eq!(parse(r"\text{a b}").unwrap(), Node::Row(vec![Node::Text("a b".to_string())]));
        let tree = parse(r"\mathbb{R}").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        assert!(matches!(items[0], Node::Styled {style: crate::node::Style::Blackboard, ..}));
    }

    #[test]
    fn operator_names_read_as_functions() {
        let tree = parse(r"\operatorname{ht} x").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        assert!(matches!(items[0], Node::Operator {..}));
        assert_eq!(crate::node::class_of(&items[0]), Class::Function);

        let tree = parse(r"\operatorname{gr}_i").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        assert!(matches!(items[0], Node::Scripts {limits: Limits::Never, ..}));

        let tree = parse(r"\operatorname*{argmax}_x").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        assert!(matches!(items[0], Node::Scripts {limits: Limits::Auto, ..}));

        assert_eq!(symbol_at(&parse(r"\operatorname{sgn} -x").unwrap(), 1).1, Class::Ordinary);
    }

    #[test]
    fn wrappers_choose_the_shape_and_come_off() {
        let plain = parse("x^2").unwrap();

        for (source, wanted) in [
            ("$x^2$", Wrapper::Inline),
            ("$$x^2$$", Wrapper::Display),
            (r"\[x^2\]", Wrapper::Display),
            (r"\(x^2\)", Wrapper::Inline),
            (r"\begin{equation} x^2 \end{equation}", Wrapper::Display),
            (r"\begin{equation*} x^2 \end{equation*}", Wrapper::Display),
            (r"\begin{displaymath} x^2 \end{displaymath}", Wrapper::Display),
            (r"\begin{math} x^2 \end{math}", Wrapper::Inline),
            ("x^2", Wrapper::None),
        ] {
            let (node, wrapper) = parse_wrapped(source).unwrap();
            assert_eq!(wrapper, wanted, "wrong wrapper: {source}");
            assert_eq!(node, plain, "the contents changed: {source}");
        }
    }

    #[test]
    fn environments_used_inside_math_are_not_wrappers() {
        let (node, wrapper) = parse_wrapped(r"\begin{pmatrix} a & b \end{pmatrix}").unwrap();
        assert_eq!(wrapper, Wrapper::None);
        let Node::Row(items) = &node else {panic!("not a Row")};
        assert!(matches!(items[0], Node::Matrix {..}));
    }

    fn matrix_of(source: &str) -> (Vec<Vec<Node>>, Vec<Align>, Spacing) {
        match parse(source).unwrap() {
            Node::Row(items) => match &items[0] {
                Node::Matrix {rows, align, spacing, ..} => (rows.clone(), align.clone(), *spacing),
                other => panic!("not a matrix: {other:?}"),
            },
            other => panic!("not a Row: {other:?}"),
        }
    }

    #[test]
    fn align_alternates_right_and_left() {
        for source in [
            r"\begin{align} a &= b & c &= d \end{align}",
            r"\begin{align*} a &= b & c &= d \end{align*}",
            r"\begin{aligned} a &= b & c &= d \end{aligned}",
        ] {
            let (rows, align, spacing) = matrix_of(source);
            assert_eq!(align, vec![Align::Right, Align::Left, Align::Right, Align::Left], "{source}");
            assert_eq!(spacing, Spacing::Align, "{source}");
            assert_eq!(rows[0].len(), 4, "{source}");
        }

        let (rows, _, _) = matrix_of(r"\begin{align} a &= b \\ c &= d \\ \end{align}");
        assert_eq!(rows.len(), 2, "the last \\\\ makes an empty row");
    }

    #[test]
    fn aligned_cells_are_display_and_the_left_columns_start_with_an_empty_group() {
        let (rows, _, _) = matrix_of(r"\begin{aligned} a &= b \end{aligned}");
        let Node::Sized {level: Level::Display, body} = &rows[0][1] else {panic!("not wrapped in display")};
        let Node::Row(items) = body.as_ref() else {panic!("not a Row")};
        assert!(node::is_empty(&items[0]), "no empty group");
        assert!(matches!(&items[1], Node::Symbol {class: Class::Relation, ..}));

        let Node::Sized {body, ..} = &rows[0][0] else {panic!("not wrapped in display")};
        let Node::Row(items) = body.as_ref() else {panic!("not a Row")};
        assert!(matches!(&items[0], Node::Symbol {class: Class::Variable, ..}), "empty group in a right-aligned column");
    }

    #[test]
    fn gather_centers_a_single_column() {
        for source in [
            r"\begin{gather} a \\ b + c \end{gather}",
            r"\begin{gather*} a \\ b + c \end{gather*}",
            r"\begin{gathered} a \\ b + c \end{gathered}",
        ] {
            let (rows, align, spacing) = matrix_of(source);
            assert_eq!(rows.len(), 2, "{source}");
            assert_eq!(align, vec![Align::Center], "{source}");
            assert_eq!(spacing, Spacing::Align, "{source}");
        }

        assert!(parse(r"\begin{gather} a & b \end{gather}").is_err());
    }

    #[test]
    fn alignat_reads_its_pair_count() {
        for source in [
            r"\begin{alignat}{2} a &= b & c &= d \end{alignat}",
            r"\begin{alignat*}{2} a &= b & c &= d \end{alignat*}",
            r"\begin{alignedat}{2} a &= b & c &= d \end{alignedat}",
        ] {
            let (_, align, spacing) = matrix_of(source);
            assert_eq!(align.len(), 4, "{source}");
            assert_eq!(spacing, Spacing::Alignat, "{source}");
        }

        assert!(parse(r"\begin{alignat}{1} a &= b & c &= d \end{alignat}").is_err());
        assert!(parse(r"\begin{alignat} a &= b \end{alignat}").is_err());
        assert!(parse(r"\begin{alignat}{0} a &= b \end{alignat}").is_err());
        assert!(parse(r"\begin{alignat}{x} a &= b \end{alignat}").is_err());
    }

    #[test]
    fn align_and_gather_are_display_and_keep_their_rows() {
        for source in [
            r"\begin{align} a &= b \\ c &= d \end{align}",
            r"\begin{align*} a &= b \end{align*}",
            r"\begin{gather} a \\ b \end{gather}",
            r"\begin{gather*} a \\ b \end{gather*}",
            r"\begin{alignat}{1} a &= b \end{alignat}",
            r"\begin{alignat*}{1} a &= b \end{alignat*}",
        ] {
            let (node, wrapper) = parse_wrapped(source).unwrap();
            assert_eq!(wrapper, Wrapper::Display, "{source}");
            let Node::Row(items) = &node else {panic!("not a Row")};
            assert!(matches!(items[0], Node::Matrix {..}), "not a matrix: {source}");
        }

        for source in [
            r"\begin{aligned} a &= b \end{aligned}",
            r"\begin{gathered} a \\ b \end{gathered}",
            r"\begin{split} a &= b \end{split}",
        ] {
            let (_, wrapper) = parse_wrapped(source).unwrap();
            assert_eq!(wrapper, Wrapper::None, "{source}");
        }
    }

    #[test]
    fn split_sits_inside_equation() {
        let source = r"\begin{equation} \begin{split} a &= b \\ &= c \end{split} \end{equation}";
        let (node, wrapper) = parse_wrapped(source).unwrap();
        assert_eq!(wrapper, Wrapper::Display);
        let Node::Row(items) = &node else {panic!("not a Row")};
        let Node::Matrix {rows, spacing, ..} = &items[0] else {panic!("not a matrix")};
        assert_eq!(rows.len(), 2);
        assert_eq!(*spacing, Spacing::Align);
    }

    #[test]
    fn a_lone_dollar_is_an_error() {
        for source in ["$x", "x$", "a $ b", "$$x$"] {
            let error = parse(source).unwrap_err();
            assert!(error.message.contains("wraps a formula"), "{source}: {}", error.message);
        }

        // To show it as a character, escape it
        assert!(parse(r"\$100").is_ok());
        // Inside \text, it is kept as it is
        assert!(parse(r"\text{100$}").is_ok());
    }

    #[test]
    fn wrapper_commands_are_refused_in_the_middle() {
        let error = parse(r"x + \[ y \]").unwrap_err();
        assert!(error.message.contains("wrap a whole formula"), "{}", error.message);
    }

    #[test]
    fn stacking_commands_force_the_limits() {
        let tree = parse(r"\overset{f}{\to}").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        assert!(matches!(items[0], Node::Scripts {limits: Limits::Always, ..}));

        let tree = parse(r"\underset{g}{\to}").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        let Node::Scripts {subscript, superscript, ..} = &items[0] else {
            panic!("not Scripts")
        };
        assert!(subscript.is_some() && superscript.is_none());
    }

    #[test]
    fn a_style_switch_covers_the_rest_of_the_row() {
        let tree = parse(r"a \displaystyle b c").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        assert_eq!(items.len(), 2, "the items after the switch are not grouped");
        assert!(matches!(items[1], Node::Sized {level: Level::Display, ..}));
    }

    #[test]
    fn sized_delimiters_carry_their_height() {
        let tree = parse(r"\bigl( \Bigg]").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        let Node::Delimiter {height, class, ..} = &items[0] else {panic!("not a Delimiter")};
        assert_eq!(*height, 1.2);
        assert_eq!(*class, Class::Open);
        let Node::Delimiter {height, ..} = &items[1] else {panic!("not a Delimiter")};
        assert_eq!(*height, 3.0);
    }

    #[test]
    fn an_extending_arrow_takes_a_label_above_and_below() {
        let tree = parse(r"\xrightarrow[g]{f}").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        let Node::Extend {above, below, ..} = &items[0] else {panic!("not an Extend")};
        assert!(above.is_some() && below.is_some());

        let tree = parse(r"\xrightarrow{f}").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        let Node::Extend {below, ..} = &items[0] else {panic!("not an Extend")};
        assert!(below.is_none());
    }

    #[test]
    fn substack_stacks_its_rows() {
        let tree = parse(r"\substack{i = 1 \\ i \neq j}").unwrap();
        let Node::Row(items) = &tree else {panic!("not a Row")};
        let Node::Matrix {rows, left, ..} = &items[0] else {panic!("not a matrix")};
        assert_eq!(rows.len(), 2);
        assert_eq!(*left, "");
    }

    #[test]
    fn reports_where_it_failed() {
        let error = parse(r"x + \foo").unwrap_err();
        assert_eq!(error.position, 4);
        assert!(error.message.contains("\\foo"));

        let error = parse(r"\frac{a}{b").unwrap_err();
        assert!(error.message.starts_with("\\frac denominator: "));
    }

    #[test]
    fn errors() {
        assert!(parse("{x").is_err());
        assert!(parse("x}").is_err());
        assert!(parse(r"\foo").is_err());
        assert!(parse(r"\frac{a}").is_err());
        assert!(parse("x^").is_err());
        assert!(parse("x^1^2").is_err());
        assert!(parse("a & b").is_err());
        assert!(parse(r"a \\ b").is_err());
        assert!(parse(r"\begin{pmatrix} a & b").is_err());
        assert!(parse(r"\begin{pmatrix} a \end{bmatrix}").is_err());
        assert!(parse(r"\begin{foo} a \end{foo}").is_err());
        assert!(parse(r"\end{matrix}").is_err());
        assert!(parse(r"\left( x").is_err());
        assert!(parse(r"x \right)").is_err());
        assert!(parse(r"\left x \right x").is_err());
        assert!(parse(r"\sqrt[3{x}").is_err());
    }
}