ssexp/

lib.rs

#![deny(missing_docs)]
/*!
See [README.md](https://crates.io/crates/ssexp)
*/

use derive_destructure::destructure;

use std::rc::Rc;

/// Represents the s-expressions as tokens.
#[derive(Clone, Debug)]
pub enum Token {
    /// A symbol token represented by its name.
    Symbol(String),
    /// A list token containing other tokens.
    List(Vec<Token>),
}

use Token::*;

impl Token {
    /// If the token is a `Symbol`, returns an `Option`, containing the symbol name.
    /// Else returns `None`.
    pub fn symbol(self) -> Option<String> {
        match self {
            Symbol(string) => Some(string),
            List(_) => None,
        }
    }

    /// Same as `fn symbol`, but returns a ref.
    pub fn symbol_ref(&self) -> Option<&String> {
        match self {
            Symbol(string) => Some(string),
            List(_) => None,
        }
    }

    /// If the token is a `List`, returns an `Option`, containing the elements.
    /// Else returns `None`.
    pub fn list(self) -> Option<Vec<Token>> {
        match self {
            Symbol(_) => None,
            List(tokens) => Some(tokens),
        }
    }

    /// Same as `fn list`, but returns a ref.
    pub fn list_ref(&self) -> Option<&Vec<Token>> {
        match self {
            Symbol(_) => None,
            List(tokens) => Some(tokens),
        }
    }
}

/// Useful for managing opening and closing subcontexts like brackets.
#[derive(Copy, Clone, Debug)]
pub enum ParsingState {
    /// Doesn't do anything, marks success.
    Fine(bool),
    /// Closes a subcontext.
    Finished,
    /// Closes a subcontext while carrying the closing character.
    Delegate(char),
}

use ParsingState::*;

mod implement_display {
    use std::fmt::{Display, Formatter, Result};

    use crate::Token;

    impl Display for Token {
        fn fmt(&self, f: &mut Formatter) -> Result {
            match self {
                Token::Symbol(string) => write!(f, "'{}'", string),
                Token::List(vec) => {
                    let mut first = true;
                    write!(f, "(").expect("Unexpected end of file");
                    for tok in vec.iter() {
                        if !first {
                            write!(f, " ").expect("Unexpected end of file");
                        } else {
                            first = false;
                        }
                        let result = write!(f, "{}", tok);
                        if result.is_err() {
                            return result;
                        }
                    }
                    write!(f, ")")
                }
            }
        }
    }
}

use std::collections::HashMap;

/// A map for storing the macro characters and their behaviours.
/// Every character may be set as macro character.
pub struct MacroMap<T>(HashMap<char, Rc<dyn Parser<T>>>);

impl<T: Iterator<Item = char>> MacroMap<T> {
    /// Creates a new `MacroMap`, which is used to save macro characters
    pub fn new() -> Self {
        MacroMap(HashMap::new())
    }

    /// Adds a new user defined macro character `char`.
    /// Takes an `Option` of the new parser.
    pub fn set(
        &mut self,
        char: char,
        value: Option<impl Parser<T> + 'static>,
    ) -> Option<Rc<dyn Parser<T>>> {
        if let Some(value) = value {
            self.0.insert(char, Rc::new(value))
        } else {
            self.0.remove(&char)
        }
    }

    /// Adds `char` as a macro character with the user defined parser `value`
    pub fn with(mut self, char: char, value: impl Parser<T> + 'static) -> Self {
        self.0.insert(char, Rc::new(value));
        self
    }

    /// Adds whitespaces as macro characters for splitting there into tokens.
    pub fn with_separating_whitespaces(self) -> Self {
        self.with(' ', EmptyParser(Fine(false)))
            .with('\n', EmptyParser(Fine(false)))
            .with('\t', EmptyParser(Fine(false)))
    }
    /// Makes `start_char` the left delimiter and `end_char` the right delimiter of a list.
    pub fn with_lists(self, start_char: char, end_char: char) -> Self {
        self.with(
            start_char,
            ListWrapper {
                prefix: None,
                parser: DelimitedListParser(end_char),
            },
        )
        .with(end_char, PanicParser)
    }
    /// Ignores macro characters in some region and parses a symbol
    pub fn with_macro_characters_ignored(self, delimiter: char) -> Self {
        self.with(delimiter, DelimitedSymbolParser)
    }
    /// Adds the ability for parsing strings, using char `string_delimiter` for delimiting strings.
    /// A string will be parsed as list, whose first element is a symbol `prefix` and whose second element is the string itself as symbol.
    pub fn with_strings(
        self,
        prefix: String,
        delimiter: char,
        replacements: Vec<(String, String)>,
    ) -> Self {
        self.with(
            delimiter,
            ListWrapper {
                prefix: Some(prefix),
                parser: SymbolReplacer {
                    replacements,
                    parser: DelimitedSymbolParser,
                },
            },
        )
    }
    /// Adds `comment_char` as macro character for single line comments.
    pub fn with_comments(self, comment_char: char) -> Self {
        self.with(comment_char, CommentParser)
    }

    /// Adds `infix_char` as infix operator.
    pub fn with_infix(self, infix_char: char, kind: InfixKind, right: bool) -> Self {
        self.with(infix_char, InfixParser(kind, right))
    }

    /// Creates a `MacroMap` from a `HashMap`
    pub fn from_hash_map(map: HashMap<char, Rc<dyn Parser<T>>>) -> Self {
        MacroMap(map)
    }
    /// Adds a new user defined macro character `char`.
    /// Takes an `Option` of the new parser already converted to the inner type.
    pub fn insert(
        &mut self,
        char: char,
        value: Option<Rc<dyn Parser<T>>>,
    ) -> Option<Rc<dyn Parser<T>>> {
        if let Some(value) = value {
            self.0.insert(char, value)
        } else {
            self.0.remove(&char)
        }
    }
}

/// Used in parsing process for getting chars and calling the parsers.
pub struct ParsingContext<T: Iterator<Item = char>> {
    char: Option<char>,
    chars: T,
    maps: Vec<MacroMap<T>>,
}

/// A handle for handling the next macro character.
#[derive(destructure)]
pub struct MacroHandle<'a, T: Iterator<Item = char>>
where
    ParsingContext<T>: 'a,
{
    char: char,
    context: &'a mut ParsingContext<T>,
    parser: Option<Rc<dyn Parser<T>>>,
}

use std::result::Result;

impl<'a, T: Iterator<Item = char>> MacroHandle<'a, T> {
    /// Tries to call the macro character. If none is defined, it some character.
    pub fn call(self, result: &mut Vec<Token>) -> Result<ParsingState, char> {
        let (char, context, parser) = self.destructure();
        if let Some(parser) = parser {
            Ok(parser.parse(Some(char), result, context))
        } else {
            Err(char)
        }
    }
}

impl<'a, T: Iterator<Item = char>> Drop for MacroHandle<'a, T> {
    /// Discards this handle. When calling the next time, the same character will be used for dispatch.
    fn drop(&mut self) {
        self.context.char = Some(self.char);
    }
}

impl<T: Iterator<Item = char>> ParsingContext<T> {
    /// Parses the next symbol and inserts it into a specified token list.
    /// Then a handle for the next macro call is returned.
    pub fn parse(&mut self, tokens: &mut Vec<Token>) -> Option<MacroHandle<T>> {
        let mut symbol = String::new();
        let (char, parser) = loop {
            let char = if let Some(old_char) = self.char {
                self.char = None;
                old_char
            } else {
                if let Some(next) = self.chars.next() {
                    next
                } else {
                    if !symbol.is_empty() {
                        tokens.push(Symbol(symbol));
                    }
                    return None;
                }
            };
            let parser = if let Some(map) = self.maps.last() {
                map.0.get(&char).cloned()
            } else {
                None
            };
            if parser.is_none() {
                symbol = format!("{}{}", symbol, char);
            } else {
                break (char, parser);
            }
        };

        if !symbol.is_empty() {
            tokens.push(Symbol(symbol));
        }
        Some(MacroHandle {
            char,
            context: self,
            parser,
        })
    }

    /// Binds a new parser to a character and returns some previous, if there was one defined, else returns `None`
    pub fn set(
        &mut self,
        char: char,
        value: Option<impl Parser<T> + 'static>,
    ) -> Option<Rc<dyn Parser<T>>> {
        if let Some(map) = self.maps.last_mut() {
            map.set(char, value)
        } else {
            None
        }
    }

    /// Binds a new parser to a character and returns some previous, if there was one defined, else returns `None`
    pub fn insert(
        &mut self,
        char: char,
        value: Option<Rc<dyn Parser<T>>>,
    ) -> Option<Rc<dyn Parser<T>>> {
        if let Some(map) = self.maps.last_mut() {
            map.insert(char, value)
        } else {
            None
        }
    }

    /// Replaces the current macro map with a new one.
    pub fn push(&mut self, map: MacroMap<T>) {
        self.maps.push(map);
    }

    /// Removes the current macro map and uses the most recent one.
    pub fn pop(&mut self) -> Option<MacroMap<T>> {
        self.maps.pop()
    }
}

/// The function for starting the parsing process. It takes some iterator of characters, an initial parser, and a macro map.
pub fn parse<T: IntoIterator<Item = char>>(
    stream: T,
    parser: impl Parser<T::IntoIter>,
    map: MacroMap<T::IntoIter>,
) -> Vec<Token> {
    let mut context = ParsingContext {
        char: None,
        chars: stream.into_iter(),
        maps: vec![map],
    };
    let mut tokens = Vec::new();
    parser.parse(None, &mut tokens, &mut context);
    tokens
}

/// A trait for task specific parsers.
pub trait Parser<T: Iterator<Item = char>> {
    /// A trait to parse code in a specific way.
    fn parse(
        &self,
        char: Option<char>,
        result: &mut Vec<Token>,
        context: &mut ParsingContext<T>,
    ) -> ParsingState;
}

use parsers::*;

/// Useful default parsers.
pub mod parsers {
    use super::*;
    /// A parser to mark some char as macro character without doing anything.
    pub struct EmptyParser(pub ParsingState);
    impl<T: Iterator<Item = char>> Parser<T> for EmptyParser {
        fn parse(
            &self,
            _char: Option<char>,
            _result: &mut Vec<Token>,
            _context: &mut ParsingContext<T>,
        ) -> ParsingState {
            self.0
        }
    }

    /// A parser, that just panics. Instead of using this, it's preferable to use `DelegateParser`
    pub struct PanicParser;
    impl<T: Iterator<Item = char>> Parser<T> for PanicParser {
        fn parse(
            &self,
            char: Option<char>,
            _result: &mut Vec<Token>,
            _context: &mut ParsingContext<T>,
        ) -> ParsingState {
            panic!("Invalid macro character {:?}", char)
        }
    }

    /// A parser, that delegates the handling of some macro character to the parser.
    pub struct DelegateParser;
    impl<T: Iterator<Item = char>> Parser<T> for DelegateParser {
        fn parse(
            &self,
            char: Option<char>,
            _result: &mut Vec<Token>,
            _context: &mut ParsingContext<T>,
        ) -> ParsingState {
            Delegate(char.expect("Delegate as main parser not possible"))
        }
    }

    /// Parses a symbol delimited by the starting char
    pub struct DelimitedSymbolParser;
    impl<T: Iterator<Item = char>> Parser<T> for DelimitedSymbolParser {
        fn parse(
            &self,
            char: Option<char>,
            result: &mut Vec<Token>,
            context: &mut ParsingContext<T>,
        ) -> ParsingState {
            let char = char.expect("Delimited Symbol parsers are not allowed as single");
            context.push(MacroMap::new().with(char, DelegateParser));
            let state = loop {
                if let Some(handle) = context.parse(result) {
                    if let Delegate(c) = handle.call(&mut Vec::new()).unwrap() {
                        if c == char {
                            break Fine(true);
                        }
                    }
                } else {
                    panic!("End of file inside symbol");
                }
            };
            context.pop();
            return state;
        }
    }

    /// Parses a single line comment delimited by `'\n'`
    pub struct CommentParser;
    impl<T: Iterator<Item = char>> Parser<T> for CommentParser {
        fn parse(
            &self,
            _char: Option<char>,
            _result: &mut Vec<Token>,
            context: &mut ParsingContext<T>,
        ) -> ParsingState {
            context.push(MacroMap::new().with('\n', DelegateParser));
            let state = loop {
                if let Some(handle) = context.parse(&mut Vec::new()) {
                    if let Delegate('\n') = handle.call(&mut Vec::new()).unwrap() {
                        break Fine(false);
                    }
                } else {
                    break Finished;
                }
            };

            context.pop();
            return state;
        }
    }

    /// Wraps the parsing result into a new list.
    pub struct ListWrapper<P> {
        /// An optinal prefix for the created list.
        pub prefix: Option<String>,
        /// The parser of the list.
        pub parser: P,
    }
    impl<T: Iterator<Item = char>, P: Parser<T>> Parser<T> for ListWrapper<P> {
        fn parse(
            &self,
            char: Option<char>,
            result: &mut Vec<Token>,
            context: &mut ParsingContext<T>,
        ) -> ParsingState {
            let mut contents = Vec::new();
            let Self { prefix, parser } = self;
            contents.extend(prefix.into_iter().map(|name| Token::Symbol(name.clone())));
            let state = parser.parse(char, &mut contents, context);
            result.push(List(contents));
            state
        }
    }

    /// Replaces substrings in symbol.
    pub struct SymbolReplacer<P> {
        /// An optinal prefix for the created list.
        pub replacements: Vec<(String, String)>,
        /// The parser of the symbol.
        pub parser: P,
    }

    impl<T: Iterator<Item = char>, P: Parser<T>> Parser<T> for SymbolReplacer<P> {
        fn parse(
            &self,
            char: Option<char>,
            result: &mut Vec<Token>,
            context: &mut ParsingContext<T>,
        ) -> ParsingState {
            let Self {
                replacements,
                parser,
            } = self;
            let state = parser.parse(char, result, context);
            if let Some(Symbol(name)) = result.last_mut() {
                for (from, to) in replacements {
                    *name = name.replace(&from[..], &to[..]);
                }
            }
            state
        }
    }

    /// Parses a list and appends it to the current list `result`
    pub struct DelimitedListParser(pub char);
    impl<T: Iterator<Item = char>> Parser<T> for DelimitedListParser {
        fn parse(
            &self,
            char: Option<char>,
            result: &mut Vec<Token>,
            context: &mut ParsingContext<T>,
        ) -> ParsingState {
            let reset = context.set(self.0, Some(DelegateParser));
            let state = loop {
                if let Some(handle) = context.parse(result) {
                    let state = handle.call(result).unwrap();
                    match state {
                        Fine(_) => (),
                        Finished => {
                            if char.is_none() {
                                break Finished;
                            } else {
                                panic!("End of file inside list")
                            }
                        }
                        Delegate(char) => {
                            if char == self.0 {
                                break Fine(true);
                            } else {
                                panic!("Unexpected delegate")
                            }
                        }
                    }
                } else {
                    if char.is_none() {
                        break Finished;
                    } else {
                        panic!("End of file inside list")
                    }
                }
            };

            context.insert(self.0, reset);
            state
        }
    }

    /// The kind infix parsers are interpreted as.
    pub enum InfixKind {
        /// Create a two element list.
        List,
        /// Create a list prefixed with some symbol.
        Prefix(String),
        /// Append the second element to a list, which is the first argument.
        Append,
    }

    /// Parses a sublist as infix operation, optionally using an infix operator.
    pub struct InfixParser(pub InfixKind, pub bool);
    impl<T: Iterator<Item = char>> Parser<T> for InfixParser {
        fn parse(
            &self,
            _char: Option<char>,
            result: &mut Vec<Token>,
            context: &mut ParsingContext<T>,
        ) -> ParsingState {
            let last = result.pop().expect("Infix operator cannot stand alone");
            let mut new_list = if let (InfixKind::Append, false) = (&self.0, self.1) {
                last.list().expect(
                    "First argument of left associative infix append is required to be a list",
                )
            } else {
                let mut new_list = Vec::new();
                if let InfixKind::Prefix(op) = &self.0 {
                    new_list.push(Symbol(op.clone()));
                }
                new_list.push(last);
                new_list
            };
            let state = loop {
                let count = new_list.len();
                let handle = context.parse(&mut new_list);
                if count < new_list.len() {
                    break Fine(true);
                }
                if let Some(handle) = handle {
                    let state = handle.call(&mut new_list).unwrap();
                    if let Fine(false) = state {
                        continue;
                    }
                    break state;
                } else {
                    break Finished;
                }
            };

            if self.1 {
                if let Fine(_) = state {
                    let mut next_list = Vec::new();
                    next_list.push(new_list.pop().unwrap());
                    let state = loop {
                        if let Some(handle) = context.parse(&mut next_list) {
                            let state = handle.call(&mut next_list).unwrap();
                            if let Fine(_) = state {
                                continue;
                            }
                            break state;
                        } else {
                            break Finished;
                        }
                    };
                    let mut append = next_list.into_iter();
                    let first = append.next().unwrap();
                    if let (InfixKind::Append, true) = (&self.0, self.1) {
                        new_list.extend(first.list().expect("Last argument of right associative infix append is required to be a list"));
                    } else {
                        new_list.push(first);
                    }
                    result.push(List(new_list));
                    result.extend(append);
                    return state;
                }
            }
            result.push(List(new_list));
            return state;
        }
    }
}