compiler/rustc_mir_dataflow/src/value_analysis.rs

   1 //! This module provides a framework on top of the normal MIR dataflow framework to simplify the
   2 //! implementation of analyses that track the values stored in places of interest.
   3 //!
   4 //! The default methods of [`ValueAnalysis`] (prefixed with `super_` instead of `handle_`)
   5 //! provide some behavior that should be valid for all abstract domains that are based only on the
   6 //! value stored in a certain place. On top of these default rules, an implementation should
   7 //! override some of the `handle_` methods. For an example, see `ConstAnalysis`.
   8 //!
   9 //! An implementation must also provide a [`Map`]. Before the anaylsis begins, all places that
  10 //! should be tracked during the analysis must be registered. Currently, the projections of these
  11 //! places may only contain derefs, fields and downcasts (otherwise registration fails). During the
  12 //! analysis, no new places can be registered.
  13 //!
  14 //! Note that if you want to track values behind references, you have to register the dereferenced
  15 //! place. For example: Assume `let x = (0, 0)` and that we want to propagate values from `x.0` and
  16 //! `x.1` also through the assignment `let y = &x`. In this case, we should register `x.0`, `x.1`,
  17 //! `(*y).0` and `(*y).1`.
  18 //!
  19 //!
  20 //! # Correctness
  21 //!
  22 //! Warning: This is a semi-formal attempt to argue for the correctness of this analysis. If you
  23 //! find any weak spots, let me know! Recommended reading: Abstract Interpretation. We will use the
  24 //! term "place" to refer to a place expression (like `mir::Place`), and we will call the
  25 //! underlying entity "object". For instance, `*_1` and `*_2` are not the same place, but depending
  26 //! on the value of `_1` and `_2`, they could refer to the same object. Also, the same place can
  27 //! refer to different objects during execution. If `_1` is reassigned, then `*_1` may refer to
  28 //! different objects before and after assignment. Additionally, when saying "access to a place",
  29 //! what we really mean is "access to an object denoted by arbitrary projections of that place".
  30 //!
  31 //! In the following, we will assume a constant propagation analysis. Our analysis is correct if
  32 //! every transfer function is correct. This is the case if for every pair (f, f#) and abstract
  33 //! state s, we have f(y(s)) <= y(f#(s)), where s is a mapping from tracked place to top, bottom or
  34 //! a constant. Since pointers (and mutable references) are not tracked, but can be used to change
  35 //! values in the concrete domain, f# must assume that all places that can be affected in this way
  36 //! for a given program point are already marked with top in s (otherwise many assignments and
  37 //! function calls would have no choice but to mark all tracked places with top). This leads us to
  38 //! an invariant: For all possible program points where there could possibly exist means of mutable
  39 //! access to a tracked place (in the concrete domain), this place must be assigned to top (in the
  40 //! abstract domain). The concretization function y can be defined as expected for the constant
  41 //! propagation analysis, although the concrete state of course contains all kinds of non-tracked
  42 //! data. However, by the invariant above, no mutable access to tracked places that are not marked
  43 //! with top may be introduced.
  44 //!
  45 //! Note that we (at least currently) do not differentiate between "this place may assume different
  46 //! values" and "a pointer to this place escaped the analysis". However, we still want to handle
  47 //! assignments to constants as usual for f#. This adds an assumption: Whenever we have an
  48 //! assignment that is captured by the analysis, all mutable access to the underlying place (which
  49 //! is not observable by the analysis) must be invalidated. This is (hopefully) covered by Stacked
  50 //! Borrows.
  51 //!
  52 //! To be continued...
  53
  54 use std::fmt::{Debug, Formatter};
  55
  56 use rustc_data_structures::fx::FxHashMap;
  57 use rustc_index::vec::IndexVec;
  58 use rustc_middle::mir::*;
  59 use rustc_middle::ty::{self, Ty, TyCtxt};
  60 use rustc_target::abi::VariantIdx;
  61
  62 use crate::{
  63     fmt::DebugWithContext, lattice::FlatSet, Analysis, AnalysisDomain, CallReturnPlaces,
  64     JoinSemiLattice, SwitchIntEdgeEffects,
  65 };
  66
  67 pub trait ValueAnalysis<'tcx> {
  68     /// For each place of interest, the analysis tracks a value of the given type.
  69     type Value: Clone + JoinSemiLattice + HasBottom + HasTop;
  70
  71     const NAME: &'static str;
  72
  73     fn map(&self) -> &Map;
  74
  75     fn handle_statement(&self, statement: &Statement<'tcx>, state: &mut State<Self::Value>) {
  76         self.super_statement(statement, state)
  77     }
  78
  79     fn super_statement(&self, statement: &Statement<'tcx>, state: &mut State<Self::Value>) {
  80         match &statement.kind {
  81             StatementKind::Assign(box (place, rvalue)) => {
  82                 self.handle_assign(*place, rvalue, state);
  83             }
  84             StatementKind::SetDiscriminant { .. } => {
  85                 // Could treat this as writing a constant to a pseudo-place.
  86             }
  87             StatementKind::CopyNonOverlapping(..) => {
  88                 // FIXME: What to do here?
  89             }
  90             StatementKind::StorageLive(..)
  91             | StatementKind::StorageDead(..)
  92             | StatementKind::Deinit(_) => {
  93                 // Could perhaps use these.
  94             }
  95             StatementKind::Nop
  96             | StatementKind::Retag(..)
  97             | StatementKind::FakeRead(..)
  98             | StatementKind::Coverage(..)
  99             | StatementKind::AscribeUserType(..) => (),
 100         }
 101     }
 102
 103     fn handle_assign(
 104         &self,
 105         target: Place<'tcx>,
 106         rvalue: &Rvalue<'tcx>,
 107         state: &mut State<Self::Value>,
 108     ) {
 109         self.super_assign(target, rvalue, state)
 110     }
 111
 112     fn super_assign(
 113         &self,
 114         target: Place<'tcx>,
 115         rvalue: &Rvalue<'tcx>,
 116         state: &mut State<Self::Value>,
 117     ) {
 118         let result = self.handle_rvalue(rvalue, state);
 119         state.assign(target.as_ref(), result, self.map());
 120     }
 121
 122     fn handle_rvalue(
 123         &self,
 124         rvalue: &Rvalue<'tcx>,
 125         state: &mut State<Self::Value>,
 126     ) -> ValueOrPlaceOrRef<Self::Value> {
 127         self.super_rvalue(rvalue, state)
 128     }
 129
 130     fn super_rvalue(
 131         &self,
 132         rvalue: &Rvalue<'tcx>,
 133         state: &mut State<Self::Value>,
 134     ) -> ValueOrPlaceOrRef<Self::Value> {
 135         match rvalue {
 136             Rvalue::Use(operand) => self.handle_operand(operand, state).into(),
 137             Rvalue::Ref(_, BorrowKind::Shared, place) => self
 138                 .map()
 139                 .find(place.as_ref())
 140                 .map(ValueOrPlaceOrRef::Ref)
 141                 .unwrap_or(ValueOrPlaceOrRef::Unknown),
 142             Rvalue::Ref(_, _, place) | Rvalue::AddressOf(_, place) => {
 143                 state.flood(place.as_ref(), self.map());
 144                 ValueOrPlaceOrRef::Unknown
 145             }
 146             Rvalue::CopyForDeref(place) => {
 147                 self.handle_operand(&Operand::Copy(*place), state).into()
 148             }
 149             _ => {
 150                 // FIXME: Check that other Rvalues really have no side-effect.
 151                 ValueOrPlaceOrRef::Unknown
 152             }
 153         }
 154     }
 155
 156     fn handle_operand(
 157         &self,
 158         operand: &Operand<'tcx>,
 159         state: &mut State<Self::Value>,
 160     ) -> ValueOrPlace<Self::Value> {
 161         self.super_operand(operand, state)
 162     }
 163
 164     fn super_operand(
 165         &self,
 166         operand: &Operand<'tcx>,
 167         state: &mut State<Self::Value>,
 168     ) -> ValueOrPlace<Self::Value> {
 169         match operand {
 170             Operand::Constant(box constant) => {
 171                 ValueOrPlace::Value(self.handle_constant(constant, state))
 172             }
 173             Operand::Copy(place) | Operand::Move(place) => {
 174                 // Do want want to handle moves different? Could flood place with bottom.
 175                 self.map()
 176                     .find(place.as_ref())
 177                     .map(ValueOrPlace::Place)
 178                     .unwrap_or(ValueOrPlace::Unknown)
 179             }
 180         }
 181     }
 182
 183     fn handle_constant(
 184         &self,
 185         constant: &Constant<'tcx>,
 186         state: &mut State<Self::Value>,
 187     ) -> Self::Value {
 188         self.super_constant(constant, state)
 189     }
 190
 191     fn super_constant(
 192         &self,
 193         _constant: &Constant<'tcx>,
 194         _state: &mut State<Self::Value>,
 195     ) -> Self::Value {
 196         Self::Value::top()
 197     }
 198
 199     fn handle_terminator(&self, terminator: &Terminator<'tcx>, state: &mut State<Self::Value>) {
 200         self.super_terminator(terminator, state)
 201     }
 202
 203     fn super_terminator(&self, _terminator: &Terminator<'tcx>, _state: &mut State<Self::Value>) {}
 204
 205     fn handle_call_return(
 206         &self,
 207         return_places: CallReturnPlaces<'_, 'tcx>,
 208         state: &mut State<Self::Value>,
 209     ) {
 210         self.super_call_return(return_places, state)
 211     }
 212
 213     fn super_call_return(
 214         &self,
 215         return_places: CallReturnPlaces<'_, 'tcx>,
 216         state: &mut State<Self::Value>,
 217     ) {
 218         return_places.for_each(|place| {
 219             state.flood(place.as_ref(), self.map());
 220         })
 221     }
 222
 223     fn handle_switch_int(
 224         &self,
 225         discr: &Operand<'tcx>,
 226         apply_edge_effects: &mut impl SwitchIntEdgeEffects<State<Self::Value>>,
 227     ) {
 228         self.super_switch_int(discr, apply_edge_effects)
 229     }
 230
 231     fn super_switch_int(
 232         &self,
 233         _discr: &Operand<'tcx>,
 234         _apply_edge_effects: &mut impl SwitchIntEdgeEffects<State<Self::Value>>,
 235     ) {
 236     }
 237
 238     fn wrap(self) -> ValueAnalysisWrapper<Self>
 239     where
 240         Self: Sized,
 241     {
 242         ValueAnalysisWrapper(self)
 243     }
 244 }
 245
 246 pub struct ValueAnalysisWrapper<T>(pub T);
 247
 248 impl<'tcx, T: ValueAnalysis<'tcx>> AnalysisDomain<'tcx> for ValueAnalysisWrapper<T> {
 249     type Domain = State<T::Value>;
 250
 251     type Direction = crate::Forward;
 252
 253     const NAME: &'static str = T::NAME;
 254
 255     fn bottom_value(&self, _body: &Body<'tcx>) -> Self::Domain {
 256         State(IndexVec::from_elem_n(T::Value::bottom(), self.0.map().value_count))
 257     }
 258
 259     fn initialize_start_block(&self, body: &Body<'tcx>, state: &mut Self::Domain) {
 260         for arg in body.args_iter() {
 261             state.flood(PlaceRef { local: arg, projection: &[] }, self.0.map());
 262         }
 263     }
 264 }
 265
 266 impl<'tcx, T> Analysis<'tcx> for ValueAnalysisWrapper<T>
 267 where
 268     T: ValueAnalysis<'tcx>,
 269 {
 270     fn apply_statement_effect(
 271         &self,
 272         state: &mut Self::Domain,
 273         statement: &Statement<'tcx>,
 274         _location: Location,
 275     ) {
 276         self.0.handle_statement(statement, state);
 277     }
 278
 279     fn apply_terminator_effect(
 280         &self,
 281         state: &mut Self::Domain,
 282         terminator: &Terminator<'tcx>,
 283         _location: Location,
 284     ) {
 285         self.0.handle_terminator(terminator, state);
 286     }
 287
 288     fn apply_call_return_effect(
 289         &self,
 290         state: &mut Self::Domain,
 291         _block: BasicBlock,
 292         return_places: crate::CallReturnPlaces<'_, 'tcx>,
 293     ) {
 294         self.0.handle_call_return(return_places, state)
 295     }
 296
 297     fn apply_switch_int_edge_effects(
 298         &self,
 299         _block: BasicBlock,
 300         discr: &Operand<'tcx>,
 301         apply_edge_effects: &mut impl SwitchIntEdgeEffects<Self::Domain>,
 302     ) {
 303         self.0.handle_switch_int(discr, apply_edge_effects)
 304     }
 305 }
 306
 307 rustc_index::newtype_index!(
 308     pub struct PlaceIndex {}
 309 );
 310
 311 rustc_index::newtype_index!(
 312     struct ValueIndex {}
 313 );
 314
 315 #[derive(PartialEq, Eq, Clone, Debug)]
 316 pub struct State<V>(IndexVec<ValueIndex, V>);
 317
 318 impl<V: Clone + HasTop> State<V> {
 319     pub fn flood_all(&mut self) {
 320         self.flood_all_with(V::top())
 321     }
 322
 323     pub fn flood_all_with(&mut self, value: V) {
 324         self.0.raw.fill(value);
 325     }
 326
 327     pub fn flood_with(&mut self, place: PlaceRef<'_>, map: &Map, value: V) {
 328         if let Some(root) = map.find(place) {
 329             self.flood_idx_with(root, map, value);
 330         }
 331     }
 332
 333     pub fn flood(&mut self, place: PlaceRef<'_>, map: &Map) {
 334         self.flood_with(place, map, V::top())
 335     }
 336
 337     pub fn flood_idx_with(&mut self, place: PlaceIndex, map: &Map, value: V) {
 338         map.preorder_invoke(place, &mut |place| {
 339             if let Some(vi) = map.places[place].value_index {
 340                 self.0[vi] = value.clone();
 341             }
 342         });
 343     }
 344
 345     pub fn flood_idx(&mut self, place: PlaceIndex, map: &Map) {
 346         self.flood_idx_with(place, map, V::top())
 347     }
 348
 349     pub fn assign_place_idx(&mut self, target: PlaceIndex, source: PlaceIndex, map: &Map) {
 350         if let Some(target_value) = map.places[target].value_index {
 351             if let Some(source_value) = map.places[source].value_index {
 352                 self.0[target_value] = self.0[source_value].clone();
 353             } else {
 354                 self.0[target_value] = V::top();
 355             }
 356         }
 357         for target_child in map.children(target) {
 358             // Try to find corresponding child in source.
 359             let projection = map.places[target_child].proj_elem.unwrap();
 360             if let Some(source_child) = map.projections.get(&(source, projection)) {
 361                 self.assign_place_idx(target_child, *source_child, map);
 362             } else {
 363                 self.flood_idx(target_child, map);
 364             }
 365         }
 366     }
 367
 368     pub fn assign(&mut self, target: PlaceRef<'_>, result: ValueOrPlaceOrRef<V>, map: &Map) {
 369         if let Some(target) = map.find(target) {
 370             self.assign_idx(target, result, map);
 371         } else {
 372             // We don't track this place nor any projections, assignment can be ignored.
 373         }
 374     }
 375
 376     pub fn assign_idx(&mut self, target: PlaceIndex, result: ValueOrPlaceOrRef<V>, map: &Map) {
 377         match result {
 378             ValueOrPlaceOrRef::Value(value) => {
 379                 // First flood the target place in case we also track any projections (although
 380                 // this scenario is currently not well-supported by the API).
 381                 self.flood_idx(target, map);
 382                 if let Some(value_index) = map.places[target].value_index {
 383                     self.0[value_index] = value;
 384                 }
 385             }
 386             ValueOrPlaceOrRef::Place(source) => self.assign_place_idx(target, source, map),
 387             ValueOrPlaceOrRef::Ref(source) => {
 388                 if let Some(value_index) = map.places[target].value_index {
 389                     self.0[value_index] = V::top();
 390                 }
 391                 if let Some(target_deref) = map.apply_elem(target, ProjElem::Deref) {
 392                     self.assign_place_idx(target_deref, source, map);
 393                 }
 394             }
 395             ValueOrPlaceOrRef::Unknown => {
 396                 self.flood_idx(target, map);
 397             }
 398         }
 399     }
 400
 401     pub fn get(&self, place: PlaceRef<'_>, map: &Map) -> V {
 402         map.find(place).map(|place| self.get_idx(place, map)).unwrap_or(V::top())
 403     }
 404
 405     pub fn get_idx(&self, place: PlaceIndex, map: &Map) -> V {
 406         map.places[place].value_index.map(|v| self.0[v].clone()).unwrap_or(V::top())
 407     }
 408 }
 409
 410 impl<V: JoinSemiLattice> JoinSemiLattice for State<V> {
 411     fn join(&mut self, other: &Self) -> bool {
 412         self.0.join(&other.0)
 413     }
 414 }
 415
 416 #[derive(Debug)]
 417 pub struct Map {
 418     locals: IndexVec<Local, Option<PlaceIndex>>,
 419     projections: FxHashMap<(PlaceIndex, ProjElem), PlaceIndex>,
 420     places: IndexVec<PlaceIndex, PlaceInfo>,
 421     value_count: usize,
 422 }
 423
 424 impl Map {
 425     pub fn new() -> Self {
 426         Self {
 427             locals: IndexVec::new(),
 428             projections: FxHashMap::default(),
 429             places: IndexVec::new(),
 430             value_count: 0,
 431         }
 432     }
 433
 434     /// Register all places with suitable types up to a certain derefence depth (to prevent cycles).
 435     pub fn register_with_filter<'tcx>(
 436         &mut self,
 437         tcx: TyCtxt<'tcx>,
 438         source: &impl HasLocalDecls<'tcx>,
 439         max_derefs: u32,
 440         mut filter: impl FnMut(Ty<'tcx>) -> bool,
 441     ) {
 442         let mut projection = Vec::new();
 443         for (local, decl) in source.local_decls().iter_enumerated() {
 444             self.register_with_filter_rec(
 445                 tcx,
 446                 max_derefs,
 447                 local,
 448                 &mut projection,
 449                 decl.ty,
 450                 &mut filter,
 451             );
 452         }
 453     }
 454
 455     fn register_with_filter_rec<'tcx>(
 456         &mut self,
 457         tcx: TyCtxt<'tcx>,
 458         max_derefs: u32,
 459         local: Local,
 460         projection: &mut Vec<PlaceElem<'tcx>>,
 461         ty: Ty<'tcx>,
 462         filter: &mut impl FnMut(Ty<'tcx>) -> bool,
 463     ) {
 464         if filter(ty) {
 465             // Since downcasts are currently not allowed, this might fail.
 466             let _ = self.register(local, projection);
 467         }
 468         if max_derefs > 0 {
 469             if let Some(ty::TypeAndMut { ty, .. }) = ty.builtin_deref(false) {
 470                 projection.push(PlaceElem::Deref);
 471                 self.register_with_filter_rec(tcx, max_derefs - 1, local, projection, ty, filter);
 472                 projection.pop();
 473             }
 474         }
 475         iter_fields(ty, tcx, |variant, field, ty| {
 476             if let Some(variant) = variant {
 477                 projection.push(PlaceElem::Downcast(None, variant));
 478             }
 479             projection.push(PlaceElem::Field(field, ty));
 480             self.register_with_filter_rec(tcx, max_derefs, local, projection, ty, filter);
 481             projection.pop();
 482             if variant.is_some() {
 483                 projection.pop();
 484             }
 485         });
 486     }
 487
 488     pub fn register<'tcx>(
 489         &mut self,
 490         local: Local,
 491         projection: &[PlaceElem<'tcx>],
 492     ) -> Result<(), ()> {
 493         // Get the base index of the local.
 494         let mut index =
 495             *self.locals.get_or_insert_with(local, || self.places.push(PlaceInfo::new(None)));
 496
 497         // Apply the projection.
 498         for &elem in projection {
 499             // For now, downcast is not allowed (see #101168).
 500             match elem {
 501                 PlaceElem::Downcast(..) => return Err(()),
 502                 _ => (),
 503             }
 504             let elem = elem.try_into()?;
 505             index = *self.projections.entry((index, elem)).or_insert_with(|| {
 506                 // Prepend new child to the linked list.
 507                 let next = self.places.push(PlaceInfo::new(Some(elem)));
 508                 self.places[next].next_sibling = self.places[index].first_child;
 509                 self.places[index].first_child = Some(next);
 510                 next
 511             });
 512         }
 513
 514         // Allocate a value slot if it doesn't have one.
 515         if self.places[index].value_index.is_none() {
 516             self.places[index].value_index = Some(self.value_count.into());
 517             self.value_count += 1;
 518         }
 519
 520         Ok(())
 521     }
 522
 523     pub fn apply_elem(&self, place: PlaceIndex, elem: ProjElem) -> Option<PlaceIndex> {
 524         self.projections.get(&(place, elem)).copied()
 525     }
 526
 527     pub fn find(&self, place: PlaceRef<'_>) -> Option<PlaceIndex> {
 528         let mut index = *self.locals.get(place.local)?.as_ref()?;
 529
 530         for &elem in place.projection {
 531             index = self.apply_elem(index, elem.try_into().ok()?)?;
 532         }
 533
 534         Some(index)
 535     }
 536
 537     pub fn children(&self, parent: PlaceIndex) -> impl Iterator<Item = PlaceIndex> + '_ {
 538         Children::new(self, parent)
 539     }
 540
 541     pub fn preorder_invoke(&self, root: PlaceIndex, f: &mut impl FnMut(PlaceIndex)) {
 542         f(root);
 543         for child in self.children(root) {
 544             self.preorder_invoke(child, f);
 545         }
 546     }
 547 }
 548
 549 #[derive(Debug)]
 550 struct PlaceInfo {
 551     next_sibling: Option<PlaceIndex>,
 552     first_child: Option<PlaceIndex>,
 553     /// The projection used to go from parent to this node (only None for root).
 554     proj_elem: Option<ProjElem>,
 555     value_index: Option<ValueIndex>,
 556 }
 557
 558 impl PlaceInfo {
 559     fn new(proj_elem: Option<ProjElem>) -> Self {
 560         Self { next_sibling: None, first_child: None, proj_elem, value_index: None }
 561     }
 562 }
 563
 564 struct Children<'a> {
 565     map: &'a Map,
 566     next: Option<PlaceIndex>,
 567 }
 568
 569 impl<'a> Children<'a> {
 570     fn new(map: &'a Map, parent: PlaceIndex) -> Self {
 571         Self { map, next: map.places[parent].first_child }
 572     }
 573 }
 574
 575 impl<'a> Iterator for Children<'a> {
 576     type Item = PlaceIndex;
 577
 578     fn next(&mut self) -> Option<Self::Item> {
 579         match self.next {
 580             Some(child) => {
 581                 self.next = self.map.places[child].next_sibling;
 582                 Some(child)
 583             }
 584             None => None,
 585         }
 586     }
 587 }
 588
 589 // FIXME: See if we can get rid of `Unknown`.
 590 pub enum ValueOrPlace<V> {
 591     Value(V),
 592     Place(PlaceIndex),
 593     Unknown,
 594 }
 595
 596 pub enum ValueOrPlaceOrRef<V> {
 597     Value(V),
 598     Place(PlaceIndex),
 599     Ref(PlaceIndex),
 600     Unknown,
 601 }
 602
 603 impl<V> From<ValueOrPlace<V>> for ValueOrPlaceOrRef<V> {
 604     fn from(x: ValueOrPlace<V>) -> Self {
 605         match x {
 606             ValueOrPlace::Value(value) => ValueOrPlaceOrRef::Value(value),
 607             ValueOrPlace::Place(place) => ValueOrPlaceOrRef::Place(place),
 608             ValueOrPlace::Unknown => ValueOrPlaceOrRef::Unknown,
 609         }
 610     }
 611 }
 612
 613 pub trait HasBottom {
 614     fn bottom() -> Self;
 615 }
 616
 617 pub trait HasTop {
 618     fn top() -> Self;
 619 }
 620
 621 impl<V> HasBottom for FlatSet<V> {
 622     fn bottom() -> Self {
 623         Self::Bottom
 624     }
 625 }
 626
 627 impl<V> HasTop for FlatSet<V> {
 628     fn top() -> Self {
 629         Self::Top
 630     }
 631 }
 632
 633 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
 634 pub enum ProjElem {
 635     Deref,
 636     Field(Field),
 637     Downcast(VariantIdx),
 638 }
 639
 640 impl<V, T> TryFrom<ProjectionElem<V, T>> for ProjElem {
 641     type Error = ();
 642
 643     fn try_from(value: ProjectionElem<V, T>) -> Result<Self, Self::Error> {
 644         match value {
 645             ProjectionElem::Deref => Ok(ProjElem::Deref),
 646             ProjectionElem::Field(field, _) => Ok(ProjElem::Field(field)),
 647             ProjectionElem::Downcast(_, variant) => Ok(ProjElem::Downcast(variant)),
 648             _ => Err(()),
 649         }
 650     }
 651 }
 652
 653 fn iter_fields<'tcx>(
 654     ty: Ty<'tcx>,
 655     tcx: TyCtxt<'tcx>,
 656     mut f: impl FnMut(Option<VariantIdx>, Field, Ty<'tcx>),
 657 ) {
 658     match ty.kind() {
 659         ty::Tuple(list) => {
 660             for (field, ty) in list.iter().enumerate() {
 661                 f(None, field.into(), ty);
 662             }
 663         }
 664         ty::Adt(def, substs) => {
 665             for (v_index, v_def) in def.variants().iter_enumerated() {
 666                 for (f_index, f_def) in v_def.fields.iter().enumerate() {
 667                     let field_ty = f_def.ty(tcx, substs);
 668                     let field_ty = tcx
 669                         .try_normalize_erasing_regions(ty::ParamEnv::reveal_all(), field_ty)
 670                         .unwrap_or(field_ty);
 671                     f(Some(v_index), f_index.into(), field_ty);
 672                 }
 673             }
 674         }
 675         ty::Closure(_, substs) => {
 676             iter_fields(substs.as_closure().tupled_upvars_ty(), tcx, f);
 677         }
 678         _ => (),
 679     }
 680 }
 681
 682 fn debug_with_context_rec<V: Debug + Eq>(
 683     place: PlaceIndex,
 684     place_str: &str,
 685     new: &State<V>,
 686     old: Option<&State<V>>,
 687     map: &Map,
 688     f: &mut Formatter<'_>,
 689 ) -> std::fmt::Result {
 690     if let Some(value) = map.places[place].value_index {
 691         match old {
 692             None => writeln!(f, "{}: {:?}", place_str, new.0[value])?,
 693             Some(old) => {
 694                 if new.0[value] != old.0[value] {
 695                     writeln!(f, "\u{001f}-{}: {:?}", place_str, old.0[value])?;
 696                     writeln!(f, "\u{001f}+{}: {:?}", place_str, new.0[value])?;
 697                 }
 698             }
 699         }
 700     }
 701
 702     for child in map.children(place) {
 703         let info_elem = map.places[child].proj_elem.unwrap();
 704         let child_place_str = match info_elem {
 705             ProjElem::Deref => format!("*{}", place_str),
 706             ProjElem::Field(field) => {
 707                 if place_str.starts_with("*") {
 708                     format!("({}).{}", place_str, field.index())
 709                 } else {
 710                     format!("{}.{}", place_str, field.index())
 711                 }
 712             }
 713             ProjElem::Downcast(variant) => format!("({} as #{})", place_str, variant.index()),
 714         };
 715         debug_with_context_rec(child, &child_place_str, new, old, map, f)?;
 716     }
 717
 718     Ok(())
 719 }
 720
 721 fn debug_with_context<V: Debug + Eq>(
 722     new: &State<V>,
 723     old: Option<&State<V>>,
 724     map: &Map,
 725     f: &mut Formatter<'_>,
 726 ) -> std::fmt::Result {
 727     for (local, place) in map.locals.iter_enumerated() {
 728         if let Some(place) = place {
 729             debug_with_context_rec(*place, &format!("{:?}", local), new, old, map, f)?;
 730         }
 731     }
 732     Ok(())
 733 }
 734
 735 impl<'tcx, T> DebugWithContext<ValueAnalysisWrapper<T>> for State<T::Value>
 736 where
 737     T: ValueAnalysis<'tcx>,
 738     T::Value: Debug,
 739 {
 740     fn fmt_with(&self, ctxt: &ValueAnalysisWrapper<T>, f: &mut Formatter<'_>) -> std::fmt::Result {
 741         debug_with_context(self, None, ctxt.0.map(), f)
 742     }
 743
 744     fn fmt_diff_with(
 745         &self,
 746         old: &Self,
 747         ctxt: &ValueAnalysisWrapper<T>,
 748         f: &mut Formatter<'_>,
 749     ) -> std::fmt::Result {
 750         debug_with_context(self, Some(old), ctxt.0.map(), f)
 751     }
 752 }