Is the equality relation of pointers after round-trip conversion guaranteed to be transitive?

Question

This question is similar to "Are all pointers guaranteed to round-trip through void * correctly?" but slightly deeper.

Given:

#include <stdint.h>

int i;
int *ip1 = &i;
void *vp1 = ip1;
intptr_t x = (intptr_t)vp1;
void *vp2 = (void *)x;
int *ip2 = vp2;

then vp1 == vp2 is guaranteed to be true (even though they might not share the same binary representation), but is ip1 == ip2 guaranteed to be true? I.e., is the equality relation transitive in this case?

score 6 · Answer 1 · answered Sep 14 '21 at 15:19

6

This conversion is guaranteed to work.

First, conversion from an object pointer to a void * and back is described in section 6.3.2.3p1 of the C standard:

A pointer to void may be converted to or from a pointer to any object type. A pointer to any object type may be converted to a pointer to void and back again; the result shall compare equal to the original pointer

Second, conversion from a void * to a intptr_t and back is described in section 7.20.1.4p1:

The following type designates a signed integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer:
intptr_t
The following type designates an unsigned integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer:
uintptr_t
These types are optional.

In this case, an int * (ip1) is converted to a void * (vp1), and the void * to a intptr_t.

The intptr_t is converted back to a void * (vp2). By 7.20.1.4p1, vp2 must compare equal to vp1.

Then vp2 is converted to an int * (ip2). Since vp2 is the same as vp1, the conversion of vp2 to int * is equivalent to converting the vp1 to int * and therefore will result in a pointer that will compare equal to ip1 as per 6.3.2.3p1.

answered Sep 14 '21 at 15:19

dbush

205,898
23
218
273

I guess what I'm asking is if it is possible through this chain of conversions to end up with two pointers to the same object that do not compare equal. – Ian Abbott Sep 14 '21 at 15:47
so technically speaking "pointer comparison is transitive when it is transitive" – tstanisl Sep 14 '21 at 16:13
Just to confirm, with respect to the conversion rules, is there a difference between an implicit conversion and an explicit cast? The explanations in the standard for ```void *``` and ```intptr_t``` use the same terminology ("converted"), but the code in the question explicitly casts uses of variable ```x```. – sj95126 Sep 14 '21 at 16:23
@sj95126 No difference. 6.3p1: *"Several operators convert operand values from one type to another automatically. This subclause specifies the result required from such an implicit conversion, as well as those that result from a cast operation (an explicit conversion). " – dbush Sep 14 '21 at 16:25
@dbush: OK, so the casts in the code don't need to be there? I'm not critiquing the code, just want to be sure I understand why some of the conversions have casts and others don't. – sj95126 Sep 14 '21 at 16:28
@sj95126 The casts are required in this case (i.e. to/from `void *` and an integer type) because the assignment operator doesn't allow it otherwise. – dbush Sep 14 '21 at 16:33

score 5 · Accepted Answer · answered Sep 14 '21 at 21:12

Transitivity of equality for pointers, regardless of provenance, follows from the specification of the equality operators. C 2018 6.5.9 6 says:

Two pointers compare equal if and only if both are null pointers, both are pointers to the same object (including a pointer to an object and a subobject at its beginning) or function, both are pointers to one past the last element of the same array object, or one is a pointer to one past the end of one array object and the other is a pointer to the start of a different array object that happens to immediately follow the first array object in the address space.

Dismissing null pointers and pointers to functions, which are not an issue here, given that a == b and b == c evaluate as true, they must satisfy one of the conditions listed in the specification, so we have these cases:

Given `a == b`.	Given `b == c`.	`a == c`?
`a` and `b` both point to the same object .	`b` and `c` both point to the same object.	`a` and `c` both point to the same object. Therefore `a == c` evaluates as true.
`a` and `b` both point to the same object.	`c` points to one past the last element of an array object and `b` points to the start of an array object that happens to follow it.	`c` points to one past the last element of an array object and `a` points to the start of an array object that happens to follow it. Therefore `a == c` evaluates as true.
`a` and `b` both point to one past the last element of the same array object.	`b` and `c` both point to one past the last element of the same array object.	`a` and `c` both point to one past the last element of the same array object. Therefore `a == c` evaluates as true.
`a` points to one past the last element of an array object and `b` points to the start of an array object that follows it.	`b` and `c` both point to the same object.	`a` points to one past the last element of an array object and `c` points to the start of an array object that follows it. Therefore `a == c` evaluates as true.
`b` points to one past the last element of an array object and `a` points to the start of an array object that follows it.	`b` and `c` both point to one past the last element of an array object.	`c` points to one past the last element of an array object and `a` points to the start of an array object that follows it. Therefore `a == c` evaluates as true.

Note there are no cases where b points to an object in the first column and to one past the last element of an array in the second column or vice-versa: Whichever of these two kinds of pointer it is, it must be the same kind in a == b and b == c.

The case of "`a` points to one past the last element of an array object and `b` points to the start of an array object that follows it." will not necessarily be true, due to some compilers keeping track of pointer provenance. See https://stackoverflow.com/questions/45966762/can-an-equality-comparison-of-unrelated-pointers-evaluate-to-true — dbush, Sep 14 '21 at 21:48
@dbush: It is a language-lawyer question. This is what the C standard says. — Eric Postpischil, Sep 14 '21 at 21:50
Thanks. I'm convinced by 6.5.9/6 since the two pointers to `int` must be pointing to the same `int` object (if you consider that an object is made of byte-sized subobjects and that both pointers to `void` before and after the round-trip through `intptr_t` must be pointing to the same byte at the start of the same `int` object), then they must compare equal. — Ian Abbott, Sep 15 '21 at 09:41

Is the equality relation of pointers after round-trip conversion guaranteed to be transitive?

2 Answers2