1use std::collections::HashSet;
4
5use rustc_hir::def_id::DefId;
6use rustc_middle::{
7 mir::{BinOp, Body, Local, Operand, Rvalue, StatementKind, TerminatorKind},
8 ty::{TyCtxt, TypingEnv},
9};
10
11use crate::{
12 def_ids::{intrinsic_api, other_api},
13 util::mir_utils,
14};
15
16#[derive(Clone, Copy, Debug, PartialEq, Eq)]
17pub(crate) enum PointerOffsetDirection {
18 Forward,
19 Backward,
20}
21
22#[derive(Clone, Copy, PartialEq, Eq)]
23struct PointerOffset {
24 base: usize,
25 count: Option<usize>,
26 direction: PointerOffsetDirection,
27}
28
29pub(crate) fn pointer_offset_direction(
32 tcx: TyCtxt<'_>,
33 callee: DefId,
34) -> Option<PointerOffsetDirection> {
35 let offset = pointer_offset(tcx, callee, 6)?;
36 (offset.base == 0 && offset.count == Some(1)).then_some(offset.direction)
37}
38
39fn pointer_offset(tcx: TyCtxt<'_>, callee: DefId, depth: usize) -> Option<PointerOffset> {
40 if depth == 0 || !tcx.is_mir_available(callee) {
41 return None;
42 }
43 let body = tcx.optimized_mir(callee);
44 let pointee = body
45 .local_decls
46 .get(Local::from_usize(1))
47 .and_then(|decl| mir_utils::pointee_ty(decl.ty));
48 let mut zst_switches = Vec::new();
49 let mut ub_switches = Vec::new();
50 let only_zst_or_ub_switches = body.basic_blocks.iter_enumerated().all(|(bb, block)| {
51 let TerminatorKind::SwitchInt { discr, .. } = &block.terminator().kind else {
52 return true;
53 };
54 if zst_property_operand(tcx, body, discr, pointee) {
55 zst_switches.push(bb);
56 true
57 } else if ub_check_result_operand(tcx, body, discr) {
58 ub_switches.push(bb);
59 true
60 } else {
61 false
62 }
63 });
64 let ub_checks_precede_zst = if ub_switches.is_empty() {
65 true
66 } else if let [zst_bb] = zst_switches.as_slice() {
67 let dominators = body.basic_blocks.dominators();
68 ub_switches
69 .iter()
70 .all(|&bb| dominators.dominates(bb, *zst_bb))
71 && body
72 .basic_blocks
73 .iter_enumerated()
74 .filter(|(_, block)| matches!(block.terminator().kind, TerminatorKind::Return))
75 .all(|(bb, _)| dominators.dominates(*zst_bb, bb))
76 } else {
77 false
78 };
79 let zst_branch = !zst_switches.is_empty() && only_zst_or_ub_switches && ub_checks_precede_zst;
80 trace_pointer_offset(
81 tcx,
82 body,
83 rustc_middle::mir::RETURN_PLACE,
84 depth,
85 zst_branch,
86 &mut HashSet::new(),
87 )
88}
89
90fn ub_check_result_operand(tcx: TyCtxt<'_>, body: &Body<'_>, discr: &Operand<'_>) -> bool {
92 let Some(place) = mir_utils::operand_mir_place(discr) else {
93 return false;
94 };
95 if !place.projection.is_empty() {
96 return false;
97 }
98 let mut callee = None;
99 for block in body.basic_blocks.iter() {
100 if block.statements.iter().any(|stmt| {
101 matches!(&stmt.kind,
102 StatementKind::Assign(assign) if assign.0.local == place.local)
103 }) {
104 return false;
105 }
106 if let TerminatorKind::Call {
107 func, destination, ..
108 } = &block.terminator().kind
109 && destination.local == place.local
110 {
111 if !destination.projection.is_empty() || callee.is_some() {
112 return false;
113 }
114 let Some(did) = mir_utils::dep_callee_def_id(func) else {
115 return false;
116 };
117 callee = Some(did);
118 }
119 }
120 callee.is_some_and(|did| other_api::is_ub_check(tcx, did))
121}
122
123fn trace_pointer_offset<'tcx>(
124 tcx: TyCtxt<'tcx>,
125 body: &Body<'tcx>,
126 local: Local,
127 depth: usize,
128 zst_branch: bool,
129 seen: &mut HashSet<Local>,
130) -> Option<PointerOffset> {
131 if !seen.insert(local) {
132 return None;
133 }
134 let index = local.as_usize();
135 if index > 0 && index <= body.arg_count {
136 return Some(PointerOffset {
137 base: index - 1,
138 count: None,
139 direction: PointerOffsetDirection::Forward,
140 });
141 }
142 let mut result = None;
143 for block in body.basic_blocks.iter() {
144 for stmt in &block.statements {
145 let StatementKind::Assign(assign) = &stmt.kind else {
146 continue;
147 };
148 let (dest, rvalue) = &**assign;
149 if dest.local != local || !dest.projection.is_empty() {
150 continue;
151 }
152 let candidate = match rvalue {
153 Rvalue::Use(op, _) | Rvalue::Cast(_, op, _) => {
154 let source = mir_utils::operand_mir_place(op)?;
155 trace_pointer_offset(
156 tcx,
157 body,
158 source.local,
159 depth,
160 zst_branch,
161 &mut seen.clone(),
162 )?
163 }
164 Rvalue::BinaryOp(BinOp::Offset, operands) => {
165 let base = mir_utils::operand_mir_place(&operands.0)?;
166 let base = trace_pointer_offset(
167 tcx,
168 body,
169 base.local,
170 depth,
171 zst_branch,
172 &mut seen.clone(),
173 )?;
174 if base.count.is_some() {
175 return None;
176 }
177 let (count, backward) =
178 trace_offset_count(tcx, body, &operands.1, &mut HashSet::new())?;
179 PointerOffset {
180 base: base.base,
181 count: Some(count),
182 direction: if backward {
183 PointerOffsetDirection::Backward
184 } else {
185 PointerOffsetDirection::Forward
186 },
187 }
188 }
189 Rvalue::Aggregate(kind, operands)
190 if operands.len() == 1
191 || matches!(&**kind, rustc_middle::mir::AggregateKind::RawPtr(..)) =>
192 {
193 let source = mir_utils::operand_mir_place(operands.iter().next()?)?;
194 trace_pointer_offset(
195 tcx,
196 body,
197 source.local,
198 depth,
199 zst_branch,
200 &mut seen.clone(),
201 )?
202 }
203 _ => return None,
204 };
205 result = Some(merge_pointer_offsets(result, candidate, zst_branch)?);
206 }
207 let TerminatorKind::Call {
208 func,
209 args,
210 destination,
211 ..
212 } = &block.terminator().kind
213 else {
214 continue;
215 };
216 if destination.local != local || !destination.projection.is_empty() {
217 continue;
218 }
219 let callee = mir_utils::dep_callee_def_id(func)?;
220 let intrinsic = intrinsic_api::intrinsic_name(tcx, Some(callee))
221 .is_some_and(|name| name.as_str() == "arith_offset");
222 let nested = if intrinsic {
223 PointerOffset {
224 base: 0,
225 count: Some(1),
226 direction: PointerOffsetDirection::Forward,
227 }
228 } else {
229 pointer_offset(tcx, callee, depth - 1)?
230 };
231 let base_arg = args.get(nested.base)?;
232 let base_place = mir_utils::operand_mir_place(&base_arg.node)?;
233 let base = trace_pointer_offset(
234 tcx,
235 body,
236 base_place.local,
237 depth,
238 zst_branch,
239 &mut seen.clone(),
240 )?;
241 if base.count.is_some() {
242 return None;
243 }
244 let candidate = if let Some(count_index) = nested.count {
245 let (count, negative) =
246 trace_offset_count(tcx, body, &args.get(count_index)?.node, &mut HashSet::new())?;
247 PointerOffset {
248 base: base.base,
249 count: Some(count),
250 direction: if negative == (nested.direction == PointerOffsetDirection::Backward) {
251 PointerOffsetDirection::Forward
252 } else {
253 PointerOffsetDirection::Backward
254 },
255 }
256 } else {
257 base
258 };
259 result = Some(merge_pointer_offsets(result, candidate, zst_branch)?);
260 }
261 result
262}
263
264fn zst_property_operand<'tcx>(
265 tcx: TyCtxt<'tcx>,
266 body: &Body<'tcx>,
267 operand: &Operand<'tcx>,
268 pointee: Option<rustc_middle::ty::Ty<'tcx>>,
269) -> bool {
270 let Some(pointee) = pointee else {
271 return false;
272 };
273 let constant = match operand {
274 Operand::Constant(constant) => Some(constant),
275 Operand::Copy(place) | Operand::Move(place) => {
276 let mut found = None;
277 for stmt in body.basic_blocks.iter().flat_map(|block| &block.statements) {
278 let StatementKind::Assign(assign) = &stmt.kind else {
279 continue;
280 };
281 if assign.0.local != place.local {
282 continue;
283 }
284 let Rvalue::Use(Operand::Constant(value), _) = &assign.1 else {
285 return false;
286 };
287 if found.replace(value).is_some() {
288 return false;
289 }
290 }
291 found
292 }
293 Operand::RuntimeChecks(_) => None,
294 };
295 let Some(constant) = constant else {
296 return false;
297 };
298 let rustc_middle::mir::Const::Unevaluated(uneval, _) = constant.const_ else {
299 return false;
300 };
301 mir_utils::is_sized_type_property(tcx, uneval.def, "IS_ZST")
302 && uneval.args.types().next() == Some(pointee)
303}
304
305fn merge_pointer_offsets(
306 current: Option<PointerOffset>,
307 next: PointerOffset,
308 zst_branch: bool,
309) -> Option<PointerOffset> {
310 match current {
311 None => Some(next),
312 Some(old) if old == next => Some(old),
313 Some(old) if zst_branch && old.base == next.base && old.count.is_none() => Some(next),
314 Some(old) if zst_branch && old.base == next.base && next.count.is_none() => Some(old),
315 _ => None,
316 }
317}
318
319fn trace_offset_count<'tcx>(
320 tcx: TyCtxt<'tcx>,
321 body: &Body<'tcx>,
322 operand: &Operand<'tcx>,
323 seen: &mut HashSet<Local>,
324) -> Option<(usize, bool)> {
325 let place = mir_utils::operand_mir_place(operand)?;
326 let local = place.local;
327 if !seen.insert(local) {
328 return None;
329 }
330 let index = local.as_usize();
331 if index > 0 && index <= body.arg_count {
332 return Some((index - 1, false));
333 }
334 let mut result = None;
335 for block in body.basic_blocks.iter() {
336 for stmt in &block.statements {
337 let StatementKind::Assign(assign) = &stmt.kind else {
338 continue;
339 };
340 if assign.0.local != local || !assign.0.projection.is_empty() {
341 continue;
342 }
343 let candidate = match &assign.1 {
344 Rvalue::Use(op, _) | Rvalue::Cast(_, op, _) => {
345 trace_offset_count(tcx, body, op, &mut seen.clone())?
346 }
347 Rvalue::BinaryOp(BinOp::Sub | BinOp::SubUnchecked, operands)
348 if is_zero_constant(tcx, &operands.0) =>
349 {
350 let (arg, neg) = trace_offset_count(tcx, body, &operands.1, &mut seen.clone())?;
351 (arg, !neg)
352 }
353 _ => return None,
354 };
355 if result.is_some_and(|old| old != candidate) {
356 return None;
357 }
358 result = Some(candidate);
359 }
360 }
361 result
362}
363
364fn is_zero_constant<'tcx>(tcx: TyCtxt<'tcx>, operand: &Operand<'tcx>) -> bool {
365 let Operand::Constant(c) = operand else {
366 return false;
367 };
368 c.const_
369 .eval(tcx, TypingEnv::fully_monomorphized(), rustc_span::DUMMY_SP)
370 .ok()
371 .and_then(|value| value.try_to_scalar_int())
372 .is_some_and(|scalar| scalar.to_bits(scalar.size()) == 0)
373}