rfc9162_tiles/
log.rs

1//! The log on a store: one [`Writer`] appends entries, seals bundles, writes
2//! tiles and then the tree state; any number of [`Reader`]s read entries and
3//! check them against the tree.
4//!
5//! Write order follows Tessera's POSIX storage: entry bundles, hash tiles,
6//! index sidecars, the manifest, then `.state/treeState` last, every file
7//! whole or not at all. On open the writer moves anything the tree state does
8//! not cover to `.state/torn-<utc>` and never adopts it silently, and rebuilds
9//! a sidecar or manifest row a sealed bundle lacks.
10
11use std::ops::Range;
12use std::time::{SystemTime, UNIX_EPOCH};
13
14use sha2::{Digest, Sha256};
15
16use crate::bundle::{decode_bundle, encode_bundle};
17use crate::checkpoint::{self, Checkpoint, Note, Signer, Verifier};
18use crate::error::{Error, Result};
19use crate::index::{identity, KeyFn, Manifest, Sidecar};
20use crate::layout::{
21    entries_path, index_path, parse_entries_path, parse_index_path, Layout, Tile, CHECKPOINT,
22    MAX_ENTRY_LEN, PUBLISH_LOCK, TILE_WIDTH, TREE_STATE, TREE_STATE_LOCK,
23};
24use crate::store::TileStore;
25use crate::tree::{encode_tile, Frontier, Hash, TileHashReader};
26
27/// What `.state/treeState` holds: the size and the root the tiles are
28/// complete to. Two lines, the decimal size and the lower-case hex root.
29#[derive(Debug, Clone, Copy, PartialEq, Eq)]
30pub struct TreeState {
31    /// Entries the tiles are complete to.
32    pub size: u64,
33    /// The root at that size.
34    pub root: Hash,
35}
36
37impl TreeState {
38    /// The state the store holds, or nothing for a store without one.
39    pub fn read(store: &impl TileStore) -> Result<Option<Self>> {
40        let Some(bytes) = store.get(TREE_STATE)? else {
41            return Ok(None);
42        };
43        let text = String::from_utf8(bytes).map_err(|_| Error::Corrupt {
44            path: TREE_STATE.to_string(),
45            reason: "not UTF-8".to_string(),
46        })?;
47        Self::parse(&text).map(Some)
48    }
49
50    /// The state in its two-line text.
51    pub fn parse(text: &str) -> Result<Self> {
52        let mut lines = text.lines();
53        let size = lines
54            .next()
55            .and_then(|l| l.parse::<u64>().ok())
56            .ok_or_else(|| Error::Corrupt {
57                path: TREE_STATE.to_string(),
58                reason: "first line is not a size".to_string(),
59            })?;
60        let root = lines
61            .next()
62            .and_then(rfc9162::from_hex)
63            .ok_or_else(|| Error::Corrupt {
64                path: TREE_STATE.to_string(),
65                reason: "second line is not a hex root".to_string(),
66            })?;
67        Ok(Self { size, root })
68    }
69
70    /// The two-line text.
71    #[must_use]
72    pub fn to_text(&self) -> String {
73        format!("{}\n{}\n", self.size, rfc9162::hex(&self.root))
74    }
75
76    /// Writes the state, whole or not at all.
77    pub fn write(&self, store: &impl TileStore) -> Result<()> {
78        store.put(TREE_STATE, self.to_text().as_bytes())?;
79        Ok(())
80    }
81}
82
83/// The one writer of a log. Holds `.state/treeState.lock` from open to drop.
84pub struct Writer<S: TileStore> {
85    store: S,
86    keys: KeyFn,
87    frontier: Frontier,
88    partial: Vec<Vec<u8>>,
89    manifest: Manifest,
90    quarantined: Vec<String>,
91    torn_dir: Option<String>,
92}
93
94impl<S: TileStore> Writer<S> {
95    /// Opens the log on `store`, takes the writer lock, quarantines a torn
96    /// tail, loads the frontier and completes the sidecars and manifest of
97    /// every sealed bundle. `keys` derives the lookup keys of an entry from
98    /// its bytes ([`crate::index::no_keys`] for the identity hash alone); a
99    /// reader has to use the same function. `Error::Locked` when another
100    /// writer holds the lock; a lock left by a crashed writer has to be
101    /// removed by hand.
102    pub fn open(store: S, keys: KeyFn) -> Result<Self> {
103        let body = format!("{}\n", std::process::id());
104        if !store.create_new(TREE_STATE_LOCK, body.as_bytes())? {
105            return Err(Error::Locked(TREE_STATE_LOCK.to_string()));
106        }
107        match Self::load(&store, &keys) {
108            Ok(loaded) => Ok(Self {
109                store,
110                keys,
111                frontier: loaded.frontier,
112                partial: loaded.partial,
113                manifest: loaded.manifest,
114                quarantined: loaded.quarantined,
115                torn_dir: loaded.torn_dir,
116            }),
117            Err(e) => {
118                let _ = store.delete(TREE_STATE_LOCK);
119                Err(e)
120            }
121        }
122    }
123
124    fn load(store: &S, keys: &KeyFn) -> Result<Loaded> {
125        let state = TreeState::read(store)?.unwrap_or(TreeState {
126            size: 0,
127            root: rfc9162::root(&[]),
128        });
129        let (quarantined, torn_dir) = quarantine(store, state.size)?;
130        let frontier = Frontier::load(store, state.size)?;
131        if frontier.root() != state.root {
132            return Err(Error::Corrupt {
133                path: TREE_STATE.to_string(),
134                reason: format!(
135                    "root {} at size {}, the partial tiles fold to {}",
136                    rfc9162::hex(&state.root),
137                    state.size,
138                    rfc9162::hex(&frontier.root())
139                ),
140            });
141        }
142        let partial = read_partial_bundle(store, &frontier)?;
143        let manifest = repair_index(store, keys, &frontier)?;
144        Ok(Loaded {
145            frontier,
146            partial,
147            manifest,
148            quarantined,
149            torn_dir,
150        })
151    }
152
153    /// The store the writer writes.
154    pub fn store(&self) -> &S {
155        &self.store
156    }
157
158    /// Entries in the log.
159    #[must_use]
160    pub fn size(&self) -> u64 {
161        self.frontier.size()
162    }
163
164    /// The root over every entry.
165    #[must_use]
166    pub fn root(&self) -> Hash {
167        self.frontier.root()
168    }
169
170    /// The tree state the tiles are complete to.
171    #[must_use]
172    pub fn tree_state(&self) -> TreeState {
173        TreeState {
174            size: self.size(),
175            root: self.root(),
176        }
177    }
178
179    /// Store paths open moved aside because the tree state did not cover
180    /// them, and the `.state/torn-<utc>` directory they went to.
181    #[must_use]
182    pub fn quarantined(&self) -> (&[String], Option<&str>) {
183        (&self.quarantined, self.torn_dir.as_deref())
184    }
185
186    /// Appends one entry and returns its index.
187    pub fn append(&mut self, entry: &[u8]) -> Result<u64> {
188        Ok(self.append_batch([entry.to_vec()])?.start)
189    }
190
191    /// Appends entries in order and returns their index range. Nothing is
192    /// written when any entry is over 65535 bytes. Bundles, tiles and the
193    /// tree state are each written once for the whole batch.
194    pub fn append_batch<I>(&mut self, entries: I) -> Result<Range<u64>>
195    where
196        I: IntoIterator<Item = Vec<u8>>,
197    {
198        let entries: Vec<Vec<u8>> = entries.into_iter().collect();
199        if let Some(long) = entries.iter().find(|e| e.len() > MAX_ENTRY_LEN) {
200            return Err(Error::EntryTooLong(long.len()));
201        }
202        let start = self.frontier.size();
203        if entries.is_empty() {
204            return Ok(start..start);
205        }
206        let mut completed: Vec<(Tile, Vec<Hash>)> = Vec::new();
207        let mut sealed: Vec<(u64, Vec<Vec<u8>>)> = Vec::new();
208        for entry in entries {
209            self.frontier
210                .push(rfc9162::leaf_hash(&entry), &mut completed);
211            self.partial.push(entry);
212            if self.partial.len() as u64 == TILE_WIDTH {
213                let index = self.frontier.size() / TILE_WIDTH - 1;
214                sealed.push((index, std::mem::take(&mut self.partial)));
215            }
216        }
217        let end = self.frontier.size();
218        let layout = Layout::new(end);
219
220        for (index, bundle) in &sealed {
221            self.store.put(
222                &entries_path(*index, TILE_WIDTH as u16),
223                &encode_bundle(bundle)?,
224            )?;
225        }
226        if !self.partial.is_empty() {
227            self.store.put(
228                &entries_path(layout.full_bundles(), layout.partial_bundle_width()),
229                &encode_bundle(&self.partial)?,
230            )?;
231        }
232        for (tile, hashes) in &completed {
233            self.store.put(&tile.path(), &encode_tile(hashes))?;
234        }
235        for (tile, hashes) in self.frontier.partial_tiles() {
236            self.store.put(&tile.path(), &encode_tile(hashes))?;
237        }
238        self.seal(&sealed)?;
239        self.tree_state().write(&self.store)?;
240
241        // Older partials of a tile that is full are covered by the full tile and
242        // the tree state, so nothing needs them; the narrower partials of the
243        // tail's tiles are covered by the widest one, which the tree state
244        // names, so only that one stays.
245        for (index, _) in &sealed {
246            self.remove_partials(&entries_path(*index, TILE_WIDTH as u16))?;
247        }
248        for (tile, _) in &completed {
249            self.remove_partials(&tile.path())?;
250        }
251        if !self.partial.is_empty() {
252            let full = entries_path(layout.full_bundles(), TILE_WIDTH as u16);
253            let keep = entries_path(layout.full_bundles(), layout.partial_bundle_width());
254            self.remove_partials_but(&full, &keep)?;
255        }
256        for (tile, _) in self.frontier.partial_tiles() {
257            let full = Tile {
258                level: tile.level,
259                index: tile.index,
260                width: TILE_WIDTH as u16,
261            };
262            self.remove_partials_but(&full.path(), &tile.path())?;
263        }
264        Ok(start..end)
265    }
266
267    /// Writes the sidecar of each sealed bundle, then the manifest with their
268    /// rows.
269    fn seal(&mut self, sealed: &[(u64, Vec<Vec<u8>>)]) -> Result<()> {
270        if sealed.is_empty() {
271            return Ok(());
272        }
273        for (index, bundle) in sealed {
274            let sidecar = Sidecar::build(bundle, &self.keys);
275            let bytes = sidecar.to_bytes();
276            self.store.put(&index_path(*index), &bytes)?;
277            self.manifest
278                .bundles
279                .push(Manifest::row(*index, &sidecar, &bytes));
280        }
281        self.manifest.write(&self.store)
282    }
283
284    /// The manifest over the sealed bundles.
285    #[must_use]
286    pub fn manifest(&self) -> &Manifest {
287        &self.manifest
288    }
289
290    /// Signs the tree state as a C2SP checkpoint under `origin` and writes
291    /// it at `checkpoint`, holding `.state/publish.lock` meanwhile. A
292    /// checkpoint already published for a larger size is never replaced, so
293    /// the signer never signs a checkpoint inconsistent with one it signed.
294    /// Returns the note.
295    pub fn checkpoint(&self, signer: &Signer, origin: &str) -> Result<Note> {
296        let body = format!("{}\n", std::process::id());
297        if !self.store.create_new(PUBLISH_LOCK, body.as_bytes())? {
298            return Err(Error::Locked(PUBLISH_LOCK.to_string()));
299        }
300        let result = self.publish(signer, origin);
301        let _ = self.store.delete(PUBLISH_LOCK);
302        result
303    }
304
305    fn publish(&self, signer: &Signer, origin: &str) -> Result<Note> {
306        if let Some(bytes) = self.store.get(CHECKPOINT)? {
307            let text = String::from_utf8(bytes).map_err(|_| Error::Corrupt {
308                path: CHECKPOINT.to_string(),
309                reason: "not UTF-8".to_string(),
310            })?;
311            let published = Checkpoint::parse(&Note::parse(&text)?.text)?;
312            if published.origin == origin && published.size > self.size() {
313                return Err(Error::OutOfRange(format!(
314                    "a checkpoint for size {} is published, the log is at {}",
315                    published.size,
316                    self.size()
317                )));
318            }
319        }
320        let note = signer.sign(&Checkpoint::new(origin, self.size(), self.root()));
321        self.store.put(CHECKPOINT, note.to_text().as_bytes())?;
322        Ok(note)
323    }
324
325    fn remove_partials(&self, full_path: &str) -> Result<()> {
326        for path in self.store.list(&format!("{full_path}.p"))? {
327            self.store.delete(&path)?;
328        }
329        Ok(())
330    }
331
332    fn remove_partials_but(&self, full_path: &str, keep: &str) -> Result<()> {
333        for path in self.store.list(&format!("{full_path}.p"))? {
334            if path != keep {
335                self.store.delete(&path)?;
336            }
337        }
338        Ok(())
339    }
340}
341
342impl<S: TileStore> Drop for Writer<S> {
343    fn drop(&mut self) {
344        let _ = self.store.delete(TREE_STATE_LOCK);
345    }
346}
347
348/// What open loads before the writer exists.
349struct Loaded {
350    frontier: Frontier,
351    partial: Vec<Vec<u8>>,
352    manifest: Manifest,
353    quarantined: Vec<String>,
354    torn_dir: Option<String>,
355}
356
357/// The manifest with a row and a sidecar for every sealed bundle: rows past
358/// the sealed bundles are dropped, missing or differing sidecars rebuilt from
359/// the bundle, and the manifest rewritten when anything changed.
360fn repair_index(store: &impl TileStore, keys: &KeyFn, frontier: &Frontier) -> Result<Manifest> {
361    let full = Layout::new(frontier.size()).full_bundles();
362    let mut manifest = Manifest::read(store)?;
363    let mut changed = false;
364    if manifest.bundles.len() as u64 > full {
365        manifest.bundles.truncate(full as usize);
366        changed = true;
367    }
368    for index in manifest.bundles.len() as u64..full {
369        let path = entries_path(index, TILE_WIDTH as u16);
370        let bytes = store.get(&path)?.ok_or_else(|| Error::Corrupt {
371            path: path.clone(),
372            reason: "missing".to_string(),
373        })?;
374        let entries = decode_bundle(&path, &bytes)?;
375        let sidecar = Sidecar::build(&entries, keys);
376        let bytes = sidecar.to_bytes();
377        if store.get(&index_path(index))?.as_deref() != Some(bytes.as_slice()) {
378            store.put(&index_path(index), &bytes)?;
379        }
380        manifest
381            .bundles
382            .push(Manifest::row(index, &sidecar, &bytes));
383        changed = true;
384    }
385    if changed {
386        manifest.write(store)?;
387    }
388    Ok(manifest)
389}
390
391/// The entries of bundle `index` at `width`. A partial bundle a writer has
392/// since widened is read from the widest partial or the full bundle, whose
393/// first `width` entries it was, since a writer keeps only the widest
394/// partial of a tail bundle.
395fn read_bundle(store: &impl TileStore, index: u64, width: u16) -> Result<Vec<Vec<u8>>> {
396    let path = entries_path(index, width);
397    if let Some(bytes) = store.get(&path)? {
398        return decode_bundle(&path, &bytes);
399    }
400    if u64::from(width) < TILE_WIDTH {
401        let full = entries_path(index, TILE_WIDTH as u16);
402        let mut covering = vec![full.clone()];
403        covering.extend(store.list(&format!("{full}.p"))?);
404        for candidate in covering {
405            if let Some(bytes) = store.get(&candidate)? {
406                let mut entries = decode_bundle(&candidate, &bytes)?;
407                if entries.len() >= usize::from(width) {
408                    entries.truncate(usize::from(width));
409                    return Ok(entries);
410                }
411            }
412        }
413        return Err(Error::Corrupt {
414            path,
415            reason: "missing, and no wider bundle covers it".to_string(),
416        });
417    }
418    Err(Error::Corrupt {
419        path,
420        reason: "missing".to_string(),
421    })
422}
423
424fn read_partial_bundle(store: &impl TileStore, frontier: &Frontier) -> Result<Vec<Vec<u8>>> {
425    let layout = Layout::new(frontier.size());
426    let width = layout.partial_bundle_width();
427    if width == 0 {
428        return Ok(Vec::new());
429    }
430    let path = entries_path(layout.full_bundles(), width);
431    let entries = read_bundle(store, layout.full_bundles(), width)?;
432    if entries.len() != usize::from(width) {
433        return Err(Error::Corrupt {
434            path,
435            reason: format!("{} entries, width {width}", entries.len()),
436        });
437    }
438    let (_, level0) = frontier
439        .partial_tiles()
440        .into_iter()
441        .find(|(tile, _)| tile.level == 0)
442        .expect("a partial bundle has a partial level-0 tile");
443    for (i, (entry, hash)) in entries.iter().zip(level0).enumerate() {
444        if rfc9162::leaf_hash(entry) != *hash {
445            return Err(Error::Corrupt {
446                path,
447                reason: format!("entry {i} does not hash to its leaf"),
448            });
449        }
450    }
451    Ok(entries)
452}
453
454/// Whether a stored path is one the tree of `size` has.
455fn covered(path: &str, layout: &Layout) -> bool {
456    if let Some((index, width)) = parse_entries_path(path) {
457        return covered_indexed(
458            index,
459            width,
460            layout.full_bundles(),
461            layout.partial_bundle_width(),
462        );
463    }
464    if let Some(index) = parse_index_path(path) {
465        return index < layout.full_bundles();
466    }
467    if let Some(tile) = Tile::parse(path) {
468        return covered_indexed(
469            tile.index,
470            tile.width,
471            layout.full_tiles_at(tile.level),
472            layout.width_at(tile.level),
473        );
474    }
475    false
476}
477
478fn covered_indexed(index: u64, width: u16, full: u64, partial_width: u16) -> bool {
479    if u64::from(width) == TILE_WIDTH {
480        index < full
481    } else {
482        index == full && width <= partial_width
483    }
484}
485
486/// Moves every path under `tile/` that the tree of `size` does not cover to
487/// `.state/torn-<utc>/`, returning the paths moved and that directory.
488fn quarantine(store: &impl TileStore, size: u64) -> Result<(Vec<String>, Option<String>)> {
489    let layout = Layout::new(size);
490    let torn: Vec<String> = store
491        .list("tile")?
492        .into_iter()
493        .filter(|path| !covered(path, &layout))
494        .collect();
495    if torn.is_empty() {
496        return Ok((Vec::new(), None));
497    }
498    let dir = format!(".state/torn-{}", utc_stamp());
499    for path in &torn {
500        store.rename(path, &format!("{dir}/{path}"))?;
501    }
502    Ok((torn, Some(dir)))
503}
504
505/// Now as `YYYYMMDDTHHMMSSZ`.
506fn utc_stamp() -> String {
507    let secs = SystemTime::now()
508        .duration_since(UNIX_EPOCH)
509        .map(|d| d.as_secs())
510        .unwrap_or(0);
511    let (date, time) = (secs / 86_400, secs % 86_400);
512    // Civil date from days since 1970-01-01 (Howard Hinnant's algorithm).
513    let z = date as i64 + 719_468;
514    let era = z.div_euclid(146_097);
515    let doe = z.rem_euclid(146_097);
516    let yoe = (doe - doe / 1460 + doe / 36_524 - doe / 146_096) / 365;
517    let y = yoe + era * 400;
518    let doy = doe - (365 * yoe + yoe / 4 - yoe / 100);
519    let mp = (5 * doy + 2) / 153;
520    let d = doy - (153 * mp + 2) / 5 + 1;
521    let m = if mp < 10 { mp + 3 } else { mp - 9 };
522    let y = if m <= 2 { y + 1 } else { y };
523    format!(
524        "{y:04}{m:02}{d:02}T{:02}{:02}{:02}Z",
525        time / 3600,
526        (time % 3600) / 60,
527        time % 60
528    )
529}
530
531/// Reads a log at one tree state. Every entry it returns hashes to the leaf
532/// the checked tiles hold for its index.
533pub struct Reader<S: TileStore> {
534    hashes: TileHashReader<S>,
535    keys: KeyFn,
536    manifest: Manifest,
537}
538
539impl<S: TileStore> Reader<S> {
540    /// A reader at the tree state the store holds, with the log's key
541    /// function; the empty tree for a store without a state.
542    pub fn open(store: S, keys: KeyFn) -> Result<Self> {
543        let state = TreeState::read(&store)?.unwrap_or(TreeState {
544            size: 0,
545            root: rfc9162::root(&[]),
546        });
547        Self::at(store, state.size, state.root, keys)
548    }
549
550    /// A reader that trusts `root` to be the root at `size`, which is how a
551    /// verified checkpoint opens a log.
552    pub fn at(store: S, size: u64, root: Hash, keys: KeyFn) -> Result<Self> {
553        let mut manifest = Manifest::read(&store)?;
554        let full = Layout::new(size).full_bundles();
555        manifest.bundles.truncate(full as usize);
556        Ok(Self {
557            hashes: TileHashReader::new(store, size, root),
558            keys,
559            manifest,
560        })
561    }
562
563    /// A reader at the store's published checkpoint, once a key in `trusted`
564    /// has signed it; the checkpoint's origin has to be `origin`. This is how
565    /// a reader that does not trust the writer's tree state opens a log.
566    pub fn open_checkpoint(
567        store: S,
568        origin: &str,
569        trusted: &[Verifier],
570        keys: KeyFn,
571    ) -> Result<Self> {
572        let bytes = store.get(CHECKPOINT)?.ok_or_else(|| Error::Corrupt {
573            path: CHECKPOINT.to_string(),
574            reason: "missing".to_string(),
575        })?;
576        let text = String::from_utf8(bytes).map_err(|_| Error::Corrupt {
577            path: CHECKPOINT.to_string(),
578            reason: "not UTF-8".to_string(),
579        })?;
580        let note = Note::parse(&text)?;
581        checkpoint::verify(&note, trusted)?;
582        let published = Checkpoint::parse(&note.text)?;
583        if published.origin != origin {
584            return Err(Error::Signature(format!(
585                "checkpoint is for {}, not {origin}",
586                published.origin
587            )));
588        }
589        Self::at(store, published.size, published.root, keys)
590    }
591
592    /// The manifest rows for the sealed bundles the root covers.
593    #[must_use]
594    pub fn manifest(&self) -> &Manifest {
595        &self.manifest
596    }
597
598    /// Indices of every entry carrying `key`, ascending: through the
599    /// manifest ranges, the filters and the sidecars for sealed bundles, then
600    /// a scan of the unsealed one. A key is an identity hash or a value the
601    /// key function derives; each hit is checked on the entry itself.
602    pub fn find(&self, key: &[u8]) -> Result<Vec<u64>> {
603        let mut found = Vec::new();
604        for row in self.manifest.candidates(key) {
605            let path = index_path(row.index);
606            let bytes = self.store().get(&path)?.ok_or_else(|| Error::Corrupt {
607                path: path.clone(),
608                reason: "missing".to_string(),
609            })?;
610            if rfc9162::hex(&Sha256::digest(&bytes)) != row.sidecar {
611                return Err(Error::Corrupt {
612                    path,
613                    reason: "does not hash to its manifest row".to_string(),
614                });
615            }
616            let sidecar = Sidecar::from_bytes(&path, &bytes)?;
617            let offsets = sidecar.lookup(key);
618            if offsets.is_empty() {
619                continue;
620            }
621            let entries = self.bundle(row.index)?;
622            for offset in offsets {
623                let entry = &entries[usize::from(offset)];
624                if self.carries(entry, key) {
625                    found.push(row.index * TILE_WIDTH + u64::from(offset));
626                }
627            }
628        }
629        let layout = Layout::new(self.size());
630        if layout.partial_bundle_width() > 0 {
631            let first = layout.full_bundles() * TILE_WIDTH;
632            for (offset, entry) in self.bundle(layout.full_bundles())?.iter().enumerate() {
633                if self.carries(entry, key) {
634                    found.push(first + offset as u64);
635                }
636            }
637        }
638        Ok(found)
639    }
640
641    fn carries(&self, entry: &[u8], key: &[u8]) -> bool {
642        identity(entry) == key || (self.keys)(entry).iter().any(|k| k == key)
643    }
644
645    /// The store behind the reader.
646    pub fn store(&self) -> &S {
647        self.hashes.store()
648    }
649
650    /// Entries the reader's root covers.
651    #[must_use]
652    pub fn size(&self) -> u64 {
653        self.hashes.size()
654    }
655
656    /// The trusted root.
657    #[must_use]
658    pub fn root(&self) -> Hash {
659        self.hashes.trusted_root()
660    }
661
662    /// The checked tile reader.
663    pub fn hashes(&self) -> &TileHashReader<S> {
664        &self.hashes
665    }
666
667    /// Entry `index`, checked against its leaf hash; nothing past the size.
668    pub fn get(&self, index: u64) -> Result<Option<Vec<u8>>> {
669        if index >= self.size() {
670            return Ok(None);
671        }
672        let (bundle, offset) = Layout::bundle_of(index);
673        let entries = self.bundle(bundle)?;
674        Ok(Some(entries[usize::from(offset)].clone()))
675    }
676
677    /// The inclusion proof for entry `index`, from checked tiles; the bytes
678    /// `rfc9162::inclusion_proof` gives over the flat leaf slice.
679    pub fn inclusion(&self, index: u64) -> Result<Option<Vec<Hash>>> {
680        self.hashes.inclusion_proof(index)
681    }
682
683    /// The consistency proof from a tree of `old` entries to this one, from
684    /// checked tiles; the bytes `rfc9162::consistency_proof` gives.
685    pub fn consistency(&self, old: u64) -> Result<Option<Vec<Hash>>> {
686        self.hashes.consistency_proof(old)
687    }
688
689    /// Every entry of bundle `index`, each checked against its leaf hash.
690    pub fn bundle(&self, index: u64) -> Result<Vec<Vec<u8>>> {
691        let layout = Layout::new(self.size());
692        let width = if index < layout.full_bundles() {
693            TILE_WIDTH as u16
694        } else if index == layout.full_bundles() && layout.partial_bundle_width() > 0 {
695            layout.partial_bundle_width()
696        } else {
697            return Err(Error::OutOfRange(format!(
698                "bundle {index} at size {}",
699                self.size()
700            )));
701        };
702        let path = entries_path(index, width);
703        let entries = read_bundle(self.store(), index, width)?;
704        if entries.len() != usize::from(width) {
705            return Err(Error::Corrupt {
706                path,
707                reason: format!("{} entries, width {width}", entries.len()),
708            });
709        }
710        let tile = self.hashes.tile(0, index)?;
711        for (i, (entry, hash)) in entries.iter().zip(tile.iter()).enumerate() {
712            if rfc9162::leaf_hash(entry) != *hash {
713                return Err(Error::Corrupt {
714                    path,
715                    reason: format!("entry {i} does not hash to its leaf"),
716                });
717            }
718        }
719        Ok(entries)
720    }
721}
rfc9162_tiles/log.rs

rfc9162_tiles/
log.rs
