src/code/type-class.lisp

   1 ;;;; stuff related to the TYPE-CLASS structure
   2
   3 ;;;; This software is part of the SBCL system. See the README file for
   4 ;;;; more information.
   5 ;;;;
   6 ;;;; This software is derived from the CMU CL system, which was
   7 ;;;; written at Carnegie Mellon University and released into the
   8 ;;;; public domain. The software is in the public domain and is
   9 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
  10 ;;;; files for more information.
  11
  12 (in-package "SB!KERNEL")
  13
  14 (!begin-collecting-cold-init-forms)
  15
  16 (defvar *type-classes*)
  17 (!cold-init-forms
  18   (unless (boundp '*type-classes*) ; FIXME: How could this be bound?
  19     (setq *type-classes* (make-hash-table :test 'eq))))
  20
  21 (defun type-class-or-lose (name)
  22   (or (gethash name *type-classes*)
  23       (error "~S is not a defined type class." name)))
  24
  25 (defun must-supply-this (&rest foo)
  26   (/show0 "failing in MUST-SUPPLY-THIS")
  27   (error "missing type method for ~S" foo))
  28
  29 ;;; A TYPE-CLASS object represents the "kind" of a type. It mainly
  30 ;;; contains functions which are methods on that kind of type, but is
  31 ;;; also used in EQ comparisons to determined if two types have the
  32 ;;; "same kind".
  33 (def!struct (type-class
  34              #-no-ansi-print-object
  35              (:print-object (lambda (x stream)
  36                               (print-unreadable-object (x stream :type t)
  37                                 (prin1 (type-class-name x) stream)))))
  38   ;; the name of this type class (used to resolve references at load time)
  39   (name nil :type symbol) ; FIXME: should perhaps be (MISSING-ARG) default?
  40   ;; Dyadic type methods. If the classes of the two types are EQ, then
  41   ;; we call the SIMPLE-xxx method. If the classes are not EQ, and
  42   ;; either type's class has a COMPLEX-xxx method, then we call it.
  43   ;;
  44   ;; Although it is undefined which method will get precedence when
  45   ;; both types have a complex method, the complex method can assume
  46   ;; that the second arg always is in its class, and the first always
  47   ;; is not. The arguments to commutative operations will be swapped
  48   ;; if the first argument has a complex method.
  49   ;;
  50   ;; Since SUBTYPEP is not commutative, we have two complex methods.
  51   ;; The ARG1 method is only called when the first argument is in its
  52   ;; class, and the ARG2 method is only called when called when the
  53   ;; second type is. If either is specified, both must be.
  54   (simple-subtypep #'must-supply-this :type function)
  55   (complex-subtypep-arg1 nil :type (or function null))
  56   (complex-subtypep-arg2 nil :type (or function null))
  57   ;; SIMPLE-UNION2, COMPLEX-UNION2, SIMPLE-INTERSECTION2, and
  58   ;; COMPLEX-INTERSECTION2 methods take pairs of types and try to find
  59   ;; a new type which expresses the result nicely, better than could
  60   ;; be done by just stuffing the two component types into an
  61   ;; UNION-TYPE or INTERSECTION-TYPE object. They return NIL on
  62   ;; failure, or a CTYPE for success.
  63   ;;
  64   ;; Note: These methods are similar to CMU CL's SIMPLE-UNION,
  65   ;; COMPLEX-UNION, SIMPLE-INTERSECTION, and COMPLEX-UNION methods.
  66   ;; They were reworked in SBCL because SBCL has INTERSECTION-TYPE
  67   ;; objects (where CMU CL just punted to HAIRY-TYPE) and because SBCL
  68   ;; wants to simplify unions and intersections by considering all
  69   ;; possible pairwise simplifications (where the CMU CL code only
  70   ;; considered simplifications between types which happened to appear
  71   ;; next to each other the argument sequence).
  72   ;;
  73   ;; Differences in detail from old CMU CL methods:
  74   ;;   * SBCL's methods are more parallel between union and
  75   ;;     intersection forms. Each returns one values, (OR NULL CTYPE).
  76   ;;   * SBCL doesn't use type methods to deal with unions or
  77   ;;     intersections of the COMPOUND-TYPE of the corresponding form.
  78   ;;     Instead the wrapper functions TYPE-UNION2, TYPE-INTERSECTION2,
  79   ;;     TYPE-UNION, and TYPE-INTERSECTION handle those cases specially
  80   ;;     (and deal with canonicalization/simplification issues at the
  81   ;;     same time).
  82   (simple-union2 #'hierarchical-union2 :type function)
  83   (complex-union2 nil :type (or function null))
  84   (simple-intersection2 #'hierarchical-intersection2 :type function)
  85   (complex-intersection2 nil :type (or function null))
  86   (simple-= #'must-supply-this :type function)
  87   (complex-= nil :type (or function null))
  88   ;; a function which returns a Common Lisp type specifier
  89   ;; representing this type
  90   (unparse #'must-supply-this :type function)
  91
  92   #|
  93   Not used, and not really right. Probably we want a TYPE= alist for the
  94   unary operations, since there are lots of interesting unary predicates that
  95   aren't equivalent to an entire class
  96   ;; Names of functions used for testing the type of objects in this type
  97   ;; class. UNARY-PREDICATE takes just the object, whereas PREDICATE gets
  98   ;; passed both the object and the CTYPE. Normally one or the other will be
  99   ;; supplied for any type that can be passed to TYPEP; there is no point in
 100   ;; supplying both.
 101   (unary-typep nil :type (or symbol null))
 102   (typep nil :type (or symbol null))
 103   ;; These are like TYPEP and UNARY-TYPEP except they coerce objects to
 104   ;; the type.
 105   (unary-coerce nil :type (or symbol null))
 106   (coerce :type (or symbol null))
 107   |#
 108   )
 109
 110 (eval-when (:compile-toplevel :load-toplevel :execute)
 111   ;; KLUDGE: If the slots of TYPE-CLASS ever change, the slots here
 112   ;; will have to be tweaked to match. -- WHN 19991021
 113   (defparameter *type-class-fun-slots*
 114     '((:simple-subtypep . type-class-simple-subtypep)
 115       (:complex-subtypep-arg1 . type-class-complex-subtypep-arg1)
 116       (:complex-subtypep-arg2 . type-class-complex-subtypep-arg2)
 117       (:simple-union2 . type-class-simple-union2)
 118       (:complex-union2 . type-class-complex-union2)
 119       (:simple-intersection2 . type-class-simple-intersection2)
 120       (:complex-intersection2 . type-class-complex-intersection2)
 121       (:simple-= . type-class-simple-=)
 122       (:complex-= . type-class-complex-=)
 123       (:unparse . type-class-unparse))))
 124
 125 (declaim (ftype (function (type-class) type-class) copy-type-class-coldly))
 126 (eval-when (#-sb-xc :compile-toplevel :load-toplevel :execute)
 127 ;;; Copy TYPE-CLASS object X, using only operations which will work
 128 ;;; early in cold load. (COPY-STRUCTURE won't work early in cold load,
 129 ;;; because it needs RAW-INDEX and RAW-LENGTH information from
 130 ;;; LAYOUT-INFO, and LAYOUT-INFO isn't initialized early in cold
 131 ;;; load.)
 132 ;;;
 133 ;;; FIXME: It's nasty having to maintain this hand-written copy
 134 ;;; function. And it seems intrinsically dain-bramaged to have
 135 ;;; RAW-INDEX and RAW-LENGTH in LAYOUT-INFO instead of directly in
 136 ;;; LAYOUT. We should fix this:
 137 ;;;   * Move RAW-INDEX and RAW-LENGTH slots into LAYOUT itself.
 138 ;;;   * Rewrite the various CHECK-LAYOUT-related functions so that
 139 ;;;     they check RAW-INDEX and RAW-LENGTH too.
 140 ;;;   * Remove this special hacked copy function, just use
 141 ;;;     COPY-STRUCTURE instead.
 142 ;;; (For even more improvement, it might be good to move the raw slots
 143 ;;; into the same object as the ordinary slots, instead of having the
 144 ;;; unfortunate extra level of indirection. But that'd probably
 145 ;;; require a lot of work, including updating the garbage collector to
 146 ;;; understand it. And it might even hurt overall performance, because
 147 ;;; the positive effect of removing indirection could be cancelled by
 148 ;;; the negative effect of imposing an unnecessary GC write barrier on
 149 ;;; raw data which doesn't actually affect GC.)
 150 (defun copy-type-class-coldly (x)
 151   ;; KLUDGE: If the slots of TYPE-CLASS ever change in a way not
 152   ;; reflected in *TYPE-CLASS-FUN-SLOTS*, the slots here will
 153   ;; have to be hand-tweaked to match. -- WHN 2001-03-19
 154   (make-type-class :name (type-class-name x)
 155                    . #.(mapcan (lambda (type-class-fun-slot)
 156                                  (destructuring-bind (keyword . slot-accessor)
 157                                      type-class-fun-slot
 158                                    `(,keyword (,slot-accessor x))))
 159                                *type-class-fun-slots*)))
 160
 161 (defun class-fun-slot-or-lose (name)
 162   (or (cdr (assoc name *type-class-fun-slots*))
 163       (error "~S is not a defined type class method." name)))
 164 ;;; FIXME: This seems to be called at runtime by cold init code.
 165 ;;; Make sure that it's not being called at runtime anywhere but
 166 ;;; one-time toplevel initialization code.
 167
 168 ) ; EVAL-WHEN
 169
 170 (defmacro !define-type-method ((class method &rest more-methods)
 171                                lambda-list &body body)
 172   (let ((name (symbolicate class "-" method "-TYPE-METHOD")))
 173     `(progn
 174        (defun ,name ,lambda-list
 175          ,@body)
 176        (!cold-init-forms
 177         ,@(mapcar (lambda (method)
 178                     `(setf (,(class-fun-slot-or-lose method)
 179                             (type-class-or-lose ',class))
 180                            #',name))
 181                   (cons method more-methods)))
 182        ',name)))
 183
 184 (defmacro !define-type-class (name &key inherits)
 185   `(!cold-init-forms
 186      ,(once-only ((n-class (if inherits
 187                                `(copy-type-class-coldly (type-class-or-lose
 188                                                          ',inherits))
 189                                '(make-type-class))))
 190         `(progn
 191            (setf (type-class-name ,n-class) ',name)
 192            (setf (gethash ',name *type-classes*) ,n-class)
 193            ',name))))
 194
 195 ;;; Invoke a type method on TYPE1 and TYPE2. If the two types have the
 196 ;;; same class, invoke the simple method. Otherwise, invoke any
 197 ;;; complex method. If there isn't a distinct COMPLEX-ARG1 method,
 198 ;;; then swap the arguments when calling TYPE1's method. If no
 199 ;;; applicable method, return DEFAULT.
 200 ;;;
 201 ;;; KLUDGE: It might be a lot easier to understand this and the rest
 202 ;;; of the type system code if we used CLOS to express it instead of
 203 ;;; trying to maintain this squirrely hand-crufted object system.
 204 ;;; Unfortunately that'd require reworking PCL bootstrapping so that
 205 ;;; all the compilation can get done by the cross-compiler, which I
 206 ;;; suspect is hard, so we'll bear with the old system for the time
 207 ;;; being. -- WHN 2001-03-11
 208 (defmacro !invoke-type-method (simple complex-arg2 type1 type2 &key
 209                                       (default '(values nil t))
 210                                       (complex-arg1 :foo complex-arg1-p))
 211   (declare (type keyword simple complex-arg1 complex-arg2))
 212   `(multiple-value-bind (result-a result-b valid-p)
 213        (%invoke-type-method ',(class-fun-slot-or-lose simple)
 214                             ',(class-fun-slot-or-lose
 215                                (if complex-arg1-p
 216                                    complex-arg1
 217                                    complex-arg2))
 218                             ',(class-fun-slot-or-lose complex-arg2)
 219                             ,complex-arg1-p
 220                             ,type1
 221                             ,type2)
 222      (if valid-p
 223          (values result-a result-b)
 224          ,default)))
 225
 226 ;;; most of the implementation of !INVOKE-TYPE-METHOD
 227 ;;;
 228 ;;; KLUDGE: This function must be INLINE in order for cold init to
 229 ;;; work, because the first three arguments are TYPE-CLASS structure
 230 ;;; accessor functions whose calls have to be compiled inline in order
 231 ;;; to work in calls to this function early in cold init. So don't
 232 ;;; conditionalize this INLINE declaration with #!-SB-FLUID or
 233 ;;; anything, unless you also rearrange things to cause the full
 234 ;;; function definitions of the relevant structure accessors to be
 235 ;;; available sufficiently early in cold init. -- WHN 19991015
 236 (declaim (inline %invoke-type-method))
 237 (defun %invoke-type-method (simple cslot1 cslot2 complex-arg1-p type1 type2)
 238   (declare (type symbol simple cslot1 cslot2))
 239   (multiple-value-bind (result-a result-b)
 240       (let ((class1 (type-class-info type1))
 241             (class2 (type-class-info type2)))
 242         (if (eq class1 class2)
 243             (funcall (the function (funcall simple class1)) type1 type2)
 244             (let ((complex2 (funcall cslot2 class2)))
 245               (declare (type (or function null) complex2))
 246               (if complex2
 247                   (funcall complex2 type1 type2)
 248                   (let ((complex1 (funcall cslot1 class1)))
 249                     (declare (type (or function null) complex1))
 250                     (if complex1
 251                         (if complex-arg1-p
 252                             (funcall complex1 type1 type2)
 253                             (funcall complex1 type2 type1))
 254                         ;; No meaningful result was found: the caller
 255                         ;; should use the default value instead.
 256                         (return-from %invoke-type-method
 257                           (values nil nil nil))))))))
 258     ;; If we get to here (without breaking out by calling RETURN-FROM)
 259     ;; then a meaningful result was found, and we return it.
 260     (values result-a result-b t)))
 261
 262 ;;; This is a very specialized implementation of CLOS-style
 263 ;;; CALL-NEXT-METHOD within our twisty little type class object
 264 ;;; system, which works given that it's called from within a
 265 ;;; COMPLEX-SUBTYPEP-ARG2 method. (We're particularly motivated to
 266 ;;; implement CALL-NEXT-METHOD in that case, because ANSI imposes some
 267 ;;; strict limits on when SUBTYPEP is allowed to return (VALUES NIL NIL),
 268 ;;; so instead of just complacently returning (VALUES NIL NIL) from a
 269 ;;; COMPLEX-SUBTYPEP-ARG2 method we usually need to CALL-NEXT-METHOD.)
 270 ;;;
 271 ;;; KLUDGE: In CLOS, this could just be CALL-NEXT-METHOD and
 272 ;;; everything would Just Work without us having to think about it. In
 273 ;;; our goofy type dispatch system, it's messier to express. It's also
 274 ;;; more fragile, since (0) there's no check that it's called from
 275 ;;; within a COMPLEX-SUBTYPEP-ARG2 method as it should be, and (1) we
 276 ;;; rely on our global knowledge that the next (and only) relevant
 277 ;;; method is COMPLEX-SUBTYPEP-ARG1, and (2) we rely on our global
 278 ;;; knowledge of the appropriate default for the CSUBTYPEP function
 279 ;;; when no next method exists. -- WHN 2002-04-07
 280 ;;;
 281 ;;; (We miss CLOS! -- CSR and WHN)
 282 (defun invoke-complex-subtypep-arg1-method (type1 type2 &optional subtypep win)
 283   (let* ((type-class (type-class-info type1))
 284          (method-fun (type-class-complex-subtypep-arg1 type-class)))
 285     (if method-fun
 286         (funcall (the function method-fun) type1 type2)
 287         (values subtypep win))))
 288
 289 ;;; KLUDGE: This function is dangerous, as its overuse could easily
 290 ;;; cause stack exhaustion through unbounded recursion.  We only use
 291 ;;; it in one place; maybe it ought not to be a function at all?
 292 (defun invoke-complex-=-other-method (type1 type2)
 293   (let* ((type-class (type-class-info type1))
 294          (method-fun (type-class-complex-= type-class)))
 295     (if method-fun
 296         (funcall (the function method-fun) type2 type1)
 297         (values nil t))))
 298
 299 (!defun-from-collected-cold-init-forms !type-class-cold-init)