src/code/early-type.lisp

   1 ;;;; This software is part of the SBCL system. See the README file for
   2 ;;;; more information.
   3 ;;;;
   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.
   9
  10 (in-package "SB!KERNEL")
  11
  12 (!begin-collecting-cold-init-forms)
  13
  14 ;;;; representations of types
  15
  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))
  22                                  (enumerable t)
  23                                  (might-contain-other-types-p t))
  24                        (:copier nil)
  25                        #!+cmu (:pure nil))
  26   ;; the Common Lisp type-specifier of the type we represent
  27   (specifier nil :type t))
  28
  29 (!define-type-class hairy)
  30
  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)
  35                          (:copier nil)))
  36
  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
  41                                     (enumerable t)
  42                                     (might-contain-other-types-p t))
  43                           (:copier nil)
  44                           #!+cmu (:pure nil))
  45   (type (missing-arg) :type ctype))
  46
  47 (!define-type-class negation)
  48
  49 ;;; ARGS-TYPE objects are used both to represent VALUES types and
  50 ;;; to represent FUNCTION types.
  51 (defstruct (args-type (:include ctype)
  52                       (:constructor nil)
  53                       (:copier nil))
  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))
  65
  66 (defun canonicalize-args-type-args (required optional rest)
  67   (when (eq rest *empty-type*)
  68     ;; or vice-versa?
  69     (setq rest nil))
  70   (loop with last-not-rest = nil
  71         for i from 0
  72         for opt in optional
  73         do (cond ((eq opt *empty-type*)
  74                   (return (values required (subseq optional i) rest)))
  75                  ((neq opt rest)
  76                   (setq last-not-rest i)))
  77         finally (return (values required
  78                                 (if last-not-rest
  79                                     (subseq optional 0 (1+ last-not-rest))
  80                                     nil)
  81                                 rest))))
  82
  83 (defun args-types (lambda-list-like-thing)
  84   (multiple-value-bind
  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))
  89     (when auxp
  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)))
  94           (keywords
  95            (collect ((key-info))
  96              (dolist (key keys)
  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))
 103                  (key-info
 104                   (make-key-info
 105                    :name kwd
 106                    :type (single-value-specifier-type (second key))))))
 107              (key-info))))
 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)))))
 111
 112 (defstruct (values-type
 113             (:include args-type
 114                       (class-info (type-class-or-lose 'values)))
 115             (:constructor %make-values-type)
 116             (:copier nil)))
 117
 118 (defun-cached (make-values-type-cached
 119                :hash-bits 8
 120                :hash-function (lambda (req opt rest allowp)
 121                                 (logand (logxor
 122                                          (type-list-cache-hash req)
 123                                          (type-list-cache-hash opt)
 124                                          (if rest
 125                                              (type-hash-value rest)
 126                                              42)
 127                                          (sxhash allowp))
 128                                         #xFF)))
 129     ((required equal-but-no-car-recursion)
 130      (optional equal-but-no-car-recursion)
 131      (rest eq)
 132      (allowp eq))
 133   (%make-values-type :required required
 134                      :optional optional
 135                      :rest rest
 136                      :allowp allowp))
 137
 138 (defun make-values-type (&key (args nil argsp)
 139                          required optional rest allowp)
 140   (if argsp
 141       (if (eq args '*)
 142           *wild-type*
 143           (multiple-value-bind (required optional rest keyp keywords allowp
 144                                 llk-p)
 145               (args-types args)
 146             (declare (ignore keywords))
 147             (when keyp
 148               (error "&KEY appeared in a VALUES type specifier ~S."
 149                      `(values ,@args)))
 150             (if llk-p
 151                 (make-values-type :required required
 152                                   :optional optional
 153                                   :rest rest
 154                                   :allowp allowp)
 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)
 159                     (null optional)
 160                     (eq rest *universal-type*))
 161                *wild-type*)
 162               ((memq *empty-type* required)
 163                *empty-type*)
 164               (t (make-values-type-cached required optional
 165                                           rest allowp))))))
 166
 167 (!define-type-class values)
 168
 169 ;;; (SPECIFIER-TYPE 'FUNCTION) and its subtypes
 170 (defstruct (fun-type (:include args-type
 171                                (class-info (type-class-or-lose 'function)))
 172                      (:constructor
 173                       %make-fun-type (&key required optional rest
 174                                            keyp keywords allowp
 175                                            wild-args
 176                                            returns
 177                                       &aux (rest (if (eq rest *empty-type*)
 178                                                      nil
 179                                                      rest)))))
 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)
 187   (if argsp
 188       (if (eq args '*)
 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)
 193               (args-types args)
 194             (if (and (null required)
 195                      (null optional)
 196                      (eq rest *universal-type*)
 197                      (not keyp))
 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
 202                                 :optional optional
 203                                 :rest rest
 204                                 :keyp keyp
 205                                 :keywords keywords
 206                                 :allowp allowp
 207                                 :returns returns))))
 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)))
 211
 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
 217             (:include ctype
 218                       (class-info (type-class-or-lose 'constant)))
 219             (:copier nil))
 220   ;; The type which the argument must be a constant instance of for this type
 221   ;; specifier to win.
 222   (type (missing-arg) :type ctype))
 223
 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)))
 230                        (:copier nil))
 231   (name nil :type symbol))
 232
 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)))
 238
 239 ;;; The type of a float format.
 240 (deftype float-format () `(member ,@*float-formats*))
 241
 242 ;;; A NUMERIC-TYPE represents any numeric type, including things
 243 ;;; such as FIXNUM.
 244 (defstruct (numeric-type (:include ctype
 245                                    (class-info (type-class-or-lose 'number)))
 246                          (:constructor %make-numeric-type)
 247                          (:copier nil))
 248   ;; the kind of numeric type we have, or NIL if not specified (just
 249   ;; NUMBER or COMPLEX)
 250   ;;
 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
 265   ;; here.
 266   (format nil :type (or float-format null) :read-only t)
 267   ;; Is this a complex numeric type?  Null if unknown (only in NUMBER).
 268   ;;
 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
 276   ;; store them here.
 277   (low nil :type (or number cons null) :read-only t)
 278   (high nil :type (or number cons null) :read-only t))
 279
 280 ;;; Impose canonicalization rules for NUMERIC-TYPE. Note that in some
 281 ;;; cases, despite the name, we return *EMPTY-TYPE* instead of a
 282 ;;; NUMERIC-TYPE.
 283 (defun make-numeric-type (&key class format (complexp :real) low high
 284                                enumerable)
 285   ;; if interval is empty
 286   (if (and low
 287            high
 288            (if (or (consp low) (consp high)) ; if either bound is exclusive
 289                (>= (type-bound-number low) (type-bound-number high))
 290                (> low high)))
 291       *empty-type*
 292       (multiple-value-bind (canonical-low canonical-high)
 293           (case class
 294             (integer
 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))
 299                          low)
 300                      (if (consp high)
 301                          (1- (type-bound-number high))
 302                          high)))
 303             (t
 304              ;; no canonicalization necessary
 305              (values low high)))
 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
 312                             :format format
 313                             :complexp complexp
 314                             :low canonical-low
 315                             :high canonical-high
 316                             :enumerable enumerable))))
 317
 318 (defun modified-numeric-type (base
 319                               &key
 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
 327                      :format format
 328                      :complexp complexp
 329                      :low low
 330                      :high high
 331                      :enumerable enumerable))
 332
 333 (defstruct (character-set-type
 334             (:include ctype
 335                       (class-info (type-class-or-lose 'character-set)))
 336             (:constructor %make-character-set-type)
 337             (:copier nil))
 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))
 351                     (cond
 352                       ((>= low sb!xc:char-code-limit))
 353                       ((< high 0))
 354                       (t (push (cons (max 0 low)
 355                                      (min high (1- sb!xc:char-code-limit)))
 356                                result))))))))
 357     (if (null pairs)
 358        *empty-type*
 359        (%make-character-set-type :pairs pairs))))
 360
 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)
 366                        (:copier nil))
 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)
 377
 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))
 383                                   (enumerable t))
 384                         (:copier nil)
 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))
 399         #!+long-float
 400         (longp (subsetp `(,(load-time-value (make-unportable-float :long-float-negative-zero)) 0.0l0) members)))
 401     (if (or singlep doublep #!+long-float longp)
 402         (let (union-types)
 403           (when singlep
 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))))
 406           (when doublep
 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))))
 409           #!+long-float
 410           (when longp
 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)))
 414           (make-union-type t
 415                            (if (null members)
 416                                union-types
 417                                (cons (%make-member-type members)
 418                                      union-types))))
 419         (%make-member-type members))))
 420
 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))
 425                           (:constructor nil)
 426                           (:copier nil))
 427   (types nil :type list :read-only t))
 428
 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))
 439                        (:copier nil)))
 440 (define-cached-synonym make-union-type)
 441
 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
 455                                                      'intersection)))
 456                               (:constructor %make-intersection-type
 457                                             (enumerable types))
 458                               (:copier nil)))
 459
 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*)
 466       *universal-type*
 467       type))
 468
 469 ;;; A CONS-TYPE is used to represent a CONS type.
 470 (defstruct (cons-type (:include ctype (class-info (type-class-or-lose 'cons)))
 471                       (:constructor
 472                        %make-cons-type (car-type
 473                                         cdr-type))
 474                       (:copier nil))
 475   ;; the CAR and CDR element types (to support ANSI (CONS FOO BAR) types)
 476   ;;
 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*))
 485       *empty-type*
 486       (%make-cons-type car-type cdr-type)))
 487
 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))
 493        (cond
 494          ((csubtypep cdr (specifier-type 'null))
 495           (values min t))
 496          ((csubtypep *universal-type* cdr)
 497           (values min nil))
 498          ((type/= (type-intersection (specifier-type 'cons) cdr) *empty-type*)
 499           (values min nil))
 500          ((type/= (type-intersection (specifier-type 'null) cdr) *empty-type*)
 501           (values min t))
 502          (t (values min :maybe))))
 503     ()))
 504
 505 \f
 506 ;;;; type utilities
 507
 508 ;;; Return the type structure corresponding to a type specifier. We
 509 ;;; pick off structure types as a special case.
 510 ;;;
 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))
 516                :hash-bits 10
 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)))
 522           (cond
 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.
 531             #+sb-xc-host (error
 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)
 535                 spec))
 536            (t
 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))))
 542               (cond (fun
 543                      (funcall fun 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)))
 554                     (t
 555                      (error "bad thing to be a type specifier: ~S"
 556                             spec))))))))))
 557
 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))
 567     res))
 568
 569 (defun single-value-specifier-type (x)
 570   (if (eq x '*)
 571       *universal-type*
 572       (specifier-type x)))
 573
 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)))
 581                    (t nil))))
 582     (if def
 583         (type-expand (funcall def (if (consp form) form (list form))))
 584         form)))
 585
 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))
 593   (values))
 594
 595 \f
 596 (!defun-from-collected-cold-init-forms !early-type-cold-init)