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");