parse.rs

//! Turns a sequence of tokens into a syntax tree
//!
//! A molecule is written as "atom, bond, atom, bond, ...". Everything after a bond is read as a
//! new molecule, so the tree extends to the right. A branch in parentheses can come in between,
//! and it is attached to the atom being read at that point.
//!
//! Inside a ring, a bond that is not in parentheses is a side of the ring itself.
//! A chain that goes out from a ring atom must always be put in parentheses.

use crate::error::Error;
use crate::node::{Angle, Atom, Bond, DEFAULT_HOOK, Hook, Kind, Node, Ring};
use crate::token::{Located, Token, tokenize};


/// The outer wrapper
///
/// This lets `\chemfig{...}` be pasted as it is from a LaTeX document.
/// For `\chemname{\chemfig{...}}{name}`, the name is taken out too
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Wrapper {
    /// There was no wrapper
    None,
    /// `\chemfig{...}`
    Chemfig,
    /// `\chemname{...}{name}`. It holds the name
    Named(String),
}


/// Turns the string of a molecule into a syntax tree. The outer wrapper is removed
pub fn parse(source: &str) -> Result<Node, Error> {
    Ok(parse_wrapped(source)?.0)
}


/// Turns the string of a molecule into a syntax tree, and also returns which wrapper it had
pub fn parse_wrapped(source: &str) -> Result<(Node, Wrapper), Error> {
    let character: Vec<char> = source.chars().collect();
    let cut = strip(&character, 0)?;

    match parse_body(&cut.body) {
        Ok(node) => Ok((node, cut.wrapper)),
        // Convert the position back to one counted in the original string
        Err(reason) => Err(Error::new(reason.message, reason.position + cut.offset)),
    }
}


/// Turns the contents, with the wrapper removed, into a syntax tree
fn parse_body(source: &str) -> Result<Node, Error> {
    let token = tokenize(source)?;
    let mut reader = Reader {token, position: 0, end: source.chars().count()};
    let node = reader.molecule()?;

    match reader.look() {
        Some(Token::Close) => Err(Error::new("対応する ( のない ) です", reader.spot())),
        Some(_) => Err(Error::new("ここは読めません", reader.spot())),
        None => Ok(node),
    }
}


/// The result of removing the wrapper. offset is where body starts in the original string
struct Stripped {
    body: String,
    offset: usize,
    wrapper: Wrapper,
}


/// Removes the outer wrapper. at is where character starts in the original string
fn strip(character: &[char], at: usize) -> Result<Stripped, Error> {
    let start = skip_space(character, 0);

    if !starts_with(character, start, "\\chem") {
        return Ok(Stripped {
            body: character.iter().collect(),
            offset: at,
            wrapper: Wrapper::None,
        });
    }

    if starts_with(character, start, "\\chemfig") {
        let (inside, next) = take_group(character, start + 8, at, "\\chemfig")?;
        finish(character, next, at, "\\chemfig")?;

        return Ok(Stripped {
            body: character[inside.clone()].iter().collect(),
            offset: at + inside.start,
            wrapper: Wrapper::Chemfig,
        });
    }

    if starts_with(character, start, "\\chemname") {
        let (body, after_body) = take_group(character, start + 9, at, "\\chemname")?;
        let (name, next) = take_group(character, after_body, at, "\\chemname")?;
        finish(character, next, at, "\\chemname")?;

        // The contents are often wrapped in \chemfig{...} as well
        let inner = strip(&character[body.clone()], at + body.start)?;

        return Ok(Stripped {
            body: inner.body,
            offset: inner.offset,
            wrapper: Wrapper::Named(character[name].iter().collect()),
        });
    }

    Err(Error::new(
        "読めるコマンドは \\chemfig と \\chemname だけです",
        at + start,
    ))
}


/// Whether word begins at position at in character
fn starts_with(character: &[char], at: usize, word: &str) -> bool {
    let wanted: Vec<char> = word.chars().collect();

    character.len() >= at + wanted.len() && character[at..at + wanted.len()] == wanted[..]
}


fn skip_space(character: &[char], mut at: usize) -> usize {
    while matches!(character.get(at), Some(' ' | '\t' | '\n' | '\r')) {
        at += 1;
    }

    at
}


/// Takes one group in braces. Returns the range of its contents and the position just after
/// the closing brace
fn take_group(
    character: &[char],
    from: usize,
    at: usize,
    name: &str,
) -> Result<(std::ops::Range<usize>, usize), Error> {
    let open = skip_space(character, from);

    if character.get(open) != Some(&'{') {
        return Err(Error::new(format!("{name} の後ろに {{ がありません"), at + open));
    }

    let mut index = open + 1;
    let mut depth = 1;

    while index < character.len() {
        match character[index] {
            '{' => depth += 1,
            '}' => {
                depth -= 1;

                if depth == 0 {
                    return Ok((open + 1..index, index + 1));
                }
            }
            _ => {}
        }

        index += 1;
    }

    Err(Error::new(format!("{name} の {{ が閉じていません"), at + open))
}


/// Checks that nothing extra follows the wrapper
fn finish(character: &[char], from: usize, at: usize, name: &str) -> Result<(), Error> {
    let rest = skip_space(character, from);

    if rest < character.len() {
        return Err(Error::new(format!("{name}{{...}} の後ろは空にしてください"), at + rest));
    }

    Ok(())
}


struct Reader {
    token: Vec<Located>,
    position: usize,
    /// Length of the original string. Used as the error position at the end
    end: usize,
}


impl Reader {
    fn look(&self) -> Option<Token> {
        self.token.get(self.position).map(|found| found.token.clone())
    }

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

    /// Reads one atom and all the bonds, branches, and rings that follow from it
    fn molecule(&mut self) -> Result<Node, Error> {
        let mut node = self.member()?;

        loop {
            match self.look() {
                Some(Token::Bond(kind)) => {
                    let bond = self.bond(kind)?;
                    let child = self.molecule()?;
                    node.branch.push((bond, child));
                }
                Some(Token::Open) => {
                    let found = self.detour()?;
                    node.branch.push(found);
                }
                _ => break,
            }
        }

        Ok(node)
    }

    /// One atom with its branches and ring. Chain bonds are not read.
    /// Each vertex inside a ring is read this way
    fn member(&mut self) -> Result<Node, Error> {
        let mut node = self.atom();

        loop {
            match self.look() {
                Some(Token::Hook) => {
                    let found = self.hook()?;
                    node.atom.hook.push(found);
                }
                Some(Token::Open) => {
                    let found = self.detour()?;
                    node.branch.push(found);
                }
                Some(Token::Ring {size, circle}) => {
                    node.ring = Some(self.ring(size, circle)?);

                    break;
                }
                _ => break,
            }
        }

        Ok(node)
    }

    /// A ring closure mark. It is written ?[<name>,<bond>]. Both can be left out
    fn hook(&mut self) -> Result<Hook, Error> {
        let position = self.spot();
        self.position += 1;
        let mut found = Hook {name: DEFAULT_HOOK.to_string(), kind: None, position};

        let Some(Token::Setting(inside)) = self.look() else {
            return Ok(found);
        };
        let at = self.token[self.position].position;
        self.position += 1;
        let field: Vec<&str> = inside.split(',').collect();

        if field.len() > 2 {
            let reason = "環を閉じる印の中は 2 つまでです。<名前>,<結合> の順です";

            return Err(Error::new(reason, at));
        }

        let name = field[0].trim();

        if !name.is_empty() {
            found.name = name.to_string();
        }

        if let Some(text) = field.get(1) {
            let trimmed = text.trim();

            if !trimmed.is_empty() {
                found.kind = Some(read_kind(trimmed, at + field[0].chars().count() + 2)?);
            }
        }

        Ok(found)
    }

    /// One atom. If no label is written, it becomes a node with no mark
    fn atom(&mut self) -> Node {
        let spot = self.spot();

        if let Some(Token::Atom(label)) = self.look() {
            let position = self.token[self.position].position;
            self.position += 1;

            return Node {
                atom: Atom {source: label, hook: Vec::new(), position},
                branch: Vec::new(),
                ring: None,
            };
        }

        Node {
            atom: Atom {source: String::new(), hook: Vec::new(), position: spot},
            branch: Vec::new(),
            ring: None,
        }
    }

    /// Reads a bond mark, and applies the contents of any square brackets that follow
    fn bond(&mut self, kind: Kind) -> Result<Bond, Error> {
        let position = self.token[self.position].position;
        self.position += 1;
        let mut bond = Bond::new(kind, position);

        if let Some(Token::Setting(inside)) = self.look() {
            let at = self.token[self.position].position;
            self.position += 1;
            apply(&mut bond, &inside, at)?;
        }

        Ok(bond)
    }

    /// Reads one branch. A branch always starts with a bond
    fn detour(&mut self) -> Result<(Bond, Node), Error> {
        let open = self.spot();
        self.position += 1;

        let Some(Token::Bond(kind)) = self.look() else {
            return Err(Error::new("枝は結合から始めます。( の次に - などを書きます", open));
        };

        let bond = self.bond(kind)?;
        let child = self.molecule()?;

        match self.look() {
            Some(Token::Close) => {
                self.position += 1;

                Ok((bond, child))
            }
            _ => Err(Error::new("( が閉じていません", open)),
        }
    }

    /// Reads a ring. There are size sides, and the atoms are one fewer than size
    fn ring(&mut self, size: usize, circle: bool) -> Result<Ring, Error> {
        let position = self.spot();
        self.position += 1;

        if self.look() != Some(Token::Open) {
            return Err(Error::new("環は ( で始めます。6 員環なら *6(...) です", position));
        }

        self.position += 1;
        let mut bond = Vec::with_capacity(size);
        let mut member = Vec::with_capacity(size - 1);

        for order in 0..size {
            let Some(Token::Bond(kind)) = self.look() else {
                let reason = format!("{size} 員環には結合が {size} 本要ります");

                return Err(Error::new(reason, self.spot()));
            };
            let one = self.bond(kind)?;

            if one.is_placed() {
                let reason = "環の辺には角度も長さも書けません。向きは環の大きさが決めます";

                return Err(Error::new(reason, one.position));
            }

            bond.push(one);

            if order + 1 < size {
                member.push(self.member()?);
            }
        }

        match self.look() {
            Some(Token::Close) => {
                self.position += 1;

                Ok(Ring {size, circle, bond, member, position})
            }
            Some(_) => {
                let reason = format!("{size} 員環の中身が多すぎます");

                Err(Error::new(reason, self.spot()))
            }
            None => Err(Error::new("環の ( が閉じていません", position)),
        }
    }
}


/// Applies the contents of square brackets to a bond.
/// The form is <angle>,<factor>,<from part>,<to part>
fn apply(bond: &mut Bond, inside: &str, at: usize) -> Result<(), Error> {
    let field: Vec<&str> = inside.split(',').collect();

    if field.len() > 4 {
        let reason = "角括弧の中は 4 つまでです。<角度>,<係数>,<出る部分>,<入る部分> の順です";

        return Err(Error::new(reason, at));
    }

    // at is the position of [, so counting starts from the character after it
    let mut offset = at + 1;

    for (order, text) in field.iter().enumerate() {
        let trimmed = text.trim();

        if !trimmed.is_empty() {
            let spot = offset + text.chars().take_while(|found| found.is_whitespace()).count();

            match order {
                0 => bond.angle = read_angle(trimmed, spot)?,
                1 => bond.length = read_length(trimmed, spot)?,
                2 => bond.from = Some(read_part(trimmed, spot)?),
                _ => bond.to = Some(read_part(trimmed, spot)?),
            }
        }

        offset += text.chars().count() + 1;
    }

    Ok(())
}


/// An angle. :45 is absolute, ::45 is the difference from the previous bond,
/// and 0 to 7 are numbers in steps of 45 degrees
fn read_angle(text: &str, at: usize) -> Result<Angle, Error> {
    if let Some(rest) = text.strip_prefix("::") {
        return Ok(Angle::Relative(read_number(rest, at + 2)?));
    }

    if let Some(rest) = text.strip_prefix(':') {
        return Ok(Angle::Absolute(read_number(rest, at + 1)?));
    }

    let step = read_number(text, at)?;

    if step.fract() != 0.0 || !(0.0..=7.0).contains(&step) {
        let reason = "角度の番号は 0 から 7 です。度で書くなら :45 のように : を付けます";

        return Err(Error::new(reason, at));
    }

    Ok(Angle::Absolute(step * 45.0))
}


/// Factor applied to the bond length
fn read_length(text: &str, at: usize) -> Result<f64, Error> {
    let value = read_number(text, at)?;

    if value <= 0.0 {
        return Err(Error::new("結合長の係数は 0 より大きい数です", at));
    }

    Ok(value)
}


/// Kind of bond drawn when a ring is closed.
/// It is written as the bond mark itself, or as a number from 1 to 3
fn read_kind(text: &str, at: usize) -> Result<Kind, Error> {
    match text {
        "-" | "1" => Ok(Kind::Single),
        "=" | "2" => Ok(Kind::Double),
        "~" | "3" => Ok(Kind::Triple),
        ">" => Ok(Kind::Wedge),
        "<" => Ok(Kind::WedgeBack),
        ">:" => Ok(Kind::Hash),
        "<:" => Ok(Kind::HashBack),
        ">|" => Ok(Kind::Hollow),
        "<|" => Ok(Kind::HollowBack),
        _ => Err(Error::new(format!("結合の種別として読めません: {text}"), at)),
    }
}


/// Number of the part where the bond leaves or arrives. It starts at 1
fn read_part(text: &str, at: usize) -> Result<usize, Error> {
    match text.parse::<usize>() {
        Ok(value) if value >= 1 => Ok(value),
        _ => Err(Error::new("部分の番号は 1 以上の整数です", at)),
    }
}


fn read_number(text: &str, at: usize) -> Result<f64, Error> {
    match text.trim().parse::<f64>() {
        Ok(value) if value.is_finite() => Ok(value),
        _ => Err(Error::new(format!("数として読めません: {text}"), at)),
    }
}


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

    #[test]
    fn a_straight_chain_hangs_to_the_right() {
        let node = parse("H-O-H").unwrap();
        assert_eq!(node.atom.source, "H");
        assert_eq!(node.branch.len(), 1);
        let (_, oxygen) = &node.branch[0];
        assert_eq!(oxygen.atom.source, "O");
        assert_eq!(oxygen.branch.len(), 1);
        assert_eq!(oxygen.branch[0].1.atom.source, "H");
        assert_eq!(count(&node), 3);
    }

    #[test]
    fn a_branch_hangs_on_the_atom_it_follows() {
        let node = parse("A-B(-X)-C").unwrap();
        let (_, middle) = &node.branch[0];
        assert_eq!(middle.atom.source, "B");
        assert_eq!(middle.branch.len(), 2);
        assert_eq!(middle.branch[0].1.atom.source, "X");
        assert_eq!(middle.branch[1].1.atom.source, "C");
    }

    #[test]
    fn a_missing_label_becomes_a_knot_with_no_mark() {
        let node = parse("-[:30]-[:-30]").unwrap();
        assert_eq!(node.atom.source, "");
        assert_eq!(count(&node), 3);
    }

    #[test]
    fn reads_the_three_ways_of_writing_an_angle() {
        let node = parse("A-[:30]B-[::60]C-[2]D").unwrap();
        let first = &node.branch[0].0;
        assert_eq!(first.angle, Angle::Absolute(30.0));
        let second = &node.branch[0].1.branch[0].0;
        assert_eq!(second.angle, Angle::Relative(60.0));
        let third = &node.branch[0].1.branch[0].1.branch[0].0;
        assert_eq!(third.angle, Angle::Absolute(90.0));
    }

    #[test]
    fn reads_the_other_fields() {
        let node = parse("A-[:30,1.5,2,3]B").unwrap();
        let bond = &node.branch[0].0;
        assert_eq!(bond.length, 1.5);
        assert_eq!(bond.from, Some(2));
        assert_eq!(bond.to, Some(3));
    }

    #[test]
    fn fields_can_be_left_out() {
        let node = parse("A-[,2]B").unwrap();
        let bond = &node.branch[0].0;
        assert_eq!(bond.angle, Angle::Default);
        assert_eq!(bond.length, 2.0);
        assert_eq!(bond.from, None);
    }

    #[test]
    fn keeps_the_kind_of_each_bond() {
        assert_eq!(parse("O=C=O").unwrap().branch[0].0.kind, Kind::Double);
        assert_eq!(parse("N~N").unwrap().branch[0].0.kind, Kind::Triple);
        assert_eq!(parse("C>H").unwrap().branch[0].0.kind, Kind::Wedge);
        assert_eq!(parse("C<:H").unwrap().branch[0].0.kind, Kind::HashBack);
    }

    #[test]
    fn subscripts_stay_with_their_atom() {
        let node = parse("H_2SO_4").unwrap();
        assert_eq!(node.atom.source, "H_2SO_4");
        assert_eq!(count(&node), 1);
    }

    #[test]
    fn a_ring_has_as_many_bonds_as_it_has_vertices() {
        let node = parse("*6(------)").unwrap();
        let ring = node.ring.as_ref().unwrap();
        assert_eq!(ring.size, 6);
        assert!(!ring.circle);
        assert_eq!(ring.bond.len(), 6);
        assert_eq!(ring.member.len(), 5);
        assert_eq!(count(&node), 6);
    }

    #[test]
    fn an_aromatic_ring_asks_for_a_circle() {
        assert!(parse("**6(------)").unwrap().ring.as_ref().unwrap().circle);
    }

    #[test]
    fn a_ring_keeps_the_kind_of_each_side() {
        let node = parse("*6(-=-=-=)").unwrap();
        let ring = node.ring.as_ref().unwrap();
        assert_eq!(ring.bond[0].kind, Kind::Single);
        assert_eq!(ring.bond[1].kind, Kind::Double);
        assert_eq!(ring.bond[5].kind, Kind::Double);
    }

    #[test]
    fn a_ring_can_carry_labels_and_branches() {
        let node = parse("*6(-N=-(-OH)-=-)").unwrap();
        let ring = node.ring.as_ref().unwrap();
        assert_eq!(ring.member[0].atom.source, "N");
        assert_eq!(ring.member[2].branch.len(), 1);
        assert_eq!(ring.member[2].branch[0].1.atom.source, "OH");
    }

    #[test]
    fn a_ring_can_hang_on_an_atom() {
        let node = parse("HO-*6(------)").unwrap();
        assert_eq!(node.atom.source, "HO");
        assert!(node.ring.is_none());
        assert!(node.branch[0].1.ring.is_some());
        assert_eq!(count(&node), 7);
    }

    #[test]
    fn a_ring_inside_a_ring_shares_its_vertex() {
        let node = parse("*6(-----*5(-----)-)").unwrap();
        let outer = node.ring.as_ref().unwrap();
        assert!(outer.member[4].ring.is_some());
        assert_eq!(count(&node), 10);
    }

    #[test]
    fn a_hook_marks_the_atom_it_follows() {
        let node = parse("A?-B?").unwrap();
        assert_eq!(node.atom.hook.len(), 1);
        assert_eq!(node.atom.hook[0].name, "a");
        assert_eq!(node.atom.hook[0].kind, None);
        assert_eq!(node.branch[0].1.atom.hook.len(), 1);
    }

    #[test]
    fn a_hook_can_carry_a_name_and_a_bond() {
        let node = parse("A?[b,=]-B?[b]").unwrap();
        assert_eq!(node.atom.hook[0].name, "b");
        assert_eq!(node.atom.hook[0].kind, Some(Kind::Double));
        let far = &node.branch[0].1.atom.hook[0];
        assert_eq!(far.name, "b");
        assert_eq!(far.kind, None);
    }

    #[test]
    fn a_hook_takes_a_bond_written_as_a_number() {
        assert_eq!(parse("A?[a,1]").unwrap().atom.hook[0].kind, Some(Kind::Single));
        assert_eq!(parse("A?[a,2]").unwrap().atom.hook[0].kind, Some(Kind::Double));
        assert_eq!(parse("A?[a,3]").unwrap().atom.hook[0].kind, Some(Kind::Triple));
    }

    #[test]
    fn a_hook_sits_on_a_knot_with_no_mark_too() {
        let node = parse("?[a]-[:90]-[:180]?[a]").unwrap();
        assert_eq!(node.atom.source, "");
        assert_eq!(node.atom.hook.len(), 1);
    }

    #[test]
    fn a_hook_that_is_written_wrong_is_reported() {
        assert!(parse("A?[a,b,c]").is_err());
        assert!(parse("A?[a,x]").is_err());
    }

    #[test]
    fn the_chemfig_wrapper_comes_off() {
        assert_eq!(parse("\\chemfig{H-O-H}").unwrap(), parse("H-O-H").unwrap());
        assert_eq!(parse_wrapped("\\chemfig{H-O-H}").unwrap().1, Wrapper::Chemfig);
        assert_eq!(parse_wrapped("H-O-H").unwrap().1, Wrapper::None);
        // Spaces before and after are dropped
        assert_eq!(parse("  \\chemfig{H-O-H}  ").unwrap(), parse("H-O-H").unwrap());
    }

    #[test]
    fn the_chemname_wrapper_gives_back_the_name() {
        let (node, wrapper) = parse_wrapped("\\chemname{\\chemfig{H-O-H}}{水}").unwrap();
        assert_eq!(node, parse("H-O-H").unwrap());
        assert_eq!(wrapper, Wrapper::Named("水".to_string()));

        // It can be read even without \chemfig inside
        let (node, wrapper) = parse_wrapped("\\chemname{H-O-H}{水}").unwrap();
        assert_eq!(node, parse("H-O-H").unwrap());
        assert_eq!(wrapper, Wrapper::Named("水".to_string()));
    }

    #[test]
    fn a_wrapper_keeps_the_place_of_a_mistake() {
        // \chemfig{ is 9 characters. The 4th character inside is the 13th in the original
        let found = parse("\\chemfig{A-[45]B}").unwrap_err();
        assert_eq!(found.position, 12);
        let plain = parse("A-[45]B").unwrap_err();
        assert_eq!(found.message, plain.message);
    }

    #[test]
    fn a_wrapper_written_wrong_is_reported() {
        assert!(parse("\\chemfig{A}B").is_err());
        assert!(parse("\\chemfig A").is_err());
        assert!(parse("\\chemfig{A").is_err());
        assert!(parse("\\chemname{A}").is_err());
        assert!(parse("\\foo{A}").is_err());
        assert!(parse("\\chemistry{A}").is_err());
    }

    #[test]
    fn a_command_in_the_middle_is_refused() {
        let found = parse("A\\foo-B").unwrap_err();
        assert!(found.message.contains("chemfig"));
    }

    #[test]
    fn says_where_it_went_wrong() {
        assert!(parse("A-[45]B").is_err());
        assert!(parse("A-[:x]B").is_err());
        assert!(parse("A-[,0]B").is_err());
        assert!(parse("A-[,,0]B").is_err());
        assert!(parse("A-[1,1,1,1,1]B").is_err());
        assert!(parse("A(B)").is_err());
        assert!(parse("A(-B").is_err());
        assert!(parse("A)B").is_err());
    }

    #[test]
    fn a_ring_that_does_not_add_up_is_reported() {
        assert!(parse("*6(-----)").is_err());
        assert!(parse("*6(-------)").is_err());
        assert!(parse("*6------").is_err());
        assert!(parse("*6(------").is_err());
    }

    #[test]
    fn a_ring_side_cannot_be_aimed() {
        let found = parse("*6(-[:30]-----)").unwrap_err();
        assert!(found.message.contains("角度"));
        assert!(parse("*6(-[,2]-----)").is_err());
        // Part numbers can be written
        assert!(parse("*6(-[,,1]-----)").is_ok());
    }

    #[test]
    fn the_position_points_at_the_mistake() {
        let found = parse("A-[45]B").unwrap_err();
        assert_eq!(found.position, 3);
    }
}