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 (file-comment
  13   "$Header$")
  14
  15 (!begin-collecting-cold-init-forms)
  16
  17 ;;; Has the type system been properly initialized? (I.e. is it OK to
  18 ;;; use it?)
  19 (defvar *type-system-initialized* #+sb-xc-host nil) ; (set in cold load)
  20 \f
  21 ;;; Return the type structure corresponding to a type specifier. We
  22 ;;; pick off structure types as a special case.
  23 ;;;
  24 ;;; Note: VALUES-SPECIFIER-TYPE-CACHE-CLEAR must be called whenever a
  25 ;;; type is defined (or redefined).
  26 (defun-cached (values-specifier-type
  27                :hash-function (lambda (x)
  28                                 ;; FIXME: the THE FIXNUM stuff is
  29                                 ;; redundant in SBCL (or modern CMU
  30                                 ;; CL) because of type inference.
  31                                 (the fixnum
  32                                      (logand (the fixnum (sxhash x))
  33                                              #x3FF)))
  34                :hash-bits 10
  35                :init-wrapper !cold-init-forms)
  36               ((orig eq))
  37   (let ((u (uncross orig)))
  38     (or (info :type :builtin u)
  39         (let ((spec (type-expand u)))
  40           (cond
  41            ((and (not (eq spec u))
  42                  (info :type :builtin spec)))
  43            ((eq (info :type :kind spec) :instance)
  44             (sb!xc:find-class spec))
  45            ((typep spec 'class)
  46             ;; There doesn't seem to be any way to translate
  47             ;; (TYPEP SPEC 'BUILT-IN-CLASS) into something which can be
  48             ;; executed on the host Common Lisp at cross-compilation time.
  49             #+sb-xc-host (error
  50                           "stub: (TYPEP SPEC 'BUILT-IN-CLASS) on xc host")
  51             (if (typep spec 'built-in-class)
  52                 (or (built-in-class-translation spec) spec)
  53                 spec))
  54            (t
  55             (let* ((lspec (if (atom spec) (list spec) spec))
  56                    (fun (info :type :translator (car lspec))))
  57               (cond (fun (funcall fun lspec))
  58                     ((or (and (consp spec) (symbolp (car spec)))
  59                          (symbolp spec))
  60                      (when *type-system-initialized*
  61                        (signal 'parse-unknown-type :specifier spec))
  62                      ;; (The RETURN-FROM here inhibits caching.)
  63                      (return-from values-specifier-type
  64                        (make-unknown-type :specifier spec)))
  65                     (t
  66                      (error "bad thing to be a type specifier: ~S"
  67                             spec))))))))))
  68
  69 ;;; Like VALUES-SPECIFIER-TYPE, except that we guarantee to never
  70 ;;; return a VALUES type.
  71 (defun specifier-type (x)
  72   (let ((res (values-specifier-type x)))
  73     (when (values-type-p res)
  74       (error "VALUES type illegal in this context:~%  ~S" x))
  75     res))
  76
  77 ;;; Similar to MACROEXPAND, but expands DEFTYPEs. We don't bother
  78 ;;; returning a second value.
  79 (defun type-expand (form)
  80   (let ((def (cond ((symbolp form)
  81                     (info :type :expander form))
  82                    ((and (consp form) (symbolp (car form)))
  83                     (info :type :expander (car form)))
  84                    (t nil))))
  85     (if def
  86         (type-expand (funcall def (if (consp form) form (list form))))
  87         form)))
  88
  89 ;;; A HAIRY-TYPE represents anything too weird to be described
  90 ;;; reasonably or to be useful, such as AND, NOT and SATISFIES and
  91 ;;; unknown types. We just remember the original type spec.
  92 (defstruct (hairy-type (:include ctype
  93                                  (class-info (type-class-or-lose 'hairy))
  94                                  (enumerable t))
  95                        #!+cmu (:pure nil))
  96   ;; the Common Lisp type-specifier
  97   (specifier nil :type t))
  98
  99 (define-type-class hairy)
 100
 101 ;;; An UNKNOWN-TYPE is a type not known to the type system (not yet
 102 ;;; defined). We make this distinction since we don't want to complain
 103 ;;; about types that are hairy but defined.
 104 (defstruct (unknown-type (:include hairy-type)))
 105
 106 ;;; ARGS-TYPE objects are used both to represent VALUES types and
 107 ;;; to represent FUNCTION types.
 108 (defstruct (args-type (:include ctype)
 109                       (:constructor nil))
 110   ;; Lists of the type for each required and optional argument.
 111   (required nil :type list)
 112   (optional nil :type list)
 113   ;; The type for the rest arg. NIL if there is no rest arg.
 114   (rest nil :type (or ctype null))
 115   ;; True if keyword arguments are specified.
 116   (keyp nil :type boolean)
 117   ;; List of key-info structures describing the keyword arguments.
 118   (keywords nil :type list)
 119   ;; True if other keywords are allowed.
 120   (allowp nil :type boolean))
 121
 122 (defstruct (values-type
 123             (:include args-type
 124                       (class-info (type-class-or-lose 'values)))))
 125
 126 (define-type-class values)
 127
 128 (defstruct (function-type
 129             (:include args-type
 130                       (class-info (type-class-or-lose 'function))))
 131   ;; True if the arguments are unrestrictive, i.e. *.
 132   (wild-args nil :type boolean)
 133   ;; Type describing the return values. This is a values type
 134   ;; when multiple values were specified for the return.
 135   (returns (required-argument) :type ctype))
 136
 137 ;;; The CONSTANT-TYPE structure represents a use of the
 138 ;;; CONSTANT-ARGUMENT "type specifier", which is only meaningful in
 139 ;;; function argument type specifiers used within the compiler. (It
 140 ;;; represents something that the compiler knows to be a constant.)
 141 (defstruct (constant-type
 142             (:include ctype
 143                       (class-info (type-class-or-lose 'constant))))
 144   ;; The type which the argument must be a constant instance of for this type
 145   ;; specifier to win.
 146   (type (required-argument) :type ctype))
 147
 148 ;;; The NAMED-TYPE is used to represent *, T and NIL. These types must be
 149 ;;; super or sub types of all types, not just classes and * & NIL aren't
 150 ;;; classes anyway, so it wouldn't make much sense to make them built-in
 151 ;;; classes.
 152 (defstruct (named-type (:include ctype
 153                                  (class-info (type-class-or-lose 'named))))
 154   (name nil :type symbol))
 155
 156 ;;; The Numeric-Type is used to represent all numeric types, including things
 157 ;;; such as FIXNUM.
 158 (defstruct (numeric-type (:include ctype
 159                                    (class-info (type-class-or-lose
 160                                                 'number)))
 161                          #!+negative-zero-is-not-zero
 162                          (:constructor %make-numeric-type))
 163   ;; The kind of numeric type we have. NIL if not specified (just NUMBER or
 164   ;; COMPLEX).
 165   ;;
 166   ;; KLUDGE: A slot named CLASS for a non-CLASS value is bad.
 167   ;; Especially when a CLASS value *is* stored in another slot (called
 168   ;; CLASS-INFO:-). Perhaps this should be called CLASS-NAME? Also
 169   ;; weird that comment above says "Numeric-Type is used to represent
 170   ;; all numeric types" but this slot doesn't allow COMPLEX as an
 171   ;; option.. how does this fall into "not specified" NIL case above?
 172   (class nil :type (member integer rational float nil))
 173   ;; Format for a float type. NIL if not specified or not a float. Formats
 174   ;; which don't exist in a given implementation don't appear here.
 175   (format nil :type (or float-format null))
 176   ;; Is this a complex numeric type?  Null if unknown (only in NUMBER.)
 177   ;;
 178   ;; FIXME: I'm bewildered by FOO-P names for things not intended to
 179   ;; interpreted as truth values. Perhaps rename this COMPLEXNESS?
 180   (complexp :real :type (member :real :complex nil))
 181   ;; The upper and lower bounds on the value. If null, there is no bound. If
 182   ;; a list of a number, the bound is exclusive. Integer types never have
 183   ;; exclusive bounds.
 184   (low nil :type (or number cons null))
 185   (high nil :type (or number cons null)))
 186
 187 ;;; The Array-Type is used to represent all array types, including
 188 ;;; things such as SIMPLE-STRING.
 189 (defstruct (array-type (:include ctype
 190                                  (class-info (type-class-or-lose 'array))))
 191   ;; The dimensions of the array. * if unspecified. If a dimension is
 192   ;; unspecified, it is *.
 193   (dimensions '* :type (or list (member *)))
 194   ;; Is this not a simple array type? (:MAYBE means that we don't know.)
 195   (complexp :maybe :type (member t nil :maybe))
 196   ;; The element type as originally specified.
 197   (element-type (required-argument) :type ctype)
 198   ;; The element type as it is specialized in this implementation.
 199   (specialized-element-type *wild-type* :type ctype))
 200
 201 ;;; The Member-Type represents uses of the MEMBER type specifier. We
 202 ;;; bother with this at this level because MEMBER types are fairly
 203 ;;; important and union and intersection are well defined.
 204 (defstruct (member-type (:include ctype
 205                                   (class-info (type-class-or-lose 'member))
 206                                   (enumerable t))
 207                         #-sb-xc-host (:pure nil))
 208   ;; The things in the set, with no duplications.
 209   (members nil :type list))
 210
 211 ;;; A UNION-TYPE represents a use of the OR type specifier which can't
 212 ;;; be canonicalized to something simpler. Canonical form:
 213 ;;;   1. There is never more than one Member-Type component.
 214 ;;;   2. There are never any Union-Type components.
 215 (defstruct (union-type (:include ctype
 216                                  (class-info (type-class-or-lose 'union)))
 217                        (:constructor %make-union-type (enumerable types)))
 218   ;; The types in the union.
 219   (types nil :type list))
 220 \f
 221 ;;; Note that the type Name has been (re)defined, updating the
 222 ;;; undefined warnings and VALUES-SPECIFIER-TYPE cache.
 223 (defun %note-type-defined (name)
 224   (declare (symbol name))
 225   (note-name-defined name :type)
 226   (when (boundp 'sb!kernel::*values-specifier-type-cache-vector*)
 227     (values-specifier-type-cache-clear))
 228   (values))
 229 \f
 230 ;;;; KLUDGE: not clear this really belongs here, but where?
 231
 232 ;;; Is X a fixnum in the target Lisp?
 233 (defun target-fixnump (x)
 234   (and (integerp x)
 235        (<= sb!vm:*target-most-negative-fixnum*
 236            x
 237            sb!vm:*target-most-positive-fixnum*)))
 238
 239 (!defun-from-collected-cold-init-forms !early-type-cold-init)