rfc9162_tiles/
layout.rs

1//! Tile coordinates, store paths and the widths a tree size gives each level,
2//! as C2SP tlog-tiles (<https://c2sp.org/tlog-tiles>) fixes them.
3//!
4//! A tile at level `l` holds up to 256 hashes; hash `i` of tile `n` is the
5//! RFC 9162 root over leaves `[(n * 256 + i) * 256^l, (n * 256 + i + 1) * 256^l)`.
6//! Level 0 holds leaf hashes. A full tile has 256 hashes; a partial tile has
7//! 1 to 255 and is never hashed into the level above.
8
9use crate::error::{Error, Result};
10
11/// Hashes per full tile, and entries per full bundle.
12pub const TILE_WIDTH: u64 = 256;
13/// `log2(TILE_WIDTH)`: the tree height one tile level covers.
14pub const TILE_HEIGHT: u32 = 8;
15/// Bytes per hash.
16pub const HASH_SIZE: usize = 32;
17/// The longest entry a bundle can length-prefix.
18pub const MAX_ENTRY_LEN: usize = u16::MAX as usize;
19/// Store path of the mutable tree state (size and root), written last.
20pub const TREE_STATE: &str = ".state/treeState";
21/// Store path of the writer lock.
22pub const TREE_STATE_LOCK: &str = ".state/treeState.lock";
23/// Store path of the checkpoint lock.
24pub const PUBLISH_LOCK: &str = ".state/publish.lock";
25/// Store path of the signed checkpoint.
26pub const CHECKPOINT: &str = "checkpoint";
27/// Store path of the manifest over the sealed bundles.
28pub const MANIFEST: &str = "manifest";
29
30/// One tile: its level, its index within the level and how many hashes it
31/// holds. `width` is 256 for a full tile and 1 to 255 for a partial one.
32#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
33pub struct Tile {
34    /// 0 for leaf hashes; each level up covers 256 times as many leaves.
35    pub level: u8,
36    /// Position within the level.
37    pub index: u64,
38    /// Hashes in the tile, 1 to 256.
39    pub width: u16,
40}
41
42impl Tile {
43    /// A tile; `width` outside 1 to 256 is refused.
44    pub fn new(level: u8, index: u64, width: u16) -> Result<Self> {
45        if width == 0 || u64::from(width) > TILE_WIDTH {
46            return Err(Error::OutOfRange(format!("tile width {width}")));
47        }
48        Ok(Self {
49            level,
50            index,
51            width,
52        })
53    }
54
55    /// Whether the tile holds 256 hashes.
56    #[must_use]
57    pub fn is_full(&self) -> bool {
58        u64::from(self.width) == TILE_WIDTH
59    }
60
61    /// `tile/<L>/<N>` for a full tile, `tile/<L>/<N>.p/<W>` for a partial.
62    #[must_use]
63    pub fn path(&self) -> String {
64        let mut path = format!("tile/{}/{}", self.level, path_elements(self.index));
65        if !self.is_full() {
66            path.push_str(&format!(".p/{}", self.width));
67        }
68        path
69    }
70
71    /// The tile a store path names, or nothing when the path is not a hash
72    /// tile path. `tile/entries/...` and `tile/index/...` are not hash tiles.
73    #[must_use]
74    pub fn parse(path: &str) -> Option<Self> {
75        let rest = path.strip_prefix("tile/")?;
76        let (level, rest) = rest.split_once('/')?;
77        if level.is_empty() || level.len() > 2 || !level.bytes().all(|b| b.is_ascii_digit()) {
78            return None;
79        }
80        if level.len() == 2 && level.starts_with('0') {
81            return None;
82        }
83        let level: u8 = level.parse().ok().filter(|l| *l < 64)?;
84        let (index, width) = parse_indexed(rest)?;
85        Self::new(level, index, width).ok()
86    }
87}
88
89/// `<N>` as zero-padded 3-digit elements, all but the last prefixed `x`:
90/// 1234067 is `x001/x234/067`.
91#[must_use]
92pub fn path_elements(index: u64) -> String {
93    let digits = format!("{index:03}");
94    let mut groups: Vec<String> = Vec::new();
95    let bytes = digits.as_bytes();
96    let head = bytes.len() % 3;
97    let mut start = 0;
98    if head != 0 {
99        groups.push(format!("{:0>3}", &digits[..head]));
100        start = head;
101    }
102    while start < bytes.len() {
103        groups.push(digits[start..start + 3].to_string());
104        start += 3;
105    }
106    let last = groups.len() - 1;
107    groups
108        .iter()
109        .enumerate()
110        .map(|(i, g)| {
111            if i == last {
112                g.clone()
113            } else {
114                format!("x{g}")
115            }
116        })
117        .collect::<Vec<_>>()
118        .join("/")
119}
120
121/// The index `path_elements` wrote, or nothing when the text is not that.
122#[must_use]
123pub fn parse_path_elements(text: &str) -> Option<u64> {
124    let elements: Vec<&str> = text.split('/').collect();
125    let last = elements.len() - 1;
126    let mut digits = String::new();
127    for (i, element) in elements.iter().enumerate() {
128        let body = if i == last {
129            *element
130        } else {
131            element.strip_prefix('x')?
132        };
133        if body.len() != 3 || !body.bytes().all(|b| b.is_ascii_digit()) {
134            return None;
135        }
136        digits.push_str(body);
137    }
138    let index: u64 = digits.parse().ok()?;
139    // The encoding is unique: anything but the canonical spelling is refused.
140    (path_elements(index) == text).then_some(index)
141}
142
143/// `<N>[.p/<W>]` into (index, width), width 256 when there is no `.p`.
144fn parse_indexed(rest: &str) -> Option<(u64, u16)> {
145    match rest.split_once(".p/") {
146        Some((index, width)) => {
147            if width.is_empty() || width.len() > 3 || !width.bytes().all(|b| b.is_ascii_digit()) {
148                return None;
149            }
150            if width.starts_with('0') {
151                return None;
152            }
153            let width: u16 = width.parse().ok()?;
154            if width == 0 || u64::from(width) >= TILE_WIDTH {
155                return None;
156            }
157            Some((parse_path_elements(index)?, width))
158        }
159        None => Some((parse_path_elements(rest)?, TILE_WIDTH as u16)),
160    }
161}
162
163/// `tile/entries/<N>` for a full bundle, `tile/entries/<N>.p/<W>` for the
164/// partial one.
165#[must_use]
166pub fn entries_path(index: u64, width: u16) -> String {
167    let mut path = format!("tile/entries/{}", path_elements(index));
168    if u64::from(width) != TILE_WIDTH {
169        path.push_str(&format!(".p/{width}"));
170    }
171    path
172}
173
174/// The (bundle index, width) an entries path names.
175#[must_use]
176pub fn parse_entries_path(path: &str) -> Option<(u64, u16)> {
177    parse_indexed(path.strip_prefix("tile/entries/")?)
178}
179
180/// `tile/index/<N>`, the key sidecar of sealed bundle `N`.
181#[must_use]
182pub fn index_path(index: u64) -> String {
183    format!("tile/index/{}", path_elements(index))
184}
185
186/// The bundle index a sidecar path names.
187#[must_use]
188pub fn parse_index_path(path: &str) -> Option<u64> {
189    parse_path_elements(path.strip_prefix("tile/index/")?)
190}
191
192/// The tiles a tree of one size is stored as.
193#[derive(Debug, Clone, Copy, PartialEq, Eq)]
194pub struct Layout {
195    /// Leaves in the tree.
196    pub size: u64,
197}
198
199impl Layout {
200    /// The layout of a tree with `size` leaves.
201    #[must_use]
202    pub fn new(size: u64) -> Self {
203        Self { size }
204    }
205
206    /// Hashes the tree has at `level`: `floor(size / 256^level)`.
207    #[must_use]
208    pub fn hashes_at(&self, level: u8) -> u64 {
209        let shift = u32::from(level) * TILE_HEIGHT;
210        if shift >= u64::BITS {
211            0
212        } else {
213            self.size >> shift
214        }
215    }
216
217    /// Levels that hold at least one hash; 0 for the empty tree.
218    #[must_use]
219    pub fn levels(&self) -> u8 {
220        let mut level = 0u8;
221        while self.hashes_at(level) > 0 {
222            level += 1;
223        }
224        level
225    }
226
227    /// Full tiles at `level`.
228    #[must_use]
229    pub fn full_tiles_at(&self, level: u8) -> u64 {
230        self.hashes_at(level) / TILE_WIDTH
231    }
232
233    /// Width of the partial tile at `level`, `floor(size / 256^level) mod 256`;
234    /// 0 when the level ends on a full tile.
235    #[must_use]
236    pub fn width_at(&self, level: u8) -> u16 {
237        (self.hashes_at(level) % TILE_WIDTH) as u16
238    }
239
240    /// The partial tile at `level`, when there is one.
241    #[must_use]
242    pub fn partial_at(&self, level: u8) -> Option<Tile> {
243        let width = self.width_at(level);
244        (width > 0).then(|| Tile {
245            level,
246            index: self.full_tiles_at(level),
247            width,
248        })
249    }
250
251    /// Every partial tile of the tree, level 0 first. Their hashes are exactly
252    /// the perfect-subtree roots the tree root is folded from.
253    #[must_use]
254    pub fn partial_tiles(&self) -> Vec<Tile> {
255        (0..self.levels())
256            .filter_map(|level| self.partial_at(level))
257            .collect()
258    }
259
260    /// Every tile of the tree, full and partial, level 0 first.
261    #[must_use]
262    pub fn tiles(&self) -> Vec<Tile> {
263        let mut out = Vec::new();
264        for level in 0..self.levels() {
265            for index in 0..self.full_tiles_at(level) {
266                out.push(Tile {
267                    level,
268                    index,
269                    width: TILE_WIDTH as u16,
270                });
271            }
272            out.extend(self.partial_at(level));
273        }
274        out
275    }
276
277    /// The tile at `level` and `index` as this tree stores it: full below the
278    /// partial, the partial at its width, nothing beyond.
279    #[must_use]
280    pub fn tile(&self, level: u8, index: u64) -> Option<Tile> {
281        let full = self.full_tiles_at(level);
282        if index < full {
283            Some(Tile {
284                level,
285                index,
286                width: TILE_WIDTH as u16,
287            })
288        } else if index == full {
289            self.partial_at(level)
290        } else {
291            None
292        }
293    }
294
295    /// Sealed (full) entry bundles.
296    #[must_use]
297    pub fn full_bundles(&self) -> u64 {
298        self.full_tiles_at(0)
299    }
300
301    /// Entries in the unsealed bundle, 0 to 255.
302    #[must_use]
303    pub fn partial_bundle_width(&self) -> u16 {
304        self.width_at(0)
305    }
306
307    /// The bundle holding entry `index`, and the entry's offset in it.
308    #[must_use]
309    pub fn bundle_of(entry: u64) -> (u64, u16) {
310        (entry / TILE_WIDTH, (entry % TILE_WIDTH) as u16)
311    }
312}
313
314#[cfg(test)]
315mod tests {
316    use super::*;
317
318    #[test]
319    fn the_spec_path_example() {
320        assert_eq!(path_elements(1_234_067), "x001/x234/067");
321        assert_eq!(parse_path_elements("x001/x234/067"), Some(1_234_067));
322        assert_eq!(path_elements(0), "000");
323        assert_eq!(path_elements(7), "007");
324        assert_eq!(path_elements(1000), "x001/000");
325        assert_eq!(parse_path_elements("x000/007"), None);
326        assert_eq!(parse_path_elements("7"), None);
327    }
328
329    #[test]
330    fn tile_paths_round_trip() {
331        let full = Tile::new(1, 300, 256).unwrap();
332        assert_eq!(full.path(), "tile/1/300");
333        let partial = Tile::new(0, 273, 112).unwrap();
334        assert_eq!(partial.path(), "tile/0/273.p/112");
335        assert_eq!(
336            Tile::new(0, 1_234_067, 5).unwrap().path(),
337            "tile/0/x001/x234/067.p/5"
338        );
339        for tile in [full, partial] {
340            assert_eq!(Tile::parse(&tile.path()), Some(tile));
341        }
342        assert_eq!(Tile::parse("tile/entries/000"), None);
343        assert_eq!(Tile::parse("tile/0/000.p/256"), None);
344        assert_eq!(Tile::parse("tile/0/000.p/0"), None);
345        assert_eq!(Tile::parse("tile/00/000"), None);
346        assert_eq!(entries_path(5, 256), "tile/entries/005");
347        assert_eq!(entries_path(5, 12), "tile/entries/005.p/12");
348        assert_eq!(parse_entries_path("tile/entries/005.p/12"), Some((5, 12)));
349        assert_eq!(index_path(1000), "tile/index/x001/000");
350        assert_eq!(parse_index_path("tile/index/x001/000"), Some(1000));
351    }
352
353    #[test]
354    fn widths_follow_the_size() {
355        let layout = Layout::new(256);
356        assert_eq!(layout.levels(), 2);
357        assert_eq!(layout.full_tiles_at(0), 1);
358        assert_eq!(layout.width_at(0), 0);
359        assert_eq!(layout.width_at(1), 1);
360        assert_eq!(Layout::new(0).levels(), 0);
361        assert!(Layout::new(0).tiles().is_empty());
362        assert_eq!(Layout::new(1).tiles(), vec![Tile::new(0, 0, 1).unwrap()]);
363        assert_eq!(Layout::bundle_of(70_000), (273, 112));
364    }
365}
rfc9162_tiles/layout.rs

rfc9162_tiles/
layout.rs
