Implement collections reform #18424

alexcrichton · 2014-10-29T15:34:44Z

Tracking issue for rust-lang/rfcs#235, there are a number of sub-issues associated with this:

Backwards incompatible changes to make:

Backwards compatible changes that will require additional language features:

Add ByNeed and Predicate traits (needs negative bounds to work with unboxed closures)

Backwards compatible changes to make:

The text was updated successfully, but these errors were encountered:

alexcrichton · 2014-10-29T15:35:45Z

My list may not be 100% accurate, so feel free to edit @aturon!

Gankra · 2014-10-29T15:40:02Z

@aturon how do you want to coordinate this work?

gamazeps · 2014-10-29T15:49:10Z

I ca give some help for the (not to hard) bugs :)
@gankro still working on your TODO, but it's a bit more complex than expected at first reading :p

Gankra · 2014-10-29T16:14:56Z

I assume it should read "implement deref on strings and vecs"?

alexcrichton · 2014-10-29T16:15:36Z

Ooops, indeed!

This commit adds the following impls: impl<T> Deref<[T]> for Vec<T> impl<T> DerefMut<[T]> for Vec<T> impl Deref<str> for String This commit also removes all duplicated inherent methods from vectors and strings as implementations will now silently call through to the slice implementation. Some breakage occurred at std and beneath due to inherent methods removed in favor of those in the slice traits and std doesn't use its own prelude, cc rust-lang#18424

This commit enables implementations of IndexMut for a number of collections, including Vec, RingBuf, SmallIntMap, TrieMap, TreeMap, and HashMap. At the same time this deprecates the `get_mut` methods on vectors in favor of using the indexing notation. cc rust-lang#18424

alexcrichton · 2014-10-30T17:29:21Z

I'll start off by removing the collections traits. @gankro and @gamazeps, do you guys have something you'd like to start on specifically? I figure we can start out by just knocking out all the bullet points above. I can add everyone's name next to what you're working on to make sure we don't conflict. Does that sound ok?

aturon · 2014-10-30T17:32:45Z

Thanks for jumping on this @alexcrichton. I'd like to do the Borrow-related stuff, Cow and IntoIterator.

Gankra · 2014-10-30T19:47:53Z

@alexcrichton we had agreed (perhaps only informally) to take this opportunity to reorganize the modules. In particular several files define two structures, where one is a convenience wrapper for the other (most of the Sets). I want to split those up like BTree and HashMap do, to make maintenance a bit more friendly. I had hoped to do this first since it will clobber all the history, but that ship has sailed, and there's a few outstanding PRs that would need a nasty rebase. Should we delay that till later, or try to get that in ASAP?

Regardless, I can take on conventions-hell.

alexcrichton · 2014-10-30T19:51:16Z

Hm, that sounds like a good idea! Why don't we wait for me to remove the collections traits and you to land some conventions stuff, and then we can reorganize, does that sound ok?

I'll assign you to conventions-related tasks

gamazeps · 2014-10-30T20:29:19Z

@alexcrichton I'm kind of a begginer so I'm not sure I'm able to really evaluate the difficulty of the different parts, if you could assign me to the an easy one I would be very happy :p (I have nothing that I would specifically want to do)

Gankra · 2014-10-30T20:36:27Z

@gamazeps Ensuring ____ is implemented should be easy (if it's not already done).

Gankra · 2014-10-30T20:40:56Z

Renaming Extendable should also be pretty easy if you're good at search-and-replace.

Gankra · 2014-10-30T20:41:47Z

Adding repeat should also be pretty quick.

alexcrichton · 2014-10-30T20:50:03Z

@gamazeps feel like tackling Extendable => Extend and making sure everyone implements it to start out?

gamazeps · 2014-10-30T21:00:49Z

Awesome :)

gamazeps · 2014-10-30T23:57:27Z

@alexcrichton Done :) (compiling for now)
Except for Slice where I don't see where I would implement it :/

Gankra · 2014-10-30T23:59:57Z

Slices can't be extended, so that's fine.

@csherratt

Includes a fix for a small mistake in `fn insert` which is caught by test_insert for len=15, but not len=7. Part of rust-lang#18424 r? @gankro @csherratt @huonw

pczarn · 2014-12-18T11:34:40Z

I'm writing bounded iterators for BTreeMap, too

Part of rust-lang#18424 This commit changes the semantics of `reserve` and `capacity` for Bitv and BitvSet to match conventions. It also introduces the notion of `reserve_index` and `reserve_index_exact` for collections with maximum-index-based capacity semantics. Deprecates free function constructors in favour of functions on Bitv itself. Changes `Bitv::pop` to return an Option rather than panicking. Deprecates and renames several methods in favour of conventions. Marks several blessed methods as unstable. This commit also substantially refactors Bitv and BitvSet's implementations. The new implementation is simpler, cleaner, better documented, and more robust against overflows. It also reduces coupling between Bitv and BitvSet. Tests have been seperated into seperate submodules. Fixes rust-lang#16958 [breaking-change]

Part of #18424 This commit changes the semantics of `reserve` and `capacity` for Bitv and BitvSet to match conventions. It also introduces the notion of `reserve_index` and `reserve_index_exact` for collections with maximum-index-based capacity semantics. Deprecates free function constructors in favour of functions on Bitv itself. Changes `Bitv::pop` to return an Option rather than panicking. Deprecates and renames several methods in favour of conventions. Marks several blessed methods as unstable. This commit also substantially refactors Bitv and BitvSet's implementations. The new implementation is simpler, cleaner, better documented, and more robust against overflows. It also reduces coupling between Bitv and BitvSet. Tests have been seperated into seperate submodules. Fixes #16958 [breaking-change]

Part of rust-lang#18424 This commit changes the semantics of `reserve` and `capacity` for Bitv and BitvSet to match conventions. It also introduces the notion of `reserve_index` and `reserve_index_exact` for collections with maximum-index-based capacity semantics. Deprecates free function constructors in favour of functions on Bitv itself. Changes `Bitv::pop` to return an Option rather than panicking. Deprecates and renames several methods in favour of conventions. Marks several blessed methods as unstable. This commit also substantially refactors Bitv and BitvSet's implementations. The new implementation is simpler, cleaner, better documented, and more robust against overflows. It also reduces coupling between Bitv and BitvSet. Tests have been seperated into seperate submodules. Fixes rust-lang#16958 [breaking-change]

Part of #18424 This commit changes the semantics of `reserve` and `capacity` for Bitv and BitvSet to match conventions. It also introduces the notion of `reserve_index` and `reserve_index_exact` for collections with maximum-index-based capacity semantics. Deprecates free function constructors in favour of functions on Bitv itself. Changes `Bitv::pop` to return an Option rather than panicking. Deprecates and renames several methods in favour of conventions. Marks several blessed methods as unstable. This commit also substantially refactors Bitv and BitvSet's implementations. The new implementation is simpler, cleaner, better documented, and more robust against overflows. It also reduces coupling between Bitv and BitvSet. Tests have been seperated into seperate submodules. Fixes #16958 [breaking-change]

Gankra · 2014-12-30T19:21:52Z

Now that Bitv is fixed up and the less-well-maintained collections are gone, all the convention issues are fully resolved, I believe. If anyone knows of outstanding API normativity issues, let me know!

Everything else needs lang stuff, or is being brutalized by @pczarn as we speak.

Gankra · 2014-12-30T19:22:01Z

(for part 1 issues, that is)

Part of collections reform part 1 and 2, rust-lang#18424 and rust-lang#19986 * shrink_to_fit * swap_back_remove * swap_front_remove * truncate * resize

@gereeter

Part of collections reform v1, #18424 Also, iteration is simplified: ``` before test btree::map::bench::iter_1000 ... bench: 17177 ns/iter (+/- 6302) test btree::map::bench::iter_100000 ... bench: 1735731 ns/iter (+/- 23908) test btree::map::bench::iter_20 ... bench: 386 ns/iter (+/- 148) after test btree::map::bench::iter_1000 ... bench: 15777 ns/iter (+/- 346) test btree::map::bench::iter_100000 ... bench: 1602604 ns/iter (+/- 73629) test btree::map::bench::iter_20 ... bench: 339 ns/iter (+/- 91) ``` cc @gereeter @cgaebel r? @gankro

@nikomatsakis

As per [RFC rust-lang#235][rfc], you can now do: [rfc]: https://github.com/rust-lang/rfcs/blob/master/text/0235-collections-conventions.md#intoiterator-and-iterable ``` rust let mut v = vec![1]; // iterate over immutable references for x in &v { assert_eq!(x, &1); } // iterate over mutable references for x in &mut v { assert_eq!(x, &mut 1); } // iterate over values, this consumes `v` for x in v { assert_eq!(x, 1); } ``` [breaking-change]s For loops now "consume" (move) the iterator, this breaks iterating over mutable references to iterators, and also breaks multiple iterations over the same iterator: ``` rust fn foo(mut it: &mut Iter) { // `Iter` implements `Iterator` for x in it { .. } //~ error: `&mut Iter` doesn't implement Iterator } fn bar() { for x in it { .. } //~ note: `it` moved here for x in it { .. } //~ error: `it` has been moved } ``` Both cases can be fixed using the `by_ref()` adapter to create an iterator from the mutable reference: ``` rust fn foo(mut it: &mut Iter) { for x in it.by_ref() { .. } } fn bar() { for x in it.by_ref() { .. } for x in it { .. } } ``` This PR also makes iterator non-implicitly copyable, as this was source of subtle bugs in the libraries. You can still use `clone()` to explictly copy the iterator. Finally, since the for loops are implemented in the frontend and use global paths to `IntoIterator`, `Iterator` and `Option` variants, users of the `core` crate will have to use add an `std` module to the root of their crate to be able to use for loops: ``` rust #![no_std] extern crate core; fn main() { for x in 0..10 {} } #[doc(hidden)] mod std { // these imports are needed to use for-loops pub use core::iter; pub use core::option; } ``` --- r? @nikomatsakis @aturon cc rust-lang#18424 closes rust-lang#18045

alexcrichton · 2015-03-17T17:45:20Z

This issue has been growing stale for some time now, and I think that we're basically all done with the implementation work, so closing.

zommiommy · 2023-12-29T12:04:44Z

From my understanding, this RFC was blocked due to the lack of support for HKT.

The proposed HKT version of the Iterable trait is currently supported in stable:

trait Iterable {
    type A;
    type I<'a>: Iterator<&'a Self::A>;

    fn iter(&self) -> Self::I<'_>;
}

trait IterableMut {
    type A;
    type I<'a>: Iterator<&'a mut Self::A>;

    fn iter_mut(&self) -> Self::I<'_>;
}

so it might be worth re-discussing this

alexcrichton added A-libs B-RFC-approved Blocker: Approved by a merged RFC but not yet implemented. labels Oct 29, 2014

alexcrichton mentioned this issue Oct 29, 2014

RFC: Collections reform rust-lang/rfcs#235

Merged

Gankra mentioned this issue Oct 29, 2014

Metabug: Libcollections TODO #18009

Closed

30 tasks

alexcrichton mentioned this issue Oct 30, 2014

collections: impl Deref for Vec/String #18443

Merged

alexcrichton mentioned this issue Oct 30, 2014

collections: Enable IndexMut for some collections #18445

Merged

alexcrichton mentioned this issue Oct 30, 2014

Add a repeat function to the prelude #18468

Merged

pczarn mentioned this issue Dec 20, 2014

Implement bounded iterators for BTree #20082

Merged

pczarn mentioned this issue Dec 24, 2014

Implement a few methods for RingBuf #20197

Merged

kmcallister added the A-collections Area: `std::collection` label Jan 16, 2015

japaric mentioned this issue Jan 23, 2015

Introduce the IntoIterator trait and reimplement for-loops to use it #20790

Merged

alexcrichton closed this as completed Mar 17, 2015

SimonSapin mentioned this issue Aug 4, 2015

Add ByNeed and Predicate traits #27517

Closed

durka mentioned this issue Aug 27, 2015

Anomalous unstable feature annotations #28037

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Implement collections reform #18424

Implement collections reform #18424

alexcrichton commented Oct 29, 2014

alexcrichton commented Oct 29, 2014

Gankra commented Oct 29, 2014

gamazeps commented Oct 29, 2014

Gankra commented Oct 29, 2014

alexcrichton commented Oct 29, 2014

alexcrichton commented Oct 30, 2014

aturon commented Oct 30, 2014

Gankra commented Oct 30, 2014

alexcrichton commented Oct 30, 2014

gamazeps commented Oct 30, 2014

Gankra commented Oct 30, 2014

Gankra commented Oct 30, 2014

Gankra commented Oct 30, 2014

alexcrichton commented Oct 30, 2014

gamazeps commented Oct 30, 2014

gamazeps commented Oct 30, 2014

Gankra commented Oct 30, 2014

pczarn commented Dec 18, 2014

Gankra commented Dec 30, 2014

Gankra commented Dec 30, 2014

alexcrichton commented Mar 17, 2015

zommiommy commented Dec 29, 2023

Implement collections reform #18424

Implement collections reform #18424

Comments

alexcrichton commented Oct 29, 2014

alexcrichton commented Oct 29, 2014

Gankra commented Oct 29, 2014

gamazeps commented Oct 29, 2014

Gankra commented Oct 29, 2014

alexcrichton commented Oct 29, 2014

alexcrichton commented Oct 30, 2014

aturon commented Oct 30, 2014

Gankra commented Oct 30, 2014

alexcrichton commented Oct 30, 2014

gamazeps commented Oct 30, 2014

Gankra commented Oct 30, 2014

Gankra commented Oct 30, 2014

Gankra commented Oct 30, 2014

alexcrichton commented Oct 30, 2014

gamazeps commented Oct 30, 2014

gamazeps commented Oct 30, 2014

Gankra commented Oct 30, 2014

pczarn commented Dec 18, 2014

Gankra commented Dec 30, 2014

Gankra commented Dec 30, 2014

alexcrichton commented Mar 17, 2015

zommiommy commented Dec 29, 2023