+;;;; general TYPE-UNION and TYPE-INTERSECTION operations
+;;;;
+;;;; These are fully general operations on CTYPEs: they'll always
+;;;; return a CTYPE representing the result.
+
+;;; shared logic for unions and intersections: Stuff TYPE into the
+;;; vector TYPES, finding pairs of types which can be simplified by
+;;; SIMPLIFY2 (TYPE-UNION2 or TYPE-INTERSECTION2) and replacing them
+;;; by their simplified forms.
+(defun accumulate1-compound-type (type types %compound-type-p simplify2)
+ (declare (type ctype type))
+ (declare (type (vector ctype) types))
+ (declare (type function simplify2))
+ ;; Any input object satisfying %COMPOUND-TYPE-P should've been
+ ;; broken into components before it reached us.
+ (aver (not (funcall %compound-type-p type)))
+ (dotimes (i (length types) (vector-push-extend type types))
+ (let ((simplified2 (funcall simplify2 type (aref types i))))
+ (when simplified2
+ ;; Discard the old (AREF TYPES I).
+ (setf (aref types i) (vector-pop types))
+ ;; Merge the new SIMPLIFIED2 into TYPES, by tail recursing.
+ ;; (Note that the tail recursion is indirect: we go through
+ ;; ACCUMULATE, not ACCUMULATE1, so that if SIMPLIFIED2 is
+ ;; handled properly if it satisfies %COMPOUND-TYPE-P.)
+ (return (accumulate-compound-type simplified2
+ types
+ %compound-type-p
+ simplify2)))))
+ ;; Voila.
+ (values))
+
+;;; shared logic for unions and intersections: Use
+;;; ACCUMULATE1-COMPOUND-TYPE to merge TYPE into TYPES, either
+;;; all in one step or, if %COMPOUND-TYPE-P is satisfied,
+;;; component by component.
+(defun accumulate-compound-type (type types %compound-type-p simplify2)
+ (declare (type function %compound-type-p simplify2))
+ (flet ((accumulate1 (x)
+ (accumulate1-compound-type x types %compound-type-p simplify2)))
+ (declare (inline accumulate1))
+ (if (funcall %compound-type-p type)
+ (map nil #'accumulate1 (compound-type-types type))
+ (accumulate1 type)))
+ (values))
+
+;;; shared logic for unions and intersections: Return a vector of
+;;; types representing the same types as INPUT-TYPES, but with
+;;; COMPOUND-TYPEs satisfying %COMPOUND-TYPE-P broken up into their
+;;; component types, and with any SIMPLY2 simplifications applied.
+(defun simplified-compound-types (input-types %compound-type-p simplify2)
+ (let ((simplified-types (make-array (length input-types)
+ :fill-pointer 0
+ :element-type 'ctype
+ ;; (This INITIAL-ELEMENT shouldn't
+ ;; matter, but helps avoid type
+ ;; warnings at compile time.)
+ :initial-element *empty-type*)))
+ (dolist (input-type input-types)
+ (accumulate-compound-type input-type
+ simplified-types
+ %compound-type-p
+ simplify2))
+ simplified-types))
+
+;;; shared logic for unions and intersections: Make a COMPOUND-TYPE
+;;; object whose components are the types in TYPES, or skip to special
+;;; cases when TYPES is short.
+(defun make-compound-type-or-something (constructor types enumerable identity)
+ (declare (type function constructor))
+ (declare (type (vector ctype) types))
+ (declare (type ctype identity))
+ (case (length types)
+ (0 identity)
+ (1 (aref types 0))
+ (t (funcall constructor
+ enumerable
+ ;; FIXME: This should be just (COERCE TYPES 'LIST), but as
+ ;; of sbcl-0.6.11.17 the COERCE optimizer is really
+ ;; brain-dead, so that would generate a full call to
+ ;; SPECIFIER-TYPE at runtime, so we get into bootstrap
+ ;; problems in cold init because 'LIST is a compound
+ ;; type, so we need to MAKE-COMPOUND-TYPE-OR-SOMETHING
+ ;; before we know what 'LIST is. Once the COERCE
+ ;; optimizer is less brain-dead, we can make this
+ ;; (COERCE TYPES 'LIST) again.
+ #+sb-xc-host (coerce types 'list)
+ #-sb-xc-host (coerce-to-list types)))))
+
+(defun type-intersection (&rest input-types)
+ (let ((simplified-types (simplified-compound-types input-types
+ #'intersection-type-p
+ #'type-intersection2)))
+ (declare (type (vector ctype) simplified-types))
+ ;; We want to have a canonical representation of types (or failing
+ ;; that, punt to HAIRY-TYPE). Canonical representation would have
+ ;; intersections inside unions but not vice versa, since you can
+ ;; always achieve that by the distributive rule. But we don't want
+ ;; to just apply the distributive rule, since it would be too easy
+ ;; to end up with unreasonably huge type expressions. So instead
+ ;; we punt to HAIRY-TYPE when this comes up.
+ (if (and (> (length simplified-types) 1)
+ (some #'union-type-p simplified-types))
+ (make-hairy-type
+ :specifier `(and ,@(map 'list #'type-specifier simplified-types)))
+ (make-compound-type-or-something #'%make-intersection-type
+ simplified-types
+ (some #'type-enumerable
+ simplified-types)
+ *universal-type*))))
+
+(defun type-union (&rest input-types)
+ (let ((simplified-types (simplified-compound-types input-types
+ #'union-type-p
+ #'type-union2)))
+ (make-compound-type-or-something #'%make-union-type
+ simplified-types
+ (every #'type-enumerable simplified-types)
+ *empty-type*)))
+\f
projects / sbcl.git / blobdiff