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-p 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 (defstruct (negation-type (:include ctype
42 (class-info (type-class-or-lose 'negation))
43 ;; FIXME: is this right? It's
44 ;; what they had before, anyway
46 (might-contain-other-types-p t))
49 (type (missing-arg) :type ctype))
51 (!define-type-class negation)
53 ;;; ARGS-TYPE objects are used both to represent VALUES types and
54 ;;; to represent FUNCTION types.
55 (defstruct (args-type (:include ctype)
58 ;; Lists of the type for each required and optional argument.
59 (required nil :type list)
60 (optional nil :type list)
61 ;; The type for the rest arg. NIL if there is no &REST arg.
62 (rest nil :type (or ctype null))
63 ;; true if &KEY arguments are specified
64 (keyp nil :type boolean)
65 ;; list of KEY-INFO structures describing the &KEY arguments
66 (keywords nil :type list)
67 ;; true if other &KEY arguments are allowed
68 (allowp nil :type boolean))
70 (defun canonicalize-args-type-args (required optional rest)
72 (let ((last-distinct-optional (position rest optional
76 (when last-distinct-optional
77 (subseq optional 0 (1+ last-distinct-optional))))))
78 (values required optional rest))
80 (defun args-types (lambda-list-like-thing)
82 (required optional restp rest keyp keys allowp auxp aux)
83 (parse-lambda-list-like-thing lambda-list-like-thing)
84 (declare (ignore aux))
86 (error "&AUX in a FUNCTION or VALUES type: ~S." lambda-list-like-thing))
87 (let ((required (mapcar #'single-value-specifier-type required))
88 (optional (mapcar #'single-value-specifier-type optional))
89 (rest (when restp (single-value-specifier-type rest)))
93 (unless (proper-list-of-length-p key 2)
94 (error "Keyword type description is not a two-list: ~S." key))
95 (let ((kwd (first key)))
96 (when (find kwd (key-info) :key #'key-info-name)
97 (error "~@<repeated keyword ~S in lambda list: ~2I~_~S~:>"
98 kwd lambda-list-like-thing))
102 :type (single-value-specifier-type (second key))))))
104 (multiple-value-bind (required optional rest)
105 (canonicalize-args-type-args required optional rest)
106 (values required optional rest keyp keywords allowp)))))
108 (defstruct (values-type
110 (class-info (type-class-or-lose 'values)))
111 (:constructor %make-values-type)
114 (defun make-values-type (&rest initargs
115 &key (args nil argsp) &allow-other-keys)
119 (multiple-value-bind (required optional rest keyp keywords allowp)
121 (if (and (null required)
123 (eq rest *universal-type*)
126 (%make-values-type :required required
132 (apply #'%make-values-type initargs)))
134 (!define-type-class values)
136 ;;; (SPECIFIER-TYPE 'FUNCTION) and its subtypes
137 (defstruct (fun-type (:include args-type
138 (class-info (type-class-or-lose 'function)))
139 (:constructor %make-fun-type))
140 ;; true if the arguments are unrestrictive, i.e. *
141 (wild-args nil :type boolean)
142 ;; type describing the return values. This is a values type
143 ;; when multiple values were specified for the return.
144 (returns (missing-arg) :type ctype))
145 (defun make-fun-type (&rest initargs
146 &key (args nil argsp) returns &allow-other-keys)
149 (if (eq returns *wild-type*)
150 (specifier-type 'function)
151 (%make-fun-type :wild-args t :returns returns))
152 (multiple-value-bind (required optional rest keyp keywords allowp)
154 (if (and (null required)
156 (eq rest *universal-type*)
158 (if (eq returns *wild-type*)
159 (specifier-type 'function)
160 (%make-fun-type :wild-args t :returns returns))
161 (%make-fun-type :required required
168 ;; FIXME: are we really sure that we won't make something that
169 ;; looks like a completely wild function here?
170 (apply #'%make-fun-type initargs)))
172 ;;; The CONSTANT-TYPE structure represents a use of the CONSTANT-ARG
173 ;;; "type specifier", which is only meaningful in function argument
174 ;;; type specifiers used within the compiler. (It represents something
175 ;;; that the compiler knows to be a constant.)
176 (defstruct (constant-type
178 (class-info (type-class-or-lose 'constant)))
180 ;; The type which the argument must be a constant instance of for this type
182 (type (missing-arg) :type ctype))
184 ;;; The NAMED-TYPE is used to represent *, T and NIL. These types must
185 ;;; be super- or sub-types of all types, not just classes and * and
186 ;;; NIL aren't classes anyway, so it wouldn't make much sense to make
187 ;;; them built-in classes.
188 (defstruct (named-type (:include ctype
189 (class-info (type-class-or-lose 'named)))
191 (name nil :type symbol))
193 ;;; a list of all the float "formats" (i.e. internal representations;
194 ;;; nothing to do with #'FORMAT), in order of decreasing precision
195 (eval-when (:compile-toplevel :load-toplevel :execute)
196 (defparameter *float-formats*
197 '(long-float double-float single-float short-float)))
199 ;;; The type of a float format.
200 (deftype float-format () `(member ,@*float-formats*))
202 ;;; A NUMERIC-TYPE represents any numeric type, including things
204 (defstruct (numeric-type (:include ctype
205 (class-info (type-class-or-lose 'number)))
206 (:constructor %make-numeric-type)
208 ;; the kind of numeric type we have, or NIL if not specified (just
209 ;; NUMBER or COMPLEX)
211 ;; KLUDGE: A slot named CLASS for a non-CLASS value is bad.
212 ;; Especially when a CLASS value *is* stored in another slot (called
213 ;; CLASS-INFO:-). Perhaps this should be called CLASS-NAME? Also
214 ;; weird that comment above says "Numeric-Type is used to represent
215 ;; all numeric types" but this slot doesn't allow COMPLEX as an
216 ;; option.. how does this fall into "not specified" NIL case above?
217 ;; Perhaps someday we can switch to CLOS and make NUMERIC-TYPE
218 ;; be an abstract base class and INTEGER-TYPE, RATIONAL-TYPE, and
219 ;; whatnot be concrete subclasses..
220 (class nil :type (member integer rational float nil) :read-only t)
221 ;; "format" for a float type (i.e. type specifier for a CPU
222 ;; representation of floating point, e.g. 'SINGLE-FLOAT -- nothing
223 ;; to do with #'FORMAT), or NIL if not specified or not a float.
224 ;; Formats which don't exist in a given implementation don't appear
226 (format nil :type (or float-format null) :read-only t)
227 ;; Is this a complex numeric type? Null if unknown (only in NUMBER).
229 ;; FIXME: I'm bewildered by FOO-P names for things not intended to
230 ;; interpreted as truth values. Perhaps rename this COMPLEXNESS?
231 (complexp :real :type (member :real :complex nil) :read-only t)
232 ;; The upper and lower bounds on the value, or NIL if there is no
233 ;; bound. If a list of a number, the bound is exclusive. Integer
234 ;; types never have exclusive bounds, i.e. they may have them on
235 ;; input, but they're canonicalized to inclusive bounds before we
237 (low nil :type (or number cons null) :read-only t)
238 (high nil :type (or number cons null) :read-only t))
240 ;;; Impose canonicalization rules for NUMERIC-TYPE. Note that in some
241 ;;; cases, despite the name, we return *EMPTY-TYPE* instead of a
243 (defun make-numeric-type (&key class format (complexp :real) low high
245 ;; if interval is empty
248 (if (or (consp low) (consp high)) ; if either bound is exclusive
249 (>= (type-bound-number low) (type-bound-number high))
252 (multiple-value-bind (canonical-low canonical-high)
255 ;; INTEGER types always have their LOW and HIGH bounds
256 ;; represented as inclusive, not exclusive values.
257 (values (if (consp low)
258 (1+ (type-bound-number low))
261 (1- (type-bound-number high))
264 ;; no canonicalization necessary
266 (when (and (eq class 'rational)
267 (integerp canonical-low)
268 (integerp canonical-high)
269 (= canonical-low canonical-high))
270 (setf class 'integer))
271 (%make-numeric-type :class class
276 :enumerable enumerable))))
278 (defun modified-numeric-type (base
280 (class (numeric-type-class base))
281 (format (numeric-type-format base))
282 (complexp (numeric-type-complexp base))
283 (low (numeric-type-low base))
284 (high (numeric-type-high base))
285 (enumerable (numeric-type-enumerable base)))
286 (make-numeric-type :class class
291 :enumerable enumerable))
293 ;;; An ARRAY-TYPE is used to represent any array type, including
294 ;;; things such as SIMPLE-STRING.
295 (defstruct (array-type (:include ctype
296 (class-info (type-class-or-lose 'array)))
297 (:constructor %make-array-type)
299 ;; the dimensions of the array, or * if unspecified. If a dimension
300 ;; is unspecified, it is *.
301 (dimensions '* :type (or list (member *)))
302 ;; Is this not a simple array type? (:MAYBE means that we don't know.)
303 (complexp :maybe :type (member t nil :maybe))
304 ;; the element type as originally specified
305 (element-type (missing-arg) :type ctype)
306 ;; the element type as it is specialized in this implementation
307 (specialized-element-type *wild-type* :type ctype))
308 (define-cached-synonym make-array-type)
310 ;;; A MEMBER-TYPE represent a use of the MEMBER type specifier. We
311 ;;; bother with this at this level because MEMBER types are fairly
312 ;;; important and union and intersection are well defined.
313 (defstruct (member-type (:include ctype
314 (class-info (type-class-or-lose 'member))
317 (:constructor %make-member-type (members))
318 #-sb-xc-host (:pure nil))
319 ;; the things in the set, with no duplications
320 (members nil :type list))
321 (defun make-member-type (&key members)
322 (declare (type list members))
323 ;; make sure that we've removed duplicates
324 (aver (= (length members) (length (remove-duplicates members))))
325 ;; if we have a pair of zeros (e.g. 0.0d0 and -0.0d0), then we can
326 ;; canonicalize to (DOUBLE-FLOAT 0.0d0 0.0d0), because numeric
327 ;; ranges are compared by arithmetic operators (while MEMBERship is
328 ;; compared by EQL). -- CSR, 2003-04-23
329 (let ((singlep (subsetp `(,(load-time-value (make-unportable-float :single-float-negative-zero)) 0.0f0) members))
330 (doublep (subsetp `(,(load-time-value (make-unportable-float :double-float-negative-zero)) 0.0d0) members))
332 (longp (subsetp `(,(load-time-value (make-unportable-float :long-float-negative-zero)) 0.0l0) members)))
333 (if (or singlep doublep #!+long-float longp)
336 (push (ctype-of 0.0f0) union-types)
337 (setf members (set-difference members `(,(load-time-value (make-unportable-float :single-float-negative-zero)) 0.0f0))))
339 (push (ctype-of 0.0d0) union-types)
340 (setf members (set-difference members `(,(load-time-value (make-unportable-float :double-float-negative-zero)) 0.0d0))))
343 (push (ctype-of 0.0l0) union-types)
344 (setf members (set-difference members `(,(load-time-value (make-unportable-float :long-float-negative-zero)) 0.0l0))))
345 (aver (not (null union-types)))
349 (cons (%make-member-type members)
351 (%make-member-type members))))
353 ;;; A COMPOUND-TYPE is a type defined out of a set of types, the
354 ;;; common parent of UNION-TYPE and INTERSECTION-TYPE.
355 (defstruct (compound-type (:include ctype
356 (might-contain-other-types-p t))
359 (types nil :type list :read-only t))
361 ;;; A UNION-TYPE represents a use of the OR type specifier which we
362 ;;; couldn't canonicalize to something simpler. Canonical form:
363 ;;; 1. All possible pairwise simplifications (using the UNION2 type
364 ;;; methods) have been performed. Thus e.g. there is never more
365 ;;; than one MEMBER-TYPE component. FIXME: As of sbcl-0.6.11.13,
366 ;;; this hadn't been fully implemented yet.
367 ;;; 2. There are never any UNION-TYPE components.
368 (defstruct (union-type (:include compound-type
369 (class-info (type-class-or-lose 'union)))
370 (:constructor %make-union-type (enumerable types))
372 (define-cached-synonym make-union-type)
374 ;;; An INTERSECTION-TYPE represents a use of the AND type specifier
375 ;;; which we couldn't canonicalize to something simpler. Canonical form:
376 ;;; 1. All possible pairwise simplifications (using the INTERSECTION2
377 ;;; type methods) have been performed. Thus e.g. there is never more
378 ;;; than one MEMBER-TYPE component.
379 ;;; 2. There are never any INTERSECTION-TYPE components: we've
380 ;;; flattened everything into a single INTERSECTION-TYPE object.
381 ;;; 3. There are never any UNION-TYPE components. Either we should
382 ;;; use the distributive rule to rearrange things so that
383 ;;; unions contain intersections and not vice versa, or we
384 ;;; should just punt to using a HAIRY-TYPE.
385 (defstruct (intersection-type (:include compound-type
386 (class-info (type-class-or-lose
388 (:constructor %make-intersection-type
392 ;;; Return TYPE converted to canonical form for a situation where the
393 ;;; "type" '* (which SBCL still represents as a type even though ANSI
394 ;;; CL defines it as a related but different kind of placeholder) is
395 ;;; equivalent to type T.
396 (defun type-*-to-t (type)
397 (if (type= type *wild-type*)
401 ;;; A CONS-TYPE is used to represent a CONS type.
402 (defstruct (cons-type (:include ctype (class-info (type-class-or-lose 'cons)))
404 ;; ANSI says that for CAR and CDR subtype
405 ;; specifiers '* is equivalent to T. In order
406 ;; to avoid special cases in SUBTYPEP and
407 ;; possibly elsewhere, we slam all CONS-TYPE
408 ;; objects into canonical form w.r.t. this
409 ;; equivalence at creation time.
410 %make-cons-type (car-raw-type
413 (car-type (type-*-to-t car-raw-type))
414 (cdr-type (type-*-to-t cdr-raw-type))))
416 ;; the CAR and CDR element types (to support ANSI (CONS FOO BAR) types)
418 ;; FIXME: Most or all other type structure slots could also be :READ-ONLY.
419 (car-type (missing-arg) :type ctype :read-only t)
420 (cdr-type (missing-arg) :type ctype :read-only t))
421 (defun make-cons-type (car-type cdr-type)
422 (if (or (eq car-type *empty-type*)
423 (eq cdr-type *empty-type*))
425 (%make-cons-type car-type cdr-type)))
429 ;;; Return the type structure corresponding to a type specifier. We
430 ;;; pick off structure types as a special case.
432 ;;; Note: VALUES-SPECIFIER-TYPE-CACHE-CLEAR must be called whenever a
433 ;;; type is defined (or redefined).
434 (defun-cached (values-specifier-type
435 :hash-function (lambda (x)
436 (logand (sxhash x) #x3FF))
438 :init-wrapper !cold-init-forms)
439 ((orig equal-but-no-car-recursion))
440 (let ((u (uncross orig)))
441 (or (info :type :builtin u)
442 (let ((spec (type-expand u)))
444 ((and (not (eq spec u))
445 (info :type :builtin spec)))
446 ((eq (info :type :kind spec) :instance)
447 (find-classoid spec))
448 ((typep spec 'classoid)
449 ;; There doesn't seem to be any way to translate
450 ;; (TYPEP SPEC 'BUILT-IN-CLASS) into something which can be
451 ;; executed on the host Common Lisp at cross-compilation time.
453 "stub: (TYPEP SPEC 'BUILT-IN-CLASS) on xc host")
454 (if (typep spec 'built-in-classoid)
455 (or (built-in-classoid-translation spec) spec)
458 (let* (;; FIXME: This automatic promotion of FOO-style
459 ;; specs to (FOO)-style specs violates the ANSI
460 ;; standard. Unfortunately, we can't fix the
461 ;; problem just by removing it, since then things
462 ;; downstream should break. But at some point we
463 ;; should fix this and the things downstream too.
464 (lspec (if (atom spec) (list spec) spec))
465 (fun (info :type :translator (car lspec))))
468 ((or (and (consp spec) (symbolp (car spec)))
470 (when (and *type-system-initialized*
471 (not (eq (info :type :kind spec)
472 :forthcoming-defclass-type)))
473 (signal 'parse-unknown-type :specifier spec))
474 ;; (The RETURN-FROM here inhibits caching.)
475 (return-from values-specifier-type
476 (make-unknown-type :specifier spec)))
478 (error "bad thing to be a type specifier: ~S"
481 ;;; This is like VALUES-SPECIFIER-TYPE, except that we guarantee to
482 ;;; never return a VALUES type.
483 (defun specifier-type (x)
484 (let ((res (values-specifier-type x)))
485 (when (values-type-p res)
486 (error "VALUES type illegal in this context:~% ~S" x))
489 (defun single-value-specifier-type (x)
490 (let ((res (specifier-type x)))
491 (if (eq res *wild-type*)
495 ;;; Similar to MACROEXPAND, but expands DEFTYPEs. We don't bother
496 ;;; returning a second value.
497 (defun type-expand (form)
498 (let ((def (cond ((symbolp form)
499 (info :type :expander form))
500 ((and (consp form) (symbolp (car form)))
501 (info :type :expander (car form)))
504 (type-expand (funcall def (if (consp form) form (list form))))
507 ;;; Note that the type NAME has been (re)defined, updating the
508 ;;; undefined warnings and VALUES-SPECIFIER-TYPE cache.
509 (defun %note-type-defined (name)
510 (declare (symbol name))
511 (note-name-defined name :type)
512 (when (boundp 'sb!kernel::*values-specifier-type-cache-vector*)
513 (values-specifier-type-cache-clear))
516 (!defun-from-collected-cold-init-forms !early-type-cold-init)