Clojure

s/coll-of and s/every take unnecessary long to generate if :into not provided

Details

  • Type: Defect Defect
  • Status: Open Open
  • Priority: Major Major
  • Resolution: Unresolved
  • Affects Version/s: Release 1.9
  • Fix Version/s: None
  • Component/s: None
  • Labels:
  • Environment:
    alpha14

Description

(s/def ::bar (s/coll-of number? :kind vector?))

(defn foo [a]
  (reduce + 0 a))

(s/fdef foo
  :args (s/cat :a ::bar)
  :ret number?)

(first (stest/check `foo))

Doesn't terminate in a reasonable amount of time.
One observes that changing :gen-max doesn't affect computation time.

One observes that it can be fixed by adding :into [] to the s/coll-of spec.

The reason is this: If :into is not provided, s/every and s/coll-of has to generate a vector (via gen of vector?) to call empty on it, to then fill it up. This is quite clearly documented in the docstring of `s/every`:

:kind - a pred/spec that the collection type must satisfy, e.g. vector?
         (default nil) Note that if :kind is specified and :into is
         not, this pred must generate in order for every to generate.

Assumedly the vector? generates quite large vectors at a certain point which significantly slows down the generation.

The responsible code is in gen* of every-impl

(gen/bind
 (cond
  gen-into (gen/return (empty gen-into))
  kind (gen/fmap #(if (empty? %) % (empty %))
                 (gensub kind overrides path rmap form))  ;; creating and mapping gen of :kind
 :else (gen/return []))
 (fn [init]
    ....

Activity

Hide
Leon Grapenthin added a comment -

I see two approaches to improve this behavior:

1. The gen uses the gen of kind to generate one value with the smallest size, calls empty on it to determine :into. This would lead to a surprise when your :kind is e. g. (s/or :a-vec vector? :a-list list?) (which currently throws, anyway)
2. We use an internal lookup table to assume :into. {clojure.core/vector? [], clojure.core/set? #{} ...}

Show
Leon Grapenthin added a comment - I see two approaches to improve this behavior: 1. The gen uses the gen of kind to generate one value with the smallest size, calls empty on it to determine :into. This would lead to a surprise when your :kind is e. g. (s/or :a-vec vector? :a-list list?) (which currently throws, anyway) 2. We use an internal lookup table to assume :into. {clojure.core/vector? [], clojure.core/set? #{} ...}

People

Vote (1)
Watch (1)

Dates

  • Created:
    Updated: