Add topological sorting

[Osse]

Background

TL;DR: Wanted to reimplement own Git script as a Rust program with gitoxide but need proper topological sorting.

I use this script a lot in my workflow. On Windows with MSYS2 it's very slow. I wanted to learn more Rust (which by now I feel I can say I know) and also found gitoxide. Match made in heaven. So I set about implementing a git_blame. (Yes, before The Big Rename... When I started gitoxide didn't have integrated diffing... 😄)

Things happened in life. Next time I picked it up gitoxide was very different, so I could get started right on the blame path.

Then other things happened in life... Eventually I managed to write a very crude blame implementation that works surprisingly well for what it is. But after a while I hit a road block, and eventually figured out that the reason was that the revisions I got back from Ancestors appear in a different order. So I switched gears and started writingblatantly copying topological sorting from Git.

As noted several places (and just above) the current Ancestors does not do the exact same thing as Git itself does. Implementing git-like topological sorting would benefit gitoxide, making it easier to implement finding merge bases and enable several proposed oxidized utilities.

Implementation

My implementation is very much based on the existing Git implementation introduced in b45424181e as well as improvements done since then. Function names are kept as much as possible (even though I don't always agree with them). In short it is a three stage process that aims to reduce the amount of traversal needed before the first result can be output.

The implementation is currently developed on as a separate crate. I tried several times to integrate this sorting into the current Ancestors as a separate sorting type but failed. It was easier to get started with a clean slate. Given the amount of state the topological walk keeps it is perhaps best to keep it separate from the existing traversal (?).

My current goal is to make topo.rs a module next to gix_traverse::commit. For testing purposes I have "merged" my code into gitoxide to be able to easier align types and general style. (Again, only for testing purposes, I literally made a symlink from gitoxide to my topo.rs to not have to update code two places. You can see it here). It compiles just fine :) But that is why my code has some weird feature gates in it.

Issues

This is not PR-ready. Several issues need to be ironed out. Here are a few of them:

Tests

My own repo has a bunch of tests that compare my walk to the output of git rev-parse. However, I have literally embedded a separate commit history into my repo (which admittedly works quite well). Enhancing TraversalAssertion (or making a similar thing) would be needed.

Abstraction level

I feel my implementation (bugs/issues notwithstanding) sort of falls in between gix_traverse::commit::Ancestors and gix::revision::Walk. It would be nice to split it in two like the existing walk, but I don't know exactly where to draw the line. Currently gix_traverse adds a dependency on gix-revision, which can easily be avoided. Also, regardless of where and whether to split, there is currently no way to access this code from gix directly. But it compiles!

BTW I have started writing some docs, but they aren't hosted anywhere at the moment.

Understanding

I cannot honestly say I fully understand how it works... I emailed the original author with some questions, but haven't been graced with a reply. It's been a couple of months by now, so I doubt I will ever receive one. But I learned a lot by thoroughly reading the email thread in which it was first added to git and relevant commit messages.

One interesting thing is that Git refuses to use this algorithm unless it has at least some generation numbers available. If it doesn't then it falls back to the old method of walking the entire history and then calculating indegrees backwards (which is also what libgit2 does). But my implementation works without any generation numbers at all, and I believe Git's own does too (I recall recompiling Git to get rid of the restriction and test this). Though I can't prove it what I think happens is that in absence of generation numbers the first walk ("explore") degenerates into a full walk making it essentially the same as the other implementation.

Next steps?

Development has stagnated a bit before and during the holidays. I need a fresh perspective on things... First off: does this seem like a decent foundation to build on to get topological sorting into gitoxide? If so, would it make sense to make a PR just to make it easier to discuss the particulars of the code?

[Byron]

Thanks so much for the writeup and for implementing a git-style blame!

The implementation is currently developed on as a separate crate. I tried several times to integrate this sorting into the current Ancestors as a separate sorting type but failed. It was easier to get started with a clean slate. Given the amount of state the topological walk keeps it is perhaps best to keep it separate from the existing traversal (?)

I agree, and think having a tested and working version first would pave the way for further integration, however that will be done then.

Tests

My own repo has a bunch of tests that compare my walk to the output of git rev-parse. However, I have literally embedded a separate commit history into my repo (which admittedly works quite well). Enhancing TraversalAssertion (or making a similar thing) would be needed.

With gix-testtools it's usually straightforward to build even complex repositories by script, and I think that should be doable here as well.

Understanding

One interesting thing is that Git refuses to use this algorithm unless it has at least some generation numbers available. If it doesn't then it falls back to the old method of walking the entire history and then calculating indegrees backwards (which is also what libgit2 does). But my implementation works without any generation numbers at all, and I believe Git's own does too (I recall recompiling Git to get rid of the restriction and test this). Though I can't prove it what I think happens is that in absence of generation numbers the first walk ("explore") degenerates into a full walk making it essentially the same as the other implementation.

This seems to be a complex algoriithm, but maybe it can use the commitgraph if present just like gix-traverse does, for max-performance. Of course, correctness would be more important at first.

Next steps?

Yes, a PR would be great for sure. My way of doing things will be to get hands-on very fast, maybe in an attempt to integrate it, and that can happen as soon as there are some tests.

So maybe that PR would start out as code-dump, from there tests can be ported, and then one can see how the real topo-sort would integrate into gitoxide.

Thanks again, a great read of an awesome feature! (I wasn't even aware the current topo-sort isn't the real one, so I guess I don't understand it either 😅.)

[Osse]

Thanks! I'm excited that you're excited! It's already been one and a half weeks since I posted this... Time goes very fast these days and it's far from every day I'm able to work on this. Just letting you know it's not abandoned.

I have made some progress. I have made a copy of TraversalAssertion and suited it to my needs, made a script to produce a repo (might want to refactor to share some code there...) But in the process I discovered a mismatch in order between my code and git so I need to track that down. So it'll be a while before I have anything PR-ready.

[Osse]

(I wasn't even aware the current topo-sort isn't the real one, so I guess I don't understand it either 😅.)

The particular thing that tripped up my blame code is the following cute sentence in man git-log/git rev-list: "Show no parents before all of its children are shown". Currently Ancestors does not guarantee this.

[Byron]

It's great to hear you found that mismatch and made it reproducible. Without baseline tests (i.e. comparisons to Git) one can never be sure, nor can these algorithms be protected from regression

The particular thing that tripped up my blame code is the following cute sentence in man git-log/git rev-list: "Show no parents before all of its children are shown". Currently Ancestors does not guarantee this.

That's definitely true, it doesn't do any queuing.

I also wanted to make @epage aware of your work as he wrote git-dive, based on git2 but with a lot of custom code related to diffing. Maybe git2 already does a correct topological traversal, maybe it's worth a look as well.

[Osse]

Oh, cool! Hadn't heard of git-dive before.

git2 has topolocal sorting, but it works the same way as the old topolocal sort in git itself, which means that the whole history has to be traversed (twice I believe) before anything more can be done. The main selling point of the "new" topological sort is that, by leveraging gen numbers, a topologically correct sorting can be guaranted earlier and so iteration can start sooner. Makes most sense for iteractive programs, of course.

(Also, I don't think I was aware Rust bindings for git2 existed when I started going down this rabbit hole, heh).

[Byron]

git2 has topolocal sorting, but it works the same way as the old topolocal sort in git itself, which means that the whole history has to be traversed (twice I believe) before anything more can be done. The main selling point of the "new" topological sort is that, by leveraging gen numbers, a topologically correct sorting can be guaranted earlier and so iteration can start sooner. Makes most sense for iteractive programs, of course.

That's interesting! It seems like the new topo-sort is dependent on the commitgraph caches being present. With that said, is there a fallback for when there is no commitgraph? It seems that's what one would have to do - traverse at least once to get the connectivity information, then traverse the in-memory graph. Maybe with the right abstraction, the algorithm can remain the same, while the source of the graph can be different: either commitgraph cache, or the in-memory cache.

For gitoxide, it definitely should be able to work without a commitgraph. Thinking about it, portions of the graph maybe cached in the commitgraph, but more recent ones are not. The current algorithm takes that into account I believe and can use the commitgraph when, and where, it is available.

(Also, I don't think I was aware Rust bindings for git2 existed when I started going down this rabbit hole, heh).

Probably you mean libgit2, as git2 is the crate producing these bindings. I am just saying this in case you mean what you write exactly, in which case I don't think I understand.