[PATCH] toposort: rename lifo field
When sorting commits topologically, the primary invariant is to emit
all children before its parent is emitted. When traversing a forked
history like this with git log C E:
ABC
\
DE
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. This is the default
behaviour for --topo-order output.
The lifo parameter of the sort_in_topological_order() function is
used to control this. 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 have already been 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, mixing commits from two parallel histories together. When lifo
is set to false, the function keeps the work to be done set sorted
in the date order to realize this sematics.
But the name lifo is too tied to the way how the function implements
its behaviour, and does not describe _what_ is the desired semantcs.
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 gits...@pobox.com
---
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.
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(-)
diff --git a/builtin/log.c b/builtin/log.c
index 8f0b2e8..8d26042 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -205,7 +205,7 @@ static void log_show_early(struct rev_info *revs, struct
commit_list *list)
int i = revs-early_output;
int show_header = 1;
- sort_in_topological_order(list, revs-lifo);
+ sort_in_topological_order(list, revs-sort_order);
while (list i) {
struct commit *commit = list-item;
switch (simplify_commit(revs, commit)) {
diff --git a/builtin/show-branch.c b/builtin/show-branch.c
index d208fd6..7c57985 100644
--- a/builtin/show-branch.c
+++ b/builtin/show-branch.c
@@ -631,7 +631,7 @@ int cmd_show_branch(int ac, const char **av, const char
*prefix)
int num_rev, i, extra = 0;
int all_heads = 0, all_remotes = 0;
int all_mask, all_revs;
- int lifo = 1;
+ enum rev_sort_order sort_order = REV_SORT_IN_GRAPH_ORDER;
char head[128];
const char *head_p;
int head_len;
@@ -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,
Re: [PATCH] toposort: rename lifo field
Junio C Hamano gits...@pobox.com 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/;
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 */
--
To unsubscribe from this list: send the line unsubscribe git in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] toposort: rename lifo field
On Thu, Jun 6, 2013 at 7:25 PM, Junio C Hamano gits...@pobox.com wrote: When sorting commits topologically, the primary invariant is to emit all children before its parent is emitted. When traversing a forked history like this with git log C E: ABC \ DE 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. This is the default behaviour for --topo-order output. The lifo parameter of the sort_in_topological_order() function is used to control this. 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 have already been 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, mixing commits from two parallel histories together. When lifo is set to false, the function keeps the work to be done set sorted in the date order to realize this sematics. s/sematics/semantics/ (or perhaps s/.../semantic/ ?) But the name lifo is too tied to the way how the function implements its behaviour, and does not describe _what_ is the desired semantcs. s/semantcs/semantics/ 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 gits...@pobox.com -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
