Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

add find_or_insert method to the Map trait #5568

Closed
thestinger opened this issue Mar 26, 2013 · 24 comments
Closed

add find_or_insert method to the Map trait #5568

thestinger opened this issue Mar 26, 2013 · 24 comments
Labels
E-easy Call for participation: Easy difficulty. Experience needed to fix: Not much. Good first issue.

Comments

@thestinger
Copy link
Contributor

No description provided.

@ghost ghost assigned thestinger Mar 26, 2013
@graydon
Copy link
Contributor

graydon commented Jun 6, 2013

Agreed. Also several of the other ones that appear on hashmap: find_or_insert_with, insert_or_update_with, reserve_at_least, consume.

@thestinger
Copy link
Contributor Author

@graydon: I think consume will get replaced with an external iterator, moving the container into the iterator on creation

@davidhalperin
Copy link
Contributor

I'm working on this. I'm trying to add default methods where possible, swap can be implemented in terms of insert_or_update_with for instance. Unfortunately, find_or_insert_with and insert_or_update_with can't quite be implemented in terms of each other. The options for this as far as I can tell are:

  • Implementing default methods for one of these inefficiently so it has to find the key twice. (Obviously the maps in std would override both anyway.)
  • Not having a default method for both of these so that there are 2 basic insert-like methods that implementations would be forced to provide.
  • Adding another most general insert-like method. (Something like insert_with_or_update_with but hopefully with a less cumbersome name.)

Any preferences between those or other suggestions?

@thestinger
Copy link
Contributor Author

I don't think there should be a default method implementation if it's going to do two searches but I'm fine with both of the other options.

@nikomatsakis
Copy link
Contributor

Perhaps we can just add "mangle" to the map trait and impl the others as default methods based on that?

@davidhalperin
Copy link
Contributor

First, sorry for saying I was going to do this and sitting on it for so long. I keep meaning to make time to try to help out with rust but getting busy with other things. I still plan to try to get this done.

How about changing find_or_insert_with to return (&'a K, &'a mut V) instead of just &'a mut V? It seems like there should be some sort of insert operation where you remember what the key was afterwards, anyway. If we did that, it would mean you could implement insert_or_update_with like so:

fn insert_or_update_with<'a>(&'a mut self, k: K, v: V,
                             f: &fn(&K, &mut V)) -> &'a mut V {
    let cell = Cell::new(v);
    let (k, v) = self.find_or_insert_with(k, |_| cell.take());
    if !cell.is_empty() {
        f(k, v);
    }
    v
}

That seems nicer than mangle to me. I think mangle is a little clunky and poorly named, FWIW. Up to you guys though.

@nikomatsakis
Copy link
Contributor

Interesting thought! I agree that mangle is clunky and awkwardly named (despite being the one who suggested it).

I would also consider just modifying the callback for insert_or_update_with not to take the key. I personally have never once needed it, and I see no code in our repository that does either (though I guess that, in the general case of affine keys, it can be useful).

@TeXitoi
Copy link
Contributor

TeXitoi commented Oct 31, 2013

@davidhalperin : are you still working on that? I am interested in working on this issue. Maybe we can work together?

@davidhalperin
Copy link
Contributor

@TeXitoi sorry for not getting back to you. I have Monday off and I think I should have a good chunk of time to work on this this weekend. By the end of the day on Monday I'll either finish this and put together a pull request or pass what I've done so far on to you to finish up. Sound good?

@TeXitoi
Copy link
Contributor

TeXitoi commented Nov 9, 2013

@davidascher Perfect :)

@davidhalperin
Copy link
Contributor

I got very close to finishing it this weekend. The one thing I couldn't figure out is how to write insert_or_update_with for TreeMap. You can't just make a recursive call and then call skew and split like the current insert does because this insert returns an internal pointer, so the current node stays mutably borrowed and you can't mutably borrow again it to balance the tree. If anyone has any ideas about how to get around that, I should be able to finish this up shortly.

@TeXitoi
Copy link
Contributor

TeXitoi commented Nov 16, 2013

IMHO, it's not possible to do that with safe code without doing an insert and then a find (i.e. with 2 searches). Then, skew and split move the children, so the reference should be valid. The only way I can see to do that with a search is with unsafe code:

fn insert_or_update_with<'a, K: TotalOrd, V>(
    node: &'a mut Option<~TreeNode<K, V>>,
    key: K, value: V,
    f: &fn(&K, &mut V)) -> &'a mut V {
    match *node {
      Some(ref mut save) => {
        match key.cmp(&save.key) {
          Less => {
            let res: *mut V = unsafe {
              transmute(insert_or_update_with(&mut save.left, key, value, f))
            };
            skew(save);
            split(save);
            unsafe{transmute(res)}
          }
          Greater => {
            let res: *mut V = unsafe {
              transmute(insert_or_update_with(&mut save.right, key, value, f))
            };
            skew(save);
            split(save);
            unsafe{transmute(res)}
          }
          Equal => {
            save.key = key;
            f(&save.key, &mut save.value);
            &mut save.value
          }
        }
      }
      None => {
       *node = Some(~TreeNode::new(key, value));
        &mut node.get_mut_ref().value
      }
    }    
}

It compiles, but I didn't try running it and that's the first time I write unsafe code. And that's quite sad to have TreeMap using unsafe code.

I hope I'm wrong and there is another solution.

@davidhalperin
Copy link
Contributor

@TeXitoi I reached the same conclusion and was going to ask for a sanity check. I don't think doing 2 searches would help even if we wanted to sacrifice performance to write safe code. The key gets moved into the map and if you tried to keep a reference while you rebalanced the key, you'd run into exactly the same issue. My implementation uses transmute_mut_region instead of transmute to be a little more specific about how it's being unsafe but is basically the same and it seems to work. Thanks for the help! I will finish this up today.

@nikomatsakis
Copy link
Contributor

That does indeed look hard to type check. It wasn't obvious to me from glancing at the code that it was safe amidst all the unique pointer juggling and so on. @davidhalperin I think doing an insert and then a search would work, if you wanted to keep the code safe? not sure why it matters that key/value are moved into the map.

@davidhalperin
Copy link
Contributor

@nikomatsakis Let's say the helper find_or_insert_with returned &'a K instead of &'a mut V. The actual method in the impl would call the helper then call find_mut. That's how we'd do the insert then search, or am I missing something? We can't safely implement a helper find_or_insert_with that returns &'a K for exactly the same reason we can't write one that returns &'a mut V. The left branch would look like:

Left => {
    let k = find_or_insert_with(&mut save.left, key, f);
    skew(save); // We can't borrow save again here because we're holding onto k
    split(save);
    k
}

Is there a different way we could avoid do the insert then search strategy that would avoid that problem?

@nikomatsakis
Copy link
Contributor

@davidhalperin Ah, NOW I think I see your point. Yes, without the ability to clone the key, it does leave us in a bit of a pickle, doesn't it? You can't do the find after the insert because the key is moved; you can't return a pointer to the key because it would prolong the loan on the map (and rightly so).

If were insistent on avoiding unsafe code, I imagine we could have some insert-like helper that takes an optional vector in which the path to the node can be encoded:

enum Path { Left, Right };

fn find_or_insert_with(key: K, value: V, ...) -> &'mut V {
    let mut path = ~[];
    self.insert_helper(key, value, &mut path);
    self.find_from_path(path)
}

fn insert_helper(key: K, value: V, ..., path: &mut ~[Path]) {
    ...
    if should insert on left left {
        path.push(Left);
        self.left.insert_helper(key, value, ...);
    } else { ... }
}

fn find_from_path(&mut self, path: &[Path]) -> &'a mut V {
    if path.is_empty() { return &mut self.value; }
    match path[0] {
        Left => self.left.find_from_path(path.slice_from(1)),
        Right => ...    
    }
}

Obviously this is a bit over the top, though out of idle curiosity I do wonder if you could encode the path in a u64 and a uint -- probably not, depends I guess on the balancing guarantees. :)

@pnkfelix
Copy link
Member

cc me

@aochagavia
Copy link
Contributor

Is this solved? If not, I would like to work on it.

@davidhalperin
Copy link
Contributor

@aochagavia My pull request got closed with the comment that the map trait should be thought out more, so I don't think this is going to be done as described in this issue (if it is, I should be able to dust of my changes pretty easily). If you want to work on something around this you should probably talk to the rust devs and see what they actually want.

@brson
Copy link
Contributor

brson commented Jun 9, 2014

Nominating for removal from milestone. The world won't end if this method isn't defined in 1.0.

@pnkfelix
Copy link
Member

Removing from milestone.

(The process of reviewing the std lib and assigning stability attributes shouid eventually address this problem, perhaps by marking the existing Map as unstable.)

@pnkfelix pnkfelix removed this from the 1.0 milestone Jun 12, 2014
@gereeter
Copy link
Contributor

Should this be closed now that rust-lang/rfcs#216 has been accepted?

@alexcrichton
Copy link
Member

This isn't quite a dupe of that RFC because it doesn't mention the Map trait specifically (which this issue is referring to), but I think this is best covered by rust-lang/rfcs#235 now, so I'm going to close this in favor of that. Note that rust-lang/rfcs#235 recommends removing all collections traits, which would make this issue moot.

@Gankra
Copy link
Contributor

Gankra commented Sep 28, 2014

At very least, find_or_insert is deprecated, now. So adding it to Map is uh... dubious?

flip1995 pushed a commit to flip1995/rust that referenced this issue May 17, 2020
…=flip1995

Rename lint `identity_conversion` to `useless_conversion`

Lint name `identity_conversion` was misleading, so this PR renames it to `useless_conversion`.

As decision has not really came up in the issue comments, this PR will probably need discussion.

fixes rust-lang#3106

changelog: Rename lint `identity_conversion` to `useless_conversion`
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
E-easy Call for participation: Easy difficulty. Experience needed to fix: Not much. Good first issue.
Projects
None yet
Development

Successfully merging a pull request may close this issue.