1use std::fmt;
2
3use crate::entity::{Entities, Entity, SceneId};
4use crate::store::{Owner, StoreError, StoreField};
5
6#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
8pub struct LinkId {
9 scene: SceneId,
10 slot: u32,
11 generation: u32,
12}
13
14impl fmt::Display for LinkId {
15 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
16 write!(f, "link {} gen {}", self.slot, self.generation)
17 }
18}
19
20#[derive(Clone, Copy, Debug)]
21pub struct Link<T> {
22 pub(crate) from: Entity,
23 pub(crate) to: Entity,
24 pub data: T,
25}
26
27impl<T> Link<T> {
28 pub fn from(&self) -> Entity {
29 self.from
30 }
31
32 pub fn to(&self) -> Entity {
33 self.to
34 }
35}
36
37#[derive(Clone, Copy)]
38struct LinkSlot {
39 generation: u32,
40 dense: Option<u32>,
41}
42
43#[derive(Clone, Copy)]
44struct Ends {
45 outgoing: u32,
46 incoming: u32,
47}
48
49#[derive(Default)]
50struct Adjacency {
51 generation: u32,
52 outgoing: Vec<LinkId>,
53 incoming: Vec<LinkId>,
54}
55
56pub struct Relation<T> {
57 scene: SceneId,
58 links: Vec<Link<T>>,
59 ids: Vec<LinkId>,
60 ends: Vec<Ends>,
61 slots: Vec<LinkSlot>,
62 free: Vec<u32>,
63 adjacency: Vec<Adjacency>,
64}
65
66impl<T> Default for Relation<T> {
67 fn default() -> Self {
68 Self::new()
69 }
70}
71
72impl<T> Relation<T> {
73 pub fn new() -> Self {
74 Self {
75 scene: SceneId::UNBOUND,
76 links: Vec::new(),
77 ids: Vec::new(),
78 ends: Vec::new(),
79 slots: Vec::new(),
80 free: Vec::new(),
81 adjacency: Vec::new(),
82 }
83 }
84
85 pub fn scene(&self) -> SceneId {
86 self.scene
87 }
88
89 pub fn len(&self) -> usize {
90 self.links.len()
91 }
92
93 pub fn is_empty(&self) -> bool {
94 self.links.is_empty()
95 }
96
97 pub fn links(&self) -> &[Link<T>] {
98 &self.links
99 }
100
101 pub fn ids(&self) -> &[LinkId] {
102 &self.ids
103 }
104
105 pub fn link(
107 &mut self,
108 entities: &Entities,
109 from: Entity,
110 to: Entity,
111 data: T,
112 ) -> Result<LinkId, StoreError> {
113 for endpoint in [from, to] {
114 if endpoint.scene() != entities.scene() {
115 return Err(StoreError::Foreign(endpoint));
116 }
117 if entities.resolve(endpoint).is_none() {
118 return Err(StoreError::Stale(endpoint));
119 }
120 }
121 if self.scene == SceneId::UNBOUND {
122 self.scene = entities.scene();
123 }
124 self.link_raw(from, to, data)
125 }
126
127 pub(crate) fn link_raw(
128 &mut self,
129 from: Entity,
130 to: Entity,
131 data: T,
132 ) -> Result<LinkId, StoreError> {
133 for endpoint in [from, to] {
134 if endpoint.scene() != self.scene {
135 return Err(StoreError::Foreign(endpoint));
136 }
137 self.claim(endpoint)?;
138 }
139 let dense = u32::try_from(self.links.len()).map_err(|_| StoreError::Capacity)?;
140 let slot = match self.free.pop() {
141 Some(slot) => slot,
142 None => {
143 self.slots.push(LinkSlot {
144 generation: 0,
145 dense: None,
146 });
147 (self.slots.len() - 1) as u32
148 }
149 };
150 self.slots[slot as usize].dense = Some(dense);
151 let id = LinkId {
152 scene: self.scene,
153 slot,
154 generation: self.slots[slot as usize].generation,
155 };
156 let outgoing = &mut self.adjacency[from.key().slot() as usize].outgoing;
157 let out_position = outgoing.len() as u32;
158 outgoing.push(id);
159 let incoming = &mut self.adjacency[to.key().slot() as usize].incoming;
160 let in_position = incoming.len() as u32;
161 incoming.push(id);
162 self.links.push(Link { from, to, data });
163 self.ids.push(id);
164 self.ends.push(Ends {
165 outgoing: out_position,
166 incoming: in_position,
167 });
168 Ok(id)
169 }
170
171 fn claim(&mut self, endpoint: Entity) -> Result<(), StoreError> {
172 let slot = endpoint.key().slot() as usize;
173 if slot >= self.adjacency.len() {
174 self.adjacency.resize_with(slot + 1, Adjacency::default);
175 }
176 let adjacency = &mut self.adjacency[slot];
177 if adjacency.generation != endpoint.key().generation() {
178 if !adjacency.outgoing.is_empty() || !adjacency.incoming.is_empty() {
179 return Err(StoreError::Occupied(endpoint));
180 }
181 adjacency.generation = endpoint.key().generation();
182 }
183 Ok(())
184 }
185
186 pub fn unlink(&mut self, id: LinkId) -> Result<Link<T>, StoreError> {
187 let dense = self.dense_index(id).ok_or(StoreError::Unlinked(id))?;
188 let ends = self.ends[dense];
189 let from_slot = self.links[dense].from.key().slot() as usize;
190 let to_slot = self.links[dense].to.key().slot() as usize;
191 let outgoing = &mut self.adjacency[from_slot].outgoing;
192 outgoing.swap_remove(ends.outgoing as usize);
193 let moved_out = outgoing.get(ends.outgoing as usize).copied();
194 if let Some(moved) = moved_out.and_then(|moved| self.dense_index(moved)) {
195 self.ends[moved].outgoing = ends.outgoing;
196 }
197 let incoming = &mut self.adjacency[to_slot].incoming;
198 incoming.swap_remove(ends.incoming as usize);
199 let moved_in = incoming.get(ends.incoming as usize).copied();
200 if let Some(moved) = moved_in.and_then(|moved| self.dense_index(moved)) {
201 self.ends[moved].incoming = ends.incoming;
202 }
203 let link = self.links.swap_remove(dense);
204 self.ids.swap_remove(dense);
205 self.ends.swap_remove(dense);
206 if let Some(&moved) = self.ids.get(dense) {
207 self.slots[moved.slot as usize].dense = Some(dense as u32);
208 }
209 let slot = &mut self.slots[id.slot as usize];
210 slot.dense = None;
211 if let Some(next) = slot.generation.checked_add(1) {
212 slot.generation = next;
213 self.free.push(id.slot);
214 }
215 Ok(link)
216 }
217
218 fn dense_index(&self, id: LinkId) -> Option<usize> {
219 if id.scene != self.scene {
220 return None;
221 }
222 let slot = self.slots.get(id.slot as usize)?;
223 if slot.generation != id.generation {
224 return None;
225 }
226 slot.dense.map(|dense| dense as usize)
227 }
228
229 pub fn get(&self, id: LinkId) -> Option<&Link<T>> {
230 self.dense_index(id).map(|dense| &self.links[dense])
231 }
232
233 pub fn get_mut(&mut self, id: LinkId) -> Option<&mut T> {
234 let dense = self.dense_index(id)?;
235 Some(&mut self.links[dense].data)
236 }
237
238 pub fn outgoing(&self, from: Entity) -> Endpoints<'_> {
239 Endpoints {
240 ids: self
241 .adjacency_of(from)
242 .map_or(&[], |adjacency| &adjacency.outgoing),
243 }
244 }
245
246 pub fn incoming(&self, to: Entity) -> Endpoints<'_> {
247 Endpoints {
248 ids: self
249 .adjacency_of(to)
250 .map_or(&[], |adjacency| &adjacency.incoming),
251 }
252 }
253
254 fn adjacency_of(&self, endpoint: Entity) -> Option<&Adjacency> {
255 if endpoint.scene() != self.scene {
256 return None;
257 }
258 let adjacency = self.adjacency.get(endpoint.key().slot() as usize)?;
259 (adjacency.generation == endpoint.key().generation()).then_some(adjacency)
260 }
261}
262
263pub struct Endpoints<'a> {
264 ids: &'a [LinkId],
265}
266
267impl Iterator for Endpoints<'_> {
268 type Item = LinkId;
269
270 fn next(&mut self) -> Option<LinkId> {
271 let (&first, rest) = self.ids.split_first()?;
272 self.ids = rest;
273 Some(first)
274 }
275}
276
277pub struct RelationSnapshot<T> {
278 links: Vec<Link<T>>,
279}
280
281impl<T> RelationSnapshot<T> {
282 pub fn links(&self) -> &[Link<T>] {
283 &self.links
284 }
285}
286
287impl<T: Clone + Send + 'static> StoreField for Relation<T> {
288 type Snapshot = RelationSnapshot<T>;
289
290 fn bind(&mut self, scene: SceneId, _owner: Owner) {
291 self.scene = scene;
292 }
293
294 fn snapshot(&self) -> RelationSnapshot<T> {
295 RelationSnapshot {
296 links: self.links.clone(),
297 }
298 }
299
300 fn restore(&mut self, from: &RelationSnapshot<T>, scene: SceneId, _owner: Owner) {
301 self.scene = scene;
302 self.links.clear();
303 self.ids.clear();
304 self.ends.clear();
305 self.slots.clear();
306 self.free.clear();
307 self.adjacency.clear();
308 for (dense, link) in from.links.iter().enumerate() {
309 let ends = [
310 Entity::new(scene, link.from.key()),
311 Entity::new(scene, link.to.key()),
312 ];
313 let id = LinkId {
314 scene,
315 slot: dense as u32,
316 generation: 0,
317 };
318 self.slots.push(LinkSlot {
319 generation: 0,
320 dense: Some(dense as u32),
321 });
322 for endpoint in ends {
323 let slot = endpoint.key().slot() as usize;
324 if slot >= self.adjacency.len() {
325 self.adjacency.resize_with(slot + 1, Adjacency::default);
326 }
327 self.adjacency[slot].generation = endpoint.key().generation();
328 }
329 let outgoing = &mut self.adjacency[ends[0].key().slot() as usize].outgoing;
330 let out_position = outgoing.len() as u32;
331 outgoing.push(id);
332 let incoming = &mut self.adjacency[ends[1].key().slot() as usize].incoming;
333 let in_position = incoming.len() as u32;
334 incoming.push(id);
335 self.links.push(Link {
336 from: ends[0],
337 to: ends[1],
338 data: link.data.clone(),
339 });
340 self.ids.push(id);
341 self.ends.push(Ends {
342 outgoing: out_position,
343 incoming: in_position,
344 });
345 }
346 }
347
348 fn release(&mut self, entity: Entity, _owner: Owner) {
349 while let Some(id) = self
350 .outgoing(entity)
351 .next()
352 .or_else(|| self.incoming(entity).next())
353 {
354 if self.unlink(id).is_err() {
355 break;
356 }
357 }
358 }
359}
360
361#[cfg(test)]
362mod tests {
363 use super::*;
364 use crate::entity::{Entities, Epoch, RuntimeId};
365
366 fn data(relation: &Relation<&'static str>, ids: Endpoints<'_>) -> Vec<&'static str> {
367 let mut data: Vec<&str> = ids.map(|id| relation.get(id).unwrap().data).collect();
368 data.sort_unstable();
369 data
370 }
371
372 #[test]
373 fn endpoints_resolve_after_a_swap_remove() {
374 let mut entities = Entities::new(SceneId {
375 runtime: RuntimeId::allocate(),
376 epoch: Epoch::default(),
377 });
378 let mut relation = Relation::new();
379 StoreField::bind(&mut relation, entities.scene(), Owner::new());
380 let [a, b, c] = [(); 3].map(|()| entities.spawn());
381 let ab = relation.link(&entities, a, b, "ab").unwrap();
382 let ac = relation.link(&entities, a, c, "ac").unwrap();
383 let bc = relation.link(&entities, b, c, "bc").unwrap();
384
385 assert_eq!(relation.unlink(ab).map(|link| link.data), Ok("ab"));
386 assert_eq!(
387 relation.unlink(ab).map(|link| link.data),
388 Err(StoreError::Unlinked(ab))
389 );
390 assert_eq!(relation.len(), 2);
391 assert!(relation.get(ab).is_none());
392 assert_eq!(relation.get(bc).map(|link| link.data), Some("bc"));
393 assert_eq!(data(&relation, relation.outgoing(a)), ["ac"]);
394 assert_eq!(data(&relation, relation.incoming(c)), ["ac", "bc"]);
395 assert!(data(&relation, relation.incoming(b)).is_empty());
396
397 assert_eq!(relation.unlink(bc).map(|link| link.data), Ok("bc"));
398 assert_eq!(data(&relation, relation.incoming(c)), ["ac"]);
399 assert_eq!(relation.get(ac).map(Link::to), Some(c));
400 let relinked = relation.link(&entities, b, c, "bc2").unwrap();
401 assert_ne!(relinked, bc);
402 assert!(relation.get(bc).is_none());
403 assert_eq!(data(&relation, relation.incoming(c)), ["ac", "bc2"]);
404 }
405
406 #[test]
407 fn mutable_link_data_keeps_adjacency_endpoints_sealed() {
408 let mut entities = Entities::new(SceneId {
409 runtime: RuntimeId::allocate(),
410 epoch: Epoch::default(),
411 });
412 let mut relation = Relation::new();
413 StoreField::bind(&mut relation, entities.scene(), Owner::new());
414 let [a, b, c] = [(); 3].map(|()| entities.spawn());
415 let ab = relation.link(&entities, a, b, "before").unwrap();
416
417 *relation.get_mut(ab).unwrap() = "after";
418
419 assert_eq!(relation.get(ab).map(Link::from), Some(a));
420 assert_eq!(relation.get(ab).map(Link::to), Some(b));
421 assert_eq!(data(&relation, relation.outgoing(a)), ["after"]);
422 assert_eq!(data(&relation, relation.incoming(b)), ["after"]);
423 assert!(relation.incoming(c).next().is_none());
424 }
425}