1use 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
70pub(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#[allow(dead_code)]
247impl FolderbaseVersionParts {
248 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 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 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 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}