rucc_sema/expr.rs
1//! Typed expressions.
2//!
3//! Design: `spec/07-types-and-semantics.md` sections 7.2 and 7.14.
4//!
5//! Every node here has a type and a value category, and every conversion the language performs
6//! without being asked is a [`Conversion`] node written into the tree. That is the whole point
7//! of the typed tree: nothing downstream is allowed to work out that an `int` and a `long` must
8//! have met somewhere, because if the two operands of an addition do not already have the same
9//! type then semantic analysis has a bug and the verifier is entitled to say so.
10//!
11//! The operators are [`rucc_ast::UnaryOp`] and [`rucc_ast::BinaryOp`], the same ones the parser
12//! read, rather than a second set with the same names. What the typed tree adds is not different
13//! operators, it is knowing what they are applied to.
14
15use rucc_ast::{BinaryOp, UnaryOp};
16use rucc_base::{Idx, IdxRange};
17use rucc_types::TypeId;
18
19use crate::decl::DeclId;
20use crate::stmt::StmtId;
21use crate::tast::{ConstId, LabelId, StrId};
22
23/// One typed expression in the arena.
24pub type ExprId = Idx<Expr>;
25
26/// The table of references to expressions, which is what a call's arguments are a run of.
27#[derive(Debug)]
28pub struct ExprRef;
29
30/// A run of expressions.
31pub type ExprList = IdxRange<ExprRef>;
32
33/// An expression, its type, and what may be done with it.
34///
35/// Twenty four bytes: the kind, the type it has, and the category it is in. The type is in the
36/// node rather than in a table beside it, which is the opposite of what the untyped tree does
37/// with spans, because everything that walks this tree reads the type at every node and almost
38/// nothing reads the span at any node.
39#[derive(Debug, Clone, Copy, PartialEq, Eq)]
40pub struct Expr {
41 /// What the expression is.
42 pub kind: ExprKind,
43 /// The type it has, after every conversion that applies to it.
44 pub ty: TypeId,
45 /// What may be done with it.
46 pub category: Category,
47}
48
49impl Expr {
50 /// An expression of the given kind, type and category.
51 #[must_use]
52 pub const fn new(kind: ExprKind, ty: TypeId, category: Category) -> Expr {
53 Expr { kind, ty, category }
54 }
55}
56
57/// What may be done with an expression, which C decides rather than the programmer.
58#[derive(Debug, Clone, Copy, PartialEq, Eq)]
59pub enum Category {
60 /// A value. It has no address and nothing may be assigned to it.
61 Rvalue,
62 /// An object. It has an address, it may be assigned to when it is not `const`, and reading
63 /// it is a [`Conversion::Lvalue`] rather than something a reader has to remember.
64 Lvalue,
65 /// A bit-field, which is an lvalue whose address cannot be taken and whose assignment
66 /// truncates to the declared width. Kept apart from an ordinary lvalue because the two
67 /// rules above are the ones a compiler forgets.
68 Bitfield,
69 /// A function designator, which is not an lvalue and which decays to a pointer everywhere
70 /// except under `sizeof` and `&`.
71 Function,
72}
73
74/// What an expression is.
75#[derive(Debug, Clone, Copy, PartialEq, Eq)]
76pub enum ExprKind {
77 /// A node that was already the subject of a diagnostic.
78 ///
79 /// Poisoned, in the sense of `spec/06-lexer-and-parser.md` section 6.8: nothing is reported
80 /// about one of these, which is what stops one bad declaration becoming forty bad uses.
81 Error,
82 /// A constant, in the value table. Every constant that could be folded already has been.
83 Const(ConstId),
84 /// A string literal, which is an array of characters with static storage duration.
85 Str(StrId),
86 /// A use of a declared object or function.
87 Decl(DeclId),
88 /// `base.field` or, after the pointer has been dereferenced, `base->field`.
89 Member {
90 /// The object the field is in.
91 base: ExprId,
92 /// Which field, as an index into the record's field list rather than as a name, since
93 /// the lookup happened here and nothing after this should repeat it.
94 field: u32,
95 },
96 /// `base[index]`, with the pointer operand first however it was written.
97 ///
98 /// Kept as a subscript rather than rewritten into `*(base + index)` because the rewriting
99 /// has exactly one home, which is the walk to the IR, and because a diagnostic about a
100 /// subscript should talk about a subscript.
101 Subscript {
102 /// The pointer, which has already decayed if it was an array.
103 base: ExprId,
104 /// The integer.
105 index: ExprId,
106 },
107 /// `callee(args)`, with the arguments already converted to the parameter types.
108 Call {
109 /// The function, which is a pointer to a function after its decay.
110 callee: ExprId,
111 /// The arguments, in order, each converted to what the prototype asks for and each
112 /// promoted where the prototype does not say.
113 args: ExprList,
114 },
115 /// A prefix or postfix operator on one operand.
116 Unary {
117 /// Which operator.
118 op: UnaryOp,
119 /// What it applies to.
120 operand: ExprId,
121 },
122 /// A binary operator on two operands of the same type, except for the shifts and the
123 /// pointer arithmetic, where the two sides legitimately differ.
124 Binary {
125 /// Which operator.
126 op: BinaryOp,
127 /// The left side.
128 lhs: ExprId,
129 /// The right side.
130 rhs: ExprId,
131 },
132 /// `lhs = rhs`, or a compound assignment with the operator kept as written.
133 Assign {
134 /// The operator of a compound assignment, absent for a plain one.
135 op: Option<BinaryOp>,
136 /// The type the operation is performed in, which is the node's own type for a plain
137 /// assignment and for most compound ones.
138 ///
139 /// It is here because `a op= b` is not `a = a op b` with the conversions left out, and
140 /// the difference is not academic: in `int i = 5; i /= 0.5;` the division happens in
141 /// `double` and the answer is ten, and a compiler that converts the right side to `int`
142 /// first divides by zero. The left side is an lvalue and cannot carry a conversion node
143 /// of its own, so the type it is read into is written here instead, which is what clang
144 /// calls the computation type and for the same reason.
145 computation: TypeId,
146 /// What is assigned to, which is an lvalue.
147 lhs: ExprId,
148 /// What is assigned.
149 rhs: ExprId,
150 },
151 /// `cond ? then : otherwise`, with both arms already converted to the common type.
152 Cond {
153 /// The condition, converted to `bool`.
154 cond: ExprId,
155 /// The arm taken when it is true. GNU's `cond ?: otherwise` has this equal to the
156 /// condition before its conversion, so the value is computed once.
157 then: ExprId,
158 /// The arm taken when it is false.
159 otherwise: ExprId,
160 },
161 /// `lhs, rhs`, whose value is the right side and whose left side is evaluated and dropped.
162 Comma {
163 /// Evaluated first, for its effects.
164 lhs: ExprId,
165 /// The value.
166 rhs: ExprId,
167 },
168 /// A cast the program wrote. The type is the node's type.
169 Cast(ExprId),
170 /// A conversion the language performed. The type is the node's type.
171 Convert {
172 /// Which conversion, so that a reader and the verifier can both tell what happened
173 /// rather than comparing the two types and guessing.
174 kind: Conversion,
175 /// What was converted.
176 operand: ExprId,
177 },
178 /// `(T){ ... }`, which is an unnamed object with an initializer and not a conversion.
179 CompoundLiteral(DeclId),
180 /// `({ ... })`, GNU's statement expression, whose value is its last expression statement.
181 StmtExpr(StmtId),
182 /// `&&label`, GNU's label address.
183 LabelAddr(LabelId),
184 /// `va_arg(list, T)`, which reads the next argument and moves the list on.
185 ///
186 /// The type it fetches is the node's own type, so there is nothing else to hold. It is a
187 /// node rather than a call because what it becomes is the target's own sequence of loads
188 /// and not a function anything links against.
189 VaArg {
190 /// The address of the list, which is what this reads through and moves on.
191 list: ExprId,
192 },
193 /// `va_start(list, last)`, which sets a list to the first argument past the named ones.
194 ///
195 /// What the source wrote as the second argument is not here. It names where the named
196 /// arguments stopped, which the enclosing function's own type already says, and it is not
197 /// evaluated: gcc rewrites `va_start(ap, last)` to a call with a zero in that place and C23
198 /// lets the program leave it out altogether.
199 VaStart {
200 /// The address of the list, which this writes.
201 list: ExprId,
202 },
203 /// `va_end(list)`, which is the end of the reading and is nothing at all on most targets.
204 VaEnd {
205 /// The address of the list.
206 list: ExprId,
207 },
208 /// `va_copy(dst, src)`, which makes a second list standing where the first one stands.
209 VaCopy {
210 /// The address of the list being written.
211 dst: ExprId,
212 /// The address of the list being read, which stays where it is.
213 src: ExprId,
214 },
215}
216
217/// A conversion the language performs without being asked.
218///
219/// Each of these is a node in the tree rather than a difference between two types that a later
220/// pass notices. The IR builder is entitled to assume it never has to insert one, and the
221/// verifier in `spec/08-ir.md` checks that assumption on every function.
222#[derive(Debug, Clone, Copy, PartialEq, Eq)]
223pub enum Conversion {
224 /// Reading an object, which drops the qualifiers and turns an lvalue into a value.
225 Lvalue,
226 /// An array becoming a pointer to its first element.
227 ArrayDecay,
228 /// A function becoming a pointer to itself.
229 FunctionDecay,
230 /// One arithmetic type to another. The integer promotions, the usual arithmetic
231 /// conversions, and the conversions an assignment or an argument performs are all this.
232 Arithmetic,
233 /// A pointer to another pointer type, which includes both directions of `void *`.
234 Pointer,
235 /// A scalar to `bool`, which is a comparison against zero rather than a truncation, and
236 /// which is why it is not [`Conversion::Arithmetic`].
237 Bool,
238 /// A null pointer constant becoming a pointer, which is not the same as converting the
239 /// integer zero, because the constant may have any integer type and `(void *)0` is one.
240 NullPointer,
241 /// A value being discarded, which is what a cast to `void` and an expression statement do.
242 Void,
243}
244
245impl Conversion {
246 /// How the conversion is written in the typed tree's textual form.
247 #[must_use]
248 pub const fn as_str(self) -> &'static str {
249 match self {
250 Conversion::Lvalue => "lvalue",
251 Conversion::ArrayDecay => "array-decay",
252 Conversion::FunctionDecay => "function-decay",
253 Conversion::Arithmetic => "arithmetic",
254 Conversion::Pointer => "pointer",
255 Conversion::Bool => "bool",
256 Conversion::NullPointer => "null-pointer",
257 Conversion::Void => "void",
258 }
259 }
260}