1#[cfg(not(target_arch = "wasm32"))]
4use std::fs::File;
5use std::io;
6#[cfg(not(target_arch = "wasm32"))]
7use std::io::Read;
8#[cfg(not(target_arch = "wasm32"))]
9use std::path::PathBuf;
10use std::path::{Component, Path};
11
12#[cfg(not(target_arch = "wasm32"))]
13use sha2::{Digest, Sha256};
14
15#[cfg(not(target_arch = "wasm32"))]
16use super::super::{Q42VerificationReceipt, Q42Volume};
17use super::super::{MAX_COMPRESSED_SUPERBLOCK_SIZE, SUPERBLOCK_SIZE};
18use super::range::{verify_source_sha256, Q42RangeSource};
19use super::range_volume::{
20 Q42RangeQueryCursor, Q42RangeQueryPage, Q42RangeQueryPlan, Q42RangeVolume,
21};
22
23pub const VOLUME_MANIFEST_MAGIC: [u8; 8] = *b"Q42VOL\0\0";
24pub const VOLUME_MANIFEST_VERSION: u16 = 2;
25pub const MAX_VOLUME_MANIFEST_BYTES: usize = 4 * 1024 * 1024;
26pub const MAX_VOLUME_SEGMENTS: usize = 65_536;
27const HEADER_BYTES: usize = 32;
28const ENTRY_FIXED_BYTES: usize = 66;
29const LEX_ENTRY_FIXED_BYTES: usize = 58;
30
31fn invalid(message: impl Into<String>) -> io::Error {
33 io::Error::new(io::ErrorKind::InvalidData, message.into())
34}
35
36#[derive(Clone, Debug, Eq, PartialEq)]
38pub struct Q42VolumeSegment {
39 pub locator: String,
42 pub byte_length: u64,
43 pub first_object_hash: u64,
44 pub last_object_hash: u64,
45 pub quin_count: u64,
46 pub sha256: [u8; 32],
47}
48
49#[derive(Clone, Debug, Eq, PartialEq)]
54pub struct Q42LexiconSegment {
55 pub locator: String,
56 pub byte_length: u64,
57 pub first_hash: u64,
58 pub last_hash: u64,
59 pub sha256: [u8; 32],
60}
61
62#[derive(Clone, Debug, Eq, PartialEq)]
64pub struct Q42VolumeManifest {
65 pub generation: u64,
66 pub segments: Vec<Q42VolumeSegment>,
67 pub lexicon_segments: Vec<Q42LexiconSegment>,
68}
69
70#[derive(Clone, Copy, Debug, Eq, PartialEq)]
72pub struct Q42SegmentMatchRange {
73 pub start: usize,
74 pub end: usize,
75}
76
77impl Q42SegmentMatchRange {
78 pub fn len(self) -> usize {
80 self.end - self.start
81 }
82
83 pub fn is_empty(self) -> bool {
85 self.start == self.end
86 }
87}
88
89#[derive(Clone, Copy, Debug, Eq, PartialEq)]
91pub struct Q42SegmentMatchPage {
92 pub range: Q42SegmentMatchRange,
93 pub returned: usize,
94 pub next_cursor: Option<usize>,
95}
96
97impl Q42VolumeManifest {
98 pub fn encode(&self) -> io::Result<Vec<u8>> {
102 self.validate()?;
103 let mut bytes = Vec::with_capacity(
104 HEADER_BYTES
105 + self.segments.len() * ENTRY_FIXED_BYTES
106 + self.lexicon_segments.len() * LEX_ENTRY_FIXED_BYTES,
107 );
108 bytes.extend_from_slice(&VOLUME_MANIFEST_MAGIC);
109 bytes.extend_from_slice(&VOLUME_MANIFEST_VERSION.to_le_bytes());
110 bytes.extend_from_slice(&0u16.to_le_bytes());
111 bytes.extend_from_slice(&(self.segments.len() as u32).to_le_bytes());
112 bytes.extend_from_slice(&self.generation.to_le_bytes());
113 bytes.extend_from_slice(&(self.lexicon_segments.len() as u64).to_le_bytes());
114 for segment in &self.segments {
115 let locator = segment.locator.as_bytes();
116 let locator_len = u16::try_from(locator.len()).map_err(|_| {
117 io::Error::new(
118 io::ErrorKind::InvalidInput,
119 "Q42 segment locator exceeds u16 length",
120 )
121 })?;
122 bytes.extend_from_slice(&segment.byte_length.to_le_bytes());
123 bytes.extend_from_slice(&segment.first_object_hash.to_le_bytes());
124 bytes.extend_from_slice(&segment.last_object_hash.to_le_bytes());
125 bytes.extend_from_slice(&segment.quin_count.to_le_bytes());
126 bytes.extend_from_slice(&segment.sha256);
127 bytes.extend_from_slice(&locator_len.to_le_bytes());
128 bytes.extend_from_slice(locator);
129 }
130 for segment in &self.lexicon_segments {
131 let locator = segment.locator.as_bytes();
132 let locator_len = u16::try_from(locator.len()).map_err(|_| {
133 io::Error::new(
134 io::ErrorKind::InvalidInput,
135 "Q42 lexicon segment locator exceeds u16 length",
136 )
137 })?;
138 bytes.extend_from_slice(&segment.byte_length.to_le_bytes());
139 bytes.extend_from_slice(&segment.first_hash.to_le_bytes());
140 bytes.extend_from_slice(&segment.last_hash.to_le_bytes());
141 bytes.extend_from_slice(&segment.sha256);
142 bytes.extend_from_slice(&locator_len.to_le_bytes());
143 bytes.extend_from_slice(locator);
144 }
145 if bytes.len() > MAX_VOLUME_MANIFEST_BYTES {
146 return Err(io::Error::new(
147 io::ErrorKind::InvalidInput,
148 "Q42 volume manifest exceeds the 4 MiB front-matter ceiling",
149 ));
150 }
151 Ok(bytes)
152 }
153
154 pub fn decode(bytes: &[u8]) -> io::Result<Self> {
157 if bytes.len() < HEADER_BYTES || bytes.len() > MAX_VOLUME_MANIFEST_BYTES {
158 return Err(invalid("invalid Q42 volume manifest length"));
159 }
160 if bytes[0..8] != VOLUME_MANIFEST_MAGIC {
161 return Err(invalid("invalid Q42 volume manifest magic"));
162 }
163 let version = u16::from_le_bytes(bytes[8..10].try_into().unwrap());
164 if version != 1 && version != VOLUME_MANIFEST_VERSION {
165 return Err(invalid("unsupported Q42 volume manifest version"));
166 }
167 let count = u32::from_le_bytes(bytes[12..16].try_into().unwrap()) as usize;
168 if count == 0 || count > MAX_VOLUME_SEGMENTS {
169 return Err(invalid("invalid Q42 volume manifest segment count"));
170 }
171 let generation = u64::from_le_bytes(bytes[16..24].try_into().unwrap());
172 let lexicon_count = if version == 1 {
173 0
174 } else {
175 usize::try_from(u64::from_le_bytes(bytes[24..32].try_into().unwrap()))
176 .map_err(|_| invalid("Q42 lexicon segment count exceeds platform"))?
177 };
178 let mut offset = HEADER_BYTES;
179 let mut segments = Vec::with_capacity(count);
180 for _ in 0..count {
181 let fixed_end = offset
182 .checked_add(ENTRY_FIXED_BYTES)
183 .ok_or_else(|| invalid("manifest entry overflow"))?;
184 if fixed_end > bytes.len() {
185 return Err(invalid("truncated Q42 volume manifest entry"));
186 }
187 let byte_length = u64::from_le_bytes(bytes[offset..offset + 8].try_into().unwrap());
188 let first_object_hash =
189 u64::from_le_bytes(bytes[offset + 8..offset + 16].try_into().unwrap());
190 let last_object_hash =
191 u64::from_le_bytes(bytes[offset + 16..offset + 24].try_into().unwrap());
192 let quin_count =
193 u64::from_le_bytes(bytes[offset + 24..offset + 32].try_into().unwrap());
194 let sha256 = bytes[offset + 32..offset + 64].try_into().unwrap();
195 offset = fixed_end;
196 let locator_len =
197 u16::from_le_bytes(bytes[offset - 2..offset].try_into().unwrap()) as usize;
198 let locator_end = offset
199 .checked_add(locator_len)
200 .ok_or_else(|| invalid("manifest locator overflow"))?;
201 if locator_end > bytes.len() {
202 return Err(invalid("truncated Q42 segment locator"));
203 }
204 let locator = std::str::from_utf8(&bytes[offset..locator_end])
205 .map_err(|_| invalid("Q42 segment locator is not UTF-8"))?
206 .to_owned();
207 segments.push(Q42VolumeSegment {
208 locator,
209 byte_length,
210 first_object_hash,
211 last_object_hash,
212 quin_count,
213 sha256,
214 });
215 offset = locator_end;
216 }
217 let mut lexicon_segments = Vec::with_capacity(lexicon_count);
218 for _ in 0..lexicon_count {
219 let fixed_end = offset
220 .checked_add(LEX_ENTRY_FIXED_BYTES)
221 .ok_or_else(|| invalid("lexicon manifest entry overflow"))?;
222 if fixed_end > bytes.len() {
223 return Err(invalid("truncated Q42 lexicon manifest entry"));
224 }
225 let byte_length = u64::from_le_bytes(bytes[offset..offset + 8].try_into().unwrap());
226 let first_hash = u64::from_le_bytes(bytes[offset + 8..offset + 16].try_into().unwrap());
227 let last_hash = u64::from_le_bytes(bytes[offset + 16..offset + 24].try_into().unwrap());
228 let sha256 = bytes[offset + 24..offset + 56].try_into().unwrap();
229 let locator_len =
230 u16::from_le_bytes(bytes[offset + 56..fixed_end].try_into().unwrap()) as usize;
231 offset = fixed_end;
232 let locator_end = offset
233 .checked_add(locator_len)
234 .ok_or_else(|| invalid("Q42 lexicon locator overflow"))?;
235 if locator_end > bytes.len() {
236 return Err(invalid("truncated Q42 lexicon segment locator"));
237 }
238 let locator = std::str::from_utf8(&bytes[offset..locator_end])
239 .map_err(|_| invalid("Q42 lexicon locator is not UTF-8"))?
240 .to_owned();
241 lexicon_segments.push(Q42LexiconSegment {
242 locator,
243 byte_length,
244 first_hash,
245 last_hash,
246 sha256,
247 });
248 offset = locator_end;
249 }
250 if offset != bytes.len() {
251 return Err(invalid("Q42 volume manifest has trailing bytes"));
252 }
253 let manifest = Self {
254 generation,
255 segments,
256 lexicon_segments,
257 };
258 manifest.validate()?;
259 Ok(manifest)
260 }
261
262 pub fn validate(&self) -> io::Result<()> {
265 if self.segments.is_empty() || self.segments.len() > MAX_VOLUME_SEGMENTS {
266 return Err(io::Error::new(
267 io::ErrorKind::InvalidInput,
268 "Q42 volume must contain 1..=65536 segments",
269 ));
270 }
271 let mut previous_last = None;
272 for segment in &self.segments {
273 validate_segment_locator(&segment.locator)?;
274 if segment.byte_length == 0
275 || segment.quin_count == 0
276 || segment.first_object_hash > segment.last_object_hash
277 {
278 return Err(io::Error::new(
279 io::ErrorKind::InvalidInput,
280 "Q42 segment metadata is invalid",
281 ));
282 }
283 if previous_last.is_some_and(|last| segment.first_object_hash < last) {
284 return Err(io::Error::new(
285 io::ErrorKind::InvalidInput,
286 "Q42 segments are not globally object-sorted",
287 ));
288 }
289 previous_last = Some(segment.last_object_hash);
290 }
291 let mut previous_last = None;
292 for segment in &self.lexicon_segments {
293 validate_segment_locator(&segment.locator)?;
294 if segment.byte_length == 0
295 || segment.first_hash > segment.last_hash
296 || previous_last.is_some_and(|last| segment.first_hash <= last)
297 {
298 return Err(io::Error::new(
299 io::ErrorKind::InvalidInput,
300 "Q42 lexicon segments are invalid or overlap",
301 ));
302 }
303 previous_last = Some(segment.last_hash);
304 }
305 Ok(())
306 }
307
308 pub fn segment_range_for_object(&self, object_hash: u64) -> Option<Q42SegmentMatchRange> {
311 let mut lo = 0usize;
312 let mut hi = self.segments.len();
313 while lo < hi {
314 let mid = lo + (hi - lo) / 2;
315 if self.segments[mid].last_object_hash < object_hash {
316 lo = mid + 1;
317 } else {
318 hi = mid;
319 }
320 }
321 let start = lo;
322 if start == self.segments.len() || self.segments[start].first_object_hash > object_hash {
323 return None;
324 }
325 lo = start;
326 hi = self.segments.len();
327 while lo < hi {
328 let mid = lo + (hi - lo) / 2;
329 if self.segments[mid].first_object_hash <= object_hash {
330 lo = mid + 1;
331 } else {
332 hi = mid;
333 }
334 }
335 Some(Q42SegmentMatchRange { start, end: lo })
336 }
337
338 pub fn segment_indices_for_object_into(
341 &self,
342 object_hash: u64,
343 cursor: usize,
344 out: &mut [usize],
345 ) -> io::Result<Option<Q42SegmentMatchPage>> {
346 let Some(range) = self.segment_range_for_object(object_hash) else {
347 return Ok(None);
348 };
349 if cursor > range.len() {
350 return Err(io::Error::new(
351 io::ErrorKind::InvalidInput,
352 "Q42 manifest segment cursor is beyond the matching interval",
353 ));
354 }
355 if out.is_empty() && cursor < range.len() {
356 return Err(io::Error::new(
357 io::ErrorKind::InvalidInput,
358 "Q42 manifest segment page requires at least one output slot",
359 ));
360 }
361 let returned = (range.len() - cursor).min(out.len());
362 for (offset, slot) in out.iter_mut().take(returned).enumerate() {
363 *slot = range.start + cursor + offset;
364 }
365 let next = cursor + returned;
366 Ok(Some(Q42SegmentMatchPage {
367 range,
368 returned,
369 next_cursor: (next < range.len()).then_some(next),
370 }))
371 }
372
373 #[cfg(not(target_arch = "wasm32"))]
374 pub fn segment_from_file(path: &Path, locator: String) -> io::Result<Q42VolumeSegment> {
378 let volume = Q42Volume::open(path)?;
379 let mut first = None;
380 let mut last = 0u64;
381 let mut quin_count = 0u64;
382 let mut block = [0u8; crate::q42_volume::SUPERBLOCK_SIZE];
383 for index in 0..volume.block_count() as usize {
384 volume.read_superblock_into(index, &mut block)?;
385 let live = u64::from_le_bytes(block[16..24].try_into().unwrap()) as usize;
386 for quin_index in 0..live {
387 let offset = crate::q42_volume::SUPERBLOCK_HEADER
388 + quin_index * crate::q42_volume::QUIN_SIZE;
389 let object =
390 u64::from_le_bytes(block[offset + 16..offset + 24].try_into().unwrap());
391 first.get_or_insert(object);
392 last = object;
393 quin_count += 1;
394 }
395 }
396 let Some(first_object_hash) = first else {
397 return Err(io::Error::new(
398 io::ErrorKind::InvalidInput,
399 "Q42 segment has no Quins",
400 ));
401 };
402 Ok(Q42VolumeSegment {
403 locator,
404 byte_length: std::fs::metadata(path)?.len(),
405 first_object_hash,
406 last_object_hash: last,
407 quin_count,
408 sha256: sha256_file(path)?,
409 })
410 }
411
412 #[cfg(not(target_arch = "wasm32"))]
413 pub fn lexicon_segment_from_file(
416 path: &Path,
417 locator: String,
418 ) -> io::Result<Q42LexiconSegment> {
419 let volume = Q42Volume::open(path)?;
420 let view = volume
421 .lex_view()
422 .map_err(|error| invalid(format!("invalid Q42LEX shard: {error:?}")))?;
423 let Some(first_hash) = view.hash_at(0) else {
424 return Err(invalid("Q42 lexicon shard is empty"));
425 };
426 let last_hash = view
427 .hash_at(view.entry_count() - 1)
428 .ok_or_else(|| invalid("Q42 lexicon shard has no last hash"))?;
429 Ok(Q42LexiconSegment {
430 locator,
431 byte_length: std::fs::metadata(path)?.len(),
432 first_hash,
433 last_hash,
434 sha256: sha256_file(path)?,
435 })
436 }
437}
438
439pub trait Q42SegmentRangeFactory {
442 type Source: Q42RangeSource;
443
444 fn open_segment(&self, segment: &Q42VolumeSegment) -> io::Result<Self::Source>;
447}
448
449pub trait Q42LexiconRangeFactory {
451 type Source: Q42RangeSource;
452
453 fn open_lexicon_segment(&self, segment: &Q42LexiconSegment) -> io::Result<Self::Source>;
455}
456
457impl<F, S> Q42LexiconRangeFactory for F
458where
459 F: Fn(&Q42LexiconSegment) -> io::Result<S>,
460 S: Q42RangeSource,
461{
462 type Source = S;
463
464 fn open_lexicon_segment(&self, segment: &Q42LexiconSegment) -> io::Result<Self::Source> {
466 self(segment)
467 }
468}
469
470impl<F, S> Q42SegmentRangeFactory for F
471where
472 F: Fn(&Q42VolumeSegment) -> io::Result<S>,
473 S: Q42RangeSource,
474{
475 type Source = S;
476
477 fn open_segment(&self, segment: &Q42VolumeSegment) -> io::Result<Self::Source> {
479 self(segment)
480 }
481}
482
483pub struct Q42RangeVolumeSet<S: Q42RangeSource> {
486 manifest: Q42VolumeManifest,
487 segments: Vec<Q42RangeVolume<S>>,
488 lexicon_segments: Vec<Q42RangeVolume<S>>,
489}
490
491#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
493pub struct Q42VolumeSetQueryCursor {
494 pub segment_index: usize,
495 pub segment_cursor: Q42RangeQueryCursor,
496}
497
498#[derive(Clone, Copy, Debug, Eq, PartialEq)]
499pub struct Q42VolumeSetQueryPage {
500 pub returned: usize,
501 pub next_cursor: Option<Q42VolumeSetQueryCursor>,
502}
503
504impl<S: Q42RangeSource> Q42RangeVolumeSet<S> {
505 pub fn open_root_with_lexicon_factory<R, DF, LF>(
508 root: &Q42RangeVolume<R>,
509 data_factory: &DF,
510 lexicon_factory: &LF,
511 ) -> io::Result<Self>
512 where
513 R: Q42RangeSource,
514 DF: Q42SegmentRangeFactory<Source = S>,
515 LF: Q42LexiconRangeFactory<Source = S>,
516 {
517 let mut set = Self::open_root(root, data_factory)?;
518 set.attach_lexicon_segments(&|segment| lexicon_factory.open_lexicon_segment(segment))?;
519 Ok(set)
520 }
521 pub fn open_root<R, F>(root: &Q42RangeVolume<R>, factory: &F) -> io::Result<Self>
525 where
526 R: Q42RangeSource,
527 F: Q42SegmentRangeFactory<Source = S>,
528 {
529 let manifest_length = root
530 .volume_manifest_length()?
531 .ok_or_else(|| invalid("Q42 root has no embedded volume manifest"))?;
532 let mut bytes = vec![0u8; manifest_length];
533 root.read_volume_manifest_into(&mut bytes)?;
534 let manifest = Q42VolumeManifest::decode(&bytes)?;
535 let mut segments = Vec::with_capacity(manifest.segments.len());
536 for entry in &manifest.segments {
537 let source = factory.open_segment(entry)?;
538 if source.length()? != entry.byte_length {
539 return Err(invalid(format!(
540 "Q42 segment length differs from root manifest: {}",
541 entry.locator
542 )));
543 }
544 let volume = Q42RangeVolume::open(source)?;
545 if volume.object_hash_bounds()?
546 != Some((entry.first_object_hash, entry.last_object_hash))
547 {
548 return Err(invalid(format!(
549 "Q42 segment object bounds differ from root manifest: {}",
550 entry.locator
551 )));
552 }
553 segments.push(volume);
554 }
555 Ok(Self {
556 manifest,
557 segments,
558 lexicon_segments: Vec::new(),
559 })
560 }
561
562 pub fn manifest(&self) -> &Q42VolumeManifest {
564 &self.manifest
565 }
566
567 pub fn segments(&self) -> &[Q42RangeVolume<S>] {
569 &self.segments
570 }
571
572 pub fn lexicon_segments(&self) -> &[Q42RangeVolume<S>] {
574 &self.lexicon_segments
575 }
576
577 pub fn attach_lexicon_segments<F>(&mut self, factory: &F) -> io::Result<()>
582 where
583 F: Fn(&Q42LexiconSegment) -> io::Result<S>,
584 {
585 if !self.lexicon_segments.is_empty() {
586 return Err(invalid("Q42 lexicon shards are already attached"));
587 }
588 let mut opened = Vec::with_capacity(self.manifest.lexicon_segments.len());
589 for entry in &self.manifest.lexicon_segments {
590 let source = factory(entry)?;
591 if source.length()? != entry.byte_length {
592 return Err(invalid(format!(
593 "Q42 lexicon segment length differs from root manifest: {}",
594 entry.locator
595 )));
596 }
597 let volume = Q42RangeVolume::open(source)?;
598 let mut header = [0u8; crate::q42_lex::LEX_HEADER_SIZE];
599 volume.read_lexicon_prefix_into(&mut header)?;
600 let entries = usize::try_from(u64::from_le_bytes(header[8..16].try_into().unwrap()))
601 .map_err(|_| invalid("Q42 lexicon entry count exceeds platform"))?;
602 if entries == 0 {
603 return Err(invalid("Q42 lexicon shard is empty"));
604 }
605 opened.push(volume);
606 }
607 self.lexicon_segments = opened;
608 Ok(())
609 }
610
611 pub fn lookup_lexicon_hash_into(
614 &self,
615 hash: u64,
616 page: &mut [u8],
617 out: &mut [u8],
618 ) -> io::Result<Option<usize>> {
619 if self.manifest.lexicon_segments.is_empty() {
620 return Ok(None);
621 }
622 if self.lexicon_segments.len() != self.manifest.lexicon_segments.len() {
623 return Err(invalid("Q42 lexicon shards have not been attached"));
624 }
625 let mut lo = 0usize;
626 let mut hi = self.manifest.lexicon_segments.len();
627 while lo < hi {
628 let mid = lo + (hi - lo) / 2;
629 if self.manifest.lexicon_segments[mid].first_hash <= hash {
630 lo = mid + 1;
631 } else {
632 hi = mid;
633 }
634 }
635 let Some(index) = lo.checked_sub(1) else {
636 return Ok(None);
637 };
638 if hash > self.manifest.lexicon_segments[index].last_hash {
639 return Ok(None);
640 }
641 self.lexicon_segments[index].lookup_lexicon_hash_into(hash, page, out)
642 }
643
644 pub fn execute_query_page_into(
649 &self,
650 plan: Q42RangeQueryPlan,
651 cursor: Q42VolumeSetQueryCursor,
652 compressed: &mut [u8],
653 decoded: &mut [u8],
654 out: &mut [crate::NQuin],
655 ) -> io::Result<Q42VolumeSetQueryPage> {
656 if out.is_empty() {
657 return Err(io::Error::new(
658 io::ErrorKind::InvalidInput,
659 "Q42 volume-set query output buffer is empty",
660 ));
661 }
662 let (start, end) = if let Some(object) = plan.pattern.object {
663 match self.manifest.segment_range_for_object(object) {
664 Some(range) => (range.start, range.end),
665 None => {
666 return Ok(Q42VolumeSetQueryPage {
667 returned: 0,
668 next_cursor: None,
669 })
670 }
671 }
672 } else {
673 (0, self.segments.len())
674 };
675 let mut segment_index = cursor.segment_index.max(start);
676 let mut segment_cursor = if segment_index == cursor.segment_index {
677 cursor.segment_cursor
678 } else {
679 Q42RangeQueryCursor::default()
680 };
681 let mut returned = 0usize;
682 while segment_index < end {
683 let page: Q42RangeQueryPage = self.segments[segment_index].execute_query_page_into(
684 plan,
685 segment_cursor,
686 compressed,
687 decoded,
688 &mut out[returned..],
689 )?;
690 returned += page.returned;
691 if returned == out.len() {
692 let next_cursor = match page.next_cursor {
693 Some(next) => Some(Q42VolumeSetQueryCursor {
694 segment_index,
695 segment_cursor: next,
696 }),
697 None if segment_index + 1 < end => Some(Q42VolumeSetQueryCursor {
698 segment_index: segment_index + 1,
699 segment_cursor: Q42RangeQueryCursor::default(),
700 }),
701 None => None,
702 };
703 return Ok(Q42VolumeSetQueryPage {
704 returned,
705 next_cursor,
706 });
707 }
708 if let Some(next) = page.next_cursor {
709 return Ok(Q42VolumeSetQueryPage {
710 returned,
711 next_cursor: Some(Q42VolumeSetQueryCursor {
712 segment_index,
713 segment_cursor: next,
714 }),
715 });
716 }
717 segment_index += 1;
718 segment_cursor = Q42RangeQueryCursor::default();
719 }
720 Ok(Q42VolumeSetQueryPage {
721 returned,
722 next_cursor: None,
723 })
724 }
725
726 pub fn segment_index_for_object(&self, object_hash: u64) -> Option<usize> {
730 self.manifest
731 .segment_range_for_object(object_hash)
732 .map(|range| range.start)
733 }
734
735 pub fn segment_indices_for_object_into(
738 &self,
739 object_hash: u64,
740 cursor: usize,
741 out: &mut [usize],
742 ) -> io::Result<Option<Q42SegmentMatchPage>> {
743 self.manifest
744 .segment_indices_for_object_into(object_hash, cursor, out)
745 }
746
747 pub fn verify_segment_hashes(&self, scratch: &mut [u8]) -> io::Result<()> {
749 for (entry, segment) in self.manifest.segments.iter().zip(&self.segments) {
750 verify_source_sha256(segment.source(), &entry.sha256, scratch)?;
751 }
752 Ok(())
753 }
754
755 pub fn verify_segment_quin_counts(
758 &self,
759 compressed: &mut [u8],
760 decoded: &mut [u8],
761 ) -> io::Result<()> {
762 if compressed.len() < MAX_COMPRESSED_SUPERBLOCK_SIZE || decoded.len() < SUPERBLOCK_SIZE {
763 return Err(io::Error::new(
764 io::ErrorKind::InvalidInput,
765 "Q42 segment verifier buffers are too small",
766 ));
767 }
768 for (entry, segment) in self.manifest.segments.iter().zip(&self.segments) {
769 let mut actual = 0u64;
770 for index in 0..segment.block_count() as usize {
771 segment.read_superblock_into(index, compressed, decoded)?;
772 let live = u64::from_le_bytes(decoded[16..24].try_into().unwrap());
773 if live > crate::QUINS_PER_BLOCK as u64 {
774 return Err(invalid("Q42 SuperBlock exceeds its Quin capacity"));
775 }
776 actual = actual
777 .checked_add(live)
778 .ok_or_else(|| invalid("Q42 segment Quin count overflow"))?;
779 }
780 if actual != entry.quin_count {
781 return Err(invalid(format!(
782 "Q42 segment Quin count differs from root manifest: {}",
783 entry.locator
784 )));
785 }
786 }
787 Ok(())
788 }
789}
790
791impl Q42VolumeSegment {
792 pub fn ipfs_cid(&self) -> Option<&str> {
794 self.locator.strip_prefix("ipfs://")
795 }
796}
797
798fn validate_segment_locator(locator: &str) -> io::Result<()> {
801 if locator.is_empty() {
802 return Err(io::Error::new(
803 io::ErrorKind::InvalidInput,
804 "Q42 segment locator is empty",
805 ));
806 }
807 if let Some(cid) = locator.strip_prefix("ipfs://") {
808 if cid.is_empty() || !cid.bytes().all(|byte| byte.is_ascii_alphanumeric()) {
809 return Err(io::Error::new(
810 io::ErrorKind::InvalidInput,
811 "Q42 IPFS locator has an invalid CID",
812 ));
813 }
814 return Ok(());
815 }
816 let path = Path::new(locator);
817 if locator.contains(':')
818 || locator.starts_with('\\')
819 || locator.split(['/', '\\']).any(|seg| seg == "..")
820 || path.is_absolute()
821 || path.components().any(|component| {
822 matches!(
823 component,
824 Component::ParentDir | Component::RootDir | Component::Prefix(_)
825 )
826 })
827 {
828 return Err(io::Error::new(
829 io::ErrorKind::InvalidInput,
830 "Q42 segment locator must be a relative path or ipfs://CID",
831 ));
832 }
833 Ok(())
834}
835
836#[cfg(not(target_arch = "wasm32"))]
839pub struct Q42VolumeSet {
840 root: Q42Volume,
841 manifest: Q42VolumeManifest,
842 segments: Vec<Q42Volume>,
843 lexicon_segments: Vec<Q42Volume>,
844}
845
846#[cfg(not(target_arch = "wasm32"))]
847impl Q42VolumeSet {
848 pub fn open_root(path: &Path) -> io::Result<Self> {
851 let root = Q42Volume::open(path)?;
852 let manifest = root
853 .volume_manifest()?
854 .ok_or_else(|| invalid("Q42 root has no embedded volume manifest"))?;
855 let parent = path.parent().unwrap_or_else(|| Path::new("."));
856 let mut segments = Vec::with_capacity(manifest.segments.len());
857 for entry in &manifest.segments {
858 let segment_path = parent.join(&entry.locator);
859 if std::fs::metadata(&segment_path)?.len() != entry.byte_length {
860 return Err(invalid(format!(
861 "Q42 segment length differs from root manifest: {}",
862 entry.locator
863 )));
864 }
865 let segment = Q42Volume::open(&segment_path)?;
866 if segment.object_hash_bounds()
867 != Some((entry.first_object_hash, entry.last_object_hash))
868 {
869 return Err(invalid(format!(
870 "Q42 segment object bounds differ from root manifest: {}",
871 entry.locator
872 )));
873 }
874 segments.push(segment);
875 }
876 let mut lexicon_segments = Vec::with_capacity(manifest.lexicon_segments.len());
877 for entry in &manifest.lexicon_segments {
878 let segment_path = parent.join(&entry.locator);
879 if std::fs::metadata(&segment_path)?.len() != entry.byte_length {
880 return Err(invalid(format!(
881 "Q42 lexicon segment length differs from root manifest: {}",
882 entry.locator
883 )));
884 }
885 let segment = Q42Volume::open(&segment_path)?;
886 let view = segment
887 .lex_view()
888 .map_err(|error| invalid(format!("invalid Q42 lexicon segment: {error:?}")))?;
889 if view.hash_at(0) != Some(entry.first_hash)
890 || view.hash_at(view.entry_count().saturating_sub(1)) != Some(entry.last_hash)
891 {
892 return Err(invalid(format!(
893 "Q42 lexicon segment hash bounds differ from root manifest: {}",
894 entry.locator
895 )));
896 }
897 lexicon_segments.push(segment);
898 }
899 Ok(Self {
900 root,
901 manifest,
902 segments,
903 lexicon_segments,
904 })
905 }
906
907 pub fn root(&self) -> &Q42Volume {
909 &self.root
910 }
911
912 pub fn manifest(&self) -> &Q42VolumeManifest {
914 &self.manifest
915 }
916 pub fn segments(&self) -> &[Q42Volume] {
918 &self.segments
919 }
920
921 pub fn lexicon_segments(&self) -> &[Q42Volume] {
923 &self.lexicon_segments
924 }
925
926 pub fn lookup_parts(&self, hash: u64) -> Option<(&str, &str)> {
931 if let Ok(root) = self.root.lex_view() {
932 if let Some(value) = root.lookup_parts(hash) {
933 return Some(value);
934 }
935 }
936 let mut lo = 0usize;
937 let mut hi = self.manifest.lexicon_segments.len();
938 while lo < hi {
939 let mid = lo + (hi - lo) / 2;
940 if self.manifest.lexicon_segments[mid].first_hash <= hash {
941 lo = mid + 1;
942 } else {
943 hi = mid;
944 }
945 }
946 let index = lo.checked_sub(1)?;
947 let descriptor = self.manifest.lexicon_segments.get(index)?;
948 if hash > descriptor.last_hash {
949 return None;
950 }
951 self.lexicon_segments
952 .get(index)?
953 .lex_view()
954 .ok()?
955 .lookup_parts(hash)
956 }
957
958 pub fn lookup_owned(&self, hash: u64) -> Option<String> {
960 let (ns, local) = self.lookup_parts(hash)?;
961 let mut out = String::with_capacity(ns.len() + local.len());
962 out.push_str(ns);
963 out.push_str(local);
964 Some(out)
965 }
966
967 pub fn lookup_hash(&self, hash: u64) -> Option<&str> {
973 match self.lookup_parts(hash) {
974 Some(("", verbatim)) => Some(verbatim),
975 _ => None,
976 }
977 }
978
979 pub fn verify_segment_hashes(&self, root_path: &Path) -> io::Result<()> {
983 let parent = root_path.parent().unwrap_or_else(|| Path::new("."));
984 for entry in &self.manifest.segments {
985 if sha256_file(&parent.join(&entry.locator))? != entry.sha256 {
986 return Err(invalid(format!(
987 "Q42 segment digest differs from root manifest: {}",
988 entry.locator
989 )));
990 }
991 }
992 for entry in &self.manifest.lexicon_segments {
993 if sha256_file(&parent.join(&entry.locator))? != entry.sha256 {
994 return Err(invalid(format!(
995 "Q42 lexicon segment digest differs from root manifest: {}",
996 entry.locator
997 )));
998 }
999 }
1000 Ok(())
1001 }
1002
1003 pub fn verify_all(&self, root_path: &Path) -> io::Result<Q42VerificationReceipt> {
1007 self.verify_segment_hashes(root_path)?;
1008 let mut receipt = Q42VerificationReceipt {
1009 blocks_verified: 0,
1010 quins_verified: 0,
1011 };
1012 for (entry, segment) in self.manifest.segments.iter().zip(&self.segments) {
1013 let segment_receipt = segment.verify_all_blocks()?;
1014 if segment_receipt.quins_verified != entry.quin_count {
1015 return Err(invalid(format!(
1016 "Q42 verified Quin count differs from root manifest: {}",
1017 entry.locator
1018 )));
1019 }
1020 receipt.blocks_verified = receipt
1021 .blocks_verified
1022 .checked_add(segment_receipt.blocks_verified)
1023 .ok_or_else(|| invalid("Q42 verified block count overflows"))?;
1024 receipt.quins_verified = receipt
1025 .quins_verified
1026 .checked_add(segment_receipt.quins_verified)
1027 .ok_or_else(|| invalid("Q42 verified Quin count overflows"))?;
1028 }
1029 Ok(receipt)
1030 }
1031}
1032
1033#[cfg(not(target_arch = "wasm32"))]
1034fn sha256_file(path: &Path) -> io::Result<[u8; 32]> {
1036 let mut file = File::open(path)?;
1037 let mut hasher = Sha256::new();
1038 let mut buffer = [0u8; 64 * 1024];
1039 loop {
1040 let read = file.read(&mut buffer)?;
1041 if read == 0 {
1042 break;
1043 }
1044 hasher.update(&buffer[..read]);
1045 }
1046 Ok(hasher.finalize().into())
1047}
1048
1049#[cfg(not(target_arch = "wasm32"))]
1050pub fn root_relative_path(root: &Path, segment: &Path) -> io::Result<String> {
1054 let parent = root.parent().unwrap_or_else(|| Path::new("."));
1055 let relative: PathBuf = segment
1056 .strip_prefix(parent)
1057 .map_err(|_| {
1058 io::Error::new(
1059 io::ErrorKind::InvalidInput,
1060 "segment must be below the root Q42 directory",
1061 )
1062 })?
1063 .to_owned();
1064 relative.to_str().map(str::to_owned).ok_or_else(|| {
1065 io::Error::new(
1066 io::ErrorKind::InvalidInput,
1067 "segment path is not valid UTF-8",
1068 )
1069 })
1070}
1071
1072#[cfg(test)]
1073mod tests {
1074 use super::*;
1075
1076 fn segment(locator: &str) -> Q42VolumeSegment {
1077 Q42VolumeSegment {
1078 locator: locator.to_owned(),
1079 byte_length: 1,
1080 first_object_hash: 1,
1081 last_object_hash: 1,
1082 quin_count: 1,
1083 sha256: [7; 32],
1084 }
1085 }
1086
1087 #[test]
1088 fn manifest_accepts_immutable_ipfs_cids_and_rejects_escaping_paths() {
1089 let manifest = Q42VolumeManifest {
1090 generation: 1,
1091 segments: vec![segment("ipfs://bafybeigdyrzt5v5cbe")],
1092 lexicon_segments: vec![],
1093 };
1094 let bytes = manifest.encode().unwrap();
1095 assert_eq!(Q42VolumeManifest::decode(&bytes).unwrap(), manifest);
1096 assert_eq!(manifest.segments[0].ipfs_cid(), Some("bafybeigdyrzt5v5cbe"));
1097
1098 for locator in [
1099 "../segment.q42",
1100 "C:\\segment.q42",
1101 "/segment.q42",
1102 "ipfs://bad/path",
1103 ] {
1104 let invalid = Q42VolumeManifest {
1105 generation: 1,
1106 segments: vec![segment(locator)],
1107 lexicon_segments: vec![],
1108 };
1109 assert!(
1110 invalid.validate().is_err(),
1111 "locator {locator:?} must be rejected"
1112 );
1113 }
1114 }
1115
1116 #[test]
1117 fn manifest_pages_all_boundary_spanning_segments_without_allocation() {
1118 let mut first = segment("one.q42");
1119 let mut second = segment("two.q42");
1120 let mut third = segment("three.q42");
1121 first.first_object_hash = 41;
1122 first.last_object_hash = 42;
1123 second.first_object_hash = 42;
1124 second.last_object_hash = 42;
1125 third.first_object_hash = 42;
1126 third.last_object_hash = 43;
1127 let manifest = Q42VolumeManifest {
1128 generation: 1,
1129 segments: vec![first, second, third],
1130 lexicon_segments: vec![],
1131 };
1132 manifest.validate().unwrap();
1133 let mut page = [usize::MAX; 2];
1134 let first_page = manifest
1135 .segment_indices_for_object_into(42, 0, &mut page)
1136 .unwrap()
1137 .unwrap();
1138 assert_eq!(first_page.range, Q42SegmentMatchRange { start: 0, end: 3 });
1139 assert_eq!(&page, &[0, 1]);
1140 assert_eq!(first_page.next_cursor, Some(2));
1141 let second_page = manifest
1142 .segment_indices_for_object_into(42, 2, &mut page)
1143 .unwrap()
1144 .unwrap();
1145 assert_eq!(second_page.returned, 1);
1146 assert_eq!(page[0], 2);
1147 assert_eq!(second_page.next_cursor, None);
1148 }
1149}