Store large inserts as text blobs (change format 2) 6f8aeb996558
A change carried every inserted line inline, so a first commit of a large tree was one object as large as the tree: 1.8 GB for Linux, over the 1 GiB an object may be. Change format version 2 stores each insert of 4 KiB or more (as encoded) as a text blob beside the change, holding the CBOR array of its lines; the change keeps a reference and the line count. The rule is deterministic, so a change still has one encoding and one hash, and identical inserts share their blob. Version 1 changes are read and re-encoded byte for byte, so existing hashes and signatures are unchanged. The store writes and resolves text blobs; bundles always carry them, so a bundle reads on its own; gc keeps them with their change and fsck checks them. Spec Draft 0.8q. refs #34
- Author
- Andy McCall @andymccall <[email protected]>
- When
- · 2026-09-29 19:39 UTC
- Signature
- ✔ signed by Andy McCall
- Hash
6f8aeb996558059ef0a54d0900da5c537a9b5fef18c9d69ba25b6c1af953add1- Depends on
- 096f447ccda0 1983686fb7a7 21b2aec279ff 23b217d75848 2863456a0f6d 28fc23d7706a 387335ff7f4d 5b1114a04905 5b9c6ad45f6e 614541c3cebd 728da0f92161 750251b21a96 75167672ebcd 79ab8528ff62 84b9e9ac0ab4 86e682c242c6 86fe29fd62ea 8f10a07a1dbe 982864068a59 a9f686edf60b b837d2b55853 ba160f60219e c07e0e7d2d85 c3069537d7c5 dfb23a3a8cfa fc1a466a1e66 ff0af1ee299d
- Depended on by
- f0a517d28237 68a924846379 b689779e9e74 648189388f1a 5b4c51307b14 4d6c9c1b358c 0f93f49ce059 2c75672fb2fe 598009a75f6c 01a47cd7f0c8 17f94b13ae54 192fad1e46a2 69816d688300 a4fad5b085c7 86e1824f2d0b 7d9dab131937 1a3b62032ed9 6caacfff1d4f
- 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
- 72 atoms, 0 tree operations, 15 files
Browse the tree at this change
modified crates/oxy-core/src/cbor.rs +31 −0
| … | 120 unchanged lines |
||
| 121 | 121 | } |
|
| 122 | 122 | } |
|
| 123 | 123 | ||
| 124 | + | /// The canonical encoding of an array of byte strings, written without |
|
| 125 | + | /// building a [`Value`] (large inserts stored as text blobs, spec §6.1). |
|
| 126 | + | pub fn encode_byte_strings(items: &[Vec<u8>]) -> Vec<u8> { |
|
| 127 | + | let mut out = Vec::with_capacity(byte_strings_len(items)); |
|
| 128 | + | head(&mut out, 4, items.len() as u64); |
|
| 129 | + | for b in items { |
|
| 130 | + | head(&mut out, 2, b.len() as u64); |
|
| 131 | + | out.extend_from_slice(b); |
|
| 132 | + | } |
|
| 133 | + | out |
|
| 134 | + | } |
|
| 135 | + | ||
| 136 | + | /// The length of [`encode_byte_strings`]' output, without encoding. |
|
| 137 | + | pub fn byte_strings_len(items: &[Vec<u8>]) -> usize { |
|
| 138 | + | head_len(items.len() as u64) |
|
| 139 | + | + items |
|
| 140 | + | .iter() |
|
| 141 | + | .map(|b| head_len(b.len() as u64) + b.len()) |
|
| 142 | + | .sum::<usize>() |
|
| 143 | + | } |
|
| 144 | + | ||
| 145 | + | fn head_len(n: u64) -> usize { |
|
| 146 | + | match n { |
|
| 147 | + | 0..=23 => 1, |
|
| 148 | + | 24..=0xff => 2, |
|
| 149 | + | 0x100..=0xffff => 3, |
|
| 150 | + | 0x1_0000..=0xffff_ffff => 5, |
|
| 151 | + | _ => 9, |
|
| 152 | + | } |
|
| 153 | + | } |
|
| 154 | + | ||
| 124 | 155 | fn head(out: &mut Vec<u8>, major: u8, n: u64) { |
|
| 125 | 156 | let m = major << 5; |
|
| 126 | 157 | if n < 24 { |
|
| … | 377 unchanged lines |
modified crates/oxy-core/src/objects.rs +255 −12
| … | 13 unchanged lines |
||
| 14 | 14 | ||
| 15 | 15 | pub const FORMAT_VERSION: u64 = 1; |
|
| 16 | 16 | ||
| 17 | + | /// The change format writers produce (spec §6.1). Version 2 stores each |
|
| 18 | + | /// large insert's lines as a text blob; readers accept 1 and 2, and a |
|
| 19 | + | /// change keeps the version it was made in, so its hash never moves. |
|
| 20 | + | pub const CHANGE_VERSION: u64 = 2; |
|
| 21 | + | ||
| 22 | + | /// In a version 2 change, an insert whose lines encode (as a CBOR array of |
|
| 23 | + | /// byte strings) to at least this many bytes is stored as a text blob |
|
| 24 | + | /// holding exactly that encoding; a shorter one is inline (spec §6.1). |
|
| 25 | + | pub const TEXT_BLOB_MIN: usize = 4096; |
|
| 26 | + | ||
| 17 | 27 | #[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)] |
|
| 18 | 28 | pub enum ObjectError { |
|
| 19 | 29 | #[error("cbor: {0}")] |
|
| … | 420 unchanged lines |
||
| 440 | 450 | *node |
|
| 441 | 451 | } |
|
| 442 | 452 | } |
|
| 453 | + | } |
|
| 454 | + | ||
| 455 | + | /// Whether this insert is stored as a text blob in a change of `version`. |
|
| 456 | + | fn stored_text(&self, version: u64) -> bool { |
|
| 457 | + | matches!(self, Edit::Insert { lines, .. } |
|
| 458 | + | if version >= 2 && cbor::byte_strings_len(lines) >= TEXT_BLOB_MIN) |
|
| 443 | 459 | } |
|
| 444 | 460 | ||
| 445 | - | fn to_value(&self) -> Value { |
|
| 461 | + | fn to_value(&self, version: u64, texts: &mut Option<&mut Vec<StoredText>>) -> Value { |
|
| 446 | 462 | let nid = |n: &NodeId| Value::Bytes(n.0.to_vec()); |
|
| 447 | 463 | let opt = |o: &Option<ObjectRef>| match o { |
|
| 448 | 464 | Some(r) => Value::Bytes(r.0.to_vec()), |
|
| … | 5 unchanged lines |
||
| 454 | 470 | after, |
|
| 455 | 471 | before, |
|
| 456 | 472 | lines, |
|
| 473 | + | } if self.stored_text(version) => { |
|
| 474 | + | let content = cbor::encode_byte_strings(lines); |
|
| 475 | + | let blob = Blob::of(&content); |
|
| 476 | + | let r = blob.hash(); |
|
| 477 | + | if let Some(t) = texts { |
|
| 478 | + | t.push(StoredText { blob, content }); |
|
| 479 | + | } |
|
| 480 | + | Value::map([ |
|
| 481 | + | (0, Value::Uint(0)), |
|
| 482 | + | (1, nid(node)), |
|
| 483 | + | (2, after.to_value()), |
|
| 484 | + | (3, before.to_value()), |
|
| 485 | + | (5, Value::Bytes(r.0.to_vec())), |
|
| 486 | + | (6, Value::Uint(lines.len() as u64)), |
|
| 487 | + | ]) |
|
| 488 | + | } |
|
| 489 | + | Edit::Insert { |
|
| 490 | + | node, |
|
| 491 | + | after, |
|
| 492 | + | before, |
|
| 493 | + | lines, |
|
| 457 | 494 | } => Value::map([ |
|
| 458 | 495 | (0, Value::Uint(0)), |
|
| 459 | 496 | (1, nid(node)), |
|
| … | 21 unchanged lines |
||
| 481 | 518 | } |
|
| 482 | 519 | } |
|
| 483 | 520 | ||
| 484 | - | fn from_value(v: &Value) -> Result<Edit, ObjectError> { |
|
| 521 | + | fn from_value(v: &Value, version: u64, resolve: &mut Resolver) -> Result<Edit, ObjectError> { |
|
| 485 | 522 | let m = map(v, "edit")?; |
|
| 486 | 523 | let tag = uint(field(m, 0, "edit tag")?, "edit tag")?; |
|
| 487 | 524 | let node = node_id(field(m, 1, "edit.node")?, "edit.node")?; |
|
| … | 6 unchanged lines |
||
| 494 | 531 | }; |
|
| 495 | 532 | Ok(match tag { |
|
| 496 | 533 | 0 => { |
|
| 497 | - | let lines = array(field(m, 4, "lines")?, "lines")? |
|
| 498 | - | .iter() |
|
| 499 | - | .map(|l| bytes(l, "line").map(|b| b.to_vec())) |
|
| 500 | - | .collect::<Result<Vec<_>, _>>()?; |
|
| 534 | + | let lines = match (m.get(&4), m.get(&5)) { |
|
| 535 | + | (Some(inline), None) => { |
|
| 536 | + | let lines = array(inline, "lines")? |
|
| 537 | + | .iter() |
|
| 538 | + | .map(|l| bytes(l, "line").map(|b| b.to_vec())) |
|
| 539 | + | .collect::<Result<Vec<_>, _>>()?; |
|
| 540 | + | if version >= 2 && cbor::byte_strings_len(&lines) >= TEXT_BLOB_MIN { |
|
| 541 | + | return schema("an insert this large is stored as a text blob in a version 2 change"); |
|
| 542 | + | } |
|
| 543 | + | lines |
|
| 544 | + | } |
|
| 545 | + | (None, Some(text)) if version >= 2 => { |
|
| 546 | + | let text = oref(text, "insert text")?; |
|
| 547 | + | let count = u32_(field(m, 6, "insert line count")?, "insert line count")?; |
|
| 548 | + | if count == 0 { |
|
| 549 | + | return schema("insert with no lines"); |
|
| 550 | + | } |
|
| 551 | + | // The resolver checks the count (`text_lines`). |
|
| 552 | + | resolve(&text, count)? |
|
| 553 | + | } |
|
| 554 | + | _ => { |
|
| 555 | + | return schema( |
|
| 556 | + | "an insert has either its lines or, in a version 2 change, a text blob", |
|
| 557 | + | ) |
|
| 558 | + | } |
|
| 559 | + | }; |
|
| 501 | 560 | if lines.is_empty() { |
|
| 502 | 561 | return schema("insert with no lines"); |
|
| 503 | 562 | } |
|
| … | 54 unchanged lines |
||
| 558 | 617 | /// A change (spec §6.1). `deps` is kept sorted and unique by `normalize`. |
|
| 559 | 618 | #[derive(Debug, Clone, PartialEq, Eq)] |
|
| 560 | 619 | pub struct Change { |
|
| 620 | + | /// The format this change is encoded in: [`CHANGE_VERSION`] for a new |
|
| 621 | + | /// one, whatever it was made in for one read back. |
|
| 622 | + | pub version: u64, |
|
| 561 | 623 | pub change_id: ChangeId, |
|
| 562 | 624 | pub deps: Vec<ChangeHash>, |
|
| 563 | 625 | pub author: KeyId, |
|
| … | 11 unchanged lines |
||
| 575 | 637 | } |
|
| 576 | 638 | ||
| 577 | 639 | pub fn to_value(&self) -> Value { |
|
| 640 | + | self.value_with(&mut None) |
|
| 641 | + | } |
|
| 642 | + | ||
| 643 | + | fn value_with(&self, texts: &mut Option<&mut Vec<StoredText>>) -> Value { |
|
| 578 | 644 | Value::map([ |
|
| 579 | - | (0, Value::Uint(FORMAT_VERSION)), |
|
| 645 | + | (0, Value::Uint(self.version)), |
|
| 580 | 646 | (1, Value::Bytes(self.change_id.0.to_vec())), |
|
| 581 | 647 | ( |
|
| 582 | 648 | 2, |
|
| … | 13 unchanged lines |
||
| 596 | 662 | ), |
|
| 597 | 663 | ( |
|
| 598 | 664 | 7, |
|
| 599 | - | Value::Array(self.edits.iter().map(|e| e.to_value()).collect()), |
|
| 665 | + | Value::Array( |
|
| 666 | + | self.edits |
|
| 667 | + | .iter() |
|
| 668 | + | .map(|e| e.to_value(self.version, texts)) |
|
| 669 | + | .collect(), |
|
| 670 | + | ), |
|
| 600 | 671 | ), |
|
| 601 | 672 | (8, Value::Uint(self.kind.tag())), |
|
| 602 | 673 | (9, Value::Map(BTreeMap::new())), |
|
| … | 8 unchanged lines |
||
| 611 | 682 | cbor::encode(&self.to_value()) |
|
| 612 | 683 | } |
|
| 613 | 684 | ||
| 685 | + | /// The encoding and the text blobs its large inserts are stored as, |
|
| 686 | + | /// which must be stored with it. |
|
| 687 | + | pub fn encode_parts(&self) -> (Vec<u8>, Vec<StoredText>) { |
|
| 688 | + | debug_assert!( |
|
| 689 | + | self.deps.windows(2).all(|w| w[0] < w[1]), |
|
| 690 | + | "deps must be normalized" |
|
| 691 | + | ); |
|
| 692 | + | let mut texts = Vec::new(); |
|
| 693 | + | let bytes = cbor::encode(&self.value_with(&mut Some(&mut texts))); |
|
| 694 | + | (bytes, texts) |
|
| 695 | + | } |
|
| 696 | + | ||
| 697 | + | /// Whether any insert is stored as a text blob. |
|
| 698 | + | pub fn has_stored_text(&self) -> bool { |
|
| 699 | + | self.edits.iter().any(|e| e.stored_text(self.version)) |
|
| 700 | + | } |
|
| 701 | + | ||
| 614 | 702 | pub fn hash(&self) -> ChangeHash { |
|
| 615 | 703 | hash_object(ObjectType::Change, &self.encode()) |
|
| 616 | 704 | } |
|
| 617 | 705 | ||
| 706 | + | /// Decode a change that stores no text blob; one that does needs |
|
| 707 | + | /// [`Change::decode_with`] and something to read them from. |
|
| 618 | 708 | pub fn decode(bytes: &[u8]) -> Result<Change, ObjectError> { |
|
| 709 | + | Self::decode_with(bytes, &mut |r, _| { |
|
| 710 | + | schema(format!( |
|
| 711 | + | "text blob {} needs a store to read it from", |
|
| 712 | + | r.short(12) |
|
| 713 | + | )) |
|
| 714 | + | }) |
|
| 715 | + | } |
|
| 716 | + | ||
| 717 | + | /// Decode a change, reading each stored insert's lines with `resolve` |
|
| 718 | + | /// (given the text blob and the line count the insert claims). |
|
| 719 | + | pub fn decode_with(bytes: &[u8], resolve: &mut Resolver) -> Result<Change, ObjectError> { |
|
| 619 | 720 | let v = cbor::decode(bytes)?; |
|
| 620 | - | Self::from_value(&v) |
|
| 721 | + | Self::from_value_with(&v, resolve) |
|
| 621 | 722 | } |
|
| 622 | 723 | ||
| 623 | 724 | pub fn from_value(v: &Value) -> Result<Change, ObjectError> { |
|
| 725 | + | Self::from_value_with(v, &mut |r, _| { |
|
| 726 | + | schema(format!( |
|
| 727 | + | "text blob {} needs a store to read it from", |
|
| 728 | + | r.short(12) |
|
| 729 | + | )) |
|
| 730 | + | }) |
|
| 731 | + | } |
|
| 732 | + | ||
| 733 | + | fn from_value_with(v: &Value, resolve: &mut Resolver) -> Result<Change, ObjectError> { |
|
| 624 | 734 | let m = map(v, "change")?; |
|
| 625 | - | check_version(m)?; |
|
| 735 | + | let version = uint(field(m, 0, "version")?, "version")?; |
|
| 736 | + | if !(1..=CHANGE_VERSION).contains(&version) { |
|
| 737 | + | return schema(format!("unsupported change format version {version}")); |
|
| 738 | + | } |
|
| 626 | 739 | let change_id = ChangeId::from_slice(bytes(field(m, 1, "change_id")?, "change_id")?) |
|
| 627 | 740 | .ok_or_else(|| ObjectError::Schema("change_id: expected 16 bytes".into()))?; |
|
| 628 | 741 | let deps = array(field(m, 2, "deps")?, "deps")? |
|
| … | 11 unchanged lines |
||
| 640 | 753 | return schema("extra must be empty in format version 1"); |
|
| 641 | 754 | } |
|
| 642 | 755 | Ok(Change { |
|
| 756 | + | version, |
|
| 643 | 757 | change_id, |
|
| 644 | 758 | deps, |
|
| 645 | 759 | author: oref(field(m, 3, "author")?, "author")?, |
|
| … | 5 unchanged lines |
||
| 651 | 765 | .collect::<Result<Vec<_>, _>>()?, |
|
| 652 | 766 | edits: array(field(m, 7, "edits")?, "edits")? |
|
| 653 | 767 | .iter() |
|
| 654 | - | .map(Edit::from_value) |
|
| 768 | + | .map(|e| Edit::from_value(e, version, resolve)) |
|
| 655 | 769 | .collect::<Result<Vec<_>, _>>()?, |
|
| 656 | 770 | kind: ChangeKind::from_tag(uint(field(m, 8, "kind")?, "kind")?)?, |
|
| 657 | 771 | }) |
|
| 658 | 772 | } |
|
| 659 | 773 | } |
|
| 660 | 774 | ||
| 775 | + | /// Reads a stored insert's lines, given the text blob and the line count |
|
| 776 | + | /// the insert claims; [`text_lines`] reads and checks a blob's content. |
|
| 777 | + | pub type Resolver<'a> = dyn FnMut(&ObjectRef, u32) -> Result<Vec<Vec<u8>>, ObjectError> + 'a; |
|
| 778 | + | ||
| 779 | + | /// A large insert's lines as stored (spec §6.1): the blob and its content, |
|
| 780 | + | /// the canonical CBOR array of the lines' byte strings. |
|
| 781 | + | #[derive(Debug, Clone, PartialEq, Eq)] |
|
| 782 | + | pub struct StoredText { |
|
| 783 | + | pub blob: Blob, |
|
| 784 | + | pub content: Vec<u8>, |
|
| 785 | + | } |
|
| 786 | + | ||
| 787 | + | /// The lines a text blob's `content` holds, checked against the rules for |
|
| 788 | + | /// one: canonical, as many as the insert claims, and not short enough to |
|
| 789 | + | /// have been inline. |
|
| 790 | + | pub fn text_lines(content: &[u8], count: u32) -> Result<Vec<Vec<u8>>, ObjectError> { |
|
| 791 | + | if content.len() < TEXT_BLOB_MIN { |
|
| 792 | + | return schema(format!( |
|
| 793 | + | "a text blob of {} bytes is short enough to be inline", |
|
| 794 | + | content.len() |
|
| 795 | + | )); |
|
| 796 | + | } |
|
| 797 | + | let v = cbor::decode(content)?; |
|
| 798 | + | let lines = array(&v, "text blob")? |
|
| 799 | + | .iter() |
|
| 800 | + | .map(|l| bytes(l, "line").map(|b| b.to_vec())) |
|
| 801 | + | .collect::<Result<Vec<_>, _>>()?; |
|
| 802 | + | if lines.len() != count as usize { |
|
| 803 | + | return schema(format!( |
|
| 804 | + | "a text blob holds {} lines, the insert says {count}", |
|
| 805 | + | lines.len() |
|
| 806 | + | )); |
|
| 807 | + | } |
|
| 808 | + | Ok(lines) |
|
| 809 | + | } |
|
| 810 | + | ||
| 661 | 811 | // ---------------------------------------------------------------- blob |
|
| 662 | 812 | ||
| 663 | 813 | /// File content as an ordered list of chunks (spec §13.2). |
|
| … | 4 unchanged lines |
||
| 668 | 818 | } |
|
| 669 | 819 | ||
| 670 | 820 | impl Blob { |
|
| 821 | + | /// The blob for `content`: its chunks as content-defined chunking cuts |
|
| 822 | + | /// them (spec §13.2). |
|
| 823 | + | pub fn of(content: &[u8]) -> Blob { |
|
| 824 | + | Blob { |
|
| 825 | + | length: content.len() as u64, |
|
| 826 | + | chunks: crate::chunk::chunks(content) |
|
| 827 | + | .into_iter() |
|
| 828 | + | .map(|c| hash_object(ObjectType::Chunk, c)) |
|
| 829 | + | .collect(), |
|
| 830 | + | } |
|
| 831 | + | } |
|
| 832 | + | ||
| 671 | 833 | pub fn encode(&self) -> Vec<u8> { |
|
| 672 | 834 | cbor::encode(&Value::map([ |
|
| 673 | 835 | (0, Value::Uint(FORMAT_VERSION)), |
|
| … | 127 unchanged lines |
||
| 801 | 963 | let n = NodeId([7; 16]); |
|
| 802 | 964 | let dep = ObjectRef([1; 32]); |
|
| 803 | 965 | let mut c = Change { |
|
| 966 | + | version: crate::objects::CHANGE_VERSION, |
|
| 804 | 967 | change_id: ChangeId([9; 16]), |
|
| 805 | 968 | deps: vec![ObjectRef([2; 32]), dep], |
|
| 806 | 969 | author: ObjectRef([3; 32]), |
|
| … | 68 unchanged lines |
||
| 875 | 1038 | let c = sample_change(); |
|
| 876 | 1039 | let mut v = c.to_value(); |
|
| 877 | 1040 | if let Value::Map(m) = &mut v { |
|
| 878 | - | m.insert(0, Value::Uint(2)); |
|
| 1041 | + | m.insert(0, Value::Uint(3)); |
|
| 879 | 1042 | } |
|
| 880 | 1043 | assert!( |
|
| 881 | 1044 | matches!(Change::from_value(&v), Err(ObjectError::Schema(s)) if s.contains("version")) |
|
| … | 17 unchanged lines |
||
| 899 | 1062 | assert!( |
|
| 900 | 1063 | matches!(Change::from_value(&v), Err(ObjectError::Schema(s)) if s.contains("extra")) |
|
| 901 | 1064 | ); |
|
| 1065 | + | } |
|
| 1066 | + | ||
| 1067 | + | fn big_lines(n: usize) -> Vec<Vec<u8>> { |
|
| 1068 | + | (0..n) |
|
| 1069 | + | .map(|i| format!("line {i} of a large insert\n").into_bytes()) |
|
| 1070 | + | .collect() |
|
| 1071 | + | } |
|
| 1072 | + | ||
| 1073 | + | fn with_insert(mut c: Change, lines: Vec<Vec<u8>>) -> Change { |
|
| 1074 | + | c.edits[0] = Edit::Insert { |
|
| 1075 | + | node: NodeId([7; 16]), |
|
| 1076 | + | after: AtomRef::Start, |
|
| 1077 | + | before: AtomRef::End, |
|
| 1078 | + | lines, |
|
| 1079 | + | }; |
|
| 1080 | + | c |
|
| 1081 | + | } |
|
| 1082 | + | ||
| 1083 | + | #[test] |
|
| 1084 | + | fn large_inserts_are_stored_as_text_blobs() { |
|
| 1085 | + | assert!( |
|
| 1086 | + | !sample_change().has_stored_text(), |
|
| 1087 | + | "a small insert stays inline" |
|
| 1088 | + | ); |
|
| 1089 | + | let lines = big_lines(500); |
|
| 1090 | + | let c = with_insert(sample_change(), lines.clone()); |
|
| 1091 | + | assert!(c.has_stored_text()); |
|
| 1092 | + | let (bytes, texts) = c.encode_parts(); |
|
| 1093 | + | assert_eq!(bytes, c.encode()); |
|
| 1094 | + | assert!(bytes.len() < 1024, "{}", bytes.len()); |
|
| 1095 | + | assert_eq!(texts.len(), 1); |
|
| 1096 | + | assert_eq!(texts[0].content, cbor::encode_byte_strings(&lines)); |
|
| 1097 | + | assert_eq!(texts[0].blob, Blob::of(&texts[0].content)); |
|
| 1098 | + | assert!(Change::decode(&bytes).is_err(), "reading it needs the text"); |
|
| 1099 | + | let d = Change::decode_with(&bytes, &mut |r, n| { |
|
| 1100 | + | assert_eq!(*r, texts[0].blob.hash()); |
|
| 1101 | + | text_lines(&texts[0].content, n) |
|
| 1102 | + | }) |
|
| 1103 | + | .unwrap(); |
|
| 1104 | + | assert_eq!(d, c); |
|
| 1105 | + | assert_eq!(d.hash(), c.hash()); |
|
| 1106 | + | } |
|
| 1107 | + | ||
| 1108 | + | #[test] |
|
| 1109 | + | fn version_1_changes_keep_their_inline_inserts_and_hashes() { |
|
| 1110 | + | let mut c = with_insert(sample_change(), big_lines(500)); |
|
| 1111 | + | c.version = 1; |
|
| 1112 | + | let bytes = c.encode(); |
|
| 1113 | + | assert!(bytes.len() > TEXT_BLOB_MIN); |
|
| 1114 | + | let (again, texts) = c.encode_parts(); |
|
| 1115 | + | assert!(texts.is_empty()); |
|
| 1116 | + | assert_eq!(again, bytes); |
|
| 1117 | + | let d = Change::decode(&bytes).unwrap(); |
|
| 1118 | + | assert_eq!(d.version, 1); |
|
| 1119 | + | assert_eq!(d.encode(), bytes); |
|
| 1120 | + | // The same inline insert in a version 2 change is not canonical. |
|
| 1121 | + | let mut v = c.to_value(); |
|
| 1122 | + | if let Value::Map(m) = &mut v { |
|
| 1123 | + | m.insert(0, Value::Uint(2)); |
|
| 1124 | + | } |
|
| 1125 | + | assert!( |
|
| 1126 | + | matches!(Change::from_value(&v), Err(ObjectError::Schema(s)) if s.contains("text blob")) |
|
| 1127 | + | ); |
|
| 1128 | + | } |
|
| 1129 | + | ||
| 1130 | + | #[test] |
|
| 1131 | + | fn text_blobs_are_checked() { |
|
| 1132 | + | let lines = big_lines(500); |
|
| 1133 | + | let content = cbor::encode_byte_strings(&lines); |
|
| 1134 | + | assert_eq!(content.len(), cbor::byte_strings_len(&lines)); |
|
| 1135 | + | assert_eq!( |
|
| 1136 | + | content, |
|
| 1137 | + | cbor::encode(&Value::Array( |
|
| 1138 | + | lines.iter().map(|l| Value::Bytes(l.clone())).collect() |
|
| 1139 | + | )) |
|
| 1140 | + | ); |
|
| 1141 | + | assert_eq!(text_lines(&content, 500).unwrap(), lines); |
|
| 1142 | + | assert!(text_lines(&content, 499).is_err()); |
|
| 1143 | + | let small = cbor::encode_byte_strings(&[b"x\n".to_vec()]); |
|
| 1144 | + | assert!(text_lines(&small, 1).is_err(), "short enough to be inline"); |
|
| 902 | 1145 | } |
|
| 903 | 1146 | ||
| 904 | 1147 | #[test] |
|
| … | 80 unchanged lines |
modified crates/oxy-core/src/protocol.rs +65 −22
| … | 533 unchanged lines |
||
| 534 | 534 | Ok(o::field(m, k, what)?) |
|
| 535 | 535 | } |
|
| 536 | 536 | ||
| 537 | + | /// A bundle's value. Each change's text blobs and their chunks (spec |
|
| 538 | + | /// §6.1) are added to its objects when they are not already there, so a |
|
| 539 | + | /// bundle can always be read on its own. |
|
| 537 | 540 | pub fn bundle_value(b: &Bundle) -> Value { |
|
| 541 | + | let mut changes = Vec::with_capacity(b.changes.len()); |
|
| 542 | + | let mut texts: Vec<(ObjectType, Vec<u8>)> = Vec::new(); |
|
| 543 | + | let mut listed: Option<std::collections::HashSet<ObjectRef>> = None; |
|
| 544 | + | for (c, s) in &b.changes { |
|
| 545 | + | let (bytes, stored) = c.encode_parts(); |
|
| 546 | + | for t in stored { |
|
| 547 | + | let listed = listed.get_or_insert_with(|| { |
|
| 548 | + | b.objects |
|
| 549 | + | .iter() |
|
| 550 | + | .map(|(ty, body)| crate::hash::hash_object(*ty, body)) |
|
| 551 | + | .collect() |
|
| 552 | + | }); |
|
| 553 | + | if !listed.insert(t.blob.hash()) { |
|
| 554 | + | continue; |
|
| 555 | + | } |
|
| 556 | + | for chunk in crate::chunk::chunks(&t.content) { |
|
| 557 | + | if listed.insert(crate::hash::hash_object(ObjectType::Chunk, chunk)) { |
|
| 558 | + | texts.push((ObjectType::Chunk, chunk.to_vec())); |
|
| 559 | + | } |
|
| 560 | + | } |
|
| 561 | + | texts.push((ObjectType::Blob, t.blob.encode())); |
|
| 562 | + | } |
|
| 563 | + | changes.push(Value::Array(vec![Value::Bytes(bytes), sigs_value(s)])); |
|
| 564 | + | } |
|
| 538 | 565 | Value::map([ |
|
| 539 | - | ( |
|
| 540 | - | 0, |
|
| 541 | - | Value::Array( |
|
| 542 | - | b.changes |
|
| 543 | - | .iter() |
|
| 544 | - | .map(|(c, s)| Value::Array(vec![Value::Bytes(c.encode()), sigs_value(s)])) |
|
| 545 | - | .collect(), |
|
| 546 | - | ), |
|
| 547 | - | ), |
|
| 566 | + | (0, Value::Array(changes)), |
|
| 548 | 567 | ( |
|
| 549 | 568 | 1, |
|
| 550 | 569 | Value::Array(b.attests.iter().map(attest_value).collect()), |
|
| … | 3 unchanged lines |
||
| 554 | 573 | Value::Array( |
|
| 555 | 574 | b.objects |
|
| 556 | 575 | .iter() |
|
| 576 | + | .chain(&texts) |
|
| 557 | 577 | .map(|(t, body)| { |
|
| 558 | 578 | Value::Array(vec![ |
|
| 559 | 579 | Value::Text(t.name().into()), |
|
| … | 13 unchanged lines |
||
| 573 | 593 | pub fn bundle_from_value(v: &Value) -> Result<Bundle> { |
|
| 574 | 594 | let m = map(v, "bundle")?; |
|
| 575 | 595 | let mut b = Bundle::default(); |
|
| 576 | - | for c in o::array(field(m, 0, "changes")?, "changes")? { |
|
| 577 | - | let pair = o::array(c, "change entry")?; |
|
| 578 | - | if pair.len() != 2 { |
|
| 579 | - | return Err(schema("change entry: expected [change, sigs]")); |
|
| 580 | - | } |
|
| 581 | - | b.changes.push(( |
|
| 582 | - | Change::decode(o::bytes(&pair[0], "change")?)?, |
|
| 583 | - | sigs_from(&pair[1])?, |
|
| 584 | - | )); |
|
| 585 | - | } |
|
| 586 | - | for a in o::array(field(m, 1, "attests")?, "attests")? { |
|
| 587 | - | b.attests.push(attest_from(a)?); |
|
| 588 | - | } |
|
| 589 | 596 | for ob in o::array(field(m, 2, "objects")?, "objects")? { |
|
| 590 | 597 | let pair = o::array(ob, "object")?; |
|
| 591 | 598 | if pair.len() != 2 { |
|
| … | 3 unchanged lines |
||
| 595 | 602 | .ok_or_else(|| schema("unknown object type"))?; |
|
| 596 | 603 | b.objects |
|
| 597 | 604 | .push((ty, o::bytes(&pair[1], "object body")?.to_vec())); |
|
| 605 | + | } |
|
| 606 | + | // Stored inserts are read from the bundle's own objects. |
|
| 607 | + | let mut by_ref: Option<std::collections::HashMap<ObjectRef, usize>> = None; |
|
| 608 | + | for c in o::array(field(m, 0, "changes")?, "changes")? { |
|
| 609 | + | let pair = o::array(c, "change entry")?; |
|
| 610 | + | if pair.len() != 2 { |
|
| 611 | + | return Err(schema("change entry: expected [change, sigs]")); |
|
| 612 | + | } |
|
| 613 | + | let change = Change::decode_with(o::bytes(&pair[0], "change")?, &mut |text, count| { |
|
| 614 | + | let by_ref = by_ref.get_or_insert_with(|| { |
|
| 615 | + | b.objects |
|
| 616 | + | .iter() |
|
| 617 | + | .enumerate() |
|
| 618 | + | .map(|(i, (ty, body))| (crate::hash::hash_object(*ty, body), i)) |
|
| 619 | + | .collect() |
|
| 620 | + | }); |
|
| 621 | + | let get = |
|
| 622 | + | |r: &ObjectRef, want: ObjectType| match by_ref.get(r).map(|i| &b.objects[*i]) { |
|
| 623 | + | Some((ty, body)) if *ty == want => Ok(body), |
|
| 624 | + | _ => Err(ObjectError::Schema(format!( |
|
| 625 | + | "the bundle lacks {} {}", |
|
| 626 | + | want.name(), |
|
| 627 | + | r.short(12) |
|
| 628 | + | ))), |
|
| 629 | + | }; |
|
| 630 | + | let blob = crate::objects::Blob::decode(get(text, ObjectType::Blob)?)?; |
|
| 631 | + | let mut content = Vec::with_capacity(blob.length as usize); |
|
| 632 | + | for chunk in &blob.chunks { |
|
| 633 | + | content.extend_from_slice(get(chunk, ObjectType::Chunk)?); |
|
| 634 | + | } |
|
| 635 | + | crate::objects::text_lines(&content, count) |
|
| 636 | + | })?; |
|
| 637 | + | b.changes.push((change, sigs_from(&pair[1])?)); |
|
| 638 | + | } |
|
| 639 | + | for a in o::array(field(m, 1, "attests")?, "attests")? { |
|
| 640 | + | b.attests.push(attest_from(a)?); |
|
| 598 | 641 | } |
|
| 599 | 642 | if let Some(ps) = m.get(&3) { |
|
| 600 | 643 | for p in o::array(ps, "policies")? { |
|
| … | 458 unchanged lines |
modified crates/oxy-core/src/repo/fsck.rs +4 −1
| … | 87 unchanged lines |
||
| 88 | 88 | let r = match ty { |
|
| 89 | 89 | ObjectType::Chunk => Ok(()), |
|
| 90 | 90 | ObjectType::Blob => Blob::decode(body).map(|_| ()), |
|
| 91 | - | ObjectType::Change => Change::decode(body).map(|_| ()), |
|
| 91 | + | // Structure only: the text blobs are checked with the change graph. |
|
| 92 | + | ObjectType::Change => { |
|
| 93 | + | Change::decode_with(body, &mut |_, _| Ok(vec![Vec::new()])).map(|_| ()) |
|
| 94 | + | } |
|
| 92 | 95 | ObjectType::Checkpoint => crate::objects::Checkpoint::decode(body).map(|_| ()), |
|
| 93 | 96 | ObjectType::Op => match Op::decode(body) { |
|
| 94 | 97 | Ok(_) => Ok(()), |
|
| … | 373 unchanged lines |
modified crates/oxy-core/src/repo/gc.rs +5 −2
| … | 129 unchanged lines |
||
| 130 | 130 | } |
|
| 131 | 131 | // Beyond the shallow boundary, or pruned under an earlier |
|
| 132 | 132 | // retention, there is nothing to keep. |
|
| 133 | - | let c = match self.store.get_change(&h) { |
|
| 134 | - | Ok(c) => c, |
|
| 133 | + | let c = match self.store.get_change_parts(&h) { |
|
| 134 | + | Ok((c, texts)) => { |
|
| 135 | + | keep.extend(texts); |
|
| 136 | + | c |
|
| 137 | + | } |
|
| 135 | 138 | Err(StoreError::NotFound(_)) => continue, |
|
| 136 | 139 | Err(e) => return Err(e.into()), |
|
| 137 | 140 | }; |
|
| … | 31 unchanged lines |
modified crates/oxy-core/src/repo/git.rs +1 −0
| … | 820 unchanged lines |
||
| 821 | 821 | gc.sha, gc.author |
|
| 822 | 822 | )); |
|
| 823 | 823 | let mut change = Change { |
|
| 824 | + | version: crate::objects::CHANGE_VERSION, |
|
| 824 | 825 | change_id: change_id_for(&gc.sha, &gc.message), |
|
| 825 | 826 | deps: vec![], |
|
| 826 | 827 | author: ObjectRef::ZERO, |
|
| … | 448 unchanged lines |
modified crates/oxy-core/src/repo/history.rs +7 −0
| … | 233 unchanged lines |
||
| 234 | 234 | let mut deps: BTreeSet<ChangeHash> = old.deps.iter().copied().collect(); |
|
| 235 | 235 | deps.extend(built.contributors.iter().copied()); |
|
| 236 | 236 | let mut new = Change { |
|
| 237 | + | version: crate::objects::CHANGE_VERSION, |
|
| 237 | 238 | change_id: old.change_id, |
|
| 238 | 239 | deps: vec![], |
|
| 239 | 240 | author: self.author(), |
|
| … | 260 unchanged lines |
||
| 500 | 501 | }); |
|
| 501 | 502 | } |
|
| 502 | 503 | let mut new = Change { |
|
| 504 | + | version: crate::objects::CHANGE_VERSION, |
|
| 503 | 505 | change_id: old.change_id, |
|
| 504 | 506 | deps: vec![], |
|
| 505 | 507 | author: self.author(), |
|
| … | 101 unchanged lines |
||
| 607 | 609 | return fail("the named paths are not touched by that change"); |
|
| 608 | 610 | } |
|
| 609 | 611 | let mut c1 = Change { |
|
| 612 | + | version: crate::objects::CHANGE_VERSION, |
|
| 610 | 613 | change_id: ChangeId::random(), |
|
| 611 | 614 | deps: old.deps.clone(), |
|
| 612 | 615 | author: old.author, |
|
| … | 23 unchanged lines |
||
| 636 | 639 | ); |
|
| 637 | 640 | } |
|
| 638 | 641 | let mut c2 = Change { |
|
| 642 | + | version: crate::objects::CHANGE_VERSION, |
|
| 639 | 643 | change_id: old.change_id, |
|
| 640 | 644 | deps: vec![], |
|
| 641 | 645 | author: old.author, |
|
| … | 106 unchanged lines |
||
| 748 | 752 | } |
|
| 749 | 753 | } |
|
| 750 | 754 | let mut c1 = Change { |
|
| 755 | + | version: crate::objects::CHANGE_VERSION, |
|
| 751 | 756 | change_id: ChangeId::random(), |
|
| 752 | 757 | deps: old.deps.clone(), |
|
| 753 | 758 | author: old.author, |
|
| … | 254 unchanged lines |
||
| 1008 | 1013 | }); |
|
| 1009 | 1014 | } |
|
| 1010 | 1015 | let mut new = Change { |
|
| 1016 | + | version: crate::objects::CHANGE_VERSION, |
|
| 1011 | 1017 | change_id: dst.change_id, |
|
| 1012 | 1018 | deps: vec![], |
|
| 1013 | 1019 | author: dst.author, |
|
| … | 149 unchanged lines |
||
| 1163 | 1169 | ); |
|
| 1164 | 1170 | } |
|
| 1165 | 1171 | let mut new = Change { |
|
| 1172 | + | version: crate::objects::CHANGE_VERSION, |
|
| 1166 | 1173 | change_id: old.change_id, |
|
| 1167 | 1174 | deps: vec![], |
|
| 1168 | 1175 | author: old.author, |
|
| … | 27 unchanged lines |
modified crates/oxy-core/src/repo/hosted.rs +1 −0
| … | 121 unchanged lines |
||
| 122 | 122 | return fail("the edits change nothing"); |
|
| 123 | 123 | } |
|
| 124 | 124 | let mut change = Change { |
|
| 125 | + | version: crate::objects::CHANGE_VERSION, |
|
| 125 | 126 | change_id: ChangeId::random(), |
|
| 126 | 127 | deps: vec![], |
|
| 127 | 128 | author, |
|
| … | 453 unchanged lines |
modified crates/oxy-core/src/repo/mod.rs +2 −7
| … | 562 unchanged lines |
||
| 563 | 563 | impl Repo { |
|
| 564 | 564 | fn new_working_copy(&self, deps: Vec<ChangeHash>, message: &str) -> Change { |
|
| 565 | 565 | let mut c = Change { |
|
| 566 | + | version: crate::objects::CHANGE_VERSION, |
|
| 566 | 567 | change_id: ChangeId::random(), |
|
| 567 | 568 | deps, |
|
| 568 | 569 | author: self.author(), |
|
| … | 318 unchanged lines |
||
| 887 | 888 | // ------------------------------------------------------------ blobs |
|
| 888 | 889 | ||
| 889 | 890 | fn blob_for(content: &[u8]) -> Blob { |
|
| 890 | - | Blob { |
|
| 891 | - | length: content.len() as u64, |
|
| 892 | - | chunks: crate::chunk::chunks(content) |
|
| 893 | - | .into_iter() |
|
| 894 | - | .map(|c| hash_object(ObjectType::Chunk, c)) |
|
| 895 | - | .collect(), |
|
| 896 | - | } |
|
| 891 | + | Blob::of(content) |
|
| 897 | 892 | } |
|
| 898 | 893 | ||
| 899 | 894 | pub fn blob_ref(content: &[u8]) -> ObjectRef { |
|
| … | 742 unchanged lines |
modified crates/oxy-core/src/repo/snapshot.rs +2 −0
| … | 369 unchanged lines |
||
| 370 | 370 | } |
|
| 371 | 371 | ||
| 372 | 372 | let mut wc = Change { |
|
| 373 | + | version: crate::objects::CHANGE_VERSION, |
|
| 373 | 374 | change_id: old_wc.change_id, |
|
| 374 | 375 | deps: vec![], |
|
| 375 | 376 | author: self.author(), |
|
| … | 257 unchanged lines |
||
| 633 | 634 | deps.insert(*d); |
|
| 634 | 635 | } |
|
| 635 | 636 | let mut change = Change { |
|
| 637 | + | version: crate::objects::CHANGE_VERSION, |
|
| 636 | 638 | change_id: if partial { |
|
| 637 | 639 | ChangeId::random() |
|
| 638 | 640 | } else { |
|
| … | 1669 unchanged lines |
modified crates/oxy-core/src/repo/tests.rs +55 −0
| … | 5512 unchanged lines |
||
| 5513 | 5513 | repo.snapshot_status("status").unwrap(); |
|
| 5514 | 5514 | assert_ne!(fs::read(&path).unwrap(), first); |
|
| 5515 | 5515 | } |
|
| 5516 | + | ||
| 5517 | + | #[test] |
|
| 5518 | + | fn large_text_files_travel_and_survive_gc_as_text_blobs() { |
|
| 5519 | + | hermetic(); |
|
| 5520 | + | let dir = tempfile::tempdir().unwrap(); |
|
| 5521 | + | let root = dir.path(); |
|
| 5522 | + | let origin_path = root.join("origin"); |
|
| 5523 | + | Repo::init(&origin_path).unwrap(); |
|
| 5524 | + | let origin_url = origin_path.to_string_lossy().to_string(); |
|
| 5525 | + | let a = Repo::clone(&origin_url, &root.join("a")).unwrap(); |
|
| 5526 | + | let big: String = (0..5000).map(|i| format!("line {i}\n")).collect(); |
|
| 5527 | + | write(&root.join("a"), "big.txt", big.as_bytes()); |
|
| 5528 | + | write(&root.join("a"), "small.txt", b"small\n"); |
|
| 5529 | + | let h1 = a.commit("large", &[]).unwrap(); |
|
| 5530 | + | let (_, body) = a.store().get(&h1).unwrap(); |
|
| 5531 | + | assert!(body.len() < 2048, "the change is {} bytes", body.len()); |
|
| 5532 | + | assert!(a.push("origin", false).unwrap()[0].ok); |
|
| 5533 | + | ||
| 5534 | + | // A clone reads the text from the blobs that came with the change. |
|
| 5535 | + | let b = Repo::clone(&origin_url, &root.join("b")).unwrap(); |
|
| 5536 | + | assert_eq!(fs::read(root.join("b/big.txt")).unwrap(), big.as_bytes()); |
|
| 5537 | + | // An edit in the middle of the stored insert is an ordinary change. |
|
| 5538 | + | let edited = big.replace("line 2500\n", "line 2500, edited\n"); |
|
| 5539 | + | write(&root.join("b"), "big.txt", edited.as_bytes()); |
|
| 5540 | + | let h2 = b.commit("edit", &[]).unwrap(); |
|
| 5541 | + | assert!(b.store().get_change(&h2).unwrap().edits.len() <= 2); |
|
| 5542 | + | assert!(b.push("origin", false).unwrap()[0].ok); |
|
| 5543 | + | assert!(a.pull("origin").unwrap().checked_out); |
|
| 5544 | + | assert_eq!(fs::read(root.join("a/big.txt")).unwrap(), edited.as_bytes()); |
|
| 5545 | + | assert_eq!( |
|
| 5546 | + | a.fsck().unwrap().errors(), |
|
| 5547 | + | 0, |
|
| 5548 | + | "{:?}", |
|
| 5549 | + | a.fsck().unwrap().problems |
|
| 5550 | + | ); |
|
| 5551 | + | ||
| 5552 | + | // With zero retention gc keeps the text blobs of every kept change. |
|
| 5553 | + | let mut a = Repo::open(&root.join("a")).unwrap(); |
|
| 5554 | + | a.config.set("core.op-retention", "0").unwrap(); |
|
| 5555 | + | a.save_config().unwrap(); |
|
| 5556 | + | let a = Repo::open(&root.join("a")).unwrap(); |
|
| 5557 | + | a.gc(true).unwrap(); |
|
| 5558 | + | let a = Repo::open(&root.join("a")).unwrap(); |
|
| 5559 | + | assert_eq!(a.store().get_change(&h1).unwrap().message, "large"); |
|
| 5560 | + | assert_eq!( |
|
| 5561 | + | a.fsck().unwrap().errors(), |
|
| 5562 | + | 0, |
|
| 5563 | + | "{:?}", |
|
| 5564 | + | a.fsck().unwrap().problems |
|
| 5565 | + | ); |
|
| 5566 | + | // And a clone of the packed repository reads them from its packs. |
|
| 5567 | + | let c = Repo::clone(&root.join("a").to_string_lossy(), &root.join("c")).unwrap(); |
|
| 5568 | + | assert_eq!(fs::read(root.join("c/big.txt")).unwrap(), edited.as_bytes()); |
|
| 5569 | + | drop(c); |
|
| 5570 | + | } |
modified crates/oxy-core/src/rewrite.rs +1 −0
| … | 453 unchanged lines |
||
| 454 | 454 | ||
| 455 | 455 | fn change(deps: Vec<ChangeHash>, tree_ops: Vec<TreeOp>, edits: Vec<Edit>, msg: &str) -> Change { |
|
| 456 | 456 | let mut c = Change { |
|
| 457 | + | version: crate::objects::CHANGE_VERSION, |
|
| 457 | 458 | change_id: ChangeId::random(), |
|
| 458 | 459 | deps, |
|
| 459 | 460 | author: ObjectRef::ZERO, |
|
| … | 314 unchanged lines |
modified crates/oxy-core/src/state.rs +1 −0
| … | 1083 unchanged lines |
||
| 1084 | 1084 | ||
| 1085 | 1085 | fn change(deps: Vec<ChangeHash>, tree_ops: Vec<TreeOp>, edits: Vec<Edit>) -> Change { |
|
| 1086 | 1086 | let mut c = Change { |
|
| 1087 | + | version: crate::objects::CHANGE_VERSION, |
|
| 1087 | 1088 | change_id: ChangeId::random(), |
|
| 1088 | 1089 | deps, |
|
| 1089 | 1090 | author: ObjectRef::ZERO, |
|
| … | 695 unchanged lines |
modified crates/oxy-core/src/store.rs +122 −4
| … | 10 unchanged lines |
||
| 11 | 11 | use crate::attest::Attest; |
|
| 12 | 12 | use crate::hash::{hash_object, header, ObjectRef, ObjectType}; |
|
| 13 | 13 | use crate::identity::{Identity, Signature}; |
|
| 14 | - | use crate::objects::{Change, ObjectError, StateObject}; |
|
| 14 | + | use crate::objects::{Blob, Change, ObjectError, StateObject}; |
|
| 15 | 15 | use crate::receipt::Receipt; |
|
| 16 | 16 | use rand::RngCore; |
|
| 17 | 17 | use std::cell::RefCell; |
|
| … | 148 unchanged lines |
||
| 166 | 166 | WrongType(ObjectRef, &'static str, &'static str), |
|
| 167 | 167 | #[error("object {0} not found")] |
|
| 168 | 168 | NotFound(ObjectRef), |
|
| 169 | - | #[error("a {kind} object of {size} bytes is larger than the {limit} bytes an object may be; nothing was stored. A first commit of a very large tree makes one change holding every text line: commit it in parts (a directory at a time)")] |
|
| 169 | + | #[error("a {kind} object of {size} bytes is larger than the {limit} bytes an object may be; nothing was stored. A change this large adds or touches too many files at once: commit it in parts (a directory at a time)")] |
|
| 170 | 170 | TooLarge { |
|
| 171 | 171 | kind: &'static str, |
|
| 172 | 172 | size: usize, |
|
| … | 700 unchanged lines |
||
| 873 | 873 | Ok(body) |
|
| 874 | 874 | } |
|
| 875 | 875 | ||
| 876 | + | /// Store a change and the text blobs (and their chunks) its large |
|
| 877 | + | /// inserts are stored as (spec §6.1). |
|
| 876 | 878 | pub fn put_change(&self, c: &Change) -> Result<ObjectRef> { |
|
| 877 | - | self.put(ObjectType::Change, &c.encode()) |
|
| 879 | + | let (bytes, texts) = c.encode_parts(); |
|
| 880 | + | for t in texts { |
|
| 881 | + | self.put_text(&t)?; |
|
| 882 | + | } |
|
| 883 | + | self.put(ObjectType::Change, &bytes) |
|
| 884 | + | } |
|
| 885 | + | ||
| 886 | + | fn put_text(&self, t: &crate::objects::StoredText) -> Result<ObjectRef> { |
|
| 887 | + | let r = t.blob.hash(); |
|
| 888 | + | if self.has(&r) { |
|
| 889 | + | return Ok(r); |
|
| 890 | + | } |
|
| 891 | + | for c in crate::chunk::chunks(&t.content) { |
|
| 892 | + | self.put_chunk(c)?; |
|
| 893 | + | } |
|
| 894 | + | self.put(ObjectType::Blob, &t.blob.encode()) |
|
| 878 | 895 | } |
|
| 879 | 896 | ||
| 880 | 897 | pub fn get_change(&self, r: &ObjectRef) -> Result<Change> { |
|
| 881 | - | Ok(Change::decode(&self.get_typed(r, ObjectType::Change)?)?) |
|
| 898 | + | Ok(self.get_change_parts(r)?.0) |
|
| 899 | + | } |
|
| 900 | + | ||
| 901 | + | /// A change and the objects its stored inserts are made of: each text |
|
| 902 | + | /// blob and its chunks, which travel and are kept with it. |
|
| 903 | + | pub fn get_change_parts(&self, r: &ObjectRef) -> Result<(Change, Vec<ObjectRef>)> { |
|
| 904 | + | let bytes = self.get_typed(r, ObjectType::Change)?; |
|
| 905 | + | let mut parts = Vec::new(); |
|
| 906 | + | let mut failed = None; |
|
| 907 | + | let decoded = Change::decode_with(&bytes, &mut |text, count| match self.read_text(text) { |
|
| 908 | + | Ok((blob, content)) => { |
|
| 909 | + | parts.push(*text); |
|
| 910 | + | parts.extend(blob.chunks); |
|
| 911 | + | crate::objects::text_lines(&content, count) |
|
| 912 | + | } |
|
| 913 | + | Err(e) => { |
|
| 914 | + | let why = e.to_string(); |
|
| 915 | + | failed = Some(e); |
|
| 916 | + | Err(ObjectError::Schema(format!( |
|
| 917 | + | "text blob {}: {why}", |
|
| 918 | + | text.short(12) |
|
| 919 | + | ))) |
|
| 920 | + | } |
|
| 921 | + | }); |
|
| 922 | + | match (decoded, failed) { |
|
| 923 | + | (Ok(c), _) => Ok((c, parts)), |
|
| 924 | + | (Err(_), Some(StoreError::NotFound(t))) => Err(StoreError::Corrupt( |
|
| 925 | + | *r, |
|
| 926 | + | format!("its text blob {} is missing", t.short(12)), |
|
| 927 | + | )), |
|
| 928 | + | (Err(e), _) => Err(StoreError::Corrupt(*r, e.to_string())), |
|
| 929 | + | } |
|
| 930 | + | } |
|
| 931 | + | ||
| 932 | + | fn read_text(&self, r: &ObjectRef) -> Result<(Blob, Vec<u8>)> { |
|
| 933 | + | let blob = Blob::decode(&self.get_typed(r, ObjectType::Blob)?)?; |
|
| 934 | + | let mut content = Vec::with_capacity(blob.length as usize); |
|
| 935 | + | for c in &blob.chunks { |
|
| 936 | + | content.extend(self.get_typed(c, ObjectType::Chunk)?); |
|
| 937 | + | } |
|
| 938 | + | Ok((blob, content)) |
|
| 882 | 939 | } |
|
| 883 | 940 | ||
| 884 | 941 | pub fn put_chunk(&self, bytes: &[u8]) -> Result<ObjectRef> { |
|
| … | 678 unchanged lines |
||
| 1563 | 1620 | // The store still opens and reads what was written. |
|
| 1564 | 1621 | let again = Store::open(dir.path()).unwrap(); |
|
| 1565 | 1622 | again.get(&hash_object(ObjectType::Blob, b"small")).unwrap(); |
|
| 1623 | + | } |
|
| 1624 | + | } |
|
| 1625 | + | ||
| 1626 | + | #[cfg(test)] |
|
| 1627 | + | mod text_tests { |
|
| 1628 | + | use super::*; |
|
| 1629 | + | use crate::objects::{AtomRef, Edit, CHANGE_VERSION}; |
|
| 1630 | + | ||
| 1631 | + | fn large_change() -> Change { |
|
| 1632 | + | let mut c = crate::objects::tests::sample_change(); |
|
| 1633 | + | assert_eq!(c.version, CHANGE_VERSION); |
|
| 1634 | + | c.edits[0] = Edit::Insert { |
|
| 1635 | + | node: crate::ids::NodeId([7; 16]), |
|
| 1636 | + | after: AtomRef::Start, |
|
| 1637 | + | before: AtomRef::End, |
|
| 1638 | + | lines: (0..2000) |
|
| 1639 | + | .map(|i| format!("line {i}\n").into_bytes()) |
|
| 1640 | + | .collect(), |
|
| 1641 | + | }; |
|
| 1642 | + | c |
|
| 1643 | + | } |
|
| 1644 | + | ||
| 1645 | + | #[test] |
|
| 1646 | + | fn a_large_insert_is_stored_beside_its_change_and_read_back() { |
|
| 1647 | + | let dir = tempfile::tempdir().unwrap(); |
|
| 1648 | + | let s = Store::open(dir.path()).unwrap(); |
|
| 1649 | + | let c = large_change(); |
|
| 1650 | + | let r = s.put_change(&c).unwrap(); |
|
| 1651 | + | assert_eq!(r, c.hash()); |
|
| 1652 | + | let (_, body) = s.get(&r).unwrap(); |
|
| 1653 | + | assert!( |
|
| 1654 | + | body.len() < 1024, |
|
| 1655 | + | "the change holds a reference, not {} bytes of lines", |
|
| 1656 | + | body.len() |
|
| 1657 | + | ); |
|
| 1658 | + | let (back, parts) = s.get_change_parts(&r).unwrap(); |
|
| 1659 | + | assert_eq!(back, c); |
|
| 1660 | + | // The text blob and its chunk. |
|
| 1661 | + | assert_eq!(parts.len(), 2); |
|
| 1662 | + | for p in &parts { |
|
| 1663 | + | assert!(s.has(p)); |
|
| 1664 | + | } |
|
| 1665 | + | // Storing it again writes nothing new. |
|
| 1666 | + | let n = s.list().unwrap().len(); |
|
| 1667 | + | s.put_change(&c).unwrap(); |
|
| 1668 | + | assert_eq!(s.list().unwrap().len(), n); |
|
| 1669 | + | } |
|
| 1670 | + | ||
| 1671 | + | #[test] |
|
| 1672 | + | fn a_change_whose_text_blob_is_missing_is_reported_not_misread() { |
|
| 1673 | + | let dir = tempfile::tempdir().unwrap(); |
|
| 1674 | + | let s = Store::open(dir.path()).unwrap(); |
|
| 1675 | + | let c = large_change(); |
|
| 1676 | + | let r = s.put_change(&c).unwrap(); |
|
| 1677 | + | let (_, parts) = s.get_change_parts(&r).unwrap(); |
|
| 1678 | + | fs::remove_file(s.path_for(&parts[0])).unwrap(); |
|
| 1679 | + | let e = s.get_change(&r).unwrap_err(); |
|
| 1680 | + | assert!( |
|
| 1681 | + | matches!(&e, StoreError::Corrupt(h, why) if *h == r && why.contains("missing")), |
|
| 1682 | + | "{e}" |
|
| 1683 | + | ); |
|
| 1566 | 1684 | } |
|
| 1567 | 1685 | } |
modified docs/spec.md +15 −13
| … | 1 unchanged lines |
||
| 2 | 2 | ||
| 3 | 3 | | | | |
|
| 4 | 4 | |---|---| |
|
| 5 | - | | **Status** | Draft 0.8p | |
|
| 6 | - | | **Format version** | 1 | |
|
| 7 | - | | **Date** | 2026-09-26 | |
|
| 5 | + | | **Status** | Draft 0.8q | |
|
| 6 | + | | **Format version** | 1 (changes: 2) | |
|
| 7 | + | | **Date** | 2026-09-29 | |
|
| 8 | 8 | | **Audience** | Implementers, security reviewers, and contributors | |
|
| 9 | 9 | ||
| 10 | 10 | The key words MUST, MUST NOT, SHOULD, SHOULD NOT, and MAY are to be interpreted as described in RFC 2119. |
|
| … | 169 unchanged lines |
||
| 180 | 180 | | Item | Encoding | |
|
| 181 | 181 | |---|---| |
|
| 182 | 182 | | `TreeOp` | Map with key 0 = variant tag: 0 `AddNode`, 1 `RemoveNode`, 2 `Move`, 3 `SetMode`; key 1 = node id; `AddNode` adds 2 kind, 3 mode, 4 parent, 5 name; `RemoveNode` adds 2 placement ref; `Move` adds 2 old placement ref, 4 parent, 5 name; `SetMode` adds 2 old mode ref, 3 mode. | |
|
| 183 | - | | `Edit` | Map with key 0 = variant tag: 0 `Insert`, 1 `Delete`, 2 `Replace`; key 1 = node id; `Insert` adds 2 after, 3 before, 4 lines (array of byte strings) or 5 `lines_blob`; `Delete` adds 2 atom ranges; `Replace` adds 2 old (bytes or null), 3 new (bytes or null). | |
|
| 183 | + | | `Edit` | Map with key 0 = variant tag: 0 `Insert`, 1 `Delete`, 2 `Replace`; key 1 = node id; `Insert` adds 2 after, 3 before, and either 4 lines (array of byte strings) or, in a version 2 change, 5 text (the text blob's ObjectRef) and 6 count (the number of lines); `Delete` adds 2 atom ranges; `Replace` adds 2 old (bytes or null), 3 new (bytes or null). | |
|
| 184 | 184 | | `NodeKind` | Unsigned integer: 0 file, 1 dir, 2 symlink, 3 subrepo (§7.8). | |
|
| 185 | 185 | | Subrepo pin | The opaque content of a `subrepo` node: a CBOR map `{0: 1, 1: kind, 2: locator, 3: pin, 4: bookmark}` where `kind` is 0 for an Oxygen repository (`locator` = repository id bytes(16), `pin` = a state object's heads as `[ChangeHash]`) or 1 for a Git repository (`locator` = null, `pin` = commit sha as text); `bookmark` is the branch or bookmark name the pin was taken from. | |
|
| 186 | 186 | | `Mode` | Unsigned integer bit field: bit 0 executable, bit 1 opaque content mode. Directories carry 0. | |
|
| … | 12 unchanged lines |
||
| 199 | 199 | ||
| 200 | 200 | ``` |
|
| 201 | 201 | Change { |
|
| 202 | - | version [0]: 1 |
|
| 202 | + | version [0]: 1 or 2 |
|
| 203 | 203 | change_id [1]: bytes(16) // random, CSPRNG; see §6.3 |
|
| 204 | 204 | deps [2]: [ChangeHash] // sorted, unique; see §8 |
|
| 205 | 205 | author [3]: KeyId // ObjectRef of an identity object |
|
| … | 2 unchanged lines |
||
| 208 | 208 | tree_ops [6]: [TreeOp] // §7.2 |
|
| 209 | 209 | edits [7]: [Edit] // §7.4 |
|
| 210 | 210 | kind [8]: 0 = normal, 1 = resolution, 2 = working-copy |
|
| 211 | - | extra [9]: map // reserved; MUST be empty in v1 |
|
| 211 | + | extra [9]: map // reserved; MUST be empty |
|
| 212 | 212 | } |
|
| 213 | 213 | ``` |
|
| 214 | + | ||
| 215 | + | Writers produce version 2. Versions 1 and 2 differ only in how an `Insert` holds its lines (§7.4): a version 1 change carries every inserted line inline, and a version 2 change stores each large insert as a **text blob** beside it, so no change grows with the size of the files it adds. Readers MUST accept both. A change keeps the version it was made in: rewriting its encoding would change its hash and invalidate its signatures. |
|
| 214 | 216 | ||
| 215 | 217 | ### 6.2 Two identifiers |
|
| 216 | 218 | ||
| … | 47 unchanged lines |
||
| 264 | 266 | ### 7.4 Edits |
|
| 265 | 267 | ||
| 266 | 268 | ``` |
|
| 267 | - | Edit = Insert { node: NodeId, after: AtomRef, before: AtomRef, lines: [bytes] | lines_blob: ObjectRef } |
|
| 269 | + | Edit = Insert { node: NodeId, after: AtomRef, before: AtomRef, lines: [bytes] | text: ObjectRef, count: u32 } |
|
| 268 | 270 | | Delete { node: NodeId, atoms: [AtomRange] } |
|
| 269 | 271 | | Replace { node: NodeId, old: ObjectRef | null, new: ObjectRef } // opaque nodes only |
|
| 270 | 272 | AtomRef = START | END | AtomId |
|
| … | 2 unchanged lines |
||
| 273 | 275 | ||
| 274 | 276 | - `Insert` introduces `len(lines)` new atoms, indexed consecutively, and edges `after → first`, `last → before`. `after` and `before` MUST be adjacent in the author's view at authoring time; the pair is the insert's **anchor**. |
|
| 275 | 277 | - Atoms introduced by the same change are referenced with the all-zero "self" hash. This is how a change can insert a line and then insert another after it without knowing its own hash. |
|
| 276 | - | - `lines_blob` MAY replace inline `lines` when the inserted content exceeds 64 KiB; the blob's content is split into atoms by the same line rule. |
|
| 278 | + | - **Text blobs.** In a version 2 change, an insert whose lines encode as a canonical CBOR array of byte strings to at least 4096 bytes MUST be stored as `text` and `count`: `text` is the blob (§13.2) whose content is exactly that encoding, and `count` is the number of lines, at least 1. A shorter insert MUST be inline. The rule is deterministic, so a change has one encoding and one hash, and identical inserts share their text blob. A reader rejects an inline insert that should have been stored, a text blob shorter than 4096 bytes, and a text blob whose lines do not number `count`. A text blob and its chunks belong to their change: they are carried with it by every transfer (§16.3), kept with it by garbage collection (§21), and checked with it by `fsck`. A change cannot be read without them, so they are never withheld from a partial clone (§13.5). |
|
| 277 | 279 | - `Replace` is the only edit for `opaque` nodes. `old` is the blob currently expected; two concurrent `Replace` operations with the same `old` and different `new` conflict (§9.3). |
|
| 278 | 280 | ||
| 279 | 281 | ### 7.5 Opaque nodes |
|
| … | 254 unchanged lines |
||
| 534 | 536 | Blob { version [0]: 1, length [1]: u64, chunks [2]: [ObjectRef] } |
|
| 535 | 537 | ``` |
|
| 536 | 538 | ||
| 537 | - | Chunks and blobs are the only object types that can be large. Every other object type MUST be under 1 MiB after encoding; a change exceeding that MUST use `lines_blob`. |
|
| 539 | + | Chunks and blobs are the objects that carry content. Other objects are small in practice; a change holds its tree operations and inserts of under 4096 bytes, with larger inserts stored as text blobs (§7.4). No object may be larger than 1 GiB after encoding: a writer MUST refuse to store one and nothing of it is written. |
|
| 538 | 540 | ||
| 539 | 541 | ### 13.3 Compression |
|
| 540 | 542 | ||
| … | 211 unchanged lines |
||
| 752 | 754 | | Message | Encoding | |
|
| 753 | 755 | |---|---| |
|
| 754 | 756 | | Signed attestation | `[attest bytes, [Signature]]` | |
|
| 755 | - | | `Bundle` | `{0: [[change bytes, [Signature]]], 1: [signed attestation], 2: [[type name, object bytes]], 3: [signed policy]}`; changes in dependency order; objects are chunks, blobs, identities, and states only; key 3 (optional) holds the policies between the receiver's serial and the one sent with a push, ascending | |
|
| 757 | + | | `Bundle` | `{0: [[change bytes, [Signature]]], 1: [signed attestation], 2: [[type name, object bytes]], 3: [signed policy]}`; changes in dependency order; objects are chunks, blobs, identities, and states only, and include the text blobs of every change in the bundle and their chunks, so a bundle can be read on its own; key 3 (optional) holds the policies between the receiver's serial and the one sent with a push, ascending | |
|
| 756 | 758 | | `capabilities` response | `{0: [versions], 1: repo id bytes(16), 2: [feature names]}` | |
|
| 757 | 759 | | Signed policy | `[policy bytes, [Signature]]` | |
|
| 758 | 760 | | `refs` response | `{0: [{0: name, 1: state ref, 2: [heads], 3: signed attestation or null, 4: last serial or null}], 1: repo id, 2: signed policy or null, 3: [tag], 4: [signed policy]}`; key 4 (optional) lists earlier policies ascending by serial; the attestation is present only when it describes the current state; a tag is `{0: name, 1: state ref, 2: [heads], 3: signed attestation or null}` | |
|
| … | 62 unchanged lines |
||
| 821 | 823 | ||
| 822 | 824 | ## 21. Garbage collection |
|
| 823 | 825 | ||
| 824 | - | An object is **reachable** if it is referenced, directly or transitively, from any bookmark, tag, policy, the current operation heads, any operation newer than `core.op-retention`, any workspace's working-copy change, or any checkpoint of a reachable state. `oxy gc` deletes unreachable objects that are older than `core.gc-grace` (default 14 days, to protect concurrent writers) and repacks. Tombstone atoms are never collected independently of their change. Divergent changes are reachable if any of their variants is. A seal is reachable if any change it covers is reachable, and reference attestations are reachable while they are the latest for their reference or are within `core.op-retention`. |
|
| 826 | + | An object is **reachable** if it is referenced, directly or transitively, from any bookmark, tag, policy, the current operation heads, any operation newer than `core.op-retention`, any workspace's working-copy change, or any checkpoint of a reachable state. `oxy gc` deletes unreachable objects that are older than `core.gc-grace` (default 14 days, to protect concurrent writers) and repacks. Tombstone atoms are never collected independently of their change. Divergent changes are reachable if any of their variants is. A change's text blobs and their chunks are reachable with it (§7.4). A seal is reachable if any change it covers is reachable, and reference attestations are reachable while they are the latest for their reference or are within `core.op-retention`. |
|
| 825 | 827 | ||
| 826 | 828 | ### 21.1 Integrity check |
|
| 827 | 829 | ||
| 828 | - | `oxy fsck` reads everything and changes nothing. It checks (1) every stored object: header, length, ObjectRef, and that the body decodes as its type; (2) the operation log: every operation reachable from the head through all parents is present and decodes, and no operation's clock is earlier than its parent's (a warning); (3) the current view's bookmarks, tags, remote bookmarks, workspaces and policy, and the dependency closure of every change they name, with each change's author identity, blobs and chunks, and each committed change's signature or seal (§14.4); (4) that every bookmark forms a valid state, that every checkpoint restores exactly the state of the changes it names (§11), and that reference and tag attestations carry valid signatures. A change beyond the shallow boundary (§17) may be absent; a blob absent from a partial clone (`filter.max-blob` or a sparse filter) is a warning, not an error. Each problem names the object it concerns. The exit status is 1 when any error is found and 0 otherwise; `--json` gives the counts and problems. |
|
| 830 | + | `oxy fsck` reads everything and changes nothing. It checks (1) every stored object: header, length, ObjectRef, and that the body decodes as its type; (2) the operation log: every operation reachable from the head through all parents is present and decodes, and no operation's clock is earlier than its parent's (a warning); (3) the current view's bookmarks, tags, remote bookmarks, workspaces and policy, and the dependency closure of every change they name, with each change's author identity, text blobs, blobs and chunks, and each committed change's signature or seal (§14.4); (4) that every bookmark forms a valid state, that every checkpoint restores exactly the state of the changes it names (§11), and that reference and tag attestations carry valid signatures. A change beyond the shallow boundary (§17) may be absent; a blob absent from a partial clone (`filter.max-blob` or a sparse filter) is a warning, not an error. Each problem names the object it concerns. The exit status is 1 when any error is found and 0 otherwise; `--json` gives the counts and problems. |
|
| 829 | 831 | ||
| 830 | 832 | ### 21.2 Doctor |
|
| 831 | 833 | ||
| … | 140 unchanged lines |
||
| 972 | 974 | ||
| 973 | 975 | --- |
|
| 974 | 976 | ||
| 975 | - | *Changelog.* Draft 0.8p (2026-09-29): Git import derives new NodeIds from the commit, making imports deterministic (§23). Draft 0.8o (2026-09-29): execution receipts, the `receipt` object and attestation (§14.6). Draft 0.8n (2026-09-29): line history, `oxy log -L` (§27). Draft 0.8m (2026-09-29): resolving replace conflicts (§9.3). Draft 0.8l (2026-09-28): deleting a reference on a remote; first serials from the clock (§16.4). Draft 0.8k (2026-09-28): the manifest records graph keys, so unchanged files are neither read nor rendered (§12.4). Draft 0.8j (2026-09-28): checkpoint payload version 2, file graphs by reference (§11). |
|
| 977 | + | *Changelog.* Draft 0.8q (2026-09-29): change format version 2 stores large inserts as text blobs, so a change does not grow with the files it adds (§6.1, §7.4); no object may exceed 1 GiB (§13.2). Draft 0.8p (2026-09-29): Git import derives new NodeIds from the commit, making imports deterministic (§23). Draft 0.8o (2026-09-29): execution receipts, the `receipt` object and attestation (§14.6). Draft 0.8n (2026-09-29): line history, `oxy log -L` (§27). Draft 0.8m (2026-09-29): resolving replace conflicts (§9.3). Draft 0.8l (2026-09-28): deleting a reference on a remote; first serials from the clock (§16.4). Draft 0.8k (2026-09-28): the manifest records graph keys, so unchanged files are neither read nor rendered (§12.4). Draft 0.8j (2026-09-28): checkpoint payload version 2, file graphs by reference (§11). |
|
| 976 | 978 | ||
| 977 | 979 | Draft 0.8i (2026-09-28): portability rules for exec bits and path names (§7.7); found by verifying a real Git import commit by commit: deletions depend on the inserters of the lines right after them, and replacements on the change that set their old blob (§8.1); replace records are superseded causally, so a reverted binary keeps its blob (§9.3); merges resolve opaque conflicts to the commit's blob, and `oxy git verify` (§23). Draft 0.8h (2026-09-28): `oxy fsck` (§21.1); durability rules and the operation head as commit point (§13.6); the operation head moves by compare-and-swap and concurrent operations are merged (§12.1); `oxy doctor` (§21.2). Draft 0.8g (2026-09-27): delegates of a rule's identities may sign reference attestations (§14.5); local-path pushes bind unbound repositories like HTTP ones. Draft 0.8f (2026-09-27): challenge signatures (§14.3) for hosts. Draft 0.8e (2026-09-27): anonymous changes (zero author) are authenticated by a seal from any key, so imported and pre-identity history can be pushed under a policy (§14.4). Draft 0.8d (2026-09-27): unbound hosted repositories adopt the first pusher's id (§16.1). Draft 0.8c (2026-09-27): bare repositories (`oxy init --bare`, §12.2: no workspace, no working copy; hosting) and the reference server as an embeddable library (§15.1). Draft 0.8b (2026-09-27): the machine interface for editors (§24): `root`, `cat`, `version`, `hunks`, `discard`, and `--json` on the reporting commands. |
|
| 978 | 980 | ||
| … | 61 unchanged lines |