1 ;;;; This software is part of the SBCL system. See the README file for
4 ;;;; This software is derived from the CMU CL system, which was
5 ;;;; written at Carnegie Mellon University and released into the
6 ;;;; public domain. The software is in the public domain and is
7 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
8 ;;;; files for more information.
10 (in-package "SB!KERNEL")
12 (!begin-collecting-cold-init-forms)
14 ;;; Has the type system been properly initialized? (I.e. is it OK to
16 (defvar *type-system-initialized* #+sb-xc-host nil) ; (set in cold load)
18 ;;; Use experimental type functionality?
20 ;;; REMOVEME: Eventually the new type functionality should be stable
21 ;;; enough that nothing depends on this, and we can remove it again.
23 (!cold-init-forms (setf *xtype?* nil))
25 ;;; Return the type structure corresponding to a type specifier. We
26 ;;; pick off structure types as a special case.
28 ;;; Note: VALUES-SPECIFIER-TYPE-CACHE-CLEAR must be called whenever a
29 ;;; type is defined (or redefined).
30 (defun-cached (values-specifier-type
31 :hash-function (lambda (x)
32 ;; FIXME: The THE FIXNUM stuff is
33 ;; redundant in SBCL (or modern CMU
34 ;; CL) because of type inference.
36 (logand (the fixnum (sxhash x))
39 :init-wrapper !cold-init-forms)
41 (let ((u (uncross orig)))
42 (or (info :type :builtin u)
43 (let ((spec (type-expand u)))
45 ((and (not (eq spec u))
46 (info :type :builtin spec)))
47 ((eq (info :type :kind spec) :instance)
48 (sb!xc:find-class spec))
50 ;; There doesn't seem to be any way to translate
51 ;; (TYPEP SPEC 'BUILT-IN-CLASS) into something which can be
52 ;; executed on the host Common Lisp at cross-compilation time.
54 "stub: (TYPEP SPEC 'BUILT-IN-CLASS) on xc host")
55 (if (typep spec 'built-in-class)
56 (or (built-in-class-translation spec) spec)
59 (let* (;; FIXME: This automatic promotion of FOO-style
60 ;; specs to (FOO)-style specs violates the ANSI
61 ;; standard. Unfortunately, we can't fix the
62 ;; problem just by removing it, since then things
63 ;; downstream should break. But at some point we
64 ;; should fix this and the things downstream too.
65 (lspec (if (atom spec) (list spec) spec))
66 (fun (info :type :translator (car lspec))))
69 ((or (and (consp spec) (symbolp (car spec)))
71 (when *type-system-initialized*
72 (signal 'parse-unknown-type :specifier spec))
73 ;; (The RETURN-FROM here inhibits caching.)
74 (return-from values-specifier-type
75 (make-unknown-type :specifier spec)))
77 (error "bad thing to be a type specifier: ~S"
80 ;;; Like VALUES-SPECIFIER-TYPE, except that we guarantee to never
81 ;;; return a VALUES type.
82 (defun specifier-type (x)
83 (let ((res (values-specifier-type x)))
84 (when (values-type-p res)
85 (error "VALUES type illegal in this context:~% ~S" x))
88 ;;; Similar to MACROEXPAND, but expands DEFTYPEs. We don't bother
89 ;;; returning a second value.
90 (defun type-expand (form)
91 (let ((def (cond ((symbolp form)
92 (info :type :expander form))
93 ((and (consp form) (symbolp (car form)))
94 (info :type :expander (car form)))
97 (type-expand (funcall def (if (consp form) form (list form))))
100 ;;; A HAIRY-TYPE represents anything too weird to be described
101 ;;; reasonably or to be useful, such as NOT, SATISFIES, unknown types,
102 ;;; and unreasonably complicated types involving AND. We just remember
103 ;;; the original type spec.
104 (defstruct (hairy-type (:include ctype
105 (class-info (type-class-or-lose 'hairy))
109 ;; the Common Lisp type-specifier
110 (specifier nil :type t))
112 (!define-type-class hairy)
114 ;;; An UNKNOWN-TYPE is a type not known to the type system (not yet
115 ;;; defined). We make this distinction since we don't want to complain
116 ;;; about types that are hairy but defined.
117 (defstruct (unknown-type (:include hairy-type)
120 ;;; ARGS-TYPE objects are used both to represent VALUES types and
121 ;;; to represent FUNCTION types.
122 (defstruct (args-type (:include ctype)
125 ;; Lists of the type for each required and optional argument.
126 (required nil :type list)
127 (optional nil :type list)
128 ;; The type for the rest arg. NIL if there is no rest arg.
129 (rest nil :type (or ctype null))
130 ;; true if &KEY arguments are specified
131 (keyp nil :type boolean)
132 ;; list of KEY-INFO structures describing the &KEY arguments
133 (keywords nil :type list)
134 ;; true if other &KEY arguments are allowed
135 (allowp nil :type boolean))
137 (defstruct (values-type
139 (class-info (type-class-or-lose 'values)))
142 (!define-type-class values)
144 (defstruct (function-type
146 (class-info (type-class-or-lose 'function))))
147 ;; True if the arguments are unrestrictive, i.e. *.
148 (wild-args nil :type boolean)
149 ;; Type describing the return values. This is a values type
150 ;; when multiple values were specified for the return.
151 (returns (required-argument) :type ctype))
153 ;;; The CONSTANT-TYPE structure represents a use of the
154 ;;; CONSTANT-ARGUMENT "type specifier", which is only meaningful in
155 ;;; function argument type specifiers used within the compiler. (It
156 ;;; represents something that the compiler knows to be a constant.)
157 (defstruct (constant-type
159 (class-info (type-class-or-lose 'constant)))
161 ;; The type which the argument must be a constant instance of for this type
163 (type (required-argument) :type ctype))
165 ;;; The NAMED-TYPE is used to represent *, T and NIL. These types must be
166 ;;; super- or sub-types of all types, not just classes and * and NIL aren't
167 ;;; classes anyway, so it wouldn't make much sense to make them built-in
169 (defstruct (named-type (:include ctype
170 (class-info (type-class-or-lose 'named)))
172 (name nil :type symbol))
174 ;;; a list of all the float "formats" (i.e. internal representations;
175 ;;; nothing to do with #'FORMAT), in order of decreasing precision
176 (eval-when (:compile-toplevel :load-toplevel :execute)
177 (defparameter *float-formats*
178 '(long-float double-float single-float short-float)))
180 ;;; The type of a float format.
181 (deftype float-format () `(member ,@*float-formats*))
183 ;;; A NUMERIC-TYPE represents any numeric type, including things
185 (defstruct (numeric-type (:include ctype
186 (class-info (type-class-or-lose 'number)))
187 #!+negative-zero-is-not-zero
188 (:constructor %make-numeric-type))
189 ;; the kind of numeric type we have, or NIL if not specified (just
190 ;; NUMBER or COMPLEX)
192 ;; KLUDGE: A slot named CLASS for a non-CLASS value is bad.
193 ;; Especially when a CLASS value *is* stored in another slot (called
194 ;; CLASS-INFO:-). Perhaps this should be called CLASS-NAME? Also
195 ;; weird that comment above says "Numeric-Type is used to represent
196 ;; all numeric types" but this slot doesn't allow COMPLEX as an
197 ;; option.. how does this fall into "not specified" NIL case above?
198 (class nil :type (member integer rational float nil))
199 ;; "format" for a float type (i.e. type specifier for a CPU
200 ;; representation of floating point, e.g. 'SINGLE-FLOAT -- nothing
201 ;; to do with #'FORMAT), or NIL if not specified or not a float.
202 ;; Formats which don't exist in a given implementation don't appear
204 (format nil :type (or float-format null))
205 ;; Is this a complex numeric type? Null if unknown (only in NUMBER).
207 ;; FIXME: I'm bewildered by FOO-P names for things not intended to
208 ;; interpreted as truth values. Perhaps rename this COMPLEXNESS?
209 (complexp :real :type (member :real :complex nil))
210 ;; The upper and lower bounds on the value, or NIL if there is no
211 ;; bound. If a list of a number, the bound is exclusive. Integer
212 ;; types never have exclusive bounds.
213 (low nil :type (or number cons null))
214 (high nil :type (or number cons null)))
216 ;;; An ARRAY-TYPE is used to represent any array type, including
217 ;;; things such as SIMPLE-STRING.
218 (defstruct (array-type (:include ctype
219 (class-info (type-class-or-lose 'array)))
221 ;; the dimensions of the array, or * if unspecified. If a dimension
222 ;; is unspecified, it is *.
223 (dimensions '* :type (or list (member *)))
224 ;; Is this not a simple array type? (:MAYBE means that we don't know.)
225 (complexp :maybe :type (member t nil :maybe))
226 ;; the element type as originally specified
227 (element-type (required-argument) :type ctype)
228 ;; the element type as it is specialized in this implementation
229 (specialized-element-type *wild-type* :type ctype))
231 ;;; A MEMBER-TYPE represent a use of the MEMBER type specifier. We
232 ;;; bother with this at this level because MEMBER types are fairly
233 ;;; important and union and intersection are well defined.
234 (defstruct (member-type (:include ctype
235 (class-info (type-class-or-lose 'member))
238 #-sb-xc-host (:pure nil))
239 ;; the things in the set, with no duplications
240 (members nil :type list))
242 ;;; A COMPOUND-TYPE is a type defined out of a set of types, the
243 ;;; common parent of UNION-TYPE and INTERSECTION-TYPE.
244 (defstruct (compound-type (:include ctype)
247 (types nil :type list :read-only t))
249 ;;; A UNION-TYPE represents a use of the OR type specifier which we
250 ;;; couldn't canonicalize to something simpler. Canonical form:
251 ;;; 1. All possible pairwise simplifications (using the UNION2 type
252 ;;; methods) have been performed. Thus e.g. there is never more
253 ;;; than one MEMBER-TYPE component. FIXME: As of sbcl-0.6.11.13,
254 ;;; this hadn't been fully implemented yet.
255 ;;; 2. There are never any UNION-TYPE components.
256 (defstruct (union-type (:include compound-type
257 (class-info (type-class-or-lose 'union)))
258 (:constructor %make-union-type (enumerable types))
261 ;;; An INTERSECTION-TYPE represents a use of the AND type specifier
262 ;;; which we couldn't canonicalize to something simpler. Canonical form:
263 ;;; 1. All possible pairwise simplifications (using the INTERSECTION2
264 ;;; type methods) have been performed. Thus e.g. there is never more
265 ;;; than one MEMBER-TYPE component.
266 ;;; 2. There are never any INTERSECTION-TYPE components: we've
267 ;;; flattened everything into a single INTERSECTION-TYPE object.
268 ;;; 3. There are never any UNION-TYPE components. Either we should
269 ;;; use the distributive rule to rearrange things so that
270 ;;; unions contain intersections and not vice versa, or we
271 ;;; should just punt to using a HAIRY-TYPE.
272 (defstruct (intersection-type (:include compound-type
273 (class-info (type-class-or-lose
275 (:constructor %make-intersection-type
279 ;;; Return TYPE converted to canonical form for a situation where the
280 ;;; "type" '* (which SBCL still represents as a type even though ANSI
281 ;;; CL defines it as a related but different kind of placeholder) is
282 ;;; equivalent to type T.
283 (defun type-*-to-t (type)
284 (if (type= type *wild-type*)
288 ;;; A CONS-TYPE is used to represent a CONS type.
289 (defstruct (cons-type (:include ctype (:class-info (type-class-or-lose 'cons)))
291 ;; ANSI says that for CAR and CDR subtype
292 ;; specifiers '* is equivalent to T. In order
293 ;; to avoid special cases in SUBTYPEP and
294 ;; possibly elsewhere, we slam all CONS-TYPE
295 ;; objects into canonical form w.r.t. this
296 ;; equivalence at creation time.
297 make-cons-type (car-raw-type
300 (car-type (type-*-to-t car-raw-type))
301 (cdr-type (type-*-to-t cdr-raw-type))))
303 ;; the CAR and CDR element types (to support ANSI (CONS FOO BAR) types)
305 ;; FIXME: Most or all other type structure slots could also be :READ-ONLY.
306 (car-type (required-argument) :type ctype :read-only t)
307 (cdr-type (required-argument) :type ctype :read-only t))
309 ;;; Note that the type NAME has been (re)defined, updating the
310 ;;; undefined warnings and VALUES-SPECIFIER-TYPE cache.
311 (defun %note-type-defined (name)
312 (declare (symbol name))
313 (note-name-defined name :type)
314 (when (boundp 'sb!kernel::*values-specifier-type-cache-vector*)
315 (values-specifier-type-cache-clear))
318 (!defun-from-collected-cold-init-forms !early-type-cold-init)