rapx/analysis/core/api_dependency/
mod.rs

1#![allow(dead_code)]
2#![allow(unused_variables)]
3
4pub mod default;
5mod extract;
6mod graph;
7mod visitor;
8
9use petgraph::{graph::NodeIndex, Graph};
10use rustc_hir::def_id::DefId;
11use rustc_middle::ty::{self, Ty, TyCtxt};
12
13use std::{collections::HashMap, hash::Hash};
14
15pub trait ApiDependencyAnalysis<'tcx> {
16    fn get_api_dependency_graph(&self) -> ApiDependencyGraph<'tcx>;
17}
18
19type InnerGraph<'tcx> = Graph<Node<'tcx>, Edge>;
20
21#[derive(Clone)]
22pub struct ApiDependencyGraph<'tcx> {
23    graph: InnerGraph<'tcx>,
24    node_indices: HashMap<Node<'tcx>, NodeIndex>,
25}
26
27#[derive(Clone, Debug, Eq, PartialEq, Hash)]
28pub enum Node<'tcx> {
29    Api(DefId),
30    Ty(TyWrapper<'tcx>),
31    GenericParamDef(DefId, usize, String, bool), // (fn_def_id, index, symbol, is_lifetime_param)
32}
33
34#[derive(Clone, Copy, Eq, PartialEq, Debug)]
35pub enum Edge {
36    Arg(usize),
37    Ret,
38    Fn2Generic,
39}
40#[derive(Hash, Eq, PartialEq, Debug)]
41pub enum LifetimeKind {
42    Static,
43    Bound(usize),
44    Any(usize),
45}
46
47#[derive(Hash, Eq, PartialEq, Debug, Copy, Clone)]
48pub struct Lifetime {
49    // pub kind: LifetimeKind,
50    pub id: usize,
51}
52
53/// TyWrapper is a wrapper of rustc_middle::ty::Ty,
54/// for the purpose of attaching custom lifetime information to Ty.
55#[derive(Clone, Eq, Debug)]
56pub struct TyWrapper<'tcx> {
57    ty: ty::Ty<'tcx>,
58    lifetime_map: Vec<Lifetime>,
59}
60
61impl Hash for TyWrapper<'_> {
62    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
63        hash_ty(self.ty, state, &mut 0);
64    }
65}
66
67fn eq_ty<'tcx>(lhs: Ty<'tcx>, rhs: Ty<'tcx>) -> bool {
68    match (lhs.kind(), rhs.kind()) {
69        (ty::TyKind::Adt(adt_def1, generic_arg1), ty::TyKind::Adt(adt_def2, generic_arg2)) => {
70            if adt_def1.did() != adt_def2.did() {
71                return false;
72            }
73            for (arg1, arg2) in generic_arg1.iter().zip(generic_arg2.iter()) {
74                match (arg1.kind(), arg2.kind()) {
75                    (ty::GenericArgKind::Lifetime(_), ty::GenericArgKind::Lifetime(_)) => continue,
76                    (ty::GenericArgKind::Type(ty1), ty::GenericArgKind::Type(ty2)) => {
77                        if !eq_ty(ty1, ty2) {
78                            return false;
79                        }
80                    }
81                    (ty::GenericArgKind::Const(ct1), ty::GenericArgKind::Const(ct2)) => {
82                        if ct1 != ct2 {
83                            return false;
84                        }
85                    }
86                    _ => return false,
87                }
88            }
89            true
90        }
91        (
92            ty::TyKind::RawPtr(inner_ty1, mutability1),
93            ty::TyKind::RawPtr(inner_ty2, mutability2),
94        )
95        | (
96            ty::TyKind::Ref(_, inner_ty1, mutability1),
97            ty::TyKind::Ref(_, inner_ty2, mutability2),
98        ) => mutability1 == mutability2 && eq_ty(*inner_ty1, *inner_ty2),
99        (ty::TyKind::Array(inner_ty1, _), ty::TyKind::Array(inner_ty2, _))
100        | (ty::TyKind::Pat(inner_ty1, _), ty::TyKind::Pat(inner_ty2, _))
101        | (ty::TyKind::Slice(inner_ty1), ty::TyKind::Slice(inner_ty2)) => {
102            eq_ty(*inner_ty1, *inner_ty2)
103        }
104        (ty::TyKind::Tuple(tys1), ty::TyKind::Tuple(tys2)) => {
105            if tys1.len() != tys2.len() {
106                return false;
107            }
108            tys1.iter()
109                .zip(tys2.iter())
110                .all(|(ty1, ty2)| eq_ty(ty1, ty2))
111        }
112        _ => lhs == rhs,
113    }
114}
115
116fn traverse_ty_with_lifetime<'tcx, F: Fn(ty::Region, usize)>(ty: Ty<'tcx>, no: &mut usize, f: &F) {
117    match ty.kind() {
118        ty::TyKind::Adt(_, generic_arg) => {
119            for arg in generic_arg.iter() {
120                match arg.kind() {
121                    ty::GenericArgKind::Lifetime(lt) => {
122                        *no = *no + 1;
123                        f(lt, *no);
124                    }
125                    ty::GenericArgKind::Type(ty) => {
126                        traverse_ty_with_lifetime(ty, no, f);
127                    }
128                    ty::GenericArgKind::Const(_) => {}
129                }
130            }
131        }
132
133        ty::TyKind::RawPtr(inner_ty, _) => {
134            traverse_ty_with_lifetime(*inner_ty, no, f);
135        }
136
137        ty::TyKind::Ref(region, inner_ty, _) => {
138            *no = *no + 1;
139            f(*region, *no);
140            traverse_ty_with_lifetime(*inner_ty, no, f);
141        }
142        ty::TyKind::Array(inner_ty, _)
143        | ty::TyKind::Pat(inner_ty, _)
144        | ty::TyKind::Slice(inner_ty) => {
145            traverse_ty_with_lifetime(*inner_ty, no, f);
146        }
147        ty::TyKind::Tuple(tys) => {
148            for inner_ty in tys.iter() {
149                traverse_ty_with_lifetime(inner_ty, no, f);
150            }
151        }
152        _ => {
153            unreachable!("unexpected ty kind");
154        }
155    }
156}
157
158// hashing Ty<'tcx>, but ignore the difference of lifetimes
159fn hash_ty<'tcx, H: std::hash::Hasher>(ty: Ty<'tcx>, state: &mut H, no: &mut usize) {
160    // hash the variant
161    match ty.kind() {
162        ty::TyKind::Adt(..) => 0,
163        ty::TyKind::RawPtr(..) => 1,
164        ty::TyKind::Ref(..) => 2,
165        ty::TyKind::Array(..) => 3,
166        ty::TyKind::Pat(..) => 4,
167        ty::TyKind::Slice(..) => 5,
168        ty::TyKind::Tuple(..) => 6,
169        _ => {
170            ty.hash(state);
171            return;
172        }
173    }
174    .hash(state);
175
176    // hash the content
177    match ty.kind() {
178        ty::TyKind::Adt(adt_def, generic_arg) => {
179            adt_def.did().hash(state);
180            for arg in generic_arg.iter() {
181                match arg.kind() {
182                    ty::GenericArgKind::Lifetime(_) => {
183                        *no = *no + 1;
184                        no.hash(state);
185                    }
186                    ty::GenericArgKind::Type(ty) => {
187                        hash_ty(ty, state, no);
188                    }
189                    ty::GenericArgKind::Const(ct) => {
190                        ct.hash(state);
191                    }
192                }
193            }
194        }
195
196        ty::TyKind::RawPtr(inner_ty, mutability) => {
197            mutability.hash(state);
198            hash_ty(*inner_ty, state, no);
199        }
200        ty::TyKind::Ref(_, inner_ty, mutability) => {
201            mutability.hash(state);
202            *no = *no + 1;
203            no.hash(state);
204            hash_ty(*inner_ty, state, no);
205        }
206        ty::TyKind::Array(inner_ty, _)
207        | ty::TyKind::Pat(inner_ty, _)
208        | ty::TyKind::Slice(inner_ty) => {
209            hash_ty(*inner_ty, state, no);
210        }
211        ty::TyKind::Tuple(tys) => {
212            for inner_ty in tys.iter() {
213                hash_ty(inner_ty, state, no);
214            }
215        }
216        _ => {
217            unreachable!("unexpected ty kind");
218        }
219    }
220}
221
222pub fn desc_ty_str<'tcx>(ty: Ty<'tcx>, no: &mut usize, tcx: TyCtxt<'tcx>) -> String {
223    match ty.kind() {
224        ty::TyKind::Adt(adt_def, generic_arg) => {
225            let mut ty_str = tcx.def_path_str(adt_def.did());
226            if !generic_arg.is_empty() {
227                ty_str += "<";
228                ty_str += &generic_arg
229                    .iter()
230                    .map(|arg| match arg.kind() {
231                        ty::GenericArgKind::Lifetime(_) => {
232                            let current_no = *no;
233                            *no = *no + 1;
234                            format!("'#{:?}", current_no)
235                        }
236                        ty::GenericArgKind::Type(ty) => desc_ty_str(ty, no, tcx),
237                        ty::GenericArgKind::Const(ct) => format!("{:?}", ct),
238                    })
239                    .collect::<Vec<String>>()
240                    .join(", ");
241                ty_str += ">";
242            }
243            ty_str
244        }
245
246        ty::TyKind::RawPtr(inner_ty, mutability) => {
247            let mut_str = {
248                match mutability {
249                    ty::Mutability::Mut => "mut",
250                    ty::Mutability::Not => "const",
251                }
252            };
253            format!("*{} {}", mut_str, desc_ty_str(*inner_ty, no, tcx))
254        }
255        ty::TyKind::Ref(_, inner_ty, mutability) => {
256            let mut_str = {
257                match mutability {
258                    ty::Mutability::Mut => "mut",
259                    ty::Mutability::Not => "",
260                }
261            };
262            let current_no = *no;
263            *no = *no + 1;
264            format!(
265                "&'#{}{} {}",
266                current_no,
267                mut_str,
268                desc_ty_str(*inner_ty, no, tcx)
269            )
270        }
271        ty::TyKind::Array(inner_ty, _)
272        | ty::TyKind::Pat(inner_ty, _)
273        | ty::TyKind::Slice(inner_ty) => desc_ty_str(*inner_ty, no, tcx),
274        ty::TyKind::Tuple(tys) => format!(
275            "({})",
276            tys.iter()
277                .map(|ty| desc_ty_str(ty, no, tcx,))
278                .collect::<Vec<String>>()
279                .join(", "),
280        ),
281        _ => format!("{:?}", ty),
282    }
283}
284
285impl<'tcx> TyWrapper<'tcx> {
286    pub fn desc_str(&self, tcx: TyCtxt<'tcx>) -> String {
287        desc_ty_str(self.ty, &mut 0, tcx)
288    }
289}
290
291impl<'tcx> From<Ty<'tcx>> for TyWrapper<'tcx> {
292    fn from(ty: ty::Ty<'tcx>) -> TyWrapper<'tcx> {
293        // TODO: initialize lifetime_map
294        let lifetime_map = Vec::new();
295        TyWrapper { ty, lifetime_map }
296    }
297}
298
299impl PartialEq for TyWrapper<'_> {
300    fn eq(&self, other: &Self) -> bool {
301        eq_ty(self.ty, other.ty)
302    }
303}
rapx/analysis/core/api_dependency/mod.rs

rapx/analysis/core/api_dependency/
mod.rs
