Support equivalent of GIT_SORT_REVERSE | GIT_SORT_TOPOLOGICAL in rev walk

[vlad-ivanov-name]

Summary 💡

There's gix_traverse::commit::Sorting::Topological, but I haven't found a way to reverse the traversal

Motivation 🔦

Used during filtering in https://github.com/josh-project/josh/

[Byron]

After having looked at the source code of libgit2 it became clear that they aren't doing anything smart to perform this impossible feat. After all, commits are linked to their ancestors, but not to their descendants which means they do the equivalent of id.ancestors().all().collect::<Vec<_>>().into_iter().rev().

As Rust has combinators for this I believe these should be used instead to not hide potentially considerable latency and memory consumption behind a seemingly innocent flag. Thanks for your understanding.

[vlad-ivanov-name]

Good point - thank you 🙏

[nrdxp]

would it be possible to implement this more performantly by implementing DoubleEndedIterator for a Walk?

My use-case is that I want to quickly calculate the origin commit (the oldest commit with no parents) as quickly as possible. If the iterator over a Walk sorted by commit time were efficiently reversible, this would essential be O(1) instead of O(n) as it is now to call last()

[nrdxp]

I believe with #1610 this would now be possible, without hurting performance, although its not for Topological searches, it is extremely fast when looking for ancient commits compared to the NewestFirst variants.

[Byron]

Thanks for making this happen! I wasn't aware that simply traversing by oldest first can mean such a huge saving, and is definitely something that should be made available.
I may also have been wrong about my initial assessment which lead to closing the issue, so reopening.