#![cfg_attr(not(feature = "std"), no_std)]
#![cfg_attr(not(feature = "std"), feature(alloc))]
#[cfg(not(feature = "std"))]
extern crate alloc;
extern crate elastic_array;
extern crate hash_db;
extern crate rand;
#[macro_use]
extern crate log;
#[cfg(test)]
extern crate env_logger;
#[cfg(test)]
#[macro_use]
extern crate hex_literal;
#[cfg(test)]
extern crate trie_standardmap as standardmap;
#[cfg(test)]
extern crate trie_root;
#[cfg(test)]
extern crate memory_db;
#[cfg(test)]
extern crate keccak_hasher;
#[cfg(all(feature = "std", test))]
extern crate reference_trie;
#[cfg(not(feature = "std"))]
extern crate hashmap_core;
#[cfg(feature = "std")]
use std as core_;
#[cfg(not(feature = "std"))]
use core as core_;
#[cfg(not(feature = "std"))]
use alloc::boxed::Box;
#[cfg(not(feature = "std"))]
use alloc::vec::Vec;
use core_::marker::PhantomData;
#[cfg(feature = "std")]
use std::error::Error;
#[cfg(feature = "std")]
use std::fmt;
#[cfg(feature = "std")]
pub trait MaybeDebug: fmt::Debug {}
#[cfg(feature = "std")]
impl<T: fmt::Debug> MaybeDebug for T {}
#[cfg(not(feature = "std"))]
pub trait MaybeDebug {}
#[cfg(not(feature = "std"))]
impl<T> MaybeDebug for T {}
pub mod node;
pub mod triedb;
pub mod triedbmut;
pub mod sectriedb;
pub mod sectriedbmut;
pub mod recorder;
mod fatdb;
mod fatdbmut;
mod lookup;
mod nibblevec;
mod nibbleslice;
mod node_codec;
pub use hash_db::{HashDB, HashDBRef, Hasher};
pub use self::triedb::{TrieDB, TrieDBIterator};
pub use self::triedbmut::{TrieDBMut, ChildReference};
pub use self::sectriedbmut::SecTrieDBMut;
pub use self::sectriedb::SecTrieDB;
pub use self::fatdb::{FatDB, FatDBIterator};
pub use self::fatdbmut::FatDBMut;
pub use self::recorder::{Recorder, Record};
pub use self::lookup::Lookup;
pub use self::nibbleslice::NibbleSlice;
pub use node_codec::NodeCodec;
pub type DBValue = elastic_array::ElasticArray128<u8>;
#[derive(Debug, PartialEq, Eq, Clone)]
pub enum TrieError<T, E> {
InvalidStateRoot(T),
IncompleteDatabase(T),
DecoderError(T, E),
}
#[cfg(feature = "std")]
impl<T, E> fmt::Display for TrieError<T, E> where T: MaybeDebug, E: MaybeDebug {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match *self {
TrieError::InvalidStateRoot(ref root) => write!(f, "Invalid state root: {:?}", root),
TrieError::IncompleteDatabase(ref missing) => write!(f, "Database missing expected key: {:?}", missing),
TrieError::DecoderError(ref hash, ref decoder_err) => {
write!(f, "Decoding failed for hash {:?}; err: {:?}", hash, decoder_err)
}
}
}
}
#[cfg(feature = "std")]
impl<T, E> Error for TrieError<T, E> where T: fmt::Debug, E: Error {
fn description(&self) -> &str {
match *self {
TrieError::InvalidStateRoot(_) => "Invalid state root",
TrieError::IncompleteDatabase(_) => "Incomplete database",
TrieError::DecoderError(_, ref err) => err.description(),
}
}
}
pub type Result<T, H, E> = ::core_::result::Result<T, Box<TrieError<H, E>>>;
pub type TrieItem<'a, U, E> = Result<(Vec<u8>, DBValue), U, E>;
pub trait Query<H: Hasher> {
type Item;
fn decode(self, data: &[u8]) -> Self::Item;
fn record(&mut self, _hash: &H::Out, _data: &[u8], _depth: u32) {}
}
impl<'a, H: Hasher> Query<H> for &'a mut Recorder<H::Out> {
type Item = DBValue;
fn decode(self, value: &[u8]) -> DBValue { DBValue::from_slice(value) }
fn record(&mut self, hash: &H::Out, data: &[u8], depth: u32) {
(&mut **self).record(hash, data, depth);
}
}
impl<F, T, H: Hasher> Query<H> for F where F: for<'a> FnOnce(&'a [u8]) -> T {
type Item = T;
fn decode(self, value: &[u8]) -> T { (self)(value) }
}
impl<'a, F, T, H: Hasher> Query<H> for (&'a mut Recorder<H::Out>, F) where F: FnOnce(&[u8]) -> T {
type Item = T;
fn decode(self, value: &[u8]) -> T { (self.1)(value) }
fn record(&mut self, hash: &H::Out, data: &[u8], depth: u32) {
self.0.record(hash, data, depth)
}
}
pub trait Trie<H: Hasher, C: NodeCodec<H>> {
fn root(&self) -> &H::Out;
fn is_empty(&self) -> bool { *self.root() == C::hashed_null_node() }
fn contains(&self, key: &[u8]) -> Result<bool, H::Out, C::Error> {
self.get(key).map(|x|x.is_some() )
}
fn get<'a, 'key>(&'a self, key: &'key [u8]) -> Result<Option<DBValue>, H::Out, C::Error> where 'a: 'key {
self.get_with(key, DBValue::from_slice)
}
fn get_with<'a, 'key, Q: Query<H>>(
&'a self,
key: &'key [u8],
query: Q
) -> Result<Option<Q::Item>, H::Out, C::Error> where 'a: 'key;
fn iter<'a>(&'a self) -> Result<Box<TrieIterator<H, C, Item = TrieItem<H::Out, C::Error >> + 'a>, H::Out, C::Error>;
}
pub trait TrieMut<H: Hasher, C: NodeCodec<H>> {
fn root(&mut self) -> &H::Out;
fn is_empty(&self) -> bool;
fn contains(&self, key: &[u8]) -> Result<bool, H::Out, C::Error> {
self.get(key).map(|x| x.is_some())
}
fn get<'a, 'key>(&'a self, key: &'key [u8]) -> Result<Option<DBValue>, H::Out, C::Error> where 'a: 'key;
fn insert(&mut self, key: &[u8], value: &[u8]) -> Result<Option<DBValue>, H::Out, C::Error>;
fn remove(&mut self, key: &[u8]) -> Result<Option<DBValue>, H::Out, C::Error>;
}
pub trait TrieIterator<H: Hasher, C: NodeCodec<H>>: Iterator {
fn seek(&mut self, key: &[u8]) -> Result<(), H::Out, <C as NodeCodec<H>>::Error>;
}
#[derive(Debug, PartialEq, Clone)]
pub enum TrieSpec {
Generic,
Secure,
Fat,
}
impl Default for TrieSpec {
fn default() -> TrieSpec {
TrieSpec::Secure
}
}
#[derive(Default, Clone)]
pub struct TrieFactory<H: Hasher, C: NodeCodec<H>> {
spec: TrieSpec,
mark_hash: PhantomData<H>,
mark_codec: PhantomData<C>,
}
pub enum TrieKinds<'db, H: Hasher + 'db, C: NodeCodec<H>> {
Generic(TrieDB<'db, H, C>),
Secure(SecTrieDB<'db, H, C>),
Fat(FatDB<'db, H, C>),
}
macro_rules! wrapper {
($me: ident, $f_name: ident, $($param: ident),*) => {
match *$me {
TrieKinds::Generic(ref t) => t.$f_name($($param),*),
TrieKinds::Secure(ref t) => t.$f_name($($param),*),
TrieKinds::Fat(ref t) => t.$f_name($($param),*),
}
}
}
impl<'db, H: Hasher, C: NodeCodec<H>> Trie<H, C> for TrieKinds<'db, H, C> {
fn root(&self) -> &H::Out {
wrapper!(self, root,)
}
fn is_empty(&self) -> bool {
wrapper!(self, is_empty,)
}
fn contains(&self, key: &[u8]) -> Result<bool, H::Out, C::Error> {
wrapper!(self, contains, key)
}
fn get_with<'a, 'key, Q: Query<H>>(&'a self, key: &'key [u8], query: Q) -> Result<Option<Q::Item>, H::Out, C::Error>
where 'a: 'key
{
wrapper!(self, get_with, key, query)
}
fn iter<'a>(&'a self) -> Result<Box<TrieIterator<H, C, Item = TrieItem<H::Out, C::Error>> + 'a>, H::Out, C::Error> {
wrapper!(self, iter,)
}
}
impl<'db, H, C> TrieFactory<H, C>
where
H: Hasher,
C: NodeCodec<H> + 'db
{
pub fn new(spec: TrieSpec) -> Self {
TrieFactory { spec, mark_hash: PhantomData, mark_codec: PhantomData }
}
pub fn readonly(
&self,
db: &'db HashDBRef<H, DBValue>,
root: &'db H::Out
) -> Result<TrieKinds<'db, H, C>, H::Out, <C as NodeCodec<H>>::Error> {
match self.spec {
TrieSpec::Generic => Ok(TrieKinds::Generic(TrieDB::new(db, root)?)),
TrieSpec::Secure => Ok(TrieKinds::Secure(SecTrieDB::new(db, root)?)),
TrieSpec::Fat => Ok(TrieKinds::Fat(FatDB::new(db, root)?)),
}
}
pub fn create(&self, db: &'db mut HashDB<H, DBValue>, root: &'db mut H::Out) -> Box<TrieMut<H, C> + 'db> {
match self.spec {
TrieSpec::Generic => Box::new(TrieDBMut::<_, C>::new(db, root)),
TrieSpec::Secure => Box::new(SecTrieDBMut::<_, C>::new(db, root)),
TrieSpec::Fat => Box::new(FatDBMut::<_, C>::new(db, root)),
}
}
pub fn from_existing(
&self,
db: &'db mut HashDB<H, DBValue>,
root: &'db mut H::Out
) -> Result<Box<TrieMut<H,C> + 'db>, H::Out, <C as NodeCodec<H>>::Error> {
match self.spec {
TrieSpec::Generic => Ok(Box::new(TrieDBMut::<_, C>::from_existing(db, root)?)),
TrieSpec::Secure => Ok(Box::new(SecTrieDBMut::<_, C>::from_existing(db, root)?)),
TrieSpec::Fat => Ok(Box::new(FatDBMut::<_, C>::from_existing(db, root)?)),
}
}
pub fn is_fat(&self) -> bool { self.spec == TrieSpec::Fat }
}