about summary refs log tree commit diff
path: root/library/alloc
AgeCommit message (Collapse)AuthorLines
2022-07-15Rollup merge of #99113 - WaffleLapkin:arc_simplify, r=Mark-SimulacrumDylan DPC-12/+11
Simplify [a]rc code a little Nothing interesting, just make [a]rc code a little nicer by using `byte_sub` and `let`-`else`.
2022-07-14add missing null ptr check in alloc exampleRalf Jung-1/+4
2022-07-14add code examplesDuarte Nunes-1/+50
2022-07-14Rollup merge of #98315 - joshtriplett:stabilize-core-ffi-c, r=Mark-SimulacrumDylan DPC-2/+0
Stabilize `core::ffi:c_*` and rexport in `std::ffi` This only stabilizes the base types, not the non-zero variants, since those have their own separate tracking issue and have not gone through FCP to stabilize.
2022-07-13Stabilize `core::ffi:c_*` and rexport in `std::ffi`Josh Triplett-2/+0
This only stabilizes the base types, not the non-zero variants, since those have their own separate tracking issue and have not gone through FCP to stabilize.
2022-07-13rustdocDuarte Nunes-1/+1
2022-07-13typoDuarte Nunes-2/+2
2022-07-13changes to wordingDuarte Nunes-9/+15
2022-07-13docs: be less harsh in wording for Vec::from_raw_partsDuarte Nunes-5/+15
In particular, be clear that it is sound to specify memory not originating from a previous `Vec` allocation. That is already suggested in other parts of the documentation about zero-alloc conversions to Box<[T]>. Incorporate a constraint from `slice::from_raw_parts` that was missing but needs to be fulfilled, since a `Vec` can be converted into a slice.
2022-07-10Use `byte_sub` in [a]rc implMaybe Waffle-12/+11
2022-07-10Auto merge of #95295 - CAD97:layout-isize, r=scottmcmbors-311/+142
Enforce that layout size fits in isize in Layout As it turns out, enforcing this _in APIs that already enforce `usize` overflow_ is fairly trivial. `Layout::from_size_align_unchecked` continues to "allow" sizes which (when rounded up) would overflow `isize`, but these are now declared as library UB for `Layout`, meaning that consumers of `Layout` no longer have to check this before making an allocation. (Note that this is "immediate library UB;" IOW it is valid for a future release to make this immediate "language UB," and there is an extant patch to do so, to allow Miri to catch this misuse.) See also #95252, [Zulip discussion](https://rust-lang.zulipchat.com/#narrow/stream/219381-t-libs/topic/Layout.20Isn't.20Enforcing.20The.20isize.3A.3AMAX.20Rule). Fixes https://github.com/rust-lang/rust/issues/95334 Some relevant quotes: `@eddyb,` https://github.com/rust-lang/rust/pull/95252#issuecomment-1078513769 > [B]ecause of the non-trivial presence of both of these among code published on e.g. crates.io: > > 1. **`Layout` "producers" / `GlobalAlloc` "users"**: smart pointers (including `alloc::rc` copies with small tweaks), collections, etc. > 2. **`Layout` "consumers" / `GlobalAlloc` "providers"**: perhaps fewer of these, but anything built on top of OS APIs like `mmap` will expose `> isize::MAX` allocations (on 32-bit hosts) if they lack extra checks > > IMO the only responsible option is to enforce the `isize::MAX` limit in `Layout`, which: > > * makes `Layout` _sound_ in terms of only ever allowing allocations where `(alloc_base_ptr: *mut u8).offset(size)` is never UB > * frees both "producers" and "consumers" of `Layout` from manually reimplementing the checks > * manual checks can be risky, e.g. if the final size passed to the allocator isn't the one being checked > * this applies retroactively, fixing the overall soundness of existing code with zero transition period or _any_ changes required from users (as long as going through `Layout` is mandatory, making a "choke point") > > > Feel free to quote this comment onto any relevant issue, I might not be able to keep track of developments. `@Gankra,` https://github.com/rust-lang/rust/pull/95252#issuecomment-1078556371 > As someone who spent way too much time optimizing libcollections checks for this stuff and tried to splatter docs about it everywhere on the belief that it was a reasonable thing for people to manually take care of: I concede the point, it is not reasonable. I am wholy spiritually defeated by the fact that _liballoc_ of all places is getting this stuff wrong. This isn't throwing shade at the folks who implemented these Rc features, but rather a statement of how impractical it is to expect anyone out in the wider ecosystem to enforce them if _some of the most audited rust code in the library that defines the very notion of allocating memory_ can't even reliably do it. > > We need the nuclear option of Layout enforcing this rule. Code that breaks this rule is _deeply_ broken and any "regressions" from changing Layout's contract is a _correctness_ fix. Anyone who disagrees and is sufficiently motivated can go around our backs but the standard library should 100% refuse to enable them. cc also `@RalfJung` `@rust-lang/wg-allocators.` Even though this technically supersedes #95252, those potential failure points should almost certainly still get nicer panics than just "unwrap failed" (which they would get by this PR). It might additionally be worth recommending to users of the `Layout` API that they should ideally use `.and_then`/`?` to complete the entire layout calculation, and then `panic!` from a single location at the end of `Layout` manipulation, to reduce the overhead of the checks and optimizations preserving the exact location of each `panic` which are conceptually just one failure: allocation too big. Probably deserves a T-lang and/or T-libs-api FCP (this technically solidifies the [objects must be no larger than `isize::MAX`](https://rust-lang.github.io/unsafe-code-guidelines/layout/scalars.html#isize-and-usize) rule further, and the UCG document says this hasn't been RFCd) and a crater run. Ideally, no code exists that will start failing with this addition; if it does, it was _likely_ (but not certainly) causing UB. Changes the raw_vec allocation path, thus deserves a perf run as well. I suggest hiding whitespace-only changes in the diff view.
2022-07-08Intra-doc-link-ify reference to Clone::clone_fromest31-1/+1
2022-07-03Auto merge of #98755 - nnethercote:faster-vec-insert, r=cuviperbors-6/+9
Optimize `Vec::insert` for the case where `index == len`. By skipping the call to `copy` with a zero length. This makes it closer to `push`. I did this recently for `SmallVec` (https://github.com/servo/rust-smallvec/pull/282) and it was a big perf win in one case. Although I don't have a specific use case in mind, it seems worth doing it for `Vec` as well. Things to note: - In the `index < len` case, the number of conditions checked is unchanged. - In the `index == len` case, the number of conditions checked increases by one, but the more expensive zero-length copy is avoided. - In the `index > len` case the code now reserves space for the extra element before panicking. This seems like an unimportant change. r? `@cuviper`
2022-07-03Auto merge of #98673 - pietroalbini:pa-bootstrap-update, r=Mark-Simulacrumbors-42/+6
Bump bootstrap compiler r? `@Mark-Simulacrum`
2022-07-01Rollup merge of #98585 - cuviper:covariant-thinbox, r=thomccDylan DPC-6/+34
Make `ThinBox<T>` covariant in `T` Just like `Box<T>`, we want `ThinBox<T>` to be covariant in `T`, but the projection in `WithHeader<<T as Pointee>::Metadata>` was making it invariant. This is now hidden as `WithOpaqueHeader`, which we type-cast whenever the real `WithHeader<H>` type is needed. Fixes the problem noted in <https://github.com/rust-lang/rust/issues/92791#issuecomment-1104636249>.
2022-07-01update cfg(bootstrap)sPietro Albini-42/+6
2022-07-01Optimize `Vec::insert` for the case where `index == len`.Nicholas Nethercote-6/+9
By skipping the call to `copy` with a zero length. This makes it closer to `push`. I did this recently for `SmallVec` (https://github.com/servo/rust-smallvec/pull/282) and it was a big perf win in one case. Although I don't have a specific use case in mind, it seems worth doing it for `Vec` as well. Things to note: - In the `index < len` case, the number of conditions checked is unchanged. - In the `index == len` case, the number of conditions checked increases by one, but the more expensive zero-length copy is avoided. - In the `index > len` case the code now reserves space for the extra element before panicking. This seems like an unimportant change.
2022-06-30correct the output of a `capacity` method examplemojave2-5/+5
2022-06-29alloc: fix `no_global_oom_handling` warningsMiguel Ojeda-3/+8
Rust 1.62.0 introduced a couple new `unused_imports` warnings in `no_global_oom_handling` builds, making a total of 5 warnings: ```txt warning: unused import: `Unsize` --> library/alloc/src/boxed/thin.rs:6:33 | 6 | use core::marker::{PhantomData, Unsize}; | ^^^^^^ | = note: `#[warn(unused_imports)]` on by default warning: unused import: `from_fn` --> library/alloc/src/string.rs:51:18 | 51 | use core::iter::{from_fn, FusedIterator}; | ^^^^^^^ warning: unused import: `core::ops::Deref` --> library/alloc/src/vec/into_iter.rs:12:5 | 12 | use core::ops::Deref; | ^^^^^^^^^^^^^^^^ warning: associated function `shrink` is never used --> library/alloc/src/raw_vec.rs:424:8 | 424 | fn shrink(&mut self, cap: usize) -> Result<(), TryReserveError> { | ^^^^^^ | = note: `#[warn(dead_code)]` on by default warning: associated function `forget_remaining_elements` is never used --> library/alloc/src/vec/into_iter.rs:126:19 | 126 | pub(crate) fn forget_remaining_elements(&mut self) { | ^^^^^^^^^^^^^^^^^^^^^^^^^ ``` This patch cleans them so that projects compiling `alloc` without infallible allocations do not see the warnings. It also enables the use of `-Dwarnings`. The couple `dead_code` ones may be reverted when some fallible allocation support starts using them. Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
2022-06-28Rollup merge of #98595 - cuviper:send-sync-thinbox, r=m-ou-seDylan DPC-0/+8
Implement `Send` and `Sync` for `ThinBox<T>` Just like `Box<T>`, `ThinBox<T>` owns its data on the heap, so it should implement `Send` and `Sync` when `T` does. This extends tracking issue #92791.
2022-06-27Implement `Send` and `Sync` for `ThinBox<T>`Josh Stone-0/+8
Just like `Box<T>`, `ThinBox<T>` owns its data on the heap, so it should implement `Send` and `Sync` when `T` does.
2022-06-27Make `ThinBox<T>` covariant in `T`Josh Stone-6/+34
Just like `Box<T>`, we want `ThinBox<T>` to be covariant in `T`, but the projection in `WithHeader<<T as Pointee>::Metadata>` was making it invariant. This is now hidden as `WithOpaqueHeader`, which we type-cast whenever the real `WithHeader<H>` type is needed.
2022-06-27liballoc tests: avoid int2ptr castRalf Jung-1/+1
2022-06-24Rollup merge of #98039 - tnballo:master, r=thomccYuki Okushi-13/+117
Fix `panic` message for `BTreeSet`'s `range` API and document `panic` cases Currently, the `panic` cases for [`BTreeSet`'s `range` API](https://doc.rust-lang.org/std/collections/struct.BTreeSet.html#method.range) are undocumented and produce a slightly wrong `panic` message (says `BTreeMap` instead of `BTreeSet`). Panic case 1 code: ```rust use std::collections::BTreeSet; use std::ops::Bound::Excluded; fn main() { let mut set = BTreeSet::new(); set.insert(3); set.insert(5); set.insert(8); for &elem in set.range((Excluded(&3), Excluded(&3))) { println!("{elem}"); } } ``` Panic case 1 message: ``` thread 'main' panicked at 'range start and end are equal and excluded in BTreeMap', /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/alloc/src/collections/btree/search.rs:105:17 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace ``` Panic case 2 code: ```rust use std::collections::BTreeSet; use std::ops::Bound::Included; fn main() { let mut set = BTreeSet::new(); set.insert(3); set.insert(5); set.insert(8); for &elem in set.range((Included(&8), Included(&3))) { println!("{elem}"); } } ``` Panic case 2: ``` thread 'main' panicked at 'range start is greater than range end in BTreeMap', /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/alloc/src/collections/btree/search.rs:110:17 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace ``` This PR fixes the output messages to say `BTreeSet`, adds the relevant unit tests, and updates the documentation for the API.
2022-06-23Fix BTreeSet's range API panic message, documenttnballo-13/+117
2022-06-23Rollup merge of #98364 - RalfJung:arc-clone, r=Mark-SimulacrumMichael Goulet-8/+9
clarify Arc::clone overflow check comment I had to read this twice to realize that this is explaining that the code is technically unsound, so move that into a dedicated paragraph and make the wording a bit more explicit.
2022-06-23Rollup merge of #96173 - jmaargh:jmaargh/with-capacity-doc-fix, r=Dylan-DPCMichael Goulet-93/+138
Fix documentation for `with_capacity` and `reserve` families of methods Fixes #95614 Documentation for the following methods - `with_capacity` - `with_capacity_in` - `with_capacity_and_hasher` - `reserve` - `reserve_exact` - `try_reserve` - `try_reserve_exact` was inconsistent and often not entirely correct where they existed on the following types - `Vec` - `VecDeque` - `String` - `OsString` - `PathBuf` - `BinaryHeap` - `HashSet` - `HashMap` - `BufWriter` - `LineWriter` since the allocator is allowed to allocate more than the requested capacity in all such cases, and will frequently "allocate" much more in the case of zero-sized types (I also checked `BufReader`, but there the docs appear to be accurate as it appears to actually allocate the exact capacity). Some effort was made to make the documentation more consistent between types as well.
2022-06-21clarify Arc::clone overflow check commentRalf Jung-8/+9
2022-06-21remove use of &Alloc in btree testsRalf Jung-6/+6
2022-06-20Rollup merge of #96609 - ibraheemdev:arc-downcast-unchecked, r=m-ou-seDylan DPC-5/+80
Add `{Arc, Rc}::downcast_unchecked` Part of #90850.
2022-06-19Fix documentation for with_capacity and reserve families of methodsjmaargh-93/+138
Documentation for the following methods with_capacity with_capacity_in with_capacity_and_hasher reserve reserve_exact try_reserve try_reserve_exact was inconsistent and often not entirely correct where they existed on the following types Vec VecDeque String OsString PathBuf BinaryHeap HashSet HashMap BufWriter LineWriter since the allocator is allowed to allocate more than the requested capacity in all such cases, and will frequently "allocate" much more in the case of zero-sized types (I also checked BufReader, but there the docs appear to be accurate as it appears to actually allocate the exact capacity). Some effort was made to make the documentation more consistent between types as well. Fix with_capacity* methods for Vec Fix *reserve* methods for Vec Fix docs for *reserve* methods of VecDeque Fix docs for String::with_capacity Fix docs for *reserve* methods of String Fix docs for OsString::with_capacity Fix docs for *reserve* methods on OsString Fix docs for with_capacity* methods on HashSet Fix docs for *reserve methods of HashSet Fix docs for with_capacity* methods of HashMap Fix docs for *reserve methods on HashMap Fix expect messages about OOM in doctests Fix docs for BinaryHeap::with_capacity Fix docs for *reserve* methods of BinaryHeap Fix typos Fix docs for with_capacity on BufWriter and LineWriter Fix consistent use of `hasher` between `HashMap` and `HashSet` Fix warning in doc test Add test for capacity of vec with ZST Fix doc test error
2022-06-19Rollup merge of #98233 - RalfJung:ref-alloc, r=thomccDylan DPC-6/+6
Remove accidental uses of `&A: Allocator` Cc https://github.com/rust-lang/rust/issues/98232 Fixes https://github.com/rust-lang/rust/issues/98176 (for real this time)
2022-06-18make btree not use &A: Allocator instanceRalf Jung-6/+6
2022-06-18Auto merge of #98004 - paolobarbolini:vecdeque-extend-trustedlen, r=the8472bors-0/+208
Add VecDeque::extend from TrustedLen specialization Continuation of #95904 Inspired by how [`VecDeque::copy_slice` works](https://github.com/rust-lang/rust/blob/c08b235a5ce10167632bb0fddcd0c5d67f2d42e3/library/alloc/src/collections/vec_deque/mod.rs#L437-L454). ## Benchmarks Before ``` test vec_deque::bench_extend_chained_bytes ... bench: 1,026 ns/iter (+/- 17) test vec_deque::bench_extend_chained_trustedlen ... bench: 1,024 ns/iter (+/- 40) test vec_deque::bench_extend_trustedlen ... bench: 637 ns/iter (+/- 693) ``` After ``` test vec_deque::bench_extend_chained_bytes ... bench: 828 ns/iter (+/- 24) test vec_deque::bench_extend_chained_trustedlen ... bench: 25 ns/iter (+/- 1) test vec_deque::bench_extend_trustedlen ... bench: 21 ns/iter (+/- 0) ``` ## Why do it this way https://rust.godbolt.org/z/15qY1fMYh The Compiler Explorer example shows how "just" removing the capacity check, like the [`Vec` `TrustedLen` specialization](https://github.com/rust-lang/rust/blob/c08b235a5ce10167632bb0fddcd0c5d67f2d42e3/library/alloc/src/vec/spec_extend.rs#L22-L58) does, wouldn't have been enough for `VecDeque`. `wrap_add` would still have greatly limited what LLVM could do while optimizing. --- r? `@the8472`
2022-06-18Auto merge of #98178 - RalfJung:btree-alloc, r=thomccbors-241/+270
btree: avoid forcing the allocator to be a reference The previous code forces the actual allocator used to be some `&A`. This generalizes the code to allow any `A: Copy`. If people truly want to use a reference, they can use `&A` themselves. Fixes https://github.com/rust-lang/rust/issues/98176
2022-06-17Document the conditional existence of `alloc::sync` and `alloc::task`.Kevin Reid-0/+15
The wording is copied from `std::sync::atomic::AtomicPtr`, with additional advice on how to `#[cfg]` for it.
2022-06-17comments explaining why we have and don't have ManuallyDropRalf Jung-0/+6
2022-06-18Expose iter::ByRefSized as unstable feature and use itPaolo Barbolini-1/+2
2022-06-18Add VecDeque::extend from TrustedLen specializationPaolo Barbolini-0/+175
2022-06-17Add VecDeque::extend TrustedLen benchmarkPaolo Barbolini-0/+32
2022-06-17Rollup merge of #95392 - Xuanwo:stablize_try_reserve_2, r=dtolnayDylan DPC-4/+2
std: Stabilize feature try_reserve_2 This PR intends to stabilize feature `try_reserve_2`, closes https://github.com/rust-lang/rust/issues/91789 This PR will also replace the previous PR: https://github.com/rust-lang/rust/pull/95139
2022-06-16btree: avoid forcing the allocator to be a referenceRalf Jung-241/+264
2022-06-16Rollup merge of #98125 - KarlWithK:entry_add_modify_doc, r=Dylan-DPCMatthias Krüger-1/+6
Entry and_modify doc This PR modifies the documentation for [HashMap](https://doc.rust-lang.org/std/collections/struct.HashMap.html#) and [BTreeMap](https://doc.rust-lang.org/std/collections/struct.BTreeMap.html#) by introducing examples for `and_modify`. `and_modify` is a function that tends to give more idiomatic rust code when dealing with these data structures -- yet it lacked examples and was hidden away. This PR adds that and addresses #98122. I've made some choices which I tried to explain in my commits. This is my first time contributing to rust, so hopefully, I made the right choices.
2022-06-16std: Stabilize feature try_reserve_2Xuanwo-4/+2
Signed-off-by: Xuanwo <github@xuanwo.io>
2022-06-15change "1" to "c" to pass testKarlWithK-1/+1
Incorrectly wrote "1" twice when writing test.
2022-06-15Add examples using `add_modify` to btreeKarlWithK-1/+6
Updated the btree's documentation to include two references to add_modify. The first is when the `Entry` API is mentioned at the beginning. With the same reasoning as HashMap's documentation, I thought it would best to keep `attack`, but show the `mana` example. The second is with the `entry` function that is used for the `Entry` API. The code example was a perfect use for `add_modify`, which is why it was changed to reflect that.
2022-06-14btreemap-alloc: fix clear implJacob Hughes-15/+6
2022-06-14BTreeMap: Add alloc paramJacob Hughes-340/+676
2022-06-14Rollup merge of #97869 - ssomers:btree_comments, r=Dylan-DPCDylan DPC-6/+7
BTree: tweak internal comments
2022-06-10additional docs example for replace **all** of strbvanjoi-0/+1
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-27 09:51:30 +0000