compiler/rustc_hir_typeck/src/fn_ctxt/arg_matrix.rs

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