Comment by xscott | Hacker News Reader

Comment by xscott | Hacker News Reader

Parent Full thread

> It takes two pointers with the extra promise that they do not alias each other.

... and then promptly uses pointer arithmetic to create an alias. It violated the promise.

> If you view this as 'derived from', you can never satisfy any restrict guarantee on a function whose implementation you have not carefully reviewed.

This is C, not Rust. You aren't getting proofs without careful review. You're using "restrict" in order to ask the compiler to create a faster function on the promise that it will never be used in a way that the pointers alias. It's a promise that needs to be upheld within the function and for everyone who calls the function.

Think of something like `memcpy` (overlaps not allowed) vs `memmove` (overlaps allowed). The compiler can make the first one faster, and it is your job to uphold the contract.

> As for having influence: Ralf Jung has written a PhD thesis on the correctness of Rust

Appeals to authority aren't motivating to me. I've known and worked with a whole lot of PhDs, and they aren't always right. In fact, frequently the ones I've known are overly confident when they step outside of their area of expertise.

> ... and then promptly uses pointer arithmetic to create an alias. It violated the promise.

I think this is where a lot can go wrong in terms of understanding.

It was my understanding that the restrict keyword requires a promise of the caller. Specifically, the caller promises that the arguments it passes do not alias. It was my point that the `uwu` function could not violate that promise, because it wasn't the one who made it.

After review of the standard, I'm no longer certain this is the case.

Disregarding this line of reasoning entirely, I still believe the author is correct.

The following is an excerpt from the Standard (or rather the latest available draft):

> An object that is accessed through a restrict-qualified pointer has a special association with that pointer. This association, defined in 6.7.3.1 below, requires that all accesses to that object use, directly or indirectly, the value of that particular pointer

The `uwu` function complies with that requirement. While it does create an aliasing pointer derived from `y`, it never uses it to actually access memory. Hence, it does not violate the requirement imposed by restrict.

The aliasing access derived from `y` (which may well be undefined behavior after all) is only introduced after one of the optimization passes. Thus, this optimization is incorrect and may not be applied.

Edit: of course, there is an aliasing pointer in the original version of `uwu`. This pointer, however, is derived from `x`, thus not violating any guarantees implied by restrict.

> Thus, this optimization is incorrect and may not be applied.

You're right, and I was wrong in my initial take on things.

I currently believe the first version of the code is fine, but that the second version is clearly incorrect. There, you'll see it's using an address derived from `y` to modify memory modified through `x`. The translation to the second version should either not be allowed, or it should not continue to declare the arguments as `strict`.

As for the promise that `strict` makes, I interpret to be a promise both about the function and a promise from all callers of the function. In other words, it's a promise from the programmer(s) to the compiler, and nothing more.

For instance, the arguments to `memcpy` were declared as `restrict`. The documentation doesn't allow overlapping ranges, so the implementation would be fine. However, `uwu` could call it with overlapping ranges. It doesn't matter if `uwu` didn't make the promise, it has to uphold it for correct behaviour.

I believe we're on the same page now. (I assume in the following that where you wrote `strict`, you meant `restrict`.)

I now understand the standard such that it implies that promises made by `restrict` must be upheld in the whole program and distinctions between caller and callee are irrelevant. Both must cooperate such that the promises remain true.

As for the given code for `uwu`, I also believe the first version is allowed and the second is not. Since the second is the result of (hypothetical proposed) optimizations, the latter may not be applied even though they seem fine on the surface.

So we must have a way to determine when optimizations may be applied and imbuing pointer-to-integer casts with side effects certainly fixes this situation. It seems like a sound approach, but I do hope for a formal analysis, of course.

> (I assume in the following that where you wrote `strict`, you meant `restrict`.)

Yup, silly typos. Sorry about that.

Looks like you ended up agreeing with my post then. :)

(FWIW I fully agree re: appealing to authority. I'd rather people engage with my arguments than take them on face value.)

I'm not sure where you get that idea from. I think you draw wild conclusions from faulty logic.

> and then promptly uses pointer arithmetic to create an alias. It violated the promise.

afaik not creating aliased pointers is not a promise you make when marking a pointer as restrict. Only when using that aliased pointer for accesses (in the presence of modifications) can you actually break the promise. To quote cppreference:

"During each execution of a block in which a restricted pointer P is declared (typically each execution of a function body in which P is a function parameter), if some object that is accessible through P (directly or indirectly) is modified, by any means, then all accesses to that object (both reads and writes) in that block must occur through P (directly or indirectly), otherwise the behavior is undefined"

> Only in the presence of accesses and modifications can you actually break the promise.

Ok, creating aliases you don't use is probably fine. I should've worded that more carefully.

However, the example code certainly modifies the same piece of memory from two different pointers, and so it broke the promise.

Yes, I think it boils down to whether creating a derived pointer from a restrict pointer and then using both is allowed. I just had a look at the C standard and I think it is allowed if the derived pointer is (what the standard calls) "based" on the restrict pointer (page 89, 6.7.3.1 paragraph 3: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2310.pdf). The standard language is very dense but it makes it sound like the program presented in the article would not uphold this "based" property and so might be UB as you suspected.

The standard defines "based on" by talking about hypothetical alternative executions where the original value has a different value. In those executions, the access in question does not even happen in my program. What this goes to show is that the definition in the standard is ill-formed -- this can happen because the standard is written in English rather than a formal, mathematical language.

However, I think it is quite clear that the intention of the standard is to allow my program. It would certainly allow the alternative where the `if (xaddr == y2addr) {` is removed and its body (then-branch) put directly into the main function. It makes no sense to disallow this program just because it introduces an extra condition, ergo I claim this program has defined behavior.

Reply on news.ycombinator.com