rucc_types/kind.rs
1//! What a C type is made of, before any of it has been interned.
2//!
3//! Design: `spec/07-types-and-semantics.md` section 7.1.
4//!
5//! Everything here is `Copy` and small, because [`TypeKind`] is the interning key and a key
6//! that owns a heap allocation cannot be hashed cheaply or compared cheaply. The two parts of
7//! a type that are genuinely variable length, a function's parameter list and a record's
8//! members, live in side tables and are referred to by index.
9
10use rucc_base::Symbol;
11
12use crate::TypeId;
13
14/// The qualifiers a type can carry.
15///
16/// A bitmask in the interning key rather than a chain of wrapper nodes, so `const int` is one
17/// entry in the table beside `int` rather than a node pointing at it. That makes stripping
18/// qualifiers a field read instead of a walk, which matters because almost every semantic rule
19/// in C is stated on the unqualified type.
20///
21/// `_Atomic` is deliberately not here. C lets it be written in the same position as a
22/// qualifier, but `_Atomic(T)` is a different type from `T` with its own size and alignment,
23/// so it is a type constructor, [`TypeKind::Atomic`], and the parser is what maps the
24/// qualifier spelling onto it.
25#[derive(Debug, Clone, Copy, PartialEq, Eq, Default, Hash, PartialOrd, Ord)]
26pub struct Qualifiers(u8);
27
28impl Qualifiers {
29 /// No qualifiers.
30 pub const NONE: Qualifiers = Qualifiers(0);
31 /// `const`.
32 pub const CONST: Qualifiers = Qualifiers(1);
33 /// `volatile`.
34 pub const VOLATILE: Qualifiers = Qualifiers(2);
35 /// `restrict`.
36 pub const RESTRICT: Qualifiers = Qualifiers(4);
37
38 /// Whether every qualifier in `other` is present here.
39 #[inline]
40 #[must_use]
41 pub const fn has(self, other: Qualifiers) -> bool {
42 self.0 & other.0 == other.0
43 }
44
45 /// This set with `other` added.
46 #[inline]
47 #[must_use]
48 pub const fn with(self, other: Qualifiers) -> Qualifiers {
49 Qualifiers(self.0 | other.0)
50 }
51
52 /// This set with `other` removed.
53 #[inline]
54 #[must_use]
55 pub const fn without(self, other: Qualifiers) -> Qualifiers {
56 Qualifiers(self.0 & !other.0)
57 }
58
59 /// Whether there are no qualifiers at all.
60 #[inline]
61 #[must_use]
62 pub const fn is_none(self) -> bool {
63 self.0 == 0
64 }
65}
66
67/// The standard integer types, the character types kept apart from them, and `__int128`.
68///
69/// `Char` is its own kind rather than an alias for one of the other two. The standard makes
70/// plain `char` a third type distinct from both `signed char` and `unsigned char` even though
71/// it has the same range as one of them, and a compiler that folds it into whichever one the
72/// target picked gets `char *` and `signed char *` wrongly deemed compatible.
73///
74/// `__int128` is here rather than modelled as a `_BitInt(128)`, because the two are different
75/// types with different layouts: `__int128` is sixteen bytes aligned to sixteen on every
76/// target we have, and `_BitInt(128)` is aligned to its granule, which is eight on x86-64. It
77/// is available everywhere for us, since all three architectures are 64-bit, and GCC has it
78/// on every 64-bit target. It is deliberately not an extended integer type in the sense the
79/// standard means, which is what keeps `intmax_t` sixty four bits wide the way GCC has it.
80#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
81pub enum IntKind {
82 /// `char`, whose signedness is a target property.
83 Char,
84 /// `signed char`.
85 SChar,
86 /// `unsigned char`.
87 UChar,
88 /// `short`.
89 Short,
90 /// `unsigned short`.
91 UShort,
92 /// `int`.
93 Int,
94 /// `unsigned int`.
95 UInt,
96 /// `long`, the width that separates LP64 from Windows LLP64.
97 Long,
98 /// `unsigned long`.
99 ULong,
100 /// `long long`.
101 LongLong,
102 /// `unsigned long long`.
103 ULongLong,
104 /// `__int128`.
105 Int128,
106 /// `unsigned __int128`.
107 UInt128,
108}
109
110impl IntKind {
111 /// Every integer kind, in rank order, with `__int128` last.
112 ///
113 /// The order is what the internal index agrees with, and it is also the order the standard
114 /// walks when it picks the type of an integer constant, so a table walk over the candidate
115 /// list for a suffix is a walk over a slice of this. `__int128` is at the end because that
116 /// is where GCC reaches for it: after every standard type has been tried and none of them
117 /// was wide enough.
118 pub const ALL: [IntKind; 13] = [
119 IntKind::Char,
120 IntKind::SChar,
121 IntKind::UChar,
122 IntKind::Short,
123 IntKind::UShort,
124 IntKind::Int,
125 IntKind::UInt,
126 IntKind::Long,
127 IntKind::ULong,
128 IntKind::LongLong,
129 IntKind::ULongLong,
130 IntKind::Int128,
131 IntKind::UInt128,
132 ];
133
134 /// A dense index, so that one of these can select a slot in a fixed size array.
135 pub(crate) const fn index(self) -> usize {
136 match self {
137 IntKind::Char => 0,
138 IntKind::SChar => 1,
139 IntKind::UChar => 2,
140 IntKind::Short => 3,
141 IntKind::UShort => 4,
142 IntKind::Int => 5,
143 IntKind::UInt => 6,
144 IntKind::Long => 7,
145 IntKind::ULong => 8,
146 IntKind::LongLong => 9,
147 IntKind::ULongLong => 10,
148 IntKind::Int128 => 11,
149 IntKind::UInt128 => 12,
150 }
151 }
152
153 /// Whether this type is signed, given what the target says about plain `char`.
154 ///
155 /// The argument is there because `char` is the one integer type whose signedness is not
156 /// in the standard. It is signed on x86-64 and unsigned on AArch64 Linux, and a compiler
157 /// that assumes either one is the source of a whole genre of bug report.
158 #[must_use]
159 pub const fn is_signed(self, char_is_signed: bool) -> bool {
160 match self {
161 IntKind::Char => char_is_signed,
162 IntKind::SChar
163 | IntKind::Short
164 | IntKind::Int
165 | IntKind::Long
166 | IntKind::LongLong
167 | IntKind::Int128 => true,
168 IntKind::UChar
169 | IntKind::UShort
170 | IntKind::UInt
171 | IntKind::ULong
172 | IntKind::ULongLong
173 | IntKind::UInt128 => false,
174 }
175 }
176
177 /// The integer conversion rank, as an ordering rather than as a number from the standard.
178 ///
179 /// The standard gives no values, only a set of relations, and every one of them is a
180 /// comparison between two ranks. Signed and unsigned of the same width share a rank, which
181 /// is what makes the usual arithmetic conversions between them pick the unsigned type
182 /// rather than the wider one.
183 #[must_use]
184 pub const fn rank(self) -> u8 {
185 match self {
186 IntKind::Char | IntKind::SChar | IntKind::UChar => 1,
187 IntKind::Short | IntKind::UShort => 2,
188 IntKind::Int | IntKind::UInt => 3,
189 IntKind::Long | IntKind::ULong => 4,
190 IntKind::LongLong | IntKind::ULongLong => 5,
191 // Above `long long`, which is what makes `__int128 + unsigned long long` an
192 // `__int128` rather than an unsigned type. Both compilers agree.
193 IntKind::Int128 | IntKind::UInt128 => 6,
194 }
195 }
196
197 /// The same width with the other signedness.
198 ///
199 /// `char` maps to `unsigned char` and back to `signed char`, which is the mapping the
200 /// usual arithmetic conversions need and is not a round trip. That asymmetry is the type
201 /// system telling the truth: there is no way back to plain `char` from either of the
202 /// other two.
203 #[must_use]
204 pub const fn flip_sign(self) -> IntKind {
205 match self {
206 IntKind::Char | IntKind::SChar => IntKind::UChar,
207 IntKind::UChar => IntKind::SChar,
208 IntKind::Short => IntKind::UShort,
209 IntKind::UShort => IntKind::Short,
210 IntKind::Int => IntKind::UInt,
211 IntKind::UInt => IntKind::Int,
212 IntKind::Long => IntKind::ULong,
213 IntKind::ULong => IntKind::Long,
214 IntKind::LongLong => IntKind::ULongLong,
215 IntKind::ULongLong => IntKind::LongLong,
216 IntKind::Int128 => IntKind::UInt128,
217 IntKind::UInt128 => IntKind::Int128,
218 }
219 }
220
221 /// How the type is spelled in a diagnostic.
222 #[must_use]
223 pub const fn as_str(self) -> &'static str {
224 match self {
225 IntKind::Char => "char",
226 IntKind::SChar => "signed char",
227 IntKind::UChar => "unsigned char",
228 IntKind::Short => "short",
229 IntKind::UShort => "unsigned short",
230 IntKind::Int => "int",
231 IntKind::UInt => "unsigned int",
232 IntKind::Long => "long",
233 IntKind::ULong => "unsigned long",
234 IntKind::LongLong => "long long",
235 IntKind::ULongLong => "unsigned long long",
236 IntKind::Int128 => "__int128",
237 IntKind::UInt128 => "unsigned __int128",
238 }
239 }
240}
241
242/// The real floating types.
243///
244/// The decimal floating types from C23 are deferred past 1.0 by `spec/19-open-questions.md`
245/// and are deliberately absent rather than present and unimplemented.
246#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
247pub enum FloatKind {
248 /// `float`, always the binary32 format.
249 Float,
250 /// `double`, always the binary64 format.
251 Double,
252 /// `long double`, whose format is a target property and is not always distinct from
253 /// `double`. It is 80 bits of x87 on SysV x86-64, quad precision on AArch64 Linux, and
254 /// the same as `double` on Apple and Windows.
255 LongDouble,
256}
257
258impl FloatKind {
259 /// Every real floating type, in rank order.
260 pub const ALL: [FloatKind; 3] = [FloatKind::Float, FloatKind::Double, FloatKind::LongDouble];
261
262 /// A dense index, so that one of these can select a slot in a fixed size array.
263 pub(crate) const fn index(self) -> usize {
264 match self {
265 FloatKind::Float => 0,
266 FloatKind::Double => 1,
267 FloatKind::LongDouble => 2,
268 }
269 }
270
271 /// The conversion rank, which for floating types is just the ordering.
272 #[must_use]
273 pub const fn rank(self) -> u8 {
274 match self {
275 FloatKind::Float => 1,
276 FloatKind::Double => 2,
277 FloatKind::LongDouble => 3,
278 }
279 }
280
281 /// How the type is spelled in a diagnostic.
282 #[must_use]
283 pub const fn as_str(self) -> &'static str {
284 match self {
285 FloatKind::Float => "float",
286 FloatKind::Double => "double",
287 FloatKind::LongDouble => "long double",
288 }
289 }
290}
291
292/// How many elements an array has, which is four different answers in C.
293#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
294pub enum ArrayLen {
295 /// `int a[4]`. The count of elements, not the size in bytes.
296 Fixed(u64),
297 /// `int a[]`, an incomplete array type. It has an element type and no size, and it is
298 /// completed by an initializer or by a later declaration.
299 Unknown,
300 /// `int a[*]`, a variably modified type in a prototype, where the size exists but is not
301 /// available to the declaration that mentions it.
302 Star,
303 /// `int a[n]`, a variable length array. The size expression stays in the AST, and the
304 /// type carries only the identity of the one that made it, because two variable length
305 /// arrays written with the same element type are still distinct types.
306 Variable(VlaId),
307}
308
309/// The identity of one variable length array's size expression.
310///
311/// An opaque number handed out by whoever is building the type, which in practice is
312/// semantic analysis walking a declarator. This crate never looks inside it; it is here so
313/// that interning two variable length arrays does not accidentally make them the same type.
314#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
315pub struct VlaId(pub u32);
316
317/// Whether a record is a `struct` or a `union`.
318#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
319pub enum RecordKind {
320 /// `struct`, whose members are laid out one after another.
321 Struct,
322 /// `union`, whose members all start at offset zero.
323 Union,
324}
325
326impl RecordKind {
327 /// How the keyword is spelled in a diagnostic.
328 #[must_use]
329 pub const fn as_str(self) -> &'static str {
330 match self {
331 RecordKind::Struct => "struct",
332 RecordKind::Union => "union",
333 }
334 }
335}
336
337/// What a type is, with its qualifiers stripped off into [`Type::quals`].
338///
339/// This is `Copy` and sixteen bytes, which is what lets it be the interning key directly.
340/// Function types and record types are the two that carry a variable amount of information,
341/// and both of them are an index into a table this crate owns.
342#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
343pub enum TypeKind {
344 /// `void`.
345 Void,
346 /// `bool`, which C23 spells without an underscore and which is one byte with two values.
347 Bool,
348 /// One of the standard integer types.
349 Int(IntKind),
350 /// One of the real floating types.
351 Float(FloatKind),
352 /// `_Complex T` for a real floating `T`.
353 Complex(FloatKind),
354 /// `_BitInt(N)` and `unsigned _BitInt(N)`.
355 ///
356 /// A distinct kind rather than an integer type with a width, because these do not take
357 /// part in the integer promotions and folding them in with the standard types is how
358 /// that rule gets forgotten.
359 BitInt {
360 /// Whether the type is signed. A signed `_BitInt(1)` is legal and holds `0` and `-1`.
361 signed: bool,
362 /// The declared width in bits, which is what the standard calls `N`.
363 width: u32,
364 },
365 /// A pointer to the given type.
366 Pointer(TypeId),
367 /// `_Atomic(T)`, which is a type and not a qualifier. See [`Qualifiers`].
368 Atomic(TypeId),
369 /// An array of the given element type.
370 Array {
371 /// The element type.
372 elem: TypeId,
373 /// How many of them there are, which may be unknown.
374 len: ArrayLen,
375 },
376 /// A function type, whose parameter list is in this crate's side table.
377 Function(FunctionId),
378 /// A GNU vector type, `__attribute__((vector_size(n)))`.
379 Vector {
380 /// The element type, which must be a scalar.
381 elem: TypeId,
382 /// How many elements there are.
383 len: u32,
384 },
385 /// A `struct` or `union`, identified by its declaration rather than by its members.
386 Record(RecordId),
387 /// An `enum`, identified by its declaration.
388 Enum(EnumId),
389 /// A typedef name, which is sugar over whatever it was declared as.
390 ///
391 /// Every semantic decision reads [`Types::canonical`](crate::Types::canonical) and never
392 /// sees this; every diagnostic reads the type as written and sees nothing else, so the
393 /// error says `size_t` rather than `unsigned long`. Compilers that drop the sugar produce
394 /// messages nobody can act on, and compilers that decide on the sugar produce wrong
395 /// answers, and both are common.
396 Typedef {
397 /// The name, for printing.
398 name: Symbol,
399 /// What it was declared as.
400 underlying: TypeId,
401 },
402}
403
404/// A type with its qualifiers, which together are one entry in the type table.
405#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
406pub struct Type {
407 /// What the type is.
408 pub kind: TypeKind,
409 /// What it is qualified with.
410 pub quals: Qualifiers,
411}
412
413impl Type {
414 /// An unqualified type of the given kind.
415 #[must_use]
416 pub const fn new(kind: TypeKind) -> Type {
417 Type { kind, quals: Qualifiers::NONE }
418 }
419}
420
421/// The identity of a function type in [`Types`](crate::Types).
422///
423/// Deduplicated by content, so two declarations written with the same return type, the same
424/// parameters and the same variadic flag share one of these and therefore one [`TypeId`].
425#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
426pub struct FunctionId(pub(crate) u32);
427
428/// The identity of a `struct` or `union` declaration in [`Types`](crate::Types).
429///
430/// Not deduplicated by content, because record types in C are nominal. Two `struct` types
431/// written with the same members in the same translation unit are different types, and the
432/// looser relation that does hold between them is compatibility rather than identity.
433#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
434pub struct RecordId(pub(crate) u32);
435
436/// The identity of an `enum` declaration in [`Types`](crate::Types).
437#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
438pub struct EnumId(pub(crate) u32);
439
440/// A function type.
441#[derive(Debug, Clone, PartialEq, Eq, Hash)]
442pub struct FunctionType {
443 /// What it returns.
444 pub ret: TypeId,
445 /// The parameter types, after the adjustments a parameter declaration gets: an array
446 /// parameter has already decayed to a pointer and a function parameter to a function
447 /// pointer, because those adjustments are part of forming the type and not part of
448 /// calling it.
449 pub params: Vec<TypeId>,
450 /// Whether the list ends in `...`.
451 pub variadic: bool,
452 /// Whether there was a prototype at all.
453 ///
454 /// `int f()` declares an unprototyped function before C23 and a function taking no
455 /// arguments from C23 onwards, and the difference is visible in what calls are checked
456 /// and in what the composite type of a redeclaration is. The dialect decides which
457 /// meaning `()` gets, and this records the decision rather than repeating it.
458 pub prototyped: bool,
459}