Should we have another non-type never?

language design
21

This one's interesting. The core allocation functions, like Vec::push and Vec::append, document panics on capacity overflow (i.e. when you have more than usize::MAX zero-sized types in a Vec), but do not document panics on memory exhaustion, and I think that the reason is that memory exhaustion is not actually a panic (it has similar effects in practice but is implemented differently). See handle_alloc_error for more information – it looks like the current rules are to abort if using std and panic if #[no_std], which implies that nothing in std panics on memory exhaustion.

There's also the fact that on some (most?) operating systems, programs don't get denied allocations if the system is out of memory; they just get killed heuristically instead (meaning that it can't be handled from inside the program). This makes sense if you think about it: when the system is low on memory, it is in practice almost always because one program is leaking memory quickly. In that situation, denying allocations based on memory pressure would mean that other processes that try to allocate memory when the system is near the limit would end up failing allocations and maybe choosing to abort as a result, so you end up with possibly some unrelated processes dying (even if they're hardly using any memory at the time and werent' responsible for the memory shortage). Having the operating system detect which process is at fault and kill that process specifially generally causes less damage to the system as a whole, but it means that you don't have any out-of-memory error you can handle. (Out-of-memory indications do happen in practice, but only when you're using per-program memory quotas: a program can reasonably get an out-of-memory signal if it hits its personal limit for how much memory it can use, even if the system as a whole still has memory spare.)

It's also worth noting that memory limits can be hit when trying to grow the stack, meaning that you can get an alloc error as a consequence of any function call at all, even one that claims to handle alloc errors, unless you calculate the amount of stack you need in advance and prefault it.

So it makes sense for memory exhaustion to be handled as a special case: it's almost impossible for programs to handle all possible cases of it, and normally the operating system would make better decisions anyway.

(Note that a possible improved OS design involves telling a program the system is out of memory "early" in cases where the program appears to be at fault for the memory exhaustion, and earlier for allocation requests than for stack growth – a scheme like that would allow alloc-error panics to work reliably. I don't believe any OSes work like that at present, but maybe it would make sense to design Rust in anticipation of a world where they might exist.)

4 Likes
22

That is really a case of language lawyering... The effect is the same: program goes away unexpectedly.

No, it it really just Linux that does over provisioning. But you can turn that off (and should for real time systems for example).

If you care about your workload you should also define limits that happen before the system as a whole run out of resources. This can take many forms (depending on the OS): ulimit, cgroups, etc

Well, the Linux OOM killer is famously bad at this. Which is why there is OOM adjustment factor files under /proc, and nowadays userspace systemd-oomd etc. I have had a runaway process in my terminal result in the entire (multi-tab) terminal getting killed, probably because it did not use cgroups to separate out the tabs.

This very much depends on what domain you are in. Database server developers are not amused by OOM killer. And in hard realtime you must use mlockall() and keep tabs on your memory usage.

You may be interested in this podcast episode: Async Allocators (about the idea of making allocation async, which works but only if everyone opts in.)

2 Likes
23

It's significantly different because if the library documents that it panics in a given situation, people will expect that they will be able to catch the panic (e.g. there are should_panic tests and those are commonly used to see if a function panics in cases where a panic would be expected, but those won't handle aborts). As such, I expect a patch to document the abort as a panic would be rejected.

This is in theory unrelated to overcommit (although Linux seems to control both of them using the same option?) – it makes sense to use an OOM killer to select which process to kill even if overcommit is disabled. (I've experienced first-hand the results of an OS using the "just deny all the allocations until something changes" technique – the desktop environment ended up aborting and didn't automatically restart, making the system unusable without a reboot. That was on a very old version of Windows; hopefully it handles that situation better nowadays.)

In any case, I don't think any of this negates the original point – Rust's standard library std, in effect, treats memory exhaustion as being out of scope, so it's unsurprising that its effects aren't documented on every standard library function that could potentially exhaust memory (especially given that any call to any non-inlined function could exhaust memory, meaning that the documentation for that would be very redundant and repetitive). Actual panics do seem to be documented pretty well, in my experience – and implementing a trait method to panic when it isn't documented to do so is an incorrect implementation of the trait.

1 Like
24

Okay I'm starting to understand. The below code compiles without warnings/errors (except for the one that it has) today, so we kind of have an answer to the question posed

fn uh_oh<T: Default>(_: fn() -> T) -> T {
    T::default()
}

#[allow(unreachable_code)]
fn just_panics() -> impl Default {
    panic!() as u32
}

fn main() {
    uh_oh(just_panics); // what impl does this use?
                        // answer: any impl would be fine
}

At minimum, the compiler can definitely find or invent a type ex nihilo and just plop in the as Ty42 part to make this pattern work.

@SkiFire13 This also just works today:

#![allow(unreachable_code)]

pub fn foo() -> impl Iterator<Item = u32> {
    panic!() as std::array::IntoIter<u32, 8>
}

pub fn bar() -> impl Iterator<Item = String> {
    panic!() as std::vec::IntoIter<String>
}
25

No - that's precisely the problem: the compiler cannot invent a type for this, this would be equivalent to implementing the trait for !.

Using any existing type may work, but is very weird.

26

I do think ! for any dyn-compatible RPIT should ideally compile. But it can't really for non dyn-compatible traits, because some of the trait functionality can be used without first creating !, and the compiler shouldn't just be choosing a random type to compile actual reachable code with.

IIUC the error doesn't (or at least shouldn't) block any of the rest of checks. It needs to prevent building, but it doesn't need to block checking the rest of the program, since it can't[1] depend on what concrete type is chosen.

This is almost the case currently. You only need two more cases:

  1. a user-defined function that panics was called
  2. stdlib has a bug; please create an issue with a reproduction

The one caveat is that this is generally considered a correctness property that SHOULD NOT be relied upon for soundness (freedom from UB). But if a panic would not cause a soundness issue, there is no expectation for your code to be resilient to arbitrary undocumented panicking.

(I am speaking from my own belief, not for T-opsem or wg-ucg.)

  1. Well, ignoring autotrait exposure. ↩︎

4 Likes
27

This is going to come across as a little nitpicky but I think the particulars are worth it. Sorry in advance.

This code is legal in current stable rust:

struct DummyStruct;

impl Iterator for DummyStruct {
    type Item = u32;

    fn next(&mut self) -> Option<Self::Item> {
        panic!()
    }
}

pub fn foo() -> impl Iterator<Item = u32> {
    panic!() as DummyStruct
}

The compiler is certainly capable of inventing the above definitions for DummyStruct and the impl Iterator, therefore: the compiler can invent a type for this.

This would be equivalent to implementing the trait for ! as DummyStruct, which as far as I can tell is different from implementing the trait for !. There is an extra complication where we'd like the as DummyStruct to be implied as well.

Agreed! That part was more for argument's sake, I would rather the compiler used an unnameable one-off definition for this purpose. The point I am trying to make is that this code can be written today, it's just verbose and weird. What's being requested is some kind of sugar for something that can already be accomplished.

28

That has the same drawback as impl for Default that people discussed. Personally I don't believe we should do it.

29

@CAD97 You seem to miss my key point: I'm well aware implementing the trait is not viable (or at least not wanted), and I don't vote for it. But since the code is truly unreachable, we don't need it to implement the trait - we can just skip the check that it does, it can cause no unsoundness.

30

Yeah, because you specified some type that implement those traits, but this means that ! is not the one implementing the trait. Moreover in this case there was some type that implemented the trait, but what if there's no type doing so?

trait Foo {}

fn foo() -> impl Foo {
    panic!() as ??? // what should the compiler put here?
}

You could claim the compiler may generate a dummy implementation of Foo, but that means that now there exist an implementation of Foo where no impl Foo for ... was ever written.

Moreover here are more situations where generating such dummy implementations become very sketchy:

  • Foo is marked as unsafe or requires an unsafe supertrait: the compiler would be generating an unsafe impl without checking the preconditions;
  • Foo contains methods that take private/hidden types, which are generally used to ensure a trait is only implemented within a specific crate: now the compiler is breaking that assumption by creating an impl that you would not be able to write manually and that the trait creator was not expecting to exist.
  • Foo is a trait that cannot be ever implemented, for example a trait requiring both Iterator<Item = u32> and Iterator<Item = String>.

I hope that this makes it clear that it's not possible for the compiler to magically implement any trait for !, nor generate dummy implementation for them. There needs to be some rules that specify which traits are allowed to be implemented, ideally without breaking expectations from those trait users.

I see two issues with this:

  • where Self: Sized bounds can't exclude methods for the sake of this analysis like it happens when we compute dyn-compatibility, because RPIT are Sized as opposed to trait objects;

  • this assumes that dyn-compatible methods all require an instance of Self existing in order to be callable, however with arbitrary_self_types_pointers you can have dyn-compatible methods taking *const Self, which can be conjured out of thin air without actually having an instance of Self.

The starting point seems promising though, but I think we need slightly different rules to make this work.

6 Likes
31

This is basically the Ur example where the requested functionality really should work if you write it like this instead:

// TODO: implement this for things. 
trait Foo {}

fn foo() -> impl Foo {
    todo!()
}

It's possible that there should be places where the compiler refuses to create a dummy implementation and still errors out[1]. An unsafe trait and a trait which requires hidden types sound like reasonable restrictions (in the sense that, if I couldn't write out a dummy implementation by hand, the compiler probably shouldn't even though e.g. it could in fact "see through" visibility constraints if it wanted to). The trait requiring mutually conflicting super traits should probably be an error, but for a different reason (defining the trait itself should be an error, no?).

  1. E.g. there are unsafe traits that specify "method foo_doesnt_panic must not panic! So for sure I can imagine reasonable limits on what one should be able to just todo!`. ↩︎

1 Like
32

The problem is that the unreachability is irrelevant because you don't have to actually execute the function. The prior example:

fn panics() -> impl Default { panic!() }
fn skip<T: Default>(_: fn() -> T) { T::default() }
fn main() {
    skip(panics); // what happens here?
}

panics() is never called. But skip receives the function itself and thus can infer its return type and knows that it implements Default, so can call <! as Default>::default. But you skipped checking that ! implements Default, so what happens here? It's certainly not obvious.

You absolutely could make an argument for todo!() specifically implementing traits where all functions todo!() because of specifically TODO semantics, but you can't just say the impl is unreachable, because it isn't.

impl Iterator<Item=Q> is different because every (required) method requires self to exist. So the body can be match self {} (with a deference for by-ref receivers) as proof that the method is actually impossible to call.

I keep having to rediscover that the compatibility is different, unfortunately; I knew this at one point, but it's hard to remember everything.

Having a separate breed of implicit compatibility for traits is a tough sell. The applicability of impl Trait for dyn Trait is already subtle enough. This pushes me back into thinking that maybe it's fine to just recommend trait authors do impl Trait for ! where possible like we recommend impl Trait for &T where T: ?Sized + Trait forwarding impls when applicable.

This precludes traits with associated types, though, and the compiler could potentially handle that case, so… I don't know.

6 Likes
33

I still feel that the logical answer to "what does <! as Default>::default() do if you actually call it" can only be "it does not return", and that this is fully consistent with both type theory and the existing specification of Default. Furthermore, I think this is the logical answer for any trait function whose return type involves Self [EDIT: whose return type means that it cannot return without constructing a value of type Self somehow, when Self is uninhabited‌].

I could be persuaded that in general the answer to "what does <! as Trait>::non_method() do if you actually call it" needs to be something else, perhaps "the compiler refuses to compile the call." However, I would like to see an example of problematic code, which would be enabled by ! being coercible to arbitrary impl Trait, and which involves a more interesting trait than Default (perhaps an unsafe one?) and/or doesn't involve actually calling any trait functions that either take or return a value that involves the Self type.

3 Likes
34

A "trait function whose return type involves Self" is a very weak constraint. Consider something that returns Option<Self>, for instance; that could very plausibly have an impl for ! that returns None. Worked example:

trait StringInfo: Sized {
    fn get(s: &str) -> Option<Self>;
}

impl StringInfo for usize {
    fn get(s: &str) -> Option<Self> {
        Some(s.len())
    }
}

impl StringInfo for char {
    fn get(s: &str) -> Option<Self> {
        s.chars().next()
    }
}

impl StringInfo for u8 {
    fn get(s: &str) -> Option<Self> {
        s.bytes().next()
    }
}

fn try_get<I: StringInfo>(
    make_default: impl FnOnce() -> I,
    opt_str: Option<&str>,
) -> Option<I> {
    opt_str.map_or_else(|| Some(make_default()), StringInfo::get)
}

fn default_info() -> impl StringInfo {
    todo!("I'll get around to it")
}

fn main() {
    // What happens here?
    assert!(matches!(
        try_get(default_info, Some("don't call `default_info`")),
        None
    ))
}

The most reasonable impl of ! for StringInfo if we were to have one would probably be to always return None:

impl StringInfo for ! {
    fn get(_: &str) -> Option<!> {
        None
    }
}

And maybe that's what I meant to add and haven't gotten around to yet! So we really don't want the compiler synthesizing panicking impls for ! in general.

(Here's a playground including the impl StringInfo for !, for convenience.)

Edit: Actually, here's a better example entirely. What about a trait where only one associated function returns Self? If you have another trait method fn other_method() -> String, there's no way to guess what that should return. Again, a worked example:

trait NamedType: Default {
    /// Get a user-friendly name for this type.  This function must never panic.
    fn type_name() -> &'static str;
}

impl NamedType for () {
    fn type_name() -> &'static str {
        "()"
    }
}

fn fn_type_name<S: NamedType, T: NamedType>(_: impl Fn(S) -> T) -> String {
    format!("{} -> {}", S::type_name(), T::type_name())
}

fn problem(_: ()) -> impl NamedType {
    todo!("I'll get around to it")
}

fn main() {
    // What should this do?
    println!("{}", fn_type_name(problem))
}

This ought to print () -> !, if it does anything; and per the trait documentation, this shouldn't panic (at least, as long as fn_type_name doesn't panic when allocating the string). But that's not something the compiler can synthesize.

(Here's a playground for convenience; comment out the todo! line and the code runs and prints () -> ().)

35

Since it seems like we're all getting on the same page here, I'd like to put in that I'd really like for the synthesized impls to do something I cannot (afaik) currently write by hand:

fn panics() -> impl Default { panic!() }
fn skip<T: Default>(_: fn() -> T) { T::default() }
fn main() {
    skip(panics); // what happens here?
}

Becomes as the handwritten code:

struct DummyFoo;
impl Default for DummyFoo {
    fn default() -> const ! {}
}

fn panics() -> impl Default { panic!() as DummyFoo }
fn skip<T: Default>(_: fn() -> T) { T::default() } // compile error
// method <! as DummyFoo>::default returns `const !`
fn main() {
    skip(panics);
}

As this is a compile error, it can later be relaxed to do something else (e.g. create a panicking impl for just Todo<!>). I would guess that compound types like Option<const !> also error where they would be created.

Edit: see below

2 Likes
36

On reflection, yeah, I was only thinking of &Self and Box<Self> and things like that, not types like Option<Self> where a value of (at least some variants of) the type can exist even if the enclosed type is uninhabited. Possibly a better wording is "a trait function that cannot return without constructing a value of type Self" [must be a function that never returns, when Self is an uninhabited type].

37

The precise version would probably be "a type that, assuming Self is uninhabited, witnesses an uninhabited type" where "witnessing" means that the type is reachable using only safe place access and projection (ignoring privacy).

38

Hm, for documentation purposes I think that's a bit too much jargon. Maybe something like this instead: For any type-level property of interest, a parametric type P<T> is said to expose T's property when it has that property if and only if T has that property. Otherwise, it is said to mask T's property.

Box<Self> exposes Self's uninhabitedness; Option<Self> masks Self's uninhabitedness.

39

Writing this out in code (with const !)

type Void = <! as MyType>;
impl Default for Void {
    fn default() -> const ! {}
}

// monomorphized by hand
impl Default for Option<Void> {
    fn default() -> Option<Void> {
        None
    }
}

// Result doesn't actually implement default but let's pretend
impl Default for Result<Void, String> {
    fn default() -> Result<Void, String> {
        Ok(<Void as Default>::default())
    }
}

fn main() {
    let a = Option::<Void>::default(); // Okay, that's `None`
    let b = Result::<Void, String>::default(); // compile error
}

And then there's no real jargon for why it's a compile error, it's just a stack trace to "calling a function that returns const !". Perhaps that error message could be better still, but the reasoning is extremely direct.

2 Likes
40

Note that this would be a compiler error only during monomorphization, i.e. with cargo build but not with cargo check.