From 8500349208e6bfd0e8bc67d294bfea93da2328a2 Mon Sep 17 00:00:00 2001
From: Linus Torvalds <torvalds@ppc970.osdl.org>
Date: Mon, 2 May 2005 16:13:18 -0700
Subject: [PATCH] Make fsck-cache do better tree checking.

We check the ordering of the entries, and we verify that none
of the entries has a slash in it (this allows us to remove the
hacky "has_full_path" member from the tree structure, since we
now just test it by walking the tree entries instead).
---
 fsck-cache.c | 58 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 tree.c       |  5 -----
 tree.h       |  1 -
 3 files changed, 57 insertions(+), 7 deletions(-)

diff --git a/fsck-cache.c b/fsck-cache.c
index cb01095747..7dda9c3eb7 100644
--- a/fsck-cache.c
+++ b/fsck-cache.c
@@ -53,13 +53,69 @@ static void check_connectivity(void)
 	}
 }
 
+/*
+ * The entries in a tree are ordered in the _path_ order,
+ * which means that a directory entry is ordered by adding
+ * a slash to the end of it.
+ *
+ * So a directory called "a" is ordered _after_ a file
+ * called "a.c", because "a/" sorts after "a.c".
+ */
+static int verify_ordered(struct tree_entry_list *a, struct tree_entry_list *b)
+{
+	int len1 = strlen(a->name);
+	int len2 = strlen(b->name);
+	int len = len1 < len2 ? len1 : len2;
+	unsigned char c1, c2;
+	int cmp;
+
+	cmp = memcmp(a->name, b->name, len);
+	if (cmp < 0)
+		return 0;
+	if (cmp > 0)
+		return -1;
+
+	/*
+	 * Ok, the first <len> characters are the same.
+	 * Now we need to order the next one, but turn
+	 * a '\0' into a '/' for a directory entry.
+	 */
+	c1 = a->name[len];
+	c2 = b->name[len];
+	if (!c1 && a->directory)
+		c1 = '/';
+	if (!c2 && b->directory)
+		c2 = '/';
+	return c1 < c2 ? 0 : -1;
+}
+
 static int fsck_tree(struct tree *item)
 {
-	if (item->has_full_path) {
+	int has_full_path = 0;
+	struct tree_entry_list *entry, *last;
+
+	last = NULL;
+	for (entry = item->entries; entry; entry = entry->next) {
+		if (strchr(entry->name, '/'))
+			has_full_path = 1;
+
+		if (last) {
+			if (verify_ordered(last, entry) < 0) {
+				fprintf(stderr, "tree %s not ordered\n",
+					sha1_to_hex(item->object.sha1));
+				return -1;
+			}
+		}
+
+		last = entry;
+	}
+
+	if (has_full_path) {
 		fprintf(stderr, "warning: fsck-cache: tree %s "
 			"has full pathnames in it\n", 
 			sha1_to_hex(item->object.sha1));
 	}
+
 	return 0;
 }
 
diff --git a/tree.c b/tree.c
index 15a16d5606..72305a357b 100644
--- a/tree.c
+++ b/tree.c
@@ -122,11 +122,6 @@ int parse_tree(struct tree *item)
 		entry->executable = mode & S_IXUSR;
 		entry->next = NULL;
 
-		/* Warn about trees that don't do the recursive thing.. */
-		if (strchr(path, '/')) {
-			item->has_full_path = 1;
-		}
-
 		bufptr += len + 20;
 		size -= len + 20;
 
diff --git a/tree.h b/tree.h
index 19b1905659..96cf4291d1 100644
--- a/tree.h
+++ b/tree.h
@@ -18,7 +18,6 @@ struct tree_entry_list {
 
 struct tree {
 	struct object object;
-	unsigned has_full_path : 1;
 	struct tree_entry_list *entries;
 };
 
-- 
2.11.4.GIT