Commit | Line | Data |
---|---|---|
d02c9bcd SM |
1 | ;;; pcase.el --- ML-style pattern-matching macro for Elisp |
2 | ||
97eedd1b | 3 | ;; Copyright (C) 2010 Free Software Foundation, Inc. |
d02c9bcd SM |
4 | |
5 | ;; Author: Stefan Monnier <monnier@iro.umontreal.ca> | |
6 | ;; Keywords: | |
7 | ||
8 | ;; This file is part of GNU Emacs. | |
9 | ||
10 | ;; GNU Emacs is free software: you can redistribute it and/or modify | |
11 | ;; it under the terms of the GNU General Public License as published by | |
12 | ;; the Free Software Foundation, either version 3 of the License, or | |
13 | ;; (at your option) any later version. | |
14 | ||
15 | ;; GNU Emacs is distributed in the hope that it will be useful, | |
16 | ;; but WITHOUT ANY WARRANTY; without even the implied warranty of | |
17 | ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
18 | ;; GNU General Public License for more details. | |
19 | ||
20 | ;; You should have received a copy of the GNU General Public License | |
21 | ;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>. | |
22 | ||
23 | ;;; Commentary: | |
24 | ||
25 | ;; ML-style pattern matching. | |
26 | ;; The entry points are autoloaded. | |
27 | ||
dcc029e0 SM |
28 | ;; Todo: |
29 | ||
30 | ;; - provide ways to extend the set of primitives, with some kind of | |
31 | ;; define-pcase-matcher. We could easily make it so that (guard BOOLEXP) | |
32 | ;; could be defined this way, as a shorthand for (pred (lambda (_) BOOLEXP)). | |
33 | ;; But better would be if we could define new ways to match by having the | |
34 | ;; extension provide its own `pcase-split-<foo>' thingy. | |
35 | ;; - ideally we'd want (pcase s ((re RE1) E1) ((re RE2) E2)) to be able to | |
36 | ;; generate a lex-style DFA to decide whether to run E1 or E2. | |
37 | ||
d02c9bcd SM |
38 | ;;; Code: |
39 | ||
40 | (eval-when-compile (require 'cl)) | |
41 | ||
42 | ;; Macro-expansion of pcase is reasonably fast, so it's not a problem | |
43 | ;; when byte-compiling a file, but when interpreting the code, if the pcase | |
44 | ;; is in a loop, the repeated macro-expansion becomes terribly costly, so we | |
45 | ;; memoize previous macro expansions to try and avoid recomputing them | |
46 | ;; over and over again. | |
47 | (defconst pcase-memoize (make-hash-table :weakness t :test 'equal)) | |
48 | ||
49 | ;;;###autoload | |
50 | (defmacro pcase (exp &rest cases) | |
51 | "Perform ML-style pattern matching on EXP. | |
52 | CASES is a list of elements of the form (UPATTERN CODE...). | |
53 | ||
54 | UPatterns can take the following forms: | |
55 | _ matches anything. | |
56 | SYMBOL matches anything and binds it to SYMBOL. | |
57 | (or UPAT...) matches if any of the patterns matches. | |
58 | (and UPAT...) matches if all the patterns match. | |
59 | `QPAT matches if the QPattern QPAT matches. | |
60 | (pred PRED) matches if PRED applied to the object returns non-nil. | |
dcc029e0 | 61 | (guard BOOLEXP) matches if BOOLEXP evaluates to non-nil. |
d02c9bcd SM |
62 | |
63 | QPatterns can take the following forms: | |
64 | (QPAT1 . QPAT2) matches if QPAT1 matches the car and QPAT2 the cdr. | |
65 | ,UPAT matches if the UPattern UPAT matches. | |
dcc029e0 | 66 | STRING matches if the object is `equal' to STRING. |
d02c9bcd SM |
67 | ATOM matches if the object is `eq' to ATOM. |
68 | QPatterns for vectors are not implemented yet. | |
69 | ||
70 | PRED can take the form | |
71 | FUNCTION in which case it gets called with one argument. | |
72 | (FUN ARG1 .. ARGN) in which case it gets called with N+1 arguments. | |
73 | A PRED of the form FUNCTION is equivalent to one of the form (FUNCTION). | |
74 | PRED patterns can refer to variables bound earlier in the pattern. | |
75 | E.g. you can match pairs where the cdr is larger than the car with a pattern | |
76 | like `(,a . ,(pred (< a))) or, with more checks: | |
77 | `(,(and a (pred numberp)) . ,(and (pred numberp) (pred (< a))))" | |
78 | (declare (indent 1) (debug case)) | |
79 | (or (gethash (cons exp cases) pcase-memoize) | |
80 | (puthash (cons exp cases) | |
81 | (pcase-expand exp cases) | |
82 | pcase-memoize))) | |
83 | ||
84 | ;;;###autoload | |
85 | (defmacro pcase-let* (bindings body) | |
86 | "Like `let*' but where you can use `pcase' patterns for bindings. | |
87 | BODY should be an expression, and BINDINGS should be a list of bindings | |
88 | of the form (UPAT EXP)." | |
89 | (if (null bindings) body | |
90 | `(pcase ,(cadr (car bindings)) | |
15413fb4 | 91 | (,(caar bindings) (pcase-let* ,(cdr bindings) ,body)) |
dcc029e0 SM |
92 | ;; FIXME: In many cases `dontcare' would be preferable, so maybe we |
93 | ;; should have `let' and `elet', like we have `case' and `ecase'. | |
15413fb4 | 94 | (t (error "Pattern match failure in `pcase-let'"))))) |
d02c9bcd SM |
95 | |
96 | ;;;###autoload | |
97 | (defmacro pcase-let (bindings body) | |
98 | "Like `let' but where you can use `pcase' patterns for bindings. | |
99 | BODY should be an expression, and BINDINGS should be a list of bindings | |
100 | of the form (UPAT EXP)." | |
101 | (if (null (cdr bindings)) | |
15413fb4 | 102 | `(pcase-let* ,bindings ,body) |
d02c9bcd SM |
103 | (setq bindings (mapcar (lambda (x) (cons (make-symbol "x") x)) bindings)) |
104 | `(let ,(mapcar (lambda (binding) (list (nth 0 binding) (nth 2 binding))) | |
105 | bindings) | |
15413fb4 SM |
106 | (pcase-let* |
107 | ,(mapcar (lambda (binding) (list (nth 1 binding) (nth 0 binding))) | |
108 | bindings) | |
109 | ,body)))) | |
d02c9bcd SM |
110 | |
111 | (defun pcase-expand (exp cases) | |
112 | (let* ((defs (if (symbolp exp) '() | |
113 | (let ((sym (make-symbol "x"))) | |
114 | (prog1 `((,sym ,exp)) (setq exp sym))))) | |
115 | (seen '()) | |
116 | (codegen | |
117 | (lambda (code vars) | |
118 | (let ((prev (assq code seen))) | |
119 | (if (not prev) | |
120 | (let ((res (pcase-codegen code vars))) | |
121 | (push (list code vars res) seen) | |
122 | res) | |
123 | ;; Since we use a tree-based pattern matching | |
124 | ;; technique, the leaves (the places that contain the | |
125 | ;; code to run once a pattern is matched) can get | |
126 | ;; copied a very large number of times, so to avoid | |
127 | ;; code explosion, we need to keep track of how many | |
128 | ;; times we've used each leaf and move it | |
129 | ;; to a separate function if that number is too high. | |
130 | ;; | |
131 | ;; We've already used this branch. So it is shared. | |
132 | (destructuring-bind (code prevvars res) prev | |
133 | (unless (symbolp res) | |
134 | ;; This is the first repeat, so we have to move | |
135 | ;; the branch to a separate function. | |
136 | (let ((bsym | |
137 | (make-symbol (format "pcase-%d" (length defs))))) | |
138 | (push `(,bsym (lambda ,(mapcar #'car prevvars) ,@code)) defs) | |
139 | (setcar res 'funcall) | |
140 | (setcdr res (cons bsym (mapcar #'cdr prevvars))) | |
141 | (setcar (cddr prev) bsym) | |
142 | (setq res bsym))) | |
143 | (setq vars (copy-sequence vars)) | |
144 | (let ((args (mapcar (lambda (pa) | |
145 | (let ((v (assq (car pa) vars))) | |
146 | (setq vars (delq v vars)) | |
147 | (cdr v))) | |
148 | prevvars))) | |
149 | (when vars ;New additional vars. | |
150 | (error "The vars %s are only bound in some paths" | |
151 | (mapcar #'car vars))) | |
152 | `(funcall ,res ,@args))))))) | |
153 | (main | |
154 | (pcase-u | |
155 | (mapcar (lambda (case) | |
156 | `((match ,exp . ,(car case)) | |
157 | ,(apply-partially | |
158 | (if (pcase-small-branch-p (cdr case)) | |
159 | ;; Don't bother sharing multiple | |
160 | ;; occurrences of this leaf since it's small. | |
161 | #'pcase-codegen codegen) | |
162 | (cdr case)))) | |
163 | cases)))) | |
164 | `(let ,defs ,main))) | |
165 | ||
166 | (defun pcase-codegen (code vars) | |
167 | `(let ,(mapcar (lambda (b) (list (car b) (cdr b))) vars) | |
168 | ,@code)) | |
169 | ||
170 | (defun pcase-small-branch-p (code) | |
171 | (and (= 1 (length code)) | |
172 | (or (not (consp (car code))) | |
173 | (let ((small t)) | |
174 | (dolist (e (car code)) | |
175 | (if (consp e) (setq small nil))) | |
176 | small)))) | |
177 | ||
178 | ;; Try to use `cond' rather than a sequence of `if's, so as to reduce | |
179 | ;; the depth of the generated tree. | |
180 | (defun pcase-if (test then else) | |
181 | (cond | |
182 | ((eq else :pcase-dontcare) then) | |
183 | ((eq (car-safe else) 'if) | |
dcc029e0 SM |
184 | (if (equal test (nth 1 else)) |
185 | ;; Doing a test a second time: get rid of the redundancy. | |
186 | ;; FIXME: ideally, this should never happen because the pcase-split-* | |
187 | ;; functions should have eliminated such things, but pcase-split-member | |
188 | ;; is imprecise, so in practice it does happen occasionally. | |
189 | `(if ,test ,then ,@(nthcdr 3 else)) | |
190 | `(cond (,test ,then) | |
191 | (,(nth 1 else) ,(nth 2 else)) | |
192 | (t ,@(nthcdr 3 else))))) | |
d02c9bcd SM |
193 | ((eq (car-safe else) 'cond) |
194 | `(cond (,test ,then) | |
dcc029e0 SM |
195 | ;; Doing a test a second time: get rid of the redundancy, as above. |
196 | ,@(remove (assoc test else) (cdr else)))) | |
d02c9bcd SM |
197 | (t `(if ,test ,then ,else)))) |
198 | ||
199 | (defun pcase-upat (qpattern) | |
200 | (cond | |
201 | ((eq (car-safe qpattern) '\,) (cadr qpattern)) | |
202 | (t (list '\` qpattern)))) | |
203 | ||
204 | ;; Note about MATCH: | |
205 | ;; When we have patterns like `(PAT1 . PAT2), after performing the `consp' | |
206 | ;; check, we want to turn all the similar patterns into ones of the form | |
207 | ;; (and (match car PAT1) (match cdr PAT2)), so you naturally need conjunction. | |
208 | ;; Earlier code hence used branches of the form (MATCHES . CODE) where | |
209 | ;; MATCHES was a list (implicitly a conjunction) of (SYM . PAT). | |
210 | ;; But if we have a pattern of the form (or `(PAT1 . PAT2) PAT3), there is | |
211 | ;; no easy way to eliminate the `consp' check in such a representation. | |
212 | ;; So we replaced the MATCHES by the MATCH below which can be made up | |
213 | ;; of conjunctions and disjunctions, so if we know `foo' is a cons, we can | |
214 | ;; turn (match foo . (or `(PAT1 . PAT2) PAT3)) into | |
215 | ;; (or (and (match car . `PAT1) (match cdr . `PAT2)) (match foo . PAT3)). | |
216 | ;; The downside is that we now have `or' and `and' both in MATCH and | |
217 | ;; in PAT, so there are different equivalent representations and we | |
218 | ;; need to handle them all. We do not try to systematically | |
219 | ;; canonicalize them to one form over another, but we do occasionally | |
220 | ;; turn one into the other. | |
221 | ||
222 | (defun pcase-u (branches) | |
223 | "Expand matcher for rules BRANCHES. | |
224 | Each BRANCH has the form (MATCH CODE . VARS) where | |
225 | CODE is the code generator for that branch. | |
226 | VARS is the set of vars already bound by earlier matches. | |
227 | MATCH is the pattern that needs to be matched, of the form: | |
228 | (match VAR . UPAT) | |
229 | (and MATCH ...) | |
230 | (or MATCH ...)" | |
231 | (when (setq branches (delq nil branches)) | |
232 | (destructuring-bind (match code &rest vars) (car branches) | |
233 | (pcase-u1 (list match) code vars (cdr branches))))) | |
234 | ||
235 | (defun pcase-and (match matches) | |
236 | (if matches `(and ,match ,@matches) match)) | |
237 | ||
238 | (defun pcase-split-match (sym splitter match) | |
239 | (case (car match) | |
240 | ((match) | |
241 | (if (not (eq sym (cadr match))) | |
242 | (cons match match) | |
243 | (let ((pat (cddr match))) | |
244 | (cond | |
245 | ;; Hoist `or' and `and' patterns to `or' and `and' matches. | |
246 | ((memq (car-safe pat) '(or and)) | |
247 | (pcase-split-match sym splitter | |
248 | (cons (car pat) | |
249 | (mapcar (lambda (alt) | |
250 | `(match ,sym . ,alt)) | |
251 | (cdr pat))))) | |
252 | (t (let ((res (funcall splitter (cddr match)))) | |
253 | (cons (or (car res) match) (or (cdr res) match)))))))) | |
254 | ((or and) | |
255 | (let ((then-alts '()) | |
256 | (else-alts '()) | |
257 | (neutral-elem (if (eq 'or (car match)) :pcase-fail :pcase-succeed)) | |
258 | (zero-elem (if (eq 'or (car match)) :pcase-succeed :pcase-fail))) | |
259 | (dolist (alt (cdr match)) | |
260 | (let ((split (pcase-split-match sym splitter alt))) | |
261 | (unless (eq (car split) neutral-elem) | |
262 | (push (car split) then-alts)) | |
263 | (unless (eq (cdr split) neutral-elem) | |
264 | (push (cdr split) else-alts)))) | |
265 | (cons (cond ((memq zero-elem then-alts) zero-elem) | |
266 | ((null then-alts) neutral-elem) | |
267 | ((null (cdr then-alts)) (car then-alts)) | |
268 | (t (cons (car match) (nreverse then-alts)))) | |
269 | (cond ((memq zero-elem else-alts) zero-elem) | |
270 | ((null else-alts) neutral-elem) | |
271 | ((null (cdr else-alts)) (car else-alts)) | |
272 | (t (cons (car match) (nreverse else-alts))))))) | |
273 | (t (error "Uknown MATCH %s" match)))) | |
274 | ||
275 | (defun pcase-split-rest (sym splitter rest) | |
276 | (let ((then-rest '()) | |
277 | (else-rest '())) | |
278 | (dolist (branch rest) | |
279 | (let* ((match (car branch)) | |
280 | (code&vars (cdr branch)) | |
281 | (splitted | |
282 | (pcase-split-match sym splitter match))) | |
283 | (unless (eq (car splitted) :pcase-fail) | |
284 | (push (cons (car splitted) code&vars) then-rest)) | |
285 | (unless (eq (cdr splitted) :pcase-fail) | |
286 | (push (cons (cdr splitted) code&vars) else-rest)))) | |
287 | (cons (nreverse then-rest) (nreverse else-rest)))) | |
288 | ||
289 | (defun pcase-split-consp (syma symd pat) | |
290 | (cond | |
291 | ;; A QPattern for a cons, can only go the `then' side. | |
292 | ((and (eq (car-safe pat) '\`) (consp (cadr pat))) | |
293 | (let ((qpat (cadr pat))) | |
294 | (cons `(and (match ,syma . ,(pcase-upat (car qpat))) | |
295 | (match ,symd . ,(pcase-upat (cdr qpat)))) | |
296 | :pcase-fail))) | |
297 | ;; A QPattern but not for a cons, can only go the `else' side. | |
298 | ((eq (car-safe pat) '\`) (cons :pcase-fail nil)))) | |
299 | ||
dcc029e0 | 300 | (defun pcase-split-equal (elem pat) |
d02c9bcd SM |
301 | (cond |
302 | ;; The same match will give the same result. | |
303 | ((and (eq (car-safe pat) '\`) (equal (cadr pat) elem)) | |
304 | (cons :pcase-succeed :pcase-fail)) | |
305 | ;; A different match will fail if this one succeeds. | |
306 | ((and (eq (car-safe pat) '\`) | |
307 | ;; (or (integerp (cadr pat)) (symbolp (cadr pat)) | |
308 | ;; (consp (cadr pat))) | |
309 | ) | |
310 | (cons :pcase-fail nil)))) | |
311 | ||
dcc029e0 SM |
312 | (defun pcase-split-member (elems pat) |
313 | ;; Based on pcase-split-equal. | |
d02c9bcd | 314 | (cond |
dcc029e0 SM |
315 | ;; The same match (or a match of membership in a superset) will |
316 | ;; give the same result, but we don't know how to check it. | |
4de81ee0 SM |
317 | ;; (??? |
318 | ;; (cons :pcase-succeed nil)) | |
319 | ;; A match for one of the elements may succeed or fail. | |
d02c9bcd | 320 | ((and (eq (car-safe pat) '\`) (member (cadr pat) elems)) |
4de81ee0 | 321 | nil) |
d02c9bcd SM |
322 | ;; A different match will fail if this one succeeds. |
323 | ((and (eq (car-safe pat) '\`) | |
324 | ;; (or (integerp (cadr pat)) (symbolp (cadr pat)) | |
325 | ;; (consp (cadr pat))) | |
326 | ) | |
327 | (cons :pcase-fail nil)))) | |
328 | ||
329 | (defun pcase-split-pred (upat pat) | |
330 | ;; FIXME: For predicates like (pred (> a)), two such predicates may | |
331 | ;; actually refer to different variables `a'. | |
332 | (if (equal upat pat) | |
333 | (cons :pcase-succeed :pcase-fail))) | |
334 | ||
335 | (defun pcase-fgrep (vars sexp) | |
336 | "Check which of the symbols VARS appear in SEXP." | |
337 | (let ((res '())) | |
338 | (while (consp sexp) | |
339 | (dolist (var (pcase-fgrep vars (pop sexp))) | |
340 | (unless (memq var res) (push var res)))) | |
341 | (and (memq sexp vars) (not (memq sexp res)) (push sexp res)) | |
342 | res)) | |
343 | ||
344 | ;; It's very tempting to use `pcase' below, tho obviously, it'd create | |
345 | ;; bootstrapping problems. | |
346 | (defun pcase-u1 (matches code vars rest) | |
347 | "Return code that runs CODE (with VARS) if MATCHES match. | |
348 | and otherwise defers to REST which is a list of branches of the form | |
349 | \(ELSE-MATCH ELSE-CODE . ELSE-VARS)." | |
350 | ;; Depending on the order in which we choose to check each of the MATCHES, | |
351 | ;; the resulting tree may be smaller or bigger. So in general, we'd want | |
352 | ;; to be careful to chose the "optimal" order. But predicate | |
353 | ;; patterns make this harder because they create dependencies | |
354 | ;; between matches. So we don't bother trying to reorder anything. | |
355 | (cond | |
356 | ((null matches) (funcall code vars)) | |
357 | ((eq :pcase-fail (car matches)) (pcase-u rest)) | |
358 | ((eq :pcase-succeed (car matches)) | |
359 | (pcase-u1 (cdr matches) code vars rest)) | |
360 | ((eq 'and (caar matches)) | |
361 | (pcase-u1 (append (cdar matches) (cdr matches)) code vars rest)) | |
362 | ((eq 'or (caar matches)) | |
363 | (let* ((alts (cdar matches)) | |
364 | (var (if (eq (caar alts) 'match) (cadr (car alts)))) | |
365 | (simples '()) (others '())) | |
366 | (when var | |
367 | (dolist (alt alts) | |
368 | (if (and (eq (car alt) 'match) (eq var (cadr alt)) | |
369 | (let ((upat (cddr alt))) | |
370 | (and (eq (car-safe upat) '\`) | |
dcc029e0 SM |
371 | (or (integerp (cadr upat)) (symbolp (cadr upat)) |
372 | (stringp (cadr upat)))))) | |
d02c9bcd SM |
373 | (push (cddr alt) simples) |
374 | (push alt others)))) | |
375 | (cond | |
376 | ((null alts) (error "Please avoid it") (pcase-u rest)) | |
377 | ((> (length simples) 1) | |
378 | ;; De-hoist the `or' MATCH into an `or' pattern that will be | |
379 | ;; turned into a `memq' below. | |
380 | (pcase-u1 (cons `(match ,var or . ,(nreverse simples)) (cdr matches)) | |
381 | code vars | |
382 | (if (null others) rest | |
383 | (cons (list* | |
384 | (pcase-and (if (cdr others) | |
385 | (cons 'or (nreverse others)) | |
386 | (car others)) | |
387 | (cdr matches)) | |
388 | code vars) | |
389 | rest)))) | |
390 | (t | |
391 | (pcase-u1 (cons (pop alts) (cdr matches)) code vars | |
392 | (if (null alts) (progn (error "Please avoid it") rest) | |
393 | (cons (list* | |
394 | (pcase-and (if (cdr alts) | |
395 | (cons 'or alts) (car alts)) | |
396 | (cdr matches)) | |
397 | code vars) | |
398 | rest))))))) | |
399 | ((eq 'match (caar matches)) | |
400 | (destructuring-bind (op sym &rest upat) (pop matches) | |
401 | (cond | |
402 | ((memq upat '(t _)) (pcase-u1 matches code vars rest)) | |
403 | ((eq upat 'dontcare) :pcase-dontcare) | |
404 | ((functionp upat) (error "Feature removed, use (pred %s)" upat)) | |
dcc029e0 | 405 | ((memq (car-safe upat) '(guard pred)) |
d02c9bcd SM |
406 | (destructuring-bind (then-rest &rest else-rest) |
407 | (pcase-split-rest | |
408 | sym (apply-partially 'pcase-split-pred upat) rest) | |
dcc029e0 | 409 | (pcase-if (if (and (eq (car upat) 'pred) (symbolp (cadr upat))) |
d02c9bcd SM |
410 | `(,(cadr upat) ,sym) |
411 | (let* ((exp (cadr upat)) | |
412 | ;; `vs' is an upper bound on the vars we need. | |
4de81ee0 | 413 | (vs (pcase-fgrep (mapcar #'car vars) exp)) |
dcc029e0 SM |
414 | (call (cond |
415 | ((eq 'guard (car upat)) exp) | |
416 | ((functionp exp) `(,exp ,sym)) | |
417 | (t `(,@exp ,sym))))) | |
4de81ee0 SM |
418 | (if (null vs) |
419 | call | |
420 | ;; Let's not replace `vars' in `exp' since it's | |
421 | ;; too difficult to do it right, instead just | |
422 | ;; let-bind `vars' around `exp'. | |
423 | `(let ,(mapcar (lambda (var) | |
424 | (list var (cdr (assq var vars)))) | |
425 | vs) | |
426 | ;; FIXME: `vars' can capture `sym'. E.g. | |
427 | ;; (pcase x ((and `(,x . ,y) (pred (fun x))))) | |
428 | ,call)))) | |
d02c9bcd SM |
429 | (pcase-u1 matches code vars then-rest) |
430 | (pcase-u else-rest)))) | |
431 | ((symbolp upat) | |
432 | (pcase-u1 matches code (cons (cons upat sym) vars) rest)) | |
433 | ((eq (car-safe upat) '\`) | |
434 | (pcase-q1 sym (cadr upat) matches code vars rest)) | |
435 | ((eq (car-safe upat) 'or) | |
dcc029e0 SM |
436 | (let ((all (> (length (cdr upat)) 1)) |
437 | (memq-fine t)) | |
d02c9bcd SM |
438 | (when all |
439 | (dolist (alt (cdr upat)) | |
440 | (unless (and (eq (car-safe alt) '\`) | |
dcc029e0 SM |
441 | (or (symbolp (cadr alt)) (integerp (cadr alt)) |
442 | (setq memq-fine nil) | |
443 | (stringp (cadr alt)))) | |
d02c9bcd SM |
444 | (setq all nil)))) |
445 | (if all | |
446 | ;; Use memq for (or `a `b `c `d) rather than a big tree. | |
447 | (let ((elems (mapcar 'cadr (cdr upat)))) | |
448 | (destructuring-bind (then-rest &rest else-rest) | |
449 | (pcase-split-rest | |
dcc029e0 SM |
450 | sym (apply-partially 'pcase-split-member elems) rest) |
451 | (pcase-if `(,(if memq-fine #'memq #'member) ,sym ',elems) | |
d02c9bcd SM |
452 | (pcase-u1 matches code vars then-rest) |
453 | (pcase-u else-rest)))) | |
454 | (pcase-u1 (cons `(match ,sym ,@(cadr upat)) matches) code vars | |
455 | (append (mapcar (lambda (upat) | |
456 | `((and (match ,sym . ,upat) ,@matches) | |
457 | ,code ,@vars)) | |
458 | (cddr upat)) | |
459 | rest))))) | |
460 | ((eq (car-safe upat) 'and) | |
461 | (pcase-u1 (append (mapcar (lambda (upat) `(match ,sym ,@upat)) (cdr upat)) | |
462 | matches) | |
463 | code vars rest)) | |
464 | ((eq (car-safe upat) 'not) | |
465 | ;; FIXME: The implementation below is naive and results in | |
466 | ;; inefficient code. | |
467 | ;; To make it work right, we would need to turn pcase-u1's | |
468 | ;; `code' and `vars' into a single argument of the same form as | |
469 | ;; `rest'. We would also need to split this new `then-rest' argument | |
470 | ;; for every test (currently we don't bother to do it since | |
471 | ;; it's only useful for odd patterns like (and `(PAT1 . PAT2) | |
472 | ;; `(PAT3 . PAT4)) which the programmer can easily rewrite | |
473 | ;; to the more efficient `(,(and PAT1 PAT3) . ,(and PAT2 PAT4))). | |
474 | (pcase-u1 `((match ,sym . ,(cadr upat))) | |
475 | (lexical-let ((rest rest)) | |
476 | ;; FIXME: This codegen is not careful to share its | |
477 | ;; code if used several times: code blow up is likely. | |
478 | (lambda (vars) | |
479 | ;; `vars' will likely contain bindings which are | |
480 | ;; not always available in other paths to | |
481 | ;; `rest', so there' no point trying to pass | |
482 | ;; them down. | |
483 | (pcase-u rest))) | |
484 | vars | |
485 | (list `((and . ,matches) ,code . ,vars)))) | |
486 | (t (error "Unknown upattern `%s'" upat))))) | |
487 | (t (error "Incorrect MATCH %s" (car matches))))) | |
488 | ||
489 | (defun pcase-q1 (sym qpat matches code vars rest) | |
490 | "Return code that runs CODE if SYM matches QPAT and if MATCHES match. | |
491 | and if not, defers to REST which is a list of branches of the form | |
492 | \(OTHER_MATCH OTHER-CODE . OTHER-VARS)." | |
493 | (cond | |
494 | ((eq (car-safe qpat) '\,) (error "Can't use `,UPATTERN")) | |
495 | ((floatp qpat) (error "Floating point patterns not supported")) | |
496 | ((vectorp qpat) | |
497 | ;; FIXME. | |
498 | (error "Vector QPatterns not implemented yet")) | |
499 | ((consp qpat) | |
500 | (let ((syma (make-symbol "xcar")) | |
501 | (symd (make-symbol "xcdr"))) | |
502 | (destructuring-bind (then-rest &rest else-rest) | |
503 | (pcase-split-rest sym (apply-partially 'pcase-split-consp syma symd) | |
504 | rest) | |
505 | (pcase-if `(consp ,sym) | |
506 | `(let ((,syma (car ,sym)) | |
507 | (,symd (cdr ,sym))) | |
508 | ,(pcase-u1 `((match ,syma . ,(pcase-upat (car qpat))) | |
509 | (match ,symd . ,(pcase-upat (cdr qpat))) | |
510 | ,@matches) | |
511 | code vars then-rest)) | |
512 | (pcase-u else-rest))))) | |
dcc029e0 | 513 | ((or (integerp qpat) (symbolp qpat) (stringp qpat)) |
d02c9bcd | 514 | (destructuring-bind (then-rest &rest else-rest) |
dcc029e0 SM |
515 | (pcase-split-rest sym (apply-partially 'pcase-split-equal qpat) rest) |
516 | (pcase-if `(,(if (stringp qpat) #'equal #'eq) ,sym ',qpat) | |
d02c9bcd SM |
517 | (pcase-u1 matches code vars then-rest) |
518 | (pcase-u else-rest)))) | |
519 | (t (error "Unkown QPattern %s" qpat)))) | |
97eedd1b | 520 | |
d02c9bcd SM |
521 | |
522 | (provide 'pcase) | |
523 | ;;; pcase.el ends here |