deep_safe_drop 0.1.0

Safe dropping of deep trees that otherwise could cause stack overflow.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

use super::*;


pub(super) struct BinaryTree<L>
{
    pub(super) left:  Option<L>,
    pub(super) right: Option<L>,
}

impl<L> BinaryTree<L>
{
    fn make_fan(depth: usize) -> Self
    where L: NewLink<Self>
    {
        let mut fan = Self { left: None, right: None };

        if depth > 0 {
            fan.left = Some(L::new(Self::make_fan(depth.saturating_sub(1))));
            fan.right = Some(L::new(Self::make_fan(depth.saturating_sub(1))));
        }

        fan
    }
}

impl<L> DeepSafeDrop<L> for BinaryTree<L>
{
    fn take_child_at_index_0(&mut self) -> Option<L>
    {
        self.left.take()
    }

    fn set_parent_at_index_0(
        &mut self,
        parent: L,
    ) -> SetParent<L>
    {
        if let Some(child) = self.left.take() {
            self.left = Some(parent);
            SetParent::YesReplacedChild { child0: child }
        }
        else {
            SetParent::No { returned_parent: parent }
        }
    }

    fn take_next_child_at_pos_index(&mut self) -> Option<L>
    {
        self.right.take()
    }
}


#[test]
fn exercise()
{
    use core::convert::TryInto;

    struct BinaryTreeBox(Box<BinaryTree<Self>>);

    impl NewLink<BinaryTree<Self>> for BinaryTreeBox
    {
        fn new(tree: BinaryTree<Self>) -> Self
        {
            Self(Box::new(tree))
        }
    }

    impl Link<BinaryTree<Self>> for BinaryTreeBox
    {
        fn get_mut(&mut self) -> &mut BinaryTree<Self>
        {
            &mut self.0
        }
    }

    impl Drop for BinaryTreeBox
    {
        fn drop(&mut self)
        {
            deep_safe_drop::<_, Self, BinaryTree<Self>>(&mut *self.0);
        }
    }

    fn fan_depth(size: usize) -> usize
    {
        fn log2(x: usize) -> u32
        {
            (usize::BITS - 1) - x.leading_zeros()
        }
        assert!(0 < size && size < usize::MAX);
        #[allow(clippy::expect_used)]
        (log2(size + 1) - 1).try_into().expect("impossible")
    }

    let fan = BinaryTree::<BinaryTreeBox>::make_fan(fan_depth(TREE_SIZE));
    drop(fan);
}