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 // HIGH LEVEL DESCRIPTION OF THE TEST ARCHITECTURE
  28 // -----------------------------------------------
  29 //
  30 // We pick a data structure and want to make a cyclic construction
  31 // from it. Each test of interest is labelled starting with "Cycle N:
  32 // { ... }" where N is the test number and the "..."`is filled in with
  33 // a graphviz-style description of the graph structure that the
  34 // author believes is being made. So "{ a -> b, b -> (c,d), (c,d) -> e }"
  35 // describes a line connected to a diamond:
  36 //
  37 //                           c
  38 //                          / \
  39 //                     a - b   e
  40 //                          \ /
  41 //                           d
  42 //
  43 // (Note that the above directed graph is actually acyclic.)
  44 //
  45 // The different graph structures are often composed of different data
  46 // types. Some may be built atop `Vec`, others atop `HashMap`, etc.
  47 //
  48 // For each graph structure, we actually *confirm* that a cycle exists
  49 // (as a safe-guard against a test author accidentally leaving it out)
  50 // by traversing each graph and "proving" that a cycle exists within it.
  51 //
  52 // To do this, while trying to keep the code uniform (despite working
  53 // with different underlying collection and smart-pointer types), we
  54 // have a standard traversal API:
  55 //
  56 // 1. every node in the graph carries a `mark` (a u32, init'ed to 0).
  57 //
  58 // 2. every node provides a method to visit its children
  59 //
  60 // 3. a traversal attmepts to visit the nodes of the graph and prove that
  61 //    it sees the same node twice. It does this by setting the mark of each
  62 //    node to a fresh non-zero value, and if it sees the current mark, it
  63 //    "knows" that it must have found a cycle, and stops attempting further
  64 //    traversal.
  65 //
  66 // 4. each traversal is controlled by a bit-string that tells it which child
  67 //    it visit when it can take different paths. As a simple example,
  68 //    in a binary tree, 0 could mean "left" (and 1, "right"), so that
  69 //    "00010" means "left, left, left, right, left". (In general it will
  70 //    read as many bits as it needs to choose one child.)
  71 //
  72 //    The graphs in this test are all meant to be very small, and thus
  73 //    short bitstrings of less than 64 bits should always suffice.
  74 //
  75 //    (An earlier version of this test infrastructure simply had any
  76 //    given traversal visit all children it encountered, in a
  77 //    depth-first manner; one problem with this approach is that an
  78 //    acyclic graph can still have sharing, which would then be treated
  79 //    as a repeat mark and reported as a detected cycle.)
  80 //
  81 // The travseral code is a little more complicated because it has been
  82 // programmed in a somewhat defensive manner. For example it also has
  83 // a max threshold for the number of nodes it will visit, to guard
  84 // against scenarios where the nodes are not correctly setting their
  85 // mark when asked. There are various other methods not discussed here
  86 // that are for aiding debugging the test when it runs, such as the
  87 // `name` method that all nodes provide.
  88 //
  89 // So each test:
  90 //
  91 // 1. allocates the nodes in the graph,
  92 //
  93 // 2. sets up the links in the graph,
  94 //
  95 // 3. clones the "ContextData"
  96 //
  97 // 4. chooses a new current mark value for this test
  98 //
  99 // 5. initiates a traversal, potentially from multiple starting points
 100 //    (aka "roots"), with a given control-string (potentially a
 101 //    different string for each root). if it does start from a
 102 //    distinct root, then such a test should also increment the
 103 //    current mark value, so that this traversal is considered
 104 //    distinct from the prior one on this graph structure.
 105 //
 106 //    Note that most of the tests work with the default control string
 107 //    of all-zeroes.
 108 //
 109 // 6. assert that the context confirms that it actually saw a cycle (since a traversal
 110 //    might have terminated, e.g. on a tree structure that contained no cycles).
 111
 112 use std::cell::{Cell, RefCell};
 113 use std::cmp::Ordering;
 114 use std::collections::BinaryHeap;
 115 use std::collections::HashMap;
 116 use std::collections::LinkedList;
 117 use std::collections::VecDeque;
 118 use std::collections::btree_map::BTreeMap;
 119 use std::collections::btree_set::BTreeSet;
 120 use std::hash::{Hash, Hasher};
 121 use std::rc::Rc;
 122 use std::sync::{Arc, RwLock, Mutex};
 123
 124 const PRINT: bool = false;
 125
 126 pub fn main() {
 127     let c_orig = ContextData {
 128         curr_depth: 0,
 129         max_depth: 3,
 130         visited: 0,
 131         max_visits: 1000,
 132         skipped: 0,
 133         curr_mark: 0,
 134         saw_prev_marked: false,
 135         control_bits: 0,
 136     };
 137
 138     // SANITY CHECK FOR TEST SUITE (thus unnumbered)
 139     // Not a cycle: { v[0] -> (v[1], v[2]), v[1] -> v[3], v[2] -> v[3] };
 140     let v: Vec<S2> = vec![Named::new("s0"),
 141                           Named::new("s1"),
 142                           Named::new("s2"),
 143                           Named::new("s3")];
 144     v[0].next.set((Some(&v[1]), Some(&v[2])));
 145     v[1].next.set((Some(&v[3]), None));
 146     v[2].next.set((Some(&v[3]), None));
 147     v[3].next.set((None, None));
 148
 149     let mut c = c_orig.clone();
 150     c.curr_mark = 10;
 151     assert!(!c.saw_prev_marked);
 152     v[0].descend_into_self(&mut c);
 153     assert!(!c.saw_prev_marked); // <-- different from below, b/c acyclic above
 154
 155     if PRINT { println!(""); }
 156
 157     // Cycle 1: { v[0] -> v[1], v[1] -> v[0] };
 158     // does not exercise `v` itself
 159     let v: Vec<S> = vec![Named::new("s0"),
 160                          Named::new("s1")];
 161     v[0].next.set(Some(&v[1]));
 162     v[1].next.set(Some(&v[0]));
 163
 164     let mut c = c_orig.clone();
 165     c.curr_mark = 10;
 166     assert!(!c.saw_prev_marked);
 167     v[0].descend_into_self(&mut c);
 168     assert!(c.saw_prev_marked);
 169
 170     if PRINT { println!(""); }
 171
 172     // Cycle 2: { v[0] -> v, v[1] -> v }
 173     let v: V = Named::new("v");
 174     v.contents[0].set(Some(&v));
 175     v.contents[1].set(Some(&v));
 176
 177     let mut c = c_orig.clone();
 178     c.curr_mark = 20;
 179     assert!(!c.saw_prev_marked);
 180     v.descend_into_self(&mut c);
 181     assert!(c.saw_prev_marked);
 182
 183     if PRINT { println!(""); }
 184
 185     // Cycle 3: { hk0 -> hv0, hv0 -> hk0, hk1 -> hv1, hv1 -> hk1 };
 186     // does not exercise `h` itself
 187
 188     let mut h: HashMap<H,H> = HashMap::new();
 189     h.insert(Named::new("hk0"), Named::new("hv0"));
 190     h.insert(Named::new("hk1"), Named::new("hv1"));
 191     for (key, val) in h.iter() {
 192         val.next.set(Some(key));
 193         key.next.set(Some(val));
 194     }
 195
 196     let mut c = c_orig.clone();
 197     c.curr_mark = 30;
 198     for (key, _) in h.iter() {
 199         c.curr_mark += 1;
 200         c.saw_prev_marked = false;
 201         key.descend_into_self(&mut c);
 202         assert!(c.saw_prev_marked);
 203     }
 204
 205     if PRINT { println!(""); }
 206
 207     // Cycle 4: { h -> (hmk0,hmv0,hmk1,hmv1), {hmk0,hmv0,hmk1,hmv1} -> h }
 208
 209     let mut h: HashMap<HM,HM> = HashMap::new();
 210     h.insert(Named::new("hmk0"), Named::new("hmv0"));
 211     h.insert(Named::new("hmk0"), Named::new("hmv0"));
 212     for (key, val) in h.iter() {
 213         val.contents.set(Some(&h));
 214         key.contents.set(Some(&h));
 215     }
 216
 217     let mut c = c_orig.clone();
 218     c.max_depth = 2;
 219     c.curr_mark = 40;
 220     for (key, _) in h.iter() {
 221         c.curr_mark += 1;
 222         c.saw_prev_marked = false;
 223         key.descend_into_self(&mut c);
 224         assert!(c.saw_prev_marked);
 225         // break;
 226     }
 227
 228     if PRINT { println!(""); }
 229
 230     // Cycle 5: { vd[0] -> vd[1], vd[1] -> vd[0] };
 231     // does not exercise vd itself
 232     let mut vd: VecDeque<S> = VecDeque::new();
 233     vd.push_back(Named::new("d0"));
 234     vd.push_back(Named::new("d1"));
 235     vd[0].next.set(Some(&vd[1]));
 236     vd[1].next.set(Some(&vd[0]));
 237
 238     let mut c = c_orig.clone();
 239     c.curr_mark = 50;
 240     assert!(!c.saw_prev_marked);
 241     vd[0].descend_into_self(&mut c);
 242     assert!(c.saw_prev_marked);
 243
 244     if PRINT { println!(""); }
 245
 246     // Cycle 6: { vd -> (vd0, vd1), {vd0, vd1} -> vd }
 247     let mut vd: VecDeque<VD> = VecDeque::new();
 248     vd.push_back(Named::new("vd0"));
 249     vd.push_back(Named::new("vd1"));
 250     vd[0].contents.set(Some(&vd));
 251     vd[1].contents.set(Some(&vd));
 252
 253     let mut c = c_orig.clone();
 254     c.curr_mark = 60;
 255     assert!(!c.saw_prev_marked);
 256     vd[0].descend_into_self(&mut c);
 257     assert!(c.saw_prev_marked);
 258
 259     if PRINT { println!(""); }
 260
 261     // Cycle 7: { vm -> (vm0, vm1), {vm0, vm1} -> vm }
 262     let mut vm: HashMap<usize, VM> = HashMap::new();
 263     vm.insert(0, Named::new("vm0"));
 264     vm.insert(1, Named::new("vm1"));
 265     vm[&0].contents.set(Some(&vm));
 266     vm[&1].contents.set(Some(&vm));
 267
 268     let mut c = c_orig.clone();
 269     c.curr_mark = 70;
 270     assert!(!c.saw_prev_marked);
 271     vm[&0].descend_into_self(&mut c);
 272     assert!(c.saw_prev_marked);
 273
 274     if PRINT { println!(""); }
 275
 276     // Cycle 8: { ll -> (ll0, ll1), {ll0, ll1} -> ll }
 277     let mut ll: LinkedList<LL> = LinkedList::new();
 278     ll.push_back(Named::new("ll0"));
 279     ll.push_back(Named::new("ll1"));
 280     for e in &ll {
 281         e.contents.set(Some(&ll));
 282     }
 283
 284     let mut c = c_orig.clone();
 285     c.curr_mark = 80;
 286     for e in &ll {
 287         c.curr_mark += 1;
 288         c.saw_prev_marked = false;
 289         e.descend_into_self(&mut c);
 290         assert!(c.saw_prev_marked);
 291         // break;
 292     }
 293
 294     if PRINT { println!(""); }
 295
 296     // Cycle 9: { bh -> (bh0, bh1), {bh0, bh1} -> bh }
 297     let mut bh: BinaryHeap<BH> = BinaryHeap::new();
 298     bh.push(Named::new("bh0"));
 299     bh.push(Named::new("bh1"));
 300     for b in bh.iter() {
 301         b.contents.set(Some(&bh));
 302     }
 303
 304     let mut c = c_orig.clone();
 305     c.curr_mark = 90;
 306     for b in &bh {
 307         c.curr_mark += 1;
 308         c.saw_prev_marked = false;
 309         b.descend_into_self(&mut c);
 310         assert!(c.saw_prev_marked);
 311         // break;
 312     }
 313
 314     if PRINT { println!(""); }
 315
 316     // Cycle 10: { btm -> (btk0, btv1), {bt0, bt1} -> btm }
 317     let mut btm: BTreeMap<BTM, BTM> = BTreeMap::new();
 318     btm.insert(Named::new("btk0"), Named::new("btv0"));
 319     btm.insert(Named::new("btk1"), Named::new("btv1"));
 320     for (k, v) in btm.iter() {
 321         k.contents.set(Some(&btm));
 322         v.contents.set(Some(&btm));
 323     }
 324
 325     let mut c = c_orig.clone();
 326     c.curr_mark = 100;
 327     for (k, _) in &btm {
 328         c.curr_mark += 1;
 329         c.saw_prev_marked = false;
 330         k.descend_into_self(&mut c);
 331         assert!(c.saw_prev_marked);
 332         // break;
 333     }
 334
 335     if PRINT { println!(""); }
 336
 337     // Cycle 10: { bts -> (bts0, bts1), {bts0, bts1} -> btm }
 338     let mut bts: BTreeSet<BTS> = BTreeSet::new();
 339     bts.insert(Named::new("bts0"));
 340     bts.insert(Named::new("bts1"));
 341     for v in bts.iter() {
 342         v.contents.set(Some(&bts));
 343     }
 344
 345     let mut c = c_orig.clone();
 346     c.curr_mark = 100;
 347     for b in &bts {
 348         c.curr_mark += 1;
 349         c.saw_prev_marked = false;
 350         b.descend_into_self(&mut c);
 351         assert!(c.saw_prev_marked);
 352         // break;
 353     }
 354
 355     if PRINT { println!(""); }
 356
 357     // Cycle 11: { rc0 -> (rc1, rc2), rc1 -> (), rc2 -> rc0 }
 358     let (rc0, rc1, rc2): (RCRC, RCRC, RCRC);
 359     rc0 = RCRC::new("rcrc0");
 360     rc1 = RCRC::new("rcrc1");
 361     rc2 = RCRC::new("rcrc2");
 362     rc0.0.borrow_mut().children.0 = Some(&rc1);
 363     rc0.0.borrow_mut().children.1 = Some(&rc2);
 364     rc2.0.borrow_mut().children.0 = Some(&rc0);
 365
 366     let mut c = c_orig.clone();
 367     c.control_bits = 0b1;
 368     c.curr_mark = 110;
 369     assert!(!c.saw_prev_marked);
 370     rc0.descend_into_self(&mut c);
 371     assert!(c.saw_prev_marked);
 372
 373     if PRINT { println!(""); }
 374
 375     // We want to take the previous Rc case and generalize it to Arc.
 376     //
 377     // We can use refcells if we're single-threaded (as this test is).
 378     // If one were to generalize these constructions to a
 379     // multi-threaded context, then it might seem like we could choose
 380     // between either a RwLock or a Mutex to hold the owned arcs on
 381     // each node.
 382     //
 383     // Part of the point of this test is to actually confirm that the
 384     // cycle exists by traversing it. We can do that just fine with an
 385     // RwLock (since we can grab the child pointers in read-only
 386     // mode), but we cannot lock a std::sync::Mutex to guard reading
 387     // from each node via the same pattern, since once you hit the
 388     // cycle, you'll be trying to acquring the same lock twice.
 389     // (We deal with this by exiting the traversal early if try_lock fails.)
 390
 391     // Cycle 12: { arc0 -> (arc1, arc2), arc1 -> (), arc2 -> arc0 }, refcells
 392     let (arc0, arc1, arc2): (ARCRC, ARCRC, ARCRC);
 393     arc0 = ARCRC::new("arcrc0");
 394     arc1 = ARCRC::new("arcrc1");
 395     arc2 = ARCRC::new("arcrc2");
 396     arc0.0.borrow_mut().children.0 = Some(&arc1);
 397     arc0.0.borrow_mut().children.1 = Some(&arc2);
 398     arc2.0.borrow_mut().children.0 = Some(&arc0);
 399
 400     let mut c = c_orig.clone();
 401     c.control_bits = 0b1;
 402     c.curr_mark = 110;
 403     assert!(!c.saw_prev_marked);
 404     arc0.descend_into_self(&mut c);
 405     assert!(c.saw_prev_marked);
 406
 407     if PRINT { println!(""); }
 408
 409     // Cycle 13: { arc0 -> (arc1, arc2), arc1 -> (), arc2 -> arc0 }, rwlocks
 410     let (arc0, arc1, arc2): (ARCRW, ARCRW, ARCRW);
 411     arc0 = ARCRW::new("arcrw0");
 412     arc1 = ARCRW::new("arcrw1");
 413     arc2 = ARCRW::new("arcrw2");
 414     arc0.0.write().unwrap().children.0 = Some(&arc1);
 415     arc0.0.write().unwrap().children.1 = Some(&arc2);
 416     arc2.0.write().unwrap().children.0 = Some(&arc0);
 417
 418     let mut c = c_orig.clone();
 419     c.control_bits = 0b1;
 420     c.curr_mark = 110;
 421     assert!(!c.saw_prev_marked);
 422     arc0.descend_into_self(&mut c);
 423     assert!(c.saw_prev_marked);
 424
 425     if PRINT { println!(""); }
 426
 427     // Cycle 14: { arc0 -> (arc1, arc2), arc1 -> (), arc2 -> arc0 }, mutexs
 428     let (arc0, arc1, arc2): (ARCM, ARCM, ARCM);
 429     arc0 = ARCM::new("arcm0");
 430     arc1 = ARCM::new("arcm1");
 431     arc2 = ARCM::new("arcm2");
 432     arc0.1.lock().unwrap().children.0 = Some(&arc1);
 433     arc0.1.lock().unwrap().children.1 = Some(&arc2);
 434     arc2.1.lock().unwrap().children.0 = Some(&arc0);
 435
 436     let mut c = c_orig.clone();
 437     c.control_bits = 0b1;
 438     c.curr_mark = 110;
 439     assert!(!c.saw_prev_marked);
 440     arc0.descend_into_self(&mut c);
 441     assert!(c.saw_prev_marked);
 442 }
 443
 444 trait Named {
 445     fn new(&'static str) -> Self;
 446     fn name(&self) -> &str;
 447 }
 448
 449 trait Marked<M> {
 450     fn mark(&self) -> M;
 451     fn set_mark(&self, mark: M);
 452 }
 453
 454 struct S<'a> {
 455     name: &'static str,
 456     mark: Cell<u32>,
 457     next: Cell<Option<&'a S<'a>>>,
 458 }
 459
 460 impl<'a> Named for S<'a> {
 461     fn new<'b>(name: &'static str) -> S<'b> {
 462         S { name: name, mark: Cell::new(0), next: Cell::new(None) }
 463     }
 464     fn name(&self) -> &str { self.name }
 465 }
 466
 467 impl<'a> Marked<u32> for S<'a> {
 468     fn mark(&self) -> u32 { self.mark.get() }
 469     fn set_mark(&self, mark: u32) { self.mark.set(mark); }
 470 }
 471
 472 struct S2<'a> {
 473     name: &'static str,
 474     mark: Cell<u32>,
 475     next: Cell<(Option<&'a S2<'a>>, Option<&'a S2<'a>>)>,
 476 }
 477
 478 impl<'a> Named for S2<'a> {
 479     fn new<'b>(name: &'static str) -> S2<'b> {
 480         S2 { name: name, mark: Cell::new(0), next: Cell::new((None, None)) }
 481     }
 482     fn name(&self) -> &str { self.name }
 483 }
 484
 485 impl<'a> Marked<u32> for S2<'a> {
 486     fn mark(&self) -> u32 { self.mark.get() }
 487     fn set_mark(&self, mark: u32) {
 488         self.mark.set(mark);
 489     }
 490 }
 491
 492 struct V<'a> {
 493     name: &'static str,
 494     mark: Cell<u32>,
 495     contents: Vec<Cell<Option<&'a V<'a>>>>,
 496 }
 497
 498 impl<'a> Named for V<'a> {
 499     fn new<'b>(name: &'static str) -> V<'b> {
 500         V { name: name,
 501             mark: Cell::new(0),
 502             contents: vec![Cell::new(None), Cell::new(None)]
 503         }
 504     }
 505     fn name(&self) -> &str { self.name }
 506 }
 507
 508 impl<'a> Marked<u32> for V<'a> {
 509     fn mark(&self) -> u32 { self.mark.get() }
 510     fn set_mark(&self, mark: u32) { self.mark.set(mark); }
 511 }
 512
 513 #[derive(Eq)]
 514 struct H<'a> {
 515     name: &'static str,
 516     mark: Cell<u32>,
 517     next: Cell<Option<&'a H<'a>>>,
 518 }
 519
 520 impl<'a> Named for H<'a> {
 521     fn new<'b>(name: &'static str) -> H<'b> {
 522         H { name: name, mark: Cell::new(0), next: Cell::new(None) }
 523     }
 524     fn name(&self) -> &str { self.name }
 525 }
 526
 527 impl<'a> Marked<u32> for H<'a> {
 528     fn mark(&self) -> u32 { self.mark.get() }
 529     fn set_mark(&self, mark: u32) { self.mark.set(mark); }
 530 }
 531
 532 impl<'a> PartialEq for H<'a> {
 533     fn eq(&self, rhs: &H<'a>) -> bool {
 534         self.name == rhs.name
 535     }
 536 }
 537
 538 impl<'a> Hash for H<'a> {
 539     fn hash<H: Hasher>(&self, state: &mut H) {
 540         self.name.hash(state)
 541     }
 542 }
 543
 544 #[derive(Eq)]
 545 struct HM<'a> {
 546     name: &'static str,
 547     mark: Cell<u32>,
 548     contents: Cell<Option<&'a HashMap<HM<'a>, HM<'a>>>>,
 549 }
 550
 551 impl<'a> Named for HM<'a> {
 552     fn new<'b>(name: &'static str) -> HM<'b> {
 553         HM { name: name,
 554              mark: Cell::new(0),
 555              contents: Cell::new(None)
 556         }
 557     }
 558     fn name(&self) -> &str { self.name }
 559 }
 560
 561 impl<'a> Marked<u32> for HM<'a> {
 562     fn mark(&self) -> u32 { self.mark.get() }
 563     fn set_mark(&self, mark: u32) { self.mark.set(mark); }
 564 }
 565
 566 impl<'a> PartialEq for HM<'a> {
 567     fn eq(&self, rhs: &HM<'a>) -> bool {
 568         self.name == rhs.name
 569     }
 570 }
 571
 572 impl<'a> Hash for HM<'a> {
 573     fn hash<H: Hasher>(&self, state: &mut H) {
 574         self.name.hash(state)
 575     }
 576 }
 577
 578
 579 struct VD<'a> {
 580     name: &'static str,
 581     mark: Cell<u32>,
 582     contents: Cell<Option<&'a VecDeque<VD<'a>>>>,
 583 }
 584
 585 impl<'a> Named for VD<'a> {
 586     fn new<'b>(name: &'static str) -> VD<'b> {
 587         VD { name: name,
 588              mark: Cell::new(0),
 589              contents: Cell::new(None)
 590         }
 591     }
 592     fn name(&self) -> &str { self.name }
 593 }
 594
 595 impl<'a> Marked<u32> for VD<'a> {
 596     fn mark(&self) -> u32 { self.mark.get() }
 597     fn set_mark(&self, mark: u32) { self.mark.set(mark); }
 598 }
 599
 600 struct VM<'a> {
 601     name: &'static str,
 602     mark: Cell<u32>,
 603     contents: Cell<Option<&'a HashMap<usize, VM<'a>>>>,
 604 }
 605
 606 impl<'a> Named for VM<'a> {
 607     fn new<'b>(name: &'static str) -> VM<'b> {
 608         VM { name: name,
 609              mark: Cell::new(0),
 610              contents: Cell::new(None)
 611         }
 612     }
 613     fn name(&self) -> &str { self.name }
 614 }
 615
 616 impl<'a> Marked<u32> for VM<'a> {
 617     fn mark(&self) -> u32 { self.mark.get() }
 618     fn set_mark(&self, mark: u32) { self.mark.set(mark); }
 619 }
 620
 621 struct LL<'a> {
 622     name: &'static str,
 623     mark: Cell<u32>,
 624     contents: Cell<Option<&'a LinkedList<LL<'a>>>>,
 625 }
 626
 627 impl<'a> Named for LL<'a> {
 628     fn new<'b>(name: &'static str) -> LL<'b> {
 629         LL { name: name,
 630              mark: Cell::new(0),
 631              contents: Cell::new(None)
 632         }
 633     }
 634     fn name(&self) -> &str { self.name }
 635 }
 636
 637 impl<'a> Marked<u32> for LL<'a> {
 638     fn mark(&self) -> u32 { self.mark.get() }
 639     fn set_mark(&self, mark: u32) { self.mark.set(mark); }
 640 }
 641
 642 struct BH<'a> {
 643     name: &'static str,
 644     mark: Cell<u32>,
 645     contents: Cell<Option<&'a BinaryHeap<BH<'a>>>>,
 646 }
 647
 648 impl<'a> Named for BH<'a> {
 649     fn new<'b>(name: &'static str) -> BH<'b> {
 650         BH { name: name,
 651              mark: Cell::new(0),
 652              contents: Cell::new(None)
 653         }
 654     }
 655     fn name(&self) -> &str { self.name }
 656 }
 657
 658 impl<'a> Marked<u32> for BH<'a> {
 659     fn mark(&self) -> u32 { self.mark.get() }
 660     fn set_mark(&self, mark: u32) { self.mark.set(mark); }
 661 }
 662
 663 impl<'a> Eq for BH<'a> { }
 664
 665 impl<'a> PartialEq for BH<'a> {
 666     fn eq(&self, rhs: &BH<'a>) -> bool {
 667         self.name == rhs.name
 668     }
 669 }
 670
 671 impl<'a> PartialOrd for BH<'a> {
 672     fn partial_cmp(&self, rhs: &BH<'a>) -> Option<Ordering> {
 673         Some(self.cmp(rhs))
 674     }
 675 }
 676
 677 impl<'a> Ord for BH<'a> {
 678     fn cmp(&self, rhs: &BH<'a>) -> Ordering {
 679         self.name.cmp(rhs.name)
 680     }
 681 }
 682
 683 struct BTM<'a> {
 684     name: &'static str,
 685     mark: Cell<u32>,
 686     contents: Cell<Option<&'a BTreeMap<BTM<'a>, BTM<'a>>>>,
 687 }
 688
 689 impl<'a> Named for BTM<'a> {
 690     fn new<'b>(name: &'static str) -> BTM<'b> {
 691         BTM { name: name,
 692              mark: Cell::new(0),
 693              contents: Cell::new(None)
 694         }
 695     }
 696     fn name(&self) -> &str { self.name }
 697 }
 698
 699 impl<'a> Marked<u32> for BTM<'a> {
 700     fn mark(&self) -> u32 { self.mark.get() }
 701     fn set_mark(&self, mark: u32) { self.mark.set(mark); }
 702 }
 703
 704 impl<'a> Eq for BTM<'a> { }
 705
 706 impl<'a> PartialEq for BTM<'a> {
 707     fn eq(&self, rhs: &BTM<'a>) -> bool {
 708         self.name == rhs.name
 709     }
 710 }
 711
 712 impl<'a> PartialOrd for BTM<'a> {
 713     fn partial_cmp(&self, rhs: &BTM<'a>) -> Option<Ordering> {
 714         Some(self.cmp(rhs))
 715     }
 716 }
 717
 718 impl<'a> Ord for BTM<'a> {
 719     fn cmp(&self, rhs: &BTM<'a>) -> Ordering {
 720         self.name.cmp(rhs.name)
 721     }
 722 }
 723
 724 struct BTS<'a> {
 725     name: &'static str,
 726     mark: Cell<u32>,
 727     contents: Cell<Option<&'a BTreeSet<BTS<'a>>>>,
 728 }
 729
 730 impl<'a> Named for BTS<'a> {
 731     fn new<'b>(name: &'static str) -> BTS<'b> {
 732         BTS { name: name,
 733              mark: Cell::new(0),
 734              contents: Cell::new(None)
 735         }
 736     }
 737     fn name(&self) -> &str { self.name }
 738 }
 739
 740 impl<'a> Marked<u32> for BTS<'a> {
 741     fn mark(&self) -> u32 { self.mark.get() }
 742     fn set_mark(&self, mark: u32) { self.mark.set(mark); }
 743 }
 744
 745 impl<'a> Eq for BTS<'a> { }
 746
 747 impl<'a> PartialEq for BTS<'a> {
 748     fn eq(&self, rhs: &BTS<'a>) -> bool {
 749         self.name == rhs.name
 750     }
 751 }
 752
 753 impl<'a> PartialOrd for BTS<'a> {
 754     fn partial_cmp(&self, rhs: &BTS<'a>) -> Option<Ordering> {
 755         Some(self.cmp(rhs))
 756     }
 757 }
 758
 759 impl<'a> Ord for BTS<'a> {
 760     fn cmp(&self, rhs: &BTS<'a>) -> Ordering {
 761         self.name.cmp(rhs.name)
 762     }
 763 }
 764
 765 #[derive(Clone)]
 766 struct RCRCData<'a> {
 767     name: &'static str,
 768     mark: Cell<u32>,
 769     children: (Option<&'a RCRC<'a>>, Option<&'a RCRC<'a>>),
 770 }
 771 #[derive(Clone)]
 772 struct RCRC<'a>(Rc<RefCell<RCRCData<'a>>>);
 773
 774 impl<'a> Named for RCRC<'a> {
 775     fn new(name: &'static str) -> Self {
 776         RCRC(Rc::new(RefCell::new(RCRCData {
 777             name: name, mark: Cell::new(0), children: (None, None), })))
 778     }
 779     fn name(&self) -> &str { self.0.borrow().name }
 780 }
 781
 782 impl<'a> Marked<u32> for RCRC<'a> {
 783     fn mark(&self) -> u32 { self.0.borrow().mark.get() }
 784     fn set_mark(&self, mark: u32) { self.0.borrow().mark.set(mark); }
 785 }
 786
 787 impl<'a> Children<'a> for RCRC<'a> {
 788     fn count_children(&self) -> usize { 2 }
 789     fn descend_one_child<C>(&self, context: &mut C, index: usize)
 790         where C: Context + PrePost<Self>, Self: Sized
 791     {
 792         let children = &self.0.borrow().children;
 793         let child = match index {
 794             0 => if let Some(child) = children.0 { child } else { return; },
 795             1 => if let Some(child) = children.1 { child } else { return; },
 796             _ => panic!("bad children"),
 797         };
 798         // println!("S2 {} descending into child {} at index {}", self.name, child.name, index);
 799         child.descend_into_self(context);
 800     }
 801 }
 802 #[derive(Clone)]
 803 struct ARCRCData<'a> {
 804     name: &'static str,
 805     mark: Cell<u32>,
 806     children: (Option<&'a ARCRC<'a>>, Option<&'a ARCRC<'a>>),
 807 }
 808 #[derive(Clone)]
 809 struct ARCRC<'a>(Arc<RefCell<ARCRCData<'a>>>);
 810
 811 impl<'a> Named for ARCRC<'a> {
 812     fn new(name: &'static str) -> Self {
 813         ARCRC(Arc::new(RefCell::new(ARCRCData {
 814             name: name, mark: Cell::new(0), children: (None, None), })))
 815     }
 816     fn name(&self) -> &str { self.0.borrow().name }
 817 }
 818
 819 impl<'a> Marked<u32> for ARCRC<'a> {
 820     fn mark(&self) -> u32 { self.0.borrow().mark.get() }
 821     fn set_mark(&self, mark: u32) { self.0.borrow().mark.set(mark); }
 822 }
 823
 824 impl<'a> Children<'a> for ARCRC<'a> {
 825     fn count_children(&self) -> usize { 2 }
 826     fn descend_one_child<C>(&self, context: &mut C, index: usize)
 827         where C: Context + PrePost<Self>, Self: Sized
 828     {
 829         let children = &self.0.borrow().children;
 830         match index {
 831             0 => if let Some(ref child) = children.0 {
 832                 child.descend_into_self(context);
 833             },
 834             1 => if let Some(ref child) = children.1 {
 835                 child.descend_into_self(context);
 836             },
 837             _ => panic!("bad children!"),
 838         }
 839     }
 840 }
 841
 842 #[derive(Clone)]
 843 struct ARCMData<'a> {
 844     mark: Cell<u32>,
 845     children: (Option<&'a ARCM<'a>>, Option<&'a ARCM<'a>>),
 846 }
 847
 848 #[derive(Clone)]
 849 struct ARCM<'a>(&'static str, Arc<Mutex<ARCMData<'a>>>);
 850
 851 impl<'a> Named for ARCM<'a> {
 852     fn new(name: &'static str) -> Self {
 853         ARCM(name, Arc::new(Mutex::new(ARCMData {
 854             mark: Cell::new(0), children: (None, None), })))
 855     }
 856     fn name(&self) -> &str { self.0 }
 857 }
 858
 859 impl<'a> Marked<u32> for ARCM<'a> {
 860     fn mark(&self) -> u32 { self.1.lock().unwrap().mark.get() }
 861     fn set_mark(&self, mark: u32) { self.1.lock().unwrap().mark.set(mark); }
 862 }
 863
 864 impl<'a> Children<'a> for ARCM<'a> {
 865     fn count_children(&self) -> usize { 2 }
 866     fn descend_one_child<C>(&self, context: &mut C, index: usize)
 867         where C: Context + PrePost<Self>, Self: Sized
 868     {
 869         let ref children = if let Ok(data) = self.1.try_lock() {
 870             data.children
 871         } else { return; };
 872         match index {
 873             0 => if let Some(ref child) = children.0 {
 874                 child.descend_into_self(context);
 875             },
 876             1 => if let Some(ref child) = children.1 {
 877                 child.descend_into_self(context);
 878             },
 879             _ => panic!("bad children!"),
 880         }
 881     }
 882 }
 883
 884 #[derive(Clone)]
 885 struct ARCRWData<'a> {
 886     name: &'static str,
 887     mark: Cell<u32>,
 888     children: (Option<&'a ARCRW<'a>>, Option<&'a ARCRW<'a>>),
 889 }
 890
 891 #[derive(Clone)]
 892 struct ARCRW<'a>(Arc<RwLock<ARCRWData<'a>>>);
 893
 894 impl<'a> Named for ARCRW<'a> {
 895     fn new(name: &'static str) -> Self {
 896         ARCRW(Arc::new(RwLock::new(ARCRWData {
 897             name: name, mark: Cell::new(0), children: (None, None), })))
 898     }
 899     fn name(&self) -> &str { self.0.read().unwrap().name }
 900 }
 901
 902 impl<'a> Marked<u32> for ARCRW<'a> {
 903     fn mark(&self) -> u32 { self.0.read().unwrap().mark.get() }
 904     fn set_mark(&self, mark: u32) { self.0.read().unwrap().mark.set(mark); }
 905 }
 906
 907 impl<'a> Children<'a> for ARCRW<'a> {
 908     fn count_children(&self) -> usize { 2 }
 909     fn descend_one_child<C>(&self, context: &mut C, index: usize)
 910         where C: Context + PrePost<Self>, Self: Sized
 911     {
 912         let children = &self.0.read().unwrap().children;
 913         match index {
 914             0 => if let Some(ref child) = children.0 {
 915                 child.descend_into_self(context);
 916             },
 917             1 => if let Some(ref child) = children.1 {
 918                 child.descend_into_self(context);
 919             },
 920             _ => panic!("bad children!"),
 921         }
 922     }
 923 }
 924
 925 trait Context {
 926     fn next_index(&mut self, len: usize) -> usize;
 927     fn should_act(&self) -> bool;
 928     fn increase_visited(&mut self);
 929     fn increase_skipped(&mut self);
 930     fn increase_depth(&mut self);
 931     fn decrease_depth(&mut self);
 932 }
 933
 934 trait PrePost<T> {
 935     fn pre(&mut self, &T);
 936     fn post(&mut self, &T);
 937     fn hit_limit(&mut self, &T);
 938 }
 939
 940 trait Children<'a> {
 941     fn count_children(&self) -> usize;
 942     fn descend_one_child<C>(&self, context: &mut C, index: usize)
 943         where C: Context + PrePost<Self>, Self: Sized;
 944
 945     fn next_child<C>(&self, context: &mut C)
 946         where C: Context + PrePost<Self>, Self: Sized
 947     {
 948         let index = context.next_index(self.count_children());
 949         self.descend_one_child(context, index);
 950     }
 951
 952     fn descend_into_self<C>(&self, context: &mut C)
 953         where C: Context + PrePost<Self>, Self: Sized
 954     {
 955         context.pre(self);
 956         if context.should_act() {
 957             context.increase_visited();
 958             context.increase_depth();
 959             self.next_child(context);
 960             context.decrease_depth();
 961         } else {
 962             context.hit_limit(self);
 963             context.increase_skipped();
 964         }
 965         context.post(self);
 966     }
 967
 968     fn descend<'b, C>(&self, c: &Cell<Option<&'b Self>>, context: &mut C)
 969         where C: Context + PrePost<Self>, Self: Sized
 970     {
 971         if let Some(r) = c.get() {
 972             r.descend_into_self(context);
 973         }
 974     }
 975 }
 976
 977 impl<'a> Children<'a> for S<'a> {
 978     fn count_children(&self) -> usize { 1 }
 979     fn descend_one_child<C>(&self, context: &mut C, _: usize)
 980         where C: Context + PrePost<Self>, Self: Sized {
 981             self.descend(&self.next, context);
 982         }
 983 }
 984
 985 impl<'a> Children<'a> for S2<'a> {
 986     fn count_children(&self) -> usize { 2 }
 987     fn descend_one_child<C>(&self, context: &mut C, index: usize)
 988         where C: Context + PrePost<Self>, Self: Sized
 989     {
 990         let children = self.next.get();
 991         let child = match index {
 992             0 => if let Some(child) = children.0 { child } else { return; },
 993             1 => if let Some(child) = children.1 { child } else { return; },
 994             _ => panic!("bad children"),
 995         };
 996         // println!("S2 {} descending into child {} at index {}", self.name, child.name, index);
 997         child.descend_into_self(context);
 998     }
 999 }
1000
1001 impl<'a> Children<'a> for V<'a> {
1002     fn count_children(&self) -> usize { self.contents.len() }
1003     fn descend_one_child<C>(&self, context: &mut C, index: usize)
1004         where C: Context + PrePost<Self>, Self: Sized
1005     {
1006         if let Some(child) = self.contents[index].get() {
1007             child.descend_into_self(context);
1008         }
1009     }
1010 }
1011
1012 impl<'a> Children<'a> for H<'a> {
1013     fn count_children(&self) -> usize { 1 }
1014     fn descend_one_child<C>(&self, context: &mut C, _: usize)
1015         where C: Context + PrePost<Self>, Self: Sized
1016     {
1017         self.descend(&self.next, context);
1018     }
1019 }
1020
1021 impl<'a> Children<'a> for HM<'a> {
1022     fn count_children(&self) -> usize {
1023         if let Some(m) = self.contents.get() { 2 * m.iter().count() } else { 0 }
1024     }
1025     fn descend_one_child<C>(&self, context: &mut C, index: usize)
1026         where C: Context + PrePost<Self>, Self: Sized
1027     {
1028         if let Some(ref hm) = self.contents.get() {
1029             for (k, v) in hm.iter().nth(index / 2) {
1030                 [k, v][index % 2].descend_into_self(context);
1031             }
1032         }
1033     }
1034 }
1035
1036 impl<'a> Children<'a> for VD<'a> {
1037     fn count_children(&self) -> usize {
1038         if let Some(d) = self.contents.get() { d.iter().count() } else { 0 }
1039     }
1040     fn descend_one_child<C>(&self, context: &mut C, index: usize)
1041         where C: Context + PrePost<Self>, Self: Sized
1042     {
1043         if let Some(ref vd) = self.contents.get() {
1044             for r in vd.iter().nth(index) {
1045                 r.descend_into_self(context);
1046             }
1047         }
1048     }
1049 }
1050
1051 impl<'a> Children<'a> for VM<'a> {
1052     fn count_children(&self) -> usize {
1053         if let Some(m) = self.contents.get() { m.iter().count() } else { 0 }
1054     }
1055     fn descend_one_child<C>(&self, context: &mut C, index: usize)
1056         where C: Context + PrePost<VM<'a>>
1057     {
1058         if let Some(ref vd) = self.contents.get() {
1059             for (_idx, r) in vd.iter().nth(index) {
1060                 r.descend_into_self(context);
1061             }
1062         }
1063     }
1064 }
1065
1066 impl<'a> Children<'a> for LL<'a> {
1067     fn count_children(&self) -> usize {
1068         if let Some(l) = self.contents.get() { l.iter().count() } else { 0 }
1069     }
1070     fn descend_one_child<C>(&self, context: &mut C, index: usize)
1071         where C: Context + PrePost<LL<'a>>
1072     {
1073         if let Some(ref ll) = self.contents.get() {
1074             for r in ll.iter().nth(index) {
1075                 r.descend_into_self(context);
1076             }
1077         }
1078     }
1079 }
1080
1081 impl<'a> Children<'a> for BH<'a> {
1082     fn count_children(&self) -> usize {
1083         if let Some(h) = self.contents.get() { h.iter().count() } else { 0 }
1084     }
1085     fn descend_one_child<C>(&self, context: &mut C, index: usize)
1086         where C: Context + PrePost<BH<'a>>
1087     {
1088         if let Some(ref bh) = self.contents.get() {
1089             for r in bh.iter().nth(index) {
1090                 r.descend_into_self(context);
1091             }
1092         }
1093     }
1094 }
1095
1096 impl<'a> Children<'a> for BTM<'a> {
1097     fn count_children(&self) -> usize {
1098         if let Some(m) = self.contents.get() { 2 * m.iter().count() } else { 0 }
1099     }
1100     fn descend_one_child<C>(&self, context: &mut C, index: usize)
1101         where C: Context + PrePost<BTM<'a>>
1102     {
1103         if let Some(ref bh) = self.contents.get() {
1104             for (k, v) in bh.iter().nth(index / 2) {
1105                 [k, v][index % 2].descend_into_self(context);
1106             }
1107         }
1108     }
1109 }
1110
1111 impl<'a> Children<'a> for BTS<'a> {
1112     fn count_children(&self) -> usize {
1113         if let Some(s) = self.contents.get() { s.iter().count() } else { 0 }
1114     }
1115     fn descend_one_child<C>(&self, context: &mut C, index: usize)
1116         where C: Context + PrePost<BTS<'a>>
1117     {
1118         if let Some(ref bh) = self.contents.get() {
1119             for r in bh.iter().nth(index) {
1120                 r.descend_into_self(context);
1121             }
1122         }
1123     }
1124 }
1125
1126 #[derive(Copy, Clone)]
1127 struct ContextData {
1128     curr_depth: usize,
1129     max_depth: usize,
1130     visited: usize,
1131     max_visits: usize,
1132     skipped: usize,
1133     curr_mark: u32,
1134     saw_prev_marked: bool,
1135     control_bits: u64,
1136 }
1137
1138 impl Context for ContextData {
1139     fn next_index(&mut self, len: usize) -> usize {
1140         if len < 2 { return 0; }
1141         let mut pow2 = len.next_power_of_two();
1142         let _pow2_orig = pow2;
1143         let mut idx = 0;
1144         let mut bits = self.control_bits;
1145         while pow2 > 1 {
1146             idx = (idx << 1) | (bits & 1) as usize;
1147             bits = bits >> 1;
1148             pow2 = pow2 >> 1;
1149         }
1150         idx = idx % len;
1151         // println!("next_index({} [{:b}]) says {}, pre(bits): {:b} post(bits): {:b}",
1152         //          len, _pow2_orig, idx, self.control_bits, bits);
1153         self.control_bits = bits;
1154         return idx;
1155     }
1156     fn should_act(&self) -> bool {
1157         self.curr_depth < self.max_depth && self.visited < self.max_visits
1158     }
1159     fn increase_visited(&mut self) { self.visited += 1; }
1160     fn increase_skipped(&mut self) { self.skipped += 1; }
1161     fn increase_depth(&mut self) {  self.curr_depth += 1; }
1162     fn decrease_depth(&mut self) {  self.curr_depth -= 1; }
1163 }
1164
1165 impl<T:Named+Marked<u32>> PrePost<T> for ContextData {
1166     fn pre(&mut self, t: &T) {
1167         for _ in 0..self.curr_depth {
1168             if PRINT { print!(" "); }
1169         }
1170         if PRINT { println!("prev {}", t.name()); }
1171         if t.mark() == self.curr_mark {
1172             for _ in 0..self.curr_depth {
1173                 if PRINT { print!(" "); }
1174             }
1175             if PRINT { println!("(probably previously marked)"); }
1176             self.saw_prev_marked = true;
1177         }
1178         t.set_mark(self.curr_mark);
1179     }
1180     fn post(&mut self, t: &T) {
1181         for _ in 0..self.curr_depth {
1182             if PRINT { print!(" "); }
1183         }
1184         if PRINT { println!("post {}", t.name()); }
1185     }
1186     fn hit_limit(&mut self, t: &T) {
1187         for _ in 0..self.curr_depth {
1188             if PRINT { print!(" "); }
1189         }
1190         if PRINT { println!("LIMIT {}", t.name()); }
1191     }
1192 }