* [PATCH] Modify git-rev-list ... in merge order [ de-nitted ]
From: jon @ 2005-06-04 7:53 UTC (permalink / raw)
To: git, jon.seymour, torvalds; +Cc: junkio
[PATCH] Modify git-rev-list to linearise the commit history in merge order.
This patch linearises the GIT commit history graph into merge order
which is defined by invariants specified in Documentation/git-rev-list.txt.
The linearisation produced by this patch is superior in an objective sense
to that produced by the existing git-rev-list implementation in that
the linearisation produced is guaranteed to have the minimum number of
discontinuities, where a discontinuity is defined as an adjacent pair of
commits in the output list which are not related in a direct child-parent
relationship.
With this patch a graph like this:
a4 ---
| \ \
| b4 |
|/ | |
a3 | |
| | |
a2 | |
| | c3
| | |
| | c2
| b3 |
| | /|
| b2 |
| | c1
| | /
| b1
a1 |
| |
a0 |
| /
root
Sorts like this:
= a4
| c3
| c2
| c1
^ b4
| b3
| b2
| b1
^ a3
| a2
| a1
| a0
= root
Instead of this:
= a4
| c3
^ b4
| a3
^ c2
^ b3
^ a2
^ b2
^ c1
^ a1
^ b1
^ a0
= root
A test script, t/t6000-rev-list.sh, includes a test which demonstrates
that the linearisation produced by --merge-order has less discontinuities
than the linearisation produced by git-rev-list without the --merge-order
flag specified. To see this, do the following:
cd t
./t6000-rev-list.sh
cd trash
cat actual-default-order
cat actual-merge-order
The existing behaviour of git-rev-list is preserved, by default. To obtain
the modified behaviour, specify --merge-order or --merge-order --show-breaks
on the command line.
This version of the patch has been tested on the git repository and also on the linux-2.6
repository and has reasonable performance on both - ~50-100% slower than the original algorithm.
For more details about this change, refer to Documentation/git-rev-list.txt
and http://blackcubes.dyndns.org/epoch/.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
diff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt
--- a/Documentation/git-rev-list.txt
+++ b/Documentation/git-rev-list.txt
@@ -9,7 +9,7 @@ git-rev-list - Lists commit objects in r
SYNOPSIS
--------
-'git-rev-list' <commit>
+'git-rev-list' [ *--max-count*=number ] [ *--max-age*=timestamp ] [ *--min-age*=timestamp ] [ *--merge-order* [ *--show-breaks* ] ] <commit>
DESCRIPTION
-----------
@@ -17,11 +17,39 @@ Lists commit objects in reverse chronolo
given commit, taking ancestry relationship into account. This is
useful to produce human-readable log output.
+If *--merge-order* is specified, the commit history is decomposed into a unique sequence of minimal, non-linear
+epochs and maximal, linear epochs. Non-linear epochs are then linearised by sorting them into merge order, which
+is described below.
+
+Maximal, linear epochs correspond to periods of sequential development. Minimal, non-linear epochs
+correspond to periods of divergent development followed by a converging merge. The theory of epochs is described
+in more detail at link:http://blackcubes.dyndns.org/epoch/[http://blackcubes.dyndns.org/epoch/].
+
+The merge order for a non-linear epoch is defined as a linearisation for which the following invariants are true:
+
+ 1. if a commit P is reachable from commit N, commit P sorts after commit N in the linearised list.
+ 2. if Pi and Pj are any two parents of a merge M (with i < j), then any commit N, such that N is reachable from Pj
+ but not reachable from Pi, sorts before all commits reachable from Pi.
+
+Invariant 1 states that later commits appear before earlier commits they are derived from.
+
+Invariant 2 states that commits unique to "later" parents in a merge, appear before all commits from "earlier" parents of
+a merge.
+
+If *--show-breaks* is specified, each item of the list is output with a 2-character prefix consisting of one of:
+ (|), (^), (=) followed by a space.
+Commits marked with (=) represent the boundaries of minimal, non-linear epochs and correspond either to the start of a period of divergent development or to the end of such a period.
+Commits marked with (|) are direct parents of commits immediately preceding the marked commit in the list.
+Commits marked with (^) are not parents of the immediately preceding commit. These "breaks" represent necessary discontinuities implied by trying to represent an arbtirary DAG in a linear form.
+
+*--show-breaks* is only valid if *--merge-order* is also specified.
Author
------
Written by Linus Torvalds <torvalds@osdl.org>
+Original *--merge-order* logic by Jon Seymour <jon.seymour@gmail.com>
+
Documentation
--------------
Documentation by David Greaves, Junio C Hamano and the git-list <git@vger.kernel.org>.
diff --git a/Makefile b/Makefile
--- a/Makefile
+++ b/Makefile
@@ -40,9 +40,9 @@ install: $(PROG) $(SCRIPTS)
$(INSTALL) $(PROG) $(SCRIPTS) $(dest)$(bin)
LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o \
- tag.o delta.o date.o index.o diff-delta.o patch-delta.o
+ tag.o delta.o date.o index.o diff-delta.o patch-delta.o epoch.o
LIB_FILE=libgit.a
-LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h
+LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h epoch.h
LIB_H += strbuf.h
LIB_OBJS += strbuf.o
@@ -134,6 +134,7 @@ diffcore-pathspec.o : $(LIB_H) diffcore.
diffcore-pickaxe.o : $(LIB_H) diffcore.h
diffcore-break.o : $(LIB_H) diffcore.h
diffcore-order.o : $(LIB_H) diffcore.h
+epoch.o: $(LIB_H)
test: all
$(MAKE) -C t/ all
diff --git a/commit.c b/commit.c
--- a/commit.c
+++ b/commit.c
@@ -129,7 +129,7 @@ void free_commit_list(struct commit_list
}
}
-static void insert_by_date(struct commit_list **list, struct commit *item)
+void insert_by_date(struct commit_list **list, struct commit *item)
{
struct commit_list **pp = list;
struct commit_list *p;
@@ -254,3 +254,25 @@ unsigned long pretty_print_commit(const
buf[offset] = '\0';
return offset;
}
+
+struct commit *pop_commit(struct commit_list **stack)
+{
+ struct commit_list *top = *stack;
+ struct commit *item = top ? top->item : NULL;
+
+ if (top) {
+ *stack = top->next;
+ free(top);
+ }
+ return item;
+}
+
+int count_parents(struct commit * commit)
+{
+ int count = 0;
+ struct commit_list * parents = commit->parents;
+ for (count=0;parents; parents=parents->next,count++)
+ ;
+ return count;
+}
+
diff --git a/commit.h b/commit.h
--- a/commit.h
+++ b/commit.h
@@ -32,6 +32,8 @@ void free_commit_list(struct commit_list
void sort_by_date(struct commit_list **list);
+void insert_by_date(struct commit_list **list, struct commit *item);
+
extern unsigned long pretty_print_commit(const char *msg, unsigned long len, char *buf, unsigned long space);
@@ -41,4 +43,7 @@ extern unsigned long pretty_print_commit
struct commit *pop_most_recent_commit(struct commit_list **list,
unsigned int mark);
+struct commit *pop_commit(struct commit_list **stack);
+
+int count_parents(struct commit * commit);
#endif /* COMMIT_H */
diff --git a/epoch.c b/epoch.c
new file mode 100644
--- /dev/null
+++ b/epoch.c
@@ -0,0 +1,454 @@
+/*
+ * Copyright (c) 2005, Jon Seymour
+ *
+ * For more information about epoch theory on which this module is based,
+ * refer to http://blackcubes.dyndns.org/epoch/. That web page defines
+ * terms such as "epoch" and "minimal, non-linear epoch" and provides rationales
+ * for some of the algorithms used here.
+ *
+ */
+#include <stdlib.h>
+#include <openssl/bn.h> // provides arbitrary precision integers required to accurately represent fractional mass
+#include "cache.h"
+#include "commit.h"
+#include "epoch.h"
+
+struct fraction {
+ BIGNUM numerator;
+ BIGNUM denominator;
+};
+
+#define HAS_EXACTLY_ONE_PARENT(n) ((n)->parents && !(n)->parents->next)
+
+static BN_CTX *context = NULL;
+static struct fraction *one = NULL;
+static struct fraction *zero = NULL;
+
+static BN_CTX *get_BN_CTX()
+{
+ if (!context) {
+ context = BN_CTX_new();
+ }
+ return context;
+}
+
+static struct fraction *new_zero()
+{
+ struct fraction *result = xmalloc(sizeof(*result));
+ BN_init(&result->numerator);
+ BN_init(&result->denominator);
+ BN_zero(&result->numerator);
+ BN_one(&result->denominator);
+ return result;
+}
+
+static void clear_fraction(struct fraction *fraction)
+{
+ BN_clear(&fraction->numerator);
+ BN_clear(&fraction->denominator);
+}
+
+static struct fraction *divide(struct fraction *result, struct fraction *fraction, int divisor)
+{
+ BIGNUM bn_divisor;
+
+ BN_init(&bn_divisor);
+ BN_set_word(&bn_divisor, divisor);
+
+ BN_copy(&result->numerator, &fraction->numerator);
+ BN_mul(&result->denominator, &fraction->denominator, &bn_divisor, get_BN_CTX());
+
+ BN_clear(&bn_divisor);
+ return result;
+}
+
+static struct fraction *init_fraction(struct fraction *fraction)
+{
+ BN_init(&fraction->numerator);
+ BN_init(&fraction->denominator);
+ BN_zero(&fraction->numerator);
+ BN_one(&fraction->denominator);
+ return fraction;
+}
+
+static struct fraction *get_one()
+{
+ if (!one) {
+ one = new_zero();
+ BN_one(&one->numerator);
+ }
+ return one;
+}
+
+static struct fraction *get_zero()
+{
+ if (!zero) {
+ zero = new_zero();
+ }
+ return zero;
+}
+
+static struct fraction *copy(struct fraction *to, struct fraction *from)
+{
+ BN_copy(&to->numerator, &from->numerator);
+ BN_copy(&to->denominator, &from->denominator);
+ return to;
+}
+
+static struct fraction *add(struct fraction *result, struct fraction *left, struct fraction *right)
+{
+ BIGNUM a, b, gcd;
+
+ BN_init(&a);
+ BN_init(&b);
+ BN_init(&gcd);
+
+ BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX());
+ BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX());
+ BN_mul(&result->denominator, &left->denominator, &right->denominator, get_BN_CTX());
+ BN_add(&result->numerator, &a, &b);
+
+ BN_gcd(&gcd, &result->denominator, &result->numerator, get_BN_CTX());
+ BN_div(&result->denominator, NULL, &result->denominator, &gcd, get_BN_CTX());
+ BN_div(&result->numerator, NULL, &result->numerator, &gcd, get_BN_CTX());
+
+ BN_clear(&a);
+ BN_clear(&b);
+ BN_clear(&gcd);
+
+ return result;
+}
+
+static int compare(struct fraction *left, struct fraction *right)
+{
+ BIGNUM a, b;
+
+ int result;
+
+ BN_init(&a);
+ BN_init(&b);
+
+ BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX());
+ BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX());
+
+ result = BN_cmp(&a, &b);
+
+ BN_clear(&a);
+ BN_clear(&b);
+
+ return result;
+}
+
+struct mass_counter {
+ struct fraction seen;
+ struct fraction pending;
+};
+
+static struct mass_counter *new_mass_counter(struct commit *commit, struct fraction *pending)
+{
+ struct mass_counter *mass_counter = xmalloc(sizeof(*mass_counter));
+ memset(mass_counter, 0, sizeof(*mass_counter));
+
+ init_fraction(&mass_counter->seen);
+ init_fraction(&mass_counter->pending);
+
+ copy(&mass_counter->pending, pending);
+ copy(&mass_counter->seen, get_zero());
+
+ commit->object.util = mass_counter;
+
+ return mass_counter;
+}
+
+static void free_mass_counter(struct mass_counter *counter)
+{
+ clear_fraction(&counter->seen);
+ clear_fraction(&counter->pending);
+ free(counter);
+}
+
+//
+// Finds the base node of an epoch.
+//
+// This algorithm uses a conservation of mass approach.
+//
+// The head starts with a weight of 1 and distributes equal portions
+// along each edge to each of its parents. The process continues until
+// one node discovers that it has acquired a total mass of 1 from its
+// descendents. This node is the base node.
+//
+// Importantly the queue of nodes to be processed is sorted in
+// reverse date order and each node occupies at most one
+// position in the queue simultaneously. These two properties
+// do not effect the algorithm's correctness. However assuming most, but
+// not all, timestamps are sane they do prevent the algorithm becoming
+// exponential by ensuring that most nodes are only visited once.
+// This is true because mass is only propagated through the network
+// when we are pretty sure we are not going to see any more coming
+// our way. The occasional bad timestamp will mean that we are
+// wrong, occasionally, but this does not matter too much.
+//
+static int find_base(struct commit *head, struct commit **boundary)
+{
+ int ret = 0;
+
+ struct commit_list *cleaner = NULL;
+ struct commit_list *pending = NULL;
+
+ *boundary = NULL;
+
+ // we inject a mass of 1 unit here
+
+ new_mass_counter(head, get_one());
+
+ commit_list_insert(head, &pending);
+ commit_list_insert(head, &cleaner);
+
+ while (!*boundary && pending && !ret) {
+
+ struct commit *latest = pop_commit(&pending);
+ struct mass_counter *latest_node = (struct mass_counter *) latest->object.util;
+
+ if ((ret = parse_commit(latest)))
+ continue;
+
+ add(&latest_node->seen, &latest_node->seen, &latest_node->pending);
+
+ int num_parents = count_parents(latest);
+
+ if (num_parents) {
+
+ struct fraction distribution;
+
+ divide(init_fraction(&distribution), &latest_node->pending, num_parents);
+
+ struct commit_list *parents;
+
+ for (parents = latest->parents; parents; parents = parents->next) {
+ struct commit *parent = parents->item;
+ struct mass_counter *parent_node = (struct mass_counter *) parent->object.util;
+ if (!parent_node) {
+ parent_node = new_mass_counter(parent, &distribution);
+ commit_list_insert(parent, &cleaner);
+ insert_by_date(&pending, parent);
+ } else {
+ if (!compare(&parent_node->pending, get_zero())) {
+ copy(&parent_node->pending, &distribution);
+ insert_by_date(&pending, parent);
+ } else {
+ add(&parent_node->pending, &parent_node->pending, &distribution);
+ }
+ }
+ }
+ }
+
+ if (!compare(&latest_node->seen, get_one()) && (latest != head)) {
+ // if this node has seen one unit of mass, it must be the base, so mark
+ // the boundary which will cause the loop to stop.
+ *boundary = latest;
+ }
+
+ copy(&latest_node->pending, get_zero());
+
+ }
+
+ for (; cleaner;) {
+ struct commit *next = pop_commit(&cleaner);
+ free_mass_counter((struct mass_counter *) next->object.util);
+ next->object.util = NULL;
+ }
+
+ if (pending)
+ free_commit_list(pending);
+
+ return ret;
+
+}
+
+//
+// This procedure traverses to the boundary of the first epoch in the epoch
+// sequence of the epoch headed at head_of_epoch. This is either the end of
+// the maximal linear epoch or the base of a minimal non-linear epoch.
+//
+// The queue of pending nodes is sorted in reverse date order and each node
+// is currently in the queue at most once.
+//
+static int find_next_epoch_boundary(struct commit *head_of_epoch, struct commit **boundary)
+{
+ int ret;
+ struct commit *item = head_of_epoch;
+
+ ret = parse_commit(item);
+ if (ret)
+ return ret;
+
+ if (HAS_EXACTLY_ONE_PARENT(item)) {
+
+ // we are at the start of a maximimal linear epoch .. traverse to the end
+
+ // traverse to the end of a maximal linear epoch
+ while (HAS_EXACTLY_ONE_PARENT(item) && !ret) {
+ item = item->parents->item;
+ ret = parse_commit(item);
+ }
+ *boundary = item;
+
+ } else {
+
+ // otherwise, we are at the start of a minimal, non-linear
+ // epoch - find the common base of all parents.
+
+ ret = find_base(item, boundary);
+
+ }
+
+ return ret;
+}
+
+//
+// Returns non-zero if parent is known to be a parent of child.
+//
+static int is_parent_of(struct commit *parent, struct commit *child)
+{
+ struct commit_list *parents;
+ for (parents = child->parents; parents; parents = parents->next) {
+ if (!memcmp(parent->object.sha1, parents->item->object.sha1, sizeof(parents->item->object.sha1)))
+ return 1;
+ }
+ return 0;
+}
+
+static void push_onto_merge_order_stack(struct commit_list **stack, struct commit *item)
+{
+ struct commit_list *top = *stack;
+ if (top && (top->item->object.flags & MERGE_ORDER_BREAK_FLAG)) {
+ if (is_parent_of(top->item, item)) {
+ top->item->object.flags &= ~MERGE_ORDER_BREAK_FLAG;
+ }
+ }
+ commit_list_insert(item, stack);
+}
+
+//
+// Sorts the nodes of the first epoch of the epoch sequence of the epoch headed at head
+// into merge order.
+//
+static void sort_first_epoch(struct commit *head, struct commit_list **stack)
+{
+ parse_commit(head);
+
+ head->object.flags |= MERGE_ORDER_VISIT_FLAG;
+
+ struct commit_list *parents;
+
+ struct commit_list *reversed_parents = NULL;
+
+ //
+ // parse_commit builds the parent list in reverse order with respect to the order of
+ // the git-commit-tree arguments.
+ //
+ // so we need to reverse this list to output the oldest (or most "local") commits last.
+ //
+
+ for (parents = head->parents; parents; parents = parents->next) {
+ commit_list_insert(parents->item, &reversed_parents);
+ }
+
+ //
+ // todo: by sorting the parents in a different order, we can alter the
+ // merge order to show contemporaneous changes in parallel branches
+ // occurring after "local" changes. This is useful for a developer
+ // when a developer wants to see all changes that were incorporated
+ // into the same merge as her own changes occur after her own
+ // changes.
+ //
+
+ for (; reversed_parents;) {
+ struct commit *parent = pop_commit(&reversed_parents);
+ parse_commit(parent);
+ if (!(parent->object.flags & MERGE_ORDER_VISIT_FLAG)) {
+ if (parent->object.flags & MERGE_ORDER_EPOCH_FLAG) {
+ if (*stack) {
+ die("something else is on the stack - %s\n", sha1_to_hex((*stack)->item->object.sha1));
+ }
+ push_onto_merge_order_stack(stack, parent);
+ parent->object.flags |= MERGE_ORDER_VISIT_FLAG;
+ } else {
+ sort_first_epoch(parent, stack);
+ if (reversed_parents) {
+ //
+ // this indicates a possible discontinuity
+ // it may not be be actual discontinuity if
+ // the head of parent N happens to be the tail
+ // of parent N+1
+ //
+ // the next push onto the stack will resolve the question
+ //
+ (*stack)->item->object.flags |= MERGE_ORDER_BREAK_FLAG;
+ }
+ }
+ }
+ }
+
+ push_onto_merge_order_stack(stack, head);
+}
+
+//
+// Sorts an arbitrary epoch into merge order by sorting each epoch
+// of its epoch sequence into order.
+//
+// Note: this algorithm currently leaves traces of its execution in the
+// object flags of nodes it discovers. This should probably be fixed.
+//
+int sort_in_merge_order(struct commit *head_of_epoch, emitter_func emitter)
+{
+ struct commit *next;
+ int ret = 0;
+ int stop = 0;
+
+ parse_commit(head_of_epoch);
+
+ for (next = head_of_epoch; next && next->parents && !ret && !stop;) {
+
+ struct commit *base = NULL;
+
+ ret = find_next_epoch_boundary(next, &base);
+ if (ret)
+ return ret;
+
+ next->object.flags |= MERGE_ORDER_EPOCH_FLAG;
+ if (base) {
+ base->object.flags |= MERGE_ORDER_EPOCH_FLAG;
+ }
+
+ if (HAS_EXACTLY_ONE_PARENT(next)) {
+
+ while (HAS_EXACTLY_ONE_PARENT(next) && !stop && !ret) {
+ stop = (*emitter) (next);
+ next = next->parents->item;
+ ret = parse_commit(next);
+ }
+
+ } else {
+
+ struct commit_list *stack = NULL;
+ sort_first_epoch(next, &stack);
+ for (; stack && !stop;) {
+ next = pop_commit(&stack);
+ if (stack) {
+ stop = (*emitter) (next);
+ }
+ }
+ if (stack) {
+ free_commit_list(stack);
+ }
+ }
+
+ }
+
+ if (next && !stop) {
+ stop = (*emitter) (next);
+ }
+
+ return ret;
+}
diff --git a/epoch.h b/epoch.h
new file mode 100644
--- /dev/null
+++ b/epoch.h
@@ -0,0 +1,12 @@
+#ifndef EPOCH_H
+#define EPOCH_H
+
+typedef int (*emitter_func) (struct commit *);
+
+int sort_in_merge_order(struct commit *head_of_epoch, emitter_func emitter);
+
+#define MERGE_ORDER_EPOCH_FLAG (1u<<3)
+#define MERGE_ORDER_VISIT_FLAG (1u<<4)
+#define MERGE_ORDER_BREAK_FLAG (1u<<5)
+
+#endif /* EPOCH_H */
diff --git a/object.h b/object.h
--- a/object.h
+++ b/object.h
@@ -15,6 +15,7 @@ struct object {
const char *type;
struct object_list *refs;
struct object_list *attached_deltas;
+ void *util;
};
extern int nr_objs;
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -1,5 +1,6 @@
#include "cache.h"
#include "commit.h"
+#include "epoch.h"
#define SEEN (1u << 0)
#define INTERESTING (1u << 1)
@@ -11,7 +12,8 @@ static const char rev_list_usage[] =
" --max-age=epoch\n"
" --min-age=epoch\n"
" --header\n"
- " --pretty";
+ " --pretty\n"
+ " --merge-order [ --show-breaks ]";
static int verbose_header = 0;
static int show_parents = 0;
@@ -21,27 +23,49 @@ static const char *prefix = "";
static unsigned long max_age = -1;
static unsigned long min_age = -1;
static int max_count = -1;
+static int merge_order = 0;
+static int show_breaks = 0;
-static void show_commit(struct commit *commit)
+static int show_commit(struct commit *commit)
{
- printf("%s%s", prefix, sha1_to_hex(commit->object.sha1));
- if (show_parents) {
- struct commit_list *parents = commit->parents;
- while (parents) {
- printf(" %s", sha1_to_hex(parents->item->object.sha1));
- parents = parents->next;
- }
- }
- putchar('\n');
- if (verbose_header) {
- const char *buf = commit->buffer;
- if (pretty_print) {
- static char pretty_header[16384];
- pretty_print_commit(commit->buffer, ~0, pretty_header, sizeof(pretty_header));
- buf = pretty_header;
- }
- printf("%s%c", buf, hdr_termination);
+ if (commit->object.flags & UNINTERESTING)
+ return 0;
+ if (min_age != -1 && (commit->date > min_age))
+ return 0;
+ if (max_age != -1 && (commit->date < max_age))
+ return 1;
+ if (max_count != -1 && !max_count--)
+ return 1;
+
+ if (!show_breaks) {
+ printf("%s%s", prefix, sha1_to_hex(commit->object.sha1));
+ if (show_parents) {
+ struct commit_list *parents = commit->parents;
+ while (parents) {
+ printf(" %s", sha1_to_hex(parents->item->object.sha1));
+ parents = parents->next;
+ }
+ }
+ putchar('\n');
+ if (verbose_header) {
+ const char *buf = commit->buffer;
+ if (pretty_print) {
+ static char pretty_header[16384];
+ pretty_print_commit(commit->buffer, ~0, pretty_header, sizeof(pretty_header));
+ buf = pretty_header;
+ }
+ printf("%s%c", buf, hdr_termination);
+ }
+ } else {
+ char c='|';
+ if (commit->object.flags & MERGE_ORDER_BREAK_FLAG) {
+ c = '^';
+ } else if (commit->object.flags & MERGE_ORDER_EPOCH_FLAG) {
+ c = '=';
+ }
+ printf("%c %s\n", c, sha1_to_hex(commit->object.sha1));
}
+ return 0;
}
static void show_commit_list(struct commit_list *list)
@@ -49,15 +73,8 @@ static void show_commit_list(struct comm
while (list) {
struct commit *commit = pop_most_recent_commit(&list, SEEN);
- if (commit->object.flags & UNINTERESTING)
- continue;
- if (min_age != -1 && (commit->date > min_age))
- continue;
- if (max_age != -1 && (commit->date < max_age))
- break;
- if (max_count != -1 && !max_count--)
- break;
- show_commit(commit);
+ if (show_commit(commit))
+ break;
}
}
@@ -142,8 +159,16 @@ int main(int argc, char **argv)
show_parents = 1;
continue;
}
+ if (!strncmp(arg, "--merge-order", 13)) {
+ merge_order = 1;
+ continue;
+ }
+ if (!strncmp(arg, "--show-breaks", 13)) {
+ show_breaks = 1;
+ continue;
+ }
- if (nr_sha > 2 || get_sha1(arg, sha1[nr_sha]))
+ if (nr_sha > 2 || get_sha1(arg, sha1[nr_sha])|| (show_breaks && !merge_order))
usage(rev_list_usage);
nr_sha++;
}
@@ -166,6 +191,14 @@ int main(int argc, char **argv)
if (end)
list = limit_list(list, end);
- show_commit_list(list);
+
+ if (!merge_order) {
+ show_commit_list(list);
+ } else {
+ if (sort_in_merge_order(commit, &show_commit)) {
+ die("merge order sort failed\n");
+ }
+ }
+
return 0;
}
diff --git a/t/t6000-rev-list.sh b/t/t6000-rev-list.sh
new file mode 100755
--- /dev/null
+++ b/t/t6000-rev-list.sh
@@ -0,0 +1,85 @@
+#!/bin/sh
+#
+# Copyright (c) 2005 Jon Seymour
+#
+
+test_description='Test rev-list --merge-order
+'
+. ./test-lib.sh
+
+function do_commit
+{
+ git-commit-tree "$@" </dev/null
+}
+
+function check_adjacency
+{
+ read previous
+ echo "= $previous"
+ while read next
+ do
+ if ! (git-cat-file commit $previous | grep "^parent $next" >/dev/null)
+ then
+ echo "^ $next"
+ else
+ echo "| $next"
+ fi
+ previous=$next
+ done
+}
+
+function sed_script
+{
+ for c in root a0 a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3
+ do
+ echo -n "s/${!c}/$c/;"
+ done
+}
+
+date >path0
+git-update-cache --add path0
+tree=$(git-write-tree)
+root=$(do_commit $tree)
+export GIT_COMMITTER_NAME=foobar # to guarantee that the commit is different
+a0=$(do_commit $tree -p $root)
+a1=$(do_commit $tree -p $a0)
+export GIT_COMMITTER_NAME=foobar2 # to guarantee that the commit is different
+b1=$(do_commit $tree -p $root)
+c1=$(do_commit $tree -p $b1)
+export GIT_COMMITTER_NAME=foobar3 # to guarantee that the commit is different
+b2=$(do_commit $tree -p $b1)
+b3=$(do_commit $tree -p $b2)
+c2=$(do_commit $tree -p $c1 -p $b2)
+c3=$(do_commit $tree -p $c2)
+a2=$(do_commit $tree -p $a1)
+a3=$(do_commit $tree -p $a2)
+b4=$(do_commit $tree -p $b3 -p $a3)
+a4=$(do_commit $tree -p $a3 -p $b4 -p $c3)
+echo $a4 > .git/HEAD
+
+git-rev-list --merge-order --show-breaks HEAD | sed "$(sed_script)" > actual-merge-order
+cat > expected-merge-order <<EOF
+= a4
+| c3
+| c2
+| c1
+^ b4
+| b3
+| b2
+| b1
+^ a3
+| a2
+| a1
+| a0
+= root
+EOF
+
+git-rev-list HEAD | check_adjacency | sed "$(sed_script)" > actual-default-order
+normal_adjacency_count=$(git-rev-list HEAD | check_adjacency | grep -c "\^" | tr -d ' ')
+merge_order_adjacency_count=$(git-rev-list --merge-order HEAD | check_adjacency | grep -c "\^" | tr -d ' ')
+
+test_expect_success 'Testing that the rev-list has correct number of entries' '[ $(git-rev-list HEAD | wc -l) -eq 13 ]'
+test_expect_success 'Testing that --merge-order produces the correct result' 'diff expected-merge-order actual-merge-order'
+test_expect_success 'Testing that --merge-order produces as many or fewer discontinuities' '[ $merge_order_adjacency_count -le $normal_adjacency_count ]'
+
+test_done
^ permalink raw reply
* [PATCH Cogito] Add -f parameter also to cg-update
From: Marcel Holtmann @ 2005-06-04 6:25 UTC (permalink / raw)
To: Petr Baudis; +Cc: GIT Mailing List
[-- Attachment #1: Type: text/plain, Size: 164 bytes --]
Hi Petr,
the attached patch adds the -f parameter to force a full pull also to
cg-update.
Regards
Marcel
Signed-off-by: Marcel Holtmann <marcel@holtmann.org>
[-- Attachment #2: patch --]
[-- Type: text/x-patch, Size: 666 bytes --]
diff --git a/cg-update b/cg-update
--- a/cg-update
+++ b/cg-update
@@ -7,16 +7,27 @@
#
# If local changes conflict with those of the branch updated from the
# merge will be blocked.
+#
+# OPTIONS
+# -------
+# -f::
+# Force the complete pull even if the heads are the same.
-USAGE="cg-update [BRANCH_NAME]"
+USAGE="cg-update [-f] [BRANCH_NAME]"
. ${COGITO_LIB}cg-Xlib
+force=
+if [ "$1" = "-f" ]; then
+ force=$1
+ shift
+fi
+
name=$1
[ "$name" ] || { [ -s $_git/refs/heads/origin ] && name=origin; }
[ "$name" ] || die "where to update from?"
-cg-pull $name || exit 1
+cg-pull $force $name || exit 1
echo
echo "Applying changes..."
cg-merge $name
^ permalink raw reply
* [PATCH] diffcore-break.c: various fixes.
From: Junio C Hamano @ 2005-06-04 6:05 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
This fixes three bugs in the -B heuristics.
- Although it was advertised that the initial break criteria
used was the same as what diffcore-rename uses, it was using
something different. Instead of using smaller of src and dst
size to compare with "edit" size, (insertion and deletion),
it was using larger of src and dst, unlike the rename/copy
detection logic. This caused the parameter to -B to mean
something different from the one to -M and -C. To compensate
for this change, the default break score is also changed to
match that of the default for rename/copy.
- The code would have crashed with division by zero when trying
to break an originally empty file.
- Contrary to what the comment said, the algorithm was breaking
small files, only to later merge them together.
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
diffcore.h | 2 +-
diffcore-break.c | 22 ++++++++--------------
2 files changed, 9 insertions(+), 15 deletions(-)
diff --git a/diffcore.h b/diffcore.h
--- a/diffcore.h
+++ b/diffcore.h
@@ -17,7 +17,7 @@
*/
#define MAX_SCORE 60000
#define DEFAULT_RENAME_SCORE 30000 /* rename/copy similarity minimum (50%) */
-#define DEFAULT_BREAK_SCORE 59400 /* minimum for break to happen (99%)*/
+#define DEFAULT_BREAK_SCORE 30000 /* minimum for break to happen (50%)*/
#define DEFAULT_MERGE_SCORE 48000 /* maximum for break-merge to happen (80%)*/
#define MINIMUM_BREAK_SIZE 400 /* do not break a file smaller than this */
diff --git a/diffcore-break.c b/diffcore-break.c
--- a/diffcore-break.c
+++ b/diffcore-break.c
@@ -61,14 +61,7 @@ static int should_break(struct diff_file
if (diff_populate_filespec(src, 0) || diff_populate_filespec(dst, 0))
return 0; /* error but caught downstream */
- delta_size = ((src->size < dst->size) ?
- (dst->size - src->size) : (src->size - dst->size));
-
- /* Notice that we use max of src and dst as the base size,
- * unlike rename similarity detection. This is so that we do
- * not mistake a large addition as a complete rewrite.
- */
- base_size = ((src->size < dst->size) ? dst->size : src->size);
+ base_size = ((src->size < dst->size) ? src->size : dst->size);
delta = diff_delta(src->data, src->size,
dst->data, dst->size,
@@ -88,10 +81,11 @@ static int should_break(struct diff_file
* less than the minimum, after rename/copy runs.
*/
if (src->size <= src_copied)
- delta_size = 0; /* avoid wrapping around */
- else
+ ; /* all copied, nothing removed */
+ else {
delta_size = src->size - src_copied;
- *merge_score_p = delta_size * MAX_SCORE / src->size;
+ *merge_score_p = delta_size * MAX_SCORE / src->size;
+ }
/* Extent of damage, which counts both inserts and
* deletes.
@@ -174,7 +168,8 @@ void diffcore_break(int break_score)
!S_ISDIR(p->one->mode) && !S_ISDIR(p->two->mode) &&
!strcmp(p->one->path, p->two->path)) {
if (should_break(p->one, p->two,
- break_score, &score)) {
+ break_score, &score) &&
+ MINIMUM_BREAK_SIZE <= p->one->size) {
/* Split this into delete and create */
struct diff_filespec *null_one, *null_two;
struct diff_filepair *dp;
@@ -185,8 +180,7 @@ void diffcore_break(int break_score)
* Also we do not want to break very
* small files.
*/
- if ((score < merge_score) ||
- (p->one->size < MINIMUM_BREAK_SIZE))
+ if (score < merge_score)
score = 0;
/* deletion of one */
------------
^ permalink raw reply
* [PATCH] diff.c: -B argument passing fix.
From: Junio C Hamano @ 2005-06-04 6:04 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
This fixes a bug that was preventing non-default parameter to -B
option to be passed correctly; you could not give more than 50%
break score.
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
diff.c | 4 ++--
1 files changed, 2 insertions(+), 2 deletions(-)
diff --git a/diff.c b/diff.c
--- a/diff.c
+++ b/diff.c
@@ -964,11 +964,11 @@ void diffcore_std(const char **paths,
{
if (paths && paths[0])
diffcore_pathspec(paths);
- if (0 <= break_opt)
+ if (break_opt != -1)
diffcore_break(break_opt);
if (detect_rename)
diffcore_rename(detect_rename, rename_score);
- if (0 <= break_opt)
+ if (break_opt != -1)
diffcore_merge_broken();
if (pickaxe)
diffcore_pickaxe(pickaxe, pickaxe_opts);
------------
^ permalink raw reply
* [PATCH] diff.c: locate_size_cache() fix.
From: Junio C Hamano @ 2005-06-04 6:02 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
This fixes two bugs.
- declaration of auto variable "cmp" was preceeded by a
statement, causing compilation error on real C compilers;
noticed and patch given by Yoichi Yuasa.
- the function's calling convention was overloading its size
parameter to mean "largest possible value means do not add
entry", which was a bad taste. Brought up during a
discussion with Peter Baudis.
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
diff.c | 11 ++++++-----
1 files changed, 6 insertions(+), 5 deletions(-)
diff --git a/diff.c b/diff.c
--- a/diff.c
+++ b/diff.c
@@ -236,6 +236,7 @@ static struct sha1_size_cache {
static int sha1_size_cache_nr, sha1_size_cache_alloc;
static struct sha1_size_cache *locate_size_cache(unsigned char *sha1,
+ int find_only,
unsigned long size)
{
int first, last;
@@ -244,9 +245,9 @@ static struct sha1_size_cache *locate_si
first = 0;
last = sha1_size_cache_nr;
while (last > first) {
- int next = (last + first) >> 1;
+ int cmp, next = (last + first) >> 1;
e = sha1_size_cache[next];
- int cmp = memcmp(e->sha1, sha1, 20);
+ cmp = memcmp(e->sha1, sha1, 20);
if (!cmp)
return e;
if (cmp < 0) {
@@ -256,7 +257,7 @@ static struct sha1_size_cache *locate_si
first = next+1;
}
/* not found */
- if (size == UINT_MAX)
+ if (find_only)
return NULL;
/* insert to make it at "first" */
if (sha1_size_cache_alloc <= sha1_size_cache_nr) {
@@ -337,13 +338,13 @@ int diff_populate_filespec(struct diff_f
struct sha1_size_cache *e;
if (size_only) {
- e = locate_size_cache(s->sha1, UINT_MAX);
+ e = locate_size_cache(s->sha1, 1, 0);
if (e) {
s->size = e->size;
return 0;
}
if (!sha1_file_size(s->sha1, &s->size))
- locate_size_cache(s->sha1, s->size);
+ locate_size_cache(s->sha1, 0, s->size);
}
else {
s->data = read_sha1_file(s->sha1, type, &s->size);
------------
^ permalink raw reply
* 'shortlog' script for git
From: Jeff Garzik @ 2005-06-04 5:49 UTC (permalink / raw)
To: Linux Kernel, Git Mailing List
[-- Attachment #1: Type: text/plain, Size: 515 bytes --]
I've been wanting a shortlog script for summarizing my kernel
submissions to Linus for a while. This is now written, and the results
are attached. Simply use like
git-shortlog < changes.txt
or
git-shortlog changes.txt
The changeset format the Perl script parses is that of
http://www.kernel.org/pub/linux/kernel/people/jgarzik/git-changes-script
I'll change it to parse the git-whatchanged output format sometime soon;
Linus hates it when I use git-changes-script since he thinks its ugly :)
Jeff
[-- Attachment #2: git-shortlog --]
[-- Type: text/plain, Size: 1263 bytes --]
#!/usr/bin/perl -w
use strict;
my ($author, $desc, %map);
my $pstate = 1;
while (<>) {
# skip to '^commit '
if ($pstate == 1) {
next unless /^commit /;
$pstate++;
}
# get author
elsif ($pstate == 2) {
next unless /^author (.*) \S+ \S+ \S+ \S+ \S+ \S+\s*$/;
$author = $1;
$pstate++;
}
# skip to blank line
elsif ($pstate == 3) {
next unless /^\s*$/;
$pstate++;
}
# skip to non-blank line
elsif ($pstate == 4) {
next if /^\s*$/;
chomp;
$desc = $_;
&shortlog_entry($author, $desc);
$pstate = 1;
}
else {
die "invalid parse state $pstate";
}
}
&shortlog_output;
exit(0);
sub shortlog_entry($$) {
my ($tmp_author, $tmp_desc) = @_;
my ($obj);
$tmp_desc =~ s#/pub/scm/linux/kernel/git/#/.../#g;
$tmp_desc =~ s/^\[PATCH] //g;
$tmp_desc =~ s/^\s+//g;
if (exists $map{$tmp_author}) {
# grab ref
$obj = $map{$tmp_author};
# add desc to array
push(@$obj, $tmp_desc);
} else {
# create ref to new array
my @arr = ($tmp_desc);
$obj = \@arr;
# store new entry in author map
$map{$tmp_author} = $obj;
}
}
sub shortlog_output {
my ($obj);
foreach $author (sort keys %map) {
print "$author:\n";
$obj = $map{$author};
foreach $desc (@$obj) {
print " $desc\n";
}
print "\n";
}
}
^ permalink raw reply
* Re: [PATCH 12/12] Optimize diff-tree -[CM] --stdin
From: Yoichi Yuasa @ 2005-06-04 2:17 UTC (permalink / raw)
To: Junio C Hamano; +Cc: yuasa, torvalds, git
In-Reply-To: <7vhdgo2s7t.fsf_-_@assigned-by-dhcp.cox.net>
Hi,
On Fri, 27 May 2005 15:56:38 -0700
Junio C Hamano <junkio@cox.net> wrote:
>
<snip>
> diff --git a/diff.c b/diff.c
> --- a/diff.c
> +++ b/diff.c
> @@ -12,6 +12,7 @@ static const char *diff_opts = "-pu";
> static unsigned char null_sha1[20] = { 0, };
>
> static int reverse_diff;
> +static int use_size_cache;
>
> static const char *external_diff(void)
> {
> @@ -222,12 +223,60 @@ static int work_tree_matches(const char
> return 1;
> }
>
> +static struct sha1_size_cache {
> + unsigned char sha1[20];
> + unsigned long size;
> +} **sha1_size_cache;
> +static int sha1_size_cache_nr, sha1_size_cache_alloc;
> +
> +static struct sha1_size_cache *locate_size_cache(unsigned char *sha1,
> + unsigned long size)
> +{
> + int first, last;
> + struct sha1_size_cache *e;
> +
> + first = 0;
> + last = sha1_size_cache_nr;
> + while (last > first) {
> + int next = (last + first) >> 1;
> + e = sha1_size_cache[next];
> + int cmp = memcmp(e->sha1, sha1, 20);
I got build error in diff.c
Please apply the following patch.
Thanks,
Yoichi
Signed-off-by: Yoichi Yuasa <yuasa@hh.iij4u.or.jp>
diff --git a/diff.c b/diff.c
--- a/diff.c
+++ b/diff.c
@@ -244,9 +244,9 @@ static struct sha1_size_cache *locate_si
first = 0;
last = sha1_size_cache_nr;
while (last > first) {
- int next = (last + first) >> 1;
+ int cmp, next = (last + first) >> 1;
e = sha1_size_cache[next];
- int cmp = memcmp(e->sha1, sha1, 20);
+ cmp = memcmp(e->sha1, sha1, 20);
if (!cmp)
return e;
if (cmp < 0) {
^ permalink raw reply
* Re: How stop tracking a file?
From: Petr Baudis @ 2005-06-04 1:24 UTC (permalink / raw)
To: jeff millar; +Cc: Junio C Hamano, git
In-Reply-To: <4290CF85.5060105@adelphia.net>
Dear diary, on Sun, May 22, 2005 at 08:29:25PM CEST, I got a letter
where jeff millar <wa1hco@adelphia.net> told me that...
> Junio C Hamano wrote:
>
> > jm> cg-rm does two things
> > jm> rm -f "$@"
> > jm> git-update-cache --remove -- "$@"
> >
> >I do not do Porcelain, but something along the following lines
> >should work:
> >
> > for path
> > do
> > git-update-cache --force-remove "$path"
> > done
> >
> Seems a bit more difficult...
> [jeff@Desk gsmc-1.1]$ git-update-cache --force-remove main.o
> [jeff@Desk gsmc-1.1]$ cg-diff
> Index: main.o
> ===================================================================
> Binary files a5d1a55e0818ab11b71fee01bcd9053c4ecc65a6/main.o
> (mode:100644) and /dev/null (tree:uncommitted) differ
> [jeff@Desk gsmc-1.1]$ cg-commit
> Refusing to make an empty commit - the tree was not modified
> since the previous commit. If you really want to make the
> commit, do: commit-tree `tree-id` -p `parent-id`
> A picky porcelain problem?
Ok, it took some non-trivial changes to cg-commit (this part was a quick
hack before, now it looks a lot better), but cg-rm -n should now do what
you want.
Thanks for the suggestion,
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
C++: an octopus made by nailing extra legs onto a dog. -- Steve Taylor
^ permalink raw reply
* Re: [PATCH] git-daemon server
From: Daniel Barkalow @ 2005-06-04 0:06 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Jason McMullan, git
In-Reply-To: <Pine.LNX.4.58.0506031450190.1876@ppc970.osdl.org>
On Fri, 3 Jun 2005, Linus Torvalds wrote:
>
>
> On Fri, 3 Jun 2005, Daniel Barkalow wrote:
> >
> > Is this somehow different from rpush/rpull aside from using an
> > externally-provided socket and having the proper locking for writing refs
> > (which I posted a while ago, but which hasn't been included anywhere yet)?
>
> Deathmatch!
>
> Anyway, I have to admit that at least as far as I'm concerned, the
> rpull/rpush thing has the same issues as Jason's code - I've not seen the
> usage documented anywhere, and that's the only real reason I don't use it
> myself.
See below. I'd foolishly explained http-pull and rpull, but neglected to
mention that rpush is actually useful in its own right. It is used in
essentially the same way, but on the other computer. (And I need to fix
the Documentation/ file, since other people seem to have missed it, too)
> Also, just out of interest, do either or both of these things pipeline the
> transfer?
Mine doesn't currently. The protocol supports a low level of pipelining
(you can request all the objects you know you want, and the sending side
doesn't care that you're sending requests before the previous ones are
satisfied), but I haven't figured out (or found out from Matt, more
likely) a good way to negotiate something more clever.
> Me, I want to have a fairly simple script that does the equivalent of what
> I do now for pushing:
>
> rsync -av --delete --exclude-from=.exclude .git/ master.kernel.org:/pub/scm/linux/kernel/git/torvalds/linux-2.6.git
>
> except I'd want it to do the locking and the "only accept trivial pushes"
> stuff (ie no merging, just a pure update).
With patches I have (but have to rebase and such), you could do:
git-rpush -a -w heads/master heads/master //master.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6.git
This would only send the heads/master file and all of the object files it
references. It would be easy to write a "--old heads/linus" which would
require that the remote value was the local value of heads/linus (I.e.,
the public value of your head that you'd been working from).
> Maybe git-rpush does this already, and I just never realized.
It currently does all the objects, but doesn't write the refs file on the
remote end. That is:
git-rpush -a heads/master //master.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6.git
Will cause the public tree to contain all the objects reachable from the
local value of heads/master. Then you need to write the new head by hand
if you don't have the newer stuff.
-Daniel
*This .sig left intentionally blank*
^ permalink raw reply
* Re: [PATCH] Use correct U*MAX.
From: Junio C Hamano @ 2005-06-04 0:09 UTC (permalink / raw)
To: Petr Baudis; +Cc: Linus Torvalds, git
In-Reply-To: <20050604000042.GG13093@pasky.ji.cz>
>>>>> "PB" == Petr Baudis <pasky@ucw.cz> writes:
>> I'd rather see it use the correct U*MAX.
PB> Care to elaborate? It doesn't make sense to me to use any U*MAX stuff
PB> there whatsoever. (And how do you define the "correct" U*MAX anyway?)
It just feels wrong to spell a parameter to the function
locate_size_cache() "-1" when I know the argument it expects is
of type unsigned long. And correct U*MAX for that case is
obviously ULONG_MAX, _assuming_ that you agree to the function's
(unwritten) calling convention of "passing the largest possible
value to me means 'do not create', not 'you are telling me that
sha1 is such a large file'".
If you feel strongly about that calling convention, you could
rewrite it to take the third argument "int do_not_create" and
pass that information separately, which is conceptually cleaner.
I just did not think that was worth it for such an internal
helper when I wrote it.
^ permalink raw reply
* Re: [PATCH] Use correct U*MAX.
From: Petr Baudis @ 2005-06-04 0:00 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Linus Torvalds, git
In-Reply-To: <7v4qcfko0q.fsf@assigned-by-dhcp.cox.net>
Dear diary, on Sat, Jun 04, 2005 at 01:40:21AM CEST, I got a letter
where Junio C Hamano <junkio@cox.net> told me that...
> I'd rather see it use the correct U*MAX.
Care to elaborate? It doesn't make sense to me to use any U*MAX stuff
there whatsoever. (And how do you define the "correct" U*MAX anyway?)
P.S.: Could you please always keep at least some context in the mail?
Thanks.
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
C++: an octopus made by nailing extra legs onto a dog. -- Steve Taylor
^ permalink raw reply
* Re: [PATCH] Use correct U*MAX.
From: Junio C Hamano @ 2005-06-03 23:40 UTC (permalink / raw)
To: Petr Baudis; +Cc: Linus Torvalds, git
In-Reply-To: <20050603230234.GC13093@pasky.ji.cz>
I'd rather see it use the correct U*MAX.
^ permalink raw reply
* Re: [PATCH] Use correct U*MAX.
From: Petr Baudis @ 2005-06-03 23:02 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Linus Torvalds, git
In-Reply-To: <7vwtpc7lju.fsf_-_@assigned-by-dhcp.cox.net>
Dear diary, on Thu, Jun 02, 2005 at 06:47:33PM CEST, I got a letter
where Junio C Hamano <junkio@cox.net> told me that...
> The largest "unsigned long" value is ULONG_MAX, not UINT_MAX.
>
> Signed-off-by: Junio C Hamano <junkio@cox.net>
> diff --git a/diff.c b/diff.c
> --- a/diff.c
> +++ b/diff.c
> @@ -256,7 +256,7 @@ static struct sha1_size_cache *locate_si
> first = next+1;
> }
> /* not found */
> - if (size == UINT_MAX)
> + if (size == ULONG_MAX)
> return NULL;
> /* insert to make it at "first" */
> if (sha1_size_cache_alloc <= sha1_size_cache_nr) {
> @@ -338,7 +338,7 @@ int diff_populate_filespec(struct diff_f
> struct sha1_size_cache *e;
>
> if (size_only) {
> - e = locate_size_cache(s->sha1, UINT_MAX);
> + e = locate_size_cache(s->sha1, ULONG_MAX);
> if (e) {
> s->size = e->size;
> return 0;
This one still applies, but it might be better to get rid of it
altogether, like...
[PATCH] Kill UINT_MAX usage in locate_size_cache()
Use -1 instead of UINT_MAX to indicate that locate_size_cache() should
do only the lookup and not create new stuff in case the looked up hash
was not found.
Signed-off-by: Petr Baudis <pasky@ucw.cz>
diff --git a/diff.c b/diff.c
--- a/diff.c
+++ b/diff.c
@@ -256,7 +256,7 @@ static struct sha1_size_cache *locate_si
first = next+1;
}
/* not found */
- if (size == UINT_MAX)
+ if (size == -1)
return NULL;
/* insert to make it at "first" */
if (sha1_size_cache_alloc <= sha1_size_cache_nr) {
@@ -337,7 +337,7 @@ int diff_populate_filespec(struct diff_f
struct sha1_size_cache *e;
if (size_only) {
- e = locate_size_cache(s->sha1, UINT_MAX);
+ e = locate_size_cache(s->sha1, -1);
if (e) {
s->size = e->size;
return 0;
|
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
C++: an octopus made by nailing extra legs onto a dog. -- Steve Taylor
^ permalink raw reply
* Re: [PATCH] ssh-protocol version, command types, response code
From: Petr Baudis @ 2005-06-03 22:49 UTC (permalink / raw)
To: Daniel Barkalow; +Cc: Linus Torvalds, git
In-Reply-To: <Pine.LNX.4.21.0506031740020.30848-100000@iabervon.org>
Dear diary, on Fri, Jun 03, 2005 at 11:43:52PM CEST, I got a letter
where Daniel Barkalow <barkalow@iabervon.org> told me that...
> This patch makes an incompatible change to the protocol used by
> rpull/rpush which will let it be extended in the future without
> incompatible changes.
>
> Signed-off-by: Daniel Barkalow <barkalow@iabervon.org>
It looks fine by me. Linus? (I would really like to see this in.)
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
C++: an octopus made by nailing extra legs onto a dog. -- Steve Taylor
^ permalink raw reply
* Re: [PATCH] git-daemon server
From: Petr Baudis @ 2005-06-03 22:39 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Daniel Barkalow, Jason McMullan, git
In-Reply-To: <Pine.LNX.4.58.0506031450190.1876@ppc970.osdl.org>
Dear diary, on Fri, Jun 03, 2005 at 11:59:38PM CEST, I got a letter
where Linus Torvalds <torvalds@osdl.org> told me that...
> Anyway, I have to admit that at least as far as I'm concerned, the
> rpull/rpush thing has the same issues as Jason's code - I've not seen the
> usage documented anywhere, and that's the only real reason I don't use it
> myself.
FWIW, Cogito's cg-pull can use rpull/rpush (if your branch URLs use the
git+ssh scheme), and I've seen people actually using it.
--
Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
C++: an octopus made by nailing extra legs onto a dog. -- Steve Taylor
^ permalink raw reply
* Re: qgit-0.3
From: Benjamin Herrenschmidt @ 2005-06-03 22:37 UTC (permalink / raw)
To: Radoslaw Szkodzinski; +Cc: git
In-Reply-To: <42A04AAA.4080205@gorzow.mm.pl>
On Fri, 2005-06-03 at 14:18 +0200, Radoslaw Szkodzinski wrote:
> It is buildable, but you need to install your own scons in the correct
> paths, e.g.
> on Gentoo:
>
> emerge scons
> And then build it by hand with:
> ./configure
> scons
>
> Then you get bin/qgit which is ready to run and/or copy.
Not on debian. Doesn't work with the disto's scons, says it can't find
qt (and libqt3-dev is installed)
Ben.
^ permalink raw reply
* [PATCH] Modify git-rev-list ... [ resend to fix whitespace mangle ]
From: Jon Seymour @ 2005-06-03 22:34 UTC (permalink / raw)
To: Git Mailing List
In-Reply-To: <2cfc4032050603153419b72444@mail.gmail.com>
On 6/4/05, Junio C Hamano <junkio@cox.net> wrote:
> I only fast-forwarded over maths on your website about the epoch
> ordering, but what the patch tries to do sounds right to me.
>
> One nitpick request I have is to name its test t6000 series, to
> match the naming convention Pasky came up with?
>
> First digit tells the family:
>
> 0 - the absolute basics and global stuff
> 1 - the basic commands concerning database
> 2 - the basic commands concerning the working tree
> 3 - the other basic commands (e.g. ls-files)
> 4 - the diff commands
> 5 - the pull and exporting commands
> 6 - the revision tree commands (even e.g. merge-base)
>
Sure. I'll modify the patch and repost.
> Also I wonder what the performance implication of this patch is.
>
It actually works quite well. I took some care to make sure the
algorithm didn't have to scan the entire tree if you only want part of
it and is roughly linear in the number of edges it actually processes.
It does this by borrowing the original heuristic of a latest date
first scan, and also by accumulating "work" to do prior to propagating
it through the network. This means that most nodes are only visited (a
small-multiple of) once.
One thing to be aware of is that it does have to scan to epoch
boundaries which, in the Linux kernel, are spaced an average of 100
commits apart. The first time you run it on a cold-cache, the output
pauses for a while after the first few commits. But run it again when
the cache is warm and the performance is, IMO, quite ok.
Here are the cold-cache stats on the Linux-2.6 tree which has 1300
commits and quite a lot of merges and forks
$ time git-rev-list --merge-order --show-breaks HEAD > out 2>err
real 0m32.283s
user 0m0.135s
sys 0m0.141s
And the warm cache stats:
$ time git-rev-list --merge-order --show-breaks HEAD > out 2>err
real 0m0.181s
user 0m0.119s
sys 0m0.040s
Compared with the standard algorithm:
$ time git-rev-list HEAD > out 2>err
real 0m0.112s
user 0m0.065s
sys 0m0.032s
So, it is perhaps 50-100% slower on a warm-cache than the standard algorithm.
jon.
--
homepage: http://www.zeta.org.au/~jon/
blog: http://orwelliantremors.blogspot.com/
^ permalink raw reply
* Re: [PATCH] git-daemon server
From: Daniel Serpell @ 2005-06-03 22:01 UTC (permalink / raw)
To: GIT Mailling list
In-Reply-To: <Pine.LNX.4.58.0506031410560.1876@ppc970.osdl.org>
On 6/3/05, Linus Torvalds <torvalds@osdl.org> wrote:
>
> On Fri, 3 Jun 2005, McMullan, Jason wrote:
> >
> > 3) Because I can't figure out how to get /bin/sh to give me two pipes
> > that hook together two processes. What I really want:
> >
> > ssh user@remote git server --db /my/git.git <|> git server request HEAD
>
> Ok, so a ssh connection _would_ work per se, and the only real issue is
> the pipe itself is one-directional as done by the shell?
>
[...]
> Anyway, with _something_ like the above you could do something like
>
> git-sync --exec "ssh master.kernel.org git-sync" ....
>
> and it would do the obvious thing.
>
I would prefer a command line more like the rsync one:
git-sync master.kernel.org:directory ....
Or:
git-sync :ssh:master.kernel.org:directory ....
Or "uri like":
git-sync ssh://mylogin@master.kernel.org/directory ....
It seems much easier, and I suppose that SSH should be the
default "developer" protocol.
Daniel.
^ permalink raw reply
* Re: [PATCH] git-daemon server
From: Linus Torvalds @ 2005-06-03 21:59 UTC (permalink / raw)
To: Daniel Barkalow; +Cc: Jason McMullan, git
In-Reply-To: <Pine.LNX.4.21.0506031727400.30848-100000@iabervon.org>
On Fri, 3 Jun 2005, Daniel Barkalow wrote:
>
> Is this somehow different from rpush/rpull aside from using an
> externally-provided socket and having the proper locking for writing refs
> (which I posted a while ago, but which hasn't been included anywhere yet)?
Deathmatch!
Anyway, I have to admit that at least as far as I'm concerned, the
rpull/rpush thing has the same issues as Jason's code - I've not seen the
usage documented anywhere, and that's the only real reason I don't use it
myself.
Also, just out of interest, do either or both of these things pipeline the
transfer?
Me, I want to have a fairly simple script that does the equivalent of what
I do now for pushing:
rsync -av --delete --exclude-from=.exclude .git/ master.kernel.org:/pub/scm/linux/kernel/git/torvalds/linux-2.6.git
except I'd want it to do the locking and the "only accept trivial pushes"
stuff (ie no merging, just a pure update).
Maybe git-rpush does this already, and I just never realized.
Linus
^ permalink raw reply
* [PATCH] ssh-protocol version, command types, response code
From: Daniel Barkalow @ 2005-06-03 21:43 UTC (permalink / raw)
To: Petr Baudis, Linus Torvalds; +Cc: git
This patch makes an incompatible change to the protocol used by
rpull/rpush which will let it be extended in the future without
incompatible changes.
Signed-off-by: Daniel Barkalow <barkalow@iabervon.org>
Index: rpull.c
===================================================================
--- 33942306faa3093107cc7105dff046de5c981d2e/rpull.c (mode:100644 sha1:36e49f799a6ac300a00f8d09d9dc9e6636b3d8e0)
+++ 1f3a64b193531d17cafb7db8aae4a08d92be3132/rpull.c (mode:100644 sha1:a3d13595d3db6c26d4d55fe7ef516efd5c8f6a0c)
@@ -6,16 +6,39 @@
static int fd_in;
static int fd_out;
+static unsigned char remote_version = 0;
+static unsigned char local_version = 1;
+
int fetch(unsigned char *sha1)
{
int ret;
+ signed char remote;
+ char type = 'o';
+ if (has_sha1_file(sha1))
+ return 0;
+ write(fd_out, &type, 1);
write(fd_out, sha1, 20);
+ if (read(fd_in, &remote, 1) < 1)
+ return -1;
+ if (remote < 0)
+ return remote;
ret = write_sha1_from_fd(sha1, fd_in);
if (!ret)
pull_say("got %s\n", sha1_to_hex(sha1));
return ret;
}
+int get_version(void)
+{
+ char type = 'v';
+ write(fd_out, &type, 1);
+ write(fd_out, &local_version, 1);
+ if (read(fd_in, &remote_version, 1) < 1) {
+ return error("Couldn't read version from remote end");
+ }
+ return 0;
+}
+
int main(int argc, char **argv)
{
char *commit_id;
@@ -46,6 +69,9 @@
if (setup_connection(&fd_in, &fd_out, "git-rpush", url, arg, argv + 1))
return 1;
+ if (get_version())
+ return 1;
+
if (pull(commit_id))
return 1;
Index: rpush.c
===================================================================
--- 33942306faa3093107cc7105dff046de5c981d2e/rpush.c (mode:100644 sha1:17d5ab8a60ab2ec7fa3a7dc927351e8a34de3a89)
+++ 1f3a64b193531d17cafb7db8aae4a08d92be3132/rpush.c (mode:100644 sha1:bd381ac9d1787dc979b1eba5bd72c1fd644a094b)
@@ -3,46 +3,81 @@
#include <sys/socket.h>
#include <errno.h>
-static void service(int fd_in, int fd_out) {
+unsigned char local_version = 1;
+unsigned char remote_version = 0;
+
+int serve_object(int fd_in, int fd_out) {
ssize_t size;
- int posn;
- char unsigned sha1[20];
+ int posn = 0;
+ char sha1[20];
unsigned long objsize;
void *buf;
+ signed char remote;
+ do {
+ size = read(fd_in, sha1 + posn, 20 - posn);
+ if (size < 0) {
+ perror("git-rpush: read ");
+ return -1;
+ }
+ if (!size)
+ return -1;
+ posn += size;
+ } while (posn < 20);
+
+ /* fprintf(stderr, "Serving %s\n", sha1_to_hex(sha1)); */
+ remote = 0;
+
+ buf = map_sha1_file(sha1, &objsize);
+
+ if (!buf) {
+ fprintf(stderr, "git-rpush: could not find %s\n",
+ sha1_to_hex(sha1));
+ remote = -1;
+ }
+
+ write(fd_out, &remote, 1);
+
+ if (remote < 0)
+ return 0;
+
+ posn = 0;
do {
- posn = 0;
- do {
- size = read(fd_in, sha1 + posn, 20 - posn);
- if (size < 0) {
- perror("git-rpush: read ");
- return;
+ size = write(fd_out, buf + posn, objsize - posn);
+ if (size <= 0) {
+ if (!size) {
+ fprintf(stderr, "git-rpush: write closed");
+ } else {
+ perror("git-rpush: write ");
}
- if (!size)
- return;
- posn += size;
- } while (posn < 20);
-
- /* fprintf(stderr, "Serving %s\n", sha1_to_hex(sha1)); */
-
- buf = map_sha1_file(sha1, &objsize);
- if (!buf) {
- fprintf(stderr, "git-rpush: could not find %s\n",
- sha1_to_hex(sha1));
+ return -1;
+ }
+ posn += size;
+ } while (posn < objsize);
+ return 0;
+}
+
+int serve_version(int fd_in, int fd_out)
+{
+ if (read(fd_in, &remote_version, 1) < 1)
+ return -1;
+ write(fd_out, &local_version, 1);
+ return 0;
+}
+
+void service(int fd_in, int fd_out) {
+ char type;
+ int retval;
+ do {
+ retval = read(fd_in, &type, 1);
+ if (retval < 1) {
+ if (retval < 0)
+ perror("rpush: read ");
return;
}
- posn = 0;
- do {
- size = write(fd_out, buf + posn, objsize - posn);
- if (size <= 0) {
- if (!size) {
- fprintf(stderr, "git-rpush: write closed");
- } else {
- perror("git-rpush: write ");
- }
- return;
- }
- posn += size;
- } while (posn < objsize);
+ if (type == 'v' && serve_version(fd_in, fd_out))
+ return;
+ if (type == 'o' && serve_object(fd_in, fd_out))
+ return;
} while (1);
}
@@ -56,7 +91,7 @@
arg++;
}
if (argc < arg + 2) {
- usage("git-rpush [-c] [-t] [-a] commit-id url");
+ usage("git-rpush [-c] [-t] [-a] commit-id url");
return 1;
}
commit_id = argv[arg];
^ permalink raw reply
* Re: [PATCH] Make rsh protocol extensible
From: Daniel Barkalow @ 2005-06-03 21:38 UTC (permalink / raw)
To: Petr Baudis; +Cc: git
In-Reply-To: <20050602205912.GD32189@pasky.ji.cz>
On Thu, 2 Jun 2005, Petr Baudis wrote:
> Dear diary, on Thu, May 19, 2005 at 07:11:46AM CEST, I got a letter
> where Daniel Barkalow <barkalow@iabervon.org> told me that...
> > This changes the rsh protocol to allow reporting failure in getting an
> > object without breaking the connection, and to allow other types of
> > request than for objects to be made. It is a preliminary to any more
> > extensive pull operation.
> >
> > Signed-off-by: Daniel Barkalow <barkalow@iabervon.org>
>
> I wanted to apply it but then I figured out that I will better hold it
> and ask you what do you think about it now after few weeks. ;-) Should I
> still go on and apply it to Cogito?
At this point, I want to also put in a protocol version number. I'll send
a replacement patch in a bit.
-Daniel
*This .sig left intentionally blank*
^ permalink raw reply
* Re: [PATCH] git-daemon server
From: Linus Torvalds @ 2005-06-03 21:38 UTC (permalink / raw)
To: McMullan, Jason; +Cc: GIT Mailling list
In-Reply-To: <1117832172.8970.22.camel@jmcmullan.timesys>
On Fri, 3 Jun 2005, McMullan, Jason wrote:
>
> 1) I used the stdin/stdout stuff as debugging
>
> 2) It works with xinetd
>
> 3) Because I can't figure out how to get /bin/sh to give me two pipes
> that hook together two processes. What I really want:
>
> ssh user@remote git server --db /my/git.git <|> git server request HEAD
Ok, so a ssh connection _would_ work per se, and the only real issue is
the pipe itself is one-directional as done by the shell?
> Where 'xxx <|> yyy' means:
>
> Take process xxx's stdin, hook it to yyy's stdout,
> Take process yyy's stdin, hook it to xxx's stdout,
> Run till they both die.
>
> If you know how to do that, I'd be grateful.
Yeah, you're right, you can't do bi-directional piping with shell, and
you'd need to do it inside your program. It should be easy enough to do
with something like adding a new flag that says "--exec", and when seeing
that, doing something like
if (!strcmp(argv[i], "--exec")) {
int fd[2][2];
pid_t pid;
if (pipe(fd[0]) < 0 || pipe(fd[1]) < 0)
die("unable to create pipes");
pid = fork();
if (pid < 0)
die("unable to fork exec process");
if (!pid) {
dup2(fd[0][0], 0);
dup2(fd[1][1], 1);
close_pipes(fd);
exit(system(argv[i+1]));
}
dup2(fd[1][0], 0);
dup2(fd[0][1], 1);
close_pipes(fd);
}
where "close_pipes()" just looks like
void close_pipes(int *fd)
{
int i;
for (i = 0; i < 3; i++)
close(fd[i]);
}
and as usual, the above is totally and utterly untested. And using
"system()" is cheezy and does an extra unnecessary fork(), so if you want
to, it could be better done with just a "execve(/bin/sh -c 'string')"
approach by hand.
Anyway, with _something_ like the above you could do something like
git-sync --exec "ssh master.kernel.org git-sync" ....
and it would do the obvious thing.
What do you think?
Linus
^ permalink raw reply
* Re: [PATCH] git-daemon server
From: Daniel Barkalow @ 2005-06-03 21:33 UTC (permalink / raw)
To: Jason McMullan; +Cc: git, torvalds
In-Reply-To: <20050603152212.GA4598@jmcmullan.timesys>
On Fri, 3 Jun 2005, Jason McMullan wrote:
> git-daemon - Client/server for exchanging GIT objects
Is this somehow different from rpush/rpull aside from using an
externally-provided socket and having the proper locking for writing refs
(which I posted a while ago, but which hasn't been included anywhere yet)?
-Daniel
*This .sig left intentionally blank*
^ permalink raw reply
* Re: [PATCH] git-daemon server
From: McMullan, Jason @ 2005-06-03 20:56 UTC (permalink / raw)
To: Linus Torvalds; +Cc: GIT Mailling list
In-Reply-To: <Pine.LNX.4.58.0506031320190.1876@ppc970.osdl.org>
[-- Attachment #1: Type: text/plain, Size: 695 bytes --]
Linus, you were wondering why stdin/stdout was the default, even though
I don't have a use case for ssh with stdin/stdout:
1) I used the stdin/stdout stuff as debugging
2) It works with xinetd
3) Because I can't figure out how to get /bin/sh to give me two pipes
that hook together two processes. What I really want:
ssh user@remote git server --db /my/git.git <|> git server request HEAD
Where 'xxx <|> yyy' means:
Take process xxx's stdin, hook it to yyy's stdout,
Take process yyy's stdin, hook it to xxx's stdout,
Run till they both die.
If you know how to do that, I'd be grateful.
--
Jason McMullan <jason.mcmullan@timesys.com>
TimeSys Corporation
[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]
^ permalink raw reply
* Re: [PATCH] git-daemon server
From: Linus Torvalds @ 2005-06-03 20:25 UTC (permalink / raw)
To: McMullan, Jason; +Cc: Git Mailing List
In-Reply-To: <1117827011.8970.2.camel@jmcmullan.timesys>
On Fri, 3 Jun 2005, McMullan, Jason wrote:
>
> No, but you could do:
That doth suck. Is there any reason for not allowing stdin/stdout as the
transfer protocol?
Making games like having ssh pipe things through is what I already have to
do with mail, and it's ok for long-running servers, but I really think of
a "git pull" as an _event_.
So why doesn't stdin/stdout work with ssh, even though the docs say that
it's even the default?
Linus
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox