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 ;;;; representations of types
16 ;;; A HAIRY-TYPE represents anything too weird to be described
17 ;;; reasonably or to be useful, such as NOT, SATISFIES, unknown types,
18 ;;; and unreasonably complicated types involving AND. We just remember
19 ;;; the original type spec.
20 (defstruct (hairy-type (:include ctype
21 (class-info (type-class-or-lose 'hairy
))
23 (might-contain-other-types-p t
))
26 ;; the Common Lisp type-specifier of the type we represent
27 (specifier nil
:type t
))
29 (!define-type-class hairy
)
31 ;;; An UNKNOWN-TYPE is a type not known to the type system (not yet
32 ;;; defined). We make this distinction since we don't want to complain
33 ;;; about types that are hairy but defined.
34 (defstruct (unknown-type (:include hairy-type
)
37 (defstruct (negation-type (:include ctype
38 (class-info (type-class-or-lose 'negation
))
39 ;; FIXME: is this right? It's
40 ;; what they had before, anyway
42 (might-contain-other-types-p t
))
45 (type (missing-arg) :type ctype
))
47 (!define-type-class negation
)
49 ;;; ARGS-TYPE objects are used both to represent VALUES types and
50 ;;; to represent FUNCTION types.
51 (defstruct (args-type (:include ctype
)
54 ;; Lists of the type for each required and optional argument.
55 (required nil
:type list
)
56 (optional nil
:type list
)
57 ;; The type for the rest arg. NIL if there is no &REST arg.
58 (rest nil
:type
(or ctype null
))
59 ;; true if &KEY arguments are specified
60 (keyp nil
:type boolean
)
61 ;; list of KEY-INFO structures describing the &KEY arguments
62 (keywords nil
:type list
)
63 ;; true if other &KEY arguments are allowed
64 (allowp nil
:type boolean
))
66 (defun canonicalize-args-type-args (required optional rest
)
67 (when (eq rest
*empty-type
*)
70 (loop with last-not-rest
= nil
73 do
(cond ((eq opt
*empty-type
*)
74 (return (values required
(subseq optional i
) rest
)))
76 (setq last-not-rest i
)))
77 finally
(return (values required
79 (subseq optional
0 (1+ last-not-rest
))
83 (defun args-types (lambda-list-like-thing)
85 (required optional restp rest keyp keys allowp auxp aux
86 morep more-context more-count llk-p
)
87 (parse-lambda-list-like-thing lambda-list-like-thing
)
88 (declare (ignore aux morep more-context more-count
))
90 (error "&AUX in a FUNCTION or VALUES type: ~S." lambda-list-like-thing
))
91 (let ((required (mapcar #'single-value-specifier-type required
))
92 (optional (mapcar #'single-value-specifier-type optional
))
93 (rest (when restp
(single-value-specifier-type rest
)))
97 (unless (proper-list-of-length-p key
2)
98 (error "Keyword type description is not a two-list: ~S." key
))
99 (let ((kwd (first key
)))
100 (when (find kwd
(key-info) :key
#'key-info-name
)
101 (error "~@<repeated keyword ~S in lambda list: ~2I~_~S~:>"
102 kwd lambda-list-like-thing
))
106 :type
(single-value-specifier-type (second key
))))))
108 (multiple-value-bind (required optional rest
)
109 (canonicalize-args-type-args required optional rest
)
110 (values required optional rest keyp keywords allowp llk-p
)))))
112 (defstruct (values-type
114 (class-info (type-class-or-lose 'values
)))
115 (:constructor %make-values-type
)
118 (defun-cached (make-values-type-cached
120 :hash-function
(lambda (req opt rest allowp
)
122 (type-list-cache-hash req
)
123 (type-list-cache-hash opt
)
125 (type-hash-value rest
)
129 ((required equal-but-no-car-recursion
)
130 (optional equal-but-no-car-recursion
)
133 (%make-values-type
:required required
138 (defun make-values-type (&key
(args nil argsp
)
139 required optional rest allowp
)
143 (multiple-value-bind (required optional rest keyp keywords allowp
146 (declare (ignore keywords
))
148 (error "&KEY appeared in a VALUES type specifier ~S."
151 (make-values-type :required required
155 (make-short-values-type required
))))
156 (multiple-value-bind (required optional rest
)
157 (canonicalize-args-type-args required optional rest
)
158 (cond ((and (null required
)
160 (eq rest
*universal-type
*))
162 ((memq *empty-type
* required
)
164 (t (make-values-type-cached required optional
167 (!define-type-class values
)
169 ;;; (SPECIFIER-TYPE 'FUNCTION) and its subtypes
170 (defstruct (fun-type (:include args-type
171 (class-info (type-class-or-lose 'function
)))
173 %make-fun-type
(&key required optional rest
177 &aux
(rest (if (eq rest
*empty-type
*)
180 ;; true if the arguments are unrestrictive, i.e. *
181 (wild-args nil
:type boolean
)
182 ;; type describing the return values. This is a values type
183 ;; when multiple values were specified for the return.
184 (returns (missing-arg) :type ctype
))
185 (defun make-fun-type (&rest initargs
186 &key
(args nil argsp
) returns
&allow-other-keys
)
189 (if (eq returns
*wild-type
*)
190 (specifier-type 'function
)
191 (%make-fun-type
:wild-args t
:returns returns
))
192 (multiple-value-bind (required optional rest keyp keywords allowp
)
194 (if (and (null required
)
196 (eq rest
*universal-type
*)
198 (if (eq returns
*wild-type
*)
199 (specifier-type 'function
)
200 (%make-fun-type
:wild-args t
:returns returns
))
201 (%make-fun-type
:required required
208 ;; FIXME: are we really sure that we won't make something that
209 ;; looks like a completely wild function here?
210 (apply #'%make-fun-type initargs
)))
212 ;;; The CONSTANT-TYPE structure represents a use of the CONSTANT-ARG
213 ;;; "type specifier", which is only meaningful in function argument
214 ;;; type specifiers used within the compiler. (It represents something
215 ;;; that the compiler knows to be a constant.)
216 (defstruct (constant-type
218 (class-info (type-class-or-lose 'constant
)))
220 ;; The type which the argument must be a constant instance of for this type
222 (type (missing-arg) :type ctype
))
224 ;;; The NAMED-TYPE is used to represent *, T and NIL. These types must
225 ;;; be super- or sub-types of all types, not just classes and * and
226 ;;; NIL aren't classes anyway, so it wouldn't make much sense to make
227 ;;; them built-in classes.
228 (defstruct (named-type (:include ctype
229 (class-info (type-class-or-lose 'named
)))
231 (name nil
:type symbol
))
233 ;;; a list of all the float "formats" (i.e. internal representations;
234 ;;; nothing to do with #'FORMAT), in order of decreasing precision
235 (eval-when (:compile-toplevel
:load-toplevel
:execute
)
236 (defparameter *float-formats
*
237 '(long-float double-float single-float short-float
)))
239 ;;; The type of a float format.
240 (deftype float-format
() `(member ,@*float-formats
*))
242 ;;; A NUMERIC-TYPE represents any numeric type, including things
244 (defstruct (numeric-type (:include ctype
245 (class-info (type-class-or-lose 'number
)))
246 (:constructor %make-numeric-type
)
248 ;; the kind of numeric type we have, or NIL if not specified (just
249 ;; NUMBER or COMPLEX)
251 ;; KLUDGE: A slot named CLASS for a non-CLASS value is bad.
252 ;; Especially when a CLASS value *is* stored in another slot (called
253 ;; CLASS-INFO:-). Perhaps this should be called CLASS-NAME? Also
254 ;; weird that comment above says "Numeric-Type is used to represent
255 ;; all numeric types" but this slot doesn't allow COMPLEX as an
256 ;; option.. how does this fall into "not specified" NIL case above?
257 ;; Perhaps someday we can switch to CLOS and make NUMERIC-TYPE
258 ;; be an abstract base class and INTEGER-TYPE, RATIONAL-TYPE, and
259 ;; whatnot be concrete subclasses..
260 (class nil
:type
(member integer rational float nil
) :read-only t
)
261 ;; "format" for a float type (i.e. type specifier for a CPU
262 ;; representation of floating point, e.g. 'SINGLE-FLOAT -- nothing
263 ;; to do with #'FORMAT), or NIL if not specified or not a float.
264 ;; Formats which don't exist in a given implementation don't appear
266 (format nil
:type
(or float-format null
) :read-only t
)
267 ;; Is this a complex numeric type? Null if unknown (only in NUMBER).
269 ;; FIXME: I'm bewildered by FOO-P names for things not intended to
270 ;; interpreted as truth values. Perhaps rename this COMPLEXNESS?
271 (complexp :real
:type
(member :real
:complex nil
) :read-only t
)
272 ;; The upper and lower bounds on the value, or NIL if there is no
273 ;; bound. If a list of a number, the bound is exclusive. Integer
274 ;; types never have exclusive bounds, i.e. they may have them on
275 ;; input, but they're canonicalized to inclusive bounds before we
277 (low nil
:type
(or number cons null
) :read-only t
)
278 (high nil
:type
(or number cons null
) :read-only t
))
280 ;;; Impose canonicalization rules for NUMERIC-TYPE. Note that in some
281 ;;; cases, despite the name, we return *EMPTY-TYPE* instead of a
283 (defun make-numeric-type (&key class format
(complexp :real
) low high
285 ;; if interval is empty
288 (if (or (consp low
) (consp high
)) ; if either bound is exclusive
289 (>= (type-bound-number low
) (type-bound-number high
))
292 (multiple-value-bind (canonical-low canonical-high
)
295 ;; INTEGER types always have their LOW and HIGH bounds
296 ;; represented as inclusive, not exclusive values.
297 (values (if (consp low
)
298 (1+ (type-bound-number low
))
301 (1- (type-bound-number high
))
304 ;; no canonicalization necessary
306 (when (and (eq class
'rational
)
307 (integerp canonical-low
)
308 (integerp canonical-high
)
309 (= canonical-low canonical-high
))
310 (setf class
'integer
))
311 (%make-numeric-type
:class class
316 :enumerable enumerable
))))
318 (defun modified-numeric-type (base
320 (class (numeric-type-class base
))
321 (format (numeric-type-format base
))
322 (complexp (numeric-type-complexp base
))
323 (low (numeric-type-low base
))
324 (high (numeric-type-high base
))
325 (enumerable (numeric-type-enumerable base
)))
326 (make-numeric-type :class class
331 :enumerable enumerable
))
333 (defstruct (character-set-type
335 (class-info (type-class-or-lose 'character-set
)))
336 (:constructor %make-character-set-type
)
338 (pairs (missing-arg) :type list
:read-only t
))
339 (defun make-character-set-type (&key pairs
)
340 (aver (equal (mapcar #'car pairs
)
341 (sort (mapcar #'car pairs
) #'<)))
342 (let ((pairs (let (result)
343 (do ((pairs pairs
(cdr pairs
)))
344 ((null pairs
) (nreverse result
))
345 (destructuring-bind (low . high
) (car pairs
)
346 (loop for
(low1 . high1
) in
(cdr pairs
)
347 if
(<= low1
(1+ high
))
348 do
(progn (setf high
(max high high1
))
349 (setf pairs
(cdr pairs
)))
350 else do
(return nil
))
352 ((>= low sb
!xc
:char-code-limit
))
354 (t (push (cons (max 0 low
)
355 (min high
(1- sb
!xc
:char-code-limit
)))
359 (%make-character-set-type
:pairs pairs
))))
361 ;;; An ARRAY-TYPE is used to represent any array type, including
362 ;;; things such as SIMPLE-BASE-STRING.
363 (defstruct (array-type (:include ctype
364 (class-info (type-class-or-lose 'array
)))
365 (:constructor %make-array-type
)
367 ;; the dimensions of the array, or * if unspecified. If a dimension
368 ;; is unspecified, it is *.
369 (dimensions '* :type
(or list
(member *)))
370 ;; Is this not a simple array type? (:MAYBE means that we don't know.)
371 (complexp :maybe
:type
(member t nil
:maybe
))
372 ;; the element type as originally specified
373 (element-type (missing-arg) :type ctype
)
374 ;; the element type as it is specialized in this implementation
375 (specialized-element-type *wild-type
* :type ctype
))
376 (define-cached-synonym make-array-type
)
378 ;;; A MEMBER-TYPE represent a use of the MEMBER type specifier. We
379 ;;; bother with this at this level because MEMBER types are fairly
380 ;;; important and union and intersection are well defined.
381 (defstruct (member-type (:include ctype
382 (class-info (type-class-or-lose 'member
))
385 (:constructor %make-member-type
(members))
386 #-sb-xc-host
(:pure nil
))
387 ;; the things in the set, with no duplications
388 (members nil
:type list
))
389 (defun make-member-type (&key members
)
390 (declare (type list members
))
391 ;; make sure that we've removed duplicates
392 (aver (= (length members
) (length (remove-duplicates members
))))
393 ;; if we have a pair of zeros (e.g. 0.0d0 and -0.0d0), then we can
394 ;; canonicalize to (DOUBLE-FLOAT 0.0d0 0.0d0), because numeric
395 ;; ranges are compared by arithmetic operators (while MEMBERship is
396 ;; compared by EQL). -- CSR, 2003-04-23
397 (let ((singlep (subsetp `(,(load-time-value (make-unportable-float :single-float-negative-zero
)) 0.0f0
) members
))
398 (doublep (subsetp `(,(load-time-value (make-unportable-float :double-float-negative-zero
)) 0.0d0
) members
))
400 (longp (subsetp `(,(load-time-value (make-unportable-float :long-float-negative-zero
)) 0.0l0) members
)))
401 (if (or singlep doublep
#!+long-float longp
)
404 (push (ctype-of 0.0f0
) union-types
)
405 (setf members
(set-difference members
`(,(load-time-value (make-unportable-float :single-float-negative-zero
)) 0.0f0
))))
407 (push (ctype-of 0.0d0
) union-types
)
408 (setf members
(set-difference members
`(,(load-time-value (make-unportable-float :double-float-negative-zero
)) 0.0d0
))))
411 (push (ctype-of 0.0l0) union-types
)
412 (setf members
(set-difference members
`(,(load-time-value (make-unportable-float :long-float-negative-zero
)) 0.0l0))))
413 (aver (not (null union-types
)))
417 (cons (%make-member-type members
)
419 (%make-member-type members
))))
421 ;;; A COMPOUND-TYPE is a type defined out of a set of types, the
422 ;;; common parent of UNION-TYPE and INTERSECTION-TYPE.
423 (defstruct (compound-type (:include ctype
424 (might-contain-other-types-p t
))
427 (types nil
:type list
:read-only t
))
429 ;;; A UNION-TYPE represents a use of the OR type specifier which we
430 ;;; couldn't canonicalize to something simpler. Canonical form:
431 ;;; 1. All possible pairwise simplifications (using the UNION2 type
432 ;;; methods) have been performed. Thus e.g. there is never more
433 ;;; than one MEMBER-TYPE component. FIXME: As of sbcl-0.6.11.13,
434 ;;; this hadn't been fully implemented yet.
435 ;;; 2. There are never any UNION-TYPE components.
436 (defstruct (union-type (:include compound-type
437 (class-info (type-class-or-lose 'union
)))
438 (:constructor %make-union-type
(enumerable types
))
440 (define-cached-synonym make-union-type
)
442 ;;; An INTERSECTION-TYPE represents a use of the AND type specifier
443 ;;; which we couldn't canonicalize to something simpler. Canonical form:
444 ;;; 1. All possible pairwise simplifications (using the INTERSECTION2
445 ;;; type methods) have been performed. Thus e.g. there is never more
446 ;;; than one MEMBER-TYPE component.
447 ;;; 2. There are never any INTERSECTION-TYPE components: we've
448 ;;; flattened everything into a single INTERSECTION-TYPE object.
449 ;;; 3. There are never any UNION-TYPE components. Either we should
450 ;;; use the distributive rule to rearrange things so that
451 ;;; unions contain intersections and not vice versa, or we
452 ;;; should just punt to using a HAIRY-TYPE.
453 (defstruct (intersection-type (:include compound-type
454 (class-info (type-class-or-lose
456 (:constructor %make-intersection-type
460 ;;; Return TYPE converted to canonical form for a situation where the
461 ;;; "type" '* (which SBCL still represents as a type even though ANSI
462 ;;; CL defines it as a related but different kind of placeholder) is
463 ;;; equivalent to type T.
464 (defun type-*-to-t
(type)
465 (if (type= type
*wild-type
*)
469 ;;; A CONS-TYPE is used to represent a CONS type.
470 (defstruct (cons-type (:include ctype
(class-info (type-class-or-lose 'cons
)))
472 %make-cons-type
(car-type
475 ;; the CAR and CDR element types (to support ANSI (CONS FOO BAR) types)
477 ;; FIXME: Most or all other type structure slots could also be :READ-ONLY.
478 (car-type (missing-arg) :type ctype
:read-only t
)
479 (cdr-type (missing-arg) :type ctype
:read-only t
))
480 (defun make-cons-type (car-type cdr-type
)
481 (aver (not (or (eq car-type
*wild-type
*)
482 (eq cdr-type
*wild-type
*))))
483 (if (or (eq car-type
*empty-type
*)
484 (eq cdr-type
*empty-type
*))
486 (%make-cons-type car-type cdr-type
)))
488 (defun cons-type-length-info (type)
489 (declare (type cons-type type
))
490 (do ((min 1 (1+ min
))
491 (cdr (cons-type-cdr-type type
) (cons-type-cdr-type cdr
)))
492 ((not (cons-type-p cdr
))
494 ((csubtypep cdr
(specifier-type 'null
))
496 ((csubtypep *universal-type
* cdr
)
498 ((type/= (type-intersection (specifier-type 'cons
) cdr
) *empty-type
*)
500 ((type/= (type-intersection (specifier-type 'null
) cdr
) *empty-type
*)
502 (t (values min
:maybe
))))
508 ;;; Return the type structure corresponding to a type specifier. We
509 ;;; pick off structure types as a special case.
511 ;;; Note: VALUES-SPECIFIER-TYPE-CACHE-CLEAR must be called whenever a
512 ;;; type is defined (or redefined).
513 (defun-cached (values-specifier-type
514 :hash-function
(lambda (x)
515 (logand (sxhash x
) #x3FF
))
517 :init-wrapper
!cold-init-forms
)
518 ((orig equal-but-no-car-recursion
))
519 (let ((u (uncross orig
)))
520 (or (info :type
:builtin u
)
521 (let ((spec (type-expand u
)))
523 ((and (not (eq spec u
))
524 (info :type
:builtin spec
)))
525 ((eq (info :type
:kind spec
) :instance
)
526 (find-classoid spec
))
527 ((typep spec
'classoid
)
528 ;; There doesn't seem to be any way to translate
529 ;; (TYPEP SPEC 'BUILT-IN-CLASS) into something which can be
530 ;; executed on the host Common Lisp at cross-compilation time.
532 "stub: (TYPEP SPEC 'BUILT-IN-CLASS) on xc host")
533 (if (typep spec
'built-in-classoid
)
534 (or (built-in-classoid-translation spec
) spec
)
537 (when (and (atom spec
)
538 (member spec
'(and or not member eql satisfies values
)))
539 (error "The symbol ~S is not valid as a type specifier." spec
))
540 (let* ((lspec (if (atom spec
) (list spec
) spec
))
541 (fun (info :type
:translator
(car lspec
))))
544 ((or (and (consp spec
) (symbolp (car spec
))
545 (not (info :type
:builtin
(car spec
))))
546 (and (symbolp spec
) (not (info :type
:builtin spec
))))
547 (when (and *type-system-initialized
*
548 (not (eq (info :type
:kind spec
)
549 :forthcoming-defclass-type
)))
550 (signal 'parse-unknown-type
:specifier spec
))
551 ;; (The RETURN-FROM here inhibits caching.)
552 (return-from values-specifier-type
553 (make-unknown-type :specifier spec
)))
555 (error "bad thing to be a type specifier: ~S"
558 ;;; This is like VALUES-SPECIFIER-TYPE, except that we guarantee to
559 ;;; never return a VALUES type.
560 (defun specifier-type (x)
561 (let ((res (values-specifier-type x
)))
562 (when (or (values-type-p res
)
563 ;; bootstrap magic :-(
564 (and (named-type-p res
)
565 (eq (named-type-name res
) '*)))
566 (error "VALUES type illegal in this context:~% ~S" x
))
569 (defun single-value-specifier-type (x)
574 ;;; Similar to MACROEXPAND, but expands DEFTYPEs. We don't bother
575 ;;; returning a second value.
576 (defun type-expand (form)
577 (let ((def (cond ((symbolp form
)
578 (info :type
:expander form
))
579 ((and (consp form
) (symbolp (car form
)))
580 (info :type
:expander
(car form
)))
583 (type-expand (funcall def
(if (consp form
) form
(list form
))))
586 ;;; Note that the type NAME has been (re)defined, updating the
587 ;;; undefined warnings and VALUES-SPECIFIER-TYPE cache.
588 (defun %note-type-defined
(name)
589 (declare (symbol name
))
590 (note-name-defined name
:type
)
591 (when (boundp 'sb
!kernel
::*values-specifier-type-cache-vector
*)
592 (values-specifier-type-cache-clear))
596 (!defun-from-collected-cold-init-forms
!early-type-cold-init
)