diff options
21 files changed, 894 insertions, 825 deletions
diff --git a/Cargo.lock b/Cargo.lock index 09eb0d98efc..74f96983b31 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -212,9 +212,9 @@ checksum = "96d30a06541fbafbc7f82ed10c06164cfbd2c401138f6addd8404629c4b16711" [[package]] name = "askama" -version = "0.12.0" +version = "0.12.1" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "47cbc3cf73fa8d9833727bbee4835ba5c421a0d65b72daf9a7b5d0e0f9cfb57e" +checksum = "b79091df18a97caea757e28cd2d5fda49c6cd4bd01ddffd7ff01ace0c0ad2c28" dependencies = [ "askama_derive", "askama_escape", @@ -222,14 +222,14 @@ dependencies = [ [[package]] name = "askama_derive" -version = "0.12.1" +version = "0.12.5" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "c22fbe0413545c098358e56966ff22cdd039e10215ae213cfbd65032b119fc94" +checksum = "19fe8d6cb13c4714962c072ea496f3392015f0989b1a2847bb4b2d9effd71d83" dependencies = [ + "askama_parser", "basic-toml", "mime", "mime_guess", - "nom", "proc-macro2", "quote", "serde", @@ -243,6 +243,15 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "619743e34b5ba4e9703bba34deac3427c72507c7159f5fd030aea8cac0cfe341" [[package]] +name = "askama_parser" +version = "0.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "acb1161c6b64d1c3d83108213c2a2533a342ac225aabd0bda218278c2ddb00c0" +dependencies = [ + "nom", +] + +[[package]] name = "autocfg" version = "1.1.0" source = "registry+https://github.com/rust-lang/crates.io-index" diff --git a/compiler/rustc_ast/src/visit.rs b/compiler/rustc_ast/src/visit.rs index 89f50d3a0a7..8d084ee29a7 100644 --- a/compiler/rustc_ast/src/visit.rs +++ b/compiler/rustc_ast/src/visit.rs @@ -375,11 +375,11 @@ pub fn walk_item<'a, V: Visitor<'a>>(visitor: &mut V, item: &'a Item) { } ItemKind::MacCall(mac) => visitor.visit_mac_call(mac), ItemKind::MacroDef(ts) => visitor.visit_mac_def(ts, item.id), - ItemKind::Delegation(box Delegation { id: _, qself, path, body }) => { + ItemKind::Delegation(box Delegation { id, qself, path, body }) => { if let Some(qself) = qself { visitor.visit_ty(&qself.ty); } - walk_path(visitor, path); + visitor.visit_path(path, *id); if let Some(body) = body { visitor.visit_block(body); } @@ -502,7 +502,7 @@ where } GenericArgs::Parenthesized(data) => { walk_list!(visitor, visit_ty, &data.inputs); - walk_fn_ret_ty(visitor, &data.output); + visitor.visit_fn_ret_ty(&data.output); } } } @@ -713,11 +713,11 @@ pub fn walk_assoc_item<'a, V: Visitor<'a>>(visitor: &mut V, item: &'a AssocItem, AssocItemKind::MacCall(mac) => { visitor.visit_mac_call(mac); } - AssocItemKind::Delegation(box Delegation { id: _, qself, path, body }) => { + AssocItemKind::Delegation(box Delegation { id, qself, path, body }) => { if let Some(qself) = qself { visitor.visit_ty(&qself.ty); } - walk_path(visitor, path); + visitor.visit_path(path, *id); if let Some(body) = body { visitor.visit_block(body); } diff --git a/compiler/rustc_codegen_ssa/src/back/link.rs b/compiler/rustc_codegen_ssa/src/back/link.rs index 959653c9326..f098fc9cb59 100644 --- a/compiler/rustc_codegen_ssa/src/back/link.rs +++ b/compiler/rustc_codegen_ssa/src/back/link.rs @@ -52,6 +52,15 @@ use std::path::{Path, PathBuf}; use std::process::{ExitStatus, Output, Stdio}; use std::{env, fmt, fs, io, mem, str}; +#[derive(Default)] +pub struct SearchPaths(OnceCell<Vec<PathBuf>>); + +impl SearchPaths { + pub(super) fn get(&self, sess: &Session) -> &[PathBuf] { + self.0.get_or_init(|| archive_search_paths(sess)) + } +} + pub fn ensure_removed(dcx: &DiagCtxt, path: &Path) { if let Err(e) = fs::remove_file(path) { if e.kind() != io::ErrorKind::NotFound { @@ -1265,7 +1274,7 @@ fn link_sanitizer_runtime( let path = find_sanitizer_runtime(sess, &filename); let rpath = path.to_str().expect("non-utf8 component in path"); linker.args(&["-Wl,-rpath", "-Xlinker", rpath]); - linker.link_dylib(&filename, false, true); + linker.link_dylib_by_name(&filename, false, true); } else if sess.target.is_like_msvc && flavor == LinkerFlavor::Msvc(Lld::No) && name == "asan" { // MSVC provides the `/INFERASANLIBS` argument to automatically find the // compatible ASAN library. @@ -1273,7 +1282,7 @@ fn link_sanitizer_runtime( } else { let filename = format!("librustc{channel}_rt.{name}.a"); let path = find_sanitizer_runtime(sess, &filename).join(&filename); - linker.link_whole_rlib(&path); + linker.link_staticlib_by_path(&path, true); } } @@ -2445,7 +2454,7 @@ fn add_native_libs_from_crate( archive_builder_builder: &dyn ArchiveBuilderBuilder, codegen_results: &CodegenResults, tmpdir: &Path, - search_paths: &OnceCell<Vec<PathBuf>>, + search_paths: &SearchPaths, bundled_libs: &FxHashSet<Symbol>, cnum: CrateNum, link_static: bool, @@ -2505,28 +2514,16 @@ fn add_native_libs_from_crate( if let Some(filename) = lib.filename { // If rlib contains native libs as archives, they are unpacked to tmpdir. let path = tmpdir.join(filename.as_str()); - if whole_archive { - cmd.link_whole_rlib(&path); - } else { - cmd.link_rlib(&path); - } + cmd.link_staticlib_by_path(&path, whole_archive); } } else { - if whole_archive { - cmd.link_whole_staticlib( - name, - verbatim, - search_paths.get_or_init(|| archive_search_paths(sess)), - ); - } else { - cmd.link_staticlib(name, verbatim) - } + cmd.link_staticlib_by_name(name, verbatim, whole_archive, search_paths); } } } NativeLibKind::Dylib { as_needed } => { if link_dynamic { - cmd.link_dylib(name, verbatim, as_needed.unwrap_or(true)) + cmd.link_dylib_by_name(name, verbatim, as_needed.unwrap_or(true)) } } NativeLibKind::Unspecified => { @@ -2534,17 +2531,17 @@ fn add_native_libs_from_crate( // link kind is unspecified. if !link_output_kind.can_link_dylib() && !sess.target.crt_static_allows_dylibs { if link_static { - cmd.link_staticlib(name, verbatim) + cmd.link_staticlib_by_name(name, verbatim, false, search_paths); } } else { if link_dynamic { - cmd.link_dylib(name, verbatim, true); + cmd.link_dylib_by_name(name, verbatim, true); } } } NativeLibKind::Framework { as_needed } => { if link_dynamic { - cmd.link_framework(name, as_needed.unwrap_or(true)) + cmd.link_framework_by_name(name, verbatim, as_needed.unwrap_or(true)) } } NativeLibKind::RawDylib => { @@ -2581,7 +2578,7 @@ fn add_local_native_libraries( } } - let search_paths = OnceCell::new(); + let search_paths = SearchPaths::default(); // All static and dynamic native library dependencies are linked to the local crate. let link_static = true; let link_dynamic = true; @@ -2623,7 +2620,7 @@ fn add_upstream_rust_crates<'a>( .find(|(ty, _)| *ty == crate_type) .expect("failed to find crate type in dependency format list"); - let search_paths = OnceCell::new(); + let search_paths = SearchPaths::default(); for &cnum in &codegen_results.crate_info.used_crates { // We may not pass all crates through to the linker. Some crates may appear statically in // an existing dylib, meaning we'll pick up all the symbols from the dylib. @@ -2698,7 +2695,7 @@ fn add_upstream_native_libraries( tmpdir: &Path, link_output_kind: LinkOutputKind, ) { - let search_path = OnceCell::new(); + let search_paths = SearchPaths::default(); for &cnum in &codegen_results.crate_info.used_crates { // Static libraries are not linked here, they are linked in `add_upstream_rust_crates`. // FIXME: Merge this function to `add_upstream_rust_crates` so that all native libraries @@ -2720,7 +2717,7 @@ fn add_upstream_native_libraries( archive_builder_builder, codegen_results, tmpdir, - &search_path, + &search_paths, &Default::default(), cnum, link_static, @@ -2791,7 +2788,7 @@ fn add_static_crate<'a>( } else { fix_windows_verbatim_for_gcc(path) }; - cmd.link_rlib(&rlib_path); + cmd.link_staticlib_by_path(&rlib_path, false); }; if !are_upstream_rust_objects_already_included(sess) @@ -2859,13 +2856,24 @@ fn add_dynamic_crate(cmd: &mut dyn Linker, sess: &Session, cratepath: &Path) { // Just need to tell the linker about where the library lives and // what its name is let parent = cratepath.parent(); + // When producing a dll, the MSVC linker may not actually emit a + // `foo.lib` file if the dll doesn't actually export any symbols, so we + // check to see if the file is there and just omit linking to it if it's + // not present. + if sess.target.is_like_msvc && !cratepath.with_extension("dll.lib").exists() { + return; + } if let Some(dir) = parent { cmd.include_path(&rehome_sysroot_lib_dir(sess, dir)); } - let stem = cratepath.file_stem().unwrap().to_str().unwrap(); + // "<dir>/name.dll -> name.dll" on windows-msvc + // "<dir>/name.dll -> name" on windows-gnu + // "<dir>/libname.<ext> -> name" elsewhere + let stem = if sess.target.is_like_msvc { cratepath.file_name() } else { cratepath.file_stem() }; + let stem = stem.unwrap().to_str().unwrap(); // Convert library file-stem into a cc -l argument. let prefix = if stem.starts_with("lib") && !sess.target.is_like_windows { 3 } else { 0 }; - cmd.link_rust_dylib(&stem[prefix..], parent.unwrap_or_else(|| Path::new(""))); + cmd.link_dylib_by_name(&stem[prefix..], false, true); } fn relevant_lib(sess: &Session, lib: &NativeLib) -> bool { diff --git a/compiler/rustc_codegen_ssa/src/back/linker.rs b/compiler/rustc_codegen_ssa/src/back/linker.rs index 90f5027c264..9f06f398288 100644 --- a/compiler/rustc_codegen_ssa/src/back/linker.rs +++ b/compiler/rustc_codegen_ssa/src/back/linker.rs @@ -1,5 +1,6 @@ use super::command::Command; use super::symbol_export; +use crate::back::link::SearchPaths; use crate::errors; use rustc_span::symbol::sym; @@ -166,13 +167,18 @@ pub fn get_linker<'a>( pub trait Linker { fn cmd(&mut self) -> &mut Command; fn set_output_kind(&mut self, output_kind: LinkOutputKind, out_filename: &Path); - fn link_dylib(&mut self, lib: &str, verbatim: bool, as_needed: bool); - fn link_rust_dylib(&mut self, lib: &str, path: &Path); - fn link_framework(&mut self, framework: &str, as_needed: bool); - fn link_staticlib(&mut self, lib: &str, verbatim: bool); - fn link_rlib(&mut self, lib: &Path); - fn link_whole_rlib(&mut self, lib: &Path); - fn link_whole_staticlib(&mut self, lib: &str, verbatim: bool, search_path: &[PathBuf]); + fn link_dylib_by_name(&mut self, name: &str, verbatim: bool, as_needed: bool); + fn link_framework_by_name(&mut self, _name: &str, _verbatim: bool, _as_needed: bool) { + bug!("framework linked with unsupported linker") + } + fn link_staticlib_by_name( + &mut self, + name: &str, + verbatim: bool, + whole_archive: bool, + search_paths: &SearchPaths, + ); + fn link_staticlib_by_path(&mut self, path: &Path, whole_archive: bool); fn include_path(&mut self, path: &Path); fn framework_path(&mut self, path: &Path); fn output_filename(&mut self, path: &Path); @@ -432,8 +438,8 @@ impl<'a> Linker for GccLinker<'a> { } } - fn link_dylib(&mut self, lib: &str, verbatim: bool, as_needed: bool) { - if self.sess.target.os == "illumos" && lib == "c" { + fn link_dylib_by_name(&mut self, name: &str, verbatim: bool, as_needed: bool) { + if self.sess.target.os == "illumos" && name == "c" { // libc will be added via late_link_args on illumos so that it will // appear last in the library search order. // FIXME: This should be replaced by a more complete and generic @@ -454,7 +460,7 @@ impl<'a> Linker for GccLinker<'a> { } } self.hint_dynamic(); - self.cmd.arg(format!("-l{}{lib}", if verbatim && self.is_gnu { ":" } else { "" },)); + self.cmd.arg(format!("-l{}{name}", if verbatim && self.is_gnu { ":" } else { "" },)); if !as_needed { if self.sess.target.is_like_osx { // See above FIXME comment @@ -463,14 +469,56 @@ impl<'a> Linker for GccLinker<'a> { } } } - fn link_staticlib(&mut self, lib: &str, verbatim: bool) { + + fn link_framework_by_name(&mut self, name: &str, _verbatim: bool, as_needed: bool) { + self.hint_dynamic(); + if !as_needed { + // FIXME(81490): ld64 as of macOS 11 supports the -needed_framework + // flag but we have no way to detect that here. + // self.cmd.arg("-needed_framework").arg(name); + self.sess.dcx().emit_warn(errors::Ld64UnimplementedModifier); + } + self.cmd.arg("-framework").arg(name); + } + + fn link_staticlib_by_name( + &mut self, + name: &str, + verbatim: bool, + whole_archive: bool, + search_paths: &SearchPaths, + ) { self.hint_static(); - self.cmd.arg(format!("-l{}{lib}", if verbatim && self.is_gnu { ":" } else { "" },)); + let colon = if verbatim && self.is_gnu { ":" } else { "" }; + if !whole_archive { + self.cmd.arg(format!("-l{colon}{name}")); + } else if self.sess.target.is_like_osx { + // -force_load is the macOS equivalent of --whole-archive, but it + // involves passing the full path to the library to link. + self.linker_arg("-force_load"); + let search_paths = search_paths.get(self.sess); + self.linker_arg(find_native_static_library(name, verbatim, search_paths, self.sess)); + } else { + self.linker_arg("--whole-archive"); + self.cmd.arg(format!("-l{colon}{name}")); + self.linker_arg("--no-whole-archive"); + } } - fn link_rlib(&mut self, lib: &Path) { + + fn link_staticlib_by_path(&mut self, path: &Path, whole_archive: bool) { self.hint_static(); - self.cmd.arg(lib); + if !whole_archive { + self.cmd.arg(path); + } else if self.sess.target.is_like_osx { + self.linker_arg("-force_load"); + self.linker_arg(path); + } else { + self.linker_arg("--whole-archive"); + self.linker_arg(path); + self.linker_arg("--no-whole-archive"); + } } + fn include_path(&mut self, path: &Path) { self.cmd.arg("-L").arg(path); } @@ -493,55 +541,6 @@ impl<'a> Linker for GccLinker<'a> { self.linker_args(&["-z", "norelro"]); } - fn link_rust_dylib(&mut self, lib: &str, _path: &Path) { - self.hint_dynamic(); - self.cmd.arg(format!("-l{lib}")); - } - - fn link_framework(&mut self, framework: &str, as_needed: bool) { - self.hint_dynamic(); - if !as_needed { - // FIXME(81490): ld64 as of macOS 11 supports the -needed_framework - // flag but we have no way to detect that here. - // self.cmd.arg("-needed_framework").arg(framework); - self.sess.dcx().emit_warn(errors::Ld64UnimplementedModifier); - } - self.cmd.arg("-framework").arg(framework); - } - - // Here we explicitly ask that the entire archive is included into the - // result artifact. For more details see #15460, but the gist is that - // the linker will strip away any unused objects in the archive if we - // don't otherwise explicitly reference them. This can occur for - // libraries which are just providing bindings, libraries with generic - // functions, etc. - fn link_whole_staticlib(&mut self, lib: &str, verbatim: bool, search_path: &[PathBuf]) { - self.hint_static(); - let target = &self.sess.target; - if !target.is_like_osx { - self.linker_arg("--whole-archive"); - self.cmd.arg(format!("-l{}{lib}", if verbatim && self.is_gnu { ":" } else { "" },)); - self.linker_arg("--no-whole-archive"); - } else { - // -force_load is the macOS equivalent of --whole-archive, but it - // involves passing the full path to the library to link. - self.linker_arg("-force_load"); - let lib = find_native_static_library(lib, verbatim, search_path, self.sess); - self.linker_arg(&lib); - } - } - - fn link_whole_rlib(&mut self, lib: &Path) { - self.hint_static(); - if self.sess.target.is_like_osx { - self.linker_arg("-force_load"); - self.linker_arg(&lib); - } else { - self.linker_args(&[OsString::from("--whole-archive"), lib.into()]); - self.linker_arg("--no-whole-archive"); - } - } - fn gc_sections(&mut self, keep_metadata: bool) { // The dead_strip option to the linker specifies that functions and data // unreachable by the entry point will be removed. This is quite useful @@ -821,9 +820,32 @@ impl<'a> Linker for MsvcLinker<'a> { } } - fn link_rlib(&mut self, lib: &Path) { - self.cmd.arg(lib); + fn link_dylib_by_name(&mut self, name: &str, verbatim: bool, _as_needed: bool) { + self.cmd.arg(format!("{}{}", name, if verbatim { "" } else { ".lib" })); + } + + fn link_staticlib_by_name( + &mut self, + name: &str, + verbatim: bool, + whole_archive: bool, + _search_paths: &SearchPaths, + ) { + let prefix = if whole_archive { "/WHOLEARCHIVE:" } else { "" }; + let suffix = if verbatim { "" } else { ".lib" }; + self.cmd.arg(format!("{prefix}{name}{suffix}")); + } + + fn link_staticlib_by_path(&mut self, path: &Path, whole_archive: bool) { + if !whole_archive { + self.cmd.arg(path); + } else { + let mut arg = OsString::from("/WHOLEARCHIVE:"); + arg.push(path); + self.cmd.arg(arg); + } } + fn add_object(&mut self, path: &Path) { self.cmd.arg(path); } @@ -845,25 +867,6 @@ impl<'a> Linker for MsvcLinker<'a> { self.cmd.arg("/OPT:NOREF,NOICF"); } - fn link_dylib(&mut self, lib: &str, verbatim: bool, _as_needed: bool) { - self.cmd.arg(format!("{}{}", lib, if verbatim { "" } else { ".lib" })); - } - - fn link_rust_dylib(&mut self, lib: &str, path: &Path) { - // When producing a dll, the MSVC linker may not actually emit a - // `foo.lib` file if the dll doesn't actually export any symbols, so we - // check to see if the file is there and just omit linking to it if it's - // not present. - let name = format!("{lib}.dll.lib"); - if path.join(&name).exists() { - self.cmd.arg(name); - } - } - - fn link_staticlib(&mut self, lib: &str, verbatim: bool) { - self.cmd.arg(format!("{}{}", lib, if verbatim { "" } else { ".lib" })); - } - fn full_relro(&mut self) { // noop } @@ -899,18 +902,7 @@ impl<'a> Linker for MsvcLinker<'a> { fn framework_path(&mut self, _path: &Path) { bug!("frameworks are not supported on windows") } - fn link_framework(&mut self, _framework: &str, _as_needed: bool) { - bug!("frameworks are not supported on windows") - } - fn link_whole_staticlib(&mut self, lib: &str, verbatim: bool, _search_path: &[PathBuf]) { - self.cmd.arg(format!("/WHOLEARCHIVE:{}{}", lib, if verbatim { "" } else { ".lib" })); - } - fn link_whole_rlib(&mut self, path: &Path) { - let mut arg = OsString::from("/WHOLEARCHIVE:"); - arg.push(path); - self.cmd.arg(arg); - } fn optimize(&mut self) { // Needs more investigation of `/OPT` arguments } @@ -1057,43 +1049,35 @@ impl<'a> Linker for EmLinker<'a> { fn set_output_kind(&mut self, _output_kind: LinkOutputKind, _out_filename: &Path) {} - fn include_path(&mut self, path: &Path) { - self.cmd.arg("-L").arg(path); - } - - fn link_staticlib(&mut self, lib: &str, _verbatim: bool) { - self.cmd.arg("-l").arg(lib); + fn link_dylib_by_name(&mut self, name: &str, _verbatim: bool, _as_needed: bool) { + // Emscripten always links statically + self.cmd.arg("-l").arg(name); } - fn output_filename(&mut self, path: &Path) { - self.cmd.arg("-o").arg(path); + fn link_staticlib_by_name( + &mut self, + name: &str, + _verbatim: bool, + _whole_archive: bool, + _search_paths: &SearchPaths, + ) { + self.cmd.arg("-l").arg(name); } - fn add_object(&mut self, path: &Path) { + fn link_staticlib_by_path(&mut self, path: &Path, _whole_archive: bool) { self.cmd.arg(path); } - fn link_dylib(&mut self, lib: &str, verbatim: bool, _as_needed: bool) { - // Emscripten always links statically - self.link_staticlib(lib, verbatim); - } - - fn link_whole_staticlib(&mut self, lib: &str, verbatim: bool, _search_path: &[PathBuf]) { - // not supported? - self.link_staticlib(lib, verbatim); - } - - fn link_whole_rlib(&mut self, lib: &Path) { - // not supported? - self.link_rlib(lib); + fn include_path(&mut self, path: &Path) { + self.cmd.arg("-L").arg(path); } - fn link_rust_dylib(&mut self, lib: &str, _path: &Path) { - self.link_dylib(lib, false, true); + fn output_filename(&mut self, path: &Path) { + self.cmd.arg("-o").arg(path); } - fn link_rlib(&mut self, lib: &Path) { - self.add_object(lib); + fn add_object(&mut self, path: &Path) { + self.cmd.arg(path); } fn full_relro(&mut self) { @@ -1112,10 +1096,6 @@ impl<'a> Linker for EmLinker<'a> { bug!("frameworks are not supported on Emscripten") } - fn link_framework(&mut self, _framework: &str, _as_needed: bool) { - bug!("frameworks are not supported on Emscripten") - } - fn gc_sections(&mut self, _keep_metadata: bool) { // noop } @@ -1249,16 +1229,30 @@ impl<'a> Linker for WasmLd<'a> { } } - fn link_dylib(&mut self, lib: &str, _verbatim: bool, _as_needed: bool) { - self.cmd.arg("-l").arg(lib); + fn link_dylib_by_name(&mut self, name: &str, _verbatim: bool, _as_needed: bool) { + self.cmd.arg("-l").arg(name); } - fn link_staticlib(&mut self, lib: &str, _verbatim: bool) { - self.cmd.arg("-l").arg(lib); + fn link_staticlib_by_name( + &mut self, + name: &str, + _verbatim: bool, + whole_archive: bool, + _search_paths: &SearchPaths, + ) { + if !whole_archive { + self.cmd.arg("-l").arg(name); + } else { + self.cmd.arg("--whole-archive").arg("-l").arg(name).arg("--no-whole-archive"); + } } - fn link_rlib(&mut self, lib: &Path) { - self.cmd.arg(lib); + fn link_staticlib_by_path(&mut self, path: &Path, whole_archive: bool) { + if !whole_archive { + self.cmd.arg(path); + } else { + self.cmd.arg("--whole-archive").arg(path).arg("--no-whole-archive"); + } } fn include_path(&mut self, path: &Path) { @@ -1283,22 +1277,6 @@ impl<'a> Linker for WasmLd<'a> { fn no_relro(&mut self) {} - fn link_rust_dylib(&mut self, lib: &str, _path: &Path) { - self.cmd.arg("-l").arg(lib); - } - - fn link_framework(&mut self, _framework: &str, _as_needed: bool) { - panic!("frameworks not supported") - } - - fn link_whole_staticlib(&mut self, lib: &str, _verbatim: bool, _search_path: &[PathBuf]) { - self.cmd.arg("--whole-archive").arg("-l").arg(lib).arg("--no-whole-archive"); - } - - fn link_whole_rlib(&mut self, lib: &Path) { - self.cmd.arg("--whole-archive").arg(lib).arg("--no-whole-archive"); - } - fn gc_sections(&mut self, _keep_metadata: bool) { self.cmd.arg("--gc-sections"); } @@ -1398,17 +1376,40 @@ pub struct L4Bender<'a> { } impl<'a> Linker for L4Bender<'a> { - fn link_dylib(&mut self, _lib: &str, _verbatim: bool, _as_needed: bool) { + fn cmd(&mut self) -> &mut Command { + &mut self.cmd + } + + fn set_output_kind(&mut self, _output_kind: LinkOutputKind, _out_filename: &Path) {} + + fn link_dylib_by_name(&mut self, _name: &str, _verbatim: bool, _as_needed: bool) { bug!("dylibs are not supported on L4Re"); } - fn link_staticlib(&mut self, lib: &str, _verbatim: bool) { + + fn link_staticlib_by_name( + &mut self, + name: &str, + _verbatim: bool, + whole_archive: bool, + _search_paths: &SearchPaths, + ) { self.hint_static(); - self.cmd.arg(format!("-PC{lib}")); + if !whole_archive { + self.cmd.arg(format!("-PC{name}")); + } else { + self.cmd.arg("--whole-archive").arg(format!("-l{name}")).arg("--no-whole-archive"); + } } - fn link_rlib(&mut self, lib: &Path) { + + fn link_staticlib_by_path(&mut self, path: &Path, whole_archive: bool) { self.hint_static(); - self.cmd.arg(lib); + if !whole_archive { + self.cmd.arg(path); + } else { + self.cmd.arg("--whole-archive").arg(path).arg("--no-whole-archive"); + } } + fn include_path(&mut self, path: &Path) { self.cmd.arg("-L").arg(path); } @@ -1436,31 +1437,6 @@ impl<'a> Linker for L4Bender<'a> { self.cmd.arg("-z").arg("norelro"); } - fn cmd(&mut self) -> &mut Command { - &mut self.cmd - } - - fn set_output_kind(&mut self, _output_kind: LinkOutputKind, _out_filename: &Path) {} - - fn link_rust_dylib(&mut self, _: &str, _: &Path) { - panic!("Rust dylibs not supported"); - } - - fn link_framework(&mut self, _framework: &str, _as_needed: bool) { - bug!("frameworks not supported on L4Re"); - } - - fn link_whole_staticlib(&mut self, lib: &str, _verbatim: bool, _search_path: &[PathBuf]) { - self.hint_static(); - self.cmd.arg("--whole-archive").arg(format!("-l{lib}")); - self.cmd.arg("--no-whole-archive"); - } - - fn link_whole_rlib(&mut self, lib: &Path) { - self.hint_static(); - self.cmd.arg("--whole-archive").arg(lib).arg("--no-whole-archive"); - } - fn gc_sections(&mut self, keep_metadata: bool) { if !keep_metadata { self.cmd.arg("--gc-sections"); @@ -1571,19 +1547,56 @@ impl<'a> AixLinker<'a> { } impl<'a> Linker for AixLinker<'a> { - fn link_dylib(&mut self, lib: &str, _verbatim: bool, _as_needed: bool) { + fn cmd(&mut self) -> &mut Command { + &mut self.cmd + } + + fn set_output_kind(&mut self, output_kind: LinkOutputKind, out_filename: &Path) { + match output_kind { + LinkOutputKind::DynamicDylib => { + self.hint_dynamic(); + self.build_dylib(out_filename); + } + LinkOutputKind::StaticDylib => { + self.hint_static(); + self.build_dylib(out_filename); + } + _ => {} + } + } + + fn link_dylib_by_name(&mut self, name: &str, _verbatim: bool, _as_needed: bool) { self.hint_dynamic(); - self.cmd.arg(format!("-l{lib}")); + self.cmd.arg(format!("-l{name}")); } - fn link_staticlib(&mut self, lib: &str, _verbatim: bool) { + fn link_staticlib_by_name( + &mut self, + name: &str, + verbatim: bool, + whole_archive: bool, + search_paths: &SearchPaths, + ) { self.hint_static(); - self.cmd.arg(format!("-l{lib}")); + if !whole_archive { + self.cmd.arg(format!("-l{name}")); + } else { + let mut arg = OsString::from("-bkeepfile:"); + let search_path = search_paths.get(self.sess); + arg.push(find_native_static_library(name, verbatim, search_path, self.sess)); + self.cmd.arg(arg); + } } - fn link_rlib(&mut self, lib: &Path) { + fn link_staticlib_by_path(&mut self, path: &Path, whole_archive: bool) { self.hint_static(); - self.cmd.arg(lib); + if !whole_archive { + self.cmd.arg(path); + } else { + let mut arg = OsString::from("-bkeepfile:"); + arg.push(path); + self.cmd.arg(arg); + } } fn include_path(&mut self, path: &Path) { @@ -1608,44 +1621,6 @@ impl<'a> Linker for AixLinker<'a> { fn no_relro(&mut self) {} - fn cmd(&mut self) -> &mut Command { - &mut self.cmd - } - - fn set_output_kind(&mut self, output_kind: LinkOutputKind, out_filename: &Path) { - match output_kind { - LinkOutputKind::DynamicDylib => { - self.hint_dynamic(); - self.build_dylib(out_filename); - } - LinkOutputKind::StaticDylib => { - self.hint_static(); - self.build_dylib(out_filename); - } - _ => {} - } - } - - fn link_rust_dylib(&mut self, lib: &str, _: &Path) { - self.hint_dynamic(); - self.cmd.arg(format!("-l{lib}")); - } - - fn link_framework(&mut self, _framework: &str, _as_needed: bool) { - bug!("frameworks not supported on AIX"); - } - - fn link_whole_staticlib(&mut self, lib: &str, verbatim: bool, search_path: &[PathBuf]) { - self.hint_static(); - let lib = find_native_static_library(lib, verbatim, search_path, self.sess); - self.cmd.arg(format!("-bkeepfile:{}", lib.to_str().unwrap())); - } - - fn link_whole_rlib(&mut self, lib: &Path) { - self.hint_static(); - self.cmd.arg(format!("-bkeepfile:{}", lib.to_str().unwrap())); - } - fn gc_sections(&mut self, _keep_metadata: bool) { self.cmd.arg("-bgc"); } @@ -1810,11 +1785,21 @@ impl<'a> Linker for PtxLinker<'a> { fn set_output_kind(&mut self, _output_kind: LinkOutputKind, _out_filename: &Path) {} - fn link_rlib(&mut self, path: &Path) { - self.cmd.arg("--rlib").arg(path); + fn link_dylib_by_name(&mut self, _name: &str, _verbatim: bool, _as_needed: bool) { + panic!("external dylibs not supported") + } + + fn link_staticlib_by_name( + &mut self, + _name: &str, + _verbatim: bool, + _whole_archive: bool, + _search_paths: &SearchPaths, + ) { + panic!("staticlibs not supported") } - fn link_whole_rlib(&mut self, path: &Path) { + fn link_staticlib_by_path(&mut self, path: &Path, _whole_archive: bool) { self.cmd.arg("--rlib").arg(path); } @@ -1844,30 +1829,10 @@ impl<'a> Linker for PtxLinker<'a> { self.cmd.arg("-o").arg(path); } - fn link_dylib(&mut self, _lib: &str, _verbatim: bool, _as_needed: bool) { - panic!("external dylibs not supported") - } - - fn link_rust_dylib(&mut self, _lib: &str, _path: &Path) { - panic!("external dylibs not supported") - } - - fn link_staticlib(&mut self, _lib: &str, _verbatim: bool) { - panic!("staticlibs not supported") - } - - fn link_whole_staticlib(&mut self, _lib: &str, _verbatim: bool, _search_path: &[PathBuf]) { - panic!("staticlibs not supported") - } - fn framework_path(&mut self, _path: &Path) { panic!("frameworks not supported") } - fn link_framework(&mut self, _framework: &str, _as_needed: bool) { - panic!("frameworks not supported") - } - fn full_relro(&mut self) {} fn partial_relro(&mut self) {} @@ -1907,11 +1872,21 @@ impl<'a> Linker for BpfLinker<'a> { fn set_output_kind(&mut self, _output_kind: LinkOutputKind, _out_filename: &Path) {} - fn link_rlib(&mut self, path: &Path) { - self.cmd.arg(path); + fn link_dylib_by_name(&mut self, _name: &str, _verbatim: bool, _as_needed: bool) { + panic!("external dylibs not supported") } - fn link_whole_rlib(&mut self, path: &Path) { + fn link_staticlib_by_name( + &mut self, + _name: &str, + _verbatim: bool, + _whole_archive: bool, + _search_paths: &SearchPaths, + ) { + panic!("staticlibs not supported") + } + + fn link_staticlib_by_path(&mut self, path: &Path, _whole_archive: bool) { self.cmd.arg(path); } @@ -1942,30 +1917,10 @@ impl<'a> Linker for BpfLinker<'a> { self.cmd.arg("-o").arg(path); } - fn link_dylib(&mut self, _lib: &str, _verbatim: bool, _as_needed: bool) { - panic!("external dylibs not supported") - } - - fn link_rust_dylib(&mut self, _lib: &str, _path: &Path) { - panic!("external dylibs not supported") - } - - fn link_staticlib(&mut self, _lib: &str, _verbatim: bool) { - panic!("staticlibs not supported") - } - - fn link_whole_staticlib(&mut self, _lib: &str, _verbatim: bool, _search_path: &[PathBuf]) { - panic!("staticlibs not supported") - } - fn framework_path(&mut self, _path: &Path) { panic!("frameworks not supported") } - fn link_framework(&mut self, _framework: &str, _as_needed: bool) { - panic!("frameworks not supported") - } - fn full_relro(&mut self) {} fn partial_relro(&mut self) {} diff --git a/compiler/rustc_middle/src/mir/mod.rs b/compiler/rustc_middle/src/mir/mod.rs index 36f5ba161d5..37c5bba46a7 100644 --- a/compiler/rustc_middle/src/mir/mod.rs +++ b/compiler/rustc_middle/src/mir/mod.rs @@ -244,18 +244,23 @@ impl<'tcx> MirSource<'tcx> { } } +/// Additional information carried by a MIR body when it is lowered from a coroutine. +/// This information is modified as it is lowered during the `StateTransform` MIR pass, +/// so not all fields will be active at a given time. For example, the `yield_ty` is +/// taken out of the field after yields are turned into returns, and the `coroutine_drop` +/// body is only populated after the state transform pass. #[derive(Clone, TyEncodable, TyDecodable, Debug, HashStable, TypeFoldable, TypeVisitable)] pub struct CoroutineInfo<'tcx> { - /// The yield type of the function, if it is a coroutine. + /// The yield type of the function. This field is removed after the state transform pass. pub yield_ty: Option<Ty<'tcx>>, - /// The resume type of the function, if it is a coroutine. + /// The resume type of the function. This field is removed after the state transform pass. pub resume_ty: Option<Ty<'tcx>>, - /// Coroutine drop glue. + /// Coroutine drop glue. This field is populated after the state transform pass. pub coroutine_drop: Option<Body<'tcx>>, - /// The layout of a coroutine. Produced by the state transformation. + /// The layout of a coroutine. This field is populated after the state transform pass. pub coroutine_layout: Option<CoroutineLayout<'tcx>>, /// If this is a coroutine then record the type of source expression that caused this coroutine @@ -303,6 +308,12 @@ pub struct Body<'tcx> { /// and used for debuginfo. Indexed by a `SourceScope`. pub source_scopes: IndexVec<SourceScope, SourceScopeData<'tcx>>, + /// Additional information carried by a MIR body when it is lowered from a coroutine. + /// + /// Note that the coroutine drop shim, any promoted consts, and other synthetic MIR + /// bodies that come from processing a coroutine body are not typically coroutines + /// themselves, and should probably set this to `None` to avoid carrying redundant + /// information. pub coroutine: Option<Box<CoroutineInfo<'tcx>>>, /// Declarations of locals. diff --git a/compiler/rustc_mir_transform/src/coroutine.rs b/compiler/rustc_mir_transform/src/coroutine.rs index 347f9b49efe..bde879f6067 100644 --- a/compiler/rustc_mir_transform/src/coroutine.rs +++ b/compiler/rustc_mir_transform/src/coroutine.rs @@ -1231,7 +1231,12 @@ fn create_coroutine_drop_shim<'tcx>( drop_clean: BasicBlock, ) -> Body<'tcx> { let mut body = body.clone(); - body.arg_count = 1; // make sure the resume argument is not included here + // Take the coroutine info out of the body, since the drop shim is + // not a coroutine body itself; it just has its drop built out of it. + let _ = body.coroutine.take(); + // Make sure the resume argument is not included here, since we're + // building a body for `drop_in_place`. + body.arg_count = 1; let source_info = SourceInfo::outermost(body.span); diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs index 4bdd9639557..b585e2082f1 100644 --- a/library/alloc/src/collections/btree/map.rs +++ b/library/alloc/src/collections/btree/map.rs @@ -1,6 +1,7 @@ use crate::vec::Vec; use core::borrow::Borrow; use core::cmp::Ordering; +use core::error::Error; use core::fmt::{self, Debug}; use core::hash::{Hash, Hasher}; use core::iter::FusedIterator; @@ -2521,14 +2522,10 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { self.len() == 0 } - /// Returns a [`Cursor`] pointing at the first element that is above the - /// given bound. + /// Returns a [`Cursor`] pointing to the first gap above the given bound. /// - /// If no such element exists then a cursor pointing at the "ghost" - /// non-element is returned. - /// - /// Passing [`Bound::Unbounded`] will return a cursor pointing at the first - /// element of the map. + /// Passing [`Bound::Unbounded`] will return a cursor pointing to the start + /// of the map. /// /// # Examples /// @@ -2542,14 +2539,16 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// a.insert(1, "a"); /// a.insert(2, "b"); /// a.insert(3, "c"); - /// a.insert(4, "c"); + /// a.insert(4, "d"); /// let cursor = a.lower_bound(Bound::Included(&2)); - /// assert_eq!(cursor.key(), Some(&2)); + /// assert_eq!(cursor.peek_prev(), Some((&1, &"a"))); + /// assert_eq!(cursor.peek_next(), Some((&2, &"b"))); /// let cursor = a.lower_bound(Bound::Excluded(&2)); - /// assert_eq!(cursor.key(), Some(&3)); + /// assert_eq!(cursor.peek_prev(), Some((&2, &"b"))); + /// assert_eq!(cursor.peek_next(), Some((&3, &"c"))); /// ``` #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> + pub fn lower_bound<Q: ?Sized>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord, @@ -2559,17 +2558,14 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { Some(root) => root.reborrow(), }; let edge = root_node.lower_bound(SearchBound::from_range(bound)); - Cursor { current: edge.next_kv().ok(), root: self.root.as_ref() } + Cursor { current: Some(edge), root: self.root.as_ref() } } - /// Returns a [`CursorMut`] pointing at the first element that is above the - /// given bound. + /// Returns a [`CursorMut`] pointing to the first gap above the given bound. /// - /// If no such element exists then a cursor pointing at the "ghost" - /// non-element is returned. /// - /// Passing [`Bound::Unbounded`] will return a cursor pointing at the first - /// element of the map. + /// Passing [`Bound::Unbounded`] will return a cursor pointing to the start + /// of the map. /// /// # Examples /// @@ -2583,14 +2579,16 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// a.insert(1, "a"); /// a.insert(2, "b"); /// a.insert(3, "c"); - /// a.insert(4, "c"); - /// let cursor = a.lower_bound_mut(Bound::Included(&2)); - /// assert_eq!(cursor.key(), Some(&2)); - /// let cursor = a.lower_bound_mut(Bound::Excluded(&2)); - /// assert_eq!(cursor.key(), Some(&3)); + /// a.insert(4, "d"); + /// let mut cursor = a.lower_bound_mut(Bound::Included(&2)); + /// assert_eq!(cursor.peek_prev(), Some((&1, &mut "a"))); + /// assert_eq!(cursor.peek_next(), Some((&2, &mut "b"))); + /// let mut cursor = a.lower_bound_mut(Bound::Excluded(&2)); + /// assert_eq!(cursor.peek_prev(), Some((&2, &mut "b"))); + /// assert_eq!(cursor.peek_next(), Some((&3, &mut "c"))); /// ``` #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn lower_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V, A> + pub fn lower_bound_mut<Q: ?Sized>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V, A> where K: Borrow<Q> + Ord, Q: Ord, @@ -2599,31 +2597,31 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { let root_node = match root.as_mut() { None => { return CursorMut { - current: None, - root: dormant_root, - length: &mut self.length, - alloc: &mut *self.alloc, + inner: CursorMutKey { + current: None, + root: dormant_root, + length: &mut self.length, + alloc: &mut *self.alloc, + }, }; } Some(root) => root.borrow_mut(), }; let edge = root_node.lower_bound(SearchBound::from_range(bound)); CursorMut { - current: edge.next_kv().ok(), - root: dormant_root, - length: &mut self.length, - alloc: &mut *self.alloc, + inner: CursorMutKey { + current: Some(edge), + root: dormant_root, + length: &mut self.length, + alloc: &mut *self.alloc, + }, } } - /// Returns a [`Cursor`] pointing at the last element that is below the - /// given bound. - /// - /// If no such element exists then a cursor pointing at the "ghost" - /// non-element is returned. + /// Returns a [`Cursor`] pointing at the last gap below the given bound. /// - /// Passing [`Bound::Unbounded`] will return a cursor pointing at the last - /// element of the map. + /// Passing [`Bound::Unbounded`] will return a cursor pointing to the end + /// of the map. /// /// # Examples /// @@ -2637,14 +2635,16 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// a.insert(1, "a"); /// a.insert(2, "b"); /// a.insert(3, "c"); - /// a.insert(4, "c"); + /// a.insert(4, "d"); /// let cursor = a.upper_bound(Bound::Included(&3)); - /// assert_eq!(cursor.key(), Some(&3)); + /// assert_eq!(cursor.peek_prev(), Some((&3, &"c"))); + /// assert_eq!(cursor.peek_next(), Some((&4, &"d"))); /// let cursor = a.upper_bound(Bound::Excluded(&3)); - /// assert_eq!(cursor.key(), Some(&2)); + /// assert_eq!(cursor.peek_prev(), Some((&2, &"b"))); + /// assert_eq!(cursor.peek_next(), Some((&3, &"c"))); /// ``` #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn upper_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> + pub fn upper_bound<Q: ?Sized>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord, @@ -2654,17 +2654,13 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { Some(root) => root.reborrow(), }; let edge = root_node.upper_bound(SearchBound::from_range(bound)); - Cursor { current: edge.next_back_kv().ok(), root: self.root.as_ref() } + Cursor { current: Some(edge), root: self.root.as_ref() } } - /// Returns a [`CursorMut`] pointing at the last element that is below the - /// given bound. - /// - /// If no such element exists then a cursor pointing at the "ghost" - /// non-element is returned. + /// Returns a [`CursorMut`] pointing at the last gap below the given bound. /// - /// Passing [`Bound::Unbounded`] will return a cursor pointing at the last - /// element of the map. + /// Passing [`Bound::Unbounded`] will return a cursor pointing to the end + /// of the map. /// /// # Examples /// @@ -2678,14 +2674,16 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// a.insert(1, "a"); /// a.insert(2, "b"); /// a.insert(3, "c"); - /// a.insert(4, "c"); - /// let cursor = a.upper_bound_mut(Bound::Included(&3)); - /// assert_eq!(cursor.key(), Some(&3)); - /// let cursor = a.upper_bound_mut(Bound::Excluded(&3)); - /// assert_eq!(cursor.key(), Some(&2)); + /// a.insert(4, "d"); + /// let mut cursor = a.upper_bound_mut(Bound::Included(&3)); + /// assert_eq!(cursor.peek_prev(), Some((&3, &mut "c"))); + /// assert_eq!(cursor.peek_next(), Some((&4, &mut "d"))); + /// let mut cursor = a.upper_bound_mut(Bound::Excluded(&3)); + /// assert_eq!(cursor.peek_prev(), Some((&2, &mut "b"))); + /// assert_eq!(cursor.peek_next(), Some((&3, &mut "c"))); /// ``` #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn upper_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V, A> + pub fn upper_bound_mut<Q: ?Sized>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V, A> where K: Borrow<Q> + Ord, Q: Ord, @@ -2694,20 +2692,24 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { let root_node = match root.as_mut() { None => { return CursorMut { - current: None, - root: dormant_root, - length: &mut self.length, - alloc: &mut *self.alloc, + inner: CursorMutKey { + current: None, + root: dormant_root, + length: &mut self.length, + alloc: &mut *self.alloc, + }, }; } Some(root) => root.borrow_mut(), }; let edge = root_node.upper_bound(SearchBound::from_range(bound)); CursorMut { - current: edge.next_back_kv().ok(), - root: dormant_root, - length: &mut self.length, - alloc: &mut *self.alloc, + inner: CursorMutKey { + current: Some(edge), + root: dormant_root, + length: &mut self.length, + alloc: &mut *self.alloc, + }, } } } @@ -2716,14 +2718,14 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// /// A `Cursor` is like an iterator, except that it can freely seek back-and-forth. /// -/// Cursors always point to an element in the tree, and index in a logically circular way. -/// To accommodate this, there is a "ghost" non-element that yields `None` between the last and -/// first elements of the tree. +/// Cursors always point to a gap between two elements in the map, and can +/// operate on the two immediately adjacent elements. /// /// A `Cursor` is created with the [`BTreeMap::lower_bound`] and [`BTreeMap::upper_bound`] methods. #[unstable(feature = "btree_cursors", issue = "107540")] pub struct Cursor<'a, K: 'a, V: 'a> { - current: Option<Handle<NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal>, marker::KV>>, + // If current is None then it means the tree has not been allocated yet. + current: Option<Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>>, root: Option<&'a node::Root<K, V>>, } @@ -2738,22 +2740,21 @@ impl<K, V> Clone for Cursor<'_, K, V> { #[unstable(feature = "btree_cursors", issue = "107540")] impl<K: Debug, V: Debug> Debug for Cursor<'_, K, V> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_tuple("Cursor").field(&self.key_value()).finish() + f.write_str("Cursor") } } /// A cursor over a `BTreeMap` with editing operations. /// /// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can -/// safely mutate the tree during iteration. This is because the lifetime of its yielded -/// references is tied to its own lifetime, instead of just the underlying tree. This means +/// safely mutate the map during iteration. This is because the lifetime of its yielded +/// references is tied to its own lifetime, instead of just the underlying map. This means /// cursors cannot yield multiple elements at once. /// -/// Cursors always point to an element in the tree, and index in a logically circular way. -/// To accommodate this, there is a "ghost" non-element that yields `None` between the last and -/// first elements of the tree. +/// Cursors always point to a gap between two elements in the map, and can +/// operate on the two immediately adjacent elements. /// -/// A `Cursor` is created with the [`BTreeMap::lower_bound_mut`] and [`BTreeMap::upper_bound_mut`] +/// A `CursorMut` is created with the [`BTreeMap::lower_bound_mut`] and [`BTreeMap::upper_bound_mut`] /// methods. #[unstable(feature = "btree_cursors", issue = "107540")] pub struct CursorMut< @@ -2762,287 +2763,271 @@ pub struct CursorMut< V: 'a, #[unstable(feature = "allocator_api", issue = "32838")] A = Global, > { - current: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV>>, + inner: CursorMutKey<'a, K, V, A>, +} + +#[unstable(feature = "btree_cursors", issue = "107540")] +impl<K: Debug, V: Debug, A> Debug for CursorMut<'_, K, V, A> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.write_str("CursorMut") + } +} + +/// A cursor over a `BTreeMap` with editing operations, and which allows +/// mutating the key of elements. +/// +/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can +/// safely mutate the map during iteration. This is because the lifetime of its yielded +/// references is tied to its own lifetime, instead of just the underlying map. This means +/// cursors cannot yield multiple elements at once. +/// +/// Cursors always point to a gap between two elements in the map, and can +/// operate on the two immediately adjacent elements. +/// +/// A `CursorMutKey` is created from a [`CursorMut`] with the +/// [`CursorMut::with_mutable_key`] method. +/// +/// # Safety +/// +/// Since this cursor allows mutating keys, you must ensure that the `BTreeMap` +/// invariants are maintained. Specifically: +/// +/// * The key of the newly inserted element must be unique in the tree. +/// * All keys in the tree must remain in sorted order. +#[unstable(feature = "btree_cursors", issue = "107540")] +pub struct CursorMutKey< + 'a, + K: 'a, + V: 'a, + #[unstable(feature = "allocator_api", issue = "32838")] A = Global, +> { + // If current is None then it means the tree has not been allocated yet. + current: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>>, root: DormantMutRef<'a, Option<node::Root<K, V>>>, length: &'a mut usize, alloc: &'a mut A, } #[unstable(feature = "btree_cursors", issue = "107540")] -impl<K: Debug, V: Debug, A> Debug for CursorMut<'_, K, V, A> { +impl<K: Debug, V: Debug, A> Debug for CursorMutKey<'_, K, V, A> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_tuple("CursorMut").field(&self.key_value()).finish() + f.write_str("CursorMutKey") } } impl<'a, K, V> Cursor<'a, K, V> { - /// Moves the cursor to the next element of the `BTreeMap`. + /// Advances the cursor to the next gap, returning the key and value of the + /// element that it moved over. /// - /// If the cursor is pointing to the "ghost" non-element then this will move it to - /// the first element of the `BTreeMap`. If it is pointing to the last - /// element of the `BTreeMap` then this will move it to the "ghost" non-element. + /// If the cursor is already at the end of the map then `None` is returned + /// and the cursor is not moved. #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn move_next(&mut self) { - match self.current.take() { - None => { - self.current = self.root.and_then(|root| { - root.reborrow().first_leaf_edge().forget_node_type().right_kv().ok() - }); + pub fn next(&mut self) -> Option<(&'a K, &'a V)> { + let current = self.current.take()?; + match current.next_kv() { + Ok(kv) => { + let result = kv.into_kv(); + self.current = Some(kv.next_leaf_edge()); + Some(result) } - Some(current) => { - self.current = current.next_leaf_edge().next_kv().ok(); + Err(root) => { + self.current = Some(root.last_leaf_edge()); + None } } } - /// Moves the cursor to the previous element of the `BTreeMap`. + /// Advances the cursor to the previous gap, returning the key and value of + /// the element that it moved over. /// - /// If the cursor is pointing to the "ghost" non-element then this will move it to - /// the last element of the `BTreeMap`. If it is pointing to the first - /// element of the `BTreeMap` then this will move it to the "ghost" non-element. + /// If the cursor is already at the start of the map then `None` is returned + /// and the cursor is not moved. #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn move_prev(&mut self) { - match self.current.take() { - None => { - self.current = self.root.and_then(|root| { - root.reborrow().last_leaf_edge().forget_node_type().left_kv().ok() - }); + pub fn prev(&mut self) -> Option<(&'a K, &'a V)> { + let current = self.current.take()?; + match current.next_back_kv() { + Ok(kv) => { + let result = kv.into_kv(); + self.current = Some(kv.next_back_leaf_edge()); + Some(result) } - Some(current) => { - self.current = current.next_back_leaf_edge().next_back_kv().ok(); + Err(root) => { + self.current = Some(root.first_leaf_edge()); + None } } } - /// Returns a reference to the key of the element that the cursor is - /// currently pointing to. - /// - /// This returns `None` if the cursor is currently pointing to the - /// "ghost" non-element. - #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn key(&self) -> Option<&'a K> { - self.current.as_ref().map(|current| current.into_kv().0) - } - - /// Returns a reference to the value of the element that the cursor is - /// currently pointing to. - /// - /// This returns `None` if the cursor is currently pointing to the - /// "ghost" non-element. - #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn value(&self) -> Option<&'a V> { - self.current.as_ref().map(|current| current.into_kv().1) - } - - /// Returns a reference to the key and value of the element that the cursor - /// is currently pointing to. - /// - /// This returns `None` if the cursor is currently pointing to the - /// "ghost" non-element. - #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn key_value(&self) -> Option<(&'a K, &'a V)> { - self.current.as_ref().map(|current| current.into_kv()) - } - - /// Returns a reference to the next element. + /// Returns a reference to the the key and value of the next element without + /// moving the cursor. /// - /// If the cursor is pointing to the "ghost" non-element then this returns - /// the first element of the `BTreeMap`. If it is pointing to the last - /// element of the `BTreeMap` then this returns `None`. + /// If the cursor is at the end of the map then `None` is returned #[unstable(feature = "btree_cursors", issue = "107540")] pub fn peek_next(&self) -> Option<(&'a K, &'a V)> { - let mut next = self.clone(); - next.move_next(); - next.current.as_ref().map(|current| current.into_kv()) + self.clone().next() } - /// Returns a reference to the previous element. + /// Returns a reference to the the key and value of the previous element + /// without moving the cursor. /// - /// If the cursor is pointing to the "ghost" non-element then this returns - /// the last element of the `BTreeMap`. If it is pointing to the first - /// element of the `BTreeMap` then this returns `None`. + /// If the cursor is at the start of the map then `None` is returned. #[unstable(feature = "btree_cursors", issue = "107540")] pub fn peek_prev(&self) -> Option<(&'a K, &'a V)> { - let mut prev = self.clone(); - prev.move_prev(); - prev.current.as_ref().map(|current| current.into_kv()) + self.clone().prev() } } impl<'a, K, V, A> CursorMut<'a, K, V, A> { - /// Moves the cursor to the next element of the `BTreeMap`. + /// Advances the cursor to the next gap, returning the key and value of the + /// element that it moved over. /// - /// If the cursor is pointing to the "ghost" non-element then this will move it to - /// the first element of the `BTreeMap`. If it is pointing to the last - /// element of the `BTreeMap` then this will move it to the "ghost" non-element. + /// If the cursor is already at the end of the map then `None` is returned + /// and the cursor is not moved. #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn move_next(&mut self) { - match self.current.take() { - None => { - // SAFETY: The previous borrow of root has ended. - self.current = unsafe { self.root.reborrow() }.as_mut().and_then(|root| { - root.borrow_mut().first_leaf_edge().forget_node_type().right_kv().ok() - }); - } - Some(current) => { - self.current = current.next_leaf_edge().next_kv().ok(); - } - } + pub fn next(&mut self) -> Option<(&K, &mut V)> { + let (k, v) = self.inner.next()?; + Some((&*k, v)) } - /// Moves the cursor to the previous element of the `BTreeMap`. + /// Advances the cursor to the previous gap, returning the key and value of + /// the element that it moved over. /// - /// If the cursor is pointing to the "ghost" non-element then this will move it to - /// the last element of the `BTreeMap`. If it is pointing to the first - /// element of the `BTreeMap` then this will move it to the "ghost" non-element. + /// If the cursor is already at the start of the map then `None` is returned + /// and the cursor is not moved. #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn move_prev(&mut self) { - match self.current.take() { - None => { - // SAFETY: The previous borrow of root has ended. - self.current = unsafe { self.root.reborrow() }.as_mut().and_then(|root| { - root.borrow_mut().last_leaf_edge().forget_node_type().left_kv().ok() - }); - } - Some(current) => { - self.current = current.next_back_leaf_edge().next_back_kv().ok(); - } - } + pub fn prev(&mut self) -> Option<(&K, &mut V)> { + let (k, v) = self.inner.prev()?; + Some((&*k, v)) } - /// Returns a reference to the key of the element that the cursor is - /// currently pointing to. + /// Returns a reference to the the key and value of the next element without + /// moving the cursor. /// - /// This returns `None` if the cursor is currently pointing to the - /// "ghost" non-element. + /// If the cursor is at the end of the map then `None` is returned #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn key(&self) -> Option<&K> { - self.current.as_ref().map(|current| current.reborrow().into_kv().0) + pub fn peek_next(&mut self) -> Option<(&K, &mut V)> { + let (k, v) = self.inner.peek_next()?; + Some((&*k, v)) } - /// Returns a reference to the value of the element that the cursor is - /// currently pointing to. + /// Returns a reference to the the key and value of the previous element + /// without moving the cursor. /// - /// This returns `None` if the cursor is currently pointing to the - /// "ghost" non-element. + /// If the cursor is at the start of the map then `None` is returned. #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn value(&self) -> Option<&V> { - self.current.as_ref().map(|current| current.reborrow().into_kv().1) + pub fn peek_prev(&mut self) -> Option<(&K, &mut V)> { + let (k, v) = self.inner.peek_prev()?; + Some((&*k, v)) } - /// Returns a reference to the key and value of the element that the cursor - /// is currently pointing to. + /// Returns a read-only cursor pointing to the same location as the + /// `CursorMut`. /// - /// This returns `None` if the cursor is currently pointing to the - /// "ghost" non-element. + /// The lifetime of the returned `Cursor` is bound to that of the + /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the + /// `CursorMut` is frozen for the lifetime of the `Cursor`. #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn key_value(&self) -> Option<(&K, &V)> { - self.current.as_ref().map(|current| current.reborrow().into_kv()) + pub fn as_cursor(&self) -> Cursor<'_, K, V> { + self.inner.as_cursor() } - /// Returns a mutable reference to the value of the element that the cursor - /// is currently pointing to. + /// Converts the cursor into a [`CursorMutKey`], which allows mutating + /// the key of elements in the tree. + /// + /// # Safety + /// + /// Since this cursor allows mutating keys, you must ensure that the `BTreeMap` + /// invariants are maintained. Specifically: /// - /// This returns `None` if the cursor is currently pointing to the - /// "ghost" non-element. + /// * The key of the newly inserted element must be unique in the tree. + /// * All keys in the tree must remain in sorted order. #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn value_mut(&mut self) -> Option<&mut V> { - self.current.as_mut().map(|current| current.kv_mut().1) + pub unsafe fn with_mutable_key(self) -> CursorMutKey<'a, K, V, A> { + self.inner } +} - /// Returns a reference to the key and mutable reference to the value of the - /// element that the cursor is currently pointing to. +impl<'a, K, V, A> CursorMutKey<'a, K, V, A> { + /// Advances the cursor to the next gap, returning the key and value of the + /// element that it moved over. /// - /// This returns `None` if the cursor is currently pointing to the - /// "ghost" non-element. + /// If the cursor is already at the end of the map then `None` is returned + /// and the cursor is not moved. #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn key_value_mut(&mut self) -> Option<(&K, &mut V)> { - self.current.as_mut().map(|current| { - let (k, v) = current.kv_mut(); - (&*k, v) - }) + pub fn next(&mut self) -> Option<(&mut K, &mut V)> { + let current = self.current.take()?; + match current.next_kv() { + Ok(mut kv) => { + // SAFETY: The key/value pointers remain valid even after the + // cursor is moved forward. The lifetimes then prevent any + // further access to the cursor. + let (k, v) = unsafe { kv.reborrow_mut().into_kv_mut() }; + let (k, v) = (k as *mut _, v as *mut _); + self.current = Some(kv.next_leaf_edge()); + Some(unsafe { (&mut *k, &mut *v) }) + } + Err(root) => { + self.current = Some(root.last_leaf_edge()); + None + } + } } - /// Returns a mutable reference to the key of the element that the cursor is - /// currently pointing to. - /// - /// This returns `None` if the cursor is currently pointing to the - /// "ghost" non-element. + /// Advances the cursor to the previous gap, returning the key and value of + /// the element that it moved over. /// - /// # Safety - /// - /// This can be used to modify the key, but you must ensure that the - /// `BTreeMap` invariants are maintained. Specifically: - /// - /// * The key must remain unique within the tree. - /// * The key must remain in sorted order with regards to other elements in - /// the tree. + /// If the cursor is already at the start of the map then `None` is returned + /// and the cursor is not moved. #[unstable(feature = "btree_cursors", issue = "107540")] - pub unsafe fn key_mut_unchecked(&mut self) -> Option<&mut K> { - self.current.as_mut().map(|current| current.kv_mut().0) + pub fn prev(&mut self) -> Option<(&mut K, &mut V)> { + let current = self.current.take()?; + match current.next_back_kv() { + Ok(mut kv) => { + // SAFETY: The key/value pointers remain valid even after the + // cursor is moved forward. The lifetimes then prevent any + // further access to the cursor. + let (k, v) = unsafe { kv.reborrow_mut().into_kv_mut() }; + let (k, v) = (k as *mut _, v as *mut _); + self.current = Some(kv.next_back_leaf_edge()); + Some(unsafe { (&mut *k, &mut *v) }) + } + Err(root) => { + self.current = Some(root.first_leaf_edge()); + None + } + } } - /// Returns a reference to the key and value of the next element. + /// Returns a reference to the the key and value of the next element without + /// moving the cursor. /// - /// If the cursor is pointing to the "ghost" non-element then this returns - /// the first element of the `BTreeMap`. If it is pointing to the last - /// element of the `BTreeMap` then this returns `None`. + /// If the cursor is at the end of the map then `None` is returned #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn peek_next(&mut self) -> Option<(&K, &mut V)> { - let (k, v) = match self.current { - None => { - // SAFETY: The previous borrow of root has ended. - unsafe { self.root.reborrow() } - .as_mut()? - .borrow_mut() - .first_leaf_edge() - .next_kv() - .ok()? - .into_kv_valmut() - } - // SAFETY: We're not using this to mutate the tree. - Some(ref mut current) => { - unsafe { current.reborrow_mut() }.next_leaf_edge().next_kv().ok()?.into_kv_valmut() - } - }; - Some((k, v)) + pub fn peek_next(&mut self) -> Option<(&mut K, &mut V)> { + let current = self.current.as_mut()?; + // SAFETY: We're not using this to mutate the tree. + let kv = unsafe { current.reborrow_mut() }.next_kv().ok()?.into_kv_mut(); + Some(kv) } - /// Returns a reference to the key and value of the previous element. + /// Returns a reference to the the key and value of the previous element + /// without moving the cursor. /// - /// If the cursor is pointing to the "ghost" non-element then this returns - /// the last element of the `BTreeMap`. If it is pointing to the first - /// element of the `BTreeMap` then this returns `None`. + /// If the cursor is at the start of the map then `None` is returned. #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn peek_prev(&mut self) -> Option<(&K, &mut V)> { - let (k, v) = match self.current.as_mut() { - None => { - // SAFETY: The previous borrow of root has ended. - unsafe { self.root.reborrow() } - .as_mut()? - .borrow_mut() - .last_leaf_edge() - .next_back_kv() - .ok()? - .into_kv_valmut() - } - Some(current) => { - // SAFETY: We're not using this to mutate the tree. - unsafe { current.reborrow_mut() } - .next_back_leaf_edge() - .next_back_kv() - .ok()? - .into_kv_valmut() - } - }; - Some((k, v)) + pub fn peek_prev(&mut self) -> Option<(&mut K, &mut V)> { + let current = self.current.as_mut()?; + // SAFETY: We're not using this to mutate the tree. + let kv = unsafe { current.reborrow_mut() }.next_back_kv().ok()?.into_kv_mut(); + Some(kv) } - /// Returns a read-only cursor pointing to the current element. + /// Returns a read-only cursor pointing to the same location as the + /// `CursorMutKey`. /// /// The lifetime of the returned `Cursor` is bound to that of the - /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the - /// `CursorMut` is frozen for the lifetime of the `Cursor`. + /// `CursorMutKey`, which means it cannot outlive the `CursorMutKey` and that the + /// `CursorMutKey` is frozen for the lifetime of the `Cursor`. #[unstable(feature = "btree_cursors", issue = "107540")] pub fn as_cursor(&self) -> Cursor<'_, K, V> { Cursor { @@ -3054,11 +3039,12 @@ impl<'a, K, V, A> CursorMut<'a, K, V, A> { } // Now the tree editing operations -impl<'a, K: Ord, V, A: Allocator + Clone> CursorMut<'a, K, V, A> { - /// Inserts a new element into the `BTreeMap` after the current one. +impl<'a, K: Ord, V, A: Allocator + Clone> CursorMutKey<'a, K, V, A> { + /// Inserts a new element into the `BTreeMap` in the gap that the + /// `CursorMutKey` is currently pointing to. /// - /// If the cursor is pointing at the "ghost" non-element then the new element is - /// inserted at the front of the `BTreeMap`. + /// After the insertion the cursor will be pointing at the gap before the + /// newly inserted element. /// /// # Safety /// @@ -3071,20 +3057,19 @@ impl<'a, K: Ord, V, A: Allocator + Clone> CursorMut<'a, K, V, A> { pub unsafe fn insert_after_unchecked(&mut self, key: K, value: V) { let edge = match self.current.take() { None => { + // Tree is empty, allocate a new root. // SAFETY: We have no other reference to the tree. - match unsafe { self.root.reborrow() } { - root @ None => { - // Tree is empty, allocate a new root. - let mut node = NodeRef::new_leaf(self.alloc.clone()); - node.borrow_mut().push(key, value); - *root = Some(node.forget_type()); - *self.length += 1; - return; - } - Some(root) => root.borrow_mut().first_leaf_edge(), - } + let root = unsafe { self.root.reborrow() }; + debug_assert!(root.is_none()); + let mut node = NodeRef::new_leaf(self.alloc.clone()); + // SAFETY: We don't touch the root while the handle is alive. + let handle = unsafe { node.borrow_mut().push_with_handle(key, value) }; + *root = Some(node.forget_type()); + *self.length += 1; + self.current = Some(handle.left_edge()); + return; } - Some(current) => current.next_leaf_edge(), + Some(current) => current, }; let handle = edge.insert_recursing(key, value, self.alloc.clone(), |ins| { @@ -3094,14 +3079,15 @@ impl<'a, K: Ord, V, A: Allocator + Clone> CursorMut<'a, K, V, A> { let root = unsafe { self.root.reborrow().as_mut().unwrap() }; root.push_internal_level(self.alloc.clone()).push(ins.kv.0, ins.kv.1, ins.right) }); - self.current = handle.left_edge().next_back_kv().ok(); + self.current = Some(handle.left_edge()); *self.length += 1; } - /// Inserts a new element into the `BTreeMap` before the current one. + /// Inserts a new element into the `BTreeMap` in the gap that the + /// `CursorMutKey` is currently pointing to. /// - /// If the cursor is pointing at the "ghost" non-element then the new element is - /// inserted at the end of the `BTreeMap`. + /// After the insertion the cursor will be pointing at the gap after the + /// newly inserted element. /// /// # Safety /// @@ -3119,15 +3105,17 @@ impl<'a, K: Ord, V, A: Allocator + Clone> CursorMut<'a, K, V, A> { root @ None => { // Tree is empty, allocate a new root. let mut node = NodeRef::new_leaf(self.alloc.clone()); - node.borrow_mut().push(key, value); + // SAFETY: We don't touch the root while the handle is alive. + let handle = unsafe { node.borrow_mut().push_with_handle(key, value) }; *root = Some(node.forget_type()); *self.length += 1; + self.current = Some(handle.right_edge()); return; } Some(root) => root.borrow_mut().last_leaf_edge(), } } - Some(current) => current.next_back_leaf_edge(), + Some(current) => current, }; let handle = edge.insert_recursing(key, value, self.alloc.clone(), |ins| { @@ -3137,14 +3125,15 @@ impl<'a, K: Ord, V, A: Allocator + Clone> CursorMut<'a, K, V, A> { let root = unsafe { self.root.reborrow().as_mut().unwrap() }; root.push_internal_level(self.alloc.clone()).push(ins.kv.0, ins.kv.1, ins.right) }); - self.current = handle.right_edge().next_kv().ok(); + self.current = Some(handle.right_edge()); *self.length += 1; } - /// Inserts a new element into the `BTreeMap` after the current one. + /// Inserts a new element into the `BTreeMap` in the gap that the + /// `CursorMutKey` is currently pointing to. /// - /// If the cursor is pointing at the "ghost" non-element then the new element is - /// inserted at the front of the `BTreeMap`. + /// After the insertion the cursor will be pointing at the gap before the + /// newly inserted element. /// /// # Panics /// @@ -3154,26 +3143,28 @@ impl<'a, K: Ord, V, A: Allocator + Clone> CursorMut<'a, K, V, A> { /// - the given key compares greater than or equal to the next element (if /// any). #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn insert_after(&mut self, key: K, value: V) { - if let Some(current) = self.key() { - if &key <= current { - panic!("key must be ordered above the current element"); + pub fn insert_after(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError> { + if let Some((prev, _)) = self.peek_prev() { + if &key <= prev { + return Err(UnorderedKeyError {}); } } if let Some((next, _)) = self.peek_next() { if &key >= next { - panic!("key must be ordered below the next element"); + return Err(UnorderedKeyError {}); } } unsafe { self.insert_after_unchecked(key, value); } + Ok(()) } - /// Inserts a new element into the `BTreeMap` before the current one. + /// Inserts a new element into the `BTreeMap` in the gap that the + /// `CursorMutKey` is currently pointing to. /// - /// If the cursor is pointing at the "ghost" non-element then the new element is - /// inserted at the end of the `BTreeMap`. + /// After the insertion the cursor will be pointing at the gap after the + /// newly inserted element. /// /// # Panics /// @@ -3183,36 +3174,36 @@ impl<'a, K: Ord, V, A: Allocator + Clone> CursorMut<'a, K, V, A> { /// - the given key compares less than or equal to the previous element (if /// any). #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn insert_before(&mut self, key: K, value: V) { - if let Some(current) = self.key() { - if &key >= current { - panic!("key must be ordered below the current element"); - } - } + pub fn insert_before(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError> { if let Some((prev, _)) = self.peek_prev() { if &key <= prev { - panic!("key must be ordered above the previous element"); + return Err(UnorderedKeyError {}); + } + } + if let Some((next, _)) = self.peek_next() { + if &key >= next { + return Err(UnorderedKeyError {}); } } unsafe { self.insert_before_unchecked(key, value); } + Ok(()) } - /// Removes the current element from the `BTreeMap`. - /// - /// The element that was removed is returned, and the cursor is - /// moved to point to the next element in the `BTreeMap`. + /// Removes the next element from the `BTreeMap`. /// - /// If the cursor is currently pointing to the "ghost" non-element then no element - /// is removed and `None` is returned. The cursor is not moved in this case. + /// The element that was removed is returned. The cursor position is + /// unchanged (before the removed element). #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn remove_current(&mut self) -> Option<(K, V)> { + pub fn remove_next(&mut self) -> Option<(K, V)> { let current = self.current.take()?; let mut emptied_internal_root = false; - let (kv, pos) = - current.remove_kv_tracking(|| emptied_internal_root = true, self.alloc.clone()); - self.current = pos.next_kv().ok(); + let (kv, pos) = current + .next_kv() + .ok()? + .remove_kv_tracking(|| emptied_internal_root = true, self.alloc.clone()); + self.current = Some(pos); *self.length -= 1; if emptied_internal_root { // SAFETY: This is safe since current does not point within the now @@ -3223,20 +3214,19 @@ impl<'a, K: Ord, V, A: Allocator + Clone> CursorMut<'a, K, V, A> { Some(kv) } - /// Removes the current element from the `BTreeMap`. + /// Removes the precending element from the `BTreeMap`. /// - /// The element that was removed is returned, and the cursor is - /// moved to point to the previous element in the `BTreeMap`. - /// - /// If the cursor is currently pointing to the "ghost" non-element then no element - /// is removed and `None` is returned. The cursor is not moved in this case. + /// The element that was removed is returned. The cursor position is + /// unchanged (after the removed element). #[unstable(feature = "btree_cursors", issue = "107540")] - pub fn remove_current_and_move_back(&mut self) -> Option<(K, V)> { + pub fn remove_prev(&mut self) -> Option<(K, V)> { let current = self.current.take()?; let mut emptied_internal_root = false; - let (kv, pos) = - current.remove_kv_tracking(|| emptied_internal_root = true, self.alloc.clone()); - self.current = pos.next_back_kv().ok(); + let (kv, pos) = current + .next_back_kv() + .ok()? + .remove_kv_tracking(|| emptied_internal_root = true, self.alloc.clone()); + self.current = Some(pos); *self.length -= 1; if emptied_internal_root { // SAFETY: This is safe since current does not point within the now @@ -3248,5 +3238,114 @@ impl<'a, K: Ord, V, A: Allocator + Clone> CursorMut<'a, K, V, A> { } } +impl<'a, K: Ord, V, A: Allocator + Clone> CursorMut<'a, K, V, A> { + /// Inserts a new element into the `BTreeMap` in the gap that the + /// `CursorMut` is currently pointing to. + /// + /// After the insertion the cursor will be pointing at the gap before the + /// newly inserted element. + /// + /// # Safety + /// + /// You must ensure that the `BTreeMap` invariants are maintained. + /// Specifically: + /// + /// * The key of the newly inserted element must be unique in the tree. + /// * All keys in the tree must remain in sorted order. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub unsafe fn insert_after_unchecked(&mut self, key: K, value: V) { + unsafe { self.inner.insert_after_unchecked(key, value) } + } + + /// Inserts a new element into the `BTreeMap` in the gap that the + /// `CursorMut` is currently pointing to. + /// + /// After the insertion the cursor will be pointing at the gap after the + /// newly inserted element. + /// + /// # Safety + /// + /// You must ensure that the `BTreeMap` invariants are maintained. + /// Specifically: + /// + /// * The key of the newly inserted element must be unique in the tree. + /// * All keys in the tree must remain in sorted order. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub unsafe fn insert_before_unchecked(&mut self, key: K, value: V) { + unsafe { self.inner.insert_before_unchecked(key, value) } + } + + /// Inserts a new element into the `BTreeMap` in the gap that the + /// `CursorMut` is currently pointing to. + /// + /// After the insertion the cursor will be pointing at the gap before the + /// newly inserted element. + /// + /// # Panics + /// + /// This function panics if: + /// - the given key compares less than or equal to the current element (if + /// any). + /// - the given key compares greater than or equal to the next element (if + /// any). + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn insert_after(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError> { + self.inner.insert_after(key, value) + } + + /// Inserts a new element into the `BTreeMap` in the gap that the + /// `CursorMut` is currently pointing to. + /// + /// After the insertion the cursor will be pointing at the gap after the + /// newly inserted element. + /// + /// # Panics + /// + /// This function panics if: + /// - the given key compares greater than or equal to the current element + /// (if any). + /// - the given key compares less than or equal to the previous element (if + /// any). + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn insert_before(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError> { + self.inner.insert_before(key, value) + } + + /// Removes the next element from the `BTreeMap`. + /// + /// The element that was removed is returned. The cursor position is + /// unchanged (before the removed element). + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn remove_next(&mut self) -> Option<(K, V)> { + self.inner.remove_next() + } + + /// Removes the precending element from the `BTreeMap`. + /// + /// The element that was removed is returned. The cursor position is + /// unchanged (after the removed element). + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn remove_prev(&mut self) -> Option<(K, V)> { + self.inner.remove_prev() + } +} + +/// Error type returned by [`CursorMut::insert_before`] and +/// [`CursorMut::insert_after`] if the key being inserted is not properly +/// ordered with regards to adjacent keys. +#[derive(Clone, PartialEq, Eq, Debug)] +#[unstable(feature = "btree_cursors", issue = "107540")] +pub struct UnorderedKeyError {} + +#[unstable(feature = "btree_cursors", issue = "107540")] +impl fmt::Display for UnorderedKeyError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "key is not properly ordered relative to neighbors") + } +} + +#[unstable(feature = "btree_cursors", issue = "107540")] +impl Error for UnorderedKeyError {} + #[cfg(test)] mod tests; diff --git a/library/alloc/src/collections/btree/map/tests.rs b/library/alloc/src/collections/btree/map/tests.rs index a1b7cfe6b17..56620cf890d 100644 --- a/library/alloc/src/collections/btree/map/tests.rs +++ b/library/alloc/src/collections/btree/map/tests.rs @@ -2349,112 +2349,151 @@ fn test_cursor() { let map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); let mut cur = map.lower_bound(Bound::Unbounded); - assert_eq!(cur.key(), Some(&1)); - cur.move_next(); - assert_eq!(cur.key(), Some(&2)); - assert_eq!(cur.peek_next(), Some((&3, &'c'))); - cur.move_prev(); - assert_eq!(cur.key(), Some(&1)); + assert_eq!(cur.peek_next(), Some((&1, &'a'))); assert_eq!(cur.peek_prev(), None); + assert_eq!(cur.prev(), None); + assert_eq!(cur.next(), Some((&1, &'a'))); + + assert_eq!(cur.next(), Some((&2, &'b'))); + + assert_eq!(cur.peek_next(), Some((&3, &'c'))); + assert_eq!(cur.prev(), Some((&2, &'b'))); + assert_eq!(cur.peek_prev(), Some((&1, &'a'))); let mut cur = map.upper_bound(Bound::Excluded(&1)); - assert_eq!(cur.key(), None); - cur.move_next(); - assert_eq!(cur.key(), Some(&1)); - cur.move_prev(); - assert_eq!(cur.key(), None); - assert_eq!(cur.peek_prev(), Some((&3, &'c'))); + assert_eq!(cur.peek_prev(), None); + assert_eq!(cur.next(), Some((&1, &'a'))); + assert_eq!(cur.prev(), Some((&1, &'a'))); } #[test] fn test_cursor_mut() { let mut map = BTreeMap::from([(1, 'a'), (3, 'c'), (5, 'e')]); let mut cur = map.lower_bound_mut(Bound::Excluded(&3)); - assert_eq!(cur.key(), Some(&5)); - cur.insert_before(4, 'd'); - assert_eq!(cur.key(), Some(&5)); + assert_eq!(cur.peek_next(), Some((&5, &mut 'e'))); + assert_eq!(cur.peek_prev(), Some((&3, &mut 'c'))); + + cur.insert_before(4, 'd').unwrap(); + assert_eq!(cur.peek_next(), Some((&5, &mut 'e'))); assert_eq!(cur.peek_prev(), Some((&4, &mut 'd'))); - cur.move_next(); - assert_eq!(cur.key(), None); - cur.insert_before(6, 'f'); - assert_eq!(cur.key(), None); - assert_eq!(cur.remove_current(), None); - assert_eq!(cur.key(), None); - cur.insert_after(0, '?'); - assert_eq!(cur.key(), None); - assert_eq!(map, BTreeMap::from([(0, '?'), (1, 'a'), (3, 'c'), (4, 'd'), (5, 'e'), (6, 'f')])); + + assert_eq!(cur.next(), Some((&5, &mut 'e'))); + assert_eq!(cur.peek_next(), None); + assert_eq!(cur.peek_prev(), Some((&5, &mut 'e'))); + cur.insert_before(6, 'f').unwrap(); + assert_eq!(cur.peek_next(), None); + assert_eq!(cur.peek_prev(), Some((&6, &mut 'f'))); + assert_eq!(cur.remove_prev(), Some((6, 'f'))); + assert_eq!(cur.remove_prev(), Some((5, 'e'))); + assert_eq!(cur.remove_next(), None); + assert_eq!(map, BTreeMap::from([(1, 'a'), (3, 'c'), (4, 'd')])); let mut cur = map.upper_bound_mut(Bound::Included(&5)); - assert_eq!(cur.key(), Some(&5)); - assert_eq!(cur.remove_current(), Some((5, 'e'))); - assert_eq!(cur.key(), Some(&6)); - assert_eq!(cur.remove_current_and_move_back(), Some((6, 'f'))); - assert_eq!(cur.key(), Some(&4)); - assert_eq!(map, BTreeMap::from([(0, '?'), (1, 'a'), (3, 'c'), (4, 'd')])); + assert_eq!(cur.peek_next(), None); + assert_eq!(cur.prev(), Some((&4, &mut 'd'))); + assert_eq!(cur.peek_next(), Some((&4, &mut 'd'))); + assert_eq!(cur.peek_prev(), Some((&3, &mut 'c'))); + assert_eq!(cur.remove_next(), Some((4, 'd'))); + assert_eq!(map, BTreeMap::from([(1, 'a'), (3, 'c')])); +} + +#[test] +fn test_cursor_mut_key() { + let mut map = BTreeMap::from([(1, 'a'), (3, 'c'), (5, 'e')]); + let mut cur = unsafe { map.lower_bound_mut(Bound::Excluded(&3)).with_mutable_key() }; + assert_eq!(cur.peek_next(), Some((&mut 5, &mut 'e'))); + assert_eq!(cur.peek_prev(), Some((&mut 3, &mut 'c'))); + + cur.insert_before(4, 'd').unwrap(); + assert_eq!(cur.peek_next(), Some((&mut 5, &mut 'e'))); + assert_eq!(cur.peek_prev(), Some((&mut 4, &mut 'd'))); + + assert_eq!(cur.next(), Some((&mut 5, &mut 'e'))); + assert_eq!(cur.peek_next(), None); + assert_eq!(cur.peek_prev(), Some((&mut 5, &mut 'e'))); + cur.insert_before(6, 'f').unwrap(); + assert_eq!(cur.peek_next(), None); + assert_eq!(cur.peek_prev(), Some((&mut 6, &mut 'f'))); + assert_eq!(cur.remove_prev(), Some((6, 'f'))); + assert_eq!(cur.remove_prev(), Some((5, 'e'))); + assert_eq!(cur.remove_next(), None); + assert_eq!(map, BTreeMap::from([(1, 'a'), (3, 'c'), (4, 'd')])); + + let mut cur = unsafe { map.upper_bound_mut(Bound::Included(&5)).with_mutable_key() }; + assert_eq!(cur.peek_next(), None); + assert_eq!(cur.prev(), Some((&mut 4, &mut 'd'))); + assert_eq!(cur.peek_next(), Some((&mut 4, &mut 'd'))); + assert_eq!(cur.peek_prev(), Some((&mut 3, &mut 'c'))); + assert_eq!(cur.remove_next(), Some((4, 'd'))); + assert_eq!(map, BTreeMap::from([(1, 'a'), (3, 'c')])); +} + +#[test] +fn test_cursor_empty() { + let mut map = BTreeMap::new(); + let mut cur = map.lower_bound_mut(Bound::Excluded(&3)); + assert_eq!(cur.peek_next(), None); + assert_eq!(cur.peek_prev(), None); + cur.insert_after(0, 0).unwrap(); + assert_eq!(cur.peek_next(), Some((&0, &mut 0))); + assert_eq!(cur.peek_prev(), None); + assert_eq!(map, BTreeMap::from([(0, 0)])); } -#[should_panic(expected = "key must be ordered above the previous element")] #[test] fn test_cursor_mut_insert_before_1() { let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); let mut cur = map.upper_bound_mut(Bound::Included(&2)); - cur.insert_before(0, 'd'); + cur.insert_before(0, 'd').unwrap_err(); } -#[should_panic(expected = "key must be ordered above the previous element")] #[test] fn test_cursor_mut_insert_before_2() { let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); let mut cur = map.upper_bound_mut(Bound::Included(&2)); - cur.insert_before(1, 'd'); + cur.insert_before(1, 'd').unwrap_err(); } -#[should_panic(expected = "key must be ordered below the current element")] #[test] fn test_cursor_mut_insert_before_3() { let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); let mut cur = map.upper_bound_mut(Bound::Included(&2)); - cur.insert_before(2, 'd'); + cur.insert_before(2, 'd').unwrap_err(); } -#[should_panic(expected = "key must be ordered below the current element")] #[test] fn test_cursor_mut_insert_before_4() { let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); let mut cur = map.upper_bound_mut(Bound::Included(&2)); - cur.insert_before(3, 'd'); + cur.insert_before(3, 'd').unwrap_err(); } -#[should_panic(expected = "key must be ordered above the current element")] #[test] fn test_cursor_mut_insert_after_1() { let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); let mut cur = map.upper_bound_mut(Bound::Included(&2)); - cur.insert_after(1, 'd'); + cur.insert_after(1, 'd').unwrap_err(); } -#[should_panic(expected = "key must be ordered above the current element")] #[test] fn test_cursor_mut_insert_after_2() { let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); let mut cur = map.upper_bound_mut(Bound::Included(&2)); - cur.insert_after(2, 'd'); + cur.insert_after(2, 'd').unwrap_err(); } -#[should_panic(expected = "key must be ordered below the next element")] #[test] fn test_cursor_mut_insert_after_3() { let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); let mut cur = map.upper_bound_mut(Bound::Included(&2)); - cur.insert_after(3, 'd'); + cur.insert_after(3, 'd').unwrap_err(); } -#[should_panic(expected = "key must be ordered below the next element")] #[test] fn test_cursor_mut_insert_after_4() { let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); let mut cur = map.upper_bound_mut(Bound::Included(&2)); - cur.insert_after(4, 'd'); + cur.insert_after(4, 'd').unwrap_err(); } #[test] @@ -2462,14 +2501,14 @@ fn cursor_peek_prev_agrees_with_cursor_mut() { let mut map = BTreeMap::from([(1, 1), (2, 2), (3, 3)]); let cursor = map.lower_bound(Bound::Excluded(&3)); - assert!(cursor.key().is_none()); + assert!(cursor.peek_next().is_none()); let prev = cursor.peek_prev(); assert_matches!(prev, Some((&3, _))); // Shadow names so the two parts of this test match. let mut cursor = map.lower_bound_mut(Bound::Excluded(&3)); - assert!(cursor.key().is_none()); + assert!(cursor.peek_next().is_none()); let prev = cursor.peek_prev(); assert_matches!(prev, Some((&3, _))); diff --git a/library/alloc/src/collections/btree/node.rs b/library/alloc/src/collections/btree/node.rs index 3233a575ecf..78ccb3af66d 100644 --- a/library/alloc/src/collections/btree/node.rs +++ b/library/alloc/src/collections/btree/node.rs @@ -648,17 +648,36 @@ impl<K, V, Type> NodeRef<marker::Owned, K, V, Type> { impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> { /// Adds a key-value pair to the end of the node, and returns - /// the mutable reference of the inserted value. - pub fn push(&mut self, key: K, val: V) -> &mut V { + /// a handle to the inserted value. + /// + /// # Safety + /// + /// The returned handle has an unbound lifetime. + pub unsafe fn push_with_handle<'b>( + &mut self, + key: K, + val: V, + ) -> Handle<NodeRef<marker::Mut<'b>, K, V, marker::Leaf>, marker::KV> { let len = self.len_mut(); let idx = usize::from(*len); assert!(idx < CAPACITY); *len += 1; unsafe { self.key_area_mut(idx).write(key); - self.val_area_mut(idx).write(val) + self.val_area_mut(idx).write(val); + Handle::new_kv( + NodeRef { height: self.height, node: self.node, _marker: PhantomData }, + idx, + ) } } + + /// Adds a key-value pair to the end of the node, and returns + /// the mutable reference of the inserted value. + pub fn push(&mut self, key: K, val: V) -> *mut V { + // SAFETY: The unbound handle is no longer accessible. + unsafe { self.push_with_handle(key, val).into_val_mut() } + } } impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::Internal> { @@ -1100,10 +1119,10 @@ impl<'a, K: 'a, V: 'a, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType> unsafe { leaf.vals.get_unchecked_mut(self.idx).assume_init_mut() } } - pub fn into_kv_valmut(self) -> (&'a K, &'a mut V) { + pub fn into_kv_mut(self) -> (&'a mut K, &'a mut V) { debug_assert!(self.idx < self.node.len()); let leaf = self.node.into_leaf_mut(); - let k = unsafe { leaf.keys.get_unchecked(self.idx).assume_init_ref() }; + let k = unsafe { leaf.keys.get_unchecked_mut(self.idx).assume_init_mut() }; let v = unsafe { leaf.vals.get_unchecked_mut(self.idx).assume_init_mut() }; (k, v) } diff --git a/library/core/src/ptr/const_ptr.rs b/library/core/src/ptr/const_ptr.rs index 12ff64de879..5ce9ddeb676 100644 --- a/library/core/src/ptr/const_ptr.rs +++ b/library/core/src/ptr/const_ptr.rs @@ -220,7 +220,7 @@ impl<T: ?Sized> *const T { /// provenance. (Reconstructing address space information, if required, is your responsibility.) /// /// Using this method means that code is *not* following [Strict - /// Provenance][../index.html#strict-provenance] rules. Supporting + /// Provenance][super#strict-provenance] rules. Supporting /// [`from_exposed_addr`][] complicates specification and reasoning and may not be supported by /// tools that help you to stay conformant with the Rust memory model, so it is recommended to /// use [`addr`][pointer::addr] wherever possible. @@ -232,7 +232,7 @@ impl<T: ?Sized> *const T { /// available. /// /// It is unclear whether this method can be given a satisfying unambiguous specification. This - /// API and its claimed semantics are part of [Exposed Provenance][../index.html#exposed-provenance]. + /// API and its claimed semantics are part of [Exposed Provenance][super#exposed-provenance]. /// /// [`from_exposed_addr`]: from_exposed_addr #[must_use] diff --git a/library/core/src/ptr/mod.rs b/library/core/src/ptr/mod.rs index a9078854125..dce7e035fc7 100644 --- a/library/core/src/ptr/mod.rs +++ b/library/core/src/ptr/mod.rs @@ -649,7 +649,7 @@ pub const fn invalid_mut<T>(addr: usize) -> *mut T { /// address makes sense in the address space that this pointer will be used with. /// /// Using this function means that code is *not* following [Strict -/// Provenance][../index.html#strict-provenance] rules. "Guessing" a +/// Provenance][self#strict-provenance] rules. "Guessing" a /// suitable provenance complicates specification and reasoning and may not be supported by /// tools that help you to stay conformant with the Rust memory model, so it is recommended to /// use [`with_addr`][pointer::with_addr] wherever possible. @@ -660,7 +660,7 @@ pub const fn invalid_mut<T>(addr: usize) -> *mut T { /// pointer has to pick up. /// /// It is unclear whether this function can be given a satisfying unambiguous specification. This -/// API and its claimed semantics are part of [Exposed Provenance][../index.html#exposed-provenance]. +/// API and its claimed semantics are part of [Exposed Provenance][self#exposed-provenance]. #[must_use] #[inline(always)] #[unstable(feature = "exposed_provenance", issue = "95228")] @@ -689,7 +689,7 @@ where /// address makes sense in the address space that this pointer will be used with. /// /// Using this function means that code is *not* following [Strict -/// Provenance][../index.html#strict-provenance] rules. "Guessing" a +/// Provenance][self#strict-provenance] rules. "Guessing" a /// suitable provenance complicates specification and reasoning and may not be supported by /// tools that help you to stay conformant with the Rust memory model, so it is recommended to /// use [`with_addr`][pointer::with_addr] wherever possible. @@ -700,7 +700,7 @@ where /// pointer has to pick up. /// /// It is unclear whether this function can be given a satisfying unambiguous specification. This -/// API and its claimed semantics are part of [Exposed Provenance][../index.html#exposed-provenance]. +/// API and its claimed semantics are part of [Exposed Provenance][self#exposed-provenance]. #[must_use] #[inline(always)] #[unstable(feature = "exposed_provenance", issue = "95228")] diff --git a/library/core/src/ptr/mut_ptr.rs b/library/core/src/ptr/mut_ptr.rs index 4f5fca4367d..3e5678a7d91 100644 --- a/library/core/src/ptr/mut_ptr.rs +++ b/library/core/src/ptr/mut_ptr.rs @@ -227,7 +227,7 @@ impl<T: ?Sized> *mut T { /// provenance. (Reconstructing address space information, if required, is your responsibility.) /// /// Using this method means that code is *not* following [Strict - /// Provenance][../index.html#strict-provenance] rules. Supporting + /// Provenance][super#strict-provenance] rules. Supporting /// [`from_exposed_addr_mut`][] complicates specification and reasoning and may not be supported /// by tools that help you to stay conformant with the Rust memory model, so it is recommended /// to use [`addr`][pointer::addr] wherever possible. @@ -239,7 +239,7 @@ impl<T: ?Sized> *mut T { /// available. /// /// It is unclear whether this method can be given a satisfying unambiguous specification. This - /// API and its claimed semantics are part of [Exposed Provenance][../index.html#exposed-provenance]. + /// API and its claimed semantics are part of [Exposed Provenance][super#exposed-provenance]. /// /// [`from_exposed_addr_mut`]: from_exposed_addr_mut #[must_use] diff --git a/library/std/src/os/linux/process.rs b/library/std/src/os/linux/process.rs index 51af432d056..2ba67a6dd1a 100644 --- a/library/std/src/os/linux/process.rs +++ b/library/std/src/os/linux/process.rs @@ -149,8 +149,7 @@ pub trait CommandExt: Sealed { /// The pidfd can be retrieved from the child with [`pidfd`] or [`take_pidfd`]. /// /// A pidfd will only be created if it is possible to do so - /// in a guaranteed race-free manner (e.g. if the `clone3` system call - /// is supported). Otherwise, [`pidfd`] will return an error. + /// in a guaranteed race-free manner. Otherwise, [`pidfd`] will return an error. /// /// If a pidfd has been successfully created and not been taken from the `Child` /// then calls to `kill()`, `wait()` and `try_wait()` will use the pidfd diff --git a/library/std/src/sys/pal/unix/process/process_unix.rs b/library/std/src/sys/pal/unix/process/process_unix.rs index fac6d92439e..df0fe2bb9d8 100644 --- a/library/std/src/sys/pal/unix/process/process_unix.rs +++ b/library/std/src/sys/pal/unix/process/process_unix.rs @@ -147,8 +147,7 @@ impl Command { #[cfg(not(target_os = "linux"))] let pidfd = -1; - // Safety: We obtained the pidfd from calling `clone3` with - // `CLONE_PIDFD` so it's valid an otherwise unowned. + // Safety: We obtained the pidfd (on Linux) using SOCK_SEQPACKET, so it's valid. let mut p = unsafe { Process::new(pid, pidfd) }; let mut bytes = [0; 8]; diff --git a/library/std/src/sys/pal/unix/process/process_unix/tests.rs b/library/std/src/sys/pal/unix/process/process_unix/tests.rs index 6e952ed7c42..0a6c6ec19fc 100644 --- a/library/std/src/sys/pal/unix/process/process_unix/tests.rs +++ b/library/std/src/sys/pal/unix/process/process_unix/tests.rs @@ -62,13 +62,14 @@ fn test_command_fork_no_unwind() { } #[test] -#[cfg(target_os = "linux")] +#[cfg(target_os = "linux")] // pidfds are a linux-specific concept fn test_command_pidfd() { use crate::assert_matches::assert_matches; use crate::os::fd::{AsRawFd, RawFd}; use crate::os::linux::process::{ChildExt, CommandExt}; use crate::process::Command; + // pidfds require the pidfd_open syscall let our_pid = crate::process::id(); let pidfd = unsafe { libc::syscall(libc::SYS_pidfd_open, our_pid, 0) }; let pidfd_open_available = if pidfd >= 0 { @@ -81,7 +82,9 @@ fn test_command_pidfd() { // always exercise creation attempts let mut child = Command::new("false").create_pidfd(true).spawn().unwrap(); - // but only check if we know that the kernel supports pidfds + // but only check if we know that the kernel supports pidfds. + // We don't assert the precise value, since the standard library + // might have opened other file descriptors before our code runs. if pidfd_open_available { assert!(child.pidfd().is_ok()); } @@ -97,4 +100,17 @@ fn test_command_pidfd() { child.kill().expect("failed to kill child"); let status = child.wait().expect("error waiting on pidfd"); assert_eq!(status.signal(), Some(libc::SIGKILL)); + + let _ = Command::new("echo") + .create_pidfd(false) + .spawn() + .unwrap() + .pidfd() + .expect_err("pidfd should not have been created when create_pid(false) is set"); + + let _ = Command::new("echo") + .spawn() + .unwrap() + .pidfd() + .expect_err("pidfd should not have been created"); } diff --git a/library/std/src/sys/pal/unix/rand.rs b/library/std/src/sys/pal/unix/rand.rs index cf0fe0f47c5..1dba1ccf64e 100644 --- a/library/std/src/sys/pal/unix/rand.rs +++ b/library/std/src/sys/pal/unix/rand.rs @@ -106,7 +106,18 @@ mod imp { // supported on the current kernel. // // Also fall back in case it is disabled by something like - // seccomp or inside of virtual machines. + // seccomp or inside of docker. + // + // If the `getrandom` syscall is not implemented in the current kernel version it should return an + // `ENOSYS` error. Docker also blocks the whole syscall inside unprivileged containers, and + // returns `EPERM` (instead of `ENOSYS`) when a program tries to invoke the syscall. Because of + // that we need to check for *both* `ENOSYS` and `EPERM`. + // + // Note that Docker's behavior is breaking other projects (notably glibc), so they're planning + // to update their filtering to return `ENOSYS` in a future release: + // + // https://github.com/moby/moby/issues/42680 + // GETRANDOM_UNAVAILABLE.store(true, Ordering::Relaxed); return false; } else if err == libc::EAGAIN { diff --git a/library/std/src/sys/pal/unsupported/net.rs b/library/std/src/sys/pal/unsupported/net.rs index bbc52703f96..931fe9ba246 100644 --- a/library/std/src/sys/pal/unsupported/net.rs +++ b/library/std/src/sys/pal/unsupported/net.rs @@ -364,7 +364,4 @@ pub mod netc { pub sin6_flowinfo: u32, pub sin6_scope_id: u32, } - - #[derive(Copy, Clone)] - pub struct sockaddr {} } diff --git a/src/librustdoc/html/templates/item_union.html b/src/librustdoc/html/templates/item_union.html index 8db7986fa75..b1c1d5a63a0 100644 --- a/src/librustdoc/html/templates/item_union.html +++ b/src/librustdoc/html/templates/item_union.html @@ -1,8 +1,8 @@ <pre class="rust item-decl"><code> - {{ self.render_attributes_in_pre() | safe }} - {{ self.render_union() | safe }} + {{ self.render_attributes_in_pre()|safe }} + {{ self.render_union()|safe }} </code></pre> -{{ self.document() | safe }} +{{ self.document()|safe }} {% if self.fields_iter().peek().is_some() %} <h2 id="fields" class="fields section-header"> {# #} Fields<a href="#fields" class="anchor">§</a> {# #} @@ -12,13 +12,13 @@ <span id="structfield.{{ name }}" {#+ #} class="{{ ItemType::StructField +}} section-header"> {# #} <a href="#structfield.{{ name }}" class="anchor field">§</a> {# #} - <code>{{ name }}: {{+ self.print_ty(ty) | safe }}</code> {# #} + <code>{{ name }}: {{+ self.print_ty(ty)|safe }}</code> {# #} </span> {% if let Some(stability_class) = self.stability_field(field) %} <span class="stab {{ stability_class }}"></span> {% endif %} - {{ self.document_field(field) | safe }} + {{ self.document_field(field)|safe }} {% endfor %} {% endif %} -{{ self.render_assoc_items() | safe }} -{{ self.document_type_layout() | safe }} +{{ self.render_assoc_items()|safe }} +{{ self.document_type_layout()|safe }} diff --git a/tests/mir-opt/coroutine_drop_cleanup.main-{closure#0}.coroutine_drop.0.panic-abort.mir b/tests/mir-opt/coroutine_drop_cleanup.main-{closure#0}.coroutine_drop.0.panic-abort.mir index 25bffbe2488..7214b01c601 100644 --- a/tests/mir-opt/coroutine_drop_cleanup.main-{closure#0}.coroutine_drop.0.panic-abort.mir +++ b/tests/mir-opt/coroutine_drop_cleanup.main-{closure#0}.coroutine_drop.0.panic-abort.mir @@ -1,25 +1,4 @@ // MIR for `main::{closure#0}` 0 coroutine_drop -/* coroutine_layout = CoroutineLayout { - field_tys: { - _0: CoroutineSavedTy { - ty: std::string::String, - source_info: SourceInfo { - span: $DIR/coroutine_drop_cleanup.rs:12:13: 12:15 (#0), - scope: scope[0], - }, - ignore_for_traits: false, - }, - }, - variant_fields: { - Unresumed(0): [], - Returned (1): [], - Panicked (2): [], - Suspend0 (3): [_0], - }, - storage_conflicts: BitMatrix(1x1) { - (_0, _0), - }, -} */ fn main::{closure#0}(_1: *mut {coroutine@$DIR/coroutine_drop_cleanup.rs:11:15: 11:17}) -> () { let mut _0: (); diff --git a/tests/mir-opt/coroutine_drop_cleanup.main-{closure#0}.coroutine_drop.0.panic-unwind.mir b/tests/mir-opt/coroutine_drop_cleanup.main-{closure#0}.coroutine_drop.0.panic-unwind.mir index 2eac754b15c..00769a493b5 100644 --- a/tests/mir-opt/coroutine_drop_cleanup.main-{closure#0}.coroutine_drop.0.panic-unwind.mir +++ b/tests/mir-opt/coroutine_drop_cleanup.main-{closure#0}.coroutine_drop.0.panic-unwind.mir @@ -1,25 +1,4 @@ // MIR for `main::{closure#0}` 0 coroutine_drop -/* coroutine_layout = CoroutineLayout { - field_tys: { - _0: CoroutineSavedTy { - ty: std::string::String, - source_info: SourceInfo { - span: $DIR/coroutine_drop_cleanup.rs:12:13: 12:15 (#0), - scope: scope[0], - }, - ignore_for_traits: false, - }, - }, - variant_fields: { - Unresumed(0): [], - Returned (1): [], - Panicked (2): [], - Suspend0 (3): [_0], - }, - storage_conflicts: BitMatrix(1x1) { - (_0, _0), - }, -} */ fn main::{closure#0}(_1: *mut {coroutine@$DIR/coroutine_drop_cleanup.rs:11:15: 11:17}) -> () { let mut _0: (); diff --git a/tests/ui/command/command-create-pidfd.rs b/tests/ui/command/command-create-pidfd.rs deleted file mode 100644 index 4df443c66d6..00000000000 --- a/tests/ui/command/command-create-pidfd.rs +++ /dev/null @@ -1,56 +0,0 @@ -// run-pass -// only-linux - pidfds are a linux-specific concept - -#![feature(linux_pidfd)] -#![feature(rustc_private)] - -extern crate libc; - -use std::io::Error; -use std::os::linux::process::{ChildExt, CommandExt}; -use std::process::Command; - -fn has_clone3() -> bool { - let res = unsafe { libc::syscall(libc::SYS_clone3, 0, 0) }; - let err = (res == -1) - .then(|| Error::last_os_error()) - .expect("probe syscall should not succeed"); - - // If the `clone3` syscall is not implemented in the current kernel version it should return an - // `ENOSYS` error. Docker also blocks the whole syscall inside unprivileged containers, and - // returns `EPERM` (instead of `ENOSYS`) when a program tries to invoke the syscall. Because of - // that we need to check for *both* `ENOSYS` and `EPERM`. - // - // Note that Docker's behavior is breaking other projects (notably glibc), so they're planning - // to update their filtering to return `ENOSYS` in a future release: - // - // https://github.com/moby/moby/issues/42680 - // - err.raw_os_error() != Some(libc::ENOSYS) && err.raw_os_error() != Some(libc::EPERM) -} - -fn main() { - // pidfds require the clone3 syscall - if !has_clone3() { - return; - } - - // We don't assert the precise value, since the standard library - // might have opened other file descriptors before our code runs. - let _ = Command::new("echo") - .create_pidfd(true) - .spawn() - .unwrap() - .pidfd().expect("failed to obtain pidfd"); - - let _ = Command::new("echo") - .create_pidfd(false) - .spawn() - .unwrap() - .pidfd().expect_err("pidfd should not have been created when create_pid(false) is set"); - - let _ = Command::new("echo") - .spawn() - .unwrap() - .pidfd().expect_err("pidfd should not have been created"); -} |