21337753792

Committed 25 Jan 2026 06:52PM UTC coverage: 96.531% (-0.2%) from 96.753%

Build # 21337753792

Build Type

Pull #187

github

Committed by

web-flow

Commit Message

Merge 922532190 into fbcc780ec

Pull Request Pull Request #187: add explicit parser

Run Details

383 of 399 new or added lines in 4 files covered. (95.99%)

4 existing lines in 1 file now uncovered.

2421 of 2508 relevant lines covered (96.53%)

24364.03 hits per line

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

95.2

/src/parser/mod.rs

pub(crate) mod grammar;

use crate::ParseTree;
use crate::error::Error;
use crate::expression::Expression;
use crate::grammar::Grammar;
use crate::production::Production;
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, GrammarParser};
///
/// let grammar: Grammar = "<dna> ::= <base> | <base> <dna>
/// <base> ::= 'A' | 'C' | 'G' | 'T'"
///     .parse()
///     .unwrap();
///
/// let parser = GrammarParser::new(&grammar)?;
/// 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 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 = GrammarParser::new(&grammar);
        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 = GrammarParser::new(&grammar);
        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 = GrammarParser::new(&grammar).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 = GrammarParser::new(&grammar).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 = GrammarParser::new(&grammar).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 = GrammarParser::new(&grammar1).unwrap();
        let parser2 = GrammarParser::new(&grammar2).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 mut 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;
                            terms.push(Term::Nonterminal(nonterms[ref_idx].clone()));
                        } 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();
                            terms.push(Term::Nonterminal(nonterms[ref_idx].clone()));
                        } 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 = GrammarParser::new(&grammar);

        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;
                            terms.push(Term::Nonterminal(nonterms[ref_idx].clone()));
                        } 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 GrammarParser::new(&grammar1) {
            Ok(p) => p,
            Err(_) => return TestResult::discard(),
        };
        let parser2 = match GrammarParser::new(&grammar2) {
            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 GrammarParser::new(&grammar) {
            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 = GrammarParser::new(&grammar);

        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::expression::Expression;
6	use crate::grammar::Grammar;
7	use crate::production::Production;
8	use crate::term::Term;
9	use grammar::ParseGrammar;
10	use std::collections::HashSet;
11	use std::rc::Rc;
12
13	/// A reusable parser built from a `Grammar` that validates all nonterminals are defined
14	/// at construction time.
15	///
16	/// # Example
17	///
18	/// ```rust
19	/// use bnf::{Grammar, GrammarParser};
20	///
21	/// let grammar: Grammar = "<dna> ::= <base> \| <base> <dna>
22	/// <base> ::= 'A' \| 'C' \| 'G' \| 'T'"
23	/// .parse()
24	/// .unwrap();
25	///
26	/// let parser = GrammarParser::new(&grammar)?;
27	/// let parse_trees: Vec<_> = parser.parse_input("GATTACA").collect();
28	/// # Ok::<(), bnf::Error>(())
29	/// ```
30	#[derive(Debug)]
31	pub struct GrammarParser<'gram> {
32	starting_term: &'gram Term,
33	parse_grammar: Rc<ParseGrammar<'gram>>,
34	}
35
36	impl<'gram> GrammarParser<'gram> {
37	/// Construct a new `GrammarParser` from a `Grammar`, validating that all
38	/// nonterminals referenced in productions have definitions.
39	///
40	/// # Errors
41	///
42	/// Returns `Error::ValidationError` if any nonterminal used in the RHS of
43	/// productions lacks a definition in the grammar.
44	pub fn new(grammar: &'gram Grammar) -> Result<Self, Error> {	407✔
45	validate_nonterminals(grammar)?;	407✔
46	let starting_term = grammar.starting_term().ok_or_else(\|\| {	318✔
NEW 47	Error::ValidationError("Grammar must have at least one production".to_string())	×
NEW 48	})?;	×
49	let parse_grammar = Rc::new(ParseGrammar::new(grammar));	318✔
50	Ok(Self {	318✔
51	starting_term,	318✔
52	parse_grammar,	318✔
53	})	318✔
54	}	407✔
55
56	/// Parse an input string using the grammar's starting nonterminal.
57	///
58	/// Returns an iterator over all possible parse trees for the input.
59	pub fn parse_input(&self, input: &'gram str) -> impl Iterator<Item = ParseTree<'gram>> {	302✔
60	self.parse_input_starting_with(input, self.starting_term)	302✔
61	}	302✔
62
63	/// Parse an input string starting with the given term (nonterminal or terminal).
64	///
65	/// Returns an iterator over all possible parse trees for the input.
66	pub fn parse_input_starting_with(	406✔
67	&self,	406✔
68	input: &'gram str,	406✔
69	start: &'gram Term,	406✔
70	) -> impl Iterator<Item = ParseTree<'gram>> {	406✔
71	crate::earley::parse_starting_with_grammar(&self.parse_grammar, input, start)	406✔
72	}	406✔
73	}
74
75	/// Validate that all nonterminals referenced in the grammar have definitions.
76	///
77	/// # Errors
78	///
79	/// Returns `Error::ValidationError` with a message listing all undefined nonterminals.
80	fn validate_nonterminals(grammar: &Grammar) -> Result<(), Error> {	407✔
81	// Collect all nonterminals defined in LHS of productions
82	let mut defined_nonterminals = HashSet::new();	407✔
83	for production in grammar.productions_iter() {	1,149✔
84	if let Term::Nonterminal(ref nt) = production.lhs {	1,149✔
85	defined_nonterminals.insert(nt.clone());	1,149✔
86	}	1,149✔
87	}
88
89	// Collect all nonterminals used in RHS of all productions
90	let mut referenced_nonterminals = HashSet::new();	407✔
91	for production in grammar.productions_iter() {	1,149✔
92	for expression in production.rhs_iter() {	1,858✔
93	for term in expression.terms_iter() {	3,020✔
94	match term {	3,020✔
95	Term::Nonterminal(nt) => {	1,232✔
96	referenced_nonterminals.insert(nt.clone());	1,232✔
97	}	1,232✔
NEW 98	Term::AnonymousNonterminal(exprs) => {	×
99	// For anonymous nonterminals, check the expressions they contain
NEW 100	for expr in exprs {	×
NEW 101	for inner_term in expr.terms_iter() {	×
NEW 102	if let Term::Nonterminal(nt) = inner_term {	×
NEW 103	referenced_nonterminals.insert(nt.clone());	×
NEW 104	}	×
105	}
106	}
107	}
108	Term::Terminal(_) => {	1,788✔
109	// Terminals don't need definitions	1,788✔
110	}	1,788✔
111	}
112	}
113	}
114	}
115
116	// Find undefined nonterminals
117	let undefined: Vec<String> = referenced_nonterminals	407✔
118	.difference(&defined_nonterminals)	407✔
119	.cloned()	407✔
120	.collect();	407✔
121
122	if !undefined.is_empty() {	407✔
123	let message = format!(	89✔
124	"Undefined nonterminals: {}",
125	undefined	89✔
126	.iter()	89✔
127	.map(\|nt\| format!("<{nt}>"))	101✔
128	.collect::<Vec<_>>()	89✔
129	.join(", ")	89✔
130	);
131	return Err(Error::ValidationError(message));	89✔
132	}	318✔
133
134	Ok(())	318✔
135	}	407✔
136
137	#[cfg(test)]
138	mod tests {
139	use super::*;
140	use crate::Grammar;
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 = GrammarParser::new(&grammar);	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 = GrammarParser::new(&grammar);	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 = GrammarParser::new(&grammar).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 = GrammarParser::new(&grammar).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 = GrammarParser::new(&grammar).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 = GrammarParser::new(&grammar1).unwrap();	1✔
258	let parser2 = GrammarParser::new(&grammar2).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 mut nonterms: Vec<String> = (0..num_nonterms).map(\|i\| format!("nt{}", i)).collect();	276✔
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() {	276✔
293	let mut expressions = Vec::new();	276✔
294
295	// Each production has 1-3 alternatives
296	let num_alternatives = usize::arbitrary(g) % 3 + 1;	276✔
297	for _ in 0..num_alternatives {	276✔
298	let mut terms = Vec::new();	518✔
299
300	// Each alternative has 1-3 terms
301	let num_terms = usize::arbitrary(g) % 3 + 1;	518✔
302	for _ in 0..num_terms {	518✔
303	if bool::arbitrary(g) && idx > 0 {	1,007✔
304	// Reference a previously defined nonterminal	328✔
305	let ref_idx = usize::arbitrary(g) % idx;	328✔
306	terms.push(Term::Nonterminal(nonterms[ref_idx].clone()));	328✔
307	} else {	679✔
308	// Use a terminal	679✔
309	let term_str = String::arbitrary(g);	679✔
310	terms.push(Term::Terminal(term_str));	679✔
311	}	679✔
312	}
313
314	expressions.push(Expression::from_parts(terms));	518✔
315	}
316
317	productions.push(Production::from_parts(	276✔
318	Term::Nonterminal(nt.clone()),	276✔
319	expressions,	276✔
320	));
321	}
322
323	Self(Grammar::from_parts(productions))	100✔
324	}	100✔
325	}
326
327	// Helper: Generate grammar that may have undefined nonterminals
328	#[derive(Debug, Clone)]
329	struct GrammarWithUndefined(Grammar);
330	impl Arbitrary for GrammarWithUndefined {
331	fn arbitrary(g: &mut Gen) -> Self {	200✔
332	let num_nonterms = usize::arbitrary(g) % 4 + 1;	200✔
333	let mut nonterms: Vec<String> = (0..num_nonterms).map(\|i\| format!("nt{}", i)).collect();	531✔
334
335	// Add some undefined nonterminals
336	let num_undefined = usize::arbitrary(g) % 3;	200✔
337	for i in 0..num_undefined {	200✔
338	nonterms.push(format!("undefined{}", i));	189✔
339	}	189✔
340
341	let mut productions = Vec::new();	200✔
342	let defined_count = num_nonterms;	200✔
343
344	for (idx, nt) in nonterms.iter().enumerate() {	720✔
345	if idx >= defined_count {	720✔
346	// Don't define the undefined nonterminals
347	continue;	189✔
348	}	531✔
349
350	let mut expressions = Vec::new();	531✔
351	let num_alternatives = usize::arbitrary(g) % 2 + 1;	531✔
352
353	for _ in 0..num_alternatives {	531✔
354	let mut terms = Vec::new();	807✔
355	let num_terms = usize::arbitrary(g) % 2 + 1;	807✔
356
357	for _ in 0..num_terms {	807✔
358	if bool::arbitrary(g) && !nonterms.is_empty() {	1,217✔
359	// Reference any nonterminal (may be undefined)	622✔
360	let ref_idx = usize::arbitrary(g) % nonterms.len();	622✔
361	terms.push(Term::Nonterminal(nonterms[ref_idx].clone()));	622✔
362	} else {	622✔
363	terms.push(Term::Terminal(String::arbitrary(g)));	595✔
364	}	595✔
365	}
366
367	expressions.push(Expression::from_parts(terms));	807✔
368	}
369
370	productions.push(Production::from_parts(	531✔
371	Term::Nonterminal(nt.clone()),	531✔
372	expressions,	531✔
373	));
374	}
375
376	Self(Grammar::from_parts(productions))	200✔
377	}	200✔
378	}
379
380	// Property test: Parser construction fails if any nonterminal lacks definition
381	fn prop_parser_fails_with_undefined_nonterminal(grammar: GrammarWithUndefined) -> TestResult {	100✔
382	let grammar = grammar.0;	100✔
383
384	// Collect all nonterminals defined in LHS
385	let mut defined = std::collections::HashSet::new();	100✔
386	for production in grammar.productions_iter() {	259✔
387	if let Term::Nonterminal(nt) = &production.lhs {	259✔
388	defined.insert(nt.clone());	259✔
389	}	259✔
390	}
391
392	// Collect all nonterminals used in RHS
393	let mut referenced = std::collections::HashSet::new();	100✔
394	for production in grammar.productions_iter() {	259✔
395	for expression in production.rhs_iter() {	406✔
396	for term in expression.terms_iter() {	600✔
397	if let Term::Nonterminal(nt) = term {	600✔
398	referenced.insert(nt.clone());	287✔
399	}	313✔
400	}
401	}
402	}
403
404	// Find undefined nonterminals
405	let undefined: Vec<_> = referenced.difference(&defined).cloned().collect();	100✔
406
407	let parser_result = GrammarParser::new(&grammar);	100✔
408
409	if undefined.is_empty() {	100✔
410	// All nonterminals are defined, parser should succeed
411	TestResult::from_bool(parser_result.is_ok())	60✔
412	} else {
413	// Some nonterminals are undefined, parser should fail
414	TestResult::from_bool(	40✔
415	parser_result.is_err()	40✔
416	&& matches!(parser_result.unwrap_err(), Error::ValidationError(_)),	40✔
417	)
418	}
419	}	100✔
420
421	#[test]
422	fn parser_fails_with_undefined_nonterminal() {	1✔
423	QuickCheck::new().tests(100).quickcheck(	1✔
424	prop_parser_fails_with_undefined_nonterminal as fn(GrammarWithUndefined) -> TestResult,	1✔
425	);
426	}	1✔
427
428	// Helper: Generate valid grammar with at least 2 productions
429	#[derive(Debug, Clone)]
430	struct ValidGrammarWithMultipleProductions(Grammar);
431	impl Arbitrary for ValidGrammarWithMultipleProductions {
432	fn arbitrary(g: &mut Gen) -> Self {	50✔
433	// Generate 2-5 nonterminals
434	let num_nonterms = usize::arbitrary(g) % 4 + 2;	50✔
435	let nonterms: Vec<String> = (0..num_nonterms).map(\|i\| format!("nt{}", i)).collect();	164✔
436
437	let mut productions = Vec::new();	50✔
438
439	for (idx, nt) in nonterms.iter().enumerate() {	164✔
440	let mut expressions = Vec::new();	164✔
441	let num_alternatives = usize::arbitrary(g) % 2 + 1;	164✔
442
443	for _ in 0..num_alternatives {	164✔
444	let mut terms = Vec::new();	247✔
445	let num_terms = usize::arbitrary(g) % 2 + 1;	247✔
446
447	for _ in 0..num_terms {	247✔
448	if bool::arbitrary(g) && idx > 0 {	375✔
449	// Reference a previously defined nonterminal	130✔
450	let ref_idx = usize::arbitrary(g) % idx;	130✔
451	terms.push(Term::Nonterminal(nonterms[ref_idx].clone()));	130✔
452	} else {	245✔
453	terms.push(Term::Terminal(String::arbitrary(g)));	245✔
454	}	245✔
455	}
456
457	expressions.push(Expression::from_parts(terms));	247✔
458	}
459
460	productions.push(Production::from_parts(	164✔
461	Term::Nonterminal(nt.clone()),	164✔
462	expressions,	164✔
463	));
464	}
465
466	Self(Grammar::from_parts(productions))	50✔
467	}	50✔
468	}
469
470	// Property test: Parser results are identical regardless of production order
471	fn prop_parser_order_independent(grammar: ValidGrammarWithMultipleProductions) -> TestResult {	50✔
472	let grammar = grammar.0;	50✔
473
474	// Create a shuffled version of the grammar
475	let mut productions: Vec<_> = grammar.productions_iter().cloned().collect();	50✔
476	let mut rng = rand::rng();	50✔
477	rand::seq::SliceRandom::shuffle(productions.as_mut_slice(), &mut rng);	50✔
478
479	let grammar1 = grammar;	50✔
480	let grammar2 = Grammar::from_parts(productions);	50✔
481
482	let parser1 = match GrammarParser::new(&grammar1) {	50✔
483	Ok(p) => p,	50✔
NEW 484	Err(_) => return TestResult::discard(),	×
485	};
486	let parser2 = match GrammarParser::new(&grammar2) {	50✔
487	Ok(p) => p,	50✔
NEW 488	Err(_) => return TestResult::discard(),	×
489	};
490
491	// Get starting term from first grammar
492	let starting_term = match grammar1.starting_term() {	50✔
493	Some(t) => t,	50✔
NEW 494	None => return TestResult::discard(),	×
495	};
496
497	// Generate a test sentence
498	let sentence = match grammar1.generate() {	50✔
499	Ok(s) => s,	50✔
NEW 500	Err(_) => return TestResult::discard(),	×
501	};
502
503	// Parse with both parsers using explicit starting term
504	let parse_trees1: Vec<_> = parser1	50✔
505	.parse_input_starting_with(&sentence, starting_term)	50✔
506	.collect();	50✔
507	let parse_trees2: Vec<_> = parser2	50✔
508	.parse_input_starting_with(&sentence, starting_term)	50✔
509	.collect();	50✔
510
511	// Results should be identical
512	TestResult::from_bool(parse_trees1.len() == parse_trees2.len())	50✔
513	}	50✔
514
515	#[test]
516	fn parser_order_independent() {	1✔
517	QuickCheck::new().tests(50).quickcheck(	1✔
518	prop_parser_order_independent as fn(ValidGrammarWithMultipleProductions) -> TestResult,	1✔
519	);
520	}	1✔
521
522	// Property test: Parser can be reused multiple times with same results
523	fn prop_parser_reusable(grammar: SimpleValidGrammar) -> TestResult {	100✔
524	let grammar = grammar.0;	100✔
525
526	// Only test with grammars that can generate
527	if !grammar.terminates() {	100✔
NEW 528	return TestResult::discard();	×
529	}	100✔
530
531	let parser = match GrammarParser::new(&grammar) {	100✔
532	Ok(p) => p,	100✔
NEW 533	Err(_) => return TestResult::discard(),	×
534	};
535
536	// Generate a sentence
537	let sentence = match grammar.generate() {	100✔
538	Ok(s) => s,	100✔
NEW 539	Err(_) => return TestResult::discard(),	×
540	};
541
542	// Parse the same sentence multiple times
543	let parse_trees1: Vec<_> = parser.parse_input(&sentence).collect();	100✔
544	let parse_trees2: Vec<_> = parser.parse_input(&sentence).collect();	100✔
545	let parse_trees3: Vec<_> = parser.parse_input(&sentence).collect();	100✔
546
547	// All results should be identical
548	TestResult::from_bool(	100✔
549	parse_trees1.len() == parse_trees2.len() && parse_trees2.len() == parse_trees3.len(),	100✔
550	)
551	}	100✔
552
553	#[test]
554	fn parser_reusable() {	1✔
555	QuickCheck::new()	1✔
556	.tests(100)	1✔
557	.quickcheck(prop_parser_reusable as fn(SimpleValidGrammar) -> TestResult);	1✔
558	}	1✔
559
560	// Property test: Parser validation catches all undefined nonterminals
561	// Simplified: Build grammars with known undefined nonterminals
562	fn prop_validation_catches_all_undefined(grammar: GrammarWithUndefined) -> TestResult {	100✔
563	let grammar = grammar.0;	100✔
564
565	// Collect all nonterminals defined in LHS
566	let mut defined = std::collections::HashSet::new();	100✔
567	for production in grammar.productions_iter() {	272✔
568	if let Term::Nonterminal(nt) = &production.lhs {	272✔
569	defined.insert(nt.clone());	272✔
570	}	272✔
571	}
572
573	// Collect all nonterminals used in RHS
574	let mut referenced = std::collections::HashSet::new();	100✔
575	for production in grammar.productions_iter() {	272✔
576	for expression in production.rhs_iter() {	401✔
577	for term in expression.terms_iter() {	617✔
578	if let Term::Nonterminal(nt) = term {	617✔
579	referenced.insert(nt.clone());	335✔
580	}	335✔
581	}
582	}
583	}
584
585	let undefined: Vec<_> = referenced.difference(&defined).cloned().collect();	100✔
586
587	let parser_result = GrammarParser::new(&grammar);	100✔
588
589	match parser_result {	48✔
590	Ok(_) => {
591	// Parser succeeded, so there should be no undefined nonterminals
592	TestResult::from_bool(undefined.is_empty())	52✔
593	}
594	Err(Error::ValidationError(msg)) => {	48✔
595	// Parser failed, error message should mention all undefined nonterminals
596	let all_mentioned = undefined	48✔
597	.iter()	48✔
598	.all(\|nt\| msg.contains(&format!("<{nt}>")) \|\| msg.contains(nt));	54✔
599	TestResult::from_bool(!undefined.is_empty() && all_mentioned)	48✔
600	}
NEW 601	Err(_) => TestResult::error("Expected ValidationError"),	×
602	}
603	}	100✔
604
605	#[test]
606	fn validation_catches_all_undefined() {	1✔
607	QuickCheck::new().tests(100).quickcheck(	1✔
608	prop_validation_catches_all_undefined as fn(GrammarWithUndefined) -> TestResult,	1✔
609	);
610	}	1✔
611	}

shnewto / bnf / 21337753792

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