Weird thing in cpp[x86-64 gcc 13.1]: the compiler thinks the if condition is always true

I’m working on an algorithmic topic and I’m running into a strange bug. when I put the source code on Complier Explorer and look at the assembly code, I seem to find out what’s causing the problem, but I don’t understand it.

Picture1:
enter image description here
Picture2:
enter image description here

When I use if(0 <= start) in Picture1, that’s ok and the code works fine.
But when I use if(0 <= j - wordDict[i].size() + 1) in Picture2, the process throw an error about "basic_string::substr: __pos (which is 18446744073709551613) > this->size() (which is 8)".

Reading the assembly code [Line84-86] when using if(0 <= j - wordDict[i].size() + 1), it’s apparently that %al is always 1 and the pc will not jump to L52 from line:86, which seems to indicate that the compiler believes that the if(0 <= j - wordDict[i].size() + 1) condition will always hold true.

Why does the compiler cause this?

Looking forward to someone addressing my query or pointing out my mistake.

Here is the complete code:

#include <string>
#include <vector>
#include <unordered_set>
using namespace std;
bool wordBreak(string s, vector<string>& wordDict) {

    vector<bool> dp(s.size(), false);
    unordered_set<string> all(wordDict.begin(), wordDict.end());

    for (int j = 0; j < s.size(); j++)
    {
        for (int i = 0; i < wordDict.size(); i++)
        {
            int start = j - wordDict[i].size() + 1;
            if (0 <= (j - wordDict[i].size() + 1))
            {
                string word = s.substr(j - wordDict[i].size() + 1, wordDict[i].size());
                if (all.find(word) != all.end() && (j - wordDict[i].size() + 1 == 0 || dp[j - wordDict[i].size()]))
                {
                    dp[j] = true;
                }
            }
        }
    }
    return dp[s.size()-1];
}

int main(int args, char * argv[])
{
    string s = "leetcode";
    vector<string> wordDict = {"leet","code"};
    wordBreak (s, wordDict);
    return 0;
}

>Solution :

You should always compile with warnings enabled. With -Wextra, you get https://godbolt.org/z/937zxjxEz

<source>:14:19: warning: comparison of unsigned expression in '>= 0' is always true [-Wtype-limits]
   14 |             if (0 <= (j - wordDict[i].size() + 1))
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

int{} - std::vector<std::string>::size_type{} + int{} is std::vector<std::string>::size_type on most compilers (since std::vector<std::string>::size_type is std::size_t which is unsigned long, so the int promotes to unsigned long)

A value of an unsigned type will always be >= 0.

Just make sure there won’t be an overflow by not subtracting:

// Add wordDict[i].size() to both sides
if (0 + wordDict[i].size() <= j - wordDict[i].size() + 1 + wordDict[i].size())
if (wordDict[i].size() <= j + 1)

And probably change the types of i and j to std::size_t too.