rapx/analysis/core/api_dependency/graph/
mod.rs

1pub mod avail;
2pub mod dep_edge;
3pub mod dep_node;
4mod dump;
5mod resolve;
6mod std_tys;
7pub mod transform;
8mod ty_wrapper;
9
10use super::Config;
11use super::utils;
12use super::visit::{self, FnVisitor};
13use crate::analysis::core::api_dependency::is_fuzzable_ty;
14use crate::analysis::utils::def_path::path_str_def_id;
15use crate::rap_debug;
16use crate::rap_trace;
17use crate::utils::fs::rap_create_file;
18use bit_set::BitSet;
19pub use dep_edge::DepEdge;
20pub use dep_node::DepNode;
21use petgraph::Direction;
22use petgraph::Graph;
23use petgraph::dot;
24use petgraph::graph::NodeIndex;
25use petgraph::visit::EdgeRef;
26use rustc_hir::def_id::DefId;
27use rustc_middle::ty::Binder;
28use rustc_middle::ty::{self, Ty, TyCtxt};
29use std::collections::HashMap;
30use std::collections::HashSet;
31use std::collections::VecDeque;
32use std::hash::Hash;
33use std::io::Write;
34use std::path::Path;
35pub use transform::TransformKind;
36pub use ty_wrapper::TyWrapper;
37
38type InnerGraph<'tcx> = Graph<DepNode<'tcx>, DepEdge>;
39
40#[derive(Clone)]
41pub struct ApiDependencyGraph<'tcx> {
42    graph: InnerGraph<'tcx>,
43    node_indices: HashMap<DepNode<'tcx>, NodeIndex>,
44    ty_nodes: Vec<NodeIndex>,
45    api_nodes: Vec<NodeIndex>,
46    tcx: TyCtxt<'tcx>,
47}
48
49#[derive(Copy, Clone, Debug)]
50pub struct Statistics {
51    pub num_api: usize,
52    pub num_generic_api: usize,
53    pub type_count: usize,
54    pub edge_cnt: usize,
55}
56
57impl Statistics {
58    pub fn info(&self) {
59        rap_info!(
60            "API Graph contains {} API nodes, {} generic API nodes, {} type nodes, {} edges",
61            self.num_api,
62            self.num_generic_api,
63            self.type_count,
64            self.edge_cnt
65        );
66    }
67}
68
69impl<'tcx> ApiDependencyGraph<'tcx> {
70    pub fn new(tcx: TyCtxt<'tcx>) -> ApiDependencyGraph<'tcx> {
71        ApiDependencyGraph {
72            graph: Graph::new(),
73            node_indices: HashMap::new(),
74            ty_nodes: Vec::new(),
75            api_nodes: Vec::new(),
76            tcx,
77        }
78    }
79
80    pub fn num_api(&self) -> usize {
81        self.api_nodes.len()
82    }
83
84    pub fn num_ty(&self) -> usize {
85        self.ty_nodes.len()
86    }
87
88    pub fn api_node_at(&self, idx: usize) -> DepNode<'tcx> {
89        let index = self.api_nodes[idx];
90        self.graph[index]
91    }
92
93    fn tcx(&self) -> TyCtxt<'tcx> {
94        self.tcx
95    }
96
97    pub fn build(&mut self, config: &Config) {
98        let tcx = self.tcx();
99        let mut visitor = FnVisitor::new(config.visit_config, tcx);
100
101        // 1. collect APIs
102        tcx.hir_visit_all_item_likes_in_crate(&mut visitor);
103
104        // 2. add non generic APIs
105        visitor.non_generic_apis().iter().for_each(|&fn_did| {
106            self.add_identity_api(fn_did);
107        });
108
109        // 3. resolve generic API to monomorphic API
110        if config.resolve_generic {
111            self.resolve_generic_api(
112                visitor.non_generic_apis(),
113                visitor.generic_apis(),
114                config.max_generic_search_iteration,
115            );
116        } else {
117            self.update_transform_edges();
118        }
119    }
120
121    pub fn inner_graph(&self) -> &InnerGraph<'tcx> {
122        &self.graph
123    }
124
125    pub fn statistics(&self) -> Statistics {
126        let mut num_api = 0;
127        let mut num_generic_api = 0;
128        let mut ty_cnt = 0;
129        let mut edge_cnt = 0;
130
131        for node in self.graph.node_indices() {
132            match self.graph[node] {
133                DepNode::Api(did, ..) => {
134                    num_api += 1;
135                    if utils::fn_requires_monomorphization(did, self.tcx) {
136                        num_generic_api += 1;
137                    }
138                }
139                DepNode::Ty(_) => ty_cnt += 1,
140            }
141        }
142
143        for edge in self.graph.edge_indices() {
144            edge_cnt += 1;
145        }
146
147        Statistics {
148            num_api,
149            num_generic_api,
150            type_count: ty_cnt,
151            edge_cnt,
152        }
153    }
154
155    pub fn is_node_exist(&self, node: &DepNode<'tcx>) -> bool {
156        self.node_indices.contains_key(&node)
157    }
158
159    pub fn get_or_create_index(&mut self, node: DepNode<'tcx>) -> NodeIndex {
160        if let Some(node_index) = self.node_indices.get(&node) {
161            *node_index
162        } else {
163            let node_index = self.graph.add_node(node.clone());
164            self.node_indices.insert(node.clone(), node_index);
165            match node {
166                DepNode::Api(..) => {
167                    self.api_nodes.push(node_index);
168                }
169                DepNode::Ty(_) => {
170                    self.ty_nodes.push(node_index);
171                }
172                _ => {}
173            }
174            node_index
175        }
176    }
177
178    pub fn get_node_from_index(&self, index: NodeIndex) -> DepNode<'tcx> {
179        self.graph[index]
180    }
181
182    pub fn get_index_by_ty(&self, ty: Ty<'tcx>) -> Option<NodeIndex> {
183        let ty_wrapper = TyWrapper::from(ty);
184        self.get_index(DepNode::Ty(ty_wrapper))
185    }
186
187    pub fn get_index(&self, node: DepNode<'tcx>) -> Option<NodeIndex> {
188        self.node_indices.get(&node).map(|index| *index)
189    }
190
191    pub fn add_edge(&mut self, src: NodeIndex, dst: NodeIndex, edge: DepEdge) {
192        self.graph.add_edge(src, dst, edge);
193    }
194
195    pub fn add_edge_once(&mut self, src: NodeIndex, dst: NodeIndex, edge: DepEdge) {
196        if !self.graph.contains_edge(src, dst) {
197            self.graph.add_edge(src, dst, edge);
198        }
199    }
200
201    pub fn add_identity_api(&mut self, fn_did: DefId) -> bool {
202        let args = ty::GenericArgs::identity_for_item(self.tcx, fn_did);
203
204        if !self.add_api(fn_did, args) {
205            return false;
206        }
207
208        self.get_or_create_index(DepNode::api(fn_did, args));
209
210        true
211    }
212
213    /// return true if the api is added successfully, false if it already exists.
214    pub fn add_api(&mut self, fn_did: DefId, args: &[ty::GenericArg<'tcx>]) -> bool {
215        let node = DepNode::api(fn_did, self.tcx.mk_args(args));
216        if self.is_node_exist(&node) {
217            return false;
218        }
219        let api_node = self.get_or_create_index(node);
220
221        rap_trace!("[ApiDependencyGraph] add fn: {:?} args: {:?}", fn_did, args);
222
223        let fn_sig = utils::fn_sig_with_generic_args(fn_did, args, self.tcx);
224
225        // add inputs/output to graph, and compute constraints based on subtyping
226        for (no, input_ty) in fn_sig.inputs().iter().enumerate() {
227            let input_node = self.get_or_create_index(DepNode::ty(*input_ty));
228            self.add_edge(input_node, api_node, DepEdge::arg(no));
229        }
230
231        let output_ty = fn_sig.output();
232        let output_node = self.get_or_create_index(DepNode::ty(output_ty));
233        self.add_edge(api_node, output_node, DepEdge::ret());
234
235        true
236    }
237
238    /// return all transform kind for `ty` that we intersted in.
239    pub fn all_transforms(&self, ty: Ty<'tcx>) -> Vec<TransformKind> {
240        let mut tfs = Vec::new();
241        if let Some(index) = self.get_index(DepNode::Ty(ty.into())) {
242            for edge in self.graph.edges_directed(index, Direction::Outgoing) {
243                if let DepEdge::Transform(kind) = edge.weight() {
244                    tfs.push(*kind);
245                }
246            }
247        }
248        tfs
249    }
250
251    pub fn is_start_node_index(&self, index: NodeIndex) -> bool {
252        match self.graph[index] {
253            DepNode::Api(..) => self
254                .graph
255                .neighbors_directed(index, Direction::Incoming)
256                .next()
257                .is_none(),
258            DepNode::Ty(ty) => utils::is_fuzzable_ty(ty.into(), self.tcx),
259        }
260    }
261
262    pub fn depth_map(&self) -> HashMap<DepNode<'tcx>, usize> {
263        let mut map = HashMap::new();
264        let mut visited = BitSet::with_capacity(self.graph.node_count());
265
266        // initialize worklist with start node (indegree is zero)
267        let mut worklist = VecDeque::from_iter(self.graph.node_indices().filter(|index| {
268            let cond = self.is_start_node_index(*index);
269            if cond {
270                visited.insert(index.index());
271                map.insert(self.get_node_from_index(*index), 0);
272            }
273            cond
274        }));
275
276        rap_trace!("[depth_map] initial worklist = {:?}", worklist);
277
278        const LARGE_ENOUGH: usize = 0xffffffff;
279
280        // initialize queue with fuzzable type
281        while let Some(current) = worklist.pop_front() {
282            let node = self.get_node_from_index(current);
283
284            if !map.contains_key(&node) {
285                // depth: Ty = min(prev_ty), Api = sum(arg_ty) + 1
286                let depth = match node {
287                    DepNode::Ty(_) => self
288                        .graph
289                        .neighbors_directed(current, Direction::Incoming)
290                        .map(|prev| {
291                            let prev_node = &self.get_node_from_index(prev);
292                            map.get(prev_node).copied().unwrap_or(LARGE_ENOUGH)
293                        })
294                        .min()
295                        .unwrap_or(0),
296                    DepNode::Api(..) => {
297                        self.graph
298                            .neighbors_directed(current, Direction::Incoming)
299                            .map(|prev| {
300                                let prev_node = &self.get_node_from_index(prev);
301                                map.get(prev_node).copied().unwrap_or(LARGE_ENOUGH)
302                            })
303                            .sum::<usize>()
304                            + 1
305                    }
306                };
307                map.insert(node, depth);
308            }
309
310            for next in self.graph.neighbors(current) {
311                let is_reachable = match self.graph[next] {
312                    DepNode::Ty(_) => true,
313                    DepNode::Api(..) => self
314                        .graph
315                        .neighbors_directed(next, petgraph::Direction::Incoming)
316                        .all(|nbor| visited.contains(nbor.index())),
317                };
318
319                if is_reachable && visited.insert(next.index()) {
320                    rap_trace!("[depth_map] add {:?} to worklist", next);
321                    worklist.push_back(next);
322                }
323            }
324        }
325
326        map
327    }
328
329    pub fn traverse_covered_api_with(
330        &self,
331        f_cover: &mut impl FnMut(DefId),
332        f_total: &mut impl FnMut(DefId),
333    ) {
334        let mut visited = BitSet::with_capacity(self.graph.node_count());
335
336        for index in self.graph.node_indices() {
337            if let DepNode::Api(did, _) = self.graph[index] {
338                f_total(did);
339            }
340        }
341
342        // initialize worklist with start node (indegree is zero)
343        let mut worklist = VecDeque::from_iter(self.graph.node_indices().filter(|index| {
344            if self.is_start_node_index(*index) {
345                visited.insert(index.index());
346                true
347            } else {
348                false
349            }
350        }));
351
352        rap_trace!("[estimate_coverage] initial worklist = {:?}", worklist);
353
354        // initialize queue with fuzzable type
355        while let Some(index) = worklist.pop_front() {
356            if let DepNode::Api(did, args) = self.graph[index] {
357                f_cover(did);
358            }
359
360            for next in self.graph.neighbors(index) {
361                let is_reachable = match self.graph[next] {
362                    DepNode::Ty(_) => true,
363                    DepNode::Api(..) => self
364                        .graph
365                        .neighbors_directed(next, petgraph::Direction::Incoming)
366                        .all(|nbor| visited.contains(nbor.index())),
367                };
368                if is_reachable && visited.insert(next.index()) {
369                    rap_trace!("[traverse_covered_api] add {:?} to worklist", next);
370                    worklist.push_back(next);
371                }
372            }
373        }
374    }
375
376    fn recache(&mut self) {
377        self.node_indices.clear();
378        self.ty_nodes.clear();
379        self.api_nodes.clear();
380        for idx in self.graph.node_indices() {
381            let node = &self.graph[idx];
382            self.node_indices.insert(node.clone(), idx);
383            match node {
384                DepNode::Api(..) => self.api_nodes.push(idx),
385                DepNode::Ty(..) => self.ty_nodes.push(idx),
386                _ => {}
387            }
388        }
389    }
390
391    pub fn uncovered_api(&self) -> Vec<DefId> {
392        let mut covered = HashSet::new();
393        let mut total = HashSet::new();
394        self.traverse_covered_api_with(
395            &mut |did| {
396                covered.insert(did);
397            },
398            &mut |did| {
399                total.insert(did);
400            },
401        );
402        total.difference(&covered).copied().collect()
403    }
404
405    /// `estimate_coverage` treat each API as the distinct API.
406    /// For example, if `foo<T>`, `foo<U>` are covered, this API return (2, 2).
407    pub fn estimate_coverage(&self) -> (usize, usize) {
408        let mut num_total = 0;
409        let mut num_estimate = 0;
410        self.traverse_covered_api_with(
411            &mut |did| {
412                num_estimate += 1;
413            },
414            &mut |did| {
415                num_total += 1;
416            },
417        );
418        (num_estimate, num_total)
419    }
420
421    /// `estimate_coverage_distinct` treat mono API as the original generic API.
422    /// For example, if `foo<T>`, `foo<U>` are covered, this API return (1, 1).
423    pub fn estimate_coverage_distinct(&self) -> (usize, usize) {
424        let mut total = HashSet::new();
425        let mut estimate = HashSet::new();
426        self.traverse_covered_api_with(
427            &mut |did| {
428                estimate.insert(did);
429            },
430            &mut |did| {
431                total.insert(did);
432            },
433        );
434        (estimate.len(), total.len())
435    }
436
437    pub fn dump_apis<P: AsRef<Path>>(&self, path: P) {
438        let tcx = self.tcx;
439        let mut file = rap_create_file(path, "can not create api file");
440
441        self.graph
442            .node_indices()
443            .for_each(|index| match self.graph[index] {
444                DepNode::Api(did, args) => {
445                    writeln!(
446                        file,
447                        "API,\t{},\tis_fuzzable = {}",
448                        tcx.def_path_str_with_args(did, args),
449                        utils::is_fuzzable_api(did, args, tcx)
450                    )
451                    .expect("fail when writing data to api file");
452                }
453                DepNode::Ty(ty) => {
454                    let ty = ty.ty();
455                    writeln!(
456                        file,
457                        "TYPE,\t{},\tis_fuzzable = {}",
458                        ty,
459                        is_fuzzable_ty(ty, tcx)
460                    )
461                    .expect("fail when writing data to api file");
462                }
463            });
464    }
465}
rapx/analysis/core/api_dependency/graph/mod.rs

rapx/analysis/core/api_dependency/graph/
mod.rs
