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

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

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