You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
This is because even though the depth parameter prevents this from going into an infinite loop, the derive implementation always calls size_hint once per field member even if they are of the same type. That makes the complexity close to $witdth^{recursion_depth}$, which here corresponds to $9^{20}$
Ideally the solution would be to somehow memoize the results of the calls to size_hint for each type but I don't see how to do that without having to add Any bounds everywhere. I tried implementing an unintrusive way to bail out when recursion is detected in https://github.com/sgued/arbitrary/tree/recursive-size-hint but it still doesn't solve every problem.
I think the most simple solution would be to make size_hint fallible and return an error in case of recursion. This would make it possible to bail out early for all implementations. It would still be easily possible to get the always correct (0, None) value by using unwrap_or_default. This would however be a breaking change.
Another solution I can think of would be to provide a way to override the size_hint implementation by something that always return (0, None)
The text was updated successfully, but these errors were encountered:
Calling
size_hint
on a "wide" recursive struct or enum is extremely slow. Examples:This is because even though the$witdth^{recursion_depth}$ , which here corresponds to $9^{20}$
depth
parameter prevents this from going into an infinite loop, the derive implementation always callssize_hint
once per field member even if they are of the same type. That makes the complexity close toIdeally the solution would be to somehow memoize the results of the calls to
size_hint
for each type but I don't see how to do that without having to addAny
bounds everywhere. I tried implementing an unintrusive way to bail out when recursion is detected in https://github.com/sgued/arbitrary/tree/recursive-size-hint but it still doesn't solve every problem.I think the most simple solution would be to make
size_hint
fallible and return an error in case of recursion. This would make it possible to bail out early for all implementations. It would still be easily possible to get the always correct(0, None)
value by usingunwrap_or_default
. This would however be a breaking change.Another solution I can think of would be to provide a way to override the
size_hint
implementation by something that always return(0, None)
The text was updated successfully, but these errors were encountered: