Generating Witnesses / Example Strings From Regular Expressions

[maximaximal]

Thank you for this very interesting work and nice library! I just stumbled over this repository and your POPL paper.

I was wondering if you could use your automaton-machinery to also generate matching strings from a regular expression. So given some regex, you could then produce e.g. an Iterator<Item=String> that each time you call its next function, some new example is produced. Ideally this would be done in such a way that the examples are not completely similar, so some BFS traversal over your automaton (with some kind of character class abstraction) sounds like a naive-but-maybe-ok starting point for simpler expressions.

This reminds me of model checking and building witnesses to found issues, the two challenges are not that different I think, especially since you build everything on your automaton.

I already looked through your implementation a bit to check where to start with this, but before I go and try too much I wanted to ask if some kind of "regex witness generation" is something that you also already thought of and if you see a place where to nicely integrate this functionality.

[ieviev]

Yes this is possible, i've been thinking of adding a "give me some sample strings this regex matches" feature for a while.

You can do it very nicely with derivatives, i think it would add another use for the library as well.

I haven't thought of what the public api should be but I have a code snippet for fuzzing with resharp somewhere, i will copy it here in a bit

[ieviev]

@maximaximal There is a little standalone example at https://github.com/ieviev/fuzzing-with-resharp.
It should be fairly efficient because you don't need to generate a full automaton at all.

I plan to add it as part of the core library as well at some point, but i'm busy with writing a dissertation at the moment.

[maximaximal]

This is really cool, thank you very much for this example! I will try this in my context. I expect to have quite a lot of alternatives, but if I don't even have to generate the full automaton, this is basically perfect.

All the best for your dissertation! Your papers certainly are a good basis for it. Hoping you can stay a bit on the cumulative-end of the dissertation spectrum, so you don't have to fully rephrase everything you already spent so much effort on for the papers.