alice_sdf/types/
drop.rs

1//! Iterative `Drop` for [`SdfNode`]
2//!
3//! `SdfNode` は子を `Arc<Self>` で持つ再帰 enum なので、default の drop は
4//! 子 → 孫 → … と再帰し、深さに比例して native stack を消費する
5//! LOL stdlib の product tree は `subtract` を 2,400 段 nest する (正当な
6//! 形) ため、2 MB stack の thread では drop だけで overflow していた
7//!
8//! ここでは子を heap 上の明示 stack に移してから解放する 再帰は一切ない
9//!
10//! 共有 subtree (`Arc::clone` で複数の親から参照される node) は
11//! `Arc::try_unwrap` が `Err` を返すのでそのまま手放す 最後の所有者が
12//! drop する時に同じ routine が走るので、深さに依らず stack 消費は O(1)
13//!
14//! Author: Moroya Sakamoto
15
16use super::SdfNode;
17use std::sync::{Arc, OnceLock};
18
19/// 子 field を抜き取った跡に置く leaf `Arc` は refcount の増減だけで
20/// allocation を伴わないので、drop の総 cost は node 数に線形
21fn leaf_sentinel() -> Arc<SdfNode> {
22    static LEAF: OnceLock<Arc<SdfNode>> = OnceLock::new();
23    Arc::clone(LEAF.get_or_init(|| Arc::new(SdfNode::Sphere { radius: 0.0 })))
24}
25
26impl SdfNode {
27    /// 子 `Arc` を全て `out` に移し、自身は leaf 相当の状態にする
28    ///
29    /// 子を持たない variant では何もしない 子を持つ variant を追加した時は
30    /// ここにも arm を足す (`tests` の `take_children_covers_every_family`
31    /// が代表 variant で検知する)
32    pub(crate) fn take_children_into(&mut self, out: &mut Vec<Arc<Self>>) {
33        match self {
34            // 二項 operation (24)
35            Self::Union { a, b, .. }
36            | Self::Intersection { a, b, .. }
37            | Self::Subtraction { a, b, .. }
38            | Self::SmoothUnion { a, b, .. }
39            | Self::SmoothIntersection { a, b, .. }
40            | Self::SmoothSubtraction { a, b, .. }
41            | Self::ChamferUnion { a, b, .. }
42            | Self::ChamferIntersection { a, b, .. }
43            | Self::ChamferSubtraction { a, b, .. }
44            | Self::StairsUnion { a, b, .. }
45            | Self::StairsIntersection { a, b, .. }
46            | Self::StairsSubtraction { a, b, .. }
47            | Self::ColumnsUnion { a, b, .. }
48            | Self::ColumnsIntersection { a, b, .. }
49            | Self::ColumnsSubtraction { a, b, .. }
50            | Self::ExpSmoothUnion { a, b, .. }
51            | Self::ExpSmoothIntersection { a, b, .. }
52            | Self::ExpSmoothSubtraction { a, b, .. }
53            | Self::XOR { a, b, .. }
54            | Self::Pipe { a, b, .. }
55            | Self::Engrave { a, b, .. }
56            | Self::Groove { a, b, .. }
57            | Self::Tongue { a, b, .. }
58            | Self::Morph { a, b, .. } => {
59                out.push(std::mem::replace(a, leaf_sentinel()));
60                out.push(std::mem::replace(b, leaf_sentinel()));
61            }
62
63            // 単項 transform (7) + modifier (23) + Animated
64            Self::Translate { child, .. }
65            | Self::Rotate { child, .. }
66            | Self::Scale { child, .. }
67            | Self::ScaleNonUniform { child, .. }
68            | Self::Shear { child, .. }
69            | Self::ProjectiveTransform { child, .. }
70            | Self::SdfSkinning { child, .. }
71            | Self::Round { child, .. }
72            | Self::Onion { child, .. }
73            | Self::Elongate { child, .. }
74            | Self::Twist { child, .. }
75            | Self::Bend { child, .. }
76            | Self::Taper { child, .. }
77            | Self::Mirror { child, .. }
78            | Self::OctantMirror { child, .. }
79            | Self::IcosahedralSymmetry { child, .. }
80            | Self::RepeatInfinite { child, .. }
81            | Self::RepeatFinite { child, .. }
82            | Self::PolarRepeat { child, .. }
83            | Self::Displacement { child, .. }
84            | Self::SineDisplacement { child, .. }
85            | Self::HeightmapDisplacement { child, .. }
86            | Self::Noise { child, .. }
87            | Self::SurfaceRoughness { child, .. }
88            | Self::Revolution { child, .. }
89            | Self::Extrude { child, .. }
90            | Self::SweepBezier { child, .. }
91            | Self::LatticeDeform { child, .. }
92            | Self::IFS { child, .. }
93            | Self::WithMaterial { child, .. }
94            | Self::Animated { child, .. } => {
95                out.push(std::mem::replace(child, leaf_sentinel()));
96            }
97
98            // 葉 (primitive 72 種) は子を持たない
99            _ => {}
100        }
101    }
102}
103
104impl Drop for SdfNode {
105    fn drop(&mut self) {
106        let mut stack: Vec<Arc<Self>> = Vec::new();
107        self.take_children_into(&mut stack);
108        if stack.is_empty() {
109            return;
110        }
111        while let Some(child) = stack.pop() {
112            // 唯一の所有者なら中身を取り出して、その子を先に stack へ退避する
113            // `node` はここで scope を抜けて drop されるが、子は既に空なので
114            // 再帰は 1 段で止まる 共有中 (`Err`) なら refcount -1 のみ
115            if let Ok(mut node) = Arc::try_unwrap(child) {
116                node.take_children_into(&mut stack);
117            }
118        }
119    }
120}
alice_sdf/types/drop.rs

alice_sdf/types/
drop.rs
