X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=src%2Fcode%2Fearly-type.lisp;h=16404c784033a9fea27cea935da95667b7315b80;hb=568214ddf4c8ecc881caec98e20848d017974ec0;hp=add9dfb87202793e889a0318569e13e23c66ec58;hpb=4eb1a6d3ad2b7dcc19ac0ec979a1eb1eb049659a;p=sbcl.git diff --git a/src/code/early-type.lisp b/src/code/early-type.lisp index add9dfb..16404c7 100644 --- a/src/code/early-type.lisp +++ b/src/code/early-type.lisp @@ -11,84 +11,7 @@ (!begin-collecting-cold-init-forms) -;;; Has the type system been properly initialized? (I.e. is it OK to -;;; use it?) -(defvar *type-system-initialized* #+sb-xc-host nil) ; (set in cold load) - -;;; Return the type structure corresponding to a type specifier. We -;;; pick off structure types as a special case. -;;; -;;; Note: VALUES-SPECIFIER-TYPE-CACHE-CLEAR must be called whenever a -;;; type is defined (or redefined). -(defun-cached (values-specifier-type - :hash-function (lambda (x) - ;; FIXME: The THE FIXNUM stuff is - ;; redundant in SBCL (or modern CMU - ;; CL) because of type inference. - (the fixnum - (logand (the fixnum (sxhash x)) - #x3FF))) - :hash-bits 10 - :init-wrapper !cold-init-forms) - ((orig eq)) - (let ((u (uncross orig))) - (or (info :type :builtin u) - (let ((spec (type-expand u))) - (cond - ((and (not (eq spec u)) - (info :type :builtin spec))) - ((eq (info :type :kind spec) :instance) - (sb!xc:find-class spec)) - ((typep spec 'class) - ;; There doesn't seem to be any way to translate - ;; (TYPEP SPEC 'BUILT-IN-CLASS) into something which can be - ;; executed on the host Common Lisp at cross-compilation time. - #+sb-xc-host (error - "stub: (TYPEP SPEC 'BUILT-IN-CLASS) on xc host") - (if (typep spec 'built-in-class) - (or (built-in-class-translation spec) spec) - spec)) - (t - (let* (;; FIXME: This automatic promotion of FOO-style - ;; specs to (FOO)-style specs violates the ANSI - ;; standard. Unfortunately, we can't fix the - ;; problem just by removing it, since then things - ;; downstream should break. But at some point we - ;; should fix this and the things downstream too. - (lspec (if (atom spec) (list spec) spec)) - (fun (info :type :translator (car lspec)))) - (cond (fun - (funcall fun lspec)) - ((or (and (consp spec) (symbolp (car spec))) - (symbolp spec)) - (when *type-system-initialized* - (signal 'parse-unknown-type :specifier spec)) - ;; (The RETURN-FROM here inhibits caching.) - (return-from values-specifier-type - (make-unknown-type :specifier spec))) - (t - (error "bad thing to be a type specifier: ~S" - spec)))))))))) - -;;; Like VALUES-SPECIFIER-TYPE, except that we guarantee to never -;;; return a VALUES type. -(defun specifier-type (x) - (let ((res (values-specifier-type x))) - (when (values-type-p res) - (error "VALUES type illegal in this context:~% ~S" x)) - res)) - -;;; Similar to MACROEXPAND, but expands DEFTYPEs. We don't bother -;;; returning a second value. -(defun type-expand (form) - (let ((def (cond ((symbolp form) - (info :type :expander form)) - ((and (consp form) (symbolp (car form))) - (info :type :expander (car form))) - (t nil)))) - (if def - (type-expand (funcall def (if (consp form) form (list form)))) - form))) +;;;; representations of types ;;; A HAIRY-TYPE represents anything too weird to be described ;;; reasonably or to be useful, such as NOT, SATISFIES, unknown types, @@ -96,10 +19,11 @@ ;;; the original type spec. (defstruct (hairy-type (:include ctype (class-info (type-class-or-lose 'hairy)) - (enumerable t)) + (enumerable t) + (might-contain-other-types-p t)) (:copier nil) #!+cmu (:pure nil)) - ;; the Common Lisp type-specifier + ;; the Common Lisp type-specifier of the type we represent (specifier nil :type t)) (!define-type-class hairy) @@ -110,6 +34,18 @@ (defstruct (unknown-type (:include hairy-type) (:copier nil))) +(defstruct (negation-type (:include ctype + (class-info (type-class-or-lose 'negation)) + ;; FIXME: is this right? It's + ;; what they had before, anyway + (enumerable t) + (might-contain-other-types-p t)) + (:copier nil) + #!+cmu (:pure nil)) + (type (missing-arg) :type ctype)) + +(!define-type-class negation) + ;;; ARGS-TYPE objects are used both to represent VALUES types and ;;; to represent FUNCTION types. (defstruct (args-type (:include ctype) @@ -127,26 +63,156 @@ ;; true if other &KEY arguments are allowed (allowp nil :type boolean)) +(defun canonicalize-args-type-args (required optional rest) + (when (eq rest *empty-type*) + ;; or vice-versa? + (setq rest nil)) + (loop with last-not-rest = nil + for i from 0 + for opt in optional + do (cond ((eq opt *empty-type*) + (return (values required (subseq optional i) rest))) + ((neq opt rest) + (setq last-not-rest i))) + finally (return (values required + (if last-not-rest + (subseq optional 0 (1+ last-not-rest)) + nil) + rest)))) + +(defun args-types (lambda-list-like-thing) + (multiple-value-bind + (required optional restp rest keyp keys allowp auxp aux + morep more-context more-count llk-p) + (parse-lambda-list-like-thing lambda-list-like-thing) + (declare (ignore aux morep more-context more-count)) + (when auxp + (error "&AUX in a FUNCTION or VALUES type: ~S." lambda-list-like-thing)) + (let ((required (mapcar #'single-value-specifier-type required)) + (optional (mapcar #'single-value-specifier-type optional)) + (rest (when restp (single-value-specifier-type rest))) + (keywords + (collect ((key-info)) + (dolist (key keys) + (unless (proper-list-of-length-p key 2) + (error "Keyword type description is not a two-list: ~S." key)) + (let ((kwd (first key))) + (when (find kwd (key-info) :key #'key-info-name) + (error "~@" + kwd lambda-list-like-thing)) + (key-info + (make-key-info + :name kwd + :type (single-value-specifier-type (second key)))))) + (key-info)))) + (multiple-value-bind (required optional rest) + (canonicalize-args-type-args required optional rest) + (values required optional rest keyp keywords allowp llk-p))))) + (defstruct (values-type (:include args-type (class-info (type-class-or-lose 'values))) + (:constructor %make-values-type) (:copier nil))) +(defun-cached (make-values-type-cached + :hash-bits 8 + :hash-function (lambda (req opt rest allowp) + (logand (logxor + (type-list-cache-hash req) + (type-list-cache-hash opt) + (if rest + (type-hash-value rest) + 42) + (sxhash allowp)) + #xFF))) + ((required equal-but-no-car-recursion) + (optional equal-but-no-car-recursion) + (rest eq) + (allowp eq)) + (%make-values-type :required required + :optional optional + :rest rest + :allowp allowp)) + +(defun make-values-type (&key (args nil argsp) + required optional rest allowp) + (if argsp + (if (eq args '*) + *wild-type* + (multiple-value-bind (required optional rest keyp keywords allowp + llk-p) + (args-types args) + (declare (ignore keywords)) + (when keyp + (error "&KEY appeared in a VALUES type specifier ~S." + `(values ,@args))) + (if llk-p + (make-values-type :required required + :optional optional + :rest rest + :allowp allowp) + (make-short-values-type required)))) + (multiple-value-bind (required optional rest) + (canonicalize-args-type-args required optional rest) + (cond ((and (null required) + (null optional) + (eq rest *universal-type*)) + *wild-type*) + ((memq *empty-type* required) + *empty-type*) + (t (make-values-type-cached required optional + rest allowp)))))) + (!define-type-class values) ;;; (SPECIFIER-TYPE 'FUNCTION) and its subtypes (defstruct (fun-type (:include args-type - (class-info (type-class-or-lose 'function)))) + (class-info (type-class-or-lose 'function))) + (:constructor + %make-fun-type (&key required optional rest + keyp keywords allowp + wild-args + returns + &aux (rest (if (eq rest *empty-type*) + nil + rest))))) ;; true if the arguments are unrestrictive, i.e. * (wild-args nil :type boolean) ;; type describing the return values. This is a values type ;; when multiple values were specified for the return. (returns (missing-arg) :type ctype)) +(defun make-fun-type (&rest initargs + &key (args nil argsp) returns &allow-other-keys) + (if argsp + (if (eq args '*) + (if (eq returns *wild-type*) + (specifier-type 'function) + (%make-fun-type :wild-args t :returns returns)) + (multiple-value-bind (required optional rest keyp keywords allowp) + (args-types args) + (if (and (null required) + (null optional) + (eq rest *universal-type*) + (not keyp)) + (if (eq returns *wild-type*) + (specifier-type 'function) + (%make-fun-type :wild-args t :returns returns)) + (%make-fun-type :required required + :optional optional + :rest rest + :keyp keyp + :keywords keywords + :allowp allowp + :returns returns)))) + ;; FIXME: are we really sure that we won't make something that + ;; looks like a completely wild function here? + (apply #'%make-fun-type initargs))) -;;; The CONSTANT-TYPE structure represents a use of the -;;; CONSTANT-ARGUMENT "type specifier", which is only meaningful in -;;; function argument type specifiers used within the compiler. (It -;;; represents something that the compiler knows to be a constant.) +;;; The CONSTANT-TYPE structure represents a use of the CONSTANT-ARG +;;; "type specifier", which is only meaningful in function argument +;;; type specifiers used within the compiler. (It represents something +;;; that the compiler knows to be a constant.) (defstruct (constant-type (:include ctype (class-info (type-class-or-lose 'constant))) @@ -155,10 +221,10 @@ ;; specifier to win. (type (missing-arg) :type ctype)) -;;; The NAMED-TYPE is used to represent *, T and NIL. These types must be -;;; super- or sub-types of all types, not just classes and * and NIL aren't -;;; classes anyway, so it wouldn't make much sense to make them built-in -;;; classes. +;;; The NAMED-TYPE is used to represent *, T and NIL. These types must +;;; be super- or sub-types of all types, not just classes and * and +;;; NIL aren't classes anyway, so it wouldn't make much sense to make +;;; them built-in classes. (defstruct (named-type (:include ctype (class-info (type-class-or-lose 'named))) (:copier nil)) @@ -234,25 +300,14 @@ (if (consp high) (1- (type-bound-number high)) high))) - #!+negative-zero-is-not-zero - (float - ;; Canonicalize a low bound of (-0.0) to 0.0, and a high - ;; bound of (+0.0) to -0.0. - (values (if (and (consp low) - (floatp (car low)) - (zerop (car low)) - (minusp (float-sign (car low)))) - (float 0.0 (car low)) - low) - (if (and (consp high) - (floatp (car high)) - (zerop (car high)) - (plusp (float-sign (car high)))) - (float -0.0 (car high)) - high))) (t ;; no canonicalization necessary (values low high))) + (when (and (eq class 'rational) + (integerp canonical-low) + (integerp canonical-high) + (= canonical-low canonical-high)) + (setf class 'integer)) (%make-numeric-type :class class :format format :complexp complexp @@ -275,10 +330,39 @@ :high high :enumerable enumerable)) +(defstruct (character-set-type + (:include ctype + (class-info (type-class-or-lose 'character-set))) + (:constructor %make-character-set-type) + (:copier nil)) + (pairs (missing-arg) :type list :read-only t)) +(defun make-character-set-type (&key pairs) + (aver (equal (mapcar #'car pairs) + (sort (mapcar #'car pairs) #'<))) + (let ((pairs (let (result) + (do ((pairs pairs (cdr pairs))) + ((null pairs) (nreverse result)) + (destructuring-bind (low . high) (car pairs) + (loop for (low1 . high1) in (cdr pairs) + if (<= low1 (1+ high)) + do (progn (setf high (max high high1)) + (setf pairs (cdr pairs))) + else do (return nil)) + (cond + ((>= low sb!xc:char-code-limit)) + ((< high 0)) + (t (push (cons (max 0 low) + (min high (1- sb!xc:char-code-limit))) + result)))))))) + (if (null pairs) + *empty-type* + (%make-character-set-type :pairs pairs)))) + ;;; An ARRAY-TYPE is used to represent any array type, including -;;; things such as SIMPLE-STRING. +;;; things such as SIMPLE-BASE-STRING. (defstruct (array-type (:include ctype (class-info (type-class-or-lose 'array))) + (:constructor %make-array-type) (:copier nil)) ;; the dimensions of the array, or * if unspecified. If a dimension ;; is unspecified, it is *. @@ -289,6 +373,7 @@ (element-type (missing-arg) :type ctype) ;; the element type as it is specialized in this implementation (specialized-element-type *wild-type* :type ctype)) +(define-cached-synonym make-array-type) ;;; A MEMBER-TYPE represent a use of the MEMBER type specifier. We ;;; bother with this at this level because MEMBER types are fairly @@ -297,13 +382,46 @@ (class-info (type-class-or-lose 'member)) (enumerable t)) (:copier nil) + (:constructor %make-member-type (members)) #-sb-xc-host (:pure nil)) ;; the things in the set, with no duplications (members nil :type list)) +(defun make-member-type (&key members) + (declare (type list members)) + ;; make sure that we've removed duplicates + (aver (= (length members) (length (remove-duplicates members)))) + ;; if we have a pair of zeros (e.g. 0.0d0 and -0.0d0), then we can + ;; canonicalize to (DOUBLE-FLOAT 0.0d0 0.0d0), because numeric + ;; ranges are compared by arithmetic operators (while MEMBERship is + ;; compared by EQL). -- CSR, 2003-04-23 + (let ((singlep (subsetp `(,(load-time-value (make-unportable-float :single-float-negative-zero)) 0.0f0) members)) + (doublep (subsetp `(,(load-time-value (make-unportable-float :double-float-negative-zero)) 0.0d0) members)) + #!+long-float + (longp (subsetp `(,(load-time-value (make-unportable-float :long-float-negative-zero)) 0.0l0) members))) + (if (or singlep doublep #!+long-float longp) + (let (union-types) + (when singlep + (push (ctype-of 0.0f0) union-types) + (setf members (set-difference members `(,(load-time-value (make-unportable-float :single-float-negative-zero)) 0.0f0)))) + (when doublep + (push (ctype-of 0.0d0) union-types) + (setf members (set-difference members `(,(load-time-value (make-unportable-float :double-float-negative-zero)) 0.0d0)))) + #!+long-float + (when longp + (push (ctype-of 0.0l0) union-types) + (setf members (set-difference members `(,(load-time-value (make-unportable-float :long-float-negative-zero)) 0.0l0)))) + (aver (not (null union-types))) + (make-union-type t + (if (null members) + union-types + (cons (%make-member-type members) + union-types)))) + (%make-member-type members)))) ;;; A COMPOUND-TYPE is a type defined out of a set of types, the ;;; common parent of UNION-TYPE and INTERSECTION-TYPE. -(defstruct (compound-type (:include ctype) +(defstruct (compound-type (:include ctype + (might-contain-other-types-p t)) (:constructor nil) (:copier nil)) (types nil :type list :read-only t)) @@ -319,6 +437,7 @@ (class-info (type-class-or-lose 'union))) (:constructor %make-union-type (enumerable types)) (:copier nil))) +(define-cached-synonym make-union-type) ;;; An INTERSECTION-TYPE represents a use of the AND type specifier ;;; which we couldn't canonicalize to something simpler. Canonical form: @@ -348,25 +467,121 @@ type)) ;;; A CONS-TYPE is used to represent a CONS type. -(defstruct (cons-type (:include ctype (:class-info (type-class-or-lose 'cons))) +(defstruct (cons-type (:include ctype (class-info (type-class-or-lose 'cons))) (:constructor - ;; ANSI says that for CAR and CDR subtype - ;; specifiers '* is equivalent to T. In order - ;; to avoid special cases in SUBTYPEP and - ;; possibly elsewhere, we slam all CONS-TYPE - ;; objects into canonical form w.r.t. this - ;; equivalence at creation time. - make-cons-type (car-raw-type - cdr-raw-type - &aux - (car-type (type-*-to-t car-raw-type)) - (cdr-type (type-*-to-t cdr-raw-type)))) + %make-cons-type (car-type + cdr-type)) (:copier nil)) ;; the CAR and CDR element types (to support ANSI (CONS FOO BAR) types) ;; ;; FIXME: Most or all other type structure slots could also be :READ-ONLY. (car-type (missing-arg) :type ctype :read-only t) (cdr-type (missing-arg) :type ctype :read-only t)) +(defun make-cons-type (car-type cdr-type) + (aver (not (or (eq car-type *wild-type*) + (eq cdr-type *wild-type*)))) + (if (or (eq car-type *empty-type*) + (eq cdr-type *empty-type*)) + *empty-type* + (%make-cons-type car-type cdr-type))) + +(defun cons-type-length-info (type) + (declare (type cons-type type)) + (do ((min 1 (1+ min)) + (cdr (cons-type-cdr-type type) (cons-type-cdr-type cdr))) + ((not (cons-type-p cdr)) + (cond + ((csubtypep cdr (specifier-type 'null)) + (values min t)) + ((csubtypep *universal-type* cdr) + (values min nil)) + ((type/= (type-intersection (specifier-type 'cons) cdr) *empty-type*) + (values min nil)) + ((type/= (type-intersection (specifier-type 'null) cdr) *empty-type*) + (values min t)) + (t (values min :maybe)))) + ())) + + +;;;; type utilities + +;;; Return the type structure corresponding to a type specifier. We +;;; pick off structure types as a special case. +;;; +;;; Note: VALUES-SPECIFIER-TYPE-CACHE-CLEAR must be called whenever a +;;; type is defined (or redefined). +(defun-cached (values-specifier-type + :hash-function (lambda (x) + (logand (sxhash x) #x3FF)) + :hash-bits 10 + :init-wrapper !cold-init-forms) + ((orig equal-but-no-car-recursion)) + (let ((u (uncross orig))) + (or (info :type :builtin u) + (let ((spec (type-expand u))) + (cond + ((and (not (eq spec u)) + (info :type :builtin spec))) + ((eq (info :type :kind spec) :instance) + (find-classoid spec)) + ((typep spec 'classoid) + ;; There doesn't seem to be any way to translate + ;; (TYPEP SPEC 'BUILT-IN-CLASS) into something which can be + ;; executed on the host Common Lisp at cross-compilation time. + #+sb-xc-host (error + "stub: (TYPEP SPEC 'BUILT-IN-CLASS) on xc host") + (if (typep spec 'built-in-classoid) + (or (built-in-classoid-translation spec) spec) + spec)) + (t + (when (and (atom spec) + (member spec '(and or not member eql satisfies values))) + (error "The symbol ~S is not valid as a type specifier." spec)) + (let* ((lspec (if (atom spec) (list spec) spec)) + (fun (info :type :translator (car lspec)))) + (cond (fun + (funcall fun lspec)) + ((or (and (consp spec) (symbolp (car spec)) + (not (info :type :builtin (car spec)))) + (and (symbolp spec) (not (info :type :builtin spec)))) + (when (and *type-system-initialized* + (not (eq (info :type :kind spec) + :forthcoming-defclass-type))) + (signal 'parse-unknown-type :specifier spec)) + ;; (The RETURN-FROM here inhibits caching.) + (return-from values-specifier-type + (make-unknown-type :specifier spec))) + (t + (error "bad thing to be a type specifier: ~S" + spec)))))))))) + +;;; This is like VALUES-SPECIFIER-TYPE, except that we guarantee to +;;; never return a VALUES type. +(defun specifier-type (x) + (let ((res (values-specifier-type x))) + (when (or (values-type-p res) + ;; bootstrap magic :-( + (and (named-type-p res) + (eq (named-type-name res) '*))) + (error "VALUES type illegal in this context:~% ~S" x)) + res)) + +(defun single-value-specifier-type (x) + (if (eq x '*) + *universal-type* + (specifier-type x))) + +;;; Similar to MACROEXPAND, but expands DEFTYPEs. We don't bother +;;; returning a second value. +(defun type-expand (form) + (let ((def (cond ((symbolp form) + (info :type :expander form)) + ((and (consp form) (symbolp (car form))) + (info :type :expander (car form))) + (t nil)))) + (if def + (type-expand (funcall def (if (consp form) form (list form)))) + form))) ;;; Note that the type NAME has been (re)defined, updating the ;;; undefined warnings and VALUES-SPECIFIER-TYPE cache. @@ -377,4 +592,5 @@ (values-specifier-type-cache-clear)) (values)) + (!defun-from-collected-cold-init-forms !early-type-cold-init)