1use crate::runtime::atom::Atom;
2use crate::util::FxHashMap;
3use std::cell::{Cell, UnsafeCell};
4use std::ptr::NonNull;
5
6#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
7pub struct ShapeId(pub usize);
8
9impl ShapeId {
10 pub fn root() -> Self {
11 ShapeId(0)
12 }
13}
14
15#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
16pub struct Transition {
17 pub property: Atom,
18 pub offset: u32,
19}
20
21pub struct Shape {
22 pub id: ShapeId,
23 pub parent: Option<NonNull<Shape>>,
24 pub transition: Option<Transition>,
25 pub property_count: u32,
26 property_map: UnsafeCell<FxHashMap<Atom, u32>>,
27 property_map_built: UnsafeCell<bool>,
28
29 children: UnsafeCell<Vec<(Atom, NonNull<Shape>)>>,
30}
31
32unsafe impl Send for Shape {}
33unsafe impl Sync for Shape {}
34
35impl Shape {
36 pub fn root() -> Self {
37 Shape {
38 id: ShapeId::root(),
39 parent: None,
40 transition: None,
41 property_count: 0,
42 property_map: UnsafeCell::new(FxHashMap::default()),
43 property_map_built: UnsafeCell::new(true),
44 children: UnsafeCell::new(Vec::new()),
45 }
46 }
47
48 pub fn add_property(&self, property: Atom, id: ShapeId) -> Shape {
49 let offset = self.property_count;
50 let parent_ptr = NonNull::from(self);
51 Shape {
52 id,
53 parent: Some(parent_ptr),
54 transition: Some(Transition { property, offset }),
55 property_count: self.property_count + 1,
56 property_map: UnsafeCell::new(FxHashMap::default()),
57 property_map_built: UnsafeCell::new(false),
58 children: UnsafeCell::new(Vec::new()),
59 }
60 }
61
62 pub fn get_offset(&self, property: Atom) -> Option<u32> {
63 if self.property_count <= 8 {
64 unsafe {
65 let mut current = Some(NonNull::from(self));
66 while let Some(shape_ptr) = current {
67 let shape = &*shape_ptr.as_ptr();
68 if let Some(ref t) = shape.transition {
69 if t.property == property {
70 return Some(t.offset);
71 }
72 }
73 current = shape.parent;
74 }
75 }
76 return None;
77 }
78 self.ensure_property_map();
79
80 unsafe { (*self.property_map.get()).get(&property).copied() }
81 }
82
83 fn ensure_property_map(&self) {
84 unsafe {
85 if *self.property_map_built.get() {
86 return;
87 }
88
89 let map = &mut *self.property_map.get();
90 map.reserve(self.property_count as usize);
91 let mut current = Some(NonNull::from(self));
92
93 while let Some(shape_ptr) = current {
94 let shape = &*shape_ptr.as_ptr();
95 if let Some(transition) = &shape.transition {
96 map.insert(transition.property, transition.offset);
97 }
98 current = shape.parent;
99 }
100
101 *self.property_map_built.get() = true;
102 }
103 }
104
105 pub fn properties(&self) -> Vec<(Atom, u32)> {
106 let mut props = Vec::with_capacity(self.property_count as usize);
107 let mut current = Some(NonNull::from(self));
108
109 while let Some(shape_ptr) = current {
110 unsafe {
111 let shape = &*shape_ptr.as_ptr();
112 if let Some(transition) = &shape.transition {
113 props.push((transition.property, transition.offset));
114 }
115 current = shape.parent;
116 }
117 }
118
119 props.reverse();
120 props
121 }
122
123 pub fn has_property(&self, property: Atom) -> bool {
124 self.get_offset(property).is_some()
125 }
126
127 pub fn is_root(&self) -> bool {
128 self.parent.is_none()
129 }
130}
131
132impl std::fmt::Debug for Shape {
133 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
134 f.debug_struct("Shape")
135 .field("id", &self.id)
136 .field("property_count", &self.property_count)
137 .field("transition", &self.transition)
138 .finish()
139 }
140}
141
142pub struct ShapeCache {
143 root_shape: NonNull<Shape>,
144 next_id: Cell<usize>,
145 shapes: Vec<Box<Shape>>,
146}
147
148impl ShapeCache {
149 pub fn new() -> Self {
150 let root = Box::new(Shape::root());
151 let root_ptr = NonNull::from(&*root);
152
153 ShapeCache {
154 root_shape: root_ptr,
155 next_id: Cell::new(1),
156 shapes: vec![root],
157 }
158 }
159
160 pub fn alloc_id(&self) -> ShapeId {
161 let id = self.next_id.get();
162 self.next_id.set(id + 1);
163 ShapeId(id)
164 }
165
166 pub fn root_shape(&self) -> NonNull<Shape> {
167 self.root_shape
168 }
169
170 pub fn transition(&mut self, parent: NonNull<Shape>, property: Atom) -> NonNull<Shape> {
171 unsafe {
172 let parent_ref = &*parent.as_ptr();
173
174 let children = &mut *parent_ref.children.get();
175 for &(atom, child_ptr) in children.iter() {
176 if atom == property {
177 return child_ptr;
178 }
179 }
180
181 let child_id = self.alloc_id();
182 let child = Box::new(parent_ref.add_property(property, child_id));
183 let child_ptr = NonNull::from(&*child);
184 children.push((property, child_ptr));
185 self.shapes.push(child);
186 child_ptr
187 }
188 }
189
190 pub fn create_shape_for_properties(&mut self, properties: &[Atom]) -> NonNull<Shape> {
191 let mut current = self.root_shape;
192
193 for property in properties {
194 current = self.transition(current, *property);
195 }
196
197 current
198 }
199}
200
201impl Default for ShapeCache {
202 fn default() -> Self {
203 Self::new()
204 }
205}
206
207impl Drop for ShapeCache {
208 fn drop(&mut self) {}
209}
210
211#[cfg(test)]
212mod tests {
213 use super::*;
214 use crate::runtime::atom::AtomTable;
215
216 #[test]
217 fn test_root_shape() {
218 let shape = Shape::root();
219 assert!(shape.is_root());
220 assert_eq!(shape.property_count, 0);
221 }
222
223 #[test]
224 fn test_shape_transitions() {
225 let mut atoms = AtomTable::new();
226 let foo = atoms.intern("foo");
227 let bar = atoms.intern("bar");
228
229 let mut cache = ShapeCache::new();
230 let root = cache.root_shape();
231
232 let shape1 = cache.transition(root, foo);
233 unsafe {
234 let s1 = &*shape1.as_ptr();
235 assert_eq!(s1.property_count, 1);
236 assert_eq!(s1.get_offset(foo), Some(0));
237 assert_eq!(s1.get_offset(bar), None);
238 }
239
240 let shape2 = cache.transition(shape1, bar);
241 unsafe {
242 let s2 = &*shape2.as_ptr();
243 assert_eq!(s2.property_count, 2);
244 assert_eq!(s2.get_offset(foo), Some(0));
245 assert_eq!(s2.get_offset(bar), Some(1));
246 }
247 }
248
249 #[test]
250 fn test_shape_caching() {
251 let mut atoms = AtomTable::new();
252 let foo = atoms.intern("foo");
253
254 let mut cache = ShapeCache::new();
255 let root = cache.root_shape();
256
257 let shape1 = cache.transition(root, foo);
258 let shape2 = cache.transition(root, foo);
259
260 assert_eq!(shape1, shape2);
261 }
262
263 #[test]
264 fn test_properties_iteration() {
265 let mut atoms = AtomTable::new();
266 let foo = atoms.intern("foo");
267 let bar = atoms.intern("bar");
268 let baz = atoms.intern("baz");
269
270 let mut cache = ShapeCache::new();
271 let root = cache.root_shape();
272
273 let shape1 = cache.transition(root, foo);
274 let shape2 = cache.transition(shape1, bar);
275 let shape3 = cache.transition(shape2, baz);
276
277 unsafe {
278 let s3 = &*shape3.as_ptr();
279 let props = s3.properties();
280 assert_eq!(props.len(), 3);
281 assert_eq!(props[0], (foo, 0));
282 assert_eq!(props[1], (bar, 1));
283 assert_eq!(props[2], (baz, 2));
284 }
285 }
286}