From: Junio C Hamano <hidden> Date: 2016-06-15 22:57:34
Junio C Hamano [off-list ref] writes:
When sorting commits topologically, the primary invariant is to emit
all children before its parent is emitted. When traversing a forked
s/its/their/;
quoted
As I needed to have an excuse to push jk/commit-info-slab topic
further (I have an unpublished show-branch rewrite on top of it),
I may take a look at doing this myself if/when I find some time.
So this is the first step, applies on top of jk/commit-info-slab.
The next step will be to replace the use of commit_list in this
function with a priority queue, whose API may look like what is at
the end of this message.
Then write a compare function that looks at commit->date field to
compare committer timestamp, and set it to commit_queue->compare
when REV_SORT_BY_COMMIT_DATE is asked for. When doing the graph
traversal order, set compare function to NULL when initializing the
commit_queue and use it as a LIFO stack.
And the step after that will be to add an author-date field to the
commit-info-slab we currently use to keep track of indegree, grab
author timestamp from commits as we encounter them, and write
another comparison function to use that information (using the
cb_data field of commit_queue to point at the info slab) to
implement REV_SORT_BY_AUTHOR_DATE. That step can also implement the
command line option parsing for the new --author-date-order option
(or alternatively, --date-order={author,committer}).
#ifndef COMMIT_QUEUE_H
#define COMMIT_QUEUE_H
/*
* Compare two commits; the third parameter is cb_data in the
* commit_queue structure.
*/
typedef int (*commit_compare_fn)(struct commit *, struct commit *, void *);
struct commit_queue {
commit_compare_fn compare;
void *cb_data;
int alloc, nr;
struct commit **array;
};
/*
* Add the commit to the queue
*/
struct commit *commit_queue_put(struct commit_queue *, struct commit *);
/*
* Extract the commit that compares the smallest out of the queue,
* or NULL. If compare function is NULL, the queue acts as a LIFO
* stack.
*/
struct commit *commit_queue_get(struct commit_queue *);
#endif /* COMMIT_QUEUE_H */
From: Junio C Hamano <hidden> Date: 2016-06-15 22:57:34
These three patches introduce a commit-queue API to manage a set of
commits in a priority queue, with a caller-specified comparison
function. The priority queue replaces the singly-listed commit_list
in the topological sort function.
The series applies on top of the commit-info-slab API sesries Peff
and I did two months ago. These three patches do not use the slab
API yet, but a follow-on patch to introduce REV_SORT_BY_AUTHOR_DATE
needs to use commit-slab to record author date for the commits being
sorted, and consult it in its comparison function when comparing the
author dates of commits.
Junio C Hamano (3):
toposort: rename "lifo" field
commit-queue: LIFO or priority queue of commits
sort-in-topological-order: use commit-queue
Makefile | 2 ++
builtin/log.c | 2 +-
builtin/show-branch.c | 14 +++++----
commit-queue.c | 84 +++++++++++++++++++++++++++++++++++++++++++++++++++
commit-queue.h | 34 +++++++++++++++++++++
commit.c | 70 +++++++++++++++++++++++++-----------------
commit.h | 14 +++++++--
revision.c | 10 +++---
revision.h | 6 +++-
9 files changed, 193 insertions(+), 43 deletions(-)
create mode 100644 commit-queue.c
create mode 100644 commit-queue.h
--
1.8.3-451-gb703ddf
From: Junio C Hamano <hidden> Date: 2016-06-15 22:57:34
Traditionally we used a singly linked list of commits to hold a set
of in-flight commits while traversing history. The most typical use
of the list is to insert commit that is newly discovered in it, keep
it sorted by commit timestamp, pick up the newest one from the list,
and keep digging. The cost of keeping the singly linked list sorted
is nontrivial, and this typical use pattern better matches a priority
queue.
Introduce a commit-queue structure, that can be used either as a
LIFO stack, or a priority queue. This will be used in the next
patch to hold in-flight commits during sort-in-topological-order.
Signed-off-by: Junio C Hamano <redacted>
---
Makefile | 2 ++
commit-queue.c | 71 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
commit-queue.h | 31 +++++++++++++++++++++++++
3 files changed, 104 insertions(+)
create mode 100644 commit-queue.c
create mode 100644 commit-queue.h
@@ -0,0 +1,71 @@+#include"cache.h"+#include"commit.h"+#include"commit-queue.h"++voidclear_commit_queue(structcommit_queue*queue)+{+free(queue->array);+queue->nr=0;+queue->alloc=0;+queue->array=NULL;+}++voidcommit_queue_put(structcommit_queue*queue,structcommit*commit)+{+commit_compare_fncompare=queue->compare;+intix,parent;++/* Append at the end */+ALLOC_GROW(queue->array,queue->nr+1,queue->alloc);+queue->array[queue->nr++]=commit;+if(!compare)+return;/* LIFO */++/* Bubble up the new one */+for(ix=queue->nr-1;ix;ix=parent){+parent=(ix-1)/2;+if(compare(queue->array[parent],queue->array[ix],+queue->cb_data)<0)+break;++commit=queue->array[parent];+queue->array[parent]=queue->array[ix];+queue->array[ix]=commit;+}+}++structcommit*commit_queue_get(structcommit_queue*queue)+{+structcommit*result,*swap;+intix,child;+commit_compare_fncompare=queue->compare;++if(!queue->nr)+returnNULL;+if(!compare)+returnqueue->array[--queue->nr];/* LIFO */++result=queue->array[0];+if(!--queue->nr)+returnresult;++queue->array[0]=queue->array[queue->nr];++/* Push down the one at the root */+for(ix=0;ix*2+1<queue->nr;ix=child){+child=ix*2+1;/* left */+if((child+1<queue->nr)&&+(compare(queue->array[child],queue->array[child+1],+queue->cb_data)>=0))+child++;/* use right child */++if(compare(queue->array[ix],queue->array[child],+queue->cb_data)<0)+break;++swap=queue->array[child];+queue->array[child]=queue->array[ix];+queue->array[ix]=swap;+}+returnresult;+}
From: Junio C Hamano <hidden> Date: 2016-06-15 22:57:34
Use the commit-queue data structure to implement a priority queue
of commits sorted by committer date, when handling --date-order.
The commit-queue structure can also be used as a simple LIFO stack,
which is a good match for --topo-order processing.
Signed-off-by: Junio C Hamano <redacted>
---
commit-queue.c | 13 +++++++++++
commit-queue.h | 3 +++
commit.c | 74 ++++++++++++++++++++++++++++++++++------------------------
3 files changed, 59 insertions(+), 31 deletions(-)
@@ -504,21 +505,41 @@ struct commit *pop_commit(struct commit_list **stack)define_commit_slab(indegree_slab,int);+staticintcompare_commits_by_commit_date(structcommit*a,structcommit*b,void*unused)+{+/* newer commits with larger date first */+if(a->date<b->date)+return1;+elseif(a->date>b->date)+return-1;+return0;+}+/**Performsanin-placetopologicalsortonthelistsupplied.*/-voidsort_in_topological_order(structcommit_list**list,enumrev_sort_ordersort_order)+voidsort_in_topological_order(structcommit_list**list,enumrev_sort_ordersort_order){structcommit_list*next,*orig=*list;-structcommit_list*work,**insert;structcommit_list**pptr;structindegree_slabindegree;+structcommit_queuequeue;+structcommit*commit;if(!orig)return;*list=NULL;init_indegree_slab(&indegree);+memset(&queue,'\0',sizeof(queue));+switch(sort_order){+default:/* REV_SORT_IN_GRAPH_ORDER */+queue.compare=NULL;+break;+caseREV_SORT_BY_COMMIT_DATE:+queue.compare=compare_commits_by_commit_date;+break;+}/* Mark them and clear the indegree */for(next=orig;next;next=next->next){
@@ -546,30 +567,28 @@ void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order s**thetipsserveasastartingsetfortheworkqueue.*/-work=NULL;-insert=&work;for(next=orig;next;next=next->next){structcommit*commit=next->item;if(*(indegree_slab_at(&indegree,commit))==1)-insert=&commit_list_insert(commit,insert)->next;+commit_queue_put(&queue,commit);}-/* process the list in topological order */-if(sort_order!=REV_SORT_IN_GRAPH_ORDER)-commit_list_sort_by_date(&work);+/*+*Thisisunfortunate;theinitialtipsneedtobeshown+*intheordergivenfromtherevisiontraversalmachinery.+*/+if(sort_order==REV_SORT_IN_GRAPH_ORDER)+commit_queue_reverse(&queue);++/* We no longer need the commit list */+free_commit_list(orig);pptr=list;*list=NULL;-while(work){-structcommit*commit;-structcommit_list*parents,*work_item;--work_item=work;-work=work_item->next;-work_item->next=NULL;+while((commit=commit_queue_get(&queue))!=NULL){+structcommit_list*parents;-commit=work_item->item;for(parents=commit->parents;parents;parents=parents->next){structcommit*parent=parents->item;int*pi=indegree_slab_at(&indegree,parent);
From: Junio C Hamano <hidden> Date: 2016-06-15 22:57:34
The primary invariant of sort_in_topological_order() is to emit all
children before their parent is emitted. When traversing a forked
history like this with "git log C E":
A----B----C
\
D----E
we ensure that A is emitted after all of B, C, D, and E are done, B
has to wait until C is done, and D has to wait until E is done.
In some applications, however, we would further want to control how
these child commits B, C, D and E on two parallel ancestry chains
are shown. Most of the time, we would want to see C and B emitted
together, and then E and D, and finally A, which is the default
behaviour for --topo-order output.
The "lifo" parameter of the sort_in_topological_order() function is
used to implement this behaviour. After inspecting C, we notice and
record that B needs to be inspected, and by structuring the "work to
be done" set as a LIFO stack, we ensure that B is inspected next,
before other in-flight commits we had known that we will need to
inspect, e.g. E, that may have already been sitting in the "work to
be done" set.
When showing in --date-order, we would want to see commits ordered
by timestamps, i.e. show C, E, B and D in this order before showing
A, possibly mixing commits from two parallel histories together.
When "lifo" parameter is set to false, the function keeps the "work
to be done" set sorted in the date order to realize this semantics.
But the name "lifo" is too tied to the way how the function implements
its behaviour, and does not describe _what_ the desired semantics is.
Replace the "lifo" field with an enum rev_sort_order, with two
possible values: REV_SORT_IN_GRAPH_ORDER and REV_SORT_BY_COMMIT_DATE.
The mechanical replacement rule is:
"lifo == 0" is equivalent to "sort_order == REV_SORT_BY_COMMIT_DATE"
"lifo == 1" is equivalent to "sort_order == REV_SORT_IN_GRAPH_ORDER"
Signed-off-by: Junio C Hamano <redacted>
---
builtin/log.c | 2 +-
builtin/show-branch.c | 14 ++++++++------
commit.c | 12 ++++++++----
commit.h | 14 +++++++++++---
revision.c | 10 +++++-----
revision.h | 6 +++++-
6 files changed, 38 insertions(+), 20 deletions(-)
@@ -666,15 +666,17 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)N_("show possible merge bases")),OPT_BOOLEAN(0,"independent",&independent,N_("show refs unreachable from any other ref")),-OPT_BOOLEAN(0,"topo-order",&lifo,-N_("show commits in topological order")),+OPT_SET_INT(0,"topo-order",&sort_order,+N_("show commits in topological order"),+REV_SORT_IN_GRAPH_ORDER),OPT_BOOLEAN(0,"topics",&topics,N_("show only commits not on the first branch")),OPT_SET_INT(0,"sparse",&dense,N_("show merges reachable from only one tip"),0),-OPT_SET_INT(0,"date-order",&lifo,+OPT_SET_INT(0,"date-order",&sort_order,N_("show commits where no parent comes before its "-"children"),0),+"children"),+REV_SORT_BY_COMMIT_DATE),{OPTION_CALLBACK,'g',"reflog",&reflog_base,N_("<n>[,<base>]"),N_("show <n> most recent ref-log entries starting at ""base"),
@@ -901,7 +903,7 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)exit(0);/* Sort topologically */-sort_in_topological_order(&seen,lifo);+sort_in_topological_order(&seen,sort_order);/* Give names to commits */if(!sha1_name&&!no_name)
@@ -556,7 +556,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)}/* process the list in topological order */-if(!lifo)+if(sort_order!=REV_SORT_IN_GRAPH_ORDER)commit_list_sort_by_date(&work);pptr=list;
From: Eric Sunshine <hidden> Date: 2016-06-15 22:57:34
On Fri, Jun 7, 2013 at 1:11 AM, Junio C Hamano [off-list ref] wrote:
The primary invariant of sort_in_topological_order() is to emit all
children before their parent is emitted. When traversing a forked
s/parent is/parents are/
history like this with "git log C E":
A----B----C
\
D----E
we ensure that A is emitted after all of B, C, D, and E are done, B
has to wait until C is done, and D has to wait until E is done.
In some applications, however, we would further want to control how
these child commits B, C, D and E on two parallel ancestry chains
are shown. Most of the time, we would want to see C and B emitted
together, and then E and D, and finally A, which is the default
behaviour for --topo-order output.
The "lifo" parameter of the sort_in_topological_order() function is
used to implement this behaviour. After inspecting C, we notice and
record that B needs to be inspected, and by structuring the "work to
be done" set as a LIFO stack, we ensure that B is inspected next,
before other in-flight commits we had known that we will need to
inspect, e.g. E, that may have already been sitting in the "work to
be done" set.
When showing in --date-order, we would want to see commits ordered
by timestamps, i.e. show C, E, B and D in this order before showing
A, possibly mixing commits from two parallel histories together.
When "lifo" parameter is set to false, the function keeps the "work
to be done" set sorted in the date order to realize this semantics.
But the name "lifo" is too tied to the way how the function implements
its behaviour, and does not describe _what_ the desired semantics is.
Replace the "lifo" field with an enum rev_sort_order, with two
possible values: REV_SORT_IN_GRAPH_ORDER and REV_SORT_BY_COMMIT_DATE.
The mechanical replacement rule is:
"lifo == 0" is equivalent to "sort_order == REV_SORT_BY_COMMIT_DATE"
"lifo == 1" is equivalent to "sort_order == REV_SORT_IN_GRAPH_ORDER"
Signed-off-by: Junio C Hamano <redacted>
From: Eric Sunshine <hidden> Date: 2016-06-15 22:57:34
On Fri, Jun 7, 2013 at 1:11 AM, Junio C Hamano [off-list ref] wrote:
Traditionally we used a singly linked list of commits to hold a set
of in-flight commits while traversing history. The most typical use
of the list is to insert commit that is newly discovered in it, keep
s/commit/a commit/
Also, "in it" is perhaps implied by "insert", so s/in it// may be appropriate.
it sorted by commit timestamp, pick up the newest one from the list,
and keep digging. The cost of keeping the singly linked list sorted
is nontrivial, and this typical use pattern better matches a priority
queue.
Introduce a commit-queue structure, that can be used either as a
LIFO stack, or a priority queue. This will be used in the next
patch to hold in-flight commits during sort-in-topological-order.
Signed-off-by: Junio C Hamano <redacted>
From: Junio C Hamano <hidden> Date: 2016-06-15 22:57:39
Not much changed in the first three patches since the edition from
last week. A clean-up to clarify the toposort API, introduction of
priority queue API, and then its use in topological sort logic.
The final patch adds "log --author-date-order" to build on top of
them.
Adding tests to t4202 and/or t6012 is left as an exercise to readers.
Junio C Hamano (4):
toposort: rename "lifo" field
commit-queue: LIFO or priority queue of commits
sort-in-topological-order: use commit-queue
log: --author-date-order
Documentation/rev-list-options.txt | 4 ++
Makefile | 2 +
builtin/log.c | 2 +-
builtin/show-branch.c | 14 ++--
commit-queue.c | 84 ++++++++++++++++++++++++
commit-queue.h | 34 ++++++++++
commit.c | 129 +++++++++++++++++++++++++++++--------
commit.h | 15 ++++-
revision.c | 13 ++--
revision.h | 6 +-
10 files changed, 260 insertions(+), 43 deletions(-)
create mode 100644 commit-queue.c
create mode 100644 commit-queue.h
--
1.8.3-451-gb703ddf
From: Junio C Hamano <hidden> Date: 2016-06-15 22:57:39
The primary invariant of sort_in_topological_order() is that a
parent commit is not emitted untile all children of it are. When
traversing a forked history like this with "git log C E":
A----B----C
\
D----E
we ensure that A is emitted after all of B, C, D, and E are done, B
has to wait until C is done, and D has to wait until E is done.
In some applications, however, we would further want to control how
these child commits B, C, D and E on two parallel ancestry chains
are shown.
Most of the time, we would want to see C and B emitted together, and
then E and D, and finally A (i.e. the --topo-order output). The
"lifo" parameter of the sort_in_topological_order() function is used
to control this behaviour. We start the traversal by knowing two
commits, C and E. While keeping in mind that we also need to
inspect E later, we pick C first to inspect, and we notice and
record that B needs to be inspected. By structuring the "work to be
done" set as a LIFO stack, we ensure that B is inspected next,
before other in-flight commits we had known that we will need to
inspect, e.g. E.
When showing in --date-order, we would want to see commits ordered
by timestamps, i.e. show C, E, B and D in this order before showing
A, possibly mixing commits from two parallel histories together.
When "lifo" parameter is set to false, the function keeps the "work
to be done" set sorted in the date order to realize this semantics.
After inspecting C, we add B to the "work to be done" set, but the
next commit we inspect from the set is E which is newer than B.
The name "lifo", however, is too strongly tied to the way how the
function implements its behaviour, and does not describe what the
behaviour _means_.
Replace this field with an enum rev_sort_order, with two possible
values: REV_SORT_IN_GRAPH_ORDER and REV_SORT_BY_COMMIT_DATE, and
update the existing code. The mechanical replacement rule is:
"lifo == 0" is equivalent to "sort_order == REV_SORT_BY_COMMIT_DATE"
"lifo == 1" is equivalent to "sort_order == REV_SORT_IN_GRAPH_ORDER"
Signed-off-by: Junio C Hamano <redacted>
---
builtin/log.c | 2 +-
builtin/show-branch.c | 14 ++++++++------
commit.c | 12 ++++++++----
commit.h | 14 +++++++++++---
revision.c | 10 +++++-----
revision.h | 6 +++++-
6 files changed, 38 insertions(+), 20 deletions(-)
@@ -666,15 +666,17 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)N_("show possible merge bases")),OPT_BOOLEAN(0,"independent",&independent,N_("show refs unreachable from any other ref")),-OPT_BOOLEAN(0,"topo-order",&lifo,-N_("show commits in topological order")),+OPT_SET_INT(0,"topo-order",&sort_order,+N_("show commits in topological order"),+REV_SORT_IN_GRAPH_ORDER),OPT_BOOLEAN(0,"topics",&topics,N_("show only commits not on the first branch")),OPT_SET_INT(0,"sparse",&dense,N_("show merges reachable from only one tip"),0),-OPT_SET_INT(0,"date-order",&lifo,+OPT_SET_INT(0,"date-order",&sort_order,N_("show commits where no parent comes before its "-"children"),0),+"children"),+REV_SORT_BY_COMMIT_DATE),{OPTION_CALLBACK,'g',"reflog",&reflog_base,N_("<n>[,<base>]"),N_("show <n> most recent ref-log entries starting at ""base"),
@@ -901,7 +903,7 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)exit(0);/* Sort topologically */-sort_in_topological_order(&seen,lifo);+sort_in_topological_order(&seen,sort_order);/* Give names to commits */if(!sha1_name&&!no_name)
@@ -561,7 +561,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)}/* process the list in topological order */-if(!lifo)+if(sort_order!=REV_SORT_IN_GRAPH_ORDER)commit_list_sort_by_date(&work);pptr=list;
From: Junio C Hamano <hidden> Date: 2016-06-15 22:57:39
Traditionally we used a singly linked list of commits to hold a set
of in-flight commits while traversing history. The most typical use
of the list is to add commits that are newly discovered to it, keep
the list sorted by commit timestamp, pick up the newest one from the
list, and keep digging. The cost of keeping the singly linked list
sorted is nontrivial, and this typical use pattern better matches a
priority queue.
Introduce a commit-queue structure, that can be used either as a
LIFO stack, or a priority queue. This will be used in the next
patch to hold in-flight commits during sort-in-topological-order.
Signed-off-by: Junio C Hamano <redacted>
---
Makefile | 2 ++
commit-queue.c | 71 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
commit-queue.h | 31 +++++++++++++++++++++++++
3 files changed, 104 insertions(+)
create mode 100644 commit-queue.c
create mode 100644 commit-queue.h
@@ -0,0 +1,71 @@+#include"cache.h"+#include"commit.h"+#include"commit-queue.h"++voidclear_commit_queue(structcommit_queue*queue)+{+free(queue->array);+queue->nr=0;+queue->alloc=0;+queue->array=NULL;+}++voidcommit_queue_put(structcommit_queue*queue,structcommit*commit)+{+commit_compare_fncompare=queue->compare;+intix,parent;++/* Append at the end */+ALLOC_GROW(queue->array,queue->nr+1,queue->alloc);+queue->array[queue->nr++]=commit;+if(!compare)+return;/* LIFO */++/* Bubble up the new one */+for(ix=queue->nr-1;ix;ix=parent){+parent=(ix-1)/2;+if(compare(queue->array[parent],queue->array[ix],+queue->cb_data)<0)+break;++commit=queue->array[parent];+queue->array[parent]=queue->array[ix];+queue->array[ix]=commit;+}+}++structcommit*commit_queue_get(structcommit_queue*queue)+{+structcommit*result,*swap;+intix,child;+commit_compare_fncompare=queue->compare;++if(!queue->nr)+returnNULL;+if(!compare)+returnqueue->array[--queue->nr];/* LIFO */++result=queue->array[0];+if(!--queue->nr)+returnresult;++queue->array[0]=queue->array[queue->nr];++/* Push down the one at the root */+for(ix=0;ix*2+1<queue->nr;ix=child){+child=ix*2+1;/* left */+if((child+1<queue->nr)&&+(compare(queue->array[child],queue->array[child+1],+queue->cb_data)>=0))+child++;/* use right child */++if(compare(queue->array[ix],queue->array[child],+queue->cb_data)<0)+break;++swap=queue->array[child];+queue->array[child]=queue->array[ix];+queue->array[ix]=swap;+}+returnresult;+}
From: Junio C Hamano <hidden> Date: 2016-06-15 22:57:39
Use the commit-queue data structure to implement a priority queue
of commits sorted by committer date, when handling --date-order.
The commit-queue structure can also be used as a simple LIFO stack,
which is a good match for --topo-order processing.
Signed-off-by: Junio C Hamano <redacted>
---
commit-queue.c | 13 +++++++++++
commit-queue.h | 3 +++
commit.c | 74 ++++++++++++++++++++++++++++++++++------------------------
3 files changed, 59 insertions(+), 31 deletions(-)
@@ -509,21 +510,41 @@ struct commit *pop_commit(struct commit_list **stack)/* count number of children that have not been emitted */define_commit_slab(indegree_slab,int);+staticintcompare_commits_by_commit_date(structcommit*a,structcommit*b,void*unused)+{+/* newer commits with larger date first */+if(a->date<b->date)+return1;+elseif(a->date>b->date)+return-1;+return0;+}+/**Performsanin-placetopologicalsortonthelistsupplied.*/-voidsort_in_topological_order(structcommit_list**list,enumrev_sort_ordersort_order)+voidsort_in_topological_order(structcommit_list**list,enumrev_sort_ordersort_order){structcommit_list*next,*orig=*list;-structcommit_list*work,**insert;structcommit_list**pptr;structindegree_slabindegree;+structcommit_queuequeue;+structcommit*commit;if(!orig)return;*list=NULL;init_indegree_slab(&indegree);+memset(&queue,'\0',sizeof(queue));+switch(sort_order){+default:/* REV_SORT_IN_GRAPH_ORDER */+queue.compare=NULL;+break;+caseREV_SORT_BY_COMMIT_DATE:+queue.compare=compare_commits_by_commit_date;+break;+}/* Mark them and clear the indegree */for(next=orig;next;next=next->next){
@@ -551,30 +572,28 @@ void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order s**thetipsserveasastartingsetfortheworkqueue.*/-work=NULL;-insert=&work;for(next=orig;next;next=next->next){structcommit*commit=next->item;if(*(indegree_slab_at(&indegree,commit))==1)-insert=&commit_list_insert(commit,insert)->next;+commit_queue_put(&queue,commit);}-/* process the list in topological order */-if(sort_order!=REV_SORT_IN_GRAPH_ORDER)-commit_list_sort_by_date(&work);+/*+*Thisisunfortunate;theinitialtipsneedtobeshown+*intheordergivenfromtherevisiontraversalmachinery.+*/+if(sort_order==REV_SORT_IN_GRAPH_ORDER)+commit_queue_reverse(&queue);++/* We no longer need the commit list */+free_commit_list(orig);pptr=list;*list=NULL;-while(work){-structcommit*commit;-structcommit_list*parents,*work_item;--work_item=work;-work=work_item->next;-work_item->next=NULL;+while((commit=commit_queue_get(&queue))!=NULL){+structcommit_list*parents;-commit=work_item->item;for(parents=commit->parents;parents;parents=parents->next){structcommit*parent=parents->item;int*pi=indegree_slab_at(&indegree,parent);
From: Junio C Hamano <hidden> Date: 2016-06-15 22:57:39
Sometimes people would want to view the commits in parallel
histories in the order of author dates, not committer dates.
Teach "topo-order" sort machinery to do so, using a commit-info slab
to record the author dates of each commit, and commit-queue to sort
them.
Signed-off-by: Junio C Hamano <redacted>
---
Documentation/rev-list-options.txt | 4 +++
commit.c | 59 ++++++++++++++++++++++++++++++++++++++
commit.h | 3 +-
revision.c | 3 ++
4 files changed, 68 insertions(+), 1 deletion(-)
@@ -617,6 +617,10 @@ By default, the commits are shown in reverse chronological order. Show no parents before all of its children are shown, but otherwise show commits in the commit timestamp order.+--author-date-order::+ Show no parents before all of its children are shown, but+ otherwise show commits in the author timestamp order.+ --topo-order:: Show no parents before all of its children are shown, and avoid showing commits on multiple lines of history
@@ -510,6 +510,53 @@ struct commit *pop_commit(struct commit_list **stack)/* count number of children that have not been emitted */define_commit_slab(indegree_slab,int);+/* record author-date for each commit object */+define_commit_slab(author_date_slab,unsignedlong);++staticvoidrecord_author_date(structauthor_date_slab*author_date,+structcommit*commit)+{+constchar*buf,*line_end;+structident_splitident;+char*date_end;+unsignedlongdate;++for(buf=commit->buffer;buf;buf=line_end+1){+line_end=strchrnul(buf,'\n');+if(prefixcmp(buf,"author ")){+if(!line_end[0]||line_end[1]=='\n')+return;/* end of header */+continue;+}+if(split_ident_line(&ident,+buf+strlen("author "),+line_end-(buf+strlen("author ")))||+!ident.date_begin||!ident.date_end)+return;/* malformed "author" line */+break;+}++date=strtoul(ident.date_begin,&date_end,10);+if(date_end!=ident.date_end)+return;/* malformed date */+*(author_date_slab_at(author_date,commit))=date;+}++staticintcompare_commits_by_author_date(structcommit*a,structcommit*b,+void*cb_data)+{+structauthor_date_slab*author_date=cb_data;+unsignedlonga_date=*(author_date_slab_at(author_date,a));+unsignedlongb_date=*(author_date_slab_at(author_date,b));++/* newer commits with larger date first */+if(a_date<b_date)+return1;+elseif(a_date>b_date)+return-1;+return0;+}+staticintcompare_commits_by_commit_date(structcommit*a,structcommit*b,void*unused){/* newer commits with larger date first */
@@ -544,12 +593,20 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order socaseREV_SORT_BY_COMMIT_DATE:queue.compare=compare_commits_by_commit_date;break;+caseREV_SORT_BY_AUTHOR_DATE:+init_author_date_slab(&author_date);+queue.compare=compare_commits_by_author_date;+queue.cb_data=&author_date;+break;}/* Mark them and clear the indegree */for(next=orig;next;next=next->next){structcommit*commit=next->item;*(indegree_slab_at(&indegree,commit))=1;+/* also record the author dates, if needed */+if(sort_order==REV_SORT_BY_AUTHOR_DATE)+record_author_date(&author_date,commit);}/* update the indegree */
From: Eric Sunshine <hidden> Date: 2016-06-15 22:57:39
On Sun, Jun 9, 2013 at 7:24 PM, Junio C Hamano [off-list ref] wrote:
The primary invariant of sort_in_topological_order() is that a
parent commit is not emitted untile all children of it are. When
s/untile/until/
traversing a forked history like this with "git log C E":
A----B----C
\
D----E
we ensure that A is emitted after all of B, C, D, and E are done, B
has to wait until C is done, and D has to wait until E is done.
In some applications, however, we would further want to control how
these child commits B, C, D and E on two parallel ancestry chains
are shown.
Most of the time, we would want to see C and B emitted together, and
then E and D, and finally A (i.e. the --topo-order output). The
"lifo" parameter of the sort_in_topological_order() function is used
to control this behaviour. We start the traversal by knowing two
commits, C and E. While keeping in mind that we also need to
inspect E later, we pick C first to inspect, and we notice and
record that B needs to be inspected. By structuring the "work to be
done" set as a LIFO stack, we ensure that B is inspected next,
before other in-flight commits we had known that we will need to
inspect, e.g. E.
When showing in --date-order, we would want to see commits ordered
by timestamps, i.e. show C, E, B and D in this order before showing
A, possibly mixing commits from two parallel histories together.
When "lifo" parameter is set to false, the function keeps the "work
to be done" set sorted in the date order to realize this semantics.
After inspecting C, we add B to the "work to be done" set, but the
next commit we inspect from the set is E which is newer than B.
The name "lifo", however, is too strongly tied to the way how the
s/the way//
function implements its behaviour, and does not describe what the
behaviour _means_.
Replace this field with an enum rev_sort_order, with two possible
values: REV_SORT_IN_GRAPH_ORDER and REV_SORT_BY_COMMIT_DATE, and
update the existing code. The mechanical replacement rule is:
"lifo == 0" is equivalent to "sort_order == REV_SORT_BY_COMMIT_DATE"
"lifo == 1" is equivalent to "sort_order == REV_SORT_IN_GRAPH_ORDER"
Signed-off-by: Junio C Hamano <redacted>
From: Jeff King <hidden> Date: 2016-06-15 22:57:39
On Sun, Jun 09, 2013 at 04:24:34PM -0700, Junio C Hamano wrote:
The name "lifo", however, is too strongly tied to the way how the
function implements its behaviour, and does not describe what the
behaviour _means_.
Replace this field with an enum rev_sort_order, with two possible
values: REV_SORT_IN_GRAPH_ORDER and REV_SORT_BY_COMMIT_DATE, and
update the existing code. The mechanical replacement rule is:
"lifo == 0" is equivalent to "sort_order == REV_SORT_BY_COMMIT_DATE"
"lifo == 1" is equivalent to "sort_order == REV_SORT_IN_GRAPH_ORDER"
Thanks. Having looked at this code for the first time in a long time
recently, I was very confused by the purpose of the "lifo" flag; this
patch would have made it much clearer.
Patch itself looks fine to me.
-Peff
From: Jeff King <hidden> Date: 2016-06-15 22:57:39
On Sun, Jun 09, 2013 at 04:24:35PM -0700, Junio C Hamano wrote:
Traditionally we used a singly linked list of commits to hold a set
of in-flight commits while traversing history. The most typical use
of the list is to add commits that are newly discovered to it, keep
the list sorted by commit timestamp, pick up the newest one from the
list, and keep digging. The cost of keeping the singly linked list
sorted is nontrivial, and this typical use pattern better matches a
priority queue.
Introduce a commit-queue structure, that can be used either as a
LIFO stack, or a priority queue. This will be used in the next
patch to hold in-flight commits during sort-in-topological-order.
Great. You may recall I had a similar patch or year or two back, in an
attempt to fix some of the O(n^2) places (e.g., in fetch-pack's
mark_complete). We ended up dropping it because duplicate removal kept
"n" small enough for common cases, and most of the commit_list users
depend on doing cheap splicing and other linked-list operations.
It may be worth looking again for other places to use this over
commit_list, but even the caller you are introducing here justifies its
presence.
Also, I wrote some basic tests to cover the priority queue as a unit. I
can rebase them on your commit if you are interested.
A few comments on the code itself:
Is it worth making this "struct commit *" a void pointer, and handling
arbitrary items in our priority queue? The compare function should be
the only thing that dereferences them.
I do not have any non-commit priority queue use in mind, but I do not
think it adds any complexity in this case.
+ /* Bubble up the new one */
+ for (ix = queue->nr - 1; ix; ix = parent) {
+ parent = (ix - 1) / 2;
+ if (compare(queue->array[parent], queue->array[ix],
+ queue->cb_data) < 0)
+ break;
In my implementation, I stopped on "compare() <= 0". It is late and my
mind is fuzzy, but I recall that heaps are never stable with respect to
insertion order, so I don't think it would matter.
-Peff
From: Jeff King <hidden> Date: 2016-06-15 22:57:39
On Sun, Jun 09, 2013 at 04:24:37PM -0700, Junio C Hamano wrote:
Sometimes people would want to view the commits in parallel
histories in the order of author dates, not committer dates.
Teach "topo-order" sort machinery to do so, using a commit-info slab
to record the author dates of each commit, and commit-queue to sort
them.
Nice, this is basically what I was envisioning when I mentioned the
slabs. However, I don't think the code works. :(
I'm not excited about introducing yet another place that parses commit
objects (mostly not for correctness, but because we have had
inconsistency in how malformed objects are treated). It is at least
using split_ident_line which covers the hard bits. I wonder how much
slower it would be to simply call format_commit_message to do the
parsing.
/* Mark them and clear the indegree */
for (next = orig; next; next = next->next) {
struct commit *commit = next->item;
*(indegree_slab_at(&indegree, commit)) = 1;
+ /* also record the author dates, if needed */
+ if (sort_order == REV_SORT_BY_AUTHOR_DATE)
+ record_author_date(&author_date, commit);
The record_author_date function assumes that commit->buffer is valid
(i.e., not NULL). We seem to assume that the commits are parsed already
(for looking at parents, and at the committer date). But if
"save_commit_buffer" is set to 0 (as it is for rev-list), we would not
have a buffer at all.
It's hard to notice the problem because a NULL buffer will cause
record_author_date to simply leave the slab entry at 0. That would give
the same output as regular "--topo-order" (because everybody has the
same timestamp), except that the priority queue heap is not stable.
With this patch: