3 use rustc_index::vec::IndexVec;
4 use rustc_middle::ty::error::TypeError;
6 rustc_index::newtype_index! {
7 #[debug_format = "ExpectedIdx({})"]
8 pub(crate) struct ExpectedIdx {}
11 rustc_index::newtype_index! {
12 #[debug_format = "ProvidedIdx({})"]
13 pub(crate) struct ProvidedIdx {}
17 pub fn to_provided_idx(self) -> ProvidedIdx {
18 ProvidedIdx::from_usize(self.as_usize())
22 // An issue that might be found in the compatibility matrix
25 /// The given argument is the invalid type for the input
27 /// There is a missing input
29 /// There's a superfluous argument
31 /// Two arguments should be swapped
33 /// Several arguments should be reordered
34 Permutation(Vec<Option<usize>>),
37 #[derive(Clone, Debug)]
38 pub(crate) enum Compatibility<'tcx> {
40 Incompatible(Option<TypeError<'tcx>>),
43 /// Similar to `Issue`, but contains some extra information
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
50 /// There's a superfluous argument
52 /// Two arguments should be swapped
53 Swap(ProvidedIdx, ProvidedIdx, ExpectedIdx, ExpectedIdx),
54 /// Several arguments should be reordered
55 Permutation(Vec<(ExpectedIdx, ProvidedIdx)>),
58 pub(crate) struct ArgMatrix<'tcx> {
59 /// Maps the indices in the `compatibility_matrix` rows to the indices of
60 /// the *user provided* inputs
61 provided_indices: Vec<ProvidedIdx>,
62 /// Maps the indices in the `compatibility_matrix` columns to the indices
63 /// of the *expected* args
64 expected_indices: Vec<ExpectedIdx>,
65 /// The first dimension (rows) are the remaining user provided inputs to
66 /// match and the second dimension (cols) are the remaining expected args
68 compatibility_matrix: Vec<Vec<Compatibility<'tcx>>>,
71 impl<'tcx> ArgMatrix<'tcx> {
72 pub(crate) fn new<F: FnMut(ProvidedIdx, ExpectedIdx) -> Compatibility<'tcx>>(
73 provided_count: usize,
74 expected_input_count: usize,
77 let compatibility_matrix = (0..provided_count)
79 (0..expected_input_count)
80 .map(|j| is_compatible(ProvidedIdx::from_usize(i), ExpectedIdx::from_usize(j)))
85 provided_indices: (0..provided_count).map(ProvidedIdx::from_usize).collect(),
86 expected_indices: (0..expected_input_count).map(ExpectedIdx::from_usize).collect(),
91 /// Remove a given input from consideration
92 fn eliminate_provided(&mut self, idx: usize) {
93 self.provided_indices.remove(idx);
94 self.compatibility_matrix.remove(idx);
97 /// Remove a given argument from consideration
98 fn eliminate_expected(&mut self, idx: usize) {
99 self.expected_indices.remove(idx);
100 for row in &mut self.compatibility_matrix {
105 /// "satisfy" an input with a given arg, removing both from consideration
106 fn satisfy_input(&mut self, provided_idx: usize, expected_idx: usize) {
107 self.eliminate_provided(provided_idx);
108 self.eliminate_expected(expected_idx);
111 // Returns a `Vec` of (user input, expected arg) of matched arguments. These
112 // are inputs on the remaining diagonal that match.
113 fn eliminate_satisfied(&mut self) -> Vec<(ProvidedIdx, ExpectedIdx)> {
114 let num_args = cmp::min(self.provided_indices.len(), self.expected_indices.len());
115 let mut eliminated = vec![];
116 for i in (0..num_args).rev() {
117 if matches!(self.compatibility_matrix[i][i], Compatibility::Compatible) {
118 eliminated.push((self.provided_indices[i], self.expected_indices[i]));
119 self.satisfy_input(i, i);
125 // Find some issue in the compatibility matrix
126 fn find_issue(&self) -> Option<Issue> {
127 let mat = &self.compatibility_matrix;
128 let ai = &self.expected_indices;
129 let ii = &self.provided_indices;
131 // Issue: 100478, when we end the iteration,
132 // `next_unmatched_idx` will point to the index of the first unmatched
133 let mut next_unmatched_idx = 0;
134 for i in 0..cmp::max(ai.len(), ii.len()) {
135 // If we eliminate the last row, any left-over arguments are considered missing
137 return Some(Issue::Missing(next_unmatched_idx));
139 // If we eliminate the last column, any left-over inputs are extra
140 if mat[i].len() == 0 {
141 return Some(Issue::Extra(next_unmatched_idx));
144 // Make sure we don't pass the bounds of our matrix
145 let is_arg = i < ai.len();
146 let is_input = i < ii.len();
147 if is_arg && is_input && matches!(mat[i][i], Compatibility::Compatible) {
148 // This is a satisfied input, so move along
149 next_unmatched_idx += 1;
153 let mut useless = true;
154 let mut unsatisfiable = true;
156 for j in 0..ii.len() {
157 // If we find at least one input this argument could satisfy
158 // this argument isn't unsatisfiable
159 if matches!(mat[j][i], Compatibility::Compatible) {
160 unsatisfiable = false;
166 for j in 0..ai.len() {
167 // If we find at least one argument that could satisfy this input
168 // this input isn't useless
169 if matches!(mat[i][j], Compatibility::Compatible) {
176 match (is_input, is_arg, useless, unsatisfiable) {
177 // If an argument is unsatisfied, and the input in its position is useless
178 // then the most likely explanation is that we just got the types wrong
179 (true, true, true, true) => return Some(Issue::Invalid(i)),
180 // Otherwise, if an input is useless, then indicate that this is an extra argument
181 (true, _, true, _) => return Some(Issue::Extra(i)),
182 // Otherwise, if an argument is unsatisfiable, indicate that it's missing
183 (_, true, _, true) => return Some(Issue::Missing(i)),
184 (true, true, _, _) => {
185 // The argument isn't useless, and the input isn't unsatisfied,
186 // so look for a parameter we might swap it with
187 // We look for swaps explicitly, instead of just falling back on permutations
188 // so that cases like (A,B,C,D) given (B,A,D,C) show up as two swaps,
189 // instead of a large permutation of 4 elements.
190 for j in 0..cmp::min(ai.len(), ii.len()) {
191 if i == j || matches!(mat[j][j], Compatibility::Compatible) {
194 if matches!(mat[i][j], Compatibility::Compatible)
195 && matches!(mat[j][i], Compatibility::Compatible)
197 return Some(Issue::Swap(i, j));
207 // We didn't find any of the individual issues above, but
208 // there might be a larger permutation of parameters, so we now check for that
209 // by checking for cycles
210 // We use a double option at position i in this vec to represent:
211 // - None: We haven't computed anything about this argument yet
212 // - Some(None): This argument definitely doesn't participate in a cycle
213 // - Some(Some(x)): the i-th argument could permute to the x-th position
214 let mut permutation: Vec<Option<Option<usize>>> = vec![None; mat.len()];
215 let mut permutation_found = false;
216 for i in 0..mat.len() {
217 if permutation[i].is_some() {
218 // We've already decided whether this argument is or is not in a loop
222 let mut stack = vec![];
225 let mut is_cycle = true;
228 // Look for params this one could slot into
233 .filter_map(|(i, c)| {
234 if matches!(c, Compatibility::Compatible) { Some(i) } else { None }
237 if compat.len() < 1 {
238 // try to find a cycle even when this could go into multiple slots, see #101097
243 if stack.contains(&j) {
248 if stack.len() <= 2 {
249 // If we encounter a cycle of 1 or 2 elements, we'll let the
250 // "satisfy" and "swap" code above handle those
253 // We've built up some chain, some of which might be a cycle
254 // ex: [1,2,3,4]; last = 2; j = 2;
255 // So, we want to mark 4, 3, and 2 as part of a permutation
256 permutation_found = is_cycle;
257 while let Some(x) = stack.pop() {
259 permutation[x] = Some(Some(j));
262 // From here on out, we're a tail leading into a cycle,
263 // not the cycle itself
267 // Some(None) ensures we save time by skipping this argument again
268 permutation[x] = Some(None);
273 if permutation_found {
274 // Map unwrap to remove the first layer of Some
275 let final_permutation: Vec<Option<usize>> =
276 permutation.into_iter().map(|x| x.unwrap()).collect();
277 return Some(Issue::Permutation(final_permutation));
282 // Obviously, detecting exact user intention is impossible, so the goal here is to
283 // come up with as likely of a story as we can to be helpful.
285 // We'll iteratively removed "satisfied" input/argument pairs,
286 // then check for the cases above, until we've eliminated the entire grid
288 // We'll want to know which arguments and inputs these rows and columns correspond to
289 // even after we delete them.
290 pub(crate) fn find_errors(
292 ) -> (Vec<Error<'tcx>>, IndexVec<ExpectedIdx, Option<ProvidedIdx>>) {
293 let provided_arg_count = self.provided_indices.len();
295 let mut errors: Vec<Error<'tcx>> = vec![];
296 // For each expected argument, the matched *actual* input
297 let mut matched_inputs: IndexVec<ExpectedIdx, Option<ProvidedIdx>> =
298 IndexVec::from_elem_n(None, self.expected_indices.len());
300 // Before we start looking for issues, eliminate any arguments that are already satisfied,
301 // so that an argument which is already spoken for by the input it's in doesn't
302 // spill over into another similarly typed input
304 // fn some_func(_a: i32, _b: i32) {}
306 // Without this elimination, the first argument causes the second argument
307 // to show up as both a missing input and extra argument, rather than
308 // just an invalid type.
309 for (provided, expected) in self.eliminate_satisfied() {
310 matched_inputs[expected] = Some(provided);
313 while !self.provided_indices.is_empty() || !self.expected_indices.is_empty() {
314 let res = self.find_issue();
316 Some(Issue::Invalid(idx)) => {
317 let compatibility = self.compatibility_matrix[idx][idx].clone();
318 let input_idx = self.provided_indices[idx];
319 let arg_idx = self.expected_indices[idx];
320 self.satisfy_input(idx, idx);
321 errors.push(Error::Invalid(input_idx, arg_idx, compatibility));
323 Some(Issue::Extra(idx)) => {
324 let input_idx = self.provided_indices[idx];
325 self.eliminate_provided(idx);
326 errors.push(Error::Extra(input_idx));
328 Some(Issue::Missing(idx)) => {
329 let arg_idx = self.expected_indices[idx];
330 self.eliminate_expected(idx);
331 errors.push(Error::Missing(arg_idx));
333 Some(Issue::Swap(idx, other)) => {
334 let input_idx = self.provided_indices[idx];
335 let other_input_idx = self.provided_indices[other];
336 let arg_idx = self.expected_indices[idx];
337 let other_arg_idx = self.expected_indices[other];
338 let (min, max) = (cmp::min(idx, other), cmp::max(idx, other));
339 self.satisfy_input(min, max);
340 // Subtract 1 because we already removed the "min" row
341 self.satisfy_input(max - 1, min);
342 errors.push(Error::Swap(input_idx, other_input_idx, arg_idx, other_arg_idx));
343 matched_inputs[other_arg_idx] = Some(input_idx);
344 matched_inputs[arg_idx] = Some(other_input_idx);
346 Some(Issue::Permutation(args)) => {
347 let mut idxs: Vec<usize> = args.iter().filter_map(|&a| a).collect();
349 let mut real_idxs: IndexVec<ProvidedIdx, Option<(ExpectedIdx, ProvidedIdx)>> =
350 IndexVec::from_elem_n(None, provided_arg_count);
352 args.iter().enumerate().filter_map(|(src, dst)| dst.map(|dst| (src, dst)))
354 let src_input_idx = self.provided_indices[src];
355 let dst_input_idx = self.provided_indices[dst];
356 let dest_arg_idx = self.expected_indices[dst];
357 real_idxs[src_input_idx] = Some((dest_arg_idx, dst_input_idx));
358 matched_inputs[dest_arg_idx] = Some(src_input_idx);
363 self.satisfy_input(i, i);
365 errors.push(Error::Permutation(real_idxs.into_iter().flatten().collect()));
368 // We didn't find any issues, so we need to push the algorithm forward
369 // First, eliminate any arguments that currently satisfy their inputs
370 let eliminated = self.eliminate_satisfied();
371 assert!(!eliminated.is_empty(), "didn't eliminated any indice in this round");
372 for (inp, arg) in eliminated {
373 matched_inputs[arg] = Some(inp);
379 return (errors, matched_inputs);