{"thread":{"id":"44187","subject":"[PATCH 1/3] add QSORT","startedAt":"2016-09-29T15:24:15Z","lastAt":"2016-10-05T16:16:30Z","messageCount":13,"participants":["René Scharfe","Junio C Hamano","Kevin Bracey"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"302890","messageId":"67bddc37-4ee2-fef0-c852-e32645421e4c@web.de","threadId":"44187","inReplyTo":null,"subject":"[PATCH 1/3] add QSORT","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-09-29T15:23:43Z","receivedAt":"2016-09-29T15:24:15Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Add the macro QSORT, a convenient wrapper for qsort(3) that infers the\nsize of the array elements and supports the convention of initializing\nempty arrays with a NULL pointer, which we use in some places.\n\nCalling qsort(3) directly with a NULL pointer is undefined -- even with\nan element count of zero -- and allows the compiler to optimize away any\nfollowing NULL checks.  Using the macro avoids such surprises.\n\nAdd a semantic patch as well to demonstrate the macro's usage and to\nautomate the transformation of trivial cases.\n\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\n contrib/coccinelle/qsort.cocci | 19 +++++++++++++++++++\n git-compat-util.h              |  8 ++++++++\n 2 files changed, 27 insertions(+)\n create mode 100644 contrib/coccinelle/qsort.cocci\n\ndiff --git a/contrib/coccinelle/qsort.cocci b/contrib/coccinelle/qsort.cocci\nnew file mode 100644\nindex 0000000..a094e7c\n--- /dev/null\n+++ b/contrib/coccinelle/qsort.cocci\n@@ -0,0 +1,19 @@\n+@@\n+expression base, nmemb, compar;\n+@@\n+- qsort(base, nmemb, sizeof(*base), compar);\n++ QSORT(base, nmemb, compar);\n+\n+@@\n+expression base, nmemb, compar;\n+@@\n+- qsort(base, nmemb, sizeof(base[0]), compar);\n++ QSORT(base, nmemb, compar);\n+\n+@@\n+type T;\n+T *base;\n+expression nmemb, compar;\n+@@\n+- qsort(base, nmemb, sizeof(T), compar);\n++ QSORT(base, nmemb, compar);\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex 8aab0c3..d7ed137 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -977,6 +977,14 @@ void git_qsort(void *base, size_t nmemb, size_t size,\n #define qsort git_qsort\n #endif\n \n+#define QSORT(base, n, compar) sane_qsort((base), (n), sizeof(*(base)), compar)\n+static void inline sane_qsort(void *base, size_t nmemb, size_t size,\n+\t\t\t      int(*compar)(const void *, const void *))\n+{\n+\tif (nmemb > 1)\n+\t\tqsort(base, nmemb, size, compar);\n+}\n+\n #ifndef REG_STARTEND\n #error \"Git requires REG_STARTEND support. Compile with NO_REGEX=NeedsStartEnd\"\n #endif\n-- \n2.10.0\n\n"},{"id":"302891","messageId":"141968a6-bcf9-8792-0313-47a1e10c60f9@web.de","threadId":"44187","inReplyTo":"67bddc37-4ee2-fef0-c852-e32645421e4c@web.de","subject":"[PATCH 2/3] use QSORT","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-09-29T15:27:31Z","receivedAt":"2016-09-29T15:27:53Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Apply the semantic patch contrib/coccinelle/qsort.cocci to the code\nbase, replacing calls of qsort(3) with QSORT.  The resulting code is\nshorter and supports empty arrays with NULL pointers.\n\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\nFreshly generated using coccicheck, compiles, survives make test.\n\n bisect.c                             |  2 +-\n builtin/describe.c                   |  2 +-\n builtin/fast-export.c                |  2 +-\n builtin/fmt-merge-msg.c              |  6 ++----\n builtin/index-pack.c                 |  8 +++-----\n builtin/mktree.c                     |  2 +-\n builtin/name-rev.c                   |  3 +--\n builtin/pack-objects.c               |  7 +++----\n builtin/remote.c                     |  3 +--\n diff.c                               |  6 +++---\n diffcore-delta.c                     |  5 +----\n diffcore-order.c                     |  2 +-\n diffcore-rename.c                    |  2 +-\n dir.c                                |  4 ++--\n fast-import.c                        |  4 ++--\n fetch-pack.c                         |  2 +-\n help.c                               | 15 +++++----------\n line-log.c                           |  2 +-\n pack-bitmap-write.c                  |  3 +--\n pack-check.c                         |  2 +-\n pack-write.c                         |  3 +--\n pathspec.c                           |  3 +--\n ref-filter.c                         |  2 +-\n refs/files-backend.c                 |  2 +-\n server-info.c                        |  2 +-\n sh-i18n--envsubst.c                  |  2 +-\n sha1-array.c                         |  2 +-\n string-list.c                        |  2 +-\n t/helper/test-dump-untracked-cache.c |  6 ++----\n tree.c                               |  3 +--\n 30 files changed, 44 insertions(+), 65 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 6f512c2..21bc6da 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -215,7 +215,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n\n \t\tarray[cnt].distance = distance;\n \t\tcnt++;\n \t}\n-\tqsort(array, cnt, sizeof(*array), compare_commit_dist);\n+\tQSORT(array, cnt, compare_commit_dist);\n \tfor (p = list, i = 0; i < cnt; i++) {\n \t\tchar buf[100]; /* enough for dist=%d */\n \t\tstruct object *obj = &(array[i].commit->object);\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 8a25abe..01490a1 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -352,7 +352,7 @@ static void describe(const char *arg, int last_one)\n \t\t\t    oid_to_hex(oid));\n \t}\n \n-\tqsort(all_matches, match_cnt, sizeof(all_matches[0]), compare_pt);\n+\tQSORT(all_matches, match_cnt, compare_pt);\n \n \tif (gave_up_on) {\n \t\tcommit_list_insert_by_date(gave_up_on, &list);\ndiff --git a/builtin/fast-export.c b/builtin/fast-export.c\nindex c0652a7..1e815b5 100644\n--- a/builtin/fast-export.c\n+++ b/builtin/fast-export.c\n@@ -347,7 +347,7 @@ static void show_filemodify(struct diff_queue_struct *q,\n \t * Handle files below a directory first, in case they are all deleted\n \t * and the directory changes to a file or symlink.\n \t */\n-\tqsort(q->queue, q->nr, sizeof(q->queue[0]), depth_first);\n+\tQSORT(q->queue, q->nr, depth_first);\n \n \tfor (i = 0; i < q->nr; i++) {\n \t\tstruct diff_filespec *ospec = q->queue[i]->one;\ndiff --git a/builtin/fmt-merge-msg.c b/builtin/fmt-merge-msg.c\nindex dc2e9e4..4976967 100644\n--- a/builtin/fmt-merge-msg.c\n+++ b/builtin/fmt-merge-msg.c\n@@ -315,12 +315,10 @@ static void add_people_info(struct strbuf *out,\n \t\t\t    struct string_list *committers)\n {\n \tif (authors->nr)\n-\t\tqsort(authors->items,\n-\t\t      authors->nr, sizeof(authors->items[0]),\n+\t\tQSORT(authors->items, authors->nr,\n \t\t      cmp_string_list_util_as_integral);\n \tif (committers->nr)\n-\t\tqsort(committers->items,\n-\t\t      committers->nr, sizeof(committers->items[0]),\n+\t\tQSORT(committers->items, committers->nr,\n \t\t      cmp_string_list_util_as_integral);\n \n \tcredit_people(out, authors, 'a');\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 4a8b4ae..7657d0a 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1190,10 +1190,8 @@ static void resolve_deltas(void)\n \t\treturn;\n \n \t/* Sort deltas by base SHA1/offset for fast searching */\n-\tqsort(ofs_deltas, nr_ofs_deltas, sizeof(struct ofs_delta_entry),\n-\t      compare_ofs_delta_entry);\n-\tqsort(ref_deltas, nr_ref_deltas, sizeof(struct ref_delta_entry),\n-\t      compare_ref_delta_entry);\n+\tQSORT(ofs_deltas, nr_ofs_deltas, compare_ofs_delta_entry);\n+\tQSORT(ref_deltas, nr_ref_deltas, compare_ref_delta_entry);\n \n \tif (verbose || show_resolving_progress)\n \t\tprogress = start_progress(_(\"Resolving deltas\"),\n@@ -1356,7 +1354,7 @@ static void fix_unresolved_deltas(struct sha1file *f)\n \tALLOC_ARRAY(sorted_by_pos, nr_ref_deltas);\n \tfor (i = 0; i < nr_ref_deltas; i++)\n \t\tsorted_by_pos[i] = &ref_deltas[i];\n-\tqsort(sorted_by_pos, nr_ref_deltas, sizeof(*sorted_by_pos), delta_pos_compare);\n+\tQSORT(sorted_by_pos, nr_ref_deltas, delta_pos_compare);\n \n \tfor (i = 0; i < nr_ref_deltas; i++) {\n \t\tstruct ref_delta_entry *d = sorted_by_pos[i];\ndiff --git a/builtin/mktree.c b/builtin/mktree.c\nindex 4282b62..de9b40f 100644\n--- a/builtin/mktree.c\n+++ b/builtin/mktree.c\n@@ -46,7 +46,7 @@ static void write_tree(unsigned char *sha1)\n \tsize_t size;\n \tint i;\n \n-\tqsort(entries, used, sizeof(*entries), ent_compare);\n+\tQSORT(entries, used, ent_compare);\n \tfor (size = i = 0; i < used; i++)\n \t\tsize += 32 + entries[i]->len;\n \ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex 57be35f..cd89d48 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -195,8 +195,7 @@ static const char *get_exact_ref_match(const struct object *o)\n \t\treturn NULL;\n \n \tif (!tip_table.sorted) {\n-\t\tqsort(tip_table.table, tip_table.nr, sizeof(*tip_table.table),\n-\t\t      tipcmp);\n+\t\tQSORT(tip_table.table, tip_table.nr, tipcmp);\n \t\ttip_table.sorted = 1;\n \t}\n \ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 166e52c..8aeba6a 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1535,7 +1535,7 @@ static void get_object_details(void)\n \tsorted_by_offset = xcalloc(to_pack.nr_objects, sizeof(struct object_entry *));\n \tfor (i = 0; i < to_pack.nr_objects; i++)\n \t\tsorted_by_offset[i] = to_pack.objects + i;\n-\tqsort(sorted_by_offset, to_pack.nr_objects, sizeof(*sorted_by_offset), pack_offset_sort);\n+\tQSORT(sorted_by_offset, to_pack.nr_objects, pack_offset_sort);\n \n \tfor (i = 0; i < to_pack.nr_objects; i++) {\n \t\tstruct object_entry *entry = sorted_by_offset[i];\n@@ -2257,7 +2257,7 @@ static void prepare_pack(int window, int depth)\n \t\tif (progress)\n \t\t\tprogress_state = start_progress(_(\"Compressing objects\"),\n \t\t\t\t\t\t\tnr_deltas);\n-\t\tqsort(delta_list, n, sizeof(*delta_list), type_size_sort);\n+\t\tQSORT(delta_list, n, type_size_sort);\n \t\tll_find_deltas(delta_list, n, window+1, depth, &nr_done);\n \t\tstop_progress(&progress_state);\n \t\tif (nr_done != nr_deltas)\n@@ -2449,8 +2449,7 @@ static void add_objects_in_unpacked_packs(struct rev_info *revs)\n \t}\n \n \tif (in_pack.nr) {\n-\t\tqsort(in_pack.array, in_pack.nr, sizeof(in_pack.array[0]),\n-\t\t      ofscmp);\n+\t\tQSORT(in_pack.array, in_pack.nr, ofscmp);\n \t\tfor (i = 0; i < in_pack.nr; i++) {\n \t\t\tstruct object *o = in_pack.array[i].object;\n \t\t\tadd_object_entry(o->oid.hash, o->type, \"\", 0);\ndiff --git a/builtin/remote.c b/builtin/remote.c\nindex 9f6a6b3..e52cf39 100644\n--- a/builtin/remote.c\n+++ b/builtin/remote.c\n@@ -1197,8 +1197,7 @@ static int show(int argc, const char **argv)\n \n \t\tinfo.width = info.width2 = 0;\n \t\tfor_each_string_list(&states.push, add_push_to_show_info, &info);\n-\t\tqsort(info.list->items, info.list->nr,\n-\t\t\tsizeof(*info.list->items), cmp_string_with_push);\n+\t\tQSORT(info.list->items, info.list->nr, cmp_string_with_push);\n \t\tif (info.list->nr)\n \t\t\tprintf_ln(Q_(\"  Local ref configured for 'git push'%s:\",\n \t\t\t\t     \"  Local refs configured for 'git push'%s:\",\ndiff --git a/diff.c b/diff.c\nindex a178ed3..c2f09fb 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -2019,7 +2019,7 @@ static void show_dirstat(struct diff_options *options)\n \t\treturn;\n \n \t/* Show all directories with more than x% of the changes */\n-\tqsort(dir.files, dir.nr, sizeof(dir.files[0]), dirstat_compare);\n+\tQSORT(dir.files, dir.nr, dirstat_compare);\n \tgather_dirstat(options, &dir, changed, \"\", 0);\n }\n \n@@ -2063,7 +2063,7 @@ static void show_dirstat_by_line(struct diffstat_t *data, struct diff_options *o\n \t\treturn;\n \n \t/* Show all directories with more than x% of the changes */\n-\tqsort(dir.files, dir.nr, sizeof(dir.files[0]), dirstat_compare);\n+\tQSORT(dir.files, dir.nr, dirstat_compare);\n \tgather_dirstat(options, &dir, changed, \"\", 0);\n }\n \n@@ -4923,7 +4923,7 @@ static int diffnamecmp(const void *a_, const void *b_)\n void diffcore_fix_diff_index(struct diff_options *options)\n {\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n-\tqsort(q->queue, q->nr, sizeof(q->queue[0]), diffnamecmp);\n+\tQSORT(q->queue, q->nr, diffnamecmp);\n }\n \n void diffcore_std(struct diff_options *options)\ndiff --git a/diffcore-delta.c b/diffcore-delta.c\nindex 4159748..2ebedb3 100644\n--- a/diffcore-delta.c\n+++ b/diffcore-delta.c\n@@ -158,10 +158,7 @@ static struct spanhash_top *hash_chars(struct diff_filespec *one)\n \t\tn = 0;\n \t\taccum1 = accum2 = 0;\n \t}\n-\tqsort(hash->data,\n-\t\t1ul << hash->alloc_log2,\n-\t\tsizeof(hash->data[0]),\n-\t\tspanhash_cmp);\n+\tQSORT(hash->data, 1ul << hash->alloc_log2, spanhash_cmp);\n \treturn hash;\n }\n \ndiff --git a/diffcore-order.c b/diffcore-order.c\nindex 69d41f7..1957f82 100644\n--- a/diffcore-order.c\n+++ b/diffcore-order.c\n@@ -101,7 +101,7 @@ void order_objects(const char *orderfile, obj_path_fn_t obj_path,\n \t\tobjs[i].orig_order = i;\n \t\tobjs[i].order = match_order(obj_path(objs[i].obj));\n \t}\n-\tqsort(objs, nr, sizeof(*objs), compare_objs_order);\n+\tQSORT(objs, nr, compare_objs_order);\n }\n \n static const char *pair_pathtwo(void *obj)\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 73d003a..54a2396 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -580,7 +580,7 @@ void diffcore_rename(struct diff_options *options)\n \tstop_progress(&progress);\n \n \t/* cost matrix sorted by most to least similar pair */\n-\tqsort(mx, dst_cnt * NUM_CANDIDATE_PER_DST, sizeof(*mx), score_compare);\n+\tQSORT(mx, dst_cnt * NUM_CANDIDATE_PER_DST, score_compare);\n \n \trename_count += find_renames(mx, dst_cnt, minimum_score, 0);\n \tif (detect_rename == DIFF_DETECT_COPY)\ndiff --git a/dir.c b/dir.c\nindex 9e09bcb..3bad1ad 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -2005,8 +2005,8 @@ int read_directory(struct dir_struct *dir, const char *path, int len, const stru\n \tif (!len || treat_leading_path(dir, path, len, simplify))\n \t\tread_directory_recursive(dir, path, len, untracked, 0, simplify);\n \tfree_simplify(simplify);\n-\tqsort(dir->entries, dir->nr, sizeof(struct dir_entry *), cmp_name);\n-\tqsort(dir->ignored, dir->ignored_nr, sizeof(struct dir_entry *), cmp_name);\n+\tQSORT(dir->entries, dir->nr, cmp_name);\n+\tQSORT(dir->ignored, dir->ignored_nr, cmp_name);\n \tif (dir->untracked) {\n \t\tstatic struct trace_key trace_untracked_stats = TRACE_KEY_INIT(UNTRACKED_STATS);\n \t\ttrace_printf_key(&trace_untracked_stats,\ndiff --git a/fast-import.c b/fast-import.c\nindex bf53ac9..cb545d7 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -1460,9 +1460,9 @@ static void mktree(struct tree_content *t, int v, struct strbuf *b)\n \tunsigned int i;\n \n \tif (!v)\n-\t\tqsort(t->entries,t->entry_count,sizeof(t->entries[0]),tecmp0);\n+\t\tQSORT(t->entries, t->entry_count, tecmp0);\n \telse\n-\t\tqsort(t->entries,t->entry_count,sizeof(t->entries[0]),tecmp1);\n+\t\tQSORT(t->entries, t->entry_count, tecmp1);\n \n \tfor (i = 0; i < t->entry_count; i++) {\n \t\tif (t->entries[i]->versions[v].mode)\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 85e77af..8a38d30 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -812,7 +812,7 @@ static struct ref *do_fetch_pack(struct fetch_pack_args *args,\n \tint agent_len;\n \n \tsort_ref_list(&ref, ref_compare_name);\n-\tqsort(sought, nr_sought, sizeof(*sought), cmp_ref_by_name);\n+\tQSORT(sought, nr_sought, cmp_ref_by_name);\n \n \tif ((args->depth > 0 || is_repository_shallow()) && !server_supports(\"shallow\"))\n \t\tdie(\"Server does not support shallow clients\");\ndiff --git a/help.c b/help.c\nindex 2ff3b5a..53e2a67 100644\n--- a/help.c\n+++ b/help.c\n@@ -170,8 +170,7 @@ void load_command_list(const char *prefix,\n \n \tif (exec_path) {\n \t\tlist_commands_in_dir(main_cmds, exec_path, prefix);\n-\t\tqsort(main_cmds->names, main_cmds->cnt,\n-\t\t      sizeof(*main_cmds->names), cmdname_compare);\n+\t\tQSORT(main_cmds->names, main_cmds->cnt, cmdname_compare);\n \t\tuniq(main_cmds);\n \t}\n \n@@ -190,8 +189,7 @@ void load_command_list(const char *prefix,\n \t\t}\n \t\tfree(paths);\n \n-\t\tqsort(other_cmds->names, other_cmds->cnt,\n-\t\t      sizeof(*other_cmds->names), cmdname_compare);\n+\t\tQSORT(other_cmds->names, other_cmds->cnt, cmdname_compare);\n \t\tuniq(other_cmds);\n \t}\n \texclude_cmds(other_cmds, main_cmds);\n@@ -238,8 +236,7 @@ void list_common_cmds_help(void)\n \t\t\tlongest = strlen(common_cmds[i].name);\n \t}\n \n-\tqsort(common_cmds, ARRAY_SIZE(common_cmds),\n-\t\tsizeof(common_cmds[0]), cmd_group_cmp);\n+\tQSORT(common_cmds, ARRAY_SIZE(common_cmds), cmd_group_cmp);\n \n \tputs(_(\"These are common Git commands used in various situations:\"));\n \n@@ -324,8 +321,7 @@ const char *help_unknown_cmd(const char *cmd)\n \n \tadd_cmd_list(&main_cmds, &aliases);\n \tadd_cmd_list(&main_cmds, &other_cmds);\n-\tqsort(main_cmds.names, main_cmds.cnt,\n-\t      sizeof(*main_cmds.names), cmdname_compare);\n+\tQSORT(main_cmds.names, main_cmds.cnt, cmdname_compare);\n \tuniq(&main_cmds);\n \n \t/* This abuses cmdname->len for levenshtein distance */\n@@ -359,8 +355,7 @@ const char *help_unknown_cmd(const char *cmd)\n \t\t\tlevenshtein(cmd, candidate, 0, 2, 1, 3) + 1;\n \t}\n \n-\tqsort(main_cmds.names, main_cmds.cnt,\n-\t      sizeof(*main_cmds.names), levenshtein_compare);\n+\tQSORT(main_cmds.names, main_cmds.cnt, levenshtein_compare);\n \n \tif (!main_cmds.cnt)\n \t\tdie(_(\"Uh oh. Your system reports no Git commands at all.\"));\ndiff --git a/line-log.c b/line-log.c\nindex 916e724..65f3558 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -113,7 +113,7 @@ void sort_and_merge_range_set(struct range_set *rs)\n \tint i;\n \tint o = 0; /* output cursor */\n \n-\tqsort(rs->ranges, rs->nr, sizeof(struct range), range_cmp);\n+\tQSORT(rs->ranges, rs->nr, range_cmp);\n \n \tfor (i = 0; i < rs->nr; i++) {\n \t\tif (rs->ranges[i].start == rs->ranges[i].end)\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex c30bcd0..9705596 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -385,8 +385,7 @@ void bitmap_writer_select_commits(struct commit **indexed_commits,\n {\n \tunsigned int i = 0, j, next;\n \n-\tqsort(indexed_commits, indexed_commits_nr, sizeof(indexed_commits[0]),\n-\t      date_compare);\n+\tQSORT(indexed_commits, indexed_commits_nr, date_compare);\n \n \tif (writer.show_progress)\n \t\twriter.progress = start_progress(\"Selecting bitmap commits\", 0);\ndiff --git a/pack-check.c b/pack-check.c\nindex d123846..72440a8 100644\n--- a/pack-check.c\n+++ b/pack-check.c\n@@ -99,7 +99,7 @@ static int verify_packfile(struct packed_git *p,\n \t\tentries[i].offset = nth_packed_object_offset(p, i);\n \t\tentries[i].nr = i;\n \t}\n-\tqsort(entries, nr_objects, sizeof(*entries), compare_entries);\n+\tQSORT(entries, nr_objects, compare_entries);\n \n \tfor (i = 0; i < nr_objects; i++) {\n \t\tvoid *data;\ndiff --git a/pack-write.c b/pack-write.c\nindex ea0b788..88bc7f9 100644\n--- a/pack-write.c\n+++ b/pack-write.c\n@@ -61,8 +61,7 @@ const char *write_idx_file(const char *index_name, struct pack_idx_entry **objec\n \t\t\tif (objects[i]->offset > last_obj_offset)\n \t\t\t\tlast_obj_offset = objects[i]->offset;\n \t\t}\n-\t\tqsort(sorted_by_sha, nr_objects, sizeof(sorted_by_sha[0]),\n-\t\t      sha1_compare);\n+\t\tQSORT(sorted_by_sha, nr_objects, sha1_compare);\n \t}\n \telse\n \t\tsorted_by_sha = list = last = NULL;\ndiff --git a/pathspec.c b/pathspec.c\nindex 24e0dd5..eda13b5 100644\n--- a/pathspec.c\n+++ b/pathspec.c\n@@ -446,8 +446,7 @@ void parse_pathspec(struct pathspec *pathspec,\n \tif (pathspec->magic & PATHSPEC_MAXDEPTH) {\n \t\tif (flags & PATHSPEC_KEEP_ORDER)\n \t\t\tdie(\"BUG: PATHSPEC_MAXDEPTH_VALID and PATHSPEC_KEEP_ORDER are incompatible\");\n-\t\tqsort(pathspec->items, pathspec->nr,\n-\t\t      sizeof(struct pathspec_item), pathspec_item_cmp);\n+\t\tQSORT(pathspec->items, pathspec->nr, pathspec_item_cmp);\n \t}\n }\n \ndiff --git a/ref-filter.c b/ref-filter.c\nindex 9adbb8a..44029b0 100644\n--- a/ref-filter.c\n+++ b/ref-filter.c\n@@ -1573,7 +1573,7 @@ static int compare_refs(const void *a_, const void *b_)\n void ref_array_sort(struct ref_sorting *sorting, struct ref_array *array)\n {\n \tref_sorting = sorting;\n-\tqsort(array->items, array->nr, sizeof(struct ref_array_item *), compare_refs);\n+\tQSORT(array->items, array->nr, compare_refs);\n }\n \n static void append_literal(const char *cp, const char *ep, struct ref_formatting_state *state)\ndiff --git a/refs/files-backend.c b/refs/files-backend.c\nindex 0709f60..d16feb1 100644\n--- a/refs/files-backend.c\n+++ b/refs/files-backend.c\n@@ -501,7 +501,7 @@ static void sort_ref_dir(struct ref_dir *dir)\n \tif (dir->sorted == dir->nr)\n \t\treturn;\n \n-\tqsort(dir->entries, dir->nr, sizeof(*dir->entries), ref_entry_cmp);\n+\tQSORT(dir->entries, dir->nr, ref_entry_cmp);\n \n \t/* Remove any duplicates: */\n \tfor (i = 0, j = 0; j < dir->nr; j++) {\ndiff --git a/server-info.c b/server-info.c\nindex 75dd677..7bc4e75 100644\n--- a/server-info.c\n+++ b/server-info.c\n@@ -229,7 +229,7 @@ static void init_pack_info(const char *infofile, int force)\n \t}\n \n \t/* renumber them */\n-\tqsort(info, num_pack, sizeof(info[0]), compare_info);\n+\tQSORT(info, num_pack, compare_info);\n \tfor (i = 0; i < num_pack; i++)\n \t\tinfo[i]->new_num = i;\n }\ndiff --git a/sh-i18n--envsubst.c b/sh-i18n--envsubst.c\nindex e06b2c1..3637a2a 100644\n--- a/sh-i18n--envsubst.c\n+++ b/sh-i18n--envsubst.c\n@@ -231,7 +231,7 @@ static inline void\n string_list_sort (string_list_ty *slp)\n {\n   if (slp->nitems > 0)\n-    qsort (slp->item, slp->nitems, sizeof (slp->item[0]), cmp_string);\n+    QSORT(slp->item, slp->nitems, cmp_string);\n }\n \n /* Test whether a sorted string list contains a given string.  */\ndiff --git a/sha1-array.c b/sha1-array.c\nindex 6f4a224..21188de 100644\n--- a/sha1-array.c\n+++ b/sha1-array.c\n@@ -16,7 +16,7 @@ static int void_hashcmp(const void *a, const void *b)\n \n static void sha1_array_sort(struct sha1_array *array)\n {\n-\tqsort(array->sha1, array->nr, sizeof(*array->sha1), void_hashcmp);\n+\tQSORT(array->sha1, array->nr, void_hashcmp);\n \tarray->sorted = 1;\n }\n \ndiff --git a/string-list.c b/string-list.c\nindex 62d2084..8c83cac 100644\n--- a/string-list.c\n+++ b/string-list.c\n@@ -225,7 +225,7 @@ static int cmp_items(const void *a, const void *b)\n void string_list_sort(struct string_list *list)\n {\n \tcompare_for_qsort = list->cmp ? list->cmp : strcmp;\n-\tqsort(list->items, list->nr, sizeof(*list->items), cmp_items);\n+\tQSORT(list->items, list->nr, cmp_items);\n }\n \n struct string_list_item *unsorted_string_list_lookup(struct string_list *list,\ndiff --git a/t/helper/test-dump-untracked-cache.c b/t/helper/test-dump-untracked-cache.c\nindex 50112cc..f752532 100644\n--- a/t/helper/test-dump-untracked-cache.c\n+++ b/t/helper/test-dump-untracked-cache.c\n@@ -18,10 +18,8 @@ static int compare_dir(const void *a_, const void *b_)\n static void dump(struct untracked_cache_dir *ucd, struct strbuf *base)\n {\n \tint i, len;\n-\tqsort(ucd->untracked, ucd->untracked_nr, sizeof(*ucd->untracked),\n-\t      compare_untracked);\n-\tqsort(ucd->dirs, ucd->dirs_nr, sizeof(*ucd->dirs),\n-\t      compare_dir);\n+\tQSORT(ucd->untracked, ucd->untracked_nr, compare_untracked);\n+\tQSORT(ucd->dirs, ucd->dirs_nr, compare_dir);\n \tlen = base->len;\n \tstrbuf_addf(base, \"%s/\", ucd->name);\n \tprintf(\"%s %s\", base->buf,\ndiff --git a/tree.c b/tree.c\nindex 2b5a5a8..ce345c5 100644\n--- a/tree.c\n+++ b/tree.c\n@@ -180,8 +180,7 @@ int read_tree(struct tree *tree, int stage, struct pathspec *match)\n \t * Sort the cache entry -- we need to nuke the cache tree, though.\n \t */\n \tcache_tree_free(&active_cache_tree);\n-\tqsort(active_cache, active_nr, sizeof(active_cache[0]),\n-\t      cmp_cache_name_compare);\n+\tQSORT(active_cache, active_nr, cmp_cache_name_compare);\n \treturn 0;\n }\n \n-- \n2.10.0\n\n"},{"id":"302892","messageId":"51040709-64da-37bf-b5b4-0228e2be51b4@web.de","threadId":"44187","inReplyTo":"67bddc37-4ee2-fef0-c852-e32645421e4c@web.de","subject":"[PATCH 3/3] remove unnecessary check before QSORT","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-09-29T15:29:29Z","receivedAt":"2016-09-29T15:29:47Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Add a semantic patch for removing checks similar to the one that QSORT\nalready does internally and apply it to the code base.\n\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\n builtin/fmt-merge-msg.c        | 10 ++++------\n contrib/coccinelle/qsort.cocci | 18 ++++++++++++++++++\n sh-i18n--envsubst.c            |  3 +--\n 3 files changed, 23 insertions(+), 8 deletions(-)\n\ndiff --git a/builtin/fmt-merge-msg.c b/builtin/fmt-merge-msg.c\nindex 4976967..efab62f 100644\n--- a/builtin/fmt-merge-msg.c\n+++ b/builtin/fmt-merge-msg.c\n@@ -314,12 +314,10 @@ static void add_people_info(struct strbuf *out,\n \t\t\t    struct string_list *authors,\n \t\t\t    struct string_list *committers)\n {\n-\tif (authors->nr)\n-\t\tQSORT(authors->items, authors->nr,\n-\t\t      cmp_string_list_util_as_integral);\n-\tif (committers->nr)\n-\t\tQSORT(committers->items, committers->nr,\n-\t\t      cmp_string_list_util_as_integral);\n+\tQSORT(authors->items, authors->nr,\n+\t      cmp_string_list_util_as_integral);\n+\tQSORT(committers->items, committers->nr,\n+\t      cmp_string_list_util_as_integral);\n \n \tcredit_people(out, authors, 'a');\n \tcredit_people(out, committers, 'c');\ndiff --git a/contrib/coccinelle/qsort.cocci b/contrib/coccinelle/qsort.cocci\nindex a094e7c..22b93a9 100644\n--- a/contrib/coccinelle/qsort.cocci\n+++ b/contrib/coccinelle/qsort.cocci\n@@ -17,3 +17,21 @@ expression nmemb, compar;\n @@\n - qsort(base, nmemb, sizeof(T), compar);\n + QSORT(base, nmemb, compar);\n+\n+@@\n+expression base, nmemb, compar;\n+@@\n+- if (nmemb)\n+    QSORT(base, nmemb, compar);\n+\n+@@\n+expression base, nmemb, compar;\n+@@\n+- if (nmemb > 0)\n+    QSORT(base, nmemb, compar);\n+\n+@@\n+expression base, nmemb, compar;\n+@@\n+- if (nmemb > 1)\n+    QSORT(base, nmemb, compar);\ndiff --git a/sh-i18n--envsubst.c b/sh-i18n--envsubst.c\nindex 3637a2a..c3a2b5a 100644\n--- a/sh-i18n--envsubst.c\n+++ b/sh-i18n--envsubst.c\n@@ -230,8 +230,7 @@ cmp_string (const void *pstr1, const void *pstr2)\n static inline void\n string_list_sort (string_list_ty *slp)\n {\n-  if (slp->nitems > 0)\n-    QSORT(slp->item, slp->nitems, cmp_string);\n+  QSORT(slp->item, slp->nitems, cmp_string);\n }\n \n /* Test whether a sorted string list contains a given string.  */\n-- \n2.10.0\n\n"},{"id":"302959","messageId":"xmqqponmcp07.fsf@gitster.mtv.corp.google.com","threadId":"44187","inReplyTo":"67bddc37-4ee2-fef0-c852-e32645421e4c@web.de","subject":"Re: [PATCH 1/3] add QSORT","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-09-29T22:36:24Z","receivedAt":"2016-09-29T22:36:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe <l.s.r@web.de> writes:\n\n> Add the macro QSORT, a convenient wrapper for qsort(3) that infers the\n> size of the array elements and supports the convention of initializing\n> empty arrays with a NULL pointer, which we use in some places.\n>\n> Calling qsort(3) directly with a NULL pointer is undefined -- even with\n> an element count of zero -- and allows the compiler to optimize away any\n> following NULL checks.  Using the macro avoids such surprises.\n>\n> Add a semantic patch as well to demonstrate the macro's usage and to\n> automate the transformation of trivial cases.\n>\n> Signed-off-by: Rene Scharfe <l.s.r@web.de>\n> ---\n>  contrib/coccinelle/qsort.cocci | 19 +++++++++++++++++++\n>  git-compat-util.h              |  8 ++++++++\n>  2 files changed, 27 insertions(+)\n>  create mode 100644 contrib/coccinelle/qsort.cocci\n\nThe direct calls to qsort(3) that this series leaves behind are\ninteresting.\n\n1. builtin/index-pack.c has this:\n\n\tif (1 < opts->anomaly_nr)\n\t\tqsort(opts->anomaly, opts->anomaly_nr, sizeof(uint32_t), cmp_uint32);\n\nwhere opts->anomaly is coming from pack.h:\n\n    struct pack_idx_option {\n            unsigned flags;\n            ...\n            int anomaly_alloc, anomaly_nr;\n            uint32_t *anomaly;\n    };\n\nI cannot quite see how the automated conversion misses it?  It's not\nlike base and nmemb are type-restricted in the rule (they are both\njust \"expression\"s).\n\n2. builtin/shortlog.c has this:\n\n\tqsort(log->list.items, log->list.nr, sizeof(struct string_list_item),\n\t      log->summary ? compare_by_counter : compare_by_list);\n\nwhere log->list is coming from shortlog.h:\n\n    struct shortlog {\n            struct string_list list;\n    };\n\nand string-list.h says:\n\n    struct string_list {\n            struct string_list_item *items;\n            unsigned int nr, alloc;\n            ...\n    };\n\nwhich seems to be a good candidate for this rule:\n\n    type T;\n    T *base;\n    expression nmemb, compar;\n    @@\n    - qsort(base, nmemb, sizeof(T), compar);\n    + QSORT(base, nmemb, compar);\n\nif we take \"T == struct string_list_item\".\n\n3. builtin/show-branch.c does this:\n\n    qsort(ref_name + bottom, top - bottom, sizeof(ref_name[0]),\n          compare_ref_name);\n\nwhere ref_name[] is a file-scope global:\n\n    static char *ref_name[MAX_REVS + 1];\n\nand top and bottom are plain integers.  The sizeof() does not take\nthe size of *base, so it is understandable that this does not get\nautomatically converted.\n\nIt seems that some calls to this function _could_ send the same top\nand bottom, asking for 0 element array to be sorted, by the way.\n\nThanks for an amusing read.\n\n"},{"id":"302962","messageId":"eeb2791e-c09b-b7bc-f8e8-336d4f3906b8@web.de","threadId":"44187","inReplyTo":"xmqqponmcp07.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 1/3] add QSORT","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-09-29T23:21:17Z","receivedAt":"2016-09-29T23:21:39Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 30.09.2016 um 00:36 schrieb Junio C Hamano:\n> René Scharfe <l.s.r@web.de> writes:\n> \n>> Add the macro QSORT, a convenient wrapper for qsort(3) that infers the\n>> size of the array elements and supports the convention of initializing\n>> empty arrays with a NULL pointer, which we use in some places.\n>>\n>> Calling qsort(3) directly with a NULL pointer is undefined -- even with\n>> an element count of zero -- and allows the compiler to optimize away any\n>> following NULL checks.  Using the macro avoids such surprises.\n>>\n>> Add a semantic patch as well to demonstrate the macro's usage and to\n>> automate the transformation of trivial cases.\n>>\n>> Signed-off-by: Rene Scharfe <l.s.r@web.de>\n>> ---\n>>  contrib/coccinelle/qsort.cocci | 19 +++++++++++++++++++\n>>  git-compat-util.h              |  8 ++++++++\n>>  2 files changed, 27 insertions(+)\n>>  create mode 100644 contrib/coccinelle/qsort.cocci\n> \n> The direct calls to qsort(3) that this series leaves behind are\n> interesting.\n> \n> 1. builtin/index-pack.c has this:\n> \n> \tif (1 < opts->anomaly_nr)\n> \t\tqsort(opts->anomaly, opts->anomaly_nr, sizeof(uint32_t), cmp_uint32);\n> \n> where opts->anomaly is coming from pack.h:\n> \n>     struct pack_idx_option {\n>             unsigned flags;\n>             ...\n>             int anomaly_alloc, anomaly_nr;\n>             uint32_t *anomaly;\n>     };\n> \n> I cannot quite see how the automated conversion misses it?  It's not\n> like base and nmemb are type-restricted in the rule (they are both\n> just \"expression\"s).\n> \n> 2. builtin/shortlog.c has this:\n> \n> \tqsort(log->list.items, log->list.nr, sizeof(struct string_list_item),\n> \t      log->summary ? compare_by_counter : compare_by_list);\n> \n> where log->list is coming from shortlog.h:\n> \n>     struct shortlog {\n>             struct string_list list;\n>     };\n> \n> and string-list.h says:\n> \n>     struct string_list {\n>             struct string_list_item *items;\n>             unsigned int nr, alloc;\n>             ...\n>     };\n> \n> which seems to be a good candidate for this rule:\n> \n>     type T;\n>     T *base;\n>     expression nmemb, compar;\n>     @@\n>     - qsort(base, nmemb, sizeof(T), compar);\n>     + QSORT(base, nmemb, compar);\n> \n> if we take \"T == struct string_list_item\".\n\nTransformations for these two are generated if we pass --all-includes\nto spatch.  So let's do that.\n\n-- >8 --\nSubject: [PATCH] coccicheck: use --all-includes by default\n\nAdd a make variable, SPATCH_FLAGS, for specifying flags for spatch, and\nset it to --all-includes by default.  This option lets it consider\nheader files which would otherwise be ignored.  That's important for\nsome rules that rely on type information.  It doubles the duration of\ncoccicheck, however.\n\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\n Makefile | 3 ++-\n 1 file changed, 2 insertions(+), 1 deletion(-)\n\ndiff --git a/Makefile b/Makefile\nindex 1aad150..d15bf8d 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -467,6 +467,7 @@ SPATCH = spatch\n export TCL_PATH TCLTK_PATH\n \n SPARSE_FLAGS =\n+SPATCH_FLAGS = --all-includes\n \n \n \n@@ -2314,7 +2315,7 @@ C_SOURCES = $(patsubst %.o,%.c,$(C_OBJ))\n %.cocci.patch: %.cocci $(C_SOURCES)\n \t@echo '    ' SPATCH $<; \\\n \tfor f in $(C_SOURCES); do \\\n-\t\t$(SPATCH) --sp-file $< $$f; \\\n+\t\t$(SPATCH) --sp-file $< $$f $(SPATCH_FLAGS); \\\n \tdone >$@ 2>$@.log; \\\n \tif test -s $@; \\\n \tthen \\\n-- \n2.10.0\n\n"},{"id":"302964","messageId":"302c140e-bfb9-a54c-7ce0-14b266611584@web.de","threadId":"44187","inReplyTo":"eeb2791e-c09b-b7bc-f8e8-336d4f3906b8@web.de","subject":"Re: [PATCH 1/3] add QSORT","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-09-29T23:40:14Z","receivedAt":"2016-09-29T23:40:47Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 30.09.2016 um 01:21 schrieb René Scharfe:\n> Am 30.09.2016 um 00:36 schrieb Junio C Hamano:\n>> René Scharfe <l.s.r@web.de> writes:\n>>\n>>> Add the macro QSORT, a convenient wrapper for qsort(3) that infers the\n>>> size of the array elements and supports the convention of initializing\n>>> empty arrays with a NULL pointer, which we use in some places.\n>>>\n>>> Calling qsort(3) directly with a NULL pointer is undefined -- even with\n>>> an element count of zero -- and allows the compiler to optimize away any\n>>> following NULL checks.  Using the macro avoids such surprises.\n>>>\n>>> Add a semantic patch as well to demonstrate the macro's usage and to\n>>> automate the transformation of trivial cases.\n>>>\n>>> Signed-off-by: Rene Scharfe <l.s.r@web.de>\n>>> ---\n>>>  contrib/coccinelle/qsort.cocci | 19 +++++++++++++++++++\n>>>  git-compat-util.h              |  8 ++++++++\n>>>  2 files changed, 27 insertions(+)\n>>>  create mode 100644 contrib/coccinelle/qsort.cocci\n>>\n>> The direct calls to qsort(3) that this series leaves behind are\n>> interesting.\n>>\n>> 1. builtin/index-pack.c has this:\n>>\n>> \tif (1 < opts->anomaly_nr)\n>> \t\tqsort(opts->anomaly, opts->anomaly_nr, sizeof(uint32_t), cmp_uint32);\n>>\n>> where opts->anomaly is coming from pack.h:\n>>\n>>     struct pack_idx_option {\n>>             unsigned flags;\n>>             ...\n>>             int anomaly_alloc, anomaly_nr;\n>>             uint32_t *anomaly;\n>>     };\n>>\n>> I cannot quite see how the automated conversion misses it?  It's not\n>> like base and nmemb are type-restricted in the rule (they are both\n>> just \"expression\"s).\n>>\n>> 2. builtin/shortlog.c has this:\n>>\n>> \tqsort(log->list.items, log->list.nr, sizeof(struct string_list_item),\n>> \t      log->summary ? compare_by_counter : compare_by_list);\n>>\n>> where log->list is coming from shortlog.h:\n>>\n>>     struct shortlog {\n>>             struct string_list list;\n>>     };\n>>\n>> and string-list.h says:\n>>\n>>     struct string_list {\n>>             struct string_list_item *items;\n>>             unsigned int nr, alloc;\n>>             ...\n>>     };\n>>\n>> which seems to be a good candidate for this rule:\n>>\n>>     type T;\n>>     T *base;\n>>     expression nmemb, compar;\n>>     @@\n>>     - qsort(base, nmemb, sizeof(T), compar);\n>>     + QSORT(base, nmemb, compar);\n>>\n>> if we take \"T == struct string_list_item\".\n> \n> Transformations for these two are generated if we pass --all-includes\n> to spatch.  So let's do that.\n\nAnd here's the result:\n\n-- >8 --\nSubject: [PATCH] use QSORT, part 2\n\nConvert two more qsort(3) calls to QSORT to reduce code size and for\nbetter safety and consistency.\n\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\nSquashable.\n\n builtin/index-pack.c | 3 +--\n builtin/shortlog.c   | 2 +-\n 2 files changed, 2 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 7657d0a..0a27bab 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1531,8 +1531,7 @@ static void read_v2_anomalous_offsets(struct packed_git *p,\n \t\topts->anomaly[opts->anomaly_nr++] = ntohl(idx2[off * 2 + 1]);\n \t}\n \n-\tif (1 < opts->anomaly_nr)\n-\t\tqsort(opts->anomaly, opts->anomaly_nr, sizeof(uint32_t), cmp_uint32);\n+\tQSORT(opts->anomaly, opts->anomaly_nr, cmp_uint32);\n }\n \n static void read_idx_option(struct pack_idx_option *opts, const char *pack_name)\ndiff --git a/builtin/shortlog.c b/builtin/shortlog.c\nindex 25fa8a6..ba0e115 100644\n--- a/builtin/shortlog.c\n+++ b/builtin/shortlog.c\n@@ -308,7 +308,7 @@ void shortlog_output(struct shortlog *log)\n \tstruct strbuf sb = STRBUF_INIT;\n \n \tif (log->sort_by_number)\n-\t\tqsort(log->list.items, log->list.nr, sizeof(struct string_list_item),\n+\t\tQSORT(log->list.items, log->list.nr,\n \t\t      log->summary ? compare_by_counter : compare_by_list);\n \tfor (i = 0; i < log->list.nr; i++) {\n \t\tconst struct string_list_item *item = &log->list.items[i];\n-- \n2.10.0\n\n\n"},{"id":"303045","messageId":"83398160-555f-adab-6b1e-3283c533b5ff@web.de","threadId":"44187","inReplyTo":"xmqqponmcp07.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 1/3] add QSORT","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-10-01T16:19:48Z","receivedAt":"2016-10-01T16:21:22Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 30.09.2016 um 00:36 schrieb Junio C Hamano:\n> 3. builtin/show-branch.c does this:\n> \n>     qsort(ref_name + bottom, top - bottom, sizeof(ref_name[0]),\n>           compare_ref_name);\n> \n> where ref_name[] is a file-scope global:\n> \n>     static char *ref_name[MAX_REVS + 1];\n> \n> and top and bottom are plain integers.  The sizeof() does not take\n> the size of *base, so it is understandable that this does not get\n> automatically converted.\n> \n> It seems that some calls to this function _could_ send the same top\n> and bottom, asking for 0 element array to be sorted, by the way.\n\nIt's hard to imagine an implementation of qsort(3) that can't handle\nzero elements.  QSORT's safety feature is that it prevents the compiler\nfrom removing NULL checks for the array pointer.  E.g. the last two\nlines in the following example could be optimized away:\n\n\tqsort(ptr, n, sizeof(*ptr), fn);\n\tif (!ptr)\n\t\tdo_stuff();\n\nYou can see that on https://godbolt.org/g/JwS99b -- an awesome website\nfor exploring compilation results for small snippets, by the way.\n\nThis optimization is dangerous when combined with the convention of\nusing a NULL pointer for empty arrays.  Diagnosing an affected NULL\ncheck is probably quite hard -- it's right there in the code after all\nand not all compilers remove it.\n\nbuiltin/show-branch.c never passes NULL, so it's not affected by that\nhazard.  We can (and should, IMHO) still use QSORT there for\nconsistency and convenience, though:\n\n-- >8 --\nSubject: [PATCH] show-branch: use QSORT\n\nShorten the code by using QSORT instead of calling qsort(3) directly,\nas the former determines the element size automatically and checks if\nthere are at least two elements to sort already.\n\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\n builtin/show-branch.c | 6 ++----\n 1 file changed, 2 insertions(+), 4 deletions(-)\n\ndiff --git a/builtin/show-branch.c b/builtin/show-branch.c\nindex 623ca56..974f340 100644\n--- a/builtin/show-branch.c\n+++ b/builtin/show-branch.c\n@@ -353,8 +353,7 @@ static int compare_ref_name(const void *a_, const void *b_)\n \n static void sort_ref_range(int bottom, int top)\n {\n-\tqsort(ref_name + bottom, top - bottom, sizeof(ref_name[0]),\n-\t      compare_ref_name);\n+\tQSORT(ref_name + bottom, top - bottom, compare_ref_name);\n }\n \n static int append_ref(const char *refname, const struct object_id *oid,\n@@ -540,8 +539,7 @@ static void append_one_rev(const char *av)\n \t\tif (saved_matches == ref_name_cnt &&\n \t\t    ref_name_cnt < MAX_REVS)\n \t\t\terror(_(\"no matching refs with %s\"), av);\n-\t\tif (saved_matches + 1 < ref_name_cnt)\n-\t\t\tsort_ref_range(saved_matches, ref_name_cnt);\n+\t\tsort_ref_range(saved_matches, ref_name_cnt);\n \t\treturn;\n \t}\n \tdie(\"bad sha1 reference %s\", av);\n-- \n2.10.0\n\n\n"},{"id":"303100","messageId":"57F290DC.5080303@bracey.fi","threadId":"44187","inReplyTo":"83398160-555f-adab-6b1e-3283c533b5ff@web.de","subject":"Re: [PATCH 1/3] add QSORT","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2016-10-03T17:09:48Z","receivedAt":"2016-10-03T17:29:30Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"On 01/10/2016 19:19, René Scharfe wrote:\n>\n> It's hard to imagine an implementation of qsort(3) that can't handle\n> zero elements.  QSORT's safety feature is that it prevents the compiler\n> from removing NULL checks for the array pointer.  E.g. the last two\n> lines in the following example could be optimized away:\n>\n> \tqsort(ptr, n, sizeof(*ptr), fn);\n> \tif (!ptr)\n> \t\tdo_stuff();\n>\n> You can see that on https://godbolt.org/g/JwS99b -- an awesome website\n> for exploring compilation results for small snippets, by the way.\n>\nAh, second attempt. Originally misread the original code, and didn't \nunderstand what it was doing.\n\nI get it now.\n\nA nasty trap I hadn't been aware of - I was under the impression NULL + \nzero length was generally legal, but the C standard does indeed not give \nyou a specific out for NULL to library functions in that case.\n\nAs such, NULL checks can still be elided even with your change. If you \neffectively change your example to:\n\n     if (nmemb > 1)\n         qsort(array, nmemb, size, cmp);\n     if (!array)\n         printf(\"array is NULL\\n\");\n\narray may only be checked for NULL if nmemb <= 1. You can see GCC doing \nthat in the compiler explorer - it effectively turns that into \"else \nif\".  To make that check really work, you have to do:\n\n     if (array)\n         qsort(array, nmemb, size, cmp);\n     else\n         printf(\"array is NULL\\n\");\n\nSo maybe your \"sane_qsort\" should be checking array, not nmemb.\n\nKevin\n\n"},{"id":"303103","messageId":"57F28B6B.1010204@bracey.fi","threadId":"44187","inReplyTo":"83398160-555f-adab-6b1e-3283c533b5ff@web.de","subject":"Re: [PATCH 1/3] add QSORT","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2016-10-03T16:46:35Z","receivedAt":"2016-10-03T18:04:22Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"On 01/10/2016 19:19, René Scharfe wrote:\n> It's hard to imagine an implementation of qsort(3) that can't handle\n> zero elements.  QSORT's safety feature is that it prevents the compiler\n> from removing NULL checks for the array pointer.  E.g. the last two\n> lines in the following example could be optimized away:\n>\n> \tqsort(ptr, n, sizeof(*ptr), fn);\n> \tif (!ptr)\n> \t\tdo_stuff();\n>\n> You can see that on https://godbolt.org/g/JwS99b -- an awesome website\n> for exploring compilation results for small snippets, by the way.\n>\n> This optimization is dangerous when combined with the convention of\n> using a NULL pointer for empty arrays.  Diagnosing an affected NULL\n> check is probably quite hard -- it's right there in the code after all\n> and not all compilers remove it.\n\nHang on, hang on. This is either a compiler bug, or you're wrong on your \nassumption about the specification of qsort.\n\nEither way, the extra layer of indirection is not proper protection. The \nunwanted compiler optimisation you're inadvertently triggering could \nstill be triggered through the inline.\n\nNow, looking at the C standard, this isn't actually clear to me. The \nstandard says that if you call qsort with nmemb zero, the pointer still \nhas to be \"valid\". Not totally clear to me if NULL is valid, by their \ndefinition in C99 7.1.4. Googling hasn't given me a concrete answer.\n\nThe compiler seems to think that NULL wouldn't be valid, so because \nyou've called qsort on it, you've invoked undefined behaviour if it's \nNULL, so it's free to elide the NULL check.\n\nKevin\n\n"},{"id":"303149","messageId":"9ff725eb-3536-638b-1ec0-ff9130478abc@web.de","threadId":"44187","inReplyTo":"57F290DC.5080303@bracey.fi","subject":"Re: [PATCH 1/3] add QSORT","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-10-03T22:00:10Z","receivedAt":"2016-10-03T22:00:19Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 03.10.2016 um 19:09 schrieb Kevin Bracey:\n> As such, NULL checks can still be elided even with your change. If you\n> effectively change your example to:\n>\n>     if (nmemb > 1)\n>         qsort(array, nmemb, size, cmp);\n>     if (!array)\n>         printf(\"array is NULL\\n\");\n>\n> array may only be checked for NULL if nmemb <= 1. You can see GCC doing\n> that in the compiler explorer - it effectively turns that into \"else\n> if\".\n\nWe don't support array == NULL together with nmemb > 1, so a segfault is \nto be expected in such cases, and thus NULL checks can be removed safely.\n\n> To make that check really work, you have to do:\n>\n>     if (array)\n>         qsort(array, nmemb, size, cmp);\n>     else\n>         printf(\"array is NULL\\n\");\n>\n> So maybe your \"sane_qsort\" should be checking array, not nmemb.\n\nIt would be safe, but arguably too much so, because non-empty arrays \nwith NULL wouldn't segfault anymore, and thus become harder to identify \nas the programming errors they are.\n\nThe intention is to support NULL pointers only for empty arrays (in \naddition to valid pointers).  That we also support NULL pointers for \narrays with a single member might be considered to be the result of a \npremature optimization, but it should be safe -- the compiler won't \nremove checks unexpectedly.\n\nDoes that make sense (it's getting late here, so my logic might already \nbe resting..)?\n\nRené\n"},{"id":"303188","messageId":"57F33E12.4020900@bracey.fi","threadId":"44187","inReplyTo":"9ff725eb-3536-638b-1ec0-ff9130478abc@web.de","subject":"Re: [PATCH 1/3] add QSORT","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2016-10-04T05:28:50Z","receivedAt":"2016-10-04T06:46:06Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"On 04/10/2016 01:00, René Scharfe wrote:\n> Am 03.10.2016 um 19:09 schrieb Kevin Bracey:\n>> As such, NULL checks can still be elided even with your change. If you\n>> effectively change your example to:\n>>\n>>     if (nmemb > 1)\n>>         qsort(array, nmemb, size, cmp);\n>>     if (!array)\n>>         printf(\"array is NULL\\n\");\n>>\n>> array may only be checked for NULL if nmemb <= 1. You can see GCC doing\n>> that in the compiler explorer - it effectively turns that into \"else\n>> if\".\n>\n> We don't support array == NULL together with nmemb > 1, so a segfault \n> is to be expected in such cases, and thus NULL checks can be removed \n> safely.\n>\nPossibly true in practice.\n\nBut technically wrong by the C standard - behaviour is undefined if the \nqsort pointer is invalid. You can't formally expect the defined \nbehaviour of a segfault when sending NULL into qsort. (Hell, maybe the \nqsort has its own NULL check and silently returns! cf printf - some \nprintfs will segfault when passed NULL, some print \"(null)\"). I've \nworked on systems that don't fault reads to NULL, only writes, so those \nmight not segfault there, if NULL appeared sorted...\n\nAnd obviously there's the language lawyer favourite possibility of the \ncall causing nasal flying monkeys or whatever.\n\nSo if it's not a program error for array to be NULL and nmemb to be zero \nin your code, and you want a diagnostic for array=NULL, nmemb non-zero, \nI think you should put that diagnostic into sane_qsort as an assert or \nsomething, not rely on qsort's undefined behaviour being a segfault.\n\n     sane_qsort(blah)\n     {\n          if (nmemb >= 1) {\n              assert(array);\n              qsort(array, nmemb, ...);\n          }\n     }\n\nCan't invoke undefined behaviour from NULL without triggering the \nassert. (Could still have other invalid pointers, of course).\n\nUsually I am on the side of \"no NULL checks\", as I make the assumption \nthat we will get a segfault as soon as NULL pointers are used, and those \nare generally easy to diagnose. But seeing a compiler invoking this sort \nof new trickery due to invoking undefined behaviour is making me more \nnervous about doing so...\n\n>> To make that check really work, you have to do:\n>>\n>>     if (array)\n>>         qsort(array, nmemb, size, cmp);\n>>     else\n>>         printf(\"array is NULL\\n\");\n>>\n>> So maybe your \"sane_qsort\" should be checking array, not nmemb.\n>\n> It would be safe, but arguably too much so, because non-empty arrays \n> with NULL wouldn't segfault anymore, and thus become harder to \n> identify as the programming errors they are.\nWell, you get the print. Although I guess you're worrying about the \nsecond if being real code, not a debugging check.\n\nI must say, this is quite a courageous new optimisation from GCC. It \nstrikes me as finding a language lawyer loophole that seems to have been \nintended for something else (mapping library functions directly onto \nCISCy CPU intrinsics), and using it to invent a whole new optimisation \nthat seems more likely to trigger bugs than optimise any significant \namount of code in a desirable way.\n\nDoubly weird as there's no (standard) language support for this. I don't \nknow how you'd define \"my_qsort\" that triggered the same optimisations.\n\nI've seen similar \nlibrary-knowledge-without-any-way-to-reproduce-in-user-code \noptimisations like \"malloc returns a new pointer that doesn't alias with \nanything existing\" (and no way to reproduce the optimisation with \nmy_malloc_wrapper). But those seemed to have a clear performance \nbenefit, without any obvious traps. Doubtful about this one.\n\nKevin\n\n"},{"id":"303294","messageId":"29d3dde0-c527-3ab8-914c-6fbdc5e81e1c@web.de","threadId":"44187","inReplyTo":"57F33E12.4020900@bracey.fi","subject":"Re: [PATCH 1/3] add QSORT","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-10-04T20:31:07Z","receivedAt":"2016-10-04T20:31:19Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 04.10.2016 um 07:28 schrieb Kevin Bracey:\n> On 04/10/2016 01:00, René Scharfe wrote:\n>> Am 03.10.2016 um 19:09 schrieb Kevin Bracey:\n>>> As such, NULL checks can still be elided even with your change. If you\n>>> effectively change your example to:\n>>>\n>>>     if (nmemb > 1)\n>>>         qsort(array, nmemb, size, cmp);\n>>>     if (!array)\n>>>         printf(\"array is NULL\\n\");\n>>>\n>>> array may only be checked for NULL if nmemb <= 1. You can see GCC doing\n>>> that in the compiler explorer - it effectively turns that into \"else\n>>> if\".\n>>\n>> We don't support array == NULL together with nmemb > 1, so a segfault\n>> is to be expected in such cases, and thus NULL checks can be removed\n>> safely.\n>>\n> Possibly true in practice.\n>\n> But technically wrong by the C standard - behaviour is undefined if the\n> qsort pointer is invalid. You can't formally expect the defined\n> behaviour of a segfault when sending NULL into qsort. (Hell, maybe the\n> qsort has its own NULL check and silently returns!\n\nA qsort(3) implementation that doesn't segfault is inconvenient, but \nstill safe.  I'm more concerned about NULL checks being removed from our \ncode.\n\n> So if it's not a program error for array to be NULL and nmemb to be zero\n> in your code, and you want a diagnostic for array=NULL, nmemb non-zero,\n> I think you should put that diagnostic into sane_qsort as an assert or\n> something, not rely on qsort's undefined behaviour being a segfault.\n>\n>     sane_qsort(blah)\n>     {\n>          if (nmemb >= 1) {\n>              assert(array);\n>              qsort(array, nmemb, ...);\n>          }\n>     }\n>\n> Can't invoke undefined behaviour from NULL without triggering the\n> assert. (Could still have other invalid pointers, of course).\n\nWe could do that, but I think it's not necessary.  We'd get a segfault \nwhen accessing the sorted array anyway.  (If we don't look at the data \nafter sorting then we can get rid of the sorting step altogether.)\n\n> Usually I am on the side of \"no NULL checks\", as I make the assumption\n> that we will get a segfault as soon as NULL pointers are used, and those\n> are generally easy to diagnose. But seeing a compiler invoking this sort\n> of new trickery due to invoking undefined behaviour is making me more\n> nervous about doing so...\n\nI was shocked a bit myself when I learned about this, but let's not \npanic. :)\n\n>>> To make that check really work, you have to do:\n>>>\n>>>     if (array)\n>>>         qsort(array, nmemb, size, cmp);\n>>>     else\n>>>         printf(\"array is NULL\\n\");\n>>>\n>>> So maybe your \"sane_qsort\" should be checking array, not nmemb.\n>>\n>> It would be safe, but arguably too much so, because non-empty arrays\n>> with NULL wouldn't segfault anymore, and thus become harder to\n>> identify as the programming errors they are.\n> Well, you get the print. Although I guess you're worrying about the\n> second if being real code, not a debugging check.\n\nYes, but the optimization is valid: If nmemb > 0 then array can only be \nNULL if we have a bug, and then we'd get a segfault eventually.  So such \nchecks can be removed safely.\n\n> I must say, this is quite a courageous new optimisation from GCC. It\n> strikes me as finding a language lawyer loophole that seems to have been\n> intended for something else (mapping library functions directly onto\n> CISCy CPU intrinsics), and using it to invent a whole new optimisation\n> that seems more likely to trigger bugs than optimise any significant\n> amount of code in a desirable way.\n\nYeah, and the bugs triggered are quite obscure in this case.  But having \nricher type information and thus restricting the range of possible \nvalues for variables *can* enable useful optimizations.\n\n> Doubly weird as there's no (standard) language support for this. I don't\n> know how you'd define \"my_qsort\" that triggered the same optimisations.\n\nThe nonnull attribute is a GCC extension, but it's also supported by clang:\n\n   http://clang.llvm.org/docs/AttributeReference.html#nonnull-gnu-nonnull\n\nI don't know if other compilers support it as well, or if there are \nefforts underway to standardize it.\n\n> I've seen similar\n> library-knowledge-without-any-way-to-reproduce-in-user-code\n> optimisations like \"malloc returns a new pointer that doesn't alias with\n> anything existing\" (and no way to reproduce the optimisation with\n> my_malloc_wrapper). But those seemed to have a clear performance\n> benefit, without any obvious traps. Doubtful about this one.\n\nStill we have to deal with it..\n\nSo let's summarize; here's the effect of a raw qsort(3) call:\n\narray == NULL  nmemb  bug  QSORT  following NULL check\n-------------  -----  ---  -----  --------------------\n             0      0  no   qsort  is skipped\n             0     >0  no   qsort  is skipped\n             1      0  no   qsort  is skipped (bad!)\n             1     >0  yes  qsort  is skipped\n\nHere's what the current implementation (nmemb > 1) does:\n\narray == NULL  nmemb  bug  QSORT  following NULL check\n-------------  -----  ---  -----  --------------------\n             0      0  no   noop   is executed\n             0      1  no   noop   is executed\n             0     >1  no   qsort  is skipped\n             1      0  no   noop   is executed\n             1      1  yes  noop   is executed\n             1     >1  yes  qsort  is skipped\n\nWith the micro-optimization removed (nmemb > 0) the matrix gets simpler:\n\narray == NULL  nmemb  bug  QSORT  following NULL check\n-------------  -----  ---  -----  --------------------\n             0      0  no   noop   is executed\n             0     >0  no   qsort  is skipped\n             1      0  no   noop   is executed\n             1     >0  yes  qsort  is skipped\n\nAnd with your NULL check (array != NULL) we'd get:\n\narray == NULL  nmemb  bug  QSORT  following NULL check\n-------------  -----  ---  -----  --------------------\n             0      0  no   qsort  reuses check result\n             0     >0  no   qsort  reuses check result\n             1      0  no   noop   reuses check result\n             1     >0  yes  noop   reuses check result\n\nDid I get it right?  AFAICS all variants (except raw qsort) are safe -- \nno useful NULL checks are removed, and buggy code should be noticed by \nsegfaults in code accessing the sorted array.  So the advantage of the \ncurrent code is that it won't call qsort for nmemb <= 1.  And the \nadvantage of checking the pointer is that the result of that check can \nbe reused by later checks.  I think the former is more useful, but only \nslightly.\n\nRené\n"},{"id":"303382","messageId":"57F51577.10709@bracey.fi","threadId":"44187","inReplyTo":"29d3dde0-c527-3ab8-914c-6fbdc5e81e1c@web.de","subject":"Re: [PATCH 1/3] add QSORT","fromName":"Kevin Bracey","fromEmail":"kevin@bracey.fi","sentAt":"2016-10-05T15:00:07Z","receivedAt":"2016-10-05T16:16:30Z","isPatch":true,"sender":{"key":"kevin@bracey.fi","avatar":"https://avatars.githubusercontent.com/u/96079793?v=4"},"body":"On 04/10/2016 23:31, René Scharfe wrote:\n\n>\n> So let's summarize; here's the effect of a raw qsort(3) call:\n>\n> array == NULL  nmemb  bug  QSORT  following NULL check\n> -------------  -----  ---  -----  --------------------\n>             0      0  no   qsort  is skipped\n>             0     >0  no   qsort  is skipped\n>             1      0  no   qsort  is skipped (bad!) ******\n>             1     >0  yes  qsort  is skipped ******\n>\nRight - row 3 may not be a bug from the point of view of your internals, \nbut it means you violate the API of qsort.Therefore a fix is required.\n\n> With the micro-optimization removed (nmemb > 0) the matrix gets simpler:\n>\n> array == NULL  nmemb  bug  QSORT  following NULL check\n> -------------  -----  ---  -----  --------------------\n>             0      0  no   noop   is executed\n>             0     >0  no   qsort  is skipped\n>             1      0  no   noop   is executed\n>             1     >0  yes  qsort  is skipped ******\n>\n> And with your NULL check (array != NULL) we'd get:\n>\n> array == NULL  nmemb  bug  QSORT  following NULL check\n> -------------  -----  ---  -----  --------------------\n>             0      0  no   qsort  reuses check result\n>             0     >0  no   qsort  reuses check result\n>             1      0  no   noop   reuses check result\n>             1     >0  yes  noop   reuses check result\n>\n> Did I get it right?  AFAICS all variants (except raw qsort) are safe \n> -- no useful NULL checks are removed, and buggy code should be noticed \n> by segfaults in code accessing the sorted array.\nI think your tables are correct.\n\nBut I disagree that you could ever call invoking the \"****\" lines safe. \nUnless you have documentation on what limit GCC (and your other \ncompilers) are prepared to put on the undefined behaviour of violating \nthat \"non-null\" constraint.\n\nUp to now dereferencing a null pointer has been implicitly (or \nexplicitly?) defined as simply generating SIGSEGV. And that has \nnaturally extended into NULL passed to library implementations. But \nthat's no longer true - it seems bets are somewhat off.\n\nBut, as long as you are confident you never invoke that line without a \nprogram bug - ie an API precondition of your own QSORT is that NULL is \nlegal iff nmemb is zero, then I guess it's fine. Behaviour is defined, \nas long as you don't violate your internal preconditions.\n\nKevin\n\n\n"}]}