Swap PredicateObligation to ThinVec

12 files changed, 73 insertions, 42 deletions

diff --git a/Cargo.lock b/Cargo.lock
index c62c379f70d..501d143890b 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -1,6 +1,6 @@
 # This file is automatically @generated by Cargo.
 # It is not intended for manual editing.
-version = 3
+version = 4
 
 [[package]]
 name = "addr2line"
@@ -3857,6 +3857,7 @@ dependencies = [
  "rustc_target",
  "rustc_type_ir",
  "smallvec",
+ "thin-vec",
  "tracing",
 ]
 
@@ -4490,6 +4491,7 @@ dependencies = [
  "rustc_transmute",
  "rustc_type_ir",
  "smallvec",
+ "thin-vec",
  "tracing",
 ]
 
@@ -4561,6 +4563,7 @@ dependencies = [
  "rustc_span",
  "rustc_type_ir_macros",
  "smallvec",
+ "thin-vec",
  "tracing",
 ]
 
diff --git a/compiler/rustc_data_structures/src/obligation_forest/mod.rs b/compiler/rustc_data_structures/src/obligation_forest/mod.rs
index aca99b9fab1..34a2464972a 100644
--- a/compiler/rustc_data_structures/src/obligation_forest/mod.rs
+++ b/compiler/rustc_data_structures/src/obligation_forest/mod.rs
@@ -75,6 +75,7 @@ use std::fmt::Debug;
 use std::hash;
 use std::marker::PhantomData;
 
+use thin_vec::ThinVec;
 use tracing::debug;
 
 use crate::fx::{FxHashMap, FxHashSet};
@@ -141,7 +142,7 @@ pub trait ObligationProcessor {
 #[derive(Debug)]
 pub enum ProcessResult<O, E> {
     Unchanged,
-    Changed(Vec<O>),
+    Changed(ThinVec<O>),
     Error(E),
 }
 
diff --git a/compiler/rustc_data_structures/src/obligation_forest/tests.rs b/compiler/rustc_data_structures/src/obligation_forest/tests.rs
index 8391e98ba8b..739ef74e3f7 100644
--- a/compiler/rustc_data_structures/src/obligation_forest/tests.rs
+++ b/compiler/rustc_data_structures/src/obligation_forest/tests.rs
@@ -1,5 +1,7 @@
 use std::fmt;
 
+use thin_vec::thin_vec;
+
 use super::*;
 
 impl<'a> super::ForestObligation for &'a str {
@@ -101,9 +103,9 @@ fn push_pop() {
     //        |-> A.3
     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
         |obligation| match *obligation {
-            "A" => ProcessResult::Changed(vec!["A.1", "A.2", "A.3"]),
+            "A" => ProcessResult::Changed(thin_vec!["A.1", "A.2", "A.3"]),
             "B" => ProcessResult::Error("B is for broken"),
-            "C" => ProcessResult::Changed(vec![]),
+            "C" => ProcessResult::Changed(thin_vec![]),
             "A.1" | "A.2" | "A.3" => ProcessResult::Unchanged,
             _ => unreachable!(),
         },
@@ -123,8 +125,8 @@ fn push_pop() {
         |obligation| match *obligation {
             "A.1" => ProcessResult::Unchanged,
             "A.2" => ProcessResult::Unchanged,
-            "A.3" => ProcessResult::Changed(vec!["A.3.i"]),
-            "D" => ProcessResult::Changed(vec!["D.1", "D.2"]),
+            "A.3" => ProcessResult::Changed(thin_vec!["A.3.i"]),
+            "D" => ProcessResult::Changed(thin_vec!["D.1", "D.2"]),
             "A.3.i" | "D.1" | "D.2" => ProcessResult::Unchanged,
             _ => unreachable!(),
         },
@@ -139,11 +141,11 @@ fn push_pop() {
     //        |-> D.2 |-> D.2.i
     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
         |obligation| match *obligation {
-            "A.1" => ProcessResult::Changed(vec![]),
+            "A.1" => ProcessResult::Changed(thin_vec![]),
             "A.2" => ProcessResult::Error("A is for apple"),
-            "A.3.i" => ProcessResult::Changed(vec![]),
-            "D.1" => ProcessResult::Changed(vec!["D.1.i"]),
-            "D.2" => ProcessResult::Changed(vec!["D.2.i"]),
+            "A.3.i" => ProcessResult::Changed(thin_vec![]),
+            "D.1" => ProcessResult::Changed(thin_vec!["D.1.i"]),
+            "D.2" => ProcessResult::Changed(thin_vec!["D.2.i"]),
             "D.1.i" | "D.2.i" => ProcessResult::Unchanged,
             _ => unreachable!(),
         },
@@ -158,7 +160,7 @@ fn push_pop() {
     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
         |obligation| match *obligation {
             "D.1.i" => ProcessResult::Error("D is for dumb"),
-            "D.2.i" => ProcessResult::Changed(vec![]),
+            "D.2.i" => ProcessResult::Changed(thin_vec![]),
             _ => panic!("unexpected obligation {:?}", obligation),
         },
         |_| {},
@@ -184,10 +186,10 @@ fn success_in_grandchildren() {
 
     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
         |obligation| match *obligation {
-            "A" => ProcessResult::Changed(vec!["A.1", "A.2", "A.3"]),
-            "A.1" => ProcessResult::Changed(vec![]),
-            "A.2" => ProcessResult::Changed(vec!["A.2.i", "A.2.ii"]),
-            "A.3" => ProcessResult::Changed(vec![]),
+            "A" => ProcessResult::Changed(thin_vec!["A.1", "A.2", "A.3"]),
+            "A.1" => ProcessResult::Changed(thin_vec![]),
+            "A.2" => ProcessResult::Changed(thin_vec!["A.2.i", "A.2.ii"]),
+            "A.3" => ProcessResult::Changed(thin_vec![]),
             "A.2.i" | "A.2.ii" => ProcessResult::Unchanged,
             _ => unreachable!(),
         },
@@ -201,7 +203,7 @@ fn success_in_grandchildren() {
     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
         |obligation| match *obligation {
             "A.2.i" => ProcessResult::Unchanged,
-            "A.2.ii" => ProcessResult::Changed(vec![]),
+            "A.2.ii" => ProcessResult::Changed(thin_vec![]),
             _ => unreachable!(),
         },
         |_| {},
@@ -211,7 +213,7 @@ fn success_in_grandchildren() {
 
     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
         |obligation| match *obligation {
-            "A.2.i" => ProcessResult::Changed(vec!["A.2.i.a"]),
+            "A.2.i" => ProcessResult::Changed(thin_vec!["A.2.i.a"]),
             "A.2.i.a" => ProcessResult::Unchanged,
             _ => unreachable!(),
         },
@@ -222,7 +224,7 @@ fn success_in_grandchildren() {
 
     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
         |obligation| match *obligation {
-            "A.2.i.a" => ProcessResult::Changed(vec![]),
+            "A.2.i.a" => ProcessResult::Changed(thin_vec![]),
             _ => unreachable!(),
         },
         |_| {},
@@ -247,7 +249,7 @@ fn to_errors_no_throw() {
     forest.register_obligation("A");
     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
         |obligation| match *obligation {
-            "A" => ProcessResult::Changed(vec!["A.1", "A.2", "A.3"]),
+            "A" => ProcessResult::Changed(thin_vec!["A.1", "A.2", "A.3"]),
             "A.1" | "A.2" | "A.3" => ProcessResult::Unchanged,
             _ => unreachable!(),
         },
@@ -269,7 +271,7 @@ fn diamond() {
     forest.register_obligation("A");
     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
         |obligation| match *obligation {
-            "A" => ProcessResult::Changed(vec!["A.1", "A.2"]),
+            "A" => ProcessResult::Changed(thin_vec!["A.1", "A.2"]),
             "A.1" | "A.2" => ProcessResult::Unchanged,
             _ => unreachable!(),
         },
@@ -280,8 +282,8 @@ fn diamond() {
 
     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
         |obligation| match *obligation {
-            "A.1" => ProcessResult::Changed(vec!["D"]),
-            "A.2" => ProcessResult::Changed(vec!["D"]),
+            "A.1" => ProcessResult::Changed(thin_vec!["D"]),
+            "A.2" => ProcessResult::Changed(thin_vec!["D"]),
             "D" => ProcessResult::Unchanged,
             _ => unreachable!(),
         },
@@ -295,7 +297,7 @@ fn diamond() {
         |obligation| match *obligation {
             "D" => {
                 d_count += 1;
-                ProcessResult::Changed(vec![])
+                ProcessResult::Changed(thin_vec![])
             }
             _ => unreachable!(),
         },
@@ -313,7 +315,7 @@ fn diamond() {
     forest.register_obligation("A'");
     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
         |obligation| match *obligation {
-            "A'" => ProcessResult::Changed(vec!["A'.1", "A'.2"]),
+            "A'" => ProcessResult::Changed(thin_vec!["A'.1", "A'.2"]),
             "A'.1" | "A'.2" => ProcessResult::Unchanged,
             _ => unreachable!(),
         },
@@ -324,8 +326,8 @@ fn diamond() {
 
     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
         |obligation| match *obligation {
-            "A'.1" => ProcessResult::Changed(vec!["D'", "A'"]),
-            "A'.2" => ProcessResult::Changed(vec!["D'"]),
+            "A'.1" => ProcessResult::Changed(thin_vec!["D'", "A'"]),
+            "A'.2" => ProcessResult::Changed(thin_vec!["D'"]),
             "D'" | "A'" => ProcessResult::Unchanged,
             _ => unreachable!(),
         },
@@ -366,7 +368,7 @@ fn done_dependency() {
 
     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
         |obligation| match *obligation {
-            "A: Sized" | "B: Sized" | "C: Sized" => ProcessResult::Changed(vec![]),
+            "A: Sized" | "B: Sized" | "C: Sized" => ProcessResult::Changed(thin_vec![]),
             _ => unreachable!(),
         },
         |_| {},
@@ -379,7 +381,9 @@ fn done_dependency() {
     forest.register_obligation("(A,B,C): Sized");
     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
         |obligation| match *obligation {
-            "(A,B,C): Sized" => ProcessResult::Changed(vec!["A: Sized", "B: Sized", "C: Sized"]),
+            "(A,B,C): Sized" => {
+                ProcessResult::Changed(thin_vec!["A: Sized", "B: Sized", "C: Sized"])
+            }
             _ => unreachable!(),
         },
         |_| {},
@@ -399,10 +403,10 @@ fn orphan() {
 
     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
         |obligation| match *obligation {
-            "A" => ProcessResult::Changed(vec!["D", "E"]),
+            "A" => ProcessResult::Changed(thin_vec!["D", "E"]),
             "B" => ProcessResult::Unchanged,
-            "C1" => ProcessResult::Changed(vec![]),
-            "C2" => ProcessResult::Changed(vec![]),
+            "C1" => ProcessResult::Changed(thin_vec![]),
+            "C2" => ProcessResult::Changed(thin_vec![]),
             "D" | "E" => ProcessResult::Unchanged,
             _ => unreachable!(),
         },
@@ -416,7 +420,7 @@ fn orphan() {
     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
         |obligation| match *obligation {
             "D" | "E" => ProcessResult::Unchanged,
-            "B" => ProcessResult::Changed(vec!["D"]),
+            "B" => ProcessResult::Changed(thin_vec!["D"]),
             _ => unreachable!(),
         },
         |_| {},
@@ -459,7 +463,7 @@ fn simultaneous_register_and_error() {
     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
         |obligation| match *obligation {
             "A" => ProcessResult::Error("An error"),
-            "B" => ProcessResult::Changed(vec!["A"]),
+            "B" => ProcessResult::Changed(thin_vec!["A"]),
             _ => unreachable!(),
         },
         |_| {},
@@ -474,7 +478,7 @@ fn simultaneous_register_and_error() {
     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
         |obligation| match *obligation {
             "A" => ProcessResult::Error("An error"),
-            "B" => ProcessResult::Changed(vec!["A"]),
+            "B" => ProcessResult::Changed(thin_vec!["A"]),
             _ => unreachable!(),
         },
         |_| {},
diff --git a/compiler/rustc_infer/Cargo.toml b/compiler/rustc_infer/Cargo.toml
index 1f616710200..ef5a1468c87 100644
--- a/compiler/rustc_infer/Cargo.toml
+++ b/compiler/rustc_infer/Cargo.toml
@@ -21,5 +21,6 @@ rustc_span = { path = "../rustc_span" }
 rustc_target = { path = "../rustc_target" }
 rustc_type_ir = { path = "../rustc_type_ir" }
 smallvec = { version = "1.8.1", features = ["union", "may_dangle"] }
+thin-vec = "0.2.12"
 tracing = "0.1"
 # tidy-alphabetical-end
diff --git a/compiler/rustc_infer/src/traits/mod.rs b/compiler/rustc_infer/src/traits/mod.rs
index 2d02391c57a..ac641ef5652 100644
--- a/compiler/rustc_infer/src/traits/mod.rs
+++ b/compiler/rustc_infer/src/traits/mod.rs
@@ -17,6 +17,7 @@ use rustc_middle::traits::solve::Certainty;
 pub use rustc_middle::traits::*;
 use rustc_middle::ty::{self, Ty, TyCtxt, Upcast};
 use rustc_span::Span;
+use thin_vec::ThinVec;
 
 pub use self::ImplSource::*;
 pub use self::SelectionError::*;
@@ -84,7 +85,7 @@ pub type PredicateObligation<'tcx> = Obligation<'tcx, ty::Predicate<'tcx>>;
 pub type TraitObligation<'tcx> = Obligation<'tcx, ty::TraitPredicate<'tcx>>;
 pub type PolyTraitObligation<'tcx> = Obligation<'tcx, ty::PolyTraitPredicate<'tcx>>;
 
-pub type PredicateObligations<'tcx> = Vec<PredicateObligation<'tcx>>;
+pub type PredicateObligations<'tcx> = ThinVec<PredicateObligation<'tcx>>;
 
 impl<'tcx> PredicateObligation<'tcx> {
     /// Flips the polarity of the inner predicate.
diff --git a/compiler/rustc_middle/src/traits/mod.rs b/compiler/rustc_middle/src/traits/mod.rs
index caa86da8a85..8ee8b4c4823 100644
--- a/compiler/rustc_middle/src/traits/mod.rs
+++ b/compiler/rustc_middle/src/traits/mod.rs
@@ -25,6 +25,7 @@ use rustc_span::{DUMMY_SP, Span};
 // FIXME: Remove this import and import via `solve::`
 pub use rustc_type_ir::solve::{BuiltinImplSource, Reveal};
 use smallvec::{SmallVec, smallvec};
+use thin_vec::ThinVec;
 
 pub use self::select::{EvaluationCache, EvaluationResult, OverflowError, SelectionCache};
 use crate::mir::ConstraintCategory;
@@ -625,14 +626,14 @@ pub enum ImplSource<'tcx, N> {
     /// for some type parameter. The `Vec<N>` represents the
     /// obligations incurred from normalizing the where-clause (if
     /// any).
-    Param(Vec<N>),
+    Param(ThinVec<N>),
 
     /// Successful resolution for a builtin impl.
-    Builtin(BuiltinImplSource, Vec<N>),
+    Builtin(BuiltinImplSource, ThinVec<N>),
 }
 
 impl<'tcx, N> ImplSource<'tcx, N> {
-    pub fn nested_obligations(self) -> Vec<N> {
+    pub fn nested_obligations(self) -> ThinVec<N> {
         match self {
             ImplSource::UserDefined(i) => i.nested,
             ImplSource::Param(n) | ImplSource::Builtin(_, n) => n,
@@ -686,7 +687,7 @@ impl<'tcx, N> ImplSource<'tcx, N> {
 pub struct ImplSourceUserDefinedData<'tcx, N> {
     pub impl_def_id: DefId,
     pub args: GenericArgsRef<'tcx>,
-    pub nested: Vec<N>,
+    pub nested: ThinVec<N>,
 }
 
 #[derive(Clone, Debug, PartialEq, Eq, Hash, HashStable, PartialOrd, Ord)]
diff --git a/compiler/rustc_trait_selection/Cargo.toml b/compiler/rustc_trait_selection/Cargo.toml
index f023a0eb53a..d4bb84838cc 100644
--- a/compiler/rustc_trait_selection/Cargo.toml
+++ b/compiler/rustc_trait_selection/Cargo.toml
@@ -26,5 +26,6 @@ rustc_target = { path = "../rustc_target" }
 rustc_transmute = { path = "../rustc_transmute", features = ["rustc"] }
 rustc_type_ir = { path = "../rustc_type_ir" }
 smallvec = { version = "1.8.1", features = ["union", "may_dangle"] }
+thin-vec = "0.2"
 tracing = "0.1"
 # tidy-alphabetical-end
diff --git a/compiler/rustc_trait_selection/src/solve/fulfill.rs b/compiler/rustc_trait_selection/src/solve/fulfill.rs
index 8ec4427091d..d9dc772eca9 100644
--- a/compiler/rustc_trait_selection/src/solve/fulfill.rs
+++ b/compiler/rustc_trait_selection/src/solve/fulfill.rs
@@ -2,6 +2,7 @@ use std::marker::PhantomData;
 use std::mem;
 use std::ops::ControlFlow;
 
+use rustc_data_structures::thinvec::ExtractIf;
 use rustc_infer::infer::InferCtxt;
 use rustc_infer::traits::query::NoSolution;
 use rustc_infer::traits::solve::{CandidateSource, GoalSource, MaybeCause};
@@ -81,7 +82,8 @@ impl<'tcx> ObligationStorage<'tcx> {
             // we get all obligations involved in the overflow. We pretty much check: if
             // we were to do another step of `select_where_possible`, which goals would
             // change.
-            self.overflowed.extend(self.pending.extract_if(|o| {
+            // FIXME: <https://github.com/Gankra/thin-vec/pull/66> is merged, this can be removed.
+            self.overflowed.extend(ExtractIf::new(&mut self.pending, |o| {
                 let goal = o.clone().into();
                 let result = <&SolverDelegate<'tcx>>::from(infcx)
                     .evaluate_root_goal(goal, GenerateProofTree::No)
diff --git a/compiler/rustc_trait_selection/src/traits/fulfill.rs b/compiler/rustc_trait_selection/src/traits/fulfill.rs
index 3e3834a11c6..e56f1866970 100644
--- a/compiler/rustc_trait_selection/src/traits/fulfill.rs
+++ b/compiler/rustc_trait_selection/src/traits/fulfill.rs
@@ -14,6 +14,7 @@ use rustc_middle::mir::interpret::ErrorHandled;
 use rustc_middle::ty::abstract_const::NotConstEvaluatable;
 use rustc_middle::ty::error::{ExpectedFound, TypeError};
 use rustc_middle::ty::{self, Binder, Const, GenericArgsRef, TypeVisitableExt};
+use thin_vec::ThinVec;
 use tracing::{debug, debug_span, instrument};
 
 use super::project::{self, ProjectAndUnifyResult};
@@ -28,7 +29,7 @@ use crate::traits::normalize::normalize_with_depth_to;
 use crate::traits::project::{PolyProjectionObligation, ProjectionCacheKeyExt as _};
 use crate::traits::query::evaluate_obligation::InferCtxtExt;
 
-pub(crate) type PendingPredicateObligations<'tcx> = Vec<PendingPredicateObligation<'tcx>>;
+pub(crate) type PendingPredicateObligations<'tcx> = ThinVec<PendingPredicateObligation<'tcx>>;
 
 impl<'tcx> ForestObligation for PendingPredicateObligation<'tcx> {
     /// Note that we include both the `ParamEnv` and the `Predicate`,
diff --git a/compiler/rustc_type_ir/Cargo.toml b/compiler/rustc_type_ir/Cargo.toml
index 98cc116bd00..8d97ec72830 100644
--- a/compiler/rustc_type_ir/Cargo.toml
+++ b/compiler/rustc_type_ir/Cargo.toml
@@ -17,6 +17,7 @@ rustc_serialize = { path = "../rustc_serialize", optional = true }
 rustc_span = { path = "../rustc_span", optional = true }
 rustc_type_ir_macros = { path = "../rustc_type_ir_macros" }
 smallvec = { version = "1.8.1", default-features = false }
+thin-vec = "0.2.12"
 tracing = "0.1"
 # tidy-alphabetical-end
 
@@ -30,7 +31,7 @@ nightly = [
     "smallvec/may_dangle",
     "smallvec/union",
     "rustc_index/nightly",
-    "rustc_ast_ir/nightly"
+    "rustc_ast_ir/nightly",
 ]
 
 [lints.rust]
diff --git a/compiler/rustc_type_ir/src/fold.rs b/compiler/rustc_type_ir/src/fold.rs
index 64ce6fd69e6..8209d6f5fe3 100644
--- a/compiler/rustc_type_ir/src/fold.rs
+++ b/compiler/rustc_type_ir/src/fold.rs
@@ -48,6 +48,7 @@
 use std::mem;
 
 use rustc_index::{Idx, IndexVec};
+use thin_vec::ThinVec;
 use tracing::instrument;
 
 use crate::data_structures::Lrc;
@@ -322,6 +323,12 @@ impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for Vec<T> {
     }
 }
 
+impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for ThinVec<T> {
+    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
+        self.into_iter().map(|t| t.try_fold_with(folder)).collect()
+    }
+}
+
 impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for Box<[T]> {
     fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
         Vec::from(self).try_fold_with(folder).map(Vec::into_boxed_slice)
diff --git a/compiler/rustc_type_ir/src/visit.rs b/compiler/rustc_type_ir/src/visit.rs
index 0ba7e2bd552..71c3646498b 100644
--- a/compiler/rustc_type_ir/src/visit.rs
+++ b/compiler/rustc_type_ir/src/visit.rs
@@ -47,6 +47,7 @@ use std::ops::ControlFlow;
 use rustc_ast_ir::visit::VisitorResult;
 use rustc_ast_ir::{try_visit, walk_visitable_list};
 use rustc_index::{Idx, IndexVec};
+use thin_vec::ThinVec;
 
 use crate::data_structures::Lrc;
 use crate::inherent::*;
@@ -184,6 +185,13 @@ impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for Vec<T> {
     }
 }
 
+impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for ThinVec<T> {
+    fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result {
+        walk_visitable_list!(visitor, self.iter());
+        V::Result::output()
+    }
+}
+
 // `TypeFoldable` isn't impl'd for `&[T]`. It doesn't make sense in the general
 // case, because we can't return a new slice. But note that there are a couple
 // of trivial impls of `TypeFoldable` for specific slice types elsewhere.