| blob | 46a5eedd15018c9d55fae485958b858eeee65f3e |
1 ;;; pcase.el --- ML-style pattern-matching macro for Elisp -*- lexical-binding: t -*-
3 ;; Copyright (C) 2010-2017 Free Software Foundation, Inc.
5 ;; Author: Stefan Monnier <monnier@iro.umontreal.ca>
6 ;; Keywords:
8 ;; This file is part of GNU Emacs.
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.
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.
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/>.
23 ;;; Commentary:
25 ;; ML-style pattern matching.
26 ;; The entry points are autoloaded.
28 ;; Todo:
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 PAT). 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.
54 ;;; Code:
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.
66 ;; (defconst pcase--memoize-1 (make-hash-table :test 'eq))
67 ;; (defconst pcase--memoize-2 (make-hash-table :weakness 'key :test 'equal))
74 pcase-PAT
75 (&or symbolp
82 pcase-MACRO
83 sexp))
86 pcase-FUN
87 (&or lambda-expr
88 ;; Punt on macros/special forms.
90 sexp))
92 ;; See bug#24717
95 ;; Only called from edebug.
106 specs)))))
109 ;;;###autoload
111 "Evaluate EXP and attempt to match it against structural patterns.
112 CASES is a list of elements of the form (PATTERN CODE...).
114 A structural PATTERN describes a template that identifies a class
116 two element list, binding its elements to symbols named `foo' and
117 `bar' -- in much the same way that `cl-destructuring-bind' would.
119 A significant difference from `cl-destructuring-bind' is that, if
120 a pattern match fails, the next case is tried until either a
121 successful match is found or there are no more cases.
123 Another difference is that pattern elements may be quoted,
125 matches only against two element lists containing the symbols
126 `foo' and `bar' in that order. (As a short-hand, atoms always
127 match themselves, such as numbers or strings, and need not be
128 quoted.)
130 Lastly, a pattern can be logical, such as (pred numberp), that
131 matches any number-like element; or the symbol `_', that matches
132 anything. Also, when patterns are backquoted, a comma may be
133 used to introduce logical patterns inside backquoted patterns.
135 The complete list of standard patterns is as follows:
137 _ matches anything.
138 SYMBOL matches anything and binds it to SYMBOL.
139 If a SYMBOL is used twice in the same pattern
140 the second occurrence becomes an `eq'uality test.
141 (or PAT...) matches if any of the patterns matches.
142 (and PAT...) matches if all the patterns match.
145 ATOM can be a keyword, an integer, or a string.
146 (pred FUN) matches if FUN applied to the object returns non-nil.
147 (guard BOOLEXP) matches if BOOLEXP evaluates to non-nil.
148 (let PAT EXP) matches if EXP matches PAT.
149 (app FUN PAT) matches if FUN applied to the object matches PAT.
151 Additional patterns can be defined using `pcase-defmacro'.
153 The FUN argument in the `app' pattern may have the following forms:
154 SYMBOL or (lambda ARGS BODY) in which case it's called with one argument.
155 (F ARG1 .. ARGn) in which case F gets called with an n+1'th argument
156 which is the value being matched.
157 So a FUN of the form SYMBOL is equivalent to (FUN).
158 FUN can refer to variables bound earlier in the pattern.
160 See Info node `(elisp) Pattern matching case statement' in the
161 Emacs Lisp manual for more information and examples."
163 ;; We want to use a weak hash table as a cache, but the key will unavoidably
164 ;; be based on `exp' and `cases', yet `cases' is a fresh new list each time
165 ;; we're called so it'll be immediately GC'd. So we use (car cases) as key
166 ;; which does come straight from the source code and should hence not be GC'd
167 ;; so easily.
169 ;; data = (EXP CASES . EXPANSION)
171 ;; We have the right expansion.
173 ;; (when (gethash (car cases) pcase--memoize-1)
174 ;; (message "pcase-memoize failed because of weak key!!"))
175 ;; (when (gethash (car cases) pcase--memoize-2)
176 ;; (message "pcase-memoize failed because of eq test on %S"
177 ;; (car cases)))
182 ;; (puthash (car cases) `(,exp ,cases ,@expansion) pcase--memoize-1)
183 ;; (puthash (car cases) `(,exp ,cases ,@expansion) pcase--memoize-2)
184 expansion))))
189 ;; FIXME: Obviously, this will collide with nadvice's use of
190 ;; function-documentation if we happen to advise `pcase'.
195 ;; So that eg emacs -Q -l cl-lib --eval "(documentation 'pcase)" works,
196 ;; where cl-lib is anything using pcase-defmacro.
212 ;;;###autoload
214 "The exhaustive version of `pcase' (which see)."
219 ;; FIXME: Could we add the FILE:LINE data in the error message?
222 ;;;###autoload
224 "Like `lambda' but allow each argument to be a pattern.
225 I.e. accepts the usual &optional and &rest keywords, but every
226 formal argument can be any pattern accepted by `pcase' (a mere
227 variable name being but a special case of it)."
234 ;; Simple vars and &rest/&optional are just passed
235 ;; through unchanged.
236 pat
240 arg)))
241 lambda-list)))
255 ;; We can either signal an error here, or just use `pcase--dontcare'
256 ;; which generates more efficient code. In practice, if we use
257 ;; `pcase--dontcare' we will still often get an error and the few
258 ;; cases where we don't do not matter that much, so
259 ;; it's a better choice.
262 ;;;###autoload
264 "Like `let*' but where you can use `pcase' patterns for bindings.
265 BODY should be an expression, and BINDINGS should be a list of bindings
266 of the form (PAT EXP)."
270 ;; cached = (BODY . EXPANSION)
275 expansion))))
277 ;;;###autoload
279 "Like `let' but where you can use `pcase' patterns for bindings.
280 BODY should be a list of expressions, and BINDINGS should be a list of bindings
281 of the form (PAT EXP).
282 The macro is expanded and optimized under the assumption that those
283 patterns *will* match, so a mismatch may go undetected or may cause
284 any kind of error."
300 ;;;###autoload
302 "Like `dolist' but where the binding can be a `pcase' pattern.
317 ;; (message "pid=%S (pcase--expand %S ...hash=%S)"
318 ;; (emacs-pid) exp (sxhash cases))
328 res)
329 ;; Since we use a tree-based pattern matching
330 ;; technique, the leaves (the places that contain the
331 ;; code to run once a pattern is matched) can get
332 ;; copied a very large number of times, so to avoid
333 ;; code explosion, we need to keep track of how many
334 ;; times we've used each leaf and move it
335 ;; to a separate function if that number is too high.
336 ;;
337 ;; We've already used this branch. So it is shared.
342 ;; This is the first repeat, so we have to move
343 ;; the branch to a separate function.
347 defs)
357 prevvars)))
358 ;; If some of `vars' were not found in `prevvars', that's
359 ;; OK it just means those vars aren't present in all
360 ;; branches, so they can be used within the pattern
361 ;; (e.g. by a `guard/let/pred') but not in the branch.
362 ;; FIXME: But if some of `prevvars' are not in `vars' we
363 ;; should remove them from `prevvars'!
372 ;; Keep track of the cases that are used.
376 ;; Don't bother sharing multiple
377 ;; occurrences of this leaf since it's small.
380 vars))))
381 cases))))
389 "Expands all macro-patterns in PAT."
403 "Unexpandable %s pattern: %S"
405 head pat)
408 ;;;###autoload
410 "Define a new kind of pcase PATTERN, by macro expansion.
411 Patterns of the form (NAME ...) will be expanded according
412 to this macro."
414 ;; Add the function via `fsym', so that an autoload cookie placed
415 ;; on a pcase-defmacro will cause the macro to be loaded on demand.
425 "Build a MATCH structure, hoisting all `or's and `and's outside."
427 ;; Hoist or/and patterns into or/and matches.
437 ;; Don't use let*, otherwise macroexp-let* may merge it with some surrounding
438 ;; let* which might prevent the setcar/setcdr in pcase--expand's fancy
439 ;; codegen from later metamorphosing this let into a funcall.
449 small))))
451 ;; Try to use `cond' rather than a sequence of `if's, so as to reduce
452 ;; the depth of the generated tree.
459 ;; Note about MATCH:
460 ;; When we have patterns like `(PAT1 . PAT2), after performing the `consp'
461 ;; check, we want to turn all the similar patterns into ones of the form
462 ;; (and (match car PAT1) (match cdr PAT2)), so you naturally need conjunction.
463 ;; Earlier code hence used branches of the form (MATCHES . CODE) where
464 ;; MATCHES was a list (implicitly a conjunction) of (SYM . PAT).
465 ;; But if we have a pattern of the form (or `(PAT1 . PAT2) PAT3), there is
466 ;; no easy way to eliminate the `consp' check in such a representation.
467 ;; So we replaced the MATCHES by the MATCH below which can be made up
468 ;; of conjunctions and disjunctions, so if we know `foo' is a cons, we can
469 ;; turn (match foo . (or `(PAT1 . PAT2) PAT3)) into
470 ;; (or (and (match car . `PAT1) (match cdr . `PAT2)) (match foo . PAT3)).
471 ;; The downside is that we now have `or' and `and' both in MATCH and
472 ;; in PAT, so there are different equivalent representations and we
473 ;; need to handle them all. We do not try to systematically
474 ;; canonicalize them to one form over another, but we do occasionally
475 ;; turn one into the other.
478 "Expand matcher for rules BRANCHES.
479 Each BRANCH has the form (MATCH CODE . VARS) where
480 CODE is the code generator for that branch.
481 VARS is the set of vars already bound by earlier matches.
482 MATCH is the pattern that needs to be matched, of the form:
483 (match VAR . PAT)
484 (and MATCH ...)
485 (or MATCH ...)"
526 pcase-mutually-exclusive-predicates)
528 pcase-mutually-exclusive-predicates)))
576 ;; The same match will give the same result.
579 ;; A different match will fail if this one succeeds.
581 ;; (or (integerp (cadr pat)) (symbolp (cadr pat))
582 ;; (consp (cadr pat)))
583 )
594 ;; FIXME: The new pred-based member code doesn't do these optimizations!
595 ;; Based on pcase--split-equal.
597 ;; The same match (or a match of membership in a superset) will
598 ;; give the same result, but we don't know how to check it.
599 ;; (???
600 ;; '(:pcase--succeed . nil))
601 ;; A match for one of the elements may succeed or fail.
603 nil)
604 ;; A different match will fail if this one succeeds.
606 ;; (or (integerp (cadr pat)) (symbolp (cadr pat))
607 ;; (consp (cadr pat)))
608 )
617 all)))
624 ;; For predicates like (pred (> a)), two such predicates may
625 ;; actually refer to different variables `a'.
627 ;; FIXME: `vars' gives us the environment in which `upat' will
628 ;; run, but we don't have the environment in which `pat' will
629 ;; run, so we can't do a reliable verification. But let's try
630 ;; and catch at least the easy cases such as (bug#14773).
656 "Check which of the symbols VARS appear in SEXP."
662 res))
674 match))
687 rest))
690 ;; Exceptionally, `sym' may be a constant expression rather than a symbol.
694 "Helper function, used internally to avoid (funcall (lambda ...) ...)."
699 "Build a function call to FUN with arg ARG."
706 vs))
709 ;; `arg' is shadowed by `env'.
717 call
718 ;; Let's not replace `vars' in `fun' since it's
719 ;; too difficult to do it right, instead just
720 ;; let-bind `vars' around `fun'.
724 "Build an expression that will evaluate EXP."
729 vs)))
732 ;; It's very tempting to use `pcase' below, tho obviously, it'd create
733 ;; bootstrapping problems.
735 "Return code that runs CODE (with VARS) if MATCHES match.
736 Otherwise, it defers to REST which is a list of branches of the form
737 \(ELSE-MATCH ELSE-CODE . ELSE-VARS)."
738 ;; Depending on the order in which we choose to check each of the MATCHES,
739 ;; the resulting tree may be smaller or bigger. So in general, we'd want
740 ;; to be careful to chose the "optimal" order. But predicate
741 ;; patterns make this harder because they create dependencies
742 ;; between matches. So we don't bother trying to reorder anything.
766 ;; Yes, we can use `memq' (or `member')!
773 code vars
781 rest))))
790 rest)))))))
801 "Pattern t is deprecated. Use `_' instead"
802 code))))
820 ;; Non-linear pattern. Turn it into an `eq' test.
822 matches)
823 code vars rest)))
825 ;; A upat of the form (let VAR EXP).
826 ;; (pcase--u1 matches code
827 ;; (cons (cons (nth 1 upat) (nth 2 upat)) vars) rest)
829 macroexp-copyable-p sym
832 code vars rest)))
834 ;; A upat of the form (app FUN PAT)
839 ;; We don't change `matches' to reuse the newly computed value,
840 ;; because we assume there shouldn't be such redundancy in there.
842 code vars
845 body
848 body))))
866 ;; FIXME: The implementation below is naive and results in
867 ;; inefficient code.
868 ;; To make it work right, we would need to turn pcase--u1's
869 ;; `code' and `vars' into a single argument of the same form as
870 ;; `rest'. We would also need to split this new `then-rest' argument
871 ;; for every test (currently we don't bother to do it since
872 ;; it's only useful for odd patterns like (and `(PAT1 . PAT2)
873 ;; `(PAT3 . PAT4)) which the programmer can easily rewrite
874 ;; to the more efficient `(,(and PAT1 PAT3) . ,(and PAT2 PAT4))).
876 ;; FIXME: This codegen is not careful to share its
877 ;; code if used several times: code blow up is likely.
879 ;; `vars' will likely contain bindings which are
880 ;; not always available in other paths to
881 ;; `rest', so there' no point trying to pass
882 ;; them down.
884 vars
890 pcase-QPAT
891 ;; Cf. edebug spec for `backquote-form' in edebug.el.
896 sexp))
899 "Backquote-style pcase patterns.
900 QPAT can take the following forms:
901 (QPAT1 . QPAT2) matches if QPAT1 matches the car and QPAT2 the cdr.
902 [QPAT1 QPAT2..QPATn] matches a vector of length n and QPAT1..QPATn match
903 its 0..(n-1)th elements, respectively.
904 ,PAT matches if the pcase pattern PAT matches.
905 ATOM matches if the object is `equal' to ATOM.
906 ATOM can be a symbol, an integer, or a string."
916 upats))
927 ;;; pcase.el ends here