Skip to main content

doublets/data/
traits.rs

1#[cfg(feature = "rayon")]
2use rayon::prelude::*;
3
4use std::collections::HashSet;
5
6use crate::{Error, Fuse, Link};
7use data::{Flow, LinkReference, LinksConstants, ToQuery};
8
9/// Callback type for read-only link enumeration.
10pub type ReadHandler<'a, T> = &'a mut dyn FnMut(Link<T>) -> Flow;
11
12/// Callback type for mutating operations that report `(before, after)` link states.
13pub type WriteHandler<'a, T> = &'a mut dyn FnMut(Link<T>, Link<T>) -> Flow;
14
15/// Low-level, raw slice-based interface for a doublets link store.
16///
17/// Implementors are required to be `Send + Sync`. Most users should prefer the
18/// higher-level [`Doublets`] trait which builds on this one.
19pub trait Links<T: LinkReference>: Send + Sync {
20    /// Returns the store's [`LinksConstants`] (any/null/range values).
21    fn constants(&self) -> &LinksConstants<T>;
22
23    /// Counts links that match `query`.
24    fn count_links(&self, query: &[T]) -> T;
25
26    /// Creates one or more links matching `query` and reports each creation via `handler`.
27    fn create_links(&mut self, query: &[T], handler: WriteHandler<'_, T>)
28        -> Result<Flow, Error<T>>;
29
30    /// Iterates over links matching `query`, calling `handler` for each.
31    fn each_links(&self, query: &[T], handler: ReadHandler<'_, T>) -> Flow;
32
33    /// Updates links matching `query` to the new values in `change`, reporting via `handler`.
34    fn update_links(
35        &mut self,
36        query: &[T],
37        change: &[T],
38        handler: WriteHandler<'_, T>,
39    ) -> Result<Flow, Error<T>>;
40
41    /// Deletes links matching `query` and reports each deletion via `handler`.
42    ///
43    /// Endpoint-reset and usage policies depend on the implementation. Memory
44    /// stores retain resetting convenience deletion; for release-only deletion
45    /// use [`crate::decorators::CheckedRelease`] or [`crate::mem::Release`].
46    fn delete_links(&mut self, query: &[T], handler: WriteHandler<'_, T>)
47        -> Result<Flow, Error<T>>;
48}
49
50/// High-level API for a doublets link store, extending [`Links`] with ergonomic helpers.
51///
52/// All methods have default implementations built on top of [`Links`].
53pub trait Doublets<T: LinkReference>: Links<T> {
54    /// Counts links matching `query`.
55    fn count_by(&self, query: impl ToQuery<T>) -> T
56    where
57        Self: Sized,
58    {
59        self.count_links(&query.to_query()[..])
60    }
61
62    /// Returns the total number of links in the store.
63    fn count(&self) -> T
64    where
65        Self: Sized,
66    {
67        self.count_by([])
68    }
69
70    /// Creates a link matching `query`, calling `handler` on each created link.
71    fn create_by_with<F>(
72        &mut self,
73        query: impl ToQuery<T>,
74        mut handler: F,
75    ) -> Result<Flow, Error<T>>
76    where
77        F: FnMut(Link<T>, Link<T>) -> Flow,
78        Self: Sized,
79    {
80        let query = query.to_query();
81        self.create_links(&query[..], &mut handler)
82    }
83
84    /// Creates a link matching `query` and returns its index.
85    fn create_by(&mut self, query: impl ToQuery<T>) -> Result<T, Error<T>>
86    where
87        Self: Sized,
88    {
89        let mut index = T::from_byte(0);
90        self.create_by_with(query, |_before, link| {
91            index = link.index;
92            Flow::Continue
93        })
94        .map(|_| index)
95    }
96
97    /// Creates a new link and calls `handler` with the before/after states.
98    fn create_with<F>(&mut self, handler: F) -> Result<Flow, Error<T>>
99    where
100        F: FnMut(Link<T>, Link<T>) -> Flow,
101        Self: Sized,
102    {
103        self.create_by_with([], handler)
104    }
105
106    /// Creates a new uninitialized link and returns its index.
107    fn create(&mut self) -> Result<T, Error<T>>
108    where
109        Self: Sized,
110    {
111        self.create_by([])
112    }
113
114    /// Iterates over links matching `query`, calling `handler` for each.
115    fn each_by<F>(&self, query: impl ToQuery<T>, mut handler: F) -> Flow
116    where
117        F: FnMut(Link<T>) -> Flow,
118        Self: Sized,
119    {
120        let query = query.to_query();
121        self.each_links(&query[..], &mut handler)
122    }
123
124    /// Iterates over all links in the store, calling `handler` for each.
125    fn each<F>(&self, handler: F) -> Flow
126    where
127        F: FnMut(Link<T>) -> Flow,
128        Self: Sized,
129    {
130        self.each_by([], handler)
131    }
132
133    /// Updates links matching `query` to `change`, calling `handler` with before/after.
134    fn update_by_with<H>(
135        &mut self,
136        query: impl ToQuery<T>,
137        change: impl ToQuery<T>,
138        mut handler: H,
139    ) -> Result<Flow, Error<T>>
140    where
141        H: FnMut(Link<T>, Link<T>) -> Flow,
142        Self: Sized,
143    {
144        let query = query.to_query();
145        let change = change.to_query();
146        self.update_links(&query[..], &change[..], &mut handler)
147    }
148
149    /// Updates links matching `query` to `change` and returns the updated link's index.
150    fn update_by(&mut self, query: impl ToQuery<T>, change: impl ToQuery<T>) -> Result<T, Error<T>>
151    where
152        Self: Sized,
153    {
154        let mut result = T::from_byte(0);
155        self.update_by_with(query, change, |_, after| {
156            result = after.index;
157            Flow::Continue
158        })
159        .map(|_| result)
160    }
161
162    /// Updates the link at `index` to `(index, source, target)`, calling `handler`.
163    fn update_with<F>(
164        &mut self,
165        index: T,
166        source: T,
167        target: T,
168        handler: F,
169    ) -> Result<Flow, Error<T>>
170    where
171        F: FnMut(Link<T>, Link<T>) -> Flow,
172        Self: Sized,
173    {
174        self.update_by_with([index], [index, source, target], handler)
175    }
176
177    /// Updates the link at `index` to `(index, source, target)` and returns the index.
178    fn update(&mut self, index: T, source: T, target: T) -> Result<T, Error<T>>
179    where
180        Self: Sized,
181    {
182        self.update_by([index], [index, source, target])
183    }
184
185    /// Deletes links matching `query`, calling `handler` with before/after states.
186    fn delete_by_with<F>(
187        &mut self,
188        query: impl ToQuery<T>,
189        mut handler: F,
190    ) -> Result<Flow, Error<T>>
191    where
192        F: FnMut(Link<T>, Link<T>) -> Flow,
193        Self: Sized,
194    {
195        let query = query.to_query();
196        self.delete_links(&query[..], &mut handler)
197    }
198
199    /// Deletes links matching `query` and returns the deleted link's index.
200    fn delete_by(&mut self, query: impl ToQuery<T>) -> Result<T, Error<T>>
201    where
202        Self: Sized,
203    {
204        let mut result = T::from_byte(0);
205        self.delete_by_with(query, |before, _after| {
206            result = before.index;
207            Flow::Continue
208        })
209        .map(|_| result)
210    }
211
212    /// Deletes the link at `index`, calling `handler` with before/after states.
213    fn delete_with<F>(&mut self, index: T, handler: F) -> Result<Flow, Error<T>>
214    where
215        F: FnMut(Link<T>, Link<T>) -> Flow,
216        Self: Sized,
217    {
218        self.delete_by_with([index], handler)
219    }
220
221    /// Deletes the link at `index` and returns its former index.
222    fn delete(&mut self, index: T) -> Result<T, Error<T>>
223    where
224        Self: Sized,
225    {
226        self.delete_by([index])
227    }
228
229    /// Returns the link at `index`, or `Err(Error::NotExists)` if it does not exist.
230    fn try_get_link(&self, index: T) -> Result<Link<T>, Error<T>> {
231        self.get_link(index).ok_or(Error::NotExists(index))
232    }
233
234    /// Returns the link at `index`, or `None` if it does not exist.
235    fn get_link(&self, index: T) -> Option<Link<T>>;
236
237    /// Deletes all links in reverse enumeration order.
238    /// Links already removed by cascading deletions are skipped.
239    fn delete_all(&mut self) -> Result<(), Error<T>>
240    where
241        Self: Sized,
242    {
243        let indices: Vec<_> = self.each_iter([]).map(|link| link.index).collect();
244        for index in indices.into_iter().rev() {
245            if self.exist(index) {
246                self.delete(index)?;
247            }
248        }
249        Ok(())
250    }
251
252    /// Deletes all links matching `query`, calling `handler` for each deletion.
253    /// Duplicate matches are deleted once, in reverse order of their first occurrence.
254    fn delete_query_with<F>(&mut self, query: impl ToQuery<T>, handler: F) -> Result<(), Error<T>>
255    where
256        F: FnMut(Link<T>, Link<T>) -> Flow,
257        Self: Sized,
258    {
259        let query = query.to_query();
260        let len = self.count_by(query.to_query()).as_();
261        let mut vec = Vec::with_capacity(len);
262        let mut seen = HashSet::with_capacity(len);
263
264        self.each_by(query, |link| {
265            if seen.insert(link.index) {
266                vec.push(link.index);
267            }
268            Flow::Continue
269        });
270
271        let mut handler = Fuse::new(handler);
272        for index in vec.into_iter().rev() {
273            self.delete_links(&[index], &mut |before, after| handler.call(before, after))?;
274        }
275        Ok(())
276    }
277
278    /// Deletes each other link that uses `index` as a source or target once,
279    /// calling `handler` for each deletion.
280    fn delete_usages_with<F>(&mut self, index: T, handler: F) -> Result<(), Error<T>>
281    where
282        F: FnMut(Link<T>, Link<T>) -> Flow,
283        Self: Sized,
284    {
285        let any = self.constants().any;
286        let mut to_delete = Vec::with_capacity(
287            self.count_by([any, index, any]).as_() + self.count_by([any, any, index]).as_(),
288        );
289        self.each_by([any, index, any], |link| {
290            if link.index != index {
291                to_delete.push(link.index);
292            }
293            Flow::Continue
294        });
295
296        self.each_by([any, any, index], |link| {
297            if link.index != index && link.source != index {
298                to_delete.push(link.index);
299            }
300            Flow::Continue
301        });
302
303        let mut handler = Fuse::new(handler);
304        for index in to_delete.into_iter().rev() {
305            self.delete_links(&[index], &mut |before, after| handler.call(before, after))?;
306        }
307        Ok(())
308    }
309
310    /// Deletes all links that use `index` as a source or target.
311    fn delete_usages(&mut self, index: T) -> Result<(), Error<T>>
312    where
313        Self: Sized,
314    {
315        self.delete_usages_with(index, |_, _| Flow::Continue)
316    }
317
318    /// Creates a self-referential point link and returns its index.
319    fn create_point(&mut self) -> Result<T, Error<T>>
320    where
321        Self: Sized,
322    {
323        let new = self.create()?;
324        self.update(new, new, new)
325    }
326
327    /// Creates a link from `source` to `target`, calling `handler` with before/after states.
328    ///
329    /// A handler's [`Flow::Break`] suppresses later callbacks and is returned even if
330    /// an inner layer returns [`Flow::Continue`]. Link initialization still completes.
331    fn create_link_with<F>(&mut self, source: T, target: T, handler: F) -> Result<Flow, Error<T>>
332    where
333        F: FnMut(Link<T>, Link<T>) -> Flow,
334        Self: Sized,
335    {
336        let mut new = T::from_byte(0);
337        let mut handler = Fuse::new(handler);
338        self.create_with(|before, after| {
339            new = after.index;
340            handler.call(before, after);
341            Flow::Continue
342        })?;
343
344        let flow = self.update_links(&[new], &[new, source, target], &mut |before, after| {
345            handler.call(before, after)
346        })?;
347        Ok(if handler.flow().is_break() {
348            Flow::Break
349        } else {
350            flow
351        })
352    }
353
354    /// Creates a link from `source` to `target` and returns its index.
355    fn create_link(&mut self, source: T, target: T) -> Result<T, Error<T>>
356    where
357        Self: Sized,
358    {
359        let mut result = T::from_byte(0);
360        self.create_link_with(source, target, |_, link| {
361            result = link.index;
362            Flow::Continue
363        })
364        .map(|_| result)
365    }
366
367    /// Returns `true` if at least one link matches `query`.
368    fn found(&self, query: impl ToQuery<T>) -> bool
369    where
370        Self: Sized,
371    {
372        self.count_by(query) != T::from_byte(0)
373    }
374
375    /// Returns the first link matching `query`, or `None`.
376    fn find(&self, query: impl ToQuery<T>) -> Option<Link<T>>
377    where
378        Self: Sized,
379    {
380        let mut result = None;
381        self.each_by(query, |link| {
382            result = Some(link);
383            Flow::Break
384        });
385        result
386    }
387
388    /// Returns the index of a link with the given `source` and `target`, or `None`.
389    fn search(&self, source: T, target: T) -> Option<T>
390    where
391        Self: Sized,
392    {
393        self.find([self.constants().any, source, target])
394            .map(|link| link.index)
395    }
396
397    #[deprecated(note = "use `search` instead")]
398    fn search_or(&self, source: T, target: T, default: T) -> T
399    where
400        Self: Sized,
401    {
402        self.search(source, target).unwrap_or(default)
403    }
404
405    /// Returns the link matching `query` only if exactly one link matches; `None` otherwise.
406    fn single(&self, query: impl ToQuery<T>) -> Option<Link<T>>
407    where
408        Self: Sized,
409    {
410        let mut result = None;
411        self.each_by(query, |link| {
412            if result.is_none() {
413                result = Some(link);
414                Flow::Continue
415            } else {
416                result = None;
417                Flow::Break
418            }
419        });
420        result
421    }
422
423    /// Returns the index of the `(source, target)` link, creating it if it does not exist.
424    fn get_or_create(&mut self, source: T, target: T) -> Result<T, Error<T>>
425    where
426        Self: Sized,
427    {
428        if let Some(link) = self.search(source, target) {
429            Ok(link)
430        } else {
431            self.create_link(source, target)
432        }
433    }
434
435    /// Returns the number of distinct other links that reference `index` as a source or target.
436    fn count_usages(&self, index: T) -> Result<T, Error<T>>
437    where
438        Self: Sized,
439    {
440        let any = self.constants().any;
441
442        let link = self.try_get_link(index)?;
443
444        let usage_source = self.count_by([any, index, any]);
445        let usage_target = self.count_by([any, any, index]);
446        let usage_both = self.count_by([any, index, index]);
447        // Remove the overlap before adding to avoid overflowing narrow address types.
448        let mut usages = usage_source + (usage_target - usage_both);
449        if index == link.source || index == link.target {
450            usages = usages - T::from_byte(1);
451        }
452
453        Ok(usages)
454    }
455
456    /// Returns the indices of distinct other links that reference `index` as a source or target.
457    fn usages(&self, index: T) -> Result<Vec<T>, Error<T>>
458    where
459        Self: Sized,
460    {
461        let any = self.constants().any;
462        let mut usages = Vec::with_capacity(self.count_usages(index)?.as_());
463
464        self.each_by([any, index, any], |link| {
465            if link.index != index {
466                usages.push(link.index);
467            }
468            Flow::Continue
469        });
470
471        self.each_by([any, any, index], |link| {
472            if link.index != index && link.source != index {
473                usages.push(link.index);
474            }
475            Flow::Continue
476        });
477        Ok(usages)
478    }
479
480    /// Returns `true` if the link at `link` exists (internal or external).
481    fn exist(&self, link: T) -> bool
482    where
483        Self: Sized,
484    {
485        let constants = self.constants();
486        if constants.is_external(link) {
487            true
488        } else {
489            constants.is_internal(link) && self.count_by([link]) != T::from_byte(0)
490        }
491    }
492
493    /// Returns `true` if any other link references `link` as a source or target.
494    fn has_usages(&self, link: T) -> bool
495    where
496        Self: Sized,
497    {
498        self.count_usages(link)
499            .is_ok_and(|link| link != T::from_byte(0))
500    }
501
502    /// Re-points all usages of `old` to `new`, calling `handler` for each update.
503    ///
504    /// A usage that references `old` as both source and target is updated once,
505    /// replacing both references together. The link at `old` itself is excluded.
506    fn rebase_with<F>(&mut self, old: T, new: T, handler: F) -> Result<(), Error<T>>
507    where
508        F: FnMut(Link<T>, Link<T>) -> Flow,
509        Self: Sized,
510    {
511        let _ = self.try_get_link(old)?;
512
513        if old == new {
514            return Ok(());
515        }
516
517        let any = self.constants().any;
518
519        let mut handler = Fuse::new(handler);
520
521        let usages: Vec<_> = self
522            .each_iter([any, old, any])
523            // Usages with `old` on both sides were already found by the source query.
524            .chain(
525                self.each_iter([any, any, old])
526                    .filter(|usage| usage.source != old),
527            )
528            .filter(|usage| usage.index != old)
529            .collect();
530        for usage in usages {
531            let source = if usage.source == old {
532                new
533            } else {
534                usage.source
535            };
536            let target = if usage.target == old {
537                new
538            } else {
539                usage.target
540            };
541            self.update_links(
542                &[usage.index],
543                &[usage.index, source, target],
544                &mut |before, after| handler.call(before, after),
545            )?;
546        }
547        Ok(())
548    }
549
550    /// Re-points all usages of `old` to `new` and returns `new`.
551    fn rebase(&mut self, old: T, new: T) -> Result<T, Error<T>>
552    where
553        Self: Sized,
554    {
555        self.rebase_with(old, new, |_, _| Flow::Continue)
556            .map(|()| new)
557    }
558
559    /// Re-points all usages of `old` to `new`, then deletes `old`. Returns `new`.
560    fn rebase_and_delete(&mut self, old: T, new: T) -> Result<T, Error<T>>
561    where
562        Self: Sized,
563    {
564        if old == new {
565            Ok(new)
566        } else {
567            self.rebase(old, new)?;
568            self.delete(old).map(|_| new)
569        }
570    }
571}
572
573impl<T: LinkReference, All: Doublets<T> + ?Sized> Links<T> for Box<All> {
574    fn constants(&self) -> &LinksConstants<T> {
575        (**self).constants()
576    }
577
578    fn count_links(&self, query: &[T]) -> T {
579        (**self).count_links(query)
580    }
581
582    fn create_links(
583        &mut self,
584        query: &[T],
585        handler: WriteHandler<'_, T>,
586    ) -> Result<Flow, Error<T>> {
587        (**self).create_links(query, handler)
588    }
589
590    fn each_links(&self, query: &[T], handler: ReadHandler<'_, T>) -> Flow {
591        (**self).each_links(query, handler)
592    }
593
594    fn update_links(
595        &mut self,
596        query: &[T],
597        change: &[T],
598        handler: WriteHandler<'_, T>,
599    ) -> Result<Flow, Error<T>> {
600        (**self).update_links(query, change, handler)
601    }
602
603    fn delete_links(
604        &mut self,
605        query: &[T],
606        handler: WriteHandler<'_, T>,
607    ) -> Result<Flow, Error<T>> {
608        (**self).delete_links(query, handler)
609    }
610}
611
612impl<T: LinkReference, All: Doublets<T> + ?Sized> Doublets<T> for Box<All> {
613    fn get_link(&self, index: T) -> Option<Link<T>> {
614        (**self).get_link(index)
615    }
616}
617
618/// Extension trait that adds iterator-based access to a [`Doublets`] store.
619///
620/// Automatically implemented for any type that implements [`Doublets`].
621pub trait DoubletsExt<T: LinkReference>: Sized + Doublets<T> {
622    /// The parallel iterator type returned by [`par_iter`](DoubletsExt::par_iter).
623    #[cfg(feature = "rayon")]
624    type IdxParIter: IndexedParallelIterator<Item = Link<T>>;
625
626    /// Returns a parallel iterator over all links in the store.
627    #[cfg(feature = "rayon")]
628    fn par_iter(&self) -> Self::IdxParIter;
629
630    /// Returns a parallel iterator over links matching `query`.
631    #[cfg(feature = "rayon")]
632    fn par_each_iter(&self, query: impl ToQuery<T>) -> Self::IdxParIter;
633
634    /// Returns an iterator over all links in the store.
635    fn iter(&self) -> impl Iterator<Item = Link<T>> + ExactSizeIterator + DoubleEndedIterator;
636
637    /// Returns an iterator over links matching `query`.
638    fn each_iter(
639        &self,
640        query: impl ToQuery<T>,
641    ) -> impl Iterator<Item = Link<T>> + ExactSizeIterator + DoubleEndedIterator;
642
643    /// Returns a small-vec-backed iterator over all links (optimised for small result sets).
644    #[cfg(feature = "small-search")]
645    fn iter_small(&self)
646        -> impl Iterator<Item = Link<T>> + ExactSizeIterator + DoubleEndedIterator;
647
648    /// Returns a small-vec-backed iterator over links matching `query`.
649    #[cfg(feature = "small-search")]
650    fn each_iter_small(
651        &self,
652        query: impl ToQuery<T>,
653    ) -> impl Iterator<Item = Link<T>> + ExactSizeIterator + DoubleEndedIterator;
654}
655
656impl<T: LinkReference, All: Doublets<T> + Sized> DoubletsExt<T> for All {
657    #[cfg(feature = "rayon")]
658    type IdxParIter = rayon::vec::IntoIter<Link<T>>;
659
660    #[cfg(feature = "rayon")]
661    fn par_iter(&self) -> Self::IdxParIter {
662        self.par_each_iter([self.constants().any; 3])
663    }
664
665    #[cfg(feature = "rayon")]
666    fn par_each_iter(&self, query: impl ToQuery<T>) -> Self::IdxParIter {
667        let mut vec = Vec::with_capacity(self.count_by(query.to_query()).as_());
668        self.each_by(query, |link| {
669            vec.push(link);
670            Flow::Continue
671        });
672        vec.into_par_iter()
673    }
674
675    #[inline]
676    fn iter(&self) -> impl Iterator<Item = Link<T>> + ExactSizeIterator + DoubleEndedIterator {
677        self.each_iter([self.constants().any; 3])
678    }
679
680    #[cfg_attr(feature = "more-inline", inline)]
681    fn each_iter(
682        &self,
683        query: impl ToQuery<T>,
684    ) -> impl Iterator<Item = Link<T>> + ExactSizeIterator + DoubleEndedIterator {
685        let cap = self.count_by(query.to_query()).as_();
686
687        let mut vec = Vec::with_capacity(cap);
688        self.each_by(query, &mut |link| {
689            vec.push(link);
690            Flow::Continue
691        });
692        vec.into_iter()
693    }
694
695    #[inline]
696    #[cfg(feature = "small-search")]
697    fn iter_small(
698        &self,
699    ) -> impl Iterator<Item = Link<T>> + ExactSizeIterator + DoubleEndedIterator {
700        self.each_iter_small([self.constants().any; 3])
701    }
702
703    #[cfg(feature = "small-search")]
704    #[cfg_attr(feature = "more-inline", inline)]
705    fn each_iter_small(
706        &self,
707        query: impl ToQuery<T>,
708    ) -> impl Iterator<Item = Link<T>> + ExactSizeIterator + DoubleEndedIterator {
709        const SIZE_HINT: usize = 2;
710
711        let mut vec = smallvec::SmallVec::<[Link<_>; SIZE_HINT]>::with_capacity(
712            self.count_by(query.to_query()).as_(),
713        );
714        self.each_by(query, |link| {
715            vec.push(link);
716            Flow::Continue
717        });
718        vec.into_iter()
719    }
720}