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