rust-lang / rust-lang/nomicon

Change Vec Drain implementation to support ranges

Open
#72 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
CSS
Stars
2.3k
Forks
325
PR merge metrics
No merged PRs in 30d

Description

Hi,
I was thinking to change Drain implementation a bit - to support Ranges like in std library - this should be nice use case for problem when leaking Drain - as original vector will not be updated at all - so nothing gets drained.

I'm beginner - so this is what I tried:

 pub struct Drain<'a, T: 'a> {
    vec: &'a mut Vec<T>,
    iter: RawValIter<T>,
    start: usize,
    end: usize,
}

and it's constructor in vector:

pub fn drain<R>(&mut self, range: R) -> Drain<T>
    where
        R: RangeBounds<usize>,
    {
        unsafe {
            let start = match range.start_bound() {
                Bound::Unbounded => 0,
                Bound::Included(s) => *s,
                Bound::Excluded(s) => *s + 1,
            };

            let end = match range.end_bound() {
                Bound::Unbounded => self.len(),
                Bound::Excluded(e) => *e,
                Bound::Included(e) => *e + 1,
            };
            assert!(start < self.len(), "invalid lower bound");
            assert!(end <= self.len(), "invalid upper bound");
            assert!(
                start <= end,
                "invalid bounds, lower must be less or equal then upper"
            );

            let iter = RawValIter::new(&self[start..end]);

            Drain {
                start: start,
                end: end,
                iter: iter,
                vec: self,
            }
        }
    }

then we can update Drop just to get rid of drained range:

impl<'a, T> Drop for Drain<'a, T> {
    fn drop(&mut self) {
        // pre-drain the iter
        for _ in &mut self.iter {}
        // now we need to fix vector - set correct len and moved drained parts our of buffer
        self.vec.remove_range(self.start, self.end)
    }
}

and vec's remove_range is:

fn remove_range(&mut self, start: usize, end: usize) {
        unsafe {
            let old_len = self.len;
            let to_remove = end - start;
            self.len = old_len - to_remove;
            // copy memory only if something was removed and something will remain in vector
            if self.len > 0 && to_remove > 0 && end < old_len {
                ptr::copy(
                    self.ptr().offset(end as isize),
                    self.ptr().offset(start as isize),
                    old_len - end,
                )
            }
        }
    }

I hope I get it right.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Locate the current Vec::drain, Drain, RawValIter, and remove_range implementations and read how draining and dropping currently affect the vector. Add range-bound support while preserving correct behavior when Drain is leaked, then verify the existing vector tests and range cases cover the requested behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
backend
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.