Ytukyg

I have a set of commit SHA1s, in no particular order. I would like to pipe this set to a command, and have those commits returned in topological order.

Here's one way of doing this:

git rev-list --all --topo-order | grep --file SET_OF_SHA1S

As you can imagine, this is a very slow way of doing it, as git rev-list is having to print out all of the commit SHA1s, not just the ones in my set.

Is there a better and faster way to do this?

Use case:

My test framework tests certain Git commits and stores the result in a database. I'm writing a web page that summarises these results, and it would be nice to display the results in order. Sorting by commit date is not ideal as some rebased commits will have exactly the same commit date.

Here's one way of speeding it up:

git rev-list --topo-order $(cat SET_OF_SHA1S) 

   | grep --file SET_OF_SHA1S --max-count $(wc -l SET_OF_SHA1S)

Optimisations:

• Only ask rev-list to list all commits reachable from your set of SHA1s.


• As soon as rev-list prints enough commits that include the set of SHA1s you're interested in, tell grep to stop grepping using the --max-count parameter. grep will in turn close its input, and rev-list will stop needlessly printing out further SHA1s.

You can use --no-walk to prevent git from dumping any SHA-1s other than the ones you supply, and use --topo-order to force the correct order. As Mort pointed out in a comment, this does not work. The git documentation acquired new text noting (indirectly) this problem, as of git version 2.4. (I consider this a bug in git rev-list, which should load enough of the commit graph to do the topological sort, then output just the user-specified revision IDs, in the correct order.)

My original script (left in here) therefore also does not work. It can be made to work by removing the --no-walk from the step that generates temporary file $TF2, then using the contents of $TF1 to extract and print the "interesting" revisions from their $TF2 (sorted) order.

This is more or less what Flimm's own answer does.

[original answer, with flawed script, below]

I'm not sure exactly what I was doing with this code, but long ago, I wrote a script to check whether arguments supplied were in topo order:

#! /bin/sh

#

# check a list of IDs to see if they're in "topo order"

usage()

{

    echo "usage: $0 id [...]"

}



case $# in

0) usage 1>&2; exit 1;;

esac



TF1=$(mktemp)

TF2=$(mktemp)

trap "rm -f $TF1 $TF2; exit" 0 1 2 3 15



# parse the arguments into one file

git rev-parse $@ > $TF1 || exit 1

# and topo-sort the arguments into another

git rev-list --topo-order --no-walk --reverse $@ > $TF2 || exit 1

# If the list is in the correct order the files will be the same

cmp -s $TF1 $TF2 || {

    # If the files differ, it's possible that some argument(s) name

    # the same rev...

    [ $(wc -l < $TF1) -eq $(wc -l < $TF2) ] || {

        echo "ERROR: there are repeats in $@"

        # finding them is a pain, we don't bother trying

        exit 1

    }

    echo "ERROR: $@ NOT in topo order"

    echo "use instead:"

    # read the topo-ordered raw IDs

    while read sha1; do

        # and find the (single) arg in $@ that names this one

        for i; do

            if [ $(git rev-parse $i) = $sha1 ]; then

                printf ' %s' $i

                break

            fi

        done

    done < $TF2

    echo

    exit 1

}

echo "$@ in topo order"

exit 0

I think what I wanted here was to emit the same argument names, e.g., if you said git-check-topo v1.7 1234567 branchX it would tell you to use (literally) branchX v1.7 1234567, if that is what got you the right order, rather than just showing the raw SHA-1s.

For your purposes, a simple:

git rev-list --topo-order --no-walk $@

(with or without --reverse as desired) should work, I think.

Another way to speed up git rev-list --topo-order is to use Git 2.20 (Q4 2018)

See commit 561b583, commit b454241, commit 5284fc5, commit f0d9cc4, commit d6b4071, commit 4b47a9a, commit aca4240 (01 Nov 2018) by Derrick Stolee (derrickstolee).
^{(Merged by Junio C Hamano -- gitster -- in commit 62ca33e, 18 Nov 2018)}

revision.c: generation-based topo-order algorithm

The current --topo-order algorithm requires walking all reachable commits up front, topo-sorting them, all before outputting the first value.

This patch introduces a new algorithm which uses stored generation numbers to
incrementally walk in topo-order, outputting commits as we go.

This can dramatically reduce the computation time to write a fixed number of commits, such as when limiting with "-n <N>" or filling the first page of a pager.

In my local testing, I used the following Git commands on the Linux repository in three modes:

• 
  HEAD~1 with no commit-graph,


• 
  HEAD~1 with a commit-graph, and


• HEAD with a commit-graph.

This allows comparing the benefits we get from parsing commits from the commit-graph and then again the benefits we get by restricting the set of commits we walk.

Test: git rev-list --topo-order -100 HEAD

HEAD~1, no commit-graph: 6.80 s

HEAD~1, w/ commit-graph: 0.77 s

  HEAD, w/ commit-graph: 0.02 s

See all the details in commit b454241.

Note: as mentioned in commit d6b4071:

The rev-list command is critical to Git's functionality.

Here are a few important types of rev-list operations:

• 
  Basic: git rev-list --topo-order HEAD
  


• 
  Range: git rev-list --topo-order compare..HEAD
  


• 
  Ancestry: git rev-list --topo-order --ancestry-path compare..HEAD
  


• 
  Symmetric Difference: git rev-list --topo-order compare...HEAD