velesdb_core/collection/graph/
label_table.rs

1//! String interning for graph labels (EPIC-019 US-004).
2//!
3//! Provides memory-efficient storage for repetitive labels in knowledge graphs.
4//! With 10M edges having only ~20 distinct labels, this can save ~200MB of memory.
5
6// Reason: Numeric casts in label table are intentional:
7// - usize->u32 for LabelId: Table capacity is bounded (typically < 10K labels)
8// - LabelId is validated against table bounds on lookup
9#![allow(clippy::cast_possible_truncation)]
10
11use std::collections::HashMap;
12use thiserror::Error;
13
14/// Error type for LabelTable operations.
15#[derive(Debug, Error)]
16#[non_exhaustive]
17pub enum LabelTableError {
18    /// The label table has reached its maximum capacity.
19    #[error("LabelTable overflow: cannot intern more than {max_labels} labels")]
20    Overflow {
21        /// Maximum number of labels supported.
22        max_labels: u32,
23    },
24}
25
26/// ID for an interned label string.
27///
28/// Using u32 allows ~4 billion unique labels while saving memory
29/// compared to storing String on each node/edge.
30#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
31pub struct LabelId(u32);
32
33impl LabelId {
34    /// Returns the raw ID value.
35    #[must_use]
36    pub fn as_u32(self) -> u32 {
37        self.0
38    }
39
40    /// Creates a LabelId from a raw value (for deserialization).
41    #[must_use]
42    pub fn from_u32(id: u32) -> Self {
43        Self(id)
44    }
45}
46
47/// String interning table for graph labels.
48///
49/// Stores each unique label string once and returns a compact `LabelId`
50/// that can be used for efficient comparison and storage.
51///
52/// # Example
53///
54/// ```rust,ignore
55/// use velesdb_core::collection::graph::LabelTable;
56///
57/// let mut table = LabelTable::new();
58///
59/// // Intern same label multiple times - returns same ID
60/// let id1 = table.intern("Person");
61/// let id2 = table.intern("Person");
62/// assert_eq!(id1, id2);
63///
64/// // Resolve ID back to string
65/// assert_eq!(table.resolve(id1), Some("Person"));
66/// ```
67#[derive(Debug, Default)]
68pub struct LabelTable {
69    /// Stored strings indexed by LabelId
70    strings: Vec<String>,
71    /// Reverse lookup: string -> LabelId
72    ids: HashMap<String, LabelId>,
73}
74
75impl LabelTable {
76    /// Creates a new empty label table.
77    #[must_use]
78    pub fn new() -> Self {
79        Self::default()
80    }
81
82    /// Creates a label table with pre-allocated capacity.
83    ///
84    /// # Arguments
85    ///
86    /// * `expected_labels` - Expected number of unique labels
87    #[must_use]
88    pub fn with_capacity(expected_labels: usize) -> Self {
89        Self {
90            strings: Vec::with_capacity(expected_labels),
91            ids: HashMap::with_capacity(expected_labels),
92        }
93    }
94
95    /// Interns a string and returns its ID.
96    ///
97    /// If the string was already interned, returns the existing ID.
98    /// Otherwise, stores the string and returns a new ID.
99    ///
100    /// # Arguments
101    ///
102    /// * `s` - The string to intern
103    ///
104    /// # Returns
105    ///
106    /// The `LabelId` for this string (existing or newly created), or an error
107    /// if the table has reached capacity (4 billion labels).
108    ///
109    /// # Errors
110    ///
111    /// Returns an error if the number of interned strings would exceed `u32::MAX`.
112    pub fn intern(&mut self, s: &str) -> Result<LabelId, LabelTableError> {
113        if let Some(&id) = self.ids.get(s) {
114            return Ok(id);
115        }
116        let len = self.strings.len();
117        if len >= u32::MAX as usize {
118            return Err(LabelTableError::Overflow {
119                max_labels: u32::MAX,
120            });
121        }
122        // Reason: len checked against u32::MAX above, truncation impossible
123        #[allow(clippy::cast_possible_truncation)]
124        let id = LabelId(len as u32);
125        let owned = s.to_owned();
126        self.strings.push(owned.clone());
127        self.ids.insert(owned, id);
128        Ok(id)
129    }
130
131    /// Resolves a LabelId back to its original string.
132    ///
133    /// # Arguments
134    ///
135    /// * `id` - The LabelId to resolve
136    ///
137    /// # Returns
138    ///
139    /// The original string, or `None` if the ID is invalid
140    #[must_use]
141    pub fn resolve(&self, id: LabelId) -> Option<&str> {
142        self.strings.get(id.0 as usize).map(String::as_str)
143    }
144
145    /// Returns the number of unique labels in the table.
146    #[must_use]
147    pub fn len(&self) -> usize {
148        self.strings.len()
149    }
150
151    /// Returns true if no labels have been interned.
152    #[must_use]
153    pub fn is_empty(&self) -> bool {
154        self.strings.is_empty()
155    }
156
157    /// Returns an iterator over all interned labels.
158    pub fn iter(&self) -> impl Iterator<Item = (LabelId, &str)> {
159        self.strings
160            .iter()
161            .enumerate()
162            .map(|(i, s)| (LabelId(i as u32), s.as_str()))
163    }
164
165    /// Gets the ID for a label if it exists, without interning.
166    ///
167    /// Useful for lookup operations where you don't want to add new labels.
168    #[must_use]
169    pub fn get_id(&self, s: &str) -> Option<LabelId> {
170        self.ids.get(s).copied()
171    }
172
173    /// Checks if a label is already interned.
174    #[must_use]
175    pub fn contains(&self, s: &str) -> bool {
176        self.ids.contains_key(s)
177    }
178}
179
180// Tests moved to label_table_tests.rs per project rules
velesdb_core/collection/graph/label_table.rs

velesdb_core/collection/graph/
label_table.rs
