Debian Codegraph @

src/libtype.scm

raw
1 ;;;
2 ;;; libtype.scm - type-related stuff
3 ;;;
4 ;;; Copyright (c) 2021-2024 Shiro Kawai <[email protected]>
5 ;;;
6 ;;; Redistribution and use in source and binary forms, with or without
7 ;;; modification, are permitted provided that the following conditions
8 ;;; are met:
9 ;;;
10 ;;; 1. Redistributions of source code must retain the above copyright
11 ;;; notice, this list of conditions and the following disclaimer.
12 ;;;
13 ;;; 2. Redistributions in binary form must reproduce the above copyright
14 ;;; notice, this list of conditions and the following disclaimer in the
15 ;;; documentation and/or other materials provided with the distribution.
16 ;;;
17 ;;; 3. Neither the name of the authors nor the names of its contributors
18 ;;; may be used to endorse or promote products derived from this
19 ;;; software without specific prior written permission.
20 ;;;
21 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ;;;
33
34 ;; This must be the first form to prevent generation of *.sci file
35 (declare)
36
37 ;; In Gauche, types are a data structure that appears in both compile-time
38 ;; and run-time, describes metalevel properties of run-time data.
39 ;;
40 ;; Gauche has two kinds of types--prescriptive types and descriptive types.
41 ;; Prescriptive types are the types that are actually used to generate the
42 ;; actual data---we also call it classes. Descriptive types are, otoh,
43 ;; used only to descrive the nature of data at the certain point of program
44 ;; execution---for example, you may say the argument must be either <integer>
45 ;; or <boolean>. The descriptive type can't be used to generate an instance,
46 ;; only to be used to validate and/or infer the actual (generative) type of
47 ;; data.
48 ;;
49 ;; Descriptive types can be constructed by type constructors. Since the
50 ;; compiler needs to know about types, type constructor expressions
51 ;; are evaluated at the compile time, much like macros.
52 ;;
53 ;; We could've implemented types with macros, but it would be tricky. Unlike
54 ;; macros, type expression needs to evaluate from inside to outside, just
55 ;; like ordinary expressions. It's more like compile-time constant folding.
56 ;;
57 ;; Since type handing is deeply intertwined with compiler, we let the compiler
58 ;; recognize type expression specifically, rather than reusing existing
59 ;; evaluation mechanism. When the compile sees (C x ...) and C has an
60 ;; inlineable binding to an instance of <type-constructor-meta>, it recognizes
61 ;; type expression.
62 ;;
63 ;; We have several kinds of descriptive types.
64 ;;
65 ;; Constraint types
66 ;; - We don't have a separate class for this, but this is a kind of
67 ;; descriptive type that constraints the type the concerned
68 ;; value can take, e.g. (</> <integer> <string>). Created by
69 ;; a type constructor. Currently, the main use is in `assert-type`.
70 ;;
71 ;; <native-type>
72 ;; - A subset of Scheme primitive types that can map onto the native
73 ;; types. E.g. <long> is a subset of <integer> but can map onto
74 ;; the underlying `long` integer value. Main use is for FFI.
75 ;;
76 ;; <proxy-type>
77 ;; - This is a wrapper of an prescriptive types, and as far as type
78 ;; checking is concerened, it behaves just like the wrapped type.
79 ;; We need this because classes can be redefined. When a class
80 ;; is redefined, a new class instance is created and the class name
81 ;; is rebound to it. We want that other aggregate descriptive types
82 ;; also start referring to the new class, so a descriptive type can't
83 ;; hold a direct reference to a prescriptive type; instead, we refer
84 ;; to it through a proxy type. A proxy type always refer to the
85 ;; the redefined class.
86 ;; Proxy types are automatically created and handled under the hood;
87 ;; users doesn't need to deal with them explicity.
88
89
90 ;; This module is not meant to be `use'd. It is just to hide
91 ;; auxiliary procedures from the rest of the system. The necessary
92 ;; bindings are injected into 'gauche' module at the initialization time.
93 (define-module gauche.typeutil)
94 (select-module gauche.typeutil)
95 (use util.match)
96
97
98 (inline-stub
99 (.include "gauche/priv/configP.h"
100 "gauche/priv/classP.h"
101 "gauche/priv/nativeP.h"
102 "gauche/priv/memoP.h"
103 "gauche/priv/typeP.h")
104
105 ;; Metaclass: <type-constructor-meta>
106 ;; Its instance is ScmTypeConstructor. Provides the following slots.
107 ;; (We don't use generic functions, for they are also called from C runtime).
108 ;;
109 ;; initializer :: <descriptive-type> args -> <descriptive-type>
110 ;; Called from a type constructor that fills the descriptive type.
111 ;; It is called from either a compiler or an initcode of precompiled code.
112 ;; Note that a raw class object should never passed in the args---the
113 ;; compiler wraps class objects with a proxy type. The initializer
114 ;; should raise an error if a class object is given.
115 ;; This procedure must be pure. We may memoize the constructor result.
116 ;; deconstructor :: <descriptive-type> -> (arg ...)
117 ;; Returns a list of arguments such that when they are passed to the
118 ;; constructor, an equivalent descriptive type is constructed again.
119 ;; This is called from the precompiler to serialize the descriptive type.
120 ;; validator :: <descriptive-type> obj -> <boolean>
121 ;; Returns true iff obj is of type <descriptive-type>. Called from
122 ;; `of-type?`.
123 ;; subtype? :: <descriptive-type> type -> <boolean>|'super
124 ;; Returns one of three values: #t if the descriptive type is a subtype
125 ;; of TYPE, which may be a class or another descriptive type. #f if
126 ;; the descriptive type is definitely not a subtype. A symbol 'super
127 ;; if you need to ask TYPE.
128 ;; Note that proxy types and native types are already excluded, as well
129 ;; as the reflective case (subtype? x x) and the base cases
130 ;; (subtype? x <top>).
131 ;; supertype? :: <descriptive-type> type -> <boolean>
132 ;; Returns true iff the descriptive type is a supertype of TYPE.
133 ;; Trivial cases are already excluded, esp., TYPE won't be the
134 ;; same kind of <descriptive-type>.
135
136 (define-cclass <type-constructor-meta> :base :private :no-meta
137 "ScmTypeConstructor*" "Scm_TypeConstructorMetaClass"
138 (c "SCM_CLASS_METACLASS_CPL")
139 ((initializer)
140 (deconstructor)
141 (validator)
142 (subtype? :c-name "subtypeP")
143 (supertype? :c-name "supertypeP"))
144 )
145
146 (define-cfn Scm_TypeConstructorP (klass) ::int
147 (return (SCM_ISA klass (& Scm_TypeConstructorMetaClass))))
148
149 ;; The 'name' slot is computed by the initializer.
150 ;; The 'constructorArgs' slot is #f by default. If the instance is
151 ;; reconstructed from the precompiled form, however, we delay the actual
152 ;; initialization until the type is used.
153 (define-ctype ScmDescriptiveType
154 ::(.struct ScmDescriptiveTypeRec
155 (SCM_INSTANCE_HEADER::||
156 name::ScmObj
157 constructorArgs::ScmObj)))
158
159 (define-cclass <descriptive-type> :base :private :no-meta
160 "ScmDescriptiveType*" "Scm_DescriptiveTypeClass"
161 (c "SCM_CLASS_METACLASS_CPL+1")
162 ((name))
163 (metaclass <type-constructor-meta>)
164 (allocator (let* ([z::ScmDescriptiveType*
165 (SCM_NEW_INSTANCE ScmDescriptiveType klass)])
166 (cast void initargs) ;suppress unused warning
167 (set! (-> z name) SCM_FALSE)
168 (set! (-> z constructorArgs) SCM_FALSE)
169 (return (SCM_OBJ z)))))
170
171 ;; We memoize constructed types. The type is keyed by the constructor class
172 ;; and a list of contructor arguments.
173 (define-cvar type-table::ScmMemoTable* :static)
174 (initcode
175 (set! type-table (SCM_MEMO_TABLE (Scm_MakeMemoTable 256 -1 0))))
176
177 (define-cfn lookup-constructed-type (type-ctor::ScmTypeConstructor*
178 args)
179 :static
180 (let* ([keys::(.array ScmObj (2))] [r])
181 (set! (aref keys 0) (SCM_OBJ type-ctor))
182 (set! (aref keys 1) args)
183 (set! r (Scm_MemoTableGetv type-table keys 2))
184 (if (SCM_UNBOUNDP r)
185 (return SCM_FALSE)
186 (return r))))
187
188 (define-cfn register-constructed-type (type-ctor::ScmTypeConstructor*
189 args
190 type)
191 :static
192 (let* ([keys::(.array ScmObj (2))])
193 (set! (aref keys 0) (SCM_OBJ type-ctor))
194 (set! (aref keys 1) args)
195 (Scm_MemoTablePutv type-table keys 2 type)
196 (return type)))
197
198 (define-cproc %dump-type-table () ::<void> ; for debug
199 (Scm__MemoTableDump type-table SCM_CURERR))
200
201 (define-ctype ScmNativeType
202 ::(.struct ScmNativeTypeRec
203 (SCM_INSTANCE_HEADER::||
204 name::ScmObj
205 c-of-type::(.function (obj) ::int *)
206 super::ScmObj
207 c-type-name::(const char *)
208 size::size_t
209 alignment::size_t)))
210
211 (define-cclass <native-type> :base :private :no-meta
212 "ScmNativeType*" "Scm_NativeTypeClass"
213 (c "SCM_CLASS_METACLASS_CPL+1")
214 ((name)
215 (super)
216 (c-type-name :type <const-cstring>)
217 (size :type <size_t>)
218 (alignment :type <size_t>))
219 (printer (Scm_Printf port "#<native-type %S>" (-> (SCM_NATIVE_TYPE obj) name))))
220 )
221
222 (define-method initialize ((c <type-constructor-meta>) initargs)
223 (next-method)
224 (unless (slot-bound? c 'subtype?)
225 (slot-set! c 'subtype? (^[type super] #f)))
226 (unless (slot-bound? c 'supertype?)
227 (slot-set! c 'supertype? (^[type sub] #f))))
228
229 ;;;
230 ;;; type? obj
231 ;;;
232
233 ;; Returns obj if it's either a class metaobject, a descriptive type,
234 ;; a native type, or a proxy type. It's the same as (is-a? obj <type>)
235 ;; but this is more concise and clear.
236 (define-cproc type? (obj) ::<boolean> :constant
237 (return (SCM_ISA obj SCM_CLASS_TYPE)))
238
239 ;;;
240 ;;; of-type? obj type
241 ;;;
242
243 (inline-stub
244 ;; This may push C continuations on VM, so must be called on VM.
245 (define-cfn Scm_VMOfType (obj type)
246 (cond [(SCM_PROXY_TYPE_P type)
247 (return (Scm_VMIsA obj (Scm_ProxyTypeRef (SCM_PROXY_TYPE type))))]
248 [(SCM_DESCRIPTIVE_TYPE_P type)
249 (let* ([k::ScmClass* (SCM_CLASS_OF type)])
250 (SCM_ASSERT (SCM_TYPE_CONSTRUCTOR_META_P k))
251 (return (Scm_VMApply2 (-> (SCM_TYPE_CONSTRUCTOR_META k) validator)
252 type obj)))]
253 [(SCM_NATIVE_TYPE_P type)
254 (return (SCM_MAKE_BOOL
255 (funcall (-> (SCM_NATIVE_TYPE type) c-of-type) obj)))]
256 [(SCM_CLASSP type)
257 (return (Scm_VMIsA obj (SCM_CLASS type)))]
258 [else
259 (Scm_Error "Second argument of of-type? must be a type, but got: %S"
260 type)]))
261
262 (define-cproc of-type? (obj type) Scm_VMOfType)
263 )
264
265 ;;;
266 ;;; subtype? type-or-class type-or-class
267 ;;;
268
269 (define-cfn delegate-to-super (sub super) :static
270 (if (SCM_DESCRIPTIVE_TYPE_P super)
271 (let* ([k::ScmClass* (Scm_ClassOf super)])
272 (SCM_ASSERT (SCM_TYPE_CONSTRUCTOR_META_P k))
273 (return (Scm_VMApply2 (-> (SCM_TYPE_CONSTRUCTOR_META k) supertypeP)
274 super sub)))
275 (return SCM_FALSE)))
276
277 (define-cproc subtype? (sub super)
278 (loop
279 (cond
280 ;; Strip proxy types first
281 [(SCM_PROXY_TYPE_P sub)
282 (set! sub (SCM_OBJ (Scm_ProxyTypeRef (SCM_PROXY_TYPE sub))))]
283 [(SCM_PROXY_TYPE_P super)
284 (set! super (SCM_OBJ (Scm_ProxyTypeRef (SCM_PROXY_TYPE super))))]
285 ;; Both are classes, we can use subclass?
286 [(and (SCM_CLASSP sub) (SCM_CLASSP super))
287 (return (SCM_MAKE_BOOL (Scm_SubclassP (SCM_CLASS sub) (SCM_CLASS super))))]
288 ;; Filter out the trivial cases
289 [(SCM_EQ super (SCM_OBJ SCM_CLASS_TOP)) (return SCM_TRUE)]
290 [(SCM_EQ sub (SCM_OBJ SCM_CLASS_BOTTOM)) (return SCM_TRUE)]
291 [(SCM_EQ super sub) (return SCM_TRUE)]
292 ;; Native types can be a subtype of a class. No type (except BOTTOM) can
293 ;; be a subtype of a native type.
294 [(SCM_NATIVE_TYPE_P sub)
295 (let* ([klass (-> (SCM_NATIVE_TYPE sub) super)])
296 (SCM_ASSERT (SCM_CLASSP klass))
297 (set! sub klass))]
298 [(SCM_NATIVE_TYPE_P super) (return FALSE)]
299 ;; Delegate descriptive types to its handlers.
300 [(SCM_DESCRIPTIVE_TYPE_P sub)
301 (let* ([k::ScmClass* (Scm_ClassOf sub)])
302 (SCM_ASSERT (SCM_TYPE_CONSTRUCTOR_META_P k))
303 (let1/cps r (Scm_VMApply2 (-> (SCM_TYPE_CONSTRUCTOR_META k) subtypeP)
304 sub super)
305 [sub super]
306 (cond [(or (SCM_FALSEP r) (SCM_EQ r SCM_TRUE)) (return r)]
307 [(SCM_EQ r 'super) (return (delegate-to-super sub super))]
308 [else
309 (Scm_Error "subtype? handler of %S returned invalid value: %S"
310 r)])))]
311 [else (return (delegate-to-super sub super))])))
312
313 ;;;
314 ;;; Descriptive type infrastructure
315 ;;;
316
317 (define-method allocate-instance ((t <descriptive-type>) initargs)
318 (error "Abstract type instance cannot instantiate a concrete object:" t))
319
320 (define-method write-object ((t <descriptive-type>) port)
321 (format port "#~a" (~ t'name)))
322
323 ;; Equality is used when consolidate literals. It's not lightweight
324 ;; (it calls deconstructor, which allocates).
325 (define-method object-equal? ((x <descriptive-type>) (y <descriptive-type>))
326 (and (equal? (class-of x) (class-of y))
327 (equal? (deconstruct-type x) (deconstruct-type y))))
328
329 ;; This can also be called from initialization of precompiled code to recover
330 ;; descripitve type instance.
331 (inline-stub
332 (define-cfn Scm_ConstructType (ctor args)
333 (SCM_ASSERT (!= ctor NULL))
334 (unless (Scm_TypeConstructorP ctor)
335 (SCM_TYPE_ERROR ctor "<type-constructor-meta>"))
336 (let* ([ct::ScmTypeConstructor* (cast ScmTypeConstructor* ctor)]
337 [type (lookup-constructed-type ct args)])
338 (unless (SCM_FALSEP type) (return type))
339 (set! type (Scm_NewInstance (SCM_CLASS ct) (sizeof ScmDescriptiveType)))
340 (Scm_ApplyRec2 (-> ct initializer) type args)
341 (return (register-constructed-type ct args type))))
342 )
343 ;; Public interface to construct a descriptive type.
344 (define-cproc construct-type (meta args) Scm_ConstructType)
345
346 ;; Internal API, required to precompile descriptive type constant
347 (define-method deconstruct-type ((t <descriptive-type>))
348 ((~ (class-of t)'deconstructor) t))
349
350
351 ;;;
352 ;;; Proxy type API.
353 ;;;
354
355 ;; These are available in gauche.internal
356
357 (define-cproc wrap-with-proxy-type (id gloc)
358 (unless (SCM_IDENTIFIERP id)
359 (SCM_TYPE_ERROR id "identifier"))
360 (unless (SCM_GLOCP gloc)
361 (SCM_TYPE_ERROR gloc "gloc"))
362 (return (Scm_MakeProxyType (SCM_IDENTIFIER id) (SCM_GLOC gloc))))
363
364 (define-cproc proxy-type-ref (type)
365 (unless (SCM_PROXY_TYPE_P type)
366 (SCM_TYPE_ERROR type "proxy-type"))
367 (return (SCM_OBJ (Scm_ProxyTypeRef (SCM_PROXY_TYPE type)))))
368
369 (define-cproc proxy-type-id (type)
370 (unless (SCM_PROXY_TYPE_P type)
371 (SCM_TYPE_ERROR type "proxy-type"))
372 (return (Scm_ProxyTypeId (SCM_PROXY_TYPE type))))
373
374 ;; Internal. Recover type from the serialized type name for precompiled subr.
375 ;; KLUDGE: 'module' here is the module where the subr is defined, but the type
376 ;; itself isn't necessarily visible from that module. A typical case is the
377 ;; subr defined in 'scheme' module---the types are obviously not visible from
378 ;; vanilla scheme. For now, we try the given module, then try #<module gauche>.
379 (define-cproc %lookup-type (mod::<module> type-name::<symbol>)
380 (let* ([g::ScmGloc* (Scm_FindBinding mod type-name 0)])
381 (when (== g NULL)
382 (set! g (Scm_FindBinding (Scm_GaucheModule) type-name 0)))
383 (when (== g NULL)
384 (return SCM_FALSE))
385 (let* ([val (Scm_GlocGetValue g)])
386 (cond [(SCM_CLASSP val)
387 (let* ([id (Scm_MakeIdentifier (SCM_OBJ type-name) mod SCM_NIL)])
388 (return (Scm_MakeProxyType (SCM_IDENTIFIER id) g)))]
389 [(SCM_ISA val SCM_CLASS_TYPE) (return val)]
390 [else (return SCM_FALSE)]))))
391
392 (define (%type-name->type module type-name)
393 (define (maybe-type y)
394 (let1 s (symbol->string y)
395 (and (eqv? (string-ref s (- (string-length s) 1)) #\?)
396 (string->symbol (substring s 0 (- (string-length s) 1))))))
397 (if-let1 m (maybe-type type-name)
398 (and-let1 mt (%lookup-type module m)
399 (construct-type <?> (list mt)))
400 (%lookup-type module type-name)))
401
402 ;;;
403 ;;; Utilities
404 ;;;
405
406 (define (join-class-names classes)
407 (string-join (map (^k (x->string
408 (cond [(is-a? k <class>) (class-name k)]
409 [(is-a? k <descriptive-type>) (~ k'name)]
410 [(is-a? k <native-type>) (~ k'name)]
411 [(is-a? k <proxy-type>)
412 (~ (proxy-type-id k) 'name)]
413 [else k])))
414 classes)
415 " " 'prefix))
416
417 (define (make-compound-type-name op-name classes)
418 ($ string->symbol
419 $ string-append "<" (x->string op-name) (join-class-names classes) ">"))
420
421 (define (make-min-max-len-type-name op-name classes min max)
422 ($ string->symbol
423 $ string-append "<" (x->string op-name) (join-class-names classes)
424 (if min
425 (if max
426 (if (= min max)
427 (format " ~d" min)
428 (format " ~d..~d" min max))
429 (format " ~d.." min))
430 (if max
431 (format " ..~d" max)
432 ""))
433 ">"))
434
435 ;;;
436 ;;; Class: <^> (maybe we want to name it <λ>)
437 ;;; Creates a procedure type.
438 ;;; The signature can be specified as
439 ;;;
440 ;;; <argtype1> <argtype2> ... -> <rettype1> <rettype2> ...
441 ;;;
442 ;;; Argument types and/or return types can be also a single symbol *,
443 ;;; indicating arbitrary number of args/values. That is, any procedure
444 ;;; can be of type * -> *.
445 ;;;
446 ;;; TODO: How to type optional and keyword arguments?
447 ;;;
448
449
450 (define (init-^ type init-args)
451 (define (scan-args xs as)
452 ;; NB: We want to allow a right arrow (U+2192) in place of ->.
453 ;; The code would be messy though, if we want to support 'none' encoding as
454 ;; well. Think about it after we drop 'none' support.
455 (match xs
456 [() (error "Missing '->' in the procedure type constructor arguments:"
457 init-args)]
458 [('-> . xs) (scan-results xs (reverse as) '())]
459 [('* '-> . xs) (scan-results xs (reverse as '(*)) '())]
460 [_
461 (if (is-a? (car xs) <type>)
462 (scan-args (cdr xs) (cons (car xs) as))
463 (error "Non-type argument in the procedure type constructor:"
464 (car xs)))]))
465 (define (scan-results xs args rs)
466 (match xs
467 [() (values args (reverse rs))]
468 [('*) (values args (reverse rs '(*)))]
469 [(x . xs)
470 (if (is-a? x <type>)
471 (scan-results xs args (cons x rs))
472 (error "Non-class argument in the procedure type constructor:" x))]
473 [_ (error "Invalid arguments:" xs)]))
474
475 (receive (args results) (scan-args init-args '())
476 (slot-set! type 'name (make-compound-type-name '^ init-args))
477 (slot-set! type 'arguments (construct-type <Tuple> args))
478 (slot-set! type 'results (construct-type <Tuple> results))))
479
480 (define (deconstruct-^ type)
481 (append (~ type'arguments'elements)
482 (if (~ type'arguments'allow-rest?) '(*) '())
483 '(->)
484 (~ type'results'elements)
485 (if (~ type'results'allow-rest?) '(*) '())))
486
487 (define (validate-^ type obj)
488 (and-let1 otype (compute-procedure-type obj)
489 (subtype? type otype)))
490
491 (define (subtype-^ type super)
492 (if (is-a? super <^>)
493 (and (subtype? (~ type'arguments) (~ super'arguments))
494 (subtype? (~ super'results) (~ type'results)))
495 'super))
496
497 ;; Internal API - called from procedure-type (libproc)
498 ;; Reconstruct #<^ ...> type from a serialized type info encoded in a vector.
499 (define (reconstruct-procedure-type proc encoded-type)
500 (if (and (vector? encoded-type)
501 (>= (vector-length encoded-type) 3)
502 (= (vector-ref encoded-type 0) 1))
503 (let* ([module-name (vector-ref encoded-type 1)]
504 [module (find-module module-name)])
505 (if (not module)
506 (begin
507 (warn "unknown module during reconstructing procedure type: ~a\n"
508 module-name)
509 (compute-procedure-type proc)) ;; fallback
510 ($ construct-type <^>
511 $ map (^e (if (or (memq e '(* ->)))
512 e
513 (or (%type-name->type module e)
514 (error "unknown type in procedure type info:" e))))
515 (vector->list encoded-type 2))))
516 (compute-procedure-type proc)))
517
518 ;; Internal API - called from procedure-type (libproc)
519 ;; Compute #<^ ...> type from the information available in the procedure.
520 ;; Once this info is computed, it is cached in PROC.
521 (define (compute-procedure-type proc)
522 (define (%procedure-type proc)
523 (if-let1 clinfo (case-lambda-decompose proc)
524 (construct-type </> (map (^v (%procedure-type (caddr v))) clinfo))
525 (or (and-let* ([ (closure? proc) ]
526 [code (closure-code proc)])
527 ((with-module gauche.internal compiled-code-type) code))
528 ;; Fallback - if we don't have detailed type info, just use
529 ;; # of arguments.
530 (let1 top (%class->proxy <top>)
531 (construct-procedure-type (make-list (~ proc'required) top)
532 (~ proc'optional)
533 '*)))))
534 (define (%method-type meth)
535 (construct-procedure-type (map %class->proxy (~ meth'specializers))
536 (~ meth'optional)
537 '*))
538 (define (%generic-type gf)
539 (construct-type </> (map %method-type (~ gf'methods))))
540
541 (cond [(is-a? proc <procedure>) (%procedure-type proc)]
542 [(is-a? proc <generic>) (%generic-type proc)]
543 [(is-a? proc <method>) (%method-type proc)]
544 ;; Dealing with applicable objects are debatable. Any object can
545 ;; become applicable, which makes its type
546 ;; (</> <original-type> <type-when-applied>). That makes type
547 ;; operations extremely complicated.
548 [else #f]))
549
550 (define-cproc %class->proxy (klass::<class>)
551 (let* ([ms (-> klass modules)]
552 [n (-> klass name)])
553 (dolist [m ms]
554 (let* ([g::ScmGloc* (Scm_FindBinding (SCM_MODULE m) (SCM_SYMBOL n) 0)])
555 (when (!= g NULL)
556 (let* ([id (Scm_MakeIdentifier n (SCM_MODULE m) SCM_NIL)])
557 (return (Scm_MakeProxyType (SCM_IDENTIFIER id) g))))))
558 ;; If we're here, the class doesn't have a known global binding.
559 ;; It is possible---a class can be created procedurally at runtime---
560 ;; but to be used in a type expession, it must be recognized by the
561 ;; compiler, which requires the class is statically bound to a global
562 ;; identifier. We raise an error if that's not the case.
563 (Scm_Error "Class %S doesn't have a known global binding and can't be used \
564 in a type expression." klass)))
565
566 ;; Utility. Called from compiler, too.
567 (define (construct-procedure-type argtypes ; (<List> <type>)
568 has-optional? ; <boolean>
569 rettypes) ; (<List> <type>) or '*
570 (let1 rts (if (eq? rettypes '*) '(*) rettypes)
571 ($ construct-type <^>
572 (if has-optional?
573 `(,@argtypes * -> ,@rts)
574 `(,@argtypes -> ,@rts)))))
575
576 (define-class <^> (<descriptive-type>)
577 ((arguments :init-keyword :arguments) ; <Tuple>
578 (results :init-keyword :results)) ; <Tuple>
579 :metaclass <type-constructor-meta>
580 :initializer init-^
581 :deconstructor deconstruct-^
582 :validator validate-^
583 :subtype? subtype-^)
584
585 ;;;
586 ;;; Class: </>
587 ;;; Creates a union type.
588 ;;;
589
590 (define-class </> (<descriptive-type>)
591 ((members :init-keyword :members))
592 :metaclass <type-constructor-meta>
593 :initializer (^[type args]
594 (assume (every (cut is-a? <> <type>) args))
595 (slot-set! type 'name (make-compound-type-name '/ args))
596 (slot-set! type 'members args))
597 :deconstructor (^[type] (~ type'members))
598 :validator (^[type obj] (any (cut of-type? obj <>) (~ type'members)))
599 :subtype? (^[type super]
600 (if (is-a? super </>)
601 (every (cut subtype? <> super) (~ type'members))
602 'super))
603 :supertype? (^[type sub] (any (cut subtype? sub <>) (~ type'members))))
604
605 ;;;
606 ;;; Class: <?>
607 ;;; Creates a boolean-optional type, that is, <type> or #f.
608 ;;;
609
610 (define-class <?> (<descriptive-type>)
611 ((primary-type :init-keyword :primary-type))
612 :metaclass <type-constructor-meta>
613 :initializer (^[type args]
614 (let1 ptype (car args)
615 (assume (is-a? ptype <type>))
616 (slot-set! type 'name (make-compound-type-name '? `(,ptype)))
617 (slot-set! type 'primary-type ptype)))
618 :deconstructor (^[type] (list (~ type'primary-type)))
619 :validator (^[type obj]
620 (or (eqv? obj #f) (of-type? obj (~ type'primary-type))))
621 :subtype? (^[type super]
622 (if (is-a? super <?>)
623 (subtype? (~ type'primary-type) (~ super'primary-type))
624 'super))
625 :supertype? (^[type sub] (subtype? sub (~ type'primary-type))))
626
627 ;;;
628 ;;; Class: <Tuple>
629 ;;; Fixed-length list, each element having its own type constraints.
630 ;;;
631
632 ;; (<Tuple> type ... [*])
633
634 (define (init-Tuple type args)
635 (receive (types rest?) (if (and (pair? args) (eqv? (last args) '*))
636 (values (drop-right args 1) #t)
637 (values args #f))
638 (dolist [t types]
639 (unless (is-a? t <type>)
640 (error "Non-type parameter in <Tuple> constructor:" t)))
641 (slot-set! type 'name (make-compound-type-name 'Tuple args))
642 (slot-set! type 'elements types)
643 (slot-set! type 'allow-rest? rest?)))
644
645 (define (deconstruct-Tuple type)
646 (if (~ type'allow-rest?)
647 (append (~ type'elements) '(*))
648 (~ type'elements)))
649
650 (define (validate-Tuple type obj)
651 (let loop ([obj obj] [elts (~ type'elements)])
652 (cond [(null? obj) (null? elts)]
653 [(not (pair? obj)) #f]
654 [(null? elts) (~ type'allow-rest?)]
655 [else (and (of-type? (car obj) (car elts))
656 (loop (cdr obj) (cdr elts)))])))
657
658 (define (subtype-Tuple type super)
659 (or (eqv? super <list>)
660 (and (is-a? super <Tuple>)
661 (if (~ type'allow-rest?)
662 (<= (length (~ type'elements)) (length (~ super'elements)))
663 (= (length (~ type'elements)) (length (~ super'elements))))
664 (every (cut subtype? <> <>) (~ type'elements) (~ super'elements)))
665 (and (is-a? super <List>)
666 (every (cute subtype? <> (~ super'element-type)) (~ type'elements))
667 (<= (or (~ super'min-length) 0)
668 (length (~ type'elements))
669 (or (~ super'max-length) +inf.0)))
670 'super))
671
672 (define-class <Tuple> (<descriptive-type>)
673 ((elements :init-keyword :elements)
674 (allow-rest? :init-keyword :allow-rest?))
675 :metaclass <type-constructor-meta>
676 :initializer init-Tuple
677 :deconstructor deconstruct-Tuple
678 :validator validate-Tuple
679 :subtype? subtype-Tuple)
680
681 ;;;
682 ;;; Class: <List>
683 ;;; Class: <Vector>
684 ;;; A list or vector of specified types.
685 ;;;
686
687 (define (make-init-Seq name)
688 (^[type args]
689 (apply (^[etype :optional (min #f) (max #f)]
690 (unless (or (not min) (real? min))
691 (error "min argument must be a real number or #f, but got:" min))
692 (unless (or (not max) (real? max))
693 (error "max argument must be a real number or #f, but got:" max))
694 (slot-set! type 'name
695 (make-min-max-len-type-name name (list etype) min max))
696 (slot-set! type 'element-type etype)
697 (slot-set! type 'min-length min)
698 (slot-set! type 'max-length max))
699 args)))
700
701 (define (deconstruct-Seq type)
702 (list (~ type'element-type) (~ type'min-length) (~ type'max-length)))
703
704 (define (validate-List type obj)
705 (let ([et (~ type'element-type)]
706 [mi (~ type'min-length)]
707 [ma (~ type'max-length)])
708 (if (not (or mi ma))
709 ;; simple case
710 (let loop ([obj obj])
711 (cond [(null? obj) #t]
712 [(not (pair? obj)) #f]
713 [(of-type? (car obj) et) (loop (cdr obj))]
714 [else #f]))
715 ;; general case
716 (let loop ([obj obj] [n 0])
717 (cond [(null? obj) (or (not mi) (<= mi n))]
718 [(and ma (<= ma n)) #f]
719 [(not (pair? obj)) #f]
720 [(of-type? (car obj) et) (loop (cdr obj) (+ n 1))]
721 [else #f])))))
722
723 (define (validate-Vector type obj)
724 (and (vector? obj)
725 (let ([et (~ type'element-type)]
726 [mi (~ type'min-length)]
727 [ma (~ type'max-length)]
728 [len (vector-length obj)])
729 (and (or (not mi) (<= mi len))
730 (or (not ma) (<= len ma))
731 (let loop ([i 0])
732 (cond [(= i len) #t]
733 [(of-type? (vector-ref obj i) et) (loop (+ i 1))]
734 [else #f]))))))
735
736 (define (make-subtype-Seq base-type)
737 (^[type super]
738 (or (eqv? super base-type)
739 (and (is-a? super (class-of type))
740 (subtype? (~ type'element-type) (~ super'element-type))
741 (>= (or (~ type'min-length) 0)
742 (or (~ super'min-length) 0))
743 (<= (or (~ type'max-length) +inf.0)
744 (or (~ super'max-length) +inf.0)))
745 'super)))
746
747 (define-class <List> (<descriptive-type>)
748 ((element-type :init-keyword :element-type)
749 (min-length :init-keyword :min-length :init-value #f)
750 (max-length :init-keyword :max-length :init-value #f))
751 :metaclass <type-constructor-meta>
752 :initializer (make-init-Seq 'List)
753 :deconstructor deconstruct-Seq
754 :validator validate-List
755 :subtype? (make-subtype-Seq <list>))
756
757 (define-class <Vector> (<descriptive-type>)
758 ((element-type :init-keyword :element-type)
759 (min-length :init-keyword :min-length :init-value #f)
760 (max-length :init-keyword :max-length :init-value #f))
761 :metaclass <type-constructor-meta>
762 :initializer (make-init-Seq 'Vector)
763 :deconstructor deconstruct-Seq
764 :validator validate-Vector
765 :subtype? (make-subtype-Seq <vector>))
766
767 ;;;
768 ;;; Class: <Assortment>
769 ;;; A type consists of a set of concrete objects.
770 ;;; If it has only one member, you can think of it as a singleton type.
771 ;;; If it has multiple members, it's a union of singleton types.
772 ;;; The members (instances) are sorted by default-comparator so that
773 ;;; equivalence is easily tested.
774 ;;;
775
776 (define-class <Assortment> (<descriptive-type>)
777 ((instances :init-keyword :instance))
778 :metaclass <type-constructor-meta>
779 :initializer (^[type args]
780 (define objs (map unwrap-syntax args))
781 (slot-set! type 'name
782 (string->symbol
783 (string-append
784 "<Assortment " (x->string objs) ">")))
785 (slot-set! type 'instances (sort objs)))
786 :deconstructor (^[type] (list (~ type'instances)))
787 :validator (^[type obj] (boolean (memv obj (~ type'instances))))
788 :subtype? (^[type super] (every (^[obj] (of-type? obj super))
789 (~ type'instances)))
790 :supertype? (^[type sub] #f))
791
792 ;;;
793 ;;; Types for bridging Scheme and C
794 ;;;
795
796 ;; Each of these types has a corresponding cgen-type that maintains
797 ;; the knowledge how it is represented in C.
798
799 (inline-stub
800 (define-cfn make_native_type (name::(const char*)
801 super
802 c-type-name::(const char*)
803 size::size_t
804 alignment::size_t
805 c-of-type::(.function (obj)::int *))
806 :static
807 (let* ([z::ScmNativeType*
808 (SCM_NEW_INSTANCE ScmNativeType (& Scm_NativeTypeClass))])
809 (set! (-> z name) (SCM_INTERN name))
810 (set! (-> z super) super)
811 (set! (-> z c-type-name) c-type-name)
812 (set! (-> z c-of-type) c-of-type)
813 (set! (-> z size) size)
814 (set! (-> z alignment) alignment)
815 (return (SCM_OBJ z))))
816
817 (define-cise-stmt define-native-type
818 [(_ name super ctype fn)
819 `(let* ([z (make_native_type ,(symbol->string name)
820 (SCM_OBJ ,super) ,(x->string ctype)
821 (sizeof (.type ,ctype))
822 (SCM_ALIGNOF (.type ,ctype))
823 ,fn)])
824 (Scm_MakeBinding (Scm_GaucheModule)
825 (SCM_SYMBOL (-> (SCM_NATIVE_TYPE z) name)) z
826 SCM_BINDING_INLINABLE))])
827
828 (define-cfn native_fixnumP (obj) ::int :static
829 (return (SCM_INTP obj)))
830
831 ;; NB: Range check is also in ext/uvector/uvector.scm. May be integrated.
832 (define-cfn native_s8P (obj) ::int :static
833 (return (and (SCM_INTP obj)
834 (>= (SCM_INT_VALUE obj) -128)
835 (<= (SCM_INT_VALUE obj) 127))))
836 (define-cfn native_u8P (obj) ::int :static
837 (return (and (SCM_INTP obj)
838 (>= (SCM_INT_VALUE obj) 0)
839 (<= (SCM_INT_VALUE obj) 255))))
840 (define-cfn native_s16P (obj) ::int :static
841 (return (and (SCM_INTP obj)
842 (>= (SCM_INT_VALUE obj) -32768)
843 (<= (SCM_INT_VALUE obj) 32767))))
844 (define-cfn native_u16P (obj) ::int :static
845 (return (and (SCM_INTP obj)
846 (>= (SCM_INT_VALUE obj) 0)
847 (<= (SCM_INT_VALUE obj) 65535))))
848 (define-cfn native_s32P (obj) ::int :static
849 (.if (== SIZEOF_LONG 4)
850 (return (or (SCM_INTP obj)
851 (and (SCM_BIGNUMP obj)
852 (>= (Scm_NumCmp obj '#x-8000_0000) 0)
853 (<= (Scm_NumCmp obj '#x7fff_ffff) 0))))
854 (return (and (SCM_INTP obj)
855 (>= (SCM_INT_VALUE obj) #x-8000_0000)
856 (<= (SCM_INT_VALUE obj) #x7fff_ffff)))))
857 (define-cfn native_u32P (obj) ::int :static
858 (.if (== SIZEOF_LONG 4)
859 (return (or (and (SCM_INTP obj)
860 (>= (SCM_INT_VALUE obj) 0))
861 (and (SCM_BIGNUMP obj)
862 (>= (Scm_Sign obj) 0)
863 (<= (Scm_NumCmp obj '#xffff_ffff) 0))))
864 (return (and (SCM_INTP obj)
865 (>= (SCM_INT_VALUE obj) 0)
866 (<= (SCM_INT_VALUE obj) #xffff_ffff)))))
867 (define-cfn native_s64P (obj) ::int :static
868 (return (or (SCM_INTP obj)
869 (and (SCM_BIGNUMP obj)
870 (>= (Scm_NumCmp obj '#x-8000_0000_0000_0000) 0)
871 (<= (Scm_NumCmp obj '#x-7fff_ffff_ffff_ffff) 0)))))
872 (define-cfn native_u64P (obj) ::int :static
873 (return (or (and (SCM_INTP obj)
874 (>= (SCM_INT_VALUE obj) 0))
875 (and (SCM_BIGNUMP obj)
876 (>= (Scm_Sign obj) 0)
877 (<= (Scm_NumCmp obj '#xffff_ffff_ffff_ffff) 0)))))
878
879 (define-cfn native_shortP (obj) ::int :static
880 (return (and (SCM_INTP obj)
881 (>= (SCM_INT_VALUE obj) SHRT_MIN)
882 (<= (SCM_INT_VALUE obj) SHRT_MAX))))
883 (define-cfn native_ushortP (obj) ::int :static
884 (return (and (SCM_INTP obj)
885 (>= (SCM_INT_VALUE obj) 0)
886 (<= (SCM_INT_VALUE obj) USHRT_MAX))))
887 (define-cfn native_intP (obj) ::int :static
888 (.if (== SIZEOF_LONG 4)
889 (if (SCM_BIGNUMP obj)
890 (let* ([oor::int FALSE]
891 [v::long (Scm_GetIntegerClamp obj SCM_CLAMP_BOTH (& oor))])
892 (return (and (not oor)
893 (>= v INT_MIN)
894 (<= v INT_MAX))))
895 (return (SCM_INTP obj)))
896 (if (SCM_INTP obj)
897 (let* ([v::long (SCM_INT_VALUE obj)])
898 (return (and (>= v INT_MIN)
899 (<= v INT_MAX))))
900 (return FALSE))))
901 (define-cfn native_uintP (obj) ::int :static
902 (.if (== SIZEOF_LONG 4)
903 (if (SCM_BIGNUMP obj)
904 (let* ([oor::int FALSE])
905 (cast (void) (Scm_GetIntegerUClamp obj SCM_CLAMP_BOTH (& oor)))
906 (return (not oor)))
907 (return (and (SCM_INTP obj) (>= (SCM_INT_VALUE obj) 0))))
908 (return (and (SCM_INTP obj)
909 (>= (SCM_INT_VALUE obj) 0)
910 (<= (SCM_INT_VALUE obj) UINT_MAX)))))
911 (define-cfn native_longP (obj) ::int :static
912 (if (SCM_BIGNUMP obj)
913 (let* ([oor::int FALSE])
914 (cast void (Scm_GetIntegerClamp obj SCM_CLAMP_BOTH (& oor)))
915 (return (not oor)))
916 (return (SCM_INTP obj))))
917 (define-cfn native_ulongP (obj) ::int :static
918 (if (SCM_BIGNUMP obj)
919 (let* ([oor::int FALSE])
920 (cast void (Scm_GetIntegerUClamp obj SCM_CLAMP_BOTH (& oor)))
921 (return (not oor)))
922 (return (and (SCM_INTP obj) (>= (SCM_INT_VALUE obj) 0)))))
923
924 ;; we don't range-check flonums
925 (define-cfn native_realP (obj) ::int :static
926 (return (SCM_REALP obj)))
927
928 (define-cfn native_cstrP (obj) ::int :static
929 (return (SCM_STRINGP obj)))
930
931 ;; subrs returning <void> actually return #<undef>
932 (define-cfn native_voidP (obj) ::int :static
933 (return (SCM_UNDEFINEDP obj)))
934
935 (define-cfn native_iportP (obj) ::int :static
936 (return (SCM_IPORTP obj)))
937 (define-cfn native_oportP (obj) ::int :static
938 (return (SCM_OPORTP obj)))
939 (define-cfn native_closureP (obj) ::int :static
940 (return (SCM_CLOSUREP obj)))
941
942 (initcode
943 (define-native-type <fixnum> SCM_CLASS_INTEGER ScmSmallInt native_fixnumP)
944 (define-native-type <short> SCM_CLASS_INTEGER short native_shortP)
945 (define-native-type <ushort> SCM_CLASS_INTEGER u_short native_ushortP)
946 (define-native-type <int> SCM_CLASS_INTEGER int native_intP)
947 (define-native-type <uint> SCM_CLASS_INTEGER u_int native_uintP)
948 (define-native-type <long> SCM_CLASS_INTEGER long native_longP)
949 (define-native-type <ulong> SCM_CLASS_INTEGER u_long native_ulongP)
950 (define-native-type <int8> SCM_CLASS_INTEGER int8_t native_s8P)
951 (define-native-type <uint8> SCM_CLASS_INTEGER uint8_t native_u8P)
952 (define-native-type <int16> SCM_CLASS_INTEGER int16_t native_s16P)
953 (define-native-type <uint16> SCM_CLASS_INTEGER uint16_t native_u16P)
954 (define-native-type <int32> SCM_CLASS_INTEGER int32_t native_s32P)
955 (define-native-type <uint32> SCM_CLASS_INTEGER uint32_t native_u32P)
956 (define-native-type <int64> SCM_CLASS_INTEGER int64_t native_s64P)
957 (define-native-type <uint64> SCM_CLASS_INTEGER uint64_t native_u64P)
958 (define-native-type <size_t> SCM_CLASS_INTEGER size_t Scm_IntegerFitsSizeP)
959 (define-native-type <ssize_t> SCM_CLASS_INTEGER ssize_t Scm_IntegerFitsSsizeP)
960 (define-native-type <ptrdiff_t> SCM_CLASS_INTEGER ptrdiff_t Scm_IntegerFitsPtrdiffP)
961 (define-native-type <off_t> SCM_CLASS_INTEGER off_t Scm_IntegerFitsOffsetP)
962 (define-native-type <intptr_t> SCM_CLASS_INTEGER intptr_t Scm_IntegerFitsIntptrP)
963 (define-native-type <uintptr_t> SCM_CLASS_INTEGER uintptr_t Scm_IntegerFitsUintptrP)
964 (define-native-type <float> SCM_CLASS_REAL float native_realP)
965 (define-native-type <double> SCM_CLASS_REAL double native_realP)
966 (define-native-type <const-cstring> SCM_CLASS_STRING "const char*" native_cstrP)
967 (define-native-type <input-port> SCM_CLASS_PORT ScmPort* native_iportP)
968 (define-native-type <output-port> SCM_CLASS_PORT ScmPort* native_oportP)
969 (define-native-type <closure> SCM_CLASS_PROCEDURE ScmClosure* native_closureP)
970 (define-native-type <void> SCM_CLASS_TOP ScmObj native_voidP)
971 ))
972
973 ;;;
974 ;;; Make exported symbol visible from outside
975 ;;;
976
977 (let ((xfer (with-module gauche.internal %transfer-bindings)))
978 (xfer (current-module)
979 (find-module 'gauche)
980 '(<type-constructor-meta>
981 <descriptive-type>
982 <native-type>
983 <^> </> <?> <Tuple> <List> <Vector> <Assortment>
984 type? subtype? of-type?))
985 (xfer (current-module)
986 (find-module 'gauche.internal)
987 '(construct-type
988 deconstruct-type
989 wrap-with-proxy-type
990 proxy-type-ref
991 proxy-type-id
992 ;; followings are called from procedure-type (libproc)
993 reconstruct-procedure-type
994 compute-procedure-type
995 construct-procedure-type)))