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 ;;;; representations of types
20 ;;; A HAIRY-TYPE represents anything too weird to be described
21 ;;; reasonably or to be useful, such as NOT, SATISFIES, unknown types,
22 ;;; and unreasonably complicated types involving AND. We just remember
23 ;;; the original type spec.
24 (defstruct (hairy-type (:include ctype
25 (class-info (type-class-or-lose 'hairy))
27 (might-contain-other-types? t))
30 ;; the Common Lisp type-specifier of the type we represent
31 (specifier nil :type t))
33 (!define-type-class hairy)
35 ;;; An UNKNOWN-TYPE is a type not known to the type system (not yet
36 ;;; defined). We make this distinction since we don't want to complain
37 ;;; about types that are hairy but defined.
38 (defstruct (unknown-type (:include hairy-type)
41 ;;; ARGS-TYPE objects are used both to represent VALUES types and
42 ;;; to represent FUNCTION types.
43 (defstruct (args-type (:include ctype)
46 ;; Lists of the type for each required and optional argument.
47 (required nil :type list)
48 (optional nil :type list)
49 ;; The type for the rest arg. NIL if there is no &REST arg.
50 (rest nil :type (or ctype null))
51 ;; true if &KEY arguments are specified
52 (keyp nil :type boolean)
53 ;; list of KEY-INFO structures describing the &KEY arguments
54 (keywords nil :type list)
55 ;; true if other &KEY arguments are allowed
56 (allowp nil :type boolean))
58 (defstruct (values-type
60 (class-info (type-class-or-lose 'values)))
63 (!define-type-class values)
65 ;;; (SPECIFIER-TYPE 'FUNCTION) and its subtypes
66 (defstruct (fun-type (:include args-type
67 (class-info (type-class-or-lose 'function))))
68 ;; true if the arguments are unrestrictive, i.e. *
69 (wild-args nil :type boolean)
70 ;; type describing the return values. This is a values type
71 ;; when multiple values were specified for the return.
72 (returns (missing-arg) :type ctype))
74 ;;; The CONSTANT-TYPE structure represents a use of the CONSTANT-ARG
75 ;;; "type specifier", which is only meaningful in function argument
76 ;;; type specifiers used within the compiler. (It represents something
77 ;;; that the compiler knows to be a constant.)
78 (defstruct (constant-type
80 (class-info (type-class-or-lose 'constant)))
82 ;; The type which the argument must be a constant instance of for this type
84 (type (missing-arg) :type ctype))
86 ;;; The NAMED-TYPE is used to represent *, T and NIL. These types must
87 ;;; be super- or sub-types of all types, not just classes and * and
88 ;;; NIL aren't classes anyway, so it wouldn't make much sense to make
89 ;;; them built-in classes.
90 (defstruct (named-type (:include ctype
91 (class-info (type-class-or-lose 'named)))
93 (name nil :type symbol))
95 ;;; a list of all the float "formats" (i.e. internal representations;
96 ;;; nothing to do with #'FORMAT), in order of decreasing precision
97 (eval-when (:compile-toplevel :load-toplevel :execute)
98 (defparameter *float-formats*
99 '(long-float double-float single-float short-float)))
101 ;;; The type of a float format.
102 (deftype float-format () `(member ,@*float-formats*))
104 ;;; A NUMERIC-TYPE represents any numeric type, including things
106 (defstruct (numeric-type (:include ctype
107 (class-info (type-class-or-lose 'number)))
108 (:constructor %make-numeric-type)
110 ;; the kind of numeric type we have, or NIL if not specified (just
111 ;; NUMBER or COMPLEX)
113 ;; KLUDGE: A slot named CLASS for a non-CLASS value is bad.
114 ;; Especially when a CLASS value *is* stored in another slot (called
115 ;; CLASS-INFO:-). Perhaps this should be called CLASS-NAME? Also
116 ;; weird that comment above says "Numeric-Type is used to represent
117 ;; all numeric types" but this slot doesn't allow COMPLEX as an
118 ;; option.. how does this fall into "not specified" NIL case above?
119 ;; Perhaps someday we can switch to CLOS and make NUMERIC-TYPE
120 ;; be an abstract base class and INTEGER-TYPE, RATIONAL-TYPE, and
121 ;; whatnot be concrete subclasses..
122 (class nil :type (member integer rational float nil) :read-only t)
123 ;; "format" for a float type (i.e. type specifier for a CPU
124 ;; representation of floating point, e.g. 'SINGLE-FLOAT -- nothing
125 ;; to do with #'FORMAT), or NIL if not specified or not a float.
126 ;; Formats which don't exist in a given implementation don't appear
128 (format nil :type (or float-format null) :read-only t)
129 ;; Is this a complex numeric type? Null if unknown (only in NUMBER).
131 ;; FIXME: I'm bewildered by FOO-P names for things not intended to
132 ;; interpreted as truth values. Perhaps rename this COMPLEXNESS?
133 (complexp :real :type (member :real :complex nil) :read-only t)
134 ;; The upper and lower bounds on the value, or NIL if there is no
135 ;; bound. If a list of a number, the bound is exclusive. Integer
136 ;; types never have exclusive bounds, i.e. they may have them on
137 ;; input, but they're canonicalized to inclusive bounds before we
139 (low nil :type (or number cons null) :read-only t)
140 (high nil :type (or number cons null) :read-only t))
142 ;;; Impose canonicalization rules for NUMERIC-TYPE. Note that in some
143 ;;; cases, despite the name, we return *EMPTY-TYPE* instead of a
145 (defun make-numeric-type (&key class format (complexp :real) low high
147 ;; if interval is empty
150 (if (or (consp low) (consp high)) ; if either bound is exclusive
151 (>= (type-bound-number low) (type-bound-number high))
154 (multiple-value-bind (canonical-low canonical-high)
157 ;; INTEGER types always have their LOW and HIGH bounds
158 ;; represented as inclusive, not exclusive values.
159 (values (if (consp low)
160 (1+ (type-bound-number low))
163 (1- (type-bound-number high))
165 #!+negative-zero-is-not-zero
167 ;; Canonicalize a low bound of (-0.0) to 0.0, and a high
168 ;; bound of (+0.0) to -0.0.
169 (values (if (and (consp low)
172 (minusp (float-sign (car low))))
173 (float 0.0 (car low))
175 (if (and (consp high)
178 (plusp (float-sign (car high))))
179 (float -0.0 (car high))
182 ;; no canonicalization necessary
184 (%make-numeric-type :class class
189 :enumerable enumerable))))
191 (defun modified-numeric-type (base
193 (class (numeric-type-class base))
194 (format (numeric-type-format base))
195 (complexp (numeric-type-complexp base))
196 (low (numeric-type-low base))
197 (high (numeric-type-high base))
198 (enumerable (numeric-type-enumerable base)))
199 (make-numeric-type :class class
204 :enumerable enumerable))
206 ;;; An ARRAY-TYPE is used to represent any array type, including
207 ;;; things such as SIMPLE-STRING.
208 (defstruct (array-type (:include ctype
209 (class-info (type-class-or-lose 'array)))
211 ;; the dimensions of the array, or * if unspecified. If a dimension
212 ;; is unspecified, it is *.
213 (dimensions '* :type (or list (member *)))
214 ;; Is this not a simple array type? (:MAYBE means that we don't know.)
215 (complexp :maybe :type (member t nil :maybe))
216 ;; the element type as originally specified
217 (element-type (missing-arg) :type ctype)
218 ;; the element type as it is specialized in this implementation
219 (specialized-element-type *wild-type* :type ctype))
221 ;;; A MEMBER-TYPE represent a use of the MEMBER type specifier. We
222 ;;; bother with this at this level because MEMBER types are fairly
223 ;;; important and union and intersection are well defined.
224 (defstruct (member-type (:include ctype
225 (class-info (type-class-or-lose 'member))
228 #-sb-xc-host (:pure nil))
229 ;; the things in the set, with no duplications
230 (members nil :type list))
232 ;;; A COMPOUND-TYPE is a type defined out of a set of types, the
233 ;;; common parent of UNION-TYPE and INTERSECTION-TYPE.
234 (defstruct (compound-type (:include ctype
235 (might-contain-other-types? t))
238 (types nil :type list :read-only t))
240 ;;; A UNION-TYPE represents a use of the OR type specifier which we
241 ;;; couldn't canonicalize to something simpler. Canonical form:
242 ;;; 1. All possible pairwise simplifications (using the UNION2 type
243 ;;; methods) have been performed. Thus e.g. there is never more
244 ;;; than one MEMBER-TYPE component. FIXME: As of sbcl-0.6.11.13,
245 ;;; this hadn't been fully implemented yet.
246 ;;; 2. There are never any UNION-TYPE components.
247 (defstruct (union-type (:include compound-type
248 (class-info (type-class-or-lose 'union)))
249 (:constructor %make-union-type (enumerable types))
252 ;;; An INTERSECTION-TYPE represents a use of the AND type specifier
253 ;;; which we couldn't canonicalize to something simpler. Canonical form:
254 ;;; 1. All possible pairwise simplifications (using the INTERSECTION2
255 ;;; type methods) have been performed. Thus e.g. there is never more
256 ;;; than one MEMBER-TYPE component.
257 ;;; 2. There are never any INTERSECTION-TYPE components: we've
258 ;;; flattened everything into a single INTERSECTION-TYPE object.
259 ;;; 3. There are never any UNION-TYPE components. Either we should
260 ;;; use the distributive rule to rearrange things so that
261 ;;; unions contain intersections and not vice versa, or we
262 ;;; should just punt to using a HAIRY-TYPE.
263 (defstruct (intersection-type (:include compound-type
264 (class-info (type-class-or-lose
266 (:constructor %make-intersection-type
270 ;;; Return TYPE converted to canonical form for a situation where the
271 ;;; "type" '* (which SBCL still represents as a type even though ANSI
272 ;;; CL defines it as a related but different kind of placeholder) is
273 ;;; equivalent to type T.
274 (defun type-*-to-t (type)
275 (if (type= type *wild-type*)
279 ;;; A CONS-TYPE is used to represent a CONS type.
280 (defstruct (cons-type (:include ctype (class-info (type-class-or-lose 'cons)))
282 ;; ANSI says that for CAR and CDR subtype
283 ;; specifiers '* is equivalent to T. In order
284 ;; to avoid special cases in SUBTYPEP and
285 ;; possibly elsewhere, we slam all CONS-TYPE
286 ;; objects into canonical form w.r.t. this
287 ;; equivalence at creation time.
288 make-cons-type (car-raw-type
291 (car-type (type-*-to-t car-raw-type))
292 (cdr-type (type-*-to-t cdr-raw-type))))
294 ;; the CAR and CDR element types (to support ANSI (CONS FOO BAR) types)
296 ;; FIXME: Most or all other type structure slots could also be :READ-ONLY.
297 (car-type (missing-arg) :type ctype :read-only t)
298 (cdr-type (missing-arg) :type ctype :read-only t))
302 ;;; Return the type structure corresponding to a type specifier. We
303 ;;; pick off structure types as a special case.
305 ;;; Note: VALUES-SPECIFIER-TYPE-CACHE-CLEAR must be called whenever a
306 ;;; type is defined (or redefined).
307 (defun-cached (values-specifier-type
308 :hash-function (lambda (x)
309 (logand (sxhash x) #x3FF))
311 :init-wrapper !cold-init-forms)
313 (let ((u (uncross orig)))
314 (or (info :type :builtin u)
315 (let ((spec (type-expand u)))
317 ((and (not (eq spec u))
318 (info :type :builtin spec)))
319 ((eq (info :type :kind spec) :instance)
320 (sb!xc:find-class spec))
322 ;; There doesn't seem to be any way to translate
323 ;; (TYPEP SPEC 'BUILT-IN-CLASS) into something which can be
324 ;; executed on the host Common Lisp at cross-compilation time.
326 "stub: (TYPEP SPEC 'BUILT-IN-CLASS) on xc host")
327 (if (typep spec 'built-in-class)
328 (or (built-in-class-translation spec) spec)
331 (let* (;; FIXME: This automatic promotion of FOO-style
332 ;; specs to (FOO)-style specs violates the ANSI
333 ;; standard. Unfortunately, we can't fix the
334 ;; problem just by removing it, since then things
335 ;; downstream should break. But at some point we
336 ;; should fix this and the things downstream too.
337 (lspec (if (atom spec) (list spec) spec))
338 (fun (info :type :translator (car lspec))))
341 ((or (and (consp spec) (symbolp (car spec)))
343 (when (and *type-system-initialized*
344 (not (eq (info :type :kind spec)
345 :forthcoming-defclass-type)))
346 (signal 'parse-unknown-type :specifier spec))
347 ;; (The RETURN-FROM here inhibits caching.)
348 (return-from values-specifier-type
349 (make-unknown-type :specifier spec)))
351 (error "bad thing to be a type specifier: ~S"
354 ;;; This is like VALUES-SPECIFIER-TYPE, except that we guarantee to
355 ;;; never return a VALUES type.
356 (defun specifier-type (x)
357 (let ((res (values-specifier-type x)))
358 (when (values-type-p res)
359 (error "VALUES type illegal in this context:~% ~S" x))
362 ;;; Similar to MACROEXPAND, but expands DEFTYPEs. We don't bother
363 ;;; returning a second value.
364 (defun type-expand (form)
365 (let ((def (cond ((symbolp form)
366 (info :type :expander form))
367 ((and (consp form) (symbolp (car form)))
368 (info :type :expander (car form)))
371 (type-expand (funcall def (if (consp form) form (list form))))
374 ;;; Note that the type NAME has been (re)defined, updating the
375 ;;; undefined warnings and VALUES-SPECIFIER-TYPE cache.
376 (defun %note-type-defined (name)
377 (declare (symbol name))
378 (note-name-defined name :type)
379 (when (boundp 'sb!kernel::*values-specifier-type-cache-vector*)
380 (values-specifier-type-cache-clear))
383 (!defun-from-collected-cold-init-forms !early-type-cold-init)