clang standard library bug or c undefined behavior?-CodePudding

Does the following C program contain any undefined behavior?

int
main()
{
        struct entry
        {
                uint32_t hash;
                uint32_t idx;
        };
        entry arr[31] = {
            {   7978558,  0}, {   9241630,  1}, {  65706826,  2},
            { 639636154,  3}, {1033996244,  4}, {1225598536,  5},
            {1231940272,  6}, {1252372402,  7}, {2019146042,  8},
            {1520971906,  9}, {1532931792, 10}, {1818609302, 11},
            {1971583702, 12}, {2116478830, 13}, { 883396844, 14},
            {1942092984, 15}, {1274626222, 16}, { 333950222, 17},
            {1265547464, 18}, { 965867746, 19}, {1471376532, 20},
            { 398997278, 21}, {1414926784, 22}, {1831587680, 23},
            { 813761492, 24}, { 138146428, 25}, { 337412092, 26},
            { 329155246, 27}, {  21320082, 28}, {1751867558, 29},
            {1155173784, 30},
        };

        std::sort(std::begin(arr), std::end(arr),
                  [](entry a, entry b) { return a.hash <= b.hash; });
}

When I compile with gnu c compiler or any clang/llvm after 12.0.0, the program works fine. However, when I compiled it with clang version 12.0.0 (the default compiler shipped on my Mac laptop), it crashed inside of std::sort() as following:

$ g   --version
Configured with: --prefix=/Library/Developer/CommandLineTools/usr --with-gxx-include-dir=/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c  /4.2.1
Apple clang version 12.0.0 (clang-1200.0.32.2)
Target: x86_64-apple-darwin21.3.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin
$ g   -g -std=c  11 bug.cc
$ ./a.out
Segmentation fault: 11

Also if I change it to use std::vector instead of fixed size array. The std::sort() will never return when compiled with clang 12.0.0

CodePudding user response：

Yes, the comparator is not a strict weak ordering which violates the preconditions of std::sort, resulting in undefined behavior.

For two arguments a and b (possibly identical), a strict weak ordering comp should never evaluate both comp(a,b) and comp(b,a) to true. In other words, it should model the behavior of the built-in <, not <=.

So in your code it should be <, not <=, to make it a strict weak ordering.