Re: [PATCH v2] last-modified: implement faster algorithm

Toon Claes <toon@iotcl.com> writes:

size_t is unsigned and cannot reutrn -1 sanely, unless the caller knows that ((size_t)-1) signals an error. The compiler warns, and we compile with -Werror, so we end up getting

    builtin/last-modified.c: In function 'path_idx':
    builtin/last-modified.c:235:38: error: operand of '?:' changes signedness from 'int' to 'size_t' {aka 'long unsigned int'} due to unsignedness of other operand [-Werror=sign-compare]
      235 |         return ent ? ent->diff_idx : -1;
          |                                      ^~

Mark lm as UNUSED, or we'd get 

    builtin/last-modified.c: In function 'pass_to_parent':
    builtin/last-modified.c:238:50: error: unused parameter 'lm' [-Werror=unused-parameter]
      238 | static void pass_to_parent(struct last_modified *lm,
          |                            ~~~~~~~~~~~~~~~~~~~~~~^~

Our -Wsign-compare forces the compiler to give a stupid warning here, that i is unsigned and diff_queued_diff.nr is signed.

    builtin/last-modified.c: In function 'process_parent':
    builtin/last-modified.c:304:23: error: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Werror=sign-compare]
      304 |         for (i = 0; i < diff_queued_diff.nr; i++) {
          |                       ^

Yes, it is comparing unsigned with signed but so what?

As people may now know, my preference is to wean ourselves off of this dogmatic trust in -Wsign-compare but those who disagree and want to remove #define DISABLE_SIGN_COMPARE_WARNINGS should help our poor compiler here by telling it that this comparison is perfectly fine.

We know diff_queued_diff.nr is an int, and i is size_t, but we also know diff_queued_diff.nr won't be negative (or we have much bigger problems) and cannot be larger than what size_t can represent.

Earlier path_idx() wanted to signal an error by returning negative, but the type is size_t that is unsigned so it cannot do so. We instead get

    builtin/last-modified.c:307:23: error: comparison of unsigned expression in '>= 0' is always true [-Werror=type-limits]
      307 |                 if (0 <= k && bitmap_get(active_c, k))
          |                       ^~

and in this case we actually deserve it (in the sense that this is not the fault of dogmatic trust in -Wsign-compare; this is caused by using size_t to count things).

And the solution for this is *not* "size_t" -> "ssize_t", because ssize_t is not "store half the range of size_t with negative values reserved for something else like errors". Its width can be much narrower (this came up in a separate thread very recently [*]). Instead we'd need something ugly like

	if (k != (size_t)-1 && bitmap_get(active_c, k))

A quick band-aid patch to make it compile is attached at the end, but it does not try to address the root causes, which are abuse of size_t as count_t and religious use of "-Wsign-compare" [*].

[Reference]

* https://lore.kernel.org/git/9eafee4d-ea94-4382-ada0-58000d229d2e@gmail.com/
* https://staticthinking.wordpress.com/2023/07/25/wsign-compare-is-garbage/

 builtin/last-modified.c | 11 +++++------
 1 file changed, 5 insertions(+), 6 deletions(-)