charon_lib/ast/expressions.rs
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587
//! Implements expressions: paths, operands, rvalues, lvalues
use crate::gast::*;
use crate::types::*;
use crate::values::*;
use derive_visitor::{Drive, DriveMut};
use macros::{EnumAsGetters, EnumIsA, EnumToGetters, VariantIndexArity, VariantName};
use serde::{Deserialize, Serialize};
use std::vec::Vec;
#[derive(Debug, PartialEq, Eq, Clone, Serialize, Deserialize, Drive, DriveMut)]
pub struct Place {
// TODO: update to transform to a recursive type
pub var_id: VarId,
pub projection: Projection,
}
pub type Projection = Vec<ProjectionElem>;
/// Note that we don't have the equivalent of "downcasts".
/// Downcasts are actually necessary, for instance when initializing enumeration
/// values: the value is initially `Bottom`, and we need a way of knowing the
/// variant.
/// For example:
/// `((_0 as Right).0: T2) = move _1;`
/// In MIR, downcasts always happen before field projections: in our internal
/// language, we thus merge downcasts and field projections.
#[derive(
Debug,
PartialEq,
Eq,
Clone,
EnumIsA,
EnumAsGetters,
EnumToGetters,
VariantName,
Serialize,
Deserialize,
Drive,
DriveMut,
)]
pub enum ProjectionElem {
/// Dereference a shared/mutable reference, a box, or a raw pointer.
Deref,
/// Projection from ADTs (variants, structures).
/// We allow projections to be used as left-values and right-values.
/// We should never have projections to fields of symbolic variants (they
/// should have been expanded before through a match).
Field(FieldProjKind, FieldId),
/// MIR imposes that the argument to an index projection be a local variable, meaning
/// that even constant indices into arrays are let-bound as separate variables.
/// We **eliminate** this variant in a micro-pass.
#[charon::opaque]
Index {
offset: Operand,
from_end: bool,
// Type of the array/slice that we index into.
ty: Ty,
},
/// Take a subslice of a slice or array. If `from_end` is `true` this is
/// `slice[from..slice.len() - to]`, otherwise this is `slice[from..to]`.
/// We **eliminate** this variant in a micro-pass.
#[charon::opaque]
Subslice {
from: Operand,
to: Operand,
from_end: bool,
// Type of the array/slice that we index into.
ty: Ty,
},
}
#[derive(
Debug,
PartialEq,
Eq,
Copy,
Clone,
EnumIsA,
EnumAsGetters,
Serialize,
Deserialize,
Drive,
DriveMut,
)]
#[charon::variants_prefix("Proj")]
pub enum FieldProjKind {
Adt(TypeDeclId, Option<VariantId>),
/// If we project from a tuple, the projection kind gives the arity of the tuple.
Tuple(usize),
/// Access to a field in a closure state.
/// We eliminate this in a micro-pass ([crate::update_closure_signatures]).
#[charon::opaque]
ClosureState,
}
#[derive(
Debug,
PartialEq,
Eq,
Copy,
Clone,
EnumIsA,
EnumAsGetters,
Serialize,
Deserialize,
Drive,
DriveMut,
)]
#[charon::variants_prefix("B")]
pub enum BorrowKind {
Shared,
Mut,
/// See <https://doc.rust-lang.org/beta/nightly-rustc/rustc_middle/mir/enum.MutBorrowKind.html#variant.TwoPhaseBorrow>
/// and <https://rustc-dev-guide.rust-lang.org/borrow_check/two_phase_borrows.html>
TwoPhaseMut,
/// Those are typically introduced when using guards in matches, to make sure guards don't
/// change the variant of an enum value while me match over it.
///
/// See <https://doc.rust-lang.org/beta/nightly-rustc/rustc_middle/mir/enum.FakeBorrowKind.html#variant.Shallow>.
Shallow,
/// Data must be immutable but not aliasable. In other words you can't mutate the data but you
/// can mutate *through it*, e.g. if it points to a `&mut T`. This is only used in closure
/// captures, e.g.
/// ```rust,ignore
/// let mut z = 3;
/// let x: &mut isize = &mut z;
/// let y = || *x += 5;
/// ```
/// Here the captured variable can't be `&mut &mut x` since the `x` binding is not mutable, yet
/// we must be able to mutate what it points to.
///
/// See <https://doc.rust-lang.org/beta/nightly-rustc/rustc_middle/mir/enum.MutBorrowKind.html#variant.ClosureCapture>.
UniqueImmutable,
}
/// Unary operation
#[derive(
Debug, PartialEq, Eq, Clone, EnumIsA, VariantName, Serialize, Deserialize, Drive, DriveMut,
)]
#[charon::rename("Unop")]
pub enum UnOp {
Not,
/// This can overflow. In practice, rust introduces an assert before
/// (in debug mode) to check that it is not equal to the minimum integer
/// value (for the proper type).
Neg,
/// Casts are rvalues in MIR, but we treat them as unops.
Cast(CastKind),
/// Coercion from array (i.e., [T; N]) to slice.
///
/// **Remark:** We introduce this unop when translating from MIR, **then transform**
/// it to a function call in a micro pass. The type and the scalar value are not
/// *necessary* as we can retrieve them from the context, but storing them here is
/// very useful. The [RefKind] argument states whethere we operate on a mutable
/// or a shared borrow to an array.
#[charon::opaque]
ArrayToSlice(RefKind, Ty, ConstGeneric),
}
/// Nullary operation
#[derive(
Debug, PartialEq, Eq, Clone, EnumIsA, VariantName, Serialize, Deserialize, Drive, DriveMut,
)]
#[charon::rename("Nullop")]
pub enum NullOp {
SizeOf,
AlignOf,
OffsetOf(Vec<(usize, FieldId)>),
UbChecks,
}
/// For all the variants: the first type gives the source type, the second one gives
/// the destination type.
#[derive(
Debug, PartialEq, Eq, Clone, EnumIsA, VariantName, Serialize, Deserialize, Drive, DriveMut,
)]
#[charon::variants_prefix("Cast")]
pub enum CastKind {
/// Conversion between types in {Integer, Bool}
/// Remark: for now we don't support conversions with Char.
Scalar(LiteralTy, LiteralTy),
RawPtr(Ty, Ty),
FnPtr(Ty, Ty),
/// [Unsize coercion](https://doc.rust-lang.org/std/ops/trait.CoerceUnsized.html). This is
/// either `[T; N]` -> `[T]` or `T: Trait` -> `dyn Trait` coercions, behind a pointer
/// (reference, `Box`, or other type that implements `CoerceUnsized`).
///
/// The special case of `&[T; N]` -> `&[T]` coercion is caught by `UnOp::ArrayToSlice`.
Unsize(Ty, Ty),
/// Reinterprets the bits of a value of one type as another type, i.e. exactly what
/// [`std::mem::transmute`] does.
Transmute(Ty, Ty),
}
/// Binary operations.
#[derive(
Debug, PartialEq, Eq, Copy, Clone, EnumIsA, VariantName, Serialize, Deserialize, Drive, DriveMut,
)]
#[charon::rename("Binop")]
pub enum BinOp {
BitXor,
BitAnd,
BitOr,
Eq,
Lt,
Le,
Ne,
Ge,
Gt,
/// Fails if the divisor is 0, or if the operation is `int::MIN / -1`.
Div,
/// Fails if the divisor is 0, or if the operation is `int::MIN % -1`.
Rem,
/// Fails on overflow.
Add,
/// Fails on overflow.
Sub,
/// Fails on overflow.
Mul,
/// Returns `(result, did_overflow)`, where `result` is the result of the operation with
/// wrapping semantics, and `did_overflow` is a boolean that indicates whether the operation
/// overflowed. This operation does not fail.
CheckedAdd,
/// Like `CheckedAdd`.
CheckedSub,
/// Like `CheckedAdd`.
CheckedMul,
/// Fails if the shift is bigger than the bit-size of the type.
Shl,
/// Fails if the shift is bigger than the bit-size of the type.
Shr,
// No Offset binary operation: this is an operation on raw pointers
}
#[derive(
Debug,
PartialEq,
Eq,
Clone,
EnumIsA,
EnumToGetters,
EnumAsGetters,
VariantName,
Serialize,
Deserialize,
Drive,
DriveMut,
)]
pub enum Operand {
Copy(Place),
Move(Place),
/// Constant value (including constant and static variables)
#[charon::rename("Constant")]
Const(ConstantExpr),
}
/// A function identifier. See [crate::ullbc_ast::Terminator]
#[derive(
Debug,
Clone,
PartialEq,
Eq,
EnumIsA,
EnumAsGetters,
VariantName,
Serialize,
Deserialize,
Drive,
DriveMut,
)]
#[charon::variants_prefix("F")]
pub enum FunId {
/// A "regular" function (function local to the crate, external function
/// not treated as a primitive one).
Regular(FunDeclId),
/// A primitive function, coming from a standard library (for instance:
/// `alloc::boxed::Box::new`).
/// TODO: rename to "Primitive"
#[charon::rename("FAssumed")]
Builtin(BuiltinFunId),
}
/// An built-in function identifier, identifying a function coming from a
/// standard library.
#[derive(
Debug,
Clone,
Copy,
PartialEq,
Eq,
EnumIsA,
EnumAsGetters,
VariantName,
Serialize,
Deserialize,
Drive,
DriveMut,
)]
#[charon::rename("AssumedFunId")]
pub enum BuiltinFunId {
/// `alloc::boxed::Box::new`
BoxNew,
/// Cast an array as a slice.
///
/// Converted from [UnOp::ArrayToSlice]
ArrayToSliceShared,
/// Cast an array as a slice.
///
/// Converted from [UnOp::ArrayToSlice]
ArrayToSliceMut,
/// `repeat(n, x)` returns an array where `x` has been replicated `n` times.
///
/// We introduce this when desugaring the [ArrayRepeat] rvalue.
ArrayRepeat,
/// Converted from indexing `ProjectionElem`s. The signature depends on the parameters. It
/// could look like:
/// - `fn ArrayIndexShared<T,N>(&[T;N], usize) -> &T`
/// - `fn SliceIndexShared<T>(&[T], usize) -> &T`
/// - `fn ArraySubSliceShared<T,N>(&[T;N], usize, usize) -> &[T]`
/// - `fn SliceSubSliceMut<T>(&mut [T], usize, usize) -> &mut [T]`
/// - etc
Index(BuiltinIndexOp),
}
/// One of 8 built-in indexing operations.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize, Drive, DriveMut)]
pub struct BuiltinIndexOp {
/// Whether this is a slice or array.
pub is_array: bool,
/// Whether we're indexing mutably or not. Determines the type ofreference of the input and
/// output.
pub mutability: RefKind,
/// Whether we're indexing a single element or a subrange. If `true`, the function takes
/// two indices and the output is a slice; otherwise, the function take one index and the
/// output is a reference to a single element.
pub is_range: bool,
}
#[derive(Debug, Clone, PartialEq, Eq, EnumAsGetters, Serialize, Deserialize, Drive, DriveMut)]
pub enum FunIdOrTraitMethodRef {
#[charon::rename("FunId")]
Fun(FunId),
/// If a trait: the reference to the trait and the id of the trait method.
/// The fun decl id is not really necessary - we put it here for convenience
/// purposes.
#[charon::rename("TraitMethod")]
Trait(TraitRef, TraitItemName, FunDeclId),
}
#[derive(Debug, PartialEq, Eq, Clone, Serialize, Deserialize, Drive, DriveMut)]
pub struct FnPtr {
pub func: FunIdOrTraitMethodRef,
pub generics: GenericArgs,
}
/// A constant expression.
///
/// Only the [Literal] and [Var] cases are left in the final LLBC.
///
/// The other cases come from a straight translation from the MIR:
///
/// [Adt] case:
/// It is a bit annoying, but rustc treats some ADT and tuple instances as
/// constants when generating MIR:
/// - an enumeration with one variant and no fields is a constant.
/// - a structure with no field is a constant.
/// - sometimes, Rust stores the initialization of an ADT as a constant
/// (if all the fields are constant) rather than as an aggregated value
/// We later desugar those to regular ADTs, see [regularize_constant_adts.rs].
///
/// [Global] case: access to a global variable. We later desugar it to
/// a separate statement.
///
/// [Ref] case: reference to a constant value. We later desugar it to a separate
/// statement.
///
/// [FnPtr] case: a function pointer (to a top-level function).
///
/// Remark:
/// MIR seems to forbid more complex expressions like paths. For instance,
/// reading the constant `a.b` is translated to `{ _1 = const a; _2 = (_1.0) }`.
#[derive(
Debug,
PartialEq,
Eq,
Clone,
VariantName,
EnumIsA,
EnumAsGetters,
Serialize,
Deserialize,
Drive,
DriveMut,
)]
#[charon::variants_prefix("C")]
pub enum RawConstantExpr {
Literal(Literal),
///
/// In most situations:
/// Enumeration with one variant with no fields, structure with
/// no fields, unit (encoded as a 0-tuple).
///
/// Less frequently: arbitrary ADT values.
///
/// We eliminate this case in a micro-pass.
#[charon::opaque]
Adt(Option<VariantId>, Vec<ConstantExpr>),
/// The value is a top-level constant/static.
///
/// We eliminate this case in a micro-pass.
///
/// Remark: constants can actually have generic parameters.
/// ```text
/// struct V<const N: usize, T> {
/// x: [T; N],
/// }
///
/// impl<const N: usize, T> V<N, T> {
/// const LEN: usize = N; // This has generics <N, T>
/// }
///
/// fn use_v<const N: usize, T>(v: V<N, T>) {
/// let l = V::<N, T>::LEN; // We need to provided a substitution here
/// }
/// ```
#[charon::opaque]
Global(GlobalDeclRef),
///
/// A trait constant.
///
/// Ex.:
/// ```text
/// impl Foo for Bar {
/// const C : usize = 32; // <-
/// }
/// ```
///
/// Remark: trait constants can not be used in types, they are necessarily
/// values.
TraitConst(TraitRef, TraitItemName),
/// A shared reference to a constant value.
///
/// We eliminate this case in a micro-pass.
#[charon::opaque]
Ref(Box<ConstantExpr>),
/// A mutable pointer to a mutable static.
///
/// We eliminate this case in a micro-pass.
#[charon::opaque]
MutPtr(Box<ConstantExpr>),
/// A const generic var
Var(ConstGenericVarId),
/// Function pointer
FnPtr(FnPtr),
}
#[derive(Debug, PartialEq, Eq, Clone, Serialize, Deserialize, Drive, DriveMut)]
pub struct ConstantExpr {
pub value: RawConstantExpr,
pub ty: Ty,
}
/// TODO: we could factor out [Rvalue] and function calls (for LLBC, not ULLBC).
/// We can also factor out the unops, binops with the function calls.
/// TODO: move the aggregate kind to operands
/// TODO: we should prefix the type variants with "R" or "Rv", this would avoid collisions
#[derive(
Debug, Clone, EnumToGetters, EnumAsGetters, EnumIsA, Serialize, Deserialize, Drive, DriveMut,
)]
pub enum Rvalue {
/// Lifts an operand as an rvalue.
Use(Operand),
/// Takes a reference to the given place.
#[charon::rename("RvRef")]
Ref(Place, BorrowKind),
/// Takes a raw pointer with the given mutability to the given place. This is generated by
/// pointer casts like `&v as *const _` or raw borrow expressions like `&raw const v.`
RawPtr(Place, RefKind),
/// Binary operations (note that we merge "checked" and "unchecked" binops)
BinaryOp(BinOp, Operand, Operand),
/// Unary operation (e.g. not, neg)
UnaryOp(UnOp, Operand),
/// Nullary operation (e.g. `size_of`)
NullaryOp(NullOp, Ty),
/// Discriminant (for enumerations).
/// Note that discriminant values have type isize. We also store the identifier
/// of the type from which we read the discriminant.
///
/// This case is filtered in [crate::remove_read_discriminant]
Discriminant(Place, TypeDeclId),
/// Creates an aggregate value, like a tuple, a struct or an enum:
/// ```text
/// l = List::Cons { value:x, tail:tl };
/// ```
/// Note that in some MIR passes (like optimized MIR), aggregate values are
/// decomposed, like below:
/// ```text
/// (l as List::Cons).value = x;
/// (l as List::Cons).tail = tl;
/// ```
/// Because we may want to plug our translation mechanism at various
/// places, we need to take both into accounts in the translation and in
/// our semantics. Aggregate value initialization is easy, you might want
/// to have a look at expansion of `Bottom` values for explanations about the
/// other case.
///
/// Remark: in case of closures, the aggregated value groups the closure id
/// together with its state.
Aggregate(AggregateKind, Vec<Operand>),
/// Copy the value of the referenced global.
/// Not present in MIR; introduced in [simplify_constants.rs].
Global(GlobalDeclRef),
/// Reference the value of the global. This has type `&T` or `*mut T` depending on desired
/// mutability.
/// Not present in MIR; introduced in [simplify_constants.rs].
GlobalRef(GlobalDeclRef, RefKind),
/// Length of a memory location. The run-time length of e.g. a vector or a slice is
/// represented differently (but pretty-prints the same, FIXME).
/// Should be seen as a function of signature:
/// - `fn<T;N>(&[T;N]) -> usize`
/// - `fn<T>(&[T]) -> usize`
///
/// We store the type argument and the const generic (the latter only for arrays).
///
/// [Len] is automatically introduced by rustc, notably for the bound checks:
/// we eliminate it together with the bounds checks whenever possible.
/// There are however occurrences that we don't eliminate (yet).
/// For instance, for the following Rust code:
/// ```text
/// fn slice_pattern_4(x: &[()]) {
/// match x {
/// [_named] => (),
/// _ => (),
/// }
/// }
/// ```
/// rustc introduces a check that the length of the slice is exactly equal
/// to 1 and that we preserve.
Len(Place, Ty, Option<ConstGeneric>),
/// [Repeat(x, n)] creates an array where [x] is copied [n] times.
///
/// We translate this to a function call.
#[charon::opaque]
Repeat(Operand, Ty, ConstGeneric),
/// Transmutes a `*mut u8` (obtained from `malloc`) into shallow-initialized `Box<T>`. This
/// only appears as part of lowering `Box::new()` in some cases. We reconstruct the original
/// `Box::new()` call.
#[charon::opaque]
ShallowInitBox(Operand, Ty),
}
/// An aggregated ADT.
///
/// Note that ADTs are desaggregated at some point in MIR. For instance, if
/// we have in Rust:
/// ```ignore
/// let ls = Cons(hd, tl);
/// ```
///
/// In MIR we have (yes, the discriminant update happens *at the end* for some
/// reason):
/// ```text
/// (ls as Cons).0 = move hd;
/// (ls as Cons).1 = move tl;
/// discriminant(ls) = 0; // assuming `Cons` is the variant of index 0
/// ```
///
/// Rem.: in the Aeneas semantics, both cases are handled (in case of desaggregated
/// initialization, `ls` is initialized to `⊥`, then this `⊥` is expanded to
/// `Cons (⊥, ⊥)` upon the first assignment, at which point we can initialize
/// the field 0, etc.).
#[derive(Debug, Clone, VariantIndexArity, Serialize, Deserialize, Drive, DriveMut)]
#[charon::variants_prefix("Aggregated")]
pub enum AggregateKind {
/// A struct, enum or union aggregate. The `VariantId`, if present, indicates this is an enum
/// and the aggregate uses that variant. The `FieldId`, if present, indicates this is a union
/// and the aggregate writes into that field. Otherwise this is a struct.
Adt(TypeId, Option<VariantId>, Option<FieldId>, GenericArgs),
/// We don't put this with the ADT cas because this is the only built-in type
/// with aggregates, and it is a primitive type. In particular, it makes
/// sense to treat it differently because it has a variable number of fields.
Array(Ty, ConstGeneric),
/// Aggregated values for closures group the function id together with its
/// state.
Closure(FunDeclId, GenericArgs),
}