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 for i in 0..cmp::max(ai.len(), ii.len()) {
134 // If we eliminate the last row, any left-over inputs are considered missing
136 return Some(Issue::Missing(i));
138 // If we eliminate the last column, any left-over arguments are extra
139 if mat[i].len() == 0 {
140 return Some(Issue::Extra(i));
143 // Make sure we don't pass the bounds of our matrix
144 let is_arg = i < ai.len();
145 let is_input = i < ii.len();
146 if is_arg && is_input && matches!(mat[i][i], Compatibility::Compatible) {
147 // This is a satisfied input, so move along
151 let mut useless = true;
152 let mut unsatisfiable = true;
154 for j in 0..ii.len() {
155 // If we find at least one input this argument could satisfy
156 // this argument isn't unsatisfiable
157 if matches!(mat[j][i], Compatibility::Compatible) {
158 unsatisfiable = false;
164 for j in 0..ai.len() {
165 // If we find at least one argument that could satisfy this input
166 // this argument isn't useless
167 if matches!(mat[i][j], Compatibility::Compatible) {
174 match (is_input, is_arg, useless, unsatisfiable) {
175 // If an argument is unsatisfied, and the input in its position is useless
176 // then the most likely explanation is that we just got the types wrong
177 (true, true, true, true) => return Some(Issue::Invalid(i)),
178 // Otherwise, if an input is useless, then indicate that this is an extra argument
179 (true, _, true, _) => return Some(Issue::Extra(i)),
180 // Otherwise, if an argument is unsatisfiable, indicate that it's missing
181 (_, true, _, true) => return Some(Issue::Missing(i)),
182 (true, true, _, _) => {
183 // The argument isn't useless, and the input isn't unsatisfied,
184 // so look for a parameter we might swap it with
185 // We look for swaps explicitly, instead of just falling back on permutations
186 // so that cases like (A,B,C,D) given (B,A,D,C) show up as two swaps,
187 // instead of a large permutation of 4 elements.
188 for j in 0..cmp::min(ai.len(), ii.len()) {
189 if i == j || matches!(mat[j][j], Compatibility::Compatible) {
192 if matches!(mat[i][j], Compatibility::Compatible)
193 && matches!(mat[j][i], Compatibility::Compatible)
195 return Some(Issue::Swap(i, j));
205 // We didn't find any of the individual issues above, but
206 // there might be a larger permutation of parameters, so we now check for that
207 // by checking for cycles
208 // We use a double option at position i in this vec to represent:
209 // - None: We haven't computed anything about this argument yet
210 // - Some(None): This argument definitely doesn't participate in a cycle
211 // - Some(Some(x)): the i-th argument could permute to the x-th position
212 let mut permutation: Vec<Option<Option<usize>>> = vec![None; mat.len()];
213 let mut permutation_found = false;
214 for i in 0..mat.len() {
215 if permutation[i].is_some() {
216 // We've already decided whether this argument is or is not in a loop
220 let mut stack = vec![];
223 let mut is_cycle = true;
226 // Look for params this one could slot into
231 .filter_map(|(i, c)| {
232 if matches!(c, Compatibility::Compatible) { Some(i) } else { None }
235 if compat.len() != 1 {
236 // this could go into multiple slots, don't bother exploring both
241 if stack.contains(&j) {
246 if stack.len() <= 2 {
247 // If we encounter a cycle of 1 or 2 elements, we'll let the
248 // "satisfy" and "swap" code above handle those
251 // We've built up some chain, some of which might be a cycle
252 // ex: [1,2,3,4]; last = 2; j = 2;
253 // So, we want to mark 4, 3, and 2 as part of a permutation
254 permutation_found = is_cycle;
255 while let Some(x) = stack.pop() {
257 permutation[x] = Some(Some(j));
260 // From here on out, we're a tail leading into a cycle,
261 // not the cycle itself
265 // Some(None) ensures we save time by skipping this argument again
266 permutation[x] = Some(None);
271 if permutation_found {
272 // Map unwrap to remove the first layer of Some
273 let final_permutation: Vec<Option<usize>> =
274 permutation.into_iter().map(|x| x.unwrap()).collect();
275 return Some(Issue::Permutation(final_permutation));
280 // Obviously, detecting exact user intention is impossible, so the goal here is to
281 // come up with as likely of a story as we can to be helpful.
283 // We'll iteratively removed "satisfied" input/argument pairs,
284 // then check for the cases above, until we've eliminated the entire grid
286 // We'll want to know which arguments and inputs these rows and columns correspond to
287 // even after we delete them.
288 pub(crate) fn find_errors(
290 ) -> (Vec<Error<'tcx>>, IndexVec<ExpectedIdx, Option<ProvidedIdx>>) {
291 let provided_arg_count = self.provided_indices.len();
293 let mut errors: Vec<Error<'tcx>> = vec![];
294 // For each expected argument, the matched *actual* input
295 let mut matched_inputs: IndexVec<ExpectedIdx, Option<ProvidedIdx>> =
296 IndexVec::from_elem_n(None, self.expected_indices.len());
298 // Before we start looking for issues, eliminate any arguments that are already satisfied,
299 // so that an argument which is already spoken for by the input it's in doesn't
300 // spill over into another similarly typed input
302 // fn some_func(_a: i32, _b: i32) {}
304 // Without this elimination, the first argument causes the second argument
305 // to show up as both a missing input and extra argument, rather than
306 // just an invalid type.
307 for (provided, expected) in self.eliminate_satisfied() {
308 matched_inputs[expected] = Some(provided);
311 while !self.provided_indices.is_empty() || !self.expected_indices.is_empty() {
312 match self.find_issue() {
313 Some(Issue::Invalid(idx)) => {
314 let compatibility = self.compatibility_matrix[idx][idx].clone();
315 let input_idx = self.provided_indices[idx];
316 let arg_idx = self.expected_indices[idx];
317 self.satisfy_input(idx, idx);
318 errors.push(Error::Invalid(input_idx, arg_idx, compatibility));
320 Some(Issue::Extra(idx)) => {
321 let input_idx = self.provided_indices[idx];
322 self.eliminate_provided(idx);
323 errors.push(Error::Extra(input_idx));
325 Some(Issue::Missing(idx)) => {
326 let arg_idx = self.expected_indices[idx];
327 self.eliminate_expected(idx);
328 errors.push(Error::Missing(arg_idx));
330 Some(Issue::Swap(idx, other)) => {
331 let input_idx = self.provided_indices[idx];
332 let other_input_idx = self.provided_indices[other];
333 let arg_idx = self.expected_indices[idx];
334 let other_arg_idx = self.expected_indices[other];
335 let (min, max) = (cmp::min(idx, other), cmp::max(idx, other));
336 self.satisfy_input(min, max);
337 // Subtract 1 because we already removed the "min" row
338 self.satisfy_input(max - 1, min);
339 errors.push(Error::Swap(input_idx, other_input_idx, arg_idx, other_arg_idx));
340 matched_inputs[other_arg_idx] = Some(input_idx);
341 matched_inputs[arg_idx] = Some(other_input_idx);
343 Some(Issue::Permutation(args)) => {
344 let mut idxs: Vec<usize> = args.iter().filter_map(|&a| a).collect();
346 let mut real_idxs: IndexVec<ProvidedIdx, Option<(ExpectedIdx, ProvidedIdx)>> =
347 IndexVec::from_elem_n(None, provided_arg_count);
349 args.iter().enumerate().filter_map(|(src, dst)| dst.map(|dst| (src, dst)))
351 let src_input_idx = self.provided_indices[src];
352 let dst_input_idx = self.provided_indices[dst];
353 let dest_arg_idx = self.expected_indices[dst];
354 real_idxs[src_input_idx] = Some((dest_arg_idx, dst_input_idx));
355 matched_inputs[dest_arg_idx] = Some(src_input_idx);
360 self.satisfy_input(i, i);
362 errors.push(Error::Permutation(real_idxs.into_iter().flatten().collect()));
365 // We didn't find any issues, so we need to push the algorithm forward
366 // First, eliminate any arguments that currently satisfy their inputs
367 for (inp, arg) in self.eliminate_satisfied() {
368 matched_inputs[arg] = Some(inp);
374 return (errors, matched_inputs);