glc 0.4.2

//! # glc
//!
//! This crate's aim is to generate random expressions based on a context-free
//! grammar.
//!
//! The acronym stands for "gramática livre de contexto" (*context-free grammar*).
//!
//! ## How to Use
//!
//! ```rust
//! use glc::{Grammar, t_or_rule, nt_seq_rule};
//!
//! let grammar = Grammar(
//!     // starting symbol
//!     "S".into(),
//!
//!     // vector of rules
//!     vec![
//!         // a rule that generates a sequence of non-terminals: "A B"
//!         nt_seq_rule!("S" => "A", "B"),
//!         nt_seq_rule!("B" => "A", "B", "N"),
//!         nt_seq_rule!("B" => "E"),
//!         t_or_rule!("E" => ""),
//!
//!         // a rule that is an "or" of terminals: any letter from a-z
//!         t_or_rule!(
//!             "A" => "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k",
//!                    "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v",
//!                    "w", "x", "y", "z"
//!         ),
//!         t_or_rule!("N" => "0", "1", "2", "3", "4", "5", "6", "7", "8", "9"),
//!     ],
//! );
//!
//! // generate a random string with this grammar
//! println!("{}", grammar.gen());
//! ```
//!
//! A simplified version of the macro above is available:
//!
//! ```rust
//! // You may need to tune this parameter depending on how large is your grammar,
//! // since the `grammar` macro is recursive.
//! #![recursion_limit = "256"]
//! use glc::grammar;
//!
//! let _grammar = grammar!{
//!     // The first non-terminal seen (head of the 1st rule) will be
//!     // the starting symbol (in this case: `S`).
//!     S => A B;
//!     B => A B N;
//!     B => E;
//!     E => "";
//!     // Or transform a non-terminal in one among many terminals
//!     A => "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k",
//!          "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v",
//!          "w", "x", "y", "z";
//!     N => "0", "1", "2", "3", "4", "5", "6", "7", "8", "9"
//! };
//!
//! ```
//!
//! For a real-life example take a look at
//! [mexe](https://github.com/yds12/mexe/blob/master/tests/integration.rs).
//!
//! ## Links
//!
//! * Documentation: [docs.rs](https://docs.rs/glc/latest)
//! * Crate: [crates.io](https://crates.io/crates/glc) and [lib.rs](https://lib.rs/crates/glc)
//! * Repository: [Github](https://github.com/yds12/glc)

use rand::prelude::*;

/// Represents a context-free grammar. Contains a [`NonTerminal`] which
/// represents the starting symbol and a list of [`Rule`]s.
#[derive(Debug, Clone)]
pub struct Grammar(pub NonTerminal, pub Vec<Rule>);

/// Represents a grammar rule. Contains a [`NonTerminal`] which represents the
/// rule's head, and a [`RuleBody`].
#[derive(Debug, Clone)]
pub struct Rule(pub NonTerminal, pub RuleBody);

/// The body of a rule. The body can be just a [`Sequence`] (of symbols) or an
/// [`Or`]. The latter is equivalent to a set of rules with the same head, each
/// with a sequence as the body.
///
/// When a rule is applied, a [`NonTerminal`] [`Symbol`] is replaced with the
/// [`RuleBody`]. If the body is an [`Or`], one of the sequences of the `Or`
/// has to be chosen.
#[derive(Debug, Clone)]
pub enum RuleBody {
    Or(Or),
    Sequence(Sequence),
}

/// A disjunction of [`Sequence`]s.
#[derive(Debug, Clone)]
pub struct Or(pub Vec<Sequence>);

/// A sequence of [`Symbol`]s.
#[derive(Debug, Clone)]
pub struct Sequence(pub Vec<Symbol>);

/// A [`Symbol`] can be a [`Terminal`] (a symbol that can appear in the final
/// expression generated by the grammar) or a [`NonTerminal`] (a symbol that
/// must be replaced further).
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Symbol {
    NonTerminal(NonTerminal),
    Terminal(Terminal),
}

/// A non-terminal symbol is a symbol that must be replaced further before the
/// final expression is complete.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct NonTerminal(pub String);

/// A terminal symbol is a symbol that is not further replaceable. It can
/// appear in the final expression generated.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Terminal(pub String);

/// A derivation starts with the starting non-terminal symbol of the grammar and
/// progresses by iteratively replacing non-terminals by some sequence of
/// symbols, according to the grammar rules.
///
/// The second parameter of type `usize` is the index of the last terminal
/// symbol (used to improve performance).
#[derive(Debug, Clone)]
pub struct Derivation(pub Vec<Symbol>, pub usize);

/// An expression constituted of a sequence of terminal symbols. These
/// expressions can be obtained by making a complete [`Derivation`] with the
/// [`Grammar`]. A [`Derivation`] that has only terminal symbols can be
/// converted into an expression.
#[derive(Debug, Clone)]
pub struct Expression(pub Vec<Terminal>);

/// Represents a disjunctive rule: a non-terminal that can be replaced by one of
/// the listed terminal symbols. An invocation of this macro looks like this:
///
///     # use glc::t_or_rule;
///     # fn main() { let _ =
///     t_or_rule!("A" => "a", "b")
///     # ; }
///
/// In the case above we have a non-terminal symbol "A" that can be replaced by
/// either "a" or "b" (both terminals). Note that you can have any number of
/// elements after the `=>`.
#[macro_export]
macro_rules! t_or_rule {
    ($nt:expr => $( $string:expr ),*) => {
        $crate::Rule($crate::NonTerminal($nt.into()),
        $crate::RuleBody::Or($crate::Or(vec![
            $(
                $crate::Sequence(vec![$crate::Symbol::Terminal($crate::Terminal($string.into()))])
            ),*
        ])))
    };
}

/// Represents a rule that replaces one non-terminal by a sequence of
/// non-terminals. Invoke it like this:
///
///     # use glc::nt_seq_rule;
///     # fn main() { let _ =
///     nt_seq_rule!("A" => "B", "C")
///     # ; }
///
/// In the case above, a non-terminal "A" would be replaced by the sequence of
/// non-terminals "B" "C". Note that you can have any number of elements after
/// the `=>`.
#[macro_export]
macro_rules! nt_seq_rule {
    ($nt:expr => $( $string:expr ),*) => {
        $crate::Rule($crate::NonTerminal($nt.into()),
        $crate::RuleBody::Sequence($crate::Sequence(vec![
            $(
                $crate::Symbol::NonTerminal($crate::NonTerminal($string.into()))
            ),*
        ])))
    };
}

/// Generate a grammar using the following syntax:
///
/// ```
/// # use glc::grammar;
/// let _g = grammar!{
///     S => A B C;
///     A => "a", "A";
///     B => "b";
///     C => ""
/// };
/// ```
///
/// As shown above, each rule is either a sequence of non-terminals, or a
/// disjuction of terminals (should be literals, comma-separated).
///
/// **Note**: If your grammar is large, you may need to change the recursion
/// limit for macro expansion in your crate with: `#![recursion_limit = "256"]`
/// (but change `256` to whatever works for your grammar), because this macro
/// heavily uses recursion.
#[macro_export]
macro_rules! grammar {
    ($start:ident $($rest:tt)*) => {
        $crate::Grammar(
            stringify!($start).into(),
            $crate::rules!([$start $($rest)*] [] [])
        )
    };
}

#[macro_export]
#[doc(hidden)]
macro_rules! rules {
    // found `;`, emit a rule (case to handle trailing `;`)
    ([;] [$($rule:tt)*] [$($emitted:tt)*]) => {
        vec![ $($emitted)* $crate::rule!($($rule)*) ]
    };
    // found `;`, emit a rule
    ([; $($rest:tt)*] [$($rule:tt)*] [$($emitted:tt)*]) => {
        $crate::rules!([$($rest)*] [] [$($emitted)* $crate::rule!($($rule)*) ,])
    };
    // emit last rule
    ([] [$($rule:tt)*] [$($emitted:tt)*]) => {
        vec![ $($emitted)* $crate::rule!($($rule)*) ]
    };
    // push one more token into the rule
    ([$first:tt $($rest:tt)*] [] [$($emitted:tt)*]) => {
        $crate::rules!([$($rest)*] [$first] [$($emitted)*])
    };
    // push one more token into the rule
    ([$first:tt $($rest:tt)*] [$($rule:tt)*] [$($emitted:tt)*]) => {
        $crate::rules!([$($rest)*] [$($rule)* $first] [$($emitted)*])
    };
}

/// Parse a rule.
///
/// ```
/// # use glc::rule;
///
/// let r1 = rule!{ A => B C };
/// let r2 = rule!{ B => "b", "c" };
///
/// ```
/// Each rule is either a sequence of non-terminals, or a
/// disjuction of terminals (should be literals, comma-separated).
#[macro_export]
macro_rules! rule {
    ($head:ident => $($nt:ident)*) => {
        $crate::Rule($crate::NonTerminal(stringify!($head).into()),
        $crate::RuleBody::Sequence($crate::Sequence(vec![
            $(
                $crate::Symbol::NonTerminal($crate::NonTerminal(stringify!($nt).into()))
            ),*
        ])))
    };
    ($head:ident => $($t:literal),*) => {
        $crate::Rule($crate::NonTerminal(stringify!($head).into()),
        $crate::RuleBody::Or($crate::Or(vec![
            $(
                $crate::Sequence(vec![$crate::Symbol::Terminal($crate::Terminal($t.into()))])
            ),*
        ])))
    };
}

impl Grammar {
    /// Generate a random expression using the grammar
    pub fn gen(&self) -> String {
        let d = self.start_derivation();
        let expr = d.derive(self);
        expr.to_string()
    }

    /// Start a [`Derivation`] based on this grammar. It will initially only
    /// have the starting [`Symbol`].
    pub fn start_derivation(&self) -> Derivation {
        Derivation(vec![Symbol::NonTerminal(self.0.clone())], 0)
    }

    fn choose_rule(&self, nt: NonTerminal) -> &Rule {
        let mut rules = Vec::new();

        for rule in self.1.iter() {
            if rule.0 == nt {
                rules.push(rule);
            }
        }

        rules.shuffle(&mut rand::thread_rng());
        rules.get(0).unwrap_or_else(|| panic!("no rule for {nt:?}"))
    }
}

impl Derivation {
    /// Apply rules until this [`Derivation`] is complete, and return the
    /// finished [`Expression`].
    pub fn derive(mut self, grammar: &Grammar) -> Expression {
        while !self.is_done() {
            self.derive_step(grammar);
        }

        self.into()
    }

    /// Apply one rule to the [`Derivation`] (if it is not finished).
    pub fn derive_step(&mut self, grammar: &Grammar) {
        if self.is_done() {
            return;
        }

        let nt = self.find_nt();

        if let Some(nt) = nt {
            let rule = grammar.choose_rule(nt);
            self.apply(rule);
        }
    }

    /// Check if the [`Derivation`] is complete, i.e. it has no [`NonTerminal`]
    /// [`Symbol`]s, only [`Terminal`]s.
    pub fn is_done(&self) -> bool {
        for symbol in &self.0[self.1..] {
            if let Symbol::NonTerminal(_) = symbol {
                return false;
            }
        }

        true
    }

    fn find_nt(&self) -> Option<NonTerminal> {
        for symbol in &self.0[self.1..] {
            if let Symbol::NonTerminal(nt) = symbol {
                return Some(nt.clone());
            }
        }

        None
    }

    fn find(&self, nt: &NonTerminal) -> Option<usize> {
        for (i, elem) in self.0.iter().enumerate() {
            if let Symbol::NonTerminal(el) = elem {
                if el == nt {
                    return Some(i);
                }
            }
        }

        None
    }

    fn apply(&mut self, rule: &Rule) {
        match self.find(&rule.0) {
            Some(index) => self.apply_at(rule, index),
            None => panic!("rule cannot be applied"),
        }
    }

    fn apply_at(&mut self, rule: &Rule, index: usize) {
        let seq = match &rule.1 {
            RuleBody::Sequence(seq) => seq.0.clone(),
            RuleBody::Or(or) => or.choose_seq().0.clone(),
        };

        self.1 = index;
        self.0.splice(index..(index + 1), seq);
    }
}

impl From<Derivation> for Expression {
    fn from(d: Derivation) -> Self {
        Self(
            d.0.into_iter()
                .map(|sym| match sym {
                    Symbol::NonTerminal(_) => panic!("derivation is not complete"),
                    Symbol::Terminal(t) => t,
                })
                .collect(),
        )
    }
}

impl From<&str> for NonTerminal {
    fn from(s: &str) -> Self {
        NonTerminal(s.to_string())
    }
}

impl std::fmt::Display for Expression {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
        for t in &self.0 {
            write!(f, "{}", t.0)?;
        }

        Ok(())
    }
}

impl std::fmt::Display for Derivation {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
        for t in &self.0 {
            match t {
                Symbol::NonTerminal(s) => write!(f, "{}", s.0)?,
                Symbol::Terminal(s) => write!(f, "{}", s.0)?,
            }
        }

        Ok(())
    }
}

impl Or {
    fn choose_seq(&self) -> &Sequence {
        if self.0.is_empty() {
            panic!("empty or");
        }

        let rand_index = rand::thread_rng().gen_range(0..self.0.len());
        &self.0[rand_index]
    }
}

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

    fn build_grammar() -> Grammar {
        grammar! {
            S => A N;
            A => "a";
            N => "0"
        }
    }

    #[test]
    fn it_works() {
        let grammar = build_grammar();
        assert_eq!(grammar.gen(), "a0");
    }

    mod grammar_macro {
        use crate::*;

        #[test]
        fn small() {
            let g: Grammar = grammar! {
                A => B C;
                B => "b";
                C => "c"
            };
            assert_eq!(g.gen(), "bc");

            let g: Grammar = grammar! {
                A => B C;
                B => "b";
                C => "c";
            };
            assert_eq!(g.gen(), "bc");

            let g: Grammar = grammar! {
                A => B C;
                B => D;
                C => "c";
                D => "d"
            };
            assert_eq!(g.gen(), "dc");

            let g: Grammar = grammar! {
                A => B C;
                B => D;
                C => "c";
                D => "d", "x"
            };
            let word = g.gen();
            assert!(word == "dc" || word == "xc");
        }

        #[test]
        fn medium() {
            let g = grammar! {
                S => B A;
                A => B A;
                A => E;
                E => "";
                B => "a", "b", "c"
            };

            for _ in 0..100 {
                let w = g.gen();
                assert!(w.chars().all(|c| c == 'a' || c == 'b' || c == 'c'));
            }
        }

        #[test]
        fn large1() {
            let _ = grammar! {
                S => B A;
                A => B A B;
                A => E;
                E => "";
                B => X Y;
                B => "a", "b", "c";
                X => "x", "eks";
                Y => ""
            };
        }

        #[test]
        fn large2() {
            let _ = grammar! {
                S => B A;
                A => B A B;
                A => E;
                E => "";
                B => X Y;
                B => "a", "b", "c";
                X => "x", "eks";
                Y => "";
            };
        }
    }
}