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 (eq rest *empty-type*)
  72     ;; or vice-versa?
  73     (setq rest nil))
  74   (loop with last-not-rest = nil
  75         for i from 0
  76         for opt in optional
  77         do (cond ((eq opt *empty-type*)
  78                   (return (values required (subseq optional i) rest)))
  79                  ((neq opt rest)
  80                   (setq last-not-rest i)))
  81         finally (return (values required
  82                                 (if last-not-rest
  83                                     (subseq optional 0 (1+ last-not-rest))
  84                                     nil)
  85                                 rest))))
  86
  87 (defun args-types (lambda-list-like-thing)
  88   (multiple-value-bind
  89         (required optional restp rest keyp keys allowp auxp aux
  90                   morep more-context more-count llk-p)
  91       (parse-lambda-list-like-thing lambda-list-like-thing)
  92     (declare (ignore aux morep more-context more-count))
  93     (when auxp
  94       (error "&AUX in a FUNCTION or VALUES type: ~S." lambda-list-like-thing))
  95     (let ((required (mapcar #'single-value-specifier-type required))
  96           (optional (mapcar #'single-value-specifier-type optional))
  97           (rest (when restp (single-value-specifier-type rest)))
  98           (keywords
  99            (collect ((key-info))
 100              (dolist (key keys)
 101                (unless (proper-list-of-length-p key 2)
 102                  (error "Keyword type description is not a two-list: ~S." key))
 103                (let ((kwd (first key)))
 104                  (when (find kwd (key-info) :key #'key-info-name)
 105                    (error "~@<repeated keyword ~S in lambda list: ~2I~_~S~:>"
 106                           kwd lambda-list-like-thing))
 107                  (key-info
 108                   (make-key-info
 109                    :name kwd
 110                    :type (single-value-specifier-type (second key))))))
 111              (key-info))))
 112       (multiple-value-bind (required optional rest)
 113           (canonicalize-args-type-args required optional rest)
 114         (values required optional rest keyp keywords allowp llk-p)))))
 115
 116 (defstruct (values-type
 117             (:include args-type
 118                       (class-info (type-class-or-lose 'values)))
 119             (:constructor %make-values-type)
 120             (:copier nil)))
 121
 122 (defun-cached (make-values-type-cached
 123                :hash-bits 8
 124                :hash-function (lambda (req opt rest allowp)
 125                                 (logand (logxor
 126                                          (type-list-cache-hash req)
 127                                          (type-list-cache-hash opt)
 128                                          (if rest
 129                                              (type-hash-value rest)
 130                                              42)
 131                                          (sxhash allowp))
 132                                         #xFF)))
 133     ((required equal-but-no-car-recursion)
 134      (optional equal-but-no-car-recursion)
 135      (rest eq)
 136      (allowp eq))
 137   (%make-values-type :required required
 138                      :optional optional
 139                      :rest rest
 140                      :allowp allowp))
 141
 142 (defun make-values-type (&key (args nil argsp)
 143                          required optional rest allowp)
 144   (if argsp
 145       (if (eq args '*)
 146           *wild-type*
 147           (multiple-value-bind (required optional rest keyp keywords allowp
 148                                 llk-p)
 149               (args-types args)
 150             (declare (ignore keywords))
 151             (when keyp
 152               (error "&KEY appeared in a VALUES type specifier ~S."
 153                      `(values ,@args)))
 154             (if llk-p
 155                 (make-values-type :required required
 156                                   :optional optional
 157                                   :rest rest
 158                                   :allowp allowp)
 159                 (make-short-values-type required))))
 160       (multiple-value-bind (required optional rest)
 161           (canonicalize-args-type-args required optional rest)
 162         (cond ((and (null required)
 163                     (null optional)
 164                     (eq rest *universal-type*))
 165                *wild-type*)
 166               ((memq *empty-type* required)
 167                *empty-type*)
 168               (t (make-values-type-cached required optional
 169                                           rest allowp))))))
 170
 171 (!define-type-class values)
 172
 173 ;;; (SPECIFIER-TYPE 'FUNCTION) and its subtypes
 174 (defstruct (fun-type (:include args-type
 175                                (class-info (type-class-or-lose 'function)))
 176                      (:constructor
 177                       %make-fun-type (&key required optional rest
 178                                            keyp keywords allowp
 179                                            wild-args
 180                                            returns
 181                                       &aux (rest (if (eq rest *empty-type*)
 182                                                      nil
 183                                                      rest)))))
 184   ;; true if the arguments are unrestrictive, i.e. *
 185   (wild-args nil :type boolean)
 186   ;; type describing the return values. This is a values type
 187   ;; when multiple values were specified for the return.
 188   (returns (missing-arg) :type ctype))
 189 (defun make-fun-type (&rest initargs
 190                       &key (args nil argsp) returns &allow-other-keys)
 191   (if argsp
 192       (if (eq args '*)
 193           (if (eq returns *wild-type*)
 194               (specifier-type 'function)
 195               (%make-fun-type :wild-args t :returns returns))
 196           (multiple-value-bind (required optional rest keyp keywords allowp)
 197               (args-types args)
 198             (if (and (null required)
 199                      (null optional)
 200                      (eq rest *universal-type*)
 201                      (not keyp))
 202                 (if (eq returns *wild-type*)
 203                     (specifier-type 'function)
 204                     (%make-fun-type :wild-args t :returns returns))
 205                 (%make-fun-type :required required
 206                                 :optional optional
 207                                 :rest rest
 208                                 :keyp keyp
 209                                 :keywords keywords
 210                                 :allowp allowp
 211                                 :returns returns))))
 212       ;; FIXME: are we really sure that we won't make something that
 213       ;; looks like a completely wild function here?
 214       (apply #'%make-fun-type initargs)))
 215
 216 ;;; The CONSTANT-TYPE structure represents a use of the CONSTANT-ARG
 217 ;;; "type specifier", which is only meaningful in function argument
 218 ;;; type specifiers used within the compiler. (It represents something
 219 ;;; that the compiler knows to be a constant.)
 220 (defstruct (constant-type
 221             (:include ctype
 222                       (class-info (type-class-or-lose 'constant)))
 223             (:copier nil))
 224   ;; The type which the argument must be a constant instance of for this type
 225   ;; specifier to win.
 226   (type (missing-arg) :type ctype))
 227
 228 ;;; The NAMED-TYPE is used to represent *, T and NIL. These types must
 229 ;;; be super- or sub-types of all types, not just classes and * and
 230 ;;; NIL aren't classes anyway, so it wouldn't make much sense to make
 231 ;;; them built-in classes.
 232 (defstruct (named-type (:include ctype
 233                                  (class-info (type-class-or-lose 'named)))
 234                        (:copier nil))
 235   (name nil :type symbol))
 236
 237 ;;; a list of all the float "formats" (i.e. internal representations;
 238 ;;; nothing to do with #'FORMAT), in order of decreasing precision
 239 (eval-when (:compile-toplevel :load-toplevel :execute)
 240   (defparameter *float-formats*
 241     '(long-float double-float single-float short-float)))
 242
 243 ;;; The type of a float format.
 244 (deftype float-format () `(member ,@*float-formats*))
 245
 246 ;;; A NUMERIC-TYPE represents any numeric type, including things
 247 ;;; such as FIXNUM.
 248 (defstruct (numeric-type (:include ctype
 249                                    (class-info (type-class-or-lose 'number)))
 250                          (:constructor %make-numeric-type)
 251                          (:copier nil))
 252   ;; the kind of numeric type we have, or NIL if not specified (just
 253   ;; NUMBER or COMPLEX)
 254   ;;
 255   ;; KLUDGE: A slot named CLASS for a non-CLASS value is bad.
 256   ;; Especially when a CLASS value *is* stored in another slot (called
 257   ;; CLASS-INFO:-). Perhaps this should be called CLASS-NAME? Also
 258   ;; weird that comment above says "Numeric-Type is used to represent
 259   ;; all numeric types" but this slot doesn't allow COMPLEX as an
 260   ;; option.. how does this fall into "not specified" NIL case above?
 261   ;; Perhaps someday we can switch to CLOS and make NUMERIC-TYPE
 262   ;; be an abstract base class and INTEGER-TYPE, RATIONAL-TYPE, and
 263   ;; whatnot be concrete subclasses..
 264   (class nil :type (member integer rational float nil) :read-only t)
 265   ;; "format" for a float type (i.e. type specifier for a CPU
 266   ;; representation of floating point, e.g. 'SINGLE-FLOAT -- nothing
 267   ;; to do with #'FORMAT), or NIL if not specified or not a float.
 268   ;; Formats which don't exist in a given implementation don't appear
 269   ;; here.
 270   (format nil :type (or float-format null) :read-only t)
 271   ;; Is this a complex numeric type?  Null if unknown (only in NUMBER).
 272   ;;
 273   ;; FIXME: I'm bewildered by FOO-P names for things not intended to
 274   ;; interpreted as truth values. Perhaps rename this COMPLEXNESS?
 275   (complexp :real :type (member :real :complex nil) :read-only t)
 276   ;; The upper and lower bounds on the value, or NIL if there is no
 277   ;; bound. If a list of a number, the bound is exclusive. Integer
 278   ;; types never have exclusive bounds, i.e. they may have them on
 279   ;; input, but they're canonicalized to inclusive bounds before we
 280   ;; store them here.
 281   (low nil :type (or number cons null) :read-only t)
 282   (high nil :type (or number cons null) :read-only t))
 283
 284 ;;; Impose canonicalization rules for NUMERIC-TYPE. Note that in some
 285 ;;; cases, despite the name, we return *EMPTY-TYPE* instead of a
 286 ;;; NUMERIC-TYPE.
 287 (defun make-numeric-type (&key class format (complexp :real) low high
 288                                enumerable)
 289   ;; if interval is empty
 290   (if (and low
 291            high
 292            (if (or (consp low) (consp high)) ; if either bound is exclusive
 293                (>= (type-bound-number low) (type-bound-number high))
 294                (> low high)))
 295       *empty-type*
 296       (multiple-value-bind (canonical-low canonical-high)
 297           (case class
 298             (integer
 299              ;; INTEGER types always have their LOW and HIGH bounds
 300              ;; represented as inclusive, not exclusive values.
 301              (values (if (consp low)
 302                          (1+ (type-bound-number low))
 303                          low)
 304                      (if (consp high)
 305                          (1- (type-bound-number high))
 306                          high)))
 307             (t
 308              ;; no canonicalization necessary
 309              (values low high)))
 310         (when (and (eq class 'rational)
 311                    (integerp canonical-low)
 312                    (integerp canonical-high)
 313                    (= canonical-low canonical-high))
 314           (setf class 'integer))
 315         (%make-numeric-type :class class
 316                             :format format
 317                             :complexp complexp
 318                             :low canonical-low
 319                             :high canonical-high
 320                             :enumerable enumerable))))
 321
 322 (defun modified-numeric-type (base
 323                               &key
 324                               (class      (numeric-type-class      base))
 325                               (format     (numeric-type-format     base))
 326                               (complexp   (numeric-type-complexp   base))
 327                               (low        (numeric-type-low        base))
 328                               (high       (numeric-type-high       base))
 329                               (enumerable (numeric-type-enumerable base)))
 330   (make-numeric-type :class class
 331                      :format format
 332                      :complexp complexp
 333                      :low low
 334                      :high high
 335                      :enumerable enumerable))
 336
 337 ;;; An ARRAY-TYPE is used to represent any array type, including
 338 ;;; things such as SIMPLE-STRING.
 339 (defstruct (array-type (:include ctype
 340                                  (class-info (type-class-or-lose 'array)))
 341                        (:constructor %make-array-type)
 342                        (:copier nil))
 343   ;; the dimensions of the array, or * if unspecified. If a dimension
 344   ;; is unspecified, it is *.
 345   (dimensions '* :type (or list (member *)))
 346   ;; Is this not a simple array type? (:MAYBE means that we don't know.)
 347   (complexp :maybe :type (member t nil :maybe))
 348   ;; the element type as originally specified
 349   (element-type (missing-arg) :type ctype)
 350   ;; the element type as it is specialized in this implementation
 351   (specialized-element-type *wild-type* :type ctype))
 352 (define-cached-synonym make-array-type)
 353
 354 ;;; A MEMBER-TYPE represent a use of the MEMBER type specifier. We
 355 ;;; bother with this at this level because MEMBER types are fairly
 356 ;;; important and union and intersection are well defined.
 357 (defstruct (member-type (:include ctype
 358                                   (class-info (type-class-or-lose 'member))
 359                                   (enumerable t))
 360                         (:copier nil)
 361                         (:constructor %make-member-type (members))
 362                         #-sb-xc-host (:pure nil))
 363   ;; the things in the set, with no duplications
 364   (members nil :type list))
 365 (defun make-member-type (&key members)
 366   (declare (type list members))
 367   ;; make sure that we've removed duplicates
 368   (aver (= (length members) (length (remove-duplicates members))))
 369   ;; if we have a pair of zeros (e.g. 0.0d0 and -0.0d0), then we can
 370   ;; canonicalize to (DOUBLE-FLOAT 0.0d0 0.0d0), because numeric
 371   ;; ranges are compared by arithmetic operators (while MEMBERship is
 372   ;; compared by EQL).  -- CSR, 2003-04-23
 373   (let ((singlep (subsetp `(,(load-time-value (make-unportable-float :single-float-negative-zero)) 0.0f0) members))
 374         (doublep (subsetp `(,(load-time-value (make-unportable-float :double-float-negative-zero)) 0.0d0) members))
 375         #!+long-float
 376         (longp (subsetp `(,(load-time-value (make-unportable-float :long-float-negative-zero)) 0.0l0) members)))
 377     (if (or singlep doublep #!+long-float longp)
 378         (let (union-types)
 379           (when singlep
 380             (push (ctype-of 0.0f0) union-types)
 381             (setf members (set-difference members `(,(load-time-value (make-unportable-float :single-float-negative-zero)) 0.0f0))))
 382           (when doublep
 383             (push (ctype-of 0.0d0) union-types)
 384             (setf members (set-difference members `(,(load-time-value (make-unportable-float :double-float-negative-zero)) 0.0d0))))
 385           #!+long-float
 386           (when longp
 387             (push (ctype-of 0.0l0) union-types)
 388             (setf members (set-difference members `(,(load-time-value (make-unportable-float :long-float-negative-zero)) 0.0l0))))
 389           (aver (not (null union-types)))
 390           (make-union-type t
 391                            (if (null members)
 392                                union-types
 393                                (cons (%make-member-type members)
 394                                      union-types))))
 395         (%make-member-type members))))
 396
 397 ;;; A COMPOUND-TYPE is a type defined out of a set of types, the
 398 ;;; common parent of UNION-TYPE and INTERSECTION-TYPE.
 399 (defstruct (compound-type (:include ctype
 400                                     (might-contain-other-types-p t))
 401                           (:constructor nil)
 402                           (:copier nil))
 403   (types nil :type list :read-only t))
 404
 405 ;;; A UNION-TYPE represents a use of the OR type specifier which we
 406 ;;; couldn't canonicalize to something simpler. Canonical form:
 407 ;;;   1. All possible pairwise simplifications (using the UNION2 type
 408 ;;;      methods) have been performed. Thus e.g. there is never more
 409 ;;;      than one MEMBER-TYPE component. FIXME: As of sbcl-0.6.11.13,
 410 ;;;      this hadn't been fully implemented yet.
 411 ;;;   2. There are never any UNION-TYPE components.
 412 (defstruct (union-type (:include compound-type
 413                                  (class-info (type-class-or-lose 'union)))
 414                        (:constructor %make-union-type (enumerable types))
 415                        (:copier nil)))
 416 (define-cached-synonym make-union-type)
 417
 418 ;;; An INTERSECTION-TYPE represents a use of the AND type specifier
 419 ;;; which we couldn't canonicalize to something simpler. Canonical form:
 420 ;;;   1. All possible pairwise simplifications (using the INTERSECTION2
 421 ;;;      type methods) have been performed. Thus e.g. there is never more
 422 ;;;      than one MEMBER-TYPE component.
 423 ;;;   2. There are never any INTERSECTION-TYPE components: we've
 424 ;;;      flattened everything into a single INTERSECTION-TYPE object.
 425 ;;;   3. There are never any UNION-TYPE components. Either we should
 426 ;;;      use the distributive rule to rearrange things so that
 427 ;;;      unions contain intersections and not vice versa, or we
 428 ;;;      should just punt to using a HAIRY-TYPE.
 429 (defstruct (intersection-type (:include compound-type
 430                                         (class-info (type-class-or-lose
 431                                                      'intersection)))
 432                               (:constructor %make-intersection-type
 433                                             (enumerable types))
 434                               (:copier nil)))
 435
 436 ;;; Return TYPE converted to canonical form for a situation where the
 437 ;;; "type" '* (which SBCL still represents as a type even though ANSI
 438 ;;; CL defines it as a related but different kind of placeholder) is
 439 ;;; equivalent to type T.
 440 (defun type-*-to-t (type)
 441   (if (type= type *wild-type*)
 442       *universal-type*
 443       type))
 444
 445 ;;; A CONS-TYPE is used to represent a CONS type.
 446 (defstruct (cons-type (:include ctype (class-info (type-class-or-lose 'cons)))
 447                       (:constructor
 448                        %make-cons-type (car-type
 449                                         cdr-type))
 450                       (:copier nil))
 451   ;; the CAR and CDR element types (to support ANSI (CONS FOO BAR) types)
 452   ;;
 453   ;; FIXME: Most or all other type structure slots could also be :READ-ONLY.
 454   (car-type (missing-arg) :type ctype :read-only t)
 455   (cdr-type (missing-arg) :type ctype :read-only t))
 456 (defun make-cons-type (car-type cdr-type)
 457   (aver (not (or (eq car-type *wild-type*)
 458                  (eq cdr-type *wild-type*))))
 459   (if (or (eq car-type *empty-type*)
 460           (eq cdr-type *empty-type*))
 461       *empty-type*
 462       (%make-cons-type car-type cdr-type)))
 463 \f
 464 ;;;; type utilities
 465
 466 ;;; Return the type structure corresponding to a type specifier. We
 467 ;;; pick off structure types as a special case.
 468 ;;;
 469 ;;; Note: VALUES-SPECIFIER-TYPE-CACHE-CLEAR must be called whenever a
 470 ;;; type is defined (or redefined).
 471 (defun-cached (values-specifier-type
 472                :hash-function (lambda (x)
 473                                 (logand (sxhash x) #x3FF))
 474                :hash-bits 10
 475                :init-wrapper !cold-init-forms)
 476               ((orig equal-but-no-car-recursion))
 477   (let ((u (uncross orig)))
 478     (or (info :type :builtin u)
 479         (let ((spec (type-expand u)))
 480           (cond
 481            ((and (not (eq spec u))
 482                  (info :type :builtin spec)))
 483            ((eq (info :type :kind spec) :instance)
 484             (find-classoid spec))
 485            ((typep spec 'classoid)
 486             ;; There doesn't seem to be any way to translate
 487             ;; (TYPEP SPEC 'BUILT-IN-CLASS) into something which can be
 488             ;; executed on the host Common Lisp at cross-compilation time.
 489             #+sb-xc-host (error
 490                           "stub: (TYPEP SPEC 'BUILT-IN-CLASS) on xc host")
 491             (if (typep spec 'built-in-classoid)
 492                 (or (built-in-classoid-translation spec) spec)
 493                 spec))
 494            (t
 495             (when (and (atom spec)
 496                        (member spec '(and or not member eql satisfies values)))
 497               (error "The symbol ~S is not valid as a type specifier." spec))
 498             (let* ((lspec (if (atom spec) (list spec) spec))
 499                    (fun (info :type :translator (car lspec))))
 500               (cond (fun
 501                      (funcall fun lspec))
 502                     ((or (and (consp spec) (symbolp (car spec)))
 503                          (symbolp spec))
 504                      (when (and *type-system-initialized*
 505                                 (not (eq (info :type :kind spec)
 506                                          :forthcoming-defclass-type)))
 507                        (signal 'parse-unknown-type :specifier spec))
 508                      ;; (The RETURN-FROM here inhibits caching.)
 509                      (return-from values-specifier-type
 510                        (make-unknown-type :specifier spec)))
 511                     (t
 512                      (error "bad thing to be a type specifier: ~S"
 513                             spec))))))))))
 514
 515 ;;; This is like VALUES-SPECIFIER-TYPE, except that we guarantee to
 516 ;;; never return a VALUES type.
 517 (defun specifier-type (x)
 518   (let ((res (values-specifier-type x)))
 519     (when (or (values-type-p res)
 520               ;; bootstrap magic :-(
 521               (and (named-type-p res)
 522                    (eq (named-type-name res) '*)))
 523       (error "VALUES type illegal in this context:~%  ~S" x))
 524     res))
 525
 526 (defun single-value-specifier-type (x)
 527   (if (eq x '*)
 528       *universal-type*
 529       (specifier-type x)))
 530
 531 ;;; Similar to MACROEXPAND, but expands DEFTYPEs. We don't bother
 532 ;;; returning a second value.
 533 (defun type-expand (form)
 534   (let ((def (cond ((symbolp form)
 535                     (info :type :expander form))
 536                    ((and (consp form) (symbolp (car form)))
 537                     (info :type :expander (car form)))
 538                    (t nil))))
 539     (if def
 540         (type-expand (funcall def (if (consp form) form (list form))))
 541         form)))
 542
 543 ;;; Note that the type NAME has been (re)defined, updating the
 544 ;;; undefined warnings and VALUES-SPECIFIER-TYPE cache.
 545 (defun %note-type-defined (name)
 546   (declare (symbol name))
 547   (note-name-defined name :type)
 548   (when (boundp 'sb!kernel::*values-specifier-type-cache-vector*)
 549     (values-specifier-type-cache-clear))
 550   (values))
 551
 552 \f
 553 (!defun-from-collected-cold-init-forms !early-type-cold-init)