rudy_dwarf/parser/
btreemap.rs

1//! BTreeMap parser implementation using combinators
2//!
3//! Inspired by the `BTreeMapProvider` in [gdb_provider.py](https://github.com/rust-lang/rust/blob/513999b936c37902120380f4171963d1f1d80347/src/etc/gdb_providers.py#L4)
4//!
5//!   Overview: BTreeMap stores key-value pairs in a B-tree structure with internal nodes and leaf nodes. The tree has a
6//! height, and we traverse from the root down to the leaves.
7//!
8//! Algorithm:
9//! 1. Start with the BTreeMap's root node and height
10//! 2. If the map is empty (length = 0), return immediately
11//! 3. Extract the root node pointer from the Option wrapper
12//! 4. Recursively traverse the tree starting from the root with the given height
13//! 5. For each node:
14//! - If it's an internal node (height > 0):
15//!     - Cast to InternalNode type to access edges
16//!   - Recursively traverse each child edge before processing keys/values
17//! - Process the node's key-value pairs:
18//!     - Read the len field to know how many pairs are in this node
19//!   - Iterate through indices 0 to len-1
20//!   - For each index, yield the key and value from the arrays
21//!
22//!
23//! Key details:
24//! - Internal nodes have edges (child pointers) in addition to keys/values
25//! - Leaf nodes only have keys/values
26//! - The tree is traversed in-order (left edge, key/value, right edge)
27//! - Zero-sized types need special handling
28
29use anyhow::Result;
30use rudy_types::{BTreeNodeLayout, BTreeRootLayout, MapLayout, MapVariant};
31
32use super::{primitives::entry_type, Parser};
33use crate::{
34    parser::{
35        children::parse_children,
36        option::parse_option_entry,
37        pointers::nonnull,
38        primitives::{data_offset, is_member, member, resolved_generic},
39    },
40    Die, DwarfDb,
41};
42
43/// Parser for btree BTreeMap layout
44pub fn btree_map() -> BTreeMapParser {
45    BTreeMapParser
46}
47
48pub struct BTreeMapParser;
49
50impl Parser<MapLayout<Die>> for BTreeMapParser {
51    fn parse(&self, db: &dyn DwarfDb, entry: Die) -> Result<MapLayout<Die>> {
52        tracing::debug!("resolving btree map type: {}", entry.print(db));
53
54        // Parse key type, value type, root field, and length field from BTreeMap
55        let (key_type, value_type, (root_offset, root_option_type), length_offset) =
56            parse_children((
57                resolved_generic("K"),
58                resolved_generic("V"),
59                is_member("root").then(data_offset().and(entry_type())),
60                is_member("length").then(data_offset()),
61            ))
62            .parse(db, entry)?;
63
64        tracing::debug!("resolving root field: {}", root_option_type.print(db));
65
66        // Parse the Option<NodeRef> to get the Some variant which contains the NodeRef
67        let (_, _, _, some_variant) = parse_option_entry().parse(db, root_option_type)?;
68        let node_ref_type = some_variant.layout;
69
70        tracing::debug!("resolving node ref field: {}", node_ref_type.print(db));
71
72        // Parse the NodeRef struct to get height and node pointer offsets
73        let (height_offset, (node_offset, node_ptr_type)) = parse_children((
74            is_member("height").then(data_offset()),
75            is_member("node").then(data_offset().and(entry_type())),
76        ))
77        .parse(db, node_ref_type)?;
78
79        // Create the root layout
80        let root_layout = BTreeRootLayout {
81            node_offset,
82            height_offset,
83        };
84
85        // The node pointer is a NonNull<LeafNode<K, V>>, resolve it to get the leaf node type
86        let leaf_node_type = nonnull().parse(db, node_ptr_type)?;
87
88        tracing::debug!("resolving leaf node type: {}", leaf_node_type.print(db));
89
90        // Parse the LeafNode structure to get offsets
91        let (len_offset, keys_offset, vals_offset) = parse_children((
92            is_member("len").then(data_offset()),
93            is_member("keys").then(data_offset()),
94            is_member("vals").then(data_offset()),
95        ))
96        .parse(db, leaf_node_type)?;
97
98        // To get the InternalNode type, we need to find the parent field which contains
99        // Option<NonNull<InternalNode<K, V>>>. We'll extract this type.
100        let parent_option_type = member("parent")
101            .then(entry_type())
102            .parse(db, leaf_node_type)?;
103
104        // Parse the Option to get the Some variant
105        let (_, _, _, parent_some_variant) = parse_option_entry().parse(db, parent_option_type)?;
106
107        // The Some variant contains NonNull<InternalNode<K, V>>, resolve it
108        let internal_node_type = nonnull().parse(db, parent_some_variant.layout)?;
109
110        // For InternalNode, we need the edges offset. The edges field is specific to InternalNode.
111        let edges_offset = member("edges")
112            .then(data_offset())
113            .parse(db, internal_node_type)?;
114
115        // Create the node layout
116        let node_layout = BTreeNodeLayout {
117            keys_offset,
118            vals_offset,
119            len_offset,
120            edges_offset,
121        };
122
123        Ok(MapLayout {
124            key_type,
125            value_type,
126            variant: MapVariant::BTreeMap {
127                length_offset,
128                root_offset,
129                root_layout,
130                node_layout,
131            },
132        })
133    }
134}
rudy_dwarf/parser/btreemap.rs

rudy_dwarf/parser/
btreemap.rs
