Re: [PATCH] string_list API: document what "sorted" means.

[Michael Haggerty <mhagger@alum.mit.edu>]

On 09/17/2012 11:17 PM, Junio C Hamano wrote:
> Michael Haggerty <mhagger@alum.mit.edu> writes:
> 
>> Junio pointed out that the sort order currently used by string_list
>> could be considered to be an implementation detail internal to
>> string_list.  But the sort order is already visible to the outside
>> world (e.g., via iteration or via print_string_list()), so it
>> shouldn't be changed willy-nilly.  Therefore, document the current
>> sort order as part of the API's contract.
>>
>> (If, at some future time, somebody wants a string_list that is sorted
>> by a different criterion, then the order should be made specifiable
>> via a callback function specified by the user.)
> 
> As I said in a separate message, we do not give any documented
> guarantee on the order the strings comes out of print_string_list(),
> other than "if you are using the unsorted list function to insert or
> append strings, we won't muck with the order of the items and you
> will get your strings back in the order you gave us".  Until we add
> a callback that the user can specify at the time of string list
> initialization, I do not think it is wise to cast it in stone and
> declare it as "shouldn't be changed willy-nilly", unnecessarily
> painting us into a corner that we need to expend extra effort to get
> out of.
> 
> Besides, nobody calls print_string_list() in the first place. I have
> always considered it as a debugging aid.

As you pointed out, mh/fetch-filter-refs depends on the sort order of
the "sought" reference array matching the sort order of the linked list
of refs received from the remote.

The linked list has been sorted since 9e8e704f using mergesort based on
strcmp().

Prior to 8bee93dd2, the sought array was sorted using qsort() and an
explicit strcmp()-based comparison function.  8bee93dd2 switched to
sorting the "sought" array using sort_string_list(), which is also based
on strcmp().

If (after mh/fetch-filter-refs) somebody would decide to change the sort
order of string_list, then it would break fetch.  So I see three
possibilities:

1. Document that string_list sorts entries according to their strcmp()
order, as proposed in this patch.  Then fetch can rely on this ordering.
 If somebody wants a different ordering in the future, it is easy to
make the sort order a parameter.

2. Leave string_list's "default" sort order unspecified, but already
implement a way to let string_list users specify a particular sort
order.  Change the fetch machinery to specify a strcmp()-based ordering
explicitly.  This approach has the advantage of letting the default sort
order of string_list to be changed, though I don't really see how this
would be helpful.

3. Change fetch back to doing its own sorting again, rather than relying
on sort_string_list().  This isn't a lot of work (inline the one line of
sort_string_list(), then either make string-list.c:cmp_items() public or
duplicate that function too).

I prefer (1) because it is nearly as flexible as (2) and doesn't require
us to do work now that might not be needed (namely, parameterizing the
compare function), nor does it require the overhead of keeping a pointer
to the compare function in the string_list header that might be needed
if string_lists with non-default sort orders should be usable with the
"functions for sorted lists only".

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/