Tracking issue for `slice::partition_dedup/by/by_key`

[Kerollmops]

Add three methods to the slice type, the partition_dedup, partition_dedup_by and partition_dedup_by_key. The two other methods are based on slice::partition_dedup_by.

Steps / History

• Implement the feature as a PR (Introduce the partition_dedup/by/by_key methods for slices #54058)
• Stabilization PR (see instructions on forge)

Unresolved Questions

• Should the methods only return one slice instead of a tuple with two slices? (comment)
• Annotate it with #[must_use]?
• slice::sort_by_key has more restrictions than slice::sort_by #34162

[SimonSapin]

This issue tracks:

impl<T> [T] {
    pub fn partition_dedup(&mut self) -> (&mut [T], &mut [T])
    where
        T: PartialEq,
    {
        self.partition_dedup_by(|a, b| a == b)
    }

    pub fn partition_dedup_by<F>(&mut self, mut same_bucket: F) -> (&mut [T], &mut [T])
    where
        F: FnMut(&mut T, &mut T) -> bool,
    {…}

    pub fn partition_dedup_by_key<K, F>(&mut self, mut key: F) -> (&mut [T], &mut [T])
    where
        F: FnMut(&mut T) -> K,
        K: PartialEq,
    {
        self.partition_dedup_by(|a, b| key(a) == key(b))
    }
}

The doc-comment of partition_dedup_by (the others are similar) is:

Moves all but the first of consecutive elements to the end of the slice satisfying a given equality relation.

Returns two slices. The first contains no consecutive repeated elements. The second contains all the duplicates in no specified order.

The same_bucket function is passed references to two elements from the slice and must determine if the elements compare equal. The elements are passed in opposite order from their order in the slice, so if same_bucket(a, b) returns true, a is moved at the end of the slice.

If the slice is sorted, the first returned slice contains no duplicates.

Examples

#![feature(slice_partition_dedup)]

let mut slice = ["foo", "Foo", "BAZ", "Bar", "bar", "baz", "BAZ"];

let (dedup, duplicates) = slice.partition_dedup_by(|a, b| a.eq_ignore_ascii_case(b));

assert_eq!(dedup, ["foo", "BAZ", "Bar", "baz"]);
assert_eq!(duplicates, ["bar", "Foo", "BAZ"]);

From the implementation PR:

The benefits of adding these methods is that it is now possible to:

• deduplicate a slice without having to allocate and possibly clone elements on the heap, really useful for embedded stuff that can't allocate for example.
• not loose duplicate elements, because, when using Vec::dedup, duplicates elements are dropped. These methods add more flexibillity to the user.

[SimonSapin]

These methods feel very niche to me (given we already have the Vec::dedup family of methods), similar to some things we currently have in https://crates.io/crates/itertools rather then std::iter. Still, multiple people were involved in the implementation PR and were evidently happy enough to land it. So I’d be inclined to propose FCP to stabilize.

@rust-lang/libs, any thoughts?

[Lokathor]

Note that Vec::dedup is actually implemented in terms of these methods, so it's very important to anyone trying to implement vec-like replacements that these become available on stable.

[LukasKalbertodt]

@leonardo-m brought up the question of whether the second element of the returned tuple is even used. If not, it would simplify the API to return only one slice instead of a tuple. So it would be really useful to know how people use this feature. If it's merely used as a way to dedup without allocation, then yes, the first slice is sufficient. All usages I was able to find via a quick GH search indeed only used the first returned slice.

But as I agree this is pretty niche, I think it's fine if the API is a bit more complicated. Niche APIs have a stronger focus on being powerful than being easy to use, I think.

My initial thought also was that this API is too niche and shouldn't be included, but apparently it is used a lot (even excluding Rust forks, there are quite a few projects using it on the first few pages of the search results). So I'd be fine with stabilizing this as soon as the return type question is resolved.

[SimonSapin]

As far as I can tell if the method returns one slice the other behavior can still be achieved by only keeping the length of that returned slice and then using split_at_mut on the original slice.

[Kerollmops]

I thought that it would be great to also add the #[must_use] attribute to these functions.

[kennytm]

The link above gives ~1500 results. Excluding the word "slice_internals" and "fmt_internals" and forcing the language to be Rust leaves only 12 results. So 99% of this "lot" are very likely just rustc clones.

A more accurate search would be:

https://github.com/search?l=Rust&q=partition_dedup+NOT+slice_internals+NOT+fmt_internals+NOT+test_binary_search_implementation_details&type=Code (12 results)
https://github.com/search?l=Rust&q=partition_dedup_by+NOT+slice_internals+NOT+fmt_internals+NOT+test_binary_search_implementation_details+NOT+vec_intoiter_debug&type=Code (10 results)
https://github.com/search?l=Rust&q=partition_dedup_by_key+NOT+slice_internals+NOT+fmt_internals+NOT+vec_intoiter_debug&type=Code (1 result)

Only 3 examples actually try to use the second element:

1. https://github.com/treuherz/AdventOfCode/blob/152da4d32c4d6a258ec669f2fc175db99a4e1df8/18/rs/src/bin/2.rs#L66-L84 uses the second part of partition_dedup() to locate the first duplicated element.

       let (_, dupes) = working.partition_dedup();
       if !dupes.is_empty() {
           assert_eq!(dupes.len(), 1);
           return dupes.first().unwrap().to_string();
       }

   but I don't think it is a good example, as it's easier to just write

       if let Some(first_dupe) = working.windows(2).find(|(p, q)| p == q) {
           return first_dupe.to_string();
       }

2. https://github.com/sachaarbonel/poker.rs/blob/1f4ef45872307b1a3c40795ff5b125b6d82cd68f/src/bin.rs uses the second part to determine if the poker hand has pairs/triples/4 of a kind. But the message already shows how unreliable it is for the purpose.

   let (dedup, _dup) = numbers.partition_dedup();
   println!("dedup {:?} dup {:?}",dedup, _dup );
   match _dup.len() {
        0 => println!("no pair"),
        1 => println!("one pair"),
        2 => println!("three of a kind or two pairs, do an other match"),
        3 => println!("four of a kind"),
        _ => println!("not handled"),
   }

   The actual implementation in https://github.com/sachaarbonel/poker.rs/blob/1f4ef45872307b1a3c40795ff5b125b6d82cd68f/src/hand/mod.rs uses two calls of partition_dedup to distinguish two-pair (AA22) vs triples (AAA) and four-of-a-kind (AAAA) vs full-house (AAA22).

   IMO partition_dedup is far from useful as a poker hand classifier since it can't handle flushes or straights.

3. https://github.com/smmalis37/aoc2019/blob/c1015c7d2bba8075176650ac84f4f3c53b63e1d3/src/days/day10.rs#L86-L101 Probably the only legit use case though I can't quite figure out what it's trying to do.

   loop {
       subangles.sort_unstable_by_key(|ad| ad.1);
       subangles.sort_by_key(|ad| ad.0);
       let (left, right) =
           subangles.partition_dedup_by(|&mut ad1, &mut ad2| float_equals(ad1.0, ad2.0));
       if seek < left.len() {
           let (angle, distance) = left[seek];
           let coord = angle_distance_to_coord(part1_coord, angle, distance);
           return (coord, coord.x * 100 + coord.y);
       } else {
           seek -= left.len();
           subangles = right;
       }
   }

Conclusion: The second element is extremely niche, and encourages bad algorithm. As mentioned in #54279 (comment), the original slice is not destroyed, so the two-element version can be easily reimplemented by the one-element version using split_at_mut (heck, the current implementation also uses split_at_mut):

fn partition_dedup(&mut self) -> (&mut Self, &mut Self) {
    let p = self.dedup_in_place().len();
    self.split_at_mut(p)
}

There is no reason to keep the second element from the return type.

[LukasKalbertodt]

@kennytm Wow, thanks for the research! I clearly didn't put enough time into my comment and was indeed fooled by my search.

In case we change the return type to only return the first part of the slice, maybe we should also think about renaming the methods. Shepmaster suggested the current name partially because of the 2-tuple return type. I don't mind the current name (the algorithm still does some kind of partitioning), but another name might be more appropriate: the return type is different than Iterator::partition and as we seem to have established, almost no one is interested in the second bucket. What about dedup_in_place?

[Lokathor]

Note: The side effect of this method is that the input slice is swapped all around on success so that the initial span of the spice is the deduped portion. Thus, must_use would be inappropriate.

[smmalis37]

Oh hey I've been mentioned. Yeah that use case is very much artificial, it was part of the Advent of Code, a series of puzzles. The puzzle for day 10 can be found at https://adventofcode.com/2019/day/10, although you'd need to solve part 1 before it reveals part 2 which this was part of. However as you said i could easily just use split_at_mut and be fine.

[dtolnay]

I would be inclined to remove these methods. This is an uncommon use case. The algorithm can be implemented in ~20 lines of safe code if you don't mind the bounds checks. I think the amount of benefit we'd deliver by stabilizing these is much less than what it costs to put these fairly complicated names and signatures in front of everyone in the documentation of slices.