{"thread":{"id":"44529","subject":"[PATCH] merge-recursive.c: use QSORT macro","startedAt":"2016-11-22T12:31:37Z","lastAt":"2016-11-25T17:23:06Z","messageCount":8,"participants":["Nguyễn Thái Ngọc Duy","Jeff King","Duy Nguyen","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"306297","messageId":"20161122123019.7169-1-pclouds@gmail.com","threadId":"44529","inReplyTo":null,"subject":"[PATCH] merge-recursive.c: use QSORT macro","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2016-11-22T12:30:19Z","receivedAt":"2016-11-22T12:31:37Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This is the follow up of rs/qsort series, merged in b8688ad (Merge\nbranch 'rs/qsort' - 2016-10-10), where coccinelle was used to do\nautomatic transformation.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n  coccinelle missed this place, understandably, because it can't know\n  that\n  \n      sizeof(*entries->items)\n  \n  is the same as\n  \n      sizeof(*df_name_compare.items)\n  \n  without some semantic analysis.\n\n merge-recursive.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex 9041c2f..2d4dca9 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -451,7 +451,7 @@ static void record_df_conflict_files(struct merge_options *o,\n \t\tstring_list_append(&df_sorted_entries, next->string)->util =\n \t\t\t\t   next->util;\n \t}\n-\tqsort(df_sorted_entries.items, entries->nr, sizeof(*entries->items),\n+\tQSORT(df_sorted_entries.items, entries->nr,\n \t      string_list_df_name_compare);\n \n \tstring_list_clear(&o->df_conflict_file_set, 1);\n-- \n2.8.2.524.g6ff3d78\n\n"},{"id":"306319","messageId":"20161122174946.jy5at4g7rifu3und@sigill.intra.peff.net","threadId":"44529","inReplyTo":"20161122123019.7169-1-pclouds@gmail.com","subject":"Re: [PATCH] merge-recursive.c: use QSORT macro","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-11-22T17:49:46Z","receivedAt":"2016-11-22T17:49:54Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Nov 22, 2016 at 07:30:19PM +0700, Nguyễn Thái Ngọc Duy wrote:\n\n> This is the follow up of rs/qsort series, merged in b8688ad (Merge\n> branch 'rs/qsort' - 2016-10-10), where coccinelle was used to do\n> automatic transformation.\n> \n> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n> ---\n>   coccinelle missed this place, understandably, because it can't know\n>   that\n>   \n>       sizeof(*entries->items)\n>   \n>   is the same as\n>   \n>       sizeof(*df_name_compare.items)\n>   \n>   without some semantic analysis.\n\nThat made me wonder why \"entries\" is used at all. Does it point to the\nsame struct? But no, df_name_compare is a string list we create with the\nsame list of strings.\n\nWhich is why...\n\n> -\tqsort(df_sorted_entries.items, entries->nr, sizeof(*entries->items),\n> +\tQSORT(df_sorted_entries.items, entries->nr,\n>  \t      string_list_df_name_compare);\n\n...it's OK to use entries->nr here, and not df_sorted_entries.nr. It\nstill seems a bit odd, though. Maybe it's worth making this:\n\n  QSORT(df_sorted_entries.items, df_sorted_entries.nr,\n        string_list_df_name_compare);\n\nwhile we're at it. Another possibility is:\n\n  df_sorted_entries.cmp = string_list_df_name_compare;\n  string_list_sort(&df_sorted_entries);\n\nIt's not any shorter, but maybe it's conceptually simpler.\n\n-Peff\n"},{"id":"306372","messageId":"CACsJy8BFRroifr0OL0O5OZjkPkndeZzVYCkg9vCNk+7Ee4zouA@mail.gmail.com","threadId":"44529","inReplyTo":"20161122174946.jy5at4g7rifu3und@sigill.intra.peff.net","subject":"Re: [PATCH] merge-recursive.c: use QSORT macro","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2016-11-23T09:43:08Z","receivedAt":"2016-11-23T09:44:22Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Nov 23, 2016 at 12:49 AM, Jeff King <peff@peff.net> wrote:\n> On Tue, Nov 22, 2016 at 07:30:19PM +0700, Nguyễn Thái Ngọc Duy wrote:\n>\n>> This is the follow up of rs/qsort series, merged in b8688ad (Merge\n>> branch 'rs/qsort' - 2016-10-10), where coccinelle was used to do\n>> automatic transformation.\n>>\n>> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n>> ---\n>>   coccinelle missed this place, understandably, because it can't know\n>>   that\n>>\n>>       sizeof(*entries->items)\n>>\n>>   is the same as\n>>\n>>       sizeof(*df_name_compare.items)\n>>\n>>   without some semantic analysis.\n>\n> That made me wonder why \"entries\" is used at all. Does it point to the\n> same struct? But no, df_name_compare is a string list we create with the\n> same list of strings.\n>\n> Which is why...\n>\n>> -     qsort(df_sorted_entries.items, entries->nr, sizeof(*entries->items),\n>> +     QSORT(df_sorted_entries.items, entries->nr,\n>>             string_list_df_name_compare);\n>\n> ...it's OK to use entries->nr here, and not df_sorted_entries.nr. It\n> still seems a bit odd, though.\n\nArgh.. I completely overlooked that entries->nr !\n\n> Maybe it's worth making this:\n>\n>   QSORT(df_sorted_entries.items, df_sorted_entries.nr,\n>         string_list_df_name_compare);\n>\n> while we're at it. Another possibility is:\n>\n>   df_sorted_entries.cmp = string_list_df_name_compare;\n>   string_list_sort(&df_sorted_entries);\n>\n> It's not any shorter, but maybe it's conceptually simpler.\n\nAgreed. Shall I re-roll with this?\n-- \nDuy\n"},{"id":"306384","messageId":"xmqqpolmm7sa.fsf@gitster.mtv.corp.google.com","threadId":"44529","inReplyTo":"20161122174946.jy5at4g7rifu3und@sigill.intra.peff.net","subject":"Re: [PATCH] merge-recursive.c: use QSORT macro","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-11-23T17:21:25Z","receivedAt":"2016-11-23T17:21:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> Another possibility is:\n>\n>   df_sorted_entries.cmp = string_list_df_name_compare;\n>   string_list_sort(&df_sorted_entries);\n>\n> It's not any shorter, but maybe it's conceptually simpler.\n\nMy first reaction to Duy's patch was: it is moronic for the\nstring-list API not to offer \"I've done _append() to add many items\nwhile avoiding the overhead of doing insertion sort all the time;\nnow I finished adding and I want the result sorted\".\n\nAnd then I looked at string-list.h and there it was ;-)\n\n"},{"id":"306404","messageId":"20161124114536.22249-1-pclouds@gmail.com","threadId":"44529","inReplyTo":"20161122123019.7169-1-pclouds@gmail.com","subject":"[PATCH v2] merge-recursive.c: use string_list_sort instead of qsort","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2016-11-24T11:45:36Z","receivedAt":"2016-11-24T11:45:53Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This started out to as a hunt for remaining qsort() calls after rs/qsort\nseries because qsort() API is a bit easy to get wrong (*). However,\nsince we have string_list_sort(), it's conceptually a better way to sort\nhere.\n\n(*) In this particular case, it's even more confusing when you sort one\nvariable but you use the number of items and item size from an unrelated\nvariable (from a first glance)\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n merge-recursive.c | 16 +++++++---------\n 1 file changed, 7 insertions(+), 9 deletions(-)\n\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex 9041c2f..90e83bd 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -388,12 +388,10 @@ static struct string_list *get_unmerged(void)\n \treturn unmerged;\n }\n \n-static int string_list_df_name_compare(const void *a, const void *b)\n+static int string_list_df_name_compare(const char *one, const char *two)\n {\n-\tconst struct string_list_item *one = a;\n-\tconst struct string_list_item *two = b;\n-\tint onelen = strlen(one->string);\n-\tint twolen = strlen(two->string);\n+\tint onelen = strlen(one);\n+\tint twolen = strlen(two);\n \t/*\n \t * Here we only care that entries for D/F conflicts are\n \t * adjacent, in particular with the file of the D/F conflict\n@@ -406,8 +404,8 @@ static int string_list_df_name_compare(const void *a, const void *b)\n \t * since in other cases any changes in their order due to\n \t * sorting cause no problems for us.\n \t */\n-\tint cmp = df_name_compare(one->string, onelen, S_IFDIR,\n-\t\t\t\t  two->string, twolen, S_IFDIR);\n+\tint cmp = df_name_compare(one, onelen, S_IFDIR,\n+\t\t\t\t  two, twolen, S_IFDIR);\n \t/*\n \t * Now that 'foo' and 'foo/bar' compare equal, we have to make sure\n \t * that 'foo' comes before 'foo/bar'.\n@@ -451,8 +449,8 @@ static void record_df_conflict_files(struct merge_options *o,\n \t\tstring_list_append(&df_sorted_entries, next->string)->util =\n \t\t\t\t   next->util;\n \t}\n-\tqsort(df_sorted_entries.items, entries->nr, sizeof(*entries->items),\n-\t      string_list_df_name_compare);\n+\tdf_sorted_entries.cmp = string_list_df_name_compare;\n+\tstring_list_sort(&df_sorted_entries);\n \n \tstring_list_clear(&o->df_conflict_file_set, 1);\n \tfor (i = 0; i < df_sorted_entries.nr; i++) {\n-- \n2.8.2.524.g6ff3d78\n\n"},{"id":"306412","messageId":"20161124205242.ts4qhvfz2hvxez36@sigill.intra.peff.net","threadId":"44529","inReplyTo":"20161124114536.22249-1-pclouds@gmail.com","subject":"Re: [PATCH v2] merge-recursive.c: use string_list_sort instead of qsort","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-11-24T20:52:42Z","receivedAt":"2016-11-24T20:52:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Nov 24, 2016 at 06:45:36PM +0700, Nguyễn Thái Ngọc Duy wrote:\n\n> This started out to as a hunt for remaining qsort() calls after rs/qsort\n> series because qsort() API is a bit easy to get wrong (*). However,\n> since we have string_list_sort(), it's conceptually a better way to sort\n> here.\n> \n> (*) In this particular case, it's even more confusing when you sort one\n> variable but you use the number of items and item size from an unrelated\n> variable (from a first glance)\n\nMakes sense, though I think I probably would have explained it in\nreverse order:\n\n  Merge-recursive sorts a string list using a raw qsort(), where it\n  feeds the \"items\" from one struct but the \"nr\" and size fields from\n  another struct. This isn't a bug because one list is a copy of the\n  other, but it's unnecessarily confusing (and also caused our recent\n  QSORT() cleanups via coccinelle to miss this call site).\n\n  Let's use string_list_sort() instead, which is more concise and harder\n  to get wrong. Note that we need to adjust our comparison function,\n  which gets fed only the strings now, not the string_list_items. That's\n  OK because we don't use the \"util\" field as part of our sort.\n\nFeel free to use or ignore my description as you see fit. :)\n\n> -static int string_list_df_name_compare(const void *a, const void *b)\n> +static int string_list_df_name_compare(const char *one, const char *two)\n>  {\n> -\tconst struct string_list_item *one = a;\n> -\tconst struct string_list_item *two = b;\n> -\tint onelen = strlen(one->string);\n> -\tint twolen = strlen(two->string);\n> +\tint onelen = strlen(one);\n> +\tint twolen = strlen(two);\n\nI guess I haven't used string_list_sort() in a while, but I was\nsurprised to find that it just feeds the strings to the comparator. That\nmakes sense for using a raw strcmp() as the comparator, but I wonder if\nany callers would ever want to take the util field into account (e.g.,\nto break ties).\n\nWe don't seem to care here, though (which can be verified by reading the\ncode, but also because any mention of one->util would be a compilation\nerror after your patch). So I guess we can punt on it until the day that\nsome caller does need it.\n\n-Peff\n"},{"id":"306423","messageId":"CACsJy8Atv9rkwmCcXgOqDb6pLP8RxQ7XnxMYt3=hN6KG4X79iA@mail.gmail.com","threadId":"44529","inReplyTo":"20161124205242.ts4qhvfz2hvxez36@sigill.intra.peff.net","subject":"Re: [PATCH v2] merge-recursive.c: use string_list_sort instead of qsort","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2016-11-25T12:15:15Z","receivedAt":"2016-11-25T12:15:52Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Nov 25, 2016 at 3:52 AM, Jeff King <peff@peff.net> wrote:\n> On Thu, Nov 24, 2016 at 06:45:36PM +0700, Nguyễn Thái Ngọc Duy wrote:\n>\n>> This started out to as a hunt for remaining qsort() calls after rs/qsort\n>> series because qsort() API is a bit easy to get wrong (*). However,\n>> since we have string_list_sort(), it's conceptually a better way to sort\n>> here.\n>>\n>> (*) In this particular case, it's even more confusing when you sort one\n>> variable but you use the number of items and item size from an unrelated\n>> variable (from a first glance)\n>\n> Makes sense, though I think I probably would have explained it in\n> reverse order:\n>\n>   Merge-recursive sorts a string list using a raw qsort(), where it\n>   feeds the \"items\" from one struct but the \"nr\" and size fields from\n>   another struct. This isn't a bug because one list is a copy of the\n>   other, but it's unnecessarily confusing (and also caused our recent\n>   QSORT() cleanups via coccinelle to miss this call site).\n>\n>   Let's use string_list_sort() instead, which is more concise and harder\n>   to get wrong. Note that we need to adjust our comparison function,\n>   which gets fed only the strings now, not the string_list_items. That's\n>   OK because we don't use the \"util\" field as part of our sort.\n>\n> Feel free to use or ignore my description as you see fit. :)\n\nI delegate the decision to Junio. He can amend the commit if he\ndecides so. I suspect it's a good idea to do so.\n\n>> -static int string_list_df_name_compare(const void *a, const void *b)\n>> +static int string_list_df_name_compare(const char *one, const char *two)\n>>  {\n>> -     const struct string_list_item *one = a;\n>> -     const struct string_list_item *two = b;\n>> -     int onelen = strlen(one->string);\n>> -     int twolen = strlen(two->string);\n>> +     int onelen = strlen(one);\n>> +     int twolen = strlen(two);\n>\n> I guess I haven't used string_list_sort() in a while, but I was\n> surprised to find that it just feeds the strings to the comparator. That\n> makes sense for using a raw strcmp() as the comparator, but I wonder if\n> any callers would ever want to take the util field into account (e.g.,\n> to break ties).\n>\n> We don't seem to care here, though (which can be verified by reading the\n> code, but also because any mention of one->util would be a compilation\n> error after your patch). So I guess we can punt on it until the day that\n> some caller does need it.\n\nSome callers do need it, or at least fmt-merge-msg.c:add_people_info()\ndoes, maybe builtin/remote.c:show() and shortlog.c:shortlog_output()\ntoo. But I'll stop here and get back to my worktree stuff.\n-- \nDuy\n"},{"id":"306433","messageId":"20161125171546.fa3zpapbjngjcl26@sigill.intra.peff.net","threadId":"44529","inReplyTo":"CACsJy8Atv9rkwmCcXgOqDb6pLP8RxQ7XnxMYt3=hN6KG4X79iA@mail.gmail.com","subject":"Re: [PATCH v2] merge-recursive.c: use string_list_sort instead of qsort","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-11-25T17:15:47Z","receivedAt":"2016-11-25T17:23:06Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Nov 25, 2016 at 07:15:15PM +0700, Duy Nguyen wrote:\n\n> > I guess I haven't used string_list_sort() in a while, but I was\n> > surprised to find that it just feeds the strings to the comparator. That\n> > makes sense for using a raw strcmp() as the comparator, but I wonder if\n> > any callers would ever want to take the util field into account (e.g.,\n> > to break ties).\n> >\n> > We don't seem to care here, though (which can be verified by reading the\n> > code, but also because any mention of one->util would be a compilation\n> > error after your patch). So I guess we can punt on it until the day that\n> > some caller does need it.\n> \n> Some callers do need it, or at least fmt-merge-msg.c:add_people_info()\n> does, maybe builtin/remote.c:show() and shortlog.c:shortlog_output()\n> too. But I'll stop here and get back to my worktree stuff.\n\nI started to work on this, figuring it would be a nice warm-up for the\nday. But it actually is a little complicated, and I think not worth\ndoing. :)\n\nThe obvious backwards-compatible way to do it is to add a \"cmp_item\"\nfield to the string list. Sorting should use that if non-NULL, and\nfallback to the string-oriented \"cmp\" otherwise.\n\nAnd that does work when you want to sort via string_list_sort, like:\n\n  authors->cmp_item = cmp_string_list_util_as_integral;\n  string_list_sort(authors);\n\n(the example is from fmt-merge-message.c). But the original use of\nsorting in string-list was to keep a sorted list as you go with\nstring_list_insert(). And in that call we have _only_ the newly added\nstring, and the caller has not yet had an opportunity to set the util\nfield. So:\n\n  struct string_list list = STRING_LIST_INIT_DUP;\n  list.cmp_item = cmp_util_fields;\n  for (...)\n\tstring_list_insert(&list, foo[i])->util = bar[i];\n\nis nonsense. It would always see a NULL util field during the\ncomparison.\n\nCertainly \"don't do that\" is a possible answer. But it's just a bad\ninterface. It encourages a nonsensical use, and it makes a natural use\n(sorting after the fact) more clunky by making the caller set a field in\nthe struct rather than pass a parameter. The correct interface is more\nlike:\n\n  string_list_sort_items(authors, cmp_string_list_util_as_integral);\n\nbut then we are not really saving much over the more generic:\n\n  QSORT(authors->items, authors->nr, cmp_string_list_util_as_integral);\n\nSo I'm inclined to leave it as-is.\n\n-Peff\n"}]}