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