Commit ancestor traversal sorted by commit time

[Byron]

The Ancestors iterator git-traverse should learn to dispatch Commits sorted by their date.

This capability is needed in many applications, which currently have to sort after storing all commits in a Vec. Ideally this can be done on the fly, to the extend possible.

[Byron]

@oknozor Maybe this issue would be something for you. It's involving standard tests and Rust, as opposed to issue 269 which I am getting done myself why the memory is fresh.

It's mainly cleanup which certainly is a thankless first issue with lots of implicit complexity, most of which isn't mentioned in the issue itself.

[oknozor]

Just to be sure I understand what you want here, let's take a simple example :

# Commit in year 2000
git checkout -q -b main
GIT_COMMITTER_DATE="2000-01-02 00:00:00 +0000" git commit -q --allow-empty -m c1

# Commit in year 2001
git checkout -q -b branch1
GIT_COMMITTER_DATE="2001-01-02 00:00:00 +0000" git commit -q --allow-empty -m b1c1

# Commit in year 2000
git checkout -q main
GIT_COMMITTER_DATE="2000-01-02 00:00:00 +0000" git commit -q --allow-empty -m c2

# Commit from branch1 made in 2001 merged in 2002
GIT_COMMITTER_DATE="2002-01-02 00:00:00 +0000" git merge branch1 -m m1b1

This would produce the following git log :

❯ git log --date=format:'%Y' --pretty=format:'%cd %H% -%d %s' --abbrev-commit --graph  
*   2002 288e509293165cb5630d08f4185bdf2445bf6170- (HEAD -> main) m1b1
|\  
| * 2001 bcb05040a6925f2ff5e10d3ae1f9264f2e8c43ac- (branch1) b1c1
* | 2000 9902e3c3e8f0c569b4ab295ddf473e6de763e1e7- c2
|/  
* 2000 134385f6d781b7e97062102c6a483440bfda2a03- c1

Currently they are not produced in the correct order using the Ancestors iterator implementation :

# c2 and b1c1 are inverted
288e509293165cb5630d08f4185bdf2445bf6170 (m1b1)
9902e3c3e8f0c569b4ab295ddf473e6de763e1e7 (c2) 
bcb05040a6925f2ff5e10d3ae1f9264f2e8c43ac (b1c1) 
134385f6d781b7e97062102c6a483440bfda2a03 (c1)

This raises a few questions :

• c2 and b1c1 should be inverted. I assume we would need to look at the committer date and fall back to the author date
  to sort them ?
• Should this be the default behavior or shall it be exposed in Ancestors, or via dedicated iterator ?
• I am not sure how this could be implemented in the current Iterator implementation. Wouldn't we need to lookup every parent on every call to Iterator::next to figure out the order, I am quite sure that's not what you have in mind. Maybe this should be done with the make_iter_lookup macro in git-odb ?

I will need some guidance to get started :)

[Byron]

A great analysis! I particularly love that it already contains a test script suitable to be dropped into the .sh file for use in unit tests.

Regarding the questions:

c2 and b1c1 should be inverted. I assume we would need to look at the committer date and fall back to the author date
to sort them ?

git2 seems to use the commit date exclusively, and I would go with the same. Since it is always set, there shouldn't be a need to fall back to the author date. The latter is something git2 doesn't seem to provide either, so I think it's ok to not provide such an option either.

Should this be the default behavior or shall it be exposed in Ancestors, or via dedicated iterator ?

I hoped it could implemented in the Ancestors iterator. It already has a way to be configured with the vaguely named mode() method. I can imagine there to be a new sorting(…) method which takes an enum to provide a choice between Topological and CommitDate sorting, with Topological being the default as its fastest, similar to what git2 does.

I am not sure how this could be implemented in the current Iterator implementation. Wouldn't we need to lookup every parent on every call to Iterator::next to figure out the order, I am quite sure that's not what you have in mind. Maybe this should be done with the make_iter_lookup macro in git-odb

It sounds expensive, but can certainly be implemented so that there is no unnecessary lookups either when limiting the sorting by date to the available parent commits only. Thus the sorting won't be 'total', but when at a branch/fork it will be able to correctly order the parent commits.

It looks like git can do it in a single iterator implementation, so I think our implementation should be able to do the same - do what you must.

Lastly, object lookup performance is always the bottleneck here and I am seeing about 150k commits per second. With an object cache, which can easily be configured in the actual find(…) implementation, so the cost for duplicate object lookups will probably get to be very small.

I will need some guidance to get started :)

My recommendation is to put down a test first starting with the one you already provided here. From there it should be easy to find a decent API to configure sorting by commit date on an iterator and validate it against a manually sorted list, so the following is true:

topo_walk | collect | sort_by_commit_date | reverse == topo_walk_sorted(by_commit_date) | collect

As I am very prone to miss things, please keep asking if anything else comes up or if there is ambiguity. It's usually a first time for me implementing anything in git, so there are many iterations until it finally feels right. I also learned it's helpful to look at git itself for guidance to benefit from the decade of experience buried in heaps of C.