Problem statement: Some spec implementations return no generator but nil, in their gen* implementation when their *recursion-limit* has been reached (e. g. s/or). Specs that implement composition of other specs sometimes respect getting no generator from other specs gen* and adjust behavior of their own gen* accordingly, sometimes to the extent of returning nothing themselves (e. g. s/or's gen* returns nil if of all of its branches specs also don't have a gen and otherwise uses only those gens it got). However, there are various specs that don't respect getting no generator from gen* (like s/every, s/map-of) and they are essential building blocks in many real world recursive specifications. They then end up throwing an exception "Unable to construct gen ...".
Here is a minimal example (not real world usecase illustration) of the problem with actual specs:
;; A ::B is an s/or with branches going through ::B recursively
(s/def ::B (s/or :A ::A))
;; An ::A is a map of keywords to ::Bs (or it is empty as recursive termination)
(s/def ::A (s/map-of keyword? ::B
:gen-max 3))
(gen/sample (s/gen ::A))
ExceptionInfo Unable to construct gen at: [1 :A 1 :A 1 :A 1 :A 1] for: :spec.examples.tree/B clojure.core/ex-info (core.clj:4725)
Valid values for the spec above (I can mail you a real usecase that enforces above pattern in which we parse an internal query DSL) are: {}, {:a {}}, {:foo {:bar {}}} etc.
The problem why the current implementation of spec fails to generate values for above spec is that ::A's map-of doesn't generate an empty map when ::B's gen* returns nil, but instead throws an exception. s/every and all derived specs are affected by this and there might be others.
Proposed fix: A spec's gen* impl must always respect other spec's gen* returning nil not by throwing but by either adjusting the returned gen or by returning nil itself so that the not-returning-gen behavior propagates back to the caller where an exception should be thrown instead.
