Thoughts on Compile-Time Function Evaluation and Type Systems

[RalfJung]

@oli-obk helpfully created a repo for const-eval concerns, so a good place to discuss things is probably the issue tracker of https://github.com/rust-rfcs/const-eval

[rocallahan]

In your make_a_bool() example, you wrote

However, due to CTFE being deterministic, we have to pick one concrete answer at compile-time, and that may not be the right answer. Hence we cannot allow this program to execute under CTFE if we want to maintain CTFE correctness.

You seem to be saying that CTFE correctness means “every compile-time execution of the code produces the same result as every run-time execution”. But why not define CTFE correctness as “every compile-time execution of the code produces the same result as some valid run-time execution”? That definition seems just as useful: in particular, it still justifies the optimization of replacing a non-const expression with its const equivalent. And by that definition your make_a_bool() example could be CTFE-correct (assuming you define some deterministic semantics for dynamic allocation), so it actually seems more useful.

[rocallahan]

Automatically promoting CTFE-correct expressions to the static lifetime sounds cool but I think like any other language feature, the cost-benefit tradeoff needs to be evaluated. The benefit depends on how often it would actually be useful; the costs include added language complexity, and possible user surprise when their code was accidentally depending on static lifetime promotion and it changes to no longer be CTFE-correct. Personally I’m skeptical this would be worth doing for non-trivial expressions — users can always be explicit by wrapping non-trivial const expressions into const functions.

[RalfJung]

You seem to be saying that CTFE correctness means “every compile-time execution of the code produces the same result as every run-time execution”. But why not define CTFE correctness as “every compile-time execution of the code produces the same result as some valid run-time execution”? That definition seems just as useful: in particular, it still justifies the optimization of replacing a non-const expression with its const equivalent. And by that definition your make_a_bool() example could be CTFE-correct (assuming you define some deterministic semantics for dynamic allocation), so it actually seems more useful.

Good point. However, I think there is a problem: Imagine the same computation is carried out twice, and only one of them ends up running during CTFE. I imagine something like

const A : &T := ...;
const B : &T := ...;
const AB_eq : bool := (A as *const _) == (B as *const _);

let AB_eq_runtime = non_constant_evaluable_function(A as *const _) == (B as *const _);
assert_eq!(AB_eq, AB_eq_runtime); // now this could fail if we picked the "wrong" answer during CTFE

I think we should avoid introducing such strange effects.

Automatically promoting CTFE-correct expressions to the static lifetime sounds cool but I think like any other language feature, the cost-benefit tradeoff needs to be evaluated. The benefit depends on how often it would actually be useful; the costs include added language complexity, and possible user surprise when their code was accidentally depending on static lifetime promotion and it changes to no longer be CTFE-correct. Personally I’m skeptical this would be worth doing for non-trivial expressions — users can always be explicit by wrapping non-trivial const expressions into const functions.

I don’t disagree. Unfortunately, we are bound by a backwards-compatibility promise.

[rocallahan]

I think we should avoid introducing such strange effects.

I confess I don’t see the problem here. There has to be some domain of compile-time reference/pointer values, and a bijection between those compile-time values (at least, those that actually survive to run-time) and run-time reference/pointer values. Given that, your example’s assertion couldn’t fail.

Unfortunately, we are bound by a backwards-compatibility promise.

Ah, I thought you were proposing extending whatever already exists.

[RalfJung]

I confess I don’t see the problem here. There has to be some domain of compile-time reference/pointer values, and a bijection between those compile-time values (at least, those that actually survive to run-time) and run-time reference/pointer values. Given that, your example’s assertion couldn’t fail.

I don’t follow. You are proposing that compile-time behavior must just be possible at run-time. Based on that, it is possible that the assertion can succeed. But it is not at all guaranteed.

[rocallahan]

This is how I expected it to work: The compile-time evaluator chooses compile-time pointer values for A and B. Because they’re used at run-time, those compile-time pointers need to be converted into corresponding run-time pointers according to some global mapping. The mapping needs to be a bijection so if the compile-time pointer values are equal, the run-time values will also be equal; if the compile-time values are non-equal, the run-time values will also be non-equal.

Perhaps I’m confused about how compile-time pointers are converted to run-time pointers? If so I should stop bothering you with my ignorance.

[RalfJung]

This is how I expected it to work: The compile-time evaluator chooses compile-time pointer values for A and B . Because they’re used at run-time, those compile-time pointers need to be converted into corresponding run-time pointers according to some global mapping. The mapping needs to be a bijection so if the compile-time pointer values are equal, the run-time values will also be equal; if the compile-time values are non-equal, the run-time values will also be non-equal.

These are out-of-bounds pointers we are talking about. We can’t “emit” them as constant, I think we have to compute them from some base addresses and getelementptr. LLVM could decide to compare them either way, and we can’t really control what it does (from what I know). @oli-obk would be the one who knows how pointers with constant values are sent to LLVM.

[oli-obk]

When we have a pointer to a static, we don’t get an actual pointer from LLVM, we just tell LLVM the name of the static. If that static is e.g. static FOO: &'static u32 = &1; we also generate an unnameable static for the 1 and tell LLVM the “name” of that when generating FOO's pointer value. LLVM probably doesn’t figure out the actual address until link time.

[RalfJung]

And what if we have a pointer into a static but not to the beginning?

static FOO: (u32, u32) = (0, 1);
static BAR: &u32 = &FOO.1;

EDIT: Ah

error[E0494]: cannot refer to the interior of another static, use a constant instead
 --> src/main.rs:2:20
  |
2 | static BAR: &u32 = &FOO.1;
  |                    ^^^^^^

[rkruppe]

LLVM (and linkers, the ultimate arbiters) can actually support that: https://godbolt.org/g/tfGi9A

We just haven’t committed to it in Rust yet.

[oli-obk]

static FOO: (u32, u32) = (0, 1);
static BAR: &u32 = &FOO.1;

This works on nightly now thanks to @alexreg who removed the barriers that existed due to old ctfe not being able to do this.

[system]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.