D-Bus specification specifies various maxima which strategy does not conform to

[mulkieran]

• Maximum total depth of internal nodes, struct, array, dict, variant is 64.
• Maximum number of arrays/dicts allowed on any given path is 32.
• Maximum number of structs allowed on any given path is 32.
• Maximum number of characters in signature is 255.

So, strategy is not sound.

[mulkieran]

It might be sensible to change the internal implementation entirely, so that it constructs a syntax tree and then travels the syntax tree to construct the actual signature string.

It is possible that the enhance argument to the recursive strategy could check its children argument for depth, and use the identity function if it is possible for the signature to have hit the maximum. Or, it might be that you could monitor the depth of the whole thing, and when you have the possibility of exceeding the maximum, stop.
Or, it might be possible to reduce the syntax tree in a post- step until it conforms to the maxima.

[mulkieran]

Note that an array adds just one character to represent the node 'a', a dict add three characters, 'a', '{', '}', and a struct adds two '(', ')'.

[mulkieran]

Note that HypothesisWorks/hypothesis#170 is a generalization of this strategy, since the core grammar of signatures is regular except for this unfortunate problem of the maxima.

[DRMacIver]

the core grammar of signatures is regular except for this unfortunate problem of the maxima.

FWIW I think this language is still regular (but may require a very large grammar to represent as such) - you can encode the grammar for each of the limits separately with the recursive step lowering some of the limits so that each level is its own regular grammar, and you can then take an intersection (because intersections of regular languages are regular).

I don't think this observation is necessarily very helpful mind you.

[mulkieran]

@DRMacIver I was wrong! The D-Bus signature grammar is LL(1), not regular. I completely lost track of my terms.

[Zac-HD]

I'd try an outer strategy with @st.composite, and an inner recursive function (not the built-in recursive strategy, alas). The inner function is called with the full bounds, draws an allowed value, decrements the bounds, and recurses. This would be messy, but legal-by-construction.

Alternatively, you could just filter the output of a more naive strategy - which might be cheaper and would certainly be easier to implement, at the cost being much less likely to hit weird boundary conditions.

[mulkieran]

This won't be addressed before version 0.6.