"Mutability polymorphism"

[glaebhoerl]

It would be desirable to, at some point, grow the ability to abstract over the "mutability" of reference types. Currently, it is frequently the case that one must write separate "getter" methods for shared & and unique &mut references, even though the bodies of these methods are exactly the same. This is especially bothersome when those method bodies are nontrivial.

See an earlier discussion on reddit here.

Ideas for accomplishing this could potentially be borrowed from the research mentioned in this presentation, as well as from the Disciple language (a language with region types, effect types (e.g. mutation involving a region), and polymorphism over both).

This could also potentially allow the Fn/FnMut/FnOnce, Deref/DerefMut, Index/IndexMut, and so forth hierarchies to be collapsed into single traits parameterized over capabilities / effects / constraints (whatever we choose to call them).

[blaenk]

Yeah, this would be very useful I think.

[thehydroimpulse]

/cc me

[reem]

It would be even better if we could abstract over ownership status, i.e. we could collapse Trait[Mut|Move]? into just Trait.

[brendanzab]

This would be great. Do you have any thoughts on how this could be added in a backwards compatible way in the future?

[reem]

Not really. I think this deserves consideration pre-1.0 because it would collapse and change traits which are lang items, such as the Deref, Fn and Index families. Code that implemented those traits would be broken.

Parametrizing over mutability is much easier than parametrizing over ownership, since you can just say "if you have &m? T you can only treat it like &T", but the story with owned? T becomes trickier.*

* note all syntax is super hypothetical

[glaebhoerl]

Yeah, figuring out how to abstract over out and move is much less obvious than mut and shared. Possibly we would have to take a capability-based perspective on it (see that presentation, particularly the part about strong updates), i.e. currently Rust's references are pointers bundled together with the capabilities to access them; maybe taking them separately and, possibly, having traits on capabilities or something might lead us in the right direction... but this is extremely hazy and hand-wavy for now.

[Gankra]

@reem I don't think it's as easy as that. &T is often less restrictive, in that much more general code structures are valid with & and than &mut. You can make multiple &'s, and &mut's often necessitate temporary wrangling to appease borrowck (although this may simply be a SESE artifact).

You would have to assume that your ptrs are &mut's in some regards, and &'s in others. Of course, in a hypothetical polymorphic mutability world many of the restrictions that & provides would be swept away by virtue of presumably all getters being polymorphic and "just working".

[crlf0710]

This can be implemented with GAT, as type family pointers.

[mrahhal]

There hasn't been any activity on this for a long time. I've been thinking about this a lot for the past few days, didn't know there's an rfc for it. It seems there's just not enough interest in this? I'm a new user of Rust and this has been one of the major pain points so far. (Simple use case is writing a visitor pattern that needs to be either & or &mut, with the exact same code otherwise. Currently trying to duplicate this using a proc macro)

[dullbananas]

This could be done with a ~~&mut:M~~ &:M syntax where M is a constant boolean

Example:

struct Thing(u8);

impl Thing {
    fn get_inner<const M: bool>(&:M self) -> &:M u8 {
        &:M self.0
    }
}

I can't believe there hasn't been a proposed syntax for 8 years!

[vimirage]

This could be done with a &mut:M syntax where M is a constant boolean

I don't believe that syntax is the real blocker here. Although, what is the blocker? Interest?

[programmerjake]

there's https://github.com/rust-lang/keyword-generics-initiative which iirc is also thinking about being generic over mutability

[qbolec]

I was facing this problem when implementing a terenary tree, which had a lot of various access methods, and each of them had to be provided in foo() and foo_mut() flavors, which was a lot of copy&paste. In this context (having tens of functions, not just two) it might be worth investing in developing an abstract "wrapper", such as the following, which you only have to do once, but then it pays of in that every access method, such as find can be implement just once as a generic find_gen. (I am new to Rust, so please forgive me if this code is buggy, or the idea was already discussed elsewhere.)

// This is just a simple example of data container, for this demo, let it be a binary tree, 
// which maps i32 keys to i32 values
type Tree = Option<Box<Node>>;

struct Node {
    key: i32,
    val: i32,
    left: Tree,
    right: Tree,
}

// This function is not an important part of the demo, it's just, 
// so that I can create a non-empty tree easily. 
// This one is not generic, but it doesn't have to be, as it is inherently 
// mutating the tree, so we only have one variant anyway. 
fn insert(tree:&mut Tree, key: i32, val: i32){
    match tree {
        None => {
            *tree = Some(Box::new(Node{key,val, left:None, right:None}));
        },
        Some(boxed) => {
            let ref mut node = *boxed;
            if node.key == key {
                node.val = val;
            } else if node.key < key {
                insert(&mut node.right,key, val)
            } else {
                insert(&mut node.left,key, val)
            }
        }
    };
}

// The following two are specific to the binary tree data structure. 
// You'd have to define something like that for your data structure yourself. 
// The main idea here is to expose methods which let you access all fields of individual fragment
// of the data structure and thus navigate the structure "locally".
// You'd need as many of them, as there are various types inside your data structure.
// Perhaps I could avoid having treating Tree as a concept separate from Node and thus eliminate AbstractTreeRef
// if I used Option<(left,right,key,val)>?
// But, I think having 2 traits here is good for demonstration purposes of the general idea: one AbstractXRef
// for any X in your data structure.
// Note that the bounds must tie all the Xes in your data structure together, 
// for example note the `NR=Self`. 
// The `V` is the main point of this whole abstrction as it defines how the values will be 
// accessed (by & or by &mut?).
// In my case key is always referenced using shared ref, as I never mutate the key even in foo_mut() variants.
// In general, if you want to mutate more fields, then you need more Vs.
// Note that the unwrap uses `self`, so it consumes the reference, so you can call it only once.
// But, this shouldn't be the problem, because unwrap() simply "explodes" the big reference into many smaller to
// individual "parts" you need.
// If your algorithm is recursive, doing some "local operations" before and recursive calls, 
// then this approach should be good enough.

trait AbstractNodeRef<'a> {
    type V;
    type TR : AbstractTreeRef<'a, V=Self::V, NR=Self>;
    fn unwrap(self) -> (Self::TR,Self::TR,&'a i32,Self::V);
}

trait AbstractTreeRef<'a> {
    type V;
    type NR: AbstractNodeRef<'a, V=Self::V,TR=Self>;
    fn unwrap(self) -> Option<Self::NR>;
}


// Now you have to define how the "local access" methods should be implemented 
// for each X in your data structure and for each kind of reference (& and &mut)

// Implementations for &
 
// Implementation for & Tree
impl<'a> AbstractTreeRef<'a> for &'a Tree {
    type V=&'a i32;
    type NR= &'a Node;
    fn unwrap(self) -> Option<Self::NR> {
        match self {
            None => None,
            Some(boxed_node) => Some(& *boxed_node),
        }
    }
}

// Implementation for & Node
impl<'a> AbstractNodeRef<'a> for &'a Node {
    type V = &'a i32;
    type TR = &'a Tree; 
    fn unwrap(self) -> (Self::TR,Self::TR,&'a i32,Self::V) {
        (&self.left,&self.right,&self.key,&self.val)
    }
}

// Implementations for &mut

// Implementation for &mut Tree
impl<'a> AbstractTreeRef<'a> for &'a mut Tree {
    type V=&'a mut i32;
    type NR= &'a mut Node;
    fn unwrap(self) -> Option<Self::NR> {
        match self.as_mut() {
            None => None,
            Some(boxed_node) => Some(&mut *boxed_node),
        }
    }
}
// Implementation for &mut Node
impl<'a> AbstractNodeRef<'a> for &'a mut Node {
    type V = &'a mut i32;
    type TR = &'a mut Tree; 
    fn unwrap(self) -> (Self::TR,Self::TR,&'a i32,Self::V) {
        (&mut self.left, &mut self.right,&self.key,&mut self.val)
    }
}

// Phew... After this initial investment, you can now write your generic access methods!

fn find_gen<'a,T>(tree:T,sought_key:i32) -> Option<T::V>
where T:AbstractTreeRef<'a>{
    match tree.unwrap() {
        None => None,
        Some(node) => {
            let (left,right,key,val) = node.unwrap();
            if key == &sought_key {
                Some(val)
            } else if key < &sought_key {
                find_gen::<T>(right, sought_key)
            } else {
                find_gen::<T>(left, sought_key)
            }
        }
    }    
}

fn in_order_gen<'a,T,C>(tree:T, visitor:&mut C) 
where T:AbstractTreeRef<'a>,
C: FnMut(&i32, T::V) {
    match tree.unwrap() {
        None => {},
        Some(node) => {
            let (left,right,key,val) = node.unwrap();
            in_order_gen::<T,C>(left, visitor);
            visitor(key, val);
            in_order_gen::<T,C>(right, visitor);
        }
    }   
}

// same for post_order, pre_order, etc.

// Now lets see how it looks in action!
fn main() {
    let mut root : Tree = None;
    insert(&mut root,0,3);
    insert(&mut root,1,10);
    insert(&mut root,-1,-10);
    insert(&mut root,0,0);
    println!("-1 is mapped to {:?}", find_gen(&root, -1));
    println!("12 is mapped to {:?}", find_gen(&root, 12));
    in_order_gen(&root,&mut |key,val| {
        println!("{:?} -> {:?}", key, val)
    });
    *find_gen(&mut root, -1).unwrap() = -4;
    println!("-1 is mapped to {:?}",find_gen(&root, -1));
    in_order_gen(&mut root,&mut |_key,val| {
        *val = *val + 100;
    });
    println!("-1 is mapped to {:?}",find_gen(&root, -1));
}

This seems to work:

$ cargo run
   Compiling abstract-ref v0.1.0 (C:\dev\rust\abstract-ref)
    Finished dev [unoptimized + debuginfo] target(s) in 3.05s
     Running `target\debug\abstract-ref.exe`
-1 is mapped to Some(-10)
12 is mapped to None
-1 -> -10
0 -> 0
1 -> 10
-1 is mapped to Some(-4)
-1 is mapped to Some(96)

I think, I saw something similar in the Category Theory lecture, where there were "destructors" or maybe "lenses" ? Anyway, the main idea here is to have a parallel universe of "abstract references to X" for all Xes in your data structure, and explain how such references can be decomposed into references to smaller parts. This in turn lets you specify "local" navigation/step of recursive algorithms in generic way.

[alexpyattaev]

This crate does address this to some extent https://docs.rs/duplicate/latest/duplicate/ Though one has to admit this is a bit of a hack. But also a perfect use case for macros.