mib_rs/mib/
node.rs

1//! OID tree nodes and the arena-backed OID tree.
2//!
3//! The [`OidTree`] stores all nodes in a contiguous arena indexed by [`NodeId`].
4//! Each [`NodeData`] holds a single arc in the OID hierarchy, links to its
5//! parent and children, and optional references to attached entities (objects,
6//! notifications, groups, etc.).
7//!
8//! For most use cases, prefer the [`Node`](super::handle::Node) handle, which
9//! wraps a `NodeId` with a `&Mib` reference and provides navigation methods
10//! that return further handles.
11
12use std::collections::BTreeMap;
13use std::sync::OnceLock;
14
15use crate::mib::Oid;
16use crate::types::{Kind, Span, Status};
17
18use super::types::*;
19
20/// A single node in the OID tree.
21///
22/// Each node corresponds to one arc in the OID hierarchy. Nodes may have
23/// attached entities (object, notification, group, compliance, capability).
24/// Access fields through the public accessor methods or the [`Node`](super::handle::Node)
25/// handle type.
26#[derive(Debug)]
27pub struct NodeData {
28    pub(crate) arc: u32,
29    pub(crate) name: String,
30    pub(crate) description: String,
31    pub(crate) reference: String,
32    pub(crate) status: Option<Status>,
33    pub(crate) kind: Kind,
34    pub(crate) span: Span,
35    pub(crate) parent: Option<NodeId>,
36    pub(crate) children: BTreeMap<u32, NodeId>,
37    pub(crate) module: Option<ModuleId>,
38    pub(crate) object: Option<ObjectId>,
39    pub(crate) notification: Option<NotificationId>,
40    pub(crate) group: Option<GroupId>,
41    pub(crate) compliance: Option<ComplianceId>,
42    pub(crate) capability: Option<CapabilityId>,
43    pub(crate) oid_cache: OnceLock<Oid>,
44}
45
46impl NodeData {
47    pub(crate) fn new(arc: u32, parent: Option<NodeId>) -> Self {
48        Self {
49            arc,
50            name: String::new(),
51            description: String::new(),
52            reference: String::new(),
53            status: None,
54            kind: Kind::Internal,
55            span: Span::SYNTHETIC,
56            parent,
57            children: BTreeMap::new(),
58            module: None,
59            object: None,
60            notification: None,
61            group: None,
62            compliance: None,
63            capability: None,
64            oid_cache: OnceLock::new(),
65        }
66    }
67
68    pub(crate) fn root() -> Self {
69        Self::new(0, None)
70    }
71}
72
73impl NodeData {
74    /// Return the node's numeric OID arc relative to its parent.
75    pub fn arc(&self) -> u32 {
76        self.arc
77    }
78
79    /// Return the node's local symbolic name.
80    pub fn name(&self) -> &str {
81        &self.name
82    }
83
84    /// Return the DESCRIPTION text for this node.
85    pub fn description(&self) -> &str {
86        &self.description
87    }
88
89    /// Return the REFERENCE text for this node.
90    pub fn reference(&self) -> &str {
91        &self.reference
92    }
93
94    /// Return the status, if set on this node.
95    pub fn status(&self) -> Option<Status> {
96        self.status
97    }
98
99    /// Return the node kind (scalar, table, internal, etc.).
100    pub fn kind(&self) -> Kind {
101        self.kind
102    }
103
104    /// Return the source span of this node's definition.
105    pub fn span(&self) -> Span {
106        self.span
107    }
108
109    /// Return the parent node id, or `None` for the root.
110    pub fn parent(&self) -> Option<NodeId> {
111        self.parent
112    }
113
114    /// Return the child map (arc -> [`NodeId`]) in ascending arc order.
115    pub fn children(&self) -> &BTreeMap<u32, NodeId> {
116        &self.children
117    }
118
119    /// Return the owning module id, if set.
120    pub fn module(&self) -> Option<ModuleId> {
121        self.module
122    }
123
124    /// Return the attached object id, if any.
125    pub fn object(&self) -> Option<ObjectId> {
126        self.object
127    }
128
129    /// Return the attached notification id, if any.
130    pub fn notification(&self) -> Option<NotificationId> {
131        self.notification
132    }
133
134    /// Return the attached group id, if any.
135    pub fn group(&self) -> Option<GroupId> {
136        self.group
137    }
138
139    /// Return the attached compliance id, if any.
140    pub fn compliance(&self) -> Option<ComplianceId> {
141        self.compliance
142    }
143
144    /// Return the attached capability id, if any.
145    pub fn capability(&self) -> Option<CapabilityId> {
146        self.capability
147    }
148
149    /// Reports whether this is the unnamed root node (no parent).
150    pub fn is_root(&self) -> bool {
151        self.parent.is_none()
152    }
153}
154
155/// Arena-allocated OID tree.
156///
157/// Nodes are stored in a contiguous `Vec` indexed by [`NodeId`]. The tree
158/// is built during resolution and then accessed read-only through the
159/// [`Mib`](super::mib::Mib) API.
160#[derive(Debug)]
161pub struct OidTree {
162    nodes: Vec<NodeData>,
163    root: NodeId,
164}
165
166impl OidTree {
167    /// Create an empty tree with a synthetic root node.
168    pub fn new() -> Self {
169        Self {
170            nodes: vec![NodeData::root()],
171            root: NodeId::new(0),
172        }
173    }
174
175    /// Return the root node id.
176    pub fn root(&self) -> NodeId {
177        self.root
178    }
179
180    /// Return the total number of nodes in the tree.
181    pub fn len(&self) -> usize {
182        self.nodes.len()
183    }
184
185    /// Return `true` if the tree contains no nodes.
186    pub fn is_empty(&self) -> bool {
187        self.nodes.is_empty()
188    }
189
190    /// Look up a node by id.
191    ///
192    /// # Panics
193    ///
194    /// Panics if `id` does not correspond to a node in this tree.
195    pub fn get(&self, id: NodeId) -> &NodeData {
196        &self.nodes[id.0 as usize]
197    }
198
199    fn alloc(&mut self, data: NodeData) -> NodeId {
200        let id = NodeId::new(self.nodes.len() as u32);
201        self.nodes.push(data);
202        id
203    }
204
205    /// Return the child at `arc` under `parent`, creating it if absent.
206    pub(crate) fn get_or_create_child(&mut self, parent: NodeId, arc: u32) -> NodeId {
207        if let Some(&child_id) = self.nodes[parent.0 as usize].children.get(&arc) {
208            return child_id;
209        }
210        let child_id = self.alloc(NodeData::new(arc, Some(parent)));
211        self.nodes[parent.0 as usize].children.insert(arc, child_id);
212        child_id
213    }
214
215    pub(crate) fn set_name(&mut self, id: NodeId, name: String) {
216        self.nodes[id.0 as usize].name = name;
217    }
218
219    pub(crate) fn set_kind(&mut self, id: NodeId, kind: Kind) {
220        self.nodes[id.0 as usize].kind = kind;
221    }
222
223    pub(crate) fn set_status(&mut self, id: NodeId, status: Status) {
224        self.nodes[id.0 as usize].status = Some(status);
225    }
226
227    pub(crate) fn set_description(&mut self, id: NodeId, desc: String) {
228        self.nodes[id.0 as usize].description = desc;
229    }
230
231    pub(crate) fn set_reference(&mut self, id: NodeId, reference: String) {
232        self.nodes[id.0 as usize].reference = reference;
233    }
234
235    pub(crate) fn set_span(&mut self, id: NodeId, span: Span) {
236        self.nodes[id.0 as usize].span = span;
237    }
238
239    pub(crate) fn set_module(&mut self, id: NodeId, module: ModuleId) {
240        self.nodes[id.0 as usize].module = Some(module);
241    }
242
243    pub(crate) fn attach_object(&mut self, id: NodeId, obj: ObjectId) {
244        self.nodes[id.0 as usize].object = Some(obj);
245    }
246
247    pub(crate) fn attach_notification(&mut self, id: NodeId, notif: NotificationId) {
248        self.nodes[id.0 as usize].notification = Some(notif);
249    }
250
251    pub(crate) fn attach_group(&mut self, id: NodeId, group: GroupId) {
252        self.nodes[id.0 as usize].group = Some(group);
253    }
254
255    pub(crate) fn attach_compliance(&mut self, id: NodeId, compliance: ComplianceId) {
256        self.nodes[id.0 as usize].compliance = Some(compliance);
257    }
258
259    pub(crate) fn attach_capability(&mut self, id: NodeId, cap: CapabilityId) {
260        self.nodes[id.0 as usize].capability = Some(cap);
261    }
262
263    /// Walk the tree from `start` following arcs in `oid`.
264    ///
265    /// Returns `(last_matched_node, true)` if all arcs matched, or
266    /// `(deepest_matched_node, false)` if the walk stopped early.
267    pub fn walk_oid(&self, start: NodeId, oid: &Oid) -> (NodeId, bool) {
268        let mut current = start;
269        for &arc in oid.iter() {
270            match self.nodes[current.0 as usize].children.get(&arc) {
271                Some(&child) => current = child,
272                None => return (current, false),
273            }
274        }
275        (current, true)
276    }
277
278    fn compute_oid(&self, id: NodeId) -> Oid {
279        let node = &self.nodes[id.0 as usize];
280        if node.parent.is_none() {
281            return Oid::default();
282        }
283        let mut arcs = Vec::new();
284        let mut current = id;
285        loop {
286            let n = &self.nodes[current.0 as usize];
287            match n.parent {
288                Some(parent) => {
289                    arcs.push(n.arc);
290                    current = parent;
291                }
292                None => break,
293            }
294        }
295        arcs.reverse();
296        Oid::from(arcs)
297    }
298
299    /// Return the OID for a node, using the per-node cache.
300    pub fn oid_of(&self, id: NodeId) -> &Oid {
301        self.nodes[id.0 as usize]
302            .oid_cache
303            .get_or_init(|| self.compute_oid(id))
304    }
305
306    /// Depth-first iterator over a subtree rooted at `start`.
307    pub fn subtree(&self, start: NodeId) -> SubtreeIter<'_> {
308        SubtreeIter {
309            tree: self,
310            stack: vec![start],
311        }
312    }
313
314    /// Depth-first iterator over all nodes (excluding root).
315    pub fn all_nodes(&self) -> SubtreeIter<'_> {
316        let root = &self.nodes[self.root.0 as usize];
317        let stack: Vec<NodeId> = root.children.values().rev().copied().collect();
318        SubtreeIter { tree: self, stack }
319    }
320
321    /// Find the deepest node matching a prefix of `oid`, starting from root.
322    pub fn longest_prefix(&self, oid: &Oid) -> NodeId {
323        let (matched, _) = self.walk_oid(self.root, oid);
324        matched
325    }
326
327    /// Find the deepest node matching a prefix of `oid`, starting from `start`.
328    pub fn longest_prefix_from(&self, start: NodeId, oid: &Oid) -> NodeId {
329        let (matched, _) = self.walk_oid(start, oid);
330        matched
331    }
332}
333
334impl Default for OidTree {
335    fn default() -> Self {
336        Self::new()
337    }
338}
339
340/// Depth-first iterator over an OID subtree, yielding [`NodeId`]s.
341pub struct SubtreeIter<'a> {
342    tree: &'a OidTree,
343    stack: Vec<NodeId>,
344}
345
346impl<'a> Iterator for SubtreeIter<'a> {
347    type Item = NodeId;
348
349    fn next(&mut self) -> Option<NodeId> {
350        let id = self.stack.pop()?;
351        let node = &self.tree.nodes[id.0 as usize];
352        // Push children in reverse order so smallest arc is popped first.
353        for (_, &child_id) in node.children.iter().rev() {
354            self.stack.push(child_id);
355        }
356        Some(id)
357    }
358}
359
360#[cfg(test)]
361mod tests {
362    use super::*;
363
364    #[test]
365    fn tree_construction() {
366        let mut tree = OidTree::new();
367        let root = tree.root();
368
369        let iso = tree.get_or_create_child(root, 1);
370        tree.set_name(iso, "iso".into());
371
372        let org = tree.get_or_create_child(iso, 3);
373        tree.set_name(org, "org".into());
374
375        let dod = tree.get_or_create_child(org, 6);
376        tree.set_name(dod, "dod".into());
377
378        assert_eq!(tree.len(), 4); // root + 3 nodes
379        assert_eq!(tree.get(iso).name, "iso");
380        assert_eq!(tree.get(org).name, "org");
381        assert_eq!(tree.get(dod).name, "dod");
382
383        let oid = tree.oid_of(dod);
384        assert_eq!(&**oid, &[1, 3, 6]);
385    }
386
387    #[test]
388    fn get_or_create_idempotent() {
389        let mut tree = OidTree::new();
390        let root = tree.root();
391
392        let a = tree.get_or_create_child(root, 1);
393        let b = tree.get_or_create_child(root, 1);
394        assert_eq!(a, b);
395        assert_eq!(tree.len(), 2);
396    }
397
398    #[test]
399    fn walk_oid_exact() {
400        let mut tree = OidTree::new();
401        let root = tree.root();
402        let a = tree.get_or_create_child(root, 1);
403        let b = tree.get_or_create_child(a, 3);
404        let c = tree.get_or_create_child(b, 6);
405
406        let oid: Oid = "1.3.6".parse().unwrap();
407        let (matched, exact) = tree.walk_oid(root, &oid);
408        assert!(exact);
409        assert_eq!(matched, c);
410    }
411
412    #[test]
413    fn walk_oid_partial() {
414        let mut tree = OidTree::new();
415        let root = tree.root();
416        let a = tree.get_or_create_child(root, 1);
417        let _b = tree.get_or_create_child(a, 3);
418
419        let oid: Oid = "1.3.6.1".parse().unwrap();
420        let (_, exact) = tree.walk_oid(root, &oid);
421        assert!(!exact);
422    }
423
424    #[test]
425    fn subtree_iteration() {
426        let mut tree = OidTree::new();
427        let root = tree.root();
428        let a = tree.get_or_create_child(root, 1);
429        let b = tree.get_or_create_child(a, 2);
430        let c = tree.get_or_create_child(a, 3);
431
432        let nodes: Vec<NodeId> = tree.subtree(a).collect();
433        assert_eq!(nodes, vec![a, b, c]);
434    }
435
436    #[test]
437    fn all_nodes_excludes_root() {
438        let mut tree = OidTree::new();
439        let root = tree.root();
440        let a = tree.get_or_create_child(root, 1);
441        let b = tree.get_or_create_child(root, 2);
442
443        let nodes: Vec<NodeId> = tree.all_nodes().collect();
444        assert_eq!(nodes, vec![a, b]);
445    }
446
447    #[test]
448    fn oid_caching() {
449        let mut tree = OidTree::new();
450        let root = tree.root();
451        let a = tree.get_or_create_child(root, 1);
452        let b = tree.get_or_create_child(a, 3);
453
454        let oid1 = tree.oid_of(b);
455        let oid2 = tree.oid_of(b);
456        assert!(std::ptr::eq(oid1, oid2));
457    }
458
459    #[test]
460    fn root_oid_is_empty() {
461        let tree = OidTree::new();
462        let root = tree.root();
463        assert!(tree.oid_of(root).is_empty());
464    }
465
466    #[test]
467    fn longest_prefix_from_node() {
468        let mut tree = OidTree::new();
469        let root = tree.root();
470        let a = tree.get_or_create_child(root, 1);
471        let b = tree.get_or_create_child(a, 3);
472        let c = tree.get_or_create_child(b, 6);
473
474        // From node a, OID "3.6" should match c exactly.
475        let matched = tree.longest_prefix_from(a, &"3.6".parse().unwrap());
476        assert_eq!(matched, c);
477
478        // From node a, OID "3.6.99" should match c (partial).
479        let matched = tree.longest_prefix_from(a, &"3.6.99".parse().unwrap());
480        assert_eq!(matched, c);
481
482        // From node b, OID "99" should stay at b (no child 99).
483        let matched = tree.longest_prefix_from(b, &"99".parse().unwrap());
484        assert_eq!(matched, b);
485    }
486
487    #[test]
488    fn is_root() {
489        let mut tree = OidTree::new();
490        let root = tree.root();
491        let child = tree.get_or_create_child(root, 1);
492
493        assert!(tree.get(root).is_root());
494        assert!(!tree.get(child).is_root());
495    }
496}
mib_rs/mib/node.rs

mib_rs/mib/
node.rs
