Skip to main content

folderbase_core/
folderbase_version.rs

1//! Canonical, provider-neutral full state for one Folderbase boundary.
2//!
3//! A Folderbase Version is a bounded data artifact. This module deliberately
4//! does not capture filesystem state, resolve Cloud authority, or persist a
5//! Local Head.
6
7use std::{
8    collections::{BTreeMap, BTreeSet},
9    fmt::{self, Write as _},
10    io::{Read, Write},
11    marker::PhantomData,
12};
13
14use chrono::{DateTime, SecondsFormat, Utc};
15use serde::{
16    Deserialize, Serialize,
17    de::{IgnoredAny, SeqAccess, Visitor},
18};
19use sha2::{Digest, Sha256};
20use unicode_casefold::UnicodeCaseFold;
21use unicode_normalization::UnicodeNormalization;
22use uuid::Uuid;
23
24pub const VERSION_FORMAT_V1: &str = "folderbase-version-v1";
25pub const VERSION_PROTOCOL_V04: &str = "0.4";
26pub const VERSION_PROTOCOL_V05: &str = "0.5";
27pub const PATH_POLICY_FORMAT_V1: &str = "folderbase-portable-path-v1";
28pub const MAX_ENCODED_VERSION_BYTES: u64 = 64 * 1024 * 1024;
29pub const MAX_VERSION_ENTRIES: usize = 16_384;
30pub const MAX_OBJECT_BYTES: u64 = 1024 * 1024 * 1024 * 1024;
31pub const MAX_ROOT_MANIFEST_BYTES: u64 = 16 * 1024 * 1024;
32pub const MAX_PATH_BYTES: usize = 4_096;
33pub const MAX_PATH_COMPONENT_BYTES: usize = 255;
34pub const MAX_PATH_DEPTH: usize = 128;
35
36#[derive(Debug)]
37pub struct FolderbaseVersion {
38    format: String,
39    protocol_version: String,
40    folderbase_id: String,
41    version_id: String,
42    parents: Vec<String>,
43    created_at: String,
44    path_policy: PathPolicy,
45    root_manifest: RootManifest,
46    bindings: Vec<PathBinding>,
47    tombstones: Vec<Tombstone>,
48    exclusions: Vec<Exclusion>,
49}
50
51#[derive(Deserialize)]
52#[serde(deny_unknown_fields)]
53struct FolderbaseVersionWire {
54    format: String,
55    protocol_version: String,
56    folderbase_id: String,
57    version_id: String,
58    parents: Vec<String>,
59    created_at: String,
60    path_policy: PathPolicy,
61    root_manifest: RootManifest,
62    #[serde(deserialize_with = "deserialize_bounded_bindings")]
63    bindings: Vec<PathBinding>,
64    #[serde(deserialize_with = "deserialize_bounded_tombstones")]
65    tombstones: Vec<Tombstone>,
66    #[serde(deserialize_with = "deserialize_bounded_exclusions")]
67    exclusions: Vec<Exclusion>,
68}
69
70/// Crate-private construction boundary for future verified producers.
71///
72/// Later capture/seal code may prepare these parts only after it has verified
73/// their referenced bytes. Construction still performs the complete protocol
74/// validation before returning a `FolderbaseVersion`.
75pub(crate) struct FolderbaseVersionParts {
76    format: String,
77    protocol_version: String,
78    folderbase_id: String,
79    version_id: String,
80    parents: Vec<String>,
81    created_at: String,
82    path_policy: PathPolicy,
83    root_manifest: RootManifest,
84    bindings: Vec<PathBinding>,
85    tombstones: Vec<Tombstone>,
86    exclusions: Vec<Exclusion>,
87}
88
89pub(crate) struct FolderbaseVersionEntries {
90    bindings: Vec<PathBinding>,
91    tombstones: Vec<Tombstone>,
92    exclusions: Vec<Exclusion>,
93}
94
95#[derive(Debug, Deserialize, Serialize)]
96#[serde(deny_unknown_fields)]
97pub(crate) struct PathPolicy {
98    format: String,
99    normalization: String,
100    normalization_unicode_version: String,
101    case_folding: String,
102    case_folding_unicode_version: String,
103}
104
105#[derive(Debug, Clone, Deserialize, Serialize, PartialEq, Eq)]
106#[serde(deny_unknown_fields)]
107pub struct RootManifest {
108    path: String,
109    object_version_id: String,
110    content_sha256: String,
111    bytes: ExactU64,
112}
113
114#[derive(Debug, Clone, Copy, PartialEq, Eq)]
115pub enum PathBindingKind {
116    Directory,
117    RegularFile,
118    Symlink,
119}
120
121#[derive(Debug, Clone, Deserialize, Serialize, PartialEq, Eq)]
122#[serde(untagged)]
123pub enum PathBinding {
124    Directory(DirectoryBinding),
125    RegularFile(RegularFileBinding),
126    Symlink(SymlinkBinding),
127}
128
129#[derive(Debug, Clone, Deserialize, Serialize, PartialEq, Eq)]
130#[serde(deny_unknown_fields)]
131pub struct DirectoryBinding {
132    path: String,
133    object_id: String,
134    lifecycle: LiveLifecycle,
135    kind: DirectoryKind,
136}
137
138#[derive(Debug, Clone, Deserialize, Serialize, PartialEq, Eq)]
139#[serde(deny_unknown_fields)]
140pub struct RegularFileBinding {
141    path: String,
142    object_id: String,
143    lifecycle: LiveLifecycle,
144    kind: RegularFileKind,
145    object_version_id: String,
146    content_sha256: String,
147    bytes: ExactU64,
148    executable: bool,
149}
150
151#[derive(Debug, Clone, Deserialize, Serialize, PartialEq, Eq)]
152#[serde(deny_unknown_fields)]
153pub struct SymlinkBinding {
154    path: String,
155    object_id: String,
156    lifecycle: LiveLifecycle,
157    kind: SymlinkKind,
158    object_version_id: String,
159    target: String,
160    target_safety: SymlinkTargetSafety,
161}
162
163#[derive(Debug, Clone, Deserialize, Serialize, PartialEq, Eq)]
164#[serde(rename_all = "snake_case")]
165enum DirectoryKind {
166    Directory,
167}
168
169#[derive(Debug, Clone, Deserialize, Serialize, PartialEq, Eq)]
170#[serde(rename_all = "snake_case")]
171enum RegularFileKind {
172    RegularFile,
173}
174
175#[derive(Debug, Clone, Deserialize, Serialize, PartialEq, Eq)]
176#[serde(rename_all = "snake_case")]
177enum SymlinkKind {
178    Symlink,
179}
180
181#[derive(Debug, Clone, Deserialize, Serialize, PartialEq, Eq)]
182#[serde(rename_all = "snake_case")]
183enum LiveLifecycle {
184    Live,
185}
186
187#[derive(Debug, Clone, Deserialize, Serialize, PartialEq, Eq)]
188#[serde(rename_all = "kebab-case")]
189enum SymlinkTargetSafety {
190    RelativeWithinFolderbase,
191}
192
193#[derive(Debug, Clone, Deserialize, Serialize, PartialEq, Eq)]
194#[serde(deny_unknown_fields)]
195pub struct Tombstone {
196    path: String,
197    object_id: String,
198    lifecycle: DeletedLifecycle,
199    deleted_kind: DeletedKind,
200    last_object_version_id: Option<String>,
201}
202
203#[derive(Debug, Clone, Deserialize, Serialize, PartialEq, Eq)]
204#[serde(rename_all = "snake_case")]
205enum DeletedLifecycle {
206    Deleted,
207}
208
209#[derive(Debug, Clone, Copy, Deserialize, Serialize, PartialEq, Eq)]
210#[serde(rename_all = "snake_case")]
211pub enum DeletedKind {
212    Directory,
213    RegularFile,
214    Symlink,
215}
216
217#[derive(Debug, Clone, Deserialize, Serialize, PartialEq, Eq)]
218#[serde(deny_unknown_fields)]
219pub struct Exclusion {
220    path: String,
221    kind: ExclusionKind,
222    reason: ExclusionReason,
223}
224
225#[derive(Debug, Clone, Copy, Deserialize, Serialize, PartialEq, Eq)]
226#[serde(rename_all = "snake_case")]
227pub enum ExclusionKind {
228    NestedFolderbase,
229    HardLink,
230    Fifo,
231    Socket,
232    BlockDevice,
233    CharacterDevice,
234    OtherSpecial,
235}
236
237#[derive(Debug, Clone, Copy, Deserialize, Serialize, PartialEq, Eq)]
238#[serde(rename_all = "kebab-case")]
239pub enum ExclusionReason {
240    NestedFolderbaseBoundary,
241    UnsupportedV1,
242}
243
244// This phase deliberately exposes the producer seam before the later sealing
245// transaction consumes it.
246#[allow(dead_code)]
247impl FolderbaseVersionParts {
248    /// Assemble the closed v1 shape from producer-verified references.
249    ///
250    /// `FolderbaseVersion::from_verified_parts` still enforces every protocol
251    /// invariant before a value can exist.
252    pub(crate) fn portable_v1_from_verified_producer(
253        folderbase_id: impl Into<String>,
254        version_id: impl Into<String>,
255        parents: Vec<String>,
256        created_at: impl Into<String>,
257        root_manifest: RootManifest,
258        entries: FolderbaseVersionEntries,
259    ) -> Self {
260        Self::portable_v1_for_protocol_from_verified_producer(
261            VERSION_PROTOCOL_V04,
262            folderbase_id,
263            version_id,
264            parents,
265            created_at,
266            root_manifest,
267            entries,
268        )
269    }
270
271    pub(crate) fn portable_v1_for_protocol_from_verified_producer(
272        protocol_version: impl Into<String>,
273        folderbase_id: impl Into<String>,
274        version_id: impl Into<String>,
275        parents: Vec<String>,
276        created_at: impl Into<String>,
277        root_manifest: RootManifest,
278        entries: FolderbaseVersionEntries,
279    ) -> Self {
280        Self {
281            format: VERSION_FORMAT_V1.to_owned(),
282            protocol_version: protocol_version.into(),
283            folderbase_id: folderbase_id.into(),
284            version_id: version_id.into(),
285            parents,
286            created_at: created_at.into(),
287            path_policy: PathPolicy::portable_v1(),
288            root_manifest,
289            bindings: entries.bindings,
290            tombstones: entries.tombstones,
291            exclusions: entries.exclusions,
292        }
293    }
294}
295
296#[allow(dead_code)]
297impl FolderbaseVersionEntries {
298    pub(crate) fn from_verified_producer(
299        bindings: Vec<PathBinding>,
300        tombstones: Vec<Tombstone>,
301        exclusions: Vec<Exclusion>,
302    ) -> Self {
303        Self {
304            bindings,
305            tombstones,
306            exclusions,
307        }
308    }
309}
310
311#[allow(dead_code)]
312impl PathPolicy {
313    fn portable_v1() -> Self {
314        Self {
315            format: PATH_POLICY_FORMAT_V1.to_owned(),
316            normalization: "NFC".to_owned(),
317            normalization_unicode_version: "17.0.0".to_owned(),
318            case_folding: "full-default".to_owned(),
319            case_folding_unicode_version: "9.0.0".to_owned(),
320        }
321    }
322}
323
324#[allow(dead_code)]
325impl RootManifest {
326    pub(crate) fn from_verified_producer(
327        object_version_id: impl Into<String>,
328        content_sha256: impl Into<String>,
329        bytes: u64,
330    ) -> Self {
331        Self {
332            path: ".folderbase/manifest.json".to_owned(),
333            object_version_id: object_version_id.into(),
334            content_sha256: content_sha256.into(),
335            bytes: ExactU64(bytes),
336        }
337    }
338}
339
340#[allow(dead_code)]
341impl PathBinding {
342    pub(crate) fn directory_from_verified_producer(
343        path: impl Into<String>,
344        object_id: impl Into<String>,
345    ) -> Self {
346        Self::Directory(DirectoryBinding {
347            path: path.into(),
348            object_id: object_id.into(),
349            lifecycle: LiveLifecycle::Live,
350            kind: DirectoryKind::Directory,
351        })
352    }
353
354    pub(crate) fn regular_file_from_verified_producer(
355        path: impl Into<String>,
356        object_id: impl Into<String>,
357        object_version_id: impl Into<String>,
358        content_sha256: impl Into<String>,
359        bytes: u64,
360        executable: bool,
361    ) -> Self {
362        Self::RegularFile(RegularFileBinding {
363            path: path.into(),
364            object_id: object_id.into(),
365            lifecycle: LiveLifecycle::Live,
366            kind: RegularFileKind::RegularFile,
367            object_version_id: object_version_id.into(),
368            content_sha256: content_sha256.into(),
369            bytes: ExactU64(bytes),
370            executable,
371        })
372    }
373
374    pub(crate) fn symlink_from_verified_producer(
375        path: impl Into<String>,
376        object_id: impl Into<String>,
377        object_version_id: impl Into<String>,
378        target: impl Into<String>,
379    ) -> Self {
380        Self::Symlink(SymlinkBinding {
381            path: path.into(),
382            object_id: object_id.into(),
383            lifecycle: LiveLifecycle::Live,
384            kind: SymlinkKind::Symlink,
385            object_version_id: object_version_id.into(),
386            target: target.into(),
387            target_safety: SymlinkTargetSafety::RelativeWithinFolderbase,
388        })
389    }
390}
391
392#[allow(dead_code)]
393impl Tombstone {
394    pub(crate) fn from_verified_producer(
395        path: impl Into<String>,
396        object_id: impl Into<String>,
397        deleted_kind: DeletedKind,
398        last_object_version_id: Option<String>,
399    ) -> Self {
400        Self {
401            path: path.into(),
402            object_id: object_id.into(),
403            lifecycle: DeletedLifecycle::Deleted,
404            deleted_kind,
405            last_object_version_id,
406        }
407    }
408}
409
410#[allow(dead_code)]
411impl Exclusion {
412    pub(crate) fn from_verified_producer(
413        path: impl Into<String>,
414        kind: ExclusionKind,
415        reason: ExclusionReason,
416    ) -> Self {
417        Self {
418            path: path.into(),
419            kind,
420            reason,
421        }
422    }
423}
424
425#[derive(Debug, Clone, PartialEq, Eq)]
426pub struct FolderbaseVersionDiff {
427    changes: Vec<FolderbaseVersionChange>,
428}
429
430impl FolderbaseVersionDiff {
431    pub fn changes(&self) -> &[FolderbaseVersionChange] {
432        &self.changes
433    }
434}
435
436#[derive(Debug, Clone, PartialEq, Eq)]
437pub enum FolderbaseVersionChange {
438    RootManifestUpdated {
439        previous_object_version_id: String,
440        object_version_id: String,
441        previous_content_sha256: String,
442        content_sha256: String,
443    },
444    Added {
445        path: String,
446        object_id: String,
447    },
448    Deleted {
449        path: String,
450        object_id: String,
451        tombstone_present: bool,
452    },
453    Moved {
454        object_id: String,
455        from_path: String,
456        to_path: String,
457    },
458    Recreated {
459        path: String,
460        previous_object_id: String,
461        object_id: String,
462    },
463    Updated {
464        path: String,
465        object_id: String,
466        previous_object_version_id: Option<String>,
467        object_version_id: Option<String>,
468    },
469    TombstoneAdded {
470        path: String,
471        object_id: String,
472    },
473    TombstoneRemoved {
474        path: String,
475        object_id: String,
476    },
477    ExclusionAdded {
478        path: String,
479        kind: ExclusionKind,
480    },
481    ExclusionRemoved {
482        path: String,
483        kind: ExclusionKind,
484    },
485}
486
487#[derive(Debug, thiserror::Error)]
488pub enum FolderbaseVersionError {
489    #[error("encoded Folderbase Version exceeds {maximum_bytes} bytes")]
490    EncodedVersionTooLarge { maximum_bytes: u64 },
491
492    #[error("Folderbase Version is not valid JSON: {0}")]
493    InvalidJson(#[from] serde_json::Error),
494
495    #[error("could not write encoded Folderbase Version: {0}")]
496    EncodingIo(#[source] std::io::Error),
497
498    #[error("Folderbase Version violates the protocol: {0}")]
499    InvalidVersion(String),
500}
501
502impl FolderbaseVersion {
503    pub fn decode_bounded(mut reader: impl Read) -> Result<Self, FolderbaseVersionError> {
504        let mut encoded = Vec::new();
505        reader
506            .by_ref()
507            .take(MAX_ENCODED_VERSION_BYTES + 1)
508            .read_to_end(&mut encoded)
509            .map_err(serde_json::Error::io)?;
510        if encoded.len() as u64 > MAX_ENCODED_VERSION_BYTES {
511            return Err(FolderbaseVersionError::EncodedVersionTooLarge {
512                maximum_bytes: MAX_ENCODED_VERSION_BYTES,
513            });
514        }
515        Self::decode_verified_slice(&encoded)
516    }
517
518    /// Encode one already-validated Folderbase Version as bounded JSON.
519    ///
520    /// The public value intentionally does not implement `Serialize`; this
521    /// method is the only supported JSON encoding path.
522    pub fn encode_bounded(&self, mut writer: impl Write) -> Result<(), FolderbaseVersionError> {
523        self.validate()?;
524        let mut encoded = BoundedJsonBuffer::new(MAX_ENCODED_VERSION_BYTES as usize);
525        let result = serde_json::to_writer(&mut encoded, &FolderbaseVersionWireRef::from(self));
526        if encoded.exceeded {
527            return Err(FolderbaseVersionError::EncodedVersionTooLarge {
528                maximum_bytes: MAX_ENCODED_VERSION_BYTES,
529            });
530        }
531        result?;
532        writer
533            .write_all(&encoded.bytes)
534            .map_err(FolderbaseVersionError::EncodingIo)
535    }
536
537    /// Construct a validated value from a bounded in-memory representation.
538    ///
539    /// This crate-private seam is reserved for later producer transactions;
540    /// external callers continue to use `decode_bounded`.
541    pub(crate) fn decode_verified_slice(encoded: &[u8]) -> Result<Self, FolderbaseVersionError> {
542        if encoded.len() as u64 > MAX_ENCODED_VERSION_BYTES {
543            return Err(FolderbaseVersionError::EncodedVersionTooLarge {
544                maximum_bytes: MAX_ENCODED_VERSION_BYTES,
545            });
546        }
547        let counts: EntryCountProbe = serde_json::from_slice(encoded)?;
548        if counts.total() > MAX_VERSION_ENTRIES {
549            return invalid("Folderbase Version entry count exceeds the v1 limit");
550        }
551        let parts =
552            FolderbaseVersionParts::from(serde_json::from_slice::<FolderbaseVersionWire>(encoded)?);
553        Self::from_verified_parts(parts)
554    }
555
556    /// Construct one value from producer-verified parts, then independently
557    /// enforce every Folderbase Version invariant.
558    pub(crate) fn from_verified_parts(
559        parts: FolderbaseVersionParts,
560    ) -> Result<Self, FolderbaseVersionError> {
561        let version = Self {
562            format: parts.format,
563            protocol_version: parts.protocol_version,
564            folderbase_id: parts.folderbase_id,
565            version_id: parts.version_id,
566            parents: parts.parents,
567            created_at: parts.created_at,
568            path_policy: parts.path_policy,
569            root_manifest: parts.root_manifest,
570            bindings: parts.bindings,
571            tombstones: parts.tombstones,
572            exclusions: parts.exclusions,
573        };
574        version.validate()?;
575        Ok(version)
576    }
577
578    pub fn validate(&self) -> Result<(), FolderbaseVersionError> {
579        if self.format != VERSION_FORMAT_V1
580            || !matches!(
581                self.protocol_version.as_str(),
582                VERSION_PROTOCOL_V04 | VERSION_PROTOCOL_V05
583            )
584        {
585            return invalid("unsupported Folderbase Version format or protocol");
586        }
587        validate_prefixed_uuid(&self.folderbase_id, "folderbase_")?;
588        validate_prefixed_uuid(&self.version_id, "fbversion_")?;
589        if self.parents.len() > 2 {
590            return invalid("a Folderbase Version has at most two parents");
591        }
592        for parent in &self.parents {
593            validate_prefixed_uuid(parent, "fbversion_")?;
594            if parent == &self.version_id {
595                return invalid("a Folderbase Version cannot be its own parent");
596            }
597        }
598        if self.parents.len() == 2 && self.parents[0] == self.parents[1] {
599            return invalid("Folderbase Version parents must be unique");
600        }
601        let parsed = DateTime::parse_from_rfc3339(&self.created_at)
602            .map_err(|_| invalid_error("created_at must be canonical UTC RFC 3339 seconds"))?;
603        if parsed.offset().local_minus_utc() != 0
604            || parsed
605                .with_timezone(&Utc)
606                .to_rfc3339_opts(SecondsFormat::Secs, true)
607                != self.created_at
608        {
609            return invalid("created_at must be canonical UTC RFC 3339 seconds");
610        }
611        if self.path_policy.format != PATH_POLICY_FORMAT_V1
612            || self.path_policy.normalization != "NFC"
613            || self.path_policy.normalization_unicode_version != "17.0.0"
614            || self.path_policy.case_folding != "full-default"
615            || self.path_policy.case_folding_unicode_version != "9.0.0"
616        {
617            return invalid("unsupported portable path policy");
618        }
619        if unicode_normalization::UNICODE_VERSION != (17, 0, 0)
620            || unicode_casefold::UNICODE_VERSION != (9, 0, 0)
621        {
622            return invalid("Core build does not provide the declared Unicode path tables");
623        }
624        if self.root_manifest.path != ".folderbase/manifest.json" {
625            return invalid("root_manifest must name the exact reserved manifest path");
626        }
627        validate_prefixed_uuid(&self.root_manifest.object_version_id, "version_")?;
628        validate_sha256(&self.root_manifest.content_sha256)?;
629        if self.root_manifest.bytes.0 == 0 || self.root_manifest.bytes.0 > MAX_ROOT_MANIFEST_BYTES {
630            return invalid("root_manifest byte length is outside the v1 limit");
631        }
632        let total = self
633            .bindings
634            .len()
635            .saturating_add(self.tombstones.len())
636            .saturating_add(self.exclusions.len());
637        if total > MAX_VERSION_ENTRIES {
638            return invalid("Folderbase Version entry count exceeds the v1 limit");
639        }
640
641        validate_strict_path_order(self.bindings.iter().map(PathBinding::path), "bindings")?;
642        validate_strict_path_order(
643            self.tombstones
644                .iter()
645                .map(|tombstone| tombstone.path.as_str()),
646            "tombstones",
647        )?;
648        validate_strict_path_order(
649            self.exclusions
650                .iter()
651                .map(|exclusion| exclusion.path.as_str()),
652            "exclusions",
653        )?;
654
655        let mut current_paths = CollisionIndex::default();
656        let mut live_object_ids = BTreeSet::new();
657        let mut object_version_owners = BTreeMap::new();
658        object_version_owners.insert(
659            self.root_manifest.object_version_id.as_str(),
660            "__folderbase_root_manifest__",
661        );
662        for binding in &self.bindings {
663            let keys = validate_portable_path(binding.path())?;
664            current_paths.insert(binding.path(), keys, Some(binding.object_id()))?;
665            validate_prefixed_uuid(binding.object_id(), "obj_")?;
666            if !live_object_ids.insert(binding.object_id()) {
667                return invalid("one live Object ID is bound to more than one path");
668            }
669            match binding {
670                PathBinding::Directory(binding) => {
671                    let _ = (&binding.lifecycle, &binding.kind);
672                }
673                PathBinding::RegularFile(binding) => {
674                    let _ = (&binding.lifecycle, &binding.kind);
675                    validate_prefixed_uuid(&binding.object_version_id, "version_")?;
676                    bind_object_version(
677                        &mut object_version_owners,
678                        &binding.object_version_id,
679                        &binding.object_id,
680                    )?;
681                    validate_sha256(&binding.content_sha256)?;
682                    if binding.bytes.0 > MAX_OBJECT_BYTES {
683                        return invalid("regular file exceeds the v1 object-size limit");
684                    }
685                }
686                PathBinding::Symlink(binding) => {
687                    let _ = (&binding.lifecycle, &binding.kind, &binding.target_safety);
688                    validate_prefixed_uuid(&binding.object_version_id, "version_")?;
689                    bind_object_version(
690                        &mut object_version_owners,
691                        &binding.object_version_id,
692                        &binding.object_id,
693                    )?;
694                }
695            }
696        }
697        if self.protocol_version == VERSION_PROTOCOL_V04 {
698            for required_path in [".folderbaseignore", "FOLDERBASE.md"] {
699                if !self.bindings.iter().any(|binding| {
700                    binding.path() == required_path
701                        && matches!(binding, PathBinding::RegularFile(_))
702                }) {
703                    return invalid(format!(
704                        "{required_path} must be a live regular-file Path Binding"
705                    ));
706                }
707            }
708        }
709
710        for exclusion in &self.exclusions {
711            let keys = validate_portable_path(&exclusion.path)?;
712            current_paths.insert(&exclusion.path, keys, None)?;
713            match (exclusion.kind, exclusion.reason) {
714                (ExclusionKind::NestedFolderbase, ExclusionReason::NestedFolderbaseBoundary)
715                | (
716                    ExclusionKind::HardLink
717                    | ExclusionKind::Fifo
718                    | ExclusionKind::Socket
719                    | ExclusionKind::BlockDevice
720                    | ExclusionKind::CharacterDevice
721                    | ExclusionKind::OtherSpecial,
722                    ExclusionReason::UnsupportedV1,
723                ) => {}
724                _ => return invalid("exclusion kind and reason do not match"),
725            }
726        }
727
728        let mut tombstone_paths = CollisionIndex::default();
729        for tombstone in &self.tombstones {
730            let _ = &tombstone.lifecycle;
731            let keys = validate_portable_path(&tombstone.path)?;
732            tombstone_paths.insert(&tombstone.path, keys.clone(), Some(&tombstone.object_id))?;
733            if let Some(current) = current_paths.exact.get(tombstone.path.as_str()) {
734                match current.object_id {
735                    Some(current_object_id) if current_object_id != tombstone.object_id => {}
736                    Some(_) => {
737                        return invalid("same-path recreation must use a new stable Object ID");
738                    }
739                    None => {
740                        return invalid("a tombstone cannot occupy an excluded current path");
741                    }
742                }
743            } else {
744                current_paths.reject_alias(&tombstone.path, &keys)?;
745            }
746            validate_prefixed_uuid(&tombstone.object_id, "obj_")?;
747            if let Some(version_id) = &tombstone.last_object_version_id {
748                validate_prefixed_uuid(version_id, "version_")?;
749                bind_object_version(&mut object_version_owners, version_id, &tombstone.object_id)?;
750            }
751            match (
752                tombstone.deleted_kind,
753                tombstone.last_object_version_id.is_some(),
754            ) {
755                (DeletedKind::Directory, false)
756                | (DeletedKind::RegularFile | DeletedKind::Symlink, true) => {}
757                _ => {
758                    return invalid(
759                        "directory tombstones omit Object Version; content tombstones require it",
760                    );
761                }
762            }
763        }
764
765        let nested_boundaries = NestedBoundaryIndex::from_paths(
766            self.exclusions
767                .iter()
768                .filter(|exclusion| exclusion.kind == ExclusionKind::NestedFolderbase)
769                .map(|exclusion| exclusion.path.as_str()),
770        );
771        for boundary in nested_boundaries.iter() {
772            if nested_boundaries.contains_strict_ancestor(boundary) {
773                return invalid(format!(
774                    "nested Folderbase boundary overlaps its ancestor: {boundary}"
775                ));
776            }
777        }
778        for binding in &self.bindings {
779            reject_nested_descendant(binding.path(), &nested_boundaries)?;
780        }
781        for tombstone in &self.tombstones {
782            reject_nested_descendant(&tombstone.path, &nested_boundaries)?;
783        }
784        for exclusion in &self.exclusions {
785            if exclusion.kind != ExclusionKind::NestedFolderbase {
786                reject_nested_descendant(&exclusion.path, &nested_boundaries)?;
787            }
788        }
789        for binding in &self.bindings {
790            if let PathBinding::Symlink(symlink) = binding {
791                validate_symlink_target(&symlink.path, &symlink.target, &nested_boundaries)?;
792            }
793        }
794        Ok(())
795    }
796
797    pub fn version_id(&self) -> &str {
798        &self.version_id
799    }
800
801    pub fn folderbase_id(&self) -> &str {
802        &self.folderbase_id
803    }
804
805    pub fn protocol_version(&self) -> &str {
806        &self.protocol_version
807    }
808
809    pub fn parents(&self) -> &[String] {
810        &self.parents
811    }
812
813    pub fn created_at(&self) -> &str {
814        &self.created_at
815    }
816
817    pub fn root_manifest(&self) -> &RootManifest {
818        &self.root_manifest
819    }
820
821    pub fn bindings(&self) -> &[PathBinding] {
822        &self.bindings
823    }
824
825    pub fn tombstones(&self) -> &[Tombstone] {
826        &self.tombstones
827    }
828
829    pub fn exclusions(&self) -> &[Exclusion] {
830        &self.exclusions
831    }
832
833    pub fn binding_count(&self) -> usize {
834        self.bindings.len()
835    }
836
837    pub fn tombstone_count(&self) -> usize {
838        self.tombstones.len()
839    }
840
841    pub fn exclusion_count(&self) -> usize {
842        self.exclusions.len()
843    }
844
845    pub fn lookup_binding(&self, path: &str) -> Option<&PathBinding> {
846        self.bindings
847            .binary_search_by(|binding| binding.path().as_bytes().cmp(path.as_bytes()))
848            .ok()
849            .map(|index| &self.bindings[index])
850    }
851
852    pub fn canonical_digest(&self) -> Result<String, FolderbaseVersionError> {
853        self.validate()?;
854
855        let mut digest = Sha256::new();
856        digest.update(b"folderbase-version-v1\0");
857        update_identifier(&mut digest, &self.protocol_version);
858        update_identifier(&mut digest, &self.folderbase_id);
859        update_identifier(&mut digest, &self.version_id);
860        digest.update([self.parents.len() as u8]);
861        for parent in &self.parents {
862            update_identifier(&mut digest, parent);
863        }
864        update_identifier(&mut digest, &self.created_at);
865        update_identifier(&mut digest, &self.path_policy.format);
866        update_identifier(&mut digest, &self.path_policy.normalization);
867        update_identifier(&mut digest, &self.path_policy.normalization_unicode_version);
868        update_identifier(&mut digest, &self.path_policy.case_folding);
869        update_identifier(&mut digest, &self.path_policy.case_folding_unicode_version);
870        update_identifier(&mut digest, &self.root_manifest.path);
871        update_identifier(&mut digest, &self.root_manifest.object_version_id);
872        digest.update(decode_sha256(&self.root_manifest.content_sha256));
873        digest.update(self.root_manifest.bytes.0.to_be_bytes());
874
875        digest.update((self.bindings.len() as u32).to_be_bytes());
876        for binding in &self.bindings {
877            update_identifier(&mut digest, binding.path());
878            update_identifier(&mut digest, binding.object_id());
879            update_identifier(&mut digest, "live");
880            match binding {
881                PathBinding::Directory(_) => digest.update([0]),
882                PathBinding::RegularFile(binding) => {
883                    digest.update([1]);
884                    update_identifier(&mut digest, &binding.object_version_id);
885                    digest.update(decode_sha256(&binding.content_sha256));
886                    digest.update(binding.bytes.0.to_be_bytes());
887                    digest.update([u8::from(binding.executable)]);
888                }
889                PathBinding::Symlink(binding) => {
890                    digest.update([2]);
891                    update_identifier(&mut digest, &binding.object_version_id);
892                    update_identifier(&mut digest, &binding.target);
893                    update_identifier(&mut digest, "relative-within-folderbase");
894                }
895            }
896        }
897
898        digest.update((self.tombstones.len() as u32).to_be_bytes());
899        for tombstone in &self.tombstones {
900            update_identifier(&mut digest, &tombstone.path);
901            update_identifier(&mut digest, &tombstone.object_id);
902            update_identifier(&mut digest, "deleted");
903            digest.update([match tombstone.deleted_kind {
904                DeletedKind::Directory => 0,
905                DeletedKind::RegularFile => 1,
906                DeletedKind::Symlink => 2,
907            }]);
908            match &tombstone.last_object_version_id {
909                Some(version_id) => {
910                    digest.update([1]);
911                    update_identifier(&mut digest, version_id);
912                }
913                None => digest.update([0]),
914            }
915        }
916
917        digest.update((self.exclusions.len() as u32).to_be_bytes());
918        for exclusion in &self.exclusions {
919            update_identifier(&mut digest, &exclusion.path);
920            digest.update([match exclusion.kind {
921                ExclusionKind::NestedFolderbase => 0,
922                ExclusionKind::HardLink => 1,
923                ExclusionKind::Fifo => 2,
924                ExclusionKind::Socket => 3,
925                ExclusionKind::BlockDevice => 4,
926                ExclusionKind::CharacterDevice => 5,
927                ExclusionKind::OtherSpecial => 6,
928            }]);
929            update_identifier(
930                &mut digest,
931                match exclusion.reason {
932                    ExclusionReason::NestedFolderbaseBoundary => "nested-folderbase-boundary",
933                    ExclusionReason::UnsupportedV1 => "unsupported-v1",
934                },
935            );
936        }
937
938        Ok(digest_hex(&digest.finalize()))
939    }
940
941    pub fn diff(&self, newer: &Self) -> Result<FolderbaseVersionDiff, FolderbaseVersionError> {
942        self.validate()?;
943        newer.validate()?;
944        if self.folderbase_id != newer.folderbase_id {
945            return invalid("cannot diff Folderbase Versions from different Folderbases");
946        }
947
948        let mut changes = Vec::new();
949        if self.root_manifest != newer.root_manifest {
950            changes.push(FolderbaseVersionChange::RootManifestUpdated {
951                previous_object_version_id: self.root_manifest.object_version_id.clone(),
952                object_version_id: newer.root_manifest.object_version_id.clone(),
953                previous_content_sha256: self.root_manifest.content_sha256.clone(),
954                content_sha256: newer.root_manifest.content_sha256.clone(),
955            });
956        }
957
958        let previous_by_object = self
959            .bindings
960            .iter()
961            .map(|binding| (binding.object_id(), binding))
962            .collect::<BTreeMap<_, _>>();
963        let current_by_object = newer
964            .bindings
965            .iter()
966            .map(|binding| (binding.object_id(), binding))
967            .collect::<BTreeMap<_, _>>();
968        for (object_id, previous) in &previous_by_object {
969            if let Some(current) = current_by_object.get(object_id)
970                && previous.path() != current.path()
971            {
972                changes.push(FolderbaseVersionChange::Moved {
973                    object_id: (*object_id).to_owned(),
974                    from_path: previous.path().to_owned(),
975                    to_path: current.path().to_owned(),
976                });
977                if !previous.state_eq_ignoring_path(current) {
978                    changes.push(FolderbaseVersionChange::Updated {
979                        path: current.path().to_owned(),
980                        object_id: (*object_id).to_owned(),
981                        previous_object_version_id: previous.object_version_id().map(str::to_owned),
982                        object_version_id: current.object_version_id().map(str::to_owned),
983                    });
984                }
985            }
986        }
987
988        let previous_by_path = self
989            .bindings
990            .iter()
991            .map(|binding| (binding.path(), binding))
992            .collect::<BTreeMap<_, _>>();
993        let current_by_path = newer
994            .bindings
995            .iter()
996            .map(|binding| (binding.path(), binding))
997            .collect::<BTreeMap<_, _>>();
998        let all_paths = previous_by_path
999            .keys()
1000            .chain(current_by_path.keys())
1001            .copied()
1002            .collect::<BTreeSet<_>>();
1003        for path in all_paths {
1004            match (previous_by_path.get(path), current_by_path.get(path)) {
1005                (None, Some(current)) if !previous_by_object.contains_key(current.object_id()) => {
1006                    changes.push(FolderbaseVersionChange::Added {
1007                        path: path.to_owned(),
1008                        object_id: current.object_id().to_owned(),
1009                    });
1010                }
1011                (Some(previous), None) if !current_by_object.contains_key(previous.object_id()) => {
1012                    let tombstone_present = newer.tombstones.iter().any(|tombstone| {
1013                        tombstone.path == path && tombstone.object_id == previous.object_id()
1014                    });
1015                    changes.push(FolderbaseVersionChange::Deleted {
1016                        path: path.to_owned(),
1017                        object_id: previous.object_id().to_owned(),
1018                        tombstone_present,
1019                    });
1020                }
1021                (Some(previous), Some(current)) if previous.object_id() != current.object_id() => {
1022                    changes.push(FolderbaseVersionChange::Recreated {
1023                        path: path.to_owned(),
1024                        previous_object_id: previous.object_id().to_owned(),
1025                        object_id: current.object_id().to_owned(),
1026                    });
1027                }
1028                (Some(previous), Some(current)) if *previous != *current => {
1029                    changes.push(FolderbaseVersionChange::Updated {
1030                        path: path.to_owned(),
1031                        object_id: current.object_id().to_owned(),
1032                        previous_object_version_id: previous.object_version_id().map(str::to_owned),
1033                        object_version_id: current.object_version_id().map(str::to_owned),
1034                    });
1035                }
1036                _ => {}
1037            }
1038        }
1039
1040        let previous_tombstones = self
1041            .tombstones
1042            .iter()
1043            .map(|tombstone| {
1044                (
1045                    (tombstone.path.as_str(), tombstone.object_id.as_str()),
1046                    tombstone,
1047                )
1048            })
1049            .collect::<BTreeMap<_, _>>();
1050        let current_tombstones = newer
1051            .tombstones
1052            .iter()
1053            .map(|tombstone| {
1054                (
1055                    (tombstone.path.as_str(), tombstone.object_id.as_str()),
1056                    tombstone,
1057                )
1058            })
1059            .collect::<BTreeMap<_, _>>();
1060        let tombstone_keys = previous_tombstones
1061            .keys()
1062            .chain(current_tombstones.keys())
1063            .copied()
1064            .collect::<BTreeSet<_>>();
1065        for (path, object_id) in tombstone_keys {
1066            match (
1067                previous_tombstones.get(&(path, object_id)),
1068                current_tombstones.get(&(path, object_id)),
1069            ) {
1070                (None, Some(_)) => {
1071                    changes.push(FolderbaseVersionChange::TombstoneAdded {
1072                        path: path.to_owned(),
1073                        object_id: object_id.to_owned(),
1074                    });
1075                }
1076                (Some(_), None) => {
1077                    changes.push(FolderbaseVersionChange::TombstoneRemoved {
1078                        path: path.to_owned(),
1079                        object_id: object_id.to_owned(),
1080                    });
1081                }
1082                (Some(previous), Some(current)) if *previous != *current => {
1083                    changes.push(FolderbaseVersionChange::TombstoneRemoved {
1084                        path: path.to_owned(),
1085                        object_id: object_id.to_owned(),
1086                    });
1087                    changes.push(FolderbaseVersionChange::TombstoneAdded {
1088                        path: path.to_owned(),
1089                        object_id: object_id.to_owned(),
1090                    });
1091                }
1092                _ => {}
1093            }
1094        }
1095
1096        let previous_exclusions = self
1097            .exclusions
1098            .iter()
1099            .map(|exclusion| (exclusion.path.as_str(), exclusion))
1100            .collect::<BTreeMap<_, _>>();
1101        let current_exclusions = newer
1102            .exclusions
1103            .iter()
1104            .map(|exclusion| (exclusion.path.as_str(), exclusion))
1105            .collect::<BTreeMap<_, _>>();
1106        let exclusion_paths = previous_exclusions
1107            .keys()
1108            .chain(current_exclusions.keys())
1109            .copied()
1110            .collect::<BTreeSet<_>>();
1111        for path in exclusion_paths {
1112            match (previous_exclusions.get(path), current_exclusions.get(path)) {
1113                (None, Some(current)) => {
1114                    changes.push(FolderbaseVersionChange::ExclusionAdded {
1115                        path: path.to_owned(),
1116                        kind: current.kind,
1117                    });
1118                }
1119                (Some(previous), None) => {
1120                    changes.push(FolderbaseVersionChange::ExclusionRemoved {
1121                        path: path.to_owned(),
1122                        kind: previous.kind,
1123                    });
1124                }
1125                (Some(previous), Some(current)) if *previous != *current => {
1126                    changes.push(FolderbaseVersionChange::ExclusionRemoved {
1127                        path: path.to_owned(),
1128                        kind: previous.kind,
1129                    });
1130                    changes.push(FolderbaseVersionChange::ExclusionAdded {
1131                        path: path.to_owned(),
1132                        kind: current.kind,
1133                    });
1134                }
1135                _ => {}
1136            }
1137        }
1138
1139        changes.sort_by_cached_key(change_sort_key);
1140        Ok(FolderbaseVersionDiff { changes })
1141    }
1142}
1143
1144struct BoundedJsonBuffer {
1145    bytes: Vec<u8>,
1146    maximum: usize,
1147    exceeded: bool,
1148}
1149
1150impl BoundedJsonBuffer {
1151    fn new(maximum: usize) -> Self {
1152        Self {
1153            bytes: Vec::with_capacity(4096),
1154            maximum,
1155            exceeded: false,
1156        }
1157    }
1158}
1159
1160impl Write for BoundedJsonBuffer {
1161    fn write(&mut self, bytes: &[u8]) -> std::io::Result<usize> {
1162        let Some(length) = self.bytes.len().checked_add(bytes.len()) else {
1163            self.exceeded = true;
1164            return Err(std::io::Error::other(
1165                "Folderbase Version encoded length overflowed",
1166            ));
1167        };
1168        if length > self.maximum {
1169            self.exceeded = true;
1170            return Err(std::io::Error::other(
1171                "Folderbase Version encoded length exceeded its limit",
1172            ));
1173        }
1174        self.bytes.extend_from_slice(bytes);
1175        Ok(bytes.len())
1176    }
1177
1178    fn flush(&mut self) -> std::io::Result<()> {
1179        Ok(())
1180    }
1181}
1182
1183#[derive(Serialize)]
1184struct FolderbaseVersionWireRef<'a> {
1185    format: &'a str,
1186    protocol_version: &'a str,
1187    folderbase_id: &'a str,
1188    version_id: &'a str,
1189    parents: &'a [String],
1190    created_at: &'a str,
1191    path_policy: &'a PathPolicy,
1192    root_manifest: &'a RootManifest,
1193    bindings: &'a [PathBinding],
1194    tombstones: &'a [Tombstone],
1195    exclusions: &'a [Exclusion],
1196}
1197
1198impl<'a> From<&'a FolderbaseVersion> for FolderbaseVersionWireRef<'a> {
1199    fn from(version: &'a FolderbaseVersion) -> Self {
1200        Self {
1201            format: &version.format,
1202            protocol_version: &version.protocol_version,
1203            folderbase_id: &version.folderbase_id,
1204            version_id: &version.version_id,
1205            parents: &version.parents,
1206            created_at: &version.created_at,
1207            path_policy: &version.path_policy,
1208            root_manifest: &version.root_manifest,
1209            bindings: &version.bindings,
1210            tombstones: &version.tombstones,
1211            exclusions: &version.exclusions,
1212        }
1213    }
1214}
1215
1216impl From<FolderbaseVersionWire> for FolderbaseVersionParts {
1217    fn from(wire: FolderbaseVersionWire) -> Self {
1218        Self {
1219            format: wire.format,
1220            protocol_version: wire.protocol_version,
1221            folderbase_id: wire.folderbase_id,
1222            version_id: wire.version_id,
1223            parents: wire.parents,
1224            created_at: wire.created_at,
1225            path_policy: wire.path_policy,
1226            root_manifest: wire.root_manifest,
1227            bindings: wire.bindings,
1228            tombstones: wire.tombstones,
1229            exclusions: wire.exclusions,
1230        }
1231    }
1232}
1233
1234impl PathBinding {
1235    pub fn path(&self) -> &str {
1236        match self {
1237            Self::Directory(binding) => &binding.path,
1238            Self::RegularFile(binding) => &binding.path,
1239            Self::Symlink(binding) => &binding.path,
1240        }
1241    }
1242
1243    pub fn object_id(&self) -> &str {
1244        match self {
1245            Self::Directory(binding) => &binding.object_id,
1246            Self::RegularFile(binding) => &binding.object_id,
1247            Self::Symlink(binding) => &binding.object_id,
1248        }
1249    }
1250
1251    pub fn kind(&self) -> PathBindingKind {
1252        match self {
1253            Self::Directory(_) => PathBindingKind::Directory,
1254            Self::RegularFile(_) => PathBindingKind::RegularFile,
1255            Self::Symlink(_) => PathBindingKind::Symlink,
1256        }
1257    }
1258
1259    pub fn object_version_id(&self) -> Option<&str> {
1260        match self {
1261            Self::Directory(_) => None,
1262            Self::RegularFile(binding) => Some(&binding.object_version_id),
1263            Self::Symlink(binding) => Some(&binding.object_version_id),
1264        }
1265    }
1266
1267    pub fn bytes(&self) -> Option<u64> {
1268        match self {
1269            Self::RegularFile(binding) => Some(binding.bytes.0),
1270            _ => None,
1271        }
1272    }
1273
1274    pub fn executable(&self) -> Option<bool> {
1275        match self {
1276            Self::RegularFile(binding) => Some(binding.executable),
1277            _ => None,
1278        }
1279    }
1280
1281    pub fn symlink_target(&self) -> Option<&str> {
1282        match self {
1283            Self::Symlink(binding) => Some(&binding.target),
1284            _ => None,
1285        }
1286    }
1287
1288    pub fn content_sha256(&self) -> Option<&str> {
1289        match self {
1290            Self::RegularFile(binding) => Some(&binding.content_sha256),
1291            _ => None,
1292        }
1293    }
1294
1295    fn state_eq_ignoring_path(&self, other: &Self) -> bool {
1296        match (self, other) {
1297            (Self::Directory(previous), Self::Directory(current)) => {
1298                previous.object_id == current.object_id
1299                    && previous.lifecycle == current.lifecycle
1300                    && previous.kind == current.kind
1301            }
1302            (Self::RegularFile(previous), Self::RegularFile(current)) => {
1303                previous.object_id == current.object_id
1304                    && previous.lifecycle == current.lifecycle
1305                    && previous.kind == current.kind
1306                    && previous.object_version_id == current.object_version_id
1307                    && previous.content_sha256 == current.content_sha256
1308                    && previous.bytes == current.bytes
1309                    && previous.executable == current.executable
1310            }
1311            (Self::Symlink(previous), Self::Symlink(current)) => {
1312                previous.object_id == current.object_id
1313                    && previous.lifecycle == current.lifecycle
1314                    && previous.kind == current.kind
1315                    && previous.object_version_id == current.object_version_id
1316                    && previous.target == current.target
1317                    && previous.target_safety == current.target_safety
1318            }
1319            _ => false,
1320        }
1321    }
1322}
1323
1324impl RootManifest {
1325    pub fn path(&self) -> &str {
1326        &self.path
1327    }
1328
1329    pub fn object_version_id(&self) -> &str {
1330        &self.object_version_id
1331    }
1332
1333    pub fn content_sha256(&self) -> &str {
1334        &self.content_sha256
1335    }
1336
1337    pub fn bytes(&self) -> u64 {
1338        self.bytes.0
1339    }
1340}
1341
1342impl Tombstone {
1343    pub fn path(&self) -> &str {
1344        &self.path
1345    }
1346
1347    pub fn object_id(&self) -> &str {
1348        &self.object_id
1349    }
1350
1351    pub fn deleted_kind(&self) -> DeletedKind {
1352        self.deleted_kind
1353    }
1354
1355    pub fn last_object_version_id(&self) -> Option<&str> {
1356        self.last_object_version_id.as_deref()
1357    }
1358}
1359
1360impl Exclusion {
1361    pub fn path(&self) -> &str {
1362        &self.path
1363    }
1364
1365    pub fn kind(&self) -> ExclusionKind {
1366        self.kind
1367    }
1368
1369    pub fn reason(&self) -> ExclusionReason {
1370        self.reason
1371    }
1372}
1373
1374fn validate_prefixed_uuid(value: &str, prefix: &str) -> Result<(), FolderbaseVersionError> {
1375    let Some(uuid) = value.strip_prefix(prefix) else {
1376        return invalid("identifier uses the wrong namespace");
1377    };
1378    let parsed = Uuid::parse_str(uuid).map_err(|_| invalid_error("identifier is not a UUID"))?;
1379    if parsed.hyphenated().to_string() != uuid {
1380        return invalid("identifier UUID is not canonical lowercase hyphenated text");
1381    }
1382    if !(1..=8).contains(&(parsed.as_bytes()[6] >> 4))
1383        || parsed.as_bytes()[8] & 0b1100_0000 != 0b1000_0000
1384    {
1385        return invalid("identifier UUID has an unsupported version or variant");
1386    }
1387    Ok(())
1388}
1389
1390fn validate_sha256(value: &str) -> Result<(), FolderbaseVersionError> {
1391    if value.len() != 64
1392        || !value
1393            .bytes()
1394            .all(|byte| byte.is_ascii_digit() || (b'a'..=b'f').contains(&byte))
1395    {
1396        return invalid("content digest is not lowercase hexadecimal SHA-256");
1397    }
1398    Ok(())
1399}
1400
1401fn update_identifier(digest: &mut Sha256, value: &str) {
1402    digest.update((value.len() as u32).to_be_bytes());
1403    digest.update(value.as_bytes());
1404}
1405
1406fn decode_sha256(value: &str) -> [u8; 32] {
1407    let mut decoded = [0_u8; 32];
1408    for (destination, encoded) in decoded.iter_mut().zip(value.as_bytes().chunks_exact(2)) {
1409        *destination = (hex_nibble(encoded[0]) << 4) | hex_nibble(encoded[1]);
1410    }
1411    decoded
1412}
1413
1414fn hex_nibble(byte: u8) -> u8 {
1415    match byte {
1416        b'0'..=b'9' => byte - b'0',
1417        b'a'..=b'f' => byte - b'a' + 10,
1418        _ => unreachable!("digest syntax is validated before canonical encoding"),
1419    }
1420}
1421
1422fn digest_hex(bytes: &[u8]) -> String {
1423    let mut encoded = String::with_capacity(bytes.len() * 2);
1424    for byte in bytes {
1425        write!(&mut encoded, "{byte:02x}").expect("writing to String cannot fail");
1426    }
1427    encoded
1428}
1429
1430fn change_sort_key(change: &FolderbaseVersionChange) -> (String, u8, String) {
1431    match change {
1432        FolderbaseVersionChange::RootManifestUpdated { .. } => (String::new(), 0, String::new()),
1433        FolderbaseVersionChange::Moved {
1434            object_id,
1435            from_path,
1436            ..
1437        } => (from_path.clone(), 1, object_id.clone()),
1438        FolderbaseVersionChange::Recreated {
1439            path, object_id, ..
1440        } => (path.clone(), 2, object_id.clone()),
1441        FolderbaseVersionChange::Added { path, object_id } => (path.clone(), 3, object_id.clone()),
1442        FolderbaseVersionChange::Updated {
1443            path, object_id, ..
1444        } => (path.clone(), 4, object_id.clone()),
1445        FolderbaseVersionChange::Deleted {
1446            path, object_id, ..
1447        } => (path.clone(), 5, object_id.clone()),
1448        FolderbaseVersionChange::TombstoneAdded { path, object_id } => {
1449            (path.clone(), 6, object_id.clone())
1450        }
1451        FolderbaseVersionChange::TombstoneRemoved { path, object_id } => {
1452            (path.clone(), 7, object_id.clone())
1453        }
1454        FolderbaseVersionChange::ExclusionAdded { path, .. } => (path.clone(), 8, String::new()),
1455        FolderbaseVersionChange::ExclusionRemoved { path, .. } => (path.clone(), 9, String::new()),
1456    }
1457}
1458
1459#[derive(Debug, Clone)]
1460struct PathKeys {
1461    nfc: String,
1462    folded: String,
1463}
1464
1465#[derive(Default)]
1466struct CollisionIndex<'a> {
1467    exact: BTreeMap<&'a str, PathOwner<'a>>,
1468    nfc: BTreeMap<String, &'a str>,
1469    folded: BTreeMap<String, &'a str>,
1470}
1471
1472#[derive(Clone, Copy)]
1473struct PathOwner<'a> {
1474    object_id: Option<&'a str>,
1475}
1476
1477impl<'a> CollisionIndex<'a> {
1478    fn insert(
1479        &mut self,
1480        path: &'a str,
1481        keys: PathKeys,
1482        object_id: Option<&'a str>,
1483    ) -> Result<(), FolderbaseVersionError> {
1484        if self.exact.insert(path, PathOwner { object_id }).is_some() {
1485            return invalid("exact portable paths collide");
1486        }
1487        if self.nfc.insert(keys.nfc, path).is_some() {
1488            return invalid("portable paths collide after NFC normalization");
1489        }
1490        if self.folded.insert(keys.folded, path).is_some() {
1491            return invalid("portable paths collide after full default case folding");
1492        }
1493        Ok(())
1494    }
1495
1496    fn reject_alias(&self, path: &str, keys: &PathKeys) -> Result<(), FolderbaseVersionError> {
1497        if self
1498            .nfc
1499            .get(&keys.nfc)
1500            .is_some_and(|existing| *existing != path)
1501        {
1502            return invalid("portable paths collide after NFC normalization");
1503        }
1504        if self
1505            .folded
1506            .get(&keys.folded)
1507            .is_some_and(|existing| *existing != path)
1508        {
1509            return invalid("portable paths collide after full default case folding");
1510        }
1511        Ok(())
1512    }
1513}
1514
1515fn validate_strict_path_order<'a>(
1516    paths: impl Iterator<Item = &'a str>,
1517    label: &str,
1518) -> Result<(), FolderbaseVersionError> {
1519    let mut previous: Option<&[u8]> = None;
1520    for path in paths {
1521        if previous.is_some_and(|previous| previous >= path.as_bytes()) {
1522            return invalid(format!(
1523                "{label} must be strictly sorted by exact UTF-8 path bytes"
1524            ));
1525        }
1526        previous = Some(path.as_bytes());
1527    }
1528    Ok(())
1529}
1530
1531pub(crate) fn validate_capture_path(path: &str) -> Result<(), FolderbaseVersionError> {
1532    validate_portable_path(path).map(|_| ())
1533}
1534
1535pub(crate) fn validate_capture_version_id(value: &str) -> Result<(), FolderbaseVersionError> {
1536    validate_prefixed_uuid(value, "fbversion_")
1537}
1538
1539pub(crate) fn validate_capture_sha256(value: &str) -> Result<(), FolderbaseVersionError> {
1540    validate_sha256(value)
1541}
1542
1543pub(crate) fn validate_capture_symlink_targets<'a>(
1544    targets: impl IntoIterator<Item = (&'a str, &'a str)>,
1545    nested_boundaries: &[String],
1546) -> Result<(), &'a str> {
1547    let nested_boundaries =
1548        NestedBoundaryIndex::from_paths(nested_boundaries.iter().map(String::as_str));
1549    for (link_path, target) in targets {
1550        if validate_symlink_target(link_path, target, &nested_boundaries).is_err() {
1551            return Err(link_path);
1552        }
1553    }
1554    Ok(())
1555}
1556
1557fn validate_portable_path(path: &str) -> Result<PathKeys, FolderbaseVersionError> {
1558    let bytes = path.as_bytes();
1559    let drive_prefix = bytes.len() >= 2 && bytes[0].is_ascii_alphabetic() && bytes[1] == b':';
1560    if bytes.is_empty()
1561        || bytes.len() > MAX_PATH_BYTES
1562        || path.starts_with('/')
1563        || path.ends_with('/')
1564        || path.contains('\\')
1565        || path.contains('\0')
1566        || drive_prefix
1567    {
1568        return invalid(format!("unsafe portable path: {path}"));
1569    }
1570    let components = path.split('/').collect::<Vec<_>>();
1571    if components.len() > MAX_PATH_DEPTH {
1572        return invalid("portable path exceeds the v1 depth limit");
1573    }
1574    for component in components {
1575        validate_portable_component(component)?;
1576    }
1577    Ok(PathKeys {
1578        nfc: path.nfc().collect(),
1579        folded: path
1580            .nfc()
1581            .collect::<String>()
1582            .case_fold()
1583            .collect::<String>()
1584            .nfc()
1585            .collect(),
1586    })
1587}
1588
1589fn validate_portable_component(component: &str) -> Result<(), FolderbaseVersionError> {
1590    if component.is_empty()
1591        || matches!(component, "." | "..")
1592        || component.len() > MAX_PATH_COMPONENT_BYTES
1593        || component.ends_with(['.', ' '])
1594        || component.eq_ignore_ascii_case(".folderbase")
1595        || component
1596            .chars()
1597            .any(|character| character <= '\u{1f}' || r#"<>:"|?*"#.contains(character))
1598    {
1599        return invalid(format!("unsafe portable path component: {component}"));
1600    }
1601    let stem = component.split('.').next().unwrap_or(component);
1602    let uppercase_stem = stem.to_ascii_uppercase();
1603    let reserved = matches!(
1604        uppercase_stem.as_str(),
1605        "CON"
1606            | "PRN"
1607            | "AUX"
1608            | "NUL"
1609            | "COM1"
1610            | "COM2"
1611            | "COM3"
1612            | "COM4"
1613            | "COM5"
1614            | "COM6"
1615            | "COM7"
1616            | "COM8"
1617            | "COM9"
1618            | "LPT1"
1619            | "LPT2"
1620            | "LPT3"
1621            | "LPT4"
1622            | "LPT5"
1623            | "LPT6"
1624            | "LPT7"
1625            | "LPT8"
1626            | "LPT9"
1627            | "COM¹"
1628            | "COM²"
1629            | "COM³"
1630            | "LPT¹"
1631            | "LPT²"
1632            | "LPT³"
1633    );
1634    if reserved {
1635        return invalid(format!(
1636            "Windows-reserved portable path component: {component}"
1637        ));
1638    }
1639    Ok(())
1640}
1641
1642fn bind_object_version<'a>(
1643    owners: &mut BTreeMap<&'a str, &'a str>,
1644    version_id: &'a str,
1645    object_id: &'a str,
1646) -> Result<(), FolderbaseVersionError> {
1647    if owners
1648        .insert(version_id, object_id)
1649        .is_some_and(|existing| existing != object_id)
1650    {
1651        return invalid("one Object Version is referenced by different Object IDs");
1652    }
1653    Ok(())
1654}
1655
1656fn reject_nested_descendant(
1657    path: &str,
1658    boundaries: &NestedBoundaryIndex,
1659) -> Result<(), FolderbaseVersionError> {
1660    let path = portable_folded_key(path);
1661    if boundaries.contains_strict_ancestor(&path) {
1662        return invalid(format!(
1663            "path enters an excluded nested Folderbase boundary: {path}"
1664        ));
1665    }
1666    Ok(())
1667}
1668
1669fn validate_symlink_target(
1670    link_path: &str,
1671    target: &str,
1672    nested_boundaries: &NestedBoundaryIndex,
1673) -> Result<(), FolderbaseVersionError> {
1674    let bytes = target.as_bytes();
1675    let drive_prefix = bytes.len() >= 2 && bytes[0].is_ascii_alphabetic() && bytes[1] == b':';
1676    if bytes.is_empty()
1677        || bytes.len() > MAX_PATH_BYTES
1678        || target.starts_with('/')
1679        || target.ends_with('/')
1680        || target.contains('\\')
1681        || target.contains('\0')
1682        || target.contains("//")
1683        || drive_prefix
1684    {
1685        return invalid("symlink target is not a portable relative target");
1686    }
1687
1688    let mut resolved = link_path.split('/').rev().skip(1).collect::<Vec<_>>();
1689    resolved.reverse();
1690    for component in target.split('/') {
1691        match component {
1692            "." => {}
1693            ".." => {
1694                if resolved.pop().is_none() {
1695                    return invalid("symlink target escapes the Folderbase root");
1696                }
1697            }
1698            component => {
1699                validate_portable_component(component)?;
1700                resolved.push(component);
1701                if resolved.len() > MAX_PATH_DEPTH {
1702                    return invalid("symlink target exceeds the v1 path depth limit");
1703                }
1704            }
1705        }
1706    }
1707    let resolved = resolved.join("/");
1708    if !resolved.is_empty() {
1709        validate_portable_path(&resolved)?;
1710        if resolved.eq_ignore_ascii_case(".folderbase")
1711            || resolved
1712                .split('/')
1713                .next()
1714                .is_some_and(|component| component.eq_ignore_ascii_case(".folderbase"))
1715        {
1716            return invalid("symlink target enters Folderbase protocol state");
1717        }
1718        let folded_resolved = portable_folded_key(&resolved);
1719        if nested_boundaries.contains_or_ancestor(&folded_resolved) {
1720            return invalid("symlink target enters a nested Folderbase boundary");
1721        }
1722    }
1723    Ok(())
1724}
1725
1726struct NestedBoundaryIndex {
1727    folded: BTreeSet<String>,
1728}
1729
1730impl NestedBoundaryIndex {
1731    fn from_paths<'a>(paths: impl IntoIterator<Item = &'a str>) -> Self {
1732        Self {
1733            folded: paths.into_iter().map(portable_folded_key).collect(),
1734        }
1735    }
1736
1737    fn iter(&self) -> impl Iterator<Item = &str> {
1738        self.folded.iter().map(String::as_str)
1739    }
1740
1741    fn contains_or_ancestor(&self, folded_path: &str) -> bool {
1742        self.contains_ancestor_with(folded_path, true, |_| {})
1743    }
1744
1745    fn contains_strict_ancestor(&self, folded_path: &str) -> bool {
1746        self.contains_ancestor_with(folded_path, false, |_| {})
1747    }
1748
1749    fn contains_ancestor_with(
1750        &self,
1751        folded_path: &str,
1752        include_exact: bool,
1753        mut inspect: impl FnMut(&str),
1754    ) -> bool {
1755        for (separator, _) in folded_path.match_indices('/') {
1756            let ancestor = &folded_path[..separator];
1757            inspect(ancestor);
1758            if self.folded.contains(ancestor) {
1759                return true;
1760            }
1761        }
1762        if include_exact {
1763            inspect(folded_path);
1764            if self.folded.contains(folded_path) {
1765                return true;
1766            }
1767        }
1768        false
1769    }
1770
1771    #[cfg(test)]
1772    fn len(&self) -> usize {
1773        self.folded.len()
1774    }
1775
1776    #[cfg(test)]
1777    fn probe_count(&self, folded_path: &str, include_exact: bool) -> usize {
1778        let mut probes = 0;
1779        let _ = self.contains_ancestor_with(folded_path, include_exact, |_| probes += 1);
1780        probes
1781    }
1782}
1783
1784fn portable_folded_key(path: &str) -> String {
1785    path.nfc()
1786        .collect::<String>()
1787        .case_fold()
1788        .collect::<String>()
1789        .nfc()
1790        .collect()
1791}
1792
1793fn invalid<T>(message: impl Into<String>) -> Result<T, FolderbaseVersionError> {
1794    Err(invalid_error(message))
1795}
1796
1797fn invalid_error(message: impl Into<String>) -> FolderbaseVersionError {
1798    FolderbaseVersionError::InvalidVersion(message.into())
1799}
1800
1801#[derive(Deserialize)]
1802struct EntryCountProbe {
1803    bindings: EntryCount,
1804    tombstones: EntryCount,
1805    exclusions: EntryCount,
1806}
1807
1808impl EntryCountProbe {
1809    fn total(&self) -> usize {
1810        self.bindings
1811            .0
1812            .saturating_add(self.tombstones.0)
1813            .saturating_add(self.exclusions.0)
1814    }
1815}
1816
1817struct EntryCount(usize);
1818
1819impl<'de> Deserialize<'de> for EntryCount {
1820    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
1821    where
1822        D: serde::Deserializer<'de>,
1823    {
1824        deserializer.deserialize_seq(EntryCountVisitor)
1825    }
1826}
1827
1828struct EntryCountVisitor;
1829
1830impl<'de> Visitor<'de> for EntryCountVisitor {
1831    type Value = EntryCount;
1832
1833    fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
1834        formatter.write_str("a bounded Folderbase Version entry array")
1835    }
1836
1837    fn visit_seq<A>(self, mut sequence: A) -> Result<Self::Value, A::Error>
1838    where
1839        A: SeqAccess<'de>,
1840    {
1841        let mut count = 0_usize;
1842        while sequence.next_element::<IgnoredAny>()?.is_some() {
1843            count = count.saturating_add(1);
1844        }
1845        Ok(EntryCount(count))
1846    }
1847}
1848
1849fn deserialize_bounded_bindings<'de, D>(deserializer: D) -> Result<Vec<PathBinding>, D::Error>
1850where
1851    D: serde::Deserializer<'de>,
1852{
1853    deserialize_bounded_entries(deserializer, "bindings")
1854}
1855
1856fn deserialize_bounded_tombstones<'de, D>(deserializer: D) -> Result<Vec<Tombstone>, D::Error>
1857where
1858    D: serde::Deserializer<'de>,
1859{
1860    deserialize_bounded_entries(deserializer, "tombstones")
1861}
1862
1863fn deserialize_bounded_exclusions<'de, D>(deserializer: D) -> Result<Vec<Exclusion>, D::Error>
1864where
1865    D: serde::Deserializer<'de>,
1866{
1867    deserialize_bounded_entries(deserializer, "exclusions")
1868}
1869
1870fn deserialize_bounded_entries<'de, D, T>(
1871    deserializer: D,
1872    label: &'static str,
1873) -> Result<Vec<T>, D::Error>
1874where
1875    D: serde::Deserializer<'de>,
1876    T: Deserialize<'de>,
1877{
1878    deserializer.deserialize_seq(BoundedEntriesVisitor {
1879        label,
1880        marker: PhantomData,
1881    })
1882}
1883
1884struct BoundedEntriesVisitor<T> {
1885    label: &'static str,
1886    marker: PhantomData<T>,
1887}
1888
1889impl<'de, T> Visitor<'de> for BoundedEntriesVisitor<T>
1890where
1891    T: Deserialize<'de>,
1892{
1893    type Value = Vec<T>;
1894
1895    fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
1896        write!(formatter, "a bounded {} array", self.label)
1897    }
1898
1899    fn visit_seq<A>(self, mut sequence: A) -> Result<Self::Value, A::Error>
1900    where
1901        A: SeqAccess<'de>,
1902    {
1903        let capacity = sequence.size_hint().unwrap_or(0).min(MAX_VERSION_ENTRIES);
1904        let mut entries = Vec::with_capacity(capacity);
1905        while entries.len() < MAX_VERSION_ENTRIES {
1906            match sequence.next_element()? {
1907                Some(entry) => entries.push(entry),
1908                None => return Ok(entries),
1909            }
1910        }
1911        if sequence.next_element::<IgnoredAny>()?.is_some() {
1912            return Err(serde::de::Error::custom(format!(
1913                "{} exceeds the v1 entry limit",
1914                self.label
1915            )));
1916        }
1917        Ok(entries)
1918    }
1919}
1920
1921#[derive(Debug, Clone, Serialize, PartialEq, Eq)]
1922struct ExactU64(u64);
1923
1924impl<'de> Deserialize<'de> for ExactU64 {
1925    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
1926    where
1927        D: serde::Deserializer<'de>,
1928    {
1929        let number = serde_json::Number::deserialize(deserializer)?;
1930        parse_exact_unsigned(&number.to_string())
1931            .filter(|value| *value <= MAX_OBJECT_BYTES)
1932            .map(Self)
1933            .ok_or_else(|| {
1934                serde::de::Error::custom(format!(
1935                    "byte length must be an exact integer from 0 through {MAX_OBJECT_BYTES}"
1936                ))
1937            })
1938    }
1939}
1940
1941fn parse_exact_unsigned(encoded: &str) -> Option<u64> {
1942    let (negative, unsigned) = match encoded.strip_prefix('-') {
1943        Some(unsigned) => (true, unsigned),
1944        None => (false, encoded),
1945    };
1946    let (coefficient, exponent) = unsigned
1947        .split_once(['e', 'E'])
1948        .map_or((unsigned, "0"), |parts| parts);
1949    let exponent = exponent.parse::<i64>().ok()?;
1950    let (integer, fraction) = coefficient
1951        .split_once('.')
1952        .map_or((coefficient, ""), |parts| parts);
1953    let digits = format!("{integer}{fraction}");
1954    let significant = digits.trim_start_matches('0');
1955    if significant.is_empty() {
1956        return Some(0);
1957    }
1958    if negative {
1959        return None;
1960    }
1961    let scale = exponent.checked_sub(fraction.len() as i64)?;
1962    let mut normalized = significant.to_owned();
1963    if scale >= 0 {
1964        let zero_count = usize::try_from(scale).ok()?;
1965        if normalized.len().checked_add(zero_count)? > 20 {
1966            return None;
1967        }
1968        normalized.extend(std::iter::repeat_n('0', zero_count));
1969    } else {
1970        let removed = usize::try_from(scale.unsigned_abs()).ok()?;
1971        if removed > normalized.len() {
1972            return None;
1973        }
1974        let retained = normalized.len() - removed;
1975        if !normalized.as_bytes()[retained..]
1976            .iter()
1977            .all(|byte| *byte == b'0')
1978        {
1979            return None;
1980        }
1981        normalized.truncate(retained);
1982        if normalized.is_empty() {
1983            return Some(0);
1984        }
1985    }
1986    normalized.parse().ok()
1987}
1988
1989#[cfg(test)]
1990mod nested_boundary_index_tests {
1991    use super::*;
1992
1993    #[test]
1994    fn maximum_boundary_set_uses_at_most_path_depth_lookups_per_target() {
1995        let boundaries = (0..MAX_VERSION_ENTRIES / 2)
1996            .map(|index| format!("boundary-{index:04}"))
1997            .collect::<Vec<_>>();
1998        let index = NestedBoundaryIndex::from_paths(boundaries.iter().map(String::as_str));
1999        let resolved = (0..MAX_PATH_DEPTH)
2000            .map(|index| format!("ordinary-{index}"))
2001            .collect::<Vec<_>>()
2002            .join("/");
2003        let folded_resolved = portable_folded_key(&resolved);
2004
2005        assert_eq!(index.len(), MAX_VERSION_ENTRIES / 2);
2006        assert_eq!(index.probe_count(&folded_resolved, true), MAX_PATH_DEPTH);
2007        assert!(!index.contains_or_ancestor(&folded_resolved));
2008    }
2009}