* Re: [PATCH] merge-base
[not found] <Pine.LNX.4.21.0504131447480.30848-100000@iabervon.org>
@ 2005-04-14 3:49 ` Linus Torvalds
2005-04-14 17:17 ` Daniel Barkalow
0 siblings, 1 reply; 3+ messages in thread
From: Linus Torvalds @ 2005-04-14 3:49 UTC (permalink / raw)
To: Daniel Barkalow; +Cc: git
On Wed, 13 Apr 2005, Daniel Barkalow wrote:
>
> I wrote a pretty dumb program that will find some common ancestor for a
> pair of commits. It finds the one which is closest to one of the commits
> by number of generations. This is, at least, not strictly worse than any
> other common ancestor, at least (like picking the original release would
> be).
>
> It wouldn't be too hard to do this much with rev-tree, but should be
> easier to extend.
I agree. But I did the silly "common revision tracking" part slightly
differently and in particular I already made fsck and rev-tree use the
same exact code.
Also, I don't see why you did the "common parent" thing as part of the
"library", since that really does seem to be a very specific to this
problem, and neither fsck nor rev-tree really wants it.
Also, the date parsing really is a separate issue from the revision
tracking (fsck does not want date parsing, but rev-tool does), so I think
you might want to do for date parsing what I just did for the revision.h
thing? No point in tying them together.
So could I ask you to re-factor it and base it on my current tree? Make
the "merge-base" program have that common parent thing in it, and factor
out the common date parsing into "parse-date.c" or something?
Linus
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] merge-base
2005-04-14 3:49 ` [PATCH] merge-base Linus Torvalds
@ 2005-04-14 17:17 ` Daniel Barkalow
2005-04-14 17:20 ` [PATCH] merge-base-rebased Daniel Barkalow
0 siblings, 1 reply; 3+ messages in thread
From: Daniel Barkalow @ 2005-04-14 17:17 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
On Wed, 13 Apr 2005, Linus Torvalds wrote:
> I agree. But I did the silly "common revision tracking" part slightly
> differently and in particular I already made fsck and rev-tree use the
> same exact code.
I think I only saw a cut-and-paste version, and I didn't want to follow
that pattern.
> Also, I don't see why you did the "common parent" thing as part of the
> "library", since that really does seem to be a very specific to this
> problem, and neither fsck nor rev-tree really wants it.
That was just silly; on the other hand, I think I'll eventually want to
have a "support-for-merging" library file, so that people can write
alternative merging programs which call library functions to pick out
history details. But that obviously shouldn't be the same file that
rev-tree and fsck share, and I'll probably do that by pulling main() out
of the program later.
> Also, the date parsing really is a separate issue from the revision
> tracking (fsck does not want date parsing, but rev-tool does), so I think
> you might want to do for date parsing what I just did for the revision.h
> thing? No point in tying them together.
I think there is some value in having a library file that completely
parses "commit"-tagged files. Having the date field in struct revision
without the code to parse it in the file that defines the struct seems
poor to me.
> So could I ask you to re-factor it and base it on my current tree? Make
> the "merge-base" program have that common parent thing in it, and factor
> out the common date parsing into "parse-date.c" or something?
I'm not actually using the date in merge-base, either, so I'll just leave
that alone for now (merge-base is based on generations, not time,
currently).
-Daniel
*This .sig left intentionally blank*
^ permalink raw reply [flat|nested] 3+ messages in thread
* [PATCH] merge-base-rebased
2005-04-14 17:17 ` Daniel Barkalow
@ 2005-04-14 17:20 ` Daniel Barkalow
0 siblings, 0 replies; 3+ messages in thread
From: Daniel Barkalow @ 2005-04-14 17:20 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
Add a dumb-but-improvable program to find a not-too-bad commit to do a
three-way-merge of two commits.
Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org>
Index: Makefile
===================================================================
--- 1756b578489f93999ded68ae347bef7d6063101c/Makefile (mode:100644 sha1:b39b4ea37586693dd707d1d0750a9b580350ec50)
+++ b07fe1a7e0836e7d906c16c4f63b2e42b4a5193a/Makefile (mode:100644 sha1:a2d920a36c1124fb0a031ae43fdd3a8106529c8f)
@@ -14,7 +14,7 @@
PROG= update-cache show-diff init-db write-tree read-tree commit-tree \
cat-file fsck-cache checkout-cache diff-tree rev-tree show-files \
- check-files ls-tree merge-tree
+ check-files ls-tree merge-tree merge-base
all: $(PROG)
@@ -67,6 +67,9 @@
merge-tree: merge-tree.o read-cache.o
$(CC) $(CFLAGS) -o merge-tree merge-tree.o read-cache.o $(LIBS)
+merge-base: merge-base.o read-cache.o
+ $(CC) $(CFLAGS) -o merge-base merge-base.o read-cache.o $(LIBS)
+
read-cache.o: cache.h
show-diff.o: cache.h
Index: merge-base.c
===================================================================
--- /dev/null (tree:1756b578489f93999ded68ae347bef7d6063101c)
+++ b07fe1a7e0836e7d906c16c4f63b2e42b4a5193a/merge-base.c (mode:100644 sha1:a3e885ef8e2ae761d76c3217002467d19bf75a8d)
@@ -0,0 +1,132 @@
+#include <stdlib.h>
+#include "cache.h"
+#include "revision.h"
+
+static int parse_commit(struct revision *rev)
+{
+ if (!(rev->flags & SEEN)) {
+ void *buffer, *bufptr;
+ unsigned long size;
+ char type[20];
+ unsigned char parent[20];
+
+ rev->flags |= SEEN;
+ buffer = bufptr = read_sha1_file(rev->sha1, type, &size);
+ if (!buffer || strcmp(type, "commit"))
+ return -1;
+ bufptr += 46; /* "tree " + "hex sha1" + "\n" */
+ while (!memcmp(bufptr, "parent ", 7) &&
+ !get_sha1_hex(bufptr+7, parent)) {
+ add_relationship(rev, parent);
+ bufptr += 48; /* "parent " + "hex sha1" + "\n" */
+ }
+ //rev->date = parse_commit_date(bufptr);
+ free(buffer);
+ }
+ return 0;
+}
+
+struct revision *common_ancestor(struct revision *rev1, struct revision *rev2)
+{
+ struct parent *parent;
+
+ struct parent *rev1list = malloc(sizeof(struct parent));
+ struct parent *rev2list = malloc(sizeof(struct parent));
+
+ struct parent *posn, *temp;
+
+ rev1list->parent = rev1;
+ rev1list->next = NULL;
+
+ rev2list->parent = rev2;
+ rev2list->next = NULL;
+
+ while (rev1list || rev2list) {
+ posn = rev1list;
+ rev1list = NULL;
+ while (posn) {
+ parse_commit(posn->parent);
+ if (posn->parent->flags & 0x0001) {
+ /*
+ printf("1 already seen %s %x\n",
+ sha1_to_hex(posn->parent->sha1),
+ posn->parent->flags);
+ */
+ // do nothing
+ } else if (posn->parent->flags & 0x0002) {
+ // XXXX free lists
+ return posn->parent;
+ } else {
+ /*
+ printf("1 based on %s\n",
+ sha1_to_hex(posn->parent->sha1));
+ */
+ posn->parent->flags |= 0x0001;
+
+ parent = posn->parent->parent;
+ while (parent) {
+ temp = malloc(sizeof(struct parent));
+ temp->next = rev1list;
+ temp->parent = parent->parent;
+ rev1list = temp;
+ parent = parent->next;
+ }
+ }
+ posn = posn->next;
+ }
+ posn = rev2list;
+ rev2list = NULL;
+ while (posn) {
+ parse_commit(posn->parent);
+ if (posn->parent->flags & 0x0002) {
+ /*
+ printf("2 already seen %s\n",
+ sha1_to_hex(posn->parent->sha1));
+ */
+ // do nothing
+ } else if (posn->parent->flags & 0x0001) {
+ // XXXX free lists
+ return posn->parent;
+ } else {
+ /*
+ printf("2 based on %s\n",
+ sha1_to_hex(posn->parent->sha1));
+ */
+ posn->parent->flags |= 0x0002;
+
+ parent = posn->parent->parent;
+ while (parent) {
+ temp = malloc(sizeof(struct parent));
+ temp->next = rev2list;
+ temp->parent = parent->parent;
+ rev2list = temp;
+ parent = parent->next;
+ }
+ }
+ posn = posn->next;
+ }
+ }
+ return NULL;
+}
+
+int main(int argc, char **argv)
+{
+ struct revision *rev1, *rev2, *ret;
+ unsigned char rev1key[20], rev2key[20];
+ if (argc != 3 ||
+ get_sha1_hex(argv[1], rev1key) ||
+ get_sha1_hex(argv[2], rev2key)) {
+ usage("mergebase <commit-id> <commit-id>");
+ }
+ rev1 = lookup_rev(rev1key);
+ rev2 = lookup_rev(rev2key);
+ ret = common_ancestor(rev1, rev2);
+ if (ret) {
+ printf("%s\n", sha1_to_hex(ret->sha1));
+ return 0;
+ } else {
+ printf("Sorry.\n");
+ return 1;
+ }
+
+}
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2005-04-14 17:18 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <Pine.LNX.4.21.0504131447480.30848-100000@iabervon.org>
2005-04-14 3:49 ` [PATCH] merge-base Linus Torvalds
2005-04-14 17:17 ` Daniel Barkalow
2005-04-14 17:20 ` [PATCH] merge-base-rebased Daniel Barkalow
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).