DRYing nearly identical implementations for &T and &mut T


#1

When writing data structures or helpers (like iterators), I find myself writing almost identical code for &Tand &mut T in straightforward cases (when wrapping another data structure, for example) and I find the current state to be a bit dissatisfying.

I’ve asked related questions about it before —

  • one based on implementing basic data structures (inspired by Gankro’s too-many-linked-lists tutorial) with a lot of near-repetitions, and
  • another about avoiding unnecessary monomorphizations with an interesting answer by brson on his attempts to reduce code bloat when rust code would result in identical machine code.

So avoiding duplication has two aspects: (1) DRYing out the code (first question post above; macros can help with that), and (2) resulting in exactly one binary monomorphization (@brson’s abandoned approach in the second post above might help with that).

The first post mentions a straightforward doubly-linked-list implementation, with

(and other kinds of near-duplication as well, but I’d like to focus on mutability.)

In the cases where it is possible, I would just love to just define IterMut with all its more stringent constraints and tell the compiler to allow it to be interpreted as an Iter as well because its implementation is (almost) identical. Essentially, what I want is to parametrize & vs &mut, write the code once, and generate identical code – kinda what we do when parametrizing by lifetime.
(Implicit in my assumption is that &T and &mut T have the same binary representation, but I may be very, very wrong since transmuting the former to the latter is undefined behavior, though it’s not obvious to me whether that’s due to correctness checking or something else in the binary.)

Is there some reason that this should not be possible?


Does rust really need higher kinded types?
#2

I wonder if it’s a good idea to be able to do this in the general case, since the semantics of an immutable borrow are totally different from a mutable one.

Aside from the issue of monomorphization, couldn’t you solve this problem by generating the method body from a macro?


#3

Both & and &mut are type constructors, so I don’t think the comparison to parameterizing over lifetimes (i.e., type variables) holds up. Sounds like you want higher kinded polymorphism to me.


#4

I wouldn’t say they are totally different – &mut T is an unaliasable pointer, whereas &T is an aliasable one and can be treated as a sub-type of the former (as one can produce the latter from the former). In various simple cases of traversing a data structure in many different ways (of which I have plenty), one only needs to ensure that the more stringent needs of &mut T are met.

Yes, indeed, macros would DRY this; I was wondering both problems could be addressed at once.

Boo, you’re totally right. But HK polymorphism would have to deal with specifying whether arbitrary type constructors can potentially put a type parameter in either & or &mut context. So there is the semi-orthogonal problem of indicating that the more stringent &mut constraints should apply for analysis in a specific scenario while the same code should allow both. This is special case because the monomorphization is identical (again, unless I am mistaken about the representation of &mut) and it’s really common for iterators. I don’t see why this couldn’t addressed earlier. For example, D does something similar using the inout keyword, though it’s focus is on mutability rather than reference aliasability.


#5

There is a clear case with closures where an immutable closure should be accepted everywhere you expect a mutable closure as an argument (but it is not currently). Its different from normal data, as you cannot directly write to the mutable struct, it is only written from the ‘enclosed’ function. This would seem easily fixed by implementing the FnMut trait for immutable closures. Generalising this I think If something is a mutable object accessed through an interface, then an immutable object that implements the same interface would be acceptable in place of the mutable one, providing all access is through the functions in the interface.

If there was a ‘single borrow immutable’ type it would be possible to pass both immutable and mutable references to arguments of this kind.

For me personally macros are not a solution, as they are manipulating the syntax of the program. In my opinion we should be able to write any generic function without resorting to the ‘text cut and paste’ of macros.

If you are interested in Generic programming, I recommend reading “Elements of Programming” by Alexander Stepanov (its about C++, but its relevant to all generic programming).


#6

Isn’t this the case already? The list of FnMut implementors includes Fn.

Edit: that’s for &F where F: Fn, but the direct Fn declaration is also pub trait Fn<Args>: FnMut<Args>.


#7

If the closure mutates some internal state it has to be passed by mutable reference which is where the problem is. I need to have:

fn f<R, A>(relation : &mut R, a : &A, b : &B) -> bool
where R : FnMut(&A, &A) -> bool) {
    relation(a, b) && relation(b, a)
}

So that I can pass a closure that mutates its internal state (for example memoises every time it is used in an internal hash table to facilitate faster evaluation), but ‘f’ does not directly mutate the closure, so I could equally well pass an immutable closure, but at the moment I would have to pass a mutable reference to the immutable closure, which prevents passing the same reference more than once (unless I use a RefCel).


#8

… then it’s not an immutable closure, unless you hide that in RefCell as you mention.

“Directly” doesn’t make sense - f mutates the closure by calling it. If f calls a mutable closure, then that will (potentially) mutate things, so this must not be aliasable.

Again, it’s not an immutable closure unless you hide that mutability. Preventing multiple mutable references is one of Rust’s primary purposes!


#9

One of Rusts primary purpose is to prevent unsafe code. Preventing multiple mutable references is a means to an end (safety). If there is a class of multiple mutable reference that is safe, then there is no reason not to allow it, providing the safety checker can distinguish the cases in the type system. Can you post an example where multiple mutable references to a closure can cause a problem?


#11

Things like RefCell or Mutex are how you represent safe mutable sharing to the type system.

Well, you mentioned memoization. Suppose your closure returns a reference to a value that you memoized. The lifetime of that reference will extend the borrow of the closure’s reference. But if you had a separate closure reference, that would be allowed to be called separately, and perhaps memoize a new value which ends up reallocating your container – invalidating the first value you had returned.

Or maybe you don’t return references, but your two closure references get sent to separate threads and called simultaneously. They both try to memoize new values, clobbering each other in updating the container at the same time.


#12

@cuviper I think you’ve misunderstood what @keean wants. @keean wants to use Fn::call for Fn types and FnMut::call_mut for FnMut types. There is no shared mutability going on here, @keean wants an abstraction that could collapse these two functions into one.

fn f<R, A>(relation : &R, a : &A, b : &A) -> bool
where R : Fn(&A, &A) -> bool {
    relation(a, b) && relation(b, a)
}

fn f_mut<R, A>(relation : &mut R, a : &A, b : &A) -> bool
where R : FnMut(&A, &A) -> bool {
    relation(a, b) && relation(b, a)
}

This is a perfectly reasonable thing to want, but unfortunately it’s not possible in Rust’s current type system.


#13

If you change that function to take a direct FnMut, then you can use any FnMut, &mut FnMut, or &Fn.

fn f_mut<R, A>(mut relation : R, a : &A, b : &A) -> bool
where R : FnMut(&A, &A) -> bool {
    relation(a, b) && relation(b, a)
}

fn main() {
    let closure = |a: &i32, b: &i32| a == b;
    let r1 = &closure;
    let r2 = &closure;
    println!("{}", f_mut(r1, &10, &10));  // first shared &Fn
    println!("{}", f_mut(r2, &10, &100)); // second shared &Fn
    
    let mut x = 0;
    let mut mut_closure = |a: &i32, b: &i32| {x = *a; a == b};
    println!("{}", f_mut(&mut mut_closure, &10, &10)); // &mut FnMut
    println!("{}", f_mut(mut_closure, &10, &100)); // FnMut
}

#14

That works okay until you want to pass the closure as an argument to multiple functions generically, for example:

    pub fn partitioned<I, P>(f : I, l : &I, p : &mut P) -> bool
    where I : Iterator + Readable, P : FnMut(&I::value_type) -> bool {
        let g = find_if(f, l, p);
        *l == find_if_not(g, l, p)
    }

#15

Doesn’t this work?

    pub fn partitioned<I, P>(f : I, l : &I, mut p : P) -> bool
    where I : Iterator + Readable, P : FnMut(&I::value_type) -> bool {
        let g = find_if(f, l, &mut p);
        *l == find_if_not(g, l, p)
    }

#16

But that means find_if would have a different signature to the other functions, as this is part of a library find_if and find_if_not and partitioned all need to have a consistent interface and take functions in the same way, as they could all be used in the same context that find_if is in this example. That means if one takes a mutable reference then they all need to take mutable references.

At the moment the best option seems to be to have all the functions taking a mutable reference for closure/function arguments, and require the user to use a RefCel to pass the same closure multiple times to the same function. Whilst this will work, I don’ think its as good as it could be. There are many cases where it is safe to pass the same mutable reference twice. The simple test is if you unify the two variables you want to pass the same mutable reference too, and they function still passes the borrow checker, then it is safe to pass the same mutable reference to both of them. You could certify such functions with a special trait to tell the borrow checker it is safe to do so.


#17

All of your functions can take FnMut, and the caller can use any FnMut, &mut FnMut, or &Fn.

If you really want the function to take &mut FnMut, then you can also pass in &mut &Fn.


#18

Ah, okay thats a lot better, it seems much more generic now.


#19

I was trying to understand which arguments can be passed with which types. It seems that you can pass a reference or a mutable reference where the function expects to take ownership, which seems better than I thought for writing generic functions. However this seems to behave strangely with traits. For example if I have a function with a type that must implement AddAssign I can no longer easily pass an &mut instead of letting it take ownership. How can I use traits generically over move and borrow?


#20

Sort of, as long as you realized it’s taking ownership of the reference itself, not the referenced object. It works in this case because the reference itself implements the trait that you require. You can see something similar with IntoIterator::into_iter(self) – it takes a value, but the implementations for values of Vec<T>, &Vec<T>, and &mut Vec<T> are all very different.


#21

In this case, AddAssign is not implemented for references. You can still require it by reference in your function, there’s just not an easy way to accept the parameter both ways, by reference or value.

fn my_add_assign<X: AddAssign<Y>, Y>(x: &mut X, y: Y) { *x += y; }