1 use clippy_utils::consts::{constant, constant_full_int, miri_to_const, FullInt};
2 use clippy_utils::diagnostics::span_lint_and_note;
3 use core::cmp::Ordering;
4 use rustc_hir::{Arm, Expr, PatKind, RangeEnd};
5 use rustc_lint::LateContext;
7 use rustc_middle::ty::Ty;
10 use super::MATCH_OVERLAPPING_ARM;
12 pub(crate) fn check<'tcx>(cx: &LateContext<'tcx>, ex: &'tcx Expr<'_>, arms: &'tcx [Arm<'_>]) {
13 if arms.len() >= 2 && cx.typeck_results().expr_ty(ex).is_integral() {
14 let ranges = all_ranges(cx, arms, cx.typeck_results().expr_ty(ex));
15 if !ranges.is_empty() {
16 if let Some((start, end)) = overlapping(&ranges) {
19 MATCH_OVERLAPPING_ARM,
21 "some ranges overlap",
30 /// Gets the ranges for each range pattern arm. Applies `ty` bounds for open ranges.
31 fn all_ranges<'tcx>(cx: &LateContext<'tcx>, arms: &'tcx [Arm<'_>], ty: Ty<'tcx>) -> Vec<SpannedRange<FullInt>> {
34 if let Arm { pat, guard: None, .. } = *arm {
35 if let PatKind::Range(ref lhs, ref rhs, range_end) = pat.kind {
36 let lhs_const = match lhs {
37 Some(lhs) => constant(cx, cx.typeck_results(), lhs)?.0,
39 let min_val_const = ty.numeric_min_val(cx.tcx)?;
40 let min_constant = mir::ConstantKind::from_value(
41 cx.tcx.valtree_to_const_val((ty, min_val_const.to_valtree())),
44 miri_to_const(cx.tcx, min_constant)?
47 let rhs_const = match rhs {
48 Some(rhs) => constant(cx, cx.typeck_results(), rhs)?.0,
50 let max_val_const = ty.numeric_max_val(cx.tcx)?;
51 let max_constant = mir::ConstantKind::from_value(
52 cx.tcx.valtree_to_const_val((ty, max_val_const.to_valtree())),
55 miri_to_const(cx.tcx, max_constant)?
58 let lhs_val = lhs_const.int_value(cx, ty)?;
59 let rhs_val = rhs_const.int_value(cx, ty)?;
60 let rhs_bound = match range_end {
61 RangeEnd::Included => EndBound::Included(rhs_val),
62 RangeEnd::Excluded => EndBound::Excluded(rhs_val),
64 return Some(SpannedRange {
66 node: (lhs_val, rhs_bound),
70 if let PatKind::Lit(value) = pat.kind {
71 let value = constant_full_int(cx, cx.typeck_results(), value)?;
72 return Some(SpannedRange {
74 node: (value, EndBound::Included(value)),
83 #[derive(Clone, Copy, Debug, Eq, PartialEq)]
84 pub enum EndBound<T> {
89 #[derive(Debug, Eq, PartialEq)]
90 struct SpannedRange<T> {
92 pub node: (T, EndBound<T>),
95 fn overlapping<T>(ranges: &[SpannedRange<T>]) -> Option<(&SpannedRange<T>, &SpannedRange<T>)>
99 #[derive(Copy, Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
106 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
107 struct RangeBound<'a, T>(T, BoundKind, &'a SpannedRange<T>);
109 impl<'a, T: Copy + Ord> PartialOrd for RangeBound<'a, T> {
110 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
111 Some(self.cmp(other))
115 impl<'a, T: Copy + Ord> Ord for RangeBound<'a, T> {
116 fn cmp(&self, RangeBound(other_value, other_kind, _): &Self) -> Ordering {
117 let RangeBound(self_value, self_kind, _) = *self;
118 (self_value, self_kind).cmp(&(*other_value, *other_kind))
122 let mut values = Vec::with_capacity(2 * ranges.len());
124 for r @ SpannedRange { node: (start, end), .. } in ranges {
125 values.push(RangeBound(*start, BoundKind::Start, r));
126 values.push(match end {
127 EndBound::Excluded(val) => RangeBound(*val, BoundKind::EndExcluded, r),
128 EndBound::Included(val) => RangeBound(*val, BoundKind::EndIncluded, r),
134 let mut started = vec![];
136 for RangeBound(_, kind, range) in values {
138 BoundKind::Start => started.push(range),
139 BoundKind::EndExcluded | BoundKind::EndIncluded => {
140 let mut overlap = None;
142 while let Some(last_started) = started.pop() {
143 if last_started == range {
146 overlap = Some(last_started);
149 if let Some(first_overlapping) = overlap {
150 return Some((range, first_overlapping));
160 fn test_overlapping() {
161 use rustc_span::source_map::DUMMY_SP;
163 let sp = |s, e| SpannedRange {
168 assert_eq!(None, overlapping::<u8>(&[]));
169 assert_eq!(None, overlapping(&[sp(1, EndBound::Included(4))]));
172 overlapping(&[sp(1, EndBound::Included(4)), sp(5, EndBound::Included(6))])
177 sp(1, EndBound::Included(4)),
178 sp(5, EndBound::Included(6)),
179 sp(10, EndBound::Included(11))
183 Some((&sp(1, EndBound::Included(4)), &sp(3, EndBound::Included(6)))),
184 overlapping(&[sp(1, EndBound::Included(4)), sp(3, EndBound::Included(6))])
187 Some((&sp(5, EndBound::Included(6)), &sp(6, EndBound::Included(11)))),
189 sp(1, EndBound::Included(4)),
190 sp(5, EndBound::Included(6)),
191 sp(6, EndBound::Included(11))