1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
//! Merklized key-value store.
use std::{
    iter,
    ops::{Deref, DerefMut},
};

use anyhow::{Error, Result};

use crate::common::{crypto::hash::Hash, namespace::Namespace};

use self::sync::Proof;

#[macro_use]
mod tree;
mod cache;
#[cfg(test)]
pub mod interop;
pub mod marshal;
pub mod sync;
#[cfg(test)]
mod tests;

pub use tree::{Depth, Key, NodeBox, NodePointer, NodePtrRef, OverlayTree, Root, RootType, Tree};

/// The type of entry in the log.
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub enum LogEntryKind {
    Insert,
    Delete,
}

/// An entry in the write log, describing a single update.
#[derive(Clone, Debug, Default, Eq, PartialEq, Hash, cbor::Encode, cbor::Decode)]
#[cbor(as_array)]
pub struct LogEntry {
    /// The key that was inserted or deleted.
    pub key: Vec<u8>,
    /// The inserted value (empty if the key was deleted).
    pub value: Option<Vec<u8>>,
}

impl LogEntry {
    pub fn new(key: &[u8], value: &[u8]) -> Self {
        Self {
            key: key.to_owned(),
            value: Some(value.to_owned()),
        }
    }

    pub fn kind(&self) -> LogEntryKind {
        match self.value {
            Some(_) => LogEntryKind::Insert,
            None => LogEntryKind::Delete,
        }
    }
}

/// The write log.
///
/// The keys in the write log must be unique.
pub type WriteLog = Vec<LogEntry>;

/// A key prefix.
#[derive(Clone, Debug, Default, Eq, PartialEq, PartialOrd, Ord, cbor::Encode, cbor::Decode)]
#[cbor(transparent)]
pub struct Prefix(Vec<u8>);

impl AsRef<[u8]> for Prefix {
    fn as_ref(&self) -> &[u8] {
        &self.0
    }
}

impl Deref for Prefix {
    type Target = Vec<u8>;

    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

impl DerefMut for Prefix {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.0
    }
}

impl From<Prefix> for Vec<u8> {
    fn from(val: Prefix) -> Self {
        val.0
    }
}

impl From<Vec<u8>> for Prefix {
    fn from(v: Vec<u8>) -> Prefix {
        Prefix(v)
    }
}

/// Merklized key-value store.
pub trait MKVS {
    /// Fetch entry with given key.
    fn get(&self, key: &[u8]) -> Option<Vec<u8>>;

    /// Fetch proof for entry with given key.
    fn get_proof(&self, key: &[u8]) -> Option<Proof>;

    /// Check if the local MKVS cache contains the given key.
    ///
    /// While get can be used to check if the MKVS as a whole contains
    /// a given key, this function specifically guarantees that no remote
    /// syncing will be invoked, only checking the local cache.
    fn cache_contains_key(&self, key: &[u8]) -> bool;

    /// Update entry with given key.
    ///
    /// If the database did not have this key present, [`None`] is returned.
    ///
    /// If the database did have this key present, the value is updated, and the old value is
    /// returned.
    ///
    /// [`None`]: std::option::Option
    fn insert(&mut self, key: &[u8], value: &[u8]) -> Option<Vec<u8>>;

    /// Remove entry with given key, returning the value at the key if the key was previously
    /// in the database.
    fn remove(&mut self, key: &[u8]) -> Option<Vec<u8>>;

    /// Populate the in-memory tree with nodes for keys starting with given prefixes.
    fn prefetch_prefixes(&self, prefixes: &[Prefix], limit: u16);

    /// Returns an iterator over the tree.
    fn iter(&self) -> Box<dyn Iterator + '_>;

    /// Commit all database changes to the underlying store.
    fn commit(&mut self, namespace: Namespace, version: u64) -> Result<(WriteLog, Hash)>;
}

/// Merklized key-value store where methods return errors instead of panicking.
pub trait FallibleMKVS {
    /// Fetch entry with given key.
    fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>>;

    /// Fetch proof for entry with given key.
    fn get_proof(&self, key: &[u8]) -> Result<Option<Proof>>;

    /// Check if the local MKVS cache contains the given key.
    ///
    /// While get can be used to check if the MKVS as a whole contains
    /// a given key, this function specifically guarantees that no remote
    /// syncing will be invoked, only checking the local cache.
    fn cache_contains_key(&self, key: &[u8]) -> bool;

    /// Update entry with given key.
    ///
    /// If the database did not have this key present, [`None`] is returned.
    ///
    /// If the database did have this key present, the value is updated, and the old value is
    /// returned.
    ///
    /// [`None`]: std::option::Option
    fn insert(&mut self, key: &[u8], value: &[u8]) -> Result<Option<Vec<u8>>>;

    /// Remove entry with given key, returning the value at the key if the key was previously
    /// in the database.
    fn remove(&mut self, key: &[u8]) -> Result<Option<Vec<u8>>>;

    /// Populate the in-memory tree with nodes for keys starting with given prefixes.
    fn prefetch_prefixes(&self, prefixes: &[Prefix], limit: u16) -> Result<()>;

    /// Returns an iterator over the tree.
    fn iter(&self) -> Box<dyn Iterator + '_>;

    /// Commit all database changes to the underlying store.
    fn commit(&mut self, namespace: Namespace, version: u64) -> Result<Hash>;
}

/// Immutable merkalized key value store.
pub trait ImmutableMKVS {
    /// Fetch entry with given key.
    fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>>;

    /// Fetch proof for entry with given key.
    fn get_proof(&self, key: &[u8]) -> Result<Option<Proof>>;

    /// Populate the in-memory tree with nodes for keys starting with given prefixes.
    fn prefetch_prefixes(&self, prefixes: &[Prefix], limit: u16) -> Result<()>;

    /// Returns an iterator over the tree.
    fn iter(&self) -> Box<dyn Iterator + '_>;
}

impl<T> ImmutableMKVS for T
where
    T: FallibleMKVS,
{
    fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>> {
        T::get(self, key)
    }

    fn get_proof(&self, key: &[u8]) -> Result<Option<Proof>> {
        T::get_proof(self, key)
    }

    fn prefetch_prefixes(&self, prefixes: &[Prefix], limit: u16) -> Result<()> {
        T::prefetch_prefixes(self, prefixes, limit)
    }

    fn iter(&self) -> Box<dyn Iterator + '_> {
        T::iter(self)
    }
}

/// An MKVS iterator.
pub trait Iterator: iter::Iterator<Item = (Vec<u8>, Vec<u8>)> {
    /// Sets the number of next elements to prefetch.
    fn set_prefetch(&mut self, prefetch: usize);

    /// Return whether the iterator is valid.
    fn is_valid(&self) -> bool;

    /// Return the error that occurred during iteration if any.
    fn error(&self) -> &Option<Error>;

    /// Moves the iterator to the first key in the tree.
    fn rewind(&mut self);

    /// Moves the iterator either at the given key or at the next larger key.
    fn seek(&mut self, key: &[u8]);

    /// The key under the iterator.
    fn get_key(&self) -> &Option<Key>;

    /// The value under the iterator.
    fn get_value(&self) -> &Option<Vec<u8>>;

    /// Advance the iterator to the next key.
    fn next(&mut self);
}

impl<T: MKVS + ?Sized> MKVS for &mut T {
    fn get(&self, key: &[u8]) -> Option<Vec<u8>> {
        T::get(self, key)
    }

    fn get_proof(&self, key: &[u8]) -> Option<Proof> {
        T::get_proof(self, key)
    }

    fn cache_contains_key(&self, key: &[u8]) -> bool {
        T::cache_contains_key(self, key)
    }

    fn insert(&mut self, key: &[u8], value: &[u8]) -> Option<Vec<u8>> {
        T::insert(self, key, value)
    }

    fn remove(&mut self, key: &[u8]) -> Option<Vec<u8>> {
        T::remove(self, key)
    }

    fn prefetch_prefixes(&self, prefixes: &[Prefix], limit: u16) {
        T::prefetch_prefixes(self, prefixes, limit)
    }

    fn iter(&self) -> Box<dyn Iterator + '_> {
        T::iter(self)
    }

    fn commit(&mut self, namespace: Namespace, version: u64) -> Result<(WriteLog, Hash)> {
        T::commit(self, namespace, version)
    }
}

impl<T: FallibleMKVS + ?Sized> FallibleMKVS for &mut T {
    fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>> {
        T::get(self, key)
    }

    fn get_proof(&self, key: &[u8]) -> Result<Option<Proof>> {
        T::get_proof(self, key)
    }

    fn cache_contains_key(&self, key: &[u8]) -> bool {
        T::cache_contains_key(self, key)
    }

    fn insert(&mut self, key: &[u8], value: &[u8]) -> Result<Option<Vec<u8>>> {
        T::insert(self, key, value)
    }

    fn remove(&mut self, key: &[u8]) -> Result<Option<Vec<u8>>> {
        T::remove(self, key)
    }

    fn prefetch_prefixes(&self, prefixes: &[Prefix], limit: u16) -> Result<()> {
        T::prefetch_prefixes(self, prefixes, limit)
    }

    fn iter(&self) -> Box<dyn Iterator + '_> {
        T::iter(self)
    }

    fn commit(&mut self, namespace: Namespace, version: u64) -> Result<Hash> {
        T::commit(self, namespace, version)
    }
}

#[cfg(test)]
mod _tests {
    use super::*;

    #[test]
    fn test_write_log_serialization() {
        let write_log = vec![LogEntry {
            key: b"foo".to_vec(),
            value: Some(b"bar".to_vec()),
        }];

        let raw = cbor::to_vec(write_log.clone());
        let deserialized: WriteLog = cbor::from_slice(&raw).unwrap();

        assert_eq!(write_log, deserialized);
    }
}