{"thread":{"id":"10","subject":"Re: [PATCH] merge-base","startedAt":"2005-04-14T03:49:51Z","lastAt":"2005-04-14T17:20:23Z","messageCount":3,"participants":["Linus Torvalds","Daniel Barkalow"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"32","messageId":"Pine.LNX.4.58.0504132040020.7211@ppc970.osdl.org","threadId":"10","inReplyTo":"Pine.LNX.4.21.0504131447480.30848-100000@iabervon.org","subject":"Re: [PATCH] merge-base","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-14T03:49:51Z","receivedAt":"2005-04-14T03:49:51Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 13 Apr 2005, Daniel Barkalow wrote:\n>\n> I wrote a pretty dumb program that will find some common ancestor for a\n> pair of commits. It finds the one which is closest to one of the commits\n> by number of generations. This is, at least, not strictly worse than any\n> other common ancestor, at least (like picking the original release would\n> be).\n> \n> It wouldn't be too hard to do this much with rev-tree, but should be\n> easier to extend.\n\nI agree. But I did the silly \"common revision tracking\" part slightly\ndifferently and in particular I already made fsck and rev-tree use the \nsame exact code.\n\nAlso, I don't see why you did the \"common parent\" thing as part of the\n\"library\", since that really does seem to be a very specific to this \nproblem, and neither fsck nor rev-tree really wants it. \n\nAlso, the date parsing really is a separate issue from the revision \ntracking (fsck does not want date parsing, but rev-tool does), so I think \nyou might want to do for date parsing what I just did for the revision.h \nthing? No point in tying them together.\n\nSo could I ask you to re-factor it and base it on my current tree? Make \nthe \"merge-base\" program have that common parent thing in it, and factor \nout the common date parsing into \"parse-date.c\" or something?\n\n\t\tLinus\n"},{"id":"92","messageId":"Pine.LNX.4.21.0504141234490.30848-100000@iabervon.org","threadId":"10","inReplyTo":"Pine.LNX.4.58.0504132040020.7211@ppc970.osdl.org","subject":"Re: [PATCH] merge-base","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-04-14T17:17:59Z","receivedAt":"2005-04-14T17:17:59Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Wed, 13 Apr 2005, Linus Torvalds wrote:\n\n> I agree. But I did the silly \"common revision tracking\" part slightly\n> differently and in particular I already made fsck and rev-tree use the \n> same exact code.\n\nI think I only saw a cut-and-paste version, and I didn't want to follow\nthat pattern.\n\n> Also, I don't see why you did the \"common parent\" thing as part of the\n> \"library\", since that really does seem to be a very specific to this \n> problem, and neither fsck nor rev-tree really wants it. \n\nThat was just silly; on the other hand, I think I'll eventually want to\nhave a \"support-for-merging\" library file, so that people can write\nalternative merging programs which call library functions to pick out\nhistory details. But that obviously shouldn't be the same file that\nrev-tree and fsck share, and I'll probably do that by pulling main() out\nof the program later.\n\n> Also, the date parsing really is a separate issue from the revision \n> tracking (fsck does not want date parsing, but rev-tool does), so I think \n> you might want to do for date parsing what I just did for the revision.h \n> thing? No point in tying them together.\n\nI think there is some value in having a library file that completely\nparses \"commit\"-tagged files. Having the date field in struct revision\nwithout the code to parse it in the file that defines the struct seems\npoor to me.\n\n> So could I ask you to re-factor it and base it on my current tree? Make \n> the \"merge-base\" program have that common parent thing in it, and factor \n> out the common date parsing into \"parse-date.c\" or something?\n\nI'm not actually using the date in merge-base, either, so I'll just leave\nthat alone for now (merge-base is based on generations, not time,\ncurrently).\n\n\t-Daniel\n*This .sig left intentionally blank*\n\n"},{"id":"93","messageId":"Pine.LNX.4.21.0504141318430.30848-100000@iabervon.org","threadId":"10","inReplyTo":"Pine.LNX.4.21.0504141234490.30848-100000@iabervon.org","subject":"[PATCH] merge-base-rebased","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-04-14T17:20:23Z","receivedAt":"2005-04-14T17:20:23Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"Add a dumb-but-improvable program to find a not-too-bad commit to do a\nthree-way-merge of two commits.\n\nSigned-Off-By: Daniel Barkalow <barkalow@iabervon.org>\n\nIndex: Makefile\n===================================================================\n--- 1756b578489f93999ded68ae347bef7d6063101c/Makefile  (mode:100644 sha1:b39b4ea37586693dd707d1d0750a9b580350ec50)\n+++ b07fe1a7e0836e7d906c16c4f63b2e42b4a5193a/Makefile  (mode:100644 sha1:a2d920a36c1124fb0a031ae43fdd3a8106529c8f)\n@@ -14,7 +14,7 @@\n \n PROG=   update-cache show-diff init-db write-tree read-tree commit-tree \\\n \tcat-file fsck-cache checkout-cache diff-tree rev-tree show-files \\\n-\tcheck-files ls-tree merge-tree\n+\tcheck-files ls-tree merge-tree merge-base\n \n all: $(PROG)\n \n@@ -67,6 +67,9 @@\n merge-tree: merge-tree.o read-cache.o\n \t$(CC) $(CFLAGS) -o merge-tree merge-tree.o read-cache.o $(LIBS)\n \n+merge-base: merge-base.o read-cache.o\n+\t$(CC) $(CFLAGS) -o merge-base merge-base.o read-cache.o $(LIBS)\n+\n read-cache.o: cache.h\n show-diff.o: cache.h\n \nIndex: merge-base.c\n===================================================================\n--- /dev/null  (tree:1756b578489f93999ded68ae347bef7d6063101c)\n+++ b07fe1a7e0836e7d906c16c4f63b2e42b4a5193a/merge-base.c  (mode:100644 sha1:a3e885ef8e2ae761d76c3217002467d19bf75a8d)\n@@ -0,0 +1,132 @@\n+#include <stdlib.h>\n+#include \"cache.h\"\n+#include \"revision.h\"\n+\n+static int parse_commit(struct revision *rev)\n+{\n+\tif (!(rev->flags & SEEN)) {\n+\t\tvoid *buffer, *bufptr;\n+\t\tunsigned long size;\n+\t\tchar type[20];\n+\t\tunsigned char parent[20];\n+\n+\t\trev->flags |= SEEN;\n+\t\tbuffer = bufptr = read_sha1_file(rev->sha1, type, &size);\n+\t\tif (!buffer || strcmp(type, \"commit\"))\n+\t\t\treturn -1;\n+\t\tbufptr += 46; /* \"tree \" + \"hex sha1\" + \"\\n\" */\n+\t\twhile (!memcmp(bufptr, \"parent \", 7) && \n+\t\t       !get_sha1_hex(bufptr+7, parent)) {\n+\t\t\tadd_relationship(rev, parent);\n+\t\t\tbufptr += 48;   /* \"parent \" + \"hex sha1\" + \"\\n\" */\n+\t\t}\n+\t\t//rev->date = parse_commit_date(bufptr);\n+\t\tfree(buffer);\n+\t}\n+\treturn 0;\n+}\n+\n+struct revision *common_ancestor(struct revision *rev1, struct revision *rev2)\n+{\n+\tstruct parent *parent;\n+\n+\tstruct parent *rev1list = malloc(sizeof(struct parent));\n+\tstruct parent *rev2list = malloc(sizeof(struct parent));\n+        \n+\tstruct parent *posn, *temp;\n+\n+\trev1list->parent = rev1;\n+\trev1list->next = NULL;\n+\n+\trev2list->parent = rev2;\n+\trev2list->next = NULL;\n+\n+\twhile (rev1list || rev2list) {\n+\t\tposn = rev1list;\n+\t\trev1list = NULL;\n+\t\twhile (posn) {\n+\t\t\tparse_commit(posn->parent);\n+\t\t\tif (posn->parent->flags & 0x0001) {\n+\t\t\t\t/*\n+\t\t\t\tprintf(\"1 already seen %s %x\\n\",\n+\t\t\t\t       sha1_to_hex(posn->parent->sha1),\n+\t\t\t\t       posn->parent->flags);\n+\t\t\t\t*/\n+                                // do nothing\n+\t\t\t} else if (posn->parent->flags & 0x0002) {\n+                                // XXXX free lists\n+\t\t\t\treturn posn->parent;\n+\t\t\t} else {\n+\t\t\t\t/*\n+\t\t\t\tprintf(\"1 based on %s\\n\",\n+\t\t\t\t       sha1_to_hex(posn->parent->sha1));\n+\t\t\t\t*/\n+\t\t\t\tposn->parent->flags |= 0x0001;\n+\n+\t\t\t\tparent = posn->parent->parent;\n+\t\t\t\twhile (parent) {\n+\t\t\t\t\ttemp = malloc(sizeof(struct parent));\n+\t\t\t\t\ttemp->next = rev1list;\n+\t\t\t\t\ttemp->parent = parent->parent;\n+\t\t\t\t\trev1list = temp;\n+\t\t\t\t\tparent = parent->next;\n+\t\t\t\t}\n+\t\t\t}\n+\t\t\tposn = posn->next;\n+\t\t}\n+\t\tposn = rev2list;\n+\t\trev2list = NULL;\n+\t\twhile (posn) {\n+\t\t\tparse_commit(posn->parent);\n+\t\t\tif (posn->parent->flags & 0x0002) {\n+\t\t\t\t/*\n+\t\t\t\tprintf(\"2 already seen %s\\n\",\n+\t\t\t\t       sha1_to_hex(posn->parent->sha1));\n+\t\t\t\t*/\n+                                // do nothing\n+\t\t\t} else if (posn->parent->flags & 0x0001) {\n+                                // XXXX free lists\n+\t\t\t\treturn posn->parent;\n+\t\t\t} else {\n+\t\t\t\t/*\n+\t\t\t\tprintf(\"2 based on %s\\n\",\n+\t\t\t\t       sha1_to_hex(posn->parent->sha1));\n+\t\t\t\t*/\n+\t\t\t\tposn->parent->flags |= 0x0002;\n+\n+\t\t\t\tparent = posn->parent->parent;\n+\t\t\t\twhile (parent) {\n+\t\t\t\t\ttemp = malloc(sizeof(struct parent));\n+\t\t\t\t\ttemp->next = rev2list;\n+\t\t\t\t\ttemp->parent = parent->parent;\n+\t\t\t\t\trev2list = temp;\n+\t\t\t\t\tparent = parent->next;\n+\t\t\t\t}\n+\t\t\t}\n+\t\t\tposn = posn->next;\n+\t\t}\n+\t}\n+\treturn NULL;\n+}\n+\n+int main(int argc, char **argv)\n+{\n+\tstruct revision *rev1, *rev2, *ret;\n+\tunsigned char rev1key[20], rev2key[20];\n+\tif (argc != 3 ||\n+\t    get_sha1_hex(argv[1], rev1key) ||\n+\t    get_sha1_hex(argv[2], rev2key)) {\n+\t\tusage(\"mergebase <commit-id> <commit-id>\");\n+\t}\n+\trev1 = lookup_rev(rev1key);\n+\trev2 = lookup_rev(rev2key);\n+\tret = common_ancestor(rev1, rev2);\n+\tif (ret) {\n+\t\tprintf(\"%s\\n\", sha1_to_hex(ret->sha1));\n+\t\treturn 0;\n+\t} else {\n+\t\tprintf(\"Sorry.\\n\");\n+\t\treturn 1;\n+\t}\n+\t\n+}\n\n"}]}