Adding string_list_sort_u to replace combined calls of string_list_sort and string_list_remove_duplicates calls.
cover Adding string_list_sort_u to replace combined calls of string_list_sort and string_list_remove_duplicates calls.
Following up with Junio's suggestion in
https://lore.kernel.org/git/[email protected]/, calls to string_list_remove_duplicates are almost always preceeded by string_list_sort which can be coupled into a single method.
There are places, for example the call of string_list_remove_duplicates in pack-objects.c where removal of that line causes no test failures, however removal of string_list_sort_u version did because removing sort is a more catchable behaviour by the current tests, this might improve the case where we were unsure why removing string_list_remove_duplicates caused no test failures.
I was unable to write unit tests for this new method in this RFC PATCH since I was quite unsure why no unit tests were present for string_list_sort and string_list_insert.
Amisha Chhajed (2):
Adding string_list_sort_u which sorts a list then deduplicates it. Replacing calls of string_list_sort and string_list_remove_duplicates
with the combined variant string_list_u.
builtin/clone.c | 3 +-- builtin/fast-export.c | 3 +-- builtin/pack-objects.c | 6 ++---- builtin/sparse-checkout.c | 6 ++---- help.c | 3 +-- notes.c | 3 +-- string-list.c | 6 ++++++ string-list.h | 6 ++++++ 8 files changed, 20 insertions(+), 16 deletions(-)
Signature · 1 line
2.51.0
RFC PATCH 1/2 Adding string_list_sort_u which sorts a list then deduplicates it.
string_list_remove_duplicates is almost always preceeded by string_list_sort, hence adding string_list_sort_u which dedupliactes post sorting.
--- string-list.c | 6 ++++++ string-list.h | 6 ++++++ 2 files changed, 12 insertions(+)
string-list.c +6 -0
@@ -247,6 +247,12 @@ void string_list_sort(struct string_list *list)QSORT_S (list->items, list->nr, cmp_items, &sort_ctx); } +void string_list_sort_u (struct string_list *list,int free_util) +{ +string_list_sort (list); +string_list_remove_duplicates (list, free_util); +} +struct string_list_item *unsorted_string_list_lookup (struct string_list *list,const char *string) {
string-list.h +6 -0
@@ -239,6 +239,12 @@ struct string_list_item *string_list_append_nodup(struct string_list *list, char*/ void string_list_sort (struct string_list *list); +/** +* Sort the list and then remove duplicate entries. If free_util is true, +* call free() on the util members of any items that have to be deleted. +*/ +void string_list_sort_u (struct string_list *list,int free_util); +/** * Like `string_list_has_string()` but for unsorted lists. Linear in * size of the list.
Signature · 1 line
2.51.0
Re: [RFC PATCH 1/2] Adding string_list_sort_u which sorts a list then deduplicates it.
Quoted 3 lines · Amisha Chhajed
string_list_remove_duplicatesis almost always preceeded bystring_list_sort, hence addingstring_list_sort_uwhich dedupliactes post sorting.
The usual way to compose a log message of this project is to
- Give an observation on how the current system works in the present tense (so no need to say "Currently X is Y", or "Previously X was Y" to describe the state before your change; just "X is Y" is enough), and discuss what you perceive as a problem in it.
- Propose a solution (optional---often, problem description trivially leads to an obvious solution in reader's minds).
- Give commands to somebody editing the codebase to "make it so", instead of saying "This commit does X".
in this order.
To those who have been intimately following the discussion, it often is understandable without some of the above, but we are not writing for those who review the patches. We are primarily writing for future readers of "git log" who are not aware of the review discussion we have on list, so we should give something to prepare them by setting the stage and stating the objective first, before going into how the patch solved it.
With that in mind, perhaps something along this line ...
Subject: string-list: add string_list_sort_u() that mimics "sort -u"
Many callsites of string_list_remove_duplicates() call it immediately after calling string_list_sort(). It is understandable because the former requires the string-list to be sorted, but at the same time, it is clear that these places are sorting only to remove duplicates and for no other reason.
Introduce a helper function string_list_sort_u() that combines these two calls that often appear together, to help simplify these callsites.
... probably?
The same comment applies to the way the other patch is explained.
Thanks.
Re: [RFC PATCH 1/2] Adding string_list_sort_u which sorts a list then deduplicates it.
Quoted 46 lines · Junio C Hamano
Quoted 3 lines · Amisha Chhajed
string_list_remove_duplicatesis almost always preceeded bystring_list_sort, hence addingstring_list_sort_uwhich dedupliactes post sorting.The usual way to compose a log message of this project is to
- Give an observation on how the current system works in the present tense (so no need to say "Currently X is Y", or "Previously X was Y" to describe the state before your change; just "X is Y" is enough), and discuss what you perceive as a problem in it.
- Propose a solution (optional---often, problem description trivially leads to an obvious solution in reader's minds).
- Give commands to somebody editing the codebase to "make it so", instead of saying "This commit does X".
in this order.
To those who have been intimately following the discussion, it often is understandable without some of the above, but we are not writing for those who review the patches. We are primarily writing for future readers of "git log" who are not aware of the review discussion we have on list, so we should give something to prepare them by setting the stage and stating the objective first, before going into how the patch solved it.
With that in mind, perhaps something along this line ...
Subject: string-list: add
string_list_sort_u()that mimics "sort -u"Many callsites of
string_list_remove_duplicates()call it immediately after callingstring_list_sort(). It is understandable because the former requires the string-list to be sorted, but at the same time, it is clear that these places are sorting only to remove duplicates and for no other reason.Introduce a helper function
string_list_sort_u()that combines these two calls that often appear together, to help simplify these callsites.
Quoted 6 lines
... probably?
The same comment applies to the way the other patch is explained.
Thanks.
Very helpful, thank you so much, i will keep in mind.
PATCH 1/2 u-string-list: add unit tests for string-list methods
In reply to Amisha ChhajedUnit tests in u-string-list.c does not cover several methods in string-list, this gap in coverage makes it difficult to ensure no regressions are introduced in future changes.
Add unit tests for the following methods to enhance coverage:string_list_remove_empty_items() unsorted_string_list_has_string() unsorted_string_list_delete_item() string_list_has_string()string_list_insert()string_list_sort()string_list_remove()
--- t/unit-tests/u-string-list.c | 197 +++++++++++++++++++++++++++++++++++ 1 file changed, 197 insertions(+)
t/unit-tests/u-string-list.c +197 -0
@@ -243,6 +243,133 @@ void test_string_list__filter(void)t_string_list_clear (&list,0 ); } +static void t_string_list_has_string (struct string_list *list,const char *string,int expected) +{ +int has_string =string_list_has_string (list, string); +cl_assert_equal_i (has_string, expected); +} + +void test_string_list__has_string (void ) +{ +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&list,0 ,NULL ); +t_string_list_has_string (&list,"" ,0 ); + +t_create_string_list_dup (&list,0 ,"a" ,"b" ,"c" ,NULL ); +t_string_list_has_string (&list,"a" ,1 ); +t_string_list_has_string (&list,"b" ,1 ); +t_string_list_has_string (&list,"c" ,1 ); +t_string_list_has_string (&list,"d" ,0 ); + +t_string_list_clear (&list,0 ); +} + +static void t_string_list_insert (struct string_list *expected_strings, ...) +{ +struct string_list strings_to_insert =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; +va_list ap; + +va_start (ap, expected_strings); +t_vcreate_string_list_dup (&strings_to_insert,0 , ap); +va_end (ap); + +for (int i =0 ; i < strings_to_insert.nr; i++) { +string_list_insert (&list, strings_to_insert.items[i].string); + } + +t_string_list_equal (&list, expected_strings); + +string_list_clear (&strings_to_insert,0 ); +string_list_clear (&list,0 ); +} + +void test_string_list__insert (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_string_list_insert (&expected_strings,NULL ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,NULL ); +t_string_list_insert (&expected_strings,"b" ,"a" ,"a" ,"b" ,NULL ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,"c" ,NULL ); +t_string_list_insert (&expected_strings,"c" ,"b" ,"a" ,"c" ,"b" ,NULL ); + +t_create_string_list_dup (&expected_strings,0 ,"" ,"a" ,NULL ); +t_string_list_insert (&expected_strings,"a" ,"a" ,"a" ,"" ,NULL ); + +t_string_list_clear (&expected_strings,0 ); +} + +static void t_string_list_sort (struct string_list *list, ...) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +va_list ap; + +va_start (ap, list); +t_vcreate_string_list_dup (&expected_strings,0 , ap); +va_end (ap); + +string_list_sort (list); +t_string_list_equal (list, &expected_strings); + +string_list_clear (&expected_strings,0 ); +} + +void test_string_list__sort (void ) +{ +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&list,0 ,NULL ); +t_string_list_sort (&list,NULL ); + +t_create_string_list_dup (&list,0 ,"b" ,"" ,"a" ,NULL ); +t_string_list_sort (&list,"" ,"a" ,"b" ,NULL ); + +t_create_string_list_dup (&list,0 ,"c" ,"a" ,"b" ,"a" ,NULL ); +t_string_list_sort (&list,"a" ,"a" ,"b" ,"c" ,NULL ); + +t_string_list_clear (&list,0 ); +} + +static void t_string_list_remove (struct string_list *expected_strings,struct string_list *list,char const *str) +{ +string_list_remove (list, str,0 ); +t_string_list_equal (list, expected_strings); +} + +void test_string_list__remove (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_create_string_list_dup (&list,0 ,NULL ); +t_string_list_remove (&expected_strings, &list,"" ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"a" ,NULL ); +t_string_list_remove (&expected_strings, &list,"a" ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,"b" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"b" ,"b" ,"c" ,NULL ); +t_string_list_remove (&expected_strings, &list,"c" ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,"d" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"b" ,"c" ,"d" ,NULL ); +t_string_list_remove (&expected_strings, &list,"c" ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,"c" ,"d" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"b" ,"c" ,"d" ,NULL ); +t_string_list_remove (&expected_strings, &list,"e" ); + +t_string_list_clear (&expected_strings,0 ); +t_string_list_clear (&list,0 ); +} +static void t_string_list_remove_duplicates (struct string_list *list, ...) {struct string_list expected_strings =STRING_LIST_INIT_DUP ;
@@ -304,3 +431,73 @@ void test_string_list__remove_duplicates(void)t_string_list_clear (&list,0 ); } + +static void t_string_list_remove_empty_items (struct string_list *expected_strings,struct string_list *list) +{ +string_list_remove_empty_items (list,0 ); +t_string_list_equal (list, expected_strings); +} + +void test_string_list__remove_empty_items (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_create_string_list_dup (&list,0 ,"" ,"" ,"" ,NULL ); +t_string_list_remove_empty_items (&expected_strings, &list); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"" ,"b" ,"" ,NULL ); +t_string_list_remove_empty_items (&expected_strings, &list); + +t_string_list_clear (&expected_strings,0 ); +t_string_list_clear (&list,0 ); +} + +static void t_string_list_unsorted_string_list_has_string (struct string_list *list,const char *str,int expected) +{ +int has_string =unsorted_string_list_has_string (list, str); +cl_assert_equal_i (has_string, expected); +} + +void test_string_list__unsorted_string_list_has_string (void ) +{ +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&list,0 ,"b" ,"d" ,"a" ,NULL ); +t_string_list_unsorted_string_list_has_string (&list,"a" ,1 ); +t_string_list_unsorted_string_list_has_string (&list,"b" ,1 ); +t_string_list_unsorted_string_list_has_string (&list,"c" ,0 ); +t_string_list_unsorted_string_list_has_string (&list,"d" ,1 ); + +t_string_list_clear (&list,0 ); +} + +static void t_string_list_unsorted_string_list_delete_item (struct string_list *expected_list,struct string_list *list,int i) +{ +unsorted_string_list_delete_item (list, i,0 ); + +t_string_list_equal (list, expected_list); +} + +void test_string_list__unsorted_string_list_delete_item (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"c" ,"b" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"d" ,"b" ,"c" ,NULL ); +t_string_list_unsorted_string_list_delete_item (&expected_strings, &list,1 ); + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_create_string_list_dup (&list,0 ,"" ,NULL ); +t_string_list_unsorted_string_list_delete_item (&expected_strings, &list,0 ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"d" ,"c" ,"b" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"d" ,"c" ,"b" ,"d" ,NULL ); +t_string_list_unsorted_string_list_delete_item (&expected_strings, &list,4 ); + +t_string_list_clear (&expected_strings,0 ); +t_string_list_clear (&list,0 ); +}
Signature · 1 line
2.51.0
PATCH 2/2 string-list: add string_list_sort_u() that mimics "sort -u"
Many callsites of string_list_remove_duplicates() call it immdediately after calling string_list_sort(), understandably as the former requires string-list to be sorted, it is clear that these places are sorting only to remove duplicates and for no other reason.
Introduce a helper function string_list_sort_u that combines these two calls that often appear together, to simplify these callsites. Replace the current calls of those methods with string_list_sort_u().
--- builtin/clone.c | 3 +-- builtin/fast-export.c | 3 +-- builtin/pack-objects.c | 6 ++---- builtin/sparse-checkout.c | 6 ++---- help.c | 3 +-- notes.c | 3 +-- string-list.c | 6 ++++++ string-list.h | 6 ++++++ t/unit-tests/u-string-list.c | 34 ++++++++++++++++++++++++++++++++++ 9 files changed, 54 insertions(+), 16 deletions(-)
builtin/clone.c +1 -2
@@ -1136,8 +1136,7 @@ int cmd_clone(int argc,int val;/* remove duplicates */ -string_list_sort (&option_recurse_submodules); -string_list_remove_duplicates (&option_recurse_submodules,0 ); +string_list_sort_u (&option_recurse_submodules,0 );/* * NEEDSWORK: In a multi-working-tree world, this needs to be
builtin/fast-export.c +1 -2
@@ -1118,8 +1118,7 @@ static void get_tags_and_duplicates(struct rev_cmdline_info *info)free (full_name); } -string_list_sort (&extra_refs); -string_list_remove_duplicates (&extra_refs,0 ); +string_list_sort_u (&extra_refs,0 ); }static void handle_tags_and_duplicates (struct string_list *extras)
builtin/pack-objects.c +2 -4
@@ -3849,10 +3849,8 @@ static void read_packs_list_from_stdin(struct rev_info *revs)strbuf_reset (&buf); } -string_list_sort (&include_packs); -string_list_remove_duplicates (&include_packs,0 ); -string_list_sort (&exclude_packs); -string_list_remove_duplicates (&exclude_packs,0 ); +string_list_sort_u (&include_packs,0 ); +string_list_sort_u (&exclude_packs,0 );repo_for_each_pack (the_repository, p) {const char *pack_name =pack_basename (p);
builtin/sparse-checkout.c +2 -4
@@ -292,8 +292,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)string_list_insert (&sl, pe->pattern); } -string_list_sort (&sl); -string_list_remove_duplicates (&sl,0 ); +string_list_sort_u (&sl,0 );fprintf (fp,"/*\n!/*/\n" );
@@ -316,8 +315,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)strbuf_release (&parent_pattern); -string_list_sort (&sl); -string_list_remove_duplicates (&sl,0 ); +string_list_sort_u (&sl,0 );for (i =0 ; i < sl.nr; i++) {char *pattern =escaped_pattern (sl.items[i].string);
help.c +1 -2
@@ -420,8 +420,7 @@ void list_cmds_by_config(struct string_list *list)if (repo_config_get_string_tmp (the_repository,"completion.commands" , &cmd_list))return ; -string_list_sort (list); -string_list_remove_duplicates (list,0 ); +string_list_sort_u (list,0 );while (*cmd_list) {struct strbuf sb =STRBUF_INIT ;
notes.c +1 -2
@@ -921,8 +921,7 @@ int combine_notes_cat_sort_uniq(struct object_id *cur_oid,if (string_list_add_note_lines (&sort_uniq_list, new_oid)) goto out;string_list_remove_empty_items (&sort_uniq_list,0 ); -string_list_sort (&sort_uniq_list); -string_list_remove_duplicates (&sort_uniq_list,0 ); +string_list_sort_u (&sort_uniq_list,0 );/* create a new blob object from sort_uniq_list */ if (for_each_string_list(&sort_uniq_list,
string-list.c +6 -0
@@ -247,6 +247,12 @@ void string_list_sort(struct string_list *list)QSORT_S (list->items, list->nr, cmp_items, &sort_ctx); } +void string_list_sort_u (struct string_list *list,int free_util) +{ +string_list_sort (list); +string_list_remove_duplicates (list, free_util); +} +struct string_list_item *unsorted_string_list_lookup (struct string_list *list,const char *string) {
string-list.h +6 -0
@@ -239,6 +239,12 @@ struct string_list_item *string_list_append_nodup(struct string_list *list, char*/ void string_list_sort (struct string_list *list); +/** +* Sort the list and then remove duplicate entries. If free_util is true, +* call free() on the util members of any items that have to be deleted. +*/ +void string_list_sort_u (struct string_list *list,int free_util); +/** * Like `string_list_has_string()` but for unsorted lists. Linear in * size of the list.
t/unit-tests/u-string-list.c +34 -0
@@ -432,6 +432,40 @@ void test_string_list__remove_duplicates(void)t_string_list_clear (&list,0 ); } +static void t_string_list_sort_u (struct string_list *list, ...) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +va_list ap; + +va_start (ap, list); +t_vcreate_string_list_dup (&expected_strings,0 , ap); +va_end (ap); + +string_list_sort_u (list,0 ); +t_string_list_equal (list, &expected_strings); + +string_list_clear (&expected_strings,0 ); +} + +void test_string_list__sort_u (void ) +{ +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&list,0 ,NULL ); +t_string_list_sort_u (&list,NULL ); + +t_create_string_list_dup (&list,0 ,"" ,"" ,"" ,"" ,NULL ); +t_string_list_sort_u (&list,"" ,NULL ); + +t_create_string_list_dup (&list,0 ,"b" ,"a" ,"a" ,"" ,NULL ); +t_string_list_sort_u (&list,"" ,"a" ,"b" ,NULL ); + +t_create_string_list_dup (&list,0 ,"b" ,"a" ,"a" ,"d" ,"c" ,"c" ,NULL ); +t_string_list_sort_u (&list,"a" ,"b" ,"c" ,"d" ,NULL ); + +t_string_list_clear (&list,0 ); +} +static void t_string_list_remove_empty_items (struct string_list *expected_strings,struct string_list *list) {string_list_remove_empty_items (list,0 );
Signature · 1 line
2.51.0
PATCH v3 1/2 u-string-list: add unit tests for string-list methods
Unit tests in u-string-list.c does not cover several methods in string-list, this gap in coverage makes it difficult to ensure no regressions are introduced in future changes.
Add unit tests for the following methods to enhance coverage:string_list_remove_empty_items() unsorted_string_list_has_string() unsorted_string_list_delete_item() string_list_has_string()string_list_insert()string_list_sort()string_list_remove()
--- t/unit-tests/u-string-list.c | 209 +++++++++++++++++++++++++++++++++++ 1 file changed, 209 insertions(+)
t/unit-tests/u-string-list.c +209 -0
@@ -243,6 +243,138 @@ void test_string_list__filter(void)t_string_list_clear (&list,0 ); } +static void t_string_list_has_string ( +struct string_list *list, +const char *string, +int expected) +{ +int has_string =string_list_has_string (list, string); +cl_assert_equal_i (has_string, expected); +} + +void test_string_list__has_string (void ) +{ +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&list,0 ,NULL ); +t_string_list_has_string (&list,"" ,0 ); + +t_create_string_list_dup (&list,0 ,"a" ,"b" ,"c" ,NULL ); +t_string_list_has_string (&list,"a" ,1 ); +t_string_list_has_string (&list,"b" ,1 ); +t_string_list_has_string (&list,"c" ,1 ); +t_string_list_has_string (&list,"d" ,0 ); + +t_string_list_clear (&list,0 ); +} + +static void t_string_list_insert (struct string_list *expected_strings, ...) +{ +struct string_list strings_to_insert =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; +va_list ap; + +va_start (ap, expected_strings); +t_vcreate_string_list_dup (&strings_to_insert,0 , ap); +va_end (ap); + +for (size_t i =0 ; i < strings_to_insert.nr; i++) +string_list_insert (&list, strings_to_insert.items[i].string); + +t_string_list_equal (&list, expected_strings); + +string_list_clear (&strings_to_insert,0 ); +string_list_clear (&list,0 ); +} + +void test_string_list__insert (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_string_list_insert (&expected_strings,NULL ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,NULL ); +t_string_list_insert (&expected_strings,"b" ,"a" ,"a" ,"b" ,NULL ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,"c" ,NULL ); +t_string_list_insert (&expected_strings,"c" ,"b" ,"a" ,"c" ,"b" ,NULL ); + +t_create_string_list_dup (&expected_strings,0 ,"" ,"a" ,NULL ); +t_string_list_insert (&expected_strings,"a" ,"a" ,"a" ,"" ,NULL ); + +t_string_list_clear (&expected_strings,0 ); +} + +static void t_string_list_sort (struct string_list *list, ...) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +va_list ap; + +va_start (ap, list); +t_vcreate_string_list_dup (&expected_strings,0 , ap); +va_end (ap); + +string_list_sort (list); +t_string_list_equal (list, &expected_strings); + +string_list_clear (&expected_strings,0 ); +} + +void test_string_list__sort (void ) +{ +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&list,0 ,NULL ); +t_string_list_sort (&list,NULL ); + +t_create_string_list_dup (&list,0 ,"b" ,"" ,"a" ,NULL ); +t_string_list_sort (&list,"" ,"a" ,"b" ,NULL ); + +t_create_string_list_dup (&list,0 ,"c" ,"a" ,"b" ,"a" ,NULL ); +t_string_list_sort (&list,"a" ,"a" ,"b" ,"c" ,NULL ); + +t_string_list_clear (&list,0 ); +} + +static void t_string_list_remove ( +struct string_list *expected_strings, +struct string_list *list, +char const *str) +{ +string_list_remove (list, str,0 ); +t_string_list_equal (list, expected_strings); +} + +void test_string_list__remove (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_create_string_list_dup (&list,0 ,NULL ); +t_string_list_remove (&expected_strings, &list,"" ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"a" ,NULL ); +t_string_list_remove (&expected_strings, &list,"a" ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,"b" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"b" ,"b" ,"c" ,NULL ); +t_string_list_remove (&expected_strings, &list,"c" ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,"d" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"b" ,"c" ,"d" ,NULL ); +t_string_list_remove (&expected_strings, &list,"c" ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,"c" ,"d" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"b" ,"c" ,"d" ,NULL ); +t_string_list_remove (&expected_strings, &list,"e" ); + +t_string_list_clear (&expected_strings,0 ); +t_string_list_clear (&list,0 ); +} +static void t_string_list_remove_duplicates (struct string_list *list, ...) {struct string_list expected_strings =STRING_LIST_INIT_DUP ;
@@ -304,3 +436,80 @@ void test_string_list__remove_duplicates(void)t_string_list_clear (&list,0 ); } + +static void t_string_list_remove_empty_items ( +struct string_list *expected_strings, +struct string_list *list) +{ +string_list_remove_empty_items (list,0 ); +t_string_list_equal (list, expected_strings); +} + +void test_string_list__remove_empty_items (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_create_string_list_dup (&list,0 ,"" ,"" ,"" ,NULL ); +t_string_list_remove_empty_items (&expected_strings, &list); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"" ,"b" ,"" ,NULL ); +t_string_list_remove_empty_items (&expected_strings, &list); + +t_string_list_clear (&expected_strings,0 ); +t_string_list_clear (&list,0 ); +} + +static void t_string_list_unsorted_string_list_has_string ( +struct string_list *list, +const char *str,int expected) +{ +int has_string =unsorted_string_list_has_string (list, str); +cl_assert_equal_i (has_string, expected); +} + +void test_string_list__unsorted_string_list_has_string (void ) +{ +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&list,0 ,"b" ,"d" ,"a" ,NULL ); +t_string_list_unsorted_string_list_has_string (&list,"a" ,1 ); +t_string_list_unsorted_string_list_has_string (&list,"b" ,1 ); +t_string_list_unsorted_string_list_has_string (&list,"c" ,0 ); +t_string_list_unsorted_string_list_has_string (&list,"d" ,1 ); + +t_string_list_clear (&list,0 ); +} + +static void t_string_list_unsorted_string_list_delete_item ( +struct string_list *expected_list, +struct string_list *list, +int i) +{ +unsorted_string_list_delete_item (list, i,0 ); + +t_string_list_equal (list, expected_list); +} + +void test_string_list__unsorted_string_list_delete_item (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"c" ,"b" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"d" ,"b" ,"c" ,NULL ); +t_string_list_unsorted_string_list_delete_item (&expected_strings, &list,1 ); + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_create_string_list_dup (&list,0 ,"" ,NULL ); +t_string_list_unsorted_string_list_delete_item (&expected_strings, &list,0 ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"d" ,"c" ,"b" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"d" ,"c" ,"b" ,"d" ,NULL ); +t_string_list_unsorted_string_list_delete_item (&expected_strings, &list,4 ); + +t_string_list_clear (&expected_strings,0 ); +t_string_list_clear (&list,0 ); +}
Signature · 1 line
2.51.0
PATCH v3 2/2 string-list: add string_list_sort_u() that mimics "sort -u"
Many callsites of string_list_remove_duplicates() call it immdediately after calling string_list_sort(), understandably as the former requires string-list to be sorted, it is clear that these places are sorting only to remove duplicates and for no other reason.
Introduce a helper function string_list_sort_u that combines these two calls that often appear together, to simplify these callsites. Replace the current calls of those methods with string_list_sort_u().
--- builtin/clone.c | 3 +-- builtin/fast-export.c | 3 +-- builtin/pack-objects.c | 6 ++---- builtin/sparse-checkout.c | 6 ++---- help.c | 3 +-- notes.c | 3 +-- string-list.c | 6 ++++++ string-list.h | 6 ++++++ t/unit-tests/u-string-list.c | 34 ++++++++++++++++++++++++++++++++++ 9 files changed, 54 insertions(+), 16 deletions(-)
builtin/clone.c +1 -2
@@ -1136,8 +1136,7 @@ int cmd_clone(int argc,int val;/* remove duplicates */ -string_list_sort (&option_recurse_submodules); -string_list_remove_duplicates (&option_recurse_submodules,0 ); +string_list_sort_u (&option_recurse_submodules,0 );/* * NEEDSWORK: In a multi-working-tree world, this needs to be
builtin/fast-export.c +1 -2
@@ -1118,8 +1118,7 @@ static void get_tags_and_duplicates(struct rev_cmdline_info *info)free (full_name); } -string_list_sort (&extra_refs); -string_list_remove_duplicates (&extra_refs,0 ); +string_list_sort_u (&extra_refs,0 ); }static void handle_tags_and_duplicates (struct string_list *extras)
builtin/pack-objects.c +2 -4
@@ -3849,10 +3849,8 @@ static void read_packs_list_from_stdin(struct rev_info *revs)strbuf_reset (&buf); } -string_list_sort (&include_packs); -string_list_remove_duplicates (&include_packs,0 ); -string_list_sort (&exclude_packs); -string_list_remove_duplicates (&exclude_packs,0 ); +string_list_sort_u (&include_packs,0 ); +string_list_sort_u (&exclude_packs,0 );repo_for_each_pack (the_repository, p) {const char *pack_name =pack_basename (p);
builtin/sparse-checkout.c +2 -4
@@ -292,8 +292,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)string_list_insert (&sl, pe->pattern); } -string_list_sort (&sl); -string_list_remove_duplicates (&sl,0 ); +string_list_sort_u (&sl,0 );fprintf (fp,"/*\n!/*/\n" );
@@ -316,8 +315,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)strbuf_release (&parent_pattern); -string_list_sort (&sl); -string_list_remove_duplicates (&sl,0 ); +string_list_sort_u (&sl,0 );for (i =0 ; i < sl.nr; i++) {char *pattern =escaped_pattern (sl.items[i].string);
help.c +1 -2
@@ -420,8 +420,7 @@ void list_cmds_by_config(struct string_list *list)if (repo_config_get_string_tmp (the_repository,"completion.commands" , &cmd_list))return ; -string_list_sort (list); -string_list_remove_duplicates (list,0 ); +string_list_sort_u (list,0 );while (*cmd_list) {struct strbuf sb =STRBUF_INIT ;
notes.c +1 -2
@@ -921,8 +921,7 @@ int combine_notes_cat_sort_uniq(struct object_id *cur_oid,if (string_list_add_note_lines (&sort_uniq_list, new_oid)) goto out;string_list_remove_empty_items (&sort_uniq_list,0 ); -string_list_sort (&sort_uniq_list); -string_list_remove_duplicates (&sort_uniq_list,0 ); +string_list_sort_u (&sort_uniq_list,0 );/* create a new blob object from sort_uniq_list */ if (for_each_string_list(&sort_uniq_list,
string-list.c +6 -0
@@ -247,6 +247,12 @@ void string_list_sort(struct string_list *list)QSORT_S (list->items, list->nr, cmp_items, &sort_ctx); } +void string_list_sort_u (struct string_list *list,int free_util) +{ +string_list_sort (list); +string_list_remove_duplicates (list, free_util); +} +struct string_list_item *unsorted_string_list_lookup (struct string_list *list,const char *string) {
string-list.h +6 -0
@@ -239,6 +239,12 @@ struct string_list_item *string_list_append_nodup(struct string_list *list, char*/ void string_list_sort (struct string_list *list); +/** +* Sort the list and then remove duplicate entries. If free_util is true, +* call free() on the util members of any items that have to be deleted. +*/ +void string_list_sort_u (struct string_list *list,int free_util); +/** * Like `string_list_has_string()` but for unsorted lists. Linear in * size of the list.
t/unit-tests/u-string-list.c +34 -0
@@ -437,6 +437,40 @@ void test_string_list__remove_duplicates(void)t_string_list_clear (&list,0 ); } +static void t_string_list_sort_u (struct string_list *list, ...) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +va_list ap; + +va_start (ap, list); +t_vcreate_string_list_dup (&expected_strings,0 , ap); +va_end (ap); + +string_list_sort_u (list,0 ); +t_string_list_equal (list, &expected_strings); + +string_list_clear (&expected_strings,0 ); +} + +void test_string_list__sort_u (void ) +{ +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&list,0 ,NULL ); +t_string_list_sort_u (&list,NULL ); + +t_create_string_list_dup (&list,0 ,"" ,"" ,"" ,"" ,NULL ); +t_string_list_sort_u (&list,"" ,NULL ); + +t_create_string_list_dup (&list,0 ,"b" ,"a" ,"a" ,"" ,NULL ); +t_string_list_sort_u (&list,"" ,"a" ,"b" ,NULL ); + +t_create_string_list_dup (&list,0 ,"b" ,"a" ,"a" ,"d" ,"c" ,"c" ,NULL ); +t_string_list_sort_u (&list,"a" ,"b" ,"c" ,"d" ,NULL ); + +t_string_list_clear (&list,0 ); +} +static void t_string_list_remove_empty_items (struct string_list *expected_strings,struct string_list *list)
Signature · 1 line
2.51.0
Re: [PATCH v3 1/2] u-string-list: add unit tests for string-list methods
In reply to Amisha ChhajedQuoted 244 lines · Amisha Chhajed
Unit tests in
u-string-list.cdoes not cover several methods in string-list, this gap in coverage makes it difficult to ensure no regressions are introduced in future changes.Add unit tests for the following methods to enhance coverage:
string_list_remove_empty_items()unsorted_string_list_has_string()unsorted_string_list_delete_item()string_list_has_string()string_list_insert()string_list_sort()string_list_remove()Signed-off-by Amisha Chhajed <[email protected]>--- t/unit-tests/u-string-list.c | 209 +++++++++++++++++++++++++++++++++++ 1 file changed, 209 insertions(+)t/unit-tests/u-string-list.c +209
-1@@ -243,6 +243,138 @@ void test_string_list__filter(void)t_string_list_clear (&list,0 ); } +static void t_string_list_has_string ( +struct string_list *list, +const char *string, +int expected) +{ +int has_string =string_list_has_string (list, string); +cl_assert_equal_i (has_string, expected); +} + +void test_string_list__has_string (void ) +{ +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&list,0 ,NULL ); +t_string_list_has_string (&list,"" ,0 ); + +t_create_string_list_dup (&list,0 ,"a" ,"b" ,"c" ,NULL ); +t_string_list_has_string (&list,"a" ,1 ); +t_string_list_has_string (&list,"b" ,1 ); +t_string_list_has_string (&list,"c" ,1 ); +t_string_list_has_string (&list,"d" ,0 ); + +t_string_list_clear (&list,0 ); +} + +static void t_string_list_insert (struct string_list *expected_strings, ...) +{ +struct string_list strings_to_insert =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; +va_list ap; + +va_start (ap, expected_strings); +t_vcreate_string_list_dup (&strings_to_insert,0 , ap); +va_end (ap); + +for (size_t i =0 ; i < strings_to_insert.nr; i++) +string_list_insert (&list, strings_to_insert.items[i].string); + +t_string_list_equal (&list, expected_strings); + +string_list_clear (&strings_to_insert,0 ); +string_list_clear (&list,0 ); +} + +void test_string_list__insert (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_string_list_insert (&expected_strings,NULL ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,NULL ); +t_string_list_insert (&expected_strings,"b" ,"a" ,"a" ,"b" ,NULL ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,"c" ,NULL ); +t_string_list_insert (&expected_strings,"c" ,"b" ,"a" ,"c" ,"b" ,NULL ); + +t_create_string_list_dup (&expected_strings,0 ,"" ,"a" ,NULL ); +t_string_list_insert (&expected_strings,"a" ,"a" ,"a" ,"" ,NULL ); + +t_string_list_clear (&expected_strings,0 ); +} + +static void t_string_list_sort (struct string_list *list, ...) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +va_list ap; + +va_start (ap, list); +t_vcreate_string_list_dup (&expected_strings,0 , ap); +va_end (ap); + +string_list_sort (list); +t_string_list_equal (list, &expected_strings); + +string_list_clear (&expected_strings,0 ); +} + +void test_string_list__sort (void ) +{ +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&list,0 ,NULL ); +t_string_list_sort (&list,NULL ); + +t_create_string_list_dup (&list,0 ,"b" ,"" ,"a" ,NULL ); +t_string_list_sort (&list,"" ,"a" ,"b" ,NULL ); + +t_create_string_list_dup (&list,0 ,"c" ,"a" ,"b" ,"a" ,NULL ); +t_string_list_sort (&list,"a" ,"a" ,"b" ,"c" ,NULL ); + +t_string_list_clear (&list,0 ); +} + +static void t_string_list_remove ( +struct string_list *expected_strings, +struct string_list *list, +char const *str) +{ +string_list_remove (list, str,0 ); +t_string_list_equal (list, expected_strings); +} + +void test_string_list__remove (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_create_string_list_dup (&list,0 ,NULL ); +t_string_list_remove (&expected_strings, &list,"" ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"a" ,NULL ); +t_string_list_remove (&expected_strings, &list,"a" ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,"b" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"b" ,"b" ,"c" ,NULL ); +t_string_list_remove (&expected_strings, &list,"c" ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,"d" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"b" ,"c" ,"d" ,NULL ); +t_string_list_remove (&expected_strings, &list,"c" ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,"c" ,"d" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"b" ,"c" ,"d" ,NULL ); +t_string_list_remove (&expected_strings, &list,"e" ); + +t_string_list_clear (&expected_strings,0 ); +t_string_list_clear (&list,0 ); +} +static void t_string_list_remove_duplicates (struct string_list *list, ...) {struct string_list expected_strings =STRING_LIST_INIT_DUP ;@@ -304,3 +436,80 @@ void test_string_list__remove_duplicates(void)t_string_list_clear (&list,0 ); } + +static void t_string_list_remove_empty_items ( +struct string_list *expected_strings, +struct string_list *list) +{ +string_list_remove_empty_items (list,0 ); +t_string_list_equal (list, expected_strings); +} + +void test_string_list__remove_empty_items (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_create_string_list_dup (&list,0 ,"" ,"" ,"" ,NULL ); +t_string_list_remove_empty_items (&expected_strings, &list); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"" ,"b" ,"" ,NULL ); +t_string_list_remove_empty_items (&expected_strings, &list); + +t_string_list_clear (&expected_strings,0 ); +t_string_list_clear (&list,0 ); +} + +static void t_string_list_unsorted_string_list_has_string ( +struct string_list *list, +const char *str,int expected) +{ +int has_string =unsorted_string_list_has_string (list, str); +cl_assert_equal_i (has_string, expected); +} + +void test_string_list__unsorted_string_list_has_string (void ) +{ +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&list,0 ,"b" ,"d" ,"a" ,NULL ); +t_string_list_unsorted_string_list_has_string (&list,"a" ,1 ); +t_string_list_unsorted_string_list_has_string (&list,"b" ,1 ); +t_string_list_unsorted_string_list_has_string (&list,"c" ,0 ); +t_string_list_unsorted_string_list_has_string (&list,"d" ,1 ); + +t_string_list_clear (&list,0 ); +} + +static void t_string_list_unsorted_string_list_delete_item ( +struct string_list *expected_list, +struct string_list *list, +int i) +{ +unsorted_string_list_delete_item (list, i,0 ); + +t_string_list_equal (list, expected_list); +} + +void test_string_list__unsorted_string_list_delete_item (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"c" ,"b" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"d" ,"b" ,"c" ,NULL ); +t_string_list_unsorted_string_list_delete_item (&expected_strings, &list,1 ); + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_create_string_list_dup (&list,0 ,"" ,NULL ); +t_string_list_unsorted_string_list_delete_item (&expected_strings, &list,0 ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"d" ,"c" ,"b" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"d" ,"c" ,"b" ,"d" ,NULL ); +t_string_list_unsorted_string_list_delete_item (&expected_strings, &list,4 ); + +t_string_list_clear (&expected_strings,0 ); +t_string_list_clear (&list,0 ); +} --
Quoted 2 lines
2.51.0
Fixed extra EOF lines and overlong lines in v3.
Re: [PATCH 2/2] string-list: add string_list_sort_u() that mimics "sort -u"
In reply to Amisha ChhajedQuoted 2 lines · Amisha Chhajed
Many callsites of
string_list_remove_duplicates()call it immdediately after callingstring_list_sort(), understandably
nit: s/immdediately/immediately
Quoted 12 lines
as the former requires string-list to be sorted, it is clear that these places are sorting only to remove duplicates and for no other reason.
Introduce a helper function
string_list_sort_uthat combines these two calls that often appear together, to simplify these callsites. Replace the current calls of those methods withstring_list_sort_u().Signed-off-by Amisha Chhajed <[email protected]>---
[snip]
Re: [PATCH 2/2] string-list: add string_list_sort_u() that mimics "sort -u"
Quoted 5 lines · Kristoffer Haugsbakk
Quoted 2 lines · Amisha Chhajed
Many callsites of
string_list_remove_duplicates()call it immdediately after callingstring_list_sort(), understandablynit: s/immdediately/immediately
Thanks for good eyes, but I've merged this version already to 'next' X-<.
Re: [PATCH 1/2] u-string-list: add unit tests for string-list methods
In reply to Amisha ChhajedQuoted 25 lines · Amisha Chhajed
Unit tests in
u-string-list.cdoes not cover several methods in string-list, this gap in coverage makes it difficult to ensure no regressions are introduced in future changes.Add unit tests for the following methods to enhance coverage:
string_list_remove_empty_items()unsorted_string_list_has_string()unsorted_string_list_delete_item()string_list_has_string()string_list_insert()string_list_sort()string_list_remove()Signed-off-by Amisha Chhajed <[email protected]>--- t/unit-tests/u-string-list.c | 197 +++++++++++++++++++++++++++++++++++ 1 file changed, 197 insertions(+)t/unit-tests/u-string-list.c +1
-0@@ -243,6 +243,133 @@ void test_string_list__filter(void) +static void t_string_list_insert (struct string_list *expected_strings, ...)
t/unit-tests/u-string-list.c void test_string_list__filter(void) · line 278
Quoted 10 lines
t/unit-tests/u-string-list.c +10
-0+{ +struct string_list strings_to_insert =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; +va_list ap; + +va_start (ap, expected_strings); +t_vcreate_string_list_dup (&strings_to_insert,0 , ap); +va_end (ap); + +for (int i =0 ; i < strings_to_insert.nr; i++) {
As strings_to_insert.nr is of type size_t, even though int is plenty large enough in practice, the compiler will complain.
t/unit-tests/u-string-list.c
Quoted 2 lines
t/unit-tests/u-string-list.c +2
-0+string_list_insert (&list, strings_to_insert.items[i].string); + }
Also, lose the {} around a single statement block.
Re: [PATCH 1/2] u-string-list: add unit tests for string-list methods
Quoted 42 lines · Junio C Hamano
Quoted 25 lines · Amisha Chhajed
Unit tests in
u-string-list.cdoes not cover several methods in string-list, this gap in coverage makes it difficult to ensure no regressions are introduced in future changes.Add unit tests for the following methods to enhance coverage:
string_list_remove_empty_items()unsorted_string_list_has_string()unsorted_string_list_delete_item()string_list_has_string()string_list_insert()string_list_sort()string_list_remove()Signed-off-by Amisha Chhajed <[email protected]>--- t/unit-tests/u-string-list.c | 197 +++++++++++++++++++++++++++++++++++ 1 file changed, 197 insertions(+)t/unit-tests/u-string-list.c +1
-0@@ -243,6 +243,133 @@ void test_string_list__filter(void) +static void t_string_list_insert (struct string_list *expected_strings, ...)t/unit-tests/u-string-list.c void test_string_list__filter(void) · line 278
Quoted 10 lines
t/unit-tests/u-string-list.c +10
-0+{ +struct string_list strings_to_insert =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; +va_list ap; + +va_start (ap, expected_strings); +t_vcreate_string_list_dup (&strings_to_insert,0 , ap); +va_end (ap); + +for (int i =0 ; i < strings_to_insert.nr; i++) {As strings_to_insert.nr is of type
size_t, even though int is plenty large enough in practice, the compiler will complain.
Quoted 4 lines
t/unit-tests/u-string-list.c
Quoted 2 lines
t/unit-tests/u-string-list.c +2
-0+string_list_insert (&list, strings_to_insert.items[i].string); + }Also, lose the {} around a single statement block.
Done, Thanks for the review.
Re: [PATCH 1/2] u-string-list: add unit tests for string-list methods
Quoted 11 lines · Amisha Chhajed
Quoted 9 lines
Quoted 1 line
+ for (int i = 0; i < strings_to_insert.nr; i++) {
As strings_to_insert.nr is of type
size_t, even though int is plenty large enough in practice, the compiler will complain.Review
Quoted 2 lines
(quoted diff) +2
-0+ string_list_insert(&list, strings_to_insert.items[i].string); + }Also, lose the {} around a single statement block.
Done, Thanks for the review.
Heh, that wasn't even a review but a knee-jerk reaction to compiler warnings.
Quoted 3 lines · Amisha Chhajed
I was unable to write unit tests for this new method in this RFC PATCH since I was quite unsure why no unit tests were present for
string_list_sortandstring_list_insert.
t/unit-tests/u-string-list.c has tests for remove_duplicates, though. If one discovers test coverage is lacking, it is perfectly fine to enhance the coverage, especially the low-level unit tests are ralatively cheap to run.
Thanks.
PATCH 1/2 u-string-list: add unit tests for string-list methods
In reply to Amisha ChhajedUnit tests in u-string-list.c does not cover several methods in string-list, this gap in coverage makes it difficult to ensure no regressions are introduced in future changes.
Add unit tests for the following methods to enhance coverage:string_list_remove_empty_items() unsorted_string_list_has_string() unsorted_string_list_delete_item() string_list_has_string()string_list_insert()string_list_sort()string_list_remove()
--- t/unit-tests/u-string-list.c | 197 +++++++++++++++++++++++++++++++++++ 1 file changed, 197 insertions(+)
t/unit-tests/u-string-list.c +197 -0
@@ -243,6 +243,133 @@ void test_string_list__filter(void)t_string_list_clear (&list,0 ); } +static void t_string_list_has_string (struct string_list *list,const char *string,int expected) +{ +int has_string =string_list_has_string (list, string); +cl_assert_equal_i (has_string, expected); +} + +void test_string_list__has_string (void ) +{ +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&list,0 ,NULL ); +t_string_list_has_string (&list,"" ,0 ); + +t_create_string_list_dup (&list,0 ,"a" ,"b" ,"c" ,NULL ); +t_string_list_has_string (&list,"a" ,1 ); +t_string_list_has_string (&list,"b" ,1 ); +t_string_list_has_string (&list,"c" ,1 ); +t_string_list_has_string (&list,"d" ,0 ); + +t_string_list_clear (&list,0 ); +} + +static void t_string_list_insert (struct string_list *expected_strings, ...) +{ +struct string_list strings_to_insert =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; +va_list ap; + +va_start (ap, expected_strings); +t_vcreate_string_list_dup (&strings_to_insert,0 , ap); +va_end (ap); + +for (int i =0 ; i < strings_to_insert.nr; i++) { +string_list_insert (&list, strings_to_insert.items[i].string); + } + +t_string_list_equal (&list, expected_strings); + +string_list_clear (&strings_to_insert,0 ); +string_list_clear (&list,0 ); +} + +void test_string_list__insert (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_string_list_insert (&expected_strings,NULL ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,NULL ); +t_string_list_insert (&expected_strings,"b" ,"a" ,"a" ,"b" ,NULL ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,"c" ,NULL ); +t_string_list_insert (&expected_strings,"c" ,"b" ,"a" ,"c" ,"b" ,NULL ); + +t_create_string_list_dup (&expected_strings,0 ,"" ,"a" ,NULL ); +t_string_list_insert (&expected_strings,"a" ,"a" ,"a" ,"" ,NULL ); + +t_string_list_clear (&expected_strings,0 ); +} + +static void t_string_list_sort (struct string_list *list, ...) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +va_list ap; + +va_start (ap, list); +t_vcreate_string_list_dup (&expected_strings,0 , ap); +va_end (ap); + +string_list_sort (list); +t_string_list_equal (list, &expected_strings); + +string_list_clear (&expected_strings,0 ); +} + +void test_string_list__sort (void ) +{ +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&list,0 ,NULL ); +t_string_list_sort (&list,NULL ); + +t_create_string_list_dup (&list,0 ,"b" ,"" ,"a" ,NULL ); +t_string_list_sort (&list,"" ,"a" ,"b" ,NULL ); + +t_create_string_list_dup (&list,0 ,"c" ,"a" ,"b" ,"a" ,NULL ); +t_string_list_sort (&list,"a" ,"a" ,"b" ,"c" ,NULL ); + +t_string_list_clear (&list,0 ); +} + +static void t_string_list_remove (struct string_list *expected_strings,struct string_list *list,char const *str) +{ +string_list_remove (list, str,0 ); +t_string_list_equal (list, expected_strings); +} + +void test_string_list__remove (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_create_string_list_dup (&list,0 ,NULL ); +t_string_list_remove (&expected_strings, &list,"" ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"a" ,NULL ); +t_string_list_remove (&expected_strings, &list,"a" ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,"b" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"b" ,"b" ,"c" ,NULL ); +t_string_list_remove (&expected_strings, &list,"c" ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,"d" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"b" ,"c" ,"d" ,NULL ); +t_string_list_remove (&expected_strings, &list,"c" ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,"c" ,"d" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"b" ,"c" ,"d" ,NULL ); +t_string_list_remove (&expected_strings, &list,"e" ); + +t_string_list_clear (&expected_strings,0 ); +t_string_list_clear (&list,0 ); +} +static void t_string_list_remove_duplicates (struct string_list *list, ...) {struct string_list expected_strings =STRING_LIST_INIT_DUP ;
@@ -304,3 +431,73 @@ void test_string_list__remove_duplicates(void)t_string_list_clear (&list,0 ); } + +static void t_string_list_remove_empty_items (struct string_list *expected_strings,struct string_list *list) +{ +string_list_remove_empty_items (list,0 ); +t_string_list_equal (list, expected_strings); +} + +void test_string_list__remove_empty_items (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_create_string_list_dup (&list,0 ,"" ,"" ,"" ,NULL ); +t_string_list_remove_empty_items (&expected_strings, &list); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"" ,"b" ,"" ,NULL ); +t_string_list_remove_empty_items (&expected_strings, &list); + +t_string_list_clear (&expected_strings,0 ); +t_string_list_clear (&list,0 ); +} + +static void t_string_list_unsorted_string_list_has_string (struct string_list *list,const char *str,int expected) +{ +int has_string =unsorted_string_list_has_string (list, str); +cl_assert_equal_i (has_string, expected); +} + +void test_string_list__unsorted_string_list_has_string (void ) +{ +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&list,0 ,"b" ,"d" ,"a" ,NULL ); +t_string_list_unsorted_string_list_has_string (&list,"a" ,1 ); +t_string_list_unsorted_string_list_has_string (&list,"b" ,1 ); +t_string_list_unsorted_string_list_has_string (&list,"c" ,0 ); +t_string_list_unsorted_string_list_has_string (&list,"d" ,1 ); + +t_string_list_clear (&list,0 ); +} + +static void t_string_list_unsorted_string_list_delete_item (struct string_list *expected_list,struct string_list *list,int i) +{ +unsorted_string_list_delete_item (list, i,0 ); + +t_string_list_equal (list, expected_list); +} + +void test_string_list__unsorted_string_list_delete_item (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"c" ,"b" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"d" ,"b" ,"c" ,NULL ); +t_string_list_unsorted_string_list_delete_item (&expected_strings, &list,1 ); + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_create_string_list_dup (&list,0 ,"" ,NULL ); +t_string_list_unsorted_string_list_delete_item (&expected_strings, &list,0 ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"d" ,"c" ,"b" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"d" ,"c" ,"b" ,"d" ,NULL ); +t_string_list_unsorted_string_list_delete_item (&expected_strings, &list,4 ); + +t_string_list_clear (&expected_strings,0 ); +t_string_list_clear (&list,0 ); +}
Signature · 1 line
2.51.0
PATCH 2/2 string-list: add string_list_sort_u() that mimics "sort -u"
Many callsites of string_list_remove_duplicates() call it immdediately after calling string_list_sort(), understandably as the former requires string-list to be sorted, it is clear that these places are sorting only to remove duplicates and for no other reason.
Introduce a helper function string_list_sort_u that combines these two calls that often appear together, to simplify these callsites. Replace the current calls of those methods with string_list_sort_u().
--- builtin/clone.c | 3 +-- builtin/fast-export.c | 3 +-- builtin/pack-objects.c | 6 ++---- builtin/sparse-checkout.c | 6 ++---- help.c | 3 +-- notes.c | 3 +-- string-list.c | 6 ++++++ string-list.h | 6 ++++++ t/unit-tests/u-string-list.c | 34 ++++++++++++++++++++++++++++++++++ 9 files changed, 54 insertions(+), 16 deletions(-)
builtin/clone.c +1 -2
@@ -1136,8 +1136,7 @@ int cmd_clone(int argc,int val;/* remove duplicates */ -string_list_sort (&option_recurse_submodules); -string_list_remove_duplicates (&option_recurse_submodules,0 ); +string_list_sort_u (&option_recurse_submodules,0 );/* * NEEDSWORK: In a multi-working-tree world, this needs to be
builtin/fast-export.c +1 -2
@@ -1118,8 +1118,7 @@ static void get_tags_and_duplicates(struct rev_cmdline_info *info)free (full_name); } -string_list_sort (&extra_refs); -string_list_remove_duplicates (&extra_refs,0 ); +string_list_sort_u (&extra_refs,0 ); }static void handle_tags_and_duplicates (struct string_list *extras)
builtin/pack-objects.c +2 -4
@@ -3849,10 +3849,8 @@ static void read_packs_list_from_stdin(struct rev_info *revs)strbuf_reset (&buf); } -string_list_sort (&include_packs); -string_list_remove_duplicates (&include_packs,0 ); -string_list_sort (&exclude_packs); -string_list_remove_duplicates (&exclude_packs,0 ); +string_list_sort_u (&include_packs,0 ); +string_list_sort_u (&exclude_packs,0 );repo_for_each_pack (the_repository, p) {const char *pack_name =pack_basename (p);
builtin/sparse-checkout.c +2 -4
@@ -292,8 +292,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)string_list_insert (&sl, pe->pattern); } -string_list_sort (&sl); -string_list_remove_duplicates (&sl,0 ); +string_list_sort_u (&sl,0 );fprintf (fp,"/*\n!/*/\n" );
@@ -316,8 +315,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)strbuf_release (&parent_pattern); -string_list_sort (&sl); -string_list_remove_duplicates (&sl,0 ); +string_list_sort_u (&sl,0 );for (i =0 ; i < sl.nr; i++) {char *pattern =escaped_pattern (sl.items[i].string);
help.c +1 -2
@@ -420,8 +420,7 @@ void list_cmds_by_config(struct string_list *list)if (repo_config_get_string_tmp (the_repository,"completion.commands" , &cmd_list))return ; -string_list_sort (list); -string_list_remove_duplicates (list,0 ); +string_list_sort_u (list,0 );while (*cmd_list) {struct strbuf sb =STRBUF_INIT ;
notes.c +1 -2
@@ -921,8 +921,7 @@ int combine_notes_cat_sort_uniq(struct object_id *cur_oid,if (string_list_add_note_lines (&sort_uniq_list, new_oid)) goto out;string_list_remove_empty_items (&sort_uniq_list,0 ); -string_list_sort (&sort_uniq_list); -string_list_remove_duplicates (&sort_uniq_list,0 ); +string_list_sort_u (&sort_uniq_list,0 );/* create a new blob object from sort_uniq_list */ if (for_each_string_list(&sort_uniq_list,
string-list.c +6 -0
@@ -247,6 +247,12 @@ void string_list_sort(struct string_list *list)QSORT_S (list->items, list->nr, cmp_items, &sort_ctx); } +void string_list_sort_u (struct string_list *list,int free_util) +{ +string_list_sort (list); +string_list_remove_duplicates (list, free_util); +} +struct string_list_item *unsorted_string_list_lookup (struct string_list *list,const char *string) {
string-list.h +6 -0
@@ -239,6 +239,12 @@ struct string_list_item *string_list_append_nodup(struct string_list *list, char*/ void string_list_sort (struct string_list *list); +/** +* Sort the list and then remove duplicate entries. If free_util is true, +* call free() on the util members of any items that have to be deleted. +*/ +void string_list_sort_u (struct string_list *list,int free_util); +/** * Like `string_list_has_string()` but for unsorted lists. Linear in * size of the list.
t/unit-tests/u-string-list.c +34 -0
@@ -432,6 +432,40 @@ void test_string_list__remove_duplicates(void)t_string_list_clear (&list,0 ); } +static void t_string_list_sort_u (struct string_list *list, ...) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +va_list ap; + +va_start (ap, list); +t_vcreate_string_list_dup (&expected_strings,0 , ap); +va_end (ap); + +string_list_sort_u (list,0 ); +t_string_list_equal (list, &expected_strings); + +string_list_clear (&expected_strings,0 ); +} + +void test_string_list__sort_u (void ) +{ +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&list,0 ,NULL ); +t_string_list_sort_u (&list,NULL ); + +t_create_string_list_dup (&list,0 ,"" ,"" ,"" ,"" ,NULL ); +t_string_list_sort_u (&list,"" ,NULL ); + +t_create_string_list_dup (&list,0 ,"b" ,"a" ,"a" ,"" ,NULL ); +t_string_list_sort_u (&list,"" ,"a" ,"b" ,NULL ); + +t_create_string_list_dup (&list,0 ,"b" ,"a" ,"a" ,"d" ,"c" ,"c" ,NULL ); +t_string_list_sort_u (&list,"a" ,"b" ,"c" ,"d" ,NULL ); + +t_string_list_clear (&list,0 ); +} +static void t_string_list_remove_empty_items (struct string_list *expected_strings,struct string_list *list) {string_list_remove_empty_items (list,0 );
Signature · 1 line
2.51.0
RFC PATCH 2/2 Replacing calls of string_list_sort and string_list_remove_duplicates with the combined variant string_list_u.
In reply to Amisha Chhajed--- builtin/clone.c | 3 +-- builtin/fast-export.c | 3 +-- builtin/pack-objects.c | 6 ++---- builtin/sparse-checkout.c | 6 ++---- help.c | 3 +-- notes.c | 3 +-- 6 files changed, 8 insertions(+), 16 deletions(-)
builtin/clone.c +1 -2
@@ -1136,8 +1136,7 @@ int cmd_clone(int argc,int val;/* remove duplicates */ -string_list_sort (&option_recurse_submodules); -string_list_remove_duplicates (&option_recurse_submodules,0 ); +string_list_sort_u (&option_recurse_submodules,0 );/* * NEEDSWORK: In a multi-working-tree world, this needs to be
builtin/fast-export.c +1 -2
@@ -1118,8 +1118,7 @@ static void get_tags_and_duplicates(struct rev_cmdline_info *info)free (full_name); } -string_list_sort (&extra_refs); -string_list_remove_duplicates (&extra_refs,0 ); +string_list_sort_u (&extra_refs,0 ); }static void handle_tags_and_duplicates (struct string_list *extras)
builtin/pack-objects.c +2 -4
@@ -3849,10 +3849,8 @@ static void read_packs_list_from_stdin(struct rev_info *revs)strbuf_reset (&buf); } -string_list_sort (&include_packs); -string_list_remove_duplicates (&include_packs,0 ); -string_list_sort (&exclude_packs); -string_list_remove_duplicates (&exclude_packs,0 ); +string_list_sort_u (&include_packs,0 ); +string_list_sort_u (&exclude_packs,0 );repo_for_each_pack (the_repository, p) {const char *pack_name =pack_basename (p);
builtin/sparse-checkout.c +2 -4
@@ -292,8 +292,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)string_list_insert (&sl, pe->pattern); } -string_list_sort (&sl); -string_list_remove_duplicates (&sl,0 ); +string_list_sort_u (&sl,0 );fprintf (fp,"/*\n!/*/\n" );
@@ -316,8 +315,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)strbuf_release (&parent_pattern); -string_list_sort (&sl); -string_list_remove_duplicates (&sl,0 ); +string_list_sort_u (&sl,0 );for (i =0 ; i < sl.nr; i++) {char *pattern =escaped_pattern (sl.items[i].string);
help.c +1 -2
@@ -420,8 +420,7 @@ void list_cmds_by_config(struct string_list *list)if (repo_config_get_string_tmp (the_repository,"completion.commands" , &cmd_list))return ; -string_list_sort (list); -string_list_remove_duplicates (list,0 ); +string_list_sort_u (list,0 );while (*cmd_list) {struct strbuf sb =STRBUF_INIT ;
notes.c +1 -2
@@ -921,8 +921,7 @@ int combine_notes_cat_sort_uniq(struct object_id *cur_oid,if (string_list_add_note_lines (&sort_uniq_list, new_oid)) goto out;string_list_remove_empty_items (&sort_uniq_list,0 ); -string_list_sort (&sort_uniq_list); -string_list_remove_duplicates (&sort_uniq_list,0 ); +string_list_sort_u (&sort_uniq_list,0 );/* create a new blob object from sort_uniq_list */ if (for_each_string_list(&sort_uniq_list,
Signature · 1 line
2.51.0
Re: [RFC PATCH 2/2] Replacing calls of string_list_sort and string_list_remove_duplicates with the combined variant string_list_u.
Quoted 9 lines · Amisha Chhajed
Signed-off-by Amisha Chhajed <[email protected]>--- builtin/clone.c | 3 +-- builtin/fast-export.c | 3 +-- builtin/pack-objects.c | 6 ++---- builtin/sparse-checkout.c | 6 ++---- help.c | 3 +-- notes.c | 3 +-- 6 files changed, 8 insertions(+), 16 deletions(-)
Nice to see many calls to remove_duplicates() are hidden away, so that we can check the remaining ones.
PATCH v2 1/2 u-string-list: add unit tests for string-list methods
In reply to Amisha ChhajedUnit tests in u-string-list.c does not cover several methods in string-list, this gap in coverage makes it difficult to ensure no regressions are introduced in future changes.
Add unit tests for the following methods to enhance coverage:string_list_remove_empty_items() unsorted_string_list_has_string() unsorted_string_list_delete_item() string_list_has_string()string_list_insert()string_list_sort()string_list_remove()
--- t/unit-tests/u-string-list.c | 196 +++++++++++++++++++++++++++++++++++ 1 file changed, 196 insertions(+)
t/unit-tests/u-string-list.c +196 -0
@@ -243,6 +243,132 @@ void test_string_list__filter(void)t_string_list_clear (&list,0 ); } +static void t_string_list_has_string (struct string_list *list,const char *string,int expected) +{ +int has_string =string_list_has_string (list, string); +cl_assert_equal_i (has_string, expected); +} + +void test_string_list__has_string (void ) +{ +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&list,0 ,NULL ); +t_string_list_has_string (&list,"" ,0 ); + +t_create_string_list_dup (&list,0 ,"a" ,"b" ,"c" ,NULL ); +t_string_list_has_string (&list,"a" ,1 ); +t_string_list_has_string (&list,"b" ,1 ); +t_string_list_has_string (&list,"c" ,1 ); +t_string_list_has_string (&list,"d" ,0 ); + +t_string_list_clear (&list,0 ); +} + +static void t_string_list_insert (struct string_list *expected_strings, ...) +{ +struct string_list strings_to_insert =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; +va_list ap; + +va_start (ap, expected_strings); +t_vcreate_string_list_dup (&strings_to_insert,0 , ap); +va_end (ap); + +for (size_t i =0 ; i < strings_to_insert.nr; i++) +string_list_insert (&list, strings_to_insert.items[i].string); + +t_string_list_equal (&list, expected_strings); + +string_list_clear (&strings_to_insert,0 ); +string_list_clear (&list,0 ); +} + +void test_string_list__insert (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_string_list_insert (&expected_strings,NULL ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,NULL ); +t_string_list_insert (&expected_strings,"b" ,"a" ,"a" ,"b" ,NULL ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,"c" ,NULL ); +t_string_list_insert (&expected_strings,"c" ,"b" ,"a" ,"c" ,"b" ,NULL ); + +t_create_string_list_dup (&expected_strings,0 ,"" ,"a" ,NULL ); +t_string_list_insert (&expected_strings,"a" ,"a" ,"a" ,"" ,NULL ); + +t_string_list_clear (&expected_strings,0 ); +} + +static void t_string_list_sort (struct string_list *list, ...) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +va_list ap; + +va_start (ap, list); +t_vcreate_string_list_dup (&expected_strings,0 , ap); +va_end (ap); + +string_list_sort (list); +t_string_list_equal (list, &expected_strings); + +string_list_clear (&expected_strings,0 ); +} + +void test_string_list__sort (void ) +{ +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&list,0 ,NULL ); +t_string_list_sort (&list,NULL ); + +t_create_string_list_dup (&list,0 ,"b" ,"" ,"a" ,NULL ); +t_string_list_sort (&list,"" ,"a" ,"b" ,NULL ); + +t_create_string_list_dup (&list,0 ,"c" ,"a" ,"b" ,"a" ,NULL ); +t_string_list_sort (&list,"a" ,"a" ,"b" ,"c" ,NULL ); + +t_string_list_clear (&list,0 ); +} + +static void t_string_list_remove (struct string_list *expected_strings,struct string_list *list,char const *str) +{ +string_list_remove (list, str,0 ); +t_string_list_equal (list, expected_strings); +} + +void test_string_list__remove (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_create_string_list_dup (&list,0 ,NULL ); +t_string_list_remove (&expected_strings, &list,"" ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"a" ,NULL ); +t_string_list_remove (&expected_strings, &list,"a" ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,"b" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"b" ,"b" ,"c" ,NULL ); +t_string_list_remove (&expected_strings, &list,"c" ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,"d" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"b" ,"c" ,"d" ,NULL ); +t_string_list_remove (&expected_strings, &list,"c" ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,"c" ,"d" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"b" ,"c" ,"d" ,NULL ); +t_string_list_remove (&expected_strings, &list,"e" ); + +t_string_list_clear (&expected_strings,0 ); +t_string_list_clear (&list,0 ); +} +static void t_string_list_remove_duplicates (struct string_list *list, ...) {struct string_list expected_strings =STRING_LIST_INIT_DUP ;
@@ -304,3 +430,73 @@ void test_string_list__remove_duplicates(void)t_string_list_clear (&list,0 ); } + +static void t_string_list_remove_empty_items (struct string_list *expected_strings,struct string_list *list) +{ +string_list_remove_empty_items (list,0 ); +t_string_list_equal (list, expected_strings); +} + +void test_string_list__remove_empty_items (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_create_string_list_dup (&list,0 ,"" ,"" ,"" ,NULL ); +t_string_list_remove_empty_items (&expected_strings, &list); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"b" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"" ,"b" ,"" ,NULL ); +t_string_list_remove_empty_items (&expected_strings, &list); + +t_string_list_clear (&expected_strings,0 ); +t_string_list_clear (&list,0 ); +} + +static void t_string_list_unsorted_string_list_has_string (struct string_list *list,const char *str,int expected) +{ +int has_string =unsorted_string_list_has_string (list, str); +cl_assert_equal_i (has_string, expected); +} + +void test_string_list__unsorted_string_list_has_string (void ) +{ +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&list,0 ,"b" ,"d" ,"a" ,NULL ); +t_string_list_unsorted_string_list_has_string (&list,"a" ,1 ); +t_string_list_unsorted_string_list_has_string (&list,"b" ,1 ); +t_string_list_unsorted_string_list_has_string (&list,"c" ,0 ); +t_string_list_unsorted_string_list_has_string (&list,"d" ,1 ); + +t_string_list_clear (&list,0 ); +} + +static void t_string_list_unsorted_string_list_delete_item (struct string_list *expected_list,struct string_list *list,int i) +{ +unsorted_string_list_delete_item (list, i,0 ); + +t_string_list_equal (list, expected_list); +} + +void test_string_list__unsorted_string_list_delete_item (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"c" ,"b" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"d" ,"b" ,"c" ,NULL ); +t_string_list_unsorted_string_list_delete_item (&expected_strings, &list,1 ); + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_create_string_list_dup (&list,0 ,"" ,NULL ); +t_string_list_unsorted_string_list_delete_item (&expected_strings, &list,0 ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"d" ,"c" ,"b" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"d" ,"c" ,"b" ,"d" ,NULL ); +t_string_list_unsorted_string_list_delete_item (&expected_strings, &list,4 ); + +t_string_list_clear (&expected_strings,0 ); +t_string_list_clear (&list,0 ); +}
Signature · 1 line
2.51.0
PATCH v2 2/2 string-list: add string_list_sort_u() that mimics "sort -u"
Many callsites of string_list_remove_duplicates() call it immdediately after calling string_list_sort(), understandably as the former requires string-list to be sorted, it is clear that these places are sorting only to remove duplicates and for no other reason.
Introduce a helper function string_list_sort_u that combines these two calls that often appear together, to simplify these callsites. Replace the current calls of those methods with string_list_sort_u().
--- builtin/clone.c | 3 +-- builtin/fast-export.c | 3 +-- builtin/pack-objects.c | 6 ++---- builtin/sparse-checkout.c | 6 ++---- help.c | 3 +-- notes.c | 3 +-- string-list.c | 6 ++++++ string-list.h | 6 ++++++ t/unit-tests/u-string-list.c | 34 ++++++++++++++++++++++++++++++++++ 9 files changed, 54 insertions(+), 16 deletions(-)
builtin/clone.c +1 -2
@@ -1136,8 +1136,7 @@ int cmd_clone(int argc,int val;/* remove duplicates */ -string_list_sort (&option_recurse_submodules); -string_list_remove_duplicates (&option_recurse_submodules,0 ); +string_list_sort_u (&option_recurse_submodules,0 );/* * NEEDSWORK: In a multi-working-tree world, this needs to be
builtin/fast-export.c +1 -2
@@ -1118,8 +1118,7 @@ static void get_tags_and_duplicates(struct rev_cmdline_info *info)free (full_name); } -string_list_sort (&extra_refs); -string_list_remove_duplicates (&extra_refs,0 ); +string_list_sort_u (&extra_refs,0 ); }static void handle_tags_and_duplicates (struct string_list *extras)
builtin/pack-objects.c +2 -4
@@ -3849,10 +3849,8 @@ static void read_packs_list_from_stdin(struct rev_info *revs)strbuf_reset (&buf); } -string_list_sort (&include_packs); -string_list_remove_duplicates (&include_packs,0 ); -string_list_sort (&exclude_packs); -string_list_remove_duplicates (&exclude_packs,0 ); +string_list_sort_u (&include_packs,0 ); +string_list_sort_u (&exclude_packs,0 );repo_for_each_pack (the_repository, p) {const char *pack_name =pack_basename (p);
builtin/sparse-checkout.c +2 -4
@@ -292,8 +292,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)string_list_insert (&sl, pe->pattern); } -string_list_sort (&sl); -string_list_remove_duplicates (&sl,0 ); +string_list_sort_u (&sl,0 );fprintf (fp,"/*\n!/*/\n" );
@@ -316,8 +315,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)strbuf_release (&parent_pattern); -string_list_sort (&sl); -string_list_remove_duplicates (&sl,0 ); +string_list_sort_u (&sl,0 );for (i =0 ; i < sl.nr; i++) {char *pattern =escaped_pattern (sl.items[i].string);
help.c +1 -2
@@ -420,8 +420,7 @@ void list_cmds_by_config(struct string_list *list)if (repo_config_get_string_tmp (the_repository,"completion.commands" , &cmd_list))return ; -string_list_sort (list); -string_list_remove_duplicates (list,0 ); +string_list_sort_u (list,0 );while (*cmd_list) {struct strbuf sb =STRBUF_INIT ;
notes.c +1 -2
@@ -921,8 +921,7 @@ int combine_notes_cat_sort_uniq(struct object_id *cur_oid,if (string_list_add_note_lines (&sort_uniq_list, new_oid)) goto out;string_list_remove_empty_items (&sort_uniq_list,0 ); -string_list_sort (&sort_uniq_list); -string_list_remove_duplicates (&sort_uniq_list,0 ); +string_list_sort_u (&sort_uniq_list,0 );/* create a new blob object from sort_uniq_list */ if (for_each_string_list(&sort_uniq_list,
string-list.c +6 -0
@@ -247,6 +247,12 @@ void string_list_sort(struct string_list *list)QSORT_S (list->items, list->nr, cmp_items, &sort_ctx); } +void string_list_sort_u (struct string_list *list,int free_util) +{ +string_list_sort (list); +string_list_remove_duplicates (list, free_util); +} +struct string_list_item *unsorted_string_list_lookup (struct string_list *list,const char *string) {
string-list.h +6 -0
@@ -239,6 +239,12 @@ struct string_list_item *string_list_append_nodup(struct string_list *list, char*/ void string_list_sort (struct string_list *list); +/** +* Sort the list and then remove duplicate entries. If free_util is true, +* call free() on the util members of any items that have to be deleted. +*/ +void string_list_sort_u (struct string_list *list,int free_util); +/** * Like `string_list_has_string()` but for unsorted lists. Linear in * size of the list.
t/unit-tests/u-string-list.c +34 -0
@@ -431,6 +431,40 @@ void test_string_list__remove_duplicates(void)t_string_list_clear (&list,0 ); } +static void t_string_list_sort_u (struct string_list *list, ...) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +va_list ap; + +va_start (ap, list); +t_vcreate_string_list_dup (&expected_strings,0 , ap); +va_end (ap); + +string_list_sort_u (list,0 ); +t_string_list_equal (list, &expected_strings); + +string_list_clear (&expected_strings,0 ); +} + +void test_string_list__sort_u (void ) +{ +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&list,0 ,NULL ); +t_string_list_sort_u (&list,NULL ); + +t_create_string_list_dup (&list,0 ,"" ,"" ,"" ,"" ,NULL ); +t_string_list_sort_u (&list,"" ,NULL ); + +t_create_string_list_dup (&list,0 ,"b" ,"a" ,"a" ,"" ,NULL ); +t_string_list_sort_u (&list,"" ,"a" ,"b" ,NULL ); + +t_create_string_list_dup (&list,0 ,"b" ,"a" ,"a" ,"d" ,"c" ,"c" ,NULL ); +t_string_list_sort_u (&list,"a" ,"b" ,"c" ,"d" ,NULL ); + +t_string_list_clear (&list,0 ); +} +static void t_string_list_remove_empty_items (struct string_list *expected_strings,struct string_list *list) {string_list_remove_empty_items (list,0 );
Signature · 1 line
2.51.0
Re: [PATCH v2 2/2] string-list: add string_list_sort_u() that mimics "sort -u"
Quoted 10 lines · Amisha Chhajed
Many callsites of
string_list_remove_duplicates()call it immdediately after callingstring_list_sort(), understandably as the former requires string-list to be sorted, it is clear that these places are sorting only to remove duplicates and for no other reason.Introduce a helper function
string_list_sort_uthat combines these two calls that often appear together, to simplify these callsites. Replace the current calls of those methods withstring_list_sort_u().
After this, only two callers of string_list_remove_duplicates() remain in the codebase.
The one in builtin/fetch.c::cmd_fetch() smells somewhat fishy. It prepares a string_list "list", populates it with for_each_remote() by appending remotes found in the configuration when asked to do "--all", or append named ones with "--multiple", and then calls "remove duplicates" without sorting the resulting list first.
- A test should be able to demonstrate that the call to string_list_remove_duplicates() is not operating on a sorted string list.
- Once a breakage is demonstrated, we need to devise a fix. Sorting the string list before removing would certainly fix the duplicates removal, but it will change the order in which the remotes are consulted. I think it is currently "whatever order these remotes appear in your configuration file(s)", but that does not mean it is a random order. It is very likely that they are in the order the user has learned to expect the remotes are to be consulted, so "sort and then dedup" might appear as a regression in behaviour. I dunno.
The one in builtin/help.c::list_config_help() is somewhat fishy as well. I didn't read it too carefully, but it walks over keys which is in sorted string_list, and sometimes pushes the key intact to keys_uniq, and some other times munges the key and pushes the result to keys_uniq. I do not know if presence of these these munged keys in the keys_uniq string list breaks the sortedness of keys_uniq. If keys_uniq is *not* sorted, then running "remove duplicates" would be broken, of course. Again, a test should be able to demonstrate if this is the case, and we should fix it as well if it is broken.
Thanks.
Re: [PATCH v2 2/2] string-list: add string_list_sort_u() that mimics "sort -u"
Quoted 10 lines
The one in builtin/fetch.c::cmd_fetch() smells somewhat fishy. It prepares a
string_list"list", populates it withfor_each_remote()by appending remotes found in the configuration when asked to do "--all", or append named ones with "--multiple", and then calls "remove duplicates" without sorting the resulting list first.- A test should be able to demonstrate that the call to
string_list_remove_duplicates()is not operating on a sorted string list.
Quoted 9 lines
- Once a breakage is demonstrated, we need to devise a fix. Sorting the string list before removing would certainly fix the duplicates removal, but it will change the order in which the remotes are consulted. I think it is currently "whatever order these remotes appear in your configuration file(s)", but that does not mean it is a random order. It is very likely that they are in the order the user has learned to expect the remotes are to be consulted, so "sort and then dedup" might appear as a regression in behaviour. I dunno.
was able to make the behavior fail on test,
from file t5506-remote-groups.sh,
test_expect_success 'group with non-adjacent duplicate remotes causes duplicate fetches (expected-to-fail)' '
mark fetch-dup &&update_repos &&
git config --add remotes.dup one &&
git config --add remotes.dup two &&
git config --add remotes.dup one &&
rm -f .git/FETCH_HEAD &&
git -c fetch.parallel=3 remote update dup &&repo_fetched two
'
gave log with command,
make -C t T=t5506-remote-groups.sh GIT_TEST_OPTS="-v"
from git/,
Fetching one
Fetching two
Fetching one
From one
d1132c8..cceba7b main -> one/main
From two
72c2514..57c13f4 main -> two/main
From one
d1132c8..cceba7b main -> one/main
error: fetching ref refs/remotes/one/main failed: incorrect old value provided could not fetch 'one' (exit code: 1)
Did not see any test failures post replacing this call with string_list_sort_u() but from the code, order of the list matters, and i think the expected behaviour is
if any duplicate the first call of the item should only remain but i am unsure if it is
achievable with the current sort and remove duplicate methods this is more of a, if current_item in seen_set:
pass
else:
add(list, current_item)
add(seen_set, current_item)
this preserves the order and maintains the time complexity and only keeps the first occurence.
Quoted 9 lines
The one in builtin/help.c::list_config_help() is somewhat fishy as well. I didn't read it too carefully, but it walks over keys which is in sorted
string_list, and sometimes pushes the key intact tokeys_uniq, and some other times munges the key and pushes the result tokeys_uniq. I do not know if presence of these these munged keys in thekeys_uniqstring list breaks the sortedness ofkeys_uniq. Ifkeys_uniqis *not* sorted, then running "remove duplicates" would be broken, of course. Again, a test should be able to demonstrate if this is the case, and we should fix it as well if it is broken.
This one is a bit more complex,
there is a very specific case that would result in un-sorted behaviour of the string-list
that is of form,
sorted: [aa*., aa.b]
post processing in &keys_uniq: [aa*, aa] (this is unsorted)
because ASCII value of * < . and the precedence in our code is . < * [1] but this still works as remove_duplicates does not depend strictly on the sorted property as we remove adjacent similar elements which would also work if similar items are somehow grouped together, which they are under the conditions of our code.
but sorted(x) != sorted(f(x)), and the processing we are doing also does not depend
on the order of the elements so maybe shifting the sort below with remove_duplicates
might work as a solution and would make the behaviour deterministic, saw no failures
post shifting the sort down with it.
[1] Snippet from fetch.c
if (dot)
cut = dot;
else if (wildcard && !tag)
cut = wildcard;
else if (!wildcard && tag)
cut = tag;
else
cut = wildcard < tag ? wildcard : tag;
Re: [PATCH v2 1/2] u-string-list: add unit tests for string-list methods
In reply to Amisha Chhajedt/unit-tests/u-string-list.c void test_string_list__filter(void) · line 354
Quoted 12 lines · Amisha Chhajed
t/unit-tests/u-string-list.c +12
-0+void test_string_list__remove (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_create_string_list_dup (&list,0 ,NULL ); +t_string_list_remove (&expected_strings, &list,"" ); + +t_create_string_list_dup (&expected_strings,0 ,"a" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"a" ,NULL ); +t_string_list_remove (&expected_strings, &list,"a" );
Not a complaint, not a suggestion to change anything, but just an observation. While "remove" requires the string-list to be sorted, its implementation does not seem to care if you by mistake fed an unsorted string list.
After seeing this particular test that feeds a list with two "a" and expects in the resulting list a single "a", I naturally wondered which one of these two "a" survives and which one is dropped.
"remove" removes only one matching element that is picked at random among the duplicates, but because the input is expected to be sorted, these duplicate elements sit next to each other forming a single strand of identical pearls. The end result of picking one of these pearls out would not be different no matter which one of them you pick. So the answer to my "which one of these 'a'?" question turns out to be "you cannot tell, but it does not matter" ;-)
Quoted 4 lines
t/unit-tests/u-string-list.c +4
-0+static void t_string_list_remove_empty_items (struct string_list *expected_strings,struct string_list *list) +{ +string_list_remove_empty_items (list,0 ); +t_string_list_equal (list, expected_strings);
t/unit-tests/u-string-list.c void test_string_list__remove_duplicates(void) · line 447
Quoted 10 lines
t/unit-tests/u-string-list.c +10
-0+} + +void test_string_list__remove_empty_items (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,NULL ); +t_create_string_list_dup (&list,0 ,"" ,"" ,"" ,NULL ); +t_string_list_remove_empty_items (&expected_strings, &list);
Again, not a complaint, not a suggestion to change anything, but just an observation. As we saw earlier, "remove" is "remove just one of many", but "remove_empty" is "remove all empties". Simply makes me wonder if the API looked more sane if we had "remove_all" whose signature is the same as string_list_remove().
Quoted 1 line
+static void
t_string_list_unsorted_string_list_delete_item(struct string_list *expected_list, struct string_list *list, int i)
This is a way overlong line.
Quoted 4 lines
t/unit-tests/u-string-list.c +4
-0+{ +unsorted_string_list_delete_item (list, i,0 ); + +t_string_list_equal (list, expected_list);
t/unit-tests/u-string-list.c void test_string_list__remove_duplicates(void) · line 490
Quoted 10 lines
t/unit-tests/u-string-list.c +10
-0+} + +void test_string_list__unsorted_string_list_delete_item (void ) +{ +struct string_list expected_strings =STRING_LIST_INIT_DUP ; +struct string_list list =STRING_LIST_INIT_DUP ; + +t_create_string_list_dup (&expected_strings,0 ,"a" ,"c" ,"b" ,NULL ); +t_create_string_list_dup (&list,0 ,"a" ,"d" ,"b" ,"c" ,NULL ); +t_string_list_unsorted_string_list_delete_item (&expected_strings, &list,1 );
This demonstrates one peculiar aspect of this "delete item from unsorted list" API function very well. If one is expected to name an element to delete by specifying its position in the list, it is natural to expect that the elements in the list to be ordered in some way that is meaningful to the application [*], and the API is not expected to shuffle the resulting list in such a way that makes further use of the list cumbersome. Yet, the function does exactly that by moving the element at the end of the list to the place the location of the deleted element.
Side note: [*] The "unsorted" in the name of the function is a reference to the fact that the elements are not sorted by the natural order string-list API uses to allow it to binary search; it does not mean the elements are entirely randomly thrown in and it shouldn't mean that the application cannot rely on
The only caller of this function is git.c::list_cmds() that is asked to remove the helper binaries (i.e., those whose name contains "--"), so even though git.c::commands[] list is in sorted order, and the list_builtins() function slurps them into a working list with string_list_append(), processing "nohelpers" will splinkle command names from near the tail of the list into random places in the middle of the list.
t/unit-tests/u-string-list.c void test_string_list__filter(void) · line 335
Quoted 4 lines
t/unit-tests/u-string-list.c +3
-0+t_string_list_clear (&expected_strings,0 ); +t_string_list_clear (&list,0 ); +}
Don't. Always end a text file with a complete line, please.