dynprops/
lib.rs

1//! Creating and extending objects with typed dynamic properties.
2//!
3//! ## Example
4//!
5//! ```
6//! use dynprops::{Subject, Dynamic};
7//!
8//! let subject = Subject::new();
9//! let prop_a = subject.new_prop_const_init(5);
10//! let prop_b = subject.new_prop_const_init("Foo");
11//! let mut obj = Dynamic::new(&subject);
12//! assert_eq!(obj[&prop_a], 5);
13//! assert_eq!(obj[&prop_b], "Foo");
14//!
15//! // Properties can be changed on a mutable object
16//! obj[&prop_b] = "Foobar";
17//! assert_eq!(obj[&prop_b], "Foobar");
18//!
19//! // New properties can be introduced after an object is already created
20//! let prop_c = subject.new_prop_default_init::<u32>();
21//! assert_eq!(obj[&prop_c], 0u32);
22//!
23//! // Properties can be initialized based on a function of other properties on the object
24//! let prop_d = subject.new_prop_fn_init(|obj| obj[&prop_b].len());
25//! assert_eq!(obj[&prop_d], 6);
26//! ```
27
28use std::alloc::{alloc_zeroed, dealloc, handle_alloc_error, Layout};
29use std::cmp::max;
30use std::marker::PhantomData;
31use std::ops::{Index, IndexMut};
32use std::ptr::NonNull;
33use std::sync::Mutex;
34use std::{mem, ptr, usize};
35
36/// Identifies a category of objects and a dynamic set of [`Property`]s that apply to those objects.
37/// New properties can be introduced into the subject at any time using [`Subject::new_prop`]
38/// and its derivatives. When accessing a property of an object, the subject of the property
39/// must match the subject of the object.
40///
41/// ## Lifetime
42/// The [`Subject`] must be alive for the entire duration that any [`Property`], [`Extended`] or
43/// [`Dynamic`] are associated with it. This is enforced by a lifetime parameter on those types. In
44/// practice, subjects will usually be bound to the `'static` lifetime.
45pub struct Subject<T> {
46    layout: Mutex<SubjectLayout>,
47    _phantom: PhantomData<fn(T)>,
48}
49
50struct SubjectLayout {
51    size: usize,
52    align: usize,
53    init_words: Vec<InitWord>,
54    drop_props: Vec<DropProperty>,
55}
56
57struct InitWord {
58    offset: usize,
59    in_use: usize,
60}
61
62struct DropProperty {
63    offset: usize,
64    init_bit_offset: usize,
65    drop: unsafe fn(NonNull<u8>),
66}
67
68struct PropertyInfo {
69    offset: usize,
70    init_bit_offset: usize,
71}
72
73impl<T> Subject<T> {
74    /// Creates a new subject.
75    pub fn new() -> Self {
76        Subject {
77            layout: Mutex::new(SubjectLayout {
78                size: 0,
79                align: 1,
80                init_words: Vec::new(),
81                drop_props: Vec::new(),
82            }),
83            _phantom: PhantomData,
84        }
85    }
86
87    /// Creates a new property within this subject. An [`Init`] must be supplied to specify how the
88    /// initial value of the property is determined.
89    pub fn new_prop<'a, P, I: Init<T, P>>(&'a self, initer: I) -> Property<'a, T, P, I> {
90        let info = self.alloc_prop::<P>();
91        return Property {
92            subject: self,
93            offset: info.offset,
94            init_bit_offset: info.init_bit_offset,
95            initer,
96            _phantom: PhantomData,
97        };
98    }
99
100    /// Creates a new property within this subject. Upon initialization, the property will have the
101    /// default value (as defined by [`Default::default()`]) for type `P`.
102    pub fn new_prop_default_init<'a, P: Default>(&'a self) -> DefaultInitProperty<'a, T, P> {
103        self.new_prop(DefaultInit)
104    }
105
106    /// Creates a new property within this subject. Upon initialization, the property will have the
107    /// given value.
108    pub fn new_prop_const_init<'a, P: Clone>(&'a self, value: P) -> ConstInitProperty<'a, T, P> {
109        self.new_prop(ConstInit { value })
110    }
111
112    /// Creates a new property within this subject. Upon initialization, the value of the property
113    /// will be determined by executing the given closure.
114    ///
115    /// Since the closure takes the object itself, the initializer may reference the base value or
116    /// any other property that has been defined on [`Subject`]. For example:
117    /// ```
118    /// use dynprops::{Subject, Extended};
119    ///
120    /// let subject = Subject::new();
121    /// let prop_value = subject.new_prop_fn_init(|obj| obj.value);
122    /// let prop_double_value = subject.new_prop_fn_init(|obj| obj[&prop_value] * 2);
123    /// let prop_square_value = subject.new_prop_fn_init(|obj| obj[&prop_value] * obj[&prop_value]);
124    /// let obj = Extended::new_extend(20, &subject);
125    /// assert_eq!(obj[&prop_value], 20);
126    /// assert_eq!(obj[&prop_double_value], 40);
127    /// assert_eq!(obj[&prop_square_value], 400);
128    /// ```
129    /// The constraints on property lifetimes ensure that circular references between property
130    /// initializers are impossible.
131    pub fn new_prop_fn_init<'a, P, F: Fn(&Extended<T>) -> P>(
132        &'a self,
133        init_fn: F,
134    ) -> FnInitProperty<'a, T, P, F> {
135        self.new_prop(FnInit { init_fn })
136    }
137
138    fn pin_layout(&self) -> Layout {
139        let guard = self.layout.lock().unwrap();
140        unsafe {
141            return Layout::from_size_align_unchecked(guard.size, guard.align);
142        }
143    }
144
145    fn alloc_prop<P>(&self) -> PropertyInfo {
146        let mut layout = self.layout.lock().unwrap();
147        return layout.alloc_prop::<P>();
148    }
149
150    fn free_prop<P>(&self, offset: usize) {
151        if !mem::needs_drop::<P>() {
152            let mut layout = self.layout.lock().unwrap();
153            return layout.free_nodrop_prop(offset);
154        }
155    }
156}
157
158impl SubjectLayout {
159    fn alloc_prop<P>(&mut self) -> PropertyInfo {
160        let init_bit_offset = self.alloc_init_bit();
161        let offset = self.alloc::<P>();
162        if mem::needs_drop::<P>() {
163            let drop = Self::drop_option_in_place::<P>;
164            self.drop_props.push(DropProperty {
165                offset,
166                init_bit_offset,
167                drop,
168            });
169        }
170        return PropertyInfo {
171            offset,
172            init_bit_offset,
173        };
174    }
175
176    unsafe fn drop_option_in_place<P>(ptr: NonNull<u8>) {
177        ptr::drop_in_place(ptr.cast::<Option<P>>().as_ptr());
178    }
179
180    fn alloc_init_bit(&mut self) -> usize {
181        // Search for an existing word that we can allocate a bit in
182        for init_word in self.init_words.iter_mut() {
183            if init_word.in_use != usize::MAX {
184                let bit = init_word.in_use.trailing_ones() as usize;
185                init_word.in_use |= 1 << bit;
186                return init_word.offset * 8 + bit;
187            }
188        }
189
190        // Allocate a new word
191        let offset = self.alloc::<usize>();
192        let mut in_use = 0;
193        let bit = 0;
194        in_use |= 1 << bit;
195        self.init_words.push(InitWord { offset, in_use });
196        return offset * 8 + bit;
197    }
198
199    fn alloc<P>(&mut self) -> usize {
200        self.alloc_raw(mem::size_of::<P>(), mem::align_of::<P>())
201    }
202
203    fn alloc_raw(&mut self, size: usize, align: usize) -> usize {
204        let offset = (self.size + align - 1) & !(align - 1);
205        self.size = offset + size;
206        self.align = max(self.align, align);
207        return offset;
208    }
209
210    fn free_nodrop_prop(&mut self, _offset: usize) {
211        // TODO: remove from layout
212    }
213}
214
215/// Identifies a property that is present on objects of the appropriate [`Subject`].
216///
217/// ## Property Lifetime
218/// The lifetime of a reference to a property on an object is limited by both the object and
219/// the property itself. This allows memory to be reclaimed/reused for properties that have been
220/// dropped.
221///
222/// ```compile_fail
223/// use dynprops::{Subject, Dynamic};
224///
225/// let subject = Subject::new();
226/// let prop = subject.new_prop_const_init(5);
227/// let mut obj = Dynamic::new(&subject);
228/// let x = &mut obj[&prop];
229/// drop(prop);
230/// *x = 10; // ERROR: This reference requires prop to be alive
231/// ```
232pub struct Property<'a, T, P, I: 'a + Init<T, P>> {
233    subject: &'a Subject<T>,
234    offset: usize,
235    init_bit_offset: usize,
236    initer: I,
237    _phantom: PhantomData<fn() -> P>,
238}
239
240/// A shortcut for a [`Property`] that is initialized by a [`DefaultInit`].
241pub type DefaultInitProperty<'a, T, P> = Property<'a, T, P, DefaultInit>;
242
243/// A shortcut for a [`Property`] that is initialized by a [`ConstInit`].
244pub type ConstInitProperty<'a, T, P> = Property<'a, T, P, ConstInit<P>>;
245
246/// A shortcut for a [`Property`] that is initialized by a [`FnInit`].
247pub type FnInitProperty<'a, T, P, F> = Property<'a, T, P, FnInit<F>>;
248
249/// A shortcut for a [`Property`] that is initialized by a [`DynInit`]. Any property can be
250/// converted into a [`DynInitProperty`] using [`Property::into_dyn_init`].
251pub type DynInitProperty<'a, T, P> = Property<'a, T, P, DynInit<'a, T, P>>;
252
253impl<'a, T, P, I: Init<T, P>> Property<'a, T, P, I> {
254    /// Gets the [`Subject`] this property is associated with. This defines which [`Dynamic`]s and
255    /// [`Extended`]s contain this property.
256    pub fn subject(&self) -> &Subject<T> {
257        self.subject
258    }
259}
260
261impl<'a, T, P, I: Init<T, P> + Sync> Property<'a, T, P, I> {
262    /// Converts this property into a [`DynInitProperty`] by wrapping its initializer in a
263    /// [`DynInit`]. Note that this will add overhead if it is already a [`DynInitProperty`].
264    pub fn into_dyn_init(self) -> DynInitProperty<'a, T, P> {
265        // Need to use unsafe here because there is no other way to take initer
266        unsafe {
267            let result = Property {
268                subject: self.subject,
269                offset: self.offset,
270                init_bit_offset: self.init_bit_offset,
271                initer: Box::new(ptr::read(&self.initer)) as DynInit<'a, T, P>,
272                _phantom: PhantomData
273            };
274            mem::forget(self);
275            return result;
276        }
277    }
278}
279
280impl<'a, T, P, I: Init<T, P>> Drop for Property<'a, T, P, I> {
281    fn drop(&mut self) {
282        self.subject.free_prop::<P>(self.offset);
283    }
284}
285
286/// Defines how a [`Property`] is initialized when first accessed.
287pub trait Init<T, P> {
288    /// Creates the initial value for the property on the given object.
289    fn init(&self, obj: &Extended<T>) -> P;
290}
291
292/// An [`Init`] which initializes values using [`Default::default()`].
293pub struct DefaultInit;
294
295/// An [`Init`] which initializes values by cloning a given value.
296pub struct ConstInit<P: Clone> {
297    pub value: P,
298}
299
300/// An [`Init`] which initializes values by executing a closure.
301pub struct FnInit<F> {
302    pub init_fn: F,
303}
304
305/// An [`Init`] that uses dynamic dispatch to defer to another [`Init`] at runtime.
306pub type DynInit<'a, T, P> = Box<dyn 'a + Sync + Init<T, P>>;
307
308impl<T, P, F: Fn(&Extended<T>) -> P> Init<T, P> for FnInit<F> {
309    fn init(&self, obj: &Extended<T>) -> P {
310        (self.init_fn)(obj)
311    }
312}
313
314impl<T, P: Clone> Init<T, P> for ConstInit<P> {
315    fn init(&self, _obj: &Extended<T>) -> P {
316        self.value.clone()
317    }
318}
319
320impl<T, P: Default> Init<T, P> for DefaultInit {
321    fn init(&self, _obj: &Extended<T>) -> P {
322        Default::default()
323    }
324}
325
326impl<'a, T, P> Init<T, P> for DynInit<'a, T, P> {
327    fn init(&self, obj: &Extended<T>) -> P {
328        self.as_ref().init(obj)
329    }
330}
331
332/// Extends a value of type `T` with properties defined in a particular [`Subject<T>`].
333///
334/// Property values are accessed by index, like so:
335/// ```
336/// use dynprops::{Subject, Extended};
337///
338/// let subject = Subject::new();
339/// let prop = subject.new_prop_default_init();
340/// let mut obj = Extended::new_extend(5, &subject);
341/// obj[&prop] = "Foo";
342/// assert_eq!(obj[&prop], "Foo");
343/// ```
344///
345/// The base value of an [`Extended`] object can always be accessed through the `value` field:
346/// ```
347/// use dynprops::{Subject, Extended};
348///
349/// let subject = Subject::new();
350/// let mut obj = Extended::new_extend(5, &subject);
351/// obj.value = 15;
352/// assert_eq!(obj.value, 15);
353/// ```
354pub struct Extended<'a, T> {
355    pub value: T,
356    subject: &'a Subject<T>,
357    data: Mutex<ExtendedData>,
358}
359
360/// An object consisting entirely of dynamic properties defined in a particular [`Subject`].
361///
362/// Property values are accessed by index, like so:
363/// ```
364/// use dynprops::{Subject, Dynamic};
365/// let subject = Subject::new();
366/// let prop = subject.new_prop_default_init();
367/// let mut obj = Dynamic::new(&subject);
368/// obj[&prop] = "Bar";
369/// assert_eq!(obj[&prop], "Bar");
370/// ```
371pub type Dynamic<'a> = Extended<'a, ()>;
372
373impl<'a, T> Extended<'a, T> {
374    /// Creates an [`Extended`] wrapper over the given value. This extends it with all of the
375    /// [`Property`]s defined on `subject`.
376    pub fn new_extend(value: T, subject: &'a Subject<T>) -> Self {
377        Extended {
378            value,
379            subject,
380            data: Mutex::new(ExtendedData::new(subject.pin_layout())),
381        }
382    }
383
384    /// Gets the [`Subject`] this object is associated with. This defines which [`Property`]s are
385    /// available on the object.
386    pub fn subject(&self) -> &Subject<T> {
387        self.subject
388    }
389
390    fn index_raw<P, I: Init<T, P>>(&self, index: &Property<'a, T, P, I>) -> NonNull<P> {
391        // Verify subject
392        if (self.subject as *const Subject<T>) != (index.subject as *const Subject<T>) {
393            panic!("Subject mismatch");
394        }
395
396        // Check for initialization
397        let get_data_layout = || self.subject.pin_layout();
398        let init_word_offset = (index.init_bit_offset / 8) & !(mem::align_of::<usize>() - 1);
399        let init_word_bit = index.init_bit_offset - (init_word_offset * 8);
400        unsafe {
401            let mut data = self.data.lock().unwrap();
402            let init_word = data
403                .get_ptr(get_data_layout, init_word_offset)
404                .cast::<usize>()
405                .as_mut();
406            let value_ptr = data.get_ptr(get_data_layout, index.offset).cast::<P>();
407
408            // Drop the lock as soon as we have the pointers we need. We don't want to hold the
409            // lock during initialization, since other properties within the same object can
410            // be referenced.
411            drop(data);
412
413            let init_bit = (*init_word & (1 << init_word_bit)) != 0;
414            if !init_bit {
415                // Do initialization
416                let init_value = index.initer.init(&self);
417
418                // Lock to write the initial value
419                let data = self.data.lock().unwrap();
420                let init_bit = (*init_word & (1 << init_word_bit)) != 0;
421                if !init_bit {
422                    ptr::write(value_ptr.as_ptr(), init_value);
423                    *init_word |= 1 << init_word_bit;
424                }
425                drop(data);
426            }
427            return value_ptr;
428        }
429    }
430}
431
432impl<'a> Dynamic<'a> {
433    /// Creates a new [`Dynamic`] object.
434    pub fn new(subject: &'a Subject<()>) -> Self {
435        Self::new_extend((), subject)
436    }
437}
438
439impl<'a, 'b, T, P, I: Init<T, P>> Index<&'b Property<'a, T, P, I>> for Extended<'b, T> {
440    type Output = P;
441
442    fn index(&self, index: &Property<'a, T, P, I>) -> &Self::Output {
443        unsafe {
444            return &(*self.index_raw(index).as_ref());
445        }
446    }
447}
448
449impl<'a, 'b, T, P, I: Init<T, P>> IndexMut<&'b Property<'a, T, P, I>> for Extended<'b, T> {
450    fn index_mut(&mut self, index: &Property<'a, T, P, I>) -> &mut Self::Output {
451        unsafe {
452            return &mut (*self.index_raw(index).as_mut());
453        }
454    }
455}
456
457impl<'a, T> Drop for Extended<'a, T> {
458    fn drop(&mut self) {
459        let mut data = self.data.lock().unwrap();
460        let layout = self.subject.layout.lock().unwrap();
461        for prop in layout.drop_props.iter() {
462            let get_data_layout = || self.subject.pin_layout();
463            let init_word_offset = (prop.init_bit_offset / 8) & !(mem::align_of::<usize>() - 1);
464            let init_word_bit = prop.init_bit_offset - (init_word_offset * 8);
465            unsafe {
466                let init_word = data
467                    .get_ptr(get_data_layout, init_word_offset)
468                    .cast::<usize>()
469                    .as_mut();
470                let init_bit = (*init_word & (1 << init_word_bit)) != 0;
471                if init_bit {
472                    // Drop property
473                    let value_ptr = data.get_ptr(get_data_layout, prop.offset);
474                    (prop.drop)(value_ptr);
475                }
476            }
477        }
478    }
479}
480
481/// The internal representation of the data for a [Extended]. Note that, unlike [Vec], we can't move
482/// underlying data when new properties are added. That's because properties can be initialized
483/// from a shared borrow at the same time that pre-existing properties are being referenced. This
484/// limits are design choices here considerably. The current implementation stores data in either
485/// a "head" chunk or an "overflow" chunk. The "head" chunk consists of the properties that
486/// existed when the [Extended] was created, and the "overflow" chunks contain blocks of new
487/// properties that were added later on.
488struct ExtendedData {
489    head_chunk: Chunk,
490    overflow_chunks: Vec<Chunk>,
491}
492
493/// Describes a chunk within [ExtendedData].
494struct Chunk {
495    ptr: NonNull<u8>,
496    layout: Layout,
497    data_end: usize,
498}
499
500impl ExtendedData {
501    fn new(head_layout: Layout) -> Self {
502        ExtendedData {
503            head_chunk: Chunk::new(head_layout, head_layout.size()),
504            overflow_chunks: Vec::new(),
505        }
506    }
507
508    /// Gets a pointer to a particular property within the [ExtendedData], given the offset of the
509    /// property within the entire [SubjectLayout]. If an additional chunk needs to be allocated,
510    /// `get_data_layout` will be used to get the latest size/alignment of the [SubjectLayout].
511    fn get_ptr(&mut self, get_data_layout: impl FnOnce() -> Layout, offset: usize) -> NonNull<u8> {
512        // Is the data in the head chunk?
513        if offset < self.head_chunk.data_end {
514            unsafe {
515                return NonNull::new_unchecked(self.head_chunk.ptr.as_ptr().add(offset));
516            }
517        }
518
519        // Is the data in an existing overflow chunk?
520        let mut overflow_data_end = self.head_chunk.data_end;
521        match self.overflow_chunks.last() {
522            Some(last_overflow_chunk) => {
523                overflow_data_end = last_overflow_chunk.data_end;
524                if offset < last_overflow_chunk.data_end {
525                    // Use binary search to figure out which chunk
526                    let mut lo_chunk_index = 0;
527                    let mut hi_chunk_index = self.overflow_chunks.len() - 1;
528                    let mut chunk_data_start = self.head_chunk.data_end;
529                    loop {
530                        if !(lo_chunk_index < hi_chunk_index) {
531                            break;
532                        }
533                        let mid_chunk_index = (lo_chunk_index + hi_chunk_index) / 2;
534                        let mid_chunk = &self.overflow_chunks[mid_chunk_index];
535                        if offset < mid_chunk.data_end {
536                            hi_chunk_index = mid_chunk_index;
537                        } else {
538                            chunk_data_start = mid_chunk.data_end;
539                            lo_chunk_index = mid_chunk_index + 1;
540                        }
541                    }
542                    unsafe {
543                        let overflow_chunk = &self.overflow_chunks[lo_chunk_index];
544                        return NonNull::new_unchecked(
545                            overflow_chunk
546                                .ptr
547                                .as_ptr()
548                                .sub(chunk_data_start)
549                                .add(offset),
550                        );
551                    }
552                }
553            }
554            _ => {}
555        }
556
557        // Create a new overflow chunk
558        let data_layout = get_data_layout();
559        let new_data_end = data_layout.size();
560        assert!(offset < new_data_end);
561        let chunk_layout =
562            Layout::from_size_align(new_data_end - overflow_data_end, data_layout.align()).unwrap();
563        let overflow_chunk = Chunk::new(chunk_layout, new_data_end);
564        let result = unsafe {
565            NonNull::new_unchecked(
566                overflow_chunk
567                    .ptr
568                    .as_ptr()
569                    .sub(overflow_data_end)
570                    .add(offset),
571            )
572        };
573        self.overflow_chunks.push(overflow_chunk);
574        return result;
575    }
576}
577
578impl Chunk {
579    fn new(layout: Layout, data_end: usize) -> Self {
580        let ptr = if layout.size() > 0 {
581            unsafe {
582                match NonNull::new(alloc_zeroed(layout)) {
583                    Some(ptr) => ptr,
584                    None => handle_alloc_error(layout),
585                }
586            }
587        } else {
588            NonNull::dangling()
589        };
590        Chunk {
591            ptr,
592            layout,
593            data_end,
594        }
595    }
596}
597
598impl Drop for Chunk {
599    fn drop(&mut self) {
600        if self.layout.size() > 0 {
601            unsafe {
602                dealloc(self.ptr.as_ptr(), self.layout);
603            }
604        }
605    }
606}
607
608#[cfg(test)]
609mod tests;
dynprops/lib.rs

dynprops/
lib.rs
