Debian Codegraph @

ext/peg/peg.scm

raw
1 ;;;
2 ;;; peg.scm - Parser Expression Grammar Parser
3 ;;;
4 ;;; Copyright (c) 2006 Rui Ueyama ([email protected])
5 ;;; Copyright (c) 2008-2024 Shiro Kawai <[email protected]>
6 ;;;
7 ;;; Redistribution and use in source and binary forms, with or without
8 ;;; modification, are permitted provided that the following conditions
9 ;;; are met:
10 ;;;
11 ;;; 1. Redistributions of source code must retain the above copyright
12 ;;; notice, this list of conditions and the following disclaimer.
13 ;;;
14 ;;; 2. Redistributions in binary form must reproduce the above copyright
15 ;;; notice, this list of conditions and the following disclaimer in the
16 ;;; documentation and/or other materials provided with the distribution.
17 ;;;
18 ;;; 3. Neither the name of the authors nor the names of its contributors
19 ;;; may be used to endorse or promote products derived from this
20 ;;; software without specific prior written permission.
21 ;;;
22 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
25 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
26 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
27 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
28 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
29 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
30 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
31 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
32 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33 ;;;
34
35 (define-module parser.peg
36 (use scheme.list)
37 (use scheme.charset)
38 (use srfi.13)
39 (use gauche.collection)
40 (use gauche.generator)
41 (use gauche.lazy)
42 (use text.tree)
43 (use util.match)
44 (export <parse-error>
45 make-peg-parse-error
46
47 peg-run-parser
48 peg-parse-string peg-parse-port
49 peg-parser->generator peg-parser->lseq
50
51 parse-success?
52 return-result return-failure
53 return-failure/expect return-failure/unexpect
54 return-failure/message return-failure/compound
55
56 $bind $return $fail $expect $lift $lift* $debug
57 $let $let* $try $assert $not
58 $or $fold-parsers $fold-parsers-right
59 $seq $seq0 $list $list* $between
60 $many $many1 $many_ $many1_ $repeat $repeat_
61 $many-till $many-till_
62 $optional
63 $sep-by $end-by $sep-end-by
64 $chain-left $chain-right
65 $lazy $parameterize
66
67 $cut $raise
68
69 $any $eos $.
70
71 $string $string-ci
72 $char $one-of $none-of
73 $satisfy $match1 $match1*
74 $binding $lbinding
75
76 $->rope $->string $->symbol rope->string rope-finalize
77 )
78 )
79
80 (select-module parser.peg)
81
82 ;;;============================================================
83 ;;; How is EBNF represented in the PEG library?
84 ;;;
85 ;;; A ::= B C
86 ;;; => (define a ($seq b c))
87 ;;; If you need values of B and C, use monadic macro $let, or applicative
88 ;;; combinator $lift
89 ;;; => (define a ($let ([x b] [y c]) ($return (cons x y))))
90 ;;; => (define a ($lift cons b c)
91 ;;;
92 ;;; A :: B | C
93 ;;; => (define a ($or b c))
94 ;;; To be precise, this actually mean B / C in PEG; if B fails without
95 ;;; consuming input, we try C. But if B ever consumes input, we don't
96 ;;; backtrack and A fails. If you want backtracking, use $try as well.
97 ;;; => (define a ($or ($try b) c))
98 ;;;
99 ;;; A :: B*
100 ;;; => (define a ($many b))
101 ;;; A :: B+
102 ;;; => (define a ($many b 1))
103 ;;; A ::= B B | B B B
104 ;;; => (define a ($many b 2 3))
105 ;;; '$many' gathers the semantic values of B into list. One common case
106 ;;; is that you want a string out of gathered values. $->string is a
107 ;;; combinator that just translates the semantic value.
108 ;;; => (define a ($->string ($many b)))
109 ;;; If the result of a is further gathered, it is wasteful to make it
110 ;;; a string, since it will be thrown away soon. We have an efficient
111 ;;; intermediate string representation called rope. Here you can make
112 ;;; the result of a as rope:
113 ;;; => (define a ($->rope ($many b)))
114 ;;; Later, you can concatenate and convert ropes to a string by
115 ;;; rope->string.
116 ;;; If you don't need the values, you can use $many_ instead, which
117 ;;; is more efficient.
118 ;;;
119 ;;; A ::= B?
120 ;;; => (define a ($optional b))
121 ;;;
122 ;;;
123
124
125 ;;; In this module, we provide various constructors of PARSERs,
126 ;;; and DRIVER procedures.
127 ;;;
128 ;;; A PARSER is merely a closure that takes a list of input (most
129 ;;; likely it's a lazy sequence of characters, but it can be a
130 ;;; list of anything), and returns three results:
131 ;;;
132 ;;; Status: #f if parse is successful, or a symbol to indicate
133 ;;; a kind of error.
134 ;;; Value: parsed value, or error message.
135 ;;; Next: a list of next input.
136 ;;;
137 ;;; That is,
138 ;;; Parser :: [a] -> (Status, Value, [a])
139 ;;;
140 ;;; Failure status and value
141 ;;;
142 ;;; status value
143 ;;; ------------------------------------------------
144 ;;; fail-message string (message)
145 ;;; fail-expect string (message), char, char-set
146 ;;; fail-unexpect string (message)
147 ;;; fail-compound ((Status . Value) ...)
148 ;;; fail-error (tag (Status . Value ...))
149 ;;;
150 ;;; A DRIVER is a wrapper to take a parser and an input.
151 ;;; DRIVER applies the parser on the input, and on success, it returns the
152 ;;; value and the rest of the input. On failure, it translates the error
153 ;;; status into <parser-error> object and raises it.
154 ;;;
155
156 ;;;============================================================
157 ;;; Parse result types
158 ;;;
159
160 ;; An error object for the external API. Note that a parser won't raise
161 ;; this error; it just returns a 'failure' value, so that other options
162 ;; can be tried if there's any. Creating, throwing, and catching an error
163 ;; is expensive operation compared to the simple call/return. It is the
164 ;; parser driver that sees the failure as the final result, and constructs
165 ;; <parse-error> to raise.
166 ;; NB: 'Token' slot is (car rest) or #<eof>. It's redundant, but kept for
167 ;; the backward compatibility.
168 (define-condition-type <parse-error> <error> #f
169 (position) ;stream position
170 (type) ;fail type
171 (objects) ;expecting/unexpecting items
172 (token) ;token that caused error
173 (rest)) ;rest of input string, including token
174
175 (define-method write-object ((o <parse-error>) out)
176 (format out "#<<parse-error> ~S>" (~ o 'message)))
177
178 ;; Primitive parts to be used inside custom parser.
179 ;; The user usually doesn't need to use them, as long as he construct
180 ;; parsers by parser combinators.
181 (define-inline (parse-success? x) (not x))
182
183 (define-inline (return-result v s) (values #f v s))
184 (define-hybrid-syntax return-failure
185 (^[t v s] (values t v s))
186 ;; If type is given as a literal symbol, we statically check it.
187 (er-macro-transformer
188 (^[f r c]
189 (match f
190 [(_ ('quote x) v s)
191 (unless (memq x '(fail-message fail-expect fail-unexpect
192 fail-error fail-compound))
193 (error "Invalid failure type; must be one of fail-message, \
194 fail-expect, fail-unexpect, fail-compund or \
195 fail-error, but got: " x))
196 (quasirename r
197 `(values ',x ,v ,s))]
198 [(_ t v s)
199 (quasirename r
200 `(values ,t ,v ,s))]
201 [_ f]))))
202 (define-inline (return-failure/message v s) (values 'fail-message v s))
203 (define-inline (return-failure/expect v s) (values 'fail-expect v s))
204 (define-inline (return-failure/unexpect v s) (values 'fail-unexpect v s))
205 (define-inline (return-failure/compound v s) (values 'fail-compound v s))
206 (define (return-error-from-failure tag failure payload s)
207 (case failure
208 [(fail-error) (match-let1 (_ . alist) payload
209 (values 'fail-error `(,tag . ,alist) s))]
210 [else (values 'fail-error `(,tag (,failure . ,payload)) s)]))
211
212 (define (make-peg-parse-error type objs pos seq)
213 (define (flatten-compound-error objs)
214 (append-map (^e (if (eq? (car e) 'fail-compound)
215 (flatten-compound-error (cdr e))
216 (list e)))
217 objs))
218 (define (analyze-compound-error objs pos)
219 (let1 grps (map (^g (cons (caar g) (map cdr g)))
220 (group-collection (flatten-compound-error objs) :key car))
221 (let ([msgs (assoc-ref grps 'fail-message)]
222 [exps (assoc-ref grps 'fail-expect)]
223 [unexps (assoc-ref grps 'fail-unexpect)])
224 (tree->string
225 (cons (or-concat (cond-list
226 [exps (compound-exps exps)]
227 [unexps (compound-unexps unexps)]
228 [msgs msgs]))
229 (format " at ~a" pos))))))
230 (define (or-concat lis)
231 (define (rec lis)
232 (match lis
233 [(x y) `("(",x") or (",y")")]
234 [(x . more) `("(",x"), ",@(rec more))]))
235 (match lis
236 [() '()]
237 [(x) `(,x)]
238 [xs (rec xs)]))
239 (define (compound-exps exps)
240 (match (delete-duplicates exps equal?)
241 [(x) (format "expecting ~s" x)]
242 [(xs ...) (format "expecting one of ~s" xs)]))
243 (define (compound-unexps unexps)
244 (match (delete-duplicates unexps equal?)
245 [(x) (format "not expecting ~s" x)]
246 [(xs ...) (format "not expecting any of ~s" xs)]))
247 (define pos-fmt
248 (if (sequence-position? pos)
249 (format "~s:~a:~a"
250 (or (sequence-position-source pos) "(unknown input)")
251 (sequence-position-line pos)
252 (sequence-position-column pos))
253 pos))
254 (define (message objs pos nexttok)
255 (case type
256 [(fail-message) (format "~a at ~a" objs pos-fmt)] ;objs is a string message
257 [(fail-expect)
258 (if (char? objs)
259 (format "expecting ~s at ~a, but got ~s" objs pos-fmt nexttok)
260 (format "expecting ~a at ~a, but got ~s" objs pos-fmt nexttok))]
261 [(fail-unexpect)
262 (if (char? objs)
263 (format "expecting but ~s at ~a, and got ~s" objs pos-fmt nexttok)
264 (format "expecting but ~a at ~a, and got ~s" objs pos-fmt nexttok))]
265 [(fail-compound) (analyze-compound-error objs pos)]
266 [(fail-error) (analyze-compound-error (cdr objs) pos)] ;car is a tag
267 [else (format "unknown parser error at ~a: ~a" pos-fmt objs)] ;for safety
268 ))
269 (let ([nexttok (if (pair? seq) (car seq) (eof-object))])
270 (make-condition <parse-error>
271 'position pos 'type type 'objects objs
272 'token nexttok 'rest seq
273 'message (message objs pos nexttok))))
274
275 (define (%get-input-pos head s)
276 (or (lseq-position s)
277 (let loop ([c 0] [head head])
278 (cond [(eq? head s) c]
279 [(null? head) "(unknown position)"]
280 [else (loop (+ c 1) (cdr head))]))))
281
282 (define (construct-peg-parser-error r v s s1)
283 (make-peg-parse-error r v (%get-input-pos s s1) s1))
284
285 ;; API
286 ;; Default driver. Returns parsed value and next stream
287 (define (peg-run-parser parser s)
288 (receive (r v s1) (parser s)
289 (if (parse-success? r)
290 (values (rope-finalize v) s1)
291 (raise (construct-peg-parser-error r v s s1)))))
292
293 ;; Coerce something to lseq. accepts generator.
294 ;; We check applicability of x->lseq first, since an object can be both
295 ;; passed to x->lseq and applicable as a thunk, but x->lseq should take
296 ;; precedence.
297 ;; NB: This is not abstract enough---the gory details should be hidden
298 ;; in gauche.lazy module.
299 (define (%->lseq obj)
300 (cond [(eq? (class-of obj) <pair>) obj] ;avoid forcing a lazy pair
301 [(applicable? x->generator (class-of obj))
302 (generator->lseq (x->generator obj))]
303 [(applicable? obj) (generator->lseq obj)]
304 [else (error "object cannot be used as a source of PEG parser:" obj)]))
305
306 ;; API
307 ;; NB: We can consolidate peg-parse-string and peg-parse-port via
308 ;; x->generator, but should we?
309 (define (peg-parse-string parser str :optional (cont #f))
310 (check-arg string? str)
311 (receive (r rest) (peg-run-parser parser (x->lseq str))
312 (if cont
313 (cont r rest)
314 r)))
315 ;; API
316 (define (peg-parse-port parser port :optional (cont #f))
317 (check-arg input-port? port)
318 (receive (r rest) (peg-run-parser parser (x->lseq port))
319 (if cont
320 (cont r rest)
321 r)))
322
323 ;; API
324 ;; Returns a generator
325 (define (peg-parser->generator parser src)
326 (let1 s (%->lseq src)
327 (^[] (if (null? s)
328 (eof-object)
329 (receive (r v s1) (parser s)
330 (cond [(not (parse-success? r))
331 (raise (construct-peg-parser-error r v s s1))]
332 [(eof-object? v) (set! s '()) v]
333 [else (set! s s1) (rope-finalize v)]))))))
334
335 ;; API
336 ;; Returns an lseq
337 ;; Input position info is propagated if available
338 (define (peg-parser->lseq parser src)
339 (let1 s (%->lseq src)
340 (generator->lseq
341 (^[] (if (null? s)
342 (eof-object)
343 (receive (r v s1) (parser s)
344 ;; TODO: Refactor this part and similar part above
345 (let1 val (cond [(not (parse-success? r))
346 (raise (construct-peg-parser-error r v s s1))]
347 [(eof-object? v) (set! s '()) v]
348 [else (set! s s1) (rope-finalize v)])
349 (if-let1 pos (lseq-position s)
350 (values val pos)
351 val))))))))
352
353 ;;;============================================================
354 ;;; Lazily-constructed string
355 ;;;
356
357 (define-inline (make-rope obj)
358 (cons 'rope obj))
359
360 (define-inline (rope? obj)
361 (and (pair? obj) (eq? (car obj) 'rope)))
362
363 (inline-stub
364 (define-cfn rope2string_int (obj p) ::void :static
365 (label restart)
366 (cond [(SCM_STRINGP obj) (SCM_PUTS obj p)]
367 [(SCM_CHARP obj) (SCM_PUTC (SCM_CHAR_VALUE obj) p)]
368 [(SCM_PAIRP obj)
369 (when (SCM_EQ (SCM_CAR obj) 'rope)
370 (set! obj (SCM_CDR obj)) (goto restart))
371 (for-each (lambda (elt)
372 (cond [(SCM_STRINGP elt) (SCM_PUTS elt p)]
373 [(SCM_CHARP elt) (SCM_PUTC (SCM_CHAR_VALUE elt) p)]
374 [else (rope2string_int elt p)]))
375 obj)]
376 [(not (or (SCM_NULLP obj) (SCM_FALSEP obj)))
377 (Scm_Error "rope->string: unknown object to write: %S" obj)]))
378
379 (define-cproc rope->string (obj)
380 (let* ([p (Scm_MakeOutputStringPort TRUE)])
381 (rope2string_int obj p)
382 (return (Scm_GetOutputString (SCM_PORT p) 0))))
383 )
384
385 ;;;============================================================
386 ;;; Primitives
387 ;;;
388
389 (define-inline ($return val) (^s (return-result val s)))
390
391 (define ($fail msg) (^s (return-failure/message msg s)))
392
393 (define $raise
394 (case-lambda
395 [(tag msg)
396 (^s (return-failure 'fail-error `(,tag (fail-message . ,msg)) s))]
397 [(msg)
398 (^s (return-failure 'fail-error `(error (fail-message . ,msg)) s))]))
399
400 ;; return a parser that tries PARSE. On success, returns what it
401 ;; returned. On failure, returns 'fail-expect with MSG.
402 (define ($expect parse msg)
403 (^s (receive (r v ss) (parse s)
404 (if (parse-success? r)
405 (return-result v ss)
406 (return-failure/expect msg ss)))))
407
408 ;; A convenience utility to check the upper bound, allowing unlimited
409 ;; upper bound by #f.
410 (define-inline (>=? count max) (and max (>= count max)))
411
412 ;;;============================================================
413 ;;; Combinators
414 ;;;
415
416 ;; API
417 ;; p :: Parser
418 ;; f :: Value -> Parser
419 ;; $bind :: Parser, (Value -> Parser) -> Parser
420 (define-inline ($bind p f)
421 (^s (receive [r v s1] (p s)
422 (if (parse-success? r)
423 ((f v) s1)
424 (return-failure r v s1)))))
425
426 ;; API
427 ;; $lift :: (a,...) -> b, (Parser,..) -> Parser
428 ;; ($lift f parser) == ($let ([x parser]) ($return (f x)))
429 ;;
430 ;; $lift* is like $lift, but f gets semantic values as a single list.
431 ;;
432 ;; The number of parsers is almost always fixed, and we macro-expand into
433 ;; chain of parser calls in such cases.
434
435 ;; Aux function for macro expander
436 (define (expand-$lift *?)
437 )
438
439 (define-hybrid-syntax $lift
440 (^[f . parsers]
441 ;; We don't use the straightforward definition (using $let or $bind)
442 ;; to reduce closure construction.
443 (^s (let accum ([s s] [parsers parsers] [vs '()])
444 (if (null? parsers)
445 (return-result (apply f (reverse vs)) s)
446 (receive [r v s1] ((car parsers) s)
447 (if (parse-success? r)
448 (accum s1 (cdr parsers) (cons v vs))
449 (return-failure r v s1)))))))
450 (er-macro-transformer
451 (^[f r c]
452 (define (generate-1 fn vs ps s)
453 (if (null? ps)
454 (quasirename r `(return-result (,fn ,@(reverse vs)) ,s))
455 (let* ([v1 (gensym "v")]
456 [inner (generate-1 fn (cons v1 vs) (cdr ps) s)])
457 (quasirename r `(receive [res ,v1 ,s] (,(car ps) ,s)
458 (if (parse-success? res)
459 ,inner
460 (return-failure res ,v1 ,s)))))))
461 (match f
462 [(_ fn . ps)
463 (let1 s (r's)
464 (quasirename r
465 `(^[,s] ,(generate-1 fn '() ps s))))]
466 [_ f]))))
467
468 (define-hybrid-syntax $lift*
469 (^[f . parsers]
470 (^s (let accum ([s s] [parsers parsers] [vs '()])
471 (if (null? parsers)
472 (return-result (f (reverse vs)) s)
473 (receive [r v s1] ((car parsers) s)
474 (if (parse-success? r)
475 (accum s1 (cdr parsers) (cons v vs))
476 (return-failure r v s1)))))))
477 (er-macro-transformer
478 (^[f r c]
479 (define (generate-1 fn vs ps s)
480 (if (null? ps)
481 (quasirename r `(return-result (,fn (list ,@(reverse vs))) ,s))
482 (let* ([v1 (gensym "v")]
483 [inner (generate-1 fn (cons v1 vs) (cdr ps) s)])
484 (quasirename r `(receive [res ,v1 ,s] (,(car ps) ,s)
485 (if (parse-success? res)
486 ,inner
487 (return-failure res ,v1 ,s)))))))
488 (match f
489 [(_ fn . ps)
490 (let1 s (r's)
491 (quasirename r
492 `(^[,s] ,(generate-1 fn '() ps s))))]
493 [_ f]))))
494
495 ;; API
496 ;; For debugging
497 (define ($debug name parser)
498 (^s (format (current-error-port) "#?parser(~a)<~,,,,v:s\n"
499 name (debug-print-width) s)
500 (receive [r v s] (parser s)
501 (debug-print-post (list r v s))
502 (values r v s))))
503
504 ;; API
505 ;; Convert failure to error
506 (define $cut
507 (case-lambda
508 [(tag parser) (^s (receive (r v s) (parser s)
509 (if (parse-success? r)
510 (return-result v s)
511 (return-error-from-failure tag r v s))))]
512 [(parser) ($cut 'error parser)]))
513
514 ;; API
515 ;; $let (bind ...) body ...
516 ;; where
517 ;; bind := (var parser)
518 ;; | (parser)
519 ;; | parser
520 ;; var's are visible from body ... (but not from parser)
521 (define-syntax $let
522 (er-macro-transformer
523 (^[f r c]
524 (match f
525 [(_ (bind ...) body ...)
526 (let1 vars&parsers
527 (map (^b (match b
528 [(var parser) `(,var ,(gensym "parser") ,parser)]
529 [(parser) `(,(gensym "_") ,(gensym "parser") ,parser)]
530 [parser `(,(gensym "_") ,(gensym "parser") ,parser)]))
531 bind)
532 (quasirename r
533 `(let (,@(map (^b `(,(cadr b) ,(caddr b))) vars&parsers))
534 ,@(let loop ([vars&parsers vars&parsers])
535 (if (null? vars&parsers)
536 body
537 (match-let1 [(var pvar _) . rest] vars&parsers
538 (quasirename r
539 `(($bind ,pvar (^[,var] ,@(loop rest)))))))))))]
540 [_ (error "Malformed $let:" f)]))))
541
542 ;; API
543 ;; $let* (bind ...) body ...
544 ;; where
545 ;; bind := (var parser)
546 ;; | (parser)
547 ;; | parser
548 ;; var's are visible from subsequent bind and body
549 (define-syntax $let*
550 (er-macro-transformer
551 (^[f r c]
552 (match f
553 [(_ () body ...) (quasirename r `(begin ,@body))]
554 [(_ ((var parser) bind ...) body ...)
555 (quasirename r
556 `($bind ,parser (^[,var] ($let* ,bind ,@body))))]
557 [(_ ((parser) bind ...) body ...)
558 (quasirename r
559 `($bind ,parser (^[,(gensym "_")] ($let* ,bind ,@body))))]
560 [(_ (parser bind ...) body ...)
561 (quasirename r
562 `($bind ,parser (^[,(gensym "_")] ($let* ,bind ,@body))))]
563 [_ (error "Malformed $let*:" f)]))))
564
565 ;; API
566 ;; ($parameterize ((param expr) ..) parser ...)
567 ;; Returns a parser that run parser ... while altering the parameter values
568 ;; like parameterize. The parser ... are run as if in $seq.
569 ;; Suggested by Saito Atsushi
570 (define-syntax $parameterize
571 (er-macro-transformer
572 (^[f r c]
573 (match f
574 [(_ ((p e) ...) parser ...)
575 (let1 tmp (gensym)
576 (quasirename r
577 `(let1 ,tmp ($seq ,@parser)
578 (^[s] (parameterize (,@(map list p e))
579 (,tmp s))))))]))))
580
581 ;; API
582 ;; $or p1 p2 ...
583 ;; $or p1 p2 ... :else pz
584 ;; Ordered choice.
585 ;; When all of p1 p2 ... fail without consuming input, returns compound
586 ;; failure of all of them, except in the latter form, where all the failures
587 ;; before pz is discarded. Usually, pz is ($fail ...) to give a nicer
588 ;; failure message than the compound one.
589 (define ($or . parsers)
590 (define (fail vs s)
591 (match vs
592 [((r . v)) (values r v s)] ;; no need to create compound error
593 [vs (return-failure/compound (reverse vs) s)]))
594 (match parsers
595 [() (^s (return-failure/message "empty $or" s))]
596 [(p) p]
597 [(ps ...)
598 (^s (let loop ([vs '()] [ps ps])
599 (if (eq? (car ps) :else)
600 (if (null? (cdr ps))
601 (error "$or - no parsers after :else")
602 (loop '() (cdr ps))) ;discard previous errors
603 (receive (r v s1) ((car ps) s)
604 (cond [(parse-success? r) (values r v s1)]
605 [(eq? r 'fail-error) (values r v s1)]
606 [(null? (cdr ps))
607 (if (eq? s s1)
608 (fail (acons r v vs) s1)
609 (return-failure r v s1))] ; last branch consumed input
610 [(eq? s s1) (loop (acons r v vs) (cdr ps))]
611 [else (fail (acons r v vs) s1)])))))]))
612
613 ;; API
614 ;; $fold-parsers proc seed parsers
615 ;; $fold-parsers-right proc seed parsers
616 ;; Apply parsers sequentially, passing around seed value.
617 ;; Note: $fold-parsers can be written much simpler (only shown in
618 ;; recursion branch):
619 ;; ($let ([v (car ps)]) ($fold-parsers proc (proc v seed) (cdr ps)))
620 ;; but it needs to create closures at parsing time, rather than construction
621 ;; time. Interestingly, $fold-parsers-right can be written simply
622 ;; without this disadvantage.
623 (define ($fold-parsers proc seed ps)
624 (if (null? ps)
625 ($return seed)
626 (lambda (s)
627 (let loop ((s s) (ps ps) (seed seed))
628 (if (null? ps)
629 (return-result seed s)
630 (receive (r1 v1 s1) ((car ps) s)
631 (if (parse-success? r1)
632 (loop s1 (cdr ps) (proc v1 seed))
633 (return-failure r1 v1 s1))))))))
634
635 ;; API
636 (define ($fold-parsers-right proc seed ps)
637 (match ps
638 [() ($return seed)]
639 [(p . ps) ($lift proc p ($fold-parsers-right proc seed ps))]))
640
641 ;; API
642 ;; $seq P ... Pz
643 ;; Matches P ... Pz sequentially, and returns the result of Pz.
644 ;; To get all the results of p1, p2, ... in a list, use $lift list p1 p2 ...
645 (define ($seq . parsers)
646 ($fold-parsers (^[v s] v) #f parsers))
647
648 ;; API
649 ;; $seq0 P0 P ...
650 ;; Matches P0 P ..., and returns the result of P.
651 (define ($seq0 parse . followers)
652 (apply $lift (^[v . _] v) parse followers))
653
654 ;; API
655 ;; $list P ...
656 ;; $list* P ...
657 ;; Same as ($lift list P ...) and ($list list* P ...), but we see them
658 ;; a lot, so it's worth to have them.
659 (define-inline ($list . parsers) (apply $lift list parsers))
660 (define-inline ($list* . parsers) (apply $lift list* parsers))
661
662 ;; API
663 ;; $try parser
664 ;; Try to match parsers. If it fails, backtrack to
665 ;; the starting position of the stream. So,
666 ;; ($or ($try a)
667 ;; ($try b)
668 ;; ...)
669 ;; would try a, b, ... even some of them consumes the input.
670 (define-inline ($try p)
671 (^[s0] (receive (r v s) (p s0)
672 (cond [(parse-success? r) (return-result v s)]
673 [(eq? r 'fail-error) (return-failure r v s)]
674 [else (return-failure r v s0)]))))
675
676 ;; API
677 ;; $assert parser
678 ;; Match parser, but never consumes the result.
679 ;; On success, the value of the parser is returned.
680 (define-inline ($assert p)
681 (^s (receive (r v s1) (p s)
682 (values r v s))))
683
684 ;; API
685 ;; $not parser
686 ;; Succeeds when the input does not matches parser. The value is #t.
687 ;; If the input matches P, unexpected failure results.
688 ;; Never consumes input.
689 (define ($not p)
690 (^s (receive (r v s1) (p s)
691 (if (parse-success? r)
692 (return-failure/unexpect v s)
693 (return-result #f s)))))
694
695 ;; API
696 (define-syntax $lazy
697 (syntax-rules ()
698 [(_ parse)
699 (let ((p (delay parse)))
700 (lambda (s) ((force p) s)))]))
701
702 ;; alternative $lazy possibility (need benchmark!)
703 ;(define-syntax $lazy
704 ; (syntax-rules ()
705 ; ((_ parse)
706 ; (letrec ((p (lambda (s) (set! p parse) (p s))))
707 ; (lambda (s) (p s))))))
708
709 ;; Utility
710 (define (%check-min-max min max)
711 (when (or (negative? min)
712 (and max (> min max)))
713 (error "invalid argument:" min max)))
714
715 ;; API
716 ;; $many p :optional min max
717 ;; $many_ p :optional min max
718 ;; $many1 p :optional max
719 ;; $many1_ p :optional max
720 (define-inline ($many parse :optional (min 0) (max #f))
721 (%check-min-max min max)
722 (lambda (s)
723 (let loop ([vs '()] [s s] [count 0])
724 (if (>=? count max)
725 (return-result (reverse! vs) s)
726 (receive (r v s1) (parse s)
727 (cond [(parse-success? r) (loop (cons v vs) s1 (+ count 1))]
728 [(and (eq? s s1) (<= min count))
729 (return-result (reverse! vs) s1)]
730 [else (return-failure r v s1)]))))))
731
732 (define-inline ($many_ parse :optional (min 0) (max #f))
733 (%check-min-max min max)
734 (lambda (s)
735 (let loop ([s s] [count 0])
736 (if (>=? count max)
737 (return-result #t s)
738 (receive (r v s1) (parse s)
739 (cond [(parse-success? r) (loop s1 (+ count 1))]
740 [(and (eq? s s1) (<= min count))
741 (return-result #t s1)]
742 [else (return-failure r v s1)]))))))
743
744 (define-inline ($many1 parse :optional (max #f)) ($many parse 1 max))
745 (define-inline ($many1_ parse :optional (max #f)) ($many_ parse 1 max))
746
747 ;; API
748 ;; $repeat p n
749 ;; $repeat_ p n
750 ;; Exactly n time of P. Same as ($many p n n)
751 (define ($repeat parse n) ($many parse n n))
752 (define ($repeat_ parse n) ($many_ parse n n))
753
754 ;; API
755 ;; $many-till P E :optional min max
756 ;; $many-till_ P E :optional min max
757 (define ($many-till parse end . args)
758 (apply $many ($seq ($not end) parse) args))
759 (define ($many-till_ parse end . args)
760 (apply $many_ ($seq ($not end) parse) args))
761
762 ;; API
763 ;; $optional p :optional fallback
764 ;; Try P. If not match, use FALLBACK as the value.
765 ;; Does not backtrack by default; if P may consume some input and
766 ;; you want to backtrack later, wrap it with $try.
767 (define ($optional parse :optional (fallback #f))
768 ($or parse ($return fallback)))
769
770 ;; API
771 ;; $sep-by p sep :optional min max
772 ;; P sparated by SEP, e.g. P SEP P SEP P. Returns list of values of P.
773 ;; If SEP consumes input then fails, or the following P fails, then the
774 ;; entire $sep-by fails.
775 (define ($sep-by parse sep :optional (min 0) (max #f))
776 (define rep
777 ($let ([x parse]
778 [xs ($many ($seq sep parse)
779 (clamp (- min 1) 0)
780 (and max (- max 1)))])
781 ($return (cons x xs))))
782 (cond
783 [(and max (zero? max)) ($return '())]
784 [(> min 0) rep]
785 [else ($or rep ($return '()))]))
786
787 ;; API
788 ;; $end-by p sep :optional min max
789 ;; Matches repetition of P SEP. Returns a list of values of P.
790 ;; This one doesn't set backtrack point, so for example the input is
791 ;; P SEP P SEP P Q, the entire match fails.
792 (define ($end-by parse sep . args)
793 (apply $many ($try ($let ([v parse] sep) ($return v))) args))
794
795 ;; API
796 ;; $sep-end-by p sep min max
797 ;; The last SEP is optional. The definition is a bit involved
798 ;; for performance.
799 (define ($sep-end-by parse sep :optional (min 0) (max #f))
800 (%check-min-max min max)
801 (^s (let loop ([vs '()] [s s] [count 0])
802 (if (>=? count max)
803 (return-result (reverse vs) s)
804 (receive (r v s.) (parse s)
805 (cond [(parse-success? r)
806 (receive (r. v. s..) (sep s.)
807 (cond [(parse-success? r.)
808 (loop (cons v vs) s.. (+ count 1))]
809 [(and (eq? s.. s.) (<= min (+ count 1)))
810 (return-result (reverse (cons v vs)) s.)]
811 [else (return-failure r. v. s..)]))]
812 [(and (eq? s s.) (<= min count))
813 (return-result (reverse vs) s)]
814 [else (return-failure r v s.)]))))))
815
816 ;; API
817 ;; $between A B C
818 ;; Matches A B C, and returns the result of B.
819 (define ($between open parse close)
820 ($let (open [v parse] close) ($return v)))
821
822 ;; API
823 ;; $chain-left P OP
824 (define ($chain-left parse op)
825 (lambda (st)
826 (receive (r v s) (parse st)
827 (if (parse-success? r)
828 (let loop ([r1 r] [v1 v] [s1 s])
829 (receive (r2 v2 s2) (($let ([proc op] [v parse])
830 ($return (proc v1 v)))
831 s1)
832 (if (parse-success? r2)
833 (loop r2 v2 s2)
834 (return-failure r1 v1 s1))))
835 (return-failure r v s)))))
836
837 ;; API
838 ;; $chain-right P OP
839 (define ($chain-right parse op)
840 (rec (loop s)
841 (($let ([h parse])
842 ($or ($try ($let ([proc op]
843 [t loop])
844 ($return (proc h t))))
845 ($return h)))
846 s)))
847
848 ;; API
849 ;; $satisfy PRED EXPECT [RESULT])
850 ;; - Returns a parser such that ...
851 ;; - If the head of input stream satisfies PRED,
852 ;; call (RESULT head (PRED head)) and let its result
853 ;; as the value of successulf parsing.
854 ;; - Otherwise, returns failure with EXPECT as the expected input.
855 (define-inline ($satisfy pred expect :optional (result #f))
856 (^s (if-let1 v (and (pair? s) (pred (car s)))
857 (return-result (if result
858 (result (car s) v)
859 (car s))
860 (cdr s))
861 (return-failure/expect expect s))))
862
863 ;; API
864 ;; $match1 PATTERN [(=> FAIL)] [RESULT]
865 ;; $match1* PATTERN [(=> FAIL)] [RESULT]
866 ;; - Run util.match#match against the input stream.
867 ;; - $match1 takes one item from stream and see if it matches
868 ;; with PATTERN.
869 ;; - $match1* applys PATTERN on the entire input stream.
870 ;; - If matched, RESULT is evaluated in the environment where pattern
871 ;; variables in PATTERN are bound, and its result becomes the result
872 ;; value of the parser.
873 ;; - If RESULT is omitted, the matched item is returned.
874 ;; - If (=> FAIL) is given, FAIL (must be an identifier) is bound to
875 ;; a closure to be called (FAIL message) to return a failure.
876 ;; NB: Unlinke the (=> FAIL) in match (util.match), FAIL is not
877 ;; a continuation but just a procedure, so it must be called at
878 ;; the tail position of RESULT.
879
880 (define-syntax $match1*
881 (er-macro-transformer
882 (^[f r c]
883 (define (=>? x) (c (r'=>) (r x)))
884 (define fail-mark (gensym))
885 (define (build-fail-decl fail)
886 (if fail
887 (quasirename r
888 `((define (,fail msg) (cons ',fail-mark msg))))
889 '()))
890 (define (build-return result fail tail)
891 (if fail
892 (quasirename r
893 `(let ((r ,result))
894 (if (and (pair? r) (eq? (car r) ',fail-mark))
895 (return-failure/message (cdr r) s)
896 (return-result r ,tail))))
897 (quasirename r
898 `(return-result ,result ,tail))))
899 ;; If pat is (x ...), add a rest var: (x ... . rest)
900 ;; Returns the pattern and the rest var.
901 (define (make-match-pattern pat)
902 (if (pair? pat)
903 (if (null? (cdr (last-pair pat)))
904 (let1 rest (gensym)
905 (values (append pat rest) rest))
906 (values pat '()))
907 (values pat '())))
908 (define (build-parser pat result fail)
909 (receive (match-pat tail) (make-match-pattern pat)
910 (quasirename r
911 `(lambda (s)
912 ,@(build-fail-decl fail)
913 (match s
914 [,match-pat ,(build-return result fail tail)]
915 [_ (return-failure/expect ,(write-to-string pat) s)])))))
916 (match f
917 [(_ pat ((? =>?) fail) result)
918 (build-parser pat result fail)]
919 [(_ pat result)
920 (build-parser pat result #f)]
921 [(_ pat)
922 (build-parser pat
923 (if-let1 n (length+ pat)
924 (quasirename r
925 `(take s ,n))
926 (r 's))
927 #f)]))))
928
929 (define-syntax $match1
930 (er-macro-transformer
931 (^[f r c]
932 (define (=>? x) (c (r'=>) (r x)))
933 (define fail-mark (gensym))
934 (define (build-fail-decl fail)
935 (if fail
936 (quasirename r
937 `((define (,fail msg) (cons ',fail-mark msg))))
938 '()))
939 (define (build-return result fail)
940 (if fail
941 (quasirename r
942 `(let ((r ,result))
943 (if (and (pair? r) (eq? (car r) ',fail-mark))
944 (return-failure/message (cdr r) s)
945 (return-result r (cdr s)))))
946 (quasirename r
947 `(return-result ,result (cdr s)))))
948 (define (build-parser pat result fail)
949 (quasirename r
950 `(lambda (s)
951 ,@(build-fail-decl fail)
952 (if (pair? s)
953 (match (car s)
954 [,pat ,(build-return result fail)]
955 [_ (return-failure/expect ,(write-to-string pat) s)])
956 (return-failure/expect ,(write-to-string pat) s)))))
957 (match f
958 [(_ pat ((? =>?) fail) result)
959 (build-parser pat result fail)]
960 [(_ pat result)
961 (build-parser pat result #f)]
962 [(_ pat)
963 (build-parser pat (quasirename r `(car s)) #f)]
964 ))))
965
966 ;; $binding <peg-bind-expression> ... [(=> FAIL)] <body>
967 ;; $lbinding <peg-bind-expression> ... [(=> FAIL)] <body>
968 ;; EXPERIMENTAL
969 ;; <peg-bind-expression> is an expression that yields a parser,
970 ;; but allowed to contain a form ($: var <peg-bind-expression>).
971 ;; When inner <peg-bind-expression> accepts an input, its semantic
972 ;; value is set to var.
973 ;;
974 ;; The parser runs as if ($seq <peg-bind-expression> ...), then
975 ;; if it succeeds, evaluate <body> with all such
976 ;; vars to be bound. If a branch of <peg-bind-expression> isn't
977 ;; tried, vars included in it is bound to #<undef>.
978 ;;
979 ;; $lbinding is similar to $binding, except that it behaves as if
980 ;; entire expression is enclosed in $lazy.
981 ;;
982 ;; An obvious translation is to create an enclosing scope, binds all
983 ;; vars to some default value, and convert ($: var expr) to
984 ;; ($lift (^x (set! var x) x) expr). However, it causes allocation
985 ;; of closures for each parser combinator every time the entire parser
986 ;; is called, which incurs performance overhead.
987 ;;
988 ;; Instead we rely on dynamic environment. All closure allocation is
989 ;; static. The main parser sets up a vector for the storage in a parameter,
990 ;; and each $: form store the value to the corresponding slot.
991 ;; If match succeeds, the stored values are retrieved and bound to VARs.
992 ;;
993 ;; If (=> FAIL) form is given, FAIL, which should be an identifier, is
994 ;; bound to a closure that can be called as (FAIL message). If you
995 ;; determine that the parser should fail inside <body>, you can call FAIL
996 ;; at a tail position, with a suitable message.
997 ;;
998 ;; Limitation - since $binding walks code, it can't be statically nested.
999
1000 (define %binding-storage
1001 (make-parameter 'accessing-binding-storage-out-of-context))
1002
1003 (define-syntax $lbinding
1004 (syntax-rules ()
1005 ([_ x ...] ($lazy ($binding x ...)))))
1006
1007 (define-syntax $binding
1008 (er-macro-transformer
1009 (^[f r c]
1010 (define $:? (let1 $:. (r'$:) (^x (c $:. (r x)))))
1011 (define =>? (let1 =>. (r'=>) (^x (c =>. (r x)))))
1012 (define fail-mark (gensym))
1013 ;; walk down form, gather variables and modify $: forms.
1014 ;; returns modified form and list of (var . index)
1015 (define (walk f vs)
1016 (match f
1017 [((? $:?) var expr)
1018 (unless (identifier? var)
1019 (error "($: var expr) form requires an identifier as var, but got:"
1020 var))
1021 (receive (expr_ vs) (walk expr vs)
1022 (receive (vs ind) (add-var var vs)
1023 (values (quasirename r
1024 `($lift (^[x] (set! (vector-ref (%binding-storage) ,ind) x) x)
1025 ,expr_))
1026 vs)))]
1027 [(xs ...) (map-accum walk vs xs)]
1028 [obj (values obj vs)]))
1029 (define (add-var var vs) ; returns var-alist and index
1030 (if-let1 p (assq var vs)
1031 (values vs (cdr p))
1032 (let1 ind (length vs)
1033 (values (acons var ind vs) ind))))
1034 (define (build-fail-decl fail)
1035 (if fail
1036 (quasirename r
1037 ;; NB: We can't optimize dynamically created case-lambda yet.
1038 ;; `((define ,fail
1039 ;; (case-lambda
1040 ;; ((msg) (list* ',fail-mark #f msg))
1041 ;; ((tag msg) (list* ',fail-mark tag msg)))))
1042 ;; With the following definition, the branch is likely
1043 ;; to be optimized out when call to fail is inlined:
1044 `((define (,fail a . b)
1045 (if (null? b)
1046 (list* ',fail-mark #f a) ;a=msg
1047 (list* ',fail-mark a (car b)))))) ;a=tag, (car b)=msg
1048 '()))
1049 (define (build-return result fail tail)
1050 (if fail
1051 (quasirename r
1052 `(let ((r ,result))
1053 (if (and (pair? r) (eq? (car r) ',fail-mark))
1054 (if (symbol? (cadr r))
1055 (return-error-from-failure (cadr r) 'fail-message (cddr r) s)
1056 (return-failure/message (cddr r) s))
1057 (return-result r ,tail))))
1058 (quasirename r
1059 `(return-result ,result ,tail))))
1060
1061 (define (build-parser parsers vs body fail)
1062 (quasirename r
1063 `(let ([parser ($seq ,@parsers)])
1064 (^[s]
1065 ,@(build-fail-decl fail)
1066 (let1 storage (make-vector ,(length vs))
1067 (parameterize ((%binding-storage storage))
1068 (receive (rr v s) (parser s)
1069 (if (parse-success? rr)
1070 ,(build-return
1071 (quasirename r
1072 `(let ,(map
1073 (^p (let ([var (car p)]
1074 [ind (cdr p)])
1075 (quasirename r
1076 `(,var (vector-ref storage ,ind)))))
1077 vs)
1078 ,body))
1079 fail
1080 (r's))
1081 (return-failure rr v s)))))))))
1082
1083 ;; optimization - if all the variable binding form is in the first level,
1084 ;; e.g.
1085 ;; ($binding ($: x parser1)
1086 ;; ($: y parser2)
1087 ;; body)
1088 ;; We can simply use $lift.
1089 ;; ($lift (lambda (x y) body) parser1 parser2)
1090 ;; This saves setting up value vector.
1091 ;; NB: we can't do this optimization if (=> fail) is used.
1092
1093 ;; check if lift optimization is possible. note that duplicate vars
1094 ;; are allowed, but that can be detected with the following, for
1095 ;; vars are deduped.
1096 (define (liftable? first-level-parsers vars)
1097 (= (length vars)
1098 (count (^p (match p
1099 [((? $:?) v _) #t]
1100 [_ #f]))
1101 first-level-parsers)))
1102
1103 (define (build-lift-form first-level-parsers body)
1104 ;; ((var . parser) ...).
1105 (define vars&parsers (map (^p (match p
1106 [((? $:?) v p) `(,v . ,p)]
1107 [p `(,(gensym) . ,p)]))
1108 first-level-parsers))
1109 (quasirename r
1110 `($lift (lambda ,(map car vars&parsers) ,body)
1111 ,@(map cdr vars&parsers))))
1112
1113 (define (bad) (error "Malformed $binding:" f))
1114
1115 (let loop ([forms (cdr f)] [ps '()])
1116 (match forms
1117 [(((? =>?) fail) body)
1118 (receive (parsers. vars) (walk (reverse ps) '())
1119 (build-parser parsers. vars body fail))]
1120 [(((? =>?) fail) body ...) (bad)]
1121 [(body)
1122 (receive (parsers. vars) (walk (reverse ps) '())
1123 (if (liftable? ps vars)
1124 (build-lift-form (reverse ps) body)
1125 (build-parser parsers. vars body #f)))]
1126 [(parser . rest) (loop rest (cons parser ps))]
1127 [() (bad)])))))
1128
1129 ;;;============================================================
1130 ;;; String parsers
1131 ;;;
1132
1133 (define-inline ($->rope parser . more-parsers)
1134 (if (null? more-parsers)
1135 ($lift make-rope parser)
1136 (apply $lift* make-rope parser more-parsers)))
1137 (define-inline ($->string parser . more-parsers)
1138 (if (null? more-parsers)
1139 ($lift ($ rope->string $ make-rope $) parser)
1140 (apply $lift* ($ rope->string $ make-rope $) parser more-parsers)))
1141 (define-inline ($->symbol parser . more-parsers)
1142 (if (null? more-parsers)
1143 ($lift ($ string->symbol $ rope->string $ make-rope $) parser)
1144 (apply $lift* ($ string->symbol $ rope->string $ make-rope $)
1145 parser more-parsers)))
1146
1147 (define (rope-finalize obj)
1148 (cond [(rope? obj) (rope->string obj)]
1149 [(pair? obj)
1150 (let ((ca (rope-finalize (car obj)))
1151 (cd (rope-finalize (cdr obj))))
1152 (if (and (eq? ca (car obj)) (eq? cd (cdr obj)))
1153 obj
1154 (cons ca cd)))]
1155 [else obj]))
1156
1157 ;; NB: On success, we know the matched input is the same as STR,
1158 ;; so we don't need to bother to collect matched chars.
1159 (define-inline ($string str)
1160 (if (= (string-length str) 1)
1161 (let1 ch (string-ref str 0)
1162 (^s
1163 (if (and (pair? s) (eqv? (car s) ch))
1164 (return-result str (cdr s))
1165 (return-failure/expect str s))))
1166 (let1 lis (string->list str)
1167 (^[s0]
1168 (let loop ([s s0] [lis lis])
1169 (if (null? lis)
1170 (return-result str s)
1171 (if (and (pair? s) (eqv? (car s) (car lis)))
1172 (loop (cdr s) (cdr lis))
1173 (return-failure/expect str s0))))))))
1174
1175 (define ($string-ci str)
1176 (let1 lis (string->list str)
1177 (^[s0]
1178 (let loop ([r '()] [s s0] [lis lis])
1179 (if (null? lis)
1180 (return-result (make-rope (reverse! r)) s)
1181 (if (and (pair? s)
1182 (char? (car s))
1183 (char-ci=? (car s) (car lis)))
1184 (loop (cons (car s) r) (cdr s) (cdr lis))
1185 (return-failure/expect str s0)))))))
1186
1187 (define-inline ($char c)
1188 (assume-type c <char>)
1189 ($satisfy (cut eqv? c <>) c))
1190
1191 (define ($char-ci c)
1192 (assume-type c <char>)
1193 ($satisfy (^x (and (char? x) (char-ci=? c x)))
1194 (list->char-set c (char-upcase c) (char-downcase c))))
1195
1196 ;; Anything except end of stream.
1197 (define-inline ($any)
1198 (^s (if (pair? s)
1199 (return-result (car s) (cdr s))
1200 (return-failure/unexpect "end of input" s))))
1201
1202 (define-inline ($eos)
1203 (^s (if (pair? s)
1204 (return-failure/expect "end of input" s)
1205 (return-result (eof-object) s))))
1206
1207 ;; Parse one item---a char, a string or a charset.
1208 (define-inline ($. item)
1209 (cond
1210 [(char-set? item) ($one-of item)]
1211 [(char? item) ($char item)]
1212 [(string? item) ($string item)]
1213 [(symbol? item) ($satisfy (cut eq? <> item) item)]
1214 [else (error "Bad item: $. requires a char, a char-set, a string, \
1215 or a symbol, but got:" item)]))
1216
1217 (define-hybrid-syntax $one-of
1218 (^[items]
1219 (cond
1220 [(char-set? items)
1221 ($satisfy (^x (and (char? x) (char-set-contains? items x)))
1222 items)]
1223 [(list? items) ($expect (apply $or (map $. items)) items)]
1224 [else (error "$one-of requires a charset or a list of items, \
1225 but got:" items)]))
1226 (er-macro-transformer
1227 (^[f r c]
1228 (match f
1229 [(_ (? char-set? items))
1230 (quasirename r
1231 `($satisfy (^[x] (and (char? x) (char-set-contains? ,items x)))
1232 ',items))]
1233 [(_ ('quote (items ...)))
1234 (if (every (^x (or (char? x) (symbol? x))) items)
1235 (quasirename r
1236 `($satisfy (^[x] (memv x ',items)) ',items))
1237 f)]
1238 [_ f]))))
1239
1240 ;; NB: $none-of can't be generalized like $one-of, for the value to return
1241 ;; on success is ambiguous except the case we're matching a single character.
1242 ;; The asymmetry doesn't look good... we may drop $none-of in future.
1243 (define ($none-of charset)
1244 (assume-type charset <char-set>)
1245 ($satisfy (^x (or (not (char? x)) (not (char-set-contains? charset x))))
1246 `(none-of ,charset)))