Support undoing staged changes

[arxanas]

Motivation

git undo can't undo everything, but we can get close. As of c3f4f3c, we can run arbitrary code after a git command (assuming that the user has set up an alias). So it should be possible to track staged changes after each git command, and allow them to be undone as well.

The end goal is that we should be able to drop back into a merge conflict resolution (as part of a rebase or merge) and continue from there, if we decided that we did it wrong previously. That is, you should be able to run git undo, and then run git status and see a file marked as "both modified" which needs to be resolved. Then you should be able to run e.g. git rebase --continue to resolve the conflict and continue rebasing.

Background

Git's object database is a content-addressed key-value store. The key is the hash of the content, and the value can be one of these types of objects:

• Blob: a chunk of binary data (e.g. a file).
• Tree: a mapping from path to object, representing a hierarchical structure. The objects can be blobs, trees, or sometimes commits (in the case of Git submodules). The objects may also be annotated with some restricted metadata, like the Unix file permissions.
• Commit: the aggregate combination of a tree, commit message, and list of parent commit objects.
• Tag: not relevant here.

The index is an on-disk structure which is used to liaise between the working copy and the repository contents. It contains a sorted list of files (but no directories!), each of which has the following interesting attributes for our purposes:

• The file's last-modified time, used to optimize index refreshes.
• Object ID: the OID for the file (a blob).
• Stage: a value from 0-3. The 0 value corresponds to a regular file, and values 1-3 correspond to the file in a state of merge conflict. See man git-merge for more details. It's possible for the same file path to exist multiple times in the index with different stage values.

Since the index stores the merge stage, it contains more information than can be represented straightforwardly in a tree object, which means that storing snapshots of the index will have to be more clever.

Design

Data

The idea is to store staging events in the event-log database. The important information is Git's index file, plus any auxiliary status files under the .git directory (like the rebase plan) that may be present. Collectively, let us call these files a "stage".

We can reuse Git's object database to store snapshots of the relevant files in the stage. None of these files are tracked by the repository normally.

However, the index file may be too big to copy and store into the object database every time we run a command (tens of megabytes in practice). So instead of storing the entire index, we'll store the parent commit ID, plus the differences from that commit's tree to the current index. Experiments indicate that calculating the diff doesn't take too long (<1s on my maxed-out 2019 Macbook), and we can also optimize by not calculating the diff if the index doesn't appear to have been modified since the most recent stage.

There can only be one stage active for a given worktree at a time.

Logically, a stage which we're persisting has these fields:

• Timestamp (to compare to the index file on disk for optimization).
• Parent commit OID.
• A tree containing:
  • An index file which represents a diff from the parent commit.
  • All the auxiliary files.
  • Any blobs referenced by the index file diff (to keep them live for garbage collection).
• Possibly a handle to the previous stage (temporally-speaking).

There is technically no requirement that the tree be associated with a commit of its own, but the easiest implementation would create a commit for each stage with the logical base commit as its parent. It would then automatically render in the correct place in the smartlog, and we could ensure the stage is kept live by the existing garbage collection integration.

Events

In the event log, we'll store stage events which contain the above fields. The active stage for a given point in time is determined by the most recent stage event. This contains the parent commit plus its diff to be able to recreate the stage.

There is no Git hook which triggers when the index changes. For now, the best we can do is wrap the git command and check the stage after each command invocation, and store an event if it appears to have changed. Note that since the stage contains a reference to the parent commit, then if the checked-out commit changes, we will need to emit another stage event (or derive the changed parent commit after the fact).

It would also be reasonable to use the same kind of event to track both commits and stages.

Undo

The inverse of a stage event is the stage event which preceded it. Unlike all other events at the time of this writing, this inverse event is not determined entirely by a given event's contents; it is sensitive to the events which have happened before it.

To undo to a previous stage, we need to check out to the corresponding commit, and then apply the diff. This means overwriting files in the .git directory. After doing this, git status will show that the working copy files are different from their staged versions. Unless we commit to also tracking unstaged changes (!), we can't restore the working copy files to their old versions. We should either leave them untouched, or update them to their staged versions, or possibly attempt to merge them together.

[arxanas]

A probably-better approach is to avoid additional special cases, and store everything as commits instead. If instead we stored the state of the repository during a conflict as a commit (with the data about which files are in conflict stored out-of-band), then it would be a lot easier to reconcile it into the current event log system. Additionally, it would naturally lend an interface for users to defer a conflict resolution for later, or go back in time to a previous conflict resolution.

Storing conflicts in commits directly is one of the design goals for https://github.com/martinvonz/jj. Now I've come to appreciate the benefits of that approach...

There are some complications, like the question of how we actually re-enter a conflict resolution state when checking out a commit (using the post-checkout hook?). The commit in the commit graph may be confusing for users, since the content doesn't inherently contain the merge conflict data (so what should happen if they try to view it or move it?).

[arxanas]

@martinvonz I understand that Jujutsu updates an internal working copy commit whenever you run a jj command. How is that implemented? With the equivalent of a git status for each jj call? Does that perform well on large repositories? Does Jujutsu have an index or dirstate file on disk which keeps track of the working copy state? When the working copy is automatically committed, does that appear in the operation log, and if so, does that operation have an inverse?

[martinvonz]

Yes, Jujutsu has its own cache of the states of files in the working copy (it's currently naively stored in protobuf file). When you run almost any jj command, a new commit object is created if the working copy has changed. The new commit replaces the previous commit (you can think of it as a successor in the evolution sense). The working copy commit is not any more internal than other commits are, by the way. You can check it out in the backing Git repo, for example (if you have a backing Git repo, of course). If you check out away from a "working copy commit" (I've technically called them "open commits"), the it'll get abandoned (pruned) if it's empty. If you have jj installed, you can run jj concepts working-copy to read a bit more about it (but also feel free to ask further questions here).

I haven't used Jujutsu on very large projects yet. My assumption is that users of very large repos will use something like watchman (which I haven't added support for yet). Then the working copy can get committed by the watchman listener and jj commands can instead ask watchman if there are events that have not yet been processed (I have never used watchman, but I hope that's doable in some way). If nothing needs to be committed, then nothing needs to be done, and e.g. jj diff (if that's what the user ran) just displays the diff of the working copy commit the way it always does.

The committing of the working copy is its own operation in the operation log. As you probably know, all operations record the set of anonymous heads and branches and their targets. They also record the current checkout, i.e. the commit the working copy is at (I plan to make the operations record the checkout in each worktree/share once I add support for multiple worktrees). So when you undo the committing of the working copy, it's like rolling back all the working copy changes since your last jj command (assuming you're undoing the most recent operation). The checkout that's recorded in the operation is the source of truth about which commit should be checked out. The working copy just follows that.

[arxanas]

Thanks for the information. The way that git undo is implemented for now is by attempting to create an inverse event for each event to be undone, the idea being that you could undo operations which didn't just occur. The actual implementation is clunky so far. It might just be better to store a snapshot of all the refs in each event like you do, rather than try to store the change that occurred as the result of the event. I didn't think very much about the design before I implemented it 😅

Do you plan to make it possible to undo certain operations in the past, without restoring the entire repository to a previous state?

I think that in practice, the two main workflows are:

• Undo the last X events, for a small X.
• Restore commit stacks from the past.

I intended to handle the second case with a general-purpose undo for non-immediately-past events, but I think the better workflow would just be to let the user browse the past and select some nodes and then click "restore" (in a hypothetical UI).

[martinvonz]

Do you plan to make it possible to undo certain operations in the past, without restoring the entire repository to a previous state?

That's already implemented. It looks surprisingly similar to how you back out a commit by doing a 3-way merge, it's just that the 3-way merge is done between repo states.

I think that in practice, the two main workflows are:

Agreed, it's rare to want to undo something a few operations back, but it's the same logic jj uses for resolving conflicts between concurrent operations so the code was pretty much there anyway. FWIW, jj has jj op undo for undoing a single operation and jj op restore for restoring the entire repo to an earlier state (so jj op restore is more like git undo, IIUC).

By the way, the logic for resolving changes pulled from a remote is also logically quite similar to the logic for handling concurrent operations and undo. It's kind of like applying the repo-level diff between the previous remote state and the current remote state. It took me a long time to realize you could think of it that way. And to code it that way.

[arxanas]

According to Google trends, it seems like undoing the operation of git add is a very common question. I think this means two things:

• It's definitely worthwhile to be able to undo staged changes.
• The staging area is a conceptual mistake. If possible, we should guide new Git users to use different, easier methods of making partial commits.