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