src/librustc_data_structures/obligation_forest/test.rs

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