reddb_file/
graph_table_index.rs

1//! Persisted graph-table index frame.
2//!
3//! The server owns the bidirectional in-memory indexes and locking. This
4//! module owns the durable byte contract for node-to-row mappings.
5
6use crate::{decode_graph_table_ref, encode_graph_table_ref, GraphTableRef, GRAPH_TABLE_REF_SIZE};
7
8pub const GRAPH_TABLE_INDEX_ENTRY_HEADER_LEN: usize = 2;
9pub const GRAPH_TABLE_INDEX_HEADER_LEN: usize = 4;
10pub const GRAPH_TABLE_INDEX_MAX_NODE_ID_LEN: usize = u16::MAX as usize;
11
12#[derive(Debug, Clone, PartialEq, Eq)]
13pub struct GraphTableIndexEntry {
14    pub node_id: String,
15    pub table_ref: GraphTableRef,
16}
17
18#[derive(Debug, Clone, PartialEq, Eq)]
19pub enum GraphTableIndexFrameError {
20    TooManyEntries { len: usize, max: usize },
21    NodeIdTooLong { len: usize, max: usize },
22    Malformed { offset: usize, reason: &'static str },
23}
24
25impl std::fmt::Display for GraphTableIndexFrameError {
26    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
27        match self {
28            Self::TooManyEntries { len, max } => {
29                write!(f, "too many graph-table index entries: {len} (max {max})")
30            }
31            Self::NodeIdTooLong { len, max } => {
32                write!(f, "graph-table node id too long: {len} bytes (max {max})")
33            }
34            Self::Malformed { offset, reason } => {
35                write!(
36                    f,
37                    "malformed graph-table index at offset {offset}: {reason}"
38                )
39            }
40        }
41    }
42}
43
44impl std::error::Error for GraphTableIndexFrameError {}
45
46pub fn encode_graph_table_index_frame(
47    entries: &[GraphTableIndexEntry],
48) -> Result<Vec<u8>, GraphTableIndexFrameError> {
49    let entry_count =
50        u32::try_from(entries.len()).map_err(|_| GraphTableIndexFrameError::TooManyEntries {
51            len: entries.len(),
52            max: u32::MAX as usize,
53        })?;
54
55    let mut buf = Vec::with_capacity(
56        GRAPH_TABLE_INDEX_HEADER_LEN
57            + entries.len() * (GRAPH_TABLE_INDEX_ENTRY_HEADER_LEN + GRAPH_TABLE_REF_SIZE),
58    );
59    buf.extend_from_slice(&entry_count.to_le_bytes());
60
61    for entry in entries {
62        let id_bytes = entry.node_id.as_bytes();
63        let id_len = u16::try_from(id_bytes.len()).map_err(|_| {
64            GraphTableIndexFrameError::NodeIdTooLong {
65                len: id_bytes.len(),
66                max: GRAPH_TABLE_INDEX_MAX_NODE_ID_LEN,
67            }
68        })?;
69
70        buf.extend_from_slice(&id_len.to_le_bytes());
71        buf.extend_from_slice(id_bytes);
72        buf.extend_from_slice(&encode_graph_table_ref(entry.table_ref));
73    }
74
75    Ok(buf)
76}
77
78pub fn decode_graph_table_index_frame(
79    data: &[u8],
80) -> Result<Vec<GraphTableIndexEntry>, GraphTableIndexFrameError> {
81    if data.len() < GRAPH_TABLE_INDEX_HEADER_LEN {
82        return Err(GraphTableIndexFrameError::Malformed {
83            offset: 0,
84            reason: "header truncated",
85        });
86    }
87
88    let count = u32::from_le_bytes(
89        data[0..GRAPH_TABLE_INDEX_HEADER_LEN]
90            .try_into()
91            .expect("header length checked"),
92    ) as usize;
93    let mut offset = GRAPH_TABLE_INDEX_HEADER_LEN;
94    let mut entries = Vec::with_capacity(count);
95
96    for _ in 0..count {
97        if data.len() < offset + GRAPH_TABLE_INDEX_ENTRY_HEADER_LEN {
98            return Err(GraphTableIndexFrameError::Malformed {
99                offset,
100                reason: "node id length truncated",
101            });
102        }
103        let id_len = u16::from_le_bytes(
104            data[offset..offset + GRAPH_TABLE_INDEX_ENTRY_HEADER_LEN]
105                .try_into()
106                .expect("entry header length checked"),
107        ) as usize;
108        offset += GRAPH_TABLE_INDEX_ENTRY_HEADER_LEN;
109
110        if data.len() < offset + id_len {
111            return Err(GraphTableIndexFrameError::Malformed {
112                offset,
113                reason: "node id bytes truncated",
114            });
115        }
116        let node_id = std::str::from_utf8(&data[offset..offset + id_len])
117            .map_err(|_| GraphTableIndexFrameError::Malformed {
118                offset,
119                reason: "node id not utf8",
120            })?
121            .to_string();
122        offset += id_len;
123
124        if data.len() < offset + GRAPH_TABLE_REF_SIZE {
125            return Err(GraphTableIndexFrameError::Malformed {
126                offset,
127                reason: "table ref truncated",
128            });
129        }
130        let table_ref = decode_graph_table_ref(&data[offset..offset + GRAPH_TABLE_REF_SIZE])
131            .ok_or(GraphTableIndexFrameError::Malformed {
132                offset,
133                reason: "invalid table ref",
134            })?;
135        offset += GRAPH_TABLE_REF_SIZE;
136
137        entries.push(GraphTableIndexEntry { node_id, table_ref });
138    }
139
140    Ok(entries)
141}
142
143#[cfg(test)]
144mod tests {
145    use super::*;
146
147    #[test]
148    fn graph_table_index_frame_round_trips() {
149        let entries = vec![
150            GraphTableIndexEntry {
151                node_id: "node:a".to_string(),
152                table_ref: GraphTableRef {
153                    table_id: 1,
154                    row_id: 100,
155                },
156            },
157            GraphTableIndexEntry {
158                node_id: "node:b".to_string(),
159                table_ref: GraphTableRef {
160                    table_id: 2,
161                    row_id: 200,
162                },
163            },
164        ];
165
166        let encoded = encode_graph_table_index_frame(&entries).unwrap();
167        let decoded = decode_graph_table_index_frame(&encoded).unwrap();
168        assert_eq!(decoded, entries);
169    }
170
171    #[test]
172    fn graph_table_index_frame_rejects_truncated_input() {
173        assert!(matches!(
174            decode_graph_table_index_frame(&[1, 2, 3]),
175            Err(GraphTableIndexFrameError::Malformed { .. })
176        ));
177
178        let encoded = encode_graph_table_index_frame(&[GraphTableIndexEntry {
179            node_id: "node:a".to_string(),
180            table_ref: GraphTableRef {
181                table_id: 1,
182                row_id: 100,
183            },
184        }])
185        .unwrap();
186        assert!(matches!(
187            decode_graph_table_index_frame(&encoded[..encoded.len() - 1]),
188            Err(GraphTableIndexFrameError::Malformed { .. })
189        ));
190    }
191
192    #[test]
193    fn graph_table_index_frame_rejects_invalid_utf8_node_id() {
194        let mut bytes = Vec::new();
195        bytes.extend_from_slice(&1u32.to_le_bytes());
196        bytes.extend_from_slice(&1u16.to_le_bytes());
197        bytes.push(0xff);
198        bytes.extend_from_slice(&encode_graph_table_ref(GraphTableRef {
199            table_id: 1,
200            row_id: 100,
201        }));
202
203        assert!(matches!(
204            decode_graph_table_index_frame(&bytes),
205            Err(GraphTableIndexFrameError::Malformed { .. })
206        ));
207    }
208}
reddb_file/graph_table_index.rs

reddb_file/
graph_table_index.rs
