Rust ownership for pushing to a vector whose members are referenced

Question

TL;DR: I want a vector of immutable elements that allows for short-lived immutable references to its members, while being able to push to it.

I'm making a crate for exact arithmetic to be used as drop-in replacements for floats. As such, it should implement Copy. Since expressions are recursive, I've had a look at this blog post that puts recursion levels in a Vec.

enum ExprData{
  Val(u32),
  Const{ch: char, f64: f64},
  Sum(Vec<(u32, ExprRef)>)
}

#[derive(Clone, Copy)] // actually had to implement Clone myself, 
struct FieldRef<'a> {  // otherwise it'd clone the Field 
  index: usize,        // or complain that Field is not Copy
  field: &'a Field
}

#[derive(Clone, Copy)]
enum ExprRef<'a> {
  Val(FieldRef<'a>)
  Const(FieldRef<'a>)
  Sum(FieldRef<'a>)
}

struct Field {
  members: SpecialContainer<ExprData>,
}

impl Field {
  fn parse(input: &str) {
    assert_eq(input, "π+1")
    self.maybe_add(ExprData::Const{char: 'π',f64: f64::consts::PI})
    self.maybe_add(ExprData::Val(1))
    self.maybe_add(ExprData::Sum(vec![(1,ExprRef::Const{FieldRef{field: &self, index: 0}}),(1,ExprRef::Val{FieldRef{field: &self, index: 1}})]))
    ExprRef::Sum{FieldRef{field: &self, index: 2}}
  }

  fn maybe_add(data: ExprData) -> usize {
    match self.members.position(data) { // <-- This requires equality, which is best with
      Some(p) => p,                     //     immutable references, cloning the vectors is
      None => {                         //     highly inefficient
        self.members.push(data) // <-- THIS IS THE CULPRIT
        self.members.len()-1
      }
    }
  }
}

fn main () {
  // Field: []
  let pi_one: ExprRef = f.parse("π+1"); //
  // Field: [π, 1, 1+π]
  let two_pi_one = pi_one + pi_one;
  // collect_like_terms([f.get_sum(pi_one),f.get_sum(pi_one)].concat())
  // [1+π] + [1+π] -> [(1,1),(1,π),(1,1),(1,π)] -collect terms-> [(2,1),(2,π)]
  // field.maybe_add(ExprData::Sum([(2,1),(2,π)])
  // Field: [π, 1, 1+π, 2+2π]
}

let me re-iterate: the elements in the SpecialContainer are immutable and I'll onle push to them. I want to use references to avoid cloning (possibly long) vectors of sums for equality.

Now, I've thought of the following options:

• Vec<OnceCell<ExprData>> <- This doesn't allow for pushing, since pushing may move data
• HashSet<ExprData> <- this doesn't allow for inserting, not sure if it moves data if it exceeds capacity.
• RefCell<Vec<ExprData>> <- This requires cloning of ExprData on every access
• LinkedList<[OnceCell<ExprData>; CHUNK_SIZE]> <- this would work, but LinkedList append still requires a mutable reference to the list and thus also to its members, even though pushing doesn't move the underlying data.
• AppendList<ExprData> <- There's a lot of magic here, but it does what I want
• something with Cow?

similar but not the same: this

Answer 1

RTFD: RefCell implements map() to return a Ref to the underlying part of the data. Since you said:

let me re-iterate: the elements in the SpecialContainer are immutable and I'll onle push to them. I want to use references to avoid cloning (possibly long) vectors of sums for equality.

I assume you'll be checking your usage at runtime. Thus, returning a Ref<ExprData> and maybe using clone() if mutability is needed is what you want:

impl Field {
  pub fn maybe_add(t: ExprData) -> usize {
    let index: Option<usize> ;
    // notice the scoping
    {
      index = self.members.borrow().iter().position(|a_t| *a_t == t)
    }
    match index {
      Some(i) => i,
      None => {
        v.borrow_mut().push(t);
        v.borrow().len()-1
      }
    }
  }

  pub fn get_data(&self, r: FieldRef) -> Ref<ExprData> {
    // match statement omitted
    Ref::map(self.members.borrow(), |v| v[r.index])
  }
}

impl Eq for ExprRef {
  fn eq(&self, other: &Self) {
    // dereference to compare inner values
    *self.field().get_data() == *other.field().get_data()
  }
}

impl Add for ExprRef {
  type Output = Self;
  fn add(&self, rhs: Self) -> Self {
    // do something smart with self.field().get_data().clone()
  }
}

Also this question was a duplicate of what you said.