New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Feat/property tests from generate #27
Conversation
Prior to this commit the generate tests only generated one random grammar to parse per run. This commit revises the approach and instead uses the generate function as an arbitrary property to test the the Grammar::from_str functionality with.
tests/grammar.rs
Outdated
let meta_grammar = bnf::Grammar::from_str(&sentence.unwrap()); | ||
assert!(meta_grammar.is_ok()); | ||
impl Arbitrary for Meta { | ||
fn arbitrary<G: Gen>(_: &mut G) -> Meta { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
According to the quickcheck docs on its Arbitrary trait the provided Gen
should be used to generate the arbitrary test data. It also highlights the importance of being able to shrink the data to a minimal failing case. This implementation seems to violate both of these contraints
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
ahh, that's interesting, like maybe use that to seed random?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Yeah we really should be able to reproduce any failures. I'll look into using an approach that lets us provide the seed
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Seems like it. And that kind of control of generate
's random isn't public to integration tests like this. Do we make it public via another API? Do we move this property testing within the Grammar
module? Is it okay to ignore the "property" aspect of property based testing and only use it as a test runner than executes multiple times?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Shrinking a Grammar
seems involved. Seems like would have to keep the grammar in its full tree state and do some branch trimming/grafting.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Also, does the meta BNF grammar guarantee non-infinite grammars? Because otherwise this test occasionally fails when the generated grammar is unlucky enough to blow the stack
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I think if we're seeding then we only have to shrink on the seed. Like it's enough to reproduce to know if you seed with xyz you generate a fail case
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
It does seem like I'd taken for granted a step that should have property tests applied to it
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Maybe shrinking is overly complex for BNF and these tests just opt out? Once a failure, shrinking does nothing. As I read the quickcheck docs, that seems to be the default behavior, so maybe it is not important. The key point seems to be that the same Gen
needs to give the same test case.
tests/grammar.rs
Outdated
@@ -19,7 +19,7 @@ mod tests { | |||
<rule> ::= <opt-whitespace> \"<\" <rule-name> \">\" | |||
<opt-whitespace> \"::=\" <opt-whitespace> | |||
<expression> <line-end> | |||
<opt-whitespace> ::= \" \" <opt-whitespace> | \"\" | |||
<opt-whitespace> ::= \"\" | \" \" <opt-whitespace> |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I must be missing something. Does this just swap the expression order?
tests/grammar.rs
Outdated
@@ -19,7 +19,7 @@ mod tests { | |||
<rule> ::= <opt-whitespace> \"<\" <rule-name> \">\" | |||
<opt-whitespace> \"::=\" <opt-whitespace> | |||
<expression> <line-end> | |||
<opt-whitespace> ::= \"\" | \" \" <opt-whitespace> | |||
<opt-whitespace> ::= \"\" | \" \" |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Does this change the meta BNF grammar to only generate grammars with 0 or 1 space between the <rule-name>
and ::=
? I thought it was legal to have more than 1.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Yeah it does, I'm not sure it's something we should remove if we don't have to, it was just the likely candidate for a lot of recursion and I wanted to see if things all built without it
Some revision needs to happen to allow |
2 similar comments
src/grammar.rs
Outdated
@@ -92,8 +92,8 @@ impl Grammar { | |||
|
|||
let expression; | |||
let expressions = production.rhs_iter().collect::<Vec<&Expression>>(); | |||
|
|||
match thread_rng().choose(&expressions) { | |||
|
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
is github lying about this whitespace?
@@ -104,7 +104,7 @@ impl Grammar { | |||
|
|||
let mut result = String::new(); | |||
for term in expression.terms_iter() { | |||
match self.eval_terminal(&term) { | |||
match self.eval_terminal(&term, rng) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Does this mean each term gets its own copy of the StdRng
? Seems strange for each term to essentially be given the same seed, or does it do something else?
src/grammar.rs
Outdated
@@ -137,7 +142,7 @@ impl Grammar { | |||
/// # assert!(sentence_clone.is_ok()); | |||
/// } | |||
/// ``` | |||
pub fn generate(&self) -> Result<String, Error> { | |||
pub fn generate_seeded(&self, rng: StdRng) -> Result<String, Error> { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Related to my previous comment, does this have to take ownership of the StdRng
or could it work with a mutable reference?
Prior to this commit the BNF for BNF had a rule that catered to deep recursion without, to me, adding any real value as sensical syntax despite that it is how the wikipedia source defines the grammar. Although the revision to the gramamr makes our failure case much less likely, I also added some logic to allow the stack to grow for deep recursion in order to give grammars that might require it more room to generate. The fact that ours had failed with regularity made me think there is a use case for allowing more stack within a threshold. That threshold is exercised by our `infinite_loop` test.
…nd use quickcheck default
Is your |
ha no the VS code started crashing my computer so I disabled it. That's a bummer about formatting, I can manually run |
I'd like to revise the grammar property tests to handle the excessive recursion potential as well as factor out the logic to potentially grow the stack to account for that heavy recursion. |
This commit contains a few revisions. First, a new error kind was introduced to indicate that the generation error isn't generic but the result of the limits of recursion being reached. This allows the property tests for the Grammar type to disregard problematic sentence generation, it is testing that what it gets is parsable. In order to manage meeting recursion limits being met in the property tests, a new use case was accounted for, one that I belive implementaion for is useful. Logic was added to allow the "from_str" trait for bnf types to be parallel to Type::new() in all cases except the Term type. Because the Term type does not have a sensical way to implement new(), "from_str" for Term types corresponds to a Terminal rule for the empty string which is allowed in parsable gramamrs. As this commit represents that addition of a new error kind it seemed that there is enough variety now to make our Error type public in order for users can match on them.
src/expression.rs
Outdated
@@ -25,6 +25,9 @@ impl Expression { | |||
|
|||
// Get `Expression` by parsing a string | |||
pub fn from_str(s: &str) -> Result<Self, Error> { | |||
if s.len() == 0 { | |||
return Ok(Expression::new()); | |||
} |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Does the expression parser not handle end of input? This special case separation between parser and from_str behavior seems strange.
src/grammar.rs
Outdated
// match sentence.unwrap() { | ||
// Error::RecursionLimit(_) => (), | ||
// e => panic!("should should be Error::RecursionLimit: {:?}", e), | ||
// } |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Vestigial code?
src/term.rs
Outdated
@@ -14,6 +14,12 @@ pub enum Term { | |||
impl Term { | |||
// Get `Term` by parsing a string | |||
pub fn from_str(s: &str) -> Result<Self, Error> { | |||
// this is a little weird, should we default to Nonterminal? | |||
// Seems like empty would correspond to a terminal that represents | |||
// the empty string. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I agree with this comment. Not sure if you meant this as an actual question for me to be removed later or if the doubt is something you would like to keep in comments
Feat/property tests from generate
Revised generate test.
Prior to this commit the generate tests only generated one
random grammar to parse per run. This commit revises the approach
and instead uses the generate function as an arbitrary property
to test the the Grammar::from_str functionality with.
Additions relevant to the reopening of this PR:
First, a new error kind was introduced to indicate that
the generation error isn't generic but the result of the
limits of recursion being reached. This allows the
property tests for the Grammar type to disregard problematic
sentence generation, it is testing that what it gets is parsable.
In order to manage meeting recursion limits being met in the
property tests, a new use case was accounted for, one that I
belive implementaion for is useful. Logic was added to allow the
"from_str" trait for bnf types to be parallel to Type::new()
in all cases except the Term type. Because the Term type does
not have a sensical way to implement new(), "from_str" for Term
types corresponds to a Terminal rule for the empty string
which is allowed in parsable gramamrs.
As this commit represents that addition of a new error kind
it seemed that there is enough variety now to make our Error
type public in order for users can match on them.