compiler/rustc_data_structures/src/obligation_forest/tests.rs

   1 use super::*;
   2
   3 use std::fmt;
   4 use std::marker::PhantomData;
   5
   6 impl<'a> super::ForestObligation for &'a str {
   7     type CacheKey = &'a str;
   8
   9     fn as_cache_key(&self) -> Self::CacheKey {
  10         self
  11     }
  12 }
  13
  14 struct ClosureObligationProcessor<OF, BF, O, E> {
  15     process_obligation: OF,
  16     _process_backedge: BF,
  17     marker: PhantomData<(O, E)>,
  18 }
  19
  20 struct TestOutcome<O, E> {
  21     pub completed: Vec<O>,
  22     pub errors: Vec<Error<O, E>>,
  23 }
  24
  25 impl<O, E> OutcomeTrait for TestOutcome<O, E>
  26 where
  27     O: Clone,
  28 {
  29     type Error = Error<O, E>;
  30     type Obligation = O;
  31
  32     fn new() -> Self {
  33         Self { errors: vec![], completed: vec![] }
  34     }
  35
  36     fn record_completed(&mut self, outcome: &Self::Obligation) {
  37         self.completed.push(outcome.clone())
  38     }
  39
  40     fn record_error(&mut self, error: Self::Error) {
  41         self.errors.push(error)
  42     }
  43 }
  44
  45 #[allow(non_snake_case)]
  46 fn C<OF, BF, O>(of: OF, bf: BF) -> ClosureObligationProcessor<OF, BF, O, &'static str>
  47 where
  48     OF: FnMut(&mut O) -> ProcessResult<O, &'static str>,
  49     BF: FnMut(&[O]),
  50 {
  51     ClosureObligationProcessor {
  52         process_obligation: of,
  53         _process_backedge: bf,
  54         marker: PhantomData,
  55     }
  56 }
  57
  58 impl<OF, BF, O, E> ObligationProcessor for ClosureObligationProcessor<OF, BF, O, E>
  59 where
  60     O: super::ForestObligation + fmt::Debug,
  61     E: fmt::Debug,
  62     OF: FnMut(&mut O) -> ProcessResult<O, E>,
  63     BF: FnMut(&[O]),
  64 {
  65     type Obligation = O;
  66     type Error = E;
  67
  68     fn needs_process_obligation(&self, _obligation: &Self::Obligation) -> bool {
  69         true
  70     }
  71
  72     fn process_obligation(
  73         &mut self,
  74         obligation: &mut Self::Obligation,
  75     ) -> ProcessResult<Self::Obligation, Self::Error> {
  76         (self.process_obligation)(obligation)
  77     }
  78
  79     fn process_backedge<'c, I>(&mut self, _cycle: I, _marker: PhantomData<&'c Self::Obligation>)
  80     where
  81         I: Clone + Iterator<Item = &'c Self::Obligation>,
  82     {
  83     }
  84 }
  85
  86 #[test]
  87 fn push_pop() {
  88     let mut forest = ObligationForest::new();
  89     forest.register_obligation("A");
  90     forest.register_obligation("B");
  91     forest.register_obligation("C");
  92
  93     // first round, B errors out, A has subtasks, and C completes, creating this:
  94     //      A |-> A.1
  95     //        |-> A.2
  96     //        |-> A.3
  97     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
  98         |obligation| match *obligation {
  99             "A" => ProcessResult::Changed(vec!["A.1", "A.2", "A.3"]),
 100             "B" => ProcessResult::Error("B is for broken"),
 101             "C" => ProcessResult::Changed(vec![]),
 102             "A.1" | "A.2" | "A.3" => ProcessResult::Unchanged,
 103             _ => unreachable!(),
 104         },
 105         |_| {},
 106     ));
 107     assert_eq!(ok, vec!["C"]);
 108     assert_eq!(err, vec![Error { error: "B is for broken", backtrace: vec!["B"] }]);
 109
 110     // second round: two delays, one success, creating an uneven set of subtasks:
 111     //      A |-> A.1
 112     //        |-> A.2
 113     //        |-> A.3 |-> A.3.i
 114     //      D |-> D.1
 115     //        |-> D.2
 116     forest.register_obligation("D");
 117     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 118         |obligation| match *obligation {
 119             "A.1" => ProcessResult::Unchanged,
 120             "A.2" => ProcessResult::Unchanged,
 121             "A.3" => ProcessResult::Changed(vec!["A.3.i"]),
 122             "D" => ProcessResult::Changed(vec!["D.1", "D.2"]),
 123             "A.3.i" | "D.1" | "D.2" => ProcessResult::Unchanged,
 124             _ => unreachable!(),
 125         },
 126         |_| {},
 127     ));
 128     assert_eq!(ok, Vec::<&'static str>::new());
 129     assert_eq!(err, Vec::new());
 130
 131     // third round: ok in A.1 but trigger an error in A.2. Check that it
 132     // propagates to A, but not D.1 or D.2.
 133     //      D |-> D.1 |-> D.1.i
 134     //        |-> D.2 |-> D.2.i
 135     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 136         |obligation| match *obligation {
 137             "A.1" => ProcessResult::Changed(vec![]),
 138             "A.2" => ProcessResult::Error("A is for apple"),
 139             "A.3.i" => ProcessResult::Changed(vec![]),
 140             "D.1" => ProcessResult::Changed(vec!["D.1.i"]),
 141             "D.2" => ProcessResult::Changed(vec!["D.2.i"]),
 142             "D.1.i" | "D.2.i" => ProcessResult::Unchanged,
 143             _ => unreachable!(),
 144         },
 145         |_| {},
 146     ));
 147     let mut ok = ok;
 148     ok.sort();
 149     assert_eq!(ok, vec!["A.1", "A.3", "A.3.i"]);
 150     assert_eq!(err, vec![Error { error: "A is for apple", backtrace: vec!["A.2", "A"] }]);
 151
 152     // fourth round: error in D.1.i
 153     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 154         |obligation| match *obligation {
 155             "D.1.i" => ProcessResult::Error("D is for dumb"),
 156             "D.2.i" => ProcessResult::Changed(vec![]),
 157             _ => panic!("unexpected obligation {:?}", obligation),
 158         },
 159         |_| {},
 160     ));
 161     let mut ok = ok;
 162     ok.sort();
 163     assert_eq!(ok, vec!["D.2", "D.2.i"]);
 164     assert_eq!(err, vec![Error { error: "D is for dumb", backtrace: vec!["D.1.i", "D.1", "D"] }]);
 165 }
 166
 167 // Test that if a tree with grandchildren succeeds, everything is
 168 // reported as expected:
 169 // A
 170 //   A.1
 171 //   A.2
 172 //      A.2.i
 173 //      A.2.ii
 174 //   A.3
 175 #[test]
 176 fn success_in_grandchildren() {
 177     let mut forest = ObligationForest::new();
 178     forest.register_obligation("A");
 179
 180     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 181         |obligation| match *obligation {
 182             "A" => ProcessResult::Changed(vec!["A.1", "A.2", "A.3"]),
 183             "A.1" => ProcessResult::Changed(vec![]),
 184             "A.2" => ProcessResult::Changed(vec!["A.2.i", "A.2.ii"]),
 185             "A.3" => ProcessResult::Changed(vec![]),
 186             "A.2.i" | "A.2.ii" => ProcessResult::Unchanged,
 187             _ => unreachable!(),
 188         },
 189         |_| {},
 190     ));
 191     let mut ok = ok;
 192     ok.sort();
 193     assert_eq!(ok, vec!["A.1", "A.3"]);
 194     assert!(err.is_empty());
 195
 196     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 197         |obligation| match *obligation {
 198             "A.2.i" => ProcessResult::Unchanged,
 199             "A.2.ii" => ProcessResult::Changed(vec![]),
 200             _ => unreachable!(),
 201         },
 202         |_| {},
 203     ));
 204     assert_eq!(ok, vec!["A.2.ii"]);
 205     assert!(err.is_empty());
 206
 207     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 208         |obligation| match *obligation {
 209             "A.2.i" => ProcessResult::Changed(vec!["A.2.i.a"]),
 210             "A.2.i.a" => ProcessResult::Unchanged,
 211             _ => unreachable!(),
 212         },
 213         |_| {},
 214     ));
 215     assert!(ok.is_empty());
 216     assert!(err.is_empty());
 217
 218     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 219         |obligation| match *obligation {
 220             "A.2.i.a" => ProcessResult::Changed(vec![]),
 221             _ => unreachable!(),
 222         },
 223         |_| {},
 224     ));
 225     let mut ok = ok;
 226     ok.sort();
 227     assert_eq!(ok, vec!["A", "A.2", "A.2.i", "A.2.i.a"]);
 228     assert!(err.is_empty());
 229
 230     let TestOutcome { completed: ok, errors: err, .. } =
 231         forest.process_obligations(&mut C(|_| unreachable!(), |_| {}));
 232
 233     assert!(ok.is_empty());
 234     assert!(err.is_empty());
 235 }
 236
 237 #[test]
 238 fn to_errors_no_throw() {
 239     // check that converting multiple children with common parent (A)
 240     // yields to correct errors (and does not panic, in particular).
 241     let mut forest = ObligationForest::new();
 242     forest.register_obligation("A");
 243     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 244         |obligation| match *obligation {
 245             "A" => ProcessResult::Changed(vec!["A.1", "A.2", "A.3"]),
 246             "A.1" | "A.2" | "A.3" => ProcessResult::Unchanged,
 247             _ => unreachable!(),
 248         },
 249         |_| {},
 250     ));
 251     assert_eq!(ok.len(), 0);
 252     assert_eq!(err.len(), 0);
 253     let errors = forest.to_errors(());
 254     assert_eq!(errors[0].backtrace, vec!["A.1", "A"]);
 255     assert_eq!(errors[1].backtrace, vec!["A.2", "A"]);
 256     assert_eq!(errors[2].backtrace, vec!["A.3", "A"]);
 257     assert_eq!(errors.len(), 3);
 258 }
 259
 260 #[test]
 261 fn diamond() {
 262     // check that diamond dependencies are handled correctly
 263     let mut forest = ObligationForest::new();
 264     forest.register_obligation("A");
 265     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 266         |obligation| match *obligation {
 267             "A" => ProcessResult::Changed(vec!["A.1", "A.2"]),
 268             "A.1" | "A.2" => ProcessResult::Unchanged,
 269             _ => unreachable!(),
 270         },
 271         |_| {},
 272     ));
 273     assert_eq!(ok.len(), 0);
 274     assert_eq!(err.len(), 0);
 275
 276     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 277         |obligation| match *obligation {
 278             "A.1" => ProcessResult::Changed(vec!["D"]),
 279             "A.2" => ProcessResult::Changed(vec!["D"]),
 280             "D" => ProcessResult::Unchanged,
 281             _ => unreachable!(),
 282         },
 283         |_| {},
 284     ));
 285     assert_eq!(ok.len(), 0);
 286     assert_eq!(err.len(), 0);
 287
 288     let mut d_count = 0;
 289     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 290         |obligation| match *obligation {
 291             "D" => {
 292                 d_count += 1;
 293                 ProcessResult::Changed(vec![])
 294             }
 295             _ => unreachable!(),
 296         },
 297         |_| {},
 298     ));
 299     assert_eq!(d_count, 1);
 300     let mut ok = ok;
 301     ok.sort();
 302     assert_eq!(ok, vec!["A", "A.1", "A.2", "D"]);
 303     assert_eq!(err.len(), 0);
 304
 305     let errors = forest.to_errors(());
 306     assert_eq!(errors.len(), 0);
 307
 308     forest.register_obligation("A'");
 309     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 310         |obligation| match *obligation {
 311             "A'" => ProcessResult::Changed(vec!["A'.1", "A'.2"]),
 312             "A'.1" | "A'.2" => ProcessResult::Unchanged,
 313             _ => unreachable!(),
 314         },
 315         |_| {},
 316     ));
 317     assert_eq!(ok.len(), 0);
 318     assert_eq!(err.len(), 0);
 319
 320     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 321         |obligation| match *obligation {
 322             "A'.1" => ProcessResult::Changed(vec!["D'", "A'"]),
 323             "A'.2" => ProcessResult::Changed(vec!["D'"]),
 324             "D'" | "A'" => ProcessResult::Unchanged,
 325             _ => unreachable!(),
 326         },
 327         |_| {},
 328     ));
 329     assert_eq!(ok.len(), 0);
 330     assert_eq!(err.len(), 0);
 331
 332     let mut d_count = 0;
 333     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 334         |obligation| match *obligation {
 335             "D'" => {
 336                 d_count += 1;
 337                 ProcessResult::Error("operation failed")
 338             }
 339             _ => unreachable!(),
 340         },
 341         |_| {},
 342     ));
 343     assert_eq!(d_count, 1);
 344     assert_eq!(ok.len(), 0);
 345     assert_eq!(
 346         err,
 347         vec![super::Error { error: "operation failed", backtrace: vec!["D'", "A'.1", "A'"] }]
 348     );
 349
 350     let errors = forest.to_errors(());
 351     assert_eq!(errors.len(), 0);
 352 }
 353
 354 #[test]
 355 fn done_dependency() {
 356     // check that the local cache works
 357     let mut forest = ObligationForest::new();
 358     forest.register_obligation("A: Sized");
 359     forest.register_obligation("B: Sized");
 360     forest.register_obligation("C: Sized");
 361
 362     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 363         |obligation| match *obligation {
 364             "A: Sized" | "B: Sized" | "C: Sized" => ProcessResult::Changed(vec![]),
 365             _ => unreachable!(),
 366         },
 367         |_| {},
 368     ));
 369     let mut ok = ok;
 370     ok.sort();
 371     assert_eq!(ok, vec!["A: Sized", "B: Sized", "C: Sized"]);
 372     assert_eq!(err.len(), 0);
 373
 374     forest.register_obligation("(A,B,C): Sized");
 375     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 376         |obligation| match *obligation {
 377             "(A,B,C): Sized" => ProcessResult::Changed(vec!["A: Sized", "B: Sized", "C: Sized"]),
 378             _ => unreachable!(),
 379         },
 380         |_| {},
 381     ));
 382     assert_eq!(ok, vec!["(A,B,C): Sized"]);
 383     assert_eq!(err.len(), 0);
 384 }
 385
 386 #[test]
 387 fn orphan() {
 388     // check that orphaned nodes are handled correctly
 389     let mut forest = ObligationForest::new();
 390     forest.register_obligation("A");
 391     forest.register_obligation("B");
 392     forest.register_obligation("C1");
 393     forest.register_obligation("C2");
 394
 395     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 396         |obligation| match *obligation {
 397             "A" => ProcessResult::Changed(vec!["D", "E"]),
 398             "B" => ProcessResult::Unchanged,
 399             "C1" => ProcessResult::Changed(vec![]),
 400             "C2" => ProcessResult::Changed(vec![]),
 401             "D" | "E" => ProcessResult::Unchanged,
 402             _ => unreachable!(),
 403         },
 404         |_| {},
 405     ));
 406     let mut ok = ok;
 407     ok.sort();
 408     assert_eq!(ok, vec!["C1", "C2"]);
 409     assert_eq!(err.len(), 0);
 410
 411     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 412         |obligation| match *obligation {
 413             "D" | "E" => ProcessResult::Unchanged,
 414             "B" => ProcessResult::Changed(vec!["D"]),
 415             _ => unreachable!(),
 416         },
 417         |_| {},
 418     ));
 419     assert_eq!(ok.len(), 0);
 420     assert_eq!(err.len(), 0);
 421
 422     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 423         |obligation| match *obligation {
 424             "D" => ProcessResult::Unchanged,
 425             "E" => ProcessResult::Error("E is for error"),
 426             _ => unreachable!(),
 427         },
 428         |_| {},
 429     ));
 430     assert_eq!(ok.len(), 0);
 431     assert_eq!(err, vec![super::Error { error: "E is for error", backtrace: vec!["E", "A"] }]);
 432
 433     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 434         |obligation| match *obligation {
 435             "D" => ProcessResult::Error("D is dead"),
 436             _ => unreachable!(),
 437         },
 438         |_| {},
 439     ));
 440     assert_eq!(ok.len(), 0);
 441     assert_eq!(err, vec![super::Error { error: "D is dead", backtrace: vec!["D"] }]);
 442
 443     let errors = forest.to_errors(());
 444     assert_eq!(errors.len(), 0);
 445 }
 446
 447 #[test]
 448 fn simultaneous_register_and_error() {
 449     // check that registering a failed obligation works correctly
 450     let mut forest = ObligationForest::new();
 451     forest.register_obligation("A");
 452     forest.register_obligation("B");
 453
 454     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 455         |obligation| match *obligation {
 456             "A" => ProcessResult::Error("An error"),
 457             "B" => ProcessResult::Changed(vec!["A"]),
 458             _ => unreachable!(),
 459         },
 460         |_| {},
 461     ));
 462     assert_eq!(ok.len(), 0);
 463     assert_eq!(err, vec![super::Error { error: "An error", backtrace: vec!["A"] }]);
 464
 465     let mut forest = ObligationForest::new();
 466     forest.register_obligation("B");
 467     forest.register_obligation("A");
 468
 469     let TestOutcome { completed: ok, errors: err, .. } = forest.process_obligations(&mut C(
 470         |obligation| match *obligation {
 471             "A" => ProcessResult::Error("An error"),
 472             "B" => ProcessResult::Changed(vec!["A"]),
 473             _ => unreachable!(),
 474         },
 475         |_| {},
 476     ));
 477     assert_eq!(ok.len(), 0);
 478     assert_eq!(err, vec![super::Error { error: "An error", backtrace: vec!["A"] }]);
 479 }