emacs-lisp/package.el: Move the compatibility-table building logic.
[emacs.git] / lisp / emacs-lisp / cconv.el
blobfa8240759336237fe5b9231121984edb90e9556c
1 ;;; cconv.el --- Closure conversion for statically scoped Emacs lisp. -*- lexical-binding: t; coding: utf-8 -*-
3 ;; Copyright (C) 2011-2015 Free Software Foundation, Inc.
5 ;; Author: Igor Kuzmin <kzuminig@iro.umontreal.ca>
6 ;; Maintainer: emacs-devel@gnu.org
7 ;; Keywords: lisp
8 ;; Package: emacs
10 ;; This file is part of GNU Emacs.
12 ;; GNU Emacs is free software: you can redistribute it and/or modify
13 ;; it under the terms of the GNU General Public License as published by
14 ;; the Free Software Foundation, either version 3 of the License, or
15 ;; (at your option) any later version.
17 ;; GNU Emacs is distributed in the hope that it will be useful,
18 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
19 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 ;; GNU General Public License for more details.
22 ;; You should have received a copy of the GNU General Public License
23 ;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>.
25 ;;; Commentary:
27 ;; This takes a piece of Elisp code, and eliminates all free variables from
28 ;; lambda expressions. The user entry points are cconv-closure-convert and
29 ;; cconv-closure-convert-toplevel (for toplevel forms).
30 ;; All macros should be expanded beforehand.
32 ;; Here is a brief explanation how this code works.
33 ;; Firstly, we analyze the tree by calling cconv-analyze-form.
34 ;; This function finds all mutated variables, all functions that are suitable
35 ;; for lambda lifting and all variables captured by closure. It passes the tree
36 ;; once, returning a list of three lists.
38 ;; Then we calculate the intersection of the first and third lists returned by
39 ;; cconv-analyze form to find all mutated variables that are captured by
40 ;; closure.
42 ;; Armed with this data, we call cconv-closure-convert-rec, that rewrites the
43 ;; tree recursively, lifting lambdas where possible, building closures where it
44 ;; is needed and eliminating mutable variables used in closure.
46 ;; We do following replacements :
47 ;; (lambda (v1 ...) ... fv1 fv2 ...) => (lambda (v1 ... fv1 fv2 ) ... fv1 fv2 .)
48 ;; if the function is suitable for lambda lifting (if all calls are known)
50 ;; (lambda (v0 ...) ... fv0 .. fv1 ...) =>
51 ;; (internal-make-closure (v0 ...) (fv0 ...) <doc>
52 ;; ... (internal-get-closed-var 0) ... (internal-get-closed-var 1) ...)
54 ;; If the function has no free variables, we don't do anything.
56 ;; If a variable is mutated (updated by setq), and it is used in a closure
57 ;; we wrap its definition with list: (list val) and we also replace
58 ;; var => (car-safe var) wherever this variable is used, and also
59 ;; (setq var value) => (setcar var value) where it is updated.
61 ;; If defun argument is closure mutable, we letbind it and wrap it's
62 ;; definition with list.
63 ;; (defun foo (... mutable-arg ...) ...) =>
64 ;; (defun foo (... m-arg ...) (let ((m-arg (list m-arg))) ...))
66 ;;; Code:
68 ;; PROBLEM cases found during conversion to lexical binding.
69 ;; We should try and detect and warn about those cases, even
70 ;; for lexical-binding==nil to help prepare the migration.
71 ;; - Uses of run-hooks, and friends.
72 ;; - Cases where we want to apply the same code to different vars depending on
73 ;; some test. These sometimes use a (let ((foo (if bar 'a 'b)))
74 ;; ... (symbol-value foo) ... (set foo ...)).
76 ;; TODO: (not just for cconv but also for the lexbind changes in general)
77 ;; - let (e)debug find the value of lexical variables from the stack.
78 ;; - make eval-region do the eval-sexp-add-defvars dance.
79 ;; - byte-optimize-form should be applied before cconv.
80 ;; OTOH, the warnings emitted by cconv-analyze need to come before optimize
81 ;; since afterwards they can because obnoxious (warnings about an "unused
82 ;; variable" should not be emitted when the variable use has simply been
83 ;; optimized away).
84 ;; - let macros specify that some let-bindings come from the same source,
85 ;; so the unused warning takes all uses into account.
86 ;; - let interactive specs return a function to build the args (to stash into
87 ;; command-history).
88 ;; - canonize code in macro-expand so we don't have to handle (let (var) body)
89 ;; and other oddities.
90 ;; - new byte codes for unwind-protect so that closures aren't needed at all.
91 ;; - a reference to a var that is known statically to always hold a constant
92 ;; should be turned into a byte-constant rather than a byte-stack-ref.
93 ;; Hmm... right, that's called constant propagation and could be done here,
94 ;; but when that constant is a function, we have to be careful to make sure
95 ;; the bytecomp only compiles it once.
96 ;; - Since we know here when a variable is not mutated, we could pass that
97 ;; info to the byte-compiler, e.g. by using a new `immutable-let'.
98 ;; - call known non-escaping functions with `goto' rather than `call'.
99 ;; - optimize mapc to a dolist loop.
101 ;; (defmacro dlet (binders &rest body)
102 ;; ;; Works in both lexical and non-lexical mode.
103 ;; (declare (indent 1) (debug let))
104 ;; `(progn
105 ;; ,@(mapcar (lambda (binder)
106 ;; `(defvar ,(if (consp binder) (car binder) binder)))
107 ;; binders)
108 ;; (let ,binders ,@body)))
110 ;; (defmacro llet (binders &rest body)
111 ;; ;; Only works in lexical-binding mode.
112 ;; `(funcall
113 ;; (lambda ,(mapcar (lambda (binder) (if (consp binder) (car binder) binder))
114 ;; binders)
115 ;; ,@body)
116 ;; ,@(mapcar (lambda (binder) (if (consp binder) (cadr binder)))
117 ;; binders)))
119 (eval-when-compile (require 'cl-lib))
121 (defconst cconv-liftwhen 6
122 "Try to do lambda lifting if the number of arguments + free variables
123 is less than this number.")
124 ;; List of all the variables that are both captured by a closure
125 ;; and mutated. Each entry in the list takes the form
126 ;; (BINDER . PARENTFORM) where BINDER is the (VAR VAL) that introduces the
127 ;; variable (or is just (VAR) for variables not introduced by let).
128 (defvar cconv-captured+mutated)
130 ;; List of candidates for lambda lifting.
131 ;; Each candidate has the form (BINDER . PARENTFORM). A candidate
132 ;; is a variable that is only passed to `funcall' or `apply'.
133 (defvar cconv-lambda-candidates)
135 ;; Alist associating to each function body the list of its free variables.
136 (defvar cconv-freevars-alist)
138 ;;;###autoload
139 (defun cconv-closure-convert (form)
140 "Main entry point for closure conversion.
141 -- FORM is a piece of Elisp code after macroexpansion.
142 -- TOPLEVEL(optional) is a boolean variable, true if we are at the root of AST
144 Returns a form where all lambdas don't have any free variables."
145 ;; (message "Entering cconv-closure-convert...")
146 (let ((cconv-freevars-alist '())
147 (cconv-lambda-candidates '())
148 (cconv-captured+mutated '()))
149 ;; Analyze form - fill these variables with new information.
150 (cconv-analyze-form form '())
151 (setq cconv-freevars-alist (nreverse cconv-freevars-alist))
152 (prog1 (cconv-convert form nil nil) ; Env initially empty.
153 (cl-assert (null cconv-freevars-alist)))))
155 ;;;###autoload
156 (defun cconv-warnings-only (form)
157 "Add the warnings that closure conversion would encounter."
158 (let ((cconv-freevars-alist '())
159 (cconv-lambda-candidates '())
160 (cconv-captured+mutated '()))
161 ;; Analyze form - fill these variables with new information.
162 (cconv-analyze-form form '())
163 ;; But don't perform the closure conversion.
164 form))
166 (defconst cconv--dummy-var (make-symbol "ignored"))
168 (defun cconv--set-diff (s1 s2)
169 "Return elements of set S1 that are not in set S2."
170 (let ((res '()))
171 (dolist (x s1)
172 (unless (memq x s2) (push x res)))
173 (nreverse res)))
175 (defun cconv--set-diff-map (s m)
176 "Return elements of set S that are not in Dom(M)."
177 (let ((res '()))
178 (dolist (x s)
179 (unless (assq x m) (push x res)))
180 (nreverse res)))
182 (defun cconv--map-diff (m1 m2)
183 "Return the submap of map M1 that has Dom(M2) removed."
184 (let ((res '()))
185 (dolist (x m1)
186 (unless (assq (car x) m2) (push x res)))
187 (nreverse res)))
189 (defun cconv--map-diff-elem (m x)
190 "Return the map M minus any mapping for X."
191 ;; Here we assume that X appears at most once in M.
192 (let* ((b (assq x m))
193 (res (if b (remq b m) m)))
194 (cl-assert (null (assq x res))) ;; Check the assumption was warranted.
195 res))
197 (defun cconv--map-diff-set (m s)
198 "Return the map M minus any mapping for elements of S."
199 ;; Here we assume that X appears at most once in M.
200 (let ((res '()))
201 (dolist (b m)
202 (unless (memq (car b) s) (push b res)))
203 (nreverse res)))
205 (defun cconv--convert-function (args body env parentform &optional docstring)
206 (cl-assert (equal body (caar cconv-freevars-alist)))
207 (let* ((fvs (cdr (pop cconv-freevars-alist)))
208 (body-new '())
209 (letbind '())
210 (envector ())
211 (i 0)
212 (new-env ()))
213 ;; Build the "formal and actual envs" for the closure-converted function.
214 (dolist (fv fvs)
215 (let ((exp (or (cdr (assq fv env)) fv)))
216 (pcase exp
217 ;; If `fv' is a variable that's wrapped in a cons-cell,
218 ;; we want to put the cons-cell itself in the closure,
219 ;; rather than just a copy of its current content.
220 (`(car-safe ,iexp . ,_)
221 (push iexp envector)
222 (push `(,fv . (car-safe (internal-get-closed-var ,i))) new-env))
224 (push exp envector)
225 (push `(,fv . (internal-get-closed-var ,i)) new-env))))
226 (setq i (1+ i)))
227 (setq envector (nreverse envector))
228 (setq new-env (nreverse new-env))
230 (dolist (arg args)
231 (if (not (member (cons (list arg) parentform) cconv-captured+mutated))
232 (if (assq arg new-env) (push `(,arg) new-env))
233 (push `(,arg . (car-safe ,arg)) new-env)
234 (push `(,arg (list ,arg)) letbind)))
236 (setq body-new (mapcar (lambda (form)
237 (cconv-convert form new-env nil))
238 body))
240 (when letbind
241 (let ((special-forms '()))
242 ;; Keep special forms at the beginning of the body.
243 (while (or (stringp (car body-new)) ;docstring.
244 (memq (car-safe (car body-new)) '(interactive declare)))
245 (push (pop body-new) special-forms))
246 (setq body-new
247 `(,@(nreverse special-forms) (let ,letbind . ,body-new)))))
249 (cond
250 ((not (or envector docstring)) ;If no freevars - do nothing.
251 `(function (lambda ,args . ,body-new)))
253 `(internal-make-closure
254 ,args ,envector ,docstring . ,body-new)))))
256 (defun cconv-convert (form env extend)
257 ;; This function actually rewrites the tree.
258 "Return FORM with all its lambdas changed so they are closed.
259 ENV is a lexical environment mapping variables to the expression
260 used to get its value. This is used for variables that are copied into
261 closures, moved into cons cells, ...
262 ENV is a list where each entry takes the shape either:
263 (VAR . (car-safe EXP)): VAR has been moved into the car of a cons-cell, and EXP
264 is an expression that evaluates to this cons-cell.
265 (VAR . (internal-get-closed-var N)): VAR has been copied into the closure
266 environment's Nth slot.
267 (VAR . (apply-partially F ARG1 ARG2 ..)): VAR has been λ-lifted and takes
268 additional arguments ARGs.
269 EXTEND is a list of variables which might need to be accessed even from places
270 where they are shadowed, because some part of ENV causes them to be used at
271 places where they originally did not directly appear."
272 (cl-assert (not (delq nil (mapcar (lambda (mapping)
273 (if (eq (cadr mapping) 'apply-partially)
274 (cconv--set-diff (cdr (cddr mapping))
275 extend)))
276 env))))
278 ;; What's the difference between fvrs and envs?
279 ;; Suppose that we have the code
280 ;; (lambda (..) fvr (let ((fvr 1)) (+ fvr 1)))
281 ;; only the first occurrence of fvr should be replaced by
282 ;; (aref env ...).
283 ;; So initially envs and fvrs are the same thing, but when we descend to
284 ;; the 'let, we delete fvr from fvrs. Why we don't delete fvr from envs?
285 ;; Because in envs the order of variables is important. We use this list
286 ;; to find the number of a specific variable in the environment vector,
287 ;; so we never touch it(unless we enter to the other closure).
288 ;;(if (listp form) (print (car form)) form)
289 (pcase form
290 (`(,(and letsym (or `let* `let)) ,binders . ,body)
292 ; let and let* special forms
293 (let ((binders-new '())
294 (new-env env)
295 (new-extend extend))
297 (dolist (binder binders)
298 (let* ((value nil)
299 (var (if (not (consp binder))
300 (prog1 binder (setq binder (list binder)))
301 (when (cddr binder)
302 (byte-compile-log-warning
303 (format "Malformed `%S' binding: %S" letsym binder)))
304 (setq value (cadr binder))
305 (car binder)))
306 (new-val
307 (cond
308 ;; Check if var is a candidate for lambda lifting.
309 ((and (member (cons binder form) cconv-lambda-candidates)
310 (progn
311 (cl-assert (and (eq (car value) 'function)
312 (eq (car (cadr value)) 'lambda)))
313 (cl-assert (equal (cddr (cadr value))
314 (caar cconv-freevars-alist)))
315 ;; Peek at the freevars to decide whether to λ-lift.
316 (let* ((fvs (cdr (car cconv-freevars-alist)))
317 (fun (cadr value))
318 (funargs (cadr fun))
319 (funcvars (append fvs funargs)))
320 ; lambda lifting condition
321 (and fvs (>= cconv-liftwhen (length funcvars))))))
322 ; Lift.
323 (let* ((fvs (cdr (pop cconv-freevars-alist)))
324 (fun (cadr value))
325 (funargs (cadr fun))
326 (funcvars (append fvs funargs))
327 (funcbody (cddr fun))
328 (funcbody-env ()))
329 (push `(,var . (apply-partially ,var . ,fvs)) new-env)
330 (dolist (fv fvs)
331 (cl-pushnew fv new-extend)
332 (if (and (eq 'car-safe (car-safe (cdr (assq fv env))))
333 (not (memq fv funargs)))
334 (push `(,fv . (car-safe ,fv)) funcbody-env)))
335 `(function (lambda ,funcvars .
336 ,(mapcar (lambda (form)
337 (cconv-convert
338 form funcbody-env nil))
339 funcbody)))))
341 ;; Check if it needs to be turned into a "ref-cell".
342 ((member (cons binder form) cconv-captured+mutated)
343 ;; Declared variable is mutated and captured.
344 (push `(,var . (car-safe ,var)) new-env)
345 `(list ,(cconv-convert value env extend)))
347 ;; Normal default case.
349 (if (assq var new-env) (push `(,var) new-env))
350 (cconv-convert value env extend)))))
352 ;; The piece of code below letbinds free variables of a λ-lifted
353 ;; function if they are redefined in this let, example:
354 ;; (let* ((fun (lambda (x) (+ x y))) (y 1)) (funcall fun 1))
355 ;; Here we can not pass y as parameter because it is redefined.
356 ;; So we add a (closed-y y) declaration. We do that even if the
357 ;; function is not used inside this let(*). The reason why we
358 ;; ignore this case is that we can't "look forward" to see if the
359 ;; function is called there or not. To treat this case better we'd
360 ;; need to traverse the tree one more time to collect this data, and
361 ;; I think that it's not worth it.
362 (when (memq var new-extend)
363 (let ((closedsym
364 (make-symbol (concat "closed-" (symbol-name var)))))
365 (setq new-env
366 (mapcar (lambda (mapping)
367 (if (not (eq (cadr mapping) 'apply-partially))
368 mapping
369 (cl-assert (eq (car mapping) (nth 2 mapping)))
370 `(,(car mapping)
371 apply-partially
372 ,(car mapping)
373 ,@(mapcar (lambda (arg)
374 (if (eq var arg)
375 closedsym arg))
376 (nthcdr 3 mapping)))))
377 new-env))
378 (setq new-extend (remq var new-extend))
379 (push closedsym new-extend)
380 (push `(,closedsym ,var) binders-new)))
382 ;; We push the element after redefined free variables are
383 ;; processed. This is important to avoid the bug when free
384 ;; variable and the function have the same name.
385 (push (list var new-val) binders-new)
387 (when (eq letsym 'let*)
388 (setq env new-env)
389 (setq extend new-extend))
390 )) ; end of dolist over binders
392 `(,letsym ,(nreverse binders-new)
393 . ,(mapcar (lambda (form)
394 (cconv-convert
395 form new-env new-extend))
396 body))))
397 ;end of let let* forms
399 ; first element is lambda expression
400 (`(,(and `(lambda . ,_) fun) . ,args)
401 ;; FIXME: it's silly to create a closure just to call it.
402 ;; Running byte-optimize-form earlier will resolve this.
403 `(funcall
404 ,(cconv-convert `(function ,fun) env extend)
405 ,@(mapcar (lambda (form)
406 (cconv-convert form env extend))
407 args)))
409 (`(cond . ,cond-forms) ; cond special form
410 `(cond . ,(mapcar (lambda (branch)
411 (mapcar (lambda (form)
412 (cconv-convert form env extend))
413 branch))
414 cond-forms)))
416 (`(function (lambda ,args . ,body) . ,_)
417 (let ((docstring (if (eq :documentation (car-safe (car body)))
418 (cconv-convert (cadr (pop body)) env extend))))
419 (cconv--convert-function args body env form docstring)))
421 (`(internal-make-closure . ,_)
422 (byte-compile-report-error
423 "Internal error in compiler: cconv called twice?"))
425 (`(quote . ,_) form)
426 (`(function . ,_) form)
428 ;defconst, defvar
429 (`(,(and sym (or `defconst `defvar)) ,definedsymbol . ,forms)
430 `(,sym ,definedsymbol
431 . ,(mapcar (lambda (form) (cconv-convert form env extend))
432 forms)))
434 ;condition-case
435 ((and `(condition-case ,var ,protected-form . ,handlers)
436 (guard byte-compile--use-old-handlers))
437 (let ((newform (cconv--convert-function
438 () (list protected-form) env form)))
439 `(condition-case :fun-body ,newform
440 ,@(mapcar (lambda (handler)
441 (list (car handler)
442 (cconv--convert-function
443 (list (or var cconv--dummy-var))
444 (cdr handler) env form)))
445 handlers))))
447 ; condition-case with new byte-codes.
448 (`(condition-case ,var ,protected-form . ,handlers)
449 `(condition-case ,var
450 ,(cconv-convert protected-form env extend)
451 ,@(let* ((cm (and var (member (cons (list var) form)
452 cconv-captured+mutated)))
453 (newenv
454 (cond (cm (cons `(,var . (car-save ,var)) env))
455 ((assq var env) (cons `(,var) env))
456 (t env))))
457 (mapcar
458 (lambda (handler)
459 `(,(car handler)
460 ,@(let ((body
461 (mapcar (lambda (form)
462 (cconv-convert form newenv extend))
463 (cdr handler))))
464 (if (not cm) body
465 `((let ((,var (list ,var))) ,@body))))))
466 handlers))))
468 (`(,(and head (or (and `catch (guard byte-compile--use-old-handlers))
469 `unwind-protect))
470 ,form . ,body)
471 `(,head ,(cconv-convert form env extend)
472 :fun-body ,(cconv--convert-function () body env form)))
474 (`(setq . ,forms) ; setq special form
475 (let ((prognlist ()))
476 (while forms
477 (let* ((sym (pop forms))
478 (sym-new (or (cdr (assq sym env)) sym))
479 (value (cconv-convert (pop forms) env extend)))
480 (push (pcase sym-new
481 ((pred symbolp) `(setq ,sym-new ,value))
482 (`(car-safe ,iexp) `(setcar ,iexp ,value))
483 ;; This "should never happen", but for variables which are
484 ;; mutated+captured+unused, we may end up trying to `setq'
485 ;; on a closed-over variable, so just drop the setq.
486 (_ ;; (byte-compile-report-error
487 ;; (format "Internal error in cconv of (setq %s ..)"
488 ;; sym-new))
489 value))
490 prognlist)))
491 (if (cdr prognlist)
492 `(progn . ,(nreverse prognlist))
493 (car prognlist))))
495 (`(,(and (or `funcall `apply) callsym) ,fun . ,args)
496 ;; These are not special forms but we treat them separately for the needs
497 ;; of lambda lifting.
498 (let ((mapping (cdr (assq fun env))))
499 (pcase mapping
500 (`(apply-partially ,_ . ,(and fvs `(,_ . ,_)))
501 (cl-assert (eq (cadr mapping) fun))
502 `(,callsym ,fun
503 ,@(mapcar (lambda (fv)
504 (let ((exp (or (cdr (assq fv env)) fv)))
505 (pcase exp
506 (`(car-safe ,iexp . ,_) iexp)
507 (_ exp))))
508 fvs)
509 ,@(mapcar (lambda (arg)
510 (cconv-convert arg env extend))
511 args)))
512 (_ `(,callsym ,@(mapcar (lambda (arg)
513 (cconv-convert arg env extend))
514 (cons fun args)))))))
516 (`(interactive . ,forms)
517 `(interactive . ,(mapcar (lambda (form)
518 (cconv-convert form nil nil))
519 forms)))
521 (`(declare . ,_) form) ;The args don't contain code.
523 (`(,func . ,forms)
524 ;; First element is function or whatever function-like forms are: or, and,
525 ;; if, catch, progn, prog1, prog2, while, until
526 `(,func . ,(mapcar (lambda (form)
527 (cconv-convert form env extend))
528 forms)))
530 (_ (or (cdr (assq form env)) form))))
532 (unless (fboundp 'byte-compile-not-lexical-var-p)
533 ;; Only used to test the code in non-lexbind Emacs.
534 (defalias 'byte-compile-not-lexical-var-p 'boundp))
535 (defvar byte-compile-lexical-variables)
537 (defun cconv--analyze-use (vardata form varkind)
538 "Analyze the use of a variable.
539 VARDATA should be (BINDER READ MUTATED CAPTURED CALLED).
540 VARKIND is the name of the kind of variable.
541 FORM is the parent form that binds this var."
542 ;; use = `(,binder ,read ,mutated ,captured ,called)
543 (pcase vardata
544 (`(,_ nil nil nil nil) nil)
545 (`((,(and var (guard (eq ?_ (aref (symbol-name var) 0)))) . ,_)
546 ,_ ,_ ,_ ,_)
547 (byte-compile-log-warning
548 (format "%s `%S' not left unused" varkind var))))
549 (pcase vardata
550 (`((,var . ,_) nil ,_ ,_ nil)
551 ;; FIXME: This gives warnings in the wrong order, with imprecise line
552 ;; numbers and without function name info.
553 (unless (or ;; Uninterned symbols typically come from macro-expansion, so
554 ;; it is often non-trivial for the programmer to avoid such
555 ;; unused vars.
556 (not (intern-soft var))
557 (eq ?_ (aref (symbol-name var) 0))
558 ;; As a special exception, ignore "ignore".
559 (eq var 'ignored))
560 (byte-compile-log-warning (format "Unused lexical %s `%S'"
561 varkind var))))
562 ;; If it's unused, there's no point converting it into a cons-cell, even if
563 ;; it's captured and mutated.
564 (`(,binder ,_ t t ,_)
565 (push (cons binder form) cconv-captured+mutated))
566 (`(,(and binder `(,_ (function (lambda . ,_)))) nil nil nil t)
567 (push (cons binder form) cconv-lambda-candidates))))
569 (defun cconv--analyze-function (args body env parentform)
570 (let* ((newvars nil)
571 (freevars (list body))
572 ;; We analyze the body within a new environment where all uses are
573 ;; nil, so we can distinguish uses within that function from uses
574 ;; outside of it.
575 (envcopy
576 (mapcar (lambda (vdata) (list (car vdata) nil nil nil nil)) env))
577 (byte-compile-bound-variables byte-compile-bound-variables)
578 (newenv envcopy))
579 ;; Push it before recursing, so cconv-freevars-alist contains entries in
580 ;; the order they'll be used by closure-convert-rec.
581 (push freevars cconv-freevars-alist)
582 (dolist (arg args)
583 (cond
584 ((byte-compile-not-lexical-var-p arg)
585 (byte-compile-log-warning
586 (format "Lexical argument shadows the dynamic variable %S"
587 arg)))
588 ((eq ?& (aref (symbol-name arg) 0)) nil) ;Ignore &rest, &optional, ...
589 (t (let ((varstruct (list arg nil nil nil nil)))
590 (cl-pushnew arg byte-compile-lexical-variables)
591 (push (cons (list arg) (cdr varstruct)) newvars)
592 (push varstruct newenv)))))
593 (dolist (form body) ;Analyze body forms.
594 (cconv-analyze-form form newenv))
595 ;; Summarize resulting data about arguments.
596 (dolist (vardata newvars)
597 (cconv--analyze-use vardata parentform "argument"))
598 ;; Transfer uses collected in `envcopy' (via `newenv') back to `env';
599 ;; and compute free variables.
600 (while env
601 (cl-assert (and envcopy (eq (caar env) (caar envcopy))))
602 (let ((free nil)
603 (x (cdr (car env)))
604 (y (cdr (car envcopy))))
605 (while x
606 (when (car y) (setcar x t) (setq free t))
607 (setq x (cdr x) y (cdr y)))
608 (when free
609 (push (caar env) (cdr freevars))
610 (setf (nth 3 (car env)) t))
611 (setq env (cdr env) envcopy (cdr envcopy))))))
613 (defun cconv-analyze-form (form env)
614 "Find mutated variables and variables captured by closure.
615 Analyze lambdas if they are suitable for lambda lifting.
616 - FORM is a piece of Elisp code after macroexpansion.
617 - ENV is an alist mapping each enclosing lexical variable to its info.
618 I.e. each element has the form (VAR . (READ MUTATED CAPTURED CALLED)).
619 This function does not return anything but instead fills the
620 `cconv-captured+mutated' and `cconv-lambda-candidates' variables
621 and updates the data stored in ENV."
622 (pcase form
623 ; let special form
624 (`(,(and (or `let* `let) letsym) ,binders . ,body-forms)
626 (let ((orig-env env)
627 (newvars nil)
628 (var nil)
629 (byte-compile-bound-variables byte-compile-bound-variables)
630 (value nil))
631 (dolist (binder binders)
632 (if (not (consp binder))
633 (progn
634 (setq var binder) ; treat the form (let (x) ...) well
635 (setq binder (list binder))
636 (setq value nil))
637 (setq var (car binder))
638 (setq value (cadr binder))
640 (cconv-analyze-form value (if (eq letsym 'let*) env orig-env)))
642 (unless (byte-compile-not-lexical-var-p var)
643 (cl-pushnew var byte-compile-lexical-variables)
644 (let ((varstruct (list var nil nil nil nil)))
645 (push (cons binder (cdr varstruct)) newvars)
646 (push varstruct env))))
648 (dolist (form body-forms) ; Analyze body forms.
649 (cconv-analyze-form form env))
651 (dolist (vardata newvars)
652 (cconv--analyze-use vardata form "variable"))))
654 (`(function (lambda ,vrs . ,body-forms))
655 (when (eq :documentation (car-safe (car body-forms)))
656 (cconv-analyze-form (cadr (pop body-forms)) env))
657 (cconv--analyze-function vrs body-forms env form))
659 (`(setq . ,forms)
660 ;; If a local variable (member of env) is modified by setq then
661 ;; it is a mutated variable.
662 (while forms
663 (let ((v (assq (car forms) env))) ; v = non nil if visible
664 (when v (setf (nth 2 v) t)))
665 (cconv-analyze-form (cadr forms) env)
666 (setq forms (cddr forms))))
668 (`((lambda . ,_) . ,_) ; First element is lambda expression.
669 (byte-compile-log-warning
670 (format "Use of deprecated ((lambda %s ...) ...) form" (nth 1 (car form)))
671 t :warning)
672 (dolist (exp `((function ,(car form)) . ,(cdr form)))
673 (cconv-analyze-form exp env)))
675 (`(cond . ,cond-forms) ; cond special form
676 (dolist (forms cond-forms)
677 (dolist (form forms) (cconv-analyze-form form env))))
679 ;; ((and `(quote ,v . ,_) (guard (assq v env)))
680 ;; (byte-compile-log-warning
681 ;; (format "Possible confusion variable/symbol for `%S'" v)))
683 (`(quote . ,_) nil) ; quote form
684 (`(function . ,_) nil) ; same as quote
686 ((and `(condition-case ,var ,protected-form . ,handlers)
687 (guard byte-compile--use-old-handlers))
688 ;; FIXME: The bytecode for condition-case forces us to wrap the
689 ;; form and handlers in closures.
690 (cconv--analyze-function () (list protected-form) env form)
691 (dolist (handler handlers)
692 (cconv--analyze-function (if var (list var)) (cdr handler)
693 env form)))
695 (`(condition-case ,var ,protected-form . ,handlers)
696 (cconv-analyze-form protected-form env)
697 (when (and var (symbolp var) (byte-compile-not-lexical-var-p var))
698 (byte-compile-log-warning
699 (format "Lexical variable shadows the dynamic variable %S" var)))
700 (let* ((varstruct (list var nil nil nil nil)))
701 (if var (push varstruct env))
702 (dolist (handler handlers)
703 (dolist (form (cdr handler))
704 (cconv-analyze-form form env)))
705 (if var (cconv--analyze-use (cons (list var) (cdr varstruct))
706 form "variable"))))
708 ;; FIXME: The bytecode for unwind-protect forces us to wrap the unwind.
709 (`(,(or (and `catch (guard byte-compile--use-old-handlers))
710 `unwind-protect)
711 ,form . ,body)
712 (cconv-analyze-form form env)
713 (cconv--analyze-function () body env form))
715 (`(defvar ,var) (push var byte-compile-bound-variables))
716 (`(,(or `defconst `defvar) ,var ,value . ,_)
717 (push var byte-compile-bound-variables)
718 (cconv-analyze-form value env))
720 (`(,(or `funcall `apply) ,fun . ,args)
721 ;; Here we ignore fun because funcall and apply are the only two
722 ;; functions where we can pass a candidate for lambda lifting as
723 ;; argument. So, if we see fun elsewhere, we'll delete it from
724 ;; lambda candidate list.
725 (let ((fdata (and (symbolp fun) (assq fun env))))
726 (if fdata
727 (setf (nth 4 fdata) t)
728 (cconv-analyze-form fun env)))
729 (dolist (form args) (cconv-analyze-form form env)))
731 (`(interactive . ,forms)
732 ;; These appear within the function body but they don't have access
733 ;; to the function's arguments.
734 ;; We could extend this to allow interactive specs to refer to
735 ;; variables in the function's enclosing environment, but it doesn't
736 ;; seem worth the trouble.
737 (dolist (form forms) (cconv-analyze-form form nil)))
739 ;; `declare' should now be macro-expanded away (and if they're not, we're
740 ;; in trouble because they *can* contain code nowadays).
741 ;; (`(declare . ,_) nil) ;The args don't contain code.
743 (`(,_ . ,body-forms) ; First element is a function or whatever.
744 (dolist (form body-forms) (cconv-analyze-form form env)))
746 ((pred symbolp)
747 (let ((dv (assq form env))) ; dv = declared and visible
748 (when dv
749 (setf (nth 1 dv) t))))))
750 (define-obsolete-function-alias 'cconv-analyse-form 'cconv-analyze-form "25.1")
752 (provide 'cconv)
753 ;;; cconv.el ends here