Re: [PATCH 00/17] Clean up how fetch_pack() handles the heads list

[Michael Haggerty <mhagger@alum.mit.edu>]

[-- Attachment #1: Type: text/plain, Size: 1511 bytes --]

On 08/23/2012 10:31 PM, Jeff King wrote:
> I think part of the confusion of this code is that inside the loop over
> the refs it is sometimes checking aspects of the ref, and sometimes
> checking invariants of the loop (like args.fetch_all). Splitting it into
> separate loops makes it easier to see what is going on, like the patch
> below (on top of Michael's series).
> 
> I'm not sure if it ends up being more readable, since the generic "cut
> down this linked list" function has to operate through callbacks with a
> void pointer. On the other hand, that function could also be used
> elsewhere.
> [...]

Despite requiring a bit more boilerplate, I think that your change makes
the logic clearer.

*If* we want to switch to using callbacks, then we can get even more
bang for the buck, as in the attached patch (which applies on top of my
patch v2).  Beyond your suggestion, this patch:

* Inlines your filter_refs() into everything_local(), because (a) it's
short and (b) the policy work implemented there logically belongs
higher-up in the call chain.

* Renames your filter_refs_callback() to filter_refs().

* Moves the initialization of the filter_by_name_data structure
(including sorting and de-duping) all the way up to fetch_pack(), and
passes a filter_by_name_data* (rather than (nr_heads, heads)) down to
the callees.

If you like this change, let me know and I'll massage it into a
digestible patch series.

Michael
-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

[-- Attachment #2: jk-filter-callback.patch --]
[-- Type: text/x-patch, Size: 6844 bytes --]

diff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c
index db77ee6..d1dabcf 100644
--- a/builtin/fetch-pack.c
+++ b/builtin/fetch-pack.c
@@ -521,51 +521,91 @@ static void mark_recent_complete_commits(unsigned long cutoff)
 	}
 }
 
-static void filter_refs(struct ref **refs, int *nr_heads, char **heads)
+static void filter_refs(struct ref **refs,
+			int (*want)(struct ref *, void *),
+			void *data)
 {
-	struct ref *newlist = NULL;
-	struct ref **newtail = &newlist;
+	struct ref **tail = refs;
 	struct ref *ref, *next;
-	int head_pos = 0, unmatched = 0;
 
 	for (ref = *refs; ref; ref = next) {
-		int keep_ref = 0;
 		next = ref->next;
-		if (!memcmp(ref->name, "refs/", 5) &&
-		    check_refname_format(ref->name, 0))
-			; /* trash */
-		else if (args.fetch_all &&
-			   (!args.depth || prefixcmp(ref->name, "refs/tags/")))
-			keep_ref = 1;
-		else
-			while (head_pos < *nr_heads) {
-				int cmp = strcmp(ref->name, heads[head_pos]);
-				if (cmp < 0) { /* definitely do not have it */
-					break;
-				} else if (cmp == 0) { /* definitely have it */
-					free(heads[head_pos++]);
-					keep_ref = 1;
-					break;
-				} else { /* might have it; keep looking */
-					heads[unmatched++] = heads[head_pos++];
-				}
-			}
-
-		if (keep_ref) {
-			*newtail = ref;
-			ref->next = NULL;
-			newtail = &ref->next;
-		} else {
+		if (want(ref, data))
+			tail = &ref->next;
+		else {
 			free(ref);
+			*tail = next;
 		}
 	}
+}
 
-	/* copy any remaining unmatched heads: */
-	while (head_pos < *nr_heads)
-		heads[unmatched++] = heads[head_pos++];
-	*nr_heads = unmatched;
+static int ref_name_is_ok(struct ref *ref, void *data)
+{
+	return memcmp(ref->name, "refs/", 5) ||
+		!check_refname_format(ref->name, 0);
+}
+
+static int ref_ok_for_shallow(struct ref *ref, void *data)
+{
+	return prefixcmp(ref->name, "refs/tags/");
+}
+
+static int compare_heads(const void *a, const void *b)
+{
+	return strcmp(*(const char **)a, *(const char **)b);
+}
+
+static int remove_duplicates(int nr_heads, char **heads)
+{
+	int src, dst;
+	for (src = dst = 1; src < nr_heads; src++)
+		if (strcmp(heads[src], heads[dst-1]))
+			heads[dst++] = heads[src];
+		else
+			free(heads[src]);
+	return dst;
+}
 
-	*refs = newlist;
+struct filter_by_name_data {
+	char **heads;
+	int *nr_heads;
+	int head_pos;
+	int unmatched;
+};
+
+static void filter_by_name_init(struct filter_by_name_data *f,
+			 int *nr_heads, char **heads)
+{
+	memset(f, 0, sizeof(*f));
+	f->heads = heads;
+	f->nr_heads = nr_heads;
+	qsort(f->heads, *f->nr_heads, sizeof(*f->heads), compare_heads);
+	*f->nr_heads = remove_duplicates(*f->nr_heads, f->heads);
+}
+
+static int filter_by_name_want(struct ref *ref, void *data)
+{
+	struct filter_by_name_data *f = data;
+
+	while (f->head_pos < *f->nr_heads) {
+		int cmp = strcmp(ref->name, f->heads[f->head_pos]);
+		if (cmp < 0) /* definitely do not have it */
+			return 0;
+		else if (cmp == 0) { /* definitely have it */
+			free(f->heads[f->head_pos++]);
+			return 1;
+		} else /* might have it; keep looking */
+			f->heads[f->unmatched++] = f->heads[f->head_pos++];
+	}
+	return 0;
+}
+
+static void filter_by_name_finish(struct filter_by_name_data *f)
+{
+	/* copy any remaining unmatched heads: */
+	while (f->head_pos < *f->nr_heads)
+		f->heads[f->unmatched++] = f->heads[f->head_pos++];
+	*f->nr_heads = f->unmatched;
 }
 
 static void mark_alternate_complete(const struct ref *ref, void *unused)
@@ -573,7 +613,8 @@ static void mark_alternate_complete(const struct ref *ref, void *unused)
 	mark_complete(NULL, ref->old_sha1, 0, NULL);
 }
 
-static int everything_local(struct ref **refs, int *nr_heads, char **heads)
+static int everything_local(struct ref **refs,
+			    struct filter_by_name_data *filter_by_name_data)
 {
 	struct ref *ref;
 	int retval;
@@ -624,7 +665,14 @@ static int everything_local(struct ref **refs, int *nr_heads, char **heads)
 		}
 	}
 
-	filter_refs(refs, nr_heads, heads);
+	filter_refs(refs, ref_name_is_ok, NULL);
+
+	if (args.fetch_all) {
+		if (args.depth)
+			filter_refs(refs, ref_ok_for_shallow, NULL);
+	} else if (filter_by_name_data) {
+		filter_refs(refs, filter_by_name_want, filter_by_name_data);
+	}
 
 	for (retval = 1, ref = *refs; ref ; ref = ref->next) {
 		const unsigned char *remote = ref->old_sha1;
@@ -754,9 +802,9 @@ static int get_pack(int xd[2], char **pack_lockfile)
 }
 
 static struct ref *do_fetch_pack(int fd[2],
-		const struct ref *orig_ref,
-		int *nr_heads, char **heads,
-		char **pack_lockfile)
+				 const struct ref *orig_ref,
+				 struct filter_by_name_data *filter_by_name_data,
+				 char **pack_lockfile)
 {
 	struct ref *ref = copy_ref_list(orig_ref);
 	unsigned char sha1[20];
@@ -796,7 +844,7 @@ static struct ref *do_fetch_pack(int fd[2],
 			fprintf(stderr, "Server supports ofs-delta\n");
 	} else
 		prefer_ofs_delta = 0;
-	if (everything_local(&ref, nr_heads, heads)) {
+	if (everything_local(&ref, filter_by_name_data)) {
 		packet_flush(fd[1]);
 		goto all_done;
 	}
@@ -816,21 +864,6 @@ static struct ref *do_fetch_pack(int fd[2],
 	return ref;
 }
 
-static int remove_duplicates(int nr_heads, char **heads)
-{
-	int src, dst;
-
-	if (!nr_heads)
-		return 0;
-
-	for (src = dst = 1; src < nr_heads; src++)
-		if (strcmp(heads[src], heads[dst-1]))
-			heads[dst++] = heads[src];
-		else
-			free(heads[src]);
-	return dst;
-}
-
 static int fetch_pack_config(const char *var, const char *value, void *cb)
 {
 	if (strcmp(var, "fetch.unpacklimit") == 0) {
@@ -1030,11 +1063,6 @@ int cmd_fetch_pack(int argc, const char **argv, const char *prefix)
 	return ret;
 }
 
-static int compare_heads(const void *a, const void *b)
-{
-	return strcmp(*(const char **)a, *(const char **)b);
-}
-
 struct ref *fetch_pack(struct fetch_pack_args *my_args,
 		       int fd[], struct child_process *conn,
 		       const struct ref *ref,
@@ -1045,6 +1073,7 @@ struct ref *fetch_pack(struct fetch_pack_args *my_args,
 {
 	struct stat st;
 	struct ref *ref_cpy;
+	struct filter_by_name_data name_data, *filter_by_name_data;
 
 	fetch_pack_setup();
 	if (&args != my_args)
@@ -1054,16 +1083,20 @@ struct ref *fetch_pack(struct fetch_pack_args *my_args,
 			st.st_mtime = 0;
 	}
 
-	if (heads && *nr_heads) {
-		qsort(heads, *nr_heads, sizeof(*heads), compare_heads);
-		*nr_heads = remove_duplicates(*nr_heads, heads);
-	}
-
 	if (!ref) {
 		packet_flush(fd[1]);
 		die("no matching remote head");
 	}
-	ref_cpy = do_fetch_pack(fd, ref, nr_heads, heads, pack_lockfile);
+	if (heads && *nr_heads) {
+		filter_by_name_data = &name_data;
+		filter_by_name_init(filter_by_name_data, nr_heads, heads);
+	} else
+		filter_by_name_data = NULL;
+
+	ref_cpy = do_fetch_pack(fd, ref, filter_by_name_data, pack_lockfile);
+
+	if (filter_by_name_data)
+		filter_by_name_finish(filter_by_name_data);
 
 	if (args.depth > 0) {
 		struct cache_time mtime;