spotifyovercastrssapple-podcasts

elm-test v2 with Martin Janiczek

Martin Janiczek joins us to talk about fuzz testing, why it matters, and how the upcoming elm-test v2 changes the way you write fuzzers in Elm.
August 1, 2022
#62

Transcript

[00:00:00]
Hello Jeroen. Hello Dillon.
[00:00:03]
Did you feel like something was missing last episode?
[00:00:06]
Yeah, like, it was a nice episode, but it felt like we didn't have like a, what do you call it? A Martin.
[00:00:13]
A Martin! Exactly! Hey, wouldn't it be nice? Actually, we've got another Martin here today. Martin Janacek back with us again. Thanks so much for coming back on, Martin.
[00:00:23]
Hey there, hello. Nice to be back here.
[00:00:25]
So soon. Ready for another Martin episode. Let's do it.
[00:00:29]
Yeah, well, thanks for joining us. And so you've been hard at work for a while on this pretty ambitious project, getting a new fuzzing approach in the Elm testing library.
[00:00:45]
So first of all, congratulations on getting like completing the project and getting that merged in. That is quite ambitious and impressive.
[00:00:53]
Yeah, thank you. It is quite a good feeling to finish a project because I have so many unfinished projects.
[00:01:03]
Yeah, and that's a lot of coordination to like actually convince people that this is like a good official approach to switch over to.
[00:01:14]
And, you know, I mean, so this fuzzing approach, like there's like a lot of interesting theory behind it that you had to really, I think, do a lot of reading about to compare these different approaches.
[00:01:28]
And but yeah, it's a really fascinating idea. So, yeah, great, great job on that.
[00:01:33]
Well, we did talk about fuzzing in the episode dedicated to Elm tests, but would you like us to, but could you explain what fuzzing is again?
[00:01:43]
I think what you're trying to say, Jeroen, is that your memory is a little fuzzy on that.
[00:01:51]
There it is. Yeah, sure. I can definitely try to describe fuzzing and why use it and so on.
[00:02:01]
So I think I think of fuzz tests or as it's more well known in the functional programming world as property based tests.
[00:02:14]
I think of them as like a continuation of the line from unit tests through parameterized tests to to infinity.
[00:02:24]
So let me explain that. So unit tests usually have just like one example, right?
[00:02:30]
You hard coded one value and you are trying to assert something about it.
[00:02:36]
Either you are trying to check the result of calling a function with like equals, right?
[00:02:42]
So adding one to three is four or you are trying to learn something else about it.
[00:02:49]
Let's say, I don't know, like multiplying by two makes it even or something like that.
[00:02:54]
So it doesn't have to be a value that you like an output value that you want to check against.
[00:03:00]
But you you usually have one specific input example that you are trying to test.
[00:03:07]
Then the next step is parameterized tests.
[00:03:12]
So you could think of them as a list of tuples, let's say.
[00:03:17]
So list of inputs and their corresponding outputs.
[00:03:21]
And so that's usually helpful. In my experience, it's helpful with parsers because it's hard to stay sane and like have everything nailed down when you are creating a parser for some language.
[00:03:38]
So that's I think those tests definitely speak the most to me about like why tests are good.
[00:03:46]
Because I just want to make sure that I didn't break something when trying to implement this new feature.
[00:03:53]
So parameterized tests are a great way to just check the same property or check the function in the same way with lots of different examples, lots of different hardcoded inputs.
[00:04:06]
And then just to clarify, Elm test does not have support for parameterized tests, but you can emulate it using like list on map.
[00:04:16]
Exactly.
[00:04:18]
Yeah. So you would have a list of these inputs and outputs and you would just pass it to list map.
[00:04:26]
You would create tests out of that and you would just give them to test.describe or test.concat or something.
[00:04:36]
Describe. Describe.
[00:04:38]
Yeah, test.describe.
[00:04:40]
Yeah, you can still do it in Elm even though it doesn't have this kind of like annotation style that let's say Java JUnit has and so on.
[00:04:51]
What's nice about parameterized tests is that when you specify more inputs, so if your function has, let's say, three arguments and you have tables for each of these, you get all the combinations, right?
[00:05:06]
So it's a nice way to cover a lot of area quickly.
[00:05:13]
But all of these, like unit tests and parameterized tests, they have the problem of only checking what you can think about, right?
[00:05:27]
So you know about edge cases like zero and minus one and so on, but perhaps you didn't think about what happens with max integer or something.
[00:05:38]
So that's what property based tests or fast tests as Elm calls them.
[00:05:46]
That's what those are really good about because they generate the inputs randomly.
[00:05:51]
And so that's nice, but it has its own issues, right?
[00:05:58]
Because if you can't hard code the inputs, suddenly you can't hard code the outputs either.
[00:06:06]
So it can't be just a simple input transform, expect equals some output because it's random.
[00:06:15]
So you can't really do that.
[00:06:17]
And so you need to change your thinking a little bit about it.
[00:06:21]
You need to change your mindset and you need to go more general.
[00:06:26]
So instead of just checking for equals, let's say you have to think about what invariants does your function, what invariants hold for your function?
[00:06:42]
Which properties hold for it?
[00:06:43]
Yeah, which properties?
[00:06:45]
What is always true, right?
[00:06:46]
No matter what input is going to be there.
[00:06:49]
And so suddenly, let's say if I, this is really like insultingly stupid example, but for the add function, you would want to check that a plus b is the same as b plus a.
[00:07:04]
You would want to check that zero plus anything equals that something, right?
[00:07:09]
That you gave it.
[00:07:10]
And so there are these like laws, mathematical laws that you have for addition that you can check with random integers.
[00:07:18]
And in a similar vein, there are different other properties that you can check for.
[00:07:25]
Let's say JSON encoders and decoders, they are each other's inverses.
[00:07:30]
So you can do that kind of round trip where you generate the value, encode it, decode it and check that is the same, right?
[00:07:37]
That you didn't lose any kind of data.
[00:07:39]
And so there's a lot of these properties that you can check, but it's definitely shift in your mindset.
[00:07:46]
So it may not come to you as easily as just writing unit tests.
[00:07:52]
Yeah, definitely.
[00:07:52]
It definitely seems like a different workflow because this test driven development approach is so based on like fake it till you make it, hard coding something.
[00:08:03]
You know, you say I expect, you know, this function to combine parts of a URL path.
[00:08:11]
And when I have this input, this is the output and then you hard code the function to return that output.
[00:08:18]
And now it's green.
[00:08:19]
And then you you go case by case with with specific concrete hard coded cases, hard coding pieces of it into the implementation.
[00:08:28]
That's like the TDD, the classic TDD approach.
[00:08:32]
So how does it change the workflow if you're doing like TDD with fuzzing?
[00:08:39]
Or is it just a separate workflow?
[00:08:41]
Right.
[00:08:42]
I'm not really sure myself if it's still TDD because in your example, as you said, you hard code the output into the implementation because that's the easiest way to get the test green.
[00:08:57]
Right.
[00:08:58]
And then you have three of those examples and it just becomes like if this then that, if this and that else is this third answer.
[00:09:05]
And it could go infinitely long.
[00:09:08]
Right. You could have like 20 inputs in your test and then you make like switch with 20 cases in the implementation.
[00:09:18]
And that's not what you want.
[00:09:19]
Right. So there needs to be a moment where you switch and say, OK, it's actually easier to do the right thing.
[00:09:27]
Right. And do the actual implementation.
[00:09:29]
And I feel like when you add the fuzz tests into the mix, if you say, let's say, let's say A plus B equals B plus A.
[00:09:39]
And let's say the associativity law, like A plus B plus C in parenthesis equals A plus B in parenthesis plus C and so on.
[00:09:50]
If you add all of these laws, you kind of define how the implementation should behave.
[00:09:59]
And suddenly, because the tests are random, you have no way of keeping that switch statement or like the case of statement in case of L.
[00:10:08]
Right. You have no way of keeping that implementation because the values, the inputs are going to be random each time.
[00:10:16]
And so either you just, you know, you have to give up on that lazy implementation mindset in a way.
[00:10:25]
And so I think it kind of forces you to go to do like, OK, let's let's do the actual implementation step.
[00:10:35]
If you add fuzz tests in there, you just have to do the right thing.
[00:10:40]
Do you typically do it in your workflow as like, you know, as you're building the implementation, driving the tests in this TDD style?
[00:10:50]
Or do you typically do fuzz testing after as a like, let's make sure we covered all the cases?
[00:10:57]
Yeah, I usually do my tests after, but it might not be.
[00:11:04]
It might be just because I am not very principled TDD practitioner.
[00:11:10]
So what about for vanilla unit tests?
[00:11:13]
Do you do do you do those first or I do streams where you do them first?
[00:11:19]
Yeah, but it's that's mostly for like Advent of Code and nice, simple examples like that.
[00:11:27]
Yeah, yeah. It's honestly it's not how I do stuff at work.
[00:11:32]
Yeah, so so far, I don't know if it's really nice because they give you the test cases right away.
[00:11:36]
Right. So it's it's nice to just put them in and check the correctness of your solution early.
[00:11:44]
But usually I am not so principled about it and I just write my implementation and write tests afterwards.
[00:11:53]
I realize that my code might be much better and cleaner and like more testable if I start with tests.
[00:12:02]
So that's something I try to do. But even for unit tests, I usually do them after.
[00:12:07]
OK, I see. I wonder because I have to say I do not I do not do very much fuzz testing.
[00:12:15]
And but my instinct is that I would probably do fuzz testing after, whereas I like to do
[00:12:26]
regular unit testing, driving the implementation.
[00:12:30]
But yeah, and it seems to be the sweet spot, I think.
[00:12:34]
Yeah, that's where I would like to get.
[00:12:36]
Yeah, I think I would do the same. It also kind of feels like when you fake it until you make it,
[00:12:42]
you hard code everything. Well, the unit test is still a hard version.
[00:12:48]
Right. And then you end up with the fuzz test. That is the real one.
[00:12:52]
Oh, interesting. I see. So you're saying you could like generalize your unit test,
[00:12:58]
start with like the unit test being the hard coded one.
[00:13:00]
And then the fuzz version would be generalizing that.
[00:13:04]
Yeah, that's a cool idea. I like that.
[00:13:07]
In a way, you could say you're not done until you have done fuzz testing.
[00:13:10]
But I mean, fuzz testing is not what you always will end up with. So that's not entirely true.
[00:13:18]
There are applications and there are places where unit tests are more appropriate.
[00:13:23]
But it's, you know, you can have both. And unit tests are great for understanding.
[00:13:28]
Let's say you have a new colleague and they look at the test and suddenly they see
[00:13:33]
how you are using your functions and so on.
[00:13:35]
And property based tests are more for getting the confidence that your functions are really correct.
[00:13:45]
Right. It approaches a proof, right? It approaches a proof as your sample size approaches infinity.
[00:13:51]
So it's and since it's random.
[00:13:54]
Yeah, I think it was Dijkstra who said that tests can only prove that there's a bug,
[00:14:02]
but they cannot prove that there's no bugs. Right.
[00:14:05]
I'm not sure of the correct wording, but that's the gist of it.
[00:14:09]
And yeah, so you can almost infinitely increase your confidence, but you can never get there.
[00:14:17]
That's where like formal methods come in and proofs and so on.
[00:14:21]
Type checkers, static analysis.
[00:14:24]
Definitely.
[00:14:27]
It definitely feels like it's more in the category of proofs.
[00:14:31]
Than just tests.
[00:14:35]
I will say like when I've coached people on these incremental approaches to writing code,
[00:14:41]
which I think hopefully people think of me as a broken record talking about incremental things.
[00:14:50]
If so, then I've achieved my mission, which is to...
[00:14:54]
You might be broken, but at least you're immutable.
[00:14:56]
No record updates for me.
[00:14:58]
Exactly.
[00:15:00]
But when I'm coaching people and like doing a TDD example, like one of the things I notice is that
[00:15:07]
people want to jump to the generalized implementation first.
[00:15:11]
And I want to untrain that habit of trying to go straight to the generalized solution
[00:15:19]
and instead say, let's talk about one case at a time, because I think our brains are actually
[00:15:23]
more effective at thinking about one case and building code for one case.
[00:15:29]
Otherwise we overengineer and our brain gets overwhelmed.
[00:15:32]
It's like too large of a problem to bite off at once.
[00:15:35]
So it gives us these manageable incremental chunks to work on.
[00:15:40]
So I definitely think there's like value to this TDD approach.
[00:15:45]
And I definitely like the idea of doing fuzzing after.
[00:15:48]
And I think that's a great way to do it.
[00:15:51]
And I think it's good for people to keep in mind that like balancing that incremental
[00:15:57]
approach with the fuzzing, which will pull you more in the generalized implementation direction.
[00:16:04]
Also, now that you talk about it, I think fuzzing is great for when you can't hold
[00:16:11]
the whole state in your head when there's too many options.
[00:16:15]
So this is more for, let's say application state and messages.
[00:16:19]
So, you want to make sure that no matter what messages you get,
[00:16:25]
something will always be true because you can't really think through it.
[00:16:30]
One example that I am now thinking of is the text editor, like Elm editor that I tried to make,
[00:16:39]
which was totally from scratch, no text area, no custom JavaScript.
[00:16:44]
So it was just like each character was its own thing.
[00:16:48]
Each character was its own div and all the cursor manipulation and selection.
[00:16:54]
It was all done from scratch.
[00:16:56]
And so there were a lot of situations where I thought the implementation is correct because
[00:17:04]
the way that I tested the application, everything seemed to be fine.
[00:17:11]
So if I am on the last line and I click the down arrow, it should move me to the end of
[00:17:19]
the line, right?
[00:17:20]
It shouldn't move it down because there's no other line.
[00:17:23]
This was the last one.
[00:17:24]
And all these cases, I could think of some, but I had no idea if that's all of them or
[00:17:31]
if there is some behavior that I am forgetting.
[00:17:33]
And so what property based tests were really good about was saying no matter what happens,
[00:17:42]
no matter what keys I press, no matter what selection is currently active, no matter where
[00:17:48]
a cursor is, if I do this, this will happen, right?
[00:17:52]
And so it was great letting the computer just throw random messages at it and tell me,
[00:18:01]
hey, no, if you do, I don't know, up arrow, down arrow, left arrow, this happens.
[00:18:09]
And you said it shouldn't, right?
[00:18:10]
And I wouldn't have thought of that example.
[00:18:12]
So I think really fast tests are great after the fact, after you implement your program.
[00:18:20]
Yeah.
[00:18:21]
It's really nice that you write these unit tests and the fastest almost the same way,
[00:18:27]
especially in the same tool, because you can switch from one to the other much easier than
[00:18:31]
if you had to write a end to end test, for instance, where you go for Cypress or Puppeteer.
[00:18:37]
Like, okay, now you have to write everything in a different language and using a different
[00:18:44]
framework.
[00:18:45]
But here's just like a few characters, few lines of change and you're good.
[00:18:49]
Yep.
[00:18:50]
Yeah.
[00:18:50]
I need to dust off this branch I have.
[00:18:55]
But I've got a branch in my LMarkdown parser that the parser, in Markdown, there's no such
[00:19:04]
thing as invalid Markdown.
[00:19:06]
It's just Markdown that won't have the effect you expected.
[00:19:12]
An incomplete link in Markdown is just plain text, but it's not invalid Markdown.
[00:19:20]
So I have a fuzz test that you throw any random string at it and there should be nothing that
[00:19:28]
has an Elm parser error.
[00:19:30]
Right.
[00:19:31]
That's a pretty straightforward, just throw a lot of input at it.
[00:19:34]
You can imagine sort of doing it in a little bit of a more sophisticated way where you
[00:19:41]
try to construct more meaningful inputs that might be better at fleshing out.
[00:19:46]
You can increase the chance of something weird happening.
[00:19:51]
Yeah.
[00:19:51]
Right.
[00:19:52]
If you know what to look for.
[00:19:54]
If you know, right, exactly.
[00:19:55]
But at the same time, you could also bias it towards the things you're already looking
[00:19:59]
for, which you're trying to avoid.
[00:20:02]
So, I mean, I guess you could do both.
[00:20:04]
You could say, here's just a totally random string.
[00:20:08]
And then you could have another fuzz test that says, here is a set of known characters
[00:20:14]
that could cause problems in unfinished HTML tag, unfinished link tag.
[00:20:20]
Yeah.
[00:20:20]
Yeah.
[00:20:21]
And we have tools for that, right?
[00:20:23]
We do have like this one of function and it's like derivatives like frequencies and weighted
[00:20:30]
and however those are called where you can say, OK, 90% of the time give me this random
[00:20:37]
string and 10% of the time give me this like carefully constructed, like tricky string.
[00:20:45]
And you can switch the weights.
[00:20:49]
You can change that.
[00:20:51]
You know, something is you can switch the weights and you can find a balance where it's
[00:20:58]
doing useful work, but you can still be sure that it will try all the crazy random things
[00:21:05]
that you didn't think of with the totally random, uniformly random string.
[00:21:10]
Yeah.
[00:21:11]
How much confidence do you have that fuzz test will discover something if there is something
[00:21:17]
to be found?
[00:21:18]
Because I think by default, they run like 100 different inputs.
[00:21:23]
So for instance, for finding errors in a mock down parser, like Shirk will find something
[00:21:29]
sometimes, but hundreds might be low.
[00:21:34]
So you might not trust it in the first run at least.
[00:21:37]
Yeah.
[00:21:38]
Yeah.
[00:21:39]
100 might be a little bit too low for that markdown example because strings are like
[00:21:43]
collections and or at least with total random string generator, 100 might be too little.
[00:21:50]
But if you had this kind of like, let's create my string from like, this is a normal world.
[00:21:58]
This is a link.
[00:21:59]
This is, you know, with missing parentheses and like all these different stuff where these
[00:22:05]
chunks are bigger, then you might cover the space better.
[00:22:11]
And so you might need less tests, but definitely depending on what you are testing, you can
[00:22:17]
say, okay, let's run these fuzz tests.
[00:22:20]
You know, let's run a million of them instead of 100.
[00:22:24]
Right.
[00:22:25]
And some people, this is now going into like testing and trying to break C programs, libraries
[00:22:33]
like PNG libraries and so on.
[00:22:36]
People do keep running them nonstop, right?
[00:22:41]
They run them 24 seven and every now and then, you know, it finds something.
[00:22:47]
So this possibly something we could do with elntest, like let it run for a specified amount
[00:22:53]
of time or let it run indefinitely instead of just saying, here's, you know, try 100
[00:23:00]
times and then stop.
[00:23:02]
Yeah.
[00:23:03]
So you can choose how many monkeys you want and what these monkeys can write.
[00:23:08]
Yeah, exactly.
[00:23:11]
Yeah.
[00:23:11]
And you're like, oh no, they wrote Harry Potter again.
[00:23:13]
We have to throw it out.
[00:23:18]
Yeah.
[00:23:19]
I think this is a very interesting topic of how you produce inputs that essentially meaningfully
[00:23:26]
represent the cases that you want to be testing.
[00:23:29]
Because I mean, in the case of the markdown input, you're actually probably going to have
[00:23:35]
an overrepresentation of, for example, cases with without matching closing tags, right?
[00:23:42]
Because the odds of getting a valid matching closing tag is very low.
[00:23:47]
That's going to produce a certain class of errors more.
[00:23:50]
It's going to represent that class of errors more.
[00:23:52]
But maybe there's a class of errors where you have a valid matching tag, but within
[00:23:59]
that there's an invalid one.
[00:24:00]
Or maybe there's a, you know, maybe there's something meaningful that happens when you
[00:24:04]
do nesting.
[00:24:05]
Maybe there's something meaningful that happens when you have something within a block quote,
[00:24:10]
which you can have all sorts of nested, these nested markdown block structures that can
[00:24:16]
have other markdown within them, which can have other markdown within them.
[00:24:20]
You're not going to represent those cases, which means you are looking at more of a monkey
[00:24:27]
typing Shakespeare situation where sure, theoretically, you're representing that input
[00:24:34]
because you're representing an infinite space that's not constrained.
[00:24:37]
But realistically, statistically, you're not representing that well enough to trust that
[00:24:45]
you're getting coverage of that case.
[00:24:47]
Yeah, I think what might work really well in that case is, well, not going with total
[00:24:54]
random string, not going with valid SAT that you would convert to string and then test,
[00:25:01]
but going in the middle in like the tokens.
[00:25:05]
Right.
[00:25:06]
So from implementing the parser, you know that, let's say left brace or the left square
[00:25:13]
bracket, those are special or indentation is special or the exclamation mark is special.
[00:25:20]
And so you can use those weights in the one of function.
[00:25:27]
You can tweak that and you can say, OK, let's try what happens if I have an image tag and
[00:25:35]
inside is something else.
[00:25:36]
Right.
[00:25:36]
So you can say with probability this and that, generate a string that is those tokens.
[00:25:45]
So like exclamation mark, square bracket, something in them, then open question, then
[00:25:53]
open parenthesis and try to run the whole thing again inside.
[00:25:58]
Right.
[00:25:58]
So you can try to create these cases.
[00:26:02]
You can try to go based on the tokens.
[00:26:06]
So the tokens are a little bit like bigger unit than just a character.
[00:26:10]
But suddenly you are trying the interesting stuff more often than just, let's say, alphabetical
[00:26:19]
characters because those do not.
[00:26:21]
Yeah, it seems like there are a lot of approaches you could use.
[00:26:23]
Like another one that comes to mind is you could, you know, if you construct the input
[00:26:30]
from an AST, then you know you're constructing valid input and you turn that into a string.
[00:26:35]
I mean, obviously, you know, you could do the reversible approach.
[00:26:40]
Reversible is always an interesting thing to try with fuzzing if there is such a concept
[00:26:46]
in the problem you're looking at.
[00:26:48]
But beyond like reversible, you can take a build a random AST.
[00:26:55]
You can wait certain things that, you know, to make sure there's an even distribution
[00:27:00]
of like things like nesting, for example.
[00:27:03]
And then you could go and change random characters or you could change, you could look for specific
[00:27:08]
characters that have meaning and either add or remove them.
[00:27:12]
That's another thing that might bring out some interesting cases.
[00:27:17]
And of course, you could just go and build your own totally custom generator that's going
[00:27:22]
to build up inputs that represent these different cases.
[00:27:26]
Yeah, exactly.
[00:27:28]
All right.
[00:27:29]
I feel like we've talked about fuzz testing in general.
[00:27:33]
I think people know what they are.
[00:27:36]
Should we talk about what you've done, Martin?
[00:27:39]
Like what is new in your implementation?
[00:27:43]
What is different?
[00:27:44]
All right.
[00:27:45]
Yeah.
[00:27:45]
So my changes to elm test and what's going to come out in elm test v2 is a re implementation
[00:27:56]
of the shrinking process.
[00:27:58]
So just to quickly summarize it, elm test will generate random inputs to your function.
[00:28:06]
And if it finds that input fails the test, it will try to simplify it.
[00:28:11]
Right.
[00:28:12]
So it might turn 512, it might turn it into zero or it might divide it by two.
[00:28:21]
It might subtract one from it.
[00:28:23]
It just tries to make it smaller somehow or simpler.
[00:28:26]
And there...
[00:28:28]
If your sorting function fails on a list with a thousand items, but it also fails to sort
[00:28:37]
correctly on a list, there's an input with two items that also fails.
[00:28:42]
You don't want your error message to say, hey, I found a failing example.
[00:28:45]
You want it to show you the simplest example.
[00:28:47]
It can show you the fails.
[00:28:49]
Yeah.
[00:28:49]
It's not very helpful if it gives you something that takes two screens just to base the value.
[00:28:54]
Right.
[00:28:55]
So definitely...
[00:28:56]
Thank you, elm test.
[00:28:59]
Yeah.
[00:29:00]
Like, I guess this is wrong.
[00:29:01]
Okay.
[00:29:02]
But it's really like when you see a failure from a property based test and it is shrunk
[00:29:11]
down to its minimal failing value, a lot of the times the bug is obvious, right?
[00:29:17]
Because you see, oh, like that's, that's that.
[00:29:21]
Because it is small and you can kind of like guess as to what happens.
[00:29:25]
But if really, if it's like, let's say for my editor, if it's a list of 500 messages,
[00:29:33]
I have no idea which of these are just like fluff and which of these are really important.
[00:29:39]
And similarly for the margramparcer, you could have a huge string, huge document and somewhere
[00:29:45]
in there is going to be the failing part.
[00:29:48]
Like let's say the image tag that is not closed or something.
[00:29:51]
And if the shrinker can remove everything else and just give you that image tag, that's
[00:29:58]
going to be much clearer for you.
[00:30:00]
And so we do this shrinking process and there are two ways, or at least in the currently
[00:30:10]
known open source world, there are two ways to do shrinking and we are using one of them.
[00:30:15]
And it has some, it has some problems.
[00:30:18]
When you say we.
[00:30:19]
Do you mean?
[00:30:21]
Elm test.
[00:30:23]
The current Elm test.
[00:30:25]
Yeah, right.
[00:30:25]
The current Elm test, let's say Elm test v1 is using value based shrinking.
[00:30:31]
So let's, let's name those two approaches.
[00:30:34]
Value based shrinking kind of knows how to shrink a value, but it doesn't know any kind
[00:30:40]
of context about it.
[00:30:42]
And so you could think about it as function from the value, let's say from integer to
[00:30:48]
many possible ways, how to make it smaller.
[00:30:51]
So from integer to a list of integers.
[00:30:54]
So giving that shrink integer function five would give you a list with four zero two,
[00:31:02]
things like that.
[00:31:04]
And when you say that it needs to return a list of integers, those are the list of things
[00:31:10]
to try out the list of possible simplifications.
[00:31:13]
Because you can simplify things in different ways.
[00:31:16]
Yes.
[00:31:18]
Yes.
[00:31:18]
You want it to represent like zeroness is an interesting thing to shrink and evenness
[00:31:25]
is an interesting thing to shrink.
[00:31:26]
So, so two and zero are meaningful and smaller numbers.
[00:31:30]
So they would be interesting to shrink.
[00:31:33]
It's I wouldn't say it's, it's about evenness, but it's just trying to make the values simpler
[00:31:42]
in some way.
[00:31:43]
So for integers, it might, you know, you might try to shrink to zero.
[00:31:47]
You might try to shrink to some negative number for strings.
[00:31:51]
You might change the character from B to A, or you might also just make the string shorter.
[00:31:58]
Right.
[00:31:58]
And for different types, the way to shrink the type will be different.
[00:32:05]
But it starts with random, right?
[00:32:08]
This, this value based or type based shrinking approach, it says, here's a random value I'm
[00:32:14]
starting with.
[00:32:15]
Now, let me, once I find a failing case, let me see if I can create another failing case
[00:32:22]
by shrinking that failing case.
[00:32:25]
Yeah.
[00:32:25]
So it will kind of follow the process of here's a value that's for some reason it's interesting
[00:32:33]
because it fails the test.
[00:32:34]
I will give you smaller values or simpler values.
[00:32:39]
And you tell me if any of those fails the test also.
[00:32:43]
Right.
[00:32:43]
And so it kind of follows this process and it shrinks.
[00:32:48]
If it finds a smaller value that still fails the test, it will run the like the candidates
[00:32:56]
function again.
[00:32:57]
Right.
[00:32:57]
It will try to see, okay, how can I shrink this one?
[00:33:01]
And so it will follow that process until it can't shrink anymore according to the test
[00:33:07]
because, you know, values from one test wouldn't necessarily be failing some other test.
[00:33:14]
So it needs to shrink with regards to the current failing test.
[00:33:20]
Yeah, absolutely.
[00:33:21]
And so that's, that's the value based shrinking.
[00:33:25]
It has no context of how the value would generate it, whether it was mapped somehow, right?
[00:33:33]
It doesn't know anything about a generator and that creates certain problems.
[00:33:38]
Let's say if you had the end then function, which, you know, with random generation, it's
[00:33:45]
often useful.
[00:33:46]
Or if you had, let's say a filter function where you would say generate integer, but
[00:33:52]
I don't want it to be even, you would shrink the failing value, but you have no way of
[00:33:59]
running those filters on it again.
[00:34:01]
So it loses some of those invariants that you generated with.
[00:34:10]
Right.
[00:34:10]
And so that's the issue.
[00:34:12]
That's the issue with shrinking purely based on the value because you have no context about
[00:34:18]
the generation.
[00:34:19]
I've definitely run into this problem before and been confused as to why before I read
[00:34:24]
about the changes you were working on, where, you know, I basically want to say, you know,
[00:34:30]
as we talked about when you're, when you're building up a fuzz test, you can't check against
[00:34:35]
concrete expected outputs.
[00:34:37]
You have to check properties.
[00:34:38]
But so often you want to prune down your input list to say, well, these properties should
[00:34:44]
hold for this subset of inputs.
[00:34:47]
You know, for even numbers or and so you have to get clever.
[00:34:53]
You can't really filter it down.
[00:34:55]
But what I recall is you can map so you can get even numbers by doing an int fuzzer and
[00:35:01]
then map and then times two, which works very neatly for that case.
[00:35:07]
But you can't really say give me random input and then filter out invalid values.
[00:35:13]
Yeah.
[00:35:14]
Yeah, and so there's this history of Elm test, like in way in the 018 days.
[00:35:24]
It actually had like and then and a way to fail the test and so on.
[00:35:28]
But we removed it because it has these issues with shrinking.
[00:35:32]
But you know, you do want to have these functions.
[00:35:35]
Sometimes they really are useful.
[00:35:37]
And sometimes you can't really just like map arbitrary integer to be even.
[00:35:43]
That's, you know, that's that's a motivating example of why you don't want to use filter
[00:35:48]
and why you want to like construct right values rather than throw them out.
[00:35:53]
But sometimes it's really it would be really nice to have the and then function and to
[00:35:59]
have the filter function.
[00:36:01]
And the other approach, which I'm trying to get to the way it will work in Elm test P2.
[00:36:11]
Doesn't have those issues because we are shrinking something else than the value itself.
[00:36:17]
We are shrinking the PRNG history.
[00:36:20]
So PRNG is the random number generation algorithm.
[00:36:25]
And so we are is the P pseudo pseudo pseudo random.
[00:36:29]
Yeah, exactly.
[00:36:31]
Right.
[00:36:31]
So in V2 Elm test will remember the context of the generation.
[00:36:38]
And it will try to shrink that context that let's say list of dice rolls.
[00:36:45]
So, you know, the PRNG dice gave you five, gave you three, gave you two.
[00:36:52]
And from that, you somehow generated a value.
[00:36:54]
Right.
[00:36:55]
That's the that's the role of the fuzzer library to kind of transform those integers to your
[00:37:02]
values, custom types, whatever.
[00:37:04]
Right.
[00:37:04]
So you're and you're talking about the dice rolled being the seeds that we started with
[00:37:09]
to generate our input values.
[00:37:11]
Yeah, maybe maybe not exactly seeds because seed does have like a meaning for the random
[00:37:19]
number generation.
[00:37:20]
But the values that the PRNG algorithm produced, we do remember those.
[00:37:27]
We know that if we generate a value from those, we will get that failing value.
[00:37:32]
And now, instead of having a shrink function for the resulting value, we are shrinking
[00:37:42]
the PRNG history.
[00:37:43]
And suddenly, suddenly, not only you as the user do not have to care about shrinkers at
[00:37:51]
all because because previously you sometimes needed to write your own shrinkers.
[00:37:57]
Yeah.
[00:37:58]
Yeah.
[00:37:59]
OK, and so you as the user do not need to use shrinkers anymore.
[00:38:05]
These are internal to library and the library has many ways to try and shrink that list
[00:38:13]
of dice rolls.
[00:38:14]
Right.
[00:38:15]
So it can zero some of them.
[00:38:17]
It can delete chunks.
[00:38:19]
It can try to sort values in a chunk.
[00:38:23]
It has all these different strategies.
[00:38:25]
And it is fine tuned to the combinators that the fuzzer library gives you.
[00:38:33]
Right.
[00:38:33]
So the shrinkers know that the list fuzzer is written in such a way that the shrinking
[00:38:42]
strategy will work really well with that.
[00:38:44]
And this also gives you the benefit of generating the values after shrinking.
[00:38:51]
Right.
[00:38:52]
So suddenly you do filter after you have shrunk the PRNG history.
[00:38:59]
You are doing the end then function after you have shrunk.
[00:39:03]
And so all these invariants now hold because you are running those functions on the new
[00:39:11]
alternative history.
[00:39:13]
So you generate a list of integers.
[00:39:16]
That's your basis from a C.
[00:39:19]
You generate a lot of values.
[00:39:20]
And for each value you derive those.
[00:39:24]
Well, one value or multiple value.
[00:39:26]
You derive those into a value that you want to test.
[00:39:31]
Right.
[00:39:31]
And I'm guessing that in some cases you could have you could shrink it to the same value.
[00:39:36]
So for instance, if I if my generator generates a number between zero and 256, like that's
[00:39:43]
that's how this library works.
[00:39:45]
But all I want is a coin flip.
[00:39:47]
So it could have it could generate 232 and it could then simplify to 231.
[00:39:54]
But those would return both in heads or tails.
[00:39:58]
And that would not be very interesting.
[00:40:01]
Yeah.
[00:40:01]
So is it?
[00:40:03]
So sometimes you can get the same value from different PRNG histories and that's fine.
[00:40:10]
We mostly care about simplifying the PRNG history as much as we can.
[00:40:17]
So making it shorter and making it smaller.
[00:40:21]
And there's this convention between the shrinking process and between the generators that if
[00:40:30]
the PRNG history is smaller, the resulting value of your type that you want to test will
[00:40:37]
be simpler.
[00:40:37]
So the shrinker just doesn't care if it was 230 or 228 that generated the zero.
[00:40:47]
It will just pick the smaller one.
[00:40:49]
And if the generator has done its job well and maps simpler maps smaller histories to
[00:40:58]
simpler values, then you will shrink towards simpler values.
[00:41:03]
And so it might go from one to zero in your final value.
[00:41:09]
It might go from zero to zero as long as we have shrunk the history a little bit.
[00:41:16]
It counts.
[00:41:17]
Yeah.
[00:41:17]
OK.
[00:41:18]
And also from a user's point of view, it doesn't really matter all that much whether it does
[00:41:24]
a few cycles extra.
[00:41:26]
It's not like you're generating duplicate use cases.
[00:41:30]
Right.
[00:41:31]
Yeah, and with Elm being pure, you don't really care about running functions again and again.
[00:41:39]
Maybe a mocked on parser, but...
[00:41:43]
So, OK, you mentioned that in an Elm 18 version of Elm test, there were these and then and
[00:41:53]
filter functions for fuzzing.
[00:41:56]
What would have happened if you encountered a failing test from using filter?
[00:42:03]
I'm not sure if like generating an even set of even numbers would be a good example of
[00:42:08]
that to do, you know, fuzz.int and then filter out only even ones.
[00:42:13]
But what would happen with the shrinking if you were to use those with the older version?
[00:42:20]
So the test would fail with a generated free, let's say, and then it would try to shrink.
[00:42:29]
But a shrinker wouldn't know about this like this predicate, right, that you were filtering
[00:42:34]
by.
[00:42:35]
And so it would shrink to a value that doesn't where the predicate doesn't hold.
[00:42:40]
So, right.
[00:42:41]
Even if the generator would always give you like one, three, five, seven, after shrinking
[00:42:47]
you could get it to.
[00:42:49]
And that's not very helpful, right?
[00:42:51]
Because you only cared about the other class of values.
[00:42:56]
That makes sense.
[00:42:57]
I think I recall trying to do some problem like this, I think with Elm 19, encountering
[00:43:05]
something where I had to be careful not to create like an unresolvable shrinker or something
[00:43:12]
where I could potentially run out of things to try and then just, you know, just run out
[00:43:18]
and just hang or crash.
[00:43:21]
Yeah, that's very much still like an issue that you can run into with the Elm test V2
[00:43:30]
because that's just like, you know, that's just how filter works.
[00:43:34]
If you generate even values and then filter those to only keep odd values, you are never
[00:43:41]
going to see a value, right?
[00:43:43]
And so it could endlessly spin.
[00:43:45]
We are, I think the implementation that got merged has like 15 tries and after 15 tries,
[00:43:55]
it just says it's impossible to generate a value that would where this filter would hold.
[00:44:01]
So we just give up.
[00:44:02]
And so, yeah, we are like adding runtime failures into like the fastest world.
[00:44:13]
I don't know how to say it, but with Elm test V1, you couldn't filter.
[00:44:19]
And so you couldn't really have this class of errors, right?
[00:44:24]
But right now you can.
[00:44:26]
And that's, I think it's a good enough compromise to have these errors if we get the end then
[00:44:36]
function in return.
[00:44:40]
So the type based shrinking, it's looking at the actual values before it shrinks the
[00:44:48]
result, which would mean like if you say fuzz.int, it's shrinking those ints.
[00:44:54]
And then if you do fuzz.map, you know, you're mapping the values, but it shrank them before
[00:44:59]
it gave them to you to map.
[00:45:01]
Whereas with the...
[00:45:02]
Well, no, in the value based shrinking approach, it shrinks after everything is generated and
[00:45:11]
mapped and filtered.
[00:45:13]
I see.
[00:45:13]
So if you map it, it shrinks based on the actual mapped value.
[00:45:18]
Yeah, it shrinks right at the end of everything.
[00:45:23]
What if you map it to a different type?
[00:45:25]
How does it know how to shrink that?
[00:45:27]
To a different type, didn't it?
[00:45:29]
It's always going to be the same type.
[00:45:31]
Well, no, you can definitely map values to be a different type.
[00:45:35]
You can create custom type based on integer or something.
[00:45:39]
And then it's still the same type.
[00:45:42]
Well, then it's a custom type.
[00:45:45]
If you do fuzz.int and then you do fuzz.map and take an int and turn it into a custom
[00:45:52]
type constructor to call?
[00:45:54]
Yeah, then you have a different variant, but you still have the same type.
[00:45:57]
But different from the original type of the fuzz generator.
[00:46:03]
Oh, yeah.
[00:46:03]
Okay.
[00:46:03]
Yeah.
[00:46:04]
So how does it know how to reduce your custom type?
[00:46:08]
Right.
[00:46:09]
So this is something that's been called integrated shrinking.
[00:46:13]
And that's why you are not using random generators.
[00:46:17]
That's why you are using fuzzers.
[00:46:19]
And so each of those fuzzer combinators has two parts.
[00:46:25]
One is about generating.
[00:46:27]
So presumably it's doing like this random map with the function that you gave it.
[00:46:32]
And then the second part is the shrinking information.
[00:46:36]
And I'm not really sure about the details, but I believe it kind of knows that it was
[00:46:42]
made from an integer.
[00:46:44]
And so it tries to shrink those integers.
[00:46:46]
And there's the mapping between the integer and your custom type.
[00:46:51]
And so it still kind of knows how to shrink because it was created from integer.
[00:46:59]
But it doesn't have any information about your type, right?
[00:47:05]
You would have to create, you would have to use something like fuzz custom where you give
[00:47:09]
it generator for your type and a shrinker for your type.
[00:47:14]
So it kind of feels like what is V2 doing?
[00:47:17]
So V2 is different in that the fuzzers are mostly just concerned about generating.
[00:47:26]
And there's no three of possible ways to shrink the whole thing down.
[00:47:33]
There are no shrink value to different value function.
[00:47:39]
It basically just goes one layer deeper.
[00:47:41]
And the shrinking is concerned with the inputs to the PRNG, right?
[00:47:47]
And so it tries to generate a different PRNG history and then tries to generate a value
[00:47:54]
from that.
[00:47:55]
It doesn't have to succeed all the time because let's say if you have a list of three items
[00:48:01]
that might need because of how the list generator, how the list fuzzer is written, it might need,
[00:48:08]
let's say three or four values, like three or four dice rolls.
[00:48:14]
And if you shrink that history into a list of two dice rolls, then you can never generate
[00:48:21]
a list of four values out of that.
[00:48:22]
There's just too little information, right?
[00:48:25]
And so it doesn't need to succeed every time.
[00:48:29]
But if it doesn't succeed, it just throws that shrinking attempt away.
[00:48:34]
And it keeps those that are somehow simpler, but still generate a value and that value
[00:48:43]
still fails.
[00:48:44]
And so you are running your generator all the time.
[00:48:48]
You are, that's the difference.
[00:48:51]
So in the v1 approach, you generate a value and then you run the shrinker and the test
[00:48:58]
a lot of times.
[00:48:59]
But in the v2 approach, you are generating a lot of times when you find a failing value,
[00:49:05]
you run the shrinker.
[00:49:06]
And after every shrink, you run the generator again.
[00:49:11]
And so all the invariants are still kept.
[00:49:14]
So you've written an upgrade guide for running your fuzzers or your fuzz tests.
[00:49:19]
And in the v1 API, I see a lot of uses of random generators.
[00:49:25]
And in the v2, you use a lot of fuzzers instead.
[00:49:29]
So this feels like it's a simplification to the API.
[00:49:33]
It's a lot more consistent.
[00:49:35]
And I'm guessing you also get a few benefits out of it.
[00:49:38]
Yeah.
[00:49:39]
So for you as the user, I believe it's nice that you can stay in one module and just use
[00:49:47]
one module fully and express everything you want just with fuzzers.
[00:49:52]
And from the perspective of the library, it's needed because we need to track the PRNG history
[00:50:01]
ourselves.
[00:50:02]
So if we gave you a function to create a fuzzer from generator, which we do, but it's an escape
[00:50:08]
hedge and it will not shrink well at all.
[00:50:10]
So please don't use it.
[00:50:11]
But if you don't use what?
[00:50:14]
Sorry?
[00:50:14]
Don't use what?
[00:50:16]
Don't use fuzz from generator.
[00:50:19]
Okay, I think it's the equivalent of the current fuzz custom with no shrinking, with shrinking
[00:50:28]
disabled.
[00:50:29]
Basically, we need to...
[00:50:32]
The fuzz library is built on top of random generator for integers and nothing else.
[00:50:40]
Right?
[00:50:42]
That's a simplification, but basically that's it.
[00:50:44]
And we build the whole like how to do floats out of integers, how to do strings out of
[00:50:51]
integers, how to do everything else from integers.
[00:50:54]
We do that ourselves because we need to be able to hold that list of generated integers
[00:50:59]
to shrink it.
[00:50:59]
Right?
[00:51:01]
And so if we give you a function where you can provide generator of your custom type,
[00:51:10]
we have no way of running it other than just generating a random integer, using that as
[00:51:19]
a seed and remembering that seed.
[00:51:22]
But it's just like a meaningless number, right?
[00:51:25]
That's the point of seeds.
[00:51:28]
Yeah, you can try and simplify it.
[00:51:32]
Yeah, there's no structure that we could try to somehow shrink down.
[00:51:37]
It's just one big integer and yeah, for the library it's a black box.
[00:51:44]
Yeah, you could try different inputs, but you wouldn't know if they were simpler or
[00:51:47]
not.
[00:51:48]
So what's the point?
[00:51:49]
Yeah.
[00:51:49]
So I guess that's the price of it.
[00:51:53]
That now you don't need to use the random library, but we really strongly urge you not
[00:52:01]
to use it, not to use the escape page.
[00:52:04]
Right?
[00:52:04]
So sometimes you might need, if for example, if your library is exposing generators, it
[00:52:13]
might now be a good idea to expose fuzzers also.
[00:52:17]
And you have no other choice than to write them from scratch using the fuzzer API.
[00:52:23]
But we have tried to make it really simple to do so.
[00:52:27]
And I know of no cases where you could do something with the random module, but couldn't
[00:52:33]
do it with the fuzzer module.
[00:52:35]
Okay.
[00:52:35]
So you just added this escape hatch just in case, basically.
[00:52:38]
Yeah.
[00:52:39]
Just in case somebody wants to use third party generator, right?
[00:52:45]
You don't want to clone Elm geometry and like see how the generator is created just so that
[00:52:52]
you can create fuzzer based on that.
[00:52:55]
You could just use the escape page, but you are not going to get nice shrinking because
[00:53:01]
it's a black box.
[00:53:03]
Yeah.
[00:53:04]
It makes sense that it somehow like loses semantic information when you just have a
[00:53:09]
generator because there are bits of state and semantics that the fuzzer keeps track
[00:53:15]
of.
[00:53:15]
I mean, I could imagine a world where the Elm random generator is just a random generator
[00:53:23]
implementation is actually just a fuzzer under the hood.
[00:53:28]
So you define it using the same thing.
[00:53:32]
And now you say fuzzer from generator and hey, what do you know?
[00:53:38]
It actually is a fuzzer.
[00:53:40]
It's just that we hid that from you or, you know.
[00:53:43]
Yeah.
[00:53:43]
You can go that way.
[00:53:46]
So we could create a function fuzzer to generator and that's fine because we don't need to
[00:53:53]
define because we just throw away the history that we needed for shrinking.
[00:53:58]
You don't need it if you just want to generate the value.
[00:54:00]
So we could give you the function.
[00:54:02]
And if that was the underlying representation of random numbers or Elm random library, we
[00:54:09]
could have a nice, very well shrinking from generator function.
[00:54:14]
But it would need, you know, it would need changes to the Elm random package.
[00:54:19]
So these inputs, could you like shed a little light on how you take like these basic generators,
[00:54:29]
which are conceptually generating ints as the input and how you derive these, you know,
[00:54:38]
kind of baseline generators for other types of values in a meaningful way, like the list
[00:54:44]
generator and pool generators and things like that.
[00:54:46]
How do you ensure that the baseline generator values map to, you know, reduce down to simpler
[00:54:55]
primitive values with these core generators or core fuzzers?
[00:54:58]
Yeah.
[00:54:59]
So, so integers are easy.
[00:55:04]
Integers just map to integers.
[00:55:06]
There's a little bit more complication around that where we prefer some ranges of integers
[00:55:12]
and then, you know, with smaller probability, we give you larger and larger integers.
[00:55:19]
There's also some things where we just take, let's say the most significant bit of the
[00:55:26]
integer to mean the sign bit so that, so that we prefer positive values to negative values.
[00:55:34]
Right.
[00:55:34]
So if, if, if both minus two and two would fail the test, we are going to give you the
[00:55:42]
two because it's just nicer.
[00:55:43]
So there are some, the world is more complicated than that, but integers are pretty easy.
[00:55:50]
And so what can we build from that?
[00:55:53]
You could build characters.
[00:55:56]
So you have the function character for code, which just uses the, it's not ASCII, right?
[00:56:02]
It's UTF 16 or something.
[00:56:05]
You just build, build a character from a number.
[00:56:08]
So you have characters.
[00:56:10]
We can have lists or just like generally collections by flipping your coin.
[00:56:18]
So this is the approach we chose to generate lists where you flip a coin.
[00:56:24]
If it's zero, then you don't create any more elements.
[00:56:33]
If you get one, you try to generate again.
[00:56:38]
So that's where and then comes in.
[00:56:40]
Right.
[00:56:40]
So you have these like recursive algorithm, which is building the list.
[00:56:45]
And so that leaves a trail of, of the PRNCh history, right?
[00:56:50]
And then some value that's mapping to the integer, then there's going to be one.
[00:56:56]
And again, history for the second value, then there's going to be zero and that's it.
[00:57:02]
Right.
[00:57:02]
Because that's when we start generating the list.
[00:57:05]
And so, so it always reduces to smaller.
[00:57:08]
Yeah.
[00:57:08]
So you can, if you delete the first two values from the PRNCh history, it's going to leave
[00:57:16]
you with a valid list.
[00:57:19]
Right.
[00:57:19]
So if one something, one something zero shrinks down to one something zero, that's going to
[00:57:26]
be fine because the list accepts that.
[00:57:28]
And so this shrinks better than if we tried to generate a number for the count of how
[00:57:37]
many values we want and then just generating those in line because you would have to decrement
[00:57:44]
the number and delete some other chunk after it.
[00:57:48]
So it's just kind of weird, you know, with the internal representation, it's kind of
[00:57:54]
not very simple way to shrink those lists.
[00:57:58]
So we opted for the nicely chunkable flip a coin approach.
[00:58:04]
And then you have multiple histories for each list elements, right?
[00:58:08]
Is that what you said?
[00:58:10]
Oh, one history for each slot.
[00:58:13]
One history.
[00:58:14]
Well, one history gives you one final value.
[00:58:19]
So one PRNCh history will give you, let's say a list of characters or something, but
[00:58:24]
each of those characters in there, it might not be composed of just one dice roll.
[00:58:30]
It might be composed of multiple, right?
[00:58:32]
So each fuzzer can draw arbitrarily many random values.
[00:58:39]
And so you could think about it as of a tree or of some kind of released of nested lists
[00:58:48]
where a given sub branch is created by this specific fuzzer, but in the end, it's all
[00:58:57]
flattened out and the shrinking library doesn't really know which dice roll is related to
[00:59:07]
which value, right?
[00:59:08]
It is kind of blind to that and it just tries different stuff, zeroing, decrementing, removing
[00:59:16]
and just sees, just throws it at the wall and sees what sticks.
[00:59:20]
Okay.
[00:59:21]
And that might result in a few things that don't make sense and which may fail, but it
[00:59:26]
will find something which will work out.
[00:59:30]
Yeah.
[00:59:31]
So does it create a new branch every time you call and then?
[00:59:34]
Is that it?
[00:59:35]
So, and then just runs another fuzzer.
[00:59:39]
And so fuzzers have state inside them, right?
[00:59:42]
They do have the current history and you can think of those like base fuzzers, like integer
[00:59:50]
or flip a coin or whatever.
[00:59:52]
You can think of them as generating value and giving, letting you do something with
[00:59:58]
that, but also appending to the state.
[01:00:02]
Right.
[01:00:02]
And so that's kind of like this monadic dance of keeping a state around where you only exposed
[01:00:10]
the value, but basically there are no like concurrent different histories.
[01:00:17]
There's just one history.
[01:00:19]
But as you go through the function and as you call these L functions recursively, they
[01:00:24]
are going to append to that state and in the end you end up with both the created value
[01:00:32]
of your type and with the PRNG history.
[01:00:35]
So fuzzer is a monad.
[01:00:39]
Yeah.
[01:00:39]
It has an end.
[01:00:41]
So yes.
[01:00:44]
That's the definition, right?
[01:00:46]
Right.
[01:00:47]
And so, and so, right, we have, we have integers, characters, lists, all these things like map,
[01:00:54]
map to, and then those can be done without the specific values.
[01:00:58]
Those are just like way to combine those.
[01:01:01]
And now that you have lists, you can do all kinds of stuff.
[01:01:05]
You can do strings, which are just conceptually just lists of characters.
[01:01:10]
You can do sets, dictionaries with the filter function.
[01:01:16]
Well, I want to say with a filter function, but it's different.
[01:01:19]
It's defined differently.
[01:01:20]
You can do lists of certain length and so on.
[01:01:24]
That's actually pretty, pretty smart.
[01:01:27]
We have this, this flip a coin fuzzer that gives you one with certain probability.
[01:01:36]
So you give it a float.
[01:01:37]
And so sometimes these lists of certain length fuzzers, if they see they have enough stuff,
[01:01:46]
they will say, okay, the next flip of a coin will be with probability zero, right?
[01:01:51]
And so it will, it will not generate stuff in advance and then just like throw it out.
[01:01:57]
It will just like stop, like I'm giving you this biased coin.
[01:02:00]
And so there is, there are tricks like that, but it works out pretty well and it's all
[01:02:07]
pretty, pretty optimized and optimal.
[01:02:11]
There's one fuzzer that is really, really, really, really complex.
[01:02:18]
And that's for floats because we can't really use a float generator, right?
[01:02:24]
We can only use generators for integers.
[01:02:27]
And we are inspired by the library hypothesis, which is this like property based distinct
[01:02:35]
library for Python, which started with this let's say internal shrinking approach.
[01:02:42]
And they gave a lot of care to shrinking floats nicely.
[01:02:50]
So, you know, with the current LN test, you could have the test that fails for some kind
[01:02:56]
of float.
[01:02:57]
And of course it will generate some random number in the like 10 millions and so on with
[01:03:04]
all these different like digits.
[01:03:06]
And it will shrink down to some really unreadable integer next to zero, right?
[01:03:11]
So 0.00008135, whatever.
[01:03:17]
And this is not very nice because if the test would fail with zero or with one, why not
[01:03:24]
give you that, right?
[01:03:25]
It would be just much nicer for the user.
[01:03:28]
And so we can't really do some kind of trick where we take two integers and divide, do
[01:03:36]
some bit magic and just divide things by the maximal float and give you flows in the uniform
[01:03:43]
distribution.
[01:03:44]
There will be a really easy way out, a really easy way to generate floats, but it doesn't
[01:03:50]
shrink well, right?
[01:03:51]
And so what hypothesis did and what LN test now does is we reorder the bits in the IEEE
[01:04:02]
754 float representation to kind of follow the rule from the shrinkers, right?
[01:04:09]
So if the random integer is smaller, it will result in a simpler float.
[01:04:15]
And so there's a lot of like bitwise masking and oring and shifting and it's really crazy.
[01:04:24]
And that's the part that I was most stressed about.
[01:04:29]
But the result is floats will shrink beautifully and it will give you, so it will prefer positive
[01:04:37]
numbers, it will prefer smaller numbers, but it will prefer integers over decimals, right?
[01:04:44]
So it will prefer numbers like one over 1.5, but also it will prefer smaller fractions
[01:04:52]
over huge fractions.
[01:04:54]
So it will give you 1.5 instead of 1.76543215, right?
[01:05:02]
And so I'm pretty happy about that.
[01:05:04]
And I'm curious to see if this like different distribution of floats, if it will find some
[01:05:12]
bugs easier than the V1 version of LN test.
[01:05:16]
I'm not really sure about that, but I'm curious to see.
[01:05:20]
And we are also adding the not the numbers in there.
[01:05:24]
We are adding the infinities in there, which is probably going to be what finds the most
[01:05:28]
bugs, but also, you know, sometimes your library or application doesn't really care about those.
[01:05:35]
And you are just like, okay, if you give me garbage, I will give you garbage no matter.
[01:05:39]
So next to like fast.float, we also have fast.nicefloat, which is just numbers.
[01:05:47]
So, you know, if suddenly you have like 30 failure tests because of infinities that will
[01:05:54]
not happen in your code, who knows?
[01:05:56]
Will they not?
[01:05:57]
Right?
[01:05:58]
That you hope won't happen.
[01:06:00]
Yeah.
[01:06:00]
But you can pick the easy way out and you can just switch from floats to nice floats.
[01:06:07]
And those tests, those test failures will go away, but perhaps keep them in.
[01:06:15]
Perhaps somehow guard against these values in your application code, right?
[01:06:19]
It's also an option you can take.
[01:06:21]
I have to say, I still haven't encountered a NAN in Elm code, like in JavaScript.
[01:06:29]
Sure.
[01:06:29]
But I have never counted one.
[01:06:32]
So I think I'm just going to go with nice floats always.
[01:06:36]
Yeah.
[01:06:37]
I mean, maybe, maybe, maybe I'll try it.
[01:06:39]
And yeah, I did.
[01:06:42]
I did encounter them at work recently.
[01:06:45]
I can't remember what specific scenario that was, but I was just getting NANs all around
[01:06:52]
and I was like, why?
[01:06:54]
These are like, there's no reason.
[01:06:58]
It's always something about like, by dividing by zero, you get infinities and then you do
[01:07:03]
something about the infinities and suddenly it's a NAN.
[01:07:05]
So yeah, it's, yeah.
[01:07:07]
All you need to do is write a fuzztest to make sure that no code returns a NAN.
[01:07:14]
That's it.
[01:07:15]
Do it everywhere and you can go to go.
[01:07:18]
Perhaps that's also something Elm review could do.
[01:07:21]
Like, Hey, what are you doing with that zero?
[01:07:23]
Put it down.
[01:07:26]
Sure.
[01:07:27]
You could check for division by zero at least.
[01:07:30]
Yeah.
[01:07:31]
I mean, with fuzzers, like why not just do a fuzz test?
[01:07:36]
Like, why not just throw more inputs at it?
[01:07:39]
If you can get meaningful test results, it's really cool how much thought you put into,
[01:07:47]
you know, all of these little details for, I mean, essentially this is kind of the user
[01:07:55]
experience, the usability of fuzzers and their errors and how meaningful they are.
[01:08:00]
Right?
[01:08:01]
Because if you write a fuzzer that fails, then you have a failing test, but it's a question
[01:08:07]
of how useful is the reduction it's able to give you this simplified value.
[01:08:12]
Yeah.
[01:08:12]
Yeah.
[01:08:13]
I think this is like the red line going through the whole release, like making stuff nicer
[01:08:20]
for the user and like giving you more power, but also giving you better results.
[01:08:27]
Yeah.
[01:08:28]
Right.
[01:08:28]
And making it map more intuitively and yeah, this definitely is giving me a lot of motivation
[01:08:36]
to like throw some more fuzzers in my projects.
[01:08:39]
I definitely have some, but I feel that I'm not doing a good enough job identifying those
[01:08:45]
opportunities and keeping my eye out for where I need to test a property and where it would
[01:08:51]
be helpful to have a lot of inputs exercised, which there are really a lot of cases.
[01:08:56]
Most of my tests are Elm review tests, so I would have to generate some Elm code and
[01:09:04]
then I would have to make sure that it's reports an error in this kind of case.
[01:09:09]
Like, yeah, I feel like fuzzers are very appropriate there, but I could learn something.
[01:09:16]
I could imagine fuzz testing with Elm review where you could say something like, you know,
[01:09:22]
with import as, and then you use that import as to generate your strings.
[01:09:31]
So you use a module a certain way because like often that's something I'll miss in Elm
[01:09:36]
review fixes or rules is I won't check for a hard coded module and maybe do fixes with
[01:09:44]
that hard coded module or without checking the way it's imported.
[01:09:48]
So if you fuzz that, you know, that would be the challenge is now, you know, you have
[01:09:54]
to write the tests and consume that instead of just writing a hard coded string.
[01:09:58]
So there's certainly a trade off there.
[01:10:00]
Also Elm review asks you to write the expected fixed code.
[01:10:06]
So you would also have to generate that based on the same input.
[01:10:09]
So basically you're redoing this, the implementation.
[01:10:13]
Yeah, that's always the issue of like, how do you stop from just writing the implementation
[01:10:20]
in the test?
[01:10:21]
Yeah.
[01:10:22]
And that's kind of, kind of really the one tricky thing about property based tests, like
[01:10:28]
thinking of the properties and there's an awesome blog post.
[01:10:35]
I can't recall the author, but it's about property based tests in F sharp.
[01:10:41]
I think it is like F sharp for fun and profit is the name of the blog.
[01:10:45]
Oh, Scott Walsh.
[01:10:47]
Oh yeah.
[01:10:49]
So he has some great blog posts about what types of properties are there, right?
[01:10:55]
So there's this like mathematical laws.
[01:10:57]
You can check that like appending an empty string to anything will be that string and
[01:11:04]
so on.
[01:11:04]
But there's also these like round trips and like Oracle testing where let's say you are
[01:11:11]
implementing your own optimized sort function.
[01:11:15]
You can always check it against the standard library list dot sort, right?
[01:11:22]
And so there are these things where you know kind of what the expected output should be
[01:11:27]
and you can test against like the reference implementation and so on.
[01:11:31]
There's all these different types of properties that you can use and he's really great about
[01:11:37]
like showing examples and kind of walking you through it, building intuition.
[01:11:43]
And yeah, so that's, I think we could put that into show notes.
[01:11:48]
That's really good intro into how to think about property based tests.
[01:11:54]
That sounds amazing.
[01:11:55]
Yeah, that sounds very helpful.
[01:11:56]
I would love to have like a, you know, just a set of categories to think about of different
[01:12:02]
types of properties to check for in my brain when I'm writing code.
[01:12:07]
That seems like that would help me motivate me to actually reach for that tool more often.
[01:12:11]
Yeah, as you say, it's a problem of identifying when to use it.
[01:12:15]
So those categories seem like a great trick for that.
[01:12:19]
And that's basically what the blog post is about, those types of categories.
[01:12:23]
So go for it.
[01:12:25]
That's great.
[01:12:26]
I see there's a video associated with it too.
[01:12:28]
That's perfect.
[01:12:30]
Also, like the amount of care that you put into shrinking to nicer values and making
[01:12:36]
that intuitive is like really changed the way I think about fuzzing and made me think like,
[01:12:43]
wow, you know, both think more deeply about like, how do I want to generate fuzz inputs
[01:12:49]
to make sure I'm meaningfully exercising the relevant cases?
[01:12:53]
And then how do I reduce those down in a meaningful way?
[01:12:56]
Like, I was thinking, you know, I'm sure you have to think carefully about the semantics
[01:13:02]
if you want to produce a fuzzer that really reduces values down meaningfully.
[01:13:07]
Now, again, if you get a fuzz test that fails, it's failing no matter how well you've reduced
[01:13:15]
it.
[01:13:15]
So you don't necessarily need to worry about that for just getting an error message.
[01:13:19]
And it's more how nice do we want to make the fuzz out?
[01:13:22]
Yeah, it's all about the UX.
[01:13:26]
Right, right.
[01:13:27]
But for the input, that's a different story because you do want to make sure that you're
[01:13:33]
exercising the important cases.
[01:13:36]
You want to be sure that you are kind of spread over the input space properly so that given
[01:13:43]
enough time, you will find the failing value.
[01:13:46]
Yeah.
[01:13:47]
It's like a question of, you know, in a unit test, it's pretty common that in TDD, I always
[01:13:54]
try to encourage people that the error message is part of the failure and part of the test
[01:14:01]
driven part in TDD.
[01:14:02]
So you don't just go make it green.
[01:14:05]
Like, see the error message, improve the error message if it doesn't tell you what to do
[01:14:12]
and then do the thing it tells you to do.
[01:14:14]
But so it would be the equivalent of like, yeah, you have a failing test, your CI is
[01:14:19]
going to break, but now you don't know why because you don't have meaningful information.
[01:14:23]
So those things are both important.
[01:14:25]
It's probably more important that it just fails in general.
[01:14:29]
But if you can make it nice output, that's great, too.
[01:14:32]
So this is this has not been released yet.
[01:14:36]
This is still in a beta version of the untest CLI.
[01:14:41]
Right, but it has a command to make sure that you can to allow you to try it out.
[01:14:47]
So this is still in a testing period, a testing period.
[01:14:54]
So how can people try it out and what do you expect to hear from people?
[01:14:58]
Right.
[01:14:59]
Yeah, we have posted some discourse posts about both the new version of the untest
[01:15:06]
CLI that allows you to try it and also call for testing, call for kind of like, please
[01:15:14]
help us find if there's anything horribly wrong before we make the 2.0.0 version.
[01:15:21]
So, yeah, so in the new CLI, I believe starting from revision 8, you have this command.
[01:15:29]
Let's say what it was, install unstable test master, something like that.
[01:15:35]
It's going to be that if you do like untest help.
[01:15:39]
Yeah, you got it right.
[01:15:40]
Yeah, yeah.
[01:15:41]
Great.
[01:15:41]
Wow.
[01:15:43]
We also linked to it in the show notes anyway.
[01:15:45]
So yes.
[01:15:46]
Thank you.
[01:15:47]
So it basically just pretends that your 1.2.2 version, which is the current untest version,
[01:15:56]
it just pretends that it contains the code from 2.0.
[01:16:00]
Right.
[01:16:01]
So it rewrites your elm home, which is usually in like the home slash dot elm slash something.
[01:16:12]
And so we are essentially rewriting your cache and on the next untest run, it will pick up
[01:16:21]
the new library.
[01:16:22]
Right.
[01:16:22]
And you can undo that either by just removing the cache, so removing the dot elm directory,
[01:16:31]
or you can use uninstall unstable test master command in elm test.
[01:16:37]
And yeah, so after you install that, after it kind of tempers with your cache, you can
[01:16:45]
run elm test or elm test RS, I believe, and it will use the new library.
[01:16:49]
And so there are some API changes, right?
[01:16:52]
So you can expect to see some failures from like test code not compiling, but that's going
[01:17:01]
to be, I believe, mostly the true and false functions being gone from the expect module
[01:17:09]
and also the tuple and triple functions changing to like pair or the other way around.
[01:17:18]
Basically tuple fuzzers got a little bit of, again, user experience improvement, I believe,
[01:17:26]
where you don't have to structure the inner fuzzers into a tuple.
[01:17:31]
Yeah, right.
[01:17:32]
Yeah, you don't have to pass in a tuple of fuzzers.
[01:17:35]
You pass in two arguments for the tuple and it's not called fuzz dot tuple.
[01:17:41]
It's called fuzz dot pair.
[01:17:42]
It's not called fuzz dot tuple three.
[01:17:44]
It's called fuzz dot triple, which I much prefer, especially if you're using a tuple
[01:17:48]
with the Elm syntax actually only having those two kinds now.
[01:17:52]
Yeah.
[01:17:52]
And so there is a document about basically API changes.
[01:17:58]
And so I have tried to do a good job of like listing them all out.
[01:18:04]
I actually used Elm div command to get that and saying what you can do instead.
[01:18:12]
And it should be quite non problematic.
[01:18:16]
It should be really just like those tuple changes and expect true and false being gone,
[01:18:23]
where again, there's the explanation of what you can do instead.
[01:18:27]
It's one to one, so all cases should be covered.
[01:18:31]
So you can test it out.
[01:18:33]
You can change your test suite and see whether there is some problem that we didn't think
[01:18:41]
about that we should fix before releasing 2.0.
[01:18:46]
And you can also tell us if it caught any new bugs or if you are happy about a fault
[01:18:55]
fuzzer, I would be very happy to hear that.
[01:18:58]
Do you expect that it could find less problems than before as well?
[01:19:03]
It's possible.
[01:19:04]
I think the distribution definitely changed.
[01:19:08]
Right, so Elm test one and Elm test two will try different points with different probability.
[01:19:15]
But we didn't really change all that much.
[01:19:19]
We will still trigger like the whole space as before.
[01:19:24]
It might be just the probabilities that change.
[01:19:26]
So again, if you run your tests enough, you should see the same errors and hopefully you
[01:19:34]
will see them sooner because we are preferring small inputs than larger inputs and so on.
[01:19:40]
It is not totally uniform.
[01:19:43]
All right, great.
[01:19:44]
So there are some really nice videos you put together kind of walking through some of the
[01:19:49]
design, so people should definitely check those out.
[01:19:51]
We'll link to those in the show notes.
[01:19:53]
Are there any other resources we should point people to?
[01:19:56]
I think we should mention that for feedback, you should go to the testing channel on Slack
[01:20:02]
or maybe open a GitHub issue.
[01:20:04]
Yeah, you can do that.
[01:20:06]
We are, or at least I am monitoring the testing channel, so I will definitely be there.
[01:20:12]
You can post on this course in the post or create your own.
[01:20:16]
You can definitely raise an issue on GitHub.
[01:20:19]
As for the resources, I'm not sure about any fundamental resources.
[01:20:27]
I definitely take a lot of inspiration from how the library Hypothesis does things in
[01:20:33]
the Python world and they have a blog with a lot of these like why do that and how to
[01:20:38]
think about it and let's say testing stateful programs, which we don't really have in like,
[01:20:44]
we don't have like side effects, but we still do have those like updated messages and so
[01:20:49]
on.
[01:20:49]
So you can, you can glean a little bit from that.
[01:20:52]
It's not always going to be applicable because we just don't have certain kinds of problems,
[01:20:58]
but yeah, I like their approach of putting the user experience or like the developer
[01:21:05]
experience as a priority.
[01:21:08]
And so we are actually in talks with Jakub Hampel, a gamble man on Slack.
[01:21:15]
We are kind of toying with the idea of, let's say a failure database.
[01:21:20]
So if the fastest we'll find a bug, it will remember it.
[01:21:24]
And the next time you run the test, it will try it first, right?
[01:21:29]
Just so that you can, you don't need to like randomly find it again, but it will try it
[01:21:36]
straight away.
[01:21:37]
And forever from now on or something.
[01:21:39]
Yeah.
[01:21:39]
Yeah.
[01:21:39]
I guess until you clear the cache or whatever.
[01:21:43]
But yeah.
[01:21:44]
So I think, I think we can still steal a lot of nice ideas from the ecosystem in different
[01:21:52]
languages.
[01:21:54]
And so hopefully the testing story in Elm is going to be nicer and nicer.
[01:22:01]
Yeah.
[01:22:02]
Which already it's so nice just by using a language like Elm with pure functions and
[01:22:08]
not having implicit state in these things.
[01:22:10]
So testing is such a fun thing.
[01:22:14]
Yeah.
[01:22:14]
Yeah.
[01:22:15]
Add fuzzing to the mix and you get potentially some flakiness back, but maybe the database
[01:22:21]
thing, it's a good kind of flakiness, but hopefully.
[01:22:25]
Yeah.
[01:22:25]
Yeah.
[01:22:26]
Hopefully your inputs are well distributed enough to not be flaky though.
[01:22:31]
Yeah.
[01:22:31]
All right.
[01:22:32]
Well, Martin, thank you so much for coming back on.
[01:22:35]
It was a pleasure.
[01:22:35]
And again, congratulations on getting this merged in.
[01:22:39]
Thank you.
[01:22:40]
Thanks for having me.
[01:22:42]
It was a pleasure.
[01:22:43]
And your rune until next time.
[01:22:45]
Until next time.