rapx/analysis/alias/
mod.rs

1pub mod default;
2pub mod mfp;
3pub mod observer;
4use crate::utils::source::get_fn_name_byid;
5
6use super::super::Analysis;
7use crate::compat::FxHashMap;
8use rustc_hir::def_id::DefId;
9use rustc_middle::{
10    mir::Local,
11    ty::{GenericArgsRef, Ty, TyCtxt, TyKind},
12};
13use rustc_span::def_id::LOCAL_CRATE;
14use std::{collections::HashSet, fmt};
15
16/// The data structure to store aliases for a set of functions.
17pub type FnAliasMap = FxHashMap<DefId, FnAliasPairs>;
18
19/// This is a wrapper struct for displaying FnAliasMap.
20pub struct FnAliasMapWrapper(pub FnAliasMap);
21
22/// This trait provides features related to alias analysis.
23pub trait AliasAnalysis: Analysis {
24    /// Return the aliases among the function arguments and return value of a specific function.
25    fn get_fn_alias(&self, def_id: DefId) -> Option<FnAliasPairs>;
26    /// Return the aliases among the function arguments and return value for all functions.
27    fn get_all_fn_alias(&self) -> FnAliasMap;
28    /// Return the aliases among the function arguments and return value for functions of the local
29    /// crate.
30    fn get_local_fn_alias(&self) -> FnAliasMap {
31        self.get_all_fn_alias()
32            .iter()
33            .filter(|(def_id, _)| def_id.krate == LOCAL_CRATE)
34            .map(|(k, v)| (*k, v.clone()))
35            .collect()
36    }
37}
38
39/// To store the alias relationships among arguments and return values.
40/// Each function may have multiple return instructions, leading to different RetAlias.
41#[derive(Debug, Clone)]
42pub struct FnAliasPairs {
43    arg_size: usize,
44    alias_set: HashSet<AliasPair>,
45}
46
47impl FnAliasPairs {
48    pub fn new(arg_size: usize) -> FnAliasPairs {
49        Self {
50            arg_size,
51            alias_set: HashSet::new(),
52        }
53    }
54
55    pub fn arg_size(&self) -> usize {
56        self.arg_size
57    }
58
59    pub fn aliases(&self) -> &HashSet<AliasPair> {
60        &self.alias_set
61    }
62
63    pub fn add_alias(&mut self, alias: AliasPair) {
64        self.alias_set.insert(alias);
65    }
66
67    pub fn len(&self) -> usize {
68        self.alias_set.len()
69    }
70
71    pub fn sort_alias_index(&mut self) {
72        let alias_set = std::mem::take(&mut self.alias_set);
73        let mut new_alias_set = HashSet::with_capacity(alias_set.len());
74
75        for mut ra in alias_set.into_iter() {
76            if ra.left_local() >= ra.right_local() {
77                ra.swap();
78            }
79            new_alias_set.insert(ra);
80        }
81        self.alias_set = new_alias_set;
82    }
83
84    /// Compress field paths: truncate each side's field list to its
85    /// first element.  This matches the old MoP alias analysis behaviour
86    /// where deeply nested fields like `0.0.0.0` are shortened to `0.0`.
87    pub fn compress_fields(&mut self) {
88        let alias_set = std::mem::take(&mut self.alias_set);
89        let mut compressed = HashSet::with_capacity(alias_set.len());
90        for mut ra in alias_set.into_iter() {
91            if !ra.lhs_fields.is_empty() {
92                ra.lhs_fields = vec![ra.lhs_fields[0]];
93            }
94            if !ra.rhs_fields.is_empty() {
95                ra.rhs_fields = vec![ra.rhs_fields[0]];
96            }
97            compressed.insert(ra);
98        }
99        self.alias_set = compressed;
100    }
101}
102
103impl fmt::Display for FnAliasPairs {
104    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
105        if self.aliases().is_empty() {
106            write!(f, "null")?;
107        } else {
108            let mut facts: Vec<_> = self.aliases().iter().collect();
109            facts.sort_by(|a, b| {
110                a.left_local
111                    .cmp(&b.left_local)
112                    .then(a.right_local.cmp(&b.right_local))
113                    .then(a.lhs_fields.cmp(&b.lhs_fields))
114                    .then(a.rhs_fields.cmp(&b.rhs_fields))
115            });
116            let joined = facts
117                .into_iter()
118                .map(|fact| format!("{}", fact))
119                .collect::<Vec<_>>()
120                .join(", ");
121            write!(f, "{}", joined)?;
122        }
123        Ok(())
124    }
125}
126
127impl fmt::Display for FnAliasMapWrapper {
128    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
129        writeln!(f, "=== Print alias analysis results ===")?;
130        for (def_id, result) in &self.0 {
131            let fn_name = get_fn_name_byid(def_id);
132            writeln!(f, "Alias of {:?}: {}", fn_name, result)?;
133        }
134        Ok(())
135    }
136}
137
138/// Identity of a struct field that a place resolves to.
139#[derive(Clone, Debug)]
140pub struct FieldOrigin {
141    pub struct_def_id: DefId,
142    pub field_index: usize,
143    pub field_name: String,
144}
145
146/// Unwrap Ref / RawPtr / Adt layers to get the innermost ADT definition.
147pub fn adt_from_ty<'tcx>(ty: Ty<'tcx>) -> Option<(DefId, GenericArgsRef<'tcx>)> {
148    match ty.kind() {
149        TyKind::Ref(_, inner, _) | TyKind::RawPtr(inner, _) => adt_from_ty(*inner),
150        TyKind::Adt(adt, args) => Some((adt.did(), *args)),
151        _ => None,
152    }
153}
154
155/// If `local` (typically `1` = self) with `fields` in `def_id`'s body
156/// corresponds to a struct field, return its identity.
157/// Trace a multi-level field path (`self.node.ptr`, `self.mid.leaf.ptr`) down
158/// to the innermost raw-pointer field, so the encapsulation check targets
159/// `Inner::ptr` / `Leaf::ptr` rather than the intermediate `Outer::node` /
160/// `Outer::mid` field. Intermediate reference and ADT layers are dereferenced
161/// through; if the path ends without reaching a raw pointer, `None` is returned.
162fn resolve_field_origin_inner<'tcx>(
163    tcx: TyCtxt<'tcx>,
164    root_ty: Ty<'tcx>,
165    fields: &[usize],
166) -> Option<FieldOrigin> {
167    let (mut struct_def_id, mut args) = adt_from_ty(root_ty)?;
168    for &idx in fields {
169        let adt = tcx.adt_def(struct_def_id);
170        let field = adt.all_fields().nth(idx)?;
171        let field_ty = crate::helpers::mir_utils::field_ty(tcx, field, args);
172        if matches!(field_ty.kind(), TyKind::RawPtr(..)) {
173            return Some(FieldOrigin {
174                struct_def_id,
175                field_index: idx,
176                field_name: field.name.to_string(),
177            });
178        }
179        let Some((did, a)) = adt_from_ty(field_ty) else {
180            return None;
181        };
182        struct_def_id = did;
183        args = a;
184    }
185    None
186}
187
188pub fn resolve_self_field_origin<'tcx>(
189    tcx: TyCtxt<'tcx>,
190    def_id: DefId,
191    local: usize,
192    fields: &[usize],
193) -> Option<FieldOrigin> {
194    if local != 1 || fields.is_empty() {
195        return None;
196    }
197    let body = tcx.optimized_mir(def_id);
198    let self_ty = body.local_decls[Local::from_usize(1)].ty;
199    resolve_field_origin_inner(tcx, self_ty, fields)
200}
201
202/// Like `resolve_self_field_origin` but uses the type of `local` instead
203/// of always `_1`.  For origins from call-site verification.
204pub fn resolve_any_field_origin<'tcx>(
205    tcx: TyCtxt<'tcx>,
206    def_id: DefId,
207    local: usize,
208    fields: &[usize],
209) -> Option<FieldOrigin> {
210    if fields.is_empty() {
211        return None;
212    }
213    let body = tcx.optimized_mir(def_id);
214    let self_ty = body.local_decls[Local::from_usize(local)].ty;
215    resolve_field_origin_inner(tcx, self_ty, fields)
216}
217
218/// AliasPair is used to store the alias relationships between two places.
219/// The result is field-sensitive.
220#[derive(Debug, Clone, Hash, PartialEq, Eq)]
221pub struct AliasPair {
222    pub left_local: usize,
223    pub lhs_fields: Vec<usize>,
224    pub right_local: usize,
225    pub rhs_fields: Vec<usize>,
226}
227
228impl AliasPair {
229    pub fn new(left_local: usize, right_local: usize) -> AliasPair {
230        AliasPair {
231            left_local,
232            lhs_fields: Vec::<usize>::new(),
233            right_local,
234            rhs_fields: Vec::<usize>::new(),
235        }
236    }
237
238    /// Swap the two elements of an alias pair, i.e., left to right, and right to left.
239    pub fn swap(&mut self) {
240        std::mem::swap(&mut self.left_local, &mut self.right_local);
241        std::mem::swap(&mut self.lhs_fields, &mut self.rhs_fields);
242    }
243
244    pub fn left_local(&self) -> usize {
245        self.left_local
246    }
247
248    pub fn right_local(&self) -> usize {
249        self.right_local
250    }
251
252    pub fn lhs_fields(&self) -> &[usize] {
253        &self.lhs_fields
254    }
255
256    pub fn rhs_fields(&self) -> &[usize] {
257        &self.rhs_fields
258    }
259}
260
261impl fmt::Display for AliasPair {
262    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
263        write!(
264            f,
265            "({},{})",
266            aa_place_desc_str(self.left_local, &self.lhs_fields, true),
267            aa_place_desc_str(self.right_local, &self.rhs_fields, true)
268        )
269    }
270}
271
272fn aa_place_desc_str(no: usize, fields: &[usize], field_sensitive: bool) -> String {
273    let mut result = String::new();
274    result.push_str(&no.to_string());
275    if !field_sensitive {
276        return result;
277    }
278    for num in fields.iter() {
279        result.push('.');
280        result.push_str(&num.to_string());
281    }
282    result
283}
rapx/analysis/alias/mod.rs

rapx/analysis/alias/
mod.rs
