ipfrs_storage/
index_builder.rs

1//! Secondary index over block metadata enabling fast filtered queries.
2//!
3//! [`StorageIndexBuilder`] maintains an in-memory index keyed by CID and
4//! supports rich filter expressions (size range, time range, tags, content
5//! type, logical AND/OR) without scanning the underlying block store.
6
7use std::collections::HashMap;
8
9// ---------------------------------------------------------------------------
10// IndexField
11// ---------------------------------------------------------------------------
12
13/// Dimensions of the secondary index.
14#[derive(Clone, Debug, PartialEq, Eq, Hash)]
15pub enum IndexField {
16    /// Block size in bytes.
17    Size,
18    /// Creation timestamp (Unix seconds).
19    CreatedAt,
20    /// Arbitrary string tag.
21    Tag,
22    /// MIME-style content type.
23    ContentType,
24}
25
26// ---------------------------------------------------------------------------
27// IndexEntry
28// ---------------------------------------------------------------------------
29
30/// A single record stored in the secondary index.
31#[derive(Clone, Debug, PartialEq, Eq)]
32pub struct IndexEntry {
33    /// Content identifier (CID) – used as the primary key.
34    pub cid: String,
35    /// Block size in bytes.
36    pub size_bytes: u64,
37    /// Creation time as Unix epoch seconds.
38    pub created_at_secs: u64,
39    /// Arbitrary string tags attached to this block.
40    pub tags: Vec<String>,
41    /// MIME-style content type (e.g. `"application/octet-stream"`).
42    pub content_type: String,
43}
44
45// ---------------------------------------------------------------------------
46// QueryFilter
47// ---------------------------------------------------------------------------
48
49/// Filter expression for querying the index.
50#[derive(Clone, Debug, PartialEq)]
51pub enum QueryFilter {
52    /// Blocks whose size falls within `[min, max]` (inclusive).
53    SizeRange { min: u64, max: u64 },
54    /// Blocks created strictly after `secs` (i.e. `created_at_secs > secs`).
55    CreatedAfter { secs: u64 },
56    /// Blocks created strictly before `secs` (i.e. `created_at_secs < secs`).
57    CreatedBefore { secs: u64 },
58    /// Blocks that carry the given tag.
59    HasTag { tag: String },
60    /// Blocks whose content type matches `ct` exactly.
61    ContentType { ct: String },
62    /// Both sub-filters must match.
63    And(Box<QueryFilter>, Box<QueryFilter>),
64    /// At least one sub-filter must match.
65    Or(Box<QueryFilter>, Box<QueryFilter>),
66}
67
68// ---------------------------------------------------------------------------
69// IndexStats
70// ---------------------------------------------------------------------------
71
72/// Summary statistics for the index.
73#[derive(Clone, Debug, PartialEq)]
74pub struct IndexStats {
75    /// Total number of entries currently held in the index.
76    pub total_entries: usize,
77    /// Dimensions that are actively indexed.
78    pub indexed_fields: Vec<IndexField>,
79}
80
81impl IndexStats {
82    /// Returns the fraction of entries that are indexed.
83    ///
84    /// Because this implementation always indexes every inserted entry this
85    /// value is always `1.0`.
86    pub fn coverage(&self) -> f64 {
87        1.0
88    }
89}
90
91// ---------------------------------------------------------------------------
92// StorageIndexBuilder
93// ---------------------------------------------------------------------------
94
95/// Builds and maintains a secondary index over block metadata.
96///
97/// # Example
98///
99/// ```rust
100/// use ipfrs_storage::index_builder::{
101///     IndexEntry, QueryFilter, StorageIndexBuilder,
102/// };
103///
104/// let mut idx = StorageIndexBuilder::new();
105/// idx.insert(IndexEntry {
106///     cid: "QmA".into(),
107///     size_bytes: 1024,
108///     created_at_secs: 1_000,
109///     tags: vec!["audio".into()],
110///     content_type: "audio/mpeg".into(),
111/// });
112///
113/// let results = idx.query(&QueryFilter::HasTag { tag: "audio".into() });
114/// assert_eq!(results.len(), 1);
115/// ```
116pub struct StorageIndexBuilder {
117    /// Primary storage: CID → [`IndexEntry`].
118    pub entries: HashMap<String, IndexEntry>,
119}
120
121impl StorageIndexBuilder {
122    /// Creates an empty index.
123    pub fn new() -> Self {
124        Self {
125            entries: HashMap::new(),
126        }
127    }
128
129    /// Inserts (or replaces) an entry keyed by its CID.
130    pub fn insert(&mut self, entry: IndexEntry) {
131        self.entries.insert(entry.cid.clone(), entry);
132    }
133
134    /// Removes the entry with the given CID.
135    ///
136    /// Returns `true` if an entry was present and removed, `false` otherwise.
137    pub fn remove(&mut self, cid: &str) -> bool {
138        self.entries.remove(cid).is_some()
139    }
140
141    /// Returns all entries that satisfy `filter`, sorted by
142    /// `created_at_secs` ascending.
143    pub fn query(&self, filter: &QueryFilter) -> Vec<&IndexEntry> {
144        let mut results: Vec<&IndexEntry> = self
145            .entries
146            .values()
147            .filter(|e| self.matches(e, filter))
148            .collect();
149
150        results.sort_by_key(|e| e.created_at_secs);
151        results
152    }
153
154    /// Replaces the tag list for the entry identified by `cid`.
155    ///
156    /// Returns `true` if the entry was found and updated, `false` otherwise.
157    pub fn update_tags(&mut self, cid: &str, tags: Vec<String>) -> bool {
158        match self.entries.get_mut(cid) {
159            Some(entry) => {
160                entry.tags = tags;
161                true
162            }
163            None => false,
164        }
165    }
166
167    /// Returns summary statistics for the current index state.
168    pub fn stats(&self) -> IndexStats {
169        IndexStats {
170            total_entries: self.entries.len(),
171            indexed_fields: vec![
172                IndexField::Size,
173                IndexField::CreatedAt,
174                IndexField::Tag,
175                IndexField::ContentType,
176            ],
177        }
178    }
179
180    // -----------------------------------------------------------------------
181    // Private helpers
182    // -----------------------------------------------------------------------
183
184    /// Recursively evaluates `filter` against a single `entry`.
185    fn matches(&self, entry: &IndexEntry, filter: &QueryFilter) -> bool {
186        match filter {
187            QueryFilter::SizeRange { min, max } => {
188                entry.size_bytes >= *min && entry.size_bytes <= *max
189            }
190            QueryFilter::CreatedAfter { secs } => entry.created_at_secs > *secs,
191            QueryFilter::CreatedBefore { secs } => entry.created_at_secs < *secs,
192            QueryFilter::HasTag { tag } => entry.tags.iter().any(|t| t == tag),
193            QueryFilter::ContentType { ct } => &entry.content_type == ct,
194            QueryFilter::And(left, right) => {
195                self.matches(entry, left) && self.matches(entry, right)
196            }
197            QueryFilter::Or(left, right) => self.matches(entry, left) || self.matches(entry, right),
198        }
199    }
200}
201
202impl Default for StorageIndexBuilder {
203    fn default() -> Self {
204        Self::new()
205    }
206}
207
208// ---------------------------------------------------------------------------
209// Tests
210// ---------------------------------------------------------------------------
211
212#[cfg(test)]
213mod tests {
214    use super::*;
215
216    fn make_entry(
217        cid: &str,
218        size_bytes: u64,
219        created_at_secs: u64,
220        tags: &[&str],
221        content_type: &str,
222    ) -> IndexEntry {
223        IndexEntry {
224            cid: cid.to_owned(),
225            size_bytes,
226            created_at_secs,
227            tags: tags.iter().map(|s| s.to_string()).collect(),
228            content_type: content_type.to_owned(),
229        }
230    }
231
232    fn populated_index() -> StorageIndexBuilder {
233        let mut idx = StorageIndexBuilder::new();
234        idx.insert(make_entry(
235            "QmA",
236            100,
237            1_000,
238            &["image", "png"],
239            "image/png",
240        ));
241        idx.insert(make_entry("QmB", 500, 2_000, &["video"], "video/mp4"));
242        idx.insert(make_entry(
243            "QmC",
244            1_000,
245            3_000,
246            &["audio", "mp3"],
247            "audio/mpeg",
248        ));
249        idx.insert(make_entry(
250            "QmD",
251            50,
252            4_000,
253            &["image", "jpeg"],
254            "image/jpeg",
255        ));
256        idx.insert(make_entry(
257            "QmE",
258            2_000,
259            5_000,
260            &[],
261            "application/octet-stream",
262        ));
263        idx
264    }
265
266    // -----------------------------------------------------------------------
267    // 1. insert + query by SizeRange
268    // -----------------------------------------------------------------------
269    #[test]
270    fn test_insert_and_query_size_range() {
271        let idx = populated_index();
272        let results = idx.query(&QueryFilter::SizeRange {
273            min: 100,
274            max: 1_000,
275        });
276        let cids: Vec<&str> = results.iter().map(|e| e.cid.as_str()).collect();
277        assert!(cids.contains(&"QmA"), "QmA (100) should be in [100, 1000]");
278        assert!(cids.contains(&"QmB"), "QmB (500) should be in [100, 1000]");
279        assert!(cids.contains(&"QmC"), "QmC (1000) should be in [100, 1000]");
280        assert!(
281            !cids.contains(&"QmD"),
282            "QmD (50) should not be in [100, 1000]"
283        );
284        assert!(
285            !cids.contains(&"QmE"),
286            "QmE (2000) should not be in [100, 1000]"
287        );
288    }
289
290    // -----------------------------------------------------------------------
291    // 2. SizeRange inclusive on both bounds
292    // -----------------------------------------------------------------------
293    #[test]
294    fn test_size_range_inclusive_bounds() {
295        let idx = populated_index();
296        // Exact lower bound
297        let lower = idx.query(&QueryFilter::SizeRange { min: 50, max: 50 });
298        assert_eq!(lower.len(), 1);
299        assert_eq!(lower[0].cid, "QmD");
300
301        // Exact upper bound
302        let upper = idx.query(&QueryFilter::SizeRange {
303            min: 2_000,
304            max: 2_000,
305        });
306        assert_eq!(upper.len(), 1);
307        assert_eq!(upper[0].cid, "QmE");
308    }
309
310    // -----------------------------------------------------------------------
311    // 3. query by CreatedAfter
312    // -----------------------------------------------------------------------
313    #[test]
314    fn test_query_created_after() {
315        let idx = populated_index();
316        let results = idx.query(&QueryFilter::CreatedAfter { secs: 3_000 });
317        let cids: Vec<&str> = results.iter().map(|e| e.cid.as_str()).collect();
318        assert!(!cids.contains(&"QmA"));
319        assert!(!cids.contains(&"QmB"));
320        assert!(!cids.contains(&"QmC"), "3000 is not > 3000");
321        assert!(cids.contains(&"QmD"));
322        assert!(cids.contains(&"QmE"));
323    }
324
325    // -----------------------------------------------------------------------
326    // 4. query by CreatedBefore
327    // -----------------------------------------------------------------------
328    #[test]
329    fn test_query_created_before() {
330        let idx = populated_index();
331        let results = idx.query(&QueryFilter::CreatedBefore { secs: 3_000 });
332        let cids: Vec<&str> = results.iter().map(|e| e.cid.as_str()).collect();
333        assert!(cids.contains(&"QmA"));
334        assert!(cids.contains(&"QmB"));
335        assert!(!cids.contains(&"QmC"), "3000 is not < 3000");
336        assert!(!cids.contains(&"QmD"));
337        assert!(!cids.contains(&"QmE"));
338    }
339
340    // -----------------------------------------------------------------------
341    // 5. query by HasTag
342    // -----------------------------------------------------------------------
343    #[test]
344    fn test_query_has_tag() {
345        let idx = populated_index();
346        let results = idx.query(&QueryFilter::HasTag {
347            tag: "image".into(),
348        });
349        let cids: Vec<&str> = results.iter().map(|e| e.cid.as_str()).collect();
350        assert!(cids.contains(&"QmA"));
351        assert!(cids.contains(&"QmD"));
352        assert!(!cids.contains(&"QmB"));
353        assert!(!cids.contains(&"QmC"));
354        assert!(!cids.contains(&"QmE"));
355    }
356
357    // -----------------------------------------------------------------------
358    // 6. query by ContentType
359    // -----------------------------------------------------------------------
360    #[test]
361    fn test_query_content_type() {
362        let idx = populated_index();
363        let results = idx.query(&QueryFilter::ContentType {
364            ct: "video/mp4".into(),
365        });
366        assert_eq!(results.len(), 1);
367        assert_eq!(results[0].cid, "QmB");
368    }
369
370    // -----------------------------------------------------------------------
371    // 7. And combines filters
372    // -----------------------------------------------------------------------
373    #[test]
374    fn test_and_filter() {
375        let idx = populated_index();
376        // image tag AND size in [0, 100]: QmA (image, 100) and QmD (image, 50) both qualify
377        let filter = QueryFilter::And(
378            Box::new(QueryFilter::HasTag {
379                tag: "image".into(),
380            }),
381            Box::new(QueryFilter::SizeRange { min: 0, max: 100 }),
382        );
383        let results = idx.query(&filter);
384        let cids: Vec<&str> = results.iter().map(|e| e.cid.as_str()).collect();
385        assert!(
386            cids.contains(&"QmA"),
387            "QmA has image tag and size=100 which is within [0,100]"
388        );
389        assert!(
390            cids.contains(&"QmD"),
391            "QmD has image tag and size=50 which is within [0,100]"
392        );
393        assert!(!cids.contains(&"QmB"), "QmB has no image tag");
394        assert!(!cids.contains(&"QmC"), "QmC has no image tag");
395        assert_eq!(results.len(), 2);
396    }
397
398    // -----------------------------------------------------------------------
399    // 8. And filter – no result when both conditions cannot be met together
400    // -----------------------------------------------------------------------
401    #[test]
402    fn test_and_filter_no_match() {
403        let idx = populated_index();
404        // video AND image tag – no entry has both
405        let filter = QueryFilter::And(
406            Box::new(QueryFilter::HasTag {
407                tag: "video".into(),
408            }),
409            Box::new(QueryFilter::HasTag {
410                tag: "image".into(),
411            }),
412        );
413        let results = idx.query(&filter);
414        assert!(results.is_empty());
415    }
416
417    // -----------------------------------------------------------------------
418    // 9. Or combines filters
419    // -----------------------------------------------------------------------
420    #[test]
421    fn test_or_filter() {
422        let idx = populated_index();
423        // audio OR video
424        let filter = QueryFilter::Or(
425            Box::new(QueryFilter::HasTag {
426                tag: "audio".into(),
427            }),
428            Box::new(QueryFilter::HasTag {
429                tag: "video".into(),
430            }),
431        );
432        let results = idx.query(&filter);
433        let cids: Vec<&str> = results.iter().map(|e| e.cid.as_str()).collect();
434        assert!(cids.contains(&"QmB"));
435        assert!(cids.contains(&"QmC"));
436        assert!(!cids.contains(&"QmA"));
437        assert!(!cids.contains(&"QmD"));
438        assert!(!cids.contains(&"QmE"));
439    }
440
441    // -----------------------------------------------------------------------
442    // 10. Or filter – returns entry matching either branch
443    // -----------------------------------------------------------------------
444    #[test]
445    fn test_or_filter_matches_both_branches() {
446        let idx = populated_index();
447        let filter = QueryFilter::Or(
448            Box::new(QueryFilter::ContentType {
449                ct: "image/png".into(),
450            }),
451            Box::new(QueryFilter::ContentType {
452                ct: "image/jpeg".into(),
453            }),
454        );
455        let results = idx.query(&filter);
456        assert_eq!(results.len(), 2);
457    }
458
459    // -----------------------------------------------------------------------
460    // 11. remove
461    // -----------------------------------------------------------------------
462    #[test]
463    fn test_remove_existing_entry() {
464        let mut idx = populated_index();
465        let removed = idx.remove("QmB");
466        assert!(removed, "remove should return true for existing CID");
467        let results = idx.query(&QueryFilter::ContentType {
468            ct: "video/mp4".into(),
469        });
470        assert!(
471            results.is_empty(),
472            "QmB should no longer appear after removal"
473        );
474    }
475
476    #[test]
477    fn test_remove_nonexistent_entry() {
478        let mut idx = populated_index();
479        let removed = idx.remove("QmDoesNotExist");
480        assert!(!removed, "remove should return false for unknown CID");
481    }
482
483    // -----------------------------------------------------------------------
484    // 12. update_tags
485    // -----------------------------------------------------------------------
486    #[test]
487    fn test_update_tags_existing() {
488        let mut idx = populated_index();
489        let updated = idx.update_tags("QmE", vec!["new-tag".into(), "another".into()]);
490        assert!(updated);
491
492        let results = idx.query(&QueryFilter::HasTag {
493            tag: "new-tag".into(),
494        });
495        assert_eq!(results.len(), 1);
496        assert_eq!(results[0].cid, "QmE");
497    }
498
499    #[test]
500    fn test_update_tags_nonexistent() {
501        let mut idx = populated_index();
502        let updated = idx.update_tags("QmNone", vec!["x".into()]);
503        assert!(!updated, "update_tags should return false for unknown CID");
504    }
505
506    // -----------------------------------------------------------------------
507    // 13. query result sorted by created_at ascending
508    // -----------------------------------------------------------------------
509    #[test]
510    fn test_query_sorted_by_created_at() {
511        let idx = populated_index();
512        let results = idx.query(&QueryFilter::SizeRange {
513            min: 0,
514            max: u64::MAX,
515        });
516        let times: Vec<u64> = results.iter().map(|e| e.created_at_secs).collect();
517        let mut sorted = times.clone();
518        sorted.sort_unstable();
519        assert_eq!(
520            times, sorted,
521            "results must be sorted by created_at_secs asc"
522        );
523    }
524
525    // -----------------------------------------------------------------------
526    // 14. empty result
527    // -----------------------------------------------------------------------
528    #[test]
529    fn test_empty_result() {
530        let idx = populated_index();
531        let results = idx.query(&QueryFilter::ContentType {
532            ct: "text/plain".into(),
533        });
534        assert!(results.is_empty());
535    }
536
537    // -----------------------------------------------------------------------
538    // 15. stats.total_entries
539    // -----------------------------------------------------------------------
540    #[test]
541    fn test_stats_total_entries() {
542        let idx = populated_index();
543        let stats = idx.stats();
544        assert_eq!(stats.total_entries, 5);
545    }
546
547    #[test]
548    fn test_stats_total_entries_after_remove() {
549        let mut idx = populated_index();
550        idx.remove("QmA");
551        assert_eq!(idx.stats().total_entries, 4);
552    }
553
554    // -----------------------------------------------------------------------
555    // 16. query all with always-true filter (Or of size 0..MAX)
556    // -----------------------------------------------------------------------
557    #[test]
558    fn test_query_all_always_true() {
559        let idx = populated_index();
560        // SizeRange [0, u64::MAX] matches every entry
561        let results = idx.query(&QueryFilter::SizeRange {
562            min: 0,
563            max: u64::MAX,
564        });
565        assert_eq!(results.len(), 5, "all 5 entries should be returned");
566    }
567
568    // -----------------------------------------------------------------------
569    // 17. IndexStats.coverage always returns 1.0
570    // -----------------------------------------------------------------------
571    #[test]
572    fn test_stats_coverage() {
573        let idx = populated_index();
574        let stats = idx.stats();
575        assert!((stats.coverage() - 1.0).abs() < f64::EPSILON);
576    }
577
578    // -----------------------------------------------------------------------
579    // 18. indexed_fields contains all four dimensions
580    // -----------------------------------------------------------------------
581    #[test]
582    fn test_stats_indexed_fields() {
583        let idx = populated_index();
584        let stats = idx.stats();
585        assert!(stats.indexed_fields.contains(&IndexField::Size));
586        assert!(stats.indexed_fields.contains(&IndexField::CreatedAt));
587        assert!(stats.indexed_fields.contains(&IndexField::Tag));
588        assert!(stats.indexed_fields.contains(&IndexField::ContentType));
589    }
590
591    // -----------------------------------------------------------------------
592    // 19. insert overwrites duplicate CID
593    // -----------------------------------------------------------------------
594    #[test]
595    fn test_insert_overwrites_existing_cid() {
596        let mut idx = StorageIndexBuilder::new();
597        idx.insert(make_entry("QmX", 100, 1_000, &["old"], "text/plain"));
598        idx.insert(make_entry("QmX", 200, 2_000, &["new"], "application/json"));
599
600        assert_eq!(
601            idx.stats().total_entries,
602            1,
603            "duplicate CID must not inflate count"
604        );
605
606        let results = idx.query(&QueryFilter::HasTag { tag: "new".into() });
607        assert_eq!(results.len(), 1);
608        assert_eq!(results[0].size_bytes, 200);
609    }
610
611    // -----------------------------------------------------------------------
612    // 20. Nested And + Or (compound filter)
613    // -----------------------------------------------------------------------
614    #[test]
615    fn test_nested_and_or_filter() {
616        let idx = populated_index();
617        // (image tag OR audio tag) AND size < 500
618        let filter = QueryFilter::And(
619            Box::new(QueryFilter::Or(
620                Box::new(QueryFilter::HasTag {
621                    tag: "image".into(),
622                }),
623                Box::new(QueryFilter::HasTag {
624                    tag: "audio".into(),
625                }),
626            )),
627            Box::new(QueryFilter::SizeRange { min: 0, max: 499 }),
628        );
629        let results = idx.query(&filter);
630        // QmA (image, 100) ✓  QmC (audio, 1000) ✗  QmD (image, 50) ✓
631        let cids: Vec<&str> = results.iter().map(|e| e.cid.as_str()).collect();
632        assert!(cids.contains(&"QmA"));
633        assert!(cids.contains(&"QmD"));
634        assert!(!cids.contains(&"QmC"));
635        assert_eq!(results.len(), 2);
636    }
637}
ipfrs_storage/index_builder.rs

ipfrs_storage/
index_builder.rs
