diff options
Diffstat (limited to '')
-rw-r--r-- | compiler/rustc_data_structures/src/obligation_forest/tests.rs | 479 |
1 files changed, 479 insertions, 0 deletions
diff --git a/compiler/rustc_data_structures/src/obligation_forest/tests.rs b/compiler/rustc_data_structures/src/obligation_forest/tests.rs new file mode 100644 index 000000000..e2991aae1 --- /dev/null +++ b/compiler/rustc_data_structures/src/obligation_forest/tests.rs @@ -0,0 +1,479 @@ +use super::*; + +use std::fmt; +use std::marker::PhantomData; + +impl<'a> super::ForestObligation for &'a str { + type CacheKey = &'a str; + + fn as_cache_key(&self) -> Self::CacheKey { + self + } +} + +struct ClosureObligationProcessor<OF, BF, O, E> { + process_obligation: OF, + _process_backedge: BF, + marker: PhantomData<(O, E)>, +} + +struct TestOutcome<O, E> { + pub completed: Vec<O>, + pub errors: Vec<Error<O, E>>, +} + +impl<O, E> OutcomeTrait for TestOutcome<O, E> +where + O: Clone, +{ + type Error = Error<O, E>; + type Obligation = O; + + fn new() -> Self { + Self { errors: vec![], completed: vec![] } + } + + fn record_completed(&mut self, outcome: &Self::Obligation) { + self.completed.push(outcome.clone()) + } + + fn record_error(&mut self, error: Self::Error) { + self.errors.push(error) + } +} + +#[allow(non_snake_case)] +fn C<OF, BF, O>(of: OF, bf: BF) -> ClosureObligationProcessor<OF, BF, O, &'static str> +where + OF: FnMut(&mut O) -> ProcessResult<O, &'static str>, + BF: FnMut(&[O]), +{ + ClosureObligationProcessor { + process_obligation: of, + _process_backedge: bf, + marker: PhantomData, + } +} + +impl<OF, BF, O, E> ObligationProcessor for ClosureObligationProcessor<OF, BF, O, E> +where + O: super::ForestObligation + fmt::Debug, + E: fmt::Debug, + OF: FnMut(&mut O) -> ProcessResult<O, E>, + BF: FnMut(&[O]), +{ + type Obligation = O; + type Error = E; + + fn needs_process_obligation(&self, _obligation: &Self::Obligation) -> bool { + true + } + + fn process_obligation( + &mut self, + obligation: &mut Self::Obligation, + ) -> ProcessResult<Self::Obligation, Self::Error> { + (self.process_obligation)(obligation) + } + + fn process_backedge<'c, I>(&mut self, _cycle: I, _marker: PhantomData<&'c Self::Obligation>) + where + I: Clone + Iterator<Item = &'c Self::Obligation>, + { + } +} + +#[test] +fn push_pop() { + let mut forest = ObligationForest::new(); + forest.register_obligation("A"); + forest.register_obligation("B"); + forest.register_obligation("C"); + + // first round, B errors out, A has subtasks, and C completes, creating this: + // A |-> A.1 + // |-> A.2 + // |-> 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"]), + "B" => ProcessResult::Error("B is for broken"), + "C" => ProcessResult::Changed(vec![]), + "A.1" | "A.2" | "A.3" => ProcessResult::Unchanged, + _ => unreachable!(), + }, + |_| {}, + )); + assert_eq!(ok, vec!["C"]); + assert_eq!(err, vec![Error { error: "B is for broken", backtrace: vec!["B"] }]); + + // second round: two delays, one success, creating an uneven set of subtasks: + // A |-> A.1 + // |-> A.2 + // |-> A.3 |-> A.3.i + // D |-> D.1 + // |-> D.2 + forest.register_obligation("D"); + let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C( + |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.i" | "D.1" | "D.2" => ProcessResult::Unchanged, + _ => unreachable!(), + }, + |_| {}, + )); + assert_eq!(ok, Vec::<&'static str>::new()); + assert_eq!(err, Vec::new()); + + // third round: ok in A.1 but trigger an error in A.2. Check that it + // propagates to A, but not D.1 or D.2. + // D |-> D.1 |-> D.1.i + // |-> 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.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"]), + "D.1.i" | "D.2.i" => ProcessResult::Unchanged, + _ => unreachable!(), + }, + |_| {}, + )); + let mut ok = ok; + ok.sort(); + assert_eq!(ok, vec!["A.1", "A.3", "A.3.i"]); + assert_eq!(err, vec![Error { error: "A is for apple", backtrace: vec!["A.2", "A"] }]); + + // fourth round: error in D.1.i + 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![]), + _ => panic!("unexpected obligation {:?}", obligation), + }, + |_| {}, + )); + let mut ok = ok; + ok.sort(); + assert_eq!(ok, vec!["D.2", "D.2.i"]); + assert_eq!(err, vec![Error { error: "D is for dumb", backtrace: vec!["D.1.i", "D.1", "D"] }]); +} + +// Test that if a tree with grandchildren succeeds, everything is +// reported as expected: +// A +// A.1 +// A.2 +// A.2.i +// A.2.ii +// A.3 +#[test] +fn success_in_grandchildren() { + let mut forest = ObligationForest::new(); + 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.1" => ProcessResult::Changed(vec![]), + "A.2" => ProcessResult::Changed(vec!["A.2.i", "A.2.ii"]), + "A.3" => ProcessResult::Changed(vec![]), + "A.2.i" | "A.2.ii" => ProcessResult::Unchanged, + _ => unreachable!(), + }, + |_| {}, + )); + let mut ok = ok; + ok.sort(); + assert_eq!(ok, vec!["A.1", "A.3"]); + assert!(err.is_empty()); + + 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![]), + _ => unreachable!(), + }, + |_| {}, + )); + assert_eq!(ok, vec!["A.2.ii"]); + assert!(err.is_empty()); + + 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.a" => ProcessResult::Unchanged, + _ => unreachable!(), + }, + |_| {}, + )); + assert!(ok.is_empty()); + assert!(err.is_empty()); + + let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C( + |obligation| match *obligation { + "A.2.i.a" => ProcessResult::Changed(vec![]), + _ => unreachable!(), + }, + |_| {}, + )); + let mut ok = ok; + ok.sort(); + assert_eq!(ok, vec!["A", "A.2", "A.2.i", "A.2.i.a"]); + assert!(err.is_empty()); + + let TestOutcome { completed: ok, errors: err, .. } = + forest.process_obligations(&mut C(|_| unreachable!(), |_| {})); + + assert!(ok.is_empty()); + assert!(err.is_empty()); +} + +#[test] +fn to_errors_no_throw() { + // check that converting multiple children with common parent (A) + // yields to correct errors (and does not panic, in particular). + let mut forest = ObligationForest::new(); + 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.1" | "A.2" | "A.3" => ProcessResult::Unchanged, + _ => unreachable!(), + }, + |_| {}, + )); + assert_eq!(ok.len(), 0); + assert_eq!(err.len(), 0); + let errors = forest.to_errors(()); + assert_eq!(errors[0].backtrace, vec!["A.1", "A"]); + assert_eq!(errors[1].backtrace, vec!["A.2", "A"]); + assert_eq!(errors[2].backtrace, vec!["A.3", "A"]); + assert_eq!(errors.len(), 3); +} + +#[test] +fn diamond() { + // check that diamond dependencies are handled correctly + let mut forest = ObligationForest::new(); + 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.1" | "A.2" => ProcessResult::Unchanged, + _ => unreachable!(), + }, + |_| {}, + )); + assert_eq!(ok.len(), 0); + assert_eq!(err.len(), 0); + + 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"]), + "D" => ProcessResult::Unchanged, + _ => unreachable!(), + }, + |_| {}, + )); + assert_eq!(ok.len(), 0); + assert_eq!(err.len(), 0); + + let mut d_count = 0; + let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C( + |obligation| match *obligation { + "D" => { + d_count += 1; + ProcessResult::Changed(vec![]) + } + _ => unreachable!(), + }, + |_| {}, + )); + assert_eq!(d_count, 1); + let mut ok = ok; + ok.sort(); + assert_eq!(ok, vec!["A", "A.1", "A.2", "D"]); + assert_eq!(err.len(), 0); + + let errors = forest.to_errors(()); + assert_eq!(errors.len(), 0); + + 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'.1" | "A'.2" => ProcessResult::Unchanged, + _ => unreachable!(), + }, + |_| {}, + )); + assert_eq!(ok.len(), 0); + assert_eq!(err.len(), 0); + + 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'"]), + "D'" | "A'" => ProcessResult::Unchanged, + _ => unreachable!(), + }, + |_| {}, + )); + assert_eq!(ok.len(), 0); + assert_eq!(err.len(), 0); + + let mut d_count = 0; + let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C( + |obligation| match *obligation { + "D'" => { + d_count += 1; + ProcessResult::Error("operation failed") + } + _ => unreachable!(), + }, + |_| {}, + )); + assert_eq!(d_count, 1); + assert_eq!(ok.len(), 0); + assert_eq!( + err, + vec![super::Error { error: "operation failed", backtrace: vec!["D'", "A'.1", "A'"] }] + ); + + let errors = forest.to_errors(()); + assert_eq!(errors.len(), 0); +} + +#[test] +fn done_dependency() { + // check that the local cache works + let mut forest = ObligationForest::new(); + forest.register_obligation("A: Sized"); + forest.register_obligation("B: Sized"); + forest.register_obligation("C: Sized"); + + let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C( + |obligation| match *obligation { + "A: Sized" | "B: Sized" | "C: Sized" => ProcessResult::Changed(vec![]), + _ => unreachable!(), + }, + |_| {}, + )); + let mut ok = ok; + ok.sort(); + assert_eq!(ok, vec!["A: Sized", "B: Sized", "C: Sized"]); + assert_eq!(err.len(), 0); + + 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"]), + _ => unreachable!(), + }, + |_| {}, + )); + assert_eq!(ok, vec!["(A,B,C): Sized"]); + assert_eq!(err.len(), 0); +} + +#[test] +fn orphan() { + // check that orphaned nodes are handled correctly + let mut forest = ObligationForest::new(); + forest.register_obligation("A"); + forest.register_obligation("B"); + forest.register_obligation("C1"); + forest.register_obligation("C2"); + + let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C( + |obligation| match *obligation { + "A" => ProcessResult::Changed(vec!["D", "E"]), + "B" => ProcessResult::Unchanged, + "C1" => ProcessResult::Changed(vec![]), + "C2" => ProcessResult::Changed(vec![]), + "D" | "E" => ProcessResult::Unchanged, + _ => unreachable!(), + }, + |_| {}, + )); + let mut ok = ok; + ok.sort(); + assert_eq!(ok, vec!["C1", "C2"]); + assert_eq!(err.len(), 0); + + let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C( + |obligation| match *obligation { + "D" | "E" => ProcessResult::Unchanged, + "B" => ProcessResult::Changed(vec!["D"]), + _ => unreachable!(), + }, + |_| {}, + )); + assert_eq!(ok.len(), 0); + assert_eq!(err.len(), 0); + + let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C( + |obligation| match *obligation { + "D" => ProcessResult::Unchanged, + "E" => ProcessResult::Error("E is for error"), + _ => unreachable!(), + }, + |_| {}, + )); + assert_eq!(ok.len(), 0); + assert_eq!(err, vec![super::Error { error: "E is for error", backtrace: vec!["E", "A"] }]); + + let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C( + |obligation| match *obligation { + "D" => ProcessResult::Error("D is dead"), + _ => unreachable!(), + }, + |_| {}, + )); + assert_eq!(ok.len(), 0); + assert_eq!(err, vec![super::Error { error: "D is dead", backtrace: vec!["D"] }]); + + let errors = forest.to_errors(()); + assert_eq!(errors.len(), 0); +} + +#[test] +fn simultaneous_register_and_error() { + // check that registering a failed obligation works correctly + let mut forest = ObligationForest::new(); + forest.register_obligation("A"); + forest.register_obligation("B"); + + let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C( + |obligation| match *obligation { + "A" => ProcessResult::Error("An error"), + "B" => ProcessResult::Changed(vec!["A"]), + _ => unreachable!(), + }, + |_| {}, + )); + assert_eq!(ok.len(), 0); + assert_eq!(err, vec![super::Error { error: "An error", backtrace: vec!["A"] }]); + + let mut forest = ObligationForest::new(); + forest.register_obligation("B"); + forest.register_obligation("A"); + + let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C( + |obligation| match *obligation { + "A" => ProcessResult::Error("An error"), + "B" => ProcessResult::Changed(vec!["A"]), + _ => unreachable!(), + }, + |_| {}, + )); + assert_eq!(ok.len(), 0); + assert_eq!(err, vec![super::Error { error: "An error", backtrace: vec!["A"] }]); +} |