compiler/rustc_typeck/src/check/fn_ctxt/arg_matrix.rs

   1 use std::cmp;
   2
   3 use rustc_middle::ty::error::TypeError;
   4
   5 // An issue that might be found in the compatibility matrix
   6 enum Issue {
   7     /// The given argument is the invalid type for the input
   8     Invalid(usize),
   9     /// There is a missing input
  10     Missing(usize),
  11     /// There's a superfluous argument
  12     Extra(usize),
  13     /// Two arguments should be swapped
  14     Swap(usize, usize),
  15     /// Several arguments should be reordered
  16     Permutation(Vec<Option<usize>>),
  17 }
  18
  19 #[derive(Clone, Debug)]
  20 pub(crate) enum Compatibility<'tcx> {
  21     Compatible,
  22     Incompatible(Option<TypeError<'tcx>>),
  23 }
  24
  25 /// Similar to `Issue`, but contains some extra information
  26 pub(crate) enum Error<'tcx> {
  27     /// The given argument is the invalid type for the input
  28     Invalid(usize, Compatibility<'tcx>),
  29     /// There is a missing input
  30     Missing(usize),
  31     /// There's a superfluous argument
  32     Extra(usize),
  33     /// Two arguments should be swapped
  34     Swap(usize, usize, usize, usize),
  35     /// Several arguments should be reordered
  36     Permutation(Vec<(usize, usize)>), // dest_arg, dest_input
  37 }
  38
  39 pub(crate) struct ArgMatrix<'tcx> {
  40     input_indexes: Vec<usize>,
  41     arg_indexes: Vec<usize>,
  42     compatibility_matrix: Vec<Vec<Compatibility<'tcx>>>,
  43 }
  44
  45 impl<'tcx> ArgMatrix<'tcx> {
  46     pub(crate) fn new<F: FnMut(usize, usize) -> Compatibility<'tcx>>(
  47         minimum_input_count: usize,
  48         provided_arg_count: usize,
  49         mut is_compatible: F,
  50     ) -> Self {
  51         let compatibility_matrix = (0..provided_arg_count)
  52             .map(|i| (0..minimum_input_count).map(|j| is_compatible(i, j)).collect())
  53             .collect();
  54         ArgMatrix {
  55             input_indexes: (0..minimum_input_count).collect(),
  56             arg_indexes: (0..provided_arg_count).collect(),
  57             compatibility_matrix,
  58         }
  59     }
  60
  61     /// Remove a given input from consideration
  62     fn eliminate_input(&mut self, idx: usize) {
  63         self.input_indexes.remove(idx);
  64         for row in &mut self.compatibility_matrix {
  65             row.remove(idx);
  66         }
  67     }
  68
  69     /// Remove a given argument from consideration
  70     fn eliminate_arg(&mut self, idx: usize) {
  71         self.arg_indexes.remove(idx);
  72         self.compatibility_matrix.remove(idx);
  73     }
  74
  75     /// "satisfy" an input with a given arg, removing both from consideration
  76     fn satisfy_input(&mut self, input_idx: usize, arg_idx: usize) {
  77         self.eliminate_input(input_idx);
  78         self.eliminate_arg(arg_idx);
  79     }
  80
  81     fn eliminate_satisfied(&mut self) -> Vec<(usize, usize)> {
  82         let mut i = cmp::min(self.input_indexes.len(), self.arg_indexes.len());
  83         let mut eliminated = vec![];
  84         while i > 0 {
  85             let idx = i - 1;
  86             if matches!(self.compatibility_matrix[idx][idx], Compatibility::Compatible) {
  87                 eliminated.push((self.arg_indexes[idx], self.input_indexes[idx]));
  88                 self.satisfy_input(idx, idx);
  89             }
  90             i -= 1;
  91         }
  92         return eliminated;
  93     }
  94
  95     // Check for the above mismatch cases
  96     fn find_issue(&self) -> Option<Issue> {
  97         let mat = &self.compatibility_matrix;
  98         let ai = &self.arg_indexes;
  99         let ii = &self.input_indexes;
 100
 101         for i in 0..cmp::max(ai.len(), ii.len()) {
 102             // If we eliminate the last row, any left-over inputs are considered missing
 103             if i >= mat.len() {
 104                 return Some(Issue::Missing(i));
 105             }
 106             // If we eliminate the last column, any left-over arguments are extra
 107             if mat[i].len() == 0 {
 108                 return Some(Issue::Extra(i));
 109             }
 110
 111             // Make sure we don't pass the bounds of our matrix
 112             let is_arg = i < ai.len();
 113             let is_input = i < ii.len();
 114             if is_arg && is_input && matches!(mat[i][i], Compatibility::Compatible) {
 115                 // This is a satisfied input, so move along
 116                 continue;
 117             }
 118
 119             let mut useless = true;
 120             let mut unsatisfiable = true;
 121             if is_arg {
 122                 for j in 0..ii.len() {
 123                     // If we find at least one input this argument could satisfy
 124                     // this argument isn't completely useless
 125                     if matches!(mat[i][j], Compatibility::Compatible) {
 126                         useless = false;
 127                         break;
 128                     }
 129                 }
 130             }
 131             if is_input {
 132                 for j in 0..ai.len() {
 133                     // If we find at least one argument that could satisfy this input
 134                     // this argument isn't unsatisfiable
 135                     if matches!(mat[j][i], Compatibility::Compatible) {
 136                         unsatisfiable = false;
 137                         break;
 138                     }
 139                 }
 140             }
 141
 142             match (is_arg, is_input, useless, unsatisfiable) {
 143                 // If an input is unsatisfied, and the argument in its position is useless
 144                 // then the most likely explanation is that we just got the types wrong
 145                 (true, true, true, true) => return Some(Issue::Invalid(i)),
 146                 // Otherwise, if an input is useless, then indicate that this is an extra argument
 147                 (true, _, true, _) => return Some(Issue::Extra(i)),
 148                 // Otherwise, if an argument is unsatisfiable, indicate that it's missing
 149                 (_, true, _, true) => return Some(Issue::Missing(i)),
 150                 (true, true, _, _) => {
 151                     // The argument isn't useless, and the input isn't unsatisfied,
 152                     // so look for a parameter we might swap it with
 153                     // We look for swaps explicitly, instead of just falling back on permutations
 154                     // so that cases like (A,B,C,D) given (B,A,D,C) show up as two swaps,
 155                     // instead of a large permutation of 4 elements.
 156                     for j in 0..cmp::min(ai.len(), ii.len()) {
 157                         if i == j || matches!(mat[j][j], Compatibility::Compatible) {
 158                             continue;
 159                         }
 160                         if matches!(mat[i][j], Compatibility::Compatible)
 161                             && matches!(mat[j][i], Compatibility::Compatible)
 162                         {
 163                             return Some(Issue::Swap(i, j));
 164                         }
 165                     }
 166                 }
 167                 _ => {
 168                     continue;
 169                 }
 170             };
 171         }
 172
 173         // We didn't find any of the individual issues above, but
 174         // there might be a larger permutation of parameters, so we now check for that
 175         // by checking for cycles
 176         // We use a double option at position i in this vec to represent:
 177         // - None: We haven't computed anything about this argument yet
 178         // - Some(None): This argument definitely doesn't participate in a cycle
 179         // - Some(Some(x)): the i-th argument could permute to the x-th position
 180         let mut permutation: Vec<Option<Option<usize>>> = vec![None; mat.len()];
 181         let mut permutation_found = false;
 182         for i in 0..mat.len() {
 183             if permutation[i].is_some() {
 184                 // We've already decided whether this argument is or is not in a loop
 185                 continue;
 186             }
 187
 188             let mut stack = vec![];
 189             let mut j = i;
 190             let mut last = i;
 191             let mut is_cycle = true;
 192             loop {
 193                 stack.push(j);
 194                 // Look for params this one could slot into
 195                 let compat: Vec<_> =
 196                     mat[j]
 197                         .iter()
 198                         .enumerate()
 199                         .filter_map(|(i, c)| {
 200                             if matches!(c, Compatibility::Compatible) { Some(i) } else { None }
 201                         })
 202                         .collect();
 203                 if compat.len() != 1 {
 204                     // this could go into multiple slots, don't bother exploring both
 205                     is_cycle = false;
 206                     break;
 207                 }
 208                 j = compat[0];
 209                 if stack.contains(&j) {
 210                     last = j;
 211                     break;
 212                 }
 213             }
 214             if stack.len() <= 2 {
 215                 // If we encounter a cycle of 1 or 2 elements, we'll let the
 216                 // "satisfy" and "swap" code above handle those
 217                 is_cycle = false;
 218             }
 219             // We've built up some chain, some of which might be a cycle
 220             // ex: [1,2,3,4]; last = 2; j = 2;
 221             // So, we want to mark 4, 3, and 2 as part of a permutation
 222             permutation_found = is_cycle;
 223             while let Some(x) = stack.pop() {
 224                 if is_cycle {
 225                     permutation[x] = Some(Some(j));
 226                     j = x;
 227                     if j == last {
 228                         // From here on out, we're a tail leading into a cycle,
 229                         // not the cycle itself
 230                         is_cycle = false;
 231                     }
 232                 } else {
 233                     // Some(None) ensures we save time by skipping this argument again
 234                     permutation[x] = Some(None);
 235                 }
 236             }
 237         }
 238
 239         if permutation_found {
 240             // Map unwrap to remove the first layer of Some
 241             let final_permutation: Vec<Option<usize>> =
 242                 permutation.into_iter().map(|x| x.unwrap()).collect();
 243             return Some(Issue::Permutation(final_permutation));
 244         }
 245         return None;
 246     }
 247
 248     // Obviously, detecting exact user intention is impossible, so the goal here is to
 249     // come up with as likely of a story as we can to be helpful.
 250     //
 251     // We'll iteratively removed "satisfied" input/argument pairs,
 252     // then check for the cases above, until we've eliminated the entire grid
 253     //
 254     // We'll want to know which arguments and inputs these rows and columns correspond to
 255     // even after we delete them.
 256     pub(crate) fn find_errors(mut self) -> (Vec<Error<'tcx>>, Vec<Option<usize>>) {
 257         let provided_arg_count = self.arg_indexes.len();
 258
 259         let mut errors: Vec<Error<'tcx>> = vec![];
 260         // For each expected argument, the matched *actual* input
 261         let mut matched_inputs: Vec<Option<usize>> = vec![None; self.input_indexes.len()];
 262
 263         // Before we start looking for issues, eliminate any arguments that are already satisfied,
 264         // so that an argument which is already spoken for by the input it's in doesn't
 265         // spill over into another similarly typed input
 266         // ex:
 267         //   fn some_func(_a: i32, _b: i32) {}
 268         //   some_func(1, "");
 269         // Without this elimination, the first argument causes the second argument
 270         // to show up as both a missing input and extra argument, rather than
 271         // just an invalid type.
 272         for (arg, inp) in self.eliminate_satisfied() {
 273             matched_inputs[inp] = Some(arg);
 274         }
 275
 276         while self.input_indexes.len() > 0 || self.arg_indexes.len() > 0 {
 277             // Check for the first relevant issue
 278             match self.find_issue() {
 279                 Some(Issue::Invalid(idx)) => {
 280                     let compatibility = self.compatibility_matrix[idx][idx].clone();
 281                     let input_idx = self.input_indexes[idx];
 282                     self.satisfy_input(idx, idx);
 283                     errors.push(Error::Invalid(input_idx, compatibility));
 284                 }
 285                 Some(Issue::Extra(idx)) => {
 286                     let arg_idx = self.arg_indexes[idx];
 287                     self.eliminate_arg(idx);
 288                     errors.push(Error::Extra(arg_idx));
 289                 }
 290                 Some(Issue::Missing(idx)) => {
 291                     let input_idx = self.input_indexes[idx];
 292                     self.eliminate_input(idx);
 293                     errors.push(Error::Missing(input_idx));
 294                 }
 295                 Some(Issue::Swap(idx, other)) => {
 296                     let input_idx = self.input_indexes[idx];
 297                     let other_input_idx = self.input_indexes[other];
 298                     let arg_idx = self.arg_indexes[idx];
 299                     let other_arg_idx = self.arg_indexes[other];
 300                     let (min, max) = (cmp::min(idx, other), cmp::max(idx, other));
 301                     self.satisfy_input(min, max);
 302                     // Subtract 1 because we already removed the "min" row
 303                     self.satisfy_input(max - 1, min);
 304                     errors.push(Error::Swap(input_idx, other_input_idx, arg_idx, other_arg_idx));
 305                     matched_inputs[input_idx] = Some(other_arg_idx);
 306                     matched_inputs[other_input_idx] = Some(arg_idx);
 307                 }
 308                 Some(Issue::Permutation(args)) => {
 309                     // FIXME: If satisfy_input ever did anything non-trivial (emit obligations to help type checking, for example)
 310                     // we'd want to call this function with the correct arg/input pairs, but for now, we just throw them in a bucket.
 311                     // This works because they force a cycle, so each row is guaranteed to also be a column
 312                     let mut idxs: Vec<usize> = args.iter().filter_map(|&a| a).collect();
 313
 314                     let mut real_idxs = vec![None; provided_arg_count];
 315                     for (src, dst) in
 316                         args.iter().enumerate().filter_map(|(src, dst)| dst.map(|dst| (src, dst)))
 317                     {
 318                         let src_arg = self.arg_indexes[src];
 319                         let dst_arg = self.arg_indexes[dst];
 320                         let dest_input = self.input_indexes[dst];
 321                         real_idxs[src_arg] = Some((dst_arg, dest_input));
 322                         matched_inputs[dest_input] = Some(src_arg);
 323                     }
 324                     idxs.sort();
 325                     idxs.reverse();
 326                     for i in idxs {
 327                         self.satisfy_input(i, i);
 328                     }
 329                     errors.push(Error::Permutation(real_idxs.into_iter().flatten().collect()));
 330                 }
 331                 None => {
 332                     // We didn't find any issues, so we need to push the algorithm forward
 333                     // First, eliminate any arguments that currently satisfy their inputs
 334                     for (arg, inp) in self.eliminate_satisfied() {
 335                         matched_inputs[inp] = Some(arg);
 336                     }
 337                 }
 338             };
 339         }
 340
 341         return (errors, matched_inputs);
 342     }
 343 }