Draft pre-DR on type compatibility intransitivity

["Joseph S. Myers" <jsm at polyomino dot org dot uk>]

Here's the promised draft pre-DR on issues related to intransitivity
of type compatibility in C, and related matters (the "IMA vs tree-ssa"
thread from February and March), intended to go to the UK C Panel for
discussion and potential submission as a DR if it is agreed that there
are defects present.  I hope this captures accurately the issues from
that discussion.  Comments and corrections welcome.

Pre-DR: Type compatibility intransitivity
=========================================

Type compatibility is not transitive.  For example:

enum e1 { A };
enum e2 { B };
// Suppose that enum e1 and enum e2 are both compatible with int.
// (6.7.2.2#4: an enum is compatible with an implementation-defined
// one of char, a signed integer type or an unsigned integer type.)
// Then they are nevertheless not compatible with each other.
enum e1 a;
enum e2 *b = &a; // Constraint violation.

I think this is clear from the text of the standard, but some
implementations reportedly do not implement this and it isn't clear
whether this is intended.

Question 1: Are enum e1 and enum e2 above indeed incompatible types?

Despite such incompatibility, type-based alias analysis (6.5#7) must
allow for these types to alias.  For example,

int f(enum e1 *a, enum e2 *b) { int x = *a; *b = x + 2; return *a; }

must allow for the write to *b changing *a, since f could have been
called as

  int x;
  f((enum e1 *)&x, (enum e2 *)&x);

where the object has declared type (and so effective type) int, so the
accesses through both types enum e1 and enum e2 are permitted.

Another case of intransitivity arises when there are multiple
translation units:

// TU 1:
struct s;
struct t { struct s *a; };

// TU 2:
struct s { int p; };
struct t { struct s *a; };

// TU 3:
struct s { long q; };
struct t { struct s *a; };

where struct t in TU 1 is compatible with that in TU2 and TU3 but they
are not compatible with each other.

C++ avoids problems with such cases by giving types linkage.  In C
types do not have linkage, and such incompatibilities can give rise to
several problems.  The requirement of 6.2.7#2 that "All declarations
that refer to the same object or function shall have compatible type;
otherwise, the behavior is undefined." does not seem sufficient to
avoid all such problems.

Question 2: Does 6.2.7#2 refer to the types immediately after the
declarations, or the types at any point where the declarations are in
scope?

If each of the above three translation units started "struct t *x;",
would there be undefined behavior?

Even if the requirement applies to the types anywhere in scope, this
may not be enough.  Each translation unit above could have prepended
to it

struct t;
static void f(void) { extern struct t *x; }

and the incompatible completions are not within the scope of x.  (x
might then be defined in another translation unit that just says
"struct t *x;".)

The above example at least leads to incompatible "ultimate" types for
x that the object has at the end of each translation unit, albeit
outside the scope of the declaration.  But now consider the following
three translation units.

// TU 1:
struct s;
struct t { struct s *a; };
int g1(struct s *);
int g2(struct s *);
int f(struct t *p, int x) { return x ? g1(p->a) : g2(p->a); }

// TU 2:
struct t { int b; };
struct s { int a; struct t *z; };
int g1(struct s *p) { return p->a  + p->z->b; }

// TU 3:
struct t { long c; };
struct s { struct t *z; long a; };
int g2(struct s *p) { return p->a + p->z->c; }


Each object and function has a well-defined complete type.  But a
struct t in TU 1 may contain pointers to two different versions of
struct s, and each of these contains pointers to an entirely different
struct t from that in TU 1.  This requires very strange gymnastics for
an implementation inlining across translation units to inline g1 and
g2 into f.  There is no single translation unit representing a natural
merger of the three above; renaming static objects with conflicting
names does not suffice (indeed, there are no such objects), and
renaming type names used in different names in different translation
units does not help either because there is no single natural
expression of a recursive completion of TU 1's struct t.

Question 3: Is an implementation required to accept compiling the
three translation units above together into a program?

-- 
Joseph S. Myers
jsm@polyomino.org.uk