oxirs_core/model/
optimized_terms.rs

1// Optimized RDF term representations based on Oxigraph's oxrdf optimizations
2// This module provides memory-efficient, hash-based term storage and encoding
3
4use crate::model::{BlankNode, Literal, NamedNode};
5use siphasher::sip128::{Hasher128, SipHasher24};
6use std::collections::HashMap;
7use std::hash::{Hash, Hasher};
8use std::sync::{Arc, RwLock};
9
10/// A 16-byte hash for efficient string deduplication (Oxigraph-inspired optimization)
11#[derive(Eq, PartialEq, Debug, Clone, Copy)]
12pub struct OxiStrHash {
13    hash: [u8; 16],
14}
15
16impl OxiStrHash {
17    pub fn new(value: &str) -> Self {
18        let mut hasher = SipHasher24::new();
19        hasher.write(value.as_bytes());
20        Self {
21            hash: u128::from(hasher.finish128()).to_be_bytes(),
22        }
23    }
24
25    #[inline]
26    pub fn from_be_bytes(hash: [u8; 16]) -> Self {
27        Self { hash }
28    }
29
30    #[inline]
31    pub fn to_be_bytes(self) -> [u8; 16] {
32        self.hash
33    }
34}
35
36impl Hash for OxiStrHash {
37    #[inline]
38    fn hash<H: Hasher>(&self, state: &mut H) {
39        state.write_u128(u128::from_ne_bytes(self.hash))
40    }
41}
42
43/// Compact encoded representation of RDF terms (Oxigraph-inspired optimization)
44#[derive(Debug, Clone, PartialEq)]
45pub enum OxiEncodedTerm {
46    DefaultGraph,
47    NamedNode {
48        iri: OxiStrHash,
49    },
50    BlankNode {
51        id: OxiStrHash,
52    },
53    Literal {
54        value: OxiStrHash,
55        datatype: Option<OxiStrHash>,
56        language: Option<String>,
57    },
58    // Optimized encodings for common literal types
59    BooleanLiteral(bool),
60    IntegerLiteral(i64),
61    FloatLiteral(f32),
62    DoubleLiteral(f64),
63    StringLiteral(OxiStrHash),
64}
65
66impl Hash for OxiEncodedTerm {
67    fn hash<H: Hasher>(&self, state: &mut H) {
68        match self {
69            OxiEncodedTerm::DefaultGraph => {
70                0u8.hash(state);
71            }
72            OxiEncodedTerm::NamedNode { iri } => {
73                1u8.hash(state);
74                iri.hash(state);
75            }
76            OxiEncodedTerm::BlankNode { id } => {
77                2u8.hash(state);
78                id.hash(state);
79            }
80            OxiEncodedTerm::Literal {
81                value,
82                datatype,
83                language,
84            } => {
85                3u8.hash(state);
86                value.hash(state);
87                datatype.hash(state);
88                language.hash(state);
89            }
90            OxiEncodedTerm::BooleanLiteral(value) => {
91                4u8.hash(state);
92                value.hash(state);
93            }
94            OxiEncodedTerm::IntegerLiteral(value) => {
95                5u8.hash(state);
96                value.hash(state);
97            }
98            OxiEncodedTerm::FloatLiteral(value) => {
99                6u8.hash(state);
100                // For floating point values, we use the bit representation for hashing
101                value.to_bits().hash(state);
102            }
103            OxiEncodedTerm::DoubleLiteral(value) => {
104                7u8.hash(state);
105                // For floating point values, we use the bit representation for hashing
106                value.to_bits().hash(state);
107            }
108            OxiEncodedTerm::StringLiteral(value) => {
109                8u8.hash(state);
110                value.hash(state);
111            }
112        }
113    }
114}
115
116impl Eq for OxiEncodedTerm {}
117
118/// High-performance string interner using hash-based deduplication
119#[derive(Debug, Default)]
120pub struct StringInterner {
121    /// Maps hashes to actual strings
122    string_storage: HashMap<OxiStrHash, String>,
123    /// Statistics
124    total_strings: usize,
125    total_deduplication_saves: usize,
126}
127
128impl StringInterner {
129    pub fn new() -> Self {
130        Self::default()
131    }
132
133    /// Intern a string and return its hash
134    pub fn intern(&mut self, value: &str) -> OxiStrHash {
135        let hash = OxiStrHash::new(value);
136
137        if let std::collections::hash_map::Entry::Vacant(e) = self.string_storage.entry(hash) {
138            e.insert(value.to_string());
139            self.total_strings += 1;
140        } else {
141            self.total_deduplication_saves += 1;
142        }
143
144        hash
145    }
146
147    /// Resolve a hash back to its string
148    pub fn resolve(&self, hash: &OxiStrHash) -> Option<&str> {
149        self.string_storage.get(hash).map(|s| s.as_str())
150    }
151
152    /// Get interning statistics
153    pub fn stats(&self) -> InternerStats {
154        InternerStats {
155            total_strings: self.total_strings,
156            deduplication_saves: self.total_deduplication_saves,
157            memory_usage: self.string_storage.values().map(|s| s.len()).sum(),
158        }
159    }
160}
161
162#[derive(Debug, Clone)]
163pub struct InternerStats {
164    pub total_strings: usize,
165    pub deduplication_saves: usize,
166    pub memory_usage: usize,
167}
168
169/// Thread-safe term encoder with optimized storage
170pub struct OptimizedTermEncoder {
171    interner: Arc<RwLock<StringInterner>>,
172}
173
174impl OptimizedTermEncoder {
175    pub fn new() -> Self {
176        Self {
177            interner: Arc::new(RwLock::new(StringInterner::new())),
178        }
179    }
180
181    /// Encode a named node efficiently
182    pub fn encode_named_node(&self, node: &NamedNode) -> OxiEncodedTerm {
183        let mut interner = self
184            .interner
185            .write()
186            .unwrap_or_else(|poisoned| poisoned.into_inner());
187        let iri_hash = interner.intern(node.as_str());
188        OxiEncodedTerm::NamedNode { iri: iri_hash }
189    }
190
191    /// Encode a blank node efficiently
192    pub fn encode_blank_node(&self, node: &BlankNode) -> OxiEncodedTerm {
193        let mut interner = self
194            .interner
195            .write()
196            .unwrap_or_else(|poisoned| poisoned.into_inner());
197        let id_hash = interner.intern(node.as_str());
198        OxiEncodedTerm::BlankNode { id: id_hash }
199    }
200
201    /// Encode a literal with type-specific optimizations
202    pub fn encode_literal(&self, literal: &Literal) -> OxiEncodedTerm {
203        let literal_str = literal.value();
204
205        // Try type-specific optimizations first
206        let datatype = literal.datatype();
207        match datatype.as_str() {
208            "http://www.w3.org/2001/XMLSchema#boolean" => {
209                if let Ok(value) = literal_str.parse::<bool>() {
210                    return OxiEncodedTerm::BooleanLiteral(value);
211                }
212            }
213            "http://www.w3.org/2001/XMLSchema#integer"
214            | "http://www.w3.org/2001/XMLSchema#int"
215            | "http://www.w3.org/2001/XMLSchema#long" => {
216                if let Ok(value) = literal_str.parse::<i64>() {
217                    return OxiEncodedTerm::IntegerLiteral(value);
218                }
219            }
220            "http://www.w3.org/2001/XMLSchema#float" => {
221                if let Ok(value) = literal_str.parse::<f32>() {
222                    return OxiEncodedTerm::FloatLiteral(value);
223                }
224            }
225            "http://www.w3.org/2001/XMLSchema#double" => {
226                if let Ok(value) = literal_str.parse::<f64>() {
227                    return OxiEncodedTerm::DoubleLiteral(value);
228                }
229            }
230            "http://www.w3.org/2001/XMLSchema#string" => {
231                let mut interner = self
232                    .interner
233                    .write()
234                    .unwrap_or_else(|poisoned| poisoned.into_inner());
235                let value_hash = interner.intern(literal_str);
236                return OxiEncodedTerm::StringLiteral(value_hash);
237            }
238            _ => {
239                // Fall through to general encoding
240            }
241        }
242
243        // General literal encoding
244        let mut interner = self
245            .interner
246            .write()
247            .unwrap_or_else(|poisoned| poisoned.into_inner());
248        let value_hash = interner.intern(literal_str);
249
250        let datatype_hash = Some(interner.intern(datatype.as_str()));
251        let language = literal.language().map(|lang| lang.to_string());
252
253        OxiEncodedTerm::Literal {
254            value: value_hash,
255            datatype: datatype_hash,
256            language,
257        }
258    }
259
260    /// Decode an encoded term back to its original form
261    pub fn decode_term(&self, encoded: &OxiEncodedTerm) -> Result<DecodedTerm, String> {
262        let interner = self
263            .interner
264            .read()
265            .unwrap_or_else(|poisoned| poisoned.into_inner());
266
267        match encoded {
268            OxiEncodedTerm::DefaultGraph => Ok(DecodedTerm::DefaultGraph),
269
270            OxiEncodedTerm::NamedNode { iri } => {
271                let iri_str = interner
272                    .resolve(iri)
273                    .ok_or("IRI hash not found in interner")?;
274                Ok(DecodedTerm::NamedNode(iri_str.to_string()))
275            }
276
277            OxiEncodedTerm::BlankNode { id } => {
278                let id_str = interner
279                    .resolve(id)
280                    .ok_or("Blank node ID hash not found in interner")?;
281                Ok(DecodedTerm::BlankNode(id_str.to_string()))
282            }
283
284            OxiEncodedTerm::BooleanLiteral(value) => Ok(DecodedTerm::Literal {
285                value: value.to_string(),
286                datatype: Some("http://www.w3.org/2001/XMLSchema#boolean".to_string()),
287                language: None,
288            }),
289
290            OxiEncodedTerm::IntegerLiteral(value) => Ok(DecodedTerm::Literal {
291                value: value.to_string(),
292                datatype: Some("http://www.w3.org/2001/XMLSchema#integer".to_string()),
293                language: None,
294            }),
295
296            OxiEncodedTerm::FloatLiteral(value) => Ok(DecodedTerm::Literal {
297                value: value.to_string(),
298                datatype: Some("http://www.w3.org/2001/XMLSchema#float".to_string()),
299                language: None,
300            }),
301
302            OxiEncodedTerm::DoubleLiteral(value) => Ok(DecodedTerm::Literal {
303                value: value.to_string(),
304                datatype: Some("http://www.w3.org/2001/XMLSchema#double".to_string()),
305                language: None,
306            }),
307
308            OxiEncodedTerm::StringLiteral(value_hash) => {
309                let value_str = interner
310                    .resolve(value_hash)
311                    .ok_or("String literal hash not found in interner")?;
312                Ok(DecodedTerm::Literal {
313                    value: value_str.to_string(),
314                    datatype: Some("http://www.w3.org/2001/XMLSchema#string".to_string()),
315                    language: None,
316                })
317            }
318
319            OxiEncodedTerm::Literal {
320                value,
321                datatype,
322                language,
323            } => {
324                let value_str = interner
325                    .resolve(value)
326                    .ok_or("Literal value hash not found in interner")?;
327
328                let datatype_str = if let Some(dt_hash) = datatype {
329                    Some(
330                        interner
331                            .resolve(dt_hash)
332                            .ok_or("Datatype hash not found in interner")?
333                            .to_string(),
334                    )
335                } else {
336                    None
337                };
338
339                Ok(DecodedTerm::Literal {
340                    value: value_str.to_string(),
341                    datatype: datatype_str,
342                    language: language.clone(),
343                })
344            }
345        }
346    }
347
348    /// Get interner statistics
349    pub fn stats(&self) -> InternerStats {
350        self.interner
351            .read()
352            .unwrap_or_else(|poisoned| poisoned.into_inner())
353            .stats()
354    }
355}
356
357impl Default for OptimizedTermEncoder {
358    fn default() -> Self {
359        Self::new()
360    }
361}
362
363/// Decoded term representation for reconstruction
364#[derive(Debug, Clone, PartialEq)]
365pub enum DecodedTerm {
366    DefaultGraph,
367    NamedNode(String),
368    BlankNode(String),
369    Literal {
370        value: String,
371        datatype: Option<String>,
372        language: Option<String>,
373    },
374}
375
376#[cfg(test)]
377mod tests {
378    use super::*;
379    use crate::model::{Literal, NamedNode};
380
381    #[test]
382    fn test_string_interner() {
383        let mut interner = StringInterner::new();
384
385        let hash1 = interner.intern("http://example.org/test");
386        let hash2 = interner.intern("http://example.org/test"); // Same string
387        let hash3 = interner.intern("http://example.org/other");
388
389        assert_eq!(hash1, hash2); // Same hash for same string
390        assert_ne!(hash1, hash3); // Different hash for different string
391
392        assert_eq!(interner.resolve(&hash1), Some("http://example.org/test"));
393        assert_eq!(interner.resolve(&hash3), Some("http://example.org/other"));
394
395        let stats = interner.stats();
396        assert_eq!(stats.total_strings, 2); // Only 2 unique strings
397        assert_eq!(stats.deduplication_saves, 1); // 1 deduplication
398    }
399
400    #[test]
401    fn test_optimized_term_encoder_survives_lock_poisoning(
402    ) -> Result<(), Box<dyn std::error::Error>> {
403        // Regression test: a panic while holding the interner lock from
404        // another thread must not permanently disable this encoder -
405        // encode/decode/stats should recover via into_inner() rather than
406        // panicking on `.expect()`.
407        let encoder = std::sync::Arc::new(OptimizedTermEncoder::new());
408
409        let poisoning_encoder = encoder.clone();
410        let handle = std::thread::spawn(move || {
411            let _guard = poisoning_encoder.interner.write().unwrap();
412            panic!("intentionally poison the interner lock");
413        });
414        let _ = handle.join(); // the panic poisons the lock; ignore the JoinError
415
416        let node = NamedNode::new("http://example.org/after-poison")?;
417        let encoded = encoder.encode_named_node(&node);
418        match encoder.decode_term(&encoded)? {
419            DecodedTerm::NamedNode(iri) => assert_eq!(iri, "http://example.org/after-poison"),
420            other => panic!("Expected named node, got {other:?}"),
421        }
422        let stats = encoder.stats();
423        assert!(stats.total_strings >= 1);
424        Ok(())
425    }
426
427    #[test]
428    fn test_optimized_encoding() -> Result<(), Box<dyn std::error::Error>> {
429        let encoder = OptimizedTermEncoder::new();
430
431        // Test named node encoding
432        let named_node = NamedNode::new("http://example.org/test")?;
433        let encoded = encoder.encode_named_node(&named_node);
434
435        match encoder.decode_term(&encoded)? {
436            DecodedTerm::NamedNode(iri) => {
437                assert_eq!(iri, "http://example.org/test");
438            }
439            _ => panic!("Expected named node"),
440        }
441
442        // Test optimized integer literal
443        let int_literal = Literal::new_typed_literal(
444            "42",
445            NamedNode::new("http://www.w3.org/2001/XMLSchema#integer")?,
446        );
447        let encoded = encoder.encode_literal(&int_literal);
448
449        assert!(matches!(encoded, OxiEncodedTerm::IntegerLiteral(42)));
450
451        // Test optimized boolean literal
452        let bool_literal = Literal::new_typed_literal(
453            "true",
454            NamedNode::new("http://www.w3.org/2001/XMLSchema#boolean")?,
455        );
456        let encoded = encoder.encode_literal(&bool_literal);
457
458        assert!(matches!(encoded, OxiEncodedTerm::BooleanLiteral(true)));
459
460        Ok(())
461    }
462
463    #[test]
464    fn test_hash_consistency() {
465        let hash1 = OxiStrHash::new("test string");
466        let hash2 = OxiStrHash::new("test string");
467        let hash3 = OxiStrHash::new("different string");
468
469        assert_eq!(hash1, hash2);
470        assert_ne!(hash1, hash3);
471
472        // Test byte conversion
473        let bytes = hash1.to_be_bytes();
474        let reconstructed = OxiStrHash::from_be_bytes(bytes);
475        assert_eq!(hash1, reconstructed);
476    }
477
478    #[test]
479    fn test_edge_cases_empty_string() {
480        let mut interner = StringInterner::new();
481
482        // Test empty string handling
483        let empty_hash = interner.intern("");
484        assert_eq!(interner.resolve(&empty_hash), Some(""));
485
486        // Test multiple empty strings (should deduplicate)
487        let empty_hash2 = interner.intern("");
488        assert_eq!(empty_hash, empty_hash2);
489
490        let stats = interner.stats();
491        assert_eq!(stats.total_strings, 1);
492        assert_eq!(stats.deduplication_saves, 1);
493    }
494
495    #[test]
496    fn test_edge_cases_unicode_strings() {
497        let mut interner = StringInterner::new();
498
499        // Test Unicode strings
500        let unicode_test_cases = [
501            "Hello, 世界!",
502            "Ħello, мир!",
503            "🌍🚀✨",
504            "नमस्ते",
505            "مرحبا",
506            "\u{1F4A9}\u{200D}\u{1F4BB}", // Complex emoji sequence
507        ];
508
509        for test_case in &unicode_test_cases {
510            let hash = interner.intern(test_case);
511            assert_eq!(interner.resolve(&hash), Some(*test_case));
512        }
513    }
514
515    #[test]
516    fn test_edge_cases_large_strings() {
517        let mut interner = StringInterner::new();
518
519        // Test very large strings
520        let large_string = "x".repeat(1_000_000); // 1MB string
521        let hash = interner.intern(&large_string);
522        assert_eq!(interner.resolve(&hash), Some(large_string.as_str()));
523
524        // Test deduplication of large strings
525        let hash2 = interner.intern(&large_string);
526        assert_eq!(hash, hash2);
527
528        let stats = interner.stats();
529        assert_eq!(stats.deduplication_saves, 1);
530    }
531
532    #[test]
533    fn test_error_conditions_invalid_hashes() {
534        let interner = StringInterner::new();
535
536        // Test resolving non-existent hash
537        let fake_hash = OxiStrHash::from_be_bytes([0xFF; 16]);
538        assert_eq!(interner.resolve(&fake_hash), None);
539    }
540
541    #[test]
542    fn test_error_conditions_decode_failures() -> Result<(), Box<dyn std::error::Error>> {
543        let encoder = OptimizedTermEncoder::new();
544
545        // Create an encoded term with a hash that doesn't exist in the interner
546        let fake_hash = OxiStrHash::from_be_bytes([0xFF; 16]);
547        let encoded = OxiEncodedTerm::NamedNode { iri: fake_hash };
548
549        // This should fail when trying to decode
550        assert!(encoder.decode_term(&encoded).is_err());
551
552        Ok(())
553    }
554
555    #[test]
556    fn test_numeric_literal_edge_cases() -> Result<(), Box<dyn std::error::Error>> {
557        let encoder = OptimizedTermEncoder::new();
558
559        // Test integer boundary values
560        let max_int = Literal::new_typed_literal(
561            i64::MAX.to_string(),
562            NamedNode::new("http://www.w3.org/2001/XMLSchema#integer")?,
563        );
564        let encoded = encoder.encode_literal(&max_int);
565        assert!(matches!(encoded, OxiEncodedTerm::IntegerLiteral(i64::MAX)));
566
567        let min_int = Literal::new_typed_literal(
568            i64::MIN.to_string(),
569            NamedNode::new("http://www.w3.org/2001/XMLSchema#integer")?,
570        );
571        let encoded = encoder.encode_literal(&min_int);
572        assert!(matches!(encoded, OxiEncodedTerm::IntegerLiteral(i64::MIN)));
573
574        // Test float special values
575        let nan_float = Literal::new_typed_literal(
576            "NaN",
577            NamedNode::new("http://www.w3.org/2001/XMLSchema#float")?,
578        );
579        let encoded = encoder.encode_literal(&nan_float);
580        if let OxiEncodedTerm::FloatLiteral(val) = encoded {
581            assert!(val.is_nan());
582        } else {
583            panic!("Expected FloatLiteral");
584        }
585
586        let inf_float = Literal::new_typed_literal(
587            "INF",
588            NamedNode::new("http://www.w3.org/2001/XMLSchema#float")?,
589        );
590        let encoded = encoder.encode_literal(&inf_float);
591        if let OxiEncodedTerm::FloatLiteral(val) = encoded {
592            assert!(val.is_infinite() && val.is_sign_positive());
593        } else {
594            panic!("Expected FloatLiteral");
595        }
596
597        Ok(())
598    }
599
600    #[test]
601    fn test_invalid_numeric_literals() -> Result<(), Box<dyn std::error::Error>> {
602        let encoder = OptimizedTermEncoder::new();
603
604        // Test invalid integer (should fall back to general literal encoding)
605        let invalid_int = Literal::new_typed_literal(
606            "not_a_number",
607            NamedNode::new("http://www.w3.org/2001/XMLSchema#integer")?,
608        );
609        let encoded = encoder.encode_literal(&invalid_int);
610        assert!(matches!(encoded, OxiEncodedTerm::Literal { .. }));
611
612        // Test invalid float (should fall back to general literal encoding)
613        let invalid_float = Literal::new_typed_literal(
614            "not_a_float",
615            NamedNode::new("http://www.w3.org/2001/XMLSchema#float")?,
616        );
617        let encoded = encoder.encode_literal(&invalid_float);
618        assert!(matches!(encoded, OxiEncodedTerm::Literal { .. }));
619
620        Ok(())
621    }
622
623    #[test]
624    fn test_memory_efficiency() {
625        let mut interner = StringInterner::new();
626
627        // Intern many duplicate strings to test memory efficiency
628        let test_string = "http://www.w3.org/1999/02/22-rdf-syntax-ns#type";
629        let num_duplicates = 10000;
630
631        for _ in 0..num_duplicates {
632            interner.intern(test_string);
633        }
634
635        let stats = interner.stats();
636        assert_eq!(stats.total_strings, 1); // Only one unique string
637        assert_eq!(stats.deduplication_saves, num_duplicates - 1);
638
639        // Memory usage should be just the size of one string
640        assert_eq!(stats.memory_usage, test_string.len());
641    }
642
643    #[test]
644    fn test_concurrent_safety_simulation() {
645        use std::sync::Arc;
646        use std::thread;
647
648        let encoder = Arc::new(OptimizedTermEncoder::new());
649        let test_strings = vec![
650            "http://example.org/test1",
651            "http://example.org/test2",
652            "http://example.org/test3",
653        ];
654
655        let handles: Vec<_> = test_strings
656            .into_iter()
657            .enumerate()
658            .map(|(i, s)| {
659                let encoder = Arc::clone(&encoder);
660                let s = s.to_string();
661                thread::spawn(move || {
662                    // Simulate concurrent access
663                    let named_node = NamedNode::new(&s).expect("valid IRI");
664                    let encoded = encoder.encode_named_node(&named_node);
665                    (i, encoded)
666                })
667            })
668            .collect();
669
670        // Wait for all threads and collect results
671        let results: Vec<_> = handles
672            .into_iter()
673            .map(|h| h.join().expect("thread should not panic"))
674            .collect();
675        assert_eq!(results.len(), 3);
676
677        // Verify all encodings are valid
678        for (_, encoded) in results {
679            assert!(matches!(encoded, OxiEncodedTerm::NamedNode { .. }));
680        }
681    }
682}
oxirs_core/model/optimized_terms.rs

oxirs_core/model/
optimized_terms.rs
