1use 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
63pub 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
75pub 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 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 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()); out.extend_from_slice(&0u64.to_le_bytes()); 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 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 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 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 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 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 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 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 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 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 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 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 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 #[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}