rapx/analysis/opt/memory_cloning/
hash_key_cloning.rs

1use annotate_snippets::Level;
2use annotate_snippets::Renderer;
3use annotate_snippets::Snippet;
4use once_cell::sync::OnceCell;
5
6use crate::analysis::core::dataflow::graph::DFSStatus;
7use crate::analysis::core::dataflow::graph::Direction;
8use crate::analysis::opt::OptCheck;
9use rustc_hir::{intravisit, Expr, ExprKind};
10use rustc_middle::mir::Local;
11use rustc_middle::ty::{TyCtxt, TypeckResults};
12use rustc_span::Span;
13use std::collections::HashSet;
14static DEFPATHS: OnceCell<DefPaths> = OnceCell::new();
15
16use crate::analysis::core::dataflow::graph::Graph;
17use crate::analysis::core::dataflow::graph::GraphNode;
18use crate::analysis::core::dataflow::graph::NodeOp;
19use crate::analysis::utils::def_path::DefPath;
20use crate::utils::log::{
21    relative_pos_range, span_to_filename, span_to_line_number, span_to_source_code,
22};
23
24struct DefPaths {
25    hashset_insert: DefPath,
26    hashmap_insert: DefPath,
27    hashset_new: DefPath,
28    hashmap_new: DefPath,
29    hashset_with: DefPath,
30    hashmap_with: DefPath,
31    clone: DefPath,
32}
33
34impl DefPaths {
35    pub fn new(tcx: &TyCtxt<'_>) -> Self {
36        Self {
37            hashset_insert: DefPath::new("std::collections::HashSet::insert", tcx),
38            hashmap_insert: DefPath::new("std::collections::HashMap::insert", tcx),
39            hashset_new: DefPath::new("std::collections::HashSet::new", tcx),
40            hashset_with: DefPath::new("std::collections::HashSet::with_capacity", tcx),
41            hashmap_new: DefPath::new("std::collections::HashMap::new", tcx),
42            hashmap_with: DefPath::new("std::collections::HashMap::with_capacity", tcx),
43            clone: DefPath::new("std::clone::Clone::clone", tcx),
44        }
45    }
46}
47
48struct HashInsertFinder<'tcx> {
49    typeck_results: &'tcx TypeckResults<'tcx>,
50    record: HashSet<Span>,
51}
52
53impl<'tcx> intravisit::Visitor<'tcx> for HashInsertFinder<'tcx> {
54    fn visit_expr(&mut self, ex: &'tcx Expr<'tcx>) {
55        if let ExprKind::MethodCall(..) = ex.kind {
56            let def_id = self
57                .typeck_results
58                .type_dependent_def_id(ex.hir_id)
59                .unwrap();
60            if def_id == DEFPATHS.get().unwrap().hashset_insert.last_def_id()
61                || def_id == DEFPATHS.get().unwrap().hashmap_insert.last_def_id()
62            {
63                self.record.insert(ex.span);
64            }
65        }
66        intravisit::walk_expr(self, ex);
67    }
68}
69
70// check that the param of insert is moved from a cloned value
71fn find_first_param_upside_clone(graph: &Graph, node: &GraphNode) -> Option<Local> {
72    let mut clone_node_idx = None;
73    let def_paths = &DEFPATHS.get().unwrap();
74    let target_def_id = def_paths.clone.last_def_id();
75    let mut node_operator = |graph: &Graph, idx: Local| -> DFSStatus {
76        let node = &graph.nodes[idx];
77        for op in node.ops.iter() {
78            if let NodeOp::Call(def_id) = op {
79                if *def_id == target_def_id {
80                    clone_node_idx = Some(idx);
81                    return DFSStatus::Stop;
82                }
83            }
84        }
85        DFSStatus::Continue
86    };
87    let mut seen = HashSet::new();
88    graph.dfs(
89        graph.edges[node.in_edges[1]].src, // the first param is self, so we use 1
90        Direction::Upside,
91        &mut node_operator,
92        &mut Graph::equivalent_edge_validator,
93        false,
94        &mut seen,
95    );
96    clone_node_idx
97}
98
99// find the upside "new" node or "with_capacity" node of the "insert" node if it exists
100fn find_hash_new_node(graph: &Graph, node: &GraphNode) -> Option<Local> {
101    let mut new_node_idx = None;
102    let def_paths = &DEFPATHS.get().unwrap();
103    let mut node_operator = |graph: &Graph, idx: Local| -> DFSStatus {
104        let node = &graph.nodes[idx];
105        for op in node.ops.iter() {
106            if let NodeOp::Call(def_id) = op {
107                if *def_id == def_paths.hashset_new.last_def_id()
108                    || *def_id == def_paths.hashmap_new.last_def_id()
109                    || *def_id == def_paths.hashset_with.last_def_id()
110                    || *def_id == def_paths.hashmap_with.last_def_id()
111                {
112                    new_node_idx = Some(idx);
113                    return DFSStatus::Stop;
114                }
115            }
116        }
117        DFSStatus::Continue
118    };
119    let mut seen = HashSet::new();
120    graph.dfs(
121        graph.edges[node.in_edges[0]].src, // the first param is self
122        Direction::Upside,
123        &mut node_operator,
124        &mut Graph::equivalent_edge_validator,
125        false,
126        &mut seen,
127    );
128    new_node_idx
129}
130
131fn report_hash_key_cloning(graph: &Graph, clone_span: Span, insert_span: Span) {
132    let code_source = span_to_source_code(graph.span);
133    let filename = span_to_filename(clone_span);
134    let snippet = Snippet::source(&code_source)
135        .line_start(span_to_line_number(graph.span))
136        .origin(&filename)
137        .fold(true)
138        .annotation(
139            Level::Error
140                .span(relative_pos_range(graph.span, clone_span))
141                .label("Cloning happens here."),
142        )
143        .annotation(
144            Level::Error
145                .span(relative_pos_range(graph.span, insert_span))
146                .label("Used here."),
147        );
148    let message = Level::Warning
149        .title("Unnecessary memory cloning detected")
150        .snippet(snippet)
151        .footer(Level::Help.title("Use borrowings as keys."));
152    let renderer = Renderer::styled();
153    println!("{}", renderer.render(message));
154}
155
156pub struct HashKeyCloningCheck {
157    record: Vec<(Span, Span)>,
158}
159
160impl OptCheck for HashKeyCloningCheck {
161    fn new() -> Self {
162        Self { record: Vec::new() }
163    }
164
165    fn check(&mut self, graph: &Graph, tcx: &TyCtxt) {
166        let _ = &DEFPATHS.get_or_init(|| DefPaths::new(tcx));
167        let def_id = graph.def_id;
168        let body = tcx.hir_body_owned_by(def_id.as_local().unwrap());
169        let typeck_results = tcx.typeck(def_id.as_local().unwrap());
170        let mut hash_finder = HashInsertFinder {
171            typeck_results,
172            record: HashSet::new(),
173        };
174        intravisit::walk_body(&mut hash_finder, body);
175        for node in graph.nodes.iter() {
176            if hash_finder.record.contains(&node.span) {
177                if let Some(clone_node_idx) = find_first_param_upside_clone(graph, node) {
178                    if let Some(new_node_idx) = find_hash_new_node(graph, node) {
179                        if !graph.is_connected(new_node_idx, Local::from_usize(0)) {
180                            let clone_span = graph.nodes[clone_node_idx].span;
181                            self.record.push((clone_span, node.span));
182                        }
183                    }
184                }
185            }
186        }
187    }
188
189    fn report(&self, graph: &Graph) {
190        for (clone_span, insert_span) in self.record.iter() {
191            report_hash_key_cloning(graph, *clone_span, *insert_span);
192        }
193    }
194
195    fn cnt(&self) -> usize {
196        self.record.len()
197    }
198}
rapx/analysis/opt/memory_cloning/hash_key_cloning.rs

rapx/analysis/opt/memory_cloning/
hash_key_cloning.rs
