Debian Codegraph @

lib/lang/c/type.scm

raw
1 ;;;
2 ;;; C type 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 ;; Common definitions related to C types.
35 ;; This is internal module; not to be directly use'd.
36
37 (define-module lang.c.type
38 (use gauche.dictionary)
39 (use util.match)
40 (use srfi.13)
41 (export grok-c-type
42 c-primary-type
43 c-basic-type-integral?
44 c-basic-type-flonum?
45 c-basic-type-scalar-numeric?
46 c-basic-type-numeric?
47 c-type-narrower?
48 c-wider-type
49 c-actual-type)
50 )
51 (select-module lang.c.type)
52
53 ;; Type representation
54 ;; We use plain S-expr rather than a bunch of records, for flexibility.
55 ;;
56 ;;
57 ;; <c-type> : (<basic-type> (<qual> ...))
58 ;; | (.pointer (<qual> ...) <c-type>)
59 ;; | (.array <c-type> <size> (<aqual> ...))
60 ;; | (.function (<fqual> ...>) <c-type> <args>)
61 ;; | (.struct <tag> (<qual> ...)
62 ;; ((<field-name> <c-type> [<size>]) ...))
63 ;; | (.union <tag> (<qual> ...)
64 ;; ((<field-name> <c-type> [<size>]) ...))
65 ;; | (.enum <tag> (<qual> ...)
66 ;; ((<enum-name> <enum-value>) ...))
67 ;; | (.type <type-name> (<qual> ...) <c-type>)
68 ;;
69 ;; <basic-type> : one of the symbols in *c-basic-types*
70 ;;
71 ;; <qual> : 'volatile | 'const | 'restrict
72 ;; | ('attribute ...) | ('asm ...)
73 ;; <fqual> : 'inline
74 ;;
75 ;; <aqual> : <qual> | 'static
76 ;; <size> : scheme-integer
77 ;; | c-constant-expression
78 ;; | #f
79 ;;
80 ;; <args> : (<arg> ...)
81 ;; | (<arg> ... <rest-arg>)
82 ;; | 'unknown-args
83 ;; <arg> : (<arg-name> <arg-type>)
84 ;; <arg-name> : symbol | #f
85 ;; <arg-type> : <c-type> | #f
86 ;; <rest-arg> : '...
87 ;;
88 ;; <tag> : <symbol> | #f
89 ;; <field-name> : <symbol> | #f
90 ;; <type-name> : symbol
91 ;;
92 ;; <enum-name> : symbol
93 ;; <enum-value> : scheme-integer
94 ;; | c-constant-expression
95 ;; | #f
96 ;;
97 ;; The (.type ...) form is used for typedef'ed types.
98
99
100 ;; API
101 ;; Input is a list of type specs obtained from the parser.
102 ;;
103 ;; <type-specs> : (<type-modifier> ... <core-type-spec>)
104 ;; <type-modifier> : (* <qual> ...)
105 ;; | (array-dimension (<aqual> ...) <dim-expr>)
106 ;; | (function <params>)
107 ;; | (attribute <attrs>)
108 ;; | (asm <asm>)
109 ;; <params> : (<param-spec> ...)
110 ;; | (<param-spec> ... '...)
111 ;; | 'no-args
112 ;; | 'unknown-args
113 ;; <core-type-spec> : mixed list of zero or more <qual>s, and <core-type>
114 ;; <core-type> : <basic-type>
115 ;; | (struct <tag> <member-spec> ...)
116 ;; | (union <tag> <member-spec> ...)
117 ;; | (enum <tag> <member-id> ...)
118 ;;
119 ;; NB: attribute and asm may appear in both type-modifier and in core quals
120 ;;
121 ;; Output is a well-formed <c-type>.
122 (define (grok-c-type type-specs typedef-dict)
123 (define (rec type-specs)
124 (match type-specs
125 [() '()]
126 [(('* . quals) . rest) `(.pointer ,quals ,(rec rest))]
127 [(('array-dimension quals size) . rest)
128 (match (fold-c-constant size)
129 [#f `(.array ,(rec rest) ,quals ,size)] ;variable size
130 [(val type)
131 (unless (c-basic-type-integral? type)
132 (error "non-integral array dimension not allowed:" type-specs))
133 `(.array ,(rec rest) ,quals ,val)])]
134 [(('function params) . rest)
135 ;; special handling of 'inline' - syntactically it is attached to
136 ;; the return type, but we need to attach it to the function part.
137 (let* ([inline? (memq 'inline (last rest))]
138 [return-type (rec (if inline?
139 (append
140 (drop-right rest 1)
141 (list (delete 'inline (last rest))))
142 rest))]
143 [param-spec (case params
144 [(no-args) '()]
145 [(unknown-args) 'unknown-args]
146 [else (map (^p (match p
147 [('ident n) `(,n #f)]
148 [(n t) p]
149 ['... p]))
150 params)])])
151 `(.function ,(if inline? '(inline) '()) ,return-type ,param-spec))]
152 [((and ('attribute . _) attr) . rest) (attach-qualifier (rec rest) attr)]
153 [((and ('asm . _) asm) . rest) (attach-qualifier (rec rest) asm)]
154 [((xs ...)) (grok-core-type xs typedef-dict)]
155 [_ (error "[internal] unrecognized type specs:" type-specs)]))
156 (rec type-specs))
157
158 (define-constant *c-basic-types*
159 '(char s-char u-char
160 short u-short
161 int u-int
162 long u-long
163 long-long u-long-long
164 float double long-double
165 float-complex double-complex long-double-complex
166 bool void
167 ;; the followings are non-standard
168 builtin-va-list
169 float128 float64x float-ibm128
170 long-long-double long-long-double-complex))
171
172 ;; (const unsigned volatile int) -> (u-int (const volatile))
173 (define (grok-core-type words typedef-dict)
174 (define (bad) (error "Invalid type:" words))
175 (define (integer-type sign size int)
176 (ecase int
177 [(#f int)
178 (if (eq? sign 'unsigned)
179 (ecase size
180 [(#f) 'u-int]
181 [(short) 'u-short]
182 [(long) 'u-long]
183 [(long-long) 'u-long-long])
184 (ecase size
185 [(#f) 'int]
186 [(short) 'short]
187 [(long) 'long]
188 [(long-long) 'long-long]))]
189 [(char)
190 (when size (bad))
191 (case sign
192 [(#f) 'char]
193 [(unsigned) 'u-char]
194 [(signed) 's-char])]
195 [(bool)
196 (when (or size sign) (bad))
197 'bool]))
198 (define (float-type size complex? flo)
199 (when (eq? size 'short) (bad))
200 (let1 base (if (memq size '(long long-long))
201 (if (eq? flo 'float)
202 (bad)
203 (symbol-append size '-double))
204 flo)
205 (if complex?
206 (symbol-append base '-complex)
207 base)))
208
209 (define (aggregate-tag tag)
210 (match tag
211 [('ident x) x]
212 [#f #f]))
213
214 (define (aggregate-type quals core)
215 (define (make-agg-type mark tag members)
216 `(,mark ,(aggregate-tag tag) ,(reverse quals) ,members))
217 (define (enum-member mem)
218 (match-let1 (name init) mem
219 (match (fold-c-constant init)
220 [#f mem]
221 [(val type) `(,name ,val)])))
222 (match core
223 [('struct tag . members) (make-agg-type '.struct tag members)]
224 [('union tag . members) (make-agg-type '.union tag members)]
225 [('enum tag . members) (make-agg-type '.enum tag
226 (map enum-member members))]))
227
228 ;; we make quals appear in the order of the original code, just to make
229 ;; testing and debugging easier---the caller shouldn't rely on that.
230 (define (finish-type quals sign size complex? core)
231 (case core
232 [(#f int char bool)
233 (if complex?
234 (bad)
235 `(,(integer-type sign size core) ,(reverse quals)))]
236 [(float double float128 float64x float-ibm128)
237 (if sign
238 (bad)
239 `(,(float-type size complex? core) ,(reverse quals)))]
240 [(void) (if (or sign size complex?)
241 (bad)
242 `(void ,(reverse quals)))]
243 [(builtin-va-list)
244 (if (or sign size complex?)
245 (bad)
246 `(buildin-va-list ,(reverse quals)))]
247 [else
248 (if (symbol? core)
249 ;; typedef name
250 (if-let1 def (and typedef-dict (dict-get typedef-dict core #f))
251 `(.type ,core ,(reverse quals) ,def)
252 (error "Unknown typedef name:" core))
253 ;; aggregate
254 (if (or sign size complex?)
255 (bad)
256 (aggregate-type quals core)))]))
257
258 (let loop ([words words]
259 [quals '()]
260 [sign #f] ; #f, signed, unsigned
261 [size #f] ; short, long, long-long
262 [complex? #f]
263 [core #f]) ; int, char, bool, float, double,
264 ; typedef-name, or struct etc.
265 (match words
266 [() (finish-type quals sign size complex? core)]
267 [('_Bool . r) (if core
268 (bad)
269 (loop r quals sign size complex? 'bool))]
270 [('char . r) (if core
271 (bad)
272 (loop r quals sign size complex? 'char))]
273 [('int . r) (if core
274 (bad)
275 (loop r quals sign size complex? 'int))]
276 [('float . r) (if core
277 (bad)
278 (loop r quals sign size complex? 'float))]
279 [('double . r) (if core
280 (bad)
281 (loop r quals sign size complex? 'double))]
282 [('_Float128 . r) (if core
283 (bad)
284 (loop r quals sign size complex? 'float128))]
285 [('_Float64x . r) (if core
286 (bad)
287 (loop r quals sign size complex? 'float64x))]
288 [('__ibm128 . r) (if core
289 (bad)
290 (loop r quals sign size complex? 'float-ibm128))]
291 [('unsigned . r) (if sign
292 (bad)
293 (loop r quals 'unsigned size complex? core))]
294 [('signed . r) (if sign
295 (bad)
296 (loop r quals 'signed size complex? core))]
297 [('short . r) (if size
298 (bad)
299 (loop r quals sign 'short complex? core))]
300 [('long . r) (case size
301 [(#f) (loop r quals sign 'long complex? core)]
302 [(long) (loop r quals sign 'long-long complex? core)]
303 [else (bad)])]
304 [('_Complex . r) (if complex?
305 (bad)
306 (loop r quals sign size #t core))]
307 [('__builtin_va_list . r)
308 (if core
309 (bad)
310 (loop r quals sign size complex? 'builtin-va-list))]
311 [('void . r) (loop r quals sign size complex? 'void)]
312 [((and (or 'const 'volatile 'restrict) q) . r)
313 (loop r (cons q quals) sign size complex? core)]
314 [(('ident name) . r) (loop r quals sign size complex? name)]
315 [((and ((or 'struct 'union 'enum) . _) aggregate) . r)
316 (loop r quals sign size complex? aggregate)]
317 [((and ((or 'attribute 'asm) . _) xqual) . r)
318 (loop r (cons xqual quals) sign size complex? core)]
319 [else (bad)])))
320
321 ;; Add qualifier to the 'main' type, which would be attached to the variable.
322 (define (attach-qualifier c-type qual)
323 (define (merge-quals new-qs qs)
324 (if (null? new-qs)
325 qs
326 (let1 qs (merge-quals (cdr new-qs) qs)
327 (if (memq (car new-qs) qs)
328 qs
329 (cons (car new-qs) qs)))))
330 (match c-type
331 [('.pointer qs inner) `(.pointer ,(merge-quals qual qs) ,inner)]
332 [('.array inner . rest) `(.array ,(attach-qualifier inner qual) ,@rest)]
333 [('.function qs . rest) `(.function ,(merge-quals qual qs) ,@rest)]
334 [('.struct tag qs . rest) `(.struct ,tag ,(merge-quals qual qs) ,@rest)]
335 [('.union tag qs . rest) `(.union ,tag ,(merge-quals qual qs) ,@rest)]
336 [('.enum tag qs . rest) `(.enum ,tag ,(merge-quals qual qs) ,@rest)]
337 [('.type name qs inner) `(.type ,name ,(merge-quals qual qs) ,inner)]
338 [(btype qs) `(,btype ,(merge-quals qual qs))]))
339
340 ;; Types and its "weight". The latter is used for type upgrading.
341 (define-constant *integral-type-weight*
342 '((bool . 0) (char . 1) (s-char . 1) (u-char . 2) (short . 3) (u-short 4)
343 (int . 5) (u-int . 6) (long . 7) (u-long . 8) (long-long . 9)
344 (u-long-long . 10)))
345
346 (define-constant *float-type-weight*
347 '((float . 10) (double . 11) (long-double . 12) (long-long-double . 13)))
348
349 (define-constant *complex-type-weight*
350 '((float-complex . 20) (double-complex . 21)
351 (long-double-complex . 11) (long-long-double-complex . 23)))
352
353 (define-constant *type-weight*
354 (append *integral-type-weight*
355 *float-type-weight*
356 *complex-type-weight*))
357
358 ;; Returns <basic-type>, .pointer, .array, .function, .struct, .union, .enum
359 ;; typedef is followed.
360 (define (c-primary-type c-type)
361 (match c-type
362 [('.type _ _ inner) (c-primary-type inner)]
363 [(p . _) p]))
364
365 (define (c-basic-type-integral? c-type)
366 (match c-type
367 [(t _) (boolean (assq t *integral-type-weight*))]
368 [_ #f]))
369
370 (define (c-basic-type-flonum? c-type)
371 (match c-type
372 [(t _) (boolean (assq t *float-type-weight*))]
373 [_ #f]))
374
375 (define (c-basic-type-scalar-numeric? c-type)
376 (match c-type
377 [(t _) (boolean (or (assq t *integral-type-weight*)
378 (assq t *float-type-weight*)))]
379 [_ #f]))
380
381 (define (c-basic-type-numeric? c-type)
382 (match c-type
383 [(t _) (boolean (assq t *type-weight*))]
384 [_ #f]))
385
386 ;; for type coertion. a and b must be numeric types.
387 (define (c-type-narrower? a b)
388 (let ([wa (assq-ref *type-weight* (car a))]
389 [wb (assq-ref *type-weight* (car b))])
390 (< wa wb)))
391
392 (define (c-wider-type c-type-1 c-type-2)
393 (and (c-basic-type-numeric? c-type-1)
394 (c-basic-type-numeric? c-type-2)
395 (if (c-type-narrower? c-type-1 c-type-2)
396 c-type-2
397 c-type-1)))
398
399 ;; strip typedefs and returns the actual type
400 (define (c-actual-type c-type)
401 (match c-type
402 [('.type _ quals inner)
403 (attach-qualifier (c-actual-type inner) quals)]
404 [_ c-type]))
405
406 ;;;
407 ;;; Folding C constant
408 ;;;
409
410 (define-constant *constant-folders*
411 `((+ . ,(^[x y type] (+ x y)))
412 (- . ,(^[x y type] (- x y)))
413 (* . ,(^[x y type] (* x y)))
414 (/ . ,(^[x y type] (if (c-basic-type-integral? type)
415 (quotient x y)
416 (/ x y))))
417 (% . ,(^[x y type] (modulo x y)))
418 (& . ,(^[x y type] (logand x y)))
419 (|\|| . ,(^[x y type] (logior x y)))
420 (^ . ,(^[x y type] (logxor x y)))
421 (<< . ,(^[x y type] (ash x y)))
422 (>> . ,(^[x y type] (ash x (- y))))
423 ))
424
425 ;; If EXPR is foldable, returns (<scheme-value> <c-type>).
426 ;; Otherwise returns #f
427 (define (fold-c-constant expr)
428 (match expr
429 [('const type lit)
430 (cond [(c-basic-type-integral? `(,type ()))
431 (let1 n (if (memq type '(char s-char u-char)) ;;TODO: wchar
432 (char->integer (string-ref lit 0))
433 (string->number (string-trim-right lit #[uUlL])))
434 (if (exact-integer? n)
435 `(,n (,type (const)))
436 (error "bad literal integer constant:" lit)))]
437 [(c-basic-type-flonum? `(,type ()))
438 (let1 n (string->number (string-trim-right lit #[lLfF]))
439 (if (real? n)
440 `(,n (,type (const)))
441 (error "bad floating-point number constant:" lit)))]
442 [else #f])]
443 [((? (cut assq <> *constant-folders*) op) x1 x2)
444 (and-let* ([v1 (fold-c-constant x1)]
445 [v2 (fold-c-constant x2)]
446 [proc (assq-ref *constant-folders* op)]
447 [type (c-wider-type (cadr v1) (cadr v2))])
448 `(,(proc (car v1) (car v2) type) ,type))]
449 [_ #f]))