Variable-length strings in structures and undefined behavior causing time travel

Question

In this Stackoverflow question or in the article Undefined behavior can result in time travel (among other things, but time travel is the funkiest) one may learn that accessing data structures at indexes greater than their size is undefined behavior, and when a compiler sees undefined behavior, it generates crazy code without even reporting that undefined behavior was encountered. This is done to make code run a few nanoseconds faster and because the standard permits it. So-called "time travel" appears because the compiler operates on control-flow branches, and when it sees undefined behavior in a branch, it just deletes that branch (on the basis that any behavior will do in place of undefined behavior).

Nevertheless, here is an old idiom:

struct myString {
    int length;
    char text[1];
}

used as

    char* s = "hello, world";
    int len = strlen(s);
    myString* m = malloc(sizeof(myString) + len);
    m->length = len;
    strcpy(&m->text,s);

and now, what will happen if I access m->text[3]? (Note how it is declared.) Will the compiler take it as undefined behavior? If yes, how do I add an array of statically unknown amount of items to the end of a structure?

In particular, I am interested in an array whose size is at least 1, but maybe more. Sort of,

struct x {
    unsigned u[1];
};

and access like `struct x* p; ... p->x[3]`.

UPD related: Is the "struct hack" technically undefined behavior? (as @mafso has noted in a comment).

Answer 1

It may be an old idiom, but it is undefined behavior in both C and C++. Since C99, you can write something like:

struct MyString
{
    int length;
    char text[];
};

and use it as you describe (although you will probably need to add 1 to the length in the malloc). In C++, you need to jump through a few more hoops:

struct MyString
{
    int length
    char* text()
    {
        return reinterpret_cast<char*>( this + 1 );
    }
};

For anything other than char, however, you'll need to watch out for alignment restrictions, since the compiler doesn't know that the end of the struct must be aligned correctly for what follows. (G++ uses, or at least used, something like this in its implementation of std::basic_string. And instantiations like std::basic_string<double> would crash on machines where size_t was only 4 bytes, and accessing a double required 8 byte alignment.)

Answer 2

To answer your question, the compiler have no bounds-checking of array indexes, which is why flexible arrays works. You can use any index in any array.

Answer 3

You seem to have an odd idea about the meaning of "undefined behavior". Compilers are not required to recognize code that results in undefined behavior, and if they do, they are not required to do anything in particular with it. One very reasonable approach, in fact, is to do nothing special with it at all. The undefinedness is not about the machine code the compiler may generate, but rather about the effect of running it.

With that said, there is a subtle but very important difference between arrays and pointers. Arrays (such as char text[1]) have associated storage, whereas pointers (char *text or char text[]) do not.

what will happen if I access m->text[3]? (Note how it is declared.) Will the compiler take it as undefined behavior?

Well, the first undefined behavior is associated with this earlier statement:

strcpy(&m->text,s);

m->text refers to a char array of length 1, and the strcpy() will write past its end. As far as definedness goes, the fact that you reserve extra space in the block allocated for your struct is irrelevant. In practice, it probably does what you intend, but it's a terrible idea to depend on that.

Similar applies to accessing m->text[3]. The compiler is more likely to recognize the out-of-bounds access, but even if it does, the effect is likely to be what you intend. "Likely", but not certain. That's why relying on undefined behavior is to be avoided.