This was a real git merge with conflicts. I'll commit the scripts I used
to do the merge next.
Not pretty, but it's half-way functional.
cat-file: cat-file.o read-cache.o
$(CC) $(CFLAGS) -o cat-file cat-file.o read-cache.o $(LIBS)
-fsck-cache: fsck-cache.o read-cache.o
- $(CC) $(CFLAGS) -o fsck-cache fsck-cache.o read-cache.o $(LIBS)
+fsck-cache: fsck-cache.o read-cache.o object.o commit.o tree.o blob.o
+ $(CC) $(CFLAGS) -o fsck-cache fsck-cache.o read-cache.o object.o commit.o tree.o blob.o $(LIBS)
checkout-cache: checkout-cache.o read-cache.o
$(CC) $(CFLAGS) -o checkout-cache checkout-cache.o read-cache.o $(LIBS)
diff-tree: diff-tree.o read-cache.o
$(CC) $(CFLAGS) -o diff-tree diff-tree.o read-cache.o $(LIBS)
-rev-tree: rev-tree.o read-cache.o
- $(CC) $(CFLAGS) -o rev-tree rev-tree.o read-cache.o $(LIBS)
+rev-tree: rev-tree.o read-cache.o object.o commit.o tree.o blob.o
+ $(CC) $(CFLAGS) -o rev-tree rev-tree.o read-cache.o object.o commit.o tree.o blob.o $(LIBS)
show-files: show-files.o read-cache.o
$(CC) $(CFLAGS) -o show-files show-files.o read-cache.o $(LIBS)
ls-tree: ls-tree.o read-cache.o
$(CC) $(CFLAGS) -o ls-tree ls-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)
+merge-base: merge-base.o read-cache.o object.o commit.o tree.o blob.o
+ $(CC) $(CFLAGS) -o merge-base merge-base.o read-cache.o object.o commit.o tree.o blob.o $(LIBS)
merge-cache: merge-cache.o read-cache.o
$(CC) $(CFLAGS) -o merge-cache merge-cache.o read-cache.o $(LIBS)
--- /dev/null
+#include "blob.h"
+#include "cache.h"
+#include <stdlib.h>
+
+const char *blob_type = "blob";
+
+struct blob *lookup_blob(unsigned char *sha1)
+{
+ struct object *obj = lookup_object(sha1);
+ if (!obj) {
+ struct blob *ret = malloc(sizeof(struct blob));
+ memset(ret, 0, sizeof(struct blob));
+ created_object(sha1, &ret->object);
+ ret->object.type = blob_type;
+ ret->object.parsed = 1;
+ return ret;
+ }
+ if (obj->parsed && obj->type != blob_type) {
+ error("Object %s is a %s, not a blob",
+ sha1_to_hex(sha1), obj->type);
+ return NULL;
+ }
+ return (struct blob *) obj;
+}
--- /dev/null
+#ifndef BLOB_H
+#define BLOB_H
+
+#include "object.h"
+
+extern const char *blob_type;
+
+struct blob {
+ struct object object;
+};
+
+struct blob *lookup_blob(unsigned char *sha1);
+
+#endif /* BLOB_H */
--- /dev/null
+#include "commit.h"
+#include "cache.h"
+#include <string.h>
+
+const char *commit_type = "commit";
+
+struct commit *lookup_commit(unsigned char *sha1)
+{
+ struct object *obj = lookup_object(sha1);
+ if (!obj) {
+ struct commit *ret = malloc(sizeof(struct commit));
+ memset(ret, 0, sizeof(struct commit));
+ created_object(sha1, &ret->object);
+ return ret;
+ }
+ if (obj->parsed && obj->type != commit_type) {
+ error("Object %s is a %s, not a commit",
+ sha1_to_hex(sha1), obj->type);
+ return NULL;
+ }
+ return (struct commit *) obj;
+}
+
+static unsigned long parse_commit_date(const char *buf)
+{
+ unsigned long date;
+
+ if (memcmp(buf, "author", 6))
+ return 0;
+ while (*buf++ != '\n')
+ /* nada */;
+ if (memcmp(buf, "committer", 9))
+ return 0;
+ while (*buf++ != '>')
+ /* nada */;
+ date = strtoul(buf, NULL, 10);
+ if (date == ULONG_MAX)
+ date = 0;
+ return date;
+}
+
+int parse_commit(struct commit *item)
+{
+ char type[20];
+ void * buffer, *bufptr;
+ unsigned long size;
+ unsigned char parent[20];
+ if (item->object.parsed)
+ return 0;
+ item->object.parsed = 1;
+ buffer = bufptr = read_sha1_file(item->object.sha1, type, &size);
+ if (!buffer)
+ return error("Could not read %s",
+ sha1_to_hex(item->object.sha1));
+ if (strcmp(type, commit_type))
+ return error("Object %s not a commit",
+ sha1_to_hex(item->object.sha1));
+ item->object.type = commit_type;
+ get_sha1_hex(bufptr + 5, parent);
+ item->tree = lookup_tree(parent);
+ add_ref(&item->object, &item->tree->object);
+ bufptr += 46; /* "tree " + "hex sha1" + "\n" */
+ while (!memcmp(bufptr, "parent ", 7) &&
+ !get_sha1_hex(bufptr + 7, parent)) {
+ struct commit_list *new_parent =
+ malloc(sizeof(struct commit_list));
+ new_parent->next = item->parents;
+ new_parent->item = lookup_commit(parent);
+ add_ref(&item->object, &new_parent->item->object);
+ item->parents = new_parent;
+ bufptr += 48;
+ }
+ item->date = parse_commit_date(bufptr);
+ free(buffer);
+ return 0;
+}
+
+void free_commit_list(struct commit_list *list)
+{
+ while (list) {
+ struct commit_list *temp = list;
+ list = temp->next;
+ free(temp);
+ }
+}
--- /dev/null
+#ifndef COMMIT_H
+#define COMMIT_H
+
+#include "object.h"
+#include "tree.h"
+
+struct commit_list {
+ struct commit *item;
+ struct commit_list *next;
+};
+
+struct commit {
+ struct object object;
+ unsigned long date;
+ struct commit_list *parents;
+ struct tree *tree;
+};
+
+extern const char *commit_type;
+
+struct commit *lookup_commit(unsigned char *sha1);
+
+int parse_commit(struct commit *item);
+
+void free_commit_list(struct commit_list *list);
+
+#endif /* COMMIT_H */
#include <sys/types.h>
#include <dirent.h>
-#include "revision.h"
+#include "commit.h"
+#include "tree.h"
+#include "blob.h"
+
+#define REACHABLE 0x0001
static int show_unreachable = 0;
static unsigned char head_sha1[20];
int i;
/* Look up all the requirements, warn about missing objects.. */
- for (i = 0; i < nr_revs; i++) {
- struct revision *rev = revs[i];
+ for (i = 0; i < nr_objs; i++) {
+ struct object *obj = objs[i];
- if (show_unreachable && !(rev->flags & REACHABLE)) {
- printf("unreachable %s %s\n", rev->tag, sha1_to_hex(rev->sha1));
+ if (show_unreachable && !(obj->flags & REACHABLE)) {
+ printf("unreachable %s\n", sha1_to_hex(obj->sha1));
continue;
}
- switch (rev->flags & (SEEN | USED)) {
- case 0:
- printf("bad %s %s\n", rev->tag, sha1_to_hex(rev->sha1));
- break;
- case USED:
- printf("missing %s, %s\n", rev->tag, sha1_to_hex(rev->sha1));
- break;
- case SEEN:
- printf("dangling %s %s\n", rev->tag, sha1_to_hex(rev->sha1));
- break;
+ if (!obj->parsed) {
+ printf("missing %s %s\n", obj->type,
+ sha1_to_hex(obj->sha1));
+ }
+ if (!obj->used) {
+ printf("dangling %s %s\n", obj->type,
+ sha1_to_hex(obj->sha1));
}
}
}
-static void mark_needs_sha1(unsigned char *parent, const char *ptag, unsigned char *child, const char *ctag)
-{
- struct revision * child_rev = add_relationship(lookup_rev(parent, ptag), child, ctag);
- child_rev->flags |= USED;
-}
-
-static int mark_sha1_seen(unsigned char *sha1, const char *tag)
-{
- struct revision *rev = lookup_rev(sha1, tag);
-
- rev->flags |= SEEN;
- return 0;
-}
-
static int fsck_tree(unsigned char *sha1, void *data, unsigned long size)
{
- int warn_old_tree = 1;
-
- while (size) {
- int len = 1+strlen(data);
- unsigned char *file_sha1 = data + len;
- char *path = strchr(data, ' ');
- unsigned int mode;
- if (size < len + 20 || !path || sscanf(data, "%o", &mode) != 1)
- return -1;
-
- /* Warn about trees that don't do the recursive thing.. */
- if (warn_old_tree && strchr(path, '/')) {
- fprintf(stderr, "warning: fsck-cache: tree %s has full pathnames in it\n", sha1_to_hex(sha1));
- warn_old_tree = 0;
- }
-
- data += len + 20;
- size -= len + 20;
- mark_needs_sha1(sha1, "tree", file_sha1, S_ISDIR(mode) ? "tree" : "blob");
+ struct tree *item = lookup_tree(sha1);
+ if (parse_tree(item))
+ return -1;
+ if (item->has_full_path) {
+ fprintf(stderr, "warning: fsck-cache: tree %s "
+ "has full pathnames in it\n", sha1_to_hex(sha1));
}
return 0;
}
static int fsck_commit(unsigned char *sha1, void *data, unsigned long size)
{
- int parents;
- unsigned char tree_sha1[20];
- unsigned char parent_sha1[20];
-
- if (memcmp(data, "tree ", 5))
+ struct commit *commit = lookup_commit(sha1);
+ if (parse_commit(commit))
return -1;
- if (get_sha1_hex(data + 5, tree_sha1) < 0)
+ if (!commit->tree)
return -1;
- mark_needs_sha1(sha1, "commit", tree_sha1, "tree");
- data += 5 + 40 + 1; /* "tree " + <hex sha1> + '\n' */
- parents = 0;
- while (!memcmp(data, "parent ", 7)) {
- if (get_sha1_hex(data + 7, parent_sha1) < 0)
- return -1;
- mark_needs_sha1(sha1, "commit", parent_sha1, "commit");
- data += 7 + 40 + 1; /* "parent " + <hex sha1> + '\n' */
- parents++;
- }
- if (!parents)
+ if (!commit->parents)
printf("root %s\n", sha1_to_hex(sha1));
return 0;
}
-static int fsck_entry(unsigned char *sha1, char *tag, void *data, unsigned long size)
+static int fsck_entry(unsigned char *sha1, char *tag, void *data,
+ unsigned long size)
{
if (!strcmp(tag, "blob")) {
- /* Nothing to check */;
+ lookup_blob(sha1); /* Nothing to check; but notice it. */
} else if (!strcmp(tag, "tree")) {
if (fsck_tree(sha1, data, size) < 0)
return -1;
return -1;
} else
return -1;
- return mark_sha1_seen(sha1, tag);
+ return 0;
}
static int fsck_name(char *hex)
unsigned long size;
void *buffer = NULL;
if (!check_sha1_signature(sha1, map, mapsize))
- buffer = unpack_sha1_file(map, mapsize, type, &size);
+ buffer = unpack_sha1_file(map, mapsize, type,
+ &size);
munmap(map, mapsize);
if (buffer && !fsck_entry(sha1, type, buffer, size))
return 0;
continue;
}
if (!get_sha1_hex(argv[i], head_sha1)) {
- mark_reachable(lookup_rev(head_sha1, "commit"), REACHABLE);
+ struct object *obj = &lookup_commit(head_sha1)->object;
+ obj->used = 1;
+ mark_reachable(obj, REACHABLE);
heads++;
continue;
}
+#include <stdlib.h>
#include "cache.h"
-#include "revision.h"
+#include "commit.h"
-/*
- * This is stupid. We could have much better heurstics, I bet.
- */
-static int better(struct revision *new, struct revision *old)
+static struct commit *process_list(struct commit_list **list_p, int this_mark,
+ int other_mark)
{
- return new->date > old->date;
+ struct commit_list *parent, *temp;
+ struct commit_list *posn = *list_p;
+ *list_p = NULL;
+ while (posn) {
+ parse_commit(posn->item);
+ if (posn->item->object.flags & this_mark) {
+ /*
+ printf("%d already seen %s %x\n",
+ this_mark
+ sha1_to_hex(posn->parent->sha1),
+ posn->parent->flags);
+ */
+ /* do nothing; this indicates that this side
+ * split and reformed, and we only need to
+ * mark it once.
+ */
+ } else if (posn->item->object.flags & other_mark) {
+ return posn->item;
+ } else {
+ /*
+ printf("%d based on %s\n",
+ this_mark,
+ sha1_to_hex(posn->parent->sha1));
+ */
+ posn->item->object.flags |= this_mark;
+
+ parent = posn->item->parents;
+ while (parent) {
+ temp = malloc(sizeof(struct commit_list));
+ temp->next = *list_p;
+ temp->item = parent->item;
+ *list_p = temp;
+ parent = parent->next;
+ }
+ }
+ posn = posn->next;
+ }
+ return NULL;
}
-static struct revision *common_parent(struct revision *rev1, struct revision *rev2)
+struct commit *common_ancestor(struct commit *rev1, struct commit *rev2)
{
- int i;
- struct revision *best = NULL;
+ struct commit_list *rev1list = malloc(sizeof(struct commit_list));
+ struct commit_list *rev2list = malloc(sizeof(struct commit_list));
+
+ rev1list->item = rev1;
+ rev1list->next = NULL;
+
+ rev2list->item = rev2;
+ rev2list->next = NULL;
- mark_reachable(rev1, 1);
- mark_reachable(rev2, 2);
- for (i = 0; i < nr_revs ;i++) {
- struct revision *rev = revs[i];
- if ((rev->flags & 3) != 3)
- continue;
- if (!best) {
- best = rev;
- continue;
+ while (rev1list || rev2list) {
+ struct commit *ret;
+ ret = process_list(&rev1list, 0x1, 0x2);
+ if (ret) {
+ /* XXXX free lists */
+ return ret;
+ }
+ ret = process_list(&rev2list, 0x2, 0x1);
+ if (ret) {
+ /* XXXX free lists */
+ return ret;
}
- if (better(rev, best))
- best = rev;
}
- return best;
+ return NULL;
}
int main(int argc, char **argv)
{
- unsigned char rev1[20], rev2[20];
- struct revision *common;
-
- if (argc != 3 || get_sha1_hex(argv[1], rev1) || get_sha1_hex(argv[2], rev2))
- usage("merge-base <commit1> <commit2>");
+ struct commit *rev1, *rev2, *ret;
+ unsigned char rev1key[20], rev2key[20];
- /*
- * We will eventually want to include a revision cache file
- * that "rev-tree.c" has generated, since this is going to
- * otherwise be quite expensive for big trees..
- *
- * That's some time off, though, and in the meantime we know
- * that we have a solution to the eventual expense.
- */
- common = common_parent(parse_commit(rev1), parse_commit(rev2));
- if (!common)
- die("no common parent found");
- printf("%s\n", sha1_to_hex(common->sha1));
+ if (argc != 3 ||
+ get_sha1_hex(argv[1], rev1key) ||
+ get_sha1_hex(argv[2], rev2key)) {
+ usage("merge-base <commit-id> <commit-id>");
+ }
+ rev1 = lookup_commit(rev1key);
+ rev2 = lookup_commit(rev2key);
+ ret = common_ancestor(rev1, rev2);
+ if (!ret)
+ return 1;
+ printf("%s\n", sha1_to_hex(ret->object.sha1));
return 0;
}
--- /dev/null
+#include "object.h"
+#include "cache.h"
+#include <stdlib.h>
+#include <string.h>
+
+struct object **objs;
+int nr_objs;
+static int obj_allocs;
+
+static int find_object(unsigned char *sha1)
+{
+ int first = 0, last = nr_objs;
+
+ while (first < last) {
+ int next = (first + last) / 2;
+ struct object *obj = objs[next];
+ int cmp;
+
+ cmp = memcmp(sha1, obj->sha1, 20);
+ if (!cmp)
+ return next;
+ if (cmp < 0) {
+ last = next;
+ continue;
+ }
+ first = next+1;
+ }
+ return -first-1;
+}
+
+struct object *lookup_object(unsigned char *sha1)
+{
+ int pos = find_object(sha1);
+ if (pos >= 0)
+ return objs[pos];
+ return NULL;
+}
+
+void created_object(unsigned char *sha1, struct object *obj)
+{
+ int pos = find_object(sha1);
+
+ obj->parsed = 0;
+ memcpy(obj->sha1, sha1, 20);
+ obj->type = NULL;
+ obj->refs = NULL;
+ obj->used = 0;
+
+ if (pos >= 0)
+ die("Inserting %s twice\n", sha1_to_hex(sha1));
+ pos = -pos-1;
+
+ if (obj_allocs == nr_objs) {
+ obj_allocs = alloc_nr(obj_allocs);
+ objs = realloc(objs, obj_allocs * sizeof(struct object *));
+ }
+
+ /* Insert it into the right place */
+ memmove(objs + pos + 1, objs + pos, (nr_objs - pos) *
+ sizeof(struct object *));
+
+ objs[pos] = obj;
+ nr_objs++;
+}
+
+void add_ref(struct object *refer, struct object *target)
+{
+ struct object_list **pp = &refer->refs;
+ struct object_list *p;
+
+ while ((p = *pp) != NULL) {
+ if (p->item == target)
+ return;
+ pp = &p->next;
+ }
+
+ target->used = 1;
+ p = malloc(sizeof(*p));
+ p->item = target;
+ p->next = NULL;
+ *pp = p;
+}
+
+void mark_reachable(struct object *obj, unsigned int mask)
+{
+ struct object_list *p = obj->refs;
+
+ /* If we've been here already, don't bother */
+ if (obj->flags & mask)
+ return;
+ obj->flags |= mask;
+ while (p) {
+ mark_reachable(p->item, mask);
+ p = p->next;
+ }
+}
--- /dev/null
+#ifndef OBJECT_H
+#define OBJECT_H
+
+struct object_list {
+ struct object *item;
+ struct object_list *next;
+};
+
+struct object {
+ unsigned parsed : 1;
+ unsigned used : 1;
+ unsigned int flags;
+ unsigned char sha1[20];
+ const char *type;
+ struct object_list *refs;
+};
+
+int nr_objs;
+struct object **objs;
+
+struct object *lookup_object(unsigned char *sha1);
+
+void created_object(unsigned char *sha1, struct object *obj);
+
+void add_ref(struct object *refer, struct object *target);
+
+void mark_reachable(struct object *obj, unsigned int mask);
+
+#endif /* OBJECT_H */
#include <ctype.h>
#include "cache.h"
-#include "revision.h"
+#include "commit.h"
/*
* revision.h leaves the low 16 bits of the "flags" field of the
static void read_cache_file(const char *path)
{
- FILE *file = fopen(path, "r");
- char line[500];
-
- if (!file)
- die("bad revtree cache file (%s)", path);
-
- while (fgets(line, sizeof(line), file)) {
- unsigned long date;
- unsigned char sha1[20];
- struct revision *rev;
- const char *buf;
-
- if (sscanf(line, "%lu", &date) != 1)
- break;
- buf = strchr(line, ' ');
- if (!buf)
- break;
- if (get_sha1_hex(buf+1, sha1))
- break;
- rev = lookup_rev(sha1, "commit");
- rev->flags |= SEEN;
- rev->date = date;
-
- /* parents? */
- while ((buf = strchr(buf+1, ' ')) != NULL) {
- unsigned char parent[20];
- if (get_sha1_hex(buf + 1, parent))
- break;
- add_relationship(rev, parent, "commit");
- }
- }
- fclose(file);
+ die("no revtree cache file yet");
}
/*
* And sometimes we're only interested in "edge" commits, ie
* places where the marking changes between parent and child.
*/
-static int interesting(struct revision *rev)
+static int interesting(struct commit *rev)
{
- unsigned mask = marked(rev);
+ unsigned mask = rev->object.flags;
if (!mask)
return 0;
if (show_edges) {
- struct parent *p = rev->parent;
+ struct commit_list *p = rev->parents;
while (p) {
- if (mask != marked(p->parent))
+ if (mask != p->item->object.flags)
return 1;
p = p->next;
}
return 1;
}
+void process_commit(unsigned char *sha1)
+{
+ struct commit_list *parents;
+ struct commit *obj = lookup_commit(sha1);
+ parse_commit(obj);
+
+ parents = obj->parents;
+ while (parents) {
+ process_commit(parents->item->object.sha1);
+ parents = parents->next;
+ }
+}
+
/*
* Usage: rev-tree [--edges] [--cache <cache-file>] <commit-id> [<commit-id2>]
*
}
if (nr >= MAX_COMMITS || get_sha1_hex(arg, sha1[nr]))
usage("rev-tree [--edges] [--cache <cache-file>] <commit-id> [<commit-id>]");
- parse_commit(sha1[nr]);
+ process_commit(sha1[nr]);
nr++;
}
* Now we have the maximal tree. Walk the different sha files back to the root.
*/
for (i = 0; i < nr; i++)
- mark_reachable(lookup_rev(sha1[i], "commit"), 1 << i);
+ mark_reachable(&lookup_commit(sha1[i])->object, 1 << i);
/*
* Now print out the results..
*/
- for (i = 0; i < nr_revs; i++) {
- struct revision *rev = revs[i];
- struct parent *p;
+ for (i = 0; i < nr_objs; i++) {
+ struct object *obj = objs[i];
+ struct commit *commit;
+ struct commit_list *p;
+
+ if (obj->type != commit_type)
+ continue;
+
+ commit = (struct commit *) obj;
- if (!interesting(rev))
+ if (!interesting(commit))
continue;
- printf("%lu %s:%d", rev->date, sha1_to_hex(rev->sha1), marked(rev));
- p = rev->parent;
+ printf("%lu %s:%d", commit->date, sha1_to_hex(obj->sha1),
+ obj->flags);
+ p = commit->parents;
while (p) {
- printf(" %s:%d", sha1_to_hex(p->parent->sha1), marked(p->parent));
+ printf(" %s:%d", sha1_to_hex(p->item->object.sha1),
+ p->item->object.flags);
p = p->next;
}
printf("\n");
--- /dev/null
+#include "tree.h"
+#include "blob.h"
+#include "cache.h"
+#include <stdlib.h>
+
+const char *tree_type = "tree";
+
+struct tree *lookup_tree(unsigned char *sha1)
+{
+ struct object *obj = lookup_object(sha1);
+ if (!obj) {
+ struct tree *ret = malloc(sizeof(struct tree));
+ memset(ret, 0, sizeof(struct tree));
+ created_object(sha1, &ret->object);
+ return ret;
+ }
+ if (obj->parsed && obj->type != tree_type) {
+ error("Object %s is a %s, not a tree",
+ sha1_to_hex(sha1), obj->type);
+ return NULL;
+ }
+ return (struct tree *) obj;
+}
+
+int parse_tree(struct tree *item)
+{
+ char type[20];
+ void *buffer, *bufptr;
+ unsigned long size;
+ if (item->object.parsed)
+ return 0;
+ item->object.parsed = 1;
+ item->object.type = tree_type;
+ buffer = bufptr = read_sha1_file(item->object.sha1, type, &size);
+ if (!buffer)
+ return error("Could not read %s",
+ sha1_to_hex(item->object.sha1));
+ if (strcmp(type, tree_type))
+ return error("Object %s not a tree",
+ sha1_to_hex(item->object.sha1));
+ while (size) {
+ struct object *obj;
+ int len = 1+strlen(bufptr);
+ unsigned char *file_sha1 = bufptr + len;
+ char *path = strchr(bufptr, ' ');
+ unsigned int mode;
+ if (size < len + 20 || !path ||
+ sscanf(bufptr, "%o", &mode) != 1)
+ return -1;
+
+ /* Warn about trees that don't do the recursive thing.. */
+ if (strchr(path, '/')) {
+ item->has_full_path = 1;
+ }
+
+ bufptr += len + 20;
+ size -= len + 20;
+
+ if (S_ISDIR(mode)) {
+ obj = &lookup_tree(file_sha1)->object;
+ } else {
+ obj = &lookup_blob(file_sha1)->object;
+ }
+ add_ref(&item->object, obj);
+ }
+ return 0;
+}
--- /dev/null
+#ifndef TREE_H
+#define TREE_H
+
+#include "object.h"
+
+extern const char *tree_type;
+
+struct tree {
+ struct object object;
+ unsigned has_full_path : 1;
+};
+
+struct tree *lookup_tree(unsigned char *sha1);
+
+int parse_tree(struct tree *tree);
+
+#endif /* TREE_H */