You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@opendal.apache.org by xu...@apache.org on 2026/09/02 05:07:59 UTC
(opendal-yinyang) branch xuanwo/yinyang-core created (now 29e3640)
This is an automated email from the ASF dual-hosted git repository.
Xuanwo pushed a change to branch xuanwo/yinyang-core
in repository https://gitbox.apache.org/repos/asf/opendal-yinyang.git
at 29e3640 feat(core): implement the YinYang Format state machine
This branch includes the following new commits:
new 29e3640 feat(core): implement the YinYang Format state machine
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
(opendal-yinyang) 01/01: feat(core): implement the YinYang Format state machine
Posted by xu...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
Xuanwo pushed a commit to branch xuanwo/yinyang-core
in repository https://gitbox.apache.org/repos/asf/opendal-yinyang.git
commit 29e364098a401939c7f61dae700fc7b77bbbb3b6
Author: Xuanwo <gi...@xuanwo.io>
AuthorDate: Wed Sep 2 13:07:45 2026 +0800
feat(core): implement the YinYang Format state machine
Co-authored-by: PsiACE <ps...@apache.org>
---
Cargo.lock | 218 ++++++++++-
Cargo.toml | 5 +-
Cargo.toml => crates/core/Cargo.toml | 46 +--
crates/core/src/error.rs | 80 ++++
crates/core/src/filesystem.rs | 686 +++++++++++++++++++++++++++++++++++
crates/core/src/identity.rs | 109 ++++++
crates/core/src/lib.rs | 37 ++
crates/core/src/publication.rs | 275 ++++++++++++++
crates/core/src/storage.rs | 87 +++++
crates/core/src/version.rs | 276 ++++++++++++++
crates/core/tests/core.rs | 591 ++++++++++++++++++++++++++++++
specs/README.md | 2 +
specs/yinyang-format.md | 118 ++++++
13 files changed, 2491 insertions(+), 39 deletions(-)
diff --git a/Cargo.lock b/Cargo.lock
index dfc63e9..666aee4 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -52,6 +52,18 @@ dependencies = [
"windows-sys",
]
+[[package]]
+name = "bumpalo"
+version = "3.20.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "72f5acc6cb2ba439de613abc23857ec3d78374d8ed5ac84e9d11336e87da8649"
+
+[[package]]
+name = "cfg-if"
+version = "1.0.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9330f8b2ff13f34540b44e946ef35111825727b38d33286ef986142615121801"
+
[[package]]
name = "clap"
version = "4.6.6"
@@ -83,7 +95,7 @@ dependencies = [
"heck",
"proc-macro2",
"quote",
- "syn",
+ "syn 3.0.3",
]
[[package]]
@@ -98,6 +110,41 @@ version = "1.0.5"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "1d07550c9036bf2ae0c684c4297d503f838287c83c53686d05370d0e139ae570"
+[[package]]
+name = "futures-core"
+version = "0.3.34"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "92d699e522242e69e3003b94ecc1f960f3a5e015aa7c5d7486e65ad01dd94f5e"
+
+[[package]]
+name = "futures-task"
+version = "0.3.34"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "cd417de3d1d015fc3bfd2b1ea46dfc7bab72ef86f1cc7cc9c78e728b34a6d1fd"
+
+[[package]]
+name = "futures-util"
+version = "0.3.34"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "0d50a92467f8ba5dd6e3ee5d4bd04d73ab2e4e1c44474a0674821dfce14b79bc"
+dependencies = [
+ "futures-core",
+ "futures-task",
+ "pin-project-lite",
+ "slab",
+]
+
+[[package]]
+name = "getrandom"
+version = "0.4.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "300e883d756b2e4ec94e02791f39b04b522276138852cfc41d9fb7e904106099"
+dependencies = [
+ "cfg-if",
+ "libc",
+ "r-efi",
+]
+
[[package]]
name = "heck"
version = "0.5.0"
@@ -110,18 +157,41 @@ version = "1.70.2"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "a6cb138bb79a146c1bd460005623e142ef0181e3d0219cb493e02f7d08a35695"
+[[package]]
+name = "js-sys"
+version = "0.3.104"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "0e0c1080212aad755ea003d18543e8768dd432c48819efd73a7bf1e39b7a5a3a"
+dependencies = [
+ "cfg-if",
+ "futures-util",
+ "wasm-bindgen",
+]
+
[[package]]
name = "libc"
version = "0.2.189"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "3eaf3ede3fee6db1a4c2ee091bf8a8b4dccdc6d17f656fb07896ee72867612f2"
+[[package]]
+name = "once_cell"
+version = "1.21.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9f7c3e4beb33f85d45ae3e3a1792185706c8e16d043238c593331cc7cd313b50"
+
[[package]]
name = "once_cell_polyfill"
version = "1.70.2"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "384b8ab6d37215f3c5301a95a4accb5d64aa607f1fcb26a11b5303878451b4fe"
+[[package]]
+name = "pin-project-lite"
+version = "0.2.17"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a89322df9ebe1c1578d689c92318e070967d1042b512afbe49518723f4e6d5cd"
+
[[package]]
name = "proc-macro2"
version = "1.0.107"
@@ -140,12 +210,41 @@ dependencies = [
"proc-macro2",
]
+[[package]]
+name = "r-efi"
+version = "6.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f8dcc9c7d52a811697d2151c701e0d08956f92b0e24136cf4cf27b57a6a0d9bf"
+
+[[package]]
+name = "rustversion"
+version = "1.0.23"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "cf54715a573b99ac80df0bc206da022bcd442c974952c7b9720069370852e21f"
+
+[[package]]
+name = "slab"
+version = "0.4.12"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "0c790de23124f9ab44544d7ac05d60440adc586479ce501c1d6d7da3cd8c9cf5"
+
[[package]]
name = "strsim"
version = "0.11.1"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "7da8b5736845d9f2fcb837ea5d9e2628564b3b043a70948a3f0b778838c5fb4f"
+[[package]]
+name = "syn"
+version = "2.0.119"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "872831b642d1a07999a962a351ed35b955ea2cfc8f3862091e2a240a84f17297"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "unicode-ident",
+]
+
[[package]]
name = "syn"
version = "3.0.3"
@@ -157,18 +256,125 @@ dependencies = [
"unicode-ident",
]
+[[package]]
+name = "tinyvec"
+version = "1.12.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "bb4ebadaa0af04fab11ae01eb5f9fdb5f9c5b875506e210e71c07873528baa7f"
+dependencies = [
+ "tinyvec_macros",
+]
+
+[[package]]
+name = "tinyvec_macros"
+version = "0.1.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1f3ccbac311fea05f86f61904b462b55fb3df8837a366dfc601a0161d0532f20"
+
+[[package]]
+name = "tokio"
+version = "1.53.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "202caea871b69668250d242070849eb495be178ed697a3e98aebce5bc81a0bed"
+dependencies = [
+ "pin-project-lite",
+ "tokio-macros",
+]
+
+[[package]]
+name = "tokio-macros"
+version = "2.7.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "78773a2a397f451582ce068015985c33193cf6dea8b74d2a639fe457b2f07b0e"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "syn 3.0.3",
+]
+
+[[package]]
+name = "unicode-casefold"
+version = "0.2.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b7f66b1c8f8caa2ab31dc6d3f35386f16efdab89668f93411e565ac368908e8f"
+
[[package]]
name = "unicode-ident"
version = "1.0.24"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "e6e4313cd5fcd3dad5cafa179702e2b244f760991f45397d14d4ebf38247da75"
+[[package]]
+name = "unicode-normalization"
+version = "0.1.25"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5fd4f6878c9cb28d874b009da9e8d183b5abc80117c40bbd187a1fde336be6e8"
+dependencies = [
+ "tinyvec",
+]
+
[[package]]
name = "utf8parse"
version = "0.2.2"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "06abde3611657adf66d383f00b093d7faecc7fa57071cce2578660c9f1010821"
+[[package]]
+name = "uuid"
+version = "1.26.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b5772d71c9be8a8a6ac2117d949c5b224c1b72241bb611d9a3012edcf8af7812"
+dependencies = [
+ "getrandom",
+ "js-sys",
+ "wasm-bindgen",
+]
+
+[[package]]
+name = "wasm-bindgen"
+version = "0.2.127"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1b70935747edd64d89de3efa29d73789b806c15798f8e7dca4d8ac356b50ce70"
+dependencies = [
+ "cfg-if",
+ "once_cell",
+ "rustversion",
+ "wasm-bindgen-macro",
+ "wasm-bindgen-shared",
+]
+
+[[package]]
+name = "wasm-bindgen-macro"
+version = "0.2.127"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "77775f8f3f7217702089053b94958f8f54061a3f663417df76e19cbdcca29bc1"
+dependencies = [
+ "quote",
+ "wasm-bindgen-macro-support",
+]
+
+[[package]]
+name = "wasm-bindgen-macro-support"
+version = "0.2.127"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e11d33f857dc2fb11b8bc75aee111aa9cbeb12cd9f25efd3d4c2a3dd4e235284"
+dependencies = [
+ "bumpalo",
+ "proc-macro2",
+ "quote",
+ "syn 2.0.119",
+ "wasm-bindgen-shared",
+]
+
+[[package]]
+name = "wasm-bindgen-shared"
+version = "0.2.127"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7ef64dbcc55df09c7e5a46182d181c2cfa3e925f3da937ea764728b4bbb9dcbf"
+dependencies = [
+ "unicode-ident",
+]
+
[[package]]
name = "which"
version = "8.0.5"
@@ -204,3 +410,13 @@ dependencies = [
[[package]]
name = "yinyang"
version = "0.0.24"
+
+[[package]]
+name = "yinyang-core"
+version = "0.0.24"
+dependencies = [
+ "tokio",
+ "unicode-casefold",
+ "unicode-normalization",
+ "uuid",
+]
diff --git a/Cargo.toml b/Cargo.toml
index be768e4..29e8b6d 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -31,7 +31,7 @@ repository.workspace = true
rust-version.workspace = true
[workspace]
-members = [".", "xtask"]
+members = [".", "crates/core", "xtask"]
resolver = "3"
[workspace.package]
@@ -43,6 +43,9 @@ rust-version = "1.91.0"
[workspace.dependencies]
clap = { version = "4.6.5", features = ["derive"] }
+unicode-casefold = "0.2"
+unicode-normalization = "0.1"
+uuid = { version = "1", features = ["v4"] }
which = { version = "8.0.5" }
[workspace.metadata.release]
diff --git a/Cargo.toml b/crates/core/Cargo.toml
similarity index 51%
copy from Cargo.toml
copy to crates/core/Cargo.toml
index be768e4..889e202 100644
--- a/Cargo.toml
+++ b/crates/core/Cargo.toml
@@ -16,50 +16,22 @@
# under the License.
[package]
-categories = ["filesystem"]
-description = "Apache OpenDAL™ YinYang"
-keywords = ["storage", "filesystem"]
-name = "yinyang"
-version = "0.0.24"
-
-authors = ["Apache OpenDAL <de...@opendal.apache.org>"]
+description = "YinYang Format semantics and publication state machine"
edition.workspace = true
-homepage.workspace = true
license.workspace = true
+name = "yinyang-core"
publish = false
repository.workspace = true
rust-version.workspace = true
+version = "0.0.24"
-[workspace]
-members = [".", "xtask"]
-resolver = "3"
-
-[workspace.package]
-edition = "2024"
-homepage = "https://opendal.apache.org/"
-license = "Apache-2.0"
-repository = "https://github.com/apache/opendal-yinyang"
-rust-version = "1.91.0"
-
-[workspace.dependencies]
-clap = { version = "4.6.5", features = ["derive"] }
-which = { version = "8.0.5" }
-
-[workspace.metadata.release]
-pre-release-commit-message = "chore: release v{{version}}"
-shared-version = true
-sign-tag = true
-tag-name = "v{{version}}"
-
-[workspace.lints.rust]
-unknown_lints = "deny"
-unsafe_code = "deny"
-unused_must_use = "deny"
+[dependencies]
+unicode-casefold.workspace = true
+unicode-normalization.workspace = true
+uuid.workspace = true
-[workspace.lints.clippy]
-dbg_macro = "deny"
-too_many_arguments = "allow"
-type_complexity = "allow"
+[dev-dependencies]
+tokio = { version = "1", features = ["macros", "rt-multi-thread"] }
[lints]
workspace = true
diff --git a/crates/core/src/error.rs b/crates/core/src/error.rs
new file mode 100644
index 0000000..3899c5a
--- /dev/null
+++ b/crates/core/src/error.rs
@@ -0,0 +1,80 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::fmt;
+
+/// Broad category of a YinYang Format failure.
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+pub enum ErrorKind {
+ Invalid,
+ Corrupt,
+ NotFound,
+ Conflict,
+ Storage,
+}
+
+/// Error returned by the YinYang Format core.
+#[derive(Debug)]
+pub struct Error {
+ kind: ErrorKind,
+ operation: &'static str,
+ message: String,
+}
+
+impl Error {
+ pub fn new(kind: ErrorKind, operation: &'static str, message: impl Into<String>) -> Self {
+ Self {
+ kind,
+ operation,
+ message: message.into(),
+ }
+ }
+
+ pub const fn kind(&self) -> ErrorKind {
+ self.kind
+ }
+
+ pub const fn operation(&self) -> &'static str {
+ self.operation
+ }
+
+ pub fn message(&self) -> &str {
+ &self.message
+ }
+
+ pub(crate) fn invalid(operation: &'static str, message: impl Into<String>) -> Self {
+ Self::new(ErrorKind::Invalid, operation, message)
+ }
+
+ pub(crate) fn corrupt(operation: &'static str, message: impl Into<String>) -> Self {
+ Self::new(ErrorKind::Corrupt, operation, message)
+ }
+
+ pub(crate) fn conflict(operation: &'static str, message: impl Into<String>) -> Self {
+ Self::new(ErrorKind::Conflict, operation, message)
+ }
+}
+
+impl fmt::Display for Error {
+ fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
+ write!(formatter, "{}: {}", self.operation, self.message)
+ }
+}
+
+impl std::error::Error for Error {}
+
+pub type Result<T, E = Error> = std::result::Result<T, E>;
diff --git a/crates/core/src/filesystem.rs b/crates/core/src/filesystem.rs
new file mode 100644
index 0000000..601a63a
--- /dev/null
+++ b/crates/core/src/filesystem.rs
@@ -0,0 +1,686 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::collections::{BTreeMap, BTreeSet};
+use std::fmt;
+
+use unicode_casefold::UnicodeCaseFold as _;
+use unicode_normalization::UnicodeNormalization as _;
+
+use crate::{Digest, Error, FileVersionId, Generation, NodeId, Result};
+
+const MAX_COMPONENT_BYTES: usize = 255;
+const MAX_PATH_BYTES: usize = 4096;
+
+/// Canonical relative filesystem path. The empty path is the root.
+#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
+pub struct Path(String);
+
+impl Path {
+ pub const fn root() -> Self {
+ Self(String::new())
+ }
+
+ pub fn new(value: impl Into<String>) -> Result<Self> {
+ let value = value.into();
+ validate_portable_path(&value)?;
+ Ok(Self(value))
+ }
+
+ pub fn as_str(&self) -> &str {
+ &self.0
+ }
+
+ pub fn is_root(&self) -> bool {
+ self.0.is_empty()
+ }
+
+ pub fn parent(&self) -> Option<Self> {
+ if self.is_root() {
+ return None;
+ }
+ Some(match self.0.rsplit_once('/') {
+ Some((parent, _)) => Self(parent.to_owned()),
+ None => Self::root(),
+ })
+ }
+
+ pub fn name(&self) -> Option<&str> {
+ (!self.is_root()).then(|| {
+ self.0
+ .rsplit('/')
+ .next()
+ .expect("a non-root path has a name")
+ })
+ }
+}
+
+impl fmt::Display for Path {
+ fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
+ formatter.write_str(&self.0)
+ }
+}
+
+/// Stable identity of one logical byte sequence.
+#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
+pub struct ContentId {
+ digest: Digest,
+ length: u64,
+}
+
+impl ContentId {
+ pub const fn new(digest: Digest, length: u64) -> Self {
+ Self { digest, length }
+ }
+
+ pub const fn digest(self) -> Digest {
+ self.digest
+ }
+
+ pub const fn length(self) -> u64 {
+ self.length
+ }
+}
+
+/// Opaque persistent reference to one verifiable immutable byte region.
+#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
+pub struct BlobRef {
+ reference: Vec<u8>,
+ content: ContentId,
+}
+
+impl BlobRef {
+ pub fn new(reference: impl Into<Vec<u8>>, content: ContentId) -> Result<Self> {
+ let reference = reference.into();
+ if reference.is_empty() {
+ return Err(Error::invalid(
+ "construct YinYang blob reference",
+ "blob reference is empty",
+ ));
+ }
+ Ok(Self { reference, content })
+ }
+
+ pub fn as_bytes(&self) -> &[u8] {
+ &self.reference
+ }
+
+ pub const fn content(&self) -> ContentId {
+ self.content
+ }
+}
+
+/// One half-open logical byte range in a file.
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+pub struct FileRange {
+ offset: u64,
+ length: u64,
+}
+
+impl FileRange {
+ pub fn new(offset: u64, length: u64) -> Result<Self> {
+ if length == 0 || offset.checked_add(length).is_none() {
+ return Err(Error::invalid(
+ "construct YinYang file range",
+ "file range is empty or overflows",
+ ));
+ }
+ Ok(Self { offset, length })
+ }
+
+ pub const fn offset(self) -> u64 {
+ self.offset
+ }
+
+ pub const fn length(self) -> u64 {
+ self.length
+ }
+
+ pub fn end(self) -> Result<u64> {
+ self.offset
+ .checked_add(self.length)
+ .ok_or_else(|| Error::corrupt("read YinYang file range", "file range end overflows"))
+ }
+}
+
+/// Independently verifiable and decodable source bytes.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct FileSource {
+ stored: BlobRef,
+ decoded: Vec<ContentId>,
+}
+
+impl FileSource {
+ pub fn new(stored: BlobRef, decoded: Vec<ContentId>) -> Self {
+ Self { stored, decoded }
+ }
+
+ pub const fn stored(&self) -> &BlobRef {
+ &self.stored
+ }
+
+ pub fn decoded(&self) -> &[ContentId] {
+ &self.decoded
+ }
+
+ pub fn content(&self) -> ContentId {
+ self.decoded
+ .last()
+ .copied()
+ .unwrap_or_else(|| self.stored.content())
+ }
+}
+
+/// Mapping from one logical file range into a source.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct FilePart {
+ range: FileRange,
+ source_offset: u64,
+ source: FileSource,
+}
+
+impl FilePart {
+ pub fn new(range: FileRange, source_offset: u64, source: FileSource) -> Result<Self> {
+ if source_offset
+ .checked_add(range.length())
+ .is_none_or(|end| end > source.content().length())
+ {
+ return Err(Error::invalid(
+ "construct YinYang file part",
+ "file part exceeds its source content",
+ ));
+ }
+ Ok(Self {
+ range,
+ source_offset,
+ source,
+ })
+ }
+
+ pub const fn range(&self) -> FileRange {
+ self.range
+ }
+
+ pub const fn source_offset(&self) -> u64 {
+ self.source_offset
+ }
+
+ pub const fn source(&self) -> &FileSource {
+ &self.source
+ }
+}
+
+/// One published logical file.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct File {
+ version: FileVersionId,
+ content: ContentId,
+ parts: Vec<FilePart>,
+}
+
+impl File {
+ pub fn new(version: FileVersionId, content: ContentId, parts: Vec<FilePart>) -> Result<Self> {
+ let file = Self {
+ version,
+ content,
+ parts,
+ };
+ file.validate(None)?;
+ Ok(file)
+ }
+
+ pub const fn version(&self) -> FileVersionId {
+ self.version
+ }
+
+ pub const fn content(&self) -> ContentId {
+ self.content
+ }
+
+ pub fn parts(&self) -> &[FilePart] {
+ &self.parts
+ }
+
+ fn validate(&self, decoding_count: Option<usize>) -> Result<()> {
+ if self.content.length() == 0 {
+ if self.parts.is_empty() {
+ return Ok(());
+ }
+ return Err(Error::invalid(
+ "validate YinYang file",
+ "empty file contains parts",
+ ));
+ }
+
+ let mut expected_offset = 0;
+ for part in &self.parts {
+ if part.range.offset() != expected_offset {
+ return Err(Error::invalid(
+ "validate YinYang file",
+ "file parts contain a gap or overlap",
+ ));
+ }
+ if decoding_count.is_some_and(|count| part.source.decoded.len() != count) {
+ return Err(Error::invalid(
+ "validate YinYang file",
+ "file source decoding count does not match the format",
+ ));
+ }
+ expected_offset = part.range.end()?;
+ }
+ if expected_offset != self.content.length() {
+ return Err(Error::invalid(
+ "validate YinYang file",
+ "file parts do not exactly cover the logical content",
+ ));
+ }
+ Ok(())
+ }
+}
+
+/// Filesystem attributes owned by one node generation.
+#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
+pub struct NodeAttrs {
+ pub executable: bool,
+}
+
+/// Directory membership state.
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+pub struct Dir {
+ entries_generation: Generation,
+}
+
+impl Dir {
+ pub const fn new(entries_generation: Generation) -> Self {
+ Self { entries_generation }
+ }
+
+ pub const fn entries_generation(self) -> Generation {
+ self.entries_generation
+ }
+}
+
+/// Node-specific filesystem state.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub enum NodeBody {
+ Dir(Dir),
+ File(File),
+}
+
+/// One stable filesystem node.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct Node {
+ id: NodeId,
+ generation: Generation,
+ attrs: NodeAttrs,
+ body: NodeBody,
+}
+
+impl Node {
+ pub const fn dir(
+ id: NodeId,
+ generation: Generation,
+ attrs: NodeAttrs,
+ entries_generation: Generation,
+ ) -> Self {
+ Self {
+ id,
+ generation,
+ attrs,
+ body: NodeBody::Dir(Dir::new(entries_generation)),
+ }
+ }
+
+ pub const fn file(id: NodeId, generation: Generation, attrs: NodeAttrs, file: File) -> Self {
+ Self {
+ id,
+ generation,
+ attrs,
+ body: NodeBody::File(file),
+ }
+ }
+
+ pub const fn id(&self) -> NodeId {
+ self.id
+ }
+
+ pub const fn generation(&self) -> Generation {
+ self.generation
+ }
+
+ pub const fn attrs(&self) -> NodeAttrs {
+ self.attrs
+ }
+
+ pub const fn body(&self) -> &NodeBody {
+ &self.body
+ }
+
+ pub const fn dir_body(&self) -> Option<Dir> {
+ match self.body {
+ NodeBody::Dir(dir) => Some(dir),
+ NodeBody::File(_) => None,
+ }
+ }
+
+ pub const fn file_body(&self) -> Option<&File> {
+ match &self.body {
+ NodeBody::Dir(_) => None,
+ NodeBody::File(file) => Some(file),
+ }
+ }
+}
+
+/// Materialized ordered filesystem tree.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct Tree {
+ entries: BTreeMap<Path, Node>,
+}
+
+impl Tree {
+ pub fn genesis(root: NodeId) -> Self {
+ Self {
+ entries: BTreeMap::from([(
+ Path::root(),
+ Node::dir(
+ root,
+ Generation::FIRST,
+ NodeAttrs::default(),
+ Generation::FIRST,
+ ),
+ )]),
+ }
+ }
+
+ pub fn from_entries(entries: impl IntoIterator<Item = (Path, Node)>) -> Result<Self> {
+ let mut tree = Self {
+ entries: BTreeMap::new(),
+ };
+ for (path, node) in entries {
+ if tree.entries.insert(path, node).is_some() {
+ return Err(Error::invalid(
+ "construct YinYang tree",
+ "tree contains a duplicate path",
+ ));
+ }
+ }
+ Ok(tree)
+ }
+
+ pub fn get(&self, path: &Path) -> Option<&Node> {
+ self.entries.get(path)
+ }
+
+ pub fn iter(&self) -> impl Iterator<Item = (&Path, &Node)> {
+ self.entries.iter()
+ }
+
+ pub fn insert(&mut self, path: Path, node: Node) -> Option<Node> {
+ self.entries.insert(path, node)
+ }
+
+ pub fn remove(&mut self, path: &Path) -> Option<Node> {
+ self.entries.remove(path)
+ }
+
+ pub fn len(&self) -> usize {
+ self.entries.len()
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.entries.is_empty()
+ }
+
+ pub(crate) fn validate(&self, root: NodeId, decoding_count: usize) -> Result<()> {
+ let root_node = self
+ .entries
+ .get(&Path::root())
+ .ok_or_else(|| Error::invalid("validate YinYang tree", "tree root is missing"))?;
+ if root_node.id != root || root_node.dir_body().is_none() {
+ return Err(Error::invalid(
+ "validate YinYang tree",
+ "tree root does not match the format",
+ ));
+ }
+
+ let mut identities = BTreeSet::new();
+ for (path, node) in &self.entries {
+ if node.generation == Generation::ZERO {
+ return Err(Error::invalid(
+ "validate YinYang tree",
+ "node generation is zero",
+ ));
+ }
+ if !identities.insert(node.id) {
+ return Err(Error::invalid(
+ "validate YinYang tree",
+ "node identity appears at more than one path",
+ ));
+ }
+ if let Some(dir) = node.dir_body()
+ && dir.entries_generation() == Generation::ZERO
+ {
+ return Err(Error::invalid(
+ "validate YinYang tree",
+ "directory entries generation is zero",
+ ));
+ }
+ if let Some(file) = node.file_body() {
+ file.validate(Some(decoding_count))?;
+ }
+ if let Some(parent) = path.parent()
+ && self.entries.get(&parent).and_then(Node::dir_body).is_none()
+ {
+ return Err(Error::invalid(
+ "validate YinYang tree",
+ "tree entry parent is missing or is not a directory",
+ ));
+ }
+ }
+ directory_membership(self)?;
+ Ok(())
+ }
+
+ pub(crate) fn validate_successor(
+ &self,
+ successor: &Self,
+ root: NodeId,
+ decoding_count: usize,
+ ) -> Result<()> {
+ self.validate(root, decoding_count)?;
+ successor.validate(root, decoding_count)?;
+
+ let previous_by_id = nodes_by_id(self);
+ let successor_by_id = nodes_by_id(successor);
+ for (id, (_, next)) in &successor_by_id {
+ let Some((_, previous)) = previous_by_id.get(id) else {
+ if next.generation != Generation::FIRST
+ || next
+ .dir_body()
+ .is_some_and(|dir| dir.entries_generation() != Generation::FIRST)
+ {
+ return Err(Error::invalid(
+ "validate YinYang tree successor",
+ "new node does not start at the first generation",
+ ));
+ }
+ continue;
+ };
+
+ if matches!(previous.body, NodeBody::Dir(_)) != matches!(next.body, NodeBody::Dir(_)) {
+ return Err(Error::invalid(
+ "validate YinYang tree successor",
+ "node kind changed without a new identity",
+ ));
+ }
+ if let (Some(previous_file), Some(next_file)) = (previous.file_body(), next.file_body())
+ && previous_file.version == next_file.version
+ && (previous_file.content != next_file.content
+ || previous_file.parts != next_file.parts)
+ {
+ return Err(Error::invalid(
+ "validate YinYang tree successor",
+ "file content changed without a new file version",
+ ));
+ }
+
+ let payload_changed = previous.attrs != next.attrs
+ || match (&previous.body, &next.body) {
+ (NodeBody::Dir(_), NodeBody::Dir(_)) => false,
+ (NodeBody::File(previous), NodeBody::File(next)) => previous != next,
+ _ => unreachable!("node kind was checked above"),
+ };
+ let expected = if payload_changed {
+ previous.generation.next()?
+ } else {
+ previous.generation
+ };
+ if next.generation != expected {
+ return Err(Error::invalid(
+ "validate YinYang tree successor",
+ "node generation does not match its content change",
+ ));
+ }
+ }
+
+ let previous_membership = directory_membership(self)?;
+ let successor_membership = directory_membership(successor)?;
+ for (id, (_, next)) in successor_by_id {
+ let Some(next_dir) = next.dir_body() else {
+ continue;
+ };
+ let Some((_, previous)) = previous_by_id.get(&id) else {
+ continue;
+ };
+ let previous_dir = previous
+ .dir_body()
+ .expect("a stable directory identity remains a directory");
+ let changed = previous_membership.get(&id) != successor_membership.get(&id);
+ let expected = if changed {
+ previous_dir.entries_generation().next()?
+ } else {
+ previous_dir.entries_generation()
+ };
+ if next_dir.entries_generation() != expected {
+ return Err(Error::invalid(
+ "validate YinYang tree successor",
+ "directory generation does not match its membership change",
+ ));
+ }
+ }
+ Ok(())
+ }
+}
+
+fn nodes_by_id(tree: &Tree) -> BTreeMap<NodeId, (&Path, &Node)> {
+ tree.entries
+ .iter()
+ .map(|(path, node)| (node.id, (path, node)))
+ .collect()
+}
+
+fn directory_membership(tree: &Tree) -> Result<BTreeMap<NodeId, BTreeMap<String, NodeId>>> {
+ let mut membership = tree
+ .entries
+ .values()
+ .filter_map(|node| node.dir_body().map(|_| (node.id, BTreeMap::new())))
+ .collect::<BTreeMap<_, _>>();
+ let mut folded_names = BTreeMap::<NodeId, BTreeSet<String>>::new();
+ for (path, node) in &tree.entries {
+ let Some(parent) = path.parent() else {
+ continue;
+ };
+ let parent_id = tree
+ .entries
+ .get(&parent)
+ .and_then(|node| node.dir_body().map(|_| node.id))
+ .ok_or_else(|| {
+ Error::invalid(
+ "validate YinYang tree",
+ "tree entry parent is missing or is not a directory",
+ )
+ })?;
+ let name = path.name().expect("a non-root path has a name");
+ if !folded_names
+ .entry(parent_id)
+ .or_default()
+ .insert(name.case_fold().nfc().collect())
+ {
+ return Err(Error::invalid(
+ "validate YinYang tree",
+ "directory contains a case-folding name collision",
+ ));
+ }
+ membership
+ .get_mut(&parent_id)
+ .expect("every directory has a membership set")
+ .insert(name.to_owned(), node.id);
+ }
+ Ok(membership)
+}
+
+fn validate_portable_path(path: &str) -> Result<()> {
+ if path.is_empty() {
+ return Ok(());
+ }
+ if path.len() > MAX_PATH_BYTES
+ || path.starts_with('/')
+ || path.ends_with('/')
+ || path.contains("//")
+ {
+ return Err(Error::invalid(
+ "construct YinYang path",
+ "path is not canonical and portable",
+ ));
+ }
+ for component in path.split('/') {
+ validate_portable_component(component)?;
+ }
+ Ok(())
+}
+
+fn validate_portable_component(component: &str) -> Result<()> {
+ if component.len() > MAX_COMPONENT_BYTES
+ || component == "."
+ || component == ".."
+ || component.ends_with([' ', '.'])
+ || component.chars().any(|character| {
+ character.is_control()
+ || matches!(character, '<' | '>' | ':' | '"' | '\\' | '|' | '?' | '*')
+ })
+ || !component.nfc().eq(component.chars())
+ {
+ return Err(Error::invalid(
+ "construct YinYang path",
+ "path component is not canonical and portable",
+ ));
+ }
+ let folded = component.case_fold().nfc().collect::<String>();
+ let stem = folded.split('.').next().unwrap_or_default();
+ if matches!(stem, "con" | "prn" | "aux" | "nul")
+ || stem.len() == 4
+ && (stem.starts_with("com") || stem.starts_with("lpt"))
+ && matches!(stem.as_bytes()[3], b'1'..=b'9')
+ || matches!(stem, "com¹" | "com²" | "com³" | "lpt¹" | "lpt²" | "lpt³")
+ {
+ return Err(Error::invalid(
+ "construct YinYang path",
+ "path component is reserved",
+ ));
+ }
+ Ok(())
+}
diff --git a/crates/core/src/identity.rs b/crates/core/src/identity.rs
new file mode 100644
index 0000000..49aec43
--- /dev/null
+++ b/crates/core/src/identity.rs
@@ -0,0 +1,109 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::fmt;
+
+use crate::{Error, Result};
+
+macro_rules! identity {
+ ($name:ident, $bytes:literal) => {
+ #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
+ pub struct $name([u8; $bytes]);
+
+ impl $name {
+ pub const fn from_bytes(bytes: [u8; $bytes]) -> Self {
+ Self(bytes)
+ }
+
+ pub const fn as_bytes(&self) -> &[u8; $bytes] {
+ &self.0
+ }
+ }
+ };
+}
+
+macro_rules! generated_identity {
+ ($($name:ident),+ $(,)?) => {
+ $(
+ impl $name {
+ pub fn generate() -> Self {
+ Self::from_bytes(*uuid::Uuid::new_v4().as_bytes())
+ }
+ }
+ )+
+ };
+}
+
+identity!(FsId, 16);
+identity!(NodeId, 16);
+identity!(FileVersionId, 16);
+identity!(CommitId, 16);
+identity!(ExtensionId, 16);
+identity!(Digest, 32);
+
+generated_identity!(FsId, NodeId, FileVersionId, CommitId);
+
+macro_rules! display_identity {
+ ($($name:ident),+ $(,)?) => {
+ $(
+ impl fmt::Display for $name {
+ fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
+ for byte in self.as_bytes() {
+ write!(formatter, "{byte:02x}")?;
+ }
+ Ok(())
+ }
+ }
+ )+
+ };
+}
+
+display_identity!(FsId, NodeId, FileVersionId, CommitId, ExtensionId, Digest);
+
+macro_rules! counter {
+ ($name:ident) => {
+ #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
+ pub struct $name(u64);
+
+ impl $name {
+ pub const ZERO: Self = Self(0);
+
+ pub const fn from_value(value: u64) -> Self {
+ Self(value)
+ }
+
+ pub const fn value(self) -> u64 {
+ self.0
+ }
+
+ pub fn next(self) -> Result<Self> {
+ self.0
+ .checked_add(1)
+ .map(Self)
+ .ok_or_else(|| Error::corrupt("advance YinYang counter", "counter overflows"))
+ }
+ }
+ };
+}
+
+counter!(Generation);
+counter!(VersionNumber);
+counter!(GcEpoch);
+
+impl Generation {
+ pub const FIRST: Self = Self(1);
+}
diff --git a/crates/core/src/lib.rs b/crates/core/src/lib.rs
new file mode 100644
index 0000000..7cb4df8
--- /dev/null
+++ b/crates/core/src/lib.rs
@@ -0,0 +1,37 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! YinYang Format semantics and publication state machine.
+
+mod error;
+mod filesystem;
+mod identity;
+mod publication;
+mod storage;
+mod version;
+
+pub use error::{Error, ErrorKind, Result};
+pub use filesystem::{
+ BlobRef, ContentId, Dir, File, FilePart, FileRange, FileSource, Node, NodeAttrs, NodeBody,
+ Path, Tree,
+};
+pub use identity::{
+ CommitId, Digest, ExtensionId, FileVersionId, FsId, GcEpoch, Generation, NodeId, VersionNumber,
+};
+pub use publication::{CommitOutcome, CreateOptions, Fs, Observation};
+pub use storage::{FormatStorage, HeadObservation};
+pub use version::{Commit, Extension, FsFormat, FsHead, FsVersion, FsVersionRef};
diff --git a/crates/core/src/publication.rs b/crates/core/src/publication.rs
new file mode 100644
index 0000000..7199f2c
--- /dev/null
+++ b/crates/core/src/publication.rs
@@ -0,0 +1,275 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::{
+ Commit, CommitId, Error, ErrorKind, Extension, FormatStorage, FsFormat, FsHead, FsId,
+ FsVersion, FsVersionRef, GcEpoch, HeadObservation, NodeId, Result, Tree, VersionNumber,
+};
+
+/// Persisted choices made when a YinYang filesystem is created.
+#[derive(Clone, Debug, Default, Eq, PartialEq)]
+pub struct CreateOptions {
+ decodings: Vec<Extension>,
+ head_extension: Option<Extension>,
+}
+
+impl CreateOptions {
+ pub const fn new() -> Self {
+ Self {
+ decodings: Vec::new(),
+ head_extension: None,
+ }
+ }
+
+ pub fn with_decodings(mut self, decodings: Vec<Extension>) -> Self {
+ self.decodings = decodings;
+ self
+ }
+
+ pub fn with_head_extension(mut self, extension: Extension) -> Self {
+ self.head_extension = Some(extension);
+ self
+ }
+}
+
+/// Current immutable version together with the condition needed for publication.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct Observation {
+ head: HeadObservation,
+ version: FsVersion,
+}
+
+impl Observation {
+ pub const fn head(&self) -> &FsHead {
+ self.head.head()
+ }
+
+ pub const fn version(&self) -> &FsVersion {
+ &self.version
+ }
+
+ pub const fn tree(&self) -> &Tree {
+ self.version.tree()
+ }
+}
+
+/// Result of an idempotent publication attempt.
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+pub enum CommitOutcome {
+ Committed { version: VersionNumber },
+ Conflict { current: VersionNumber },
+}
+
+/// Open YinYang filesystem over one storage implementation.
+#[derive(Debug)]
+pub struct Fs<S> {
+ format: FsFormat,
+ storage: S,
+}
+
+impl<S: FormatStorage> Fs<S> {
+ /// Create a filesystem, or reopen the existing filesystem with the same configuration.
+ pub async fn create(storage: S, options: CreateOptions) -> Result<Self> {
+ let requested = FsFormat::new(
+ FsId::generate(),
+ NodeId::generate(),
+ options.decodings,
+ options.head_extension,
+ );
+ let format = if storage.create_format(&requested).await? {
+ requested
+ } else {
+ let existing = storage.read_format().await?.ok_or_else(|| {
+ Error::new(
+ ErrorKind::Storage,
+ "create YinYang filesystem",
+ "format disappeared after create conflict",
+ )
+ })?;
+ if !existing.has_same_configuration(&requested) {
+ return Err(Error::conflict(
+ "create YinYang filesystem",
+ "storage contains a different format configuration",
+ ));
+ }
+ existing
+ };
+
+ let filesystem = Self { format, storage };
+ filesystem.initialize().await?;
+ Ok(filesystem)
+ }
+
+ /// Open and validate an existing filesystem.
+ pub async fn open(storage: S) -> Result<Self> {
+ let format = storage.read_format().await?.ok_or_else(|| {
+ Error::new(
+ ErrorKind::NotFound,
+ "open YinYang filesystem",
+ "format is missing",
+ )
+ })?;
+ let filesystem = Self { format, storage };
+ filesystem.observe().await?;
+ Ok(filesystem)
+ }
+
+ pub const fn format(&self) -> &FsFormat {
+ &self.format
+ }
+
+ pub const fn storage(&self) -> &S {
+ &self.storage
+ }
+
+ /// Observe the head and materialize its immutable version.
+ pub async fn observe(&self) -> Result<Observation> {
+ let head = self.storage.observe_head().await?.ok_or_else(|| {
+ Error::new(
+ ErrorKind::NotFound,
+ "observe YinYang filesystem",
+ "head is missing",
+ )
+ })?;
+ self.read_observation(head).await
+ }
+
+ /// Publish one validated successor tree using a caller-assigned idempotency key.
+ pub async fn commit(
+ &self,
+ observed: &Observation,
+ id: CommitId,
+ tree: Tree,
+ ) -> Result<CommitOutcome> {
+ self.validate_observation(observed)?;
+ if let Some(committed) = observed
+ .version
+ .commits()
+ .iter()
+ .find(|commit| commit.id() == id)
+ {
+ return Ok(CommitOutcome::Committed {
+ version: committed.version(),
+ });
+ }
+
+ observed.version.tree().validate_successor(
+ &tree,
+ self.format.root(),
+ self.format.decodings().len(),
+ )?;
+ let number = observed.version.number().next()?;
+ let mut commits = observed.version.commits().to_vec();
+ commits.push(Commit::new(id, number));
+ let version = FsVersion::new(&self.format, number, tree, commits)?;
+ let blob = self.storage.write_version(&version).await?;
+ let reference = FsVersionRef::new(number, blob);
+ let next = FsHead::new(
+ reference,
+ observed.head().gc_epoch(),
+ observed.head().min_retained(),
+ )?;
+
+ match self.storage.replace_head(&observed.head, &next).await {
+ Ok(true) => Ok(CommitOutcome::Committed { version: number }),
+ Ok(false) => self.resolve_conflict(id).await,
+ Err(error) => match self.find_commit(id).await {
+ Ok(Some(version)) => Ok(CommitOutcome::Committed { version }),
+ Ok(None) | Err(_) => Err(error),
+ },
+ }
+ }
+
+ async fn initialize(&self) -> Result<()> {
+ if let Some(head) = self.storage.observe_head().await? {
+ self.read_observation(head).await?;
+ return Ok(());
+ }
+
+ let genesis = FsVersion::new(
+ &self.format,
+ VersionNumber::ZERO,
+ Tree::genesis(self.format.root()),
+ Vec::new(),
+ )?;
+ let blob = self.storage.write_version(&genesis).await?;
+ let head = FsHead::new(
+ FsVersionRef::new(VersionNumber::ZERO, blob),
+ GcEpoch::ZERO,
+ VersionNumber::ZERO,
+ )?;
+ self.storage.create_head(&head).await?;
+ self.observe().await?;
+ Ok(())
+ }
+
+ async fn read_observation(&self, head: HeadObservation) -> Result<Observation> {
+ head.head().validate()?;
+ let version = self
+ .storage
+ .read_version(head.head().current().blob())
+ .await?;
+ version.validate(&self.format)?;
+ if version.number() != head.head().current().number() {
+ return Err(Error::corrupt(
+ "observe YinYang filesystem",
+ "version number does not match the head reference",
+ ));
+ }
+ Ok(Observation { head, version })
+ }
+
+ fn validate_observation(&self, observed: &Observation) -> Result<()> {
+ observed.head().validate()?;
+ observed.version.validate(&self.format)?;
+ if observed.version.number() != observed.head().current().number() {
+ return Err(Error::invalid(
+ "commit YinYang filesystem",
+ "observation does not match its head",
+ ));
+ }
+ Ok(())
+ }
+
+ async fn resolve_conflict(&self, id: CommitId) -> Result<CommitOutcome> {
+ let current = self.observe().await?;
+ if let Some(commit) = current
+ .version
+ .commits()
+ .iter()
+ .find(|commit| commit.id() == id)
+ {
+ return Ok(CommitOutcome::Committed {
+ version: commit.version(),
+ });
+ }
+ Ok(CommitOutcome::Conflict {
+ current: current.version.number(),
+ })
+ }
+
+ async fn find_commit(&self, id: CommitId) -> Result<Option<VersionNumber>> {
+ Ok(self
+ .observe()
+ .await?
+ .version
+ .commits()
+ .iter()
+ .find(|commit| commit.id() == id)
+ .map(|commit| commit.version()))
+ }
+}
diff --git a/crates/core/src/storage.rs b/crates/core/src/storage.rs
new file mode 100644
index 0000000..ff1d0ee
--- /dev/null
+++ b/crates/core/src/storage.rs
@@ -0,0 +1,87 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::future::Future;
+
+use crate::{BlobRef, FsFormat, FsHead, FsVersion, Result};
+
+/// One head value and the opaque condition required to replace that observation.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct HeadObservation {
+ head: FsHead,
+ condition: Vec<u8>,
+}
+
+impl HeadObservation {
+ pub fn new(head: FsHead, condition: Vec<u8>) -> Result<Self> {
+ if condition.is_empty() {
+ return Err(crate::Error::invalid(
+ "construct YinYang head observation",
+ "head condition is empty",
+ ));
+ }
+ Ok(Self { head, condition })
+ }
+
+ pub const fn head(&self) -> &FsHead {
+ &self.head
+ }
+
+ pub fn condition(&self) -> &[u8] {
+ &self.condition
+ }
+}
+
+/// Persistent capabilities required by the YinYang Format state machine.
+pub trait FormatStorage: Send + Sync {
+ /// Create the bootstrap record when it does not exist.
+ fn create_format<'a>(
+ &'a self,
+ format: &'a FsFormat,
+ ) -> impl Future<Output = Result<bool>> + Send + 'a;
+
+ /// Read the bootstrap record.
+ fn read_format(&self) -> impl Future<Output = Result<Option<FsFormat>>> + Send + '_;
+
+ /// Persist one immutable filesystem version and return its verifiable reference.
+ fn write_version<'a>(
+ &'a self,
+ version: &'a FsVersion,
+ ) -> impl Future<Output = Result<BlobRef>> + Send + 'a;
+
+ /// Read and verify one immutable filesystem version.
+ fn read_version<'a>(
+ &'a self,
+ reference: &'a BlobRef,
+ ) -> impl Future<Output = Result<FsVersion>> + Send + 'a;
+
+ /// Create the mutable head when it does not exist.
+ fn create_head<'a>(
+ &'a self,
+ head: &'a FsHead,
+ ) -> impl Future<Output = Result<bool>> + Send + 'a;
+
+ /// Read the head and a condition bound to the same observed value.
+ fn observe_head(&self) -> impl Future<Output = Result<Option<HeadObservation>>> + Send + '_;
+
+ /// Replace the complete head when `observed` is still current.
+ fn replace_head<'a>(
+ &'a self,
+ observed: &'a HeadObservation,
+ next: &'a FsHead,
+ ) -> impl Future<Output = Result<bool>> + Send + 'a;
+}
diff --git a/crates/core/src/version.rs b/crates/core/src/version.rs
new file mode 100644
index 0000000..84a8a96
--- /dev/null
+++ b/crates/core/src/version.rs
@@ -0,0 +1,276 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::{
+ BlobRef, CommitId, Error, ExtensionId, FsId, GcEpoch, NodeId, Result, Tree, VersionNumber,
+};
+
+/// Persisted extension identity and configuration.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct Extension {
+ id: ExtensionId,
+ configuration: Vec<u8>,
+}
+
+impl Extension {
+ pub fn new(id: ExtensionId, configuration: Vec<u8>) -> Self {
+ Self { id, configuration }
+ }
+
+ pub const fn id(&self) -> ExtensionId {
+ self.id
+ }
+
+ pub fn configuration(&self) -> &[u8] {
+ &self.configuration
+ }
+}
+
+/// Bootstrap record required before reading a YinYang filesystem.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct FsFormat {
+ fs: FsId,
+ root: NodeId,
+ decodings: Vec<Extension>,
+ head_extension: Option<Extension>,
+}
+
+impl FsFormat {
+ pub fn new(
+ fs: FsId,
+ root: NodeId,
+ decodings: Vec<Extension>,
+ head_extension: Option<Extension>,
+ ) -> Self {
+ Self {
+ fs,
+ root,
+ decodings,
+ head_extension,
+ }
+ }
+
+ pub const fn fs(&self) -> FsId {
+ self.fs
+ }
+
+ pub const fn root(&self) -> NodeId {
+ self.root
+ }
+
+ pub fn decodings(&self) -> &[Extension] {
+ &self.decodings
+ }
+
+ pub fn head_extension(&self) -> Option<&Extension> {
+ self.head_extension.as_ref()
+ }
+
+ pub(crate) fn has_same_configuration(&self, other: &Self) -> bool {
+ self.decodings == other.decodings && self.head_extension == other.head_extension
+ }
+}
+
+/// Reference to one immutable filesystem version.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct FsVersionRef {
+ number: VersionNumber,
+ blob: BlobRef,
+}
+
+impl FsVersionRef {
+ pub const fn new(number: VersionNumber, blob: BlobRef) -> Self {
+ Self { number, blob }
+ }
+
+ pub const fn number(&self) -> VersionNumber {
+ self.number
+ }
+
+ pub const fn blob(&self) -> &BlobRef {
+ &self.blob
+ }
+}
+
+/// Durable fact binding an idempotency key to a published version.
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+pub struct Commit {
+ id: CommitId,
+ version: VersionNumber,
+}
+
+impl Commit {
+ pub const fn new(id: CommitId, version: VersionNumber) -> Self {
+ Self { id, version }
+ }
+
+ pub const fn id(self) -> CommitId {
+ self.id
+ }
+
+ pub const fn version(self) -> VersionNumber {
+ self.version
+ }
+}
+
+/// One immutable materialized filesystem version.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct FsVersion {
+ fs: FsId,
+ number: VersionNumber,
+ tree: Tree,
+ commits: Vec<Commit>,
+}
+
+impl FsVersion {
+ pub fn new(
+ format: &FsFormat,
+ number: VersionNumber,
+ tree: Tree,
+ commits: Vec<Commit>,
+ ) -> Result<Self> {
+ let version = Self {
+ fs: format.fs,
+ number,
+ tree,
+ commits,
+ };
+ version.validate(format)?;
+ Ok(version)
+ }
+
+ pub const fn fs(&self) -> FsId {
+ self.fs
+ }
+
+ pub const fn number(&self) -> VersionNumber {
+ self.number
+ }
+
+ pub const fn tree(&self) -> &Tree {
+ &self.tree
+ }
+
+ pub fn commits(&self) -> &[Commit] {
+ &self.commits
+ }
+
+ pub(crate) fn validate(&self, format: &FsFormat) -> Result<()> {
+ if self.fs != format.fs {
+ return Err(Error::corrupt(
+ "read YinYang version",
+ "filesystem identity does not match the format",
+ ));
+ }
+ self.tree.validate(format.root, format.decodings.len())?;
+ validate_commits(self.number, &self.commits)
+ }
+}
+
+/// Mutable publication cell for one YinYang filesystem.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct FsHead {
+ current: FsVersionRef,
+ gc_epoch: GcEpoch,
+ min_retained: VersionNumber,
+}
+
+impl FsHead {
+ pub fn new(
+ current: FsVersionRef,
+ gc_epoch: GcEpoch,
+ min_retained: VersionNumber,
+ ) -> Result<Self> {
+ if min_retained > current.number {
+ return Err(Error::invalid(
+ "construct YinYang head",
+ "minimum retained version exceeds the current version",
+ ));
+ }
+ Ok(Self {
+ current,
+ gc_epoch,
+ min_retained,
+ })
+ }
+
+ pub const fn current(&self) -> &FsVersionRef {
+ &self.current
+ }
+
+ pub const fn gc_epoch(&self) -> GcEpoch {
+ self.gc_epoch
+ }
+
+ pub const fn min_retained(&self) -> VersionNumber {
+ self.min_retained
+ }
+
+ pub(crate) fn validate(&self) -> Result<()> {
+ if self.min_retained > self.current.number {
+ return Err(Error::corrupt(
+ "read YinYang head",
+ "minimum retained version exceeds the current version",
+ ));
+ }
+ Ok(())
+ }
+}
+
+fn validate_commits(number: VersionNumber, commits: &[Commit]) -> Result<()> {
+ use std::collections::BTreeSet;
+
+ if number == VersionNumber::ZERO {
+ if commits.is_empty() {
+ return Ok(());
+ }
+ return Err(Error::corrupt(
+ "read YinYang version",
+ "genesis version contains commits",
+ ));
+ }
+ let Some(first) = commits.first().copied() else {
+ return Err(Error::corrupt(
+ "read YinYang version",
+ "non-genesis version has no retained commits",
+ ));
+ };
+ if first.version == VersionNumber::ZERO
+ || commits.last().map(|commit| commit.version) != Some(number)
+ {
+ return Err(Error::corrupt(
+ "read YinYang version",
+ "commit range does not end at the filesystem version",
+ ));
+ }
+
+ let mut identities = BTreeSet::new();
+ let mut previous = None;
+ for commit in commits {
+ if !identities.insert(commit.id)
+ || previous
+ .is_some_and(|previous: VersionNumber| previous.next().ok() != Some(commit.version))
+ {
+ return Err(Error::corrupt(
+ "read YinYang version",
+ "commits are not unique and contiguous",
+ ));
+ }
+ previous = Some(commit.version);
+ }
+ Ok(())
+}
diff --git a/crates/core/tests/core.rs b/crates/core/tests/core.rs
new file mode 100644
index 0000000..9b40750
--- /dev/null
+++ b/crates/core/tests/core.rs
@@ -0,0 +1,591 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::collections::BTreeMap;
+use std::sync::{Arc, Mutex};
+
+use yinyang_core::{
+ BlobRef, CommitId, CommitOutcome, ContentId, CreateOptions, Digest, Error, ErrorKind,
+ Extension, ExtensionId, File, FilePart, FileRange, FileSource, FormatStorage, Fs, FsFormat,
+ FsHead, FsVersion, Generation, HeadObservation, Node, NodeAttrs, NodeId, Path, Result, Tree,
+ VersionNumber,
+};
+
+#[derive(Clone, Debug, Default)]
+struct MemoryStorage {
+ state: Arc<Mutex<MemoryState>>,
+}
+
+#[derive(Debug, Default)]
+struct MemoryState {
+ format: Option<FsFormat>,
+ head: Option<FsHead>,
+ head_revision: u64,
+ versions: BTreeMap<BlobRef, FsVersion>,
+ next_blob: u64,
+ fail_after_replace: bool,
+}
+
+impl MemoryStorage {
+ fn fail_next_replace_after_success(&self) {
+ self.state.lock().unwrap().fail_after_replace = true;
+ }
+
+ fn remove_current_version(&self) {
+ let mut state = self.state.lock().unwrap();
+ let reference = state
+ .head
+ .as_ref()
+ .expect("the test filesystem has a head")
+ .current()
+ .blob()
+ .clone();
+ state.versions.remove(&reference);
+ }
+}
+
+impl FormatStorage for MemoryStorage {
+ async fn create_format(&self, format: &FsFormat) -> Result<bool> {
+ let mut state = self.state.lock().unwrap();
+ if state.format.is_some() {
+ return Ok(false);
+ }
+ state.format = Some(format.clone());
+ Ok(true)
+ }
+
+ async fn read_format(&self) -> Result<Option<FsFormat>> {
+ Ok(self.state.lock().unwrap().format.clone())
+ }
+
+ async fn write_version(&self, version: &FsVersion) -> Result<BlobRef> {
+ let mut state = self.state.lock().unwrap();
+ state.next_blob += 1;
+ let identity = state.next_blob;
+ let mut digest = [0; 32];
+ digest[..8].copy_from_slice(&identity.to_le_bytes());
+ let reference = BlobRef::new(
+ identity.to_le_bytes(),
+ ContentId::new(Digest::from_bytes(digest), 1),
+ )?;
+ state.versions.insert(reference.clone(), version.clone());
+ Ok(reference)
+ }
+
+ async fn read_version(&self, reference: &BlobRef) -> Result<FsVersion> {
+ self.state
+ .lock()
+ .unwrap()
+ .versions
+ .get(reference)
+ .cloned()
+ .ok_or_else(|| {
+ Error::new(
+ ErrorKind::Corrupt,
+ "read in-memory YinYang version",
+ "referenced version is missing",
+ )
+ })
+ }
+
+ async fn create_head(&self, head: &FsHead) -> Result<bool> {
+ let mut state = self.state.lock().unwrap();
+ if state.head.is_some() {
+ return Ok(false);
+ }
+ state.head = Some(head.clone());
+ state.head_revision = 1;
+ Ok(true)
+ }
+
+ async fn observe_head(&self) -> Result<Option<HeadObservation>> {
+ let state = self.state.lock().unwrap();
+ state
+ .head
+ .clone()
+ .map(|head| HeadObservation::new(head, state.head_revision.to_le_bytes().to_vec()))
+ .transpose()
+ }
+
+ async fn replace_head(&self, observed: &HeadObservation, next: &FsHead) -> Result<bool> {
+ let mut state = self.state.lock().unwrap();
+ if state.head.is_none() || observed.condition() != state.head_revision.to_le_bytes() {
+ return Ok(false);
+ }
+ state.head = Some(next.clone());
+ state.head_revision += 1;
+ if state.fail_after_replace {
+ state.fail_after_replace = false;
+ return Err(Error::new(
+ ErrorKind::Storage,
+ "replace in-memory YinYang head",
+ "publication response was lost",
+ ));
+ }
+ Ok(true)
+ }
+}
+
+fn add_directory(tree: &Tree, name: &str, id: NodeId) -> Tree {
+ let mut successor = tree.clone();
+ advance_root_membership(&mut successor);
+ successor.insert(
+ Path::new(name).unwrap(),
+ Node::dir(
+ id,
+ Generation::FIRST,
+ NodeAttrs::default(),
+ Generation::FIRST,
+ ),
+ );
+ successor
+}
+
+fn advance_root_membership(tree: &mut Tree) {
+ let root_path = Path::root();
+ let root = tree
+ .get(&root_path)
+ .expect("a valid tree has a root")
+ .clone();
+ let root_dir = root.dir_body().expect("the root is a directory");
+ tree.insert(
+ root_path,
+ Node::dir(
+ root.id(),
+ root.generation(),
+ root.attrs(),
+ root_dir.entries_generation().next().unwrap(),
+ ),
+ );
+}
+
+#[tokio::test]
+async fn creates_and_reopens_one_filesystem() {
+ let storage = MemoryStorage::default();
+ let (left, right) = tokio::join!(
+ Fs::create(storage.clone(), CreateOptions::new()),
+ Fs::create(storage.clone(), CreateOptions::new()),
+ );
+ let left = left.unwrap();
+ let right = right.unwrap();
+
+ assert_eq!(left.format(), right.format());
+ let observed = Fs::open(storage).await.unwrap().observe().await.unwrap();
+ assert_eq!(observed.version().number(), VersionNumber::ZERO);
+ assert_eq!(observed.tree().len(), 1);
+ assert_eq!(
+ observed.tree().get(&Path::root()).unwrap().id(),
+ left.format().root()
+ );
+}
+
+#[tokio::test]
+async fn rejects_a_different_create_configuration() {
+ let storage = MemoryStorage::default();
+ Fs::create(storage.clone(), CreateOptions::new())
+ .await
+ .unwrap();
+ let options = CreateOptions::new().with_decodings(vec![Extension::new(
+ ExtensionId::from_bytes([1; 16]),
+ Vec::new(),
+ )]);
+
+ let error = Fs::create(storage, options).await.unwrap_err();
+ assert_eq!(error.kind(), ErrorKind::Conflict);
+}
+
+#[tokio::test]
+async fn publishes_and_retries_one_commit() {
+ let storage = MemoryStorage::default();
+ let filesystem = Fs::create(storage.clone(), CreateOptions::new())
+ .await
+ .unwrap();
+ let observed = filesystem.observe().await.unwrap();
+ let commit = CommitId::generate();
+ let successor = add_directory(observed.tree(), "dir", NodeId::generate());
+
+ assert_eq!(
+ filesystem
+ .commit(&observed, commit, successor.clone())
+ .await
+ .unwrap(),
+ CommitOutcome::Committed {
+ version: VersionNumber::from_value(1)
+ }
+ );
+ assert_eq!(
+ filesystem
+ .commit(&observed, commit, successor)
+ .await
+ .unwrap(),
+ CommitOutcome::Committed {
+ version: VersionNumber::from_value(1)
+ }
+ );
+
+ let reopened = Fs::open(storage).await.unwrap();
+ let current = reopened.observe().await.unwrap();
+ assert!(current.tree().get(&Path::new("dir").unwrap()).is_some());
+ assert_eq!(current.version().commits().len(), 1);
+ assert_eq!(current.version().commits()[0].id(), commit);
+}
+
+#[tokio::test]
+async fn reports_conflict_for_competing_observations() {
+ let filesystem = Fs::create(MemoryStorage::default(), CreateOptions::new())
+ .await
+ .unwrap();
+ let first = filesystem.observe().await.unwrap();
+ let second = filesystem.observe().await.unwrap();
+
+ let first_tree = add_directory(first.tree(), "first", NodeId::generate());
+ let second_tree = add_directory(second.tree(), "second", NodeId::generate());
+ assert!(matches!(
+ filesystem
+ .commit(&first, CommitId::generate(), first_tree)
+ .await
+ .unwrap(),
+ CommitOutcome::Committed { .. }
+ ));
+ assert_eq!(
+ filesystem
+ .commit(&second, CommitId::generate(), second_tree)
+ .await
+ .unwrap(),
+ CommitOutcome::Conflict {
+ current: VersionNumber::from_value(1)
+ }
+ );
+}
+
+#[tokio::test]
+async fn resolves_a_lost_publication_response() {
+ let storage = MemoryStorage::default();
+ let filesystem = Fs::create(storage.clone(), CreateOptions::new())
+ .await
+ .unwrap();
+ let observed = filesystem.observe().await.unwrap();
+ let successor = add_directory(observed.tree(), "durable", NodeId::generate());
+ storage.fail_next_replace_after_success();
+
+ assert_eq!(
+ filesystem
+ .commit(&observed, CommitId::generate(), successor)
+ .await
+ .unwrap(),
+ CommitOutcome::Committed {
+ version: VersionNumber::from_value(1)
+ }
+ );
+}
+
+#[tokio::test]
+async fn requires_directory_generation_for_membership_changes() {
+ let filesystem = Fs::create(MemoryStorage::default(), CreateOptions::new())
+ .await
+ .unwrap();
+ let observed = filesystem.observe().await.unwrap();
+ let mut invalid = observed.tree().clone();
+ invalid.insert(
+ Path::new("child").unwrap(),
+ Node::dir(
+ NodeId::generate(),
+ Generation::FIRST,
+ NodeAttrs::default(),
+ Generation::FIRST,
+ ),
+ );
+
+ let error = filesystem
+ .commit(&observed, CommitId::generate(), invalid)
+ .await
+ .unwrap_err();
+ assert_eq!(error.kind(), ErrorKind::Invalid);
+}
+
+#[tokio::test]
+async fn rejects_duplicate_nodes_and_missing_parents() {
+ let filesystem = Fs::create(MemoryStorage::default(), CreateOptions::new())
+ .await
+ .unwrap();
+ let observed = filesystem.observe().await.unwrap();
+ let node = NodeId::generate();
+ let mut duplicate = add_directory(observed.tree(), "first", node);
+ duplicate.insert(
+ Path::new("second").unwrap(),
+ Node::dir(
+ node,
+ Generation::FIRST,
+ NodeAttrs::default(),
+ Generation::FIRST,
+ ),
+ );
+ assert_eq!(
+ filesystem
+ .commit(&observed, CommitId::generate(), duplicate)
+ .await
+ .unwrap_err()
+ .kind(),
+ ErrorKind::Invalid
+ );
+
+ let mut missing_parent = observed.tree().clone();
+ missing_parent.insert(
+ Path::new("missing/child").unwrap(),
+ Node::dir(
+ NodeId::generate(),
+ Generation::FIRST,
+ NodeAttrs::default(),
+ Generation::FIRST,
+ ),
+ );
+ assert_eq!(
+ filesystem
+ .commit(&observed, CommitId::generate(), missing_parent)
+ .await
+ .unwrap_err()
+ .kind(),
+ ErrorKind::Invalid
+ );
+}
+
+#[tokio::test]
+async fn rejects_case_folding_collisions_within_a_directory() {
+ let filesystem = Fs::create(MemoryStorage::default(), CreateOptions::new())
+ .await
+ .unwrap();
+ let observed = filesystem.observe().await.unwrap();
+ let mut successor = observed.tree().clone();
+ advance_root_membership(&mut successor);
+ successor.insert(
+ Path::new("Readme").unwrap(),
+ Node::dir(
+ NodeId::generate(),
+ Generation::FIRST,
+ NodeAttrs::default(),
+ Generation::FIRST,
+ ),
+ );
+ successor.insert(
+ Path::new("README").unwrap(),
+ Node::dir(
+ NodeId::generate(),
+ Generation::FIRST,
+ NodeAttrs::default(),
+ Generation::FIRST,
+ ),
+ );
+
+ let error = filesystem
+ .commit(&observed, CommitId::generate(), successor)
+ .await
+ .unwrap_err();
+ assert_eq!(error.kind(), ErrorKind::Invalid);
+}
+
+#[tokio::test]
+async fn requires_a_new_file_version_for_content_changes() {
+ let filesystem = Fs::create(MemoryStorage::default(), CreateOptions::new())
+ .await
+ .unwrap();
+ let genesis = filesystem.observe().await.unwrap();
+ let node = NodeId::generate();
+ let file_version = yinyang_core::FileVersionId::generate();
+ let mut first = genesis.tree().clone();
+ advance_root_membership(&mut first);
+ first.insert(
+ Path::new("file").unwrap(),
+ Node::file(
+ node,
+ Generation::FIRST,
+ NodeAttrs::default(),
+ File::new(
+ file_version,
+ ContentId::new(Digest::from_bytes([1; 32]), 0),
+ Vec::new(),
+ )
+ .unwrap(),
+ ),
+ );
+ filesystem
+ .commit(&genesis, CommitId::generate(), first)
+ .await
+ .unwrap();
+
+ let observed = filesystem.observe().await.unwrap();
+ let mut changed = observed.tree().clone();
+ changed.insert(
+ Path::new("file").unwrap(),
+ Node::file(
+ node,
+ Generation::from_value(2),
+ NodeAttrs::default(),
+ File::new(
+ file_version,
+ ContentId::new(Digest::from_bytes([2; 32]), 0),
+ Vec::new(),
+ )
+ .unwrap(),
+ ),
+ );
+ assert_eq!(
+ filesystem
+ .commit(&observed, CommitId::generate(), changed)
+ .await
+ .unwrap_err()
+ .kind(),
+ ErrorKind::Invalid
+ );
+}
+
+#[tokio::test]
+async fn requires_each_configured_decoding_identity() {
+ let filesystem = Fs::create(
+ MemoryStorage::default(),
+ CreateOptions::new().with_decodings(vec![Extension::new(
+ ExtensionId::from_bytes([1; 16]),
+ Vec::new(),
+ )]),
+ )
+ .await
+ .unwrap();
+ let observed = filesystem.observe().await.unwrap();
+ let content = ContentId::new(Digest::from_bytes([3; 32]), 1);
+ let source = FileSource::new(
+ BlobRef::new(b"encoded".to_vec(), content).unwrap(),
+ Vec::new(),
+ );
+ let part = FilePart::new(FileRange::new(0, 1).unwrap(), 0, source).unwrap();
+ let mut tree = observed.tree().clone();
+ advance_root_membership(&mut tree);
+ tree.insert(
+ Path::new("file").unwrap(),
+ Node::file(
+ NodeId::generate(),
+ Generation::FIRST,
+ NodeAttrs::default(),
+ File::new(yinyang_core::FileVersionId::generate(), content, vec![part]).unwrap(),
+ ),
+ );
+
+ assert_eq!(
+ filesystem
+ .commit(&observed, CommitId::generate(), tree)
+ .await
+ .unwrap_err()
+ .kind(),
+ ErrorKind::Invalid
+ );
+}
+
+#[tokio::test]
+async fn preserves_node_generation_across_rename() {
+ let filesystem = Fs::create(MemoryStorage::default(), CreateOptions::new())
+ .await
+ .unwrap();
+ let genesis = filesystem.observe().await.unwrap();
+ let node_id = NodeId::generate();
+ filesystem
+ .commit(
+ &genesis,
+ CommitId::generate(),
+ add_directory(genesis.tree(), "before", node_id),
+ )
+ .await
+ .unwrap();
+ let observed = filesystem.observe().await.unwrap();
+ let mut renamed = observed.tree().clone();
+ let node = renamed
+ .remove(&Path::new("before").unwrap())
+ .expect("the committed directory exists");
+ renamed.insert(Path::new("after").unwrap(), node.clone());
+ let root = renamed.get(&Path::root()).unwrap().clone();
+ let dir = root.dir_body().unwrap();
+ renamed.insert(
+ Path::root(),
+ Node::dir(
+ root.id(),
+ root.generation(),
+ root.attrs(),
+ dir.entries_generation().next().unwrap(),
+ ),
+ );
+
+ filesystem
+ .commit(&observed, CommitId::generate(), renamed)
+ .await
+ .unwrap();
+ let current = filesystem.observe().await.unwrap();
+ assert_eq!(
+ current
+ .tree()
+ .get(&Path::new("after").unwrap())
+ .unwrap()
+ .generation(),
+ Generation::FIRST
+ );
+}
+
+#[test]
+fn validates_file_part_coverage_and_sources() {
+ let source_content = ContentId::new(Digest::from_bytes([1; 32]), 8);
+ let source = FileSource::new(
+ BlobRef::new(b"blob".to_vec(), source_content).unwrap(),
+ Vec::new(),
+ );
+ let first = FilePart::new(FileRange::new(0, 4).unwrap(), 0, source.clone()).unwrap();
+ let second = FilePart::new(FileRange::new(5, 3).unwrap(), 4, source.clone()).unwrap();
+ let content = ContentId::new(Digest::from_bytes([2; 32]), 8);
+
+ assert_eq!(
+ File::new(
+ yinyang_core::FileVersionId::generate(),
+ content,
+ vec![first, second]
+ )
+ .unwrap_err()
+ .kind(),
+ ErrorKind::Invalid
+ );
+ assert_eq!(
+ FilePart::new(FileRange::new(0, 5).unwrap(), 4, source)
+ .unwrap_err()
+ .kind(),
+ ErrorKind::Invalid
+ );
+}
+
+#[test]
+fn accepts_only_canonical_portable_paths() {
+ assert_eq!(Path::new("").unwrap(), Path::root());
+ assert!(Path::new("dir/file").is_ok());
+ for invalid in ["/rooted", "trailing/", "double//slash", ".", "CON", "bad?"] {
+ assert_eq!(Path::new(invalid).unwrap_err().kind(), ErrorKind::Invalid);
+ }
+}
+
+#[tokio::test]
+async fn rejects_a_missing_referenced_version() {
+ let storage = MemoryStorage::default();
+ let filesystem = Fs::create(storage.clone(), CreateOptions::new())
+ .await
+ .unwrap();
+ storage.remove_current_version();
+
+ let error = filesystem.observe().await.unwrap_err();
+ assert_eq!(error.kind(), ErrorKind::Corrupt);
+}
diff --git a/specs/README.md b/specs/README.md
index 0a2c879..bd6ac5c 100644
--- a/specs/README.md
+++ b/specs/README.md
@@ -3,6 +3,8 @@
This directory contains the current, maintained contracts for Apache OpenDAL™
YinYang.
+- [YinYang Format core](yinyang-format.md)
+
A specification describes the currently supported behavior, APIs, wire formats,
invariants, compatibility rules, and implementation boundaries. Specifications
evolve with the implementation and must be updated in the same change as the
diff --git a/specs/yinyang-format.md b/specs/yinyang-format.md
new file mode 100644
index 0000000..9061fa0
--- /dev/null
+++ b/specs/yinyang-format.md
@@ -0,0 +1,118 @@
+# YinYang Format Core
+
+## Scope
+
+The YinYang Format core defines the filesystem values and publication state
+machine shared by all persistent encodings. It owns `FsFormat`, the materialized
+`Tree`, immutable `FsVersion` values, durable `Commit` facts, and the mutable
+`FsHead`. A storage implementation supplies create-once records, immutable
+blobs, and conditional head replacement.
+
+The current implementation stores complete materialized versions and retains
+all commits. Persistent encodings may introduce snapshots, deltas, streams,
+packing, or compaction while preserving the values and transitions in this
+specification.
+
+## Filesystem values
+
+`FsFormat` is created once and contains the filesystem identity, root node
+identity, ordered content-decoding extensions, and an optional head extension.
+The order of content-decoding extensions is significant.
+
+`Tree` is an ordered map from canonical relative `Path` values to `Node` values.
+The empty path is the root. Every other path has an existing directory parent.
+Each `NodeId` occurs at exactly one path. The root is a directory whose identity
+equals `FsFormat.root`.
+
+A node contains its stable identity, node generation, attributes, and either a
+`Dir` or `File` body. Directory membership has an independent generation. A
+file contains a publication identity, a `ContentId`, and ordered `FilePart`
+values. Parts are non-empty, non-overlapping, and exactly cover
+`[0, File.content.length)`. An empty file has no parts. Every part fits within
+the logical content of its `FileSource`, and each source contains one decoded
+identity for every decoding extension in `FsFormat`.
+
+`BlobRef` is an opaque persistent reference plus the identity of its referenced
+bytes. The storage implementation constructs and verifies it. The
+core does not interpret object keys, byte-range syntax, framing, or integrity
+metadata inside the reference.
+
+Paths use normalized portable components. They are relative, NFC-normalized,
+at most 4096 bytes, and contain components of at most 255 bytes. Empty,
+dot-relative, control-character, Windows-reserved, and trailing-space or
+trailing-dot components are rejected. A directory cannot contain two names with
+the same Unicode case-folded NFC form.
+
+## Successor tree contract
+
+New nodes start at node generation 1; new directories also start at membership
+generation 1. A stable `NodeId` cannot change between directory and file.
+
+Rename preserves the node identity and node generation. A change to node
+attributes or file state advances the node generation by exactly one. Unchanged
+node state preserves its generation. File content or parts cannot change while
+retaining the same `FileVersionId`; publishing the same logical bytes under a
+new file version remains valid.
+
+Directory membership is compared as `name -> NodeId`. A create, remove,
+replacement, or rename affecting that mapping advances the directory membership
+generation by exactly one. Unchanged membership preserves its generation.
+
+## Versions and commits
+
+`FsVersion.number` is the publication order. Genesis is version 0 and contains
+no commits. Every non-genesis version retains a contiguous commit sequence that
+ends at its own version number. Commit identities are unique within the retained
+sequence, and each `Commit` binds one caller-assigned `CommitId` to one published
+version.
+
+`FsHead.current.number` equals the referenced version number. The referenced
+version uses the same `FsId` as `FsFormat`. `FsHead.min_retained` never exceeds
+the current version. The initial implementation keeps `min_retained` at version
+0 and carries every commit into its successor.
+
+## Storage contract
+
+A `FormatStorage` implementation provides seven operations:
+
+1. create and read the create-once `FsFormat`;
+2. write and read a verified immutable `FsVersion` blob;
+3. create the initial `FsHead`;
+4. observe `FsHead` together with an opaque condition bound to that exact read;
+5. replace the complete head when the observed condition remains current.
+
+Create and compare-exchange report whether they won the conditional operation.
+An observed condition is never reconstructed through a later metadata request.
+The storage implementation rejects a missing, truncated, or unverifiable blob
+as corrupt data.
+
+## Lifecycle
+
+Creation first publishes `FsFormat`. The winner initializes an empty root tree,
+writes genesis as an immutable version, and creates `FsHead`. Concurrent
+creators that observe the same format configuration reopen the winner. A
+different persisted configuration returns a conflict.
+
+Observation reads `FsHead` and its condition, reads the referenced immutable
+version, and validates the head, filesystem identity, version number, tree, and
+retained commits before returning the value.
+
+Commit accepts an observation, caller-assigned `CommitId`, and complete successor
+tree. It validates the successor, constructs version `current + 1`, persists the
+immutable version, then conditionally replaces `FsHead`. A successful replacement
+returns `Committed`.
+
+When replacement loses a race, the core observes the new current version. The
+same `CommitId` in retained commits means the earlier attempt succeeded and also
+returns `Committed`; otherwise the result is `Conflict`. When replacement
+returns an error after the storage system may have accepted it, the core performs
+the same commit lookup before returning the storage error. This makes retry safe
+when the publication response is lost.
+
+## Encoding boundary
+
+This specification defines no wire representation. An encoding owns record
+envelopes, field layout, object locations, snapshots, deltas, streams, packing,
+and compaction. Decoding must produce values accepted by the core validators;
+encoding must preserve every identity, generation, reference, ordering rule,
+and publication result defined here.