From 218caa410aa38c29984be31a5229b9fa717560ee Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:19:13 +0200 Subject: Merging upstream version 1.68.2+dfsg1. Signed-off-by: Daniel Baumann --- src/test/ui/drop/dropck_legal_cycles.rs | 1183 ------------------------------- 1 file changed, 1183 deletions(-) delete mode 100644 src/test/ui/drop/dropck_legal_cycles.rs (limited to 'src/test/ui/drop/dropck_legal_cycles.rs') diff --git a/src/test/ui/drop/dropck_legal_cycles.rs b/src/test/ui/drop/dropck_legal_cycles.rs deleted file mode 100644 index 6a0fe7784..000000000 --- a/src/test/ui/drop/dropck_legal_cycles.rs +++ /dev/null @@ -1,1183 +0,0 @@ -// run-pass -// This test exercises cases where cyclic structure is legal, -// including when the cycles go through data-structures such -// as `Vec` or `TypedArena`. -// -// The intent is to cover as many such cases as possible, ensuring -// that if the compiler did not complain circa Rust 1.x (1.2 as of -// this writing), then it will continue to not complain in the future. -// -// Note that while some of the tests are only exercising using the -// given collection as a "backing store" for a set of nodes that hold -// the actual cycle (and thus the cycle does not go through the -// collection itself in such cases), in general we *do* want to make -// sure to have at least one example exercising a cycle that goes -// through the collection, for every collection type that supports -// this. - -// HIGH LEVEL DESCRIPTION OF THE TEST ARCHITECTURE -// ----------------------------------------------- -// -// We pick a data structure and want to make a cyclic construction -// from it. Each test of interest is labelled starting with "Cycle N: -// { ... }" where N is the test number and the "..."`is filled in with -// a graphviz-style description of the graph structure that the -// author believes is being made. So "{ a -> b, b -> (c,d), (c,d) -> e }" -// describes a line connected to a diamond: -// -// c -// / \ -// a - b e -// \ / -// d -// -// (Note that the above directed graph is actually acyclic.) -// -// The different graph structures are often composed of different data -// types. Some may be built atop `Vec`, others atop `HashMap`, etc. -// -// For each graph structure, we actually *confirm* that a cycle exists -// (as a safe-guard against a test author accidentally leaving it out) -// by traversing each graph and "proving" that a cycle exists within it. -// -// To do this, while trying to keep the code uniform (despite working -// with different underlying collection and smart-pointer types), we -// have a standard traversal API: -// -// 1. every node in the graph carries a `mark` (a u32, init'ed to 0). -// -// 2. every node provides a method to visit its children -// -// 3. a traversal attmepts to visit the nodes of the graph and prove that -// it sees the same node twice. It does this by setting the mark of each -// node to a fresh non-zero value, and if it sees the current mark, it -// "knows" that it must have found a cycle, and stops attempting further -// traversal. -// -// 4. each traversal is controlled by a bit-string that tells it which child -// it visit when it can take different paths. As a simple example, -// in a binary tree, 0 could mean "left" (and 1, "right"), so that -// "00010" means "left, left, left, right, left". (In general it will -// read as many bits as it needs to choose one child.) -// -// The graphs in this test are all meant to be very small, and thus -// short bitstrings of less than 64 bits should always suffice. -// -// (An earlier version of this test infrastructure simply had any -// given traversal visit all children it encountered, in a -// depth-first manner; one problem with this approach is that an -// acyclic graph can still have sharing, which would then be treated -// as a repeat mark and reported as a detected cycle.) -// -// The travseral code is a little more complicated because it has been -// programmed in a somewhat defensive manner. For example it also has -// a max threshold for the number of nodes it will visit, to guard -// against scenarios where the nodes are not correctly setting their -// mark when asked. There are various other methods not discussed here -// that are for aiding debugging the test when it runs, such as the -// `name` method that all nodes provide. -// -// So each test: -// -// 1. allocates the nodes in the graph, -// -// 2. sets up the links in the graph, -// -// 3. clones the "ContextData" -// -// 4. chooses a new current mark value for this test -// -// 5. initiates a traversal, potentially from multiple starting points -// (aka "roots"), with a given control-string (potentially a -// different string for each root). if it does start from a -// distinct root, then such a test should also increment the -// current mark value, so that this traversal is considered -// distinct from the prior one on this graph structure. -// -// Note that most of the tests work with the default control string -// of all-zeroes. -// -// 6. assert that the context confirms that it actually saw a cycle (since a traversal -// might have terminated, e.g., on a tree structure that contained no cycles). - -use std::cell::{Cell, RefCell}; -use std::cmp::Ordering; -use std::collections::BinaryHeap; -use std::collections::HashMap; -use std::collections::LinkedList; -use std::collections::VecDeque; -use std::collections::btree_map::BTreeMap; -use std::collections::btree_set::BTreeSet; -use std::hash::{Hash, Hasher}; -use std::rc::Rc; -use std::sync::{Arc, RwLock, Mutex}; - -const PRINT: bool = false; - -pub fn main() { - let c_orig = ContextData { - curr_depth: 0, - max_depth: 3, - visited: 0, - max_visits: 1000, - skipped: 0, - curr_mark: 0, - saw_prev_marked: false, - control_bits: 0, - }; - - // SANITY CHECK FOR TEST SUITE (thus unnumbered) - // Not a cycle: { v[0] -> (v[1], v[2]), v[1] -> v[3], v[2] -> v[3] }; - let v: Vec = vec![Named::new("s0"), - Named::new("s1"), - Named::new("s2"), - Named::new("s3")]; - v[0].next.set((Some(&v[1]), Some(&v[2]))); - v[1].next.set((Some(&v[3]), None)); - v[2].next.set((Some(&v[3]), None)); - v[3].next.set((None, None)); - - let mut c = c_orig.clone(); - c.curr_mark = 10; - assert!(!c.saw_prev_marked); - v[0].descend_into_self(&mut c); - assert!(!c.saw_prev_marked); // <-- different from below, b/c acyclic above - - if PRINT { println!(); } - - // Cycle 1: { v[0] -> v[1], v[1] -> v[0] }; - // does not exercise `v` itself - let v: Vec = vec![Named::new("s0"), - Named::new("s1")]; - v[0].next.set(Some(&v[1])); - v[1].next.set(Some(&v[0])); - - let mut c = c_orig.clone(); - c.curr_mark = 10; - assert!(!c.saw_prev_marked); - v[0].descend_into_self(&mut c); - assert!(c.saw_prev_marked); - - if PRINT { println!(); } - - // Cycle 2: { v[0] -> v, v[1] -> v } - let v: V = Named::new("v"); - v.contents[0].set(Some(&v)); - v.contents[1].set(Some(&v)); - - let mut c = c_orig.clone(); - c.curr_mark = 20; - assert!(!c.saw_prev_marked); - v.descend_into_self(&mut c); - assert!(c.saw_prev_marked); - - if PRINT { println!(); } - - // Cycle 3: { hk0 -> hv0, hv0 -> hk0, hk1 -> hv1, hv1 -> hk1 }; - // does not exercise `h` itself - - let mut h: HashMap = HashMap::new(); - h.insert(Named::new("hk0"), Named::new("hv0")); - h.insert(Named::new("hk1"), Named::new("hv1")); - for (key, val) in h.iter() { - val.next.set(Some(key)); - key.next.set(Some(val)); - } - - let mut c = c_orig.clone(); - c.curr_mark = 30; - for (key, _) in h.iter() { - c.curr_mark += 1; - c.saw_prev_marked = false; - key.descend_into_self(&mut c); - assert!(c.saw_prev_marked); - } - - if PRINT { println!(); } - - // Cycle 4: { h -> (hmk0,hmv0,hmk1,hmv1), {hmk0,hmv0,hmk1,hmv1} -> h } - - let mut h: HashMap = HashMap::new(); - h.insert(Named::new("hmk0"), Named::new("hmv0")); - h.insert(Named::new("hmk0"), Named::new("hmv0")); - for (key, val) in h.iter() { - val.contents.set(Some(&h)); - key.contents.set(Some(&h)); - } - - let mut c = c_orig.clone(); - c.max_depth = 2; - c.curr_mark = 40; - for (key, _) in h.iter() { - c.curr_mark += 1; - c.saw_prev_marked = false; - key.descend_into_self(&mut c); - assert!(c.saw_prev_marked); - // break; - } - - if PRINT { println!(); } - - // Cycle 5: { vd[0] -> vd[1], vd[1] -> vd[0] }; - // does not exercise vd itself - let mut vd: VecDeque = VecDeque::new(); - vd.push_back(Named::new("d0")); - vd.push_back(Named::new("d1")); - vd[0].next.set(Some(&vd[1])); - vd[1].next.set(Some(&vd[0])); - - let mut c = c_orig.clone(); - c.curr_mark = 50; - assert!(!c.saw_prev_marked); - vd[0].descend_into_self(&mut c); - assert!(c.saw_prev_marked); - - if PRINT { println!(); } - - // Cycle 6: { vd -> (vd0, vd1), {vd0, vd1} -> vd } - let mut vd: VecDeque = VecDeque::new(); - vd.push_back(Named::new("vd0")); - vd.push_back(Named::new("vd1")); - vd[0].contents.set(Some(&vd)); - vd[1].contents.set(Some(&vd)); - - let mut c = c_orig.clone(); - c.curr_mark = 60; - assert!(!c.saw_prev_marked); - vd[0].descend_into_self(&mut c); - assert!(c.saw_prev_marked); - - if PRINT { println!(); } - - // Cycle 7: { vm -> (vm0, vm1), {vm0, vm1} -> vm } - let mut vm: HashMap = HashMap::new(); - vm.insert(0, Named::new("vm0")); - vm.insert(1, Named::new("vm1")); - vm[&0].contents.set(Some(&vm)); - vm[&1].contents.set(Some(&vm)); - - let mut c = c_orig.clone(); - c.curr_mark = 70; - assert!(!c.saw_prev_marked); - vm[&0].descend_into_self(&mut c); - assert!(c.saw_prev_marked); - - if PRINT { println!(); } - - // Cycle 8: { ll -> (ll0, ll1), {ll0, ll1} -> ll } - let mut ll: LinkedList = LinkedList::new(); - ll.push_back(Named::new("ll0")); - ll.push_back(Named::new("ll1")); - for e in &ll { - e.contents.set(Some(&ll)); - } - - let mut c = c_orig.clone(); - c.curr_mark = 80; - for e in &ll { - c.curr_mark += 1; - c.saw_prev_marked = false; - e.descend_into_self(&mut c); - assert!(c.saw_prev_marked); - // break; - } - - if PRINT { println!(); } - - // Cycle 9: { bh -> (bh0, bh1), {bh0, bh1} -> bh } - let mut bh: BinaryHeap = BinaryHeap::new(); - bh.push(Named::new("bh0")); - bh.push(Named::new("bh1")); - for b in bh.iter() { - b.contents.set(Some(&bh)); - } - - let mut c = c_orig.clone(); - c.curr_mark = 90; - for b in &bh { - c.curr_mark += 1; - c.saw_prev_marked = false; - b.descend_into_self(&mut c); - assert!(c.saw_prev_marked); - // break; - } - - if PRINT { println!(); } - - // Cycle 10: { btm -> (btk0, btv1), {bt0, bt1} -> btm } - let mut btm: BTreeMap = BTreeMap::new(); - btm.insert(Named::new("btk0"), Named::new("btv0")); - btm.insert(Named::new("btk1"), Named::new("btv1")); - for (k, v) in btm.iter() { - k.contents.set(Some(&btm)); - v.contents.set(Some(&btm)); - } - - let mut c = c_orig.clone(); - c.curr_mark = 100; - for (k, _) in &btm { - c.curr_mark += 1; - c.saw_prev_marked = false; - k.descend_into_self(&mut c); - assert!(c.saw_prev_marked); - // break; - } - - if PRINT { println!(); } - - // Cycle 10: { bts -> (bts0, bts1), {bts0, bts1} -> btm } - let mut bts: BTreeSet = BTreeSet::new(); - bts.insert(Named::new("bts0")); - bts.insert(Named::new("bts1")); - for v in bts.iter() { - v.contents.set(Some(&bts)); - } - - let mut c = c_orig.clone(); - c.curr_mark = 100; - for b in &bts { - c.curr_mark += 1; - c.saw_prev_marked = false; - b.descend_into_self(&mut c); - assert!(c.saw_prev_marked); - // break; - } - - if PRINT { println!(); } - - // Cycle 11: { rc0 -> (rc1, rc2), rc1 -> (), rc2 -> rc0 } - let (rc0, rc1, rc2): (RCRC, RCRC, RCRC); - rc0 = RCRC::new("rcrc0"); - rc1 = RCRC::new("rcrc1"); - rc2 = RCRC::new("rcrc2"); - rc0.0.borrow_mut().children.0 = Some(&rc1); - rc0.0.borrow_mut().children.1 = Some(&rc2); - rc2.0.borrow_mut().children.0 = Some(&rc0); - - let mut c = c_orig.clone(); - c.control_bits = 0b1; - c.curr_mark = 110; - assert!(!c.saw_prev_marked); - rc0.descend_into_self(&mut c); - assert!(c.saw_prev_marked); - - if PRINT { println!(); } - - // We want to take the previous Rc case and generalize it to Arc. - // - // We can use refcells if we're single-threaded (as this test is). - // If one were to generalize these constructions to a - // multi-threaded context, then it might seem like we could choose - // between either an RwLock or a Mutex to hold the owned arcs on - // each node. - // - // Part of the point of this test is to actually confirm that the - // cycle exists by traversing it. We can do that just fine with an - // RwLock (since we can grab the child pointers in read-only - // mode), but we cannot lock a std::sync::Mutex to guard reading - // from each node via the same pattern, since once you hit the - // cycle, you'll be trying to acquiring the same lock twice. - // (We deal with this by exiting the traversal early if try_lock fails.) - - // Cycle 12: { arc0 -> (arc1, arc2), arc1 -> (), arc2 -> arc0 }, refcells - let (arc0, arc1, arc2): (ARCRC, ARCRC, ARCRC); - arc0 = ARCRC::new("arcrc0"); - arc1 = ARCRC::new("arcrc1"); - arc2 = ARCRC::new("arcrc2"); - arc0.0.borrow_mut().children.0 = Some(&arc1); - arc0.0.borrow_mut().children.1 = Some(&arc2); - arc2.0.borrow_mut().children.0 = Some(&arc0); - - let mut c = c_orig.clone(); - c.control_bits = 0b1; - c.curr_mark = 110; - assert!(!c.saw_prev_marked); - arc0.descend_into_self(&mut c); - assert!(c.saw_prev_marked); - - if PRINT { println!(); } - - // Cycle 13: { arc0 -> (arc1, arc2), arc1 -> (), arc2 -> arc0 }, rwlocks - let (arc0, arc1, arc2): (ARCRW, ARCRW, ARCRW); - arc0 = ARCRW::new("arcrw0"); - arc1 = ARCRW::new("arcrw1"); - arc2 = ARCRW::new("arcrw2"); - arc0.0.write().unwrap().children.0 = Some(&arc1); - arc0.0.write().unwrap().children.1 = Some(&arc2); - arc2.0.write().unwrap().children.0 = Some(&arc0); - - let mut c = c_orig.clone(); - c.control_bits = 0b1; - c.curr_mark = 110; - assert!(!c.saw_prev_marked); - arc0.descend_into_self(&mut c); - assert!(c.saw_prev_marked); - - if PRINT { println!(); } - - // Cycle 14: { arc0 -> (arc1, arc2), arc1 -> (), arc2 -> arc0 }, mutexs - let (arc0, arc1, arc2): (ARCM, ARCM, ARCM); - arc0 = ARCM::new("arcm0"); - arc1 = ARCM::new("arcm1"); - arc2 = ARCM::new("arcm2"); - arc0.1.lock().unwrap().children.0 = Some(&arc1); - arc0.1.lock().unwrap().children.1 = Some(&arc2); - arc2.1.lock().unwrap().children.0 = Some(&arc0); - - let mut c = c_orig.clone(); - c.control_bits = 0b1; - c.curr_mark = 110; - assert!(!c.saw_prev_marked); - arc0.descend_into_self(&mut c); - assert!(c.saw_prev_marked); -} - -trait Named { - fn new(_: &'static str) -> Self; - fn name(&self) -> &str; -} - -trait Marked { - fn mark(&self) -> M; - fn set_mark(&self, mark: M); -} - -struct S<'a> { - name: &'static str, - mark: Cell, - next: Cell>>, -} - -impl<'a> Named for S<'a> { - fn new(name: &'static str) -> S<'a> { - S { name: name, mark: Cell::new(0), next: Cell::new(None) } - } - fn name(&self) -> &str { self.name } -} - -impl<'a> Marked for S<'a> { - fn mark(&self) -> u32 { self.mark.get() } - fn set_mark(&self, mark: u32) { self.mark.set(mark); } -} - -struct S2<'a> { - name: &'static str, - mark: Cell, - next: Cell<(Option<&'a S2<'a>>, Option<&'a S2<'a>>)>, -} - -impl<'a> Named for S2<'a> { - fn new(name: &'static str) -> S2<'a> { - S2 { name: name, mark: Cell::new(0), next: Cell::new((None, None)) } - } - fn name(&self) -> &str { self.name } -} - -impl<'a> Marked for S2<'a> { - fn mark(&self) -> u32 { self.mark.get() } - fn set_mark(&self, mark: u32) { - self.mark.set(mark); - } -} - -struct V<'a> { - name: &'static str, - mark: Cell, - contents: Vec>>>, -} - -impl<'a> Named for V<'a> { - fn new(name: &'static str) -> V<'a> { - V { name: name, - mark: Cell::new(0), - contents: vec![Cell::new(None), Cell::new(None)] - } - } - fn name(&self) -> &str { self.name } -} - -impl<'a> Marked for V<'a> { - fn mark(&self) -> u32 { self.mark.get() } - fn set_mark(&self, mark: u32) { self.mark.set(mark); } -} - -#[derive(Eq)] -struct H<'a> { - name: &'static str, - mark: Cell, - next: Cell>>, -} - -impl<'a> Named for H<'a> { - fn new(name: &'static str) -> H<'a> { - H { name: name, mark: Cell::new(0), next: Cell::new(None) } - } - fn name(&self) -> &str { self.name } -} - -impl<'a> Marked for H<'a> { - fn mark(&self) -> u32 { self.mark.get() } - fn set_mark(&self, mark: u32) { self.mark.set(mark); } -} - -impl<'a> PartialEq for H<'a> { - fn eq(&self, rhs: &H<'a>) -> bool { - self.name == rhs.name - } -} - -impl<'a> Hash for H<'a> { - fn hash(&self, state: &mut H) { - self.name.hash(state) - } -} - -#[derive(Eq)] -struct HM<'a> { - name: &'static str, - mark: Cell, - contents: Cell, HM<'a>>>>, -} - -impl<'a> Named for HM<'a> { - fn new(name: &'static str) -> HM<'a> { - HM { name: name, - mark: Cell::new(0), - contents: Cell::new(None) - } - } - fn name(&self) -> &str { self.name } -} - -impl<'a> Marked for HM<'a> { - fn mark(&self) -> u32 { self.mark.get() } - fn set_mark(&self, mark: u32) { self.mark.set(mark); } -} - -impl<'a> PartialEq for HM<'a> { - fn eq(&self, rhs: &HM<'a>) -> bool { - self.name == rhs.name - } -} - -impl<'a> Hash for HM<'a> { - fn hash(&self, state: &mut H) { - self.name.hash(state) - } -} - - -struct VD<'a> { - name: &'static str, - mark: Cell, - contents: Cell>>>, -} - -impl<'a> Named for VD<'a> { - fn new(name: &'static str) -> VD<'a> { - VD { name: name, - mark: Cell::new(0), - contents: Cell::new(None) - } - } - fn name(&self) -> &str { self.name } -} - -impl<'a> Marked for VD<'a> { - fn mark(&self) -> u32 { self.mark.get() } - fn set_mark(&self, mark: u32) { self.mark.set(mark); } -} - -struct VM<'a> { - name: &'static str, - mark: Cell, - contents: Cell>>>, -} - -impl<'a> Named for VM<'a> { - fn new(name: &'static str) -> VM<'a> { - VM { name: name, - mark: Cell::new(0), - contents: Cell::new(None) - } - } - fn name(&self) -> &str { self.name } -} - -impl<'a> Marked for VM<'a> { - fn mark(&self) -> u32 { self.mark.get() } - fn set_mark(&self, mark: u32) { self.mark.set(mark); } -} - -struct LL<'a> { - name: &'static str, - mark: Cell, - contents: Cell>>>, -} - -impl<'a> Named for LL<'a> { - fn new(name: &'static str) -> LL<'a> { - LL { name: name, - mark: Cell::new(0), - contents: Cell::new(None) - } - } - fn name(&self) -> &str { self.name } -} - -impl<'a> Marked for LL<'a> { - fn mark(&self) -> u32 { self.mark.get() } - fn set_mark(&self, mark: u32) { self.mark.set(mark); } -} - -struct BH<'a> { - name: &'static str, - mark: Cell, - contents: Cell>>>, -} - -impl<'a> Named for BH<'a> { - fn new(name: &'static str) -> BH<'a> { - BH { name: name, - mark: Cell::new(0), - contents: Cell::new(None) - } - } - fn name(&self) -> &str { self.name } -} - -impl<'a> Marked for BH<'a> { - fn mark(&self) -> u32 { self.mark.get() } - fn set_mark(&self, mark: u32) { self.mark.set(mark); } -} - -impl<'a> Eq for BH<'a> { } - -impl<'a> PartialEq for BH<'a> { - fn eq(&self, rhs: &BH<'a>) -> bool { - self.name == rhs.name - } -} - -impl<'a> PartialOrd for BH<'a> { - fn partial_cmp(&self, rhs: &BH<'a>) -> Option { - Some(self.cmp(rhs)) - } -} - -impl<'a> Ord for BH<'a> { - fn cmp(&self, rhs: &BH<'a>) -> Ordering { - self.name.cmp(rhs.name) - } -} - -struct BTM<'a> { - name: &'static str, - mark: Cell, - contents: Cell, BTM<'a>>>>, -} - -impl<'a> Named for BTM<'a> { - fn new(name: &'static str) -> BTM<'a> { - BTM { name: name, - mark: Cell::new(0), - contents: Cell::new(None) - } - } - fn name(&self) -> &str { self.name } -} - -impl<'a> Marked for BTM<'a> { - fn mark(&self) -> u32 { self.mark.get() } - fn set_mark(&self, mark: u32) { self.mark.set(mark); } -} - -impl<'a> Eq for BTM<'a> { } - -impl<'a> PartialEq for BTM<'a> { - fn eq(&self, rhs: &BTM<'a>) -> bool { - self.name == rhs.name - } -} - -impl<'a> PartialOrd for BTM<'a> { - fn partial_cmp(&self, rhs: &BTM<'a>) -> Option { - Some(self.cmp(rhs)) - } -} - -impl<'a> Ord for BTM<'a> { - fn cmp(&self, rhs: &BTM<'a>) -> Ordering { - self.name.cmp(rhs.name) - } -} - -struct BTS<'a> { - name: &'static str, - mark: Cell, - contents: Cell>>>, -} - -impl<'a> Named for BTS<'a> { - fn new(name: &'static str) -> BTS<'a> { - BTS { name: name, - mark: Cell::new(0), - contents: Cell::new(None) - } - } - fn name(&self) -> &str { self.name } -} - -impl<'a> Marked for BTS<'a> { - fn mark(&self) -> u32 { self.mark.get() } - fn set_mark(&self, mark: u32) { self.mark.set(mark); } -} - -impl<'a> Eq for BTS<'a> { } - -impl<'a> PartialEq for BTS<'a> { - fn eq(&self, rhs: &BTS<'a>) -> bool { - self.name == rhs.name - } -} - -impl<'a> PartialOrd for BTS<'a> { - fn partial_cmp(&self, rhs: &BTS<'a>) -> Option { - Some(self.cmp(rhs)) - } -} - -impl<'a> Ord for BTS<'a> { - fn cmp(&self, rhs: &BTS<'a>) -> Ordering { - self.name.cmp(rhs.name) - } -} - -#[derive(Clone)] -struct RCRCData<'a> { - name: &'static str, - mark: Cell, - children: (Option<&'a RCRC<'a>>, Option<&'a RCRC<'a>>), -} -#[derive(Clone)] -struct RCRC<'a>(Rc>>); - -impl<'a> Named for RCRC<'a> { - fn new(name: &'static str) -> Self { - RCRC(Rc::new(RefCell::new(RCRCData { - name: name, mark: Cell::new(0), children: (None, None), }))) - } - fn name(&self) -> &str { self.0.borrow().name } -} - -impl<'a> Marked for RCRC<'a> { - fn mark(&self) -> u32 { self.0.borrow().mark.get() } - fn set_mark(&self, mark: u32) { self.0.borrow().mark.set(mark); } -} - -impl<'a> Children<'a> for RCRC<'a> { - fn count_children(&self) -> usize { 2 } - fn descend_one_child(&self, context: &mut C, index: usize) - where C: Context + PrePost, Self: Sized - { - let children = &self.0.borrow().children; - let child = match index { - 0 => if let Some(child) = children.0 { child } else { return; }, - 1 => if let Some(child) = children.1 { child } else { return; }, - _ => panic!("bad children"), - }; - // println!("S2 {} descending into child {} at index {}", self.name, child.name, index); - child.descend_into_self(context); - } -} -#[derive(Clone)] -struct ARCRCData<'a> { - name: &'static str, - mark: Cell, - children: (Option<&'a ARCRC<'a>>, Option<&'a ARCRC<'a>>), -} -#[derive(Clone)] -struct ARCRC<'a>(Arc>>); - -impl<'a> Named for ARCRC<'a> { - fn new(name: &'static str) -> Self { - ARCRC(Arc::new(RefCell::new(ARCRCData { - name: name, mark: Cell::new(0), children: (None, None), }))) - } - fn name(&self) -> &str { self.0.borrow().name } -} - -impl<'a> Marked for ARCRC<'a> { - fn mark(&self) -> u32 { self.0.borrow().mark.get() } - fn set_mark(&self, mark: u32) { self.0.borrow().mark.set(mark); } -} - -impl<'a> Children<'a> for ARCRC<'a> { - fn count_children(&self) -> usize { 2 } - fn descend_one_child(&self, context: &mut C, index: usize) - where C: Context + PrePost, Self: Sized - { - let children = &self.0.borrow().children; - match index { - 0 => if let Some(ref child) = children.0 { - child.descend_into_self(context); - }, - 1 => if let Some(ref child) = children.1 { - child.descend_into_self(context); - }, - _ => panic!("bad children!"), - } - } -} - -#[derive(Clone)] -struct ARCMData<'a> { - mark: Cell, - children: (Option<&'a ARCM<'a>>, Option<&'a ARCM<'a>>), -} - -#[derive(Clone)] -struct ARCM<'a>(&'static str, Arc>>); - -impl<'a> Named for ARCM<'a> { - fn new(name: &'static str) -> Self { - ARCM(name, Arc::new(Mutex::new(ARCMData { - mark: Cell::new(0), children: (None, None), }))) - } - fn name(&self) -> &str { self.0 } -} - -impl<'a> Marked for ARCM<'a> { - fn mark(&self) -> u32 { self.1.lock().unwrap().mark.get() } - fn set_mark(&self, mark: u32) { self.1.lock().unwrap().mark.set(mark); } -} - -impl<'a> Children<'a> for ARCM<'a> { - fn count_children(&self) -> usize { 2 } - fn descend_one_child(&self, context: &mut C, index: usize) - where C: Context + PrePost, Self: Sized - { - let ref children = if let Ok(data) = self.1.try_lock() { - data.children - } else { return; }; - match index { - 0 => if let Some(ref child) = children.0 { - child.descend_into_self(context); - }, - 1 => if let Some(ref child) = children.1 { - child.descend_into_self(context); - }, - _ => panic!("bad children!"), - } - } -} - -#[derive(Clone)] -struct ARCRWData<'a> { - name: &'static str, - mark: Cell, - children: (Option<&'a ARCRW<'a>>, Option<&'a ARCRW<'a>>), -} - -#[derive(Clone)] -struct ARCRW<'a>(Arc>>); - -impl<'a> Named for ARCRW<'a> { - fn new(name: &'static str) -> Self { - ARCRW(Arc::new(RwLock::new(ARCRWData { - name: name, mark: Cell::new(0), children: (None, None), }))) - } - fn name(&self) -> &str { self.0.read().unwrap().name } -} - -impl<'a> Marked for ARCRW<'a> { - fn mark(&self) -> u32 { self.0.read().unwrap().mark.get() } - fn set_mark(&self, mark: u32) { self.0.read().unwrap().mark.set(mark); } -} - -impl<'a> Children<'a> for ARCRW<'a> { - fn count_children(&self) -> usize { 2 } - fn descend_one_child(&self, context: &mut C, index: usize) - where C: Context + PrePost, Self: Sized - { - let children = &self.0.read().unwrap().children; - match index { - 0 => if let Some(ref child) = children.0 { - child.descend_into_self(context); - }, - 1 => if let Some(ref child) = children.1 { - child.descend_into_self(context); - }, - _ => panic!("bad children!"), - } - } -} - -trait Context { - fn next_index(&mut self, len: usize) -> usize; - fn should_act(&self) -> bool; - fn increase_visited(&mut self); - fn increase_skipped(&mut self); - fn increase_depth(&mut self); - fn decrease_depth(&mut self); -} - -trait PrePost { - fn pre(&mut self, _: &T); - fn post(&mut self, _: &T); - fn hit_limit(&mut self, _: &T); -} - -trait Children<'a> { - fn count_children(&self) -> usize; - fn descend_one_child(&self, context: &mut C, index: usize) - where C: Context + PrePost, Self: Sized; - - fn next_child(&self, context: &mut C) - where C: Context + PrePost, Self: Sized - { - let index = context.next_index(self.count_children()); - self.descend_one_child(context, index); - } - - fn descend_into_self(&self, context: &mut C) - where C: Context + PrePost, Self: Sized - { - context.pre(self); - if context.should_act() { - context.increase_visited(); - context.increase_depth(); - self.next_child(context); - context.decrease_depth(); - } else { - context.hit_limit(self); - context.increase_skipped(); - } - context.post(self); - } - - fn descend<'b, C>(&self, c: &Cell>, context: &mut C) - where C: Context + PrePost, Self: Sized - { - if let Some(r) = c.get() { - r.descend_into_self(context); - } - } -} - -impl<'a> Children<'a> for S<'a> { - fn count_children(&self) -> usize { 1 } - fn descend_one_child(&self, context: &mut C, _: usize) - where C: Context + PrePost, Self: Sized { - self.descend(&self.next, context); - } -} - -impl<'a> Children<'a> for S2<'a> { - fn count_children(&self) -> usize { 2 } - fn descend_one_child(&self, context: &mut C, index: usize) - where C: Context + PrePost, Self: Sized - { - let children = self.next.get(); - let child = match index { - 0 => if let Some(child) = children.0 { child } else { return; }, - 1 => if let Some(child) = children.1 { child } else { return; }, - _ => panic!("bad children"), - }; - // println!("S2 {} descending into child {} at index {}", self.name, child.name, index); - child.descend_into_self(context); - } -} - -impl<'a> Children<'a> for V<'a> { - fn count_children(&self) -> usize { self.contents.len() } - fn descend_one_child(&self, context: &mut C, index: usize) - where C: Context + PrePost, Self: Sized - { - if let Some(child) = self.contents[index].get() { - child.descend_into_self(context); - } - } -} - -impl<'a> Children<'a> for H<'a> { - fn count_children(&self) -> usize { 1 } - fn descend_one_child(&self, context: &mut C, _: usize) - where C: Context + PrePost, Self: Sized - { - self.descend(&self.next, context); - } -} - -impl<'a> Children<'a> for HM<'a> { - fn count_children(&self) -> usize { - if let Some(m) = self.contents.get() { 2 * m.iter().count() } else { 0 } - } - fn descend_one_child(&self, context: &mut C, index: usize) - where C: Context + PrePost, Self: Sized - { - if let Some(ref hm) = self.contents.get() { - if let Some((k, v)) = hm.iter().nth(index / 2) { - [k, v][index % 2].descend_into_self(context); - } - } - } -} - -impl<'a> Children<'a> for VD<'a> { - fn count_children(&self) -> usize { - if let Some(d) = self.contents.get() { d.iter().count() } else { 0 } - } - fn descend_one_child(&self, context: &mut C, index: usize) - where C: Context + PrePost, Self: Sized - { - if let Some(ref vd) = self.contents.get() { - if let Some(r) = vd.iter().nth(index) { - r.descend_into_self(context); - } - } - } -} - -impl<'a> Children<'a> for VM<'a> { - fn count_children(&self) -> usize { - if let Some(m) = self.contents.get() { m.iter().count() } else { 0 } - } - fn descend_one_child(&self, context: &mut C, index: usize) - where C: Context + PrePost> - { - if let Some(ref vd) = self.contents.get() { - if let Some((_idx, r)) = vd.iter().nth(index) { - r.descend_into_self(context); - } - } - } -} - -impl<'a> Children<'a> for LL<'a> { - fn count_children(&self) -> usize { - if let Some(l) = self.contents.get() { l.iter().count() } else { 0 } - } - fn descend_one_child(&self, context: &mut C, index: usize) - where C: Context + PrePost> - { - if let Some(ref ll) = self.contents.get() { - if let Some(r) = ll.iter().nth(index) { - r.descend_into_self(context); - } - } - } -} - -impl<'a> Children<'a> for BH<'a> { - fn count_children(&self) -> usize { - if let Some(h) = self.contents.get() { h.iter().count() } else { 0 } - } - fn descend_one_child(&self, context: &mut C, index: usize) - where C: Context + PrePost> - { - if let Some(ref bh) = self.contents.get() { - if let Some(r) = bh.iter().nth(index) { - r.descend_into_self(context); - } - } - } -} - -impl<'a> Children<'a> for BTM<'a> { - fn count_children(&self) -> usize { - if let Some(m) = self.contents.get() { 2 * m.iter().count() } else { 0 } - } - fn descend_one_child(&self, context: &mut C, index: usize) - where C: Context + PrePost> - { - if let Some(ref bh) = self.contents.get() { - if let Some((k, v)) = bh.iter().nth(index / 2) { - [k, v][index % 2].descend_into_self(context); - } - } - } -} - -impl<'a> Children<'a> for BTS<'a> { - fn count_children(&self) -> usize { - if let Some(s) = self.contents.get() { s.iter().count() } else { 0 } - } - fn descend_one_child(&self, context: &mut C, index: usize) - where C: Context + PrePost> - { - if let Some(ref bh) = self.contents.get() { - if let Some(r) = bh.iter().nth(index) { - r.descend_into_self(context); - } - } - } -} - -#[derive(Copy, Clone)] -struct ContextData { - curr_depth: usize, - max_depth: usize, - visited: usize, - max_visits: usize, - skipped: usize, - curr_mark: u32, - saw_prev_marked: bool, - control_bits: u64, -} - -impl Context for ContextData { - fn next_index(&mut self, len: usize) -> usize { - if len < 2 { return 0; } - let mut pow2 = len.next_power_of_two(); - let _pow2_orig = pow2; - let mut idx = 0; - let mut bits = self.control_bits; - while pow2 > 1 { - idx = (idx << 1) | (bits & 1) as usize; - bits = bits >> 1; - pow2 = pow2 >> 1; - } - idx = idx % len; - // println!("next_index({} [{:b}]) says {}, pre(bits): {:b} post(bits): {:b}", - // len, _pow2_orig, idx, self.control_bits, bits); - self.control_bits = bits; - return idx; - } - fn should_act(&self) -> bool { - self.curr_depth < self.max_depth && self.visited < self.max_visits - } - fn increase_visited(&mut self) { self.visited += 1; } - fn increase_skipped(&mut self) { self.skipped += 1; } - fn increase_depth(&mut self) { self.curr_depth += 1; } - fn decrease_depth(&mut self) { self.curr_depth -= 1; } -} - -impl> PrePost for ContextData { - fn pre(&mut self, t: &T) { - for _ in 0..self.curr_depth { - if PRINT { print!(" "); } - } - if PRINT { println!("prev {}", t.name()); } - if t.mark() == self.curr_mark { - for _ in 0..self.curr_depth { - if PRINT { print!(" "); } - } - if PRINT { println!("(probably previously marked)"); } - self.saw_prev_marked = true; - } - t.set_mark(self.curr_mark); - } - fn post(&mut self, t: &T) { - for _ in 0..self.curr_depth { - if PRINT { print!(" "); } - } - if PRINT { println!("post {}", t.name()); } - } - fn hit_limit(&mut self, t: &T) { - for _ in 0..self.curr_depth { - if PRINT { print!(" "); } - } - if PRINT { println!("LIMIT {}", t.name()); } - } -} -- cgit v1.2.3