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