[Build your own git] #5 write-tree 명령어 만들기

이전 연재글

[Build your own git] #0 시작

[Build your own git] #1 git init 과 .git 폴더의 구조

[Build your own git] #2 cat-file 명령어와 Git Object

[Build your own git] #3 git hash-object 명령어 만들기

[Build your own git] #4 ls-tree 명령어와 tree objects

주요 키워드

• git write-tree
• tree objects

 

서론

지난 글에서 tree objects 에서 파일/디렉터리 이름을 가져오는 ls-tree --name-only  기능을 구현해보았으니 이번엔 tree object 를 생성하는 기능인 write-tree 를 구현해보았다.

 

이것 또한 hash-object 처럼 읽는 것의 역순으로 차근차근 접근하면 문제 없지만, 단일 파일을 다루는 blob 과 달리 트리의 정보를 구축하는 동작이기 때문에 재귀적으로 하위에 있는 폴더와 파일들의 해시(20byte binary 형식) 을 계산할 필요가 있었다.

 

 

리마인드 - Tree Objects 의 구조 

트리 오브젝트는 트리의 전체적인 정보를 나타내는 '헤더'와 해당 디렉터리에 속한 파일/하위 디렉터리의 정보가 나열된 '엔트리'로 구성되어 있다.

tree <size>\0
<mode> <name>\0<20_byte_sha>
<mode> <name>\0<20_byte_sha>
(...)

 

 

구현을 진행하면서 내가 트리 오브젝트의 구조를 정확히 이해하지 못했거나 헷갈린 탓에 삽질을 했던 부분이 있는데, 언젠가 또 삽질할 것을 방지하기 위해 설명을 남겨둔다.

• <size> : 실제 하위 파일의 사이즈가 아닌 트리 오브젝트에서 엔트리가 차지하는 바이트(압축하지 않은 상태)를 의미한다.
• <20_byte_sha>  : 지금까지 해싱을 할 때 사용했던 hex 형식의 문자열 아닌 정확히 20 바이트의 바이너리를 그대로 저장해야한다. (open ssl 로 SHA-1 해시를 생성했을 때 출력되는 uint8_t 배열을 파일에 그대로 입력)
• <mode> : 실제 git 명령어로 모드 값을 추출했을 때 040000 으로 출력되는데, 실제 코드에서 모드 값을 입력할 때엔 앞의 0은 제외하고 40000 으로 해야만 한다. 이걸 모르는 상태에서 트리 오브젝트를 생성했을 때, 예상되는 해시값이 나오지 않아 혼란에 빠졌다. 육안으로 보면 완전 동일했기 때문에 사이즈를 확인해보니 직접 생성한 파일의 사이즈가 2바이트 더 크게 나왔다. 트리 오브젝트를 생성하는 로직을 하나하나 살펴보던 중, mode 앞에 0을 붙인 것이 가장 의심이 되었다. 40000 은 디렉터리에 붙는 모드 값이고 0 문자열 하나는 1바이트, 그리고 현재 트리의 디렉터리 갯수는 2개. 가설이 맞다면 '0' 2개로 인해 2바이트가 늘어날 것이다. 그리고 그 가설은 진짜였다(...) 실제 파일을 까볼 수 없어 git 명령어로만 출력해서 본 탓에 생긴 문제였던 것 같다.  직접 코드를 통해 압축을 해제해서 나온 값을 기준으로 작업했다면 발생하지 않았을 것 같다. 다음 기능에는 직접 압축을 풀어서 봐야겠다.
• 엔트리의 순서는 : 디렉터리 > 파일로 저장되어야하며 동일한 타입끼린 오름차순으로 정렬해야한다.

 

필요한 구현

write-tree 기능은 '스테이징 영역(Staging Area)' 에 있는 정보를 토대로 트리에 추가할지 말지 결정을 하는데, 이번 구현에서는 워킹 디렉터리에 있는 파일들이 모두 스테이징 영역에 있다는 가정하에 구현했다.

 

0) 재귀 호출을 위해 write_tree 라는 함수로 작성한다.

1) (shell , bash 기준) 현재 위치에 속한 파일과 디렉터리를 모두 순회한다.

 

2-1) 파일인 경우 hash-object 처럼 blob object 를 생성하고 만들어진 20byte 해시를 가져와서 파일의 데이터를 만든다.

ex) 100644 <파일 이름>\0 <20바이트 해시>

 

2-2) 디렉터리인 경우 write_tree 를 재귀호출하고 만들어진 20byte 해시를 가져와서 디렉터리의 데이터를 만든다.

ex) 40000 <디렉터리 이름>\0 <20바이트 해시>

 

3) 2-1), 2-2) 에서 만들어진 데이터들을 규칙에 맞게 정렬하고 하나로 합친다. (= 엔트리)

4) tree <엔트리의 사이즈(바이트)>\0 로 헤더를 만든다.

5) 헤더와 엔트리를 합쳐 원본 형태의 트리 오브젝트를 만들고 SHA-1 해싱한 값(여기서는 40-char hex 문자열)을 저장해둔다.

6) 원본 형태의 트리 오브젝트를 압축하고, 5)에서 만든 해시를 사용하여 objects/디렉터리(2-char) / 파일이름(38-char) 로 저장한다.

7) 모든 과정이 성공했다면 5) 의 hex 문자열 해시를 콘솔에 출력한다.

 

코드

아래는 write_tree 함수이다. 파일을 생성하고 그 결과로 나온 바이너리 형태의 해시와 텍스트 형식의 해시를 외부에 제공하기 위해 다소 요상한 형태의 매개변수 목록이 만들어졌다. 사실 바이너리 해시만 반환하고 외부에서 직접 텍스트로 바꾸면 간단해지지 않을까? 라고 생각했지만 내부에서도 트리 오브젝트 파일을 만들 때 디렉터리와 파일 이름을 위해 텍스트 형식의 해시를 만들어버리기 때문에 외부에서 텍스트 형식으로 변환하는건 중복으로 일하게 되는 꼴이라 함께 외부로 반환하게 되었다.

 

그 외에도 지적할 부분이 많아 보여서 지속적으로 개선할 계획이다 :(

 

int write_tree(const std::string& path, std::string& outHash_hex, uint8_t *& outHash) {
/*
tree <size>\0
<mode> <name>\0<20_byte_sha>
<mode> <name>\0<20_byte_sha>
<20_byte_sha> => not hexadeciaml format
*/

    // iterate current directory
    // assume all files in the working directory are staged. (except .git)
    
    auto content_data = std::string();
    auto iter_directory = std::filesystem::directory_iterator(std::filesystem::path(path));

    // 간단하게 디렉터리와 파일의 순서를 정하기 위한 벡터들
    auto vec_string_directories = std::vector<std::string>();
    auto vec_string_files = std::vector<std::string>();
    
    for (const auto& dirEntry : iter_directory) {
        auto pathString = dirEntry.path().string();
        if (pathString.find(".git") != pathString.npos) {
            // ignore .git
            continue;
        }

        auto hash_hex = std::string();
        uint8_t* hash = new uint8_t[SHA_DIGEST_LENGTH];
        if (dirEntry.is_directory()) {

            if (auto res = write_tree(pathString, hash_hex, hash); res == EXIT_FAILURE) {
                return EXIT_FAILURE;
            }

            std::string strDirectory = "40000 " + dirEntry.path().filename().string() + '\0';
            strDirectory.append(reinterpret_cast<char*>(hash), SHA_DIGEST_LENGTH);
            vec_string_directories.push_back(strDirectory);
        }
        else {
            if (auto res = write_blob(pathString, hash_hex, hash); res == EXIT_FAILURE) {
                return EXIT_FAILURE;
            }

            std::string strFile = "100644 " + dirEntry.path().filename().string() + '\0';
            strFile.append(reinterpret_cast<char*>(hash), SHA_DIGEST_LENGTH);
            vec_string_files.push_back(strFile);
        }
    }

    // directory_iterator 는 이름 오름차순 정렬을 보장해주지 않았다.
    std::sort(vec_string_directories.begin(), vec_string_directories.end());
    std::sort(vec_string_files.begin(), vec_string_files.end());

    // 디렉터리 > 파일 순으로 최종 컨텐츠에 스트링을 더한다.
    for (const auto& strEntry : vec_string_directories)
    {
        content_data.append(strEntry);
    }

    for (const auto& strEntry : vec_string_files)
    {
        content_data.append(strEntry);
    }

    // 압축 전의 최종 컨텐츠의 사이즈가 트리의 사이즈 정보가 된다.
    int treeSize = content_data.size();
    std::string tree_object = "tree " + std::to_string(treeSize) + '\0' + content_data;
    std::string compressed_object = std::string();
    if (auto res = compressData(compressed_object, tree_object); res == EXIT_FAILURE) {
        return EXIT_FAILURE;
    }

	get_hash(tree_object, outHash);
	outHash_hex = hexStr(outHash, SHA_DIGEST_LENGTH);

	const auto tree_hash_hex = std::string_view(outHash_hex);
	const auto tree_dir = tree_hash_hex.substr(0, 2);
	const auto tree_name = tree_hash_hex.substr(2);

    // write tree file
    std::filesystem::path tree_dirPath = std::filesystem::path(".git/objects") / tree_dir;
    std::filesystem::create_directory(tree_dirPath);
    std::ofstream treeFile(tree_dirPath / tree_name);

    if (treeFile.is_open())
    {
        treeFile << compressed_object;
        treeFile.close();
    }
    else
    {
        std::cerr << "Failed to create tree file. \n";
        return EXIT_FAILURE;
    }


    return EXIT_SUCCESS;
}