rustc_middle/mir/interpret/
mod.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
//! An interpreter for MIR used in CTFE and by miri.

#[macro_use]
mod error;

mod allocation;
mod pointer;
mod queries;
mod value;

use std::io::{Read, Write};
use std::num::NonZero;
use std::{fmt, io};

use rustc_ast::LitKind;
use rustc_data_structures::fx::FxHashMap;
use rustc_data_structures::sync::Lock;
use rustc_errors::ErrorGuaranteed;
use rustc_hir::def_id::{DefId, LocalDefId};
use rustc_macros::{HashStable, TyDecodable, TyEncodable, TypeFoldable, TypeVisitable};
use rustc_middle::ty::print::with_no_trimmed_paths;
use rustc_serialize::{Decodable, Encodable};
use rustc_target::abi::{AddressSpace, Endian, HasDataLayout};
use tracing::{debug, trace};
// Also make the error macros available from this module.
pub use {
    err_exhaust, err_inval, err_machine_stop, err_ub, err_ub_custom, err_ub_format, err_unsup,
    err_unsup_format, throw_exhaust, throw_inval, throw_machine_stop, throw_ub, throw_ub_custom,
    throw_ub_format, throw_unsup, throw_unsup_format,
};

pub use self::allocation::{
    AllocBytes, AllocError, AllocRange, AllocResult, Allocation, ConstAllocation, InitChunk,
    InitChunkIter, alloc_range,
};
pub use self::error::{
    BadBytesAccess, CheckAlignMsg, CheckInAllocMsg, ErrorHandled, EvalStaticInitializerRawResult,
    EvalToAllocationRawResult, EvalToConstValueResult, EvalToValTreeResult, ExpectedKind,
    InterpError, InterpErrorInfo, InterpResult, InvalidMetaKind, InvalidProgramInfo,
    MachineStopType, Misalignment, PointerKind, ReportedErrorInfo, ResourceExhaustionInfo,
    ScalarSizeMismatch, UndefinedBehaviorInfo, UnsupportedOpInfo, ValidationErrorInfo,
    ValidationErrorKind, interp_ok,
};
pub use self::pointer::{CtfeProvenance, Pointer, PointerArithmetic, Provenance};
pub use self::value::Scalar;
use crate::mir;
use crate::ty::codec::{TyDecoder, TyEncoder};
use crate::ty::{self, Instance, Ty, TyCtxt};

/// Uniquely identifies one of the following:
/// - A constant
/// - A static
#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash, TyEncodable, TyDecodable)]
#[derive(HashStable, TypeFoldable, TypeVisitable)]
pub struct GlobalId<'tcx> {
    /// For a constant or static, the `Instance` of the item itself.
    /// For a promoted global, the `Instance` of the function they belong to.
    pub instance: ty::Instance<'tcx>,

    /// The index for promoted globals within their function's `mir::Body`.
    pub promoted: Option<mir::Promoted>,
}

impl<'tcx> GlobalId<'tcx> {
    pub fn display(self, tcx: TyCtxt<'tcx>) -> String {
        let instance_name = with_no_trimmed_paths!(tcx.def_path_str(self.instance.def.def_id()));
        if let Some(promoted) = self.promoted {
            format!("{instance_name}::{promoted:?}")
        } else {
            instance_name
        }
    }
}

/// Input argument for `tcx.lit_to_const`.
#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash, HashStable)]
pub struct LitToConstInput<'tcx> {
    /// The absolute value of the resultant constant.
    pub lit: &'tcx LitKind,
    /// The type of the constant.
    pub ty: Ty<'tcx>,
    /// If the constant is negative.
    pub neg: bool,
}

/// Error type for `tcx.lit_to_const`.
#[derive(Copy, Clone, Debug, Eq, PartialEq, HashStable)]
pub enum LitToConstError {
    /// The literal's inferred type did not match the expected `ty` in the input.
    /// This is used for graceful error handling (`span_delayed_bug`) in
    /// type checking (`Const::from_anon_const`).
    TypeError,
    Reported(ErrorGuaranteed),
}

#[derive(Copy, Clone, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct AllocId(pub NonZero<u64>);

// We want the `Debug` output to be readable as it is used by `derive(Debug)` for
// all the Miri types.
impl fmt::Debug for AllocId {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if f.alternate() { write!(f, "a{}", self.0) } else { write!(f, "alloc{}", self.0) }
    }
}

// No "Display" since AllocIds are not usually user-visible.

#[derive(TyDecodable, TyEncodable)]
enum AllocDiscriminant {
    Alloc,
    Fn,
    VTable,
    Static,
}

pub fn specialized_encode_alloc_id<'tcx, E: TyEncoder<I = TyCtxt<'tcx>>>(
    encoder: &mut E,
    tcx: TyCtxt<'tcx>,
    alloc_id: AllocId,
) {
    match tcx.global_alloc(alloc_id) {
        GlobalAlloc::Memory(alloc) => {
            trace!("encoding {:?} with {:#?}", alloc_id, alloc);
            AllocDiscriminant::Alloc.encode(encoder);
            alloc.encode(encoder);
        }
        GlobalAlloc::Function { instance } => {
            trace!("encoding {:?} with {:#?}", alloc_id, instance);
            AllocDiscriminant::Fn.encode(encoder);
            instance.encode(encoder);
        }
        GlobalAlloc::VTable(ty, poly_trait_ref) => {
            trace!("encoding {:?} with {ty:#?}, {poly_trait_ref:#?}", alloc_id);
            AllocDiscriminant::VTable.encode(encoder);
            ty.encode(encoder);
            poly_trait_ref.encode(encoder);
        }
        GlobalAlloc::Static(did) => {
            assert!(!tcx.is_thread_local_static(did));
            // References to statics doesn't need to know about their allocations,
            // just about its `DefId`.
            AllocDiscriminant::Static.encode(encoder);
            // Cannot use `did.encode(encoder)` because of a bug around
            // specializations and method calls.
            Encodable::<E>::encode(&did, encoder);
        }
    }
}

#[derive(Clone)]
enum State {
    Empty,
    Done(AllocId),
}

pub struct AllocDecodingState {
    // For each `AllocId`, we keep track of which decoding state it's currently in.
    decoding_state: Vec<Lock<State>>,
    // The offsets of each allocation in the data stream.
    data_offsets: Vec<u64>,
}

impl AllocDecodingState {
    #[inline]
    pub fn new_decoding_session(&self) -> AllocDecodingSession<'_> {
        AllocDecodingSession { state: self }
    }

    pub fn new(data_offsets: Vec<u64>) -> Self {
        let decoding_state =
            std::iter::repeat_with(|| Lock::new(State::Empty)).take(data_offsets.len()).collect();

        Self { decoding_state, data_offsets }
    }
}

#[derive(Copy, Clone)]
pub struct AllocDecodingSession<'s> {
    state: &'s AllocDecodingState,
}

impl<'s> AllocDecodingSession<'s> {
    /// Decodes an `AllocId` in a thread-safe way.
    pub fn decode_alloc_id<'tcx, D>(&self, decoder: &mut D) -> AllocId
    where
        D: TyDecoder<I = TyCtxt<'tcx>>,
    {
        // Read the index of the allocation.
        let idx = usize::try_from(decoder.read_u32()).unwrap();
        let pos = usize::try_from(self.state.data_offsets[idx]).unwrap();

        // Decode the `AllocDiscriminant` now so that we know if we have to reserve an
        // `AllocId`.
        let (alloc_kind, pos) = decoder.with_position(pos, |decoder| {
            let alloc_kind = AllocDiscriminant::decode(decoder);
            (alloc_kind, decoder.position())
        });

        // We are going to hold this lock during the entire decoding of this allocation, which may
        // require that we decode other allocations. This cannot deadlock for two reasons:
        //
        // At the time of writing, it is only possible to create an allocation that contains a pointer
        // to itself using the const_allocate intrinsic (which is for testing only), and even attempting
        // to evaluate such consts blows the stack. If we ever grow a mechanism for producing
        // cyclic allocations, we will need a new strategy for decoding that doesn't bring back
        // https://github.com/rust-lang/rust/issues/126741.
        //
        // It is also impossible to create two allocations (call them A and B) where A is a pointer to B, and B
        // is a pointer to A, because attempting to evaluate either of those consts will produce a
        // query cycle, failing compilation.
        let mut entry = self.state.decoding_state[idx].lock();
        // Check the decoding state to see if it's already decoded or if we should
        // decode it here.
        if let State::Done(alloc_id) = *entry {
            return alloc_id;
        }

        // Now decode the actual data.
        let alloc_id = decoder.with_position(pos, |decoder| match alloc_kind {
            AllocDiscriminant::Alloc => {
                trace!("creating memory alloc ID");
                let alloc = <ConstAllocation<'tcx> as Decodable<_>>::decode(decoder);
                trace!("decoded alloc {:?}", alloc);
                decoder.interner().reserve_and_set_memory_alloc(alloc)
            }
            AllocDiscriminant::Fn => {
                trace!("creating fn alloc ID");
                let instance = ty::Instance::decode(decoder);
                trace!("decoded fn alloc instance: {:?}", instance);
                decoder.interner().reserve_and_set_fn_alloc(instance, CTFE_ALLOC_SALT)
            }
            AllocDiscriminant::VTable => {
                trace!("creating vtable alloc ID");
                let ty = Decodable::decode(decoder);
                let poly_trait_ref = Decodable::decode(decoder);
                trace!("decoded vtable alloc instance: {ty:?}, {poly_trait_ref:?}");
                decoder.interner().reserve_and_set_vtable_alloc(ty, poly_trait_ref, CTFE_ALLOC_SALT)
            }
            AllocDiscriminant::Static => {
                trace!("creating extern static alloc ID");
                let did = <DefId as Decodable<D>>::decode(decoder);
                trace!("decoded static def-ID: {:?}", did);
                decoder.interner().reserve_and_set_static_alloc(did)
            }
        });

        *entry = State::Done(alloc_id);

        alloc_id
    }
}

/// An allocation in the global (tcx-managed) memory can be either a function pointer,
/// a static, or a "real" allocation with some data in it.
#[derive(Debug, Clone, Eq, PartialEq, Hash, TyDecodable, TyEncodable, HashStable)]
pub enum GlobalAlloc<'tcx> {
    /// The alloc ID is used as a function pointer.
    Function { instance: Instance<'tcx> },
    /// This alloc ID points to a symbolic (not-reified) vtable.
    /// We remember the full dyn type, not just the principal trait, so that
    /// const-eval and Miri can detect UB due to invalid transmutes of
    /// `dyn Trait` types.
    VTable(Ty<'tcx>, &'tcx ty::List<ty::PolyExistentialPredicate<'tcx>>),
    /// The alloc ID points to a "lazy" static variable that did not get computed (yet).
    /// This is also used to break the cycle in recursive statics.
    Static(DefId),
    /// The alloc ID points to memory.
    Memory(ConstAllocation<'tcx>),
}

impl<'tcx> GlobalAlloc<'tcx> {
    /// Panics if the `GlobalAlloc` does not refer to an `GlobalAlloc::Memory`
    #[track_caller]
    #[inline]
    pub fn unwrap_memory(&self) -> ConstAllocation<'tcx> {
        match *self {
            GlobalAlloc::Memory(mem) => mem,
            _ => bug!("expected memory, got {:?}", self),
        }
    }

    /// Panics if the `GlobalAlloc` is not `GlobalAlloc::Function`
    #[track_caller]
    #[inline]
    pub fn unwrap_fn(&self) -> Instance<'tcx> {
        match *self {
            GlobalAlloc::Function { instance, .. } => instance,
            _ => bug!("expected function, got {:?}", self),
        }
    }

    /// Panics if the `GlobalAlloc` is not `GlobalAlloc::VTable`
    #[track_caller]
    #[inline]
    pub fn unwrap_vtable(&self) -> (Ty<'tcx>, Option<ty::PolyExistentialTraitRef<'tcx>>) {
        match *self {
            GlobalAlloc::VTable(ty, dyn_ty) => (ty, dyn_ty.principal()),
            _ => bug!("expected vtable, got {:?}", self),
        }
    }

    /// The address space that this `GlobalAlloc` should be placed in.
    #[inline]
    pub fn address_space(&self, cx: &impl HasDataLayout) -> AddressSpace {
        match self {
            GlobalAlloc::Function { .. } => cx.data_layout().instruction_address_space,
            GlobalAlloc::Static(..) | GlobalAlloc::Memory(..) | GlobalAlloc::VTable(..) => {
                AddressSpace::DATA
            }
        }
    }
}

pub const CTFE_ALLOC_SALT: usize = 0;

pub(crate) struct AllocMap<'tcx> {
    /// Maps `AllocId`s to their corresponding allocations.
    alloc_map: FxHashMap<AllocId, GlobalAlloc<'tcx>>,

    /// Used to deduplicate global allocations: functions, vtables, string literals, ...
    ///
    /// The `usize` is a "salt" used by Miri to make deduplication imperfect, thus better emulating
    /// the actual guarantees.
    dedup: FxHashMap<(GlobalAlloc<'tcx>, usize), AllocId>,

    /// The `AllocId` to assign to the next requested ID.
    /// Always incremented; never gets smaller.
    next_id: AllocId,
}

impl<'tcx> AllocMap<'tcx> {
    pub(crate) fn new() -> Self {
        AllocMap {
            alloc_map: Default::default(),
            dedup: Default::default(),
            next_id: AllocId(NonZero::new(1).unwrap()),
        }
    }
    fn reserve(&mut self) -> AllocId {
        let next = self.next_id;
        self.next_id.0 = self.next_id.0.checked_add(1).expect(
            "You overflowed a u64 by incrementing by 1... \
             You've just earned yourself a free drink if we ever meet. \
             Seriously, how did you do that?!",
        );
        next
    }
}

impl<'tcx> TyCtxt<'tcx> {
    /// Obtains a new allocation ID that can be referenced but does not
    /// yet have an allocation backing it.
    ///
    /// Make sure to call `set_alloc_id_memory` or `set_alloc_id_same_memory` before returning such
    /// an `AllocId` from a query.
    pub fn reserve_alloc_id(self) -> AllocId {
        self.alloc_map.lock().reserve()
    }

    /// Reserves a new ID *if* this allocation has not been dedup-reserved before.
    /// Should not be used for mutable memory.
    fn reserve_and_set_dedup(self, alloc: GlobalAlloc<'tcx>, salt: usize) -> AllocId {
        let mut alloc_map = self.alloc_map.lock();
        if let GlobalAlloc::Memory(mem) = alloc {
            if mem.inner().mutability.is_mut() {
                bug!("trying to dedup-reserve mutable memory");
            }
        }
        let alloc_salt = (alloc, salt);
        if let Some(&alloc_id) = alloc_map.dedup.get(&alloc_salt) {
            return alloc_id;
        }
        let id = alloc_map.reserve();
        debug!("creating alloc {:?} with id {id:?}", alloc_salt.0);
        alloc_map.alloc_map.insert(id, alloc_salt.0.clone());
        alloc_map.dedup.insert(alloc_salt, id);
        id
    }

    /// Generates an `AllocId` for a memory allocation. If the exact same memory has been
    /// allocated before, this will return the same `AllocId`.
    pub fn reserve_and_set_memory_dedup(self, mem: ConstAllocation<'tcx>, salt: usize) -> AllocId {
        self.reserve_and_set_dedup(GlobalAlloc::Memory(mem), salt)
    }

    /// Generates an `AllocId` for a static or return a cached one in case this function has been
    /// called on the same static before.
    pub fn reserve_and_set_static_alloc(self, static_id: DefId) -> AllocId {
        let salt = 0; // Statics have a guaranteed unique address, no salt added.
        self.reserve_and_set_dedup(GlobalAlloc::Static(static_id), salt)
    }

    /// Generates an `AllocId` for a function. Will get deduplicated.
    pub fn reserve_and_set_fn_alloc(self, instance: Instance<'tcx>, salt: usize) -> AllocId {
        self.reserve_and_set_dedup(GlobalAlloc::Function { instance }, salt)
    }

    /// Generates an `AllocId` for a (symbolic, not-reified) vtable. Will get deduplicated.
    pub fn reserve_and_set_vtable_alloc(
        self,
        ty: Ty<'tcx>,
        dyn_ty: &'tcx ty::List<ty::PolyExistentialPredicate<'tcx>>,
        salt: usize,
    ) -> AllocId {
        self.reserve_and_set_dedup(GlobalAlloc::VTable(ty, dyn_ty), salt)
    }

    /// Interns the `Allocation` and return a new `AllocId`, even if there's already an identical
    /// `Allocation` with a different `AllocId`.
    /// Statics with identical content will still point to the same `Allocation`, i.e.,
    /// their data will be deduplicated through `Allocation` interning -- but they
    /// are different places in memory and as such need different IDs.
    pub fn reserve_and_set_memory_alloc(self, mem: ConstAllocation<'tcx>) -> AllocId {
        let id = self.reserve_alloc_id();
        self.set_alloc_id_memory(id, mem);
        id
    }

    /// Returns `None` in case the `AllocId` is dangling. An `InterpretCx` can still have a
    /// local `Allocation` for that `AllocId`, but having such an `AllocId` in a constant is
    /// illegal and will likely ICE.
    /// This function exists to allow const eval to detect the difference between evaluation-
    /// local dangling pointers and allocations in constants/statics.
    #[inline]
    pub fn try_get_global_alloc(self, id: AllocId) -> Option<GlobalAlloc<'tcx>> {
        self.alloc_map.lock().alloc_map.get(&id).cloned()
    }

    #[inline]
    #[track_caller]
    /// Panics in case the `AllocId` is dangling. Since that is impossible for `AllocId`s in
    /// constants (as all constants must pass interning and validation that check for dangling
    /// ids), this function is frequently used throughout rustc, but should not be used within
    /// the interpreter.
    pub fn global_alloc(self, id: AllocId) -> GlobalAlloc<'tcx> {
        match self.try_get_global_alloc(id) {
            Some(alloc) => alloc,
            None => bug!("could not find allocation for {id:?}"),
        }
    }

    /// Freezes an `AllocId` created with `reserve` by pointing it at an `Allocation`. Trying to
    /// call this function twice, even with the same `Allocation` will ICE the compiler.
    pub fn set_alloc_id_memory(self, id: AllocId, mem: ConstAllocation<'tcx>) {
        if let Some(old) = self.alloc_map.lock().alloc_map.insert(id, GlobalAlloc::Memory(mem)) {
            bug!("tried to set allocation ID {id:?}, but it was already existing as {old:#?}");
        }
    }

    /// Freezes an `AllocId` created with `reserve` by pointing it at a static item. Trying to
    /// call this function twice, even with the same `DefId` will ICE the compiler.
    pub fn set_nested_alloc_id_static(self, id: AllocId, def_id: LocalDefId) {
        if let Some(old) =
            self.alloc_map.lock().alloc_map.insert(id, GlobalAlloc::Static(def_id.to_def_id()))
        {
            bug!("tried to set allocation ID {id:?}, but it was already existing as {old:#?}");
        }
    }
}

////////////////////////////////////////////////////////////////////////////////
// Methods to access integers in the target endianness
////////////////////////////////////////////////////////////////////////////////

#[inline]
pub fn write_target_uint(
    endianness: Endian,
    mut target: &mut [u8],
    data: u128,
) -> Result<(), io::Error> {
    // This u128 holds an "any-size uint" (since smaller uints can fits in it)
    // So we do not write all bytes of the u128, just the "payload".
    match endianness {
        Endian::Little => target.write(&data.to_le_bytes())?,
        Endian::Big => target.write(&data.to_be_bytes()[16 - target.len()..])?,
    };
    debug_assert!(target.len() == 0); // We should have filled the target buffer.
    Ok(())
}

#[inline]
pub fn read_target_uint(endianness: Endian, mut source: &[u8]) -> Result<u128, io::Error> {
    // This u128 holds an "any-size uint" (since smaller uints can fits in it)
    let mut buf = [0u8; std::mem::size_of::<u128>()];
    // So we do not read exactly 16 bytes into the u128, just the "payload".
    let uint = match endianness {
        Endian::Little => {
            source.read_exact(&mut buf[..source.len()])?;
            Ok(u128::from_le_bytes(buf))
        }
        Endian::Big => {
            source.read_exact(&mut buf[16 - source.len()..])?;
            Ok(u128::from_be_bytes(buf))
        }
    };
    debug_assert!(source.len() == 0); // We should have consumed the source buffer.
    uint
}