| blob | c267916245746b9895ce8b49323a3133550f1aae |
1 ;;;; stuff related to the TYPE-CLASS structure
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.
16 ;; We can't make an instance of any CTYPE descendant until its type-class
17 ;; exists in *TYPE-CLASSES* and the quasi-random state has been made.
18 ;; By initializing the state and type-class storage vector at once,
19 ;; it is obvious that either both have been made or neither one has been.
20 #-sb-xc
24 #+sb-xc
33 ;; The value forms are for type-correctness only.
34 ;; COLD-INIT-FORMS will already have been run.
37 (!cold-init-forms
46 #-sb-xc-host
48 ;; If NAME is a quoted constant, the resultant form should be
49 ;; a fixed index into *TYPE-CLASSES* except that during the building
50 ;; of the cross-compiler the array hasn't been populated yet.
51 ;; One solution to that, which I favored, is that DEFINE-TYPE-CLASS
52 ;; appear before the structure definition that uses the corresponding
53 ;; type-class in its slot initializer. That posed a problem for
54 ;; the :INHERITS option, because the constructor of a descendant
55 ;; grabs all the methods [sic] from its ancestor at the time the
56 ;; descendant is defined, which means the methods of the ancestor
57 ;; should have been filled in, which means at least one DEFINE-TYPE-CLASS
58 ;; wants to appear _after_ a structure definition that uses it.
64 form))
70 ;;; A TYPE-CLASS object represents the "kind" of a type. It mainly
71 ;;; contains functions which are methods on that kind of type, but is
72 ;;; also used in EQ comparisons to determined if two types have the
73 ;;; "same kind".
75 #-no-ansi-print-object
79 ;; the name of this type class (used to resolve references at load time)
81 ;; Dyadic type methods. If the classes of the two types are EQ, then
82 ;; we call the SIMPLE-xxx method. If the classes are not EQ, and
83 ;; either type's class has a COMPLEX-xxx method, then we call it.
84 ;;
85 ;; Although it is undefined which method will get precedence when
86 ;; both types have a complex method, the complex method can assume
87 ;; that the second arg always is in its class, and the first always
88 ;; is not. The arguments to commutative operations will be swapped
89 ;; if the first argument has a complex method.
90 ;;
91 ;; Since SUBTYPEP is not commutative, we have two complex methods.
92 ;; The ARG1 method is only called when the first argument is in its
93 ;; class, and the ARG2 method is only called when called when the
94 ;; second type is. If either is specified, both must be.
98 ;; SIMPLE-UNION2, COMPLEX-UNION2, SIMPLE-INTERSECTION2, and
99 ;; COMPLEX-INTERSECTION2 methods take pairs of types and try to find
100 ;; a new type which expresses the result nicely, better than could
101 ;; be done by just stuffing the two component types into an
102 ;; UNION-TYPE or INTERSECTION-TYPE object. They return NIL on
103 ;; failure, or a CTYPE for success.
104 ;;
105 ;; Note: These methods are similar to CMU CL's SIMPLE-UNION,
106 ;; COMPLEX-UNION, SIMPLE-INTERSECTION, and COMPLEX-UNION methods.
107 ;; They were reworked in SBCL because SBCL has INTERSECTION-TYPE
108 ;; objects (where CMU CL just punted to HAIRY-TYPE) and because SBCL
109 ;; wants to simplify unions and intersections by considering all
110 ;; possible pairwise simplifications (where the CMU CL code only
111 ;; considered simplifications between types which happened to appear
112 ;; next to each other the argument sequence).
113 ;;
114 ;; Differences in detail from old CMU CL methods:
115 ;; * SBCL's methods are more parallel between union and
116 ;; intersection forms. Each returns one values, (OR NULL CTYPE).
117 ;; * SBCL doesn't use type methods to deal with unions or
118 ;; intersections of the COMPOUND-TYPE of the corresponding form.
119 ;; Instead the wrapper functions TYPE-UNION2, TYPE-INTERSECTION2,
120 ;; TYPE-UNION, and TYPE-INTERSECTION handle those cases specially
121 ;; (and deal with canonicalization/simplification issues at the
122 ;; same time).
129 ;; monadic functions
131 ;; a function which returns a Common Lisp type specifier
132 ;; representing this type
135 ;; Can types of this type-class contain other types?
136 ;; A global property of our
137 ;; implementation (which unfortunately seems impossible to enforce
138 ;; with assertions or other in-the-code checks and constraints) is
139 ;; that subclasses which don't contain other types correspond to
140 ;; disjoint subsets (except of course for the NAMED-TYPE T, which
141 ;; covers everything). So NUMBER-TYPE is disjoint from CONS-TYPE is
142 ;; is disjoint from MEMBER-TYPE and so forth. But types which can
143 ;; contain other types, like HAIRY-TYPE and INTERSECTION-TYPE, can
144 ;; violate this rule.
146 ;; a function which returns T if the CTYPE could possibly be
147 ;; equivalent to a MEMBER type. If not a function, then it's
148 ;; a constant T or NIL for all instances of this type class.
149 ;; Note that the old comment for this slot was
150 ;; "True if this type has a fixed number of members, and as such
151 ;; could possibly be completely specified in a MEMBER type."
152 ;; The second half of that is right because of the "possibly,"
153 ;; but "has a fixed number" is too strong a claim, because we
154 ;; set enumerable=T for NEGATION and HAIRY and some other things.
155 ;; Conceptually the choices are really {yes, no, unknown}, but
156 ;; whereas "no" means "definitely not", T means "yes or maybe".
158 ;; a function which returns T if the CTYPE is inhabited by a single
159 ;; object and, as a value, the object. Otherwise, returns NIL, NIL.
160 ;; The default case (NIL) is interpreted as a function that always
161 ;; returns NIL, NIL.
164 #|
166 unary operations, since there are lots of interesting unary predicates that
167 aren't equivalent to an entire class
168 ;; Names of functions used for testing the type of objects in this type
169 ;; class. UNARY-PREDICATE takes just the object, whereas PREDICATE gets
170 ;; passed both the object and the CTYPE. Normally one or the other will be
171 ;; supplied for any type that can be passed to TYPEP; there is no point in
172 ;; supplying both.
175 ;; These are like TYPEP and UNARY-TYPEP except they coerce objects to
176 ;; the type.
179 |#
180 )
183 #+sb-xc
186 ;; there exist two boolean slots, plus NAME
193 ;; Unfortunately redundant with the slots in the DEF!STRUCT,
194 ;; but allows asserting about correctness of the constructor
195 ;; without relying on introspection in host Lisp.
198 complex-subtypep-arg1
199 complex-subtypep-arg2
200 simple-union2
201 complex-union2
202 simple-intersection2
203 complex-intersection2
204 simple-=
205 complex-=
206 negate
207 unparse
208 singleton-p)
217 (!cold-init-forms
227 enumerable-supplied-p)
230 might-contain-other-types-supplied-p))
236 enumerable
238 :might-contain-other-types-p
240 might-contain-other-types
246 #-sb-xc
251 #+sb-xc
252 `(!cold-init-forms
257 ;;; Invoke a type method on TYPE1 and TYPE2. If the two types have the
258 ;;; same class, invoke the simple method. Otherwise, invoke any
259 ;;; complex method. If there isn't a distinct COMPLEX-ARG1 method,
260 ;;; then swap the arguments when calling TYPE1's method. If no
261 ;;; applicable method, return DEFAULT.
262 ;;;
263 ;;; KLUDGE: It might be a lot easier to understand this and the rest
264 ;;; of the type system code if we used CLOS to express it instead of
265 ;;; trying to maintain this squirrely hand-crufted object system.
266 ;;; Unfortunately that'd require reworking PCL bootstrapping so that
267 ;;; all the compilation can get done by the cross-compiler, which I
268 ;;; suspect is hard, so we'll bear with the old system for the time
269 ;;; being. -- WHN 2001-03-11
294 ;;; This is a very specialized implementation of CLOS-style
295 ;;; CALL-NEXT-METHOD within our twisty little type class object
296 ;;; system, which works given that it's called from within a
297 ;;; COMPLEX-SUBTYPEP-ARG2 method. (We're particularly motivated to
298 ;;; implement CALL-NEXT-METHOD in that case, because ANSI imposes some
299 ;;; strict limits on when SUBTYPEP is allowed to return (VALUES NIL NIL),
300 ;;; so instead of just complacently returning (VALUES NIL NIL) from a
301 ;;; COMPLEX-SUBTYPEP-ARG2 method we usually need to CALL-NEXT-METHOD.)
302 ;;;
303 ;;; KLUDGE: In CLOS, this could just be CALL-NEXT-METHOD and
304 ;;; everything would Just Work without us having to think about it. In
305 ;;; our goofy type dispatch system, it's messier to express. It's also
306 ;;; more fragile, since (0) there's no check that it's called from
307 ;;; within a COMPLEX-SUBTYPEP-ARG2 method as it should be, and (1) we
308 ;;; rely on our global knowledge that the next (and only) relevant
309 ;;; method is COMPLEX-SUBTYPEP-ARG1, and (2) we rely on our global
310 ;;; knowledge of the appropriate default for the CSUBTYPEP function
311 ;;; when no next method exists. -- WHN 2002-04-07
312 ;;;
313 ;;; (We miss CLOS! -- CSR and WHN)
321 ;;; KLUDGE: This function is dangerous, as its overuse could easily
322 ;;; cause stack exhaustion through unbounded recursion. We only use
323 ;;; it in one place; maybe it ought not to be a function at all?