What are semantics of empty enums that have been artificially fabricated?

[brson]

Updated bug report follows (see bottom for original bug report)

This bug appears to have been filed in error but then spawned a very interesting conversation.

The question centers around how empty enums (e.g. enum Foo { }, which has zero variants) which in principle cannot safely exist, interact with our casting operations (namely safe as and unsafecast::transmute).

Here is an some code that I wrote that summarizes the various scenarios that were described in the comments. Most of the scenarios do not compile (which is good). The fifth, sixth, and seventh all compile; their runtime behaviors vary, but most are acceptable. The only questionable thing @pnkfelix can see here is the behavior for the seventh example, cfg ex7.
Code:

#[allow(dead_code)];
use std::cast;
enum Foo { }
struct Bar;

#[cfg(ex1)]
fn main() {
    let i = Foo as int;
    println!("i: {:?}", i);
}

#[cfg(ex2)]
fn main() {
    fn f(f: Foo) -> int { f as int }
}

#[cfg(ex3)]
fn main() {
    let i : Foo = unsafe { cast::transmute(3) };
    println!("i: {:?}", i);
}

#[cfg(ex4)]
fn main() {
    let b : Bar = Bar;
    let i : Foo = b as Foo;
    println!("b: {:?}", b);
    println!("i: {:?}", i);
}

#[cfg(ex5)]
fn main() {
    let b : Bar = Bar;
    let i : Foo = unsafe { cast::transmute(b) };
    println!("b: {:?}", b);
    println!("i: {:?}", i);
}

#[cfg(ex6)]
fn main() {
    let b : Bar = Bar;
    let i : Foo = unsafe { cast::transmute(b) };
    println!("b: {:?}", b);
    match i {
    }
}

#[cfg(ex7)]
fn main() {
    let b : Bar = Bar;
    let i : Foo = unsafe { cast::transmute(b) };
    println!("b: {:?}", b);
    match i {
        _ => { println!("The impossible!"); }
    }
}

Transcript of compile (+ runs when compilable):

% rustc --cfg ex1 /tmp/ee.rs && ./ee
/tmp/ee.rs:8:13: 8:16 error: unresolved name `Foo`.
/tmp/ee.rs:8     let i = Foo as int;
                         ^~~
error: aborting due to previous error
% rustc --cfg ex2 /tmp/ee.rs && ./ee
/tmp/ee.rs:14:27: 14:35 error: non-scalar cast: `Foo` as `int`
/tmp/ee.rs:14     fn f(f: Foo) -> int { f as int }
                                        ^~~~~~~~
error: aborting due to previous error
% rustc --cfg ex3 /tmp/ee.rs && ./ee
/tmp/ee.rs:1:1: 1:1 error: transmute called on types with different sizes: int (64 bits) to Foo (0 bits)
/tmp/ee.rs:1 #[allow(dead_code)];
             ^
% rustc --cfg ex4 /tmp/ee.rs && ./ee
/tmp/ee.rs:26:19: 26:27 error: non-scalar cast: `Bar` as `Foo`
/tmp/ee.rs:26     let i : Foo = b as Foo;
                                ^~~~~~~~
error: aborting due to previous error
% rustc --cfg ex5 /tmp/ee.rs && ./ee
b: Bar
task '<main>' failed at 'enum value matched no variant', /Users/fklock/Dev/Mozilla/rust.git/src/libstd/repr.rs:559
% rustc --cfg ex6 /tmp/ee.rs && ./ee
b: Bar
task '<main>' failed at 'scrutinizing value that can't exist', /tmp/ee.rs:44
% rustc --cfg ex7 /tmp/ee.rs && ./ee
b: Bar
The impossible!
% 

Original bug report follows:

Something like this works:

enum Foo { }

let i = Foo as int;

Doesn't make any sense.

[catamorphism]

I don't think this actually does work? Foo is a type, not a term; the second line of code there errors out because Foo isn't in the value namespace.

Since it's impossible to construct a value of type Foo here, there's no problem as far as I can tell -- if you can construct a value of type Foo, then you can cast it to int. False implies anything. But maybe I'm misunderstanding?

[brson]

Oh, you are right. My example is bogus and doesn't demonstrate the problem. Take this one:

enum Foo { }
fn f(f: Foo) -> int { f as int }

Of course this code can never be run (without unsafe) since Foo can't be constructed. The cast though is allowed even though we know it is bogus. It almost certainly represents a logic error that could be reported.

But there are a lot of other similar things we could catch, like using match with a zero-variant enum and the line must be drawn somewhere.

[catamorphism]

Huh, now I'm morbidly wondering what happens if you cast something to Foo in an unsafe block.

I'm not really sure what error we should report here, tbh. I'd be fine with disallowing uninhabited types, but they do have their uses. If we make a conscious decision to allow uninhabited types, then it doesn't seem principled to forbid doing perfectly sound things with them. After all, if someone is using uninhabited types, they are probably up to some monkey business that we can't usefully second-guess.

[nikomatsakis]

I think we should have a policy that uninhabited types are fine, but if we encounter a place where we can't sensibly codegen because the type is uninhabited, we generate a fail. An example would be matching an empty enum.

This case is borderline to me because being C-like (and hence castable to uint) is not a property that all enums share, so we can choose to say that empty enums do not have this property if we like. However, it also seems reasonable to say "C-like enums are those for which all variants have arguments", in which case empty variants qualify. In that case, I'd say that 'foo as uint' should fail, since there is no sensible way to codegen it.

[catamorphism]

That's what we already do for matching on an empty enum -- fail with "the impossible happened" or something like that.

[nikomatsakis]

right, that's what I thought we did

[catamorphism]

This is really a language spec question. Nominating for milestone 1.

[graydon]

consensus is "this should be an error", accepted for backwards compatibility

[bblum]

The only thing you can cast to an empty enum is another 0-size struct, so attempting anything else will give a transmute called on types with different sizes error.

This test case fails with enum value matched no variant:

use std::cast;
use std::io;
enum Void { }
struct Foo;
fn main() {
    let x: Void = unsafe { cast::transmute(Foo) };
    io::println(fmt!("%?", x));
}

I also can't seem to cast an empty enum to anything. The compiler says non-scalar cast: Voidasuint``. So I'd say this isn't an issue.

However, maybe we could also make the type-size of empty enums something other than 0, so even the above transmute attempt fails? Would that make sense, or would it mess up e.g. cases where you have a void inside a struct?

[thestinger]

Triage bump.

[pnkfelix]

(maybe we should hide empty Enums under a feature flag for 1.0?)

[nikomatsakis]

On Thu, Sep 26, 2013 at 10:53:58AM -0700, Felix S Klock II wrote:

(maybe we should hide empty Enums under a feature flag for 1.0?)

No! Let's just decide and settle this. It is... really not important.
I vote for "whatever the behavior is now, it's fine." :)

[pnkfelix]

@nikomatsakis its more that there are other things that seem ... questionable with empty enums.

Like case of struct X in the examples I added to the description for Issue #2634

[flaper87]

visiting for triage

@nikomatsakis @pnkfelix @brson what's the final take here?

[pnkfelix]

@flaper87 I'm inclined at this point to go with @nikomatsakis and say that behavior now, as described by @bblum in the above comment is fine.

There may be other oddities with empty enums (like #2634), but as it stands this bug is kind of bogus: According to a survey I just did of the examples provided in the description and comments, only bblum's comment seems to reflect the current state of affairs, and his example does not describe a bug per se, but rather just shows how you can currently use transmute to get an instance of an empty enum (but only by feeding it another empty struct).

I'm going to update the description to reflect this state of things. And then I'm going to close the bug.

[pnkfelix]

Okay, I am not going to close the bug quite yet, because I would like us to official decide whether or not our current behavior on these two cases (copied from my updated bug description) are okay:

use std::cast;
enum Foo { }
struct Bar;

#[cfg(ex6)]
fn main() {
    let b : Bar = Bar;
    let i : Foo = unsafe { cast::transmute(b) };
    println!("b: {:?}", b);
    match i {
    }
}

#[cfg(ex7)]
fn main() {
    let b : Bar = Bar;
    let i : Foo = unsafe { cast::transmute(b) };
    println!("b: {:?}", b);
    match i {
        _ => { println!("The impossible!"); }
    }
}

The difference in the two behaviors is kind of strange/interesting. I think the results are acceptable, but it might also be reasonable to think that ex7 should behave in exactly the same manner as ex6.

[pnkfelix]

Nominating for 1.0, P-backcompat-lang.

[flaper87]

@pnkfelix uh, mmhh o_0 IMHO, ex7 doesn't sound right. Since Foo doesn't have any variant, it can be very confusing for users to know what the actual behavior in ex7 is. A match on an empty enum should probably raise a compile error, IMHO.

[glaebhoerl]

The question is absurd. Types are propositions, and constructing an inhabitant of an uninhabited type corresponds to proving a contradiction. If you could do it in safe code, it would mean the type system is unsound. Doing it in unsafe code should be undefined behavior. In which case the implementation has no particular obligations, and anything it chooses to do is just fine. It makes no more sense to define a semantics for this than it does to define a semantics for using unsafe to read from uninitialized memory, construct two &mut references to the same object, or break any other type system invariant.

[pnkfelix]

In case it is not clear, my main goal was to report what the implementation does now, since one of the suggested paths forward was "whatever the behavior is now, it's fine." I wanted to see what the current behavior was before I signed off on that path.

What I was expecting when I made these experiments, based on this comment thread, was for that match expression to fail in ex7, similarly to how it did in ex6. But ex7 did not, so I have not closed this ticket, because it seemed worth double-checking.

@flaper87 I don't have a strong objection to making match on an empty-enum a compiler-error, except that it might inadvertently cause problems for certain macro- or template-instantiations that expand/monomorphize into code that has such a match. (Hopefully such code would be unreachable, I am just hypothesizing here.)

@glaebhoerl The question may indeed be absurd. I did not intend to imply that I wanted a concrete definition of the behavior one gets; I just whipped up the current bug title because the previous title on the bug was misleading about the issue here. I do not mind saying that using unsafe code to create an instance of an empty enum yields undefined behavior. But I do think that it is worth spelling that undefined-ness here out explicitly in our documentation somewhere; mixing together unsafe transmutation and type-safe algebraic enums is not standard programming-language practice. (I have seen plenty of such transmutation when implementing language runtimes, but my impression is that Rust must define up front the semantics of many such interactions between unsafe constructs and the type system.)

In short, I still think it is interesting that the behavior differs so significantly between ex6 and ex7, and I want to make sure that we do not accidentally include these cases in our backward-compatibility story without realizing it.

[glaebhoerl]

An empty match on an empty enum is perfectly legitimate: it has type ! and witnesses the fact that it's an impossible circumstance, and the code in question is unreachable. (In safe code, the only way a function or expression can "return" an empty enum is if it never returns.) (If someone abuses unsafe to do otherwise, again, that's undefined behavior.)

It might be a good idea to forbid any arms at all, including wildcards, inside an empty enum match, or more generally: a match on any uninhabited type. Or at least warn about it. (Perhaps it should be an error iff the compiler can always tell whether a type is inhabited, and a warning otherwise.)

EDIT: If I write this:

enum X { X }
fn x() -> X { unimplemented!() }
match x() {
    X => println!("yo"),
    _ => println!("sup")
}

the compiler complains:

error: unreachable pattern
     _ => println!("sup")

If I remove the variant from the enum and the corresponding arm from the match, I should get the same error.

[pnkfelix]

@pcwalton points out that memory layout of non C-like enums are undefined. as long as zero-variant enums are not C-like enums, I am willing to retract my prior belief about this being a 1.0 issue. Unnominating.

[glaebhoerl]

I've opened #12609 about what I see as the actual bug here: you should not be able to even write a wildcard match on an empty enum, so there's no behavioral inconsistency between ex6 and ex7, as only ex6 should be legal.

[huonw]

Is there a way in which constructing a value of a type which supposedly has zero values can be regarded as anything but a flagrant abuse of the type system and severely undefined behaviour?

With or without enums having an undefined representation, it seems that having a value of an uninhabited type is horribly bad practice, and we don't need to specify what happens when one does occur (nasal demons and so on).

In particular, assuming that enum Void {} is completely non-constructable allows one to have stronger guarantees for something like

trait Foo<T, E> { fn run(&self) -> Result<T, E>; }

impl Foo<int, Void> for PureIntCalculation {
    fn run(&self) -> Result<int, Void> { ... }
}

impl Foo<int, IoError> for ImpureIntCalc { ... }

where the first impl is effectively asserting that the Err variant never happens, and then we could theoretically optimise based on this, e.g. remove the discriminant in the Result<.., Void> case (this is getting "dangerously" close to (an approximation to) GADTs).

[thestinger]

I think this is clearly undefined under the current definition of enum. The memory layout is undefined, so any conversion to an enum without a repr attribute is undefined behaviour. It's also already undefined behaviour to create an enum not specified by a variant - this is undefined for the same reason as transmuting 5 to #[repr(int)] enum Foo { A = 3, B = 4 } is undefined.