patchrefs/packed: fix BUG when seeking refs with UTF-8 characters

>
> It was reported that using git-pull(1) in a repository whose remote
> contains branches with emojis leads to the following bug:
>
>     $ git pull
>     remote: Enumerating objects: 161255, done.
>     remote: Counting objects: 100% (55884/55884), done.
>     remote: Compressing objects: 100% (5518/5518), done.
>     remote: Total 161255 (delta 54253), reused 50509 (delta 50364),
>     pack-reused 105371 (from 4)
>     Receiving objects: 100% (161255/161255), 309.90 MiB | 16.87 MiB/s, done.
>     Resolving deltas: 100% (118048/118048), completed with 13416 local objects.
>     From github.com:github/github
>        97ab7ae3f3745..8fb2f9fa180ed  master -> origin/master
>     [...snip many screenfuls of updates to origin remotes...]
>     BUG: refs/packed-backend.c:984: packed-refs backend yielded reference
>     preceding its prefix
>     error: fetch died of signal 6
>
> This issue bisects to 22600c04529 (refs/iterator: implement seeking for
> packed-ref iterators, 2025-03-12) where we have implemented seeking for
> the packed-ref iterator. As part of that change we introduced a check
> that verifies that the iterator only returns refnames bigger than the
> prefix. In theory, this check should always hold: when a prefix is set
> we know that we would've seeked that prefix first, so we should never
> see a reference sorting before that prefix.
>
> But in practice the check itself is misbehaving when handling unicode
> characters. The particular issue triggered with a branch that got the
> "shaved ice" unicode character in its name, which is composed of the
> bytes "0xEE 0x90 0xBF". The bug triggers when we compare the refname
> "refs/heads/<shaved-ice>" to something like "refs/heads/z", and it
> specifically hits when comparing the first byte, "0xEE".
>
> The root cause is that the most-significant bit of 0xEE is set. The
> `refname` and `prefix` pointers that we use to compare bytes with one
> another are both pointers to signed characters. As such, when we
> dereference the 0xEE byte the result is a _negative_ value, and this
> value will of course compare smaller than "z".
>
> We can see that this issue is avoided in `cmp_packed_refname()`, where
> we explicitly cast each byte to its unsigned form. Fix the bug by doing
> the same in `packed_ref_iterator_advance()`.
>
> Reported-by: Elijah Newren <newren@gmail.com>
> Signed-off-by: Patrick Steinhardt <ps@pks.im>
> ---
> Hi,
>
> this patch addresses the issue reported by Elijah at [1]. Thanks!

> Patrick
>
> [1]: <CABPp-BFBqC_t5QSexRQpYsqXBa11WK+OqGt167E=K=xod=buQw@mail.gmail.com>
> ---
>  refs/packed-backend.c  |  4 ++--
>  t/t1408-packed-refs.sh | 15 +++++++++++++++
>  2 files changed, 17 insertions(+), 2 deletions(-)
>
> diff --git a/refs/packed-backend.c b/refs/packed-backend.c
> index b4289a7d9ce..7e31904bd41 100644
> --- a/refs/packed-backend.c
> +++ b/refs/packed-backend.c
> @@ -980,9 +980,9 @@ static int packed_ref_iterator_advance(struct ref_iterator *ref_iterator)
>                         continue;
>
>                 while (prefix && *prefix) {
> -                       if (*refname < *prefix)
> +                       if ((unsigned char)*refname < (unsigned char)*prefix)
>                                 BUG("packed-refs backend yielded reference preceding its prefix");
> -                       else if (*refname > *prefix)
> +                       else if ((unsigned char)*refname > (unsigned char)*prefix)
>                                 return ITER_DONE;
>                         prefix++;
>                         refname++;

> diff --git a/t/t1408-packed-refs.sh b/t/t1408-packed-refs.sh
> index 41ba1f1d7fc..833477f0fa3 100755
> --- a/t/t1408-packed-refs.sh
> +++ b/t/t1408-packed-refs.sh
> @@ -42,4 +42,19 @@ test_expect_success 'no error from stale entry in packed-refs' '
>         test_cmp expect actual
>  '
>
> +test_expect_success 'list packed refs with unicode characters' '
> +       test_when_finished "rm -rf repo" &&
> +       git init repo &&
> +       (
> +               cd repo &&
> +               test_commit --no-tag A &&
> +               git update-ref refs/heads/ HEAD &&
> +               git update-ref refs/heads/z HEAD &&
> +               git pack-refs --all &&
> +               printf "%s commit\trefs/heads/z\n" $(git rev-parse HEAD) >expect &&
> +               git for-each-ref refs/heads/z >actual &&
> +               test_cmp expect actual
> +       )
> +'
> +
>  test_done
>
> ---
> base-commit: 5b97a56fa0e7d580dc8865b73107407c9b3f0eff
> change-id: 20250404-b4-pks-packed-backend-seek-with-utf8-668c182ddcf7

> But in practice the check itself is misbehaving when handling unicode
> characters. The particular issue triggered with a branch that got the
> "shaved ice" unicode character in its name, which is composed of the
> bytes "0xEE 0x90 0xBF". The bug triggers when we compare the refname
> "refs/heads/<shaved-ice>" to something like "refs/heads/z", and it
> specifically hits when comparing the first byte, "0xEE".
> 
> The root cause is that the most-significant bit of 0xEE is set. The
> `refname` and `prefix` pointers that we use to compare bytes with one
> another are both pointers to signed characters. As such, when we
> dereference the 0xEE byte the result is a _negative_ value, and this
> value will of course compare smaller than "z".
> 
> We can see that this issue is avoided in `cmp_packed_refname()`, where
> we explicitly cast each byte to its unsigned form. Fix the bug by doing
> the same in `packed_ref_iterator_advance()`.

> diff --git a/refs/packed-backend.c b/refs/packed-backend.c
> index b4289a7d9ce..7e31904bd41 100644
> --- a/refs/packed-backend.c
> +++ b/refs/packed-backend.c
> @@ -980,9 +980,9 @@ static int packed_ref_iterator_advance(struct ref_iterator *ref_iterator)
>  			continue;
>  
>  		while (prefix && *prefix) {
> -			if (*refname < *prefix)
> +			if ((unsigned char)*refname < (unsigned char)*prefix)
>  				BUG("packed-refs backend yielded reference preceding its prefix");
> -			else if (*refname > *prefix)
> +			else if ((unsigned char)*refname > (unsigned char)*prefix)
>  				return ITER_DONE;
>  			prefix++;
>  			refname++;

> +test_expect_success 'list packed refs with unicode characters' '
> +	test_when_finished "rm -rf repo" &&
> +	git init repo &&
> +	(
> +		cd repo &&
> +		test_commit --no-tag A &&
> +		git update-ref refs/heads/ HEAD &&
> +		git update-ref refs/heads/z HEAD &&

> On Fri, Apr 04, 2025 at 12:58:38PM +0200, Patrick Steinhardt wrote:
> 
> > But in practice the check itself is misbehaving when handling unicode
> > characters. The particular issue triggered with a branch that got the
> > "shaved ice" unicode character in its name, which is composed of the
> > bytes "0xEE 0x90 0xBF". The bug triggers when we compare the refname
> > "refs/heads/<shaved-ice>" to something like "refs/heads/z", and it
> > specifically hits when comparing the first byte, "0xEE".
> > 
> > The root cause is that the most-significant bit of 0xEE is set. The
> > `refname` and `prefix` pointers that we use to compare bytes with one
> > another are both pointers to signed characters. As such, when we
> > dereference the 0xEE byte the result is a _negative_ value, and this
> > value will of course compare smaller than "z".
> > 
> > We can see that this issue is avoided in `cmp_packed_refname()`, where
> > we explicitly cast each byte to its unsigned form. Fix the bug by doing
> > the same in `packed_ref_iterator_advance()`.
> 
> Ah, good catch. I think this signed-ness issue has come up before, long
> ago, but I don't remember the context. In theory any stable ordering is
> OK for sorting, but of course cmp_packed_refname() chose to use unsigned
> in order to match strcmp(), and the standard defines it as interpreting
> the bytes as unsigned. One of the enjoyable quirks of C.

> > diff --git a/refs/packed-backend.c b/refs/packed-backend.c
> > index b4289a7d9ce..7e31904bd41 100644
> > --- a/refs/packed-backend.c
> > +++ b/refs/packed-backend.c
> > @@ -980,9 +980,9 @@ static int packed_ref_iterator_advance(struct ref_iterator *ref_iterator)
> >  			continue;
> >  
> >  		while (prefix && *prefix) {
> > -			if (*refname < *prefix)
> > +			if ((unsigned char)*refname < (unsigned char)*prefix)
> >  				BUG("packed-refs backend yielded reference preceding its prefix");
> > -			else if (*refname > *prefix)
> > +			else if ((unsigned char)*refname > (unsigned char)*prefix)
> >  				return ITER_DONE;
> >  			prefix++;
> >  			refname++;
> 
> The patch itself looks good to me.

> > +test_expect_success 'list packed refs with unicode characters' '
> > +	test_when_finished "rm -rf repo" &&
> > +	git init repo &&
> > +	(
> > +		cd repo &&
> > +		test_commit --no-tag A &&
> > +		git update-ref refs/heads/ HEAD &&
> > +		git update-ref refs/heads/z HEAD &&
> 
> It's possible some filesystems might be unhappy with this character, but
> I guess we can see if anybody screams.

> > Ah, good catch. I think this signed-ness issue has come up before, long
> > ago, but I don't remember the context. In theory any stable ordering is
> > OK for sorting, but of course cmp_packed_refname() chose to use unsigned
> > in order to match strcmp(), and the standard defines it as interpreting
> > the bytes as unsigned. One of the enjoyable quirks of C.
> 
> I'd agree it's a quirk, but I'm not sure I'd call it enjoyable.  Anyway,
> this does seem like the right solution and I agree matching strcmp is
> the right decision here.  I also think unsigned byte comparisons are
> more intuitive, honestly.

> > It's possible some filesystems might be unhappy with this character, but
> > I guess we can see if anybody screams.
> 
> I very much doubt that's going to be a problem.  Windows uses UTF-16
> internally, so it will have no problems with Unicode; macOS only allows
> UTF-8 in its file systems and I know it gracefully supports emoji; and
> other Unix systems don't care one way or the other because it's just
> some bytes.  Even ISO9660 with Rock Ridge or Joliet extensions will work
> here, as will FAT, UDF (used on DVDs and some hard disks), and 9P.
> 
> Certainly somebody could try something very esoteric, but I expect other
> things will break as well.  I'm okay with favouring testing things we
> know many people _are_ using (emojis and Unicode) over things very few
> people are using (very esoteric file systems[0]).