mina_tree/
base.rs

1use std::{
2    collections::HashSet,
3    ops::{ControlFlow, Deref},
4    path::PathBuf,
5    sync::atomic::AtomicU64,
6};
7
8use mina_curves::pasta::Fp;
9use mina_signer::CompressedPubKey;
10use serde::{Deserialize, Serialize};
11
12use crate::{
13    account::{Account, AccountId, TokenId},
14    address::Address,
15    database::DatabaseError,
16    scan_state::transaction_logic::AccountState,
17    sparse_ledger::LedgerIntf,
18    Mask,
19};
20
21pub type Uuid = String;
22
23static UUID_GENERATOR: AtomicU64 = AtomicU64::new(0);
24
25pub fn next_uuid() -> Uuid {
26    // use uuid::Uuid;
27
28    uuid::Uuid::new_v4().to_string()
29
30    // "a".to_string()
31    // UUID_GENERATOR.fetch_add(1, Ordering::AcqRel)
32}
33
34#[derive(PartialEq, Eq)]
35pub enum MerklePath {
36    Left(Fp),
37    Right(Fp),
38}
39
40impl MerklePath {
41    pub fn hash(&self) -> &Fp {
42        match self {
43            MerklePath::Left(h) => h,
44            MerklePath::Right(h) => h,
45        }
46    }
47}
48
49impl std::fmt::Debug for MerklePath {
50    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
51        match self {
52            Self::Left(arg0) => f.write_fmt(format_args!("Left({:?})", arg0)),
53            Self::Right(arg0) => f.write_fmt(format_args!("Right({:?})", arg0)),
54        }
55    }
56}
57
58pub trait BaseLedger {
59    /// list of accounts in the ledger
60    fn to_list(&self) -> Vec<Account>;
61
62    /// iterate over all indexes and accounts
63    fn iter<F>(&self, fun: F)
64    where
65        F: FnMut(&Account);
66
67    /// fold over accounts in the ledger, passing the Merkle address
68    fn fold<B, F>(&self, init: B, fun: F) -> B
69    where
70        F: FnMut(B, &Account) -> B;
71
72    /// the set of `account_id`s are ledger elements to skip during the fold,
73    /// because they're in a mask
74    fn fold_with_ignored_accounts<B, F>(&self, ignoreds: HashSet<AccountId>, init: B, fun: F) -> B
75    where
76        F: FnMut(B, &Account) -> B;
77
78    /// fold until `fun` returns `ControlFlow::Stop`
79    fn fold_until<B, F>(&self, init: B, fun: F) -> B
80    where
81        F: FnMut(B, &Account) -> ControlFlow<B, B>;
82
83    /// set of account ids associated with accounts
84    fn accounts(&self) -> HashSet<AccountId>;
85
86    /// Get the account id that owns a token.
87    fn token_owner(&self, token_id: TokenId) -> Option<AccountId>;
88
89    /// Get all of the tokens for which a public key has accounts.
90    fn tokens(&self, public_key: CompressedPubKey) -> HashSet<TokenId>;
91
92    fn location_of_account(&self, account_id: &AccountId) -> Option<Address>;
93
94    fn location_of_account_batch(
95        &self,
96        account_ids: &[AccountId],
97    ) -> Vec<(AccountId, Option<Address>)>;
98
99    /// This may return an error if the ledger is full.
100    fn get_or_create_account(
101        &mut self,
102        account_id: AccountId,
103        account: Account,
104    ) -> Result<GetOrCreated, DatabaseError>;
105
106    /// the ledger should not be used after calling `close`
107    fn close(&self);
108
109    /// for account locations in the ledger, the last (rightmost) filled location
110    fn last_filled(&self) -> Option<Address>;
111
112    fn get_uuid(&self) -> Uuid;
113
114    /// return Some `directory` for ledgers that use a file system, else None
115    fn get_directory(&self) -> Option<PathBuf>;
116
117    fn get(&self, addr: Address) -> Option<Box<Account>>;
118
119    fn get_batch(&self, addr: &[Address]) -> Vec<(Address, Option<Box<Account>>)>;
120
121    fn set(&mut self, addr: Address, account: Box<Account>);
122
123    fn set_batch(&mut self, list: &[(Address, Box<Account>)]);
124
125    fn get_at_index(&self, index: AccountIndex) -> Option<Box<Account>>;
126
127    fn set_at_index(&mut self, index: AccountIndex, account: Box<Account>) -> Result<(), ()>;
128
129    fn index_of_account(&self, account_id: AccountId) -> Option<AccountIndex>;
130
131    /// meant to be a fast operation: the root hash is stored, rather
132    /// than calculated dynamically
133    fn merkle_root(&mut self) -> Fp;
134
135    fn merkle_path(&mut self, addr: Address) -> Vec<MerklePath>;
136
137    fn merkle_path_at_index(&mut self, index: AccountIndex) -> Vec<MerklePath>;
138
139    fn remove_accounts(&mut self, ids: &[AccountId]);
140
141    /// Triggers when the ledger has been detached and should no longer be
142    /// accessed.
143    fn detached_signal(&mut self);
144
145    // Following methods from Syncable_intf
146
147    fn depth(&self) -> u8;
148
149    fn num_accounts(&self) -> usize;
150
151    fn merkle_path_at_addr(&mut self, addr: Address) -> Vec<MerklePath>;
152
153    fn get_inner_hash_at_addr(&mut self, addr: Address) -> Result<Fp, String>;
154
155    fn set_inner_hash_at_addr(&mut self, addr: Address, hash: Fp) -> Result<(), ()>;
156
157    fn set_all_accounts_rooted_at(
158        &mut self,
159        addr: Address,
160        accounts: &[Box<Account>],
161    ) -> Result<(), ()>;
162
163    fn set_batch_accounts(&mut self, list: &[(Address, Box<Account>)]) {
164        Self::set_batch(self, list)
165    }
166
167    /// Get all of the accounts that are in a subtree of the underlying Merkle
168    /// tree rooted at `address`. The accounts are ordered by their addresses.
169    fn get_all_accounts_rooted_at(&self, addr: Address) -> Option<Vec<(Address, Box<Account>)>>;
170
171    fn make_space_for(&mut self, space: usize);
172
173    // Following are internal methods, they might be better in a private trait
174    fn get_account_hash(&mut self, account_index: AccountIndex) -> Option<Fp>;
175    /// Used on mask only, has no effect with other implementation
176    /// Required for `LedgerIntf` on masks
177    fn commit(&mut self);
178}
179
180#[derive(Serialize, Deserialize, Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
181pub struct AccountIndex(pub u64);
182
183impl AccountIndex {
184    pub fn as_u64(&self) -> u64 {
185        self.0
186    }
187}
188
189impl PartialEq<u64> for AccountIndex {
190    fn eq(&self, other: &u64) -> bool {
191        self.0 == *other
192    }
193}
194
195impl PartialEq<usize> for AccountIndex {
196    fn eq(&self, other: &usize) -> bool {
197        let other: u64 = (*other).try_into().unwrap();
198        self.0 == other
199    }
200}
201
202impl From<usize> for AccountIndex {
203    fn from(n: usize) -> Self {
204        Self(n.try_into().unwrap())
205    }
206}
207
208#[derive(Clone, Debug)]
209pub enum GetOrCreated {
210    Added(Address),
211    Existed(Address),
212}
213
214impl GetOrCreated {
215    pub fn addr(self) -> Address {
216        match self {
217            GetOrCreated::Added(addr) => addr,
218            GetOrCreated::Existed(addr) => addr,
219        }
220    }
221}
222
223impl Deref for GetOrCreated {
224    type Target = Address;
225
226    fn deref(&self) -> &Self::Target {
227        match self {
228            GetOrCreated::Added(addr) => addr,
229            GetOrCreated::Existed(addr) => addr,
230        }
231    }
232}
233
234impl LedgerIntf for Mask {
235    type Location = Address;
236
237    fn get(&self, addr: &Address) -> Option<Box<Account>> {
238        BaseLedger::get(self, addr.clone())
239    }
240
241    fn location_of_account(&self, account_id: &AccountId) -> Option<Address> {
242        BaseLedger::location_of_account(self, account_id)
243    }
244
245    fn set(&mut self, addr: &Address, account: Box<Account>) {
246        BaseLedger::set(self, addr.clone(), account)
247    }
248
249    /// <https://github.com/MinaProtocol/mina/blob/05c2f73d0f6e4f1341286843814ce02dcb3919e0/src/lib/mina_ledger/ledger.ml#L311>
250    fn get_or_create(
251        &mut self,
252        account_id: &AccountId,
253    ) -> Result<(AccountState, Box<Account>, Address), String> {
254        let location = BaseLedger::get_or_create_account(
255            self,
256            account_id.clone(),
257            Account::initialize(account_id),
258        )
259        .map_err(|e| format!("{:?}", e))?;
260
261        let action = match location {
262            GetOrCreated::Added(_) => AccountState::Added,
263            GetOrCreated::Existed(_) => AccountState::Existed,
264        };
265
266        let addr = location.addr();
267        let account = BaseLedger::get(self, addr.clone()).ok_or_else(|| {
268            "get_or_create: Account was not found in the ledger after creation".to_string()
269        })?;
270
271        Ok((action, account, addr))
272    }
273
274    /// <https://github.com/MinaProtocol/mina/blob/05c2f73d0f6e4f1341286843814ce02dcb3919e0/src/lib/mina_ledger/ledger.ml#L304>
275    fn create_new_account(&mut self, account_id: AccountId, account: Account) -> Result<(), ()> {
276        match BaseLedger::get_or_create_account(self, account_id, account).unwrap() {
277            GetOrCreated::Added(_) => {}
278            GetOrCreated::Existed(_) => panic!(),
279        }
280        Ok(())
281    }
282
283    fn remove_accounts_exn(&mut self, account_ids: &[AccountId]) {
284        BaseLedger::remove_accounts(self, account_ids)
285    }
286
287    fn merkle_root(&mut self) -> Fp {
288        BaseLedger::merkle_root(self)
289    }
290
291    fn empty(depth: usize) -> Self {
292        let root = Mask::new_unattached(depth);
293        root.make_child()
294    }
295
296    /// Create a ledger as a mask on top of the existing ledger.
297    /// Warning: This skips mask registration, for use in transaction logic,
298    /// where we always have either 0 or 1 masks, and the mask is always either
299    /// committed or discarded. This function is deliberately not exposed in the
300    /// public API of this module.
301    /// This should *NOT* be used to create a ledger for other purposes.
302    fn create_masked(&self) -> Self {
303        let mut mask = Mask::new_unattached(self.depth() as usize);
304
305        if self.has_token_owners() {
306            mask.set_token_owners();
307        }
308
309        // We don't register the mask here. This is only used in transaction logic,
310        // where we don't want to unregister. Transaction logic is also
311        // synchronous, so we don't need to worry that our mask will be reparented.
312
313        mask.set_parent(self.clone(), None)
314    }
315
316    fn apply_mask(&mut self, mask: Self) {
317        // ignore `self` here:
318        // <https://github.com/MinaProtocol/mina/blob/f6756507ff7380a691516ce02a3cf7d9d32915ae/src/lib/mina_ledger/ledger.ml#L236-L246>
319        mask.commit()
320    }
321
322    fn account_locations(&self) -> Vec<Self::Location> {
323        let mut addrs: Vec<Address> = self
324            .accounts()
325            .into_iter()
326            .map(|account_id| BaseLedger::location_of_account(self, &account_id).unwrap())
327            .collect();
328
329        addrs.sort_by_key(Address::to_index);
330
331        addrs
332    }
333}
mina_tree/base.rs

mina_tree/
base.rs
