src/test/run-pass/dropck_legal_cycles.rs

   1 // Copyright 2015 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 // This test exercises cases where cyclic structure is legal,
  12 // including when the cycles go through data-structures such
  13 // as `Vec` or `TypedArena`.
  14 //
  15 // The intent is to cover as many such cases as possible, ensuring
  16 // that if the compiler did not complain circa Rust 1.x (1.2 as of
  17 // this writing), then it will continue to not complain in the future.
  18 //
  19 // Note that while some of the tests are only exercising using the
  20 // given collection as a "backing store" for a set of nodes that hold
  21 // the actual cycle (and thus the cycle does not go through the
  22 // collection itself in such cases), in general we *do* want to make
  23 // sure to have at least one example exercising a cycle that goes
  24 // through the collection, for every collection type that supports
  25 // this.
  26
  27 #![feature(vecmap)]
  28
  29 use std::cell::Cell;
  30 use std::cmp::Ordering;
  31 use std::collections::BinaryHeap;
  32 use std::collections::HashMap;
  33 use std::collections::LinkedList;
  34 use std::collections::VecDeque;
  35 use std::collections::VecMap;
  36 use std::collections::btree_map::BTreeMap;
  37 use std::collections::btree_set::BTreeSet;
  38 use std::hash::{Hash, Hasher};
  39
  40 const PRINT: bool = false;
  41
  42 pub fn main() {
  43     let c_orig = ContextData {
  44         curr_depth: 0,
  45         max_depth: 3,
  46         visited: 0,
  47         max_visits: 1000,
  48         skipped: 0,
  49         curr_mark: 0,
  50         saw_prev_marked: false,
  51     };
  52
  53     // Cycle 1: { v[0] -> v[1], v[1] -> v[0] };
  54     // does not exercise `v` itself
  55     let v: Vec<S> = vec![Named::new("s0"),
  56                          Named::new("s1")];
  57     v[0].next.set(Some(&v[1]));
  58     v[1].next.set(Some(&v[0]));
  59
  60     let mut c = c_orig.clone();
  61     c.curr_mark = 10;
  62     assert!(!c.saw_prev_marked);
  63     v[0].for_each_child(&mut c);
  64     assert!(c.saw_prev_marked);
  65
  66     if PRINT { println!(""); }
  67
  68     // Cycle 2: { v[0] -> v, v[1] -> v }
  69     let v: V = Named::new("v");
  70     v.contents[0].set(Some(&v));
  71     v.contents[1].set(Some(&v));
  72
  73     let mut c = c_orig.clone();
  74     c.curr_mark = 20;
  75     assert!(!c.saw_prev_marked);
  76     v.for_each_child(&mut c);
  77     assert!(c.saw_prev_marked);
  78
  79     if PRINT { println!(""); }
  80
  81     // Cycle 3: { hk0 -> hv0, hv0 -> hk0, hk1 -> hv1, hv1 -> hk1 };
  82     // does not exercise `h` itself
  83
  84     let mut h: HashMap<H,H> = HashMap::new();
  85     h.insert(Named::new("hk0"), Named::new("hv0"));
  86     h.insert(Named::new("hk1"), Named::new("hv1"));
  87     for (key, val) in h.iter() {
  88         val.next.set(Some(key));
  89         key.next.set(Some(val));
  90     }
  91
  92     let mut c = c_orig.clone();
  93     c.curr_mark = 30;
  94     for (key, _) in h.iter() {
  95         c.curr_mark += 1;
  96         c.saw_prev_marked = false;
  97         key.for_each_child(&mut c);
  98         assert!(c.saw_prev_marked);
  99     }
 100
 101     if PRINT { println!(""); }
 102
 103     // Cycle 4: { h -> (hmk0,hmv0,hmk1,hmv1), {hmk0,hmv0,hmk1,hmv1} -> h }
 104
 105     let mut h: HashMap<HM,HM> = HashMap::new();
 106     h.insert(Named::new("hmk0"), Named::new("hmv0"));
 107     h.insert(Named::new("hmk0"), Named::new("hmv0"));
 108     for (key, val) in h.iter() {
 109         val.contents.set(Some(&h));
 110         key.contents.set(Some(&h));
 111     }
 112
 113     let mut c = c_orig.clone();
 114     c.max_depth = 2;
 115     c.curr_mark = 40;
 116     for (key, _) in h.iter() {
 117         c.curr_mark += 1;
 118         c.saw_prev_marked = false;
 119         key.for_each_child(&mut c);
 120         assert!(c.saw_prev_marked);
 121         // break;
 122     }
 123
 124     if PRINT { println!(""); }
 125
 126     // Cycle 5: { vd[0] -> vd[1], vd[1] -> vd[0] };
 127     // does not exercise vd itself
 128     let mut vd: VecDeque<S> = VecDeque::new();
 129     vd.push_back(Named::new("d0"));
 130     vd.push_back(Named::new("d1"));
 131     vd[0].next.set(Some(&vd[1]));
 132     vd[1].next.set(Some(&vd[0]));
 133
 134     let mut c = c_orig.clone();
 135     c.curr_mark = 50;
 136     assert!(!c.saw_prev_marked);
 137     vd[0].for_each_child(&mut c);
 138     assert!(c.saw_prev_marked);
 139
 140     if PRINT { println!(""); }
 141
 142     // Cycle 6: { vd -> (vd0, vd1), {vd0, vd1} -> vd }
 143     let mut vd: VecDeque<VD> = VecDeque::new();
 144     vd.push_back(Named::new("vd0"));
 145     vd.push_back(Named::new("vd1"));
 146     vd[0].contents.set(Some(&vd));
 147     vd[1].contents.set(Some(&vd));
 148
 149     let mut c = c_orig.clone();
 150     c.curr_mark = 60;
 151     assert!(!c.saw_prev_marked);
 152     vd[0].for_each_child(&mut c);
 153     assert!(c.saw_prev_marked);
 154
 155     if PRINT { println!(""); }
 156
 157     // Cycle 7: { vm -> (vm0, vm1), {vm0, vm1} -> vm }
 158     let mut vm: VecMap<VM> = VecMap::new();
 159     vm.insert(0, Named::new("vm0"));
 160     vm.insert(1, Named::new("vm1"));
 161     vm[0].contents.set(Some(&vm));
 162     vm[1].contents.set(Some(&vm));
 163
 164     let mut c = c_orig.clone();
 165     c.curr_mark = 70;
 166     assert!(!c.saw_prev_marked);
 167     vm[0].for_each_child(&mut c);
 168     assert!(c.saw_prev_marked);
 169
 170     if PRINT { println!(""); }
 171
 172     // Cycle 8: { ll -> (ll0, ll1), {ll0, ll1} -> ll }
 173     let mut ll: LinkedList<LL> = LinkedList::new();
 174     ll.push_back(Named::new("ll0"));
 175     ll.push_back(Named::new("ll1"));
 176     for e in &ll {
 177         e.contents.set(Some(&ll));
 178     }
 179
 180     let mut c = c_orig.clone();
 181     c.curr_mark = 80;
 182     for e in &ll {
 183         c.curr_mark += 1;
 184         c.saw_prev_marked = false;
 185         e.for_each_child(&mut c);
 186         assert!(c.saw_prev_marked);
 187         // break;
 188     }
 189
 190     if PRINT { println!(""); }
 191
 192     // Cycle 9: { bh -> (bh0, bh1), {bh0, bh1} -> bh }
 193     let mut bh: BinaryHeap<BH> = BinaryHeap::new();
 194     bh.push(Named::new("bh0"));
 195     bh.push(Named::new("bh1"));
 196     for b in bh.iter() {
 197         b.contents.set(Some(&bh));
 198     }
 199
 200     let mut c = c_orig.clone();
 201     c.curr_mark = 90;
 202     for b in &bh {
 203         c.curr_mark += 1;
 204         c.saw_prev_marked = false;
 205         b.for_each_child(&mut c);
 206         assert!(c.saw_prev_marked);
 207         // break;
 208     }
 209
 210     if PRINT { println!(""); }
 211
 212     // Cycle 10: { btm -> (btk0, btv1), {bt0, bt1} -> btm }
 213     let mut btm: BTreeMap<BTM, BTM> = BTreeMap::new();
 214     btm.insert(Named::new("btk0"), Named::new("btv0"));
 215     btm.insert(Named::new("btk1"), Named::new("btv1"));
 216     for (k, v) in btm.iter() {
 217         k.contents.set(Some(&btm));
 218         v.contents.set(Some(&btm));
 219     }
 220
 221     let mut c = c_orig.clone();
 222     c.curr_mark = 100;
 223     for (k, _) in &btm {
 224         c.curr_mark += 1;
 225         c.saw_prev_marked = false;
 226         k.for_each_child(&mut c);
 227         assert!(c.saw_prev_marked);
 228         // break;
 229     }
 230
 231     if PRINT { println!(""); }
 232
 233     // Cycle 10: { bts -> (bts0, bts1), {bts0, bts1} -> btm }
 234     let mut bts: BTreeSet<BTS> = BTreeSet::new();
 235     bts.insert(Named::new("bts0"));
 236     bts.insert(Named::new("bts1"));
 237     for v in bts.iter() {
 238         v.contents.set(Some(&bts));
 239     }
 240
 241     let mut c = c_orig.clone();
 242     c.curr_mark = 100;
 243     for b in &bts {
 244         c.curr_mark += 1;
 245         c.saw_prev_marked = false;
 246         b.for_each_child(&mut c);
 247         assert!(c.saw_prev_marked);
 248         // break;
 249     }
 250 }
 251
 252 trait Named {
 253     fn new(&'static str) -> Self;
 254     fn name(&self) -> &str;
 255 }
 256
 257 trait Marked<M> {
 258     fn mark(&self) -> M;
 259     fn set_mark(&self, mark: M);
 260 }
 261
 262 struct S<'a> {
 263     name: &'static str,
 264     mark: Cell<u32>,
 265     next: Cell<Option<&'a S<'a>>>,
 266 }
 267
 268 impl<'a> Named for S<'a> {
 269     fn new<'b>(name: &'static str) -> S<'b> {
 270         S { name: name, mark: Cell::new(0), next: Cell::new(None) }
 271     }
 272     fn name(&self) -> &str { self.name }
 273 }
 274
 275 impl<'a> Marked<u32> for S<'a> {
 276     fn mark(&self) -> u32 { self.mark.get() }
 277     fn set_mark(&self, mark: u32) { self.mark.set(mark); }
 278 }
 279
 280 struct V<'a> {
 281     name: &'static str,
 282     mark: Cell<u32>,
 283     contents: Vec<Cell<Option<&'a V<'a>>>>,
 284 }
 285
 286 impl<'a> Named for V<'a> {
 287     fn new<'b>(name: &'static str) -> V<'b> {
 288         V { name: name,
 289             mark: Cell::new(0),
 290             contents: vec![Cell::new(None), Cell::new(None)]
 291         }
 292     }
 293     fn name(&self) -> &str { self.name }
 294 }
 295
 296 impl<'a> Marked<u32> for V<'a> {
 297     fn mark(&self) -> u32 { self.mark.get() }
 298     fn set_mark(&self, mark: u32) { self.mark.set(mark); }
 299 }
 300
 301 #[derive(Eq)]
 302 struct H<'a> {
 303     name: &'static str,
 304     mark: Cell<u32>,
 305     next: Cell<Option<&'a H<'a>>>,
 306 }
 307
 308 impl<'a> Named for H<'a> {
 309     fn new<'b>(name: &'static str) -> H<'b> {
 310         H { name: name, mark: Cell::new(0), next: Cell::new(None) }
 311     }
 312     fn name(&self) -> &str { self.name }
 313 }
 314
 315 impl<'a> Marked<u32> for H<'a> {
 316     fn mark(&self) -> u32 { self.mark.get() }
 317     fn set_mark(&self, mark: u32) { self.mark.set(mark); }
 318 }
 319
 320 impl<'a> PartialEq for H<'a> {
 321     fn eq(&self, rhs: &H<'a>) -> bool {
 322         self.name == rhs.name
 323     }
 324 }
 325
 326 impl<'a> Hash for H<'a> {
 327     fn hash<H: Hasher>(&self, state: &mut H) {
 328         self.name.hash(state)
 329     }
 330 }
 331
 332 #[derive(Eq)]
 333 struct HM<'a> {
 334     name: &'static str,
 335     mark: Cell<u32>,
 336     contents: Cell<Option<&'a HashMap<HM<'a>, HM<'a>>>>,
 337 }
 338
 339 impl<'a> Named for HM<'a> {
 340     fn new<'b>(name: &'static str) -> HM<'b> {
 341         HM { name: name,
 342              mark: Cell::new(0),
 343              contents: Cell::new(None)
 344         }
 345     }
 346     fn name(&self) -> &str { self.name }
 347 }
 348
 349 impl<'a> Marked<u32> for HM<'a> {
 350     fn mark(&self) -> u32 { self.mark.get() }
 351     fn set_mark(&self, mark: u32) { self.mark.set(mark); }
 352 }
 353
 354 impl<'a> PartialEq for HM<'a> {
 355     fn eq(&self, rhs: &HM<'a>) -> bool {
 356         self.name == rhs.name
 357     }
 358 }
 359
 360 impl<'a> Hash for HM<'a> {
 361     fn hash<H: Hasher>(&self, state: &mut H) {
 362         self.name.hash(state)
 363     }
 364 }
 365
 366
 367 struct VD<'a> {
 368     name: &'static str,
 369     mark: Cell<u32>,
 370     contents: Cell<Option<&'a VecDeque<VD<'a>>>>,
 371 }
 372
 373 impl<'a> Named for VD<'a> {
 374     fn new<'b>(name: &'static str) -> VD<'b> {
 375         VD { name: name,
 376              mark: Cell::new(0),
 377              contents: Cell::new(None)
 378         }
 379     }
 380     fn name(&self) -> &str { self.name }
 381 }
 382
 383 impl<'a> Marked<u32> for VD<'a> {
 384     fn mark(&self) -> u32 { self.mark.get() }
 385     fn set_mark(&self, mark: u32) { self.mark.set(mark); }
 386 }
 387
 388 struct VM<'a> {
 389     name: &'static str,
 390     mark: Cell<u32>,
 391     contents: Cell<Option<&'a VecMap<VM<'a>>>>,
 392 }
 393
 394 impl<'a> Named for VM<'a> {
 395     fn new<'b>(name: &'static str) -> VM<'b> {
 396         VM { name: name,
 397              mark: Cell::new(0),
 398              contents: Cell::new(None)
 399         }
 400     }
 401     fn name(&self) -> &str { self.name }
 402 }
 403
 404 impl<'a> Marked<u32> for VM<'a> {
 405     fn mark(&self) -> u32 { self.mark.get() }
 406     fn set_mark(&self, mark: u32) { self.mark.set(mark); }
 407 }
 408
 409 struct LL<'a> {
 410     name: &'static str,
 411     mark: Cell<u32>,
 412     contents: Cell<Option<&'a LinkedList<LL<'a>>>>,
 413 }
 414
 415 impl<'a> Named for LL<'a> {
 416     fn new<'b>(name: &'static str) -> LL<'b> {
 417         LL { name: name,
 418              mark: Cell::new(0),
 419              contents: Cell::new(None)
 420         }
 421     }
 422     fn name(&self) -> &str { self.name }
 423 }
 424
 425 impl<'a> Marked<u32> for LL<'a> {
 426     fn mark(&self) -> u32 { self.mark.get() }
 427     fn set_mark(&self, mark: u32) { self.mark.set(mark); }
 428 }
 429
 430 struct BH<'a> {
 431     name: &'static str,
 432     mark: Cell<u32>,
 433     contents: Cell<Option<&'a BinaryHeap<BH<'a>>>>,
 434 }
 435
 436 impl<'a> Named for BH<'a> {
 437     fn new<'b>(name: &'static str) -> BH<'b> {
 438         BH { name: name,
 439              mark: Cell::new(0),
 440              contents: Cell::new(None)
 441         }
 442     }
 443     fn name(&self) -> &str { self.name }
 444 }
 445
 446 impl<'a> Marked<u32> for BH<'a> {
 447     fn mark(&self) -> u32 { self.mark.get() }
 448     fn set_mark(&self, mark: u32) { self.mark.set(mark); }
 449 }
 450
 451 impl<'a> Eq for BH<'a> { }
 452
 453 impl<'a> PartialEq for BH<'a> {
 454     fn eq(&self, rhs: &BH<'a>) -> bool {
 455         self.name == rhs.name
 456     }
 457 }
 458
 459 impl<'a> PartialOrd for BH<'a> {
 460     fn partial_cmp(&self, rhs: &BH<'a>) -> Option<Ordering> {
 461         Some(self.cmp(rhs))
 462     }
 463 }
 464
 465 impl<'a> Ord for BH<'a> {
 466     fn cmp(&self, rhs: &BH<'a>) -> Ordering {
 467         self.name.cmp(rhs.name)
 468     }
 469 }
 470
 471 struct BTM<'a> {
 472     name: &'static str,
 473     mark: Cell<u32>,
 474     contents: Cell<Option<&'a BTreeMap<BTM<'a>, BTM<'a>>>>,
 475 }
 476
 477 impl<'a> Named for BTM<'a> {
 478     fn new<'b>(name: &'static str) -> BTM<'b> {
 479         BTM { name: name,
 480              mark: Cell::new(0),
 481              contents: Cell::new(None)
 482         }
 483     }
 484     fn name(&self) -> &str { self.name }
 485 }
 486
 487 impl<'a> Marked<u32> for BTM<'a> {
 488     fn mark(&self) -> u32 { self.mark.get() }
 489     fn set_mark(&self, mark: u32) { self.mark.set(mark); }
 490 }
 491
 492 impl<'a> Eq for BTM<'a> { }
 493
 494 impl<'a> PartialEq for BTM<'a> {
 495     fn eq(&self, rhs: &BTM<'a>) -> bool {
 496         self.name == rhs.name
 497     }
 498 }
 499
 500 impl<'a> PartialOrd for BTM<'a> {
 501     fn partial_cmp(&self, rhs: &BTM<'a>) -> Option<Ordering> {
 502         Some(self.cmp(rhs))
 503     }
 504 }
 505
 506 impl<'a> Ord for BTM<'a> {
 507     fn cmp(&self, rhs: &BTM<'a>) -> Ordering {
 508         self.name.cmp(rhs.name)
 509     }
 510 }
 511
 512 struct BTS<'a> {
 513     name: &'static str,
 514     mark: Cell<u32>,
 515     contents: Cell<Option<&'a BTreeSet<BTS<'a>>>>,
 516 }
 517
 518 impl<'a> Named for BTS<'a> {
 519     fn new<'b>(name: &'static str) -> BTS<'b> {
 520         BTS { name: name,
 521              mark: Cell::new(0),
 522              contents: Cell::new(None)
 523         }
 524     }
 525     fn name(&self) -> &str { self.name }
 526 }
 527
 528 impl<'a> Marked<u32> for BTS<'a> {
 529     fn mark(&self) -> u32 { self.mark.get() }
 530     fn set_mark(&self, mark: u32) { self.mark.set(mark); }
 531 }
 532
 533 impl<'a> Eq for BTS<'a> { }
 534
 535 impl<'a> PartialEq for BTS<'a> {
 536     fn eq(&self, rhs: &BTS<'a>) -> bool {
 537         self.name == rhs.name
 538     }
 539 }
 540
 541 impl<'a> PartialOrd for BTS<'a> {
 542     fn partial_cmp(&self, rhs: &BTS<'a>) -> Option<Ordering> {
 543         Some(self.cmp(rhs))
 544     }
 545 }
 546
 547 impl<'a> Ord for BTS<'a> {
 548     fn cmp(&self, rhs: &BTS<'a>) -> Ordering {
 549         self.name.cmp(rhs.name)
 550     }
 551 }
 552
 553
 554 trait Context {
 555     fn should_act(&self) -> bool;
 556     fn increase_visited(&mut self);
 557     fn increase_skipped(&mut self);
 558     fn increase_depth(&mut self);
 559     fn decrease_depth(&mut self);
 560 }
 561
 562 trait PrePost<T> {
 563     fn pre(&mut self, &T);
 564     fn post(&mut self, &T);
 565     fn hit_limit(&mut self, &T);
 566 }
 567
 568 trait Children<'a> {
 569     fn for_each_child<C>(&self, context: &mut C)
 570         where C: Context + PrePost<Self>, Self: Sized;
 571
 572     fn descend_into_self<C>(&self, context: &mut C)
 573         where C: Context + PrePost<Self>, Self: Sized
 574     {
 575         context.pre(self);
 576         if context.should_act() {
 577             context.increase_visited();
 578             context.increase_depth();
 579             self.for_each_child(context);
 580             context.decrease_depth();
 581         } else {
 582             context.hit_limit(self);
 583             context.increase_skipped();
 584         }
 585         context.post(self);
 586     }
 587
 588     fn descend<'b, C>(&self, c: &Cell<Option<&'b Self>>, context: &mut C)
 589         where C: Context + PrePost<Self>, Self: Sized
 590     {
 591         if let Some(r) = c.get() {
 592             r.descend_into_self(context);
 593         }
 594     }
 595 }
 596
 597 impl<'a> Children<'a> for S<'a> {
 598     fn for_each_child<C>(&self, context: &mut C)
 599         where C: Context + PrePost<S<'a>>
 600     {
 601         self.descend(&self.next, context);
 602     }
 603 }
 604
 605 impl<'a> Children<'a> for V<'a> {
 606     fn for_each_child<C>(&self, context: &mut C)
 607         where C: Context + PrePost<V<'a>>
 608     {
 609         for r in &self.contents {
 610             self.descend(r, context);
 611         }
 612     }
 613 }
 614
 615 impl<'a> Children<'a> for H<'a> {
 616     fn for_each_child<C>(&self, context: &mut C)
 617         where C: Context + PrePost<H<'a>>
 618     {
 619         self.descend(&self.next, context);
 620     }
 621 }
 622
 623 impl<'a> Children<'a> for HM<'a> {
 624     fn for_each_child<C>(&self, context: &mut C)
 625         where C: Context + PrePost<HM<'a>>
 626     {
 627         if let Some(ref hm) = self.contents.get() {
 628             for (k, v) in hm.iter() {
 629                 for r in &[k, v] {
 630                     r.descend_into_self(context);
 631                 }
 632             }
 633         }
 634     }
 635 }
 636
 637 impl<'a> Children<'a> for VD<'a> {
 638     fn for_each_child<C>(&self, context: &mut C)
 639         where C: Context + PrePost<VD<'a>>
 640     {
 641         if let Some(ref vd) = self.contents.get() {
 642             for r in vd.iter() {
 643                 r.descend_into_self(context);
 644             }
 645         }
 646     }
 647 }
 648
 649 impl<'a> Children<'a> for VM<'a> {
 650     fn for_each_child<C>(&self, context: &mut C)
 651         where C: Context + PrePost<VM<'a>>
 652     {
 653         if let Some(ref vd) = self.contents.get() {
 654             for (_idx, r) in vd.iter() {
 655                 r.descend_into_self(context);
 656             }
 657         }
 658     }
 659 }
 660
 661 impl<'a> Children<'a> for LL<'a> {
 662     fn for_each_child<C>(&self, context: &mut C)
 663         where C: Context + PrePost<LL<'a>>
 664     {
 665         if let Some(ref ll) = self.contents.get() {
 666             for r in ll.iter() {
 667                 r.descend_into_self(context);
 668             }
 669         }
 670     }
 671 }
 672
 673 impl<'a> Children<'a> for BH<'a> {
 674     fn for_each_child<C>(&self, context: &mut C)
 675         where C: Context + PrePost<BH<'a>>
 676     {
 677         if let Some(ref bh) = self.contents.get() {
 678             for r in bh.iter() {
 679                 r.descend_into_self(context);
 680             }
 681         }
 682     }
 683 }
 684
 685 impl<'a> Children<'a> for BTM<'a> {
 686     fn for_each_child<C>(&self, context: &mut C)
 687         where C: Context + PrePost<BTM<'a>>
 688     {
 689         if let Some(ref bh) = self.contents.get() {
 690             for (k, v) in bh.iter() {
 691                 for r in &[k, v] {
 692                     r.descend_into_self(context);
 693                 }
 694             }
 695         }
 696     }
 697 }
 698
 699 impl<'a> Children<'a> for BTS<'a> {
 700     fn for_each_child<C>(&self, context: &mut C)
 701         where C: Context + PrePost<BTS<'a>>
 702     {
 703         if let Some(ref bh) = self.contents.get() {
 704             for r in bh.iter() {
 705                 r.descend_into_self(context);
 706             }
 707         }
 708     }
 709 }
 710
 711 #[derive(Copy, Clone)]
 712 struct ContextData {
 713     curr_depth: usize,
 714     max_depth: usize,
 715     visited: usize,
 716     max_visits: usize,
 717     skipped: usize,
 718     curr_mark: u32,
 719     saw_prev_marked: bool,
 720 }
 721
 722 impl Context for ContextData {
 723     fn should_act(&self) -> bool {
 724         self.curr_depth < self.max_depth && self.visited < self.max_visits
 725     }
 726     fn increase_visited(&mut self) { self.visited += 1; }
 727     fn increase_skipped(&mut self) { self.skipped += 1; }
 728     fn increase_depth(&mut self) {  self.curr_depth += 1; }
 729     fn decrease_depth(&mut self) {  self.curr_depth -= 1; }
 730 }
 731
 732 impl<T:Named+Marked<u32>> PrePost<T> for ContextData {
 733     fn pre(&mut self, t: &T) {
 734         for _ in 0..self.curr_depth {
 735             if PRINT { print!(" "); }
 736         }
 737         if PRINT { println!("prev {}", t.name()); }
 738         if t.mark() == self.curr_mark {
 739             for _ in 0..self.curr_depth {
 740                 if PRINT { print!(" "); }
 741             }
 742             if PRINT { println!("(probably previously marked)"); }
 743             self.saw_prev_marked = true;
 744         }
 745         t.set_mark(self.curr_mark);
 746     }
 747     fn post(&mut self, t: &T) {
 748         for _ in 0..self.curr_depth {
 749             if PRINT { print!(" "); }
 750         }
 751         if PRINT { println!("post {}", t.name()); }
 752     }
 753     fn hit_limit(&mut self, t: &T) {
 754         for _ in 0..self.curr_depth {
 755             if PRINT { print!(" "); }
 756         }
 757         if PRINT { println!("LIMIT {}", t.name()); }
 758     }
 759 }