Skip to main content

sheetkit_core/
sst.rs

1//! Runtime shared string table.
2//!
3//! The [`SharedStringTable`] provides an efficient in-memory index for looking
4//! up and inserting shared strings. It bridges the gap between the XML-level
5//! [`sheetkit_xml::shared_strings::Sst`] and the high-level cell API.
6
7use std::collections::HashMap;
8use std::sync::Arc;
9
10use sheetkit_xml::shared_strings::{Si, Sst, T};
11
12use crate::rich_text::{xml_to_run, RichTextRun};
13
14/// Runtime shared string table for efficient string lookup and insertion.
15///
16/// Maintains both an ordered list of strings (for index-based lookup) and a
17/// reverse hash map (for deduplication when inserting). Uses `Arc<str>` so that
18/// both collections share the same string allocation. Original [`Si`] items
19/// loaded from file are preserved so that `to_sst()` can reuse them without
20/// cloning the string data a second time.
21#[derive(Debug)]
22pub struct SharedStringTable {
23    read_data: Arc<SharedStringReadData>,
24    /// Dedup index for plain-text entries (no rich-text runs).
25    index_map: HashMap<Arc<str>, usize>,
26    /// Dedup index for rich-text entries, keyed on a serialization of the
27    /// full `Si` (text and run formatting) so that a rich entry never
28    /// collides with a plain entry or with differently formatted runs.
29    rich_index_map: HashMap<String, usize>,
30}
31
32#[derive(Debug, Clone)]
33struct SharedStringReadData {
34    strings: Vec<Arc<str>>,
35    /// Original or constructed Si items, parallel to `strings`.
36    /// `None` for plain-text items added via `add()` / `add_owned()`.
37    si_items: Vec<Option<Si>>,
38}
39
40impl SharedStringTable {
41    /// Create a new, empty shared string table.
42    pub fn new() -> Self {
43        Self {
44            read_data: Arc::new(SharedStringReadData {
45                strings: Vec::new(),
46                si_items: Vec::new(),
47            }),
48            index_map: HashMap::new(),
49            rich_index_map: HashMap::new(),
50        }
51    }
52
53    /// Build from an XML [`Sst`], taking ownership to avoid cloning items.
54    ///
55    /// Plain-text items consume the `t.value` String directly (zero-copy into
56    /// `Arc<str>`). Rich-text items concatenate direct text and all run texts.
57    /// Pre-sizes internal containers.
58    pub fn from_sst(sst: Sst) -> Self {
59        let cap = sst.items.len();
60        let mut strings = Vec::with_capacity(cap);
61        let mut index_map = HashMap::with_capacity(cap);
62        let mut rich_index_map = HashMap::new();
63        let mut si_items: Vec<Option<Si>> = Vec::with_capacity(cap);
64
65        for mut si in sst.items {
66            let is_rich = !si.r.is_empty();
67            let has_space_attr = si.t.as_ref().is_some_and(|t| t.xml_space.is_some());
68            let preserve_si = is_rich || has_space_attr;
69
70            let text: Arc<str> = if preserve_si {
71                // Rich text or space-preserved: extract text without consuming
72                // the Si, since we need to store it.
73                si_to_string(&si).into()
74            } else if let Some(ref mut t) = si.t {
75                // Plain text: take ownership of the string to avoid cloning.
76                std::mem::take(&mut t.value).into()
77            } else {
78                // Empty item.
79                Arc::from("")
80            };
81
82            let idx = strings.len();
83            if is_rich {
84                rich_index_map.entry(rich_key(&si)).or_insert(idx);
85            } else {
86                index_map.entry(Arc::clone(&text)).or_insert(idx);
87            }
88            if preserve_si {
89                si_items.push(Some(si));
90            } else {
91                si_items.push(None);
92            }
93            strings.push(text);
94        }
95
96        Self {
97            read_data: Arc::new(SharedStringReadData { strings, si_items }),
98            index_map,
99            rich_index_map,
100        }
101    }
102
103    /// Convert back to an XML [`Sst`] struct for serialization.
104    ///
105    /// Reuses stored [`Si`] items for entries loaded from file. Builds new
106    /// `Si` items only for strings added at runtime.
107    pub fn to_sst(&self) -> Sst {
108        let items: Vec<Si> = self
109            .read_data
110            .strings
111            .iter()
112            .enumerate()
113            .map(|(idx, s)| {
114                if let Some(ref si) = self.read_data.si_items[idx] {
115                    si.clone()
116                } else {
117                    Si {
118                        t: Some(T {
119                            xml_space: if needs_space_preserve(s) {
120                                Some("preserve".to_string())
121                            } else {
122                                None
123                            },
124                            value: s.to_string(),
125                        }),
126                        r: vec![],
127                    }
128                }
129            })
130            .collect();
131
132        let len = items.len() as u32;
133        Sst {
134            xmlns: sheetkit_xml::namespaces::SPREADSHEET_ML.to_string(),
135            count: Some(len),
136            unique_count: Some(len),
137            items,
138        }
139    }
140
141    /// Get a string by its index.
142    pub fn get(&self, index: usize) -> Option<&str> {
143        self.read_data.strings.get(index).map(|s| &**s)
144    }
145
146    /// Add a string by reference, returning its index.
147    ///
148    /// If the string already exists, the existing index is returned (dedup).
149    pub fn add(&mut self, s: &str) -> usize {
150        if let Some(&idx) = self.index_map.get(s) {
151            return idx;
152        }
153        let idx = self.read_data.strings.len();
154        let rc: Arc<str> = s.into();
155        let data = Arc::make_mut(&mut self.read_data);
156        data.strings.push(Arc::clone(&rc));
157        self.index_map.insert(rc, idx);
158        data.si_items.push(None);
159        idx
160    }
161
162    /// Add a string by value, returning its index.
163    ///
164    /// Avoids one allocation compared to `add()` when the caller already
165    /// owns a `String`.
166    pub fn add_owned(&mut self, s: String) -> usize {
167        if let Some(&idx) = self.index_map.get(s.as_str()) {
168            return idx;
169        }
170        let idx = self.read_data.strings.len();
171        let rc: Arc<str> = s.into();
172        self.index_map.insert(Arc::clone(&rc), idx);
173        let data = Arc::make_mut(&mut self.read_data);
174        data.strings.push(rc);
175        data.si_items.push(None);
176        idx
177    }
178
179    /// Add rich text runs, returning the SST index.
180    ///
181    /// Deduplication considers both the text and the run formatting, so a
182    /// rich entry is never shared with a plain entry of the same text.
183    pub fn add_rich_text(&mut self, runs: &[RichTextRun]) -> usize {
184        let si = crate::rich_text::runs_to_si(runs);
185        if si.r.is_empty() {
186            let plain: String = runs.iter().map(|r| r.text.as_str()).collect();
187            return self.add_owned(plain);
188        }
189        let key = rich_key(&si);
190        if let Some(&idx) = self.rich_index_map.get(&key) {
191            return idx;
192        }
193        let idx = self.read_data.strings.len();
194        let rc: Arc<str> = si_to_string(&si).into();
195        self.rich_index_map.insert(key, idx);
196        let data = Arc::make_mut(&mut self.read_data);
197        data.strings.push(rc);
198        data.si_items.push(Some(si));
199        idx
200    }
201
202    /// Get rich text runs for an SST entry, if it has formatting.
203    ///
204    /// Returns `None` for plain-text entries.
205    pub fn get_rich_text(&self, index: usize) -> Option<Vec<RichTextRun>> {
206        self.read_data
207            .si_items
208            .get(index)
209            .and_then(|opt| opt.as_ref())
210            .filter(|si| !si.r.is_empty())
211            .map(|si| si.r.iter().map(xml_to_run).collect())
212    }
213
214    /// Number of unique strings.
215    pub fn len(&self) -> usize {
216        self.read_data.strings.len()
217    }
218
219    /// Returns `true` if the table contains no strings.
220    pub fn is_empty(&self) -> bool {
221        self.read_data.strings.is_empty()
222    }
223
224    /// Create a read-only clone suitable for use by an owned stream reader.
225    ///
226    /// Shares the immutable lookup data in O(1) and omits the reverse
227    /// `index_map`, which a reader never needs. Later workbook mutation uses
228    /// copy-on-write so the snapshot remains stable.
229    pub(crate) fn clone_for_read(&self) -> Self {
230        Self {
231            read_data: Arc::clone(&self.read_data),
232            index_map: HashMap::new(),
233            rich_index_map: HashMap::new(),
234        }
235    }
236
237    #[cfg(test)]
238    fn shares_read_storage_with(&self, other: &Self) -> bool {
239        Arc::ptr_eq(&self.read_data, &other.read_data)
240    }
241}
242
243impl Default for SharedStringTable {
244    fn default() -> Self {
245        Self::new()
246    }
247}
248
249/// Build the dedup key for a rich-text item from its full structure.
250fn rich_key(si: &Si) -> String {
251    format!("{si:?}")
252}
253
254/// Check whether a string needs `xml:space="preserve"`.
255fn needs_space_preserve(s: &str) -> bool {
256    s.starts_with(' ')
257        || s.ends_with(' ')
258        || s.contains("  ")
259        || s.contains('\n')
260        || s.contains('\t')
261}
262
263/// Extract the plain-text content of a shared string item.
264///
265/// Concatenate the direct text, when present, with all rich-text runs.
266fn si_to_string(si: &Si) -> String {
267    let mut text =
268        si.t.as_ref()
269            .map(|value| value.value.clone())
270            .unwrap_or_default();
271    for run in &si.r {
272        text.push_str(&run.t.value);
273    }
274    text
275}
276
277#[cfg(test)]
278mod tests {
279    use super::*;
280    use sheetkit_xml::shared_strings::{Si, Sst, R, T};
281
282    #[test]
283    fn test_sst_new_is_empty() {
284        let table = SharedStringTable::new();
285        assert!(table.is_empty());
286        assert_eq!(table.len(), 0);
287    }
288
289    #[test]
290    fn test_sst_add_returns_index() {
291        let mut table = SharedStringTable::new();
292        assert_eq!(table.add("hello"), 0);
293        assert_eq!(table.add("world"), 1);
294        assert_eq!(table.add("foo"), 2);
295        assert_eq!(table.len(), 3);
296    }
297
298    #[test]
299    fn read_snapshot_is_o1_and_copy_on_write() {
300        let mut table = SharedStringTable::new();
301        table.add("original");
302        let snapshot = table.clone_for_read();
303        assert!(table.shares_read_storage_with(&snapshot));
304
305        table.add("later");
306        assert!(!table.shares_read_storage_with(&snapshot));
307        assert_eq!(snapshot.len(), 1);
308        assert_eq!(snapshot.get(0), Some("original"));
309        assert_eq!(snapshot.get(1), None);
310    }
311
312    #[test]
313    fn test_sst_add_deduplicates() {
314        let mut table = SharedStringTable::new();
315        assert_eq!(table.add("hello"), 0);
316        assert_eq!(table.add("world"), 1);
317        assert_eq!(table.add("hello"), 0); // duplicate -> same index
318        assert_eq!(table.len(), 2); // only 2 unique strings
319    }
320
321    #[test]
322    fn test_sst_add_owned() {
323        let mut table = SharedStringTable::new();
324        assert_eq!(table.add_owned("hello".to_string()), 0);
325        assert_eq!(table.add_owned("world".to_string()), 1);
326        assert_eq!(table.add_owned("hello".to_string()), 0); // dedup
327        assert_eq!(table.len(), 2);
328        assert_eq!(table.get(0), Some("hello"));
329        assert_eq!(table.get(1), Some("world"));
330    }
331
332    #[test]
333    fn test_sst_get() {
334        let mut table = SharedStringTable::new();
335        table.add("alpha");
336        table.add("beta");
337
338        assert_eq!(table.get(0), Some("alpha"));
339        assert_eq!(table.get(1), Some("beta"));
340        assert_eq!(table.get(2), None);
341    }
342
343    #[test]
344    fn test_sst_from_xml_and_back() {
345        let xml_sst = Sst {
346            xmlns: sheetkit_xml::namespaces::SPREADSHEET_ML.to_string(),
347            count: Some(3),
348            unique_count: Some(3),
349            items: vec![
350                Si {
351                    t: Some(T {
352                        xml_space: None,
353                        value: "Name".to_string(),
354                    }),
355                    r: vec![],
356                },
357                Si {
358                    t: Some(T {
359                        xml_space: None,
360                        value: "Age".to_string(),
361                    }),
362                    r: vec![],
363                },
364                Si {
365                    t: Some(T {
366                        xml_space: None,
367                        value: "City".to_string(),
368                    }),
369                    r: vec![],
370                },
371            ],
372        };
373
374        let table = SharedStringTable::from_sst(xml_sst);
375        assert_eq!(table.len(), 3);
376        assert_eq!(table.get(0), Some("Name"));
377        assert_eq!(table.get(1), Some("Age"));
378        assert_eq!(table.get(2), Some("City"));
379
380        // Convert back
381        let back = table.to_sst();
382        assert_eq!(back.items.len(), 3);
383        assert_eq!(back.items[0].t.as_ref().unwrap().value, "Name");
384        assert_eq!(back.items[1].t.as_ref().unwrap().value, "Age");
385        assert_eq!(back.items[2].t.as_ref().unwrap().value, "City");
386        assert_eq!(back.count, Some(3));
387        assert_eq!(back.unique_count, Some(3));
388    }
389
390    #[test]
391    fn test_sst_from_xml_rich_text() {
392        let xml_sst = Sst {
393            xmlns: sheetkit_xml::namespaces::SPREADSHEET_ML.to_string(),
394            count: Some(1),
395            unique_count: Some(1),
396            items: vec![Si {
397                t: None,
398                r: vec![
399                    R {
400                        r_pr: None,
401                        t: T {
402                            xml_space: None,
403                            value: "Bold".to_string(),
404                        },
405                    },
406                    R {
407                        r_pr: None,
408                        t: T {
409                            xml_space: None,
410                            value: " Normal".to_string(),
411                        },
412                    },
413                ],
414            }],
415        };
416
417        let table = SharedStringTable::from_sst(xml_sst);
418        assert_eq!(table.len(), 1);
419        assert_eq!(table.get(0), Some("Bold Normal"));
420    }
421
422    #[test]
423    fn test_sst_default() {
424        let table = SharedStringTable::default();
425        assert!(table.is_empty());
426    }
427
428    #[test]
429    fn test_add_rich_text() {
430        let mut table = SharedStringTable::new();
431        let runs = vec![
432            RichTextRun {
433                text: "Hello ".to_string(),
434                font: None,
435                size: None,
436                bold: true,
437                italic: false,
438                color: None,
439            },
440            RichTextRun {
441                text: "World".to_string(),
442                font: None,
443                size: None,
444                bold: false,
445                italic: false,
446                color: None,
447            },
448        ];
449        let idx = table.add_rich_text(&runs);
450        assert_eq!(idx, 0);
451        assert_eq!(table.get(0), Some("Hello World"));
452        assert!(table.get_rich_text(0).is_some());
453    }
454
455    fn bold_run(text: &str) -> RichTextRun {
456        RichTextRun {
457            text: text.to_string(),
458            font: None,
459            size: None,
460            bold: true,
461            italic: false,
462            color: None,
463        }
464    }
465
466    #[test]
467    fn plain_then_rich_with_same_text_keep_separate_entries() {
468        let mut table = SharedStringTable::new();
469        let plain = table.add("Hello");
470        let rich = table.add_rich_text(&[bold_run("Hello")]);
471        assert_ne!(plain, rich);
472        assert!(table.get_rich_text(plain).is_none());
473        let runs = table.get_rich_text(rich).unwrap();
474        assert!(runs[0].bold);
475        assert_eq!(table.len(), 2);
476
477        let sst = table.to_sst();
478        assert_eq!(sst.unique_count, Some(2));
479        assert!(sst.items[plain].r.is_empty());
480        assert_eq!(sst.items[rich].r.len(), 1);
481    }
482
483    #[test]
484    fn rich_then_plain_with_same_text_keep_separate_entries() {
485        let mut table = SharedStringTable::new();
486        let rich = table.add_rich_text(&[bold_run("Hello")]);
487        let plain = table.add("Hello");
488        let plain_owned = table.add_owned("Hello".to_string());
489        assert_ne!(plain, rich);
490        assert_eq!(plain, plain_owned);
491        assert!(table.get_rich_text(plain).is_none());
492        assert!(table.get_rich_text(rich).is_some());
493        assert_eq!(table.len(), 2);
494    }
495
496    #[test]
497    fn rich_text_dedupes_on_formatting_not_just_text() {
498        let mut table = SharedStringTable::new();
499        let bold = table.add_rich_text(&[bold_run("Hi")]);
500        let mut italic_run = bold_run("Hi");
501        italic_run.bold = false;
502        italic_run.italic = true;
503        let italic = table.add_rich_text(&[italic_run]);
504        assert_ne!(bold, italic);
505        assert_eq!(table.add_rich_text(&[bold_run("Hi")]), bold);
506        assert_eq!(table.len(), 2);
507    }
508
509    #[test]
510    fn loaded_rich_item_does_not_capture_plain_add() {
511        let xml_sst = Sst {
512            xmlns: sheetkit_xml::namespaces::SPREADSHEET_ML.to_string(),
513            count: Some(1),
514            unique_count: Some(1),
515            items: vec![Si {
516                t: None,
517                r: vec![R {
518                    r_pr: None,
519                    t: T {
520                        xml_space: None,
521                        value: "Hello".to_string(),
522                    },
523                }],
524            }],
525        };
526        let mut table = SharedStringTable::from_sst(xml_sst);
527        let plain = table.add("Hello");
528        assert_eq!(plain, 1);
529        assert!(table.get_rich_text(plain).is_none());
530    }
531
532    #[test]
533    fn test_get_rich_text_none_for_plain() {
534        let mut table = SharedStringTable::new();
535        table.add("plain");
536        assert!(table.get_rich_text(0).is_none());
537    }
538
539    #[test]
540    fn test_rich_text_roundtrip_through_sst() {
541        let xml_sst = Sst {
542            xmlns: sheetkit_xml::namespaces::SPREADSHEET_ML.to_string(),
543            count: Some(1),
544            unique_count: Some(1),
545            items: vec![Si {
546                t: None,
547                r: vec![
548                    R {
549                        r_pr: None,
550                        t: T {
551                            xml_space: None,
552                            value: "Bold".to_string(),
553                        },
554                    },
555                    R {
556                        r_pr: None,
557                        t: T {
558                            xml_space: None,
559                            value: " Normal".to_string(),
560                        },
561                    },
562                ],
563            }],
564        };
565        let table = SharedStringTable::from_sst(xml_sst);
566        let back = table.to_sst();
567        assert!(back.items[0].t.is_none());
568        assert_eq!(back.items[0].r.len(), 2);
569    }
570
571    #[test]
572    fn test_space_preserve_roundtrip() {
573        let xml_sst = Sst {
574            xmlns: sheetkit_xml::namespaces::SPREADSHEET_ML.to_string(),
575            count: Some(1),
576            unique_count: Some(1),
577            items: vec![Si {
578                t: Some(T {
579                    xml_space: Some("preserve".to_string()),
580                    value: " leading space".to_string(),
581                }),
582                r: vec![],
583            }],
584        };
585        let table = SharedStringTable::from_sst(xml_sst);
586        let back = table.to_sst();
587        assert_eq!(
588            back.items[0].t.as_ref().unwrap().xml_space,
589            Some("preserve".to_string())
590        );
591    }
592
593    #[test]
594    fn test_add_owned_then_to_sst() {
595        let mut table = SharedStringTable::new();
596        table.add_owned("test".to_string());
597        let sst = table.to_sst();
598        assert_eq!(sst.items.len(), 1);
599        assert_eq!(sst.items[0].t.as_ref().unwrap().value, "test");
600    }
601
602    #[test]
603    fn test_from_sst_zero_copy_plain_text() {
604        let xml_sst = Sst {
605            xmlns: sheetkit_xml::namespaces::SPREADSHEET_ML.to_string(),
606            count: Some(3),
607            unique_count: Some(3),
608            items: vec![
609                Si {
610                    t: Some(T {
611                        xml_space: None,
612                        value: "Alpha".to_string(),
613                    }),
614                    r: vec![],
615                },
616                Si {
617                    t: Some(T {
618                        xml_space: None,
619                        value: "Beta".to_string(),
620                    }),
621                    r: vec![],
622                },
623                Si {
624                    t: Some(T {
625                        xml_space: None,
626                        value: "Gamma".to_string(),
627                    }),
628                    r: vec![],
629                },
630            ],
631        };
632        let table = SharedStringTable::from_sst(xml_sst);
633        assert_eq!(table.len(), 3);
634        assert_eq!(table.get(0), Some("Alpha"));
635        assert_eq!(table.get(1), Some("Beta"));
636        assert_eq!(table.get(2), Some("Gamma"));
637        let back = table.to_sst();
638        assert_eq!(back.items[0].t.as_ref().unwrap().value, "Alpha");
639        assert_eq!(back.items[1].t.as_ref().unwrap().value, "Beta");
640        assert_eq!(back.items[2].t.as_ref().unwrap().value, "Gamma");
641    }
642
643    #[test]
644    fn test_from_sst_mixed_plain_and_rich_text() {
645        let xml_sst = Sst {
646            xmlns: sheetkit_xml::namespaces::SPREADSHEET_ML.to_string(),
647            count: Some(3),
648            unique_count: Some(3),
649            items: vec![
650                Si {
651                    t: Some(T {
652                        xml_space: None,
653                        value: "Plain".to_string(),
654                    }),
655                    r: vec![],
656                },
657                Si {
658                    t: None,
659                    r: vec![
660                        R {
661                            r_pr: None,
662                            t: T {
663                                xml_space: None,
664                                value: "Rich".to_string(),
665                            },
666                        },
667                        R {
668                            r_pr: None,
669                            t: T {
670                                xml_space: None,
671                                value: " Text".to_string(),
672                            },
673                        },
674                    ],
675                },
676                Si {
677                    t: Some(T {
678                        xml_space: Some("preserve".to_string()),
679                        value: " spaced ".to_string(),
680                    }),
681                    r: vec![],
682                },
683            ],
684        };
685        let table = SharedStringTable::from_sst(xml_sst);
686        assert_eq!(table.len(), 3);
687        assert_eq!(table.get(0), Some("Plain"));
688        assert_eq!(table.get(1), Some("Rich Text"));
689        assert_eq!(table.get(2), Some(" spaced "));
690        assert!(table.get_rich_text(0).is_none());
691        assert!(table.get_rich_text(1).is_some());
692    }
693
694    #[test]
695    fn test_from_sst_empty_items() {
696        let xml_sst = Sst {
697            xmlns: sheetkit_xml::namespaces::SPREADSHEET_ML.to_string(),
698            count: Some(0),
699            unique_count: Some(0),
700            items: vec![],
701        };
702        let table = SharedStringTable::from_sst(xml_sst);
703        assert!(table.is_empty());
704    }
705
706    #[test]
707    fn test_from_sst_preserves_mixed_direct_and_rich_text() {
708        let xml_sst = Sst {
709            xmlns: sheetkit_xml::namespaces::SPREADSHEET_ML.to_string(),
710            count: Some(1),
711            unique_count: Some(1),
712            items: vec![Si {
713                t: Some(T {
714                    xml_space: Some("preserve".to_string()),
715                    value: " direct ".to_string(),
716                }),
717                r: vec![R {
718                    r_pr: None,
719                    t: T {
720                        xml_space: Some("preserve".to_string()),
721                        value: " rich ".to_string(),
722                    },
723                }],
724            }],
725        };
726
727        let table = SharedStringTable::from_sst(xml_sst);
728        assert_eq!(table.get(0), Some(" direct  rich "));
729        let roundtripped = table.to_sst();
730        assert_eq!(roundtripped.items[0].t.as_ref().unwrap().value, " direct ");
731        assert_eq!(roundtripped.items[0].r[0].t.value, " rich ");
732    }
733}