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             #!+negative-zero-is-not-zero
 264             (float
 265              ;; Canonicalize a low bound of (-0.0) to 0.0, and a high
 266              ;; bound of (+0.0) to -0.0.
 267              (values (if (and (consp low)
 268                               (floatp (car low))
 269                               (zerop (car low))
 270                               (minusp (float-sign (car low))))
 271                          (float 0.0 (car low))
 272                          low)
 273                      (if (and (consp high)
 274                               (floatp (car high))
 275                               (zerop (car high))
 276                               (plusp (float-sign (car high))))
 277                          (float -0.0 (car high))
 278                          high)))
 279             (t
 280              ;; no canonicalization necessary
 281              (values low high)))
 282         (when (and (eq class 'rational)
 283                    (integerp canonical-low)
 284                    (integerp canonical-high)
 285                    (= canonical-low canonical-high))
 286           (setf class 'integer))
 287         (%make-numeric-type :class class
 288                             :format format
 289                             :complexp complexp
 290                             :low canonical-low
 291                             :high canonical-high
 292                             :enumerable enumerable))))
 293
 294 (defun modified-numeric-type (base
 295                               &key
 296                               (class      (numeric-type-class      base))
 297                               (format     (numeric-type-format     base))
 298                               (complexp   (numeric-type-complexp   base))
 299                               (low        (numeric-type-low        base))
 300                               (high       (numeric-type-high       base))
 301                               (enumerable (numeric-type-enumerable base)))
 302   (make-numeric-type :class class
 303                      :format format
 304                      :complexp complexp
 305                      :low low
 306                      :high high
 307                      :enumerable enumerable))
 308
 309 ;;; An ARRAY-TYPE is used to represent any array type, including
 310 ;;; things such as SIMPLE-STRING.
 311 (defstruct (array-type (:include ctype
 312                                  (class-info (type-class-or-lose 'array)))
 313                        (:constructor %make-array-type)
 314                        (:copier nil))
 315   ;; the dimensions of the array, or * if unspecified. If a dimension
 316   ;; is unspecified, it is *.
 317   (dimensions '* :type (or list (member *)))
 318   ;; Is this not a simple array type? (:MAYBE means that we don't know.)
 319   (complexp :maybe :type (member t nil :maybe))
 320   ;; the element type as originally specified
 321   (element-type (missing-arg) :type ctype)
 322   ;; the element type as it is specialized in this implementation
 323   (specialized-element-type *wild-type* :type ctype))
 324 (define-cached-synonym make-array-type)
 325
 326 ;;; A MEMBER-TYPE represent a use of the MEMBER type specifier. We
 327 ;;; bother with this at this level because MEMBER types are fairly
 328 ;;; important and union and intersection are well defined.
 329 (defstruct (member-type (:include ctype
 330                                   (class-info (type-class-or-lose 'member))
 331                                   (enumerable t))
 332                         (:copier nil)
 333                         (:constructor %make-member-type (members))
 334                         #-sb-xc-host (:pure nil))
 335   ;; the things in the set, with no duplications
 336   (members nil :type list))
 337 (defun make-member-type (&key members)
 338   (declare (type list members))
 339   ;; make sure that we've removed duplicates
 340   (aver (= (length members) (length (remove-duplicates members))))
 341   ;; if we have a pair of zeros (e.g. 0.0d0 and -0.0d0), then we can
 342   ;; canonicalize to (DOUBLE-FLOAT 0.0d0 0.0d0), because numeric
 343   ;; ranges are compared by arithmetic operators (while MEMBERship is
 344   ;; compared by EQL).  -- CSR, 2003-04-23
 345   (let ((singlep (subsetp '(-0.0f0 0.0f0) members))
 346         (doublep (subsetp '(-0.0d0 0.0d0) members))
 347         #!+long-float
 348         (longp (subsetp '(-0.0l0 0.0l0) members)))
 349     (if (or singlep doublep #!+long-float longp)
 350         (let (union-types)
 351           (when singlep
 352             (push (ctype-of 0.0f0) union-types)
 353             (setf members (set-difference members '(-0.0f0 0.0f0))))
 354           (when doublep
 355             (push (ctype-of 0.0d0) union-types)
 356             (setf members (set-difference members '(-0.0d0 0.0d0))))
 357           #!+long-float
 358           (when longp
 359             (push (ctype-of 0.0l0) union-types)
 360             (setf members (set-difference members '(-0.0l0 0.0l0))))
 361           (aver (not (null union-types)))
 362           (make-union-type t
 363                            (if (null members)
 364                                union-types
 365                                (cons (%make-member-type members)
 366                                      union-types))))
 367         (%make-member-type members))))
 368
 369 ;;; A COMPOUND-TYPE is a type defined out of a set of types, the
 370 ;;; common parent of UNION-TYPE and INTERSECTION-TYPE.
 371 (defstruct (compound-type (:include ctype
 372                                     (might-contain-other-types-p t))
 373                           (:constructor nil)
 374                           (:copier nil))
 375   (types nil :type list :read-only t))
 376
 377 ;;; A UNION-TYPE represents a use of the OR type specifier which we
 378 ;;; couldn't canonicalize to something simpler. Canonical form:
 379 ;;;   1. All possible pairwise simplifications (using the UNION2 type
 380 ;;;      methods) have been performed. Thus e.g. there is never more
 381 ;;;      than one MEMBER-TYPE component. FIXME: As of sbcl-0.6.11.13,
 382 ;;;      this hadn't been fully implemented yet.
 383 ;;;   2. There are never any UNION-TYPE components.
 384 (defstruct (union-type (:include compound-type
 385                                  (class-info (type-class-or-lose 'union)))
 386                        (:constructor %make-union-type (enumerable types))
 387                        (:copier nil)))
 388 (define-cached-synonym make-union-type)
 389
 390 ;;; An INTERSECTION-TYPE represents a use of the AND type specifier
 391 ;;; which we couldn't canonicalize to something simpler. Canonical form:
 392 ;;;   1. All possible pairwise simplifications (using the INTERSECTION2
 393 ;;;      type methods) have been performed. Thus e.g. there is never more
 394 ;;;      than one MEMBER-TYPE component.
 395 ;;;   2. There are never any INTERSECTION-TYPE components: we've
 396 ;;;      flattened everything into a single INTERSECTION-TYPE object.
 397 ;;;   3. There are never any UNION-TYPE components. Either we should
 398 ;;;      use the distributive rule to rearrange things so that
 399 ;;;      unions contain intersections and not vice versa, or we
 400 ;;;      should just punt to using a HAIRY-TYPE.
 401 (defstruct (intersection-type (:include compound-type
 402                                         (class-info (type-class-or-lose
 403                                                      'intersection)))
 404                               (:constructor %make-intersection-type
 405                                             (enumerable types))
 406                               (:copier nil)))
 407
 408 ;;; Return TYPE converted to canonical form for a situation where the
 409 ;;; "type" '* (which SBCL still represents as a type even though ANSI
 410 ;;; CL defines it as a related but different kind of placeholder) is
 411 ;;; equivalent to type T.
 412 (defun type-*-to-t (type)
 413   (if (type= type *wild-type*)
 414       *universal-type*
 415       type))
 416
 417 ;;; A CONS-TYPE is used to represent a CONS type.
 418 (defstruct (cons-type (:include ctype (class-info (type-class-or-lose 'cons)))
 419                       (:constructor
 420                        ;; ANSI says that for CAR and CDR subtype
 421                        ;; specifiers '* is equivalent to T. In order
 422                        ;; to avoid special cases in SUBTYPEP and
 423                        ;; possibly elsewhere, we slam all CONS-TYPE
 424                        ;; objects into canonical form w.r.t. this
 425                        ;; equivalence at creation time.
 426                        %make-cons-type (car-raw-type
 427                                         cdr-raw-type
 428                                         &aux
 429                                         (car-type (type-*-to-t car-raw-type))
 430                                         (cdr-type (type-*-to-t cdr-raw-type))))
 431                       (:copier nil))
 432   ;; the CAR and CDR element types (to support ANSI (CONS FOO BAR) types)
 433   ;;
 434   ;; FIXME: Most or all other type structure slots could also be :READ-ONLY.
 435   (car-type (missing-arg) :type ctype :read-only t)
 436   (cdr-type (missing-arg) :type ctype :read-only t))
 437 (defun make-cons-type (car-type cdr-type)
 438   (if (or (eq car-type *empty-type*)
 439           (eq cdr-type *empty-type*))
 440       *empty-type*
 441       (%make-cons-type car-type cdr-type)))
 442 \f
 443 ;;;; type utilities
 444
 445 ;;; Return the type structure corresponding to a type specifier. We
 446 ;;; pick off structure types as a special case.
 447 ;;;
 448 ;;; Note: VALUES-SPECIFIER-TYPE-CACHE-CLEAR must be called whenever a
 449 ;;; type is defined (or redefined).
 450 (defun-cached (values-specifier-type
 451                :hash-function (lambda (x)
 452                                 (logand (sxhash x) #x3FF))
 453                :hash-bits 10
 454                :init-wrapper !cold-init-forms)
 455               ((orig equal-but-no-car-recursion))
 456   (let ((u (uncross orig)))
 457     (or (info :type :builtin u)
 458         (let ((spec (type-expand u)))
 459           (cond
 460            ((and (not (eq spec u))
 461                  (info :type :builtin spec)))
 462            ((eq (info :type :kind spec) :instance)
 463             (find-classoid spec))
 464            ((typep spec 'classoid)
 465             ;; There doesn't seem to be any way to translate
 466             ;; (TYPEP SPEC 'BUILT-IN-CLASS) into something which can be
 467             ;; executed on the host Common Lisp at cross-compilation time.
 468             #+sb-xc-host (error
 469                           "stub: (TYPEP SPEC 'BUILT-IN-CLASS) on xc host")
 470             (if (typep spec 'built-in-classoid)
 471                 (or (built-in-classoid-translation spec) spec)
 472                 spec))
 473            (t
 474             (let* (;; FIXME: This automatic promotion of FOO-style
 475                    ;; specs to (FOO)-style specs violates the ANSI
 476                    ;; standard. Unfortunately, we can't fix the
 477                    ;; problem just by removing it, since then things
 478                    ;; downstream should break. But at some point we
 479                    ;; should fix this and the things downstream too.
 480                    (lspec (if (atom spec) (list spec) spec))
 481                    (fun (info :type :translator (car lspec))))
 482               (cond (fun
 483                      (funcall fun lspec))
 484                     ((or (and (consp spec) (symbolp (car spec)))
 485                          (symbolp spec))
 486                      (when (and *type-system-initialized*
 487                                 (not (eq (info :type :kind spec)
 488                                          :forthcoming-defclass-type)))
 489                        (signal 'parse-unknown-type :specifier spec))
 490                      ;; (The RETURN-FROM here inhibits caching.)
 491                      (return-from values-specifier-type
 492                        (make-unknown-type :specifier spec)))
 493                     (t
 494                      (error "bad thing to be a type specifier: ~S"
 495                             spec))))))))))
 496
 497 ;;; This is like VALUES-SPECIFIER-TYPE, except that we guarantee to
 498 ;;; never return a VALUES type.
 499 (defun specifier-type (x)
 500   (let ((res (values-specifier-type x)))
 501     (when (values-type-p res)
 502       (error "VALUES type illegal in this context:~%  ~S" x))
 503     res))
 504
 505 (defun single-value-specifier-type (x)
 506   (let ((res (specifier-type x)))
 507     (if (eq res *wild-type*)
 508         *universal-type*
 509         res)))
 510
 511 ;;; Similar to MACROEXPAND, but expands DEFTYPEs. We don't bother
 512 ;;; returning a second value.
 513 (defun type-expand (form)
 514   (let ((def (cond ((symbolp form)
 515                     (info :type :expander form))
 516                    ((and (consp form) (symbolp (car form)))
 517                     (info :type :expander (car form)))
 518                    (t nil))))
 519     (if def
 520         (type-expand (funcall def (if (consp form) form (list form))))
 521         form)))
 522
 523 ;;; Note that the type NAME has been (re)defined, updating the
 524 ;;; undefined warnings and VALUES-SPECIFIER-TYPE cache.
 525 (defun %note-type-defined (name)
 526   (declare (symbol name))
 527   (note-name-defined name :type)
 528   (when (boundp 'sb!kernel::*values-specifier-type-cache-vector*)
 529     (values-specifier-type-cache-clear))
 530   (values))
 531 \f
 532 (!defun-from-collected-cold-init-forms !early-type-cold-init)