DEV Community: Caleb Sander

N-dimensional slices

Caleb Sander — Sat, 02 Jul 2022 23:51:41 +0000

In this post, I'll introduce the idea of an "N-dimensional slice" and explore different implementations in Rust. I hope to convince you that the "stride vector" approach is especially elegant and allows many common operations to avoid copying data. We'll start with matrices, the simplest case, and then see how the ideas generalize to any number of dimensions.

What is an N-dimensional slice?

Okay, before I start talking about "N-dimensional slices", I should probably give a definition. Let's start by considering a single possible value for N: 1. A 1-dimensional slice is a standard array or list. Each element has an index (consisting of 1 number). In Rust, we would represent this with the type &[T] (or &mut [T], Box<[T]>, etc. depending on the ownership).
If you're unfamiliar with "boxed slices" in Rust
Don't worry, I think Box<[T]> is underused in Rust code! It's similar to Vec<T>: it's an owned, heap-allocated slice of Ts. The difference is that it's created with a fixed length, so it can't be grown. In exchange for this restriction, it has the advantage of only consisting of a pointer and a length, whereas a Vec<T> stores a pointer, a length, and a capacity. So it shaves a full 1/3 off the size of a Vec<T> (and potentially more off the heap space for the elements, since no extra is allocated)!

Box<[T]> is actually not a special type; it is just a combination of Box and [T]. [T] (a slice of Ts) is a valid type in Rust. But since it's not Sized, it can't be passed around by value. It needs to be behind some kind of pointer. This can be &, &mut, Box or even more exotically, Rc, Arc, or Cow. Rc<[T]>, a reference-counted slice of Ts, has no Vec equivalent!

Here's a Rust example of a 1-dimensional slice:

fn main() {
  // A 1-dimensional array of chars with length 3
  let data: [char; 3] = ['A', 'B', 'C'];
  // A 1-dimensional slice (borrowed immutably) with length 3
  let slice: &[char] = &data;
  // The slice's length is 1 number
  println!("Length: {}", slice.len());
  // We can access elements of the slice by indexing with 1 number
  println!("Elements: {:?}, {:?}, {:?}", slice[0], slice[1], slice[2]);
}

This prints:

Length: 3
Elements: 'A', 'B', 'C'

In a 2-dimensional slice (usually called a "matrix"), each element's index consists of 2 indices, one for each dimension. Similarly, the length consists of 2 numbers, the length in each dimension. Rust doesn't have builtin support for 2-dimensional slices, but it does allow for multi-dimensional arrays, as long as the length of each dimension is known when the program is compiled. For example:

fn main() {
  // A 2-dimensional array of chars with length (2, 3). That may look backwards,
  // but 3 is the length of the inner arrays, so it is the second dimension.
  let data: [[char; 3]; 2] = [
    ['A', 'B', 'C'],
    ['D', 'E', 'F'],
  ];
  // Each element of `data` has a unique index (i, j),
  // where `i` and `j` range from 0 to the length in each dimension
  for i in 0..2 {
    for j in 0..3 {
      println!("data[{}][{}] = {:?}", i, j, data[i][j]);
    }
  }
}

This prints:

data[0][0] = 'A'
data[0][1] = 'B'
data[0][2] = 'C'
data[1][0] = 'D'
data[1][1] = 'E'
data[1][2] = 'F'

How about a 0-dimensional slice?

No, seriously, think about it! OK, here's the answer:

Its length is 0-dimensional, i.e. (). So you might assume the slice would have 0 elements. But in fact, that's not the case...

Each index in the slice has an index consists of 0 numbers, i.e. it has the form (). How many values are there of type ()? Just the one! So a 0-dimensional slice contains just a single value. For example, a 0-dimensional slice of i32s is just an i32.

Another way to see this is to notice that an N-dimensional slice with length (length_1, length_2, ..., length_N) has length_1 * length_2 * ... * length_N total elements. So the number of elements in a slice with length () is the empty product, 1. Rust confirms:

  fn main() {
    let empty: [usize; 0] = [];
    println!("The empty product is: {}", empty.into_iter().product::());
  }

Prints:

  The empty product is: 1

As with 1-dimensional slices, we will require that every value in an N-dimensional slice has the same type.

But why?

So a 1-dimensional slice is a normal slice and a 0-dimensional slice is just a value. Maybe you accept those are useful, but why would we need more dimensions?

Well, lots of datasets are naturally multi-dimensional. For example, if we measure the same data points across different samples, or at different points in time, we will have a 2-dimensional dataset. Each value can be indexed by (measurement #, sample #) or (measurement #, time #).

And if there were data for more combinations of inputs, we could end up with higher-dimensional slices. For example, a dataset consisting of the grade for each student in each class each year would be 3-dimensional.

See the end of the post for an example of how we'll be able to manipulate N-dimensional slices with our final code.

Representing a 2-dimensional slice, first try

We saw above that if we can know the length of our 2-dimensional slice at compile time, we can represent it with a nested array. But often, our slice's length will be determined during the execution of our program. And we want to write code to operate on N-dimensional slices regardless of their lengths.

Rust already has 0-dimensional slices (T) and 1-dimensional slices (&[T], Box<[T]>, etc.). It looks like the pattern is to just slap another Box<[ and ]> around the type and you get 1 more dimension. Let's try it out:

/// A 2-dimensional (owned) slice of i32 elements
struct Slice2D(Box<[Box<[i32]>]>);

impl Slice2D {
  /// Makes a length0 x length1 2-dimensional slice of 0s
  fn zero(length0: usize, length1: usize) -> Self {
    // For each index in the 0th dimension, make a row
    let rows = (0..length0).map(|_| {
      // For each index in the 1st dimension, add a 0 to the row
      (0..length1).map(|_| 0).collect()
    }).collect();
    Self(rows)
  }

  /// Gets the 2-dimensional length of the slice
  fn len(&self) -> (usize, usize) {
    // Question: for what lengths does this not work?
    (self.0.len(), self.0[0].len())
  }

  /// Gets the value of the element at a given index
  fn get(&self, index0: usize, index1: usize) -> i32 {
    self.0[index0][index1]
  }

  /// Sets the value of the element at a given index
  fn set(&mut self, index0: usize, index1: usize, value: i32) {
    self.0[index0][index1] = value;
  }
}

len(), get(), and set() are the core operations we need. Some way to make a new slice is also necessary: we can use zero(), followed by set() if we want the elements not to be 0.

With these functions, we can implement whatever complex processing of 2-dimensional slices we want. For example:

/// Makes a new slice by adding `value` to each element of `slice`
fn add_to_all_elements(slice: &Slice2D, value: i32) -> Slice2D {
  let (length0, length1) = slice.len();
  let mut new_slice = Slice2D::zero(length0, length1);
  for index0 in 0..length0 {
    for index1 in 0..length1 {
      new_slice.set(index0, index1, slice.get(index0, index1) + value);
    }
  }
  new_slice
}

/// Prints the contents of a slice for debugging purposes
fn print_slice(slice: &Slice2D) {
  let (length0, length1) = slice.len();
  for index0 in 0..length0 {
    for index1 in 0..length1 {
      print!("{} ", slice.get(index0, index1));
    }
    println!();
  }
}

fn main() {
  let mut slice = Slice2D::zero(3, 3);
  slice.set(0, 0, 1); slice.set(0, 1, 2); slice.set(0, 2, 3);
  slice.set(1, 0, 8); slice.set(1, 1, 9); slice.set(1, 2, 4);
  slice.set(2, 0, 7); slice.set(2, 1, 6); slice.set(2, 2, 5);
  println!("Original slice:");
  print_slice(&slice);
  let slice = add_to_all_elements(&slice, 10);
  println!("New slice:");
  print_slice(&slice);
}

This prints the original slice we created and the new one where 10 has been added to all the elements:

Original slice:
1 2 3
8 9 4
7 6 5
New slice:
11 12 13
18 19 14
17 16 15

Pros and cons

One thing this approach definitely has going for it is how little code was required. An added feature we get is being able to extract a single row (all elements with a particular 0th index) by partially indexing it:

impl Slice2D {
  /// Gets a 1-dimensional slice containing
  /// all elements with a particular 0th index
  fn extract_row(&self, index0: usize) -> &[i32] {
    &self.0[index0]
  }
}

fn main() {
  // ...
  println!("Original slice:");
  print_slice(&slice);
  println!("Row 1: {:?}", slice.extract_row(1));
}

This prints:

Original slice:
1 2 3
8 9 4
7 6 5
Row 1: [8, 9, 4]

Unfortunately, we can't do the same for the 1st index.

A major downside is the memory-efficiency of this representation. We store each row in a separate Box<i32>. To get a sense of the overhead, imagine we have a 10 x 10 slice of i32s. This requires 10 * 10 * size_of::<i32>() = 400 bytes to store the elements.

We then have 10 rows represented as Box<[i32]>s, each of which requires 16 bytes (a pointer and a length). So that's another 160 bytes of overhead. (Part of this is due to a lot of just pointing elsewhere, and part is due to all rows having the same length, so storing it 10 times is redundant.) And the outer Box<[Box<[i32]>]> takes another 16 bytes. 176 bytes of total overhead is almost half the space we need for the elements themselves. We also have 11 separate heap allocations (the 10 rows plus the slice of rows), and if you know how memory allocators work, extra space is likely needed for book-keeping and alignment of each allocation. That's not great.

Representing a 2-dimensional slice, second try

Our main complaint with the previous representation was its memory overhead, so let's fix that! The key idea is to avoid a separate allocation for each row. Instead, we'll "flatten" the 2-dimensional slice into a 1-dimensional allocation.

Consider this 2x3 2-dimensional slice:

4 3 1
2 6 5

There are two ways we might reasonable flatten it into a single 1-dimensional slice with 6 elements, generally called "row-major" and "column-major" orders:

In row-major order, we list each row in order, so the elements within each row are contiguous. This looks like [4, 3, 1, 2, 6, 5] for our sample slice.
In column-major order, we list each column in order, so the elements within each column are contiguous. This looks like [4, 2, 3, 6, 1, 5] for our sample slice.

Either approach works, and there is no clear reason to prefer one to the other. The only difference is in how we find an element in the 1-dimensional slice:

In row-major order, going down one row (incrementing index0) advances 3 (length1) elements in the slice. Going right one column (incrementing index1) advances 1 element in the slice.
In column-major order, going down one row (incrementing index0) advances 1 element in the slice. Going right one column (incrementing index1) advances 2 (length0) elements in the slice.

We can see this in action:

fn main() {
  let length0 = 2usize;
  let length1 = 3;
  let row_major_slice = [4, 3, 1, 2, 6, 5];
  let row_major_index = |index0, index1| index0 * length1 + index1;
  for index0 in 0..length0 {
    for index1 in 0..length1 {
      print!("{} ", row_major_slice[row_major_index(index0, index1)]);
    }
    println!();
  }
  println!();

  let column_major_slice = [4, 2, 3, 6, 1, 5];
  let column_major_index = |index0, index1| index0 + index1 * length0;
  for index0 in 0..length0 {
    for index1 in 0..length1 {
      print!("{} ", column_major_slice[column_major_index(index0, index1)]);
    }
    println!();
  }
}

Both approaches print the same 2-dimensional slice:

We'll make the arbitrary choice to use row-major for now. Here's what our new type looks like:

struct Slice2D {
  data: Box<[i32]>,
  length0: usize,
  length1: usize,
}

data stores the flattened 1-dimensional slice in row-major order. (data consists of both the pointer to the first element and the length of the flattened slice. We actually only need the pointer, since the length can be computed from length0 * length1. But making this optimization requires some unsafe code, so we'll leave it for later.)

Consider the size of our 10 x 10 slice of i32s under this representation: data will be a 400-byte allocation, then we need 16 + 8 + 8 = 32 more bytes for the fields of the struct (can be reduced to 24 if we make data just a *mut i32). 32 or 24 bytes of overhead for the 400 bytes of data is way better than the 176 bytes we used previously!

Here's what the methods look like now:

impl Slice2D {
  fn zero(length0: usize, length1: usize) -> Self {
    let data = vec![0; length0 * length1].into_boxed_slice();
    Self { data, length0, length1 }
  }

  fn len(&self) -> (usize, usize) {
    (self.length0, self.length1)
  }

  /// Helper method for computing a row-major index
  fn index(&self, index0: usize, index1: usize) -> usize {
    index0 * self.length1 + index1
  }

  fn get(&self, index0: usize, index1: usize) -> i32 {
    self.data[self.index(index0, index1)]
  }

  fn set(&mut self, index0: usize, index1: usize, value: i32) {
    self.data[self.index(index0, index1)] = value;
  }
}

We can operate on a sample slice just as we did before:

Original slice:
1 2 3
8 9 4
7 6 5
New slice:
11 12 13
18 19 14
17 16 15

And since the slice is flattened in row-major order, we can still extract individual rows. (If it were in column-major order, we could extract columns instead.)

impl Slice2D {
  fn extract_row(&self, index0: usize) -> &[i32] {
    // The row starts at index `(index0, 0)` and is `length1` elements long
    &self.data[self.index(index0, 0)..][..self.length1]
  }
}

Our row extraction program works just as before:

Original slice:
1 2 3
8 9 4
7 6 5
Row 1: [8, 9, 4]

Representing a 2-dimensional slice, third try

Here's an interesting question: what happens if we reinterpret a row-major slice as a column-major slice? Well, then advancing one element in the slice (which used to mean going right one column) now means going down one row. So the meanings of the row and column indices are swapped! This means we also need to swap length0 and length1, since these tell us the number of rows and columns. Let's try it:

fn main() {
  // Lengths swapped
  let length0 = 3usize;
  let length1 = 2;
  // ...
  for index0 in 0..length0 {
    for index1 in 0..length1 {
      // Access the row-major slice as though it were a column-major slice
      print!("{} ", row_major_slice[column_major_index(index0, index1)]);
    }
    println!();
  }
}

Recall the original slice was:

4 3 1
2 6 5

Our new program prints:

4 2
3 6
1 5

If you've seen some linear algebra, you may recognize this as the matrix "transpose" operation, which reflects the elements across the diagonal (4 and 6 stay in place, 2 and 3 swap, etc.). (And this isn't just true for our sample matrix: switching between row-major and column-major representations transposes a the matrix of any length.) The transpose operation shows up frequently, for example in the least-squares linear regression estimator.

We have just shown we can compute a matrix's transpose without reading or writing any of the elements! For large matrices, this can save a lot of time.

To make use of this, we could define a slice "view" that additionally stores whether it's transposed:

struct Slice2DView<'a> {
  data: &'a [i32], // borrowed, so we can have multiple views for one allocation
  length0: usize,
  length1: usize,
  is_transposed: bool,
}

To compute the length of the view and a flattened index, we would have two cases depending on whether it's transposed:

impl Slice2DView<'_> {
  fn len(&self) -> (usize, usize) {
    if self.is_transposed {
      (self.length1, self.length0)
    }
    else {
      (self.length0, self.length1)
    }
  }

  fn index(&self, index0: usize, index1: usize) -> usize {
    if self.is_transposed {
      index0 + index1 * self.length0 // column-major order
    }
    else {
      index0 * self.length1 + index1 // row-major order
    }
  }
}

We could implement the rest of the methods as before, but it turns out there's an even better representation. Start by noticing the similarity between the row-major and column-major index calculations. If we add * 1, the symmetry is a bit more clear:

fn index(&self, index0: usize, index1: usize) -> usize {
  if self.is_transposed {
    index0 * 1 + index1 * self.length0
  }
  else {
    index0 * self.length1 + index1 * 1
  }
}

In each case, we multiply index0 and index1 by some constant and add them together. Because the multiplier tells us how many elements we need to advance in the flattened slice in order to advance 1 element along that dimension, it's often called the dimension's "stride". So instead of storing an is_transposed field, we can store the stride in each dimension. (We will also need to update the lengths when we transpose the view.) Here's what that looks like:

struct Slice2DView<'a> {
  data: &'a [i32], // borrowed, so we can have multiple views for one allocation
  length0: usize,
  length1: usize,
  /// How many elements to advance in `data`
  /// to advance 1 element along dimension 0
  stride0: usize,
  /// How many elements to advance in `data`
  /// to advance 1 element along dimension 1
  stride1: usize,
}

This significantly simplifies our len() and index() methods:

impl Slice2DView<'_> {
  fn len(&self) -> (usize, usize) {
    (self.length0, self.length1)
  }

  fn index(&self, index0: usize, index1: usize) -> usize {
    index0 * self.stride0 + index1 * self.stride1
  }
}

Computing the initial stride and the transposed stride isn't too complicated either:

impl Slice2D {
  /// Creates a (borrowed) view of the owned slice
  fn view(&self) -> Slice2DView<'_> {
    let Self { ref data, length0, length1 } = *self;
    // Slice is in row-major order, so initial stride is `(length1, 1)`
    Slice2DView { data, length0, length1, stride0: length1, stride1: 1 }
  }
}

impl Slice2DView<'_> {
  /// Creates a view that is the transpose of this view
  fn transpose(&self) -> Self {
    let Self { data, length0, length1, stride0, stride1 } = *self;
    // Lengths and strides are swapped to swap the meaning of the dimensions
    Self {
      data,
      length0: length1,
      length1: length0,
      stride0: stride1,
      stride1: stride0,
    }
  }
}

Adding a get() method to Slice2DView, we can now demonstrate transposing the slice:

impl Slice2DView<'_> {
  fn get(&self, index0: usize, index1: usize) -> i32 {
    self.data[self.index(index0, index1)]
  }
}

// This is the same as before, but now takes a Slice2DView, not a Slice2D
fn print_slice(slice: &Slice2DView) {
  let (length0, length1) = slice.len();
  for index0 in 0..length0 {
    for index1 in 0..length1 {
      print!("{} ", slice.get(index0, index1));
    }
    println!();
  }
}

fn main() {
  let mut slice = Slice2D::zero(2, 3);
  // Initialize the data since we haven't implemented `set()`
  for (element, i) in slice.data.iter_mut().zip(1..) {
    *element = i;
  }
  println!("Original slice:");
  let view = slice.view();
  print_slice(&view);
  println!("Transposed:");
  print_slice(&view.transpose());
}

This prints:

Original slice:
1 2 3
4 5 6
Transposed:
1 4
2 5
3 6

In the example above, we allocate a single 2-dimensional slice (represented as a Slice2D) and create multiple views of it (represented as Slice2DViews). From an ownership perspective, Slice2D is analogous to a Box<[i32]> and Slice2DView serves the role of &[i32]. (We can "dereference" a Slice2D into a Slice2DView, Slice2DView doesn't allow the elements to be mutated, Slice2DView can be Copy, etc.) The missing analog to &mut [i32] would be something like Slice2DViewMut, allowing mutable access to the elements.

Going unsafe

I promised that storing data: &[i32] in Slice2DView was unnecessary; we only need the pointer to the start of the data, not the length. Currently, the program is safe because the length stored in data is used to check the bounds every time we index data. However, we shouldn't rely on this bounds check to ensure the index we provide to get() is valid. Since the elements are stored contiguously, we can provide an invalid index as long as self.index(index0, index1) stays within data.len():

fn main() {
  // Make a 2-dimensional slice with length (3, 3)
  let mut slice = Slice2D::zero(3, 3);
  for (element, i) in slice.data.iter_mut().zip(1..) {
    *element = i;
  }
  let view = slice.view();
  // Access index (0, 4), which should be out of bounds
  println!("slice[0, 4] = {}", view.get(0, 4));
  // Oops, we end up getting (1, 1) instead!
}

So we really should be checking each index against that dimension's length. Since we know data is large enough to store all our elements, we know we won't access out-of-bounds memory if index0 < length0 && index1 < length1. Therefore, storing just the pointer to the start of data is enough. (A NonNull<i32> would be even better, since it allows Option<Slice2DView> to have the same size as Slice2DView.)

struct Slice2DView {
  data: *const i32, // the address of the start of the data (index (0, 0))
  length0: usize,
  length1: usize,
  stride0: usize,
  stride1: usize,
}

impl Slice2D {
  fn view(&self) -> Slice2DView {
    let Self { ref data, length0, length1 } = *self;
    let data = data.as_ptr(); // only need the pointer to the first element
    Slice2DView { data, length0, length1, stride0: length1, stride1: 1 }
  }
}

impl Slice2DView {
  fn get(&self, index0: usize, index1: usize) -> i32 {
    // Both indices need to be within their bounds
    assert!(
      index0 < self.length0 && index1 < self.length1,
      "Invalid index ({}, {}) for length ({}, {})",
      index0, index1, self.length0, self.length1,
    );
    let index = self.index(index0, index1);
    // SAFETY: we checked that the index is in-bounds
    unsafe { *self.data.add(index) }
  }
}

Our transpose test program still works:

Original slice:
1 2 3
4 5 6
Transposed:
1 4
2 5
3 6

And our invalid access panics properly now:

thread 'main' panicked at 'Invalid index (0, 4) for length (3, 3)', src/main.rs:59:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

The power of the stride vector

Okay, storing the stride in each dimension is an alternate way to implement the transpose operation, *shrug*.

Well, it turns out that many other useful operations on N-dimensional slices can be done by manipulating the strides (collectively called the "stride vector"). This means these operations are cheap even on large slices (there is no need to copy the elements themselves). And more importantly, since these operations all manipulate the stride vector, they can be chained together, all without copying. Let's take a look at all the operations that are possible.

Transposing

We've discussed the matrix transpose operation (swapping rows with columns) above. Here was an example:

[
  [1, 2, 3],
  [4, 5, 6],
]
becomes
[
  [1, 4],
  [2, 5],
  [3, 6],
]

We implemented this by swapping the row stride with the column stride, and swapping the row length with the column length.

More generally, we can permute the dimensions any way we want. For example, if a 3-dimensional slice was originally indexed by (i, j, k), we could make a new view indexed by (j, k, i) or (k, j, i) instead.

Slicing

Just like normal Rust slices (&[T]) can be sliced (&some_slice[1..3]), N-dimensional slices can be sliced along any dimension. Here is an example, slicing 1..3 along dimension 1 (the columns):

[
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
]
becomes
[
  [2, 3],
  [5, 6],
  [8, 9],
]

Note that slicing doesn't affect the dimensions (an N-dimensional slice would remain an N-dimensional slice after slicing it any way and the dimensions would still have the same meaning). So the stride vector is unchanged. To slice from start to end along dimension d, start * stride[d] is added to the starting pointer to skip the first start elements in that dimension, and len[d] becomes end - start.

Skipping

Normal slices in Rust don't have a stride associated with them. But what if they did? A stride of 2, for example, would pick out only the even indices of the slice. A stride of 3 would pick out every third element. Since we are already storing the stride vector, we can easily apply an additional stride along any dimension. Here is an example, applying stride 2 along dimension 1 (the columns):

[
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
]
becomes
[
  [1, 3],
  [4, 6],
  [7, 9],
]

Applying a stride of s along dimension d doesn't change the starting pointer, but it multiplies stride[d] by s and divides len[d] by s (rounding up).

Removing a dimension

So far, all the operations we've seen don't affect an N-dimensional slice's dimensions. But we sometimes want to change the number of dimensions in an N-dimensional slice. One example is picking out a single index along one of the dimensions. For example, we could take a matrix (2 dimensions) and pick out only the elements with index 1 along dimension 0 (the rows), resulting in a 1-dimensional slice:

[
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
]
becomes
[4, 5, 6]

Note that slicing 1..=1 along dimension 0 would give the same elements, but keep it a 2-dimensional slice:

[
  [4, 5, 6],
]

Picking out index 0 along dimension d simply removes dimension d from the stride and length vectors. Picking out index i additionally requires adding i * stride[d] to the starting pointer, just as when slicing. We end up with an N - 1-dimensional slice.

Adding a dimension

Removing a dimension by picking out data at one index may seem reasonable, but how could we possibly add a new dimension without creating or copying any data?

Well, first consider the case where we want the new dimension to have length 1. When going from a 1-dimensional slice to a 2-dimensional slice, this is called creating a row or column vector, depending on which dimension is added:

[1, 2, 3]
becomes (row vector)
[
  [1, 2, 3],
]
or (column vector)
[
  [1],
  [2],
  [3],
]

In this case, the underlying elements are exactly the same (by adding a dimension of length 1, we have multiplied the total number of elements by 1). This would just require adding the length 1 to the length vector and any stride to the stride vector (it is only possible to access index 0 along this dimension, so the stride is irrelevant).

Let's try to generalize this: adding a dimension with length l would give an N + 1-dimensional slice with l copies of the original slice along the new dimension. Can we represent an N-dimensional slice where every index along the new dimension refers to the same (original) data? Actually, we can! Since we want to advance along the new dimension without moving in the underlying slice, we need the dimension to have a stride of 0. Using this trick, we could, for example, add a new dimension 0 with length 3:

[1, 2, 3]
becomes
[
  [1, 2, 3],
  [1, 2, 3],
  [1, 2, 3],
]

Making it generic

So far, we've played with a 2-dimensional slice of i32s. But the same concepts work for any N-dimensional slice of any (Sized) type T. To extend the operations we've implemented to any possible slice, we would want to make it generic over both N and T. With Rust's recent "const generics" features, this is actually doable with just a few unstable features. N-dimensional indices, lengths, and strides can be represented as [usize; N].

You can find the full implementation on GitHub with some tests to illustrate how it can be used. I won't bore you with all the details, but I want to give the gist of what it looks like.

The interfaces

There are different N-dimensional slice types corresponding to the ownership of Box, &, and &mut (some helper types removed for clarity):

use std::marker::PhantomData;
use std::ptr::NonNull;

/// N-dimensional analog of Box<[T]>
pub struct NDBox<T, const N: usize> {
  data: NonNull<T>,
  len: [usize; N],
}

/// N-dimensional analog of &[T]
pub struct NDSlice<'a, T, const N: usize> {
  data: NonNull<T>,
  len: [usize; N],
  stride: [usize; N],
  phantom: PhantomData<&'a T>,
}

/// N-dimensional analog of &mut [T]
pub struct NDSliceMut<'a, T, const N: usize> {
  data: NonNull<T>,
  len: [usize; N],
  stride: [usize; N],
  phantom: PhantomData<&'a mut T>,
}

All N-dimensional slices start from an NDBox, which allocates the storage for the values as a Box<[T]> in row-major order. An NDBox can be created most generally by providing the length in each dimension and an initializer function to create the value at each index. There are also helpers to create a slice filled with a single value or the default value for T:

impl<T, const N: usize> NDBox<T, N> {
  pub fn new_with<F>(len: [usize; N], mut init: F) -> Self
    where F: FnMut([usize; N]) -> T
  {
    // ...
  }

  pub fn new_fill(len: [usize; N], value: T) -> Self where T: Clone {
    Self::new_with(len, |_| value.clone())
  }

  pub fn new_default(len: [usize; N]) -> Self where T: Default {
    Self::new_with(len, |_| T::default())
  }
}

And From implementations to write what look like NDBox literals (up to 2 dimensions):

/// 0-dimensional NDBox literal, e.g.:
/// NDBox::from(123)
impl<T> From<T> for NDBox<T, 0> {
  fn from(value: T) -> Self {
    // ...
  }
}

/// 1-dimensional NDBox literal, e.g.:
/// NDBox::from([1, 2, 3])
impl<T, const L0: usize> From<[T; L0]> for NDBox<T, 1> {
  fn from(value: [T; L0]) -> Self {
    // ...
  }
}

/// 2-dimensional NDBox literal, e.g.:
/// NDBox::from([
///   [1, 2, 3],
///   [4, 5, 6],
///   [7, 8, 9],
/// ])
impl<T, const L0: usize, const L1: usize> From<[[T; L1]; L0]> for NDBox<T, 2> {
  fn from(value: [[T; L1]; L0]) -> Self {
    // ...
  }
}

From an NDBox, you can create an NDSlice or NDSliceMut of all its elements:

impl<T, const N: usize> NDBox<T, N> {
  pub fn as_slice(&self) -> NDSlice<T, N> {
    let Self { data, len } = *self;
    NDSlice { data, len, stride: self.stride(), phantom: PhantomData }
  }

  pub fn as_mut(&mut self) -> NDSliceMut<T, N> {
    let Self { data, len } = *self;
    NDSliceMut { data, len, stride: self.stride(), phantom: PhantomData }
  }
}

An NDSliceMut can also be borrowed as an NDSlice:

impl<'a, T, const N: usize> NDSliceMut<'a, T, N> {
  pub fn as_slice(&self) -> NDSlice<'a, T, N> {
    let Self { data, len, stride, .. } = *self;
    NDSlice { data, len, stride, phantom: PhantomData }
  }
}

Just like &T, NDSlice is Copy, so we can have multiple (read-only) slices of the same data:

impl<T, const N: usize> Clone for NDSlice<'_, T, N> {
  fn clone(&self) -> Self {
    *self
  }
}

impl<T, const N: usize> Copy for NDSlice<'_, T, N> {}

As with &[T] and &mut [T], elements can be accessed using:

The Index/IndexMut operators, which panic if the index is out of bounds
The get()/get_mut() methods, which return None on out-of-bounds
The unsafe get_unchecked()/get_unchecked_mut() methods, which assume the index is in bounds

Both NDSlice and NDSliceMut can be manipulated using the stride and length vector operations discussed above:

/// Since `True` is only implemented for `Is<true>`,
/// the constraint `Is<X>: True` requires `X` to be true.
pub enum Is<const B: bool> {}
pub trait True {}
impl True for Is<true> {}

/// A range along a dimension, along with a number of indices to skip in between.
/// (Builder methods omitted for brevity.)
pub struct Bounds {
  start: Option<usize>,
  end: Option<usize>,
  step: usize,
}

impl<'a, T, const N: usize> NDSlice<'a, T, N> {
  /// Picks out the elements at a given index along dimension `D`.
  /// The dimension is required to be a constant so it can be checked at compile time.
  pub fn extract<const D: usize>(self, dimension_index: usize)
    -> NDSlice<'a, T, {N - 1}>
    where Is<{D < N}>: True
  {
    // ...
  }

  /// Adds a new dimension at index `D` with the given length.
  /// Picking out any index along the new dimension will give the original slice.
  /// The dimension is required to be a constant so it can be checked at compile time.
  pub fn add_dimension<const D: usize>(self, dimension_len: usize)
    -> NDSlice<'a, T, {N + 1}>
    where Is<{D <= N}>: True
  {
    // ...
  }

  /// Restricts the array to a slice along each dimension.
  /// Also allows applying an additional stride with Bounds::step().
  /// To leave a dimension unsliced, use Bounds::all() as its bounds.
  pub fn slice(self, bounds: [Bounds; N]) -> Self {
    // ...
  }

  /// Reverses the dimensions, so what was at index [a, ..., z] becomes index [z, ..., a].
  /// For a 2-dimensional slice, this is the matrix transpose operation.
  pub fn transpose(self) -> Self {
    // ...
  }
}

The implementation

Allocation size, default stride vector, and indexing

Generalizing the 2-dimensional case, the total number of elements is computed by multiplying the lengths in each dimension.

fn size(len: [usize; N]) -> usize {
  len.iter().product()
}

Since NDBox elements are stored in row-major order, the stride is computed as the cumulative products of the final dimension lengths:

fn default_stride(len: [usize; N]) -> [usize; N] {
  // Row-major order: indices are ordered by dimension 0, then 1, ..., N - 1.
  // So dimension N - 1 has stride 1, dimension N - 2 has stride len[N - 1], etc.
  let mut stride = [0; N];
  let mut next_stride = 1;
  for (dimension_stride, dimension_len) in iter::zip(&mut stride, len).rev() {
    *dimension_stride = next_stride;
    next_stride *= dimension_len;
  }
  stride
}

The location of an element is computed by multiplying each dimension index against the corresponding stride and offsetting it from the first element:

use std::iter;

impl<'a, T, const N: usize> NDSlice<'a, T, N> {
  /// SAFETY: each dimension index must be at most the corresponding dimension length
  /// (so the resulting pointer does not go past the end of the underlying allocation)
  unsafe fn location(self, index: [usize; N]) -> NonNull<T> {
    let offset = iter::zip(index, self.stride)
      .map(|(dimension_index, dimension_stride)| {
        dimension_index * dimension_stride
      })
      .sum();
    NonNull::new_unchecked(self.data.as_ptr().add(offset))
  }
}

`extract()`

extract() is implemented by offsetting to the specified index along the dimension and removing that dimension from the length and stride vectors:

fn remove<const N: usize, const I: usize>(input: [usize; N]) -> [usize; N - 1]
  where Is<{I < N}>: True
{
  let mut result = [0; N - 1];
  result[..I].copy_from_slice(&input[..I]);
  result[I..].copy_from_slice(&input[I + 1..]);
  result
}

impl<'a, T, const N: usize> NDSlice<'a, T, N> {
  pub fn extract<const D: usize>(self, dimension_index: usize)
    -> NDSlice<'a, T, {N - 1}>
    where Is<{D < N}>: True
  {
    let Self { len, stride, .. } = self;
    let mut index = [0; N];
    index[D] = dimension_index;
    let data = unsafe { self.location(index) };
    let len = remove::<N, D>(len);
    let stride = remove::<N, D>(stride);
    NDSlice { data, len, stride, phantom: PhantomData }
  }
}

`add_dimension()`

add_dimension() is implemented by simply inserting the new dimension length into the length vector and stride 0 into the stride vector at the given dimension:

fn insert<const N: usize, const I: usize>(input: [usize; N], value: usize)
  -> [usize; N + 1]
  where Is<{I <= N}>: True
{
  let mut result = [value; N + 1];
  result[..I].copy_from_slice(&input[..I]);
  result[I + 1..].copy_from_slice(&input[I..]);
  result
}

impl<'a, T, const N: usize> NDSlice<'a, T, N> {
  pub fn add_dimension<const D: usize>(self, dimension_len: usize)
    -> NDSlice<'a, T, {N + 1}>
    where Is<{D <= N}>: True
  {
    let Self { data, len, stride, .. } = self;
    let len = insert::<N, D>(len, dimension_len);
    let stride = insert::<N, D>(stride, 0);
    NDSlice { data, len, stride, phantom: PhantomData }
  }
}

`slice()`

slice() allows every dimension to be sliced simultaneously so the syntax can be similar to indexing:

// Assuming nd_slice is a 2-dimensional slice (matrix),
// slice only the even rows, and columns 1 to 3
nd_slice.slice([Bounds::all().step(2), Bounds::all().from(1).to(3)])

The data pointer is offset to the starting index in each dimension. The new length in each dimension is the difference between the starting and ending indices, divided by the step size (rounding up). And the stride in each dimension is multiplied by the step size.

impl<'a, T, const N: usize> NDSlice<'a, T, N> {
  pub fn slice(self, bounds: [Bounds; N]) -> Self {
    let Self { len, stride, .. } = self;
    let dimensions = bounds.zip(len).zip(stride)
      .map(|((dimension_bounds, dimension_len), dimension_stride)| {
        let dimension_start = dimension_bounds.start.unwrap_or(0);
        let dimension_end = dimension_bounds.end.unwrap_or(dimension_len);
        let dimension_len = (dimension_start..dimension_end)
          .step_by(dimension_bounds.step)
          .len();
        let dimension_stride = dimension_stride * dimension_bounds.step;
        (dimension_start, dimension_len, dimension_stride)
      });
    let index = dimensions.map(|(dimension_start, _, _)| dimension_start);
    let data = unsafe { self.location(index) };
    let len = dimensions.map(|(_, dimension_len, _)| dimension_len);
    let stride = dimensions.map(|(_, _, dimension_stride)| dimension_stride);
    Self { data, len, stride, phantom: PhantomData }
  }
}

`transpose()`

transpose() simply reverses the length and stride vectors, which reverses the meaning of indices in the index vector:

impl<'a, T, const N: usize> NDSlice<'a, T, N> {
  pub fn transpose(mut self) -> Self {
    self.len.0.reverse();
    self.stride.0.reverse();
    self
  }
}

An example

As a practical example of what we can now do, let's consider a dataset with the high temperatures over 10 days in 3 cities:

let temperatures_fahrenheit = NDBox::<f32, 2>::from([
  // NYC, LAX, CHI
  [72.0, 80.0, 79.0], // 2022-06-01
  [79.0, 79.0, 79.0], // 2022-06-02
  [76.0, 73.0, 83.0], // 2022-06-03
  [80.0, 70.0, 72.0], // 2022-06-04
  [77.0, 75.0, 81.0], // 2022-06-05
  [80.0, 77.0, 76.0], // 2022-06-06
  [78.0, 76.0, 71.0], // 2022-06-07
  [82.0, 75.0, 72.0], // 2022-06-08
  [81.0, 80.0, 80.0], // 2022-06-09
  [77.0, 81.0, 82.0], // 2022-06-10
]);
let [days, cities] = temperatures_fahrenheit.len();

First, let's convert the temperatures to Celsius. Since temp_C = (temp_F - 32) / 1.8, we create two slices of the same length as temperatures_fahrenheit, one filled with 32 and one with 1.8. Using add_dimension(), we only need to allocate 1 element for each slice:

let const_32 = NDBox::from(32.0);
let const_32 = const_32.as_slice()
  .add_dimension::<0>(days)
  .add_dimension::<1>(cities);
let const_1_8 = NDBox::from(1.8);
let const_1_8 = const_1_8.as_slice()
  .add_dimension::<0>(days)
  .add_dimension::<1>(cities);
dbg!(const_32);

Printing out const_32 shows it has the value 32.0 for each day and city:

[src/main.rs:28] const_32 = [
    [32.0, 32.0, 32.0],
    [32.0, 32.0, 32.0],
    [32.0, 32.0, 32.0],
    [32.0, 32.0, 32.0],
    [32.0, 32.0, 32.0],
    [32.0, 32.0, 32.0],
    [32.0, 32.0, 32.0],
    [32.0, 32.0, 32.0],
    [32.0, 32.0, 32.0],
    [32.0, 32.0, 32.0],
]

Now we can use the binary operators implemented on slices to perform the Celsius conversion:

let temperatures_celsius =
  (temperatures_fahrenheit.as_slice() - const_32) / const_1_8;
let temperatures_celsius = temperatures_celsius.as_slice();
dbg!(temperatures_celsius);

The Celsius values are:

[src/main.rs:35] temperatures_celsius = [
    [22.222223, 26.666668, 26.111113],
    [26.111113, 26.111113, 26.111113],
    [24.444445, 22.777779, 28.333334],
    [26.666668, 21.111113, 22.222223],
    [25.0, 23.88889, 27.222223],
    [26.666668, 25.0, 24.444445],
    [25.555555, 24.444445, 21.666668],
    [27.777779, 23.88889, 22.222223],
    [27.222223, 26.666668, 26.666668,],
    [25.0, 27.222223, 27.777779],
]

We can then compute the average temperatures for each city by extracting that city's temperatures and averaging them:

let average_temperatures = NDBox::new_with([cities], |[city]| {
  let city_temperatures = temperatures_celsius.extract::<1>(city);
  city_temperatures.into_iter().sum::<f32>() / days as f32
});
let average_temperatures = average_temperatures.as_slice();
dbg!(average_temperatures);

The result is a 1-dimensional slice:

[src/main.rs:42] average_temperatures = [
    25.666668,
    24.777779,
    25.27778,
]

Missing features

If you want to tinker with the codebase, here are some features it should probably support but doesn't at the moment:

Slicing in reverse (without copying!): for example, turn the view [1, 2, 3] into [3, 2, 1]. This could be accomplished by an additional bool indicating whether an NDSlice is reversed in each dimension. Could you do it with just the stride vector instead? :)
Permuting dimensions arbitrarily: currently, transpose() just reverses the dimensions, but any permutation should be allowed (see "Transposing")

These are marked with TODO in the code.

Git Internals part 3: the SSH transport

Caleb Sander — Sun, 20 Mar 2022 06:34:45 +0000

This post is the last in the "Git Internals" series. In part 1, we introduced git's object storage model, and in part 2, we saw how objects are stored in "packfiles" to save space.

In this post, we'll turn our attention from local git repositories (stored on your computer) to remote ones (stored on a server, e.g. GitHub). We'll inspect the protocol git uses to communicate with "remotes" and implement git fetch from the ground up.

If you use online git repositories (like those on GitHub) frequently, you may know you can git clone a repository using either an HTTP/HTTPS URL (e.g. https://github.com/git/git.git) or an "SSH" URL (e.g. git@github.com:git/git.git). The difference between these URLs is the protocol that git uses to communicate with the GitHub server during a git clone, git fetch, git pull, or git push. git implements several protocols: "dumb" HTTP/HTTPS, "smart" HTTP/HTTPS, SSH, and "git". The dumb protocol is less efficient, so it is rarely used in practice. The smart protocols use the same procedures, but differ in the underlying protocol used to connect to the server. We'll focus on the SSH one because it is so common and is an interesting application of SSH.

The protocol is human-readable, so we will mostly learn how it works by observing what the client and server send each other. If you want to look at git's documentation on the topic, here are some good resources:

The git book chapter on transfer protocols provides a high-level overview of the available transports and how they work
The git internal "pack protocol" documentation describes the SSH transport protocol in detail
The git internal "protocol capabilities" documentation explains each of the optional features for the SSH transport

Sorry for the delay on part 3! My life has been busier than expected the past few months.

The source code for this post can be found here.

Where does SSH come in?

Using an SSH git URL requires you to upload your SSH public key to the server. SSH keys are typically used to authenticate SSH connections, so you might be able to guess that your git client is communicating with the git server over an SSH connection.

If you're unfamiliar with SSH, here's a quick overview of how it's used. (We won't worry about how SSH is implemented, but that's also fascinating.) SSH allows you to run terminal commands on a remote computer. For example, I can run hostname to see the name of my computer:

csander:~ $ hostname
csander-mac.local

I can also use SSH to open a terminal on the EC2 instance hosting calebsander.com and run hostname there:

csander:~ $ ssh ubuntu@calebsander.com # ubuntu is the user to log in as
ubuntu@ip-172-31-52-11:~ $ hostname
ip-172-31-52-11
ubuntu@ip-172-31-52-11:~ $ exit
Connection to calebsander.com closed.

By default, ssh runs a terminal process (e.g. bash) on the server. You can tell ssh to run a different command instead:

csander:~ $ ssh ubuntu@calebsander.com hostname
ip-172-31-52-11

A key feature git will leverage is that the SSH connection is bidirectional: your local standard input is connected to the input of the remote process and the remote standard output back to the local one. This is easiest to see when running a command like cat (copy standard input to standard output). If you send type a line of text, it gets sent to the cat process running on the other computer, which prints the line, causing it to be sent back.

csander:~ $ ssh ubuntu@calebsander.com cat
abc # input sent to server
abc # output sent back
123 # input
123 # output
(enter Ctrl+D to end the standard input, terminating the process)

SSH provides both authentication (the server checks that the client's SSH key may access the repository) and encryption (the communication is hidden from anyone snooping on the connection), which is likely why git chose to use it.

If we run the command git clone git@github.com:git/git.git and use ps aux | grep ssh to list the SSH processes while it's running, we can see the SSH command that git used:

/usr/bin/ssh -o SendEnv=GIT_PROTOCOL git@github.com git-upload-pack 'git/git.git'

-o SendEnv=GIT_PROTOCOL is unnecessary, so the SSH command can be simplified to:

ssh git@github.com git-upload-pack git/git.git

There we can see all the pieces of the URL git@github.com:git/git.git! The part before the : is the SSH login (e.g. user@domain.name) and the part after the : is the argument to the git-upload-pack executable, specifying the repository. (It may be confusing that git-upload-pack is used for a clone/fetch/pull and git-receive-pack is used for push, but this is from the perspective of the server.)

If you're curious, the GitHub SSH server is restricted so you can't run other commands:

$ ssh git@github.com
PTY allocation request failed on channel 0
Hi calebsander! You've successfully authenticated, but GitHub does not provide shell access.
Connection to github.com closed.
$ ssh git@github.com echo Hello world
Invalid command: 'echo Hello world'
  You appear to be using ssh to clone a git:// URL.
  Make sure your core.gitProxy config option and the
  GIT_PROXY_COMMAND environment variable are NOT set.

Now that we know the SSH command, we can run it ourselves and see what the server sends back:

$ ssh git@github.com git-upload-pack git/git.git
014e74cc1aa55f30ed76424a0e7226ab519aa6265061 HEADmulti_ack thin-pack side-band side-band-64k ofs-delta shallow deepen-since deepen-not deepen-relative no-progress include-tag multi_ack_detailed allow-tip-sha1-in-want allow-reachable-sha1-in-want symref=HEAD:refs/heads/master filter object-format=sha1 agent=git/github-g2faa647c16c3
003d74cc1aa55f30ed76424a0e7226ab519aa6265061 refs/heads/main
003e4c53a8c20f8984adb226293a3ffd7b88c3f4ac1a refs/heads/maint
003f74cc1aa55f30ed76424a0e7226ab519aa6265061 refs/heads/master
003dd65ed663a79d75fb636a4602eca466dbd258082e refs/heads/next
003d583a5781c12c1d6d557fae77552f6cee5b966f8d refs/heads/seen
003db1b3e2657f1904c7c603ea4313382a24af0fd91f refs/heads/todo
003ff0d0fd3a5985d5e588da1e1d11c85fba0ae132f8 refs/pull/10/head
0040c8198f6c2c9fc529b25988dfaf5865bae5320cb5 refs/pull/10/merge
...
003edcba104ffdcf2f27bc5058d8321e7a6c2fe8f27e refs/tags/v2.9.5
00414d4165b80d6b91a255e2847583bd4df98b5d54e1 refs/tags/v2.9.5^{}
0000(waiting for input)

Okay, that's a lot to unpack (pun definitely intended), so let's break it down!

Opening an SSH connection in Rust

First, we'll see how to open this SSH connection in Rust. We can construct the same ssh command we ran ourselves, using Stdio::piped() for the input and output streams so we get an ssh_input that implements Write and an ssh_output implementing Read.

use std::env;
use std::io;
use std::process::{ChildStdin, ChildStdout, Command, Stdio};

// Using the types and functions implemented in previous posts

struct Transport {
  ssh_input: ChildStdin,
  ssh_output: ChildStdout,
}

impl Transport {
  fn connect(repository: &str) -> io::Result<Self> {
    // `repository` will look like "git@github.com:git/git.git".
    // "git@github.com" is the SSH login (user "git", hostname "github.com").
    // "git/git.git" specifies the repository to fetch on this server.
    let repository_pieces: Vec<_> = repository.split(':').collect();
    let [login, repository] = <[&str; 2]>::try_from(repository_pieces)
      .map_err(|_| {
        make_error(&format!("Invalid SSH repository: {}", repository))
      })?;
    // Start an SSH process to connect to this repository.
    // We don't wait for the `ssh` command to finish because we are going to
    // communicate back and forth with the server through its standard input and output.
    let mut ssh_process = Command::new("ssh")
      .args([login, "git-upload-pack", repository])
      .stdin(Stdio::piped())
      .stdout(Stdio::piped())
      .spawn()?;
    let ssh_input = ssh_process.stdin.take().ok_or_else(|| {
      make_error("Failed to open ssh stdin")
    })?;
    let ssh_output = ssh_process.stdout.take().ok_or_else(|| {
      make_error("Failed to open ssh stdout")
    })?;
    Ok(Transport { ssh_input, ssh_output })
  }
}

fn main() -> io::Result<()> {
  let args: Vec<_> = env::args().collect();
  let [_, repository] = <[String; 2]>::try_from(args).unwrap();
  let mut transport = Transport::connect(&repository)?;
  // Print the SSH output
  io::copy(&mut transport.ssh_output, &mut io::stdout())?;
  Ok(())
}

Running this program gives the same result as running the SSH command directly:

$ cargo run git@github.com:git/git.git
014e74cc1aa55f30ed76424a0e7226ab519aa6265061 HEADmulti_ack thin-pack side-band side-band-64k ofs-delta shallow deepen-since deepen-not deepen-relative no-progress include-tag multi_ack_detailed allow-tip-sha1-in-want allow-reachable-sha1-in-want symref=HEAD:refs/heads/master filter object-format=sha1 agent=git/github-g2faa647c16c3
003d74cc1aa55f30ed76424a0e7226ab519aa6265061 refs/heads/main
003e4c53a8c20f8984adb226293a3ffd7b88c3f4ac1a refs/heads/maint
003f74cc1aa55f30ed76424a0e7226ab519aa6265061 refs/heads/master
003dd65ed663a79d75fb636a4602eca466dbd258082e refs/heads/next
003d583a5781c12c1d6d557fae77552f6cee5b966f8d refs/heads/seen
003db1b3e2657f1904c7c603ea4313382a24af0fd91f refs/heads/todo
003ff0d0fd3a5985d5e588da1e1d11c85fba0ae132f8 refs/pull/10/head
0040c8198f6c2c9fc529b25988dfaf5865bae5320cb5 refs/pull/10/merge
...
003edcba104ffdcf2f27bc5058d8321e7a6c2fe8f27e refs/tags/v2.9.5
00414d4165b80d6b91a255e2847583bd4df98b5d54e1 refs/tags/v2.9.5^{}
(waiting)

Finding the default remote URL

In the example above, we passed the desired repository URL to our program. But when using git, it is common to run git fetch/pull/push without specifying a repository. By default, git uses the URL specified during the initial git clone, so it must be stored somewhere. Exploring the .git directory, we see:

$ git clone git@github.com:git/git.git
Cloning into 'git'...
remote: Enumerating objects: 325167, done.
remote: Total 325167 (delta 0), reused 0 (delta 0), pack-reused 325167
Receiving objects: 100% (325167/325167), 185.01 MiB | 7.77 MiB/s, done.
Resolving deltas: 100% (242985/242985), done.
Updating files: 100% (4084/4084), done.
$ cd git
$ cat .git/config
[core]
    repositoryformatversion = 0
    filemode = true
    bare = false
    logallrefupdates = true
    ignorecase = true
    precomposeunicode = true
[remote "origin"]
    url = git@github.com:git/git.git
    fetch = +refs/heads/*:refs/remotes/origin/*
[branch "master"]
    remote = origin
    merge = refs/heads/master

There is a [remote ...] section for each remote repository. By default, the repository used in the git clone command is called origin. The url parameter gives us the URL for that remote.

There is also a [branch ...] section for each branch, e.g. master, indicating which remote and remote ref name to push and pull the branch from by default.

For example, consider running git pull with master checked out. The [branch "master"] and [remote "origin"] config sections translate this into fetching git@github.com:git/git.git and merging origin/master into master.

We can find the URL for origin by parsing the config file and then extracting the url parameter from the [remote "origin"] section:

use std::collections::HashMap;
use std::fs::File;
use std::io::{BufRead, BufReader};

const CONFIG_FILE: &str = ".git/config";
// `r#` is handy for string literals with quotes
const REMOTE_ORIGIN_SECTION: &str = r#"[remote "origin"]"#;
const URL_PARAMETER: &str = "url";

// A parsed .git/config file, represented as
// a map of section -> parameter -> value
#[derive(Debug)]
struct ConfigFile(HashMap<String, HashMap<String, String>>);

impl ConfigFile {
  fn read() -> io::Result<Self> {
    let config_file = File::open(CONFIG_FILE)?;
    let mut sections = HashMap::new();
    // The parameter values for the current section
    let mut parameters: Option<&mut HashMap<String, String>> = None;
    for line in BufReader::new(config_file).lines() {
      let line = line?;
      if let Some(parameter_line) = line.strip_prefix('\t') {
        // The line is indented, so it's a parameter in a section
        let (parameter, value) = parameter_line.split_once(" = ")
          .ok_or_else(|| {
            make_error(&format!("Invalid parameter line: {:?}", parameter_line))
          })?;
        // All parameters should be under a section
        let parameters = parameters.as_mut().ok_or_else(|| {
          make_error("Config parameter is not in a section")
        })?;
        parameters.insert(parameter.to_string(), value.to_string());
      }
      else {
        // The line starts a new section
        parameters = Some(sections.entry(line).or_default());
      }
    }
    Ok(ConfigFile(sections))
  }

  fn get_origin_url(&self) -> Option<&str> {
    let remote_origin_section = self.0.get(REMOTE_ORIGIN_SECTION)?;
    let url = remote_origin_section.get(URL_PARAMETER)?;
    Some(url)
  }
}

fn main() -> io::Result<()> {
  let config = ConfigFile::read()?;
  println!("Config file: {:#?}", config);
  let origin_url = config.get_origin_url().ok_or_else(|| {
    make_error("Missing remote 'origin'")
  })?;
  println!("Remote 'origin' URL: {}", origin_url);
  Ok(())
}

Running this prints:

Config file: ConfigFile(
    {
        "[remote \"origin\"]": {
            "url": "git@github.com:git/git.git",
            "fetch": "+refs/heads/*:refs/remotes/origin/*",
        },
        "[core]": {
            "repositoryformatversion": "0",
            "bare": "false",
            "ignorecase": "true",
            "filemode": "true",
            "logallrefupdates": "true",
            "precomposeunicode": "true",
        },
        "[branch \"master\"]": {
            "remote": "origin",
            "merge": "refs/heads/master",
        },
    },
)
Remote 'origin' URL: git@github.com:git/git.git

The SSH transport protocol

Chunks

Let's try to understand what the server sent over the SSH connection. It looks like a series of lines, each starting with a hexadecimal string. These look like hashes, and in fact they almost are, except they're 44 characters long instead of 40. You may notice that the first 4 hexadecimal characters mostly follow the pattern of "003x" or "004x", and the last (empty) line has "0000" as its first 4 characters. You can check that these 4 characters encode the length of each line (including the 4 characters at the start and the newline character at the end) in hexadecimal. The "0000" line is special; it indicates the end of the lines being sent. git documentation calls prefixing each line with its length in hexadecimal the "pkt-line" format. I'll refer to these lines as "chunks".

We'll see chunks later with binary data instead of text, so we'll start with a method to read a chunk as bytes:

const CHUNK_LENGTH_DIGITS: usize = 4;

impl Transport {
  fn read_chunk(&mut self) -> io::Result<Option<Vec<u8>>> {
    // Chunks start with 4 hexadecimal digits indicating their length,
    // including the length digits
    let length_digits: [_; CHUNK_LENGTH_DIGITS] =
      read_bytes(&mut self.ssh_output)?;
    let chunk_length = length_digits.iter().try_fold(0, |value, &byte| {
      let char_value = hex_char_value(byte)?;
      Some(value << 4 | char_value as usize)
    }).ok_or_else(|| {
      make_error(&format!("Invalid chunk length: {:?}", length_digits))
    })?;
    // The chunk "0000" indicates the end of a sequence of chunks
    if chunk_length == 0 {
      return Ok(None)
    }

    let chunk_length = chunk_length.checked_sub(CHUNK_LENGTH_DIGITS)
      .ok_or_else(|| {
        make_error(&format!("Chunk length too short: {}", chunk_length))
      })?;
    let mut chunk = vec![0; chunk_length];
    self.ssh_output.read_exact(&mut chunk)?;
    Ok(Some(chunk))
  }
}

Then we can read a text chunk by converting the bytes to a string and removing the \n at the end:

impl Transport {
  fn read_text_chunk(&mut self) -> io::Result<Option<String>> {
    let chunk = self.read_chunk()?;
    let chunk = match chunk {
      Some(chunk) => chunk,
      _ => return Ok(None),
    };

    let mut text_chunk = String::from_utf8(chunk).map_err(|_| {
      make_error("Invalid text chunk")
    })?;
    // Text chunks should end with a newline character, but don't have to.
    // Remove it if it exists.
    if text_chunk.ends_with('\n') {
      text_chunk.pop();
    }
    Ok(Some(text_chunk))
  }
}

fn main() -> io::Result<()> {
  // ...

  let mut transport = Transport::connect(origin_url)?;
  // Print each text chunk the server sends back
  while let Some(chunk) = transport.read_text_chunk()? {
    println!("{:?}", chunk);
  }
  Ok(())
}

This program shows every parsed text chunk until the 0000 line which indicates the end of chunks. The chunks look identical to the SSH output with the 4 hexadecimal characters removed from the start of each line. We can also see a 0 byte (\u{0}) in the first text chunk that was hidden by my terminal.

"74cc1aa55f30ed76424a0e7226ab519aa6265061 HEAD\u{0}multi_ack thin-pack side-band side-band-64k ofs-delta shallow deepen-since deepen-not deepen-relative no-progress include-tag multi_ack_detailed allow-tip-sha1-in-want allow-reachable-sha1-in-want symref=HEAD:refs/heads/master filter object-format=sha1 agent=git/github-g2faa647c16c3"
"74cc1aa55f30ed76424a0e7226ab519aa6265061 refs/heads/main"
"4c53a8c20f8984adb226293a3ffd7b88c3f4ac1a refs/heads/maint"
"74cc1aa55f30ed76424a0e7226ab519aa6265061 refs/heads/master"
"d65ed663a79d75fb636a4602eca466dbd258082e refs/heads/next"
"583a5781c12c1d6d557fae77552f6cee5b966f8d refs/heads/seen"
"b1b3e2657f1904c7c603ea4313382a24af0fd91f refs/heads/todo"
"f0d0fd3a5985d5e588da1e1d11c85fba0ae132f8 refs/pull/10/head"
"c8198f6c2c9fc529b25988dfaf5865bae5320cb5 refs/pull/10/merge"
...
"dcba104ffdcf2f27bc5058d8321e7a6c2fe8f27e refs/tags/v2.9.5"
"4d4165b80d6b91a255e2847583bd4df98b5d54e1 refs/tags/v2.9.5^{}"

Refs

Looking at the lines sent by the server, we can see that each one lists a commit hash and a name (HEAD, refs/heads/main, etc.). The first line also has an additional string of capabilities, which we'll discuss shortly. These commit-name combinations are called "refs" (short for "references") and tell the client which commits it can fetch. They fall into several categories:

HEAD: this is the default commit to check out when doing a git clone (it's identical to refs/heads/main)
refs/heads/BRANCH_NAME: these are the branches on the remote repository
refs/tags/TAG_NAME: these are the tags on the remote (not fetched by default)
refs/pull/PULL_REQUEST_NUMBER/head and /merge: these are GitHub-specific, indicating the current commit of each pull request and the commit that merged it into the repository (if applicable)

Here's code to read the refs and capabilities returned by the server:

use std::collections::HashSet;

struct Refs {
  capabilities: HashSet<String>,
  // Map of ref name (e.g. "refs/heads/main") to commit hashes
  refs: HashMap<String, Hash>,
}

impl Transport {
  fn receive_refs(&mut self) -> io::Result<Refs> {
    // The first chunk contains the HEAD ref and a list of capabilities.
    // Even if the repository is empty, capabilities are still needed,
    // so a hash of all 0s is sent.
    let head_chunk = match self.read_text_chunk()? {
      Some(chunk) => chunk,
      _ => return Err(make_error("No chunk received from server")),
    };

    let (head_ref, capabilities) = head_chunk.split_once('\0').ok_or_else(|| {
      make_error("Invalid capabilities chunk")
    })?;
    let capabilities = capabilities.split(' ').map(str::to_string).collect();
    let mut refs = HashMap::new();
    let mut add_ref = |chunk: &str| -> io::Result<()> {
      // Each subsequent chunk contains a ref (a commit hash and a name)
      let (hash, ref_name) = chunk.split_once(' ').ok_or_else(|| {
        make_error("Invalid ref chunk")
      })?;
      let hash = Hash::from_str(hash)?;
      refs.insert(ref_name.to_string(), hash);
      Ok(())
    };
    add_ref(head_ref)?;
    while let Some(chunk) = self.read_text_chunk()? {
      add_ref(&chunk)?;
    }
    Ok(Refs { capabilities, refs })
  }
}

fn main() -> io::Result<()> {
  // ...

  let Refs { capabilities, refs } = transport.receive_refs()?;
  println!("Capabilities: {:?}", capabilities);
  for (ref_name, hash) in refs {
    println!("Ref {} has hash {}", ref_name, hash);
  }
  Ok(())
}

Running this program prints the capabilities and refs the server sent back. Note that the order is randomized since we are iterating over a HashSet and a HashMap.

Capabilities: {"deepen-since", "symref=HEAD:refs/heads/master", "object-format=sha1", "allow-reachable-sha1-in-want", "include-tag", "shallow", "thin-pack", "allow-tip-sha1-in-want", "side-band-64k", "deepen-not", "filter", "agent=git/github-g2faa647c16c3", "side-band", "multi_ack_detailed", "deepen-relative", "ofs-delta", "no-progress", "multi_ack"}
Ref refs/pull/531/head has hash 1572444361982199fdab9c6f6b7e94383717b6c9
Ref refs/pull/983/merge has hash d217f9ec363d5ed88a37ab15a72fad6b4d90acf1
Ref refs/pull/891/head has hash 7d7e794ab7286db0aea88c6e1eab881fc5d188f7
Ref refs/tags/v2.14.1^{} has hash 4d7268b888d7bb6d675340ec676e4239739d0f6d
...
Ref refs/tags/v1.2.3 has hash 51f2164fdc92913c3d1c6d199409b43cb9b6649f

Capabilities

Both the server and client communicate "capabilities" they support. This allows them each to implement new git features while remaining backwards-compatible with older clients and servers. For example, the ofs-delta capability means that the server can send (or the client can understand) "offset delta" objects in packfiles.

The server sends the list of its capabilities and the client requests a subset of them to enable. This way, both the server and client support all the enabled capabilities.

git also uses the capabilities to send miscellaneous information (e.g. symref=HEAD:refs/heads/master indicates that master is the default branch).

For now, we will only request the ofs-delta capability (if the server supports it). The last post (part 2) has an in-depth discussion of offset deltas, but the gist is that they make for smaller packfiles than hash deltas (which are always supported). Just as the server sends its capabilities in its first ref chunk, the client requests capabilities in its first "want" chunk, which we'll discuss next.

Wants

Once the server has advertised the available refs, the client chooses which ones it wants by responding with their hashes. For example, running git pull origin main, the client would only request the commit for ref refs/heads/main. The server sends only the requested commit objects and the commit, tree, and blob objects it (indirectly) references.

Wanted refs are sent as text chunks starting with want. The same format (prefixed by hexadecimal length) is used when sending chunks to the server as when receiving chunks. The only difference is that they are written to the SSH input rather than read from the SSH output.

Here's a Rust implementation. Note that we can send an empty chunk (transport.write_text_chunk(None)) just like we receive an empty chunk at the end of the refs.

// git reserves chunk lengths 65521 to 65535
const MAX_CHUNK_LENGTH: usize = 65520;

impl Transport {
  fn write_text_chunk(&mut self, chunk: Option<&str>) -> io::Result<()> {
    let chunk_length = match chunk {
      // Includes the 4 hexadecimal digits at the start and the \n at the end
      Some(chunk) => CHUNK_LENGTH_DIGITS + chunk.len() + 1,
      _ => 0,
    };
    if chunk_length >= MAX_CHUNK_LENGTH {
      return Err(make_error("Chunk is too large"))
    }

    write!(self.ssh_input, "{:04x}", chunk_length)?;
    if let Some(chunk) = chunk {
      write!(self.ssh_input, "{}\n", chunk)?;
    }
    Ok(())
  }
}

To request a hash, we send a text chunk starting with want. The first want, like the first ref chunk, can also include capabilities that the client requests.

impl Transport {
  fn send_wants(&mut self, hashes: &[Hash], capabilities: &[&str])
    -> io::Result<()>
  {
    let mut first_want = true;
    for hash in hashes {
      println!("Requesting {}", hash);
      let mut chunk = format!("want {}", hash);
      if first_want {
        // Only the first want should list capabilities
        for capability in capabilities {
          chunk.push(' ');
          chunk += capability;
        }
      }
      self.write_text_chunk(Some(&chunk))?;
      first_want = false;
    }
    self.write_text_chunk(None)
  }
}

Putting this all together, we can now tell the server which refs to send. We'll fetch all the branches (i.e. refs starting with refs/heads/).

const BRANCH_REF_PREFIX: &str = "refs/heads/";
const REQUESTED_CAPABILITIES: &[&str] = &["ofs-delta"];

impl Transport {
  fn fetch(&mut self) -> io::Result<()> {
    let Refs { capabilities, refs } = self.receive_refs()?;
    // Request all the capabilities that we want and the server supports
    let use_capabilities: Vec<_> = REQUESTED_CAPABILITIES.iter()
      .copied()
      .filter(|&capability| capabilities.contains(capability))
      .collect();
    // Request all refs corresponding to branches
    // (not tags, pull requests, etc.)
    let branch_refs: Vec<_> = refs.iter()
      .filter_map(|(ref_name, &hash)| {
        ref_name.strip_prefix(BRANCH_REF_PREFIX).map(|branch| (branch, hash))
      })
      .collect();
    let wants: Vec<_> = branch_refs.iter().map(|&(_, hash)| hash).collect();
    self.send_wants(&wants, &use_capabilities)?;

    // TODO: there's another negotiation with the server about which objects
    // the client already has, but for now we'll pretend it has none.
    // We'll implement this later (see "Haves").
    self.write_text_chunk(Some("done"))?;
    self.read_text_chunk()?;

    // TODO: receive the objects the server sends back
    Ok(())
  }
}

fn main() -> io::Result<()> {
  // ...

  transport.fetch()
}

Running this program shows that 6 branches (main, maint, master, next, seen, and todo) were requested. Since main and master are interchangeable, one of the commits is requested twice (this is unnecessary but allowed).

Requesting b1b3e2657f1904c7c603ea4313382a24af0fd91f
Requesting 583a5781c12c1d6d557fae77552f6cee5b966f8d
Requesting 74cc1aa55f30ed76424a0e7226ab519aa6265061
Requesting 74cc1aa55f30ed76424a0e7226ab519aa6265061
Requesting d65ed663a79d75fb636a4602eca466dbd258082e
Requesting 4c53a8c20f8984adb226293a3ffd7b88c3f4ac1a

Packfiles make a triumphant return

Once the server knows what objects the client needs, it must send them. There are potentially thousands of commits, trees, and blobs, so it's important to encode them compactly. If you read the last post (part 2), you'll see this is a primary use case for packfiles.

So the server builds a packfile containing all the objects and sends it to the client over the SSH connection. git could unpack the objects from this packfile, but as we saw in the last post, it leaves them packed by default to save storage space.

We'll do the same, creating a temp.pack file in the packfile directory. Since the packfile contents are sent to the SSH output, we can simply copy the output to a file:

const TEMP_PACK_FILE: &str = ".git/objects/pack/temp.pack";

impl Transport {
  fn fetch(&mut self) -> io::Result<()> {
    // ...

    let mut pack_file = File::create(TEMP_PACK_FILE)?;
    io::copy(&mut self.ssh_output, &mut pack_file)?;
    Ok(())
  }
}

fn main() -> io::Result<()> {
  // ...

  transport.fetch()
}

Running this program successfully downloads the pack file!

$ mkdir git
$ cd git
$ git init # create an empty git repository to test fetching all the objects
Initialized empty Git repository
$ git remote add origin git@github.com:git/git.git
$ cargo run
$ file .git/objects/pack/temp.pack
.git/objects/pack/temp.pack: Git pack, version 2, 324311 objects

Saving refs

Now we have all the objects we need, but unfortunately trying to use them in a git command still doesn't work:

$ git log origin/main
fatal: ambiguous argument 'origin/main': unknown revision or path not in the working tree.
Use '--' to separate paths from revisions, like this:
'git <command> [<revision>...] -- [<file>...]'

This is because we haven't updated the "remote refs" that we received from the server. For example, the server told us that main is currently at commit 74cc1aa55f30ed76424a0e7226ab519aa6265061:

74cc1aa55f30ed76424a0e7226ab519aa6265061 refs/heads/main

So we need to store this remote ref in the local repository.

Back in post 1, we saw that the local branches (and refs in general) are stored in the .git/refs directory. Each remote (e.g. origin) has its own subdirectory in .git/refs with all the refs fetched from the remote.

Here is code to create the ref files during the fetch:

use std::fs;
use std::path::Path;

const REMOTE_ORIGIN_REFS_DIRECTORY: &str = ".git/refs/remotes/origin";

fn save_remote_ref(branch: &str, hash: Hash) -> io::Result<()> {
  let origin_ref_path = Path::new(REMOTE_ORIGIN_REFS_DIRECTORY).join(branch);
  // Create .git/refs/remotes and .../origin if they don't exist.
  // Also, if the branch includes '/' (e.g. "feature/abc"), the path will be
  // .../feature/abc, so the "feature" directory must also be created.
  fs::create_dir_all(origin_ref_path.parent().unwrap())?;
  let mut origin_ref_file = File::create(origin_ref_path)?;
  write!(origin_ref_file, "{}\n", hash)
}

impl Transport {
  fn fetch(&mut self) -> io::Result<()> {
    // ...

    for (branch, hash) in branch_refs {
      save_remote_ref(branch, hash)?;
    }
    Ok(())
  }
}

Now, running our program records the remote refs:

$ ls -R .git/refs/remotes
origin

.git/refs/remotes/origin:
main   maint  master next   seen   todo

Let's try running the git log again. This time, it fails with a different error: it knows that origin/main is commit 74cc1aa55f30ed76424a0e7226ab519aa6265061, but it can't read that object.

$ git log origin/main
fatal: bad object origin/main

git can't find the object because we're missing a .idx file for the temp.pack file we created. We'll fix this next.

Building an index file

As we saw in the last post, scanning through a packfile is slow, so git depends on a corresponding "pack index" file to locate objects in the packfile. The index file acts like a HashMap<Hash, u64>, making it fast to look up where an object is located in the corresponding packfile. It can be generated from the packfile by decompressing (and un-deltifying, if necessary) each object in the pack and computing its hash. The server doesn't send it because it doesn't contain any additional information, so we need to build it ourselves.

We'll use the code we wrote last time to read objects out of packfiles, with one main modification. Before, we only wanted to unpack a single object, so if the object was a HashDelta or OffsetDelta, we had to unpack its base object, and its base object's base object, etc. until we found an undeltified object. If we use this approach for all the objects in the packfile, we may recompute each base object many times. For example, if both objects B and C are deltified with base object A, then unpacking the objects will unpack A 3 times (when computing each of A, B, and C). And for HashDeltas that refer to base objects within the packfile, we can't even find the base object by hash because we haven't created a pack index yet! So I've modified the code to remember the objects unpacked from the packfile so far by both hash and offset. See the source code for the full details.

First we'll read the temporary packfile (see the last post for a detailed discussion of the packfile format):

// Creates a temporary pack index for the temporary packfile
// and returns the packfile's checksum
fn build_pack_index() -> io::Result<Hash> {
  let mut pack_file = File::open(TEMP_PACK_FILE)?;
  let magic = read_bytes(&mut pack_file)?;
  if magic != *b"PACK" {
    return Err(make_error("Invalid packfile"))
  }

  let version = read_u32(&mut pack_file)?;
  if version != 2 {
    return Err(make_error("Unexpected packfile version"))
  }

  let total_objects = read_u32(&mut pack_file)?;
  // Cache the unpacked objects by offset and hash
  let mut object_cache = PackObjectCache::default();
  // Count how many objects have a hash starting with each byte
  let mut first_byte_objects = [0u32; 1 << u8::BITS];
  // Store where each hash is located in the packfile
  // (the sorted version of this is the index)
  let mut object_offsets = Vec::with_capacity(total_objects as usize);
  // Unpack each object
  for _ in 0..total_objects {
    let offset = get_offset(&mut pack_file)?;
    let object = read_pack_object(&mut pack_file, offset, &mut object_cache)?;
    let object_hash = object.hash();
    first_byte_objects[object_hash.0[0] as usize] += 1;
    let offset = u32::try_from(offset).map_err(|_| {
      make_error("Packfile is too large")
    })?;
    object_offsets.push((object_hash, offset));
  }
  let pack_checksum = read_hash(&mut pack_file)?;
  assert!(at_end_of_stream(&mut pack_file)?);

  // TODO: produce index file

  Ok(pack_checksum)
}

Although the last post discussed version-2 index files, we will make a version-1 one for simplicity. git can still understand them; the only restriction is that they can only represent offsets that fit in a u32 (hence the check above). Here's the implementation:

const TEMP_INDEX_FILE: &str = ".git/objects/pack/idx.pack";

fn build_pack_index() -> io::Result<Hash> {
  // ...

  let mut index_file = File::create(TEMP_INDEX_FILE)?;
  let mut cumulative_objects = 0;
  for objects in first_byte_objects {
    cumulative_objects += objects;
    // The number (u32) of hashes with first byte <= 0, 1, ..., 255
    index_file.write_all(&cumulative_objects.to_be_bytes())?;
  }
  // Each hash and its offset (u32) in the pack file,
  // sorted for efficient lookup
  object_offsets.sort();
  for (hash, offset) in object_offsets {
    index_file.write_all(&offset.to_be_bytes())?;
    index_file.write_all(&hash.0)?;
  }
  // A SHA-1 checksum of the pack file
  index_file.write_all(&pack_checksum.0)?;
  // TODO: this should be a SHA-1 hash of the contents of the index file.
  // But git doesn't check it when reading the index file, so we'll skip it.
  index_file.write_all(&[0; HASH_BYTES])?;
  Ok(pack_checksum)
}

And finally, we rename the temporary pack and index files with the pack checksum, like git does:

impl Transport {
  fn fetch(&mut self) -> io::Result<()> {
    // ...

    let pack_hash = build_pack_index()?;
    // Rename the packfile to, e.g.
    // pack-bda11b853cfa9131a39b2e3e55f15bb7f7485450.pack
    let pack_file_name = Path::new(PACKS_DIRECTORY)
      .join(format!("pack-{}{}", pack_hash, PACK_FILE_SUFFIX));
    fs::rename(TEMP_PACK_FILE, pack_file_name)?;
    // Rename the index file to, e.g.
    // pack-bda11b853cfa9131a39b2e3e55f15bb7f7485450.idx
    let index_file_name = Path::new(PACKS_DIRECTORY)
      .join(format!("pack-{}{}", pack_hash, INDEX_FILE_SUFFIX));
    fs::rename(TEMP_INDEX_FILE, index_file_name)?;

    // ...
  }
}

If we do another fetch, we generate an index file and our git log finally works! If you're trying this at home, make sure to run in release mode, or otherwise it will be much too slow! (The code could probably be sped up significantly by using BufReaders and BufWriters with these files and the SSH output.)

$ ls -lh .git/objects/pack
total 394896
-rw-r--r--  1 csander  staff   7.4M Mar 19 15:56 pack-bda11b853cfa9131a39b2e3e55f15bb7f7485450.idx
-rw-r--r--  1 csander  staff   185M Mar 19 15:56 pack-bda11b853cfa9131a39b2e3e55f15bb7f7485450.pack
$ git log origin/main
commit 74cc1aa55f30ed76424a0e7226ab519aa6265061 (origin/master, origin/main)
Author: Junio C Hamano <gitster@pobox.com>
Date:   Wed Mar 16 17:45:59 2022 -0700

    The twelfth batch

    Signed-off-by: Junio C Hamano <gitster@pobox.com>
...

We can even use git show to show the diff of this commit, which requires reading commit, tree, and blob objects from the packfile:

$ git show origin/main
commit 74cc1aa55f30ed76424a0e7226ab519aa6265061
Author: Junio C Hamano <gitster@pobox.com>
Date:   Wed Mar 16 17:45:59 2022 -0700

    The twelfth batch

    Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/Documentation/RelNotes/2.36.0.txt b/Documentation/RelNotes/2.36.0.txt
index 6b2c6bfcc7..d67727baa1 100644
--- a/Documentation/RelNotes/2.36.0.txt
+++ b/Documentation/RelNotes/2.36.0.txt
@@ -70,6 +70,10 @@ UI, Workflows & Features
  * The level of verbose output from the ort backend during inner merge
    has been aligned to that of the recursive backend.

+ * "git remote rename A B", depending on the number of remote-tracking
+   refs involved, takes long time renaming them.  The command has been
+   taught to show progress bar while making the user wait.
+

 Performance, Internal Implementation, Development Support etc.

@@ -122,6 +126,12 @@ Performance, Internal Implementation, Development Support etc.
  * Makefile refactoring with a bit of suffixes rule stripping to
    optimize the runtime overhead.

+ * "git stash drop" is reimplemented as an internal call to
+   reflog_delete() function, instead of invoking "git reflog delete"
+   via run_command() API.
+
+ * Count string_list items in size_t, not "unsigned int".
+

 Fixes since v2.35
 -----------------
@@ -299,6 +309,17 @@ Fixes since v2.35
    Adjustments have been made to accommodate these changes.
    (merge b0b70d54c4 fs/gpgsm-update later to maint).

+ * The untracked cache newly computed weren't written back to the
+   on-disk index file when there is no other change to the index,
+   which has been corrected.
+
+ * "git config -h" did not describe the "--type" option correctly.
+   (merge 5445124fad mf/fix-type-in-config-h later to maint).
+
+ * The way generation number v2 in the commit-graph files are
+   (not) handled has been corrected.
+   (merge 6dbf4b8172 ds/commit-graph-gen-v2-fixes later to maint).
+
  * Other code cleanup, docfix, build fix, etc.
    (merge cfc5cf428b jc/find-header later to maint).
    (merge 40e7cfdd46 jh/p4-fix-use-of-process-error-exception later to maint).

Haves

Great, we can clone a real repository!

Now let's imagine there is a slight change to the repository (e.g. one commit is pushed to main). If we do Transport::fetch() again, we'll download a new packfile with all the objects now in the remote repository. This would work, but unfortunately we would end up with two copies of each object that was already in the repository!

We would definitely like to avoid wasting space storing duplicate objects. We could do this by identifying the duplicate objects and making a new packfile without them. But ideally the server wouldn't have sent them in the first place, as this makes the fetch unnecessarily slow.

In order for the server to know exactly which objects the packfile needs, the client needs to tell the server which ones it already has. After the want chunks are sent in the transport protocol, the client informs the server of objects it already has by sending have chunks. The haves are terminated by a "done" chunk. The server responds with an ACK chunk if it recognizes any of the client's haves, or a NAK chunk otherwise. (See the multi_ack documentation for the more complicated negotiation that git uses in practice.)

The client could tell the server every object it has, but there can easily be hundreds of thousands, and so this would still take a lot of space even at 20 bytes each. git makes use of the fact that when the client receives objects from the server, it always gets exactly those that are referenced by one or more commits. For example, suppose there are commits C1, C2, and C3 with trees T1, T2, and T3, respectively, and a few blobs:

C1 <-- C2 <-- C3
|      |      |
v      v      v
T1     T2     T3
| \   /  \   /| \
v   v      v  v  v
B1  B2     B3 B4 B5

When the client sent want C2 before, it received C1, C2, T1, T2, B1, B2, and B3 because they C2 (indirectly) references them. So if the client tells the server it has C2, the server knows it has all these objects, but not C3, T3, B4, or B5.

Therefore, the client can just say the latest commit it has fetched on each remote branch and the server will know exactly which of its objects the client already has. (git's implementation also checks for commits from the client that are on the remote without the client's knowledge. For example, the client pushed to remote A and someone else then fetched and pushed to remote B. But we won't worry about optimizing for that situation.)

We will send a have for the commit hash we have recorded for each remote branch:

use std::path::PathBuf;

impl Transport {
  // Sends haves for all refs under the given ref directory
  fn send_haves_dir(&mut self, ref_path: &mut PathBuf) -> io::Result<()> {
    let entries = fs::read_dir(&ref_path);
    if let Err(err) = &entries {
      if err.kind() == ErrorKind::NotFound {
        // If .git/refs/remotes/origin doesn't exist, there are no haves
        return Ok(())
      }
    }

    for entry in entries? {
      let entry = entry?;
      ref_path.push(entry.file_name());
      let entry_type = entry.file_type()?;
      if entry_type.is_dir() {
        // Explore subdirectories recursively (to find refs containing '/')
        self.send_haves_dir(ref_path)?;
      }
      else {
        let hash = fs::read_to_string(&ref_path)?;
        let hash = Hash::from_str(hash.trim_end())?;
        self.write_text_chunk(Some(&format!("have {}", hash)))?;
      }
      ref_path.pop();
    }
    Ok(())
  }

  fn send_haves(&mut self) -> io::Result<()> {
    fn valid_have_response(response: Option<&str>) -> bool {
      // Expect "ACK {HASH}" if acknowledged, "NAK" otherwise
      match response {
        Some("NAK") => true,
        Some(response) => {
          match response.strip_prefix("ACK ") {
            Some(hash) => Hash::from_str(hash).is_ok(),
            _ => false,
          }
        }
        _ => false,
      }
    }

    // Send haves for all the most recent commits we have fetched
    self.send_haves_dir(&mut PathBuf::from(REMOTE_ORIGIN_REFS_DIRECTORY))?;
    self.write_text_chunk(Some("done"))?;
    let response = self.read_text_chunk()?;
    if !valid_have_response(response.as_deref()) {
      return Err(make_error("Invalid ACK/NAK"))
    }

    Ok(())
  }

  fn fetch(&mut self) -> io::Result<()> {
    // ...

    self.send_wants(&wants, &use_capabilities)?;

    self.send_haves()?;

    // ...
  }
}

If we fetch the git repository again with no new commits, the server sends an empty packfile because the client already has all the required objects:

$ cargo run
$ ls -lh .git/objects/pack
total 410624
-rw-r--r--  1 csander  staff   1.0K Mar 19 17:29 pack-029d08823bd8a8eab510ad6ac75c823cfd3ed31e.idx
-rw-r--r--  1 csander  staff    32B Mar 19 17:29 pack-029d08823bd8a8eab510ad6ac75c823cfd3ed31e.pack
-rw-r--r--  1 csander  staff   7.4M Mar 19 16:38 pack-8641e8298f69b5dc78c3eb224dc508757f59a13f.idx
-rw-r--r--  1 csander  staff   185M Mar 19 16:37 pack-8641e8298f69b5dc78c3eb224dc508757f59a13f.pack
$ file .git/objects/pack/pack-029d08823bd8a8eab510ad6ac75c823cfd3ed31e.pack
.git/objects/pack/pack-029d08823bd8a8eab510ad6ac75c823cfd3ed31e.pack: Git pack, version 2, 0 objects

Side-band progress updates

It may take a while for the server to prepare and transmit a packfile, so it's helpful to provide the user some progress updates. The protocol we've seen so far doesn't allow for this, but there is yet another capability, side-band-64k, to enable it.

Instead of sending the packfile directly on the SSH connection, the server breaks it up and sends each piece inside a chunk. Between packfile chunks, the server can send progress or error message chunks. The first byte of each chunk indicates the type of chunk (1 for packfile data, 2 for progress message, or 3 for fatal error message). The remainder of the chunk is either the next piece of the packfile or a message to print. An empty chunk is sent to terminate the side-band chunks.

Here is the implementation:

const SIDE_BAND_CAPABILITY: &str = "side-band-64k";
const REQUESTED_CAPABILITIES: &[&str] = &["ofs-delta", SIDE_BAND_CAPABILITY];

impl Transport {
  fn receive_side_band_pack(&mut self, pack_file: &mut File) -> io::Result<()> {
    while let Some(chunk) = self.read_chunk()? {
      let (&chunk_type, chunk) = chunk.split_first().ok_or_else(|| {
        make_error("Missing side-band chunk type")
      })?;
      match chunk_type {
        // Packfile data
        1 => pack_file.write_all(chunk)?,
        // Progress message; print to stderr
        2 => io::stderr().write_all(chunk)?,
        // Fatal fetch error message
        3 => {
          let err = format!("Fetch error: {}", String::from_utf8_lossy(chunk));
          return Err(make_error(&err))
        }
        _ => {
          let err = format!("Invalid side-band chunk type {}", chunk_type);
          return Err(make_error(&err))
        }
      }
    }
    Ok(())
  }

  fn fetch(&mut self) -> io::Result<()> {
    // ...

    let mut pack_file = File::create(TEMP_PACK_FILE)?;
    // Check whether we were able to enable side-band-64k
    if capabilities.contains(SIDE_BAND_CAPABILITY) {
      // The packfile is wrapped in side-band chunks
      self.receive_side_band_pack(&mut pack_file)?;
    }
    else {
      // The SSH stream has the packfile contents
      io::copy(&mut self.ssh_output, &mut pack_file)?;
    }

    // ...
  }
}

If we now call Transport::fetch(), we see the server's progress indicators:

Enumerating objects: 324311, done.
Total 324311 (delta 0), reused 0 (delta 0), pack-reused 324311

Here, the server had already created a packfile with the required objects and is simply sending it to us. If the git server needs to generate a new packfile, we will see additional status indicators, for example:

Enumerating objects: 7605, done.
Counting objects: 100% (630/630), done.
Compressing objects: 100% (292/292), done.
Total 7605 (delta 421), reused 448 (delta 333), pack-reused 6975

In the "Counting objects" phase, git is determining which objects it doesn't already have in packfiles (630 = 7605 - 6975). In the "Compressing objects" phase, git is creating deltified representations for some of these new objects.

For long fetches, you may have noticed that these progress indicators update periodically. If you're wondering how that works, it's by printing the \r (carriage return) character followed by the new contents of the line. \r this resets the terminal's printing location to the start of the current line, but unlike \n, doesn't advance to the next line.

push protocol

We've covered all of the major parts of a git fetch over the SSH transport. But how does a git push work? Perhaps unsurprisingly, git reuses much of the SSH protocol for pushes. So much is the same that I don't think there's much to learn by implementing git push too.

The major differences between fetch and push are:

The SSH command invokes git-receive-pack instead of git-upload-pack
No have negotiation is required because the client already knows which of its commits the server has (since it pushed them)
After receiving the list of refs from the server, the client indicates which ones it wants to create (e.g. new branch), update (e.g. new commit on branch), or delete (e.g. remove branch)
The client sends the packfile of new objects to the server

The end

And that's a wrap on the git internals series! We learned how a large portion of git works under the hood, from the .git directory to how repository history is stored in objects, from how packfiles combine and compress objects to how a git client and server communicate to share a repository. Hopefully the next time you run a git command you'll have a newfound understanding and appreciation for how it does its task.

Sorry these posts ended up being so long; there are just so many interesting pieces in the git puzzle! Please let me know if there are any other git topics you'd like me to cover. I have several other (hopefully shorter!) posts I'd like to write on a variety of topics, so stay tuned.

Git Internals part 2: packfiles

Caleb Sander — Sat, 27 Nov 2021 19:34:16 +0000

This post continues the "Git Internals" series. In part 1, we introduced git's object storage model. This post will look at object storage in more depth, so I recommend looking at that post first if you haven't already.

First, we'll see that git usually does not store objects the way we saw last time. We'll introduce the "packfile", which is what git uses instead.

Then, we'll look at the two parts of a packfile: the .idx and .pack files. Since git uses the .idx file to access the .pack file, we'll examine the .idx file first. Then we'll dig into the .pack file to understand how git can store objects more efficiently by "packing" them together. The design of the .pack file is much more interesting, so I recommend skipping past the .idx discussion to the .pack section if your time is limited.

The source code for this post can be found here.

A convenient lie

In the last post, we saw that git objects (including commits, trees, and blobs) are stored in the .git/objects directory. So let's clone a repository and look at its objects:

$ git clone git@github.com:git/git.git
$ cd git
$ ls -R .git/objects
info pack

.git/objects/info:

.git/objects/pack:
pack-d851c0ab72a0034ab858061940ed04abebe20d32.idx
pack-d851c0ab72a0034ab858061940ed04abebe20d32.pack

What happened to all the object files?!

Given the title of this post, you might guess that the files in the .git/objects/pack directory have something to do with it. We can test this hypothesis by temporarily moving the packfiles:

$ git show # successfully displays the current commit
$ mv .git/objects/pack/* . # move the pack-* files out of the .git directory
$ git show
fatal: bad object HEAD

So all the objects must be stored somehow in the .idx or .pack file. If we look at their sizes, we can see that the .pack file is about 20 times larger (174 vs 8.5 MB), so it looks like that's where the objects are:

ls -lh .git/objects/pack/*
-r--r--r--  1 csander  staff   8.5M Nov 11 20:17 .git/objects/pack/pack-d851c0ab72a0034ab858061940ed04abebe20d32.idx
-r--r--r--  1 csander  staff   174M Nov 11 20:17 .git/objects/pack/pack-d851c0ab72a0034ab858061940ed04abebe20d32.pack

The corresponding .idx ("index") file doesn't contain any additional information; it is generated from the .pack file. However, git is also unable to read objects if the .idx file is moved. This suggests that the .idx file is needed to find the objects within the .pack file.

Why packfiles?

The convenient lie from the last post was that each object is stored as an individual file. While git does store new objects like this, git may combine multiple objects into a packfile to reduce storage space.

In its simplest form, a packfile is essentially the concatenation of (compressed) object files. This makes it easier to transfer many objects during a git push or pull (more accurately, a fetch). However, the real benefit of a packfile is that it can store objects as diffs ("deltas") from other objects. As mentioned in the last post, git tends to create many similar objects, such as the new blob created when making a small change to a file. Whereas storing objects individually would require storing each entire blob, a packfile can store just one of the blobs and express the other as a delta from the first.

git generates packfiles in two main cases:

Transferring objects during a push or pull. For the common git protocols, communicating with a remote repository always involves sending a packfile. We'll look at git transports in detail in the next post.
Periodic "garbage collection" of the .git/objects folder. If git decides there are too many individual objects, it combines them into a packfile to reduce the repository's size on disk.

What's in a packfile?

Unfortunately, unlike individual object files, .pack and .idx file formats are neither straightforward nor human-readable. The best description of how they work is the Documentation/technical/pack-format.txt file within the git source code, rendered here. We'll implement the specification, which will require filling in a few details where the documentation is vague. The .idx (packfile index) file is what git reads first to find an object within a packfile, so we'll start with it.

Packfile indices

The goal of a packfile index is to take an object hash (e.g. 4d53e91c6b2c3f5b5c7375e579a453fc5053c08b) and efficiently locate it in a packfile. This is important to ensure that reading objects from packfiles isn't too much slower than reading them from the .git/objects directory (the approach we covered in the last post). Since an object could be located anywhere within a many-MB packfile, the .idx file acts as a map from hashes to positions within the packfile.

So, if we want to find an object, we first check the .git/objects directory for an unpacked object file (e.g. .git/objects/4d/53e91c6b2c3f5b5c7375e579a453fc5053c08b). If it isn't unpacked, we look through each packfile index until we find the packfile containing the object.

The index header

The packfile index starts with the magic bytes [0xff, b't', b'O', b'c'] ("table of contents"?). This is followed by the version number 2, stored as a big-endian 32-bit integer (i.e. the bytes [0, 0, 0, 2]). (There is a version 1 format as well, but we will ignore it since git no longer creates it.) We'll start by asserting that the index file has the correct header:

use std::fs::File;
use std::io::{self, Read};

const PACKS_DIRECTORY: &str = ".git/objects/pack";

// Reads a fixed number of bytes from a stream.
// Rust's "const generics" make this function very useful.
fn read_bytes<R: Read, const N: usize>(stream: &mut R)
  -> io::Result<[u8; N]>
{
  let mut bytes = [0; N];
  stream.read_exact(&mut bytes)?;
  Ok(bytes)
}

// Reads a big-endian 32-bit (4-byte) integer from a stream
fn read_u32<R: Read>(stream: &mut R) -> io::Result<u32> {
  let bytes = read_bytes(stream)?;
  Ok(u32::from_be_bytes(bytes))
}

fn read_pack_index(file: &str) -> io::Result<()> {
  let mut file = File::open(Path::new(PACKS_DIRECTORY).join(file))?;

  // Check index header
  let magic = read_bytes(&mut file)?;
  assert_eq!(magic, *b"\xfftOc");
  let version = read_u32(&mut file)?;
  assert_eq!(version, 2);

  // TODO: read the rest of the index
}

fn main() -> io::Result<()> {
  let args: Vec<_> = env::args().collect();
  let [_, index_file] = <[String; 2]>::try_from(args).unwrap();
  read_pack_index(&index_file)
}

And it runs successfully:

$ cd git
$ cargo run pack-d851c0ab72a0034ab858061940ed04abebe20d32.idx

The list of hashes

Recall that the index file acts as a map from object hashes to offsets within the pack. It's structured much like a hash map (no pun intended). The hash map has 256 buckets, and the first byte of an object's hash determines which one it falls into. Then, since multiple hashes can have the same first byte, each bucket contains a list of all the hashes with that first byte. The hashes in each bucket are pre-sorted so a hash can be quickly found within its bucket using a binary search. (Since the buckets are ordered by the first byte of the hash, this means that all the hashes in the index file are in sorted order.)

// Copied from the last post
struct Hash([u8; HASH_BYTES]);

// Read an object hash from a stream
fn read_hash<R: Read>(stream: &mut R) -> io::Result<Hash> {
  let bytes = read_bytes(stream)?;
  Ok(Hash(bytes))
}

fn read_pack_index(file: &str) -> io::Result<()> {
  // ...

  // For each of the 256 possible first bytes `b` of a hash,
  // read the cumulative number of objects with first byte <= `b`
  let mut cumulative_objects = [0; 1 << u8::BITS];
  for objects in &mut cumulative_objects {
    *objects = read_u32(&mut file)?;
  }

  // Read the hash of each of the objects.
  // Check that the hashes have the correct first byte and are sorted.
  let mut previous_objects = 0;
  for (first_byte, &objects) in cumulative_objects.iter().enumerate() {
    // The difference in the cumulative number of objects
    // is the number of objects with this first byte
    let mut previous_hash = None;
    for _ in 0..(objects - previous_objects) {
      // We already know the first byte of the hash, so ensure it matches
      let hash = read_hash(&mut file)?;
      assert_eq!(hash.0[0], first_byte as u8);
      if let Some(previous_hash) = previous_hash {
        assert!(hash > previous_hash);
      }
      previous_hash = Some(hash);
    }
    previous_objects = objects;
  }
  // `cumulative_objects[255]` is the total number of objects
  let total_objects = previous_objects;

  // TODO: read the rest of the index
}

The object offsets

Now we've read all the object hashes, but we still haven't figured out where the objects are in the packfile.

Following the list of objects, there are two more lists. These lists both have with one element corresponding to every object. First is a list of checksums (specifically, CRC-32s) of the packed objects. These aren't necessary to read the objects, so we'll ignore them. Then, there is the list of positions of the objects within the packfile. For example, if an object's packed data starts at byte 1234 of the packfile, the 32-bit integer 1234 would be stored in this list.

fn read_pack_index(file: &str) -> io::Result<()> {
  // ...

  // Read a checksum of the packed data for each object
  for _ in 0..total_objects {
    let _crc32 = read_u32(&mut file)?;
  }

  // Read the offset of each object within the packfile
  for _ in 0..total_objects {
    let _pack_offset = read_u32(&mut file)?;
    // TODO: there's one more step needed to read large pack offsets
  }
}

And this is all we need to read our example .idx file! However, storing each pack offset as a 32-bit integer means we can't represent an offset into a packfile larger than 2³² bytes (4 GB). (This limitation with version 1 index files is the reason for version 2.) The index file could support larger packfiles by storing the offset as a 64-bit integer, but this would waste space for the vast majority of packfiles.

Instead, the most significant bit of the 32-bit pack offset indicates whether a 64-bit offset is needed. If it is set, the value is instead an index into a list of 64-bit offsets directly after the 32-bit offsets:

// The most significant bit of a 32-bit integer
const LONG_OFFSET_FLAG: u32 = 1 << 31;

// Just like read_u32(), except reads a 64-bit integer
fn read_u64<R: Read>(stream: &mut R) -> io::Result<u64> {
  let bytes = read_bytes(stream)?;
  Ok(u64::from_be_bytes(bytes))
}

fn read_pack_index(file: &str) -> io::Result<()> {
  // ...

  // Read the offset of each object within the packfile
  let mut long_offsets = 0;
  for _ in 0..total_objects {
    let pack_offset = read_u32(&mut file)?;
    if pack_offset & LONG_OFFSET_FLAG != 0 {
      // If the most significant bit is set,
      // the offset is instead an index into the 64-bit offsets
      let offset_index = pack_offset & !LONG_OFFSET_FLAG;
      long_offsets = long_offsets.max(offset_index + 1);
    }
  }

  // Read the list of 64-bit offsets, if there are any
  for _ in 0..long_offsets {
    let _pack_offset = read_u64(&mut file)?;
  }
}

Looking up an object offset

Now we've seen how the pack index is laid out by reading it sequentially. But this isn't how the pack index is read. It's instead designed to efficiently take an object hash and determine its offset in the packfile. Keep an eye on how few reads this process requires.

First, we use two consecutive entries in cumulative_objects to get bounds on the index of an object within the index file. (Sorry about the overloaded term "index". I'll use "index" to refer to the location of the object in the sorted list of objects and "index file" to refer to the .idx file.)

use std::io::{Seek, SeekFrom};

const fn cumulative_objects_position(first_byte: u8) -> u64 {
  // Skip the magic bytes, version number,
  // and previous cumulative object counts
  4 + 4 + first_byte as u64 * 4
}

fn seek(file: &mut File, offset: u64) -> io::Result<()> {
  file.seek(SeekFrom::Start(offset))?;
  Ok(())
}

// Gets lower and upper bounds on the index of an object hash
// in an index file, using the cumulative object counts
fn get_object_index_bounds(index_file: &mut File, hash: Hash)
  -> io::Result<(u32, u32)>
{
  // The previous cumulative object count is the lower bound (inclusive)
  let first_byte = hash.0[0];
  let index_lower_bound = if first_byte == 0 {
    seek(index_file, cumulative_objects_position(0))?;
    // There aren't any hashes with a lower first byte than 0
    0
  }
  else {
    seek(index_file, cumulative_objects_position(first_byte - 1))?;
    read_u32(index_file)?
  };
  // The next cumulative object count is the upper bound (exclusive)
  let index_upper_bound = read_u32(index_file)?;
  Ok((index_lower_bound, index_upper_bound))
}

Then, to actually find the object's index, we perform a binary search between these index bounds:

const TOTAL_OBJECTS_POSITION: u64 = cumulative_objects_position(u8::MAX);
fn hash_position(object_index: u32) -> u64 {
  // Skip the cumulative object counts and the previous hashes
  TOTAL_OBJECTS_POSITION + 4 + object_index as u64 * HASH_BYTES as u64
}

fn get_object_index(index_file: &mut File, hash: Hash)
  -> io::Result<Option<u32>>
{
  use std::cmp::Ordering::*;

  // Track the range of possible indices for the object hash.
  // (left_index is inclusive, right_index is exclusive)
  let (mut left_index, mut right_index) =
    get_object_index_bounds(index_file, hash)?;
  while left_index < right_index {
    // Compare with the object hash in the middle of the range
    let mid_index = left_index + (right_index - left_index) / 2;
    seek(index_file, hash_position(mid_index))?;
    let mid_hash = read_hash(index_file)?;
    match hash.cmp(&mid_hash) {
      Less => right_index = mid_index, // the object is to the left
      Equal => return Ok(Some(mid_index)), // we found the object
      Greater => left_index = mid_index + 1, // the object is to the right
    }
  }
  // If the range is empty, the object isn't in the index file
  Ok(None)
}

Finally, we use the object's index to read its offset from the offset list. (Note that we need to read the total number of objects so we can calculate where the offset list starts.) If the offset is a long offset, we need one more read.

fn crc32_position(total_objects: u32, object_index: u32) -> u64 {
  // Skip the hashes and previous CRC-32s
  hash_position(total_objects) + object_index as u64 * 4
}
fn offset_position(total_objects: u32, object_index: u32) -> u64 {
  // Skip the CRC-32s and previous object offsets
  crc32_position(total_objects, total_objects) + object_index as u64 * 4
}
fn long_offset_position(total_objects: u32, offset_index: u32) -> u64 {
  // Skip the short object offsets and previous long object offsets
  offset_position(total_objects, total_objects) + offset_index as u64 * 8
}

fn get_pack_offset_at_index(index_file: &mut File, object_index: u32)
  -> io::Result<u64>
{
  seek(index_file, TOTAL_OBJECTS_POSITION)?;
  let total_objects = read_u32(index_file)?;
  seek(index_file, offset_position(total_objects, object_index))?;
  let pack_offset = read_u32(index_file)?;
  if pack_offset & LONG_OFFSET_FLAG == 0 {
    // If the flag bit isn't set, the offset is just a 32-bit offset
    Ok(pack_offset as u64)
  }
  else {
    // If the flag bit is set, the rest of the offset
    // is an index into the 64-bit offsets
    let offset_index = pack_offset & !LONG_OFFSET_FLAG;
    seek(index_file, long_offset_position(total_objects, offset_index))?;
    read_u64(index_file)
  }
}

Combining these functions, we can use an index file to find an object in the corresponding pack file:

// Gets the offset of an object in a packfile.
// `pack` is the name of the packfile, without ".idx" or ".pack".
fn get_pack_offset(pack: &str, hash: Hash) -> io::Result<Option<u64>> {
  let path = Path::new(PACKS_DIRECTORY)
    .join(pack.to_string() + INDEX_FILE_SUFFIX);
  let mut file = File::open(path)?;
  let object_index = get_object_index(&mut file, hash)?;
  let object_index = match object_index {
    Some(object_index) => object_index,
    _ => return Ok(None),
  };

  let pack_offset = get_pack_offset_at_index(&mut file, object_index)?;
  Ok(Some(pack_offset))
}

fn main() -> io::Result<()> {
  let args: Vec<_> = env::args().collect();
  let [_, pack, object] = <[String; 3]>::try_from(args).unwrap();
  let offset = get_pack_offset(&pack, Hash::from_str(&object).unwrap())?;
  println!("{:?}", offset);
  Ok(())
}

Looking up a real object shows its offset in the pack, and looking up a fake object shows it's not in the pack:

$ cargo run pack-d851c0ab72a0034ab858061940ed04abebe20d32 4d53e91c6b2c3f5b5c7375e579a453fc5053c08b
Some(3827)
$ cargo run pack-d851c0ab72a0034ab858061940ed04abebe20d32 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
None

Reading an object from a packfile

After the .idx file tells us where an object is located in a packfile, we need to actually read it from there.

The packfile data for an object (much like an unpacked object) starts with its type and size. However, where an unpacked object would have a header like "commit 189\u{0}", the packed object only needs 2 bytes for this information. As in several other places in packfiles, git stores the type and length as a variable-length integer. Variable-length integers allow arbitrarily large values, while using few bytes in the common case of small values. (This is very similar to how UTF-8 works.)

Specifically, git uses the upper bit of each byte to indicate whether there are additional bytes and the remaining 7 bits as data. For example, the bytes [0b1xxxxxxx, 0b1yyyyyyy, 0b0zzzzzzz] represent the integer 0bzzzzzzzyyyyyyyxxxxxxx. Note that values 0 to 127 only require a single byte 0b0xxxxxxx.

// Each byte contributes 7 bits of data
const VARINT_ENCODING_BITS: u8 = 7;
// The upper bit indicates whether there are more bytes
const VARINT_CONTINUE_FLAG: u8 = 1 << VARINT_ENCODING_BITS;

// Read 7 bits of data and a flag indicating whether there are more
fn read_varint_byte<R: Read>(stream: &mut R) -> io::Result<(u8, bool)> {
  let [byte] = read_bytes(stream)?;
  let value = byte & !VARINT_CONTINUE_FLAG;
  let more_bytes = byte & VARINT_CONTINUE_FLAG != 0;
  Ok((value, more_bytes))
}

// Read a "size encoding" variable-length integer.
// (There's another slightly different variable-length format
// called the "offset encoding".)
fn read_size_encoding<R: Read>(stream: &mut R) -> io::Result<usize> {
  let mut value = 0;
  let mut length = 0; // the number of bits of data read so far
  loop {
    let (byte_value, more_bytes) = read_varint_byte(stream)?;
    // Add in the data bits
    value |= (byte_value as usize) << length;
    // Stop if this is the last byte
    if !more_bytes {
      return Ok(value)
    }

    length += VARINT_ENCODING_BITS;
  }
}

The object type and size are combined into a single variable-length integer. There upper 3 data bits of the first byte indicate the object type, and the rest of the bits form the size. For example, the bytes [0b1tttxxxx, 0b0yyyyyyy] would indicate a type of 0bttt and a size of 0byyyyyyyxxxx. So let's see what the value of this integer is for our packed object:

const PACK_FILE_SUFFIX: &str = ".pack";

fn read_pack_object(pack_file: &mut File, offset: u64) -> io::Result<()> {
  seek(pack_file, offset)?;
  let type_and_size = read_size_encoding(pack_file)?;
  println!("Type and size: {:b}", type_and_size);
  Ok(())
}

fn main() -> io::Result<()> {
  let args: Vec<_> = env::args().collect();
  let [_, pack, object] = <[String; 3]>::try_from(args).unwrap();
  let offset = get_pack_offset(&pack, Hash::from_str(&object).unwrap())?;
  let path = Path::new(PACKS_DIRECTORY).join(pack + PACK_FILE_SUFFIX);
  let mut file = File::open(path)?;
  read_pack_object(&mut file, offset.unwrap())
}

$ cargo run pack-d851c0ab72a0034ab858061940ed04abebe20d32 4d53e91c6b2c3f5b5c7375e579a453fc5053c08b
Type and size: 100010011010

Since the variable-length integer was read as 0byyyyyyytttxxxx, this means yyyyyyy is 0010001, ttt is 001, and xxxx is 1010. The type is therefore 1, meaning a commit, and the length is 0b00100011010 (282).

We can use a few bitwise operations to extract the type and length:

// The number of bits storing the object type
const TYPE_BITS: u8 = 3;
// The number of bits of the object size in the first byte.
// Each additional byte has VARINT_ENCODING_BITS of size.
const TYPE_BYTE_SIZE_BITS: u8 = VARINT_ENCODING_BITS - TYPE_BITS;

// Read the lower `bits` bits of `value`
fn keep_bits(value: usize, bits: u8) -> usize {
  value & ((1 << bits) - 1)
}

fn read_type_and_size<R: Read>(stream: &mut R) -> io::Result<(u8, usize)> {
  // Object type and uncompressed pack data size
  // are stored in a "size-encoding" variable-length integer.
  // Bits 4 through 6 store the type and the remaining bits store the size.
  let value = read_size_encoding(stream)?;
  let object_type = keep_bits(value >> TYPE_BYTE_SIZE_BITS, TYPE_BITS) as u8;
  let size = keep_bits(value, TYPE_BYTE_SIZE_BITS)
           | (value >> VARINT_ENCODING_BITS << TYPE_BYTE_SIZE_BITS);
  Ok((object_type, size))
}

Undeltified objects

We've already seen the object type 1 (for commit). The other allowed object types are 2 (tree), 3 (blob), 4 (tag), 6 (offset delta), and 7 (hash delta). We'll first handle the non-delta object types. Aside from their headers, their contents are stored as zlib-compressed data, just like in unpacked object files.

#[derive(Clone, Copy, Debug)]
enum ObjectType {
  Commit,
  Tree,
  Blob,
  Tag,
}

// A packed object can either store the object's contents directly,
// or as a "delta" from another object
enum PackObjectType {
  Base(ObjectType),
  OffsetDelta,
  HashDelta,
}

// An object, which may be read from a packfile or an unpacked file
#[derive(Debug)]
struct Object {
  object_type: ObjectType,
  contents: Vec<u8>,
}

// Shorthand for making an io::Error
fn make_error(message: &str) -> Error {
  Error::new(ErrorKind::Other, message)
}

fn read_pack_object(pack_file: &mut File, offset: u64) -> io::Result<Object> {
  use ObjectType::*;
  use PackObjectType::*;

  seek(pack_file, offset)?;
  let (object_type, size) = read_type_and_size(pack_file)?;
  let object_type = match object_type {
    1 => Base(Commit),
    2 => Base(Tree),
    3 => Base(Blob),
    4 => Base(Tag),
    6 => OffsetDelta,
    7 => HashDelta,
    _ => {
      return Err(make_error(&format!("Invalid object type: {}", object_type)))
    }
  };
  match object_type {
    Base(object_type) => {
      // The object contents are zlib-compressed
      let mut contents = Vec::with_capacity(size);
      ZlibDecoder::new(pack_file).read_to_end(&mut contents)?;
      if contents.len() != size {
        return Err(make_error("Incorrect object size"))
      }

      Ok(Object { object_type, contents })
    }
    OffsetDelta | HashDelta => unimplemented!(),
  }
}

fn unpack_object(pack: &str, offset: u64) -> io::Result<Object> {
  let path = Path::new(PACKS_DIRECTORY)
    .join(pack.to_string() + PACK_FILE_SUFFIX);
  let mut file = File::open(path)?;
  read_pack_object(&mut file, offset)
}

fn main() -> io::Result<()> {
  let args: Vec<_> = env::args().collect();
  let [_, pack, object] = <[String; 3]>::try_from(args).unwrap();
  let offset = get_pack_offset(&pack, Hash::from_str(&object).unwrap())?;
  let Object { object_type, contents } = unpack_object(pack, offset.unwrap())?;
  println!("Type: {:?}", object_type);
  println!("{}", String::from_utf8_lossy(&contents));
  Ok(())
}

Note that we use size to pre-allocate contents with the correct capacity. Storing the object's size in the packfile is redundant, since zlib streams already indicate where they end. But git frequently prefixes variable-length data with its size (we will see this again with delta objects). This is a performance tradeoff—it makes the packfile slightly larger in exchange for not having to grow the contents Vec or allocate excess capacity.

Finally, we can successfully read the contents of the HEAD commit from the packfile:

$ cargo run pack-d851c0ab72a0034ab858061940ed04abebe20d32 4d53e91c6b2c3f5b5c7375e579a453fc5053c08b
Type: Commit
tree 93bf6ec9945e4c490227048b31659adc2f953c16
parent fe319d5fe11b9ce068f5095782c9b5c3a69caeb3
author Junio C Hamano <gitster@pobox.com> 1636585191 -0800
committer Junio C Hamano <gitster@pobox.com> 1636585281 -0800

A few hotfixes

Signed-off-by: Junio C Hamano <gitster@pobox.com>

Deltified objects

So far, we've seen how to find an object in a packfile and read its compressed representation. However, we're still missing the main motivation for packfiles: being able to save space by storing one object in terms of another. This is where the "offset delta" and "hash delta" object types come in.

The idea of a "deltified" object is simple: the object is formed by combining chunks copied from a "base object" with new data. Ideally the two objects are very similar, in which case only a few large chunks need to be copied and little new data needs to be specified. The only difference between the offset delta and hash delta types is how the base object is specified: a hash delta uses the object's (20-byte) hash, whereas an offset delta specifies its position in the same packfile (using yet another variable-length int encoding). The offset representation is shorter and makes it easier to locate the base object, but doesn't allow for base objects outside the packfile.

We'll start by decoding the "offset" of an offset delta. It uses a variable-length integer, similar to the size encoding. However, the bytes are in the opposite order (from most to least significant). The encoding is also slightly more efficient because it avoids duplicate representations of the same value. For example, [0b0xxxxxxx] and [0b10000000, 0b0xxxxxxx] would otherwise both decode to 0bxxxxxxx since the additional 0 bits don't change the value. So, if there is a second byte, the offset encoding always adds 2⁷ to the value. If there is a third byte, 2⁷ + 2¹⁴ is added, and so on. This way, all 1-byte values are less than all 2-byte values, which are less than all 3-byte values, etc.

fn read_offset_encoding<R: Read>(stream: &mut R) -> io::Result<u64> {
  let mut value = 0;
  loop {
    let (byte_value, more_bytes) = read_varint_byte(stream)?;
    // Add the new bits at the *least* significant end of the value
    value = (value << VARINT_ENCODING_BITS) | byte_value as u64;
    if !more_bytes {
      return Ok(value)
    }

    // Increase the value if there are more bytes, to avoid redundant encodings
    value += 1;
  }
}

This offset is relative to the offset of the deltified object. For example, a value of 1234 means "go back 1234 bytes to read the base object".

Delta instructions

After the offset or hash of the base offset, both deltified representations contain a zlib-compressed stream. The stream starts with the size of the base object (redundant) and the size of the new object (useful for preallocating it). The rest of the compressed stream is a sequence of instructions for building the new object. There are two types of instructions:

Data(bytes): append the specified bytes to the new object
Copy(offset, size): copy the size bytes starting at offset in the base object and append them to the new object

The instructions are distinguished by the upper bit of their first byte: a data instruction starts with a 0 bit, while a copy instruction starts with a 1. In a data instruction, the remaining 7 bits indicate the number of data bytes that follow. A copy instruction is followed by an offset (up to 4 bytes) and a size (up to 3 bytes) to copy in the base object. The lower 7 bits in the instruction byte indicate which of these offset and size bytes are present. For example, consider this copy instruction:

[0b1_001_0101, 0bxxxxxxxx, 0byyyyyyyy, 0bzzzzzzzz]
                                       ^ size byte 0
                           ^ offset byte 2
               ^ offset byte 0
          ^ only bytes 0 and 2 of offset are provided
       ^ only byte 0 of size is provided
   ^ copy instruction

Offset: 0b00000000yyyyyyyy00000000xxxxxxxx
Size:           0b0000000000000000zzzzzzzz

Here's the (lengthy) implementation. Keep in mind that we are just repeatedly reading an enum DeltaInstruction { Data(Vec<u8>), Copy(usize, usize) } and executing it.

const COPY_INSTRUCTION_FLAG: u8 = 1 << 7;
const COPY_OFFSET_BYTES: u8 = 4;
const COPY_SIZE_BYTES: u8 = 3;
const COPY_ZERO_SIZE: usize = 0x10000;

// Read an integer of up to `bytes` bytes.
// `present_bytes` indicates which bytes are provided. The others are 0.
fn read_partial_int<R: Read>(
  stream: &mut R, bytes: u8, present_bytes: &mut u8
) -> io::Result<usize> {
  let mut value = 0;
  for byte_index in 0..bytes {
    // Use one bit of `present_bytes` to determine if the byte exists
    if *present_bytes & 1 != 0 {
      let [byte] = read_bytes(stream)?;
      value |= (byte as usize) << (byte_index * 8);
    }
    *present_bytes >>= 1;
  }
  Ok(value)
}

// Reads a single delta instruction from a stream
// and appends the relevant bytes to `result`.
// Returns whether the delta stream still had instructions.
fn apply_delta_instruction<R: Read>(
  stream: &mut R, base: &[u8], result: &mut Vec<u8>
) -> io::Result<bool> {
  // Check if the stream has ended, meaning the new object is done
  let instruction = match read_bytes(stream) {
    Ok([instruction]) => instruction,
    Err(err) if err.kind() == ErrorKind::UnexpectedEof => return Ok(false),
    Err(err) => return Err(err),
  };
  if instruction & COPY_INSTRUCTION_FLAG == 0 {
    // Data instruction; the instruction byte specifies the number of data bytes
    if instruction == 0 {
      // Appending 0 bytes doesn't make sense, so git disallows it
      return Err(make_error("Invalid data instruction"))
    }

    // Append the provided bytes
    let mut data = vec![0; instruction as usize];
    stream.read_exact(&mut data)?;
    result.extend_from_slice(&data);
  }
  else {
    // Copy instruction
    let mut nonzero_bytes = instruction;
    let offset =
      read_partial_int(stream, COPY_OFFSET_BYTES, &mut nonzero_bytes)?;
    let mut size =
      read_partial_int(stream, COPY_SIZE_BYTES, &mut nonzero_bytes)?;
    if size == 0 {
      // Copying 0 bytes doesn't make sense, so git assumes a different size
      size = COPY_ZERO_SIZE;
    }
    // Copy bytes from the base object
    let base_data = base.get(offset..(offset + size)).ok_or_else(|| {
      make_error("Invalid copy instruction")
    })?;
    result.extend_from_slice(base_data);
  }
  Ok(true)
}

fn apply_delta(pack_file: &mut File, base: &Object) -> io::Result<Object> {
  let Object { object_type, contents: ref base } = *base;
  let mut delta = ZlibDecoder::new(pack_file);
  let base_size = read_size_encoding(&mut delta)?;
  if base.len() != base_size {
    return Err(make_error("Incorrect base object length"))
  }

  let result_size = read_size_encoding(&mut delta)?;
  let mut result = Vec::with_capacity(result_size);
  while apply_delta_instruction(&mut delta, base, &mut result)? {}
  if result.len() != result_size {
    return Err(make_error("Incorrect object length"))
  }

  // The object type is the same as the base object
  Ok(Object { object_type, contents: result })
}

The delta format seems unnecessarily complex to me. Why does it need 3 different variable-length integer representations?!

If we ignore the details though, we can see that a delta is really a generalization of a diff. In fact, git often uses previous versions of blob and tree objects as base objects for the next versions' deltas, just like git diff would do. Instead of comparing on a line-by-line basis, though, the delta works with individual bytes. The chunks copied from the base object also do not need to be in the same order they were in. But the benefits are exactly same: when the changes are small, storing a diff reduces the amount of duplicated data. So packfiles really do give git the best of both worlds: storing blobs for every file at every commit makes git checkout very fast, but storing them as deltas in packfiles keeps them from taking up excessive space.

Reading an object (for real this time)

We can now fill in the remaining cases in read_pack_object():

fn read_pack_object(pack_file: &mut File, offset: u64) -> io::Result<Object> {
  // ...

  match object_type {
    Base(object_type) => /* ... */,
    OffsetDelta => {
      let delta_offset = read_offset_encoding(pack_file)?;
      let base_offset = offset.checked_sub(delta_offset).ok_or_else(|| {
        make_error("Invalid OffsetDelta offset")
      })?;
      // Save and restore the offset since read_pack_offset() will change it
      let offset = get_offset(pack_file)?;
      let base_object = read_pack_object(pack_file, base_offset)?;
      seek(pack_file, offset)?;
      apply_delta(pack_file, &base_object)
    }
    HashDelta => {
      let hash = read_hash(pack_file)?;
      let base_object = read_object(hash)?; // to implement shortly
      apply_delta(pack_file, &base_object)
    }
  }
}

And now we can successfully read HEAD's tree object:

93bf6ec9945e4c490227048b31659adc2f953c16 is an offset delta (delta size 5417) from
cc13e418d3294ff306b8a111f08db5ee645d993c is an offset delta (delta size 6311) from
42bee03862795ea50d80bcb25ec564e2b880fd2e is undeltified (size 18464)

You can see that we had to compute 2 prior versions of the tree object, but overall we achieve a tradeoff between computing too many deltas and storing too many near-duplicate objects. (Each delta skips many commits and is only about 1/3 the size of the original object.)

Finally, we can find an object regardless of whether it's packed or unpacked. We first look where the object would be in the objects directory if it were unpacked. If it's not there, we have to try each packfile, using the index file to tell us whether the object is in the pack.

use std::fs;

const COMMIT_OBJECT_TYPE: &[u8] = b"commit";
const TREE_OBJECT_TYPE: &[u8] = b"tree";
const BLOB_OBJECT_TYPE: &[u8] = b"blob";
const TAG_OBJECT_TYPE: &[u8] = b"tag";

impl Object {
  // Compute the hash that an object would have, given its type and contents
  fn hash(&self) -> Hash {
    use ObjectType::*;

    let hash = Sha1::new()
      .chain(match self.object_type {
        Commit => COMMIT_OBJECT_TYPE,
        Tree => TREE_OBJECT_TYPE,
        Blob => BLOB_OBJECT_TYPE,
        Tag => TAG_OBJECT_TYPE,
      })
      .chain(b" ")
      .chain(self.contents.len().to_string())
      .chain(b"\0")
      .chain(&self.contents)
      .finalize();
    Hash(<[u8; HASH_BYTES]>::try_from(hash.as_slice()).unwrap())
  }
}

// Remove the `.idx` suffix from an index filename.
// Returns None if not an index file.
fn strip_index_file_name(file_name: &OsStr) -> Option<&str> {
  let file_name = file_name.to_str()?;
  file_name.strip_suffix(INDEX_FILE_SUFFIX)
}

// Read a packed object from the packs directory
fn read_packed_object(hash: Hash) -> io::Result<Object> {
  // Try every file in the packs directory
  for pack_or_index in fs::read_dir(PACKS_DIRECTORY)? {
    let pack_or_index = pack_or_index?;
    let file_name = pack_or_index.file_name();
    // Skip any non-index files
    let pack = match strip_index_file_name(&file_name) {
      Some(pack) => pack,
      _ => continue,
    };

    // Skip the pack if the object is not in the index
    let pack_offset = get_pack_offset(pack, hash)?;
    let pack_offset = match pack_offset {
      Some(pack_offset) => pack_offset,
      _ => continue,
    };

    // If the object is found in the index, read it from the pack
    return unpack_object(pack, pack_offset)
  }
  Err(make_error(&format!("Object {} not found", hash)))
}

// Read an unpacked object from the objects directory
fn read_unpacked_object(hash: Hash) -> io::Result<Object> {
  // Modified from read_object() and check_header() in the last post
  // ...
}

// Read an object when we don't know if it's packed or unpacked
fn read_object(hash: Hash) -> io::Result<Object> {
  let object = match read_unpacked_object(hash) {
    Ok(object) => object,
    Err(err) if err.kind() == ErrorKind::NotFound => {
      read_packed_object(hash)?
    }
    err => return err,
  };

  // Verify that the object has the SHA-1 hash we expected
  let object_hash = object.hash();
  if object_hash != hash {
    return Err(make_error(
      &format!("Object {} has wrong hash {}", hash, object_hash)
    ))
  }

  Ok(object)
}

fn main() -> io::Result<()> {
  let args: Vec<_> = env::args().collect();
  let [_, hash] = <[String; 2]>::try_from(args).unwrap();
  let hash = Hash::from_str(&hash)?;
  let Object { object_type, contents } = read_object(hash)?;
  println!("Object type: {:?}", object_type);
  println!("{}", String::from_utf8_lossy(&contents));
  Ok(())
}

That's the full story of how git stores its objects! New object files start out unpacked in .git/objects. If you push or pull new objects, they are sent in a packfile. Received packfiles are saved in .git/objects/pack. And git may occasionally decide the objects directory has gotten too big and combine the objects into a packfile.

You may have noticed that the loop over all possible packfiles can be slow if there are a large number of packfiles. For this reason, git may choose to combine small packfiles into a single one. Newer versions of git also support a "multi-pack-index" file (documentation) so only a single index file needs to be consulted to find a packed object in any packfile. But git still seems to default to individual pack indices.

Up next...

So far, we've inspected how git stores the state of a repository locally. We've seen in gory detail how the HEAD file, refs directory, and objects directory represent the branches, commits, trees, and blobs that make up a repository.

In the next (maybe last) post of the series, we'll switch focus to how git transfers the state of a repository to and from a remote repository. We'll look specifically at the SSH "transport", the special protocol used to perform a git push or git pull (really, git fetch) over SSH. Along the way, we'll answer questions like:

How does git know what branches are available to pull?
How does git send repository state and only send what changed? (Spoiler alert: objects and packfiles play a central role.)
Where do the messages like "Enumerating objects: 176, done." come from?

I think this is the most interesting part of git's implementation; hopefully you will enjoy it too!

Git Internals part 1: The git object model

Caleb Sander — Sat, 30 Oct 2021 21:30:33 +0000

This is the first of several posts exploring how git works under the hood. While lots of programmers are familiar with using git, I wanted to do a deep dive into how git is implemented. git employs many clever ideas to optimize common version control operations.

I'm a big fan of trying to understand software by playing around with it rather than reading lots of documentation. To that end, I've written these posts as summaries of reverse-engineering git. The official documentation relevant to this post can be found at https://git-scm.com/book/en/v2/Git-Internals-Git-Objects.

The source code for this post can be found here. I've written it in Rust, but you can find git implementations in lots of other languages. The canonical git is written in C.

git refresher

This series isn't meant as an introduction to git. There are lots of good explanations online of how to use git, such as the Pro Git book. But I do want to review a few of the core git concepts, since they are important to understanding how git works.

Version control

git is one of many examples of "version control software", although it is currently the most popular by far. Although VCS implementations differ in their details, they have many of the same core ideas. The purpose of version control is to store not just the current state of a set of files, but the history of how those files changed over time. This history can be browsed, updated, and shared, which makes version control a very useful tool in applications where edit histories matter, especially software development.

Commits

git stores its history as a collection of snapshots, called "commits". You can browse the state of the files at any commit; this operation is called "checking out" the commit. You can think of commits as a series of backups of your code, although we will see later that git has several tricks to reduce the storage space needed for all these backups.

Each commit builds on earlier commits, which are called its "parent" commits. In the simplest case, the commit history is "linear", where each commit has a single parent and child (except for the first and last commits). For example, there could be three commits made in order, A, B, and C. We would visualize this with a commit diagram:

A --- B --- C

However, even on small projects, commit histories are rarely perfectly linear. git allows commit histories to "branch", where multiple commits build on top of the same parent commit. This is useful, for example, when developers are working on features in parallel and don't want to affect each other's code until their features are finalized. This can lead to a commit diagram like the following:

A --- B --- C --- D
        \
         E --- F --- G

Commit histories can also "merge", where one commit combines multiple parent commits. In the example above, commit G might be merged into D, producing a new commit H.

A --- B --- C --- D --- H
        \             /
         E --- F --- G

Branches and tags

Every commit is assigned an ID, called a "commit hash" (we will see where this hash comes from). Although we can refer to any commit by its hash, it is often convenient to name commits. Branches and tags are the two methods to do this. Both act as references to commits. The difference is that committing on top of a branch updates the branch to refer to the new commit, whereas tags always point to the same commit. It is conventional to use the main branch to point to the latest production-ready commit and feature/xyz, fix/xyz, etc. to track progress on adding a feature or fixing a bug. Tags are mainly used to mark commits corresponding to particular release versions.

A sample git repository

We'll use the directory structure created by cargo init to create a new repository with a single commit:

$ cargo init
$ git add . # track all the newly created files with git
$ git commit -am 'Initial commit'
[main (root-commit) af64eba] Initial commit
 4 files changed, 19 insertions(+)
 create mode 100644 .gitignore
 create mode 100644 Cargo.lock
 create mode 100644 Cargo.toml
 create mode 100644 src/main.rs

git tells us that a new commit was created. It refers to the commit as af64eba; we'll see later where this hexadecimal string comes from and how it gets used.

Where am I?

Almost all git commands need to know what commit is currently checked out. For example, git commit needs to know the current commit since it will become the parent of the new commit. In our toy repository, we are at commit af64eba. How does git know that?

You may know that HEAD can be used to refer to the current commit. For example, git show HEAD shows the commit message of the current commit and the changes it introduced. All of the git state is stored in the .git directory, and this includes the file which tells us where we currently are: .git/HEAD. Let's look at its contents.

(Note: these examples use synchronous I/O in order to focus on the git internals. There are ample opportunities to perform the filesystem operations in parallel, so using asynchronous I/O could significantly improve performance.)

use std::fs;
use std::io;

const HEAD_FILE: &str = ".git/HEAD";

fn get_head() -> io::Result<String> {
  fs::read_to_string(HEAD_FILE)
}

fn main() -> io::Result<()> {
  let head = get_head()?;
  println!("Head file: {:?}", head);
  Ok(())
}

Running this program, we get the following output:

Head file: "ref: refs/heads/main\n"

The .git/HEAD file is telling us that we have the main branch checked out. That's part of what we wanted to know, but we still haven't figured out how git knows what commit main refers to. It turns out that refs/heads/main is actually the name of a file under the .git directory. Let's read it:

use std::path::Path;

const BRANCH_REFS_DIRECTORY: &str = ".git/refs/heads";

fn get_branch_head(branch: &str) -> io::Result<String> {
  let ref_file = Path::new(BRANCH_REFS_DIRECTORY).join(branch);
  fs::read_to_string(ref_file)
}

fn main() -> io::Result<()> {
  let main_head = get_branch_head("main")?;
  println!("main: {:?}", main_head);
  Ok(())
}

We see:

main: "af64eba00e3cfccc058403c4a110bb49b938af2f\n"

If you remember, the commit we created was referred to as af64eba, and it's no coincidence that .git/refs/heads/main starts with those hexadecimal digits. This full string of 40 hexadecimal digits (representing 20 bytes) is called a "commit hash". We'll see how it's computed soon (and why it's called a "hash"), but for now you can think of it as a unique identifier for the commit.

It's also possible (although less common) to check out a specific commit, rather than a branch. For example, we can run git checkout af64eba to check out the current commit:

Note: switching to 'af64eba'.

You are in 'detached HEAD' state. You can look around, make experimental
changes and commit them, and you can discard any commits you make in this
state without impacting any branches by switching back to a branch.

If you want to create a new branch to retain commits you create, you may
do so (now or later) by using -c with the switch command. Example:

  git switch -c <new-branch-name>

Or undo this operation with:

  git switch -

Turn off this advice by setting config variable advice.detachedHead to false

HEAD is now at af64eba Initial commit

In this case, the .git/HEAD file specifies the commit hash directly:

Head file: "af64eba00e3cfccc058403c4a110bb49b938af2f\n"

Implementing HEAD lookup

Now that we know how .git/HEAD and the files under .git/refs/heads work together, let's define some types:

const HASH_BYTES: usize = 20;

// A (commit) hash is a 20-byte identifier.
// We will see that git also gives hashes to other things.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Hash([u8; HASH_BYTES]);

// The head is either at a specific commit or a named branch
enum Head {
  Commit(Hash),
  Branch(String),
}

Next, we will want to be able to convert hashes back and forth between the 40-character hexadecimal representation and the compact 20-byte representation. I'll omit the implementation details, but you can find them in the source code for this post.

use std::fmt::{self, Display, Formatter};
use std::io::Error;
use std::str::FromStr;

impl FromStr for Hash {
  type Err = Error;

  fn from_str(hex_hash: &str) -> io::Result<Self> {
    // Parse a hexadecimal string like "af64eba00e3cfccc058403c4a110bb49b938af2f"
    // into  [0xaf, 0x64, ..., 0x2f]. Returns an error if the string is invalid.

    // ...
  }
}

impl Display for Hash {
  fn fmt(&self, f: &mut Formatter) -> fmt::Result {
    // Turn the hash back into a hexadecimal string
    for byte in self.0 {
      write!(f, "{:02x}", byte)?;
    }
    Ok(())
  }
}

Now we can write the core logic: reading the .git/HEAD file and determining what commit hash it corresponds to:

fn get_head() -> io::Result<Head> {
  use Head::*;

  let hash_contents = fs::read_to_string(HEAD_FILE)?;
  // Remove trailing newline
  let hash_contents = hash_contents.trim_end();
  // If .git/HEAD starts with `ref: refs/heads/`, it's a branch name.
  // Otherwise, it should be a commit hash.
  Ok(match hash_contents.strip_prefix(REF_PREFIX) {
    Some(branch) => Branch(branch.to_string()),
    _ => {
      let hash = Hash::from_str(hash_contents)?;
      Commit(hash)
    }
  })
}

impl Head {
  fn get_hash(&self) -> io::Result<Hash> {
    use Head::*;

    match self {
      Commit(hash) => Ok(*hash),
      Branch(branch) => {
        // Copied from get_branch_head()
        let ref_file = Path::new(BRANCH_REFS_DIRECTORY).join(branch);
        let hash_contents = fs::read_to_string(ref_file)?;
        Hash::from_str(hash_contents.trim_end())
      }
    }
  }
}

fn main() -> io::Result<()> {
  let head = get_head()?;
  let head_hash = head.get_hash()?;
  println!("Head hash: {}", head_hash);
  Ok(())
}

Now, whether we check out the main branch or the commit hash directly, this will print:

Head hash: af64eba00e3cfccc058403c4a110bb49b938af2f

We've successfully identified the hash of the current commit! Now, how do we figure out what information that commit stores?

What's in a commit?

When you look at a commit in a web interface like GitHub or through a command like git show, you'll see the changes ("diff") introduced by the commit. So you might assume that git stores each commit as a diff.

Alternatively, it would be possible to store each commit like a backup, with the contents of every file at that commit.

Either of these approaches could work: you can compute a diff from two copies of files, and you can compute the contents of files by applying every diff in order (starting either with the empty repository or from a recent commit). Which one to use depends on what you are trying to optimize. The diff-based approach will take up less storage space; it minimizes the amount of repeated information, since it only stores what changed. However, storing contents makes it much faster to check out the code at a particular commit, since we don't have to apply potentially thousands of diffs. (It also makes it easy to implement git clone --depth 1, which speeds up clone by only downloading the most recent commit.) And it's not too time-consuming to compute diffs from two commits' contents if there are few changes: diffing algorithms are pretty fast, and git can automatically skip directories/files that haven't changed, as we'll see later.

For these reasons, git has gone with the "storing the contents of every file" approach. git's implementation manages to only store one copy of identical files, which saves a lot of storage space over the naive solution.

Where are the commits?

A commit is one of several things ("objects") that git stores the same way. Every object is uniquely identified by a hash. So, in order to read a commit, we need to first read a generic object, and then interpret it as a commit.

You might not be surprised to learn that objects are stored in yet another .git subdirectory, .git/objects. Here is what its structure looks like:

$ ls -R .git/objects
30   7a   82   a0   af   e7   ea   ed   info pack

.git/objects/30:
5157a396c6858705a9cb625bab219053264ee4

.git/objects/7a:
a5ac9dda7449f167dc03cc3dfb50529d2315f8

.git/objects/82:
50b5cb3a8980fd6d6ad1a29691bbb785080a90

.git/objects/a0:
4ab3c3aee930a929339c5014186cfdd64c8d84

.git/objects/af:
64eba00e3cfccc058403c4a110bb49b938af2f

.git/objects/e7:
a11a969c037e00a796aafeff6258501ec15e9a

.git/objects/ea:
8c4bf7f35f6f77f75d92ad8ce8349f6e81ddba

.git/objects/ed:
9fcacf599c2aaefd46b9c2867339727d2339c3

.git/objects/info:

.git/objects/pack:

We'll learn about the pack directory in the next post; for now, let's focus on the directories with hexadecimal names. If you look at the filename .git/objects/af/64eba00e3cfccc058403c4a110bb49b938af2f, you may be able to guess where it comes from. There are 2 hexadecimal digits in the directory name and 38 in the filename. Together, they make up a single 40-digit hash. In this case, it's our commit hash af64eba00e3cfccc058403c4a110bb49b938af2f!

In general, there are up to 256 object directories (00 through ff) and each one contains all the objects whose hashes start with those 2 digits. I'm not sure why git does this rather than store all objects in a single directory. (Perhaps it's to reduce the number of files in each directory, since some platforms place limit directory sizes. It may also make it faster to find an object file if the OS loops linearly through the entries in each directory, although modern file systems use sorted trees for faster lookup.)

So we've found where our commit object is stored. Now, what's inside it? If we inspect the bytes, the file doesn't seem to contain any readable text:

$ xxd -g1 .git/objects/af/64eba00e3cfccc058403c4a110bb49b938af2f
00000000: 78 01 9d 8d 41 0a 02 31 0c 45 5d f7 14 b9 80 43  x...A..1.E]....C
00000010: 62 6a a7 05 11 c1 95 6b 4f 90 49 ab 16 da 19 18  bj.....kO.I.....
00000020: eb fd ad 7a 03 97 ef c1 7f 5f 97 5a 73 03 f2 61  ...z....._.Zs..a
00000030: d3 d6 94 40 d0 ca c4 ca 92 52 60 94 b0 0b cc 41  ...@.....R`....A
00000040: f7 48 96 bc d3 5b 8c ce aa 8f de 1a 79 b5 c7 b2  .H...[......y...
00000050: c2 59 4a 9a e0 2a 73 4c 2b 1c f4 43 c3 f3 4b a7  .YJ..*sL+..C..K.
00000060: 7b 95 5c 06 5d ea 11 c8 31 13 8d e4 10 b6 38 22  {.\.]...1.....8"
00000070: 9a 6e fb 6d eb 9b 3f 03 e6 32 e7 96 a5 c0 af 64  .n.m..?..2.....d
00000080: de 12 79 3d 46                                   ..y=F

So it's probably in a binary format. We can use the file command to guess what format this is:

$ file .git/objects/af/64eba00e3cfccc058403c4a110bb49b938af2f
.git/objects/af/64eba00e3cfccc058403c4a110bb49b938af2f: zlib compressed data

Ah, so it's a compressed file!

Let's add a library to read these compressed files. We'll use the Rust library flate2, which includes the functionality we need plus much more.

$ cargo add flate2 # using cargo-edit

Now we can write a short script to print the decompressed contents of this object:

use std::fs::File;
use std::io::Read;
use flate2::read::ZlibDecoder;

const OBJECTS_DIRECTORY: &str = ".git/objects";

// Read the byte contents of an object
fn read_object(hash: Hash) -> io::Result<Vec<u8>> {
  // The first 2 characters of the hexadecimal hash form the directory;
  // the rest forms the filename
  let hex_hash = hash.to_string();
  let (directory_name, file_name) = hex_hash.split_at(2);
  let object_file = Path::new(OBJECTS_DIRECTORY)
    .join(directory_name)
    .join(file_name);
  let object_file = File::open(object_file)?;
  let mut contents = vec![];
  ZlibDecoder::new(object_file).read_to_end(&mut contents)?;
  Ok(contents)
}

fn main() -> io::Result<()> {
  let head = get_head()?;
  let head_hash = head.get_hash()?;
  let head_contents = read_object(head_hash)?;
  // Spoiler alert: the commit object is a text file, so print it as a string
  let head_contents = String::from_utf8(head_contents).unwrap();
  println!("Object {} contents:", head_hash);
  println!("{:?}", head_contents);
  Ok(())
}

This prints:

Object af64eba00e3cfccc058403c4a110bb49b938af2f contents:
"commit 189\u{0}tree a04ab3c3aee930a929339c5014186cfdd64c8d84\nauthor Caleb Sander <caleb.sander@gmail.com> 1633117160 -0700\ncommitter Caleb Sander <caleb.sander@gmail.com> 1633117160 -0700\n\nInitial commit\n"

So finally, we can see the author, committer, and commit message ("Initial commit") of the commit! Commit objects start with a header like "commit 189\u{0}". 189 indicates that there are 189 bytes in the body of the commit (after the header).

This commit is special, since it's the first commit, but generally each commit will also have a parent commit (or multiple, for merge commits). We can see that if we add another commit and re-run the script:

$ git add Cargo.toml Cargo.lock
$ git commit -m 'Add flate2 dependency'
[main b1ffae7] Add flate2 dependency
 2 files changed, 59 insertions(+)
$ cargo run
Object b1ffae7cd17860fc6688bfcabbfe0d75301a7d46 contents:
"commit 244\u{0}tree b195f77cbea5fc36ddbee3b739ce5a924893b72f\nparent af64eba00e3cfccc058403c4a110bb49b938af2f\nauthor Caleb Sander <caleb.sander@gmail.com> 1633801460 -0700\ncommitter Caleb Sander <caleb.sander@gmail.com> 1633801460 -0700\n\nAdd flate2 dependency\n"

Note the additional parent line in the output, with a hash referring to our previous commit.

Finally, we can parse the commit object into a Commit type. For simplicity, we will skip parsing the author and committer lines into (name, email, timestamp, timezone).

const COMMIT_HEADER: &[u8] = b"commit ";
const TREE_LINE_PREFIX: &[u8] = b"tree ";
const PARENT_LINE_PREFIX: &[u8] = b"parent ";
const AUTHOR_LINE_PREFIX: &[u8] = b"author ";
const COMMITTER_LINE_PREFIX: &[u8] = b"committer ";

// Some helper functions for parsing objects

fn decimal_char_value(decimal_char: u8) -> Option<u8> {
  match decimal_char {
    b'0'..=b'9' => Some(decimal_char - b'0'),
    _ => None,
  }
}

// Parses a decimal string, e.g. "123", into its value, e.g. 123.
// Returns None if any characters are invalid or the value overflows a usize.
fn parse_decimal(decimal_str: &[u8]) -> Option<usize> {
  let mut value = 0usize;
  for &decimal_char in decimal_str {
    let char_value = decimal_char_value(decimal_char)?;
    value = value.checked_mul(10)?;
    value = value.checked_add(char_value as usize)?;
  }
  Some(value)
}

// Like str::split_once(), split the slice at the next delimiter
fn split_once<T: PartialEq>(slice: &[T], delimiter: T) -> Option<(&[T], &[T])> {
  let index = slice.iter().position(|element| *element == delimiter)?;
  Some((&slice[..index], &slice[index + 1..]))
}

// Checks that an object's header has the expected type, e.g. "commit ",
// and the object size is correct
fn check_header<'a>(object: &'a [u8], header: &[u8]) -> Option<&'a [u8]> {
  let object = object.strip_prefix(header)?;
  let (size, object) = split_once(object, b'\0')?;
  let size = parse_decimal(size)?;
  if object.len() != size {
    return None
  }

  Some(object)
}

#[derive(Debug)]
struct Commit {
  tree: Hash,
  parents: Vec<Hash>,
  author: String, // name, email, and timestamp (not parsed)
  committer: String, // same contents as `author`
  message: String, // includes commit description
}

fn parse_commit(object: &[u8]) -> Option<Commit> {
  let object = check_header(object, COMMIT_HEADER)?;

  let object = object.strip_prefix(TREE_LINE_PREFIX)?;
  let (tree, mut object) = split_once(object, b'\n')?;
  let tree = hex_to_hash(tree)?;

  let mut parents = vec![];
  while let Some(object_rest) = object.strip_prefix(PARENT_LINE_PREFIX) {
    let (parent, object_rest) = split_once(object_rest, b'\n')?;
    let parent = hex_to_hash(parent)?;
    parents.push(parent);
    object = object_rest;
  }

  let object = object.strip_prefix(AUTHOR_LINE_PREFIX)?;
  let (author, object) = split_once(object, b'\n')?;
  let author = String::from_utf8(author.to_vec()).ok()?;

  let object = object.strip_prefix(COMMITTER_LINE_PREFIX)?;
  let (committer, object) = split_once(object, b'\n')?;
  let committer = String::from_utf8(committer.to_vec()).ok()?;

  let object = object.strip_prefix(b"\n")?;
  let message = String::from_utf8(object.to_vec()).ok()?;

  Some(Commit { tree, parents, author, committer, message })
}

fn read_commit(hash: Hash) -> io::Result<Commit> {
  let object = read_object(hash)?;
  parse_commit(&object).ok_or_else(|| {
    Error::new(ErrorKind::Other, format!("Malformed commit object: {}", hash))
  })
}

fn main() -> io::Result<()> {
  let head = get_head()?;
  let head_hash = head.get_hash()?;
  let commit = read_commit(head_hash)?;
  println!("Commit {}:", head_hash);
  println!("{:x?}", commit);
  Ok(())
}

Here's what our commit looks like:

Commit b1ffae7cd17860fc6688bfcabbfe0d75301a7d46:
Commit { tree: Hash([b1, 95, f7, 7c, be, a5, fc, 36, dd, be, e3, b7, 39, ce, 5a, 92, 48, 93, b7, 2f]), parents: [Hash([af, 64, eb, a0, e, 3c, fc, cc, 5, 84, 3, c4, a1, 10, bb, 49, b9, 38, af, 2f])], author: "Caleb Sander <caleb.sander@gmail.com> 1633801460 -0700", committer: "Caleb Sander <caleb.sander@gmail.com> 1633801460 -0700", message: "Add flate2 dependency\n" }

How do we check out the files at a commit?

Most of the fields in a commit object should make sense to a git user:

parent is the commit (or commits) that this commit builds on top of
author is the person credited for the commit contents, along with the time when they authored the commit
committer is the person who actually made the commit (often the same as author)
message is the combined commit message and description

But what does the tree hash mean?

Since each hash refers to an object, let's inspect the object referenced by the tree hash:

use std::fs;

fn main() -> io::Result<()> {
  let head = get_head()?;
  let head_hash = head.get_hash()?;
  let commit = read_commit(head_hash)?;
  let tree_contents = read_object(commit.tree)?;
  fs::write("tree", tree_contents)
}

Running this program creates a file called "tree" with the decompressed contents of the tree object. Unfortunately, unlike commit objects, this object stores a mix of text and binary information. We can use xxd to see both the byte values and the text characters:

$ xxd -g1 tree
00000000: 74 72 65 65 20 31 34 34 00 31 30 30 36 34 34 20  tree 144.100644
00000010: 2e 67 69 74 69 67 6e 6f 72 65 00 ea 8c 4b f7 f3  .gitignore...K..
00000020: 5f 6f 77 f7 5d 92 ad 8c e8 34 9f 6e 81 dd ba 31  _ow.]....4.n...1
00000030: 30 30 36 34 34 20 43 61 72 67 6f 2e 6c 6f 63 6b  00644 Cargo.lock
00000040: 00 85 a3 d4 da 06 7e 56 92 4f 41 99 ae 37 f2 d1  ......~V.OA..7..
00000050: a2 f0 82 2c b8 31 30 30 36 34 34 20 43 61 72 67  ...,.100644 Carg
00000060: 6f 2e 74 6f 6d 6c 00 47 82 47 98 37 bf 5a f0 bf  o.toml.G.G.7.Z..
00000070: 9b 80 92 91 14 3a ce 2f e4 a8 c3 34 30 30 30 30  .....:./...40000
00000080: 20 73 72 63 00 30 51 57 a3 96 c6 85 87 05 a9 cb   src.0QW........
00000090: 62 5b ab 21 90 53 26 4e e4                       b[.!.S&N.

The header should look familiar. In this case, the type of the object is tree instead of commit and the size in bytes is 144.

After the header, there's a number (100644), followed by a space, and then a filename (.gitignore), followed by a 0 byte. The next 20 bytes don't look like readable text. Then the pattern repeats for Cargo.lock, Cargo.toml, and src.

You may notice that 100644 is used for all the filenames that are files (.gitignore, Cargo.lock, and Cargo.toml), whereas 40000 is used for the directory src. This is a good approximation, although there are other numbers (called "modes") corresponding to executable files, symbolic links, and git submodules.

You might guess that each of these sequences of 20 bytes represents a hash. (Who knows why tree objects store hashes as bytes while commit objects store them as hexadecimal strings.)

We can parse tree objects using the helper functions we developed for commits:

use std::str;

const TREE_HEADER: &[u8] = b"tree ";

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Mode {
  Directory,
  File,
  // We'll ignore other modes for now
}

#[derive(Debug)]
struct TreeEntry {
  mode: Mode,
  name: String,
  hash: Hash,
}

#[derive(Debug)]
struct Tree(Vec<TreeEntry>);

fn parse_tree(object: &[u8]) -> Option<Tree> {
  let mut object = check_header(object, TREE_HEADER)?;
  let mut entries = vec![];
  while !object.is_empty() {
    let (mode, object_rest) = split_once(object, b' ')?;
    let mode = match mode {
      b"40000" => Mode::Directory,
      b"100644" => Mode::File,
      _ => return None,
    };

    let (name, object_rest) = split_once(object_rest, b'\0')?;
    let name = String::from_utf8(name.to_vec()).ok()?;

    let hash = object_rest.get(..HASH_BYTES)?;
    let hash = Hash(*<&[u8; HASH_BYTES]>::try_from(hash).unwrap());
    object = &object_rest[HASH_BYTES..];

    entries.push(TreeEntry { mode, name, hash });
  }
  Some(Tree(entries))
}

fn read_tree(hash: Hash) -> io::Result<Tree> {
  let object = read_object(hash)?;
  parse_tree(&object).ok_or_else(|| {
    Error::new(ErrorKind::Other, format!("Malformed tree object: {}", hash))
  })
}

We've glossed over the meaning of the hash in each tree entry. It turns out that it refers to a different type of object depending on the mode of the entry. If the entry is a directory, then it contains files and directories of its own, forming a subtree. So it should make sense that the hash of a directory entry refers to another tree object. However, if an entry is a file, then the hash instead needs to give us the contents of the file. This is accomplished with one more type of object, the "blob". (And if the entry is a git submodule, referring to another git repository, then the hash refers to the checked-out commit object in that other repository.)

Thankfully, blob objects are the simplest of all. They just contain a header, followed by the raw contents of a file.

Let's parse them:

const BLOB_HEADER: &[u8] = b"blob ";

struct Blob(Vec<u8>);

fn read_blob(hash: Hash) -> io::Result<Blob> {
  let object = read_object(hash)?;
  let bytes = check_header(&object, BLOB_HEADER).ok_or_else(|| {
    Error::new(ErrorKind::Other, format!("Malformed blob object: {}", hash))
  })?;
  Ok(Blob(bytes.to_vec()))
}

Armed with an understanding of the HEAD file, ref files, commit objects, tree objects, and blob objects, we can finally view the contents of a file (say, src/main.rs) at the current commit:

fn get_file_blob(tree: Hash, path: &str) -> io::Result<Blob> {
  let mut hash = tree;
  for name in path.split('/') {
    let tree = read_tree(hash)?;
    let entry = tree.0.iter().find(|entry| entry.name == name).ok_or_else(|| {
      Error::new(ErrorKind::Other, format!("No such entry: {}", name))
    })?;
    hash = entry.hash;
  }
  read_blob(hash)
}

fn main() -> io::Result<()> {
  let head = get_head()?;
  let head_hash = head.get_hash()?;
  let commit = read_commit(head_hash)?;
  let blob = get_file_blob(commit.tree, "src/main.rs")?;
  print!("{}", String::from_utf8(blob.0).unwrap()); // assume a text file
  Ok(())
}

This prints out the contents of src/main.rs that cargo init created:

fn main() {
    println!("Hello, world!");
}

What is a hash?

So far, we've been treating hashes simply as object IDs. They look like random values, 20 bytes or 40 hexadecimal characters long. But there is actually a precise way that a hash is computed which explains why it's called a "hash".

If you're unfamiliar with hash functions (e.g. MD5, SHA-1, SHA-256), the idea is that they are functions that take inputs (typically expressed as an an array of bytes) and compute fixed-size outputs (called "hashes"). For example, MD5 computes a 128-bit hash, SHA-1 computes a 160-bit hash, and SHA-256 computes a 256-bit hash. What's important is that these functions are "deterministic" (passing in the same input always results in the same hash), yet "chaotic" (passing in slightly different inputs results in completely different hashes). For this reason, hashes are sometimes called "signatures" or "fingerprints": they give each input a consistent and (almost) unique label.

Since git's hashes are 20 bytes long, or 160 bits, you might have guessed that they are SHA-1 hashes. So what input does an object's hash correspond to? Well, the only natural thing to take the hash of when determining an object's hash is the contents of the object itself. So this is exactly what git does.

We can check that each object we read has a correct hash. First, we will need the sha-1 crate to compute SHA-1 hashes:

cargo add sha-1

Then we can modify our read_object() function to compare the hash of an object's contents against the hash it was supposed to have:

use sha1::{Digest, Sha1};

fn read_object(hash: Hash) -> io::Result<Vec<u8>> {
  // ...
  // The entire uncompressed contents of the object, including the header
  // are the input to the hash function
  let contents_hash = Sha1::digest(&contents);
  if contents_hash.as_slice() != hash.0 {
    return Err(Error::new(
      ErrorKind::Other,
      format!("Object {} has wrong hash {:x}", hash, contents_hash),
    ))
  }

  Ok(contents)
}

Hash functions are often used to quickly check whether two inputs are equal. Since they are deterministic, two identical inputs will always have the same hash. Since they are chaotic, it is very unlikely that two different inputs have the same hash (a "hash collision"). SHA-1 produces 160-bit hashes, so (assuming the hashes are evenly distributed) the likelihood of two different inputs having the same hash is around 2^-160, or 10^-48. This is an exceedingly small number, so git actually assumes that any objects with the same hash are identical. In fact, it is common to refer to commits by just a 7-character hash (like the af64eba reported by git commit earlier) because even this collision probability is negligible for a small repository.

The fact that git stores every object by hash has a very useful consequence. If two files (or the same file in multiple commits) have the same contents, git will try to create blob objects for both of them, and these objects will have the same hash. git can recognize the second hash as one that it already has, and will just reuse the existing blob.

In fact, the same holds for tree objects. Since a tree object consists of the names, modes, and hashes of the entries in the tree, a tree's hash is a hash of the names, modes, and contents of all the files under it. (It is important that tree entries are sorted by name; otherwise, the representation of a tree would not be unique.) So, if an entire directory is the same between two commits, git will reuse the same tree.

As mentioned in "What's in a commit?", this reuse of objects is crucial to save storage space. But keep in mind that this check only happens for whole objects. If you change even a single character of a file, its blob will have a completely different hash, so the whole new file will be stored in a separate blob object. (We will see in the next post how git avoids actually storing two very similar objects.)

Implementing a git command

We've learned a lot! We can traverse the commit history of a git repository, see files at any commit, and understand where object hashes come from. Let's put this together to implement a real git command: git diff COMMIT1 COMMIT2, which shows the difference between all files at two commit hashes.

We will need to compare the blobs corresponding to the same file in two commits. Instead of always comparing the contents of the blobs, we can skip them if their hashes are the same, since that means they are the same object. We also need to handle the case where one of the blobs is missing, which means the file was added or removed between the commits.

We use the UNIX command-line program diff to compare the contents of the files. diff expects two files as input, so we copy the blobs to temporary files .git/a and .git/b.

use std::process::Command;

const EMPTY_FILE: &str = "/dev/null";
const DIFF_LEFT_FILE: &str = ".git/a";
const DIFF_RIGHT_FILE: &str = ".git/b";

// Prints the diff between two blobs with the given filename
fn diff_blob(path: &Path, blob1: Option<Hash>, blob2: Option<Hash>)
  -> io::Result<()>
{
  // If the hashes match, the blob objects are the same
  if blob1 == blob2 {
    return Ok(())
  }

  // We will store each blob's contents in a temporary file,
  // so print the real filename of the blobs
  println!("{}", path.display());
  // If either blob is missing, compare an empty file instead
  let filename1 = match blob1 {
    Some(blob) => {
      let blob = read_blob(blob)?;
      fs::write(DIFF_LEFT_FILE, blob.0)?;
      DIFF_LEFT_FILE
    }
    _ => EMPTY_FILE,
  };
  let filename2 = match blob2 {
    Some(blob) => {
      let blob = read_blob(blob)?;
      fs::write(DIFF_RIGHT_FILE, blob.0)?;
      DIFF_RIGHT_FILE
    }
    _ => EMPTY_FILE,
  };
  // Run `diff -u FILENAME1 FILENAME2` to produce a git-like diff
  Command::new("diff").args(&["-u", filename1, filename2]).status()?;
  Ok(())
}

Now, since we will be comparing the entire trees corresponding to the two commit objects, we want a function to compare trees. Again, we can skip the entire tree if the hashes are the same. And either tree object might not exist, in which case we treat it as any empty tree.

Since trees list their entries in name order, we can merge these two sorted slices to process all entries in both trees in order and find all entries that exist in both trees. Note that the same filename might correspond to a file in one tree and a directory in the other, in which case we treat it as though the file were deleted and the directory added.

use std::path::PathBuf;

// Reads a tree if a tree hash is given, or simulates an empty tree
fn read_optional_tree(hash: Option<Hash>) -> io::Result<Tree> {
  match hash {
    Some(hash) => read_tree(hash),
    // If the tree doesn't exist, pretend it's empty
    _ => Ok(Tree(vec![])),
  }
}

// Prints the diffs of all files under two trees with the given filename
fn diff_tree(path: &mut PathBuf, tree1: Option<Hash>, tree2: Option<Hash>)
  -> io::Result<()>
{
  use std::cmp::Ordering::*;

  // If the hashes match, the tree objects are the same
  if tree1 == tree2 {
    return Ok(())
  }

  let tree1 = read_optional_tree(tree1)?;
  let tree2 = read_optional_tree(tree2)?;

  // Since the entries are sorted by name, we can merge them together
  let mut entries_left1 = tree1.0.as_slice();
  let mut entries_left2 = tree2.0.as_slice();
  while let (Some((entry1, entries_rest1)), Some((entry2, entries_rest2))) =
    (entries_left1.split_first(), entries_left2.split_first())
  {
    match entry1.name.cmp(&entry2.name) {
      // Only compare the entries if they are both files or both directories.
      // Otherwise, treat them as separate entries.
      Equal if entry1.mode == entry2.mode => {
        diff_entry(path, Some(entry1), Some(entry2))?;
        entries_left1 = entries_rest1;
        entries_left2 = entries_rest2;
      }
      // The entry only exists in the left tree, so it was deleted
      Less | Equal => {
        diff_entry(path, Some(entry1), None)?;
        entries_left1 = entries_rest1;
      }
      // The entry only exists in the right tree, so it was added
      Greater => {
        diff_entry(path, None, Some(entry2))?;
        entries_left2 = entries_rest2;
      }
    }
  }
  // Process any remaining entries after one of the trees is finished
  for entry in entries_left1 {
    diff_entry(path, Some(entry), None)?;
  }
  for entry in entries_left2 {
    diff_entry(path, None, Some(entry))?;
  }
  Ok(())
}

// Prints the diff under two tree entries, which may be blobs or trees
fn diff_entry(
  path: &mut PathBuf,
  entry1: Option<&TreeEntry>,
  entry2: Option<&TreeEntry>,
) -> io::Result<()> {
  use Mode::*;

  // At least one of the entries must be provided.
  // If both are provided, they must have the same name and mode.
  let entry = entry1.or(entry2).unwrap();
  let hash1 = entry1.map(|entry| entry.hash);
  let hash2 = entry2.map(|entry| entry.hash);
  // Append the name to the path, e.g. "dir1/dir2" becomes "dir1/dir2/file"
  path.push(&entry.name);
  match entry.mode {
    File => diff_blob(path, hash1, hash2)?,
    Directory => diff_tree(path, hash1, hash2)?,
  }
  // Reset the path
  path.pop();
  Ok(())
}

And finally, we can add some basic command-line argument processing to parse the two commit hashes we pass.

use std::env;

fn main() -> io::Result<()> {
  // Read 2 commit hashes from the command-line arguments
  let args: Vec<_> = env::args().collect();
  let [_, commit1, commit2] = <[String; 3]>::try_from(args).map_err(|args| {
    Error::new(ErrorKind::Other, format!("Usage: {} COMMIT1 COMMIT2", args[0]))
  })?;
  let commit1 = Hash::from_str(&commit1)?;
  let commit2 = Hash::from_str(&commit2)?;

  // Diff the trees corresponding to the commits
  let commit1 = read_commit(commit1)?;
  let commit2 = read_commit(commit2)?;
  diff_tree(&mut PathBuf::new(), Some(commit1.tree), Some(commit2.tree))?;
  // Remove the temporary files we might have created
  let _ = fs::remove_file(DIFF_LEFT_FILE);
  let _ = fs::remove_file(DIFF_RIGHT_FILE);
  Ok(())
}

Running the program on the two commits, we can see the changes introduced by cargo add flate2:

Cargo.lock
--- .git/a  2021-10-30 14:01:38.000000000 -0700
+++ .git/b  2021-10-30 14:01:38.000000000 -0700
@@ -3,5 +3,63 @@
 version = 3

 [[package]]
+name = "adler"
+version = "1.0.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f26201604c87b1e01bd3d98f8d5d9a8fcbb815e8cedb41ffccbeb4bf593a35fe"
+
+[[package]]
+name = "autocfg"
+version = "1.0.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "cdb031dd78e28731d87d56cc8ffef4a8f36ca26c38fe2de700543e627f8a464a"
+
+[[package]]
+name = "cfg-if"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd"
+
+[[package]]
+name = "crc32fast"
+version = "1.2.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "81156fece84ab6a9f2afdb109ce3ae577e42b1228441eded99bd77f627953b1a"
+dependencies = [
+ "cfg-if",
+]
+
+[[package]]
+name = "flate2"
+version = "1.0.22"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1e6988e897c1c9c485f43b47a529cef42fde0547f9d8d41a7062518f1d8fc53f"
+dependencies = [
+ "cfg-if",
+ "crc32fast",
+ "libc",
+ "miniz_oxide",
+]
+
+[[package]]
 name = "git"
 version = "0.1.0"
+dependencies = [
+ "flate2",
+]
+
+[[package]]
+name = "libc"
+version = "0.2.103"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "dd8f7255a17a627354f321ef0055d63b898c6fb27eff628af4d1b66b7331edf6"
+
+[[package]]
+name = "miniz_oxide"
+version = "0.4.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a92518e98c078586bc6c934028adcca4c92a53d6a958196de835170a01d84e4b"
+dependencies = [
+ "adler",
+ "autocfg",
+]
Cargo.toml
--- .git/a  2021-10-30 14:01:38.000000000 -0700
+++ .git/b  2021-10-30 14:01:38.000000000 -0700
@@ -6,3 +6,4 @@
 # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

 [dependencies]
+flate2 = "1.0.22"

Up next...

In the next post of this series, we'll see that the .git/objects directory is much more complicated than it looked. We'll learn how a "pack file" compresses collections of objects, both in the .git directory and during a git pull or git push. And we'll investigate git's solution to efficiently find objects within pack files.