nakamoto_test/block/cache/
model.rs

1//! Block cache *model*.
2//! Not for production use.
3
4use std::ops::RangeInclusive;
5
6use nakamoto_common::bitcoin_hashes::Hash;
7use nakamoto_common::block::filter::{self, BlockFilter, FilterHash, FilterHeader, Filters};
8use nakamoto_common::block::iter::Iter;
9use nakamoto_common::block::tree::{BlockReader, BlockTree, Branch, Error, ImportResult};
10use nakamoto_common::block::Height;
11use nakamoto_common::nonempty::NonEmpty;
12
13use std::collections::{BTreeMap, HashMap, VecDeque};
14
15use nakamoto_common::bitcoin::blockdata::block::BlockHeader;
16use nakamoto_common::bitcoin::hash_types::BlockHash;
17
18#[derive(Debug, Clone)]
19pub struct Cache {
20    pub headers: HashMap<BlockHash, BlockHeader>,
21    pub chain: NonEmpty<BlockHeader>,
22    pub tip: BlockHash,
23    pub genesis: BlockHash,
24}
25
26impl Cache {
27    pub fn new(genesis: BlockHeader) -> Self {
28        let mut headers = HashMap::new();
29        let hash = genesis.block_hash();
30        let chain = NonEmpty::new(genesis);
31
32        headers.insert(hash, genesis);
33
34        Self {
35            headers,
36            chain,
37            tip: hash,
38            genesis: hash,
39        }
40    }
41
42    pub fn from(chain: NonEmpty<BlockHeader>) -> Self {
43        let genesis = chain.head.block_hash();
44        let tip = chain.last().block_hash();
45
46        let mut headers = HashMap::new();
47        for h in chain.iter() {
48            headers.insert(h.block_hash(), *h);
49        }
50
51        Self {
52            headers,
53            chain,
54            tip,
55            genesis,
56        }
57    }
58
59    pub fn rollback(&mut self, height: Height) -> Result<(), Error> {
60        for block in self.chain.tail.drain(height as usize..) {
61            self.headers.remove(&block.block_hash());
62        }
63        Ok(())
64    }
65
66    fn branch(&self, tip: &BlockHash) -> Option<NonEmpty<BlockHeader>> {
67        let mut headers = VecDeque::new();
68        let mut tip = *tip;
69
70        while let Some(header) = self.headers.get(&tip) {
71            tip = header.prev_blockhash;
72            headers.push_front(*header);
73        }
74
75        match headers.pop_front() {
76            Some(root) if root.block_hash() == self.genesis => {
77                Some(NonEmpty::from((root, headers.into())))
78            }
79            _ => None,
80        }
81    }
82
83    fn longest_chain(&self) -> NonEmpty<BlockHeader> {
84        let mut branches = Vec::new();
85
86        for tip in self.headers.keys() {
87            if let Some(branch) = self.branch(tip) {
88                branches.push(branch);
89            }
90        }
91
92        branches
93            .into_iter()
94            .max_by(|a, b| {
95                let a_work = Branch(&a.tail).work();
96                let b_work = Branch(&b.tail).work();
97
98                if a_work == b_work {
99                    let a_hash = a.last().block_hash();
100                    let b_hash = b.last().block_hash();
101
102                    b_hash.cmp(&a_hash)
103                } else {
104                    a_work.cmp(&b_work)
105                }
106            })
107            .unwrap()
108    }
109}
110
111impl BlockTree for Cache {
112    fn import_blocks<I: Iterator<Item = BlockHeader>, C>(
113        &mut self,
114        chain: I,
115        _context: &C,
116    ) -> Result<ImportResult, Error> {
117        let old = self.chain.clone();
118        let mut disconnected = Vec::new();
119        let mut connected = Vec::new();
120
121        for header in chain {
122            self.headers.insert(header.block_hash(), header);
123        }
124        let tip = self.tip;
125
126        self.chain = self.longest_chain();
127        self.tip = self.chain.last().block_hash();
128
129        if tip != self.tip {
130            for (height, header) in old.iter().enumerate() {
131                if !self.chain.contains(header) {
132                    disconnected.push((height as Height, *header));
133                }
134            }
135            for (height, header) in self.chain.iter().enumerate() {
136                if !old.contains(header) {
137                    connected.push((height as Height, *header));
138                }
139            }
140            let connected = NonEmpty::from_vec(connected).unwrap();
141
142            Ok(ImportResult::TipChanged(
143                self.chain.last().to_owned(),
144                self.tip,
145                self.height(),
146                disconnected,
147                connected,
148            ))
149        } else {
150            Ok(ImportResult::TipUnchanged)
151        }
152    }
153
154    fn extend_tip<C>(&mut self, header: BlockHeader, _context: &C) -> Result<ImportResult, Error> {
155        if header.prev_blockhash == self.tip {
156            let hash = header.block_hash();
157
158            self.headers.insert(hash, header);
159            self.chain.push(header);
160            self.tip = hash;
161
162            Ok(ImportResult::TipChanged(
163                header,
164                self.tip,
165                self.height(),
166                vec![],
167                NonEmpty::new((self.height(), header)),
168            ))
169        } else {
170            Ok(ImportResult::TipUnchanged)
171        }
172    }
173}
174
175impl BlockReader for Cache {
176    fn get_block(&self, hash: &BlockHash) -> Option<(Height, &BlockHeader)> {
177        for (height, header) in self.chain.iter().enumerate() {
178            if hash == &header.block_hash() {
179                return Some((height as Height, header));
180            }
181        }
182        None
183    }
184
185    fn find_branch(&self, _to: &BlockHash) -> Option<(Height, NonEmpty<BlockHeader>)> {
186        unimplemented!()
187    }
188
189    fn locate_headers(
190        &self,
191        _locators: &[BlockHash],
192        _stop_hash: BlockHash,
193        _max: usize,
194    ) -> Vec<BlockHeader> {
195        unimplemented!()
196    }
197
198    fn last_checkpoint(&self) -> Height {
199        0
200    }
201
202    fn checkpoints(&self) -> BTreeMap<Height, BlockHash> {
203        BTreeMap::new()
204    }
205
206    fn locator_hashes(&self, _from: Height) -> Vec<BlockHash> {
207        vec![self.chain.last().block_hash()]
208    }
209
210    fn get_block_by_height(&self, height: Height) -> Option<&BlockHeader> {
211        self.chain.get(height as usize)
212    }
213
214    fn tip(&self) -> (BlockHash, BlockHeader) {
215        let tip = self.chain.last();
216        (tip.block_hash(), *tip)
217    }
218
219    fn height(&self) -> Height {
220        self.chain.len() as Height - 1
221    }
222
223    fn iter<'a>(&'a self) -> Box<dyn DoubleEndedIterator<Item = (Height, BlockHeader)> + 'a> {
224        Box::new(Iter::new(&self.chain).map(|(i, h)| (i, *h)))
225    }
226
227    fn contains(&self, hash: &BlockHash) -> bool {
228        self.headers.contains_key(hash) && self.chain.iter().any(|b| b.block_hash() == *hash)
229    }
230
231    fn is_known(&self, hash: &BlockHash) -> bool {
232        self.headers.contains_key(hash)
233    }
234}
235
236#[derive(Debug, Clone)]
237pub struct FilterCache {
238    headers: NonEmpty<(FilterHash, FilterHeader)>,
239    filters: BTreeMap<Height, BlockFilter>,
240}
241
242impl FilterCache {
243    pub fn new(genesis: FilterHeader) -> Self {
244        Self {
245            headers: NonEmpty::new((FilterHash::all_zeros(), genesis)),
246            filters: BTreeMap::new(),
247        }
248    }
249
250    pub fn from(headers: NonEmpty<(FilterHash, FilterHeader)>) -> Self {
251        Self {
252            headers,
253            filters: BTreeMap::new(),
254        }
255    }
256}
257
258impl Filters for FilterCache {
259    fn get_header(&self, height: Height) -> Option<(FilterHash, FilterHeader)> {
260        self.headers.get(height as usize).copied()
261    }
262
263    fn get_headers(&self, range: RangeInclusive<Height>) -> Vec<(FilterHash, FilterHeader)> {
264        let (start, end) = (*range.start(), *range.end());
265
266        assert!(start <= end);
267
268        self.headers
269            .iter()
270            .cloned()
271            .skip(start as usize)
272            .take(end as usize - start as usize + 1)
273            .collect()
274    }
275
276    fn import_headers(
277        &mut self,
278        headers: Vec<(FilterHash, FilterHeader)>,
279    ) -> Result<Height, filter::Error> {
280        self.headers.tail.extend(headers);
281
282        Ok(self.height())
283    }
284
285    fn tip(&self) -> (&FilterHash, &FilterHeader) {
286        let (hash, header) = self.headers.last();
287        (hash, header)
288    }
289
290    fn height(&self) -> Height {
291        self.headers.tail.len() as Height
292    }
293
294    fn rollback(&mut self, height: Height) -> Result<(), filter::Error> {
295        self.headers.tail.truncate(height as usize);
296
297        let heights = self
298            .filters
299            .range(height + 1..)
300            .map(|(h, _)| *h)
301            .collect::<Vec<_>>();
302
303        for h in heights {
304            self.filters.remove(&h);
305        }
306        Ok(())
307    }
308
309    fn clear(&mut self) -> Result<(), filter::Error> {
310        self.headers.tail.clear();
311        self.filters.clear();
312
313        Ok(())
314    }
315}
nakamoto_test/block/cache/model.rs

nakamoto_test/block/cache/
model.rs
