* net/tramp-sh.el (tramp-histfile-override): Add :version.
[emacs.git] / lisp / emacs-lisp / pcase.el
1 ;;; pcase.el --- ML-style pattern-matching macro for Elisp -*- lexical-binding: t; coding: utf-8 -*-
2
3 ;; Copyright (C) 2010-2014 Free Software Foundation, Inc.
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
28 ;; Todo:
29
30 ;; - (pcase e (`(,x . ,x) foo)) signals an "x unused" warning if `foo' doesn't
31 ;;   use x, because x is bound separately for the equality constraint
32 ;;   (as well as any pred/guard) and for the body, so uses at one place don't
33 ;;   count for the other.
34 ;; - provide ways to extend the set of primitives, with some kind of
35 ;;   define-pcase-matcher.  We could easily make it so that (guard BOOLEXP)
36 ;;   could be defined this way, as a shorthand for (pred (lambda (_) BOOLEXP)).
37 ;;   But better would be if we could define new ways to match by having the
38 ;;   extension provide its own `pcase--split-<foo>' thingy.
39 ;; - along these lines, provide patterns to match CL structs.
40 ;; - provide something like (setq VAR) so a var can be set rather than
41 ;;   let-bound.
42 ;; - provide a way to fallthrough to subsequent cases (not sure what I meant by
43 ;;   this :-()
44 ;; - try and be more clever to reduce the size of the decision tree, and
45 ;;   to reduce the number of leaves that need to be turned into function:
46 ;;   - first, do the tests shared by all remaining branches (it will have
47 ;;     to be performed anyway, so better do it first so it's shared).
48 ;;   - then choose the test that discriminates more (?).
49 ;; - provide Agda's `with' (along with its `...' companion).
50 ;; - implement (not UPAT).  This might require a significant redesign.
51 ;; - ideally we'd want (pcase s ((re RE1) E1) ((re RE2) E2)) to be able to
52 ;;   generate a lex-style DFA to decide whether to run E1 or E2.
53
54 ;;; Code:
55
56 (require 'macroexp)
57
58 ;; Macro-expansion of pcase is reasonably fast, so it's not a problem
59 ;; when byte-compiling a file, but when interpreting the code, if the pcase
60 ;; is in a loop, the repeated macro-expansion becomes terribly costly, so we
61 ;; memoize previous macro expansions to try and avoid recomputing them
62 ;; over and over again.
63 ;; FIXME: Now that macroexpansion is also performed when loading an interpreted
64 ;; file, this is not a real problem any more.
65 (defconst pcase--memoize (make-hash-table :weakness 'key :test 'eq))
66 ;; (defconst pcase--memoize-1 (make-hash-table :test 'eq))
67 ;; (defconst pcase--memoize-2 (make-hash-table :weakness 'key :test 'equal))
68
69 (defconst pcase--dontcare-upats '(t _ pcase--dontcare))
70
71 (defvar pcase--dontwarn-upats '(pcase--dontcare))
72
73 (def-edebug-spec
74   pcase-UPAT
75   (&or symbolp
76        ("or" &rest pcase-UPAT)
77        ("and" &rest pcase-UPAT)
78        ("`" pcase-QPAT)
79        ("guard" form)
80        ("let" pcase-UPAT form)
81        ("pred"
82         &or lambda-expr
83         ;; Punt on macros/special forms.
84         (functionp &rest form)
85         sexp)
86        sexp))
87
88 (def-edebug-spec
89   pcase-QPAT
90   (&or ("," pcase-UPAT)
91        (pcase-QPAT . pcase-QPAT)
92        sexp))
93
94 ;;;###autoload
95 (defmacro pcase (exp &rest cases)
96   "Perform ML-style pattern matching on EXP.
97 CASES is a list of elements of the form (UPATTERN CODE...).
98
99 UPatterns can take the following forms:
100   _             matches anything.
101   SELFQUOTING   matches itself.  This includes keywords, numbers, and strings.
102   SYMBOL        matches anything and binds it to SYMBOL.
103   (or UPAT...)  matches if any of the patterns matches.
104   (and UPAT...) matches if all the patterns match.
105   'VAL          matches if the object is `equal' to VAL
106   `QPAT         matches if the QPattern QPAT matches.
107   (pred FUN)    matches if FUN applied to the object returns non-nil.
108   (guard BOOLEXP)       matches if BOOLEXP evaluates to non-nil.
109   (let UPAT EXP)        matches if EXP matches UPAT.
110   (app FUN UPAT)        matches if FUN applied to the object matches UPAT.
111 If a SYMBOL is used twice in the same pattern (i.e. the pattern is
112 \"non-linear\"), then the second occurrence is turned into an `eq'uality test.
113
114 QPatterns can take the following forms:
115   (QPAT1 . QPAT2)       matches if QPAT1 matches the car and QPAT2 the cdr.
116   [QPAT1 QPAT2..QPATn]  matches a vector of length n and QPAT1..QPATn match
117                            its 0..(n-1)th elements, respectively.
118   ,UPAT                 matches if the UPattern UPAT matches.
119   STRING                matches if the object is `equal' to STRING.
120   ATOM                  matches if the object is `eq' to ATOM.
121
122 FUN can take the form
123   SYMBOL or (lambda ARGS BODY)  in which case it's called with one argument.
124   (F ARG1 .. ARGn) in which case F gets called with an n+1'th argument
125                         which is the value being matched.
126 So a FUN of the form SYMBOL is equivalent to one of the form (FUN).
127 FUN can refer to variables bound earlier in the pattern.
128 FUN is assumed to be pure, i.e. it can be dropped if its result is not used,
129 and two identical calls can be merged into one.
130 E.g. you can match pairs where the cdr is larger than the car with a pattern
131 like `(,a . ,(pred (< a))) or, with more checks:
132 `(,(and a (pred numberp)) . ,(and (pred numberp) (pred (< a))))"
133   (declare (indent 1) (debug (form &rest (pcase-UPAT body))))
134   ;; We want to use a weak hash table as a cache, but the key will unavoidably
135   ;; be based on `exp' and `cases', yet `cases' is a fresh new list each time
136   ;; we're called so it'll be immediately GC'd.  So we use (car cases) as key
137   ;; which does come straight from the source code and should hence not be GC'd
138   ;; so easily.
139   (let ((data (gethash (car cases) pcase--memoize)))
140     ;; data = (EXP CASES . EXPANSION)
141     (if (and (equal exp (car data)) (equal cases (cadr data)))
142         ;; We have the right expansion.
143         (cddr data)
144       ;; (when (gethash (car cases) pcase--memoize-1)
145       ;;   (message "pcase-memoize failed because of weak key!!"))
146       ;; (when (gethash (car cases) pcase--memoize-2)
147       ;;   (message "pcase-memoize failed because of eq test on %S"
148       ;;            (car cases)))
149       (when data
150         (message "pcase-memoize: equal first branch, yet different"))
151       (let ((expansion (pcase--expand exp cases)))
152         (puthash (car cases) `(,exp ,cases ,@expansion) pcase--memoize)
153         ;; (puthash (car cases) `(,exp ,cases ,@expansion) pcase--memoize-1)
154         ;; (puthash (car cases) `(,exp ,cases ,@expansion) pcase--memoize-2)
155         expansion))))
156
157 ;;;###autoload
158 (defmacro pcase-exhaustive (exp &rest cases)
159   "The exhaustive version of `pcase' (which see)."
160   (declare (indent 1) (debug pcase))
161   (let* ((x (make-symbol "x"))
162          (pcase--dontwarn-upats (cons x pcase--dontwarn-upats)))
163     (pcase--expand
164      ;; FIXME: Could we add the FILE:LINE data in the error message?
165      exp (append cases `((,x (error "No clause matching `%S'" ,x)))))))
166
167 (defun pcase--let* (bindings body)
168   (cond
169    ((null bindings) (macroexp-progn body))
170    ((pcase--trivial-upat-p (caar bindings))
171     (macroexp-let* `(,(car bindings)) (pcase--let* (cdr bindings) body)))
172    (t
173     (let ((binding (pop bindings)))
174       (pcase--expand
175        (cadr binding)
176        `((,(car binding) ,(pcase--let* bindings body))
177          ;; We can either signal an error here, or just use `pcase--dontcare'
178          ;; which generates more efficient code.  In practice, if we use
179          ;; `pcase--dontcare' we will still often get an error and the few
180          ;; cases where we don't do not matter that much, so
181          ;; it's a better choice.
182          (pcase--dontcare nil)))))))
183
184 ;;;###autoload
185 (defmacro pcase-let* (bindings &rest body)
186   "Like `let*' but where you can use `pcase' patterns for bindings.
187 BODY should be an expression, and BINDINGS should be a list of bindings
188 of the form (UPAT EXP)."
189   (declare (indent 1)
190            (debug ((&rest (pcase-UPAT &optional form)) body)))
191   (let ((cached (gethash bindings pcase--memoize)))
192     ;; cached = (BODY . EXPANSION)
193     (if (equal (car cached) body)
194         (cdr cached)
195       (let ((expansion (pcase--let* bindings body)))
196         (puthash bindings (cons body expansion) pcase--memoize)
197         expansion))))
198
199 ;;;###autoload
200 (defmacro pcase-let (bindings &rest body)
201   "Like `let' but where you can use `pcase' patterns for bindings.
202 BODY should be a list of expressions, and BINDINGS should be a list of bindings
203 of the form (UPAT EXP)."
204   (declare (indent 1) (debug pcase-let*))
205   (if (null (cdr bindings))
206       `(pcase-let* ,bindings ,@body)
207     (let ((matches '()))
208       (dolist (binding (prog1 bindings (setq bindings nil)))
209         (cond
210          ((memq (car binding) pcase--dontcare-upats)
211           (push (cons (make-symbol "_") (cdr binding)) bindings))
212          ((pcase--trivial-upat-p (car binding)) (push binding bindings))
213          (t
214           (let ((tmpvar (make-symbol (format "x%d" (length bindings)))))
215             (push (cons tmpvar (cdr binding)) bindings)
216             (push (list (car binding) tmpvar) matches)))))
217       `(let ,(nreverse bindings) (pcase-let* ,matches ,@body)))))
218
219 (defmacro pcase-dolist (spec &rest body)
220   (declare (indent 1) (debug ((pcase-UPAT form) body)))
221   (if (pcase--trivial-upat-p (car spec))
222       `(dolist ,spec ,@body)
223     (let ((tmpvar (make-symbol "x")))
224       `(dolist (,tmpvar ,@(cdr spec))
225          (pcase-let* ((,(car spec) ,tmpvar))
226            ,@body)))))
227
228
229 (defun pcase--trivial-upat-p (upat)
230   (and (symbolp upat) (not (memq upat pcase--dontcare-upats))))
231
232 (defun pcase--expand (exp cases)
233   ;; (message "pid=%S (pcase--expand %S ...hash=%S)"
234   ;;          (emacs-pid) exp (sxhash cases))
235   (macroexp-let2 macroexp-copyable-p val exp
236     (let* ((defs ())
237            (seen '())
238            (codegen
239             (lambda (code vars)
240               (let ((prev (assq code seen)))
241                 (if (not prev)
242                     (let ((res (pcase-codegen code vars)))
243                       (push (list code vars res) seen)
244                       res)
245                   ;; Since we use a tree-based pattern matching
246                   ;; technique, the leaves (the places that contain the
247                   ;; code to run once a pattern is matched) can get
248                   ;; copied a very large number of times, so to avoid
249                   ;; code explosion, we need to keep track of how many
250                   ;; times we've used each leaf and move it
251                   ;; to a separate function if that number is too high.
252                   ;;
253                   ;; We've already used this branch.  So it is shared.
254                   (let* ((code (car prev))         (cdrprev (cdr prev))
255                          (prevvars (car cdrprev))  (cddrprev (cdr cdrprev))
256                          (res (car cddrprev)))
257                     (unless (symbolp res)
258                       ;; This is the first repeat, so we have to move
259                       ;; the branch to a separate function.
260                       (let ((bsym
261                              (make-symbol (format "pcase-%d" (length defs)))))
262                         (push `(,bsym (lambda ,(mapcar #'car prevvars) ,@code))
263                               defs)
264                         (setcar res 'funcall)
265                         (setcdr res (cons bsym (mapcar #'cdr prevvars)))
266                         (setcar (cddr prev) bsym)
267                         (setq res bsym)))
268                     (setq vars (copy-sequence vars))
269                     (let ((args (mapcar (lambda (pa)
270                                           (let ((v (assq (car pa) vars)))
271                                             (setq vars (delq v vars))
272                                             (cdr v)))
273                                         prevvars)))
274                       ;; If some of `vars' were not found in `prevvars', that's
275                       ;; OK it just means those vars aren't present in all
276                       ;; branches, so they can be used within the pattern
277                       ;; (e.g. by a `guard/let/pred') but not in the branch.
278                       ;; FIXME: But if some of `prevvars' are not in `vars' we
279                       ;; should remove them from `prevvars'!
280                       `(funcall ,res ,@args)))))))
281            (used-cases ())
282            (main
283             (pcase--u
284              (mapcar (lambda (case)
285                        `(,(pcase--match val (pcase--macroexpand (car case)))
286                          ,(lambda (vars)
287                             (unless (memq case used-cases)
288                               ;; Keep track of the cases that are used.
289                               (push case used-cases))
290                             (funcall
291                              (if (pcase--small-branch-p (cdr case))
292                                  ;; Don't bother sharing multiple
293                                  ;; occurrences of this leaf since it's small.
294                                  #'pcase-codegen codegen)
295                              (cdr case)
296                              vars))))
297                      cases))))
298       (dolist (case cases)
299         (unless (or (memq case used-cases)
300                     (memq (car case) pcase--dontwarn-upats))
301           (message "Redundant pcase pattern: %S" (car case))))
302       (macroexp-let* defs main))))
303
304 (defun pcase--macroexpand (pat)
305   "Expands all macro-patterns in PAT."
306   (let ((head (car-safe pat)))
307     (cond
308      ((null head)
309       (if (pcase--self-quoting-p pat) `',pat pat))
310      ((memq head '(pred guard quote)) pat)
311      ((memq head '(or and)) `(,head ,@(mapcar #'pcase--macroexpand (cdr pat))))
312      ((eq head 'let) `(let ,(pcase--macroexpand (cadr pat)) ,@(cddr pat)))
313      ((eq head 'app) `(app ,(nth 1 pat) ,(pcase--macroexpand (nth 2 pat))))
314      (t
315       (let* ((expander (get head 'pcase-macroexpander))
316              (npat (if expander (apply expander (cdr pat)))))
317         (if (null npat)
318             (error (if expander
319                        "Unexpandable %s pattern: %S"
320                      "Unknown %s pattern: %S")
321                    head pat)
322           (pcase--macroexpand npat)))))))
323
324 ;;;###autoload
325 (defmacro pcase-defmacro (name args &rest body)
326   "Define a pcase UPattern macro."
327   (declare (indent 2) (debug (def-name sexp def-body)) (doc-string 3))
328   `(put ',name 'pcase-macroexpander
329         (lambda ,args ,@body)))
330
331 (defun pcase--match (val upat)
332   "Build a MATCH structure, hoisting all `or's and `and's outside."
333   (cond
334    ;; Hoist or/and patterns into or/and matches.
335    ((memq (car-safe upat) '(or and))
336     `(,(car upat)
337       ,@(mapcar (lambda (upat)
338                   (pcase--match val upat))
339                 (cdr upat))))
340    (t
341     `(match ,val . ,upat))))
342
343 (defun pcase-codegen (code vars)
344   ;; Don't use let*, otherwise macroexp-let* may merge it with some surrounding
345   ;; let* which might prevent the setcar/setcdr in pcase--expand's fancy
346   ;; codegen from later metamorphosing this let into a funcall.
347   `(let ,(mapcar (lambda (b) (list (car b) (cdr b))) vars)
348      ,@code))
349
350 (defun pcase--small-branch-p (code)
351   (and (= 1 (length code))
352        (or (not (consp (car code)))
353            (let ((small t))
354              (dolist (e (car code))
355                (if (consp e) (setq small nil)))
356              small))))
357
358 ;; Try to use `cond' rather than a sequence of `if's, so as to reduce
359 ;; the depth of the generated tree.
360 (defun pcase--if (test then else)
361   (cond
362    ((eq else :pcase--dontcare) then)
363    ((eq then :pcase--dontcare) (debug) else) ;Can/should this ever happen?
364    (t (macroexp-if test then else))))
365
366 ;; Note about MATCH:
367 ;; When we have patterns like `(PAT1 . PAT2), after performing the `consp'
368 ;; check, we want to turn all the similar patterns into ones of the form
369 ;; (and (match car PAT1) (match cdr PAT2)), so you naturally need conjunction.
370 ;; Earlier code hence used branches of the form (MATCHES . CODE) where
371 ;; MATCHES was a list (implicitly a conjunction) of (SYM . PAT).
372 ;; But if we have a pattern of the form (or `(PAT1 . PAT2) PAT3), there is
373 ;; no easy way to eliminate the `consp' check in such a representation.
374 ;; So we replaced the MATCHES by the MATCH below which can be made up
375 ;; of conjunctions and disjunctions, so if we know `foo' is a cons, we can
376 ;; turn (match foo . (or `(PAT1 . PAT2) PAT3)) into
377 ;; (or (and (match car . `PAT1) (match cdr . `PAT2)) (match foo . PAT3)).
378 ;; The downside is that we now have `or' and `and' both in MATCH and
379 ;; in PAT, so there are different equivalent representations and we
380 ;; need to handle them all.  We do not try to systematically
381 ;; canonicalize them to one form over another, but we do occasionally
382 ;; turn one into the other.
383
384 (defun pcase--u (branches)
385   "Expand matcher for rules BRANCHES.
386 Each BRANCH has the form (MATCH CODE . VARS) where
387 CODE is the code generator for that branch.
388 VARS is the set of vars already bound by earlier matches.
389 MATCH is the pattern that needs to be matched, of the form:
390   (match VAR . UPAT)
391   (and MATCH ...)
392   (or MATCH ...)"
393   (when (setq branches (delq nil branches))
394     (let* ((carbranch (car branches))
395            (match (car carbranch)) (cdarbranch (cdr carbranch))
396            (code (car cdarbranch))
397            (vars (cdr cdarbranch)))
398       (pcase--u1 (list match) code vars (cdr branches)))))
399
400 (defun pcase--and (match matches)
401   (if matches `(and ,match ,@matches) match))
402
403 (defconst pcase-mutually-exclusive-predicates
404   '((symbolp . integerp)
405     (symbolp . numberp)
406     (symbolp . consp)
407     (symbolp . arrayp)
408     (symbolp . vectorp)
409     (symbolp . stringp)
410     (symbolp . byte-code-function-p)
411     (integerp . consp)
412     (integerp . arrayp)
413     (integerp . vectorp)
414     (integerp . stringp)
415     (integerp . byte-code-function-p)
416     (numberp . consp)
417     (numberp . arrayp)
418     (numberp . vectorp)
419     (numberp . stringp)
420     (numberp . byte-code-function-p)
421     (consp . arrayp)
422     (consp . vectorp)
423     (consp . stringp)
424     (consp . byte-code-function-p)
425     (arrayp . byte-code-function-p)
426     (vectorp . byte-code-function-p)
427     (stringp . vectorp)
428     (stringp . byte-code-function-p)))
429
430 (defun pcase--mutually-exclusive-p (pred1 pred2)
431   (or (member (cons pred1 pred2)
432               pcase-mutually-exclusive-predicates)
433       (member (cons pred2 pred1)
434               pcase-mutually-exclusive-predicates)))
435
436 (defun pcase--split-match (sym splitter match)
437   (cond
438     ((eq (car-safe match) 'match)
439      (if (not (eq sym (cadr match)))
440          (cons match match)
441        (let ((res (funcall splitter (cddr match))))
442          (cons (or (car res) match) (or (cdr res) match)))))
443     ((memq (car-safe match) '(or and))
444      (let ((then-alts '())
445            (else-alts '())
446            (neutral-elem (if (eq 'or (car match))
447                              :pcase--fail :pcase--succeed))
448            (zero-elem (if (eq 'or (car match)) :pcase--succeed :pcase--fail)))
449        (dolist (alt (cdr match))
450          (let ((split (pcase--split-match sym splitter alt)))
451            (unless (eq (car split) neutral-elem)
452              (push (car split) then-alts))
453            (unless (eq (cdr split) neutral-elem)
454              (push (cdr split) else-alts))))
455        (cons (cond ((memq zero-elem then-alts) zero-elem)
456                    ((null then-alts) neutral-elem)
457                    ((null (cdr then-alts)) (car then-alts))
458                    (t (cons (car match) (nreverse then-alts))))
459              (cond ((memq zero-elem else-alts) zero-elem)
460                    ((null else-alts) neutral-elem)
461                    ((null (cdr else-alts)) (car else-alts))
462                    (t (cons (car match) (nreverse else-alts)))))))
463     ((memq match '(:pcase--succeed :pcase--fail)) (cons match match))
464     (t (error "Uknown MATCH %s" match))))
465
466 (defun pcase--split-rest (sym splitter rest)
467   (let ((then-rest '())
468         (else-rest '()))
469     (dolist (branch rest)
470       (let* ((match (car branch))
471              (code&vars (cdr branch))
472              (split
473               (pcase--split-match sym splitter match)))
474         (unless (eq (car split) :pcase--fail)
475           (push (cons (car split) code&vars) then-rest))
476         (unless (eq (cdr split) :pcase--fail)
477           (push (cons (cdr split) code&vars) else-rest))))
478     (cons (nreverse then-rest) (nreverse else-rest))))
479
480 (defun pcase--split-equal (elem pat)
481   (cond
482    ;; The same match will give the same result.
483    ((and (eq (car-safe pat) 'quote) (equal (cadr pat) elem))
484     '(:pcase--succeed . :pcase--fail))
485    ;; A different match will fail if this one succeeds.
486    ((and (eq (car-safe pat) 'quote)
487          ;; (or (integerp (cadr pat)) (symbolp (cadr pat))
488          ;;     (consp (cadr pat)))
489          )
490     '(:pcase--fail . nil))
491    ((and (eq (car-safe pat) 'pred)
492          (symbolp (cadr pat))
493          (get (cadr pat) 'side-effect-free))
494     (ignore-errors
495       (if (funcall (cadr pat) elem)
496           '(:pcase--succeed . nil)
497         '(:pcase--fail . nil))))))
498
499 (defun pcase--split-member (elems pat)
500   ;; FIXME: The new pred-based member code doesn't do these optimizations!
501   ;; Based on pcase--split-equal.
502   (cond
503    ;; The same match (or a match of membership in a superset) will
504    ;; give the same result, but we don't know how to check it.
505    ;; (???
506    ;;  '(:pcase--succeed . nil))
507    ;; A match for one of the elements may succeed or fail.
508    ((and (eq (car-safe pat) 'quote) (member (cadr pat) elems))
509     nil)
510    ;; A different match will fail if this one succeeds.
511    ((and (eq (car-safe pat) 'quote)
512          ;; (or (integerp (cadr pat)) (symbolp (cadr pat))
513          ;;     (consp (cadr pat)))
514          )
515     '(:pcase--fail . nil))
516    ((and (eq (car-safe pat) 'pred)
517          (symbolp (cadr pat))
518          (get (cadr pat) 'side-effect-free)
519          (ignore-errors
520            (let ((p (cadr pat)) (all t))
521              (dolist (elem elems)
522                (unless (funcall p elem) (setq all nil)))
523              all)))
524     '(:pcase--succeed . nil))))
525
526 (defun pcase--split-pred (vars upat pat)
527   (let (test)
528     (cond
529      ((and (equal upat pat)
530            ;; For predicates like (pred (> a)), two such predicates may
531            ;; actually refer to different variables `a'.
532            (or (and (eq 'pred (car upat)) (symbolp (cadr upat)))
533                ;; FIXME: `vars' gives us the environment in which `upat' will
534                ;; run, but we don't have the environment in which `pat' will
535                ;; run, so we can't do a reliable verification.  But let's try
536                ;; and catch at least the easy cases such as (bug#14773).
537                (not (pcase--fgrep (mapcar #'car vars) (cadr upat)))))
538       '(:pcase--succeed . :pcase--fail))
539      ((and (eq 'pred (car upat))
540            (let ((otherpred
541                   (cond ((eq 'pred (car-safe pat)) (cadr pat))
542                         ((not (eq 'quote (car-safe pat))) nil)
543                         ((consp (cadr pat)) #'consp)
544                         ((vectorp (cadr pat)) #'vectorp)
545                         ((byte-code-function-p (cadr pat))
546                          #'byte-code-function-p))))
547              (pcase--mutually-exclusive-p (cadr upat) otherpred)))
548       '(:pcase--fail . nil))
549      ((and (eq 'pred (car upat))
550            (eq 'quote (car-safe pat))
551            (symbolp (cadr upat))
552            (or (symbolp (cadr pat)) (stringp (cadr pat)) (numberp (cadr pat)))
553            (get (cadr upat) 'side-effect-free)
554            (ignore-errors
555              (setq test (list (funcall (cadr upat) (cadr pat))))))
556       (if (car test)
557           '(nil . :pcase--fail)
558         '(:pcase--fail . nil))))))
559
560 (defun pcase--fgrep (vars sexp)
561   "Check which of the symbols VARS appear in SEXP."
562   (let ((res '()))
563     (while (consp sexp)
564       (dolist (var (pcase--fgrep vars (pop sexp)))
565         (unless (memq var res) (push var res))))
566     (and (memq sexp vars) (not (memq sexp res)) (push sexp res))
567     res))
568
569 (defun pcase--self-quoting-p (upat)
570   (or (keywordp upat) (numberp upat) (stringp upat)))
571
572 (defun pcase--app-subst-match (match sym fun nsym)
573   (cond
574    ((eq (car-safe match) 'match)
575     (if (and (eq sym (cadr match))
576              (eq 'app (car-safe (cddr match)))
577              (equal fun (nth 1 (cddr match))))
578         (pcase--match nsym (nth 2 (cddr match)))
579       match))
580    ((memq (car-safe match) '(or and))
581     `(,(car match)
582       ,@(mapcar (lambda (match)
583                   (pcase--app-subst-match match sym fun nsym))
584                 (cdr match))))
585    ((memq match '(:pcase--succeed :pcase--fail)) match)
586    (t (error "Uknown MATCH %s" match))))
587
588 (defun pcase--app-subst-rest (rest sym fun nsym)
589   (mapcar (lambda (branch)
590             `(,(pcase--app-subst-match (car branch) sym fun nsym)
591               ,@(cdr branch)))
592           rest))
593
594 (defsubst pcase--mark-used (sym)
595   ;; Exceptionally, `sym' may be a constant expression rather than a symbol.
596   (if (symbolp sym) (put sym 'pcase-used t)))
597
598 (defmacro pcase--flip (fun arg1 arg2)
599   "Helper function, used internally to avoid (funcall (lambda ...) ...)."
600   (declare (debug (sexp body)))
601   `(,fun ,arg2 ,arg1))
602
603 (defun pcase--funcall (fun arg vars)
604   "Build a function call to FUN with arg ARG."
605   (if (symbolp fun)
606       `(,fun ,arg)
607     (let* (;; `vs' is an upper bound on the vars we need.
608            (vs (pcase--fgrep (mapcar #'car vars) fun))
609            (env (mapcar (lambda (var)
610                           (list var (cdr (assq var vars))))
611                         vs))
612            (call (progn
613                    (when (memq arg vs)
614                      ;; `arg' is shadowed by `env'.
615                      (let ((newsym (make-symbol "x")))
616                        (push (list newsym arg) env)
617                        (setq arg newsym)))
618                    (if (functionp fun)
619                        `(funcall #',fun ,arg)
620                      `(,@fun ,arg)))))
621       (if (null vs)
622           call
623         ;; Let's not replace `vars' in `fun' since it's
624         ;; too difficult to do it right, instead just
625         ;; let-bind `vars' around `fun'.
626         `(let* ,env ,call)))))
627
628 (defun pcase--eval (exp vars)
629   "Build an expression that will evaluate EXP."
630   (let* ((found (assq exp vars)))
631     (if found (cdr found)
632       (let* ((vs (pcase--fgrep (mapcar #'car vars) exp))
633              (env (mapcar (lambda (v) (list v (cdr (assq v vars))))
634                           vs)))
635         (if env (macroexp-let* env exp) exp)))))
636
637 ;; It's very tempting to use `pcase' below, tho obviously, it'd create
638 ;; bootstrapping problems.
639 (defun pcase--u1 (matches code vars rest)
640   "Return code that runs CODE (with VARS) if MATCHES match.
641 Otherwise, it defers to REST which is a list of branches of the form
642 \(ELSE-MATCH ELSE-CODE . ELSE-VARS)."
643   ;; Depending on the order in which we choose to check each of the MATCHES,
644   ;; the resulting tree may be smaller or bigger.  So in general, we'd want
645   ;; to be careful to chose the "optimal" order.  But predicate
646   ;; patterns make this harder because they create dependencies
647   ;; between matches.  So we don't bother trying to reorder anything.
648   (cond
649    ((null matches) (funcall code vars))
650    ((eq :pcase--fail (car matches)) (pcase--u rest))
651    ((eq :pcase--succeed (car matches))
652     (pcase--u1 (cdr matches) code vars rest))
653    ((eq 'and (caar matches))
654     (pcase--u1 (append (cdar matches) (cdr matches)) code vars rest))
655    ((eq 'or (caar matches))
656     (let* ((alts (cdar matches))
657            (var (if (eq (caar alts) 'match) (cadr (car alts))))
658            (simples '()) (others '()) (memq-ok t))
659       (when var
660         (dolist (alt alts)
661           (if (and (eq (car alt) 'match) (eq var (cadr alt))
662                    (let ((upat (cddr alt)))
663                      (eq (car-safe upat) 'quote)))
664               (let ((val (cadr (cddr alt))))
665                 (unless (or (integerp val) (symbolp val))
666                   (setq memq-ok nil))
667                 (push (cadr (cddr alt)) simples))
668             (push alt others))))
669       (cond
670        ((null alts) (error "Please avoid it") (pcase--u rest))
671        ;; Yes, we can use `memq' (or `member')!
672        ((> (length simples) 1)
673         (pcase--u1 (cons `(match ,var
674                                  . (pred (pcase--flip
675                                           ,(if memq-ok #'memq #'member)
676                                           ',simples)))
677                          (cdr matches))
678                    code vars
679                    (if (null others) rest
680                      (cons (cons
681                             (pcase--and (if (cdr others)
682                                             (cons 'or (nreverse others))
683                                           (car others))
684                                         (cdr matches))
685                             (cons code vars))
686                            rest))))
687        (t
688         (pcase--u1 (cons (pop alts) (cdr matches)) code vars
689                    (if (null alts) (progn (error "Please avoid it") rest)
690                      (cons (cons
691                             (pcase--and (if (cdr alts)
692                                             (cons 'or alts) (car alts))
693                                         (cdr matches))
694                             (cons code vars))
695                            rest)))))))
696    ((eq 'match (caar matches))
697     (let* ((popmatches (pop matches))
698            (_op (car popmatches))      (cdrpopmatches (cdr popmatches))
699            (sym (car cdrpopmatches))
700            (upat (cdr cdrpopmatches)))
701       (cond
702        ((memq upat '(t _)) (pcase--u1 matches code vars rest))
703        ((eq upat 'pcase--dontcare) :pcase--dontcare)
704        ((memq (car-safe upat) '(guard pred))
705         (if (eq (car upat) 'pred) (pcase--mark-used sym))
706         (let* ((splitrest
707                 (pcase--split-rest
708                  sym (lambda (pat) (pcase--split-pred vars upat pat)) rest))
709                (then-rest (car splitrest))
710                (else-rest (cdr splitrest)))
711           (pcase--if (if (eq (car upat) 'pred)
712                          (pcase--funcall (cadr upat) sym vars)
713                        (pcase--eval (cadr upat) vars))
714                      (pcase--u1 matches code vars then-rest)
715                      (pcase--u else-rest))))
716        ((symbolp upat)
717         (pcase--mark-used sym)
718         (if (not (assq upat vars))
719             (pcase--u1 matches code (cons (cons upat sym) vars) rest)
720           ;; Non-linear pattern.  Turn it into an `eq' test.
721           (pcase--u1 (cons `(match ,sym . (pred (eq ,(cdr (assq upat vars)))))
722                            matches)
723                      code vars rest)))
724        ((eq (car-safe upat) 'let)
725         ;; A upat of the form (let VAR EXP).
726         ;; (pcase--u1 matches code
727         ;;            (cons (cons (nth 1 upat) (nth 2 upat)) vars) rest)
728         (macroexp-let2
729             macroexp-copyable-p sym
730             (pcase--eval (nth 2 upat) vars)
731           (pcase--u1 (cons (pcase--match sym (nth 1 upat)) matches)
732                      code vars rest)))
733        ((eq (car-safe upat) 'app)
734         ;; A upat of the form (app FUN UPAT)
735         (pcase--mark-used sym)
736         (let* ((fun (nth 1 upat))
737                (nsym (make-symbol "x"))
738                (body
739                 ;; We don't change `matches' to reuse the newly computed value,
740                 ;; because we assume there shouldn't be such redundancy in there.
741                 (pcase--u1 (cons (pcase--match nsym (nth 2 upat)) matches)
742                            code vars
743                            (pcase--app-subst-rest rest sym fun nsym))))
744           (if (not (get nsym 'pcase-used))
745               body
746             (macroexp-let*
747              `((,nsym ,(pcase--funcall fun sym vars)))
748              body))))
749        ((eq (car-safe upat) 'quote)
750         (pcase--mark-used sym)
751         (let* ((val (cadr upat))
752                (splitrest (pcase--split-rest
753                            sym (lambda (pat) (pcase--split-equal val pat)) rest))
754                (then-rest (car splitrest))
755                (else-rest (cdr splitrest)))
756           (pcase--if (cond
757                       ((null val) `(null ,sym))
758                       ((or (integerp val) (symbolp val))
759                        (if (pcase--self-quoting-p val)
760                            `(eq ,sym ,val)
761                          `(eq ,sym ',val)))
762                       (t `(equal ,sym ',val)))
763                      (pcase--u1 matches code vars then-rest)
764                      (pcase--u else-rest))))
765        ((eq (car-safe upat) 'not)
766         ;; FIXME: The implementation below is naive and results in
767         ;; inefficient code.
768         ;; To make it work right, we would need to turn pcase--u1's
769         ;; `code' and `vars' into a single argument of the same form as
770         ;; `rest'.  We would also need to split this new `then-rest' argument
771         ;; for every test (currently we don't bother to do it since
772         ;; it's only useful for odd patterns like (and `(PAT1 . PAT2)
773         ;; `(PAT3 . PAT4)) which the programmer can easily rewrite
774         ;; to the more efficient `(,(and PAT1 PAT3) . ,(and PAT2 PAT4))).
775         (pcase--u1 `((match ,sym . ,(cadr upat)))
776                    ;; FIXME: This codegen is not careful to share its
777                    ;; code if used several times: code blow up is likely.
778                    (lambda (_vars)
779                      ;; `vars' will likely contain bindings which are
780                      ;; not always available in other paths to
781                      ;; `rest', so there' no point trying to pass
782                      ;; them down.
783                      (pcase--u rest))
784                    vars
785                    (list `((and . ,matches) ,code . ,vars))))
786        (t (error "Unknown internal pattern `%S'" upat)))))
787    (t (error "Incorrect MATCH %S" (car matches)))))
788
789 (pcase-defmacro \` (qpat)
790   (cond
791    ((eq (car-safe qpat) '\,) (cadr qpat))
792    ((vectorp qpat)
793     `(and (pred vectorp)
794           (app length ,(length qpat))
795           ,@(let ((upats nil))
796               (dotimes (i (length qpat))
797                 (push `(app (pcase--flip aref ,i) ,(list '\` (aref qpat i)))
798                       upats))
799               (nreverse upats))))
800    ((consp qpat)
801     `(and (pred consp)
802           (app car ,(list '\` (car qpat)))
803           (app cdr ,(list '\` (cdr qpat)))))
804    ((or (stringp qpat) (integerp qpat) (symbolp qpat)) `',qpat)))
805
806
807 (provide 'pcase)
808 ;;; pcase.el ends here