1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

//! Collection types which allows insertion of new values while shared references to its contents
//! are alive. This is done by storing each value in a stable memory location and preventing an
//! earlier inserted value to be overwritten.
use std::cell::{RefCell, Ref};
use std::collections::HashMap;
use std::fmt;
use std::hash::Hash;
use std::iter::{FromIterator, IntoIterator};
use std::ops::{Index, IndexMut};

// NOTE: transmute is used to circumvent the borrow checker in this module
// This is safe since the containers hold boxed values meaning allocating larger
// storage does not invalidate the references that are handed out and because values
// can only be inserted, never modified (this could be done with a Rc pointer as well but
// is not done for efficiency since it is not needed)

unsafe fn forget_lifetime<'a, 'b, T: ?Sized>(x: &'a T) -> &'b T {
    ::std::mem::transmute(x)
}

unsafe fn forget_lifetime_mut<'a, 'b, T: ?Sized>(x: &'a mut T) -> &'b mut T {
    ::std::mem::transmute(x)
}

// A mapping between K and V where once a value has been inserted it cannot be changed
// Through this and the fact the all values are stored as pointers it is possible to safely
// insert new values without invalidating pointers retrieved from it
pub struct FixedMap<K, V> {
    map: RefCell<HashMap<K, Box<V>>>,
}

impl<K: Eq + Hash, V> Default for FixedMap<K, V> {
    fn default() -> FixedMap<K, V> {
        FixedMap::new()
    }
}

impl<K: Eq + Hash + fmt::Debug, V: fmt::Debug> fmt::Debug for FixedMap<K, V> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        self.map.borrow().fmt(f)
    }
}

impl<K: Eq + Hash, V> FixedMap<K, V> {
    pub fn new() -> FixedMap<K, V> {
        FixedMap { map: RefCell::new(HashMap::new()) }
    }

    pub fn clear(&mut self) {
        self.map.borrow_mut().clear();
    }

    pub fn try_insert(&self, key: K, value: V) -> Result<(), (K, V)> {
        if self.get(&key).is_some() {
            Err((key, value))
        } else {
            self.map.borrow_mut().insert(key, Box::new(value));
            Ok(())
        }
    }

    pub fn len(&self) -> usize {
        self.map.borrow().len()
    }

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    pub fn get(&self, k: &K) -> Option<&V> {
        self.map
            .borrow()
            .get(k)
            .map(|x| unsafe { forget_lifetime(&**x) })
    }
}

#[derive(Debug)]
pub struct FixedVec<T> {
    vec: RefCell<Vec<Box<T>>>,
}

impl<T> FixedVec<T> {
    pub fn new() -> FixedVec<T> {
        FixedVec { vec: RefCell::new(Vec::new()) }
    }

    pub fn clear(&mut self) {
        self.vec.borrow_mut().clear();
    }

    pub fn push(&self, value: T) {
        self.vec.borrow_mut().push(Box::new(value))
    }

    #[allow(dead_code)]
    pub fn extend<I: Iterator<Item = T>>(&self, iter: I) {
        self.vec.borrow_mut().extend(iter.map(Box::new))
    }

    pub fn borrow(&self) -> Ref<Vec<Box<T>>> {
        self.vec.borrow()
    }

    pub fn find<F>(&self, mut test: F) -> Option<(usize, &T)>
        where F: FnMut(&T) -> bool
    {
        self.vec
            .borrow()
            .iter()
            .enumerate()
            .find(|&(_, boxed)| test(&**boxed))
            .map(|(i, boxed)| (i, unsafe { forget_lifetime(&**boxed) }))
    }

    pub fn len(&self) -> usize {
        self.vec.borrow().len()
    }

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
}

impl<T> Index<usize> for FixedVec<T> {
    type Output = T;
    fn index(&self, index: usize) -> &T {
        let vec = self.vec.borrow();
        let result = &*vec[index];
        unsafe { forget_lifetime(result) }
    }
}

impl<T> IndexMut<usize> for FixedVec<T> {
    fn index_mut(&mut self, index: usize) -> &mut T {
        let mut vec = self.vec.borrow_mut();
        let result = &mut *vec[index];
        unsafe { forget_lifetime_mut(result) }
    }
}

impl<A> FromIterator<A> for FixedVec<A> {
    fn from_iter<T: IntoIterator<Item = A>>(iterator: T) -> FixedVec<A> {
        let vec: Vec<_> = iterator.into_iter().map(Box::new).collect();
        FixedVec { vec: RefCell::new(vec) }
    }
}