avoid deadlocks by no longer returning read guard

5 files changed, 103 insertions, 18 deletions

diff --git a/incria/Cargo.lock b/incria/Cargo.lock
index 315a8a8..9a19675 100644
--- a/incria/Cargo.lock
+++ b/incria/Cargo.lock
@@ -3,6 +3,12 @@
 version = 3
 
 [[package]]
+name = "allocator-api2"
+version = "0.2.15"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "56fc6cf8dc8c4158eed8649f9b8b0ea1518eb62b544fe9490d66fa0b349eafe9"
+
+[[package]]
 name = "anes"
 version = "0.1.6"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -32,6 +38,16 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "bef38d45163c2f1dde094a7dfd33ccf595c92905c8f8f4fdc18d06fb1037718a"
 
 [[package]]
+name = "blink-alloc"
+version = "0.3.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "eedafeef9c2d56b08e6d14b0f9b22e371261a38c81cbfc69a4014b0f2d1094a7"
+dependencies = [
+ "allocator-api2",
+ "parking_lot",
+]
+
+[[package]]
 name = "bumpalo"
 version = "3.13.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -279,6 +295,7 @@ dependencies = [
 name = "incria"
 version = "0.1.0"
 dependencies = [
+ "blink-alloc",
  "criterion",
  "tokio",
 ]
@@ -330,6 +347,16 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "2b00cc1c228a6782d0f076e7b232802e0c5689d41bb5df366f2a6b6621cfdfe1"
 
 [[package]]
+name = "lock_api"
+version = "0.4.10"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "c1cc9717a20b1bb222f333e6a92fd32f7d8a18ddc5a3191a11af45dcbf4dcd16"
+dependencies = [
+ "autocfg",
+ "scopeguard",
+]
+
+[[package]]
 name = "log"
 version = "0.4.18"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -382,6 +409,29 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "ceedf44fb00f2d1984b0bc98102627ce622e083e49a5bacdb3e514fa4238e267"
 
 [[package]]
+name = "parking_lot"
+version = "0.12.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3742b2c103b9f06bc9fff0a37ff4912935851bee6d36f3c02bcc755bcfec228f"
+dependencies = [
+ "lock_api",
+ "parking_lot_core",
+]
+
+[[package]]
+name = "parking_lot_core"
+version = "0.9.8"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "93f00c865fe7cabf650081affecd3871070f26767e7b2070a3ffae14c654b447"
+dependencies = [
+ "cfg-if",
+ "libc",
+ "redox_syscall",
+ "smallvec",
+ "windows-targets",
+]
+
+[[package]]
 name = "pin-project-lite"
 version = "0.2.9"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -462,6 +512,15 @@ dependencies = [
 ]
 
 [[package]]
+name = "redox_syscall"
+version = "0.3.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "567664f262709473930a4bf9e51bf2ebf3348f2e748ccc50dea20646858f8f29"
+dependencies = [
+ "bitflags",
+]
+
+[[package]]
 name = "regex"
 version = "1.8.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -529,6 +588,12 @@ dependencies = [
 ]
 
 [[package]]
+name = "smallvec"
+version = "1.10.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a507befe795404456341dfab10cef66ead4c041f62b8b11bbb92bffe5d0953e0"
+
+[[package]]
 name = "syn"
 version = "2.0.16"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/incria/Cargo.toml b/incria/Cargo.toml
index 2dbe28a..55e6cdf 100644
--- a/incria/Cargo.toml
+++ b/incria/Cargo.toml
@@ -4,6 +4,7 @@ version = "0.1.0"
 edition = "2021"
 
 [dependencies]
+blink-alloc = { version = "0.3.0", features = ["sync"] }
 tokio = { version = "1.28.1", features = ["sync", "rt"] }
 
 [dev-dependencies]
@@ -16,4 +17,4 @@ path = "benches/pascal.rs"
 
 [[bench]]
 name = "pascal"
-harness = false
\ No newline at end of file
+harness = false
diff --git a/incria/benches/pascal.rs b/incria/benches/pascal.rs
index 3c06de1..01befe5 100644
--- a/incria/benches/pascal.rs
+++ b/incria/benches/pascal.rs
@@ -85,7 +85,7 @@ fn benchmarks_with_n(c: &mut Criterion, n: isize) {
 
 #[inline(always)]
 async fn do_calc(key: &Key) {
-    drop(deps::with_node_id(deps::next_node_id(), pascal_mapping().get(key)).await);
+    deps::with_node_id(deps::next_node_id(), pascal_mapping().get(key)).await;
 }
 
 #[inline(always)]
diff --git a/incria/src/lazy_mapping.rs b/incria/src/lazy_mapping.rs
index bef3a3d..27bd76e 100644
--- a/incria/src/lazy_mapping.rs
+++ b/incria/src/lazy_mapping.rs
@@ -1,5 +1,8 @@
-use std::{collections::HashMap, future::Future, hash::Hash, sync::Arc};
+use std::{
+    collections::HashMap, fmt::Debug, future::Future, hash::Hash, mem::transmute, sync::Arc,
+};
 
+use blink_alloc::{Blink, SyncBlinkAlloc};
 use tokio::sync::{Mutex, Notify, RwLock, RwLockReadGuard};
 
 use crate::{
@@ -12,13 +15,15 @@ pub trait LazyMappingBackend<K, V> {
     fn compute(&self, key: K) -> impl Future<Output = V> + Send + '_;
 }
 
-#[derive(Debug, Default)]
-pub struct LazyMapper<K, V, B> {
+#[derive(Default)]
+pub struct LazyMapper<K, V: 'static, B> {
     /// The backend we use to compute values and check dirtiness
     backend: B,
 
+    values: SyncBlinkAlloc,
+
     /// Map of all values we've calculated already
-    calculated: RwLock<HashMap<K, (V, NodeId)>>,
+    calculated: RwLock<HashMap<K, (&'static V, NodeId)>>,
 
     /// Values we're currently calculating
     /// The Notify will be triggered when computation is done.
@@ -34,6 +39,7 @@ impl<K: Clone + Eq + Hash + Send + Sync, V: Send + Sync, B: LazyMappingBackend<K
             backend,
             calculated: RwLock::default(),
             waiting: Mutex::default(),
+            values: SyncBlinkAlloc::new(),
         }
     }
 
@@ -50,24 +56,24 @@ impl<K: Clone + Eq + Hash + Send + Sync, V: Send + Sync, B: LazyMappingBackend<K
 
 impl<K, V, B> Mapper for LazyMapper<K, V, B>
 where
-    K: Clone + Eq + Hash + Send + Sync,
-    V: Send + Sync,
+    K: Clone + Eq + Hash + Send + Sync + Debug,
+    V: Send + Sync + 'static,
     B: LazyMappingBackend<K, V>,
 {
     type Key = K;
     type Value = V;
-    type Wrapper<'a> = RwLockReadGuard<'a, V> where V: 'a;
+    type Wrapper<'a> = &'a V where V: 'a;
 
     async fn get<'a>(&'a self, key: &Self::Key) -> Self::Wrapper<'a> {
         // Attempt to reuse or evict the existing value
         let mut reuse_dep_id = None;
         {
             let finished = self.calculated.read().await;
-            if let Some((_, node)) = finished.get(key) {
+            if let Some((val, node)) = finished.get(key) {
                 let dirty = deps::is_dirty(*node) || self.backend.is_dirty(key).await;
                 if !dirty {
                     deps::add_dep(*node);
-                    return RwLockReadGuard::map(finished, |hm| &hm.get(key).unwrap().0);
+                    return val;
                 } else {
                     reuse_dep_id = Some(*node);
                     drop(finished);
@@ -85,10 +91,12 @@ where
             // Waiting for completion
             barrier.notified().await;
 
-            let val = RwLockReadGuard::map(self.calculated.read().await, |hm| hm.get(key).unwrap());
-            deps::add_dep(val.1);
+            let (value, node_id) =
+                *RwLockReadGuard::map(self.calculated.read().await, |hm| hm.get(key).unwrap());
+
+            deps::add_dep(node_id);
 
-            return RwLockReadGuard::map(val, |inf| &inf.0);
+            value
         } else {
             // Needs calculated
             let notify = Arc::new(Notify::new());
@@ -105,19 +113,26 @@ where
             };
 
             let val = deps::with_node_id(dep, self.backend.compute(key.clone())).await;
+            let val_ref: &'static V = unsafe { transmute(Blink::new_in(&self.values).put(val)) };
             deps::add_dep(dep);
 
             self.calculated
                 .write()
                 .await
-                .insert(key.clone(), (val, dep));
+                .insert(key.clone(), (val_ref, dep));
             self.waiting.lock().await.remove(key);
 
             notify.notify_waiters();
 
-            return RwLockReadGuard::map(self.calculated.read().await, |hm| {
-                &hm.get(key).unwrap().0
-            });
+            val_ref
         }
     }
 }
+
+impl<K: Debug, V: Debug, B: Debug> Debug for LazyMapper<K, V, B> {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        f.debug_struct("LazyMapper")
+            .field("backend", &self.backend)
+            .finish_non_exhaustive()
+    }
+}
diff --git a/incria/src/thunk.rs b/incria/src/thunk.rs
index 937f109..2fe7873 100644
--- a/incria/src/thunk.rs
+++ b/incria/src/thunk.rs
@@ -19,6 +19,10 @@ impl<T> ThunkBackend<T> {
     pub fn new(thunk: T) -> Self {
         Self { thunk }
     }
+
+    pub fn thunk(&self) -> &T {
+        &self.thunk
+    }
 }
 
 impl<K, V: 'static, T> LazyMappingBackend<K, V> for ThunkBackend<T>