1use std::cell::{Cell, RefCell};
42use std::collections::{BTreeMap, BTreeSet};
43use std::fs::File;
44use std::io::{Read, Seek, SeekFrom};
45use std::os::unix::fs::FileExt;
46use std::path::{Path, PathBuf};
47
48use sha2::{Digest, Sha256};
49
50use crate::container::header::{HEADER_LEN, Header};
51use crate::container::record::{RECORD_HEADER_LEN, RECORD_TRAILER_LEN, RecordTag, read_record_at};
52use crate::dra::Program;
53use crate::dra::op::Op;
54use crate::error::{Error, Result};
55use crate::limits::Limits;
56use crate::store::Id;
57
58use super::FieldStore;
59use super::dag::SourceServer;
60use super::manifest::{FieldId, FieldRoot};
61use super::observe::{ObserveRequest, ObserveStats};
62
63const COARSE_MAGIC: [u8; 4] = *b"VCI1";
65const MAX_UNITS: u64 = 1 << 20;
67const ENTRY_LEN: usize = 17;
69
70#[derive(Debug, Clone, Copy, PartialEq, Eq)]
72#[repr(u8)]
73pub enum UnitKind {
74 Gap = 0,
76 AuthorityLeaf = 1,
78 PdfObject = 2,
80 PdfTail = 3,
82 ZipMember = 4,
84 ZipDirectory = 5,
86 ParquetColumnChunk = 6,
88 ParquetFooter = 7,
90}
91
92impl UnitKind {
93 fn code(self) -> u8 {
94 self as u8
95 }
96
97 fn from_code(c: u8) -> Result<Self> {
98 Ok(match c {
99 0 => Self::Gap,
100 1 => Self::AuthorityLeaf,
101 2 => Self::PdfObject,
102 3 => Self::PdfTail,
103 4 => Self::ZipMember,
104 5 => Self::ZipDirectory,
105 6 => Self::ParquetColumnChunk,
106 7 => Self::ParquetFooter,
107 _ => return Err(Error::invalid_container("unknown coarse unit kind")),
108 })
109 }
110}
111
112#[derive(Debug, Clone, Copy)]
114pub struct CoarseUnit {
115 pub kind: UnitKind,
117 pub id: u32,
119 pub offset: u64,
121 pub len: u32,
123}
124
125#[derive(Debug, Clone)]
127pub struct CoarseIndex {
128 pub format: u8,
130 pub source_len: u64,
132 pub source_sha256: [u8; 32],
134 pub object_base: u64,
136 pub object_count: u32,
138 pub graph_ops: u32,
140 pub units: Vec<CoarseUnit>,
142}
143
144pub fn format_name(code: u8) -> &'static str {
146 match code {
147 1 => "pdf",
148 2 => "zip",
149 3 => "parquet",
150 _ => "unsupported",
151 }
152}
153
154impl CoarseIndex {
155 pub fn encode(&self) -> Vec<u8> {
157 let mut out = Vec::with_capacity(69 + self.units.len() * ENTRY_LEN);
158 out.extend_from_slice(&COARSE_MAGIC);
159 out.push(self.format);
160 out.extend_from_slice(&self.object_count.to_le_bytes());
161 out.extend_from_slice(&self.graph_ops.to_le_bytes());
162 out.extend_from_slice(&self.source_len.to_le_bytes());
163 out.extend_from_slice(&self.object_base.to_le_bytes());
164 out.extend_from_slice(&self.source_sha256);
165 out.extend_from_slice(&(self.units.len() as u32).to_le_bytes());
166 for u in &self.units {
167 out.push(u.kind.code());
168 out.extend_from_slice(&u.id.to_le_bytes());
169 out.extend_from_slice(&u.offset.to_le_bytes());
170 out.extend_from_slice(&u.len.to_le_bytes());
171 }
172 out
173 }
174
175 pub fn decode(bytes: &[u8], limits: Limits) -> Result<Self> {
177 let mut p = 0usize;
178 let magic = bytes
179 .get(p..p + 4)
180 .ok_or_else(|| Error::invalid_container("coarse index truncated (magic)"))?;
181 if magic != COARSE_MAGIC {
182 return Err(Error::invalid_container("coarse index magic mismatch"));
183 }
184 p += 4;
185 let format = *bytes
186 .get(p)
187 .ok_or_else(|| Error::invalid_container("coarse index truncated (format)"))?;
188 p += 1;
189 let object_count = read_u32(bytes, &mut p)?;
190 let graph_ops = read_u32(bytes, &mut p)?;
191 let source_len = read_u64(bytes, &mut p)?;
192 let object_base = read_u64(bytes, &mut p)?;
193 let sha = bytes
194 .get(p..p + 32)
195 .ok_or_else(|| Error::invalid_container("coarse index truncated (sha)"))?;
196 let mut source_sha256 = [0u8; 32];
197 source_sha256.copy_from_slice(sha);
198 p += 32;
199 let count = u64::from(read_u32(bytes, &mut p)?);
200 if count > MAX_UNITS || count > u64::from(limits.max_record_len) {
201 return Err(Error::resource_limit(
202 "coarse index unit count exceeds limit",
203 ));
204 }
205 let need = (count as usize)
206 .checked_mul(ENTRY_LEN)
207 .ok_or_else(|| Error::resource_limit("coarse index size overflow"))?;
208 if bytes.len().saturating_sub(p) < need {
209 return Err(Error::invalid_container("coarse index truncated (units)"));
210 }
211 let mut units = Vec::with_capacity(count as usize);
212 for _ in 0..count {
213 let kind = UnitKind::from_code(bytes[p])?;
214 p += 1;
215 let id = read_u32(bytes, &mut p)?;
216 let offset = read_u64(bytes, &mut p)?;
217 let len = read_u32(bytes, &mut p)?;
218 units.push(CoarseUnit {
219 kind,
220 id,
221 offset,
222 len,
223 });
224 }
225 if p != bytes.len() {
226 return Err(Error::invalid_container("coarse index has trailing bytes"));
227 }
228 let index = CoarseIndex {
229 format,
230 source_len,
231 source_sha256,
232 object_base,
233 object_count,
234 graph_ops,
235 units,
236 };
237 index.validate()?;
238 Ok(index)
239 }
240
241 fn validate(&self) -> Result<()> {
243 let mut cursor = 0u64;
244 for u in &self.units {
245 let end = u
246 .offset
247 .checked_add(u64::from(u.len))
248 .ok_or_else(|| Error::invalid_container("coarse unit length overflow"))?;
249 if u.offset != cursor || end > self.source_len {
250 return Err(Error::invalid_container(
251 "coarse units are not an ascending partition of the source",
252 ));
253 }
254 cursor = end;
255 }
256 if cursor != self.source_len {
257 return Err(Error::invalid_container(
258 "coarse units do not cover the whole source",
259 ));
260 }
261 Ok(())
262 }
263
264 #[allow(dead_code)]
266 fn covering(&self, offset: u64, end: u64) -> Vec<usize> {
267 let mut out = Vec::new();
268 for (i, u) in self.units.iter().enumerate() {
269 let ue = u.offset + u64::from(u.len);
270 if u.offset < end && offset < ue {
271 out.push(i);
272 }
273 }
274 out
275 }
276
277 pub fn encoded_len(&self) -> u64 {
279 self.encode().len() as u64
280 }
281}
282
283fn read_u32(bytes: &[u8], p: &mut usize) -> Result<u32> {
284 let s = bytes
285 .get(*p..*p + 4)
286 .ok_or_else(|| Error::invalid_container("coarse index truncated"))?;
287 *p += 4;
288 Ok(u32::from_le_bytes([s[0], s[1], s[2], s[3]]))
289}
290
291fn read_u64(bytes: &[u8], p: &mut usize) -> Result<u64> {
292 let s = bytes
293 .get(*p..*p + 8)
294 .ok_or_else(|| Error::invalid_container("coarse index truncated"))?;
295 *p += 8;
296 Ok(u64::from_le_bytes([
297 s[0], s[1], s[2], s[3], s[4], s[5], s[6], s[7],
298 ]))
299}
300
301fn push(units: &mut Vec<CoarseUnit>, kind: UnitKind, id: u32, offset: u64, len: u64, total: u64) {
306 if len == 0 || offset >= total || u32::try_from(len).is_err() {
307 return;
308 }
309 let capped = len.min(total - offset);
310 units.push(CoarseUnit {
311 kind,
312 id,
313 offset,
314 len: capped as u32,
315 });
316}
317
318fn partition(mut units: Vec<CoarseUnit>, total: u64) -> Vec<CoarseUnit> {
321 units.retain(|u| u.len > 0 && u.offset < total);
322 units.sort_by(|a, b| a.offset.cmp(&b.offset).then(a.len.cmp(&b.len)));
323 let mut out: Vec<CoarseUnit> = Vec::new();
324 let mut cursor = 0u64;
325 for u in units {
326 let start = u.offset.max(cursor);
327 let end = u.offset + u64::from(u.len);
328 if end <= cursor {
329 continue;
330 }
331 if start > cursor {
332 out.push(CoarseUnit {
333 kind: UnitKind::Gap,
334 id: 0,
335 offset: cursor,
336 len: (start - cursor) as u32,
337 });
338 }
339 let len = (end - start) as u32;
340 out.push(CoarseUnit {
341 kind: u.kind,
342 id: u.id,
343 offset: start,
344 len,
345 });
346 cursor = end;
347 }
348 if cursor < total {
349 out.push(CoarseUnit {
350 kind: UnitKind::Gap,
351 id: 0,
352 offset: cursor,
353 len: (total - cursor) as u32,
354 });
355 }
356 out
357}
358
359fn is_word(b: u8) -> bool {
360 b.is_ascii_alphanumeric() || b == b'_'
361}
362
363fn find(hay: &[u8], needle: &[u8]) -> Option<usize> {
364 if needle.is_empty() || hay.len() < needle.len() {
365 return None;
366 }
367 let first = needle[0];
368 let mut i = 0;
369 while i + needle.len() <= hay.len() {
370 if hay[i] == first && &hay[i..i + needle.len()] == needle {
371 return Some(i);
372 }
373 i += 1;
374 }
375 None
376}
377
378fn rfind(hay: &[u8], needle: &[u8]) -> Option<usize> {
379 if needle.is_empty() || hay.len() < needle.len() {
380 return None;
381 }
382 let mut i = hay.len() - needle.len();
383 loop {
384 if &hay[i..i + needle.len()] == needle {
385 return Some(i);
386 }
387 if i == 0 {
388 return None;
389 }
390 i -= 1;
391 }
392}
393
394fn obj_header_start(d: &[u8], objp: usize) -> Option<usize> {
395 let mut i = objp;
396 while i > 0 && d[i - 1].is_ascii_whitespace() {
397 i -= 1;
398 }
399 let g_end = i;
400 while i > 0 && d[i - 1].is_ascii_digit() {
401 i -= 1;
402 }
403 if i == g_end {
404 return None;
405 }
406 while i > 0 && d[i - 1].is_ascii_whitespace() {
407 i -= 1;
408 }
409 let n_end = i;
410 while i > 0 && d[i - 1].is_ascii_digit() {
411 i -= 1;
412 }
413 if i == n_end {
414 return None;
415 }
416 Some(i)
417}
418
419fn pdf_units(data: &[u8], units: &mut Vec<CoarseUnit>) {
420 let n = data.len();
421 let total = n as u64;
422 let mut pos = 0usize;
423 let mut id = 0u32;
424 while pos + 3 <= n {
425 if &data[pos..pos + 3] == b"obj"
426 && (pos + 3 == n || !is_word(data[pos + 3]))
427 && let Some(start) = obj_header_start(data, pos)
428 {
429 match find(&data[pos + 3..], b"endobj") {
430 Some(e) => {
431 let end = pos + 3 + e + b"endobj".len();
432 push(
433 units,
434 UnitKind::PdfObject,
435 id,
436 start as u64,
437 (end - start) as u64,
438 total,
439 );
440 id += 1;
441 pos = end;
442 continue;
443 }
444 None => break,
448 }
449 }
450 pos += 1;
451 }
452 if let Some(x) = rfind(data, b"startxref") {
453 push(units, UnitKind::PdfTail, 0, x as u64, (n - x) as u64, total);
454 }
455}
456
457fn u16le(d: &[u8], i: usize) -> Option<u16> {
458 let s = d.get(i..i + 2)?;
459 Some(u16::from_le_bytes([s[0], s[1]]))
460}
461
462fn u32le(d: &[u8], i: usize) -> Option<u32> {
463 let s = d.get(i..i + 4)?;
464 Some(u32::from_le_bytes([s[0], s[1], s[2], s[3]]))
465}
466
467fn zip_units(data: &[u8], units: &mut Vec<CoarseUnit>) -> Result<()> {
470 let n = data.len();
471 let total = n as u64;
472 let search_from = n.saturating_sub(65_557);
473 let eocd = rfind(&data[search_from..], b"PK\x05\x06")
474 .map(|i| i + search_from)
475 .ok_or_else(|| Error::invalid_container("ZIP: no end-of-central-directory"))?;
476 let disk = u16le(data, eocd + 4).unwrap_or(1);
477 let entries_disk = u16le(data, eocd + 8).unwrap_or(0);
478 let entries_total = u16le(data, eocd + 10).unwrap_or(0);
479 let cd_size = u32le(data, eocd + 12).unwrap_or(0);
480 let cd_off = u32le(data, eocd + 16).unwrap_or(0);
481 if disk != 0 || entries_disk != entries_total {
482 return Err(Error::unsupported_feature(
483 "ZIP: multi-disk archives declined",
484 ));
485 }
486 if entries_total == u16::MAX || cd_size == u32::MAX || cd_off == u32::MAX {
487 return Err(Error::unsupported_feature("ZIP64 archives declined"));
488 }
489 let cd_off = cd_off as usize;
490 if cd_off > n {
491 return Err(Error::invalid_container(
492 "ZIP: central directory offset out of range",
493 ));
494 }
495 let mut p = cd_off;
496 for i in 0..entries_total {
497 if data.get(p..p + 4) != Some(b"PK\x01\x02") {
498 return Err(Error::invalid_container("ZIP: bad central-directory entry"));
499 }
500 let method = u16le(data, p + 10).unwrap_or(0);
501 let comp = u32le(data, p + 20).unwrap_or(0);
502 let name_len = u16le(data, p + 28).unwrap_or(0) as usize;
503 let extra_len = u16le(data, p + 30).unwrap_or(0) as usize;
504 let comment_len = u16le(data, p + 32).unwrap_or(0) as usize;
505 let lo_raw = u32le(data, p + 42).unwrap_or(0);
506 let _ = method;
507 if comp == u32::MAX || lo_raw == u32::MAX {
508 return Err(Error::unsupported_feature("ZIP64 member declined"));
509 }
510 let lo = lo_raw as usize;
511 if data.get(lo..lo + 4) != Some(b"PK\x03\x04") {
513 return Err(Error::invalid_container("ZIP: bad local header"));
514 }
515 let ln = u16le(data, lo + 26).unwrap_or(0) as usize;
516 let le = u16le(data, lo + 28).unwrap_or(0) as usize;
517 let start = lo as u64;
518 let end = (lo as u64)
519 .saturating_add(30)
520 .saturating_add(ln as u64)
521 .saturating_add(le as u64)
522 .saturating_add(comp as u64);
523 if end > total || end < start {
524 return Err(Error::invalid_container("ZIP: member span out of range"));
525 }
526 units.push(CoarseUnit {
527 kind: UnitKind::ZipMember,
528 id: i as u32,
529 offset: start,
530 len: (end - start) as u32,
531 });
532 p = p
533 .checked_add(46 + name_len + extra_len + comment_len)
534 .ok_or_else(|| Error::invalid_container("ZIP: central directory overflow"))?;
535 }
536 push(
537 units,
538 UnitKind::ZipDirectory,
539 0,
540 cd_off as u64,
541 total.saturating_sub(cd_off as u64),
542 total,
543 );
544 Ok(())
545}
546
547#[derive(Debug)]
549enum TVal {
550 Bool,
551 Int(i64),
552 Bytes,
553 List(Vec<TVal>),
554 Struct(Vec<(i16, TVal)>),
555 Other,
556}
557
558const MAX_THRIFT_DEPTH: u32 = 64;
561
562struct TC<'a> {
563 b: &'a [u8],
564 i: usize,
565 depth: u32,
566}
567
568impl<'a> TC<'a> {
569 fn byte(&mut self) -> Result<u8> {
570 let v = *self
571 .b
572 .get(self.i)
573 .ok_or_else(|| Error::invalid_container("thrift: truncated"))?;
574 self.i += 1;
575 Ok(v)
576 }
577
578 fn varint(&mut self) -> Result<u64> {
579 let mut shift = 0u32;
580 let mut out = 0u64;
581 loop {
582 let c = self.byte()?;
583 out |= u64::from(c & 0x7F) << shift;
584 if c & 0x80 == 0 {
585 return Ok(out);
586 }
587 shift += 7;
588 if shift > 63 {
589 return Err(Error::invalid_container("thrift: varint overflow"));
590 }
591 }
592 }
593
594 fn zig(&mut self) -> Result<i64> {
595 let u = self.varint()?;
596 Ok(((u >> 1) as i64) ^ -((u & 1) as i64))
597 }
598
599 fn skip(&mut self, t: u8) -> Result<TVal> {
600 Ok(match t {
601 1 | 2 => TVal::Bool,
602 3 => TVal::Int(i64::from(self.byte()?)),
603 4..=6 => TVal::Int(self.zig()?),
604 7 => {
605 self.i = self
606 .i
607 .checked_add(8)
608 .ok_or_else(|| Error::invalid_container("thrift: overflow"))?;
609 TVal::Other
610 }
611 8 => {
612 let ln = self.varint()? as usize;
613 if self.b.get(self.i..self.i + ln).is_none() {
614 return Err(Error::invalid_container("thrift: truncated binary"));
615 }
616 self.i += ln;
617 TVal::Bytes
618 }
619 9 | 10 => {
620 let h = self.byte()?;
621 let mut size = u64::from((h & 0xF0) >> 4);
622 let et = h & 0x0F;
623 if size == 15 {
624 size = self.varint()?;
625 }
626 if size > MAX_UNITS {
627 return Err(Error::resource_limit("thrift: list too long"));
628 }
629 self.descend()?;
630 let mut items = Vec::with_capacity(size as usize);
631 for _ in 0..size {
632 items.push(self.skip(et)?);
633 }
634 self.ascend();
635 TVal::List(items)
636 }
637 11 => {
638 let size = self.varint()?;
639 if size == 0 {
640 TVal::Other
641 } else {
642 let kv = self.byte()?;
643 self.descend()?;
644 for _ in 0..size {
645 self.skip((kv & 0xF0) >> 4)?;
646 self.skip(kv & 0x0F)?;
647 }
648 self.ascend();
649 TVal::Other
650 }
651 }
652 12 => {
653 self.descend()?;
654 let s = TVal::Struct(self.read_struct()?);
655 self.ascend();
656 s
657 }
658 _ => return Err(Error::invalid_container("thrift: unknown type")),
659 })
660 }
661
662 fn descend(&mut self) -> Result<()> {
663 self.depth += 1;
664 if self.depth > MAX_THRIFT_DEPTH {
665 return Err(Error::invalid_container("thrift: nesting too deep"));
666 }
667 Ok(())
668 }
669
670 fn ascend(&mut self) {
671 self.depth = self.depth.saturating_sub(1);
672 }
673
674 fn read_struct(&mut self) -> Result<Vec<(i16, TVal)>> {
675 let mut out = Vec::new();
676 let mut last: i16 = 0;
677 loop {
678 let h = self.byte()?;
679 if h == 0 {
680 return Ok(out);
681 }
682 let delta = i16::from((h & 0xF0) >> 4);
683 let t = h & 0x0F;
684 let fid = if delta == 0 {
685 self.zig()? as i16
686 } else {
687 last + delta
688 };
689 last = fid;
690 let v = self.skip(t)?;
691 out.push((fid, v));
692 }
693 }
694}
695
696fn struct_field(fields: &[(i16, TVal)], id: i16) -> Option<&TVal> {
697 fields.iter().find(|(k, _)| *k == id).map(|(_, v)| v)
698}
699
700fn as_list(v: Option<&TVal>) -> &[TVal] {
701 match v {
702 Some(TVal::List(l)) => l,
703 _ => &[],
704 }
705}
706
707fn as_i64(v: Option<&TVal>) -> Option<i64> {
708 match v {
709 Some(TVal::Int(i)) => Some(*i),
710 _ => None,
711 }
712}
713
714fn parquet_units(data: &[u8], units: &mut Vec<CoarseUnit>) -> Result<()> {
717 let n = data.len();
718 let total = n as u64;
719 let flen =
720 u32le(data, n - 8).ok_or_else(|| Error::invalid_container("parquet: short"))? as usize;
721 if flen + 8 > n || flen == 0 {
722 return Err(Error::invalid_container("parquet: bad footer length"));
723 }
724 let fstart = n - 8 - flen;
725 let mut tc = TC {
726 b: &data[fstart..n - 8],
727 i: 0,
728 depth: 0,
729 };
730 let meta = tc.read_struct()?;
731 let rgs = as_list(struct_field(&meta, 4));
732 let mut id = 0u32;
733 for rg in rgs {
734 let TVal::Struct(rg_fields) = rg else {
735 continue;
736 };
737 for col in as_list(struct_field(rg_fields, 1)) {
738 let TVal::Struct(col_fields) = col else {
739 continue;
740 };
741 let Some(TVal::Struct(cm)) = struct_field(col_fields, 3) else {
742 continue;
743 };
744 let start = as_i64(struct_field(cm, 11))
745 .or_else(|| as_i64(struct_field(cm, 9)))
746 .unwrap_or(0);
747 let size = as_i64(struct_field(cm, 7)).unwrap_or(0);
748 if start < 0 || size <= 0 {
749 continue;
750 }
751 let start = start as u64;
752 let size = size as u64;
753 if start + size > total || size > u64::from(u32::MAX) {
754 return Err(Error::invalid_container(
755 "parquet: column chunk out of range",
756 ));
757 }
758 units.push(CoarseUnit {
759 kind: UnitKind::ParquetColumnChunk,
760 id,
761 offset: start,
762 len: size as u32,
763 });
764 id += 1;
765 }
766 }
767 push(
768 units,
769 UnitKind::ParquetFooter,
770 0,
771 fstart as u64,
772 (8 + flen) as u64,
773 total,
774 );
775 Ok(())
776}
777
778pub fn build_units(source: &[u8]) -> (u8, Vec<CoarseUnit>) {
780 let n = source.len() as u64;
781 let mut units: Vec<CoarseUnit> = Vec::new();
782 let format = if source.starts_with(b"%PDF-") {
783 pdf_units(source, &mut units);
784 1
785 } else if source.starts_with(b"PK\x03\x04") && zip_units(source, &mut units).is_ok() {
786 2
787 } else if source.len() >= 12
788 && source.starts_with(b"PAR1")
789 && source.ends_with(b"PAR1")
790 && parquet_units(source, &mut units).is_ok()
791 {
792 3
793 } else {
794 units.clear();
795 0
796 };
797 if format == 0 {
798 units.clear();
799 units.push(CoarseUnit {
800 kind: UnitKind::AuthorityLeaf,
801 id: 0,
802 offset: 0,
803 len: u32::try_from(n).unwrap_or(u32::MAX),
804 });
805 }
806 (format, partition(units, n))
807}
808
809pub struct Authority {
816 pub object_base: u64,
818 pub payload: Vec<u8>,
820 pub object_count: u32,
822 pub graph_ops: u32,
824}
825
826pub fn discover_authority(
833 descriptor_path: &Path,
834 manifest: &FieldRoot,
835 limits: Limits,
836) -> Result<Option<Authority>> {
837 let mut file =
838 File::open(descriptor_path).map_err(|e| Error::io(format!("opening descriptor: {e}")))?;
839 let mut hdr = [0u8; HEADER_LEN];
840 file.read_exact(&mut hdr)
841 .map_err(|_| Error::invalid_container("truncated header"))?;
842 let _header = Header::decode(&hdr)?;
843 let file_len = file
844 .seek(SeekFrom::End(0))
845 .map_err(|e| Error::io(format!("seek to end failed: {e}")))?;
846 let mut object_sites: Vec<(u64, u32)> = Vec::new();
847 let mut graph: Option<Vec<u8>> = None;
848 let mut pos = HEADER_LEN as u64;
849 while pos < file_len {
850 let mut rec_hdr = [0u8; RECORD_HEADER_LEN];
851 file.seek(SeekFrom::Start(pos))
852 .map_err(|e| Error::io(format!("seek failed: {e}")))?;
853 file.read_exact(&mut rec_hdr)
854 .map_err(|_| Error::invalid_container("truncated record header"))?;
855 let tag = rec_hdr[0];
856 let len = u32::from_le_bytes([rec_hdr[4], rec_hdr[5], rec_hdr[6], rec_hdr[7]]);
857 let total = RECORD_HEADER_LEN as u64 + u64::from(len) + RECORD_TRAILER_LEN as u64;
858 let end = pos
859 .checked_add(total)
860 .ok_or_else(|| Error::invalid_container("record length overflow"))?;
861 if end > file_len {
862 return Err(Error::invalid_container("truncated record"));
863 }
864 match RecordTag::from_u8(tag) {
865 Some(RecordTag::Object) => {
866 object_sites.push((pos + RECORD_HEADER_LEN as u64, len));
867 }
868 Some(RecordTag::Graph) => {
869 let rec = read_record_at(&mut file, pos, limits)?;
870 graph = Some(rec.payload);
871 }
872 Some(RecordTag::ExternalRef) => return Ok(None),
873 Some(RecordTag::Trailer) => break,
874 _ => {}
875 }
876 pos = end;
877 }
878 if object_sites.len() != 1 {
879 return Ok(None);
880 }
881 let Some(graph) = graph else {
882 return Ok(None);
883 };
884 let program = Program::decode(&graph, limits)?;
885 if program.ops.len() != 1 || !matches!(program.ops[0], Op::EmitObject { object_id: 0 }) {
886 return Ok(None);
887 }
888 let (object_base, object_len) = object_sites[0];
889 let mut payload = vec![0u8; object_len as usize];
890 file.read_exact_at(&mut payload, object_base)
891 .map_err(|e| Error::io(format!("reading authority object: {e}")))?;
892 let mut h = Sha256::new();
893 h.update(&payload);
894 let digest: [u8; 32] = h.finalize().into();
895 if digest != manifest.source_sha256 || payload.len() as u64 != manifest.source_len {
896 return Ok(None);
897 }
898 Ok(Some(Authority {
899 object_base,
900 payload,
901 object_count: 1,
902 graph_ops: 1,
903 }))
904}
905
906fn hex(bytes: &[u8]) -> String {
911 const HEX: &[u8; 16] = b"0123456789abcdef";
912 let mut s = String::with_capacity(bytes.len() * 2);
913 for b in bytes {
914 s.push(HEX[(b >> 4) as usize] as char);
915 s.push(HEX[(b & 0x0F) as usize] as char);
916 }
917 s
918}
919
920fn coarse_dir(root: &Path) -> PathBuf {
921 root.join("coarse")
922}
923
924pub fn index_path(root: &Path, descriptor_id: &[u8; 32]) -> PathBuf {
926 coarse_dir(root).join(format!("{}.idx", hex(descriptor_id)))
927}
928
929pub fn map_path(root: &Path, descriptor_id: &[u8; 32]) -> PathBuf {
931 coarse_dir(root).join(format!("{}.map", hex(descriptor_id)))
932}
933
934pub fn load_map(path: &Path) -> BTreeMap<String, Vec<usize>> {
936 let mut out = BTreeMap::new();
937 let Ok(text) = std::fs::read_to_string(path) else {
938 return out;
939 };
940 for line in text.lines() {
941 if let Some((k, v)) = line.split_once('\t') {
942 let units: Vec<usize> = v
943 .split(',')
944 .filter_map(|s| s.parse::<usize>().ok())
945 .collect();
946 out.insert(k.to_string(), units);
947 }
948 }
949 out
950}
951
952fn save_map(path: &Path, map: &BTreeMap<String, Vec<usize>>) {
953 let mut text = String::new();
954 for (k, v) in map {
955 let joined: Vec<String> = v.iter().map(usize::to_string).collect();
956 text.push_str(k);
957 text.push('\t');
958 text.push_str(&joined.join(","));
959 text.push('\n');
960 }
961 let _ = super::write_atomic(path, text.as_bytes());
962}
963
964pub struct CoarseSource {
971 file: File,
972 object_base: u64,
973 source_len: u64,
974 units: Vec<CoarseUnit>,
975 loaded: RefCell<Vec<Option<Vec<u8>>>>,
976 touched: RefCell<BTreeSet<usize>>,
980 expand: bool,
981 reads: Cell<u64>,
982 bytes_read: Cell<u64>,
983 misses: Cell<u64>,
984 covered_lo: Cell<u64>,
985 covered_hi: Cell<u64>,
986}
987
988impl CoarseSource {
989 fn new(descriptor_path: &Path, index: &CoarseIndex, expand: bool) -> Result<Self> {
990 let file = File::open(descriptor_path)
991 .map_err(|e| Error::io(format!("opening descriptor: {e}")))?;
992 let n = index.units.len();
993 Ok(CoarseSource {
994 file,
995 object_base: index.object_base,
996 source_len: index.source_len,
997 units: index.units.clone(),
998 loaded: RefCell::new(vec![None; n]),
999 touched: RefCell::new(BTreeSet::new()),
1000 expand,
1001 reads: Cell::new(0),
1002 bytes_read: Cell::new(0),
1003 misses: Cell::new(0),
1004 covered_lo: Cell::new(u64::MAX),
1005 covered_hi: Cell::new(0),
1006 })
1007 }
1008
1009 pub fn bytes_read(&self) -> u64 {
1011 self.bytes_read.get()
1012 }
1013
1014 pub fn reads(&self) -> u64 {
1016 self.reads.get()
1017 }
1018
1019 pub fn misses(&self) -> u64 {
1021 self.misses.get()
1022 }
1023
1024 pub fn touched_units(&self) -> Vec<usize> {
1026 self.touched.borrow().iter().copied().collect()
1027 }
1028
1029 pub fn covered_span(&self) -> Option<(u64, u64)> {
1031 if self.covered_hi.get() <= self.covered_lo.get() {
1032 None
1033 } else {
1034 Some((self.covered_lo.get(), self.covered_hi.get()))
1035 }
1036 }
1037
1038 fn fetch(&self, i: usize, loaded: &mut [Option<Vec<u8>>]) -> Result<()> {
1039 if loaded[i].is_some() {
1040 return Ok(());
1041 }
1042 if !self.expand {
1043 self.misses.set(self.misses.get() + 1);
1044 return Err(Error::unsupported_feature(
1045 "coarse plan did not cover a required unit; falling back to the full read",
1046 ));
1047 }
1048 self.read_unit(i, loaded)
1049 }
1050
1051 fn read_unit(&self, i: usize, loaded: &mut [Option<Vec<u8>>]) -> Result<()> {
1053 if loaded[i].is_some() {
1054 return Ok(());
1055 }
1056 let u = self.units[i];
1057 let mut buf = vec![0u8; u.len as usize];
1058 self.file
1059 .read_exact_at(&mut buf, self.object_base + u.offset)
1060 .map_err(|e| Error::io(format!("coarse pread failed: {e}")))?;
1061 self.bytes_read
1062 .set(self.bytes_read.get() + buf.len() as u64);
1063 self.reads.set(self.reads.get() + 1);
1064 self.touched.borrow_mut().insert(i);
1065 self.covered_lo.set(self.covered_lo.get().min(u.offset));
1066 self.covered_hi
1067 .set(self.covered_hi.get().max(u.offset + u64::from(u.len)));
1068 loaded[i] = Some(buf);
1069 Ok(())
1070 }
1071
1072 fn read_exact_range(&self, offset: u64, len: u64, limits: Limits) -> Result<Vec<u8>> {
1080 let end = offset
1081 .checked_add(len)
1082 .ok_or_else(|| Error::usage("fine-grained read range overflows"))?;
1083 if end > self.source_len {
1084 return Err(Error::usage(format!(
1085 "fine-grained read {offset}..{end} exceeds source length {}",
1086 self.source_len
1087 )));
1088 }
1089 if len > limits.max_input_bytes {
1090 return Err(Error::resource_limit(format!(
1091 "fine-grained read of {len} bytes exceeds max_input_bytes {}",
1092 limits.max_input_bytes
1093 )));
1094 }
1095 let mut buf = vec![0u8; len as usize];
1096 if len > 0 {
1097 self.file
1098 .read_exact_at(&mut buf, self.object_base + offset)
1099 .map_err(|e| Error::io(format!("fine-grained pread failed: {e}")))?;
1100 }
1101 self.bytes_read
1102 .set(self.bytes_read.get() + buf.len() as u64);
1103 self.reads.set(self.reads.get() + 1);
1104 if len > 0 {
1105 self.covered_lo.set(self.covered_lo.get().min(offset));
1110 self.covered_hi.set(self.covered_hi.get().max(end));
1111 }
1112 Ok(buf)
1113 }
1114
1115 fn prefetch(&self, ordinals: &[usize]) -> Result<()> {
1121 let mut loaded = self.loaded.borrow_mut();
1122 for &i in ordinals {
1123 if i < self.units.len() {
1124 self.read_unit(i, &mut loaded)?;
1125 }
1126 }
1127 Ok(())
1128 }
1129}
1130
1131impl SourceServer for CoarseSource {
1132 fn serve_range(&self, offset: u64, len: u64, _limits: Limits) -> Result<Vec<u8>> {
1133 let end = offset
1134 .checked_add(len)
1135 .ok_or_else(|| Error::usage("source slice end overflows"))?;
1136 if end > self.source_len {
1137 return Err(Error::usage(format!(
1138 "source slice {offset}..{end} exceeds source length {}",
1139 self.source_len
1140 )));
1141 }
1142 if len == 0 {
1143 return Ok(Vec::new());
1144 }
1145 let needed = {
1147 let mut v = Vec::new();
1148 for (i, u) in self.units.iter().enumerate() {
1149 let ue = u.offset + u64::from(u.len);
1150 if u.offset < end && offset < ue {
1151 v.push(i);
1152 }
1153 }
1154 v
1155 };
1156 if needed.is_empty() {
1157 return Err(Error::internal_invariant(
1158 "coarse units do not cover a requested source range",
1159 ));
1160 }
1161 let mut loaded = self.loaded.borrow_mut();
1162 for &i in &needed {
1163 self.fetch(i, &mut loaded)?;
1164 }
1165 let mut out = Vec::with_capacity((end - offset) as usize);
1166 let mut cursor = offset;
1167 for &i in &needed {
1168 let u = self.units[i];
1169 let ue = u.offset + u64::from(u.len);
1170 let s = cursor.max(u.offset);
1171 let e = end.min(ue);
1172 if e > s {
1173 if let Some(buf) = loaded[i].as_ref() {
1174 let a = (s - u.offset) as usize;
1175 let b = (e - u.offset) as usize;
1176 out.extend_from_slice(&buf[a..b]);
1177 }
1178 cursor = e;
1179 }
1180 }
1181 if cursor != end {
1182 return Err(Error::internal_invariant(
1183 "coarse units left a gap in a requested source range",
1184 ));
1185 }
1186 Ok(out)
1187 }
1188
1189 fn serve_document(&self, _limits: Limits) -> Result<Vec<u8>> {
1190 let mut buf = vec![0u8; self.source_len as usize];
1191 self.file
1192 .read_exact_at(&mut buf, self.object_base)
1193 .map_err(|e| Error::io(format!("coarse whole-object pread failed: {e}")))?;
1194 self.bytes_read
1195 .set(self.bytes_read.get() + buf.len() as u64);
1196 self.reads.set(self.reads.get() + 1);
1197 self.covered_lo.set(0);
1198 self.covered_hi.set(self.source_len);
1199 Ok(buf)
1200 }
1201
1202 fn read_exact(&self, offset: u64, len: u64, limits: Limits) -> Result<Option<Vec<u8>>> {
1203 Ok(Some(self.read_exact_range(offset, len, limits)?))
1204 }
1205
1206 fn exact_len(&self) -> Option<u64> {
1207 Some(self.source_len)
1208 }
1209
1210 fn zip_directory(&self, limits: Limits) -> Result<Option<(u64, Vec<u8>)>> {
1211 let Some(u) = self.units.iter().find(|u| u.kind == UnitKind::ZipDirectory) else {
1212 return Ok(None);
1213 };
1214 let bytes = self.read_exact_range(u.offset, u64::from(u.len), limits)?;
1215 Ok(Some((u.offset, bytes)))
1216 }
1217}
1218
1219pub struct BuildReport {
1225 pub format: &'static str,
1227 pub units: usize,
1229 pub native_units: usize,
1231 pub index_bytes: u64,
1233 pub store_bytes: u64,
1235 pub fraction: f64,
1237 pub path: String,
1239}
1240
1241fn dir_bytes(path: &Path) -> u64 {
1242 let mut total = 0u64;
1243 let Ok(rd) = std::fs::read_dir(path) else {
1244 return 0;
1245 };
1246 for entry in rd.flatten() {
1247 let Ok(ft) = entry.file_type() else { continue };
1248 if ft.is_dir() {
1249 total += dir_bytes(&entry.path());
1250 } else if let Ok(md) = entry.metadata() {
1251 total += md.len();
1252 }
1253 }
1254 total
1255}
1256
1257pub fn build(
1259 store_dir: &Path,
1260 packed: bool,
1261 field_hex: &str,
1262 limits: Limits,
1263) -> Result<BuildReport> {
1264 let store = if packed {
1265 FieldStore::open_packed(store_dir)?
1266 } else {
1267 FieldStore::open(store_dir)?
1268 };
1269 let field_id = FieldId::from_hex(field_hex)?;
1270 let manifest = store.get_field(&field_id)?;
1271 let descriptor_path = store
1272 .descriptor_path(&Id::from_bytes(manifest.descriptor_id))
1273 .ok_or_else(|| Error::unsupported_feature("descriptor is not a filesystem file"))?;
1274 let authority = discover_authority(&descriptor_path, &manifest, limits)?.ok_or_else(|| {
1275 Error::unsupported_feature(
1276 "descriptor is not a verbatim single authority object; coarse index not built",
1277 )
1278 })?;
1279 let (format, units) = build_units(&authority.payload);
1280 let native_units = units
1281 .iter()
1282 .filter(|u| u.kind != UnitKind::Gap && u.kind != UnitKind::AuthorityLeaf)
1283 .count();
1284 let index = CoarseIndex {
1285 format,
1286 source_len: manifest.source_len,
1287 source_sha256: manifest.source_sha256,
1288 object_base: authority.object_base,
1289 object_count: authority.object_count,
1290 graph_ops: authority.graph_ops,
1291 units,
1292 };
1293 let encoded = index.encode();
1294 let path = index_path(store.root(), &manifest.descriptor_id);
1295 super::write_atomic(&path, &encoded)?;
1296 let store_bytes = dir_bytes(store.root());
1297 let index_bytes = encoded.len() as u64;
1298 Ok(BuildReport {
1299 format: format_name(format),
1300 units: index.units.len(),
1301 native_units,
1302 index_bytes,
1303 store_bytes,
1304 fraction: if store_bytes == 0 {
1305 0.0
1306 } else {
1307 index_bytes as f64 / store_bytes as f64
1308 },
1309 path: path.display().to_string(),
1310 })
1311}
1312
1313pub struct ReadRow {
1315 pub request: String,
1317 pub outcome: &'static str,
1320 pub fallback_reason: String,
1322 pub units_read: usize,
1324 pub preads: u64,
1326 pub unit_bytes: u64,
1328 pub covered: Option<(u64, u64)>,
1330 pub manifest_bytes: u64,
1332 pub index_bytes: u64,
1334 pub seed_bytes: u64,
1336 pub dir_bytes: u64,
1338 pub closure_bytes: u64,
1340 pub answer_bytes: u64,
1342 pub matches_full: bool,
1344}
1345
1346fn same_answer(a: &super::provenance::FieldAnswer, b: &super::provenance::FieldAnswer) -> bool {
1347 a.value == b.value && a.basis == b.basis
1348}
1349
1350pub fn read(
1355 store_dir: &Path,
1356 packed: bool,
1357 field_hex: &str,
1358 requests: &[(String, ObserveRequest)],
1359 use_map: bool,
1360 limits: Limits,
1361) -> Result<Vec<ReadRow>> {
1362 let mut store = if packed {
1363 FieldStore::open_packed(store_dir)?
1364 } else {
1365 FieldStore::open(store_dir)?
1366 };
1367 let field_id = FieldId::from_hex(field_hex)?;
1368 let manifest = store.get_field(&field_id)?;
1369 let descriptor_path = store
1370 .descriptor_path(&Id::from_bytes(manifest.descriptor_id))
1371 .ok_or_else(|| Error::unsupported_feature("descriptor is not a filesystem file"))?;
1372 let idx_path = index_path(store.root(), &manifest.descriptor_id);
1373 let map_path = map_path(store.root(), &manifest.descriptor_id);
1374 let mut map = load_map(&map_path);
1375 let index = std::fs::read(&idx_path)
1376 .ok()
1377 .and_then(|b| CoarseIndex::decode(&b, limits).ok());
1378 let dir_bytes = std::fs::metadata(&idx_path).map(|m| m.len()).unwrap_or(0);
1379
1380 let mut rows = Vec::with_capacity(requests.len());
1381 for (line, req) in requests {
1382 let mut row = ReadRow {
1383 request: line.clone(),
1384 outcome: "fallback",
1385 fallback_reason: String::new(),
1386 units_read: 0,
1387 preads: 0,
1388 unit_bytes: 0,
1389 covered: None,
1390 manifest_bytes: 0,
1391 index_bytes: 0,
1392 seed_bytes: 0,
1393 dir_bytes,
1394 closure_bytes: 0,
1395 answer_bytes: 0,
1396 matches_full: false,
1397 };
1398 let mut cold = req.clone();
1401 cold.use_cache = false;
1402 let (full_answer, full_stats, _) =
1403 super::observe::observe(&mut store, &field_id, &cold, limits)?;
1404
1405 let plan = match (&index, use_map) {
1406 (Some(_), true) => map.get(line).cloned(),
1407 _ => None,
1408 };
1409 let expand = !(use_map && plan.is_some());
1410 let outcome: std::result::Result<(), String> = match &index {
1411 None => Err("no coarse index for this field".into()),
1412 Some(ix) if ix.format == 0 => {
1413 Err("coarse index declines this format (no native units)".into())
1414 }
1415 Some(ix) => {
1416 let src = CoarseSource::new(&descriptor_path, ix, expand)?;
1417 if let Some(units) = &plan {
1418 src.prefetch(units)?;
1419 }
1420 let res = super::observe::observe_with_source(
1421 &mut store,
1422 &manifest,
1423 field_id,
1424 &src,
1425 (ix.object_count, ix.graph_ops),
1426 &cold,
1427 limits,
1428 );
1429 match res {
1430 Ok((ans, stats, _)) if src.misses() == 0 => {
1431 row.outcome = "planned";
1432 row.units_read = src.touched_units().len();
1433 row.preads = src.reads();
1434 row.unit_bytes = src.bytes_read();
1435 row.covered = src.covered_span();
1436 row.manifest_bytes = stats.manifest_bytes_read;
1437 row.index_bytes = stats.index_bytes_read;
1438 row.seed_bytes = stats.seed_bytes_read;
1439 row.answer_bytes = stats.bytes_returned;
1440 row.closure_bytes = dir_bytes
1441 .saturating_add(src.bytes_read())
1442 .saturating_add(stats.manifest_bytes_read)
1443 .saturating_add(stats.index_bytes_read)
1444 .saturating_add(stats.seed_bytes_read);
1445 row.matches_full = same_answer(&ans, &full_answer);
1446 if !use_map {
1447 map.insert(line.clone(), src.touched_units());
1448 }
1449 Ok(())
1450 }
1451 Ok(_) => Err("coverage miss (uncovered unit)".into()),
1452 Err(e) => Err(format!("coarse lane declined: {e}")),
1453 }
1454 }
1455 };
1456 if let Err(reason) = outcome {
1457 row.outcome = "fallback";
1459 row.fallback_reason = reason;
1460 row.manifest_bytes = full_stats.manifest_bytes_read;
1461 row.index_bytes = full_stats.index_bytes_read;
1462 row.seed_bytes = full_stats.seed_bytes_read;
1463 row.answer_bytes = full_stats.bytes_returned;
1464 row.closure_bytes = full_stats.bytes_read;
1465 row.matches_full = true;
1466 }
1467 rows.push(row);
1468 }
1469 if !use_map {
1470 save_map(&map_path, &map);
1471 }
1472 Ok(rows)
1473}
1474
1475pub fn full_read(
1477 store_dir: &Path,
1478 packed: bool,
1479 field_hex: &str,
1480 requests: &[(String, ObserveRequest)],
1481 limits: Limits,
1482) -> Result<Vec<ObserveStats>> {
1483 let mut store = if packed {
1484 FieldStore::open_packed(store_dir)?
1485 } else {
1486 FieldStore::open(store_dir)?
1487 };
1488 let field_id = FieldId::from_hex(field_hex)?;
1489 let mut out = Vec::with_capacity(requests.len());
1490 for (_, req) in requests {
1491 let mut cold = req.clone();
1492 cold.use_cache = false;
1493 let (_, stats, _) = super::observe::observe(&mut store, &field_id, &cold, limits)?;
1494 out.push(stats);
1495 }
1496 Ok(out)
1497}