3 use rustc_index::vec::IndexVec;
4 use rustc_middle::ty::error::TypeError;
6 rustc_index::newtype_index! {
7 pub(crate) struct ExpectedIdx {
8 DEBUG_FORMAT = "ExpectedIdx({})",
12 rustc_index::newtype_index! {
13 pub(crate) struct ProvidedIdx {
14 DEBUG_FORMAT = "ProvidedIdx({})",
19 pub fn to_provided_idx(self) -> ProvidedIdx {
20 ProvidedIdx::from_usize(self.as_usize())
24 // An issue that might be found in the compatibility matrix
27 /// The given argument is the invalid type for the input
29 /// There is a missing input
31 /// There's a superfluous argument
33 /// Two arguments should be swapped
35 /// Several arguments should be reordered
36 Permutation(Vec<Option<usize>>),
39 #[derive(Clone, Debug)]
40 pub(crate) enum Compatibility<'tcx> {
42 Incompatible(Option<TypeError<'tcx>>),
45 /// Similar to `Issue`, but contains some extra information
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
52 /// There's a superfluous argument
54 /// Two arguments should be swapped
55 Swap(ProvidedIdx, ProvidedIdx, ExpectedIdx, ExpectedIdx),
56 /// Several arguments should be reordered
57 Permutation(Vec<(ExpectedIdx, ProvidedIdx)>),
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
70 compatibility_matrix: Vec<Vec<Compatibility<'tcx>>>,
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,
79 let compatibility_matrix = (0..provided_count)
81 (0..expected_input_count)
82 .map(|j| is_compatible(ProvidedIdx::from_usize(i), ExpectedIdx::from_usize(j)))
87 provided_indices: (0..provided_count).map(ProvidedIdx::from_usize).collect(),
88 expected_indices: (0..expected_input_count).map(ExpectedIdx::from_usize).collect(),
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);
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 {
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);
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);
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;
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
139 return Some(Issue::Missing(next_unmatched_idx));
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));
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;
155 let mut useless = true;
156 let mut unsatisfiable = true;
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;
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) {
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) {
196 if matches!(mat[i][j], Compatibility::Compatible)
197 && matches!(mat[j][i], Compatibility::Compatible)
199 return Some(Issue::Swap(i, j));
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
224 let mut stack = vec![];
227 let mut is_cycle = true;
230 // Look for params this one could slot into
235 .filter_map(|(i, c)| {
236 if matches!(c, Compatibility::Compatible) { Some(i) } else { None }
239 if compat.len() < 1 {
240 // try to find a cycle even when this could go into multiple slots, see #101097
245 if stack.contains(&j) {
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
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() {
261 permutation[x] = Some(Some(j));
264 // From here on out, we're a tail leading into a cycle,
265 // not the cycle itself
269 // Some(None) ensures we save time by skipping this argument again
270 permutation[x] = Some(None);
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));
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.
287 // We'll iteratively removed "satisfied" input/argument pairs,
288 // then check for the cases above, until we've eliminated the entire grid
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(
294 ) -> (Vec<Error<'tcx>>, IndexVec<ExpectedIdx, Option<ProvidedIdx>>) {
295 let provided_arg_count = self.provided_indices.len();
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());
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
306 // fn some_func(_a: i32, _b: i32) {}
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);
315 while !self.provided_indices.is_empty() || !self.expected_indices.is_empty() {
316 let res = self.find_issue();
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));
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));
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));
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);
348 Some(Issue::Permutation(args)) => {
349 let mut idxs: Vec<usize> = args.iter().filter_map(|&a| a).collect();
351 let mut real_idxs: IndexVec<ProvidedIdx, Option<(ExpectedIdx, ProvidedIdx)>> =
352 IndexVec::from_elem_n(None, provided_arg_count);
354 args.iter().enumerate().filter_map(|(src, dst)| dst.map(|dst| (src, dst)))
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);
365 self.satisfy_input(i, i);
367 errors.push(Error::Permutation(real_idxs.into_iter().flatten().collect()));
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);
381 return (errors, matched_inputs);