* [1/5] Header files for object parsing
2005-04-18 2:33 ` [0/5] Parsers for git objects, porting some programs Daniel Barkalow
@ 2005-04-18 2:35 ` Daniel Barkalow
2005-04-18 2:36 ` [2/5] Implementations of parsing functions Daniel Barkalow
` (4 subsequent siblings)
5 siblings, 0 replies; 16+ messages in thread
From: Daniel Barkalow @ 2005-04-18 2:35 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Petr Baudis, git
This adds the structs and function declarations for parsing git objects.
Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org>
Index: blob.h
===================================================================
--- /dev/null (tree:5ca133e1b74aee39b2124c0ec9fd51539babb5e0)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/blob.h (mode:100644 sha1:9a23db3a7deca67981b67ceb768411e31f723715)
@@ -0,0 +1,14 @@
+#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 */
Index: commit.h
===================================================================
--- /dev/null (tree:5ca133e1b74aee39b2124c0ec9fd51539babb5e0)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/commit.h (mode:100644 sha1:8cd20b046875f5f7e534b0607fdd97f330f53272)
@@ -0,0 +1,27 @@
+#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 */
Index: object.h
===================================================================
--- /dev/null (tree:5ca133e1b74aee39b2124c0ec9fd51539babb5e0)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/object.h (mode:100644 sha1:20f879e0867b8d6a052c458d9230fbc7786d2864)
@@ -0,0 +1,29 @@
+#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 */
Index: tree.h
===================================================================
--- /dev/null (tree:5ca133e1b74aee39b2124c0ec9fd51539babb5e0)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/tree.h (mode:100644 sha1:14ebbacded09d5e058c7f94652dcb9e12bc31cae)
@@ -0,0 +1,17 @@
+#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 */
^ permalink raw reply [flat|nested] 16+ messages in thread* [2/5] Implementations of parsing functions
2005-04-18 2:33 ` [0/5] Parsers for git objects, porting some programs Daniel Barkalow
2005-04-18 2:35 ` [1/5] Header files for object parsing Daniel Barkalow
@ 2005-04-18 2:36 ` Daniel Barkalow
2005-04-18 2:37 ` [3/5] Port rev-tree to " Daniel Barkalow
` (3 subsequent siblings)
5 siblings, 0 replies; 16+ messages in thread
From: Daniel Barkalow @ 2005-04-18 2:36 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Petr Baudis, git
This implements the parsing functions.
Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org>
Index: blob.c
===================================================================
--- /dev/null (tree:5ca133e1b74aee39b2124c0ec9fd51539babb5e0)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/blob.c (mode:100644 sha1:04e0c1da9b1f4cdb1d1c5881b785babd3b0ceb09)
@@ -0,0 +1,24 @@
+#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));
+ bzero(ret, 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;
+}
Index: commit.c
===================================================================
--- /dev/null (tree:5ca133e1b74aee39b2124c0ec9fd51539babb5e0)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/commit.c (mode:100644 sha1:0099baa63971d86ee30ef2a7da25057f0f45a964)
@@ -0,0 +1,85 @@
+#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));
+ bzero(ret, 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);
+ }
+}
Index: object.c
===================================================================
--- /dev/null (tree:5ca133e1b74aee39b2124c0ec9fd51539babb5e0)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/object.c (mode:100644 sha1:986624ac7a7fd9229e05e1f181fd500640298d9e)
@@ -0,0 +1,96 @@
+#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;
+ }
+}
Index: tree.c
===================================================================
--- /dev/null (tree:5ca133e1b74aee39b2124c0ec9fd51539babb5e0)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/tree.c (mode:100644 sha1:7c5e5e46f4967b0812b06c0114946c3a6432c8d8)
@@ -0,0 +1,67 @@
+#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));
+ bzero(ret, 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;
+}
^ permalink raw reply [flat|nested] 16+ messages in thread* [3/5] Port rev-tree to parsing functions
2005-04-18 2:33 ` [0/5] Parsers for git objects, porting some programs Daniel Barkalow
2005-04-18 2:35 ` [1/5] Header files for object parsing Daniel Barkalow
2005-04-18 2:36 ` [2/5] Implementations of parsing functions Daniel Barkalow
@ 2005-04-18 2:37 ` Daniel Barkalow
2005-04-18 2:40 ` [4/5] Port fsck-cache to use " Daniel Barkalow
` (2 subsequent siblings)
5 siblings, 0 replies; 16+ messages in thread
From: Daniel Barkalow @ 2005-04-18 2:37 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Petr Baudis, git
This ports rev-tree to use the parsing functions introduced in the
previous patches.
Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org>
Index: Makefile
===================================================================
--- 5ca133e1b74aee39b2124c0ec9fd51539babb5e0/Makefile (mode:100644 sha1:773166a462f88b1c69930ce36d336d3d7badc319)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/Makefile (mode:100644 sha1:c8908268d3c2253d3905671de5cabe4c84674128)
@@ -52,8 +52,8 @@
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)
Index: rev-tree.c
===================================================================
--- 5ca133e1b74aee39b2124c0ec9fd51539babb5e0/rev-tree.c (mode:100644 sha1:2d331b04c8243baab9546611ced07ba3439ab8ae)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/rev-tree.c (mode:100644 sha1:38e992ac027c733f38b18932caa4032849936d05)
@@ -4,7 +4,7 @@
#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
@@ -18,38 +18,7 @@
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);
- 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);
- }
- }
- fclose(file);
+ die("no revtree cache file yet");
}
/*
@@ -61,16 +30,16 @@
* 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;
}
@@ -82,6 +51,18 @@
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>]
*
@@ -119,7 +100,7 @@
}
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++;
}
@@ -127,22 +108,30 @@
* 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]), 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");
^ permalink raw reply [flat|nested] 16+ messages in thread* [4/5] Port fsck-cache to use parsing functions
2005-04-18 2:33 ` [0/5] Parsers for git objects, porting some programs Daniel Barkalow
` (2 preceding siblings ...)
2005-04-18 2:37 ` [3/5] Port rev-tree to " Daniel Barkalow
@ 2005-04-18 2:40 ` Daniel Barkalow
2005-04-18 2:42 ` [5/5] Switch implementations of merge-base, port to parsing Daniel Barkalow
2005-04-18 18:34 ` [0/5] Parsers for git objects, porting some programs Linus Torvalds
5 siblings, 0 replies; 16+ messages in thread
From: Daniel Barkalow @ 2005-04-18 2:40 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Petr Baudis, git
This ports fsck-cache to use parsing functions. Note that performance
could be improved here by only reading each object once, but this requires
somewhat more complicated flow control.
Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org>
Index: Makefile
===================================================================
--- 499f6cf77edad6935da0106cca4472e50fdbde34/Makefile (mode:100644 sha1:f00a9c3c1cdbfef7e96cfa98256aad35e63131e7)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/Makefile (mode:100644 sha1:c8908268d3c2253d3905671de5cabe4c84674128)
@@ -43,8 +43,8 @@
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)
Index: fsck-cache.c
===================================================================
--- 499f6cf77edad6935da0106cca4472e50fdbde34/fsck-cache.c (mode:100644 sha1:cff04ce34e9445cd57db9c1026040d56f045e5e7)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/fsck-cache.c (mode:100644 sha1:2000f16efc84911a51a40664fef8a637c90e2dcc)
@@ -3,7 +3,11 @@
#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];
@@ -13,96 +17,54 @@
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\n", 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\n", sha1_to_hex(rev->sha1));
- break;
- case USED:
- printf("missing %s\n", sha1_to_hex(rev->sha1));
- break;
- case SEEN:
- printf("dangling %s\n", 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 * tag, unsigned char *child)
-{
- struct revision * child_rev = add_relationship(lookup_rev(parent), child);
- child_rev->flags |= USED;
-}
-
-static int mark_sha1_seen(unsigned char *sha1, char *tag)
-{
- struct revision *rev = lookup_rev(sha1);
-
- 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, S_ISDIR(mode) ? "tree" : "blob", file_sha1);
+ 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, "tree", tree_sha1);
- 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);
- 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;
@@ -111,7 +73,7 @@
return -1;
} else
return -1;
- return mark_sha1_seen(sha1, tag);
+ return 0;
}
static int fsck_name(char *hex)
@@ -125,7 +87,8 @@
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;
@@ -186,7 +149,10 @@
continue;
}
if (!get_sha1_hex(argv[i], head_sha1)) {
- mark_reachable(lookup_rev(head_sha1), REACHABLE);
+ struct object *obj =
+ &lookup_commit(head_sha1)->object;
+ obj->used = 1;
+ mark_reachable(obj, REACHABLE);
heads++;
continue;
}
^ permalink raw reply [flat|nested] 16+ messages in thread* [5/5] Switch implementations of merge-base, port to parsing
2005-04-18 2:33 ` [0/5] Parsers for git objects, porting some programs Daniel Barkalow
` (3 preceding siblings ...)
2005-04-18 2:40 ` [4/5] Port fsck-cache to use " Daniel Barkalow
@ 2005-04-18 2:42 ` Daniel Barkalow
2005-04-18 18:34 ` [0/5] Parsers for git objects, porting some programs Linus Torvalds
5 siblings, 0 replies; 16+ messages in thread
From: Daniel Barkalow @ 2005-04-18 2:42 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Petr Baudis, git
This switches to my implementation of merge-base, but with the new parsing
library.
Signed-Off-By: Daniel Barkalow <barkalow@iabervon.org>
Index: Makefile
===================================================================
--- 108bfb69c14c55c3c6e30a298307390c82cf1b3b/Makefile (mode:100644 sha1:affc0e96030d4514f8306ee29020ca6bb320648f)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/Makefile (mode:100644 sha1:c8908268d3c2253d3905671de5cabe4c84674128)
@@ -64,8 +64,8 @@
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)
read-cache.o: cache.h
show-diff.o: cache.h
Index: merge-base.c
===================================================================
--- 108bfb69c14c55c3c6e30a298307390c82cf1b3b/merge-base.c (mode:100644 sha1:c98cad0befcf7e04fcc329d9bb7cb550506a4574)
+++ 1172a9b8f45b2fd640985595cc5258db3b027828/merge-base.c (mode:100644 sha1:414ff419c679dba122b2f21b698c1e2c8abdd965)
@@ -1,57 +1,95 @@
+#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.
- */
- parse_commit(rev1);
- parse_commit(rev2);
-
- common = common_parent(lookup_rev(rev1), lookup_rev(rev2));
- if (!common)
- die("no common parent found");
- printf("%s\n", sha1_to_hex(common->sha1));
- return 0;
+ 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) {
+ printf("%s\n", sha1_to_hex(ret->object.sha1));
+ return 0;
+ } else {
+ return 1;
+ }
+
}
^ permalink raw reply [flat|nested] 16+ messages in thread* Re: [0/5] Parsers for git objects, porting some programs
2005-04-18 2:33 ` [0/5] Parsers for git objects, porting some programs Daniel Barkalow
` (4 preceding siblings ...)
2005-04-18 2:42 ` [5/5] Switch implementations of merge-base, port to parsing Daniel Barkalow
@ 2005-04-18 18:34 ` Linus Torvalds
2005-04-18 20:12 ` Daniel Barkalow
5 siblings, 1 reply; 16+ messages in thread
From: Linus Torvalds @ 2005-04-18 18:34 UTC (permalink / raw)
To: Daniel Barkalow; +Cc: Petr Baudis, git
On Sun, 17 Apr 2005, Daniel Barkalow wrote:
>
> This series introduces common parsers for objects, and ports the programs
> that currently use revision.h to them.
>
> 1: the header files
> 2: the implementations
> 3: port rev-tree
> 4: port fsck-cache
> 5: port merge-base
Ok, having now looked at the code, I don't have any objections at all.
Could you clarify the "fsck" issue about reading the same object twice?
When does that happen?
Linus
^ permalink raw reply [flat|nested] 16+ messages in thread* Re: [0/5] Parsers for git objects, porting some programs
2005-04-18 18:34 ` [0/5] Parsers for git objects, porting some programs Linus Torvalds
@ 2005-04-18 20:12 ` Daniel Barkalow
2005-04-19 1:15 ` Junio C Hamano
0 siblings, 1 reply; 16+ messages in thread
From: Daniel Barkalow @ 2005-04-18 20:12 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Petr Baudis, git
On Mon, 18 Apr 2005, Linus Torvalds wrote:
> On Sun, 17 Apr 2005, Daniel Barkalow wrote:
> >
> > This series introduces common parsers for objects, and ports the programs
> > that currently use revision.h to them.
> >
> > 1: the header files
> > 2: the implementations
> > 3: port rev-tree
> > 4: port fsck-cache
> > 5: port merge-base
>
> Ok, having now looked at the code, I don't have any objections at all.
> Could you clarify the "fsck" issue about reading the same object twice?
> When does that happen?
Currently, the fsck-cache code is unpacking the objects to find out what
type they are, and the old code would pass the unpacked objects to the
parsing code. The new code doesn't take the unpacked objects, so it
unpacks them again. (I.e., fsck-cache will look at each object exactly
twice). The right solution is to have the internals reorganized slightly
such that a "parse_object" method, which does what fsck-cache wants (i.e.,
parse this object regardless of what type it is, and tell me the type),
could be fit in efficiently. But it doesn't affect the header file
interface, and it's only relevant to fsck-cache, which wants to look at
random junk that it doesn't have a reference to.
-Daniel
*This .sig left intentionally blank*
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [0/5] Parsers for git objects, porting some programs
2005-04-18 20:12 ` Daniel Barkalow
@ 2005-04-19 1:15 ` Junio C Hamano
2005-04-19 1:23 ` Daniel Barkalow
2005-04-19 2:04 ` Daniel Barkalow
0 siblings, 2 replies; 16+ messages in thread
From: Junio C Hamano @ 2005-04-19 1:15 UTC (permalink / raw)
To: Daniel Barkalow; +Cc: Linus Torvalds, Petr Baudis, git
>>>>> "DB" == Daniel Barkalow <barkalow@iabervon.org> writes:
DB> On Mon, 18 Apr 2005, Linus Torvalds wrote:
>> On Sun, 17 Apr 2005, Daniel Barkalow wrote:
>> >
>> > This series introduces common parsers for objects, and ports the programs
>> > that currently use revision.h to them.
>> >
>> > 1: the header files
>> > 2: the implementations
>> > 3: port rev-tree
>> > 4: port fsck-cache
>> > 5: port merge-base
>>
>> Ok, having now looked at the code, I don't have any objections at all.
I was looking at the tree part and am thinking that it would
make it much nicer if your tree object records path for each
entry. Currently it just borrows from object.refs to represent
its children, which is good enough for the applications listed
above (none of them would care where in the tree the object
belongs to), but I was thinking about an incremental dumper I
talked about in another thread and noticed that I cannot use the
current struct tree as is to compare two trees to find related
sha1 files (then I would inflate both, run diff and record the
output as a recipe to create one sha1 object from the other).
Or am I misreading the code that parses tree objects?
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [0/5] Parsers for git objects, porting some programs
2005-04-19 1:15 ` Junio C Hamano
@ 2005-04-19 1:23 ` Daniel Barkalow
2005-04-19 2:04 ` Daniel Barkalow
1 sibling, 0 replies; 16+ messages in thread
From: Daniel Barkalow @ 2005-04-19 1:23 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Linus Torvalds, Petr Baudis, git
On Mon, 18 Apr 2005, Junio C Hamano wrote:
> I was looking at the tree part and am thinking that it would
> make it much nicer if your tree object records path for each
> entry.
You're entirely right, and I've actually now written the code that does
it. I'm planning to send out a patch for that shortly.
> Currently it just borrows from object.refs to represent
> its children
Note that object.refs needs to get filled out for those
applications, even if the information is also included in the
parse; object.refs is for finding what you can reach without worrying
about how you do it.
-Daniel
*This .sig left intentionally blank*
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [0/5] Parsers for git objects, porting some programs
2005-04-19 1:15 ` Junio C Hamano
2005-04-19 1:23 ` Daniel Barkalow
@ 2005-04-19 2:04 ` Daniel Barkalow
1 sibling, 0 replies; 16+ messages in thread
From: Daniel Barkalow @ 2005-04-19 2:04 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Linus Torvalds, Petr Baudis, git
On Mon, 18 Apr 2005, Junio C Hamano wrote:
> >>>>> "DB" == Daniel Barkalow <barkalow@iabervon.org> writes:
>
> DB> On Mon, 18 Apr 2005, Linus Torvalds wrote:
> >> On Sun, 17 Apr 2005, Daniel Barkalow wrote:
> >> >
> >> > This series introduces common parsers for objects, and ports the programs
> >> > that currently use revision.h to them.
> >> >
> >> > 1: the header files
> >> > 2: the implementations
> >> > 3: port rev-tree
> >> > 4: port fsck-cache
> >> > 5: port merge-base
> >>
> >> Ok, having now looked at the code, I don't have any objections at all.
>
> I was looking at the tree part and am thinking that it would
> make it much nicer if your tree object records path for each
> entry.
As it turns out, the code I just doesn't actually record the path; it does
everything else, and it should be easy to add the path to those entries. I
mainly wanted object type (i.e., do I have to recurse into the object), so
I skipped that one. But it should now be clear what you need to add.
-Daniel
*This .sig left intentionally blank*
^ permalink raw reply [flat|nested] 16+ messages in thread