Import the Oxygen specification and the first Rust implementation (root change) ff0af1ee299d

Author: unknown
When: 1 month ago · 2026-09-26 19:37 UTC
Signature: ◈ sealed by Andy McCall
Hash: ff0af1ee299d64b3ca59b3a9f70da9645e199e3e13c338c2c29a4fb300939220
Depends on: nothing: a root change
Depended on by: 835ceb9b3ea7 135bdcadec4a c397a8c36a9f 6f4226bfb87f 91334b7fa574 ed931d1d1102 6c3dbe2018e0 642da2636de2 4275ecb110f5 c0d4075cadc0 80b069facc69 2452b4407ab7 4afe288b7946 9bd98cfb4f7e e02edccce98c 795b8b502ded 544d0541a7e5 157d02e95586 4476cdbb0443 570e35310f31 b260109d27c5 f3811eb20bea 7bd805ffb418 d3b270909c78 45a6f5ec85cf b63fc7a77fc6 82202a4d0025 1ec6fdbc6bcb 6f06d9f912b4 771661aa50f4 8156967b882c ef7d4ea6f33b 67a4fe1aa2d5 8b3c9b2ba502 ad2496f7e608 d36ba2f79f95 028545dfa7a4 87322662f607 c2e1d09047db 69953b507188 0299076f09a2 733ea16a9701 767ac6cd0545 7e0e8e5ad882 51d4862a16d8 b0621c2f8cc4 e59512f2f075 0ed150d62994 e5f8eb2a2006 68dcf21fe055 f05b84d1ad2d c895bc52e4e0 a2387d547373 f53cbe7a204e f0a517d28237 3a6effc74835 c63fed2e0465 02e691881a4e efad40f9ac8e a67914bced23 2cd6bf89adb4 74b4a3c62ea4 092457020692 a39754d02c58 e5d9b0513f3e 3a4b3e018326 b582948f1912 68a924846379 d0016e229b04 7fc365369758 b689779e9e74 530a0fc650a2 e2a5edbf1395 d6e0d5b8b339 aedfe465b611 cb8b8082fa73 ac03130a2b95 5552e69c7325 79b5a90ffd43 170bb436e1d5 d0bf2da15094 579afd107b9b 54e2e6309aa3 dd21fd82687d 33be24095b4b d45dab0484ea c71a5777509a ff1a64f81c1c 648189388f1a 2c9ddac3c387 47ce8b8e2d4b 7ba155f20aa0 9ae4d15a0e4b 2cd40ea1c04c c3d2ef6104c2 f874dc8659c2 8e1194860efa 8d80356371c5 a5f76c79666c 8ad9dfe16303 b277870b0749 a70dce536476 6a0008781d5e bea00d4177c6 5b4c51307b14 360aa74a6277 fddf64baa3d2 e96a430c78f3 b30a880fa409 10b4fd430eab b0461604ed98 14edbaaf5291 ff1f62fee654 3d7120efe04a fd280228bdc2 fb5b6181618a d4dbab97e948 a17fc622ca43 091fef80755d acadb5ed28a1 e266b7d4065c 638fb21420d7 d616faf5d136 ce14f0d68b15 4cce912a0953 e0d56dfca51d 36e51aa806c6 3f1b8fe25ec9 61e9ad6ddc2d 930e5f3f1682 05059d434aca f9575918477f 7eac74abc586 19527875ebdc 40a40bb7b798 dbf06d342e1d e83354cdac22 2306a4d24779 d0d52107b074 f6451fbbae3f 4d6c9c1b358c ab4d4e31b38d 0f93f49ce059 da652d6392d8 57d8dc05c9d4 a87c7b9d563a 519c7c061bcb 598009a75f6c 01a47cd7f0c8 17f94b13ae54 192fad1e46a2 206c76cad4bf 69816d688300 a4fad5b085c7 c5ce0367eddf da868d5d2646 86e1824f2d0b d443639bcf35 1a3b62032ed9 4fe7d6045860 6caacfff1d4f 33e77a5526fa 6f8aeb996558 a9f686edf60b e293c90dca62 dfb23a3a8cfa fc1a466a1e66 83d61e803ccd f7510b63cceb e7ac6c2e84e4 6a81dbab471d 1c2bd9abdd4f be451356e3ef 61e3bce7ea5b 8c30d814f2cc f8c695764c95 cc7a00565161 e8d38e47e9d7 afaba5f1306d 696bbf29d3eb 0bdc3f91a39f 7891e21c762f c863c7a7a2d1 62794ecc7f74 d42369abf180 3e5772ccf9da 19555025a2ac e7ddd552b619 07eb99be126e 1d360c91a289 4dcb8c0916b7 387335ff7f4d 37c299cec358 75036530b621 84b9e9ac0ab4 d82e44097323 9d333fc9ca1b 119bbf50cb86 7aa2dc9369e3 b0e64e81e4fb 05e71ed6cdf1 75167672ebcd e02bf0cd0533 c6aa5bd9d1c8 8b678b298fee 728da0f92161 957fee30826e 4dee277c327a fbda43e7d8ed b3c5a59a875a fe7a964b3c88 86fe29fd62ea 9ac1fbe211b4 50a046e439e9 ee06a6c557b7 b7f102fcbb17 8f10a07a1dbe 2b872d074ddb 30ea9c1e70fa 6e723b81f5b9 6706bdcfb63e 28fc23d7706a 23b217d75848 6d3eefbce2f0 cdb5beba7f05 4e88e774777a 132b884b9a8d 2863456a0f6d 7421309f5372 135212de5370 cfb7d414eae6 252e8cb23fbc 96f7610fa666 315167f3e208 c3069537d7c5 ba160f60219e f77698833f9f c07e0e7d2d85 d02e545dc265 83e0677b07fe 2b5ee371060e 982864068a59 fce44ae9ad29 096f447ccda0 750251b21a96 4161262eeb29 adec9a0796b8 5b9c6ad45f6e 86e682c242c6 b288cd254343 20247a03a596 5b1114a04905 1983686fb7a7 e993a086c13f f9c98deef326 55e5a16a2b9c 648724d8e0de
In bookmarks: agents-in-readme bare-hashes carried-not-removed carry-identical doctor-trust identical-sides keyless-tags main merge-remote-bookmark only-help-103 paths-for-resolutions-and-amend push-notes show-stat subrepo-pin-state switch-says
In tags: v0.1.0 v0.10.0 v0.11.0 v0.2.0 v0.3.0 v0.3.1 v0.4.0 v0.4.1 v0.4.2 v0.4.3 v0.4.4 v0.4.5 v0.4.6 v0.5.0 v0.5.1 v0.6.0 v0.7.0 v0.8.0 v0.9.0
Edits: 19 atoms, 24 tree operations, 19 files

Browse the tree at this change

hide whitespace changes

added .gitignore +1 −0

added .oxyignore +1 −0

added Cargo.lock +622 −0

added Cargo.toml +28 −0

added crates/oxy-core/Cargo.toml +17 −0

added crates/oxy-core/src/cbor.rs +322 −0

added crates/oxy-core/src/diff.rs +146 −0

added crates/oxy-core/src/graph.rs +587 −0

added crates/oxy-core/src/hash.rs +150 −0

added crates/oxy-core/src/ids.rs +93 −0

added crates/oxy-core/src/lib.rs +15 −0

added crates/oxy-core/src/objects.rs +657 −0

added crates/oxy-core/src/oplog.rs +132 −0

added crates/oxy-core/src/repo.rs +1080 −0

added crates/oxy-core/src/state.rs +392 −0

added crates/oxy-core/src/store.rs +177 −0

added crates/oxy-core/src/tree.rs +372 −0

added docs/spec.md +776 −0

added src/main.rs +213 −0

1	+	[workspace]
2	+	members = ["crates/oxy-core", "."]
3	+	resolver = "2"
4	+
5	+	[workspace.package]
6	+	version = "0.1.0"
7	+	edition = "2021"
8	+	license = "MIT OR Apache-2.0"
9	+
10	+	[package]
11	+	name = "oxy"
12	+	version.workspace = true
13	+	edition.workspace = true
14	+	license.workspace = true
15	+	description = "Oxygen: a distributed, commutative version control system"
16	+	default-run = "oxy"
17	+
18	+	[[bin]]
19	+	name = "oxy"
20	+	path = "src/main.rs"
21	+
22	+	[dependencies]
23	+	oxy-core = { path = "crates/oxy-core" }
24	+	clap = { version = "4", features = ["derive"] }
25	+	anyhow = "1"
26	+
27	+	[dev-dependencies]
28	+	tempfile = "3"

1	+	[package]
2	+	name = "oxy-core"
3	+	version.workspace = true
4	+	edition.workspace = true
5	+	license.workspace = true
6	+	description = "Core data model, change graph, and storage for Oxygen"
7	+
8	+	[dependencies]
9	+	blake3 = "1"
10	+	hex = "0.4"
11	+	rand = "0.8"
12	+	similar = "2"
13	+	thiserror = "1"
14	+	ignore = "0.4"
15	+
16	+	[dev-dependencies]
17	+	tempfile = "3"

1	+	//! Turn a working-copy file into edits against the live atoms of a node.
2	+	//! Anchors follow the convention in spec §7.4: an insertion at old position
3	+	//! `i` is anchored after `old[i-1]` and before `old[i]`, both of which are
4	+	//! adjacent in the author's view.
5	+
6	+	use crate::graph::AtomKey;
7	+	use crate::ids::NodeId;
8	+	use crate::objects::{AtomRange, AtomRef, Edit};
9	+	use similar::{capture_diff_slices, Algorithm, DiffOp};
10	+
11	+	/// Split into lines, each keeping its terminator; a final unterminated line
12	+	/// is its own atom.
13	+	pub fn split_lines(b: &[u8]) -> Vec<&[u8]> {
14	+	let mut out = Vec::new();
15	+	let mut start = 0;
16	+	for (i, &c) in b.iter().enumerate() {
17	+	if c == b'\n' {
18	+	out.push(&b[start..=i]);
19	+	start = i + 1;
20	+	}
21	+	}
22	+	if start < b.len() {
23	+	out.push(&b[start..]);
24	+	}
25	+	out
26	+	}
27	+
28	+	/// Coalesce atom keys into half-open ranges of consecutive indices per change.
29	+	pub fn ranges(keys: &[AtomKey]) -> Vec<AtomRange> {
30	+	let mut out: Vec<AtomRange> = Vec::new();
31	+	for &(c, i) in keys {
32	+	match out.last_mut() {
33	+	Some(r) if r.change == c && r.to == i => r.to = i + 1,
34	+	_ => out.push(AtomRange { change: c, from: i, to: i + 1 }),
35	+	}
36	+	}
37	+	out
38	+	}
39	+
40	+	/// Edits that transform the live lines `old` of `node` into `new`.
41	+	pub fn text_edits(node: NodeId, old: &[(AtomKey, Vec<u8>)], new: &[u8]) -> Vec<Edit> {
42	+	let old_lines: Vec<&[u8]> = old.iter().map(\|(_, l)\| l.as_slice()).collect();
43	+	let new_lines = split_lines(new);
44	+	let ops = capture_diff_slices(Algorithm::Myers, &old_lines, &new_lines);
45	+
46	+	let anchor = \|i: usize\| -> (AtomRef, AtomRef) {
47	+	let after = if i == 0 { AtomRef::Start } else { AtomRef::Atom { change: old[i - 1].0 .0, index: old[i - 1].0 .1 } };
48	+	let before = if i >= old.len() { AtomRef::End } else { AtomRef::Atom { change: old[i].0 .0, index: old[i].0 .1 } };
49	+	(after, before)
50	+	};
51	+
52	+	let mut deleted: Vec<AtomKey> = Vec::new();
53	+	let mut inserts: Vec<Edit> = Vec::new();
54	+	for op in ops {
55	+	match op {
56	+	DiffOp::Equal { .. } => {}
57	+	DiffOp::Delete { old_index, old_len, .. } => {
58	+	deleted.extend(old[old_index..old_index + old_len].iter().map(\|(k, _)\| *k));
59	+	}
60	+	DiffOp::Insert { old_index, new_index, new_len } => {
61	+	let (after, before) = anchor(old_index);
62	+	inserts.push(Edit::Insert {
63	+	node,
64	+	after,
65	+	before,
66	+	lines: new_lines[new_index..new_index + new_len].iter().map(\|l\| l.to_vec()).collect(),
67	+	});
68	+	}
69	+	DiffOp::Replace { old_index, old_len, new_index, new_len } => {
70	+	deleted.extend(old[old_index..old_index + old_len].iter().map(\|(k, _)\| *k));
71	+	let (after, before) = anchor(old_index);
72	+	inserts.push(Edit::Insert {
73	+	node,
74	+	after,
75	+	before,
76	+	lines: new_lines[new_index..new_index + new_len].iter().map(\|l\| l.to_vec()).collect(),
77	+	});
78	+	}
79	+	}
80	+	}
81	+	let mut edits = Vec::new();
82	+	if !deleted.is_empty() {
83	+	edits.push(Edit::Delete { node, atoms: ranges(&deleted) });
84	+	}
85	+	edits.extend(inserts);
86	+	edits
87	+	}
88	+
89	+	#[cfg(test)]
90	+	mod tests {
91	+	use super::*;
92	+	use crate::hash::ObjectRef;
93	+
94	+	fn h(n: u8) -> ObjectRef {
95	+	ObjectRef([n; 32])
96	+	}
97	+
98	+	#[test]
99	+	fn split_keeps_terminators() {
100	+	assert_eq!(split_lines(b"a\nb\n"), vec![&b"a\n"[..], &b"b\n"[..]]);
101	+	assert_eq!(split_lines(b"a\nb"), vec![&b"a\n"[..], &b"b"[..]]);
102	+	assert_eq!(split_lines(b""), Vec::<&[u8]>::new());
103	+	assert_eq!(split_lines(b"\n\n"), vec![&b"\n"[..], &b"\n"[..]]);
104	+	}
105	+
106	+	#[test]
107	+	fn ranges_coalesce() {
108	+	let r = ranges(&[(h(1), 0), (h(1), 1), (h(1), 3), (h(2), 0)]);
109	+	assert_eq!(
110	+	r,
111	+	vec![
112	+	AtomRange { change: h(1), from: 0, to: 2 },
113	+	AtomRange { change: h(1), from: 3, to: 4 },
114	+	AtomRange { change: h(2), from: 0, to: 1 }
115	+	]
116	+	);
117	+	}
118	+
119	+	#[test]
120	+	fn edits_for_typical_changes() {
121	+	let node = NodeId::random();
122	+	let old: Vec<(AtomKey, Vec<u8>)> = ["a\n", "b\n", "c\n"].iter().enumerate().map(\|(i, l)\| ((h(1), i as u32), l.as_bytes().to_vec())).collect();
123	+	// No change.
124	+	assert!(text_edits(node, &old, b"a\nb\nc\n").is_empty());
125	+	// Replace middle line.
126	+	let e = text_edits(node, &old, b"a\nB\nc\n");
127	+	assert_eq!(
128	+	e,
129	+	vec![
130	+	Edit::Delete { node, atoms: vec![AtomRange { change: h(1), from: 1, to: 2 }] },
131	+	Edit::Insert { node, after: AtomRef::Atom { change: h(1), index: 0 }, before: AtomRef::Atom { change: h(1), index: 1 }, lines: vec![b"B\n".to_vec()] },
132	+	]
133	+	);
134	+	// Prepend and append.
135	+	let e = text_edits(node, &old, b"top\na\nb\nc\nend\n");
136	+	assert_eq!(e.len(), 2);
137	+	assert!(matches!(&e[0], Edit::Insert { after: AtomRef::Start, before: AtomRef::Atom { index: 0, .. }, .. }));
138	+	assert!(matches!(&e[1], Edit::Insert { after: AtomRef::Atom { index: 2, .. }, before: AtomRef::End, .. }));
139	+	// Delete everything.
140	+	let e = text_edits(node, &old, b"");
141	+	assert_eq!(e, vec![Edit::Delete { node, atoms: vec![AtomRange { change: h(1), from: 0, to: 3 }] }]);
142	+	// From empty.
143	+	let e = text_edits(node, &[], b"x\n");
144	+	assert_eq!(e, vec![Edit::Insert { node, after: AtomRef::Start, before: AtomRef::End, lines: vec![b"x\n".to_vec()] }]);
145	+	}
146	+	}

1	+	//! Object references: BLAKE3-256 over a domain-separating header and the body
2	+	//! (spec §5.2).
3	+
4	+	use std::fmt;
5	+
6	+	#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
7	+	pub struct ObjectRef(pub [u8; 32]);
8	+
9	+	/// A change is referenced by the ObjectRef of its encoding.
10	+	pub type ChangeHash = ObjectRef;
11	+	/// An identity is referenced by the ObjectRef of its encoding.
12	+	pub type KeyId = ObjectRef;
13	+
14	+	impl ObjectRef {
15	+	/// Reserved: means "this change" inside a change (spec §5.2, §7.4).
16	+	pub const ZERO: ObjectRef = ObjectRef([0; 32]);
17	+
18	+	pub fn is_zero(&self) -> bool {
19	+	*self == Self::ZERO
20	+	}
21	+	pub fn to_hex(&self) -> String {
22	+	hex::encode(self.0)
23	+	}
24	+	pub fn from_hex(s: &str) -> Option<ObjectRef> {
25	+	let v = hex::decode(s).ok()?;
26	+	let a: [u8; 32] = v.try_into().ok()?;
27	+	Some(ObjectRef(a))
28	+	}
29	+	pub fn from_slice(b: &[u8]) -> Option<ObjectRef> {
30	+	let a: [u8; 32] = b.try_into().ok()?;
31	+	Some(ObjectRef(a))
32	+	}
33	+	/// First `n` hex characters.
34	+	pub fn short(&self, n: usize) -> String {
35	+	let h = self.to_hex();
36	+	h[..n.min(h.len())].to_string()
37	+	}
38	+	pub fn starts_with_hex(&self, prefix: &str) -> bool {
39	+	self.to_hex().starts_with(prefix)
40	+	}
41	+	}
42	+
43	+	impl fmt::Display for ObjectRef {
44	+	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
45	+	f.write_str(&self.to_hex())
46	+	}
47	+	}
48	+
49	+	impl fmt::Debug for ObjectRef {
50	+	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
51	+	write!(f, "#{}", self.short(12))
52	+	}
53	+	}
54	+
55	+	#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
56	+	pub enum ObjectType {
57	+	Chunk,
58	+	Blob,
59	+	Change,
60	+	Checkpoint,
61	+	Op,
62	+	Attest,
63	+	Identity,
64	+	Policy,
65	+	}
66	+
67	+	impl ObjectType {
68	+	pub const ALL: [ObjectType; 8] = [
69	+	ObjectType::Chunk,
70	+	ObjectType::Blob,
71	+	ObjectType::Change,
72	+	ObjectType::Checkpoint,
73	+	ObjectType::Op,
74	+	ObjectType::Attest,
75	+	ObjectType::Identity,
76	+	ObjectType::Policy,
77	+	];
78	+
79	+	pub fn name(self) -> &'static str {
80	+	match self {
81	+	ObjectType::Chunk => "chunk",
82	+	ObjectType::Blob => "blob",
83	+	ObjectType::Change => "change",
84	+	ObjectType::Checkpoint => "checkpoint",
85	+	ObjectType::Op => "op",
86	+	ObjectType::Attest => "attest",
87	+	ObjectType::Identity => "identity",
88	+	ObjectType::Policy => "policy",
89	+	}
90	+	}
91	+
92	+	pub fn from_name(s: &str) -> Option<ObjectType> {
93	+	Self::ALL.iter().copied().find(\|t\| t.name() == s)
94	+	}
95	+	}
96	+
97	+	/// `ObjectRef = BLAKE3-256("oxy1 " \|\| type \|\| " " \|\| decimal(len) \|\| 0x00 \|\| body)`.
98	+	pub fn hash_object(ty: ObjectType, body: &[u8]) -> ObjectRef {
99	+	let mut h = blake3::Hasher::new();
100	+	h.update(&header(ty, body.len()));
101	+	h.update(body);
102	+	ObjectRef(*h.finalize().as_bytes())
103	+	}
104	+
105	+	pub fn header(ty: ObjectType, len: usize) -> Vec<u8> {
106	+	let mut v = Vec::with_capacity(32);
107	+	v.extend_from_slice(b"oxy1 ");
108	+	v.extend_from_slice(ty.name().as_bytes());
109	+	v.push(b' ');
110	+	v.extend_from_slice(len.to_string().as_bytes());
111	+	v.push(0);
112	+	v
113	+	}
114	+
115	+	#[cfg(test)]
116	+	mod tests {
117	+	use super::*;
118	+
119	+	#[test]
120	+	fn header_matches_spec() {
121	+	assert_eq!(header(ObjectType::Chunk, 5), b"oxy1 chunk 5\0");
122	+	assert_eq!(header(ObjectType::Change, 1234), b"oxy1 change 1234\0");
123	+	}
124	+
125	+	#[test]
126	+	fn types_are_domain_separated() {
127	+	let body = b"same bytes";
128	+	let a = hash_object(ObjectType::Chunk, body);
129	+	let b = hash_object(ObjectType::Blob, body);
130	+	assert_ne!(a, b);
131	+	assert_eq!(a, hash_object(ObjectType::Chunk, body));
132	+	// Reference vector: pin so the format cannot drift silently.
133	+	assert_eq!(
134	+	hash_object(ObjectType::Chunk, b"").to_hex(),
135	+	blake3::hash(b"oxy1 chunk 0\0").to_hex().as_str()
136	+	);
137	+	}
138	+
139	+	#[test]
140	+	fn hex_round_trip() {
141	+	let r = hash_object(ObjectType::Chunk, b"x");
142	+	assert_eq!(ObjectRef::from_hex(&r.to_hex()), Some(r));
143	+	assert_eq!(ObjectRef::from_hex("zz"), None);
144	+	assert!(r.starts_with_hex(&r.short(7)));
145	+	assert!(ObjectRef::ZERO.is_zero());
146	+	for t in ObjectType::ALL {
147	+	assert_eq!(ObjectType::from_name(t.name()), Some(t));
148	+	}
149	+	}
150	+	}

1	+	//! Oxygen core: data model, change graph, and storage.
2	+	//!
3	+	//! See `docs/spec.md` for the specification this implements.
4	+
5	+	pub mod cbor;
6	+	pub mod diff;
7	+	pub mod graph;
8	+	pub mod hash;
9	+	pub mod ids;
10	+	pub mod objects;
11	+	pub mod oplog;
12	+	pub mod repo;
13	+	pub mod state;
14	+	pub mod store;
15	+	pub mod tree;

1	+	# This file is automatically @generated by Cargo.
2	+	# It is not intended for manual editing.
3	+	version = 4
4	+
5	+	[[package]]
6	+	name = "aho-corasick"
7	+	version = "1.1.5"
8	+	source = "registry+https://github.com/rust-lang/crates.io-index"
9	+	checksum = "c982642fa9e8606056828ee9a8505737230110bb1099153c79efe865c59d12ba"
10	+	dependencies = [
11	+	"memchr",
12	+	]
13	+
14	+	[[package]]
15	+	name = "anstream"
16	+	version = "1.0.0"
17	+	source = "registry+https://github.com/rust-lang/crates.io-index"
18	+	checksum = "824a212faf96e9acacdbd09febd34438f8f711fb84e09a8916013cd7815ca28d"
19	+	dependencies = [
20	+	"anstyle",
21	+	"anstyle-parse",
22	+	"anstyle-query",
23	+	"anstyle-wincon",
24	+	"colorchoice",
25	+	"is_terminal_polyfill",
26	+	"utf8parse",
27	+	]
28	+
29	+	[[package]]
30	+	name = "anstyle"
31	+	version = "1.0.14"
32	+	source = "registry+https://github.com/rust-lang/crates.io-index"
33	+	checksum = "940b3a0ca603d1eade50a4846a2afffd5ef57a9feac2c0e2ec2e14f9ead76000"
34	+
35	+	[[package]]
36	+	name = "anstyle-parse"
37	+	version = "1.0.0"
38	+	source = "registry+https://github.com/rust-lang/crates.io-index"
39	+	checksum = "52ce7f38b242319f7cabaa6813055467063ecdc9d355bbb4ce0c68908cd8130e"
40	+	dependencies = [
41	+	"utf8parse",
42	+	]
43	+
44	+	[[package]]
45	+	name = "anstyle-query"
46	+	version = "1.1.5"
47	+	source = "registry+https://github.com/rust-lang/crates.io-index"
48	+	checksum = "40c48f72fd53cd289104fc64099abca73db4166ad86ea0b4341abe65af83dadc"
49	+	dependencies = [
50	+	"windows-sys",
51	+	]
52	+
53	+	[[package]]
54	+	name = "anstyle-wincon"
55	+	version = "3.0.11"
56	+	source = "registry+https://github.com/rust-lang/crates.io-index"
57	+	checksum = "291e6a250ff86cd4a820112fb8898808a366d8f9f58ce16d1f538353ad55747d"
58	+	dependencies = [
59	+	"anstyle",
60	+	"once_cell_polyfill",
61	+	"windows-sys",
62	+	]
63	+
64	+	[[package]]
65	+	name = "anyhow"
66	+	version = "1.0.104"
67	+	source = "registry+https://github.com/rust-lang/crates.io-index"
68	+	checksum = "330a5ed07fa54e4702c9d6c4174f74427fc0ef6e214bbd677ae50a5099946470"
69	+
70	+	[[package]]
71	+	name = "arrayvec"
72	+	version = "0.7.8"
73	+	source = "registry+https://github.com/rust-lang/crates.io-index"
74	+	checksum = "d3fb67a6e08acf24fdeccbac2cb6ac4305825bd1f117462e0e6f2f193345ad56"
75	+
76	+	[[package]]
77	+	name = "bitflags"
78	+	version = "2.13.2"
79	+	source = "registry+https://github.com/rust-lang/crates.io-index"
80	+	checksum = "3ded4057c258ba199e2d26386d3af3780957ecaee6c4ef4041c6b4b8b97c0b06"
81	+
82	+	[[package]]
83	+	name = "blake3"
84	+	version = "1.8.7"
85	+	source = "registry+https://github.com/rust-lang/crates.io-index"
86	+	checksum = "6d9e454fc11f76977dc803893aff6304ed33d6a26efae8696573bea74baa27ae"
87	+	dependencies = [
88	+	"arrayvec",
89	+	"cc",
90	+	"cfg-if",
91	+	"constant_time_eq",
92	+	"cpufeatures",
93	+	]
94	+
95	+	[[package]]
96	+	name = "bstr"
97	+	version = "1.13.1"
98	+	source = "registry+https://github.com/rust-lang/crates.io-index"
99	+	checksum = "6bb31b46c14244e20ee9984b11bf5c992b91fb6939fea616e3512c8baecdbe5f"
100	+	dependencies = [
101	+	"memchr",
102	+	"serde_core",
103	+	]
104	+
105	+	[[package]]
106	+	name = "cc"
107	+	version = "1.5.1"
108	+	source = "registry+https://github.com/rust-lang/crates.io-index"
109	+	checksum = "f360145194ee8e21db5ee7f3fcd4fe52210864c75c985dae33218202c8bbe040"
110	+	dependencies = [
111	+	"find-msvc-tools",
112	+	"shlex",
113	+	]
114	+
115	+	[[package]]
116	+	name = "cfg-if"
117	+	version = "1.0.5"
118	+	source = "registry+https://github.com/rust-lang/crates.io-index"
119	+	checksum = "4e7648175b45a9a48536d676f68d918270699102aa8dab5496df06904c914600"
120	+
121	+	[[package]]
122	+	name = "clap"
123	+	version = "4.6.7"
124	+	source = "registry+https://github.com/rust-lang/crates.io-index"
125	+	checksum = "aa8876b300ab35ba921adea3dfd70157a46249b33f95c9084ae5709785478946"
126	+	dependencies = [
127	+	"clap_builder",
128	+	"clap_derive",
129	+	]
130	+
131	+	[[package]]
132	+	name = "clap_builder"
133	+	version = "4.6.7"
134	+	source = "registry+https://github.com/rust-lang/crates.io-index"
135	+	checksum = "ec0797fb7aeb1406c84efac526901f7ec3ead2124f946b494e72879d4b54704d"
136	+	dependencies = [
137	+	"anstream",
138	+	"anstyle",
139	+	"clap_lex",
140	+	"strsim",
141	+	]
142	+
143	+	[[package]]
144	+	name = "clap_derive"
145	+	version = "4.6.7"
146	+	source = "registry+https://github.com/rust-lang/crates.io-index"
147	+	checksum = "f9c751b79415d4e559e3d1fcf128e09e720eb673a06d26cf6f392d37d75b66e0"
148	+	dependencies = [
149	+	"heck",
150	+	"proc-macro2",
151	+	"quote",
152	+	"syn 3.0.6",
153	+	]
154	+
155	+	[[package]]
156	+	name = "clap_lex"
157	+	version = "1.1.1"
158	+	source = "registry+https://github.com/rust-lang/crates.io-index"
159	+	checksum = "1c133bc6a41be0d194c306b5506d15e6feeea7b1d6604bd3f8310dfb2ca96486"
160	+
161	+	[[package]]
162	+	name = "colorchoice"
163	+	version = "1.0.5"
164	+	source = "registry+https://github.com/rust-lang/crates.io-index"
165	+	checksum = "1d07550c9036bf2ae0c684c4297d503f838287c83c53686d05370d0e139ae570"
166	+
167	+	[[package]]
168	+	name = "constant_time_eq"
169	+	version = "0.4.2"
170	+	source = "registry+https://github.com/rust-lang/crates.io-index"
171	+	checksum = "3d52eff69cd5e647efe296129160853a42795992097e8af39800e1060caeea9b"
172	+
173	+	[[package]]
174	+	name = "cpufeatures"
175	+	version = "0.3.1"
176	+	source = "registry+https://github.com/rust-lang/crates.io-index"
177	+	checksum = "5ca28b0ae3115b884660db4118d803791fd6756b6e88f39c0f3f7859060d7566"
178	+	dependencies = [
179	+	"libc",
180	+	]
181	+
182	+	[[package]]
183	+	name = "crossbeam-deque"
184	+	version = "0.8.8"
185	+	source = "registry+https://github.com/rust-lang/crates.io-index"
186	+	checksum = "622f3fc73690be383c7214310406f28a90e6edeadc3cea882f9d71e495b9711a"
187	+	dependencies = [
188	+	"crossbeam-epoch",
189	+	"crossbeam-utils",
190	+	]
191	+
192	+	[[package]]
193	+	name = "crossbeam-epoch"
194	+	version = "0.9.21"
195	+	source = "registry+https://github.com/rust-lang/crates.io-index"
196	+	checksum = "dc74980687109a3b14c72fd458107bf0baa1da1a1a805e178d15501ba9b86d9d"
197	+	dependencies = [
198	+	"crossbeam-utils",
199	+	]
200	+
201	+	[[package]]
202	+	name = "crossbeam-utils"
203	+	version = "0.8.23"
204	+	source = "registry+https://github.com/rust-lang/crates.io-index"
205	+	checksum = "a31eee39dddec8330830986fcd7625edb5a24ec90ea038215273bbc3adb08ac6"
206	+
207	+	[[package]]
208	+	name = "errno"
209	+	version = "0.3.14"
210	+	source = "registry+https://github.com/rust-lang/crates.io-index"
211	+	checksum = "39cab71617ae0d63f51a36d69f866391735b51691dbda63cf6f96d042b63efeb"
212	+	dependencies = [
213	+	"libc",
214	+	"windows-sys",
215	+	]
216	+
217	+	[[package]]
218	+	name = "fastrand"
219	+	version = "2.5.0"
220	+	source = "registry+https://github.com/rust-lang/crates.io-index"
221	+	checksum = "da7c62ceae207dd37ea5b845da6a0696c799f85e97da1ab5b7910be3c1c80223"
222	+
223	+	[[package]]
224	+	name = "find-msvc-tools"
225	+	version = "0.1.14"
226	+	source = "registry+https://github.com/rust-lang/crates.io-index"
227	+	checksum = "aedcfb3409746eddb02b9e19ebda1c3394f759a152e48ee875a0844d1b955484"
228	+
229	+	[[package]]
230	+	name = "getrandom"
231	+	version = "0.2.17"
232	+	source = "registry+https://github.com/rust-lang/crates.io-index"
233	+	checksum = "ff2abc00be7fca6ebc474524697ae276ad847ad0a6b3faa4bcb027e9a4614ad0"
234	+	dependencies = [
235	+	"cfg-if",
236	+	"libc",
237	+	"wasi",
238	+	]
239	+
240	+	[[package]]
241	+	name = "getrandom"
242	+	version = "0.4.3"
243	+	source = "registry+https://github.com/rust-lang/crates.io-index"
244	+	checksum = "300e883d756b2e4ec94e02791f39b04b522276138852cfc41d9fb7e904106099"
245	+	dependencies = [
246	+	"cfg-if",
247	+	"libc",
248	+	"r-efi",
249	+	]
250	+
251	+	[[package]]
252	+	name = "globset"
253	+	version = "0.4.20"
254	+	source = "registry+https://github.com/rust-lang/crates.io-index"
255	+	checksum = "07c34a9410465b45bd9787443bc7370f37735bad04b0f0cd57ff1a3186c98988"
256	+	dependencies = [
257	+	"aho-corasick",
258	+	"bstr",
259	+	"log",
260	+	"regex-automata",
261	+	"regex-syntax",
262	+	]
263	+
264	+	[[package]]
265	+	name = "heck"
266	+	version = "0.5.0"
267	+	source = "registry+https://github.com/rust-lang/crates.io-index"
268	+	checksum = "2304e00983f87ffb38b55b444b5e3b60a884b5d30c0fca7d82fe33449bbe55ea"
269	+
270	+	[[package]]
271	+	name = "hex"
272	+	version = "0.4.3"
273	+	source = "registry+https://github.com/rust-lang/crates.io-index"
274	+	checksum = "7f24254aa9a54b5c858eaee2f5bccdb46aaf0e486a595ed5fd8f86ba55232a70"
275	+
276	+	[[package]]
277	+	name = "ignore"
278	+	version = "0.4.33"
279	+	source = "registry+https://github.com/rust-lang/crates.io-index"
280	+	checksum = "00b69833ed729dc5aa7d19541d96d6cf8e9137194207a04916d658e43168402f"
281	+	dependencies = [
282	+	"crossbeam-deque",
283	+	"globset",
284	+	"log",
285	+	"memchr",
286	+	"regex-automata",
287	+	"same-file",
288	+	"walkdir",
289	+	"winapi-util",
290	+	]
291	+
292	+	[[package]]
293	+	name = "is_terminal_polyfill"
294	+	version = "1.70.2"
295	+	source = "registry+https://github.com/rust-lang/crates.io-index"
296	+	checksum = "a6cb138bb79a146c1bd460005623e142ef0181e3d0219cb493e02f7d08a35695"
297	+
298	+	[[package]]
299	+	name = "libc"
300	+	version = "0.2.189"
301	+	source = "registry+https://github.com/rust-lang/crates.io-index"
302	+	checksum = "3eaf3ede3fee6db1a4c2ee091bf8a8b4dccdc6d17f656fb07896ee72867612f2"
303	+
304	+	[[package]]
305	+	name = "linux-raw-sys"
306	+	version = "0.12.1"
307	+	source = "registry+https://github.com/rust-lang/crates.io-index"
308	+	checksum = "32a66949e030da00e8c7d4434b251670a91556f4144941d37452769c25d58a53"
309	+
310	+	[[package]]
311	+	name = "log"
312	+	version = "0.4.34"
313	+	source = "registry+https://github.com/rust-lang/crates.io-index"
314	+	checksum = "f9f8bd3e56ce4dfc153cf470fffbfa98c7620958b312ca5c3a4b8d5181fd13c6"
315	+
316	+	[[package]]
317	+	name = "memchr"
318	+	version = "2.8.3"
319	+	source = "registry+https://github.com/rust-lang/crates.io-index"
320	+	checksum = "cf8baf1c55e62ffcace7a9f06f4bd9cd3f0c4beb022d3b367256b91b87513d98"
321	+
322	+	[[package]]
323	+	name = "once_cell"
324	+	version = "1.21.4"
325	+	source = "registry+https://github.com/rust-lang/crates.io-index"
326	+	checksum = "9f7c3e4beb33f85d45ae3e3a1792185706c8e16d043238c593331cc7cd313b50"
327	+
328	+	[[package]]
329	+	name = "once_cell_polyfill"
330	+	version = "1.70.2"
331	+	source = "registry+https://github.com/rust-lang/crates.io-index"
332	+	checksum = "384b8ab6d37215f3c5301a95a4accb5d64aa607f1fcb26a11b5303878451b4fe"
333	+
334	+	[[package]]
335	+	name = "oxy"
336	+	version = "0.1.0"
337	+	dependencies = [
338	+	"anyhow",
339	+	"clap",
340	+	"oxy-core",
341	+	"tempfile",
342	+	]
343	+
344	+	[[package]]
345	+	name = "oxy-core"
346	+	version = "0.1.0"
347	+	dependencies = [
348	+	"blake3",
349	+	"hex",
350	+	"ignore",
351	+	"rand",
352	+	"similar",
353	+	"tempfile",
354	+	"thiserror",
355	+	]
356	+
357	+	[[package]]
358	+	name = "ppv-lite86"
359	+	version = "0.2.21"
360	+	source = "registry+https://github.com/rust-lang/crates.io-index"
361	+	checksum = "85eae3c4ed2f50dcfe72643da4befc30deadb458a9b590d720cde2f2b1e97da9"
362	+	dependencies = [
363	+	"zerocopy",
364	+	]
365	+
366	+	[[package]]
367	+	name = "proc-macro2"
368	+	version = "1.0.107"
369	+	source = "registry+https://github.com/rust-lang/crates.io-index"
370	+	checksum = "985e7ec9bb745e6ce6535b544d84d6cd6f7ad8bd711c398938ae983b91a766d9"
371	+	dependencies = [
372	+	"unicode-ident",
373	+	]
374	+
375	+	[[package]]
376	+	name = "quote"
377	+	version = "1.0.47"
378	+	source = "registry+https://github.com/rust-lang/crates.io-index"
379	+	checksum = "1fbf4db142a473a8d80c26bbf18454ed458bf8d26c8219c331daecfdbd079001"
380	+	dependencies = [
381	+	"proc-macro2",
382	+	]
383	+
384	+	[[package]]
385	+	name = "r-efi"
386	+	version = "6.0.0"
387	+	source = "registry+https://github.com/rust-lang/crates.io-index"
388	+	checksum = "f8dcc9c7d52a811697d2151c701e0d08956f92b0e24136cf4cf27b57a6a0d9bf"
389	+
390	+	[[package]]
391	+	name = "rand"
392	+	version = "0.8.8"
393	+	source = "registry+https://github.com/rust-lang/crates.io-index"
394	+	checksum = "e058c7de0b26af77780c769414d6257830bb240f3c38477dbc2c16e5f54d6d4c"
395	+	dependencies = [
396	+	"libc",
397	+	"rand_chacha",
398	+	"rand_core",
399	+	]
400	+
401	+	[[package]]
402	+	name = "rand_chacha"
403	+	version = "0.3.1"
404	+	source = "registry+https://github.com/rust-lang/crates.io-index"
405	+	checksum = "e6c10a63a0fa32252be49d21e7709d4d4baf8d231c2dbce1eaa8141b9b127d88"
406	+	dependencies = [
407	+	"ppv-lite86",
408	+	"rand_core",
409	+	]
410	+
411	+	[[package]]
412	+	name = "rand_core"
413	+	version = "0.6.4"
414	+	source = "registry+https://github.com/rust-lang/crates.io-index"
415	+	checksum = "ec0be4795e2f6a28069bec0b5ff3e2ac9bafc99e6a9a7dc3547996c5c816922c"
416	+	dependencies = [
417	+	"getrandom 0.2.17",
418	+	]
419	+
420	+	[[package]]
421	+	name = "regex-automata"
422	+	version = "0.4.18"
423	+	source = "registry+https://github.com/rust-lang/crates.io-index"
424	+	checksum = "ad8553b9b26413251cbf30e620595c7a41b3887f03da04579c0e6b0d6a06b4b2"
425	+	dependencies = [
426	+	"aho-corasick",
427	+	"memchr",
428	+	"regex-syntax",
429	+	]
430	+
431	+	[[package]]
432	+	name = "regex-syntax"
433	+	version = "0.8.11"
434	+	source = "registry+https://github.com/rust-lang/crates.io-index"
435	+	checksum = "d6f6ff9a378485b298a5286656da665ba74413d36db0979633275d2e708145d4"
436	+
437	+	[[package]]
438	+	name = "rustix"
439	+	version = "1.1.5"
440	+	source = "registry+https://github.com/rust-lang/crates.io-index"
441	+	checksum = "891efababe418670775f199f0d233d84843c227a0949a883ce15b37c78d6629d"
442	+	dependencies = [
443	+	"bitflags",
444	+	"errno",
445	+	"libc",
446	+	"linux-raw-sys",
447	+	"windows-sys",
448	+	]
449	+
450	+	[[package]]
451	+	name = "same-file"
452	+	version = "1.0.6"
453	+	source = "registry+https://github.com/rust-lang/crates.io-index"
454	+	checksum = "93fc1dc3aaa9bfed95e02e6eadabb4baf7e3078b0bd1b4d7b6b0b68378900502"
455	+	dependencies = [
456	+	"winapi-util",
457	+	]
458	+
459	+	[[package]]
460	+	name = "serde_core"
461	+	version = "1.0.229"
462	+	source = "registry+https://github.com/rust-lang/crates.io-index"
463	+	checksum = "67dca2c9c51e58a4791a4b1ed58308b39c64224d349a935ab5039aa360942a48"
464	+	dependencies = [
465	+	"serde_derive",
466	+	]
467	+
468	+	[[package]]
469	+	name = "serde_derive"
470	+	version = "1.0.229"
471	+	source = "registry+https://github.com/rust-lang/crates.io-index"
472	+	checksum = "e7a5d71263a5a7d47b41f6b3f06ba276f10cc18b0931f1799f710578e2309348"
473	+	dependencies = [
474	+	"proc-macro2",
475	+	"quote",
476	+	"syn 3.0.6",
477	+	]
478	+
479	+	[[package]]
480	+	name = "shlex"
481	+	version = "2.0.1"
482	+	source = "registry+https://github.com/rust-lang/crates.io-index"
483	+	checksum = "f8fadd59c855ef2080decdef8ff161eb6661b86933c9d82e5ba29dc602a55aba"
484	+
485	+	[[package]]
486	+	name = "similar"
487	+	version = "2.7.0"
488	+	source = "registry+https://github.com/rust-lang/crates.io-index"
489	+	checksum = "bbbb5d9659141646ae647b42fe094daf6c6192d1620870b449d9557f748b2daa"
490	+
491	+	[[package]]
492	+	name = "strsim"
493	+	version = "0.11.1"
494	+	source = "registry+https://github.com/rust-lang/crates.io-index"
495	+	checksum = "7da8b5736845d9f2fcb837ea5d9e2628564b3b043a70948a3f0b778838c5fb4f"
496	+
497	+	[[package]]
498	+	name = "syn"
499	+	version = "2.0.119"
500	+	source = "registry+https://github.com/rust-lang/crates.io-index"
501	+	checksum = "872831b642d1a07999a962a351ed35b955ea2cfc8f3862091e2a240a84f17297"
502	+	dependencies = [
503	+	"proc-macro2",
504	+	"quote",
505	+	"unicode-ident",
506	+	]
507	+
508	+	[[package]]
509	+	name = "syn"
510	+	version = "3.0.6"
511	+	source = "registry+https://github.com/rust-lang/crates.io-index"
512	+	checksum = "8593e8e72159ed2257d083c7a454a85cbf854f37a0966d8d483aff8c8a3ebcee"
513	+	dependencies = [
514	+	"proc-macro2",
515	+	"quote",
516	+	"unicode-ident",
517	+	]
518	+
519	+	[[package]]
520	+	name = "tempfile"
521	+	version = "3.27.0"
522	+	source = "registry+https://github.com/rust-lang/crates.io-index"
523	+	checksum = "32497e9a4c7b38532efcdebeef879707aa9f794296a4f0244f6f69e9bc8574bd"
524	+	dependencies = [
525	+	"fastrand",
526	+	"getrandom 0.4.3",
527	+	"once_cell",
528	+	"rustix",
529	+	"windows-sys",
530	+	]
531	+
532	+	[[package]]
533	+	name = "thiserror"
534	+	version = "1.0.69"
535	+	source = "registry+https://github.com/rust-lang/crates.io-index"
536	+	checksum = "b6aaf5339b578ea85b50e080feb250a3e8ae8cfcdff9a461c9ec2904bc923f52"
537	+	dependencies = [
538	+	"thiserror-impl",
539	+	]
540	+
541	+	[[package]]
542	+	name = "thiserror-impl"
543	+	version = "1.0.69"
544	+	source = "registry+https://github.com/rust-lang/crates.io-index"
545	+	checksum = "4fee6c4efc90059e10f81e6d42c60a18f76588c3d74cb83a0b242a2b6c7504c1"
546	+	dependencies = [
547	+	"proc-macro2",
548	+	"quote",
549	+	"syn 2.0.119",
550	+	]
551	+
552	+	[[package]]
553	+	name = "unicode-ident"
554	+	version = "1.0.26"
555	+	source = "registry+https://github.com/rust-lang/crates.io-index"
556	+	checksum = "d245f478577f809a851594d02313b640fb437e0bb33866753cff937863096954"
557	+
558	+	[[package]]
559	+	name = "utf8parse"
560	+	version = "0.2.2"
561	+	source = "registry+https://github.com/rust-lang/crates.io-index"
562	+	checksum = "06abde3611657adf66d383f00b093d7faecc7fa57071cce2578660c9f1010821"
563	+
564	+	[[package]]
565	+	name = "walkdir"
566	+	version = "2.5.0"
567	+	source = "registry+https://github.com/rust-lang/crates.io-index"
568	+	checksum = "29790946404f91d9c5d06f9874efddea1dc06c5efe94541a7d6863108e3a5e4b"
569	+	dependencies = [
570	+	"same-file",
571	+	"winapi-util",
572	+	]
573	+
574	+	[[package]]
575	+	name = "wasi"
576	+	version = "0.11.1+wasi-snapshot-preview1"
577	+	source = "registry+https://github.com/rust-lang/crates.io-index"
578	+	checksum = "ccf3ec651a847eb01de73ccad15eb7d99f80485de043efb2f370cd654f4ea44b"
579	+
580	+	[[package]]
581	+	name = "winapi-util"
582	+	version = "0.1.11"
583	+	source = "registry+https://github.com/rust-lang/crates.io-index"
584	+	checksum = "c2a7b1c03c876122aa43f3020e6c3c3ee5c05081c9a00739faf7503aeba10d22"
585	+	dependencies = [
586	+	"windows-sys",
587	+	]
588	+
589	+	[[package]]
590	+	name = "windows-link"
591	+	version = "0.2.1"
592	+	source = "registry+https://github.com/rust-lang/crates.io-index"
593	+	checksum = "f0805222e57f7521d6a62e36fa9163bc891acd422f971defe97d64e70d0a4fe5"
594	+
595	+	[[package]]
596	+	name = "windows-sys"
597	+	version = "0.61.2"
598	+	source = "registry+https://github.com/rust-lang/crates.io-index"
599	+	checksum = "ae137229bcbd6cdf0f7b80a31df61766145077ddf49416a728b02cb3921ff3fc"
600	+	dependencies = [
601	+	"windows-link",
602	+	]
603	+
604	+	[[package]]
605	+	name = "zerocopy"
606	+	version = "0.8.59"
607	+	source = "registry+https://github.com/rust-lang/crates.io-index"
608	+	checksum = "6df92bf3d9227be3d53173901ddbffac2babc27ae50f397776ffd6dc33f800cb"
609	+	dependencies = [
610	+	"zerocopy-derive",
611	+	]
612	+
613	+	[[package]]
614	+	name = "zerocopy-derive"
615	+	version = "0.8.59"
616	+	source = "registry+https://github.com/rust-lang/crates.io-index"
617	+	checksum = "ac4f328cf2f05d084e496c3e9c3f33ed0a183656a16e1fcec4d464d8373aec82"
618	+	dependencies = [
619	+	"proc-macro2",
620	+	"quote",
621	+	"syn 2.0.119",
622	+	]

1	+	//! Deterministic CBOR (RFC 8949 §4.2.1) restricted to the profile of spec §5.1:
2	+	//! unsigned integers, byte strings, text strings, arrays, maps with unsigned
3	+	//! integer keys in increasing order, booleans, and null. Everything else is
4	+	//! rejected on decode and cannot be expressed on encode.
5	+
6	+	use std::collections::BTreeMap;
7	+
8	+	#[derive(Clone, Debug, PartialEq, Eq)]
9	+	pub enum Value {
10	+	Uint(u64),
11	+	Bytes(Vec<u8>),
12	+	Text(String),
13	+	Array(Vec<Value>),
14	+	Map(BTreeMap<u64, Value>),
15	+	Bool(bool),
16	+	Null,
17	+	}
18	+
19	+	#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
20	+	pub enum CborError {
21	+	#[error("unexpected end of input")]
22	+	UnexpectedEnd,
23	+	#[error("non-canonical encoding: {0}")]
24	+	NonCanonical(&'static str),
25	+	#[error("unsupported CBOR item: {0}")]
26	+	Unsupported(&'static str),
27	+	#[error("trailing bytes after value")]
28	+	TrailingBytes,
29	+	#[error("invalid UTF-8 in text string")]
30	+	InvalidUtf8,
31	+	#[error("map keys must be strictly increasing unsigned integers")]
32	+	BadMapKey,
33	+	#[error("length exceeds input")]
34	+	LengthOverflow,
35	+	}
36	+
37	+	impl Value {
38	+	pub fn map(pairs: impl IntoIterator<Item = (u64, Value)>) -> Value {
39	+	Value::Map(pairs.into_iter().collect())
40	+	}
41	+	pub fn as_uint(&self) -> Option<u64> {
42	+	if let Value::Uint(n) = self { Some(*n) } else { None }
43	+	}
44	+	pub fn as_bytes(&self) -> Option<&[u8]> {
45	+	if let Value::Bytes(b) = self { Some(b) } else { None }
46	+	}
47	+	pub fn as_text(&self) -> Option<&str> {
48	+	if let Value::Text(t) = self { Some(t) } else { None }
49	+	}
50	+	pub fn as_array(&self) -> Option<&[Value]> {
51	+	if let Value::Array(a) = self { Some(a) } else { None }
52	+	}
53	+	pub fn as_map(&self) -> Option<&BTreeMap<u64, Value>> {
54	+	if let Value::Map(m) = self { Some(m) } else { None }
55	+	}
56	+	pub fn as_bool(&self) -> Option<bool> {
57	+	if let Value::Bool(b) = self { Some(*b) } else { None }
58	+	}
59	+	pub fn is_null(&self) -> bool {
60	+	matches!(self, Value::Null)
61	+	}
62	+	}
63	+
64	+	pub fn encode(v: &Value) -> Vec<u8> {
65	+	let mut out = Vec::new();
66	+	encode_into(v, &mut out);
67	+	out
68	+	}
69	+
70	+	pub fn encode_into(v: &Value, out: &mut Vec<u8>) {
71	+	match v {
72	+	Value::Uint(n) => head(out, 0, *n),
73	+	Value::Bytes(b) => {
74	+	head(out, 2, b.len() as u64);
75	+	out.extend_from_slice(b);
76	+	}
77	+	Value::Text(t) => {
78	+	head(out, 3, t.len() as u64);
79	+	out.extend_from_slice(t.as_bytes());
80	+	}
81	+	Value::Array(a) => {
82	+	head(out, 4, a.len() as u64);
83	+	for x in a {
84	+	encode_into(x, out);
85	+	}
86	+	}
87	+	Value::Map(m) => {
88	+	head(out, 5, m.len() as u64);
89	+	for (k, x) in m {
90	+	head(out, 0, *k);
91	+	encode_into(x, out);
92	+	}
93	+	}
94	+	Value::Bool(false) => out.push(0xf4),
95	+	Value::Bool(true) => out.push(0xf5),
96	+	Value::Null => out.push(0xf6),
97	+	}
98	+	}
99	+
100	+	fn head(out: &mut Vec<u8>, major: u8, n: u64) {
101	+	let m = major << 5;
102	+	if n < 24 {
103	+	out.push(m \| n as u8);
104	+	} else if n <= 0xff {
105	+	out.push(m \| 24);
106	+	out.push(n as u8);
107	+	} else if n <= 0xffff {
108	+	out.push(m \| 25);
109	+	out.extend_from_slice(&(n as u16).to_be_bytes());
110	+	} else if n <= 0xffff_ffff {
111	+	out.push(m \| 26);
112	+	out.extend_from_slice(&(n as u32).to_be_bytes());
113	+	} else {
114	+	out.push(m \| 27);
115	+	out.extend_from_slice(&n.to_be_bytes());
116	+	}
117	+	}
118	+
119	+	pub fn decode(bytes: &[u8]) -> Result<Value, CborError> {
120	+	let mut d = Decoder { b: bytes, pos: 0, depth: 0 };
121	+	let v = d.value()?;
122	+	if d.pos != bytes.len() {
123	+	return Err(CborError::TrailingBytes);
124	+	}
125	+	Ok(v)
126	+	}
127	+
128	+	const MAX_DEPTH: u32 = 256;
129	+
130	+	struct Decoder<'a> {
131	+	b: &'a [u8],
132	+	pos: usize,
133	+	depth: u32,
134	+	}
135	+
136	+	impl<'a> Decoder<'a> {
137	+	fn byte(&mut self) -> Result<u8, CborError> {
138	+	let x = *self.b.get(self.pos).ok_or(CborError::UnexpectedEnd)?;
139	+	self.pos += 1;
140	+	Ok(x)
141	+	}
142	+
143	+	fn take(&mut self, n: u64) -> Result<&'a [u8], CborError> {
144	+	let n = usize::try_from(n).map_err(\|_\| CborError::LengthOverflow)?;
145	+	let end = self.pos.checked_add(n).ok_or(CborError::LengthOverflow)?;
146	+	if end > self.b.len() {
147	+	return Err(CborError::UnexpectedEnd);
148	+	}
149	+	let s = &self.b[self.pos..end];
150	+	self.pos = end;
151	+	Ok(s)
152	+	}
153	+
154	+	/// Reads a head for majors 0..=5 and returns (major, argument), enforcing
155	+	/// shortest-form arguments.
156	+	fn head(&mut self) -> Result<(u8, u64), CborError> {
157	+	let ib = self.byte()?;
158	+	let major = ib >> 5;
159	+	let ai = ib & 0x1f;
160	+	if major == 7 {
161	+	return Err(CborError::Unsupported("simple value or float where a length or integer was expected"));
162	+	}
163	+	let n = match ai {
164	+	0..=23 => ai as u64,
165	+	24 => {
166	+	let n = self.byte()? as u64;
167	+	if n < 24 {
168	+	return Err(CborError::NonCanonical("argument fits in the initial byte"));
169	+	}
170	+	n
171	+	}
172	+	25 => {
173	+	let n = u16::from_be_bytes(self.take(2)?.try_into().unwrap()) as u64;
174	+	if n <= 0xff {
175	+	return Err(CborError::NonCanonical("argument fits in one byte"));
176	+	}
177	+	n
178	+	}
179	+	26 => {
180	+	let n = u32::from_be_bytes(self.take(4)?.try_into().unwrap()) as u64;
181	+	if n <= 0xffff {
182	+	return Err(CborError::NonCanonical("argument fits in two bytes"));
183	+	}
184	+	n
185	+	}
186	+	27 => {
187	+	let n = u64::from_be_bytes(self.take(8)?.try_into().unwrap());
188	+	if n <= 0xffff_ffff {
189	+	return Err(CborError::NonCanonical("argument fits in four bytes"));
190	+	}
191	+	n
192	+	}
193	+	28..=30 => return Err(CborError::Unsupported("reserved additional information")),
194	+	_ => return Err(CborError::Unsupported("indefinite-length item")),
195	+	};
196	+	Ok((major, n))
197	+	}
198	+
199	+	fn value(&mut self) -> Result<Value, CborError> {
200	+	self.depth += 1;
201	+	if self.depth > MAX_DEPTH {
202	+	return Err(CborError::Unsupported("nesting deeper than 256"));
203	+	}
204	+	let ib = *self.b.get(self.pos).ok_or(CborError::UnexpectedEnd)?;
205	+	let v = if ib >> 5 == 7 {
206	+	self.pos += 1;
207	+	match ib {
208	+	0xf4 => Value::Bool(false),
209	+	0xf5 => Value::Bool(true),
210	+	0xf6 => Value::Null,
211	+	_ => return Err(CborError::Unsupported("simple value, float, undefined, or break")),
212	+	}
213	+	} else {
214	+	let (major, n) = self.head()?;
215	+	match major {
216	+	0 => Value::Uint(n),
217	+	1 => return Err(CborError::Unsupported("negative integer")),
218	+	2 => Value::Bytes(self.take(n)?.to_vec()),
219	+	3 => Value::Text(
220	+	std::str::from_utf8(self.take(n)?)
221	+	.map_err(\|_\| CborError::InvalidUtf8)?
222	+	.to_owned(),
223	+	),
224	+	4 => {
225	+	let mut a = Vec::new();
226	+	for _ in 0..n {
227	+	a.push(self.value()?);
228	+	}
229	+	Value::Array(a)
230	+	}
231	+	5 => {
232	+	let mut m = BTreeMap::new();
233	+	let mut last: Option<u64> = None;
234	+	for _ in 0..n {
235	+	let (km, k) = self.head()?;
236	+	if km != 0 {
237	+	return Err(CborError::BadMapKey);
238	+	}
239	+	if let Some(l) = last {
240	+	if k <= l {
241	+	return Err(CborError::BadMapKey);
242	+	}
243	+	}
244	+	last = Some(k);
245	+	let v = self.value()?;
246	+	m.insert(k, v);
247	+	}
248	+	Value::Map(m)
249	+	}
250	+	_ => return Err(CborError::Unsupported("tag")),
251	+	}
252	+	};
253	+	self.depth -= 1;
254	+	Ok(v)
255	+	}
256	+	}
257	+
258	+	#[cfg(test)]
259	+	mod tests {
260	+	use super::*;
261	+
262	+	fn rt(v: Value) -> Vec<u8> {
263	+	let b = encode(&v);
264	+	assert_eq!(decode(&b).unwrap(), v);
265	+	b
266	+	}
267	+
268	+	#[test]
269	+	fn integers_use_shortest_form() {
270	+	assert_eq!(rt(Value::Uint(0)), [0x00]);
271	+	assert_eq!(rt(Value::Uint(23)), [0x17]);
272	+	assert_eq!(rt(Value::Uint(24)), [0x18, 24]);
273	+	assert_eq!(rt(Value::Uint(255)), [0x18, 255]);
274	+	assert_eq!(rt(Value::Uint(256)), [0x19, 1, 0]);
275	+	assert_eq!(rt(Value::Uint(65536)), [0x1a, 0, 1, 0, 0]);
276	+	assert_eq!(rt(Value::Uint(1 << 32)), [0x1b, 0, 0, 0, 1, 0, 0, 0, 0]);
277	+	assert_eq!(rt(Value::Uint(u64::MAX)).len(), 9);
278	+	}
279	+
280	+	#[test]
281	+	fn rejects_non_shortest_integers() {
282	+	assert_eq!(decode(&[0x18, 5]), Err(CborError::NonCanonical("argument fits in the initial byte")));
283	+	assert_eq!(decode(&[0x19, 0, 5]), Err(CborError::NonCanonical("argument fits in one byte")));
284	+	assert_eq!(decode(&[0x1a, 0, 0, 0, 5]), Err(CborError::NonCanonical("argument fits in two bytes")));
285	+	assert_eq!(decode(&[0x1b, 0, 0, 0, 0, 0, 0, 0, 5]), Err(CborError::NonCanonical("argument fits in four bytes")));
286	+	}
287	+
288	+	#[test]
289	+	fn rejects_unsupported_items() {
290	+	assert!(matches!(decode(&[0x20]), Err(CborError::Unsupported(_)))); // -1
291	+	assert!(matches!(decode(&[0xc0, 0x00]), Err(CborError::Unsupported(_)))); // tag
292	+	assert!(matches!(decode(&[0xf9, 0, 0]), Err(CborError::Unsupported(_)))); // float16
293	+	assert!(matches!(decode(&[0x9f, 0xff]), Err(CborError::Unsupported(_)))); // indefinite array
294	+	assert!(matches!(decode(&[0xf7]), Err(CborError::Unsupported(_)))); // undefined
295	+	}
296	+
297	+	#[test]
298	+	fn maps_are_sorted_and_unique() {
299	+	let v = Value::map([(2, Value::Uint(1)), (0, Value::Null), (1, Value::Bool(true))]);
300	+	let b = rt(v);
301	+	assert_eq!(b, [0xa3, 0x00, 0xf6, 0x01, 0xf5, 0x02, 0x01]);
302	+	assert_eq!(decode(&[0xa2, 0x01, 0x00, 0x00, 0x00]), Err(CborError::BadMapKey));
303	+	assert_eq!(decode(&[0xa2, 0x01, 0x00, 0x01, 0x00]), Err(CborError::BadMapKey));
304	+	assert_eq!(decode(&[0xa1, 0x61, 0x61, 0x00]), Err(CborError::BadMapKey)); // text key
305	+	}
306	+
307	+	#[test]
308	+	fn strings_arrays_and_trailing() {
309	+	rt(Value::Bytes(vec![1, 2, 3]));
310	+	rt(Value::Text("héllo".into()));
311	+	rt(Value::Array(vec![Value::Uint(1), Value::Text("x".into()), Value::Array(vec![])]));
312	+	assert_eq!(decode(&[0x00, 0x00]), Err(CborError::TrailingBytes));
313	+	assert_eq!(decode(&[0x62, 0xff, 0xfe]), Err(CborError::InvalidUtf8));
314	+	assert_eq!(decode(&[0x43, 1, 2]), Err(CborError::UnexpectedEnd));
315	+	}
316	+
317	+	#[test]
318	+	fn huge_length_does_not_allocate() {
319	+	assert_eq!(decode(&[0x5b, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]), Err(CborError::LengthOverflow));
320	+	assert!(decode(&[0x9b, 0x00, 0x00, 0x00, 0x01, 0, 0, 0, 0]).is_err());
321	+	}
322	+	}

1	+	//! The per-file atom graph (spec §7.3), its materialization, and text conflict
2	+	//! detection (spec §9.1, §9.5).
3	+	//!
4	+	//! The graph is a pure function of the set of changes applied to it: inserts
5	+	//! add vertices and edges, deletes set a flag, and nothing is ever removed.
6	+
7	+	use crate::hash::ChangeHash;
8	+	use crate::objects::AtomRange;
9	+	use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
10	+
11	+	/// `(introducing change, index within that change for this node)`.
12	+	pub type AtomKey = (ChangeHash, u32);
13	+
14	+	#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
15	+	pub enum Vertex {
16	+	Start,
17	+	Atom(AtomKey),
18	+	End,
19	+	}
20	+
21	+	/// Transitive dependency test between changes; `depends_on(a, a)` is true.
22	+	pub trait DepOracle {
23	+	fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool;
24	+	}
25	+
26	+	/// No change depends on any other: every pair commutes.
27	+	pub struct NoDeps;
28	+	impl DepOracle for NoDeps {
29	+	fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool {
30	+	a == b
31	+	}
32	+	}
33	+
34	+	#[derive(Default, Clone, Debug)]
35	+	struct AtomInfo {
36	+	/// `None` until the introducing change has been applied.
37	+	content: Option<Vec<u8>>,
38	+	deleted_by: BTreeSet<ChangeHash>,
39	+	}
40	+
41	+	#[derive(Clone, Debug)]
42	+	pub struct FileGraph {
43	+	atoms: HashMap<AtomKey, AtomInfo>,
44	+	succ: HashMap<Vertex, BTreeSet<Vertex>>,
45	+	pred: HashMap<Vertex, BTreeSet<Vertex>>,
46	+	}
47	+
48	+	impl Default for FileGraph {
49	+	fn default() -> Self {
50	+	Self::new()
51	+	}
52	+	}
53	+
54	+	/// One piece of a materialized file.
55	+	#[derive(Clone, Debug, PartialEq, Eq)]
56	+	pub enum Segment {
57	+	Lines(Vec<AtomKey>),
58	+	/// Order conflict: alternatives that cannot be ordered against each other.
59	+	Conflict(Vec<Vec<AtomKey>>),
60	+	/// Delete/insert conflict: `inserted` was anchored to `deleted` by a change
61	+	/// that commutes with the deletion.
62	+	Zombie { deleted: Vec<AtomKey>, inserted: Vec<AtomKey> },
63	+	}
64	+
65	+	#[derive(Clone, Debug, PartialEq, Eq, Default)]
66	+	pub struct Materialized {
67	+	pub segments: Vec<Segment>,
68	+	}
69	+
70	+	impl Materialized {
71	+	pub fn is_conflicted(&self) -> bool {
72	+	self.segments.iter().any(\|s\| !matches!(s, Segment::Lines(_)))
73	+	}
74	+	pub fn conflict_count(&self) -> usize {
75	+	self.segments.iter().filter(\|s\| !matches!(s, Segment::Lines(_))).count()
76	+	}
77	+	/// Every live atom in materialized order, conflict sides concatenated.
78	+	pub fn live_atoms(&self) -> Vec<AtomKey> {
79	+	let mut out = Vec::new();
80	+	for s in &self.segments {
81	+	match s {
82	+	Segment::Lines(a) => out.extend(a),
83	+	Segment::Conflict(sides) => sides.iter().for_each(\|x\| out.extend(x)),
84	+	Segment::Zombie { inserted, .. } => out.extend(inserted),
85	+	}
86	+	}
87	+	out
88	+	}
89	+	}
90	+
91	+	impl FileGraph {
92	+	pub fn new() -> Self {
93	+	let mut g = FileGraph { atoms: HashMap::new(), succ: HashMap::new(), pred: HashMap::new() };
94	+	g.edge(Vertex::Start, Vertex::End);
95	+	g
96	+	}
97	+
98	+	fn edge(&mut self, a: Vertex, b: Vertex) {
99	+	self.succ.entry(a).or_default().insert(b);
100	+	self.pred.entry(b).or_default().insert(a);
101	+	self.succ.entry(b).or_default();
102	+	self.pred.entry(a).or_default();
103	+	}
104	+
105	+	/// Apply an `Insert` by `change` whose first new atom has index `first_index`.
106	+	pub fn insert(&mut self, change: ChangeHash, first_index: u32, after: Vertex, before: Vertex, lines: &[Vec<u8>]) {
107	+	let mut prev = after;
108	+	for (i, line) in lines.iter().enumerate() {
109	+	let key = (change, first_index + i as u32);
110	+	self.atoms.entry(key).or_default().content = Some(line.clone());
111	+	let v = Vertex::Atom(key);
112	+	self.edge(prev, v);
113	+	prev = v;
114	+	}
115	+	self.edge(prev, before);
116	+	}
117	+
118	+	/// Apply a `Delete` of `range` by change `by`.
119	+	pub fn delete(&mut self, by: ChangeHash, range: &AtomRange) {
120	+	for i in range.from..range.to {
121	+	self.atoms.entry((range.change, i)).or_default().deleted_by.insert(by);
122	+	}
123	+	}
124	+
125	+	pub fn is_live(&self, k: &AtomKey) -> bool {
126	+	self.atoms.get(k).is_some_and(\|a\| a.content.is_some() && a.deleted_by.is_empty())
127	+	}
128	+
129	+	pub fn content(&self, k: &AtomKey) -> Option<&[u8]> {
130	+	self.atoms.get(k).and_then(\|a\| a.content.as_deref())
131	+	}
132	+
133	+	pub fn deleters(&self, k: &AtomKey) -> impl Iterator<Item = &ChangeHash> {
134	+	self.atoms.get(k).into_iter().flat_map(\|a\| a.deleted_by.iter())
135	+	}
136	+
137	+	/// Number of atoms introduced by `change` in this graph (for index bookkeeping).
138	+	pub fn atom_count(&self) -> usize {
139	+	self.atoms.len()
140	+	}
141	+
142	+	fn is_ghost(&self, k: &AtomKey, info: &AtomInfo, deps: &dyn DepOracle) -> bool {
143	+	// A deleted atom is a ghost when a live direct successor was inserted by
144	+	// a change that no deleter depends on (spec §9.1, delete/insert).
145	+	self.succ.get(&Vertex::Atom(*k)).is_some_and(\|ss\| {
146	+	ss.iter().any(\|s\| match s {
147	+	Vertex::Atom(y) if self.is_live(y) => !info.deleted_by.iter().any(\|d\| deps.depends_on(d, &y.0)),
148	+	_ => false,
149	+	})
150	+	})
151	+	}
152	+
153	+	/// Successors of `v` in the graph with non-kept vertices contracted away.
154	+	fn reduced_succ(&self, v: Vertex, kept: &HashSet<Vertex>, memo: &mut HashMap<Vertex, BTreeSet<Vertex>>) -> BTreeSet<Vertex> {
155	+	let mut out = BTreeSet::new();
156	+	let mut stack: Vec<Vertex> = self.succ.get(&v).map(\|s\| s.iter().copied().collect()).unwrap_or_default();
157	+	let mut seen = HashSet::new();
158	+	while let Some(s) = stack.pop() {
159	+	if kept.contains(&s) {
160	+	out.insert(s);
161	+	} else if seen.insert(s) {
162	+	if let Some(m) = memo.get(&s) {
163	+	out.extend(m.iter().copied());
164	+	} else if let Some(next) = self.succ.get(&s) {
165	+	stack.extend(next.iter().copied());
166	+	}
167	+	}
168	+	}
169	+	out
170	+	}
171	+
172	+	/// Order the live atoms and locate conflicts.
173	+	pub fn materialize(&self, deps: &dyn DepOracle) -> Materialized {
174	+	// 1. Vertices that survive contraction: live atoms, ghosts, Start, End.
175	+	let mut kept: HashSet<Vertex> = HashSet::new();
176	+	let mut ghosts: HashSet<AtomKey> = HashSet::new();
177	+	kept.insert(Vertex::Start);
178	+	kept.insert(Vertex::End);
179	+	for (k, info) in &self.atoms {
180	+	if info.content.is_none() {
181	+	continue;
182	+	}
183	+	if info.deleted_by.is_empty() {
184	+	kept.insert(Vertex::Atom(*k));
185	+	} else if self.is_ghost(k, info, deps) {
186	+	kept.insert(Vertex::Atom(*k));
187	+	ghosts.insert(*k);
188	+	}
189	+	}
190	+
191	+	// 2. Reduced graph over kept vertices.
192	+	let mut memo = HashMap::new();
193	+	let mut rsucc: HashMap<Vertex, BTreeSet<Vertex>> = HashMap::new();
194	+	let mut indeg: HashMap<Vertex, usize> = HashMap::new();
195	+	for &u in &kept {
196	+	indeg.entry(u).or_insert(0);
197	+	let rs = self.reduced_succ(u, &kept, &mut memo);
198	+	for &w in &rs {
199	+	*indeg.entry(w).or_insert(0) += 1;
200	+	}
201	+	rsucc.insert(u, rs);
202	+	}
203	+
204	+	// 3. Kahn's algorithm with side labelling for conflict regions.
205	+	let mut ready: BTreeSet<Vertex> = indeg.iter().filter(\|(_, &d)\| d == 0).map(\|(v, _)\| *v).collect();
206	+	let mut side: HashMap<Vertex, u32> = HashMap::new();
207	+	let mut joins: HashSet<Vertex> = HashSet::new();
208	+	let mut next_side = 0u32;
209	+	let mut plain: Vec<Vertex> = Vec::new();
210	+	let mut conflict: Option<BTreeMap<u32, Vec<Vertex>>> = None;
211	+	let mut segments: Vec<Segment> = Vec::new();
212	+
213	+	let flush_plain = \|plain: &mut Vec<Vertex>, segments: &mut Vec<Segment>\| {
214	+	let atoms: Vec<AtomKey> = plain.iter().filter_map(\|v\| if let Vertex::Atom(k) = v { Some(*k) } else { None }).collect();
215	+	plain.clear();
216	+	if !atoms.is_empty() {
217	+	segments.extend(split_zombies(atoms, &ghosts));
218	+	}
219	+	};
220	+	let finish_conflict = \|c: BTreeMap<u32, Vec<Vertex>>, segments: &mut Vec<Segment>\| {
221	+	let sides: Vec<Vec<AtomKey>> = c
222	+	.into_values()
223	+	.map(\|vs\| {
224	+	vs.into_iter()
225	+	.filter_map(\|v\| match v {
226	+	Vertex::Atom(k) if !ghosts.contains(&k) => Some(k),
227	+	_ => None,
228	+	})
229	+	.collect::<Vec<_>>()
230	+	})
231	+	.filter(\|s\| !s.is_empty())
232	+	.collect();
233	+	match sides.len() {
234	+	0 => {}
235	+	1 => segments.push(Segment::Lines(sides.into_iter().next().unwrap())),
236	+	_ => segments.push(Segment::Conflict(sides)),
237	+	}
238	+	};
239	+
240	+	while !ready.is_empty() {
241	+	if ready.len() >= 2 {
242	+	if conflict.is_none() {
243	+	flush_plain(&mut plain, &mut segments);
244	+	conflict = Some(BTreeMap::new());
245	+	}
246	+	for r in &ready {
247	+	if !side.contains_key(r) {
248	+	side.insert(*r, next_side);
249	+	next_side += 1;
250	+	}
251	+	}
252	+	}
253	+	let v = ready.pop_first().unwrap();
254	+	let my_side = side.get(&v).copied();
255	+	match (&mut conflict, my_side) {
256	+	(Some(c), Some(s)) => c.entry(s).or_default().push(v),
257	+	(Some(_), None) => {
258	+	let c = conflict.take().unwrap();
259	+	finish_conflict(c, &mut segments);
260	+	plain.push(v);
261	+	}
262	+	(None, _) => plain.push(v),
263	+	}
264	+	for &w in &rsucc[&v] {
265	+	let d = indeg.get_mut(&w).unwrap();
266	+	*d -= 1;
267	+	if conflict.is_some() && !joins.contains(&w) {
268	+	match (my_side, side.get(&w).copied()) {
269	+	(Some(s), None) => {
270	+	side.insert(w, s);
271	+	}
272	+	(Some(s), Some(t)) if s != t => {
273	+	side.remove(&w);
274	+	joins.insert(w);
275	+	}
276	+	(None, Some(_)) => {
277	+	side.remove(&w);
278	+	joins.insert(w);
279	+	}
280	+	_ => {}
281	+	}
282	+	}
283	+	if *d == 0 {
284	+	ready.insert(w);
285	+	}
286	+	}
287	+	}
288	+	if let Some(c) = conflict.take() {
289	+	finish_conflict(c, &mut segments);
290	+	}
291	+	flush_plain(&mut plain, &mut segments);
292	+	Materialized { segments }
293	+	}
294	+
295	+	/// Render a materialization to bytes with conflict markers (spec §9.5).
296	+	/// `label` gives the short description of a change for marker headers.
297	+	pub fn render(&self, m: &Materialized, label: &dyn Fn(&ChangeHash) -> String) -> Vec<u8> {
298	+	let total = m.conflict_count();
299	+	let mut n = 0;
300	+	let mut out: Vec<u8> = Vec::new();
301	+	let push_atoms = \|out: &mut Vec<u8>, atoms: &[AtomKey]\| {
302	+	for a in atoms {
303	+	if let Some(c) = self.content(a) {
304	+	out.extend_from_slice(c);
305	+	}
306	+	}
307	+	};
308	+	let newline_if_needed = \|out: &mut Vec<u8>\| {
309	+	if !out.is_empty() && *out.last().unwrap() != b'\n' {
310	+	out.push(b'\n');
311	+	}
312	+	};
313	+	for seg in &m.segments {
314	+	match seg {
315	+	Segment::Lines(a) => push_atoms(&mut out, a),
316	+	Segment::Conflict(sides) => {
317	+	n += 1;
318	+	let k = sides.len();
319	+	for (i, s) in sides.iter().enumerate() {
320	+	newline_if_needed(&mut out);
321	+	let who = s.first().map(\|a\| label(&a.0)).unwrap_or_default();
322	+	let marker = if i == 0 { "<<<<<<<" } else { "=======" };
323	+	out.extend_from_slice(
324	+	format!("{marker} oxy conflict {n} of {total}, side {} of {k}: change {who}\n", i + 1).as_bytes(),
325	+	);
326	+	push_atoms(&mut out, s);
327	+	}
328	+	newline_if_needed(&mut out);
329	+	out.extend_from_slice(format!(">>>>>>> oxy conflict {n} of {total} end\n").as_bytes());
330	+	}
331	+	Segment::Zombie { deleted, inserted } => {
332	+	n += 1;
333	+	newline_if_needed(&mut out);
334	+	let deleter = deleted
335	+	.first()
336	+	.and_then(\|a\| self.deleters(a).next().copied())
337	+	.map(\|d\| label(&d))
338	+	.unwrap_or_default();
339	+	let inserter = inserted.first().map(\|a\| label(&a.0)).unwrap_or_default();
340	+	out.extend_from_slice(
341	+	format!("<<<<<<< oxy conflict {n} of {total}, side 1 of 2: deleted by change {deleter}\n-------\n").as_bytes(),
342	+	);
343	+	push_atoms(&mut out, deleted);
344	+	newline_if_needed(&mut out);
345	+	out.extend_from_slice(format!("======= oxy conflict {n} of {total}, side 2 of 2: change {inserter}\n").as_bytes());
346	+	push_atoms(&mut out, inserted);
347	+	newline_if_needed(&mut out);
348	+	out.extend_from_slice(format!(">>>>>>> oxy conflict {n} of {total} end\n").as_bytes());
349	+	}
350	+	}
351	+	}
352	+	out
353	+	}
354	+	}
355	+
356	+	/// Split a plain run into `Lines` and `Zombie` segments around ghost atoms.
357	+	fn split_zombies(atoms: Vec<AtomKey>, ghosts: &HashSet<AtomKey>) -> Vec<Segment> {
358	+	let mut out = Vec::new();
359	+	let mut lines: Vec<AtomKey> = Vec::new();
360	+	let mut i = 0;
361	+	while i < atoms.len() {
362	+	if !ghosts.contains(&atoms[i]) {
363	+	lines.push(atoms[i]);
364	+	i += 1;
365	+	continue;
366	+	}
367	+	if !lines.is_empty() {
368	+	out.push(Segment::Lines(std::mem::take(&mut lines)));
369	+	}
370	+	let mut deleted = Vec::new();
371	+	while i < atoms.len() && ghosts.contains(&atoms[i]) {
372	+	deleted.push(atoms[i]);
373	+	i += 1;
374	+	}
375	+	let mut inserted = Vec::new();
376	+	if i < atoms.len() {
377	+	let ch = atoms[i].0;
378	+	while i < atoms.len() && atoms[i].0 == ch && !ghosts.contains(&atoms[i]) {
379	+	inserted.push(atoms[i]);
380	+	i += 1;
381	+	}
382	+	}
383	+	out.push(Segment::Zombie { deleted, inserted });
384	+	}
385	+	if !lines.is_empty() {
386	+	out.push(Segment::Lines(lines));
387	+	}
388	+	out
389	+	}
390	+
391	+	#[cfg(test)]
392	+	mod tests {
393	+	use super::*;
394	+	use crate::hash::ObjectRef;
395	+
396	+	fn h(n: u8) -> ChangeHash {
397	+	ObjectRef([n; 32])
398	+	}
399	+	fn lines(v: &[&str]) -> Vec<Vec<u8>> {
400	+	v.iter().map(\|s\| s.as_bytes().to_vec()).collect()
401	+	}
402	+	fn text(g: &FileGraph, m: &Materialized) -> String {
403	+	String::from_utf8(g.render(m, &\|c\| c.short(4))).unwrap()
404	+	}
405	+
406	+	struct Deps(HashMap<ChangeHash, Vec<ChangeHash>>);
407	+	impl DepOracle for Deps {
408	+	fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool {
409	+	if a == b {
410	+	return true;
411	+	}
412	+	let mut stack = vec![*a];
413	+	let mut seen = HashSet::new();
414	+	while let Some(x) = stack.pop() {
415	+	if let Some(ds) = self.0.get(&x) {
416	+	for d in ds {
417	+	if d == b {
418	+	return true;
419	+	}
420	+	if seen.insert(*d) {
421	+	stack.push(*d);
422	+	}
423	+	}
424	+	}
425	+	}
426	+	false
427	+	}
428	+	}
429	+
430	+	#[test]
431	+	fn sequential_inserts_and_deletes() {
432	+	let mut g = FileGraph::new();
433	+	g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n", "c\n"]));
434	+	let m = g.materialize(&NoDeps);
435	+	assert!(!m.is_conflicted());
436	+	assert_eq!(text(&g, &m), "a\nb\nc\n");
437	+
438	+	// Change 2 depends on 1, inserts between b and c and deletes a.
439	+	g.insert(h(2), 0, Vertex::Atom((h(1), 1)), Vertex::Atom((h(1), 2)), &lines(&["x\n"]));
440	+	g.delete(h(2), &AtomRange { change: h(1), from: 0, to: 1 });
441	+	let deps = Deps([(h(2), vec![h(1)])].into_iter().collect());
442	+	let m = g.materialize(&deps);
443	+	assert!(!m.is_conflicted());
444	+	assert_eq!(text(&g, &m), "b\nx\nc\n");
445	+	assert_eq!(m.live_atoms(), vec![(h(1), 1), (h(2), 0), (h(1), 2)]);
446	+	}
447	+
448	+	#[test]
449	+	fn concurrent_inserts_at_same_anchor_conflict() {
450	+	let mut g = FileGraph::new();
451	+	g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
452	+	g.insert(h(2), 0, Vertex::Atom((h(1), 0)), Vertex::Atom((h(1), 1)), &lines(&["from-2\n"]));
453	+	g.insert(h(3), 0, Vertex::Atom((h(1), 0)), Vertex::Atom((h(1), 1)), &lines(&["from-3\n", "more-3\n"]));
454	+	let deps = Deps([(h(2), vec![h(1)]), (h(3), vec![h(1)])].into_iter().collect());
455	+	let m = g.materialize(&deps);
456	+	assert!(m.is_conflicted());
457	+	assert_eq!(m.conflict_count(), 1);
458	+	assert_eq!(
459	+	m.segments,
460	+	vec![
461	+	Segment::Lines(vec![(h(1), 0)]),
462	+	Segment::Conflict(vec![vec![(h(2), 0)], vec![(h(3), 0), (h(3), 1)]]),
463	+	Segment::Lines(vec![(h(1), 1)]),
464	+	]
465	+	);
466	+	let t = text(&g, &m);
467	+	assert!(t.starts_with("a\n<<<<<<< oxy conflict 1 of 1, side 1 of 2: change 0202\nfrom-2\n======= oxy conflict 1 of 1, side 2 of 2: change 0303\nfrom-3\nmore-3\n>>>>>>> oxy conflict 1 of 1 end\nb\n"), "{t}");
468	+	}
469	+
470	+	#[test]
471	+	fn concurrent_inserts_at_different_anchors_do_not_conflict() {
472	+	let mut g = FileGraph::new();
473	+	g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n", "c\n"]));
474	+	g.insert(h(2), 0, Vertex::Start, Vertex::Atom((h(1), 0)), &lines(&["top\n"]));
475	+	g.insert(h(3), 0, Vertex::Atom((h(1), 2)), Vertex::End, &lines(&["bottom\n"]));
476	+	let deps = Deps([(h(2), vec![h(1)]), (h(3), vec![h(1)])].into_iter().collect());
477	+	let m = g.materialize(&deps);
478	+	assert!(!m.is_conflicted());
479	+	assert_eq!(text(&g, &m), "top\na\nb\nc\nbottom\n");
480	+	}
481	+
482	+	#[test]
483	+	fn concurrent_deletes_of_the_same_line_agree() {
484	+	let mut g = FileGraph::new();
485	+	g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
486	+	g.delete(h(2), &AtomRange { change: h(1), from: 0, to: 1 });
487	+	g.delete(h(3), &AtomRange { change: h(1), from: 0, to: 1 });
488	+	let deps = Deps([(h(2), vec![h(1)]), (h(3), vec![h(1)])].into_iter().collect());
489	+	let m = g.materialize(&deps);
490	+	assert!(!m.is_conflicted());
491	+	assert_eq!(text(&g, &m), "b\n");
492	+	}
493	+
494	+	#[test]
495	+	fn delete_insert_conflict_is_a_zombie() {
496	+	let mut g = FileGraph::new();
497	+	g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
498	+	// 2 deletes a; 3 (concurrent) inserts after a.
499	+	g.delete(h(2), &AtomRange { change: h(1), from: 0, to: 1 });
500	+	g.insert(h(3), 0, Vertex::Atom((h(1), 0)), Vertex::Atom((h(1), 1)), &lines(&["after-a\n"]));
501	+	let deps = Deps([(h(2), vec![h(1)]), (h(3), vec![h(1)])].into_iter().collect());
502	+	let m = g.materialize(&deps);
503	+	assert!(m.is_conflicted());
504	+	assert_eq!(
505	+	m.segments,
506	+	vec![
507	+	Segment::Zombie { deleted: vec![(h(1), 0)], inserted: vec![(h(3), 0)] },
508	+	Segment::Lines(vec![(h(1), 1)]),
509	+	]
510	+	);
511	+	let t = text(&g, &m);
512	+	assert!(t.contains("-------\na\n======="), "{t}");
513	+	assert!(t.contains("after-a\n>>>>>>>"), "{t}");
514	+
515	+	// If the deleter saw the insert (depends on 3), there is no conflict.
516	+	let deps = Deps([(h(2), vec![h(1), h(3)]), (h(3), vec![h(1)])].into_iter().collect());
517	+	let m = g.materialize(&deps);
518	+	assert!(!m.is_conflicted());
519	+	assert_eq!(text(&g, &m), "after-a\nb\n");
520	+	}
521	+
522	+	#[test]
523	+	fn resolution_collapses_a_conflict() {
524	+	let mut g = FileGraph::new();
525	+	g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n"]));
526	+	g.insert(h(2), 0, Vertex::Start, Vertex::Atom((h(1), 0)), &lines(&["x\n"]));
527	+	g.insert(h(3), 0, Vertex::Start, Vertex::Atom((h(1), 0)), &lines(&["y\n"]));
528	+	let mut deps: HashMap<_, _> = [(h(2), vec![h(1)]), (h(3), vec![h(1)])].into_iter().collect();
529	+	assert!(g.materialize(&Deps(deps.clone())).is_conflicted());
530	+	// Resolution keeps y, drops x.
531	+	g.delete(h(4), &AtomRange { change: h(2), from: 0, to: 1 });
532	+	deps.insert(h(4), vec![h(2), h(3)]);
533	+	let m = g.materialize(&Deps(deps));
534	+	assert!(!m.is_conflicted());
535	+	assert_eq!(text(&g, &m), "y\na\n");
536	+	}
537	+
538	+	#[test]
539	+	fn empty_and_unterminated_files() {
540	+	let g = FileGraph::new();
541	+	let m = g.materialize(&NoDeps);
542	+	assert_eq!(m.segments, vec![]);
543	+	assert_eq!(text(&g, &m), "");
544	+	let mut g = FileGraph::new();
545	+	g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["no newline"]));
546	+	assert_eq!(text(&g, &g.materialize(&NoDeps)), "no newline");
547	+	}
548	+
549	+	/// Spec §7.3: the graph is a function of the set of changes, not their order.
550	+	#[test]
551	+	fn application_order_is_irrelevant() {
552	+	use rand::seq::SliceRandom;
553	+	type Op = (ChangeHash, Vec<(u32, Vertex, Vertex, Vec<Vec<u8>>)>, Vec<AtomRange>);
554	+	let ops: Vec<Op> = vec![
555	+	(h(1), vec![(0, Vertex::Start, Vertex::End, lines(&["a\n", "b\n", "c\n"]))], vec![]),
556	+	(h(2), vec![(0, Vertex::Atom((h(1), 0)), Vertex::Atom((h(1), 1)), lines(&["p\n"]))], vec![]),
557	+	(h(3), vec![(0, Vertex::Atom((h(1), 0)), Vertex::Atom((h(1), 1)), lines(&["q\n", "r\n"]))], vec![AtomRange { change: h(1), from: 2, to: 3 }]),
558	+	(h(4), vec![(0, Vertex::Atom((h(3), 1)), Vertex::Atom((h(1), 1)), lines(&["s\n"]))], vec![AtomRange { change: h(1), from: 1, to: 2 }]),
559	+	(h(5), vec![(0, Vertex::Atom((h(1), 2)), Vertex::End, lines(&["z\n"]))], vec![]),
560	+	];
561	+	let deps = Deps(
562	+	[(h(2), vec![h(1)]), (h(3), vec![h(1)]), (h(4), vec![h(3), h(1)]), (h(5), vec![h(1)])].into_iter().collect(),
563	+	);
564	+	let build = \|order: &[usize]\| {
565	+	let mut g = FileGraph::new();
566	+	for &i in order {
567	+	let (c, ins, dels) = &ops[i];
568	+	for (idx, a, b, l) in ins {
569	+	g.insert(c, idx, a, b, l);
570	+	}
571	+	for d in dels {
572	+	g.delete(*c, d);
573	+	}
574	+	}
575	+	let m = g.materialize(&deps);
576	+	(m.clone(), text(&g, &m))
577	+	};
578	+	let reference = build(&[0, 1, 2, 3, 4]);
579	+	assert!(reference.0.is_conflicted());
580	+	let mut rng = rand::thread_rng();
581	+	let mut order: Vec<usize> = (0..ops.len()).collect();
582	+	for _ in 0..50 {
583	+	order.shuffle(&mut rng);
584	+	assert_eq!(build(&order), reference, "order {order:?}");
585	+	}
586	+	}
587	+	}

1	+	//! Random 128-bit identifiers: ChangeId, NodeId, WorkspaceId (spec §6.3, §7.1, §12.2).
2	+
3	+	use rand::RngCore;
4	+	use std::fmt;
5	+
6	+	macro_rules! id128 {
7	+	($name:ident, $doc:literal) => {
8	+	#[doc = $doc]
9	+	#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
10	+	pub struct $name(pub [u8; 16]);
11	+
12	+	impl $name {
13	+	pub const ZERO: $name = $name([0; 16]);
14	+
15	+	/// A fresh identifier from the OS CSPRNG.
16	+	pub fn random() -> $name {
17	+	let mut b = [0u8; 16];
18	+	rand::rngs::OsRng.fill_bytes(&mut b);
19	+	$name(b)
20	+	}
21	+	pub fn to_hex(&self) -> String {
22	+	hex::encode(self.0)
23	+	}
24	+	pub fn from_hex(s: &str) -> Option<$name> {
25	+	let v = hex::decode(s).ok()?;
26	+	Some($name(v.try_into().ok()?))
27	+	}
28	+	pub fn from_slice(b: &[u8]) -> Option<$name> {
29	+	Some($name(b.try_into().ok()?))
30	+	}
31	+	pub fn short(&self, n: usize) -> String {
32	+	let h = self.to_hex();
33	+	h[..n.min(h.len())].to_string()
34	+	}
35	+	pub fn starts_with_hex(&self, prefix: &str) -> bool {
36	+	self.to_hex().starts_with(prefix)
37	+	}
38	+	}
39	+
40	+	impl fmt::Display for $name {
41	+	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
42	+	f.write_str(&self.to_hex())
43	+	}
44	+	}
45	+	impl fmt::Debug for $name {
46	+	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
47	+	write!(f, "{}({})", stringify!($name), self.short(8))
48	+	}
49	+	}
50	+	};
51	+	}
52	+
53	+	id128!(ChangeId, "Stable identity of a change across rewrites (spec §6.2).");
54	+	id128!(NodeId, "Stable identity of a file, directory, or symlink across renames (spec §7.1). `NodeId::ZERO` is the root directory.");
55	+	id128!(WorkspaceId, "Identity of a checkout directory (spec §12.2).");
56	+
57	+	impl NodeId {
58	+	pub const ROOT: NodeId = NodeId::ZERO;
59	+	pub fn is_root(&self) -> bool {
60	+	self.is_zero()
61	+	}
62	+	}
63	+
64	+	impl ChangeId {
65	+	pub fn is_zero(&self) -> bool {
66	+	*self == Self::ZERO
67	+	}
68	+	}
69	+	impl NodeId {
70	+	pub fn is_zero(&self) -> bool {
71	+	*self == Self::ZERO
72	+	}
73	+	}
74	+	impl WorkspaceId {
75	+	pub fn is_zero(&self) -> bool {
76	+	*self == Self::ZERO
77	+	}
78	+	}
79	+
80	+	#[cfg(test)]
81	+	mod tests {
82	+	use super::*;
83	+
84	+	#[test]
85	+	fn random_ids_differ_and_round_trip() {
86	+	let a = ChangeId::random();
87	+	let b = ChangeId::random();
88	+	assert_ne!(a, b);
89	+	assert_eq!(ChangeId::from_hex(&a.to_hex()), Some(a));
90	+	assert!(NodeId::ROOT.is_root());
91	+	assert!(!NodeId::random().is_root());
92	+	}
93	+	}

1	+	//! Operation log objects (spec §12.1): every mutation of local repository
2	+	//! state records an `Op` whose `view` is the complete set of references and
3	+	//! workspaces afterwards.
4	+	//!
5	+	//! Encoding: `bookmarks` is an array of `[name, [heads]]` sorted by name and
6	+	//! `workspaces` an array of `[workspace_id, change_hash]` sorted by id, since
7	+	//! canonical maps carry only integer keys.
8	+
9	+	use crate::cbor::{self, Value};
10	+	use crate::hash::{hash_object, ChangeHash, ObjectRef, ObjectType};
11	+	use crate::ids::WorkspaceId;
12	+	use crate::objects::{array, bytes, check_version, field, oref, text, Hlc, ObjectError, FORMAT_VERSION};
13	+	use std::collections::BTreeMap;
14	+
15	+	#[derive(Clone, Debug, Default, PartialEq, Eq)]
16	+	pub struct View {
17	+	pub bookmarks: BTreeMap<String, Vec<ChangeHash>>,
18	+	pub workspaces: BTreeMap<WorkspaceId, ChangeHash>,
19	+	}
20	+
21	+	#[derive(Clone, Debug, PartialEq, Eq)]
22	+	pub struct Op {
23	+	pub parents: Vec<ObjectRef>,
24	+	pub hlc: Hlc,
25	+	pub command: String,
26	+	pub view: View,
27	+	}
28	+
29	+	impl View {
30	+	fn to_value(&self) -> Value {
31	+	Value::map([
32	+	(
33	+	0,
34	+	Value::Array(
35	+	self.bookmarks
36	+	.iter()
37	+	.map(\|(n, hs)\| {
38	+	Value::Array(vec![
39	+	Value::Text(n.clone()),
40	+	Value::Array(hs.iter().map(\|h\| Value::Bytes(h.0.to_vec())).collect()),
41	+	])
42	+	})
43	+	.collect(),
44	+	),
45	+	),
46	+	(
47	+	1,
48	+	Value::Array(
49	+	self.workspaces
50	+	.iter()
51	+	.map(\|(w, h)\| Value::Array(vec![Value::Bytes(w.0.to_vec()), Value::Bytes(h.0.to_vec())]))
52	+	.collect(),
53	+	),
54	+	),
55	+	])
56	+	}
57	+
58	+	fn from_value(v: &Value) -> Result<View, ObjectError> {
59	+	let m = v.as_map().ok_or_else(\|\| ObjectError::Schema("view: expected map".into()))?;
60	+	let mut view = View::default();
61	+	for b in array(field(m, 0, "bookmarks")?, "bookmarks")? {
62	+	let pair = array(b, "bookmark")?;
63	+	if pair.len() != 2 {
64	+	return Err(ObjectError::Schema("bookmark: expected [name, heads]".into()));
65	+	}
66	+	let name = text(&pair[0], "bookmark name")?.to_owned();
67	+	let mut heads = array(&pair[1], "heads")?.iter().map(\|h\| oref(h, "head")).collect::<Result<Vec<_>, _>>()?;
68	+	heads.sort();
69	+	heads.dedup();
70	+	view.bookmarks.insert(name, heads);
71	+	}
72	+	for w in array(field(m, 1, "workspaces")?, "workspaces")? {
73	+	let pair = array(w, "workspace")?;
74	+	if pair.len() != 2 {
75	+	return Err(ObjectError::Schema("workspace: expected [id, change]".into()));
76	+	}
77	+	let id = WorkspaceId::from_slice(bytes(&pair[0], "workspace id")?)
78	+	.ok_or_else(\|\| ObjectError::Schema("workspace id: expected 16 bytes".into()))?;
79	+	view.workspaces.insert(id, oref(&pair[1], "workspace change")?);
80	+	}
81	+	Ok(view)
82	+	}
83	+	}
84	+
85	+	impl Op {
86	+	pub fn to_value(&self) -> Value {
87	+	Value::map([
88	+	(0, Value::Uint(FORMAT_VERSION)),
89	+	(1, Value::Array(self.parents.iter().map(\|p\| Value::Bytes(p.0.to_vec())).collect())),
90	+	(2, self.hlc.to_value()),
91	+	(3, Value::Text(self.command.clone())),
92	+	(4, self.view.to_value()),
93	+	])
94	+	}
95	+	pub fn encode(&self) -> Vec<u8> {
96	+	cbor::encode(&self.to_value())
97	+	}
98	+	pub fn hash(&self) -> ObjectRef {
99	+	hash_object(ObjectType::Op, &self.encode())
100	+	}
101	+	pub fn decode(b: &[u8]) -> Result<Op, ObjectError> {
102	+	let v = cbor::decode(b)?;
103	+	let m = v.as_map().ok_or_else(\|\| ObjectError::Schema("op: expected map".into()))?;
104	+	check_version(m)?;
105	+	Ok(Op {
106	+	parents: array(field(m, 1, "parents")?, "parents")?.iter().map(\|p\| oref(p, "parent")).collect::<Result<Vec<_>, _>>()?,
107	+	hlc: Hlc::from_value(field(m, 2, "hlc")?)?,
108	+	command: text(field(m, 3, "command")?, "command")?.to_owned(),
109	+	view: View::from_value(field(m, 4, "view")?)?,
110	+	})
111	+	}
112	+	}
113	+
114	+	#[cfg(test)]
115	+	mod tests {
116	+	use super::*;
117	+
118	+	#[test]
119	+	fn op_round_trip() {
120	+	let mut view = View::default();
121	+	view.bookmarks.insert("main".into(), vec![ObjectRef([2; 32]), ObjectRef([1; 32])]);
122	+	view.bookmarks.insert("dev".into(), vec![]);
123	+	view.workspaces.insert(WorkspaceId([5; 16]), ObjectRef([9; 32]));
124	+	let op = Op { parents: vec![ObjectRef([7; 32])], hlc: Hlc { wall_ms: 5, logical: 1 }, command: "oxy commit".into(), view };
125	+	let d = Op::decode(&op.encode()).unwrap();
126	+	// Heads are normalized to sorted order on decode.
127	+	assert_eq!(d.view.bookmarks["main"], vec![ObjectRef([1; 32]), ObjectRef([2; 32])]);
128	+	assert_eq!(d.command, op.command);
129	+	assert_eq!(d.parents, op.parents);
130	+	assert_eq!(d.hash(), Op::decode(&d.encode()).unwrap().hash());
131	+	}
132	+	}

1	+	//! A state: a dependency-closed set of changes, applied to a tree graph and
2	+	//! per-node file graphs (spec §8.3), with materialization (spec §9.5, §11).
3	+
4	+	use crate::graph::{AtomKey, DepOracle, FileGraph, Materialized, Vertex};
5	+	use crate::hash::{ChangeHash, ObjectRef};
6	+	use crate::ids::NodeId;
7	+	use crate::objects::{AtomRef, Change, Edit, Mode, NodeKind, TreeOp};
8	+	use crate::tree::{TreeGraph, TreeView};
9	+	use std::cell::RefCell;
10	+	use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
11	+	use std::rc::Rc;
12	+
13	+	#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
14	+	pub enum StateError {
15	+	#[error("change {1} depends on {0}, which is not in the state")]
16	+	MissingDep(ChangeHash, ChangeHash),
17	+	}
18	+
19	+	#[derive(Default)]
20	+	pub struct State {
21	+	changes: HashMap<ChangeHash, Change>,
22	+	tree: TreeGraph,
23	+	files: HashMap<NodeId, FileGraph>,
24	+	replaces: HashMap<NodeId, Vec<(ChangeHash, Option<ObjectRef>, Option<ObjectRef>)>>,
25	+	closure: RefCell<HashMap<ChangeHash, Rc<HashSet<ChangeHash>>>>,
26	+	}
27	+
28	+	#[derive(Clone, Debug, PartialEq, Eq)]
29	+	pub enum FileContent {
30	+	Text { bytes: Vec<u8>, materialized: Materialized },
31	+	/// Live blobs; more than one is a replace conflict (spec §9.3).
32	+	Opaque { blobs: Vec<ObjectRef> },
33	+	Dir,
34	+	}
35	+
36	+	#[derive(Clone, Debug, PartialEq, Eq)]
37	+	pub struct FileState {
38	+	pub node: NodeId,
39	+	pub kind: NodeKind,
40	+	pub mode: Mode,
41	+	pub content: FileContent,
42	+	}
43	+
44	+	impl FileState {
45	+	pub fn is_conflicted(&self) -> bool {
46	+	match &self.content {
47	+	FileContent::Text { materialized, .. } => materialized.is_conflicted(),
48	+	FileContent::Opaque { blobs } => blobs.len() > 1,
49	+	FileContent::Dir => false,
50	+	}
51	+	}
52	+	}
53	+
54	+	/// The whole tree of a state, materialized.
55	+	#[derive(Clone, Debug, Default)]
56	+	pub struct Snapshot {
57	+	pub tree: TreeView,
58	+	pub files: BTreeMap<String, FileState>,
59	+	}
60	+
61	+	impl Snapshot {
62	+	pub fn is_conflicted(&self) -> bool {
63	+	self.tree.is_conflicted() \|\| self.files.values().any(\|f\| f.is_conflicted())
64	+	}
65	+	}
66	+
67	+	fn vertex(r: AtomRef) -> Vertex {
68	+	match r {
69	+	AtomRef::Start => Vertex::Start,
70	+	AtomRef::End => Vertex::End,
71	+	AtomRef::Atom { change, index } => Vertex::Atom((change, index)),
72	+	}
73	+	}
74	+
75	+	/// Replace self references in a tree op with the concrete change hash.
76	+	pub fn resolve_tree_op(op: &TreeOp, me: ChangeHash) -> TreeOp {
77	+	match op {
78	+	TreeOp::RemoveNode { node, placement } => TreeOp::RemoveNode { node: *node, placement: placement.resolve(me) },
79	+	TreeOp::Move { node, old, parent, name } => {
80	+	TreeOp::Move { node: node, old: old.resolve(me), parent: parent, name: name.clone() }
81	+	}
82	+	TreeOp::SetMode { node, old, mode } => TreeOp::SetMode { node: node, old: old.resolve(me), mode: mode },
83	+	add @ TreeOp::AddNode { .. } => add.clone(),
84	+	}
85	+	}
86	+
87	+	impl State {
88	+	pub fn new() -> Self {
89	+	Self::default()
90	+	}
91	+
92	+	pub fn len(&self) -> usize {
93	+	self.changes.len()
94	+	}
95	+	pub fn is_empty(&self) -> bool {
96	+	self.changes.is_empty()
97	+	}
98	+	pub fn contains(&self, h: &ChangeHash) -> bool {
99	+	self.changes.contains_key(h)
100	+	}
101	+	pub fn get(&self, h: &ChangeHash) -> Option<&Change> {
102	+	self.changes.get(h)
103	+	}
104	+	pub fn changes(&self) -> impl Iterator<Item = (&ChangeHash, &Change)> {
105	+	self.changes.iter()
106	+	}
107	+	pub fn tree(&self) -> &TreeGraph {
108	+	&self.tree
109	+	}
110	+	pub fn file(&self, node: &NodeId) -> Option<&FileGraph> {
111	+	self.files.get(node)
112	+	}
113	+
114	+	/// Add a change whose dependencies are already present.
115	+	pub fn add(&mut self, change: Change) -> Result<ChangeHash, StateError> {
116	+	let h = change.hash();
117	+	if self.changes.contains_key(&h) {
118	+	return Ok(h);
119	+	}
120	+	for d in &change.deps {
121	+	if !self.changes.contains_key(d) {
122	+	return Err(StateError::MissingDep(*d, h));
123	+	}
124	+	}
125	+	Ok(self.add_unchecked(change))
126	+	}
127	+
128	+	/// Add a change in any order; call `validate` once all are in.
129	+	pub fn add_unchecked(&mut self, change: Change) -> ChangeHash {
130	+	let h = change.hash();
131	+	if self.changes.contains_key(&h) {
132	+	return h;
133	+	}
134	+	self.apply(h, &change);
135	+	self.changes.insert(h, change);
136	+	self.closure.borrow_mut().clear();
137	+	h
138	+	}
139	+
140	+	pub fn validate(&self) -> Result<(), StateError> {
141	+	for (h, c) in &self.changes {
142	+	for d in &c.deps {
143	+	if !self.changes.contains_key(d) {
144	+	return Err(StateError::MissingDep(d, h));
145	+	}
146	+	}
147	+	}
148	+	Ok(())
149	+	}
150	+
151	+	fn apply(&mut self, h: ChangeHash, c: &Change) {
152	+	for (i, op) in c.tree_ops.iter().enumerate() {
153	+	self.tree.apply(h, i as u32, &resolve_tree_op(op, h));
154	+	}
155	+	let mut counters: HashMap<NodeId, u32> = HashMap::new();
156	+	for e in &c.edits {
157	+	match e {
158	+	Edit::Insert { node, after, before, lines } => {
159	+	let idx = counters.entry(*node).or_default();
160	+	let first = *idx;
161	+	*idx += lines.len() as u32;
162	+	self.files.entry(*node).or_default().insert(h, first, vertex(after.resolve(h)), vertex(before.resolve(h)), lines);
163	+	}
164	+	Edit::Delete { node, atoms } => {
165	+	let g = self.files.entry(*node).or_default();
166	+	for r in atoms {
167	+	g.delete(h, &r.resolve(h));
168	+	}
169	+	}
170	+	Edit::Replace { node, old, new } => {
171	+	self.replaces.entry(node).or_default().push((h, old, *new));
172	+	}
173	+	}
174	+	}
175	+	}
176	+
177	+	/// Transitive dependencies of `h`, excluding `h` itself.
178	+	pub fn closure(&self, h: &ChangeHash) -> Rc<HashSet<ChangeHash>> {
179	+	if let Some(c) = self.closure.borrow().get(h) {
180	+	return c.clone();
181	+	}
182	+	let mut out = HashSet::new();
183	+	let mut stack: Vec<ChangeHash> = self.changes.get(h).map(\|c\| c.deps.clone()).unwrap_or_default();
184	+	while let Some(d) = stack.pop() {
185	+	if out.insert(d) {
186	+	if let Some(c) = self.changes.get(&d) {
187	+	stack.extend(c.deps.iter().copied());
188	+	}
189	+	}
190	+	}
191	+	let rc = Rc::new(out);
192	+	self.closure.borrow_mut().insert(*h, rc.clone());
193	+	rc
194	+	}
195	+
196	+	/// Changes that no other change depends on directly, sorted.
197	+	pub fn heads(&self) -> Vec<ChangeHash> {
198	+	let depended: HashSet<&ChangeHash> = self.changes.values().flat_map(\|c\| c.deps.iter()).collect();
199	+	let mut heads: Vec<ChangeHash> = self.changes.keys().filter(\|h\| !depended.contains(h)).copied().collect();
200	+	heads.sort();
201	+	heads
202	+	}
203	+
204	+	/// Maximal elements among `hashes` (those not in the closure of another).
205	+	pub fn maximal(&self, hashes: &[ChangeHash]) -> Vec<ChangeHash> {
206	+	let set: BTreeSet<ChangeHash> = hashes.iter().copied().collect();
207	+	set.iter().filter(\|h\| !set.iter().any(\|o\| o != *h && self.closure(o).contains(h))).copied().collect()
208	+	}
209	+
210	+	pub fn materialize_file(&self, node: &NodeId) -> Materialized {
211	+	self.files.get(node).map(\|g\| g.materialize(self)).unwrap_or_default()
212	+	}
213	+
214	+	/// Live lines of a text node in materialized order.
215	+	pub fn live_lines(&self, node: &NodeId) -> Vec<(AtomKey, Vec<u8>)> {
216	+	let Some(g) = self.files.get(node) else { return vec![] };
217	+	let m = g.materialize(self);
218	+	m.live_atoms().into_iter().map(\|a\| (a, g.content(&a).unwrap_or_default().to_vec())).collect()
219	+	}
220	+
221	+	/// Live blobs of an opaque node: every `new` that no later `Replace` retired.
222	+	pub fn live_blobs(&self, node: &NodeId) -> Vec<ObjectRef> {
223	+	let Some(rs) = self.replaces.get(node) else { return vec![] };
224	+	let olds: HashSet<ObjectRef> = rs.iter().filter_map(\|(_, o, _)\| *o).collect();
225	+	let mut live: Vec<ObjectRef> = rs.iter().filter_map(\|(_, _, n)\| *n).filter(\|n\| !olds.contains(n)).collect();
226	+	live.sort();
227	+	live.dedup();
228	+	live
229	+	}
230	+
231	+	/// Short label for conflict markers: `changeid-prefix "message"`.
232	+	pub fn label(&self, h: &ChangeHash) -> String {
233	+	match self.changes.get(h) {
234	+	Some(c) => format!("{} \"{}\"", c.change_id.short(8), c.message.lines().next().unwrap_or("")),
235	+	None => format!("#{}", h.short(12)),
236	+	}
237	+	}
238	+
239	+	pub fn render_file(&self, node: &NodeId) -> (Vec<u8>, Materialized) {
240	+	let Some(g) = self.files.get(node) else { return (Vec::new(), Materialized::default()) };
241	+	let m = g.materialize(self);
242	+	let bytes = g.render(&m, &\|h\| self.label(h));
243	+	(bytes, m)
244	+	}
245	+
246	+	pub fn materialize(&self) -> Snapshot {
247	+	let tree = self.tree.view();
248	+	let mut files = BTreeMap::new();
249	+	for (path, e) in &tree.entries {
250	+	let content = match e.kind {
251	+	NodeKind::Dir => FileContent::Dir,
252	+	NodeKind::Symlink => FileContent::Opaque { blobs: self.live_blobs(&e.node) },
253	+	NodeKind::File if e.mode.opaque => FileContent::Opaque { blobs: self.live_blobs(&e.node) },
254	+	NodeKind::File => {
255	+	let (bytes, materialized) = self.render_file(&e.node);
256	+	FileContent::Text { bytes, materialized }
257	+	}
258	+	};
259	+	files.insert(path.clone(), FileState { node: e.node, kind: e.kind, mode: e.mode, content });
260	+	}
261	+	Snapshot { tree, files }
262	+	}
263	+	}
264	+
265	+	impl DepOracle for State {
266	+	fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool {
267	+	a == b \|\| self.closure(a).contains(b)
268	+	}
269	+	}
270	+
271	+	#[cfg(test)]
272	+	mod tests {
273	+	use super::*;
274	+	use crate::ids::ChangeId;
275	+	use crate::objects::{AtomRange, ChangeKind, Hlc, OpRef};
276	+
277	+	fn change(deps: Vec<ChangeHash>, tree_ops: Vec<TreeOp>, edits: Vec<Edit>) -> Change {
278	+	let mut c = Change {
279	+	change_id: ChangeId::random(),
280	+	deps,
281	+	author: ObjectRef::ZERO,
282	+	hlc: Hlc { wall_ms: 1, logical: 0 },
283	+	message: "m".into(),
284	+	tree_ops,
285	+	edits,
286	+	kind: ChangeKind::Normal,
287	+	};
288	+	c.normalize();
289	+	c
290	+	}
291	+
292	+	#[test]
293	+	fn build_edit_and_materialize() {
294	+	let mut st = State::new();
295	+	let f = NodeId::random();
296	+	let c1 = change(
297	+	vec![],
298	+	vec![TreeOp::AddNode { node: f, kind: NodeKind::File, mode: Mode::TEXT, parent: NodeId::ROOT, name: "a.txt".into() }],
299	+	vec![Edit::Insert { node: f, after: AtomRef::Start, before: AtomRef::End, lines: vec![b"one\n".to_vec(), b"two\n".to_vec()] }],
300	+	);
301	+	let h1 = st.add(c1).unwrap();
302	+	// Depends on h1: append a line and delete "one".
303	+	let c2 = change(
304	+	vec![h1],
305	+	vec![],
306	+	vec![
307	+	Edit::Delete { node: f, atoms: vec![AtomRange { change: h1, from: 0, to: 1 }] },
308	+	Edit::Insert { node: f, after: AtomRef::Atom { change: h1, index: 1 }, before: AtomRef::End, lines: vec![b"three\n".to_vec()] },
309	+	],
310	+	);
311	+	let h2 = st.add(c2).unwrap();
312	+	assert_eq!(st.heads(), vec![h2]);
313	+	assert!(st.depends_on(&h2, &h1));
314	+	assert!(!st.depends_on(&h1, &h2));
315	+	let snap = st.materialize();
316	+	assert!(!snap.is_conflicted());
317	+	let a = &snap.files["a.txt"];
318	+	assert!(matches!(&a.content, FileContent::Text { bytes, .. } if bytes == b"two\nthree\n"));
319	+	assert_eq!(st.live_lines(&f).len(), 2);
320	+	}
321	+
322	+	#[test]
323	+	fn missing_dependency_is_rejected() {
324	+	let mut st = State::new();
325	+	let c = change(vec![ObjectRef([1; 32])], vec![], vec![]);
326	+	assert!(matches!(st.add(c), Err(StateError::MissingDep(..))));
327	+	}
328	+
329	+	#[test]
330	+	fn self_references_and_multi_insert_indexing() {
331	+	let mut st = State::new();
332	+	let f = NodeId::random();
333	+	let me = OpRef { change: ObjectRef::ZERO, index: 0 };
334	+	let c1 = change(
335	+	vec![],
336	+	vec![
337	+	TreeOp::AddNode { node: f, kind: NodeKind::File, mode: Mode::TEXT, parent: NodeId::ROOT, name: "x".into() },
338	+	TreeOp::SetMode { node: f, old: me, mode: Mode { exec: true, opaque: false } },
339	+	],
340	+	vec![
341	+	Edit::Insert { node: f, after: AtomRef::Start, before: AtomRef::End, lines: vec![b"a\n".to_vec(), b"c\n".to_vec()] },
342	+	// Insert between the two lines just inserted, using self references.
343	+	Edit::Insert {
344	+	node: f,
345	+	after: AtomRef::Atom { change: ObjectRef::ZERO, index: 0 },
346	+	before: AtomRef::Atom { change: ObjectRef::ZERO, index: 1 },
347	+	lines: vec![b"b\n".to_vec()],
348	+	},
349	+	],
350	+	);
351	+	st.add(c1).unwrap();
352	+	let snap = st.materialize();
353	+	let x = &snap.files["x"];
354	+	assert_eq!(x.mode, Mode { exec: true, opaque: false });
355	+	assert!(matches!(&x.content, FileContent::Text { bytes, .. } if bytes == b"a\nb\nc\n"));
356	+	}
357	+
358	+	#[test]
359	+	fn opaque_replace_and_conflict() {
360	+	let mut st = State::new();
361	+	let f = NodeId::random();
362	+	let b1 = ObjectRef([1; 32]);
363	+	let b2 = ObjectRef([2; 32]);
364	+	let b3 = ObjectRef([3; 32]);
365	+	let h1 = st.add(change(
366	+	vec![],
367	+	vec![TreeOp::AddNode { node: f, kind: NodeKind::File, mode: Mode::OPAQUE, parent: NodeId::ROOT, name: "img".into() }],
368	+	vec![Edit::Replace { node: f, old: None, new: Some(b1) }],
369	+	))
370	+	.unwrap();
371	+	assert_eq!(st.live_blobs(&f), vec![b1]);
372	+	st.add(change(vec![h1], vec![], vec![Edit::Replace { node: f, old: Some(b1), new: Some(b2) }])).unwrap();
373	+	st.add(change(vec![h1], vec![], vec![Edit::Replace { node: f, old: Some(b1), new: Some(b3) }])).unwrap();
374	+	let snap = st.materialize();
375	+	assert!(snap.is_conflicted());
376	+	assert!(matches!(&snap.files["img"].content, FileContent::Opaque { blobs } if blobs == &vec![b2, b3]));
377	+	}
378	+
379	+	#[test]
380	+	fn maximal_elements() {
381	+	let mut st = State::new();
382	+	let h1 = st.add(change(vec![], vec![], vec![])).unwrap();
383	+	let h2 = st.add(change(vec![h1], vec![], vec![])).unwrap();
384	+	let h3 = st.add(change(vec![], vec![], vec![])).unwrap();
385	+	let mut m = st.maximal(&[h1, h2, h3]);
386	+	m.sort();
387	+	let mut want = vec![h2, h3];
388	+	want.sort();
389	+	assert_eq!(m, want);
390	+	assert_eq!(st.heads(), want);
391	+	}
392	+	}

1	+	//! Loose object store (spec §13.1): one file per object under
2	+	//! `objects/loose/<hh>/<rest>`, written atomically and verified on read.
3	+	//! Packs come later.
4	+
5	+	use crate::hash::{hash_object, header, ObjectRef, ObjectType};
6	+	use crate::objects::{Change, ObjectError};
7	+	use rand::RngCore;
8	+	use std::fs;
9	+	use std::io::{self, Write};
10	+	use std::path::{Path, PathBuf};
11	+
12	+	#[derive(Debug, thiserror::Error)]
13	+	pub enum StoreError {
14	+	#[error("io: {0}")]
15	+	Io(#[from] io::Error),
16	+	#[error("corrupt object {0}: {1}")]
17	+	Corrupt(ObjectRef, String),
18	+	#[error("object {0}")]
19	+	Object(#[from] ObjectError),
20	+	#[error("object {0} is a {1}, expected {2}")]
21	+	WrongType(ObjectRef, &'static str, &'static str),
22	+	#[error("object {0} not found")]
23	+	NotFound(ObjectRef),
24	+	}
25	+
26	+	pub type Result<T> = std::result::Result<T, StoreError>;
27	+
28	+	#[derive(Debug, Clone)]
29	+	pub struct Store {
30	+	dir: PathBuf,
31	+	}
32	+
33	+	impl Store {
34	+	pub fn open(dir: impl Into<PathBuf>) -> io::Result<Store> {
35	+	let dir = dir.into();
36	+	fs::create_dir_all(dir.join("loose"))?;
37	+	Ok(Store { dir })
38	+	}
39	+
40	+	pub fn dir(&self) -> &Path {
41	+	&self.dir
42	+	}
43	+
44	+	fn path_for(&self, r: &ObjectRef) -> PathBuf {
45	+	let h = r.to_hex();
46	+	self.dir.join("loose").join(&h[..2]).join(&h[2..])
47	+	}
48	+
49	+	pub fn has(&self, r: &ObjectRef) -> bool {
50	+	self.path_for(r).is_file()
51	+	}
52	+
53	+	/// Store `body` as an object of type `ty`; idempotent.
54	+	pub fn put(&self, ty: ObjectType, body: &[u8]) -> Result<ObjectRef> {
55	+	let r = hash_object(ty, body);
56	+	let path = self.path_for(&r);
57	+	if path.is_file() {
58	+	return Ok(r);
59	+	}
60	+	fs::create_dir_all(path.parent().unwrap())?;
61	+	let mut nonce = [0u8; 8];
62	+	rand::rngs::OsRng.fill_bytes(&mut nonce);
63	+	let tmp = self.dir.join("loose").join(format!("tmp-{}", hex::encode(nonce)));
64	+	{
65	+	let mut f = fs::File::create(&tmp)?;
66	+	f.write_all(&header(ty, body.len()))?;
67	+	f.write_all(body)?;
68	+	f.sync_all()?;
69	+	}
70	+	fs::rename(&tmp, &path)?;
71	+	Ok(r)
72	+	}
73	+
74	+	/// Read and verify an object.
75	+	pub fn get(&self, r: &ObjectRef) -> Result<(ObjectType, Vec<u8>)> {
76	+	let path = self.path_for(r);
77	+	let data = match fs::read(&path) {
78	+	Ok(d) => d,
79	+	Err(e) if e.kind() == io::ErrorKind::NotFound => return Err(StoreError::NotFound(*r)),
80	+	Err(e) => return Err(e.into()),
81	+	};
82	+	let nul = data.iter().position(\|&b\| b == 0).ok_or_else(\|\| StoreError::Corrupt(*r, "no header".into()))?;
83	+	let head = std::str::from_utf8(&data[..nul]).map_err(\|_\| StoreError::Corrupt(*r, "header not UTF-8".into()))?;
84	+	let mut parts = head.split(' ');
85	+	let (Some("oxy1"), Some(ty), Some(len), None) = (parts.next(), parts.next(), parts.next(), parts.next()) else {
86	+	return Err(StoreError::Corrupt(*r, format!("bad header {head:?}")));
87	+	};
88	+	let ty = ObjectType::from_name(ty).ok_or_else(\|\| StoreError::Corrupt(*r, format!("unknown type {ty}")))?;
89	+	let len: usize = len.parse().map_err(\|_\| StoreError::Corrupt(*r, "bad length".into()))?;
90	+	let body = &data[nul + 1..];
91	+	if body.len() != len {
92	+	return Err(StoreError::Corrupt(*r, format!("length {} != header {len}", body.len())));
93	+	}
94	+	if hash_object(ty, body) != *r {
95	+	return Err(StoreError::Corrupt(*r, "hash mismatch".into()));
96	+	}
97	+	Ok((ty, body.to_vec()))
98	+	}
99	+
100	+	pub fn get_typed(&self, r: &ObjectRef, want: ObjectType) -> Result<Vec<u8>> {
101	+	let (ty, body) = self.get(r)?;
102	+	if ty != want {
103	+	return Err(StoreError::WrongType(*r, ty.name(), want.name()));
104	+	}
105	+	Ok(body)
106	+	}
107	+
108	+	pub fn put_change(&self, c: &Change) -> Result<ObjectRef> {
109	+	self.put(ObjectType::Change, &c.encode())
110	+	}
111	+
112	+	pub fn get_change(&self, r: &ObjectRef) -> Result<Change> {
113	+	Ok(Change::decode(&self.get_typed(r, ObjectType::Change)?)?)
114	+	}
115	+
116	+	pub fn put_chunk(&self, bytes: &[u8]) -> Result<ObjectRef> {
117	+	self.put(ObjectType::Chunk, bytes)
118	+	}
119	+
120	+	/// Every object reference in the store (slow; for gc and tests).
121	+	pub fn list(&self) -> io::Result<Vec<ObjectRef>> {
122	+	let mut out = Vec::new();
123	+	let loose = self.dir.join("loose");
124	+	for d in fs::read_dir(&loose)? {
125	+	let d = d?;
126	+	if !d.file_type()?.is_dir() {
127	+	continue;
128	+	}
129	+	let prefix = d.file_name().to_string_lossy().to_string();
130	+	for f in fs::read_dir(d.path())? {
131	+	let f = f?;
132	+	let name = f.file_name().to_string_lossy().to_string();
133	+	if let Some(r) = ObjectRef::from_hex(&format!("{prefix}{name}")) {
134	+	out.push(r);
135	+	}
136	+	}
137	+	}
138	+	out.sort();
139	+	Ok(out)
140	+	}
141	+	}
142	+
143	+	#[cfg(test)]
144	+	mod tests {
145	+	use super::*;
146	+
147	+	#[test]
148	+	fn put_get_verify() {
149	+	let dir = tempfile::tempdir().unwrap();
150	+	let s = Store::open(dir.path().join("objects")).unwrap();
151	+	let r = s.put(ObjectType::Chunk, b"hello").unwrap();
152	+	assert!(s.has(&r));
153	+	assert_eq!(s.get(&r).unwrap(), (ObjectType::Chunk, b"hello".to_vec()));
154	+	assert_eq!(s.put(ObjectType::Chunk, b"hello").unwrap(), r);
155	+	assert_eq!(s.list().unwrap(), vec![r]);
156	+	assert!(matches!(s.get_typed(&r, ObjectType::Blob), Err(StoreError::WrongType(..))));
157	+	assert!(matches!(s.get(&ObjectRef([9; 32])), Err(StoreError::NotFound(_))));
158	+
159	+	// Tamper: flip a byte, read must fail.
160	+	let path = s.path_for(&r);
161	+	let mut data = fs::read(&path).unwrap();
162	+	let last = data.len() - 1;
163	+	data[last] ^= 1;
164	+	fs::write(&path, data).unwrap();
165	+	assert!(matches!(s.get(&r), Err(StoreError::Corrupt(..))));
166	+	}
167	+
168	+	#[test]
169	+	fn change_round_trip_through_store() {
170	+	let dir = tempfile::tempdir().unwrap();
171	+	let s = Store::open(dir.path()).unwrap();
172	+	let c = crate::objects::tests::sample_change();
173	+	let r = s.put_change(&c).unwrap();
174	+	assert_eq!(r, c.hash());
175	+	assert_eq!(s.get_change(&r).unwrap(), c);
176	+	}
177	+	}

1	+	//! The tree graph: nodes, placements, and modes as atoms (spec §7.1, §7.2),
2	+	//! with tree conflict detection and path assignment (spec §9.2).
3	+
4	+	use crate::hash::ChangeHash;
5	+	use crate::ids::NodeId;
6	+	use crate::objects::{Mode, NodeKind, OpRef, TreeOp};
7	+	use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
8	+
9	+	/// `(change, index into that change's tree_ops)`.
10	+	pub type OpKey = (ChangeHash, u32);
11	+
12	+	#[derive(Clone, Debug, PartialEq, Eq)]
13	+	pub struct Placement {
14	+	pub node: NodeId,
15	+	pub parent: NodeId,
16	+	pub name: String,
17	+	}
18	+
19	+	#[derive(Clone, Debug, Default)]
20	+	pub struct TreeGraph {
21	+	kinds: HashMap<NodeId, NodeKind>,
22	+	introduced: HashMap<NodeId, ChangeHash>,
23	+	placements: HashMap<OpKey, Placement>,
24	+	modes: HashMap<OpKey, (NodeId, Mode)>,
25	+	/// Placement atoms retired by `RemoveNode`/`Move`, and mode atoms retired
26	+	/// by `SetMode`. Kept apart because `AddNode` introduces one of each
27	+	/// under the same key.
28	+	deleted_placements: HashMap<OpKey, BTreeSet<ChangeHash>>,
29	+	deleted_modes: HashMap<OpKey, BTreeSet<ChangeHash>>,
30	+	placements_of: HashMap<NodeId, BTreeSet<OpKey>>,
31	+	modes_of: HashMap<NodeId, BTreeSet<OpKey>>,
32	+	}
33	+
34	+	#[derive(Clone, Debug, PartialEq, Eq)]
35	+	pub enum TreeConflict {
36	+	/// Two live nodes share `(parent, name)`.
37	+	Name { parent: NodeId, name: String, nodes: Vec<NodeId> },
38	+	/// One node has several live placements.
39	+	MultiPlacement { node: NodeId, placements: Vec<OpKey> },
40	+	/// A live node's parent is not live.
41	+	Orphan { node: NodeId, parent: NodeId },
42	+	/// A directory is placed inside its own descendant.
43	+	Cycle { node: NodeId },
44	+	/// Several live mode atoms.
45	+	Mode { node: NodeId, modes: Vec<Mode> },
46	+	}
47	+
48	+	/// A node as it appears in the working copy.
49	+	#[derive(Clone, Debug, PartialEq, Eq)]
50	+	pub struct TreeEntry {
51	+	pub path: String,
52	+	pub node: NodeId,
53	+	pub kind: NodeKind,
54	+	pub mode: Mode,
55	+	/// The placement this entry materializes (for building `RemoveNode`/`Move`).
56	+	pub placement: OpKey,
57	+	/// The live mode atom (for building `SetMode`).
58	+	pub mode_atom: Option<OpKey>,
59	+	}
60	+
61	+	#[derive(Clone, Debug, Default, PartialEq, Eq)]
62	+	pub struct TreeView {
63	+	/// Path → entry, paths use `/` and have no leading slash; conflicted
64	+	/// entries carry a `.oxy-conflict-<n>` suffix.
65	+	pub entries: BTreeMap<String, TreeEntry>,
66	+	pub conflicts: Vec<TreeConflict>,
67	+	}
68	+
69	+	impl TreeView {
70	+	pub fn is_conflicted(&self) -> bool {
71	+	!self.conflicts.is_empty()
72	+	}
73	+	pub fn by_node(&self) -> HashMap<NodeId, &TreeEntry> {
74	+	self.entries.values().map(\|e\| (e.node, e)).collect()
75	+	}
76	+	}
77	+
78	+	impl TreeGraph {
79	+	pub fn new() -> Self {
80	+	Self::default()
81	+	}
82	+
83	+	/// Apply tree op `index` of `change`; `OpRef` self references must already be resolved.
84	+	pub fn apply(&mut self, change: ChangeHash, index: u32, op: &TreeOp) {
85	+	let key = (change, index);
86	+	match op {
87	+	TreeOp::AddNode { node, kind, mode, parent, name } => {
88	+	self.kinds.insert(node, kind);
89	+	self.introduced.insert(*node, change);
90	+	self.placements.insert(key, Placement { node: node, parent: parent, name: name.clone() });
91	+	self.placements_of.entry(*node).or_default().insert(key);
92	+	if *kind != NodeKind::Dir {
93	+	self.modes.insert(key, (node, mode));
94	+	self.modes_of.entry(*node).or_default().insert(key);
95	+	}
96	+	}
97	+	TreeOp::RemoveNode { placement, .. } => {
98	+	self.deleted_placements.entry(op_key(*placement)).or_default().insert(change);
99	+	}
100	+	TreeOp::Move { node, old, parent, name } => {
101	+	self.deleted_placements.entry(op_key(*old)).or_default().insert(change);
102	+	self.placements.insert(key, Placement { node: node, parent: parent, name: name.clone() });
103	+	self.placements_of.entry(*node).or_default().insert(key);
104	+	}
105	+	TreeOp::SetMode { node, old, mode } => {
106	+	self.deleted_modes.entry(op_key(*old)).or_default().insert(change);
107	+	self.modes.insert(key, (node, mode));
108	+	self.modes_of.entry(*node).or_default().insert(key);
109	+	}
110	+	}
111	+	}
112	+
113	+	fn placement_live(&self, k: &OpKey) -> bool {
114	+	self.deleted_placements.get(k).is_none_or(\|d\| d.is_empty())
115	+	}
116	+	fn mode_live(&self, k: &OpKey) -> bool {
117	+	self.deleted_modes.get(k).is_none_or(\|d\| d.is_empty())
118	+	}
119	+
120	+	pub fn kind(&self, node: &NodeId) -> Option<NodeKind> {
121	+	if node.is_root() { Some(NodeKind::Dir) } else { self.kinds.get(node).copied() }
122	+	}
123	+
124	+	/// The change whose `AddNode` introduced `node`.
125	+	pub fn introducer(&self, node: &NodeId) -> Option<ChangeHash> {
126	+	self.introduced.get(node).copied()
127	+	}
128	+
129	+	pub fn placement(&self, k: &OpKey) -> Option<&Placement> {
130	+	self.placements.get(k)
131	+	}
132	+
133	+	pub fn live_placements(&self, node: &NodeId) -> Vec<(OpKey, &Placement)> {
134	+	self.placements_of
135	+	.get(node)
136	+	.into_iter()
137	+	.flat_map(\|ks\| ks.iter())
138	+	.filter(\|k\| self.placement_live(k))
139	+	.filter_map(\|k\| self.placements.get(k).map(\|p\| (*k, p)))
140	+	.collect()
141	+	}
142	+
143	+	pub fn live_modes(&self, node: &NodeId) -> Vec<(OpKey, Mode)> {
144	+	self.modes_of
145	+	.get(node)
146	+	.into_iter()
147	+	.flat_map(\|ks\| ks.iter())
148	+	.filter(\|k\| self.mode_live(k))
149	+	.filter_map(\|k\| self.modes.get(k).map(\|(_, m)\| (k, m)))
150	+	.collect()
151	+	}
152	+
153	+	/// Every node that has at least one live placement.
154	+	pub fn placed_nodes(&self) -> impl Iterator<Item = NodeId> + '_ {
155	+	self.placements_of.keys().copied().filter(\|n\| !self.live_placements(n).is_empty())
156	+	}
157	+
158	+	/// Resolve the tree: assign paths, find conflicts.
159	+	pub fn view(&self) -> TreeView {
160	+	let mut view = TreeView::default();
161	+
162	+	// Live placements grouped by parent.
163	+	let mut children: HashMap<NodeId, Vec<(OpKey, &Placement)>> = HashMap::new();
164	+	for (k, p) in &self.placements {
165	+	if self.placement_live(k) {
166	+	children.entry(p.parent).or_default().push((*k, p));
167	+	}
168	+	}
169	+	for c in children.values_mut() {
170	+	c.sort_by(\|a, b\| a.1.name.cmp(&b.1.name).then(a.0.cmp(&b.0)));
171	+	}
172	+
173	+	// Multi-placement and mode conflicts.
174	+	let mut nodes: Vec<NodeId> = self.placements_of.keys().copied().collect();
175	+	nodes.sort();
176	+	let mut multi: HashSet<NodeId> = HashSet::new();
177	+	for n in &nodes {
178	+	let lp = self.live_placements(n);
179	+	let distinct_places: BTreeSet<(&NodeId, &str)> = lp.iter().map(\|(_, p)\| (&p.parent, p.name.as_str())).collect();
180	+	if distinct_places.len() > 1 {
181	+	multi.insert(*n);
182	+	view.conflicts.push(TreeConflict::MultiPlacement { node: n, placements: lp.iter().map(\|(k, _)\| k).collect() });
183	+	}
184	+	let lm = self.live_modes(n);
185	+	let distinct_modes: BTreeSet<Mode> = lm.iter().map(\|(_, m)\| *m).collect();
186	+	if distinct_modes.len() > 1 {
187	+	view.conflicts.push(TreeConflict::Mode { node: *n, modes: distinct_modes.into_iter().collect() });
188	+	}
189	+	}
190	+
191	+	// BFS from the root, assigning paths.
192	+	let mut reached: HashSet<NodeId> = HashSet::new();
193	+	reached.insert(NodeId::ROOT);
194	+	let mut queue: Vec<(NodeId, String)> = vec![(NodeId::ROOT, String::new())];
195	+	let mut on_path: HashSet<NodeId> = HashSet::new();
196	+	while let Some((dir, dir_path)) = queue.pop() {
197	+	let Some(kids) = children.get(&dir) else { continue };
198	+	// Name conflicts within this directory.
199	+	let mut by_name: BTreeMap<&str, Vec<(OpKey, &Placement)>> = BTreeMap::new();
200	+	for (k, p) in kids {
201	+	by_name.entry(p.name.as_str()).or_default().push((*k, p));
202	+	}
203	+	for (name, group) in by_name {
204	+	let distinct: BTreeSet<NodeId> = group.iter().map(\|(_, p)\| p.node).collect();
205	+	if distinct.len() > 1 {
206	+	view.conflicts.push(TreeConflict::Name { parent: dir, name: name.to_string(), nodes: distinct.iter().copied().collect() });
207	+	}
208	+	let suffixed = distinct.len() > 1;
209	+	for (i, (k, p)) in group.iter().enumerate() {
210	+	let node = p.node;
211	+	if node == dir \|\| on_path.contains(&node) {
212	+	view.conflicts.push(TreeConflict::Cycle { node });
213	+	continue;
214	+	}
215	+	let needs_suffix = suffixed \|\| multi.contains(&node);
216	+	let leaf = if needs_suffix { format!("{name}.oxy-conflict-{}", i + 1) } else { name.to_string() };
217	+	let path = if dir_path.is_empty() { leaf } else { format!("{dir_path}/{leaf}") };
218	+	let kind = self.kind(&node).unwrap_or(NodeKind::File);
219	+	let modes = self.live_modes(&node);
220	+	let mode_atom = modes.iter().map(\|(k, _)\| *k).max();
221	+	let mode = mode_atom.and_then(\|k\| self.modes.get(&k).map(\|(_, m)\| *m)).unwrap_or_default();
222	+	view.entries.insert(path.clone(), TreeEntry { path: path.clone(), node, kind, mode, placement: *k, mode_atom });
223	+	if kind == NodeKind::Dir && reached.insert(node) {
224	+	on_path.insert(dir);
225	+	queue.push((node, path));
226	+	} else {
227	+	reached.insert(node);
228	+	}
229	+	}
230	+	}
231	+	}
232	+
233	+	// Nodes with live placements that were never reached: orphans or cycles.
234	+	for n in &nodes {
235	+	if reached.contains(n) {
236	+	continue;
237	+	}
238	+	let lp = self.live_placements(n);
239	+	if lp.is_empty() {
240	+	continue;
241	+	}
242	+	let mut seen = HashSet::new();
243	+	let mut cur = *n;
244	+	let conflict = loop {
245	+	if !seen.insert(cur) {
246	+	break TreeConflict::Cycle { node: *n };
247	+	}
248	+	let lp = self.live_placements(&cur);
249	+	let Some((_, p)) = lp.first() else {
250	+	break TreeConflict::Orphan { node: *n, parent: cur };
251	+	};
252	+	if reached.contains(&p.parent) {
253	+	// Parent reached but this node was not: the parent is not a
254	+	// directory, so this is a name/kind problem surfaced as orphan.
255	+	break TreeConflict::Orphan { node: *n, parent: p.parent };
256	+	}
257	+	cur = p.parent;
258	+	};
259	+	if !view.conflicts.contains(&conflict) {
260	+	view.conflicts.push(conflict);
261	+	}
262	+	}
263	+	view
264	+	}
265	+	}
266	+
267	+	pub fn op_key(r: OpRef) -> OpKey {
268	+	(r.change, r.index)
269	+	}
270	+
271	+	#[cfg(test)]
272	+	mod tests {
273	+	use super::*;
274	+	use crate::hash::ObjectRef;
275	+
276	+	fn h(n: u8) -> ChangeHash {
277	+	ObjectRef([n; 32])
278	+	}
279	+	fn nid(n: u8) -> NodeId {
280	+	NodeId([n; 16])
281	+	}
282	+	fn add(g: &mut TreeGraph, c: u8, i: u32, node: u8, kind: NodeKind, parent: NodeId, name: &str) {
283	+	g.apply(h(c), i, &TreeOp::AddNode { node: nid(node), kind, mode: Mode::TEXT, parent, name: name.into() });
284	+	}
285	+	fn paths(v: &TreeView) -> Vec<String> {
286	+	v.entries.keys().cloned().collect()
287	+	}
288	+
289	+	#[test]
290	+	fn nested_paths_and_rename() {
291	+	let mut g = TreeGraph::new();
292	+	add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "src");
293	+	add(&mut g, 1, 1, 2, NodeKind::File, nid(1), "main.rs");
294	+	add(&mut g, 1, 2, 3, NodeKind::File, NodeId::ROOT, "README");
295	+	let v = g.view();
296	+	assert_eq!(paths(&v), ["README", "src", "src/main.rs"]);
297	+	assert!(!v.is_conflicted());
298	+
299	+	// Rename src/main.rs → src/lib.rs, move src → lib (subtree follows).
300	+	g.apply(h(2), 0, &TreeOp::Move { node: nid(2), old: OpRef { change: h(1), index: 1 }, parent: nid(1), name: "lib.rs".into() });
301	+	g.apply(h(2), 1, &TreeOp::Move { node: nid(1), old: OpRef { change: h(1), index: 0 }, parent: NodeId::ROOT, name: "lib".into() });
302	+	let v = g.view();
303	+	assert_eq!(paths(&v), ["README", "lib", "lib/lib.rs"]);
304	+	assert_eq!(v.entries["lib/lib.rs"].placement, (h(2), 0));
305	+
306	+	g.apply(h(3), 0, &TreeOp::RemoveNode { node: nid(3), placement: OpRef { change: h(1), index: 2 } });
307	+	assert_eq!(paths(&g.view()), ["lib", "lib/lib.rs"]);
308	+	}
309	+
310	+	#[test]
311	+	fn name_conflict_gets_suffixes() {
312	+	let mut g = TreeGraph::new();
313	+	add(&mut g, 1, 0, 1, NodeKind::File, NodeId::ROOT, "a.txt");
314	+	add(&mut g, 2, 0, 2, NodeKind::File, NodeId::ROOT, "a.txt");
315	+	let v = g.view();
316	+	assert_eq!(paths(&v), ["a.txt.oxy-conflict-1", "a.txt.oxy-conflict-2"]);
317	+	assert_eq!(v.conflicts, vec![TreeConflict::Name { parent: NodeId::ROOT, name: "a.txt".into(), nodes: vec![nid(1), nid(2)] }]);
318	+	}
319	+
320	+	#[test]
321	+	fn concurrent_renames_are_multi_placement() {
322	+	let mut g = TreeGraph::new();
323	+	add(&mut g, 1, 0, 1, NodeKind::File, NodeId::ROOT, "a");
324	+	g.apply(h(2), 0, &TreeOp::Move { node: nid(1), old: OpRef { change: h(1), index: 0 }, parent: NodeId::ROOT, name: "b".into() });
325	+	g.apply(h(3), 0, &TreeOp::Move { node: nid(1), old: OpRef { change: h(1), index: 0 }, parent: NodeId::ROOT, name: "c".into() });
326	+	let v = g.view();
327	+	assert_eq!(paths(&v), ["b.oxy-conflict-1", "c.oxy-conflict-1"]);
328	+	assert!(matches!(v.conflicts[0], TreeConflict::MultiPlacement { node, .. } if node == nid(1)));
329	+	}
330	+
331	+	#[test]
332	+	fn orphan_and_cycle() {
333	+	let mut g = TreeGraph::new();
334	+	add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "d");
335	+	add(&mut g, 1, 1, 2, NodeKind::File, nid(1), "f");
336	+	// Concurrently: 2 removes d, 3 adds d/g.
337	+	g.apply(h(2), 0, &TreeOp::RemoveNode { node: nid(1), placement: OpRef { change: h(1), index: 0 } });
338	+	add(&mut g, 3, 0, 3, NodeKind::File, nid(1), "g");
339	+	let v = g.view();
340	+	assert_eq!(paths(&v), Vec::<String>::new());
341	+	assert!(v.conflicts.contains(&TreeConflict::Orphan { node: nid(2), parent: nid(1) }));
342	+	assert!(v.conflicts.contains(&TreeConflict::Orphan { node: nid(3), parent: nid(1) }));
343	+
344	+	// Cycle: a/b, then concurrently move a under b and b under a's parent... simplest: move a into b.
345	+	let mut g = TreeGraph::new();
346	+	add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "a");
347	+	add(&mut g, 1, 1, 2, NodeKind::Dir, nid(1), "b");
348	+	g.apply(h(2), 0, &TreeOp::Move { node: nid(1), old: OpRef { change: h(1), index: 0 }, parent: nid(2), name: "a".into() });
349	+	let v = g.view();
350	+	assert!(v.conflicts.iter().any(\|c\| matches!(c, TreeConflict::Cycle { .. })), "{:?}", v.conflicts);
351	+	}
352	+
353	+	#[test]
354	+	fn mode_conflict_and_resolution() {
355	+	let mut g = TreeGraph::new();
356	+	add(&mut g, 1, 0, 1, NodeKind::File, NodeId::ROOT, "run.sh");
357	+	g.apply(h(2), 0, &TreeOp::SetMode { node: nid(1), old: OpRef { change: h(1), index: 0 }, mode: Mode { exec: true, opaque: false } });
358	+	g.apply(h(3), 0, &TreeOp::SetMode { node: nid(1), old: OpRef { change: h(1), index: 0 }, mode: Mode { exec: false, opaque: true } });
359	+	let v = g.view();
360	+	assert!(matches!(v.conflicts[0], TreeConflict::Mode { .. }));
361	+	// Materialized with the greatest mode atom.
362	+	assert_eq!(v.entries["run.sh"].mode, Mode { exec: false, opaque: true });
363	+	// The placement introduced by the same AddNode is unaffected.
364	+	assert_eq!(v.entries["run.sh"].placement, (h(1), 0));
365	+	// Resolution: retire both live mode atoms; identical live values do not conflict.
366	+	g.apply(h(4), 0, &TreeOp::SetMode { node: nid(1), old: OpRef { change: h(2), index: 0 }, mode: Mode { exec: true, opaque: false } });
367	+	g.apply(h(4), 1, &TreeOp::SetMode { node: nid(1), old: OpRef { change: h(3), index: 0 }, mode: Mode { exec: true, opaque: false } });
368	+	let v = g.view();
369	+	assert!(!v.is_conflicted(), "{:?}", v.conflicts);
370	+	assert_eq!(v.entries["run.sh"].mode, Mode { exec: true, opaque: false });
371	+	}
372	+	}

1	+	//! `oxy`: command-line interface for Oxygen.
2	+
3	+	use anyhow::{bail, Context, Result};
4	+	use clap::{Parser, Subcommand};
5	+	use oxy_core::repo::{ChangeStatus, Repo};
6	+	use std::path::PathBuf;
7	+
8	+	#[derive(Parser)]
9	+	#[command(name = "oxy", version, about = "Oxygen: breathing fresh air into version control")]
10	+	struct Cli {
11	+	#[command(subcommand)]
12	+	cmd: Cmd,
13	+	}
14	+
15	+	#[derive(Subcommand)]
16	+	enum Cmd {
17	+	/// Create a repository in PATH (default: current directory)
18	+	Init { path: Option<PathBuf> },
19	+	/// Show the working copy: changed paths and conflicts
20	+	Status,
21	+	/// Record the working copy as a change on the current bookmark
22	+	Commit {
23	+	#[arg(short, long)]
24	+	message: String,
25	+	/// Extra explicit dependencies (ChangeId prefix, #hash prefix)
26	+	#[arg(long = "depends-on")]
27	+	depends_on: Vec<String>,
28	+	},
29	+	/// List changes reachable from the bookmark and the working copy
30	+	Log,
31	+	/// Show what the working copy changes against its base
32	+	Diff,
33	+	/// Show one change (ChangeId prefix, #hash prefix, or @)
34	+	Show { change: String },
35	+	/// Undo the last operation
36	+	Undo,
37	+	/// List operations
38	+	#[command(name = "op")]
39	+	Op {
40	+	#[command(subcommand)]
41	+	cmd: OpCmd,
42	+	},
43	+	}
44	+
45	+	#[derive(Subcommand)]
46	+	enum OpCmd {
47	+	Log,
48	+	}
49	+
50	+	fn main() {
51	+	match run() {
52	+	Ok(code) => std::process::exit(code),
53	+	Err(e) => {
54	+	eprintln!("error: {e:#}");
55	+	std::process::exit(1);
56	+	}
57	+	}
58	+	}
59	+
60	+	fn open() -> Result<Repo> {
61	+	Repo::open(&std::env::current_dir()?).context("opening repository")
62	+	}
63	+
64	+	fn short_id(c: &oxy_core::objects::Change) -> String {
65	+	c.change_id.short(8)
66	+	}
67	+
68	+	fn when(ms: u64) -> String {
69	+	let secs = (ms / 1000) as i64;
70	+	let days = secs.div_euclid(86_400);
71	+	let rem = secs.rem_euclid(86_400);
72	+	// Civil-from-days (Howard Hinnant), UTC.
73	+	let z = days + 719_468;
74	+	let era = z.div_euclid(146_097);
75	+	let doe = z - era * 146_097;
76	+	let yoe = (doe - doe / 1460 + doe / 36_524 - doe / 146_096) / 365;
77	+	let y = yoe + era * 400;
78	+	let doy = doe - (365 * yoe + yoe / 4 - yoe / 100);
79	+	let mp = (5 * doy + 2) / 153;
80	+	let d = doy - (153 * mp + 2) / 5 + 1;
81	+	let m = if mp < 10 { mp + 3 } else { mp - 9 };
82	+	let y = if m <= 2 { y + 1 } else { y };
83	+	format!("{y:04}-{m:02}-{d:02} {:02}:{:02}:{:02}Z", rem / 3600, (rem % 3600) / 60, rem % 60)
84	+	}
85	+
86	+	fn run() -> Result<i32> {
87	+	let cli = Cli::parse();
88	+	match cli.cmd {
89	+	Cmd::Init { path } => {
90	+	let path = path.unwrap_or(std::env::current_dir()?);
91	+	let repo = Repo::init(&path)?;
92	+	println!("Initialized oxy repository in {}", repo.root().display());
93	+	println!("Bookmark: {} Author: {} <{}>", repo.config.bookmark, repo.config.author_name, repo.config.author_email);
94	+	Ok(0)
95	+	}
96	+	Cmd::Status => {
97	+	let repo = open()?;
98	+	let snap = repo.snapshot("oxy status")?;
99	+	let heads = repo.bookmark_heads()?;
100	+	println!(
101	+	"Working copy: {} on {} ({} head{})",
102	+	snap.wc.change_id.short(8),
103	+	repo.config.bookmark,
104	+	heads.len(),
105	+	if heads.len() == 1 { "" } else { "s" }
106	+	);
107	+	if snap.statuses.is_empty() {
108	+	println!("The working copy is clean.");
109	+	}
110	+	for s in &snap.statuses {
111	+	let tag = match s.status {
112	+	ChangeStatus::Added => "A",
113	+	ChangeStatus::Modified => "M",
114	+	ChangeStatus::Removed => "D",
115	+	ChangeStatus::ModeChanged => "X",
116	+	ChangeStatus::ConflictEdited => "C!",
117	+	};
118	+	println!("{tag:2} {}", s.path);
119	+	}
120	+	let mut code = 0;
121	+	if snap.base_snapshot.is_conflicted() {
122	+	println!("\nConflicts in the base state:");
123	+	for c in &snap.base_snapshot.tree.conflicts {
124	+	println!(" tree: {c:?}");
125	+	}
126	+	for (p, f) in &snap.base_snapshot.files {
127	+	if f.is_conflicted() {
128	+	println!(" {p}");
129	+	}
130	+	}
131	+	code = 2;
132	+	}
133	+	Ok(code)
134	+	}
135	+	Cmd::Commit { message, depends_on } => {
136	+	let repo = open()?;
137	+	let mut deps = Vec::new();
138	+	for d in &depends_on {
139	+	deps.push(repo.resolve_change(d)?);
140	+	}
141	+	let h = repo.commit(&message, &deps)?;
142	+	let c = repo.store().get_change(&h)?;
143	+	println!("Committed {} #{}: {}", short_id(&c), h.short(12), message.lines().next().unwrap_or(""));
144	+	Ok(0)
145	+	}
146	+	Cmd::Log => {
147	+	let repo = open()?;
148	+	repo.snapshot("oxy log")?;
149	+	for e in repo.log()? {
150	+	let c = &e.change;
151	+	let mut flags = Vec::new();
152	+	if e.is_working_copy {
153	+	flags.push("working copy");
154	+	}
155	+	if e.is_head {
156	+	flags.push("head");
157	+	}
158	+	let flags = if flags.is_empty() { String::new() } else { format!(" ({})", flags.join(", ")) };
159	+	println!("{} #{}{}", short_id(c), e.hash.short(12), flags);
160	+	println!(" {}", when(c.hlc.wall_ms));
161	+	if !c.deps.is_empty() {
162	+	println!(" deps: {}", c.deps.iter().map(\|d\| format!("#{}", d.short(12))).collect::<Vec<_>>().join(" "));
163	+	}
164	+	let msg = if c.message.is_empty() { "(no description)" } else { &c.message };
165	+	for line in msg.lines() {
166	+	println!(" {line}");
167	+	}
168	+	println!();
169	+	}
170	+	Ok(0)
171	+	}
172	+	Cmd::Diff => {
173	+	let repo = open()?;
174	+	let snap = repo.snapshot("oxy diff")?;
175	+	print!("{}", oxy_core::repo::render_change(&snap.wc, &snap.base, &snap.base_snapshot));
176	+	Ok(0)
177	+	}
178	+	Cmd::Show { change } => {
179	+	let repo = open()?;
180	+	repo.snapshot("oxy show")?;
181	+	let h = repo.resolve_change(&change)?;
182	+	let c = repo.store().get_change(&h)?;
183	+	println!("change {} #{}", short_id(&c), h);
184	+	println!("kind: {:?}", c.kind);
185	+	println!("date: {}", when(c.hlc.wall_ms));
186	+	println!("deps: {}", c.deps.iter().map(\|d\| format!("#{}", d.short(12))).collect::<Vec<_>>().join(" "));
187	+	println!("\n{}\n", if c.message.is_empty() { "(no description)" } else { &c.message });
188	+	print!("{}", repo.describe_change(&h)?);
189	+	Ok(0)
190	+	}
191	+	Cmd::Undo => {
192	+	let repo = open()?;
193	+	let op = repo.undo()?;
194	+	println!("Undid the last operation; now at: {}", op.command);
195	+	Ok(0)
196	+	}
197	+	Cmd::Op { cmd: OpCmd::Log } => {
198	+	let repo = open()?;
199	+	for (i, (r, op)) in repo.op_log()?.into_iter().enumerate() {
200	+	println!("{}{} {} {}", if i == 0 { "@ " } else { " " }, r.short(12), when(op.hlc.wall_ms), op.command);
201	+	}
202	+	Ok(0)
203	+	}
204	+	}
205	+	.map_err(\|e: anyhow::Error\| e)
206	+	.or_else(\|e\| {
207	+	if e.to_string().is_empty() {
208	+	bail!("unknown error")
209	+	} else {
210	+	Err(e)
211	+	}
212	+	})
213	+	}

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

1	+	//! A repository on disk: the `.oxy` directory, one workspace, the operation
2	+	//! log, and the working-copy change (spec §12, §13.1).
3	+	//!
4	+	//! Not yet implemented from the spec: signatures and identities (the author
5	+	//! is `ObjectRef::ZERO`), packs, content-defined chunking (blobs use fixed
6	+	//! 256 KiB chunks), checkpoints, multiple workspaces, remotes, and resolving
7	+	//! conflicts by editing markers.
8	+
9	+	use crate::diff::{ranges, split_lines, text_edits};
10	+	use crate::hash::{hash_object, ChangeHash, ObjectRef, ObjectType};
11	+	use crate::ids::{ChangeId, NodeId, WorkspaceId};
12	+	use crate::objects::{Blob, Change, ChangeKind, Edit, Hlc, Mode, NodeKind, OpRef, TreeOp};
13	+	use crate::oplog::{Op, View};
14	+	use crate::state::{FileContent, Snapshot, State};
15	+	use crate::store::{Store, StoreError};
16	+	use crate::tree::OpKey;
17	+	use std::collections::{BTreeMap, BTreeSet, HashMap};
18	+	use std::fs;
19	+	use std::io::Write;
20	+	use std::path::{Path, PathBuf};
21	+
22	+	pub const OXY_DIR: &str = ".oxy";
23	+	pub const FORMAT_LINE: &str = "oxy repository format 1\n";
24	+	pub const CHUNK_SIZE: usize = 256 * 1024;
25	+	const BINARY_SNIFF: usize = 8 * 1024;
26	+
27	+	#[derive(Debug, thiserror::Error)]
28	+	pub enum RepoError {
29	+	#[error("io: {0}")]
30	+	Io(#[from] std::io::Error),
31	+	#[error(transparent)]
32	+	Store(#[from] StoreError),
33	+	#[error(transparent)]
34	+	Object(#[from] crate::objects::ObjectError),
35	+	#[error(transparent)]
36	+	State(#[from] crate::state::StateError),
37	+	#[error("{0}")]
38	+	Msg(String),
39	+	}
40	+

1	+	# Oxygen (`oxy`) — Version Control System Specification
2	+
3	+	\| \| \|
4	+	\|---\|---\|
5	+	\| Status \| Draft 0.4 \|
6	+	\| Format version \| 1 \|
7	+	\| Date \| 2026-09-26 \|
8	+	\| Audience \| Implementers, security reviewers, and contributors \|
9	+
10	+	The key words MUST, MUST NOT, SHOULD, SHOULD NOT, and MAY are to be interpreted as described in RFC 2119.
11	+
12	+	---
13	+
14	+	## Table of contents
15	+
16	+	1. [Overview](#1-overview)
17	+	2. [Goals, non-goals, and lineage](#2-goals-non-goals-and-lineage)
18	+	3. [Threat model](#3-threat-model)
19	+	4. [Terminology](#4-terminology)
20	+	5. [Object model and hashing](#5-object-model-and-hashing)
21	+	6. [The change graph](#6-the-change-graph)
22	+	7. [Files, trees, and atoms](#7-files-trees-and-atoms)
23	+	8. [Dependencies and commutation](#8-dependencies-and-commutation)
24	+	9. [Conflicts](#9-conflicts)
25	+	10. [States, bookmarks, and tags](#10-states-bookmarks-and-tags)
26	+	11. [Checkpoints](#11-checkpoints)
27	+	12. [Operation log, workspaces, and the working copy](#12-operation-log-workspaces-and-the-working-copy)
28	+	13. [Storage engine](#13-storage-engine)
29	+	14. [Identity, signatures, and trust policy](#14-identity-signatures-and-trust-policy)
30	+	15. [Transport](#15-transport)
31	+	16. [Wire protocol](#16-wire-protocol)
32	+	17. [Partial, sparse, and shallow repositories](#17-partial-sparse-and-shallow-repositories)
33	+	18. [Locks for unmergeable files](#18-locks-for-unmergeable-files)
34	+	19. [Repository configuration files](#19-repository-configuration-files)
35	+	20. [Hooks and server policy](#20-hooks-and-server-policy)
36	+	21. [Garbage collection](#21-garbage-collection)
37	+	22. [Client profiles and retro hardware](#22-client-profiles-and-retro-hardware)
38	+	23. [Git interoperability](#23-git-interoperability)
39	+	24. [Command-line interface](#24-command-line-interface)
40	+	25. [Performance targets](#25-performance-targets)

Import the Oxygen specification and the first Rust implementation (root change) ff0af1ee299d

Keyboard