std: Add a `backtrace` module

This commit adds a `backtrace` module to the standard library, as
designed in [RFC 2504]. The `Backtrace` type is intentionally very
conservative, effectively only allowing capturing it and printing it.

Additionally this commit also adds a `backtrace` method to the `Error`
trait which defaults to returning `None`, as specified in [RFC 2504].
More information about the design here can be found in [RFC 2504] and in
the [tracking issue].

Implementation-wise this is all based on the `backtrace` crate and very
closely mirrors the `backtrace::Backtrace` type on crates.io. Otherwise
it's pretty standard in how it handles everything internally.

[RFC 2504]: https://github.com/rust-lang/rfcs/blob/master/text/2504-fix-error.md
[tracking issue]: https://github.com/rust-lang/rust/issues/53487

cc #53487

4 files changed, 433 insertions, 54 deletions

diff --git a/src/libstd/backtrace.rs b/src/libstd/backtrace.rs
new file mode 100644
index 00000000000..5d46ef7dbb1
--- /dev/null
+++ b/src/libstd/backtrace.rs
@@ -0,0 +1,352 @@
+//! Support for capturing a stack backtrace of an OS thread
+//!
+//! This module contains the support necessary to capture a stack backtrace of a
+//! running OS thread from the OS thread itself. The `Backtrace` type supports
+//! capturing a stack trace via the `Backtrace::capture` and
+//! `Backtrace::force_capture` functions.
+//!
+//! A backtrace is typically quite handy to attach to errors (e.g. types
+//! implementing `std::error::Error`) to get a causal chain of where an error
+//! was generated.
+//!
+//! > **Note**: this module is unstable and is designed in [RFC 2504], and you
+//! > can learn more about its status in the [tracking issue].
+//!
+//! [RFC 2504]: https://github.com/rust-lang/rfcs/blob/master/text/2504-fix-error.md
+//! [tracking issue]: https://github.com/rust-lang/rust/issues/53487
+//!
+//! ## Accuracy
+//!
+//! Backtraces are attempted to be as accurate as possible, but no guarantees
+//! are provided about the exact accuracy of a backtrace. Instruction pointers,
+//! symbol names, filenames, line numbers, etc, may all be incorrect when
+//! reported. Accuracy is attempted on a best-effort basis, however, and bugs
+//! are always welcome to indicate areas of improvement!
+//!
+//! For most platforms a backtrace with a filename/line number requires that
+//! programs be compiled with debug information. Without debug information
+//! filenames/line numbers will not be reported.
+//!
+//! ## Platform support
+//!
+//! Not all platforms that libstd compiles for support capturing backtraces.
+//! Some platforms simply do nothing when capturing a backtrace. To check
+//! whether the platform supports capturing backtraces you can consult the
+//! `BacktraceStatus` enum as a result of `Backtrace::status`.
+//!
+//! Like above with accuracy platform support is done on a best effort basis.
+//! Sometimes libraries may not be available at runtime or something may go
+//! wrong which would cause a backtrace to not be captured. Please feel free to
+//! report issues with platforms where a backtrace cannot be captured though!
+//!
+//! ## Environment Variables
+//!
+//! The `Backtrace::capture` function may not actually capture a backtrace by
+//! default. Its behavior is governed by two environment variables:
+//!
+//! * `RUST_LIB_BACKTRACE` - if this is set to `0` then `Backtrace::capture`
+//!   will never capture a backtrace. Any other value this is set to will enable
+//!   `Backtrace::capture`.
+//!
+//! * `RUST_BACKTRACE` - if `RUST_LIB_BACKTRACE` is not set, then this variable
+//!   is consulted with the same rules of `RUST_LIB_BACKTRACE`.
+//!
+//! * If neither of the above env vars are set, then `Backtrace::capture` will
+//!   be disabled.
+//!
+//! Capturing a backtrace can be a quite expensive runtime operation, so the
+//! environment variables allow either forcibly disabling this runtime
+//! performance hit or allow selectively enabling it in some programs.
+//!
+//! Note that the `Backtrace::force_capture` function can be used to ignore
+//! these environment variables. Also note that the state of environment
+//! variables is cached once the first backtrace is created, so altering
+//! `RUST_LIB_BACKTRACE` or `RUST_BACKTRACE` at runtime may not actually change
+//! how backtraces are captured.
+
+#![unstable(feature = "backtrace", issue = "53487")]
+
+// NB: A note on resolution of a backtrace:
+//
+// Backtraces primarily happen in two steps, one is where we actually capture
+// the stack backtrace, giving us a list of instruction pointers corresponding
+// to stack frames. Next we take these instruction pointers and, one-by-one,
+// turn them into a human readable name (like `main`).
+//
+// The first phase can be somewhat expensive (walking the stack), especially
+// on MSVC where debug information is consulted to return inline frames each as
+// their own frame. The second phase, however, is almost always extremely
+// expensive (on the order of milliseconds sometimes) when it's consulting debug
+// information.
+//
+// We attempt to amortize this cost as much as possible by delaying resolution
+// of an address to a human readable name for as long as possible. When
+// `Backtrace::create` is called to capture a backtrace it doesn't actually
+// perform any symbol resolution, but rather we lazily resolve symbols only just
+// before they're needed for printing. This way we can make capturing a
+// backtrace and throwing it away much cheaper, but actually printing a
+// backtrace is still basically the same cost.
+//
+// This strategy comes at the cost of some synchronization required inside of a
+// `Backtrace`, but that's a relatively small price to pay relative to capturing
+// a backtrace or actually symbolizing it.
+
+use crate::env;
+use crate::fmt;
+use crate::sync::atomic::{AtomicUsize, Ordering::SeqCst};
+use crate::sync::Mutex;
+use crate::sys_common::backtrace::{output_filename, lock};
+use crate::vec::Vec;
+use backtrace::BytesOrWideString;
+
+/// A captured OS thread stack backtrace.
+///
+/// This type represents a stack backtrace for an OS thread captured at a
+/// previous point in time. In some instances the `Backtrace` type may
+/// internally be empty due to configuration. For more information see
+/// `Backtrace::capture`.
+pub struct Backtrace {
+    inner: Inner,
+}
+
+/// The current status of a backtrace, indicating whether it was captured or
+/// whether it is empty for some other reason.
+#[non_exhaustive]
+#[derive(Debug)]
+pub enum BacktraceStatus {
+    /// Capturing a backtrace is not supported, likely because it's not
+    /// implemented for the current platform.
+    Unsupported,
+    /// Capturing a backtrace has been disabled through either the
+    /// `RUST_LIB_BACKTRACE` or `RUST_BACKTRACE` environment variables.
+    Disabled,
+    /// A backtrace has been captured and the `Backtrace` should print
+    /// reasonable information when rendered.
+    Captured,
+}
+
+enum Inner {
+    Unsupported,
+    Disabled,
+    Captured(Mutex<Capture>),
+}
+
+struct Capture {
+    actual_start: usize,
+    resolved: bool,
+    frames: Vec<BacktraceFrame>,
+}
+
+fn _assert_send_sync() {
+    fn _assert<T: Send + Sync>() {}
+    _assert::<Backtrace>();
+}
+
+struct BacktraceFrame {
+    frame: backtrace::Frame,
+    symbols: Vec<BacktraceSymbol>,
+}
+
+struct BacktraceSymbol {
+    name: Option<Vec<u8>>,
+    filename: Option<BytesOrWide>,
+    lineno: Option<u32>,
+}
+
+enum BytesOrWide {
+    Bytes(Vec<u8>),
+    Wide(Vec<u16>),
+}
+
+impl Backtrace {
+    /// Returns whether backtrace captures are enabled through environment
+    /// variables.
+    fn enabled() -> bool {
+        // Cache the result of reading the environment variables to make
+        // backtrace captures speedy, because otherwise reading environment
+        // variables every time can be somewhat slow.
+        static ENABLED: AtomicUsize = AtomicUsize::new(0);
+        match ENABLED.load(SeqCst) {
+            0 => {}
+            1 => return false,
+            _ => return true,
+        }
+        let enabled = match env::var("RUST_LIB_BACKTRACE") {
+            Ok(s) => s != "0",
+            Err(_) => match env::var("RUST_BACKTRACE") {
+                Ok(s) => s != "0",
+                Err(_) => false,
+            },
+        };
+        ENABLED.store(enabled as usize + 1, SeqCst);
+        return enabled;
+    }
+
+    /// Capture a stack backtrace of the current thread.
+    ///
+    /// This function will capture a stack backtrace of the current OS thread of
+    /// execution, returning a `Backtrace` type which can be later used to print
+    /// the entire stack trace or render it to a string.
+    ///
+    /// This function will be a noop if the `RUST_BACKTRACE` or
+    /// `RUST_LIB_BACKTRACE` backtrace variables are both not set. If either
+    /// environment variable is set and enabled then this function will actually
+    /// capture a backtrace. Capturing a backtrace can be both memory intensive
+    /// and slow, so these environment variables allow liberally using
+    /// `Backtrace::capture` and only incurring a slowdown when the environment
+    /// variables are set.
+    ///
+    /// To forcibly capture a backtrace regardless of environment variables, use
+    /// the `Backtrace::force_capture` function.
+    #[inline(never)] // want to make sure there's a frame here to remove
+    pub fn capture() -> Backtrace {
+        if !Backtrace::enabled() {
+            return Backtrace { inner: Inner::Disabled };
+        }
+        Backtrace::create(Backtrace::capture as usize)
+    }
+
+    /// Forcibly captures a full backtrace, regardless of environment variable
+    /// configuration.
+    ///
+    /// This function behaves the same as `capture` except that it ignores the
+    /// values of the `RUST_BACKTRACE` and `RUST_LIB_BACKTRACE` environment
+    /// variables, always capturing a backtrace.
+    ///
+    /// Note that capturing a backtrace can be an expensive operation on some
+    /// platforms, so this should be used with caution in performance-sensitive
+    /// parts of code.
+    #[inline(never)] // want to make sure there's a frame here to remove
+    pub fn force_capture() -> Backtrace {
+        Backtrace::create(Backtrace::force_capture as usize)
+    }
+
+    // Capture a backtrace which start just before the function addressed by
+    // `ip`
+    fn create(ip: usize) -> Backtrace {
+        let _lock = lock();
+        let mut frames = Vec::new();
+        let mut actual_start = None;
+        unsafe {
+            backtrace::trace_unsynchronized(|frame| {
+                frames.push(BacktraceFrame { frame: frame.clone(), symbols: Vec::new() });
+                if frame.symbol_address() as usize == ip && actual_start.is_none() {
+                    actual_start = Some(frames.len());
+                }
+                true
+            });
+        }
+
+        // If no frames came out assume that this is an unsupported platform
+        // since `backtrace` doesn't provide a way of learning this right now,
+        // and this should be a good enough approximation.
+        let inner = if frames.len() == 0 {
+            Inner::Unsupported
+        } else {
+            Inner::Captured(Mutex::new(Capture {
+                actual_start: actual_start.unwrap_or(0),
+                frames,
+                resolved: false,
+            }))
+        };
+
+        Backtrace { inner }
+    }
+
+    /// Returns the status of this backtrace, indicating whether this backtrace
+    /// request was unsupported, disabled, or a stack trace was actually
+    /// captured.
+    pub fn status(&self) -> BacktraceStatus {
+        match self.inner {
+            Inner::Unsupported => BacktraceStatus::Unsupported,
+            Inner::Disabled => BacktraceStatus::Disabled,
+            Inner::Captured(_) => BacktraceStatus::Captured,
+        }
+    }
+}
+
+impl fmt::Display for Backtrace {
+    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
+        fmt::Debug::fmt(self, fmt)
+    }
+}
+
+impl fmt::Debug for Backtrace {
+    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
+        let mut capture = match &self.inner {
+            Inner::Unsupported => return fmt.write_str("unsupported backtrace"),
+            Inner::Disabled => return fmt.write_str("disabled backtrace"),
+            Inner::Captured(c) => c.lock().unwrap(),
+        };
+        capture.resolve();
+
+        let full = fmt.alternate();
+        let (frames, style) = if full {
+            (&capture.frames[..], backtrace::PrintFmt::Full)
+        } else {
+            (&capture.frames[capture.actual_start..], backtrace::PrintFmt::Short)
+        };
+
+        // When printing paths we try to strip the cwd if it exists, otherwise
+        // we just print the path as-is. Note that we also only do this for the
+        // short format, because if it's full we presumably want to print
+        // everything.
+        let cwd = crate::env::current_dir();
+        let mut print_path = move |fmt: &mut fmt::Formatter<'_>, path: BytesOrWideString<'_>| {
+            output_filename(fmt, path, style, cwd.as_ref().ok())
+        };
+
+        let mut f = backtrace::BacktraceFmt::new(fmt, style, &mut print_path);
+        f.add_context()?;
+        for frame in frames {
+            let mut f = f.frame();
+            if frame.symbols.is_empty() {
+                f.print_raw(frame.frame.ip(), None, None, None)?;
+            } else {
+                for symbol in frame.symbols.iter() {
+                    f.print_raw(
+                        frame.frame.ip(),
+                        symbol.name.as_ref().map(|b| backtrace::SymbolName::new(b)),
+                        symbol.filename.as_ref().map(|b| match b {
+                            BytesOrWide::Bytes(w) => BytesOrWideString::Bytes(w),
+                            BytesOrWide::Wide(w) => BytesOrWideString::Wide(w),
+                        }),
+                        symbol.lineno,
+                    )?;
+                }
+            }
+        }
+        f.finish()?;
+        Ok(())
+    }
+}
+
+impl Capture {
+    fn resolve(&mut self) {
+        // If we're already resolved, nothing to do!
+        if self.resolved {
+            return;
+        }
+        self.resolved = true;
+
+        // Use the global backtrace lock to synchronize this as it's a
+        // requirement of the `backtrace` crate, and then actually resolve
+        // everything.
+        let _lock = lock();
+        for frame in self.frames.iter_mut() {
+            let symbols = &mut frame.symbols;
+            unsafe {
+                backtrace::resolve_frame_unsynchronized(&frame.frame, |symbol| {
+                    symbols.push(BacktraceSymbol {
+                        name: symbol.name().map(|m| m.as_bytes().to_vec()),
+                        filename: symbol.filename_raw().map(|b| match b {
+                            BytesOrWideString::Bytes(b) => BytesOrWide::Bytes(b.to_owned()),
+                            BytesOrWideString::Wide(b) => BytesOrWide::Wide(b.to_owned()),
+                        }),
+                        lineno: symbol.lineno(),
+                    });
+                });
+            }
+        }
+    }
+}
diff --git a/src/libstd/error.rs b/src/libstd/error.rs
index 117a430eec6..998d59f90a2 100644
--- a/src/libstd/error.rs
+++ b/src/libstd/error.rs
@@ -17,6 +17,7 @@ use core::array;
 
 use crate::alloc::{AllocErr, LayoutErr, CannotReallocInPlace};
 use crate::any::TypeId;
+use crate::backtrace::Backtrace;
 use crate::borrow::Cow;
 use crate::cell;
 use crate::char;
@@ -204,6 +205,20 @@ pub trait Error: Debug + Display {
     fn type_id(&self, _: private::Internal) -> TypeId where Self: 'static {
         TypeId::of::<Self>()
     }
+
+    /// Returns a stack backtrace, if available, of where this error ocurred.
+    ///
+    /// This function allows inspecting the location, in code, of where an error
+    /// happened. The returned `Backtrace` contains information about the stack
+    /// trace of the OS thread of execution of where the error originated from.
+    ///
+    /// Note that not all errors contain a `Backtrace`. Also note that a
+    /// `Backtrace` may actually be empty. For more information consult the
+    /// `Backtrace` type itself.
+    #[unstable(feature = "backtrace", issue = "53487")]
+    fn backtrace(&self) -> Option<&Backtrace> {
+        None
+    }
 }
 
 mod private {
diff --git a/src/libstd/lib.rs b/src/libstd/lib.rs
index 71050b0dcd1..388c997d7c7 100644
--- a/src/libstd/lib.rs
+++ b/src/libstd/lib.rs
@@ -452,6 +452,7 @@ pub mod f64;
 #[macro_use]
 pub mod thread;
 pub mod ascii;
+pub mod backtrace;
 pub mod collections;
 pub mod env;
 pub mod error;
diff --git a/src/libstd/sys_common/backtrace.rs b/src/libstd/sys_common/backtrace.rs
index f434b62aced..839dc51b9e9 100644
--- a/src/libstd/sys_common/backtrace.rs
+++ b/src/libstd/sys_common/backtrace.rs
@@ -4,8 +4,9 @@
 use crate::env;
 use crate::fmt;
 use crate::io;
+use crate::borrow::Cow;
 use crate::io::prelude::*;
-use crate::path::{self, Path};
+use crate::path::{self, Path, PathBuf};
 use crate::sync::atomic::{self, Ordering};
 use crate::sys::mutex::Mutex;
 
@@ -14,10 +15,26 @@ use backtrace::{BacktraceFmt, BytesOrWideString, PrintFmt};
 /// Max number of frames to print.
 const MAX_NB_FRAMES: usize = 100;
 
-/// Prints the current backtrace.
-pub fn print(w: &mut dyn Write, format: PrintFmt) -> io::Result<()> {
+pub fn lock() -> impl Drop {
+    struct Guard;
     static LOCK: Mutex = Mutex::new();
 
+    impl Drop for Guard {
+        fn drop(&mut self) {
+            unsafe {
+                LOCK.unlock();
+            }
+        }
+    }
+
+    unsafe {
+        LOCK.lock();
+        return Guard;
+    }
+}
+
+/// Prints the current backtrace.
+pub fn print(w: &mut dyn Write, format: PrintFmt) -> io::Result<()> {
     // There are issues currently linking libbacktrace into tests, and in
     // general during libstd's own unit tests we're not testing this path. In
     // test mode immediately return here to optimize away any references to the
@@ -29,71 +46,67 @@ pub fn print(w: &mut dyn Write, format: PrintFmt) -> io::Result<()> {
     // Use a lock to prevent mixed output in multithreading context.
     // Some platforms also requires it, like `SymFromAddr` on Windows.
     unsafe {
-        LOCK.lock();
-        let res = _print(w, format);
-        LOCK.unlock();
-        res
+        let _lock = lock();
+        _print(w, format)
     }
 }
 
-fn _print(w: &mut dyn Write, format: PrintFmt) -> io::Result<()> {
+unsafe fn _print(w: &mut dyn Write, format: PrintFmt) -> io::Result<()> {
     struct DisplayBacktrace {
         format: PrintFmt,
     }
     impl fmt::Display for DisplayBacktrace {
         fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
-            _print_fmt(fmt, self.format)
+            unsafe {
+                _print_fmt(fmt, self.format)
+            }
         }
     }
     write!(w, "{}", DisplayBacktrace { format })
 }
 
-fn _print_fmt(fmt: &mut fmt::Formatter<'_>, print_fmt: PrintFmt) -> fmt::Result {
+unsafe fn _print_fmt(fmt: &mut fmt::Formatter<'_>, print_fmt: PrintFmt) -> fmt::Result {
+    let cwd = env::current_dir().ok();
     let mut print_path = move |fmt: &mut fmt::Formatter<'_>, bows: BytesOrWideString<'_>| {
-        output_filename(fmt, bows, print_fmt)
+        output_filename(fmt, bows, print_fmt, cwd.as_ref())
     };
     let mut bt_fmt = BacktraceFmt::new(fmt, print_fmt, &mut print_path);
     bt_fmt.add_context()?;
-    let mut skipped = false;
-    unsafe {
-        let mut idx = 0;
-        let mut res = Ok(());
-        backtrace::trace_unsynchronized(|frame| {
-            if print_fmt == PrintFmt::Short && idx > MAX_NB_FRAMES {
-                skipped = true;
-                return false;
-            }
+    let mut idx = 0;
+    let mut res = Ok(());
+    backtrace::trace_unsynchronized(|frame| {
+        if print_fmt == PrintFmt::Short && idx > MAX_NB_FRAMES {
+            return false;
+        }
 
-            let mut hit = false;
-            let mut stop = false;
-            backtrace::resolve_frame_unsynchronized(frame, |symbol| {
-                hit = true;
-                if print_fmt == PrintFmt::Short {
-                    if let Some(sym) = symbol.name().and_then(|s| s.as_str()) {
-                        if sym.contains("__rust_begin_short_backtrace") {
-                            skipped = true;
-                            stop = true;
-                            return;
-                        }
+        let mut hit = false;
+        let mut stop = false;
+        backtrace::resolve_frame_unsynchronized(frame, |symbol| {
+            hit = true;
+            if print_fmt == PrintFmt::Short {
+                if let Some(sym) = symbol.name().and_then(|s| s.as_str()) {
+                    if sym.contains("__rust_begin_short_backtrace") {
+                        stop = true;
+                        return;
                     }
                 }
-
-                res = bt_fmt.frame().symbol(frame, symbol);
-            });
-            if stop {
-                return false;
-            }
-            if !hit {
-                res = bt_fmt.frame().print_raw(frame.ip(), None, None, None);
             }
 
-            idx += 1;
-            res.is_ok()
+            res = bt_fmt.frame().symbol(frame, symbol);
         });
-        res?;
-    }
+        if stop {
+            return false;
+        }
+        if !hit {
+            res = bt_fmt.frame().print_raw(frame.ip(), None, None, None);
+        }
+
+        idx += 1;
+        res.is_ok()
+    });
+    res?;
     bt_fmt.finish()?;
-    if skipped {
+    if print_fmt == PrintFmt::Short {
         writeln!(
             fmt,
             "note: Some details are omitted, \
@@ -147,36 +160,34 @@ pub fn log_enabled() -> Option<PrintFmt> {
 /// Prints the filename of the backtrace frame.
 ///
 /// See also `output`.
-fn output_filename(
+pub fn output_filename(
     fmt: &mut fmt::Formatter<'_>,
     bows: BytesOrWideString<'_>,
     print_fmt: PrintFmt,
+    cwd: Option<&PathBuf>,
 ) -> fmt::Result {
-    #[cfg(windows)]
-    let path_buf;
-    let file = match bows {
+    let file: Cow<'_, Path> = match bows {
         #[cfg(unix)]
         BytesOrWideString::Bytes(bytes) => {
             use crate::os::unix::prelude::*;
-            Path::new(crate::ffi::OsStr::from_bytes(bytes))
+            Path::new(crate::ffi::OsStr::from_bytes(bytes)).into()
         }
         #[cfg(not(unix))]
         BytesOrWideString::Bytes(bytes) => {
-            Path::new(crate::str::from_utf8(bytes).unwrap_or("<unknown>"))
+            Path::new(crate::str::from_utf8(bytes).unwrap_or("<unknown>")).into()
         }
         #[cfg(windows)]
         BytesOrWideString::Wide(wide) => {
             use crate::os::windows::prelude::*;
-            path_buf = crate::ffi::OsString::from_wide(wide);
-            Path::new(&path_buf)
+            Cow::Owned(crate::ffi::OsString::from_wide(wide).into())
         }
         #[cfg(not(windows))]
         BytesOrWideString::Wide(_wide) => {
-            Path::new("<unknown>")
+            Path::new("<unknown>").into()
         }
     };
     if print_fmt == PrintFmt::Short && file.is_absolute() {
-        if let Ok(cwd) = env::current_dir() {
+        if let Some(cwd) = cwd {
             if let Ok(stripped) = file.strip_prefix(&cwd) {
                 if let Some(s) = stripped.to_str() {
                     return write!(fmt, ".{}{}", path::MAIN_SEPARATOR, s);