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