Liking cljdoc? Tell your friends :D

malli.impl.regex

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.

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`.
raw docstring

*-explainerclj/s

(*-explainer p)
source

*-parserclj/s

(*-parser p)
source

*-transformerclj/s

(*-transformer p)
source

*-validatorclj/s

(*-validator p)
source

+-explainerclj/s

(+-explainer p)
source

+-parserclj/s

(+-parser p)
source

+-transformerclj/s

(+-transformer p)
source

+-validatorclj/s

(+-validator p)
source

-park-explainer!clj

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

-park-transformer!clj

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

-park-validator!clj

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

?-explainerclj/s

(?-explainer p)
source

?-parserclj/s

(?-parser p)
source

?-transformerclj/s

(?-transformer p)
source

?-validatorclj/s

(?-validator p)
source

alt*-parserclj/s

(alt*-parser [tag r])
(alt*-parser kr & krs)
source

alt-explainerclj/s

(alt-explainer ?kr)
(alt-explainer ?kr ?kr*)
(alt-explainer ?kr ?kr* & ?krs)
source

alt-parserclj/s

(alt-parser r)
(alt-parser r & rs)
source

alt-transformerclj/s

(alt-transformer ?kr)
(alt-transformer ?kr ?kr*)
(alt-transformer ?kr ?kr* & ?krs)
source

alt-validatorclj/s

(alt-validator ?kr)
(alt-validator ?kr ?kr*)
(alt-validator ?kr ?kr* & ?krs)
source

cat*-parserclj/s

(cat*-parser & krs)
source

cat-explainerclj/s

(cat-explainer)
(cat-explainer ?kr)
(cat-explainer ?kr ?kr*)
(cat-explainer ?kr ?kr* & ?krs)
source

cat-parserclj/s

(cat-parser & rs)
source

cat-transformerclj/s

(cat-transformer)
(cat-transformer ?kr)
(cat-transformer ?kr ?kr*)
(cat-transformer ?kr ?kr* & ?krs)
source

cat-validatorclj/s

(cat-validator)
(cat-validator ?kr)
(cat-validator ?kr ?kr*)
(cat-validator ?kr ?kr* & ?krs)
source

end-explainerclj/s

(end-explainer schema path)
source

end-parserclj/s

(end-parser)
source

end-transformerclj/s

(end-transformer)
source

end-validatorclj/s

(end-validator)
source

ensure-cached!clj

(ensure-cached! cache f pos regs)
source

explainerclj/s

(explainer schema path p)
source

fail!clj

(fail! self pos errors*)
source

fmapclj/s

(fmap f p)
source

item-decoderclj/s

(item-decoder decode valid?)
source

item-encoderclj/s

(item-encoder valid? encode)
source

item-explainerclj/s

(item-explainer path schema schema-explainer)
source

item-parserclj/s

(item-parser parse)
source

item-transformerclj/s

(item-transformer method validator t)
source

item-validatorclj/s

(item-validator valid?)
source

latest-errorsclj

(latest-errors self)
source

park-explainer!clj

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

park-transformer!clj

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

park-validator!clj

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

parserclj/s

(parser p)
source

pop-thunk!clj

(pop-thunk! self)
source

pure-parserclj/s

(pure-parser v)
source

repeat-explainerclj/s

(repeat-explainer min max p)
source

repeat-parserclj/s

(repeat-parser min max p)
source

repeat-transformerclj/s

(repeat-transformer min max p)
source

repeat-validatorclj/s

(repeat-validator min max p)
source

succeed!clj

(succeed! self)
source

succeed-with!clj

(succeed-with! self v)
source

succeeded?clj

(succeeded? self)
source

success-resultclj

(success-result self)
source

transformerclj/s

(transformer p)
source

validatorclj/s

(validator p)
source

value-pathclj

(value-path self pos)
source

cljdoc is a website building & hosting documentation for Clojure/Script libraries

× close