T* versus char* pointer arithmetic

Question

Assume we have an array that contains N elements of type T.

T a[N];

According to the C++14 Standard, under which conditions do we have a guarantee that

 (char*)(void*)&a[0] + n*sizeof(T) == (char*)(void*)&a[n],  (0<=n<N) ?

While this is true for many types and implementations, the standard mentions it in a footnote, and in an ambiguous way:

§5.7.6, footnote 85) Another way to approach pointer arithmetic ...

There is little indication that this other way was thought of being equivalent to the standard's way. It might rather be a hint for implementers that suggests one of many conforming implementations.

---

Edits:

People have underestimated the difficulty of this question.

This question is not about what you can read in textbooks, it is about what what you can deduce from the C++14 Standard through the use of logic and reason.

If you use 'contiguous' or 'contiguously', please also say what is being contiguous.

While T[] and T* are closely related, they are abstractions, and the addition on T* x N may be defined by the implementation in any consistent way.

The equation was rearranged using pointer addition. If p points to a char, p+1 is always defined using (§5.7 (4)) or unary addition, so we don't run into UB. The original included a pointer subtraction, which might have caused UB early on. (The char pointers are only compared, not dereferenced).

Jamestown

Shouldn't this be always true? – Ethiopic

I'm not even convinced that that pointer arithmetic has formally defined behavior. – Airing

Note that pointer arithmetic is valid in the range 0<=n<=N, and that also applies to scalars. – Scarface

In the published C++14 standard, doesn't [expr.add]/7 answer your question? The answer being, as far as I can tell, under no conditions, sadly. In the current draft, that's paragraph 6 (slightly relaxed, but it still doesn't allow that subtraction). – Turquoise

If the paragraph quoted above applies to subtraction, it applies to addition just as well. p + 1 is defined, but that doesn't mean p + anything is also defined. The published C++14 standard text is recognized to have some defects in this area. Some have been fixed (see P0137), some still need work (for example, CWG1701). Keep in mind that P0137 clarified that a and a[0] are not pointer-interconvertible. It's not just about layout, it's also about restrictions imposed to allow optimizations. – Turquoise

@Turquoise '... a pointer to a to a nonarray object behaves the same as a pointer to the first element of an array of length one...' I thought of this as a free pass to iterate the p->p+1 mapping for char pointers, unless end of memory is reached. If that's false, then the problem is more severe than I thought. You really think that the proposition is not even guaranteed for T==char? – Jamestown

@HeikoBloch Iterate through char* to the end of memory? No, that will never be allowed by the standard. That would mean that if you had a function taking a char*, you could legally access the value of any object in the program through that pointer, making the aliasing rules (for example) irrelevant. – Turquoise

Remember that the array subscript operator is defined in terms of pointer arithmetic in C: a[b] is equivalent to *(a+b), which is also the reason why it is also equivalent to b[a]. With C++ operator overloading, this principle has deteriorated somewhat, nevetheless it places a very firm restriction on the layout of any C-style array. And that restriction guarantees that your equivalence must be true. – Condillac

@Turquoise I think if you add 1 at a time and launder it after each addition, it should work...? – Airing

@Airing Do you mean within the array in the question, or are you referring to the "iterate to the end of memory" in the comments? The way I understand it, I don't think you can launder a pointer past the end of an object, because the reachability requirement in [ptr.launder] can't be satisfied. The pointer doesn't point to an actual object, so there's no associated storage, so no bytes can be reachable from that pointer. Besides, the notion of reachable seems to be defined only if we start from a pointer value that points to an object. – Turquoise

@Turquoise Not to the end of memory, of course. That's as undefined as always. I think you are right that the reachability clause prevents laundering past-the-end pointers. – Airing

@Airing Phew... I was wondering whether I had missed something. So, I guess this leaves us with the fact that we currently can't legally memcpy a whole int[7] using an int* to its first member (in a way, similarly to how we can't flatten an int[3][7] to an int[21]); we have to either use a pointer to the array itself, or reinterpret_cast the int* to int (*)[7] and launder it. And if the "array" was created by new int[nonconstant]... we can't memcpy that at all. Hmmm... It would be nice if CWG1701 and 2182 could be resolved in time for C++17. – Turquoise

@bogdan: The Standard would allow an implementation to behave as though every separate allocation is its own memory space, and attempts to index a pointer outside its memory space would yield UB, but if a 32-byte PODS s contains unsigned char foo[16]; as its first member, laundering that pointer should give an unsigned char* that can access the whole struct. – Incommensurable

@Incommensurable Yes, that is pretty much what I've said above. Going from an unsigned char (*)[16] pointing to that array to a PODS* wouldn't even need a launder, as the two objects are pointer-interconvertible; a reinterpret_cast is enough. Going from an unsigned char* pointing to the first element of the array member to a pointer to the array, however, requires a launder. The array element and the array itself are not pointer-interconvertible, so the array element and the containing PODS aren't either. The subsequent unsigned char* thing requires a suitable resolution of CWG1701. – Turquoise

@Incommensurable But if you meant that unsigned char* p = std::launder(foo); will give you a p that allows you to access the whole PODS object, I don't think that's how it works. I think what's needed is unsigned char* p = reinterpret_cast<unsigned char*>(std::launder(reinterpret_cast<PODS*>(foo)));. The inner cast gives a pointer that, although of type PODS*, still points to the first unsigned char element of foo. The launder gives a pointer that points to the whole struct, and the outer cast yields a pointer that still points to the struct, and so can access the whole object. – Turquoise

@bogdan: That makes sense, though I'm curious what the expected migration path would be for code that was written for earlier standards which didn't distinguish between a char* that can only access an inner object versus one that can access an outer object, and where code might receive a pointer and a size, and need to be able to use memcpy to copy the indicated number of bytes without necessarily knowing the enclosing type. – Incommensurable

@Incommensurable That's a good point. As far as I understand, the new wording formalizes things that optimizing compilers were already doing, so it's unlikely that code that worked before will start acting up now. And it's not finished; some things are still not covered. – Turquoise

@Incommensurable That being said, I just realized that my code above is wrong, because not all bytes of the PODS object are reachable through a pointer to the first array element, so we can't launder directly. If p_elem points to the first array element, then we need this: unsigned char* p = reinterpret_cast<unsigned char*>(reinterpret_cast<PODS*>(std::launder(reinterpret_cast<unsigned char (*)[16]>(p_elem))));. – Turquoise

@bogdan: Yikes. It would seem there oughta be some way of saying "don't assume you know anything about that pointer". Doing that within a loop would often be bad for performance, but being able to do it before a loop may ease aliasing issues within the loop. – Incommensurable

Let us continue this discussion in chat. – Turquoise

Does it really matter that much?The standard codifies existing practice. That's its purpose in life. If it fails to do so in a clear unambiguous manner, it needs to be fixed. If you need to jump through hoops in order to either prove or disprove your assumption, this is a defect in the standard, not a logic puzzle waiting to be solved. – Censorship

@n.m. It's a question about who is to be held liable in case of error: the one who wrote the sourcecode or the compiler vendor. If someone is liable for software defects at all, the standard may be used as legal document that determines who. This may be important to insurance companies. – Jamestown

Yeah, more lawyers telling us how to program, that's what we need. Is this code UB? Call Steve from legal! – Censorship

Answer 1

In [dcl.array]:

An object of array type contains a contiguously allocated non-empty set of N subobjects of type T.

Contiguous implies that the offset between any consecutive subobjects of type T is sizeof(T), which implies that the offset of the nth subobject is n*sizeof(T).

The upper bound of n < N comes from [expr.add]:

When an expression that has integral type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the expression P points to element x[i] of an array object x with n elements, the expressions P + J and J + P (where J has the value j) point to the (possibly-hypothetical) element x[i + j] if 0 <= i + j < n; otherwise, the behavior is undefined.

Generality

See the definition of contiguously in (§23.3.2.1), which says that 'contiguously' only means 'array arithmetic is compatible with pointer arithmetic'. Compare #39792306 – Jamestown

@HeikoBloch There is no such definition in the latest working draft. – Generality

I refer to the sentence: 'The elements of an array are stored contiguously, meaning that, ...'. While it is no formal definition, it is the sentence that comes closest. – Jamestown

@HeikoBloch std::array is not an array. – Generality

But the sentence suggests that the words contiguously (in allocated or stored contiguously) and contiguous (in sequence of contiguous bytes) are used with slightly different meanings, and that would help resolve other apparent contradictions. – Jamestown

@HeikoBloch The library section does not define terms for the language section. The two are distinct. – Generality

Let us continue this discussion in chat. – Jamestown

I consider 'Contiguous implies that the offset ... is sizeof(T)' obvious only in case objects of type T are bound to be contiguous in the first place. And if the authors had meant such a simple formula, why haven't they written it down? – Jamestown

@HeikoBloch "contiguously... and contiguous... are used with slightly different meanings" this could be only viewed as a defect in the standard. – Censorship

@Barry: "the latest working draft" and C++14 are not the same thing. I believe we've had this discussion before... – Blanks

@LightnessRacesinOrbit I'm not sure there is one document that is exactly C++14. There's the draft that's closest to when C++14 was finalized, but then that wouldn't include any of the defect reports since then, so that's not really C++14 either. Regardless, in a draft that has that section (e.g. N3242), that section refers to std::array, not arrays. – Generality

@Barry: I think it's fairly clear that the current (14th October 2016) working draft is a lot closer to C++17 than it is to whatever you end up calling C++14 (which I consider to be FDIS + new cover page, though I accept that some subsequent DRs sort of count too). – Blanks

@Generality Please add an answer to the question to your post and explain your notion of contiguity. Especially, how can contiguity requirements impose a particular order on the subobjects? (If that's what you intended) – Jamestown

Answer 2

It's always true, but instead of looking at the rules for pointer arithmetic you must rely on the semantics given for the sizeof operator (5.3.3 [expr.sizeof]):

When applied to a reference or a reference type, the result is the size of the referenced type. When applied to a class, the result is the number of bytes in an object of that class including any padding required for placing objects of that type in an array. The size of a most derived class shall be greater than zero. The result of applying sizeof to a base class subobject is the size of the base class type. When applied to an array, the result is the total number of bytes in the array. This implies that the size of an array of n elements is n times the size of an element.

It should be clear that there's only one packing that puts n non-overlapping elements in space of n * sizeof(element), namely that they are regularly spaced sizeof (element) bytes apart. And only one ordering is allowed by the pointer comparison rules found under the relational operator section (5.9 [expr.rel]):

Comparing pointers to objects is defined as follows:

• If two pointers point to different elements of the same array, or to subobjects thereof, the pointer to the element with the higher subscript compares greater.

Deformation

Do you mean there is no need for the contiguity requirement in [dcl.array] at all? – Jamestown

Answer 3

The declaration in the first line is also a definition. (§3.1(2)) It creates the array object. (§1.8(1))

An object can be accessed via multiple lvalues due to the aliasing rules. (§3.10(10)) In particular, the objects on the right hand side may be legally accessed (aliased) through char pointers.

Lets look at a sentence in the array definition and then disambiguate 'contiguous'.

"An object of array type contains a contiguously allocated non-empty set of N subobjects of type T." [dcl.array] §8.3.4.

---

Disambiguation

We start from the binary symmetric relation 'contiguous' for char objects, which should be obvious. ('iff' is short for 'if and only if', sets and sequences are mathematical ones, not C++ containers) If you can link to a better or more acknowledged definition, comment.

A sequence x_1 ... x_N of char objects is contiguous iff x_i and x_{i+1} are contiguous in memory for all i=1...N-1.

A set M of char objects is contiguous iff the objects in M can be numbered, x_1 ...x_N, say, such that the sequence (x_i)_i is contiguous. That is, iff M is the image of a contiguous, injective sequence.

Two sets M_1, M_2 of char objects are contiguous iff there exist x_1 in M_1 and x_2 in M_2 such that x_1 and x_2 are contiguous.

A sequence M_1 ... M_N of sets of char objects is contiguous iff M_i and M_{i+1} are contiguous for all i=1...N-1.

A set of sets of char objects is contiguous iff it is the image of a contiguous, injective sequence of sets of char objects.

Now which version of 'contiguous' to apply? Linguistic overload resolution:

1) 'contiguous' may refer to 'allocation'. As an allocation function call provides a subset of the available char objects, this would invoke the set-of-chars variant. That is, the set of all char objects that occur in any of the N subobjects would be meant to be contiguous.

2) 'contiguous' may refer to 'set'. This would invoke the set-of-sets-of-chars variant with every subobject considered as a set of char objects.

---

What does this mean? First, while the authors numbered the array subobjects a[0] ... a[N-1], they chose not to say anything about the order of subobjects in memory: they used 'set' instead of 'sequence'. They described the allocation as contiguous, but they do not say that a[j] and a[j+1] are contiguous in memory. Also, they chose not to write down the straightforward formula involving (char*) pointers and sizeof(). While it looks like they deliberately separated contiguity from ordering concerns, §5.9 (3) requires one and the same ordering for array subobjects of all types.

If pointers point to two different elements of the same array, or a subobject thereof, the pointer to the element with the higher subscript compares greater.

Now do the bytes that make up the array subobjects qualify as subobjects in the sense of the above quote? Reading §1.8(2) and Complete object or subobject? the answer is: No, at least not for arrays whose elements don't contain subobjects and are no arrays of chars, e.g. arrays of ints. So we may find examples where no particular ordering is imposed on the array elements.

But for the moment let's assume that our array subobjects are populated with chars only. What does this mean considering the two possible interpretations of 'contiguous'?

1) We have a contiguous set of bytes that coincides with an ordered set of subobjects. Then the claim in the OP is unconditionally true.

2) We have a contiguous sequence of subobjects, each of which may be non-contiguous individually. This may happen in two ways: either the subobjects may have gaps, that is, they contain two char objects at distance greater than sizeof(subobject)-1. Or the subobjects may be distributed among different sequences of contiguous bytes.

In case 2) there is no guarantee that that the claim in the OP is true.

Therefore, it is important to be clear about what 'contiguous' means.

---

Finally, here's an example of an implementation where no obvious ordering is imposed on the array subobjects by §5.9 because the array subobjects don't have subobjects themselves. Readers raised concerns that this would contradict the standard in other places, but no definite contradiction has been demonstrated yet.

Assume T is int, and we have one particular conforming implementation that behaves as expected naively with one exception:

It allocates arrays of ints in reversed memory order, putting the array's first element at the high-memory-address end of the object:

a[N-1], a[N-2], ... a[0]  

instead of

a[0], a[1],   ... a[N-1]  

This implementation satisfies any reasonable contiguity requirement, so we don't have to agree on a single interpretation of 'contiguous' to proceed with the argument.

Then if p points to a, mapping p to &a[0] (invoking [conv.array]) would make the pointer jump near the high memory end of a. As array arithmetic has to be compatible with pointer arithmetic, we'd also have

int * p= &intVariable;
(char*)(p+1) + sizeof(int) == (char*)p

and

int a[N];

(char*)(void*)&a[n] + n*sizeof(int)==(char*)(void*)&a[0],  (0<=n<N)

Then, for T=int, there is no guarantee that the claim in the original post is true.

---

edit history: removed and reintroduced in modified form a possibly erroneous shortcut that was due to not applying a relevant part of the pointer < relation specification. It has not been determined yet whether this was justified or not, but the main argument about contiguity comes through anyway.

Jamestown

Uh, indexing into an array is defined as addition. How do you figure you're allowed to go backwards? – Generality

"They described the allocation as contiguous, but they do not say that a[j] and a[j+1] are contiguous in memory." What do you think contiguous means in that context? Your interpretation is apparently that it's purely decorative. – Generality

@Generality Answered your question. It's your turn. – Jamestown

"they chose not to say anything about the order of subobjects in memory" and "There is nothing in the standard that prevents the implementation from allocating arrays of ints in reversed memory order" is totally false, section 5.9 most certainly requires elements to be placed in ascending order. – Deformation

@BenVoigt ascending order with respect to which pointer type? In my example, array elements are placed in ascending order with respect to int* pointers, but in descending order with respect to char* pointers. No one said pointer casts must be monotonically increasing. In the example, the (char*) cast is a decreasing function with respect to the respective ordering relations. If you find that this is not allowed -- tell me where. – Jamestown

@Heiko: I did. The rule applies just as well considering char* pointing into your array as int*. – Deformation

And then there's also the whole fact that +0 has to be a no-op. – Deformation

section 4.2 says "An lvalue or rvalue of type 'array of N T' or 'array of unknown bound of T' can be converted to a prvalue of type 'pointer to T'. The result is a pointer to the first element of the array." Please explain how your descending-order system makes this work for arrays of unknown bound. Don't forget that all arrays with the same element type have to use the same ordering scheme, the same scheme used by int*. – Deformation

Please also explain how placement new works on arrays in your descending-order scheme, given that: (1) it must return a pointer to the initial element -- see 5.3.4 and (2) it must return the same pointer passed in -- see 18.6.2.3 – Deformation

In summary, when the actual requirements of the Standard are considered, your analysis has more holes in it than a block of swiss cheese. – Deformation

@BenVoigt 18.6.2.3 is type new_handler, you mean 18.6.1.3 (5)?? The array new expression needs not return the same address as the allocation function anyway, 5.3.4 (14). +0 applied to what? If you mean a+0, a standard conversion kicks in, so the +0 is non-op, but the standard conversion not. Arrays with unknown bound have incomplete type, so there will be no objects of that type. The 'and subobjects thereof' part in the definition of the ordering relation was the thing I was missing. – Jamestown

@BenVoigt 'I did. The rule applies just as well...' this depends on whether the char lvalues that alias the array count as subobjects. This may be the case, but it is not obvious to me. – Jamestown