Re: [PATCH v2] merge-recursive.c: use string_list_sort instead of qsort

From: Jeff King <peff@peff.net>
Date: Nov 25, 2016, 17:15 UTC
Message-ID: <20161125171546.fa3zpapbjngjcl26@sigill.intra.peff.net>
In-Reply-To: <CACsJy8Atv9rkwmCcXgOqDb6pLP8RxQ7XnxMYt3=hN6KG4X79iA@mail.gmail.com>

On Fri, Nov 25, 2016 at 07:15:15PM +0700, Duy Nguyen wrote:

Show 14 quoted lines

> > I guess I haven't used string_list_sort() in a while, but I was
> > surprised to find that it just feeds the strings to the comparator. That
> > makes sense for using a raw strcmp() as the comparator, but I wonder if
> > any callers would ever want to take the util field into account (e.g.,
> > to break ties).
> >
> > We don't seem to care here, though (which can be verified by reading the
> > code, but also because any mention of one->util would be a compilation
> > error after your patch). So I guess we can punt on it until the day that
> > some caller does need it.
> 
> Some callers do need it, or at least fmt-merge-msg.c:add_people_info()
> does, maybe builtin/remote.c:show() and shortlog.c:shortlog_output()
> too. But I'll stop here and get back to my worktree stuff.

I started to work on this, figuring it would be a nice warm-up for the day. But it actually is a little complicated, and I think not worth doing. :)

The obvious backwards-compatible way to do it is to add a "cmp_item" field to the string list. Sorting should use that if non-NULL, and fallback to the string-oriented "cmp" otherwise.

And that does work when you want to sort via string_list_sort, like:

  authors->cmp_item = cmp_string_list_util_as_integral;
  string_list_sort(authors);

(the example is from fmt-merge-message.c). But the original use of sorting in string-list was to keep a sorted list as you go with string_list_insert(). And in that call we have _only_ the newly added string, and the caller has not yet had an opportunity to set the util field. So:

  struct string_list list = STRING_LIST_INIT_DUP;
  list.cmp_item = cmp_util_fields;
  for (...)
	string_list_insert(&list, foo[i])->util = bar[i];

is nonsense. It would always see a NULL util field during the comparison.

Certainly "don't do that" is a possible answer. But it's just a bad interface. It encourages a nonsensical use, and it makes a natural use (sorting after the fact) more clunky by making the caller set a field in the struct rather than pass a parameter. The correct interface is more like:

  string_list_sort_items(authors, cmp_string_list_util_as_integral);

but then we are not really saving much over the more generic:

  QSORT(authors->items, authors->nr, cmp_string_list_util_as_integral);

So I'm inclined to leave it as-is.

-Peff