Building Git: part IV

2025-03-31

Building Git: Part IV

Git Tree

Yo what’s good, guys? What amazing project you guys are working on? In the previous part we built the link to the past, aka commit history. Currently, in our implementation we are just storing only the singletree (or the root directory) but the git also stores all the sub-directories in the root directory or the directory in which the .git file has been initialized.

Now, we are going to update our code to store all the sub-directories in the root tree.

Executable files

Currently, we are just storing the file mode as 100644, which is the default for all the normal files, but what about the files that are not normal? Like exectuable complied file created by running go build. These files have different file mode mainly 100755.

The starting 10 tells us that it is a file, and the remaining part tells us the permission of the files for the different users. If you want to understand the file permission you can read my Understanding Linux filesystem.

Storing Executable files in tree

Now let’s get to storing the file modes.

database.go

1
import (
2
    "syscall"
3
)
4

5

6
// Updating the Entries struct
7
type Entries struct {
8
    Path string
9
    OID  []byte
10
    Stat string // New field for storing file mode
11
}
12

13
func CreateTreeEntry(entries []Entries) bytes.Buffer {
14
    var buf bytes.Buffer
15
    for _, entry := range entries {
16
        // Update this line, now storing dynamic filemode
17
        input := fmt.Sprintf("%s %s", entry.Stat, entry.Path)
18
        buf.WriteString(input)
19
        buf.WriteByte(0)
20
        buf.Write(entry.OID)
21
    }
22
    return buf
23
}
24

25
// New function to get the file mode
26
func FileMode(file os.DirEntry) (uint32, error) {
27
    f, err := os.Stat(file.Name())
28
    if err != nil {
29
        return 0, err
30
    }
31
    // getting the stat from the underlying syscall
32
    // it will only work for unix like operating systems
33
    // but we can make it work for the windows, by checking
34
    // the underlying operating system. But that for later
35
    // me.
36
    stat := f.Sys().(*syscall.Stat_t)
37
    return stat.Mode, nil
38
}

cmdHandler.go

1
import (
2
    "strconv"
3
)
4

5

6
func cmdCommitHandler(commit string) error {
7
  // Get all the files in the working directory
8
  allFiles, err := os.ReadDir(gitgo.ROOTPATH)
9
  if err != nil {
10
    return fmt.Errorf("Error reading Dir: %s", err)
11
  }
12
  workFiles := gitgo.RemoveIgnoreFiles(
13
    allFiles,
14
    gitgo.GITGO_IGNORE,
15
  ) // Remove the files or Dir that are in ignore.
16

17
  var entries []gitgo.Entries
18
  for _, file := range workFiles {
19
    if file.IsDir() {
20
      continue
21
    }
22

23
    data, err := os.ReadFile(file.Name())
24
    if err != nil {
25
      return fmt.Errorf("Error reading file: %s\n%s", file.Name(), err)
26
    }
27

28
    fileMode, err := gitgo.FileMode(file)
29
    if err != nil {
30
      return err
31
    }
32
    blobSHA, err := gitgo.StoreBlobObject(data)
33
    entry := gitgo.Entries{
34
      Path: file.Name(),
35
      OID:  blobSHA,
36
      Stat: strconv.FormatUint(uint64(fileMode), 8),
37
    }
38
    entries = append(entries, entry)
39
  }
40

41
    // .....

With this, now we can store the executable files in our tree structure.

Nested tree

Firstly, we will have to see how, git stores the sub-direcotries.

Let’s make a new directory to test this out.

1
mkdir test && cd test

1
echo "this is file1" > file1.txt
2
mkdir folder1
3
echo "this is file2" > folder1/file2.txt
4
mkdir folder1/folder2
5
echo "this is file3" > folder1/folder2/file3.txt

Now commit this to git, you will get a root hash.

1
❯ git cat-file -p 6eab21e
2
tree 314adb2b05c2d64911655eff66cf5c9d381a5a4c
3
author Vikuuu <adivik672@gmail.com> 1743399030 +0530
4
committer Vikuuu <adivik672@gmail.com> 1743399030 +0530
5

6
initial commit

Now cat the tree file.

1
❯ git cat-file -p 314adb2b05c2d64911655eff66cf5c9d381a5a4c
2
100644 blob 433eb172726bc7b6d60e8d68efb0f0ef4e67a667  file1.txt
3
040000 tree 7662ba3434fd7f48ad6d1df1c7501498631bfd74  folder1

Hmmm, so we can see here that we have a blob, and a tree in our root tree, which is the same as we created our directory, that has a file and a folder. Now lets see inside the folder1 tree.

1
❯ git cat-file -p 7662ba3434fd7f48ad6d1df1c7501498631bfd74
2
100644 blob f138820097c8ef62a012205db0b1701df516f6d5  file2.txt
3
040000 tree 29200651ef2c4956cf3d6d04d164570c43966781  folder2

We get the similar output, that is identical to our directory. the folder1 directory has a single file and a folder. Now lets see inside the folder2.

1
❯ git cat-file -p 29200651ef2c4956cf3d6d04d164570c43966781
2
100644 blob a309e46e332a0f166453c6137344852fab38d120  file3.txt

Now we only get a blob object, because we only have a single file in folder2

As we saw in the above examples, the tree blob stores another tree hash, for the sub-directories and then that tree stores the hash for the blob objects. This tree structure in called Merkle tree, in merkle tree the parent holds the hash of its children.

Building a Merkle tree

So firstly, we want to get all the files, files inside the folders, and so on. And we want our output to look something like this,

1
{
2
    "file1.txt",
3
    "file2.txt",
4
    "folder1/file3.txt",
5
    "folder2/folder3/file4.txt",
6
    "folder2/folder3/file5.txt",
7
}

We want the flatten list of all the files, and files inside any subdirectories.

database.go

1
var g_ignore = map[string]bool{
2
    ".":      true,
3
    "..":     true,
4
    ".gitgo": true,
5
}

files.go

1
package gitgo
2

3
import (
4
    "fmt"
5
    "io/fs"
6
    "path/filepath"
7
)
8

9
func ListFiles(dir string) ([]string, error) {
10
    var workfiles []string
11

12
    err := filepath.WalkDir(dir, func(path string, d fs.DirEntry, err error) error {
13
        if err != nil {
14
            return err
15
        }
16
        name := filepath.Base(path)
17

18
        if _, found := g_ignore[name]; found {
19
            if d.IsDir() {
20
                return filepath.SkipDir
21
            }
22
            return nil
23
        }
24

25
        // Append only files, not directories
26
        if !d.IsDir() {
27
            relPath, _ := filepath.Rel(dir, path)
28
            workfiles = append(workfiles, relPath)
29
        }
30

31
        return nil
32
    })
33
    if err != nil {
34
        return nil, err
35
    }
36

37
    return workfiles, nil
38
}

Here we are using the WalkDir function from the path/filepath standard library, to walk all the files and folders inside the root directory provided. and then just adding there relative name, with respect to the root directory path provided, here we are only adding the files, so that we get only the file paths.

Now we can change our cmdHandler function to first store all the blob objects to the disk using this flatten list returned to it, and then try to create a tree structure from the given flatten list. And then store all the sub-tree object and then lastly the root tree object onto the disk.

cmd/gitgo/cmdHandler.go

1
func cmdCommitHandler(_ string) error {
2
    rootPath := gitgo.ROOTPATH
3
    // storing all the blobs first
4
    entries, err := gitgo.StoreOnDisk(rootPath)
5
    if err != nil {
6
        return err
7
    }
8

9
    // build merkle tree, and store all the
10
    // subdirectories tree file
11
    tree := gitgo.BuildTree(entries)
12
    e, err := gitgo.TraverseTree(tree)
13
    if err != nil {
14
        return err
15
    }
16

17
    // now store the root tree
18
    rootTree := gitgo.TreeBlob{Data: gitgo.CreateTreeEntry(e)}.Init()
19
    treeHash, err := rootTree.Store()
20
    if err != nil {
21
        return err
22
    }
23

24
    // storing commit object
25
    // ....
26
}

In this we laid out the structure, now build how we are goint to accomplish this.

Let’s move the Entries struct to a new file

entries.go

1
package gitgo
2

3
type Entries struct {
4
    Path string
5
    OID  string
6
    Stat string
7
}
8

9
func NewEntry(name, oid, stat string) *Entries {
10
    return &Entries{Path: name, OID: oid, Stat: stat}
11
}

database.go

Let’s change the name of our previous Tree struct

1
type Tree struct {
2
type TreeBlob struct {
3
   Prefix string
4
   Data   bytes.Buffer
5
 }
6

7
func BlobInitialize(data []byte) *Blob {
8
  prefix := fmt.Sprintf(`blob %d`, len(data))
9
  return &Blob{
10
    Prefix: prefix,
11
    Data:   data,
12
  }
13
func (b Blob) Init() *Blob {
14
  prefix := fmt.Sprintf(`blob %d`, len(b.Data))
15
  b.Prefix = prefix
16
  return &b
17
 }
18

19
func TreeInitialize(data bytes.Buffer) *Tree {
20
  prefix := fmt.Sprintf(`tree %d`, data.Len())
21
  return &Tree{
22
    Prefix: prefix,
23
    Data:   data,
24
  }
25
func (t TreeBlob) Init() *TreeBlob {
26
  prefix := fmt.Sprintf(`tree %d`, t.Data.Len())
27
  t.Prefix = prefix
28
  return &t
29
 }
30

31
func (b *Blob) Store() ([]byte, error) {
32
func (b *Blob) Store() (string, error) {
33
   return StoreBlobObject(b.Data, b.Prefix)
34
 }
35

36
func (t *Tree) Store() (string, error) {
37
func (t *TreeBlob) Store() (string, error) {
38
   return StoreTreeObject(t.Data, t.Prefix)
39
 }
40

41

42
func StoreBlobObject(blobData []byte, prefix string) ([]byte, error) {
43
func StoreBlobObject(blobData []byte, prefix string) (string, error) {
44

45
@@ -129,10 +126,10 @@ func StoreBlobObject(blobData []byte, prefix string) ([]byte, error) {
46
   permPath := filepath.Join(DBPATH, hexBlobSha[:2], hexBlobSha[2:])
47
   err := StoreObject(blob, prefix, folderPath, permPath)
48
   if err != nil {
49
    return nil, err
50
    return "", err
51
   }
52

53
  return blobSHA, nil
54
  return hexBlobSha, nil
55
 }
56

57
 func StoreCommitObject(commitData, prefix string) (string, error) {
58

59

60
func FileMode(file os.DirEntry) (uint32, error) {
61
  f, err := os.Stat(file.Name())
62
func FileMode(file string) (uint32, error) {
63
  f, err := os.Stat(file)
64
   if err != nil {
65
     return 0, err
66
   }

After all the patching, let’s write the code for abstracting the storage of the blob object,

database.go

1
func StoreOnDisk(path string) ([]Entries, error) {
2
    // returns the flatten list of files in root directory
3
    files, err := ListFiles(path)
4
    if err != nil {
5
        return nil, err
6
    }
7

8
    var entries []Entries
9
    for _, f := range files {
10
        err = blobStore(f, &entries)
11
        if err != nil {
12
            return nil, err
13
        }
14
    }
15
    return entries, nil
16
}
17

18
func blobStore(f string, entries []Entries) error {
19
    fp := filepath.Join(ROOTPATH, f)
20
    data, err := os.ReadFile(fp)
21
    if err != nil {
22
        return err
23
    }
24
    blob := Blob{Data: data}.Init()
25
    fileMode, err := FileMode(fp)
26
    if err != nil {
27
        return err
28
    }
29

30
    hash, err := blob.Store()
31
    entry := Entries{
32
        Path: f,
33
        OID:  hash,
34
        Stat: strconv.FormatUint(uint64(fileMode), 8),
35
    }
36

37
    *entries = append(*entries, entry)
38
    return nil
39
}

With this now we firstly store all the blob object in our repository.

Now, let’s build the tree structure from the flatten list and then store all the tree structure.

tree.go

1
package gitgo
2

3
import (
4
    "bytes"
5
    "encoding/hex"
6
    "errors"
7
    "fmt"
8
    "log"
9
    "sort"
10
    "strings"
11
)
12

13
type Node interface{}
14

15
type Tree struct {
16
    Nodes map[string]Node
17
}
18

19
func NewTree() *Tree {
20
    return &Tree{Nodes: make(map[string]Node)}
21
}
22

23
func BuildTree(entries []Entries) *Tree {
24
    root := NewTree()
25
    for _, entry := range entries {
26
        parts := strings.Split(entry.Path, "/")
27
        current := root
28
        // Walk through each part of the path.
29
        for i, part := range parts {
30
            // Last part, this is file entry
31
        }
32
        if i == len(parts)-1 {
33
            current.Nodes[part] = NewEntry(part, entry.OID, entry.Stat)
34
        } else {
35
            // Intermediate directory, see if a Tree already exists.
36
            if node, ok := current.Nodes[part]; ok {
37
                if subtree, ok := node.(*Tree); ok {
38
                    current = subtree
39
                } else {
40
                    // conflict, an entry already exists where a directory is expected.
41
                    log.Printf("%q already exists as a file; cannot create directory\n" part)
42
                    break
43
                }
44
            } else {
45
                // Create a new tree for this directory
46
                newTree := NewTree()
47
                current.Nodes[part] = newTree
48
                current = newTree
49
            }
50
        }
51
    }
52
}
53

54
func TraverseTree(tree *Tree) ([]Entries, error) {
55
    entry := []Entries{}
56
    for name, node := range tree.Nodes {
57
        switch n := node.(type) {
58
        case *Tree:
59
            e, err := TraverseTree(n)
60
            if err != nil {
61
                return nil, err
62
            }
63
            tree := TreeBlob{Data: CreateTreeEntry(e)}.Init()
64
            hash, err := tree.Store()
65
            if err != nil {
66
                return nil, err
67
            }
68
            ne := Entries{Path: name, OID: hash, Stat: "040000"}
69
            entry = append(entry, ne)
70
        case *Entries:
71
            entry = append(entry, *n)
72
        default:
73
            return nil, errors.New("unknown data type")
74
        }
75
    }
76
    return entry, nli
77
}

Let’s move the CreateTreeEntry function from the database.go to the tree.go

tree.go

1
func CreateTreeEntry(entries []Entries) bytes.Buffer {
2
    var buf bytes.Buffer
3
    sort.Slice(entries, func(i, j int) bool {
4
        return entries[i].Path < entries[j].Path
5
    })
6
    for _, entry := range entries {
7
        input := fmt.Sprintf("%s %s", entry.Stat, entry.Path)
8
        buf.WriteString(input)
9
        buf.WriteByte(0)
10
        rawOID, err := hex.DecodeString(entry.OID)
11
        if err != nil {
12
            log.Printf("converting oid to raw: %s, for: %s", err, entry.Path)
13
        }
14
        buf.Write(rawOID)
15
    }
16
    return buf
17
}

In our CreateTreeEntry function we added the sorting function, to first sort all the entries, and then write them to the disk, because git also firstly sorts the directory and then stores them to the disk. This help in know if there is any change in the directory structure or not.

Design choice

Why are we first creating a flattened list, storing all the blobs and then recreating the tree from that flatten list and then storing the tree? Why can’t we store the blobs and tree object on disk as we traverse the directory and do it in one go?

Well, I just blindly followed the book…jk. I was also thinking about this and trying to be a smart ass. So, I also thought about this why not do it in a single time, and use the dfs and recursion, for this. So I set out on a journey to do so, and just to find no end :(.

Well I could not implement it, it was wasting my time, and the book also said that this is a good design choice as we are not intermingling the storing of blob, and tree object.

So Here you have the answer for this question

Afterwords

So, in this blog we extended our git implementation, we can now store the sub-directories and not be limited to the single root directory structure. And we also able to store the executable files in the tree object

In the next part we will be working on creating an Index.

Code Link: Github

Just know this,

Reinvent the wheel, so that you can learn how to invent wheel

– a nobody

#git

#go

#system-tools