The File System

The in-memory file system will store our files. We could implement this lab with real files, but this will make it much easier to test our code. The file system will store a collection of file entries, where each entry contains the name of the file, and a String containing the files contents. We can simulate a directory structure by using / in filenames, but the file system itself doesnt know anything about directories. The file entries in the file system must be kept sorted by filename. The class FileSystem has been provided for you and most of its code is complete. You will need to fill in the two empty methods.

public static class FileSystemEntry implements Comparable {

public FileSystemEntry(String filename) {

}

public String getFilename() {

return null;

}

/**

* Returns the contents of the file

* @return the contents of the file

*/

@Override

public String toString() {

return null;

}

public void setContents(String contents) {

}

@Override

public int compareTo(FileEntry that) {

return this.filename.compareTo(that.filename);

}

}

public class FileSystem {

/* Supplied code omitted */

public String readFileContents(String filename) {

return null;

}

public void writeFileContents(String filename, String contents) {

}

}

The Object Store

There are three types of objects that we will be storing: blobs, trees, and commits. Each object has a specific file format. Well be using slightly different formats from the real Git object store. In each file format below, there is a newline at the end of every line, and is the number of characters in the data after the first line, including the at the end of the last line.

There are two areas in the file system that were interested in the working directory (the root), and the object store, which will be stored in the .git directory. Again, the file system doesnt know about directories, so this just means well have some filenames that start with .git/ and others that dont.

Blobs are raw data. Each time we store a snapshot of a file in Git, that snapshot is stored as a blob containing the files data. The format for a blob is:

blob

Trees store metadata about the files in your working directory. Each entry in the tree stores the mode of the file (for us this will always be 100644), its name, and the hash of the files contents. Real Git trees can reference other trees so that you can have subdirectories in your working directory, but we wont be implementing that function. The format for a tree is:

tree

Commits store information about a snapshot of your working directory. Each commit stores the hash of the tree of files it contains, the hash of the previous commit (if any), the author of the commit, and the commit comment. The format for a commit is:

commit

tree

parent This line is missing (not blank) for the first commit

author

When an object is stored in Git, the object data is hashed using the SHA-1 algorithm which gives a 40-character hexadecimal number as output. The object data is then written to a filename based on the result of the hash. For example, if we wanted to store a file containing the text Hello, Git!, we would convert it to the following blob:

blob 12

Hello, Git!

Hashing that blob gives 24be4db7b866e915bb21a87ab3c12ea44d7a99c5, and the object is then stored in a directory inside .git/objects. The subdirectory is the first two characters of the hash, and the filename is the remaining 38 characters, so this blob would be stored in the file

.git/objects/24/be4db7b866e915bb21a87ab3c12ea44d7a99c5

Trees and commits are stored in exactly the same way. You can read more about the details of this at the following link, but keep in mind that the data formats are a little different for us: https://git-scm.com/book/en/v2/Git-Internals-Git-Objects

A SHORT NOTE ABOUT SHA-1

A lot of people become concerned at some point that they will, by random happenstance, have two objects in their repository that hash to the same SHA-1 value. What then?

...

However, you should be aware of how ridiculously unlikely this scenario is. The SHA-1 digest is 20 bytes or 160 bits. The number of randomly hashed objects needed to ensure a 50% probability of a single collision is about 2^80 ...Thats 1,200 times the number of grains of sand on the earth...A higher probability exists that every member of your programming team will be attacked and killed by wolves in unrelated incidents on the same night.

public class Sha1 { public static MessageDigest getInstance(String algorithm) { try { return MessageDigest.getInstance(algorithm); } catch (NoSuchAlgorithmException e) { throw new RuntimeException(e); } }

public static String hash(String data) { MessageDigest md = getInstance("SHA-1"); return DatatypeConverter.printHexBinary(md.digest(data.getBytes())).toLowerCase(); } }

import java.util.Scanner;

public class GitBlob extends GitObject {

public GitBlob(String data) {

}

public String getData() {

return this.file;

}

@Override

public String toString() {

}

public static GitBlob fromFile(Scanner in) {

}

}

import java.util.List; import java.util.Scanner;

public class GitTree extends GitObject {

public void addFile(String filename, int mode, String hash) { }

public List getFiles() { return null; }

public GitTreeEntry getFile(String filename) { return null; }

@Override public String toString() { return null; }

public static GitTree fromFile(Scanner in) { return null; } }

import java.util.Scanner;

public class GitCommit extends GitObject {

public GitCommit(String treeHash, String parentHash, String author, String comment) { }

public String getTreeHash() { return null; }

public String getParentHash() { return null; }

public String getAuthor() { return null; }

public String getComment() { return null; }

@Override public String toString() { return null; }

public static GitCommit fromFile(Scanner in) { return null; } }

import java.util.List;

public class Git { private FileSystem fs; private List commits;

public Git(FileSystem fs) { }

public String storeObject(GitObject obj) { return null; }

public String catFile(String hash) { return null; }

public String commit(String author, String comment) { return null; }

public String log() { return null; }

public void checkout(String hash) { } }