diff options
| -rw-r--r-- | cmd/mygit/main.go | 498 |
1 files changed, 492 insertions, 6 deletions
diff --git a/cmd/mygit/main.go b/cmd/mygit/main.go index 686392e..155d84a 100644 --- a/cmd/mygit/main.go +++ b/cmd/mygit/main.go @@ -4,23 +4,46 @@ import ( "bytes" "compress/zlib" "crypto/sha1" + "encoding/binary" "fmt" "io" + "net/http" "os" + "path/filepath" "strconv" + "strings" "time" ) -func init_repo() { +type TreeNode struct { + Mode int + Name string + Hash string +} + +type objectType uint8 + +const ( + COMMIT objectType = 0b001 + TREE objectType = 0b010 + BLOB objectType = 0b011 + TAG objectType = 0100 + OFS_DELTA objectType = 0b110 + REF_DELTA objectType = 0b111 +) + +func init_repo(createBranch bool) { for _, dir := range []string{".git", ".git/objects", ".git/refs"} { if err := os.MkdirAll(dir, 0755); err != nil { fmt.Fprintf(os.Stderr, "Error creating directory: %s\n", err) } } - headFileContents := []byte("ref: refs/heads/master\n") - if err := os.WriteFile(".git/HEAD", headFileContents, 0644); err != nil { - fmt.Fprintf(os.Stderr, "Error writing file: %s\n", err) + if createBranch { + headFileContents := []byte("ref: refs/heads/master\n") + if err := os.WriteFile(".git/HEAD", headFileContents, 0644); err != nil { + fmt.Fprintf(os.Stderr, "Error writing file: %s\n", err) + } } fmt.Println("Initialized git directory") @@ -242,6 +265,459 @@ func commit_tree(tree_sha, parent_sha, message string) []byte { return create_obj(content) } +func read_nbytes(n int, reader io.Reader) (data []byte) { + blobData := make([]byte, n) + io.ReadFull(reader, blobData) + return blobData +} + +func read_pack(reader io.Reader) (data []byte) { + length, _ := strconv.ParseUint(string(read_nbytes(4, reader)), 16, 32) + if length <= 4 { + return nil + } + return read_nbytes(int(length)-4, reader) +} + +func type_git(hash string) (objectType string, err error) { + reader, err := reader(hash) + if err != nil { + return "", err + } + defer reader.Close() + return strings.Split(read_to_next_nbytes(reader), " ")[0], nil +} + +func make_branch(ref string, hash string) (err error) { + objectType, err := type_git(hash) + if err != nil { + return err + } + if objectType != "commit" { + return fmt.Errorf("%s isn't a commit and so can't be made a branch", hash) + } + + if err := os.MkdirAll(".git/refs/heads", 0755); err != nil { + return err + } + + if err := os.WriteFile(fmt.Sprintf(".git/refs/heads/%s", ref), []byte(hash+"\n"), 0644); err != nil { + return err + } + + return nil +} + +func read_to_next_nbytes(reader io.Reader) (header string) { + bytes := []byte{} + for { + data := read_nbytes(1, reader) + if len(data) < 1 || data[0] == 0 { + break + } + bytes = append(bytes, data[0]) + } + return string(bytes) +} + +func file_for_hash(hash string) (file string, err error) { + if len(hash) < 2 { + return "", fmt.Errorf("provided hash isn't long enough") + } + directory := hash[:2] + filename := hash[2:] + + files, err := filepath.Glob(fmt.Sprintf(".git/objects/%s/%s*", directory, filename)) + if err != nil { + return "", err + } + + if len(files) < 1 { + return "", fmt.Errorf("fatal: Not a valid object name %s", hash) + } + if len(files) > 1 { + return "", fmt.Errorf("provided hash isn't unique enough") + } + + return files[0], nil +} + +func reader(hash string) (reader io.ReadCloser, err error) { + filepath, err := file_for_hash(hash) + if err != nil { + return nil, err + } + + file, err := os.Open(filepath) + if err != nil { + return nil, err + } + + return zlib.NewReader(file) +} + +func constructBlob(path string, name string, hash string) (err error) { + blobReader, err := reader(hash) + if err != nil { + return err + } + read_to_next_nbytes(blobReader) + blobData, err := io.ReadAll(blobReader) + if err != nil { + return err + } + return os.WriteFile(path+name, blobData, 0644) +} + +func readTree(length int, reader io.Reader) []TreeNode { + result := []TreeNode{} + for length > 0 { + header := read_to_next_nbytes(reader) + parts := strings.Split(header, " ") + + mode, _ := strconv.Atoi(parts[0]) + name := parts[1] + hash := fmt.Sprintf("%x", read_nbytes(20, reader)) + result = append(result, TreeNode{mode, name, hash}) + + length -= len(header) + 21 + } + return result +} + +func constructTree(path string, hash string) (err error) { + treeReader, err := reader(hash) + if err != nil { + return err + } + defer treeReader.Close() + + length, err := strconv.Atoi(strings.Split(string(read_to_next_nbytes(treeReader)), " ")[1]) + if err != nil { + return err + } + treeNodes := readTree(length, treeReader) + + for _, treeNode := range treeNodes { + if treeNode.Mode == 40000 { + if err = os.Mkdir(path+treeNode.Name, 0755); err != nil { + return err + } + if err = constructTree(path+treeNode.Name+"/", treeNode.Hash); err != nil { + return err + } + } else { + if err = constructBlob(path, treeNode.Name, treeNode.Hash); err != nil { + return err + } + } + } + + return nil +} + +func checkout(ref string) (err error) { + hash, err := os.ReadFile(fmt.Sprintf(".git/refs/heads/%s", ref)) + if err != nil { + return err + } + stringHash := string(hash[:len(hash)-1]) + + headFileContents := []byte(fmt.Sprintf("ref: refs/heads/%s\n", ref)) + if err := os.WriteFile(".git/HEAD", headFileContents, 0644); err != nil { + return fmt.Errorf("error writing file: %s", err) + } + + commitReader, err := reader(stringHash) + if err != nil { + return err + } + read_to_next_nbytes(commitReader) + read_nbytes(5, commitReader) + treeHash := string(read_nbytes(20, commitReader)) + commitReader.Close() + return constructTree("./", treeHash) +} + +func read_byte(reader io.Reader) byte { + return read_nbytes(1, reader)[0] +} + +func readTypeAndSize(reader io.Reader) (oType objectType, size uint64) { + // first byte is special because it contains the type + firstByte := read_byte(reader) + oType = objectType((firstByte & 0b01110000) >> 4) + size = uint64(firstByte & 0b1111) + + if firstByte&0b10000000 == 0 { + return oType, size + } + + bytesRead := 1 + for { + b := read_byte(reader) + bytesRead += 1 + size = size | (uint64(b&0b1111111) << ((bytesRead-2)*7 + 4)) + if b&0b10000000 == 0 { + break + } + } + return oType, size +} + +func hash_data(data []byte) (hash []byte) { + hasher := sha1.New() + hasher.Write(data) + return hasher.Sum(nil) +} + +func write_object(data []byte) (hash []byte, err error) { + hash = hash_data(data) + + directory := fmt.Sprintf(".git/objects/%x", hash[:1]) + if err := os.MkdirAll(directory, 0755); err != nil { + return nil, fmt.Errorf("error creating directory: %s", err) + } + + filepath := fmt.Sprintf("%s/%x", directory, hash[1:]) + file, err := os.Create(filepath) + if err != nil { + return nil, fmt.Errorf("error creating file: %s", err) + } + defer file.Close() + + w := zlib.NewWriter(file) + _, err = w.Write(data) + if err != nil { + return nil, fmt.Errorf("error writing file: %s", err) + } + w.Close() + + return hash, nil +} + +func write_tree(data []byte) (hash []byte, err error) { + leadingBytes := []byte(fmt.Sprintf("tree %d%c", len(data), 0)) + return write_object(append(leadingBytes, data...)) +} + +func write_commit(data []byte) (hash []byte, err error) { + leadingBytes := []byte(fmt.Sprintf("commit %d%c", len(data), 0)) + return write_object(append(leadingBytes, data...)) +} + +func write_blob(data []byte) (hash []byte, err error) { + leadingBytes := []byte(fmt.Sprintf("blob %d%c", len(data), 0)) + return write_object(append(leadingBytes, data...)) +} + +func zlib_read(size uint64, reader io.Reader) (data []byte) { + zlibReader, _ := zlib.NewReader(reader) + data = read_nbytes(int(size), zlibReader) + zlibReader.Close() + return data +} + +func readSize(reader io.Reader) (size uint64) { + size = 0 + bytesRead := 0 + for { + b := read_byte(reader) + bytesRead += 1 + size = size | (uint64(b&0b1111111) << ((bytesRead - 1) * 7)) + if b&0b10000000 == 0 { + break + } + } + return size +} + +func applyDelta(referenceHash string, delta []byte) (targetData []byte, err error) { + deltaBuffer := bytes.NewBuffer(delta) + sourceLength := readSize(deltaBuffer) + targetLength := readSize(deltaBuffer) + + objectType, err := type_git(referenceHash) + if err != nil { + return nil, err + } + sourceReader, err := reader(referenceHash) + if err != nil { + return nil, err + } + defer sourceReader.Close() + read_to_next_nbytes(sourceReader) + sourceData, err := io.ReadAll(sourceReader) + if err != nil { + return nil, err + } + if len(sourceData) != int(sourceLength) { + return nil, fmt.Errorf("source object wasn't the correct length for de deltifying") + } + + for deltaBuffer.Len() > 0 { + command := read_byte(deltaBuffer) + if command&0b10000000 == 0 { + // insert + targetData = append(targetData, read_nbytes(int(command&0b1111111), deltaBuffer)...) + } else { + // copy + offset := uint32(0) + for i := 0; i < 4; i++ { + if command&(0b1<<i) != 0 { + offset |= uint32(read_byte(deltaBuffer)) << (8 * i) + } + } + size := uint32(0) + for i := 0; i < 3; i++ { + if command&(0b10000<<i) != 0 { + size |= uint32(read_byte(deltaBuffer)) << (8 * i) + } + } + + targetData = append(targetData, sourceData[offset:offset+size]...) + } + } + + if len(targetData) != int(targetLength) { + return nil, fmt.Errorf("target object wasn't the correct length for de deltifying") + } + + targetData = append([]byte(fmt.Sprintf("%s %d%c", objectType, len(targetData), 0)), targetData...) + return targetData, nil +} + +func unpack(directory string, reader io.Reader) (err error) { + packData, err := io.ReadAll(reader) + if err != nil { + return err + } + + if string(packData[:4]) != "PACK" { + return fmt.Errorf("not a valid pack") + } + + checksum := packData[len(packData)-20:] + packData = packData[:len(packData)-20] + if !bytes.Equal(checksum, hash_data(packData)) { + return fmt.Errorf("pack data did not pass checksum") + } + + packBuffer := bytes.NewBuffer(packData) + read_nbytes(8, packBuffer) + + objectCount := binary.BigEndian.Uint32(read_nbytes(4, packBuffer)) + + for i := uint32(0); i < objectCount; i++ { + oType, size := readTypeAndSize(packBuffer) + switch oType { + case COMMIT: + write_commit(zlib_read(size, packBuffer)) + case TREE: + write_tree(zlib_read(size, packBuffer)) + case BLOB: + write_blob(zlib_read(size, packBuffer)) + case TAG: + zlib_read(size, packBuffer) + case OFS_DELTA: + return fmt.Errorf("offset deltas aren't currently supported") + case REF_DELTA: + referenceHash := read_nbytes(20, packBuffer) + data := zlib_read(size, packBuffer) + targetData, err := applyDelta(fmt.Sprintf("%x", referenceHash), data) + if err != nil { + return err + } + write_object(targetData) + } + + } + + return nil +} + +func clone_repo(remoteUrl string, directory string) (response string, err error) { + if remoteUrl[len(remoteUrl)-1] == '/' { + remoteUrl = remoteUrl[:len(remoteUrl)-1] + } + + client := http.Client{Timeout: time.Duration(30) * time.Second} + discoveryRequest, err := http.NewRequest("GET", fmt.Sprintf("%s/info/refs?service=git-upload-pack", remoteUrl), nil) + if err != nil { + return "", err + } + discoveryResponse, err := client.Do(discoveryRequest) + if err != nil { + return "", err + } + if discoveryResponse.StatusCode != 200 { + return "", fmt.Errorf("discovery status: %s", discoveryResponse.Status) + } + defer discoveryResponse.Body.Close() + + data := read_pack(discoveryResponse.Body) + for data != nil { + data = read_pack(discoveryResponse.Body) + } + + data = read_pack(discoveryResponse.Body) + refParts := strings.Split(strings.Split(string(data), "\x00")[0], " ") + if refParts[1] != "HEAD" { + return "", fmt.Errorf("no HEAD ref advertized") + } + headHash := refParts[0] + + headRef := "" + for data := read_pack(discoveryResponse.Body); data != nil; data = read_pack(discoveryResponse.Body) { + refParts := strings.Split(string(data), " ") + if refParts[0] != headHash { + continue + } + headRef = refParts[1] + if headRef[len(headRef)-1] == '\n' { + headRef = headRef[:len(headRef)-1] + } + } + if headRef == "" { + return "", fmt.Errorf("a ref that matches HEAD could not be found") + } + refName := headRef[strings.LastIndex(headRef, "/")+1:] + + packBody := bytes.NewBuffer([]byte(fmt.Sprintf("0032want %s\n00000009done\n", headHash))) + packRequest, err := http.NewRequest("POST", fmt.Sprintf("%s/git-upload-pack?service=git-upload-pack", remoteUrl), packBody) + if err != nil { + return "", err + } + packRequest.Header.Add("Content-Type", "application/x-git-upload-pack-request") + packResponse, err := client.Do(packRequest) + if err != nil { + return "", err + } + if packResponse.StatusCode != 200 { + return "", fmt.Errorf("pack status: %s", discoveryResponse.Status) + } + defer packResponse.Body.Close() + + if err = os.Mkdir(directory, 0755); err != nil { + return "", err + } + os.Chdir(directory) + init_repo(false) + + read_pack(packResponse.Body) + if err = unpack(directory, packResponse.Body); err != nil { + return "", err + } + if err = make_branch(refName, headHash); err != nil { + return "", err + } + if err = checkout(refName); err != nil { + return "", err + } + + return fmt.Sprintf("cloned remote %s to %s\n", remoteUrl, directory), nil +} + func main() { if len(os.Args) < 2 { fmt.Fprintf(os.Stderr, "usage: mygit <command> [<args>...]\n") @@ -250,7 +726,7 @@ func main() { switch command := os.Args[1]; command { case "init": - init_repo() + init_repo(true) case "cat-file": content := read_obj(os.Args[3]) @@ -271,8 +747,18 @@ func main() { sha := commit_tree(os.Args[2], os.Args[4], os.Args[6]) fmt.Printf("%x\n", sha) + case "clone": + clone, err := clone_repo(os.Args[2], os.Args[3]) + + if err != nil { + fmt.Fprintf(os.Stderr, "Error cloning repo: %s\n", err) + os.Exit(0) + } + + fmt.Printf("%x\n", clone) + default: fmt.Fprintf(os.Stderr, "Unknown command %s\n", command) - os.Exit(1) + os.Exit(0) } } |