Re: [PATCH v3 7/8] packed-backend: check whether the "packed-refs" is sorted

[Patrick Steinhardt <ps@pks.im>]

On Thu, Feb 06, 2025 at 01:59:55PM +0800, shejialuo wrote:
> diff --git a/refs/packed-backend.c b/refs/packed-backend.c
> index 658f6bc7da..0fbdc5c3fa 100644
> --- a/refs/packed-backend.c
> +++ b/refs/packed-backend.c
> @@ -1767,6 +1773,28 @@ static struct ref_iterator *packed_reflog_iterator_begin(struct ref_store *ref_s
>  	return empty_ref_iterator_begin();
>  }
>  
> +struct fsck_packed_ref_entry {
> +	unsigned long line_number;
> +
> +	struct snapshot_record record;
> +};
> +
> +static struct fsck_packed_ref_entry *create_fsck_packed_ref_entry(unsigned long line_number,
> +								  const char *start)
> +{
> +	struct fsck_packed_ref_entry *entry = xcalloc(1, sizeof(*entry));
> +	entry->line_number = line_number;
> +	entry->record.start = start;
> +	return entry;
> +}
> +
> +static void free_fsck_packed_ref_entries(struct fsck_packed_ref_entry **entries, size_t nr)
> +{
> +	for (size_t i = 0; i < nr; i++)
> +		free(entries[i]);
> +	free(entries);
> +}
> +
>  static int packed_fsck_ref_next_line(struct fsck_options *o,
>  				     struct strbuf *packed_entry, const char *start,
>  				     const char *eof, const char **eol)
> @@ -1794,19 +1822,33 @@ static int packed_fsck_ref_next_line(struct fsck_options *o,
>  }
>  
>  static int packed_fsck_ref_header(struct fsck_options *o,
> -				  const char *start, const char *eol)
> +				  const char *start, const char *eol,
> +				  unsigned int *sorted)
>  {
> -	if (!starts_with(start, "# pack-refs with:")) {
> +	struct string_list traits = STRING_LIST_INIT_NODUP;
> +	char *tmp_line;
> +	int ret = 0;
> +	char *p;
> +
> +	tmp_line = xmemdupz(start, eol - start);
> +	if (!skip_prefix(tmp_line, "# pack-refs with:", (const char **)&p)) {
>  		struct fsck_ref_report report = { 0 };
>  		report.path = "packed-refs.header";
>  
> -		return fsck_report_ref(o, &report,
> -				       FSCK_MSG_BAD_PACKED_REF_HEADER,
> -				       "'%.*s' does not start with '# pack-refs with:'",
> -				       (int)(eol - start), start);
> +		ret = fsck_report_ref(o, &report,
> +				      FSCK_MSG_BAD_PACKED_REF_HEADER,
> +				      "'%.*s' does not start with '# pack-refs with:'",
> +				      (int)(eol - start), start);
> +		goto cleanup;
>  	}
>  
> -	return 0;
> +	string_list_split_in_place(&traits, p, " ", -1);
> +	*sorted = unsorted_string_list_has_string(&traits, "sorted");

I think we call them capabilities, not traits.

[snip]
>  static int packed_fsck_ref_content(struct fsck_options *o,
>  				   struct ref_store *ref_store,
>  				   const char *start, const char *eof)
>  {
>  	struct strbuf packed_entry = STRBUF_INIT;
> +	struct fsck_packed_ref_entry **entries;
>  	struct strbuf refname = STRBUF_INIT;
>  	unsigned long line_number = 1;
> +	unsigned int sorted = 0;
> +	size_t entry_alloc = 20;
> +	size_t entry_nr = 0;
>  	const char *eol;
>  	int ret = 0;
>  
>  	strbuf_addf(&packed_entry, "packed-refs line %lu", line_number);
>  	ret |= packed_fsck_ref_next_line(o, &packed_entry, start, eof, &eol);
>  	if (*start == '#') {
> -		ret |= packed_fsck_ref_header(o, start, eol);
> +		ret |= packed_fsck_ref_header(o, start, eol, &sorted);
>  
>  		start = eol + 1;
>  		line_number++;
>  	}
>  
> +	ALLOC_ARRAY(entries, entry_alloc);
>  	while (start < eof) {
> +		struct fsck_packed_ref_entry *entry
> +			= create_fsck_packed_ref_entry(line_number, start);

Instead of slurping in all entries and allocating them in an array, can
we instead remember the last one and just compare that the last record
is smaller than the current record?

> @@ -1915,11 +2011,16 @@ static int packed_fsck_ref_content(struct fsck_options *o,
>  			start = eol + 1;
>  			line_number++;
>  		}
> +		entry->record.len = start - entry->record.start;
>  	}
>  
> +	if (!ret && sorted)
> +		ret |= packed_fsck_ref_sorted(o, ref_store, entries, entry_nr);

Okay, we now conditionally check whether the refs are sorted based on
whether or not we found the "sorted" capability.

> diff --git a/t/t0602-reffiles-fsck.sh b/t/t0602-reffiles-fsck.sh
> index 3ab6b5bba5..adcb5c1bda 100755
> --- a/t/t0602-reffiles-fsck.sh
> +++ b/t/t0602-reffiles-fsck.sh
> @@ -706,4 +706,67 @@ test_expect_success 'packed-refs content should be checked' '
>  	)
>  '
>  
> +test_expect_success 'packed-ref with sorted trait should be checked' '
> +	test_when_finished "rm -rf repo" &&
> +	git init repo &&
> +	(
> +		cd repo &&
> +		test_commit default &&
> +		git branch branch-1 &&
> +		git branch branch-2 &&
> +		git tag -a annotated-tag-1 -m tag-1 &&
> +		branch_1_oid=$(git rev-parse branch-1) &&
> +		branch_2_oid=$(git rev-parse branch-2) &&
> +		tag_1_oid=$(git rev-parse annotated-tag-1) &&
> +		tag_1_peeled_oid=$(git rev-parse annotated-tag-1^{}) &&
> +		refname1="refs/heads/main" &&
> +		refname2="refs/heads/foo" &&
> +		refname3="refs/tags/foo" &&
> +		printf "# pack-refs with: peeled fully-peeled sorted \n"  >.git/packed-refs &&
> +		printf "%s %s\n" "$branch_2_oid" "$refname1" >>.git/packed-refs &&
> +		printf "%s %s\n" "$branch_1_oid" "$refname2" >>.git/packed-refs &&

Same comment here as in the previous patch, this can be simplified with
HERE docs.

> +		test_must_fail git refs verify 2>err &&
> +		cat >expect <<-EOF &&
> +		error: packed-refs line 2: packedRefUnsorted: refname '\''$refname1'\'' is not less than next refname '\''$refname2'\''
> +		EOF
> +		rm .git/packed-refs &&
> +		test_cmp expect err &&
> +
> +		printf "# pack-refs with: peeled fully-peeled sorted \n"  >.git/packed-refs &&
> +		printf "%s %s\n" "$tag_1_oid" "$refname3" >>.git/packed-refs &&
> +		printf "^%s\n" "$tag_1_peeled_oid" >>.git/packed-refs &&
> +		printf "%s %s\n" "$branch_2_oid" "$refname2" >>.git/packed-refs &&
> +		test_must_fail git refs verify 2>err &&
> +		cat >expect <<-EOF &&
> +		error: packed-refs line 2: packedRefUnsorted: refname '\''$refname3'\'' is not less than next refname '\''$refname2'\''
> +		EOF
> +		rm .git/packed-refs &&
> +		test_cmp expect err
> +	)
> +'
> +
> +test_expect_success 'packed-ref without sorted trait should not be checked' '
> +	test_when_finished "rm -rf repo" &&
> +	git init repo &&
> +	(
> +		cd repo &&
> +		test_commit default &&
> +		git branch branch-1 &&
> +		git branch branch-2 &&
> +		git tag -a annotated-tag-1 -m tag-1 &&
> +		branch_1_oid=$(git rev-parse branch-1) &&
> +		branch_2_oid=$(git rev-parse branch-2) &&
> +		tag_1_oid=$(git rev-parse annotated-tag-1) &&
> +		tag_1_peeled_oid=$(git rev-parse annotated-tag-1^{}) &&
> +		refname1="refs/heads/main" &&
> +		refname2="refs/heads/foo" &&
> +		refname3="refs/tags/foo" &&
> +		printf "# pack-refs with: peeled fully-peeled \n"  >.git/packed-refs &&
> +		printf "%s %s\n" "$branch_2_oid" "$refname1" >>.git/packed-refs &&
> +		printf "%s %s\n" "$branch_1_oid" "$refname2" >>.git/packed-refs &&

And here.

Patrick