From be60bcb28a4e4099e29aa8f6e9e3ca851193344b Mon Sep 17 00:00:00 2001 From: Nicholas Nethercote Date: Wed, 8 Mar 2023 15:53:56 +1100 Subject: Rename `MapInPlace` as `FlatMapInPlace`. After removing the `map_in_place` method, which isn't much use because modifying every element in a collection such as a `Vec` can be done trivially with iteration. --- compiler/rustc_ast/src/mut_visit.rs | 2 +- .../rustc_data_structures/src/flat_map_in_place.rs | 72 ++++++++++++++++++++ compiler/rustc_data_structures/src/lib.rs | 2 +- compiler/rustc_data_structures/src/map_in_place.rs | 79 ---------------------- compiler/rustc_expand/src/config.rs | 2 +- compiler/rustc_expand/src/expand.rs | 2 +- 6 files changed, 76 insertions(+), 83 deletions(-) create mode 100644 compiler/rustc_data_structures/src/flat_map_in_place.rs delete mode 100644 compiler/rustc_data_structures/src/map_in_place.rs diff --git a/compiler/rustc_ast/src/mut_visit.rs b/compiler/rustc_ast/src/mut_visit.rs index 7dcb03b4c78..6fed0b660e8 100644 --- a/compiler/rustc_ast/src/mut_visit.rs +++ b/compiler/rustc_ast/src/mut_visit.rs @@ -12,7 +12,7 @@ use crate::ptr::P; use crate::token::{self, Token}; use crate::tokenstream::*; -use rustc_data_structures::map_in_place::MapInPlace; +use rustc_data_structures::flat_map_in_place::FlatMapInPlace; use rustc_data_structures::sync::Lrc; use rustc_span::source_map::Spanned; use rustc_span::symbol::Ident; diff --git a/compiler/rustc_data_structures/src/flat_map_in_place.rs b/compiler/rustc_data_structures/src/flat_map_in_place.rs new file mode 100644 index 00000000000..f58844f2817 --- /dev/null +++ b/compiler/rustc_data_structures/src/flat_map_in_place.rs @@ -0,0 +1,72 @@ +use smallvec::{Array, SmallVec}; +use std::ptr; +use thin_vec::ThinVec; + +pub trait FlatMapInPlace: Sized { + fn flat_map_in_place(&mut self, f: F) + where + F: FnMut(T) -> I, + I: IntoIterator; +} + +// The implementation of this method is syntactically identical for all the +// different vector types. +macro_rules! flat_map_in_place { + () => { + fn flat_map_in_place(&mut self, mut f: F) + where + F: FnMut(T) -> I, + I: IntoIterator, + { + let mut read_i = 0; + let mut write_i = 0; + unsafe { + let mut old_len = self.len(); + self.set_len(0); // make sure we just leak elements in case of panic + + while read_i < old_len { + // move the read_i'th item out of the vector and map it + // to an iterator + let e = ptr::read(self.as_ptr().add(read_i)); + let iter = f(e).into_iter(); + read_i += 1; + + for e in iter { + if write_i < read_i { + ptr::write(self.as_mut_ptr().add(write_i), e); + write_i += 1; + } else { + // If this is reached we ran out of space + // in the middle of the vector. + // However, the vector is in a valid state here, + // so we just do a somewhat inefficient insert. + self.set_len(old_len); + self.insert(write_i, e); + + old_len = self.len(); + self.set_len(0); + + read_i += 1; + write_i += 1; + } + } + } + + // write_i tracks the number of actually written new items. + self.set_len(write_i); + } + } + }; +} + +impl FlatMapInPlace for Vec { + flat_map_in_place!(); +} + +impl> FlatMapInPlace for SmallVec { + flat_map_in_place!(); +} + +impl FlatMapInPlace for ThinVec { + flat_map_in_place!(); +} diff --git a/compiler/rustc_data_structures/src/lib.rs b/compiler/rustc_data_structures/src/lib.rs index a94e52fdfe6..c595bf830a3 100644 --- a/compiler/rustc_data_structures/src/lib.rs +++ b/compiler/rustc_data_structures/src/lib.rs @@ -50,6 +50,7 @@ pub fn cold_path R, R>(f: F) -> R { pub mod base_n; pub mod binary_search_util; pub mod captures; +pub mod flat_map_in_place; pub mod flock; pub mod functor; pub mod fx; @@ -57,7 +58,6 @@ pub mod graph; pub mod intern; pub mod jobserver; pub mod macros; -pub mod map_in_place; pub mod obligation_forest; pub mod owning_ref; pub mod sip128; diff --git a/compiler/rustc_data_structures/src/map_in_place.rs b/compiler/rustc_data_structures/src/map_in_place.rs deleted file mode 100644 index a0d4b7ade1f..00000000000 --- a/compiler/rustc_data_structures/src/map_in_place.rs +++ /dev/null @@ -1,79 +0,0 @@ -use smallvec::{Array, SmallVec}; -use std::ptr; -use thin_vec::ThinVec; - -pub trait MapInPlace: Sized { - fn map_in_place(&mut self, mut f: F) - where - F: FnMut(T) -> T, - { - self.flat_map_in_place(|e| Some(f(e))) - } - - fn flat_map_in_place(&mut self, f: F) - where - F: FnMut(T) -> I, - I: IntoIterator; -} - -// The implementation of this method is syntactically identical for all the -// different vector types. -macro_rules! flat_map_in_place { - () => { - fn flat_map_in_place(&mut self, mut f: F) - where - F: FnMut(T) -> I, - I: IntoIterator, - { - let mut read_i = 0; - let mut write_i = 0; - unsafe { - let mut old_len = self.len(); - self.set_len(0); // make sure we just leak elements in case of panic - - while read_i < old_len { - // move the read_i'th item out of the vector and map it - // to an iterator - let e = ptr::read(self.as_ptr().add(read_i)); - let iter = f(e).into_iter(); - read_i += 1; - - for e in iter { - if write_i < read_i { - ptr::write(self.as_mut_ptr().add(write_i), e); - write_i += 1; - } else { - // If this is reached we ran out of space - // in the middle of the vector. - // However, the vector is in a valid state here, - // so we just do a somewhat inefficient insert. - self.set_len(old_len); - self.insert(write_i, e); - - old_len = self.len(); - self.set_len(0); - - read_i += 1; - write_i += 1; - } - } - } - - // write_i tracks the number of actually written new items. - self.set_len(write_i); - } - } - }; -} - -impl MapInPlace for Vec { - flat_map_in_place!(); -} - -impl> MapInPlace for SmallVec { - flat_map_in_place!(); -} - -impl MapInPlace for ThinVec { - flat_map_in_place!(); -} diff --git a/compiler/rustc_expand/src/config.rs b/compiler/rustc_expand/src/config.rs index 01500c2c77c..d6cb173ba9b 100644 --- a/compiler/rustc_expand/src/config.rs +++ b/compiler/rustc_expand/src/config.rs @@ -12,8 +12,8 @@ use rustc_ast::tokenstream::{LazyAttrTokenStream, TokenTree}; use rustc_ast::NodeId; use rustc_ast::{self as ast, AttrStyle, Attribute, HasAttrs, HasTokens, MetaItem}; use rustc_attr as attr; +use rustc_data_structures::flat_map_in_place::FlatMapInPlace; use rustc_data_structures::fx::FxHashMap; -use rustc_data_structures::map_in_place::MapInPlace; use rustc_feature::{Feature, Features, State as FeatureState}; use rustc_feature::{ ACCEPTED_FEATURES, ACTIVE_FEATURES, REMOVED_FEATURES, STABLE_REMOVED_FEATURES, diff --git a/compiler/rustc_expand/src/expand.rs b/compiler/rustc_expand/src/expand.rs index 79d058d9c97..4092a192e0c 100644 --- a/compiler/rustc_expand/src/expand.rs +++ b/compiler/rustc_expand/src/expand.rs @@ -20,7 +20,7 @@ use rustc_ast::{ForeignItemKind, HasAttrs, HasNodeId}; use rustc_ast::{Inline, ItemKind, MacStmtStyle, MetaItemKind, ModKind}; use rustc_ast::{NestedMetaItem, NodeId, PatKind, StmtKind, TyKind}; use rustc_ast_pretty::pprust; -use rustc_data_structures::map_in_place::MapInPlace; +use rustc_data_structures::flat_map_in_place::FlatMapInPlace; use rustc_data_structures::sync::Lrc; use rustc_errors::PResult; use rustc_feature::Features; -- cgit 1.4.1-3-g733a5