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