Implementation of Index and IndexMut that's not just a read

help
1

My goal is to implement an array of 8 booleans as an u8 (each bit of the u8 representing a boolean)

I would also like to use the bracket syntax (this is why I didn't use getters and setters), so I tried implementing the Index and IndexMut traits to my struct:

use std::ops::{Index, IndexMut};

struct Foo(u8);

impl Index<u8> for Foo {
    type Output = bool;

    fn index(&self, index: u8) -> &Self::Output {
        if index >= 8 {panic!("Index out of bounds!")}
        let mask = 1 << index;
        if (index & mask) != 0 {
            return &true;
        } else {
            return &false;
        }
    }
}

impl IndexMut<u8> for Foo {
    fn index_mut(&mut self, index: u8) -> &mut Self::Output {
        if index >= 8 {panic!("Index out of bounds!")}
        let mask = 1 << index;
        if (index & mask) != 0 {
            return &mut true;
        } else {
            return &mut false;
        }
    }
}

When I try to compile this code, Index works (but I feel like the &true is kind of a hack)

However, my implementation of IndexMut doesn't work, with the compiler saying that I tried to return a reference to a temporary value

I understand that my code is wrong (though I'm not sure about why Index worked), but is there a way to implement IndexMut that would do what I want ?

I feel like this should be possible, since otherwise all implementations of IndexMut would only be able to return fields of the current data structure, and AFAIK Vecs don't work like that (I tried reading Vec<T>'s implementation, but i didn't understood it)

2

Index works because true and false get promoted to static memory, and you return a reference to that. IndexMut can't work that way because you can't promote something to a mutable static (mutable statics are almost impossible to use soundly, much less allowable in safe code).

You can't directly return a &mut bool without storing it somewhere (or leaking it). There's no good way of doing what you want.

Implementations of IndexMut (and Index) are intended to work like that (to return data owned by the implementing type, it doesn't have to be a direct field). And Vecs does work like that (it owns an allocation of size_of(T) * capacity to store the Ts).

What would happen when you do this?

bitvec[3] = true;

That's something like

*IndexMut::index_mut(&mut bitvec, 3) = true;

How are you going to get that value into your u8 without presenting an invalid bool (which is UB) and without clobbering all 8 bits instead of just 1?

2 Likes
3

One workaround is to define a guard object that represents a single bit of the value and writes it into the proper place on drop():

use std::ops::{Deref, DerefMut};
use std::cell::Cell;

pub struct Foo(u8);

impl Foo {
    pub fn bits_mut(&mut self) -> [BitMut<'_>;8] {
        let parent = Cell::from_mut(&mut self.0);
        std::array::from_fn(|i| {
            let mask = 1u8 << i;
            BitMut { parent, mask, value: parent.get() & mask != 0 }
        })
    }
}

pub struct BitMut<'a> {
    mask: u8,
    parent: &'a Cell<u8>,
    value: bool
}

impl Deref for BitMut<'_> {
    type Target = bool;
    fn deref(&self)->&bool { &self.value }
}

impl DerefMut for BitMut<'_> {
    fn deref_mut(&mut self)->&mut bool { &mut self.value }
}

impl Drop for BitMut<'_> {
    fn drop(&mut self) {
        let &mut BitMut { mask, parent, value } = self;
        
        parent.set( match value {
            true => parent.get() | mask,
            false => parent.get() & !mask
        });
    }
}

fn main() {
    let mut x = Foo(0);
    {
        let mut bits = x.bits_mut();
        *bits[1] = true;
        *bits[3] = true;
        *bits[5] = true;
        *bits[7] = true;
    }
    
    eprintln!("0x{:x}", x.0);
}
2 Likes
4

Another alternative is to provide an update method that breaks the value apart into a [bool;_], calls a closure, and the puts it back together again:

pub struct Foo(u8);

impl Foo {
    pub fn update<O>(&mut self, f:impl FnOnce(&mut [bool;8])->O)->O {
        let mut bits = std::array::from_fn(|i| self.0 & (1<<i) != 0);
        let out = f(&mut bits);
        self.0 = 0;
        for (i,b) in bits.into_iter().enumerate() {
            if b { self.0 |= 1<<i }
        }
        out
    }
}

fn main() {
    let mut x = Foo(0);
    x.update(|bits| {
        bits[1] = true;
        bits[3] = true;
        bits[5] = true;
        bits[7] = true;
    });
    
    eprintln!("0x{:x}", x.0);
}

NB: It looks like the optimizer is pretty good at handling this version.

5

Why not just unpack the bools into an array in a BitsMut and impl Index and IndexMut on that struct instead? I think that would have basically the same performance characteristics[1] without requiring the explicit * for the assignment.

(the bit manipulation might not be 100% correct, I threw it together really fast)
Playground

use std::ops::{Index, IndexMut};

pub struct Foo(u8);

impl Foo {
    pub fn bits_mut(&mut self) -> BitsMut<'_> {
        let bits = std::array::from_fn(|i| {
            let mask = 1u8 << i;
            self.0 & mask != 0
        });
        BitsMut { bits, parent: self }
    }
}

pub struct BitsMut<'a> {
    bits: [bool; 8],
    parent: &'a mut Foo,
}

impl Index<usize> for BitsMut<'_> {
    type Output = bool;

    fn index(&self, index: usize) -> &Self::Output {
        &self.bits[index]
    }
}

impl IndexMut<usize> for BitsMut<'_> {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        &mut self.bits[index]
    }
}

impl Drop for BitsMut<'_> {
    fn drop(&mut self) {
        let BitsMut { parent, bits } = self;

        let value = bits
            .iter()
            .copied()
            .enumerate()
            .fold(0, |acc, (i, value)| acc | (if value { 1 } else { 0 } << i));
        parent.0 = value;
    }
}

fn main() {
    let mut x = Foo(0);
    {
        let mut bits = x.bits_mut();
        bits[1] = true;
        bits[3] = true;
        bits[5] = true;
        bits[7] = true;
    }

    eprintln!("0x{:x}", x.0);
}

  1. or possibly better since there's no interior mutability involved ↩ī¸Ž

1 Like
6

That makes a lot more sense than my original version, for many reasons. You can make it a bit more general by Derefing to [bool;8] instead of implementing Index... manually, so that you can use range indexing, iter_mut(), etc:

1 Like
7

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.