258 lines · 9 KBtext/plain; charset=utf-8
Onset: version control where nobody waits and nothing gets lost. The on command, its core and onset-server.
| 6 | //! many thousands of each, from fixed seeds so a failure repeats. |
| 7 |
| 8 | use onset_core::bundle::{self, Frame}; |
| 9 | use onset_core::git; |
| 10 | use onset_core::object::{self, Kind, Object}; |
| 11 | use onset_core::tree::{self, EntryKind, TreeEntry}; |
| 12 | use onset_core::{Id, MemSource}; |
| 13 |
| 14 | struct Rng(u64); |
| 15 |
| 16 | impl Rng { |
| 17 | fn next(&mut self) -> u64 { |
| 18 | // xorshift64* |
| 19 | self.0 ^= self.0 >> 12; |
| 20 | self.0 ^= self.0 << 25; |
| 21 | self.0 ^= self.0 >> 27; |
| 22 | self.0.wrapping_mul(0x2545_F491_4F6C_DD1D) |
| 23 | } |
| 24 |
| 25 | fn below(&mut self, n: usize) -> usize { |
| 26 | if n == 0 { 0 } else { (self.next() % n as u64) as usize } |
| 27 | } |
| 28 |
| 29 | fn bytes(&mut self, n: usize) -> Vec<u8> { |
| 30 | (0..n).map(|_| self.next() as u8).collect() |
| 31 | } |
| 32 | } |
| 33 |
| 34 | /// `seed` with a few random changes. |
| 35 | fn mutate(rng: &mut Rng, seed: &[u8]) -> Vec<u8> { |
| 36 | let mut out = seed.to_vec(); |
| 37 | for _ in 0..1 + rng.below(6) { |
| 38 | let at = rng.below(out.len() + 1); |
| 39 | match rng.below(7) { |
| 40 | 0 if !out.is_empty() => { |
| 41 | let i = rng.below(out.len()); |
| 42 | out[i] ^= 1 << rng.below(8); |
| 43 | } |
| 44 | 1 => out.insert(at, rng.next() as u8), |
| 45 | 2 if at < out.len() => { |
| 46 | let end = (at + 1 + rng.below(16)).min(out.len()); |
| 47 | out.drain(at..end); |
| 48 | } |
| 49 | 3 => out.truncate(at), |
| 50 | 4 if at < out.len() => { |
| 51 | let end = (at + 1 + rng.below(32)).min(out.len()); |
| 52 | let piece = out[at..end].to_vec(); |
| 53 | let to = rng.below(out.len() + 1); |
| 54 | out.splice(to..to, piece); |
| 55 | } |
| 56 | 5 if !out.is_empty() => { |
| 57 | // Sizes and counts: the extremes. |
| 58 | let i = rng.below(out.len()); |
| 59 | out[i] = if rng.below(2) == 0 { 0xff } else { 0x00 }; |
| 60 | } |
| 61 | _ => { |
| 62 | let n = rng.below(8); |
| 63 | let extra = rng.bytes(n); |
| 64 | out.splice(at..at, extra); |
| 65 | } |
| 66 | } |
| 67 | } |
| 68 | out |
| 69 | } |
| 70 |
| 71 | /// ONSET_FUZZ_SCALE=20 runs twenty times as many, with other seeds. |
| 72 | fn scale() -> u64 { |
| 73 | std::env::var("ONSET_FUZZ_SCALE").ok().and_then(|s| s.parse().ok()).unwrap_or(1).max(1) |
| 74 | } |
| 75 |
| 76 | fn each_input(seeds: &[Vec<u8>], rounds: usize, salt: u64, mut f: impl FnMut(&[u8])) { |
| 77 | let rounds = rounds * scale() as usize; |
| 78 | let mut rng = Rng(0x9E37_79B9_7F4A_7C15 ^ salt ^ scale().wrapping_mul(0x1000_0001)); |
| 79 | for seed in seeds { |
| 80 | f(seed); |
| 81 | } |
| 82 | for i in 0..rounds { |
| 83 | let input = if i % 5 == 4 { |
| 84 | let n = rng.below(256); |
| 85 | rng.bytes(n) |
| 86 | } else { |
| 87 | mutate(&mut rng, &seeds[i % seeds.len()]) |
| 88 | }; |
| 89 | f(&input); |
| 90 | } |
| 91 | } |
| 92 |
| 93 | fn tree_bytes() -> Vec<u8> { |
| 94 | let e = |name: &str, kind, b: u8| TreeEntry { name: name.into(), kind, id: Id([b; 32]) }; |
| 95 | tree::encode(&[e("README.md", EntryKind::File, 1), e("src", EntryKind::Tree, 2), e("run.sh", EntryKind::Exec, 3), e("link", EntryKind::Link, 4), e("lib", EntryKind::Gitlink, 5)]) |
| 96 | } |
| 97 |
| 98 | #[test] |
| 99 | fn bundles() { |
| 100 | let objects = [Object::blob(b"hello\n".to_vec()), Object::new(Kind::Tree, tree_bytes()), Object::blob(vec![])]; |
| 101 | let mut seed = Vec::new(); |
| 102 | bundle::write_header(&mut seed); |
| 103 | for o in &objects { |
| 104 | bundle::write_frame(&mut seed, &Frame::raw(o)); |
| 105 | } |
| 106 | bundle::write_end(&mut seed); |
| 107 | assert_eq!(bundle::read(&seed).unwrap().len(), 3); |
| 108 | each_input(&[seed], 40_000, 1, |input| { |
| 109 | if let Ok(frames) = bundle::read(input) { |
| 110 | for f in frames { |
| 111 | let _ = bundle::verify(&f, &f.payload); |
| 112 | } |
| 113 | } |
| 114 | }); |
| 115 | } |
| 116 |
| 117 | #[test] |
| 118 | fn trees() { |
| 119 | let seed = tree_bytes(); |
| 120 | assert_eq!(tree::decode(&seed).unwrap().len(), 5); |
| 121 | each_input(&[seed], 40_000, 2, |input| { |
| 122 | if let Ok(entries) = tree::decode(input) { |
| 123 | // Whatever decodes encodes again without trouble. |
| 124 | let _ = tree::encode(&entries); |
| 125 | } |
| 126 | }); |
| 127 | } |
| 128 |
| 129 | #[test] |
| 130 | fn trees_read_through_a_source() { |
| 131 | // Merges, diffs and edits over a tree whose bytes are hostile. |
| 132 | let mut rng = Rng(3); |
| 133 | let seed = tree_bytes(); |
| 134 | for _ in 0..5_000 { |
| 135 | let mut src = MemSource::default(); |
| 136 | let bad = src.put(Object::new(Kind::Tree, mutate(&mut rng, &seed))); |
| 137 | let good = src.put(Object::new(Kind::Tree, seed.clone())); |
| 138 | let _ = tree::flatten(&src, &bad); |
| 139 | let _ = tree::diff_trees(&src, &good, &bad); |
| 140 | let _ = tree::unsafe_path(&src, &good, &bad); |
| 141 | let _ = tree::edit(&src, &bad, &[tree::Put { path: "src/new.txt".into(), kind: EntryKind::File, content: b"x".to_vec() }], &["README.md".into()]); |
| 142 | let _ = onset_core::merge::trees(&src, Some(&good), &bad, &good, onset_core::merge::Mode::Land, ("a", "b")); |
| 143 | } |
| 144 | } |
| 145 |
| 146 | #[test] |
| 147 | fn chunk_lists() { |
| 148 | let seed = object::encode_chunks(&[(Id([1; 32]), 65_536), (Id([2; 32]), 12)]); |
| 149 | assert_eq!(object::decode_chunks(&seed).unwrap().len(), 2); |
| 150 | each_input(&[seed], 40_000, 4, |input| { |
| 151 | let _ = object::decode_chunks(input); |
| 152 | }); |
| 153 | } |
| 154 |
| 155 | /// A small pack with whole objects and both kinds of delta, as git sends. |
| 156 | fn pack_bytes() -> Vec<u8> { |
| 157 | use sha1::{Digest, Sha1}; |
| 158 | use std::io::Write; |
| 159 | let deflate = |data: &[u8]| { |
| 160 | let mut z = flate2::write::ZlibEncoder::new(Vec::new(), flate2::Compression::fast()); |
| 161 | z.write_all(data).unwrap(); |
| 162 | z.finish().unwrap() |
| 163 | }; |
| 164 | let header = |code: u8, size: usize| { |
| 165 | let mut out = Vec::new(); |
| 166 | let mut b = (code << 4) | (size & 15) as u8; |
| 167 | let mut rest = size >> 4; |
| 168 | while rest > 0 { |
| 169 | out.push(b | 0x80); |
| 170 | b = (rest & 0x7f) as u8; |
| 171 | rest >>= 7; |
| 172 | } |
| 173 | out.push(b); |
| 174 | out |
| 175 | }; |
| 176 | let base = b"line one\nline two\n".repeat(4); |
| 177 | let mut delta = vec![base.len() as u8, (base.len() + 4) as u8, 0x90, base.len() as u8, 4]; |
| 178 | delta.extend_from_slice(b"end\n"); |
| 179 | let mut pack = b"PACK\0\0\0\x02\0\0\0\x03".to_vec(); |
| 180 | let base_at = pack.len(); |
| 181 | pack.extend(header(3, base.len())); |
| 182 | pack.extend(deflate(&base)); |
| 183 | let at = pack.len(); |
| 184 | pack.extend(header(6, delta.len())); |
| 185 | pack.push((at - base_at) as u8); |
| 186 | pack.extend(deflate(&delta)); |
| 187 | pack.extend(header(7, delta.len())); |
| 188 | pack.extend(git::object_id(git::GitKind::Blob, &base)); |
| 189 | pack.extend(deflate(&delta)); |
| 190 | let sum = Sha1::digest(&pack); |
| 191 | pack.extend_from_slice(&sum); |
| 192 | pack |
| 193 | } |
| 194 |
| 195 | #[test] |
| 196 | fn git_packs() { |
| 197 | let seed = pack_bytes(); |
| 198 | assert_eq!(git::read_pack(&seed, 1 << 20).unwrap().objects.len(), 2); |
| 199 | each_input(&[seed], 20_000, 5, |input| { |
| 200 | let _ = git::read_pack(input, 1 << 20); |
| 201 | }); |
| 202 | // With the checksum fixed after each change, so the parser itself is reached. |
| 203 | let mut rng = Rng(6); |
| 204 | let seed = pack_bytes(); |
| 205 | for _ in 0..20_000 { |
| 206 | use sha1::{Digest, Sha1}; |
| 207 | let mut body = mutate(&mut rng, &seed[..seed.len() - 20]); |
| 208 | if body.len() < 12 { |
| 209 | continue; |
| 210 | } |
| 211 | body[..4].copy_from_slice(b"PACK"); |
| 212 | let sum = Sha1::digest(&body); |
| 213 | body.extend_from_slice(&sum); |
| 214 | if let Ok(pack) = git::read_pack(&body, 1 << 20) { |
| 215 | for (kind, data) in pack.objects.values() { |
| 216 | if *kind == git::GitKind::Commit { |
| 217 | let _ = git::Commit::parse(data); |
| 218 | } |
| 219 | } |
| 220 | } |
| 221 | } |
| 222 | } |
| 223 |
| 224 | #[test] |
| 225 | fn git_deltas_commits_and_trees() { |
| 226 | let base = b"0123456789abcdef".repeat(4); |
| 227 | let mut delta = vec![base.len() as u8, 20, 0x91, 4, 16]; |
| 228 | delta.extend_from_slice(&[4]); |
| 229 | delta.extend_from_slice(b"tail"); |
| 230 | assert_eq!(git::apply_delta(&base, &delta, 1 << 20).unwrap().len(), 20); |
| 231 | each_input(&[delta], 40_000, 7, |input| { |
| 232 | let _ = git::apply_delta(&base, input, 1 << 20); |
| 233 | }); |
| 234 | let commit = b"tree 0123456789012345678901234567890123456789\nparent 0123456789012345678901234567890123456789\nauthor A <a@b.c> 1700000000 +0000\ncommitter A <a@b.c> 1700000000 +0000\n\nTitle\n\nBody\n".to_vec(); |
| 235 | assert!(git::Commit::parse(&commit).is_ok()); |
| 236 | each_input(&[commit], 40_000, 8, |input| { |
| 237 | let _ = git::Commit::parse(input); |
| 238 | }); |
| 239 | let mut gtree = b"100644 a.txt\0".to_vec(); |
| 240 | gtree.extend_from_slice(&[1; 20]); |
| 241 | gtree.extend_from_slice(b"40000 src\0"); |
| 242 | gtree.extend_from_slice(&[2; 20]); |
| 243 | assert_eq!(git::tree_entries(>ree).unwrap().len(), 2); |
| 244 | each_input(&[gtree.clone()], 40_000, 9, |input| { |
| 245 | let _ = git::tree_entries(input); |
| 246 | }); |
| 247 | // Converting a hostile git tree into an Onset tree. |
| 248 | let mut rng = Rng(10); |
| 249 | for _ in 0..10_000 { |
| 250 | let data = mutate(&mut rng, >ree); |
| 251 | let id = git::object_id(git::GitKind::Tree, &data); |
| 252 | let mut pack = git::Pack::default(); |
| 253 | pack.objects.insert(id, (git::GitKind::Tree, data)); |
| 254 | let known = std::collections::HashMap::new(); |
| 255 | let _ = git::ToOnset::new(&pack, &known).tree(id, true); |
| 256 | } |
| 257 | } |
| 258 |