src/tools/clippy/clippy_lints/src/matches/overlapping_arms.rs

   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;
   6 use rustc_middle::mir;
   7 use rustc_middle::ty::Ty;
   8 use rustc_span::Span;
   9
  10 use super::MATCH_OVERLAPPING_ARM;
  11
  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) {
  17                 span_lint_and_note(
  18                     cx,
  19                     MATCH_OVERLAPPING_ARM,
  20                     start.span,
  21                     "some ranges overlap",
  22                     Some(end.span),
  23                     "overlaps with this",
  24                 );
  25             }
  26         }
  27     }
  28 }
  29
  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>> {
  32     arms.iter()
  33         .filter_map(|arm| {
  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,
  38                         None => {
  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())),
  42                                 ty,
  43                             );
  44                             miri_to_const(cx.tcx, min_constant)?
  45                         },
  46                     };
  47                     let rhs_const = match rhs {
  48                         Some(rhs) => constant(cx, cx.typeck_results(), rhs)?.0,
  49                         None => {
  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())),
  53                                 ty,
  54                             );
  55                             miri_to_const(cx.tcx, max_constant)?
  56                         },
  57                     };
  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),
  63                     };
  64                     return Some(SpannedRange {
  65                         span: pat.span,
  66                         node: (lhs_val, rhs_bound),
  67                     });
  68                 }
  69
  70                 if let PatKind::Lit(value) = pat.kind {
  71                     let value = constant_full_int(cx, cx.typeck_results(), value)?;
  72                     return Some(SpannedRange {
  73                         span: pat.span,
  74                         node: (value, EndBound::Included(value)),
  75                     });
  76                 }
  77             }
  78             None
  79         })
  80         .collect()
  81 }
  82
  83 #[derive(Clone, Copy, Debug, Eq, PartialEq)]
  84 pub enum EndBound<T> {
  85     Included(T),
  86     Excluded(T),
  87 }
  88
  89 #[derive(Debug, Eq, PartialEq)]
  90 struct SpannedRange<T> {
  91     pub span: Span,
  92     pub node: (T, EndBound<T>),
  93 }
  94
  95 fn overlapping<T>(ranges: &[SpannedRange<T>]) -> Option<(&SpannedRange<T>, &SpannedRange<T>)>
  96 where
  97     T: Copy + Ord,
  98 {
  99     #[derive(Copy, Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
 100     enum BoundKind {
 101         EndExcluded,
 102         Start,
 103         EndIncluded,
 104     }
 105
 106     #[derive(Copy, Clone, Debug, Eq, PartialEq)]
 107     struct RangeBound<'a, T>(T, BoundKind, &'a SpannedRange<T>);
 108
 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))
 112         }
 113     }
 114
 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))
 119         }
 120     }
 121
 122     let mut values = Vec::with_capacity(2 * ranges.len());
 123
 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),
 129         });
 130     }
 131
 132     values.sort();
 133
 134     let mut started = vec![];
 135
 136     for RangeBound(_, kind, range) in values {
 137         match kind {
 138             BoundKind::Start => started.push(range),
 139             BoundKind::EndExcluded | BoundKind::EndIncluded => {
 140                 let mut overlap = None;
 141
 142                 while let Some(last_started) = started.pop() {
 143                     if last_started == range {
 144                         break;
 145                     }
 146                     overlap = Some(last_started);
 147                 }
 148
 149                 if let Some(first_overlapping) = overlap {
 150                     return Some((range, first_overlapping));
 151                 }
 152             },
 153         }
 154     }
 155
 156     None
 157 }
 158
 159 #[test]
 160 fn test_overlapping() {
 161     use rustc_span::source_map::DUMMY_SP;
 162
 163     let sp = |s, e| SpannedRange {
 164         span: DUMMY_SP,
 165         node: (s, e),
 166     };
 167
 168     assert_eq!(None, overlapping::<u8>(&[]));
 169     assert_eq!(None, overlapping(&[sp(1, EndBound::Included(4))]));
 170     assert_eq!(
 171         None,
 172         overlapping(&[sp(1, EndBound::Included(4)), sp(5, EndBound::Included(6))])
 173     );
 174     assert_eq!(
 175         None,
 176         overlapping(&[
 177             sp(1, EndBound::Included(4)),
 178             sp(5, EndBound::Included(6)),
 179             sp(10, EndBound::Included(11))
 180         ],)
 181     );
 182     assert_eq!(
 183         Some((&sp(1, EndBound::Included(4)), &sp(3, EndBound::Included(6)))),
 184         overlapping(&[sp(1, EndBound::Included(4)), sp(3, EndBound::Included(6))])
 185     );
 186     assert_eq!(
 187         Some((&sp(5, EndBound::Included(6)), &sp(6, EndBound::Included(11)))),
 188         overlapping(&[
 189             sp(1, EndBound::Included(4)),
 190             sp(5, EndBound::Included(6)),
 191             sp(6, EndBound::Included(11))
 192         ],)
 193     );
 194 }