Support minLength and maxLength for stringMatching

[TomerAberbach]

🚀 Feature Request

stringMatching generates based on the regular expression, but doesn't provide a way to set a min or max length on the generated strings.

Motivation

Sometimes you want to test specific lengths of a string matching a regex, but modifying a regular expression to have a specific min and/or max length can be pretty hard and confusing. It would be a lot easier to just be able to pass minLength and maxLength like the string arbitrary.

Example

const nameRegex = /^[a-z]+$/

// Test different lengths without having to modify regex
fc.stringMatching(nameRegex, { minLength: 10 })
fc.stringMatching(nameRegex, { maxLength: 10 })
fc.stringMatching(nameRegex, { minLength: 5, maxLength: 10 })

[dubzzz]

So far the only option I have for it is to play with .filter but unfortunately performance-wise it will not be ideal. I'd need to think about a way to make such constraint more optimal before offering it on the arbitrary.

[gruhn]

Hmm, interesting problem. Regular expressions are closed under intersection. So one idea might be to "just" compute the intersection of nameRegex and for example /^.{5,10}$/. That gives a new regular expression which is restricted to strings with min length 5 and max length 10. I think this can be done in ~O(n^2). Not super cheap but it's an upfront cost and maybe negligible for small user defined regular expressions.

One way to do it might be:

1. Convert both regular expressions to NFAs (I think: O(n))
2. Compute NFA intersection (I think: O(n^2))
3. Convert resulting NFA back to regular expression (I think: O(n))

Any route involving DFAs seems to come with the danger of exponential blow up.

For the regular expressions from formal language theory, this is maybe not too complicated but I can imagine you need a ton of case distinctions for the the full JavaScript regular expressions. So not sure if this is the best approach.

[TomerAberbach]

This certainly sounds quite tricky! Thanks for all the research here :)

By the way @dubzzz, in case it changes priority, in addition to needing this for typespec-fast-check, we actually coincidentally needed the same exact thing at Stainless (where I work).

We were trying to automatically generate example values for OpenAPI spec schemas like the following (this is just an example schema):

type: string
pattern: [a-z]+
minLength: 3
maxLength: 10

I ended doing fc.stringMatching(...).filter(s => s.length >= minLength && s.length <= maxLength) and passing that to fc.sample.

It's still very quick, but I only needed to generate one value from fc.sample so that probably helped