malli.impl.regex — metosin/malli 0.16.4

Regular expressions of sequences implementation namespace.

The implementation is very similar to Packrat or GLL parser combinators. The parsing functions need to be written in CPS to support backtracking inside :, :+ and :repeat. They also need to be trampolined because the (manually) CPS-converted code (for :, :+ and :repeat) has to use tail calls instead of loops and Clojure does not have TCO.

Because backtracking is used we need to memoize (parsing function, seq position, register stack) triples to avoid exponential behaviour. Discarding the memoization cache after traversing an input seq also requires trampolining. Because regular expressions don't use (nontail) recursion by definition, finding a memoization entry just means the parser already went 'here' and ultimately failed; much simpler than the graph-structured stacks of GLL. And the register stack is only there for and used by :repeat.

NOTE: For the memoization to work correctly, every node in the schema tree must get its own validation/explanation/... function instance. So even every (malli.impl.regex/cat) call must return a new fn instance although it does not close over anything.

https://epsil.github.io/gll/ is a nice explanation of GLL parser combinators and has links to papers etc. It also inspired Instaparse, which Engelberg had a presentation about at Clojure/West 2014.

Despite the CPS and memoization, this implementation looks more like normal Clojure code than the 'Pike VM' in Seqexp. Hopefully JITs also see it that way and compile decent machine code for it. It is also much easier to extend for actual parsing (e.g. encode, decode [and parse?]) instead of just recognition for validate.

For a more detailed explanation of this namespace see also https://www.metosin.fi/blog/malli-regex-schemas/.

*-explainer clj/s

(*-explainer p)

*-parser clj/s

(*-parser p)

*-transformer clj/s

(*-transformer p)

*-unparser clj/s

(*-unparser up)

*-validator clj/s

(*-validator p)

+-explainer clj/s

(+-explainer p)

+-parser clj/s

(+-parser p)

+-transformer clj/s

(+-transformer p)

+-unparser clj/s

(+-unparser up)

+-validator clj/s

(+-validator p)

?-explainer clj/s

(?-explainer p)

?-parser clj/s

(?-parser p)

?-transformer clj/s

(?-transformer p)

?-unparser clj/s

(?-unparser p)

?-validator clj/s

(?-validator p)

alt-explainer clj/s

(alt-explainer ?kr & ?krs)

alt-parser clj/s

(alt-parser & rs)

alt-transformer clj/s

(alt-transformer ?kr & ?krs)

alt-unparser clj/s

(alt-unparser & unparsers)

alt-validator clj/s

(alt-validator ?kr & ?krs)

altn-parser clj/s

(altn-parser kr & krs)

altn-unparser clj/s

(altn-unparser & unparsers)

cat-explainer clj/s

(cat-explainer)

(cat-explainer ?kr & ?krs)

cat-parser clj/s

(cat-parser)

(cat-parser r & rs)

cat-transformer clj/s

(cat-transformer)

(cat-transformer ?kr & ?krs)

cat-unparser clj/s

(cat-unparser & unparsers)

cat-validator clj/s

(cat-validator)

(cat-validator ?kr & ?krs)

catn-parser clj/s

(catn-parser)

(catn-parser kr & krs)

catn-unparser clj/s

(catn-unparser & unparsers)

end-explainer clj/s

(end-explainer schema path)

end-parser clj/s

(end-parser)

end-transformer clj/s

(end-transformer)

end-validator clj/s

(end-validator)

ensure-cached! clj

(ensure-cached! cache f pos regs)

explainer clj/s

(explainer schema path p)

fail! clj

(fail! self pos errors*)

fmap-parser clj/s

(fmap-parser f p)

item-decoder clj/s

(item-decoder decode valid?)

item-encoder clj/s

(item-encoder valid? encode)

item-explainer clj/s

(item-explainer path schema schema-explainer)

item-parser clj/s

(item-parser parse)

item-transformer clj/s

(item-transformer method validator t)

item-unparser clj/s

(item-unparser unparse)

item-validator clj/s

(item-validator valid?)

latest-errors clj

(latest-errors self)

noncaching-park-explainer! clj

(noncaching-park-explainer! driver explainer regs pos coll k)

noncaching-park-transformer! clj

(noncaching-park-transformer! driver transformer regs coll* pos coll k)

noncaching-park-validator! clj

(noncaching-park-validator! driver validator regs pos coll k)

park-explainer! clj

(park-explainer! driver explainer regs pos coll k)

park-transformer! clj

(park-transformer! driver transformer regs coll* pos coll k)

park-validator! clj

(park-validator! driver validator regs pos coll k)

parser clj/s

(parser p)

pop-thunk! clj

(pop-thunk! self)

pure-parser clj/s

(pure-parser v)

pure-unparser clj/s

(pure-unparser _)

repeat-explainer clj/s

(repeat-explainer min max p)

repeat-parser clj/s

(repeat-parser min max p)

repeat-transformer clj/s

(repeat-transformer min max p)

repeat-unparser clj/s

(repeat-unparser min max up)

repeat-validator clj/s

(repeat-validator min max p)

succeed! clj

(succeed! self)

succeed-with! clj

(succeed-with! self v)

succeeded? clj

(succeeded? self)

success-result clj

(success-result self)

transformer clj/s

(transformer p)

validator clj/s

(validator p)

value-path clj

(value-path self pos)