Skip to main content

qualia_core_db/
q42_lex_ns.rs

1//! Q42LEX v4 — paged lexicon with per-page namespace dictionaries.
2//!
3//! Ownership note (AGENTS.md §0-B): the v3 codec is decomposed out of
4//! `q42_lex.rs` (which stays the reader state machine) so each file keeps a
5//! single purpose. The reader additions for v3 live in `q42_lex.rs` because
6//! they share the page-walk state; the writer and namespace economics live
7//! here. The version word is 4, aligned with the Q42 volume generation that
8//! first ships it — there is no LEX v3 (unreleased software; see ADR 0015).
9//!
10//! ## Why namespaces are stored once per page
11//!
12//! RDF term strings are dominated by a small set of repeated namespace
13//! prefixes (`https://schema.org/`, `http://www.w3.org/2000/01/rdf-schema#`,
14//! `did:q42:`, `urn:q42:`, …). v2 pages store every term verbatim, so each
15//! term re-pays its namespace bytes. v4 keeps a namespace table **inside each
16//! page** and encodes qualifying terms as `(namespace id, local name)`.
17//!
18//! The table is page-local by design: a page is the unit an HTTP-Range /
19//! IPFS reader fetches, so every page stays independently decodable and the
20//! range-query contract of the v2 layout is preserved exactly. A volume may
21//! contain many ontologies, and an ontology may declare many namespaces —
22//! each page simply carries whichever namespaces its own terms use.
23//!
24//! ## Layout (v4 page, little-endian)
25//!
26//! ```text
27//! page header (16 B): [u32 entry_count][u32 ns_count][u64 blob_offset]
28//! index:              entry_count × [u64 hash][u64 relative-from-blob-start]
29//! blob:               ns table:  ns_count × [u16 len][utf-8 namespace]
30//!                     entries:   0x01 [u16 len][utf-8]                    (verbatim)
31//!                                0x04 [u16 ns_id][u16 local_len][utf-8]    (namespaced)
32//! ```
33//!
34//! `ns_count` occupies the u32 slot v2 writers zeroed, so v2 pages read back
35//! with `ns_count == 0` and the reader fails closed on any `0x04` entry in a
36//! v2 page. Old binaries that only know versions 1–2 reject v4 headers up
37//! front (`BadIndex`) instead of misparsing.
38//!
39//! ## Namespace extraction
40//!
41//! `namespace_split` is scheme-agnostic: it splits at the final `/`, `#`, or
42//! `:` (all ASCII, so a UTF-8 codepoint is never split). The namespace keeps
43//! its trailing separator. This uniformly covers `http(s)` IRIs, `did:`
44//! methods (e.g. `did:q42:`, `did:web:`), `urn:`, and any future scheme whose
45//! terms end in a separator-delimited local name.
46//!
47//! ## When a term is encoded namespaced
48//!
49//! Only when it strictly shrinks the page. Per namespace with `m` member
50//! terms of length `n`, the saving is `m·(n − 2) − (n + 2)` bytes (each
51//! namespaced entry pays a 2-byte ns_id instead of the namespace bytes, the
52//! namespace itself is paid once, both sides pay their u16 lengths). The
53//! rule is deterministic, so identical input maps produce identical bytes.
54
55use std::collections::HashMap;
56
57use crate::q42_lex::{
58    LexError, INDEX_ENTRY_SIZE, LEX_HEADER_SIZE, LEX_MAGIC, LEX_TAG_NAMESPACED, LEX_TAG_STRING,
59    LEX_VERSION_V4, PAGED_DIRECTORY_ENTRY_SIZE, PAGED_DIRECTORY_HEADER_SIZE,
60    PAGED_PAGE_HEADER_SIZE,
61};
62
63/// Split a term into `(namespace, local)` at the final `/`, `#`, or `:`.
64/// The namespace includes its trailing separator; the local name is the rest.
65/// Returns `None` when the term has no separator — verbatim literals stay
66/// verbatim.
67pub fn namespace_split(term: &str) -> Option<(&str, &str)> {
68    let split = term
69        .as_bytes()
70        .iter()
71        .rposition(|&b| b == b'/' || b == b'#' || b == b':')?;
72    Some((&term[..split + 1], &term[split + 1..]))
73}
74
75/// Serialize a hash → string map into the namespaced paged `Q42LEX` v4 byte
76/// layout that [`crate::q42_lex::Q42LexMmap`] reads back.
77///
78/// Entries are sorted by hash and chunked into pages of `page_entries`
79/// exactly like the v2 writer; within each page, terms whose namespace group
80/// passes the economics test above are stored as `0x04` references into the
81/// page-local namespace table, and everything else stays verbatim (`0x01`).
82/// Pages remain independently addressable: decoding any one page needs only
83/// that page's byte range.
84pub fn serialize_namespaced_paged_lexicon(
85    entries: &HashMap<u64, String>,
86    page_entries: usize,
87) -> Result<Vec<u8>, LexError> {
88    if page_entries == 0 {
89        return Err(LexError::BadIndex);
90    }
91    let mut sorted: Vec<(&u64, &String)> = entries.iter().collect();
92    sorted.sort_unstable_by_key(|(h, _)| **h);
93    let page_count = (sorted.len() + page_entries - 1) / page_entries;
94    let directory_len = PAGED_DIRECTORY_HEADER_SIZE + page_count * PAGED_DIRECTORY_ENTRY_SIZE;
95    let mut out = Vec::with_capacity(LEX_HEADER_SIZE + directory_len + entries.len() * 24);
96    out.extend_from_slice(&LEX_MAGIC);
97    out.extend_from_slice(&(sorted.len() as u64).to_le_bytes());
98    out.extend_from_slice(&(LEX_HEADER_SIZE as u64).to_le_bytes());
99    out.extend_from_slice(&LEX_VERSION_V4.to_le_bytes());
100    out.extend_from_slice(&(page_count as u64).to_le_bytes());
101    out.resize(LEX_HEADER_SIZE + directory_len, 0);
102
103    for (page_index, chunk) in sorted.chunks(page_entries).enumerate() {
104        let page_offset = out.len();
105        let page_start = out.len();
106
107        // Namespace groups inside this page, in first-appearance order.
108        let mut ns_ids: HashMap<&str, u16> = HashMap::new();
109        let mut ns_table: Vec<&str> = Vec::new();
110        let mut members: HashMap<&str, usize> = HashMap::new();
111        for (_, text) in chunk {
112            if text.len() > u16::MAX as usize {
113                return Err(LexError::TermTooLong);
114            }
115            if let Some((ns, _)) = namespace_split(text) {
116                *members.entry(ns).or_insert(0usize) += 1;
117            }
118        }
119        let use_ns = |ns: &str| -> bool {
120            match members.get(ns) {
121                Some(&m) if ns.len() >= 3 => {
122                    // m·(n − 2) − (n + 2) > 0, in usize-safe form.
123                    (m as u64) * (ns.len() as u64 - 2) > (ns.len() as u64 + 2)
124                }
125                _ => false,
126            }
127        };
128
129        out.extend_from_slice(&(chunk.len() as u32).to_le_bytes());
130        out.extend_from_slice(&0u32.to_le_bytes()); // ns_count, patched below
131        out.extend_from_slice(&0u64.to_le_bytes()); // blob_offset, patched below
132        let blob_offset = PAGED_PAGE_HEADER_SIZE + chunk.len() * INDEX_ENTRY_SIZE;
133        let index_start = out.len();
134        out.resize(index_start + chunk.len() * INDEX_ENTRY_SIZE, 0);
135
136        // Namespace table at the start of the blob region. Iterating
137        // `members` (a HashMap) would permute ns ids per process and make
138        // the serialised volume non-reproducible — sort for a canonical
139        // byte layout.
140        let mut accepted: Vec<&str> = members
141            .iter()
142            .filter(|(ns, count)| *count > &0 && use_ns(ns))
143            .map(|(ns, _)| *ns)
144            .collect();
145        accepted.sort_unstable();
146        for ns in accepted {
147            ns_ids.insert(ns, ns_table.len() as u16);
148            ns_table.push(ns);
149        }
150        for ns in &ns_table {
151            let bytes = ns.as_bytes();
152            let len = u16::try_from(bytes.len()).map_err(|_| LexError::TermTooLong)?;
153            out.extend_from_slice(&len.to_le_bytes());
154            out.extend_from_slice(bytes);
155        }
156
157        for (entry_index, (hash, text)) in chunk.iter().enumerate() {
158            let relative = (out.len() - page_start - blob_offset) as u64;
159            let b = text.as_bytes();
160            match namespace_split(text).filter(|(ns, _)| ns_ids.contains_key(ns)) {
161                Some((ns, local)) => {
162                    let ns_id = ns_ids[ns];
163                    let local = local.as_bytes();
164                    let local_len =
165                        u16::try_from(local.len()).map_err(|_| LexError::TermTooLong)?;
166                    out.push(LEX_TAG_NAMESPACED);
167                    out.extend_from_slice(&ns_id.to_le_bytes());
168                    out.extend_from_slice(&local_len.to_le_bytes());
169                    out.extend_from_slice(local);
170                }
171                None => {
172                    let len = u16::try_from(b.len()).map_err(|_| LexError::TermTooLong)?;
173                    out.push(LEX_TAG_STRING);
174                    out.extend_from_slice(&len.to_le_bytes());
175                    out.extend_from_slice(&b[..len as usize]);
176                }
177            }
178            let index_offset = index_start + entry_index * INDEX_ENTRY_SIZE;
179            out[index_offset..index_offset + 8].copy_from_slice(&hash.to_le_bytes());
180            out[index_offset + 8..index_offset + 16].copy_from_slice(&relative.to_le_bytes());
181        }
182
183        let ns_count = ns_table.len() as u32;
184        out[page_start + 4..page_start + 8].copy_from_slice(&ns_count.to_le_bytes());
185        out[page_start + 8..page_start + 16].copy_from_slice(&(blob_offset as u64).to_le_bytes());
186
187        let page_length = (out.len() - page_start) as u64;
188        let directory =
189            LEX_HEADER_SIZE + PAGED_DIRECTORY_HEADER_SIZE + page_index * PAGED_DIRECTORY_ENTRY_SIZE;
190        out[directory..directory + 8].copy_from_slice(&chunk[0].0.to_le_bytes());
191        out[directory + 8..directory + 16].copy_from_slice(&(page_offset as u64).to_le_bytes());
192        out[directory + 16..directory + 24].copy_from_slice(&page_length.to_le_bytes());
193        out[directory + 24..directory + 28].copy_from_slice(&(chunk.len() as u32).to_le_bytes());
194    }
195    Ok(out)
196}
197
198#[cfg(test)]
199mod tests {
200    use super::*;
201    use crate::q42_lex::{Q42LexMmap, LEX_VERSION_PAGED, LEX_VERSION_V4};
202
203    #[test]
204    fn namespace_split_is_scheme_agnostic() {
205        assert_eq!(
206            namespace_split("http://theontology.tld/Term"),
207            Some(("http://theontology.tld/", "Term"))
208        );
209        assert_eq!(
210            namespace_split("http://www.w3.org/2001/XMLSchema#integer"),
211            Some(("http://www.w3.org/2001/XMLSchema#", "integer"))
212        );
213        assert_eq!(
214            namespace_split("did:q42:z6MkpTHR8V"),
215            Some(("did:q42:", "z6MkpTHR8V"))
216        );
217        assert_eq!(
218            namespace_split("urn:uuid:550e8400-e29b"),
219            Some(("urn:uuid:", "550e8400-e29b"))
220        );
221        assert_eq!(namespace_split("dog"), None);
222        // Multibyte locals survive: separators are ASCII.
223        assert_eq!(
224            namespace_split("https://ex.org/อย่างสะเพร่า"),
225            Some(("https://ex.org/", "อย่างสะเพร่า"))
226        );
227    }
228
229    #[test]
230    fn v4_round_trips_multi_ontology_namespaces() {
231        // Three ontologies in one volume: schema.org, W3C RDF, and a DID-based
232        // Webizen namespace — plus a bare literal that must stay verbatim.
233        let mut map = HashMap::new();
234        for name in ["Thing", "Person", "Organization", "CreativeWork"] {
235            map.insert(crate::q_hash(name), format!("https://schema.org/{name}"));
236        }
237        for name in ["label", "comment", "isDefinedBy", "seeAlso", "domain"] {
238            map.insert(
239                crate::q_hash(name),
240                format!("http://www.w3.org/2000/01/rdf-schema#{name}"),
241            );
242        }
243        for n in 0..6u32 {
244            map.insert(
245                crate::q_hash(&format!("did-term-{n}")),
246                format!("did:q42:z6MkTopic{n}"),
247            );
248        }
249        map.insert(
250            crate::q_hash("bare"),
251            "bare-literal-no-separator".to_string(),
252        );
253
254        let bytes = serialize_namespaced_paged_lexicon(&map, 3).unwrap();
255        assert_eq!(
256            u64::from_le_bytes(bytes[24..32].try_into().unwrap()),
257            LEX_VERSION_V4
258        );
259        let view = Q42LexMmap::from_bytes(&bytes).unwrap();
260        assert_eq!(view.entry_count(), map.len());
261        for (hash, text) in &map {
262            let (ns, local) = view.lookup_parts(*hash).expect("term must resolve");
263            assert_eq!(format!("{ns}{local}"), *text);
264            assert_eq!(view.lookup_owned(*hash).as_deref(), Some(text.as_str()));
265        }
266        // The bare literal stays verbatim: parts are ("", full).
267        let (ns, local) = view.lookup_parts(crate::q_hash("bare")).unwrap();
268        assert_eq!(ns, "");
269        assert_eq!(local, "bare-literal-no-separator");
270    }
271
272    #[test]
273    fn v4_pages_decode_from_isolated_byte_ranges() {
274        // HTTP-Range proof: reconstruct lookups using only the global header,
275        // the directory, and ONE page's bytes — never the full lexicon.
276        let mut map = HashMap::new();
277        for i in 0..40u64 {
278            map.insert(
279                crate::q_hash(&format!("term-{i}")),
280                format!("https://example.org/vocab/term-{i}"),
281            );
282        }
283        let bytes = serialize_namespaced_paged_lexicon(&map, 4).unwrap();
284        let view = Q42LexMmap::from_bytes(&bytes).unwrap();
285
286        let page_count = u64::from_le_bytes(bytes[32..40].try_into().unwrap()) as usize;
287        assert_eq!(page_count, 10);
288        for page in 0..page_count {
289            let dir = 40 + page * PAGED_DIRECTORY_ENTRY_SIZE;
290            let page_offset = usize::try_from(u64::from_le_bytes(
291                bytes[dir + 8..dir + 16].try_into().unwrap(),
292            ))
293            .unwrap();
294            let page_length = usize::try_from(u64::from_le_bytes(
295                bytes[dir + 16..dir + 24].try_into().unwrap(),
296            ))
297            .unwrap();
298            let count = u32::from_le_bytes(bytes[dir + 24..dir + 28].try_into().unwrap()) as usize;
299            // The slice a range reader would hold for this page alone.
300            let page_bytes = &bytes[page_offset..page_offset + page_length];
301            let ns_count = u32::from_le_bytes(page_bytes[4..8].try_into().unwrap()) as usize;
302            assert_eq!(ns_count, 1, "one namespace shared by the whole page");
303            for item in 0..count {
304                let entry = 16 + item * INDEX_ENTRY_SIZE;
305                let hash = u64::from_le_bytes(page_bytes[entry..entry + 8].try_into().unwrap());
306                let relative =
307                    u64::from_le_bytes(page_bytes[entry + 8..entry + 16].try_into().unwrap())
308                        as usize;
309                let blob_offset =
310                    u64::from_le_bytes(page_bytes[8..16].try_into().unwrap()) as usize;
311                let start = blob_offset + relative;
312                assert_eq!(page_bytes[start], LEX_TAG_NAMESPACED);
313                let ns_id =
314                    u16::from_le_bytes(page_bytes[start + 1..start + 3].try_into().unwrap());
315                let local_len =
316                    u16::from_le_bytes(page_bytes[start + 3..start + 5].try_into().unwrap());
317                // Walk the page-local namespace table to rebuild the ns.
318                // Namespace table entries are [u16 len][utf-8] — no tag byte.
319                let mut cursor = blob_offset;
320                let mut ns = "";
321                for _ in 0..=ns_id {
322                    let len = u16::from_le_bytes(page_bytes[cursor..cursor + 2].try_into().unwrap())
323                        as usize;
324                    ns = std::str::from_utf8(&page_bytes[cursor + 2..cursor + 2 + len]).unwrap();
325                    cursor += 2 + len;
326                }
327                let local =
328                    std::str::from_utf8(&page_bytes[start + 5..start + 5 + local_len as usize])
329                        .unwrap();
330                let text = format!("{ns}{local}");
331                assert_eq!(text, view.lookup_owned(hash).unwrap());
332            }
333        }
334    }
335
336    #[test]
337    fn v4_is_smaller_than_v2_for_shared_namespaces() {
338        let mut map = HashMap::new();
339        for i in 0..512u32 {
340            map.insert(
341                crate::q_hash(&format!("term-{i}")),
342                format!("https://schema.org/term-{i}"),
343            );
344        }
345        let v2 = crate::q42_lex::serialize_paged_string_lexicon(&map, 4096).unwrap();
346        let v4 = serialize_namespaced_paged_lexicon(&map, 4096).unwrap();
347        assert!(
348            v4.len() < v2.len(),
349            "v4 ({}) must beat v2 ({}) on shared namespaces",
350            v4.len(),
351            v2.len()
352        );
353        // 512 terms × 18 namespace bytes minus per-entry and table overhead.
354        let saved = v2.len() - v4.len();
355        assert!(saved > 8_000, "expected a material saving, got {saved} B");
356    }
357
358    #[test]
359    fn v4_never_grows_a_lexicon() {
360        // Worst case: every term unique (no shared namespaces) — v4 falls
361        // back to verbatim entries plus empty ns tables.
362        let mut map = HashMap::new();
363        for i in 0..64u32 {
364            map.insert(
365                crate::q_hash(&format!("u{i}")),
366                format!("urn:u{i}:only-one"),
367            );
368        }
369        let v2 = crate::q42_lex::serialize_paged_string_lexicon(&map, 4096).unwrap();
370        let v4 = serialize_namespaced_paged_lexicon(&map, 4096).unwrap();
371        // Same entries, same pages; ns_count fields are 0. The only delta is
372        // the format version word, so sizes are equal.
373        assert_eq!(v2.len(), v4.len());
374        let view = Q42LexMmap::from_bytes(&v4).unwrap();
375        for (hash, text) in &map {
376            assert_eq!(view.lookup_owned(*hash).as_deref(), Some(text.as_str()));
377        }
378    }
379
380    #[test]
381    fn v2_reader_rejects_namespaced_entries() {
382        // Fail-closed: a 0x04 tag in a v2 page (ns_count slot 0) must not
383        // decode, even if the bytes otherwise look plausible.
384        let mut map = HashMap::new();
385        for i in 0..4u32 {
386            map.insert(
387                crate::q_hash(&format!("t{i}")),
388                format!("https://ex.org/t{i}"),
389            );
390        }
391        let mut bytes = crate::q42_lex::serialize_paged_string_lexicon(&map, 4).unwrap();
392        bytes[24..32].copy_from_slice(&LEX_VERSION_PAGED.to_le_bytes());
393        // Flip the first entry tag from 0x01 (verbatim) to 0x04.
394        let dir = 40;
395        let page_offset = usize::try_from(u64::from_le_bytes(
396            bytes[dir + 8..dir + 16].try_into().unwrap(),
397        ))
398        .unwrap();
399        let blob_offset =
400            u64::from_le_bytes(bytes[page_offset + 8..page_offset + 16].try_into().unwrap())
401                as usize;
402        bytes[page_offset + blob_offset] = 0x04;
403        assert!(Q42LexMmap::from_bytes(&bytes).is_err());
404    }
405
406    #[test]
407    fn v4_rejects_overlong_terms() {
408        let long = "あ".repeat(22_000);
409        let mut map = HashMap::new();
410        map.insert(crate::q_hash(&long), long);
411        assert_eq!(
412            serialize_namespaced_paged_lexicon(&map, 4),
413            Err(LexError::TermTooLong)
414        );
415    }
416
417    /// Real-data receipt: load the term set of an actual in-repo volume and
418    /// compare what the v2 paged layout would cost against the v4 namespaced
419    /// layout for the *same* terms. Stable regardless of which generation is
420    /// on disk. Hashed-only volumes (32-byte stub lexicons — e.g.
421    /// `princeton.q42`) are skipped honestly: no terms to deduplicate.
422    #[test]
423    fn real_volume_lexicon_shrinks_under_v4() {
424        let candidates = [
425            "docs/data/schemaorg/30.0/schemaorg-current-https.q42",
426            "../../docs/data/schemaorg/30.0/schemaorg-current-https.q42",
427            "bundled/ontologies/w3c-archives/ldp.q42",
428            "../../bundled/ontologies/w3c-archives/ldp.q42",
429        ];
430        let mut chosen: Option<(std::path::PathBuf, HashMap<u64, String>, u64)> = None;
431        for candidate in candidates {
432            let path = std::path::Path::new(candidate);
433            if !path.is_file() {
434                continue;
435            }
436            let Ok(volume) = crate::q42_volume::Q42Volume::open(path) else {
437                continue;
438            };
439            let mut map;
440            let entries;
441            {
442                let Ok(view) = volume.lex_view() else {
443                    continue;
444                };
445                entries = view.entry_count() as u64;
446                map = HashMap::with_capacity(view.entry_count());
447                for i in 0..view.entry_count() {
448                    let Some(hash) = view.hash_at(i) else {
449                        break;
450                    };
451                    if let Some((ns, local)) = view.string_parts_at(i) {
452                        let mut text = String::with_capacity(ns.len() + local.len());
453                        text.push_str(ns);
454                        text.push_str(local);
455                        map.insert(hash, text);
456                    }
457                }
458            }
459            if map.is_empty() {
460                eprintln!(
461                    "[lex-v4] {} is hashed-only (empty lexicon) — no terms to deduplicate",
462                    path.display()
463                );
464                continue;
465            }
466            chosen = Some((path.to_path_buf(), map, entries));
467            break;
468        }
469        let Some((path, map, entries)) = chosen else {
470            eprintln!("[lex-v4] no in-repo volume with a populated lexicon — receipt skipped");
471            return;
472        };
473        let v2 = crate::q42_lex::serialize_paged_string_lexicon(
474            &map,
475            crate::q42_lex::DEFAULT_LEX_PAGE_ENTRIES,
476        )
477        .unwrap();
478        let v4 = serialize_namespaced_paged_lexicon(&map, crate::q42_lex::DEFAULT_LEX_PAGE_ENTRIES)
479            .unwrap();
480        let saved = v2.len().saturating_sub(v4.len());
481        println!(
482            "[lex-v4] {} — {entries} terms; same lexicon under v2 layout = {} B vs v4 = {} B, saved {saved} B ({:.1}%)",
483            path.display(),
484            v2.len(),
485            v4.len(),
486            saved as f64 * 100.0 / v2.len() as f64
487        );
488        assert!(
489            v4.len() < v2.len(),
490            "v4 must beat v2 for a real ontology lexicon ({} → {})",
491            v2.len(),
492            v4.len()
493        );
494    }
495}