aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_arena
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ra_arena')
-rw-r--r--crates/ra_arena/src/lib.rs101
-rw-r--r--crates/ra_arena/src/map.rs32
2 files changed, 79 insertions, 54 deletions
diff --git a/crates/ra_arena/src/lib.rs b/crates/ra_arena/src/lib.rs
index fc0f7c12f..ea98d5444 100644
--- a/crates/ra_arena/src/lib.rs
+++ b/crates/ra_arena/src/lib.rs
@@ -2,6 +2,7 @@
2 2
3use std::{ 3use std::{
4 fmt, 4 fmt,
5 hash::{Hash, Hasher},
5 iter::FromIterator, 6 iter::FromIterator,
6 marker::PhantomData, 7 marker::PhantomData,
7 ops::{Index, IndexMut}, 8 ops::{Index, IndexMut},
@@ -36,86 +37,110 @@ impl fmt::Display for RawId {
36 } 37 }
37} 38}
38 39
39#[derive(Clone, PartialEq, Eq)] 40pub struct Idx<T> {
40pub struct Arena<ID, T> { 41 raw: RawId,
41 data: Vec<T>, 42 _ty: PhantomData<fn() -> T>,
42 _ty: PhantomData<ID>,
43} 43}
44 44
45impl<ID: ArenaId, T: fmt::Debug> fmt::Debug for Arena<ID, T> { 45impl<T> Clone for Idx<T> {
46 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { 46 fn clone(&self) -> Self {
47 fmt.debug_struct("Arena").field("len", &self.len()).field("data", &self.data).finish() 47 *self
48 } 48 }
49} 49}
50impl<T> Copy for Idx<T> {}
50 51
51#[macro_export] 52impl<T> PartialEq for Idx<T> {
52macro_rules! impl_arena_id { 53 fn eq(&self, other: &Idx<T>) -> bool {
53 ($name:ident) => { 54 self.raw == other.raw
54 impl $crate::ArenaId for $name { 55 }
55 fn from_raw(raw: $crate::RawId) -> Self { 56}
56 $name(raw) 57impl<T> Eq for Idx<T> {}
57 } 58
58 fn into_raw(self) -> $crate::RawId { 59impl<T> Hash for Idx<T> {
59 self.0 60 fn hash<H: Hasher>(&self, state: &mut H) {
60 } 61 self.raw.hash(state)
62 }
63}
64
65impl<T> fmt::Debug for Idx<T> {
66 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
67 let mut type_name = std::any::type_name::<T>();
68 if let Some(idx) = type_name.rfind(':') {
69 type_name = &type_name[idx + 1..]
61 } 70 }
62 }; 71 write!(f, "Idx::<{}>({})", type_name, self.raw)
72 }
63} 73}
64 74
65pub trait ArenaId { 75impl<T> Idx<T> {
66 fn from_raw(raw: RawId) -> Self; 76 pub fn from_raw(raw: RawId) -> Self {
67 fn into_raw(self) -> RawId; 77 Idx { raw, _ty: PhantomData }
78 }
79 pub fn into_raw(self) -> RawId {
80 self.raw
81 }
82}
83
84#[derive(Clone, PartialEq, Eq)]
85pub struct Arena<T> {
86 data: Vec<T>,
68} 87}
69 88
70impl<ID, T> Arena<ID, T> { 89impl<T: fmt::Debug> fmt::Debug for Arena<T> {
71 pub const fn new() -> Arena<ID, T> { 90 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
72 Arena { data: Vec::new(), _ty: PhantomData } 91 fmt.debug_struct("Arena").field("len", &self.len()).field("data", &self.data).finish()
73 } 92 }
74} 93}
75 94
76impl<ID: ArenaId, T> Arena<ID, T> { 95impl<T> Arena<T> {
96 pub const fn new() -> Arena<T> {
97 Arena { data: Vec::new() }
98 }
99
77 pub fn len(&self) -> usize { 100 pub fn len(&self) -> usize {
78 self.data.len() 101 self.data.len()
79 } 102 }
80 pub fn is_empty(&self) -> bool { 103 pub fn is_empty(&self) -> bool {
81 self.data.is_empty() 104 self.data.is_empty()
82 } 105 }
83 pub fn alloc(&mut self, value: T) -> ID { 106 pub fn alloc(&mut self, value: T) -> Idx<T> {
84 let id = RawId(self.data.len() as u32); 107 let id = RawId(self.data.len() as u32);
85 self.data.push(value); 108 self.data.push(value);
86 ID::from_raw(id) 109 Idx::from_raw(id)
87 } 110 }
88 pub fn iter(&self) -> impl Iterator<Item = (ID, &T)> + ExactSizeIterator + DoubleEndedIterator { 111 pub fn iter(
89 self.data.iter().enumerate().map(|(idx, value)| (ID::from_raw(RawId(idx as u32)), value)) 112 &self,
113 ) -> impl Iterator<Item = (Idx<T>, &T)> + ExactSizeIterator + DoubleEndedIterator {
114 self.data.iter().enumerate().map(|(idx, value)| (Idx::from_raw(RawId(idx as u32)), value))
90 } 115 }
91} 116}
92 117
93impl<ID: ArenaId, T> Default for Arena<ID, T> { 118impl<T> Default for Arena<T> {
94 fn default() -> Arena<ID, T> { 119 fn default() -> Arena<T> {
95 Arena { data: Vec::new(), _ty: PhantomData } 120 Arena { data: Vec::new() }
96 } 121 }
97} 122}
98 123
99impl<ID: ArenaId, T> Index<ID> for Arena<ID, T> { 124impl<T> Index<Idx<T>> for Arena<T> {
100 type Output = T; 125 type Output = T;
101 fn index(&self, idx: ID) -> &T { 126 fn index(&self, idx: Idx<T>) -> &T {
102 let idx = idx.into_raw().0 as usize; 127 let idx = idx.into_raw().0 as usize;
103 &self.data[idx] 128 &self.data[idx]
104 } 129 }
105} 130}
106 131
107impl<ID: ArenaId, T> IndexMut<ID> for Arena<ID, T> { 132impl<T> IndexMut<Idx<T>> for Arena<T> {
108 fn index_mut(&mut self, idx: ID) -> &mut T { 133 fn index_mut(&mut self, idx: Idx<T>) -> &mut T {
109 let idx = idx.into_raw().0 as usize; 134 let idx = idx.into_raw().0 as usize;
110 &mut self.data[idx] 135 &mut self.data[idx]
111 } 136 }
112} 137}
113 138
114impl<ID: ArenaId, T> FromIterator<T> for Arena<ID, T> { 139impl<T> FromIterator<T> for Arena<T> {
115 fn from_iter<I>(iter: I) -> Self 140 fn from_iter<I>(iter: I) -> Self
116 where 141 where
117 I: IntoIterator<Item = T>, 142 I: IntoIterator<Item = T>,
118 { 143 {
119 Arena { data: Vec::from_iter(iter), _ty: PhantomData } 144 Arena { data: Vec::from_iter(iter) }
120 } 145 }
121} 146}
diff --git a/crates/ra_arena/src/map.rs b/crates/ra_arena/src/map.rs
index b73d4e365..5e764113d 100644
--- a/crates/ra_arena/src/map.rs
+++ b/crates/ra_arena/src/map.rs
@@ -2,17 +2,17 @@
2 2
3use std::marker::PhantomData; 3use std::marker::PhantomData;
4 4
5use super::ArenaId; 5use crate::Idx;
6 6
7/// A map from arena IDs to some other type. Space requirement is O(highest ID). 7/// A map from arena IDs to some other type. Space requirement is O(highest ID).
8#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] 8#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
9pub struct ArenaMap<ID, T> { 9pub struct ArenaMap<ID, V> {
10 v: Vec<Option<T>>, 10 v: Vec<Option<V>>,
11 _ty: PhantomData<ID>, 11 _ty: PhantomData<ID>,
12} 12}
13 13
14impl<ID: ArenaId, T> ArenaMap<ID, T> { 14impl<T, V> ArenaMap<Idx<T>, V> {
15 pub fn insert(&mut self, id: ID, t: T) { 15 pub fn insert(&mut self, id: Idx<T>, t: V) {
16 let idx = Self::to_idx(id); 16 let idx = Self::to_idx(id);
17 if self.v.capacity() <= idx { 17 if self.v.capacity() <= idx {
18 self.v.reserve(idx + 1 - self.v.capacity()); 18 self.v.reserve(idx + 1 - self.v.capacity());
@@ -25,43 +25,43 @@ impl<ID: ArenaId, T> ArenaMap<ID, T> {
25 self.v[idx] = Some(t); 25 self.v[idx] = Some(t);
26 } 26 }
27 27
28 pub fn get(&self, id: ID) -> Option<&T> { 28 pub fn get(&self, id: Idx<T>) -> Option<&V> {
29 self.v.get(Self::to_idx(id)).and_then(|it| it.as_ref()) 29 self.v.get(Self::to_idx(id)).and_then(|it| it.as_ref())
30 } 30 }
31 31
32 pub fn get_mut(&mut self, id: ID) -> Option<&mut T> { 32 pub fn get_mut(&mut self, id: Idx<T>) -> Option<&mut V> {
33 self.v.get_mut(Self::to_idx(id)).and_then(|it| it.as_mut()) 33 self.v.get_mut(Self::to_idx(id)).and_then(|it| it.as_mut())
34 } 34 }
35 35
36 pub fn values(&self) -> impl Iterator<Item = &T> { 36 pub fn values(&self) -> impl Iterator<Item = &V> {
37 self.v.iter().filter_map(|o| o.as_ref()) 37 self.v.iter().filter_map(|o| o.as_ref())
38 } 38 }
39 39
40 pub fn values_mut(&mut self) -> impl Iterator<Item = &mut T> { 40 pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> {
41 self.v.iter_mut().filter_map(|o| o.as_mut()) 41 self.v.iter_mut().filter_map(|o| o.as_mut())
42 } 42 }
43 43
44 pub fn iter(&self) -> impl Iterator<Item = (ID, &T)> { 44 pub fn iter(&self) -> impl Iterator<Item = (Idx<T>, &V)> {
45 self.v.iter().enumerate().filter_map(|(idx, o)| Some((Self::from_idx(idx), o.as_ref()?))) 45 self.v.iter().enumerate().filter_map(|(idx, o)| Some((Self::from_idx(idx), o.as_ref()?)))
46 } 46 }
47 47
48 fn to_idx(id: ID) -> usize { 48 fn to_idx(id: Idx<T>) -> usize {
49 u32::from(id.into_raw()) as usize 49 u32::from(id.into_raw()) as usize
50 } 50 }
51 51
52 fn from_idx(idx: usize) -> ID { 52 fn from_idx(idx: usize) -> Idx<T> {
53 ID::from_raw((idx as u32).into()) 53 Idx::from_raw((idx as u32).into())
54 } 54 }
55} 55}
56 56
57impl<ID: ArenaId, T> std::ops::Index<ID> for ArenaMap<ID, T> { 57impl<T, V> std::ops::Index<Idx<V>> for ArenaMap<Idx<V>, T> {
58 type Output = T; 58 type Output = T;
59 fn index(&self, id: ID) -> &T { 59 fn index(&self, id: Idx<V>) -> &T {
60 self.v[Self::to_idx(id)].as_ref().unwrap() 60 self.v[Self::to_idx(id)].as_ref().unwrap()
61 } 61 }
62} 62}
63 63
64impl<ID, T> Default for ArenaMap<ID, T> { 64impl<T, V> Default for ArenaMap<Idx<V>, T> {
65 fn default() -> Self { 65 fn default() -> Self {
66 ArenaMap { v: Vec::new(), _ty: PhantomData } 66 ArenaMap { v: Vec::new(), _ty: PhantomData }
67 } 67 }