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

1pub mod avail;
2pub mod dep_edge;
3pub mod dep_node;
4mod resolve;
5mod serialize;
6pub mod transform;
7mod ty_wrapper;
8
9use super::utils;
10use super::visitor::FnVisitor;
11use super::Config;
12use crate::analysis::utils::def_path::path_str_def_id;
13use crate::rap_debug;
14use crate::rap_trace;
15use crate::utils::fs::rap_create_file;
16pub use dep_edge::DepEdge;
17pub use dep_node::{desc_str, DepNode};
18use petgraph::dot;
19use petgraph::graph::NodeIndex;
20use petgraph::visit::EdgeRef;
21use petgraph::Direction;
22use petgraph::Graph;
23use rustc_hir::def_id::DefId;
24use rustc_middle::ty::Binder;
25use rustc_middle::ty::{self, Ty, TyCtxt};
26use std::collections::HashMap;
27use std::collections::HashSet;
28use std::collections::VecDeque;
29use std::hash::Hash;
30use std::io::Write;
31use std::path::Path;
32pub use transform::TransformKind;
33pub use ty_wrapper::TyWrapper;
34
35type InnerGraph<'tcx> = Graph<DepNode<'tcx>, DepEdge>;
36
37#[derive(Clone)]
38pub struct ApiDependencyGraph<'tcx> {
39    graph: InnerGraph<'tcx>,
40    node_indices: HashMap<DepNode<'tcx>, NodeIndex>,
41    ty_nodes: Vec<NodeIndex>,
42    api_nodes: Vec<NodeIndex>,
43    all_apis: HashSet<DefId>,
44    tcx: TyCtxt<'tcx>,
45}
46
47pub struct Statistics {
48    pub api_count: usize,
49    pub type_count: usize,
50    pub edge_cnt: usize,
51}
52
53impl<'tcx> ApiDependencyGraph<'tcx> {
54    pub fn new(tcx: TyCtxt<'tcx>) -> ApiDependencyGraph<'tcx> {
55        ApiDependencyGraph {
56            graph: Graph::new(),
57            node_indices: HashMap::new(),
58            ty_nodes: Vec::new(),
59            api_nodes: Vec::new(),
60            tcx,
61            all_apis: HashSet::new(),
62        }
63    }
64
65    pub fn num_api(&self) -> usize {
66        self.api_nodes.len()
67    }
68
69    pub fn num_ty(&self) -> usize {
70        self.ty_nodes.len()
71    }
72
73    pub fn api_at(&self, idx: usize) -> (DefId, ty::GenericArgsRef<'tcx>) {
74        let index = self.api_nodes[idx];
75        self.graph[index].expect_api()
76    }
77
78    fn tcx(&self) -> TyCtxt<'tcx> {
79        self.tcx
80    }
81
82    pub fn build(&mut self, config: Config) {
83        let tcx = self.tcx();
84        let mut fn_visitor = FnVisitor::new(self, config, tcx);
85
86        // 1. collect APIs
87        tcx.hir_visit_all_item_likes_in_crate(&mut fn_visitor);
88        self.all_apis = fn_visitor.apis().into_iter().collect();
89        // add auxillary API from std
90        // self.add_auxiliary_api();
91
92        // 2. resolve generic API to monomorphic API
93        if config.resolve_generic {
94            self.resolve_generic_api();
95        } else {
96            self.update_transform_edges();
97        }
98    }
99
100    pub fn inner_graph(&self) -> &InnerGraph<'tcx> {
101        &self.graph
102    }
103
104    pub fn statistics(&self) -> Statistics {
105        let mut api_cnt = 0;
106        let mut ty_cnt = 0;
107        let mut edge_cnt = 0;
108
109        for node in self.graph.node_indices() {
110            match self.graph[node] {
111                DepNode::Api(..) => api_cnt += 1,
112                DepNode::Ty(_) => ty_cnt += 1,
113            }
114        }
115
116        for edge in self.graph.edge_indices() {
117            edge_cnt += 1;
118        }
119
120        Statistics {
121            api_count: api_cnt,
122            type_count: ty_cnt,
123            edge_cnt,
124        }
125    }
126
127    pub fn is_node_exist(&self, node: &DepNode<'tcx>) -> bool {
128        self.node_indices.contains_key(&node)
129    }
130
131    pub fn get_or_create_index(&mut self, node: DepNode<'tcx>) -> NodeIndex {
132        if let Some(node_index) = self.node_indices.get(&node) {
133            *node_index
134        } else {
135            let node_index = self.graph.add_node(node.clone());
136            self.node_indices.insert(node.clone(), node_index);
137            match node {
138                DepNode::Api(..) => {
139                    self.api_nodes.push(node_index);
140                }
141                DepNode::Ty(_) => {
142                    self.ty_nodes.push(node_index);
143                }
144                _ => {}
145            }
146            node_index
147        }
148    }
149
150    pub fn get_index(&self, node: DepNode<'tcx>) -> Option<NodeIndex> {
151        self.node_indices.get(&node).map(|index| *index)
152    }
153
154    pub fn add_edge(&mut self, src: NodeIndex, dst: NodeIndex, edge: DepEdge) {
155        self.graph.add_edge(src, dst, edge);
156    }
157
158    pub fn add_edge_once(&mut self, src: NodeIndex, dst: NodeIndex, edge: DepEdge) {
159        if !self.graph.contains_edge(src, dst) {
160            self.graph.add_edge(src, dst, edge);
161        }
162    }
163
164    pub fn add_generic_api(&mut self, fn_did: DefId) -> bool {
165        let args = ty::GenericArgs::identity_for_item(self.tcx, fn_did);
166
167        if !self.add_api(fn_did, args) {
168            return false;
169        }
170
171        let api_node = self.get_or_create_index(DepNode::api(fn_did, args));
172        let binder_fn_sig = self.tcx.fn_sig(fn_did).instantiate_identity();
173
174        true
175    }
176
177    /// return true if the api is added successfully, false if it already exists.
178    pub fn add_api(&mut self, fn_did: DefId, args: &[ty::GenericArg<'tcx>]) -> bool {
179        let node = DepNode::api(fn_did, self.tcx.mk_args(args));
180        if self.is_node_exist(&node) {
181            return false;
182        }
183        let api_node = self.get_or_create_index(node);
184
185        rap_trace!("[ApiDependencyGraph] add fn: {:?} args: {:?}", fn_did, args);
186
187        let fn_sig = utils::fn_sig_with_generic_args(fn_did, args, self.tcx);
188
189        // add inputs/output to graph, and compute constraints based on subtyping
190        for (no, input_ty) in fn_sig.inputs().iter().enumerate() {
191            let input_node = self.get_or_create_index(DepNode::ty(*input_ty));
192            self.add_edge(input_node, api_node, DepEdge::arg(no));
193        }
194
195        let output_ty = fn_sig.output();
196        let output_node = self.get_or_create_index(DepNode::ty(output_ty));
197        self.add_edge(api_node, output_node, DepEdge::ret());
198
199        true
200    }
201
202    /// return all transform kind for `ty` that we intersted in.
203    pub fn all_transforms(&self, ty: Ty<'tcx>) -> Vec<TransformKind> {
204        let mut tfs = Vec::new();
205        if let Some(index) = self.get_index(DepNode::Ty(ty.into())) {
206            for edge in self.graph.edges_directed(index, Direction::Outgoing) {
207                if let DepEdge::Transform(kind) = edge.weight() {
208                    tfs.push(*kind);
209                }
210            }
211        }
212        tfs
213    }
214
215    pub fn is_start_node_index(&self, index: NodeIndex) -> bool {
216        match self.graph[index] {
217            DepNode::Api(..) => self
218                .graph
219                .neighbors_directed(index, Direction::Incoming)
220                .next()
221                .is_none(),
222            DepNode::Ty(ty) => utils::is_fuzzable_ty(ty.into(), self.tcx),
223        }
224    }
225
226    pub fn estimate_coverage_with(
227        &self,
228        tcx: TyCtxt<'tcx>,
229        f_cover: &mut impl FnMut(DefId),
230        f_total: &mut impl FnMut(DefId),
231    ) {
232        let mut reachable = vec![false; self.graph.node_count()];
233
234        for index in self.graph.node_indices() {
235            if let DepNode::Api(did, _) = self.graph[index] {
236                f_total(did);
237            }
238        }
239
240        // initialize worklist with start node (indegree is zero)
241        let mut worklist = VecDeque::from_iter(self.graph.node_indices().filter(|index| {
242            if self.is_start_node_index(*index) {
243                reachable[index.index()] = true;
244                true
245            } else {
246                false
247            }
248        }));
249
250        rap_trace!("[estimate_coverage] initial worklist = {:?}", worklist);
251
252        // initialize queue with fuzzable type
253        while let Some(index) = worklist.pop_front() {
254            if let DepNode::Api(did, args) = self.graph[index] {
255                f_cover(did);
256            }
257
258            for next in self.graph.neighbors(index) {
259                if reachable[next.index()] {
260                    continue;
261                }
262                if match self.graph[next] {
263                    DepNode::Ty(_) => true,
264                    DepNode::Api(..) => {
265                        if self
266                            .graph
267                            .neighbors_directed(next, petgraph::Direction::Incoming)
268                            .all(|nbor| reachable[nbor.index()])
269                        {
270                            true
271                        } else {
272                            false
273                        }
274                    }
275                } {
276                    // rap_trace!("[estimate_coverage] add {:?} to worklist", next);
277                    reachable[next.index()] = true;
278                    worklist.push_back(next);
279                }
280            }
281        }
282    }
283
284    /// `estimate_coverage` treat each API as the distinct API.
285    /// For example, if `foo<T>`, `foo<U>` are covered, this API return (2, 2).
286    pub fn estimate_coverage(&mut self) -> (usize, usize) {
287        let mut num_total = 0;
288        let mut num_estimate = 0;
289        self.estimate_coverage_with(
290            self.tcx,
291            &mut |did| {
292                num_estimate += 1;
293            },
294            &mut |did| {
295                num_total += 1;
296            },
297        );
298        (num_estimate, num_total)
299    }
300
301    /// `estimate_coverage_distinct` treat mono API as the original generic API.
302    /// For example, if `foo<T>`, `foo<U>` are covered, this API return (1, 1).
303    pub fn estimate_coverage_distinct(&mut self) -> (usize, usize) {
304        let mut total = HashSet::new();
305        let mut estimate = HashSet::new();
306        self.estimate_coverage_with(
307            self.tcx,
308            &mut |did| {
309                estimate.insert(did);
310            },
311            &mut |did| {
312                total.insert(did);
313            },
314        );
315        (estimate.len(), total.len())
316    }
317
318    pub fn dump_to_dot<P: AsRef<Path>>(&self, path: P, tcx: TyCtxt<'tcx>) {
319        let get_edge_attr =
320            |graph: &Graph<DepNode<'tcx>, DepEdge>,
321             edge_ref: petgraph::graph::EdgeReference<DepEdge>| {
322                let color = match edge_ref.weight() {
323                    DepEdge::Arg(_) | DepEdge::Ret => "black",
324                    DepEdge::Transform(_) => "darkorange",
325                };
326                format!("label=\"{}\", color = {}", edge_ref.weight(), color)
327            };
328        let get_node_attr = |graph: &Graph<DepNode<'tcx>, DepEdge>,
329                             node_ref: (NodeIndex, &DepNode<'tcx>)| {
330            format!("label={:?}, ", desc_str(node_ref.1.clone(), tcx))
331                + match node_ref.1 {
332                    DepNode::Api(..) => "color = blue",
333                    DepNode::Ty(_) => "color = red",
334                }
335                + ", shape=box"
336        };
337
338        let dot = dot::Dot::with_attr_getters(
339            &self.graph,
340            &[dot::Config::NodeNoLabel, dot::Config::EdgeNoLabel],
341            &get_edge_attr,
342            &get_node_attr,
343        );
344        let mut file = rap_create_file(path, "can not create dot file");
345        write!(&mut file, "{:?}", dot).expect("fail when writing data to dot file");
346        // println!("{:?}", dot);
347    }
348}
rapx/analysis/core/api_dependency/graph/mod.rs

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