1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

use std::ops::{Index, RangeFrom, RangeTo};
use std::cell::UnsafeCell;

use parking_lot::{RawMutex, lock_api::RawMutex as _};

mod private {
    /// Sealed trait for types that can be shared in a `SharedStack`.
    ///
    /// The type of values passed to
    /// [`local_cache`](crate::request::local_cache) must implement this trait.
    /// Since this trait is sealed, the types implementing this trait are known
    /// and finite: `String` and `Vec<T> for all T: Sync + Send + 'static`.
    ///
    /// # Safety
    ///
    /// Types implementing this trait must have a stable address when deref'd.
    pub unsafe trait Shareable: std::ops::Deref + Sync + Send + 'static {
        /// The current size of the owned shareable.
        fn size(&self) -> usize;
    }

    unsafe impl Shareable for String {
        fn size(&self) -> usize { self.len() }
    }

    unsafe impl<T: Send + Sync + 'static> Shareable for Vec<T> {
        fn size(&self) -> usize { self.len() }
    }
}

pub use private::Shareable;

/// A stack of strings (chars of bytes) that can be shared between threads while
/// remaining internally mutable and while allowing references into the stack to
/// persist across mutations.
pub struct SharedStack<T: Shareable> {
    stack: UnsafeCell<Vec<T>>,
    mutex: RawMutex,
}

impl<T: Shareable> SharedStack<T>
    where T::Target: Index<RangeFrom<usize>, Output = T::Target>
                     + Index<RangeTo<usize>, Output = T::Target>
{
    /// Creates a new stack.
    pub fn new() -> Self {
        SharedStack {
            stack: UnsafeCell::new(vec![]),
            mutex: RawMutex::INIT,
        }
    }

    /// Pushes the string `S` onto the stack. Returns a reference of the string
    /// in the stack.
    pub(crate) fn push<S: Into<T>>(&self, string: S) -> &T::Target {
        // SAFETY:
        //   * Aliasing: We retrieve a mutable reference to the last slot (via
        //     `push()`) and then return said reference as immutable; these
        //     occur in serial, so they don't alias. This method accesses a
        //     unique slot each call: the last slot, subsequently replaced by
        //     `push()` each next call. No other method accesses the internal
        //     buffer directly. Thus, the outstanding reference to the last slot
        //     is never accessed again mutably, preserving aliasing guarantees.
        //   * Liveness: The returned reference is to a `String`; we must ensure
        //     that the `String` is never dropped while `self` lives. This is
        //     guaranteed by returning a reference with the same lifetime as
        //     `self`, so `self` can't be dropped while the string is live, and
        //     by never removing elements from the internal `Vec` thus not
        //     dropping `String` itself: `push()` is the only mutating operation
        //     called on `Vec`, which preserves all previous elements; the
        //     stability of `String` itself means that the returned address
        //     remains valid even after internal realloc of `Vec`.
        //   * Thread-Safety: Parallel calls to `push_one` without exclusion
        //     would result in a race to `vec.push()`; `RawMutex` ensures that
        //     this doesn't occur.
        unsafe {
            self.mutex.lock();
            let vec: &mut Vec<T> = &mut *self.stack.get();
            vec.push(string.into());
            let last = vec.last().expect("push() => non-empty");
            self.mutex.unlock();
            last
        }
    }

    /// Just like `push` but `string` must already be the owned `T`.
    pub fn push_owned(&self, string: T) -> &T::Target {
        self.push(string)
    }

    /// Pushes the string `S` onto the stack which is assumed to internally
    /// contain two strings with the first string being of length `n`. Returns
    /// references to the two strings on the stack.
    ///
    /// # Panics
    ///
    /// Panics if `string.len() < len`.
    pub(crate) fn push_split<S: Into<T>>(&self, string: S, n: usize) -> (&T::Target, &T::Target) {
        let buffered = self.push(string);
        let a = &buffered[..n];
        let b = &buffered[n..];
        (a, b)
    }

    /// Pushes the strings `a` and `b` onto the stack without allocating for
    /// both strings. Returns references to the two strings on the stack.
    pub(crate) fn push_two<V>(&self, a: V, b: V) -> (&T::Target, &T::Target)
        where T: From<V> + Extend<V>,
    {
        let mut value = T::from(a);
        let split_len = value.size();
        value.extend(Some(b));
        self.push_split(value, split_len)
    }
}

unsafe impl<T: Shareable> Sync for SharedStack<T> {}