Method accepting an iterator of either T or &T items

help
1

I'm trying to give the possibility to build an object from a collection of either items or item references, without too much code redundancy.

In my case, T is Copy (here, it's an usize), which allows me to use Borrow like in the code below. I'm not considering something more general with types that are only cloneable.

The code it compiles to seems identical to a method that accepts respectively only T or &T, so it's well optimized, but I'm not convinced it's the best way to do it. Or even a good way to do it.

Note: I used U below to avoid any confusion with T in the title—here, T = usize. And my real use-case is of course a little more complex than that, so there's a little more code in from.

use std::borrow::Borrow;

pub struct Node<U> {
    value: U,
    children: Vec<usize>
}

impl<U, I> From<(U, I)> for Node<U>
where I: IntoIterator<Item: Borrow<usize>>    
{
    fn from((value, children): (U, I)) -> Self {
        Node {
            value,
            children: children.into_iter().map(|c| *c.borrow()).collect()
            //                                     ^^^^^^^^^^^ is it fine?
        }
    }
}

// Examples:
pub fn make_from_ref(value: String, ch: &[usize]) -> Node<String> {
    Node::from((value, ch))
}

pub fn make_from_owned(value: String, ch: Vec<usize>) -> Node<String> {
    Node::from((value, ch))
}

In some cases, I know it would be possible to define a custom trait and implement it for both T and &T, but in my case the implementations conflict because the difference is only in Item=usize / Item=&usize. Another solution, of course, is to implement two Node methods (so with different names). Either way, it's a little sad to have two copies of almost the same code.

What do you think? Is that good or bad, and is there a better solution?

2

For Copy types it's technically fine, but may be an unnecessary complication. Iterators have a .copied() adapter that converts &usize to usize.

This kind of abstraction over owned vs borrowed types can often be problematic and sometimes not even possible. This is because memory management of owned and borrowed types is different, and may need structurally different code. Not just one call here and there, but a different way of storing the data.

Borrowing in Rust isn't just a choice of storing by value vs storing by reference (like T vs Box<T>). It's a choice between unrestricted self-contained types, and temporary views that are always bound to a scope. These are semantically quite different, and Rust deliberately will never let you abstract away the fact that some type is limited to a temporary scope.

In this code .map() always destroys the c element (because into_iter() consumes the container, and c isn't saved anywhere else), so you couldn't keep references to whatever has been borrowed from inside c. And if you tried storing owned values instead of references, you couldn't either (without Copy/Clone), because borrow() doesn't let you keep the result as owned.

3 Likes
3

But I don't see how I'd define a bound that encompasses both usize and &usize. Or should I make a custom, fake trait that I implement for both types? I haven't tried that.

I'm only interested in storing owned values.

In the case of a Copy value, I don't see any destruction of the items:

  • if the items are references, the code will allocate a vector and copy the values in it. The result would be the same with a straightforward IntoIterator<Item = &T>.
  • if the items are owned in a vector that can be moved, like in the 2nd example, it simply moves the vector, even for user types that are Copy, so not only for usize. The result would be the same with IntoIterator<Item = T> or Vec<T>.
  • if the items are owned but in another iterable, then it has to copy them (again, like it would in another situation).

Borrow for a type T simply returns a reference to it, so the compiler sees *&c, and for &T, it sees *&**c (I'm not sure why there are two derefs of c instead of one, there). So I assume it's able to simplify that as well as in the "straightforward" case.

Conceptually, though, I agree it's a weird to use Borrow for that purpose.

4

For a trait bound, Borrow<usize> or AsRef<usize> should work. There are blanket impls for &T that work with AsRef<T>.

It's not possible to make a blanket trait impl for any T and &T, because it overlaps when T = &U (T doesn't mean non-reference, it's just unknown whether it is a reference or not). You can have blanket impl for &T and then individual impls for specific types that are not references.

5

I'm sorry but I really don't see how to make that work. If I keep the same bound with Borrow<usize>, I can't use copied because I don't have an explicit reference to a type. And I don't think AsRef is implemented for usize, but maybe I'm missing something.

6

I could do this, just to avoid using the Borrow concept.

// [...]

trait IntoUsize {
    fn into_usize(self) -> usize;
}

impl IntoUsize for usize {
    fn into_usize(self) -> usize { self }
}

impl IntoUsize for &usize {
    fn into_usize(self) -> usize { *self }
}

impl<U, I> From<(U, I)> for Node<U>
where
    I: IntoIterator<Item: IntoUsize>,
{
    fn from((value, children): (U, I)) -> Self {
        Node {
            value,
            children: children.into_iter().map(|c| c.into_usize()).collect(),
        }
    }
}

I think it can't be generalized to a blanket implementation because I see now way to avoid a conflict by saying "implement this for types that are references" and "implement this for types that aren't references" (I wish Rust had exclusion clauses). But if it's for one type only, it's manageable.

7

You can make your code accept usize and leave it to the caller to call .copied() or .cloned(). This is straightforward, friendly to type inference, and arguably better practice than hiding a clone inside your code (in the case where the element type is not Copy).

7 Likes
8

Thanks for clarifying, I was looking at the wrong end of the problem. :smiley:
I suppose I could do that, though the idea was precisely to avoid that complication.

Since the type is always Copy, we're in copy semantics and there won't be any clone operation.

9

Oh, I’m sorry; I misread your original post as saying that in your real case the T was not Copy.

10

I just wanted to boost this. If you're dealing in an iterator already, there's really no need to accept other things and convert yourself. People can just .copied() themselves to get you the usizes. TBH they should probably be doing that anyway, because slice.iter().copied().filter(...) is usually better than slice.iter().filter(...) anyway (when the element type is something trivial like usize).

If you're trying to accept both &[&str] and &[String], or something like that, where you need the heterogeneity because there's isn't a trivial conversion, then it might be worth doing something. But once it's an iterator already, there's no need for the extra hoops that just make inference work worse.

2 Likes
11

Sorry, I took the wrong post to indicate the solution earlier! It was late...

Nothing to be sorry for, especially after helping me understand! It's indeed quite particular so I should have stated that more clearly.

I don't think it needs further boosting with two others already advising that idea. :wink:

In theory for trivial cases, I would agree, but in this case, it's just second-guessing the OP.

To give more details: I've given a simplified version of the code for the sake of clarity. In the real code, those nodes are packed together with other data in arrays, and the conversion isn't that trivial. In some instances, the data are generated dynamically and are owned. In other instances, static data are generated in source code to rebuild the object (in a 2-staged compilation of a tool that either generates a part of its own code or generates source code for its user).

If From doesn't accept &usize, the "user" has to work around with multiple levels of into_iter / map to destructure the data, isolate each component, then change children's items to usize. It's not impossible, and the source code to do it can be generated, too, but I wanted to see if it was possible to avoid that.

Granted, the flexible solution requires some extra work by the compiler, but writing code that's simpler to compile shouldn't always be the driving factor, IMHO. It's those extra hoops that make the standard library easier to use for us.

Thanks all for your help! I'm not entirely sure yet on which side I'll cure the problem. Using copied could be interesting in other situations anyway, so it's useful advice. :slight_smile:

12

It looks similar with linked lists data structures. node should be in Vec<Node> :thinking: . I have watched someone they’ve do

struct Node{}

//and 

struct NodeI{}
// N : Node for test. and N:&Node for release
impl <borrow<N>> NodeI {}

edit:

    pub struct Node <U>{
        heading:U,
        content:Vec<usize>
    }

    
    impl<U> From <(U,Vec<usize>)> for Node<U> {
        fn from((heading,content): (U,Vec<usize>)) -> Self {
           Self {
               heading,
               content
           } 
        }
    }

fn main() {
    let mut node = Node{heading:"hello",content:vec![1,2,3,4]};
    let node2=Node::from(("hello",vec![1,2,3,4]));
    let arr = &[1,2,3,4][0..];
    let node3=Node::from(("hello",arr.into()));
    assert_eq!(node2.content,node3.content);
}

why don't you do this ?

13

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.