Git Concepts

It would be helpful to be familiar with Git concepts before you start working on this assignment. You can refer to the official guide from Git or any Git introduction online. But here we provide a brief introduction to essential concepts.

A repository is the database of a version control system. A repository tracks a file if it maintains the version of the file. The tracked files of the repository are the files that are tracked by the repository. Untracked files are the files that are not maintained by the repository.

A commit records a snapshot, or the state of the repository. Each commit therefore records the content of the tracked files of the repository when the commit was made. Initially, the repository is empty and hence there exists an initial commit that tracks no files.

Files can be changed in three ways: a new file is added, the content of an existing file is modified, and a file is deleted. To record changes to the repository, the changes are staged: For adding a new file or modifying an existing file, the file is added to the staging area, where the current content is saved. Bear in mind that the staging area only contains the version of the file when it was staged. If a file is modified after staging, the changes are not recorded in the repository unless the file is staged again. For deleting a file, it is removed from the tracked files.

When a new commit is made, only the staged changes are recorded. For other tracked files, they inherit from the previous commit. The previous commit becomes the parent commit of the new commit. As a result, the repository maintains a history of commits where files can be restored from, which is referred as checkout.

A sequence of commits is referred as a branch. A branch is associated with a head commit. The commit sequence of the branch is obtained by following the parent commits starting from the head commit of the branch. A branch can be checked out. This restores all files from the head commit of that branch and change the tracked files to be those tracked by the head commit as well.

The history of changes recorded by different branches can be merged together. This is essential in software development: Software developers work on the project by committing to their own branch. Ultimately, they would merge their work into the master branch which has the combined product of the developers.

File Fingerprinting

To support versioning, we need an efficient way to determine whether two versions are different. In other words, we wish to generate "fingerprints" for files such that we can check the fingerprints to determine whether two file versions are different.

To achieve this, we compute the SHA-1 value of file contents. SHA-1 is a cryptographic hash function that produces a hash value with 160 bits. Usually, we represent the hash values using 40-digit hex strings (since a hex digit represents 4-bit binary value):

                  SHA-1 for "Gitlite": 4ed6b233fe07f0b956e3460e9774f7bfd25d5b7c
                  SHA-1 for "gitlite": ddf639cf894badea22b7b7370dc677dedd404ff7
                

Cryptographic hash functions have the property that it is difficult to generate two inputs that have the same hash value. So we can say that given two file versions, the probability that their hash values are equal is one divided by two to the power of 160, which is negligible. Thus, we can simply check whether two hex strings are the same to determine whether two files versions are identical.

A third-party library, TinySHA1, is utilized to compute SHA-1 values. You don't need to understand and use this library as helper functions have been implemented to use this library (See Compilation to see how we can compile Gitlite with external libraries).

Storing Persistent Data

Gitlite requires some data structures representing the state of the repository to be maintained persistently across different executions of Gitlite. For example, one may use Gitlite to make a commit. When he runs Gitlite the next time, the commit should not be lost.

To achieve this, Gitlite maintains a .gitlite directory which stores the data structures of Gitlite (See Appendix for the structure of the .gitlite directory). Helper functions have been implemented to perform all filesystem operations which use the filesystem feature from C++17. A third-party library, cereal is used for serializing objects upon filesystem operations (See Compilation to see the compilation requirements of Gitlite).

Differences with Git

Since Gitlite is a simplified version of Git, there exists many subtle difference with Git. These will be mentioned when the Gitlite commands to implemented are described. If you are a sophisticated Git user, pay attention to these differences and make sure you implement the expected behavior of Gitlite.

Data Structure

The following data data structures are defined in Commit.h and are essential in Gitlite.

• Blob stands for Binary Large Object. We use Blob object as the common data structure to represent files and branches.

  
                        struct Blob {
                            string name;
  
                            string ref;
  
                            Commit *commit = nullptr;
  
                            Blob *prev = nullptr, *next = nullptr;
                        };
                      

  • When it represents a file, name stores the filename, ref stores the SHA-1 hash value in hex string. This hash value is used by the wrapper functions to refer to the saved copy of the file in the repository (See Appendix for the directory structure of .gitlite). commit is unused.
  • When it represents a branch, name stores the name of the branch, commit points to the head commit of the branch. ref is unused. Blob objects do not own commits, so no need to free the commit when freeing a Blob.
  • prev and next are pointers to the previous and next element in the linked list.
• List is a circular linked list with sentinel node of Blob objects. Implementation of linked list operations is the task of Part 1.

  
                        struct List {
                            Blob *head = nullptr;
                        };
                      

  • All Blob objects in a linked list are always either represents a file or a branch, but not both.
• Commit objects are abstractions of commits.

  
                        struct Commit {
                            string message;
  
                            string time;
  
                            string commit_id;
  
                            Commit *parent = nullptr, *second_parent = nullptr;
  
                            List *tracked_files = nullptr;
                        };
                      

  • message is the commit message.
  • time is the time string of when the commit was made.
  • commit_id is the commit id that uniquely identifies the commit. We compute the commit using the SHA-1 hash value of the commit message and time. This is done by a helper function.
  • parent points to the parent commit. It is nullptr only if it is the first commit, referred as the initial commit, of the repository.
  • second_parent points to the second parent commit, which exists only for the commit created after merging two branches. Otherwise, it is nullptr.
  • tracked_files is the linked list of Blob objects representing the files tracked by the repository when this commit was made. Different commits do not share same Blob objects. If a tracked file is identical in two commits, the two Blob objects in each of the commit have the same ref value.
  • Note: Since commit id uses hash value, two different commits with the same message and the same time have the identical commit id. You can assume this never occurs in grading. Also, during testing, make sure you do not use the same commit message for commits that will be taken during a short interval.

init

Initialize a repository

                  void init(Blob *&current_branch,
                            List *&branches,
                            List *&staged_files,
                            List *&tracked_files,
                            Commit *&head_commit);
                

• Usage: gitlite init
• Description:
  1. Initialize the linked lists: branches, staged_files, tracked_files.
  2. Create the initial commit with message initial commit. Set the time string and compute the hash. This commit tracks no files (initialize commit->tracked_files as well) and has no parents.
  3. Create a branch called master and set it as the current branch. Add the initial commit to the branch. Set the head commit of the repository as well.
• Hints:
  • Remember that you have already implemented linked list operations in Part 1. We expect you to use them in Part 2.
  • See Utils.cpp for some useful functions.
  • All output messages in Part 2 are available as constant strings in the top of gitlite.cpp.
• Notes:
  • Parameters are passed by reference. The changes in this function are visible by the wrapper function after this function returns.
  • This function always succeed. When it returns, the wrapper function would add the commit pointed by head_commit to the global list of commits, create a .gitlite directory in the current working directory, and save the newly initialized data structures to this directory.
  • Attempt to initialize in a directory with a .gitlite directory would fail with the message: A Gitlite version-control system already exists in the current directory. This is handled by the wrapper function.
  • The rest of Gitlite commands requires an initialized .gitlite directory. If Gitlite cannot find an initialized .gitlite directory, it would print Not in an initialized Gitlite directory. and terminates immediately. This is handled by the wrapper function.
• Differences from Git:
  • Git does not explicitly create the initial commit.
  • In Git, the name of the first branch is not fixed to master.

add

Add content of a file to the repository

                  bool add(const string &filename,
                           List *staged_files,
                           List *tracked_files,
                           const Commit *head_commit);
                

• Usage: gitlite add [filename]
• Description:
  1. Add content of the file to the repository by saving the content of the file to the currently tracked files of the repository.
  2. Perform one of the following:
     • In most cases, simply save the content of the file to the staging area as well. Return true.
     • If the file is tracked in the head commit of the repository, with the same content as the current file, then remove the file from the staging area (if it is staged). Return false. (This happens when a modified file was added, then restored to original version, and added again. Since the file was restored, it should be removed from the staging area.)
• Hints:
  • tracked_files stores the currently tracked files of the repository and their saved content.
  • head_commit->tracked_files contains the tracked files of the repository and their saved content at the head commit of the repository.
  • See Utils.cpp for some useful helper functions.
  • Remember that you have already implemented linked list operations in Part 1. We expect you to use them in Part 2.
  • Added October 13: You should use list_put() to add files to the list such that the name follows ascending lexicographic order.
• Notes:
  • This is known as staging the file for addition. The file is now staged for addition. Staging an already staged file overwrites previous results.
  • Before this function is called, the wrapper function ensures the file specified by filename exists in the current directory. Otherwise, the wrapper function would report File does not exist.
  • When this function returns, the wrapper function would make filesystem operations to the .gitlite directory to save a copy of the file and update the index for staging area. The saved copies are identified by the hash value, such that only one copy is save for different file versions with the same content.
• Differences from Git:
  • Gitlite only tracks files in the current directory, while Git can track files in sub-directories. So the tracked files in Git forms a tree, while linked list is sufficient to represent tracked files in Gitlite.

commit

Take a snapshot the repository such that it can be restored later

                  bool commit(const string &message,
                              Blob *current_branch,
                              List *staged_files,
                              List *tracked_files,
                              Commit *&head_commit);
                

• Usage: gitlite commit [message]
• Description:
  1. Failure check: If there are no files in the staging area, and no files staged for removal, print No changes added to the commit. and return false.
  2. Create a new commit. Save the message, time and commit id.
  3. Take a snapshot of the repository by copying the tracked files of the repository to the tracked files of this commit. These files become the files that are tracked by this commit.
  4. Add this commit to the current branch and update the head commit of the repository.
  5. Clear the staging area and return true.
• Hints:
  • See Utils.cpp for some useful helper functions.
  • To make a snapshot, should you do shallow copy or deep copy?
  • A file is staged for removal if it is tracked by the head commit of the repository but not currently tracked by the repository. (See remove).
• Notes:
  • The staging area is cleared because a new commit is made. Now there are no files that are changed since the head commit of the repository.
  • For best practices, the commit message should describe the changes introduced in this commit.
  • If this function returns true, the wrapper function would add the commit pointed by head_commit to the global list of commits, and make filesystem operations to the .gitlite directory to write changes to filesystem.

remove

Remove a file from the current working directory and the repository

                  bool remove(const string &filename,
                              List* staged_files,
                              List *tracked_files,
                              const Commit *head_commit);
                

• Usage: gitlite rm [filename]
• Description:
  1. If the file is tracked by the head commit of the repository, then remove it from the currently tracked files of the repository and remove the file from the current working directory (if it exists). The file is staged for removal.
  2. If the file was staged for addition, remove it from the tracked files of the repository and the staging area.
  3. If none of the above is satisfied, print No reason to remove the file. and return false. Otherwise, return true.
• Hints:
  • See restricted_delete(filename) in Utils.cpp for deleting a file from filesystem.
• Notes:
  • This command may remove existing files.
  • If this function returns true, the wrapper function would make filesystem operations to the .gitlite directory to remove index for staging area.

log

Display the log of previous commits

                  void log(const Commit *head_commit);
                

• Usage: gitlite log
• Description:
  1. Starting from the head commit of the repository, display information for each commit backwards until the initial commit, by following the parent commit (ignore second parents).
  2. Display the log in the following format:

  
                          ===
                          commit fd0efd44873699357e2a452ec8f17e79ac965e4c
                          Date: Thu Jul 22 22:23:56 2021
  
                          Another commit message
  
                          ===
                          commit 61db0df36b222c7acc910b2dec40e5461e4041cb
                          Date: Thu Jul 22 22:23:31 2021
  
                          A commit message
  
                          ===
                          commit 0ed4cfc32f3478a10c755c5c8cca980b14c54f17
                          Date: Thu Jul 22 22:22:50 2021
  
                          initial commit
                        

• Hints:
  • See commit_print(commit) in Commit.cpp for displaying information of a commit.
• Notes:

status

Display the status of the repository

                  void status(const Blob *current_branch,
                              const List *branches,
                              const List *staged_files,
                              const List *tracked_files,
                              const List *cwd_files,
                              const Commit *head_commit);
                

• Usage: gitlite status
• Description: Display the status according to the following format: (Example updated October 13)

  
                        === Branches ===
                        another-branch
                        *master
  
                        === Staged Files ===
                        staged_file.txt
  
                        === Removed Files ===
                        gone.txt
  
                        === Modifications Not Staged For Commit ===
                        changed.txt (modified)
                        file1.txt (modified)
                        file2.txt (deleted)
                        file3.txt (modified)
                        file4.txt (deleted)
                        missing.txt (deleted)
  
                        === Untracked Files ===
                        files.untracked
                      

  • Branches: Display the names of all branches. Marks the current branch with *.
  • Staged Files: Display the filenames of all files that are staged for addition.
  • Removed Files: Display the filenames of all files that are staged for removal.
  • Modifications Not Staged For Commit: Display the filenames for the following files. Append (modified) for case 1 and 2. Append (deleted) for case 3 and 4.
    1. Unstaged files that are tracked in the head commit of the repository, but the content recorded in the commit is different with the content in the current working directory (CWD).
    2. Files that were staged for addition, but the content recorded in the staging area is different with the content in CWD.
    3. Files staged for addition but deleted in CWD.
    4. Files not staged for removal but tracked in the head commit of the repository and deleted in CWD.
  • Untracked Files: Files exist in CWD but not currently tracked by the repository.
  • Entries in each group should be listed in ascending lexicographic order. The * of current branch does not count.
• Hints (Updated October 13):
  • cwd_files stores the files located in the currently working directory. Use this to find out untracked files.
  • get_sha1(filename) returns the hash of the file version in CWD.
  • is_file_exists(filename) checks whether a file exists in CWD.
  • A file is staged for removal if it is tracked by the head commit of the repository but not currently tracked by the repository. (See remove).
  • For Modifications Not Staged For Commit, traverse tracked_files to see whether each file matches one of the 4 conditions.
• Notes:
  • The linked list are created by the wrapper function using list_put(). Filenames and branch names follow ascending lexicographic order if list_put() is implemented correctly.

checkout file

Restore a file from a given commit (or the head commit of the repository)

                  bool checkout(const string &filename,
                                Commit *commit);
                

• Usage: gitlite checkout -- [filename] or gitlite checkout [commit_id] -- [filename]
• Description:
  1. Failure check:
     • If commit is nullptr, then the wrapper function cannot find the commit with the commit id. Print No commit with that id exists. and return false.
     • If the file is not tracked by the commit, print File does not exist in that commit. and return false.
  2. Take the version of the file as it exists in the given commit and write the content to the current working directory. Overwrite any existing file.
  3. No need to update the currently tracked files of the repository and the staging area. Return true.
• Hints:
  • See write_file(filename, ref) for writing the content referred by ref to the file in filesystem.
• Notes:
  • This command may overwrite existing files.
  • The wrapper function resolves the given commit id into a commit and pass it to this function. Commit can be abbreviated given that it has unique prefix. For example, 61db0df36b222c7acc910b2dec40e5461e4041cb can be abbreviated as 61db0df or simply 61, if no other commits with that same prefix exist. The shortest abbreviation has 2 characters.
  • The wrapper function passes the head commit of the repository to this function if commit id was not specified in the command.

checkout branch

Switch to a branch

                  bool checkout(const string &branch_name,
                                Blob *&current_branch,
                                const List *branches,
                                List *staged_files,
                                List *tracked_files,
                                const List *cwd_files,
                                Commit *&head_commit);
                

• Usage: gitlite checkout [branch_name]
• Description:
  1. Failure check:
     • If the given branch does not exist, print A branch with that name does not exist. and return false.
     • If the given branch is the current branch, print No need to checkout the current branch. and return false.
     • If there exists untracked files in the current working directory that would be overwritten (see below for the files that would be overwritten), print There is an untracked file in the way; delete it, or add and commit it first. and return false.
  2. Take all files in the head commit of the branch and write the content of them to the current working directory. Overwrite any existing files.
  3. Any files that are tracked in the head commit of the repository but not the head commit of the given branch are deleted.
  4. Set the currently tracked files of the repository to those that are tracked by the head commit of the given branch. Clear the staging area as well.
  5. The given branch becomes the current branch. Also update the head commit of the repository.
  6. Return true.
• Hints:
  • See restricted_delete(filename) for deleting a file from filesystem.
  • See write_file(filename, ref) for writing the content referred by ref to the file in filesystem.
• Notes:
  • This command may overwrite existing files.
  • When this function returns, the wrapper function would make filesystem operations to the .gitlite directory to update the index for staging area and tracked files.

reset

Reset the current state of the repository to a given commit

                  bool reset(Commit *commit,
                             Blob *current_branch,
                             List *staged_files,
                             List *tracked_files,
                             const List *cwd_files,
                             Commit *&head_commit);
                

• Usage: gitlite reset [commit_id]
• Description:
  1. Failure check:
     • If commit is nullptr, then the wrapper cannot find the commit with the commit id. Print No commit with that id exists. and return false.
     • If there exists untracked files in the current working directory that would be overwritten (see below for the files that would be overwritten), print There is an untracked file in the way; delete it, or add and commit it first. and return false.
  2. Take all files in the given commit and write the content of them to the current working directory. Overwrite any existing files.
  3. Any files that are tracked in the head commit of the repository but not by the given commit are deleted.
  4. Updated October 8: Set the currently tracked files of the repository to those that are tracked by the head commit of the given branch given commit. Clear the staging area as well.
  5. The given commit becomes the head commit of the current branch. Also update the head commit of the repository.
  6. Return true.
• Hints:
  • See restricted_delete(filename) for deleting a file from filesystem.
  • See write_file(filename, ref) for writing the content referred by ref to the file in filesystem.
• Notes:
  • This command may overwrite existing files.
  • The wrapper function resolves the given commit id into a commit and pass it to this function.

branch

Create a new branch

                  Blob *branch(const string &branch_name,
                               List *branches,
                               Commit *head_commit);
                

• Usage: gitlite branch [branch_name]
• Description:
  1. Failure check: If a branch with the given name already exists, print A branch with that name already exists. and return nullptr.
  2. The head commit of the repository becomes the head commit of the new branch.
  3. Added October 15: Add the new branch to branches.
  4. Return a pointer to the new branch.
• Notes:
  • The default branch upon initializing the repository is the master branch.
  • No need to checkout the new branch.
  • If this function does not return nullptr, the wrapper function would make filesystem operations to the .gitlite directory to write the branch information.

remove branch

Delete an existing branch

                  bool remove_branch(const string &branch_name,
                                     Blob *current_branch,
                                     List *branches);
                

• Usage: gitlite rm-branch [branch_name]
• Description:
  1. Failure check:
     • If the given branch does not exist, print A branch with that name does not exist. and return false.
     • If trying to remove the current branch, print Cannot remove the current branch. and return false.
  2. Delete the branch from the repository. Do not delete any commits. Updated October 15: Return true.
• Notes:
  • If this function returns true, the wrapper function would make filesystem operations to the .gitlite directory to remove information of the branch.

merge

Join the history of a given branch into the current branch

                  bool merge(const string &branch_name,
                             Blob *&current_branch,
                             List *branches, List *staged_files,
                             List *tracked_files,
                             const List *cwd_files,
                             Commit *&head_commit);
                

• Usage: gitlite merge [branch_name]
• Description:
  1. Failure check:
     • If the given branch does not exist, print A branch with that name does not exist., and return false.
     • If trying to merge the current branch, print Cannot merge a branch with itself. and return false.
     • If there exists uncommitted changes, print You have uncommitted changes. and return false.
  2. Otherwise, proceed to compute the split point of the current branch and the given branch. The split point is a latest common ancestor of the head commit of the current branch and the head commit of the given branch:

     
                               initial commit --- c1 --- c2 --- c3 --- c4 (head of master)
                                                           \
                                                             --- n1 --- n2 (head of new)
                             

     The split point of the master branch and the new branch is the commit c2.
     • The ancestors of a commit are the commits that are reachable by following parent pointers (excluding second parent). In the above example, ancestors of c4 are c3, c2, c1 and the initial commit.
     • The common ancestors of two commits are the commits that are ancestors of both commits. In the above example, the common ancestors of c4 and n2 are c2, c1 and the initial commit.
     • A latest common ancestor is a common ancestor that is not an ancestor of any other common ancestors. In the above example, c2 is the only latest common ancestor. Hence it is the split point of master and new.
     • Since all branches can be traced back to the initial commit, the initial commit must be a common ancestor of any two commits. So there exists at least one latest common ancestor.
     • In some cases, there can be more than one latest common ancestor. But we ignore these cases. We assume there is only one latest common ancestor.
     • Thus, the split point determines the latest common history of two branches.
     • Implement split point computation in the following function in Commit.cpp. This will be graded separately:

       
                                     Commit *get_lca(Commit *c1, Commit *c2);
                                   

       For two given commits c1 and c2, return the latest common ancestor.
     • Bonus (10 points): Also consider second parents in the computation of split point.
  3. If the split point is the head commit of the given branch, then all changes in the given branch exist in the current branch (the current branch is ahead of the given branch). So there is nothing to be done in the current branch. Simply print Given branch is an ancestor of the current branch. and return true.
  4. Updated October 15: Moved from Step 6. Failure check: Traverse cwd_files, if there exists a file that is not tracked in the head commit of the current branch but tracked in the head commit of the given branch, print There is an untracked file in the way; delete it, or add and commit it first. and return false.
  5. If the split point is the head commit of the current branch, then all changes in the current branch exist in the given branch (the given branch is ahead of the current branch). Simply set the state of the repository to the head commit of the given branch (using one command above). If it succeeded, print Current branch fast-forwarded. and return true. If it failed, return false.
  6. Otherwise, the split point is neither the head commit of the current branch and the head commit of the given branch. Their history has diverged, like the above example. We need to incorporate the latest changes from both branches.
  Updated October 15: Moved to Step 4. Failure check: Updated October 12: If there exists untracked files in the current working directory that would be overwritten by the merge (see below for the files that would be overwritten) Traverse cwd_files, if there exists a file that is not tracked in the head commit of the current branch but tracked in the head commit of the given branch, print There is an untracked file in the way; delete it, or add and commit it first. and return false.
  7. Otherwise, proceed to merge the two branches with rules below. A general idea is to incorporate the latest changes from both branches.
     1. Any files that have been modified in the given branch but not modified in the current branch since the split point should be changed to their versions in the given branch.
        • Checkout the files and stage the files for addition.
        • In addition, you need to call stage_content(filename) explicitly to modify the index in the .gitlite directory.
     2. Any files that have been modified in the current branch but not modified in the given branch since the split point should remain unchanged.
     3. Any files that have been modified in both the current branch and the given branch in the same way (both modified with same content or both removed), should remain unchanged.
     4. Any files that were not present at the split point and are present only in the current branch should remained unchanged.
     5. Any files that were not present at the split point and are present only in the given branch should be added with their versions in the given branch.
        • Checkout the files and stage the files for addition.
        • In addition, you need to call stage_content(filename) explicitly to modify the index in the .gitlite directory.
     6. Any files present at the split point, unmodified in the current branch, and absent in the given branch should be staged for removal.
     7. Any files present at the split point, unmodified in the given branch, and absent in the current branch should remain absent.
     8. Any files modified in different ways in the current branch and the given branch are in conflict.
        • A file is modified in different ways if:
          1. It is changed in both branches with different content.
          2. It is changed in one branch but deleted in another branch.
          3. It was absent at the split point but present in both branches with different content.
        • Replace the content of these files in the current working directory by the conflict resolution marker: (See add_conflict_marker(filename, ref) in Utils.cpp)

          
                                            <<<<<<< HEAD
                                            contents of the file in the current branch
                                            =======
                                            contents of the file in the given branch
                                            >>>>>>>
                                          

        • Stage these files for addition.
        • In addition, you need to call stage_content(filename) explicitly to modify the index in the .gitlite directory.
  8. After processing the files, create a merge commit with message Merged [given branch name] into [current branch name]. Added October 15: Use get_merge_commit_message() to compose this message.
     • The first parent of the merge commit is the head commit of the current branch.
     • The second parent of the merge commit is the head commit of the given branch.
  9. If a conflict was ever encountered, print Encountered a merge conflict. (once is enough)
  10. Return true.
  11. If a commit error occurred, just print the error, ignore it and still return true.
• Hints:
  • Added October 15: For step 7, compare tracked_files of these three commits: split point, head commit of the current branch, head commit of the given branch.
• Notes:
  • In the above example, suppose we merge new into master which results the merge commit m1. The set of commit becomes:

    
                              initial commit --- c1 --- c2 --- c3 --- c4 --- m1 (head of master)
                                                          \                 /
                                                            --- n1 ------ n2 (head of new)
                            

    The split point (excluding second parents) of the master branch and the new branch is c2.
    The split point (including second parents) of the master branch and the new branch is n2. This is the behavior of Git.
  • This command may overwrite existing files.
  • Updated October 9: for add_conflict_marker(),
    • If the file is deleted in the given branch, you provide an empty for ref, like this would do: add_conflict_marker(filename, string()).
    • If the file is deleted in the current branch, you can still use the filename. If the file is not found in the CWD, then add_conflict_marker() would use an empty line for the current branch version.

Running Gitlite

After successful compilation, you would find an executable file named gitlite (or gitlite.exe for Windows) in the current directory.

Gitlite process commands by reading the command line arguments argv that are passed to main(). When no command line arguments are given, argc is 1 and Gitlite terminates immediately. You may want to modify the if branch when argc == 1 in main() to test the linked list implementation or something else.

Otherwise, Gitlite parses argv and dispatch the command by calling the wrapper function for the function you have implemented in Part 2.

To run a Gitlite command, enter ./gitlite (or .\gitlite.exe for Windows) followed by the Gitlite command and optional arguments, separated by spaces. For arguments with spaces, wrap them in a pair of quotes:

                  # For macOS and Linux
                  $ ./gitlite init
                  $ ./gitlite commit "a commit message with spaces"

                  # For Windows
                  $ .\gitlite.exe init
                  $ .\gitlite.exe commit "a commit message with spaces"
                

Setting Up a Dedicated Testing Directory

It is highly recommended to setup a dedicated directory for testing Gitlite.

Create a directory, say, testing:

                  pa2/
                  ├── testing/
                  ├── Commit.cpp*
                  ├── gitlite.cpp*
                  ├── gitlite
                  └── ...
                

Then, change the working directory to testing. If you are using VSCode, right click on testing in the directory structure that appears on the left, click "Open in Integrated Terminal". Run Gitlite, which is located in the parent directory, in the following way:

                  # For macOS and Linux
                  $ ../gitlite

                  # For Windows
                  > ..\gitlite.exe
                

Now you can place files in testing and run Gitlite commands to test it:

                  pa2/
                  ├── testing/
                  │   ├── .gitlite/
                  │   ├── file1.txt
                  │   ├── file2.txt
                  │   ├── file3.txt
                  │   └── ...
                  ├── Commit.cpp*
                  ├── gitlite.cpp*
                  ├── gitlite
                  └── ...
                

                  # For macOS and Linux
                  $ ../gitlite init
                  $ ../gitlite add file1.txt
                  $ ../gitlite status
                  $ ../gitlite commit "some message"
                  $ ../gitlite log

                  # For Windows
                  > ..\gitlite.exe init
                  > ..\gitlite.exe add file1.txt
                  > ..\gitlite.exe status
                  > ..\gitlite.exe commit "some message"
                  > ..\gitlite.exe log
                

If you want to reset Gitlite, remove the .gitlite directory and run gitlite init again.

You may want to setup shell alias to ease your testing.

Extra Commands

Two commands have been implemented to facilitate debugging and testing:

• gitlite find [commit message]
  • Print the commit id of the commits with the given message.
• gitlite global-log
  • Display the log of all commits.

Automated Testing Environment

In the skeleton files, there is a directory named auto-testing. This is the environment for the automated testing module. It consists of two directories:

• src: Stores all files accessible by the automated testing module. Depending on the running test case, files in this directory would be copied to or compared with the ones in auto-testing.
• tests: Stores all test cases files (with .in file extension) and optional include files (for example definitions.inc) that are used in test cases.

                  pa2/
                  ├── auto-testing/
                  │   ├── src/
                  │   │   ├── akari.c
                  │   │   ├── img.png
                  │   │   ├── text1.txt
                  │   │   └── text2.txt
                  │   └── tests/
                  │       ├── basic-checkout.in
                  │       ├── basic-operations.in
                  │       ├── basic-status.in
                  │       ├── definitions.inc
                  │       └── init.in
                  ├── Commit.cpp*
                  ├── gitlite.cpp*
                  ├── gitlite
                  └── ...
                

To run a test case, make sure you first change the working directory to auto-testing, then run the following command:

                  $ ../gitlite -t [path]
                

• If the path points to a single file, then the test case will be run. For example:

  
                        $ ../gitlite -t tests/init.in
                      

  init.in will be run.
• If the path is a directory, then all test cases (with .in extension) will be run. For example:

  
                        $ ../gitlite -t tests
                      

  All test cases (with .in extension) in tests will be run.

A test case passes if all output matches the expected output. You would see the following message:

                  Running test: tests/init.in
                  Test PASSED
                

Otherwise, the test case fails and you would see the output and the expected output. The differences are highlighted in the following example:

                  Running test: tests/init.in
                  Wrong output for command: log
                  Expected:
                  ===
                  commit ([a-f0-9]+)[ \t]*\n(?:Merge:\s+[0-9a-f]{7}\s+[0-9a-f]{7}[ ]*\n)?Date: \w\w\w \w\w\w  ?\d+ \d\d:\d\d:\d\d \d\d\d\d

                  the initial commit


                  Actual:
                  ===
                  commit a22b278a25b176ab6da1c40eb1b26e638e54bcf9
                  Date: Fri Oct  1 20:07:59 2021

                  initial commit


                  Test FAILED
                

• Regular expression is used to match variable text, such as the commit id a22b... and the date. You would see the regular expression ([a-f0-9]+)... in the expected output. This is normal.
• To see more verbose output when testing, use the following command:

  
                        $ ../gitlite -tv [path]
                      

Test Case Format

Here are the set of statements avaliable to use in test cases. All paths are interpreted relative to the current working directory

                  I FILE
                        Include a file. Replace this statement with the contents of FILE.

                  + NAME F
                        Copy the contents of src/F into a file named NAME.

                  - NAME
                        Delete the file named NAME.

                  > COMMAND ARGUMENTS
                  LINE1
                  LINE2
                  ...
                  <<<
                        Run Gitlite with COMMAND ARGUMENTS as its parameters.
                        Compare its output with LINE1, LINE2, etc.,
                        report error if any discrepancy is found.
                        The end of output is denoted by the <<< delimiter.

                  = NAME F
                        Check whether the file named NAME is identical to src/F, and report an
                        error if it does not.

                  * NAME
                        Check whether the file NAME does not exist, and report an error if it
                        does exist.

                  E NAME
                        Check whether the file or directory named NAME exists, and report an error if it
                        does not.

                  D VAR "VALUE"
                        Define the variable VAR to have the literal value VALUE.
                        The variable can be used by ${VAR}.
                

• Here is an example:

  
                        I tests/definitions.inc         # include provided definitions in ./tests/definitions.inc
                        > init                          # run init command
                        <<<                             # no expected output for init command
                        + sample.txt sample_src.txt     # copy ./src/sample_src.txt to ./sample.txt
                        > add sample.txt                # run add command
                        <<<                             # no expected output for add command
                        > commit "add sample"
                        <<<
                        > log          # run log command
                        ===            # beginning of expected output of log command
                        ${COMMIT_HEAD} # ${COMMIT_HEAD} will be replaced by the value of variable COMMIT_HEAD
                        add sample
  
                        ===
                        ${COMMIT_HEAD}
                        initial commit
  
                        <<<            # end of expected output of log command
                      

  • The first line will be replaced with the contents in definitions.inc, which contains some useful variable definitions of regular expressions:
    • DATE matches time strings in commit log. For example,

      Date: Wed Oct 16 23:26:06 2021

    • COMMIT_HEAD matches commit log headers, including the date string. For example:

      
                                    commit cf992c00717703ae7c23e799c01e0c3467b2305e
                                    Date: Wed Oct  6 23:26:06 2021
                                  

      The commit id (cf992c00...) can be captured and reused as variables. ${1} would be defined as the first commit id that appears in the output, ${2} as the second commit id, and so on. This is useful for testing commands that requires commit ids. The results are available until the next command (which would discard all previous ${n}). See below for an example.
    • ARBLINE matches an arbitrary line (may be empty).
    • ARBLINES matches any number of arbitrary lines (including no lines).
  • For example, the following text would match the expected output of the log command (lines 10-17):

    
                              ===
                              commit cf992c00717703ae7c23e799c01e0c3467b2305e
                              Date: Wed Oct  6 23:26:06 2021
    
                              add sample
    
                              ===
                              commit 3ee35c73c836a209ee0c4e3f4655431016a9163f
                              Date: Wed Oct  6 23:24:58 2021
    
                              initial commit
    
                            

  • You are not required to understand regular expressions to understand test cases. But you can learn more about them and test them here.
• Here is another example:

  
                        ...                              # previous contents omitted
                        > log
                        ===
                        ${COMMIT_HEAD}                   # first commit id in the output, saved to ${1}
                        add sample
  
                        ===
                        ${COMMIT_HEAD}                   # second commit id in the output, saved to ${2}
                        initial commit
  
                        <<<
                        D c2 "${1}"                      # c2 is the commit id of the commit "add sample"
                        D c1 "${2}"                      # c1 is the commit id of the initial commit
                        > checkout ${c2} -- sample.txt   # checkout sample.txt from the initial commit
                        <<<
                        > status
                        === Branches ===
                        \*master                         # escape '*'
  
                        === Staged Files ===
  
                        === Removed Files ===
  
                        === Modifications Not Staged For Commit ===
                        something_modified.txt \(modified\)    # escape '(' and ')'
  
                        === Untracked Files ===
                        ${ARBLINES}
                        <<<
                      

  • You need to escape the following characters: *, ( and ), by adding \ before them, since they are reserved characters in regular expressions.