paradis_core/par_access.rs
1use crate::{Bounds, RecordIndex};
2
3/// Unsynchronized access to records in a collection.
4///
5/// The trait provides *unsynchronized* access to *records*, defined by the
6/// associated [`Record`](Self::Record) type, that are indexed by the `Index` parameter.
7/// This trait gives data structures a means to give users
8/// unfettered access to its records, without exposing internal implementation details
9/// to the user. In turn, it is the responsibility of the user to maintain the invariants
10/// of Rust's memory safety model.
11///
12/// An access object for a data structure is usually a lightweight wrapper around one
13/// or more pointers, plus necessary metadata.
14///
15/// In order to use higher-level functionality in `paradis`,
16/// implementors should try to implement [`BoundedParAccess`] too, whenever possible.
17///
18/// # Safety
19///
20/// A user must ensure that a record — accessed by the same index — is only accessed once,
21/// at any given time. It may be helpful to imagine that [`Record`](Self::Record) is
22/// a mutable reference, `&mut T`, and so it is undefined behavior to obtain two mutable
23/// references to the same object. In other words, once a specific [`Record`](Self::Record)
24/// is accessed, it can not be accessed through this access object again until the previous
25/// instance is dropped.
26///
27/// An implementor must ensure that, for as long as any access object exists, the size of the
28/// data structure remains unchanged, and that the same index always refers to the same "slot"
29/// in the data structure.
30///
31/// # Notes on design
32///
33/// In an early iteration of `paradis`, [`Record`](Self::Record) was not required to implement
34/// `Send`. The idea was that you should be able to use the abstraction also in single-threaded
35/// scenarios, possibly with types that are not `Send`. However, since we want `ParAccess` to
36/// be `Send` and `Sync`, this could lead to unsoundness because moving an access object
37/// into a thread would allow us to create, say, a single-threaded iterator to records in
38/// that thread, even though those records were not constrained to be `Send`.
39/// To eliminate problems like these, we therefore require that [`Record`](Self::Record)
40/// implements `Send`.
41pub unsafe trait ParAccess<Index: Copy>: Sync + Send {
42 /// A record (element) in the underlying collection.
43 type Record: Send;
44
45 /// Clones this access.
46 ///
47 /// # Safety
48 ///
49 /// This is unsafe, because methods that consume access objects typically assume that
50 /// the access is exclusive. If the access is cloned, then the user must ensure that
51 /// the invariants are uphold across *all* active accesses. Typically, this is achieved
52 /// by having each access work on disjoint sets of records.
53 unsafe fn clone_access(&self) -> Self;
54
55 /// Unsynchronized lookup of record without bounds checks.
56 ///
57 /// # Safety
58 ///
59 /// See trait documentation.
60 unsafe fn get_unsync_unchecked(&self, index: Index) -> Self::Record;
61}
62
63/// Unsynchronized access to a bounded collection.
64///
65/// This trait allows a data structure that is structurally similar to a multidimensional array
66/// to describe its bounds, which enables use of the data structure with higher-level functionality
67/// in `paradis`.
68///
69/// # Safety
70///
71/// The bounds reported *must* be correct, in the sense that any index contained in the bounds
72/// may be used to access a valid record.
73pub unsafe trait BoundedParAccess<Index: Copy>: ParAccess<Index> {
74 /// The bounds of this data structure.
75 ///
76 /// # Safety
77 ///
78 /// The bounds for a collection must never change while an access object still lives.
79 fn bounds(&self) -> Bounds<Index>;
80
81 /// Determine if the provided index is in bounds.
82 ///
83 /// Can be overridden by implementors for a simpler implementation than the default,
84 /// which may aid the compiler in eliding bounds checks in situations where bounds may
85 /// not be eliminated upfront.
86 fn in_bounds(&self, index: Index) -> bool
87 where
88 Index: RecordIndex,
89 {
90 self.bounds().contains_index(index)
91 }
92
93 /// Unsynchronized mutable lookup of record.
94 ///
95 /// The access is unsynchronized (and therefore unsafe), but bounds checked.
96 ///
97 /// # Safety
98 ///
99 /// See trait documentation.
100 ///
101 /// # Panics
102 ///
103 /// Panics if index is out of bounds.
104 unsafe fn get_unsync(&self, index: Index) -> Self::Record
105 where
106 Index: RecordIndex,
107 {
108 assert!(self.in_bounds(index), "index out of bounds");
109 unsafe { self.get_unsync_unchecked(index) }
110 }
111}
112
113/// A type that can be converted into a parallel access object.
114pub trait IntoParAccess<Index: Copy = usize> {
115 /// The access type obtained through this trait.
116 type Access: BoundedParAccess<Index>;
117
118 /// Obtain parallel access to this collection.
119 fn into_par_access(self) -> Self::Access;
120}
121
122impl<Index: Copy, Access: BoundedParAccess<Index>> IntoParAccess<Index> for Access {
123 type Access = Self;
124
125 fn into_par_access(self) -> Self::Access {
126 self
127 }
128}
129
130/// An unsynchronized access to an array-like structure, indexed by `usize`.
131///
132/// # Safety
133///
134/// The length of the collection must be reported correctly.
135pub unsafe trait LinearParAccess: BoundedParAccess<usize> {
136 /// The number of accessible records in the collection.
137 ///
138 /// An implementor must ensure that this length never changes. In other words,
139 /// once an access is obtained, the size of the collection must never not change
140 /// while an access is active.
141 ///
142 /// It must also be equivalent to the result returned by the extent of the
143 /// [`Bounds`] of the access.
144 fn collection_len(&self) -> usize {
145 self.bounds().extent
146 }
147}