1use std::fmt::{Debug, Formatter};
2use std::ops::Range;
3
4use rustc_abi::{FieldIdx, VariantIdx};
5use rustc_data_structures::fx::{FxHashMap, FxIndexSet, StdEntry};
6use rustc_data_structures::stack::ensure_sufficient_stack;
7use rustc_index::IndexVec;
8use rustc_index::bit_set::DenseBitSet;
9use rustc_middle::mir::visit::{MutatingUseContext, PlaceContext, Visitor};
10use rustc_middle::mir::*;
11use rustc_middle::ty::{self, Ty, TyCtxt};
12use tracing::debug;
13
14use crate::JoinSemiLattice;
15use crate::lattice::{HasBottom, HasTop};
16
17rustc_index::newtype_index!(
18 pub struct PlaceIndex {}
23);
24
25rustc_index::newtype_index!(
26 struct ValueIndex {}
30);
31
32#[derive(PartialEq, Eq, Debug)]
34pub struct StateData<V> {
35 bottom: V,
36 map: FxHashMap<ValueIndex, V>,
38}
39
40impl<V: HasBottom> StateData<V> {
41 fn new() -> StateData<V> {
42 StateData { bottom: V::BOTTOM, map: FxHashMap::default() }
43 }
44
45 fn get(&self, idx: ValueIndex) -> &V {
46 self.map.get(&idx).unwrap_or(&self.bottom)
47 }
48
49 fn insert(&mut self, idx: ValueIndex, elem: V) {
50 if elem.is_bottom() {
51 self.map.remove(&idx);
52 } else {
53 self.map.insert(idx, elem);
54 }
55 }
56}
57
58impl<V: Clone> Clone for StateData<V> {
59 fn clone(&self) -> Self {
60 StateData { bottom: self.bottom.clone(), map: self.map.clone() }
61 }
62
63 fn clone_from(&mut self, source: &Self) {
64 self.map.clone_from(&source.map)
65 }
66}
67
68impl<V: JoinSemiLattice + Clone> JoinSemiLattice for StateData<V> {
69 fn join(&mut self, other: &Self) -> bool {
70 let mut changed = false;
71 #[allow(rustc::potential_query_instability)]
72 for (i, v) in other.map.iter() {
73 match self.map.entry(*i) {
74 StdEntry::Vacant(e) => {
75 e.insert(v.clone());
76 changed = true
77 }
78 StdEntry::Occupied(e) => changed |= e.into_mut().join(v),
79 }
80 }
81 changed
82 }
83}
84
85#[derive(PartialEq, Eq, Debug)]
96pub enum State<V> {
97 Unreachable,
98 Reachable(StateData<V>),
99}
100
101impl<V: Clone> Clone for State<V> {
102 fn clone(&self) -> Self {
103 match self {
104 Self::Reachable(x) => Self::Reachable(x.clone()),
105 Self::Unreachable => Self::Unreachable,
106 }
107 }
108
109 fn clone_from(&mut self, source: &Self) {
110 match (&mut *self, source) {
111 (Self::Reachable(x), Self::Reachable(y)) => {
112 x.clone_from(&y);
113 }
114 _ => *self = source.clone(),
115 }
116 }
117}
118
119impl<V: Clone + HasBottom> State<V> {
120 pub fn new_reachable() -> State<V> {
121 State::Reachable(StateData::new())
122 }
123
124 pub fn all_bottom(&self) -> bool {
125 match self {
126 State::Unreachable => false,
127 State::Reachable(values) =>
128 {
129 #[allow(rustc::potential_query_instability)]
130 values.map.values().all(V::is_bottom)
131 }
132 }
133 }
134
135 pub fn is_reachable(&self) -> bool {
136 matches!(self, State::Reachable(_))
137 }
138
139 pub fn flood_with(&mut self, place: PlaceRef<'_>, map: &Map<'_>, value: V) {
141 self.flood_with_tail_elem(place, None, map, value)
142 }
143
144 pub fn flood(&mut self, place: PlaceRef<'_>, map: &Map<'_>)
146 where
147 V: HasTop,
148 {
149 self.flood_with(place, map, V::TOP)
150 }
151
152 fn flood_discr_with(&mut self, place: PlaceRef<'_>, map: &Map<'_>, value: V) {
154 self.flood_with_tail_elem(place, Some(TrackElem::Discriminant), map, value)
155 }
156
157 pub fn flood_discr(&mut self, place: PlaceRef<'_>, map: &Map<'_>)
159 where
160 V: HasTop,
161 {
162 self.flood_discr_with(place, map, V::TOP)
163 }
164
165 pub fn flood_with_tail_elem(
173 &mut self,
174 place: PlaceRef<'_>,
175 tail_elem: Option<TrackElem>,
176 map: &Map<'_>,
177 value: V,
178 ) {
179 let State::Reachable(values) = self else { return };
180 map.for_each_aliasing_place(place, tail_elem, &mut |vi| values.insert(vi, value.clone()));
181 }
182
183 fn insert_idx(&mut self, target: PlaceIndex, result: ValueOrPlace<V>, map: &Map<'_>) {
188 match result {
189 ValueOrPlace::Value(value) => self.insert_value_idx(target, value, map),
190 ValueOrPlace::Place(source) => self.insert_place_idx(target, source, map),
191 }
192 }
193
194 pub fn insert_value_idx(&mut self, target: PlaceIndex, value: V, map: &Map<'_>) {
199 let State::Reachable(values) = self else { return };
200 if let Some(value_index) = map.places[target].value_index {
201 values.insert(value_index, value)
202 }
203 }
204
205 pub fn insert_place_idx(&mut self, target: PlaceIndex, source: PlaceIndex, map: &Map<'_>) {
213 let State::Reachable(values) = self else { return };
214
215 if let Some(target_value) = map.places[target].value_index {
219 if let Some(source_value) = map.places[source].value_index {
220 values.insert(target_value, values.get(source_value).clone());
221 }
222 }
223 for target_child in map.children(target) {
224 let projection = map.places[target_child].proj_elem.unwrap();
226 if let Some(source_child) = map.projections.get(&(source, projection)) {
227 self.insert_place_idx(target_child, *source_child, map);
228 }
229 }
230 }
231
232 pub fn assign(&mut self, target: PlaceRef<'_>, result: ValueOrPlace<V>, map: &Map<'_>)
234 where
235 V: HasTop,
236 {
237 self.flood(target, map);
238 if let Some(target) = map.find(target) {
239 self.insert_idx(target, result, map);
240 }
241 }
242
243 pub fn assign_discr(&mut self, target: PlaceRef<'_>, result: ValueOrPlace<V>, map: &Map<'_>)
245 where
246 V: HasTop,
247 {
248 self.flood_discr(target, map);
249 if let Some(target) = map.find_discr(target) {
250 self.insert_idx(target, result, map);
251 }
252 }
253
254 pub fn try_get(&self, place: PlaceRef<'_>, map: &Map<'_>) -> Option<V> {
256 let place = map.find(place)?;
257 self.try_get_idx(place, map)
258 }
259
260 pub fn try_get_discr(&self, place: PlaceRef<'_>, map: &Map<'_>) -> Option<V> {
262 let place = map.find_discr(place)?;
263 self.try_get_idx(place, map)
264 }
265
266 pub fn try_get_len(&self, place: PlaceRef<'_>, map: &Map<'_>) -> Option<V> {
268 let place = map.find_len(place)?;
269 self.try_get_idx(place, map)
270 }
271
272 pub fn try_get_idx(&self, place: PlaceIndex, map: &Map<'_>) -> Option<V> {
274 match self {
275 State::Reachable(values) => {
276 map.places[place].value_index.map(|v| values.get(v).clone())
277 }
278 State::Unreachable => None,
279 }
280 }
281
282 pub fn get(&self, place: PlaceRef<'_>, map: &Map<'_>) -> V
286 where
287 V: HasBottom + HasTop,
288 {
289 match self {
290 State::Reachable(_) => self.try_get(place, map).unwrap_or(V::TOP),
291 State::Unreachable => V::BOTTOM,
293 }
294 }
295
296 pub fn get_discr(&self, place: PlaceRef<'_>, map: &Map<'_>) -> V
300 where
301 V: HasBottom + HasTop,
302 {
303 match self {
304 State::Reachable(_) => self.try_get_discr(place, map).unwrap_or(V::TOP),
305 State::Unreachable => V::BOTTOM,
307 }
308 }
309
310 pub fn get_len(&self, place: PlaceRef<'_>, map: &Map<'_>) -> V
314 where
315 V: HasBottom + HasTop,
316 {
317 match self {
318 State::Reachable(_) => self.try_get_len(place, map).unwrap_or(V::TOP),
319 State::Unreachable => V::BOTTOM,
321 }
322 }
323
324 pub fn get_idx(&self, place: PlaceIndex, map: &Map<'_>) -> V
328 where
329 V: HasBottom + HasTop,
330 {
331 match self {
332 State::Reachable(values) => {
333 map.places[place].value_index.map(|v| values.get(v).clone()).unwrap_or(V::TOP)
334 }
335 State::Unreachable => {
336 V::BOTTOM
338 }
339 }
340 }
341}
342
343impl<V: JoinSemiLattice + Clone> JoinSemiLattice for State<V> {
344 fn join(&mut self, other: &Self) -> bool {
345 match (&mut *self, other) {
346 (_, State::Unreachable) => false,
347 (State::Unreachable, _) => {
348 *self = other.clone();
349 true
350 }
351 (State::Reachable(this), State::Reachable(other)) => this.join(other),
352 }
353 }
354}
355
356#[derive(Debug)]
363pub struct Map<'tcx> {
364 locals: IndexVec<Local, Option<PlaceIndex>>,
365 projections: FxHashMap<(PlaceIndex, TrackElem), PlaceIndex>,
366 places: IndexVec<PlaceIndex, PlaceInfo<'tcx>>,
367 value_count: usize,
368 inner_values: IndexVec<PlaceIndex, Range<usize>>,
370 inner_values_buffer: Vec<ValueIndex>,
371}
372
373impl<'tcx> Map<'tcx> {
374 pub fn new(tcx: TyCtxt<'tcx>, body: &Body<'tcx>, value_limit: Option<usize>) -> Self {
380 let mut map = Self {
381 locals: IndexVec::from_elem(None, &body.local_decls),
382 projections: FxHashMap::default(),
383 places: IndexVec::new(),
384 value_count: 0,
385 inner_values: IndexVec::new(),
386 inner_values_buffer: Vec::new(),
387 };
388 let exclude = excluded_locals(body);
389 map.register(tcx, body, exclude, value_limit);
390 debug!("registered {} places ({} nodes in total)", map.value_count, map.places.len());
391 map
392 }
393
394 #[tracing::instrument(level = "trace", skip(self, tcx, body))]
396 fn register(
397 &mut self,
398 tcx: TyCtxt<'tcx>,
399 body: &Body<'tcx>,
400 exclude: DenseBitSet<Local>,
401 value_limit: Option<usize>,
402 ) {
403 for (local, decl) in body.local_decls.iter_enumerated() {
405 if exclude.contains(local) {
406 continue;
407 }
408 if decl.ty.is_async_drop_in_place_coroutine(tcx) {
409 continue;
410 }
411
412 debug_assert!(self.locals[local].is_none());
414 let place = self.places.push(PlaceInfo::new(decl.ty, None));
415 self.locals[local] = Some(place);
416 }
417
418 let mut collector =
420 PlaceCollector { tcx, body, map: self, assignments: Default::default() };
421 collector.visit_body(body);
422 let PlaceCollector { mut assignments, .. } = collector;
423
424 let mut num_places = 0;
436 while num_places < self.places.len() {
437 num_places = self.places.len();
438
439 for assign in 0.. {
440 let Some(&(lhs, rhs)) = assignments.get_index(assign) else { break };
441
442 let mut child = self.places[lhs].first_child;
444 while let Some(lhs_child) = child {
445 let PlaceInfo { ty, proj_elem, next_sibling, .. } = self.places[lhs_child];
446 let rhs_child =
447 self.register_place(ty, rhs, proj_elem.expect("child is not a projection"));
448 assignments.insert((lhs_child, rhs_child));
449 child = next_sibling;
450 }
451
452 let mut child = self.places[rhs].first_child;
454 while let Some(rhs_child) = child {
455 let PlaceInfo { ty, proj_elem, next_sibling, .. } = self.places[rhs_child];
456 let lhs_child =
457 self.register_place(ty, lhs, proj_elem.expect("child is not a projection"));
458 assignments.insert((lhs_child, rhs_child));
459 child = next_sibling;
460 }
461 }
462 }
463 drop(assignments);
464
465 let typing_env = body.typing_env(tcx);
467 for place_info in self.places.iter_mut() {
468 if let Some(value_limit) = value_limit
470 && self.value_count >= value_limit
471 {
472 break;
473 }
474
475 if let Ok(ty) = tcx.try_normalize_erasing_regions(typing_env, place_info.ty) {
476 place_info.ty = ty;
477 }
478
479 assert!(place_info.value_index.is_none());
481 if let Ok(layout) = tcx.layout_of(typing_env.as_query_input(place_info.ty))
482 && layout.backend_repr.is_scalar()
483 {
484 place_info.value_index = Some(self.value_count.into());
485 self.value_count += 1;
486 }
487 }
488
489 self.inner_values_buffer = Vec::with_capacity(self.value_count);
493 self.inner_values = IndexVec::from_elem(0..0, &self.places);
494 for local in body.local_decls.indices() {
495 if let Some(place) = self.locals[local] {
496 self.cache_preorder_invoke(place);
497 }
498 }
499
500 for opt_place in self.locals.iter_mut() {
502 if let Some(place) = *opt_place
503 && self.inner_values[place].is_empty()
504 {
505 *opt_place = None;
506 }
507 }
508 #[allow(rustc::potential_query_instability)]
509 self.projections.retain(|_, child| !self.inner_values[*child].is_empty());
510 }
511
512 #[tracing::instrument(level = "trace", skip(self), ret)]
513 fn register_place(&mut self, ty: Ty<'tcx>, base: PlaceIndex, elem: TrackElem) -> PlaceIndex {
514 *self.projections.entry((base, elem)).or_insert_with(|| {
515 let next = self.places.push(PlaceInfo::new(ty, Some(elem)));
516 self.places[next].next_sibling = self.places[base].first_child;
517 self.places[base].first_child = Some(next);
518 next
519 })
520 }
521
522 fn cache_preorder_invoke(&mut self, root: PlaceIndex) {
525 let start = self.inner_values_buffer.len();
526 if let Some(vi) = self.places[root].value_index {
527 self.inner_values_buffer.push(vi);
528 }
529
530 let mut next_child = self.places[root].first_child;
532 while let Some(child) = next_child {
533 ensure_sufficient_stack(|| self.cache_preorder_invoke(child));
534 next_child = self.places[child].next_sibling;
535 }
536
537 let end = self.inner_values_buffer.len();
538 self.inner_values[root] = start..end;
539 }
540}
541
542struct PlaceCollector<'a, 'tcx> {
543 tcx: TyCtxt<'tcx>,
544 body: &'a Body<'tcx>,
545 map: &'a mut Map<'tcx>,
546 assignments: FxIndexSet<(PlaceIndex, PlaceIndex)>,
547}
548
549impl<'tcx> PlaceCollector<'_, 'tcx> {
550 #[tracing::instrument(level = "trace", skip(self))]
551 fn register_place(&mut self, place: Place<'tcx>) -> Option<PlaceIndex> {
552 let mut place_index = self.map.locals[place.local]?;
554 let mut ty = PlaceTy::from_ty(self.body.local_decls[place.local].ty);
555 tracing::trace!(?place_index, ?ty);
556
557 if let ty::Ref(_, ref_ty, _) | ty::RawPtr(ref_ty, _) = ty.ty.kind()
558 && let ty::Slice(..) = ref_ty.kind()
559 {
560 self.map.register_place(self.tcx.types.usize, place_index, TrackElem::DerefLen);
561 } else if ty.ty.is_enum() {
562 let discriminant_ty = ty.ty.discriminant_ty(self.tcx);
563 self.map.register_place(discriminant_ty, place_index, TrackElem::Discriminant);
564 }
565
566 for proj in place.projection {
567 let track_elem = proj.try_into().ok()?;
568 ty = ty.projection_ty(self.tcx, proj);
569 place_index = self.map.register_place(ty.ty, place_index, track_elem);
570 tracing::trace!(?proj, ?place_index, ?ty);
571
572 if let ty::Ref(_, ref_ty, _) | ty::RawPtr(ref_ty, _) = ty.ty.kind()
573 && let ty::Slice(..) = ref_ty.kind()
574 {
575 self.map.register_place(self.tcx.types.usize, place_index, TrackElem::DerefLen);
576 } else if ty.ty.is_enum() {
577 let discriminant_ty = ty.ty.discriminant_ty(self.tcx);
578 self.map.register_place(discriminant_ty, place_index, TrackElem::Discriminant);
579 }
580 }
581
582 Some(place_index)
583 }
584}
585
586impl<'tcx> Visitor<'tcx> for PlaceCollector<'_, 'tcx> {
587 #[tracing::instrument(level = "trace", skip(self))]
588 fn visit_place(&mut self, place: &Place<'tcx>, ctxt: PlaceContext, _: Location) {
589 if !ctxt.is_use() {
590 return;
591 }
592
593 self.register_place(*place);
594 }
595
596 fn visit_assign(&mut self, lhs: &Place<'tcx>, rhs: &Rvalue<'tcx>, location: Location) {
597 self.super_assign(lhs, rhs, location);
598
599 match rhs {
600 Rvalue::Use(Operand::Move(rhs) | Operand::Copy(rhs)) | Rvalue::CopyForDeref(rhs) => {
601 let Some(lhs) = self.register_place(*lhs) else { return };
602 let Some(rhs) = self.register_place(*rhs) else { return };
603 self.assignments.insert((lhs, rhs));
604 }
605 Rvalue::Aggregate(kind, fields) => {
606 let Some(mut lhs) = self.register_place(*lhs) else { return };
607 match **kind {
608 AggregateKind::Adt(_, _, _, _, Some(_)) => return,
610 AggregateKind::Adt(_, variant, _, _, None) => {
611 let ty = self.map.places[lhs].ty;
612 if ty.is_enum() {
613 lhs = self.map.register_place(ty, lhs, TrackElem::Variant(variant));
614 }
615 }
616 AggregateKind::RawPtr(..)
617 | AggregateKind::Array(_)
618 | AggregateKind::Tuple
619 | AggregateKind::Closure(..)
620 | AggregateKind::Coroutine(..)
621 | AggregateKind::CoroutineClosure(..) => {}
622 }
623 for (index, field) in fields.iter_enumerated() {
624 if let Some(rhs) = field.place()
625 && let Some(rhs) = self.register_place(rhs)
626 {
627 let lhs = self.map.register_place(
628 self.map.places[rhs].ty,
629 lhs,
630 TrackElem::Field(index),
631 );
632 self.assignments.insert((lhs, rhs));
633 }
634 }
635 }
636 _ => {}
637 }
638 }
639}
640
641impl<'tcx> Map<'tcx> {
642 pub fn apply(&self, place: PlaceIndex, elem: TrackElem) -> Option<PlaceIndex> {
644 self.projections.get(&(place, elem)).copied()
645 }
646
647 fn find_extra(
649 &self,
650 place: PlaceRef<'_>,
651 extra: impl IntoIterator<Item = TrackElem>,
652 ) -> Option<PlaceIndex> {
653 let mut index = *self.locals[place.local].as_ref()?;
654
655 for &elem in place.projection {
656 index = self.apply(index, elem.try_into().ok()?)?;
657 }
658 for elem in extra {
659 index = self.apply(index, elem)?;
660 }
661
662 Some(index)
663 }
664
665 pub fn find(&self, place: PlaceRef<'_>) -> Option<PlaceIndex> {
667 self.find_extra(place, [])
668 }
669
670 pub fn find_discr(&self, place: PlaceRef<'_>) -> Option<PlaceIndex> {
672 self.find_extra(place, [TrackElem::Discriminant])
673 }
674
675 pub fn find_len(&self, place: PlaceRef<'_>) -> Option<PlaceIndex> {
677 self.find_extra(place, [TrackElem::DerefLen])
678 }
679
680 fn children(&self, parent: PlaceIndex) -> impl Iterator<Item = PlaceIndex> {
682 Children::new(self, parent)
683 }
684
685 fn for_each_aliasing_place(
693 &self,
694 place: PlaceRef<'_>,
695 tail_elem: Option<TrackElem>,
696 f: &mut impl FnMut(ValueIndex),
697 ) {
698 if place.is_indirect_first_projection() {
699 return;
701 }
702 let Some(mut index) = self.locals[place.local] else {
703 return;
705 };
706 let elems = place.projection.iter().map(|&elem| elem.try_into()).chain(tail_elem.map(Ok));
707 for elem in elems {
708 if let Some(vi) = self.places[index].value_index {
710 f(vi);
711 }
712
713 let Ok(elem) = elem else { return };
714 let sub = self.apply(index, elem);
715 if let TrackElem::Variant(..) | TrackElem::Discriminant = elem {
716 self.for_each_variant_sibling(index, sub, f);
718 }
719 if let Some(sub) = sub {
720 index = sub
721 } else {
722 return;
723 }
724 }
725 self.for_each_value_inside(index, f);
726 }
727
728 fn for_each_variant_sibling(
730 &self,
731 parent: PlaceIndex,
732 preserved_child: Option<PlaceIndex>,
733 f: &mut impl FnMut(ValueIndex),
734 ) {
735 for sibling in self.children(parent) {
736 let elem = self.places[sibling].proj_elem;
737 if let Some(TrackElem::Variant(..) | TrackElem::Discriminant) = elem
740 && Some(sibling) != preserved_child
742 {
743 self.for_each_value_inside(sibling, f);
744 }
745 }
746 }
747
748 fn for_each_value_inside(&self, root: PlaceIndex, f: &mut impl FnMut(ValueIndex)) {
750 let range = self.inner_values[root].clone();
751 let values = &self.inner_values_buffer[range];
752 for &v in values {
753 f(v)
754 }
755 }
756
757 pub fn for_each_projection_value<O>(
759 &self,
760 root: PlaceIndex,
761 value: O,
762 project: &mut impl FnMut(TrackElem, &O) -> Option<O>,
763 f: &mut impl FnMut(PlaceIndex, &O),
764 ) {
765 if self.inner_values[root].is_empty() {
767 return;
768 }
769
770 if self.places[root].value_index.is_some() {
771 f(root, &value)
772 }
773
774 for child in self.children(root) {
775 let elem = self.places[child].proj_elem.unwrap();
776 if let Some(value) = project(elem, &value) {
777 self.for_each_projection_value(child, value, project, f);
778 }
779 }
780 }
781}
782
783#[derive(Debug)]
788struct PlaceInfo<'tcx> {
789 ty: Ty<'tcx>,
791
792 value_index: Option<ValueIndex>,
794
795 proj_elem: Option<TrackElem>,
797
798 first_child: Option<PlaceIndex>,
800
801 next_sibling: Option<PlaceIndex>,
803}
804
805impl<'tcx> PlaceInfo<'tcx> {
806 fn new(ty: Ty<'tcx>, proj_elem: Option<TrackElem>) -> Self {
807 Self { ty, next_sibling: None, first_child: None, proj_elem, value_index: None }
808 }
809}
810
811struct Children<'a, 'tcx> {
812 map: &'a Map<'tcx>,
813 next: Option<PlaceIndex>,
814}
815
816impl<'a, 'tcx> Children<'a, 'tcx> {
817 fn new(map: &'a Map<'tcx>, parent: PlaceIndex) -> Self {
818 Self { map, next: map.places[parent].first_child }
819 }
820}
821
822impl Iterator for Children<'_, '_> {
823 type Item = PlaceIndex;
824
825 fn next(&mut self) -> Option<Self::Item> {
826 match self.next {
827 Some(child) => {
828 self.next = self.map.places[child].next_sibling;
829 Some(child)
830 }
831 None => None,
832 }
833 }
834}
835
836#[derive(Debug)]
838pub enum ValueOrPlace<V> {
839 Value(V),
840 Place(PlaceIndex),
841}
842
843impl<V: HasTop> ValueOrPlace<V> {
844 pub const TOP: Self = ValueOrPlace::Value(V::TOP);
845}
846
847#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
851pub enum TrackElem {
852 Field(FieldIdx),
853 Variant(VariantIdx),
854 Discriminant,
855 DerefLen,
857}
858
859impl<V, T> TryFrom<ProjectionElem<V, T>> for TrackElem {
860 type Error = ();
861
862 fn try_from(value: ProjectionElem<V, T>) -> Result<Self, Self::Error> {
863 match value {
864 ProjectionElem::Field(field, _) => Ok(TrackElem::Field(field)),
865 ProjectionElem::Downcast(_, idx) => Ok(TrackElem::Variant(idx)),
866 _ => Err(()),
867 }
868 }
869}
870
871pub fn iter_fields<'tcx>(
873 ty: Ty<'tcx>,
874 tcx: TyCtxt<'tcx>,
875 typing_env: ty::TypingEnv<'tcx>,
876 mut f: impl FnMut(Option<VariantIdx>, FieldIdx, Ty<'tcx>),
877) {
878 match ty.kind() {
879 ty::Tuple(list) => {
880 for (field, ty) in list.iter().enumerate() {
881 f(None, field.into(), ty);
882 }
883 }
884 ty::Adt(def, args) => {
885 if def.is_union() {
886 return;
887 }
888 for (v_index, v_def) in def.variants().iter_enumerated() {
889 let variant = if def.is_struct() { None } else { Some(v_index) };
890 for (f_index, f_def) in v_def.fields.iter().enumerate() {
891 let field_ty = f_def.ty(tcx, args);
892 let field_ty = tcx
893 .try_normalize_erasing_regions(typing_env, field_ty)
894 .unwrap_or_else(|_| tcx.erase_regions(field_ty));
895 f(variant, f_index.into(), field_ty);
896 }
897 }
898 }
899 ty::Closure(_, args) => {
900 iter_fields(args.as_closure().tupled_upvars_ty(), tcx, typing_env, f);
901 }
902 ty::Coroutine(_, args) => {
903 iter_fields(args.as_coroutine().tupled_upvars_ty(), tcx, typing_env, f);
904 }
905 ty::CoroutineClosure(_, args) => {
906 iter_fields(args.as_coroutine_closure().tupled_upvars_ty(), tcx, typing_env, f);
907 }
908 _ => (),
909 }
910}
911
912pub fn excluded_locals(body: &Body<'_>) -> DenseBitSet<Local> {
914 struct Collector {
915 result: DenseBitSet<Local>,
916 }
917
918 impl<'tcx> Visitor<'tcx> for Collector {
919 fn visit_place(&mut self, place: &Place<'tcx>, context: PlaceContext, _location: Location) {
920 if (context.is_borrow()
921 || context.is_address_of()
922 || context.is_drop()
923 || context == PlaceContext::MutatingUse(MutatingUseContext::AsmOutput))
924 && !place.is_indirect()
925 {
926 self.result.insert(place.local);
929 }
930 }
931 }
932
933 let mut collector = Collector { result: DenseBitSet::new_empty(body.local_decls.len()) };
934 collector.visit_body(body);
935 collector.result
936}
937
938fn debug_with_context_rec<V: Debug + Eq + HasBottom>(
939 place: PlaceIndex,
940 place_str: &str,
941 new: &StateData<V>,
942 old: Option<&StateData<V>>,
943 map: &Map<'_>,
944 f: &mut Formatter<'_>,
945) -> std::fmt::Result {
946 if let Some(value) = map.places[place].value_index {
947 match old {
948 None => writeln!(f, "{}: {:?}", place_str, new.get(value))?,
949 Some(old) => {
950 if new.get(value) != old.get(value) {
951 writeln!(f, "\u{001f}-{}: {:?}", place_str, old.get(value))?;
952 writeln!(f, "\u{001f}+{}: {:?}", place_str, new.get(value))?;
953 }
954 }
955 }
956 }
957
958 for child in map.children(place) {
959 let info_elem = map.places[child].proj_elem.unwrap();
960 let child_place_str = match info_elem {
961 TrackElem::Discriminant => {
962 format!("discriminant({place_str})")
963 }
964 TrackElem::Variant(idx) => {
965 format!("({place_str} as {idx:?})")
966 }
967 TrackElem::Field(field) => {
968 if place_str.starts_with('*') {
969 format!("({}).{}", place_str, field.index())
970 } else {
971 format!("{}.{}", place_str, field.index())
972 }
973 }
974 TrackElem::DerefLen => {
975 format!("Len(*{})", place_str)
976 }
977 };
978 debug_with_context_rec(child, &child_place_str, new, old, map, f)?;
979 }
980
981 Ok(())
982}
983
984pub fn debug_with_context<V: Debug + Eq + HasBottom>(
985 new: &StateData<V>,
986 old: Option<&StateData<V>>,
987 map: &Map<'_>,
988 f: &mut Formatter<'_>,
989) -> std::fmt::Result {
990 for (local, place) in map.locals.iter_enumerated() {
991 if let Some(place) = place {
992 debug_with_context_rec(*place, &format!("{local:?}"), new, old, map, f)?;
993 }
994 }
995 Ok(())
996}