1 ;;;; Type checking of higher order functions.
3 ;;;; This software is part of the SBCL system. See the README file for
6 ;;;; This software is derived from the CMU CL system, which was
7 ;;;; written at Carnegie Mellon University and released into the
8 ;;;; public domain. The software is in the public domain and is
9 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
10 ;;;; files for more information.
14 (defun assert-function-designator (caller lvars lvar annotation policy
)
15 (destructuring-bind (args &optional results
&rest options
) annotation
16 (declare (ignore options
))
17 (multiple-value-bind (arg-specs result-specs deps
)
18 (callable-dependant-lvars caller lvars args results
)
19 (let* ((type (make-fun-type
21 (make-list (+ (length arg-specs
)
22 ;; Count ordinary types without annotations
23 (count-if #'atom args
))
24 :initial-element
*universal-type
*)
27 (annotation (make-lvar-function-designator-annotation
30 :result-specs result-specs
33 (when (add-annotation lvar annotation
)
34 (assert-lvar-type lvar
35 (specifier-type 'function-designator
)
38 (defun fun-type-positional-count (fun-type)
39 (+ (length (fun-type-required fun-type
))
40 (length (fun-type-optional fun-type
))))
42 (defun callable-dependant-lvars (caller lvars args results
)
43 (let ((fun-type (global-ftype caller
)))
45 (let ((arg-position -
1)
46 (optional-args (nthcdr (fun-type-positional-count fun-type
) lvars
)))
47 (labels ((record-lvar (lvar)
50 (handle-keys (options)
51 (loop for
(key value
*) on options by
#'cddr
52 for value
= (if (or (eq key
:key
)
55 (let ((value-lvar (getf optional-args
(car value
*))))
57 (let ((if (getf optional-args
(second value
*))))
59 (list (record-lvar value-lvar
)
60 (record-lvar if
) (third value
*)))
61 ((null (third value
*))
62 (record-lvar value-lvar
))))))
63 (let ((lvar (getf optional-args value
*)))
75 (list* (record-lvar (nth (cadr arg
) lvars
))
76 (handle-keys (cddr arg
)))))
78 (loop for lvar in optional-args
80 (list* (record-lvar lvar
)
81 (handle-keys (cdr arg
)))))
84 (list* 'or
(process-args (cdr arg
)))))))
90 (values (process-args args
)
92 (car (process-arg results
)))
95 (defun map-key-lvars (function args type
)
96 (when (fun-type-keyp type
)
97 (let ((key-args (nthcdr (fun-type-positional-count type
)
99 (key-types (fun-type-keywords type
))
102 (loop for
(key lvar
) on key-args by
#'cddr
103 for key-value
= (and (constant-lvar-p key
)
105 for key-info
= (find key-value key-types
:key
#'key-info-name
)
107 (unless (memq key-value seen
)
108 (funcall function key-value lvar
)
109 (push key-value seen
)))
113 (push key unknown
))))
116 ;;; Turn constant LVARs in keyword arg positions to constants so that
117 ;;; they can be passed to FUN-INFO-CALLABLE-CHECK.
118 (defun resolve-key-args (args type
)
119 (if (fun-type-keyp type
)
120 (let ((non-key (fun-type-positional-count type
)))
121 (if (> (length args
) non-key
)
123 (unknown (map-key-lvars (lambda (key value
)
124 (push key key-arguments
)
125 (push value key-arguments
))
128 (values (nconc (subseq args
0 non-key
)
129 (nreverse key-arguments
))
134 ;;; The function should accept
135 ;;; (lvar args results &key (unknown-keys boolean) (no-function-conversion boolean) (arg-lvars list-of-lvars))
136 (defun map-callable-arguments (function combination
)
137 (let* ((combination-name (lvar-fun-name (combination-fun combination
) t
))
138 (type (global-ftype combination-name
))
139 (info (info :function
:info combination-name
))
140 (annotation (fun-info-annotation info
)))
142 (multiple-value-bind (arg-lvars unknown
) (resolve-key-args (combination-args combination
) type
)
143 (flet ((call (lvar annotation
)
144 (destructuring-bind (args &optional results . options
) annotation
146 (loop for arg in args
147 if
(typep arg
'(cons (eql rest-args
)))
148 nconc
(loop repeat
(- (length (combination-args combination
))
149 (fun-type-positional-count type
))
155 :unknown-keys unknown
157 (loop for
(n kind . annotation
) in
(fun-type-annotation-positional annotation
)
158 when
(memq kind
'(function function-designator
))
160 (let ((arg (nth n arg-lvars
)))
162 (call arg annotation
))))
163 (loop with keys
= (nthcdr (fun-type-positional-count type
)
165 for
(key (kind . annotation
)) on
(fun-type-annotation-key annotation
) by
#'cddr
166 when
(memq kind
'(function function-designator
))
168 (let ((lvar (getf keys key
)))
170 (call lvar annotation
)))))))))
172 ;; Handle #'function, 'function and (lambda (x y))
173 (defun node-fun-type (node &optional defined-here asserted-type
)
175 (lvar-type (single-value-type (node-derived-type use
)))
176 (leaf (if (ref-p use
)
178 (return-from node-fun-type
180 (node-source-form use
)))))
182 (defined-type (and (global-var-p leaf
)
183 (case (leaf-where-from leaf
)
187 (cond ((or defined-here
189 (and (defined-fun-p leaf
)
190 (eq (defined-fun-inlinep leaf
) 'notinline
))
191 (fun-lexically-notinline-p (leaf-%source-name leaf
)
192 (node-lexenv (lvar-dest (node-lvar node
)))))
196 (global-ftype (leaf-%source-name leaf
)))))
197 ((:defined-here
:declared-verify
)
198 (cond ((or (and (defined-fun-p leaf
)
199 (eq (defined-fun-inlinep leaf
) 'notinline
))
200 (fun-lexically-notinline-p (leaf-%source-name leaf
)
201 (node-lexenv (lvar-dest (node-lvar node
)))))
204 (global-ftype (leaf-%source-name leaf
)))))
206 (global-var-defined-type leaf
)))))
207 (entry-fun (if (and (functional-p leaf
)
208 (functional-kind-eq leaf external
))
209 (functional-entry-fun leaf
)
211 (lvar-type (cond ((and defined-type
212 (neq defined-type
*universal-type
*))
214 ((and (functional-p entry-fun
)
215 (fun-type-p (functional-type entry-fun
)))
216 (functional-type entry-fun
))
217 ((and (not (fun-type-p lvar-type
))
219 (functional-kind-eq entry-fun nil
)
220 (lambda-tail-set entry-fun
))
221 (make-fun-type :wild-args t
223 (tail-set-type (lambda-tail-set entry-fun
))))
225 (not (constant-p leaf
)))
227 ;; Don't trust FUNCTION type declarations,
228 ;; they perform no runtime assertions.
229 (specifier-type 'function
))
233 (fun-name (cond ((or (fun-type-p lvar-type
)
236 (cond ((constant-p leaf
)
237 (let ((value (constant-value leaf
)))
244 ((and (lambda-p leaf
)
245 (functional-kind-eq leaf external
))
246 (leaf-debug-name (lambda-entry-fun leaf
)))
248 (leaf-debug-name leaf
))))
250 (constant-value leaf
))
252 (return-from node-fun-type lvar-type
))))
253 (type (cond ((fun-type-p lvar-type
)
256 (if (or (fun-lexically-notinline-p fun-name
257 (node-lexenv (node-dest node
)))
258 (and (or asserted-type
260 (neq (info :function
:where-from fun-name
) :declared
)))
262 (global-ftype fun-name
)))
264 (let ((info (functional-info leaf
)))
266 (specifier-type (entry-info-type info
))
270 (values type fun-name leaf asserted
)))
272 (defun lvar-fun-type (lvar &optional defined-here asserted-type
)
273 (let* ((use (principal-lvar-use lvar
))
274 (lvar-type (lvar-type lvar
)))
276 (multiple-value-bind (type fun-name leaf asserted
) (node-fun-type use defined-here asserted-type
)
277 (let ((int (if (fun-type-p lvar-type
)
278 ;; save the cast type
279 (type-intersection type lvar-type
)
281 (values (if (neq int
*empty-type
*)
284 fun-name leaf asserted
)))
288 (node-source-form use
))
292 (defun callable-argument-lossage-kind (fun-name leaf soft hard
)
294 (and (not (memq (leaf-where-from leaf
) '(:defined-here
:declared-verify
)))
295 (not (and (functional-p leaf
)
297 (functional-kind-eq leaf toplevel-xep
))))
299 (not (info :function
:info fun-name
)))))
303 (defun validate-test-and-test-not (combination)
304 (let* ((combination-name (lvar-fun-name (combination-fun combination
) t
))
305 (info (info :function
:info combination-name
)))
307 (ir1-attributep (fun-info-attributes info
) call
))
310 (null-type (specifier-type 'null
)))
311 (map-key-lvars (lambda (key value
)
312 (when (and (not test
)
315 (when (and (not test-not
)
317 (setf test-not value
)))
318 (combination-args combination
)
319 (global-ftype combination-name
))
322 (eq (type-intersection null-type
(lvar-type test
))
324 (eq (type-intersection null-type
(lvar-type test-not
))
326 (note-lossage "~s: can't specify both :TEST and :TEST-NOT"
327 combination-name
))))))
329 (defun function-designator-lvar-types (annotation)
330 (labels ((arg-type (arg)
334 (sequence-element-type (type)
335 (cond ((array-type-p type
)
336 (let ((elt-type (array-type-element-type type
)))
337 (if (eq elt-type
*wild-type
*)
340 ((csubtypep type
(specifier-type 'string
))
341 (specifier-type 'character
))
344 (let ((deps (lvar-function-designator-annotation-deps annotation
))
345 (arg-specs (lvar-function-designator-annotation-arg-specs annotation
))
346 (result-specs (lvar-function-designator-annotation-result-specs annotation
)))
347 (labels ((%process-arg
(spec)
348 (destructuring-bind (nth-arg . options
) spec
349 (let* ((arg (nth nth-arg deps
))
350 (value-nth (getf options
:value
))
351 (key-nth (getf options
:key
))
352 (value (and value-nth
353 (nth (if (consp value-nth
)
357 (key (and key-nth
(nth key-nth deps
)))
358 (key-return-type (cond ((not key
)
361 (multiple-value-bind (type name
) (lvar-fun-type key
)
362 (cond ((eq name
'identity
)
365 (single-value-type (fun-type-returns type
)))
370 (type (cond (key-return-type)
371 ((getf options
:sequence
)
372 (sequence-element-type (arg-type arg
)))
373 ((getf options
:sequence-type
)
374 (or (let* ((value (cond ((constant-p arg
)
375 (constant-value arg
))
377 (constant-lvar-p arg
))
380 (careful-specifier-type value
))))
382 (sequence-element-type type
)))
387 (if (consp value-nth
)
388 (let* ((option (nth (second value-nth
) deps
))
389 (option-p (third value-nth
))
390 (false (or (not option
)
391 (csubtypep (lvar-type option
) (specifier-type 'null
))))
393 (csubtypep (lvar-type option
) (specifier-type '(not null
)))))
394 (unknown (not (or true false
))))
396 (type-union (lvar-type value
)
400 ((and false
(not option-p
))
410 (if (eq (car spec
) 'or
)
411 (cons 'or
(mapcar #'%process-arg
(cdr spec
)))
412 (%process-arg spec
))))
415 (mapcar #'process-arg arg-specs
)
417 (lvar-function-designator-annotation-type annotation
)))
419 (process-arg result-specs
)
420 (fun-type-returns (lvar-function-designator-annotation-type annotation
))))))))
422 ;;; Return MIN, MAX, whether it contaions &optional/&key/&rest
423 (defun fun-type-arg-limits (type)
424 (if (fun-type-wild-args type
)
426 (let* ((min (length (fun-type-required type
)))
427 (max (and (not (or (fun-type-rest type
)
428 (fun-type-keyp type
)))
430 (length (fun-type-optional type
))))))
431 (values min max
(or (fun-type-rest type
)
433 (fun-type-optional type
))))))
435 ;;; Should have enough types for N
436 (defun fun-type-n-arg-types (n type
)
439 (loop for type in types
440 do
(push type result
)
441 while
(plusp (decf n
)))))
442 (pick (fun-type-required type
))
443 (pick (fun-type-optional type
))
444 (loop with rest
= (or (fun-type-rest type
)
447 do
(push rest result
)))
450 (defun report-arg-count-mismatch (fun caller type arg-count
452 &optional lossage-fun name
)
453 (flet ((lose (format-control &rest format-args
)
455 (apply lossage-fun format-control format-args
)
456 (warn condition-type
:format-control format-control
457 :format-arguments format-args
))
461 (nth-value 1 (lvar-fun-type fun
))))
464 (loop for annotation in
(lvar-annotations fun
)
465 when
(typep annotation
'lvar-function-designator-annotation
)
466 do
(setf *compiler-error-context
* annotation
)
467 (return (lvar-function-designator-annotation-caller annotation
))))))
468 (multiple-value-bind (min max optional
) (fun-type-arg-limits type
)
471 ((and (not min
) (not max
))
474 (when (/= arg-count min
)
476 "The function ~S is called~@[ by ~S~] with ~R argument~:P, but wants exactly ~R."
481 "The function ~S is called~@[ by ~S~] with ~R argument~:P, but wants at least ~R."
488 "The function ~S called~@[ by ~S~] with ~R argument~:P, but wants at most ~R."
491 (let ((positional (fun-type-positional-count type
)))
492 (when (and (fun-type-keyp type
)
493 (> arg-count positional
)
494 (oddp (- arg-count positional
)))
496 "The function ~s is called with odd number of keyword arguments."
499 (defun disable-arg-count-checking (leaf type arg-count
)
500 (when (lambda-p leaf
)
502 ;; TODO: what if all destinations can disable arg count checking.
503 (map-leaf-refs (lambda (dest)
504 (declare (ignore dest
))
505 (when (shiftf once t
)
506 (return-from disable-arg-count-checking
)))
508 (multiple-value-bind (min max
) (fun-type-arg-limits type
)
511 (<= min arg-count max
)
513 (setf (lambda-lexenv leaf
)
514 (make-lexenv :default
(lambda-lexenv leaf
)
515 :policy
(augment-policy verify-arg-count
0
516 (lexenv-policy (lambda-lexenv leaf
)))))))))
518 ;;; This can provide better errors and better handle OR types than a
519 ;;; simple type intersection.
520 (defun check-function-designator-lvar (lvar annotation
)
523 (multiple-value-bind (type name leaf
) (node-fun-type node
)
526 (valid-function-name-p name
)
527 (memq (info :function
:kind name
) '(:macro
:special-form
)))
528 (compiler-warn "~(~a~) ~s where a function is expected"
529 (info :function
:kind name
) name
))
531 ;; If the destination is a combination-fun that means the function
532 ;; is called here and not passed somewhere else, there's no longer a
533 ;; need to check the function type, the arguments to the call will
535 (unless (let* ((dest (lvar-dest lvar
)))
536 (and (basic-combination-p dest
)
537 (eq (basic-combination-fun dest
) lvar
)))
538 (multiple-value-bind (args results
)
539 (function-designator-lvar-types annotation
)
540 (let* ((condition (if (eq node
(principal-lvar-use lvar
))
541 (callable-argument-lossage-kind name
543 'simple-style-warning
545 'simple-style-warning
))
546 (type-condition (case condition
547 (simple-style-warning
551 (caller (lvar-function-designator-annotation-caller annotation
))
552 (arg-count (length args
)))
553 (or (report-arg-count-mismatch lvar caller
559 (let ((param-types (fun-type-n-arg-types arg-count type
)))
560 (unless (and (eq caller
'reduce
)
562 (disable-arg-count-checking leaf type arg-count
))
564 ;; Need to check each OR seperately, a UNION could
565 ;; intersect with the function parameters
566 (labels ((hide-ors (current-or or-part
)
567 (loop for spec in args
568 collect
(cond ((eq spec current-or
)
570 ((typep spec
'(cons (eql or
)))
571 (sb-kernel::%type-union
(cdr spec
)))
574 (check (arg param
&optional
576 (when (eq (type-intersection param arg
) *empty-type
*)
579 "The function ~S is called by ~S with ~S but it accepts ~S."
584 (mapcar #'type-specifier
(hide-ors current-spec arg
))
585 (mapcar #'type-specifier param-types
)))
587 (loop for arg-type in args
588 for param-type in param-types
589 if
(typep arg-type
'(cons (eql or
)))
590 do
(loop for type in
(cdr arg-type
)
591 do
(check type param-type arg-type
))
592 else do
(check arg-type param-type
)))))
593 (let ((returns (single-value-type (fun-type-returns type
))))
594 (when (and (neq returns
*wild-type
*)
595 (neq returns
*empty-type
*)
596 (neq results
*wild-type
*)
597 (eq (type-intersection returns results
) *empty-type
*))
600 "The function ~S called by ~S returns ~S but ~S is expected"
605 (type-specifier returns
)
606 (type-specifier results
)))))))))))))
610 (defun check-function-lvar (lvar annotation
)
611 (let ((atype (lvar-function-annotation-type annotation
)))
612 (multiple-value-bind (type name leaf
) (lvar-fun-type lvar
)
613 (when (fun-type-p type
)
614 (let ((condition (callable-argument-lossage-kind name
618 (if (eq (lvar-function-annotation-context annotation
) :mv-call
)
619 (let* ((*compiler-error-context
* annotation
)
620 (max-accepted (nth-value 1 (fun-type-nargs (lvar-fun-type lvar
))))
621 (min-args (fun-type-nargs atype
)))
622 (when (and max-accepted
623 (> min-args max-accepted
))
626 "~@<MULTIPLE-VALUE-CALL calls ~a with with at least ~R ~
627 values when it expects at most ~R.~@:>"
628 :format-arguments
(list name min-args
630 (let ((int (type-intersection type atype
)))
631 (when (or (memq *empty-type
* (fun-type-required int
))
632 (and (eq (fun-type-returns int
) *empty-type
*)
633 (neq (fun-type-returns type
) *empty-type
*)
634 (not (and (eq (fun-type-returns atype
) *empty-type
*)
635 (eq (fun-type-returns type
) *wild-type
*)))))
636 (%compile-time-type-error-warn annotation
637 (type-specifier atype
)
638 (type-specifier type
)
640 :condition condition
)))))))))