From 8cf9c2719652d298006d51bc82a32908ab4e5335 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Wed, 12 Sep 2018 21:50:15 +0300 Subject: generic salsa algo --- crates/salsa/src/lib.rs | 238 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 238 insertions(+) create mode 100644 crates/salsa/src/lib.rs (limited to 'crates/salsa/src') diff --git a/crates/salsa/src/lib.rs b/crates/salsa/src/lib.rs new file mode 100644 index 000000000..69c7b35fa --- /dev/null +++ b/crates/salsa/src/lib.rs @@ -0,0 +1,238 @@ +extern crate im; +extern crate parking_lot; + +use std::{ + sync::Arc, + any::Any, + collections::HashMap, + cell::RefCell, +}; +use parking_lot::Mutex; + +type GroundQueryFn = fn(&T, &(Any + Send + Sync + 'static)) -> (Box, OutputFingerprint); +type QueryFn = fn(&QueryCtx, &(Any + Send + Sync + 'static)) -> (Box, OutputFingerprint); + +#[derive(Debug)] +pub struct Db { + db: Arc>, + query_config: Arc>, +} + +pub struct QueryConfig { + ground_fn: HashMap>, + query_fn: HashMap>, +} + +impl ::std::fmt::Debug for QueryConfig { + fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result { + ::std::fmt::Display::fmt("QueryConfig { ... }", f) + } +} + +#[derive(Debug)] +struct DbState { + ground_data: T, + gen: Gen, + graph: Mutex)>>, +} + +#[derive(Debug)] +struct QueryRecord { + params: Arc, + output: Arc, + output_fingerprint: OutputFingerprint, + deps: Vec<(QueryId, OutputFingerprint)>, +} + +impl DbState { + fn record( + &self, + query_id: QueryId, + params: Arc, + output: Arc, + output_fingerprint: OutputFingerprint, + deps: Vec<(QueryId, OutputFingerprint)>, + ) { + let gen = self.gen; + let record = QueryRecord { + params, + output, + output_fingerprint, + deps, + }; + self.graph.lock().insert(query_id, (gen, Arc::new(record))); + } +} + +impl QueryConfig { + pub fn new() -> Self { + QueryConfig { + ground_fn: HashMap::new(), + query_fn: HashMap::new(), + } + } + pub fn with_ground_query( + mut self, + query_type: QueryTypeId, + query_fn: GroundQueryFn + ) -> Self { + let prev = self.ground_fn.insert(query_type, query_fn); + assert!(prev.is_none()); + self + } + pub fn with_query( + mut self, + query_type: QueryTypeId, + query_fn: QueryFn, + ) -> Self { + let prev = self.query_fn.insert(query_type, query_fn); + assert!(prev.is_none()); + self + } +} + +pub struct QueryCtx { + db: Arc>, + query_config: Arc>, + stack: RefCell>>, + executed: RefCell>, +} + +impl QueryCtx { + fn new(db: &Db) -> QueryCtx { + QueryCtx { + db: Arc::clone(&db.db), + query_config: Arc::clone(&db.query_config), + stack: RefCell::new(vec![Vec::new()]), + executed: RefCell::new(Vec::new()), + } + } + pub fn get( + &self, + query_id: QueryId, + params: Arc, + ) -> Arc { + let (res, output_fingerprint) = self.get_inner(query_id, params); + self.record_dep(query_id, output_fingerprint); + res + } + + pub fn get_inner( + &self, + query_id: QueryId, + params: Arc, + ) -> (Arc, OutputFingerprint) { + let (gen, record) = { + let guard = self.db.graph.lock(); + match guard.get(&query_id).map(|it| it.clone()){ + None => { + drop(guard); + return self.force(query_id, params); + }, + Some(it) => it, + } + }; + if gen == self.db.gen { + return (record.output.clone(), record.output_fingerprint) + } + if self.query_config.ground_fn.contains_key(&query_id.0) { + return self.force(query_id, params); + } + for (dep_query_id, prev_fingerprint) in record.deps.iter().cloned() { + let dep_params: Arc = { + let guard = self.db.graph.lock(); + guard[&dep_query_id] + .1 + .params + .clone() + }; + if prev_fingerprint != self.get_inner(dep_query_id, dep_params).1 { + return self.force(query_id, params) + } + } + let gen = self.db.gen; + { + let mut guard = self.db.graph.lock(); + guard[&query_id].0 = gen; + } + (record.output.clone(), record.output_fingerprint) + } + fn force( + &self, + query_id: QueryId, + params: Arc, + ) -> (Arc, OutputFingerprint) { + self.executed.borrow_mut().push(query_id.0); + self.stack.borrow_mut().push(Vec::new()); + + let (res, output_fingerprint) = if let Some(f) = self.ground_query_fn_by_type(query_id.0) { + f(&self.db.ground_data, &*params) + } else if let Some(f) = self.query_fn_by_type(query_id.0) { + f(self, &*params) + } else { + panic!("unknown query type: {:?}", query_id.0); + }; + + let res: Arc = res.into(); + + let deps = self.stack.borrow_mut().pop().unwrap(); + self.db.record(query_id, params, res.clone(), output_fingerprint, deps); + (res, output_fingerprint) + } + fn ground_query_fn_by_type(&self, query_type: QueryTypeId) -> Option> { + self.query_config.ground_fn.get(&query_type).map(|&it| it) + } + fn query_fn_by_type(&self, query_type: QueryTypeId) -> Option> { + self.query_config.query_fn.get(&query_type).map(|&it| it) + } + fn record_dep( + &self, + query_id: QueryId, + output_fingerprint: OutputFingerprint, + ) -> () { + let mut stack = self.stack.borrow_mut(); + let deps = stack.last_mut().unwrap(); + deps.push((query_id, output_fingerprint)) + } +} + +impl Db { + pub fn new(query_config: QueryConfig, ground_data: T) -> Db { + Db { + db: Arc::new(DbState { ground_data, gen: Gen(0), graph: Default::default() }), + query_config: Arc::new(query_config), + } + } + + pub fn with_ground_data(&self, ground_data: T) -> Db { + let gen = Gen(self.db.gen.0 + 1); + let graph = self.db.graph.lock().clone(); + let graph = Mutex::new(graph); + Db { + db: Arc::new(DbState { ground_data, gen, graph }), + query_config: Arc::clone(&self.query_config) + } + } + pub fn get( + &self, + query_id: QueryId, + params: Box, + ) -> (Arc, Vec) { + let ctx = QueryCtx::new(self); + let res = ctx.get(query_id, params.into()); + let executed = ::std::mem::replace(&mut *ctx.executed.borrow_mut(), Vec::new()); + (res, executed) + } +} + +#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] +struct Gen(u64); +#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] +pub struct InputFingerprint(pub u64); +#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] +pub struct OutputFingerprint(pub u64); +#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] +pub struct QueryTypeId(pub u16); +#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] +pub struct QueryId(pub QueryTypeId, pub InputFingerprint); + -- cgit v1.2.3