malli.impl.regex — org.clojars.alexandergunnarson/malli 8289dd6d53b4140d0c94d19cc778992776ee074f

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.

*-explainer clj/s

(*-explainer p)

*-parser clj/s

(*-parser p)

*-transformer clj/s

(*-transformer p)

*-validator clj/s

(*-validator p)

+-explainer clj/s

(+-explainer p)

+-parser clj/s

(+-parser p)

+-transformer clj/s

(+-transformer p)

+-validator clj/s

(+-validator p)

-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)

?-explainer clj/s

(?-explainer p)

?-parser clj/s

(?-parser p)

?-transformer clj/s

(?-transformer p)

?-validator clj/s

(?-validator p)

alt*-parser clj/s

(alt*-parser [tag r])

(alt*-parser kr & krs)

alt-explainer clj/s

(alt-explainer ?kr)

(alt-explainer ?kr ?kr*)

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

alt-parser clj/s

(alt-parser r)

(alt-parser r & rs)

alt-transformer clj/s

(alt-transformer ?kr)

(alt-transformer ?kr ?kr*)

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

alt-validator clj/s

(alt-validator ?kr)

(alt-validator ?kr ?kr*)

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

cat*-parser clj/s

(cat*-parser & krs)

cat-explainer clj/s

(cat-explainer)

(cat-explainer ?kr)

(cat-explainer ?kr ?kr*)

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

cat-parser clj/s

(cat-parser & rs)

cat-transformer clj/s

(cat-transformer)

(cat-transformer ?kr)

(cat-transformer ?kr ?kr*)

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

cat-validator clj/s

(cat-validator)

(cat-validator ?kr)

(cat-validator ?kr ?kr*)

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

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 clj/s

(fmap 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-validator clj/s

(item-validator valid?)

latest-errors clj

(latest-errors self)

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)

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-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)