rucc_sema/expr.rs
1//! Typed expressions.
2//!
3//! Design: `spec/07-types-and-semantics.md` sections 7.2 and 7.12.
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 argument list, which is an lvalue that this modifies.
191 list: ExprId,
192 },
193}
194
195/// A conversion the language performs without being asked.
196///
197/// Each of these is a node in the tree rather than a difference between two types that a later
198/// pass notices. The IR builder is entitled to assume it never has to insert one, and the
199/// verifier in `spec/08-ir.md` checks that assumption on every function.
200#[derive(Debug, Clone, Copy, PartialEq, Eq)]
201pub enum Conversion {
202 /// Reading an object, which drops the qualifiers and turns an lvalue into a value.
203 Lvalue,
204 /// An array becoming a pointer to its first element.
205 ArrayDecay,
206 /// A function becoming a pointer to itself.
207 FunctionDecay,
208 /// One arithmetic type to another. The integer promotions, the usual arithmetic
209 /// conversions, and the conversions an assignment or an argument performs are all this.
210 Arithmetic,
211 /// A pointer to another pointer type, which includes both directions of `void *`.
212 Pointer,
213 /// A scalar to `bool`, which is a comparison against zero rather than a truncation, and
214 /// which is why it is not [`Conversion::Arithmetic`].
215 Bool,
216 /// A null pointer constant becoming a pointer, which is not the same as converting the
217 /// integer zero, because the constant may have any integer type and `(void *)0` is one.
218 NullPointer,
219 /// A value being discarded, which is what a cast to `void` and an expression statement do.
220 Void,
221}
222
223impl Conversion {
224 /// How the conversion is written in the typed tree's textual form.
225 #[must_use]
226 pub const fn as_str(self) -> &'static str {
227 match self {
228 Conversion::Lvalue => "lvalue",
229 Conversion::ArrayDecay => "array-decay",
230 Conversion::FunctionDecay => "function-decay",
231 Conversion::Arithmetic => "arithmetic",
232 Conversion::Pointer => "pointer",
233 Conversion::Bool => "bool",
234 Conversion::NullPointer => "null-pointer",
235 Conversion::Void => "void",
236 }
237 }
238}