rapx/analysis/opt/memory_cloning/
hash_key_cloning.rs

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

rapx/analysis/opt/memory_cloning/
hash_key_cloning.rs
