Skip to main content

rapx/analysis/alias/
tree.rs

1//! Per-function alias *derivation* forest, used only for field-path resolution.
2//!
3//! Every pointer-bearing local is a node; an edge `parent ← child` records that
4//! the child was derived from the parent (reborrow, raw-pointer cast, field
5//! read), each edge carrying the field path (`self.node.ptr` → `[node, ptr]`).
6//! [`AliasTree::resolve_local_to_root`] walks the forest to the root local,
7//! concatenating field paths, which the escape/encapsulation analysis uses to
8//! find *which* struct field a view came from.
9//!
10//! The view-vs-view (shared-XOR-mutable) aliasing check no longer lives here —
11//! it is flow-sensitive and walks the VM's current locals + allocation `parent`
12//! chain (`flow_xor_violation` in `vm/alias.rs`), so this static forest is not
13//! consulted for live-value grouping.
14
15use crate::util::mir_utils;
16use super::hazard as alias_hazard;
17use rustc_hash::FxHashMap;
18use rustc_hir::def_id::DefId;
19use rustc_middle::{
20    mir::{Local, Operand, Rvalue, StatementKind},
21    ty::{Ty, TyCtxt, TyKind},
22};
23
24/// A node identifier (index into [`AliasTree::nodes`]).
25pub(crate) type TagId = usize;
26
27/// A single node in the alias forest.
28#[derive(Clone, Debug)]
29pub(crate) struct AliasNode {
30    pub parent: Option<TagId>,
31    /// Field projections (`ProjectionElem::Field` indices) from the parent's
32    /// referent down to this pointer (e.g. `self.node.ptr` → `[node, ptr]`).
33    /// Empty for whole-local pointers. Used by [`AliasTree::resolve_to_root`] to
34    /// reconstruct the nested-field origin.
35    pub fields: Vec<usize>,
36    pub local: Local,
37}
38
39/// The per-function alias derivation forest.
40#[derive(Clone, Debug)]
41pub(crate) struct AliasTree {
42    pub nodes: Vec<AliasNode>,
43    /// The tag that `local` currently names (its most recent binding).
44    tag_of_local: FxHashMap<Local, TagId>,
45}
46
47impl AliasTree {
48    /// Build the derivation forest for `def_id` by scanning its MIR.
49    ///
50    /// Parameters and owned results are roots; every `target =
51    /// <ref/cast/raw/copy> source` statement adds an edge from `source`'s tag to
52    /// a new (or shared) tag for `target`. `StorageDead`/moves are *not* applied
53    /// here — the forest is a static, block-order approximation used only for
54    /// field-path resolution.
55    pub(crate) fn build<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> Self {
56        let body = tcx.optimized_mir(def_id);
57        let mut tree = AliasTree {
58            nodes: Vec::new(),
59            tag_of_local: FxHashMap::default(),
60        };
61
62        for local_index in 1..=body.arg_count {
63            let local = Local::from_usize(local_index);
64            let ty = body.local_decls[local].ty;
65            if classify(ty).is_some() {
66                tree.add(None, Vec::new(), local);
67            }
68        }
69
70        for block in body.basic_blocks.iter() {
71            for statement in &block.statements {
72                let StatementKind::Assign(assign) = &statement.kind else {
73                    continue;
74                };
75                let (target, rvalue) = assign.as_ref();
76                match rvalue {
77                    // Copy/move of a *whole* pointer is the same tag, not a new
78                    // node. A copy through a field projection (`_2 = (*self).next`)
79                    // is a *derivation* (reads the raw field), so it falls through
80                    // to the derivation arm below.
81                    Rvalue::Use(Operand::Copy(place), ..)
82                    | Rvalue::Use(Operand::Move(place), ..)
83                    | Rvalue::CopyForDeref(place)
84                        if field_projection(place).is_empty() =>
85                    {
86                        if let Some(tag) = tree.tag_of_local.get(&place.local).copied() {
87                            tree.tag_of_local.insert(target.local, tag);
88                        }
89                    }
90                    // True derivation: reborrow (`&mut x`), raw-pointer creation
91                    // (`addr_of!(x)`), cast (`&mut → *mut`, `*mut → *const`) and
92                    // field read (`(*self).next`).
93                    _ => {
94                        if let Some(place) = mir_utils::rvalue_source_place(rvalue)
95                            && let Some(parent) = tree.tag_of_local.get(&place.local).copied()
96                        {
97                            let ty = body.local_decls[target.local].ty;
98                            if classify(ty).is_some() {
99                                tree.add(Some(parent), field_projection(place), target.local);
100                            }
101                        }
102                    }
103                }
104            }
105
106            // An owned result is a fresh root. For pointer/reference results,
107            // resolve the source argument from the callee MIR when available.
108            if let rustc_middle::mir::TerminatorKind::Call {
109                func, args, destination, ..
110            } = &block.terminator().kind
111            {
112                let dest_local = destination.local;
113                let dest_ty = body.local_decls[dest_local].ty;
114                if let Some(is_owned) = classify(dest_ty) {
115                    if is_owned {
116                        tree.add(None, Vec::new(), dest_local);
117                    } else if let Some(source_arg) = call_source_arg(tcx, func, args)
118                        && let Some(place) = args[source_arg].node.place()
119                        && let Some(parent) = tree.tag_of_local.get(&place.local).copied()
120                    {
121                        tree.add(Some(parent), field_projection(&place), dest_local);
122                    }
123                }
124            }
125        }
126
127        tree
128    }
129
130    fn add(&mut self, parent: Option<TagId>, fields: Vec<usize>, local: Local) -> TagId {
131        let tag = self.nodes.len();
132        self.nodes.push(AliasNode {
133            parent,
134            fields,
135            local,
136        });
137        self.tag_of_local.insert(local, tag);
138        tag
139    }
140
141    /// The tag bound to `local`, if any.
142    pub(crate) fn tag_of(&self, local: Local) -> Option<TagId> {
143        self.tag_of_local.get(&local).copied()
144    }
145
146    /// Walk `tag`'s parent edges to the root, concatenating the `fields` of each
147    /// hop. Returns the root local and the full field path (`self.node.ptr` →
148    /// `(self, [node, ptr])`).
149    fn resolve_to_root(&self, tag: TagId) -> (Local, Vec<usize>) {
150        let mut cur = tag;
151        let mut fields: Vec<usize> = Vec::new();
152        let mut guard = 0;
153        loop {
154            let node = &self.nodes[cur];
155            let mut combined = node.fields.clone();
156            combined.extend(fields.iter().copied());
157            fields = combined;
158            match node.parent {
159                Some(parent) => cur = parent,
160                None => return (node.local, fields),
161            }
162            guard += 1;
163            if guard > self.nodes.len() {
164                return (self.nodes[cur].local, fields);
165            }
166        }
167    }
168
169    /// Resolve a local to its root `(root_local, field_path)` via the tree. An
170    /// unmapped local resolves to itself with an empty field path.
171    pub(crate) fn resolve_local_to_root(&self, local: Local) -> (usize, Vec<usize>) {
172        match self.tag_of(local) {
173            Some(tag) => {
174                let (root, fields) = self.resolve_to_root(tag);
175                (root.as_usize(), fields)
176            }
177            None => (local.as_usize(), Vec::new()),
178        }
179    }
180}
181
182fn call_source_arg<'tcx>(
183    tcx: TyCtxt<'tcx>,
184    func: &Operand<'tcx>,
185    args: &[rustc_span::Spanned<Operand<'tcx>>],
186) -> Option<usize> {
187    let callee = mir_utils::dep_callee_def_id(func)?;
188    if let Some(source_arg) = alias_hazard::pointer_result_source_arg(tcx, callee) {
189        return (source_arg < args.len()).then_some(source_arg);
190    }
191    let inputs = tcx.fn_sig(callee).skip_binder().inputs().skip_binder();
192    let mut pointer_args = inputs.iter().enumerate().filter(|(index, ty)| {
193        *index < args.len() && classify(**ty).is_some()
194    });
195    let (source_arg, _) = pointer_args.next()?;
196    pointer_args.next().is_none().then_some(source_arg)
197}
198
199/// The `Field` projection indices of `place`, in order (`Deref`/index/etc. are
200/// skipped), matching `PlaceKey::fields`.
201fn field_projection(place: &rustc_middle::mir::Place<'_>) -> Vec<usize> {
202    place
203        .projection
204        .iter()
205        .filter_map(|p| match p {
206            rustc_middle::mir::ProjectionElem::Field(idx, _) => Some(idx.as_usize()),
207            _ => None,
208        })
209        .collect()
210}
211
212/// Whether `ty` is pointer-bearing (`Ref`/`RawPtr`/`Adt`), returning whether it
213/// is an *owned* container (`Box`/`Vec`/… — a forest root) when it is.
214fn classify(ty: Ty<'_>) -> Option<bool> {
215    match ty.kind() {
216        TyKind::Ref(_, _, _) | TyKind::RawPtr(_, _) => Some(false),
217        TyKind::Adt(_, _) => Some(true),
218        _ => None,
219    }
220}