| blob | e82181b4e0cec79c1eb847a15fbda4de6b1cc92d |
1 ;;;; This file contains code which knows about both the type
2 ;;;; representation and the compiler IR1 representation. This stuff is
3 ;;;; used for doing type checking.
5 ;;;; This software is part of the SBCL system. See the README file for
6 ;;;; more information.
7 ;;;;
8 ;;;; This software is derived from the CMU CL system, which was
9 ;;;; written at Carnegie Mellon University and released into the
10 ;;;; public domain. The software is in the public domain and is
11 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
12 ;;;; files for more information.
14 ;;;; FIXME: This is a poor name for this file, since CTYPE is the name
15 ;;;; of the type used internally to represent Lisp types. It'd
16 ;;;; probably be good to rename this file to "call-type.lisp" or
17 ;;;; "ir1-type.lisp" or something.
23 ;;; These are the functions that are to be called when a problem is
24 ;;; detected. They are passed format arguments. If null, we don't do
25 ;;; anything. The LOSSAGE function is called when something is
26 ;;; definitely incorrect. The UNWINNAGE function is called when it is
27 ;;; somehow impossible to tell whether the call is correct. (Thus,
28 ;;; they should correspond fairly closely to the FAILURE-P and WARNINGS-P
29 ;;; return values of CL:COMPILE and CL:COMPILE-FILE. However, see the
30 ;;; KLUDGE note below for *LOSSAGE-DETECTED*.)
34 ;;; the function that we use for type checking. The derived type is
35 ;;; its first argument and the type we are testing against is its
36 ;;; second argument. The function should return values like CSUBTYPEP.
38 ;;; FIXME: Why is this a variable? Explain.
40 ;;; *LOSSAGE-DETECTED* is set when a "definite incompatibility" is
41 ;;; detected. *UNWINNAGE-DETECTED* is set when we can't tell whether the
42 ;;; call is compatible or not. Thus, they should correspond very closely
43 ;;; to the FAILURE-P and WARNINGS-P return values of CL:COMPILE and
44 ;;; CL:COMPILE-FILE.) However...
45 ;;;
46 ;;; KLUDGE: Common Lisp is a dynamic language, even if CMU CL was not.
47 ;;; As far as I can see, none of the "definite incompatibilities"
48 ;;; detected in this file are actually definite under the ANSI spec.
49 ;;; They would be incompatibilites if the use were within the same
50 ;;; compilation unit as the contradictory definition (as per the spec
51 ;;; section "3.2.2.3 Semantic Constraints") but the old Python code
52 ;;; doesn't keep track of whether that's the case. So until/unless we
53 ;;; upgrade the code to keep track of that, we have to handle all
54 ;;; these as STYLE-WARNINGs. -- WHN 2001-02-10
59 ;;; Signal a warning if appropriate and set *FOO-DETECTED*.
72 \f
73 ;;;; stuff for checking a call against a function type
74 ;;;;
75 ;;;; FIXME: This is stuff to look at when I get around to fixing
76 ;;;; function type inference and declarations.
78 ;;; A dummy version of SUBTYPEP useful when we want a functional like
79 ;;; SUBTYPEP that always returns true.
84 ;;; Determine whether a use of a function is consistent with its type.
85 ;;; These values are returned:
86 ;;; T, T: the call is definitely valid.
87 ;;; NIL, T: the call is definitely invalid.
88 ;;; NIL, NIL: unable to determine whether the call is valid.
89 ;;;
90 ;;; The ARGUMENT-TEST function is used to determine whether an
91 ;;; argument type matches the type we are checking against. Similarly,
92 ;;; the RESULT-TEST is used to determine whether the result type
93 ;;; matches the specified result.
94 ;;;
95 ;;; Unlike the argument test, the result test may be called on values
96 ;;; or function types. NODE-DERIVED-TYPE is intersected with the
97 ;;; trusted asserted type.
98 ;;;
99 ;;; The error and warning functions are functions that are called to
100 ;;; explain the result. We bind *COMPILER-ERROR-CONTEXT* to the
101 ;;; combination node so that COMPILER-WARNING and related functions
102 ;;; will do the right thing if they are supplied.
109 ;; FIXME: Could TYPE here actually be something like
110 ;; (AND GENERIC-FUNCTION (FUNCTION (T) T))? How
111 ;; horrible... -- CSR, 2003-05-03
128 and i from 1
133 "The function was called with ~R argument~:P, but wants exactly ~R."
134 nargs min-args)
138 "The function was called with ~R argument~:P, but wants at least ~R."
139 nargs min-args))
144 "The function was called with ~R argument~:P, but wants at most ~R."
145 nargs max-args))
164 dtype))
175 and i from 1
181 info
186 ;; One more check for structure constructors:
194 ;;; Turn constant LVARs in keyword arg positions to constants so that
195 ;;; they can be passed to FUN-INFO-CALLABLE-CHECK.
200 key-arguments)
215 args))
217 ;;; Return MIN, MAX, whether it contaions &optional/&key/&rest
225 (+ min
237 nil
238 t))
242 t))))
246 ;; Handle #'function, 'function and (lambda (x y))
266 lvar-type)
270 leaf)))
276 #'compiler-style-warn
285 "The function ~S is called by ~S with ~R argument~:P, but wants exactly ~R."
286 fun-name
288 arg-count min)))
291 "The function ~S is called by ~S with ~R argument~:P, but wants at least ~R."
292 fun-name
294 arg-count min))
298 "The function ~S called by ~S with ~R argument~:P, but wants at most ~R."
299 fun-name
301 arg-count max)))))))
316 ;; Ignore &AUX vars - it's not the caller's fault if wrong.
318 ;; is this right, or should it be EQ
319 ;; like in DETERMINE-UNSAFE-SLOTS ?
326 lambda-list-element arg)))
328 ;; Deduce the keyword (if any) that initializes this slot.
337 lambda-list-element arg))))
342 ;; Return T if value-form definitely does not satisfy
343 ;; the type-check for DSD. Return NIL if we can't decide.
347 ;; Find uses of nil-returning functions as defaults,
348 ;; like ERROR and MISSING-ARG.
352 ;; Don't examine :function :type of macros!
361 ;;; Check that the derived type of the LVAR is compatible with TYPE. N
362 ;;; is the arg number, for error message purposes. We return true if
363 ;;; arg is definitely o.k. If the type is a magic CONSTANT-TYPE, then
364 ;;; we check for the argument being a constant value of the specified
365 ;;; type. If there is a manifest type error (DERIVED-TYPE = NIL), then
366 ;;; we flame about the asserted type even when our type is satisfied
367 ;;; under the test.
377 nil)
381 nil)
384 nil)
388 nil)
395 constant ~S:~% ~S"
397 nil)
401 nil)
404 ;;; Check that each of the type of each supplied argument intersects
405 ;;; with the type specified for that argument. If we can't tell, then
406 ;;; we can complain about the absence of manifest winnage.
421 ;;; Check that the &KEY args are of the correct type. Each key should
422 ;;; be known and the corresponding argument should be of the correct
423 ;;; type. If the key isn't a constant, then we can't tell, so we can
424 ;;; complain about absence of manifest winnage.
438 a constant, weakening keyword argument ~
440 ;; An unknown key may turn out to be :ALLOW-OTHER-KEYS at runtime,
441 ;; so we cannot signal full warnings for keys that look bad.
452 :yes
471 ;;; Construct a function type from a definition.
472 ;;;
473 ;;; Due to the lack of a (LIST X) type specifier, we can't reconstruct
474 ;;; the &REST type.
492 (:keyword
503 :rest rest
510 \f
511 ;;;; approximate function types
512 ;;;;
513 ;;;; FIXME: This is stuff to look at when I get around to fixing function
514 ;;;; type inference and declarations.
515 ;;;;
516 ;;;; Approximate function types provide a condensed representation of all the
517 ;;;; different ways that a function has been used. If we have no declared or
518 ;;;; defined type for a function, then we build an approximate function type by
519 ;;;; examining each use of the function. When we encounter a definition or
520 ;;;; proclamation, we can check the actual type for compatibity with the
521 ;;;; previous uses.
524 ;; the smallest and largest numbers of arguments that this function
525 ;; has been called with.
530 ;; a list of lists of the all the types that have been used in each
531 ;; argument position
533 ;; A list of APPROXIMATE-KEY-INFO structures describing all the
534 ;; things that looked like &KEY arguments. There are distinct
535 ;; structures describing each argument position in which the keyword
536 ;; appeared.
540 ;; The keyword name of this argument. Although keyword names don't
541 ;; have to be keywords, we only match on keywords when figuring an
542 ;; approximate type.
544 ;; The position at which this keyword appeared. 0 if it appeared as the
545 ;; first argument, etc.
548 ;; a list of all the argument types that have been used with this keyword
550 ;; true if this keyword has appeared only in calls with an obvious
551 ;; :ALLOW-OTHER-KEYS
554 ;;; Return an APPROXIMATE-FUN-TYPE representing the context of
555 ;;; CALL. If TYPE is supplied and not null, then we merge the
556 ;;; information into the information already accumulated in TYPE.
559 approximate-fun-type)
560 note-fun-use))
569 args)))
583 arg))))
603 pos)))
614 :name name
615 :position pos
616 :allowp allowp
618 type))
620 ;;; This is similar to VALID-FUN-USE, but checks an
621 ;;; APPROXIMATE-FUN-TYPE against a real function type.
625 valid-approximate-type))
647 "~:@<The function was previously called with ~R argument~:P, ~
648 but wants at least ~R.~:>"
649 call-min min-args)))
655 "~:@<The function was previously called with ~R argument~:P, ~
656 but wants at most ~R.~:>"
657 call-max max-args))
660 "~:@<The function was previously called with an odd number of ~
667 rest)
673 ;;; Check that each of the types used at each arg position is
674 ;;; compatible with the actual type.
677 check-approximate-fixed-and-rest))
688 ;;; Check that each of the call-types is compatible with DECL-TYPE,
689 ;;; complaining if not or if we can't tell.
691 check-approximate-arg-type))
699 argument type ~S is a ~S"
700 context
701 args
712 ;;; Check the types of each manifest keyword that appears in a keyword
713 ;;; argument position. Check the validity of all keys that appeared in
714 ;;; valid keyword positions.
715 ;;;
716 ;;; ### We could check the APPROXIMATE-FUN-TYPE-TYPES to make
717 ;;; sure that all arguments in keyword positions were manifest
718 ;;; keywords.
743 name)))))))
744 \f
745 ;;;; ASSERT-DEFINITION-TYPE
747 ;;; Intersect LAMBDA's var types with TYPES, giving a warning if there
748 ;;; is a mismatch. If all intersections are non-null, we return lists
749 ;;; of the variables and intersections, otherwise we return NIL, NIL.
759 "Definition's declared type for variable ~A:~% ~S~@
760 conflicts with this type from ~A:~% ~S"
766 vars types)
769 ;;; Check that the optional-dispatch OD conforms to TYPE. We return
770 ;;; the values of TRY-TYPE-INTERSECTIONS if there are no syntax
771 ;;; problems, otherwise NIL, NIL.
772 ;;;
773 ;;; Note that the variables in the returned list are the actual
774 ;;; original variables (extracted from the optional dispatch arglist),
775 ;;; rather than the variables that are arguments to the main entry.
776 ;;; This difference is significant only for &KEY args with hairy
777 ;;; defaults. Returning the actual vars allows us to use the right
778 ;;; variable name in warnings.
779 ;;;
780 ;;; A slightly subtle point: with keywords and optionals, the type in
781 ;;; the function type is only an assertion on calls --- it doesn't
782 ;;; constrain the type of default values. So we have to union in the
783 ;;; type of the default. With optionals, we can't do any assertion
784 ;;; unless the default is constant.
785 ;;;
786 ;;; With keywords, we exploit our knowledge about how hairy keyword
787 ;;; defaulting is done when computing the type assertion to put on the
788 ;;; main-entry argument. In the case of hairy keywords, the default
789 ;;; has been clobbered with NIL, which is the value of the main-entry
790 ;;; arg in the unsupplied case, whatever the actual default value is.
791 ;;; So we can just assume the default is constant, effectively
792 ;;; unioning in NULL, and not totally blow off doing any type
793 ;;; assertion.
811 "The definition has ~R ~A arg~P, but ~A has ~R."
812 num-definition arg-kind num-definition where num-type)))
816 "The definition ~:[doesn't have~;has~] ~A, but ~
817 ~A ~:[doesn't~;does~]."
818 in-od-p section where in-type-p))))
820 ;; When TYPE does not have &OPTIONAL parameters and the type of
821 ;; the &REST parameter is T, it may have been simplified from
822 ;;
823 ;; (function (... &optional t &rest t ...) ...)
824 ;;
825 ;; We cannot check the exact number of optional parameters then.
850 (:keyword
859 "Defining a ~S keyword not present in ~A."
860 key where)
863 (:optional
864 ;; We can exhaust TYPE-OPTIONAL when the type was
865 ;; simplified as described above.
869 (:rest
872 (:more-context
875 (:more-count
893 "The definition lacks the ~S key present in ~A."
898 ;;; Check that TYPE doesn't specify any funny args, and do the
899 ;;; intersection.
905 "The definition has no ~A, but the ~A did."
906 what where))))
916 nvars where nreq))
921 ;;; Check for syntactic and type conformance between the definition
922 ;;; FUNCTIONAL and the specified FUN-TYPE. If they are compatible
923 ;;; and REALLY-ASSERT is T, then add type assertions to the definition
924 ;;; from the FUN-TYPE.
925 ;;;
926 ;;; If there is a syntactic or type problem, then we call
927 ;;; LOSSAGE-FUN with an error message using WHERE as context
928 ;;; describing where FUN-TYPE came from.
929 ;;;
930 ;;; If there is no problem, we return T (even if REALLY-ASSERT was
931 ;;; false). If there was a problem, we return NIL.
936 unwinnage-fun
958 type-returns)))
960 "The result type from ~A:~% ~
961 ~/sb!impl:print-type/~@
962 conflicts with the definition's result type:~% ~
963 ~/sb!impl:print-type/"
964 where type-returns dtype)
965 nil)
972 policy)))
979 #-sb-xc identity
980 "Assignment to argument: ~S~% ~
981 prevents use of assertion from function ~
989 t))))))
991 ;;; FIXME: This is quite similar to ASSERT-NEW-DEFINITION.
1001 fun type
1005 ;; Can't actually test this. DEFSTRUCTs declare this, but non-toplevel
1006 ;; ones won't have an FTYPE at compile-time.
1007 #+nil
1011 ;;; If the function has both &REST and &KEY, FIND-OPTIONAL-DISPATCH-TYPES
1012 ;;; doesn't complain about the type missing &REST -- which is good, because in
1013 ;;; that case &REST is really an implementation detail and not part of the
1014 ;;; interface. However since we set the leaf type missing &REST from there
1015 ;;; would be a bad thing -- to make up a new type if necessary.
1030 type))
1031 \f
1032 ;;; Call FUN with (arg-lvar arg-type)
1061 ;;; Assert that CALL is to a function of the specified TYPE. It is
1062 ;;; assumed that the call is legal and has only constants in the
1063 ;;; keyword positions.
1071 ;; If the value is used in a non-tail position, and the lvar
1072 ;; is a single-use, assert the type. Multiple use sites need
1073 ;; to be elided because the assertion has to apply to all
1074 ;; uses. Tail positions are elided because the assertion
1075 ;; would cause us not the be in a tail-position anymore. MV
1076 ;; calls are elided because not only are the assertions of
1077 ;; less use there, but they can cause the MV call conversion
1078 ;; to cause astray.
1089 call))
1091 \f
1092 ;;;; FIXME: Move to some other file.
1100 "~@<Using ~S of type ~/sb!impl:print-type/ as ~
1101 a catch tag (which tends to be unportable because THROW ~
1102 and CATCH use EQ comparison)~@:>"
1105 "~@<Using ~{~S~^~#[~; or ~:;, ~]~} in ~S of type ~
1106 ~/sb!impl:print-type/ as a catch tag (which tends to be ~
1107 unportable because THROW and CATCH use EQ comparison)~@:>"
1116 :expected-type atype
1117 :format-control
1118 "~@<Value set ~2I~_[~{~S~^ ~}] ~I~_from ~S in~_~A ~
1119 ~I~_is not of type ~
1120 ~2I~_~/sb!impl:print-type-specifier/.~:>"
1123 atype))
1126 :expected-type atype
1127 :format-control
1128 "~@<Value set ~2I~_[~{~S~^ ~}] ~
1129 ~I~_from ~2I~_~{~S~^~#[~; or ~:;, ~]~} ~
1130 ~I~_of ~2I~_~S ~I~_in~_~A ~I~_is not of type ~
1131 ~2I~_~/sb!impl:print-type-specifier/.~:>"
1134 context
1135 atype)))
1139 :expected-type atype
1140 :format-control
1141 "~@<Value of ~S in ~_~A ~I~_is ~2I~_~S, ~
1142 ~I~_not a ~2I~_~/sb!impl:print-type-specifier/.~:@>"
1145 atype))
1148 :expected-type atype
1149 :format-control
1150 "~@<Value from ~2I~_~{~S~^~#[~; or ~:;, ~]~} ~
1151 ~I~_of ~2I~_~S ~I~_in~_~A ~I~_is ~2I~_~S, ~
1152 ~I~_not a ~2I~_~/sb!impl:print-type-specifier/.~:@>"
1155 atype)))))
1171 :format-control
1172 "~@<Constant ~2I~_~S ~Iconflicts with its ~
1173 asserted type ~
1174 ~2I~_~/sb!impl::print-type-specifier/.~@:>"
1177 :format-control
1178 "~@<Derived type of ~S is ~2I~_~S, ~
1179 ~I~_conflicting with its asserted type ~
1180 ~2I~_~/sb!impl:print-type-specifier/.~@:>"
1183 :format-control
1184 "~@<Derived type of ~2I~_~{~S~^~#[~; and ~:;, ~
1185 ~]~} ~I~_in ~2I~_~S ~I~_is ~
1186 ~2I~_~/sb!impl:print-type-specifier/, ~
1187 ~I~_conflicting with their asserted type ~
1188 ~2I~_~/sb!impl:print-type-specifier/.~@:>"
1190 dtype atype)))))