Skip to content

Commit 4ac2425

Browse files
borsbors
committed
Auto merge of #48296 - ishitatsuyuki:exp-unblow, r=<try>
Fix exponential projection complexity on nested types This implements solution 1 from #38528 (comment). The code quality is currently extremely poor, but we can improve them during review. Blocking issues: - we probably don't want a quadratic deduplication for obligations. - is there an alternative to deduplication? Based on #48315. Needs changelog. Noticable improvement on compile time is expected. Fix #38528 Close #39684 Close #43757
2 parents 1ad094d + 4a40c55 commit 4ac2425

File tree

6 files changed

+111
-119
lines changed

6 files changed

+111
-119
lines changed

‎src/librustc/traits/mod.rs

+3-3
Original file line numberDiff line numberDiff line change
@@ -304,7 +304,7 @@ pub type SelectionResult<'tcx, T> = Result<Option<T>, SelectionError<'tcx>>;
304304
/// ### The type parameter `N`
305305
///
306306
/// See explanation on `VtableImplData`.
307-
#[derive(Clone, RustcEncodable, RustcDecodable)]
307+
#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable)]
308308
pub enum Vtable<'tcx, N> {
309309
/// Vtable identifying a particular impl.
310310
VtableImpl(VtableImplData<'tcx, N>),
@@ -374,13 +374,13 @@ pub struct VtableClosureData<'tcx, N> {
374374
pub nested: Vec<N>
375375
}
376376

377-
#[derive(Clone, RustcEncodable, RustcDecodable)]
377+
#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable)]
378378
pub struct VtableAutoImplData<N> {
379379
pub trait_def_id: DefId,
380380
pub nested: Vec<N>
381381
}
382382

383-
#[derive(Clone, RustcEncodable, RustcDecodable)]
383+
#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable)]
384384
pub struct VtableBuiltinData<N> {
385385
pub nested: Vec<N>
386386
}

‎src/librustc/traits/project.rs

+92-83
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,7 @@ use super::translate_substs;
1616
use super::Obligation;
1717
use super::ObligationCause;
1818
use super::PredicateObligation;
19+
use super::Selection;
1920
use super::SelectionContext;
2021
use super::SelectionError;
2122
use super::VtableClosureData;
@@ -101,7 +102,7 @@ pub struct MismatchedProjectionTypes<'tcx> {
101102
pub err: ty::error::TypeError<'tcx>
102103
}
103104

104-
#[derive(PartialEq, Eq, PartialOrd, Ord, Debug)]
105+
#[derive(PartialEq, Eq, Debug)]
105106
enum ProjectionTyCandidate<'tcx> {
106107
// from a where-clause in the env or object type
107108
ParamEnv(ty::PolyProjectionPredicate<'tcx>),
@@ -110,7 +111,7 @@ enum ProjectionTyCandidate<'tcx> {
110111
TraitDef(ty::PolyProjectionPredicate<'tcx>),
111112

112113
// from a "impl" (or a "pseudo-impl" returned by select)
113-
Select,
114+
Select(Selection<'tcx>),
114115
}
115116

116117
struct ProjectionTyCandidateSet<'tcx> {
@@ -818,55 +819,57 @@ fn project_type<'cx, 'gcx, 'tcx>(
818819
&obligation_trait_ref,
819820
&mut candidates);
820821

822+
let decide_commit = |candidates: &mut ProjectionTyCandidateSet<'tcx>| {
823+
debug!("{} candidates, ambiguous={}",
824+
candidates.vec.len(),
825+
candidates.ambiguous);
826+
827+
// Prefer where-clauses. As in select, if there are multiple
828+
// candidates, we prefer where-clause candidates over impls. This
829+
// may seem a bit surprising, since impls are the source of
830+
// "truth" in some sense, but in fact some of the impls that SEEM
831+
// applicable are not, because of nested obligations. Where
832+
// clauses are the safer choice. See the comment on
833+
// `select::SelectionCandidate` and #21974 for more details.
834+
if candidates.vec.len() > 1 {
835+
debug!("retaining param-env candidates only from {:?}", candidates.vec);
836+
candidates.vec.retain(|c| match *c {
837+
ProjectionTyCandidate::ParamEnv(..) => true,
838+
ProjectionTyCandidate::TraitDef(..) |
839+
ProjectionTyCandidate::Select(..) => false,
840+
});
841+
debug!("resulting candidate set: {:?}", candidates.vec);
842+
if candidates.vec.len() != 1 {
843+
candidates.ambiguous = true;
844+
return false;
845+
}
846+
}
847+
848+
assert!(candidates.vec.len() <= 1);
849+
match candidates.vec.get(0) {
850+
Some(&ProjectionTyCandidate::Select(..)) => true,
851+
_ => false,
852+
}
853+
};
854+
855+
// Note that at here, if `ProjectionTyCandidate::Select` is not going to be
856+
// a valid candidate, the closure is not executed at all. There are two cases,
857+
// one being trait selection error, and another being ambiguous candidates.
858+
// We handle both by the early return below.
821859
if let Err(e) = assemble_candidates_from_impls(selcx,
822860
obligation,
823861
&obligation_trait_ref,
824-
&mut candidates) {
862+
&mut candidates,
863+
decide_commit) {
825864
return Err(ProjectionTyError::TraitSelectionError(e));
826865
}
827866

828-
debug!("{} candidates, ambiguous={}",
829-
candidates.vec.len(),
830-
candidates.ambiguous);
831-
832867
// Inherent ambiguity that prevents us from even enumerating the
833868
// candidates.
834869
if candidates.ambiguous {
835870
return Err(ProjectionTyError::TooManyCandidates);
836871
}
837872

838-
// Drop duplicates.
839-
//
840-
// Note: `candidates.vec` seems to be on the critical path of the
841-
// compiler. Replacing it with an HashSet was also tried, which would
842-
// render the following dedup unnecessary. The original comment indicated
843-
// that it was 9% slower, but that data is now obsolete and a new
844-
// benchmark should be performed.
845-
candidates.vec.sort_unstable();
846-
candidates.vec.dedup();
847-
848-
// Prefer where-clauses. As in select, if there are multiple
849-
// candidates, we prefer where-clause candidates over impls. This
850-
// may seem a bit surprising, since impls are the source of
851-
// "truth" in some sense, but in fact some of the impls that SEEM
852-
// applicable are not, because of nested obligations. Where
853-
// clauses are the safer choice. See the comment on
854-
// `select::SelectionCandidate` and #21974 for more details.
855-
if candidates.vec.len() > 1 {
856-
debug!("retaining param-env candidates only from {:?}", candidates.vec);
857-
candidates.vec.retain(|c| match *c {
858-
ProjectionTyCandidate::ParamEnv(..) => true,
859-
ProjectionTyCandidate::TraitDef(..) |
860-
ProjectionTyCandidate::Select => false,
861-
});
862-
debug!("resulting candidate set: {:?}", candidates.vec);
863-
if candidates.vec.len() != 1 {
864-
return Err(ProjectionTyError::TooManyCandidates);
865-
}
866-
}
867-
868-
assert!(candidates.vec.len() <= 1);
869-
870873
match candidates.vec.pop() {
871874
Some(candidate) => {
872875
Ok(ProjectedTy::Progress(
@@ -962,7 +965,7 @@ fn assemble_candidates_from_predicates<'cx, 'gcx, 'tcx, I>(
962965
debug!("assemble_candidates_from_predicates: predicate={:?}",
963966
predicate);
964967
match predicate {
965-
ty::Predicate::Projection(ref data) => {
968+
ty::Predicate::Projection(data) => {
966969
let same_def_id =
967970
data.0.projection_ty.item_def_id == obligation.predicate.item_def_id;
968971

@@ -985,26 +988,33 @@ fn assemble_candidates_from_predicates<'cx, 'gcx, 'tcx, I>(
985988
data, is_match, same_def_id);
986989

987990
if is_match {
988-
candidate_set.vec.push(ctor(data.clone()));
991+
candidate_set.vec.push(ctor(data));
989992
}
990993
}
991-
_ => { }
994+
_ => {}
992995
}
993996
}
994997
}
995998

996-
fn assemble_candidates_from_impls<'cx, 'gcx, 'tcx>(
999+
enum NoImplCandidateError<'tcx> {
1000+
CanceledCommit,
1001+
SelectionError(SelectionError<'tcx>),
1002+
}
1003+
1004+
fn assemble_candidates_from_impls<'cx, 'gcx, 'tcx,
1005+
F: FnOnce(&mut ProjectionTyCandidateSet<'tcx>) -> bool>(
9971006
selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
9981007
obligation: &ProjectionTyObligation<'tcx>,
9991008
obligation_trait_ref: &ty::TraitRef<'tcx>,
1000-
candidate_set: &mut ProjectionTyCandidateSet<'tcx>)
1009+
candidate_set: &mut ProjectionTyCandidateSet<'tcx>,
1010+
decide_commit: F)
10011011
-> Result<(), SelectionError<'tcx>>
10021012
{
10031013
// If we are resolving `<T as TraitRef<...>>::Item == Type`,
10041014
// start out by selecting the predicate `T as TraitRef<...>`:
10051015
let poly_trait_ref = obligation_trait_ref.to_poly_trait_ref();
10061016
let trait_obligation = obligation.with(poly_trait_ref.to_poly_trait_predicate());
1007-
selcx.infcx().probe(|_| {
1017+
match selcx.infcx().commit_if_ok(|_| {
10081018
let vtable = match selcx.select(&trait_obligation) {
10091019
Ok(Some(vtable)) => vtable,
10101020
Ok(None) => {
@@ -1014,21 +1024,20 @@ fn assemble_candidates_from_impls<'cx, 'gcx, 'tcx>(
10141024
Err(e) => {
10151025
debug!("assemble_candidates_from_impls: selection error {:?}",
10161026
e);
1017-
return Err(e);
1027+
return Err(NoImplCandidateError::SelectionError(e));
10181028
}
10191029
};
10201030

1021-
match vtable {
1022-
super::VtableClosure(_) |
1023-
super::VtableGenerator(_) |
1024-
super::VtableFnPointer(_) |
1025-
super::VtableObject(_) => {
1031+
let eligible = match &vtable {
1032+
&super::VtableClosure(_) |
1033+
&super::VtableGenerator(_) |
1034+
&super::VtableFnPointer(_) |
1035+
&super::VtableObject(_) => {
10261036
debug!("assemble_candidates_from_impls: vtable={:?}",
10271037
vtable);
1028-
1029-
candidate_set.vec.push(ProjectionTyCandidate::Select);
1038+
true
10301039
}
1031-
super::VtableImpl(ref impl_data) => {
1040+
&super::VtableImpl(ref impl_data) => {
10321041
// We have to be careful when projecting out of an
10331042
// impl because of specialization. If we are not in
10341043
// trans (i.e., projection mode is not "any"), and the
@@ -1072,29 +1081,27 @@ fn assemble_candidates_from_impls<'cx, 'gcx, 'tcx>(
10721081
node_item.item.defaultness.has_value()
10731082
} else {
10741083
node_item.item.defaultness.is_default() ||
1075-
selcx.tcx().impl_is_default(node_item.node.def_id())
1084+
selcx.tcx().impl_is_default(node_item.node.def_id())
10761085
};
10771086

10781087
// Only reveal a specializable default if we're past type-checking
10791088
// and the obligations is monomorphic, otherwise passes such as
10801089
// transmute checking and polymorphic MIR optimizations could
10811090
// get a result which isn't correct for all monomorphizations.
1082-
let new_candidate = if !is_default {
1083-
Some(ProjectionTyCandidate::Select)
1091+
if !is_default {
1092+
true
10841093
} else if obligation.param_env.reveal == Reveal::All {
10851094
assert!(!poly_trait_ref.needs_infer());
10861095
if !poly_trait_ref.needs_subst() {
1087-
Some(ProjectionTyCandidate::Select)
1096+
true
10881097
} else {
1089-
None
1098+
false
10901099
}
10911100
} else {
1092-
None
1093-
};
1094-
1095-
candidate_set.vec.extend(new_candidate);
1101+
false
1102+
}
10961103
}
1097-
super::VtableParam(..) => {
1104+
&super::VtableParam(..) => {
10981105
// This case tell us nothing about the value of an
10991106
// associated type. Consider:
11001107
//
@@ -1120,19 +1127,32 @@ fn assemble_candidates_from_impls<'cx, 'gcx, 'tcx>(
11201127
// in the compiler: a trait predicate (`T : SomeTrait`) and a
11211128
// projection. And the projection where clause is handled
11221129
// in `assemble_candidates_from_param_env`.
1130+
false
11231131
}
1124-
super::VtableAutoImpl(..) |
1125-
super::VtableBuiltin(..) => {
1132+
&super::VtableAutoImpl(..) |
1133+
&super::VtableBuiltin(..) => {
11261134
// These traits have no associated types.
11271135
span_bug!(
11281136
obligation.cause.span,
11291137
"Cannot project an associated type from `{:?}`",
11301138
vtable);
11311139
}
1140+
};
1141+
1142+
if eligible {
1143+
candidate_set.vec.push(ProjectionTyCandidate::Select(vtable));
11321144
}
11331145

1134-
Ok(())
1135-
})
1146+
if decide_commit(candidate_set) {
1147+
Ok(())
1148+
} else {
1149+
Err(NoImplCandidateError::CanceledCommit)
1150+
}
1151+
}) {
1152+
Ok(()) => Ok(()),
1153+
Err(NoImplCandidateError::CanceledCommit) => Ok(()),
1154+
Err(NoImplCandidateError::SelectionError(e)) => Err(e),
1155+
}
11361156
}
11371157

11381158
fn confirm_candidate<'cx, 'gcx, 'tcx>(
@@ -1152,30 +1172,19 @@ fn confirm_candidate<'cx, 'gcx, 'tcx>(
11521172
confirm_param_env_candidate(selcx, obligation, poly_projection)
11531173
}
11541174

1155-
ProjectionTyCandidate::Select => {
1156-
confirm_select_candidate(selcx, obligation, obligation_trait_ref)
1175+
ProjectionTyCandidate::Select(vtable) => {
1176+
confirm_select_candidate(selcx, obligation, obligation_trait_ref, vtable)
11571177
}
11581178
}
11591179
}
11601180

11611181
fn confirm_select_candidate<'cx, 'gcx, 'tcx>(
11621182
selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
11631183
obligation: &ProjectionTyObligation<'tcx>,
1164-
obligation_trait_ref: &ty::TraitRef<'tcx>)
1184+
obligation_trait_ref: &ty::TraitRef<'tcx>,
1185+
vtable: Selection<'tcx>)
11651186
-> Progress<'tcx>
11661187
{
1167-
let poly_trait_ref = obligation_trait_ref.to_poly_trait_ref();
1168-
let trait_obligation = obligation.with(poly_trait_ref.to_poly_trait_predicate());
1169-
let vtable = match selcx.select(&trait_obligation) {
1170-
Ok(Some(vtable)) => vtable,
1171-
_ => {
1172-
span_bug!(
1173-
obligation.cause.span,
1174-
"Failed to select `{:?}`",
1175-
trait_obligation);
1176-
}
1177-
};
1178-
11791188
match vtable {
11801189
super::VtableImpl(data) =>
11811190
confirm_impl_candidate(selcx, obligation, data),

‎src/librustc/traits/select.rs

+12-1
Original file line numberDiff line numberDiff line change
@@ -3282,7 +3282,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
32823282
// that order.
32833283
let predicates = tcx.predicates_of(def_id);
32843284
assert_eq!(predicates.parent, None);
3285-
let predicates = predicates.predicates.iter().flat_map(|predicate| {
3285+
let mut predicates: Vec<_> = predicates.predicates.iter().flat_map(|predicate| {
32863286
let predicate = normalize_with_depth(self, param_env, cause.clone(), recursion_depth,
32873287
&predicate.subst(tcx, substs));
32883288
predicate.obligations.into_iter().chain(
@@ -3293,6 +3293,17 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
32933293
predicate: predicate.value
32943294
}))
32953295
}).collect();
3296+
if predicates.len() > 1 {
3297+
let mut i = 0;
3298+
while i != predicates.len() {
3299+
let has_dup = (0..i).any(|j| predicates[i] == predicates[j]);
3300+
if has_dup {
3301+
predicates.swap_remove(i);
3302+
} else {
3303+
i += 1;
3304+
}
3305+
}
3306+
}
32963307
self.infcx().plug_leaks(skol_map, snapshot, predicates)
32973308
}
32983309
}

0 commit comments

Comments
 (0)