threads / rfc / 5662

RFC patchfor_each_ref() returning heads in wrong order

Subject: [RFC][PATCH] for_each_ref() returning heads in wrong order

## tl;dr

6 messages between Sep 23, 2006 and Sep 23, 2006. Diffs are folded; open one to read it.

replies: 5people: 4as markdown or json

Petr Baudis· Sep 23, 2006, 16:36 UTC · lore

Using the #next branch I've now hit a problem with git-fetch-pack master choosing refs/bases/master (I geuss created by StGIT) instead of refs/heads/master. The old upload-pack returned the refs in the order heads-tags-everything_else but the new one just goes for whatever order readdir() returns them in (modulo merging with packed refs). I actually can't see the difference that caused this right now, though.

This is a _really ugly_ patch to fix that. I wonder if there's a more elegant solution to this.

If you have your refs already packed, you should somehow unpack them and then pack them again.

Signed-off-by: Petr Baudis <pasky@suse.cz>
---
 I send the patch with the hope that someone will be so irritated by it
that he'll create a nicer one. ;-)
 refs.c |   39 ++++++++++++++++++++++++++++++++++++---
 1 files changed, 36 insertions(+), 3 deletions(-)
Show changes to refs.c +36 −3
diff --git a/refs.c b/refs.c
index 2cef2b4..9b3986a 100644
--- a/refs.c
+++ b/refs.c
@@ -91,7 +91,8 @@ static struct ref_list *get_packed_refs(
 	return refs;
 }
 
-static struct ref_list *get_ref_dir(const char *base, struct ref_list *list)
+static struct ref_list *get_ref_dir(const char *base, struct ref_list *list,
+                                    char **except)
 {
 	DIR *dir = opendir(git_path("%s", base));
 
@@ -121,7 +122,13 @@ static struct ref_list *get_ref_dir(cons
 			if (stat(git_path("%s", ref), &st) < 0)
 				continue;
 			if (S_ISDIR(st.st_mode)) {
-				list = get_ref_dir(ref, list);
+				if (except) {
+					char **e;
+					for (e = except; *e; e++)
+						if (!strcmp(*e, ref))
+							goto nextitem;
+				}
+				list = get_ref_dir(ref, list, except);
 				continue;
 			}
 			if (!resolve_ref(ref, sha1, 1, &flag)) {
@@ -129,6 +136,7 @@ static struct ref_list *get_ref_dir(cons
 				continue;
 			}
 			list = add_ref(ref, sha1, flag, list);
+nextitem:;
 		}
 		free(ref);
 		closedir(dir);
@@ -142,7 +150,23 @@ static struct ref_list *get_loose_refs(v
 	static struct ref_list *refs = NULL;
 
 	if (!did_refs) {
-		refs = get_ref_dir("refs", NULL);
+		/* We need to make sure refs/heads and refs/tags always
+		 * go before everything else. */
+		char *except[] = {"refs/heads", "refs/tags", NULL};
+		struct ref_list *other_refs = NULL, *r;
+
+		refs = get_ref_dir("refs/heads", NULL, NULL);
+		refs = get_ref_dir("refs/tags", refs, NULL);
+
+		other_refs = get_ref_dir("refs", NULL, except);
+		if (refs) {
+			for (r = refs; r->next; r = r->next)
+				;
+			r->next = other_refs;
+		} else {
+			refs = other_refs;
+		}
+
 		did_refs = 1;
 	}
 	return refs;
@@ -298,10 +322,19 @@ static int do_for_each_ref(const char *b
 	while (packed && loose) {
 		struct ref_list *entry;
 		int cmp = strcmp(packed->name, loose->name);
+		int packed_is_ht, loose_is_ht;
 		if (!cmp) {
 			packed = packed->next;
 			continue;
 		}
+		/* We need to make sure refs/heads and refs/tags always
+		 * go before everything else. */
+		packed_is_ht = !strncmp(packed->name, "refs/heads", 10)
+		               || !strncmp(packed->name, "refs/tags", 9);
+		loose_is_ht = !strncmp(loose->name, "refs/heads", 10)
+		              || !strncmp(loose->name, "refs/tags", 9);
+		if (packed_is_ht != loose_is_ht)
+			cmp = loose_is_ht - packed_is_ht;
 		if (cmp > 0) {
 			entry = loose;
 			loose = loose->next;
Petr Baudis· Sep 23, 2006, 16:47 UTC · re: Petr Baudis · lore

Re: [RFC][PATCH] for_each_ref() returning heads in wrong order

Dear diary, on Sat, Sep 23, 2006 at 06:36:21PM CEST, I got a letter where Petr Baudis <pasky@suse.cz> said that...

Show 6 quoted lines
> Using the #next branch I've now hit a problem with git-fetch-pack
> master choosing refs/bases/master (I geuss created by StGIT) instead
> of refs/heads/master. The old upload-pack returned the refs in the order
> heads-tags-everything_else but the new one just goes for whatever order
> readdir() returns them in (modulo merging with packed refs). I actually
> can't see the difference that caused this right now, though.

Portion of this is obsolete, I've since noticed what the difference actually is - the _old_ one processed the directory unsorted and the new one actually keeps it sorted in add_ref().

Alternate approach would be just to modify add_ref() sort order to take heads and tags into account (but you still need to keep the cmp hack for merging packed/loose refs). Should be pretty easy to do, but I personally need to proceed with my TODO list for now since I've already a working workaround.

-- 
				Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
#!/bin/perl -sp0777i<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<j]dsj
$/=unpack('H*',$_);$_=`echo 16dio\U$k"SK$/SM$n\EsN0p[lN*1
lK[d2%Sa2/d0$^Ixp"|dc`;s/\W//g;$_=pack('H*',/((..)*)$/)
Johannes Schindelin· Sep 23, 2006, 17:20 UTC · re: Petr Baudis · lore

Re: [RFC][PATCH] for_each_ref() returning heads in wrong order

Hi,
On Sat, 23 Sep 2006, Petr Baudis wrote:
Show 8 quoted lines
> Dear diary, on Sat, Sep 23, 2006 at 06:36:21PM CEST, I got a letter
> where Petr Baudis <pasky@suse.cz> said that...
> > Using the #next branch I've now hit a problem with git-fetch-pack
> > master choosing refs/bases/master (I geuss created by StGIT) instead
> > of refs/heads/master. The old upload-pack returned the refs in the order
> > heads-tags-everything_else but the new one just goes for whatever order
> > readdir() returns them in (modulo merging with packed refs). I actually
> > can't see the difference that caused this right now, though.

Why don't you just specify (or match) "heads/refs/master", so that git-fetch-pack cannot choose anything wrong to begin with?

Ciao, Dscho

Petr Baudis· Sep 23, 2006, 17:42 UTC · re: Johannes Schindelin · lore

Re: [RFC][PATCH] for_each_ref() returning heads in wrong order

  Hi,

Dear diary, on Sat, Sep 23, 2006 at 07:20:42PM CEST, I got a letter where Johannes Schindelin <Johannes.Schindelin@gmx.de> said that...

Show 13 quoted lines
> On Sat, 23 Sep 2006, Petr Baudis wrote:
> 
> > Dear diary, on Sat, Sep 23, 2006 at 06:36:21PM CEST, I got a letter
> > where Petr Baudis <pasky@suse.cz> said that...
> > > Using the #next branch I've now hit a problem with git-fetch-pack
> > > master choosing refs/bases/master (I geuss created by StGIT) instead
> > > of refs/heads/master. The old upload-pack returned the refs in the order
> > > heads-tags-everything_else but the new one just goes for whatever order
> > > readdir() returns them in (modulo merging with packed refs). I actually
> > > can't see the difference that caused this right now, though.
> 
> Why don't you just specify (or match) "heads/refs/master", so that 
> git-fetch-pack cannot choose anything wrong to begin with?
  hmm, does git-fetch prepend refs/heads/ to the refspecs or does it
pass them as is to git-fetch-pack?
  If the former, then we could as well do that, but in that case I'd
rather just require that for any refs passed to git-fetch-pack since
passing the "short form" just serves for buggy scripts to get confused
when someone adds some refs directory that sorts before heads/ to the
repository.
-- 
				Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
#!/bin/perl -sp0777i<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<j]dsj
$/=unpack('H*',$_);$_=`echo 16dio\U$k"SK$/SM$n\EsN0p[lN*1
lK[d2%Sa2/d0$^Ixp"|dc`;s/\W//g;$_=pack('H*',/((..)*)$/)
Linus Torvalds· Sep 23, 2006, 17:12 UTC · re: Petr Baudis · lore

Re: [RFC][PATCH] for_each_ref() returning heads in wrong order

On Sat, 23 Sep 2006, Petr Baudis wrote:
Show 7 quoted lines
>
> Using the #next branch I've now hit a problem with git-fetch-pack
> master choosing refs/bases/master (I geuss created by StGIT) instead
> of refs/heads/master. The old upload-pack returned the refs in the order
> heads-tags-everything_else but the new one just goes for whatever order
> readdir() returns them in (modulo merging with packed refs). I actually
> can't see the difference that caused this right now, though.
Actually, I think it's exactly the other way around.

The _old_ "for_each_refs()" returned things in a totally random order, depending on the readdir(). On many (but not all) filesystems, that ends up being somewhat decided by the order the entries were created in, so for example, you'd generally get "refs/heads/" and "refs/tags/" early (discounting HEAD, which is always a special case and comes first).

The _new_ thing is totally reliable. It returns things sorted alphabetically according to "strcmp". It doesn't matter what ordering readdir() gives.

Now, we could change the sorting order artificially, but I think your patch is actually incorrect. Because you no longer sort the list appropriately, the merge-sort done by "do_show_each_ref()" is no longer guaranteed to work, I think.

Ugly.

The proper way to fix it (if you want to do this at all) is to just define the sort-order to be something else than a plain "strcmp()", and change the things that compare ordering to just use the new ordering instead.

In other words, start from something like THIS, and just change "ref_name_compare()" to taste. Make sure it's a complete ordering, though.

		Linus
---
Show changes to refs.c +14 −3
diff --git a/refs.c b/refs.c
index 2cef2b4..05b7006 100644
--- a/refs.c
+++ b/refs.c
@@ -37,6 +37,17 @@ static const char *parse_ref_line(char *
 	return line;
 }
 
+/*
+ * This is the ordering function for refnames. It has the
+ * same semantics as "strcmp()", but you can define it to
+ * order "refs/heads/" and "refs/tags/" before other names,
+ * for example.
+ */
+static int ref_name_compare(const char *a, const char *b)
+{
+	return strcmp(a,b);
+}
+
 static struct ref_list *add_ref(const char *name, const unsigned char *sha1,
 				int flag, struct ref_list *list)
 {
@@ -45,7 +56,7 @@ static struct ref_list *add_ref(const ch
 
 	/* Find the place to insert the ref into.. */
 	while ((entry = *p) != NULL) {
-		int cmp = strcmp(entry->name, name);
+		int cmp = ref_name_compare(entry->name, name);
 		if (cmp > 0)
 			break;
 
@@ -179,7 +190,7 @@ const char *resolve_ref(const char *ref,
 		if (lstat(path, &st) < 0) {
 			struct ref_list *list = get_packed_refs();
 			while (list) {
-				if (!strcmp(ref, list->name)) {
+				if (!ref_name_compare(ref, list->name)) {
 					hashcpy(sha1, list->sha1);
 					if (flag)
 						*flag |= REF_ISPACKED;
@@ -297,7 +308,7 @@ static int do_for_each_ref(const char *b
 
 	while (packed && loose) {
 		struct ref_list *entry;
-		int cmp = strcmp(packed->name, loose->name);
+		int cmp = ref_name_compare(packed->name, loose->name);
 		if (!cmp) {
 			packed = packed->next;
 			continue;
Junio C Hamano· Sep 23, 2006, 19:31 UTC · re: Petr Baudis · lore

Re: [RFC][PATCH] for_each_ref() returning heads in wrong order

Petr Baudis <pasky@suse.cz> writes:
Show 6 quoted lines
> Using the #next branch I've now hit a problem with git-fetch-pack
> master choosing refs/bases/master (I geuss created by StGIT) instead
> of refs/heads/master. The old upload-pack returned the refs in the order
> heads-tags-everything_else but the new one just goes for whatever order
> readdir() returns them in (modulo merging with packed refs). I actually
> can't see the difference that caused this right now, though.

I think it is the other way around (the new one sorts, the old one doesn't). fetch-pack lets for_each_ref() to pick, but the wrapper git-fetch I think prepends refs/ and refs/heads as needed, so if you explicitly say heads/master I do not think you have a problem.

However, I see a bit bigger problem here. I think rev-parse would not complain "master" is ambiguous in your repository, because it has a fixed list of prefixes ("", refs, refs/tags, refs/heads, refs/remotes, refs/remotes/%/HEAD) it uses to DWIM in sha1_file.c::get_sha1_basic(), and refs/bases is not part of the prefixes.

I suspect we should fix connect.c::count_refspec_match(), which currently is just a strict tail match, to use the same list of prefix.

← back to recent threads