21339734862

Committed 25 Jan 2026 09:19PM UTC coverage: 96.233% (-0.5%) from 96.753%

Build # 21339734862

Build Type

Pull #187

github

Committed by

web-flow

Commit Message

Merge d1bd07d72 into fbcc780ec

Pull Request Pull Request #187: add explicit parser

Run Details

387 of 411 new or added lines in 5 files covered. (94.16%)

1 existing line in 1 file now uncovered.

2427 of 2522 relevant lines covered (96.23%)

24194.7 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

93.02

/src/parser/mod.rs

pub(crate) mod grammar;

use crate::ParseTree;
use crate::error::Error;
use crate::grammar::Grammar;
use crate::term::Term;
use grammar::ParseGrammar;
use std::collections::HashSet;
use std::rc::Rc;

/// A reusable parser built from a `Grammar` that validates all nonterminals are defined
/// at construction time.
///
/// # Example
///
/// ```rust
/// use bnf::Grammar;
///
/// let grammar: Grammar = "<dna> ::= <base> | <base> <dna>
/// <base> ::= 'A' | 'C' | 'G' | 'T'"
///     .parse()
///     .unwrap();
///
/// let parser = grammar.build_parser()?;
/// let parse_trees: Vec<_> = parser.parse_input("GATTACA").collect();
/// # Ok::<(), bnf::Error>(())
/// ```
#[derive(Debug)]
pub struct GrammarParser<'gram> {
    starting_term: &'gram Term,
    parse_grammar: Rc<ParseGrammar<'gram>>,
}

impl<'gram> GrammarParser<'gram> {
    /// Construct a new `GrammarParser` from a `Grammar`, validating that all
    /// nonterminals referenced in productions have definitions.
    ///
    /// # Errors
    ///
    /// Returns `Error::ValidationError` if any nonterminal used in the RHS of
    /// productions lacks a definition in the grammar.
    pub fn new(grammar: &'gram Grammar) -> Result<Self, Error> {
        validate_nonterminals(grammar)?;
        let starting_term = grammar.starting_term().ok_or_else(|| {
            Error::ValidationError("Grammar must have at least one production".to_string())
        })?;
        let parse_grammar = Rc::new(ParseGrammar::new(grammar));
        Ok(Self {
            starting_term,
            parse_grammar,
        })
    }

    /// Parse an input string using the grammar's starting nonterminal.
    ///
    /// Returns an iterator over all possible parse trees for the input.
    pub fn parse_input(&self, input: &'gram str) -> impl Iterator<Item = ParseTree<'gram>> {
        self.parse_input_starting_with(input, self.starting_term)
    }

    /// Parse an input string starting with the given term (nonterminal or terminal).
    ///
    /// Returns an iterator over all possible parse trees for the input.
    pub fn parse_input_starting_with(
        &self,
        input: &'gram str,
        start: &'gram Term,
    ) -> impl Iterator<Item = ParseTree<'gram>> {
        crate::earley::parse_starting_with_grammar(&self.parse_grammar, input, start)
    }
}

/// Validate that all nonterminals referenced in the grammar have definitions.
///
/// # Errors
///
/// Returns `Error::ValidationError` with a message listing all undefined nonterminals.
fn validate_nonterminals(grammar: &Grammar) -> Result<(), Error> {
    // Collect all nonterminals defined in LHS of productions
    let mut defined_nonterminals = HashSet::new();
    for production in grammar.productions_iter() {
        if let Term::Nonterminal(ref nt) = production.lhs {
            defined_nonterminals.insert(nt.clone());
        }
    }

    // Collect all nonterminals used in RHS of all productions
    let mut referenced_nonterminals = HashSet::new();
    for production in grammar.productions_iter() {
        for expression in production.rhs_iter() {
            for term in expression.terms_iter() {
                match term {
                    Term::Nonterminal(nt) => {
                        referenced_nonterminals.insert(nt.clone());
                    }
                    Term::AnonymousNonterminal(exprs) => {
                        // For anonymous nonterminals, check the expressions they contain
                        for expr in exprs {
                            for inner_term in expr.terms_iter() {
                                if let Term::Nonterminal(nt) = inner_term {
                                    referenced_nonterminals.insert(nt.clone());
                                }
                            }
                        }
                    }
                    Term::Terminal(_) => {
                        // Terminals don't need definitions
                    }
                }
            }
        }
    }

    // Find undefined nonterminals
    let undefined: Vec<String> = referenced_nonterminals
        .difference(&defined_nonterminals)
        .cloned()
        .collect();

    if !undefined.is_empty() {
        let message = format!(
            "Undefined nonterminals: {}",
            undefined
                .iter()
                .map(|nt| format!("<{nt}>"))
                .collect::<Vec<_>>()
                .join(", ")
        );
        return Err(Error::ValidationError(message));
    }

    Ok(())
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::Grammar;
    use crate::expression::Expression;
    use crate::production::Production;
    use quickcheck::{Arbitrary, Gen, QuickCheck, TestResult};

    #[test]
    fn parser_construction_with_valid_grammar() {
        let grammar: Grammar = "<dna> ::= <base> | <base> <dna>
        <base> ::= 'A' | 'C' | 'G' | 'T'"
            .parse()
            .unwrap();

        let parser = grammar.build_parser();
        assert!(
            parser.is_ok(),
            "Parser should be constructible from valid grammar"
        );
    }

    #[test]
    fn parser_construction_fails_with_undefined_nonterminal() {
        let grammar: Grammar = "<dna> ::= <base> | <base> <dna>
        <base> ::= <undefined>"
            .parse()
            .unwrap();

        let parser = grammar.build_parser();
        assert!(
            parser.is_err(),
            "Parser construction should fail with undefined nonterminal"
        );
        assert!(
            matches!(parser.unwrap_err(), Error::ValidationError(_)),
            "Error should be ValidationError"
        );
    }

    #[test]
    fn parser_can_parse_multiple_inputs() {
        let grammar: Grammar = "<dna> ::= <base> | <base> <dna>
        <base> ::= 'A' | 'C' | 'G' | 'T'"
            .parse()
            .unwrap();

        let parser = grammar.build_parser().unwrap();

        let input1 = "GATTACA";
        let input2 = "ATCG";

        let parse_trees1: Vec<_> = parser.parse_input(input1).collect();
        let parse_trees2: Vec<_> = parser.parse_input(input2).collect();

        assert!(!parse_trees1.is_empty(), "Should parse first input");
        assert!(!parse_trees2.is_empty(), "Should parse second input");
    }

    #[test]
    fn parser_accepts_explicit_starting_nonterminal() {
        let grammar: Grammar = "<base> ::= 'A' | 'C' | 'G' | 'T'
        <dna> ::= <base> | <base> <dna>"
            .parse()
            .unwrap();

        let parser = grammar.build_parser().unwrap();
        let input = "GATTACA";
        let start_term = Term::Nonterminal("dna".to_string());

        let parse_trees: Vec<_> = parser
            .parse_input_starting_with(input, &start_term)
            .collect();

        assert!(
            !parse_trees.is_empty(),
            "Should parse with explicit starting nonterminal"
        );
    }

    #[test]
    fn parser_accepts_explicit_starting_terminal() {
        let grammar: Grammar = "<base> ::= 'A' | 'C' | 'G' | 'T'
        <dna> ::= <base> | <base> <dna>"
            .parse()
            .unwrap();

        let parser = grammar.build_parser().unwrap();
        let input = "G";
        let start_term = Term::Terminal("G".to_string());

        // Note: Starting with a terminal directly doesn't work with Earley parser
        // since it expects a nonterminal to have productions. This test verifies
        // the API accepts terminals, but they won't produce parse trees unless
        // there's a production with that terminal as LHS (which is invalid).
        let parse_trees: Vec<_> = parser
            .parse_input_starting_with(input, &start_term)
            .collect();

        // This will be empty since there's no production with a terminal as LHS
        // The API accepts it, but it won't produce results
        assert_eq!(
            parse_trees.len(),
            0,
            "Terminal starting term produces no parse trees"
        );
    }

    #[test]
    fn parser_is_order_independent() {
        // Create grammar with productions in one order
        let grammar1: Grammar = "<dna> ::= <base> | <base> <dna>
        <base> ::= 'A' | 'C' | 'G' | 'T'"
            .parse()
            .unwrap();

        // Create same grammar with productions in different order
        let grammar2: Grammar = "<base> ::= 'A' | 'C' | 'G' | 'T'
        <dna> ::= <base> | <base> <dna>"
            .parse()
            .unwrap();

        let parser1 = grammar1.build_parser().unwrap();
        let parser2 = grammar2.build_parser().unwrap();

        let input = "GATTACA";
        // Use explicit starting term to ensure both use the same starting point
        let start_term = Term::Nonterminal("dna".to_string());

        let parse_trees1: Vec<_> = parser1
            .parse_input_starting_with(input, &start_term)
            .collect();
        let parse_trees2: Vec<_> = parser2
            .parse_input_starting_with(input, &start_term)
            .collect();

        // Results should be identical regardless of production order when using
        // the same explicit starting term
        assert_eq!(
            parse_trees1.len(),
            parse_trees2.len(),
            "Should produce same number of parse trees regardless of order"
        );
    }

    // Helper: Generate a simple valid grammar with known structure
    #[derive(Debug, Clone)]
    struct SimpleValidGrammar(Grammar);
    impl Arbitrary for SimpleValidGrammar {
        fn arbitrary(g: &mut Gen) -> Self {
            // Generate 1-5 nonterminal names
            let num_nonterms = usize::arbitrary(g) % 5 + 1;
            let nonterms: Vec<String> = (0..num_nonterms).map(|i| format!("nt{}", i)).collect();

            let mut productions = Vec::new();

            // Create productions: each nonterminal references only defined ones
            for (idx, nt) in nonterms.iter().enumerate() {
                let mut expressions = Vec::new();

                // Each production has 1-3 alternatives
                let num_alternatives = usize::arbitrary(g) % 3 + 1;
                for _ in 0..num_alternatives {
                    let mut terms = Vec::new();

                    // Each alternative has 1-3 terms
                    let num_terms = usize::arbitrary(g) % 3 + 1;
                    for _ in 0..num_terms {
                        if bool::arbitrary(g) && idx > 0 {
                            // Reference a previously defined nonterminal
                            let ref_idx = usize::arbitrary(g) % idx;
                            if let Some(nt) = nonterms.get(ref_idx) {
                                terms.push(Term::Nonterminal(nt.clone()));
                            } else {
                                // Use a terminal if index is out of bounds
                                let term_str = String::arbitrary(g);
                                terms.push(Term::Terminal(term_str));
                            }
                        } else {
                            // Use a terminal
                            let term_str = String::arbitrary(g);
                            terms.push(Term::Terminal(term_str));
                        }
                    }

                    expressions.push(Expression::from_parts(terms));
                }

                productions.push(Production::from_parts(
                    Term::Nonterminal(nt.clone()),
                    expressions,
                ));
            }

            Self(Grammar::from_parts(productions))
        }
    }

    // Helper: Generate grammar that may have undefined nonterminals
    #[derive(Debug, Clone)]
    struct GrammarWithUndefined(Grammar);
    impl Arbitrary for GrammarWithUndefined {
        fn arbitrary(g: &mut Gen) -> Self {
            let num_nonterms = usize::arbitrary(g) % 4 + 1;
            let mut nonterms: Vec<String> = (0..num_nonterms).map(|i| format!("nt{}", i)).collect();

            // Add some undefined nonterminals
            let num_undefined = usize::arbitrary(g) % 3;
            for i in 0..num_undefined {
                nonterms.push(format!("undefined{}", i));
            }

            let mut productions = Vec::new();
            let defined_count = num_nonterms;

            for (idx, nt) in nonterms.iter().enumerate() {
                if idx >= defined_count {
                    // Don't define the undefined nonterminals
                    continue;
                }

                let mut expressions = Vec::new();
                let num_alternatives = usize::arbitrary(g) % 2 + 1;

                for _ in 0..num_alternatives {
                    let mut terms = Vec::new();
                    let num_terms = usize::arbitrary(g) % 2 + 1;

                    for _ in 0..num_terms {
                        if bool::arbitrary(g) && !nonterms.is_empty() {
                            // Reference any nonterminal (may be undefined)
                            let ref_idx = usize::arbitrary(g) % nonterms.len();
                            if let Some(nt) = nonterms.get(ref_idx) {
                                terms.push(Term::Nonterminal(nt.clone()));
                            } else {
                                terms.push(Term::Terminal(String::arbitrary(g)));
                            }
                        } else {
                            terms.push(Term::Terminal(String::arbitrary(g)));
                        }
                    }

                    expressions.push(Expression::from_parts(terms));
                }

                productions.push(Production::from_parts(
                    Term::Nonterminal(nt.clone()),
                    expressions,
                ));
            }

            Self(Grammar::from_parts(productions))
        }
    }

    // Property test: Parser construction fails if any nonterminal lacks definition
    fn prop_parser_fails_with_undefined_nonterminal(grammar: GrammarWithUndefined) -> TestResult {
        let grammar = grammar.0;

        // Collect all nonterminals defined in LHS
        let mut defined = std::collections::HashSet::new();
        for production in grammar.productions_iter() {
            if let Term::Nonterminal(nt) = &production.lhs {
                defined.insert(nt.clone());
            }
        }

        // Collect all nonterminals used in RHS
        let mut referenced = std::collections::HashSet::new();
        for production in grammar.productions_iter() {
            for expression in production.rhs_iter() {
                for term in expression.terms_iter() {
                    if let Term::Nonterminal(nt) = term {
                        referenced.insert(nt.clone());
                    }
                }
            }
        }

        // Find undefined nonterminals
        let undefined: Vec<_> = referenced.difference(&defined).cloned().collect();

        let parser_result = grammar.build_parser();

        if undefined.is_empty() {
            // All nonterminals are defined, parser should succeed
            TestResult::from_bool(parser_result.is_ok())
        } else {
            // Some nonterminals are undefined, parser should fail
            TestResult::from_bool(
                parser_result.is_err()
                    && matches!(parser_result.unwrap_err(), Error::ValidationError(_)),
            )
        }
    }

    #[test]
    fn parser_fails_with_undefined_nonterminal() {
        QuickCheck::new().tests(100).quickcheck(
            prop_parser_fails_with_undefined_nonterminal as fn(GrammarWithUndefined) -> TestResult,
        );
    }

    // Helper: Generate valid grammar with at least 2 productions
    #[derive(Debug, Clone)]
    struct ValidGrammarWithMultipleProductions(Grammar);
    impl Arbitrary for ValidGrammarWithMultipleProductions {
        fn arbitrary(g: &mut Gen) -> Self {
            // Generate 2-5 nonterminals
            let num_nonterms = usize::arbitrary(g) % 4 + 2;
            let nonterms: Vec<String> = (0..num_nonterms).map(|i| format!("nt{}", i)).collect();

            let mut productions = Vec::new();

            for (idx, nt) in nonterms.iter().enumerate() {
                let mut expressions = Vec::new();
                let num_alternatives = usize::arbitrary(g) % 2 + 1;

                for _ in 0..num_alternatives {
                    let mut terms = Vec::new();
                    let num_terms = usize::arbitrary(g) % 2 + 1;

                    for _ in 0..num_terms {
                        if bool::arbitrary(g) && idx > 0 {
                            // Reference a previously defined nonterminal
                            let ref_idx = usize::arbitrary(g) % idx;
                            if let Some(nt) = nonterms.get(ref_idx) {
                                terms.push(Term::Nonterminal(nt.clone()));
                            } else {
                                terms.push(Term::Terminal(String::arbitrary(g)));
                            }
                        } else {
                            terms.push(Term::Terminal(String::arbitrary(g)));
                        }
                    }

                    expressions.push(Expression::from_parts(terms));
                }

                productions.push(Production::from_parts(
                    Term::Nonterminal(nt.clone()),
                    expressions,
                ));
            }

            Self(Grammar::from_parts(productions))
        }
    }

    // Property test: Parser results are identical regardless of production order
    fn prop_parser_order_independent(grammar: ValidGrammarWithMultipleProductions) -> TestResult {
        let grammar = grammar.0;

        // Create a shuffled version of the grammar
        let mut productions: Vec<_> = grammar.productions_iter().cloned().collect();
        let mut rng = rand::rng();
        rand::seq::SliceRandom::shuffle(productions.as_mut_slice(), &mut rng);

        let grammar1 = grammar;
        let grammar2 = Grammar::from_parts(productions);

        let parser1 = match grammar1.build_parser() {
            Ok(p) => p,
            Err(_) => return TestResult::discard(),
        };
        let parser2 = match grammar2.build_parser() {
            Ok(p) => p,
            Err(_) => return TestResult::discard(),
        };

        // Get starting term from first grammar
        let starting_term = match grammar1.starting_term() {
            Some(t) => t,
            None => return TestResult::discard(),
        };

        // Generate a test sentence
        let sentence = match grammar1.generate() {
            Ok(s) => s,
            Err(_) => return TestResult::discard(),
        };

        // Parse with both parsers using explicit starting term
        let parse_trees1: Vec<_> = parser1
            .parse_input_starting_with(&sentence, starting_term)
            .collect();
        let parse_trees2: Vec<_> = parser2
            .parse_input_starting_with(&sentence, starting_term)
            .collect();

        // Results should be identical
        TestResult::from_bool(parse_trees1.len() == parse_trees2.len())
    }

    #[test]
    fn parser_order_independent() {
        QuickCheck::new().tests(50).quickcheck(
            prop_parser_order_independent as fn(ValidGrammarWithMultipleProductions) -> TestResult,
        );
    }

    // Property test: Parser can be reused multiple times with same results
    fn prop_parser_reusable(grammar: SimpleValidGrammar) -> TestResult {
        let grammar = grammar.0;

        // Only test with grammars that can generate
        if !grammar.terminates() {
            return TestResult::discard();
        }

        let parser = match grammar.build_parser() {
            Ok(p) => p,
            Err(_) => return TestResult::discard(),
        };

        // Generate a sentence
        let sentence = match grammar.generate() {
            Ok(s) => s,
            Err(_) => return TestResult::discard(),
        };

        // Parse the same sentence multiple times
        let parse_trees1: Vec<_> = parser.parse_input(&sentence).collect();
        let parse_trees2: Vec<_> = parser.parse_input(&sentence).collect();
        let parse_trees3: Vec<_> = parser.parse_input(&sentence).collect();

        // All results should be identical
        TestResult::from_bool(
            parse_trees1.len() == parse_trees2.len() && parse_trees2.len() == parse_trees3.len(),
        )
    }

    #[test]
    fn parser_reusable() {
        QuickCheck::new()
            .tests(100)
            .quickcheck(prop_parser_reusable as fn(SimpleValidGrammar) -> TestResult);
    }

    // Property test: Parser validation catches all undefined nonterminals
    // Simplified: Build grammars with known undefined nonterminals
    fn prop_validation_catches_all_undefined(grammar: GrammarWithUndefined) -> TestResult {
        let grammar = grammar.0;

        // Collect all nonterminals defined in LHS
        let mut defined = std::collections::HashSet::new();
        for production in grammar.productions_iter() {
            if let Term::Nonterminal(nt) = &production.lhs {
                defined.insert(nt.clone());
            }
        }

        // Collect all nonterminals used in RHS
        let mut referenced = std::collections::HashSet::new();
        for production in grammar.productions_iter() {
            for expression in production.rhs_iter() {
                for term in expression.terms_iter() {
                    if let Term::Nonterminal(nt) = term {
                        referenced.insert(nt.clone());
                    }
                }
            }
        }

        let undefined: Vec<_> = referenced.difference(&defined).cloned().collect();

        let parser_result = grammar.build_parser();

        match parser_result {
            Ok(_) => {
                // Parser succeeded, so there should be no undefined nonterminals
                TestResult::from_bool(undefined.is_empty())
            }
            Err(Error::ValidationError(msg)) => {
                // Parser failed, error message should mention all undefined nonterminals
                let all_mentioned = undefined
                    .iter()
                    .all(|nt| msg.contains(&format!("<{nt}>")) || msg.contains(nt));
                TestResult::from_bool(!undefined.is_empty() && all_mentioned)
            }
            Err(_) => TestResult::error("Expected ValidationError"),
        }
    }

    #[test]
    fn validation_catches_all_undefined() {
        QuickCheck::new().tests(100).quickcheck(
            prop_validation_catches_all_undefined as fn(GrammarWithUndefined) -> TestResult,
        );
    }
}

1	pub(crate) mod grammar;
2
3	use crate::ParseTree;
4	use crate::error::Error;
5	use crate::grammar::Grammar;
6	use crate::term::Term;
7	use grammar::ParseGrammar;
8	use std::collections::HashSet;
9	use std::rc::Rc;
10
11	/// A reusable parser built from a `Grammar` that validates all nonterminals are defined
12	/// at construction time.
13	///
14	/// # Example
15	///
16	/// ```rust
17	/// use bnf::Grammar;
18	///
19	/// let grammar: Grammar = "<dna> ::= <base> \| <base> <dna>
20	/// <base> ::= 'A' \| 'C' \| 'G' \| 'T'"
21	/// .parse()
22	/// .unwrap();
23	///
24	/// let parser = grammar.build_parser()?;
25	/// let parse_trees: Vec<_> = parser.parse_input("GATTACA").collect();
26	/// # Ok::<(), bnf::Error>(())
27	/// ```
28	#[derive(Debug)]
29	pub struct GrammarParser<'gram> {
30	starting_term: &'gram Term,
31	parse_grammar: Rc<ParseGrammar<'gram>>,
32	}
33
34	impl<'gram> GrammarParser<'gram> {
35	/// Construct a new `GrammarParser` from a `Grammar`, validating that all
36	/// nonterminals referenced in productions have definitions.
37	///
38	/// # Errors
39	///
40	/// Returns `Error::ValidationError` if any nonterminal used in the RHS of
41	/// productions lacks a definition in the grammar.
42	pub fn new(grammar: &'gram Grammar) -> Result<Self, Error> {	407✔
43	validate_nonterminals(grammar)?;	407✔
44	let starting_term = grammar.starting_term().ok_or_else(\|\| {	330✔
NEW 45	Error::ValidationError("Grammar must have at least one production".to_string())	×
NEW 46	})?;	×
47	let parse_grammar = Rc::new(ParseGrammar::new(grammar));	330✔
48	Ok(Self {	330✔
49	starting_term,	330✔
50	parse_grammar,	330✔
51	})	330✔
52	}	407✔
53
54	/// Parse an input string using the grammar's starting nonterminal.
55	///
56	/// Returns an iterator over all possible parse trees for the input.
57	pub fn parse_input(&self, input: &'gram str) -> impl Iterator<Item = ParseTree<'gram>> {	302✔
58	self.parse_input_starting_with(input, self.starting_term)	302✔
59	}	302✔
60
61	/// Parse an input string starting with the given term (nonterminal or terminal).
62	///
63	/// Returns an iterator over all possible parse trees for the input.
64	pub fn parse_input_starting_with(	406✔
65	&self,	406✔
66	input: &'gram str,	406✔
67	start: &'gram Term,	406✔
68	) -> impl Iterator<Item = ParseTree<'gram>> {	406✔
69	crate::earley::parse_starting_with_grammar(&self.parse_grammar, input, start)	406✔
70	}	406✔
71	}
72
73	/// Validate that all nonterminals referenced in the grammar have definitions.
74	///
75	/// # Errors
76	///
77	/// Returns `Error::ValidationError` with a message listing all undefined nonterminals.
78	fn validate_nonterminals(grammar: &Grammar) -> Result<(), Error> {	407✔
79	// Collect all nonterminals defined in LHS of productions
80	let mut defined_nonterminals = HashSet::new();	407✔
81	for production in grammar.productions_iter() {	1,148✔
82	if let Term::Nonterminal(ref nt) = production.lhs {	1,148✔
83	defined_nonterminals.insert(nt.clone());	1,148✔
84	}	1,148✔
85	}
86
87	// Collect all nonterminals used in RHS of all productions
88	let mut referenced_nonterminals = HashSet::new();	407✔
89	for production in grammar.productions_iter() {	1,148✔
90	for expression in production.rhs_iter() {	1,840✔
91	for term in expression.terms_iter() {	2,950✔
92	match term {	2,950✔
93	Term::Nonterminal(nt) => {	1,219✔
94	referenced_nonterminals.insert(nt.clone());	1,219✔
95	}	1,219✔
NEW 96	Term::AnonymousNonterminal(exprs) => {	×
97	// For anonymous nonterminals, check the expressions they contain
NEW 98	for expr in exprs {	×
NEW 99	for inner_term in expr.terms_iter() {	×
NEW 100	if let Term::Nonterminal(nt) = inner_term {	×
NEW 101	referenced_nonterminals.insert(nt.clone());	×
NEW 102	}	×
103	}
104	}
105	}
106	Term::Terminal(_) => {	1,731✔
107	// Terminals don't need definitions	1,731✔
108	}	1,731✔
109	}
110	}
111	}
112	}
113
114	// Find undefined nonterminals
115	let undefined: Vec<String> = referenced_nonterminals	407✔
116	.difference(&defined_nonterminals)	407✔
117	.cloned()	407✔
118	.collect();	407✔
119
120	if !undefined.is_empty() {	407✔
121	let message = format!(	77✔
122	"Undefined nonterminals: {}",
123	undefined	77✔
124	.iter()	77✔
125	.map(\|nt\| format!("<{nt}>"))	89✔
126	.collect::<Vec<_>>()	77✔
127	.join(", ")	77✔
128	);
129	return Err(Error::ValidationError(message));	77✔
130	}	330✔
131
132	Ok(())	330✔
133	}	407✔
134
135	#[cfg(test)]
136	mod tests {
137	use super::*;
138	use crate::Grammar;
139	use crate::expression::Expression;
140	use crate::production::Production;
141	use quickcheck::{Arbitrary, Gen, QuickCheck, TestResult};
142
143	#[test]
144	fn parser_construction_with_valid_grammar() {	1✔
145	let grammar: Grammar = "<dna> ::= <base> \| <base> <dna>	1✔
146	<base> ::= 'A' \| 'C' \| 'G' \| 'T'"	1✔
147	.parse()	1✔
148	.unwrap();	1✔
149
150	let parser = grammar.build_parser();	1✔
151	assert!(	1✔
152	parser.is_ok(),	1✔
153	"Parser should be constructible from valid grammar"
154	);
155	}	1✔
156
157	#[test]
158	fn parser_construction_fails_with_undefined_nonterminal() {	1✔
159	let grammar: Grammar = "<dna> ::= <base> \| <base> <dna>	1✔
160	<base> ::= <undefined>"	1✔
161	.parse()	1✔
162	.unwrap();	1✔
163
164	let parser = grammar.build_parser();	1✔
165	assert!(	1✔
166	parser.is_err(),	1✔
167	"Parser construction should fail with undefined nonterminal"
168	);
169	assert!(	1✔
170	matches!(parser.unwrap_err(), Error::ValidationError(_)),	1✔
171	"Error should be ValidationError"
172	);
173	}	1✔
174
175	#[test]
176	fn parser_can_parse_multiple_inputs() {	1✔
177	let grammar: Grammar = "<dna> ::= <base> \| <base> <dna>	1✔
178	<base> ::= 'A' \| 'C' \| 'G' \| 'T'"	1✔
179	.parse()	1✔
180	.unwrap();	1✔
181
182	let parser = grammar.build_parser().unwrap();	1✔
183
184	let input1 = "GATTACA";	1✔
185	let input2 = "ATCG";	1✔
186
187	let parse_trees1: Vec<_> = parser.parse_input(input1).collect();	1✔
188	let parse_trees2: Vec<_> = parser.parse_input(input2).collect();	1✔
189
190	assert!(!parse_trees1.is_empty(), "Should parse first input");	1✔
191	assert!(!parse_trees2.is_empty(), "Should parse second input");	1✔
192	}	1✔
193
194	#[test]
195	fn parser_accepts_explicit_starting_nonterminal() {	1✔
196	let grammar: Grammar = "<base> ::= 'A' \| 'C' \| 'G' \| 'T'	1✔
197	<dna> ::= <base> \| <base> <dna>"	1✔
198	.parse()	1✔
199	.unwrap();	1✔
200
201	let parser = grammar.build_parser().unwrap();	1✔
202	let input = "GATTACA";	1✔
203	let start_term = Term::Nonterminal("dna".to_string());	1✔
204
205	let parse_trees: Vec<_> = parser	1✔
206	.parse_input_starting_with(input, &start_term)	1✔
207	.collect();	1✔
208
209	assert!(	1✔
210	!parse_trees.is_empty(),	1✔
211	"Should parse with explicit starting nonterminal"
212	);
213	}	1✔
214
215	#[test]
216	fn parser_accepts_explicit_starting_terminal() {	1✔
217	let grammar: Grammar = "<base> ::= 'A' \| 'C' \| 'G' \| 'T'	1✔
218	<dna> ::= <base> \| <base> <dna>"	1✔
219	.parse()	1✔
220	.unwrap();	1✔
221
222	let parser = grammar.build_parser().unwrap();	1✔
223	let input = "G";	1✔
224	let start_term = Term::Terminal("G".to_string());	1✔
225
226	// Note: Starting with a terminal directly doesn't work with Earley parser
227	// since it expects a nonterminal to have productions. This test verifies
228	// the API accepts terminals, but they won't produce parse trees unless
229	// there's a production with that terminal as LHS (which is invalid).
230	let parse_trees: Vec<_> = parser	1✔
231	.parse_input_starting_with(input, &start_term)	1✔
232	.collect();	1✔
233
234	// This will be empty since there's no production with a terminal as LHS
235	// The API accepts it, but it won't produce results
236	assert_eq!(	1✔
237	parse_trees.len(),	1✔
238	0,
239	"Terminal starting term produces no parse trees"
240	);
241	}	1✔
242
243	#[test]
244	fn parser_is_order_independent() {	1✔
245	// Create grammar with productions in one order
246	let grammar1: Grammar = "<dna> ::= <base> \| <base> <dna>	1✔
247	<base> ::= 'A' \| 'C' \| 'G' \| 'T'"	1✔
248	.parse()	1✔
249	.unwrap();	1✔
250
251	// Create same grammar with productions in different order
252	let grammar2: Grammar = "<base> ::= 'A' \| 'C' \| 'G' \| 'T'	1✔
253	<dna> ::= <base> \| <base> <dna>"	1✔
254	.parse()	1✔
255	.unwrap();	1✔
256
257	let parser1 = grammar1.build_parser().unwrap();	1✔
258	let parser2 = grammar2.build_parser().unwrap();	1✔
259
260	let input = "GATTACA";	1✔
261	// Use explicit starting term to ensure both use the same starting point
262	let start_term = Term::Nonterminal("dna".to_string());	1✔
263
264	let parse_trees1: Vec<_> = parser1	1✔
265	.parse_input_starting_with(input, &start_term)	1✔
266	.collect();	1✔
267	let parse_trees2: Vec<_> = parser2	1✔
268	.parse_input_starting_with(input, &start_term)	1✔
269	.collect();	1✔
270
271	// Results should be identical regardless of production order when using
272	// the same explicit starting term
273	assert_eq!(	1✔
274	parse_trees1.len(),	1✔
275	parse_trees2.len(),	1✔
276	"Should produce same number of parse trees regardless of order"
277	);
278	}	1✔
279
280	// Helper: Generate a simple valid grammar with known structure
281	#[derive(Debug, Clone)]
282	struct SimpleValidGrammar(Grammar);
283	impl Arbitrary for SimpleValidGrammar {
284	fn arbitrary(g: &mut Gen) -> Self {	100✔
285	// Generate 1-5 nonterminal names
286	let num_nonterms = usize::arbitrary(g) % 5 + 1;	100✔
287	let nonterms: Vec<String> = (0..num_nonterms).map(\|i\| format!("nt{}", i)).collect();	270✔
288
289	let mut productions = Vec::new();	100✔
290
291	// Create productions: each nonterminal references only defined ones
292	for (idx, nt) in nonterms.iter().enumerate() {	270✔
293	let mut expressions = Vec::new();	270✔
294
295	// Each production has 1-3 alternatives
296	let num_alternatives = usize::arbitrary(g) % 3 + 1;	270✔
297	for _ in 0..num_alternatives {	270✔
298	let mut terms = Vec::new();	506✔
299
300	// Each alternative has 1-3 terms
301	let num_terms = usize::arbitrary(g) % 3 + 1;	506✔
302	for _ in 0..num_terms {	506✔
303	if bool::arbitrary(g) && idx > 0 {	953✔
304	// Reference a previously defined nonterminal
305	let ref_idx = usize::arbitrary(g) % idx;	287✔
306	if let Some(nt) = nonterms.get(ref_idx) {	287✔
307	terms.push(Term::Nonterminal(nt.clone()));	287✔
308	} else {	287✔
NEW 309	// Use a terminal if index is out of bounds	×
NEW 310	let term_str = String::arbitrary(g);	×
NEW 311	terms.push(Term::Terminal(term_str));	×
NEW 312	}	×
313	} else {	666✔
314	// Use a terminal	666✔
315	let term_str = String::arbitrary(g);	666✔
316	terms.push(Term::Terminal(term_str));	666✔
317	}	666✔
318	}
319
320	expressions.push(Expression::from_parts(terms));	506✔
321	}
322
323	productions.push(Production::from_parts(	270✔
324	Term::Nonterminal(nt.clone()),	270✔
325	expressions,	270✔
326	));
327	}
328
329	Self(Grammar::from_parts(productions))	100✔
330	}	100✔
331	}
332
333	// Helper: Generate grammar that may have undefined nonterminals
334	#[derive(Debug, Clone)]
335	struct GrammarWithUndefined(Grammar);
336	impl Arbitrary for GrammarWithUndefined {
337	fn arbitrary(g: &mut Gen) -> Self {	200✔
338	let num_nonterms = usize::arbitrary(g) % 4 + 1;	200✔
339	let mut nonterms: Vec<String> = (0..num_nonterms).map(\|i\| format!("nt{}", i)).collect();	512✔
340
341	// Add some undefined nonterminals
342	let num_undefined = usize::arbitrary(g) % 3;	200✔
343	for i in 0..num_undefined {	200✔
344	nonterms.push(format!("undefined{}", i));	189✔
345	}	189✔
346
347	let mut productions = Vec::new();	200✔
348	let defined_count = num_nonterms;	200✔
349
350	for (idx, nt) in nonterms.iter().enumerate() {	701✔
351	if idx >= defined_count {	701✔
352	// Don't define the undefined nonterminals
353	continue;	189✔
354	}	512✔
355
356	let mut expressions = Vec::new();	512✔
357	let num_alternatives = usize::arbitrary(g) % 2 + 1;	512✔
358
359	for _ in 0..num_alternatives {	512✔
360	let mut terms = Vec::new();	769✔
361	let num_terms = usize::arbitrary(g) % 2 + 1;	769✔
362
363	for _ in 0..num_terms {	769✔
364	if bool::arbitrary(g) && !nonterms.is_empty() {	1,163✔
365	// Reference any nonterminal (may be undefined)
366	let ref_idx = usize::arbitrary(g) % nonterms.len();	622✔
367	if let Some(nt) = nonterms.get(ref_idx) {	622✔
368	terms.push(Term::Nonterminal(nt.clone()));	622✔
369	} else {	622✔
NEW 370	terms.push(Term::Terminal(String::arbitrary(g)));	×
NEW 371	}	×
372	} else {	541✔
373	terms.push(Term::Terminal(String::arbitrary(g)));	541✔
374	}	541✔
375	}
376
377	expressions.push(Expression::from_parts(terms));	769✔
378	}
379
380	productions.push(Production::from_parts(	512✔
381	Term::Nonterminal(nt.clone()),	512✔
382	expressions,	512✔
383	));
384	}
385
386	Self(Grammar::from_parts(productions))	200✔
387	}	200✔
388	}
389
390	// Property test: Parser construction fails if any nonterminal lacks definition
391	fn prop_parser_fails_with_undefined_nonterminal(grammar: GrammarWithUndefined) -> TestResult {	100✔
392	let grammar = grammar.0;	100✔
393
394	// Collect all nonterminals defined in LHS
395	let mut defined = std::collections::HashSet::new();	100✔
396	for production in grammar.productions_iter() {	258✔
397	if let Term::Nonterminal(nt) = &production.lhs {	258✔
398	defined.insert(nt.clone());	258✔
399	}	258✔
400	}
401
402	// Collect all nonterminals used in RHS
403	let mut referenced = std::collections::HashSet::new();	100✔
404	for production in grammar.productions_iter() {	258✔
405	for expression in production.rhs_iter() {	387✔
406	for term in expression.terms_iter() {	589✔
407	if let Term::Nonterminal(nt) = term {	589✔
408	referenced.insert(nt.clone());	312✔
409	}	312✔
410	}
411	}
412	}
413
414	// Find undefined nonterminals
415	let undefined: Vec<_> = referenced.difference(&defined).cloned().collect();	100✔
416
417	let parser_result = grammar.build_parser();	100✔
418
419	if undefined.is_empty() {	100✔
420	// All nonterminals are defined, parser should succeed
421	TestResult::from_bool(parser_result.is_ok())	62✔
422	} else {
423	// Some nonterminals are undefined, parser should fail
424	TestResult::from_bool(	38✔
425	parser_result.is_err()	38✔
426	&& matches!(parser_result.unwrap_err(), Error::ValidationError(_)),	38✔
427	)
428	}
429	}	100✔
430
431	#[test]
432	fn parser_fails_with_undefined_nonterminal() {	1✔
433	QuickCheck::new().tests(100).quickcheck(	1✔
434	prop_parser_fails_with_undefined_nonterminal as fn(GrammarWithUndefined) -> TestResult,	1✔
435	);
436	}	1✔
437
438	// Helper: Generate valid grammar with at least 2 productions
439	#[derive(Debug, Clone)]
440	struct ValidGrammarWithMultipleProductions(Grammar);
441	impl Arbitrary for ValidGrammarWithMultipleProductions {
442	fn arbitrary(g: &mut Gen) -> Self {	50✔
443	// Generate 2-5 nonterminals
444	let num_nonterms = usize::arbitrary(g) % 4 + 2;	50✔
445	let nonterms: Vec<String> = (0..num_nonterms).map(\|i\| format!("nt{}", i)).collect();	176✔
446
447	let mut productions = Vec::new();	50✔
448
449	for (idx, nt) in nonterms.iter().enumerate() {	176✔
450	let mut expressions = Vec::new();	176✔
451	let num_alternatives = usize::arbitrary(g) % 2 + 1;	176✔
452
453	for _ in 0..num_alternatives {	176✔
454	let mut terms = Vec::new();	263✔
455	let num_terms = usize::arbitrary(g) % 2 + 1;	263✔
456
457	for _ in 0..num_terms {	263✔
458	if bool::arbitrary(g) && idx > 0 {	394✔
459	// Reference a previously defined nonterminal
460	let ref_idx = usize::arbitrary(g) % idx;	144✔
461	if let Some(nt) = nonterms.get(ref_idx) {	144✔
462	terms.push(Term::Nonterminal(nt.clone()));	144✔
463	} else {	144✔
NEW 464	terms.push(Term::Terminal(String::arbitrary(g)));	×
NEW 465	}	×
466	} else {	250✔
467	terms.push(Term::Terminal(String::arbitrary(g)));	250✔
468	}	250✔
469	}
470
471	expressions.push(Expression::from_parts(terms));	263✔
472	}
473
474	productions.push(Production::from_parts(	176✔
475	Term::Nonterminal(nt.clone()),	176✔
476	expressions,	176✔
477	));
478	}
479
480	Self(Grammar::from_parts(productions))	50✔
481	}	50✔
482	}
483
484	// Property test: Parser results are identical regardless of production order
485	fn prop_parser_order_independent(grammar: ValidGrammarWithMultipleProductions) -> TestResult {	50✔
486	let grammar = grammar.0;	50✔
487
488	// Create a shuffled version of the grammar
489	let mut productions: Vec<_> = grammar.productions_iter().cloned().collect();	50✔
490	let mut rng = rand::rng();	50✔
491	rand::seq::SliceRandom::shuffle(productions.as_mut_slice(), &mut rng);	50✔
492
493	let grammar1 = grammar;	50✔
494	let grammar2 = Grammar::from_parts(productions);	50✔
495
496	let parser1 = match grammar1.build_parser() {	50✔
497	Ok(p) => p,	50✔
NEW 498	Err(_) => return TestResult::discard(),	×
499	};
500	let parser2 = match grammar2.build_parser() {	50✔
501	Ok(p) => p,	50✔
NEW 502	Err(_) => return TestResult::discard(),	×
503	};
504
505	// Get starting term from first grammar
506	let starting_term = match grammar1.starting_term() {	50✔
507	Some(t) => t,	50✔
NEW 508	None => return TestResult::discard(),	×
509	};
510
511	// Generate a test sentence
512	let sentence = match grammar1.generate() {	50✔
513	Ok(s) => s,	50✔
NEW 514	Err(_) => return TestResult::discard(),	×
515	};
516
517	// Parse with both parsers using explicit starting term
518	let parse_trees1: Vec<_> = parser1	50✔
519	.parse_input_starting_with(&sentence, starting_term)	50✔
520	.collect();	50✔
521	let parse_trees2: Vec<_> = parser2	50✔
522	.parse_input_starting_with(&sentence, starting_term)	50✔
523	.collect();	50✔
524
525	// Results should be identical
526	TestResult::from_bool(parse_trees1.len() == parse_trees2.len())	50✔
527	}	50✔
528
529	#[test]
530	fn parser_order_independent() {	1✔
531	QuickCheck::new().tests(50).quickcheck(	1✔
532	prop_parser_order_independent as fn(ValidGrammarWithMultipleProductions) -> TestResult,	1✔
533	);
534	}	1✔
535
536	// Property test: Parser can be reused multiple times with same results
537	fn prop_parser_reusable(grammar: SimpleValidGrammar) -> TestResult {	100✔
538	let grammar = grammar.0;	100✔
539
540	// Only test with grammars that can generate
541	if !grammar.terminates() {	100✔
NEW 542	return TestResult::discard();	×
543	}	100✔
544
545	let parser = match grammar.build_parser() {	100✔
546	Ok(p) => p,	100✔
NEW 547	Err(_) => return TestResult::discard(),	×
548	};
549
550	// Generate a sentence
551	let sentence = match grammar.generate() {	100✔
552	Ok(s) => s,	100✔
NEW 553	Err(_) => return TestResult::discard(),	×
554	};
555
556	// Parse the same sentence multiple times
557	let parse_trees1: Vec<_> = parser.parse_input(&sentence).collect();	100✔
558	let parse_trees2: Vec<_> = parser.parse_input(&sentence).collect();	100✔
559	let parse_trees3: Vec<_> = parser.parse_input(&sentence).collect();	100✔
560
561	// All results should be identical
562	TestResult::from_bool(	100✔
563	parse_trees1.len() == parse_trees2.len() && parse_trees2.len() == parse_trees3.len(),	100✔
564	)
565	}	100✔
566
567	#[test]
568	fn parser_reusable() {	1✔
569	QuickCheck::new()	1✔
570	.tests(100)	1✔
571	.quickcheck(prop_parser_reusable as fn(SimpleValidGrammar) -> TestResult);	1✔
572	}	1✔
573
574	// Property test: Parser validation catches all undefined nonterminals
575	// Simplified: Build grammars with known undefined nonterminals
576	fn prop_validation_catches_all_undefined(grammar: GrammarWithUndefined) -> TestResult {	100✔
577	let grammar = grammar.0;	100✔
578
579	// Collect all nonterminals defined in LHS
580	let mut defined = std::collections::HashSet::new();	100✔
581	for production in grammar.productions_iter() {	254✔
582	if let Term::Nonterminal(nt) = &production.lhs {	254✔
583	defined.insert(nt.clone());	254✔
584	}	254✔
585	}
586
587	// Collect all nonterminals used in RHS
588	let mut referenced = std::collections::HashSet::new();	100✔
589	for production in grammar.productions_iter() {	254✔
590	for expression in production.rhs_iter() {	382✔
591	for term in expression.terms_iter() {	574✔
592	if let Term::Nonterminal(nt) = term {	574✔
593	referenced.insert(nt.clone());	310✔
594	}	310✔
595	}
596	}
597	}
598
599	let undefined: Vec<_> = referenced.difference(&defined).cloned().collect();	100✔
600
601	let parser_result = grammar.build_parser();	100✔
602
603	match parser_result {	38✔
604	Ok(_) => {
605	// Parser succeeded, so there should be no undefined nonterminals
606	TestResult::from_bool(undefined.is_empty())	62✔
607	}
608	Err(Error::ValidationError(msg)) => {	38✔
609	// Parser failed, error message should mention all undefined nonterminals
610	let all_mentioned = undefined	38✔
611	.iter()	38✔
612	.all(\|nt\| msg.contains(&format!("<{nt}>")) \|\| msg.contains(nt));	44✔
613	TestResult::from_bool(!undefined.is_empty() && all_mentioned)	38✔
614	}
NEW 615	Err(_) => TestResult::error("Expected ValidationError"),	×
616	}
617	}	100✔
618
619	#[test]
620	fn validation_catches_all_undefined() {	1✔
621	QuickCheck::new().tests(100).quickcheck(	1✔
622	prop_validation_catches_all_undefined as fn(GrammarWithUndefined) -> TestResult,	1✔
623	);
624	}	1✔
625	}

shnewto / bnf / 21339734862

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous