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

zenoh_keyexpr/keyexpr_tree/
arc_tree.rs
