[Nauty] Undefined behavior in nauty (Going over bounds)

[Mathieu Dutour]

>
> Not so fast.
>
Yes, indeed I was too fast.

There is a structural type declared like this:
>
> typedef struct permnodestruct
> {
>      struct permnodestruct *prev,*next;   /* prev&next in circular list */
>      unsigned long refcount;              /* number of references */
>      int nalloc;                          /* size of p[] in ints,
>                                              <= 0 for a perm marker */
>      int mark;                            /* a mark, 0 unless changed */
>      int p[2];                            /* actual vector, extended to
>                                              nalloc enties */
> } permnode;
>
> Variables of this type are allocated in newpermnode() thus:
>
>      malloc(sizeof(permnode)+(n-2)*sizeof(int));
>
> This allocates enough space for the member p to hold n ints. (The case
> n=1 doesn't occur, but I don't remember why I used [2] instead of [1].)
>
Thank you, I did not know about this construction. The name is "struct
hack".

This is a traditional way of having a dynamically-sized array in a
> structure.
>
Yes, it is popular and traditional. However, it does appear to be
undefined behavior.
See, e.g.
http://c-faq.com/struct/structhack.html
http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_051.html
https://stackoverflow.com/questions/3711233/is-the-struct-hack-technically-undefined-behavior

But here we see an awkward portability problem.  In the C99 standard,
> the correct way to achieve this is to use an "incomplete array", like this:
>
>      int p[];
>
Those are named "flexible array members" and they were introduced in C99.

The ANSI C standard and
> ISO C (C89/90) explicitly forbade structure members of incomplete type.
>
Yes, the flexible array members were introduced as a solution to the struct
hack
problem.

I don't know about C95 or post-C99 standards.
>
> See here for some discussion:
> https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html
>
> I'm not going to require nauty users to have C99-compatible compilers,
> and I know as a fact that many don't.

I understand your wish. However, my wish is to run conformant code
without undefined behavior since those may cause some problem at one
point or another.

I try conservatively to not use
> features newer than ANSI C unless necessary.

I completely understand your wish.


> Perhaps I should add this issue to the configuration script.

That would be much welcome. A defined statement like C99_CONFORMANT
would be very useful.


> On the other hand, I can't see anything
> in the C99 standard to forbid my usage

I think the http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_051.html
is quite explicit about it not being legal.
The solution adopted by the C standard was "flexible array members". Thus
I think that struct arrays were never legal.


> and the sanitizers in gcc+clang
> do not define what is legal.
>
The definition of what is legal or not is not in the saninitizer, but in
the norm.

Thank you very much for your explanations and of course for nauty!

  Mathieu