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 ;;; Has the type system been properly initialized? (I.e. is it OK to
  15 ;;; use it?)
  16 (defvar *type-system-initialized* #+sb-xc-host nil) ; (set in cold load)
  17 \f
  18 ;;;; representations of types
  19
  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))
  26                                  (enumerable t)
  27                                  (might-contain-other-types-p t))
  28                        (:copier nil)
  29                        #!+cmu (:pure nil))
  30   ;; the Common Lisp type-specifier of the type we represent
  31   (specifier nil :type t))
  32
  33 (!define-type-class hairy)
  34
  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)
  39                          (:copier nil)))
  40
  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
  45                                     (enumerable t)
  46                                     (might-contain-other-types-p t))
  47                           (:copier nil)
  48                           #!+cmu (:pure nil))
  49   (type (missing-arg) :type ctype))
  50
  51 (!define-type-class negation)
  52
  53 ;;; ARGS-TYPE objects are used both to represent VALUES types and
  54 ;;; to represent FUNCTION types.
  55 (defstruct (args-type (:include ctype)
  56                       (:constructor nil)
  57                       (:copier nil))
  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))
  69
  70 (defun canonicalize-args-type-args (required optional rest)
  71   (when rest
  72     (let ((last-distinct-optional (position rest optional
  73                                             :from-end t
  74                                             :test-not #'type=)))
  75       (setf optional
  76             (when last-distinct-optional
  77               (subseq optional 0 (1+ last-distinct-optional))))))
  78   (values required optional rest))
  79
  80 (defun args-types (lambda-list-like-thing)
  81   (multiple-value-bind
  82         (required optional restp rest keyp keys allowp auxp aux)
  83       (parse-lambda-list-like-thing lambda-list-like-thing)
  84     (declare (ignore aux))
  85     (when auxp
  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)))
  90           (keywords
  91            (collect ((key-info))
  92              (dolist (key keys)
  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))
  99                  (key-info
 100                   (make-key-info
 101                    :name kwd
 102                    :type (single-value-specifier-type (second key))))))
 103              (key-info))))
 104       (multiple-value-bind (required optional rest)
 105           (canonicalize-args-type-args required optional rest)
 106         (values required optional rest keyp keywords allowp)))))
 107
 108 (defstruct (values-type
 109             (:include args-type
 110                       (class-info (type-class-or-lose 'values)))
 111             (:constructor %make-values-type)
 112             (:copier nil)))
 113
 114 (defun make-values-type (&rest initargs
 115                          &key (args nil argsp) &allow-other-keys)
 116   (if argsp
 117       (if (eq args '*)
 118           *wild-type*
 119           (multiple-value-bind (required optional rest keyp keywords allowp)
 120               (args-types args)
 121             (if (and (null required)
 122                      (null optional)
 123                      (eq rest *universal-type*)
 124                      (not keyp))
 125                 *wild-type*
 126                 (%make-values-type :required required
 127                                    :optional optional
 128                                    :rest rest
 129                                    :keyp keyp
 130                                    :keywords keywords
 131                                    :allowp allowp))))
 132       (apply #'%make-values-type initargs)))
 133
 134 (!define-type-class values)
 135
 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)
 147   (if argsp
 148       (if (eq args '*)
 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)
 153               (args-types args)
 154             (if (and (null required)
 155                      (null optional)
 156                      (eq rest *universal-type*)
 157                      (not keyp))
 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
 162                                 :optional optional
 163                                 :rest rest
 164                                 :keyp keyp
 165                                 :keywords keywords
 166                                 :allowp allowp
 167                                 :returns returns))))
 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)))
 171
 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
 177             (:include ctype
 178                       (class-info (type-class-or-lose 'constant)))
 179             (:copier nil))
 180   ;; The type which the argument must be a constant instance of for this type
 181   ;; specifier to win.
 182   (type (missing-arg) :type ctype))
 183
 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)))
 190                        (:copier nil))
 191   (name nil :type symbol))
 192
 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)))
 198
 199 ;;; The type of a float format.
 200 (deftype float-format () `(member ,@*float-formats*))
 201
 202 ;;; A NUMERIC-TYPE represents any numeric type, including things
 203 ;;; such as FIXNUM.
 204 (defstruct (numeric-type (:include ctype
 205                                    (class-info (type-class-or-lose 'number)))
 206                          (:constructor %make-numeric-type)
 207                          (:copier nil))
 208   ;; the kind of numeric type we have, or NIL if not specified (just
 209   ;; NUMBER or COMPLEX)
 210   ;;
 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
 225   ;; here.
 226   (format nil :type (or float-format null) :read-only t)
 227   ;; Is this a complex numeric type?  Null if unknown (only in NUMBER).
 228   ;;
 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
 236   ;; store them here.
 237   (low nil :type (or number cons null) :read-only t)
 238   (high nil :type (or number cons null) :read-only t))
 239
 240 ;;; Impose canonicalization rules for NUMERIC-TYPE. Note that in some
 241 ;;; cases, despite the name, we return *EMPTY-TYPE* instead of a
 242 ;;; NUMERIC-TYPE.
 243 (defun make-numeric-type (&key class format (complexp :real) low high
 244                                enumerable)
 245   ;; if interval is empty
 246   (if (and low
 247            high
 248            (if (or (consp low) (consp high)) ; if either bound is exclusive
 249                (>= (type-bound-number low) (type-bound-number high))
 250                (> low high)))
 251       *empty-type*
 252       (multiple-value-bind (canonical-low canonical-high)
 253           (case class
 254             (integer
 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))
 259                          low)
 260                      (if (consp high)
 261                          (1- (type-bound-number high))
 262                          high)))
 263             (t
 264              ;; no canonicalization necessary
 265              (values low high)))
 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
 272                             :format format
 273                             :complexp complexp
 274                             :low canonical-low
 275                             :high canonical-high
 276                             :enumerable enumerable))))
 277
 278 (defun modified-numeric-type (base
 279                               &key
 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
 287                      :format format
 288                      :complexp complexp
 289                      :low low
 290                      :high high
 291                      :enumerable enumerable))
 292
 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)
 298                        (:copier nil))
 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)
 309
 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))
 315                                   (enumerable t))
 316                         (:copier nil)
 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))
 331         #!+long-float
 332         (longp (subsetp `(,(load-time-value (make-unportable-float :long-float-negative-zero)) 0.0l0) members)))
 333     (if (or singlep doublep #!+long-float longp)
 334         (let (union-types)
 335           (when singlep
 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))))
 338           (when doublep
 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))))
 341           #!+long-float
 342           (when longp
 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)))
 346           (make-union-type t
 347                            (if (null members)
 348                                union-types
 349                                (cons (%make-member-type members)
 350                                      union-types))))
 351         (%make-member-type members))))
 352
 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))
 357                           (:constructor nil)
 358                           (:copier nil))
 359   (types nil :type list :read-only t))
 360
 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))
 371                        (:copier nil)))
 372 (define-cached-synonym make-union-type)
 373
 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
 387                                                      'intersection)))
 388                               (:constructor %make-intersection-type
 389                                             (enumerable types))
 390                               (:copier nil)))
 391
 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*)
 398       *universal-type*
 399       type))
 400
 401 ;;; A CONS-TYPE is used to represent a CONS type.
 402 (defstruct (cons-type (:include ctype (class-info (type-class-or-lose 'cons)))
 403                       (:constructor
 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
 411                                         cdr-raw-type
 412                                         &aux
 413                                         (car-type (type-*-to-t car-raw-type))
 414                                         (cdr-type (type-*-to-t cdr-raw-type))))
 415                       (:copier nil))
 416   ;; the CAR and CDR element types (to support ANSI (CONS FOO BAR) types)
 417   ;;
 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*))
 424       *empty-type*
 425       (%make-cons-type car-type cdr-type)))
 426 \f
 427 ;;;; type utilities
 428
 429 ;;; Return the type structure corresponding to a type specifier. We
 430 ;;; pick off structure types as a special case.
 431 ;;;
 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))
 437                :hash-bits 10
 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)))
 443           (cond
 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.
 452             #+sb-xc-host (error
 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)
 456                 spec))
 457            (t
 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))))
 466               (cond (fun
 467                      (funcall fun lspec))
 468                     ((or (and (consp spec) (symbolp (car spec)))
 469                          (symbolp 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)))
 477                     (t
 478                      (error "bad thing to be a type specifier: ~S"
 479                             spec))))))))))
 480
 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))
 487     res))
 488
 489 (defun single-value-specifier-type (x)
 490   (let ((res (specifier-type x)))
 491     (if (eq res *wild-type*)
 492         *universal-type*
 493         res)))
 494
 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)))
 502                    (t nil))))
 503     (if def
 504         (type-expand (funcall def (if (consp form) form (list form))))
 505         form)))
 506
 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))
 514   (values))
 515 \f
 516 (!defun-from-collected-cold-init-forms !early-type-cold-init)