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 &optional keyp)
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)))
75 ((and (not keyp) (neq opt rest))
76 (setq last-not-rest i)))
77 finally (return (values required
81 (subseq optional 0 (1+ last-not-rest))))
84 (defun parse-args-types (lambda-list-like-thing)
86 (required optional restp rest keyp keys allowp auxp aux
87 morep more-context more-count llk-p)
88 (parse-lambda-list-like-thing lambda-list-like-thing :silent t)
89 (declare (ignore aux morep more-context more-count))
91 (error "&AUX in a FUNCTION or VALUES type: ~S." lambda-list-like-thing))
92 (let ((required (mapcar #'single-value-specifier-type required))
93 (optional (mapcar #'single-value-specifier-type optional))
94 (rest (when restp (single-value-specifier-type rest)))
98 (unless (proper-list-of-length-p key 2)
99 (error "Keyword type description is not a two-list: ~S." key))
100 (let ((kwd (first key)))
101 (when (find kwd (key-info) :key #'key-info-name)
102 (error "~@<repeated keyword ~S in lambda list: ~2I~_~S~:>"
103 kwd lambda-list-like-thing))
107 :type (single-value-specifier-type (second key))))))
109 (multiple-value-bind (required optional rest)
110 (canonicalize-args-type-args required optional rest keyp)
111 (values required optional rest keyp keywords allowp llk-p)))))
113 (defstruct (values-type
115 (class-info (type-class-or-lose 'values)))
116 (:constructor %make-values-type)
119 (defun-cached (make-values-type-cached
121 :hash-function (lambda (req opt rest allowp)
123 (type-list-cache-hash req)
124 (type-list-cache-hash opt)
126 (type-hash-value rest)
130 ((required equal-but-no-car-recursion)
131 (optional equal-but-no-car-recursion)
134 (%make-values-type :required required
139 (defun make-values-type (&key required optional rest allowp)
140 (multiple-value-bind (required optional rest)
141 (canonicalize-args-type-args required optional rest)
142 (cond ((and (null required)
144 (eq rest *universal-type*))
146 ((memq *empty-type* required)
148 (t (make-values-type-cached required optional
151 (!define-type-class values)
153 ;;; (SPECIFIER-TYPE 'FUNCTION) and its subtypes
154 (defstruct (fun-type (:include args-type
155 (class-info (type-class-or-lose 'function)))
157 make-fun-type (&key required optional rest
161 &aux (rest (if (eq rest *empty-type*)
164 ;; true if the arguments are unrestrictive, i.e. *
165 (wild-args nil :type boolean)
166 ;; type describing the return values. This is a values type
167 ;; when multiple values were specified for the return.
168 (returns (missing-arg) :type ctype))
170 ;;; The CONSTANT-TYPE structure represents a use of the CONSTANT-ARG
171 ;;; "type specifier", which is only meaningful in function argument
172 ;;; type specifiers used within the compiler. (It represents something
173 ;;; that the compiler knows to be a constant.)
174 (defstruct (constant-type
176 (class-info (type-class-or-lose 'constant)))
178 ;; The type which the argument must be a constant instance of for this type
180 (type (missing-arg) :type ctype))
182 ;;; The NAMED-TYPE is used to represent *, T and NIL, the standard
183 ;;; special cases, as well as other special cases needed to
184 ;;; interpolate between regions of the type hierarchy, such as
185 ;;; INSTANCE (which corresponds to all those classes with slots which
186 ;;; are not funcallable), FUNCALLABLE-INSTANCE (those classes with
187 ;;; slots which are funcallable) and EXTENDED-SEQUUENCE (non-LIST
188 ;;; non-VECTOR classes which are also sequences). These special cases
189 ;;; are the ones that aren't really discussed by Baker in his
190 ;;; "Decision Procedure for SUBTYPEP" paper.
191 (defstruct (named-type (:include ctype
192 (class-info (type-class-or-lose 'named)))
194 (name nil :type symbol))
196 ;;; a list of all the float "formats" (i.e. internal representations;
197 ;;; nothing to do with #'FORMAT), in order of decreasing precision
198 (eval-when (:compile-toplevel :load-toplevel :execute)
199 (defparameter *float-formats*
200 '(long-float double-float single-float short-float)))
202 ;;; The type of a float format.
203 (deftype float-format () `(member ,@*float-formats*))
205 ;;; A NUMERIC-TYPE represents any numeric type, including things
207 (defstruct (numeric-type (:include ctype
208 (class-info (type-class-or-lose 'number)))
209 (:constructor %make-numeric-type)
211 ;; the kind of numeric type we have, or NIL if not specified (just
212 ;; NUMBER or COMPLEX)
214 ;; KLUDGE: A slot named CLASS for a non-CLASS value is bad.
215 ;; Especially when a CLASS value *is* stored in another slot (called
216 ;; CLASS-INFO:-). Perhaps this should be called CLASS-NAME? Also
217 ;; weird that comment above says "Numeric-Type is used to represent
218 ;; all numeric types" but this slot doesn't allow COMPLEX as an
219 ;; option.. how does this fall into "not specified" NIL case above?
220 ;; Perhaps someday we can switch to CLOS and make NUMERIC-TYPE
221 ;; be an abstract base class and INTEGER-TYPE, RATIONAL-TYPE, and
222 ;; whatnot be concrete subclasses..
223 (class nil :type (member integer rational float nil) :read-only t)
224 ;; "format" for a float type (i.e. type specifier for a CPU
225 ;; representation of floating point, e.g. 'SINGLE-FLOAT -- nothing
226 ;; to do with #'FORMAT), or NIL if not specified or not a float.
227 ;; Formats which don't exist in a given implementation don't appear
229 (format nil :type (or float-format null) :read-only t)
230 ;; Is this a complex numeric type? Null if unknown (only in NUMBER).
232 ;; FIXME: I'm bewildered by FOO-P names for things not intended to
233 ;; interpreted as truth values. Perhaps rename this COMPLEXNESS?
234 (complexp :real :type (member :real :complex nil) :read-only t)
235 ;; The upper and lower bounds on the value, or NIL if there is no
236 ;; bound. If a list of a number, the bound is exclusive. Integer
237 ;; types never have exclusive bounds, i.e. they may have them on
238 ;; input, but they're canonicalized to inclusive bounds before we
240 (low nil :type (or number cons null) :read-only t)
241 (high nil :type (or number cons null) :read-only t))
243 ;;; Impose canonicalization rules for NUMERIC-TYPE. Note that in some
244 ;;; cases, despite the name, we return *EMPTY-TYPE* instead of a
246 (defun make-numeric-type (&key class format (complexp :real) low high
248 ;; if interval is empty
251 (if (or (consp low) (consp high)) ; if either bound is exclusive
252 (>= (type-bound-number low) (type-bound-number high))
255 (multiple-value-bind (canonical-low canonical-high)
258 ;; INTEGER types always have their LOW and HIGH bounds
259 ;; represented as inclusive, not exclusive values.
260 (values (if (consp low)
261 (1+ (type-bound-number low))
264 (1- (type-bound-number high))
267 ;; no canonicalization necessary
269 (when (and (eq class 'rational)
270 (integerp canonical-low)
271 (integerp canonical-high)
272 (= canonical-low canonical-high))
273 (setf class 'integer))
274 (%make-numeric-type :class class
279 :enumerable enumerable))))
281 (defun modified-numeric-type (base
283 (class (numeric-type-class base))
284 (format (numeric-type-format base))
285 (complexp (numeric-type-complexp base))
286 (low (numeric-type-low base))
287 (high (numeric-type-high base))
288 (enumerable (numeric-type-enumerable base)))
289 (make-numeric-type :class class
294 :enumerable enumerable))
296 (defstruct (character-set-type
298 (class-info (type-class-or-lose 'character-set)))
299 (:constructor %make-character-set-type)
301 (pairs (missing-arg) :type list :read-only t))
302 (defun make-character-set-type (&key pairs)
303 ; (aver (equal (mapcar #'car pairs)
304 ; (sort (mapcar #'car pairs) #'<)))
305 ;; aver that the cars of the list elements are sorted into increasing order
306 (aver (or (null pairs)
307 (do ((p pairs (cdr p)))
309 (when (> (caar p) (caadr p)) (return nil)))))
310 (let ((pairs (let (result)
311 (do ((pairs pairs (cdr pairs)))
312 ((null pairs) (nreverse result))
313 (destructuring-bind (low . high) (car pairs)
314 (loop for (low1 . high1) in (cdr pairs)
315 if (<= low1 (1+ high))
316 do (progn (setf high (max high high1))
317 (setf pairs (cdr pairs)))
318 else do (return nil))
320 ((>= low sb!xc:char-code-limit))
322 (t (push (cons (max 0 low)
323 (min high (1- sb!xc:char-code-limit)))
327 (%make-character-set-type :pairs pairs))))
329 ;;; An ARRAY-TYPE is used to represent any array type, including
330 ;;; things such as SIMPLE-BASE-STRING.
331 (defstruct (array-type (:include ctype
332 (class-info (type-class-or-lose 'array)))
333 (:constructor %make-array-type)
335 ;; the dimensions of the array, or * if unspecified. If a dimension
336 ;; is unspecified, it is *.
337 (dimensions '* :type (or list (member *)))
338 ;; Is this not a simple array type? (:MAYBE means that we don't know.)
339 (complexp :maybe :type (member t nil :maybe))
340 ;; the element type as originally specified
341 (element-type (missing-arg) :type ctype)
342 ;; the element type as it is specialized in this implementation
343 (specialized-element-type *wild-type* :type ctype))
344 (define-cached-synonym make-array-type)
346 ;;; A MEMBER-TYPE represent a use of the MEMBER type specifier. We
347 ;;; bother with this at this level because MEMBER types are fairly
348 ;;; important and union and intersection are well defined.
349 (defstruct (member-type (:include ctype
350 (class-info (type-class-or-lose 'member))
353 (:constructor %make-member-type (xset fp-zeroes))
354 #-sb-xc-host (:pure nil))
355 (xset (missing-arg) :type xset)
356 (fp-zeroes (missing-arg) :type list))
357 (defun make-member-type (&key xset fp-zeroes members)
359 (aver (not fp-zeroes))
360 (setf xset (alloc-xset))
361 (dolist (elt members)
363 (pushnew elt fp-zeroes)
364 (add-to-xset elt xset))))
365 ;; if we have a pair of zeros (e.g. 0.0d0 and -0.0d0), then we can
366 ;; canonicalize to (DOUBLE-FLOAT 0.0d0 0.0d0), because numeric
367 ;; ranges are compared by arithmetic operators (while MEMBERship is
368 ;; compared by EQL). -- CSR, 2003-04-23
371 (do ((tail (cdr fp-zeroes) (cdr tail))
372 (zero (car fp-zeroes) (car tail)))
375 `(let ((neg (neg-fp-zero zero)))
376 (if (member neg tail)
377 (push (ctype-of ,c) union-types)
378 (push zero unpaired)))))
380 (single-float (frob 0.0f0))
381 (double-float (frob 0.0d0))
383 (long-float (frob 0.0l0)))))
384 ;; The actual member-type contains the XSET (with no FP zeroes),
385 ;; and a list of unpaired zeroes.
386 (let ((member-type (unless (and (xset-empty-p xset) (not unpaired))
387 (%make-member-type xset unpaired))))
389 (make-union-type t (if member-type
390 (cons member-type union-types)
397 (defun member-type-size (type)
398 (+ (length (member-type-fp-zeroes type))
399 (xset-count (member-type-xset type))))
401 (defun member-type-member-p (x type)
403 (and (member x (member-type-fp-zeroes type)) t)
404 (xset-member-p x (member-type-xset type))))
406 (defun mapcar-member-type-members (function type)
407 (declare (function function))
409 (map-xset (lambda (x)
410 (results (funcall function x)))
411 (member-type-xset type))
412 (dolist (zero (member-type-fp-zeroes type))
413 (results (funcall function zero)))
416 (defun mapc-member-type-members (function type)
417 (declare (function function))
418 (map-xset function (member-type-xset type))
419 (dolist (zero (member-type-fp-zeroes type))
420 (funcall function zero)))
422 (defun member-type-members (type)
423 (append (member-type-fp-zeroes type)
424 (xset-members (member-type-xset type))))
426 ;;; A COMPOUND-TYPE is a type defined out of a set of types, the
427 ;;; common parent of UNION-TYPE and INTERSECTION-TYPE.
428 (defstruct (compound-type (:include ctype
429 (might-contain-other-types-p t))
432 (types nil :type list :read-only t))
434 ;;; A UNION-TYPE represents a use of the OR type specifier which we
435 ;;; couldn't canonicalize to something simpler. Canonical form:
436 ;;; 1. All possible pairwise simplifications (using the UNION2 type
437 ;;; methods) have been performed. Thus e.g. there is never more
438 ;;; than one MEMBER-TYPE component. FIXME: As of sbcl-0.6.11.13,
439 ;;; this hadn't been fully implemented yet.
440 ;;; 2. There are never any UNION-TYPE components.
441 (defstruct (union-type (:include compound-type
442 (class-info (type-class-or-lose 'union)))
443 (:constructor %make-union-type (enumerable types))
445 (define-cached-synonym make-union-type)
447 ;;; An INTERSECTION-TYPE represents a use of the AND type specifier
448 ;;; which we couldn't canonicalize to something simpler. Canonical form:
449 ;;; 1. All possible pairwise simplifications (using the INTERSECTION2
450 ;;; type methods) have been performed. Thus e.g. there is never more
451 ;;; than one MEMBER-TYPE component.
452 ;;; 2. There are never any INTERSECTION-TYPE components: we've
453 ;;; flattened everything into a single INTERSECTION-TYPE object.
454 ;;; 3. There are never any UNION-TYPE components. Either we should
455 ;;; use the distributive rule to rearrange things so that
456 ;;; unions contain intersections and not vice versa, or we
457 ;;; should just punt to using a HAIRY-TYPE.
458 (defstruct (intersection-type (:include compound-type
459 (class-info (type-class-or-lose
461 (:constructor %make-intersection-type
465 ;;; Return TYPE converted to canonical form for a situation where the
466 ;;; "type" '* (which SBCL still represents as a type even though ANSI
467 ;;; CL defines it as a related but different kind of placeholder) is
468 ;;; equivalent to type T.
469 (defun type-*-to-t (type)
470 (if (type= type *wild-type*)
474 ;;; A CONS-TYPE is used to represent a CONS type.
475 (defstruct (cons-type (:include ctype (class-info (type-class-or-lose 'cons)))
477 %make-cons-type (car-type
480 ;; the CAR and CDR element types (to support ANSI (CONS FOO BAR) types)
482 ;; FIXME: Most or all other type structure slots could also be :READ-ONLY.
483 (car-type (missing-arg) :type ctype :read-only t)
484 (cdr-type (missing-arg) :type ctype :read-only t))
485 (defun make-cons-type (car-type cdr-type)
486 (aver (not (or (eq car-type *wild-type*)
487 (eq cdr-type *wild-type*))))
488 (if (or (eq car-type *empty-type*)
489 (eq cdr-type *empty-type*))
491 (%make-cons-type car-type cdr-type)))
493 (defun cons-type-length-info (type)
494 (declare (type cons-type type))
495 (do ((min 1 (1+ min))
496 (cdr (cons-type-cdr-type type) (cons-type-cdr-type cdr)))
497 ((not (cons-type-p cdr))
499 ((csubtypep cdr (specifier-type 'null))
501 ((csubtypep *universal-type* cdr)
503 ((type/= (type-intersection (specifier-type 'cons) cdr) *empty-type*)
505 ((type/= (type-intersection (specifier-type 'null) cdr) *empty-type*)
507 (t (values min :maybe))))
513 ;;; Return the type structure corresponding to a type specifier. We
514 ;;; pick off structure types as a special case.
516 ;;; Note: VALUES-SPECIFIER-TYPE-CACHE-CLEAR must be called whenever a
517 ;;; type is defined (or redefined).
518 (defun-cached (values-specifier-type
519 :hash-function (lambda (x)
520 (logand (sxhash x) #x3FF))
522 :init-wrapper !cold-init-forms)
523 ((orig equal-but-no-car-recursion))
524 (let ((u (uncross orig)))
525 (or (info :type :builtin u)
526 (let ((spec (type-expand u)))
528 ((and (not (eq spec u))
529 (info :type :builtin spec)))
530 ((eq (info :type :kind spec) :instance)
531 (find-classoid spec))
532 ((typep spec 'classoid)
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)