rapx/check/opt/memory_cloning/
hash_key_cloning.rs

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

rapx/check/opt/memory_cloning/
hash_key_cloning.rs
