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

[shejialuo <shejialuo@gmail.com>]

On Wed, Feb 12, 2025 at 10:56:56AM +0100, Patrick Steinhardt wrote:
> 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.
> 

Yes, capabilities will be more semantic. But the original code in
"packed-backend.c" uses "traits". Let us follow the original style to
make sure consistency.

> [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.
> 

Thanks, I will improve this in the next version.

> Patrick