How can I sort a set of git commit IDs in topological order?












4















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.










share|improve this question























  • Note: git rev-list --topo-order will be faster with Git 2.20 (Q4 2018). See my answer below.

    – VonC
    Nov 19 '18 at 20:59
















4















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.










share|improve this question























  • Note: git rev-list --topo-order will be faster with Git 2.20 (Q4 2018). See my answer below.

    – VonC
    Nov 19 '18 at 20:59














4












4








4


2






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.










share|improve this question














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.







git






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked Mar 28 '14 at 13:33









FlimmFlimm

52.7k23136158




52.7k23136158













  • Note: git rev-list --topo-order will be faster with Git 2.20 (Q4 2018). See my answer below.

    – VonC
    Nov 19 '18 at 20:59



















  • Note: git rev-list --topo-order will be faster with Git 2.20 (Q4 2018). See my answer below.

    – VonC
    Nov 19 '18 at 20:59

















Note: git rev-list --topo-order will be faster with Git 2.20 (Q4 2018). See my answer below.

– VonC
Nov 19 '18 at 20:59





Note: git rev-list --topo-order will be faster with Git 2.20 (Q4 2018). See my answer below.

– VonC
Nov 19 '18 at 20:59












3 Answers
3






active

oldest

votes


















5














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.






share|improve this answer
























  • When the set of commits that you’re interested in is small compared to the repository size, and the commits are relatively close together in the history, it can be a significant improvement to exclude the parents of git merge-base --all --octopus "${shas[@]}" from the rev-list invocation.

    – wchargin
    yesterday



















4














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.






share|improve this answer


























  • I do not think --no-walk will do it. From the 2.6.2 docs you can see that --no-walk either outputs the commits int he order they were supplied or by date. ` --no-walk[=(sorted|unsorted)] Only show the given commits, but do not traverse their ancestors. This has no effect if a range is specified. If the argument unsorted is given, the commits are shown in the order they were given on the command line. Otherwise (if sorted or no argument was given), the commits are shown in reverse chronological order by commit time. Cannot be combined with --graph.`

    – Mort
    Jan 8 '16 at 20:35













  • @Mort: interesting: that text was added in git 2.4.0. Inspection of the source shows that it did indeed never work (the --no-walk flag causes the code to return before even attempting a topo-sort, probably because nothing has bothered to load enough of the graph to achieve it anyway). The rev-list command doesn't reject the request, and it could do it (by doing the necessary walking, but keeping these commits internal-only); it just doesn't bother.

    – torek
    Jan 9 '16 at 6:07



















1














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







share|improve this answer
























  • So to answer the question, the command to run is still git rev-list --all --topo-order | grep --file SET_OF_SHA1S, it just happens to be faster in Git 2.20?

    – Flimm
    Nov 20 '18 at 6:32











  • Yes, that is the idea.

    – VonC
    Nov 20 '18 at 6:39











Your Answer






StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f22714371%2fhow-can-i-sort-a-set-of-git-commit-ids-in-topological-order%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























3 Answers
3






active

oldest

votes








3 Answers
3






active

oldest

votes









active

oldest

votes






active

oldest

votes









5














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.






share|improve this answer
























  • When the set of commits that you’re interested in is small compared to the repository size, and the commits are relatively close together in the history, it can be a significant improvement to exclude the parents of git merge-base --all --octopus "${shas[@]}" from the rev-list invocation.

    – wchargin
    yesterday
















5














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.






share|improve this answer
























  • When the set of commits that you’re interested in is small compared to the repository size, and the commits are relatively close together in the history, it can be a significant improvement to exclude the parents of git merge-base --all --octopus "${shas[@]}" from the rev-list invocation.

    – wchargin
    yesterday














5












5








5







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.






share|improve this answer













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.







share|improve this answer












share|improve this answer



share|improve this answer










answered Mar 28 '14 at 13:52









FlimmFlimm

52.7k23136158




52.7k23136158













  • When the set of commits that you’re interested in is small compared to the repository size, and the commits are relatively close together in the history, it can be a significant improvement to exclude the parents of git merge-base --all --octopus "${shas[@]}" from the rev-list invocation.

    – wchargin
    yesterday



















  • When the set of commits that you’re interested in is small compared to the repository size, and the commits are relatively close together in the history, it can be a significant improvement to exclude the parents of git merge-base --all --octopus "${shas[@]}" from the rev-list invocation.

    – wchargin
    yesterday

















When the set of commits that you’re interested in is small compared to the repository size, and the commits are relatively close together in the history, it can be a significant improvement to exclude the parents of git merge-base --all --octopus "${shas[@]}" from the rev-list invocation.

– wchargin
yesterday





When the set of commits that you’re interested in is small compared to the repository size, and the commits are relatively close together in the history, it can be a significant improvement to exclude the parents of git merge-base --all --octopus "${shas[@]}" from the rev-list invocation.

– wchargin
yesterday













4














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.






share|improve this answer


























  • I do not think --no-walk will do it. From the 2.6.2 docs you can see that --no-walk either outputs the commits int he order they were supplied or by date. ` --no-walk[=(sorted|unsorted)] Only show the given commits, but do not traverse their ancestors. This has no effect if a range is specified. If the argument unsorted is given, the commits are shown in the order they were given on the command line. Otherwise (if sorted or no argument was given), the commits are shown in reverse chronological order by commit time. Cannot be combined with --graph.`

    – Mort
    Jan 8 '16 at 20:35













  • @Mort: interesting: that text was added in git 2.4.0. Inspection of the source shows that it did indeed never work (the --no-walk flag causes the code to return before even attempting a topo-sort, probably because nothing has bothered to load enough of the graph to achieve it anyway). The rev-list command doesn't reject the request, and it could do it (by doing the necessary walking, but keeping these commits internal-only); it just doesn't bother.

    – torek
    Jan 9 '16 at 6:07
















4














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.






share|improve this answer


























  • I do not think --no-walk will do it. From the 2.6.2 docs you can see that --no-walk either outputs the commits int he order they were supplied or by date. ` --no-walk[=(sorted|unsorted)] Only show the given commits, but do not traverse their ancestors. This has no effect if a range is specified. If the argument unsorted is given, the commits are shown in the order they were given on the command line. Otherwise (if sorted or no argument was given), the commits are shown in reverse chronological order by commit time. Cannot be combined with --graph.`

    – Mort
    Jan 8 '16 at 20:35













  • @Mort: interesting: that text was added in git 2.4.0. Inspection of the source shows that it did indeed never work (the --no-walk flag causes the code to return before even attempting a topo-sort, probably because nothing has bothered to load enough of the graph to achieve it anyway). The rev-list command doesn't reject the request, and it could do it (by doing the necessary walking, but keeping these commits internal-only); it just doesn't bother.

    – torek
    Jan 9 '16 at 6:07














4












4








4







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.






share|improve this answer















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.







share|improve this answer














share|improve this answer



share|improve this answer








edited May 23 '17 at 12:15









Community

11




11










answered Mar 28 '14 at 23:55









torektorek

190k18236319




190k18236319













  • I do not think --no-walk will do it. From the 2.6.2 docs you can see that --no-walk either outputs the commits int he order they were supplied or by date. ` --no-walk[=(sorted|unsorted)] Only show the given commits, but do not traverse their ancestors. This has no effect if a range is specified. If the argument unsorted is given, the commits are shown in the order they were given on the command line. Otherwise (if sorted or no argument was given), the commits are shown in reverse chronological order by commit time. Cannot be combined with --graph.`

    – Mort
    Jan 8 '16 at 20:35













  • @Mort: interesting: that text was added in git 2.4.0. Inspection of the source shows that it did indeed never work (the --no-walk flag causes the code to return before even attempting a topo-sort, probably because nothing has bothered to load enough of the graph to achieve it anyway). The rev-list command doesn't reject the request, and it could do it (by doing the necessary walking, but keeping these commits internal-only); it just doesn't bother.

    – torek
    Jan 9 '16 at 6:07



















  • I do not think --no-walk will do it. From the 2.6.2 docs you can see that --no-walk either outputs the commits int he order they were supplied or by date. ` --no-walk[=(sorted|unsorted)] Only show the given commits, but do not traverse their ancestors. This has no effect if a range is specified. If the argument unsorted is given, the commits are shown in the order they were given on the command line. Otherwise (if sorted or no argument was given), the commits are shown in reverse chronological order by commit time. Cannot be combined with --graph.`

    – Mort
    Jan 8 '16 at 20:35













  • @Mort: interesting: that text was added in git 2.4.0. Inspection of the source shows that it did indeed never work (the --no-walk flag causes the code to return before even attempting a topo-sort, probably because nothing has bothered to load enough of the graph to achieve it anyway). The rev-list command doesn't reject the request, and it could do it (by doing the necessary walking, but keeping these commits internal-only); it just doesn't bother.

    – torek
    Jan 9 '16 at 6:07

















I do not think --no-walk will do it. From the 2.6.2 docs you can see that --no-walk either outputs the commits int he order they were supplied or by date. ` --no-walk[=(sorted|unsorted)] Only show the given commits, but do not traverse their ancestors. This has no effect if a range is specified. If the argument unsorted is given, the commits are shown in the order they were given on the command line. Otherwise (if sorted or no argument was given), the commits are shown in reverse chronological order by commit time. Cannot be combined with --graph.`

– Mort
Jan 8 '16 at 20:35







I do not think --no-walk will do it. From the 2.6.2 docs you can see that --no-walk either outputs the commits int he order they were supplied or by date. ` --no-walk[=(sorted|unsorted)] Only show the given commits, but do not traverse their ancestors. This has no effect if a range is specified. If the argument unsorted is given, the commits are shown in the order they were given on the command line. Otherwise (if sorted or no argument was given), the commits are shown in reverse chronological order by commit time. Cannot be combined with --graph.`

– Mort
Jan 8 '16 at 20:35















@Mort: interesting: that text was added in git 2.4.0. Inspection of the source shows that it did indeed never work (the --no-walk flag causes the code to return before even attempting a topo-sort, probably because nothing has bothered to load enough of the graph to achieve it anyway). The rev-list command doesn't reject the request, and it could do it (by doing the necessary walking, but keeping these commits internal-only); it just doesn't bother.

– torek
Jan 9 '16 at 6:07





@Mort: interesting: that text was added in git 2.4.0. Inspection of the source shows that it did indeed never work (the --no-walk flag causes the code to return before even attempting a topo-sort, probably because nothing has bothered to load enough of the graph to achieve it anyway). The rev-list command doesn't reject the request, and it could do it (by doing the necessary walking, but keeping these commits internal-only); it just doesn't bother.

– torek
Jan 9 '16 at 6:07











1














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







share|improve this answer
























  • So to answer the question, the command to run is still git rev-list --all --topo-order | grep --file SET_OF_SHA1S, it just happens to be faster in Git 2.20?

    – Flimm
    Nov 20 '18 at 6:32











  • Yes, that is the idea.

    – VonC
    Nov 20 '18 at 6:39
















1














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







share|improve this answer
























  • So to answer the question, the command to run is still git rev-list --all --topo-order | grep --file SET_OF_SHA1S, it just happens to be faster in Git 2.20?

    – Flimm
    Nov 20 '18 at 6:32











  • Yes, that is the idea.

    – VonC
    Nov 20 '18 at 6:39














1












1








1







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







share|improve this answer













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








share|improve this answer












share|improve this answer



share|improve this answer










answered Nov 19 '18 at 20:56









VonCVonC

841k29426603209




841k29426603209













  • So to answer the question, the command to run is still git rev-list --all --topo-order | grep --file SET_OF_SHA1S, it just happens to be faster in Git 2.20?

    – Flimm
    Nov 20 '18 at 6:32











  • Yes, that is the idea.

    – VonC
    Nov 20 '18 at 6:39



















  • So to answer the question, the command to run is still git rev-list --all --topo-order | grep --file SET_OF_SHA1S, it just happens to be faster in Git 2.20?

    – Flimm
    Nov 20 '18 at 6:32











  • Yes, that is the idea.

    – VonC
    Nov 20 '18 at 6:39

















So to answer the question, the command to run is still git rev-list --all --topo-order | grep --file SET_OF_SHA1S, it just happens to be faster in Git 2.20?

– Flimm
Nov 20 '18 at 6:32





So to answer the question, the command to run is still git rev-list --all --topo-order | grep --file SET_OF_SHA1S, it just happens to be faster in Git 2.20?

– Flimm
Nov 20 '18 at 6:32













Yes, that is the idea.

– VonC
Nov 20 '18 at 6:39





Yes, that is the idea.

– VonC
Nov 20 '18 at 6:39


















draft saved

draft discarded




















































Thanks for contributing an answer to Stack Overflow!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f22714371%2fhow-can-i-sort-a-set-of-git-commit-ids-in-topological-order%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Guess what letter conforming each word

Port of Spain

Run scheduled task as local user group (not BUILTIN)