zenoh_keyexpr/keyexpr_tree/
arc_tree.rs

1//
2// Copyright (c) 2023 ZettaScale Technology
3//
4// This program and the accompanying materials are made available under the
5// terms of the Eclipse Public License 2.0 which is available at
6// http://www.eclipse.org/legal/epl-2.0, or the Apache License, Version 2.0
7// which is available at https://www.apache.org/licenses/LICENSE-2.0.
8//
9// SPDX-License-Identifier: EPL-2.0 OR Apache-2.0
10//
11// Contributors:
12//   ZettaScale Zenoh Team, <zenoh@zettascale.tech>
13//
14
15use alloc::{
16    string::String,
17    sync::{Arc, Weak},
18};
19use core::fmt::Debug;
20
21use token_cell::prelude::*;
22
23use super::{box_tree::PruneResult, support::IterOrOption};
24use crate::{
25    keyexpr,
26    keyexpr_tree::{support::IWildness, *},
27};
28
29pub struct KeArcTreeInner<
30    Weight,
31    Wildness: IWildness,
32    Children: IChildrenProvider<
33        Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
34    >,
35    Token: TokenTrait,
36> {
37    children: Children::Assoc,
38    wildness: Wildness,
39}
40
41impl<Weight, Wildness, Children, Token> core::fmt::Debug
42    for KeArcTreeInner<Weight, Wildness, Children, Token>
43where
44    Wildness: IWildness,
45    Children: IChildrenProvider<
46        Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
47    >,
48    Token: TokenTrait,
49{
50    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
51        f.debug_struct("KeArcTreeInner")
52            .field("children", &"..")
53            .field("is_wild", &self.wildness.get())
54            .finish()
55    }
56}
57
58token_cell::token!(pub DefaultToken);
59fn ketree_borrow<'a, T, Token: TokenTrait>(
60    cell: &'a TokenCell<T, Token>,
61    token: &'a Token,
62) -> &'a T {
63    cell.try_borrow(token)
64        .unwrap_or_else(|_| panic!("Attempted to use KeArcTree with the wrong Token"))
65}
66fn ketree_borrow_mut<'a, T, Token: TokenTrait>(
67    cell: &'a TokenCell<T, Token>,
68    token: &'a mut Token,
69) -> &'a mut T {
70    cell.try_borrow_mut(token)
71        .unwrap_or_else(|_| panic!("Attempted to mutably use KeArcTree with the wrong Token"))
72}
73
74/// A shared KeTree.
75///
76/// The tree and its nodes have shared ownership, while their mutability is managed through the `Token`.
77///
78/// Most of its methods are declared in the [`ITokenKeyExprTree`] trait.
79// tags{ketree.arc}
80pub struct KeArcTree<
81    Weight,
82    Token: TokenTrait = DefaultToken,
83    Wildness: IWildness = bool,
84    Children: IChildrenProvider<
85        Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
86    > = DefaultChildrenProvider,
87> {
88    inner: TokenCell<KeArcTreeInner<Weight, Wildness, Children, Token>, Token>,
89}
90
91impl<Weight, Token, Wildness, Children> core::fmt::Debug
92    for KeArcTree<Weight, Token, Wildness, Children>
93where
94    Token: TokenTrait,
95    Wildness: IWildness,
96    Children: IChildrenProvider<
97        Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
98    >,
99{
100    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
101        f.debug_tuple("KeArcTree").field(&"..").finish()
102    }
103}
104
105impl<
106        Weight,
107        Wildness: IWildness,
108        Children: IChildrenProvider<
109            Arc<
110                TokenCell<
111                    KeArcTreeNode<Weight, Weak<()>, Wildness, Children, DefaultToken>,
112                    DefaultToken,
113                >,
114            >,
115        >,
116    > KeArcTree<Weight, DefaultToken, Wildness, Children>
117{
118    /// Constructs the KeArcTree, returning it and its token, unless constructing the Token failed.
119    ///
120    /// # Type inference papercut
121    /// Despite some of `KeArcTree`'s generic parameters having default values, those are only taken into
122    /// account by the compiler when a type is named with some parameters omitted, and not when a type is
123    /// inferred with the same parameters unconstrained.
124    ///
125    /// The simplest way to resolve this is to eventually assign to tree part of the return value
126    /// to a variable or field whose type is named `KeArcTree<_>` (the `Weight` parameter can generally be inferred).
127    pub fn new() -> Result<(Self, DefaultToken), <DefaultToken as TokenTrait>::ConstructionError> {
128        let token = DefaultToken::new()?;
129        Ok((Self::with_token(&token), token))
130    }
131}
132
133impl<
134        Weight,
135        Wildness: IWildness,
136        Children: IChildrenProvider<
137            Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
138        >,
139        Token: TokenTrait,
140    > KeArcTree<Weight, Token, Wildness, Children>
141{
142    /// Constructs the KeArcTree with a specific token.
143    pub fn with_token(token: &Token) -> Self {
144        Self {
145            inner: TokenCell::new(
146                KeArcTreeInner {
147                    children: Default::default(),
148                    wildness: Wildness::non_wild(),
149                },
150                token,
151            ),
152        }
153    }
154}
155
156#[allow(clippy::type_complexity)]
157impl<
158        'a,
159        Weight: 'a,
160        Wildness: IWildness + 'a,
161        Children: IChildrenProvider<
162                Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
163            > + 'a,
164        Token: TokenTrait + 'a,
165    > ITokenKeyExprTree<'a, Weight, Token> for KeArcTree<Weight, Token, Wildness, Children>
166where
167    Children::Assoc: IChildren<
168        Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
169    >,
170{
171    type Node = (
172        &'a Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
173        &'a Token,
174    );
175    type NodeMut = (
176        &'a Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
177        &'a mut Token,
178    );
179    // tags{ketree.arc.node}
180    fn node(&'a self, token: &'a Token, at: &keyexpr) -> Option<Self::Node> {
181        let inner = ketree_borrow(&self.inner, token);
182        let mut chunks = at.chunks_impl();
183        let mut node = inner.children.child_at(chunks.next().unwrap())?;
184        for chunk in chunks {
185            let as_node: &Arc<
186                TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>,
187            > = node.as_node();
188            // SAFETY: upheld by the surrounding invariants and prior validation.
189            node = unsafe { (*as_node.get()).children.child_at(chunk)? };
190        }
191        Some((node.as_node(), token))
192    }
193    // tags{ketree.arc.node.mut}
194    fn node_mut(&'a self, token: &'a mut Token, at: &keyexpr) -> Option<Self::NodeMut> {
195        self.node(
196            // SAFETY: upheld by the surrounding invariants and prior validation.
197            unsafe { core::mem::transmute::<&Token, &Token>(&*token) },
198            at,
199        )
200        .map(|(node, _)| (node, token))
201    }
202    // tags{ketree.arc.node.or_create}
203    fn node_or_create(&'a self, token: &'a mut Token, at: &keyexpr) -> Self::NodeMut {
204        let inner = ketree_borrow_mut(&self.inner, token);
205        if at.is_wild_impl() {
206            inner.wildness.set(true);
207        }
208        let inner: &mut KeArcTreeInner<Weight, Wildness, Children, Token> =
209            // SAFETY: upheld by the surrounding invariants and prior validation.
210            unsafe { core::mem::transmute(inner) };
211        let construct_node = |k: &keyexpr, parent| {
212            Arc::new(TokenCell::new(
213                KeArcTreeNode {
214                    parent,
215                    chunk: k.into(),
216                    children: Default::default(),
217                    weight: None,
218                },
219                token,
220            ))
221        };
222        let mut chunks = at.chunks_impl();
223        let mut node = inner
224            .children
225            .entry(chunks.next().unwrap())
226            .get_or_insert_with(|k| construct_node(k, None));
227        for chunk in chunks {
228            let as_node: &Arc<
229                TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>,
230            > = node.as_node();
231            // SAFETY: upheld by the surrounding invariants and prior validation.
232            node = unsafe {
233                (*as_node.get())
234                    .children
235                    .entry(chunk)
236                    .get_or_insert_with(|k| construct_node(k, Some(Arc::downgrade(as_node))))
237            };
238        }
239        (node, token)
240    }
241
242    type TreeIterItem = Self::Node;
243    type TreeIter = TokenPacker<
244        TreeIter<
245            'a,
246            Children,
247            Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
248            Weight,
249        >,
250        &'a Token,
251    >;
252    // tags{ketree.arc.tree_iter}
253    fn tree_iter(&'a self, token: &'a Token) -> Self::TreeIter {
254        let inner = ketree_borrow(&self.inner, token);
255        TokenPacker {
256            iter: TreeIter::new(&inner.children),
257            token,
258        }
259    }
260
261    type TreeIterItemMut = Tokenized<
262        &'a Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
263        &'a mut Token,
264    >;
265    type TreeIterMut = TokenPacker<
266        TreeIter<
267            'a,
268            Children,
269            Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
270            Weight,
271        >,
272        &'a mut Token,
273    >;
274    // tags{ketree.arc.tree_iter.mut}
275    fn tree_iter_mut(&'a self, token: &'a mut Token) -> Self::TreeIterMut {
276        let inner = ketree_borrow(&self.inner, token);
277        TokenPacker {
278            // SAFETY: upheld by the surrounding invariants and prior validation.
279            iter: TreeIter::new(unsafe {
280                core::mem::transmute::<&Children::Assoc, &Children::Assoc>(&inner.children)
281            }),
282            token,
283        }
284    }
285
286    type IntersectionItem = Self::Node;
287    type Intersection = IterOrOption<
288        TokenPacker<
289            Intersection<
290                'a,
291                Children,
292                Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
293                Weight,
294            >,
295            &'a Token,
296        >,
297        Self::IntersectionItem,
298    >;
299    // tags{ketree.arc.intersecting}
300    fn intersecting_nodes(&'a self, token: &'a Token, key: &'a keyexpr) -> Self::Intersection {
301        let inner = ketree_borrow(&self.inner, token);
302        if inner.wildness.get() || key.is_wild_impl() {
303            IterOrOption::Iter(TokenPacker {
304                iter: Intersection::new(&inner.children, key),
305                token,
306            })
307        } else {
308            IterOrOption::Opt(self.node(token, key))
309        }
310    }
311    type IntersectionItemMut = Self::TreeIterItemMut;
312    type IntersectionMut = IterOrOption<
313        TokenPacker<
314            Intersection<
315                'a,
316                Children,
317                Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
318                Weight,
319            >,
320            &'a mut Token,
321        >,
322        Self::IntersectionItemMut,
323    >;
324    // tags{ketree.arc.intersecting.mut}
325    fn intersecting_nodes_mut(
326        &'a self,
327        token: &'a mut Token,
328        key: &'a keyexpr,
329    ) -> Self::IntersectionMut {
330        let inner = ketree_borrow(&self.inner, token);
331        if inner.wildness.get() || key.is_wild_impl() {
332            IterOrOption::Iter(TokenPacker {
333                iter: Intersection::new(
334                    // SAFETY: upheld by the surrounding invariants and prior validation.
335                    unsafe {
336                        core::mem::transmute::<&Children::Assoc, &Children::Assoc>(&inner.children)
337                    },
338                    key,
339                ),
340                token,
341            })
342        } else {
343            IterOrOption::Opt(self.node_mut(token, key).map(Into::into))
344        }
345    }
346
347    type InclusionItem = Self::Node;
348    type Inclusion = IterOrOption<
349        TokenPacker<
350            Inclusion<
351                'a,
352                Children,
353                Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
354                Weight,
355            >,
356            &'a Token,
357        >,
358        Self::InclusionItem,
359    >;
360    // tags{ketree.arc.included}
361    fn included_nodes(&'a self, token: &'a Token, key: &'a keyexpr) -> Self::Inclusion {
362        let inner = ketree_borrow(&self.inner, token);
363        if inner.wildness.get() || key.is_wild_impl() {
364            IterOrOption::Iter(TokenPacker {
365                iter: Inclusion::new(&inner.children, key),
366                token,
367            })
368        } else {
369            IterOrOption::Opt(self.node(token, key))
370        }
371    }
372    type InclusionItemMut = Self::TreeIterItemMut;
373    type InclusionMut = IterOrOption<
374        TokenPacker<
375            Inclusion<
376                'a,
377                Children,
378                Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
379                Weight,
380            >,
381            &'a mut Token,
382        >,
383        Self::InclusionItemMut,
384    >;
385    // tags{ketree.arc.included.mut}
386    fn included_nodes_mut(&'a self, token: &'a mut Token, key: &'a keyexpr) -> Self::InclusionMut {
387        let inner = ketree_borrow(&self.inner, token);
388        if inner.wildness.get() || key.is_wild_impl() {
389            // SAFETY: upheld by the surrounding invariants and prior validation.
390            unsafe {
391                IterOrOption::Iter(TokenPacker {
392                    iter: Inclusion::new(
393                        core::mem::transmute::<&Children::Assoc, &Children::Assoc>(&inner.children),
394                        key,
395                    ),
396                    token,
397                })
398            }
399        } else {
400            IterOrOption::Opt(self.node_mut(token, key).map(Into::into))
401        }
402    }
403
404    type IncluderItem = Self::Node;
405    type Includer = IterOrOption<
406        TokenPacker<
407            Includer<
408                'a,
409                Children,
410                Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
411                Weight,
412            >,
413            &'a Token,
414        >,
415        Self::IncluderItem,
416    >;
417    // tags{ketree.arc.including}
418    fn nodes_including(&'a self, token: &'a Token, key: &'a keyexpr) -> Self::Includer {
419        let inner = ketree_borrow(&self.inner, token);
420        if inner.wildness.get() || key.is_wild_impl() {
421            IterOrOption::Iter(TokenPacker {
422                iter: Includer::new(&inner.children, key),
423                token,
424            })
425        } else {
426            IterOrOption::Opt(self.node(token, key))
427        }
428    }
429    type IncluderItemMut = Self::TreeIterItemMut;
430    type IncluderMut = IterOrOption<
431        TokenPacker<
432            Includer<
433                'a,
434                Children,
435                Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
436                Weight,
437            >,
438            &'a mut Token,
439        >,
440        Self::IncluderItemMut,
441    >;
442    // tags{ketree.arc.including.mut}
443    fn nodes_including_mut(&'a self, token: &'a mut Token, key: &'a keyexpr) -> Self::IncluderMut {
444        let inner = ketree_borrow(&self.inner, token);
445        if inner.wildness.get() || key.is_wild_impl() {
446            // SAFETY: upheld by the surrounding invariants and prior validation.
447            unsafe {
448                IterOrOption::Iter(TokenPacker {
449                    iter: Includer::new(
450                        core::mem::transmute::<&Children::Assoc, &Children::Assoc>(&inner.children),
451                        key,
452                    ),
453                    token,
454                })
455            }
456        } else {
457            IterOrOption::Opt(self.node_mut(token, key).map(Into::into))
458        }
459    }
460    type PruneNode = KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>;
461
462    // tags{ketree.arc.prune.where}
463    fn prune_where<F: FnMut(&mut Self::PruneNode) -> bool>(
464        &self,
465        token: &mut Token,
466        mut predicate: F,
467    ) {
468        let mut wild = false;
469        let inner = ketree_borrow_mut(&self.inner, token);
470        inner.children.filter_out(
471            // SAFETY: upheld by the surrounding invariants and prior validation.
472            &mut |child| match unsafe { (*child.get()).prune(&mut predicate) } {
473                PruneResult::Delete => Arc::strong_count(child) <= 1,
474                PruneResult::NonWild => false,
475                PruneResult::Wild => {
476                    wild = true;
477                    false
478                }
479            },
480        );
481        inner.wildness.set(wild);
482    }
483}
484
485pub(crate) mod sealed {
486    use alloc::sync::Arc;
487    use core::ops::{Deref, DerefMut};
488
489    use token_cell::prelude::{TokenCell, TokenTrait};
490
491    pub struct Tokenized<A, B>(pub A, pub(crate) B);
492    impl<A, B> core::fmt::Debug for Tokenized<A, B> {
493        fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
494            f.debug_tuple("Tokenized").field(&"..").finish()
495        }
496    }
497    impl<T, Token: TokenTrait> Deref for Tokenized<&TokenCell<T, Token>, &Token> {
498        type Target = T;
499        fn deref(&self) -> &Self::Target {
500            // SAFETY: upheld by the surrounding invariants and prior validation.
501            unsafe { &*self.0.get() }
502        }
503    }
504    impl<T, Token: TokenTrait> Deref for Tokenized<&TokenCell<T, Token>, &mut Token> {
505        type Target = T;
506        fn deref(&self) -> &Self::Target {
507            // SAFETY: upheld by the surrounding invariants and prior validation.
508            unsafe { &*self.0.get() }
509        }
510    }
511    impl<T, Token: TokenTrait> DerefMut for Tokenized<&TokenCell<T, Token>, &mut Token> {
512        fn deref_mut(&mut self) -> &mut Self::Target {
513            // SAFETY: upheld by the surrounding invariants and prior validation.
514            unsafe { &mut *self.0.get() }
515        }
516    }
517    impl<T, Token: TokenTrait> Deref for Tokenized<&Arc<TokenCell<T, Token>>, &Token> {
518        type Target = T;
519        fn deref(&self) -> &Self::Target {
520            // SAFETY: upheld by the surrounding invariants and prior validation.
521            unsafe { &*self.0.get() }
522        }
523    }
524    impl<T, Token: TokenTrait> Deref for Tokenized<&Arc<TokenCell<T, Token>>, &mut Token> {
525        type Target = T;
526        fn deref(&self) -> &Self::Target {
527            // SAFETY: upheld by the surrounding invariants and prior validation.
528            unsafe { &*self.0.get() }
529        }
530    }
531    impl<T, Token: TokenTrait> DerefMut for Tokenized<&Arc<TokenCell<T, Token>>, &mut Token> {
532        fn deref_mut(&mut self) -> &mut Self::Target {
533            // SAFETY: upheld by the surrounding invariants and prior validation.
534            unsafe { &mut *self.0.get() }
535        }
536    }
537    impl<A, B> From<(A, B)> for Tokenized<A, B> {
538        fn from((a, b): (A, B)) -> Self {
539            Self(a, b)
540        }
541    }
542    pub struct TokenPacker<I, T> {
543        pub(crate) iter: I,
544        pub(crate) token: T,
545    }
546
547    impl<I, T> core::fmt::Debug for TokenPacker<I, T> {
548        fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
549            f.debug_struct("TokenPacker").finish_non_exhaustive()
550        }
551    }
552
553    impl<'a, I: Iterator, T> Iterator for TokenPacker<I, &'a T> {
554        type Item = (I::Item, &'a T);
555        fn next(&mut self) -> Option<Self::Item> {
556            self.iter.next().map(|i| (i, self.token))
557        }
558    }
559
560    impl<'a, I: Iterator, T> Iterator for TokenPacker<I, &'a mut T> {
561        type Item = Tokenized<I::Item, &'a mut T>;
562        fn next(&mut self) -> Option<Self::Item> {
563            self.iter.next().map(|i| {
564                // SAFETY: upheld by the surrounding invariants and prior validation.
565                Tokenized(i, unsafe {
566                    // SAFETY: while this makes it possible for multiple mutable references to the Token to exist,
567                    // it prevents them from being extracted and thus used to create multiple mutable references to
568                    // a same memory address.
569                    core::mem::transmute_copy(&self.token)
570                })
571            })
572        }
573    }
574}
575pub use sealed::{TokenPacker, Tokenized};
576
577pub trait IArcProvider {
578    type Ptr<T>: IArc<T>;
579}
580pub trait IArc<T> {
581    fn weak(&self) -> Weak<T>;
582    type UpgradeErr: Debug;
583    fn upgrade(&self) -> Result<Arc<T>, Self::UpgradeErr>;
584}
585impl IArcProvider for Arc<()> {
586    type Ptr<T> = Arc<T>;
587}
588impl IArcProvider for Weak<()> {
589    type Ptr<T> = Weak<T>;
590}
591impl<T> IArc<T> for Arc<T> {
592    fn weak(&self) -> Weak<T> {
593        Arc::downgrade(self)
594    }
595    type UpgradeErr = core::convert::Infallible;
596    fn upgrade(&self) -> Result<Arc<T>, core::convert::Infallible> {
597        Ok(self.clone())
598    }
599}
600#[derive(Debug, Clone, Copy)]
601pub struct WeakConvertError;
602impl<T> IArc<T> for Weak<T> {
603    fn weak(&self) -> Weak<T> {
604        self.clone()
605    }
606    type UpgradeErr = WeakConvertError;
607    fn upgrade(&self) -> Result<Arc<T>, WeakConvertError> {
608        Weak::upgrade(self).ok_or(WeakConvertError)
609    }
610}
611
612#[allow(clippy::type_complexity)]
613pub struct KeArcTreeNode<
614    Weight,
615    Parent: IArcProvider,
616    Wildness: IWildness,
617    Children: IChildrenProvider<
618        Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
619    >,
620    Token: TokenTrait,
621> {
622    parent: Option<
623        Parent::Ptr<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
624    >,
625    chunk: OwnedKeyExpr,
626    children: Children::Assoc,
627    weight: Option<Weight>,
628}
629
630impl<Weight, Parent, Wildness, Children, Token> core::fmt::Debug
631    for KeArcTreeNode<Weight, Parent, Wildness, Children, Token>
632where
633    Weight: Debug,
634    Parent: IArcProvider,
635    Wildness: IWildness,
636    Children: IChildrenProvider<
637        Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
638    >,
639    Token: TokenTrait,
640{
641    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
642        f.debug_struct("KeArcTreeNode")
643            .field("has_parent", &self.parent.is_some())
644            .field("chunk", &self.chunk)
645            .field("children", &"..")
646            .field("weight", &self.weight)
647            .finish()
648    }
649}
650
651impl<
652        Weight,
653        Wildness: IWildness,
654        Children: IChildrenProvider<
655            Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
656        >,
657        Token: TokenTrait,
658    > KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>
659where
660    Children::Assoc: IChildren<
661        Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
662    >,
663{
664    fn prune<F: FnMut(&mut Self) -> bool>(&mut self, predicate: &mut F) -> PruneResult {
665        let mut result = PruneResult::NonWild;
666        self.children.filter_out(&mut |child| {
667            // SAFETY: upheld by the surrounding invariants and prior validation.
668            let c = unsafe { &mut *child.get() };
669            match c.prune(predicate) {
670                PruneResult::Delete => Arc::strong_count(child) <= 1,
671                PruneResult::NonWild => false,
672                PruneResult::Wild => {
673                    result = PruneResult::Wild;
674                    false
675                }
676            }
677        });
678        if predicate(self) && self.children.is_empty() {
679            result = PruneResult::Delete
680        } else if self.chunk.is_wild_impl() {
681            result = PruneResult::Wild
682        }
683        result
684    }
685}
686
687impl<
688        Weight,
689        Parent: IArcProvider,
690        Wildness: IWildness,
691        Children: IChildrenProvider<
692            Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
693        >,
694        Token: TokenTrait,
695    > UIKeyExprTreeNode<Weight>
696    for Arc<TokenCell<KeArcTreeNode<Weight, Parent, Wildness, Children, Token>, Token>>
697where
698    Children::Assoc: IChildren<
699        Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
700    >,
701{
702    type Parent = <KeArcTreeNode<Weight, Parent, Wildness, Children, Token> as UIKeyExprTreeNode<
703        Weight,
704    >>::Parent;
705    /// # Safety
706    /// Callers must uphold the invariants required by this unsafe API.
707    unsafe fn __parent(&self) -> Option<&Self::Parent> {
708        // SAFETY: token guarantees exclusive/valid access to the inner node.
709        unsafe { (*self.get()).parent() }
710    }
711
712    /// # Safety
713    /// Callers must uphold the invariants required by this unsafe API.
714    unsafe fn __keyexpr(&self) -> OwnedKeyExpr {
715        // SAFETY: token guarantees exclusive/valid access to the inner node.
716        unsafe { (*self.get()).keyexpr() }
717    }
718
719    /// # Safety
720    /// Callers must uphold the invariants required by this unsafe API.
721    unsafe fn __weight(&self) -> Option<&Weight> {
722        // SAFETY: token guarantees exclusive/valid access to the inner node.
723        unsafe { (*self.get()).weight() }
724    }
725
726    type Child = <KeArcTreeNode<Weight, Parent, Wildness, Children, Token> as UIKeyExprTreeNode<
727        Weight,
728    >>::Child;
729
730    type Children= <KeArcTreeNode<Weight, Parent, Wildness, Children, Token> as UIKeyExprTreeNode<
731    Weight,
732>>::Children;
733
734    /// # Safety
735    /// Callers must uphold the invariants required by this unsafe API.
736    unsafe fn __children(&self) -> &Self::Children {
737        // SAFETY: token guarantees exclusive/valid access to the inner node.
738        unsafe { (*self.get()).children() }
739    }
740}
741
742impl<
743        Weight,
744        Parent: IArcProvider,
745        Wildness: IWildness,
746        Children: IChildrenProvider<
747            Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
748        >,
749        Token: TokenTrait,
750    > HasChunk for KeArcTreeNode<Weight, Parent, Wildness, Children, Token>
751{
752    fn chunk(&self) -> &keyexpr {
753        &self.chunk
754    }
755}
756
757impl<
758        Weight,
759        Parent: IArcProvider,
760        Wildness: IWildness,
761        Children: IChildrenProvider<
762            Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
763        >,
764        Token: TokenTrait,
765    > IKeyExprTreeNode<Weight> for KeArcTreeNode<Weight, Parent, Wildness, Children, Token>
766where
767    Children::Assoc: IChildren<
768        Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
769    >,
770{
771}
772
773impl<
774        Weight,
775        Parent: IArcProvider,
776        Wildness: IWildness,
777        Children: IChildrenProvider<
778            Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
779        >,
780        Token: TokenTrait,
781    > UIKeyExprTreeNode<Weight> for KeArcTreeNode<Weight, Parent, Wildness, Children, Token>
782where
783    Children::Assoc: IChildren<
784        Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
785    >,
786{
787    type Parent =
788        Parent::Ptr<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>;
789    /// # Safety
790    /// Callers must uphold the invariants required by this unsafe API.
791    unsafe fn __parent(&self) -> Option<&Self::Parent> {
792        self.parent.as_ref()
793    }
794    /// May panic if the node has been zombified (see [`Self::is_zombie`])
795    /// # Safety
796    /// Callers must uphold the invariants required by this unsafe API.
797    unsafe fn __keyexpr(&self) -> OwnedKeyExpr {
798        // SAFETY: upheld by the surrounding invariants and prior validation.
799        unsafe {
800            // self._keyexpr is guaranteed to return a valid KE, so no checks are necessary
801            OwnedKeyExpr::from_string_unchecked(self._keyexpr(0))
802        }
803    }
804    /// # Safety
805    /// Callers must uphold the invariants required by this unsafe API.
806    unsafe fn __weight(&self) -> Option<&Weight> {
807        self.weight.as_ref()
808    }
809
810    type Child = Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>;
811    type Children = Children::Assoc;
812    /// # Safety
813    /// Callers must uphold the invariants required by this unsafe API.
814    unsafe fn __children(&self) -> &Self::Children {
815        &self.children
816    }
817}
818
819impl<
820        Weight,
821        Parent: IArcProvider,
822        Wildness: IWildness,
823        Children: IChildrenProvider<
824            Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
825        >,
826        Token: TokenTrait,
827    > IKeyExprTreeNodeMut<Weight> for KeArcTreeNode<Weight, Parent, Wildness, Children, Token>
828where
829    Children::Assoc: IChildren<
830        Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
831    >,
832{
833    fn parent_mut(&mut self) -> Option<&mut Self::Parent> {
834        self.parent.as_mut()
835    }
836    fn weight_mut(&mut self) -> Option<&mut Weight> {
837        self.weight.as_mut()
838    }
839    fn take_weight(&mut self) -> Option<Weight> {
840        self.weight.take()
841    }
842    fn insert_weight(&mut self, weight: Weight) -> Option<Weight> {
843        self.weight.replace(weight)
844    }
845    fn children_mut(&mut self) -> &mut Self::Children {
846        &mut self.children
847    }
848}
849
850impl<
851        Weight,
852        Wildness: IWildness,
853        Children: IChildrenProvider<
854            Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
855        >,
856        Token: TokenTrait,
857    > KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>
858where
859    Children::Assoc: IChildren<
860        Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
861    >,
862{
863    /// Under specific circumstances, a node that's been cloned from a tree might have a destroyed parent.
864    /// Such a node is "zombified", and becomes unable to perform certain operations such as navigating its parents,
865    /// which may be necessary for operations such as [`IKeyExprTreeNode::keyexpr`].
866    ///
867    /// To become zombified, a node and its parents must both have been pruned from the tree that constructed them, while at least one of the parents has also been dropped everywhere it was aliased through [`Arc`].
868    pub fn is_zombie(&self) -> bool {
869        match &self.parent {
870            Some(parent) => match parent.upgrade() {
871                // SAFETY: upheld by the surrounding invariants and prior validation.
872                Some(parent) => unsafe { &*parent.get() }.is_zombie(),
873                None => true,
874            },
875            None => false,
876        }
877    }
878}
879
880impl<
881        Weight,
882        Parent: IArcProvider,
883        Wildness: IWildness,
884        Children: IChildrenProvider<
885            Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
886        >,
887        Token: TokenTrait,
888    > KeArcTreeNode<Weight, Parent, Wildness, Children, Token>
889where
890    Children::Assoc: IChildren<
891        Arc<TokenCell<KeArcTreeNode<Weight, Weak<()>, Wildness, Children, Token>, Token>>,
892    >,
893{
894    fn _keyexpr(&self, capacity: usize) -> String {
895        let mut s = match self.parent() {
896            Some(parent) => {
897                // SAFETY: upheld by the surrounding invariants and prior validation.
898                let parent = unsafe {
899                    &*parent
900                        .upgrade()
901                        .expect("Attempted to use a zombie KeArcTreeNode (see KeArcTreeNode::is_zombie())")
902                        .get()
903                };
904                parent._keyexpr(capacity + self.chunk.len() + 1) + "/"
905            }
906            None => String::with_capacity(capacity + self.chunk.len()),
907        };
908        s.push_str(self.chunk.as_str());
909        s
910    }
911}
zenoh_keyexpr/keyexpr_tree/arc_tree.rs

zenoh_keyexpr/keyexpr_tree/
arc_tree.rs
