lambda_cat/

lexer.rs

//! Tokenizer for the lambda calculus surface syntax.
//!
//! Source must be ASCII; any non-ASCII byte is reported as [`Error::UnexpectedChar`].
//! Lexing is purely functional: the entry point [`lex`] threads an immutable
//! accumulator through a recursive scan, producing a `Vec<Token>` on success.
//!
//! [`Error::UnexpectedChar`]: crate::error::Error::UnexpectedChar

use crate::error::Error;
use crate::syntax::{Position, VarName};

/// A token paired with its source position.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Token {
    kind: TokenKind,
    at: Position,
}

impl Token {
    /// The token's syntactic kind.
    #[must_use]
    pub fn kind(&self) -> &TokenKind {
        &self.kind
    }

    /// Byte offset where the token begins in the source.
    #[must_use]
    pub fn at(&self) -> Position {
        self.at
    }

    fn new(kind: TokenKind, at: Position) -> Self {
        Self { kind, at }
    }
}

/// The syntactic kind of a token.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum TokenKind {
    /// An identifier that is not a reserved keyword.
    Ident(VarName),
    /// The `let` keyword.
    KwLet,
    /// The `in` keyword.
    KwIn,
    /// The `fix` keyword.
    KwFix,
    /// A lambda head, written `\`.
    Lambda,
    /// A dot `.` separating a lambda head from its body.
    Dot,
    /// An equals sign `=` in a let-binding.
    Equals,
    /// An opening parenthesis `(`.
    LParen,
    /// A closing parenthesis `)`.
    RParen,
}

impl std::fmt::Display for TokenKind {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::Ident(name) => write!(f, "identifier {:?}", name.as_str()),
            Self::KwLet => f.write_str("keyword `let`"),
            Self::KwIn => f.write_str("keyword `in`"),
            Self::KwFix => f.write_str("keyword `fix`"),
            Self::Lambda => f.write_str("`\\`"),
            Self::Dot => f.write_str("`.`"),
            Self::Equals => f.write_str("`=`"),
            Self::LParen => f.write_str("`(`"),
            Self::RParen => f.write_str("`)`"),
        }
    }
}

/// One step of the lexer: either a byte to dispatch on or end-of-input.
enum Step {
    End,
    Byte(u8),
}

fn peek(src: &[u8], pos: usize) -> Step {
    src.get(pos).copied().map_or(Step::End, Step::Byte)
}

/// Lex the entire source string into a vector of tokens.
///
/// # Errors
///
/// Returns [`Error::UnexpectedChar`] on any non-ASCII byte or any character
/// outside the grammar.
///
/// # Examples
///
/// ```
/// # fn main() -> Result<(), lambda_cat::error::Error> {
/// use lambda_cat::lexer::{lex, TokenKind};
///
/// let tokens = lex("\\x. x")?;
/// assert_eq!(tokens.len(), 4);
/// # Ok(())
/// # }
/// ```
pub fn lex(src: &str) -> Result<Vec<Token>, Error> {
    step(src.as_bytes(), 0, Vec::new())
}

fn step(src: &[u8], pos: usize, acc: Vec<Token>) -> Result<Vec<Token>, Error> {
    match peek(src, pos) {
        Step::End => Ok(acc),
        Step::Byte(b) => take_token(src, pos, acc, b),
    }
}

fn take_token(src: &[u8], pos: usize, acc: Vec<Token>, b: u8) -> Result<Vec<Token>, Error> {
    match b {
        b' ' | b'\t' | b'\n' | b'\r' => step(src, pos + 1, acc),
        b'\\' => emit(src, pos + 1, acc, Token::new(TokenKind::Lambda, pos.into())),
        b'.' => emit(src, pos + 1, acc, Token::new(TokenKind::Dot, pos.into())),
        b'=' => emit(src, pos + 1, acc, Token::new(TokenKind::Equals, pos.into())),
        b'(' => emit(src, pos + 1, acc, Token::new(TokenKind::LParen, pos.into())),
        b')' => emit(src, pos + 1, acc, Token::new(TokenKind::RParen, pos.into())),
        other if is_ident_start(other) => read_ident(src, pos, acc),
        other => Err(Error::UnexpectedChar {
            at: pos.into(),
            ch: char::from(other),
        }),
    }
}

fn emit(src: &[u8], next_pos: usize, acc: Vec<Token>, token: Token) -> Result<Vec<Token>, Error> {
    step(src, next_pos, push(acc, token))
}

fn push(acc: Vec<Token>, token: Token) -> Vec<Token> {
    acc.into_iter().chain(std::iter::once(token)).collect()
}

fn read_ident(src: &[u8], start: usize, acc: Vec<Token>) -> Result<Vec<Token>, Error> {
    let end = scan_ident(src, start);
    let slice = src.get(start..end).unwrap_or(&[]);
    let token = classify_ident(slice, start);
    step(src, end, push(acc, token))
}

fn scan_ident(src: &[u8], pos: usize) -> usize {
    src.get(pos)
        .copied()
        .filter(|b| is_ident_continue(*b))
        .map_or(pos, |_| scan_ident(src, pos + 1))
}

fn classify_ident(slice: &[u8], start: usize) -> Token {
    let at = Position::from(start);
    match slice {
        b"let" => Token::new(TokenKind::KwLet, at),
        b"in" => Token::new(TokenKind::KwIn, at),
        b"fix" => Token::new(TokenKind::KwFix, at),
        bytes => Token::new(
            TokenKind::Ident(VarName::from(
                std::str::from_utf8(bytes).unwrap_or_default(),
            )),
            at,
        ),
    }
}

fn is_ident_start(b: u8) -> bool {
    b.is_ascii_alphabetic() || b == b'_'
}

fn is_ident_continue(b: u8) -> bool {
    b.is_ascii_alphanumeric() || b == b'_'
}

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

    #[test]
    fn lex_identity_lambda() -> Result<(), Error> {
        let tokens = lex("\\x. x")?;
        let kinds: Vec<TokenKind> = tokens.iter().map(|t| t.kind().clone()).collect();
        let expected = vec![
            TokenKind::Lambda,
            TokenKind::Ident(VarName::from("x")),
            TokenKind::Dot,
            TokenKind::Ident(VarName::from("x")),
        ];
        (kinds == expected)
            .then_some(())
            .ok_or(Error::UnexpectedEnd {
                expected: "identity tokenization",
            })
    }

    #[test]
    fn lex_let_keyword() -> Result<(), Error> {
        let tokens = lex("let x = y in x")?;
        let kinds: Vec<TokenKind> = tokens.iter().map(|t| t.kind().clone()).collect();
        let expected = vec![
            TokenKind::KwLet,
            TokenKind::Ident(VarName::from("x")),
            TokenKind::Equals,
            TokenKind::Ident(VarName::from("y")),
            TokenKind::KwIn,
            TokenKind::Ident(VarName::from("x")),
        ];
        (kinds == expected)
            .then_some(())
            .ok_or(Error::UnexpectedEnd {
                expected: "let tokenization",
            })
    }

    #[test]
    fn lex_rejects_non_ascii() -> Result<(), Error> {
        let result = lex("λx. x");
        match result {
            Err(Error::UnexpectedChar { .. }) => Ok(()),
            Err(other) => Err(other),
            Ok(_) => Err(Error::UnexpectedEnd {
                expected: "rejection of non-ASCII source",
            }),
        }
    }
}