1 | ;;; subtypep.lisp |
---|
2 | ;;; |
---|
3 | ;;; Copyright (C) 2003-2005 Peter Graves |
---|
4 | ;;; $Id: subtypep.lisp 15729 2023-07-13 13:15:16Z mevenson $ |
---|
5 | ;;; |
---|
6 | ;;; This program is free software; you can redistribute it and/or |
---|
7 | ;;; modify it under the terms of the GNU General Public License |
---|
8 | ;;; as published by the Free Software Foundation; either version 2 |
---|
9 | ;;; of the License, or (at your option) any later version. |
---|
10 | ;;; |
---|
11 | ;;; This program is distributed in the hope that it will be useful, |
---|
12 | ;;; but WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
13 | ;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
---|
14 | ;;; GNU General Public License for more details. |
---|
15 | ;;; |
---|
16 | ;;; You should have received a copy of the GNU General Public License |
---|
17 | ;;; along with this program; if not, write to the Free Software |
---|
18 | ;;; Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
---|
19 | ;;; |
---|
20 | ;;; As a special exception, the copyright holders of this library give you |
---|
21 | ;;; permission to link this library with independent modules to produce an |
---|
22 | ;;; executable, regardless of the license terms of these independent |
---|
23 | ;;; modules, and to copy and distribute the resulting executable under |
---|
24 | ;;; terms of your choice, provided that you also meet, for each linked |
---|
25 | ;;; independent module, the terms and conditions of the license of that |
---|
26 | ;;; module. An independent module is a module which is not derived from |
---|
27 | ;;; or based on this library. If you modify this library, you may extend |
---|
28 | ;;; this exception to your version of the library, but you are not |
---|
29 | ;;; obligated to do so. If you do not wish to do so, delete this |
---|
30 | ;;; exception statement from your version. |
---|
31 | |
---|
32 | (in-package #:system) |
---|
33 | |
---|
34 | (defparameter *known-types* (make-hash-table :test 'eq)) |
---|
35 | |
---|
36 | (defun initialize-known-types () |
---|
37 | (let ((ht (make-hash-table :test 'eq))) |
---|
38 | (dolist (i '((ARITHMETIC-ERROR ERROR) |
---|
39 | (ARRAY) |
---|
40 | (BASE-STRING STRING) |
---|
41 | (BIGNUM INTEGER) |
---|
42 | (BIT FIXNUM) |
---|
43 | (BIT-VECTOR VECTOR) |
---|
44 | (BOOLEAN SYMBOL) |
---|
45 | (BUILT-IN-CLASS CLASS) |
---|
46 | (CELL-ERROR ERROR) |
---|
47 | (CHARACTER) |
---|
48 | (CLASS STANDARD-OBJECT) |
---|
49 | (COMPILED-FUNCTION FUNCTION) |
---|
50 | (COMPLEX NUMBER) |
---|
51 | (CONDITION) |
---|
52 | (CONS LIST) |
---|
53 | (CONTROL-ERROR ERROR) |
---|
54 | (DIVISION-BY-ZERO ARITHMETIC-ERROR) |
---|
55 | (DOUBLE-FLOAT FLOAT) |
---|
56 | (END-OF-FILE STREAM-ERROR) |
---|
57 | (ERROR SERIOUS-CONDITION) |
---|
58 | (EXTENDED-CHAR CHARACTER NIL) |
---|
59 | (FILE-ERROR ERROR) |
---|
60 | (FIXNUM INTEGER) |
---|
61 | (FLOAT REAL) |
---|
62 | (FLOATING-POINT-INEXACT ARITHMETIC-ERROR) |
---|
63 | (FLOATING-POINT-INVALID-OPERATION ARITHMETIC-ERROR) |
---|
64 | (FLOATING-POINT-OVERFLOW ARITHMETIC-ERROR) |
---|
65 | (FLOATING-POINT-UNDERFLOW ARITHMETIC-ERROR) |
---|
66 | (FUNCTION) |
---|
67 | (GENERIC-FUNCTION FUNCTION) |
---|
68 | (HASH-TABLE) |
---|
69 | (INTEGER RATIONAL) |
---|
70 | (KEYWORD SYMBOL) |
---|
71 | (LIST SEQUENCE) |
---|
72 | (LONG-FLOAT FLOAT) |
---|
73 | (NIL-VECTOR SIMPLE-STRING) |
---|
74 | (NULL BOOLEAN LIST) |
---|
75 | (NUMBER) |
---|
76 | (PACKAGE) |
---|
77 | (PACKAGE-ERROR ERROR) |
---|
78 | (PARSE-ERROR ERROR) |
---|
79 | (PATHNAME) |
---|
80 | (PRINT-NOT-READABLE ERROR) |
---|
81 | (PROGRAM-ERROR ERROR) |
---|
82 | (RANDOM-STATE) |
---|
83 | (RATIO RATIONAL) |
---|
84 | (RATIONAL REAL) |
---|
85 | (READER-ERROR PARSE-ERROR STREAM-ERROR) |
---|
86 | (READTABLE) |
---|
87 | (REAL NUMBER) |
---|
88 | (RESTART) |
---|
89 | (SERIOUS-CONDITION CONDITION) |
---|
90 | (SHORT-FLOAT FLOAT) |
---|
91 | (SIMPLE-ARRAY ARRAY) |
---|
92 | (SIMPLE-BASE-STRING SIMPLE-STRING BASE-STRING) |
---|
93 | (SIMPLE-BIT-VECTOR BIT-VECTOR SIMPLE-ARRAY) |
---|
94 | (SIMPLE-CONDITION CONDITION) |
---|
95 | (SIMPLE-ERROR SIMPLE-CONDITION ERROR) |
---|
96 | (SIMPLE-STRING BASE-STRING STRING SIMPLE-ARRAY) |
---|
97 | (SIMPLE-TYPE-ERROR SIMPLE-CONDITION TYPE-ERROR) |
---|
98 | (SIMPLE-VECTOR VECTOR SIMPLE-ARRAY) |
---|
99 | (SIMPLE-WARNING SIMPLE-CONDITION WARNING) |
---|
100 | (SINGLE-FLOAT FLOAT) |
---|
101 | (STANDARD-CHAR CHARACTER) |
---|
102 | (STANDARD-CLASS CLASS) |
---|
103 | (STANDARD-GENERIC-FUNCTION GENERIC-FUNCTION) |
---|
104 | (STANDARD-OBJECT) |
---|
105 | (STORAGE-CONDITION SERIOUS-CONDITION) |
---|
106 | (STREAM) |
---|
107 | (STREAM-ERROR ERROR) |
---|
108 | (STRING VECTOR) |
---|
109 | (STRUCTURE-CLASS CLASS STANDARD-OBJECT) |
---|
110 | (STYLE-WARNING WARNING) |
---|
111 | (SYMBOL) |
---|
112 | (TWO-WAY-STREAM STREAM) |
---|
113 | (TYPE-ERROR ERROR) |
---|
114 | (UNBOUND-SLOT CELL-ERROR) |
---|
115 | (UNBOUND-VARIABLE CELL-ERROR) |
---|
116 | (UNDEFINED-FUNCTION CELL-ERROR) |
---|
117 | (VECTOR ARRAY SEQUENCE) |
---|
118 | (WARNING CONDITION))) |
---|
119 | (setf (gethash (%car i) ht) (%cdr i))) |
---|
120 | (setf *known-types* ht))) |
---|
121 | |
---|
122 | (initialize-known-types) |
---|
123 | |
---|
124 | (defun known-type-p (type) |
---|
125 | (multiple-value-bind (value present-p) (gethash type *known-types*) |
---|
126 | present-p)) |
---|
127 | |
---|
128 | (defun sub-interval-p (i1 i2) |
---|
129 | (let (low1 high1 low2 high2) |
---|
130 | (if (null i1) |
---|
131 | (setq low1 '* high1 '*) |
---|
132 | (if (null (cdr i1)) |
---|
133 | (setq low1 (car i1) high1 '*) |
---|
134 | (setq low1 (car i1) high1 (cadr i1)))) |
---|
135 | (if (null i2) |
---|
136 | (setq low2 '* high2 '*) |
---|
137 | (if (null (cdr i2)) |
---|
138 | (setq low2 (car i2) high2 '*) |
---|
139 | (setq low2 (car i2) high2 (cadr i2)))) |
---|
140 | (when (and (consp low1) (integerp (%car low1))) |
---|
141 | (setq low1 (1+ (car low1)))) |
---|
142 | (when (and (consp low2) (integerp (%car low2))) |
---|
143 | (setq low2 (1+ (car low2)))) |
---|
144 | (when (and (consp high1) (integerp (%car high1))) |
---|
145 | (setq high1 (1- (car high1)))) |
---|
146 | (when (and (consp high2) (integerp (%car high2))) |
---|
147 | (setq high2 (1- (car high2)))) |
---|
148 | (cond ((eq low1 '*) |
---|
149 | (unless (eq low2 '*) |
---|
150 | (return-from sub-interval-p nil))) |
---|
151 | ((eq low2 '*)) |
---|
152 | ((consp low1) |
---|
153 | (if (consp low2) |
---|
154 | (when (< (%car low1) (%car low2)) |
---|
155 | (return-from sub-interval-p nil)) |
---|
156 | (when (< (%car low1) low2) |
---|
157 | (return-from sub-interval-p nil)))) |
---|
158 | ((if (consp low2) |
---|
159 | (when (<= low1 (%car low2)) |
---|
160 | (return-from sub-interval-p nil)) |
---|
161 | (when (< low1 low2) |
---|
162 | (return-from sub-interval-p nil))))) |
---|
163 | (cond ((eq high1 '*) |
---|
164 | (unless (eq high2 '*) |
---|
165 | (return-from sub-interval-p nil))) |
---|
166 | ((eq high2 '*)) |
---|
167 | ((consp high1) |
---|
168 | (if (consp high2) |
---|
169 | (when (> (%car high1) (%car high2)) |
---|
170 | (return-from sub-interval-p nil)) |
---|
171 | (when (> (%car high1) high2) |
---|
172 | (return-from sub-interval-p nil)))) |
---|
173 | ((if (consp high2) |
---|
174 | (when (>= high1 (%car high2)) |
---|
175 | (return-from sub-interval-p nil)) |
---|
176 | (when (> high1 high2) |
---|
177 | (return-from sub-interval-p nil))))) |
---|
178 | (return-from sub-interval-p t))) |
---|
179 | |
---|
180 | (defun dimension-subtypep (dim1 dim2) |
---|
181 | (cond ((eq dim2 '*) |
---|
182 | t) |
---|
183 | ((equal dim1 dim2) |
---|
184 | t) |
---|
185 | ((integerp dim2) |
---|
186 | (and (listp dim1) (= (length dim1) dim2))) |
---|
187 | ((eql dim1 0) |
---|
188 | (null dim2)) |
---|
189 | ((integerp dim1) |
---|
190 | (and (consp dim2) |
---|
191 | (= (length dim2) dim1) |
---|
192 | (equal dim2 (make-list dim1 :initial-element '*)))) |
---|
193 | ((and (consp dim1) (consp dim2) (= (length dim1) (length dim2))) |
---|
194 | (do* ((list1 dim1 (cdr list1)) |
---|
195 | (list2 dim2 (cdr list2)) |
---|
196 | (e1 (car list1) (car list1)) |
---|
197 | (e2 (car list2) (car list2))) |
---|
198 | ((null list1) t) |
---|
199 | (unless (or (eq e2 '*) (eql e1 e2)) |
---|
200 | (return nil)))) |
---|
201 | (t |
---|
202 | nil))) |
---|
203 | |
---|
204 | (defun simple-subtypep (type1 type2) |
---|
205 | (if (eq type1 type2) |
---|
206 | t |
---|
207 | (multiple-value-bind (type1-supertypes type1-known-p) |
---|
208 | (gethash type1 *known-types*) |
---|
209 | (if type1-known-p |
---|
210 | (if (memq type2 type1-supertypes) |
---|
211 | t |
---|
212 | (dolist (supertype type1-supertypes) |
---|
213 | (when (simple-subtypep supertype type2) |
---|
214 | (return t)))) |
---|
215 | nil)))) |
---|
216 | |
---|
217 | ;; (defstruct ctype |
---|
218 | ;; ((:constructor make-ctype (super type))) |
---|
219 | ;; super |
---|
220 | ;; type) |
---|
221 | |
---|
222 | (defun make-ctype (super type) |
---|
223 | (cons super type)) |
---|
224 | |
---|
225 | (defun ctype-super (ctype) |
---|
226 | (car ctype)) |
---|
227 | |
---|
228 | (defun ctype-type (ctype) |
---|
229 | (cdr ctype)) |
---|
230 | |
---|
231 | (defun ctype (type) |
---|
232 | (cond ((classp type) |
---|
233 | nil) |
---|
234 | (t |
---|
235 | (let ((tp (if (atom type) type (car type)))) |
---|
236 | (case tp |
---|
237 | ((ARRAY VECTOR STRING SIMPLE-ARRAY SIMPLE-STRING BASE-STRING |
---|
238 | SIMPLE-BASE-STRING BIT-VECTOR SIMPLE-BIT-VECTOR NIL-VECTOR) |
---|
239 | (make-ctype 'ARRAY type)) |
---|
240 | ((REAL INTEGER BIT FIXNUM SIGNED-BYTE UNSIGNED-BYTE BIGNUM RATIO |
---|
241 | FLOAT SINGLE-FLOAT DOUBLE-FLOAT SHORT-FLOAT LONG-FLOAT) |
---|
242 | (make-ctype 'REAL type)) |
---|
243 | (COMPLEX |
---|
244 | (make-ctype 'COMPLEX |
---|
245 | (if (atom type) '* (cadr type)))) |
---|
246 | (FUNCTION |
---|
247 | (make-ctype 'FUNCTION type))))))) |
---|
248 | |
---|
249 | (defun csubtypep-array (ct1 ct2) |
---|
250 | (let ((type1 (normalize-type (ctype-type ct1))) |
---|
251 | (type2 (normalize-type (ctype-type ct2)))) |
---|
252 | (when (eq type1 type2) |
---|
253 | (return-from csubtypep-array (values t t))) |
---|
254 | (let (t1 t2 i1 i2) |
---|
255 | (if (atom type1) |
---|
256 | (setf t1 type1 i1 nil) |
---|
257 | (setf t1 (car type1) i1 (cdr type1))) |
---|
258 | (if (atom type2) |
---|
259 | (setf t2 type2 i2 nil) |
---|
260 | (setf t2 (car type2) i2 (cdr type2))) |
---|
261 | (cond ((and (classp t1) (eq (%class-name t1) 'array) (eq t2 'array)) |
---|
262 | (values (equal i2 '(* *)) t)) |
---|
263 | ((and (memq t1 '(array simple-array)) (eq t2 'array)) |
---|
264 | (let ((e1 (car i1)) |
---|
265 | (e2 (car i2)) |
---|
266 | (d1 (cadr i1)) |
---|
267 | (d2 (cadr i2))) |
---|
268 | (cond ((and (eq e2 '*) (eq d2 '*)) |
---|
269 | (values t t)) |
---|
270 | ((or (eq e2 '*) |
---|
271 | (equal e1 e2) |
---|
272 | (equal (upgraded-array-element-type e1) |
---|
273 | (upgraded-array-element-type e2))) |
---|
274 | (values (dimension-subtypep d1 d2) t)) |
---|
275 | (t |
---|
276 | (values nil t))))) |
---|
277 | ((and (memq t1 '(simple-base-string base-string simple-string string nil-vector)) |
---|
278 | (memq t2 '(simple-base-string base-string simple-string string nil-vector))) |
---|
279 | (if (and (simple-subtypep t1 t2) |
---|
280 | (or (eql (car i1) (car i2)) |
---|
281 | (eq (car i2) '*))) |
---|
282 | (return-from csubtypep-array (values t t)) |
---|
283 | (return-from csubtypep-array (values nil t)))) |
---|
284 | ((and (memq t1 '(array simple-array)) (eq t2 'string)) |
---|
285 | (let ((element-type (car i1)) |
---|
286 | (dim (cadr i1)) |
---|
287 | (size (car i2))) |
---|
288 | (unless (%subtypep element-type 'character) |
---|
289 | (return-from csubtypep-array (values nil t))) |
---|
290 | (when (integerp size) |
---|
291 | (if (and (consp dim) (= (length dim) 1) (eql (%car dim) size)) |
---|
292 | (return-from csubtypep-array (values t t)) |
---|
293 | (return-from csubtypep-array (values nil t)))) |
---|
294 | (when (or (null size) (eql size '*)) |
---|
295 | (if (or (eql dim 1) |
---|
296 | (and (consp dim) (= (length dim) 1))) |
---|
297 | (return-from csubtypep-array (values t t)) |
---|
298 | (return-from csubtypep-array (values nil t)))))) |
---|
299 | ((and (eq t1 'simple-array) (eq t2 'simple-string)) |
---|
300 | (let ((element-type (car i1)) |
---|
301 | (dim (cadr i1)) |
---|
302 | (size (car i2))) |
---|
303 | (unless (%subtypep element-type 'character) |
---|
304 | (return-from csubtypep-array (values nil t))) |
---|
305 | (when (integerp size) |
---|
306 | (if (and (consp dim) (= (length dim) 1) (eql (%car dim) size)) |
---|
307 | (return-from csubtypep-array (values t t)) |
---|
308 | (return-from csubtypep-array (values nil t)))) |
---|
309 | (when (or (null size) (eql size '*)) |
---|
310 | (if (or (eql dim 1) |
---|
311 | (and (consp dim) (= (length dim) 1))) |
---|
312 | (return-from csubtypep-array (values t t)) |
---|
313 | (return-from csubtypep-array (values nil t)))))) |
---|
314 | ((and (memq t1 '(string simple-string nil-vector)) (eq t2 'array)) |
---|
315 | (let ((element-type (car i2)) |
---|
316 | (dim (cadr i2)) |
---|
317 | (size (car i1))) |
---|
318 | (unless (eq element-type '*) |
---|
319 | (return-from csubtypep-array (values nil t))) |
---|
320 | (when (integerp size) |
---|
321 | (if (or (eq dim '*) |
---|
322 | (eql dim 1) |
---|
323 | (and (consp dim) |
---|
324 | (= (length dim) 1) |
---|
325 | (or (eq (%car dim) '*) |
---|
326 | (eql (%car dim) size)))) |
---|
327 | (return-from csubtypep-array (values t t)) |
---|
328 | (return-from csubtypep-array (values nil t)))) |
---|
329 | (when (or (null size) (eql size '*)) |
---|
330 | (if (or (eq dim '*) |
---|
331 | (eql dim 1) |
---|
332 | (and (consp dim) (= (length dim) 1))) |
---|
333 | (return-from csubtypep-array (values t t)) |
---|
334 | (return-from csubtypep-array (values nil t)))))) |
---|
335 | ((and (memq t1 '(bit-vector simple-bit-vector)) (eq t2 'array)) |
---|
336 | (let ((element-type (car i2)) |
---|
337 | (dim (cadr i2)) |
---|
338 | (size (car i1))) |
---|
339 | (unless (or (memq element-type '(bit *)) |
---|
340 | (equal element-type '(integer 0 1))) |
---|
341 | (return-from csubtypep-array (values nil t))) |
---|
342 | (when (integerp size) |
---|
343 | (if (or (eq dim '*) |
---|
344 | (eql dim 1) |
---|
345 | (and (consp dim) |
---|
346 | (= (length dim) 1) |
---|
347 | (or (eq (%car dim) '*) |
---|
348 | (eql (%car dim) size)))) |
---|
349 | (return-from csubtypep-array (values t t)) |
---|
350 | (return-from csubtypep-array (values nil t)))) |
---|
351 | (when (or (null size) (eql size '*)) |
---|
352 | (if (or (eq dim '*) |
---|
353 | (eql dim 1) |
---|
354 | (and (consp dim) (= (length dim) 1))) |
---|
355 | (return-from csubtypep-array (values t t)) |
---|
356 | (return-from csubtypep-array (values nil t)))))) |
---|
357 | ((eq t2 'simple-array) |
---|
358 | (case t1 |
---|
359 | (simple-array |
---|
360 | (let ((e1 (car i1)) |
---|
361 | (e2 (car i2)) |
---|
362 | (d1 (cadr i1)) |
---|
363 | (d2 (cadr i2))) |
---|
364 | (cond ((and (eq e2 '*) (eq d2 '*)) |
---|
365 | (values t t)) |
---|
366 | ((or (eq e2 '*) |
---|
367 | (equal e1 e2) |
---|
368 | (equal (upgraded-array-element-type e1) |
---|
369 | (upgraded-array-element-type e2))) |
---|
370 | (values (dimension-subtypep d1 d2) t)) |
---|
371 | (t |
---|
372 | (values nil t))))) |
---|
373 | ((simple-string simple-bit-vector nil-vector) |
---|
374 | (let ((element-type (car i2)) |
---|
375 | (dim (cadr i2)) |
---|
376 | (size (car i1))) |
---|
377 | (unless (eq element-type '*) |
---|
378 | (return-from csubtypep-array (values nil t))) |
---|
379 | (when (integerp size) |
---|
380 | (if (or (eq dim '*) |
---|
381 | (and (consp dim) (= (length dim) 1) (eql (%car dim) size))) |
---|
382 | (return-from csubtypep-array (values t t)) |
---|
383 | (return-from csubtypep-array (values nil t)))) |
---|
384 | (when (or (null size) (eql size '*)) |
---|
385 | (if (or (eq dim '*) |
---|
386 | (eql dim 1) |
---|
387 | (and (consp dim) (= (length dim) 1))) |
---|
388 | (return-from csubtypep-array (values t t)) |
---|
389 | (return-from csubtypep-array (values nil t)))))) |
---|
390 | (t |
---|
391 | (values nil t)))) |
---|
392 | ((eq t2 'bit-vector) |
---|
393 | (let ((size1 (car i1)) |
---|
394 | (size2 (car i2))) |
---|
395 | (case t1 |
---|
396 | ((bit-vector simple-bit-vector) |
---|
397 | (values (if (or (eq size2 '*) (eql size1 size2)) |
---|
398 | t |
---|
399 | nil) t)) |
---|
400 | (t |
---|
401 | (values nil t))))) |
---|
402 | ((eq t2 'simple-bit-vector) |
---|
403 | (let ((size1 (car i1)) |
---|
404 | (size2 (car i2))) |
---|
405 | (if (and (eq t1 'simple-bit-vector) |
---|
406 | (or (eq size2 '*) |
---|
407 | (eql size1 size2))) |
---|
408 | (values t t) |
---|
409 | (values nil t)))) |
---|
410 | ((classp t2) |
---|
411 | (let ((class-name (%class-name t2))) |
---|
412 | (cond ((eq class-name t1) |
---|
413 | (values t t)) |
---|
414 | ((and (eq class-name 'array) |
---|
415 | (memq t1 '(array simple-array vector simple-vector string |
---|
416 | simple-string simple-base-string bit-vector |
---|
417 | simple-bit-vector))) |
---|
418 | (values t t)) |
---|
419 | ((eq class-name 'vector) |
---|
420 | (cond ((memq t1 '(string simple-string)) |
---|
421 | (values t t)) |
---|
422 | ((eq t1 'array) |
---|
423 | (let ((dim (cadr i1))) |
---|
424 | (if (or (eql dim 1) |
---|
425 | (and (consp dim) (= (length dim) 1))) |
---|
426 | (values t t) |
---|
427 | (values nil t)))) |
---|
428 | (t |
---|
429 | (values nil t)))) |
---|
430 | ((and (eq class-name 'simple-vector) |
---|
431 | (eq t1 'simple-array)) |
---|
432 | (let ((dim (cadr i1))) |
---|
433 | (if (or (eql dim 1) |
---|
434 | (and (consp dim) (= (length dim) 1))) |
---|
435 | (values t t) |
---|
436 | (values nil t)))) |
---|
437 | ((and (eq class-name 'bit-vector) |
---|
438 | (eq t1 'simple-bit-vector)) |
---|
439 | (values t t)) |
---|
440 | ((and (eq class-name 'string) |
---|
441 | (memq t1 '(string simple-string))) |
---|
442 | (values t t)) |
---|
443 | (t |
---|
444 | (values nil nil))))) |
---|
445 | (t |
---|
446 | (values nil nil)))))) |
---|
447 | |
---|
448 | (defun csubtypep-function (ct1 ct2) |
---|
449 | (let ((type1 (ctype-type ct1)) |
---|
450 | (type2 (ctype-type ct2))) |
---|
451 | (cond ((and (listp type1) (atom type2)) |
---|
452 | (values t t)) |
---|
453 | (t |
---|
454 | (values nil nil))))) |
---|
455 | |
---|
456 | (defun csubtypep-complex (ct1 ct2) |
---|
457 | (let ((type1 (cdr ct1)) |
---|
458 | (type2 (cdr ct2))) |
---|
459 | (cond ((or (null type2) (eq type2 '*)) |
---|
460 | (values t t)) |
---|
461 | ((eq type1 '*) |
---|
462 | (values nil t)) |
---|
463 | (t |
---|
464 | (subtypep type1 type2))))) |
---|
465 | |
---|
466 | (defun csubtypep (ctype1 ctype2) |
---|
467 | (cond ((null (and ctype1 ctype2)) |
---|
468 | (values nil nil)) |
---|
469 | ((neq (ctype-super ctype1) (ctype-super ctype2)) |
---|
470 | (values nil t)) |
---|
471 | ((eq (ctype-super ctype1) 'array) |
---|
472 | (csubtypep-array ctype1 ctype2)) |
---|
473 | ((eq (ctype-super ctype1) 'function) |
---|
474 | (csubtypep-function ctype1 ctype2)) |
---|
475 | ((eq (ctype-super ctype1) 'complex) |
---|
476 | (csubtypep-complex ctype1 ctype2)) |
---|
477 | (t |
---|
478 | (values nil nil)))) |
---|
479 | |
---|
480 | (defun properly-named-class-p (thing environment) |
---|
481 | (and (classp thing) (class-name thing) |
---|
482 | (eq thing (find-class (class-name thing) nil environment)))) |
---|
483 | |
---|
484 | (defun %subtypep (type1 type2 &optional environment) |
---|
485 | (when (or (eq type1 type2) |
---|
486 | (null type1) |
---|
487 | (eq type2 t) |
---|
488 | (and (classp type2) (eq type2 (find-class t)))) |
---|
489 | (return-from %subtypep (values t t))) |
---|
490 | (when (properly-named-class-p type1 environment) |
---|
491 | (setf type1 (class-name type1))) |
---|
492 | (when (properly-named-class-p type2 environment) |
---|
493 | (setf type2 (class-name type2))) |
---|
494 | (let ((ct1 (ctype type1)) |
---|
495 | (ct2 (ctype type2))) |
---|
496 | (multiple-value-bind (subtype-p valid-p) |
---|
497 | (csubtypep ct1 ct2) |
---|
498 | (when valid-p |
---|
499 | (return-from %subtypep (values subtype-p valid-p))))) |
---|
500 | (when (and (atom type1) (atom type2)) |
---|
501 | (let* ((classp-1 (classp type1)) |
---|
502 | (classp-2 (classp type2)) |
---|
503 | class1 class2) |
---|
504 | (when (and (setf class1 (if classp-1 |
---|
505 | type1 |
---|
506 | (and (symbolp type1) (find-class type1 nil)))) |
---|
507 | (setf class2 (if classp-2 |
---|
508 | type2 |
---|
509 | (and (symbolp type2) (find-class type2 nil))))) |
---|
510 | (return-from %subtypep (values (subclassp class1 class2) t))) |
---|
511 | (when (or classp-1 classp-2) |
---|
512 | (let ((t1 (if classp-1 (class-name type1) type1)) |
---|
513 | (t2 (if classp-2 (class-name type2) type2))) |
---|
514 | (return-from %subtypep (values (simple-subtypep t1 t2) t)))))) |
---|
515 | (setf type1 (normalize-type type1) |
---|
516 | type2 (normalize-type type2)) |
---|
517 | (when (eq type1 type2) |
---|
518 | (return-from %subtypep (values t t))) |
---|
519 | (let (t1 t2 i1 i2) |
---|
520 | (if (atom type1) |
---|
521 | (setf t1 type1 i1 nil) |
---|
522 | (setf t1 (%car type1) i1 (%cdr type1))) |
---|
523 | (if (atom type2) |
---|
524 | (setf t2 type2 i2 nil) |
---|
525 | (setf t2 (%car type2) i2 (%cdr type2))) |
---|
526 | (cond ((null t1) |
---|
527 | (return-from %subtypep (values t t))) |
---|
528 | ((eq t1 'atom) |
---|
529 | (return-from %subtypep (values (eq t2 t) t))) |
---|
530 | ((eq t2 'atom) |
---|
531 | (return-from %subtypep (cond ((memq t1 '(cons list sequence)) |
---|
532 | (values nil t)) |
---|
533 | (t |
---|
534 | (values t t))))) |
---|
535 | ((eq t1 'member) |
---|
536 | (dolist (e i1) |
---|
537 | (unless (typep e type2) (return-from %subtypep (values nil t)))) |
---|
538 | (return-from %subtypep (values t t))) |
---|
539 | ((eq t1 'eql) |
---|
540 | (case t2 |
---|
541 | (EQL |
---|
542 | (return-from %subtypep (values (eql (car i1) (car i2)) t))) |
---|
543 | (SATISFIES |
---|
544 | (return-from %subtypep (values (funcall (car i2) (car i1)) t))) |
---|
545 | (t |
---|
546 | (return-from %subtypep (values (typep (car i1) type2) t))))) |
---|
547 | ((eq t1 'or) |
---|
548 | (dolist (tt i1) |
---|
549 | (multiple-value-bind (tv flag) (%subtypep tt type2) |
---|
550 | (unless tv (return-from %subtypep (values tv flag))))) |
---|
551 | (return-from %subtypep (values t t))) |
---|
552 | ((eq t1 'and) |
---|
553 | (dolist (tt i1) |
---|
554 | (let ((tv (%subtypep tt type2))) |
---|
555 | (when tv (return-from %subtypep (values t t))))) |
---|
556 | (when |
---|
557 | (and |
---|
558 | (eq t2 'null) |
---|
559 | (= (length i1) 2) |
---|
560 | (member 'symbol i1) |
---|
561 | (member 'list i1)) |
---|
562 | (return-from %subtypep (values t t))) |
---|
563 | (return-from %subtypep (values nil nil))) |
---|
564 | ((eq t1 'cons) |
---|
565 | (case t2 |
---|
566 | ((LIST SEQUENCE) |
---|
567 | (return-from %subtypep (values t t))) |
---|
568 | (CONS |
---|
569 | (when (and (%subtypep (car i1) (car i2)) |
---|
570 | (%subtypep (cadr i1) (cadr i2))) |
---|
571 | (return-from %subtypep (values t t))))) |
---|
572 | (return-from %subtypep (values nil (known-type-p t2)))) |
---|
573 | ((eq t2 'or) |
---|
574 | (dolist (tt i2) |
---|
575 | (let ((tv (%subtypep type1 tt))) |
---|
576 | (when tv (return-from %subtypep (values t t))))) |
---|
577 | (when |
---|
578 | (and |
---|
579 | (eq t1 'list) |
---|
580 | (= (length i2) 2) |
---|
581 | (member 'null i2) |
---|
582 | (member 'cons i2)) |
---|
583 | (return-from %subtypep (values t t))) |
---|
584 | (return-from %subtypep (values nil nil))) |
---|
585 | ((eq t2 'and) |
---|
586 | (dolist (tt i2) |
---|
587 | (multiple-value-bind (tv flag) (%subtypep type1 tt) |
---|
588 | (unless tv (return-from %subtypep (values tv flag))))) |
---|
589 | (return-from %subtypep (values t t))) |
---|
590 | ((eq t1 'mod) |
---|
591 | (return-from %subtypep |
---|
592 | (%subtypep `(integer 0 ,(1- (first i1))) |
---|
593 | type2))) |
---|
594 | ((eq t2 'mod) |
---|
595 | (return-from %subtypep |
---|
596 | (%subtypep type1 |
---|
597 | `(integer 0 ,(1- (first i2)))))) |
---|
598 | ((null (or i1 i2)) |
---|
599 | (return-from %subtypep (values (simple-subtypep t1 t2) t))) |
---|
600 | ((eq t2 'SEQUENCE) |
---|
601 | (cond ((memq t1 '(null cons list)) |
---|
602 | (values t t)) |
---|
603 | ((memq t1 '(simple-base-string base-string simple-string string nil-vector)) |
---|
604 | (values t t)) |
---|
605 | ((memq t1 '(bit-vector simple-bit-vector)) |
---|
606 | (values t t)) |
---|
607 | ((memq t1 '(array simple-array)) |
---|
608 | (cond ((and (cdr i1) (consp (cadr i1)) (null (cdadr i1))) |
---|
609 | (values t t)) |
---|
610 | ((and (cdr i1) (eql (cadr i1) 1)) |
---|
611 | (values t t)) |
---|
612 | (t |
---|
613 | (values nil t)))) |
---|
614 | (t (values nil (known-type-p t1))))) |
---|
615 | ((eq t1 'integer) |
---|
616 | (cond ((memq t2 '(integer rational real number)) |
---|
617 | (values (sub-interval-p i1 i2) t)) |
---|
618 | ((or (eq t2 'bignum) |
---|
619 | (and (classp t2) (eq (class-name t2) 'bignum))) |
---|
620 | (values |
---|
621 | (or (sub-interval-p i1 (list '* (list most-negative-fixnum))) |
---|
622 | (sub-interval-p i1 (list (list most-positive-fixnum) '*))) |
---|
623 | t)) |
---|
624 | (t |
---|
625 | (values nil (known-type-p t2))))) |
---|
626 | ((eq t1 'rational) |
---|
627 | (if (memq t2 '(rational real number)) |
---|
628 | (values (sub-interval-p i1 i2) t) |
---|
629 | (values nil (known-type-p t2)))) |
---|
630 | ((eq t1 'float) |
---|
631 | (if (memq t2 '(float real number)) |
---|
632 | (values (sub-interval-p i1 i2) t) |
---|
633 | (values nil (known-type-p t2)))) |
---|
634 | ((memq t1 '(single-float short-float)) |
---|
635 | (if (memq t2 '(single-float short-float float real number)) |
---|
636 | (values (sub-interval-p i1 i2) t) |
---|
637 | (values nil (known-type-p t2)))) |
---|
638 | ((memq t1 '(double-float long-float)) |
---|
639 | (if (memq t2 '(double-float long-float float real number)) |
---|
640 | (values (sub-interval-p i1 i2) t) |
---|
641 | (values nil (known-type-p t2)))) |
---|
642 | ((eq t1 'real) |
---|
643 | (if (memq t2 '(real number)) |
---|
644 | (values (sub-interval-p i1 i2) t) |
---|
645 | (values nil (known-type-p t2)))) |
---|
646 | ((eq t1 'complex) |
---|
647 | (cond ((eq t2 'number) |
---|
648 | (values t t)) |
---|
649 | ((eq t2 'complex) |
---|
650 | (cond ((equal i2 '(*)) |
---|
651 | (values t t)) |
---|
652 | ((equal i1 '(*)) |
---|
653 | (values nil t)) |
---|
654 | (t |
---|
655 | (values (subtypep (car i1) (car i2)) t)))))) |
---|
656 | ((and (classp t1) |
---|
657 | (eq (class-name t1) 'array) |
---|
658 | (eq t2 'array)) |
---|
659 | (values (equal i2 '(* *)) t)) |
---|
660 | ((and (memq t1 '(array simple-array)) (eq t2 'array)) |
---|
661 | (let ((e1 (car i1)) |
---|
662 | (e2 (car i2)) |
---|
663 | (d1 (cadr i1)) |
---|
664 | (d2 (cadr i2))) |
---|
665 | (cond ((and (eq e2 '*) (eq d2 '*)) |
---|
666 | (values t t)) |
---|
667 | ((or (eq e2 '*) |
---|
668 | (equal e1 e2) |
---|
669 | (equal (upgraded-array-element-type e1) |
---|
670 | (upgraded-array-element-type e2))) |
---|
671 | (values (dimension-subtypep d1 d2) t)) |
---|
672 | (t |
---|
673 | (values nil t))))) |
---|
674 | ((and (memq t1 '(array simple-array)) (eq t2 'string)) |
---|
675 | (let ((element-type (car i1)) |
---|
676 | (dim (cadr i1)) |
---|
677 | (size (car i2))) |
---|
678 | (unless (%subtypep element-type 'character) |
---|
679 | (return-from %subtypep (values nil t))) |
---|
680 | (when (integerp size) |
---|
681 | (if (and (consp dim) (= (length dim) 1) (eql (%car dim) size)) |
---|
682 | (return-from %subtypep (values t t)) |
---|
683 | (return-from %subtypep (values nil t)))) |
---|
684 | (when (or (null size) (eql size '*)) |
---|
685 | (if (or (eql dim 1) |
---|
686 | (and (consp dim) (= (length dim) 1))) |
---|
687 | (return-from %subtypep (values t t)) |
---|
688 | (return-from %subtypep (values nil t)))))) |
---|
689 | ((and (eq t1 'simple-array) (eq t2 'simple-string)) |
---|
690 | (let ((element-type (car i1)) |
---|
691 | (dim (cadr i1)) |
---|
692 | (size (car i2))) |
---|
693 | (unless (%subtypep element-type 'character) |
---|
694 | (return-from %subtypep (values nil t))) |
---|
695 | (when (integerp size) |
---|
696 | (if (and (consp dim) (= (length dim) 1) (eql (%car dim) size)) |
---|
697 | (return-from %subtypep (values t t)) |
---|
698 | (return-from %subtypep (values nil t)))) |
---|
699 | (when (or (null size) (eql size '*)) |
---|
700 | (if (or (eql dim 1) |
---|
701 | (and (consp dim) (= (length dim) 1))) |
---|
702 | (return-from %subtypep (values t t)) |
---|
703 | (return-from %subtypep (values nil t)))))) |
---|
704 | ((and (memq t1 '(string simple-string)) (eq t2 'array)) |
---|
705 | (let ((element-type (car i2)) |
---|
706 | (dim (cadr i2)) |
---|
707 | (size (car i1))) |
---|
708 | (unless (eq element-type '*) |
---|
709 | (return-from %subtypep (values nil t))) |
---|
710 | (when (integerp size) |
---|
711 | (if (or (eq dim '*) |
---|
712 | (and (consp dim) (= (length dim) 1) (eql (%car dim) size))) |
---|
713 | (return-from %subtypep (values t t)) |
---|
714 | (return-from %subtypep (values nil t)))) |
---|
715 | (when (or (null size) (eql size '*)) |
---|
716 | (if (or (eq dim '*) |
---|
717 | (eql dim 1) |
---|
718 | (and (consp dim) (= (length dim) 1))) |
---|
719 | (return-from %subtypep (values t t)) |
---|
720 | (return-from %subtypep (values nil t)))))) |
---|
721 | ((eq t2 'simple-array) |
---|
722 | (case t1 |
---|
723 | (simple-array |
---|
724 | (let ((e1 (car i1)) |
---|
725 | (e2 (car i2)) |
---|
726 | (d1 (cadr i1)) |
---|
727 | (d2 (cadr i2))) |
---|
728 | (cond ((and (eq e2 '*) (eq d2 '*)) |
---|
729 | (values t t)) |
---|
730 | ((or (eq e2 '*) |
---|
731 | (equal e1 e2) |
---|
732 | (equal (upgraded-array-element-type e1) |
---|
733 | (upgraded-array-element-type e2))) |
---|
734 | (values (dimension-subtypep d1 d2) t)) |
---|
735 | (t |
---|
736 | (values nil t))))) |
---|
737 | ((simple-string simple-bit-vector) |
---|
738 | (let ((element-type (car i2)) |
---|
739 | (dim (cadr i2)) |
---|
740 | (size (car i1))) |
---|
741 | (unless (eq element-type '*) |
---|
742 | (return-from %subtypep (values nil t))) |
---|
743 | (when (integerp size) |
---|
744 | (if (or (eq dim '*) |
---|
745 | (and (consp dim) (= (length dim) 1) (eql (%car dim) size))) |
---|
746 | (return-from %subtypep (values t t)) |
---|
747 | (return-from %subtypep (values nil t)))) |
---|
748 | (when (or (null size) (eql size '*)) |
---|
749 | (if (or (eq dim '*) |
---|
750 | (eql dim 1) |
---|
751 | (and (consp dim) (= (length dim) 1))) |
---|
752 | (return-from %subtypep (values t t)) |
---|
753 | (return-from %subtypep (values nil t)))))) |
---|
754 | (t |
---|
755 | (values nil t)))) |
---|
756 | ((eq t2 'bit-vector) |
---|
757 | (let ((size1 (car i1)) |
---|
758 | (size2 (car i2))) |
---|
759 | (case t1 |
---|
760 | ((bit-vector simple-bit-vector) |
---|
761 | (values (if (or (eq size2 '*) (eql size1 size2)) |
---|
762 | t |
---|
763 | nil) t)) |
---|
764 | (t |
---|
765 | (values nil t))))) |
---|
766 | ((classp t2) |
---|
767 | (let ((class-name (class-name t2))) |
---|
768 | (cond ((eq class-name t1) |
---|
769 | (values t t)) |
---|
770 | ((and (eq class-name 'array) |
---|
771 | (memq t1 '(array simple-array vector simple-vector string |
---|
772 | simple-string simple-base-string bit-vector |
---|
773 | simple-bit-vector))) |
---|
774 | (values t t)) |
---|
775 | ((eq class-name 'vector) |
---|
776 | (cond ((memq t1 '(string simple-string)) |
---|
777 | (values t t)) |
---|
778 | ((memq t1 '(array simple-array)) |
---|
779 | (let ((dim (cadr i1))) |
---|
780 | (if (or (eql dim 1) |
---|
781 | (and (consp dim) (= (length dim) 1))) |
---|
782 | (values t t) |
---|
783 | (values nil t)))) |
---|
784 | (t |
---|
785 | (values nil t)))) |
---|
786 | ((and (eq class-name 'simple-vector) |
---|
787 | (eq t1 'simple-array)) |
---|
788 | (let ((dim (cadr i1))) |
---|
789 | (if (or (eql dim 1) |
---|
790 | (and (consp dim) (= (length dim) 1))) |
---|
791 | (values t t) |
---|
792 | (values nil t)))) |
---|
793 | ((and (eq class-name 'bit-vector) |
---|
794 | (eq t1 'simple-bit-vector)) |
---|
795 | (values t t)) |
---|
796 | ((and (eq class-name 'string) |
---|
797 | (memq t1 '(string simple-string))) |
---|
798 | (values t t)) |
---|
799 | (t |
---|
800 | (values nil nil))))) |
---|
801 | (t |
---|
802 | (values nil nil))))) |
---|
803 | |
---|
804 | (defun subtypep (type1 type2 &optional environment) |
---|
805 | (%subtypep type1 type2 environment)) |
---|