Add schema simplification / worker optimization

[bsless]

Schemas that contain choice need to backtrack when validation or coercion fail. As schemas get larger and more complicated, this can result in redundant work.

Proposed solution, using boolean algebra notation:

( A B ) + (A C) -> A (B +C)

This can be done trivially for validation, and with some care for transformation as well.

Users might want to trade off compile time for run time, so it should be configurable.

Also see: https://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm

[opqdonut]

See also: https://github.com/miikka/boolean-simplifier

[frenchy64]

I've been experimenting in this direction. The idea is to have a new namespace malli.solver that returns returns descriptions of values that satisfy schemas. This intermediate representation is then used to create more direct predicates and generators.

For example, all these schemas mean the same thing:

  (is (= [{:type :map, :open-map true}]
         (solver/solve [:map])
         (solver/solve [:map {:closed false}])
         (solver/solve [:map [::m/default [:map]]])
         (solver/solve [:map {:closed false} [::m/default [:map]]])
         (solver/solve [:map {:closed true} [::m/default [:map]]])))

Then we can create a predicate with a lot more information at our disposal.

;; malli.optimize
(defmethod -solution-validator :map
  [{:keys [open-map] :as solution} options]
  (if open-map
    (-validate-map-linearly solution options)
    (-validate-map-via-lookup solution options)))

Also works for integer constraints:

  (is (= [{:type :number, :>-number -1}] (solver/solve [:and [:> -1] [:>= -1]] nil)))
  (is (= [{:type :number, :<-number -1}] (solver/solve [:and [:< -1] [:<= -1]] nil)))
  (is (= [{:type :number, :max-number 0, :min-number 0}] (solver/solve zero?)))

;; malli.optimize
(defn- -min-max-validator [{:keys [min-number max-number >-number <-number]}]
  (when (or min-number max-number >-number <-number)
    (miu/-every-pred
      (into (if (and min-number (= min-number max-number))
              [#(= min-number %)]
              (cond-> []
                min-number (conj #(<= min-number %))
                >-number (conj #(< >-number %))
                max-number (conj #(<= % max-number))
                <-number (conj #(< % <-number))))))))
(defmethod -solution-validator :number
  [solution _]
  (let [mmv (-min-max-validator solution)]
    (miu/-every-pred
      (cond-> [number?]
        mmv (conj mmv)))))

The branch is a bit messy since it includes #1161, which has been extracted and proposed upstream:

https://github.com/frenchy64/malli/pull/23/files