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

I'm sorry if you saw my earlier comment, I was confused. It's unusual to see a 2D array of char. — Mark Ransom
– Mark Ransom, Commented Apr 17, 2023 at 21:16

HTNW · Accepted Answer · 2023-04-17 21:57:25Z

5

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).

edited Apr 17, 2023 at 21:57

answered Apr 17, 2023 at 21:16

HTNW

29.7k2 gold badges37 silver badges63 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

ocirocir Over a year ago

Indeed, it is likely a bug in GCC. strncmp is not constexpr, it shouldn't be allowed in a constexpr function.

HTNW Over a year ago

@user17732522 Actually, I'm thinking that's not necessary. The thing passed as template parameter is not the object (STRINGS) itself, but the address of its first element, and the code within the function again doesn't read any of the arrays in STRINGS, but their elements. And static-lifetime scalar constants do not need constexpr to be usable under constexpr, while dealing with addresses in constexpr only requires static lifetime and not the objects being constexpr. But marking STRINGS as constexpr would be clarifying to the reader.

HTNW Over a year ago

@user17732522 No, T[i] is itself an array, to which lvalue-to-rvalue conversion cannot be applied. Instead, array-to-pointer conversion (decay) is applied, which doesn't require the object T[i] to be usable in constant expressions. And subobjects of string literals (the actual chars of STRINGS) are usable in constant expressions automatically regardless of being marked constexpr.

user17732522 Over a year ago

@HTNW I think you are right. I did not think about this clearly.

user17732522 Over a year ago

@HTNW However, the access to the const char objects inside strncmp wouldn't be to elements of the string literal, but the nested array, and the exceptional rule not requiring constexpr for usable in constant expressions applies only to variables that are of const non-volatile integral/enumeration type, not any object or arrays thereof and usable in constant expressions applies to subobjects only if the parent object is usable in constant expressions. So accessing the const char elements of the 2D array would not be covered: godbolt.org/z/q1f1r7sdW

|

paddy · Accepted Answer · 2023-04-17 23:38:52Z

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

Collectives™ on Stack Overflow

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

2 Answers 2

6 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related