| 1 | //! Reading the objects in a git pack, as a push sends them, so that what a |
| 2 | //! push adds can be looked at before it is stored. |
| 3 | //! |
| 4 | //! A pushed pack is usually thin: some objects are deltas against objects |
| 5 | //! the repository already has. Those are left pending until the caller |
| 6 | //! supplies their bases with [`Pack::supply`]. |
| 7 | //! |
| 8 | //! Writing is the small part g1t needs for a merge it makes itself: a pack |
| 9 | //! of whole objects ([`write_pack`]), or one fetched from elsewhere with a |
| 10 | //! few objects added ([`extend_pack`]). |
| 11 | |
| 12 | use std::cell::RefCell; |
| 13 | use std::collections::{HashMap, VecDeque}; |
| 14 | use std::rc::Rc; |
| 15 | |
| 16 | use miniz_oxide::inflate::TINFLStatus; |
| 17 | use miniz_oxide::inflate::core::{DecompressorOxide, decompress, inflate_flags}; |
| 18 | use sha1::{Digest, Sha1}; |
| 19 | |
| 20 | /// Beyond this much content, counted as each object is in full (a delta |
| 21 | /// as the object it makes), the pack is not read: the work of reading |
| 22 | /// it, not the memory, which stays within [`CACHE_BYTES`] and the pack. |
| 23 | pub const MAX_INFLATED: usize = 512 * 1024 * 1024; |
| 24 | /// Objects kept inflated at a time, as bases for the deltas that follow |
| 25 | /// them. Others are inflated again from the pack when asked for. |
| 26 | const CACHE_BYTES: usize = 24 * 1024 * 1024; |
| 27 | |
| 28 | #[derive(Clone, Copy, Debug, PartialEq, Eq)] |
| 29 | pub enum ObjectKind { |
| 30 | Commit, |
| 31 | Tree, |
| 32 | Blob, |
| 33 | Tag, |
| 34 | } |
| 35 | |
| 36 | impl ObjectKind { |
| 37 | fn from_type(code: u8) -> Option<ObjectKind> { |
| 38 | Some(match code { |
| 39 | 1 => ObjectKind::Commit, |
| 40 | 2 => ObjectKind::Tree, |
| 41 | 3 => ObjectKind::Blob, |
| 42 | 4 => ObjectKind::Tag, |
| 43 | _ => return None, |
| 44 | }) |
| 45 | } |
| 46 | |
| 47 | /// The type code a pack gives objects of this kind. |
| 48 | fn code(self) -> u8 { |
| 49 | match self { |
| 50 | ObjectKind::Commit => 1, |
| 51 | ObjectKind::Tree => 2, |
| 52 | ObjectKind::Blob => 3, |
| 53 | ObjectKind::Tag => 4, |
| 54 | } |
| 55 | } |
| 56 | |
| 57 | fn name(self) -> &'static str { |
| 58 | match self { |
| 59 | ObjectKind::Commit => "commit", |
| 60 | ObjectKind::Tree => "tree", |
| 61 | ObjectKind::Blob => "blob", |
| 62 | ObjectKind::Tag => "tag", |
| 63 | } |
| 64 | } |
| 65 | } |
| 66 | |
| 67 | /// A git object's id: the SHA-1 of its header and content, in hex. |
| 68 | pub fn object_id(kind: ObjectKind, data: &[u8]) -> String { |
| 69 | let mut hasher = Sha1::new(); |
| 70 | hasher.update(format!("{} {}\0", kind.name(), data.len()).as_bytes()); |
| 71 | hasher.update(data); |
| 72 | hasher.finalize().iter().map(|byte| format!("{byte:02x}")).collect() |
| 73 | } |
| 74 | |
| 75 | enum Base { |
| 76 | /// An earlier entry in the pack, by its index. |
| 77 | Entry(usize), |
| 78 | /// Any object, by id. |
| 79 | Id(String), |
| 80 | } |
| 81 | |
| 82 | enum State { |
| 83 | /// Read, with its id known. |
| 84 | Known(ObjectKind), |
| 85 | /// A delta whose base is not known yet. |
| 86 | Waiting, |
| 87 | /// A delta that does not apply, or whose base is gone: dropped. |
| 88 | Dropped, |
| 89 | } |
| 90 | |
| 91 | /// An object read: its kind and its content, shared with the cache. |
| 92 | pub type Object = (ObjectKind, Rc<[u8]>); |
| 93 | |
| 94 | /// One entry of the pack, read in place. |
| 95 | struct Entry { |
| 96 | /// Where its compressed data starts. |
| 97 | data: usize, |
| 98 | /// Its inflated size: for a delta, the delta's. |
| 99 | size: usize, |
| 100 | base: Option<Base>, |
| 101 | state: State, |
| 102 | } |
| 103 | |
| 104 | /// Objects inflated lately, by entry, up to [`CACHE_BYTES`]; the first |
| 105 | /// kept is the first let go. |
| 106 | #[derive(Default)] |
| 107 | struct Cache { |
| 108 | objects: HashMap<usize, Rc<[u8]>>, |
| 109 | order: VecDeque<usize>, |
| 110 | bytes: usize, |
| 111 | budget: usize, |
| 112 | } |
| 113 | |
| 114 | impl Cache { |
| 115 | fn get(&self, entry: usize) -> Option<Rc<[u8]>> { |
| 116 | self.objects.get(&entry).cloned() |
| 117 | } |
| 118 | |
| 119 | fn keep(&mut self, entry: usize, data: Rc<[u8]>) { |
| 120 | if data.len() > self.budget || self.objects.contains_key(&entry) { |
| 121 | return; |
| 122 | } |
| 123 | while self.bytes + data.len() > self.budget { |
| 124 | let Some(oldest) = self.order.pop_front() else { break }; |
| 125 | if let Some(gone) = self.objects.remove(&oldest) { |
| 126 | self.bytes -= gone.len(); |
| 127 | } |
| 128 | } |
| 129 | self.bytes += data.len(); |
| 130 | self.order.push_back(entry); |
| 131 | self.objects.insert(entry, data); |
| 132 | } |
| 133 | } |
| 134 | |
| 135 | /// The objects of a pack, by id. The pack is kept as it came, compressed, |
| 136 | /// and an object is inflated (its deltas applied) when it is asked for: |
| 137 | /// what is held inflated at once stays within [`CACHE_BYTES`], however |
| 138 | /// much the pack holds. |
| 139 | #[derive(Default)] |
| 140 | pub struct Pack { |
| 141 | pack: Vec<u8>, |
| 142 | entries: Vec<Entry>, |
| 143 | /// Each object's entry, by id. |
| 144 | ids: HashMap<String, usize>, |
| 145 | /// Bases the repository supplied for a thin pack. |
| 146 | supplied: HashMap<String, Object>, |
| 147 | /// Commits, in the order they were read. |
| 148 | commits: Vec<String>, |
| 149 | cache: RefCell<Cache>, |
| 150 | } |
| 151 | |
| 152 | /// Where the pack starts in a receive-pack request: after the commands |
| 153 | /// and anything else sent as pkt-lines. |
| 154 | pub fn pack_start(body: &[u8]) -> Option<usize> { |
| 155 | let mut at = 0; |
| 156 | loop { |
| 157 | if body.get(at..at + 4) == Some(b"PACK") { |
| 158 | return Some(at); |
| 159 | } |
| 160 | let length = std::str::from_utf8(body.get(at..at + 4)?) |
| 161 | .ok() |
| 162 | .and_then(|hex| usize::from_str_radix(hex, 16).ok())?; |
| 163 | // A flush packet is four bytes; any other line counts its own length. |
| 164 | at += if length == 0 { 4 } else { length.max(4) }; |
| 165 | } |
| 166 | } |
| 167 | |
| 168 | fn inflate(input: &[u8], size: usize) -> Result<(Vec<u8>, usize), String> { |
| 169 | let mut out = vec![0u8; size.max(1)]; |
| 170 | let mut state = DecompressorOxide::new(); |
| 171 | let flags = inflate_flags::TINFL_FLAG_PARSE_ZLIB_HEADER | inflate_flags::TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF; |
| 172 | let (status, consumed, written) = decompress(&mut state, input, &mut out, 0, flags); |
| 173 | match status { |
| 174 | TINFLStatus::Done => { |
| 175 | out.truncate(written); |
| 176 | if written != size { |
| 177 | return Err(format!("an object inflated to {written} bytes, not {size}")); |
| 178 | } |
| 179 | Ok((out, consumed)) |
| 180 | } |
| 181 | other => Err(format!("an object could not be inflated: {other:?}")), |
| 182 | } |
| 183 | } |
| 184 | |
| 185 | fn varint(data: &[u8], at: &mut usize) -> Option<usize> { |
| 186 | let (mut value, mut shift) = (0usize, 0); |
| 187 | loop { |
| 188 | let byte = *data.get(*at)?; |
| 189 | *at += 1; |
| 190 | value |= ((byte & 0x7f) as usize) << shift; |
| 191 | shift += 7; |
| 192 | if byte & 0x80 == 0 || shift > 56 { |
| 193 | return Some(value); |
| 194 | } |
| 195 | } |
| 196 | } |
| 197 | |
| 198 | /// An entry's header in a pack: its type and its inflated size. |
| 199 | fn header(code: u8, size: usize) -> Vec<u8> { |
| 200 | let mut out = Vec::new(); |
| 201 | let mut byte = (code << 4) | (size & 15) as u8; |
| 202 | let mut rest = size >> 4; |
| 203 | while rest > 0 { |
| 204 | out.push(byte | 0x80); |
| 205 | byte = (rest & 0x7f) as u8; |
| 206 | rest >>= 7; |
| 207 | } |
| 208 | out.push(byte); |
| 209 | out |
| 210 | } |
| 211 | |
| 212 | fn write_entries(pack: &mut Vec<u8>, objects: &[(ObjectKind, Vec<u8>)]) { |
| 213 | for (kind, data) in objects { |
| 214 | pack.extend(header(kind.code(), data.len())); |
| 215 | pack.extend(miniz_oxide::deflate::compress_to_vec_zlib(data, 6)); |
| 216 | } |
| 217 | } |
| 218 | |
| 219 | fn seal(mut pack: Vec<u8>) -> Vec<u8> { |
| 220 | let checksum = Sha1::digest(&pack); |
| 221 | pack.extend_from_slice(&checksum); |
| 222 | pack |
| 223 | } |
| 224 | |
| 225 | /// A version 2 pack holding `objects` whole, with no deltas: what git's |
| 226 | /// receive-pack takes, when the objects are few and new. |
| 227 | pub fn write_pack(objects: &[(ObjectKind, Vec<u8>)]) -> Vec<u8> { |
| 228 | let mut pack = b"PACK".to_vec(); |
| 229 | pack.extend_from_slice(&2u32.to_be_bytes()); |
| 230 | pack.extend_from_slice(&(objects.len() as u32).to_be_bytes()); |
| 231 | write_entries(&mut pack, objects); |
| 232 | seal(pack) |
| 233 | } |
| 234 | |
| 235 | /// `pack` with `objects` added after its own, as one pack. Its entries keep |
| 236 | /// their offsets, since the header stays the same length, so its deltas |
| 237 | /// still find their bases. `pack` must not be thin. |
| 238 | pub fn extend_pack(pack: &[u8], objects: &[(ObjectKind, Vec<u8>)]) -> Result<Vec<u8>, String> { |
| 239 | if pack.len() < 32 || &pack[..4] != b"PACK" { |
| 240 | return Err("not a pack".into()); |
| 241 | } |
| 242 | let (body, trailer) = pack.split_at(pack.len() - 20); |
| 243 | if Sha1::digest(body).as_slice() != trailer { |
| 244 | return Err("the pack's checksum does not match".into()); |
| 245 | } |
| 246 | let count = u32::from_be_bytes([pack[8], pack[9], pack[10], pack[11]]) as usize; |
| 247 | let total = u32::try_from(count + objects.len()).map_err(|_| "the pack is too large")?; |
| 248 | let mut out = body.to_vec(); |
| 249 | out[8..12].copy_from_slice(&total.to_be_bytes()); |
| 250 | write_entries(&mut out, objects); |
| 251 | Ok(seal(out)) |
| 252 | } |
| 253 | |
| 254 | /// Applies a git delta to its base. |
| 255 | pub fn apply_delta(base: &[u8], delta: &[u8]) -> Result<Vec<u8>, String> { |
| 256 | let mut at = 0; |
| 257 | let bad = || "a delta is malformed".to_owned(); |
| 258 | let source = varint(delta, &mut at).ok_or_else(bad)?; |
| 259 | if source != base.len() { |
| 260 | return Err("a delta does not fit its base".into()); |
| 261 | } |
| 262 | let target = varint(delta, &mut at).ok_or_else(bad)?; |
| 263 | let mut out = Vec::with_capacity(target); |
| 264 | while at < delta.len() { |
| 265 | let op = delta[at]; |
| 266 | at += 1; |
| 267 | if op & 0x80 != 0 { |
| 268 | let mut offset = 0usize; |
| 269 | let mut size = 0usize; |
| 270 | for bit in 0..4 { |
| 271 | if op & (1 << bit) != 0 { |
| 272 | offset |= (*delta.get(at).ok_or_else(bad)? as usize) << (8 * bit); |
| 273 | at += 1; |
| 274 | } |
| 275 | } |
| 276 | for bit in 0..3 { |
| 277 | if op & (0x10 << bit) != 0 { |
| 278 | size |= (*delta.get(at).ok_or_else(bad)? as usize) << (8 * bit); |
| 279 | at += 1; |
| 280 | } |
| 281 | } |
| 282 | if size == 0 { |
| 283 | size = 0x10000; |
| 284 | } |
| 285 | out.extend_from_slice(base.get(offset..offset + size).ok_or_else(bad)?); |
| 286 | } else if op != 0 { |
| 287 | out.extend_from_slice(delta.get(at..at + op as usize).ok_or_else(bad)?); |
| 288 | at += op as usize; |
| 289 | } else { |
| 290 | return Err(bad()); |
| 291 | } |
| 292 | } |
| 293 | if out.len() != target { |
| 294 | return Err(bad()); |
| 295 | } |
| 296 | Ok(out) |
| 297 | } |
| 298 | |
| 299 | impl Pack { |
| 300 | /// Reads every object in `pack`, resolving the deltas whose bases are |
| 301 | /// in it. |
| 302 | pub fn parse(pack: &[u8]) -> Result<Pack, String> { |
| 303 | Pack::parse_within(pack, CACHE_BYTES) |
| 304 | } |
| 305 | |
| 306 | /// [`Pack::parse`], holding at most `cache` bytes inflated. |
| 307 | fn parse_within(pack: &[u8], cache: usize) -> Result<Pack, String> { |
| 308 | if pack.len() < 12 || &pack[..4] != b"PACK" { |
| 309 | return Err("not a pack".into()); |
| 310 | } |
| 311 | let count = u32::from_be_bytes([pack[8], pack[9], pack[10], pack[11]]) as usize; |
| 312 | let cache = RefCell::new(Cache { budget: cache, ..Cache::default() }); |
| 313 | let mut result = Pack { pack: pack.to_vec(), cache, ..Pack::default() }; |
| 314 | let mut at_offset: HashMap<usize, usize> = HashMap::new(); |
| 315 | let mut at = 12; |
| 316 | let mut inflated = 0usize; |
| 317 | for index in 0..count { |
| 318 | let start = at; |
| 319 | let mut byte = *pack.get(at).ok_or("the pack ends early")?; |
| 320 | at += 1; |
| 321 | let code = (byte >> 4) & 7; |
| 322 | let mut size = (byte & 15) as usize; |
| 323 | let mut shift = 4; |
| 324 | while byte & 0x80 != 0 { |
| 325 | byte = *pack.get(at).ok_or("the pack ends early")?; |
| 326 | at += 1; |
| 327 | size |= ((byte & 0x7f) as usize) << shift; |
| 328 | shift += 7; |
| 329 | } |
| 330 | let base = match code { |
| 331 | 6 => { |
| 332 | let mut byte = *pack.get(at).ok_or("the pack ends early")?; |
| 333 | at += 1; |
| 334 | let mut offset = (byte & 0x7f) as usize; |
| 335 | while byte & 0x80 != 0 { |
| 336 | byte = *pack.get(at).ok_or("the pack ends early")?; |
| 337 | at += 1; |
| 338 | offset = ((offset + 1) << 7) | (byte & 0x7f) as usize; |
| 339 | } |
| 340 | let base = start.checked_sub(offset).ok_or("a delta points before the pack")?; |
| 341 | Some(Base::Entry(*at_offset.get(&base).ok_or("a delta points between objects")?)) |
| 342 | } |
| 343 | 7 => { |
| 344 | let id = pack.get(at..at + 20).ok_or("the pack ends early")?; |
| 345 | at += 20; |
| 346 | Some(Base::Id(id.iter().map(|byte| format!("{byte:02x}")).collect())) |
| 347 | } |
| 348 | _ => None, |
| 349 | }; |
| 350 | let state = match base { |
| 351 | Some(_) => State::Waiting, |
| 352 | None => State::Known(ObjectKind::from_type(code).ok_or("an object has an unknown type")?), |
| 353 | }; |
| 354 | let (data, consumed) = inflate(&pack[at..], size)?; |
| 355 | result.entries.push(Entry { data: at, size, base, state }); |
| 356 | at_offset.insert(start, index); |
| 357 | at += consumed; |
| 358 | // Named now, while it is at hand: a whole object, or a delta |
| 359 | // whose base is known; a delta whose base is not, once it is. |
| 360 | inflated += match result.entries[index].state { |
| 361 | State::Known(kind) => { |
| 362 | let size = data.len(); |
| 363 | result.name(index, kind, data.into()); |
| 364 | size |
| 365 | } |
| 366 | _ => result.resolve_one(index, Some(data)).unwrap_or(0), |
| 367 | }; |
| 368 | if inflated > MAX_INFLATED { |
| 369 | return Err("the pack is too large to read".into()); |
| 370 | } |
| 371 | } |
| 372 | if inflated + result.resolve() > MAX_INFLATED { |
| 373 | return Err("the pack is too large to read".into()); |
| 374 | } |
| 375 | Ok(result) |
| 376 | } |
| 377 | |
| 378 | /// Records `entry` as the object `data` of `kind`, kept for the deltas |
| 379 | /// that may follow it. |
| 380 | fn name(&mut self, entry: usize, kind: ObjectKind, data: Rc<[u8]>) { |
| 381 | let id = object_id(kind, &data); |
| 382 | if kind == ObjectKind::Commit { |
| 383 | self.commits.push(id.clone()); |
| 384 | } |
| 385 | self.entries[entry].state = State::Known(kind); |
| 386 | self.ids.entry(id).or_insert(entry); |
| 387 | self.cache.get_mut().keep(entry, data); |
| 388 | } |
| 389 | |
| 390 | /// Names the waiting delta at `entry` (inflated already when `delta` |
| 391 | /// is given) if its base is known by now, and says how large the |
| 392 | /// object it makes is; drops it if it does not apply. `None` while it |
| 393 | /// waits. |
| 394 | fn resolve_one(&mut self, entry: usize, delta: Option<Vec<u8>>) -> Option<usize> { |
| 395 | match self.base_of(entry)? { |
| 396 | Ok((kind, base)) => match delta.map_or_else(|| self.inflate_entry(entry), Ok).and_then(|delta| apply_delta(&base, &delta)) { |
| 397 | Ok(data) => { |
| 398 | let size = data.len(); |
| 399 | self.name(entry, kind, data.into()); |
| 400 | Some(size) |
| 401 | } |
| 402 | Err(_) => { |
| 403 | self.entries[entry].state = State::Dropped; |
| 404 | Some(0) |
| 405 | } |
| 406 | }, |
| 407 | Err(()) => { |
| 408 | self.entries[entry].state = State::Dropped; |
| 409 | Some(0) |
| 410 | } |
| 411 | } |
| 412 | } |
| 413 | |
| 414 | /// The base of the delta at `entry`: `None` while it is not known, |
| 415 | /// `Err` when it was dropped. |
| 416 | fn base_of(&self, entry: usize) -> Option<Result<Object, ()>> { |
| 417 | let base = match self.entries[entry].base.as_ref()? { |
| 418 | Base::Entry(base) => *base, |
| 419 | Base::Id(id) => match self.supplied.get(id) { |
| 420 | Some((kind, data)) => return Some(Ok((*kind, data.clone()))), |
| 421 | None => *self.ids.get(id)?, |
| 422 | }, |
| 423 | }; |
| 424 | match self.entries[base].state { |
| 425 | State::Known(_) => Some(self.object_at(base).ok_or(())), |
| 426 | State::Waiting => None, |
| 427 | State::Dropped => Some(Err(())), |
| 428 | } |
| 429 | } |
| 430 | |
| 431 | /// Resolves every waiting delta whose base is known by now, and says |
| 432 | /// how much they made. |
| 433 | fn resolve(&mut self) -> usize { |
| 434 | let mut made = 0; |
| 435 | loop { |
| 436 | let mut progress = false; |
| 437 | for entry in 0..self.entries.len() { |
| 438 | if matches!(self.entries[entry].state, State::Waiting) |
| 439 | && let Some(size) = self.resolve_one(entry, None) |
| 440 | { |
| 441 | made += size; |
| 442 | progress = true; |
| 443 | } |
| 444 | } |
| 445 | if !progress { |
| 446 | return made; |
| 447 | } |
| 448 | } |
| 449 | } |
| 450 | |
| 451 | /// The stored data of `entry`, inflated: for a delta, the delta. |
| 452 | fn inflate_entry(&self, entry: usize) -> Result<Vec<u8>, String> { |
| 453 | let entry = &self.entries[entry]; |
| 454 | inflate(&self.pack[entry.data..], entry.size).map(|(data, _)| data) |
| 455 | } |
| 456 | |
| 457 | /// The object at a known `entry`, from the cache or inflated again |
| 458 | /// from the pack: down its chain of deltas to an object at hand, then |
| 459 | /// each delta applied on the way back up. |
| 460 | fn object_at(&self, entry: usize) -> Option<Object> { |
| 461 | let State::Known(kind) = self.entries[entry].state else { return None }; |
| 462 | let mut chain = Vec::new(); |
| 463 | let mut at = entry; |
| 464 | let mut data = loop { |
| 465 | if let Some(data) = self.cache.borrow().get(at) { |
| 466 | break data; |
| 467 | } |
| 468 | match self.entries[at].base.as_ref() { |
| 469 | None => break Rc::from(self.inflate_entry(at).ok()?), |
| 470 | Some(base) => { |
| 471 | chain.push(at); |
| 472 | match base { |
| 473 | Base::Entry(base) => at = *base, |
| 474 | Base::Id(id) => match self.supplied.get(id) { |
| 475 | Some((_, data)) => break data.clone(), |
| 476 | None => at = *self.ids.get(id)?, |
| 477 | }, |
| 478 | } |
| 479 | } |
| 480 | } |
| 481 | }; |
| 482 | while let Some(delta) = chain.pop() { |
| 483 | data = apply_delta(&data, &self.inflate_entry(delta).ok()?).ok()?.into(); |
| 484 | self.cache.borrow_mut().keep(delta, data.clone()); |
| 485 | } |
| 486 | Some((kind, data)) |
| 487 | } |
| 488 | |
| 489 | /// Objects the pack's deltas are based on that it does not hold: what |
| 490 | /// the repository has to supply. |
| 491 | pub fn missing_bases(&self) -> Vec<String> { |
| 492 | let mut ids: Vec<String> = self |
| 493 | .entries |
| 494 | .iter() |
| 495 | .filter(|entry| matches!(entry.state, State::Waiting)) |
| 496 | .filter_map(|entry| match &entry.base { |
| 497 | Some(Base::Id(id)) if !self.contains(id) => Some(id.clone()), |
| 498 | _ => None, |
| 499 | }) |
| 500 | .collect(); |
| 501 | ids.sort(); |
| 502 | ids.dedup(); |
| 503 | ids |
| 504 | } |
| 505 | |
| 506 | /// Supplies a base object from the repository, and resolves what |
| 507 | /// depends on it. |
| 508 | pub fn supply(&mut self, id: &str, kind: ObjectKind, data: Vec<u8>) { |
| 509 | self.supplied.insert(id.to_owned(), (kind, data.into())); |
| 510 | let _ = self.resolve(); |
| 511 | } |
| 512 | |
| 513 | /// Deltas still unresolved. |
| 514 | pub fn unresolved(&self) -> usize { |
| 515 | self.entries.iter().filter(|entry| matches!(entry.state, State::Waiting)).count() |
| 516 | } |
| 517 | |
| 518 | pub fn get(&self, id: &str) -> Option<Object> { |
| 519 | if let Some((kind, data)) = self.supplied.get(id) { |
| 520 | return Some((*kind, data.clone())); |
| 521 | } |
| 522 | self.object_at(*self.ids.get(id)?) |
| 523 | } |
| 524 | |
| 525 | pub fn contains(&self, id: &str) -> bool { |
| 526 | self.ids.contains_key(id) || self.supplied.contains_key(id) |
| 527 | } |
| 528 | |
| 529 | /// The commits in the pack: what the push adds. |
| 530 | pub fn commits(&self) -> &[String] { |
| 531 | &self.commits |
| 532 | } |
| 533 | |
| 534 | pub fn commit(&self, id: &str) -> Option<CommitInfo> { |
| 535 | match self.get(id)? { |
| 536 | (ObjectKind::Commit, data) => Some(parse_commit(&data)), |
| 537 | _ => None, |
| 538 | } |
| 539 | } |
| 540 | |
| 541 | pub fn tree(&self, id: &str) -> Option<Vec<TreeItem>> { |
| 542 | match self.get(id)? { |
| 543 | (ObjectKind::Tree, data) => Some(parse_tree(&data)), |
| 544 | _ => None, |
| 545 | } |
| 546 | } |
| 547 | |
| 548 | pub fn blob(&self, id: &str) -> Option<Rc<[u8]>> { |
| 549 | match self.get(id)? { |
| 550 | (ObjectKind::Blob, data) => Some(data), |
| 551 | _ => None, |
| 552 | } |
| 553 | } |
| 554 | |
| 555 | /// What the pack's own commits and trees say the objects they name |
| 556 | /// are: a commit's tree and parents, a tree's entries (submodules |
| 557 | /// left out). How a missing base can be asked for as what it is. |
| 558 | pub fn named_kinds(&self) -> HashMap<String, ObjectKind> { |
| 559 | let mut kinds = HashMap::new(); |
| 560 | let read = self.ids.values().filter(|entry| matches!(self.entries[**entry].state, State::Known(ObjectKind::Commit | ObjectKind::Tree))); |
| 561 | let objects = read.filter_map(|entry| self.object_at(*entry)).chain(self.supplied.values().cloned()); |
| 562 | for (kind, data) in objects { |
| 563 | let data = &data[..]; |
| 564 | match kind { |
| 565 | ObjectKind::Commit => { |
| 566 | let commit = parse_commit(data); |
| 567 | kinds.insert(commit.tree, ObjectKind::Tree); |
| 568 | kinds.extend(commit.parents.into_iter().map(|parent| (parent, ObjectKind::Commit))); |
| 569 | } |
| 570 | ObjectKind::Tree => { |
| 571 | for item in parse_tree(data) { |
| 572 | if item.is_tree() { |
| 573 | kinds.insert(item.id, ObjectKind::Tree); |
| 574 | } else if item.mode != "160000" { |
| 575 | kinds.insert(item.id, ObjectKind::Blob); |
| 576 | } |
| 577 | } |
| 578 | } |
| 579 | _ => {} |
| 580 | } |
| 581 | } |
| 582 | kinds |
| 583 | } |
| 584 | } |
| 585 | |
| 586 | /// What a commit says about its place in history, and whose it is. |
| 587 | #[derive(Debug, Default, PartialEq, Eq)] |
| 588 | pub struct CommitInfo { |
| 589 | pub tree: String, |
| 590 | pub parents: Vec<String>, |
| 591 | /// The address on the `author` line, as written. |
| 592 | pub author_email: Option<String>, |
| 593 | /// The address on the `committer` line, as written. |
| 594 | pub committer_email: Option<String>, |
| 595 | } |
| 596 | |
| 597 | /// The address in a signature line's value: `Name <address> 1700000000 +0000`. |
| 598 | fn signature_email(value: &str) -> Option<String> { |
| 599 | let start = value.rfind('<')?; |
| 600 | let end = start + value[start..].find('>')?; |
| 601 | Some(value[start + 1..end].trim().to_owned()) |
| 602 | } |
| 603 | |
| 604 | pub fn parse_commit(data: &[u8]) -> CommitInfo { |
| 605 | let text = String::from_utf8_lossy(data); |
| 606 | let mut info = CommitInfo::default(); |
| 607 | for line in text.lines() { |
| 608 | if line.is_empty() { |
| 609 | break; |
| 610 | } |
| 611 | if let Some(tree) = line.strip_prefix("tree ") { |
| 612 | info.tree = tree.trim().to_owned(); |
| 613 | } else if let Some(parent) = line.strip_prefix("parent ") { |
| 614 | info.parents.push(parent.trim().to_owned()); |
| 615 | } else if let Some(author) = line.strip_prefix("author ") { |
| 616 | info.author_email = signature_email(author); |
| 617 | } else if let Some(committer) = line.strip_prefix("committer ") { |
| 618 | info.committer_email = signature_email(committer); |
| 619 | } |
| 620 | } |
| 621 | info |
| 622 | } |
| 623 | |
| 624 | /// One entry of a tree. |
| 625 | #[derive(Clone, Debug, PartialEq, Eq)] |
| 626 | pub struct TreeItem { |
| 627 | /// `100644`, `100755`, `120000`, `40000` or `160000`. |
| 628 | pub mode: String, |
| 629 | pub name: String, |
| 630 | pub id: String, |
| 631 | } |
| 632 | |
| 633 | impl TreeItem { |
| 634 | pub fn is_tree(&self) -> bool { |
| 635 | self.mode == "40000" |
| 636 | } |
| 637 | |
| 638 | /// A regular or executable file; not a link or a submodule. |
| 639 | pub fn is_file(&self) -> bool { |
| 640 | self.mode.starts_with("100") |
| 641 | } |
| 642 | } |
| 643 | |
| 644 | pub fn parse_tree(data: &[u8]) -> Vec<TreeItem> { |
| 645 | let mut items = Vec::new(); |
| 646 | let mut at = 0; |
| 647 | while at < data.len() { |
| 648 | let Some(space) = data[at..].iter().position(|byte| *byte == b' ') else { |
| 649 | break; |
| 650 | }; |
| 651 | let Some(nul) = data[at + space..].iter().position(|byte| *byte == 0) else { |
| 652 | break; |
| 653 | }; |
| 654 | let mode = String::from_utf8_lossy(&data[at..at + space]).into_owned(); |
| 655 | let name = String::from_utf8_lossy(&data[at + space + 1..at + space + nul]).into_owned(); |
| 656 | let id_at = at + space + nul + 1; |
| 657 | let Some(id) = data.get(id_at..id_at + 20) else { |
| 658 | break; |
| 659 | }; |
| 660 | items.push(TreeItem { mode, name, id: id.iter().map(|byte| format!("{byte:02x}")).collect() }); |
| 661 | at = id_at + 20; |
| 662 | } |
| 663 | items |
| 664 | } |
| 665 | |
| 666 | /// A tree's bytes from its entries, as git writes them: what a delta |
| 667 | /// against a tree the repository has needs as its base. |
| 668 | pub fn encode_tree(items: &[TreeItem]) -> Vec<u8> { |
| 669 | let mut out = Vec::new(); |
| 670 | for item in items { |
| 671 | out.extend_from_slice(item.mode.as_bytes()); |
| 672 | out.push(b' '); |
| 673 | out.extend_from_slice(item.name.as_bytes()); |
| 674 | out.push(0); |
| 675 | for pair in item.id.as_bytes().chunks(2) { |
| 676 | out.push(u8::from_str_radix(std::str::from_utf8(pair).unwrap_or("00"), 16).unwrap_or(0)); |
| 677 | } |
| 678 | } |
| 679 | out |
| 680 | } |
| 681 | |
| 682 | #[cfg(test)] |
| 683 | pub(crate) mod tests { |
| 684 | use super::*; |
| 685 | use miniz_oxide::deflate::compress_to_vec_zlib; |
| 686 | |
| 687 | /// A pack of whole objects, plus ref-deltas given as (base id, delta). |
| 688 | pub fn build_pack(objects: &[(ObjectKind, Vec<u8>)], ref_deltas: &[(String, Vec<u8>)]) -> Vec<u8> { |
| 689 | let mut pack = b"PACK".to_vec(); |
| 690 | pack.extend_from_slice(&2u32.to_be_bytes()); |
| 691 | pack.extend_from_slice(&((objects.len() + ref_deltas.len()) as u32).to_be_bytes()); |
| 692 | for (kind, data) in objects { |
| 693 | pack.extend(header(kind.code(), data.len())); |
| 694 | pack.extend(compress_to_vec_zlib(data, 6)); |
| 695 | } |
| 696 | for (base, delta) in ref_deltas { |
| 697 | pack.extend(header(7, delta.len())); |
| 698 | for pair in base.as_bytes().chunks(2) { |
| 699 | pack.push(u8::from_str_radix(std::str::from_utf8(pair).unwrap(), 16).unwrap()); |
| 700 | } |
| 701 | pack.extend(compress_to_vec_zlib(delta, 6)); |
| 702 | } |
| 703 | pack.extend_from_slice(&[0u8; 20]); |
| 704 | pack |
| 705 | } |
| 706 | |
| 707 | /// A delta that keeps the first `keep` bytes of `base` and appends `tail`. |
| 708 | pub fn delta(base: &[u8], keep: usize, tail: &[u8]) -> Vec<u8> { |
| 709 | let mut out = Vec::new(); |
| 710 | let put = |mut value: usize, out: &mut Vec<u8>| loop { |
| 711 | let byte = (value & 0x7f) as u8; |
| 712 | value >>= 7; |
| 713 | if value == 0 { |
| 714 | out.push(byte); |
| 715 | break; |
| 716 | } |
| 717 | out.push(byte | 0x80); |
| 718 | }; |
| 719 | put(base.len(), &mut out); |
| 720 | put(keep + tail.len(), &mut out); |
| 721 | // Copy from offset 0, `keep` bytes (one size byte). |
| 722 | out.push(0x80 | 0x10); |
| 723 | out.push(keep as u8); |
| 724 | out.push(tail.len() as u8); |
| 725 | out.extend_from_slice(tail); |
| 726 | out |
| 727 | } |
| 728 | |
| 729 | #[test] |
| 730 | fn ids_match_git() { |
| 731 | assert_eq!(object_id(ObjectKind::Blob, b""), "e69de29bb2d1d6434b8b29ae775ad8c2e48c5391"); |
| 732 | assert_eq!(object_id(ObjectKind::Blob, b"hello\n"), "ce013625030ba8dba906f756967f9e9ca394464a"); |
| 733 | } |
| 734 | |
| 735 | #[test] |
| 736 | fn whole_objects_and_deltas_are_read() { |
| 737 | let base = b"first line\n".to_vec(); |
| 738 | let base_id = object_id(ObjectKind::Blob, &base); |
| 739 | let pack = build_pack(&[(ObjectKind::Blob, base.clone())], &[(base_id.clone(), delta(&base, base.len(), b"second\n"))]); |
| 740 | let parsed = Pack::parse(&pack).unwrap(); |
| 741 | let grown = b"first line\nsecond\n"; |
| 742 | assert_eq!(parsed.blob(&object_id(ObjectKind::Blob, grown)).as_deref(), Some(&grown[..])); |
| 743 | assert!(parsed.missing_bases().is_empty()); |
| 744 | } |
| 745 | |
| 746 | #[test] |
| 747 | fn a_chain_of_deltas_is_read_again_from_the_pack_once_let_go() { |
| 748 | // Each version a delta on the one before; nothing stays cached, so |
| 749 | // every read inflates the chain down to the whole object again. |
| 750 | let mut versions = vec![b"v0\n".to_vec()]; |
| 751 | let mut deltas = Vec::new(); |
| 752 | for n in 1..6 { |
| 753 | let before = versions.last().unwrap().clone(); |
| 754 | deltas.push((object_id(ObjectKind::Blob, &before), delta(&before, before.len(), format!("v{n}\n").as_bytes()))); |
| 755 | versions.push([before, format!("v{n}\n").into_bytes()].concat()); |
| 756 | } |
| 757 | let pack = Pack::parse_within(&build_pack(&[(ObjectKind::Blob, versions[0].clone())], &deltas), 0).unwrap(); |
| 758 | assert_eq!(pack.unresolved(), 0); |
| 759 | assert!(pack.cache.borrow().objects.is_empty()); |
| 760 | for version in versions.iter().rev() { |
| 761 | assert_eq!(pack.blob(&object_id(ObjectKind::Blob, version)).as_deref(), Some(&version[..])); |
| 762 | } |
| 763 | } |
| 764 | |
| 765 | #[test] |
| 766 | fn the_cache_lets_the_oldest_go_first() { |
| 767 | let mut cache = Cache { budget: 8, ..Cache::default() }; |
| 768 | cache.keep(0, Rc::from(&b"abcd"[..])); |
| 769 | cache.keep(1, Rc::from(&b"efgh"[..])); |
| 770 | cache.keep(2, Rc::from(&b"ij"[..])); |
| 771 | assert!(cache.get(0).is_none() && cache.get(1).is_some() && cache.get(2).is_some()); |
| 772 | assert_eq!(cache.bytes, 6); |
| 773 | // Larger than the whole budget: not kept, nothing let go for it. |
| 774 | cache.keep(3, Rc::from(&b"0123456789"[..])); |
| 775 | assert!(cache.get(3).is_none() && cache.get(1).is_some()); |
| 776 | } |
| 777 | |
| 778 | #[test] |
| 779 | fn a_thin_pack_waits_for_its_base() { |
| 780 | let base = b"kept in the repository\n".to_vec(); |
| 781 | let base_id = object_id(ObjectKind::Blob, &base); |
| 782 | let pack = build_pack(&[], &[(base_id.clone(), delta(&base, 4, b" and more\n"))]); |
| 783 | let mut parsed = Pack::parse(&pack).unwrap(); |
| 784 | assert_eq!(parsed.missing_bases(), vec![base_id.clone()]); |
| 785 | parsed.supply(&base_id, ObjectKind::Blob, base); |
| 786 | assert_eq!(parsed.unresolved(), 0); |
| 787 | assert!(parsed.blob(&object_id(ObjectKind::Blob, b"kept and more\n")).is_some()); |
| 788 | } |
| 789 | |
| 790 | #[test] |
| 791 | fn a_pack_says_what_the_objects_it_names_are() { |
| 792 | let blob_id = object_id(ObjectKind::Blob, b"x"); |
| 793 | let sub_id = "1".repeat(40); |
| 794 | let module_id = "2".repeat(40); |
| 795 | let tree = encode_tree(&[ |
| 796 | TreeItem { mode: "100644".into(), name: "a.txt".into(), id: blob_id.clone() }, |
| 797 | TreeItem { mode: "40000".into(), name: "src".into(), id: sub_id.clone() }, |
| 798 | TreeItem { mode: "160000".into(), name: "vendor".into(), id: module_id.clone() }, |
| 799 | ]); |
| 800 | let tree_id = object_id(ObjectKind::Tree, &tree); |
| 801 | let parent = "3".repeat(40); |
| 802 | let commit = format!("tree {tree_id}\nparent {parent}\nauthor A <a@x> 1 +0000\n\nm\n"); |
| 803 | let pack = Pack::parse(&build_pack(&[(ObjectKind::Tree, tree), (ObjectKind::Commit, commit.into_bytes())], &[])).unwrap(); |
| 804 | let kinds = pack.named_kinds(); |
| 805 | assert_eq!(kinds.get(&blob_id), Some(&ObjectKind::Blob)); |
| 806 | assert_eq!(kinds.get(&sub_id), Some(&ObjectKind::Tree)); |
| 807 | assert_eq!(kinds.get(&tree_id), Some(&ObjectKind::Tree)); |
| 808 | assert_eq!(kinds.get(&parent), Some(&ObjectKind::Commit)); |
| 809 | // A submodule's commit lives in another repository. |
| 810 | assert_eq!(kinds.get(&module_id), None); |
| 811 | } |
| 812 | |
| 813 | #[test] |
| 814 | fn commits_and_trees_are_parsed_and_trees_rebuilt() { |
| 815 | let blob_id = object_id(ObjectKind::Blob, b"x"); |
| 816 | let tree = encode_tree(&[ |
| 817 | TreeItem { mode: "100644".into(), name: "a.txt".into(), id: blob_id.clone() }, |
| 818 | TreeItem { mode: "40000".into(), name: "src".into(), id: blob_id.clone() }, |
| 819 | ]); |
| 820 | let items = parse_tree(&tree); |
| 821 | assert_eq!(items.len(), 2); |
| 822 | assert!(items[0].is_file() && items[1].is_tree()); |
| 823 | assert_eq!(encode_tree(&items), tree); |
| 824 | let commit = format!("tree {}\nparent aaaa\nparent bbbb\nauthor x\n\nmessage\nparent no\n", object_id(ObjectKind::Tree, &tree)); |
| 825 | let info = parse_commit(commit.as_bytes()); |
| 826 | assert_eq!(info.parents, ["aaaa", "bbbb"]); |
| 827 | assert_eq!(info.tree.len(), 40); |
| 828 | assert_eq!(info.author_email, None); |
| 829 | let signed = parse_commit( |
| 830 | b"tree t |
| 831 | author Ada L <Ada@Example.com> 1700000000 +0000 |
| 832 | committer Bot <bot@x.io> 1700000000 +0000 |
| 833 | |
| 834 | author <no@x.io> |
| 835 | ", |
| 836 | ); |
| 837 | assert_eq!(signed.author_email.as_deref(), Some("Ada@Example.com")); |
| 838 | assert_eq!(signed.committer_email.as_deref(), Some("bot@x.io")); |
| 839 | let pack = build_pack(&[(ObjectKind::Commit, commit.into_bytes())], &[]); |
| 840 | assert_eq!(Pack::parse(&pack).unwrap().commits().len(), 1); |
| 841 | } |
| 842 | |
| 843 | #[test] |
| 844 | fn the_pack_is_found_after_the_commands() { |
| 845 | let line = b"old new refs/heads/PACKAGING\0report-status\n"; |
| 846 | let commands = [format!("{:04x}", line.len() + 4).into_bytes(), line.to_vec(), b"0000".to_vec()].concat(); |
| 847 | let body = [commands.clone(), b"PACK\0\0\0\x02".to_vec()].concat(); |
| 848 | assert_eq!(pack_start(&body), Some(commands.len())); |
| 849 | assert_eq!(pack_start(&commands), None); |
| 850 | assert!(Pack::parse(b"nope").is_err()); |
| 851 | } |
| 852 | |
| 853 | #[test] |
| 854 | fn written_packs_are_sealed_and_extend() { |
| 855 | let blob = b"hello |
| 856 | ".to_vec(); |
| 857 | let pack = write_pack(&[(ObjectKind::Blob, blob.clone())]); |
| 858 | let (body, trailer) = pack.split_at(pack.len() - 20); |
| 859 | assert_eq!(Sha1::digest(body).as_slice(), trailer); |
| 860 | let more = extend_pack(&pack, &[(ObjectKind::Blob, b"more |
| 861 | ".to_vec())]).unwrap(); |
| 862 | assert_eq!(&more[8..12], &2u32.to_be_bytes()); |
| 863 | let read = Pack::parse(&more).unwrap(); |
| 864 | assert!(read.blob("ce013625030ba8dba906f756967f9e9ca394464a").is_some()); |
| 865 | assert!(read.blob(&object_id(ObjectKind::Blob, b"more |
| 866 | ")).is_some()); |
| 867 | let mut broken = pack.clone(); |
| 868 | broken[12] ^= 1; |
| 869 | assert!(extend_pack(&broken, &[]).is_err()); |
| 870 | } |
| 871 | } |