Move `Error` trait into core

[yaahc]

EDIT: Current Status Update

---

Building upon these prior issues:

• Tracking issue for RFC 2504, "Fix the Error trait" rust#53487
• Stabilize the backtrace feature. rust#72981

From this comment Backtrace stabilization is currently blocked on prototyping one or more of the suggested solutions for moving the std::error::Error trait into core

That comment suggests three possible solutions.

1. Remove `backtrace` from `Error` and instead provide it via some generic context mechanism (RFC 2895).

2. Define a `Backtrace` trait in core and have an implementation of that trait in libstd. `Error::backtrace` would then return a `&dyn Backtrace`.

3. Define `Backtrace` in core but have it dispatch via an internal vtable. This is effectively the same as 2 but the trait is hidden. The `capture` method will have to be moved to a free function in libstd.

Option one is already known to work, and so it does not need to be prototyped. In addition to these backtrace related issues a prototype of the error trait in core will need to find a way to work around pub fn downcast<T: Error + 'static>(self: Box<Self>) -> Result<Box<T>, Box<dyn Error>> since Box won't be available in core. The top level comment in @withoutboats's stabilization PR goes into more detail on this second issue and outlines how a new core::error::Error implementation could use hooks that are defined in std, similar to panic hooks, to work solve the issues around Box.

Boats has already raised issues about option two in this comment so I think the best way forward is to start working on a core::error::Error trait and core::backtrace::Backtrace type that both rely on hooks / manual vtables to maintain backwards compatibility with the existing error trait.

[nagisa]

I attempted to prototype the move to libcore with backtrace removed in this branch.

The mentioned downcast is indeed not at all an issue (I applied the suggestion I made in this comment), but

impl<'a> From<&str> for Box<dyn Error + Send + Sync + 'a> {

comes up as an issue. In particular it will trigger coherence's wrath with

error[E0119]: conflicting implementations of trait `core::convert::From<&str>` for type `boxed::Box<dyn core::error::Error + core::marker::Send + core::marker::Sync>`:
    --> library/alloc/src/errors.rs:66:1
     |
66   | impl<'a, E: Error + Send + Sync + 'a> From<E> for Box<dyn Error + Send + Sync + 'a> {
     | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `boxed::Box<dyn core::error::Error + core::marker::Send + core::marker::Sync>`
     |
    ::: library/alloc/src/boxed.rs:1155:1
     |
1155 | impl<'a> From<&str> for Box<dyn Error + Send + Sync + 'a> {
     | --------------------------------------------------------- first implementation here
     |
     = note: upstream crates may add a new impl of trait `core::error::Error` for type `&str` in future versions

[yaahc]

Here's a link to a related zulip discussion thread: https://rust-lang.zulipchat.com/#narrow/stream/257204-project-error-handling/topic/Stabilizing.20Backtrace.20.2F.20Core.20Error.20Proof.20of.20Concept/near/211291775

Once we've talked through potential solutions to the orphan rule issue more I'll come back and summarize the potential steps forward in the top level issue.

[yaahc]

I'm now trying to prototype the actual backtrace hook in core implementation to prove that all works and is something we could merge. I'm not really sure what I'm doing so I'm going to write out what I understand as the necessary steps so that more people more experienced with working on the language can give feedback and guidance. I'm basing this largely on the way rust structures it's panic handler.

Expected Steps

• Create a Backtrace type in core with the same interface as the current Backtrace type but without the implementation.
  • a function to conditionally construct a backtrace
  • a function to force construction of a backtrace
  • a function to access a backtrace status
  • Display and Debug implementations
• Add hooks that are called in these core implementations to access the implementations defined in std
  • fn backtrace_enabled_impl() -> bool
  • fn backtrace_capture_impl() -> *mut ()
  • fn backtrace_status_impl(*mut ()) -> BacktraceStatus
  • fn backtrace_fmt_impl(*mut (), use_display: bool, &mut core::fmt::Formatter) -> fmt::Result
• add these to the weak_lang_items definition in src/librustc_hir/weak_lang_items.rs
• implement these lang items in libstd
• move the content of the current implementations of the backtrace interface to these hooks
• remove the existing std backtrace types and reexport those defined in core

I do not love the idea of defining a bunch of lang items for this, so I'm assuming this is only vaguely correct.

Unanswered Questions

• what hooks end up getting used in a no_std context when a Backtrace is constructed? Does the compiler automatically insert some or link some dummy impl in when it sees std isn't available?
• Do we want it to be possible for users to provide implementations for these hooks?
  • If so, how do we guarantee we can add an iterator API to backtraces in the future backwards compatibly?

[yaahc]

I'm still unconvinced that hooks are the best solution as opposed to defining a Backtrace trait in core. Here is my analysis of the trade offs.

Comparison

• Both traits and hooks are essentially ways to define a vtable
• Traits carry the vtable as part of the object via a wide pointer
• hooks store the vtable in a single static location
• traits are dynamically dispatched via virtual calls
• hooks are statically dispatched like any other non virtual function
• With traits you can have many implementations of the vtable in the same binary
• with hooks you can must have exactly one implementation, unless you never attempt to call the hooks
• with traits have to pay the cost of virtual function calls
• traits are likely simpler implementation wise
• A trait based solution would require either a wide pointer on the stack or an extra layer of indirection

To my pattern matching brain traits feel like a universally quantified form of dynamic dispatch whereas these ad-hoc hooks feel like an existentially quantified form of const dynamic dispatch.

Previously @withoutboats raised concerns about stability when using traits. I don't think this is a fundamental issue though. We could twrap the trait in a newtype and make the trait itself unstable, which is essentially what we're doing with the hooks. Either way if the user is ever allowed to provide the vtable, whether via traits or hooks, adding new items to that vtable will require handling the default case.

The question is, which is more appropriate for backtraces?

• What use cases are there for being able to work with multiple types of backtraces via a common interface?
  • SpanTrace - doesn't seem useful here unless the generic member access RFC never merges
  • Backtraces of frames of other languages via FFI? - Could this be handled by defining your own backtrace handler via the static hooks that is capable of understanding frames in of all the languages it will interact with?

[eddyb]

This is a full example of what @yaahc, @mystor and I have discussed (I don't plan to be actively involved, but felt like I needed to exemplify my suggestions): https://play.rust-lang.org/?version=nightly&mode=release&edition=2018&gist=63b4720d0347d05391643df9da08c72f

Also here's a more pseudocode version of it (and without most implementation details), to facilitate discussion:

mod core::panic {
    // perma(?)-unstable
    pub trait RawBacktraceImpl: fmt::Debug + fmt::Display + 'static {
        unsafe fn drop_and_free(self: *mut Self);
    }

    #[stable]
    pub struct Backtrace(*mut dyn RawBacktraceImpl);

    impl Backtrace {
        // perma(?)-unstable
        pub unsafe fn new(p: *mut dyn RawBacktraceImpl) -> Self {
            Self(p)
        }

        #[stable]
        pub fn capture() -> Option<Self> {
            extern "Rust" {
                #[lang_item = "backtrace_capture"]
                fn backtrace_capture() -> Option<Backtrace>;
            }
            unsafe { backtrace_capture() }
        }
    }

    impl !Send for Backtrace {}
    impl !Sync for Backtrace {}
    impl Drop for Backtrace {...}
    impl fmt::Debug for Backtrace {...}
    impl fmt::Display for Backtrace {...}
}

mod alloc::panic {
    #[stable]
    pub trait BacktraceImpl: fmt::Debug + fmt::Display + 'static {}

    impl<T: BacktraceImpl> From<Box<T>> for Backtrace {
        fn from(x: Box<T>) -> Self {
            struct Wrapper<T>(T);

            impl<T: BacktraceImpl> RawBacktraceImpl for Wrapper<T> {...}
            impl<T: fmt::Debug> fmt::Debug for Wrapper<T> {...}
            impl<T: fmt::Display> fmt::Display for Wrapper<T> {...}

            unsafe {
                Backtrace::new(Box::into_raw(x) as *mut Wrapper<T> as *mut dyn RawBacktraceImpl)
            }
        }
    }
}

mod std::panic {
    #[lang_item = "backtrace_capture"]
    fn backtrace_capture() -> Option<Backtrace> {
        struct StdBacktrace;

        impl fmt::Debug for StdBacktrace {...}
        impl fmt::Display for StdBacktrace {...}
        impl BacktraceImpl for StdBacktrace {}

        Some(Box::new(StdBacktrace).into())
    }
}

[yaahc]

Status Update

We're getting a clearer and clearer picture of what's needed to move the error trait into core so here is a list of the specific blockers that need to be resolved still:

Integrate negative trait impls with Coherence checks

Currently tracked in:

• Implement coherence checks for negative trait impls rust#85764
• https://rust-lang.zulipchat.com/#narrow/stream/144729-wg-traits/topic/negative.20impls.20in.20coherence

This feature is necessary to handle the following from impl on box.

impl From<&str> for Box<dyn Error> { ... }

Without having negative traits affect coherence moving the error trait into core and moving that From impl to alloc will cause the from impl to no longer compile because of a potential future incompatibility. The compiler indicates that &str could introduce an Error impl in the future, and thus prevents the From impl in alloc that would cause an overlap with From<E: Error> for Box<dyn Error>. Adding impl !Error for &str {} with the negative trait coherence feature will disable this error by encoding a stability guarantee that &str will never implement Error, making the From impl compile.

Resolve fn backtrace in core issue

After fixing the previous issue it will still not be possible to move Error straight into core because it has a method that includes the Backtrace type in it's signature, which is also confined to std rather than core. There are two potential solutions to this we're currently considering.

• Move the Backtrace type to core using lang items to define it's functionality in std or provide a dummy impl / custom impl when in no_std contexts. Draft PR
• Remove fn backtrace from the error trait in favor of generic member access. RFC

We are currently favoring the second option, removing fn backtrace entirely. However this approach is blocked by landing generic member access.

Generic Member Access

In order to remove the backtrace function we need to add an alternative API that maintains equivalent functionality. The Generic member access RFC proposes such a mechanism. This RFC is more or less ready to be implemented but is currently blocked on splitting out the type erasure mechanisms it introduces into its own RFC and landing those first, due to their complexity, and because they're partially justified by usecases unrelated to error handling.

@nrc has written a draft of this RFC: nrc/rfcs#1

Downcast

The last issue is the presence of downcast APIs associated with dyn Errors, some of these APIs reference the Box type, which cannot be moved to core. We currently believe that these methods can be moved to alloc via an impl Box<dyn Error> { ... } block, but this has not been tested yet. Once we resolve the previous three issues we will attempt to move the error trait to core and see if any additional unforeseen issues pop up.