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

zenoh_keyexpr/keyexpr_tree/
arc_tree.rs
