rapx/check/opt/checking/bounds_checking/
bounds_len.rs

1use std::collections::HashSet;
2
3use once_cell::sync::OnceCell;
4
5use rustc_ast::BinOpKind;
6use rustc_hir::{Expr, ExprKind, intravisit};
7use rustc_middle::{mir::Local, ty::TyCtxt};
8use rustc_span::Span;
9
10use crate::{
11    analysis::dataflow::*,
12    helpers::def_path::DefPath,
13    utils::log::{relative_pos_range, span_to_filename, span_to_line_number, span_to_source_code},
14};
15use annotate_snippets::{Level, Renderer, Snippet};
16
17use super::super::super::NO_STD;
18
19static DEFPATHS: OnceCell<DefPaths> = OnceCell::new();
20
21struct DefPaths {
22    ops_range: DefPath,
23    vec_len: DefPath,
24    slice_len: DefPath,
25    ops_index: DefPath,
26    ops_index_mut: DefPath,
27}
28
29impl DefPaths {
30    pub fn new(tcx: &TyCtxt<'_>) -> Self {
31        let no_std = NO_STD.lock().unwrap();
32        if *no_std {
33            Self {
34                ops_range: DefPath::new("core::ops::Range", tcx),
35                vec_len: DefPath::new("alloc::vec::Vec::len", tcx),
36                slice_len: DefPath::new("core::slice::len", tcx),
37                ops_index: DefPath::new("core::ops::Index::index", tcx),
38                ops_index_mut: DefPath::new("core::ops::IndexMut::index_mut", tcx),
39            }
40        } else {
41            Self {
42                ops_range: DefPath::new("std::ops::Range", tcx),
43                vec_len: DefPath::new("std::vec::Vec::len", tcx),
44                slice_len: DefPath::new("slice::len", tcx),
45                ops_index: DefPath::new("std::ops::Index::index", tcx),
46                ops_index_mut: DefPath::new("std::ops::IndexMut::index_mut", tcx),
47            }
48        }
49    }
50}
51
52use crate::check::opt::OptCheck;
53
54pub struct BoundsLenCheck {
55    pub record: Vec<(Local, Vec<Local>)>,
56}
57
58struct IfFinder {
59    record: Vec<(Span, Vec<Span>)>,
60}
61struct LtFinder {
62    record: Vec<Span>,
63}
64struct IndexFinder {
65    record: Vec<Span>,
66}
67
68impl intravisit::Visitor<'_> for LtFinder {
69    fn visit_expr(&mut self, ex: &Expr) {
70        if let ExprKind::Binary(op, ..) = ex.kind {
71            if op.node == BinOpKind::Lt {
72                self.record.push(ex.span);
73            }
74        }
75        intravisit::walk_expr(self, ex);
76    }
77}
78
79impl<'tcx> intravisit::Visitor<'tcx> for IfFinder {
80    fn visit_expr(&mut self, ex: &'tcx Expr<'tcx>) {
81        if let ExprKind::If(cond, e1, _) = ex.kind {
82            let mut lt_finder = LtFinder { record: vec![] };
83            intravisit::walk_expr(&mut lt_finder, cond);
84            if !lt_finder.record.is_empty() {
85                let mut index_finder = IndexFinder { record: vec![] };
86                intravisit::walk_expr(&mut index_finder, e1);
87                if !index_finder.record.is_empty() {
88                    self.record.push((lt_finder.record[0], index_finder.record));
89                }
90            }
91        }
92        intravisit::walk_expr(self, ex);
93    }
94}
95
96impl<'tcx> intravisit::Visitor<'tcx> for IndexFinder {
97    fn visit_expr(&mut self, ex: &'tcx Expr<'tcx>) {
98        if let ExprKind::Index(_, ex2, _) = ex.kind {
99            self.record.push(ex2.span);
100        }
101        intravisit::walk_expr(self, ex);
102    }
103}
104
105impl OptCheck for BoundsLenCheck {
106    fn new() -> Self {
107        Self { record: vec![] }
108    }
109
110    fn check(&mut self, graph: &Graph, tcx: &TyCtxt) {
111        let _ = &DEFPATHS.get_or_init(|| DefPaths::new(tcx));
112        for (node_idx, node) in graph.nodes.iter_enumerated() {
113            if let Some(upperbound_node_idx) = extract_upperbound_node_if_ops_range(graph, node) {
114                if let Some(vec_len_node_idx) = find_upside_len_node(graph, upperbound_node_idx) {
115                    let maybe_vec_node_idx = graph.get_upside_idx(vec_len_node_idx, 0).unwrap();
116                    let maybe_vec_node_idxs =
117                        graph.collect_equivalent_locals(maybe_vec_node_idx, true);
118                    let mut index_record = vec![];
119                    for index_node_idx in find_downside_index_node(graph, node_idx).into_iter() {
120                        let maybe_vec_node_idx = graph.get_upside_idx(index_node_idx, 0).unwrap();
121                        if maybe_vec_node_idxs.contains(&maybe_vec_node_idx) {
122                            index_record.push(index_node_idx);
123                        }
124                    }
125                    if !index_record.is_empty() {
126                        self.record.push((upperbound_node_idx, index_record));
127                    }
128                }
129            }
130        }
131        let def_id = graph.def_id;
132        let body = tcx.hir_body_owned_by(def_id.as_local().unwrap());
133        let mut if_finder = IfFinder { record: vec![] };
134        intravisit::walk_body(&mut if_finder, body);
135        for (cond, slice_index_record) in if_finder.record.iter() {
136            if let Some((node_idx, node)) = graph.query_node_by_span(*cond, true) {
137                let left_arm = graph.edges[node.in_edges[0]].src;
138                let right_arm = graph.edges[node.in_edges[1]].src;
139                if find_upside_len_node(graph, right_arm).is_some() {
140                    let index_set = graph.collect_ancestor_locals(left_arm, true);
141                    let len_set = graph.collect_ancestor_locals(right_arm, true);
142                    let mut slice_node_indice = vec![];
143                    for slice_index_idx in slice_index_record {
144                        if let Some((index_node_idx, _)) =
145                            graph.query_node_by_span(*slice_index_idx, true)
146                        {
147                            let index_ancestors =
148                                graph.collect_ancestor_locals(index_node_idx, true);
149                            let indexed_node_idx =
150                                find_indexed_node_from_index(graph, index_node_idx);
151                            if let Some(indexed_node_idx) = indexed_node_idx {
152                                let indexed_ancestors =
153                                    graph.collect_ancestor_locals(indexed_node_idx, true);
154                                // Warning: We only checks index without checking the indexed value
155                                if index_ancestors.intersection(&index_set).next().is_some()
156                                    && indexed_ancestors.intersection(&len_set).next().is_some()
157                                {
158                                    slice_node_indice.push(index_node_idx);
159                                }
160                            }
161                        }
162                    }
163                    self.record.push((node_idx, slice_node_indice));
164                }
165            }
166        }
167    }
168
169    fn report(&self, graph: &Graph) {
170        for (upperbound_node_idx, index_record) in self.record.iter() {
171            report_upperbound_bug(graph, *upperbound_node_idx, index_record);
172        }
173    }
174
175    fn cnt(&self) -> usize {
176        self.record.iter().map(|(_, spans)| spans.len()).sum()
177    }
178}
179
180fn find_indexed_node_from_index(graph: &Graph, index_node_idx: Local) -> Option<Local> {
181    let def_paths = &DEFPATHS.get().unwrap();
182    let index_node = &graph.nodes[index_node_idx];
183    for edge_idx in index_node.out_edges.iter() {
184        let dst_node_idx = graph.edges[*edge_idx].dst;
185        let dst_node = &graph.nodes[dst_node_idx];
186        for op in dst_node.ops.iter() {
187            if let NodeOp::Call(def_id) = op {
188                if *def_id == def_paths.ops_index.last_def_id()
189                    || *def_id == def_paths.ops_index_mut.last_def_id()
190                {
191                    let index_operator_node =
192                        &graph.nodes[graph.edges[index_node.out_edges[0]].dst];
193
194                    return Some(graph.edges[index_operator_node.in_edges[0]].src);
195                }
196            }
197            if graph.is_marker(dst_node_idx) {
198                for edge_idx_ in dst_node.in_edges.iter() {
199                    let edge = &graph.edges[*edge_idx_];
200                    if let EdgeOp::Index = edge.op {
201                        return Some(edge.src);
202                    }
203                }
204            }
205        }
206    }
207    None
208}
209
210fn extract_upperbound_node_if_ops_range(graph: &Graph, node: &GraphNode) -> Option<Local> {
211    let def_paths = &DEFPATHS.get().unwrap();
212    let target_def_id = def_paths.ops_range.last_def_id();
213    for op in node.ops.iter() {
214        if let NodeOp::Aggregate(AggKind::Adt(def_id)) = op {
215            if *def_id == target_def_id {
216                let upperbound_edge = &graph.edges[node.in_edges[1]]; // the second field
217                return Some(upperbound_edge.src);
218            }
219        }
220    }
221    None
222}
223
224fn find_upside_len_node(graph: &Graph, node_idx: Local) -> Option<Local> {
225    let mut len_node_idx = None;
226    let def_paths = &DEFPATHS.get().unwrap();
227    // Warning: may traverse all upside nodes and the new result will overwrite on the previous result
228    let mut node_operator = |graph: &Graph, idx: Local| -> DFSStatus {
229        let node = &graph.nodes[idx];
230        for op in node.ops.iter() {
231            if let NodeOp::Call(def_id) = op {
232                if *def_id == def_paths.vec_len.last_def_id()
233                    || *def_id == def_paths.slice_len.last_def_id()
234                {
235                    len_node_idx = Some(idx);
236                    return DFSStatus::Stop;
237                }
238            }
239        }
240        DFSStatus::Continue
241    };
242    let mut seen = HashSet::new();
243    graph.dfs(
244        node_idx,
245        Direction::Upside,
246        &mut node_operator,
247        &mut Graph::equivalent_edge_validator,
248        false,
249        &mut seen,
250    );
251    len_node_idx
252}
253
254fn find_downside_index_node(graph: &Graph, node_idx: Local) -> Vec<Local> {
255    let mut index_node_idxs: Vec<Local> = vec![];
256    let def_paths = &DEFPATHS.get().unwrap();
257    // Warning: traverse all downside nodes
258    let mut node_operator = |graph: &Graph, idx: Local| -> DFSStatus {
259        let node = &graph.nodes[idx];
260        for op in node.ops.iter() {
261            if let NodeOp::Call(def_id) = op {
262                if *def_id == def_paths.ops_index.last_def_id()
263                    || *def_id == def_paths.ops_index_mut.last_def_id()
264                {
265                    index_node_idxs.push(idx);
266                    break;
267                }
268            }
269        }
270        DFSStatus::Continue
271    };
272    let mut seen = HashSet::new();
273    graph.dfs(
274        node_idx,
275        Direction::Downside,
276        &mut node_operator,
277        &mut Graph::always_true_edge_validator,
278        true,
279        &mut seen,
280    );
281    index_node_idxs
282}
283
284fn report_upperbound_bug(graph: &Graph, upperbound_node_idx: Local, index_record: &Vec<Local>) {
285    let upperbound_span = graph.nodes[upperbound_node_idx].span;
286    let code_source = span_to_source_code(graph.span);
287    let filename = span_to_filename(upperbound_span);
288    let mut snippet = Snippet::source(&code_source)
289        .line_start(span_to_line_number(graph.span))
290        .origin(&filename)
291        .fold(true)
292        .annotation(
293            Level::Info
294                .span(relative_pos_range(graph.span, upperbound_span))
295                .label("Index is upperbounded."),
296        );
297    for node_idx in index_record {
298        let index_span = graph.nodes[*node_idx].span;
299        snippet = snippet.annotation(
300            Level::Error
301                .span(relative_pos_range(graph.span, index_span))
302                .label("Checked here."),
303        );
304    }
305    let message = Level::Warning
306        .title("Unnecessary bounds checkings detected")
307        .snippet(snippet)
308        .footer(Level::Help.title("Use unsafe APIs instead."));
309    let renderer = Renderer::styled();
310    rap_warn!("{}", renderer.render(message));
311}
rapx/check/opt/checking/bounds_checking/bounds_len.rs

rapx/check/opt/checking/bounds_checking/
bounds_len.rs
