From b5af9107270171b79d46b099ee0b198e653f3a24 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Fri, 22 Apr 2005 17:15:28 -0700 Subject: New "diff-cache" implementation. This one is about a million times simpler, and much more likely to be correct too. Instead of trying to match up a tree object against the index, we just read in the tree object side-by-side into the index, and just walk the resulting index file. This was what all the read-tree cleanups were all getting to. diff --git a/cache.h b/cache.h index 69dc877..bf30ac4 100644 --- a/cache.h +++ b/cache.h @@ -99,7 +99,9 @@ extern int read_cache(void); extern int write_cache(int newfd, struct cache_entry **cache, int entries); extern int cache_name_pos(const char *name, int namelen); extern int add_cache_entry(struct cache_entry *ce, int ok_to_add); +extern int remove_entry_at(int pos); extern int remove_file_from_cache(char *path); +extern int same_name(struct cache_entry *a, struct cache_entry *b); extern int cache_match_stat(struct cache_entry *ce, struct stat *st); #define MTIME_CHANGED 0x0001 diff --git a/diff-cache.c b/diff-cache.c index 5e1d1a6..b407d75 100644 --- a/diff-cache.c +++ b/diff-cache.c @@ -1,220 +1,90 @@ #include "cache.h" static int cached_only = 0; -static int recursive = 0; static int line_termination = '\n'; -static int diff_cache(void *tree, unsigned long size, struct cache_entry **ac, int entries, const char *base); - -static void update_tree_entry(void **bufp, unsigned long *sizep) -{ - void *buf = *bufp; - unsigned long size = *sizep; - int len = strlen(buf) + 1 + 20; - - if (size < len) - die("corrupt tree file 1 (%s)", size); - *bufp = buf + len; - *sizep = size - len; -} - -static const unsigned char *extract(void *tree, unsigned long size, const char **pathp, unsigned int *modep) -{ - int len = strlen(tree)+1; - const unsigned char *sha1 = tree + len; - const char *path = strchr(tree, ' '); - - if (!path || size < len + 20 || sscanf(tree, "%o", modep) != 1) - die("corrupt tree file 2 (%d)", size); - *pathp = path+1; - return sha1; -} - -static char *malloc_base(const char *base, const char *path, int pathlen) -{ - int baselen = strlen(base); - char *newbase = malloc(baselen + pathlen + 2); - memcpy(newbase, base, baselen); - memcpy(newbase + baselen, path, pathlen); - memcpy(newbase + baselen + pathlen, "/", 2); - return newbase; -} - -static void show_file(const char *prefix, const char *path, unsigned int mode, const unsigned char *sha1, const char *base); - -/* A whole sub-tree went away or appeared */ -static void show_tree(const char *prefix, void *tree, unsigned long size, const char *base) -{ - while (size) { - const char *path; - unsigned int mode; - const unsigned char *sha1 = extract(tree, size, &path, &mode); - - show_file(prefix, path, mode, sha1, base); - update_tree_entry(&tree, &size); - } -} - /* A file entry went away or appeared */ -static void show_file(const char *prefix, const char *path, unsigned int mode, const unsigned char *sha1, const char *base) +static void show_file(const char *prefix, struct cache_entry *ce) { - if (recursive && S_ISDIR(mode)) { - char type[20]; - unsigned long size; - char *newbase = malloc_base(base, path, strlen(path)); - void *tree; - - tree = read_sha1_file(sha1, type, &size); - if (!tree || strcmp(type, "tree")) - die("corrupt tree sha %s", sha1_to_hex(sha1)); - - show_tree(prefix, tree, size, newbase); - - free(tree); - free(newbase); - return; - } - - printf("%s%o\t%s\t%s\t%s%s%c", prefix, mode, - S_ISDIR(mode) ? "tree" : "blob", - sha1_to_hex(sha1), base, path, - line_termination); + printf("%s%o\t%s\t%s\t%s%c", prefix, ntohl(ce->ce_mode), "blob", + sha1_to_hex(ce->sha1), ce->name, line_termination); } -static int compare_tree_entry(const char *path1, unsigned int mode1, const unsigned char *sha1, - struct cache_entry **ac, int *entries, const char *base) +static int show_modified(struct cache_entry *old, struct cache_entry *new) { - int baselen = strlen(base); - struct cache_entry *ce = *ac; - const char *path2 = ce->name + baselen; - unsigned int mode2 = ntohl(ce->ce_mode); - const unsigned char *sha2 = ce->sha1; - int cmp, pathlen1, pathlen2; - char old_sha1_hex[50]; - - pathlen1 = strlen(path1); - pathlen2 = strlen(path2); - cmp = cache_name_compare(path1, pathlen1, path2, pathlen2); - if (cmp < 0) { - if (S_ISDIR(mode1)) { - char type[20]; - unsigned long size; - void *tree = read_sha1_file(sha1, type, &size); - char *newbase = malloc(baselen + 2 + pathlen1); - - memcpy(newbase, base, baselen); - memcpy(newbase + baselen, path1, pathlen1); - memcpy(newbase + baselen + pathlen1, "/", 2); - if (!tree || strcmp(type, "tree")) - die("unable to read tree object %s", sha1_to_hex(sha1)); - *entries = diff_cache(tree, size, ac, *entries, newbase); - free(newbase); - free(tree); - return -1; - } - show_file("-", path1, mode1, sha1, base); - return -1; - } + unsigned int mode = ntohl(new->ce_mode), oldmode; + unsigned char *sha1 = new->sha1; + unsigned char old_sha1_hex[60]; if (!cached_only) { static unsigned char no_sha1[20]; - int fd, changed; + int changed; struct stat st; - fd = open(ce->name, O_RDONLY); - if (fd < 0 || fstat(fd, &st) < 0) { - show_file("-", path1, mode1, sha1, base); + if (stat(new->name, &st) < 0) { + show_file("-", old); return -1; } - changed = cache_match_stat(ce, &st); - close(fd); + changed = cache_match_stat(new, &st); if (changed) { - mode2 = st.st_mode; - sha2 = no_sha1; + mode = st.st_mode; + sha1 = no_sha1; } } - if (cmp > 0) { - show_file("+", path2, mode2, sha2, base); - return 1; - } - if (!memcmp(sha1, sha2, 20) && mode1 == mode2) + oldmode = ntohl(old->ce_mode); + if (mode == oldmode && !memcmp(sha1, old->sha1, 20)) return 0; - /* - * If the filemode has changed to/from a directory from/to a regular - * file, we need to consider it a remove and an add. - */ - if (S_ISDIR(mode1) || S_ISDIR(mode2)) { - show_file("-", path1, mode1, sha1, base); - show_file("+", path2, mode2, sha2, base); - return 0; - } - - strcpy(old_sha1_hex, sha1_to_hex(sha1)); - printf("*%o->%o\t%s\t%s->%s\t%s%s%c", mode1, mode2, - S_ISDIR(mode1) ? "tree" : "blob", - old_sha1_hex, sha1_to_hex(sha2), base, path1, - line_termination); + strcpy(old_sha1_hex, sha1_to_hex(old->sha1)); + printf("*%o->%o\t%s\t%s->%s\t%s%c", oldmode, mode, + "blob", + old_sha1_hex, sha1_to_hex(sha1), + old->name, line_termination); return 0; } -static int diff_cache(void *tree, unsigned long size, struct cache_entry **ac, int entries, const char *base) +static int diff_cache(struct cache_entry **ac, int entries) { - int baselen = strlen(base); - - for (;;) { - struct cache_entry *ce; - unsigned int mode; - const char *path; - const unsigned char *sha1; - int left; - - /* - * No entries in the cache (with this base)? - * Output the tree contents. - */ - if (!entries || ce_namelen(ce = *ac) < baselen || memcmp(ce->name, base, baselen)) { - if (!size) - return entries; - sha1 = extract(tree, size, &path, &mode); - show_file("-", path, mode, sha1, base); - update_tree_entry(&tree, &size); - continue; - } + while (entries) { + struct cache_entry *ce = *ac; - /* - * No entries in the tree? Output the cache contents - */ - if (!size) { - show_file("+", ce->name, ntohl(ce->ce_mode), ce->sha1, ""); + /* No matching 0-stage (current) entry? Show it as deleted */ + if (ce_stage(ce)) { + show_file("-", ce); ac++; entries--; continue; } - - sha1 = extract(tree, size, &path, &mode); - left = entries; - switch (compare_tree_entry(path, mode, sha1, ac, &left, base)) { - case -1: - update_tree_entry(&tree, &size); - if (left < entries) { - ac += (entries - left); - entries = left; - } - continue; - case 0: - update_tree_entry(&tree, &size); - /* Fallthrough */ - case 1: + /* No matching 1-stage (tree) entry? Show the current one as added */ + if (entries == 1 || !same_name(ce, ac[1])) { + show_file("-", ce); ac++; entries--; continue; } - die("diff-cache: internal error"); + show_modified(ac[1], ce); + ac += 2; + entries -= 2; + continue; } return 0; } +static void remove_merge_entries(void) +{ + int i; + for (i = 0; i < active_nr; i++) { + struct cache_entry *ce = active_cache[i]; + if (!ce_stage(ce)) + break; + printf("%s: unmerged\n", ce->name); + while (remove_entry_at(i)) { + if (!ce_stage(active_cache[i])) + break; + } + } +} + static char *diff_cache_usage = "diff-cache [-r] [-z] [--cached] "; int main(int argc, char **argv) @@ -229,7 +99,7 @@ int main(int argc, char **argv) argv++; argc--; if (!strcmp(arg, "-r")) { - recursive = 1; + /* We accept the -r flag just to look like diff-tree */ continue; } if (!strcmp(arg, "-z")) { @@ -246,9 +116,13 @@ int main(int argc, char **argv) if (argc != 2 || get_sha1_hex(argv[1], tree_sha1)) usage(diff_cache_usage); + remove_merge_entries(); + tree = read_tree_with_tree_or_commit_sha1(tree_sha1, &size, 0); if (!tree) die("bad tree object %s", argv[1]); + if (read_tree(tree, size, 1)) + die("unable to read tree object %s", argv[1]); - return diff_cache(tree, size, active_cache, active_nr, ""); + return diff_cache(active_cache, active_nr); } diff --git a/read-cache.c b/read-cache.c index 4b668be..f67aceb 100644 --- a/read-cache.c +++ b/read-cache.c @@ -87,7 +87,7 @@ int cache_name_pos(const char *name, int namelen) } /* Remove entry, return true if there are more entries to go.. */ -static int remove_entry_at(int pos) +int remove_entry_at(int pos) { active_nr--; if (pos >= active_nr) @@ -106,7 +106,7 @@ int remove_file_from_cache(char *path) return 0; } -static int same_name(struct cache_entry *a, struct cache_entry *b) +int same_name(struct cache_entry *a, struct cache_entry *b) { int len = ce_namelen(a); return ce_namelen(b) == len && !memcmp(a->name, b->name, len); -- cgit v0.10.2-6-g49f6