• d-bugmail puremagic.com (151/151) Oct 22 2012 http://d.puremagic.com/issues/show_bug.cgi?id=8874

d-bugmail puremagic.com writes:

http://d.puremagic.com/issues/show_bug.cgi?id=8874

           Summary: Possible warning for always true/always false
                    comparisons on unsigned values
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Keywords: diagnostic
          Severity: enhancement
          Priority: P2
         Component: DMD
        AssignedTo: nobody puremagic.com
        ReportedBy: bearophile_hugs eml.cc


--- Comment #0 from bearophile_hugs eml.cc 2012-10-22 15:33:11 PDT ---
This small C program solves a common Subset sum problem:

http://rosettacode.org/wiki/Subset_sum_problem


// C code starts here ------------------------
#include <stdio.h>
#include <stdlib.h>

typedef struct { char* data; int weight; } item;
typedef struct { int sum; unsigned int mask; } sum_t;

item em[] = {
    {"alliance",    -624},  {"archbishop",  -915},  {"balm",     397},
    {"bonnet",   452},  {"brute",    870},  {"centipede",   -658},
    {"cobol",    362},  {"covariate",    590},  {"departure",    952},
    {"deploy",    44},  {"diophantine",  645},  {"efferent",      54},
    {"elysee",  -326},  {"eradicate",    376},  {"escritoire",   856},
    {"exorcism",    -983},  {"fiat",     170},  {"filmy",   -874},
    {"flatworm",     503},  {"gestapo",  915},  {"infra",   -847},
    {"isis",    -982},  {"lindholm",     999},  {"markham",  475},
    {"mincemeat",   -880},  {"moresby",  756},  {"mycenae",  183},
    {"plugging",    -266},  {"smokescreen",  423},  {"speakeasy",   -745},
    {"vein",     813}
};
#define N (sizeof(em)/sizeof(em[0]))

int cmp_sums(const void *a, const void *b)
{
    return ((sum_t*)a)->sum - ((sum_t*)b)->sum;
}

sum_t *mksums(item *p, int n, int shift)
{
    sum_t *r = malloc(sizeof(*r) * (1 << n));
    int i;
    for (i = 0; i < n; i++)
        r[1<<i].sum = p[i].weight;

    r[0].mask = 0, r[0].sum = 0;

    for (i = 1; i < 1<<n; i++) {
        unsigned int b = i & -(int)i;
        r[i].mask = i << shift;
        r[i].sum = r[i & ~b].sum + r[b].sum;
    }

    qsort(r, 1<<n, sizeof(*r), cmp_sums);
    return r;
}

int main(void)
{
    int n1 = N / 2, n2 = N - n1, sols = 0;
    int i, j, i1, j1;
#define SHOW_ALL 1
#define N1 (1 << n1)
#define N2 (1 << n2)
    sum_t   *l = mksums(em, n1, 0),
        *r = mksums(em + n1, n2, n1);

    void showmask(unsigned int mask)
    {
        unsigned int m;
        for (m = 0; (1<<m) <= mask; m++) {
            if (mask & (1<<m))
                printf("(%s,%d) ", em[m].data, em[m].weight);
        }
        if (mask) puts("");
    }

    int printlist() {
        int x, y, s = (i1 - i) * (j - j1);
        if (!l[i].sum) s--;

        if (SHOW_ALL)
            for (x = i; x < i1; x++)
            for (y = j; y > j1; y--)
                showmask(l[x].mask | r[y].mask);
        return s;
    }

    i = 0, j = N2 - 1;
    while (1) {
        while (l[i].sum + r[j].sum) {
            while (i < N1 && l[i].sum + r[j].sum < 0) i++;
            while (j >= 0 && l[i].sum + r[j].sum > 0) j--;
            if (i >= N1 || j < 0) break;
        }
        if (i >= N1 || j < 0) break;

        for (i1 = i + 1; i1 < N1 && l[i1].sum == l[i].sum; i1++);
        for (j1 = j - 1; j1 >= 0 && r[j1].sum == r[j].sum; j1--);

        sols += printlist();

        i = i1, j = j1;
    }
    printf("zero sums: %d\n", sols);

    return 0;
}
// C code ends here ------------------------


The i, j, i1, j1 variables are used as array indexes, so to "improve" the code
I am willing to try replacing the line of code:

int i, j, i1, j1;

With:

size_t i, j, i1, j1;



Compiling with GCC 4.7.1, using "-Wall -Wextra", it produces the warnings:

temp.c: In function 'showmask':
temp.c:59:28: warning: comparison between signed and unsigned integer
expressions [-Wsign-compare]
temp.c: In function 'printlist':
temp.c:71:27: warning: comparison between signed and unsigned integer
expressions [-Wsign-compare]
temp.c:72:27: warning: comparison between signed and unsigned integer
expressions [-Wsign-compare]
temp.c: In function 'main':
temp.c:80:22: warning: comparison between signed and unsigned integer
expressions [-Wsign-compare]
temp.c:81:13: warning: comparison of unsigned expression >= 0 is always true
[-Wtype-limits]
temp.c:82:19: warning: comparison between signed and unsigned integer
expressions [-Wsign-compare]
temp.c:82:13: warning: comparison of unsigned expression < 0 is always false
[-Wtype-limits]
temp.c:84:15: warning: comparison between signed and unsigned integer
expressions [-Wsign-compare]
temp.c:84:9: warning: comparison of unsigned expression < 0 is always false
[-Wtype-limits]
temp.c:86:29: warning: comparison between signed and unsigned integer
expressions [-Wsign-compare]
temp.c:87:9: warning: comparison of unsigned expression >= 0 is always true
[-Wtype-limits]


Here the warning messages generated by "-Wtype-limits" save me from those bugs
caused by refactoring.


With DMD 2.061alpha using the "-wi" compilation switch this code gives no
warning messages:

// D code
int foo(uint x, uint y) {
    uint count = 0;
    if (x >= 0)
        count++;
    if (y < 0)
        count++;
    return count;
}
void main() {}


In this little foo() function it's easy to see the problems, but in a large
function it's more easy to miss the mistake of using unsigned x and y with
those comparisons that are always false or always true.

So consider the possibility of adding such warning to D/DMD.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------