bail out of selection when there are multiple surviving candidates

In some cases (e.g. <[int-var] as Add<[int-var]>>), selection can turn up
a large number of candidates. Bailing out early avoids O(n^2) performance.

This improves item-type checking time by quite a bit, resulting in ~2% of total
time-to-typeck.

1 files changed, 7 insertions, 7 deletions

diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index 70ddcff5181..6442487ead9 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -943,17 +943,17 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                     debug!("Retaining candidate #{}/{}: {:?}",
                            i, candidates.len(), candidates[i]);
                     i += 1;
+
+                    // If there are *STILL* multiple candidates, give up
+                    // and report ambiguity.
+                    if i > 1 {
+                        debug!("multiple matches, ambig");
+                        return Ok(None);
+                    }
                 }
             }
         }
 
-        // If there are *STILL* multiple candidates, give up and
-        // report ambiguity.
-        if candidates.len() > 1 {
-            debug!("multiple matches, ambig");
-            return Ok(None);
-        }
-
         // If there are *NO* candidates, then there are no impls --
         // that we know of, anyway. Note that in the case where there
         // are unbound type variables within the obligation, it might