Legalization of empty objects

2016-06-24 Permalink

For many novice C++ programmers[1] it comes as a surprise that empty classes are of non-zero size:

struct E {};
assert(sizeof(E) == 1);

A proof is that this is a recurring question on many forums and Q&A sites. People are further surprised when they accidentally discover the empty-base optimization, which permits empty sub-objects to be of zero size, but only in some circumstances:

struct F {};
struct B : E { F x; };
assert(sizeof(B) == 1); // empty base optimization works!

struct C : E { E x; };
assert(sizeof(C) == 2); // WAT!?

The canonical explanation of sizeof(E) == 1 comes from BS himself, who says that it’s specified so ‘to ensure that the addresses of two different objects will be different’. However, despite an intensive search, I couldn’t find anywhere an explanation of why this requirement is necessary for empty objects.

Worms

There is a deeper reason, however. It is that there are places where we divide by sizeof(E), even implicitly by compiler generated code. If empty objects were of zero size, then the following code would fail to compile:

E a[10], *p, *q;
int size = sizeof(a)/sizeof(E); // error: division by zero
int diff = q - p; // error: division by zero (implicit)

Actually, if you think about it, this would be logical... but it doesn’t stop here. For zero-sized types the following two loops would iterate a different number of times:

for(int i = 0; i < 10; ++i) f(a[i]);
for(p = a, q = a + 10; p != q; ++p) f(*p);

This is a big deal. Both methods are routinely interchanged today, and we have no way to guarantee that only one of them will always be used. There is not even a reason to favor one loop over the other:

If we think of E[10] as 10 distinct objects of type E, then the first loop is the correct way to iterate.[2] This is the traditional way of iterating over a contiguously allocated sequence. Pointers wouldn‘t do as iterators of C arrays anymore as we would need a base pointer plus an index to reference each individual element in the array.
Alternatively, we can define that for empty types E[n] is the same as E[0] for all n (sure, empty arrays aren‘t permitted in C++, but once we allow zero-sized types we can fix that as described bellow). In such case the second loop would be the correct way to iterate. This is also the idiomatic STL approach to iterate over sequences, and we could continue using native pointers as iterators over C arrays.

This is a tough dilemma which I still cannot decide. Each time I think about it my brain explodes in a division by zero accident.

Yet not all is lost. Notice that all the problems listed above stem in arrays of empty types, but the main use of empty types is not in their arrays. Instead they are heavily used, even unknowingly, as template arguments (e.g. the default std::vector allocator) or extra function parameters for overload resolution (e.g. iterator category tags).

Zero is a natural number

As a wildly used advanced language that recognizes zero-based indices it is strange that C++ still struggles recognizing the concept of emptiness. Let‘s fix this with some language surgery. See the exact standardese wording in the end of the article.

Empty objects

We allow empty objects to have zero size. We allow creating such objects but not performing pointer arithmetic on them or creating arrays thereof. Empty base optimization is not longer needed, because empty objects are now permitted to be densely packed into the same address, even if they are of the same type. The constructors and destructors of such objects are called per each declared instance, even if it means calling the same constructor or destructor with the same this address twice.

struct E {
	E() { printf("I'm empty\n"); }
	~E() { printf("I'm dtor\n"); }
};

struct A {
	int a; // +0
	E b, c; // +4, +4
	int d; // +4
};
assert(sizeof(A) == 8);

A x; // prints "I'm empty" twice
x.c.~E(); // prints "I'm dtor"
// don't know whether calling x.c.~E() again is defined or not,
// but you should not do that.

x.b.~E(); // prints "I'm dtor" again

struct B : E { E x; };
assert(sizeof(B) == 0);

E a[10]; // error: cannot declare arrays of empty type
E *p = new E; // ok
++p; // error: pointer arithmetic on empty types is not allowed
p[2]; // error: pointer arithmetic on empty types is not allowed

Empty arrays

Once we allow types and objects of zero size, there is no reason to disallow zero-sized arrays. They are allowed too, though still require a non-empty element type. We can now use trailing arrays similar to those of C:

struct S {
	int size;
	char data[0]; // in C we use an incomplete type char[] instead
};
assert(sizeof(S) == 4);

The `void`

ISO C++ treats void as an incomplete type, with some special wording allowing casting to void and returning void values from functions:

int f(int a) {
	(void)a; // unused parameter
	return 1;
}

void g() {
	return void(f(2));
}

Even though it looks like the return statement in g creates a void temporary, it does not, because there can‘t be void objects in ISO C++. Instead, let‘s redefine void to be a complete empty type. Now we can use it in a bunch of other situations that would otherwise be ill-formed:

assert(sizeof(void) == 0);

template<class T>
class X { T x; };
X<void> x; // ok

void a[10]; // error: cannot declare arrays of empty type
void *p = new void; // ok, returns non-null
void *q = new void; // ok, may return q == p, but probably won't on typical implementations
void y = *p; // ok
++p; // error: pointer arithmetic on empty types is not allowed
delete p;
delete q; // shall succeed even if p == q

Rationale

You might be asking why we would want to change anything, and if we do then why this and not another way? Here are the principles I follow:

Principle of least surprise. As experience shows, people are surprised by sizeof(E) == 1, EBO, and that empty arrays are disallowed by the standard even though they are supported by multiple compilers. I expect that the new rules better match people‘s expectations.
What you don’t use, you don‘t pay for. I don‘t want to pay with extra bytes plus alignment for empty objects when they arise—usually as parameters to generic code. If somebody really needs to guarantee uniqueness of empty object addresses, e.g. to insert/delete them into a global registry map, she can always state this explicitly by making the object non-empty through insertion of a dummy char member.
Uniformity. There shall be as few special cases as possible: in user-code, in the library implementation, in the compiler and in the standard, in that order of preference. Currently to avoid paying for empty objects in generic code, the author of that code is responsible for employing EBO. It appears that when we increase uniformity of the standard by extending the ‘natural’ behavior to the edge cases, then the compiler, the library and the user-code get simpler.
If it doesn‘t make sense, leave it undefined or ill-formed. This is where the restrictions on the empty types stem.

Currently ISO C++ violates the first three principles, and this is what I am trying to fix here.

Proposed wording

This is a diff relative to the WG21 N3337 core. Due to the scope of the change there might be a lot of places I missed or other inconsistencies. This diff permits empty objects to be of zero size, but does not require them to be so. Note that EBO isn‘t mandatory in ISO C++ either.

Replace all ~~incompletely-defined object type~~ with incomplete type.
Replace all ~~object type or void~~ with object type.
Replace all ~~incomplete object type or void~~ with incomplete type.
§1.8/5 ~~Unless it is a bit-field (9.6), a most derived object shall have a non-zero size and shall occupy one or more bytes of storage. Base class subobjects may have zero size.~~Objects occupy zero or more bytes of storage.
§1.8/6 Unless an object is a bit-field or ~~a base class subobject~~an object of zero size, the address of that object is the address of the first byte it occupies. Two objects that are not bit-fields may have the same address if one is a subobject of the other, or if at least one is ~~a base class subobject~~an object of zero size~~and they are of different types~~; otherwise, they shall have distinct addresses.⁴
§3.9/5 A class that has been declared but not defined, or an array of unknown size or of incomplete element type, is an incomplete~~ly-defined object~~ type.⁴³~~Incompletely-defined object types and the void types are incomplete types (3.9.1).~~
§3.9/8 An object type is a (possibly cv-qualified) type that is not a function type,and not a reference type~~, and not a void type~~.
§3.9/9 Arithmetic types (3.9.1), enumeration types, pointer types, pointer to member types (3.9.2), std::nullptr_t, void, and cv-qualified versions of these types (3.9.3) are collectively called scalar types.
§3.9/9+ An empty type is an empty class (Clause 9) or void.
§3.9.1/9 The void type has an empty set of values. ~~The void type is an incomplete type that cannot be completed.~~ It is used as the return type for functions that do not return a value. Any expression can be explicitly converted to type cvvoid (5.4). An expression of type void shall be used only as an expression statement (6.2), as an operand of a comma expression (5.18), as a second or third operand of ?: (5.16), as the operand of typeid or decltype, as the expression in a return statement (6.6.3) for a function with the return type void, or as the operand of an explicit conversion to type cvvoid.
§3.9.2/1 — arrays of objects of a given non-emptytype, 8.3.4;
§3.9.2/3 ~~[ Note: A pointer to void does not have a pointer-to-object type, however, because void is not an object type. — end note ]~~
§5.2.1/1 The type “T” shall be a completely-defined non-empty object type.
§5.2.6/1 The type of the operand shall be an arithmetic type or a pointer to a complete non-emptyobject type.
§5.3.2/1 The type of the operand shall be an arithmetic type or a pointer to a completely-defined non-emptyobject type.
§5.3.3/1 sizeof(void) is 0.
§5.3.3/2 ~~The size of a most derived class shall be greater than zero (1.8).~~
§5.7/1 For addition, either both operands shall have arithmetic or unscoped enumeration type, or one operand shall be a pointer to a completely-defined non-emptyobject type and the other shall have integral or unscoped enumeration type.
§5.7/2
— both operands are pointers to cv-qualified or cv-unqualified versions of the same completely-defined non-emptyobject type; or
— the left operand is a pointer to a completely-defined non-emptyobject type and the right operand has integral or unscoped enumeration type.
§5.17/7 In += and -=, E1 shall either have arithmetic type or be a pointer to a possibly cv-qualified completely-defined non-emptyobject type.
§8.3.4/1 T is called the array element type; this type shall not be a reference type, ~~the (possibly cv-qualified) type void,~~ a function type,or an abstract class typeor a (possibly cv-qualified) empty type. If the constant-expression (5.19) is present, it shall be an integral constant expression and its value shall be greater than or equal tozero.
§9/4 ~~Complete objects and member subobjects of class type shall have nonzero size.¹⁰⁷~~
§9/6+ An empty class is a class that:
— has no non-static data members of non-empty type (or array of such types),
— has no virtual functions and no virtual base classes, and
— has no non-empty base classes.
§10/8 A base class subobject may be of zero size (Clause 9); however, two subobjects that have the same class type and that belong to the same most derived object must not be allocated at the same address (5.10).

Conclusion

C++ still suffers from a lack of uniformity when it comes to edge cases and built-in types. I have shown how it is possible to increase uniformity and simplify the language. Unfortunately everything comes at a price: the proposed modifications are incompatible with the current language standard, and as such they are unlikely to be ever adopted. One should, however, consider this in other language designs.

Footnotes

C prohibits empty structs.
Even the innocent definition of a above requires calling constructors and destructors of E equally many times, even if one of them throws in the middle. Think how the compiler would do that.