1 files changed, 463 insertions, 0 deletions
diff --git a/vendor/rowan/src/arc.rs b/vendor/rowan/src/arc.rs
new file mode 100644
index 000000000..348831290
--- /dev/null
+++ b/vendor/rowan/src/arc.rs
@@ -0,0 +1,463 @@
+//! Vendored and stripped down version of triomphe
+use std::{
+    alloc::{self, Layout},
+    cmp::Ordering,
+    hash::{Hash, Hasher},
+    marker::PhantomData,
+    mem::{self, ManuallyDrop},
+    ops::Deref,
+    ptr,
+    sync::atomic::{
+        self,
+        Ordering::{Acquire, Relaxed, Release},
+    },
+};
+
+use memoffset::offset_of;
+
+/// A soft limit on the amount of references that may be made to an `Arc`.
+///
+/// Going above this limit will abort your program (although not
+/// necessarily) at _exactly_ `MAX_REFCOUNT + 1` references.
+const MAX_REFCOUNT: usize = (isize::MAX) as usize;
+
+/// The object allocated by an Arc<T>
+#[repr(C)]
+pub(crate) struct ArcInner<T: ?Sized> {
+    pub(crate) count: atomic::AtomicUsize,
+    pub(crate) data: T,
+}
+
+unsafe impl<T: ?Sized + Sync + Send> Send for ArcInner<T> {}
+unsafe impl<T: ?Sized + Sync + Send> Sync for ArcInner<T> {}
+
+/// An atomically reference counted shared pointer
+///
+/// See the documentation for [`Arc`] in the standard library. Unlike the
+/// standard library `Arc`, this `Arc` does not support weak reference counting.
+///
+/// [`Arc`]: https://doc.rust-lang.org/stable/std/sync/struct.Arc.html
+#[repr(transparent)]
+pub(crate) struct Arc<T: ?Sized> {
+    pub(crate) p: ptr::NonNull<ArcInner<T>>,
+    pub(crate) phantom: PhantomData<T>,
+}
+
+unsafe impl<T: ?Sized + Sync + Send> Send for Arc<T> {}
+unsafe impl<T: ?Sized + Sync + Send> Sync for Arc<T> {}
+
+impl<T> Arc<T> {
+    /// Reconstruct the Arc<T> from a raw pointer obtained from into_raw()
+    ///
+    /// Note: This raw pointer will be offset in the allocation and must be preceded
+    /// by the atomic count.
+    ///
+    /// It is recommended to use OffsetArc for this
+    #[inline]
+    pub(crate) unsafe fn from_raw(ptr: *const T) -> Self {
+        // To find the corresponding pointer to the `ArcInner` we need
+        // to subtract the offset of the `data` field from the pointer.
+        let ptr = (ptr as *const u8).sub(offset_of!(ArcInner<T>, data));
+        Arc { p: ptr::NonNull::new_unchecked(ptr as *mut ArcInner<T>), phantom: PhantomData }
+    }
+}
+
+impl<T: ?Sized> Arc<T> {
+    #[inline]
+    fn inner(&self) -> &ArcInner<T> {
+        // This unsafety is ok because while this arc is alive we're guaranteed
+        // that the inner pointer is valid. Furthermore, we know that the
+        // `ArcInner` structure itself is `Sync` because the inner data is
+        // `Sync` as well, so we're ok loaning out an immutable pointer to these
+        // contents.
+        unsafe { &*self.ptr() }
+    }
+
+    // Non-inlined part of `drop`. Just invokes the destructor.
+    #[inline(never)]
+    unsafe fn drop_slow(&mut self) {
+        let _ = Box::from_raw(self.ptr());
+    }
+
+    /// Test pointer equality between the two Arcs, i.e. they must be the _same_
+    /// allocation
+    #[inline]
+    pub(crate) fn ptr_eq(this: &Self, other: &Self) -> bool {
+        this.ptr() == other.ptr()
+    }
+
+    pub(crate) fn ptr(&self) -> *mut ArcInner<T> {
+        self.p.as_ptr()
+    }
+}
+
+impl<T: ?Sized> Clone for Arc<T> {
+    #[inline]
+    fn clone(&self) -> Self {
+        // Using a relaxed ordering is alright here, as knowledge of the
+        // original reference prevents other threads from erroneously deleting
+        // the object.
+        //
+        // As explained in the [Boost documentation][1], Increasing the
+        // reference counter can always be done with memory_order_relaxed: New
+        // references to an object can only be formed from an existing
+        // reference, and passing an existing reference from one thread to
+        // another must already provide any required synchronization.
+        //
+        // [1]: (www.boost.org/doc/libs/1_55_0/doc/html/atomic/usage_examples.html)
+        let old_size = self.inner().count.fetch_add(1, Relaxed);
+
+        // However we need to guard against massive refcounts in case someone
+        // is `mem::forget`ing Arcs. If we don't do this the count can overflow
+        // and users will use-after free. We racily saturate to `isize::MAX` on
+        // the assumption that there aren't ~2 billion threads incrementing
+        // the reference count at once. This branch will never be taken in
+        // any realistic program.
+        //
+        // We abort because such a program is incredibly degenerate, and we
+        // don't care to support it.
+        if old_size > MAX_REFCOUNT {
+            std::process::abort();
+        }
+
+        unsafe { Arc { p: ptr::NonNull::new_unchecked(self.ptr()), phantom: PhantomData } }
+    }
+}
+
+impl<T: ?Sized> Deref for Arc<T> {
+    type Target = T;
+
+    #[inline]
+    fn deref(&self) -> &T {
+        &self.inner().data
+    }
+}
+
+impl<T: ?Sized> Arc<T> {
+    /// Provides mutable access to the contents _if_ the `Arc` is uniquely owned.
+    #[inline]
+    pub(crate) fn get_mut(this: &mut Self) -> Option<&mut T> {
+        if this.is_unique() {
+            unsafe {
+                // See make_mut() for documentation of the threadsafety here.
+                Some(&mut (*this.ptr()).data)
+            }
+        } else {
+            None
+        }
+    }
+
+    /// Whether or not the `Arc` is uniquely owned (is the refcount 1?).
+    pub(crate) fn is_unique(&self) -> bool {
+        // See the extensive discussion in [1] for why this needs to be Acquire.
+        //
+        // [1] https://github.com/servo/servo/issues/21186
+        self.inner().count.load(Acquire) == 1
+    }
+}
+
+impl<T: ?Sized> Drop for Arc<T> {
+    #[inline]
+    fn drop(&mut self) {
+        // Because `fetch_sub` is already atomic, we do not need to synchronize
+        // with other threads unless we are going to delete the object.
+        if self.inner().count.fetch_sub(1, Release) != 1 {
+            return;
+        }
+
+        // FIXME(bholley): Use the updated comment when [2] is merged.
+        //
+        // This load is needed to prevent reordering of use of the data and
+        // deletion of the data.  Because it is marked `Release`, the decreasing
+        // of the reference count synchronizes with this `Acquire` load. This
+        // means that use of the data happens before decreasing the reference
+        // count, which happens before this load, which happens before the
+        // deletion of the data.
+        //
+        // As explained in the [Boost documentation][1],
+        //
+        // > It is important to enforce any possible access to the object in one
+        // > thread (through an existing reference) to *happen before* deleting
+        // > the object in a different thread. This is achieved by a "release"
+        // > operation after dropping a reference (any access to the object
+        // > through this reference must obviously happened before), and an
+        // > "acquire" operation before deleting the object.
+        //
+        // [1]: (www.boost.org/doc/libs/1_55_0/doc/html/atomic/usage_examples.html)
+        // [2]: https://github.com/rust-lang/rust/pull/41714
+        self.inner().count.load(Acquire);
+
+        unsafe {
+            self.drop_slow();
+        }
+    }
+}
+
+impl<T: ?Sized + PartialEq> PartialEq for Arc<T> {
+    fn eq(&self, other: &Arc<T>) -> bool {
+        Self::ptr_eq(self, other) || *(*self) == *(*other)
+    }
+
+    fn ne(&self, other: &Arc<T>) -> bool {
+        !Self::ptr_eq(self, other) && *(*self) != *(*other)
+    }
+}
+
+impl<T: ?Sized + PartialOrd> PartialOrd for Arc<T> {
+    fn partial_cmp(&self, other: &Arc<T>) -> Option<Ordering> {
+        (**self).partial_cmp(&**other)
+    }
+
+    fn lt(&self, other: &Arc<T>) -> bool {
+        *(*self) < *(*other)
+    }
+
+    fn le(&self, other: &Arc<T>) -> bool {
+        *(*self) <= *(*other)
+    }
+
+    fn gt(&self, other: &Arc<T>) -> bool {
+        *(*self) > *(*other)
+    }
+
+    fn ge(&self, other: &Arc<T>) -> bool {
+        *(*self) >= *(*other)
+    }
+}
+
+impl<T: ?Sized + Ord> Ord for Arc<T> {
+    fn cmp(&self, other: &Arc<T>) -> Ordering {
+        (**self).cmp(&**other)
+    }
+}
+
+impl<T: ?Sized + Eq> Eq for Arc<T> {}
+
+impl<T: ?Sized + Hash> Hash for Arc<T> {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        (**self).hash(state)
+    }
+}
+
+#[derive(Debug, Eq, PartialEq, Hash, PartialOrd)]
+#[repr(C)]
+pub(crate) struct HeaderSlice<H, T: ?Sized> {
+    pub(crate) header: H,
+    length: usize,
+    slice: T,
+}
+
+impl<H, T> HeaderSlice<H, [T]> {
+    pub(crate) fn slice(&self) -> &[T] {
+        &self.slice
+    }
+}
+
+impl<H, T> Deref for HeaderSlice<H, [T; 0]> {
+    type Target = HeaderSlice<H, [T]>;
+
+    fn deref(&self) -> &Self::Target {
+        unsafe {
+            let len = self.length;
+            let fake_slice: *const [T] =
+                ptr::slice_from_raw_parts(self as *const _ as *const T, len);
+            &*(fake_slice as *const HeaderSlice<H, [T]>)
+        }
+    }
+}
+
+/// A "thin" `Arc` containing dynamically sized data
+///
+/// This is functionally equivalent to `Arc<(H, [T])>`
+///
+/// When you create an `Arc` containing a dynamically sized type
+/// like `HeaderSlice<H, [T]>`, the `Arc` is represented on the stack
+/// as a "fat pointer", where the length of the slice is stored
+/// alongside the `Arc`'s pointer. In some situations you may wish to
+/// have a thin pointer instead, perhaps for FFI compatibility
+/// or space efficiency.
+///
+/// Note that we use `[T; 0]` in order to have the right alignment for `T`.
+///
+/// `ThinArc` solves this by storing the length in the allocation itself,
+/// via `HeaderSlice`.
+#[repr(transparent)]
+pub(crate) struct ThinArc<H, T> {
+    ptr: ptr::NonNull<ArcInner<HeaderSlice<H, [T; 0]>>>,
+    phantom: PhantomData<(H, T)>,
+}
+
+unsafe impl<H: Sync + Send, T: Sync + Send> Send for ThinArc<H, T> {}
+unsafe impl<H: Sync + Send, T: Sync + Send> Sync for ThinArc<H, T> {}
+
+// Synthesize a fat pointer from a thin pointer.
+fn thin_to_thick<H, T>(
+    thin: *mut ArcInner<HeaderSlice<H, [T; 0]>>,
+) -> *mut ArcInner<HeaderSlice<H, [T]>> {
+    let len = unsafe { (*thin).data.length };
+    let fake_slice: *mut [T] = ptr::slice_from_raw_parts_mut(thin as *mut T, len);
+    // Transplants metadata.
+    fake_slice as *mut ArcInner<HeaderSlice<H, [T]>>
+}
+
+impl<H, T> ThinArc<H, T> {
+    /// Temporarily converts |self| into a bonafide Arc and exposes it to the
+    /// provided callback. The refcount is not modified.
+    #[inline]
+    pub(crate) fn with_arc<F, U>(&self, f: F) -> U
+    where
+        F: FnOnce(&Arc<HeaderSlice<H, [T]>>) -> U,
+    {
+        // Synthesize transient Arc, which never touches the refcount of the ArcInner.
+        let transient = unsafe {
+            ManuallyDrop::new(Arc {
+                p: ptr::NonNull::new_unchecked(thin_to_thick(self.ptr.as_ptr())),
+                phantom: PhantomData,
+            })
+        };
+
+        // Expose the transient Arc to the callback, which may clone it if it wants.
+        let result = f(&transient);
+
+        // Forward the result.
+        result
+    }
+
+    /// Creates a `ThinArc` for a HeaderSlice using the given header struct and
+    /// iterator to generate the slice.
+    pub(crate) fn from_header_and_iter<I>(header: H, mut items: I) -> Self
+    where
+        I: Iterator<Item = T> + ExactSizeIterator,
+    {
+        assert_ne!(mem::size_of::<T>(), 0, "Need to think about ZST");
+
+        let num_items = items.len();
+
+        // Offset of the start of the slice in the allocation.
+        let inner_to_data_offset = offset_of!(ArcInner<HeaderSlice<H, [T; 0]>>, data);
+        let data_to_slice_offset = offset_of!(HeaderSlice<H, [T; 0]>, slice);
+        let slice_offset = inner_to_data_offset + data_to_slice_offset;
+
+        // Compute the size of the real payload.
+        let slice_size = mem::size_of::<T>().checked_mul(num_items).expect("size overflows");
+        let usable_size = slice_offset.checked_add(slice_size).expect("size overflows");
+
+        // Round up size to alignment.
+        let align = mem::align_of::<ArcInner<HeaderSlice<H, [T; 0]>>>();
+        let size = usable_size.wrapping_add(align - 1) & !(align - 1);
+        assert!(size >= usable_size, "size overflows");
+        let layout = Layout::from_size_align(size, align).expect("invalid layout");
+
+        let ptr: *mut ArcInner<HeaderSlice<H, [T; 0]>>;
+        unsafe {
+            let buffer = alloc::alloc(layout);
+
+            if buffer.is_null() {
+                alloc::handle_alloc_error(layout);
+            }
+
+            // // Synthesize the fat pointer. We do this by claiming we have a direct
+            // // pointer to a [T], and then changing the type of the borrow. The key
+            // // point here is that the length portion of the fat pointer applies
+            // // only to the number of elements in the dynamically-sized portion of
+            // // the type, so the value will be the same whether it points to a [T]
+            // // or something else with a [T] as its last member.
+            // let fake_slice: &mut [T] = slice::from_raw_parts_mut(buffer as *mut T, num_items);
+            // ptr = fake_slice as *mut [T] as *mut ArcInner<HeaderSlice<H, [T]>>;
+            ptr = buffer as *mut _;
+
+            let count = atomic::AtomicUsize::new(1);
+
+            // Write the data.
+            //
+            // Note that any panics here (i.e. from the iterator) are safe, since
+            // we'll just leak the uninitialized memory.
+            ptr::write(ptr::addr_of_mut!((*ptr).count), count);
+            ptr::write(ptr::addr_of_mut!((*ptr).data.header), header);
+            ptr::write(ptr::addr_of_mut!((*ptr).data.length), num_items);
+            if num_items != 0 {
+                let mut current = ptr::addr_of_mut!((*ptr).data.slice) as *mut T;
+                debug_assert_eq!(current as usize - buffer as usize, slice_offset);
+                for _ in 0..num_items {
+                    ptr::write(
+                        current,
+                        items.next().expect("ExactSizeIterator over-reported length"),
+                    );
+                    current = current.offset(1);
+                }
+                assert!(items.next().is_none(), "ExactSizeIterator under-reported length");
+
+                // We should have consumed the buffer exactly.
+                debug_assert_eq!(current as *mut u8, buffer.add(usable_size));
+            }
+            assert!(items.next().is_none(), "ExactSizeIterator under-reported length");
+        }
+
+        ThinArc { ptr: unsafe { ptr::NonNull::new_unchecked(ptr) }, phantom: PhantomData }
+    }
+}
+
+impl<H, T> Deref for ThinArc<H, T> {
+    type Target = HeaderSlice<H, [T]>;
+
+    #[inline]
+    fn deref(&self) -> &Self::Target {
+        unsafe { &(*thin_to_thick(self.ptr.as_ptr())).data }
+    }
+}
+
+impl<H, T> Clone for ThinArc<H, T> {
+    #[inline]
+    fn clone(&self) -> Self {
+        ThinArc::with_arc(self, |a| Arc::into_thin(a.clone()))
+    }
+}
+
+impl<H, T> Drop for ThinArc<H, T> {
+    #[inline]
+    fn drop(&mut self) {
+        let _ = Arc::from_thin(ThinArc { ptr: self.ptr, phantom: PhantomData });
+    }
+}
+
+impl<H, T> Arc<HeaderSlice<H, [T]>> {
+    /// Converts an `Arc` into a `ThinArc`. This consumes the `Arc`, so the refcount
+    /// is not modified.
+    #[inline]
+    pub(crate) fn into_thin(a: Self) -> ThinArc<H, T> {
+        assert_eq!(a.length, a.slice.len(), "Length needs to be correct for ThinArc to work");
+        let fat_ptr: *mut ArcInner<HeaderSlice<H, [T]>> = a.ptr();
+        mem::forget(a);
+        let thin_ptr = fat_ptr as *mut [usize] as *mut usize;
+        ThinArc {
+            ptr: unsafe {
+                ptr::NonNull::new_unchecked(thin_ptr as *mut ArcInner<HeaderSlice<H, [T; 0]>>)
+            },
+            phantom: PhantomData,
+        }
+    }
+
+    /// Converts a `ThinArc` into an `Arc`. This consumes the `ThinArc`, so the refcount
+    /// is not modified.
+    #[inline]
+    pub(crate) fn from_thin(a: ThinArc<H, T>) -> Self {
+        let ptr = thin_to_thick(a.ptr.as_ptr());
+        mem::forget(a);
+        unsafe { Arc { p: ptr::NonNull::new_unchecked(ptr), phantom: PhantomData } }
+    }
+}
+
+impl<H: PartialEq, T: PartialEq> PartialEq for ThinArc<H, T> {
+    #[inline]
+    fn eq(&self, other: &ThinArc<H, T>) -> bool {
+        **self == **other
+    }
+}
+
+impl<H: Eq, T: Eq> Eq for ThinArc<H, T> {}
+
+impl<H: Hash, T: Hash> Hash for ThinArc<H, T> {
+    fn hash<HSR: Hasher>(&self, state: &mut HSR) {
+        (**self).hash(state)
+    }
+}