5 files changed, 156 insertions, 21 deletions

diff --git a/src/collection/boxed_collection.rs b/src/collection/boxed_collection.rs
index bcb941b..1aae1e4 100644
--- a/src/collection/boxed_collection.rs
+++ b/src/collection/boxed_collection.rs
@@ -26,7 +26,7 @@ impl<'a, L> Drop for BoxedLockCollection<'a, L> {
 	}
 }
 
-impl<'a, L: OwnedLockable<'a> + 'a> BoxedLockCollection<'a, L> {
+impl<'a, L: OwnedLockable> BoxedLockCollection<'a, L> {
 	#[must_use]
 	pub fn new(data: L) -> Self {
 		let boxed = Box::leak(Box::new(data));
@@ -34,18 +34,18 @@ impl<'a, L: OwnedLockable<'a> + 'a> BoxedLockCollection<'a, L> {
 	}
 }
 
-impl<'a, L: OwnedLockable<'a> + 'a> BoxedLockCollection<'a, &'a L> {
+impl<'a, L: OwnedLockable> BoxedLockCollection<'a, &'a L> {
 	#[must_use]
 	pub fn new_ref(data: &'a L) -> Self {
 		let boxed = Box::leak(Box::new(data));
 
-		// this is a reference to an OwnedLockable, which can't possibly
-		// contain inner duplicates
+		// safety: this is a reference to an OwnedLockable, which can't
+		//         possibly contain inner duplicates
 		Self(unsafe { RefLockCollection::new_unchecked(boxed) })
 	}
 }
 
-impl<'a, L: Lockable<'a> + 'a> BoxedLockCollection<'a, L> {
+impl<'a, L: Lockable> BoxedLockCollection<'a, L> {
 	#[must_use]
 	pub unsafe fn new_unchecked(data: L) -> Self {
 		let boxed = Box::leak(Box::new(data));
diff --git a/src/collection/guard.rs b/src/collection/guard.rs
index 3b98d29..e3ffb21 100644
--- a/src/collection/guard.rs
+++ b/src/collection/guard.rs
@@ -4,15 +4,15 @@ use crate::{key::Keyable, Lockable};
 
 use super::LockGuard;
 
-impl<'a, 'key: 'a, L: Lockable<'a>, Key: Keyable> Deref for LockGuard<'a, 'key, L, Key> {
-	type Target = L::Guard;
+impl<'a, 'key: 'a, L: Lockable + 'a, Key: Keyable> Deref for LockGuard<'a, 'key, L, Key> {
+	type Target = L::Guard<'a>;
 
 	fn deref(&self) -> &Self::Target {
 		&self.guard
 	}
 }
 
-impl<'a, 'key: 'a, L: Lockable<'a>, Key: Keyable> DerefMut for LockGuard<'a, 'key, L, Key> {
+impl<'a, 'key: 'a, L: Lockable + 'a, Key: Keyable> DerefMut for LockGuard<'a, 'key, L, Key> {
 	fn deref_mut(&mut self) -> &mut Self::Target {
 		&mut self.guard
 	}
diff --git a/src/collection/owned_collection.rs b/src/collection/owned_collection.rs
index dbc9a45..ea8f2f2 100644
--- a/src/collection/owned_collection.rs
+++ b/src/collection/owned_collection.rs
@@ -4,22 +4,19 @@ use crate::{lockable::Lock, Keyable, Lockable, OwnedLockable};
 
 use super::{LockGuard, OwnedLockCollection};
 
-fn get_locks<'a, L: Lockable<'a> + 'a>(data: &'a L) -> Vec<&'a dyn Lock> {
+fn get_locks<L: Lockable>(data: &L) -> Vec<&dyn Lock> {
 	let mut locks = Vec::new();
 	data.get_ptrs(&mut locks);
 	locks
 }
 
-impl<'a, L: OwnedLockable<'a>> OwnedLockCollection<L> {
+impl<L: OwnedLockable> OwnedLockCollection<L> {
 	#[must_use]
 	pub const fn new(data: L) -> Self {
 		Self { data }
 	}
 
-	pub fn lock<'s: 'a, 'key, Key: Keyable + 'key>(
-		&'s self,
-		key: Key,
-	) -> LockGuard<'a, 'key, L, Key> {
+	pub fn lock<'a, 'key, Key: Keyable + 'key>(&'a self, key: Key) -> LockGuard<'a, 'key, L, Key> {
 		let locks = get_locks(&self.data);
 		for lock in locks {
 			// safety: we have the thread key, and these locks happen in a
@@ -36,7 +33,7 @@ impl<'a, L: OwnedLockable<'a>> OwnedLockCollection<L> {
 		}
 	}
 
-	pub fn try_lock<'key: 'a, Key: Keyable + 'key>(
+	pub fn try_lock<'a, 'key: 'a, Key: Keyable + 'key>(
 		&'a self,
 		key: Key,
 	) -> Option<LockGuard<'a, 'key, L, Key>> {
diff --git a/src/collection/ref_collection.rs b/src/collection/ref_collection.rs
index 9dfa0e9..41f6b16 100644
--- a/src/collection/ref_collection.rs
+++ b/src/collection/ref_collection.rs
@@ -5,7 +5,7 @@ use crate::{key::Keyable, lockable::Lock, Lockable, OwnedLockable};
 use super::{LockGuard, RefLockCollection};
 
 #[must_use]
-fn get_locks<'a, L: Lockable<'a> + 'a>(data: &'a L) -> Vec<&'a dyn Lock> {
+fn get_locks<L: Lockable>(data: &L) -> Vec<&dyn Lock> {
 	let mut locks = Vec::new();
 	data.get_ptrs(&mut locks);
 	locks.sort_by_key(|lock| std::ptr::from_ref(*lock));
@@ -19,19 +19,19 @@ fn contains_duplicates(l: &[&dyn Lock]) -> bool {
 		.any(|window| std::ptr::eq(window[0], window[1]))
 }
 
-impl<'a, L: Lockable<'a>> AsRef<L> for RefLockCollection<'a, L> {
+impl<'a, L: Lockable> AsRef<L> for RefLockCollection<'a, L> {
 	fn as_ref(&self) -> &L {
 		self.data
 	}
 }
 
-impl<'a, L: Lockable<'a>> AsRef<Self> for RefLockCollection<'a, L> {
+impl<'a, L: Lockable> AsRef<Self> for RefLockCollection<'a, L> {
 	fn as_ref(&self) -> &Self {
 		self
 	}
 }
 
-impl<'a, L: Lockable<'a>> AsMut<Self> for RefLockCollection<'a, L> {
+impl<'a, L: Lockable> AsMut<Self> for RefLockCollection<'a, L> {
 	fn as_mut(&mut self) -> &mut Self {
 		self
 	}
@@ -49,7 +49,7 @@ where
 	}
 }
 
-impl<'a, L: OwnedLockable<'a> + 'a> RefLockCollection<'a, L> {
+impl<'a, L: OwnedLockable> RefLockCollection<'a, L> {
 	/// Creates a new collection of owned locks.
 	///
 	/// Because the locks are owned, there's no need to do any checks for
@@ -72,7 +72,7 @@ impl<'a, L: OwnedLockable<'a> + 'a> RefLockCollection<'a, L> {
 	}
 }
 
-impl<'a, L: Lockable<'a>> RefLockCollection<'a, L> {
+impl<'a, L: Lockable> RefLockCollection<'a, L> {
 	/// Creates a new collections of locks.
 	///
 	/// # Safety
diff --git a/src/collection/retry_collection.rs b/src/collection/retry_collection.rs
new file mode 100644
index 0000000..73f9e18
--- /dev/null
+++ b/src/collection/retry_collection.rs
@@ -0,0 +1,138 @@
+use std::marker::PhantomData;
+
+use crate::{lockable::Lock, Keyable, Lockable, OwnedLockable};
+
+use super::{LockGuard, RetryingLockCollection};
+
+fn contains_duplicates<L: Lockable>(data: L) -> bool {
+	let mut locks = Vec::new();
+	data.get_ptrs(&mut locks);
+	let mut locks: Vec<_> = locks.into_iter().map(|l| l as *const dyn Lock).collect();
+	locks.sort_unstable();
+	locks.windows(2).any(|w| std::ptr::addr_eq(w[0], w[1]))
+}
+
+impl<L: OwnedLockable> RetryingLockCollection<L> {
+	#[must_use]
+	pub const fn new(data: L) -> Self {
+		Self { data }
+	}
+}
+
+impl<'a, L: OwnedLockable> RetryingLockCollection<&'a L> {
+	#[must_use]
+	pub const fn new_ref(data: &'a L) -> Self {
+		Self { data }
+	}
+}
+
+impl<L: Lockable> RetryingLockCollection<L> {
+	#[must_use]
+	pub const unsafe fn new_unchecked(data: L) -> Self {
+		Self { data }
+	}
+
+	pub fn try_new(data: L) -> Option<Self> {
+		contains_duplicates(&data).then_some(Self { data })
+	}
+
+	pub fn lock<'a, 'key: 'a, Key: Keyable + 'key>(
+		&'a self,
+		key: Key,
+	) -> LockGuard<'a, 'key, L, Key> {
+		let mut first_index = 0;
+		let mut locks = Vec::new();
+		self.data.get_ptrs(&mut locks);
+
+		if locks.is_empty() {
+			return LockGuard {
+				// safety: there's no data being returned
+				guard: unsafe { self.data.guard() },
+				key,
+				_phantom: PhantomData,
+			};
+		}
+
+		let guard = unsafe {
+			'outer: loop {
+				// safety: we have the thread key
+				locks[first_index].lock();
+				for (i, lock) in locks.iter().enumerate() {
+					if i == first_index {
+						continue;
+					}
+
+					// safety: we have the thread key
+					if !lock.try_lock() {
+						for lock in locks.iter().take(i) {
+							// safety: we already locked all of these
+							lock.unlock();
+						}
+
+						if first_index >= i {
+							// safety: this is already locked and can't be unlocked
+							//         by the previous loop
+							locks[first_index].unlock();
+						}
+
+						first_index = i;
+						continue 'outer;
+					}
+				}
+
+				// safety: we locked all the data
+				break self.data.guard();
+			}
+		};
+
+		LockGuard {
+			guard,
+			key,
+			_phantom: PhantomData,
+		}
+	}
+
+	pub fn try_lock<'a, 'key: 'a, Key: Keyable + 'key>(
+		&'a self,
+		key: Key,
+	) -> Option<LockGuard<'a, 'key, L, Key>> {
+		let mut locks = Vec::new();
+		self.data.get_ptrs(&mut locks);
+
+		if locks.is_empty() {
+			return Some(LockGuard {
+				// safety: there's no data being returned
+				guard: unsafe { self.data.guard() },
+				key,
+				_phantom: PhantomData,
+			});
+		}
+
+		let guard = unsafe {
+			for (i, lock) in locks.iter().enumerate() {
+				// safety: we have the thread key
+				if !lock.try_lock() {
+					for lock in locks.iter().take(i) {
+						// safety: we already locked all of these
+						lock.unlock();
+					}
+					return None;
+				}
+			}
+
+			// safety: we locked all the data
+			self.data.guard()
+		};
+
+		Some(LockGuard {
+			guard,
+			key,
+			_phantom: PhantomData,
+		})
+	}
+
+	pub fn unlock<'key, Key: Keyable + 'key>(guard: LockGuard<'_, 'key, L, Key>) -> Key {
+		drop(guard.guard);
+		guard.key
+	}
+}