From 93d77e9b22c38a3587f3b7d5c3c6d517b66f3314 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Sun, 7 Oct 2018 11:32:21 +0300 Subject: remove our own copy of salsa salsa-rs/salsa is faster and more type safe --- crates/salsa/Cargo.toml | 8 -- crates/salsa/src/lib.rs | 293 -------------------------------------- crates/salsa/tests/integration.rs | 170 ---------------------- 3 files changed, 471 deletions(-) delete mode 100644 crates/salsa/Cargo.toml delete mode 100644 crates/salsa/src/lib.rs delete mode 100644 crates/salsa/tests/integration.rs diff --git a/crates/salsa/Cargo.toml b/crates/salsa/Cargo.toml deleted file mode 100644 index 9eb83234f..000000000 --- a/crates/salsa/Cargo.toml +++ /dev/null @@ -1,8 +0,0 @@ -[package] -name = "salsa" -version = "0.1.0" -authors = ["Aleksey Kladov "] - -[dependencies] -parking_lot = "0.6.3" -im = "12.0.0" diff --git a/crates/salsa/src/lib.rs b/crates/salsa/src/lib.rs deleted file mode 100644 index 35deed374..000000000 --- a/crates/salsa/src/lib.rs +++ /dev/null @@ -1,293 +0,0 @@ -extern crate im; -extern crate parking_lot; - -use std::{ - sync::Arc, - collections::{HashSet, HashMap}, - cell::RefCell, -}; -use parking_lot::Mutex; - -pub type GroundQueryFn = Box (D, OutputFingerprint) + Send + Sync + 'static>; -pub type QueryFn = Box, &D) -> (D, OutputFingerprint) + Send + Sync + 'static>; - -#[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: D, - output: D, - output_fingerprint: OutputFingerprint, - deps: Vec<(QueryId, OutputFingerprint)>, -} - -impl DbState { - fn record( - &self, - query_id: QueryId, - params: D, - output: D, - 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 -where - D: Clone -{ - 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: D, - ) -> D { - let (res, output_fingerprint) = self.get_inner(query_id, params); - self.record_dep(query_id, output_fingerprint); - res - } - pub fn trace(&self) -> Vec { - ::std::mem::replace(&mut *self.executed.borrow_mut(), Vec::new()) - } - - fn get_inner( - &self, - query_id: QueryId, - params: D, - ) -> (D, 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) { - let (invalidated, record) = { - let guard = self.db.graph.lock(); - let (gen, ref record) = guard[&query_id]; - (gen == INVALIDATED, record.clone()) - }; - if invalidated { - return self.force(query_id, params); - } else { - return (record.output.clone(), record.output_fingerprint); - } - } - for (dep_query_id, prev_fingerprint) in record.deps.iter().cloned() { - let dep_params: D = { - 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: D, - ) -> (D, 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.query_config.ground_fn.get(&query_id.0) { - f(&self.db.ground_data, ¶ms) - } else if let Some(f) = self.query_config.query_fn.get(&query_id.0) { - f(self, ¶ms) - } else { - panic!("unknown query type: {:?}", query_id.0); - }; - - let res: D = 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 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)) - } -} - -pub struct Invalidations { - types: HashSet, - ids: Vec, -} - -impl Invalidations { - pub fn new() -> Invalidations { - Invalidations { - types: HashSet::new(), - ids: Vec::new(), - } - } - pub fn invalidate( - &mut self, - query_type: QueryTypeId, - params: impl Iterator, - ) { - self.types.insert(query_type); - self.ids.extend(params.map(|it| QueryId(query_type, it))) - } -} - -impl Db -where - D: Clone -{ - 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 ground_data(&self) -> &T { - &self.db.ground_data - } - pub fn with_ground_data( - &self, - ground_data: T, - invalidations: Invalidations, - ) -> Db { - for id in self.query_config.ground_fn.keys() { - assert!( - invalidations.types.contains(id), - "all ground queries must be invalidated" - ); - } - - let gen = Gen(self.db.gen.0 + 1); - let mut graph = self.db.graph.lock().clone(); - for id in invalidations.ids { - if let Some((gen, _)) = graph.get_mut(&id) { - *gen = INVALIDATED; - } - } - let graph = Mutex::new(graph); - Db { - db: Arc::new(DbState { ground_data, gen, graph }), - query_config: Arc::clone(&self.query_config) - } - } - pub fn query_ctx(&self) -> QueryCtx { - QueryCtx::new(self) - } - pub fn get( - &self, - query_id: QueryId, - params: D, - ) -> (D, Vec) { - let ctx = self.query_ctx(); - 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); -const INVALIDATED: Gen = Gen(!0); -#[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); - diff --git a/crates/salsa/tests/integration.rs b/crates/salsa/tests/integration.rs deleted file mode 100644 index aed9219be..000000000 --- a/crates/salsa/tests/integration.rs +++ /dev/null @@ -1,170 +0,0 @@ -extern crate salsa; -use std::{ - iter::once, - sync::Arc, - collections::hash_map::{HashMap, DefaultHasher}, - any::Any, - hash::{Hash, Hasher}, -}; - -type State = HashMap; -type Data = Arc; -const GET_TEXT: salsa::QueryTypeId = salsa::QueryTypeId(1); -const GET_FILES: salsa::QueryTypeId = salsa::QueryTypeId(2); -const FILE_NEWLINES: salsa::QueryTypeId = salsa::QueryTypeId(3); -const TOTAL_NEWLINES: salsa::QueryTypeId = salsa::QueryTypeId(4); - -fn mk_ground_query( - state: &State, - params: &Data, - f: fn(&State, &T) -> R, -) -> (Data, salsa::OutputFingerprint) -where - T: 'static, - R: Hash + Send + Sync + 'static, -{ - let params = params.downcast_ref().unwrap(); - let result = f(state, params); - let fingerprint = o_print(&result); - (Arc::new(result), fingerprint) -} - -fn get(db: &salsa::Db, query_type: salsa::QueryTypeId, param: T) -> (Arc, Vec) -where - T: Hash + Send + Sync + 'static, - R: Send + Sync + 'static, -{ - let i_print = i_print(¶m); - let param = Arc::new(param); - let (res, trace) = db.get(salsa::QueryId(query_type, i_print), param); - (res.downcast().unwrap(), trace) -} - -struct QueryCtx<'a>(&'a salsa::QueryCtx); - -impl<'a> QueryCtx<'a> { - fn get_text(&self, id: u32) -> Arc { - let i_print = i_print(&id); - let text = self.0.get(salsa::QueryId(GET_TEXT, i_print), Arc::new(id)); - text.downcast().unwrap() - } - fn get_files(&self) -> Arc> { - let i_print = i_print(&()); - let files = self.0.get(salsa::QueryId(GET_FILES, i_print), Arc::new(())); - let res = files.downcast().unwrap(); - res - } - fn get_n_lines(&self, id: u32) -> usize { - let i_print = i_print(&id); - let n_lines = self.0.get(salsa::QueryId(FILE_NEWLINES, i_print), Arc::new(id)); - *n_lines.downcast().unwrap() - } -} - -fn mk_query( - query_ctx: &salsa::QueryCtx, - params: &Data, - f: fn(QueryCtx, &T) -> R, -) -> (Data, salsa::OutputFingerprint) -where - T: 'static, - R: Hash + Send + Sync + 'static, -{ - let params: &T = params.downcast_ref().unwrap(); - let query_ctx = QueryCtx(query_ctx); - let result = f(query_ctx, params); - let fingerprint = o_print(&result); - (Arc::new(result), fingerprint) -} - -fn mk_queries() -> salsa::QueryConfig { - salsa::QueryConfig::::new() - .with_ground_query(GET_TEXT, Box::new(|state, id| { - mk_ground_query::(state, id, |state, id| state[id].clone()) - })) - .with_ground_query(GET_FILES, Box::new(|state, id| { - mk_ground_query::<(), Vec>(state, id, |state, &()| state.keys().cloned().collect()) - })) - .with_query(FILE_NEWLINES, Box::new(|query_ctx, id| { - mk_query(query_ctx, id, |query_ctx, &id| { - let text = query_ctx.get_text(id); - text.lines().count() - }) - })) - .with_query(TOTAL_NEWLINES, Box::new(|query_ctx, id| { - mk_query(query_ctx, id, |query_ctx, &()| { - let mut total = 0; - for &id in query_ctx.get_files().iter() { - total += query_ctx.get_n_lines(id) - } - total - }) - })) -} - -#[test] -fn test_number_of_lines() { - let mut state = State::new(); - let db = salsa::Db::new(mk_queries(), state.clone()); - let (newlines, trace) = get::<(), usize>(&db, TOTAL_NEWLINES, ()); - assert_eq!(*newlines, 0); - assert_eq!(trace.len(), 2); - let (newlines, trace) = get::<(), usize>(&db, TOTAL_NEWLINES, ()); - assert_eq!(*newlines, 0); - assert_eq!(trace.len(), 0); - - state.insert(1, "hello\nworld".to_string()); - let mut inv = salsa::Invalidations::new(); - inv.invalidate(GET_TEXT, once(i_print(&1u32))); - inv.invalidate(GET_FILES, once(i_print(&()))); - let db = db.with_ground_data(state.clone(), inv); - let (newlines, trace) = get::<(), usize>(&db, TOTAL_NEWLINES, ()); - assert_eq!(*newlines, 2); - assert_eq!(trace.len(), 4); - - state.insert(2, "spam\neggs".to_string()); - let mut inv = salsa::Invalidations::new(); - inv.invalidate(GET_TEXT, once(i_print(&2u32))); - inv.invalidate(GET_FILES, once(i_print(&()))); - let db = db.with_ground_data(state.clone(), inv); - let (newlines, trace) = get::<(), usize>(&db, TOTAL_NEWLINES, ()); - assert_eq!(*newlines, 4); - assert_eq!(trace.len(), 4); - - let mut invs = vec![]; - for i in 0..10 { - let id = i + 10; - invs.push(i_print(&id)); - state.insert(id, "spam".to_string()); - } - let mut inv = salsa::Invalidations::new(); - inv.invalidate(GET_TEXT, invs.into_iter()); - inv.invalidate(GET_FILES, once(i_print(&()))); - let db = db.with_ground_data(state.clone(), inv); - let (newlines, trace) = get::<(), usize>(&db, TOTAL_NEWLINES, ()); - assert_eq!(*newlines, 14); - assert_eq!(trace.len(), 22); - - state.insert(15, String::new()); - let mut inv = salsa::Invalidations::new(); - inv.invalidate(GET_TEXT, once(i_print(&15u32))); - inv.invalidate(GET_FILES, once(i_print(&()))); - let db = db.with_ground_data(state.clone(), inv); - let (newlines, trace) = get::<(), usize>(&db, TOTAL_NEWLINES, ()); - assert_eq!(*newlines, 13); - assert_eq!(trace.len(), 4); -} - -fn o_print(x: &T) -> salsa::OutputFingerprint { - let mut hasher = DefaultHasher::new(); - x.hash(&mut hasher); - let hash = hasher.finish(); - salsa::OutputFingerprint(hash) -} - -fn i_print(x: &T) -> salsa::InputFingerprint { - let mut hasher = DefaultHasher::new(); - x.hash(&mut hasher); - let hash = hasher.finish(); - salsa::InputFingerprint(hash) -} -- cgit v1.2.3