regexp/parse/ast.rkt

6 (define rx:never 'never)
7 (define rx:empty 'empty)
8 (define rx:any 'any)
9 (define rx:start 'start)
10 (define rx:end 'end)
11 (define rx:line-start 'line-start)
12 (define rx:line-end 'line-end)
13 (define rx:word-boundary 'word-boundary)
14 (define rx:not-word-boundary 'not-word-boundary)
20 (struct rx:alts (rx1 rx2) #:transparent)
21 (struct rx:sequence (rxs needs-backtrack?) #:transparent)
22 (struct rx:group (rx number) #:transparent)
23 (struct rx:repeat (rx min max non-greedy?) #:transparent)
24 (struct rx:maybe (rx non-greedy?) #:transparent) ; special case in size validation
25 (struct rx:conditional (tst rx1 rx2 n-start num-n needs-backtrack?) #:transparent)
26 (struct rx:lookahead (rx match? n-start num-n) #:transparent)
27 (struct rx:lookbehind (rx match? [lb-min #:mutable] [lb-max #:mutable] ; min & max set by `validate`
30 (struct rx:cut (rx n-start num-n needs-backtrack?) #:transparent)
31 (struct rx:reference (n case-sensitive?) #:transparent)
32 (struct rx:range (range) #:transparent)
33 (struct rx:unicode-categories (symlist match?) #:transparent)
35 ;; We need to backtrack for `rx` if it has alternatives;
39 (define (needs-backtrack? rx)
41    [(rx:alts? rx) #t]
42    [(rx:sequence? rx) (rx:sequence-needs-backtrack? rx)]
43    [(rx:group? rx) #t] ; to unwind success mappings
44    [(rx:repeat? rx) #t]
45    [(rx:maybe? rx) #t]
46    [(rx:conditional? rx) (rx:conditional-needs-backtrack? rx)]
47    [(rx:cut? rx) (rx:cut-needs-backtrack? rx)] ; doesn't actually backtrack, but count varies
48    [(rx:unicode-categories? rx) #t]
51 (define (rx-range range limit-c)
54    [(range-includes? range 0 limit-c) rx:any]
55    [else (rx:range range)]))
57 (define (rx-sequence l)
59    [(null? l) rx:empty]
65      [else (rx:sequence merged-l (ormap needs-backtrack? merged-l))])]))
73            (rx:sequence? (car l)))
75       (loop mode accum (append (rx:sequence-rxs (car l)) (cdr l)))]
77            (or (eq? rx:empty (car l))
127 (define (rx-alts rx1 rx2 limit-c)
129    [(eq? rx:never rx1) rx2]
130    [(eq? rx:never rx2) rx1]
131    [(and (rx:range? rx1) (rx:range? rx2))
132     (rx-range (range-union (rx:range-range rx1)
133                            (rx:range-range rx2))
135    [(and (rx:range? rx1) (rx:alts? rx2) (rx:range? (rx:alts-rx1 rx2)))
136     (rx-alts (rx-alts rx1 (rx:alts-rx1 rx2) limit-c)
137              (rx:alts-rx2 rx2)
139    [(and (rx:range? rx1) (integer? rx2))
140     (rx-range (range-add (rx:range-range rx1) rx2) limit-c)]
141    [(and (rx:range? rx2) (integer? rx1))
142     (rx-alts rx2 rx1 limit-c)]
144     (rx-range (range-add (range-add empty-range rx1) rx2) limit-c)]
146     (rx:alts rx1 rx2)]))
148 (define (rx-group rx n)
149   (rx:group rx n))
151 (define (rx-cut rx n-start num-n)
152   (rx:cut rx n-start num-n (needs-backtrack? rx)))
154 (define (rx-conditional tst pces1 pces2 n-start num-n)
155   (rx:conditional tst pces1 pces2 n-start num-n (or (needs-backtrack? pces1)