diff options
author | Aleksey Kladov <[email protected]> | 2018-09-11 08:31:04 +0100 |
---|---|---|
committer | Aleksey Kladov <[email protected]> | 2018-09-15 22:00:05 +0100 |
commit | c81d0d51bf05791b6ed39376d67d6e2876dd2a1e (patch) | |
tree | 386b98e25d7c12d29fd803635c1bc8e22ed1e73d /crates/libanalysis/src/db.rs | |
parent | db14b4270c0b328f89a3a2262f2814b2f80b083c (diff) |
add deps tracking
Diffstat (limited to 'crates/libanalysis/src/db.rs')
-rw-r--r-- | crates/libanalysis/src/db.rs | 148 |
1 files changed, 119 insertions, 29 deletions
diff --git a/crates/libanalysis/src/db.rs b/crates/libanalysis/src/db.rs index 31c73c402..bfff5357f 100644 --- a/crates/libanalysis/src/db.rs +++ b/crates/libanalysis/src/db.rs | |||
@@ -1,5 +1,5 @@ | |||
1 | use std::{ | 1 | use std::{ |
2 | hash::Hash, | 2 | hash::{Hash, Hasher}, |
3 | sync::Arc, | 3 | sync::Arc, |
4 | cell::RefCell, | 4 | cell::RefCell, |
5 | fmt::Debug, | 5 | fmt::Debug, |
@@ -45,17 +45,35 @@ impl DbHost { | |||
45 | pub(crate) fn query_ctx(&self) -> QueryCtx { | 45 | pub(crate) fn query_ctx(&self) -> QueryCtx { |
46 | QueryCtx { | 46 | QueryCtx { |
47 | db: Arc::clone(&self.db), | 47 | db: Arc::clone(&self.db), |
48 | stack: RefCell::new(Vec::new()), | ||
48 | trace: RefCell::new(Vec::new()), | 49 | trace: RefCell::new(Vec::new()), |
49 | } | 50 | } |
50 | } | 51 | } |
51 | fn db_mut(&mut self) -> &mut Db { | 52 | fn db_mut(&mut self) -> &mut Db { |
52 | // NB: this "forks" the database & clears the cache | 53 | // NB: this "forks" the database |
53 | let db = Arc::make_mut(&mut self.db); | 54 | let db = Arc::make_mut(&mut self.db); |
54 | *db.cache.get_mut() = Default::default(); | 55 | db.cache.get_mut().gen += 1; |
55 | db | 56 | db |
56 | } | 57 | } |
57 | } | 58 | } |
58 | 59 | ||
60 | type QueryInvocationId = (u32, u64); | ||
61 | type Gen = u64; | ||
62 | type OutputHash = u64; | ||
63 | |||
64 | fn id<Q: Query>(params: &Q::Params) -> QueryInvocationId { | ||
65 | use std::collections::hash_map::DefaultHasher; | ||
66 | let mut hasher = DefaultHasher::new(); | ||
67 | params.hash(&mut hasher); | ||
68 | (Q::ID, hasher.finish()) | ||
69 | } | ||
70 | fn output_hash<Q: Query>(output: &Q::Output) -> OutputHash { | ||
71 | use std::collections::hash_map::DefaultHasher; | ||
72 | let mut hasher = DefaultHasher::new(); | ||
73 | output.hash(&mut hasher); | ||
74 | hasher.finish() | ||
75 | } | ||
76 | |||
59 | #[derive(Debug)] | 77 | #[derive(Debug)] |
60 | pub(crate) struct Db { | 78 | pub(crate) struct Db { |
61 | file_resolver: FileResolverImp, | 79 | file_resolver: FileResolverImp, |
@@ -73,9 +91,13 @@ impl Clone for Db { | |||
73 | } | 91 | } |
74 | } | 92 | } |
75 | 93 | ||
76 | #[derive(Clone, Default, Debug)] | 94 | |
95 | #[derive(Default, Debug)] | ||
77 | pub(crate) struct Cache { | 96 | pub(crate) struct Cache { |
78 | pub(crate) module_descr: QueryCache<ModuleDescr> | 97 | pub(crate) module_descr: QueryCache<ModuleDescr>, |
98 | gen: Gen, | ||
99 | green: im::HashMap<QueryInvocationId, (Gen, OutputHash)>, | ||
100 | deps: im::HashMap<QueryInvocationId, Vec<(QueryInvocationId, OutputHash)>>, | ||
79 | } | 101 | } |
80 | #[allow(type_alias_bounds)] | 102 | #[allow(type_alias_bounds)] |
81 | pub(crate) type QueryCache<Q: Query> = im::HashMap< | 103 | pub(crate) type QueryCache<Q: Query> = im::HashMap< |
@@ -91,6 +113,7 @@ impl Cache { | |||
91 | 113 | ||
92 | pub(crate) struct QueryCtx { | 114 | pub(crate) struct QueryCtx { |
93 | db: Arc<Db>, | 115 | db: Arc<Db>, |
116 | stack: RefCell<Vec<QueryInvocationId>>, | ||
94 | pub(crate) trace: RefCell<Vec<TraceEvent>>, | 117 | pub(crate) trace: RefCell<Vec<TraceEvent>>, |
95 | } | 118 | } |
96 | 119 | ||
@@ -102,12 +125,28 @@ pub(crate) struct TraceEvent { | |||
102 | 125 | ||
103 | #[derive(Clone, Copy, Debug, PartialEq, Eq)] | 126 | #[derive(Clone, Copy, Debug, PartialEq, Eq)] |
104 | pub(crate) enum TraceEventKind { | 127 | pub(crate) enum TraceEventKind { |
105 | Start, Finish | 128 | Start, Evaluating, Finish |
106 | } | 129 | } |
107 | 130 | ||
108 | impl QueryCtx { | 131 | impl QueryCtx { |
109 | pub(crate) fn get<Q: Get>(&self, params: &Q::Params) -> Q::Output { | 132 | pub(crate) fn get<Q: Get>(&self, params: &Q::Params) -> Q::Output { |
133 | let me = id::<Q>(params); | ||
134 | eprintln!("eval: {:?}", me); | ||
135 | let parent = self.stack.borrow().last().map(|&id| id); | ||
136 | self.stack.borrow_mut().push(me); | ||
137 | self.trace(TraceEvent { query_id: Q::ID, kind: TraceEventKind::Start }); | ||
110 | let res = Q::get(self, params); | 138 | let res = Q::get(self, params); |
139 | self.trace(TraceEvent { query_id: Q::ID, kind: TraceEventKind::Finish }); | ||
140 | if let Some(parent) = parent { | ||
141 | let h = output_hash::<Q>(&res); | ||
142 | let mut cache = self.db.cache.lock(); | ||
143 | cache.deps | ||
144 | .entry(parent) | ||
145 | .or_insert(Vec::new()) | ||
146 | .push((me, h)) | ||
147 | } | ||
148 | let also_me = self.stack.borrow_mut().pop(); | ||
149 | assert_eq!(also_me, Some(me)); | ||
111 | res | 150 | res |
112 | } | 151 | } |
113 | fn trace(&self, event: TraceEvent) { | 152 | fn trace(&self, event: TraceEvent) { |
@@ -118,47 +157,80 @@ impl QueryCtx { | |||
118 | pub(crate) trait Query { | 157 | pub(crate) trait Query { |
119 | const ID: u32; | 158 | const ID: u32; |
120 | type Params: Hash + Eq + Debug; | 159 | type Params: Hash + Eq + Debug; |
121 | type Output: Debug; | 160 | type Output: Hash + Debug; |
122 | } | 161 | } |
123 | 162 | ||
124 | pub(crate) trait Get: Query { | 163 | pub(crate) trait Get: Query { |
125 | fn get(ctx: &QueryCtx, params: &Self::Params) -> Self::Output; | 164 | fn get(ctx: &QueryCtx, params: &Self::Params) -> Self::Output; |
126 | } | 165 | } |
127 | 166 | ||
128 | impl<T: Eval> Get for T | 167 | impl<Q: Eval> Get for Q |
129 | where | 168 | where |
130 | T::Params: Clone, | 169 | Q::Params: Clone, |
131 | T::Output: Clone, | 170 | Q::Output: Clone, |
132 | { | 171 | { |
133 | fn get(ctx: &QueryCtx, params: &Self::Params) -> Self::Output { | 172 | fn get(ctx: &QueryCtx, params: &Self::Params) -> Self::Output { |
134 | { | 173 | if !Self::cacheable() { |
135 | let mut cache = ctx.db.cache.lock(); | 174 | ctx.trace(TraceEvent { query_id: Q::ID, kind: TraceEventKind::Evaluating }); |
136 | if let Some(cache) = Self::cache(&mut cache) { | 175 | return Self::eval(ctx, params); |
137 | if let Some(res) = cache.get(params) { | ||
138 | return res.clone(); | ||
139 | } | ||
140 | } | ||
141 | } | 176 | } |
142 | ctx.trace(TraceEvent { query_id: Self::ID, kind: TraceEventKind::Start }); | ||
143 | let res = Self::eval(ctx, params); | ||
144 | ctx.trace(TraceEvent { query_id: Self::ID, kind: TraceEventKind::Finish }); | ||
145 | 177 | ||
146 | let mut cache = ctx.db.cache.lock(); | 178 | if let Some(res) = try_reuse::<Q>(ctx, params) { |
147 | if let Some(cache) = Self::cache(&mut cache) { | 179 | return res; |
148 | cache.insert(params.clone(), res.clone()); | ||
149 | } | 180 | } |
150 | 181 | ||
182 | ctx.trace(TraceEvent { query_id: Q::ID, kind: TraceEventKind::Evaluating }); | ||
183 | let res = Self::eval(ctx, params); | ||
184 | |||
185 | let mut cache = ctx.db.cache.lock(); | ||
186 | let gen = cache.gen; | ||
187 | let output_hash = output_hash::<Q>(&res); | ||
188 | let id = id::<Q>(params); | ||
189 | cache.green.insert(id, (gen, output_hash)); | ||
190 | let cache = Self::cache(&mut cache); | ||
191 | cache.insert(params.clone(), res.clone()); | ||
151 | res | 192 | res |
152 | } | 193 | } |
153 | } | 194 | } |
154 | 195 | ||
196 | fn try_reuse<Q: Eval>(ctx: &QueryCtx, params: &Q::Params) -> Option<Q::Output> | ||
197 | where | ||
198 | Q::Params: Clone, | ||
199 | Q::Output: Clone, | ||
200 | { | ||
201 | let id = id::<Q>(params); | ||
202 | let mut cache = ctx.db.cache.lock(); | ||
203 | let curr_gen = cache.gen; | ||
204 | let old_hash = match *cache.green.get(&id)? { | ||
205 | (gen, _) if gen == curr_gen => { | ||
206 | return Some(Q::cache(&mut cache)[params].clone()); | ||
207 | } | ||
208 | (_, hash) => hash, | ||
209 | }; | ||
210 | let deps_are_fresh = cache.deps[&id] | ||
211 | .iter() | ||
212 | .all(|&(dep_id, dep_hash)| { | ||
213 | match cache.green.get(&dep_id) { | ||
214 | //TODO: store the value of parameters, and re-execute the query | ||
215 | Some((gen, hash)) if gen == &curr_gen && hash == &dep_hash => true, | ||
216 | _ => false, | ||
217 | } | ||
218 | }); | ||
219 | if !deps_are_fresh { | ||
220 | return None; | ||
221 | } | ||
222 | cache.green.insert(id, (curr_gen, old_hash)); | ||
223 | Some(Q::cache(&mut cache)[params].clone()) | ||
224 | } | ||
225 | |||
155 | pub(crate) trait Eval: Query | 226 | pub(crate) trait Eval: Query |
156 | where | 227 | where |
157 | Self::Params: Clone, | 228 | Self::Params: Clone, |
158 | Self::Output: Clone, | 229 | Self::Output: Clone, |
159 | { | 230 | { |
160 | fn cache(_cache: &mut Cache) -> Option<&mut QueryCache<Self>> { | 231 | fn cacheable() -> bool { false } |
161 | None | 232 | fn cache(_cache: &mut Cache) -> &mut QueryCache<Self> { |
233 | unimplemented!() | ||
162 | } | 234 | } |
163 | fn eval(ctx: &QueryCtx, params: &Self::Params) -> Self::Output; | 235 | fn eval(ctx: &QueryCtx, params: &Self::Params) -> Self::Output; |
164 | } | 236 | } |
@@ -168,6 +240,12 @@ pub(crate) struct DbFiles { | |||
168 | db: Arc<Db>, | 240 | db: Arc<Db>, |
169 | } | 241 | } |
170 | 242 | ||
243 | impl Hash for DbFiles { | ||
244 | fn hash<H: Hasher>(&self, hasher: &mut H) { | ||
245 | self.db.cache.lock().gen.hash(hasher) | ||
246 | } | ||
247 | } | ||
248 | |||
171 | impl DbFiles { | 249 | impl DbFiles { |
172 | pub(crate) fn iter<'a>(&'a self) -> impl Iterator<Item=FileId> + 'a { | 250 | pub(crate) fn iter<'a>(&'a self) -> impl Iterator<Item=FileId> + 'a { |
173 | self.db.files.keys().cloned() | 251 | self.db.files.keys().cloned() |
@@ -184,8 +262,14 @@ impl Query for Files { | |||
184 | type Output = DbFiles; | 262 | type Output = DbFiles; |
185 | } | 263 | } |
186 | impl Get for Files { | 264 | impl Get for Files { |
187 | fn get(ctx: &QueryCtx, _params: &()) -> DbFiles { | 265 | fn get(ctx: &QueryCtx, params: &()) -> DbFiles { |
188 | DbFiles { db: Arc::clone(&ctx.db) } | 266 | let res = DbFiles { db: Arc::clone(&ctx.db) }; |
267 | let id = id::<Self>(params); | ||
268 | let hash = output_hash::<Self>(&res); | ||
269 | let mut cache = ctx.db.cache.lock(); | ||
270 | let gen = cache.gen; | ||
271 | cache.green.insert(id, (gen, hash)); | ||
272 | res | ||
189 | } | 273 | } |
190 | } | 274 | } |
191 | 275 | ||
@@ -197,7 +281,13 @@ impl Query for FileText { | |||
197 | } | 281 | } |
198 | impl Get for FileText { | 282 | impl Get for FileText { |
199 | fn get(ctx: &QueryCtx, file_id: &FileId) -> Arc<String> { | 283 | fn get(ctx: &QueryCtx, file_id: &FileId) -> Arc<String> { |
200 | ctx.db.files[file_id].clone() | 284 | let res = ctx.db.files[file_id].clone(); |
285 | let id = id::<Self>(file_id); | ||
286 | let hash = output_hash::<Self>(&res); | ||
287 | let mut cache = ctx.db.cache.lock(); | ||
288 | let gen = cache.gen; | ||
289 | cache.green.insert(id, (gen, hash)); | ||
290 | res | ||
201 | } | 291 | } |
202 | } | 292 | } |
203 | 293 | ||