Verify an array of fixed-length character strings is sorted at compile time

Question

When trying to verify an array of fixed-length character strings is sorted at compile time, there is odd behavior in using strncmp.

If the validation function references the global array, all values of N seem to work.

#include <cstring>

#define N 8 // vary values of N

const char STRINGS[][N] = {"a", "b", "c"};

constexpr bool is_sorted_global() {
    for (int i = 0; i < sizeof(STRINGS) / N - 1; i++) {
        if (strncmp(STRINGS[i], STRINGS[i + 1], N) > 0) {
            return false;
        }
    }

    return true;
}

int main()
{
    // always works for any N
    static_assert(is_sorted_global(), "list is not sorted");
}

However, if using a function template, only values where N is less than or equal to 8 seem to work.

template<const char T[][N]>
constexpr bool is_sorted_t() {
    for (int i = 0; i < sizeof(T) / N - 1; i++) {
        if (strncmp(T[i], T[i+1], N) > 0) {
            return false;
        } 
    }

    return true;
}

int main()
{
    // only works for N <= 8
    static_assert(is_sorted_t<STRINGS>(), "list not sorted");
}

For example, with N = 9, the template approach will error with...

C:\msys64\mingw64\bin\g++.exe -fdiagnostics-color=always -g C:\Projects\helloworld\helloworld.cpp -o C:\Projects\helloworld\helloworld.exe

C:\Projects\helloworld\helloworld.cpp: In function 'int main()':
C:\Projects\helloworld\helloworld.cpp:34:39: error: non-constant condition for static assertion
   34 |     static_assert(is_sorted_t<STRINGS>(), "list is not sorted");
      |                   ~~~~~~~~~~~~~~~~~~~~^~
C:\Projects\helloworld\helloworld.cpp:34:39:   in 'constexpr' expansion of 'is_sorted_t<(& STRINGS)>()'
C:\Projects\helloworld\helloworld.cpp:23:25: error: 'strncmp(((const char*)(& STRINGS)), (((const char*)(& STRINGS)) + 9), 9)' is not a constant expression
   23 |         if (std::strncmp(T[i], T[i + 1], N) > 0) {
      |             ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

Unfortunately for me, I need N to equal 16 and I have multiple global STRINGS arrays to verify, so I was hoping the function template would allow me to check each one with static assertion.

Compiler explorer link

Answer 1

Although this won't answer the question of why your compiler behaves that way for the function template, here is a solution you can use. Pass the array as a function argument instead of template parameter as follows:

template<size_t Size, size_t Len>
constexpr bool is_sorted(const char (&arr)[Size][Len]) {
    for (size_t i = 1; i < Size; i++) {
        if (strncmp(arr[i-1], arr[i], Len) > 0) {
            return false;
        } 
    }
    return true;
}

This combines the benefits of template expansion with your working "global" approach. It also relaxes the dependency on the macro N.

static_assert(is_sorted(STRINGS), "list is not sorted");

That at least works with your compiler, although as pointed out in another answer strncmp is not actually a constexpr. This works in GCC but not Clang.

To correct this, a simple modification is to define your own constexpr string comparison and also make your array constexpr:

#include <cstddef>

#define N 16

constexpr char STRINGS[][N] = {"a", "b", "c"};

constexpr int my_strncmp(const char *a, const char *b, size_t n) {
    int delta = 0;
    if (n > 0) {
        do {
            delta = (int)(unsigned char)*a
                  - (int)(unsigned char)*b;
        } while (delta == 0 && *a++ && *b++ && --n != 0);
    }
    return delta;
}

template<size_t Size, size_t Len>
constexpr bool is_sorted(const char (&arr)[Size][Len]) {
    for (size_t i = 1; i < Size; i++) {
        if (my_strncmp(arr[i-1], arr[i], Len) > 0) {
            return false;
        } 
    }
    return true;
}

static_assert(is_sorted(STRINGS), "list is not sorted");

Answer 2

strncmp and even std::strncmp are not constexpr according to the C++ standard. So, really, your code should simply never work. It appears strncmp is a GCC/Clang magic builtin, so that's probably why all the weird behavior is happening (but your compiler is actually buggy for ever letting any of your examples compile).

Write your own strncmp that is constexpr. Also, mark STRINGS as constexpr (see confusion in comments).